Image processing apparatus and method

• US 6,486,909 B1
• Filed: 09/13/1999
• Issued: 11/26/2002
• Est. Priority Date: 07/26/1996
• Status: Expired due to Term

• Current Assignee: Image Processing Technologies, LLC (General Patent Corporation), William J. Brown
• Original Assignee: Holding B.E.V. S.A.
• Inventors: Pirim, Patrick
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): Bugg, George A
• Application Number:
  US09/230,502
• Time in Patent Office: 1,170 Days
• Field of Search: 348/143, 382/262, 382/107, 382/236
• US Class Current: 348/143
• CPC Class Codes: G06T 7/254 involving subtraction of images
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation

Abstract

The purpose of this invention is a process and a device operating in real time for identifying and localizing an area in relative movement in a scene and determining the speed and oriented direction of this relative movement in real time.

The process carries out temporal processing of the digital video input signal S(PI) that consists in deducing, from the variations between the value of each pixel in a frame and in the immediately preceding frame, a binary signal DP identifying whether or not there was a significant variation and a digital signal CO representing the magnitude of this variation, and a spatial processing consisting in distributing in a matrix these two signals successively for a single frame that is scanned through the matrix, and deducing the required relative movement and its parameters from this matrix distribution. The device achieves this by including a temporal processing unit 15 associated with a memory 16 and a spatial processing unit 17 associated with a delay unit 18; the clock unit 20 and the control unit 19 control the rate of operation of units 15 and 17.

Claims

1. A process for identifying relative movement in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the process comprising:

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; and

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.

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

3. The process according to claim 2 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 along an oriented direction around the particular pixel.

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

5. The process according to claim 4 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 a long an oriented direction a round the particular pixel.

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

7. The process according to claim 6 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.

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

9. The process according to claim 8 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.

10. A process of smoothing an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the process 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, including 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 (LI) exceeds a threshold (SE); 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;

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

$\mathrm{LO}=\mathrm{LI}+\frac{\mathrm{PI}-\mathrm{LI}}{\mathrm{CO}}.$

11. The process according to claim 10 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.

12. The process according to claim 11 wherein p is incremented or decremented by one.

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

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

15. A process for identifying an area in relative movement in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the process comprising:

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.

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

n matrices, where n is odd.

17. The process according to claim 16 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.

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

19. A process for identifying the velocity of movement of an area of an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the process comprising:

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; and

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.

20. The process according to claim 19 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.

21. An apparatus for identifying relative movement in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the apparatus comprising:

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

means for 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 signal between the current frame and the immediately previous smoothed input frame, and for determining the amplitude of the variation;

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;

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

means for determining in the first matrix a particular area in which the binary value for each pixel is a particular value representing significant variation, and, for such particular area, for 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 in the oriented direction, the amplitude of the variation along the oriented direction determining the velocity of movement of the pixel.

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

23. The apparatus according to claim 21 wherein the first and second matrices are hexagonal matrices centered on the particular pixel.

24. The apparatus according to claim 21 wherein the first and second matrices are inverted L-shaped matrices with a single row and a single column.

25. The apparatus according to claim 21 wherein the time constant is in the form 2^p, the time constant being reduced or increased by incrementing or decrementing p.

27. The apparatus according to claim 21 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.

26. An apparatus for smoothing an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the apparatus comprising:

means for smoothing each pixel of the input signal using a time constant (CO) for such pixel, thereby generating a smoothed pixel value (LO); and

means for determining the existence of a significant variation for a given pixel, and modifying the time constant (CO) for the pixel to be used in smoothing the pixel in subsequent frames of the input signal based upon the existence of such significant variation,

wherein the means for determining the existence of a significant variation for a given pixel comprises means for 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 (LI) exceeds a threshold (SE); and

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

$\mathrm{LO}=\mathrm{LI}+\frac{\mathrm{PI}-\mathrm{LI}}{\mathrm{CO}}.$

28. An apparatus for smoothing an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the apparatus comprising:

means for smoothing each pixel of the input signal using a time constant (CO) for such pixel, thereby generating a smoothed pixel value (LO);

means for determining the existence of a significant variation for a given pixel, and modifying the time constant (CO) for the pixel to be used in smoothing the pixel in subsequent frames of the input signal based upon the existence of such significant variation; and

means for generating an output signal comprising, for each pixel, a binary value (DP) indicating the existence or non-existence of a significant variation, and the value of the time constant (CO).

29. The apparatus according to claim 28 further comprising a frame-size memory, wherein the binary values (DP) and the time constants (CO) are stored in the memory.

30. An apparatus for identifying an area in relative movement in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the apparatus comprising:

means for 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;

means for generating a second array indicative of the magnitude of significant variation of each pixel between the current frame and a prior frame;

means for 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

means for determining whether the pixel under consideration and each pixel along an oriented direction relative to the pixel under consideration within the first matrix is a particular value representing the presence of significant variation, and if so, for establishing a second matrix within the first matrix, centered on the pixel under consideration, and for determining whether the amplitude of the pixels in the second matrix are indicative of movement along an oriented direction relative to the pixel under consideration, 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.

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

n matrices, where n is odd.

32. The apparatus according to claim 31 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.

33. The apparatus according to claim 30 wherein the first and second matrices are selected from the group consisting of hexagonal matrices and inverted L-shaped matrices.

34. An apparatus for identifying the velocity of movement of an area of an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the apparatus 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 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.

35. The apparatus according to claim 34 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.

36. The apparatus according to claim 35 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.