Granted Patent B2

US 8,467,606 · App. 13/217,376 · Granted Jun 18, 2013

Abstract

Claims (52)

1. A method for segmenting a composite image containing a plurality of individual images, comprising:

receiving digital image data representing the composite image;

using a data processor to locate line segments corresponding to edges in the composite image;

defining a plurality of candidate rectangles by identifying sets of four line segments having a first pair of line segments that are parallel to within a predefined tolerance and a second pair of line segments that are perpendicular to the first pair of line segments to within a predefined tolerance;

identifying image regions that are more than a predefined isolation distance from any of the line segments or that are more than a predefined isolation distance from the any of the candidate rectangles;

identifying a set of enclosing rectangles from among the candidate rectangles for each of the identified image regions;

selecting a rectangle for each of the identified image regions from the corresponding set of enclosing rectangles by applying geometric constraints;

forming a plurality of sub-images from the composite image by extracting the digital image data corresponding to the selected rectangles; and

storing the sub-images in a processor-accessible memory.

2. The method of claim 1 wherein the composite image is subdivided into a plurality of image tiles and wherein the line segments are located within the image tiles.

3. The method of claim 2 further including combining short line segments having slopes and intercepts that are equal to within a predefined tolerance to form combined line segments.

4. The method of claim 3 wherein the line segments that are combined to form a particular combined line segment are separated by gaps smaller than a predefined gap tolerance.

5. The method of claim 4 wherein the predefined gap tolerance is less than or equal to the size of two image tiles.

6. The method of claim 1 further including discarding any line segments having lengths shorter than a predefined minimum length.

7. The method of claim 1 further including iteratively applying a combining step that combines short line segments having slopes and intercepts that are equal to within a predefined tolerance to form combined line segments and a discarding step that discards any line segments having lengths shorter than a predefined minimum length.

8. The method of claim 1 wherein the candidate line segments are located by applying a Hough transform to the digital image data within an image tile to determine a line segment slope and an intercept.

9. The method of claim 1 wherein the candidate line segments are located by applying a K-means classifier to the digital image data within an image tile to determine a line segment slope and an intercept.

10. The method of claim 1 wherein the sets of four combined line segments for the candidate rectangles are selected such that first pair of line segments is horizontal to within a predefined tolerance and the second pair of line segments is vertical to within a predefined tolerance.

11. The method of claim 1 wherein the isolation distance is between ¼ inch and 1 inch.

12. The method of claim 1 wherein the image regions are identified by:

computing the distances between the combined line segments and a regular lattice of grid points to determine a set of isolated points that are more than the predefined isolation distance from any of the combined line segments; and

grouping isolated points that are closer than a predefined group distance to define the image regions.

13. The method of claim 1 wherein the set of enclosing rectangles for a particular identified image region is identified by:

determining a centroid for the particular identified image region; and

identifying a set of enclosing rectangles from among the candidate rectangles that enclose the centroid.

14. The method of claim 1 wherein the geometric constraints include a minimum size constraint, a minimum area constraint, edge over-extension constraint, an edge-coverage constraint, an aspect ratio constraint or an edge cut constraint.

15. The method of claim 1 wherein if two or more of the selected rectangles overlap, one or more of the overlapping selected rectangles are eliminated by applying additional geometric constraints to form a non-overlapping set of selected rectangles.

16. The method of claim 1 wherein the sub-images correspond to the individual images in the composite image.

17. The method of claim 1 wherein the composite image is a scan of a hardcopy original.

18. The method of claim 17 wherein the hardcopy original is a photographic album page, a scrapbook page, a photo collage, a printed publication or a collection of individual images arranged on a scanner platen.

19. The method of claim 1 wherein the composite image is a digitally created composite image.

20. The method of claim 1 wherein the individual images include photographic images, artwork or computer generated images.

21. A computer program product for segmenting a composite image containing a plurality of individual images comprising a non-transitory tangible computer readable storage medium storing an executable software application for causing a data processing system to perform the steps of:

receiving digital image data representing the composite image;

using a data processor to locate line segments corresponding to edges in the composite image;

defining a plurality of candidate rectangles by identifying sets of four line segments having a first pair of line segments that are parallel to within a predefined tolerance and a second pair of line segments that are perpendicular to the first pair of line segments to within a predefined tolerance;

identifying image regions that are more than a predefined isolation distance from any of the line segments;

identifying a set of enclosing rectangles from among the candidate rectangles for each of the identified image regions;

selecting a rectangle for each of the identified image regions from the corresponding set of enclosing rectangles by applying geometric constraints;

forming a plurality of sub-images from the composite image by extracting the digital image data corresponding to the selected rectangles; and

storing the sub-images in a processor-accessible memory.

22. A system comprising:

a data processing system; and

a memory system communicatively connected to the data processing system and storing instructions configured to cause the data processing system to implement a method for segmenting a composite image containing a plurality of individual images, wherein the method comprises:

receiving digital image data representing the composite image;

using a data processor to locate line segments corresponding to edges in the composite image;

defining a plurality of candidate rectangles by identifying sets of four line segments having a first pair of line segments that are parallel to within a predefined tolerance and a second pair of line segments that are perpendicular to the first pair of line segments to within a predefined tolerance;

identifying image regions that are more than a predefined isolation distance from any of the line segments;

identifying a set of enclosing rectangles from among the candidate rectangles for each of the identified image regions;

selecting a rectangle for each of the identified image regions from the corresponding set of enclosing rectangles by applying geometric constraints;

forming a plurality of sub-images from the composite image by extracting the digital image data corresponding to the selected rectangles; and

storing the sub-images in a processor-accessible memory.

Assignments (12)