Data compression and decompression

• US 5,546,477 A
• Filed: 03/30/1993
• Issued: 08/13/1996
• Est. Priority Date: 03/30/1993
• Status: Expired due to Term

• Current Assignee: Creative Technology Ltd.
• Original Assignee: Klics Limited, Media Vision, Inc.
• Inventors: Knowles, Gregory P., Lewis, Adrian S.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/040,301
• Time in Patent Office: 1,232 Days
• Field of Search: 382/41, 382/44, 382/56, 382/27, 382/42, 382/205, 382/278, 382/279, 382/233, 382/244, 382/242, 382/260, 382/264
• US Class Current: 382/242
• CPC Class Codes: G06F 17/14 Fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms for correlation function computation G06F17/156; spectrum analysers G01R23/16
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/619 the transform being operated outside the prediction loop
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/635 characterised by filter definition or implementation details

Abstract

A compression and decompression method using a wavelet decomposition, frequency based tree encoding, tree based motion encoding, frequency weighted quantization, Huffman encoding, and tree based activity estimation for bit rate control. Forward and inverse quasi-perfect reconstruction transforms are used to generate the wavelet decomposition and to reconstruct data values close to the original data values. The forward and inverse quasi-perfect reconstruction transforms utilize special filters at the boundaries of the data being transformed and/or inverse transformed.

Claims

1. A method for compressing a first image represented by a first matrix of pixels into an encoded data sequence for transmission and/or storage, where each of said pixels is represented by an input digital signal data point, and for decompressing the encoded data sequence into a plurality of output digital signal data points corresponding to a second matrix of pixels representing a second image, wherein said input digital signal data points at or near boundary of the image comprise a plurality of boundary subsequences and said input digital signal data points not at or near the boundary of the image comprise a plurality of non-boundary subsequences, comprising the steps of:

(a) identifying each boundary subsequence and each non-boundary subsequence of a first image represented by a first matrix of pixels, each of said pixels represented by an input digital signal data point, said input digital signal data points forming said first image having a first combined data length;

(b) filtering each said boundary subsequence using a low pass boundary forward quasi-perfect reconstruction filter and a high pass boundary forward quasi-perfect reconstruction filter to produce a plurality of filtered boundary subsequences including interleaved low and high frequency values at one or more octaves;

(c) filtering each said non-boundary subsequence using a low pass non-boundary forward quasi-perfect reconstruction filter and a high pass non-boundary forward quasi-perfect reconstruction filter to produce a plurality of filtered nonboundary subsequences including interleaved low and high frequency values at one or more octaves, said interleaved low and high frequency values of said filtered boundary subsequences and said filtered non-boundary subsequences forming a filtered digital signal array having a plurality of filtered digital signal data points;

(d) selecting interleaved low and high frequency values at one or more octaves from said filtered digital signal array via a plurality of counters and predefined sub-indices;

(e) encoding said selected interleaved low and high frequency values at one or more octaves to produce encoded data values; and

(f) repeating steps (d) and (e) for all the interleaved low and high values at one or more octaves in said filtered digital signal array to accumulate the encoded data values to produce an encoded data sequence having a second combined data length where said second combined data length is smaller than said first combined data length.

2. A method as recited in claim 1 wherein the decompressing of said encoded data sequence is comprised of the following steps:

(g) evaluating the encoded data values in said encoded data sequence to identify the placement of reproduced interleaved low and high frequency values in a second filtered digital signal array;

(h) decoding the encoded data values in said encoded data sequence to produce said second filtered digital signal array having a plurality of reproduced filtered boundary subsequences and a plurality of reproduced filtered non-boundary subsequences;

(i) using an inverse boundary quasi-perfect reconstruction filter to compose reconstructed boundary subsequences from said reproduced filtered boundary subsequences; and

(j) using an inverse non-boundary quasi-perfect reconstruction filter to compose reconstructed nonboundary subsequences from said reproduced filtered non-boundary subsequences, said reconstructed boundary subsequences and said reconstructed non-boundary subsequences forming output digital signal data points for a second matrix of pixels representing a second image.

3. A method as recited in claim 2 wherein said non-boundary inverse quasi-perfect reconstruction filter includes an even interleaved inverse quasi-perfect reconstruction filter and an odd interleaved inverse quasi-perfect reconstruction filter.

4. A method as recited in claim 3 wherein said even interleaved inverse quasi-perfect reconstruction filter composes a reconstructed digital signal data point D_2x from said filtered digital signal data points in accordance with the following relationship:

space="preserve" listing-type="equation">D.sub.2x =-d*H.sub.x-1 +a*G.sub.x-1 +b*H.sub.x +c*G.sub.x

wherein G_x and G_x-1 are high pass filtered digital signal data points, H_x and H_-1 are low pass filtered digital signal data points, and a, b, c, and d are coefficients.

5. A method as recited in claim 3 wherein said odd interleaved inverse quasi-perfect reconstruction filter composes a reconstructed digital signal data point D_2x-1 from said filtered digital signal data points in accordance with the following relationship:

space="preserve" listing-type="equation">D.sub.2x-1 =c*H.sub.x-1 -b*G.sub.x-1 +a*H.sub.x +d*G.sub.x

wherein G_x and G_x-1 are high pass filtered digital signal data points, H_x and H_x-1 are low pass filtered digital signal data points, and a, b, c, and d are coefficients.

6. A method as recited in claim 2 wherein said boundary inverse quasi-perfect reconstruction filter includes a start inverse quasi-perfect reconstruction filter and an end inverse quasi-perfect reconstruction filter.

7. A method as recited in claim 6 wherein said start inverse quasi-perfect reconstruction filter composes a reconstructed boundary digital signal data point D_O from said filtered digital signal data points in accordance with the following relationship:

space="preserve" listing-type="equation">D.sub.0 =4*

wherein G_O is a high pass filtered boundary data point, H₀ is a low pass filtered boundary data point, and (b-a) and (c-d) are coefficients.

8. A method as recited in claim 6 wherein said end inverse quasi-perfect reconstruction filter composes a reconstructed boundary digital signal data point D_B from said filtered digital signal data points in accordance with the following relationship:

space="preserve" listing-type="equation">D.sub.B =4,

wherein G_B is a high pass filtered boundary data point, H_B is a low pass filtered boundary data point, and (a+b) and (c+d) are coefficients.

9. A method as recited in claim 2 wherein four coefficients and combinations thereof are used in said filters to produce a filtered digital data point, the coefficients being a (11/32), b (19/32), c (5/32), and d (3/32).

10. A method as recited in claim 1 wherein each said boundary subsequence corresponds to either the start or end of a row or column of a two-dimensional visual image.

11. A method as recited in claim 1 wherein each of the filters uses a plurality of coefficients and a plurality of consecutive input digital signal data points to produce a filtered digital signal data point for said filtered digital signal array, each of said filtering steps comprising the substeps of:

multiplying said plurality of coefficients by particular ones of said consecutive input digital signal data points to produce a plurality of weighed signal values; and

summing said plurality of weighted signal values to produce the filtered digital signal data point.

12. A method as recited in claim 1 wherein four coefficients and combinations thereof are used in said filters to produce a filtered digital data point, the coefficients being a (11/32), b (19/32), c (5/32), and d (3/32).

13. A method as recited in claim 1 wherein said high pass and low pass boundary forward quasi-perfect reconstruction filters use a first plurality of coefficients to produce filtered digital signal data points, and said high pass and low pass non-boundary forward quasi-perfect reconstruction filters use a second plurality of coefficients to produce the filtered digital signal data points, the number of coefficients in said second plurality of coefficients being greater than the number of coefficients in said first plurality of coefficients.

14. A method as recited in claim 1 wherein said high pass non-boundary forward quasi-perfect reconstruction filter produces a high pass filtered digital signal data point G_x/2, in accordance with the following relationship:

space="preserve" listing-type="equation">G.sub.x/2 =d*D.sub.x-1 +c*D.sub.x -b*D.sub.x+1 +a*D.sub.x+2,

where D_x-1, D_x, D_x+1, and D_x+2 are consecutive input digital signal data points, and a, b, c, and d are coefficients.

15. A method as recited in claim 1 wherein said low pass non-boundary forward quasi-perfect reconstruction filter produces a low pass filtered digital signal data point H_x/2, in accordance with the following relationship:

space="preserve" listing-type="equation">H.sub.x/2 =a*D.sub.x-1 +b*D.sub.x +c*D.sub.x+1 -d*D.sub.x+2,

where D_x-1, D_x, D_x-1, and D_x-2 are consecutive input digital signal data points, and a, b, c, and d are coefficients.

16. A method as recited in claim 1 wherein said high pass boundary forward quasi-perfect reconstruction filter includes a high pass start boundary forward quasi-perfect reconstruction filter and a high pass end boundary quasi-perfect reconstruction filter, and wherein said low pass boundary forward quasi-perfect reconstruction filter includes a low pass start boundary forward quasi-perfect reconstruction filter and a low pass end boundary forward quasi-perfect reconstruction filter.

17. A method as recited in claim 16 wherein said high pass start boundary forward quasi-perfect reconstruction filter produces a filtered boundary digital signal data point G₀ by substituting D₀, a boundary data point, for D_-1, a non-exist data point, in accordance with the following relationship:

space="preserve" listing-type="equation">G.sub.0 =(c+d)*D.sub.0 -b*D.sub.1 +a*D.sub.2,

where D₀, D₁ and D₂ are boundary input digital signal data points, and a, b, (c+d) are coefficients.

18. A method as recited in claim 16 wherein said low pass start boundary forward quasi-perfect reconstruction filter produces a filtered boundary digital signal data point by substituting D₀, a boundary data point, for D_-1, a non-exist data point, in accordance with the following relationship:

space="preserve" listing-type="equation">H.sub.0 =(a+b)*D.sub.0 +c*D.sub.1 -d*D.sub.2

where D₀, D₁, and D₂ are boundary input digital signal data points, and (a+b), c, and d are coefficients.

19. A method as recited in claim 16 wherein said high pass end boundary forward quasi-perfect reconstruction filter produces a filtered boundary digital signal data point G_B by substituting D_B, a boundary data point, for D_c, a non-exist data point, in accordance with the following relationship:

space="preserve" listing-type="equation">G.sub.B =d*D.sub.x-2 +c*D.sub.x-1 +(a-b)*D.sub.B,

where D_x-2, D_x-1 and D_B are boundary input digital signal data points, and (a-b), c, and d are coefficients.

20. A method as recited in claim 16 wherein said low pass end boundary forward quasi-perfect reconstruction filter produces a filtered boundary digital signal data point H_B by substituting D_B, a boundary data point, for D_c, a non-exist data point, in accordance with the following relationship:

space="preserve" listing-type="equation">H.sub.B =a*D.sub.x-2 +b*D.sub.x-1 +(c-d)*D.sub.B

where D_x-2, D_x-1, and D_B are boundary input digital signal data points, and a, b, and (c-d) are coefficients.

21. A method as recited in claim 16 wherein four coefficients and combinations thereof are used in said filters to produce a filtered digital data point, the coefficients being a (11/32), b (19/32), c (5/32), and d (3/32).

22. A method as recited in claim 1 wherein said encoding step further includes the steps of:

quantizing said encoded data values by a quality factor to produce a quantized digital data sequence; and

huffman encoding said quantized digital data sequence to produce huffman encoded values, wherein said huffman encoded values are accumulated to generate said encoded data sequence.

23. A method as recited in claim 22 wherein prior to said quantizing step an overall quality factor Q is selected to estimate a compression ratio of the input digital signal data points to a plurality of encoded data points within said encoded data sequence, wherein said filtered digital data array is stored in blocks within a tree structure, comprising the steps of:

(1) generating a plurality of quality factors as a function of said filtered digital data points of said selected blocks and a predefined threshold limit;

(2) producing an overall quality factor, Q, as a function of said plurality of quality factors and a predetermined bit rate for a particular frame of image, wherein said quality factors indicate an estimate of the amount of data to be encoded for the frame from the filtered digital data points, and said bit rate indicates the amount of data permitted for the frame; and

(3) using said overall quality factor in said encoding step wherein said plurality of blocks of said filtered digital signal data points are quantized as a function of said overall quality factor to produce an index, said index being subsequently encoded.

24. A method as recited in claim 1 wherein said encoding step includes the substeps of:

comparing a plurality of said filtered digital signal data points with a threshold value to determine a mode within a plurality of modes; and

generating a token representing said plurality of said filtered digital signal data points in accordance with the determined mode.

25. A method as recited in claim 1 wherein said filtered digital signal array is stored in a predetermined format including a plurality of N x N blocks, wherein said blocks are addressed via a plurality of counters interconnected to incrementally address said blocks.

26. A method as recited in claim 1 wherein six coefficients and combinations thereof are used by said filters in the filtering of said input digital signal sequence, the six coefficients being a (30/128), b (73/128), c (41/128), d (12/128), e (7/128), and f (3/128).

27. A method as recited in claim 1 wherein a quality factor Q is selected to vary the amount of data encoded by said encoding step, and wherein a higher quality factor results in the generation of more encoded data points in said encoded data sequence, and a lower quality factor results in the generation of a lower number of encoded data points in said encoded data sequence.

28. A method as recited in claim 1 wherein said high pass quasi-perfect reconstruction filter having a plurality of coefficients and said low pass quasi-perfect reconstruction filter having a plurality of coefficients are generated from a wavelet function, comprising the steps of:

determining a low pass wavelet filter and a high pass wavelet filter from said wavelet function, said low pass wavelet filter having a plurality of real number coefficients, said high pass wavelet filter have a plurality of real number coefficients;

choosing the coefficients of said low pass quasi-perfect reconstruction filter to be integer values such that when a test sequence of data points each having a value of 1 is input to said low pass quasi-perfect reconstruction filter the output of said low pass quasi-perfect reconstruction filter is equal to a value taken from a set of values generated by powers of 2; and

choosing the coefficients of the high pass quasi-perfect reconstruction filter to be integer values such that when a test sequence of data values each having a value of 1 is processed by said high pass quasi-perfect reconstruction filter the output of said high pass quasi-perfect reconstruction filter is equal to 0, whereby each of the plurality of coefficients of said low pass quasi-perfect reconstruction filter closely approximates a corresponding one of said plurality of real number coefficients of said low pass wavelet filter, and whereby each of the plurality of coefficients of said high pass quasi-perfect reconstruction filter closely approximates a corresponding one of said plurality of coefficients of said high pass wavelet filter.

29. A method as recited in claim 1 wherein an overall quality factor Q is selected to estimate a compression ratio of the input digital signal data points to a plurality of encoded data points within said encoded data sequence, wherein said filtered digital data array is stored in blocks within a tree structure, comprising the steps of:

(1) generating a plurality of quality factors as a function of said filtered digital data points of said selected blocks and a predefined threshold limit;

(2) producing an overall quality factor, Q, as a function of said plurality of quality factors and a predetermined bit rate for a particular frame of image, wherein said quality factors indicate an estimate of the amount of data to be encoded for the frame from the filtered digital data points, and said bit rate indicates the amount of data permitted for the frame; and

(3) using said overall quality factor in said encoding step wherein said plurality of blocks of said filtered digital signal data points are quantized as a function of said overall quality factor to produce an index, said index being subsecuently encoded.

30. A method as recited in claim 29 wherein said filtered digital signal array includes filtered digital data points at different octaves created by filtering said input digital signal data points a number of times, wherein each of said octaves having a low frequency component and high frequency components, and wherein said selected blocks are the blocks in the high frequency components of the highest octave in said octaves.

31. A method as recited in claim 29 wherein said filtered digital signal array includes filtered digital data points at different octaves created by filtering said input digital signal data points a number of times, wherein each of said octaves having a low frequency component and high frequency components, and wherein said selected blocks are the blocks in the high frequency components of the highest octave in said octaves.

32. A method as recited in claim 1 wherein four consecutive input digital signal data points, D_x D_x+3 are used to produce filtered digital signal data points, and an input digital signal data point, D_x+4, is skipped before the next four consecutive input digital signal data points, D_x+5 -D_x+8, are used for filtering.

33. A method as recited in claim 1 wherein said tree encoding step includes a still image tree encoding mode and a video image tree encoding mode.

34. A method as recited in claim 33 wherein said filtered digital signal array is stored in a predetermined tree structure with at least one branch having a plurality of N x N blocks and at least one other branch having a plurality of N x N blocks, wherein said still image tree encoding mode includes a still submode and a void submode, and includes the steps of:

(a) selecting a branch from said tree structure;

(b) entering said still submode to evaluate said selected branch of said tree structure;

(c) selecting a block from said selected branch of said tree structure, a value being derived from said block;

(d) comparing said block value to a threshold value to determine whether said block is interesting or not, said block is interesting if said block value is greater than said threshold value, said block is not interesting if said block value is smaller than said threshold value;

(e) if the block is interesting, generating a token representing said still submode and data representing said block;

(f) if the block is not interesting, entering said void submode, generating a token representing said void submode, and selecting another branch; and

(g) repeating steps (b)-(f) until all branches are processed.

36. A method as recited in claim 33 wherein a plurality frames of video images contains a first frame and a plurality of next frames, wherein said filtered digital signal array for a frame of video image is stored in a predetermined tree structure having at least one branch with at least one N x N block, wherein said video image tree encoding mode includes a send submode and a void submode, and includes the steps of:

(a) entering said still image tree encoding mode to encode said first frame of said video image and storing said encoded first frame in an old frame storage buffer;

(b) inputting a next frame into a new frame storage buffer;

(c) selecting a branch from said next frame stored in said new frame storage buffer;

(d) entering said send submode to evaluate a block;

(e) selecting a block from said branch and deriving a value from said block;

(f) evaluating said block value to generated at least one compared value and comparing said compared value to at least one video threshold value to determine a next mode;

(g) generating a token representing said next mode;

(h) encoding said block if the next mode is said send submode;

(i) selecting another branch if the next mode is said void mode;

(j) repeating steps (e)-(i) for all branches of said second frame;

(k) relabeling said new frame storage buffer as an old frame storage buffer and said old frame storage buffer as said new frame storage buffer; and

(l) repeating steps (b)-(k) until all next frames are processed.

37. A method as recited in claim 1 wherein said filtered digital signal array contains filtered digital signal data points representing interleaved high and low frequency values at different octaves and wherein said encoding step includes a tree encoding step where filtered digital data points are stored in a tree structure with at least one branch, said tree structure having a top end and a bottom end, said filtered digital signal data points at a lower octave being stored at the top end of said tree structure, and said filtered digital signal data point at a higher octave being stored at the bottom end of said tree structure.

38. A method as recited in claim 1 wherein said plurality of counters are comprised of one or more interconnected counters, wherein by using said counters and said indices said filtered digital signal array is traversed.

39. A method as recited in claim 1 wherein said plurality of counters are comprised of a first set of two two-bit interconnected counters and a second set of two interconnected counters, each of said counters in said first set of counters having a least-significant bit and a most-significant-bit, wherein said first set of counters are aligned vertically where the least-significant-bit of said counters generate an x-coordinate for traversing said array and the most-significant-bit of said counters generate a y-coordinate for traversing said array, wherein said second set of counters having a first counter interconnected to a second counter are aligned horizontally where said first counter generates an x-coordinate and said second counter generates a y-coordinate, wherein in conjunction with said predefined indices, one or more sets of coordinates for said filtered digital signal data points are accessed, and wherein said interconnecting counters providing a sequence for incrementing count from one counter to the interconnected counter.

40. A method as recited in claim 39 wherein said predefined indices, sub_x and sub_y, are sub-band dependent, where the sub-bands are comprised of low-pass HH, low-pass HG, high pass GH, and high pass GG, and said indices having the following values corresponding to the sub-bands:

space="preserve" listing-type="tabular">______________________________________ sub-band sub.sub.x sub.sub.y ______________________________________ low pass HH 0 0 low pass HG 0 1 high pass GH 1 0 high pass GG 1 1 ______________________________________

41. A method as recited in claim 39 wherein, in generating said x and y coordinates in a first octave, only one counter in said first set of counters are used, said predefined indices are shifted one place to the left and the least-significant-bits of said indices are filled with zeros.

42. A method as recited in claim 1 wherein said filtering steps remove information outside of the human visual frequency range.

35. A method as recited in 34 wherein said still image tree encoding mode further includes a low-pass still submode wherein said filtered digital signal array includes filtered digital data points at different octaves created by filtering said input digital signal data points a number of times, wherein each of said octaves having a low frequency component and high frequency components, said still image tree encoding mode includes the steps of:

(a) entering said low-pass-still submode to evaluate a block of said low frequency component;

(b) selecting a block from said component, a value being derived from said block;

(c) comparing said block value to a low-pass-filtered threshold value to determine whether said block is interesting or not, said block is interesting if said block value is greater than said threshold value, said block is not interesting if said block value is smaller than said threshold value;

(d) if the block is interesting, generating data representing said block; and

(e) repeating steps (b)-(d) for all blocks in said low frequency component.

43. A method for compressing and decompressing a video image comprised of a plurality of pixels forming a two-dimensional grid space having a plurality of columns and a plurality of rows, wherein each of said columns forming a vertical line and each of said rows forming a horizontal line, and each said line having a starting edge, a non-edge portion, and an ending edge, comprising the steps of:

a) identifying a starting edge, a non-edge portion, and an ending edge for a line of a video image having a plurality of video lines and a plurality of horizontal lines;

b) filtering said starting edge of said line to retain a first frequency range of said starting edge at a first resolution, wherein said first frequency range being within the human visual frequency range;

c) filtering said non-edge portion of said line to retain said first frequency range of said non-edge portion at said first resolution;

d) filtering ending edge of said line to retain said first frequency range of said ending edge at said first resolution;

e) repeating steps b)-d) for each of said horizontal lines of said video image;

f) repeating steps b)-d) for each of said vertical lines of said video image;

g) repeating steps b)-f) a plurality of times using a set of second frequency ranges at corresponding second resolutions to produce a two dimensional array of filtered digital signal data points;

h) selecting filtered digital signal data points at different octaves from said array by using a plurality of counters and predefined indices; and

i) encoding said selected filtered digital signal data points to produce encoded data values;

j) repeating steps h) and i) for all of said filtered digital signal data points in said array to accumulate the encoded data values to produce an encoded data sequence for storage or transmission.