(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2004/0228527 A1
`(43) Pub. Date:
`Nov. 18, 2004
`Ourcha et al.
`
`US 2004O228527A1
`
`(54) METHOD AND APPARATUS FOR BLOCK
`BASED IMAGE COMPRESSION WITH
`MULTIPLE NON-UNIFORM BLOCK
`ENCODINGS
`
`(76) Inventors: Konstantine Iourcha, San Jose, CA
`(US); Andrew S.C. Pomianowski, Palo
`Alto, CA (US); Raja Koduri, Santa
`Clara, CA (US)
`Correspondence Address:
`COUDERT BROTHERS LLP
`333 SOUTH HOPE STREET
`23RD FLOOR
`LOS ANGELES, CA 90071 (US)
`(21) Appl. No.:
`10/778,902
`(22) Filed:
`Feb. 13, 2004
`Related U.S. Application Data
`(60) Provisional application No. 60/447,862, filed on Feb.
`13, 2003.
`
`Publication Classification
`
`(51) Int. Cl." ............................... G06K 9/00; G06K 9/36
`(52) U.S. Cl. ............................................ 382/166; 382/232
`(57)
`ABSTRACT
`Embodiments of the present invention are directed to a
`method and apparatus for block based image compression
`with multiple non-uniform block encodings. In one embodi
`ment, an image is divided into blocks of pixels. In one
`embodiment the blocks are four pixels by four pixels, but
`other block sizes are used in other embodiments. In one
`embodiment, a block of pixels in the original image is
`compressed using two different methods to produce a first
`and Second compressed block. Thus, each block in the
`original image is represented by two, typically different,
`compressed blockS. In one embodiment, color associated
`with a pixel is determined by combining the compressed
`information about the pixel in the first compressed block
`with information about the pixel in the Second compressed
`block. In another embodiment, global information about the
`image is combined with the information in the first and
`Second compressed blockS.
`
`Tiage Divided into
`Plurality of Blocks
`
`
`
`
`
`Each Block is
`Decomposed into a
`Plurality of Decomposed
`Blocks
`
`Each Decomposed block
`is Compressed to Foma
`Plurality of Compressed
`Blocks
`
`The Piurality of
`Compressed Blocks are
`Combined to Generate
`an Output Block
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 1 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 1 of 13
`
`US 2004/0228527 A1
`
`
`
`100
`Image Divided into
`Plurality of Blocks
`
`110
`Each Block is
`Decomposed into a
`Plurality of Decomposed
`Blocks
`
`120
`Each Decomposed Block
`is Compressed to Form a
`Plurality of Compressed
`Blocks
`
`130
`The Plurality of
`Compressed Blocks are
`Cornbined to Generate
`an Output Block
`
`Figure 1
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 2 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 2 of 13
`
`US 2004/0228527 A1
`
`
`
`200
`First Value Associated
`With Pixel Decoded From
`First Compressed Block
`
`210
`Second Value Associated
`With Same Pixel
`Decoded From Second
`Compressed Block
`
`220
`First and Second Values
`Are Combined
`
`Figure 2
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 3 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 3 of 13
`
`US 2004/0228527 A1
`
`
`
`300
`Best Fit Curve With
`Endpoints of Pre
`Determined Size is
`Determined
`
`310
`Endpoints Stored as Part
`of Compressed Block
`
`32O
`Each Pixel in Block is
`Encoded as an Index into
`Group of Possible Color
`Values
`
`330
`indices Stored as Part of
`Compressed Block
`
`Figure 3
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 4 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 4 of 13
`
`US 2004/0228527 A1
`
`
`
`400
`Best Fit Curve With
`16-Bit Endpoints
`Determined
`
`410
`16-Bit Endpoints Stored
`as Part of Compressed
`Block
`
`420
`Each Pixel in Block is
`Encoded as 2-Bit Index
`into Group of Possible
`Color Values
`
`430
`indices Stored as Part of
`Compressed Block
`
`Figure 4
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 5 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 5 of 13
`
`US 2004/0228527 A1
`
`
`
`500
`Function Applied to Each
`Value of PixelBlock to
`Obtain New Value
`
`510
`Best Fit Curve With
`Endpoints of Pre
`Determined Size is
`Determined. Using New
`Values
`
`52O
`Endpoints Stored as Part
`of Compressed Block
`
`53O
`Each Pixel in Block
`Encoded as Index into
`Group of Possible Color
`Values
`
`540
`Indices Stored as Part of
`Compressed Block
`
`Figure 5
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 6 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 6 of 13
`
`US 2004/0228527 A1
`
`
`
`600
`Each 24-BitPixel Value
`Converted to 8-Bit Value
`by Applying a Function
`
`610
`New Values Placed in
`New PixelBlock
`
`62O
`Best Fit Curve With 8-Bit
`Endpoints is Determined
`
`63O
`8-Bit Endpoints Stored as
`Part of Compressed
`Block
`
`640
`Each Pixel in Block is
`Encoded as 3-Bit Index
`into Group of Possible
`Color Values
`
`650
`indices Stored as Part of
`Compressed Block
`
`Figure 6
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 7 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 7 of 13
`
`US 2004/0228527 A1
`
`700
`Image Divided into
`Plurality of PixelBlocks
`
`710
`Each PixelBlock is
`Decomposed into Two
`Decomposed Blocks, viz.
`Decomposed First Block
`and Decomposed
`Second Block
`
`72O
`Decomposed First Block
`is Compressed Using a
`First Compression
`Method
`
`
`
`
`
`
`
`730
`Decomposed Second
`Block is Compressed
`Using a Second
`Compression Method
`
`
`
`Figure 7
`
`
`
`
`
`
`
`
`
`
`
`740
`ls Error Generated by the
`First and Second Compression
`Methods Greater ThanThreshold
`Value?
`
`750
`Encoding is Acceptable
`
`
`
`
`
`
`
`760
`Values in Compressed
`Blocks Are Altered to
`Reduce Error
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 8 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 8 of 13
`
`US 2004/0228527 A1
`
`- - - - - - - - - - - - - -
`
`PROCESSOR
`
`813
`
`
`
`MOUSE
`81
`
`VIDEO AMP
`816
`
`VIDE MEM
`
`|MASS STORAGE
`
`82
`
`
`
`
`
`
`
`817
`
`
`
`
`
`COMM
`INT
`
`820
`
`818
`
`MAN
`
`- - - - - - -
`
`MEMORY
`
`815
`
`- - - - - - - - - - - -
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NETWORK LINK 821
`
`LOCAL
`NETWORK
`822
`
`
`
`INTERNET
`825
`
`FIGURE 8
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 9 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 9 of 13
`
`US 2004/0228.527 A1
`
`
`
`900
`First Subset is
`Compressed
`
`910
`Compressed First Subset
`is DeCompressed
`
`920
`The Results of the
`Decompression are Fed
`to a Decomposer Device
`that Changes the Data
`Value of the Second
`Subset
`
`930
`The Second Subset is
`Compressed
`
`Figure 9
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 10 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 10 of 13
`
`US 2004/0228527 A1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1000
`First Subset is
`Compressed
`
`
`
`1010
`Compressed First Subset
`is Decompressed
`
`
`
`1020
`The Results of the
`Decompression are Fed
`to a Decomposer Device
`that Changes the Data
`Value of the Second
`Subset
`
`1050
`The Results of the
`Decompression are Fed
`to a DeComposer Device
`that Changes the Data
`Value of the First Subset
`
`Figure 10
`
`1030
`The Second Subset is
`Compressed
`
`
`
`
`
`1040
`Compressed Second
`Subset is Decompressed
`
`
`
`1060
`Has the optimization met the desired
`threshold?
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 11 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 11 of 13
`
`US 2004/0228527 A1
`
`
`
`
`
`
`
`
`
`
`
`
`
`1100
`An Original image Block
`is Projected onto a
`Predefined Vector
`
`1110
`Magnitude is Stored in a
`First New Block by a
`Decomposer Device
`
`1120
`The Projected image is
`Subtracted From the
`Original image
`
`Figure 11
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 12 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 12 of 13
`
`US 2004/0228.527 A1
`
`1200
`An Original Image is
`Projected onto a
`Predefined Vector
`
`1210
`The Image Magnitude is
`Stored in a First New
`Block by a Decomposer
`Device
`
`1220
`The First New Block is
`Compressed Using Any
`of the Compression
`Schemes to Generate a
`Compressed First Block
`
`1230
`The Compressed First
`Block is Decompressed
`
`1270
`Generate Output Block
`
`
`
`
`
`
`
`1260
`Compressed First Block
`and Compressed Second
`Block are Combined
`
`1240
`The Data Value of the
`Decompressed Block is
`Subtracted from the Data
`Value of the Original
`Block to Generate a New
`Second Block
`
`
`
`
`
`
`
`1250
`The New Second Block is
`Compressed to Generate
`a Compressed Second
`Block
`
`
`
`Figure 12
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 13 of 23
`
`

`

`Patent Application Publication Nov. 18, 2004 Sheet 13 of 13
`
`US 2004/0228.527 A1
`
`13OO
`An Original Image is
`Projected onto a
`Predefined Vector
`
`1310
`The Image Magnitude is
`Stored in a First New
`Block by a Decomposer
`Device
`
`1320
`The First New Block is
`Compressed Using Any
`of the Compression
`Schemes to Generate a
`Compressed First Block
`
`1330
`The Compressed First
`Block is Decompressed
`
`1340
`The Data Value of the
`Decompressed Block is
`Subtracted from the Data
`Value of the Original
`Block to Generate a New
`Second Block
`
`
`
`1350
`The New Second Block is
`Compressed to Generate
`a Compressed Second
`Block .
`
`Figure 13
`
`1390
`Compressed First Block
`is Combined with
`Compressed Second
`Block to Generate an
`Output Block
`
`yes
`
`1380
`Desired Threshold Met?
`
`
`
`
`
`
`
`O
`
`1370
`The Data Value of the
`Third New Block is
`Subtracted from the Data
`Value of the Original
`Block and the Result is
`Stored Back in the First
`Block
`
`1360
`Compressed Second
`Block is Decompressed
`and its Data Value is
`Subtracted from the Data
`Value of the Original
`Block and the Results are
`Stored in a Third New
`Block
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 14 of 23
`
`

`

`US 2004/0228527 A1
`
`Nov. 18, 2004
`
`METHOD AND APPARATUS FOR BLOCK BASED
`IMAGE COMPRESSION WITH MULTIPLE
`NON-UNIFORM BLOCK ENCODINGS
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`0001. The present application claims the benefit of pri
`ority from pending U.S. Provisional Patent Application No.
`60/447,862, entitled Method and Apparatus For Block
`Based Image Compression With Multiple Non-Uniform
`Block Encodings, filed on Feb. 13, 2003, which is herein
`incorporated by reference in its entirety.
`
`BACKGROUND OF THE INVENTION
`0002) 1. Field of the Invention
`0003. The present invention relates to the field of image
`compression, and in particular to a method and apparatus for
`block based image compression with multiple non-uniform
`block encodings.
`0004 2. Background Art
`0005 Typically, there is a desire to compress images used
`for texturing operations in 3D graphics accelerator hardware
`to improve the performance of rendering and reduce the
`memory required to Store the information. However, prior
`art image compression methods frequently produce undes
`ired Visual artifacts when rendering images, making their
`application appropriate for a limited number of images. This
`problem can be better understood with a review of image
`compression.
`Image Compression
`0006)
`0007 Prior art compression techniques can be catego
`rized in at least two ways. First, a technique can be either
`loSS-leSS or lossy. Second, a technique can be either fixed or
`variable rate. A loSS-leSS compression technique is one in
`which no information about the image is lost due to the
`compression. Thus, an image could be compressed and
`decompressed and the decompressed image would be iden
`tical to the original image. A lossy compression technique is
`one in which Some information about the image is lost due
`to the compression. Thus, compression of an image followed
`by decompression could result in a decompressed image that
`is not identical to the original image.
`0008 A fixed rate compression technique reduces the
`Storage requirement of an image by a fixed percentage. Since
`most image formats do not contain unnecessary data, almost
`all fixed rate compression techniques are lossy in general
`(however, they may not be lossy for a particular image). A
`variable rate compression technique reduces the Storage
`requirement of an image by an amount that is not known at
`the time when the image is compressed. In fact, the Storage
`requirement may not be reduced at all.
`0009 Because loss-less, variable rate compression tech
`niques are unable to guarantee any rate of compression,
`graphics Systems typically use lossy, fixed rate compression
`techniques. However, the lossy nature Sometimes results in
`unacceptable image quality (i.e., visual artifacts). Some
`times, it is So difficult to determine when compression will
`result in unacceptable loSS of image quality and when it will
`not that users and/or Systems elect to forgo compression
`altogether. AS Systems are developed that utilize larger
`
`amounts of information about the System, the desire for
`compression increases, but the problem of unacceptable
`image quality loSS also increases in prior art compression
`Systems.
`
`SUMMARY OF THE INVENTION
`0010 Embodiments of the present invention are directed
`to a method and apparatus for block based image compres
`Sion with multiple non-uniform block encodings. In one
`embodiment of the present invention, an image is divided
`into blocks of pixels. In one embodiment the blocks are four
`pixels by four pixels, but other block sizes are used in other
`embodiments.
`0011. In one embodiment, a block of pixels in the original
`image is decompressed into one or more decompressed
`blocks, each of which represent a partial data value of the
`original block. Each of these blocks are compressed using
`the same or different methods for each block to produce one
`or more compressed blocks, which are combined to produce
`an output block. Thus, each block in the original image is
`represented by a plurality, typically different, compressed
`blocks each representing all the data values of the block. In
`one embodiment, color (or a similar value) associated with
`a pixel is determined by combining the compressed infor
`mation about the pixel in one compressed block with com
`pressed information about the same pixel in another com
`pressed block. In another embodiment, global information
`about the image is also combined with the information in
`one or more compressed blocks to produce a desired value
`for a pixel.
`0012. According to one embodiment, decompression of
`the original image is optimized to reduce the loSS. According
`to one embodiment, the optimization is performed by con
`ducting a Series of functions on a first Subset comprising of
`one or more decompressed blocks and applying the results
`to a Second Subset comprising of one or more decompressed
`blocks different from the ones in the first Subset. According
`to one embodiment, these functions are iterated through the
`Subsets until a predetermined value of the image is obtained,
`or Some other factor is Satisfied. According to another
`embodiment, the optimization is performed by projecting an
`original block to a predefined vector and Storing the original
`block's magnitude in a first block, and using a device that
`projects and Subtracts the projection block from of the
`original block and Stores the value in a Second block.
`According to another embodiment, the optimization is per
`formed by conducting a Series of functions on the first and
`Second blockS obtained in the previous embodiment.
`According to another embodiment, the optimization of the
`previous embodiment is iterated in a loop until a desired
`output image is accomplished or Some other factor is met.
`0013 As way of example, two decompressed blocks of
`an original box of pixels in the image are compressed using
`two different methods to produce a first and a Second
`compressed block by encoding each pixel value as an index
`into a color map before combining the two compressed
`blocks to generate an output block. In one embodiment, the
`color map maps pixels to a best fit curve with two endpoints
`in a color Space. In one embodiment the curve is a Straight
`line. In one embodiment, the end points of the best fit curve
`are values to which the mapping can map. In another
`embodiment, the mapping can map to an extrapolated value
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 15 of 23
`
`

`

`US 2004/0228527 A1
`
`Nov. 18, 2004
`
`between two endpoints along the best fit curve. In still
`another embodiment, the mapping can map to a plurality of
`different extrapolated values between two endpoints along
`the best fit curve. In one embodiment, the compressed block
`is comprised of the two endpoints of the best fit curve and
`indeX values for each of the pixels.
`0.014.
`In an example embodiment, the original block is a
`four pixel by four pixel block wherein each pixel value is
`represented by 24bits (e.g., a 24-bit RGB color value). Two,
`16-bit endpoints for a best fit curve are stored. Additionally,
`Sixteen 2-bit indices (one for each pixel in the block) are
`stored. The indices encode which of the two endpoint colors
`or two interpolated values along the curve are the com
`pressed color for each pixel. The endpoints and the indices
`comprise a first compressed block.
`0.015. In another example embodiment, a compressed
`block is created by applying a function to each of the values
`of the original block to obtain new block values. In one
`embodiment, the function combines components of each
`value to reduce the amount of Space needed to encode the
`data. In an example embodiment, 24-bit RGB values are
`combined to create an 8-bit grey Scale value (e.g., (R--G+
`B)/3). In one embodiment, the new block values are com
`pressed by encoding the block as an indeX for mapping onto
`a best fit curve. In one embodiment, two endpoints are
`Stored. In another embodiment, the indices map to either the
`two end points or any of one or more interpolated values
`along the best fit curve. The two stored endpoints and the
`block of indices comprise a Second compressed block.
`0016. In an example embodiment, the original block is a
`four pixel by four pixel block wherein each pixel value is
`represented by 24 bits (e.g., a 24-bit RGB color value). The
`values in the block are converted to 8-bit grey Scale values.
`Two, 8-bit endpoints for a best fit curve are stored. Addi
`tionally, sixteen 3-bit indices (one for each pixel in the
`block) are stored. The indices encode which of the two
`endpoint colors or Six interpolated values along the curve are
`the compressed color for each pixel. The endpoints and the
`indices comprise a third compressed block. Further com
`pressed blockS can be similarly obtained.
`0.017. In one embodiment, the error generated by com
`pression is computed and if the error is greater than a
`threshold value, one or more values in the plurality of
`compressed blocks are altered to reduce the computed error.
`In one embodiment, the color values are encoded as YCrCb.
`In one embodiment, the Y component is encoded in one
`compressed block and CrCb endpoints are used to encode
`another compressed block. In another embodiment, the color
`values are encoded as RGB values. One of the RGB com
`ponents are encoded in one compressed block and endpoints
`in the other two components’ color Spaces are used to
`encode another compressed block.
`0.018. In one embodiment, the function associated with
`the creation of one or more compressed blockS is not a grey
`Scale function. Instead, a vector that represents the axis of
`the function is Stored in the compressed blockS. In one
`embodiment, the vector is of unit length. In another embodi
`ment, the vector is of non-unit length. In one embodiment,
`the vector is a 16-bit axis vector stored in addition to the
`endpoints and indices as part of the one or more compressed
`blocks. In another embodiment, two 8-bit Theta-Phi axis
`components are Stored in addition to the endpoints and
`
`indices as part of the one or more compressed blockS. The
`Theta-Phi axis components represent angle and elevation of
`the axis vector on a hemisphere. In one embodiment, the
`number of bits per indeX is reduced to allow Storage of the
`vector value without increasing the size of a compressed
`block beyond a desired maximum size. In various other
`embodiments, more than one compressed blocks are
`encoded to represent each original block. Specific bit values
`have been for the purpose of example. One of ordinary skill
`in the art will recognize that embodiments of the present
`invention may be practiced with original pixel values of any
`Size, using any color encoding Scheme, and generating one
`or more compressed blockS.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0019. These and other features, aspects and advantages of
`the present invention will become better understood with
`regard to the following description, appended claims and
`accompanying drawings where:
`0020 FIG. 1 is a flow diagram of the process of com
`pressing an image in accordance with one embodiment of
`the present invention.
`0021
`FIG. 2 is a flow diagram of the process of deter
`mining a color for a pixel in accordance with one embodi
`ment of the present invention.
`0022 FIG. 3 is a flow diagram of the process of com
`pressing a pixel block in accordance with one embodiment
`of the present invention.
`0023 FIG. 4 is a flow diagram of the process of com
`pressing a 24-bit per pixel, four pixel by four pixel block in
`accordance with one embodiment of the present invention.
`0024 FIG. 5 is a flow diagram of the process of com
`pressing a pixel block in accordance with one embodiment
`of the present invention.
`0025 FIG. 6 is a flow diagram of the process of com
`pressing a 24-bit per pixel, four pixel by four pixel block in
`accordance with one embodiment of the present invention.
`0026 FIG. 7 is a flow diagram of the process of reducing
`the occurrence of Visual artifacts in accordance with one
`embodiment of the present invention.
`0027 FIG. 8 is a block diagram of a general purpose
`computer.
`0028 FIG. 9 is an optimization method according to one
`embodiment of the present invention.
`0029 FIG. 10 is another optimization method according
`to one embodiment of the present invention.
`0030 FIG. 11 is another optimization method according
`to one embodiment of the present invention.
`0031
`FIG. 12 is another optimization method according
`to one embodiment of the present invention.
`0032 FIG. 13 is another optimization method according
`to one embodiment of the present invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`0033. The invention is a method and apparatus for block
`based image compression with multiple non-uniform block
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 16 of 23
`
`

`

`US 2004/0228527 A1
`
`Nov. 18, 2004
`
`encodings. In the following description, numerous specific
`details are Set forth to provide a more thorough description
`of embodiments of the invention. It is apparent, however, to
`one skilled in the art, that the invention may be practiced
`without these specific details. In other instances, well known
`features have not been described in detail So as not to
`obscure the invention.
`0034) Multiple Blocks
`0.035 Embodiments of the present invention are directed
`to a method and apparatus for block based image compres
`Sion with multiple non-uniform block encodings. In one
`embodiment of the present invention, an image is divided
`into blocks of pixels. In one embodiment the blocks are four
`pixels by four pixels, but other block sizes are used in other
`embodiments.
`0036). In one embodiment, a block of pixels in the original
`image is decompressed into one or more decompressed
`blocks, each of which represent a partial data value of the
`original block. According to one embodiment, the decom
`pression is based on applying a predefined transform func
`tion to each block. According to another embodiment, the
`decompression is optimized to reduce the loSS of image
`quality. Each of these decompressed blocks are then com
`pressed using the same or different methods for each block
`to produce one or more compressed blocks, which are
`combined to produce an output block. Thus, each block in
`the original image is represented by a plurality, typically
`different, compressed blocks each representing all the data
`values of the block. In one embodiment, color (or a similar
`value) associated with a pixel is determined by combining
`the compressed information about the pixel in one com
`pressed block with compressed information about the same
`pixel in another compressed block. In another embodiment,
`global information about the image is also combined with
`the information in one or more compressed blocks to pro
`duce a desired value for a pixel.
`0037 FIG. 1 illustrates the process of compressing an
`image in accordance with one embodiment of the present
`invention. At block 100, an image is divided into a plurality
`of blocks. At block 110, each block is decompressed into a
`plurality of decompressed blocks. At step 120, each of these
`decompressed blockS is compressed to form a plurality of
`compressed blocks. At step 130, the plurality of compressed
`blocks are combined to generate an output block.
`0.038
`Optimization of Decompressed Image Block
`0.039 According to one embodiment, the decompression
`of each original block of the image is optimized So that the
`loSS in image quality is reduced to a desired amount, or
`meets Some threshold. According to another embodiment of
`the present invention, there are Several levels of optimization
`available depending on the threshold or other factorS Such as
`time constraints, quality of output image, etc. It should be
`noted here, that the optimization methods mentioned below
`take into account only a limited amount of blocks (2 in these
`cases), but an unlimited amount of blocks can be used
`without departing from the Scope of the present invention.
`0040. A first optimization method uses a first Subset
`comprising of one or more decompressed blocks and a
`Second Subset comprising of one or more decompressed
`blocks different from the ones in the first Subset. This
`optimization method is illustrated in FIG. 9. At block 900,
`
`the first Subset is compressed. Compression Schemes are
`explained in more detail below. Next, at block 910, the
`compressed first Subset is decompressed. Next, at block 920,
`the results of the decompression are fed to a decompress
`device that changes the data value of the Second Subset.
`Next, at bock 930, the second subset is compressed. Blocks
`900 through 930 are repeated for every subset of an image
`until the entire image is compressed.
`0041) A second optimization method uses the first opti
`mization method in addition to a final iteration Step. This
`optimization method is illustrated in FIG. 10. Blocks 900
`through 930 remain the same and are numbered 1000
`through 1030. Next, at block 1060, if the optimization has
`met a certain threshold or Some other factor, then we stop,
`else at block 1040 the compressed second subset is decom
`pressed. Next, at block 1050, the results of the decompres
`Sion are fed to a decompress device that changes the data
`value of the first Subset, and blocks 1000, 1010, 1020, 1030,
`and 1060 are repeated again.
`0042. A third optimization method uses an original image
`block in conjunction with a Series of functions to generate
`two new blocks. This optimization method is illustrated in
`FIG. 11. At block 1100, an original image block is projected
`onto a predefined vector, and at block 1110 its magnitude is
`Stored in a first new block by a decompress device. Con
`currently, at block 1120, the projected image is Subtracted
`from the original image and the result is Stored in a Second
`new block.
`0043. A fourth optimization method uses an original
`image block in conjunction with a Series of functions to
`generate two new blocks. This optimization method is
`illustrated in FIG. 12. At block 1200, an original image
`block is projected onto a predefined vector, and at 1210 its
`magnitude is Stored in a first new block by a decompress
`device. Next, at block 1220, the first new block is com
`pressed using any of the compression Schemes described
`below to generate a compressed first block. Next, at block
`1230, the compressed first block is decompressed. Next, at
`block 1240, the data value of the decompressed block is
`subtracted from the data value of the original block to
`generate a new second block. Next, at block 1250, new
`Second block is compressed to generate a compressed Sec
`ond block. Next, at block 1260, compressed first block and
`compressed Second block are combined to generate an
`output block at block 1270.
`0044) A fifth optimization method uses an original image
`block in conjunction with a Series of functions to generate
`two new blocks. This optimization method is illustrated in
`FIG. 13. At block 1300, an original image block is projected
`onto a predefined vector, and at 1310 its magnitude is stored
`in a first new block by a decompress device. Next, at block
`1320, the first new block is compressed using any of the
`compression Schemes described below to generate a com
`pressed first block. Next, at block 1330, the compressed first
`block is decompressed. Next, at block 1340, the data value
`of the decompressed block is subtracted from the data value
`of the original block to generate a new Second block. Next,
`at block 1350, new second block is compressed to generate
`a compressed second block. Next, at block 1360, com
`pressed Second block is decompressed and its data value
`subtracted from the data value of the original block and the
`results are stored in a third new block. Next, at block 1370,
`
`Realtek Ex. 1016
`Case No. IPR2023-00688
`Page 17 of 23
`
`

`

`US 2004/0228527 A1
`
`Nov. 18, 2004
`
`the data value of the third new block is Subtracted from the
`data value of the original block and the result is Stored back
`in the first new block. At block 1380, if the desired threshold
`is met, then the compressed first block is combined with the
`compressed Second block to generate an output block at
`block 1390, else blocks 1310-1370 are repeated again.
`0045 One Compression Method
`0.046
`FIG. 2 illustrates the process of determining a
`color for a pixel in accordance with one embodiment of the
`present invention. At block 200, a first value associated with
`a pixel is decoded from a first compressed block. At block
`210, a Second value associated with the Same pixel is
`decoded from a second compressed block. At block 220, the
`first and Second values are combined to generate an output
`pixel. In one embodiment, the values are combined by
`averaging. In another embodiment, the values are combined
`by appending one to the end of another. In other embodi
`ments, other combining functions are used. It should be
`noted here that there can be more than two compressed
`blocks each containing a different value associated with the
`Same pixel, but the general idea of combining the values of
`each compressed block to generate an output pixel remains
`the same as explained above.
`0047 Another Compression Method
`0.048. In one embodiment, a first compressed block is
`created by encoding each pixel value as an indeX into a color
`map. In one embodiment, the color map maps pixels to a
`best fit curve with two end points in a color space. In one
`embodiment the curve is a Straight line. In one embodiment,
`the end points of the best fit curve are values to which the
`mapping can map. In another embodiment, the mapping can
`map to an extrapolated value between two endpoints along
`the best fit curve. In Still another embodiment, the mapping
`can map to a plurality of different extrapolated values
`between two endpoints along the best fit curve. In one
`embodiment, the compressed block is comprised of two
`points of the best fit curve and index values for each of the
`pixels. In another embodiment, the two points are the two
`endpoints.
`0049 FIG. 3 illustrates the process of compressing a
`decompressed block in accordance with one embodiment of
`the present invention. At block 300, a best fit curve with
`endpoints of a pre-determined size is determined. At block
`310, the endpoints are Stored as part of a compressed block.
`At block 320, each pixel in the decompressed block is
`encoded as an indeX into a group of possible color values. In
`one embodiment, the possible color values are comprised of
`the Stored endpoints. In another embodiment, the possible
`color values are comprised of the Stored endpoints and one
`or more interpolated values on the best fit curve. At block
`330, the indices are stored as part of the compressed block.
`0050. In an example embodiment, the original block is a
`four pixel by four pixel block wherein each pixel value is
`represented by 24bits (e.g., a 24-bit RGB color value). Two,
`16-bit endpoints for a best fit curve are stored. Additionally,
`Sixteen 2-bit indices (o