Methods and apparatus for identifying and localizing an area of relative movement in a scene

• US 7,181,047 B2
• Filed: 02/23/2001
• Issued: 02/20/2007
• Est. Priority Date: 07/26/1996
• Status: Expired due to Term

• Current Assignee: Image Processing Technologies, LLC (General Patent Corporation), Southern District of Florida
• Original Assignee: Brown William J As Trustee For Joseph D Harbaugh
• Inventors: Pirim, Patrick
• Primary Examiner(s): Mehta; Bhavesh M.
• Assistant Examiner(s): Seth; Manav
• Application Number:
  US09/792,294
• Publication Number:
  US 20020071595A1
• Time in Patent Office: 2,188 Days
• Field of Search: 382/103, 382/104, 382/106, 382/107, 382/115, 382/164, 382/165, 382/168, 382/170, 382/171, 382/173, 382/174, 382/181, 382/190, 382/195, 382/197, 382/205, 382/224, 382/225, 382/226, 382/227, 382/206
• US Class Current: 382/107
• CPC Class Codes: G06T 7/254 involving subtraction of images
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation

Abstract

A method and apparatus for localizing an area in relative movement and for determining the speed and direction thereof in real time is disclosed. Each pixel of an image is smoothed using its own time constant. A binary value corresponding to the existence of a significant variation in the amplitude of the smoothed pixel from the prior frame, and the amplitude of the variation, are determined, and the time constant for the pixel is updated. For each particular pixel, two matrices are formed that include a subset of the pixels spatially related to the particular pixel. The first matrix contains the binary values of the subset of pixels. The second matrix contains the amplitude of the variation of the subset of pixels. In the first matrix, it is determined whether the pixels along an oriented direction relative to the particular pixel have binary values representative of significant variation, and, for such pixels, it is determined in the second matrix whether the amplitude of these pixels varies in a known manner indicating movement in the oriented direction. In each of several domains, histogram of the values in the first and second matrices falling in such domain is formed. Using the histograms, it is determined whether there is an area having the characteristics of the particular domain. The domains include luminance, hue, saturation, speed (V), oriented direction (D1), time constant (CO), first axis (x(m)), and second axis (y(m)).

Claims

1. A process for identifying pixels in an input signal in one of a plurality of classes in one of a plurality of domains in histogram formation blocks including classifiers and associated with validation blocks, the input signal comprising a succession of frames, each frame comprising a succession of pixels, each histogram formation block having a memory capable of storing the number of pixels in a frame, the process comprising, on a frame-by-frame basis:

for each pixel of the input signal, analyzing the pixel and providing an output signal for each domain containing information to identify each domain in which the pixel is classified;

providing a histogram formation block with its classifier for each domain, the classifier enabling classification of pixels within each domain to selected classes within the domain to an output;

providing a validation signal for the domains from the validation block of the respective histogram formation block, the validation signal selecting one or more of the plurality of domains for processing in the respective histogram formation block;

forming a histogram in the memory for pixels of the output signal within the classes selected by the classifier within each domain selected by the validation signal, the output of each classifier being communicated to each of the validation blocks via a bus; and

computing, in parallel to the forming of a histogram, key characteristics of the histogram including at least the position (POSRMAX) of the maximum of the histogram.

2. The process according to claim 1 further comprising:

forming histograms along coordinate axes for the pixels within the classes selected by the classifier within each domain selected by the validation signal; and

forming a composite signal from the classification output of the axes in a combination unit and corresponding to the spatial position of such pixels within the frame.

5. A process according to claim 1 for identifying a non-moving area in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the process comprising

forming histograms along coordinate axes for pixels of the input signal without significant variation between the current frame and a prior frame;

and

forming a composite signal corresponding to the spatial position of such pixels within the frame.

6. The process according to claim 2 or 5 further comprising identifying pixels falling within limits l_a, l_b, l_c, l_d in the histograms along the coordinate axes, and forming the composite signal from the pixels falling within such limits.

47. The process according to claim 1 wherein the domains are selected from the group consisting of i) luminance, ii) speed (V), iii) oriented direction (D1), iv) time constant (CO), v) hue, vi) saturation, vii) first axis (x(m)), and viii) second axis (y(m)) and ix) data characterized by external inputs.

3. A process for identifying pixels in an input signal in one of a plurality of classes in one of a plurality of domains, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the process comprising, on a frame-by-frame basis:

for each pixel of the input signal, analyzing the pixel and providing an output signal for each domain containing information to identify each domain in which the pixel is classified;

providing a classifier for each domain, the classifier enabling classification of pixels within each domain to selected classes within the domain;

providing a validation signal for the domains, the validation signal selecting one or more of the plurality of domains for processing; and

forming a histogram for pixels of the output signal within the classes selected by the classifier within each domain selected by the validation signal, the process further comprising identifying the velocity of movement of an area of the input signal, by;

for each particular pixel of the input signal, forming a first matrix comprising binary values indicating the existence or non-existence of a significant variation in the amplitude of the pixel signal between the current frame and a prior frame for a subset of the pixels of the frame spatially related to such particular pixel, and a second matrix comprising the amplitude of such variation;

determining in the first matrix whether the particular pixel and the pixels along an oriented direction relative to the particular pixel have binary values of a particular value representing significant variation, and, for such pixels, determining in the second matrix whether, the amplitudes of the pixels along an oriented direction relative to the particular pixel vary in a known manner indicating movement of the pixel and the pixels along an oriented direction relative to the particular pixel, the amplitude of the variation along the oriented direction determining the velocity of movement of the particular pixel.

4. The process according to claim 3 further comprising:

prior to determining the binary values for each pixel, smoothing each pixel of the input signal using a time constant for such pixel, thereby generating a smoothed input signal, the determination of the existence of a significant variation in the amplitude of the pixel being performed for each pixel of the smoothed input signal; and

using the existence of a significant variation for a given pixel to modify the time constant for the pixel to be used in smoothing subsequent frames of the input signal.

7. The process according to claim 4 further comprising:

prior to the histogram forming step i) smoothing the input signal for each pixel thereof using a time constant for such pixel, thereby generating a smoothed input signal, and ii) determining for each pixel in the smoothed input signal a binary value corresponding to the non-existence of a significant variation in the amplitude of the pixel signal between the current frame and the immediately previous smoothed input frame.

8. The process according to claim 7 further comprising using the existence of a significant variation for a given pixel to modify the time constant for the pixel to be used in smoothing subsequent frames of the input signal.

21. The process according to claim 4, comprising:

for each pixel of the input signal, i) smoothing the pixel using a time constant (CO) for such pixel, thereby generating a smoothed pixel value (LO), ii) determining whether there exists a significant variation between such pixel and the same pixel in a previous frame, and iii) modifying the time constant (CO) for such pixel to be used in smoothing the pixel in subsequent frames of the input signal based upon the existence or non-existence of a significant variation.

22. The process according to claim 21 wherein:

(a) the step of determining the existence of a significant variation for a given pixel comprises determining whether the absolute value of the difference (AB) between the given pixel value (PI) and the value of such pixel in a smoothed prior frame (L1) exceeds a threshold (SE); and

(b) the step of smoothing the input signal comprises, for each pixel, i) modifying a time constant (CO) for pixel such based upon the existence of a significant variation as determined in step (a), and ii) determining a smoothed value for the pixel (LO) as follows;

23. The process according to claim 22 wherein the time constant (CO) is in the form 2^P, and wherein p is incremented in the event that AB<

SE, and wherein p is decremented in the event AB>

=SE.

24. The process according to claim 22 further comprising generating an output signal comprising, for each pixel, a binary value (DP) indicating the existence or nonexistence of a significant variation, and the value of the time constant (CO).

25. The process according to claim 24 wherein the binary values (DP) and the time constants (CO) are stored in a memory sized to correspond to the frame size.

46. The process according to claim 23 wherein p is incremented or decremented by one.

9. A process for identifying pixels in an input signal in one of a plurality of classes in one of a plurality of domains, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the process comprising, on a frame-by-frame basis:

for each pixel of the input signal, analyzing the pixel and providing an output signal for each domain containing information to identify each domain in which the pixel is classified;

providing a classifier for each domain, the classifier enabling classification of pixels within each domain to selected classes within the domain;

providing a validation signal for the domains, the validation signal selecting one or more of the plurality of domains for processing; and

forming a histogram for pixels of the output signal within the classes selected by the classifier within each domain selected by the validation signal, the process further comprising identifying relative movement in the input signal, by;

for each pixel of the input signal, smoothing the input signal using a time constant for such pixel, thereby generating a smoothed input signal;

determining for each pixel in the smoothed input signal a binary value corresponding to the existence of a significant variation in the amplitude of the pixel between the current frame and the immediately previous smoothed input frame, and the amplitude of the variation;

using the existence of a significant variation for a given pixel, modifying the time constant for the pixel to be used in smoothing subsequent frames of the input signal;

for each particular pixel of the input signal, forming a first matrix comprising the binary values of a subset of the pixels of the frame spatially related to such particular pixel, and a second matrix comprising the amplitude of the variation of the subset of the pixels of the frame spatially related to such particular pixel;

determining in the first matrix whether the particular pixel and the pixels along an oriented direction relative to the particular pixel have binary values of a particular value representing significant variation, and, for such pixels, determining in the second matrix whether the amplitude of the pixels along the oriented direction relative to the particular pixel varies in a known manner indicating movement in the oriented direction of the particular pixel and the pixels along the oriented direction relative to the particular pixel, the amplitude of the variation of the pixels along the oriented direction determining the velocity of movement of the pixel and the pixels along the oriented direction relative to the particular pixel,

in each of one or more domains, forming a histogram of the values distributed in the first and second matrices falling in each such domain,

for a particular domain, determining from the histogram for such domain an area of significant variation;

forming histograms of the area of significant variation along coordinate axes; and

determining from the histograms along the coordinate axes, whether there is an area in movement for the particular domain.

10. The process according to claim 9 wherein the domains are selected from the group consisting of i) luminance, ii) speed (V), iii) oriented direction (D1), iv) time constant (CO), v) hue, vi) saturation, vii) first axis (x(m)), and viii) second axis (y(m)) and ix) data characterized by external inputs.

11. The process according to claim 9 wherein the first and second matrices are square matrices with the same odd number of rows and columns, centered on the particular pixel.

12. The process according to claim 11 wherein the steps of determining in the first matrix whether the particular pixel and the pixels along an oriented direction relative to the particular pixel have binary values of a particular value representing significant variation, and the step of determining in the second matrix whether the amplitude signal varies in a predetermined criteria along an oriented direction relative to the particular pixel, comprise applying nested n×

n matrices, where n is odd, centered on the particular pixel to the pixels within each of the first and second matrices, the process further comprising;

determining the smallest nested matrix in which the amplitude signal varies of predetermined values symmetrical relative to the particular pixel along an oriented direction around said particular pixel.

13. The process according to claim 9 wherein the first and second matrices are hexagonal matrices centered on the particular pixel.

14. The process according to claim 13 wherein the steps of determining in the first matrix whether the particular pixel and the pixels along an oriented direction relative to the particular pixel have binary values of a particular value representing significant variation, and the step of determining in the second matrix whether the amplitude signal varies in a predetermined criteria along an oriented direction relative to the particular pixel, comprise applying nested hexagonal matrices of varying size centered on the particular pixel to the pixels within each of the first and second matrices, the process further comprising

determining the smallest nested matrix in which the amplitude signal varies of predetermined values symmetrical relative to the particular pixel along an oriented direction around said particular pixel.

15. The process according to claim 9 wherein the first and second matrices are inverted L-shaped matrices with a single row and a single column.

16. The process according to claim 15 wherein the steps of determining in the first matrix whether the particular pixel and the pixels along an oriented direction relative to the particular pixel have binary values of a particular value representing significant variation, and the step of determining in the second matrix whether the amplitude signal varies in a predetermined criteria along an oriented direction relative to the particular pixel, comprise applying nested n×

n matrices, where n is odd, to the single line and the single column to determine the smallest matrix in which the amplitude varies on a line with the steepest slope and constant quantification.

17. The process according to claim 9 wherein the first and second matrices are angular sector shaped matrices reproducing a portion of an eye.

18. The process according to claim 17 wherein the steps of determining in the first matrix whether the particular pixel and the pixels along an oriented direction relative to the particular pixel have binary values of a particular value representing significant variation, and the step of determining in the second matrix whether the amplitude signal varies in a predetermined criteria along an oriented direction relative to the particular pixel, comprise applying nested angular sector shaped matrices of varying size centered on the particular pixel to the pixels within each of the first and second matrices, the process further comprising

determining the smallest nested matrix in which the amplitude signal varies of predetermined values symmetrical relative to the particular pixel along an oriented direction around said particular pixel.

19. The process according to claim 9 wherein the time constant is in the form 2^P, the time constant being reduced or increased by incrementing or decrementing p.

20. The process according to claim 19 wherein successive decreasing portions of complete frames of the input signal are considered using a Mallat time-scale algorithm and the largest of these portions, which provides displacement, speed and orientation indications compatible with the value of p, is selected.

26. A process for identifying pixels in an input signal in one of a plurality of classes in one of a plurality of domains, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the process comprising, on a frame-by-frame basis:

for each pixel of the input signal, analyzing the pixel and providing an output signal for each domain containing information to identify each domain in which the pixel is classified;

providing a classifier for each domain, the classifier enabling classification of pixels within each domain to selected classes within the domain;

providing a validation signal for the domains, the validation signal selecting one or more of the plurality of domains for processing; and

forming a histogram for pixels of the output signal within the classes selected by the classifier within each domain selected by the validation signal, the process further comprising identifying an area in relative movement in said input signal, through;

generating a first array indicative of the existence of significant variation in the magnitude of each pixel between a current frame and a prior frame;

generating a second array indicative of the magnitude of significant variation of each pixel between the current frame and a prior frame, establishing a first moving matrix centered on a pixel under consideration and comprising pixels spatially related to the pixel under consideration, the first moving matrix traversing the first array for consideration of each pixel of the current frame; and

determining whether the pixel under consideration and each pixel of the pixels spatially related to the pixel under consideration along an oriented direction relative thereto within the first matrix are a particular value representing the presence of significant variation, and if so, establishing in a second matrix within the first matrix, centered on the pixel under consideration, and determining whether the amplitude of the pixels in the second matrix spatially related to the pixel under consideration along an oriented direction relative thereto are indicative of movement along such oriented direction, the amplitude of the variation along the oriented direction being indicative of the velocity of movement, the size of the second matrix being varied to identify the matrix size most indicative of movement.

27. The process according to claim 26 further comprising:

in at least one domain selected from the group consisting of i) luminance, ii) speed (V), iii) oriented direction (D1), iv) time constant (CO), v) hue, vi) saturation, and vii) first axis (x(m)), and viii) second axis (y(m)), and ix) data characterized by external inputs, forming at least one histogram of the values in such domain for pixels indicative of movement along an oriented direction relative to the pixel under consideration.

28. The process according to claim 27 further comprising:

for the pixels in said at least one histogram, forming histograms of the position of such pixels along coordinate axes.

29. The process according to claim 28 further comprising determining from the histograms along the coordinate axes an area of the image meeting criteria of the at least one domain.

30. The process according to claim 26 wherein the first and second matrices are square, and the sizes of the second matrix are nested n×

n matrices, where n is odd.

31. The process according to claim 30 wherein the matrix most indicative of movement is the smallest nested matrix containing pixels indicative of movement along an oriented direction relative to the pixel under consideration.

32. The process according to claim 26 wherein the first and second matrices are selected from the group consisting of hexagonal matrices and inverted L-shaped matrices.

33. An apparatus for identifying pixels in an input signal in one of a plurality of classes in one of a plurality of domains in histogram formation blocks including classifiers and associated with validation blocks, the input signal comprising a succession of frames, each frame comprising a succession of pixels, each histogram formation block having a memory capable of storing the number of pixels in a frame, the apparatus comprising:

means for analyzing each pixel of the input signal and for providing an output signal for each domain containing information to identify each domain in which the pixel is classified;

a histogram formation block with its classifier for each domain, the classifier classifying pixels within each domain in selected classes within the domain;

a linear combination unit for each domain, each linear combination unit generating a validation signal for the domain from the validation block of the respective histogram formation block, the validation signal selecting one or more of the plurality of domains for processing in the histogram formation block; and

means for forming a histogram in the memory for pixels of the output signal within the classes selected by the classifier within each domain selected by the validation signals, the output of each classifier being communicated to each of the validation blocks via a bus; and

means for computing, in parallel to the forming of a histogram, key characteristics of the histogram including at least the position (POSRMAX) of the maximum of the histogram.

34. The apparatus according to claim 33 further comprising:

means for forming histograms along coordinate axes for the pixels within the classes selected by the classifier within each domain selected by the validation signal; and

means for forming a composite signal from the classification output of the axes in a combination unit and corresponding to the spatial position of such pixels within the frame.

35. The apparatus according to claim 33 wherein the domains are selected from the groups consisting of i) luminance, ii) speed (V), iii) oriented direction (D1), iv) time constant (CO), v) hue, vi) saturation, and vii) first axis (x(m)), and viii) second axis (y(m)) and ix) data characterized by external inputs.

38. The apparatus according to claim 33 for identifying a non-moving area in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the apparatus comprising:

means for forming histograms along coordinate axes for pixels of a current frame without a significant variation from such pixels in a prior frame; and

means for forming a composite signal corresponding to the spatial position of such pixels within the frame.

39. The apparatus according to any one of claims 33 and 38 further comprising means for identifying pixels falling within limits l_a, l_b, l_c, l_d in the histograms along the coordinate axes, and forming the composite signal from the pixels falling within such limits.

42. The apparatus according to claim 33, further comprising a histogram formation block forming histograms of speed, a memory storing up to the number of pixels in an image, multiplexors controlling setting an clearing of said memory, a classifier enabling only data having selected classification criteria to be considered further, meaning to possibly be included in histograms formed by corresponding histogram formation block.

43. The apparatus of claim 42 wherein the classifier includes a register that enables the classification criteria to be set by the user or by a separate program.

44. The apparatus according to claim 42, comprising a computing unit for comprising the key characteristics for histograms formed in said memory said computing unit including memories for each of the key characteristics which include the minimum (MIN) of the histogram, the maximum (MAX) of the histogram, the number of points (NBPTS) in the histogram, the position (POSRMAX) of the maximum of the histogram and the number of points (RMAX) at the maximum of the histogram.

45. The apparatus according to claim 42, further comprising an adder incrementing output of said memory, said adder being controlled by a validation signal from a corresponding validation unit receiving via a bus the output of said classifier so as to select only data points in any selected classes within any selected domains.

36. An apparatus for identifying pixels in an input signal in one of a plurality of classes in one of a plurality of domains, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the apparatus comprising:

means for analyzing each pixel of the input signal and for providing an output signal for each domain containing information to identify each domain in which the pixel is classified;

a classifier for each domain, the classifier classifying pixels within each domain in selected classes within the domain;

a linear combination unit for each domain, the linear combination unit generating a validation signal for the domain, the validation signal selecting one or more of the plurality of domains for processing; and

means for forming a histogram for pixels of the output signal within the classes selected by the classifier within each domain selected by the validation signal,

the apparatus further comprising;

means for determining for each pixel in the input signal a binary value corresponding to the existence of a significant variation in the amplitude of the pixel signal between the current frame and the immediately previous smoothed input frame, and for determining the amplitude of the variation;

means for forming, for each particular pixel of the input signal, a first matrix comprising the binary values of a subset of the pixels spatially related to such particular pixel, and a second matrix comprising the amplitude of the variation of the subset of the pixels spatially related to such particular pixel; and

means for determining in the first matrix whether for a particular pixel, and other pixels along an oriented direction relative to the particular pixel, the binary value for each pixel is a particular value representing significant variation, and, for such particular pixel and other pixels, determining in the second matrix whether the amplitude varies along an oriented direction relative to the particular pixel in a known manner indicating movement of the pixel and the other pixels, the amplitude of the variation along the oriented direction determining the velocity of movement of the pixel and the other pixels.

37. The apparatus according to claim 36 further comprising means for smoothing each pixel of the input signal using a time constant for such pixel prior to determining a binary value for each pixel, the binary values being determined on the smoothed pixels.

40. An apparatus for identifying pixels in an input signal in one of a plurality of classes in one of a plurality of domains, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the apparatus comprising:

means for analyzing each pixel of the input signal and for providing an output sianal for each domain containing information to identify each domain in which the pixel is classified;

a classifier for each domain, the classifier classifying pixels within each domain in selected classes within the domain;

a linear combination unit for each domain, the linear combination unit generating a validation signal for the domain, the validation signal selecting one or more of the plurality of domains for processing; and

means for forming a histogram for pixels of the output signal within the classes selected by the classifier within each domain selected by the validation signal,

the apparatus further comprising;

means for forming histograms along coordinate axes for pixels of a current frame without a significant variation from such pixels in a prior frame;

means for forming a composite signal corresponding to the spatial position of such pixels within the frame;

means for smoothing the input signal using a time constant for each pixel, thereby generating a smoothed input signal; and

means for determining for each pixel in the smoothed input signal a binary value corresponding to the existence or non-existence of the significant variation in the amplitude of the pixel signal between the current frame and the immediately previous smoothed input frame.

41. The apparatus according to claim 40 further comprising means for using the existence of a significant variation for a given pixel to modify the time constant for the pixel to be used in smoothing subsequent frames of the input signal.