In this paper, we introduce a general framework for analyzing the numerical conditioning of minimal problems in multiple view geometry, using tools from computational algebra and Riemannian geometry. Special motivation comes from the fact that relative pose estimation, based on standard 5-point or 7-point Random Sample Consensus (RANSAC) algorithms, can fail even when no outliers are present and there is enough data to support a hypothesis. We argue that these cases arise due to the intrinsic instability of the 5- and 7-point minimal problems. We apply our framework to characterize the instabilities, both in terms of the world scenes that lead to infinite condition number, and directly in terms of ill-conditioned image data. The approach produces computational tests for assessing the condition number before solving the minimal problem. Lastly, synthetic and real data experiments suggest that RANSAC serves not only to remove outliers, but in practice it also selects for well-conditioned image data, which is consistent with our theory.

Relative pose estimation for RGB-D cameras is crucial in a number of applications. A typical approach relies on RANSAC to find a triplet pair of 3D point correspondences from which relative pose can be derived. A key aspect to this work ensures the geometric consistency of the triplet, i.e., pairwise distances between 3D points are preserved between the two views. Observe, however, that depth values are typically an order of magnitude less precise than feature locations, leading to large distance thresholds and admission of numerous false positives. This paper proposes that the constraint of 3D distance can be cast as a 2D constraint which we refer to as the Geometric Correspondence Constraint (GCC). This constraint states that given one pair of correspondences, the two images are partitioned into a family nested of curves such that corresponding points must lie on corresponding curves. This can act as a filter in the RANSAC process with significant savings in computation and with increased robustness and accuracy as demonstrated in experiments using TUM, ICL-NUIM, and RGBD Scene v2 datasets.

Homotopy Continuation (HC) is an effective tool for solving systems of polynomial equations arising from multiview geometry problems in computer vision. Specifically, polynomial systems of camera pose estimation are widely considered as many are used in visual odometry (VO) or simultaneous localization and mapping (SLAM) frameworks. However, existing HC solvers are very slow for many VOs or SLAMs whose efficiency is critical. In addition, in the presence of outliers, the camera pose is typically solved repeatedly under a hypothesis-verification scheme, or RANSAC, for robust estimation, discouraging even more applications from adopting HC as a practical solver. In this paper, we accelerate the state-of-the-art GPU-HC solver progressively by direct parameter homotopy evaluation, improving GPU utilization, pruning homotopy paths, and early termination of RANSAC process, showing around$9.17 \times$,$13.75 \times$,$17.06 \times$, and$17 \times$speedups on NVIDIA V100, A100, H100, and GH200 GPUs, respectively. Additionally, multiple GPUs are also used to demonstrate strong scalability on up to 8 GPUs. We apply the optimized GPU-HC solver on a trifocal pose estimation problem which solves for camera poses using triplet 2D-2D oriented point matches, where one is associated with a 3D point in space. This is particularly useful in recovering VO/SLAM estimation failure when the scene is textureless, as existing recovering methods rely on ample 2D-3D point matches regardless of many 2D-2D pairs present in the images. Experiments show that integrating the accelerated GPU-HC with modern SLAMs substantially increases the success rate of recovering estimation failure without the cost of losing significant runtime.

The semantic reconstruction of a scene relies in part on the curvilinear structure inherent in images. The recovery of curvilinear structure is not only key to the representation of objects via ridges and other object curves but is also critical to the reconstruction from texture-poor images which lack a sufficient number of features. Prior methods advocate for the recovery of curve segments from images and reconstructing these into an organized collection of 3D curve segments often referred to as the 3D curve sketch, which serves as the basis for further reconstruction of curves and surfaces. Observing that the process of edge grouping can lead to fictitious curves or missing veridical groupings, this paper advocates for a reconstruction of curvilinear structure directly from image edges in the form of a 3D edge sketch. The multiview reconstruction of edges faces significant combinatorial challenges which are effectively addressed in this paper. We demonstrate through experiments that the 3D edge sketch recovers a vast majority of the curvilinear structure and is a reliable substrate from which 3D curves can be constructed.

The Half Space Proximal (HSP) graph is a low out-degree monotonic graph with a wide range of applications in various domains, including combinatorial optimization in strings, enhancing k NN classification, simplifying chemical networks, estimating local intrinsic dimensionality, and generating uniform samples from skewed distributions, among others. However, the linear complexity of finding HSP neighbors of a query limits its scalability, thus motivating approximate indexing which sacrifices accuracy in favor of restricting the test to a small local neighborhood. This compromise leads to the loss of crucial long-range connections which as a result introduce false positives and exclude false negatives, and compromising some of the essential properties of the HSP. To overcome these limitations, this paper proposes a fast and exact algorithm for computing the HSP which enjoys sublinear complexity as demonstrated by extensive experimentation. Our hierarchical approach leverages the triangle inequality applied to pivots to enable efficient HSP search in metric spaces with the Hilbert Exclusion property. A key component of our approach is the concept of the shifted generalized hyperplane between two points, which allows for the invalidation of entire groups of points. Our approach ensures the computation of the exact HSP with efficiency, even for datasets containing hundreds of millions of points.

For a generalized (or non-central) camera model, the minimal problem for two views of six points has efficient solvers. However, minimal problems of three views with four points and three views of six lines have not yet been explored and solved, despite the efforts from the computer vision community. This paper develops the formulations of these two minimal problems and shows how state-of-the-art GPU implementations of Homotopy Continuation solver can be used effectively. The proposed methods are evaluated on both synthetic and real datasets, demonstrating that they are fast, accurate and that they improve on structure from motion estimations, when employed in an hypothesis and test setting.

We present a method for solving two minimal problems for relative camera pose estimation from three views, which are based on three view correspondences of (i) three points and one line and the novel case of (ii) three points and two lines through two of the points. These problems are too difficult to be efficiently solved by the state of the art Gröbner basis methods. Our method is based on a new efficient homotopy continuation (HC) solver framework MINUS, which dramatically speeds up previous HC solving by specializing hc methods to generic cases of our problems. We characterize their number of solutions and show with simulated experiments that our solvers are numerically robust and stable under image noise, a key contribution given the borderline intractable degree of nonlinearity of trinocular constraints. We show in real experiments that (i) sift feature location and orientation provide good enough point-and-line correspondences for three-view reconstruction and (ii) that we can solve difficult cases with too few or too noisy tentative matches, where the state of the art structure from motion initialization fails.

This paper presents the Brown Pedestrian Odometry Dataset (BPOD) for benchmarking visual odometry algorithms on data from head-mounted sensors. This dataset was captured with stereo and RGB streams from RealSense cameras with rolling and global shutters in 12 diverse indoor and outdoor locations on Brown University's campus. Its associated ground-truth trajectories were generatedfrom third-person videos that documented the recorded pedestrians' positions relative to stick-on markers placed along their paths. We evaluate the performance of canonical approaches representative of direct, feature-based, and learning-based visual odometry methods on BPOD. Our finding is that current methods which are successful on other benchmarks fail on BPOD. The failure modes correspond in part to rapid pedestrian rotation, erratic body movements, etc. We hope this dataset will play a significant role in the identification of these failure modes and in the design, development, and evaluation of pedestrian odometry algorithms.

Systems of polynomial equations arise frequently in computer vision, especially in multiview geometry problems. Traditional methods for solving these systems typically aim to eliminate variables to reach a univariate polynomial, e.g., a tenth-order polynomial for 5-point pose estimation, using clever manipulations, or more generally using Grobner basis, resultants, and elimination templates, leading to successful algorithms for multiview geometry and other problems. However, these methods do not work when the problem is complex and when they do, they face efficiency and stability issues. Homotopy Continuation (HC) can solve more complex problems without the stability issues, and with guarantees of a global solution, but they are known to be slow. In this paper we show that HC can be parallelized on a GPU, showing significant speedups up to 56 times on polynomial benchmarks. We also show that GPU-HC can be generically applied to a range of computer vision problems, including 4-view triangulation and trifocal pose estimation with unknown focal length, which cannot be solved with elimination template but they can be efficiently solved with HC. GPU-HC opens the door to easy formulation and solution of a range of computer vision problems.

Relative pose estimation using the 5-point or 7-point Random Sample Consensus (RANSAC) algorithms can fail even when no outliers are present and there are enough inliers to support a hypothesis. These cases arise due to numerical instability of the 5- and 7-point minimal problems. This paper characterizes these instabilities, both in terms of minimal world scene configurations that lead to infinite condition number in epipolar estimation, and also in terms of the related minimal image feature pair correspondence configurations. The instability is studied in the context of a novel framework for analyzing the conditioning of minimal problems in multiview geometry, based on Riemannian manifolds. Experiments with synthetic and real-world data reveal that RANSAC does not only serve to filter out outliers, but RANSAC also selects for well-conditioned image data, sufficiently separated from the ill-posed locus that our theory predicts. These findings suggest that, in future work, one could try to accelerate and increase the success of RANSAC by testing only well-conditioned image data.

There is an emerging sense that the vulnerability of Image Convolutional Neural Networks (CNN), i.e., sensitivity to image corruptions, perturbations, and adversarial attacks, is connected with Texture Bias. This relative lack of Shape Bias is also responsible for poor performance in Domain Generalization (DG). The inclusion of a role of shape alleviates these vulnerabilities and some approaches have achieved this by training on negative images, images endowed with edge maps, or images with conflicting shape and texture information. This paper advocates an explicit and complete representation of shape using a classical computer vision approach, namely, representing the shape content of an image with the shock graph of its contour map. The resulting graph and its descriptor is a complete representation of contour content and is classified using recent Graph Neural Network (GNN) methods. The experimental results on three domain shift datasets, Colored MNIST, PACS, and VLCS demonstrate that even without using appearance the shape-based approach exceeds classical Image CNN based methods in domain generalization.

This paper considers and solves the problem of estimating camera pose given a pair of point-tangent correspondences between a 3D scene and a projected image. The problem arises when considering curve geometry as the basis of forming correspondences, computation of structure and calibration, which in its simplest form is a point augmented with the curve tangent. We show that while the resectioning problem is solved with a minimum of three points given the intrinsic parameters, when points are augmented with tangent information only two points are required, leading to substantial robustness and computational savings, e.g., as a minimal engine within ransac. In addition, algorithms are developed to find a practical solution shown to effectively recover camera pose using synthetic and real datasets. This technology is intended as a building block of curve-based structure from motion systems, allowing new views to be incrementally registered to a core set of views for which relative pose has been computed.

A key bottleneck in the use of Multiview Stereo (MVS) to produce high quality reconstructions is the gaps arising from textureless, shaded areas and lack of fine-scale detail. Shape-from-Shading (SfS) has been used in conjunction with MVS to obtain fine-scale detail and veridical reconstruction in the gap areas. The similarity metric that gauges candidate correspondences is critical to this process, typically a combination of photometric consistency and brightness gradient constancy. Two observations motivate this paper. First, brightness gradient constancy can be erroneous due to foreshortening. Second, the standard ZSSD/NCC patchwise photometric consistency measures when applied to shaded areas is, to a first-order approximation, a calculation of brightness gradient differences, which can be subject to foreshortening. The paper proposes a novel trinocular differential photometric consistency that constrains the brightness gradients in three views so that the image gradient in one view is completely determined by the image gradients at corresponding points in the the other two views. The theoretical developments here advocate the integration of this new measure, whose viability in practice has been demonstrated in a set of illustrative numerical experiments.

We present a method for solving two minimal problems for relative camera pose estimation from three views, which are based on three view correspondences of (i) three points and one line and (ii) three points and two lines through two of the points. These problems are too difficult to be efficiently solved by the state of the art Grobner basis methods. Our method is based on a new efficient homotopy continuation (HC) solver, which dramatically speeds up previous HC solving by specializing HC methods to generic cases of our problems. We show in simulated experiments that our solvers are numerically robust and stable under image noise. We show in real experiment that (i) SIFT features provide good enough point-and-line correspondences for three-view reconstruction and (ii) that we can solve difficult cases with too few or too noisy tentative matches where the state of the art structure from motion initialization fails.

We propose an unsupervised method to establish dense semantic correspondences between images depicting different instances of the same object category. We posit that alignment is compositional in nature and requires the detection of a similar visual concept between images. We realize this in a top-down fashion using objectness, saliency, and visual similarity cues to co-localize the regions of holistic foreground objects. Jointly maximizing visual similarity and bounding the geometric distortion induced by their configuration, the target foreground object is then composed by the subregions of the source foreground object. The resultant composition is used to form a dense motion field enabling the alignment. Experimental results on several benchmark datasets support the efficacy of the proposed method.

The vast majority of edge detection literature has aimed at improving edge recall and precision, with relatively few addressing the accuracy of edge orientation estimates which are often based on gradient. We show that first-order estimates of orientation can have significant error and this can be remedied by employing Third-Order estimates. This paper aims at estimating differential geometry attributes of an edge, namely, localization, orientation, and curvature, as well as edge topology, and develop robust numerical techniques in gray-scale and color images, applicable to a variety of popular edge detectors, such as gradient-based, gPb and SE. Second, a combinatorial model of edge grouping in a small neighborhood is developed to capture all geometrically consistent grouping called curvels, which establish: (i) edge topology in the form of potential links between an edge and other edges; (ii) an accurate curvature estimate for each possible grouping, whose performance is comparable to methods which use global and multi-scale methods; (iii) a more accurate localization of an edge. These have been evaluated using four distinct methodologies (i) traditional human annotated datasets; (ii) using coherence measure; (iii) stability analysis under visual perturbation, and (iv) utilitarian evaluation, and show meaningful improvements.

The three-dimensional reconstruction of scenes from multiple views has made impressive strides in recent years, chiefly by methods correlating isolated feature points, intensities, or curvilinear structure. In the general setting, i.e., without requiring controlled acquisition, limited number of objects, abundant patterns on objects, or object curves to follow particular models, the majority of these methods produce unorganized point clouds, meshes, or voxel representations of the reconstructed scene, with some exceptions producing 3D drawings as networks of curves. Many applications, e.g., robotics, urban planning, industrial design, and hard surface modeling, however, require structured representations which make explicit 3D curves, surfaces, and their spatial relationships. Reconstructing surface representations can now be constrained by the 3D drawing acting like a scaffold to hang on the computed representations, leading to increased robustness and quality of reconstruction. This paper presents one way of completing such 3D drawings with surface reconstructions, by exploring occlusion reasoning through lofting algorithms.

Interest point-based multiview 3D reconstruction and calibration methods have been very successful in select applications but are not applicable when an abundance of feature points are not available. They also lead to an unorganized point cloud reconstruction where the geometry of the scene is not explicit. The multiview stereo methods on the other hand yield dense surface geometry but require a highly controlled or calibrated setting. We propose and develop a novel framework for 3D reconstruction and calibration based on image curve content, whose output is a 3D curve sketch, an unorganized set of 3D curve fragments. This approach, which is meant to augment the previous approaches, results in a reconstruction of geometric curve structure which can serve as a scaffold on which surface patches can be potentially reconstructed. It is intented for the setting where a number of images are available with coarsely calibrated cameras. The approach operates in two stages. A reliable partial 3D curve sketch is first reconstructed and this is used to refine the cameras to yield a more complete 3D curve sketch in a second stage. A key advantage of this approach is the ability to integrate information across a large number of views. The results have been evaluated on a few datasets.

The success of skeletal model in object recognition from segmented images motivates the development of a skeletal model for top-down object recognition and segmentation. We propose a novel skeleton-based generative shape model which is suitable for effi-cient search using dynamic programming (DP). We have devised an exclusion principle enabling DP to discover multiple instances of an object category in one pass. Finally, we have improved an oriented chamfer distance for rank-ordering generated hypotheses. Improved or comparable recognition and segmentation results are reported on the ETHZ data set. 1

The instabilities of the medial axis of a shape under deformations have long been recognized as a major obstacle to its use in recognition and other applications. These instabilities, or transitions, occur when the structure of the medial axis graph changes abruptly under deformations of shape. The recent classification of these transitions in 2D for the medial axis and for the shock graph was a key factor in the development of an object recognition system where the classified instabilities were utilized to represent deformation paths. The classification of generic transitions of the 3D medial axis could likewise potentially lead to a similar representation in 3D. In this paper, these transitions are classified by examining the order of contact of spheres with the surface, leading to an enumeration of possible transitions which are then examined on a case-by-case basis. Some cases are ruled out as never occurring in any family of deformations, while others are shown to be nongeneric in a one-parameter family of deformations. Finally, the remaining cases are shown to be viable by developing a specific example for each. Our work is inspired by that of Bogaevsky, who obtained the transitions as part of an investigation of viscosity solutions of Hamilton-Jacobi equations. Our contribution is to give a more down-to-earth approach, bringing this work to the attention of the computer vision community, and to provide explicit constructions for the various transitions using simple surfaces. We believe that the classification of these transitions is vital to the successful regularization of the medial axis in its use in real applications.

This paper addresses a key bottleneck in the use of the 3D medial axis (MA) representation, namely, how the complex MA structure can be regularized so that similar, within-category 3D shapes yield similar 3D MA that are distinct from the non-category shapes. We rely on previous work which (i) constructs a hierarchical MA hypergraph, the medial scaffold (MS), and (ii) the theoretical classification of the instabilities of this structure, or transitions (sudden topological changes due to a small perturbation). The shapes at transition point are degenerate. Our approach is to recognize the transitions which are close-by to a given shape and transform the shape to this transition point, and repeat until no close-by transitions exists. This move towards degeneracy is the basis of simplification of shape. We derive 11 transforms from 7 transitions and follow a greedy scheme in applying the transform. The results show that the simplified MA preserves with-in-category similarity, thus indicating its potential use in various applications including shape analysis, manipulation, and matching.

We propose a new methodology to partition a natural image into regions based on the shock graph of its contour fragments. We show that these regions, or shock patch fragments, are often object fragments, thus effecting a partial segmentation of the image. We utilize shock patch fragments to recognize objects with dominant shape cues eliminating the need to segment out the entire object from the image first. Our preliminary results with minimal training are promising with respect to the state of the art recognition systems.

We present a framework for extracting image contours based on geometric and structural consistency among edge element locations and orientations. The paper presents two contributions. First, we observe that while the traditional edge orientation operators are based on first-order derivatives, orientation as tangent of a localized curve requires third-order derivatives. We derive a numerically stable third-order edge operator and show that it outperforms current techniques. Second, we consider all discrete n-tuples of edges in a local neighborhood (7times7) and retain those that are geometrically consistent with a third-order local curve model. This results in a number of ordered discrete combinations of edges, each represented by a bundle of curves. The resulting curve bundle map is a representation of all possible local groupings from which longer contour fragments are constructed. We validate our results and show that our framework outperforms traditional approaches to contour extraction.

We propose a novel generative language for shape that is based on the shock graph: given a shock graph topology, we explore constraints on the geometry and dynamics of the shock graph branches at each point required to generate a valid shape, i.e., with no self-intersection, cusps, or crossovers. We model the shape boundary as a piece-wise smooth circular arc spline, which is dense in the space of piecewise smooth curves. Using this model we derive an independent set of parameters which generate a variety of shapes and satisfy the reconstruction constraints. We show simple examples of using this generative model as an active deformable shape and for morphing between two shapes. The results illustrate that it is possible to generate any generic shape with relatively few parameters, further reduced if prior knowledge of shape is available.

We propose an approach to model the background of images in a video sequence based on subpixel edge map. This work is motivated by the observation that intensity based background models are sensitive to changes in illumination and camera parameters, e.g., gain control. In addition, the false positive rate is higher due to accidental alignment of figure intensities with the background model. Background models of edge maps, however, are more localized and thus reduce the likelihood of accidental alignment. We argue that the discretization error in pixel-level background models is also responsible for some of the false positives and develop a method based on subpixel edges whose background is thus highly selective. This method models the edge position and orientation using a Mixture of Gaussians model. This approach has been tested on a wide range of videos and the resulting background models are a much more selective figure-ground segregation.

We introduce the notion of the medial scaffold, a hierarchical organization of the medial axis of a 3D shape in the form of a graph constructed from special medial curves connecting special medial points. A key advantage of the scaffold is that it captures the qualitative aspects of shape in a hierarchical and tightly condensed representation. We propose an efficient and exact method for computing the medial scaffold based on a notion of propagation along the scaffold itself, starting from initial sources of the flow and constructing the scaffold during the propagation. We examine this method specifically in the context of an unorganized cloud of points in 3D, e.g., as obtained from laser range finders, which typically involve hundreds of thousands of points, but the ideas are generalizable to data arising from geometrically described surface patches. The computational bottleneck in the propagation-based scheme is in finding the initial sources of the flow. We thus present several ideas to avoid the unnecessary consideration of pairs of points which cannot possibly form a medial point source, such as the "visibility" of a point from another given a third point and the interaction of clusters of points. An application of using the medial scaffold for the representation of point samplings of real-life objects is also illustrated.

Shape is an important cue for generic object recognition but can be insufficient without other cues such as object appearance. We explore a number of ways in which the geometric aspects of an object can be augmented with its appearance. The main idea is to construct a dense correspondence between the interior regions of two shapes based on a shape-based correspondence so that the intensity and gradient distributions can be compared, e.g., using a mutual information paradigm. Three methods for regional alignment are suggested and compared here, based on: (i) propagation of correspondences from the silhouette to parallel curves in the interior, (ii) intersection of line segments anchored on corresponding points on the contour, and (iii) correspondence of shape skeletons. These methods have been implemented and applied to vehicle category recognition from aerial videos under known viewing and illumination conditions. We have constructed a photo-realistic synthetic video database to explore the performance of these methods under controlled conditions. We have also tested these algorithms on real video collected for this purpose from a balloon. Our findings indicate that (i) augmenting shape with appearance significantly increases recognition rate, and (ii) the region correspondence induced by the shape skeleton yields the highest performance.

This paper proposes a novel hypergraph skeletal representation for 3D shape based on a formal derivation of the generic structure of its medial axis. By classifying each skeletal point by its order of contact, we show that, generically, the medial axis consists of five types of points, which are then organized into sheets, curves, and points: 1) sheets (manifolds with boundary) which are the locus of bitangent spheres with regular tangency A1(2) (Ak(n) notation means n distinct k-fold tangencies of the sphere of contact, as explained in the text); two types of curves, 2) the intersection curve of three sheets and the locus of centers of tritangent spheres, A1(3), and 3) the boundary of sheets, which are the locus of centers of spheres whose radius equals the larger principal curvature, i.e., higher order contact A3 points; and two types of points, 4) centers of quad-tangent spheres, A1(4), and 5) centers of spheres with one regular tangency and one higher order tangency, A1A3. The geometry of the 3D medial axis thus consists of sheets (A1(2)) bounded by one type of curve (A3) on their free end, which corresponds to ridges on the surface, and attached to two other sheets at another type of curve (A1(3)), which support a generalized cylinder description. The A3 curves can only end in A1A3 points where they must meet an A1(3) curve. The A1(3) curves meet together in fours at an A1(4) point. This formal result leads to a compact representation for 3D shape, referred to as the medial axis hypergraph representation consisting of nodes (A1(4) and A1A3 points), links between pairs of nodes (A1(3) and A3 curves) and hyperlinks between groups of links (A1(2) sheets). The description of the local geometry at nodes by itself is sufficient to capture qualitative aspects of shapes, in analogy to 2D. We derive a pointwise reconstruction formula to reconstruct a surface from this medial axis hypergraph together with the radius function. Thus, this information completely characterizes 3D shape and lays the theoretical foundation for its use in recognition, morphing, design, and manipulation of shapes.

This paper presents a novel framework for the recognition of objects based on their silhouettes. The main idea is to measure the distance between two shapes as the minimum extent of deformation necessary for one shape to match the other. Since the space of deformations is very high-dimensional, three steps are taken to make the search practical: 1) define an equivalence class for shapes based on shock-graph topology, 2) define an equivalence class for deformation paths based on shock-graph transitions, and 3) avoid complexity-increasing deformation paths by moving toward shock-graph degeneracy. Despite these steps, which tremendously reduce the search requirement, there still remain numerous deformation paths to consider. To that end, we employ an edit-distance algorithm for shock graphs that finds the optimal deformation path in polynomial time. The proposed approach gives intuitive correspondences for a variety of shapes and is robust in the presence of a wide range of visual transformations. The recognition rates on two distinct databases of 99 and 216 shapes each indicate highly successful within category matches (100 percent in top three matches), which render the framework potentially usable in a range of shape-based recognition applications.

The shock scaffold is a hierarchical organization of the medial axis in 3D consisting of special medial points and curves connecting these points, thereby forming a geometric directed graph, which is key in applications such as object recognition. In this paper we describe a method for computing the shock scaffold of realistic datasets, which involve tens or hundreds of thousands of points, in a practical time frame. Our approach is based on propagation along the scaffold from initial sources of flow by considering pairs of input points. We present seven principles which avoid the consideration of those pairs of points which cannot possibly lead to a shock flow; they involve: (i) the "visibility" of a point from another, (ii) the clustering of points, (iii) the visibility of a cluster from another, (iv) the convex hull of a cluster, (v) the vertices of such convex hulls as "virtual" points, (vi) a multi-resolution framework, and, finally, (vii) a search strategy organized in layers.

The main question we address is: What is the minimal information required to generate closed, nonintersecting planar boundaries? For this paper, we restrict "shape" to this meaning. More precisely, we examine whether the medial axis, together with dynamics, can serve as a language to design shapes and to effect shape changes. We represent the medial axis together with a direction of flow along the axis as the shock graph and examine the reconstruction of shape along each of the three types of medial axis points, A/sub 1//sup 2/, A/sub 1//sup 3/, A/sub 3/, and the associated six types of shock points. First, we show that the tangent and curvature of the medial axis and the speed and acceleration of the shock with respect to time of propagation are sufficient to determine the boundary tangent and curvature at corresponding points of the boundary. This implies that a rather coarse sampling of the symmetry axis, its tangent, curvature, speed, and acceleration is sufficient to regenerate accurately a local neighborhood of shape at regular axis points (A/sub 1//sup 2/). Second, we examine the reconstruction of shape at branch points (A/sub 1//sup 3/) where three regular branches are joined. We show that the three pairs of geometry (that is, curvature) and dynamics (that is, acceleration) must satisfy certain constraints. Finally, we derive similar results for the end points of shock branches (A/sub 3/ points). These formulas completely specify the local reconstruction of a shape from its shock-graph or medial axis and the conditions required to form a coherent shape from the medial axis.

We present a novel approach to finding a correspondence (alignment) between two curves. The correspondence is based on a notion of an alignment curve which treats both curves symmetrically. We then define a similarity metric based on the alignment curve using two intrinsic properties of the curve, namely, length and curvature. The optimal correspondence is found by an efficient dynamic-programming method both for aligning pairs of curve segments and pairs of closed curves, and is effective in the presence of a variety of transformations of the curve. Finally, the correspondence is shown in application to handwritten character recognition, prototype formation, and object recognition, and is potentially useful in other applications such as registration and tracking.

We present three distinct improvements to the neck and limb-based approach to partitioning of visual form, where pairs of negative curvature minima with good continuation of their respective tangents constitute limbs, and locally shortest lines through the shape constitute necks. The numerous conflicting limb and neck hypotheses are resolved through a notion of salience, leading to intuitive parts for smooth shapes. We improve on this approach in three ways. First a significant difficulty is dealing with scale, e.g., in partitioning noisy shapes where some perceptually valid limbs are not marked by salient negative curvature minima, and where numerous hypotheses arise due to noise. We present an approach which can reliably construct and detect coarse-scale negative curvature extremas. Second, we devise a multiscale partitioning scheme, thus minimizing the coarse-scale interaction of part-lines arising from features at different scales. Third, we employ an Euler spiral as the part-curve instead of a straight part-line for partitioning shape thus improving the partitioning results.

We approach the problem of 2D and 3D puzzle solving by matching the geometric features of puzzle pieces three at a time. First, we define an affinity measure for a pair of pieces in two stages, one based on a coarse-scale representation of curves and one based on a fine-scale elastic curve matching method. This re-examination of the top coarse-scale matches at the fine scale results in an optimal relative pose as well as a matching cost which is used as the affinity measure for a pair of pieces. Pairings with overlapping boundaries are impossible and are removed from further consideration, resulting in a set of top valid candidate pairs. Second, triples arising from generic junctions are formed from this rank-ordered list of pairs. The puzzle is solved by a recursive grouping of triples using a best-first search strategy, with backtracking in the case of overlapping pieces. We also generalize aspects of this approach to matching of 3D pieces. Specifically, ridges of 3D fragments scanned using a laser range finder are detected using a dynamic programming method. A pair of ridges are matched using a generalization of the 2D curve matching approach to space curves by using an energy solution involving curvature and torsion, which are computed using a novel robust numerical method. The reconstruction of map fragments and broken tiles using this method is illustrated.

The usefulness of the 3D medial axis (MA) is dependent on both the availability of accurate and stable methods for computing individual MA points and on schemes for deriving the local structure and connectivity among these points. We review the leading approaches for computing the 3D MA and the different fields of application for this representation of 3D shapes. We also present the shock scaffold which combines the advantages of exact bisector computations used in computational geometry on the one hand, and the local nature of propagation-based algorithms on the other, but without the computational complexity, connectivity, added dimensionality, and post processing issues commonly found in other approaches.

The type of representation used in describing shape can have a significant impact on the effectiveness of a recognition strategy. Shape has been represented by its bounding curve as well as by the medial axis representation which captures the regional interaction of the boundaries. Shape matching with the former representation is achieved by curve matching, while the latter is achieved by matching skeletal graphs. We compare the effectiveness of these two methods using approaches which we have developed recently for each. The results indicate that skeletal matching involves a higher degree of computational complexity, but is better than curve matching in the presence of articulation or rearrangement of parts. However, when these variations are not present, curve matching is a better strategy due to its lower complexity and roughly equivalent recognition rate.

This paper proposes a novel hypergraph skeletal representation for 3D shape based on a formal derivation of the generic structure of its medial axis. By classifying each skeletal point by its order of contact, we shout that generically the medial axis consists of five types of points which are then organized into sheets, curves, and points: (i) sheets (manifolds with boundary) which are the locus of bitangent spheres with regular tangency/sup 1/ A/sub 1//sup 2/. Two types of curves (ii) the intersection curve of three sheets and the locus of centers of tritangent spheres, A/sub 1//sup 3/, and (iii) the boundary of sheets which are the locus of centers of spheres whose radius equals the larger principle curvature, i.e., higher order contact A/sub 3/ points; and two types of points (iv) centers of quad-tangent spheres, A/sub 1//sup 4/, and, (v) centers of spheres with one regular tangency and one higher order tangency, A/sub 1/A/sub 3/ The geometry of the 3D medial axis thus consists of sheets (A/sub 1//sup 2/) bounded by one type of curve (A/sub 3/) on their free end, which corresponds to ridges on the surface, and attached to two other sheets at another type of curves (A/sub 1//sup 3/), which support a generalized cylinder description. The A/sub 3/ curves can only end in A/sub 1/A/sub 3/ points where they must meet an A/sub 1//sup 3/ curve. The A/sub 1//sup 3/ curves can either meet one A/sub 3/ curve or meet three other A/sub 1//sup 3/ curve at an A/sub 1//sup 4/ point. This formal result leads to a compact representation for 3D shape, referred to as the medial axis hypergraph representation consisting of nodes (A/sub 1//sup 4/ and A/sub 1/A/sub 3/ points), links between pairs of nodes (A/sub 1//sup 3/ and A/sub 3/ curves) and hyperlinks between groups of links (A/sub 1//sup 2/ sheets). The description of the local geometry at nodes by itself is sufficient to capture qualitative aspects of shapes, in analogy to 2D. We derive a pointwise reconstruction formula to reconstruct a surface from this medial axis hypergraph. Thus, the hypergraph completely characterizes 3D shape and lays the theoretical foundation for its use in recognition, morphing, design and manipulation of shapes.

We address the issue of the use of symmetry-based representations, such as the medial axis and an augmented form of it, the shock structure, to regenerate shapes. First, we address pointwise reconstruction of the boundary from points of the medial axis. As classified into three generic types (A/sup 2//1 mid-branch, A/sub 3/ end point of a branch, and A/sub 1//sup 3/ junction). Second, we examine the intrinsic reconstruction of shape when differential properties of the axis are also available. We show the surprising result that the tangent and curvature of the medial axis, coupled with the speed and acceleration of the shock flowing along the's axis, i.e., first and second order properties, are sufficient to determine the boundary tangents and curvatures at corresponding points of the boundary. This implies that for a rather coarse sampling of the symmetry axis, the location together with its tangent, curvature: speed, and acceleration is sufficient to accurately regenerate a local neighborhood of shape at this point. Together with reconstruction properties at junction (A/sup 3//sub 1/) and end points (A/sub 3/), these results lead to the full intrinsic regeneration of a shape from a representation of it as a directed planar graph (where the links represent curvature and acceleration functions, and where the nodes contain tangent and speed information): a representation ideally suited for the design and manipulation of free-form shape.

Variations in the projection of objects on a 2D image, e.g., due to occlusion and articulation, lead to edge maps which are noisy, contain gaps and spurious elements, and which are deformed. These variations in turn cause variations in the edge map which are typically regularized by the use of a salient measure for each edge element. The use of edge salience, however, typically faced with two drawback. First, salience measures take advantage of boundary continuity, but not of shape continuity, which includes continuity of the interior. Second, while each edge element can only belong to one object boundary, in the computation of salience measures, it often freely contributes to the salience of edges in competing grouping hypotheses as well. We identify both drawbacks with the lack of an explicit intermediate representation between the edge map and grouped object boundaries. We propose that (i) a symmetry map can fully represent the initial edge map so that both boundary and regional continuities can be represented via skeletal/shock continuity; (ii) a re-organization of the edge map in the form of completing gaps, discarding spurious elements, smoothing, and partitioning a contour (grouped set of edge elements) can be represented by transformations on the symmetry map; (iii) the optimal grouping corresponds to the least action path consisting of a sequence of symmetry transforms. The focus of this paper is to define transformations on the symmetry map and illustrate results for them. Specifically, we illustrate how spurious elements can be removed, gaps completed, and parts computed despite significant noise.

In this report we explore the local geometry of the medial axes (MA) and shocks (SH), and their structural changes under deformations, by viewing these symmetries as subsets of the symmetry set (SS) and present two results. First, we establish that the local form of the medial axes must generically be one of three cases: endpoints (A/sub 3/)/sup 1/, interior points (A/sub 1//sup 2/), and junctions (A/sub 1//sup 3/). The local form of shocks is a subclassification of these points. Second, we address the (classical) instability of the MA, i.e., abrupt changes in the representation with a slight changes in shape, as when a new branch appears with slight protrusion. The identification of these "transitions" is clearly crucial in robust object recognition. We show that for the medial axis only two such instabilities are possible: (i) when four branches come together (A/sub 1//sup 4/), and (ii) when a new branch grows out of an existing one (A/sub 1/A/sub 3/). Similarly, the six cases of shock instabilities are sub-classifications of these. The identification of these skeletal instabilities allows us to make equivalent structurally distinct skeletons arising from highly similar shapes, thus, regularizing the recognition process.

This paper presents an approach for computing the symmetries (skeletons) of an edge map consisting of a collection of curve segments. This approach is a combination of analytic computations in the style of computational geometry and discrete propagations on a grid in the style of the numerical solutions of PDE's. Specifically, waves from each of the initial curve segments are initialized and propagated as a discrete wavefront along discrete directions. In addition, to avoid error built up due to the discrete nature of propagation, shockwaves are detected and explicitly propagated along a secondary dynamic grid. The propagation of shockwaves, integrated with the propagation of the wavefront along discrete directions, leads to an exact simulation of propagation by the Eikonal equation. The resulting symmetries are simply the collection of shockwaves formed in this process which can be manipulated locally, exactly, and efficiently under local changes in an edge map (gap completion, removal of spurious elements, etc.). The ability to express grouping operations in the language of symmetry maps makes it an appropriate intermediate representation between low-level edge maps and high level object hypotheses.

We earlier introduced an approach to categorical shape description based on the singularities (shocks) of curve evolution equations. The approach relates to many techniques in computer vision, such as Blum's grassfire transform, but since the motivation was abstract it is not clear that it should also relate to human perception. We now report that this shock-based computational model can account for recent psychophysical data collected by Burbeck and Pizer. In these experiments subjects were asked to estimate the local centers of stimuli consisting of rectangles with `wiggles' (sides modulated by sinusoids). Since the experiments were motivated by their `core' model, in which the scale of boundary detail is proportional to object width, we conclude that such properties are also implicit in shock-based shape descriptions. More generally, the results suggest that significance is a structural notion, not an image-based one, and that scale should be defined primarily in terms of relationships between abstract entities, not concrete pixels.

The extraction of figure symmetry from image contours faces a number of fundamental difficulties: object symmetries are distorted due to (i) gaps in the bounding contour of a shape due to figure-ground blending, weak contrast edges, highlights, noise, etc.; (ii) an introduction of parts and occluders, and (iii) spurious edge elements due to surface markings, texture, etc. A framework for extracting such symmetries from real images is proposed based on the propagation of contour orientation information and the detection of four types of singularities (shocks) arising from the collision of propagating elements. In this paper, we show that an additional labeling of shocks based on whether the colliding wavefronts carry true orientation information (regular vs. rarefaction waves) allows a division of shocks into three sets: regular shocks are the partial shocks of partial contours as they remain invariant to the completion of the contour; semi-degenerate and degenerate shocks depict potential parts and gaps. Finally, shocks altered due to spurious edges, occlusion, and gaps are recovered via a simulation of inter-penetrating waves generated at select shock groups which with the aid of the above shock labels leads to second and further generations of shocks.

Subpixel methods that locate curves and their singularities, and that accurately measure geometric quantities, such as orientation and curvature, are of significant importance in computer vision and graphics. Such methods often use local surface fits or structural models for a local neighborhood of the curve to obtain the interpolated curve. Whereas their performance is good in smooth regions of the curve, it is typically poor in the vicinity of singularities. Similarly, the computation of geometric quantities is often regularized to deal with noise present in discrete data. However, in the process, discontinuities are blurred over, leading to poor estimates at them and in their vicinity. In this paper we propose a geometric interpolation technique to overcome these limitations by locating curves and obtaining geometric estimates while (1) not blurring across discontinuities and (2) explicitly and accurately placing them. The essential idea is to avoid the propagation of information across singularities. This is accomplished by a one-sided smoothing technique, where information is propagated from the direction of the side with the “smoother” neighborhood. When both sides are nonsmooth, the two existing discontinuities are relieved by placing a single discontinuity, or shock. The placement of shocks is guided by geometric continuity constraints, resulting in subpixel interpolation with accurate geometric estimates. Since the technique was originally motivated by curve evolution applications, we demonstrate its usefulness in capturing not only smooth evolving curves, but also ones with orientation discontinuities. In particular, the technique is shown to be far better than traditional methods when multiple or entire curves are present in a very small neighborhood.

We confront the theoretical and practical difficulties of computing a representation for two-dimensional shape, based on shocks or singularities that arise as the shape's boundary is deformed. First, we develop subpixel local detectors for finding and classifying shocks. Second, to show that shock patterns are not arbitrary but obey the rules of a grammar, and in addition satisfy specific topological and geometric constraints. Shock hypotheses that violate the grammar or are topologically or geometrically invalid are pruned to enforce global consistency. Survivors are organized into a hierarchical graph of shock groups computed in the reaction-diffusion space, where diffusion plays a role of regularization to determine the significance of each shock group. The shock groups can be functionally related to the object's parts, protrusions and bends, and the representation is suited to recognition: several examples illustrate its stability with rotations, scale changes, occlusion and movement of parts, even at very low resolutions.

Figure-ground segmentation is a fundamental problem in computer vision. The main difficulty is the integration of low-level, pixel-based local image features to obtain global object-based descriptions. Active contours in the form of snakes, balloons, and level-set modeling techniques have been proposed that satisfactorily address this question for certain applications. However, these methods require manual initialization, do not always perform well near sharp protrusions or indentations, or often cross gaps. We propose an approach inspired by these methods and a shock-based representation of shape in terms of parts, protrusions, and bends. Since initially it is not clear where the objects or their parts are, parts are hypothesized in the form of fourth order shocks randomly initialized in homogeneous areas of images. These shocks then form evolving contours, or bubbles, which grow, shrink, merge, split and disappear to capture the objects in the image. In the homogeneous areas of the image bubbles deform by a reaction-diffusion process. In the inhomogeneous areas, indicated by differential properties computed from low-level processes such as edge-detection, texture, optical-flow and stereo, etc., bubbles do not deform. As such, the randomly initialized bubbles integrate low-level information and, in the process, segment the figures from the ground.>

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.

Underlying recognition is an organization of objects and their parts into classes and hierarchies. A representation of parts for recognition requires that they be invariant to rigid transformations, robust in the presence of occlusions, stable with changes in viewing geometry, and be arranged in a hierarchy. These constraints are captured in a general framework using notions of a PART-LINE and a PARTITIONING SCHEME. A proposed general principle of "form from function" motivates a particular partitioning scheme involving two types of parts, neck-based and limb-based. Neck-based parts arise from narrowings in shape, or the local minima in distance between two points on the boundary, while limb-based parts arise from a pair of negative curvature minima which have "co-circular" tangents. In this paper, we present computational support for the limb-based and neck-based parts by showing that they are invariant, robust, stable and yield a hierarchy of parts. Examples illustrate that the resulting decompositions are robust in the presence of occlusion and clutter for a range of man-made and natural objects, and lead to natural and intuitive parts which can be used for recognition.>

We propose a geometric smoothing method based on local curvature in shapes and images which is governed by the geometric heat equation and is a special case of the reaction-diffusion framework proposed by Faugeras (1990). For shapes, the approach is analogous to the classical heat equation smoothing, but with a renormalization by arc-length at each infinitesimal step. For images, the smoothing is similar to anisotropic diffusion in that, since the component of diffusion in the direction of the brightness gradient is nil, edge location and sharpness are left intact. We present several properties of curvature deformation smoothing of shape: it preserves inclusion order, annihilates extrema and inflection points without creating new ones, decreases total curvature, satisfies the semi-group property allowing for local iterative computations, etc. Curvature deformation smoothing of an image is based on viewing it as a collection of iso-intensity level sets, each of which is smoothed by curvature and then reassembled. This is shown to be mathematically sound and applicable to medical, aerial and range images.>

This paper presents a novel approach to surface representation based on its differential deformations. The evolution of an arbitrary curve by curvature deforms it to a round point while in the process simplifying it. Similarly, we seek a process that deforms an arbitrary surface into a sphere without developing self-intersections, in the process creating a sequence of increasingly simpler surfaces. No previously studied curvature dependent flow satisfies this requirement: mean curvature flow leads to a splitting of the surface, while Gaussian curvature flow leads to instabilities. Thus, in search for such a process, we impose constraints (motivated by visual representation) to narrow down the space of candidate flows. Our main result is to establish a direction for the movement of points to avoid self-intersections: (1) convex elliptic points should move in, while concave elliptic points move out; and (2) hyperbolic and parabolic points should not move at all. Accordingly, we propose /spl part//spl psi///spl part/t=sign(H)/spl radic/(G.>

A proposed general principle of form from function motivates a particular partitioning scheme involving two types of parts, neck-based and limb-based. Neck-based parts arise from narrowings in shape, or the local minima in distance between two points on the boundary, while limb-based parts arise from a pair of negative curvature extrema which have co-circular tangents. Computational support for the limb-based and neck-based parts is presented by showing that they are invariant, robust, stable, and yield a hierarchy of parts. Examples illustrate that the resulting decompositions are robust in the presence of occlusion and noise for a range of man-made and natural objects and that they lead to natural and intuitive parts which can be used for recognition.>

The authors complement the standard algebraic view of mathematical morphology with a geometric, differential view. Three observations underlie this approach. (1) Certain structuring elements (convex) are scalable in that a sequence of repeated operations is equivalent to a single operation, but with a larger structuring element of the same shape. (2) To determine the outcome of the operation, it is sufficient to consider how the boundary is modified. (3) The modifications of the boundary are such that each point can be moved along the normal by a certain amount, which is dependent on the structuring element. Taken together, these observations, when the size of the structuring element shrinks to zero, assert that mathematical morphology operations with a convex structuring element are captured by a differential deformation of the boundary along the normal, governed by a Hamilton-Jacobi partial differential equation (PDE). A second theme is to show that mathematical morphology operations can be numerically implemented in a highly accurate fashion as the solution of these PDEs.>