“Fast multiresolution image querying” by Jacobs, Finkelstein and Salesin

We present a method for searching in an image database using a query image that is similar to the intended target. The query image may be a hand-drawn sketch or a (potentially low-quality) scan of the image to be retrieved. Our searching algorithm makes use of multiresolution wavelet decompositions of the query and database images. The coefficients of these decompositions are distilled into small “signatures” for each image. We introduce an “image querying metric” that operates on these signatures. This metric essentially compares how many significant wavelet coefficients the query has in common with potential targets. The metric includes parameters that can be tuned, using a statistical analysis, to accommodate the kinds of image distortions found in different types of image queries. The resulting algorithm is simple, requires very little storage overhead for the database of signatures, and is fast enough to be performed on a database of 20,000 images at interactive rates (on standard desktop machines) as a query is sketched. Our experiments with hundreds of queries in databases of 1000 and 20,000 images show dramatic improvement, in both speed and success rate, over using a conventional L1, L2, or color histogram norm.

1. R. Barber, W. Equitz, W. Niblack, D. Petkovic, and R Yanker. Efficient query by image content for very large image databases. In Digest of Papers. COMPCON Spring ’93, pages 17-19, San Francisco, CA, USA, 1993.
2. G. Beylkin, R. Coifman, and V. Rokhlin. Fast wavelet transforms and numerical algorithms I. Communications on Pure and Applied Mathematics, 44:141-183, 1991.
3. R. DeVore, B. Jawerth, and B. Lucier. Image compression through wavelet transform coding. IEEE Transactions on Information Theory, 38(2):719-746, March 1992.
4. C. Faloutsos, R. Barber, M. Flickner, J. Hatner, W. Niblack, D. Petkovic, and W. Equitz. Efficient and effective querying by image content. Journal of Intelligent Information Systems: Integrating Artificial Intelligence and Database Technologies, 3(3-4):231-262, 1994.
5. James D. Foley, Andries van Dam, Steven K. Feiner, and John F. Hughes. Computer Graphics: Principles and Practice. Prentice-Hall, 1990.
6. T. Gevers and A. W. M. Smuelders. An approach to image retrieval for image databases. In V. Marik, J. Lazansky, and R. R. Wagner, editors, Database and Expert Systems Applicatons (DEXA ‘ 93), pages 615-626, Prague, Czechoslovakia, 1993.
7. Yihong Gong, Hongjiang Zhang, H. C. Chuan, and M. Sakauchi. An image database system with content capturing and fast image indexing abilities. In P1vceedings of the International Conference on Multimedia Computing and Systems, pages 121-130. IEEE, 1994.
8. William I. Grosky, Rajiv Mehrotra, F. Golshani, H. V. Jagadish, Ramesh Jain, and Wayne Niblack. Research directions in image database management. In Eighth International Conference on Data Engineering, pages 146-148. IEEE, 1992.
9. Donald Hearn and M. Pauline Baker. Computer Graphics. Addison-Wesley Publishing Company, Inc., 1994.
10. K. Hirata and T. Kato. Query by visual example — content based image retrieval. In A. Pirotte, C. Delobel, and G. Gottlob, editors, Advances in Database Technology (EDBT ’92), pages 56-71, Vienna, Austria, 1992.
11. N. Jayant, J. Johnston, and R. Safranek. Perceptual coding of images. In P1vceedings of the SHE — The International Society for Optical Engineering, volume 1913, pages 168-178, 1993.
12. Atreyi Kankanhalli, Hong Jiang Zhang, and Chien Yong Low. Using texture for image retrieval. In International Conference on Automation, Robotics and Computer Vision. IEE, 1994.
13. T. Kato. Database architecture for content-based image retrieval. In P~vceedings of the SPIE — The International Society for Optical Engineering, volume 1662, pages 112-123, San Jose, CA, USA, 1992.
14. T. Kato, T. Kurita, N. Otsu, and K. Hirata. A sketch retrieval method for lull color image database — query by visual example. In Proceedings of the llth IAPR International Conference on Pattern Recognition, pages 530-533, Los Alamitos, CA, USA, 1992.
15. Patrick M. Kelly and T. Michael Cannon. CANDID: Comparison Algorithm for Navigating Digital Image Databases. In Proceedings of the Seventh International Working Conference on Scientific and Statistical Database Management Storage and Retrieval for Image and Video Databases. IEEE, 1994.
16. A. Kitamoto, C. Zhou, and M. Takagi. Similarity retrieval of NOAA satellite imagery by graph matching. In Storage and Retrieval for Image and Video Databases, pages 60-73, San Jose, CA, USA, 1993.
17. J. Liang and C. C. Chang. Similarity retrieval on pictorial databases based upon module operation. In S. Moon and H. Ikeda, editors, Database Systems for AdvancedApplications, pages 19-26, Taejon, South Korea, 1993.
18. G.S. Maddala. Intlvduction to Econometrics. Macmillan Publishing Company, second edition, 1992.
19. Stephane Mallat and Sifen Zhong. Wavelet transform maxima and multiscale edges. In Ruskai, et al, editor, Wavelets and Their Applications, pages 67-104. Jones and Bartlett Publishers, Inc., Boston, 1992.
20. W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, R Yanker, C. Faloutsos, and G. Taubin. The QBIC project: Querying images by content using color, texture, and shape. In Storage and Retrieval for Image and Video Databases, pages 173-187. SPIE, 1993.
21. G. Petraglia, M. Sebillo, M. Tucci, and G. Tortora. Rotation invariant iconic indexing for image database retrieval. In S. Impedovo, editor, P~vceedings of the 7th International Conference on Image Analysis and P1vcessing, pages 271-278, Monopoli, Italy, 1993.
22. Brian Pinkerton. Finding what people want: Experiences with the WebCrawler. In The Second International WWW Conference ’94: Mosaic and the Web, October 1994.
23. William H. Press, Brian R Flannery, Saul A. Teukolsky, and William T. Fetterling. Numerical Recipes. Cambridge University Press, second edition, 1992.
24. T.R. Reed, V. R. Algazi, G. E. Forrd, and I. Hussain. Perceptually-based coding of monochrome and color still images. In DCC ’92- Data Compression Conference, pages 142-51, 1992.
25. SAS Institute Inc. SAS/STAT User’s Guide, Version 6, Fourth Edition, Volume 2. SAS Institute Inc., 1989.
26. R. Shann, D. Davis, J. Oakley, and F. White. Detection and characterisation of Carboniferous Foraminifera for content-based retrieval from an image database. In Storage and Retrieval for Image and Video Databases, volume 1908, pages 188-197. SPIE, 1993.
27. M. Shibata and S. Inoue. Associative retrieval method for image database. Transactions of the Institute of Electlvnics, Information and Communication Engineers D-H, J73D-II:526-34, 1990.
28. E. R Simoncelli, W. T. Freeman, E. H. Adelson, and D. J. Heeger. Shiftable multiscale transforms. IEEE Transactions on Information Theory, 38:587-607, 1992.
29. Stephen W. Smoliar and Hong Jiang Zhang. Content-based video indexing and retrieval. IEEE Multimedia, 1(2):62-72, 1994.
30. R L. Stanchev, A. W. M. Smeulders, and F. C. A. Groen. An approach to image indexing of documents. IFIP Transactions A (Computer Science and Technology), A-7:63-77, 1992.
31. Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for computer graphics: A primer, Part I. IEEE Computer Graphics and Applications, 15(3):76- 84, May 1995.
32. Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for computer graphics: A primer, Part II. IEEE Computer Graphics and Applications, 15(4), July 1995. In press.
33. Michael J. Swain. Interactive indexing into image databases. In Storage and Retrieval for Image and Video Databases, volume 1908, pages 95-103. SPIE, 1993.
34. Patrick C. Teo and David J. Heeger. Perceptual image distortion. In Human Vision, Visual P1vcessing and Digital Display V, IS&T/SPIE’s Symposium on Electronic Imaging: Science & Technology, 1994. In press.
35. Chen Wu Tzong and Chin Chen Chang. Application of geometric hashing to iconic database retrieval. Pattern Recognition Letters, 15(9):871-876, 1994.
36. M. Weiser. Some computer science issues in ubiquitous computing. Communications of the ACM, 36(7):74-84, 1993.