EDGE DETECTION

• US 20120093434A1
• Filed: 06/05/2009
• Published: 04/19/2012
• Est. Priority Date: 06/05/2009
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Banerjee, Serene, Shaffi, Noushath, Parikh, Pulkit
• Granted Patent: US 8,559,748 B2
• Time in Patent Office: Days
• US Class Current: 382/266
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines
• CPC Class Codes: G06V 30/162 Quantising the image signal
• CPC Class Codes: G06V 30/18019 by matching or filtering

Abstract

An edge detection method and apparatus is disclosed. The method comprises the steps of: calculating a pixel gradient value for each of a plurality of pixels of a digital image, the pixel gradient value representing the difference of a pixel value with respect to at least one neighbouring pixel; for each of a plurality of binarization threshold values, determining a corresponding edge map representing the location of pixel gradient values exceeding the binarization threshold value with respect to a side of the digital image; for each edge map, computing a measure of linearity; determining an optimal binarization threshold value based on the computed measures of linearity; and selecting the edge map corresponding to the optimal binarization threshold value.

Claims

1. An edge detection method for detecting a substantially linear edge in a digital image, the method comprising the steps of:

calculating a pixel gradient value for each of a plurality of pixels of a digital image, the pixel gradient value representing the difference of a pixel value with respect to at least one neighbouring pixel;

for each of a plurality of binarization threshold values, determining a corresponding edge map representing the location of pixel gradient values exceeding the binarization threshold value with respect to a side of the digital image;

for each edge map, computing a measure of linearity;

determining an optimal binarization threshold value based on the computed measures of linearity; and

selecting the edge map corresponding to the optimal binarization threshold value.

2. The method of claim 1, further comprising the steps of:

prior to the step of calculating pixel gradient values, preprocessing the digital image to down sample the digital image to produce a downsampled digital image having a resolution that is lower than that of the digital image; and

smoothing the downsampled digital image to reduce noise.

3. The method of claim 1, wherein the step of determining edge maps comprises, for each of a plurality of sides of the digital image, determining an edge map for each of a plurality of binarization threshold values representing the location of pixel gradient values exceeding the binarization threshold value with respect to the side of the digital image.

4. The method of claim 1, wherein the step of determining a plurality of edge maps comprises, for each of a plurality of binarization threshold values, determining a corresponding edge map by undertaking the steps of:

converting pixel gradient values to one of two values based on a comparison of the pixel value with the binarization threshold value so as to generate a binarised gradient image; and

for each row or column of the binarised gradient image, determining the location, with respect to a side of the image, of the first change in pixel value between neighbouring pixels.

5. The method of claim 1, wherein the step of determining an optimal binarization threshold value comprises selecting a binarization threshold value corresponding to a second minimum in a graph of edge map linearity versus binarization threshold value as the optimal binarization threshold value.

6. A method for detecting a page edge in a digital image comprising the steps of:

performing the edge detection method of claim 1; and

detecting the page edge by identifying the location of a substantially linear line in the selected edge map.

7. The method of claim 6, further comprising the steps of:

differentiating between small content and noise beyond the detected page edge using a threshold comparison test; and

defining a page boundary so that small content identified by the differentiating step is within the document page defined by the page boundary.

8. The method of claim 6, further comprising the step of processing the digital image so that an area beyond the detected page edge is colored with a background color.

9. Edge detection apparatus for detecting an edge of a page in a digital image, the apparatus comprising:

processing means adapted to calculate a pixel gradient value for each of a plurality of pixels of a digital image, the pixel gradient value representing the difference of a pixel value with respect to at least one neighbouring pixel;

edge map calculation means adapted to determine, for each of a plurality of binarization threshold values, a corresponding edge map representing the location of pixel gradient values exceeding the binarization threshold value with respect to a side of the digital image;

linearity calculation means adapted to compute a measure of linearity for each edge map;

threshold determination means adapted to determine an optimal binarization threshold value based on the computed measures of linearity; and

edge map selection means adapted to select the edge map corresponding to the optimal binarization threshold value

10. The apparatus of claim 9, further comprising preprocessing means adapted to preprocess the digital image to down sample the digital image so as to produce a downsampled digital image having a resolution that is lower than that of the digital image, and to smooth the downsampled digital image so as to reduce noise.

11. The apparatus of claim 9, wherein the threshold determination means are adapted to select a binarization threshold value corresponding to a second minimum in a graph of edge map linearity versus binarization threshold value as the optimal binarization threshold value.

12. The apparatus of claim 9, further comprising page edge detection means adapted to detect the page edge by identifying the location of a substantially linear line in the selected edge map.

13. A computer program product arranged to, when executed on a computer, execute the steps of:

calculating a pixel gradient value for each of a plurality of pixels of a digital image, the pixel gradient value representing the difference of a pixel value with respect to at least one neighbouring pixel;

for each of a plurality of binarization threshold values, determining a corresponding edge map representing the location of pixel gradient values exceeding the binarization threshold value with respect to a side of the digital image;

for each edge map, computing a measure of linearity;

determining an optimal binarization threshold value based on the computed measures of linearity; and

selecting the edge map corresponding to the optimal binarization threshold value.

14. A computer-readable data storage medium comprising the computer program product of claim 13.

15. A system comprising:

data storage means for storing information;

a computer program memory comprising the computer program product of claim 13; and

a data processor having access the computer program memory and the data storage means, the data processor being arranged to execute said computer program product.