Automatic detection and grouping of straight lines in images for personalization

• US 8,805,056 B2
• Filed: 01/24/2011
• Issued: 08/12/2014
• Est. Priority Date: 01/24/2011
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Bala, Raja, Fan, Zhigang, Ding, Hengzhou, Allebach, Jan P., Bouman, Charles A.
• Primary Examiner(s): Park, Chan
• Assistant Examiner(s): RICE, ELISA M
• Application Number:
  US13/011,959
• Publication Number:
  US 20120189190A1
• Time in Patent Office: 1,296 Days
• Field of Search: 382/154, 382/176
• US Class Current: 382/154
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/168 involving transform domain methods
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06T 7/536 from perspective effects, e.g. by using vanishing points

Abstract

As set forth herein, a computer-implemented method is employed to place personalized text into an image. A location within the image is selected where the text is to be placed, and region is grown around the selected location. The 3D geometry of the surface is estimated proximate to the location and sets of parallel straight lines in the image are identified and selected to define a bounding polygon into which text may be inserted. Optionally, a user is permitted to adjust the bounding polygon once it has been automatically generated.

Claims

1. A computer-implemented method for determining planar surface geometry for image personalization comprising:

receiving a two-dimensional (2D) image having a selected location within the image for personalization;

automatically growing a region around the selected location in the 2D image;

automatically estimating parameters required for deriving three-dimensional (3D) planar geometry of the grown region; and

determining the 3D planar geometry of the grown region as a function of the estimated 3D parameters;

wherein estimating parameters for deriving 3D planar geometry of the grown region further comprises;

performing an edge detection procedure to detect straight lines in the grown region and generate an edge map of the grown region, the straight lines corresponding to geometric features in the 3D planar geometry of at least one object in the 2D image;

preprocessing the image to remove spurious straight lines in the edge map; and

grouping remaining straight lines into a first set and a second set of 3D parallel lines, wherein the first set of 3D parallel lines is perpendicular to the second set of 3D parallel lines in 3D space.

2. The method according to claim 1, further comprising:

rendering a personalized text string onto the image at the selected location according to the determined 3D planar geometry.

3. The method according to claim 1, wherein the edge detection is performed using a Canny Edge Detector.

4. The method according to claim 1, wherein detecting the straight lines further comprises:

computing a Hough transform for the edge map;

locating intensity peaks in the Hough transform, the peaks having an intensity that is above a predetermined threshold intensity;

iteratively identifying a highest peak in the Hough transform;

adding a straight line corresponding to the identified peak to the edge map, and removing the identified peak from the Hough transform once the straight line is added to the edge map; and

continuing to iteratively identify remaining peaks having intensities above the predetermined intensity threshold, add corresponding straight lines to the edge map and removing the identified peaks, until all peaks having intensities above the predetermined intensity threshold have been removed from the Hough transform.

5. The method according to claim 1, wherein estimating parameters further comprises:

identifying a first pair of 3D parallel lines from the first set, and a second pair of 3D parallel lines from the second set; and

deriving a first vanishing point for the first pair of 3D parallel lines and a second vanishing point for the second pair of 3D parallel lines.

6. The method according to claim 5, further comprising permitting a user to adjust a position of the lines in the identified first and second pairs of 3D parallel lines.

7. The method of claim 5 wherein the grouping and identifying steps are performed using one or more of the following criteria about plausible planar surface geometry:

the first and second pair of 3D parallel lines result in a valid 3D scene and camera geometry, wherein validity of the 3D scene is evaluated as a function of an angle formed by a center of the image and the first and second vanishing points;

the 3D geometry parameters are drawn from known prior probability distributions;

all identified lines lie on one side of the vanishing line;

convergence of identified lines suggests that they are parallel in 3D.

8. The method of claim 7 wherein all four lines corresponding to both pairs are detected directly from the edge map.

9. The method of claim 8 further comprising:

performing an exhaustive search across all possible parallel line pairs to solve for a first and a second pair of 3D parallel lines that satisfy said criteria; and

if multiple solutions arise, selecting the first and second pair that has the largest sum of line lengths.

10. The method according to claim 7, wherein at least one of the lines from the first and second pair of 3D parallel lines is not detected directly from the edge map and is instead estimated based on one or more of the criteria.

11. The method of claim 1, wherein determining the 3D planar geometry comprises computing the field of view and normal vector from two vanishing points corresponding to the two pairs of 3D parallel lines.

12. A computer-implemented method for defining a bounding polygon in an image for text insertion, comprising:

receiving an image for personalization;

receiving input regarding a user-selected location in the image for text insertion;

growing a region around the selected location;

generating an edge map of the grown region;

detecting straight lines in the edge map;

preprocessing the image to remove spurious straight lines in the edge map;

grouping remaining straight lines into a first set and a second set of 3D parallel lines, wherein the first set of 3D parallel lines is perpendicular to the second set of 3D parallel lines in 3D space;

estimating a 3D geometry of the grown region based on the first and second sets of 3D parallel lines; and

rendering a personalized text string in the grown region according to the estimated 3D geometry.

13. The method of claim 12, wherein the region is grown using a connected-component analysis, and the edge map is generated using a Canny'"'"'s edge detection technique.

14. The method of claim 12, wherein detecting straight lines in the edge map further comprises:

computing a Hough transform for the edge map;

locating intensity peaks in the Hough transform, the peaks having an intensity that is above a predetermined threshold intensity;

iteratively identifying a highest peak in the Hough transform;

adding a straight line corresponding to the identified peak to the edge map, and removing the identified peak from the Hough transform once the straight line is added to the edge map; and

continuing to iteratively identify remaining peaks having intensities above the predetermined intensity threshold, add corresponding straight lines to the edge map, and removing the identified peak from the Hough transform, until all peaks having intensities above the predetermined intensity threshold have been removed from the Hough transform.

15. The method of claim 12, wherein the estimating 3D geometry further comprises:

identifying a first pair of 3D parallel lines in the edge map by determining whether at least two detected straight lines converge on a first vanishing point; and

identifying a second pair of 3D parallel lines in the edge map by determining whether at least two detected straight lines converge on a second vanishing point

wherein the first pair of 3D parallel lines is perpendicular to the second pair of 3D parallel lines in 3D space.

16. The method of claim 15, further comprising:

permitting a user to adjust a position of the lines in the selected pairs of parallel lines.

17. The method according to claim 12, wherein estimating the 3D geometry comprises:

identifying a first pair of 3D parallel lines from the first set, and a second pair of 3D parallel lines from the second set; and

deriving a first vanishing point for the first pair of 3D parallel lines and a second vanishing point for the second pair of 3D parallel lines.

18. The method of claim 17, wherein the grouping and identifying steps further comprise determining that the 3D parallel lines meet one or more criteria related to planar surface geometry the one or more criteria comprising at least one of:

the first and second pair of 3D parallel lines result in a valid 3D scene and camera geometry, wherein validity of the 3D scene is evaluated as a function of an angle formed by a center of the image and the first and second vanishing points;

the 3D geometry parameters are drawn from known prior probability distributions;

all identified lines lie on one side of the vanishing line; and

convergence of identified lines suggests that they are parallel in 3D space.

19. The method of claim 17, wherein all four lines corresponding to both pairs are detected directly from the edge map, and further comprising:

performing an exhaustive search across all possible parallel line pairs to solve for a first and a second pair of 3D parallel lines that satisfy said criteria; and

if multiple solutions arise, selecting the first and second pair that has the largest sum of line lengths.

20. The method according to claim 17, wherein at least one of the lines from the first and second pairs of 3D parallel lines is not detected directly from the edge map and is instead estimated based on one or more of the criteria.

21. The method of claim 12, wherein determining the 3D planar geometry comprises computing a field of view and normal vector from two vanishing points corresponding to the two pairs of 3D parallel lines.