Introduction

Unsupervised or human guided object retrieval is one of the basic functionalities of content-centric Internet services. The first generation of digital database retrieval systems was built on the use of metadata describing the semantic content of a multimedia database, usually extracted by manual procedures. However, Future Internet content aware services require more efficient functionalities for inspection, crawling, recognition, categorization, and indexing of multimedia content with minimal human intervention.

The research activity on Content Based Image Retrieval (CBIR) has been focused on the analysis of local and global image features for the refinement of the coarse annotation, extracted from the WEB pages containing the image, and for re-ranking the results obtained by searching those annotations [1], [3], [4], [5]. In fact, up to the present, traditional search based on keywords has focused on direct use of image content, because of the difficulty in providing at least a sketch of the desired picture. Nevertheless, the widespread diffusion of cameraphones seems to open new opportunities to CBIR for the easiness in providing samples taken from the real word when browsing an image archive by means of a cell phone [2].

Current CBIR techniques are based on comparisons of global features like dominant colors, object shapes, textures as well as of local features relating to the most salient points, like corners. They evaluate a similarity index computed on the basis of the features extracted from the reference template and those of the candidate image. The similarity index can either directly employ these features, as in the case of adoption, as index, of the maximum likelihood or of the belief functional, or can be based on the comparison of the statistical distribution of the features, as in the case of the use of the Kullback-Leibler divergence. On the other hand, irrespective of the set of local or global features employed for comparing image and video contents, current search engines produce a list of candidates usually sorted with respect to the similarity index. The consequence is that in the presence of several clusters of candidates, the search engine will report the elements of the most similar images and, if the number of elements belonging to that cluster is large enough, the other clusters may be completely cluttered by the dominant one.

The aim of this contribution is to propose a technique for sorting the list of potential candidates in such a way that all the relevant clusters are represented in the list displayed to the user, thus preserving the diversity of possible solutions.

More specifically, a pre-selection of candidates by considering a similarity index accounting only for a subset of the whole feature set is performed. This subset can be either predetermined by referring, for instance, to those features like morphology, that the user regards as more relevant, or automatically selected as those maximizing like a partial similarity index, as described in the next section. Then, the candidate set is clustered by extracting the local maxima of the similarity index evaluated on the full set of features. Finally, for each local maximum, including the absolute one, a representative set of images to be presented as query results is selected. The cardinality of each set may be proportional to the similarity index.

With respect to the evaluation of the partial similarity on the basis of a predefined feature subset, we observe that the relative importance of each feature strictly depends on the user needs. Therefore, although default values for different applications and contests can be specified, the user should have the possibility to provide this information to the search engine.

In the examples reported in this contribution, it is assumed that morphology is the most discriminating global feature for the user, while color based features act as elements discriminating the various clusters. In order to verify the performances of the proposed method in highlighting the differences among the search outcomes, we simplified the set of features employed in the comparison. Thus, with respect to the MPEG-7 ensemble of global and local features, see [1], we focused our attention on the texture morphology, as described by the statistics of the outputs of a set of steerable filters, and on the dominant colors. The simulation results confirm that search results clustering driven by the relative maxima of the similarity index is a powerful technique for preserving web diversity.

The fair similarity ranking

Let us model the global feature space V as an M -dimensional vector space, partitioned into L subspaces W j , each one corresponding to a particular feature set, so that V can be written as direct sum of these subspaces:

V = W 1 ⊕ W 2 ⊕ • • •⊕W M .

Given two elements x, y ∈ V , their similarity s(x, y) can be computed:

s(x, y) = L i=1 s i (x i , y i ),(1)

where s i (x i , y i ) is the similarity index corresponding to the i-th feature set. Let us consider, without loss of generality, the subset V consisting of N subspaces corresponding to the first N features. Let C k,M be the set of k-combinations of the N -element index set, then for any

k-combination i = (i 1 , i 2 , . . . , i k−1 , i k ) let us denote with W i the set obtained as direct sum of V i1 , V i2 , . . . , V i k−1 , V i k , i.e., W i = V i1 ⊕ V i2 ⊕ . . . ⊕ V i k−1 ⊕ V i k .

Then given two elements x, y ∈ V we define as partial similarity sk,N (x, y) based on the best k features out of N as

sk,N (x, y) = M ax i ∈ C k,N k h=1 s i h (x i h , y i h ).

(

)2

We observe that the concept of similarity can be easily replaced by the concept of dissimilarity. Consequently, we define as partial dissimilarity dk,N (x, y) based on the best k features out of N as

dk,N (x, y) = min i ∈ C k,N k h=1 di h (x i h , y i h ).(3)

The use of dissimilarity in place of similarity is suggested by the fact that some effective indicators widely used in statistics like the Kullback-Leibler divergence do not satisfy the triangle inequality. Thus, for a given template x, the set A(x) of candidates can now be computed by thresholding the partial dissimilarity, namely:

A(x) = {y dk,N (x, y) ≤ γ}.(4)

Finally, clustering of the candidate set A(x) on the basis of the whole feature space V is performed. The dissimilarity threshold γ V employed in the cluster formation is, in general, lower than the threshold γ used in the candidate selection phase.

Laguerre Gauss decomposition and texture classification

Texture segmentation and classification has been intensively studied and many texture description algorithms have been proposed including statistical [6] and feature based methods [7], [8]. In many applications, segmentation and classification need to be performed without taking object orientations into account, so rotation invariant descriptions of texture patterns are employed.

In this context, a relevant role has been played by the Circular Harmonic Functions (CHF), initially introduced in the field of optical processing for rotation invariant pattern recognition, and recently casted in a wavelet decomposition scheme [10], [11]. Since CHFs are intrinsically tuned to image features like edges, lines, equiangular forks, orthogonal crosses without regard to their orientations, they are good candidates for such applications. A detailed description of Laguerre Gauss wavelet decomposition can be found in [10].

In this paper, we use the pixel classification algorithm employed by Randen and Husoy in their feature set comparisons [9] for segmentation. Then we utilize a multiscale segmentation method, [10], starting from CHF moments. These moments are obtained by the decomposition of a template on complex CHFs that form a complete orthogonal basis on a unit disc. Due to a general property of the CHFs, a pattern can be easily steered by multiplying the expansion coefficients by complex exponential factors whose phase is proportional to the rotation angle, [12], [13]. As a consequence, rotation invariants can be easily obtained by considering the magnitude of the expansion coefficients.

In our method, the texture classification is performed by considering both the structural (morphological) and the color components. To represent a texture pattern morphology, the expansion coefficients of the Laguerre-Gauss transform of the luminance component Y corresponding to a finite set of N K order pairs {(n, k)| n = 1, ..., N, k = 0, ..., K − 1} are employed. In particular n = 1, .., 3 and k = 0, .., 3 at 3 different resolutions have been employed in the examples reported in the following. Since the magnitude of the transform coefficients is rotation invariant, we use their statistics. In particular, as already stated in [10] it is possible to characterize the marginal density of a wavelet decomposition by using a generalized Gaussian function. This distribution is characterized by two parameters, α and β, directly related to the mean and variance distribution. Thus, mean and variance are sufficient to describe the statistical properties of the Laguerre-Gauss transform coefficient magnitudes of a portion of an image. As a consequence, for each point of a given region of interest (ROI) we first compute the KN Laguerre-Gauss transform coefficients. Then, we evaluate the mean and the variance of their magnitudes inside the ROI, so that to each pattern a morphology feature vector of length 2N K is associated.

The partial dissimilarity index dY (x, z) associated to the structure of two textures x, z is then evaluated as the the Kullback-Leibler distance KLD among the generalized Gaussian probability density functions modeling the statistical behavior of the wavelet coefficient magnitudes:

sY (x, z) = KLD W L (n) k Y x (b, 0, a) , W L (n) k Y z (b, 0, a) . (5)

where

W L (n) k Y x (b, 0, a)

represents the Laguerre-Gauss transform at location b, rotation ϕ, and scale a.

In order to evaluate the dissimilarity index related to the chromatic components Cb, Cr we characterize them by their mean and their centered moments of the second and third order [2], computed as follows:

µ = 1 N r N c Nr i=1 Nc j=1 p (i, j)(6)σ =   1 N r N c Nr i=1 Nc j=1 (p (i, j) − µ) 2   1 / 2 (7) t =   1 N r N c Nr i=1 Nc j=1 (p (i, j) − µ) 3   1 / 3 (8)

where p represents the pixel chromatic component at location (i, j), N r and N c respectively represent the height and the width of the image. The color information is therefore represented by a features vector of six elements. In this case, the color matching is based on the Euclidean distance among vectors. The partial dissimilarity index based on the chromatic components is therefore computed as follows

dCr (x, z) = [µ Cr (x) − µ Cr (z)] 2 + [σ Cr (x) − σ Cr (z)] 2 + [t Cr (x) − t Cr (z)]2 1 / 2 (9) dCb(x, z) = [µ Cb (x) − µ Cb (z)] 2 + [σ Cb (x) − σ Cb (z)] 2 + [t Cb (x) − t Cb (z)] 2 1 / 2(10)

The overall dissimilarity Dtot between two textures is finally computed as follows:

Dtot = dY (x, z) + α dCr (x, z) 2 + dCb (x, z) 2 1/2(11)

where α is the factor is used to select the relative importance between structural and chromatic components.

Clustering algorithm

The clustering algorithm proposed in the follow aims to realize a data ranking starting from a query-by-example image where the images are grouped together in clusters on the basis of a similarity index, while different relevant clusters are preserved and displayed to the user, thus representing at the same time similarity and diversity between the data set. The algorithm consists of four main steps:

1. In the first step the images in the database are ranked according to the similarity to the query image, on the base of Eq. 11. Both luminance and color components are used in this phase. The first 32 images are considered relevant and they will be used in the following steps (see table 4). 2. A new ranking is performed by computing the similarity between the 32 images previously selected with the image ranked the last position of the previous step. The comparison is made by considering both luminance and color components. A new cluster is created with the images presenting a distance value, with respect to the query image, lower than a fixed threshold. These images are removed from the initial cluster. This step is repeated until the original cluster is empty. For each cluster a feature vector is computed by averaging the features of the images belonging to it. 3. The operations performed on the images in the previous step are repeated on the clusters, by operating on theirs features vectors. This step is iterated until at least one new cluster is created. If the algorithm does not create any new cluster, the threshold is increased and the step is repeated again. This step ends if the threshold becomes higher than a fixed maximum value or the number of cluster is less than a minimum value (6 in our experiments). 4. By rearranging the clusters created at the previous step considering the number of elements it is possible to obtain the final classification, table 4.

The image which represents the cluster can be the first one in the cluster or the image with the most similar representative vector to the representative vector of the cluster.

In our experiments, the starting value of the threshold in the step 3 is the same of the threshold used in the step 2. The optimal value is automatically determined during the process by histogram evaluation.

Experimental results

The performance of the proposed method are evaluated by using a database composed by 640 images. In the database there are 40 classes of images, each class is composed by 16 images. We analyze the results obtained using each image in the database as query image. The experimental results are shown in table 5. To a better understanding of table 5 it is important to clarify the meaning of outsider and impure cluster. An outsider is an image that the algorithm puts in a wrong cluster, instead an impure cluster is a cluster which has at least one outsider. The results show that the algorithm creates a right number of cluster, indeed the average number of clusters created is 5.46 and the true average number of clusters is 4.67, furthermore the percentage of impure clusters is very low, only 9.12%.

Conclusions

In this contribution a novel method for a fair organization of the results of a query-by-example retrieval system is presented. The system is able to show,