Compressing a signal that represents a physical attribute

Patent metadata

Field	Value
Publication number	US-10410377-B2
Application number	US-201715702042-A
Country	US
Kind code	B2
Filing date	Sep 12, 2017
Priority date	Sep 13, 2016
Publication date	Sep 10, 2019
Grant date	Sep 10, 2019

Abstract

The invention notably relates to a computer-implemented method for compressing data representing values of a physical attribute in a predetermined space. The method comprises providing a signal that includes a mapping from leaf cells of a hierarchical subdivision of the predetermined space each onto a respective coefficient representative of a value of the physical attribute at the respective leaf cell. The method also comprises determining a discrete wavelet transform of the signal and encoding the determined discrete wavelet transform. The method provides an improved way to compress a modeled object that represents a real object.

First claim

The invention claimed is:

1. A computer-implemented method for compressing data representing values of a physical attribute in a predetermined space (S), the method comprising:
providing a signal (c N,000 ) that includes a mapping (c N,000 (⋅)) from leaf cells (α N 1 α N 2 . . . α N N ∈C(L N (octree N (S))), α N n,n∈(1, . . . , N) ∈{0,1} 3 ) of a hierarchical subdivision (octree N (S)) of the predetermined space each onto a respective coefficient (c N,000 (α N 1 α N 2 . . . α N N )) representative of a value of the physical attribute at the respective leaf cell;
determining a discrete wavelet transform of the signal with a predetermined basis of wavelet convolution filters (f I (d,s), I∈{0,1} 3 or I∈{L,H} 3 ), thereby recursively determining subbands (c D,I , I∈{0,1} 3 or I∈{L,H} 3 ), including a low-pass subband (c D,000 ), by passing, at each current recursion (D∈{N−1, N−2, . . . , 0}), each wavelet convolution filter (f I ) over the low-pass subband)(c D+1,000 ) of the previous recursion (D+1), starting from the signal (c N,000 );
the subbands (c D,I ) determined at a current recursion (D) each including a respective mapping (c D,I (⋅)) from leaf cells (α D 1 α D 2 . . . α D D ∈C(L D (octree D (S))), α D n,n∈{1, . . . , D} ∈{0,1} 3 ), of a same hierarchical subdivision (octree D (S)) of which the hierarchical subdivision (octree D+1 (S)) of the previous recursion (D+1) is a subdivision, each given leaf cell (α D 1* α D 2* . . . α D D* ) being mapped onto a respective coefficient (c D,I )(α D 1* α D 2* . . . α D D* )) determined, during the passing of a respective wavelet convolution filter (f I ) over the low-pass subband)(c D+1,000 ) of the previous recursion (D+1), by applying the respective wavelet convolution filter (f I ) to the coefficients (c D+1,000 (α D 1* α D 2* . . . α D D* α D+1 D+1 )) of the low-pass subband (c D+1,000 ) of the previous recursion (D+1) mapped onto from leaf cells (α D 1* α D 2* . . . α D D* α D+1 D+1 ∈C(L D+1 (octree D+1 (S))), α D+1 D+1 ∈{0,1} 3 )) of the hierarchical subdivision (octree D+1 (S)) of the previous recursion (D+1) that subdivide the given leaf cell (α D 1* α D 2* . . . α D D* ); and
encoding the determined discrete wavelet transform.

2. The method of claim 1 , wherein the wavelet convolution filters (f I ) have a compact support ({0,1} 3 ).

3. The method of claim 2 , wherein at least at one given recursion (D) the passing encounters at least one leaf cell (α D+1 1′ α D+1 2′ . . . α D+1 D+1′ ∉C(L D+1 (octree D+1 (S)))) of the low-pass subband)(c D+1,000 ) of the previous recursion (D+1) mapped onto no coefficient, the determining of a discrete wavelet transform including assigning a value (c′ D+1,000 (α D+1 1′ α D+1 2′ . . . α D+1 D+1′ )) to the encountered cell, the assigned value being inputted to each of the wavelet convolution filters.

4. The method of claim 3 , wherein the assigned value is determined with respect to a criterion related to forcing one or more zeros in the subbands determined at the given recursion (D).

5. The method of claim 4 , wherein the criterion (|c N,000 (⋅)|=Σ ∈{0,1} 3 ,D∈{N−1, N−2, . . . , 0} |c D,I (⋅)|) is that the number of coefficients of all the subbands determined at the given recursion (D) not forced to zero is equal to the number of coefficients of the low-pass subband of the previous recursion (D+1) not forced to zero.

6. The method of claim 2 , wherein the size of the compact support is smaller or equal to the minimal value of the divider of the hierarchical subdivision.

7. The method of claim 6 , wherein the divider of the hierarchical subdivision has a constant value (2 3 ) and the size of the compact support is equal to the constant value of the divider of the hierarchical subdivision.

8. A computer-implemented method for decompressing a compressed signal obtainable by a computer-implemented method for compressing data representing values of a physical attribute in a predetermined space, the method comprising:
providing a signal that includes a mapping from leaf cells of a hierarchical subdivision of the predetermined space each onto a respective coefficient representative of a value of the physical attribute at the respective leaf cell;
determining a discrete wavelet transform of the signal with a predetermined basis of wavelet convolution filters, thereby recursively determining subbands, including a low-pass subband, by passing, at each current recursion, each wavelet convolution filter over the low-pass subband of the previous recursion, starting from the signal,
the subbands determined at a current recursion each including a respective mapping from leaf cells, of a same hierarchical subdivision of which the hierarchical subdivision of the previous recursion is a subdivision, each given leaf cell being mapped onto a respective coefficient determined, during the passing of a respective wavelet convolution filter over the low-pass subband of the previous recursion, by applying the respective wavelet convolution filter to the coefficients of the low-pass subband of the previous recursion mapped onto from leaf cells of the hierarchical subdivision of the previous recursion that subdivide the given leaf cell; and
encoding the determined discrete wavelet transform.

9. A device comprising:
a non-transitory memory having recorded thereon a computer program comprising instructions for performing a computer-implemented method for compressing data representing values of a physical attribute in a predetermined space, the method comprising:
providing a signal that includes a mapping from leaf cells of a hierarchical subdivision of the predetermined space each onto a respective coefficient representative of a value of the physical attribute at the respective leaf cell;
determining a discrete wavelet transform of the signal with a predetermined basis of wavelet convolution filters, thereby recursively determining subbands, including a low-pass subband, by passing, at each current recursion, each wavelet convolution filter over the low-pass subband of the previous recursion, starting from the signal,
the subbands determined at a current recursion each including a respective mapping from leaf cells, of a same hierarchical subdivision of which the hierarchical subdivision of the previous recursion is a subdivision, each given leaf cell being mapped onto a respective coefficient determined, during the passing of a respective wavelet convolution filter over the low-pass subband of the previous recursion, by applying the respective wavelet convolution filter to the coefficients of the low-pass subband of the previous recursion mapped onto from leaf cells of the hierarchical subdivision of the previous recursion that subdivide the given leaf cell; and
encoding the determined discrete wavelet transform.

10. A non-transitory data storage medium having stored thereon a computer program comprising instructions for performing the computer-implemented method for compressing data representing values of the physical attribute in the predetermined space according to claim 8 .

11. The device of claim 9 , further comprising a processor coupled to the memory, the device being a computer system.

12. A device comprising:
a non-transitory memory having recorded thereon a computer program comprising instructions for performing a computer-implemented method for decompressing a compressed signal obtainable by a computer-implemented method for compressing data representing values of a physical attribute in a predetermined space, the method comprising:
providing a signal that includes a mapping from leaf cells of a hierarchical subdivision

Assignees

• Dassault Systemes
• Dassault Systems

Inventors

• Tuffreau Jean-Julien
• Boulkenafed Malika

Classifications

• H04N19/63

  using sub-band based transform, e.g. wavelets · CPC title

• G06T9/40 Primary

  Tree coding, e.g. quadtree, octree · CPC title

• G06T9/001

  Model-based coding, e.g. wire frame · CPC title

• H03M7/40 Primary

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title