Layout indexing of trademark images

ABSTRACT

Ensuring the uniqueness of trademark images and protecting their identities are the most important objectives for the trademark registration process. To prevent trademark infringement, each new trademark must be compared to a database of existing trademarks. Given a newly designed trademark image, trademark retrieval systems are not only concerned with finding images with similar shapes but also locating images with similar layouts. Performing a linear-search, i.e., computing the similarity between the query and each database entry and selecting the closest one, is inefficient for large database systems. An effective and efficient indexing mechanism is, therefore, essential to select a small collection of candidates. This paper proposes a framework in which a graph-based indexing schema will be applied to facilitate efficient trademark retrieval based on spatial relations between image components, regardless of mutual shape similarity.

Our framework starts by segmenting trademark images into distinct shapes using a shape identification algorithm. Identified shapes are then encoded automatically into an attributed graph whose vertices represent shapes and whose edges show spatial relations (both directional and topological) between the shapes. Using a graph-based indexing schema, the topological structure of the graph as well as that of its subgraphs are represented as vectors in which the components correspond to the sorted Laplacian eigenvalues of the graph or subgraphs. Having established the signatures, the indexing amounts to a nearest neighbour search in a model database. For a query graph and a large graph data set, the indexing problem is reformulated as that of fast selection of candidate graphs whose signatures are close to the query signature in the vector space. An extensive set of recognition trials, including a comparison with manually constructed graphs, show the efficacy of both the automatic graph construction process and the indexing schema.

REFERENCES

• 1: S. Alwis. Content-Based Retrieval of Trademark Images. PhD thesis, Dept. of Computer Science, University of York, UK, 1999.
• 2: W. N. Anderson and T. D. Morley. Eigenvalues of the laplacian of a graph. Linear and Multilinear Algebra, 18:141--145, 1985.
• 3: S. Beucher. Watersheds of functions and picture segmentation, acoustics, speech, and signal processing. In IEEE International Conference on ICASSP'82, pages 1928--1931, 1982.
• 4: S. Chang, E. Jungert, and Y. Li. Representation and retrieval of symbolic pictures using generalized 2D strings. In SPIE Conference on Visual Communications and Image Processing, volume 3, pages 1360--1372, November 1989.
• 5: S. K. Chang , Q. Y. Shi , C. W. Yan, Iconic indexing by 2-D strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.3, p.413-428, May 1987 [doi>10.1109/TPAMI.1987.4767923]
• 6: D. Cvetković, M. Doob, and H. Sachs. Spectra of Graphs: Theory and Application. VEB Deutscher Verlag der Wissenschaften, Berlin, 2nd edition, 1982.
• 7: J. P. Eakins, K. Shields, and J. M. Boardman. Artisan: A shape retrieval system based on boundary family indexing. In Storage and Retrieval for Image and Video Databases (SPIE), pages 17--28, 1996.
• 8: M. Egenhofer and R. Franzosa. Point Set Topological Relations. International Journal of Geographical Information Systems, 5(2):161--174, 1991.
• 9: Essam A. El-Kwae , Mansur R. Kabuka, A robust framework for content-based retrieval by spatial similarity in image databases, ACM Transactions on Information Systems (TOIS), v.17 n.2, p.174-198, April 1999 [doi>10.1145/306686.306689]
• 10: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 11: C. Godsil and B. McKay. Constructing cospectral graphs. In Aequationes Mathematicae, pages 257--268, 1982.
• 12: Robert Grone , Russell Merris , V. S. Sunder, The Laplacian spectrum of a graph, SIAM Journal on Matrix Analysis and Applications, v.11 n.2, p.218-238, Apr. 1990 [doi>10.1137/0611016]
• 13: Venkat N. Gudivada , Vijay V. Raghavan, Design and evaluation of algorithms for image retrieval by spatial similarity, ACM Transactions on Information Systems (TOIS), v.13 n.2, p.115-144, April 1995 [doi>10.1145/201040.201041]
• 14: Willem H. Haemers , Edward Spence, Enumeration of cospectral graphs, European Journal of Combinatorics, v.25 n.2, p.199-211, February 2004 [doi>10.1016/S0195-6698(03)00100-8]
• 15: Victoria J. Hodge , John Eakins , James Austin, Inducing a perceptual relevance shape classifier, Proceedings of the 6th ACM international conference on Image and video retrieval, p.138-145, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282306]
• 16: K. Koffka. Principles of Gestalt Psychology. Harcourt Brace. New York, 1963.
• 17: Suh-Yin Lee , Fang-Jung Hsu, 2D C-string: a new spatial knowledge representation for image database systems, Pattern Recognition, v.23 n.10, p.1077-1087, 1990 [doi>10.1016/0031-3203(90)90004-5]
• 18: D G Lowe, Three-dimensional object recognition from single two-dimensional images, Artificial Intelligence, v.31 n.3, p.355-395, March 1987 [doi>10.1016/0004-3702(87)90070-1]
• 19: B. Messmer and H. Bunke. A decision tree approach to graph and subgraph isomorphism detection. Pattern Recognition, 32(12):1979--1998, 1999.
• 20: B. Mohar. The laplacian spectrum of graphs. In Sixth International Conference on the Theory and Applications of Graphs, pages 871--898, 1988.
• 21: W. I. P. Organisation. CD-NIVILO ISBN 92-805-1280-7. WIPO, 2003.
• 22: Euripides G. M. Petrakis , Christos Faloutsos , King-Ip (David) Lin, ImageMap: An Image Indexing Method Based on Spatial Similarity, IEEE Transactions on Knowledge and Data Engineering, v.14 n.5, p.979-987, September 2002 [doi>10.1109/TKDE.2002.1033768]
• 23: E. Petrakis and S. Orphanoudakis. A Methology for the Representation, Indexing, and Retrieval of Images by Content. Image and Vision Computing, 8(11):504--512, October 1993.
• 24: Sudeep Sarkar , Kim L. Boyer, On Optimal Infinite Impulse Response Edge Detection Filters, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.11, p.1154-1171, November 1991 [doi>10.1109/34.103275]
• 25: Eric Saund, Finding Perceptually Closed Paths in Sketches and Drawings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.475-491, April 2003 [doi>10.1109/TPAMI.2003.1190573]
• 26: Ali Shokoufandeh , Diego Macrini , Sven Dickinson , Kaleem Siddiqi , Steven W. Zucker, Indexing Hierarchical Structures Using Graph Spectra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1125-1140, July 2005 [doi>10.1109/TPAMI.2005.142]
• 27: M. Wertheimer. Laws of organization in perceptual forms (1923)., 1938.
• 28: Daniel M. Wuescher , Kim L. Boyer, Robust Contour Decomposition Using a Constant Curvature Criterion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.1, p.41-51, January 1991 [doi>10.1109/34.67629]
• 29: S. Zucker. Region growing: Childhood and adolescence. Computer Graphics & Image Processing, 5:382--399, 1976.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Keywords:
Laplacian spectrum, content-based image retrieval, indexing, trademark retrieval