Computing Convergence Angle From Random Dot Stereograms

1. Introduction.

Marr and Poggio's (1979) theory of binocular stereopsis is one of the most visible examples of the success of the so-called computational approach to (visual) perception (Marr, 1982). It is also one of the most widely known modern theories of stereos­ copic vision. Its cornerstone is a mathematical analysis of distri­ bution of projected features (oriented edge segments) along a line. This results in a (rather simple, but effective) feature matching schema which makes use of another geometrical con­ venience: the epipolar constraint. The epipolar constraint expli­ citly identifies conjugated lines in the two images: features lying on such a line in one image must have their matching counter­ parts on the appropriate conjugated line in the other image (e.g. Duda and Hart, 1973). The theory (like all projection field theories) reduces the problem of binocular vision to solving the correspondence problem. In this paper it will be taken as an example of an edge-based, epipolar-line oriented approach to stereoscopic matching.

The criticism of the theory (e.g. Julesz and Schumer, 1981; Baker and Blicher, 1982; Mayhew and Frisby, 1981) concentrated mainly on some aspects of the epipolar matching strategy or on the role of eye movements. One of the major but rarely dis­ cussed problems with any epipolar-based matching scheme is the requirement that the orientation of the epipolar lines on the image surface be known with high accuracy before matching (i.e. the images must be rectified). While this requirement does not pose a problem when the convergence angle of the two eyes is small (the epipolars are nearly horizontal, in this case), the prob­ lem becomes urgent when viewing nearby objects, and must definitely be taken seriously when viewing objects in the near space, e.g. reading a book, or trying to get a thread through the eye of a needle. As the fixation point comes nearer to the observer, the orientation as well as the position of the epipolar lines on the image surface change rapidly (Prazdny, 1982). A common approach (at least in computer vision or automatic photo interpretation) to solve this problem of camera calibration relies on uniqueness of certain monocular features. The correspon­ dence problem is usually solvable for a small. set of such monocu­ larly unique and distinguishable image elements which in tum makes camera calibration (and thus image rectification) possible

(e.g. Moravec, 1980; Gennery, 1979; Longuet-Higgins, 1981).

Random dot stereograms (RDS) do not, in general, contain such unique features so that it is not possible to perform camera

calibration using the above mentioned methods. A related issue are two distinct points, in general. The degenerate case of non­ intersection is detectable by the high value of the sum of squares function returned by the algorithm.

The actual minimization of the sum of squares was done using the variable metric descent to a minimum as suggested by Nash (1979, pp.159-160). This method was found to be very fast, reliable, and easy to code.

The algorithm proceeds as follows:

• [1]. Chose (at random) a (non-meridian) point on the left image (p1) and establish some fixed neighbourhood N around p 1 ·
• [2]. Choose a point in the right image (p,) lying within N and compute the angle a as outlined above.
• (3]. Repeat [2] for all right image points p, within N. Save the results (i .e. the angles at) in an array At .
• (4]. Chose another (non-meridian) left image point . Perform steps [1]-(3] and save the results in an array A 1 ·
• (5]. Compute the set intersection of At with A1 and store the results in an array I .
• [6]. Copy I into At and repeat steps (4]-[5] until the intersection set I contains only one element.

The reason for not considering meridian points in step [1] is that such points do not have vertical disparities (which carry informa­ tion about a, see Mayhew (1982) for a discussion of the impor­ tance of vertical disparities). The neighbourhood radius in [1] is determined by the maximum allowable horizontal disparity. In step [3], each computed value is actually represented by an uncer­ tainty interval (a fixed proportion of the computed value a) and the intersection operation is performed on these intervals because it is unlikely that the obtained values are ever noise free.

Figure 3 shows a (synthetic, wide-angle) stereo image (of a transparent ellipsoid) compatible with the model. The image plane was quantized into a 1000x1000 array. This quantization and numerical errors (double precision arithmetic was not used) are the principal sources of noise. The algorithm has been tested on a series of such synthetic images with good results. The values of a found were within about :!:: 2 degrees of the actual value. The algorithm only rarely needed to consider more than about 5 image neighbourhoods (this was the case only when some points in either image did not have matching points in the other image).

3. Discussion and Conclusion.

In this paper we investigated the feasibility of computing the convergence angle for a simple stereo camera model and random dot stereograms without solving the correspondence problem (in fact, in order to be able to solve the correspondence problem). The extension to a less restricted case in which both cameras are free to move is, conceptually at least, straightforward. The com­ putations will become more involved, however, because 2 points (and the corresponding matches) are needed to obtain the conver­ gence angle. One must fear that the combinatorial explosion asso­ ciated with solutions requiring 4 or more points (with associated matches) wiii make them computationally prohibitive. The set intersection method used by the algorithm outlined here is much faster and less complicated than the histogram updating suggested in (Prazdny, 1982). This is because it requires only a handfull of image neighbourhoods (histogram updating requires a large set of values at for a reliable identification of the peak).

As mentioned in the antecendent paper (Prazdny, 1982), it is not clear how to extend a method based on the existence of discrete image locations to the general case of smooth (real world) images. This "pointilistic" way of treating images is prob­ ably the most serious drawback of the current method.

REF'ERENCES.

Baker H. Blicher P. 1982

Review of Grimson's "Fr om Images to Surfaces"

Sigart Newsletter #BZ (October), 12-14

Duda R.O. Hart P.E 1973 Pattern Classification and Scene Analysis

New York: Wiley

Faux I. D. Pratt M.J. 1979 Computation al geometry f or design a:nd manuf acture

Chichester: Ellis Horwood Ltd.

Gennery D.B. 1979 Stereo Camer a Clibration .Proc.DARPA J. U. Workshop 101-107

Grimson W.E.L. 1981 Prom Images to Surfaces Cambridge : MIT Pr ess

Julesz B. 197·1

Foundations of Cyclopean Perception Chicago: The University of Chicago Pr ess

Julesz B. Schumer R.A. 1981 Early Visual Perception An.Rev.Psy chol . 32, 575-62?

Kauffman L. 1974 Sight and Mind New York: Oxford University Pr ess

Longuet-Higgins H.C. 1981

A comput er algorit hm for recons tructing a scene

from two pr ojections

Nature 293, 133-135

Marr D. Wsion San Francisco: Fr eeman

Marr D. Poggio T. 1979 A computational theory of human s tereo vision .Proc. R. Soc . London b-204, 301-328

Mayhew J.E.W. 1982

The interpretation of s tereo-disparity information (submitted to "Perception")

Mayhew J.E.W. Frisby J .P. 1981 Psychophysical and computational studies towards a theory of human stereopsis Artifi cial Inteligen ce 17, 349-385

Moravec H.P. 1980

OJstacle avoidance and navigation in the real world by a seeing robot rover

PhD. Thesis, Stanford University Rept. AIM-304a

Nash J .C. 1979

Compact numerical m ethods f or computers

New York: Wiley

Prazdny K. 1982 The role of eye position information in algorithms for ster eoscopic depth

Proceedings AAAI, 1-4

Figure!.

Geometry of the stereo camera model used in the paper. Left image plane is fixed, and right camera is allowed to rotate (on the plane with normal zL = zR) about a pivot point PPR (not necessarily) distinct from the centre of projection. FP is the fixation point deter­ mined as the intersection of the two principal rays (ih . 1JR). OL and OR are the centres of the left and the right coordinate systems. respectively. The mutual orienta­ tion of the left and right image planes is determined by the angle ex.

Consider a right image point (xR,ZR) with 3D coordi­ nates R=(xR.fR,zR) .. As the (right) camera rotates about the pivot point PPR. the line determined by r going through OR generates a (ruled) surface. The equation of this surface is:

where z=zL =zR is the "vertical" (unit) vector common to both coordinate systems. The intersection of this surface RS(cx,p) with a line L(X) through Oz (determined by the visual direction corresponding to a left image point) can be computed by minimizing the sum of square function

IRS(cx.p )-L(X)jZ.

~ure3.

A (s)llltetic) wide-angle stereo image pair of a tran­ sparent elipsoid generated using the model in Figure 1 (d=210mm, c=?Omm, J 1=Jr=60mm, a:=20 degrees) . 'I!he distance of the centre of the ellipsoid is 450mm measured from Oz . Each image contains approximately 4:00 points

---.

I