Plane Detection and Tracking for Structure from Motion

• US 20130044913A1
• Filed: 07/17/2012
• Published: 02/21/2013
• 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
• Granted Patent: US 9,153,025 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• 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 according to a two-dimensional (2D) plane in at least two of the frames, wherein said generating comprises;

estimating an inter-image homography for an initial frame pair according to a subset of a plurality of point trajectories that traverse the initial frame pair, each point trajectory in the plurality of point trajectories tracking a feature across two or more of the frames; and

estimating an inter-image homography at each of one or more subsequent frame pairs according to a subset of the point trajectories that traverse the respective frame pair;

wherein the inter-image homography at each frame pair corresponds to the plane at the respective frame pair.

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

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

identifying a set of inliers at the initial frame pair and at each subsequent frame pair according to the estimated inter-image homography for the respective frame pair, wherein an inlier is a point trajectory that corresponds to the plane at a frame; and

at each of the one or more subsequent frame pairs, selecting point trajectories to be included in the subset of the point trajectories according to the set of inliers identified at the previous frame pair.

4. The method as recited in claim 3, 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 inliers from the plurality of sets as the set of inter-image homographies for the image sequence.

5. The method as recited in claim 3, further comprising, at each subsequent frame pair, terminating said estimating upon determining that a count of inliers at the frame pair is below a threshold.

6. The method as recited in claim 1, wherein said estimating an inter-image homography at each of the one or more subsequent frame pairs according to the subset of the point trajectories that traverse the respective frame pair comprises, at each subsequent frame pair:

calculating a plurality of inter-image homographies for the frame pair and determining a count of inliers consistent with each of the plurality of inter-image homographies for the frame pair, wherein an inlier is a point trajectory that corresponds to the plane at a frame; 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 frame pair.

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

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.

8. 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.

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

identifying a set of inliers at the initial frame pair and at each subsequent frame pair according to the estimated inter-image homography for the respective frame pair, wherein an inlier is a point trajectory that corresponds to the plane at a frame; and

at the initial frame pair and at each subsequent frame pair, adding the inter-image homography and the inliers for the respective frame pair to a projective reconstruction for the image sequence.

10. The method as recited in claim 9, wherein said generating further comprises, at each of the one or more subsequent frame pairs, 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.

11. A system, comprising:

one or more processors; and

a memory comprising program instructions, wherein the program instructions are 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 according to a two-dimensional (2D) plane in at least two of the frames, wherein to generate the set of in set of inter-image homographies for the image sequence, the program instructions are executable by the at least one processor to;

estimate an inter-image homography for an initial frame pair according to a subset of a plurality of point trajectories that traverse the initial frame pair, each point trajectory in the plurality of point trajectories tracking a feature across two or more of the frames; and

estimate an inter-image homography at each of one or more subsequent frame pairs according to a subset of the point trajectories that traverse the respective frame pair;

wherein the inter-image homography at each frame pair corresponds to the plane at the respective frame pair.

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

13. The system as recited in claim 11, wherein, to generate the set of in set of inter-image homographies for the image sequence, the program instructions are further executable by the at least one processor to:

identify a set of inliers at the initial frame pair and at each subsequent frame pair according to the estimated inter-image homography for the respective frame pair, wherein an inlier is a point trajectory that corresponds to the plane at a frame; and

at each of the one or more subsequent frame pairs, select point trajectories to be included in the subset of the point trajectories according to the set of inliers identified at the previous frame pair.

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

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

select 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.

15. The system as recited in claim 11, wherein, to estimate an inter-image homography at each of the one or more subsequent frame pairs according to the subset of the point trajectories that traverse the respective frame pair, the program instructions are executable by the at least one processor to, at each subsequent frame pair:

calculate a plurality of inter-image homographies for the frame pair and determining a count of inliers consistent with each of the plurality of inter-image homographies for the frame pair, wherein an inlier is a point trajectory that corresponds to the plane at a frame; and

select, 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 frame pair.

16. The system as recited in claim 11, wherein the program instructions are executable by the at least one processor to:

generate 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

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

17. A non-transitory computer-readable storage medium storing program instructions, wherein the program instructions are computer-executable to implement:

generating a set of inter-image homographies for an image sequence comprising a plurality of frames according to a two-dimensional (2D) plane in at least two of the frames, wherein said generating comprises;

estimating an inter-image homography for an initial frame pair according to a subset of a plurality of point trajectories that traverse the initial frame pair, each point trajectory in the plurality of point trajectories tracking a feature across two or more of the frames; and

estimating an inter-image homography at each of one or more subsequent frame pairs according to a subset of the point trajectories that traverse the respective frame pair;

wherein the inter-image homography at each frame pair corresponds to the plane at the respective frame pair.

18. The non-transitory computer-readable storage medium as recited in claim 17, wherein each 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, in said generating, the program instructions are further computer-executable to implement:

identifying a set of inliers at the initial frame pair and at each subsequent frame pair according to the estimated inter-image homography for the respective frame pair, wherein an inlier is a point trajectory that corresponds to the plane at a frame; and

at each of the one or more subsequent frame pairs, selecting point trajectories to be included in the subset of the point trajectories according to the set of inliers identified at the previous frame pair.

20. The non-transitory computer-readable storage medium as recited in claim 19, wherein the program instructions are further computer-executable to implement:

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.

21. The non-transitory computer-readable storage medium as recited in claim 17, wherein, in said estimating an inter-image homography at each of the one or more subsequent frame pairs according to the subset of the point trajectories that traverse the respective frame pair, the program instructions are computer-executable to implement, at each subsequent frame pair:

calculating a plurality of inter-image homographies for the frame pair and determining a count of inliers consistent with each of the plurality of inter-image homographies for the frame pair, wherein an inlier is a point trajectory that corresponds to the plane at a frame; 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 frame pair.

22. The non-transitory computer-readable storage medium as recited in claim 17, wherein the program instructions are further computer-executable to implement:

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.