ICCV07 : Non-metric affinity propagation for unsupervised image categorization

Abstract:

Unsupervised categorization of images or image parts is
often needed for image and video summarization or as a
preprocessing step in supervised methods for classification,
tracking and segmentation. While many metric-based techniques
have been applied to this problem in the vision community,
often, the most natural measures of similarity (e.g.,
number of matching SIFT features) between pairs of images
or image parts is non-metric. Unsupervised categorization
by identifying a subset of representative exemplars can
be efficiently performed with the recently-proposed ‘affinity
propagation’ algorithm. In contrast to k-centers clustering,
which iteratively refines an initial randomly-chosen
set of exemplars, affinity propagation simultaneously considers
all data points as potential exemplars and iteratively
exchanges messages between data points until a good solution
emerges. When applied to the Olivetti face data set
using a translation-invariant non-metric similarity, affinity
propagation achieves a much lower reconstruction error
and nearly halves the classification error rate, compared
to state-of-the-art techniques. For the more challenging
problem of unsupervised categorization of images from the
Caltech101 data set, we derived non-metric similarities between
pairs of images by matching SIFT features. Affinity
propagation successfully identifies meaningful categories,
which provide a natural summarization of the training images
and can be used to classify new input images.

link