Abstract

Annotating or tagging multimedia objects is an important task for enhancing multimedia information retrieval processes. In the context of the Web, automatic tagging deals with many issues, such as loosely tagged images and huge collections of images with no textual data at all. Recently, graph representations have been shown useful for modeling relationships between images and their associated semantics. Using these types of graphs, it is possible to represent images and their textual labels as nodes, and the relationship between them as edges, under the assumption that visual similarity implies semantic similarity. In this work, we present an algorithm for automatic tag propagation in such a graph structure, called the visual-semantic graph. This graph has been used in prior work only for the task of image retrieval re-ranking. The goal of our work, is to show how the visual-semantic graph can be used for efficient tag propagation to unlabeled images. More specifically, our contributions are: (1) An algorithm to propagate tags automatically based on the breadth-first traversal and (2) A set of heuristics for pruning this approach for large size collections. Copyright 2011 ACM.