Ambiguous Graph Matching by Evolutionary Optimization
Richard Myers and Edwin Hancock
University of York

This paper presents a method of registering ambiguous feature sets extracted from images. The method is based on Wilson and Hancock's Bayesian matching framework, which is extended to handle the case where the feature measurements are ambiguous. A multimodal evolutionary optimisation framework is proposed, which is capable of simultaneously producing several good alternative solutions. Unlike other multimodal genetic algorithms, the one reported here requires no extra parameters: solution yields are maximised by removing bias in the selection step, while optimisation performance is maintained by a local search step. An experimental study demonstrates the effectiveness of the new approach on synthetic and real data. The framework is in principle applicable to any multimodal optimisation problem where local search performs well.

Stochastic Clustering and its Applications to Image Segmentation
Yoram Gdalyahu, Daphna Wenshall and Michael Werman
Hebrew University

We present a stochastic clustering algorithm which uses pairwise similarity of elements. The problem is viewed as a graph partitioning problem, where nodes represent data elements and the weights of the edges represent pairwise similarities. We generate samples of cuts in this graph, by using David Karger's contraction algorithm, and compute an "average" cut which is our solution to the clustering problem. The stochastic nature of our method makes it robust against noise, including accidental edges and small spurious clusters. The complexity of our algorithm is very low: $O(N \log^2 N)$ for a fixed accuracy level. In addition, and without additional computational cost, our algorithm provides a hierarchy of nested partitions. We demonstrate the superiority of our method for image segmentation on a few synthetic and real images, B\&W and color, where some other recently proposed methods (such as normalized-cut) fail or perform less well.

MRF Solutions for probabilistic optical flow formulations
Sebastien Roy and Venu Govindu

In this paper we propose an efficient, non-iterative method for estimating non-parametric dense optical flow. We develop a probabilistic framework that is appropriate for describing the inherent uncertainty in the brightness constraint due to errors in image derivative computation. We separate the flow into two one-dimensional representations and pose the problem of flow estimation as one of solving for the most probable configuration of one-dimensional labels in an Markov Random Field (MRF) with linear clique potentials. The global optimum for this problem can be efficiently solved by using the maxflow computation in a graph. We develop this formulation and describe how the use of the probabilistic framework, the parametrisation and the MRF formulation together enables us to capture the desirable properties for flow estimation. We demonstrate the performance of our algorithm and compare our results with those of other algorithms described in the performance evaluation paper of Barron et. al..

Attributed Tree Homomorphism Using Association Graphs
Massimo Bartoli,  Marcello Pelillo,  Kaleem Siddiqi and Steven W. Zucker
University of Venezia, McGill University and Yale University

The matching of hierarchical relational structures is of significant interest in computer vision and pattern recognition. We have recently introduced a new solution to this problem, based on a maximal clique formulation in a (derived) ``association graph.'' This allows us to exploit the full arsenal of clique finding algorithms developed in the algorithms community. However, thus far we have focussed on one-to-one correspondences (isomorphisms), which appears to be too strict a requirement for many vision problems. In this paper we provide a generalization of the association graph framework to handle many-to-one correspondences. We define a notion of an $\epsilon$-homomorphism (a many-to-one mapping) between attributed trees, and provide a method of constructing an association graph where maximal cliques are in one-to-one correspondence with maximal subtree homomorphisms. We then solve the problem by using {\em replicator} dynamical systems from evolutionary game theory. An extension of the framework takes similarity between attribute vectors into account, and is shown to be equivalent to the maximum weight clique problem. We illustrate the approach by matching articulated and deformed shapes described by shock trees.

Recognizing Flexible Objects
Pedro Felzenszwalb and Daniel Huttenlocher
Cornell University

In this paper we present an approach to the problem of recognizing objects using generic, flexible, parts-based models. Our approach uses MAP estimation to find the globally optimal location of the model parts in an image. We identify an interesting class of models where the dependencies among the parts form a tree. The key result is that for such models the MAP estimate can be found efficiently using dynamic programming and a novel generalization of distance transforms. This distance transform method is useful in its own right, for a fairly broad range of minimization problems. We illustrate our approach using a generic model of a person, and show results of finding people in complex scenes under a broad range of lighting conditions and in varied poses. The method is quite practical, our implementation runs in just a few seconds on a desktop workstation.

Applications of Bipartite Matching to Problems in Object Recognition
Ali Shokoufandeh and Sven Dickinson
Drexel University and Rutgers University

The matching of hierarchical (e.g., multiscale or multilevel) image features is a common problem in object recognition. Such structures are often represented as trees or directed acyclic graphs, where nodes represent image feature abstractions and arcs represent spatial relations, mappings across resolution levels, component parts, etc. Such matching problems can be formulated as largest isomorphic subgraph  or largest isomorphic subtree problems, for which a wealth of literature exists in the graph algorithms community. However, the nature of the vision instantiation of this problem often precludes the direct application of these methods. Due to occlusion and noise, no significant isomorphisms may exists between two graphs or trees. In this paper, we review our application of a more general class of matching methods, called bipartite matching, to two problems in object recognition.