Estimating 3D structure from a 2D image

• US 8,611,694 B2
• Filed: 12/16/2009
• Issued: 12/17/2013
• Est. Priority Date: 12/16/2009
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kogan, Hadas, Maurer, Ron, Keshet, Renato
• Primary Examiner(s): Kassa, Yosef
• Application Number:
  US13/259,253
• Publication Number:
  US 20120070101A1
• Time in Patent Office: 1,462 Days
• Field of Search: 382/154, 382/266, 382/274, 382/275, 382/278, 358/1.2, 358/3.26, 358/3.27, 358/463
• US Class Current: 382/281
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 7/536 from perspective effects, e.g. by using vanishing points

Abstract

A method for estimating three-dimensional structure from a two-dimensional image (502) includes obtaining first and second vanishing points (120, 122); comparing image patches (202) along first and second virtual lines (204, 208) extending from the first and second vanishing points (120, 122), respectively, and through a pixel; generating values for each of the first and second virtual lines (204, 208) based on the comparison of the image patches (202); accumulating the values for each the pixel in the two-dimensional image (502); and determining a corner pixel (106) based on a highest of the accumulated values.

Claims

1. A method for estimating three-dimensional structure from a two-dimensional image (502), comprising:

providing a computer processor configured to process images, said computer processor capable of performing the method comprising;

obtaining first and second vanishing points (120, 122);

comparing image patches (202) along first and second virtual lines (204, 208) extending from said first and second vanishing points (120, 122), respectively, and through a pixel;

generating values for each of said first and second virtual lines (204, 208) based on said comparison of said image patches (202);

accumulating said values for each said pixel in said two-dimensional image (502); and

determining a corner point (106) based on a highest of said accumulated values.

2. The method of claim 1, in which determining said corner point (106) comprises:

generating first and second Hough transform maps (220) from said accumulated values for said first and second vanishing points (120, 122);

combining said first and second Hough transform maps through bitwise multiplication to produce a probability map (230),

in which at least a first corner point (106) is identified from a first peak (246) in a probability profile (240) of said probability map.

3. The method of claim 2, in which a second corner point (108) is identified from a second peak (246) in said probability profile (240).

4. The method of claim 2, further comprising identifying said first peak (246) by fitting a line that passes through a vertical vanishing point and comprises high accumulated values in said probability map (230), such that said line passing through said vertical vanishing point also passes through said corner point (106).

5. The method of claim 2, in which all corner points are determined by selecting peaks (246) in said probability profile (240) above a desired threshold value that is determined heuristically from said two-dimensional image (502).

6. The method of claim 1, in which said two-dimensional image (502) is a man-made scene.

7. The method of claim 1, in which said method is a semi-automated method, such that said vanishing points (120, 122) are entered by a user, and all corner points (106, 108) are then automatically identified from said two-dimensional image (502).

8. The method of claim 1, in which said method is a fully automated method, such that said vanishing points (120, 122) and all corner points (106, 108) are automatically identified from said two-dimensional image (502) without any additional user input.

9. The method of claim 1, further comprising calculating a projection matrix that maps two-dimensional image points to a three-dimensional structure, and allowing a user to manipulate objects within said produced three-dimensional image.

10. A method for calculating three-dimensional vanishing points from a two-dimensional image (502), comprising:

providing a computer processor configured to process images, said computer processor capable of performing the method comprising;

obtaining first and second corner points (106, 108);

comparing image patches (202) along first and second virtual lines extending from said first and second corner points (106, 108), respectively, and through a candidate vanishing point;

generating values for each of said first and second virtual lines based on said comparison of said image patches (202);

accumulating said values for each said candidate vanishing point (120) in said two-dimensional image; and

determining a vanishing point (120) based on a highest of said accumulated values.

11. The method of claim 10, in which said first and second corner points (106, 108) are obtained by a user marking said first and second corners (106, 108) in said two-dimensional image (502).

12. The method of claim 10, in which determining said vanishing point (120) comprises:

generating first and second Hough transform maps (220) from said accumulated values for said first and second corner points (106, 108);

combining said first and second Hough transform maps (220) through bitwise multiplication to produce a probability map (230),

in which at least a first vanishing point (120) is identified as a first peak (246) in a probability profile (240) of said probability map (230).

13. The method of claim 12, in which a second vanishing point (122) is identified as a second peak (246) in said probability profile (240).

14. The method of claim 12, in which all vanishing points (120, 122) are determined by selecting peaks (246) in said probability profile (240) above a desired threshold value.

15. A computer readable storage medium having stored thereon instructions for causing a processor to execute a method for calculating three-dimensional image characteristics (106) from a two-dimensional image (502), said method comprising:

obtaining a set of first three-dimensional characteristic points (120, 122) from said two-dimensional image (502);

comparing image patches (202) along first and second virtual lines (204, 208) extending from said set of first three-dimensional characteristic points (120, 122), respectively, and through a candidate second three-dimensional characteristic point;

generating values for each of said first and second virtual lines (204, 208) based on said comparison of said image patches (202);

accumulating said values for each said candidate second three-dimensional characteristic point; and

determining an actual second three-dimensional characteristic point (106) based on a highest of said accumulated values.