如何從影像資料庫中迅速搜尋出使用者所需要的影像，一直是相當熱門的研究議題，而基於內容的相似影像尋取(Content-Based Image Retrieval, CBIR)技術則為目前影像資料庫系統的設計趨勢，而影像內容大致可分為低階視覺特徵(low-level visual feature)和高階關係特徵(high-level relationship feature)。一般利用高階關係特徵來衡量影像相似度的CBIR技術多採用逐一比較兩影像中相對應物件的二元空間關係(binary spatial relationships)，來衡量影像間的相似度，而所謂的空間關係包含拓撲(topology)、方向(direction)及距離(distance)三種關係。若影像中有n個物件，可產生二元空間關係至少有n(n-1)/2種。因此，通常影像相似衡量運算所需要時間複雜度為O(n^2)。 本篇論文提出一個更快速的影像相似度尋取的方法Position Similarity Matching (PSM)，利用將影像A轉換成影像B時所需要的最小成本來衡量兩者之相似度。成本的衡量方式為計算兩影像中相對應物件質心座標位置與Minimum Bounding Rectangles (MBRs)長寬的差異，並利用平移的方式，將一影像中整體物件移動到一個最佳位置，使兩影像之總差異成本為最小，以此做為兩影像相似度的依據。此衡量相似度的方法考量到影像相似度衡量上的偏移不變性(translation invariance)及尺度不變性(scale invariance)，且能夠同時衡量到兩影像中相對應物件間的三種空間關係相似度，而整體演算法所需要的時間複雜度只為O(nlogn)。最後，我們從實驗結果中證實了PSM演算法的運算效率及正確性，也證明了此方法能夠達到影像相似度衡量上的偏移不變性及尺度不變性。 How to search out the image that the user needs rapidly from the image databases, it has been a quite hot research topic all the time. In this field, Content-Based Image Retrieval (CBIR) technology is a trend on the image databases design at present. Generally, the CBIR technology to measure similarity between two images with their high-level relationships features mostly compares corresponding attributes and binary spatial relationships of objects in two images one by one and then calculate the difference between them to measures their similarity. The high-level relationships mentioning above usually include topology, direction and distance. When there are n objects in a image, the number of kinds of binary spatial relationships will be n(n-1)/2 at least. Thus, the time complexity of similarity measure usually is O(n^2). In this paper, we propose a faster method, Position Similarity Matching (PSM), to mesure the similarity between two images by calculating the difference of the coordinates of centroids and Minimum Bounding Rectangles (MBRs) of corresponding objects in them and consider to three kinds similarity of binary spatial relationships of the images at the same time. In addition, the time complexity needed is only O(nlogn). Finally, some experiments are performed to demonstrate this algorithm has better performance and accuracy and possess the properties of translation invariance and scale invariance。
