We propose the CXHistogram and CXSim() as an image representation and a similarity measure, respectively, for efficient partial similarity search in image databases. By using CXHistogram and CXSim(), XMage and HIPAS are introduced in this thesis as a model for partial similarity searching in image databases. XMage is an image matching method based on the partial similarity, while HIPAS is a method for subimage matching application. Region-based image retrieval is a method of retrieving partially similar images. It has been proposed as a way to accurately process queries in an image database. In region-based image retrieval, region matching is indispensable for computing the partial similarity between two images because the query processing is based upon regions instead of the entire image. A naive method of region matching is a sequential comparison between regions, which causes severe overhead and deteriorates the performance of query processing. In this thesis, a new image contents representation, called CXHistogram(Condensed eXtended Histogram), is presented in conjunction with a well-defined distance function CXSim() on the CXHistogram. The CXSim() is a new image-to-image similarity measure to compute the partial similarity between two images. It achieves the effect of comparing regions of two images by simply comparing the two images. The CXSim() reduces query space by pruning irrelevant images, and it is used as a filtering function before sequential scanning. Extensive experiments were performed on real image data to evaluate XMage and HIPAS. It provides a significant pruning of irrelevant images with no false dismissals. As a consequence, XMage and HIPAS achieve up to 5.9-fold and 4.84-fold speed-up, respectively, in search over the $R^*$-tree search followed by sequential scanning.
이미지 데이터베이스에서의 효율적인 부분 유사성 검색을 위하여 새로운 이미지 데이터 표현과 유사성 함수로서 CXHistogram과 CXSim()을 각각 제안한다. 본 논문에서 제안하는 XMage와 HIPAS는 이미지 데이터를 위한 부분 유사성 검색 모델이며 둘다 CXHistogram과 CXSim()을 사용한다. HIPAS가 부이미지(Subimage) 매칭(정합, Matching)응용을 위한 부분 유사성 검색 방법인 반면 XMage는 부분 유사성에 기반한 이미지 매칭(Image Matching)을 위한 방법이다. 영역-기반 이미지 검색은 부분적으로 유사한 이미지들을 찾는 방법으로서 이미지 데이터베이스에서 좀더 정확한 질의를 위한 한 방법으로 제안되었다. 그러나 영역-기반 이미지 검색에서는 두 이미지 사이의 부분 유사성을 계산하기 위하여 반드시 영역들 간의 유사성 검사가 이루어 져야 한다. 그 이유는 질의 처리가 이미지 전체가 아닌 영역들을 기반으로 이루어 지기 때문이다. 영역 매칭을 위한 가 장 손쉬운 방법은 영역들간의 연속적인 비교이지만 이는 시스템의 심각한 과부하(overhead)를 야기하여 질의 처리의 성능을 떨어뜨리게 된다. 본 논문은 이러한 영역들간의 연속적 비교로 말미암은 성능 저하를 해결하기 위하여 CXHistogram(Condensed eXtended Histogram)과 CXSim()을 새로운 이미지 표현과 거리함수로 제안하며, CXSim()은 XHistogram 에서 정의되는 거리함수이다. 즉, CXSim() 함수는 두 이미지 사이의 부분 유사성을 계산하기 위하여 이미지와 이미지를 비교하는 함수이며, 단지 두 이미지를 비교함으로써 두 이미지의 영역들을 비교하는 효과를 나타내는 함수이다. 이러한 CXSim()은 질의 이미지(Query Image)와 목표 이미지(Target Image) 사이의 연속적인 부분 유사성 검색전에 여과 함수로 사용되어짐으로써 관련없는 이미지들을 질의 결과에서 사전에 제거함으로써 질의 공간을 줄이게 된다. 실제 이미지 데이터를 사용하여 XMage와 HIPAS 모델을 위한 광범위한 실험이 이루어 졌다. 실험을 통하여 CXSim() 함수가 정확한 답을 제거하지 않으면서 질의 결과에 포함되지 않을 이미지들을 사전에 제거함으로써 결과적으로 아주 양호한 여과를 함을 확인할 수 있었다. 그 결과, XMage와 HIPAS는 각각 5.9배, 4.84배 속도 향상을 가져온다. 이 때 XMage와 HIPAS와의 비교 대상은 $R^*$ 트리 검색에 이어서 연속적 비교를 하는 부분 유사성 검색 모델이다.
