# US 10,768,304 B2 · Processing point clouds of vehicle sensors having variable scan line distributions using interpolation functions

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

- Number: US 10,768,304 B2
- Document ID: US10768304B2
- Status: Granted
- Kind: B2
- Application number: 16/176,567
- Filed: 2018-10-31
- Published: 2019-06-13
- Granted: 2020-09-08
- Earliest claimed: 2017-12-13
- Assignees: Luminar Technologies, Inc.
- Applicants: Luminar Technologies, Inc.
- Inventors: Benjamin Englard; Eric C. Danziger; Austin K. Russell
- Web page: https://patentgrep.com/patent/US10768304B2

## CPC

- G01S 7/40: Means for monitoring or calibrating
- B60W 10/04: including control of propulsion units
- B60W 30/18145: {Cornering}
- B60W 30/18163: {Lane change; Overtaking manoeuvres}
- B60W 50/06: Improving the dynamic response of the control system, e.g. improving the speed of regulation or avoiding hunting or overshoot
- B60W 60/00276: {for two or more other traffic participants}
- G01S 7/4026: {Antenna boresight}
- G01S 7/417: {involving the use of neural networks}
- G01S 7/4808: {Evaluating distance, position or velocity data}
- G01S 7/4817: {relating to scanning}
- G01S 7/4972: {Alignment of sensor}
- G01S 13/42: Simultaneous measurement of distance and other co-ordinates (indirect measurement G01S13/46)
- G01S 13/865: {Combination of radar systems with lidar systems}
- G01S 13/867: {Combination of radar systems with cameras}
- G01S 13/89: for mapping or imaging
- G01S 13/931: of land vehicles
- G01S 17/66: Tracking systems using electromagnetic waves other than radio waves
- G01S 17/86: Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
- G01S 17/931: of land vehicles
- 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/0094: {involving pointing a payload, e.g. camera, weapon, sensor, towards a fixed or moving target}
- G05D 1/0231: {using optical position detecting means (position-fixing by using electromagnetic waves other than radio waves, e.g. optical position detecting means G01S5/16)}
- G05D 1/0248: {in combination with a laser (lasers per se H01S)}
- G06F 18/2163: {Partitioning the feature space}
- G06F 18/217: {Validation; Performance evaluation; Active pattern learning techniques}
- G06F 18/24143: {Distances to neighbourhood prototypes, e.g. restricted Coulomb energy networks [RCEN]}
- G06N 3/045: Combinations of networks
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/08: Learning methods
- G06N 3/086: using evolutionary algorithms, e.g. genetic algorithms or genetic programming
- G06N 3/09: Supervised learning
- G06N 3/092: Reinforcement learning
- G06T 3/4007: based on interpolation, e.g. bilinear interpolation (image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403)
- G06T 7/50: Depth or shape recovery
- G06T 15/08: Volume rendering
- G06T 17/05: Geographic models
- G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation}
- G06V 10/764: using classification, e.g. of video objects
- G06V 10/776: Validation; Performance evaluation
- G06V 10/82: using neural networks
- G06V 20/56: exterior to a vehicle by using sensors mounted on the vehicle
- B60W 2420/403: Image sensing, e.g. optical camera
- B60W 2420/408: Radar; Laser, e.g. lidar
- B60W 2552/15: Road slope, i.e. the inclination of a road segment in the longitudinal direction
- B60W 2554/00: Input parameters relating to objects
- B60W 2554/20: Static objects
- B60W 2554/4026: Cycles
- B60W 2554/4029: Pedestrians
- B60W 2554/60: Traversable objects, e.g. speed bumps or curbs
- B60W 2554/805: Azimuth angle
- B60W 2555/20: Ambient conditions, e.g. wind or rain
- B60W 2555/40: Altitude
- B60W 2555/60: Traffic rules, e.g. speed limits or right of way
- B60W 2720/106: Longitudinal acceleration
- B60W 2720/12: Lateral speed
- B60W 2720/125: Lateral acceleration
- G01S 7/403: {in azimuth, i.e. in the horizontal plane}
- G01S 7/4034: {in elevation, i.e. in the vertical plane}
- G01S 13/426: {Scanning radar, e.g. 3D radar (G01S13/66 takes precedence)}
- G01S 13/86: Combinations of radar systems with non-radar systems, e.g. sonar, direction finder
- G01S 2013/9323: {Alternative operation using light waves}
- G01S 2013/9324: {Alternative operation using ultrasonic waves}
- G05D 1/0257: {using a radar (radar systems designed for anti-collision purposes between land vehicles or between land vehicle and fixed obstacles G01S13/931)}
- G06F 18/214: Generating training patterns; Bootstrap methods, e.g. bagging or boosting
- G06F 18/24: Classification techniques
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06T 7/20: Analysis of motion (motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51)
- G06T 2207/10028: Range image; Depth image; 3D point clouds
- G06T 2207/20081: Training; Learning
- G06T 2207/20084: Artificial neural networks [ANN]
- G06T 2207/30252: Vehicle exterior; Vicinity of vehicle
- G06V 20/59: inside of a vehicle, e.g. relating to seat occupancy, driver state or inner lighting conditions
- 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
- 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
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A method for processing point clouds having variable spatial distributions of scan lines includes receiving a point cloud frame generated by a sensor configured to sense an environment through which a vehicle is moving. The point cloud frame includes scan lines arranged according to a particular spatial distribution. The method also includes either generating an enhanced point cloud frame with a larger number of points than the received point cloud frame, or constructing, by one or more processors and based on points of the received point cloud frame, a three-dimensional mesh. The method also includes generating, by performing an interpolation function on the enhanced point cloud frame or a virtual surface provided by the three-dimensional mesh, a normalized point cloud frame, and generating, using the normalized point cloud frame, signals descriptive of a current state of the environment through which the vehicle is moving.

## Claims

### Claim 1

A method for processing point clouds having variable spatial distributions of scan lines, the method comprising:
receiving a point cloud frame generated by a sensor configured to sense an environment through which a vehicle is moving, the point cloud frame including a plurality of scan lines arranged according to a particular spatial distribution;
constructing, by one or more processors and based on points of the received point cloud frame, a three-dimensional mesh, including forming triangles from subsets of the points of the received point cloud frame;
generating, by one or more processors performing an interpolation function on a virtual surface provided by the three-dimensional mesh, a normalized point cloud frame, including generating points within planes of the triangles and at positions that at least approximate a reference scan line distribution; and
generating, by one or more processors and using the normalized point cloud frame, signals descriptive of a current state of the environment through which the vehicle is moving.

### Claim 2 (depends on 1)

The method of claim 1, wherein the method further comprises generating an enhanced point cloud frame having a larger number of points than the received point cloud frame.

### Claim 3 (depends on 1)

The method of claim 1, wherein the method further comprises:
receiving camera image data generated by a camera disposed on or in the vehicle;
generating, using the camera image data, an enhanced point cloud frame; and
generating another normalized point cloud frame by performing another interpolation function on the enhanced point cloud frame.

### Claim 4 (depends on 3)

The method of claim 3, wherein generating, using the camera image data, the enhanced point cloud frame includes:
transforming the received camera image data to points in a three-dimensional space; and
generating the enhanced point cloud frame using the received point cloud and the points in the three-dimensional space.

### Claim 5 (depends on 3)

The method of claim 3, wherein performing the another interpolation function on the enhanced point cloud frame includes sampling points of the enhanced point cloud frame in a manner that at least approximates a reference scan line distribution.

### Claim 6 (depends on 1)

The method of claim 1, wherein the sensor is a lidar device.

### Claim 7 (depends on 1)

The method of claim 1, wherein the particular spatial distribution of scan lines comprises a uniform distribution, a Gaussian distribution, a multimodal distribution, and/or an arbitrary distribution.

### Claim 8 (depends on 1)

The method of claim 1, wherein generating the signals descriptive of the current state of the environment through which the vehicle is moving includes:
partitioning the normalized point cloud frame into a plurality of portions in accordance with probable boundaries between separate physical objects; and
classifying at least some of the plurality of portions according to object types.

### Claim 9

A non-transitory computer-readable medium storing thereon instructions executable by one or more processors to implement a self-driving control architecture of a vehicle, the self-driving control architecture comprising:
a perception component configured to:
receive a point cloud frame generated by a sensor configured to sense an environment through which a vehicle is moving, the point cloud frame including a plurality of scan lines arranged according to a particular spatial distribution,
construct, based on points of the received point cloud frame, a three-dimensional mesh, including forming triangles from subsets of the points of the received point cloud frame,
generate, by performing an interpolation function on a virtual surface provided by the three-dimensional mesh, a normalized point cloud frame, including generating points within planes of the triangles and at positions that at least approximate a reference scan line distribution, and
generate, using the normalized point cloud frame, signals descriptive of a current state of the environment through which the vehicle is moving.

### Claim 10 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the perception component is further configured to:
receive camera image data generated by a camera disposed on or in the vehicle;
generate, using the camera image data, an enhanced point cloud frame; and
generate another normalized point cloud frame by performing another interpolation function on the enhanced point cloud frame.

### Claim 11 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the perception component is configured to generate, using the camera image data, the enhanced point cloud frame at least by:
transforming the received camera image data to points in a three-dimensional space; and
generating the enhanced point cloud frame using the received point cloud and the points in the three-dimensional space.

### Claim 12 (depends on 10)

The non-transitory computer-readable medium of claim 10, wherein the perception component is configured to perform the another interpolation function on the enhanced point cloud frame at least by sampling points of the enhanced point cloud frame in a manner that at least approximates a reference scan line distribution.

### Claim 13 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the sensor is a lidar device.

### Claim 14 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the perception component is configured to generate the signals descriptive of the current state of the environment through which the vehicle is moving at least by:
partitioning the normalized point cloud frame into a plurality of portions in accordance with probable boundaries between separate physical objects; and
classifying at least some of the plurality of portions according to object types.

### Claim 15 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the particular spatial distribution of scan lines comprises a uniform distribution, a Gaussian distribution, a multimodal distribution, and/or an arbitrary distribution.

### Claim 16

A vehicle comprising:
a sensor configured to sense an environment through which the vehicle is moving and generate point cloud frames;
one or more operational subsystems; and
a computing system configured to:
receive a point cloud frame generated by the sensor, the point cloud frame including a plurality of scan lines arranged according to a particular spatial distribution,
construct, based on points of the received point cloud frame, a three-dimensional mesh, including forming triangles from subsets of the points of the received point cloud frame,
generate, by performing an interpolation function on a virtual surface provided by the three-dimensional mesh, a normalized point cloud frame, including generating points within planes of the triangles and at positions that at least approximate a reference scan line distribution,
generate, using the normalized point cloud frame, signals descriptive of a current state of the environment through which the vehicle is moving,
generate driving decisions based on the signals descriptive of the current state of the environment, and
cause the one or more operational subsystems of the vehicle to maneuver the vehicle in accordance with the generated driving decisions.

### Claim 17 (depends on 16)

The vehicle of claim 16, wherein the vehicle further comprises a camera disposed on or in the vehicle, and wherein the computing system is further configured to:
receive camera image data generated by the camera;
generate, using the camera image data, an enhanced point cloud frame; and
generate another normalized point cloud frame by performing another interpolation function on the enhanced point cloud frame.

### Claim 18 (depends on 17)

The vehicle of claim 17, wherein the computing system is configured to generate, using the camera image data, the enhanced point cloud frame at least by:
transforming the received camera image data to points in a three-dimensional space; and
generating the enhanced point cloud frame using the received point cloud and the points in the three-dimensional space.

### Claim 19 (depends on 16)

The vehicle of claim 16, wherein the sensor is a lidar device.

### Claim 20 (depends on 16)

The vehicle of claim 16, wherein the particular spatial distribution of scan lines comprises a uniform distribution, a Gaussian distribution, a multimodal distribution, and/or an arbitrary distribution.

### Claim 21 (depends on 16)

The vehicle of claim 16, wherein the computing system is configured to generate the signals descriptive of the current state of the environment through which the vehicle is moving at least by:
partitioning the normalized point cloud frame into a plurality of portions in accordance with probable boundaries between separate physical objects; and
classifying at least some of the plurality of portions according to object types.