Improving Image Search through MKFCM Clustering Strategy-Based Re-ranking Measure

3.1 Training Phase

Consider the dataset D, which has N number of images. In this work, we used seven types of images for analysis. In the training stage, we desired to train our framework to recognize an image appropriately by its extracted feature values. Basically, the testing stage is totally dependent on the training stage. The superior training of the framework gives superior test results and better accuracy of the framework. In this proposed model, the training phase consists of three stages: (i) pre-processing, (ii) feature extraction, and (iii) clustering. The step-by-step training process is explained below.

Stage 1: Pre-processing

The fundamental target of the pre-processing stage is enhancing the image into further processing. Consider the input RGB image, and we decompose the RGB image into R, G, and B components. These components are used for further processing.

Stage 2: Feature extraction

Feature extraction is an important process of image retrieval. In this, useful features are extracted from the image for retrieval purpose. Our proposed system uses four-level DWT for image feature extraction. The DWT splits the image into high- and low-frequency components. In the first level of decomposition, there are four sub-bands obtained, such as LL1, LH1, HL1, and HH1. For each successive level of decomposition, the LL sub-band of the previous level is used as the input. To perform second-level decomposition, the DWT is applied to the LL1 band, which decomposes the LL1 band into four sub-bands, such as LL2, LH2, HL2, and HH2. To perform the third decomposition, the DWT is applied to the LL2 band, which decomposes this band into the four sub-bands LL3, LH3, HL3, and HH3. To perform fourth-level decomposition, the DWT is applied to the LL3 band, which decomposes this band into again four sub-bands LL4, LH4, HL4, and HH4. The four-level DWT decomposition is shown in Figure 2. After the four-level decomposition, we select the third- and fourth-level LL coefficient. These selected coefficients are considered as the two types of features. Then, we calculate the standard deviation (SD) of the third and fourth sub-bands of all the three components. The SD is calculated using Eq. (1). Here, we obtain the eight features of each component. Totally, we obtain 24 features for one image. Using this procedure, we calculate the features for all the images. The standard deviation is calculated using Eq. (1):

Figure 2:

Four-Level Discrete Wavelet Transforms.

Here, we consider that N is representing the amount of wavelet coefficient at the specific sub-band, while Y_i is the wavelet coefficient value at a specific point at that sub-band.

Stage 3: MKFCM-based clustering

After the feature extraction, we apply the clustering process to group the database images into N-number of clusters. In this paper, we used seven as the number of clusters. Here, we use MKFCM for the clustering process. MKFCM is already used for a lot of image segmentation processes [3, 7, 22]. Huang et al. [7] proposed the multiple MKFCM algorithm, which extends the FCM algorithm with the multiple-kernel learning setting also used for face clustering. In the multi-kernel process, there are two hybrid kernels such as the linear and quadratic kernels. In hybrid work, new hybridized kernel functions are taken and the clustering process is performed based on these hybrid kernel functions. Let k₁ and k₂ be two kernels. Then, three hybrid kernels are formulated based on the definition given in Refs. [3, 18].

K(p, q) = K1 (p, q) +K2(p, q)  is a kernel.

K(p, q) = α∗ K1(p, q) is a kernel, when α>0.

K(p, q) = K1 (p, q)∗K2(p, q).

The general framework of the proposed MKFCM aims to minimize the objective function that is given in Eq. (3):

where N is the number of clusters, a is the number of data points, M_ij is the membership of j^th data in the i^th cluster A_i, A is the cluster center, K_MK is the multiple kernel function, and m is the degree of fuzziness of the algorithm.

In MKFCM, t_j represents the kernel function K_MK(x, y). Here, we are considering that multiple kernels for our proposed work are linear and quadratic kernels.

1. Applying the first theorem

   Step 1: At first, randomly initialize the cluster size a.

   Step 2: Randomly choose the centroid for each cluster A_i.

   Step 3: Calculate the objective function F:

   F = ∑i=1N∑j=1aMijm(1−KMK(tj, Ai )).

   Step 4: Substitute the first theorem in Eq. (3), where K₁ is a linear kernel and K₂ is the quadratic kernel.

   (4) KMK(p, q) = K1 (p, q) + K2 (p, q),

   (5) K1(p, q)=pTq+c,

   (6) K2(p, q)=1−||p−q||2||p−q||2+ c,

   where c is a constant value.

   Step 5: Then, we calculate the cluster center using Eq. (7):

   (7) Ai = ∑i=1NMijmKMK(p, q)∑i=1NMij     .

   Step 6: Membership update is done by using Eq. (8):

   (8) Mij = 1∑K=1A(‖KMK(p, q)−Ai‖‖KMK(p, q)−AK‖)2m−1.

   Based on the MKFCM, the images are clustered. In this work, we utilize the cluster size N=7.

2. Applying the second theorem

   When applying the second theorem to the FCM, at first we randomly initialize the cluster size. After that, we calculate the kernel-based objective function F.

   F = ∑i=1N∑j=1aMijm(1−KMK(tj, Ai )),

   where

   (9) KMK = α∗ K1(p, q),

   where α is a random value. In this paper, we take the random value as 0.1.

   (10) F = ∑i=1N∑j=1aMijm(1−α∗ K1(p, q)(tj,Ai )),

   (11) K1(p, q)=pTq+c,

   (12) Ai = ∑i=1NMijm (α∗K1(p, q))∑i=1NMij,

   (13) Mij = 1∑K=1A(‖(α∗K1(p, q))−Ai‖‖(α∗K1(p, q))−AK‖)2m−1.

3. Applying the third theorem

   In this section, we explain the third theorem. Here, we use the kernel K_MK, which is k₁(p, q)*k₂(p, q). The objective function of theorem 3 is given in Eq. (14):

   (14) F = ∑i=1N∑j=1aMijm(1−(K1(p, q)∗ K2(p, q)) (tj, Ai ))K1(p, q)=pTq+c.

   (15) K2(p, q)=1−||p−q||2||p−q||2+c.

   (16) Ai = ∑i=1NMijm (K1(p, q)∗ K2(p, q))∑i=1NMij.

   (17) Mij = 1∑K=1A(‖(K1(p, q)∗ K2(p, q))−Ai‖‖(K1(p, q)∗ K2(p, q))−AK‖)2m−1.

Based on the above three theorems, in this paper, we perform the clustering process and the effectiveness of the performance of these three algorithms is analyzed in Section 4. Based on the MKFCM, the images are clustered. In this work, we utilize the cluster size N=7. After the MKFCM process, we obtain the number of cluster sets, such as C₁, C₂, C₃, C₄, C₅, C₆, C₇. These clustered images are used for the testing process.

3.2 Testing Phase

After the training process is completed, we start doing the testing process. The testing phase depends on the training phase only. The testing process images are fully different from the training images; however, the categories are the same. In the testing process, query-based images are retrieved using multiple stages.

Step 1: Consider the query image Q_i, which is present in database D. In this paper, at first we have given the query image to the system. The aim of this section is to retrieve the corresponding query-based images in the ranked format.

Step 2: Then, we apply four-level DWT to the image for calculating the features of the query image. The feature extraction process is explained in the training phase, and the same process is also repeated in this testing process.

Step 3: After that, we take the similarities between centroid (obtained from the training process) and query image features. The minimum distance-based corresponding cluster (C_i) images are retrieved. The retrieved images are ranked in decreasing order of similarity between the query image and cluster. This output is called first-level retrieval output R^First. Based on the image position, we generate the index RIndexFirst.

Step 4: After the first-level retrieval, we rank the images because the obtained retrieval results are not properly ranked. Therefore, in this paper, we introduce the ranking methodology. To rank the first-level retrieval result images R^First, we group the images using the clustering process.

Step 5: Before applying the clustering process to R^First images, we calculate the features of all the retrieved images. The features are already extracted in the training phase.

Step 6: In this, we utilize the FCM clustering algorithm for clustering the image features. Here, we group the R^First images into N-number of clusters (C₁, C₂,…, C_N) based on a distance measure.

Step 7: Then, we calculate the similarities between centroid A_i and query images. Based on the similarities, we arrange the clusters (C₁, C₂, …, C_N). The cluster-based images are retrieved. In this step, we obtain the retrieved result, called ranked retrieval result R^Rank. Based on the image position, we generate the index RIndexRank.

Step 8: To improve the ranking performance of images, we perform re-ranking. Here, we combine RIndexFirst and RIndexRank using Eq. (18):

where RIndexFirst represents the first-level retrieval output index, RIndexFirst represents the ranked retrieval result index, and D′(I, I′) represents the re-ranked retrieved result. Utilizing Eq. (18), we re-calculate the similarities between the query image and the images in the retrieved result. At that point, we re-arrange the positions of the images as indicated by the re-calculated values in decreasing order. Figure 3 demonstrates the arrangement of recalculating the similarity that clarifies the development of image cluster and the combination of two similarities. Here, the images that have more similarity to each other are assembled into one group and insignificant images are separated into various groups. In this way, the similarity between the query and the images in the closer group is adjusted in accordance with a smaller value; otherwise, the similarity is modified to a larger value by Eq. (18).

Figure 3:

Re-evaluating Similarity.

4.1 Performance Measures

System performance is analyzed by using the most common performance measures, known as precision (P), recall (R), and F-measure (F). A precision rate can be defined as the percentage of retrieved images similar to the query among the total number of retrieved images. A recall rate is defined as the percentage of retrieved images that are similar to the query among the total number of images similar to the query in the database. It can be easily seen that both precision and recall rates are the functions of the total number of retrieved images. In order to have a high accuracy, the system needs to have both high precision and high recall rates. Mathematically, P, R, and F are defined as

where N^Q represents the number of relevant images retrieved from the database, T^Q represents the total number of images retrieved, and D^Q represents the number of images in the database relevant to query image Q.

4.2 Experimental Results in the Proposed Approach

In this section, we show the visual representation of the proposed algorithm. The visual results contain the query image, first-level retrieval output, and final re-ranked images. Figures 5–7 show the visual results of three images, such as butterfly, car, and rose.

Figure 5:

Retrieval Example Using Query Image (Butterfly).

(A) First-level retrieval output images. (B) Re-ranked image output.

Figure 6:

Retrieval Example Using Query Image (Car).

(A) First-level retrieval output images. (B) Re-ranked image output.

Figure 7:

Retrieval Example Using Query Image (Rose).

(A) First-level retrieval output images. (B) Re-ranked image output.

4.3 Comparative Analysis

The performance of the proposed image retrieval and re-ranking system is analyzed with the help of precision, recall, and F-measure, which are the most significant performance parameters. The effectiveness of the proposed technique is demonstrated by performing a comparison between the retrieval results of the proposed MKFCM clustering method with other approaches. The principal objective of the proposed system is to effectively rank the retrieved images. Here, at first, we convert the input image into R, G, and B components. Then, we extract the features of the three components using four-level DWT. Then, we apply the MKFCM clustering algorithm to cluster the images using distance measures. After that, the query-based image clusters are retrieved. Then, we rank the retrieved images using the FCM algorithm. To improve the efficiency of ranking performance, in this paper we propose a re-ranking method. Here, we prove the effectiveness of the proposed approach and compare our work with the different theorems.

Figures 8–10 analyze the performance of the proposed approach using different measures. In this work, for the training process, we utilized the MKFCM algorithm. In multi-kernels, we used linear and quadratic kernels. Based on the hybrid kernels, we implemented three theorems. Based on the three kernels, we evaluated the results. Figure 8 shows the performance analysis of different approaches using the precision value. Here, the x-axis represents the query images and the y-axis represents the precision value. When the query image is “butterfly”, we obtain the maximum precision of 0.8 for using theorem 1, 0.6 for using theorem 2, 0.76 for using theorem 3, and 0.4 for using k-means algorithm-based re-ranking. When analyzing Figure 8, we obtain the maximum precision of 0.83 for the rose image using theorem 1. Comparing these four methods, theorem 1 obtains the better result compared to theorem 2, theorem 3, and the k-means algorithm. Similarly, the k-means algorithm-based image re-ranking method has poor performance compared to the other three methods. Figure 9 shows the performance analysis of different approaches using recall measure. Using theorem 1, we obtain the maximum recall of 0.88 for the butterfly image; using theorem 2, we obtain the maximum recall of 0.92 for the rose image; using theorem 3, we obtain the maximum recall of 0.56 for the waterfall image; and using the k-means algorithm, we obtain the maximum recall of 0.45 for the waterfall image. Moreover, Figure 10 shows the performance analysis of a different approach using F-measure. From the result, we clearly understand that our proposed approach obtains the better performance.

Figure 8:

Performance Analysis of Different Approaches Using Precision Measure.

Figure 9:

Performance Analysis of Different Approaches Using Recall Measure.

Figure 10:

Performance Analysis of Different Approaches Using F-measure.

Tables 1–4 show the confusion matrix of theorem 1, theorem 2, theorem 3, and k-means-based retrieval. Here, the user gives the query to the system and the query-based images are retrieved. In the confusion matrix, this is the diagonal element divided by the sum over the relevant row. Table 1 shows the confusion matrix of theorem 1. Here, the user-recommended number of images is 100. So, when we give the query image, the query-based 100 images are retrieved. It is equivalent to recall. Using theorem 1, we obtain 80 butterfly images, six nature images, three rose images, one car image, four deer images, three waterfall images, and four Tajmahal images for “butterfly image”. We correctly retrieve 80%. Compared to the entire confusion matrix, we obtain the maximum retrieval accuracy for theorem 1, theorem 2, and theorem 3. The best average precision of 83%, 80%, 76%, and 46% was obtained using theorem 1, theorem 2, theorem 3, and k-means, respectively. To evaluate the significance of the obtained results, we employed the analysis of variance test on the maximum precision values. We ranked all models by maximum precision and evaluated groups of models to find classes with similar intra-class performance and significantly different inter-class performance. From Section 4, we clearly understand that our proposed approach is better than k-means algorithm-based retrieval.

4.4 Comparative Analysis of Other Works

Here, we compare our proposed work with other published works related to image retrievals, such as those of Voravuthikunchai et al. [23] and Srilatha [20]. In Ref. [23], the authors explained an image re-ranking based on statistical f frequency patterns. More specifically, the approach consists in computing efficiently and on-the-fly frequent closed patterns, and in re-ranking images based on the number of patterns they contain. Similarly, in Ref. [20], the authors explained a scalable image search re-ranking through the CBIR method. Here, k-means clustering, support vector machine classifier, and re-ranking algorithm technique are used to obtain the efficient prototype-based scalable result.

Table 5 shows the comparative analysis based on precision measures. Here, we compare our proposed three theorems with existing two approaches. Our proposed approach achieves the maximum precision of 0.83 for theorem 1 using a rose image, which is 0.69 for using Ref. [23] and 0.7 for using Ref. [20]. From the result, we clearly understand that our proposed approach achieves the maximum output compared to other works.