# US 10,309,777 B2 · Visual odometry and pairwise alignment for high definition map creation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,309,777 B2
- Document ID: US10309777B2
- Status: Granted
- Kind: B2
- Application number: 15/855,116
- Filed: 2017-12-27
- Published: 2018-07-05
- Granted: 2019-06-04
- Earliest claimed: 2016-12-30
- Assignees: Deepmap Inc.
- Applicants: DeepMap Inc.
- Inventors: Ronghua Zhang; Chen Chen; Di Zeng; Mark Damon Wheeler
- Web page: https://patentgrep.com/patent/US10309777B2

## CPC

- G06T 17/05: Geographic models
- B60W 40/06: Road conditions
- G01C 11/06: by comparison of two or more pictures of the same area
- G01C 11/12: the pictures being supported in the same relative position as when they were taken
- G01C 11/30: by triangulation
- G01C 21/005: {with correlation of navigation data from several sources, e.g. map or contour matching (G01C21/30 takes precedence)}
- G01C 21/3602: {Input other than that of destination using image analysis, e.g. detection of road signs, lanes, buildings, real preceding vehicles using a camera}
- G01C 21/3635: {Guidance using 3D or perspective road maps}
- G01C 21/3694: {Output thereof on a road map}
- G01C 21/3848: {Data obtained from both position sensors and additional sensors}
- G01C 21/3867: {Geometry of map features, e.g. shape points, polygons or for simplified maps}
- G01S 19/42: Determining position
- G05D 1/00: Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots (drive control systems specially adapted for autonomous road vehicles B60W60/00)
- G05D 1/0246: {using a video camera in combination with image processing means}
- G05D 1/249: from positioning sensors located off-board the vehicle, e.g. from cameras
- G06T 7/11: Region-based segmentation
- G06T 7/246: using feature-based methods, e.g. the tracking of corners or segments
- G06T 7/248: {involving reference images or patches}
- G06T 7/55: from multiple images
- G06T 7/593: from stereo images
- G06T 7/68: of symmetry
- G06T 7/70: Determining position or orientation of objects or cameras (camera calibration G06T7/80)
- G06T 7/73: using feature-based methods
- G06T 7/74: {involving reference images or patches}
- G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation}
- G06V 10/462: {Salient features, e.g. scale invariant feature transforms [SIFT]}
- G06V 10/758: {Involving statistics of pixels or of feature values, e.g. histogram matching}
- G06V 20/56: exterior to a vehicle by using sensors mounted on the vehicle
- G06V 20/58: Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads
- G06V 20/588: {Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road}
- G08G 1/20: {Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles}
- B60W 2552/00: Input parameters relating to infrastructure
- B60W 2552/53: Road markings, e.g. lane marker or crosswalk
- G01S 17/89: for mapping or imaging
- G01S 19/46: the supplementary measurement being of a radio-wave signal type
- G01S 19/47: the supplementary measurement being an inertial measurement, e.g. tightly coupled inertial
- G06T 2200/04: involving 3D image data
- G06T 2207/10021: Stereoscopic video; Stereoscopic image sequence
- G06T 2207/10028: Range image; Depth image; 3D point clouds
- G06T 2207/20048: Transform domain processing
- G06T 2207/30252: Vehicle exterior; Vicinity of vehicle
- G06T 2207/30256: Lane; Road marking
- G06T 2210/56: Particle system, point based geometry or rendering
- G06T 2215/12: Shadow map, environment map
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- B60W: CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

As an autonomous vehicle moves through a local area, pairwise alignment may be performed to calculate changes in the pose of the vehicle between different points in time. The vehicle comprises an imaging system configured to capture image frames depicting a portion of the surrounding area. Features are identified from the captured image frames, and a 3-D location is determined for each identified feature. The features of different image frames corresponding to different points in time are analyzed to determine a transformation in the pose of the vehicle during the time period between the image frames. The determined poses of the vehicle are used to generate an HD map of the local area.

## Claims

### Claim 1

A method, comprising:
receiving, from an imaging system mounted on a vehicle, a plurality of image frames, each image frame associated with a local area surrounding the vehicle at a particular point in time, and comprising a first image captured using a first camera of the imaging system and a second image captured using a second camera of the imaging system;
for each image frame of the plurality of image frames, determining locations of a set of features corresponding to features within the local area, by:
identifying a first set of feature points on the first image of the image frame, and a second set of feature points on the second image of the image frame;
assigning a descriptor for each identified feature point of the first and second sets of feature points of the image frame;
determining the set of features for the image frame, each corresponding to a feature point of the first set of feature points matched with a feature point of the second set of feature points, comprising, for a first feature point of the first set of feature points on the first image of the image frame:
identifying one or more feature points of the second set of feature points, based upon a distance between a location of the first feature point and each of the one or more feature points of the second set of feature points;
comparing the assigned descriptors of the first feature point and each of the one or more features points to determine a similarity between the first feature point and each of the one or more feature points; and
in response to a determination that a similarity between the first feature point and a second feature point of the one or more feature points satisfies a threshold value, matching the first and second feature points to correspond to a feature of the set of features; and
determining a location of each feature of the set of features by triangulating the corresponding feature points of the first and second set of feature points;
determining a transformation between a first position of the vehicle at a first point in time corresponding to a first image frame of the plurality of image frames, and a second position of the vehicle at a second point in time corresponding to a second image frame of the plurality of image frames, by:
selecting a first subset of features from the set of features associated with the first image frame;
identifying a second subset of features from the second image frame corresponding to the first subset of features, based upon a level of geometric similarity between the features of the first and second subsets;
using the first and second subsets of features for each of the first and second image frames, determining the transformation between the determined positions of features of the first and second subsets of features;
generating a high definition map of the local area based on the transformation, the high definition map for use in driving by one or more autonomous vehicles; and
transmitting the generated high definition map to an autonomous vehicle, wherein the autonomous vehicle generates a control signal to drive the autonomous vehicle based upon the generated high definition map.

### Claim 2 (depends on 1)

The method of claim 1, wherein the transformation is determined using a PnP (Perspective-n-Point) algorithm.

### Claim 3 (depends on 1)

The method of claim 1, further comprising rectifying the first image and the second image of the image frame such that the first image and the second image are coplanar.

### Claim 4 (depends on 1)

The method of claim 1, wherein the first and second feature points are not matched to correspond to a feature point in response to at least two of the one or more feature points having a similarity with the first feature point satisfying a threshold value.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first and second feature points are not matched to correspond to a feature in response to a determination that a location of the first feature point on the first image and a location of the second feature point on the second image do not correspond to the same row of the first and second images.

### Claim 6 (depends on 1)

The method of claim 1, further comprising removing a feature from the set of features in response to a determination that the determined location of the feature corresponds to a distance from the imaging system exceeding a threshold distance.

### Claim 7 (depends on 1)

The method of claim 1, wherein determining the transformation between the first and second positions further comprises:
for each of a plurality of iterations:
selecting a different first subset of features from the set of features associated with the first image frame;
identifying the second subset of features from the second image frame corresponding to the selected first subset of features;
determining the transformation between the determined positions of features of the first and second subsets of features;
for each feature of first image frame, applying the determined transformation to the feature and determining a nearest feature of the second image frame.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
for each of the plurality of iterations, determining a count for the transformation based upon a number of transformed features of the first image frame having a nearest feature of the second image frame within a threshold distance; and
identifying the transformation associated with a highest count of the plurality of iterations.

### Claim 9 (depends on 1)

The method of claim 1, wherein each feature of the first subset of features is selected to be at least a threshold distance from the remaining features of the first subset of features.

### Claim 10

A computer program product for generating a high definition map of a local area based upon sensor readings of a vehicle traveling through the local area, the computer program product comprising a tangible computer-readable storage medium containing computer program code that when executed causes one or more processors to:
receive, from an imaging system mounted on the vehicle, a plurality of image frames, each image frame associated with the local area surrounding the vehicle at a particular point in time, and comprising a first image captured using a first camera of the imaging system and a second image captured using a second camera of the imaging system;
for each image frame of the plurality of image frames, determine locations of a set of features corresponding to features within the local area, by:
identifying a first set of feature points on the first image of the image frame, and a second set of feature points on the second image of the image frame;
assigning a descriptor for each identified feature point of the first and second sets of feature points of the image frame;
determining the set of features for the image frame, each corresponding to a feature point of the first set of feature points matched with a feature point of the second set of feature points, comprising, for a first feature point of the first set of feature points on the first image of the image frame:
identifying one or more feature points of the second set of feature points, based upon a distance between a location of the first feature point and each of the one or more feature points of the second set of feature points;
comparing the assigned descriptors of the first feature point and each of the one or more features points to determine a similarity between the first feature point and each of the one or more feature points; and
in response to a determination that a similarity between the first feature point and a second feature point of the one or more feature points satisfies a threshold value, matching the first and second feature points to correspond to a feature of the set of features; and
determining a location of each feature of the set of features by triangulating the corresponding feature points of the first and second set of feature points;
determine a transformation between a first position of the vehicle at a first point in time corresponding to a first image frame of the plurality of image frames, and a second position of the vehicle at a second point in time corresponding to a second image frame of the plurality of image frames, by:
selecting a first subset of features from the set of features associated with the first image frame;
identifying a second subset of features from the second image frame corresponding to the first subset of features, based upon a level of geometric similarity between the features of the first and second subsets;
using the first and second subsets of features for each of the first and second image frames, determining the transformation between the determined positions of features of the first and second subsets of features;
generate a high definition map of the local area based on the transformation, the high definition map for use in driving by one or more autonomous vehicles; and
transmit the generated high definition map to an autonomous vehicle, wherein the autonomous vehicle generates a control signal to drive the autonomous vehicle based upon the generated high definition map.

### Claim 11 (depends on 10)

The computer program product of claim 10, each feature of the first subset of features is selected to be at least a threshold distance from the remaining features of the first subset of features.

### Claim 12 (depends on 10)

The computer program product of claim 10, wherein the transformation is determined using a PnP (Perspective-n-Point) algorithm.

### Claim 13 (depends on 10)

The computer program product of claim 10, wherein the tangible computer-readable storage medium further contains computer program code that when executed causes one or more processors to rectify the first image and the second image of the image frame such that the first image and the second image are coplanar.

### Claim 14 (depends on 10)

The computer program product of claim 10, wherein the first and second feature points are not matched to correspond to a feature point in response to at least two of the one or more feature points having a similarity with the first feature point satisfying a threshold value.

### Claim 15 (depends on 10)

The computer program product of claim 10, wherein the first and second feature points are not matched to correspond to a feature in response to a determination that a location of the first feature point on the first image and a location of the second feature point on the second image do not correspond to the same row of the first and second images.

### Claim 16 (depends on 10)

The computer program product of claim 10, wherein the tangible computer-readable storage medium further contains computer program code that when executed causes one or more processors to remove a feature from the set of features in response to a determination that the determined location of the feature corresponds to a distance from the imaging system exceeding a threshold distance.

### Claim 17 (depends on 10)

The computer program product of claim 10, wherein the tangible computer-readable storage medium further contains computer program code that when executed causes one or more processors to determine the transformation between the first and second positions by:
for each of a plurality of iterations:
selecting a different first subset of features from the set of features associated with the first image frame;
identifying the second subset of features from the second image frame corresponding to the selected first subset of features;
determining the transformation between the determined positions of features of the first and second subsets of features;
for each feature of first image frame, applying the determined transformation to the feature and determining a nearest feature of the second image frame.

### Claim 18 (depends on 17)

The computer program product of claim 17, wherein the tangible computer-readable storage medium further contains computer program code that when executed causes one or more processors to:
for each of the plurality of iterations, determine a count for the transformation based upon a number of transformed features of the first image frame having a nearest feature of the second image frame within a threshold distance; and
identify the transformation associated with a highest count of the plurality of iterations.

### Claim 19

A computer system for generating a high definition map of a local area based upon sensor readings of a vehicle traveling through the local area, the computer system comprising:
one or more computer processors; and
a tangible computer-readable storage medium containing computer program code that when executed causes one or more processors to:
receive, from an imaging system mounted on the vehicle, a plurality of image frames, each image frame associated with the local area surrounding the vehicle at a particular point in time, and comprising a first image captured using a first camera of the imaging system and a second image captured using a second camera of the imaging system;
for each image frame of the plurality of image frames, determine locations of a set of features corresponding to features within the local area, by:
identifying a first set of feature points on the first image of the image frame, and a second set of feature points on the second image of the image frame;
assigning a descriptor for each identified feature point of the first and second sets of feature points of the image frame;
determining the set of features for the image frame, each corresponding to a feature point of the first set of feature points matched with a feature point of the second set of feature points, comprising, for a first feature point of the first set of feature points on the first image of the image frame:
identifying one or more feature points of the second set of feature points, based upon a distance between a location of the first feature point and each of the one or more feature points of the second set of feature points;
comparing the assigned descriptors of the first feature point and each of the one or more features points to determine a similarity between the first feature point and each of the one or more feature points; and
in response to a determination that a similarity between the first feature point and a second feature point of the one or more feature points satisfies a threshold value, matching the first and second feature points to correspond to a feature of the set of features; and
determining a location of each feature of the set of features by triangulating the corresponding feature points of the first and second set of feature points;
determine a transformation between a first position of the vehicle at a first point in time corresponding to a first image frame of the plurality of image frames, and a second position of the vehicle at a second point in time corresponding to a second image frame of the plurality of image frames, by:
selecting a first subset of features from the set of features associated with the first image frame;
identifying a second subset of features from the second image frame corresponding to the first subset of features, based upon a level of geometric similarity between the features of the first and second subsets;
using the first and second subsets of features for each of the first and second image frames, determining the transformation between the determined positions of features of the first and second subsets of features;
generate a high definition map of the local area based on the transformation, the high definition map for use in driving by one or more autonomous vehicles; and
transmit the generated high definition map to an autonomous vehicle, wherein the autonomous vehicle generates a control signal to drive the autonomous vehicle based upon the generated high definition map.

### Claim 20 (depends on 19)

The computer system of claim 19, wherein the computer-readable storage medium further contains computer program code that when executed causes the one or more processors to determine the transformation between the first and second positions by:
for each of a plurality of iterations:
selecting a different first subset of features from the set of features associated with the first image frame;
identifying the second subset of features from the second image frame corresponding to the selected first subset of features;
determining the transformation between the determined positions of features of the first and second subsets of features;
for each feature of first image frame, applying the determined transformation to the feature and determining a nearest feature of the second image frame.