Depth from Edge and Intensity Based Stereo

Abatraet

The past lew yeatJ have seen a growing interest in the application of three-dimensional image processing. With the in· creasing demand lor J..D spatial information lor tasks of paui\le ntwtgation{7,12j, automBtic survei11Bnce{9/, aerial cartography{I0,13}, and inspection in industrial automBtion, the importance of e.tf'ecti'l'e 1tereo analysis has been made quite dear. A particular challenge i1 to provide reliable and accurate depth data for input to object or terrain modelling systems (such as {5/). This paper deocribeo an algorithm lor such atereo senoing. It uses an edge-based line-by-line stereo correlation ocheme, and appean to be fast, robust, and parallel implementable. The proce11ing conoists of extracting edge descriptions for a otereo pair · of image·, linking these edges to their nearest neigh bon to obtain the edge connectivity structure, correlating the edge descriptions on the basis of local edge properties, then cooperatively removing th01e edge correopondences determined to be in error - thooe which violate the connectivity otructure of the two images. A further correlation procen, using a technique similar to that used lor the edges, is applied to the image inten1ity value· over intervals defined by the previous correla­ tion . The result of the proce11ing is a full image array disparity map of the .oc:ene viewed.

Mechani1m and Con1traiuh

Et19e-6ased stereo Ul!l!l operators to reduce an image to a depic­ tion of ih intensity boundaries, which are then correlated. Area-baaed 1tereo u.es area windowing mechanism· to measure local 1tati·tieal properties of the intensities, which can then be _conelated. The 1y1tem described here deals, initially, with the former, edges, becau.e of the:

1. re-duced combinatorics (there are fewer edges than pixel·),
2. greater anuracy (edges can bP. posit.ioned to sub-pixel preci­ sion, while area po1itioning precision is inversely propor­ tional to window 1ise, and considerably poorer), and
3. more realistic invariance assumptiqns (area-baaed analy1il presupposes that the photometnc properties of a tcene are invariant to viewing position, while edge-baaed analy·i· works with the assumption that it is the geometric proper­ ties that are invariant to viewing position).

Figure 1

DEPTH Jt'ROM EDGE AND INTENSITY DASED STEREO

H. Darlyn Baker and Thoma· 0. Binford

Artificial Intelligence Laboratory, Computer Science Department Stanford University, Stanford, California, 94305

Edges are found by a convolution operator. They are located at positions in the image where a change in 1igo of second dill'erenoe in inten·ity occun. A particular operator, the one described here being 1 by 7 pixels in aise, measures the directional lint dill'erenoe in intensity at each pixel'. Second differences are computed from th-, and change· in 1igo of these aecond differences are uted to interpolate sero cro11ing1 (i .e. peaks in first difference). Certain local propertiea other than poaition are measured and associated with each edp - contrast, image slope, and intennt11 to either aide · and link· are kept to nearest ·neighbours above, below, and to the 1ide1. It i1 th­ propertie· that define an edge and provide the ba1is for the correlation (see the diiCUUiOnl in [1,21).

The correlation is a search for edge correspondence between images. Fig. 2 show· the edges found in the two imagea of fig. 1 with the aecond dill'ereoce operator (note: all stereo pain in thi1 paper are drawn for cro11-eyed viewing). Although the operator workl in both horizontal and vertical directions, it only allows correlation on edge~ whose horisontal gradient liea above the noioe · one 1tandard deviation of the first difference in intensity . With no prior knowledge of the viewing aituation, one could have any edge in one image matcbins any edge in the other.

By con1training the geometry of the cameru during picture taking one can vastly limit the computation that i1 required in deter· mining corresponding edges in the two images. Consider fig. 3. Ir two balanced, equal focal length cameru are arranged with axes parallel, then they can be conceived of as sharing a 1ingle common image plane. Any point in the scene will project to two point. on that joint image plane (one through each of the two len1 centers), the connection o( which wiU produce a line parallel to the baseline between the cameras. Thu· corre1ponding edges in the two image· muot lie along the 11&1118 line in the joint image plane. This line is termed an epipol11r lit~e. If the bateline between the two camera· happens . to be parallel to an axis of the cameraa, then the correlation only need consider edge· lyins .along corresponding linea parallel to that axis in the two images. Fig. 3 indicate· thil camera geometry · a geometry which produce· redi/ied

1 The edae operator is .;mple, buically one dimen1ional, and il not.ewonhr oolr iD ~at it it: fut and fairly etrectin.

images. The algorithm deacribed auumea the atereo pair to be rectified, and if thia ia not the caoe then the appropriate tranaformation of one image relatin to the other must be made before further proceuing ia done. Note that a leu reatrictive solution would be to have the correl· tion informed or the camera J!eometries, and have it soln for the more general epipolar situation.

Fig. 4 ahowa a pair of corresponding linea from the atereo pair or ig. 1, while fig. 5 ploh the actual intensities or theae linea, - aa doh, auperimpooed on t.he edges determined by the edge operator. Since one needa to compare edges only from correaponding linea in the two imagea, the correlation can be applied to the edgea ahown in fie. 5. The proceaa or correlating could proceed at this point by aearc:b­ ing for the 'beat' aaaignment or edges along auch corresponding linea · one which optimises aome goodness measure. However, normal com­ binatoric oearch ia quite inadequate here. Typical linea han upward· o( n = 30 edgea each and the combinatoric apace, witla a naive upper bound of n!, growa rapidly with n (the CDC imagery above ian't typi­ r.al, but rather ia ayntbetic, and actually quite noiae-free - in contraat oee tbe imagea or fig. 10). Even with extensive heuriatic pruning, runt with a combinatoric aearcb approach often take oeconda per line ... and sometime· minutea (on a DEC KL-10). A auperior approach te the cor­ relation taak liea in uaing t.he Viterbi algorithm [6], a dynamic procr&lll· mine technique uaed exteoaively in apeech proceaaing, and flnt uaed in viaion reaearch ia aome recent work at Control Data Corporation[9].

tl~~ll~l What distinguishes the Yiterbi technique from normal aearch is the requirement that one be able to partition the original problem into two subproblems, each of which can be solved optimally and whoae results can be processed to yield a global optimum for the original prob­ lem ('optimal' with respect to an evaluation function on the choaen parameters). In a recursive way, each of the subproblems may be divided and the solution process repeated. Geometrically , the partition­ ing constraint here is one of monotomcity of edge order. A left-right ordering of edges in one image cannot correspond to a right-left order­ ing in the other; i.e. there can be DO positional reversals Of edge1 in the image plane. This constraint allows one to make n tentative u­ aignmenta of an edge on one line with the edges or the correaponding line in the other image, with each tentative assignment partitioning the correspondence problem into two subproblems. The two subproblema are the matching of edges lying to the left and right of the aelected edge on the one line with edges lying to the left and right re·spectively or ita tentative match on the other line. The optimality criterion aeleeta the aeries of auch assignments judged 'beat'. Tbia constraint excludea from analysis, for the time being, features auch 31 wire· or OtJerhonginr ·ur face· which lead to positional reversals in the image. Experience suggests that this reversal also causes the human vision aystem trouble -we can fuae one or the other , the nearer or the further, but not both at the same time.

The correlation could uae the edgea aa indicated in fig. 2 above, but in the interests of robuatnesa and efficiency a different approach ia taken here. A large amount of small acale detail in the imagea will exponentially iocreaae the coat or the correlation. Reducing the level o( detail and narrowing the extent of the required aearcb will reduce the computation time and enhance noise immunity. This is achieved through the use of a coa,.e-to-fine analysis in which a reduced resolu­ tion correlation is first applied to bring the two images into rough cor­ reapondence. The removal of the small scale detail brings quite a reduc­ tion in the number of edgea to be dealt with. Successive re6nementa in resolution bring successively finer detail into the analysis, and each such phaae can use the results or the previous lower resolution analyaia to narrow its aearcb. Such an approach has had previous aucceuful ap­ plication in visual processing (e.g. [8,11,12}), and baa relevant ties to the neurophyoiology of vision, where it ia felt a multiple spatial frequency analysis is part or the human system'· processing [14] (although the filtering used here is low pass, and not bandpass). It W31 our intent to uae the low resolution components of the images to determine local ap­ proximate disparitiu, and to use theae 31 guides for the full resolution correlation. To obtain the resolution reduction we use a linear smooth­ ing filter to succeuively halve image resolutions, cont inuing until the image signal content reaches an acceptable level (smoothing reduces noiae, so increases signal-to-noise ratio). Fig. 6 abows the edges in suc­ eellive resolution reductions or a sample line pair from the image· or llg. 10, again with doh marking the intenaitiea.

The aame buic ~erond diiJerence operator ia uaed throughout the resolution reduction analyses, but ita aise and noise-based threa­ boldo are altered to keep it matched to the characteriatica of the 'new' reduced resolution image. These lowest resolution edges are conelated in a manner to be deocribed below. The intervGla 1pecified hetween neareat-correlated edge pain and their mates in the other image define local dioparitiea to be uaed by the run resolution conelation proc:en.

The Correopondence Proceaa

The proceaa of determining edge correspondences ia batically the aame for both the reduced resolution aod the run resolution cor· relations; the only diiJerence ia in the aet of parametera uaed by the optimization function . Full resolution correlation uaea edge Gngle, ·itk intenaitiea, relGtiue diapGrity (aa meaaured by the reduced resolu­ tion phase), and interi!Gl compreuion implied by the correspondence (which uses edge position to determine the foreshortening of ocene sur­ faces 14)). In reduced resolution correlation, aide intenaitiea, contrG.t, and interuGI compre··ion are used. These parameter meaaurea all enter the computation aa probabiliatic weigbtinga: 0 ~ P ~ 1.

Each edge from a line in the reference image ia aasociated with a aet of possible matching edges from ita corresponding line in the other image (including the null match, which would imply that the edge ia either apurioua or ia obscured in the other image). Slightly complicating this, each ouch edge ia treated aa a doublet, being a left aide (the ter­ mination of the interval to its left) and a right aide (the atart of the in­ terval to ita right); left aides of edges can only match left aidea of edges, right aides only right aides (quite obviously). Thia lefi-right distinction ia eaaential in domaina where aurfacea may occlude one another, leaving a aurface to one aide of an edge hidden from one viewpoint while it ia viaible to the other. Each aide of an edge ia termed a he~lf-edge . For each pairing in the aet of pouible matches the a!Gtic probability of cor· respondence ia determined · tbia is the product of all of the mentioned probability meaaurea except intervGl comprea·ion (which is determined dynamically). The optimisation proceaa then uaea these probabilitiea, compoaing them with the dynamic interuGI comprea·ion probabilitiea in determining the 'beat' correapondence of half-edges along a line in one image with half-edgea along the correaponding line in the other image (detaila in 13)). This computation ia O(n 3 ) for n edges along either image line- it would be O(n 2 ) were it not for the use of intertJGl compre··ion probabilities.

The Connectivity Constraint

Fig. 7 shows the reaulta of the whole image line-by-line correla­ tion . Wherever there ia a noticeable horisontal jag across the image, there ia an error in the correlation. What is really being depicted here is change in diaparity along connected edges in each image. This ia achieved by plotting between the connected edges of an image, but rather than using just each edge's coordinate, use ita coordinate plus aasociated diaparity. Thus, when a connected stretch of edges in one image ia matched to varioua parta of the other image, the drawing will· jump horizontally back and forth in the other image's space, touch­ ing the various parta correlated with the connected stretch. At these horizontal jumps, the proceu ia suggesting that there is a large change in depth. This ia a auggeation of a /weak in depth continuit11.

Let ua emphasise, the dynamic programming algorithm above performa a local optimisation for the correlation of individual lines in the image · it uses no information outside of those linea. A very atrong global conatraint ia apparent and available here, that of edge connectivity. It may be presumed (by general position) that, in the absence of other information, a connected sequence of edges in one image should be seen aa a connected sequence of edges in the other, and that the structure in the ocene underlying these observations may be inferred to be a continuous aurface detail or a continuous surface contour. A cooperative procedure uses thia connectivity aasumption to remove edge correspondences which violate surface continuity. The evidence for these miacorrelationa ia found through the tracking of diaparitiea along connected edgea on adjacent linea (this is what fig. 7 depicts). The reaulta of the correlation after this proceaa baa functioned are abown in fig. 8 (with the aame type of depiction aa fig. 7). Fig. 9 shows a perapective view of these connected edge elements in depth. Notice that tbia figure drawn by the program ahowo that it baa truly captured something of the 3-D structure of the scene.

Figa. 11 through 14 show the various atagea of the edge-baaed stereo correlation proceu when applied to the image pair of fig. 10. This data (provided by the Night Vision Laboratory of the U.S. Army), an aerial view of natural terrain, ia considerably noisier and aignificantly more detailed than the synthetic urban imagery of fig. 1. It more clearly demonstrates the importance of the interline connectivity constraint and, u shown in fig. 6, the use of resolution reduction during the correlation.

The description so far baa been of an edge-baaed stereo cor­ relation scheme - one which uaea a Viterbi optimality condition and a cooperative continuity enforcement proceaa in establishing reliable cor· reapondences between the intensity boundaries, or edges, of a stereo pair of imagea. Yet there is much more information one could have about scenes such aa those depicted in figs. 1 and 10. The edge descriptions of figs. 9 and 14 juat highlight the structure of the scenea, providing rather sparse disparity meaaurea. One would like funer atereo detail from the correlation, and a subsequent correlation proceas, this time baaed on image intensity values, supplies tbia.

lntenaity Baaed Correlation

The aboYe edp-baaed correlation, in indicating correapondinc edge· iD the two imagea, proTide· atrong local 'vergence' information which greatly conatraina the matchiDg problem for any remaminc cor­ relation. One can take unpaired edge· from an interval along one line (epipolar line) and correlate them (again, via Viterbi) with unpaired edgea from the correaponding interval of tbe l&tlle line in the other image (the intervale are bounded by either correlated edge paira or the periphery of the im~). Thia correlation serve· to "fill iD the cape" of the primary edge-baaed correlation. A final correlation (the fourth!) talcea intenaity valuea from the intervals between paired edge· along correoponding linea and doea yet one more Viterbi correlation on them. We are still developinc the metric· used in this correlation - at the present we uoe I) intenaity variance and 2) deviation from linearity of the interpolated ourface. Fig. 15 indicatea the reaulta of tbia proceu­ ing on two aample lines (CDC line to left, NVL to right) . Arrowhead· ( .. and ~ ) show half-edge pairings (to the left oide and to the right aide, reopectively), and the plotted contoun show the dioparity valuea uoigned by the intensity correlation (depth can eaoily be determined from diaparity once the camera parameten are known).

Figo. 16 and 17 show stereo perspective views of the full cor­ relation reoulta for the two seta of imagery (disparitieo are those of the left camera image), and fig. 18 showo single views of the same surface· after convolution with a 4 X 4 smoother (for easier viewing, although with less surface clarity). These figures ohow that the correlation algo­ rithm produces a fuU image array disparity map of the viewed acenea. We have not yet measured ita accuracy .

Figure 17

Performance

The correlation algorithm de~eribed here providea thia thre&­ dimeoaiooal eenaing in a faat, robuat, and parallel implementable way.

[/nat] The analyaea u ahown in figa. 9 and 14 took roughly 25 and 35 eeconda apiece from image input to the final edge correlation reaulta u depicted. The remaining edge and intenaity correlation· of figa. 16 and 17 required a further 45 and 15 aeconda, reapectively (on a KL-10).

lrobuatl The uae of lin&-by-line correlation, each procened independently (accumulating a good deal of redundant evidence), and the uae of a coar~&-to-line atrategy (where the more reliable lower frequency component. are correlated lint) give a good baaia for obtaining the correct global con­ eenaua in the aubaequent cooperative procen.

!parallel implementoble) Since there ia no interline dependence during the varioua correlation a, and the au beequent coopera­ tive proceas has only pairwise interline interaction·, there ia a high potential for a parallel (n-procenora for n linea) realisation.

Ahead

There ia still, of course, conaiderable reaearch to be done within thia depth determination proceaa. We will be:

• o looking into improvement inuea in the preaent algorithm, auch aa having the correlator uae colour information,
• o teating it on further atereo imagery, both aerial and near range, uaing digital terrain modela for accuracy teata, where pouible, and
• o atudying the applicability of the disparity meaaurea derived by the algorithm to aurface and object modelling (u in ACRONYM (5]).

Further afield, we are intereated in developing auch a correlation -ICheme into a continuoua, multi-image correlator, capable of integrat­ ing analyaea over a aeriea of pusively senaed atereo views in building a highly accurate and detailed map of ~eene depth.

Acknowledgement.

Thia reeearch hal been supported by the Defenae Advanced Reaearch Projecta Agency on contract MDA 903-SD-C-0102. Special thanka to Sid Liebea and Peter Blieher for their comments on a draft of thla paper.

Reference·

• (1] Arnold, R.D. and T.O. Binford, 'Geometric Conatrainta in Stereo Viaion,' Proc. SPIE Meclint, San Diqo, California, July 1980.
• (2] Baker, H. Harlyn, 'Edge Baaed Stereo Correlation,' Proc. ARPA lm4ge Undmtandi"f Worb4D,, Univenity of Maryland, April 1980, 16S-175.
• J3J Baker, H. Harlyn, 'Depth from Edce and lnteoaity Baaed Stereo,' {/ortAcomi"f Ph.D. U.e.W).
• (4] Blakemore, Colin, 'A New Kind ol Stereoacopic Viaion,' Vilton RuearcA, Vol. 10, 1970, 1181-llgg.
• J5J Brook a, Rodney A., 'Symbolic Reuoning Among 3-D Modela and 2-D I maceo,' Arl·fit~ollntellirence Jo·mal, Vol. 16, 1981.
• J6J Forney, G. David Jr., 'The Viterbi Algori thm,' Proc. IEEE, Vol. 61, No. 3, March 1973.
• J7J Gennery, Donald B., 'Modelling the Environment of an E:rplorinc Vehicle by Means of Stereo Viaion,' Stanford AI Lob Memo AIM-3!9, June 1980.
• J8J Grimaon, W. E. L.,'Computing Shape Uaiog a Theory of Human Stereo Viaion,' Deportment of MotAemoliu, MIT (theaio), June 1980.

Jll] Henderoon, Robert L., Walter J. Miller, C. B. Groach, 'Automatic Stereo Recognition of Mao-Made Targeta,' Soc . Pholo-Optico/lrutrumentotion Engineer·, Vol. 186, Auguat 1978.

[10) Kelly, R., P. McConnell and S. Mildenberger, 'The Geotalt Photomapping Syotem,' Journal o/ PAotogrommctric Engineering and Remote Senoing, Vol. 43, November 1977, 1407-1417.

JUJ Marr, D. and T. Posiio, 'A Theory of Human Stereo Vioion,' MIT AI Memo No . 451, November 1877.

• JUJ Moravec, Hano P., 'Obatacle Avoidance and Navigation in the Real World by a Seeing Robot Rover,' Stanford AI Lob Memo AIM-'40, September 1880.
• JUJ Panton, Dale J., 'A Fluible Approach to Digital Stereo Mapping,' PAolognmmttr1t Engineering Gncl Remote Stn.sing, Vol. 44 , No. 12, December 1978, 1499-1512.
• [14) Wilaon, Hugh R., 'Quantitative Prediction of Line Spread Function Measurements: lmplicationa ror Channel Bandwidth·,' Vin"on Research, Vol. 18, 493-496.