Methods and systems for content-boundary detection

• US 9,547,799 B2
• Filed: 07/17/2008
• Issued: 01/17/2017
• Est. Priority Date: 07/17/2008
• Status: Active Grant

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Chen, Lawrence Shao-hsien, Dolan, John E.
• Primary Examiner(s): Bali, Vikkram
• Assistant Examiner(s): CHEN, XUEMEI G
• Application Number:
  US12/175,386
• Publication Number:
  US 20100014774A1
• Time in Patent Office: 3,106 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06V 10/242 by image rotation, e.g. by 90 degrees
• CPC Class Codes: G06V 10/243 by compensating for image skew or non-uniform image deformations

Abstract

Aspects of the present invention are related to systems and methods for automatically determining the content boundaries in a digital image. A gradient field may be generated using an edge detector, and the gradient field may be thresholded, by magnitude, to retain strong edges. The resulting localized edge positions may be projected onto a first direction and a second direction to form two projection histograms. The projection histograms may be analyzed to determine the boundaries of the image content. Corners of a cropping rectangle may be computed, and the digital image may be cropped according to the content boundaries.

Claims

1. A method for content-boundary detection in a digital image, said method comprising:

determining the location of edges in a first image related to a digital image, thereby producing an edge map;

receiving a skew parameter;

determining a skew vector associated with said skew parameter;

forming a first projection histogram of said edge map in a first projection direction, wherein said first projection direction is related to said skew vector;

forming a second projection histogram of said edge map in a second projection direction, wherein said second projection direction is normal to said first projection direction; and

determining a content boundary associated with said digital image using said first projection histogram and said second projection histogram.

2. The method as described in claim 1 further comprising:

projecting said edge map onto said skew vector; and

projecting said edge map onto a vector normal to said skew vector.

3. The method as described in claim 1, wherein said first image is a low-resolution representation of said digital image.

4. The method as described in claim 1, wherein said first image is a smoothed version of said digital image.

5. The method as described in claim 4, wherein said smoothed version of said digital image is formed by convolving said digital image with a Gaussian filter.

6. The method as described in claim 1, wherein said first image is a smoothed version of a low-resolution representation of said digital image.

7. The method as described in claim 1 further comprising clipping said digital image according to said content boundary.

8. The method as described in claim 1, wherein said determining the location of edges comprises:

determining a first gradient field of said first image in a first direction;

determining a second gradient field of said first image in a second direction;

computing a gradient magnitude from said first gradient field and said second gradient field; and

thresholding said gradient magnitude.

9. The method as described in claim 8, wherein:

said determining a first gradient field comprising convolving said first image with a first edge kernel; and

said determining a second gradient field comprises convolving said first image with a second edge kernel.

10. The method as described in claim 8, wherein said thresholding comprises a threshold based on the mean of said gradient magnitude and an adjustable rejection parameter associated with edge strength.

11. The method as described in claim 1, wherein said determining a content boundary associated with said digital image using said first projection histogram and said second projection histogram comprises:

determining a first coordinate in a first coordinate direction, wherein said first coordinate is associated with the first histogram bin having a non-zero count in said first projection histogram;

determining a second coordinate in said first coordinate direction, wherein said second coordinate is associated with the last histogram bin having a non-zero count in said first projection histogram;

determining a third coordinate in a second coordinate direction, wherein said third coordinate is associated with the first histogram bin having a non-zero count in said second projection histogram;

determining a fourth coordinate in said second coordinate direction, wherein said fourth coordinate is associated with the last histogram bin having a non-zero count in said second projection histogram; and

wherein said content boundary is a bounding rectangle described by the four vertices given by;

said first coordinate and said third coordinate;

said first coordinate and said fourth coordinate;

said second coordinate and said third coordinate; and

said second coordinate and said fourth coordinate.

12. A method for content-boundary detection in a digital image, said method comprising:

partitioning a first image into a plurality of image tiles, said plurality of image tiles comprising a first tile and a second tile;

receiving a skew parameter;

determining a skew vector associated with said skew parameter;

determining the location of edges in said first tile, thereby producing a first edge map;

forming a first first-tile projection histogram of said first edge map in a first projection direction, wherein said first projection direction is related to said skew vector;

forming a second first-tile projection histogram of said first edge map in a second projection direction, wherein said second projection direction is normal to said first projection direction;

determining a first-tile content boundary associated with said first tile using said first first-tile projection histogram and said second first-tile projection histogram;

determining the location of edges in said second tile, thereby producing a second edge map;

forming a first second-tile projection histogram of said second edge map in said first projection direction;

forming a second second-tile projection histogram of said second edge map in said second projection direction;

determining a second-tile content boundary associated with said second tile using said first second-tile projection histogram and said second second-tile projection histogram; and

determining an image-content boundary using said first-tile content boundary and said second-tile content boundary.

13. The method as described in claim 12 further comprising:

projecting said first edge map onto said skew vector; and

projecting said second edge map onto said skew vector.

14. The method as described in claim 12, wherein said first image tile and said second image tile are non-overlapping.

15. The method as described in claim 12, wherein said first image tile and said second image tile are overlapping.

16. The method as described in claim 12, wherein said first image is a low-resolution representation of a digital image.

17. The method as described in claim 12, wherein said first image is a smoothed version of said digital image.

18. The method as described in claim 12, wherein said first image is a smoothed version of a low-resolution representation of said digital image.

19. The method as described in claim 12 further comprising clipping said digital image according to said image-content boundary.

20. The method as described in claim 12, wherein said determining the location of edges in said first tile comprises:

determining a first gradient field of said first tile in a first direction;

determining a second gradient field of said first tile in a second direction;

computing a gradient magnitude from said first gradient field and said second gradient field; and

thresholding said gradient magnitude.

21. The method as described in claim 20, wherein:

said determining a first gradient field comprising convolving said first tile with a first edge kernel; and

said determining a second gradient field comprises convolving said first tile with a second edge kernel.

22. The method as described in claim 20, wherein said thresholding comprises a threshold based on the mean of said gradient magnitude and an adjustable rejection parameter associated with edge strength.

23. The method as described in claim 12, wherein said determining a first-tile content boundary using said first first-tile projection histogram and said second first-tile projection histogram comprises:

determining a first coordinate in a first coordinate direction, wherein said first coordinate is associated with the first histogram bin having a non-zero count in said first first-tile projection histogram;

determining a second coordinate in said first coordinate direction, wherein said second coordinate is associated with the last histogram bin having a non-zero count in said first first-tile projection histogram;

determining a third coordinate in a second coordinate direction, wherein said third coordinate is associated with the first histogram bin having a non-zero count in said second first-tile projection histogram; and

determining a fourth coordinate in said second coordinate direction, wherein said fourth coordinate is associated with the last histogram bin having a non-zero count in said second first-tile projection histogram.

24. The method as described in claim 12, wherein said determining an image-content boundary using said first-tile content boundary and said second-tile content boundary comprises:

comparing a first-tile first coordinate in a first coordinate direction, wherein said first-tile first coordinate is associated with the first histogram bin having a non-zero count in said first first-tile projection histogram, and a second-tile first coordinate in said first coordinate direction, wherein said second-tile first coordinate is associated with the first histogram bin having a non-zero count in said first second-tile projection histogram;

comparing a first-tile second coordinate in said first coordinate direction, wherein said first-tile second coordinate is associated with the last histogram bin having a non-zero count in said first first-tile projection histogram, and a second-tile second coordinate in said first coordinate direction, wherein said second-tile second coordinate is associated with the last histogram bin having a non-zero count in said first second-tile projection histogram;

comparing a first-tile third coordinate in a second coordinate direction, wherein said first-tile third coordinate is associated with the first histogram bin having a non-zero count in said second first-tile projection histogram, and a second-tile third coordinate in said second coordinate direction, wherein said second-tile third coordinate is associated with the first histogram bin having a non-zero count in said second second-tile projection histogram; and

comparing a first-tile fourth coordinate in said second coordinate direction, wherein said first-tile fourth coordinate is associated with the last histogram bin having a non-zero count in said second first-tile projection histogram, and a second-tile fourth coordinate in said second coordinate direction, wherein said second-tile fourth coordinate is associated with the last histogram bin having a non-zero count in said second second-tile projection histogram.

25. A system, encoded on a non-transitory computer-readable medium, for content-boundary detection in a digital image, said system comprising:

an edge extractor for determining the location of edges in a first image related to a digital image, thereby producing an edge map;

a skew parameter receiver for receiving a skew parameter;

a skew vector determiner for determining a skew vector associated with said skew parameter;

a first projection histogram generator for forming a first projection histogram of said edge map in a first projection direction, wherein said first projection direction is related to said skew parameter;

a second projection histogram generator for forming a second projection histogram of said edge map in a second projection direction, wherein said second projection direction is normal to said first projection direction; and

a boundary determiner for determining a content boundary associated with said digital image using said first projection histogram and said second projection histogram.

26. The system as described in claim 25 further comprising:

a first edge-map projector for projecting said edge map onto said skew vector; and

a second edge-map projector for projecting said edge map onto a vector normal to said skew vector.