lap?
`
`:111 1111 1,[trak Imp 1I3
`
`ijohryin-nr-mmurm
`
`maimemmoing TILE KC P-REsEsont
`ccoAkm
`UNITED STATES DEPARTMENT OF COMMERCE
`United States Patent and Trademark Office
`
`May 02, 2018
`
`THIS IS TO CERTIFY THAT ANNEXED IS A TRUE COPY OF
`THE INTERNATIONAL PUBLICATION NUMBER WO 98/40842
`PUBLISHED SEPTEMBER 17, 1998.
`
`By Authority of the
`Under Secretary of Commerce for Intellectual Property
`and Director of the United States Patent and Trademark Office
`
`, -144/
`. MONTGO 1 RY
`Certifying Officer
`
`I fl
`
`rin
`
`m Llllltllr
`
`inioinamili1131Mium;;;Girtimt6mminvilinonna
`
`hk4Z1-1111I
`
`1"
`
`Olnitlirmr41111
`
`!LIU
`
`Comcast - Exhibit 1016, page 1
`
`

`

`PCT
`INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`WO 98/40842
`
`WORLD INTELLECTUAL PROPERTY ORGANIZATION
`International Bureau
`
`(51) International Patent Classification 6 :
`GO6K 9/00
`
`(11) International Publication Number:
`
`Al
`
`(43) International Publication Date:
`
`17 September 1998 (17.09.98)
`
`(21) International Application Number:
`
`PCT/US98/04700
`
`(22) International Filing Date:
`
`11 March 1998 (11.03.98)
`
`(30) Priority Data:
`60/040,241
`09/038,562
`
`11 March 1997 (11.03.97)
`10 March 1998 (10.03.98)
`
`US
`US
`
`(71) Applicant: COMPUTER INFORMATION AND SCIENCES,
`INC. [US/US]; Suite 104, 3401 East University, Denton, TX
`76208 (US).
`
`(72) Inventors: CHAO, Hongyang; 1011 Chestnut #10, Denton, TX
`76201 (US). HUA, Zeyi; 2197 S. Uecker #357, Denton,
`TX 76201 (US). FISCHER, Howard, P.; 3106 Saints
`Circle, Denton, TX 76201 (US). FISCHER, Paul, S.; 34
`Timbergreen Circle, Denton, TX 76205 (US).
`
`(74) Agents: SAMPLES, Kenneth, H. et al.; Fitch, Even, Tabin &
`Flannery, Room 900, 135 S. LaSalle, Chicago, IL 60603
`(US).
`
`(81) Designated States: AL, AM, AT, AU, AZ, BA, BB, BG, BR,
`BY, CA, CH, CN, CU, CZ, DE, DK, EE, ES, FI, GB,
`GE, GH, GM, GW, HU, ID, IL, IS, JP, KE, KG, KP, KR,
`KZ, LC, LK, LR, LS, LT, LU, LV, MD, MG, MK, MN,
`MW, MX, NO, NZ, PL, PT, RO, RU, SD, SE, SG, SI,
`SK, SL, TJ, TM, TR, TT, UA, UG, UZ, VN, YU, ZW,
`ARIPO patent (GH, GM, KE, LS, MW, SD, SZ, UG, ZW),
`European patent (AT, BE, CH, DE, DK, ES, FI, FR, GB,
`GR, IE, IT, LU, MC, NL, PT, SE), OAPI patent (BF, BJ,
`CF, CG, CI, CM, GA, GN, ML, MR, NE, SN, TD, TG).
`
`Published
`With international search report.
`Before the expiration of the time limit for amending the
`claims and to be republished in the event of the receipt of
`amendments.
`
`(54) Title: SYSTEM AND METHOD FOR IMAGE COMPRESSION AND DECOMPRESSION
`
`(57) Abstract
`
`A wavelet—based image compression sys-
`tem and method are presented (24). Compression
`is accomplished by performing a wavelet trans-
`formation of an input digital image (20). The
`resulting wavelet coefficients are compared to a
`threshold value. Coefficients falling below the
`threshold are discarded. The remaining coeffi-
`cients are quantized (26). The quantized coeffi-
`cients are then compressed using an entropy en-
`coding technique (28).
`
`INPUT ORIGINAL IMAGE
`
`DISPLAY IMAGE
`
`20
`
`2
`
`IMAGE TRANSFORMATIONS
`
`V
`QUANTIZATION AND THRESHOLDING
`
`24
`
`26
`
`ENCODING
`
`28
`
`OUTPUT COMPRESSED IMAGE FILE
`
`30
`
`Comcast - Exhibit 1016, page 2
`
`

`

`FOR THE PURPOSES OF INFORMATION ONLY
`
`Codes used to identify States party to the PCT on the front pages of pamphlets publishing international applications under the PCT.
`
`AL
`AM
`AT
`AU
`AZ
`BA
`BB
`BE
`BF
`BG
`BJ
`BR
`BY
`CA
`CF
`CG
`CH
`CI
`CM
`CN
`CU
`CZ
`DE
`DK
`EE
`
`Albania
`Armenia
`Austria
`Australia
`Azerbaijan
`Bosnia and Herzegovina
`Barbados
`Belgium
`Burkina Faso
`Bulgaria
`Benin
`Brazil
`Belarus
`Canada
`Central African Republic
`Congo
`Switzerland
`Cote d'Ivoire
`Cameroon
`China
`Cuba
`Czech Republic
`Germany
`Denmark
`Estonia
`
`ES
`FI
`FR
`GA
`GB
`GE
`GH
`GN
`GR
`HU
`IE
`IL
`IS
`IT
`JP
`KR
`KG
`KP
`
`KR
`KZ
`LC
`LI
`LK
`LR
`
`Spain
`Finland
`France
`Gabon
`United Kingdom
`Georgia
`Ghana
`Guinea
`Greece
`Hungary
`Ireland
`Israel
`Iceland
`Italy
`Japan
`Kenya
`Kyrgyzstan
`Democratic People's
`Republic of Korea
`Republic of Korea
`Kazakstan
`Saint Lucia
`Liechtenstein
`Sri Lanka
`Liberia
`
`LS
`LT
`LU
`LV
`MC
`MD
`MG
`MK
`
`ML
`MN
`MR
`MW
`MX
`NE
`NL
`NO
`NZ
`PL
`PT
`RO
`RU
`SD
`SE
`SG
`
`Lesotho
`Lithuania
`Luxembourg
`Latvia
`Monaco
`Republic of Moldova
`Madagascar
`The former Yugoslav
`Republic of Macedonia
`Mali
`Mongolia
`Mauritania
`Malawi
`Mexico
`Niger
`Netherlands
`Norway
`New Zealand
`Poland
`Portugal
`Romania
`Russian Federation
`Sudan
`Sweden
`Singapore
`
`SI
`SK
`SN
`SZ
`TD
`TG
`TJ
`TM
`TR
`TT
`UA
`UG
`US
`UZ
`VN
`YU
`ZW
`
`Slovenia
`Slovakia
`Senegal
`Swaziland
`Chad
`Togo
`Tajikistan
`Turkmenistan
`Turkey
`Trinidad and Tobago
`Ukraine
`Uganda
`United States of America
`Uzbekistan
`Viet Nam
`Yugoslavia
`Zimbabwe
`
`Comcast - Exhibit 1016, page 3
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`SYSTEM AND METHOD FOR IMAGE COMPRESSION AND DECOMPRESSION
`
`This application claims the benefit of U.S.
`Provisional Application No. 60/040,241, filed March 11,
`1997, System and Method for Still Image Compression,
`5 which is incorporated herein by reference.
`
`Field of the Invention
`
`The present invention relates generally to
`
`digital image compression/decompression, and
`
`particularly, to a wavelet-based system and method of
`10 image compression and decompression.
`
`Background of the Invention
`
`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
`15 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
`20 (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
`
`25 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.
`
`In addition imaging systems, compression
`
`30 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
`
`Comcast - Exhibit 1016, page 4
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`2
`
`include video telephones, remote security systems, and
`other types of monitoring systems.
`Several standards for compressing real-time
`video currently exist. The H.263 standard for real-time
`5 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
`10 performs interframe coding adequately, its compression
`ratio and speed can be improved upon.
`Various other types of data compression have
`been developed in recent years. Conventional data
`compression techniques are generally referred to as being
`15 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
`20 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
`25 that may be required or even useful at some later point.
`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
`30 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.
`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,
`
`35
`
`Comcast - Exhibit 1016, page 5
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`3
`
`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
`5 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
`10 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.
`
`15
`
`Summary of the Invention
`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
`20 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
`25 and decompress images, as well as the time required to
`
`perform the same.
`
`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
`
`30 images.
`
`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.
`
`35
`
`According to one aspect of the invention, a
`wavelet-based image compression method can be implemented
`using a software program. Compression is accomplished by
`
`Comcast - Exhibit 1016, page 6
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`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
`
`10 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
`
`15 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
`
`25 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.
`
`30
`
`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
`35 compressor can be implemented using one or more
`electronic components, such as application specific
`integrated circuits (ASICs), microprocessors, discrete
`
`Comcast - Exhibit 1016, page 7
`
`

`

`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.
`
`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
`15 embodiment of the present invention;
`FIGS. 2-4 depict wavelet coefficients for
`various 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. 1;
`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
`30 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
`
`Comcast - Exhibit 1016, page 8
`
`

`

`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
`
`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
`
`of the invention. In step 20, a digital image is
`
`15 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
`
`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
`
`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
`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
`images. In order to get a higher compression ratio, the
`
`Comcast - Exhibit 1016, page 9
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`7
`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.
`
`5 RGB to YIQ:
`
`FY1=- 0.299
`111=1-0.596
`LIQJ.L 0.212
`
`0.587
`
`-0.275
`
`-0.523
`
`0.1141 FR71
`0.3211 IGI
`0.311] LBJ
`
`10
`
`RBG to YUV:
`FY14 0.299
`0.587
`1U1=1 0.148 -0.289
`LVJ=L 0.615 -0.515
`
`0.1141 rR1
`0.4391 IGI
`-0.1] LB]
`
`In the YIQ color space, there is one
`luminescence (Y) and two color planes (I, Q). The Y
`15 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
`20 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
`25 transform. However, to develop a better understanding of
`the preferred transform, the following alternative
`wavelet transform is first described.
`
`Let C° = [CTO (j - 0, ..., M-1; k = 0, ...,
`
`N-1) represent the original, uncompressed image, where M
`30 and N are integers which have the common factor 2L (L is a
`positive integer). A one-level wavelet decomposition,
`where L = 1, results in the four coefficient quadrants as
`
`Comcast - Exhibit 1016, page 10
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`8
`
`shown in Figure 2. Each quadrant represents a set of
`wavelet coefficients.
`Quadrant Cl represents the blurred image of the
`original image C°, where Cl =[c.4] (j=o,...,1-1;
`
`5 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
`10 example, for L = 2, C° is set to equal Cl. The iterative
`formula for computing a decomposition is given as
`follows:
`(1) Let ° = rC°, r>0 is a factor which can be changed for
`different needs.
`15 (2) Transform for image columns:
`For k=0,...,N-1, calculate
`
`al -ETic-"-C-:IC
`Ok.,
`2
`M ,
` 1 ,,.., o
`,13.
`077-0 z.
`-'2j,k' L'2j+i,k) I i =1 I ••• I '--- - J. •
` k L'2j- 1,k - '
`''k --
`2
`4
`3
`
`(3.1.1)
`
`For k=0,...,N-1, calculate
`
`'- '0k
`
`'1,k
`
`,
`
`;_,1 .7,0 _ aok+a1,k
`2
`x .,.,4
`M
``4.1k . `4.1+1,k 4 _..1
`, j - J. , •••
`-
`' 2 '
`2
`
`,,....3 7,
`l. jk = L.2 j + 1 , k-
`
`(3.1.2)
`
`)- e';2 2
`
`a
`2, k=E;; o 1,k--2-'
`
`
`
`
`, k.
`
`(3) Transform for rows:
`For j = 0, . . . M/2 - 1, computing
`
`Comcast - Exhibit 1016, page 11
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`9
`
`-
`di
`.7,o
`
`2
`
`(3.1.3)
`
`hdfic-
`
`4 (— .-j
`C
`
`2k-1-2 ° j,2k+1, 1-elj,2k+1) 1 Ic'.--1 - — 11
`'
`-
`2
`
`-1 .
`
`and
`
`-7.
`I.
`c.10.=ci , i -
`
`hdj•o+hdjii
`2
`
`1
`
`,..1
`1
`,..,e--i-
`j,2k+1-
`t-j
`
`h 3,d1
`
`1
`k +hd3,k+i,
`2
`
`-2,
`
`2
`
`(3.1.4)
`
`-1
`
`N-2
`2 -
`
`For j = 0,
`
`.
`
`.
`
`.
`
`, M/2 - 1, computing
`
`ddl - aj-,1-210
`2,0
`2
`
`dd 4-jk= 1 -a" (al 3,2k-1- 22.1,2k+a7,2k4-7.)
`{
`
`2
`
`(3.1.5)
`
`and
`
`vd1 o -al
`34-
`
`dcl; 0+ dcla
`2
`
`<
`
`1
`
`'1
`
`Vdik=a j, 2k+1
`
`ddb, -dd4",
`.7k+1
`2
`
`,
`
`, •••
`
`M
`2
`
`,
`
`(3.1.6)
`
`-ddlvd3., 11-2 =a N-1,k
`
`
`j, N-2
`2
`
`'
`
`(4) C1=
`k=0,...
`-2-
`
`-1.
`
`, HD 3- = [hdj • ,
`
`, VD1 [u
`
`, lc] and DD= [dd31-, k] ,
`
`41-1
`
`Remark: If it is necessary, we also can use matrix
`5 multiply Wavelet Coefficient Image of 1 levels=WiC°WiT.
`
`Comcast - Exhibit 1016, page 12
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`10
`
`Here, W1 is the transform matrix for 1 level wavelet
`decomposition.
`
`FIG. 3 depicts a three-level wavelet
`
`decomposition, where L = 3.
`
`5
`
`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
`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 spatial frequencies, which reduces the size of a
`
`20
`
`compressed image.
`A multilevel uniform thresholding method can be
`used as described below.
`tL, ti„.1) be the chosen
`Let T = (t
`thresholds, where tt is the threshold for 1 the (1=1,
`L) level and tL+1 is a threshold for blurred image CL.
`25 Thresholding sets every entry in the blocks CL, HD1, VD'
`
`0
`
`0 0f
`
`and M I (1 = I,
`
`L) to be zero if its absolute value is
`
`not greater than the corresponding threshold.
`
`For color images, three threshold vectors which
`
`correspond three different color planes, such as y, I and
`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.
`
`Comcast - Exhibit 1016, page 13
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`rT`11 HD
`1
`q VD
`
`rf
`•-1l DD
`
`,
`'I 2 HD
`2
`q 2
`rf
`'12 DD
`
`VD
`
`11
`
`• • •
`
`CI LHD
`L
`q VD
`
`CILDD
`
`L.1
`SIC
`
`5
`
`TABLE 1
`In Table 1, the entries a .1HD are quantization
`L), qlvt, and a .2DD for
`factors for blocks HD' (1 = I,
`L) respectively, and the
`blocks VD' and DD1 (1 = I,
`factor ca,L+1 is for the most blurred image CL. The factors
`can be integers between 0 and 255. The quantization
`L) is
`10 scheme for the block HD' (1 = I,
`
`hd1 ' - g -2n
`,j=0,
`.171Z11- =round
`j,k
`1
`max
`HD
`
`—
`21
`
`-
`
`N
`2
`
`(3.2.1
`
`Here,
`
`(i =0 ,..., 2 -11-2
`
`- 1;
`
`k=0 T:i -1) are quantized
`
`wavelet coefficients of block HD1 (1=1,...,L)
`
`maxh,D1 = max ( Ihdl,k1)
`(M/21-1)
`$31c (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
`20 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.
`
`Comcast - Exhibit 1016, page 14
`
`

`

`WO 98/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-
`5 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
`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-
`15 quantized data. In step 48, optional image post-
`processing takes place to refine the decompressed image.
`In step 50, the decompressed image is displayed.
`
`The decoding of step 42 is the inverse operation
`
`of the encoding of step 28. Similarly, it can be divided
`20 into two parts: Entropy decoding (Huffman or
`
`arithmetic), and coefficient rearranging.
`
`The decoding step produces quantized wavelet
`
`coefficients in 3*L+1 blocks. Dequantizing (step 44)
`uses the same quantization table as quantizing (Table 1),
`25 and the scheme as follows: for 1 = I,
`L
`
`hd
`
`l
`
`
`
`Cd
`
`j,
`
`
`
`aX -I
`
`gr im
`
`M
`
`LD
`
`=
`
`°
`
`"
`
`
`
`i2M -1
`
` k--
`
`0,...,2
`
`-1, (4.2.1)
`
`Equation (4.2.1) produces the approximate coefficients
`for the blocks HD' (1 = I,
`L), which are shown in
`FIG. 3. The dequantizing scheme for other blocks is
`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. FIG. 4 depicts a
`one-level wavelet reconstruction.
`
`30
`
`Comcast - Exhibit 1016, page 15
`
`

`

`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:
`
`5
`
`For j=0,
`
` M -1, calculate
`
`dj,l
`
`_udj 0 +
`
`ddl +dl
`dj,i
`2
`
`
`ddl -d& k
`j ' ic+1 k=1
`
`2
`
`
`
`2 -2
`N
`
`(4.3.1)
`
`a3,2k+1'ocl k
`4
`
`k
`
`j N-1 +dd l,
`3. 2
`2
`
`and
`
`and
`
`a'„= dj',1-2 dc1.1', 0 ,
`{
`al
`+al
` j,2k-1
`x.
`2
`
`"j,2k -
`
`j,2k+1
`-2d&
`j,k,
`
`k- 1
`
`-
`
`-I•••
`
`(4.3.2)
`
`N -1.
`
`-
`
`'
`
`For j=0, ..., M/2 - 1, calculate
`
`hd31.0+hc134.1
`
`3.
`1 _
`ci , l-cio +
`2
`1 h4 k-124k.3. ,
`< A1
`,-.1, 2k+1= Cjk +
`2
`Oli,N_1=Ci , N-2 +hd .,1. , N_2 .
`2
`2
`"'
`
`i A.
`
`-
`
`1
`
`, ••• ,
`
`N
`.. 2,
`2
`
`(4.3.3)
`
`t''' 1
`&- -2hd l
`{ 3,o= 3 1
`i3O,
`
`A i
` /A i
`-Al
`‘-'j 2k =— k (-- j 2k 1. -r t-- 1 2k 1) -2hd l k=1 N 1 jk, -, — -
`
`'
`2
`' -
`-' +-
`2
`
`
`
`•
`
`(4.3.4
`
`(2) Inverse transform for column:
`For k=0,
`N - 1, calculate
`
`10
`
`and
`
`Comcast - Exhibit 1016, page 16
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`14
`
`IIci° ,k=egk+ a°1k+ all' k ,
`1c'c';)k= cfk -2 a olk,
`
`2
`-a1
`„..1 _i_ a k
`77o
`'-'2.1+1,k=.-jk •
`31 2
`,o
`,_,,,13.
`xl
`‘'N-1 , k=" 1-• N-2 k -r " N-2 k •
`2
`'
`2
`'
`
`j+1,k , i
`
`____M _2 ,
`.=3. , ...
`' 2
`
`(4.3.5)
`
`1-•2j
`
`_
`
`2
`
`C2j-1,k '
`
`) - z•Ltik,
`
`•
`j =1 , ••• — - 1.
`2
`
`(4.3.6)
`
`(3)
`
`c.79, k=e39, k /r, j=0,-,M- 1; k=0,..., N-1
`
`[ c3,k1 fe•
`
`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:
`
`1R1 1 1.000
`0.6211 FY1
`0.956
`1G1=1 1.000 -0.272 -0.6471 111
`[EU L 1.000 -1.106
`1.703) Lcd
`
`For YUV to RGB:
`1.1401 ryl
`imi r 1.000
`0.000
`'GI.' 1.000 -0.395 -0.5811 1U1
`I_Ed L 1.000
`0.000] LVJ
`
`2.032
`
`(5)
`
`(6)
`
`In step 48, a user can optionally apply image
`filtering to improve the image quality. Filters are
`15 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
`20 header. In addition to optionally applying the filters,
`
`Comcast - Exhibit 1016, page 17
`
`

`

`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
`25 the image.
`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
`30 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
`35 devices, peripherals 72-76 can be implemented using a
`single memory device, such as a hard disk drive commonly
`
`found in computers.
`
`Comcast - Exhibit 1016, page 18
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`16
`
`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 85 can
`
`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-
`
`10 time video to the I/O 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.
`
`15
`
`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
`20 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
`
`25 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
`30 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. 1, 8, 10, and 12;
`
`Comcast - Exhibit 1016, page 19
`
`

`

`WO 98/40842
`
`PCT/US98/04700
`
`17
`
`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
`5 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
`15 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
`20 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 valu