Localisation and mapping

• US 9,679,381 B2
• Filed: 07/25/2013
• Issued: 06/13/2017
• Est. Priority Date: 07/30/2012
• Status: Active Grant

• Current Assignee: Sony Interactive Entertainment Europe Limited (Sony Group Corp.)
• Original Assignee: Sony Computer Entertainment Europe Limited (Sony Group Corp.)
• Inventors: Martini, Antonio
• Primary Examiner(s): McClellan, James S
• Application Number:
  US14/417,938
• Publication Number:
  US 20150209673A1
• Time in Patent Office: 1,419 Days
• Field of Search: 463 31, 463 42
• CPC Class Codes: A63F 13/25 Output arrangements for video game devices
• CPC Class Codes: A63F 13/50 Controlling the output signals based on the game progress
• CPC Class Codes: A63F 13/5378 for displaying an additional top view, e.g. radar screens or maps using two or more virtual cameras concurrently A63F13/5252
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/006 Mixed reality object pose determination, tracking or camera calibration for mixed reality G06T7/00
• CPC Class Codes: G06T 2200/08 involving all processing steps from image acquisition to 3D model generation
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 2215/16 Using real world measurements to influence rendering
• CPC Class Codes: G06T 2219/2004 Aligning objects, relative positioning of parts
• CPC Class Codes: G06T 7/0008 checking presence/absence
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/337 involving reference images or patches
• CPC Class Codes: G06T 7/55 from multiple images
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 30/422 : Technical drawings; Geographical maps
• CPC Class Codes: H04N 13/207 : using a single 2D image sensor
• CPC Class Codes: H04N 13/211 : using temporal multiplexing
• CPC Class Codes: H04N 7/18 : Closed-circuit television [CCTV] systems, i.e. systems in which the video signal is not broadcast

Abstract

A method generates a three-dimensional map of a region from successive images of that region captured from different positions. The method includes detecting feature points within the captured images; designating a subset of the captured images as a set of keyframes each having respective sets of measurement data representing image positions of landmark points detected as feature points in that image, where each keyframe is connected to at least one other keyframe in the set; and detecting whether candidate measurement data associated with a keyframe may be removed from the set of measurement data for that keyframe by detecting whether each keyframe, in the set of keyframes without the candidate measurement data, is still directly or indirectly connected to all of the other keyframes in the set of keyframes by a sequence of one or more connections. And in this case, the method includes removing that candidate measurement data.

Claims

1. A method of generating a three-dimensional map of a region from successive images of the region captured from different camera positions, the map comprising a set of landmark points each defined by a three dimensional spatial position and image information associated with that three dimensional position, the method comprising:

capturing, by an imaging device, successive images of the region;

detecting, by a processor, feature points within the captured images;

designating, by the processor, a subset of the captured images as a set of keyframes each having respective sets of measurement data representing image positions of landmark points detected as feature points in that image, each keyframe being connected to at least one other keyframe in the set by a connection comprising at least a threshold number of landmark points, having corresponding measurement data for that keyframe, in common with the same landmark points having corresponding measurement data for that other keyframe in the set, and the set of keyframes being such that each keyframe in the set is directly or indirectly connected to all of the other keyframes in the set by a sequence of one or more such connections;

detecting, by the processor, whether candidate measurement data associated with a given one of the keyframes may be removed from the set of measurement data for that keyframe, by detecting whether each keyframe, in the set of keyframes without the candidate measurement data, is still directly or indirectly connected to all of the other keyframes in the set of keyframes by a sequence of one or more connections;

and if so, removing that candidate measurement data.

2. A method according to claim 1, in which the threshold number of landmark points is at least three.

3. A method according to claim 1, in which the step of detecting whether candidate measurement data may be removed comprises:

generating a connection graph between the keyframes of the set, excluding the candidate measurement data, by connected components analysis; and

removing the candidate measurement data if the connection graph comprises only one component.

4. A method according to claim 3, in which, where the candidate measurement data comprises all measurement data associated with a keyframe:

the detecting whether candidate measurement data may be removed further comprises detecting whether each keyframe, in the set of keyframes, excluding the keyframe corresponding to the candidate measurement data, is still directly or indirectly connected to all of the other keyframes in the set of keyframes, excluding the keyframe corresponding to the candidate measurement data, by a sequence of one or more connections; and

the removing step comprises removing that keyframe from the set of keyframes.

5. A method according to claim 1, in which the designating step comprises designating a captured image as a keyframe by:

detecting whether at least a threshold number of feature points within that captured image correspond to landmark points for which one or more keyframes in the set of keyframes have associated measurement data.

6. A method according to claim 1, in which the designating step comprises designating a captured image as a keyframe by;

detecting whether the feature points in the captured image represent a view which is sufficiently different to that of the corresponding landmark points as to allow triangulation of a respective position from the feature points and the corresponding landmark points.

7. A method according to claim 1, in which each keyframe has associated camera position data defining a three dimensional camera position and orientation for that image.

8. A method according to claim 7, further comprising:

refining the measurement data and the camera position data associated with at least a subset of the keyframes by;

deriving a difference between the measurement data for landmark points in the keyframes and corresponding image positions obtained from the camera position data and the three dimensional spatial position of that landmark point; and

adjusting one or both of the camera position data for one or more keyframes and the three dimensional spatial position of one or more landmark points so as to reduce the detected difference.

9. A non-transitory computer-readable recording medium storing computer instructions thereon, the computer instructions, when executed by a computer, causes the computer to carry out a method of of generating a three-dimensional map of a region from successive images of the region captured from different camera positions, the map comprising a set of landmark points each defined by a three dimensional spatial position and image information associated with that three dimensional position, the method comprising:

capturing successive images of the region;

detecting feature points within the captured images;

designating a subset of the captured images as a set of keyframes each having respective sets of measurement data representing image positions of landmark points detected as feature points in that image, each keyframe being connected to at least one other keyframe in the set by a connection comprising at least a threshold number of landmark points, having corresponding measurement data for that keyframe, in common with the same landmark points having corresponding measurement data for that other keyframe in the set, and the set of keyframes being such that each keyframe in the set is directly or indirectly connected to all of the other keyframes in the set by a sequence of one or more such connections;

detecting whether candidate measurement data associated with a given one of the keyframes may be removed from the set of measurement data for that keyframe, by detecting whether each keyframe, in the set of keyframes without the candidate measurement data, is still directly or indirectly connected to all of the other keyframes in the set of keyframes by a sequence of one or more connections;

and if so, removing that candidate measurement data.

10. The non-transitory computer-readable recording medium of claim 9, in which the step of detecting whether candidate measurement data may be removed comprises:

generating a connection graph between the keyframes of the set, excluding the candidate measurement data, by connected components analysis; and

removing the candidate measurement data if the connection graph comprises only one component.

11. Image processing apparatus operable to generate a three-dimensional map of a region from successive captured images of the region captured from different camera positions, the map comprising a set of landmark points each defined by a three dimensional spatial position and image information associated with that three dimensional position, a subset of the captured images being designated as a set of keyframes each having respective sets of measurement data representing image positions of landmark points detected as feature points in that image, each keyframe being connected to at least one other keyframe in the set by a connection comprising at least a threshold number of landmark points, having corresponding measurement data for that keyframe, in common with the same landmark points having corresponding measurement data for that other keyframe in the set, and the set of keyframes being such that each keyframe in the set is directly or indirectly connected to all of the other keyframes in the set by a sequence of one or more such connections, the apparatus comprising:

a detector configured to detect whether candidate measurement data associated with a keyframe may be removed from the set of measurement data for that keyframe, by detecting whether each keyframe, in the set of keyframes without the candidate measurement data, is still directly or indirectly connected to all of the other keyframes in the set of keyframes by a sequence of one or more connections and if so, to remove that candidate measurement data.

12. Computer games apparatus comprising:

an image processing apparatus according to claim 11; and

an image renderer configured to render an image for display by combining a captured image with one or more computer-generated image portions generated with respect to map positions associated with feature points of the captured image.

13. Apparatus according to claim 12, comprising a camera configured to capture the images.