WO1993003579A1

WO1993003579A1 - Three-dimensional vision system

Info

Publication number: WO1993003579A1
Application number: PCT/GB1991/001638
Authority: WO
Inventors: Andrew Blake
Original assignee: Isis Innovation Limited
Priority date: 1991-07-26
Filing date: 1991-09-24
Publication date: 1993-02-18
Also published as: GB9116151D0

Abstract

A three-dimensional vision system for optical inspection and robotics. One or two projectors establish structured light in an object field comprising two sets of parallel stripes on a ground plane, one set having a periodicity on the ground plane of 1/rA and making a first angle with epipolar lines of the system and the other set having a periodicity on the ground plane of 1/rB and making a second, much larger angle with the epipolar lines.

Description

THREE-DIMENSIONAL VISION SYSTEM

The invention relates to a three-dimensional vision system for optical inspection and robotics. In particular the invention concerns an active vision system where the object field to be viewed is illuminated in a particular manner and the perceived image is analysed having regard to the specific manner of illumination. One kind of active vision system uses structured light, the object field being illuminated in a predetermined pattern. This may be achieved by a mechanical scanning device or by a projector system which, by the use of optical masking, projects a static pattern of light on to the object field. Such a system is proposed by Hu and Stockman ("3D surface solution using structured light and constant propagation" - IEEE Trans. PAMI No 4 pages 390-402, 1989) who suggested the use of a grid of light from a single projector to illuminate the scene, providing easily-matched artificial "surface features" . However, the system was incapable of unambiguous operation - for each imaged grid point, several candidate 3D points were generated. Proposed solutions to the ambiguity problem have involved coding stripes by colour, thickness, or pattern. Colour coding cannot comfortably be combined with narrow band optical filtering for daylight operation. Thickness coding may be deceived when the thickness of a stripe is modified by surface effects. Space coding relies on projected codes remaining substantially undamaged by surface relief . The present invention provides a solution to the problem of resolving ambiguities in such a system. According to the invention there is provided a three-dimensional vision system which comprises:

(a) an object field having a ground plane;

(b) a projector system for illuminating the object field with structured light, the projector system having a focal length f', a projector plane and centre of projection a height H from the ground plane;

(c) a camera for viewing the object field, the camera having an optical centre; and (d) a base line of length t constituted by a straight line joining the centre of projection to the camera optical centre, epipolar lines in the projector plane being defined as lines co-planar with the base line, characterised in that the structured light comprises two sets of parallel stripes on the ground plane, one

1 set having a periodicity on the ground plane of /r. and making a first angle with the epipolar lines and the other set having a periodicity on the ground plane 1 of /r and making a second, much larger angle with the epipolar lines.

In a preferred embodiment of the invention the object field is restricted by a plane parallel to the ground plane at a height h, h being given by the equation

h = H

where e is the system measurement error referred to the projector plane.

Angling the stripes and restricting the working volume in the manner described ensures that ambiguities are avoided.

It can be arranged, as in the Hu and Stockman system, for example, that both stripe sets emanate from the same optical aperture. However, this requires corner detection in the analysis of the received image and it is found that edge detection can be more accurate. Accordingly, it is preferred to use separate projectors for the two sets of stripes, and the system can be regarded as trinocular, having two projectors and a camera. In order to establish a centre of projection and a projector plane for a system employing two projectors, it is arranged that lines common to projected planes of light from each projector intersect, thereby giving a virtual centre of projection and a virtual projector plane.

The invention will further be described with reference to the accompanying drawings, of which:-

Figure 1 is a diagram of a three-dimensional vision system in accordance with the invention with two projectors;

Figure 2 is a diagram illustrating the vertical centre of projection and the vertical projector plane for the two-projector system; Figure 3 is a schematic diagram of a single projector system;

Figure 4 is a diagram of the projector plane of the Figure 1 arrangement;

Figure 5 is a diagram illustrating the selection of the skew angle of the grid lines with respect to the epipolar lines of the system; and

Figure 6 is a diagram illustrating the selection of the working volume for the system.

Referring to Figure 1 the system comprises two projectors A and B with masks 3 and 4 which define respective sets of parallel lines. The sets are crossed. Light-planes 5 are shown emanating from projector A and a light plane 6 is shown emanating from projector B. The light is directed to an object field having a ground plane 7. A video camera 8 is provided and this has an image plane 9.

Figure 3 shows that when the two projectors are in a suitable mutual alignment there is then a single virtual centre of projection 12 - the point through which all planes in A and B projectors pass. A fine height adjustment ensures, as part of the stripe calibration process, that all planes pass through a common point. A virtual projection plane 13 is chosen parallel to the planes of both projectors so that stripes are parallel on the virtual plane. Then a fine adjustment for the camera ensures that epipolar lines are also parallel on this projection plane.

Figure 3 illustrates a single projector system to which the two-projector system is equivalent under the conditions of Figure 2. It will be seen that the object 10 being viewed has crossed lines projected on to it and the image of these as detected by the camera is computer analysed. The purpose of using two projectors rather than one is so that each can carry its own set of parallel stripes, and can be switched on or off independently. Thus the two sets of stripes are imaged separately in two frames, and only overlaid computationally in the image plane to form a grid. This means that grid points in the image, which are now virtual intersections of stripe-pairs, can be localised as finely as the accuracy that the edge- detector will allow. In practice this means that an order of magnitude of sub-pixel resolution is possible which is better than can be achieved by a corner detector. The disadvantage is that motion is no longer frozen if the two frames are captured sequentially. However, the two frames could be captured simultaneously using a standard 3-colour CCD camera, leaving the third colour channel free as an intensity reference, providing some degree of rejection of surface markings and discontinuities.

In the projector plane 13 there is a grid of lines constituted by intersecting parallel sets A and .B. The straight line joining the centre of projection 12 with the optical centre 15 of the camera is a base line shown at 16, having a length t. A target point T on the object 10 defines with the base line 16 a plane, the intersection of which with the projector plane 13 is an epipolar line 17. It is clear that a stripe intersection corresponding to the position of target T must lie in the projector plane on the epipolar line 17. Given a stripe-intersection at P in the image, it is required to identify which pair (a,b) of stripes in the projector plane generated it. The epipolar constraint (figure 3) greatly limits candidate solutions for (a,b) but there may still be some ambiguity. It is clear that reducing system error and increasing stripe spacing would reduce ambiguity. However, ambiguity can be eliminated if a "near-degenerate" arrangement is used, as in figure 4. By arranging for epipolar lines to be almost parallel to one set of stripes in the grid - say the "A" set - the number of candidate solutions for intersections of stripes with a given epipolar line is greatly reduced. If, further, the intersection can be guaranteed to lie within a certain window W in the projector plane then just one unique solution remains. This can be achieved by restricting the working volume over which the range-sensor operates. Provided working volume limits are compatible with measurement tolerance, ambiguity is avoided. If, for example, measurement error bounds are deliberately slackened, by a factor of 2 the 3D positions of about half of the grid-nodes become ambiguous. Hence performance is dependent on careful analysis of error and epipolar geometry.

In order to achieve optimal suppression of ambiguity, the "A" stripes must be rotated to a near- degenerate alignment. Let us denote by p A,,Pτ o the periodicity, on the projection plane, of stripes from projectors A and B respectively. The angle £ between the epipolar line through a particular grid crossing and the A stripe should be just large enough that the nodes immediately adjacent on the A stripe should clear the thickened epipolar line (figure 5) . This is achieved by choosing sin © > p

^pB Where e is the system error parameter whereby epipolar lines are eff ectively thickened . Thi s parameter can be measured experimentally . If an arrangement is used in which the baseline is parallel to the proj ector plane epipolar lines are mutually paral l el on the pro j e ctor plane , s o tha t the rotational alignment can be achieved simultaneously throughout the plane . Now the bound for delta can be

₁ eexxpprreesssseedd iinn tteerrmmss ooff tthhee density r_ (in mm ) of stripes on the ground-plane :

f where f is the projector's focal length and H is the height of its centre of projection above the ground- plane. If, for some reason, it were essential to use a non-parallel baseline then a matching non-parallel stripe set could be used in the projector to maintain simultaneous alignment.

Assuming near-degenerate alignment as specified above, how much must the working volume be restricted in order to guarantee a unique solution for the stripe intersection? The answer can be expressed as a design rule which represents a trade-off between the stripe densities r , r_ on the ground-plane, for projectors A, B respectively, measurement error e referred to the projector plane and the height h of the working volume above the ground plane. The design rule stated here applies to the case in which the projector-camera baseline is parallel to the ground plane, as in figure 6. In that case, for a given error e , the working volume is bounded above by a plane parallel to the ground plane, at a height

H M

where H is the height of

ground, f ' is its focal length and t is the length of the camera-projector baseline.

The implications of this rule for system design are most easily appreciated by looking at the approximation in the limit that h << H (the top of the working volume is well below the centre of the projector) and that e << p. (measurement error much smaller than stripe spacing) . Furthermore, we take projector plane error e to be the bounding value. In that case, the design rule approximates to

f cos 0 where Λ = 1/(r_Ar„), the area of a grid square on the baseplate and e_χ is area referred to the image plane.

The principal design trade-offs are then as follows. Overall system performance is limited by the angular measurement accuracy. Working-volume height h is traded off against the size of the smallest resolvable area, . Resolvable area and/or working volume constraints can be improved by enlarging the baseline t which also improves depth resolution, but at the expense of an increased incidence of occlusion of the projected pattern.

The design rule depends to some extent on the angle £ small, certainly in relation to the angle 90 -( which stripes B make with the epipolar lines.

Although the above description has been made with reference to thin stripes, these are an inefficient use of illuminant power. In practice, thick stripes are used, preferably a 1:1 mark-to-space ratio and positive and negative light/dark transitions are treated as "mathematical" stripes. They can be precisely localised by a directional edge-detector. Furthermore, positive and negative stripes can be distinguished by their orientation in the image-plane, hence effectively doubling the achievable stripe density as specified by the above design rule. Of course the orientation n of a stripe as measured in the image plane (n is the image-stripe normal, pointing towards the light side of the stripe) depends on the orientation of the object surface- Notwithstanding, the following result can be proved which provides a robust constraint which immediately distinguishes positive and negative stripes:

An image stripe with normal n is distinguished as positive or negative according to sign of the scalar product n.e, where e is the direction of an epipolar line that cuts the stripe.

Equivalently, no matter how the orientation of the object surface varies, an image stripe never rotates through an epipolar line.

The grid-point matching process can be quickened considerably by computing certain tables offline, that is, at calibration time.

Stripe-range table - ranges of the indices a, b indicating, at each image point P, which stripes could possibly be imaged at the point P, given the working volume constraints. In practice this cuts down enormously the number of grid-nodes a, b that need be tested online. In our system, the stripe-range table, together with the stripe-polarity test above cuts down the number of grid-nodes to be tested from 2500 to less than 10.

Node-epipolar table - a table containing the coefficients of the equation of the epipolar line in the image plane for each grid-node is constructed off-line. Then, in place of the test in the projector plane for intersection between the epipolar line and a grid-node, the dual test is carried out. The dual of the grid-node in the projector plane is its corresponding epipolar line in the image plane. The dual of the epipolar in the projector plane is the image point P. " The node-epipolar table requires only a modest amount of storage space (2500 nodes in our system) and makes the intersection test very rapid. The original test in the projector plane would require either on-line generation of epipolars, which is slow, or storage of epipolar lines for all possible image

7 positions (say 10 of them) which is impractical.

Testing against a "thick" epipolar line to allow for image measurement error is done by ensuring that node-epipolars are stored as suitably normalised vectors c and the test for intersection is then

- e_τ < c.P < e_τ.

The current system where e_χ is the image measurement error of the system achieves an accuracy

₃ of about 0.2mm over a working volume of 50mm . It runs at a rate of around 10 ms per node processed, on a SUN 4/260. Most of the computation time is spent in edge-detection, applying Gaussian masks, searching for maxima and interpolating between pixels. Current efforts to reduce this by using fixed-point framestore convolution hardware to implement a preliminary pass of low-precision edge-detection will leave computationally costly, subpixel edge-localisation to be done only at the grid points themselves.

Claims

1. A three-dimensional vision system which comprises: (a) an object field having a ground plane;

(c) a camera for viewing the object field, the camera having an optical centre; and

(d) a base line of length t constituted by a straight line joining the centre of projection to the camera optical centre, epipolar lines in the projector plane being defined as lines co-planar with the base line, characterised in that the structured light comprises two sets of parallel stripes on the ground plane, one

1 set having a periodicity on the ground plane of /r_A and making a first angle with the epipolar lines and the other set having a periodicity on the ground plane

1 of /r and making a second, much larger angle with the epipolar lines.

2. A three-dimensional vision system as claimed in

Claim 1 further characterised in that in a preferred embodiment of the invention the object field is restricted by a plane parallel to the ground plane at a height h, h being given by the equation

+ ^HrA^rB^tθP

f "2He_pr_A

where e is the system measurement error referred to

P the projector plane.

3. A three-dimensional vision system as claimed in Claim 1 or Claim 2 wherein there are provided separate projectors for the two sets of stripes, the system thus being trinocular having two projectors and a camer .

4. A three-dimensional vision system as claimed in Claim 3 wherein it is arranged that lines common to projected planes of light from each projector intersect, thereby giving a virtual centre of projection and a virtual projector plane.