An algebraic approach to shape-from-image problems

Decomposition of complex line drawings with hidden lines for 3D planar-faced manifold object reconstruction

Three-dimensional object reconstruction from a single 2D line drawing is an important problem in computer vision. Many methods have been presented to solve this problem, but they usually fail when the geometric structure of a 3D object becomes complex. In this paper, a novel approach based on a divide-and-conquer strategy is proposed to handle the 3D reconstruction of a planar-faced complex manifold object from its 2D line drawing with hidden lines visible. The approach consists of four steps: 1) identifying the internal faces of the line drawing, 2) decomposing the line drawing into multiple simpler ones based on the internal faces, 3) reconstructing the 3D shapes from these simpler line drawings, and 4) merging the 3D shapes into one complete object represented by the original line drawing. A number of examples are provided to show that our approach can handle 3D reconstruction of more complex objects than previous methods.

A symbolic approach to polyhedral scene analysis by parametric calotte propagation

Polyhedral scene analysis studies whether a 2D line drawing of a 3D polyhedron is realizable in space, and if so, it gives the results of parameterizing the space of all possible realizations. For generic 2D data, symbolic computation with Grassmann–Cayley algebra is needed in the analysis. In this paper, we propose a method called parametric calotte propagation to solve the realization and parameterization problems for general polyhedral scenes at the same time. In algebraic manipulation, parametric propagation is more efficient than elimination. In applications, it can lead to linear construction sequences for nonspherical polyhedra whose resolvable sequences do not exist.

What the back of the object looks like: 3D reconstruction from line drawings without hidden lines

The human vision system can interpret a single 2D line drawing as a 3D object without much difficulty even if the hidden lines of the object are invisible. Many reconstruction methods have been proposed to emulate this ability, but they cannot recover the complete object if the hidden lines of the object are not shown. This paper proposes a novel approach to reconstructing a complete 3D object, including the shape of the back of the object, from a line drawing without hidden lines. First, we develop theoretical constraints and an algorithm for the inference of the topology of the invisible edges and vertices of an object. Then we present a reconstruction method based on perceptual symmetry and planarity of the object. We show a number of examples to demonstrate the success of our approach.

Plane-based optimization for 3D object reconstruction from single line drawings

In previous optimization-based methods of 3D planar-faced object reconstruction from single 2D line drawings, the missing depths of the vertices of a line drawing (and other parameters in some methods) are used as the variables of the objective functions. A 3D object with planar faces is derived by finding values for these variables that minimize the objective functions. These methods work well for simple objects with a small number N of variables. As N grows, however, it is very difficult for them to find expected objects. This is because with the nonlinear objective functions in a space of large dimension N, the search for optimal solutions can easily get trapped into local minima. In this paper, we use the parameters of the planes that pass through the planar faces of an object as the variables of the objective function. This leads to a set of linear constraints on the planes of the object, resulting in a much lower dimensional nullspace where optimization is easier to achieve. We prove that the dimension of this nullspace is exactly equal to the minimum number of vertex depths which define the 3D object. Since a practical line drawing is usually not an exact projection of a 3D object, we expand the nullspace to a larger space based on the singular value decomposition of the projection matrix of the line drawing. In this space, robust 3D reconstruction can be achieved. Compared with two most related methods, our method not only can reconstruct more complex 3D objects from 2D line drawings, but also is computationally more efficient.

A shape-from-shading method of polyhedral objects using prior information

We propose a new method for recovering the 3D shape of a polyhedral object from its single 2D image using the shading information contained in the image and the prior information on the object. In a strict sense, we cannot recover the shape of a polyhedron from an incorrect line drawing, even if it is practically almost correct. In order to overcome this problem, we propose a flexible face positioning method that can permit inconsistencies in the recovered shape that arise from vertex-position errors contained in incorrect line drawings. Also, we propose to use prior information about the horizontality and verticality of special faces and the convex and concave properties of the edges in order to attain good solutions and present a method of formulating such prior information as physical constraints. The shape-from-shading method is formulated as a minimization problem of a nonlinear cost function with the nonlinear constraints and its solution is searched by a global optimization algorithm. In the experiments with a synthetic image and three kinds of real images, shapes that are similar to those of the actual objects were recovered in all cases. As a result, the proposed method has proven to be effective in the shape recovery of simple-shape polyhedral objects.

Limitations on shape information provided by texture cues

This paper uses visual, empirical and formal methods (Li & Zaidi, Vision Research, 40 (2000) 217; Li & Zaidi, Vision Research, 41 (22) (2001a) 2927) to examine the roles of oriented texture components in conveying veridical percepts of concave and convex surfaces that are pitched towards or away from the observer. The results show that pairs of components, oriented symmetrically around the axis of maximum curvature, combine to provide the geodesic orientation modulations that are critical for veridical shape perception. The degree of pitch determines the orientations of the critical pair of components. Perspective is crucial to the veridical perception of concavities and convexities, regardless of the degree of pitch. The results of this paper reconfirm that veridical shape perception depends on extracting critical patterns of oriented energy, but also show that the class of textures capable of conveying veridical percepts of developable shapes in general views is even more restricted than that identified by Li and Zaidi (Journal of Optical Society of America A, 18 (2001b), 2430).

Distance perception mediated through nested contact relations among surfaces

In complex natural scenes, objects at different spatial locations can usually be related to each other through nested contact relations among adjoining surfaces. Our research asks how well human observers, under monocular static viewing conditions, are able to utilize this information in distance perception. We present computer-generated naturalistic scenes of a cube resting on a platform, which is in turn resting on the ground. Observers adjust the location of a marker on the ground to equal the perceived distance of the cube. We find that (1) perceived distance of the cube varies appropriately as the perceived location of contact between the platform and the ground varies; (2) variability increases systematically as the relating surfaces move apart; and (3) certain local edge alignments allow precise propagation of distance information. These results demonstrate considerable efficiency in the mediation of distance perception through nested contact relations among surfaces.

Induced effects of backgrounds and foregrounds in three-dimensional configurations: the role of T-junctions

In three-dimensional configurations, and two-dimensional pictures of such configurations, simultaneous contrast induction from proximate backgrounds affects perceived brightness, color, and internal contrast to a greater extent than induction from coplanar or occluding surrounds or from more distant backgrounds. In the projected image the presence of occluding flanks or retinally adjacent distant backgrounds is indicated by T-junctions. However, the presence of T-junctions inhibits induced contrast irrespective of the three-dimensional percept. The configurations in this paper refute the notions that perceived coplanarity or perceptual belonging necessarily enhance induced contrast.

Computation of surface orientation and structure of objects using grid coding

In this correspondence, algorithms are introduced to infer surface orientation and structure of visible object surfaces using grid coding. We adopt the active lighting technique to spatially ``encode'' the scene for analysis. The observed objects, which can have surfaces of arbitrary shape, are assumed to rest on a plane (base plane) in a scene which is ``encoded'' with light cast through a grid plane. Two orthogonal grid patterns are used, where each pattern is obtained with a set of equally spaced stripes marked on a glass pane. The scene is observed through a camera and the object surface orientation is determined using the projected patterns on the object surface. If the surfaces under consideration obey certain smoothness constraints, a dense orientation map can be obtained through proper interpolation. The surface structure can then be recovered given this dense orientation map. Both planar and curved surfaces can be handled in a uniform manner. The algorithms we propose yield reasonably accurate results and are relatively tolerant to noise, especially when compared to shape-from-shading techniques. In contrast to other grid coding techniques reported which match the grid junctions for depth reconstruction under the stereopsis principle, our techniques use the direction of the projected stripes to infer local surface orientation and do not require any correspondence relationship between either the grid lines or the grid junctions to be specified. The algorithm has the ability to register images and can therefore be embedded in a system which integrates knowledge from multiple views.

A necessary and sufficient condition for a picture to represent a polyhedral scene

As Shapira pointed out, a theorem by the author on line drawings of polyhedral scenes was not accurate. The present paper shows that the validity of the theorem is attained by a slight revision of the formulation.