Wavelet transformation of dithered quantized/reduced color pixels for color bit depth image compression and decompression

[0002] This is a divisional of application Ser. No. 09/038,562, filed Mar. 11, 1998.

[0003] This application claims the benefit of U.S. Provisional Application No. 60/040,241, filed Mar. 11, 1997, System and Method for Still Image Compression, which is incorporated herein by reference.

[0004] The present invention relates generally to digital image compression/decompression, and particularly, to a wavelet-based system and method of image compression and decompression.

[0005] Nearly every computer user needs to store, transfer, and view images. These images include still images, or pictures, as well as video images, which are sequences of still images displayed in a manner that depicts motion. The enormous size of image files leads to serious file management limitations. For example, a single still image (equivalent to a video frame) displayed by a rectangular array of picture elements (pixels) arranged in 640 rows and 800 columns, with the color of each pixel represented by twenty-four bits, would require over 1.5 megabytes of digital memory to store. One solution to this problem is high-quality data compression technology. Essentially, image compression mathematically transforms a grid of image pixels into a new, much smaller set of digital values holding the information needed to regenerate the original image or data file.

[0006] In addition to imaging systems, compression technology can be incorporated into “video on demand” systems, such as video servers. Compression technology can also be applied to streaming video, which is the real-time capture and display of video images over a communications link. Applications for streaming video include video telephones, remote security systems, and other types of monitoring systems.

[0007] Several standards for compressing real-time video currently exist. The H.263 standard for real-time video is an industry standard based upon the discrete co-sign transform (DCT). DCT is also the basis for both of the public domain image compression standards, MPEG (Motion Picture Experts Group) and JPEG (Joint Photographic Experts Group). Although the DCT approach performs interframe coding adequately, its compression ratio and speed can be improved upon.

[0008] Various other types of data compression have been developed in recent years. Conventional data compression techniques are generally referred to as being either “lossless” or “lossy”, depending upon whether data is discarded in the compression process. Examples of conventional lossless compression techniques include Huffman encoding, arithmetic encoding, and Fano-Shannon encoding. With a lossless compression, the decompression process will reproduce all bits of the original image. Lossless compression is important for images found in such applications as medical and space science. In such situations, the designer of the compression algorithm must be very careful to avoid discarding any information that may be required or even useful at some later point.

[0009] Lossy compression, in contrast, provides greater efficiency over lossless compression in terms of speed and storage, as some data is discarded. As a result, lossy techniques are employed where some degree of inaccuracy relative to the input data is tolerable. Accordingly, lossy compression is frequently used in video or commercial image processing. Two popular lossy image compression standards are the MPEG and JPEG compression methods.

[0010] The wavelet transform has proven to be one of the most powerful tools in the field of data compression. Theoretically, the wavelet transformation is lossless, but since all computers have only finite precision even when using floating point calculations, most of the transformations are lossy in practice. On the other hand, integer calculations are much faster than floating point for virtually all computers; and integer computations are much easier to implement in hardware, which is more important in some applications. While integers require less memory than real numbers, the direct use of integers in conventional wavelet transforms and their inverses typically causes an unacceptable loss of accuracy. Accordingly, there is a need for a wavelet-based compression technique that permits lossless or near-lossless data compression, yet retains the speed and memory advantages of integer arithmetic.

[0011] It is an advantage of the present invention to provide a system and method of wavelet-based data compression that permits integer computations in a computer without significant loss of accuracy. This is accomplished by using an integer reversible wavelet transform that possesses a property of precision preservation (PPP). The integer reversible transform greatly reduces the computer resources needed to compress and decompress images, as well as the time required to perform the same.

[0012] It is an advantage of the present invention to provide a system and method of wavelet-based image compression that is suitable for both still and video images.

[0013] It is also an advantage of the present invention to provide a system and method of image compression that is capable of selectively performing lossless and lossy compression of either color or gray-scale images.

[0014] According to one aspect of the invention, a wavelet-based image compression method can be implemented using a software program. Compression is accomplished by performing a wavelet transform on an input digital image. The resulting wavelet components are compared to a threshold value; coefficients falling below the threshold are discarded. The remaining coefficients are quantized. The quantized coefficients are then compressed using an entropy encoding technique, such as arithmetic, run length, or Huffman encoding, or a combination of Huffman and run length encoding. The wavelet transform can be an integer reversible wavelet transform derived using a lifting scheme or correction method, while the quantization scheme can be sub-band oriented. To further enhance the speed of the compression scheme, input color image pixels can be reduced using a color table. In addition, color pixels can be transformed between color spaces prior to wavelet transformation.

[0015] According to another aspect of the invention, a corresponding method of decompression is provided.

[0016] According to another aspect of the present invention, a compression method is provided that allows user selected portions of an image to be compressed to different image qualities, thereby permitting non-uniform image compression.

[0017] According to another aspect of the present invention, a compression method is provided that permits compression quality to be based on image specific parameters.

[0018] According to another aspect of the present invention, a method of compressing images using a “split and merge” technique is provided.

[0019] According to further aspect of the present invention, an image compression system includes a compressor configured to generate a compressed image based on an integer wavelet transform derived using either a lifting scheme or correction method. The compressor can be implemented using one or more electronic components, such as application specific integrated circuits (ASICs), microprocessors, discrete logic components, or any combination of the aforementioned.

[0020] According to another aspect of the present invention, a corresponding image decompression system is provided.

[0021] The invention is pointed out with particularity in the appended claims. However, other features of the invention will become more apparent, and the invention will be best understood by referring to the following detailed description in conjunction with the accompanying drawings, in which:

[0022] FIG. 1 illustrates a flow diagram for a method of compressing an image that is in accordance with an embodiment of the present invention;

[0023] FIGS. 2-4 depict wavelet coefficients for various levels of decomposition;

[0024] FIG. 5 illustrates a flow diagram of a method of decompressing an image that has been compressed using the method of FIG. 1;

[0025] FIG. 6 is a block diagram of a system that can incorporate a software program implementing any of the methods shown in FIGS. 1, 5, and 8-13 in accordance with a second embodiment of the present invention;

[0026] FIG. 7 is a block diagram of a system for compressing and decompressing an image in accordance with another embodiment of the present invention;

[0027] FIG. 8 illustrates a flow diagram of a method compressing an image that is in accordance with a further embodiment of the present invention;

[0028] FIG. 9 illustrates a flow diagram of a method for decompressing an image that has been compressed according to the method of FIG. 8;

[0029] FIG. 10 illustrates a flow diagram of a method of compressing an image in accordance with a further embodiment of the present invention;

[0030] FIG. 11 illustrates a flow diagram of a method of decompressing an image that has been compressed according to the method of FIG. 10;

[0031] FIG. 12 illustrates a flow diagram of a method of compressing an image that is in accordance with a further embodiment of the present invention; and

[0032] FIG. 13 illustrates a flow diagram of a method for decompressing an image that has been compressed according to the method of FIG. 12.

[0033] Referring now to the drawings, and in particular to FIG. 1, there is shown a flow diagram of a method for compressing an image that conforms to a first embodiment of the invention. In step 20, a digital image is received from an image source. The digital image consists of a matrix of values representing an array of pixels. Specifically, the array of pixels represents a still image or a frame from a video image. In step 22, the image is optionally displayed on an appropriate viewing device, such as a computer or video display unit having a flat panel or cathode ray tube (CRT). Next, in step 24, color and wavelet transformations of the image take place. The image transformations involved in this step include color transform for color images only, and wavelet transform for both gray level images and color images. In step 26, the values representing the transformed images are quantized and compared to thresholds. Values falling outside the threshold are discarded. In step 28, the remaining quantized values are encoded to remove redundant information, creating a compressed image file. Next, in step 30 the compressed image file is generated as output.

[0034] Referring to the color transformation of step 24, digital color images are typically based on an RGB color model, such as is commonly used with TIFF or BMP images. In order to get a higher compression ratio, the RGB pixels are transformed to other color models, such as YIQ or YUV models. The method can convert RGB inputs into YIQ or YUV color spaces according to the following relationships. $\mathrm{RGB}\mathrm{to}\mathrm{YIQ}\text{:}\left[\begin{array}{c}Y\\ I\\ Q\end{array}\right]=\left[\begin{array}{ccc}0.299& 0.587& 0.114\\ -0.596& -0.275& 0.321\\ 0.212& -0.523& 0.311\end{array}\right]\left[\begin{array}{c}R\\ G\\ B\end{array}\right]$ $\mathrm{RGB}\mathrm{to}\mathrm{YUV}\text{:}\left[\begin{array}{c}Y\\ U\\ V\end{array}\right]=\left[\begin{array}{ccc}0.299& 0.587& 0.114\\ 0.148& -0.289& 0.439\\ 0.615& -0.515& -0.1\end{array}\right]\left[\begin{array}{c}R\\ G\\ B\end{array}\right]$

[0035] In the YIQ color space, there is one luminescence (Y) and two color planes (I, Q). The Y component is critical, while the I-Q components are less sensitive to error introduced by data compression.

[0036] The wavelet transform (also referred To as wavelet decomposition) operates on the converted color space signals. The purpose of the wavelet transform is to represent the original image by a different basis to achieve the objective of decorrelation. There are many different wavelet transforms that can be used in this step. For instance, the reversible integer wavelet transform described herein below is a preferred wavelet transform. However, to develop a better understanding of the preferred transform, the following alternative wavelet transform is first described. $\mathrm{Let}{C}^0=\left[C_{\mathrm{jk}}^0\right](j-0,\dots ,M-1;k=0,\dots ,$

[0037] N−1) represent the original, uncompressed image, where M and N are integers which have the common factor 2^l(L is a positive integer). A one-level wavelet decomposition, where L=1, results in the four coefficient quadrants as shown in FIG. 2. Each quadrant represents a set of wavelet coefficients.

[0038] Quadrant C¹represents the blurred image of the original image C⁰, where C¹=[C_jk¹](j=0, . . . , M/2−1; k=0, . . . , N/2−1). HD¹represents the horizontal high frequency part of C⁰, while VD¹represents the vertical high frequency part of C⁰, and DD¹represents the diagonal high frequency part of C⁰. The decomposition can be iteratively repeated L times to obtain different levels of decomposition. For example, for L=2, C⁰is set to equal C¹. The iterative formula for computing a decomposition is given as follows:

[0039] (1) Let {overscore (C)}⁰=rC⁰, r>0 is a factor which can be changed for different needs.

[0040] (2) Transform for image columns: $\begin{array}{cc}\mathrm{For}k=0,\dots ,N-1,\mathrm{calculate}& \\ \{\begin{array}{c}{\tilde{d}}_{0k}^1=\frac{{\stackrel{\_}{C}}_{1k}^0-{\stackrel{\_}{C}}_{0K}^0}{2},\\ {\tilde{d}}_{\mathrm{jk}}^1=\frac{1}{4}\left({\stackrel{\_}{C}}_{2j-1,l}^{-0}-2{\stackrel{\_}{c}}_{2j,k}^{-0}+{\stackrel{\_}{c}}_{2j+1,k}\right),j=1,\dots ,\frac{M}{2}-1.\end{array}& \left(3.1\mathrm{.1}\right)\\ \mathrm{For}k=0,\dots ,N-1,\mathrm{calculate}& \\ \{\begin{array}{c}{\tilde{C}}_{0k}^1=C_{l,k}^0-\frac{{\tilde{d}}_{\mathrm{ok}}+{\tilde{d}}_{l,k}}{2},\\ {\tilde{c}}_{\mathrm{jk}}^1={\stackrel{\_}{c}}_{2j+l,k}-\frac{{\tilde{d}}_{\mathrm{jk}}^1+{\tilde{d}}_{j+l,k}}{2},j=1,\dots ,\frac{M}{2},\\ \frac{{\tilde{C}}_{N-2}^{-1}}{2},k={\tilde{C}}_{N-1,k}^{-0}-\frac{{\tilde{d}}_{N-2}}{2},k.\end{array}& \left(3.1\mathrm{.2}\right)\end{array}$

[0041] (3) Transform for rows: $\begin{array}{cc}\begin{array}{c}\mathrm{For}j=0,\dots M/2-1,\mathrm{computing}\\ \{\begin{array}{c}{\mathrm{hd}}_{j,0}^1=\frac{{\tilde{c}}_{\mathrm{j1}}-{\tilde{c}}_{\mathrm{j0}}^1}{2},\\ {\mathrm{hd}}_{\mathrm{jk}}^1=\frac{1}{4}\left({\tilde{c}}_{j,2k-1}^1-2{\tilde{c}}_{j,2k+1},{\tilde{c}}_{j,2k+1}\right),k=1\dots \frac{N}{2}-1.\end{array}\end{array}\mathrm{and}& \text{(3.1.3)}\\ \{\begin{array}{c}{c}_{\mathrm{jo}}^1={\tilde{c}}_{j,1}^1-\frac{{\mathrm{hd}}_{\mathrm{j0}}^1+{\mathrm{hd}}_{j,k+1}^1}{2},\\ c_{\mathrm{jk}}^1=c_{j,2k+1}^1-\frac{{\mathrm{hd}}_{j,k}^1+{\mathrm{hd}}_{j,k+1}^1}{2},\dots ,\frac{M}{2}-2,\\ c_{j{,}_{\frac{N-2}{2}}}={\tilde{c}}_{j,N-1}^1{\mathrm{hd}}_j{,}_{\frac{N-2}{2}},\end{array}\mathrm{For}j=0,\dots ,M/2-1,\mathrm{computing}& \text{(3.1.4)}\\ \{\begin{array}{c}{\mathrm{dd}}_{j,0}^1=\frac{{\tilde{d}}_{j,1}^1-{\tilde{d}}_{\mathrm{j0}}^1}{2},\\ {\mathrm{dd}}_{\mathrm{jk}}^1=\frac{1}{4}\left({\tilde{d}}_{j,2k-1}^1-2{\tilde{d}}_{j,2k}+{\tilde{d}}_{j,2k+1}^1\right),k=1\dots \frac{N}{2}-1.\end{array}\mathrm{and}& \text{(3.1.5)}\\ \{\begin{array}{c}{\mathrm{vd}}_{\mathrm{j0}}^1={\tilde{d}}_{j,1}^1-\frac{{\mathrm{dd}}_{\mathrm{j0}}^1+{\mathrm{dd}}_{\mathrm{j1}}^1}{2},\\ {\mathrm{vd}}_{\mathrm{jk}}^1={\tilde{d}}_{j,2k+1}^1-\frac{{\mathrm{dd}}_{j,k}^1+{\mathrm{dd}}_{j,k+1}^1}{2},k=1,\dots ,\frac{M}{2}-2,\\ {\mathrm{vd}}_{j{,}_{\frac{N-2}{2}}}={\tilde{d}}_{N-1,k}-{\mathrm{dd}}_{\frac{j,N-2}{2}}^1,\end{array}& \text{(3.1.6)}\\ C^1=\left[c_{j,k}^1\right],{\mathrm{HD}}^1=\left[{\mathrm{hd}}_{j,k}^1\right],{\mathrm{VD}}^1\left[\upsilon d_{j,k}^1\right]\mathrm{and}\mathrm{DD}=\left[{\mathrm{dd}}_{j,k}^1\right],j=0,\dots ,\frac{M}{2}-1k=0,\dots ,\frac{M}{2}-1& \left(4\right)\end{array}$

[0042] Remark: If it is necessary, we also can use matrix multiply Wavelet Coefficient Image of 1 levels=W₁C⁰W₁^T. Here, W¹is the transform matrix for 1 level wavelet decomposition.

[0043] FIG. 3 depicts a three-level wavelet decomposition, where L=3.

[0044] In step 26, the first loss in accuracy occurs. Both thresholding and quantization reduce accuracy with which the wavelet coefficients are represented. In step 26, the wavelet coefficients are matched against threshold values, and if the values are less than the established threshold values specified, then the resultant value is set to zero.

[0045] An important feature of the invention is that the wavelet coefficients are then quantized to a number of levels depending upon which quadrant is being processed, and the desired compression or quality factor. This can be very important in image compression, as it tends to make many coefficients zeros, especially those for high spatial frequencies, which reduces the size of a compressed image.

[0046] A multilevel uniform thresholding method can be used as described below.

[0047] Let T=(t₁, . . . , t_L, t_L+1) be the chosen thresholds, where t_tis the threshold for l the (l=I, . . . , L) level and t_L+1is a threshold for blurred image C^L. Thresholding sets every entry in the blocks C^L, HD^l, VD^land DD^l(l=I, . . . L) to be zero if its absolute value is not greater than the corresponding threshold.

[0048] For color images, three threshold vectors which correspond three different color planes, such as y, I and Q, are used.

[0049] The step of quantization essentially scales the wavelet coefficients and truncates them to a predetermined set of integer values. The quantization table shown in Table 1 can be used.

[0050] In Table 1, the entries q^l_HDare quantization factors for blocks HD^l(l=I, . . . L), q^l_VDand q^l_DDfor blocks VD^land DD^l(l=I, . . . , L) respectively, and the factor q_c^L+1is for the most blurred image C^L. The factors can be integers between 0 and 255. The quantization scheme for the block HD^l(l=I, . . . , L) is $\begin{array}{cc}{\stackrel{\_}{\mathrm{hd}}}_{j,k}^1=\mathrm{round}\frac{{\mathrm{hd}}_{j,k}^1·q_{\mathrm{HD}}^1}{{\max }_{\mathrm{HD}}^1},j=0,\dots ,\frac{M}{2^l}-1;k=0,\dots ,\frac{N}{2^l}-1.& \left(3.2\mathrm{.1}\right)\end{array}$

[0051] Here, ${\stackrel{\_}{\mathrm{hd}}}_{j,k}^l\left(j=0,\dots ,\frac{M}{2^l}-1;,k=0,\dots ,\frac{N}{2^l}-1\right)$

[0052] are quantized wavelet coefficients of block HD^l(l=1, . . . , L) ${\max }_{\mathrm{HD}}^1=\max \left(\left|{\mathrm{hd}}_{j,k}^1\right|\right),0⪯j⪯\left(M/2^l-1\right)$ $0⪯k⪯\left(N/2^l-1\right)$

[0053] and the function round(x) gives the nearest integer of x. Equation (3.2.1) is used for quantization of the other blocks (quadrants).

[0054] For color images, there are three separate quantization tables for the different color bands.

[0055] In step 28, entropy compression is applied to the resultant coefficients using either Arithmetic, Run Length, or Huffman, or Huffman and Run Length combined. The compression algorithm can be selected at run-time by the user, based on the desired compression ratio and the amount of time required to get the selected level of compression. The encoding step includes the entropy compression as well as coefficient rearranging.

[0056] An alternative process to that shown in FIG. 1 includes an optional down sampling of the IQ color planes. This down sampling may be done once or twice to produce two image planes either one-fourth or one-sixteenth the size of the original plane. If the down sampling is done, it will be accomplished prior to the wavelet transform of step 24. The down sampling reduces the compression time and size of the image file.

[0057] FIG. 5 shows a corresponding method for decompressing an image compressed using the method of FIG. 1. In step 40, the compressed image file is input. In step 42, the image is decoded. Next, in step 44 the values are de-quantized. Next, in step 46 inverse color and wavelet transformations are performed on the de-quantized data. In step 48, optional image post-processing takes place to refine the decompressed image. In step 50, the decompressed image is displayed.

[0058] The decoding of step 42 is the inverse operation of the encoding of step 28. Similarly, it can be divided into two parts: Entropy decoding (Huffman or arithmetic), and coefficient rearranging.

[0059] The decoding step produces quantized wavelet coefficients in 3*L+1 blocks. Dequantizing (step 44) uses the same quantization table as quantizing (Table 1), and the scheme as follows: for l=I, . . . , L $\begin{array}{cc}{\underset{\_}{\mathrm{hd}}}_{j,k}^l=\frac{{\stackrel{\_}{\mathrm{hd}}}_{j,k}^l·{\max }_{\mathrm{HD}}^l}{q_{\mathrm{HD}}},j=0,\dots ,\frac{M}{2^l}-1;k=0,\dots ,\frac{N}{2^l}-1.& \left(4.2\mathrm{.1}\right)\end{array}$

[0060] Equation (4.2.1) produces the approximate coefficients for the blocks HD^l(l=I, . . . , L), which are shown in FIG. 3. The dequantizing scheme for other blocks is similar to 4.1.2).

[0061] In step 46, the inverse wavelet transform, also referred to as wavelet reconstruction, is performed prior to the inverse color transformation. FIG. 4 depicts a one-level wavelet reconstruction.

[0062] The wavelet reconstruction can be iteratively performed for various levels of decomposition, according to the following equations.

[0063] (1) Inverse transform for rows: $\begin{array}{cc}\mathrm{For}j=0,\dots ,\frac{M}{2}-1,\mathrm{calculate}& \\ \{\begin{array}{c}{\tilde{d}}_{j,1}^1=\upsilon d_{j,0}^1+\frac{{\mathrm{dd}}_{j,0}^1+{\mathrm{dd}}_{j,1}^1}{2},\\ {\tilde{d}}_{j,2k+1}^1=\upsilon d_{\mathrm{jk}}^1+\frac{{\mathrm{dd}}_{j,k}^1-{\mathrm{dd}}_{j,k+1}^1}{2},k=1,\dots ,\frac{M}{2}-2,\\ {\tilde{d}}_{N-1,k}=\upsilon d_{j,\frac{N-1}{2}}+{\mathrm{dd}}_{j,\frac{N-2}{2}}^1.\end{array}\mathrm{and}& \text{(4.3.1)}\\ \{\begin{array}{c}{\tilde{d}}_{j,0}^1=d_{j,1}^1-2{\mathrm{dd}}_{j,0}^1,\\ {\tilde{d}}_{j,2k}^1=\frac{{\tilde{d}}_{j,2k-1}^1-{\tilde{d}}_{j,2k+1}^1}{2}-2{\mathrm{dd}}_{j,k}^1,k=1,\dots ,\frac{N}{2}-1,\end{array}\mathrm{For}j=0,\dots ,M/2-1,\mathrm{calculate}& \text{(4.3.2)}\\ \{\begin{array}{c}{\tilde{c}}_{j,1}^1={\tilde{c}}_{\mathrm{j0}}^1+\frac{{\mathrm{hd}}_{\mathrm{j0}}^1+{\mathrm{hd}}_{\mathrm{j1}}^1}{2},\\ {\tilde{c}}_{j,2k+1}^1=c_{\mathrm{jk}}^1+\frac{{\mathrm{hd}}_{j,k}^1-{\mathrm{hd}}_{j,k+1}^1}{2},k=1,\dots ,\frac{N}{2}-2,\\ {\tilde{c}}_{j,N-1}=c_{j,\frac{N-2}{2}}+{\mathrm{hd}}_j{,}_{\frac{N-2}{2}}^1,\end{array}\mathrm{and}& \text{(4.3.3)}\\ \{\begin{array}{c}{\tilde{c}}_{j,0}^1={\tilde{c}}_{j,1}^1-2{\mathrm{hd}}_{j,0}^1,\\ {\tilde{c}}_{j,2k}^1=\frac{1}{2}\left({\tilde{c}}_{j,2k-1}^1+{\tilde{c}}_{j,2k+1}^1\right)-2{\mathrm{hd}}_{\mathrm{jk}}^1,k=1,\dots ,\frac{N}{2}-1.\end{array}& \left(4.3\mathrm{.4}\right)\end{array}$

[0064] (2) Inverse transform for column:

[0065] For k=0, . . . , N−1, calculate and $\begin{array}{cc}\{\begin{array}{c}{\stackrel{\_}{c}}_{1,k}^1={\tilde{c}}_{0k}^1+\frac{{\tilde{d}}_{\mathrm{j0}}^1+{\tilde{d}}_{\mathrm{j1}}^1}{2},\\ {\stackrel{\_}{c}}_{j+1,k}^1={\tilde{c}}_{\mathrm{jk}}^1+\frac{{\tilde{d}}_{j,k}^1-{\tilde{d}}_{j+1,k}^1}{2},j=1,\dots ,\frac{M}{2}-2,\\ {\stackrel{\_}{c}}_{N-1,k}^0={\tilde{c}}_{\frac{N-2}{2},k}^1+{\tilde{d}}_{\frac{N-2}{2},k}^1.\end{array}& \text{(4.3.5)}\\ \{\begin{array}{c}{\stackrel{\_}{c}}_{0k}^0={\tilde{c}}_{1k}^0-2{\stackrel{\_}{d}}_{0k}^1,\\ {\stackrel{\_}{c}}_{j,2k}^1=\frac{1}{2}\left({\stackrel{\_}{c}}_{2j-1,k}^0+{\stackrel{\_}{c}}_{2j+1k,}^0\right)-2{\tilde{d}}_{\mathrm{jk}}^1,j=1,\dots ,\frac{M}{2}-1.\end{array}& \text{(4.3.6)}\\ c_{j,k}^0={\tilde{c}}_{j,k}^0/r,j=0,\dots M-1;k=0,\dots ,N-1.C^0\left[c_{j,k}^0\right]\frac{N}{1}\times \frac{N}{2}.& \left(3\right)\end{array}$

[0066] Following the inverse wavelet transformation, an inverse color transform is performed. Equations (5)-(6) give the inverse transforms for the YIQ and YUV color spaces. $\begin{array}{cc}\mathrm{For}\mathrm{YIQ}\mathrm{to}\mathrm{RGB}\text{:}\left[\begin{array}{c}R\\ G\\ B\end{array}\right]=\left[\begin{array}{ccc}1.000& 0.956& 0.621\\ 1.000& -0.272& -0.647\\ 1.000& -1.106& 1.703\end{array}\right]\left[\begin{array}{c}Y\\ I\\ Q\end{array}\right]& \left(5\right)\\ \mathrm{For}\mathrm{YUV}\mathrm{to}\mathrm{RGB}\text{:}\left[\begin{array}{c}R\\ G\\ B\end{array}\right]=\left[\begin{array}{ccc}1.000& 0.000& 1.140\\ 1.000& -0.395& -0.581\\ 1.000& 2.032& 0.000\end{array}\right]\left[\begin{array}{c}Y\\ U\\ V\end{array}\right]& \left(6\right)\end{array}$

[0067] In step 48, a user can optionally apply image filtering to improve the image quality. Filters are known in the art for sharpening, smoothing and brightening images. Users can choose any number of processing filters at compression time. Information defining the selected filters can be stored in the coded image file, in a form such as a one byte flag in a file header. In addition to optionally applying the filters, the method can also be implemented to automatically detect and apply the selected filters following decompression.

[0068] To sharpen an image, a filter is used that weights the eight pixels adjacent to the current pixel, as well as the current pixel, by one or more predetermined values. The weighted values of the nine pixels are then summed to derive a new value for the current pixel. For example, the surrounding eight pixel values can be weighted by the value −35/800, while the current pixel is weighted by 1.35. The sharpening filter is applied to every pixel in the image.

[0069] To smooth images, for every pixel, the average of the pixel and the eight adjacent pixels is calculated. Then the pixel value and the average is compared. The smaller of the two replaces the original pixel and is output as the smoothed pixel value.

[0070] To brighten images, the weighted sum of each pixel and the correspond eight adjacent pixels is calculated. For example, each of the adjacent pixels can be multiplied by the value 1/90 and the summed with the current pixel to obtain a brighten current pixel.

[0071] Another filter that can be used is one that adds a random value between [−12, 12] to each of the pixels in the image.

[0072] In FIG. 6 there is displayed a preferred hardware platform that can execute software for implementing an embodiment of the present invention. The computer system of FIG. 3 includes a CPU 62, a main memory 64, an I/O subsystem 66, and a display 68, all coupled to a CPU bus 70. The I/O subsystem 66 communicates with peripheral devices that include an image source 72, an image storage device 74, and a mass storage memory 76. Although shown as three separate devices, peripherals 72-76 can be implemented using a single memory device, such as a hard disk drive commonly found in computers.

[0073] The image source 72 may be a digital still image or video source, such as a CD-ROM drive, scanner, or network connection. In addition, the image source 72 can include analog video sources, such as a video camera, VCR, television broadcast or cable receiver. The analog video signals would be converted to a digital form by the image source 72 using conventional conversion techniques. Alternatively, an image source 72 can include a video camera and communications systems for transmitting real-time video to the I/O subsystem 66.

[0074] The image storage 74 can be a computer disk, such as a that used by a hard drive, or a portable memory medium, such as a floppy or ZIP disk, or a read/write optical CD.

[0075] In operation, a computer program, which implements aspects of the invention, is retrieved from the mass storage memory 76 into the main memory 64 for execution by the CPU 62. Upon execution of the compression aspect of the invention, the compressed image file can be stored in the image storage 74; while upon execution of the decompression aspect of the invention, the decompressed image can be viewed on the display 68. Operating under the control of the computer program, the CPU 62 can process images according to the methods set forth herein, as shown in FIGS. 1-2 and 6-10.

[0076] FIG. 7 illustrates an alternative hardware platform implementing a system in accordance with a further embodiment of the present invention. System 80 can be implemented using a variety of different hardware components, such as ASIC (Application Specific Integrated Circuits), or a combination of discrete digital components, such as microprocessors, standard logic components, and other programmable logic devices. The system 80 includes a compression system 81 and a decompression system 82. The compression system 81 can be configured to perform any one or combination of the compression methods set forth in FIGS. 1, 8, 10, and 12; while the decompression system can be configured to perform any one or combination of the decompression methods set forth in FIGS. 5, 9, 11, and 13.

[0077] An image source 85 provides digital pixel values to a color converter 84. The image source 85 can provide the same functionality as described earlier for the image source 72 of FIG. 6.

[0078] The color converter 84 performs a color space transformation on the input pixels, such as any of those described herein for FIG. 1. The converter functionality can be provided by conventional integrated circuits that are readily available from various manufacturers. Compressor 86 compresses the transformed pixels, removing redundant data. The compressed image file generated by the compressor 86 can be transferred directly to the decompression system 82 over a transmission medium 91. The transmission medium 91 can be a radio-link, computer network, cable television network, or satellite link. Alternatively, the compressor 86 can transmit its output to a portable storage medium 92, such as an optical, floppy, or ZIP disk; or to a mass storage device 94 such as a computer hard disk or archival system.

[0079] The decompressor 88 expands the compressed image file by applying an inverse wavelet transformation, as well as de-quantization and de-encoding functions. The decompressed data is then passed to an inverse color converter 90 that applies an inverse color space transformation to generate pixel values in a color space and format appropriate for the image display 89. Standard electronic components are readily available for performing the function of the inverse color converter 90.

[0080] FIG. 8 illustrates a flow diagram of a method of compressing an image in accordance with an alternative embodiment of the present invention. In step 100, a digital image is input. In step 102, a color space transformation is performed on the input image pixels. In step 104, the pixels are subjected to a wavelet transformation. In step 106, sub-band quantization is performed on the wavelet coefficients. Next, in step 108 the quantized sub-bands are respectively entropy encoded. In step 110, the coded image file is output.

[0081] Sub-band oriented quantization and entropy coding are well suited for wavelet-based image compression. The main idea is to take the advantage of different quantizations at different sub-bands (wavelet quadrant) and encode each band accordingly. Quadrants having a high variance in wavelet values can be allocated a finer mesh size for quantization, while those quadrants with smaller variances will be assigned fewer levels of quantization. That is, the number of bits one wishes to allocate to the output could be varied by quadrant. Those quadrants with large variances will utilize more bits, while those with low variants will utilize fewer bits. In this way, the number of bits resulting from quantization will remain the same, but their allocation will differ depending upon the nature of the image. This technique greatly improves image quality while maintaining a high compression ratio.

[0082] FIG. 9 illustrates a flow diagram of a method of decompressing an image compressed according to the methods shown in FIG. 8. Step 120, the compressed file is input. In step 122, the input image is entropy decoded. In step 124, de-quantization is performed on the decoded image file. Next, in step 126, an inverse wavelet transform is performed on the image. In step 128, an inverse color transformation is performed. In step 130, post-processing altering is optionally performed. In step 132, the decompressed image file is then displayed.

[0083] FIG. 10 illustrates a flow diagram of a method of compressing an image in accordance with another embodiment of the present invention. This method performs color-bit depth compression, which essentially reduces the number of colors in the image to achieve compression. In step 140, the image is input with its original color. For example, each color pixel could be represented by a standard 24-bit value. Next, in step 142, a color table is created corresponding to the image. The color table is a set of quantized color values. The quantized color values represent a smaller number of colors with correspondingly fewer bits. Each of the input pixels is mapped to the color table. In step 144, an index is calculated for each pixel in the image by dithering the pixel values. Dithering is accomplished by weighting pixels adjacent to the current pixel in a frame and then arithmetically combining the weighted values with the current pixel value to produce the index, which then represents the current pixel. The dithering process is repeated for each pixel in a frame. In step 146, the indexes are wavelet transformed. In step 148, the wavelet coefficients are entropy coded. In step 150, the coded image file is output.

[0084] FIG. 11 illustrates a flow diagram of a method of decompressing an image that has been compressed according to the method shown in FIG. 10. In step 160, a compressed image file is received. Next, in step 162, the image file is entropy decoded. In step 164, an inverse wavelet transform is applied to the decoded data. Next, in step 166, post-processing filtering of the image is optionally applied. Next, in step 168, the decompressed image is displayed.

[0085] FIG. 12 illustrates another method of compressing an image in accordance with another embodiment of the present invention. In this method, a user can selectively vary compression parameters (step 173) to obtain a lossless or near-lossless compressed image at a desired compression ratio. In step 170, the image is input. In step 172, an integer color transform is performed on the input image. In step 173, compression parameters are selected by the user using a software interface. These parameters can include those described herein below in the subsection title “Peak Signal to Noise Ratio (PSNR) Controlled Compression”. In step 174, an integer wavelet transform is performed on the color transformed pixels. In step 176, the wavelet coefficients are entropy coded. Next, in step 178, the compressed image file is then output from the system.

[0086] The integer color transformation of step 172 is an integer reversible transform which can be used in color image compression to reduce processing time and image size. Step 172 transforms RGB color components to a set of color components Y-Nb-Nr, which are known.

[0087] The RGB to Y-Nb-Nr transform is given by the equations: $Y=G+\mathrm{Int}\left(R/2+B/2\right),\mathrm{Nb}=B-\mathrm{Int}\left(Y/2\right),\mathrm{Nr}=R-\mathrm{Int}\left(Y/2\right).$

[0088] The integer wavelet transform of step 174 is described below in detail.

[0089] FIG. 13 illustrates a method of decompressing an image file that has been compressed according to the method shown in FIG. 12. In step 180, a compressed image file is input. In step 182, the image is entropy decoded. Next, in step 184, an inverse integer wavelet transform is performed on the decoded data. In step 186, an inverse integer color transform is performed. Next, in step 188 optional post-processing filtering is performed on the image. Next, in step 190, the decompressed image is displayed.

[0090] The Y-Nb-Nr to RGB transform of step 186 is given by the equations: $R=\mathrm{Nr}+\mathrm{Int}\left(Y/2\right),B=\mathrm{Nb}+\mathrm{Int}\left(Y/2\right),G=Y-\mathrm{Int}\left(R/2+B/2\right)$

[0091] The inverse integer wavelet transform of step 184 is described in detail below.

[0092] This method allows a series of transformations which are very close to the corresponding biorthogonal wavelet transforms or some non-orthogonal wavelet transforms, but can be calculated with only integer addition and bit-shift operations. In addition, the integer wavelet transforms created disclosed herein possess a property of precision preservation (PPP). This property is very useful for conserving memory in both compression and decompression, and speed up the whole procedure in some applications. Two general methods from which one can get the integer wavelet transform desired are disclosed.

[0093] Two examples are provided as the starting point for the unique method. For the sake of convenience, length, and simplicity, presented is only the algorithm for a one level decomposition and reconstruction and only for a one dimensional signal. The extension to two dimensions is immediate as the rows and columns can be treated into a sequence of one dimensional signals. For the following examples, assume that ${\left\{C_n^0\right\}}_{n=0}^{N-1}$

[0094] is the original signal where the superscript indicates level and the subscript indicates a particular point in the signal. Also, ${\left\{c_n^1\right\}}_{n=0}^{N_1-1}\mathrm{and}{\left\{d_n^1\right\}}_{n=0}^{M_1-1}$

[0095] are its decomposition parts at the first level. Here $N_1=\{\begin{array}{c}\frac{N}{2},\mathrm{if}N\mathrm{is}\mathrm{an}\mathrm{even}\mathrm{number},\\ \frac{N+1}{2},\mathrm{if}N\mathrm{is}\mathrm{an}\mathrm{odd}\mathrm{number};\end{array}{M}_1=N-N_1$ $\begin{array}{cc}{\left\{c_n^1\right\}}_{n=0}^{N_1-1}\mathrm{and}{\left\{d_n^1\right\}}_{n=0}^{M_1-1}\mathrm{are}\mathrm{its}\mathrm{low}\mathrm{frequency}& \left(1\right)\end{array}$

[0096] part and high frequency (h) part, respectively. For multi-levels, we just create ${\left\{c_n^1\right\}}_{n=0}^{N_1-1}\mathrm{as}{\left\{c_n^0\right\}}_{n=0}^{N_1}$

[0097] and repeat the procedure again.

[0098] A (2,2)-Wavelet Transform by Integer Calculation.

[0099] This transformation is similar to a variation of the Haar wavelet transform which uses low and high pass analysis (decomposition) filters given as:

[0100] (1) Compute $\begin{array}{cc}{d}_k^1=c_{2k}^0-c_{2k+1,}^0,k=0,\dots ,M_1-1.& \left(2.1\right)\end{array}$

[0101] (2) Compute $c_k^1=\mathrm{Int}\left(\frac{d_k^1}{2}\right)+c_{2k+1}^0,k=0,\dots ,N_1-2,$ $\begin{array}{cc}{c}_{N_1-1}^1=\{\begin{array}{cc}\mathrm{Int}\left(\frac{d_{M_1-1}^1}{2}\right)+c_{2k+1}^0,& \mathrm{if}N\mathrm{is}\mathrm{an}\mathrm{even}\mathrm{number},\\ c_{N-1}^0,& \mathrm{if}N\mathrm{is}\mathrm{an}\mathrm{odd}\mathrm{number},\end{array}& \text{(2.2)}\end{array}$

[0102] Here, Int(x) is an arbitrary rounding function which may have different interpretations. For example, Int(x) can be the integer which is nearest to x, or Int(x) may be any integer which satisfies x−1<Int(x)≦x, etc. It is easy to see that all entries in both ${\left\{c_n^1\right\}}_{n=0}^{N_1-1}\mathrm{and}{\left\{d_n^1\right\}}_{n=0}^{M_1-1}$

[0103] are integers.

[0104] From (2.1)-(2.2), we can easily get the following integer reconstruction algorithm:

[0105] (b) Reconstruction

[0106] (1) If N is an even number, compute: $\begin{array}{cc}{c}_{2k+1}^0=c_k^1-\mathrm{Int}\left(\frac{d_k^1}{2}\right),k-0,\dots ,N_1-1;& \left(2.3\right)\end{array}$

[0107] or, if N is an odd number, we have $\begin{array}{cc}{c}_{2k+1}^0{c}_k^1-\mathrm{Int}\left(\frac{d_k^1}{2}\right).k=0,\dots ,N_1-2;c_{N-1}^0=c_{N_1}^1.& \left(2.4\right)\end{array}$

[0108] (2) Compute $\begin{array}{cc}{c}_{2k}^0=d_k^1+c_{2k+1}^{0}k=0,\dots ,M_1-1.& \left(2.5\right)\end{array}$

[0109] REMARK. Since (2.1)-(2.5) are not linear because of the rounding operation Int(x), this means the transformation order becomes significant. For instance, if the decomposition was applied first to the columns and then to the rows, the inverse transformation must be applied first to the rows and then to the columns.

[0110] Lazy Wavelet Transform.

[0111] The lazy wavelet transform is used to illustrate an important concept. The corresponding inverse transform is nothing else but sub-sampling the even and odd indexed samples. Decomposition and reconstruction can use the same formula as follows: $c_k^1=c_{2k}^0,k=0,\dots ,N_1-1;$ $d_k^1=c_{2k+1}^0,k=0,\dots ,M_1-1.$

[0112] Examples 1 and 2 are not good transforms for image compression, but they are simple. Much better transforms can be achieved from these two. As suggested above, they are considered only as a starting point for the integer, reversible, wavelet transform algorithm of the disclosed invention.

[0113] It is noted that there is another interesting property in the above two transforms which may not be easily seen. If the values of the signal pixels are represented by a finite number of bits, say one bit or one byte, the same number of bits can be used to represent the result of the forward transform within the computer itself because of the complementary code property. While, from the reconstruction algorithm, the computer will get back the exact original signal through the same complementary code property. This property is called a Property of Precision Preservation (PPP) for these wavelets.

[0114] It is known that the general values for the high frequency wavelet coefficients are small, and all higher levels of the decomposition provide generally small values in the high frequency band. This allows the preservation of precision during the computational stage of the wavelet coefficients. Now, the complementary code property, the other aspect of the PPP property, is a well know characteristic of the integer arithmetic as done by the computer. Consider the computation of the difference of two integers given as c=b−a and the inverse computation of a=b−c. the nature of the computation within the computer can be specified as follows: $c_m=\{\begin{array}{c}b-a\mathrm{if}-2^{q-1}⪯b-a{<}^{q^{-1}}-1\\ -2^q+b-a\mathrm{if}b-a⪰2^{q^{-1}}\\ 2^q+b-a\mathrm{if}b-a<-{2^q}^{-1}\end{array}$

[0115] and the inverse is $a_m=\{\begin{array}{c}b-c_m\mathrm{if}-2^{q-1}⪯b-a{<}^{q^{-1}}-1\\ -2^q+b-c_m\mathrm{if}b-c_m⪰2^{q^{-1}}\\ 2^q+b-c_m\mathrm{if}b-c_m<-{2^q}^{-1}\end{array}$

[0116] where the m subscript indicates the internal representation, and the range of the integers a, b, c is [−2^q,2^q−1]. The internal representation of c_mwhen it is outside the range, its appearance is as a two's complement number, so the representation may not be the same as the external representation of c. However, the same complementary code for the a_mwill cause the internal representation to be identical to the external representation of a. For example, if we let b=2 (00000010) and a=−127 (10000001) then c_mhas the internal binary value of (10000001) when q=4. With a value of −127 for c_mthe inverse value for a_mwill just be a.

[0117] In fact, for Example 2, this property is obviously true. While for Example 1, if the range of the pixel values is within a finite number of bits, say q, we can only use q bits as the working unit, which means the value of transform coefficients will also be within the interval with length 2^q, say [−2^q−1, 2^q−1−1]. Due to the nature of computation on a machine, most machines will implement (2.1)-(2.2) automatically as follows (the complementary code property): $\begin{array}{cc}{d}_k^1=\{\begin{array}{cc}{c}_{2k}^0-c_{2k+1}^0,& \mathrm{if}-2^{q^{-1}}⪯c_{2k}^0-c_{2k+1}^0<2^{q^{-1}},\\ c_{2k}^0-c_{2k+1}^0-2^q,& \mathrm{if}{c}_{2k}^0-c_{2k+1}^0⪰2^{q^{-1}},\\ 2^q+\left(c_{2k}^0-c_{2k+1}^0\right),& \mathrm{if}{c}_{2k}^0-c_{2k+1}^0<-2^{q^{-1}}.\end{array}& \text{(2.6)}\\ c_k^1=\{\begin{array}{cc}\mathrm{Int}\left(\frac{d_k^1}{2}\right)+c_{2k+1}^0,& \mathrm{if}-2^{q^{-1}}⪯\mathrm{Int}\left(\frac{d_k^1}{2}\right)+c_{2k+1}^0<2^{q^{-1}},\\ \mathrm{Int}\left(\frac{d_k^1}{2}\right)+c_{2k+1}^0-2^q,& \mathrm{if}\mathrm{Int}\left(\frac{d_k^1}{2}\right)+c_{2k+1}^0⪰2^{q^{-1}},\\ \mathrm{Int}\left(\frac{d_k^1}{2}\right)+c_{2k+1}^0+2^q,& \mathrm{if}\mathrm{Int}\left(\frac{d_k^1}{2}\right)+c_{2k+1}^0<-2^{q^{-1}}.\end{array}& \left(2.7\right)\end{array}$

[0118] While the reconstruction algorithm (2.3) and (2.5) will be implemented by the computer itself as $\begin{array}{cc}{c}_{2k+1}^1=\{\begin{array}{cc}{c}_k^1-\mathrm{Int}\left(\frac{d_k^1}{2}\right),& \mathrm{if}-2^{q^{-1}}⪯c_k^1-\mathrm{Int}\left(\frac{d_k^1}{2}\right)<2^q,\\ 2^q+\left(c_k^1-\mathrm{Int}\left(\frac{d_k^1}{2}\right)\right),& \mathrm{if}{c}_k^1-\mathrm{Int}\left(\frac{d_k^1}{2}\right)\prec -2^{q^{-1}},\\ \left(c_k^1-\mathrm{Int}\left(\frac{d_k^1}{2}\right)\right)-2^q,& \mathrm{if}{c}_k^1-\mathrm{Int}\left(\frac{d_k^1}{2}\right)\succ -2^{q^{-1}}.\end{array}& \text{(2.8)}\\ c_{2k}^1=\{\begin{array}{cc}{d}_k^1+c_{2k+1}^0,& \mathrm{if}-2^{q^{-1}}⪯d_k^1+c_{2k+1}^0<2^{q^{-1}},\\ d_k^1+c_{2k+1}^0+2^q,& \mathrm{if}{d}_k^1+c_{2k+1}^0<-2^{q^{-1}},\\ d_k^1+c_{2k+1}^0-2^q,& \mathrm{if}{d}_k^1+c_{2k+1}^0⪰-2^{q^{-1}}.\end{array}& \text{(2.9)}\end{array}$

[0119] It is obvious that (2.8)-(2.9) are just the reverse of (2.6)-(2.7). It is also easy to see that if we properly take advantage of the bound in the coefficient size mentioned above, the algorithm can be implemented using a minimal amount of storage.

[0120] The following are examples which give motivation for our new approach.

[0121] A (2.6) wavelet transform by integer calculation (2).

[0122] This transformation is similar to using the following analysis filters:

[0123] (a) Decomposition

[0124] Decomposition starts with Example 1 at step (1) and (2), and then upgrades the high frequency component at step (3):

[0125] (1) Compute $d_k^{1,0}=c_{2k}^0-c_{2k+1}^0,k=0,⃛,M_1-1.$

[0126] (2) Compute $c_k^1=\mathrm{Int}\left(\frac{d_k^{1,0}}{2}\right)+c_{2k+1}^0,k=0,⃛,N_1-2,$ $c_{N_1-1}^1=\{\begin{array}{cc}\mathrm{Int}\left(\frac{d_{M_1-1}^{1,0}}{4}\right),+C_{N-1}^0,& \mathrm{if}N\mathrm{is}\mathrm{an}\mathrm{even}\mathrm{number},\\ c_{N-1}^0,& \mathrm{if}N\mathrm{is}\mathrm{an}\mathrm{odd}\mathrm{number};\end{array}$

[0127] (3) Compute $\{\begin{array}{c}{d}_0^1=\mathrm{Int}\left(\frac{c_{0-}{c}_1^1}{4}\right),+d_0^{1,0}\\ d_k^1=\mathrm{Int}\left(\frac{c_{k-1}^1-c_{k+1}^1}{4}\right)-d_k^{1,0},k=1,⃛,M_1-2,\end{array}$

[0128] and then, if N is even, calculate $d_{M_1-1}^1=\mathrm{Int}\left(\frac{c_{N_1-2}^1-c_{N_1-1}^1}{4}\right)-d_{M_1-1}^{1,0}$

[0129] else, calculate $d_{M_1-1}^1=\mathrm{Int}\left(\frac{c_{N_1-3}^1-c_{N_1-1}^1}{4}\right)-d_{M_1-1}^{1,0}.$

[0130] (b) Reconstruction

[0131] The reconstruction algorithm is identical to the decomposition algorithm, except it is now running “backwards”.

[0132] (1) Compute $\{\begin{array}{c}{d}_0^{1,0}=\mathrm{Int}\left(\frac{c_{0-}^1{c}_1^1}{4}\right),-d_0^1\\ d_k^{1,0}=\mathrm{Int}\left(\frac{c_{k-1}^1-c_{k+1}^1}{4}\right)-d_k^1,k=1,⃛,M_1-2,\end{array}$

[0133] and then, if N is even, calculate $d_{M_1-1}^{1,0}=\mathrm{Int}\left(\frac{c_{N_1-2}^1-c_{N_1-1}^1}{4}\right)-d_{M_1-1}^{1,1},$

[0134] else calculate $d_{M_1-1}^{1,0}=\mathrm{Int}\left(\frac{c_{N_1-3}^1-c_{N_1-1}^1}{4}\right)-d_{M_1-1}^{1,1},$

[0135] (2) If N is an even number, compute $c_{2k+1}^0=c_k^1-\mathrm{Int}\left(\frac{d_k^{1,0}}{2}\right),k=0,⃛,N_1-1;$

[0136] or, if N is an odd number, we have $c_{2k+1}^0=c_k^1-\mathrm{Int}\left(\frac{d_k^{1,0}}{2}\right),k=0,⃛,N_1-2;$ $c_{N-1}^0=c_{N_1}^1.$

[0137] (3) Compute $c_{2k}^0=d_k^{1,0}+c_{2k+1}^0,k=0,⃛,M_1-1.$

[0138] We see in step (2)-(3) above, that they are just the same as shown for the reconstruction of the (2.2)-wavelet transform (Example 1).

[0139] A (1,3)-Wavelet Transform by Integer Calculation.

[0140] The following nonlinear transform is a variation of the transform which uses biorthogonal analysis filters:

[0141] (a) Decomposition

[0142] This decomposition starts with the Lazy wavelet at step (1) and upgrades the high frequency component at step (2):

[0143] (1) Set $c_k^1=c_{2k}^0,k=0,⃛,N_1-1;$ $d_k^1=c_{2k+1}^0,k=0,⃛,M_1-1.$

[0144] (2) If N is an even number, calculate $\{\begin{array}{c}{d}_k^1=\mathrm{Int}\left(\frac{c_{k-}^1-c_{k+1}^1}{2}\right)-d_k^{1,0},k=0,⃛,M_1-2,\\ d_{M_1-1}^1,=c_{N_1-1}^1-d_{M_1-1}^{1,0}.\end{array}$

[0145] Otherwise, if N is an odd number, calculate $d_k^1=\mathrm{Int}\left(\frac{c_{2k}^0-c_{2k+2}^1}{2}\right)-c_{2k+1},k=0,⃛,M_1-1.$

[0146] (b) Reconstruction

[0147] (1) Set $c_{2k}^0=c_k^1,k=0,⃛,N_1-1;$

[0148] (2) If N is an even number, calculate $\{\begin{array}{c}{c}_{2k+1}^0=\mathrm{Int}\left(\frac{c_{2k}^0+c_{2k+2}^0}{2}\right)-d_k^1,k=0,⃛,M_1-2,\\ c_{N-1}^0,=c_{N-2}^0-d_{M_1-1}^1.\end{array}$

[0149] Otherwise, if N is an odd number, calculate $c_{2k+1}^0=\mathrm{Int}\left(\frac{c_{2k}^0+c_{2k+2}^0}{2}\right)-d_k^1,k=0,⃛,M_1-1.$

[0150] (5.3)-Wavelet Transform by Integer Calculation.

[0151] This transformation is also similar in function to using the biorthogonal analysis filters. It is given by

[0152] (a) Decomposition

[0153] This decomposition starts with Example 3 at step (1) and upgrade low frequency components at step (2):

[0154] (1) Set $c_k^{1,0}=c_{2k}^0,k=0,⃛,N_1-1;$

[0155] If N is an even number, calculate $\{\begin{array}{c}{d}_k^1=\mathrm{Int}\left(\frac{c_{2k}^0+c_{2k+2}^0}{2}\right)-c_{2k+1}^0,k=0,⃛,M_1-2,\\ d_{M_1-1}^1=c_{N-2}^0-c_{N-1}^1.\end{array}$

[0156] Otherwise, if N is an odd number, calculate $d_k^1=\mathrm{Int}\left(\frac{c_{2k}^0+c_{2k+2}^0}{2}\right)-c_{2k+1},k=0,⃛,M_1-1.$

[0157] (2) If N is an even number, compute $\{\begin{array}{c}{c}_0^1=c_0^{1,0}-\mathrm{Int}\left(\frac{d_0^1}{2}\right),\\ c_k^1=c_k^{1,0}-\mathrm{Int}\left(\frac{d_{k-1}^1+d_k^1}{4}\right),k=1,⃛,N_1-2,\\ c_{N-1}^1=c_{N_1-2}^{1,0}-\mathrm{Int}\left(\frac{d_{N_1-2}^1+d_{N_1-1}^1}{4}\right).\end{array}$

[0158] Otherwise, if N is an odd number, calculate $\{\begin{array}{c}{c}_0^1=c_0^{1,0}-\mathrm{Int}\left(\frac{d_0^1}{2}\right),\\ c_k^1=c_k^{1,0}-\mathrm{Int}\left(\frac{d_{k-1}^1+d_k^1}{4}\right),k=1,⃛,N_1-2,\\ c_{N-1}^1=c_{N_1-2}^{1,0}-\mathrm{Int}\left(\frac{d_{M_1-1}^1}{2}\right).\end{array}$

[0159] (b) Reconstruction

[0160] (1) Compute $\begin{array}{c}{c}_0^0=c_0^1+\mathrm{Int}\left(\frac{d_0^1}{2}\right),\\ c_{2K}^0=c_k^1+\mathrm{Int}\left(\frac{d_{k-1}^1+d_k^1}{4}\right),k=1,⃛,N_1-2,\end{array}$

[0161] Then, if N is even, calculate $c_{N-2}^0=c_{N_1-1}^1+\mathrm{Int}\left(\frac{d_{N_1-2}^1+d_{N_1-1}^1}{4}\right).$

[0162] else calculate $c_{N-1}^0=c_{N_1-1}^1+\mathrm{Int}\left(\frac{d_{M_1-1}^1}{2}\right).$