Image processing methods and systems

• US 20050169531A1
• Filed: 01/30/2004
• Published: 08/04/2005
• Est. Priority Date: 01/30/2004
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Fan, Jian
• Granted Patent: US 7,672,507 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06T 7/181 involving edge growing; involving edge linking

Abstract

Systems and methods according to the present invention provide techniques to reliably detect edges, lines and quadrilaterals, especially those with low local contrast, in color images. Edges can be detected using a color gradient operator is based on color distance with a non-linear weight determined by the consistency of local gradient orientations, thereby significantly improving the signal/noise ratio. In detecting lines, a variant of the Gradient Weighted Hough Transform can be used employing both the edge strength and orientation. Multiple non-overlapping quadrilaterals can be detected using a process which includes quality metrics (for both individual quadrilaterals and for a set of non-overlapping quadrilaterals) and a graph-searching method.

Claims

10. A computer-readable medium containing a program that performs the steps of:

determining, for each of a plurality of different color channels, a channel gradient and a weighting factor associated with each color channel in an image;

setting, for each pixel, a color gradient equal to one of said channel gradients having a maximum weighted magnitude based on said weighting factors;

preliminarily identifying edges in said image by using said color gradients; and

confirming said edges using at least one threshold.

11. The computer-readable medium of claim 10, wherein said step of determining, for each of a plurality of different color channels, a channel gradient and a weighting factor associated with each color channel in an image further comprises the step of:

using, as said weighting factor, a non-linear weighting factor.

12. The computer-readable medium of claim 11, wherein said non-linear weighting factor is computed as:

w_i,j^c=λ

e<sup>−

σ

c2/μ</sup>

, wherein w_i,j^c refers to said non-linear weighting factor associated with pixel (i,j) in color channel c, λ and

μ

are constants and σ

is a standard deviation of channel gradient orientations within an L-by-L window centered at (i,j) and with magnitude M_i,j^c over a threshold t=kM_i,j^c.

13. The computer-readable medium of claim 10, wherein said step of confirming said edges using at least one threshold further comprises the steps of:

identifying a first pixel having a color gradient magnitude which exceeds a first threshold; and

confirming, as edge pixels, pixels which neighbor said first pixel, if said neighboring pixels have a color gradient magnitude which exceeds a second threshold and if said neighboring pixels have an orientation difference which is less than an orientation threshold.

14. An image processing system comprising:

an image capture device for capturing an image; and

a processor, connected to said image capture device, for determining, for each of a plurality of different color channels, a channel gradient and a weighting factor associated with each color channel in an image;

setting, for each pixel, a color gradient equal to one of said channel gradients having a maximum weighted magnitude based on said weighting factors;

preliminarily identifying edges in said image by using said color gradients; and

confirming said edges using at least one threshold.

15. The image processing step of claim 14, wherein said processor employs, as said weighting factor, a non-linear weighting factor.

16. The image processing system of claim 15, wherein said non-linear weighting factor is computed as:

w_i,j^c=λ

e<sup>−

σ

2/μ</sup>

, wherein w_i,j^c refers to said non-linear weighting factor associated with pixel (i,j) in color channel c, λ and

μ

are constants and σ

is a standard deviation of channel gradient orientations within an L-by-L window centered at (i,j) and with magnitude M_i,j^c over a threshold t=kM_i,j^c.

17. The image processing system of claim 14, wherein said processor confirms said edges by identifying a first pixel having a color gradient magnitude which exceeds a first threshold;

and confirming, as edge pixels, pixels which neighbor said first pixel, if said neighboring pixels have a color gradient magnitude which exceeds a second threshold and if said neighboring pixels have an orientation difference which is less than an orientation threshold.

18. An image processing system comprising:

means for capturing an image; and

means, connected to said image capture device, for determining, for each of a plurality of different color channels, a channel gradient and a weighting factor associated with each color channel in an image;

setting, for each pixel, a color gradient equal to one of said channel gradients having a maximum weighted magnitude based on said weighting factors;

preliminarily identifying edges in said image by using said color gradients; and

confirming said edges using at least one threshold.

19. A method for image processing comprising the steps of:

identifying a first plurality of candidate shapes in an image based on line data;

screening said first plurality of candidate shapes against predetermined criteria to generate a second plurality of candidate shapes;

determining at least one confidence level for each of said second plurality of candidate shapes and;

eliminating those of said second plurality of candidate shapes wherein said at least one confidence level is less than a predetermined value to generate a set of confirmed shapes.

20. The method of claim 19, wherein said first and second plurality of candidate shapes are candidate quadrilaterals.

21. The method of claim 19, wherein said predetermined criteria include at least one of:

minimum vertex angle values, maximum vertex angle values, maximum distance of a vertext outside image boundaries, minimum side length, minimum shape area, and minimum overlap between a detected line segment and a corresponding side of a shape.

22. The method of claim 19, wherein said step of determining at least one confidence level for each of said second plurality of candidate shapes further comprises the step of:

determining confidence levels for sides and corners of each candidate shape and using said side and corner confidence levels to determine said shape confidence levels.

23. The method of claim 19, wherein said predetermined value is one of:

a predetermined side confidence level, a predetermined corner confidence value and a predetermined shape confidence value.

24. The method of claim 19, further comprising the steps of:

identifying a plurality of sets of mutually non-overlapping shapes from said set of confirmed shapes; and

selecting, from said plurality of sets of mutually non-overlapping shapes, a set of mutually non-overlapping shapes having a largest total effective area.

25. A computer-readable medium containing a program that performs the steps of:

identifying a first plurality of candidate shapes in an image based on line data;

screening said first plurality of candidate shapes against predetermined criteria to generate a second plurality of candidate shapes;

determining at least one confidence level for each of said second plurality of candidate shapes and;

eliminating those of said second plurality of candidate shapes wherein said at least one confidence level is less than a predetermined value to generate a set of confirmed shapes.

26. The computer-readable medium claim 25, wherein said first and second plurality of candidate shapes are candidate quadrilaterals.

27. The computer-readable medium of claim 25, wherein said predetermined criteria include at least one of:

minimum vertex angle values, maximum vertex angle values, maximum distance of a vertex outside image boundaries, minimum side length, minimum shape area, and minimum overlap between a detected line segment and a corresponding side of a shape.

28. The computer-readable medium of claim 25, wherein said step of determining at least one confidence level for each of said second plurality of candidate shapes further comprises the step of:

determining confidence levels for sides and corners of each candidate shape and using said side and corner confidence levels to determine said shape confidence levels.

29. The computer-readable medium of claim 25, wherein said predetermined value is one of:

a predetermined side confidence level, a predetermined corner confidence value and a predetermined shape confidence value.

30. The computer-readable medium of claim 25, further comprising the steps of:

identifying a plurality of sets of mutually non-overlapping shapes from said set of confirmed shapes; and

selecting, from said plurality of sets of mutually non-overlapping shapes, a set of mutually non-overlapping shapes having a largest total effective area.

31. An image processing system comprising:

an image capture device for capturing an image; and

a processor for identifying a first plurality of candidate shapes in said image based on line data;

screening said first plurality of candidate shapes against predetermined criteria to generate a second plurality of candidate shapes;

determining at least one confidence level for each of said second plurality of candidate shapes and;

eliminating those of said second plurality of candidate shapes wherein said at least one confidence level is less than a predetermined value to generate a set of confirmed shapes.

1. A method for image processing comprising the steps of:

determining, for each of a plurality of different color channels, a channel gradient and a weighting factor associated with each color channel in an image;

setting, for each pixel, a color gradient equal to one of said channel gradients having a maximum weighted magnitude based on said weighting factors;

preliminarily identifying edges in said image using said color gradients; and

confirming said edges using at least one threshold.

2. The method of claim 1, wherein said step of determining, for each of a plurality of different color channels, a channel gradient and a weighting factor associated with each color channel in an image further comprises the step of:

using, as said weighting factor, a non-linear weighting factor.

3. The method of claim 2, wherein said non-linear weighting factor is computed as:

w_i,j^c=λ

e<sup>−

σ

2/μ</sup>

, wherein w_i,j^c refers to said non-linear weighting factor associated with pixel (i,j) in color channel c, λ and

μ

are constants and σ

is a standard deviation of channel gradient orientations within an L-by-L window centered at (i,j) and with magnitude M_i,j^c over a threshold t=kM_i,j^c.

4. The method of claim 1, wherein said plurality of different color channels further comprise a red channel (r), a green channel (g) and a blue channel (b).

5. The method of claim 1, wherein said step of confirming said edges using at least one threshold further comprises the steps of:

identifying a first pixel having a color gradient magnitude which exceeds a first threshold; and

confirming, as edge pixels, pixels which neighbor said first pixel, if said neighboring pixels have a color gradient magnitude which exceeds a second threshold and if said neighboring pixels have an orientation difference which is less than an orientation threshold.

6. The method of claim 1, further comprising the step of:

detecting, based upon said confirmed edges, lines within said image.

7. The method of claim 6, wherein said step of detecting lines within said image further comprises the step of:

computing a Gradient Weighted Hough Transform based on, among other things, edge strength and orientation.

8. The method of claim 6, further comprising the step of:

identifying quadrilaterals within said image using said detected lines.

9. The method of claim 8, further comprising the step of:

selecting a set of mutally non-overlapping quadrilaterals from said identified quadrilaterals.

32. The system of claim 31, wherein said first and second plurality of candidate shapes are candidate quadrilaterals.

33. The system of claim 31, wherein said processor determines confidence levels for sides and corners of each candidate shape and uses said side and corner confidence levels to determine said shape confidence levels.

35. The system of claim 31, wherein said predetermined value is one of:

a predetermined side confidence level, a predetermined corner confidence value and a predetermined shape confidence value.

36. The system of claim 31, wherein said processor identifies a plurality of sets of mutually non-overlapping shapes from said set of confirmed shapes;

and selects, from said plurality of sets of mutually non-overlapping shapes, a set of mutually non-overlapping shapes having a largest total effective area.

32-1. The system of claim 31, wherein said predetermined criteria include at least one of:

minimum vertex angle values, maximum vertex angle values, maximum distance of a vertext outside image boundaries, minimum side length, minimum shape area, and minimum overlap between a detected line segment and a corresponding side of a shape.

37. A system for image processing comprising:

means for identifying a first plurality of candidate shapes in an image based on line data;

means for screening said first plurality of candidate shapes against predetermined criteria to generate a second plurality of candidate shapes;

means for determining at least one confidence level for each of said second plurality of candidate shapes and;

means for eliminating those of said second plurality of candidate shapes wherein said at least one confidence level is less than a predetermined value.