Method and apparatus for adaptive stripe based patch matching for depth estimation

• US 6,393,142 B1
• Filed: 04/22/1998
• Issued: 05/21/2002
• Est. Priority Date: 04/22/1998
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Wang, Yao, Swain, Cassandra Turner
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Dang, Duy M.
• Application Number:
  US09/064,058
• Time in Patent Office: 1,490 Days
• Field of Search: 382/154, 382/158, 382/173, 382/156, 382/157, 382/199, 382/174, 382/128, 382/108, 382/109, 382/243, 382/285, 716/19, 716/20
• US Class Current: 382/154
• CPC Class Codes: G06T 7/50 Depth or shape recovery
• CPC Class Codes: G06V 10/10 Image acquisition document image scanning and transmission H04N1/00; control of digital cameras H04N23/60
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects

Abstract

A method and apparatus provide a technique for generating a mesh based on an image view. The mesh includes a plurality of trapezoidal patches which can be used in a comparison operation with regard to a second co-planar image view. The comparison operation extracts disparity information between the patches of the respective images and these disparities can be used to calculate depth estimations for objects within the image of use.

Claims

1. A method for generating a mesh representative of an image, the method comprising the steps of:

dividing the image into a plurality of horizontal stripe regions, said step of dividing including;

calculating a power value for each of the plurality of horizontal lines of the image;

selecting M (where M is an integer ≧

1) lines of the plurality of horizontal lines employing selection criteria that includes reference to the respective power values of the lines; and

for each horizontal stripe region,

selecting at least one line segment extending from a top boundary of the region to a bottom boundary of the region from a plurality of line segments,

wherein said selection is made with reference to a relative power of the plurality of line segments.

2. The method of claim 1 wherein said selection criteria further include a predetermined minimum width of a horizontal stripe region.

3. The method of claim 1 further comprising the step of determining a reference line for each horizontal stripe region and wherein said step of calculating is performed with respect to said reference line.

4. The method of claim 3 wherein said reference line comprises a center line of the region.

5. The method of claim 3 further comprising the steps of,

for each of a plurality of points along said reference line, deriving a plurality of possible line segments through the point;

for each line segment estimating a power value; and

making said selection of at least one line segment with reference to said power values.

6. The method of claim 5 wherein said selection if at least one line segment is made also with reference to segment separation criteria.

7. In a process for performing depth estimation, a method for generating a patch pattern in relation to an image to be analyzed, the method comprising the steps of:

determining horizontal edges for a plurality of horizontal stripes corresponding to the image, said step of determining including;

determining a power value for each horizontal row of pixels, and

selecting a row of pixels as a horizontal edge based on a power value of the row and a distance from an adjacent horizontal edge; and

selecting one or more line segments between the horizontal edges of a particular region so as to divide said particular region into a plurality of trapezoidal patches.

8. The method of claim 7 wherein said step of selecting one or more line segments in a particular region comprises the sub-steps of:

determining a reference line in said particular region;

for each of a plurality of points along said reference line, deriving a plurality of possible line segments through the point;

for each line segment estimating a power value; and

making a selection of a line segment, with reference to said power values.

9. The method of claim 8 wherein said selection is made also with reference to segment separation criteria.

10. In a process for performing depth estimation, a method for generating a patch pattern in relation to an image to be analyzed, the method comprising the steps of:

determining horizontal edges for a plurality of horizontal stripes corresponding to the image; and

selecting one or more line segments between the horizontal edges of a particular region so as to divide said particular region into a plurality of trapezoidal patches, wherein said step of selecting includes;

determining a reference line in said particular region;

for each of a plurality of points along said reference line, deriving a plurality of possible line segments through the point;

for each line segment estimating a power value; and

making a selection of a line segment with reference to said power values.

11. The method of claim 10 wherein said selection is made also with reference to segment separation criteria.

12. A method for performing depth estimation of an object in an image field, the method comprising the steps of:

generating a first image of the object from a first perspective;

dividing the first image into mesh representation, the step of dividing including the sub-steps of;

dividing the image into a plurality of horizontal stripe regions, and

for each stripe region selecting at least one line segment extending between horizontal edges of the stripe region in accordance with a power value associated with said at least one line segment;

generating a second image of the object from a second perspective;

comparing said second image and said first image to determine portions of aid second image corresponding to patches of said mesh representation of said first mage;

determining a disparity of corresponding portions of the second images and he patches of the mesh representation that relate to the object;

estimating depth based on determined disparity and information relating to said first perspective and said second perspective.

13. The method of claim 12 wherein said first image and said second image are processed as if they are co-planar images.

14. The method of claim 12 wherein said step of dividing the image comprises the sub-steps of:

calculating a power value for each of a plurality of horizontal lines of the image;

selecting M (where M is an integer ≧

1) lines of said plurality of horizontal lines employing selection criteria that includes reference to the respective power values of the lines.

15. The method of claim 12 wherein said step of selecting at least one line segment in a stripe region comprises the sub-steps of:

determining a reference line in said particular region;

for each of a plurality of points along said reference line, deriving a plurality of possible line segments through the point;

for each line segment estimating a power value; and

making a selection of a line segment with reference to said power values.

16. The method of claim 15 wherein said step of dividing the image comprises the sub-steps of:

calculating a power value for each of a plurality of horizontal lines of the image;

selecting M (where M is an integer ≧

1) lines of said plurality of horizontal lines employing selection criteria that includes reference to the respective power values of the lines.

17. A method for comparing co-planar images of a field of view to estimate depth of at least one object in the field of view, the method comprising the steps of:

generating a mesh representation of a first one of the co-planar images, said mesh constituting a plurality of trapezoidal regions having parallel horizontal edges and having boundaries defined in relation to relative powers of regions of the first image;

analyzing a second one of said co-planar images with reference to the generated mesh to find regions in said second one of said co-planar images corresponding to trapezoidal regions in said mesh; and

detecting a disparity between a trapezoidal region and a corresponding region in the second one of said co-planar images.

18. The method of claim 17 comprising the further step of determining a depth of an object using detected disparity related to the regions of the first and second co-planar images in which the object appears.

19. A method for detecting a position of an object with respect to a reference position, the method comprising the steps of:

detecting a pair of co-planar images of an image field including the object;

dividing a first one of the pair of co-planar images into a mesh representation constituting a plurality of trapezoidal regions having parallel horizontal edges and having boundaries defined in relation to relative powers of regions of the first image; and

comparing a second one of said pair of co-planar images to aid mesh representation, said step of comparing comprising the sub-steps of,

detecting a region in said second image that includes the object and which corresponds to a trapezoidal region in the mesh that includes the object;

detecting a disparity between the detected region and its corresponding trapezoidal region; and

determining a depth of the object having the detected disparity.

20. A method for obtaining depth estimation of an object in a first image and a second image, the method comprising the steps of:

dividing the first image into a plurality of horizontal stripe regions;

for each horizontal stripe region,

selecting at least one line segment extending from a top boundary of the region to a bottom boundary of the region from a plurality of line segments,

wherein said selection is made with reference to a relative power of the plurality of line segments; and

obtaining depth estimation for the object based on the horizontal stripe regions and the at least one line segment.