Sketch Based Image Retrieval – A Short Survey

Sketch Based Image Retrieval – A Short Survey

1. C. Vishal Patil, 2. R. Kavin Kumar , 3. R. Aarthi

1.Student – Computer Science , 2. Student – Computer Science , 3. Asst. Professor Computer Science Amrita VishwaVidyapeetham,

Coimbatore-641112.

Abstract-In the last two decades, there has been a lot of growth in digital media to search and retrieve images. This demands an effective and user friendly methods to fetch images from large databases. To cater to this need, sketch based image retrieval methods are developed from traditional Content Based Image Retrieval (CBIR). The objective of this paper is to compare the various techniques in retrieving images from database using sketch.The output obtained and the efficiency calculated for various methods have been analyzed. This comparison of efficiencies will help in concluding the efficient method for sketch based image retrieval.

Keywords-Distance Transform, Image Retrieval, Canny edge Detection, Filters, Sketch.

1. INTRODUCTION

   According to the Moores Law of Big Data the amount of data is doubling every 20 to 24 months. In order to retrieve images from databases, there is a need for efficient methods for retrieval. The most common method used for image retrieval is Content Based Image Retrieval (CBIR) [1],in which the output images are similar to a user provided query image. The main advantages of using Content Based Image Retrieval (CBIR) are (i) Fast Retrieval (ii) Ease ofimplementation. The main disadvantages in Content Based Image Retrieval are (i) time consumption to tag all the available data (ii) results are user subjective. However,there can be a lack in clarity of information if images are tried to be communicated through words. Sketch based image retrieval is used where the input is given as a hand drawn sketch using software like paint. Since this technique requires a particular amount of basic artistic skills, some people may refrain from using this.

   This paper focuses on comparing three algorithms Chamfer Matching Algorithm, Edge Histogram and

   Histogram of Gradient (HOG). Parameters such as time, accuracy and efficiency of the three algorithms are compared.

   Fig. 1 : Sample input and output[5] (a)Sample Sketch Image

   (b)&(c) Retrieved Database Images

2. ARCHITECTURE

   Fig.2 : Architecture Diagram

3. COMPARATIVE STUDY

   A. Chamfer Matching Algorithm

   This method was first proposed in 1997 to find the best fit of the edge points from two different images, by minimizing a generalized distance between them. The edge points of one image are transformed by a set of parametric equations that describes how the images can be geometrically distorted in relation to one another. Based on the number of matches image are ranked accordingly [11]. A max filter is applied to the images and this will reduce the noise and sharpen the images.After extracting the edge, Euclidean distance [12] is calculated separately for query image and edge image. The result obtained after Distance Transform are subtracted and then squared. All the values are summed up and the result is divided by the contour length. The result obtained is sorted in ascending order and then the top few results are displayed.The main disadvantage of this algorithm is that it is less reliable in presence of background clutter.

   B.Edge Histogram

   Edge Histogram Descriptor takes into account only the edge features. One way of representing such an edge feature is to use a histogram. An edge histogram [2] in the image space represents the frequency and the directionality of the brightness changes in the image. The image is divided into fixed number of non-overlapping blocks regardless of the size of the image, resulting in formation of sub images. We extract the edges of the images. Each bin represents a range of angle values. The distance between the histograms of input image and set of images in a database are calculated for similarity matching, the image whose distance is smaller among the images in database is considered as more relevant to the input image than the other images.

   C. A Technique using Histogram of Gradient (HOG)

   This method gives a block based retrieval technique that facilitates sketch based image retrieval in large image databases. Instead of exporting a single visual descriptor for every image, non-overlapping blocks are utilized[5]. Rank similarities between a hand drawn sketch and the images in a database through a matching process where near duplicates are retrieved [5]. The similarity between the sketch and database imagesis efficiently estimated with a second nearest neighbor algorithm [10].Every image in the database is divided into nine non-overlapping blocks of equal size [5]. The sketch query undergoes the same process as the database images.The features of the images are extracted to compare the images and to find similarity between them. Then use Histogram of Gradient (HOG) descriptors for features extraction of the image [8]. The features are extracted within the blocks of the image and similar features of the input sketch are also obtained only from the blocks. The values obtained are stored in the excel file which are later used for comparison.The comparison of the extracted Histogram of Gradient values is carried out to estimate the match between

   the sketch and the database images. There are six values produced for each block since the bin size is considered to be 6 in the HOG process there by giving 54 values for an image. The values of sketch image is stored in the dimension 1 x 54 whereas the values of all the database images are stored in the dimension 54 x 1 .Then dot product is taken for all the values of the database images versus the sketch image thereby producing one value as a result of the dot product. The highest number is the closest match for the sketch image. Thereby we sort the values in the descending order and the images corresponding to the top values are displayed.

4. EVALUATION

   In this paper, comparison of the working of three sketch based image retrieval algorithms across 250 images in a databaseis carried out and the results are shown in Table 1. When a query is given to a database 16 result images are displayed out of which, 3 to 4 images on an average are relevant and matches the input in chamfer matching algorithm. 5 to 6 images on an average are relevant and matches the input in edge histogram algorithm. 11 to 12 images on an average are relevant and match the input using HOG.

   METHOD	EDGE HISTOGRAM	HISTOGRAM OF GRADIENT (HOG)	CHAMFER MATCHING
   SCALE INVARIENT	Yes	No	No
   ROTATION INVARIENT	No	No	No
   ACCURACY
   BOAT	4	10	5
   BUILDING	5	11	3
   CAVE	3	13	4
   FLOWER	5	14	5

   Table 1: Comparison of algorithm results

   With the above comparison, HOG has the best efficiency and gives the best results.

5. REFERENCE

1. Datta, R., Joshi, D., Li, J., Wang, J.Z.: Image retrieval: Ideas, influences, and trends of the new age. ACM Comput. Surv. 40, 160 (2008)

2. Chee Sun Won et al, T. (2002). Efficient Use of MPG-7 Edge Histogram Descriptor, ETRI Journal,Volume 24,Number 1.

3. ISO/IEC : Core Experiment Results for Spa-tial Intensity Descriptor (CT4), MPEG document M5374, Maui, Dec. 1999.

4. S. J. Park, D. K. Park, C. S. Won, Core experiments on MPEG-7 edge histogram descriptor, MPEG document M5984, Geneva, May, 2000.

5. KonstantinosBozas and EbroulIzquierdo, Large Scale Sketch Based Image Retrieval Using Patch Hashing, Springer-Verlag Berlin Heidelberg 2012.

6. 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, 16241636 (2011).

7. Liang, S., Sun, Z., Li, B.: Sketch retrieval based on spatial relations. In: Proc. Int. Computer Graphics, Imaging and Vision: New Trends Conf., pp. 2429 (2005).

8. 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. 886893 (2005).

9. J. Canny, A computational approach to edge detection, IEEE Tans. Pattern Analysis and Machine Intelligence, Vol. 8, No, 6, pp. 679-698, November

10. 1986.Image Processing, Analysis ,and Machine Vision By Milan Sonka (The University of Iowa, Iowa City),Vaclav Hlavac ( Czech Technical University, Prague), Roger Boyle ( University of Leeds, Leeds).

11. Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., and Wu, A.

    Y. (1998). An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM, 45:891923.

12. G. Borgefors. Hierarchical chamfer matching: A parametric edge matching algorithm. PAMI,1988.

13. R. Fabbri, L.D.F. Costa, J.C. Torelli, and O.M. Bruno, 2D Euclidean distance transform algorithms: a comparative survey, ACM Computing Surveys, vol. 44, pp. 144, February 2008.