Point cloud data compression using a space-filling curve
AssigneeGoogle Inc.
InventorsMichael Hemmer, Ondrej Stava
Life of this patent
Estimating the term…
Abstract
Techniques of data compression involve ordering the points of a point cloud according to distance along a space-filling curve. Advantageously, a space-filling curve has the property that points close in distance along the curve are close together in Euclidean space. Thus, differences between points ordered by distance along such a curve, e.g., a Hilbert curve, will be close. When the curve is fractal, i.e., self-similar at all levels, the differences will be small even when the points are very unevenly clustered throughout the point cloud. Such small differences will provide greatly improved compression to the resulting delta-encoded set of points.
Claims20
A method, comprising:
- identifying, by controlling circuitry of a computer, portions of a space-filling curve with a plurality of points in space;
- defining, by the controlling circuitry, a sequence for encoding the plurality of points in space according to positions of each of the plurality of points along the space-filling curve;
- and
- generating, by the controlling circuitry, an encoding of the plurality of points as arranged in the sequence.
A computer program product comprising a nontransitive storage medium, the computer program product including code that, when executed by processing circuitry of a computer, causes the processing circuitry to perform a method, the method comprising:
- identifying, by controlling circuitry of a computer, portions of a space-filling curve with a plurality of points in space;
- defining, by the controlling circuitry, a sequence for encoding the plurality of points in space according to positions of each of the plurality of points along the space-filling curve;
- and
- generating, by the controlling circuitry, an encoding of the plurality of points as arranged in the sequence.
An electronic apparatus comprising:
- memory;
- and
- controlling circuitry coupled to the memory, the controlling circuitry being configured to:
- identify portions of a space-filling curve with a plurality of points in space;
- define a sequence for encoding the plurality of points in space according to positions of each of the plurality of points along the space-filling curve;
- and
- generate an encoding of the plurality of points as arranged in the sequence.
Dependencies are inferred from the claim text.