# US 10,769,840 B2 · Analysis of point cloud data using polar depth maps and planarization techniques

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

- Number: US 10,769,840 B2
- Document ID: US10769840B2
- Status: Granted
- Kind: B2
- Application number: 16/051,219
- Filed: 2018-07-31
- Published: 2019-08-29
- Granted: 2020-09-08
- Earliest claimed: 2018-02-27
- Assignees: NVIDIA Corporation
- Applicants: Nvidia Corporation
- Inventors: Ishwar Kulkarni; Ibrahim Eden; Michael Kroepfl; David Nister
- Web page: https://patentgrep.com/patent/US10769840B2

## CPC

- G06T 7/20: Analysis of motion (motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51)
- 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
- G01S 17/58: Velocity or trajectory determination systems; Sense-of-movement determination systems
- G01S 17/89: for mapping or imaging
- G01S 17/931: of land vehicles
- G06T 7/30: Determination of transform parameters for the alignment of images, i.e. image registration
- G06T 7/521: from laser ranging, e.g. using interferometry; from the projection of structured light
- G06T 11/10: Texturing; Colouring; Generation of textures or colours (retouching, inpainting or scratch removal G06T5/77)
- G06T 15/04: Texture mapping
- G06V 20/56: exterior to a vehicle by using sensors mounted on the vehicle
- G06V 20/582: {of traffic signs}
- G06V 20/584: {of vehicle lights or traffic lights}
- G06T 2207/10028: Range image; Depth image; 3D point clouds
- G06T 2207/30241: Trajectory
- G06V 2201/12: Acquisition of 3D measurements of objects
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- 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

## Abstract

Various types of systems or technologies can be used to collect data in a 3D space. For example, LiDAR (light detection and ranging) and RADAR (radio detection and ranging) systems are commonly used to generate point cloud data for 3D space around vehicles, for such functions as localization, mapping, and tracking. This disclosure provides improvements for processing the point cloud data that has been collected. The processing improvements include using a three dimensional polar depth map to assist in performing nearest neighbor analysis on point cloud data for object detection, trajectory detection, freespace detection, obstacle detection, landmark detection, and providing other geometric space parameters.

## Claims

### Claim 1

A method of generating geometric space parameters, utilizing a graphics processing unit (GPU), comprising:
transforming point cloud data, for a three dimensional (3D) point representation, to a 3D polar depth map that includes distances between data points of said point cloud data and a sensor for collecting said data points, wherein said point cloud data are not received as said polar depth map;
determining plane information for said data points of said polar depth map;
performing nearest neighbor analysis for said data points utilizing said plane information and said polar depth map; and
generating said geometric space parameters utilizing said nearest neighbor analysis and said polar depth map.

### Claim 2 (depends on 1)

The method as recited in claim 1, further comprising:
storing said plane information and said polar depth map in a two dimensional (2D) depth map, wherein said performing utilizes said stored plane information and said stored polar depth map.

### Claim 3 (depends on 2)

The method as recited in claim 2, wherein said storing utilizes a texture map.

### Claim 4 (depends on 1)

The method as recited in claim 1, further comprising:
utilizing a LiDAR system to generate, at a periodic interval, multiple slices of said point cloud data wherein said 3D point representation is for part of a geometric space associated with said LiDAR system.

### Claim 5 (depends on 4)

The method as recited in claim 4, wherein said transforming, said determining, said performing, and said generating are executed for each of said multiple slices.

### Claim 6 (depends on 1)

The method as recited in claim 1, further comprising:
estimating trajectory equations utilizing said nearest neighbor analysis and said point cloud data; and
calculating moving object parameters utilizing said trajectory equations.

### Claim 7 (depends on 1)

The method as recited in claim 1, wherein said geometric space parameters are parameters for at least one of obstacle detection, freespace detection, and landmark detection.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein said determining plane information utilizes a best fit model over a bounded neighborhood of said data points.

### Claim 9 (depends on 8)

The method as recited in claim 8, wherein said bounded neighborhood utilizes a five by five grid of said data points.

### Claim 10 (depends on 8)

The method as recited in claim 8, wherein said bounded neighborhood utilizes a fixed grid of said data points.

### Claim 11 (depends on 8)

The method as recited in claim 8, wherein said bounded neighborhood utilizes a depth parameter to remove some of said data points from said determining plane information.

### Claim 12

A point cloud data analysis system to compute geometric space parameters for a vehicle, comprising:
a receiver, operable to receive point cloud data of a three dimensional (3D) point representation of at least part of a geometric space surrounding a vehicle; and
a graphics processing unit (GPU) operable to transform said point cloud data to a polar depth map, wherein said polar depth map includes distances between data points of said point cloud data and an initiator for collecting said data points.

### Claim 13 (depends on 12)

The system as recited in claim 12, further comprising:
said initiator, operable to initiate generation of said point cloud data at a periodic interval.

### Claim 14 (depends on 13)

The system as recited in claim 13, wherein said initiator is a LiDAR system.

### Claim 15 (depends on 12)

The system as recited in claim 12, wherein said vehicle is one of an autonomous vehicle and a semi-autonomous vehicle.

### Claim 16 (depends on 12)

The system as recited in claim 12, wherein said geometric space parameters are parameters for at least one of a moving object detection, obstacle detection, freespace detection, and landmark detection.

### Claim 17

A computer program product having a series of operating instructions stored on a non-transitory computer-readable medium that directs a data processing apparatus, when executed thereby, to perform operations, comprising:
receiving point cloud data, wherein said point cloud data are a three dimensional (3D) point representation of at least part of a geometric space surrounding a vehicle;
transforming said point cloud data to a 3D polar depth map that includes distances between data points of said point cloud data and a sensor for collecting said data points;
determining plane information for said data points of said polar depth map;
performing nearest neighbor analysis for said data points utilizing said plane information and said polar depth map; and
computing geometric space parameters utilizing said nearest neighbor analysis and said polar depth map.

### Claim 18 (depends on 17)

The computer program product as recited in claim 17, further comprising:
storing said plane information and said polar depth map in a two dimensional (2D) depth map, wherein said performing utilizes said stored plane information and said stored polar depth map.

### Claim 19 (depends on 17)

The computer program product as recited in claim 17, further comprising:
utilizing a LiDAR system to generate, at a periodic interval, multiple slices of said point cloud data.

### Claim 20 (depends on 19)

The computer program product as recited in claim 19, wherein said receiving, said transforming, said determining, said performing, and said computing are executed on each of said multiple slices.

### Claim 21 (depends on 17)

The computer program product as recited in claim 17, wherein said geometric space parameters are parameters for at least one of moving object detection, obstacle detection, freespace detection, and landmark detection.

### Claim 22 (depends on 17)

The computer program product as recited in claim 17, wherein said determining plane information utilizes a best fit model over a determined neighborhood of said data points, and said determined neighborhood utilizes a depth parameter to remove some of said data points from said determining plane information.

### Claim 23

A method of storing three dimensional (3D) sensor ranging information, comprising:
collecting 3D data points employing a detection and ranging sensor; and
storing said collected 3D data points as a 3D polar depth map, wherein said polar depth map includes distances between said 3D data points and said sensor.

### Claim 24 (depends on 23)

The method as recited in claim 23, further comprising:
transforming said 3D data points to said 3D polar depth map, wherein said received 3D data points are not received as said 3D polar depth map; and
determining plane information for data points of said 3D polar depth map and adjusting said 3D polar depth map utilizing said plane information.