Adaptive edge map threshold

• US 8,295,607 B1
• Filed: 06/24/2009
• Issued: 10/23/2012
• Est. Priority Date: 07/09/2008
• Status: Active Grant

• Current Assignee: Synaptics Incorporated, Synaptics, LLC (Synaptics Incorporated)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Biswas, Mainak, Namboodiri, Vipin
• Primary Examiner(s): STREGE, JOHN B
• Application Number:
  US12/490,639
• Time in Patent Office: 1,217 Days
• Field of Search: 382/199, 382/224, 382/270, 382/271, 382/192, 382/194
• US Class Current: 382/199
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/136 involving thresholding

Abstract

A method for detecting edges includes calculating a gradient level value for each pixel of a digital image and assigning each pixel to one of a plurality of gradient bins based on the calculated gradient level value for each pixel, the gradient bins being defined by threshold levels. One or more of the gradient bins are assigned as edge bins, and one or more of the gradient bins are assigned as non-edge bins according to the number of pixels assigned to each gradient bin. Pixels in the one or more edge bins are identified as edge pixels, and pixels in the one or more non-edge bins are identified as non-edge pixels in an edge map. The one or more gradient bins are assigned such that a minimum number of pixels are identified as edge pixels and no more than a maximum number of pixels are identified as edge pixels.

Claims

1. A method of detecting edges, comprising:

calculating a gradient level value for each pixel of a digital image;

assigning each pixel to one of a plurality of gradient bins based on the calculated gradient level value for each pixel, the gradient bins being defined by a plurality of threshold values;

assigning one or more of the gradient bins as edge bins and one or more of the gradient bins as non-edge bins according to the number of pixels assigned to each gradient bin;

identifying pixels in the one or more edge bins as edge pixels and identifying pixels in the one or more non-edge bins as non-edge pixels in an edge map; and

the assigning one or more of the gradient bins being configured such that a minimum number of pixels are identified as edge pixels and no more than a maximum number of pixels are identified as edge pixels.

2. The method of claim 1, further comprising adjusting the plurality of threshold values that define the gradient bins for detecting edges in a subsequent digital image according to a distribution of the gradient level values for pixels in the digital image.

3. The method of claim 1, wherein a first number of gradient bins are utilized;

wherein a first gradient bin is always assigned as an non-edge bin;

wherein a last gradient bin is always assigned as a edge bin;

wherein a plurality of gradient bins other than the first gradient bin and the last gradient bin may each be assigned as either an non-edge bin or an edge bin.

4. The method of claim 3, wherein the minimum number of pixels to be identified as edge pixels is represented as X;

wherein the maximum number of pixels to be identified as edge pixels is represented as Y;

wherein gradient bins are assigned as edge bins or non-edge bins such that the number of pixels identified as edge pixels is greater than X and less than Y.

5. The method of claim 3, wherein the minimum number of pixels to be identified as edge pixels is represented as X;

wherein the maximum number of pixels to be identified as edge pixels is represented as Y;

wherein the first gradient bin is defined by a threshold value, TH0, the first gradient bin containing gradient values (g) defined by g<

=TH0;

wherein a second gradient bin is defined by the threshold value, TH0, and a threshold value, TH1, the second gradient bin containing gradient values defined by TH0<

g<

=TH1;

wherein a third gradient bin is defined by the threshold value, TH1, and a threshold value, TH2, the third gradient bin containing gradient values defined by TH1<

g<

=TH2;

wherein a fourth gradient bin is defined by the threshold value, TH2, and includes all values greater than TH2, the fourth gradient bin containing gradient values defined by TH2<

g;

wherein a value A is a number of pixels in the first gradient bin;

wherein a value D is a number of pixels in the fourth gradient bin;

wherein only the second gradient bin, the third gradient bin, and the fourth gradient bin are assigned as edge bins if A is greater than or equal to X;

wherein only the fourth gradient bin is assigned as an edge bin if A is less than X and D is greater than or equal to Y;

wherein only the third and fourth gradient bins are assigned as edge bins if A is less than X and D is less than Y.

6. The method of claim 1, further comprising selecting a motion vector for each pixel in part based upon whether the pixel is an edge pixel or a non-edge pixel.

7. The method of claim 6, wherein a motion vector associated with small object motion is selected for a majority of edge pixels.

8. A method generating a motion vector describing motion of a pixel from a previous frame to a current frame comprising:

decomposing received previous frame data and current frame data into a high pass component and a low pass component, the high pass component corresponding to small object motion, the low pass component corresponding to large object motion;

said decomposing including performing an edge detection on pixels of the previous frame or the current frame, the edge detection including;

calculating a gradient level value for each pixel;

assigning each pixel to one of a plurality of gradient bins based on the calculated gradient level value for each pixel, the gradient bins being defined by a plurality of threshold values;

assigning one or more of the gradient bins as edge bins and one or more of the gradient bins as non-edge bins according to the number of pixels assigned to each gradient bin;

identifying pixels in the one or more edge bins as edge pixels and identifying pixels in the one or more non-edge bins as non-edge pixels;

the assigning one or more of the gradient bins being configured such that a minimum number of pixels are identified as edge pixels and no more than a maximum number of pixels are identified as edge pixels;

calculating a low pass motion vector based on the low pass component and a high pass motion vector based on the high pass component;

selecting between the low pass motion vector and the high pass motion vector for a pixel based in part on whether the pixel is identified as an edge pixel.

9. The method of claim 8, wherein the performing an edge detection further includes adjusting the plurality of threshold values that define the gradient bins for detecting edges in a subsequent frame according to a distribution of gradient level values.

10. The method of claim 9, wherein four gradient bins are utilized in performing an edge detection;

wherein a first gradient bin is always assigned as an non-edge bin;

wherein a fourth gradient bin is always assigned as a edge bin;

wherein a second gradient bin and a third gradient bin may each be assigned as either an non-edge bin or an edge bin.

11. The method of claim 10, wherein the minimum number of pixels to be identified as edge pixels is represented as X;

wherein the maximum number of pixels to be identified as edge pixels is represented as Y;

wherein the first gradient bin is defined by a gradient level value of zero and a threshold value, TH0, the first gradient bin containing gradient values (g) defined by 0<

=g<

=TH0;

wherein a second gradient bin is defined by the threshold value, TH0, and a threshold value, TH1, the second gradient bin containing gradient values defined by TH0<

g<

=TH1;

wherein a third gradient bin is defined by the threshold value, TH1, and a threshold value, TH2, the third gradient bin containing gradient values defined by TH1<

g<

=TH2;

wherein a fourth gradient bin is defined by the threshold value, TH2, and includes all values greater than TH2, the fourth gradient bin containing gradient values defined by TH2<

g;

wherein a value A is a number of pixels in the first gradient bin;

wherein a value D is a number of pixels in the fourth gradient bin;

wherein only the second gradient bin, the third gradient bin, and the fourth gradient bin are assigned as edge bins if A is greater than or equal to X;

wherein only the fourth gradient bin is assigned as an edge bin if A is less than X and D is greater than or equal to Y;

wherein only the third and fourth gradient bins are assigned as edge bins if A is less than X and D is less than Y.

12. The method of claim 9, wherein a first number of gradient bins are utilized in performing an edge detection;

wherein a first gradient bin is always assigned as an non-edge bin;

wherein a last gradient bin is always assigned as a edge bin;

wherein a plurality of intermediate gradient bins may each be assigned as either an non-edge bin or an edge bin;

wherein the minimum number of pixels to be identified as edge pixels is represented as X;

wherein the maximum number of pixels to be identified as edge pixels is represented as Y.

13. The method of claim 8, wherein calculating a low pass motion vector based on the low pass component and a high pass motion vector based on the high pass component includes:

performing a fast Fourier transform of the high pass component and low pass component of the previous frame data and the current frame data;

calculating a first phase difference between the high pass component of the current frame data and the high pass component of the previous frame data;

calculating a second phase difference between the low pass component of the current frame data and the low pass component of the previous frame data;

performing an inverse fast Fourier transform on the first phase difference and the second phase difference to generate a first inverse Fourier result and a second inverse Fourier result; and

calculating a low pass motion vector based on the first inverse Fourier result and a high pass motion vector based on the second inverse Fourier result.

14. The method of claim 8, wherein the high pass motion vector is not selected for at least the first two frames following a scene change.

15. A system comprising:

an edge detector for detecting edges in a digital video frame including;

a gradient level value calculator to calculate a gradient level value for each pixel of the digital video frame;

a plurality of gradient bins configured to store pixels assigned to particular gradient bins based on the calculated gradient level value for each pixel, the gradient bins being defined by a plurality of threshold values;

a bin assigner configured to assign one or more of the gradient bins as edge bins and one or more of the gradient bins as non-edge bins according to the number of pixels assigned to each gradient bin, the bin assigner assigning bins such that a minimum number of pixels are contained in edge bins and no more than a maximum number of pixels are contained in non-edge bins;

an edge pixel identifier configured to identify pixels in the one or more edge bins as edge pixels and to identify pixels in the one or more non-edge bins as non-edge pixels.

16. The system of claim 15, wherein the edge detector further includes a distribution calculator configured to calculate a distribution of gradient level values for each of the pixels in the digital video frame, the distribution calculator being further configured to adjust the plurality of threshold values according to the distribution.

17. The system of claim 16, wherein the distribution calculator receives gradient level value scores for each pixels of the digital video frame, calculates a distribution of the gradient level value scores across population of pixels, and identifies certain percentile points in the distribution.

18. The system of claim 16, wherein the gradient level value calculator utilizes a Sobel edge detector.

19. The system of claim 16, further comprising:

a decomposition filter that receives previous frame data and current frame data, the decomposition filter comprising a high pass filter and a low pass filter; and

a motion vector calculator configured to generate a high pass motion vector based on outputs of the high pass filter and a low pass motion vector based on outputs of the low pass filter;

a motion vector selector configured to select from between the high pass motion vector and the low pass motion vector for a pixel based in part on whether the pixel is identified as an edge pixel.

20. The system of claim 19, wherein the motion vector calculator further comprises:

a fast Fourier transform calculator configured to generate low pass frequency domain representations of the previous frame data and the current frame data from the low pass filter output and high pass frequency domain representations of the previous frame data and the current frame data from the high pass filter output;

a phase difference calculator configured to calculate a first phase difference between the previous frame low pass frequency domain representation and the current frame low pass frequency domain representation, the phase difference calculator further configured to calculate a second phase difference between the previous frame high pass frequency domain representation and the current frame high pass frequency domain representation;

an inverse Fourier transform calculator configured to generate a first inverse Fourier result based on the first phase difference, the inverse Fourier transform calculator further configured to generate a second inverse Fourier result based on the second phase difference; and

a motion vector calculator configured to generate the low pass motion vector based on the first inverse Fourier result and the high pass motion vector based on the second inverse Fourier result.