Method and apparatus for predicting the direction of movement in machine vision

• US 5,109,425 A
• Filed: 09/30/1988
• Issued: 04/28/1992
• Est. Priority Date: 09/30/1988
• Status: Expired due to Fees

• Current Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Original Assignee: United States Administrator of National Aeronautics and Space Administration
• Inventors: Lawton, Teri B.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/251,500
• Time in Patent Office: 1,306 Days
• Field of Search: 382/22, 382/1, 382/48, 382/43, 382/41, 358/105, 358/103, 358/142, 358/125, 901/1, 901/8, 901/46, 364/825, 364/724.1, 364/424.01, 364/424.02, 364/443, 364/444, 364/513
• US Class Current: 382/107
• CPC Class Codes: G05D 1/0253 extracting relative motion information from a plurality of images taken successively, e.g. visual odometry, optical flow determining position or orientation from images G06T7/70
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 7/262 using transform domain methods, e.g. Fourier domain methods
• CPC Class Codes: G06T 7/579 from motion

Abstract

A computer-simulated cortical network computes the visibility of shifts in the direction of movement and computes: 1) the magnitude of the position difference between the test and background patterns, 2) localized contrast differences at different spatial scales analyzed by computing temporal gradients of the difference and sum of the outputs of paired even- and odd-symmetric bandpass filters convolved with the input pattern and 3) using global processes that pool the output from paired even- and odd-symmetric simple and complex cells across the spatial extent of the background frame of reference to determine the direction a test pattern moved relative to a textured background. The direction of movement of an object in the field of view of a robotic vision system is detected in accordance with non-linear Gabor function algorithms. The movement of objects relative to their background is used to infer the 3-dimensional structure and motion of object surfaces.

Claims

1. A machine vision system for determining movement in a 2-dimensional field of view comprising:

a) video camera means for viewing the field of view and producing 2-dimensional binary representations of the pattern thereof at consecutive times t₁ and t₂ ;

b) image enhancement means for receiving said 2-dimensional binary representations of the field of view and for producing enhanced 2-dimensional binary representations thereof;

c) computational means for producing smoothed versions of said enhanced 2-dimensional binary representations, said computational means including means for filtering binary data comprising said enhanced 2-dimensional binary representations to provided the spatial gradients of components thereof comprising a background frame of reference and components identified with objects moving against said background frame of reference;

d) means for producing the temporal gradients of said enhanced 2-dimensional binary representations; and

,

e) sensing means for comparing said spatial and temporal gradients at said consecutive times to one another to determine any motion parallax existing in the field of view, whereby movement of objects in the field of view is determined.

2. The machine vision system of claim 1 wherein:

the outputs from paired Gabor filters summed across said background frame of reference are used by said sensing means to determine the direction of movement.

3. The machine vision system of claim 1 and additionally including:

a) means for encoding the image intensity of said pattern of the field of view by separable spatial and temporal filters consisting of paired even- and odd-symmetric simple cells in quadrature phase;

b) for each combination of said paired even- and odd-symmetric filters at each spatial scale being analyzed, means for passing the input signal through said spatial and temporal filters to produce four separable responses wherein the output from each said spatial filter is processed during two different time intervals by a low-pass temporal filter and a bandpass temporal filter; and

,

c) means for taking the sums and differences of the outputs from said paired filters to produce spatiotemporally-oriented nonlinear responses that are selective for the direction of any motion.

4. The machine vision system of claim 3 wherein:

said paired even- and odd-symmetric simple cells in quadrature phase are tuned to a 90°

spatial-phase difference.

5. The machine vision system of claim 3 wherein said separable spatial and temporal filters comprise:

a) an even-symmetric Gabor function, F_ES, described as,

space="preserve" listing-type="equation">F.sub.ES (f,x,σ

.sup.2)=cos (2π

fx)e.sup.-(x-x.sbsp.o.sup.).spsp.2.sup./2σ

.spsp.2 ;

and,

b) an odd-symmetric Gabor function, F_OS, described as,

space="preserve" listing-type="equation">F.sub.OS (f,x,σ

.sup.2)=sin (2π

fx)e.sup.-( x-x.sbsp.o.sup.).spsp.2.sup./2σ

.spsp.2

, where f corresponds to the spatial-frequency of said pattern, x corresponds to the horizontal spatial position being examined, x_o corresponds to said video camera mean'"'"'s fixation point, and σ

² corresponds to the variability within said pattern'"'"'s spatial period in locating the position of the most salient contrast difference, x_o.

6. The machine vision system of claim 3 and additionally including:

means for discriminating the direction an object in said pattern moves relative to said background frame of reference at two different times whenever an output from said means for taking the sums and differences of outputs from said paired filters pooled across said background frame of reference exceeds a pre-established threshold.

7. The machine vision system of claim 3 wherein:

a) said low-pass temporal filter F_ES is described by, ##EQU5## b) and said bandpass temporal filter F_OS is described by, ##EQU6## , where C_t corresponds to the contrast of a test pattern, k_ft corresponds to the contrast threshold for a test frequency, C_b corresponds to the contrast of the pattern of said background frame of reference, k_fb corresponds to the contrast threshold for the frequencies of said background frame of reference, C_o, that depends on the temporal frequency, is a constant that corresponds to the signal-to-noise ratio used when detecting left-right movement of a test pattern relative to of said background frame of reference, n corresponds to the slope of the contrast response function, m is a constant, B corresponds to the spatial period of said background frame of reference, x_o corresponds to a zero-crossing or contrast difference used as the point of reference to judge the direction said test pattern moved between two pattern presentations at times t₁ and t₂, and k_i, k_j are changeable constants for the gain of the contrast sensitivity which may be changed by feedback.

8. The machine vision system of claim 1 wherein said video camera means comprises:

a) a video camera having an input lens for viewing an area of interest and producing an analog signal at an output thereof reflecting a 2-dimensional area of interest being viewed by said input lens;

b) analog to digital conversion means connected to said output of said video camera for converting said analog signal into a binary signal; and

,

c) digital buffer means for storing said binary signal.

9. In a machine vision system including a video camera having an input lens for viewing an area of interest and producing an analog signal at an output thereof reflecting a 2-dimensional area of interest being viewed by the input lens, an analog to digital converter connected to the output of the video camera for converting the analog signal into a binary signal, a digital buffer for storing the binary signal, and logic for analyzing the binary signal at times t1 and t2 to provide information about the contents of the area of interest, the method for determining movement in the area of interest comprising the steps of:

a) filtering the binary signal from the digital buffer at times t₁ and t₂ to produce enhanced 2-dimensional binary representations of the area of interest at the times;

b) producing smoothed versions of the enhanced 2-dimensional binary representations;

c) processing the enhanced 2-dimensional binary representations to provided the spatial gradients of components thereof comprising a background frame of reference and components identified with objects moving against the background frame of reference;

d) producing the temporal gradients of the enhanced 2-dimensional binary representations; and

,

e) comparing the spatial and temporal gradients at times t₁ and t₂ to one another to determine any motion parallax existing in the area of interest, whereby movement of objects in the area of interest is determined.

10. The method of claim 9 and additionally including the steps of:

a) summing the outputs from paired Gabor filters across the background frame of reference; and

,

b) using the summed output to determine the direction of movement.

11. The method of claim 9 and additionally including the steps of:

a) encoding the image intensity of the pattern of the area of interest by separable spatial and temporal filters consisting of paired even- and odd-symmetric simple cells in quadrature phase;

b) for each combination of the paired even- and odd-symmetric filters at each spatial scale being analyzed, passing the input signal through the spatial and temporal filters to produce four separable responses wherein the output from each the spatial filter is processed during two different time intervals by a low-pass temporal filter and a bandpass temporal filter; and

,

c) taking the sums and differences of the outputs from the paired filters to produce spatiotemporally-oriented nonlinear responses that are selective for the direction of any motion.

12. The method of claim 11 and additionally including the step of:

tuning the paired even- and odd-symmetric simple cells in quadrature phase to a 90°

spatial-phase difference.

13. The method of claim 11 wherein the separable spatial and temporal filters comprise:

a) an even-symmetric Gabor function, F_ES, described as,

space="preserve" listing-type="equation">F.sub.ES (f,x,σ

.sup.2)=cos (2π

fx)e.sup.-(x-x.sbsp.o.sup.).spsp.2.sup./2σ

.spsp.2 ;

and,

b) an odd-symmetric Gabor function, F_OS, described as,

space="preserve" listing-type="equation">F.sub.OS (f,x,σ

.sup.2)=sin (2π

fx)e.sup.-(x-x.sbsp.o.sup.).spsp.2.sup./2σ

.spsp.2

,where f corresponds to the spatial-frequency of the pattern, x corresponds to the horizontal spatial position being examined, x_o corresponds to the video camera mean'"'"'s fixation point, and σ

² corresponds to the variability within the pattern'"'"'s spatial period in locating the position of the most salient contrast difference, x_o.

14. The method of claim 11 and additionally including the step of:

discriminating the direction an object in the pattern moves relative to the background frame of reference at two different times whenever the sums and differences of outputs from the paired filters pooled across the background frame of reference exceeds a pre-established threshold.

15. The method of claim 11 wherein:

a) the low-pass temporal filter F_ES is described by, ##EQU7## b) and the bandpass temporal filter F_OS is described by, ##EQU8## , where C_t corresponds to the contrast of a test pattern, k_ft corresponds to the contrast threshold for a test frequency, C_b corresponds to the contrast of the pattern of the background frame of reference, k_fb corresponds to the contrast threshold for the frequencies of the background frame of reference, C_o, that depends on the temporal frequency, is a constant that corresponds to the signal-to-noise ratio used when detecting left-right movement of a test pattern relative to of the background frame of reference, n corresponds to the slope of the contrast response function, m is a constant, B corresponds to the spatial period of the background frame of reference, x_o corresponds to a zero-crossing or contrast difference used as the point of reference to judge the direction the test pattern moved between two pattern presentations at times t₁ and t₂, and k_i, k_j are changeable constants for the gain of the contrast sensitivity which may be changed by feedback.

16. The method of claim 15 and first additionally including determining the direction a test pattern moves relative to a multi-frequency background by the steps of:

a) computing and comparing the difference and sum of the output of paired Gabor filters during each of a pair of temporal intervals being examined;

b) establishing leftward movement by the difference between the outputs; and

,

c) establishing rightward movement by the sum of the outputs.

17. The method of claim 16 and first additionally including the steps of:

a) discriminating left-right movement at one spatial position when the difference or sum of the paired even- and odd-symmetric filters at time t₁ differs significantly from the difference or sum at time t₂ ; and

,

b) squaring the output of the paired filters to introduce a component at the difference frequency whereby the sign of the temporal gradient determines whether the test pattern moved to the right or moved to the left of the background'"'"'s peak luminance.

18. The method of claim 17 and additionally including the steps of:

a) detecting the contrast of each pattern component using filters tuned to spatial-frequencies having a bandwidth of 1 to 11/2 octaves; and

,

b) employing a hyperbolic contrast response function such as that which optimally characterizes the contrast transducer function of normal observers and simple and complex cells in the striate cortex to predict the minimum contrast needed to discriminate the direction of movement.

19. The method of claim 18 wherein:

the hyperbolic contrast transducer function is a nonlinear function that contains both a nonlinear power function for the contrast of the test pattern and thresholding factors.

20. In a machine vision system including a video camera having an input lens for viewing an area of interest and producing an analog signal at an output thereof reflecting a 2-dimensional area of interest being viewed by the input lens, an analog to digital converter connected to the output of the video camera for converting the analog signal into a binary signal, a digital buffer for storing the binary signal, and logic for analyzing the binary signal at times t₁ and t₂ to provide information about the contents of the area of interest, the method for determining movement in the area of interest by establishing the 2-dimensional velocity of objects and converting them into a 3-dimensional position and depth map comprising the steps of:

a) horizontally scanning the area of interest to create a sequence of video images taken at small distance intervals so as to measure motion parallax or translational movement taking place in the area of interest; and

,

b) constructing the depth map by scene analysis using paired even- and odd-symmetric filters that are normalized Gabor filters, that comprise a cosine times a Gaussian and a sine times a Gaussian, the even- and odd-symmetric filters being oriented filters that compute both the smoothed contrast and the corresponding spatial gradient at each spatial position to provide two independent measures of the contrast differences in the area of interest, the paired filters being computed at several orientations and resolutions using a coarse-to-fine matching procedure;

wherein said step of scanning the area of interest includes the step of;

dividing the area of interest into rectangular windows of attention determined by different object widths wherein closer occluding objects determine a maximum window of attention that can be used to view more distant object;

wherein;

a) within each window of attention, the location that produces the maximum output of the paired even- and odd-symmetric filters at low resolutions that is above a pre-established threshold is used to determine the width of objects that are used to partition the area of interest into different depth regions with those objects being verified at higher resolution spatial scales;

b) constructing the depth map using regions of constant velocity to construct each moving object'"'"'s height and width and changes in the direction of movement relative to the video camera and other objects in the scene to infer the position of the objects in a three-dimensional scene such that the closer an object is to the video camera, the larger the distance transversed by the object in each video image of the scene; and

,

c) updating the depth map by minimizing deviations from expected changes in object boundaries at different depths over time.

21. The method of claim 20 and additionally including the steps of:

a) scanning the area of interest until a first suprathreshold contrast difference is found;

b) determining the motion parallax of objects moving within the area of interest; and

,

c) constructing the depth map using oriented paired filters analyzed over different windows of attention across the area of interest.

22. The method of claim 21 wherein;

the paired even- and odd-symmetric filters employed in step (c) include a nonlinear contrast transducer function that incorporates gain and threshold changes induced by different scene parameters, such as illumination, to normalize the output of the paired filters.

23. The method of claim 21 and additionally including the step of:

tuning the paired even- and odd-symmetric filters employed in step (c) in quadrature phase to a 90°

spatial-phase difference.

24. The method of claim 21 wherein the paired even- and odd-symmetric filters employed in step (c) are separable spatial and temporal filters comprising:

a) an even-symmetric Gabor function, F_ES, described as,

space="preserve" listing-type="equation">F.sub.ES (f,x,σ

.sup.2)=cos (2π

fx)e.sup.-(x-x.sbsp.o.sup.).spsp.2.sup./2σ

.spsp.2 ;

and,

b) an odd-symmetric Gabor function, F_OS, described as,

space="preserve" listing-type="equation">F.sub.OS (f,x,σ

.sup.2)=sin (2π

fx)e.sup.-(x-x.sbsp.o.sup.).spsp.2.sup./2σ

.spsp.2

,where f corresponds to the spatial-frequency of the pattern of the area of interest, x corresponds to the horizontal spatial position being examined, x_o corresponds to the video camera'"'"'s fixation point, and σ

² corresponds to the variability within the pattern'"'"'s spatial period in locating the position of the most salient contrast difference, x_o.

25. The method of claim 24 and additionally including the step of:

discriminating the direction an object moves relative to the background frame of reference at two different times whenever the sums and differences of outputs from the paired filters pooled across the background frame of reference exceeds a pre-established threshold.

26. The method of claim 24 wherein additionally:

a) the low-pass temporal filter F_ES is described by, ##EQU9## b) and the bandpass temporal filter F_OS is described by, ##EQU10## , where C_t corresponds to the contrast of a test pattern, k_ft corresponds to the contrast threshold for a test frequency, C_b corresponds to the contrast of the pattern of the background frame of reference, k_fb corresponds to the contrast threshold for the frequencies of the background frame of reference, C_o, that depends on the temporal frequency, is a constant that corresponds to the signal-to-noise ratio used when detecting left-right movement of a test pattern relative to of the background frame of reference, n corresponds to the slope of the contrast response function, m is a constant, B corresponds to the spatial period of the background frame of reference, x_o corresponds to a zero-crossing or contrast difference used as the point of reference to judge the direction the test pattern moved between two pattern presentations at times t₁ and t₂, and k_i, k_j are changeable constants for the gain of the contrast sensitivity which may be changed by feedback.

27. The method of claim 20 and additionally including the steps of:

a) filtering the binary signal from the digital buffer at times t₁ and t₂ to produce enhanced 2-dimensional binary representations of the area of interest at the times;

b) producing smoothed versions of the enhanced 2-dimensional binary representations;

c) processing the enhanced 2-dimensional binary representations to provided the spatial gradients of components thereof comprising a background frame of reference and components identified with objects moving against the background frame of reference;

d) producing the temporal gradients of the enhanced 2-dimensional binary representations; and

,

e) comparing the spatial and temporal gradients at times t₁ and t₂ to one another to determine any motion parallax existing in the area of interest, whereby movement of objects in the area of interest is determined.