# US 9,521,431 B2 · Method and a system for wavelet based processing > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,521,431 B2 - Document ID: US9521431B2 - Status: Granted - Kind: B2 - Application number: 12/448,733 - Filed: 2008-01-03 - Published: 2011-02-10 - Granted: 2016-12-13 - Earliest claimed: 2007-01-03 - Assignees: Numeri Ltd. - Applicants: Ilan Bar-On; Oleg Kostenko - Inventors: Ilan Bar-On; Oleg Kostenko - Web page: https://patentgrep.com/patent/US9521431B2 ## CPC - H04N 19/647: {using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]} - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract A method for compressing digital data. The method comprises creating a plurality of wavelet coefficients associated with an input signal by iteratively performing a plurality of wavelet transforms to a plurality of sub-bands of the input signal, adjusting a zerotree dataset according to each the wavelet transform, and encoding the plurality of wavelet coefficients according to the zerotree dataset. ## Claims ### Claim 1 A method of defining relations between sub-bands of a sequence of wavelet transforms applied to an original n-dimensional signal, comprising: a. defining a list of sub-bands initially containing the original n-dimensional signal with a null label; b. repeatedly: (1) removing any sub-band with its label from said list of sub-bands; (2) creating a new low sub-band and a new high sub-band by respectively applying a pair of a low-pass and a high-pass 1D(1-dimensional) wavelet filters to said removed sub-band in the direction of dimension k of said sub-band's n dimensions; (3) defining a label for the new low sub-band as the removed sub-band's label concatenated with the symbol Lk, and a label for the new high sub-band as the removed sub-band's label concatenated with the symbol Hk; (4) inserting said two newly created low and high sub-bands, with their labels, to the list of sub-bands; c. defining the phase-space information of a given sub-band as the number and direction of symbols “Hk” appearing in the sub-band's label; d. partitioning the sub-bands of the list into groups of equal phase-space sub-bands; and e. defining a DAG (Directed Acyclic Graph) data structure comprising DAG relations between the sub-bands in each group. ### Claim 2 (depends on 1) The method of claim 1, wherein said DAG relations between the sub-bands in each group are defined first by dimension ordering relations and then, in case of equality, by lexicographic ordering relations. ### Claim 3 (depends on 1) The method of claim 1, wherein said DAG relations between the sub-bands in each group are defined by origin ordering relations and enforcing a dimension ordering constraint by recursively applying additional transformations. ### Claim 4 (depends on 1) The method of claim 1, wherein said DAG relations between the sub-bands in each group are defined by origin ordering relations and enforcing the “Ruling Class” constraint, that all sub-bands whose origin point is smaller than the sub-band end point be of smaller dimension ordering, by applying the required additional transformations. ### Claim 5 (depends on 1) The method of defining the DAG data structure of claim 1, comprising: defining an initial group consisting of one sub-band having a null label, said sub-band being the original n-dimensional signal, and the corresponding DAG of said initial group; and repeatedly applying the following operations: a. removing an input sub-band from its DAG group of equally phase-space sub-bands; b. applying a low and high pass wavelet filters to said input sub-band to create a new low sub-band having the same phase-space information as that of the input sub-band, and a new high sub-band having a different phase-space information than that of the input sub-band; c. inserting said low sub-band to the DAG data structure of said input sub-band in accordance with that DAG relations; d. inserting said high sub-band to the DAG data structure of the respective group of sub-bands having that same phase-space information, in accordance with that DAG relations; or creating a new group consisting of said high sub-band only and the corresponding DAG consisting of said high sub-band only, if a group having that same phase-space information does not exist. ### Claim 6 (depends on 2) The method of constructing the DAG data structure of claim 2, comprising: defining an initial group consisting of one sub-band having a null label, said sub-band being the original signal, and the corresponding DAG of said initial group; and repeatedly applying the following operations: a. removing an input sub-band from its DAG group of equally phase-space sub-bands; b. applying a low and high pass wavelet filters to said input sub-band to create a new low sub-band having the same phase-space information as that of the input sub-band, and a new high sub-band having a different phase-space information than that of the input sub-band; c. inserting said low sub-band to the DAG data structure of said input sub-band in accordance with the dimension ordering and the lexicographical ordering constraints; d. inserting said high sub-band to the DAG data structure of the respective group of sub-bands having that same phase-space information in accordance with the dimension ordering and the lexicographical ordering constraints; or -creating a new group consisting of said high sub-band only and the corresponding DAG consisting of said high sub-band only, if a group having that same phase-space information does not exist. ### Claim 7 (depends on 3) The method of constructing the DAG data structure of claim 3, comprising: defining an initial group consisting of one sub-band having a null label, said sub-band being the original signal, and the corresponding DAG of said initial group; and repeatedly applying the following operations: a. removing an input sub-band from its DAG group of equally phase-space sub-bands; b. applying a low and high pass wavelet filters to said input sub-band to create a new low sub-band having the same phase-space information as that of the input sub-band, and a new high sub-band having a different phase-space information than that of the input sub-band; c. inserting said low sub-band to the DAG data structure of said input sub-band in accordance with the origin ordering constraint, maintaining the dimension ordering constraint by recursively applying additional wavelet transformations and updating the respective DAG data structures accordingly; d. inserting said high sub-band to the DAG data structure of the respective group of sub-bands having that same phase-space information, in accordance with the origin ordering constraint, maintaining the dimension ordering constraint by recursively applying additional wavelet transformations and updating the respective DAG data structures accordingly; or creating a new group consisting of said high sub-band only and the corresponding DAG consisting of said high sub-band only, if a group having that same phase-space information does not exist. ### Claim 8 (depends on 4) The method of constructing the DAG data structure of claim 4, comprising: defining an initial group consisting of one sub-band having a null label, said sub-band being the original signal, and the corresponding DAG of said initial group; and repeatedly applying the following operations: a. removing an input sub-band from its DAG group of equally phase-space sub-bands; b. applying a low and high pass wavelet filters to said input sub-band to create a new low sub-band having the same phase-space information as that of the input sub-band, and a new high sub-band having a different phase-space information than that of the input sub-band; c. inserting said low sub-band to the DAG data structure of said input sub-band in accordance with the origin ordering constraint, maintaining the “Ruling Class” constraint by iteratively applying the additional required wavelet transformations and updating the respective DAG data structures accordingly; d. inserting said high sub-band to the DAG data structure of the respective group of sub-bands having that same phase-space information, in accordance with the origin ordering constraint, maintaining the “Ruling Class” constraint by iteratively applying the additional required wavelet transformations and updating the respective DAG data structures accordingly; or creating a new group consisting of said high sub-band only and the corresponding DAG consisting of said high sub-band only, if a group having that same phase-space information does not exist. ### Claim 9 (depends on 1) The method of claim 1, wherein said wavelet transforms and said defining the DAG data structures are performed concurrently. ### Claim 10 (depends on 1) The method of claim 1, wherein said n-dimensional signal is selected from a group consisting of: an image, a sequence of images, a video stream, a three dimensional image, and a four dimensional image. ### Claim 11 (depends on 1) The method of claim 1, further comprising after defining the DAG data structures in step (e), defining respective tree data structures corresponding to said DAG data structures. ### Claim 12 (depends on 5) The method of claim 5, further comprising after inserting said sub-bands into the corresponding DAG data structures at steps c) and d), updating respective tree data structures corresponding to said DAG data structures. ### Claim 13 (depends on 6) The method of claim 6, further comprising after inserting said sub-bands into the corresponding DAG data structures at steps c) and d), updating respective tree data structures corresponding to said DAG data structures. ### Claim 14 (depends on 7) The method of claim 7, further comprising after inserting said sub-bands into the corresponding DAG data structures at steps c) and d), updating respective tree data structures corresponding to said DAG data structures. ### Claim 15 (depends on 8) The method of claim 8, further comprising after inserting said sub-bands into the corresponding DAG data structures at steps c) and d), updating respective tree data structures corresponding to said DAG data structures. ### Claim 16 (depends on 1) The method of claim 1, further comprising after defining the DAG data structure in step e), encoding the wavelet coefficients of each sub-band in said DAG, said encoding method selected from the group consisting of: a scalar quantization method, a vector quantization method, a Huffman coding method, an arithmetic coding method and a zero tree method. ### Claim 17 (depends on 5) The method of claim 5, further comprising after defining the DAG data structures in steps c) and d), encoding the wavelet coefficients of said DAG sub-bands, said encoding method selected from the group consisting of: a scalar quantization method, a vector quantization method, a Huffman coding method, an arithmetic coding method, and a zero tree method. ### Claim 18 (depends on 6) The method of claim 6, further comprising after defining the DAG data structures in steps c) and d), encoding the wavelet coefficients of said DAG sub-bands, said encoding method selected from the group consisting of: a scalar quantization method, a vector quantization method, a Huffman coding method, an arithmetic coding method, and a zero tree method. ### Claim 19 (depends on 7) The method of claim 7, further comprising after defining the DAG data structures in steps c) and d), encoding the wavelet coefficients of said DAG sub-bands, said encoding method selected from the group consisting of: a scalar quantization method, a vector quantization method, a Huffman coding method, an arithmetic coding method, and a zero tree method. ### Claim 20 (depends on 8) The method of claim 8, further comprising after defining the DAG data structures in steps c) and d), encoding the wavelet coefficients of said DAG sub-bands, said encoding method selected from the group consisting of: a scalar quantization method, a vector quantization method, a Huffman coding method, an arithmetic coding method, and a zero tree method. ### Claim 21 (depends on 1) The method of claim 1, further comprising after defining the DAG sub-band groups in step e), performing optimal rate control analysis of said wavelet coefficients of said DAG sub-band groups, said analysis further guiding the sequence of wavelet transforms to perform. ### Claim 22 (depends on 5) The method of claim 5, further comprising after defining the DAG sub-band groups in steps c) and d), performing optimal rate control analysis of said wavelet coefficients of said DAG sub-band groups, said analysis further guiding the sequence of wavelet transforms to perform. ### Claim 23 (depends on 6) The method of claim 6, further comprising after defining the DAG sub-band groups in steps c) and d), performing optimal rate control analysis of said wavelet coefficients of said DAG sub-band groups, said analysis further guiding the sequence of wavelet transforms to perform. ### Claim 24 (depends on 7) The method of claim 7, further comprising after defining the DAG sub-band groups in steps c) and d), performing optimal rate control analysis of said wavelet coefficients of said DAG sub-band groups, said analysis further guiding the sequence of wavelet transforms to perform. ### Claim 25 (depends on 8) The method of claim 8, further comprising after defining the DAG sub-band groups in steps c) and d), performing optimal rate control analysis of said wavelet coefficients of said DAG sub-band groups, said analysis further guiding the sequence of wavelet transforms to perform.