We present a novel approach to measuring similarity between shapes and exploit it for object recognition. In our framework, the measurement of similarity is preceded by: (1) solving for correspondences between points on the two shapes; (2) using the correspondences to estimate an aligning transform. In order to solve the correspondence problem, we attach a descriptor, the shape context, to each point. The shape context at a reference point captures the distribution of the remaining points relative to it, thus offering a globally discriminative characterization. Corresponding points on two similar shapes will have similar shape contexts, enabling us to solve for correspondences as an optimal assignment problem. Given the point correspondences, we estimate the transformation that best aligns the two shapes; regularized thin-plate splines provide a flexible class of transformation maps for this purpose. The dissimilarity between the two shapes is computed as a sum of matching errors between corresponding points, together with a term measuring the magnitude of the aligning transform. We treat recognition in a nearest-neighbor classification framework as the problem of finding the stored prototype shape that is maximally similar to that in the image. Results are presented for silhouettes, trademarks, handwritten digits, and the COIL data set.

Texture is an inherently non-local image property. All common texture descriptors, therefore, have a significant spatial support which renders classical edge detection schemes inadequate for the detection of texture boundaries. In this paper we propose a novel scheme to learn filters for texture edge detection. Textures are defined by the statistical distribution of Gabor filter responses. Optimality criteria for detection reliability and localization accuracy are suggested in the spirit of Canny's edge detector. Texture edges are determined as zero crossings of the difference of the two a posteriori class distributions. An optimization algorithm is designed to determine the best filter kernel according to the underlying quality measure. The effectiveness of the approach is demonstrated on texture mondrians composed from the Brodatz album and a series of synthetic aperture radar (SAR) imagery. Moreover, we indicate how the proposed scheme can be combined with snake-type algorithms for prior-knowledge driven boundary refinement and interactive annotation.

Grouping algorithms based on histograms over measured image features have very successfully been applied to textured image segmentation. However, the competing goals of statistical estimation significance demanding few quantization levels versus the necessary richness in representation often prevent a successful application for the color cue, since quantization may result in contouring. We combine a halftoning technique called spatial quantization with distribution-based grouping algorithms to synthesize a powerful color image segmentation technique. The spatial quantization simultaneously determines color palette and halftoning by optimization of a joint cost function. It therefore allows for a highly adapted image representation with a smooth transition of color distributions for non-constant image surfaces.

We develop an approach to object recognition based on match(cid:173) ing shapes and using a resulting measure of similarity in a nearest neighbor classifier. The key algorithmic problem here is that of finding pointwise correspondences between an image shape and a stored prototype shape. We introduce a new shape descriptor, the shape context, which makes this possible, using a simple and robust algorithm. The shape context at a point captures the distri(cid:173) bution over relative positions of other shape points and thus sum(cid:173) marizes global shape in a rich, local descriptor. We demonstrate that shape contexts greatly simplify recovery of correspondences between points of two given shapes. Once shapes are aligned, shape contexts are used to define a robust score for measuring shape sim(cid:173) ilarity. We have used this score in a nearest-neighbor classifier for recognition of hand written digits as well as 3D objects, using exactly the same distance function. On the benchmark MNIST dataset of handwritten digits, this yields an error rate of 0.63%, outperforming other published techniques.

Image quantization and digital halftoning, two fundamental image processing problems, are generally performed sequentially and, in most cases, independent of each other. Color reduction with a pixel-wise defined distortion measure and the halftoning process with its local averaging neighborhood typically optimize different quality criteria or, frequently, follow a heuristic approach without reference to any quantitative quality measure. In this paper, we propose a new model to simultaneously quantize and halftone color images. The method is based on a rigorous cost-function approach which optimizes a quality criterion derived from a simplified model of human perception. It incorporates spatial and contextual information into the quantization and thus overcomes the artificial separation of quantization and halftoning. Optimization is performed by an efficient multiscale procedure which substantially alleviates the computational burden. The quality criterion and the optimization algorithms are evaluated on a representative set of artificial and real-world images showing a significant image quality improvement compared to standard color reduction approaches. Applying the developed cost function, we also suggest a new distortion measure for evaluating the overall quality of color reduction schemes.

This paper introduces a novel statistical mixture model for probabilistic grouping of distributional (histogram) data. Adopting the Bayesian framework, we propose to perform annealed maximum a posteriori estimation to compute optimal clustering solutions. In order to accelerate the optimization process, an efficient multiscale formulation is developed. We present a prototypical application of this method for the unsupervised segmentation of textured images based on local distributions of Gabor coefficients. Benchmark results indicate superior performance compared to K-means clustering and proximity-based algorithms.

This paper empirically compares nine image dissimilarity measures that are based on distributions of color and texture features summarizing over 1,000 CPU hours of computational experiments. Ground truth is collected via a novel random sampling scheme for color and via an image partitioning method for texture. Quantitative performance evaluations are given for classification, image retrieval, and segmentation tasks, and for a wide variety of dissimilarity measures. It is demonstrated how the selection of a measure, based on large scale evaluation, substantially improves the quality of classification, retrieval, and unsupervised segmentation of color and texture images.

We derive real-time global optimization algorithms for several clustering optimization methods used in unsupervised texture segmentation. Speed is achieved by exploiting the topological relation of features to design a multiscale optimization technique, while accuracy and global optimization properties are provided by a deterministic annealing method. Coarse grained costfunctions are derived for both central and sparse pairwise clustering, where the problem of coarsening sparse random graphs is solved by the concept of structured randomization. Annealing schedules and coarse-to-fine optimization are tightly coupled by a statistical convergence criterion derived from computational learning theory. The algorithms are benchmarked on Brodatz-like micro-texture mondrians. Results are presented for an autonomous robotics application.

Modeling and predicting co-occurrences of events is a fundamental problem of unsupervised learning. We develop a general statistical framework for analyzing co-occurrence data based on probabilistic clustering by mixture models. More specifically, we discuss three models which pursue different modeling goals and which differ in the way they define the probabilistic partitioning of the observations. Adopting the maximum likelihood principle, annealed EM algorithms are derived for parameter estimation. From the class of potential applications in pattern recognition and data analysis, we have chosen document retrieval, language modeling, and unsupervised texture segmentation to test and evaluate the proposed algorithms.

Image quantization and digital halftoning are fundamental problems in computer graphics, which arise when displaying high‐color images on non‐truecolor devices. Both steps are generally performed sequentially and, in most cases, independent of each other. Color quantization with a pixel‐wise defined distortion measure and the dithering process with its local neighborhood optimize different quality criteria or, frequently, follow a heuristic without reference to any quality measure. In this paper we propose a new method to simultaneously quantize and dither color images. The method is based on a rigorous cost‐function approach which optimizes a quality criterion derived from a generic model of human perception. A highly efficient algorithm for optimization based on a multiscale method is developed for the dithered color quantization cost function. The quality criterion and the optimization algorithms are evaluated on a representative set of artificial and real‐world images as well as on a collection of icons. A significant image quality improvement is observed compared to standard color reduction approaches.

We present a novel optimization framework for unsupervised texture segmentation that relies on statistical tests as a measure of homogeneity. Texture segmentation is formulated as a data clustering problem based on sparse proximity data. Dissimilarities of pairs of textured regions are computed from a multiscale Gabor filter image representation. We discuss and compare a class of clustering objective functions which is systematically derived from invariance principles. As a general optimization framework, we propose deterministic annealing based on a mean-field approximation. The canonical way to derive clustering algorithms within this framework as well as an efficient implementation of mean-field annealing and the closely related Gibbs sampler are presented. We apply both annealing variants to Brodatz-like microtexture mixtures and real-word images.

In this paper we propose and examine non-parametric statistical tests to define similarity and homogeneity measures for textures. The statistical tests are applied to the coefficients of images filtered by a multi-scale Gabor filter bank. We demonstrate that these similarity measures are useful for both, texture based image retrieval and for unsupervised texture segmentation, and hence offer a unified approach to these closely related tasks. We present results on Brodatz-like micro-textures and a collection of real-word images.

We introduce a novel optimization framework for hierarchical data clustering and apply it to the problem of unsupervised texture segmentation. The proposed objective function assesses the quality of an image partitioning simultaneously at different resolution levels and yields a sequence of consistently nested image segmentations. A novel model selection criterion to select significant image structures from various scales is proposed. As an efficient deterministic optimization heuristic a mean-field annealing algorithm is derived.

A novel approach to unsupervised texture segmentation is presented which is formulated as a combinatorial optimization problem known as pairwise data clustering with a sparse neighborhood structure. Pairwise dissimilarities between texture blocks are measured in terms of distribution differences of multi-resolution features. The feature vectors are based on a Gabor wavelet image representation. To efficiently solve the data clustering problem a deterministic annealing algorithm on the basis of a mean field approximation is derived. An application to collages of Brodatz-like microtexture is demonstrated. The adequacy of the proposed segmentation cost function is statistically validated. The deterministic annealing algorithm outperforms its stochastic variants in terms of quality and efficiency.