In a typical content-based image retrieval (CBIR) system, query result is a set of images sorted by feature similarities with respect to the query. We introduce a new approach to CBIR result representation. We propose that CBIR system should retrieve image clusters, which elements should be sorted by the most meaningful feature similarities. Actually, this paper does not present a full approach but rather work in progress.
In image search, good organization of the search results is as important as the search accuracy. Many existing CBIR search engines return large quantity of search results, ranked by their relevance to the given query. Users have to go through the list and look for the desired ones. This is a time consuming task since the returned results usually contain multiple topics and these topics are mixed together. Things become even worse when one topic is dominating but it is not what the user desires. A possible solution to this problem is to cluster search results into different semantic groups. In traditional CBIR area, image clustering techniques are often used to design a convenient user interface, which helps to make more meaningful representations of search results. However, as the images were usually represented by low level visual features, it is hard to get a good clustering result from semantic perspective, because images with high feature similarities to each other may be very different in terms of semantics. This is known as the semantic gap problem.
In this paper, we consider the problem of clustering and ranking image search results. We propose a framework to represent an image query result as a clustering structure where elements in each cluster are sorted by the most meaningful features.
In this section we will review graph partitioning and spectral clustering method, which are the foundation of our framework. Such approaches are successfuly used in
This work is partially supported by Russian Foundation for Basic Research under grant 07-07-00268. other CBIR systems, for example F-I-T[6] and ImageRank[7], but these systems do not consider information about image features meaning, which can be obtained during clustering process. However, we suppose that such kind of information can be usefull for search result representation. 2.1
Bipartite graph model Graph model is widely used in different clustering tasks, such as sparse matrix partitioning, circuit partitioning, image segmentation and document clustering. It can also be used in image clustering. Qiu[4] used the undirected bipartite graph(Figure 1) to represent the relationship between images and their low-level features. This graph is constructed as following. Assuming each image in the database is represented by an m-bin colour histogram and Hk = (h(c1); h(c2) : : : h(cm)) denotes the histogram of the k-th image, where k = 1; 2; : : : n and the value of hk(ci) indicates an association of the colour ci with the k-th image. Then the bipartite graph can be represented by a triplet G = (I ; C; W ), where I = fi1; i2; ; ing is a set of images, C = fc1; c2; ; cmg is a set of colors and W is a set of edges connecting vertices from different vertex sets, i.e., W = f< i; j > ji 2 I ; j 2 Cg. The weight of edge Wij = hi(cj ) is the j-th colour bin count of the i-th image.
Note that we can consider this graph as a similarity graph with similarity function S = Wij . The adjacency matrix of G will be written as:
M = I
C
I 0 W T
C
W
0
(
In this context co-clustering of images and features can be translated to a graph partitioning problem.
Graph partitioning and spectral co-clustering The idea of clustering is to separate a set of points into different groups according to their similarities. For data given in a form of a similarity graph this problem can be restated as follows: we want to find a partition of the graph such that the edges between different groups have very low weight (which means that points in different clusters are dissimilar from each other) and the edges within a group have high weight (which means that points within the same cluster are similar to each other). Given a similarity graph G =< V; E > (in our case V = I [ C and E = W ) with adjacency matrix M , the simplest and most direct way to construct a partition is to solve the mincut problem. This consists of choosing the partition fA1; : : : ; Akg which minimizes where cut(A1; : : : Ak) = k X cut(Ai; Ai) i=1 cut(Ai; Ai) =
X i2A;j2Ai mij ; mij is element of adjacency matrix M , which corresponds to edge form i vertex to j vertex, and Ai is the complement of a subset A 2 V . The problem is that in many cases, the solution of mincut simply consists in separating one individual vertex from the rest of the graph. Of course this is not what we want to achieve in clustering, as clusters should be reasonably large groups of points. One way to circumvent this problem is to explicitly request that the sets A1; : : : ; Ak are ”reasonably large”. The two most common objective functions which encode this are RatioCut and the normalized cut – Ncut. In RatioCut, the size of a subset A of a graph is measured by its number of vertices j j A , while in Ncut the size is measured by the weights of its edges vol(A).
RatioCut(A1; : : : Ak) =
N cut(A1; : : : Ak) =
Pk i=1 cut(Ai; Ai)
jAij Pk i=1 cut(Ai; Ai) vol(Ai) In this work we use Ncut as objective function, because it implements both clustering tasks mentioned below: Ncut minimizes the between-cluster similarity and maximizes the within-cluster similarity unlike RatioCut, that implements only first of them. Ncut could be rewritten as a trace minimization problem and leads to retrieving first k generalized eigenvectors of
Lv =
Dv
here D is a diagonal matrix with Dii = Pkn=1 mik,
which is also called degree matrix, and L = D M
is unnormalized graph Laplacian matrix. After that, the
desired image clusters can be obtained by running some
routine clustering algorithms such as k-means on these
eigenvectors.
(
Co-clustering and ranking framework Suppose the dashed line in Figure 1 shows the very partition that minimizes two part cut. After applying clustering algorithm, we will obtain two subsets fi1; i2; i3; i4; c1; c2g and fi5; i6; c3; c4g. We define such clusters as mixed. Consequently, the low-level features are divided into two feature clusters fc1; c2g and fc3; c4g, while the images are divided into two image clusters fi1; i2; i3; i4g and fi5; i6g respectively. The most of CBIR systems return obtained image subsets and do not use feature subsets at all. We propose to sort images in each image cluster using low-level features from corresponding feature cluster. We suggest that such kind of ranking helps us to improve image retrieval results.
To sort images by more than one feature we need a data fusion method. In general data fusion is use of techniques that combine data from multiple sources and gather that information in order to achieve inferences, which will be more efficient and potentially more accurate than if they were achieved by means of a single source. In our case source is a list of images ranked by one of the selected low-level features. A lot of commonly used data fusion algorithms such as CombSUM, CombMNZ are successfuly used in text retrieval. CombMNZ is considered to outperform other data fusion algorithms. It works as follows. Element in the result ranked-list gets rank equaled to the sum of all its ranks in fused lists multipied by the number of lists in which this element exists with non-zero rank: rankresult(i) = ranklist(i) nz
(7)
X fusedlists where nz is number of non-zero rank lists. To summarize, our algorithm of images and features co-clustering and ranking can be listed as below.
Algorithm 1 Co-clustering and ranking algorithm Require: Image set I and the vectors H representing histograms of these images 1: Form a bipartite graph G =< I; C; W > 2: Compute matrix M , D : Dii = Pn k=1 mik and L =
D M . 3: Compute the first k eigenvectors v1; : : : ; vk of the generalized eigenproblem Lv = Dv. 4: Let V 2 Rn k be the matrix containing the vectors v1; : : : ; vk as columns. 5: For i = 1 : : : n let yi 2 Rk be the vector corresponding to the i-th row of V . 6: Cluster the points (yi)i=1;:::;n in Rk with the kmeans algorithm into mixed clusters C1; : : : ; Ck. 7: Extract image clusters from mixed ones. Rank images in every cluster use features from corresponding feature clusters and data fusion method CombMNZ. 8: Return set of image clusters I1; : : : ; Ik.
It is important to note that we should normalize feature values before applying the algorithm to the graph. In fact, most widely used image features such as color histogram, CPAM histogram and Spatial CPAM, have already introduced the mechanism of normalization. First, we will test our framework on real image queries. We plan to use two different databases from CorelPhotoSet collection: ImageDBCorel database(650 images in 9 semantic classes) and CorelSmall-100 database(100 images in 16 semantic classes). Second, if our co-clustering and ranking scheme gives good results, we use the following research approach.
As in many other clustering systems, the most difficult question in our co-clustering scheme is ”How will we define a number of clusters?”. In our case such clustering algorithms as G-means and X-means, which provide a number of clusters, are not applicable because we need this number for eigenvectors search before clustering algorithm starts. There is some research in spectral clustering, where authors propose to use eigengap in order to define a correct number of clusters, so this method can be tested in our framework too.
Concerning directly clustering algorithm, K-means is easy-to-implement classical method which can provide a good clustering scheme. In our case its main disadvantage is the assumption that image clusters are crisp, but it is easy to see that in most cases image clusters are overlaping. Therefore we suppose that fuzzy clustering methods(for example fuzzy K-means) can provide more realevant result in image clustering than crisp ones and we will check this hypothesis.
Also our framework should be extended for using multiple feature sets: color histograms and texture features simultaneously, because only color data is insufficient for retrieval in collections of heterogeneous images. Actually, in this case we have two important problems. First of them is definition a set of features which should be used for clustering. A wide variety of color, texture and shape features have been proposed to represent image content, so selecting the most meaningful ones is really difficult. The second problem is a normalization problem. If we combine all our image features values into one image representation vector, this vector should be normalized. Suitable normalization method is needed. 5
This research is conducted under the supervision of Boris Novikov. The contribution of this paper is a model of new co-clustering and ranking scheme. This scheme combines different information retrieval technics, such as spectral clustering, ranking and data fusion methods, in order to improve image retrieval effectiveness. We suppose that our search results representation should be realy convinient and helpful. We plan to include the developed framework into CBIR system Foto Finder, which is being created in our research group.
Guoping Qiu: CBipartite Graph Partitioning and Content-based Image Clustering.
Manjeet Rege, Ming Dong, Jing Hua: Clustering Web Images with Multi-modal Features. SIGMM07, September 2328, 2007.
Bin Gao, Tie-Yan Liu, Tao Qin, Xin Zheng1, QianSheng Cheng, Wei-Ying Ma: Web Image Clustering by Consistent Utilization of Visual Features and Surrounding Texts. SIGMM05, November 611, 2005.
Xiaofei He, Wei-Ying Ma, Hongjiang Zhang: ImageRank : Spectral Tecnhiques For Structural Analysis of Image Database.