在這篇論文中，我們提出了一個在「符號化影像資料庫」(symbolic image database, SID) 中可以表示一個符號化影像、可以作為「相似性影像檢索」(similarity image retrieval)、以及可以進行「圖形比對」(graph matching) 的架構。在此架構中，我們假設影像中的物件已經被辨識出來並且被賦予物件類別符號作為其標籤。同時物件的屬性如大小與顏色等也可以一併被擷取出來而構成更完整的影像描述。影像中物件的屬性以及存在於物件間的空間關係可以被「植基於內容的影像檢索系統」(content-based image retrieval system, CBIR) 用來作為影像檢索之用。
這個架構包含一種新的標籤有向圖“SRG”(spatial relation graph)，用來承載單一影像中所有的物件及它們之間的空間關係。每張影像可以被表示成一個SRG，並且在此SRG中標籤化頂點用來表示此圖形中的物件，而標籤化的邊則是任一對物件間的空間關係。我們也提出基於SRG結構的演算法來計算兩張影像的相似度，是藉由將兩個對應的SRG做交集運算。由於SRG結構的特性使得進行相似性檢索時具有較高的效率。
同時，為了提升檢索的效果，本架構也提出一個相似性檢索演算法“CPM”(common pattern method)，此方法藉由取得查詢影像與一個資料庫影像之間的「最大共同子影像」(maximal common subimage)來計算這兩張圖形的相似度。一個新的資料結構“CP_DAG”(common pattern directed acyclic graph) 也被設計出來以便更有效率地取得共同子影像與計算相似度，這些CP_DAG是在兩個影像做比較的過程中被產生的。
將影像表示成SRG之後，我們便可以很自然地針對兩個SRG圖形進行比對，或針對SID中「頻繁空間配置型樣」(frequent spatial patterns) 進行探勘。在比對及探勘過程中，圖形的「同構測試」(isomorphism testing) 是一項相當費時的工作。我們因此提出一個標籤圖形同構測試演算法“CISC”(class-wise isomorphism testing with limited backtracking)。此演算法適合所有需要以圖形表示並且需進行同構測試的應用，例如影像處理與型樣識別等。
我們也將本架構的演算法與現有廣為被接受的演算法加以比較，並且進行一系列的實驗以評估這些演算法的效率與效果性能。實驗結果顯示SRG在所有狀況下均具有最佳的效率。CPM則具有最佳的檢索效果，同時在物件數目及物件類別重複率增加時，具有穩定的效率。CISC在標籤圖形的表現較其他三種知名的方法為佳，具有最少的比對時間，特別當圖形沒有規律性時，CISC在非標籤圖形的表現也是最好的。

In this dissertation, a new framework is presented which supports the representation, retrieval, and matching of images in a symbolic image database (SID). The images in a SID are preprocessed to recognize the contained objects, and these objects are then assigned class symbols as object labels. The attributes of the objects such as sizes and colors are simultaneously extracted for providing more complete descriptions. The spatial relationships and the attributes of the objects are available to be utilized for discriminating images by a content-based image retrieval (CBIR) system.
To convey the information of the spatial relationships and the attributes of the contained objects in a symbolic image, a new labeled digraph “SRG” (spatial relation graph) is proposed in this framework. Each symbolic image can be represented by its corresponding derived SRG, in which a labeled vertex symbolizes one or many objects with the same attribute and a labeled arc stands for a specific spatial relationship between a pair of image objects. Being the representation of a symbolic image, the main characteristic of SRG model is its efficiency of similarity retrieval in a SID.
In addition, in order to promote the retrieval effectiveness, we also propose a method “CPM” (common pattern method) which performs similarity retrieval in a SID by finding the maximal common subimage between query image and a database image. A new data structure “CP_DAG” (common pattern directed acyclic graph) is proposed to efficiently find the common subimages and attain the similarity degree. These CP_DAG structures are constructed during the process of comparing query image and a database image.
Since an image can be represented as a derived SRG, mining the frequent spatial patterns of the images becomes of interests. During the process of graph-based data mining, graph and subgraph isomorphism testing is one of the most time-consuming tasks. Hence we proposed a new algorithm “CISC” (class-wise isomorphism testing with limited backtracking) for labeled graph isomorphism testing. This algorithm is suitable for all the applications that need to employ graphs for modeling and to perform isomorphism testing such as image processing and pattern recognition.
We have also compared the proposed algorithms with several well-known similarity retrieval and isomorphism testing algorithms. The efficiency and effectiveness of these algorithms are evaluated by a series of experiments. The experimental results show that SRG is the most efficient method, and CPM has the best average effectiveness and stable efficiency while the number of objects and the duplication rate of object symbols increasing. In addition, CISC outperforms three compared methods in efficiency for labeled graphs. For graphs with little regularity, CISC is the best even the graphs are unlabeled.

[1] I. Ahmad and W. I. Grosky, “Indexing and retrieval of images by spatial constraints,” Journal of Visual Communication and Image Representation, Vol. 14, pp. 291-320, 2003.
[2] P. Artymiuk, A. Poirrette, H. Grindley, D. Rice, and P. Willett, “A Graph-theoretic Approach to the Identification of Three-dimensional Patterns of Amino Acid Side-chains in Protein Structures,” Journal of Molecular Biology, Vol. 243, Issue 2, pp. 327-344, Oct. 1994.
[3] R. Baeza-Yates and B. Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Publishers, Inc., New York, 1999.
[4] A. D. Bimbo, Visual Information Retrieval, Morgan Kaufmann Publishers, Inc., San Francisco, 1999.
[5] P. Bollman, F. Jochum, U. Reiner, V. Weissmann, and J. Zuse, “The LIVE-Project: Retrieval experiments based on evaluation view points,” Proceedings of ACM SIGIR, pp. 213-214, 1985.
[6] C. C. Chang and S. Y. Lee, “Retrieval of Similar Pictures on Pictorial Database,” Pattern Recognition, Vol. 24, No. 7, pp. 675-680, 1991.
[7] C. C. Chang and T. C. Wu, “An exact match retrieval scheme based upon principal component analysis,” Pattern Recognition Letters, Vol. 9, No. 5, pp. 413-418, 1995.
[8] S. K. Chang, Q. Y. Shi, and C. W. Yan, “Iconic Indexing by 2-D Strings,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, No. 3, pp. 413-428, 1987.
[9] G. Chartrand and P. Zhang, Introduction to Graph Theory, McGraw Hill, New York, 2002.
[10] J. Chen, T. N. Pappas, A. Mojsilovic, and B. E. Rogowitz, “Adaptive Perceptual Color-Texture Segmentation,” IEEE Transactions on Image Processing, Vol. 14, No. 10, pp. 1524-1536, 2005.
[11] D. Conte, P. Foggia, C. Sansone, and M. Vento, “Thirty Years of Graph Matching in Pattern Recognition,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 18, No. 3, pp. 265-298, 2004.
[12] L. Cordella, P. Foggia, C. Sansone, and M. Vento, “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, No. 10, pp. 1367-1372, Oct. 2004.
[13] R. Datta, J. Li, and J. Z. Wang, “Content-Based Image Retrieval – Approaches and Trends of the New Age,” Proceedings of Multimedia Information Retrieval Conference, pp. 253-262, Nov. 2005.
[14] Y. Deng, B. S. Manjunath, C. Kenney, M. S. Moore, and H. Shin, “An Efficient Color Representation for Image Retrieval,” IEEE Transactions on Image Processing, Vol. 10, No. 1, pp. 140-147, 2001.
[15] M. J. Egnehofer and R. D. Granzasa, “On the equivalence of topological relations,” Journal of Geographic Information System, Vol. 9, No. 2, pp. 133-152, 1995.
[16] E. A. El-kwae and M. R. Kabuka, “A Robust Framework for Content-based Retrieval by Spatial Similarity in Image Databases,” ACM Transactions on Information Systems, Vol. 17, No. 2, pp. 174-198, 1999.
[17] I. El-Naga, Y. Yang, N. P. Galatsanos, R. M. Nishikawa, and N. W. Wernick, “A Similarity Learning Approach to Content-Based Image Retrieval: Application to Digital Mammograph,” IEEE Transactions on Medical Imaging, Vol. 23, No. 10, pp. 1233-1244, 2004.
[18] M. A. Eshera and K. S. Fu, “A Graph distance measure for image analysis,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 14, No. 3, pp. 353-363, 1984.
[19] P. Foggia, C. Sansone, and M. Vento, “A Performance Comparison of Five Algorithms for Graph Isomorphism,” Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representation, Italy, 2001.
[20] M. R. Gary and D. S. Johnson, Computers and Intractability: a guide to the theory of NP-completeness, W. H. Freeman and Co., 1979.
[21] C. Grant, “Data Structures and Algorithms for Graph Based Remote Sensed Image Content Storage and Retrieval,” Proceedings of IEEE Geoscience and Remote Sensing Symposium, Vol. 13, pp. 2159-2162, 2004.
[22] J. Gross and J. Yellen (editors), Handbook of Graph Theory, CRC Press, Florida, 2004.
[23] D. J. Guan, C. Y. Chou, and C. W. Chen, “Computational complexity of similarity retrieval in a pictorial database,” Information Processing Letters, Vol. 75, pp. 113-117, 2000.
[24] V. N. Gudivada, “Theta-R string: A Geometry-Based Representation for Efficient and Effective Retrieval of Images by Spatial Similarity,” IEEE Trans. Knowledge and Data Engineering, Vol. 10, No. 3, pp. 504-512, 1998.
[25] V. N. Gudivada and V. V. Raghavan, “Design and Evaluation of Algorithms for Image Retrieval by Spatial Similarity,” ACM Transactions on Information Systems, Vol.13, No. 2, pp. 115-144, 1995.
[26] D. S. Guru, P. Punitha, and P. Nagabhushan, “Archival and Retrieval of Symbolic Images: An Invariant Scheme Based on Triangular Spatial Relationship,” Pattern Recognition Letters, Vol. 24, pp. 2397-2408, 2003.
[27] D. S. Guru and P. Punitha, “An Invariant Scheme for Exact Match Retrieval of Symbolic Images Based upon Principal Component Analysis,” Pattern Recognition Letters, Vol. 25, pp. 73-86, 2004.
[28] P. Hong and T. Huang, “Mining Inexact Spatial Patterns,” Workshop on Discrete Mathematics and Data Mining, 2002.
[29] S. M. Hsieh and C. C. Hsu, “New Method for Similarity Retrieval of Iconic Image Database”, Proceedings of 2005 SPIE-IS&T Symposium on Electronic Imaging: Conference on Storage and Retrieval Methods and Applications for Multimedia, Vol. 5682, pp. 247-257, Jan. 2005.
[30] J. Huan, W. Wang, and J. Prims, “Efficient Mining of Frequent Subgraph in the Presence of Isomorphism,” University of North Carolina Computer Science Technical Report, 2003.
[31] P. W. Huang and S. K. Dai , “Design of a two-stage content-based image retrieval system using texture similarity,” Information Processing and Management, Vol. 40, pp. 81-96, 2004.
[32] A. K. Jain and A. Vilaya, “Image retrieval using color and shape,” Pattern Recognition, Vol. 29, No. 8, pp. 1233-1244, 1996.
[33] N. Kim, N. Shiffeldrim, H, Gan, and T. Schlick, “Candidates for Novel RNA Topologies”, Journal of Molecular Biology, Vol. 34, No. 1, pp. 1129-1144, 2004.
[34] M. Kuramochi and G. Karypis, “An Efficient Algorithm for Discovering Frequent Subgraphs”, IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 9, pp. 1038-1051, Sep. 2004.
[35] S. Y. Lee, M. K. Shan, and W. P. Wang, “Similarity Retrieval of Iconic Image Database,” Pattern Recognition, Vol. 22, No. 6, pp. 675-682, 1989.
[36] 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-1087, 1990.
[37] W. Li, J. You, and D. Zhang, “Texture-Based Palmprint Retrieval Using a Layered Search Scheme for Personal Identification,” IEEE Transactions on Multimedia, Vol. 7, No. 5, pp. 891-898, 2005.
[38] T. C. Lu and C. C. Chang, “Color image retrieval techniques based on color features and image bitmap,” Information Processing and Management, Vol. 43, pp. 461-472, 2007.
[39] B. D. McKay, “Nauty Users Guide,” available online at: http://cs.anu.edu.au/~bdm/nauty/, 2003.
[40] B. D. McKay, “Practical Graph Isomorphism,” Congressus Numerantium, Vol. 30, pp. 45-87, 1981.
[41] B. T. Messmer, “Efficient Graph Matching Algorithms,” Ph.D. Dissertation, University of Bern, Switzerland, 1995.
[42] E. Milios and E. G. M. Petrakis, “Shape Retrieval Based on Dynamic Programming,” IEEE Transactions on Image Processing, Vol. 9, No. 1, pp. 141-147, 2000.
[43] A. Mojsilovic, J. Hu, and E. Soljanin, “Extraction of Perceptually Important Colors and Similarity Measurement for Image Matching, Retrieval, and Analysis,” IEEE Transactions on Image Processing, Vol. 11, No. 11, 2002.
[44] D. Neumann and K. R. Genenfurtner, “Image retrieval and perceptual similarity,” ACM Transactions on Applied Perception, Vol. 3, No. 1, pp. 31-47, 2006.
[45] W. Niblack, R. Barber, W. Equitz, M. Glickner, E. Glasman, D. Petkovic, and P. Yanker. “The QBIC Project: Querying Images by Content Using Color, Texture and Shape,” Proceedings of SPIE International Symposium on Electronic Imaging: Science & Technology, Vol. 1908, Storage and Retrieval of Image and Video Databases, Feb. 1993.
[46] C. Ordonez and E. Omiecinski, “Discovering Association Rules Based on Image Content,” Proceedings of IEEE Forum on Research and Technology Advances in Digital Libraries, pp. 38-49, 1999.
[47] E. Petrakis, C. Faloutsos, and K. Lin, “ImageMap: An Image Indexing Method Based on Spatial Similarity”, IEEE Transactions on Knowledge and Data Engineering, Vol. 14, No. 5, pp. 979-987, 2002.
[48] E. G. M. Petrakis, “Design and Evaluation of Spatial Similarity Approaches for Image Retrieval,” Image and Vision Computing, Vol. 20, pp. 59-76, 2002.
[49] E. G. M. Petrakis, “Image Indexing and Retrieval Based on Spatial Relationships and Properties of Objects,” Ph. D. Dissertation, Department of Computer Science, University of Crete, Mar. 1993.
[50] P. Punitha and D. S. Guru, “An Effective and Efficient Exact Match Retrieval Scheme for Symbolic Image Database Systems Based on Spatial Reasoning: A Logarithmic Search Time Approach,” IEEE Transactions on Knowledge and Data Engineering, Vol. 18, No. 10, pp. 1368-1381, 2006.
[51] E. Di Sciascio, M. Mongiello, F. M. Donini, and L. Allegretti, “Retrieval by spatial similarity: an algorithm and a comparative evaluation,” Pattern Recognition Letters, Vol. 25, 1633-1645, 2004.
[52] A. Smeuloders, M. Worring, S. Sontini, A. Gupta, and R. Jain, “Content-Based Image Retrieval at the End of the Early Years,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, No. 12, pp. 1349-1380, 2000.
[53] D. Theobald, “Topology revisited: representing spatial relations”, International Journal of Geographical Information Science, Vol. 15, No. 8, pp. 689-705, 2001.
[54] M. Tucci, G. Costagliola, and S. K. Chang, “A Remark on NP-Completeness of Picture Matching,” Information Processing Letters , Vol. 39, pp. 242-243, 1991.
[55] T. Uchiyama and M. A. Arbib, “Color Image Segmentation Using Competitive Learning,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, No. 12, pp. 1197-1206, 1994.
[56] J. R. Ullmann, “An Algorithm for Subgraph Isomorphism,” Journal of ACM, Vol. 23, pp. 31-42 1976.
[57] G. Valiente, “Trading uninitialized space for time,” Information Processing Letters, Vol. 92, pp. 9-13, 2004.
[58] W. D. Wallis, P. Shoubridge, M. Kraetz, and D. Ray, “Graph distances using graph union,” Pattern Recognition Letters Vol. 22, pp. 701-704, 2001.
[59] J. Z. Wang, J. Li, and G. Weiderhold, “Simplicity: Semantic Sensitive Integrated Matching for Picture Libraries,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 9, pp. 947-963, 2001.
[60] Y. Wang and C. Maple, “A Novel Efficient Algorithm for Determining Maximum Common Subgraphs,” IEEE Ninth International Conference on Information Visualization (IV’05), 2005.
[61] Y. H. Wang, “Image indexing and similarity retrieval based on spatial relationship model,” Information Sciences, Vol. 154, pp. 39-58, 2003.
[62] T. Washio and H. Motoda, “State of the Art of Graph-Based Data Mining,” ACM SIGKDD Exploration Newsletters, Vol. 5, Issue 1, July 2003.
[63] X. Yan and J. Han, “gSpan: Graph-Based Substructure Pattern Mining,” Proceedings of IEEE International Conference on Data Mining (ICDM), 2002.