Rotation invariant indexing of shapes and line drawings

ABSTRACT

We present data representations, distance measures and organizational structures for fast and efficient retrieval of similar shapes in image databases. Using the Hough Transform we extract shape signatures that correspond to important features of an image. The new shape descriptor is robust against line discontinuities and takes into consideration not only the shape boundaries, but also the content inside the object perimeter. The object signatures are eventually projected into a space that renders them invariant to translation, scaling and rotation. In order to provide support for real-time query-by-content, we also introduce an index structure that hierarchically organizes compressed versions of the extracted object signatures. In this manner we can achieve a significant performance boost for multimedia retrieval. Our experiments suggest that by exploiting the proposed framework, similarity search in a database of 100,000 images would require under 1 sec, using an off-the-shelf personal computer.

REFERENCES

• 1: Marvel: Multimedia analysis and retrieval system. http://www.research.ibm.com/marvel/.
• 2: H. G. Barrow, J. M. Tenenbaum, R. C. Bolles, and H. C. Wolf. Parametric correspondence and chamfer matching: Two new techniques for image matching. In IJCAI, 1977.
• 3: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558]
• 4: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
• 5: P. Fränti, A. Mednonogov, V. Kyrki, and H. Kälviäinen. Content-based matching of line-drawing images using the Hough transform. In IJDAR(3), No. 2, 2000.
• 6: Ada Wai-chee Fu , Polly Mei-shuen Chan , Yin-Ling Cheung , Yiu Sang Moon, Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.2, p.154-173, July 2000 [doi>10.1007/PL00010672]
• 7: K. Grauman and T. Darrell. Fast contour matching using approximate earth movers distance. In CVPR, 2004.
• 8: D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993 [doi>10.1109/34.232073]
• 9: Yong-Sung Kim , Whoi-Yul Kim, Content-based trademark retrieval system using visually salient features, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.307, June 17-19, 1997
• 10: Philip (Flip) Korn , Nicholas Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast and Effective Retrieval of Medical Tumor Shapes, IEEE Transactions on Knowledge and Data Engineering, v.10 n.6, p.889-904, November 1998 [doi>10.1109/69.738356]
• 11: C.-L. Lee and S.-Y. Chen. Classification for Leaf Images. In Proc. of IPPR CVGIP, 2003.
• 12: Euripides G. M. Petrakis , Aristeidis Diplaros , Evangelos Milios, Matching and Retrieval of Distorted and Occluded Shapes Using Dynamic Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.11, p.1501-1516, November 2002 [doi>10.1109/TPAMI.2002.1046166]
• 13: Davood Rafiei , Alberto O. Mendelzon, Efficient retrieval of similar shapes, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.1, p.17-27, August 2002 [doi>10.1007/s007780100059]
• 14: S. Tabbone, L. Wendling, and K. Tombre. Matching of graphical symbols in line-drawing images using angular signature information. In IJDAR(6), No. 2, 2003.
• 15: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 16: W. Zorski, B. Foxon, J. Blackledge, and M. Turner. Fingerprint and iris identification method based on the hough transform. In Proc. of Imaging and Digital Image Processing, pages 69-81, 2000.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
Hough Transform, image signature, metric tree