Comparative analysis of distance metrics for designing an effective content-based image retrieval system using colour and texture features

Published Online December 2017 in MECS

Recently the collection of images has significantly grown due to information being collected from everywhere and being digitalized and made available in image format. The increase in digital libraries and the large multimedia collection has led to an important need for the development of search tools for retrieving information from them. Thus there is continued need to develop efficient algorithms for retrieving images.

Content-based image retrieval (CBIR) means that the search examines the visual content of the image, such as colour, texture etc. rather than the text data such as tags and keywords [19]. Content-based image retrieval algorithm uses the visual content of the image for retrieval which removes the disadvantages of text-based retrieval systems [20, 21]. Some approaches have been proposed as an attempt to retrieve similar image among the large collection. Swain et al. [1] implemented the method of the colour histogram which has proved to be effective, efficient and easy to implement. Daisy et al. [2] propose the use of shapes and texture features which are extracted from the query images and are compared by means of Euclidean distance metric. Vatamanu et al. [3] used Local Binary Pattern Operator and Data Mining Techniques for the retrieval process. Block-Based Methods for Image Retrieval Using Local Binary Patterns was proposed by Valtteri et al. [4]. Kekre et al. [5] used DCT on Row mean, Column mean and Combination for Grayscale Image Retrieval. Similarly, row mean and column mean of images using 2D DWT was proposed by Sai and Patil [6]. Mistry et al. [7] used combination of spatial, frequency, CEDD and BSIF features to develop a hybrid CBIR algorithm. Goyal and Walia [8] used local binary pattern (LBP), local directional pattern (LDP) and their variations. Priya and David [9] proposed the use of multiple feature fusion and matching to retrieve images from the database. Many other features such as colour correlogram [10], colour moments [11] and MPEG-7 colour descriptors [12] have been used too. Singh et al [13-14, 16] have introduced the concept related to the combination of various computationally light weighted colour and texture features for image retrieval.

In order to further improve the retrieval performance of the CBIR, more and more researchers attempted to take advantage of primitive features to fuse for better performance. In this paper, features are derived from the entire image database and the feature vectors have been stored. Features extracted are HSV histogram, Colour moments, and Local Binary Patterns (LBP). Feature extraction using HSV histogram includes colour space conversion, colour quantization, and histogram computation. The colour moments feature extraction process includes conversion of RGB into individual components and involves computation of mean, standard deviation, and skewness of each component. Local binary patterns (LBP) is a type of visual descriptor used for classification. These stored feature vectors are then compared with the feature vectors of the query image. Analysis on different distance metrics such as Euclidean, City block, Chebyshev, Minkowski, Cosine, Correlation, and Spearman have been done to find out the best performing distance metric. The obtained distance metric has been used for retrieval.

Comparing to the existing algorithm which consists of colour and texture features, in this article, a hybrid feature using the fusion of LBP and HSV Histogram is proposed which improves the retrieval efficiency of the algorithm. The rest of this paper is organized as follows. Section II describes the various colour and texture feature extraction methods and distance metrics. Section III presents the approach taken to formulate the algorithm and the retrieval measures. Section IV presents simulation results and discussions. Finally, Section V concludes the paper.

The second step is to minimize the complexity and to reduce the feature vector size. Third and the last step is to obtain a histogram for each image which shows the frequency distribution of quantized HSV values of each pixel in the given image.

In this method various intervals are used such as for H 8 bins are used; for S 2 bins are used and for V 2 bins are used. A 32-D feature vector is obtained. Figure 1 shows various components of the HSV image along with the feature vector.

Fig.1. Various components of the HSV image along with the feature vector

• 2)    LBP Features: LBP captures the texture characteristics of an image and mathematically defined as [18]:

  • II.    Methods and Models

  • A. Feature extraction

  Feature extraction is an important step in the content based image retrieval systems as it affects the retrieval performance. This process involves deriving features from the image to a differentiable extent for better classification. In this study, we have used the combination of HSV and LBP Histogram for feature extraction, which are explained in the next sub-sections.

  • 1)    HSV Histogram: Feature extraction using HSV histogram includes three steps and they are colour space conversion, colour quantization, and histogram computation. The first step is to convert RGB image into HSV colour space. In the HSV colour space, h stands for hue, s stands for saturation which is the percentage of white light added to a pure colour and v stands for value which refers to the perceived light intensity [13]. These are calculated from the RGB components of the image using the formula:

  
  

  P - 1

  LBP p , r = Z 2 ' 5 ( I i - I c )

  i = 0

  
  

  5 ( x ) =

  
  
  

  if x <  0 else

  
  
  
  

  H = cos 1 [

  
  

  ______ 2^{[(R -} G)+ ^{(R -} B ^)] ______-i

  V(R - G)2 + (R - B)(G - B)

  
  
  
  

  S = 1 - [

  
  

  3[min(R,G,B)] R+G+B

  
  

  ]

  
  
  
  

  [R+G+B]

  
  
  
  
  
  

  Where I i and I c are neighbouring and centre pixel of an image. The connectivity from neighbouring pixels is represented as P and the neighbourhood radius is denoted as R. The LBP feature vectors created in the following step. The first step is to divide the examined window into cells. Each pixel in a cell is compared to each of its 8 neighbours. The set of neighbours is selected from a circularly symmetric pattern around each pixel. The number of neighbours (P) is increased to encode greater detail around each pixel. The radius of circular pattern (R) is to capture detail over the spatial scale. To capture detail over a larger spatial scale, the radius is increased. When the centre pixel's value is greater than the neighbour’s value, 0 is stored. Otherwise, 1 is stored. The second step is to set the rotation invariance flag which can be set as either not to encode rotation information or to encode the rotationally invariant features. The third step is to compute the histogram using the LBP feature vector, returned as a 1-by- N vector of length N which depends on the rotation invariance flag.

  The value of N, if the rotation information is not encoded then is [(P) (P–1) +3] and if the rotation

  information is encoded then is [P+2]. In this study, we

  
  

have taken P=8 for the first criteria. Therefore, we get feature dimension of 59. Figure 2 shows the neighbouring relationship of centre pixel for different radius and Figure 3 shows the histogram of LBP feature for a sample image of used database.

5) Cosine Distance: The cosine distance contains the dot product scaled by the product of the Euclidean distances of each vector from the origin. It represents the angular distance between two vectors. It is given by the formula:

Fig.2. LBP computation with the values of P as 8, 12 and 16 and R as 1, 2.5 and 4 respectively

D = 1

xyf ^(xx ' )(yy ' )

6) Correlation Distance: Distance correlation is a measure of statistical dependence between two random variables or two random vectors of arbitrary, not necessarily equal, dimension. The distance correlation of two random variables is obtained by dividing their distance covariance by the product of their distance standard deviations. It is given by the formula:

Fig. 3. LBP feature vector extraction

D = 1 -

(x-x.s)(y-yt)’

^ (x-xs) (x-xs}f^ (y-yt) (y—yt)'

B. Distance metrics

The following Distance metrics has been used in this paper:

1) Euclidean Distance: The Euclidean distance is the L2-norm of the difference. It is the square root of the sum of the square of the difference of respective element in two vectors. It is the natural distance in a geometric interpretation. It is given by the formula:

Where,

XS = ^ XjX sjj

7 J yt = 7^jytJ

7) Spearman Distance: Spearman Rank Correlation measures the correlation between two sequences of values. The two sequences are ranked separately and the differences in rank are calculated at each position. It is given by the formula:

(rs-rs)(rt-rt)i

D — 1 — —,               ,            —

^(rs-rs)(rs-rs)f^ (rt-rt)(rt-rt)f

Where,

D = 7 ( x - y ) 2

2) City Block Distance: The City Block distance is the L1-norm of the difference and is equivalent to the sum of absolute difference. It is given by the formula:

^D = Z ”=i ^j- ytj¹             (7)

• 3)    Chebyshev Distance: The Chebyshev distance is the L∞-norm of the difference. It is equal to Minkowski distance where p tends to infinity. It is given by the formula:

D = max j ^ ⁽ X sj ^- y j ^{) 2}            (8)

• 4)    Minkowski Distance: The Minkowski distance is the generalized Lp-norm of the difference. In this project, the value of p is taken as 3. It is given by the formula:

^D = ^7=1 ^lxsj- ytj^{I P            (9)}

• III.    Image Retrieval Framework

Image retrieval mainly has two steps which are Feature Extraction and Query Execution. Four different techniques are used here for image retrieval namely colour moments, HSV histogram, GLCM, and LBP. In the first technique, an RGB image is separated into R, G and B component images and then the mean, standard deviation and skewness of each of the component is computed. Colour moments create a 9-D feature vector. In the second technique, a 32-D vector of HSV histogram is generated using the methods discussed in previous section 2. In the third technique, GLCM matrix for an image is generated. Features like Contrast, Correlation, Energy, and Homogeneity were extracted from the matrix and a 4-D feature vector was formed. In the last technique,

LBP feature vector was generated using the approach mentioned in previous section 2 and a 59-D feature vector was generated.

Fcolour moments = {Fc1, Fc2, ……., Fc9}(13)

FHSV Histogram = {Fh1, Fh2, …….,Fh32}(14)

and

FLBP = {FL1, FL2, ……., FL59}(15)

For image retrieval, feature vectors of HSV histogram and LBP are combined. Final Feature vector is represented as

^F= ^{F HSVHistogram ^U F LBP } = ^{Fh 1 , ^Fh 2 ^,^.Fh³2, F L1 ,

F L2 ….., F L59 }

By combining the both feature vectors, we get a final hybrid feature of dimension 91. Working diagram of this hybrid feature extraction and retrieval is also shown in Fig.4

Fig.4. Block diagram of CBIR system.

The feature vector of both query images and image database is compared using the various distance metrics.

• IV.    Simulation Results

  For evaluation of the proposed method a general purpose WANG database containing 1000 images of 10 different classes in JPG format of size 384 × 256 or 256 × 384 is used. The image set comprises of 100 images in each of 10 different classes as horse, dinosaurs, mountain, cuisine, and monument etc. Sample images from each class are shown in figure 5 [17]. For each distance metric Precision and Recall is found using the following formulas:

„   . .      Number of relevant images retrieved     Z1 _x

Precision =                                   (17)

Total number of images retrieved

Recall =

Number of relevant images retrieved

Total number of relevant images in the database

In figures (6-7), precision by using the Euclidean distance and City Block distance was evaluated and was plotted against the no. of images. It’s evident from the graph that the Hybrid feature performs better compared to other feature in both the cases. The average precision if 20 images were retrieved was found to be around 65% for Euclidean and 71% for City Block.

Fig.5. Sample images from each class

In Figures (8-9), precision by using the Chebyshev distance and Minkowski distance was evaluated For Minkowski distance, hybrid feature performs much better compared to others but for Chebyshev distance performance of colour moments surpasses that of the hybrid feature when more than 25 images are retrieved. The average precision if 20 images were retrieved was found to be around 62% for Minkowski and 55% for Chebyshev. In figures (10-11), precision by using the Cosine distance and Correlation Distance was evaluated. It’s evident from the graph that the Hybrid feature performs better compared to other feature in both the cases. The average precision if 20 images were retrieved was found to be around 65% for both cases. A comparative analysis for seven different similarity measures has been done in figure 12 where it is clearly depicted that the best result is obtained using the City Block distance for the proposed algorithm. It is evident from the Figures shown that the hybrid features formed from the union of the feature vectors of HSV histogram and LBP perform better than other features such as colour moments, HSV histogram and LBP.

In distance metrics, the best result is obtained for the City Block distance. Further using City Block distance for the retrieval process, in figure 13, the performance of algorithm class wise is computed. The bins of the bar graph in figure 13 depict the classes of Africa, Beach, Monument, Bus, Dinosaur, Elephant, Flower, Horse, Mountain and Cuisine respectively. In figure 14 and 15, image retrieval using the algorithm for City Block Distance is shown. The top left image is the query image for the retrieval process. Here, we have tested the retrieval performance for 2 different sample queries and got very promising test results.

In Table 1 the analysis of each class with respect to each distance metric is shown and it is evident that City Block distance metric gives better results for all the classes except Beach, Elephant and Mountains where the Spearman distance performs better. However, the overall performance of City Block is much better than the Spearman as shown in the table.

Fig.6 .Precision vs number of retrieved image for Euclidean distance

Fig.9. Precision vs number of retrieved image for Minkowski distance

Fig.7. Precision vs number of retrieved image for City Block distance

Fig.10. Precision vs number of retrieved image for Cosine distance respectively

Fig.8 .Precision vs number of retrieved image for Chebyshev distance

Fig.11. Precision vs number of retrieved image for Correlation distance respectively

Fig.12. Precision for various distance metrics

QUERY IMAGE

Fig.14. Image Retrieval for sample query of bus for City Block distance

In figure 12, Distance Metrics labels:

• 1.   Euclidean

• 2.   City Block

• 3.  Chebychev

• 4.  Minkowski

• 5.   Cosine

• 6.   Correlation

• 7.  Spearman

QUERY IMAGE

Fig.13. The class wise performance of hybrid feature for City block distance

Fig.15. Image Retrieval for sample query: Food

Table 1. Class vs distance metric precision

	Africa	Beach	Monument	Bus	Dinosaur	Elephant	Flower	Horse	Mountain	Cuisine	Average
Euclidean	68.5	31	54	80.5	94	43	86.5	81.5	37.5	72	64.85
City Block	78	39.5	57	91.5	100	46.5	89.5	85.5	46.5	73	70.7
Chebyshev	55	27.5	39.5	58.5	87	34.5	69	81	36	59	54.7
Minkowski	63	28.5	49.5	74	91.5	42.5	81	81	36	68	61.5
Cosine	68.5	31	53	79	94	43.5	82	82	39	72.5	64.45
Correlation	68	30	54.5	80	94	43.5	81.5	81.5	39.5	74	64.65
Spearman	70.5	46.5	49.5	66	87.5	57	87.5	49	49	75	63.75
Average	67.36	33.43	51	75.64	92.57	44.36	82.43	77.36	40.5	70.5	63.52

• V.    Conclusion

In this paper, hybrid feature extraction method and different similarity measures are evaluated for efficient CBIR. Using colour and texture features individually, low retrieval performance was obtained for the retrieval. Colour feature that is HSV histogram feature and texture feature that is LBP feature are concatenated to increase retrieval performance of the presented algorithm. Further, it was evident from the experiments that the distance metric best suitable for this method was City Block as compared to other distance metrics.