US-12625269-B2 - Multiple resolution, simultaneous localization and mapping based on 3-D LIDAR measurements

US12625269B2US 12625269 B2US12625269 B2US 12625269B2US-12625269-B2

Abstract

Methods and systems for improved simultaneous localization and mapping based on 3-D LIDAR image data. In one aspect, LIDAR image frames are segmented and clustered before feature detection to improve computational efficiency while maintaining both mapping and localization accuracy. Segmentation involves removing redundant data before feature extraction. Clustering involves grouping pixels associated with similar objects together before feature extraction. In another aspect, features are extracted from LIDAR image frames based on a measured optical property associated with each measured point. The pools of feature points comprise a low resolution feature map associated with each image frame. Low resolution feature maps are aggregated over time to generate high resolution feature maps. In another aspect, the location of a LIDAR measurement system in a three dimensional environment is slowly updated based on the high resolution feature maps and quickly updated based on the low resolution feature maps.

Inventors

Kiran K. GUNNAM

Assignees

VELODYNE LIDAR USA, INC.

Dates

Publication Date: 20260512
Application Date: 20231011

Claims (20)

1 . A system, comprising: a photodetector that detects an amount of return light reflected from a point in a three dimensional environment in response to a pulse of illumination light; a simultaneous localization and mapping engine, configured to: receive a time sequence of image frames, each image frame including a plurality of measured points, each associated with a location in a three dimensional environment; generate a plurality of small feature maps, each small feature map corresponding to a respective image frame in the time sequence of image frames, wherein each small feature map is generated by: segmenting and clustering the plurality of measured points in a respective image frame; and extracting one or more feature points from the respective image frame; generating a first large feature map from a first sequence of the small feature maps by projecting the feature points of each of the first sequence of small feature maps to a world coordinate frame fixed to the three dimensional environment; and generating a second large feature map from a second sequence of the small feature maps by projecting the feature points of each of the second sequence of small feature maps to the world coordinate frame fixed to the three dimensional environment, wherein the second sequence of small feature maps follows the first sequence of small feature maps; and estimate a location of the system within the three dimensional environment.
2 . The system of claim 1 , wherein the simultaneous localization and mapping engine is further configured to: estimate a second location of the system with respect to the world coordinate frame based on the location of the system.
3 . The system of claim 1 , wherein the simultaneous localization and mapping module include one or more odometry modules configured to estimate a position of the system.
4 . The system of claim 3 , wherein a first odometry meter provides an estimate of the position of the system at a rate of 10 Hz, and a second odometry meter provides an estimate of the position of the system at a rate of 1 Hz.
5 . The system of claim 1 , wherein the simultaneous localization and mapping module utilizes a k-dimensional tree to organize the feature points.
6 . The system of claim 5 , wherein the k-dimensional tree matches a dimension of attributes associated with the measured points.
7 . The system of claim 1 , wherein the simultaneous localization and mapping module generates a large feature map based at least in part on the small feature maps.
8 . The system of claim 1 , wherein each image frame comprises high resolution data in a region of interest.
9 . The system of claim 1 , wherein the simultaneous localization and mapping module further estimates an updated current location of the system with respect to the world coordinate frame based on a current location of the system and a location of the system at the current image frame with respect to an immediately prior image frame.
10 . The system of claim 1 , wherein clustering the plurality of measured points in the respective image frame comprises clustering a subset of measured points associated with the respective image frame into one or more sub-groups each associated with one or more similar objects.
11 . The system of claim 1 , wherein extracting the one or more feature points from the respective image frame comprises identifying a subset of measured points associated with the respective image frame, based at least in part on an optical property of each of the subset of measured points.
12 . The system of claim 1 , wherein an optical property of each of the plurality of measured points includes at least one of reflectivity, an intensity of return light, and a reliability of a measurement of a measured point of the plurality of measured points.
13 . A method comprising: generating, by a LIDAR system, a time sequence of image frames, each image frame including a plurality of measured points, each associated with a location in a three dimensional environment; generating a plurality of small feature maps, each small feature map corresponding to a respective image frame in the time sequence of image frames, wherein each small feature map is generated by: segmenting and clustering the plurality of measured points in a respective image frame; and extracting one or more feature points from the respective image frame; generating a first large feature map from a first sequence of the small feature maps by projecting the feature points of each of the first sequence of small feature maps to a world coordinate frame fixed to the three dimensional environment; and generating a second large feature map from a second sequence of the small feature maps by projecting the feature points of each of the second sequence of small feature maps to the world coordinate frame fixed to the three dimensional environment, wherein the second sequence of small feature maps follows the first sequence of small feature maps; and estimating a location of the system within the three dimensional environment.
14 . The method of claim 13 , wherein segmenting the plurality of measured points in the respective image frame further comprises: subdividing the respective image frame into a three dimensional grid of cells; projecting the three dimensional grid of cells onto a two dimensional grid of cells along a height dimension; for each respective cell in the two dimensional grid of cells, determining an average value of an optical property of the measured points within the respective cell; and for each respective measured point of the measured points within the respective cell, (i) determining a difference between a value of the optical property of the respective measured point and an average value of the optical property for the respective cell, and (ii) retaining the respective measured point within the respective cell if the difference exceeds a predetermined threshold value.
15 . The method of claim 14 , wherein the retained respected measured points plurality of measured points are retained for further analysis.
16 . The method of claim 14 , wherein the optical property includes at least one of a reflectivity, an intensity of return light, and a reliability of the measurement.
17 . The method of claim 13 , wherein each of the plurality of measured points includes an indication of a location of the measured point with respect to the LIDAR system.
18 . The method of claim 13 , further comprising estimating an updated current location of the LIDAR system with respect to the world coordinate frame based on the location of the LIDAR system and a location of the LIDAR system at a current image frame with respect to an immediately prior image frame.
19 . The method of claim 13 , wherein clustering the plurality of measured points in the respective image frame comprises clustering a subset of measured points associated with the respective image frame into one or more sub-groups each associated with one or more similar objects.
20 . The method of claim 13 , wherein extracting the one or more feature points from the respective image frame comprises identifying the one or more feature points based on an optical property of each of a subset of measured points.

Description

CROSS-REFERENCES TO RELATED APPLICATIONS The present application is a continuation of U.S. application Ser. No. 16/130,610, now U.S. Pat. No. 11,821,987, entitled “Multiple Resolution, Simultaneous Localization And Mapping Based On 3-D LIDAR Measurements”, filed Sep. 13, 2018, and claims priority to U.S. Provisional patent application Ser. No. 62/558,256 entitled “Multiple Resolution, Simultaneous Localization And Mapping Based On 3-D LIDAR Measurements,” filed Sep. 13, 2017, the subject matter of each which are incorporated herein by reference in their entirety. TECHNICAL FIELD The described embodiments relate to LIDAR based 3-D point cloud measuring systems, and more specifically, efficient mapping of the measured environment and localization of the LIDAR measurement system. BACKGROUND INFORMATION LIDAR systems employ pulses of light to measure distance to an object based on the time of flight (TOF) of each pulse of light. A pulse of light emitted from a light source of a LIDAR system interacts with a distal object. A portion of the light reflects from the object and returns to a detector of the LIDAR system. Based on the time elapsed between emission of the pulse of light and detection of the returned pulse of light, a distance is estimated. In some examples, pulses of light are generated by a laser emitter. The light pulses are focused through a lens or lens assembly. The time it takes for a pulse of laser light to return to a detector mounted near the emitter is measured. A distance is derived from the time measurement with high accuracy. Some LIDAR systems employ a single laser emitter/detector combination combined with a rotating mirror to effectively scan across a plane. Distance measurements performed by such a system are effectively two dimensional (i.e., planar), and the captured distance points are rendered as a 2-D (i.e. single plane) point cloud. In some examples, rotating mirrors are rotated at very fast speeds (e.g., thousands of revolutions per minute). In many operational scenarios, a 3-D point cloud is required. A number of schemes have been employed to interrogate the surrounding environment in three dimensions. In some examples, a 2-D instrument is actuated up and down and/or back and forth, often on a gimbal. This is commonly known within the art as “winking” or “nodding” the sensor. Thus, a single beam LIDAR unit can be employed to capture an entire 3-D array of distance points, albeit one point at a time. In a related example, a prism is employed to “divide” the laser pulse into multiple layers, each having a slightly different vertical angle. This simulates the nodding effect described above, but without actuation of the sensor itself. In many applications it is necessary to see over a broad field of view. For example, in an autonomous vehicle application, the vertical field of view should extend down as close as possible to see the ground in front of the vehicle. In addition, the vertical field of view should extend above the horizon, in the event the car enters a dip in the road. In addition, it is necessary to have a minimum of delay between the actions happening in the real world and the imaging of those actions. In some examples, it is desirable to provide a complete image update at least five times per second. To address these requirements, a 3-D LIDAR system has been developed that includes an array of multiple laser emitters and detectors. This system is described in U.S. Pat. No. 7,969,558 issued on Jun. 28, 2011, the subject matter of which is incorporated herein by reference in its entirety. In many applications, a sequence of pulses is emitted. The direction of each pulse is sequentially varied in rapid succession. In these examples, a distance measurement associated with each individual pulse can be considered a pixel, and a collection of pixels emitted and captured in rapid succession (i.e., “point cloud”) can be rendered as an image or analyzed for other reasons (e.g., detecting obstacles),In some examples, viewing software is employed to render the resulting point clouds as images that appear three dimensional to a user. Different schemes can be used to depict the distance measurements as 3-D images that appear as if they were captured by a live action camera. In an autonomous vehicle application, it is desirable to construct a three dimensional geometrical map of the surrounding environment and locate the LIDAR measurement system within the environment. In many existing examples, the three dimensional map is constructed first and then the LIDAR measurement system is located within the mapped environment. However, this approach is often limited to well controlled, indoor environments or slow moving operational scenarios which are not consistent with actual driving conditions. Improvements in real-time mapping and localization of LIDAR measurement systems are desired. In particular, simultaneous localization and mapping compatible with highly dynamic urban, sub-urban,