VisualRank: Applying PageRank to Large-Scale Image Search
Paper: http://www.kevinjing.com/jing_pami.pdf
The PageRank algorithm provides a way to rank webpages by looking at the structure of a graph of hyperlinks. The ranking so generated provides search engines like Google and Bing a way to order the results of the search queries. It is one of the many measures used to determine which pages are relevant and the degree to which they are relevant. But finding relevant content is relatively easy with web documents that have text in them for two reasons. First, the text content of a web page is an intrinsic measure of the relevance of the page to a given query – you can directly look for specific words and phrases in a page to a determine if it is relevant. Second, thanks to the way web pages are created, they usually have links to the other pages, which is what the PageRank algorithm exploits to rank the pages.
Determining relevant content and their ranking is much harder in case of images. Unlike text, it is very difficult to determine if an image contains a given object, particularly due to variations in shape and size of objects. This is compounded by the fact that even images of the same object can look very different under varied rotation, scaling, perspective and lighting. Moreover, queries can be about abstract entities, which do not represent any image. For example, an image of the Cornell campus has no object named Cornell in it, yet it still is relevant. Lastly, images don’t (usually) have embedded hyperlinks that would indicate which images are relevant to others. In the face of these challenges, most commercial search engines mostly use the text associated with images (such as on the page containing the image) to determine the relevance of an image to a given text query.
Scientists at Google have developed a novel image ranking system, called VisualRank, which uses a measure of similarity between images similar to how PageRank uses hyperlinks. The linked paper discusses the details of the algorithm that is used to compute the similarity. Once the similarities are computed, they are treated as probabilities that are then used to bias the PageRank random walk, thus, providing a direct integration of the visual relevance score into the non-visual (text-based) score.