IMAGE PROCESSING METHOD

US 20140198952A1
Filed: 03/17/2014
Published: 07/17/2014
Est. Priority Date: 07/26/1996
Status: Active Grant

First Claim

Patent Images

1. 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.

View all claims

4 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

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)).

3 Citations

50 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, 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.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 42, 45, 46, 47, 48, 49, 50)
- - 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 corresponding to the spatial position of such pixels within the frame.
  - 3. The process according to claim 1 comprising 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, said identifying of the velocity of movement 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;
      
      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.
  - 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 comprisingforming histograms along coordinate axes for pixels of the input signal without significant variation between the current frame and a prior frame;
    - andforming 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 I_a, I_b, I_c, I_din the histograms along the coordinate axes, and forming the composite signal from the pixels falling within such limits.
  - 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 6 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.
  - 9. A process according to claim 1 comprising identifying relative movement in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, wherein the identifying of relative movement comprises:
    - 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 one of claims 1 and 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 comprisingdetermining 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 comprisingdetermining 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.
  - 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 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.
  - 24. The process according to claim 23 wherein p is incremented or decremented by one.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.
  - 26. The process according to claim 1 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.
  - 42. A process according to any one of claims 1-32 for tracking a target in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the target comprising pixels in one or more of a plurality of classes in one or more of a plurality of domains, the process comprising:
    - selecting a pixel of the target as a starting pixel;
      
      on a frame-by-frame basis;
      
      forming a tracking box around the starting pixel and for each pixel of the input signal in the tracking box forming a histogram of the pixels in the one or more of a plurality of classes in the one or more of a plurality of domains;
      
      successively increasing the size of the tracking box and for each pixel of the input signal, in each successive tracking box forming a histogram of the pixels in the one or more of a plurality of classes in the one or more of a plurality of domains;
      
      determining when the target is substantially within the tracking box, stopping the size increasing of said tracking box, and adjusting the center of the tracking box based upon the histograms.
  - 45. The process according to claims 42 and 44, comprising centering the tracking box relative to the optical axis of the image.
  - 46. The apparatus according any one of claims 32-41, 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.
  - 47. The apparatus of claim 46 wherein the classifier includes a register that enables the classification criteria to be set by the user or by a separate program.
  - 48. The apparatus according to claim 46, 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.
  - 49. The apparatus according to claims 46-48 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.
  - 50. The process according to claims 42-45 comprising calculating a histogram according to a projection axis in a region delimited by an associated classifier, between two points on the projection axis, creating a histogram of the same points with orientation and intensity of motion as input parameters and modifying the values corresponding to said two points of the classifier and calculate an anticipated next frame.

33. 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.
- View Dependent Claims (35, 36, 37, 38, 39, 40, 41)
- - 35. he apparatus according to claim 33 wherein the domains are selected from the groups consisting of i) luminance, ii) speed (V), iii) oriented direction (DI), 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.
  - 36. The apparatus according to claim 33 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 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.
  - 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 I_a, I_b, I_c, I_din the histograms along the coordinate axes, and forming the composite signal from the pixels falling within such limits.
  - 40. The apparatus according to claim 38 further comprising:
    - 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.

34. The apparatus according to claim 34 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 corresponding to the spatial position of such pixels within the frame.

43. A process of tracking a target in an input signal, the input signal comprising a succession of frames, each frame comprising a succession of pixels, the target comprising pixels in one or more of a plurality of classes in one or more of a plurality of domains, the process comprising, on a frame-by-frame basis:
- forming at least one histogram of the pixels in the one or more of a plurality of classes in the one or more of a plurality of domains, said at least one histogram referring to classes defining said target, and identifying the target from said at least one histogram.
- View Dependent Claims (44)
- - 44. The process according to claim 43 further comprising drawing a tracking box around the target.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Image Processing Technologies, LLC (General Patent Corporation), Southern District of Florida
Original Assignee
Image Processing Technologies, LLC (General Patent Corporation)
Inventors
PIRIM, Patrick

Granted Patent

US 8,983,134 B2
Time in Patent Office

Days
Field of Search
US Class Current

382/103
CPC Class Codes

G06T 2207/10016   Video; Image sequence

G06T 2207/20104   Interactive definition of r...

G06T 2207/30241   Trajectory

G06T 5/70   Denoising; Smoothing

G06T 7/10   Segmentation; Edge detectio...

G06T 7/20   Analysis of motion motion e...

G06T 7/246   using feature-based methods...

G06T 7/70   Determining position or ori...

G06T 7/73   using feature-based methods

G06V 10/255   Detecting or recognising po...

G06V 10/50   by performing operations wi...

G06V 20/52   Surveillance or monitoring ...

H04N 23/69   Control of means for changi...

IMAGE PROCESSING METHOD

First Claim

4 Assignments

0 Petitions

Accused Products

Abstract

3 Citations

50 Claims

Specification

Solutions

Use Cases

Quick Links

IMAGE PROCESSING METHOD

First Claim

4 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

3 Citations

50 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links