I
`
`WO 98/40842
`
`PCT /US98/04700
`
`10
`
`15
`
`4
`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.
`5 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
`In
`image pixels can be reduced using a color table.
`addition, color pixels can be transformed between color
`spaces prior to wavelet transformation.
`According to another aspect of the invention, a
`corresponding method of decompression is provided.
`According to another aspect of the present
`invention, a compression method is provided that allows
`20 user selected portions of an image to compressed to
`different image qualities, whereby permitting non-uniform
`image compression.
`According to another aspect of the present
`invention, a compression method is provided that permits
`compression quality to be based on image specific
`parameters.
`According to another aspect of the present
`invention, a method of compressing images using a "split
`and merge" technique is provided.
`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
`
`25
`
`30
`
`35
`
`IPR2023-00332 Page 00420
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`5
`
`logic components, or any combination of the
`aforementioned.
`According to another aspect of the present
`invention, a corresponding image decompression system is
`5 provided.
`
`15
`
`Brief Description of the Drawings
`The invention is pointed out with particularity
`in the appended claims. However, other features of the
`invention will become more apparent, and the invention
`10 will be best understood by referring to the following
`detailed description in conjunction with the accompanying
`drawings, in which:
`FIG. 1 illustrates a flow diagram for a method
`of compressing an image that is in accordance with an
`embodiment of the present invention;
`FIGS. 2-4 depict wavelet coefficients for
`varjous levels of decomposition;
`FIG. 5 illustrates a flow diagram of a method of
`decompressing an image that has been compressed using the
`20 method of FIG. l;
`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;
`FIG. 7 is a block diagram of a system for
`compressing and decompressing an image in accordance with
`another embodiment of the present invention;
`FIG. 8 illustrates a flow diagram of a method
`compressing an image that is in accordance with a further
`embodiment of the present invention;
`FIG. 9 illustrates a flow diagram of a method
`for decompressing an image that has been compressed
`according to the method of FIG. 8;
`FIG. 10 illustrates a flow diagram of a method
`35 of compressing an image in accordance with a further
`embodiment of the present invention;
`
`25
`
`30
`
`IPR2023-00332 Page 00421
`
`

`

`WO 98/40842
`
`PCT /US98/04700
`
`6
`
`FIG. 11 illustrates a flow diagram of a method
`of decompressing an image that has been compressed
`according to the method of FIG. 10;
`FIG. 12 illustrates a flow diagram of a method
`5 of compressing an image that is in accordance with a
`further embodiment of the present invention; and
`FIG. 13 illustrates a flow diagram of a method
`for decompressing an image that has been compressed
`according to the method of FIG" 12.
`
`10
`
`15
`
`Detailed Description of the Preferred Embodiments
`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
`In step 20, a digital image is
`of the invention.
`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
`In step 22,
`still image or a frame from a video image.
`the image is optionally displayed on an appropriate
`20 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
`25 wavelet transform for both gray level images and color
`In step 26, the values representing the
`images.
`transformed images are quantized and compared to
`thresholds. V2lues falling outside the threshold are
`In step 28, the remaining quantized values
`discarded.
`30 are encoded to remove redundant information, creating a
`compressed image file. Next, in step 30 the compressed
`image file is generated as output"
`Referring to the color transformation of step
`24, digital color images are typically based on an RGB
`35 color model, such as is commonly used with TIFF or BMP
`In order to get a higher compression ratio, the
`images.
`
`IPR2023-00332 Page 00422
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`I,
`
`'
`
`7
`
`RGB pixels are transformed to other color models, such as
`YIQ or YTN models. The method can convert RGB inputs
`into YIQ or YW color spaces according to the following
`relationships.
`
`5
`
`RGB to YIQ:
`
`fYl=r 0.299
`IIl=l-0.596
`LQJ=L 0.212
`
`0.587
`-0.275
`-0. 523
`
`0.1147 IRl
`!GI
`0.321!
`0.3llj LBJ
`
`RBG to YW:
`fYl=r 0.299
`IUl=I 0.148
`LVJ=L 0.615
`
`0.587
`-0.289
`-0.515
`
`0.1147 rRl
`IGI
`0.439!
`-0.lj LBJ
`
`In the YIQ color space, there is one
`lumines~ence (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.
`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.
`
`- 0, •.. , M-1; k = 0,
`( j
`N-1) represent the original, uncompressed image, where M
`and N are integers which have the common factor 21 (Lis a
`positive integer). A one-level wavelet decomposition,
`where L = 1, results in the four coefficient quadrants as
`
`10
`
`15
`
`20
`
`25
`
`30
`
`IPR2023-00332 Page 00423
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`,
`
`8
`shown in Figure 2. Each quadrant represents a set of
`wavelet coefficients.
`Quadrant C1 represents the blurred image of the
`, where C1 =[Cfk)(j=o, ... ,f-1;k=O, ... ,f-1).
`original image c 0
`5 HD1 represents the horizontal high frequency part of c0
`while VD1 represents the vertical high frequency part of
`, and DD1 represents the diagonal high frequency part of
`c 0
`• The decomposition can be iteratively repeated L times
`c0
`to obtain different levels of decomposition. For
`• The iterative
`c 0 is set to equal C1
`10 example, for L = 2,
`formula for computing a decomposition is given as
`follows:
`(1) Let c0 = rc 0
`,
`different needs.
`(2) Transform for image columns:
`For k=O, ... ,N-1, calculate
`
`r>O is a factor which can be changed for
`
`15
`
`For k=O, ... ,N-1, calculate
`
`c;~2 k= c- -a
`-2-,
`
`- aN-2 k
`- 2-
`N-l,k
`
`1
`
`(3.1. 1)
`
`(3.1.2)
`
`•
`
`(3) Transform for rows:
`For j = 0, . . . M/2 - 1, computing
`
`IPR2023-00332 Page 00424
`
`

`

`WO98/40842
`
`PCT /US98/04700
`
`9
`
`and
`
`hd}o+hd}1
`1
`-1
`Cj = C · 1 - -...;._------
`2
`o
`J,
`
`For j = 0,
`
`.
`
`.
`
`.
`
`, Ml 2
`
`1, computing
`
`dd~ = aJ, i -aJo
`2
`,
`
`J,0
`
`and
`
`(3.l.3}
`
`(3.1.4)
`
`(3.l.5)
`
`(3.1.6)
`
`{ 4) C 1 = [ c],k] , HD 1 = [hd],k] , VD 1 [ud},k] and DD= [ dd},k] , j =O, ... , ~ -1
`M
`k=O, ... , 2 -1.
`
`Remark: If it is necessary, we also can use matrix
`5 multiply Wavelet Coefficient Image of 1 levels=W1C0 W/.
`
`I
`I'
`
`I
`
`I
`
`I
`
`IPR2023-00332 Page 00425
`
`

`

`WO 98/40842
`
`PCT /US98/04700
`
`5
`
`10
`Here, W1 is the transform matrix for l level wavelet
`decomp_osition.
`FIG. 3 depicts a three-level wavelet
`decomposition, where L = 3.
`In step 26, the first loss in accuracy occurs.
`Both thresholding and quantization reduce accuracy with
`In step
`which the wavelet coefficients are represented.
`26, the wavelet coefficients are matched against
`threshold values, and if the values are less than the
`10 established threshold values specified, then the
`resultant value is set to zero.
`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
`15 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 suatial frequencies, which reduces the size of a
`compressed image.
`A multilevel uniform thresholding method can be
`used as described below.
`t 1 +1 ) be the chosen
`Let T = ( tu ... ,
`t 1 ,
`thresholds, where tt is the threshold for l the (l=I, ... ,
`level and t~ 1 is a threshold for blurred image c1
`•
`L)
`, VD 1
`25 Thresholding sets every eP-try in the blocks C1 , HD 1
`to be zero if its absolute value is
`(1 = I, ... L)
`and DD 1
`not greater than the corresponding threshold.
`For color images, three threshold vectors which
`I and
`correspond three different color planes, such as y,
`30 Q, are used.
`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.
`
`20
`
`IPR2023-00332 Page 00426
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`q·HD
`qlVD
`1
`q DD
`
`2
`q HD
`
`q2VD
`
`2
`q DD
`
`11
`
`...
`...
`...
`
`ct HD
`L q VD
`q1DD
`
`'
`
`,r. ... 1
`qc
`
`'!
`
`TABLE 1
`In Table 1, the entries q\0 are quantization
`factors for blocks HD 1
`(1 = I, ... L), q 1vo and q 1
`00 for
`blocks VD1 and DD1 (1 = I, ... , L) respectively, and the
`factor q/+1 is for the most blurred image CL.
`The factors
`can be integers between O and 255. The quantization
`(1 = I, ... , L) is
`scheme for the block HD 1
`
`5
`
`10
`
`d hd}k•qiv
`M -l ·k-O
`._0
`N _1
`hd i
`i, k = I oun
`, J -
`, ... , 1
`,
`-
`, ... , 1
`.1 ,
`1
`maxHD
`2
`2
`
`(3.2.l
`
`Here,
`
`M
`· d
`N
`·
`hd l (,
`- k J=O, ... , --1; ,k=O, ... , --1, are quantize
`,
`21
`1
`21
`wavelet coefficients of block HD 1 (l•l, ... ,L)
`
`maxiID• max {lhd}kn I
`0:1.j-1. (M/2 1 -1)
`O:sk~ (N/21-1)
`
`and the function round(x) gives the nearest integer of x.
`Equation (3.2.1) is used for quantization of the other
`blocks (quadrants).
`For color images, there are three separate
`15 quantization tables for the different color bands.
`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.
`
`20
`
`IPR2023-00332 Page 00427
`
`

`

`WO98/40842
`
`PCT /US98/04700
`
`12
`
`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-
`s 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.
`FIG. 5 shows a corresponding method for
`10 decompressing an image compressed using the method of
`In step 40, the compressed image file is input.
`FIG. 1.
`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-
`In step 48, optional image post(cid:173)
`15 quantized data.
`processing takes place to refine the decompressed image.
`In step 50, the decompressed image is displayed.
`The ~ecoding of step 42 is the inverse operation
`of the encoding of step 280 Similarly, it can be divided
`into two parts: Entropy decoding (Huffman or
`arithmetic), and coefficient rearranging.
`The decoding step produces quantized wavelet
`coefficients in 3*L+l blocks. Dequantizing (step 44)
`uses the same quantization table as quantizing (Table 1),
`for 1 = I, • o o p L
`and the scheme as follows:
`
`20
`
`25
`
`1
`1
`-
`._
`- hdj,k. max.HD
`M
`i
`iKJ.. k ---=-----, J-0, ... , -
`qHD
`2 1
`J,
`
`N
`.
`-1, k=O, ... , -
`2 1
`
`-1.
`
`(4.2.1)
`
`Equation (4.2.1) produces the approximate coefficients
`(1 = I, ... , L), which are shown in
`for the blocks HD 1
`The dequantizing scheme for other blocks is
`FIG. 30
`similar to 4 .1.2).
`In step 46, the inverse wavelet transform, also
`referred to as wavelet reconstruction, is performed prior
`to the inverse color transformation. FIGo 4 depicts a
`one-level wavelet reconstruction.
`
`30
`
`IPR2023-00332 Page 00428
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`13
`The wavelet reconstruction can be iteratively
`performed for various levels of decomposition, according
`to the following equations.
`(1) Inverse transform for rows:
`For j=O, . ,. .. ., , M -l, calculate
`
`2
`
`5
`
`a1
`
`-u
`dl
`+
`j,1-
`J,O
`
`ddJ; 0 +dd~ ,
`,
`.,,-
`2
`
`al
`
`-
`1
`j,2k+1-udik+
`
`1
`1
`ddj,k-ddj,k+1
`2
`
`--
`N
`,k-.L, ... , 2-2,
`
`(4.3.1)
`
`aN-1 k=ud · N-1 +dd~ N-2 ,
`J,-2-
`J,-2-
`
`I
`
`a}. 0 =d},1 -2 dd], o,
`a1
`a1
`al = j,Zk-1+ j,2k+1 _2dd+
`{
`
`j t 2.k
`
`2
`
`k=1
`
`-
`
`.Y-"'!
`, ••• ' 2
`
`..!.. •
`
`<4.3.2}
`
`J , k I
`
`and
`
`and
`
`For j=O, ... , M/2 - 1, calculate
`
`1 hd]0 -1-hd}1
`_ 1
`Cj,1=Cjo+
`2
`hd},k-hd},k+l
`_.,
`N
`'k-.:i.. I ••• I 2 -2'
`2
`
`-1
`_
`1
`Cj,2k+l -Cjk+
`
`CJ· N-i =c
`. N-2 +hd~ N-z •
`1
`,
`,-2-
`J,-2-
`
`(4.3.3)
`
`I
`
`I
`
`(4 0 3. 4
`
`N -1
`K---••I 2
`'
`i -1
`
`)
`
`(2) Inverse transform for column:
`For k=O, ... , N - 1, calculate
`
`10
`
`and
`
`IPR2023-00332 Page 00429
`
`

`

`WO 98/40842
`
`PCT/0S98/04700
`
`14
`
`(4.3.5)
`
`M _1
`J--,·•·12
`·-1
`
`.
`
`(4.3.6}
`
`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.
`
`5
`
`10
`
`For YIQ to RGB:
`r 1.000
`1Rl
`I
`lGl=I 1.000
`LBJ L 1.000
`
`0.956
`-0.272
`-1.106
`
`0. 6217 1Yl
`-0.647j I Ii
`1. 703J L QJ
`
`For YTJV to RGB:
`r 1.000
`rR1
`!
`IGl=I 1.000
`LBJ L 1.000
`
`0.000
`-0.395
`2.032
`
`1.1407 fYl
`lul
`-0.581!
`0.000J LVJ
`
`(5)
`
`{ 6)
`
`15
`
`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 nurnbe:- of
`Information
`processing filters at compression time.
`defining the selected filters can be stored in the coded
`image file, in a form such as a one byte flag in a file
`In addition to optionally applying the filtersr
`20 header.
`
`IPR2023-00332 Page 00430
`
`

`

`i
`' I
`
`i'
`
`I
`,j
`I
`
`I
`
`WO 98/40842
`
`PCT/US98/04700
`
`15
`
`the method can also be implemented to automatically
`detect and apply the selected filters
`following
`decompression.
`To sharpen an image, a filter is used that
`5 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
`10 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.
`To smooth images, for every pixel, the average
`of the pixel and the eight adjacent pixels is calculated.
`15 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.
`To brighten images, the weighted sum of each
`pixel and the correspond eight adjacent pixels is
`20 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.
`Another filter that can be used is one that adds
`a random value between [-12, 12] to each of the pixels in
`the image.
`In FIG. 6 there is displayed a preferred
`hardware platform that can execute software for
`irnpleme~ting an embodiment of the present invention. The
`computer system of FIG. 3 includes 2 CPU 62, a main
`30 memory 64, an I/0 subsystem 66, and a display 68, all
`coupled to a CPU bus 70. The I/0 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
`35 devices, peripherals 72-76 can be implemented using a
`single memory device, such as a hard disk drive commonly
`found in computers.
`
`25
`
`IPR2023-00332 Page 00431
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`10
`
`15
`
`20
`
`16
`The image source 72 may be a digital still image
`or video source, such as a CD-ROM drive, scanner, or
`In addition, the image source 85 can
`network connection.
`include analog video sources, such as a video camera,
`5 VCR, television broadcast or cable receiver. The analog
`video signals would be converted to a digital form by the
`image source 85 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/0 subsystem 66.
`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.
`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.
`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
`35 decompression system 82. The compression system 81 can
`be configured to perform any one or combination of the
`compression methods set forth in FIGS. lr 8, 10, and 12;
`
`25
`
`30
`
`IPR2023-00332 Page 00432
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`17
`
`5
`
`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.
`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.
`The color converter 84 performs a color space
`transformation on the input pixels, such as any of those
`10 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.
`The decompressor 88 expands the compressed image
`file by applying an inverse wavelet transformation, as
`25 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.
`30 Standard electronic components are readily available for
`performing the function of the inverse color converter
`90.
`
`15
`
`20
`
`35
`
`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.
`
`IPR2023-00332 Page 00433
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`18
`
`5
`
`In step 104, the pixels are subjected to a wavelet
`In step 106, sub-band quantization is
`transformation.
`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.
`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
`10 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
`That is, the number of bits one wishes to
`quantization.
`15 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
`In this way, the number of bits resulting from
`bits.
`quantization will remain the same, but their allocation
`20 will differ depending upon the nature of the image. This
`technique greatly improves image quality while
`maintaining a high compression ratio.
`FIG. 9 illustrates a flow diagram of a method of
`decompressing an image compressed according t6 the
`25 methods shown in FIG. 8. Step 120, the compressed file
`In step 122, the input image is entropy
`is input.
`In step 124, de-quantization is performed on
`decoded.
`the decoded image file. Next, in step 126, an inverse
`wavelet transform is performed on the image..
`In step
`In
`30 128, an inverse color transformation is performed.
`step 130, post-processing altering is optionally
`In step 132, the decompressed image file is
`performed.
`then displayed.
`FIG. 10 illustrates a flow diagram of a method
`35 of compressing an image in accordance with another
`embodiment of the present invention. This method
`performs color-bit depth compression, which essentially
`
`IPR2023-00332 Page 00434
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`19
`
`15
`
`20
`
`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
`5 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,
`10 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.
`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.
`FIG. 12 illustrates another method of
`compressing an image in accordance with another
`embodiment of the present invention.
`In this method, a
`user can selective vary compression parameters (step 173)
`to obtain a lossless or near-lossless compressed image at
`a desired compression ratio.
`In step 170 1
`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
`
`25
`
`30
`
`35
`
`I:
`
`I
`
`I
`
`IPR2023-00332 Page 00435
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`5
`
`20
`interface. These parameters can include those described
`herein below in the subsection title "Peak Signal to
`In step 174,
`Noise Ratio (PSNR) Controlled Compression".
`an integer wavelet transform is performed on the color
`In step 176, the wavelet
`transformed pixels.
`coefficients are entropy coded. Next, in step 178, the
`compressed image file is then output from the system.
`The integer color transformation of step 172 is
`an integer reversible transform which can be used in
`10 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.
`The RGB to Y-Nb-Nr transform is given by the
`equations:
`
`15
`
`20
`
`25
`
`30
`
`35
`
`y = G + Int(R/2 + B/2),
`Int (Y/2),
`Nb = B
`Int(Y/2).
`Nr = R
`
`The integer wavelet transform of step 174 is
`described below in detail.
`FIG. 13 illustrates a method of decompressing an
`image file that has been compressed according to the
`In step 180, a compressed image
`method shown in FIG. 12.
`In step 182, the image is entropy
`file is input.
`decoded. Next, in step 184, an inverse integer wavelet
`In step 186,
`transform is performed on the decoded data.
`an inverse integer color transform is performed. Next 1
`in step 188 optional post-processing filtering is
`the
`performed on the image. Next, in step 190 1
`decompressed image is displayed.
`The Y-Nb-Nr to RGB transform of step 186 is
`given by the equations:
`R = Nr + Int(Y/2),
`B =Nb+ Int(Y/2),
`G = Y -
`Int (R/2 + B/2)
`The inverse integer wavelet transform of step
`184 is described in detail below.
`
`IPR2023-00332 Page 00436
`
`

`

`WO98/40842
`
`PCT /US98/04700
`
`21
`
`5
`
`Reversible Integer Wavelet Transform
`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
`10 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.
`
`15
`
`Basic Integer Wavelet Transformations
`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
`20 dimensions is immediate as the rows and columns can be
`treated into a sequence of one dimensional signals. For
`
`the following examples, assume that
`
`is the
`
`original signal where the superscript indicates level and
`the subscript indicates a particular point in the signal.
`1 and {d};}M1
`- 1
`Also, {c;;}N1
`
`are its decomposition parts at the
`
`-
`n°0
`
`n=O
`
`25
`
`first level. Here
`
`i
`
`I
`
`I
`I
`
`I
`
`I',
`
`IPR2023-00332 Page 00437
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`22
`
`i f N is an even number,
`
`N,= { ~ ~ ,
`
`i f N is an odd nwnber;
`
`M1 =N-N1
`
`{c 1}N1-1and{d1}n,-1
`n n•o
`n n•O
`
`' t 1
`are l
`OW
`S
`
`-F
`.L.requency
`
`(1)
`
`part and high frequency (h) part, respectivelyo For
`{cl}N1-l as JcO}Nl
`l n n=o
`
`and repeat
`
`multi-levels, we just create
`
`n n=O
`
`the procedure again.
`Example 1: A (2,2)-wavelet transform by integer
`calculation.
`This transformation is similar to a variation of
`the Haar wavelet transform which uses low and
`high pass analysis (decomposition) filters given
`as:
`
`5
`
`10
`
`n
`
`En
`9'n
`
`0
`
`1
`
`1/2
`1/2
`
`1/2
`-1/2
`
`I
`
`(1) Compute
`
`(2) Compute
`
`(2 .1)
`
`IPR2023-00332 Page 00438
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`23
`
`d~-1
`0
`Int(--) +C2 k+i, i f N is an even number,
`1
`2
`Cn -1 =
`l
`{
`c!-1 ,
`
`i f N is an odd number.
`
`(2. 2)
`
`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-l<Int(x)~ x,
`5 etc. It is easy to see that all entries in both
`{c 1}N,-l and {d 1}Mi-l are integers.
`
`n n•O
`
`n n•O
`
`From (2.1)-(2.2), we can easily get the
`following integer reconstruction algorithm:
`Reconstruction
`(b)
`(l)If N is an even number, compute:
`
`10
`
`or, if N is an odd number, we have
`
`(2) Compute
`
`(2. 3)
`
`(2. 4)
`
`(2.5)
`
`I
`
`IPR2023-00332 Page 00439
`
`

`

`WO98/40842
`
`PCT/US98/04700
`
`24
`
`Remark. Since (2.1)-(2.6) 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.
`
`Example 2: Lazy wavelet transform.
`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:
`
`5
`
`10
`
`1
`0
`ck=c2k, k=O, ... ,N1 -l;
`d;=clk ... 1 , k=O, ... , M1 -1.
`
`15
`
`Examples 1 and 2 are not good transforms for
`image compression, but they are s~mple. 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.
`It is noted that there is another interesting
`20 property in the above two transforms which may not be
`If the values of the signal pixels are
`easily seen.
`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
`25 computer itself because of the complementary code
`property. Whilef 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.
`It is known that the general values for the high
`frequency wavelet coefficients are small, and all higher
`levels of the decomposition also provide generally small
`
`30
`
`IPR2023-00332 Page 00440
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`25
`
`5
`
`values in the high frequency band. This allows the
`preservation of precision during the computational stage
`the complementary code
`of the wavelet coefficients. Now,
`property, the other aspect of the PPP property is a well
`known characteristic of integer arithrr,etic as done by the
`computer. Consider the com