Shape from Texture: An Aggregation Transform that Maps a Class of Textures into Surface Orientation

1. INTRODUCTION

One central task of image understanding is the recovery of three-dimensional scene information from the two-dimensional perspective transformation that is the Image. The recovery of the missing dimension can be achieved by the use of multiple views: either extensive in time, as in the determination of structure from motion [ 1 ], or extensive in space, as in deriving shape from binocular disparity [2, 3]. However, even a single Image often contains powerful cues as to object definition and shape; for example, many properties of object surfaces can be derived from an understanding and exploitation of in1age intensities [4~ In restricting the input to a single Image, the task necessarily becomes a heuristic one, given the vast array of scenes that can generate Identical Images. But such heuristic approaches, especially to the degree that they are model-free, can provide basic theories and algorithms applicable to many Image tasks.

This paper begins with a very brief outline of one such relatively model-free approach to deriving shape Information from a static monocular view. This method is based on the analysis of texture gradients and the application of principles of projective geometry. Just as an understanding of surface reflectivity enables shape to be derived from shading, so too can shape be derived from the textural properties of a scene.

This research was sponsored in part by an IBM Graduate Fellowship, and in part by the Defense Advanced Research Projects Agency (000), ARPA Order No. 3597, monitored by the Air Force Avionics Laboratory under contract F33615-78-t-1551.

The remainder of the paper Is devoted to the presentation of a new image aggregation transform, in the style of the Hough transform. It is more efficient and "natural" than existing Hough-like transforms, and (under certain conditions) can determine the location of local or global vanishing points or lines. A theorem is proven which sh;,ws the intimate relation of such points and lines to the local surface gradient. It further demonstrates Uoe natural correspondence that the transform establishes between perspectlvlty In the scene and the gradient space [5~

2. SHAPE-RELATED ASPECTS QE. TEXTURE

"Texture" is an ill-defined term. However, In some respects, it can be considered an attribute of surfaces, like reflectance or color: its appearance is usually dependent on illumination and view angle. It Is well known that blurred textures behave very much like aray scale tones. Similarly, texture gradients behave like Intensity gradients.

But there are also important, exploitable differences. Intensities are usually identified one-to-one with picture elements ("pixels"); they have no shape. Under many conditions, the observed intensities of a surface's pixels are fully independent of their distance from the observer; the inverse square law of optics is cancelled by the square law of solid angle. Most discouraging of all, It is difficult to discriminate intensity differences due to illumination variations, reflectance differences, or changes in orientation.

In contrast are textures, especially those made up of Identifiable texture elements ("texels"). Texel definition can be rather Insensitive to Illumination variation. Indeed, if individual texture elements have negligible extent normal to the surface they define (the texture Is "paint"), even shadows may not obliterete the fundamental textural pattern. Further, texture density is directly correlated with surface distance; the inverse squere law holds exactly. In addition, &iven the necessarily larger area needed to define a texel, tents comprise a multi-dimensional family, compared to the one dimension which describes pixels. They are therefore potentially more discriminating at occlusions, and less sensitive to noise. Thus, Intensity and texture are somewhat complementarya in fact, they often coexist within the same surface (e.a. the surface of a aolf ball).

1.1 Physical Assumptions

At least three interrelated physical phenomena pertain to the derivation of shape information from textural Information. These phenomena in turn provide the necessary assumptions needed in recoverin& three-dimensional surf ace descriptions. First, there is surface textual homogeneity, which Implies that like, nearby regions are really the same region. In the Intensity domein this forms the justificetion for region-growing or -splitting approaches. The analogue for a textured object is based on the assumptions of local texel similarity. Looked at another wey, region-growing and -splitting algorithms Implicitly recover near-planar surfaces based on the similarity of very small texels: pixels.

Secondly, there is the phenomenon of surface uniqueness and smoothness. It implies the assumptions directly applied in shape-from-shadina: the uniqueness of the local surface ("microplane") orientation with respect to an observer, and the continuity of the alobal surface. Smooth changes in surface orientation usually create textural (and intensity) aradients, but the opposite In not always true; heuristic rules are necessary to reverse the implication.

Lastly, there is the phenomenon of surface position. As position with respect to the observer varies, additional texture gradients arise due to perspective deformation. Such gradients have no direct counterpart in the Intensity domain. However, they can be analyzed by using the implied assumption of viewpoint uniqueness. It is with respect to this one viewer position that surfaces have direction or distance.

Each of these three phenomena can be studied in isolation by carefully selectin& images that minimize the effect of the other two. In the absence of curvature and perspective, texel similarity has been explored by, among others, [6], who segmented planar objects under orthographic projection. Large, simply-curved surfaces isolate the problem of determining global shape from local clues; processing would be analogous to the

Intensity-based work of [n Large, simply-textured planar surfaces (e.g. tilled checkerboards) single out the last aspect, perspectlvity.

Perspectlvity has received little attention. In fact, much research assumes orthographic projection and takes pains to compensate for, rather than utilize, perspective effects. As a consequence, model-free approaches have found it difficult to determine quantitative depth and orientation information: there is no fixed viewer position under orthographic projection. It is these Issues that the remainder of this paper addresses, by exploinfing the properties of a special, perspective-isolatina domain.

3. A NEW AGGREGATION TRANSFORM

Suppose the task of determining shape from texture is simplified to the following very simple subtask. Texels are restricted to be one-dimensional and line-likea they are organized into textures in a regular mesh- like fashion. This is a "structural" texture, somewhat like a grid, except that the line segments can have arbitrarily long gaps, and they do not have to have a fixed spatial frequency. The scene is limited to large planes set at various distances and orientations. The planes are "painted", in the scene, with such a network of parallel lines; In the image, these lines are usually perspectively distorted. Although an abstraction, these conditions fairly well imitate many man-made surfaces: building faces, walls, floors, and so on.

The subtask has several exploitable properties. Surface planarity Implies that any local surf ace orientation (relative to the observer) Is the global one as well. Therefore, the determination of local vanishing lines Is equivalent to finding global vanishing lines. The latter can be done once, in the large, with consequent Improvement In accuracy. Segmentation is eased by the uniformities of the texture component directions. Individual texels are easily identified by an edge detectora no local region growing, etc., Is necessary to define them.

The major problem is to aggregate the texels (in this case, edgels) Into surfaces, mindful of the vanishing points. Most traditional textural transforms are of limited use here; most were developed with the Implicit assumption that the image was the orthographic projection of a frontal two-dimensional scene. Using them, it would bfj difficult to distinguish intrinsic textural variations from perspective-induced ones.

The new aggregation transform is Initially designed, then, to group texels according to the two or more vanishing points they orient towards. (This is a very strong assumption. The occurrence of two or more vanishing points is a special case of the general problem of the vanishing line. Vanishing lines exist independently "'f texel orientation; they occur with

statistical textures, and even with no textures at all.)

Conceptually, it ought to be sufficient to infinitely extend each line segment, and detect points of mutual Intersection. Texels can then be classified Into Implied surfaces by their respective vanishing points. In effect, this would Implement the general image understanding heuristic that converging Image lines often arise from parallel lines defining a surface within the scene.

Practically, the problem is a bit more complex. Many times vanishing points are very distant, If not infinite. Further, any solution should be computationally Inexpensive, and finding all mutual Intersections Is not. Lastly, It would be beneficial If the agsreg1tion operttor grouped together like-oriented texels in an ensemble that can be easily defined 1nd detected. It will be seen that this, and more, can be efficiently att1ined.

3.1 The Hough Transform

The vector version of the rho-theta Hough transform is a likely starting point for such a transform (see Figs. 1 and 2). Under it, Image points are mapped into sine waves in the parameter space; edge vectors are mapped Into points [8l Collnear edge segments are represented (and recovered) by the accumulation of their transform values at unique points In the Hough space. It Is easy to see that parallel line segments are indicated by accumulation points sharing the same thefa value. That

Fia. 3. The new polar form of the aggregating transform of Fig. 1. Both sets of parallel line segments 1ra mapped Into accumulation points that lie on circles.

is, parallel lines transform into a line of accumul1tion points In the parameter space; the line Is theta · c. Any mutually converging line segments (possible parallel lines in perspective) transform Into accumulation points lying on a sine curve. That sine curve Is the transform of their vanishing point.

Unfortunately, sines In the Hough space are difficult to detect. It Is likely one would need to apply a similar Hough-like transform to do so: mapping e1ch potential sine point Into a curve In a second parameter space, and detecting accumulation points there. Still, this aggregation has the advantage of Implicitly representing and aggregating like-oriented edge segments by exactly one curve.

3.2 A First Modification

The following modification of the vectored rho-theta Hough preserves Its local grouping property, but represents aggregates in a form that is easier to detect. In addition, It Is computationally cheaper, conceptually and visually more forthright, and can be used to replace other Hough-like transforms used for vector groupln& (for example, the transform used In the gradient Intensity transform method ("GITM") of [9]).

This new appro~tch plot" the rho-theta transform space on polar coordinatea (see Fig. 3). This has many desirable effects. Points now map into circles which pass through the ortgm. Edge vectors still map into points, but with two interesting new properties. Consider the transformed edge vector (a point) as a vector with respect to the transform origin. Now its direction Is parallel to the direction of the edge vector itself. And, Its length is equal to the distance (from the Image origin) of the line determined by the edge Itself. These two properties make the transform easier to view and Imagine. As an elegant bonus, no trigonometry is required to calculate this new trensform. If the edge vector Is the vector E · (Ex, Ey), and if Its position In the image Is considered the vector P · (Px, Py), then the transformed point, represented as the vector T · (T x· T y>· Is defined as:

where ·.· Is the dot product and "II II" Is the Euclidean norm.

Further, the transform maps mutually converging line seaments Into accumulation points that lie on circles passing through the origin. The vanishing point is represented by that point on the circle farthest from the origin. In the case of parallel line segments (with Infinite vanishing point), the accumulation points lie on e line through the origin perpendicular to the parallels. Local grouping Is preserved; but now the aggregate representation (circles through the origin) is easier to detect, as shown below. Almost all of this discussion, Including the claims of computational efficiency, hiS been shown to apply anelogously to the other uses of the vectored rho-theta Hough. As an example, In the GITM method, what once mapped into secant curves In the transform spaces now maps Into straight lines.

Detectina the clrculer arcs can be done efficiently in the following menner. Consider a second transform that involutes the result of the first polar trensform (see Fig. 4). That Is, all transformed edge vectors, which are represented in the first polar space as (rho, theta) are mapped Into (Kirho, theta), for some K. This transform has even more desirable effects. Infinite vanishing points are now mapped into the origin (Kirho · 0). Lines through the first polar origin (along which lie the transforms of parellel lines) are unchanged. Most lmportently, all circles pesslng through the first polar origin (along which lie the trensforms of converging lines) are mapped into straight lines. Thus, In either case, a set of scenic parallel lines, perspectively deformed In the image or not, is mapped Into accumulation points that lie along a straight line. The distance of this straiaht line from the newest origin is Inversely proportional to the distance to the vanishing point of the line set. A normal to the straight line Is parallel to the vanishing point direction. Another bonus: If this transformation is composed with the first, the combined operation is even cheaper then that of the first alone. The transform vector f · (T x· T y> Is then defined in terms of the edge vector E · <Ex, E ), the edae position P · (PJ!, PY.)' and the scaling constanY K as: T · (K I (E · P)) E

where "·" is again the dot product.

Lines are easy to detect, especially when compared to the original suggestion of searching for sines.

4. M VANISHING LINE-GRADIENT SPACE RELATION

These lines, however, have yet another remarkable property. Under very natural conditions, they Intersect In the transform space at (p, q), the value of the surfece gradient vector. That is, the transform simultaneously achieves three goals. It aggregates edgels Into straight lines (represented by points In the transform space). It aggregates straight lines Into sets of (perspect ively distorted) parallel lines (represented by lines in the transform space). And it aggregates parallel line sets Into planes (represented by the Intersection of lines In the transform space at the unique point corresponding to the plane's orientation).

The following theorem formalizes the conditions under which the above claims are valid.

Theorem: Suppose an image contains the perspective projection of a planar surface defined by two or more coplanar sets of parallel line segments. Let the origin of the transform space correspond to the coordinates of the focal point in the image (that is, where the camera is "aimed"). Let R equal the focal distance. Then T · R E I (E · P) (as defined above) transforms edges so that the Intersection of lines of accumulation points in the transform space is at (p, q), the gradient vector of the surface.

Proof: By the duality of the transform, the transform of the vanishing line (a point) lies on the intersection of the transforms of the vanishing points (lines). It Is this intersection which occurs in the transform space. It Is now only necessary to show the correspondence, under the transform, of the vanishing lines and surface gradients.

The imaging process can be modeled as in Fig. 5. The center of projection corresponds to the origin of the (x, y, z) coordinate system. The customarily upside-down focal surface (the "film") has been rotated through the center of projection so that it is right-side-up; it Is at a focal distance of R. The projection of the focal point passes through the focal surface at (0, 0, R). On the "film" Is the Image of a mesh-like planar surface. Also depleted in the figure, for illustrative purposes only, Is the plane's vanishing line and two vanishing points. It Is important to note that such lines and points are usually only theoretic constructs. They rarely appear in the image itself.

Let the surface equation be given by px+qy+c · z, following Huffman. Its gradient vector is thus (~z/~x, ~z/C'iy) · (p, q). Points on the surface map onto the focal surface under central projection according to the relation (x, y, z) -> (Rxlz, Ry lz, R) (Rxl(px+qy+c), Ryl(px+qy+c), R). The equation of the vanishing line on the focal surface can be found by passing a line through two different vanishing points. However, a vanishing point is defined as the limit of the projection of an infinite line lying in the surface. Let (x, 0, R) and (0, y, R) be two such lines; the limits of their projections, as x and y respectively tend to Infinity, are (Rip, 0, R) and (0, Rlq, R).

Now, impose a coordinate system on the focal surface in the natural way: "film" points (x, y) are the points (x, y, R) In three-space. The vanishing line In the two-dimensional coordinate system then has the equation y · -(plq)x+Riq. Its normals (its "edge vectors") have everywhere a slope of (qlp); that Is, they are In the direction of the vector (p, q). Therefore, any point on the vanishing line Is transformed Into R E I (E · P) · R (p, q) I ((p, q) · (x, -(p/q)x+R/q)) · R (p, q) I (px-px+R) · (p, q). This last is the surface &radient.

Thus, the theorem is proved: vanishing lines map Into gradient vectors. Or, put another way, the transform creates a natural correspondence between the Hough transform and the gradient space.

5. EXAMPLES AND SUMMARY

The complete transform process is summarized and illustrated by the following figures, using a synthetic textured Image (Fig. 6: a simulated building face). :rhe focal point Is at the center of the image; the focal distance is equal to the width of the image. The surface was created with gradient (p, q)- (0, -1).

Edge vectors (Fig. 7) are first mapped into accumulation points in a polar rho-theta Hough space. Mutually converging lines are thereby mapped into accumulation points that lie on circular arcs through the origin (Fig. 8). Involuting the transform space maps these arcs into straight lines (Fig. 9). This result was actually derived directly from the edge image by means of the more efficient second form of the transform. The lines in the involuted polar space are seen to intersect at (p, q) ·

(0, -1), which Is both the transform of the surface's vanishing line, and the value of the surface's gradient.

Determining shape from texture has many facets1 the transform reported here Is only one small one. other approaches based on different classes of texels, toaether with an overall computational paradigm showing their common relations, will be presented In [10l

ACKNOWtED�E~NTS

The author gratefully acknowledges many stimulating discussions with Takeo Kanade.