Formulating semantic image annotation as a supervised learning problem

We introduce a new method to automatically annotate and retrieve images using a vocabulary of image semantics. The novel contributions include a discriminant formulation of the problem, a multiple instance learning solution that enables the estimation of concept probability distributions without prior image segmentation, and a hierarchical description of the density of each image class that enables very efficient training. Compared to current methods of image annotation and retrieval, the one now proposed has significantly smaller time complexity and better recognition performance. Specifically, its recognition complexity is O(C/spl times/R), where C is the number of classes (or image annotations) and R is the number of image regions, while the best results in the literature have complexity O(T/spl times/R), where T is the number of training images. Since the number of classes grows substantially slower than that of training images, the proposed method scales better during training, and processes test images faster This is illustrated through comparisons in terms of complexity, time, and recognition performance with current state-of-the-art methods.