Range finding method and apparatus

• US 4,695,156 A
• Filed: 07/03/1986
• Issued: 09/22/1987
• Est. Priority Date: 07/03/1986
• Status: Expired due to Fees

• Current Assignee: Westinghouse Electric Corporation (Paramount Global (f/k/a ViacomCBS Inc.))
• Original Assignee: Westinghouse Electric Corporation (Paramount Global (f/k/a ViacomCBS Inc.))
• Inventors: Taft, Jeffrey D.
• Primary Examiner(s): Buczinski, Stephen C.
• Application Number:
  US06/882,006
• Time in Patent Office: 446 Days
• Field of Search: 356/1, 356/2, 356/376, 356/383, 356/384, 358/107, 901/47
• US Class Current: 356/3.14
• CPC Class Codes: G01C 11/06 by comparison of two or more pictures of the same area
• CPC Class Codes: G01S 11/12 using electromagnetic waves other than radio waves

Abstract

A range finding apparatus includes a pair of spaced apart cameras which provide signals that are digitalized, stored in frame buffers, and provided to a computer that provides a range map of a target object viewed by the cameras. The computer optimizes a disparity function by minimizing a cost functional, thereby finding the range at different points on the surface of the target object based on variations in illumination, reflectivity, and texture.

Claims

1. A method for finding the range of a target object, comprising the steps of:

(a) viewing the target object from a first perspective, using a camera having a sensor with light-sensitive regions that are disposed in a row having ends, to provide a signal V_A (I_A) corresponding to the first perspective, where V_A is a voltage proportional to light intensity at a light-sensitive region of the row and I_A is an integer corresponding to the distance between the respective light-sensitive region and a predetermined end of the row;

(b) viewing the target object from a second perspective, using a camera having a sensor with light-sensitive regions that are disposed in a row having ends, to provide a signal V_B (I_B) corresponding to the second perspective, where V_B is a voltage proportional to light intensity at a light-sensitive region of the row and I_B is an integer corresponding to the distance between the respective light-sensitive region and a predetermined end of the row;

(c) finding a disparity function D(I_A) which maps V_A (I_A) onto V_B (I_B) for every I_A in an interval, the interval including a plurality of consecutive integers;

(d) using the disparity function D(I_A) to determine the range of the target object at a plurality of points on the target object; and

(e) providing electrical signals corresponding to the range to an output device.

2. The method of claim 1, wherein step (c) comprises:

(f) establishing a disparity matrix in a memory, the disparity matrix having rows corresponding to different values of I_B and columns corresponding to different values of I_A ;

(g) finding a peak in V_A (I_A) and a matching peak in V_B (I_B);

(h) marking the disparity matrix at a row and column corresponding to the I_B and I_A, respectively, of the peaks in step (g);

(i) finding an unmarked column in the disparity matrix where I_A differs by one from the column that was marked in the previous step;

(j) marking the disparity matrix, in the column found in step (i), at an I_B that lies on the disparity function D(I_A);

(k) repeating steps (i) and (j) a plurality of times.

3. The method of claim 2, wherein step (j) comprises finding a relative extremum of a cost functional.

4. The method of claim 2, wherein step (j) comprises minimizing a cost functional having a term that is a function of the difference between V_A (I_A) and V_B [I_A -D(I_A)].

5. The method of claim 2, wherein step (j) comprises minimizing a cost functional having a term that is a function of the difference between a derivative of V_A (I_A) and a derivative of V_B [I_A -D(I_A)].

6. The method of claim 2, wherein step (j) comprises minimizing a cost functional having a term that is a function of D(I_A).

7. The method of claim 2, wherein step (j) comprises minimizing a cost functional having a term that is a function of the difference between V_A (I_A) and V_B [I_A -D(I_A)], and term that is a function of the difference between a derivative of V_A (I_A) and a derivative of V_B [I_A -D(I_A)].

8. The method of claim 2, wherein step (j) comprises minimizing a cost functional having a term that is a function of the difference between V_A (I_A) and V_B [I_A -D(I_A)], a term that is a function of the difference between a derivative of V_A (I_A) and a derivative of V[I_A -D(I_A)], and a term that is a function of D(I_A).

9. The method of claim 8, wherein the cost functional is ##EQU5## where k₁, k₂, and k₃ are constants.

10. The method of claim 8, further comprising the step of marking the disparity matrix with constraints after step (h) and marking the disparity matrix with constraints after each repetition of step (i).

11. The method of claim 10, wherein the constraints include a line-of-sight constraint.

12. The method of claim 10, wherein the constraints include a convex surface constraint.

13. The method of claim 8, wherein step (a) is conducted using a first camera having a first sensor with light sensitive regions that are disposed in a plurality of first rows, wherein step (b) is conducted using a second camera having a second sensor with light sensitive regions that are disposed in a plurality of second rows, and further comprising the step of repeating steps (f) through (k) for a plurality of first and second rows.

14. The method of claim 2, wherein step (a) is conducted using a first camera having a first sensor with light sensitive regions that are disposed in a plurality of first rows, wherein step (b) is conducted using a second camera having a second sensor with light sensitive regions that are disposed in a plurality of second rows, and further comprising the step of repeating steps (f) through (k) for a plurality of first and second rows.

15. The method of claim 2, further comprising the step of marking the disparity matrix with constraints after step (h) and marking the disparity matrix with constraints after each repetition of step (i).

16. The method of claim 1, wherein step (a) is conducted using a first camera having a first sensor with light sensitive regions that are disposed in a first row, wherein step (b) is conducted using a second camera having a second sensor with light sensitive regions that are disposed in a second row, wherein the first and second cameras are identical and further include lens means for focusing light on the respective sensor, the sensors being disposed in a plane, and wherein step (d) comprises the step of solving, for a plurality of I_A, the equation ##EQU6## where Z_c is the range, b is half the center-to-center distance between the sensors, f is the focal length of the lens means, I_max is the number of light sensitive regions in a row, and L_x is the distance between the ends of a row.

17. The method of claim 16, wherein step (c) comprises finding the relative extremum of a cost functional having a term that is a function of the difference between V_A (I_A) and V_B [I_A -D(I_A)], and having a term that is a function of the difference between a derivative of V_A (I_A) and a derivative of V_B [I_A -D(I_A)].

18. The method of claim 1, wherein step (c) comprises finding the relative extremum of a cost functional having a term that is a function of the difference between V_A (I_A) and V_B [I_A -D(I_A)], and having a term that is a function of the difference between a derivative of V_A (I_A) and a derivative of V_B [I_A -D(I_A 0].

19. An apparatus for finding the range of a target object, comprising:

a first camera directed toward the target object to view the target object from a first perspective, the first camera having a first sensor with light-sensitive regions that are disposed in a first row having ends, the first camera providing a signal V_A (I_A), where V_A is a voltage proportional to light intensity at a light-sensitive region of the first row and I_A is an integer corresponding to the distance between the respective light-sensitive region and a predetermined end of the first row;

a second camera directed toward the target object to view the target object from a second perspective, the second camera having a second sensor with light-sensitive regions that are disposed in a second row having ends, the second camera providing a signal V_B (I_B), where V_B is a voltage proportional to light intensity at a light-sensitive region of the second row and I_B is an integer corresponding to the distance between the respective light-sensitive region and a predetermined end of the second row; and

means for finding a disparity function D(I_A) which maps V_A (I_A) onto V_B (I_B) for every I_A in an interval, the interval including a plurality of consecutive integers, and for using the disparity function D(I_A) to determine the range of the target object at a plurality of points on the target object.

20. The apparatus of claim 19, wherein said means for finding comprises a memory and means for establishing a disparity matrix in the memory, the disparity matrix having rows corresponding to different values of I_B and columns corresponding to different values of I_A.