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 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.

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.

This is the second part of an investigation into the visual clues in illuminated scenes, in terms of the interactions between apparent contours, shade and cast shadow curves, boundary edges, and markings on smooth surfaces, pairs of surfaces meeting in a crease, and triples of surfaces meeting in a corner. We consider both “stable” and “codimension 1” cases, the latter meaning that we list events which occur in a generic “fly-past” of the scene. We assume that there is a single principal source of light. The first part of this work is [Internat. J. Comput. Vision, 82 (2009), pp. 25–47]; in this second part we give details of the cases which involve creases and corners, and the “multilocal” cases where two surfaces separated in space interact via occlusion or cast shadows. We also give some details of the mathematical background to our work; the full mathematical treatment will appear in [Damon, Giblin, and Haslinger, Characterizing Stable Local Features of Illuminated Surfaces and Their Generic Transitions from Viewer Movement, in preparation].

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 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.

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.

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.

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.

Affine invariant medial axes and symmetry sets of planar shapes are introduced and studied in this paper. Two different approaches are presented. The first one is based on affine invariant distances, and defines the symmetry set, a set containing the medial axis; as the closure of the locus of points on (at least) two affine normals an affine-equidistant from the corresponding points on the curve. The second approach is based on affine bitangent conics. In this case the symmetry set is defined as the closure of the locus of centers of conics with (at least) three-point contact with two or more distinct points on the curve. This is equivalent to conic and curve having, at those points, the same affine tangent, or the same Euclidean tangent and curvature. Although the two analogous definitions for the classical Euclidean symmetry set (medial axis) are equivalent, this is not the case for the affine group. We then show how to use the symmetry set to detect affine skew symmetry, proving that the contact based symmetry set is a straight line if and only if the given shape is the affine transformation of a symmetric object.

The frontier of a curved surface is the envelope of contour generators showing the boundary, at least locally, of the visible region swept out under viewer motion. In general, the outlines of curved surfaces (apparent contours) from different viewpoints are generated by different contour generators on the surface and hence do not provide a constraint on viewer motion. We show that frontier points, however, have projections which correspond to a real point on the surface and can be used to constrain viewer motion by the epipolar constraint. We show how to recover viewer motion from frontier points for both continuous and discrete motion, calibrated and uncalibrated cameras. We present preliminary results of an iterative scheme to recover the epipolar line structure from real image sequences using only the outlines of curved surfaces. A statistical evaluation as also performed to estimate the stability of the solution.>

It is known that the deformations of the apparent contours of a surface under perspective projection and viewer motion enable the recovery of the geometry of the surface, for example by utilising the epipolar parametrization. These methods break down with apparent contours that are singular i.e. with cusps. In this paper, we study this situation in detail and show how, nevertheless, the surface geometry (including the Gauss curvature and mean curvature of the surface) can be recovered by following the cusps. Indeed the formulae are much simpler in this case, and require lower spatio-temporal derivatives than in the general case of nonsingular apparent contours. We give a simulated example, and also show that following cusps does not by itself provide us with information on ego-motion.>

A standard method to perform skeletonisation is to use a distance transform. Unfortunately such an approach has the drawback that only the Symmetric axis transform can be computed and not the more practical smoothed local symmetries or the more general symmetry set. Using singularity theory we introduce an extended distance transform which may be used to capture more of the symmetries of a shape. We describe the relationship of this extended distance transform to the skeletal shape descriptors themselves and other geometric phenomema related to the boundary of the curve. We then show how the extended distance transform can be used to derive skeletal descriptions of an object.