Abstract
This paper introduces a hashing based framework that facilitates sketch based image retrieval in large image databases. Instead of exporting a single visual descriptor for every image, an overlapping spatial grid is utilised to generate a pool of patches. We rank similarities between a hand drawn sketch and the natural images in a database through a voting process where near duplicate in terms of shape and structure patches arbitrate for the result. Patch similarity is efficiently estimated with a hashing algorithm. A reverse index structure built on the hashing keys ensures the scalability of our scheme and at the same time allows for real time reranking on query updates. Experiments in a publicly available benchmark dataset demonstrate the superiority of our approach.
This work is partially supported by EU project CUBRIK under grant agreement FP7 287704.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Datta, R., Joshi, D., Li, J., Wang, J.Z.: Image retrieval: Ideas, influences, and trends of the new age. ACM Comput. Surv. 40, 1–60 (2008)
Eitz, M., Kristian Hildebrand, T.B., Alexa, M.: A descriptor for large scale image retrieval based on sketched feature lines. In: Eurographics Symposium on Sketch-Based Interfaces and Modeling, pp. 29–38 (2009)
Cole, F., Golovinskiy, A., Limpaecher, A., Barros, H.S., Finkelstein, A., Funkhouser, T., Rusinkiewicz, S.: Where do people draw lines? Communications of the ACM 55, 107–115 (2012)
Cole, F., Sanik, K., DeCarlo, D., Finkelstein, A., Funkhouser, T., Rusinkiewicz, S., Singh, M.: How well do line drawings depict shape? ACM Transactions on Graphics (Proc. SIGGRAPH) 28 (2009)
Eitz, M., Hildebrand, K., Boubekeur, T., Alexa, M.: Sketch-based image retrieval: Benchmark and bag-of-features descriptors. IEEE Transactions on Visualization and Computer Graphics 17, 1624–1636 (2011)
Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. Journal of Computer and System Sciences 60, 327–336 (1998)
Chum, O., Philbin, J., Zisserman, A.: Near duplicate image detection: min-hash and tf-idf weighting. In: Proceedings of the British Machine Vision Conference (2008)
Dalal, N., Triggs, B.: Histograms of oriented gradients for human detection. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005, vol. 1, pp. 886–893 (2005)
Hirata, K., Kato, T.: Query by Visual Example. In: Pirotte, A., Delobel, C., Gottlob, G. (eds.) EDBT 1992. LNCS, vol. 580, pp. 56–71. Springer, Heidelberg (1992)
Lopresti, D., Tomkins, A.: Computing in the ink domain. In: Yuichiro Anzai, K.O., Mori, H. (eds.) Symbiosis of Human and Artifact - Future Computing and Design for Human-Computer Interaction. Proceedings of the Sixth International Conference on Human-Computer Interaction (HCI International 1995). Advances in Human Factors/Ergonomics, vol. 20, pp. 543–548. Elsevier (1995)
Liang, S., Sun, Z., Li, B.: Sketch retrieval based on spatial relations. In: Proc. Int. Computer Graphics, Imaging and Vision: New Trends Conf., pp. 24–29 (2005)
Del Bimbo, A., Pala, P.: Visual image retrieval by elastic matching of user sketches. IEEE Transactions on Pattern Analysis and Machine Intelligence 19, 121–132 (1997)
Matusiak, S., Daoudi, M., Blu, T., Avaro, O.: Sketch-Based Images Database Retrieval. In: Jajodia, S., Özsu, M.T., Dogac, A. (eds.) MIS 1998. LNCS, vol. 1508, pp. 185–191. Springer, Heidelberg (1998)
Chalechale, A., Naghdy, G., Mertins, A.: Sketch-based image matching using angular partitioning. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans 35, 28–41 (2005)
Eitz, M., Hildebrand, K., Boubekeur, T., Alexa, M.: A descriptor for large scale image retrieval based on sketched feature lines. In: Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling, SBIM 2009, pp. 29–36. ACM, New York (2009)
Sivic, J., Zisserman, A.: Video Google. In: Proceedings of the International Conference on Computer Vision, vol. 2, pp. 1470–1477 (2003)
Hu, R., Barnard, M., Collomosse, J.: Gradient field descriptor for sketch based retrieval and localization. In: Proc. 17th IEEE Int. Conf. Image Processing, ICIP, pp. 1025–1028 (2010)
Hu, R., Wang, T., Collomosse, J.: A bag-of-regions approach to sketch-based image retrieval. In: 2011 18th IEEE International Conference on Image Processing, ICIP, pp. 3661–3664 (2011)
Cao, Y., Wang, C., Zhang, L., Zhang, L.: Edgel index for large-scale sketch-based image search. In: 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR, pp. 761–768 (2011)
Lee, Y.J., Zitnick, C.L., Cohen, M.F.: Shadowdraw: real-time user guidance for freehand drawing. ACM Trans. Graph. 30, 27 (2011)
Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC 1998, pp. 604–613. ACM, New York (1998)
Canny, J.: A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8, 679–698 (1986)
Martin, D., Fowlkes, C., Malik, J.: Learning to detect natural image boundaries using local brightness, color, and texture cues. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 530–549 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bozas, K., Izquierdo, E. (2012). Large Scale Sketch Based Image Retrieval Using Patch Hashing. In: Bebis, G., et al. Advances in Visual Computing. ISVC 2012. Lecture Notes in Computer Science, vol 7431. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33179-4_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-33179-4_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33178-7
Online ISBN: 978-3-642-33179-4
eBook Packages: Computer ScienceComputer Science (R0)