Theoretical Foundations of Computer Vision

Invariant Thinning and Distance Transform. Thinning is a preprocessing method which is applied to binary (i.e. black-and-white) digital (i.e. discretized) images. The goal of thinning is to reduce the sets of black points in the image to “thin” sets while retaining the “topology” of them as well as “form” properties. Usually thinning methods are organized in an iterative way by “peeling off” outer layers of the sets under consideration. This implies that thinning is an extremely time-consuming task. Recently, Neusius and Olszewski [12] proposed a thinning method which is based on a distance transform. This idea is indeed not new (see e.g. [6]), but Neusius and Olszewski were the first to treat it in a systematic way. Since the distance transform can be calculated efficiently by a two-sweep method, this approach looks attractive. The aim of this paper is to show that under certain assumptions a ‘classical’ thinning method [4], which has invariance with respect to motions as a distinctive feature, also can be interpreted as a distance-transform-based method.

Symmetric Bi- and Trinocular Stereo: Tradeoffs between Theoretical Foundations and Heuristics. Tradeoffs between theoretical and heuristic sides of ill-posed problems of the intensity-based computational stereo are discussed, as applied to the previously proposed symmetric approach for solving this problem. The heuristics are needed to deal with discontinuities in stereo images due to partial occlusions of observed surface. Basically, it is these discontinuities that cause the ill-posedness of the stereo problems. Theoretical base of the symmetric stereo is refined here by introducing a novel probabilistic model of the surface geometry and by deducing compound Bayesian decision rules to be implemented by dynamic programming techniques, as in the case of simple MAP-decision with the maximum a posteriori probability. Also, several heuristics are proposed to regularize the binocular stereo.

Computer Vision and Mathematical Morphology. Mathematical morphology as originally developed by Matheron and Serra is a theory of set mappings, modeling binary image transformations, which are invariant under the group of Euclidean translations. This framework turns out to be too restricted for many applications, in particular for computer vision where group theoretical considerations such as behavior under perspective transformations and invariant object recognition play an essential role. So far, symmetry properties have been incorporated by assuming that the allowed image transformations are invariant under a certain commutative group. This can be generalized by dropping the assumption that the invariance group is commutative. To this end we consider an arbitrary homogeneous space (the plane with the Euclidean translation group is one example, the sphere with the rotation group another), i.e. a set X on which a transitive but not necessarily commutative transformation group Г is defined. As our object space we then take the Boolean algebra P(X) of all subsets of this homogeneous space. Generalizations of dilations, erosions, openings and closings are defined and several representation theorems can be proved. We outline some of the limitations of mathematical morphology in its present form for computer vision and discuss the relevance of the generalizations discussed here.

Banach Constructor and Image Compression. The Banach constructor is defined as a concept unifying special cases of deterministic fractal modeling. The fractal compression of digital images is presented as a Banach constructor defined by a patchwork. The patchwork concept is a formal mathematical model which allowed for: a compact definition of the fractal operator, specification of a condition for its contractivity (for all v norms, 1 ≤ v ≤ ∞), and formulating conditions ensuring the required fidelity of the reconstructed image. Fast fractal compression algorithm (FFC) is based on patchworks which are affine (with contrast and scaling fixed), sparse, and local. Formulas for the best fit, affine, contrast fixed transforms which perform the best fit of two digital patches, are given for v norms with v = 1, v = 2, and v = ∞. Experiments confirm superiority of quadratic norm at quality-time tradeoff.

Stability and Likelihood of Views of Three Dimensional Objects. Evaluating the representative power of two dimensional images of three dimensional objects has come up in a number of applications, mostly concerning 3D object recognition. We address the question of image characterization independently of these applications. We first introduce the basic concepts of view stability and likelihood for general objects. The stability and likelihood functions are then used to quantitatively characterize the repre-sentability of images. For objects composed of localized features, we develop explicit expressions through which the stability and likelihood functions of any view of a general object can be evaluated from its three principal second moments. This permits a quantitative characterization of the viewing sphere of objects. By way of qualitative analysis we compute the most stable and most likely views, which can identify the characteristic views of objects. We show that the most stable and most likely views of an object are the same and are often unique. This view is the “flattest” view of the object, obtained when the three dimensional object has its minimal spread along the viewing direction. We demonstrate these results using images of familiar objects.