Online environment mapping

• US 8,913,055 B2
• Filed: 05/30/2012
• Issued: 12/16/2014
• Est. Priority Date: 05/31/2011
• Status: Expired due to Fees

• Current Assignee: ETH Zurich, Honda Motor Co., Ltd. (Honda Motor Company), University of North Carolina At Chapel Hill (University of North Carolina System)
• Original Assignee: ETH Zurich, Honda Motor Co., Ltd. (Honda Motor Company), University of North Carolina At Chapel Hill (University of North Carolina System)
• Inventors: Lim, Jongwoo, Frahm, Jan-Michael, Pollefeys, Marc
• Primary Examiner(s): Welch, David T
• Application Number:
  US13/484,127
• Publication Number:
  US 20120306847A1
• Time in Patent Office: 930 Days
• Field of Search: 345/418, 345/581, 382/103
• US Class Current: 345/418
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7837 using objects detected or recognised in the video content
• CPC Class Codes: G06T 2207/20072 Graph-based image processing
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06T 2207/30244 Camera pose
• 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/579 from motion
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames

Abstract

A system and method are disclosed for online mapping of large-scale environments using a hybrid representation of a metric Euclidean environment map and a topological map. The system includes a scene module, a location recognition module, a local adjustment module and a global adjustment module. The scene flow module is for detecting and tracking video features of the frames of an input video sequence. The scene flow module is also configured to identify multiple keyframes of the input video sequence and add the identified keyframes into an initial environment map of the input video sequence. The location recognition module is for detecting loop closures in the environment map. The local adjustment module enforces local metric properties of the keyframes in the environment map, and the global adjustment module is for optimizing the entire environment map subject to global metric properties of the keyframes in the keyframe pose graph.

Claims

1. A computer implemented method for generating an environment map of an input video sequence, the method comprising:

identifying a plurality of keyframes of the input video sequence and adding the identified keyframes into an initial environment map, the keyframes being identified based on video features associated with a plurality of video frames of the input video sequence, and the initial environment map being represented by a keyframe pose graph;

enforcing local metric properties of a group of identified keyframes of the initial environment map;

optimizing the initial environment map based on global metric properties of the identified keyframes, wherein optimizing the initial environment map comprises;

clustering the identified keyframes into a plurality of disjoint sets of keyframes based on geodesic distance information of the keyframe pose graph, a disjoint set of keyframes representing a segment of keyframes;

for each segment of keyframes, enforcing local metric properties of the keyframes in the segment;

applying global segment optimization to the segments of keyframes, comprising;

embedding the segments of keyframes and landmarks associated with the keyframes of the segments into a metric space; and

updating projected three-dimensional coordinates of the landmarks to the associated keyframes based on the metric constraints of the landmarks and keyframes; and

generating an output environment map based on the optimization.

2. The method of claim 1, further comprising:

computing motion estimation of a camera system based on detected video features of the input video sequence;

identifying a plurality of inlier features among the detected video features of the video sequence, wherein an inlier feature of the video sequence is modeled by a set of model parameters used to track the video features of the video sequence; and

detecting loop closures of the initial environment map.

3. The method of claim 1, wherein the keyframe pose graph comprises:

a plurality of nodes and a plurality of edges a pair of nodes of the plurality of nodes, a node of the graph representing a keyframe added to the initial environment map, and an edge between two nodes of the graph representing the relative pose between the two keyframes represented by the nodes.

4. The method of claim 1, wherein a keyframe of the input video sequence has one or more landmarks associated with the keyframe, and the association between the keyframe and a landmark is determined based on whether the landmark is observed by the keyframe.

5. The method of claim 4, wherein two keyframes observing a same landmark are linked, the linkage between the two keyframes is represented by an edge between the two keyframes in the keyframe pose graph.

6. The method of claim 1, wherein enforcing local metric properties of a group of identified keyframes of the initial environment map comprises:

selecting the group of keyframes most recently added to the keyframe pose graph, the size of the group being predetermined; and

applying sparse bundle adjustment to the group of the keyframes, wherein the sparse bundle adjustment refines a plurality of three-dimensional coordinates describing a scene geometry observed by the group of the keyframes subject to the local metric properties of the group of the keyframes.

7. The method of claim 1, further comprising:

extracting one or more video features from the plurality of video frames of the input video sequence; and

tracking the video features in two or more video frames of the input video sequence.

8. The method of claim 1, wherein applying global segment optimization further comprises:

repeating the global segment optimization operations to segments of newly added keyframes and landmarks in the environment map.

9. A non-transitory computer-readable storage medium storing executable computer program code for generating an environment map of an input video sequence, the computer program code comprising instructions for:

identifying a plurality of keyframes of the input video sequence and adding the identified keyframes into an initial environment map, the keyframes being identified based on video features associated with a plurality of video frames of the input video sequence, and the initial environment map being represented by a keyframe pose graph;

enforcing local metric properties of a group of identified keyframes of the initial environment map;

optimizing the initial environment map based on global metric properties of the identified keyframes, wherein optimizing the initial environment map comprises;

clustering the identified keyframes into a plurality of disjoint sets of keyframes based on geodesic distance information of the keyframe pose graph, a disjoint set of keyframes representing a segment of keyframes;

for each segment of keyframes, enforcing local metric properties of the keyframes in the segment;

applying global segment optimization to the segments of keyframes, comprising;

embedding the segments of keyframes and landmarks associated with the keyframes of the segments into a metric space; and

updating projected three-dimensional coordinates of the landmarks to the associated keyframes based on the metric constraints of the landmarks and keyframes; and

generating an output environment map based on the optimization.

10. The computer-readable storage medium of claim 9, further comprising computer program instructions for:

computing motion estimation of a camera system based on detected video features of the input video sequence;

identifying a plurality of inlier features among the detected video features of the video sequence, wherein an inlier feature of the video sequence is modeled by a set of model parameters used to track the video features of the video sequence; and

detecting loop closures of the initial environment map.

11. The computer-readable storage medium of claim 9, wherein the keyframe pose graph comprises:

a plurality of nodes and a plurality of edges a pair of nodes of the plurality of nodes, a node of the graph representing a keyframe added to the initial environment map, and an edge between two nodes of the graph representing the relative pose between the two keyframes represented by the nodes.

12. The computer-readable storage medium of claim 9, wherein a keyframe of the input video sequence has one or more landmarks associated with the keyframe, and the association between the keyframe and a landmark is determined based on whether the landmark is observed by the keyframe.

13. The computer-readable storage medium of claim 12, wherein two keyframes observing a same landmark are linked, the linkage between the two keyframes is represented by an edge between the two keyframes in the keyframe pose graph.

14. The computer-readable storage medium of claim 9, wherein the computer program instructions for enforcing local metric properties of a group of identified keyframes of the initial environment map comprise instructions for:

selecting the group of keyframes most recently added to the keyframe pose graph, the size of the group being predetermined; and

applying sparse bundle adjustment to the group of the keyframes, wherein the sparse bundle adjustment refines a plurality of three-dimensional coordinates describing a scene geometry observed by the group of the keyframes subject to the local metric properties of the group of the keyframes.

15. The computer-readable storage medium of claim 9, further comprising computer program instructions for:

extracting one or more video features from the plurality of video frames of the input video sequence; and

tracking the video features in two or more video frames of the input video sequence.

16. The computer-readable storage medium of claim 9, wherein the computer program instructions for applying global segment optimization further comprise instructions for:

repeating the global segment optimization operations to segments of newly added keyframes and landmarks in the environment map.

17. A computer system for generating an environment map of an input video sequence, the system comprising:

a location recognition module for identifying a plurality of keyframes of the input video sequence and adding the identified keyframes into an initial environment map, the keyframes being identified based on the video features associated with a plurality of video frames of the input video sequence, and the initial environment map being represented by a keyframe pose graph;

a local adjustment module for enforcing local metric properties of a group of identified keyframes of the initial environment map; and

a global adjustment module for;

optimizing the initial environment map based on global metric properties of the identified keyframes, wherein optimizing the initial environment map comprises;

clustering the identified keyframes into a plurality of disjoint sets of keyframes based on geodesic distance information of the keyframe pose graph, a disjoint set of keyframes representing a segment of keyframes;

for each segment of keyframes, enforcing local metric properties of the keyframes in the segment;

applying global segment optimization to the segments of keyframes, comprising;

embedding the segments of keyframes and landmarks associated with the keyframes of the segments into a metric space; and

updating projected three-dimensional coordinates of the landmarks to the associated keyframes based on the metric constraints of the landmarks and keyframes; and

generating an output environment map based on the optimization.

18. The system of claim 17, wherein:

a scene flow module is for;

computing motion estimation of a camera system based on detected video features of the input video sequence;

identifying a plurality of inlier features among the detected video features of the video sequence, wherein an inlier feature of the video sequence is modeled by a set of model parameters used to track the video features of the video sequence; and

the location recognition module is further for detecting loop closures of the initial environment map.