Multiple image area detection in a digital image

• US 20030095709A1
• Filed: 11/09/2001
• Published: 05/22/2003
• Est. Priority Date: 11/09/2001
• Status: Active Grant

• Current Assignee: ArcSoft, Inc.
• Original Assignee: ArcSoft, Inc.
• Inventors: Zhou, Lingxiang
• Granted Patent: US 6,898,316 B2
• Time in Patent Office: Days
• US Class Current: 382/190
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/20132 Image cropping
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: H04N 1/3872 Repositioning or masking

Abstract

A method for detecting an image area in a digital image includes identifying in the digital image a first image region indicative of a background area and a second image region indicative of the image area, computing gradient values using the pixel values of the digital image, defining a list of strokes based on the gradient values, merging the list of strokes, defining a list of corners using the list of strokes, and defining an image area rectangle delimiting the image area using the list of corners and the list of strokes. The image area rectangle can be used to define a binding box for extracting the image area from the digital image. The method enables the automatic detection of multiple image areas in a digital image. Moreover, the method implements a robust algorithm for image area detection such that even imperfect image areas can be detected without errors.

Claims

1. A method for detecting an image area in a digital image including said image area and a background area, said digital image being represented as a two-dimensional array of pixel values, comprising:

identifying in said digital image a first image region indicative of said background area and a second image region indicative of said image area;

computing gradient values using said pixel values for pixel locations in said digital image associated with a boundary between said first image region and said second image region;

defining a plurality of strokes based on said gradient values, each stroke being a line segment having a start pixel location and an end pixel location, and each stroke being derived from a region of pixel locations having non-zero gradient values of the same sign, wherein pixel locations to a first side of each stroke are in said second image region and pixel locations to a second side of each stroke are in said first image region;

merging said plurality of strokes, wherein a first stroke and a second stroke in said plurality of strokes are merged when said first and second strokes are collinear and a start pixel location of one of said first and second strokes is near an end pixel location of the other one of said first and second strokes;

defining a plurality of corners using said strokes, wherein each corner is a pixel location of an intersection of a third stroke and a fourth stroke, said third stroke and said fourth stroke forming a corner when said third stroke is perpendicular to said fourth stroke, said third and fourth strokes are arranged in a third direction, and a start pixel location of one of said third and fourth strokes is close to an end pixel location of the other one of said third and fourth strokes; and

defining an image area rectangle delimiting said image area using said plurality of corners and said plurality of strokes, wherein said image area rectangle is defined based on one or more corners fitting a predefined corner configuration and one or more strokes associated with said one or more corners, said one or more strokes forming at least a portion of a perimeter of said image area rectangle.

2. The method of claim 1, further comprising:

before said identifying in said digital image said first image region and said second image region, resizing said digital image to a reduced size digital image, said reduced size digital image having a lower resolution than said digital image;

wherein said reduced size digital image is used as said digital image in acts following said act of resizing.

3. The method of claim 2, wherein said digital image has a size of at least 2000×

3000 pixels and said reduced size digital image has a size of 512×

512 pixels or less.

4. The method of claim 2, wherein said resizing comprises averaging an n×

n neighborhood of pixel values at each pixel location.

5. The method of claim 2, wherein said image area rectangle is defined for said reduced sized digital image and said method further comprises:

resizing said image area rectangle to a size equal to the size of said digital image.

6. The method of claim 1, wherein said identifying in said digital image said first image region and said second image region comprises:

(a) selecting a pixel location in said digital image;

(b) determining if a pixel value at a pixel location in said digital image is greater than a threshold value;

(c) if said pixel value is greater than said threshold value, identifying said pixel location as being in said first image region; and

(d) if said pixel value is not greater than said threshold value, identifying said pixel location as being in said second image region.

7. The method of claim 6, further comprising repeating said acts (a) to (d) to identify each pixel location in said digital image as in said first image region or said second image region.

8. The method of claim 6, wherein said threshold value is selected to identify pixel values indicative of a white color as being in said first image region.

9. The method of claim 6, wherein each of said pixel value is a color pixel value comprising pixel values for at least three color components, and said act (b) comprises determining if pixel values for said at least three color components at a pixel location are each greater than said threshold value.

10. The method of claim 1, wherein said computing gradient values using said pixel values comprises:

computing gradient values in a vertical direction for each pixel location except pixel locations at a perimeter of said digital image;

computing gradient values in a horizontal direction for each pixel location except pixel locations at a perimeter of said digital image;

for each pixel location, selecting the larger of said vertical and said horizontal gradient values as a selected gradient value; and

storing said selected gradient value for a pixel location if said pixel location is in said first image region or within one pixel location of said first image region.

11. The method of claim 10, wherein each of said pixel value is a color pixel value comprising pixel values for at least three color components, said computing gradient values in said vertical direction and in said horizontal direction each comprises:

computing gradient values for each of said at least three color components using said color pixel value; and

selecting the largest of said gradient values of said at least three color components as said gradient value for said pixel location.

12. The method of claim 1, wherein when a stroke is viewed from said start pixel location to said end pixel location, said first side of said stroke is a left side and said second side of said stroke is a right side.

13. The method of claim 1, wherein said defining a plurality of strokes comprises:

selecting a first pixel location in said digital image having a non-zero gradient value;

determining a sign of said non-zero gradient value;

tracing a region surrounding said first pixel location for pixels having a non-zero gradient value with the same sign as said sign of said first pixel location;

determining if said region has an area greater than a threshold value;

if said region has an area greater than said threshold value, fitting a straight line through said region; and

defining a start point and an end point of a first stroke using said straight line and said sign of said first pixel location.

14. The method of claim 13, wherein said fitting a straight line through said region uses a linear regression technique and each pixel location in said region is weighted by a corresponding gradient value.

15. The method of claim 13, wherein said tracing a region surrounding said first pixel location comprises tracing pixel locations to the left, the right, the top and the bottom of said first pixel location.

16. The method of claim 1, wherein said merging said plurality of strokes comprises:

selecting said first stroke and said second stroke in said plurality of strokes;

determining if said first stroke and said second stroke are collinear;

if said first stroke and said second stroke are collinear, determining if an end pixel location of said first stroke is close to a start pixel location of said second stroke; and

if said end pixel location of said first stroke is close to said start pixel location of said second stroke, merging said first stroke and said second stroke.

17. The method of claim 16, wherein said merging said first stroke and said second stroke comprises setting said end pixel location of said first stroke to an end pixel location of said second stroke.

18. The method of claim 16, wherein said end pixel location of said first stroke is close to said start pixel location of said second stroke when said end pixel location of said first stroke is within 4 pixels of said start pixel location of said second stroke.

19. The method of claim 16, further comprises:

if said end pixel location of said first stroke is not close to said start pixel location of said second stroke, determining if a start pixel location of said first stroke is close to an end pixel location of said second stroke; and

if said start pixel location of said first stroke is close to said end pixel location of said second stroke, merging said second stroke and said first stroke.

20. The method of claim 19, wherein said merging said second stroke and said first stroke comprises setting said start pixel location of said first stroke to a start pixel location of said second stroke.

21. The method of claim 19, wherein said start pixel location of said first stroke is close to said end pixel location of said second stroke when said start pixel location of said first stroke is within 4 pixels of said end pixel location of said second stroke.

22. The method of claim 16, wherein said determining if said first stroke and said second stroke are collinear comprises:

determining the length of said first stroke and said second stroke;

assigning a stroke A as the longer of said first stroke and said second stroke;

assigning a stroke B as the shorter of aid first stroke and said second stroke;

determining if a first vertical distance from a start pixel location of said stroke B to said stroke A is less than a threshold value;

determining if a second vertical distance from an end pixel location of said stroke B to said stroke A is less than said threshold value; and

if said first and second vertical distances are both less than said threshold value, returning a value indicating said first stroke and said second stroke are collinear.

23. The method of claim 22, wherein said threshold value is 2 pixels.

24. The method of claim 1, wherein in defining a plurality of corners, said third and fourth stroke are arranged in a third direction when said start pixel location and said end pixel location of each of said third and fourth stroke are arranged in a counter-clockwise direction.

25. The method of claim 1, wherein in defining a plurality of corners, said start pixel location of one of said third and fourth strokes is close to said end pixel location of the other one of said third and fourth strokes is determined by computing a corner likelihood value.

26. The method of claim 25, wherein said computing a corner likelihood value comprises:

computing a third distance being a vertical distance from said start pixel location of said third stroke to said fourth stroke;

computing a fourth distance being a vertical distance from said end pixel location of said third stroke to said fourth stroke;

computing a third distance being a vertical distance from said start pixel location of said fourth stroke to said third stroke;

computing a fourth distance being a vertical distance from said end pixel location of said fourth stroke to said third stroke;

computing a third likelihood value using the equation;

1—

(fourth distance/third distance);

computing a fourth likelihood value using the equation;

1—

(third distance/fourth distance); and

selecting the smaller of said third likelihood value and said fourth likelihood value as said corner likelihood value.

27. The method of claim 26, further comprising:

comparing said corner likelihood value to a threshold value;

wherein said start pixel location of one of said third and fourth strokes is close to said end pixel location of the other one of said third and fourth strokes when said corner likelihood value is greater than said threshold value.

28. The method of claim 1, wherein said image area is one of a plurality of image areas and said defining an image area rectangle comprises defining a plurality of image area rectangles, each image area rectangle delimiting one of said plurality of image areas.

29. The method of claim 1, wherein said predefined corner configuration is one of a plurality of predefined corner configurations, said plurality of predefined corner configurations comprising a one-corner configuration, two-corner configurations, three-corner configurations and a four-corner configuration.

30. The method of claim 29, wherein said defining an image area rectangle comprises:

selecting a first corner from said plurality of corners;

initiating a depth-first search of corners in said plurality of corners;

generating a one-corner hypothesis based on said one-corner configuration;

generating a two-corner hypothesis based on said two-corner configurations;

generating a three-corner hypothesis based on said three-corner configurations;

generating a four-corner hypothesis based on said four-corner configuration;

computing a likelihood value for each of said one-corner hypothesis, said two-corner hypothesis, said three-corner hypothesis, and said four-corner hypothesis;

selecting an hypothesis with the largest likelihood value;

determining if said likelihood value is greater than a threshold value; and

if said likelihood value is greater than a threshold value, defining said image area rectangle using said selected hypothesis.

31. The method of claim 30, wherein said computing a likelihood value for each of said one-corner hypothesis, said two-corner hypothesis, said three-corner hypothesis, and said four-corner hypothesis comprises:

determining a set of strokes from said plurality of strokes forming a perimeter of each of said hypothesis;

determining a total length of said set of strokes; and

setting said likelihood value equal to said total length of said set of strokes.

32. The method of claim 30, further comprising:

if said likelihood value is greater than a threshold value, removing strokes and corners forming a perimeter of said image area rectangle and strokes and corners within said image area rectangle.