# US 2013/0159263 A1 · Lossy compression of data points using point-wise error constraints

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

- Number: US 2013/0159263 A1
- Document ID: US20130159263A1
- Status: Published application
- Kind: A1
- Application number: 13/329,290
- Filed: 2011-12-18
- Published: 2013-06-20
- Earliest claimed: 2011-12-18
- Assignees: Numerica Corporation
- Inventors: Randy C. Paffenroth; Ryan Nong; Woody D. Leed; Scott M. Lundberg
- Web page: https://patentgrep.com/patent/US20130159263A1

## CPC

- G06T 9/007: {Transform coding, e.g. discrete cosine transform}
- H04N 19/90: using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- H04N 19/34: Scalability techniques involving progressive bit-plane based encoding of the enhancement layer, e.g. fine granular scalability [FGS]
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method for compressing a cloud of points with imposed error constraints at each point is disclosed. Surfaces are constructed that approach each point to within the constraint specified at that point, and from the plurality of surfaces that satisfy the constraints at all points, a surface is chosen which minimizes the amount of memory required to store the surface on a digital computer.

## Claims

### Claim 1

A computer implemented method, comprising the step of constructing a representation xεRn of a cloud of points bεRm with imposed error constraints uεRm at each point in an over-complete dictionary AεRm×n such that |Ax−b|u.

### Claim 2 (depends on 1)

The method of claim 1, wherein the representation x is compressed with respect to the original point cloud b, such that the amount of electronic memory required to store x is less than that for b.

### Claim 3 (depends on 1)

The method of claim 1, wherein the representation x is the solution to the constrained l1 optimization problem,
min
x


x

1
.

### Claim 4 (depends on 3)

The method of claim 3, further comprising the step of introducing two slack variables s1 and s2 to transform the constrained l1 optimization problem into
min
y


y

1
such that Gy=h, where y=[x s1 s2]T,
G
=
[
A
α


I
0
-
A
0
α


I
]
,
and
h
=
[
b
+
u
-
b
+
u
]
.

### Claim 5 (depends on 4)

The method of claim 4, further comprising the step of using the split Bregman algorithm to solve the resulting constrained l1 optimization problem,
min
y


y

1
.

### Claim 6 (depends on 5)

The method of claim 5, wherein A is an overcomplete dictionary of n orthonormal bases.

### Claim 7 (depends on 6)

The method of claim 6, wherein A=[F I], where F is an orthonormal Fourier basis and I is the Delta basis.

### Claim 8 (depends on 6)

The method of claim 6, wherein n>2.

### Claim 9 (depends on 8)

The method of claim 8, wherein the orthonormal bases are chosen from Fourier, Wavelet and Delta bases.

### Claim 10 (depends on 1)

The method of claim 1, wherein said point clouds are chosen from digital elevation map data points and light detection and ranging data points.

### Claim 11

A computer implemented lossy compression of data points, comprising the step of constructing a representation xεRn of a cloud of points bεRm with imposed error constraints uεRm at each point in an over-complete dictionary AεRm×n such that |Ax−b|u.

### Claim 12 (depends on 11)

The method of claim 11, wherein the representation x is compressed with respect to the original point cloud b, such that the amount of electronic memory required to store x is less than that for b.

### Claim 13 (depends on 11)

The method of claim 11, wherein the representation x is the solution to the constrained l1 optimization problem,
min
x


x

1
.

### Claim 14 (depends on 13)

The method of claim 13, further comprising the step of introducing two slack variables s1 and s2 to transform the constrained l1 optimization problem into
min
y


y

1
such that Gy=h, where y=[x s1 s2]T,
G
=
[
A
α


I
0
-
A
0
α


I
]
,
and
h
=
[
b
+
u
-
b
+
u
]
.

### Claim 15 (depends on 14)

The method of claim 14, further comprising the step of using the split Bregman algorithm to solve the resulting constrained l1 optimization problem,
min
y


y

1
.

### Claim 16 (depends on 15)

The method of claim 15, wherein A is an overcomplete dictionary of n orthonormal bases.

### Claim 17 (depends on 16)

The method of claim 16, further comprising the step of quantizing the result of the constrained l1 optimization problem,
min
y


y

1
into binary coefficients.

### Claim 18 (depends on 17)

The method of claim 17, further comprising the step of decompressing the quantized binary coefficients.

### Claim 19 (depends on 16)

The method of claim 16, wherein A=[F I], where F is an orthonormal Fourier basis and I is the Delta basis.

### Claim 20 (depends on 16)

The method of claim 16, wherein n>2.

### Claim 21 (depends on 20)

The method of claim 20, wherein the orthonormal bases are chosen from Fourier, Wavelet and Delta bases.

### Claim 22 (depends on 11)

The method of claim 11, wherein said point clouds are chosen from digital elevation map data points and light detection and ranging data points.