Plane detection and tracking for structure from motion

• US 9,153,025 B2
• Filed: 07/17/2012
• Issued: 10/06/2015
• Est. Priority Date: 08/19/2011
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Jin, Hailin, Zhou, Zihan
• Primary Examiner(s): Le, Vu
• Assistant Examiner(s): BEG, SAMAH A
• Application Number:
  US13/551,603
• Publication Number:
  US 20130044913A1
• Time in Patent Office: 1,176 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06T 7/174 involving the use of two or more images
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/80 Analysis of captured images to determine intrinsic or extrinsic camera parameters, i.e. camera calibration
• CPC Class Codes: H04N 13/20 Image signal generators

Abstract

Plane detection and tracking algorithms are described that may take point trajectories as input and provide as output a set of inter-image homographies. The inter-image homographies may, for example, be used to generate estimates for 3D camera motion, camera intrinsic parameters, and plane normals using a plane-based self-calibration algorithm. A plane detection and tracking algorithm may obtain a set of point trajectories for a set of images (e.g., a video sequence, or a set of still photographs). A 2D plane may be detected from the trajectories, and trajectories that follow the 2D plane through the images may be identified. The identified trajectories may be used to compute a set of inter-image homographies for the images as output.

Claims

1. A method, comprising:

generating, by one or more computing devices, a set of inter-image homographies for an image sequence comprising a plurality of frames, said generating comprising;

determining a plurality of point trajectories that traverse an initial frame pair;

determining a subset of the plurality of point trajectories that traverse the initial frame pair, the subset of the plurality of point trajectories that traverse the initial frame pair corresponding to points defining a two-dimensional (2D) plane;

estimating an inter-image homography for the initial frame pair according to the subset of the plurality of point trajectories that traverse the initial frame pair; and

for each of one or more subsequent frame pairs, perform operations comprising;

adding one or more inlier points whose trajectories correspond to trajectories of a subset of points tracked through a previous frame pair to create a plurality of point trajectories that traverse a current frame pair, the plurality of point trajectories that traverse the current frame pair corresponding to points defining the plane;

determining a new subset of points tracked through the current frame pair from the plurality of point trajectories that traverse the current frame pair; and

estimating an inter-image homography for the subsequent frame pair according to trajectories of the new subset of points tracked through the subsequent frame pair.

2. The method as recited in claim 1, wherein the subsequent frame pair includes one frame that is also in the previous frame pair.

3. The method as recited in claim 1, further comprising:

iteratively performing said generating to generate a plurality of sets of inter-image homographies for the image sequence; and

selecting a set of inter-image homographies that has a largest total count of inlier points.

4. The method as recited in claim 1, further comprising, at the current frame pair, terminating said generating upon determining that a count of inlier points at the current frame pair is below a threshold.

5. The method as recited in claim 1, wherein estimating the inter-image homography for the subsequent frame pair comprises:

selecting a plurality of subsets of points tracked through the previous frame pair, adding inlier points to each of the plurality of subsets of points tracked through the previous frame pair to create a plurality of sets of points tracked through the current frame pair, selecting a plurality of new subsets of the plurality of sets of points that traverse the current frame pair, estimating a plurality of inter-image homographies for the subsequent frame pair based on tracking the plurality of new subsets of the plurality of sets of points that traverse the subsequent frame pair; and

selecting, from the plurality of inter-image homographies for the subsequent frame pair, an inter-image homography for the subsequent frame pair that has tracked a largest count of inlier points.

6. The method as recited in claim 1, further comprising:

performing said generating for two or more subsets of the plurality of frames in the image sequence to generate two or more sets of inter-image homographies for the image sequence, wherein a different plane is identified and tracked in at least two of the subsets of the plurality of frames; and

concatenating the two or more sets of inter-image homographies to generate a single combined set of inter-image homographies for the image sequence.

7. The method as recited in claim 1, further comprising generating three-dimensional (3D) structure and motion information for the image sequence according to the set of inter-image homographies for the image sequence.

8. The method as recited in claim 1, wherein said generating further comprises:

creating a projective reconstruction for the image sequence by combining all of the inter-image homographies together.

9. The method as recited in claim 8, wherein said generating further comprises, at the subsequent frame pair, subsequent to adding the inter-image homography and the inliers for the respective frame pair to the projective reconstruction:

globally optimizing the projective reconstruction;

identifying and removing outliers from the projective reconstruction, wherein an outlier is a point trajectory that does not correspond to the plane in at least one frame in the projective reconstruction;

identifying and adding inliers to the projective reconstruction; and

if a count of inliers added to the projective reconstruction is greater than a threshold, globally optimizing the projective reconstruction.

10. The method as recited in claim 1, wherein the new subset of points tracked through the current frame pair is determined based on a RANSAC algorithm.

11. A system, comprising:

one or more processors; and

a memory comprising program instructions, the program instructions being executable by at least one of the one or more processors to generate a set of inter-image homographies for an image sequence comprising a plurality of frames to generate the set of inter-image homographies for the image sequence, the program instructions being executable by the at least one processor to perform operations comprising;

determining a plurality of point trajectories that traverse an initial frame pair;

estimating an inter-image homography for the initial frame pair according to a subset of the plurality of point trajectories that traverse the initial frame pair, the subset of the plurality of point trajectories that traverse the initial frame pair corresponding to points defining a two-dimensional (2D) plane; and

for each of one or more subsequent frame pairs, perform operations comprising;

determining a subset of points tracked through a previous frame pair whose trajectories correspond to a trajectory of the plane through the previous frame pair;

adding inliers to the subset of points tracked through the previous frame pair, the inliers corresponding to points whose trajectories match the subset of points tracked through the previous frame pair;

selecting a new subset of points from the inliers and the subset of points tracked through the previous frame pair; and

estimating an inter-image homography for the subsequent frame pair according to trajectories of the new subset of points tracked through the subsequent frame pair.

12. The system as recited in claim 11, wherein the subsequent frame pair includes one frame that is also in the previous frame pair.

13. The system as recited in claim 11, wherein the program instructions are further executable by the at least one processor to perform operations comprising:

generating a plurality of sets of inter-image homographies for the image sequence; and

selecting a set of inter-image homographies that has a largest total count of inliers from the plurality of sets as the set of inter-image homographies for the image sequence.

14. The system as recited in claim 11, wherein the estimating the inter-image homography for the subsequent frame pair comprises:

calculating a plurality of inter-image homographies for the subsequent frame pair based on a plurality of new subsets of points and determining a count of inliers consistent with each of the plurality of inter-image homographies for the subsequent frame pair; and

selecting, from the plurality of inter-image homographies, an inter-image homography that has a largest count of inliers as the estimated inter-image homography for the subsequent frame pair.

15. The system as recited in claim 11, wherein the program instructions are further executable by the at least one processor to perform operations comprising:

generating a set of inter-image homographies for two or more subsets of the plurality of frames in the image sequence, wherein a different plane is identified and tracked in at least two of the subsets of the plurality of frames; and

concatenating the two or more sets of inter-image homographies to generate a single combined set of inter-image homographies for the image sequence.

16. The system as recited in claim 11, wherein the new subset of points is determined based on a RANSAC algorithm.

17. A non-transitory computer-readable storage medium storing program instructions, the program instructions being computer-executable to perform operations comprising:

generating a set of inter-image homographies for an image sequence comprising a plurality of frames, said generating comprising;

determining a plurality of point trajectories that traverse an initial frame pair;

estimating an inter-image homography for the initial frame pair according to a subset of the plurality of point trajectories that traverse the initial frame pair, the subset of the plurality of point trajectories that traverse the initial frame pair corresponding to points defining a two-dimensional (2D) plane; and

for each of one or more subsequent frame pairs, perform operations comprising;

determining a subset of points tracked through a previous frame pair whose trajectories correspond to a trajectory of the plane through the previous frame pair;

adding inliers to the subset of points tracked through the previous frame pair, the inliers corresponding to points whose trajectories match the subset of points tracked through the previous frame pair;

selecting a new subset of points from the inliers and the subset of points tracked through the previous frame pair; and

estimating an inter-image homography for the subsequent frame pair according to trajectories of the new subset of points tracked through the subsequent frame pair.

18. The non-transitory computer-readable storage medium as recited in claim 17, wherein the subsequent frame pair includes one frame that is also in the previous frame pair.

19. The non-transitory computer-readable storage medium as recited in claim 17, wherein generating a set of inter-image homographies for the image sequence further comprises:

iteratively performing said generating to generate a plurality of sets of inter-image homographies for the image sequence; and

selecting a set of inter-image homographies that has a largest total count of inliers from the plurality of sets as the set of inter-image homographies for the image sequence.

20. The non-transitory computer-readable storage medium as recited in claim 17, wherein the estimating the inter-image homography for the subsequent frame pair comprises:

determining a plurality of subsets of points tracked through the previous frame pair;

adding respective inliers to each of the plurality of subsets of points tracked through the previous frame pair;

counting respective numbers of inliers added to each of the plurality of subsets of points tracked through the previous frame pair; and

estimating the inter-image homography for the subsequent image pair based on a subset of points of the plurality of subsets of points tracked through the previous frame pair that has the largest number of inliers.

21. The non-transitory computer-readable storage medium as recited in claim 17, wherein the operations further comprise:

performing said generating for two or more subsets of the plurality of frames in image sequence to generate two or more sets of inter-image homographies for the image sequence, wherein a different plane is identified and tracked in at least two of the subsets of the plurality of frames; and

concatenating the two or more sets of inter-image homographies to generate a single combined set of inter-image homographies for the image sequence.

22. The non-transitory computer-readable storage medium as recited in claim 17, wherein the new subset of points is determined based on a RANSAC algorithm.