| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Efficient Matching and Indexing of Graph Models in Content-Based Retrieval
October 2001 (vol. 23 no. 10)
pp. 1089-1105
—In retrieval from image databases, evaluation of similarity, based both on the appearance of spatial entities and on their mutual relationships, depends on content representation based on Attributed Relational Graphs. This kind of modeling entails complex matching and indexing, which presently prevents its usage within comprehensive applications. In this paper, we provide a graph-theoretical formulation for the problem of retrieval based on the joint similarity of individual entities and of their mutual relationships and we expound its implications on indexing and matching. In particular, we propose the usage of metric indexing to organize large archives of graph models, and we propose an original look-ahead method which represents an efficient solution for the (sub)graph error correcting isomorphism problem needed to compute object distances. Analytic comparison and experimental results show that the proposed look-ahead improves the state-of-the-art in state-space search methods and that the combined use of the proposed matching and indexing scheme permits for the management of the complexity of a typical application of retrieval by spatial arrangement.
[1] H.A. Almohamad and S.O. Duffuaa, “A Linear Programming Approach for the Weighted Graph Matching Problem,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 5, pp. 522-525, May 1993.
[2] S. Berretti, A. Del Bimbo, and E. Vicario, “Modeling Spatial Relationships between Color Clusters,” Pattern Analysis and Applications, vol. 4, no.2/3, pp. 83-92, June 2001.
[3] S. Berretti, A. Del Bimbo, and E. Vicario, “Spatial Arrangement of Color in Retrieval by Visual Similarity,” Pattern Recognition, to appear.
[4] S. Berretti, A. Del Bimbo, and E. Vicario, “Weighting Spatial Arrangement of Colors in Content Based Image Retrieval,” Proc. IEEE Int'l Conf. Multimedia Computing and Systems (ICMCS' 99), June 1999.
[5] S. Berretti, A. Del Bimbo, and E. Vicario, “Modeling Spatial Relationships between Color Sets,” Proc. IEEE Int'l Workshop Content Based Access of Image and Video Libraries (CBAIVL '00), June 2000.
[6] S. Berretti, A. Del Bimbo, and E. Vicario, “Weighted Walkthroughs between Extended Entities for Retrieval by Spatial Arrangement,” IEEE Trans. Multimedia, to appear.
[7] I.M. Bomze, M. Budinich, P.M. Pardalos, and M. Pelillo, “The Maximum Clique Problem,” Handbook of Combinatorial Optimization, supplement volume A, D.Z. Du and P.M. Pardalos, eds., Boston: Kluwer Academic, 1999.
[8] T. Bozkaya and M. Özsoyoglu, “Indexing Large Metric Spaces for Similarity Search Queries,” ACM Trans. Database Systems, vol. 24, no. 3, pp. 361-404, Sept. 1999.
[9] S. Brin, “Near Neighbour Search in Large Metric Spaces,” Proc. 21st Int'l Conf. Very Large Data Bases, pp. 574-584, Sept. 1995.
[10] 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-427, July 1987.
[11] S.K. Chang and E. Jungert, “Pictorial Data Management Based upon the Theory of Symbolic Projections,” J. Visual Languages and Computing, vol. 2, no. 2, pp. 195-215, June 1991.
[12] J.-Y. Chen, C.A. Bouman, and J.C. Dalton, “Hierarchical Browsing and Search of Large Image Databases,” IEEE Trans. Image Processing, vol. 9, no. 3, pp. 442-455, Mar. 2000.
[13] T. Chiueh, “Content Based Image Indexing,” Proc. 20th Int'l Conf. Very Large Data Bases, pp. 582-593, Sept. 1994.
[14] P. Ciaccia, M. Patella, and P. Zezula, “M-Tree: An Efficient Access Method for Similarity Search in Metric Spaces,” Proc. Int'l Conf. Very Large Data Bases, 1997.
[15] P. Ciaccia, M. Patella, and P. Zezula, “Processing Complex Similarity Queries with Distance-Based Access Methods,” Proc. Sixth Int'l Conf. Extending Database Technology, Mar. 1998.
[16] A. Del Bimbo, Visual Information Retrieval. Academic Press, 1999.
[17] A. Del Bimbo, M. Mugnaini, P. Pala, and F. Turco, “Visual Querying by Color Perceptive Regions,” Pattern Recognition, vol. 31, no. 9, pp. 1241-1253, 1998.
[18] A. Del Bimbo and E. Vicario, “Using Weighted Spatial Relationships in Retrieval by Visual Contents,” IEEE Workshop Content-Based Access of Image and Video Databases, June 1998.
[19] M. De Marsico, L. Cinque, and S. Levialdi, “Indexing Pictorial Documents by Their Content: A Survey of Current Techniques,” Image and Vision Computing, vol. 15, pp. 119-141, Feb. 1997.
[20] M.J. Egenhofer and R. Franzosa, “Point-Set Topological Spatial Relations,” Int'l J. Geographical Information Systems, vol. 5, no. 2, pp. 161-174, 1991.
[21] M.J. Egenhofer and R. Franzosa, “On the Equivalence of Topological Relations,” Int'l J. Geographical Information Systems, vol. 9, no. 2, pp. 133-152, 1992.
[22] M.A. Eshera and K.-S. Fu, “A Graph Distance Measure for Image Analysis,” IEEE Trans. Systems, Man, Cybernetics, vol. 14, pp. 398-407, May/June 1984.
[23] C. Faloutsos, Searching Multimedia Databases by Content. Kluwer Academic, 1996.
[24] U. Frank, “Qualitative Spatial Reasoning about Distances and Directions in Geographic Space,” J. Visual Languages and Computing, vol. 3, no. 3, pp. 343-371, 1992.
[25] C. Freska, “Using Orientation Information for Qualitative Spatial Reasoning,” Proc. Int'l Conf. Methods for Spatio-Temporal Reasoning in GIS, Sept. 1992.
[26] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness.New York: W.H. Freeman, 1979.
[27] S. Gold and A. Rangarajan, “A Graduated Assignment Algorithm for Graph Matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 4, pp. 377-388, Apr. 1996.
[28] 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, Apr. 1995.
[29] V.N. Gudivada and V.V. Raghavan, “Special Issue on Content Based Image Retrieval Systems,” Computer, vol. 28, no. 9, Sept. 1995.
[30] A. Gupta and R. Jain, “Visual Information Retrieval,” Comm. ACM, vol. 40, no. 5, pp. 70-79, May 1997.
[31] J. Huang, S.R. Kumar, M. Mitra, W. Zhu, and R. Zabih, Image Indexing Using Color Correlograms Proc. Computer Vision and Pattern Recognition, pp. 762-768, 1997.
[32] E. Jungert, “Qualitative Spatial Reasoning for Determination of Object Relations Using Symbolic Interval Projections,” IEEE Int'l Workshop Visual Languages, pp. 83-87, 1993.
[33] S.Y. Lee and F. Hsu, “Spatial Reasoning and Similarity Retrieval of Images using 2D C-Strings Knowledge Representation,” Pattern Recognition, vol. 25, no. 3, pp. 305-318, 1992.
[34] R. Mehrotra and J.E. Gary, “Similar-Shape Retrieval in Shape Data Management,” IEEE Computer, pp. 57-62, Sept. 1995.
[35] B.T. Messmer, “Efficient Graph Matching Algorithms for Preprocessed Model Graphs,” PhD thesis, Institut fur Informatik und Angewandte Matheatik, Universitat Bern, Switzerland, 1995.
[36] B.T. Messmer and H. Bunke, “A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 5, pp. 493-504, May 1998.
[37] A. Nagasaka and Y. Tanaka, “Automatic Video Indexing and Full Video Search for Object Appearances,” IFIP Trans. Visual Database Systems II, Knuth and Wegner, eds., pp. 113-127, 1992.
[38] C.H. Papadimitriu and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1987.
[39] M. Pelillo, K. Siddiqi, and S.W. Zucker, “Matching Hierarchical Structures Using Association Graphs,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 21, no. 11, pp. 1105-1120, 1999.
[40] E.G.M. Petrakis and C. Faloutsos, “Similarity Searching in Medical Image Databases,” IEEE Trans. Knowledge and Data Eng., vol. 9, no. 3, pp. 435-447, May/June 1997.
[41] K.E. Price, “Relaxation Matching Techniques—A Comparison,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 7, no. 5, pp. 617-623, Sept. 1985.
[42] Y. Rui, T.S. Huang, M. Ortega, and S. Mehrotra, “Relevance Feednack: A Power Tool for Interactive Conten-Based Image Retrieval,” IEEE Trans. Circuits, and Video Technology, Sept. 1998.
[43] G. Ciocca and R. Schettini, “Using a Relevance Feedback Mechanism to Improve Content Based Image Retrieval,” Proc. Visual '99: Information and Information Systems, pp. 107-114, 1999.
[44] K. Sengupta and K.L. Boyer, “Organizing Large Structural Modelbases,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 4, pp. 321-332, Apr. 1995.
[45] L.G. Shapiro and R.M. Haralick, “Structural Descriptions and Inexact Matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 3, no. 5, pp. 504-519, Sept. 1981.
[46] A. Shokoufandeh, S.J. Dickinson, K. Siddiqi, and S.W. Zucker, “Indexing Using Spectral Encoding of Topological Structure,” Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, June 1999.
[47] K. Siddiqi and B.B. Kimia, “Parts of Visual Form: Computational Aspects,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 3, Mar. 1995.
[48] J.R. Smith and S.F. Chang, “Automated Image Retrieval Using Color and Texture,” Technical Report 414-95-20, Columbia Univ., July 1995.
[49] J.R. Smith and S.F. Chang, “VisualSEEk: A Fully Automated Content-Based Image Query System,” ACM Multimedia '96, Nov. 1996.
[50] A. Soffer and H. Samet, “Handling Multiple Instances of Symbols in Pictorial Queries by Image Similarity,” Proc. Int'l Workshop Image Databases and Multimedia Search (IDB-MMS `96), Aug. 1996.
[51] Y. Tao and W.I. Grosky, “Spatial Color Indexing: A Novel Approach for Content-Based Image Retrieval,” Proc. IEEE Int'l Conf. Multimedia Computing and Systems, June 1999.
[52] W.-H. Tsai and K.-S. Fu, “Error-Correcting Isomorphisms of Attributed Relational Graphs for Pattern Analysis,” IEEE Trans. Systems, Man, Cybernetics, vol. 12, pp. 657-767, Dec. 1979.
[53] J.K. Uhlmann, “Satisfying General Proximity/Similarity Queries with Metric Trees,” Information Processing Letters, vol. 40, no. 4, pp. 175-179, Nov. 1991.
[54] J.R. Ullman, “An Algorithm for Subgraph Isomorphism,” J. ACM, vol. 23, no. 1, Jan. 1976.
[55] S. Umeyama, “An Eigendecomposition Approach to Weighted Graph Matching Problems,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 10, no. 5, pp. 695-703, Sept. 1988.
[56] E. Vicario, Image Description and Retrieval. Plenum Press, 1998.
[57] E. Vicario and W.X. He, “Weighted Walkthroughs in Retrieval by Contents of Pictorial Data,” Proc. Int'l Conf. Image Analysis and Processing, Sept. 1997.
[58] A.K.C Wong, M. You, and S.C. Chan, “An Algorithm for Graph Optimal Monomorphism,” IEEE Trans. Systems, Man and Cybernetics, vol. 20, no. 3, pp. 628-636, May/June 1990.
[59] Web Museum:http:/www.oir.ucf.edu. 2001.
Citation:
S. Berretti, A. Del Bimbo, E. Vicario, "Efficient Matching and Indexing of Graph Models in Content-Based Retrieval," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 10, pp. 1089-1105, Oct. 2001, doi:10.1109/34.954600
