1 3
DOI 10.1007/s00530-014-0419-4
Multimedia Systems
SPECIAL ISSUE PAPER
Graph‑based clustering and ranking for diversified image search
Yan Yan · Gaowen Liu · Sen Wang ·
Jian Zhang · Kai Zheng
© Springer-Verlag Berlin Heidelberg 2014
used to cluster images into topics in this paper. In order to
perform CCCMRW, a two-layer image graph is constructed
with image cluster nodes as upper layer added to a base
image graph. Conditioned on the image cluster information
from upper layer, Markov random walk is constrained to
incline to walk across different image clusters, so as to give
high rank scores to images of different topics and therefore
gain the diversity. Encouraging clustering and re-ranking
outputs on Google image search results are reported in this
paper.
Keywords Web image clustering · Ranking · Diversity ·
Visibility · Graph model
1 Introduction
Using keywords to search images are currently the most
popular approach [11], such as the Google and Yahoo!
image search engines. However, most keywords used by
persons for queries are visually polysemous words, which
means a word has several dictionary senses that are visu-
ally distinct [30]. Taken visually polysemous words as
queries the image search results always comprise images
of multiple topics and images of different topics are mixed
together. Furthermore, high ranking items always come
from a few topics, i.e. one or two topics. For instance, the
query word jaguar represents an example of visually poly-
semous word. In response to this query, images returned by
Google image search mainly fall into following four topics:
jaguar cat, jaguar car, jaguar logo and jaguar plane. How-
ever, the top 20 search results ranked by Google only cover
two limited topics: jaguar cat and jaguar car, which is in
poor diversity. The importance of result diversification has
been recognized since early work on information retrieval
Abstract In this paper, we consider the problem of clus-
tering and re-ranking web image search results so as to
improve diversity at high ranks. We propose a novel ranking
framework, namely cluster-constrained conditional Markov
random walk (CCCMRW), which has two key steps: first,
cluster images into topics, and then perform Markov ran-
dom walk in an image graph conditioned on constraints of
image cluster information. In order to cluster the retrieval
results of web images, a novel graph clustering model is
proposed in this paper. We explore the surrounding text to
mine the correlations between words and images and there-
fore the correlations are used to improve clustering results.
Two kinds of correlations, namely word to image and word
to word correlations, are mainly considered. As a standard
text process technique, tf-idf method cannot measure the
correlation of word to image directly. Therefore, we pro-
pose to combine tf-idf method with a novel feature of word,
namely visibility, to infer the word-to-image correlation.
By latent Dirichlet allocation model, we define a topic rel-
evance function to compute the weights of word-to-word
correlations. Taking word to image correlations as hetero-
geneous links and word-to-word correlations as homoge-
neous links, graph clustering algorithms, such as complex
graph clustering and spectral co-clustering, are respectively
Y. Yan · S. Wang · K. Zheng
School of Information Technology and Electrical Engineering,
The University of Queensland, Brisbane, QLD, Australia
G. Liu
Department of Information Engineering and Computer Science,
University of Trento, Trento, Italy
J. Zhang (*)
School of Science and Technology, Zhejiang International
Studies University, Zhejiang, China
e-mail: jeyzhang@outlook.com