×

Symbolic image indexing and retrieval by spatial similarity: An approach based on B-tree. (English) Zbl 1132.68657

Summary: The problem of indexing symbolic images based on spatial similarity is addressed. A model based on modified triangular spatial relationship (TSR) and B-tree is proposed. The model preserves TSR among the components in a symbolic image by the use of quadruples. A Symbolic Image Database is created through the construction of B-tree, an efficient multilevel indexing structure. A methodology to retrieve similar symbolic images for a given query image is also presented. The presented retrieval model has logarithmic search time complexity. The study made in this work reveals that the model bears various advantages when compared to other existing models and it could be extended towards dynamic databases. An extensive experimentation is conducted on various symbolic images and also on the ORL and YALE face databases. The results of the experimentation conducted have revealed that the proposed scheme outperforms the existing algorithms and is of practical relevance.

MSC:

68T10 Pattern recognition, speech recognition
68P20 Information storage and retrieval of data

Software:

Yale Face; ORL face
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gudivada, V. N., \( \Theta\) R-string: a geometry-based representation for efficient and effective retrieval of images by spatial similarity, IEEE Trans. Knowledge Data Eng., 10, 3, 504-512 (1998)
[2] D. Maltoni, D. Maio, A.K. Jain, S. Prabhakar, Handbook of Fingerprint Recognition, Springer Professional Computing, 2005.; D. Maltoni, D. Maio, A.K. Jain, S. Prabhakar, Handbook of Fingerprint Recognition, Springer Professional Computing, 2005. · Zbl 1027.68114
[3] D.S. Guru, Towards accurate recognition of objects employing a partial knowledge base: some new approaches, Ph.D. Thesis, Department of Studies in Computer Science, University of Mysore, Manasagangothri, Mysore, India, 2000.; D.S. Guru, Towards accurate recognition of objects employing a partial knowledge base: some new approaches, Ph.D. Thesis, Department of Studies in Computer Science, University of Mysore, Manasagangothri, Mysore, India, 2000.
[4] Grosky, W.; Mehrotra, R., Index-based object recognition in pictorial data management, Comput. Vision Graphics Image Process., 52, 3, 416-436 (1990)
[5] R. Dinesh, D.S. Guru, Mathematical morphology based corner detection scheme: a non-parametric approach. in: Fourth Indian Conference on Computer Vision, Graphics and Image Processing (ICVGIP-2004) held at Science City, Kolkata, India, December 16-18, 2004, pp. 76-81.; R. Dinesh, D.S. Guru, Mathematical morphology based corner detection scheme: a non-parametric approach. in: Fourth Indian Conference on Computer Vision, Graphics and Image Processing (ICVGIP-2004) held at Science City, Kolkata, India, December 16-18, 2004, pp. 76-81.
[6] Gudivada, V. N.; Raghavan, V. V., Modeling and retrieving images by content, Information Processing and Management, 33, 4, 427-452 (1997)
[7] Majumdar, A. K.; Bhattacharya, I.; Saha, A. K., An object-oriented fuzzy data model for similarity detection in image databases, IEEE Trans. Knowledge and Data Engineering, 14, 5, 1186-1189 (2002)
[8] Fischler, M. A.; Elschlager, R. A., The representation and matching of pictorial structures, IEEE Trans. Comput., 22, 1, 67-92 (1973)
[9] Chang, S. K.; Yan, C. W.; Dimitroff, D. C.; Arndt, T., An intelligent image database system, IEEE Trans. Software Eng., 14, 5, 681-688 (1988)
[10] Guru, D. S.; Nagabhushan, P., Triangular spatial relationship: a new approach for spatial knowledge representation, Pattern Recognition Lett., 22, 9, 999-1006 (2001) · Zbl 0988.68184
[11] P. Punitha, IARS: image archival and retrieval system, Ph.D. Thesis, Department of Studies in Computer Science, University of Mysore, Manasagangothri, Mysore, Karnataka, India, 2006.; P. Punitha, IARS: image archival and retrieval system, Ph.D. Thesis, Department of Studies in Computer Science, University of Mysore, Manasagangothri, Mysore, Karnataka, India, 2006.
[12] Chock, M.; Cardenas, A. F.; Klinger, A., Database structure and manipulation capabilities of picture database management system (PICDMS), IEEE Trans. Pattern Anal. Mach. Intell., 9, 3, 413-428 (1984)
[13] Samet, H., The quadtree and related data structures, ACM Comput. Surv., 16, 2, 187-260 (1984)
[14] A. Guttman, R-trees: a dynamic index structure for spatial searching, in: Proceedings of ACM-SIGMOD International Conference on Management of Data, 1984, pp. 47-57.; A. Guttman, R-trees: a dynamic index structure for spatial searching, in: Proceedings of ACM-SIGMOD International Conference on Management of Data, 1984, pp. 47-57.
[15] Chang, C. C.; Lin, D. C., A spatial data representation: an adaptive 2D-H string, Pattern Recognition Lett., 17, 2, 175-185 (1996)
[16] Chang, S. K.; Shi, Q. Y.; Yan, C. W., Iconic indexing by 2D strings, IEEE Trans. Pattern Anal. Mach. Intell., 9, 5, 413-428 (1987)
[17] S.K. Chang, Y. Li, Representation of multi resolution symbolic and binary pictures using 2D-H strings, in: Proceedings of the IEEE Workshop on Languages for Automata. MD, 1988, pp. 190-195.; S.K. Chang, Y. Li, Representation of multi resolution symbolic and binary pictures using 2D-H strings, in: Proceedings of the IEEE Workshop on Languages for Automata. MD, 1988, pp. 190-195.
[18] Chang, Y. I.; Ann, H. Y., A note on adaptive 2D-H strings, Pattern Recognition Lett., 20, 1, 15-20 (1999) · Zbl 0920.68115
[19] E. Jungert, Extended symbolic projection used in a knowledge structure for spatial reasoning, in: Proceedings of 4th International Conference on Pattern Recognition, Springer, March 20-30, 1988, pp. 343-351.; E. Jungert, Extended symbolic projection used in a knowledge structure for spatial reasoning, in: Proceedings of 4th International Conference on Pattern Recognition, Springer, March 20-30, 1988, pp. 343-351.
[20] Chang, S. K.; Jungert, E.; Li, Y., Representation and retrieval of symbolic pictures using generalized 2D strings, (SPIE Proceedings on Visual Communications and Image Processing (1989), Philadelphia), 1360-1372
[21] Lee, S. Y.; Hsu, F. J., 2D-C string: a new spatial knowledge representation for image database system, Pattern Recognition, 23, 10, 1077-1087 (1990)
[22] Lee, S. Y.; Hsu, F. J., Picture algebra for spatial reasoning of iconic images represented in 2D C string, Pattern Recognition Lett., 12, 7, 425-435 (1991)
[23] Lee, A. J.T.; Chiu, H. P., 2D Z-string: a new spatial knowledge representation for image databases, Pattern Recognition Lett., 24, 16, 3015-3026 (2003)
[24] Huang, P. W.; Jean, Y. R., Using 2D \(C^+\) strings as spatial knowledge representation for image database systems, Pattern Recognition, 27, 9, 1249-1257 (1994)
[25] Lee, S. Y.; Shan, M. K.; Yang, W. P., Similarity retrieval of iconic image databases, Pattern Recognition, 22, 6, 675-682 (1989)
[26] Lee, S. Y.; Hsu, F. J., Spatial reasoning and similarity retrieval of images using 2D C string knowledge representation, Pattern Recognition, 25, 3, 305-318 (1992)
[27] Lee, S. Y.; Hsu, F. J., Spatial knowledge representation for iconic image database, (Chen, C. H.; Pan, L. F.; Wang, P. S.P., Handbook of Pattern Recognition and Computer Vision (1993), World Scientific Publishing Company: World Scientific Publishing Company Singapore), 839-861
[28] S.K. Chang, C. Lee, C. Dow, A 2D string matching algorithm for conceptual pictorial queries, in: Image Storage and Retrieval Systems, SPIE, vol. 1662, 1992, pp. 47-58.; S.K. Chang, C. Lee, C. Dow, A 2D string matching algorithm for conceptual pictorial queries, in: Image Storage and Retrieval Systems, SPIE, vol. 1662, 1992, pp. 47-58.
[29] J. Drakopoulos, P. Constantopoulos, An exact algorithm for 2D string matching, Technical Report 21, Institute of Computer Science, Foundation for Research and Technology, Heraklion, Greece, 1989.; J. Drakopoulos, P. Constantopoulos, An exact algorithm for 2D string matching, Technical Report 21, Institute of Computer Science, Foundation for Research and Technology, Heraklion, Greece, 1989.
[30] E.G.M. Petrakis, Image representation, indexing and retrieval based on spatial relationships and properties of objects, Ph.D. Dissertation, Department of Computer Science, University of Crete, Germany, 1993.; E.G.M. Petrakis, Image representation, indexing and retrieval based on spatial relationships and properties of objects, Ph.D. Dissertation, Department of Computer Science, University of Crete, Germany, 1993.
[31] Chang, C. C.; Lee, C. F., Relative coordinates oriented symbolic string for spatial relationship retrieval, Pattern Recognition, 28, 4, 563-570 (1995)
[32] Petraglia, G.; Sebillo, M.; Tucci, M.; Tortora, G., Virtual images for similarity retrieval in image databases, IEEE Trans. Knowledge Data Eng., 13, 6, 951-967 (2001)
[33] Petraglia, G.; Sebillo, M.; Tucci, M.; Tortora, G., A normalized index for image databases, (Chang, S. K.; Jungert, E.; Tortora, G., Intelligent Image Database Systems (1996), World Scientific: World Scientific Singapore)
[34] Huang, P. W.; Jean, Y. R., Spatial reasoning and similarity retrieval for image database systems based on RS-strings, Pattern Recognition, 29, 12, 2103-2114 (1996)
[35] Sciascio, D. E.; Mongiello, M.; Donini, F. M.; Allegretti, L., Retrieval by spatial similarity: an algorithm and comparative evaluation, Pattern Recognition Lett., 25, 14, 1633-1645 (2004)
[36] Gudivada, V. N.; Raghavan, V. V., Design and evaluation of algorithms for image retrieval by spatial similarity, ACM Trans. Inf. Systems, 13, 2, 115-144 (1995)
[37] Segupta, K.; Boyer, K. L., Organising large structural modelbases, IEEE Trans. Pattern Recognition Mach. Intell., 17, 4, 321-332 (1995)
[38] B.T. Messmer, H. Bunke, Fast error correcting graph isomorphism based on model precompilation, Technical Report, University of Bern, Switzerland, 1996.; B.T. Messmer, H. Bunke, Fast error correcting graph isomorphism based on model precompilation, Technical Report, University of Bern, Switzerland, 1996.
[39] El-Kwae, E. A.; Kabuka, M., A robust framework for content based retrieval by spatial similarity in image databases, ACM Trans. Inf. Systems, 17, 2, 174-198 (1999)
[40] Shapiro, L. G.; Haralick, R. M., Structural descriptions and inexact matching, IEEE Trans. Pattern Anal. Mach. Intell., 3, 5, 504-519 (1981)
[41] E.G.M. Petrakis, Fast retrieval by spatial structure in images databases, Technical Report, Department of Electronic and Computer Engineering, Technical University of Crete, Crete, Greece, 2002.; E.G.M. Petrakis, Fast retrieval by spatial structure in images databases, Technical Report, Department of Electronic and Computer Engineering, Technical University of Crete, Crete, Greece, 2002.
[42] Petrakis, E. G.M., Imagemap: an image indexing method based on spatial similarity, IEEE Trans. Knowledge Data Eng., 14, 5, 979-987 (2002)
[43] Petrakis, E. G.M.; Faloustsos, C., Similarity searching in medical image databases, IEEE Trans. Knowledge Data Eng., 9, 3, 435-447 (1997)
[44] Korn, P.; Sidiropulos, N.; Faloustsos, C.; Siegel, E.; Proptopapas, Z., Fast and effective retrieval of medical tumor shapes, IEEE Trans. Knowledge Data Eng., 10, 6, 889-904 (1998)
[45] Papadias, D.; Mamoulis, N.; Delis, V., Algorithms for querying by spatial structure, (Proceedings of 24th VLDB Conference (1998), New York: New York USA), 546-557
[46] El-Kwae, E. A.; Kabuka, M., Efficient content based indexing of large image databases, ACM Trans. Inf. Systems, 18, 2, 171-210 (2000)
[47] Messmer, B. T.; Bunke, H., A new algorithm for error-tolerant subgraph isomorphism detection, IEEE Trans. Pattern Anal. Mach. Intell., 20, 5, 493-504 (1998)
[48] T.Y. Hou, P. Lui, M.Y. Chui, A content based indexing technique using relative geometry features, in: Proceedings of Image Storage and Retrieval Systems, SPIE, vol. 1662, 1992, pp. 59-68.; T.Y. Hou, P. Lui, M.Y. Chui, A content based indexing technique using relative geometry features, in: Proceedings of Image Storage and Retrieval Systems, SPIE, vol. 1662, 1992, pp. 59-68.
[49] Zhou, X. M.; Ang, C. H.; Ling, T. W., Image retrieval based on object’s orientation spatial relationship, Pattern Recognition Lett., 22, 5, 469-477 (2001) · Zbl 1010.68866
[50] Chang, C. C.; Lee, S. Y., Retrieval of similar pictures on pictorial database, Pattern Recognition, 24, 7, 675-680 (1991)
[51] Bhatia, S. K.; Sabharwal, C. L., A fast implementation of a perfect hash function for picture objects, Pattern Recognition, 27, 3, 365-376 (1994)
[52] Sabharwal, C. L.; Bhatia, S. K., Perfect hash table algorithm for image databases using negative associated values, Pattern Recognition, 28, 7, 1091-1101 (1995)
[53] Zhou, X. M.; Ang, C. H., Retrieving similar pictures from pictorial database by an improved hashing table, Pattern Recognition Lett., 18, 9, 751-758 (1997)
[54] Sabharwal, C. L.; Bhatia, S. K., Image databases and near perfect hash table, Pattern Recognition, 30, 11, 1867-1876 (1997)
[55] Cook, C. R.; Oldehoeft, R., A letter oriented minimal perfect hashing function, ACM SIGPlan Notices, 17, 9, 18-27 (1982)
[56] Cichelli, R., Minimal perfect hash functions made simple, Commun. ACM, 23, 1, 17-19 (1980)
[57] Wu, T. C.; Cheng, J., Retrieving similar pictures from iconic database using G-Tree, Pattern Recognition Lett., 18, 6, 595-603 (1997)
[58] Kumar, A., G-tree: a new data structure for organizing multidimensional data, IEEE Trans. Knowledge Data Eng., 6, 2, 341-347 (1994)
[59] Chang, C. C., Spatial match retrieval of symbolic pictures, Inf. Sci. Eng., 7, 3, 405-422 (1991)
[60] Chang, C. C.; Wu, T. C., An exact match retrieval scheme based upon principal component analysis, Pattern Recognition Lett., 16, 5, 465-470 (1995)
[61] Lee, S. Y.; Shan, M. K., Access methods of image databases, Pattern Recognition Artif. Intell., 4, 1, 27-44 (1990)
[62] Chang, C. C.; Jiang, J. H., A fast spatial match retrieval using a superimposed coding technique, (Proceedings of the International Symposium on Advanced Database Technologies and their Integration (1994), Nara: Nara Japan), 71-78
[63] Chang, J. W.; Kim, Y. J.; Chang, K. J., A spatial match representation scheme for indexing and querying in iconic image databases, (Proceedings of Conference on Information and Knowledge Management (1997), Las Vegas, NV: Las Vegas, NV USA), 169-176
[64] Chang, Y. I.; Yang, B. Y., A prime-number-based matrix strategy for efficient iconic indexing of symbolic pictures, Pattern Recognition, 30, 10, 1745-1757 (1997)
[65] Chang, Y. I.; Ann, H. Y.; Yeh, W. H., A unique-ID-based matrix strategy for efficient iconic indexing of symbolic pictures, Pattern Recognition, 33, 8, 1263-1276 (2000)
[66] Chang, Y. I.; Yang, B. Y.; Yeh, W. H., A generalized prime number based matrix for efficient iconic indexing of symbolic pictures, Pattern Recognition Lett., 22, 6/7, 657-666 (2001) · Zbl 1010.68888
[67] Chang, Y. I.; Yang, B. Y.; Yeh, W. H., A bit pattern based matrix strategy for efficient iconic indexing of symbolic pictures, Pattern Recognition Lett., 24, 1-3, 537-545 (2003)
[68] Guru, D. S.; Punitha, P., An invariant scheme for exact match retrieval of symbolic images based upon principal component analysis, Pattern Recognition Lett., 25, 1, 73-86 (2004)
[69] Punitha, P.; Guru, D. S., An effective and efficient exact match retrieval scheme for image database systems based on spatial reasoning: a logarithmic search time approach, IEEE Trans. Knowledge Data Eng., 18, 10, 1368-1381 (2006)
[70] Punitha, P.; Guru, D. S., An invariant scheme for exact match retrieval of symbolic images: triangular spatial relationship based approach, Pattern Recognition Lett., 26, 7, 893-907 (2005)
[71] Guru, D. S.; Punitha, P.; Nagabhushan, P., Archival and retrieval of symbolic images: an invariant scheme based on triangular spatial relationship, Pattern Recognition Lett., 24, 14, 2397-2408 (2003) · Zbl 1052.68026
[72] Bentley, J. L., Multidimensional binary search trees used for associative searching, Commun. ACM, 18, 9, 509-517 (1975) · Zbl 0306.68061
[73] J.T. Robinson, The KDB tree: a search structure for large multidimensional dynamic indexes, in: Proceedings of ACM SIGMOD Conference Ann Arbor, MI, 1981, pp. 10-18.; J.T. Robinson, The KDB tree: a search structure for large multidimensional dynamic indexes, in: Proceedings of ACM SIGMOD Conference Ann Arbor, MI, 1981, pp. 10-18.
[74] Nievergelt, J.; Hinterberger, H.; Sevick, K., The gridfile: an adaptable, symmetric multikey file structure, ACM Trans. Database Systems, 9, 1, 38-71 (1984)
[75] Hinrichs, K., Implementation of the grid file: design concepts and experience, BIT, 25, 4, 569-592 (1985) · Zbl 0578.68021
[76] Rothnie, J. B.; Lozano, T., Attribute based file organization in a paged memory environment, Commun. ACM, 17, 2, 63-69 (1974)
[77] Dandamudi, S. P.; Sorenson, P. G., An empirical performance comparison of some variations of the k-d tree and bd tree, Comput. Inf. Sci., 14, 3, 134-158 (1985)
[78] Bukhard, W., Interpolation based index maintenance, BIT, 23, 3, 274-294 (1983) · Zbl 0513.68056
[79] M. Ouskel, P. Scheuermann, Storage mappings for multidimensional linear dynamic hashing, in: Proceedings of 2nd ACM SIGACT-SIGMOD Symposium, Principles of Database systems, Atlanta, 1983, pp. 90-105.; M. Ouskel, P. Scheuermann, Storage mappings for multidimensional linear dynamic hashing, in: Proceedings of 2nd ACM SIGACT-SIGMOD Symposium, Principles of Database systems, Atlanta, 1983, pp. 90-105.
[80] N. Katayama, S. Satoh, The SR-tree: an index structure for high dimensional nearest neighbor queries, in: Proceedings of ACM SIGMOD, 1997, pp. 369-380.; N. Katayama, S. Satoh, The SR-tree: an index structure for high dimensional nearest neighbor queries, in: Proceedings of ACM SIGMOD, 1997, pp. 369-380.
[81] Chang, C. C.; Wu, T. C., Retrieving the most similar symbolic pictures from pictorial databases, Inf. Process. Manage., 28, 5, 581-588 (1992)
[82] Wu, T. C.; Chang, C. C., Application of geometric hashing to iconic database retrieval, Pattern Recognition Lett., 15, 9, 871-876 (1994)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.