This work aims at organizing the results of query-by-example image database management system so that also the less relevant objects still representing a minority, are presented to the user. Usually, during image retrieval, the objects very similar to the query are ranked in the rst positions and shown to the user. On the contrary, objects that slightly di er from the target image, and that are less numerous, are hardly ever shown to the user. The proposed method increases the chances for a fair retrieval of multimedia data from digital databases.
Unsupervised or human guided object retrieval is one of the basic functionalities of content-centric Internet services. The rst 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 e cient 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 re nement of
the coarse annotation, extracted from the WEB pages containing the image, and
for re-ranking the results obtained by searching those annotations [
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 speci cally, 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 prede ned feature subset, we observe that the relative importance of each feature strictly depends on the user needs. Therefore, although default values for di erent applications and contests can be speci ed, 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 di erences among the search
outcomes, we simpli ed the set of features employed in the comparison. Thus,
with respect to the MPEG-7 ensemble of global and local features, see [
Let us model the global feature space V as an M -dimensional vector space, partitioned into L subspaces Wj , each one corresponding to a particular feature set, so that V can be written as direct sum of these subspaces: V = W1 W2 s(x; y) =
L X si(xi; yi); i=1 where si(xi; yi) 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 rst N features.
Let Ck;M be the set of k-combinations of the N -element index set, then for any k-combination i = (i1; i2; : : : ; ik 1; ik) let us denote with Wi the set obtained as direct sum of Vi1 ; Vi2 ; : : : ; Vik 1 ; Vik , i.e., Wi = Vi1 Vi2 : : : Vik 1 Vik :
Then given two elements x; y 2 V we de ne as partial similarity s~k;N (x; y) based on the best k features out of N as s~k;N (x; y) =
M ax k
X sih (xih ; yih ): i 2 Ck;N h=1
We observe that the concept of similarity can be easily replaced by the concept of dissimilarity. Consequently, we de ne as partial dissimilarity d~k;N (x; y) based on the best k features out of N as WM : Given two elements x; y 2 V , their similarity s(x; y) can be computed: d~k;N (x; y) = min k
X d~ih (xih ; yih ): i 2 Ck;N h=1 (1) (2) (3) (4)
The use of dissimilarity in place of similarity is suggested by the fact that some e ective 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) = fykd~k;N (x; y) g:
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. 3
Texture segmentation and classi cation has been intensively studied and many
texture description algorithms have been proposed including statistical [
In this context, a relevant role has been played by the Circular Harmonic
Functions (CHF), initially introduced in the eld of optical processing for
rotation invariant pattern recognition, and recently casted in a wavelet
decomposition scheme [
In this paper, we use the pixel classi cation algorithm employed by Randen
and Husoy in their feature set comparisons [
In our method, the texture classi cation is performed by considering both
the structural (morphological) and the color components. To represent a texture
pattern morphology, the expansion coe cients of the Laguerre-Gauss transform
of the luminance component Y corresponding to a nite set of N K order pairs
f(n; k)j n = 1; :::; N; k = 0; :::; K 1g are employed. In particular n = 1; ::; 3
and k = 0; ::; 3 at 3 di erent resolutions have been employed in the examples
reported in the following. Since the magnitude of the transform coe cients is
rotation invariant, we use their statistics. In particular, as already stated in [
The partial dissimilarity index d~Y (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 coe cient magnitudes: s~Y (x; z) = KLD h i WL(kn) Yx (b; 0; a) ; WL(kn) Yz (b; 0; a) : (5) where WL(kn) Yx (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 [
1 XNr XNc p (i; j)
NrNc i=1 j=1 2 2
1 XNr XNc (p (i; j) = 4 NrNc i=1 j=1
1 XNr XNc (p (i; j) t = 4 NrNc i=1 j=1
31/2 where p represents the pixel chromatic component at location (i; j), Nr and Nc 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 d~Cr(x; z) = h[ Cr(x)
Cr(z)]2 + [ Cr(x)
Cr(z)]2 + [tCr(x) d~Cb(x; z) = h[ Cb(x)
Cb(z)]2 + [ Cb(x)
Cb(z)]2 + [tCb(x) hd~Cr(x; z)2 + d~Cb(x; z)2i1=2 (11) where is the factor is used to select the relative importance between structural and chromatic components. 4
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 di erent 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: (6) (7) (8) 1 tCr(z)]2i /2 (9) 1 tCb(z)]2i /2 1. In the rst 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 rst 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 xed 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 xed 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 nal classi cation, table 4. The image which represents the cluster can be the rst 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. 5
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%. 6
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, together with the most similar match, also some less similar image cluster. In this way, not only objects very similar to the query are shown to the user. On the contrary, objects that slightly di er from the target image, and that are less numerous, are hardly ever shown to the user. The proposed method increases the chances that all the relevant clusters are represented in the list displayed to the user, thus preserving the diversity of possible solutions.