An optimization approach to labelling problems in computer vision.

This thesis is concerned with the development of an optimization based approach to solving labelling problems which involve the assignment of image entities into interpretation categories in computer vision. Attention is mainly focussed on the theoretical basis and computational aspect of continuous relaxation for solving a discrete labelling problem based on an optimization framework. First, a theoretical basis for continuous relaxation is presented which includes the formulation of a discrete labelling problem as a continuous minimization problem and an analysis of labelling unambiguity associated with continuous relaxation. The main advantage of the formulation over existing formulations is the embedding of relational measurements into the specification of a consistent labelling. The analysis provides a sufficient condition for a continuous labelling formulation to ensure that a consistent labelling is unambiguous. Second, a continuous relaxation labelling algorithm based on mean field theory is presented with the aim of approximating simulated annealing in a deterministic manner. The novelty of the algorithm lies in the utilization of mean field theory technique to avoid stochastic optimization for approximating the global optimum of a consistent labelling criterion. This is contrast to the conventional methods which find a local optimum near an initial estimate of labelling. A special three-frame discrete labelling problem of establishing trinocular stereo correspondence and a mixed labelling problem of interpreting image entities in terms of cylindrical objects and their locations are also addressed. For the former, two orientation based geometric constraints are suggested for matching lines among three viewpoints and a method is presented to find a consistent labelling using simulated annealing. For the latter, the image interpretation of 3D cylindrical objects and their 3D locations is achieved using three knowledge sources: edge map, region map and the ground plane constraint. The method differs from existing methods in that it exploits an integrated use of multiple image cues to simplify the interpretation task and improve the interpretation performance. Experimental results on both synthetic data and real images are provided to demonstrate the viability and the potential of the proposed methods throughout the thesis