Environmental Labelings in Low-Level Image Understanding

1 Introduction

Many image environments are immersed in a .force that strongly on cnts objects in a pref~rred way. It IS I_Jot difficult. to be convinced that grav1ty mflue!JC<'S t_he d~s1gn of image understanding algonthms, especially m h1gher level processing. However, we show in this paper that assunung the presence of gravJty ~an ai_d the l<;nyer le_vels of image processing as well. 1 h1s IS a b1t surpnsmg, s1nce many low-level routines do work--and ought to work--ju~t as well with images inverted. Nevertheless, certam heuristics regarding the _exploitation _of " horizontal", "vertical" and other grav1ty-based environmental labels can make 'low-level shape recovery more effi cient. f'hese heuristics generate additional members of a fam1ly of preference-based algorithms for. local. su~face orienta~ion that are linked together by theJr denvatwn and use m a common methodological paradigm, called shape from texture [Kender 80].

2 Gradient Space Relations

Environmental labels first appear in the description of the degrees of freedom of the imaging sensor. The terms "pan", "ti lt", and " roll " imply a gravity-dependent coordinate system, and are defined 111 environmental terms. Pan IS sensor rotation in the horizontal plane; ti lt is rot:'tlion in the vertical pla.ne passing through the central visual rav. Roll is defin ed as rotation in the image plane, and its effect is therefore dependent on tilt and pan; in the abscence of roll , the image of an environmentally vertical plane that passes through the central visual ray is a retinally vertical line.

*This resrarch was sponsored in part by the Defense Adv~Jnced HPsrarch Projects Agency under contract N00039-82-C-04 27.

A second class of env ironmental labels concerns surfaces . "Hori zontal" is simQiy a label for a unique preferr<'d surface orientation. In terms of the grad ient space [Shafer 83], it is a unique point: (ph·%)· Its coordin ates can lie obtained by a simple gravity sensor. If there is no sensor roll , this point sim[>lifies to (0,%)· Further, every "vertical" surface must hen map mto a gradient S))ace point of the form (p,-1/%) , smce the gradients of surfaces perpendicular to (Ph ,Qh J must satisfx the relation PPh+qqh = -1. Thus, the' one-dimensional family of vert1cal sul'races maps into the one-dimensional locus q = -1/9.1. As a S))ec1al rase, if there is neither sensor roll nor tdt thrn the line of verticals becomes the p axis.

More generally , similar basic relationships hold even if there is a roll component . The gradient space can be environmentally labeled by invoking the rotational coupling of the image space to the gradient space. All these relations hold independently of any considerations of imaging projection . They are true for both orthography and perspective; they are true, in fact, even w1th no image at all. Further the)' can be used in either direction: given sensor inr'ormat.ion, the gradient space can

be labeled, and vice versa.

It is interesting t.o note that the environmental surface labels of tiorizontal and vertical apply to envi ronmental lines as well , and even to lines on the retina. However, the size of the class of environmentallx horizontal lines is one dimension greater than that of environmentally vertical ones; this 1s the reverse of the case with surfaces.

3 Image Space Relations

Environmental surface labels, environmental line labels, and the sensor parameters are related in several ways. Consider first the case of pers))ective imaging where the sensor has no roll component. Scale the image plane in units of focal length; this will simplify the mathematics. Now image a scene consisting of vertical lines emerging from a horizontal plane: rather like a vast, stylized forest.

Unfortunately, any line in the image can be the image of an environmentally horizontal line. About the only exploitable horizontal property is the horizon itself. Th1s line, the limit of the proj ection of the horizontal plane, is retinally horizontal. It has the equation y = 1/%, as a plane with gradient (p,q} has vanishing line px+qy = 1.

More interesting is the behavior of the environmental verticals. Any environmentally vertical line must image into a retinal line that passes through the point (x ,y ) = (0 -q 1 J This follows as a special case of the analysiS of vanishing points. As the sensor's tilt increases so that its central visu:d ray approaches the vertical (i.e. as % approaches 0), this vamshing point of verticals approacnes the image origin. Simultaneously the horizon moves off in the pos1tive y direction. ,

If the forest scene is imaged by an orthographic sensor , very little environmental information remains in the image. Nothing at all remains of the horizon. All environmentally_ vertical lines are imaged as retinally vertical lines. Therefore, under orthography there are no environmental cues to sensor tilt.

All these image relations hold analogously under sensor roll. The close relation between tilt and roll and the horizon line is well knowni it is exploited in the artificial horizon instruments of auplane cockpits.

Note that unlike the gradient space relations these image relations are not automatically reversible. That is, a given image phenomenon does not necessarily imply any one sensor configuration. In general, environmental labeling must be done heuristically, as described below.

4 Using Gradient Space Relations

The relationships described above can be exploited in many ways. For example, given the sensor configuration, one can recover an environmentally labeled gradient space map. If the sensor configuration is uncE>rtain , the gradient space map (more s1mfly, the gradient of a properly labeled horizontal surface can be used to help calibrate tilt and roll. (Pan can not recovered; it is "gravity invariant". Pan does not even have any. common envir.onm~ntal names: the closest terms for 1t are compass d1rectwns.)

Additional uses of these relations include the following. If the sensor parameters are known then the determination that a given surface is horizontal uniquely specifies its gradient. The determination that it is vertical creates a linear constraint in the gradient space on which ' its gradient must lie. This constraint can be used with any other gradient space constraints: for example, those obtained by shape from shading, skewed symmetry, or shape from texture.

If the sensor parameters are unknown, then a determination that two non-parallel surfaces are vertical yields tilt and roll: their gradients generate the line of verticals in the gradient space. The determination of a single surface bemg vertical constrains tilt and roll to one degree of freedom; horizontal surfaces must be perpendicular to it.

4.1 A Hough-like Algorithm

Suppose we pose the more difficult problem in which tnere is neither a labeling nor sensor information. Nevertheless, both can still be (heuristically) recovered. Consider the additional assumption that aU (or most) surfaces are either horizontal or vertical--an assumption often supportable in man-made environments. Then the gradiC'nt space r E>presentation can be analyzed for the presence of the characteristic point-of-horizontal/line-of­ verticals configuration .

This can be achieved using a type of Hough accumulator approach. Since a given surface is likely to be either horizontal or vertical, it votes once for itself since it may itself be horizontal. However, since it may also be vertical, it votes once for all surfaces perpendicular to it: in this case, at least one of these surfaces must be the horizontaL Graphically, this is displayed in Figure ~· A vote for the self is sh<?wn by .a circle about tile pomt; ~ vote for all perpendiculars IS indicated by a dashed !me. In the example, only one surface has received four votes; it is assumed to be horizontal.

4.2 A Critique of the Algorithm

This method is not without its problems. Most critically, any such weighting scheme is neavily dependent on the given gradient space map, which in turn is affected by the environment and by the sensor position.

But the method does have some justifications. In particular like most Hough transforms it can be made heuristicaily more efficient, and it is likely to be robust with respect to noise--which in this case are surfaces which are neither horizontal or vertical. Further, it works with surfaces that are curved verticals: building sup_port columns, say, or drapery. In these cases, the gradient ~ace map of the vertical surfaces is diffused along a line. Perhaps most interesting is the result that the horizontal can be found even if there is no direct evidence for it in the image. This occurs when many environmentally vertical surfaces all vote for their perpendiculars; the one perpendicular they have in common must be horizontal.

5 Using Image Space Relations

The relations concerning ima~ configurations can also be exploited in many ways. The simplest case is when all sensor information is known. One immediate result is that locations of both the horizon and the vanishing point of verticals are then also known, whether or not they actually appear in the image. (If either is suggested oy an image configuration, then its position can further calibrate sensor tilt and roll.}

Again, the more interesting algorithms occur when the sensor mformation is unknown , uncertain, or known only partially. Under perspective, if the focal point of the retina and the focal length of the sensor are known, then sensor tilt and roll can be found immediately from a line that has been correctly labeled as the horizon. The same is true if a pair of non-colinear lines are environmentally labeled as vertical: the intersection of their extensions give the vanishing point of verticals, and hence tilt and roll. (No image information provides pan.) If there is onlv one such vertical, then the tilt and roll are constrained to one degree of freedom. Since the vanishing point of verticals can occur anywhere on this vertical hne 1 this constraint corresponds to the "vanishing gradient' of the line as definea in [Shafer 83].

Still under perspective, if focal point, focal length, and roll are known, then only one environmentally vertical line suffices to obtain tilt. In this case, the line that would be the image of a vertical plane through the focal point can be hallucinated; its intersection with the given vertical gives the vanishing point of verticals, which gives tilt.

Under orthography, only roll is recoverable since the images of environmentally vertical lines no longer converge. However, roll can now be determined from a single Image line that has been properly labeled as an environmental vertical.

Two questions remain: how is roll (and tilt) obtained if it is unknown and how are lines environmentally labeled? Given that people can usually make sense of environmentally detached /hotographs, it must be true that heuristics can be use to help quantify the missing parameters.

One can assume that all retinally near-vertical linest for suitable definitions of "near" are the images o environmentally vertical ones. Under perspective, a Hough-like scheme can then be used to help refine this heurtstic labeling. Extend (and weight) all such Jines, and take their most common intersection as the vertical vanishing point; tilt and roll come free. Under orthography, the method degenerates to one-dimensional histogramming of image slope. (The analogous methods for environmentally horizontal lines appear to be much weaker, given their unconstrained behaviOr in the image.)

A special case of such heuristic labeling of vertical lines is used in the Phoenix system [Herman 82]. It works on aerial views of buildings in Washington O.C., taken with a sensor aligned directlv downward. The vanishing point for verticals is therefore the image origin. The method then becomes: any line whose extenston passes through the image origin is heuristically labeled a building's vertical.

6 Using Linear Perpendicularities

We have described several algorithms that exploit the perpendicularities that are created upon horizontal surfaces by vertical surfaces or lines. We now show several ways in which to exploit the perpendicularities created uron horizontal lines by vertical lines. We assume al sensor parameters are known, and to simply the presentation, we further assume that there is no sensor roll.

These algorithms are based on the observation that an environmentally horizontal line meets an environmentally vertical line at a right angle, creating a environmentally vertical surface. If sensor parameters are known, the vertical line is redundant. It can be hallucinated, since it must pass through the vanishing point of verticals (an ideal point, in the case of orthography). Thus, all that is needed to define a vertical surface is the image of an environmentally horizontal line.

The gradient of this hallucinated surface can be quantified. The knowledge that the plane is vertical alreadv restricts its gradient to the line of vertical surfaces in the gradient space. But the fact that the environmental angle is a right angle generates a second one-dimensional constraint m the gradient space (often, the "Kanade hyperbola".) These two constraints can be intersected, usually specifying the gradient directly. Thus, a line labeled as environmentally horizontal often generates a completely specified vertical surface:

In the most general case, the second constraint is complex: it is a fourth degree curve in gradient space parameters p and q. However, under orthography, or under perspective if the vertex of the angle lies on the focal point (local orthography), it simplifie~ .to ~he Kanade hyperbola m p and q. A further simphftcatwn occurs when one side of the angle is environmentally vertical: the angle can be drawn with the vertex at the image origin and the environmentally vertical side aligned with the y­ axis. The resultant constraint is extremely simple: it is p ==- cotn(q+l/q), with p now a function of q.

This function is uniquely intercepted by the line of vertical surfaces, q = -1/CJ!,, for any value of%· Thus, under orthographic conditions the gradient of the generated vertical surface is uniquely defined . (Note that If the vertical line is an object edge and the horizontal line is the edge's shadow, then this unique gradient is a constraint on the direction of the illuminant.)

This function has several other interesting properties. The first is that the minimum value of p always occurs at q = -1, independent of n. Since in orthographic photographs there is no indication of the sensor tilt %t the observer is free to select a tilt at will. The choice o % = -1 guarantees that left-right slant is minimized (i.e. the surface "regresses to the frontal plane"). This value of q is equivalent to looking down at the horizontal plane at 45°; this angle is commonly used in architectural drawing.

A second property is that under pure orthography all right angles witfi a vertical side behave identically, in one respect. Distances on the horizontal plane on which they stand can be read off from the image, independently of the angle n that their images form. On any image line y = c, the depth on the vertical leg is c/CJb and the depth on the horizontal leg is CCJ)l, indepenaent _of n. . In particular, any rectangular prtsm of whatever size, restmg on a honzontal surface with known tilt, can be easily labeled for relative depth in the image itself. Starting at any vertex depth changes are propagated outwards: proportional to 1/CJil on vertical members, and to % on hortzontal.

7 Ambiguity in Labeling

In the previous section, we gave algorithms for exploiting the perpendicularttJ' that arises between horizontal and vertical lines. We demonstrate here that that configuration's power comes not from the perpendicularity per se, nor even from the fact that the su rface that is formed is vertical but from the line's individual environmental labels. in this discussion, we make the simplest of assumptions: orthographic imaging with known sensor parameters and no roll; oasically, this is a counter-example.

Consider the im!J-gc of an envir~nmen tally ver.tical pl:1ne in w~ich . there .·s embedded a r.1ght angle, ne 1 ~her side of winch IS environmentally hon zonta.l or ve~tJcal. T he constraint in the gradient space that the Image generates from the assumption that it is environ~nentally ri ght is again the Kanade hyperbola: see Figure 2. How~ver because of the orientation of the image angle, this hyperbola is no longer a function of either p or q FurtJi cr some values of q have no corresponding p· tl~ at. is, some values of se~sor til t % are incqmpatible \Yith t he mterpretatwn o( the Image angle as a ng~t angle m a vert ical plane. (Th1s was. not so m the previOus case. of environmrntally labeled s1des. ) .Worse, n~arly every Im.e of vert i('a.) surfaces that does mtersect 1t mtersects 1t twice. That is, for nearly every sen~or til t for .which the image has an in terpretatiOn as a vertical plane, 1t has two possible gradients.

It turns out that the two interpretations are somewhat difficul t to visualize; see Figure 3.

The case where the line of verticals is tangent to the hyperbola probably corr~sponds to the confl,guration whPre both lrgs of the n ght angle are at 45 to the environ menta I hor izon tal.

8 Discussion

Many of the relationships discussed in this paper have depended on heuristic assumptions of a. similar form. The bas1c reasoning was as follows.

Certain preferred . environmental obj cc ~s create specific image config~ratiol_l s; for example, the Images. of environmentally vert ical li1_1 es converge .to a va.mshmg point. However , other environmental obJ ects could also create the same conftguratwn; for example, environmentally horizon.ta.l. or ob.Iique lines could . a!so conver<Te on the va.mshtng pomt. The heunsttcs throughout assumed that the image configurations could be uniquely inverted as to cause: here, convergence would be taken to imply environmentally v ~rti ca.l. More simplyd the presence of an image feature sumlar .to a. preferre obj ect's image features was taken as evtdence for the preferred obj ect. This " nea~ implies preferred" meta­ heuristic has proven useful m several other contexts, specifically shape from texture and skewed symmetry .

What sorts of enviro1_1rnental <;>bj e~t~ are prefem;d? One basis for preference ts the sunplzczty wtth .which image signatures can be inverted. For example, m the gradient space both horizontal and vertical surfaces are easy to. manipulate because their classes a.r~ small and wel1-d r fmed; obltque surfaces are not. Hon zo1_1tal and vert ical surfaces are therefore preferred. Thts meta­ heuristic that "preferred implies simple" has also proven useful in other contexts.

Bu t perhaps the most ev idence of the ut il,ity of the meta-heuristics ts in the suggestio!! that fo'!'ca.tJOn .seryes purposes other than an increase m resolut~on. Vtewmg perj)endicularities .off-axis u~1d er perspective leads to Clifficul t mathema.ttcs; fovca~mg them makes the .math very simple. Thus, fov~atwn helps to c r~ate s1m_ple signatures and helps defme a preferre.d obj ect . The implica.t ion f~r im.age underst a.nCimg mtght be t~at all near-perpendtcul anttes should be fo'(eated; they mtght. be the tmages of an easily determmable local vertical surfaces.

Acknowledgements

I thank Kerny Calaway for her graphic skills.