如何從影像資料庫中迅速搜尋出使用者所需要的影像，一直是相當熱門的研究議題，而基於內容的相似影像尋取(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。

目錄
第一章	緒論---------------------------------------------1
1.1	研究背景-----------------------------------------1
1.2	研究動機-----------------------------------------2
1.3	研究目的-----------------------------------------3
1.4	論文架構-----------------------------------------3
第二章	相關研究-----------------------------------------4
2.1	空間關係-----------------------------------------4
2.2	衡量2D-string差異性的影像相似度尋取方法----------6
2.2.1	2D-string簡介------------------------------------6
2.2.2	2D C-string簡介----------------------------------6
2.2.3	2D B-string簡介----------------------------------8
2.2.4	以2D string方法進行影像相似尋取的基本觀念--------8
2.3	衡量二元空間關係差異性的影像相似度尋取方法------10
2.3.1	ARG簡介-----------------------------------------10
2.3.2	2D-PIR簡介--------------------------------------12
2.3.3	AREM簡介----------------------------------------15
2.3.4	相關研究總結------------------------------------17
第三章	影像相似尋取方法--------------------------------18
3.1      影像相似度衡量概念------------------------------18
3.2      演算法觀念說明----------------------------------19
3.3      影像相似尋取演算法------------------------------22
3.3.1    影像相似度的初步衡量----------------------------22
3.3.2    空間位置相似度演算法前置處理--------------------23
3.3.3    空間位置相似度演算法----------------------------24
第四章	實驗與效能分析----------------------------------29
4.1      效能分析----------------------------------------29
4.2      偏移影像測試------------------------------------30
4.3      不同大小影像測試--------------------------------32
4.4      影像相似尋取正確性測試--------------------------34
第五章   結論與未來研究方向------------------------------36
附錄：性質證明-------------------------------------------37
參考文獻-------------------------------------------------42

圖目錄
圖2-1-1 拓撲關係------------------------------------------4
圖2-2-1 2D-string範例圖形---------------------------------6
圖2-2-2 2D C-string影像範例-------------------------------7
圖2-2-3 2D B-string影像範例-------------------------------8
圖2-3-1 data image範例(左圖)及其ARG表示法(右圖)----------11
圖2-3-2 query image範例(左圖)及其ARG表示法(右圖)---------11
圖2-3-3 2D投影方式(左圖)與2D-PIR graph(右圖)-------------13
圖2-3-4 Topological neighborhood graph-------------------14
圖2-3-5 Interval neighborhood graph----------------------14
圖2-3-6 AREM影像範例-------------------------------------15
圖2-3-7 AREM internal neighborhood graph-----------------16
圖3-1-1 影像X與Y相似度衡量示意圖-------------------------19
圖3-2-1 影像I與J相似度衡量示意圖-------------------------20
圖3-2-2 物件P與Q之拓撲關係-------------------------------21
圖3-3-1 影像Q--------------------------------------------22
圖3-3-2 影像I--------------------------------------------22
圖3-3-3 影像正規化示意圖---------------------------------24
圖3-3-4 f(tx)函數圖形------------------------------------26
圖3-3-5 g(tx)函數圖形------------------------------------27
圖4-1-1 不同影像張數與物件數之效能-----------------------30
圖4-2-1 偏移影像測試資料---------------------------------31
圖4-3-1 不同大小影像測試資料-----------------------------33
圖4-4-1 道路空拍影像-------------------------------------34

表目錄
表2-2-1 2D C-string空間關係符號涵意-----------------------7
表2-3-1 ARG差異成本計算方式------------------------------12
表2-3-2 運算子差異成本-----------------------------------16
表4-4-1 正確性實驗結果-----------------------------------35

[1] A.W.M. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain, “Content-Based Image Retrieval at the End of the Early Years,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol.22, no.11, pp.1349-1380, Dec.2000.
[2] P.W. Huang and C.-H. Lee, “Image Database Design Based on 9D-SPA Representation for Spatial Relations,” IEEE Trans. Knowledge and Data Eng., vol. 16, no. 12, pp.1486-1496, Dec. 2004.
[3] M.J. Egenhofer and R.D. Franzosa, “Point-Set Topological Spatial Relations,” Int’l J. Geographical Information Systems, vol. 4, no. 2, pp.161-174, 1991.
[4] E.G..M. Petrakis, C. Faloutsos and K.-I. Lin, “ImageMap:An Image Indexing Method Based on Spatial Similarity,” IEEE Trans. Knowledge and Data Eng., vol. 14, no. 5, pp.979-987, Sep./Oct. 2002.
[5] G. Petraglia, M. Sebillo, M. Tucci and G. Tortora, “Virtual Images for Similarity Retrieval in Image Databases”, IEEE Trans. Knowledge and Data Eng., vol. 13, no. 6, pp.951-967, Nov./Dec. 2001.
[6] M. Nabil, A.H.H. Ngu, and J. Shepherd, “Picture Similarity Retrieval Using the 2D Projection Interval Representation,” IEEE Trans. Knowledge and Data Eng., vol. 8, no. 4, pp.533-539, Aug. 1996.
[7] S.K. Chang, Q.Y. Shi, and C.W. Yan, “Iconic Indexing by 2-D Strings,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 9, no. 3, pp.413-428, May. 1987.
[8] S.Y. Lee and F.J. Hsu, “2D C-String: A New Spatial Knowledge Representation for Image Database Systems”, Pattern Recognition, vol. 23, pp.1077-1088, Oct.1990.
[9] P.W. Huang and Y.R. Jean, “Using 2D C+-string as Spatial Knowledge Representation for Image Database Systems,” Pattern Recognition, vol. 27, no. 9, pp.1249-1257, 1994.
[10] S. Y. Lee, M. C. Yang and J. W. Chen , “2D B-string: A Spatial Knowledge Representation for Image Database Systems,” Proc. ICSC’92 Second Int. Computer Sci. Conf., pp.609-615, 1992.
[11] H.T. Bruns and M. J. Egenhofer, “Similarity of Spatial Scenes”, Seventh International Symposium on Spatial Data Handling, Delft, The Netherlands, Taylor & Francis, London, pp.173-184, 1996.
[12] A. Stefanidis, P. Agouris, M. Bertolotto, and J.D. Carswell, “Scale- and Orientation-Invariant Scene Similarity Metrics for Image Queries,” Int’l J. Geographical Information Science, vol. 16, no. 8, pp.749-772, 2002.
[13] Gonzalez, R.C. and Woods, R.E., Digital Image Processing, Addison-Wesley, USA, 1992.
[14] Y.H. Wang, “Image indexing and similarity retrieval based on A new Spatial Relation Model,” Int’l. Conf. on Distributed Computing Systems Workshop, pp.16-19, Apr. 2001.
[15]D.H. Ballard and C.M. Brown, “Computer Vision.” Prentice Hall, USA, 1982.
[16] E.G.M Petrakis, “Design and Evaluation of Spatial Similarity Approaches for Image Retrieval,” Image and Vision Computing, vol.20, no.1, pp.59-76, Jan. 2002.
[17] B.T. Messmer, “Efficient Graph Matching Algorithms,” PhD thesis, Univ. of Bern, Switzerland, 1995. Also available at http://iamwww.unibe.ch/~fki/reserch/graphmatching.html
[18] V.N. Gudivada and V.V. Raghavan, “Design and Evaluation of Algorithms for Image Retrieval by Spatial Similarity,” ACM Trans. Information Systems, vol. 13, no.2, pp.115-144, Apr. 1995.
[19] E.A. El-Kwae and M. Kabuka, “A Robust Framework for Content-Based Retrieval by Spatial Similarity in Image Databases,” ACM Trans. Information Systems, vol. 17, no. 2, pp. 174-198, Apr. 1999.
[20] J.F. Allen, “Maintaining Knowledge about Temporal Intervals,” Comm. ACM, vol. 26, no. 11, pp.832-843, Nov. 1983.