We present a novel computational puzzle solver for square-piece image jigsaw puzzles with no prior information such as piece orientation or anchor pieces. By "piece" we mean a square $d$d x $d$d block of pixels, where we investigate pieces as small as 7 × 7 pixels. To reconstruct such challenging puzzles, we propose to find maximum geometric consensus between pieces, specifically hierarchical piece loops. The proposed algorithm seeks out loops of four pieces and aggregates the smaller loops into higher order "loops of loops" in a bottom-up fashion. In contrast to previous puzzle solvers which aim to maximize compatibility measures between all pairs of pieces and thus depend heavily on the pairwise compatibility measures used, our approach reduces the dependency on the pairwise compatibility measures which become increasingly uninformative for small scales and instead exploits geometric agreement among pieces. Our contribution also includes an improved pairwise compatibility measure which exploits directional derivative information along adjoining boundaries of the pieces. We verify the proposed algorithm as well as its individual components with mathematical analysis and reconstruction experiments.

In this paper, we present a novel computational puzzle solver for square-piece image jigsaw puzzles with no prior information such as piece orientation, anchor pieces or resulting dimension of the puzzle. By "piece" we mean a square dxd block of pixels, where we investigate pieces as small as 7x7 pixels. To reconstruct such challenging puzzles, we aim to search for piece configurations which maximize the size of consensus (i.e. grid or loop) configurations which represent a geometric consensus or agreement among pieces. Pieces are considered for addition to the existing assemblies if these pieces increase the size of the consensus configurations. In contrast to previous puzzle solvers which goal for assemblies maximizing compatibility measures between all pairs of pieces and thus depend heavily on the pairwise compatibility measure used, our new approach reduces the dependency on the pairwise compatibility measures which become increasingly uninformative at small scales and instead exploits geometric agreement among pieces. Our contribution also includes an improved pairwise compatibility measure which exploits directional derivative information along adjoining boundaries of the pieces. For the challenging unknown orientation piece puzzles where the size of pieces is small, we reduce assembly error by up to 75% compared with previous algorithms for standard datasets.

This paper proposes a new formulation and solution to image-based 3D modeling (aka "multi-view stereo") based on generative statistical modeling and inference. The proposed new approach, named statistical inverse ray tracing, models and estimates the occlusion relationship accurately through optimizing a physically sound image generation model based on volumetric ray tracing. Together with geometric priors, they are put together into a Bayesian formulation known as Markov random field (MRF) model. This MRF model is different from typical MRFs used in image analysis in the sense that the ray clique, which models the ray-tracing process, consists of thousands of random variables instead of two to dozens. To handle the computational challenges associated with large clique size, an algorithm with linear computational complexity is developed by exploiting, using dynamic programming, the recursive chain structure of the ray clique. We further demonstrate the benefit of exact modeling and accurate estimation of the occlusion relationship by evaluating the proposed algorithm on several challenging data sets.

This paper introduces a novel approach for reassembling pot sherds found at archaeological excavation sites, for the purpose of reconstructing clay pots that had been made on a wheel. These pots and the sherds into which they have broken are axially symmetric. The reassembly process can be viewed as 3D puzzle solving or generalized cylinder learning from broken fragments. The estimation exploits both local and semi-global geometric structure, thus making it a fundamental problem of geometry estimation from noisy fragments in computer vision and pattern recognition. The data used are densely digitized 3D laser scans of each fragment's outer surface. The proposed reassembly system is automatic and functions when the pile of available fragments is from one or multiple pots, and even when pieces are missing from any pot. The geometric structure used are curves on the pot along which the surface had broken and the silhouette of a pot with respect to an axis, called axis-profile curve (APC). For reassembling multiple pots with or without missing pieces, our algorithm estimates the APC from each fragment, then reassembles into configurations the ones having distinctive APC. Further growth of configurations is based on adding remaining fragments such that their APC and break curves are consistent with those of a configuration. The method is novel, more robust and handles the largest numbers of fragments to date.

This paper proposes a new method for estimating the symmetric axis of a pottery from its small fragment using surface geometry. For the automatic assembly of broken sherds, the axis estimation is an important measure [2]. When a fragment is small, it is difficult to estimate axis orientation since it looks like a patch of a sphere and conventional methods mostly fail, but the proposed method provides reliable axis estimation by using multiple constraints. The computational cost is also much lowered. To estimate the symmetric axis, the proposed algorithm uses three constraints: (1) the curvature is constant on a circumference CH. (2) the curvature is invariant in any scale. (3) also the principal curvatures does not vary on CH. CHis a planar circle which is one of all the possible circumferences of a pottery or sherd. A hypothesis test for axis is performed using maximum likelihood. The variance of curvature, multi-scale curvature and principal curvatures are computed in the likelihood function. We also show that the principal curvatures can be used for grouping of sherds. The grouping of sherds will reduce the computation significantly by omitting impossible configurations in pottery assembly.

This paper presents a complete solution to estimating a scene's 3D geometry and appearance from multiple 2D images by using a statistical inverse ray tracing method. Instead of matching image features/pixels across images, the inverse ray tracing approach models the image generation process directly and searches for the best 3D geometry and surface reflectance model to explain all the observations. Here the image generation process is modeled through volumetric ray tracing, where the occlusion/visibility is exactly modeled. All the constraints (including ray constraints and prior knowledge about the geometry) are put into the Ray Markov Random Field (Ray MRF) formulation, developed in [10]. Differently from [10], where the voxel colors are estimated independently of the voxel occupancies, in this work, both voxel occupancies and colors (i.e., both geometry and appearance) are modeled and estimated jointly in the same inversey ray tracing framework (Ray MRF + deep belief propagation) and implemented in a common message passing scheme, which improves the accuracy significantly as verified by extensive experiments. The complete inverse ray tracing approach can better handle difficult problems in multi-view stereo than do traditional methods, including large camera baseline, occlusion, matching ambiguities, color constant or slowly changing regions, etc., without additional information and assumptions, such as initial surface estimate or simple background assumption. A prototype system is built and tested over several challenging datasets and compared with the state-of-the-art systems, which demonstrates its good performance and wide applicability.

In this paper, we present an approach to multi-view image-based 3D reconstruction by statistically inversing the ray-tracing based image generation process. The proposed algorithm is fast, accurate and does not need any initialization. The geometric representation is a discrete volume divided into voxels, with each voxel associated with two properties: opacity (shape) and color (appearance). The problem is then formulated as inferring each voxel's most probable opacity and color through MAP estimation of the developed Ray Markov Random Fields (RayMRF). RayMRF is constructed with three kinds of cliques: the usual unary and pairwise cliques favoring connected voxel regions, and most importantly ray-cliques modelling the ray-tracing based image generation process. Each ray-clique connects the voxels that the viewing ray passes through. It provides a principled way of modeling the occlusion without approximation. The inference problem involved in the MAP estimation is handled by an optimized belief propagation algorithm. One unusual structure of the proposed MRF is that each ray-clique usually involves hundreds/thousands of random variables, which seems to make the inference computationally formidable. Thanks to the special property of the ray-clique functional form, we investigate the deep factorization property of ray-clique energy and get a highly efficient algorithm based on the general loopy belief propagation, which has reduced the computational complexity from exponential to linear. Both of the efficient inference algorithm and the overall system concept are new. Combining these results in an algorithm that can reverse the image generation process very fast. 3D surface reconstruction in a 100×100×100, i.e., 106voxel space with 10 images requires roughly 3 minutes on a 3.0 GHz single-core CPU. The running time grows linearly with respect to the number of voxels and the number of images. And the speed could be further improved with a hierarchical sparse representation of the volume, like octree. Experiments on several standard datasets show the quality and speed of the proposed models and algorithms.

Central to many problems in scene understanding based on using a network of tens, hundreds or even thousands of randomly distributed cameras with on-board processing and wireless communication capability is the “efficient” reconstruction of the 3D geometry structure in the scene. What is meant by “efficient” reconstruction? In this paper we investigate this from different aspects in the context of visual sensor networks and offer a distributed reconstruction algorithm roughly meeting the following goals: 1. Close to achievable 3D reconstruction accuracy and robustness; 2. Minimization of the processing time by adaptive computing-job distribution among all the cameras in the network and asynchronous parallel processing; 3. Communication Optimization and minimization of the (battery-stored) energy, by reducing and localizing the communications between cameras. A volumetric representation of the scene is reconstructed with a shape from apparent contour algorithm, which is suitable for distributed processing because it is essentially a local operation in terms of the involved cameras, and apparent contours are robust to ourdoor illumination conditions. Each camera processes its own image and performs the computation for a small subset of voxels, and updates the voxels through collaborating with its neighbor cameras. By exploring the structure of the reconstruction algorithm, we design the minimum-spanning-tree (MST) message passing protocol in order to minimize the communication. Of interest is that the resulting system is an example of “swarm behavior”. 3D reconstruction is illustrated using two real image sets, running on a single computer. The iterative computations used in the single processor experiment are exactly the same as are those used in the network computations. Distributed concepts and algorithms for network control and communication performance are theoretical designs and estimates.

This paper presents a new normalcy model of a scene for change detection using images taken from multiple views and varying illumination conditions. Each coregistered pixel site is statistically modeled by a probability distribution conditioned on a set of pixels in a non-local neighborhood that are less likely to be affected by a change that happens at the pixel of interest. These ldquonon-compact neighborsrdquo are located using information theoretic approaches. The associated change detection algorithm is called non-compact Markovian Likelihood (NorMaL), which predicts normalcy of a scene based on non-compact neighborhoods using non-parametric conditional density estimation.

In this paper, the duality in differential form is developed between a 3D primal surface and its dual manifold formed by the surface's tangent planes, i.e., each tangent plane of the primal surface is represented as a four-dimensional vector which constitutes a point on the dual manifold. The iterated dual theorem shows that each tangent plane of the dual manifold corresponds to a point on the original 3D surface, i.e., the dual of the dual goes back to the primal. This theorem can be directly used to reconstruct 3D surface from image edges by estimating the dual manifold from these edges. In this paper we further develop the work in our original conference papers resulting in the robust differential dual operator. We argue that the operator makes good use of the information available in the image data, by using both points of intensity discontinuity and their edge directions; we provide a simple physical interpretation of what the abstract algorithm is actually estimating and why it makes sense in terms of estimation accuracy; our algorithm operates on all edges in the images, including silhouette edges, self occlusion edges, and texture edges, without distinguishing their types (thus resulting in improved accuracy and handling locally concave surface estimation if texture edges are present); the algorithm automatically handles various degeneracies; and the algorithm incorporates new methodologies for implementing the required operations such as appropriately relating edges in pairs of images, evaluating and using the algorithm's sensitivity to noise to determine the accuracy of an estimated 3D point. Experiments with both synthetic and real images demonstrate that the operator is accurate, robust to degeneracies and noise, and general for reconstructing free-form objects from occluding edges and texture edges detected in calibrated images or video sequences.

A prototype system for the automatic evolution of biomimetic structures using structural automata is described and its utility for generating digital sculpture is demonstrated. Sculptures are generated from a primordial shape which is represented in terms of a triangular mesh and sculpture is created by extending the original surface using tetrahedral structural elements. Recursively applicable rules or equivalently, automata, are defined which allow the sculptor to generate a volumetric scaffold from the original surface. This scaffold is generated using the stated rules for inserting and connecting together the tetrahedral elements. The software is operated as a generative process where sculptures are grown from an original triangular surface mesh as a sequence of layers. Each layer is created as a 2-step process. In step 1, we populate the surface with tetrahedral structures where the base of each tetrahedron coincides with a surface triangle. Step 2 re-triangulates the apexes of the tetrahedra from step 1 creating an offset and deformed version of the original surface mesh. The sculptor has artistic control of the process at all points and may assign or change rules to generate different biomimetic behaviors, i.e., structures which tend to replicate natural phenomena.

The Mid-Ocean Studio, Brown University's SHAPE lab, and Goldsmiths College are collaborating on a prototype system for the automatic evolution of biomimetic sculpture using structural automata. This collaboration is resulting in effective, computerized means to autogenerate large, increasingly complex works of art, and allowing for a long-anticipated development of the desire to create works that reflect and respond to the environment they are in. We propose to create an installation that allows visitors to a site at Goldsmiths College to experience and interact with the development of our structures.

A concept and algorithm are presented for non-iterative robust estimation of piecewise smooth curves of maximal edge strength in small image windows-typically 8/spl times/8 to 32/spl times/32. This boundary-estimation algorithm has the nice properties that it uses all the data in the window and thus can find locally weak boundaries embedded in noise or texture and boundaries when there are more than two regions to be segmented in a window; it does not require step edges-but handles ramp edges well. The curve-estimates found are among the level sets of a dth degree polynomial fit to "suitable" weightings of the image gradient vector at each pixel in the image window. Since the polynomial fitting is linear least squares, the computation to this point is very fast. Level sets then chosen to be appropriate boundary curves are those having the highest differences in average gray level in regions to either side. This computation is also fast. The boundary curves and segmented regions found are suitable for all purposes but especially for indexing using algebraic curve invariants in this form.

We introduce a completely new approach to fitting implicit polynomial geometric shape models to data and to studying these polynomials. The power of these models is in their ability to represent nonstar complex shapes in two(2D) and three-dimensional (3D) data to permit fast, repeatable fitting to unorganized data which may not be uniformly sampled and which may contain gaps, to permit position-invariant shape recognition based on new complete sets of Euclidean and affine invariants and to permit fast, stable single-computation pose estimation. The algorithm represents a significant advancement of implicit polynomial technology for four important reasons. First, it is orders of magnitude taster than existing fitting methods for implicit polynomial 2D curves and 3D surfaces, and the algorithms for 2D and 3D are essentially the same. Second, it has significantly better repeatability, numerical stability, and robustness than current methods in dealing with noisy, deformed, or missing data. Third, it can easily fit polynomials of high, such as 14th or 16th, degree. Fourth, additional linear constraints can be easily incorporated into the fitting process, and general linear vector space concepts apply.

Representations are introduced for handling 2D algebraic curves (implicit polynomial curves) of arbitrary degree in the scope of computer vision applications. These representations permit fast, accurate pose-independent shape recognition under Euclidean transformations with a complete set of invariants, and fast accurate pose-estimation based on all the polynomial coefficients. The latter is accomplished by a centering of a polynomial based on its coefficients, followed by rotation estimation by decomposing polynomial coefficient space into a union of orthogonal subspaces for which rotations within two-dimensional subspaces or identity transformations within one-dimensional subspaces result from rotations in x, y measured-data space. Angles of these rotations in the two-dimensional coefficient subspaces are proportional to each other and are integer multiples of the rotation angle in the x, y data space. By recasting this approach in terms of a complex variable, i.e., x+iy=z, and complex polynomial-coefficients, further conceptual and computational simplification results. Application to shape-based indexing into databases is presented to illustrate the usefulness and the robustness of the complex representation of algebraic curves.

An algebraic curve is defined as the zero set of a polynomial in two variables. Algebraic curves are practical for modeling shapes much more complicated than conics or superquadrics. The main drawback in representing shapes by algebraic curves has been the lack of repeatability in fitting algebraic curves to data. Usually, arguments against using algebraic curves involve references to mathematicians Wilkinson (and Runge). The first goal of this article is to understand the stability issue of algebraic curve fitting. Then a fitting method based on ridge regression and restricting the representation to well behaved subsets of polynomials is proposed, and its properties are investigated. The fitting algorithm is of sufficient stability for very fast position-invariant shape recognition, position estimation, and shape tracking, based on invariants and new representations. Among appropriate applications are shape-based indexing into image databases.

An algebraic curve is defined as the zero set of a polynomial in two variables. Algebraic curves are practical for modeling shapes much more complicated than conics or superquadrics. The main drawback in representing shapes by algebraic curves has been the lack of repeatability in fitting algebraic curves to data. A regularized fast linear fitting method based on ridge regression and restricting the representation to well behaved subsets of polynomials is proposed, and its properties are investigated. The fitting algorithm is of sufficient stability for very fast position-invariant shape recognition, position estimation, and shape tracking, based on new invariants and representations, and is appropriate to open as well as closed curves of unorganized data. Among appropriate applications are shape-based indexing into image databases.

New representations are developed for 2D IP (implicit polynomial) curves of arbitrary degree. These representations permit shape recognition and pose estimation with essentially single, rather than iterative, computation, and extract and use all the information in the polynomial coefficients. This is accomplished by decomposing polynomial coefficient space into a union of orthogonal subspaces for which rotations within two dimensional subspaces or identity transformations within one dimensional subspaces result from rotations in x, y measured-data space. These rotations in the two dimensional coefficient subspaces are related in simple ways to each other and to rotation in the x, y data space. By recasting this approach in terms of complex polynomials, i.e., z=x+iy and complex coefficients, further simplification occurs for rotations and some simplification occurs for translation.

We present completely new very powerful solutions to two fundamental problems central to computer vision. Given data sets representing C objects to be stored in a database, and given a new data set for an object, determine the object in the database that is most like the object measured. We solve this problem through use of PIMs ("Polynomial Interpolated Measures"), which is a new representation integrating implicit polynomial curves and surfaces, explicit polynomials, and discrete data sets which may be sparse. The method provides high accuracy at low computational cost. 2. Given noisy 2D data along a curve (or 3D data along a surface), decompose the data into patches such that new data taken along affine transformations or Euclidean transformations of the curve (or surface) can be decomposed into corresponding patches. Then recognition of complex or partially occluded objects can be done in terms of invariantly determined patches. We briefly outline a low computational cost image-database indexing-system based on this representation for objects having complex shape-geometry.

This paper outlines a geometric parameterization of 2D curves where the parameterization is in terms of geometric invariants and terms that determine an intrinsic coordinate system. Thus, we present a new approach to handle two fundamental problems: single-computation alignment and recognition of 2D shapes under affine transformations. The approach is model-based, and every shape is first fit by an implicit fourth degree (quartic) polynomial. Based on the decomposition of this equation into three covariant conics, we are able to define a unique intrinsic reference system that incorporates usable alignment information contained in the implicit polynomial representation, a complete set of geometric invariants, and thus an associated canonical form for a quartic. This representation permits shape recognition based on 8 affine invariants. This is illustrated in experiments with real data sets.

A new implicit polynomial (IP) fitting method is presented. It provides a different way of viewing the IP fitting problem from those of the nonlinear optimization approaches. It requires less computation, and can be done automatically or interactively. Linear programming is used to do the fitting. The approach can incorporate a variety of distance measures and global geometric constraints.

A heretofore unsolved challenge is the completely automatic and accurate estimation of road boundaries in aerial images when the roads may be partially or completely locally occluded and clutter may be prevalent. We introduce a roadfinder that is effective in meeting this challenge. The roadfinder begins with one or more seeds on each long road, and then accurately estimates the remaining boundaries, which can be found completely automatically by the algorithm described by Barzohar and Cooper (see IEEE PAMI, vol.18, no.7, p.407-21, 1996). The algorithm is robust to missing boundary edges on one side of the road and on both sides of the road simultaneously. (These arise from shadows and occlusion by trees, poles, small structures, etc.) It is also robust to clutter within the road caused by cars or trucks, and to clutter resulting from intersecting or close parallel roads. The algorithm is based on simple clutter and occlusion models and a combined multihypothesis generalized Kalman filter (MGKF).

Query By Sketch for indexing into an image database involves presenting the machine with a sketch of the object to be found in the database. The sketch can be of the object shape or distinct contours on the image of the object. This sketch can be made from memory, or can be refined interactively in response to what the database search returns at each iteration. Or the sketch can be made by generating curves of an object boundary or object-surface image-discontinuities from an example image. This paper introduces and describes a family of 2D curves for this purpose, and an algorithm for generating a representation which passes within E of a set of control points specified by the user. Control points can be placed at arbitrary locations and in arbitrary order, and can be erased by the user at will, in order to arrive at the desired shape representation. These curves can be applied in a number of ways: we illustrate their use in one approach to indexing.

Denote a point in the plane by z=(z,y) and a polynomial of nth degree in z by f(z) /spl Sigma//sub i,j//spl ges/o/sub 1/i+j/spl les/n(a/sub ij/x/sup i/y/sup j/). Denote by Z(f) the set of points for which f(z)=0. Z(f) is the 2D curve represented by f(z). In this paper, we present a new approach to fitting 2D curves to data in the plane (or 3D surfaces to range data) which has significant advantages over presently known methods. It requires considerably less computation and the resulting curve can be forced to lie close to the data set at prescribed points provided that there is an nth degree polynomial that can reasonably approximate the data. Linear programming is used to do the fitting. The approach can incorporate a variety of distance measures and global geometric constraints.

Implicit polynomial 2D curves and 3D surfaces are potentially among the most useful object or data representations for use in computer vision and image analysis. This is because of their interpolation property, Euclidean and affine invariants, and Bayesian recognizers. The paper studies and compares various fitting algorithms in a unified framework of stability analysis. It presents a new robust 3L fitting method that is repeatable, numerically stable and computationally fast and can be used for high degree implicit polynomials to capture complex object structure. With this, the authors lay down a foundation that enables a technology based on implicit polynomial curves and surfaces for applications in indexing into pictorial databases, robot vision, CAD for free-form shapes, etc.

This paper presents an automated approach to finding main roads in aerial images. The approach is to build geometric-probabilistic models for road image generation. We use Gibbs distributions. Then, given an image, roads are found by MAP (maximum a posteriori probability) estimation. The MAP estimation is handled by partitioning an image into windows, realizing the estimation in each window through the use of dynamic programming, and then, starting with the windows containing high confidence estimates, using dynamic programming again to obtain optimal global estimates of the roads present. The approach is model-based from the outset and is completely different than those appearing in the published literature. It produces two boundaries for each road, or four boundaries when a mid-road barrier is present.

We treat the use of more complex higher degree polynomial curves and surfaces of degree higher than 2, which have many desirable properties for object recognition and position estimation, and attack the instability problem arising in their use with partial and noisy data. The scenario discussed in this paper is one where we have a set of objects that are modeled as implicit polynomial functions, or a set of representations of classes of objects with each object in a class modeled as an implicit polynomial function, stored in the database. Then, given partial data from one of the objects, we want to recognize the object (or the object class) or collect more data in order to get better parameter estimates for more reliable recognition. Two problems arising in this scenario are discussed: 1) the problem of recognizing these polynomials by comparing them in terms of their coefficients; and 2) the problem of where to collect data so as to improve the parameter estimates as quickly as possible. We use an asymptotic Bayesian approximation for solving the two problems. The intrinsic dimensionality of polynomials and the use of the Mahalanobis distance are discussed.

An effective approach has appeared in the literature for recognizing a 2D curve or 3D surface objects of modest complexity based on representing an object by a single implicit polynomial of 3/sup rd/ or 4/sup th/ degree, computing a vector of Euclidean or affine invariants which are functions of the polynomial coefficients, followed by Bayesian object recognition of the invariants, thus producing a low computational cost robust recognition. This paper extends the approach, as well as an initial work on mutual invariants recognizers, to the recognition of objects too complicated to be represented by a single polynomial. Hence, an object to be recognized is partitioned into patches, each patch is represented by a single implicit polynomial, mutual invariants are computed for pairs of polynomials for pairs of patches, and the object recognition is via a Bayesian recognition of vectors of self and mutual invariants. We discuss why the complete object geometry can be captured by the geometry of pairs of patches, how to design mutual invariants, and how to match patches in the data with those in the database at a low computational cost. The approach is a low computational cost recognition of partially occluded articulated objects in an arbitrary position and in noise by recognizing the self or joint geometry of one or more patches.

We present an approach to recognition that is based on partitioning and invariant recognition in a Bayesian framework. The intended application domain is that of complex articulated objects in arbitrary position and under considerable occlusion. First, since the performance of traditional model-based recognition strategies degrades with increasing object data-base size, with partial occlusion, and with articulation, we employ a partitioning that does not rely on apriori primitives or models. Rather, this scheme decomposes segmented shapes into parts, where the form of each part is not known apriori, but is derived based on generic geometric assumptions about objects and their projections. Specifically, two types of parts, neck-based and limb-based, give rise to a shape decomposition that remains invariant under occlusion in the visible portion of the object, unaltered under articulation of parts, is stable under slight changes in viewing geometry and finally is robust with changes in resolution and scale. Second, the parts derived from the first stage are described by implicit polynomial curves. These polynomials represent the parts well and are computationally simple to fit to the data. However, the great advantage in using implicit polynomials is the algebraic invariance associated with them. Each part is represented by a vector of invariants that remains essentially independent of viewing geometry, and as such is suitable for matching purposes. The matching process is a Bayesian engine based on asymptotic distributions. In the conclusion section, we briefly indicate how this technology fits into a complete object recognition system.

This paper treats some of the problem in recognizing the geometry of objects composed of groups of curves that undergo arbitrary affine transformations, providing the objects can be invariantly segmented into groups of curves representable by third degree implicit polynomials. As an illustrative example, the authors treat the problem of representing and recognizing portions of roads in aerial images. The approach the authors develop is to represent each road segment in a disc by a third degree implicit-polynomial, and recognition of road geometry is then Bayesian recognition of a vector of mutual algebraic invariants for the polynomials within such a disc. The mutual affine invariants developed and used are for pairs of polynomials. This is a new powerful approach to dealing with the recognition of complex curves.

This paper introduces and focuses on two problems. First is the representation power of closed implicit polynomials of modest degree for curves in 2-D images and surfaces in 3-D range data. Super quadrics are a small subset of object boundaries that are well fitted by these polynomials. The second problem is the stable computationally efficient fitting of noisy data by closed implicit polynomial curves and surfaces. The attractive features of these polynomials for Vision is discussed.>

An automated approach to finding main roads in aerial images is presented. The approach is to build geometric-probabilistic models for road image generation. Gibbs distributions are used. Then, given an image, roads are found by MAP (maximum aposteriori probability) estimation. The MAP estimation is handled by partitioning an image into windows, realizing the estimation in each window through the use of dynamic programming, and then, starting with the windows containing high confidence estimates, using dynamic programming again to obtain optimal global estimates of the roads present. The approach is model-based from the outset. It produces two boundaries for each road, or four boundaries when a midroad barrier is present. >

The problem addressed is the matching of corresponding regions in two images, even when the image intensity may be smoothly varying without distinctive edges. Corresponding small regions are assumed to be related by affine transformations. The matching is done by using a new class of low computational cost affine invariants. This approach also computes the affine transformation, and is ideal for applications to 3-D motion estimation and 3-D surface reconstruction, image alignment, etc. No feature extraction, segmentation or epipolar constraint is required. The advantage of the authors' approach over area matching is that it handles large baselines, i.e., the distance between camera positions, where the differences in orientation and linear distortion of two areas being compared is large.>

The authors present a robust low-computational-cost system for recognizing freeform objects in 3-D range data or in 2-D curve data in the image plane. Objects are represented by implicit polynomials, i.e., 3-D algebraic surfaces or 2-D algebraic curves of degrees greater than two, and are recognized by computing and matching vectors of their algebraic invariants, which are functions of their coefficients that are invariant to translations, rotations, and general linear transformations. Implicit polynomials of fourth degree can represent complicated asymmetric free-form shapes. A design of Bayesian recognizers for these models and their invariants that results in low-computational-cost recognizers robust to noise, partial occlusion, and other perturbations of the data sets is considered. This work extends the work of D. Keren et al. (1992) by developing and using new invariants for 3-D surface polynomials and applying the Bayesian recognizer to operating on invariants.>

Two problems pertinent to using implicit higher degree polynomials in real-world robust systems are dealt with: (1) characterization and fitting algorithms for the subset of these algebraic curves and surfaces that is bounded and exists largely in the vicinity of the data; (2) a Mahalanobis distance for comparing the coefficients of two polynomials, to determine whether the curves or surfaces that they represent are close over a specified region. These tools make practical use of geometric invariants for determining whether one implicit polynomial curve or surface is a rotation, translation, or an affine transformation of another. The approach is ideally suited to smooth curves and smooth curved surfaces that do not have detectable features.>

An approach and algorithm for 3D primitive model recognition, parameter estimation, and segmentation from a sequence of images taken by one or more calibrated cameras are presented. Though the approach and algorithm are applicable to more general models, the experiments described are for primitive objects that are 3D planes. Given two or more images taken by one or more calibrated cameras, the algorithm simultaneously segments the images and 3D space into regions, each region associated with a single planar patch, and estimates the parameters of the 3D plane associated with each segmented region. The algorithm is suitable for parallel processing and should function at close to the best possible accuracy. Markov random fields are used to provide very coarse prior knowledge of the regions occupied by the planar patches, resulting in markedly enhanced accuracy.>

The problem of multiresolution 2-D and 3-D shape representation is addressed. Shape is defined as a probability measure with compact support. Both object representations, typically sets of curves and/or surface patches, and observations, sets of scattered data, can be represented in this way. Global properties of shapes are defined as expectations (statistical averages) of certain functions. In particular, the moments of the shapes are global properties. To any shape S and every integer d>0 is associated a shape polynomial of degree 2d, whose coefficients are functions of the moments of S. These polynomials are related to the shape S in an affine-invariant way. They yield small values near S and large values far away, and their level sets approximate S. The shape polynomials define two distances between shapes. As asymmetric measures how well one shape fits as a subset of another one; a symmetric version indicates how equal two shapes are. The evaluation of these distance measures is determined by a sequence of computationally very fast matrix operations. The distance measures are used for recognition and positioning of objects in occluded environments.>

A parametric modeling and statistical estimation approach is proposed and simulation data are shown for estimating 3-D object surfaces from images taken by calibrated cameras in two positions. The parameter estimation suggested is gradient descent, though other search strategies are also possible. Processing image data in blocks (windows) is central to the approach. After objects are modeled as patches of spheres, cylinders, planes and general quadrics-primitive objects, the estimation proceeds by searching in parameter space to simultaneously determine and use the appropriate pair of image regions, one from each image, and to use these for estimating a 3-D surface patch. The expression for the joint likelihood of the two images is derived and it is shown that the algorithm is a maximum-likelihood parameter estimator. A concept arising in the maximum likelihood estimation of 3-D surfaces is modeled and estimated. Cramer-Rao lower bounds are derived for the covariance matrices for the errors in estimating the a priori unknown object surface shape parameters.>

A unifying decision-theoretic model-based approach is presented for solving a broad range of vision problems. These include 3-D scene (outdoor and indoor) segmentation of a 2-D image, 3-D surface recognition and shape and position estimation from one or more images, and tracking of a moving camera from a sequence of images of fixed scenes. The image associated with a 3-D surface patch is locally approximated by either a homogeneous Markov random field (MRF) texture model, which is specified by a few parameters having unknown values, by parameterized contour curves having a few unknown parameters, or by other simply parameterized models. The least structured model considered consists of the expectation at each pixel of a single image treated as a completely arbitrary a priori unknown parameter, thus modeling every possible image but requiring a huge number of parameters. 3-D surfaces are modeled as functions described by a priori unknown parameters, ranging from a few to many. To provide a direct link between the image data and the 3-D surface that generates it, the 3-D surface parameters, the camera geometry, the scene lighting, and the image model parameters are related. Because of this linking, 3-D shape recognition, location and orientation estimation, and scene segmentation are possible and can be easily formulated as optimal detection and estimation problems.>

An approach is introduced to estimating object surfaces in 3D space from a sequence of images. A 3D surface of interest is modeled as a function known up to the values of a few parameters. Surface estimation is then treated as the general problem of maximum-likelihood parameter estimation based on two or more functionally related data sets, which constitute a sequence of images taken at different locations and orientations. Experiments are run to illustrate the various advantages of using as many images as possible in the estimation and of distributing camera positions from first to last over as large a baseline as possible. The authors introduce the use of asymptotic Bayesian approximations to summarize the useful information in a sequence of images, thereby drastically reducing both storage and processing. This results in a Bayesian estimator for the surface parameters. All the usual tools of statistical signal analysis can be brought to bear, the information extraction appears to be robust and computationally reasonable, the concepts are geometric and simple, and essentially optimal accuracy should result.>

A method of calculating the maximum-likelihood clustering for the unsupervised estimation of polynomial models for the data in images of smooth surfaces or for range data for such surfaces is presented. An image or a depth map of a region of smooth 3-D surface is modeled as a polynomial plus white noise. A region of physically meaningful textured-image such as the image of foliage, grass, or road in outdoor scenes or conductor or lintburn on a thick-film substrate is modeled as a colored Gaussian-Markov random field (MRF) with a polynomial mean-value function. Unsupervised-model parameter-estimation is accomplished by determining the segmentation and model parameter values that maximize the likelihood of the data or a more general Bayesian performance functional. Agglomerative clustering is used for this purpose.>

The modeling and segmentation of images by MRF's (Markov random fields) is treated. These are two-dimensional noncausal Markovian stochastic processes. Two conceptually new algorithms are presented for segmenting textured images into regions in each of which the data are modeled as one of C MRF's. The algorithms are designed to operate in real time when implemented on new parallel computer architectures that can be built with present technology. A doubly stochastic representation is used in image modeling. Here, a Gaussian MRF is used to model textures in visible light and infrared images, and an autobinary (or autoternary, etc.) MRF to model a priori information about the local geometry of textured image regions. For image segmentation, the true texture class regions are treated either as a priori completely unknown or as a realization of a binary (or ternary, etc.) MRF. In the former case, image segmentation is realized as true maximum likelihood estimation. In the latter case, it is realized as true maximum a posteriori likelihood segmentation. In addition to providing a mathematically correct means for introducing geometric structure, the autobinary (or ternary, etc.) MRF can be used in a generative mode to generate image geometries and artificial images, and such simulations constitute a very powerful tool for studying the effects of these models and the appropriate choice of model parameters. The first segmentation algorithm is hierarchical and uses a pyramid-like structure in new ways that exploit the mutual dependencies among disjoint pieces of a textured region.

A new approach is introduced to 3-D parameterized object estimation and recognition. Though the theory is applicable for any parameterization, we use a model for which objects are approximated by patches of spheres, cylinders, and planes-primitive objects. These primitive surfaces are special cases of 3-D quadric surfaces. Primitive surface estimation is treated as parameter estimation using data patches in two or more noisy images taken by calibrated cameras in different locations and from different directions. Included is the case of a single moving camera. Though various techniques can be used to implement this nonlinear estimation, we discuss the use of gradient descent. Experiments are run and discussed for the case of a sphere of unknown location. It is shown that the estimation procedure can be viewed geometrically as a cross correlation of nonlinearly transformed image patches in two or more images. Approaches to object surface segmentation into primitive object surfaces, and primitive object-type recognition are briefly presented and discussed. The attractiveness of the approach is that maximum likelihood estimation and all the usual tools of statistical signal analysis can be brought to bear, the information extraction appears to be robust and computationally reasonable, the concepts are geometric and simple, and close to optimal accuracy should result.

An important problem in robot vision is that of very accurately segmenting a t.v. image into regions that correspond to homogeneous three-dimensional surfaces in the scene. We model an image of a homogeneous surface as a polynomial plus additive white noise. Highly accurate segmentation requires knowing the polynomials representing the image surfaces. We present a maximum likelihood estimation approach to the unsupervised learning of these polynomials. 3-D objects of interest are assumed to be composed of patches of smooth surfaces. An image of an object is decomposed into square windows, with each window assumed to view a piece of one 3-D surface and sometimes pieces of two such surfaces. The window is divided into small square blocks. The data in each block is approximated by a polynomial using least squares estimation. Those blocks recognized as viewing the same 3-D surface are clustered together, and a single polynomial is fit to the data in each cluster. The clustering chosen and the fitting of a polynomial to each cluster is done simultaneously and in such a way as to maximize the likelihood of the data. The clustering used is agglomerative clustering, where each small block is initially treated as a cluster, and clustering proceeds through a sequence of stages, with a pair of clusters merged into a larger cluster at each stage. Statistical tests for the homogeneity of data in the clusters are proposed for deciding when to stop the clustering. This maximum likelihood clustering can also be applied to polynomial model estimation for 3-D range data, and Markov Random Field model estimation for textured images.

New asymptotic methods are introduced that permit computationally simple Bayesian recognition and parameter estimation for many large data sets described by a combination of algebraic, geometric, and probabilistic models. The techniques introduced permit controlled decomposition of a large problem into small problems for separate parallel processing where maximum likelihood estimation or Bayesian estimation or recognition can be realized locally. These results can be combined to arrive at globally optimum estimation or recognition. The approach is applied to the maximum likelihood estimation of 3-D complex-object position. To this end, the surface of an object is modeled as a collection of patches of primitive quadrics, i.e., planar, cylindrical, and spherical patches, possibly augmented by boundary segments. The primitive surface-patch models are specified by geometric parameters, reflecting location, orientation, and dimension information. The object-position estimation is based on sets of range data points, each set associated with an object primitive. Probability density functions are introduced that model the generation of range measurement points. This entails the formulation of a noise mechanism in three-space accounting for inaccuracies in the 3-D measurements and possibly for inaccuracies in the 3-D modeling. We develop the necessary techniques for optimal local parameter estimation and primitive boundary or surface type recognition for each small patch of data, and then optimal combining of these inaccurate locally derived parameter estimates in order to arrive at roughly globally optimum object-position estimation.

The recognition in image data of viewed patches of spheres, cylinders, and planes in the 3-D world is discussed as a first step to complex object recognition or complex object location and orientation estimation. Accordingly, an image is partitioned into small square windows, each of which is a view of a piece of a sphere, or of a cylinder, or of a plane. Windows are processed in parallel for recognition of content. New concepts and techniques include approximations of the image within a window by 2-D quadric polynomials where each approximation is constrained by one of the hypotheses that the 3-D surface shape seen is either planar, cylindrical, or spherical; a recognizer based upon these approximations to determine whether the object patch viewed is a piece of a sphere, or a piece of a cylinder, or a piece of a plane; lowpass filtering of the image by the approximation. The shape recognition is computationally simple, and for large windows is approximately Bayesian minimum-probability-of-error recognition. These classifications are useful for many purposes. One such purpose is to enable a following processor to use an appropriate estimator to estimate shape, and orientation and location parameters for the 3-D surface seen within a window.

An approach to object location and orientation estimation is discussed in which objects in 3-D space are approximated by chunks of spheres, cylinders, and planes. The surface-shape parameters of these chunks of primitive subobjects are estimated in real time from a single 2-D image assuming a Lambertian reflection model. This processing is realized by partitioning an image into small square windows and processing the windows in parallel. It is assumed that a small window views a portion of one of the spherical, cylindrical or planar chunks. The paper applies standard statistical estimators in new ways to the estimation of the 3-D shape parameters for spherical and cylindrical surfaces. Linear regression and scatter matrix eigenvalue analysis techniques are used here. The algorithms are computationally simple yet are robust and can handle noisy highly variable data.

In order to realize robust real-time 3-D object recognition and object location and orientation estimation, a 2-D image is partitioned into small square windows which are processed in parallel. It is assumed that a 3-D object can be approximated by chunks of planes, spheres, and cylinders and that one such surface type is seen within a small window. Our solutions are largely for matte surfaces (i.e. diffusely reflecting); we do touch on specular (i.e, mirror) surfaces. Two kinds of results have been obtained in this work. For the purpose of 3-D object type recognition, a simple 2-D polynomial approximation is made to the image data in a window. Based on the relationships between polynomial coefficients and 3-D surface shape-types, a reliable decision can be made as to whether the object surface seen is that of a plane, a cylinder or sphere. In addition to providing the appropriate observables for surface-type recognition, these polynomial fits act as remarkably effective nonlinear lowpass filters.

The problem considered in this paper is the estimation of highly variable object boundaries in noisy images. Boundaries may be those of a tank in an IR image, a spinal canal in a CAT scan, a cloud in a visible light image, etc. Or they may be internal to an object such as the boundary between a spherical surface and a cylindrical surface in a manufactured object. The focus of the paper is on parallel multiple-window boundary estimation algorithms. Here the image field is parti-tioned into an array of rectangular windows, and boundary finders are run simultaneously within the windows. The boundary segments found within the windows are then seamed together to obtain meaningful global boundaries. The entire procedure is treated within a maximum likelihood estimation framework that we have developed for boundary finding. Although our multiple-window estimation approach can be used with a number of local boundary finding algorithms, we concen-trate on one which is based on dynamic programming and will produce the true maximum likelihood boundary. Some theoretical considera-tions for boundary model design and boundary-finding runtime are covered. Included is the use of a low computational cost F-test for test-ing whether a window contains a boundary, and an analytical treatment which shows that use of coarse pixels with a chi-square test or an F-test improves the probability of correctly recognizing whether a boundary is present in a window.

This paper presents a suboptimal boundary estimation algorithm for noisy images which is based upon an optimal maximum likelihood problem formulation. Both the maximum likelihood formulation and the resulting algorithm are described in detail, and computational results are given. In addition, the potential power of the likelihood formulation is demonstrated through the presentation of three simple but insightful analyses of algorithm performance. These analyses are based on a technique we have developed for comparing the accuracies of different boundary finding algorithms. This technique also helps in understanding the interplay of object shape and data models in the relative performances of boundary finders. Some of the algorithm design considerations resulting from the use of our analysis technique are new and, at first, surprising. Our technique appears to be the only one developed for comparing the accuracies of different boundary finding algorithms.

This paper formulates the problem of object boundary estimation in noisy black and white images as a state sequence estimation problem for a discrete-time Markov process. Based upon this formulation and the resulting likelihood function a suboptimal estimation algorithm is developed for elliptically shaped boundaries. Appropriate transition probabilities are calculated by developing a dynamic model for boundary generation and implementing a Kalman filter.

This paper deals with the software implementa tion of a new type of region grower for object boundary finding when the boundaries are highly variable and the images very noisy. The approach is both structural and probabilistic and consists of data modeling followed by boundary finding through statistical estimation realized as cost functional minimization. The algorithm, involving a first guess at the boundary followed by successively improving approximations, is described, and also described is its implementation and experimental results.

Effective and elegant procedures have recently appeared in the published literature for determining by computer a highly variable blob boundary in a noisy image [1]-[3]. In this paper we point out that if the blob boundary is modeled as a Markov process and the additive noise is modeled as a white Gaussian noise field, then maximization of the joint likelihood of the hypothesized blob boundary and all of the image data results in roughly the same blob boundary determination as does one of the aforementioned deterministic formulations [2]. However, the formulation in this paper provides insights into and optimal parameter values for the functions involved and reveals suboptimalities in some of the formulations appearing in the literature. More generally, we agree that maximization of the joint likelihood of the hypothesized blob boundary and of the entire picture function is a fundamental approach to boundary estimation or the estimation of linear features (roads, rivers, etc.) in images, and provides a powerful mechanism for designing sequential, parallel, or other boundary estimation algorithms. The ripple filter, an advanced form of region growing, is briefly introduced and illustrates one of a number of alternative algorithms for maximizing the likelihood function. Hence, this likelihood maximization approach provides a unified view for seemingly different approaches, such as sequential boundary finding and region growing. Bounds on the accuracy of boundary estimation are readily derived with this formulation and are presented.

In this work we explore a number of questions arising in the Gaussian two-category classification problem when the common covariance matrix is unknown and must be estimated in order to approximate the hyperplane for decisionmaking, which is optimum for the true covariance matrix. Computed curves and, in some cases, closed form expressions are presented for describing the performance of such adaptive systems as a function of data dimensionality and learning sample size. In particular, we show that a considerable improvement in performance can be realized through the use of some {\em a priori} knowledge of covariance matrix structure. We use the adaptive filter output signal-to-interference noise power ratio (SIR) as a measure of detection performance to compare estimators designed for a weakly stationary stochastic process (Toeplitz form covariance matrix) with an estimator designed for a general sample covariance matrix. The ratio of expected SIR performance for a generalized covariance estimate to that for a filter which is optimum for the true covariance matrix is shown to be\cong [1 - N/N_{s} - 7/N_{s}], whereNis the filter (data) dimension, andN_{s}is the sample size. For a constrained Toeplitz form covariance matrix estimate, it is argued that the expected SIR approaches the optimum SIR as\cong [1 - \pi' (N;B)/N_{s} - 7 \pi'(N;B)/NN_{s}], with\pi'(N;B) \cong A + (B + 1) \ln N + 1/2N, whereA = 0.577is Euler's constant, and0 \leq B < Nis the input data correlation time normalized by the sampling period. Therefore, the constrained Toeplitz covariance matrix estimate appears to operate with an "effective sample size" equal toN'_{s} \cong [N/ \pi' (N;B)]N_{s}and offers the potential of high expected SIR at a sample sizeN_{s}for which the generalized estimator may provide poor results. The effective sample size is shown to be {\em even greater} if the dimensionality of the constrained Toeplitz covariance matrix estimate is tailored to the input data correlation time in the sense that only a band of lags about the main diagonal is estimated. In this case,N'_{s} \cong (kN^{2})N_{s}, where k is a constant, independent of N. An estimate of the computational error associated with the results, and due primarily to a quadratic approximation employed for the SIR, is derived and compared with the normal statistical error. Because closed form solutions for adaptive filter performance generally involve tedious calculations and involved expressions, certain other workers have relied on a similar approximation, but without the benefit of knowing the quality of the approximation for a givenNandN_{s}. Insight is also provided into other matters such as the effect of the specific form of the category mean value vector (signal) on adaptation performance. It is felt that many application areas will benefit from the results presented here, e.g., biomedical image recognition, earth resource satellite multispectral data classification, adaptive linear prediction, adaptive antenna array processing, etc. The manner in which the results impact the array processing area is discussed in some detail.

Approximation of noisy data in the plane by straight line or elliptic or single-branch hyperbolic curve segments arises in pattern recognition, data compaction, and other problems. A number of questions concerning the efficient search for and approximation of data by such curves are examined. Recursive least-squares linear curve fitting is applied to the original or to transformed data in the plane to provide computationally simple algorithms for sequentially searching out appropriate data points and fitting straight line segments or quadratic arcs to the data found. The error minimized by the algorithms is interpreted. Central processing unit (CPU) times for estimating parameters for fitting straight lines and quadratic curves are determined and compared. CPU time for data search is also determined for the case of straight line fitting. Quadratic curve fitting is shown to require about six times as much CPU time as does straight line fitting. Curves relating CPU time and fitting error are determined for straight line fitting. A number of the preceding results are extended by using maximum likelihood curve estimation, and the modification of the classical least-squares curve fit resulting from the use of an a priori probability density function for the unknown curve parameters is determined.

Satisfactory proof does not yet exist for the consistency of "learning with a probabilistic teacher" estimators, which are a class of randomized decision-directed estimators for adaptive multihypothesis decision making. Since a number of computer simulations described in the published literature indicate that the algorithms are convergent, we take as our starting point the assumption that this is generally true and develop an equation for use in determining for general distributions whether convergence is to the true parameter value. Using a numerical solution, we show that for the example of two one-dimensional Gaussian hypotheses and one unknown mean (the example appearing in the paper introducing the algorithm), if the estimator is convergent, convergence is to the true parameter value. Our formulation should be of help in constructing a more complete solution to the convergence problem and may be of use in investigating the consistency of other adaptive decision-making algorithms.

We present a view of the learning phase of statistical pattern recognition as a problem in optimum mode switching for learning systems which can operate in the supervised and nonsupervised modes. We assume the standardJ-category statistical pattern recognition model, in which patterns are represented as points in Euclideann-space and the learning problem is to estimate the unknowns in the problem probability structure. More specifically, we assume each learning sample can be processed in either mode, but the machine incurs a cost for this processing--a larger cost for processing in the supervised mode than in the nonsupervised mode. The goal is to have the machine make the decision for each learning pattern concerning mode usage that results in minimum expected cost to learn the unknowns to a predetermined accuracy. We treat the parametric problem as a problem in stochastic control. Simple closed-form expressions partially describing system performance are derived for very general problem probability structures for the case of good learning, or, equivalently, large number of learning samples. Among the results obtained for identifiable probability structures for this case are i) expressions for purely supervised and purely nonsupervised learning costs; ii) a proof that supervised learning is always faster (though not necessarily less costly) than is nonsupervised learning; iii) an example showing that, depending on the relative costs of the two mode usages as well as on the problem probability structure, the learning cost of an optimum combined-mode learning system can be remarkably lower than that of a pure-mode learning system; iv) an argument to the effect that the a posteriori distribution of the unknown parameter vector is asymptotically Gaussian for a wide range of mode usage policies; v) a fairly simple functional equation that can be solved numerically for the optimum mode usage policy (for some probability structures the nature of the optimum mode usage policy can be inferred without resorting to computer calculation); vi) the conclusion that in general optimum mode usage involves mode switching, i.e., pure-mode learning is not optimum. For the most general discretized nonidentifiable probability structure, we show that dual-mode learning may be significantly less costly than is purely supervised learning. This example also illustrates the effectiveness of making use of hard constraints, imposed by prior knowledge or experimentation, in reducing learning cost.

This paper treats an aspect of the learning or estimation phase of statistical pattern recognition (and adaptive statistical decision making in general). Simple mathematical expressions are derived for the improvement in supervised learning provided by additional nonsupervised learning when the number of learning samples is large so that asymptotic approximations are appropriate. The paper consists largely of the examination of a specific example, but, as is briefly discussed, the same procedure can be applied to other parametric problems and generalization to nonparametric problems seems possible. The example treated has the additional interesting aspect that the data does not have structure that would enable the machine to learn in the nonsupervised mode alone; but the additional nonsupervised learning can provide substantial improvement over the results obtainable by supervised learning alone. A second purpose of the paper is to suggest that a new fruitful area of research is the analytical study of the possible benefits of combining supervised and nonsupervised learning.