United States Patent [19J
`Iourcha et al.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US005956431A
`[11] Patent Number:
`(451 Date of Patent:
`
`5,956,431
`Sep.21,1999
`
`(54] SYSTEM AND METHOD FOR FIXED-RATE
`BLOCK-BASED IMAGE COMPRESSION
`WITH INFERRE D PfXEL VALUES
`
`Primary Examiner-Edward L. Coles
`Assistant Examiner- Jimmy Nguyen
`Auorney, Agent, or Firm-Fenwick & West LLP
`
`[75]
`
`inventors: Konstantine I . l ourcha, San Jose;
`Krishna S. Nayak. Stanford: Zhou
`Hong, San Jose, all of Calif.
`
`[73] Assignee: S3 Incorporated, Santa Clara, Calif.
`
`(21] Appl. No.: 08/942,860
`
`[22]
`
`Oct. 2, 1997
`
`filed:
`lnt. C l.6
`[51]
`•.•..........•.••.•...... ......•... ......••••... ......• G06K 9/36
`(52] U.S. Cl ........................... 382/253; 382/166; 382/232;
`382/233
`[58] Field of Search ..................................... 382/253. 166,
`382/233, 232, 236, 238, 239; 358/539,
`425.426, 427,430
`
`(56]
`
`References C ited
`
`U.S. PATENT DOCUMENTS
`
`3/ !998 Wittenstein et al .................... 382/ 166
`5.734,744
`5,822,465 10/ 1998 Normile et al. ........................ 382/253
`
`OTHER PUBLICATIONS
`
`A. Schilling, et aL; "Texram: A Smart Memory for Textur(cid:173)
`ing"; IEEE Computer Graphics & Applications; May 1996:
`16(3) pp. 9- 19.
`G. Kniuel, ct al.; "Hardware and Software for Superior
`Texture Performance"; fn 10; £urographies Hardware Work(cid:173)
`shop '95; Maastricht, NL; Aug. 28-29, 1995; pp. 1-8.
`G. Campbell, et a!.; "Two Bit/Pixel Full Color Encoding":
`Computer Graphics, (Proc. Siggraph '86); Aug. 18-22,
`1986; vol. 20, No. 4, Dallas TX: pp. 215- 219.
`
`[57]
`
`ABSTRACT
`
`An image processing system includes an image encoder
`system and a image decoder system that are coupled
`together. The image encoder system includes a block decom(cid:173)
`poser and a block encoder that are coupled together. The
`block encoder inchrdes a color quantizer and a bitmap
`construction modu lc. Tbc block decomposer breaks an origi(cid:173)
`nal image into blocks. Each block is then processed by the
`block encoder. Specifically, the color quantizer selects some
`ntunber of base points, or codcwords, that serve as reference
`pi:xel values. such as colors, from which quantized pixel
`values arc derived. The bitmap construction module tbco
`maps each pixel colors to one of the derived quantized
`colors. The codewords and bilmap are output as encoded
`image blocks. 'Jbe decoder system includes a block decoder.
`The block decoder includes a block type detector, one or
`more decoder units, and an output selector. Using the
`codewords of the encoded data blocks, the comparator and
`the decoder units determine the quantized colors for tbe
`encoded image block and map each pixel to one of the
`quantized colors.1oe output selector outputs the appropriate
`color, which is ordered in an image composer with the other
`decoded blocks to output ao image representative of tbe
`original image. A method for encoding an original image and
`for decoding the encoded image to generate a representation
`of the original image is also disclosed.
`
`22 Claims, 16 Drawing Sbcets
`
`310
`
`~315
`
`~318
`
`HEADER
`CONVERTER
`
`.....r- 321
`
`IMAGE
`t
`IMAGE
`DECOMPOSER
`~
`BLOCK
`ENCODER
`+
`ENCODED IMAGE ~319
`COMPOSER
`~
`OUTPUT
`
`320
`
`220
`
`0001
`
`Volkswagen 1006
`
`

`
`U.S. Patent
`
`Sep.21,1999
`
`Sheet 1 of 16
`
`5,956,431
`
`PROCESSING w
`
`145
`
`UNIT
`110
`
`MEMORY
`115
`
`STORAGE
`DEVICE
`120
`
`GRAPHICS
`SUBSYSTEM
`135
`
`OUTPUT
`DEVICE
`130
`
`INPUT DEVICE
`125
`
`FIG. 1
`
`0002
`
`

`
`U.S. Patent
`
`Sep. 21,1999
`
`Sheet 2 of 16
`
`5,956,431
`
`IMAGE
`SOURCE
`210
`I ...
`IMAGE
`ENCODER
`220
`I •
`
`MEMORY 11 5/
`STORAGE DEVICE
`120
`
`t •
`
`IMAGE
`DECODER
`230
`I
`+
`OUTPUT
`240
`
`FIG. 2A
`
`4----- -W- ---+
`
`v
`
`H
`
`270
`
`260
`
`FIG. 28
`
`0003
`
`

`
`U.S. Patent
`
`Sep.21,1999
`
`Sheet 3 of 16
`
`5,956,431
`
`IMAGE
`t
`IMAGE
`DECOMPOSER
`l
`BLOCK
`ENCODER
`t
`ENCODED IMAGE
`COMPOSER
`t
`OUTPUT
`
`310
`
`_r-315
`
`___,.-- 318
`
`~,-r-319
`
`320
`
`HEADER
`CONVERTER
`
`__r- 321
`
`220 FIG. 3A
`
`318n l
`
`•••
`"-r"""
`
`T
`
`IMAGE
`t
`IMAGE
`DECOMPOSER
`t •••
`I
`BLOC)
`,...,
`BLOCK
`ENCODER
`
`,....
`
`310
`
`_r-315
`
`I
`
`v-- 318a
`
`1 1
`ENCODED IMAGE v--319
`COMPOSER
`t
`OUTPUT
`
`320
`
`HEADER
`CONVERTER
`
`v
`
`321
`
`220 FIG. 38
`
`0004
`
`

`
`U.S. Patent
`
`Sep.21,1999
`
`Sheet 4 of 16
`
`5,956,431
`
`i- ·- ·- ·- ·- ·- ·- - ·- ·- ·- ·- ·- ·- ·- - ·- ·- ·- ·-·-· - ·- ·- ·- ·- ·- ·- ·- ·- ·
`
`COLOR
`QUANTIZER
`335
`
`BLOCK TYPE
`MODULE
`345
`
`CURVE SELECTION
`MODULE 355
`
`BITMAP
`.__.. CONSTRUCTION
`MODULE 340
`
`CODEWORD
`GENERATION
`MODULE 360
`
`I
`I
`I
`I
`I
`
`I
`I
`
`I
`I
`I
`
`I
`I
`I
`I
`
`I
`I
`I
`I
`
`I
`I
`
`I
`I
`I
`I
`
`I
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`I
`
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`FIG. 3C
`
`0005
`
`

`
`U.S. Patent
`
`Sep. 21,1999
`
`Sheet 5 of 16
`
`5,956,431
`
`( 380a
`
`{JBOb
`
`OR/G.
`HEADER
`
`IMAGE DATA
`
`FIG. 3D
`
`380
`
`385a
`
`~+-14 - - 390-1 - 390-R
`
`(
`
`MOD.
`HEADER
`
`390
`
`FIG. 3E
`
`•••
`
`385
`
`r--390a1,J ____.,.,~~ 4-- 390b1-Q
`I r I 1
`BITMAP
`
`cw0 ••• c~-1
`
`• • •
`
`390
`
`FIG. 3F
`
`0006
`
`

`
`U.S. Patent
`
`Sep.21,1999
`
`Sheet 6 of 16
`
`5,956,431
`
`START
`
`418
`
`420
`
`SELECT
`CODEWORDS
`
`422
`
`QUANTIZE
`COLORS FOR
`IMAGE BLOCK
`
`RESULT
`
`424
`
`FIG. 48
`
`START
`
`402
`
`INPUT IMAGE
`
`DECOMPOSE
`IMAGE INTO
`BLOCKS
`
`408
`
`CONVERT
`HEADER
`INFO
`
`ENCODE
`EACH BLOCK
`
`404
`
`406
`
`410
`
`COMPOSE
`HEADER AND
`l...----+1 ENCODED
`BLOCKS
`
`412
`
`414
`
`WRITE
`HEADER AND
`ENCODED
`BLOCKS
`
`RESULT
`
`416
`
`FIG. 4A
`
`0007
`
`

`
`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 7 of 16
`
`5,956,431
`
`~------------------------~
`
`438
`
`STORE ERROR
`
`440
`
`STORE BLOCK
`TYPE AND
`CODEWORDS
`
`NO
`
`YES
`
`YES
`
`446
`
`OUTPUT
`BLOCK TYPE &
`CODEWORDS
`PRODUCING
`MIN ERROR
`
`447
`
`RESULT
`
`START
`
`426
`
`428
`
`SELECT
`BLOCK TYPE
`
`432
`
`SELECT
`PARTITION
`
`434
`, --
`- - - -L - - - - ,
`COMPUTE
`OPTIMAL
`CODEWORDS
`FOR
`PARTITION
`
`436
`
`COMPUTE
`ERROR
`
`FIG. 4C
`
`0008
`
`

`
`U.S. Patent
`
`Sep. 21,1999
`
`Sheet 8 of 16
`
`5,956,431
`
`START
`
`448
`
`START
`
`456
`
`450
`
`COMPUTE
`GRAVITY
`CENTER
`
`452
`
`IDENTIFY
`VECTOR IN
`COLORS PACE
`TO MINIMIZE
`FIRST
`MOMENT
`
`RESULT
`
`454
`
`458
`
`PROJECT
`COLORS ONTO
`CURVE
`
`460
`
`ORDER
`COLORS
`ALONG
`ANALOG
`CURVE
`
`r
`
`SEARCH FOR
`OPTIMAL
`PARTITION
`
`462
`
`••
`END
`
`464
`
`FIG. 4D
`
`FIG. 4E
`
`0009
`
`

`
`U.S. Patent
`
`Sep.21,1999
`
`Sheet 9 of 16
`
`5,956,431
`
`ENCODED IMAGE
`DATA 385 FROM
`OUTPUT 320
`
`ENCODED IMAGE
`DECOMPOSER
`501
`
`HEADER
`CONVERTER
`508
`
`BLC
`505m E
`
`I
`
`BLOCK DECODER
`505a
`
`L------+~ IMAGE COMPOSER ~~.. OUTPUT 240
`504
`
`FIG. 5A
`
`0010
`
`

`
`U.S. Patent
`
`Sep.21, 1999
`
`Sheet 10 of 16
`
`5,956,431
`
`BLOCK TYPE
`DETECTOR
`520
`
`FIRST
`DECODER
`UNIT
`533a-1
`
`SECOND
`DECODER
`UNIT
`533a-2
`
`• • •
`
`kth
`DECODER
`UNIT
`533a-k
`
`-
`
`OUTPUT SELECTOR
`523
`~--------~
`
`FIG. 58
`
`0011
`
`

`
`U.S. Patent
`
`Sep.21, 1999
`
`Sheet 11 of 16
`
`5,956,431
`
`BLOCK TYPE
`DETECTOR
`520
`
`FIRST
`DECODER
`UNIT
`(4-COLOR)
`530
`
`SECOND
`DECODER UNIT
`(3-COLOR +
`TRANSPARENCY)
`540
`
`OUTPUT SELECTOR
`523
`1+------.......J
`
`FIG. 5C
`
`0012
`
`

`
`U.S. Patent
`
`Sep.21,1999
`
`Sheet 12 of 16
`
`5,956,431
`
`390~ ~--------~
`codeword
`0{16}
`codeword
`1(16}
`ID
`ID
`ID
`ID
`(2) (2) (2) (2)
`ID
`ID
`ID
`ID
`(2) (2) (2) (2)~
`ID
`ID
`ID
`ID
`(2) (2) (2) (2)
`ID
`ID
`ID
`ID
`(2} (2) (2) (2)
`546 .J
`
`551bl
`
`R{or G, 8}
`channel of color 1
`
`-. color 1 R
`
`{or G, B)
`1
`
`550b....J
`
`..--
`
`544 ,
`5461
`
`\
`
`551o '-
`
`R{or C, B)
`channel of color 0
`
`•
`color 0 R
`550oJ {or G, B)
`I
`I
`
`552o
`
`1
`
`...---
`
`I
`full odder
`+
`~ 554o
`full adder ~
`+
`
`r
`
`•
`
`CLA adder v-556o
`+
`
`t
`
`t
`
`525b
`
`525a
`
`_,f;,ID-
`526
`
`FIG. 50
`
`1
`'\
`
`4X1 MUX
`I
`texel color
`R{or G,B) channel
`t
`
`0013
`
`I
`I
`color 0
`552b, ~ {16}
`1 522) 1
`full odder
`+
`comparator
`1 554b
`> {16 bits)
`full adder ~
`+
`•
`
`520
`
`j
`
`colo r 1
`)
`{16
`
`558( 1
`
`r
`
`CLA adder (r556b
`+
`I
`
`adder
`+
`I
`" \ 2X1 MUX J_
`~
`/
`2X1 MUX A
`!
`•
`
`

`
`U.S. Patent
`
`Sep.21, 1999
`
`Sheet 13 of 16
`
`5,956,431
`
`START
`
`600
`
`605
`
`610
`
`615
`
`RECEIVE
`ENCODED
`IMAGE DATA
`
`DECOMPOSE
`ENCODED
`IMAGE DATA
`
`DECODE
`IMAGE
`BLOCKS
`
`COMPOSE
`HEADER AND
`DECODED
`BLOCKS
`
`620
`
`~
`
`612
`
`CONVERT
`HEADER
`INFORMATION
`
`OUTPUT
`
`625
`
`FIG. 6A
`
`0014
`
`

`
`U.S. Patent
`
`Sep.21,1999
`
`Sheet 14 of 16
`
`5,956,431
`
`START
`
`630
`
`635
`
`RECEIVE
`ENCODED
`IMAGE BLOCK
`
`640
`
`DETECT
`BLOCK TYPE
`
`645
`
`SELECT
`DECODER
`UNIT
`
`650
`CALCULATE
`QUANTIZED
`COLOR
`LEVELS
`
`655
`
`READ BITMAP
`VALUE FOR
`EACH PIXEL
`
`660
`MAP EACH
`PIXEL TO
`CALCULATED
`COLOR
`
`665
`
`RESULT
`
`FIG. 68
`
`0015
`
`

`
`U.S. Patent
`
`Sep. 21, 1999
`
`Sheet 15 of 16
`
`5,956,431
`
`
`OED ENCO
`DATA
`IMAGE
`ORTION
`BLOCK P
`
`38 5b
`
`ENCODED IMAGE
`DATA
`385
`
`HEADER INFO
`385a
`i
`BLOCK ADDRESS
`COMPUTATION
`MODULE
`710
`
`~
`
`..
`
`"
`
`BLOCK FETCHING
`MODULE
`720
`
`BLOCK DECODER
`505
`
`FIG. 7A
`
`0016
`
`700
`
`

`
`U.S. Patent
`
`Sep.21,1999
`
`Sheet 16 of 16
`
`5,956,431
`
`START
`
`COMPUTE
`ENCODED
`BLOCK
`ADDRESS
`
`,
`
`FETCH
`ENCODED
`BLOCK
`
`COMPUTE
`QUANTIZED
`COLOR
`LEVELS
`
`SELECT
`COLOR OF
`PIXEL
`
`OUTPUT
`
`740
`
`745
`
`750
`
`755
`
`760
`
`765
`
`0017
`
`FIG. 78
`
`

`
`5,956,431
`
`1
`SYSTEM AND METHOD FOR FlXI<:D-RATE
`BLOCK-BASED IMAGE COMPRESSION
`WITH INFERRED PIXEL VALUES
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invemion relates to image processing
`systems. and more specifically, to three-dimensional render(cid:173)
`ing systems using fixed-ra te image compression for textures.
`2. Description of the Related Art
`The art of generating images, such as realistic or animated
`graphics on a computer is known. To generate such images
`requires tremendous memory bandwidth and processing
`power on a graphics subsystem. To reduce Lbe bandwidth
`and proces.sing power requirements. various compression
`methods and systems were developed. These methods and
`systems included Entropy or lossless encoders, discrete
`cosine transform or JPEG type compressors, block tru.nca(cid:173)
`tion coding, color cell compression, and o thers. Each of
`these methods and systems. however, have numerous draw(cid:173)
`backs.
`EDltropy or lossless encoders include Lempel-Ziv encod(cid:173)
`ers and arc used for many different purposes. Entropy coding
`relies on predictability. For data con1pression using Enlropy 2.s
`encoders, a few bits are used to encode the most commonly
`occurring symbols. In stationary systems where the prob(cid:173)
`abilities are fixed, Entropy coding provides a lower bound
`for the compression than can be achieved with a given
`alphabet of symbols. A problem with Entropy coding is that 30
`it does not allow random access to any given symbol. The
`part of the c.ompres.sed data preceding a symbol of interest
`must be first fetched and decompressed to decode the
`symbol which takes considerable processing time and
`resolllrces as well as decreasing memory throughput. 35
`Another problem with existing Entropy methods and sys(cid:173)
`tem:::. is that they do not provide any guaranteed compression
`factor which makes this type of encoding scheme imprac(cid:173)
`tical where the memory size is lixed.
`Discrete Cosine Transform ("DCT'') or JPEG-type
`compressors, allow users to select a level of image quality.
`With DCI~ uocorrclated coefficients are produced w that
`each coefficient can be treated independently without loss of
`compression efficiency. 1l1e DCT coefficients can be quan- 45
`tized using visually-weighted quantization values which
`selectively discard the least important information.
`DCT, however, suffers from a number of shortcomings.
`One p roblem with DCT and JPEG-type compressors is that
`they require usually bigger blocks of pixels, typically 8x8 or so
`16xL6 pixels, as a minimally accessible unit in order to
`obtain a reasonable compression factor and quality. Access
`to a very small area, or even a single pixel involves fetching
`a large quantity of compressed data, thus requiring increased
`proces.<;Or power and memory bandwidth. A second problem 55
`with DCT and JPEG-type compressors is that the compres(cid:173)
`sion factor is variable, therefore requiring a complicated
`memory management system that, in turn, requires greater
`processor resources. A third problem with DCT and JPEG(cid:173)
`type compression is that using a large compression factor 60
`significantly degrades image quality. For example, the image
`may be considerably distorted with a form of a ringing
`around the edges in the image as well as noticeable color
`shifts in areas of tbe image. Neither artifact can be remove<.!
`with subsequent low-pass filtering.
`A fourth problem with DCT and JPEG-type compression
`is that such a decompressor is complex and bas a significant
`
`2
`associated hardware cost. Further, the high latency of the
`decompressor results in a large additional hardware cost for
`buffering throughout the system to compensate for the
`latency. Finally, a A fifth problem with DCf and JPEG-type
`s compressors is that it is not clear whether a color keyed
`image can be compressed with such a method and system.
`Block truncation coding (··BTC") and color cell compres(cid:173)
`sion ("CCC") use a local one-bit quantizcr on 4x4 pixel
`blocks. Tbe compressed data for sucb a block consists of
`10 only two colors and 16-bits tbat indicate which one of the
`two colors is assigned to each of the 16 pixels. Decoding a
`BTC/CCC image consists of using a multiplexer with a
`look-up table so that once a 16-texel-block (32-bits) is
`retrieved from memory, the individual pixels are decoded by
`15 looking up the two pos.<>ible colors for that block and
`selecting the color according to 1 be associated bit from the
`16 decision bits.
`The BTC/CCC methods quantize each block to just two
`color levels resulting in significant image degradation.
`zo Furtber, a two-bit variation of CCC stores the two colors as
`eight-b'il indices into a 256-entry color lookup table. Thus,
`such pixel blocks cannot be decoded without fetching addi(cid:173)
`tional information that can consume additiona l memory
`bandwidth.
`The BTC!CCC methods and systems can use a three-bit
`per pixel scheme which store tbe two colors as 16-bit values
`(not indices into a table) resulting in pixel blocks of six
`bytes. Fetching such units, however. decreases sy:::.tem per(cid:173)
`formance because of addi6onal overhead due to memory
`misalignment. Another problem with BTC/CCC is that when
`it is used to compress images that use color keying to
`indicate transparent pixels, there will be a high degradation
`of image quality.
`1berefore, there ~'> a need for a method and system rbat
`ma>..imizes the accuracy of compressed images while mini(cid:173)
`mizing storage, memory bandwidth requirements, and
`decoding hardware complexities. wbile also compressing
`image data blocks into convenient sizes to maintain align(cid:173)
`ment for random access to any one or more pixels.
`
`40
`
`SUMMARY OF THE INVENTION
`
`An image processing system includes an image encoder
`or compression system and an image decoder or decompres(cid:173)
`sion system that arc coupled together. 1l1e image encoder
`system receives an original image from a source and
`encodes tbe original image into a compressed form tbat is
`reduced in size and that represents the original image with
`minimal loss of image quality. 1l1e image decoder system
`decodes the encoded image to generate an output represent(cid:173)
`ing the original image.
`The image encoder system includes an image decomposer
`that is coupled to one or more block encoders. T he one or
`more block encoders are, in turn, coupled to an encoded
`image composer. The encoded image composer is coupled to
`an output. In addition, the image decomposer and the
`encoded image composer are coupled to a header converter.
`The output of the encoded image composer may be coupled
`with a storage device, a memory, or a data transmission line,
`for example.
`The image decomposer breaks the original image into its
`header and some number of image blocks. The header is
`forwarded to tbe header co.nverter wbich modifies the header
`and forwards it to the encoded image composer. Each image
`65 block has a fixed size, e.g., four-by-four pixels, and is
`forwarded to the one or more block encoders. The block
`encoders convert the image block into a compressed or
`
`0018
`
`

`
`5,956,431
`
`4
`block type detector is coupled witb each decoder unit and the
`output selector. In addition, each decoder unit is coupled
`with the output selector. The block type detector determines
`which decoder unit is selected to decode the encoded block.
`In a p referred embodiment, the block type is determined
`through an arithmetic comparison of the encoded block's
`codewords.
`Based on the selected decoder, the qua ntized colors arc
`inferred from the codewords for the encoded block. An
`index value (ID value) for each pixel in the block is read
`from the bitmap data string to map each pixel to the
`appropriate quantized color. The colors for each pixel in the
`block are output to the output selector. The output selector
`sends the appropriate decoded block to the image composer
`for ordering to generate tbe final image at the output.
`1nc present invention also provides for decoding only
`portions of the encoded image by allowing for random
`access to portions of the image. Thus, the presem invemion
`advantageously can decode an encoded image in a particular
`order and portion. For example, in a three-dimensional
`graphics environments, the present invention can select parts
`of the encoded image used for texture maps.
`The features and advantages described in the specilication
`are not all inclusive and, in particular, many additional
`features and advantages will be apparent to one of ordinary
`skill in the art in view of lbe drawings, specification, and
`claims. Moreover, it should be noted I bat the lang11age used
`in the speci.fication has been principaiJy selected for read(cid:173)
`ability and instructional purposes, and may not have been
`selected to delineate or circumscribe the inventive subject
`matter.
`
`5
`
`3
`encoded block form, wbi.cb is also of a fixed size. The
`encoded image composer orders the encoded image blocks
`and concatenates them wilb the modified header to produce
`an 01Utput that is an encoded image data representing the
`original image.
`Each block encoder includes a color quantizer and a
`bitmap construction module that are coupled together.
`Further, the color quantizcr includes a block type module, a
`curve selection mod we, and a codeword generation module.
`The block type module is coupled to the curve selection 10
`module and the curve selection module is coupled to the
`codeword generation module.
`In a preferred embodiment, the block type module iden(cid:173)
`tilies which one of two color sets, which comprise eilber
`four quantized pixel values (e.g., colors) or three quantized 15
`pixel values (e.g., colors) and a transparency, is to be used
`for tble encoding of each data block received from the block
`decomposer. TI1e curve selection module and the codeword
`generation module function to select two base colors, or
`codewords, that may be used to identify the color set to zo
`which each pixel in the image block is mapped.
`In a preferred embodiment, the set of colors are equidis(cid:173)
`ta nt along a line in a color space. In addition, the two
`endpoint quan tized colors are used as the codewords
`tben1selves, and the remaining one or Lwo quantized colors 2.s
`are inferred or interpolated. If one quantized color is
`inferred. the fourth reference may be a transparency.
`Once the codcwords and quantized colors arc identified,
`the bitmap construction module constructs a bitmap value 30
`for each pixel in the block. Each pixel's bitmap vaJue is an
`index (identified as an ID value) indicating which of the
`quantized colors best matches the pixel. The bitmap con(cid:173)
`struction module outputs the bitmap and the codewords as a
`single encoded image block. lo a preferred embodinlent, 35
`each bitmap value is two-bits, comprising a bitmap of
`32-b:ils, which along with two 16-bit codewords form a
`64-b.it encoded image block.
`Each of the encoded image data blocks from a block
`encoder is then ordered in the encoded image composer 10 40
`generate a data file of the encoded image blocks. The data
`file of the encoded image blocks is concatenated with the
`header information from the origina l image data to generate
`the encoded or compressed image data. The encode image
`data may then be decoded or decompressed in the image 45
`dt:coder system.
`The image decoder system includes an encoded inlage
`decomposer, a header converter. one or more block
`decoders, and an image composer. "Ibe encoded image
`decomposer is coupled to the header converter and the one so
`or more block decoders. The image composer is coupled to
`the one or more block decoders and the header converter.
`Ibe image composer i<; coupled to output an image repre(cid:173)
`senting the original image.
`The encoded image data is received by the encoded image ss
`decomposer that decomposes, or breaks. the encoded image
`data into its header and its encoded image blocks. The
`header is forwarded 10 the header converter which modifies
`the header and forwards it to the image composer. The one
`or more encoded image blocks are independently decoded 60
`by ooe or more block decoders. The image composer orders
`the decoded image blocks into a data file of decoded image
`blocks. The data file is concatenated with the header from
`the header convener and the ..:ntire lilt: is output as an inlage
`representing the original image.
`Each block decoder includes a block type detector, a
`decoder unit for each block type, and an output selector. The
`
`BRIEF DESCRIPTION OF TIIE DRAWINGS
`PIG. 1 is a block diagram of a data processing system in
`accordance with the present invention;
`FIG. 2Ais a block diagram of an inlage processing system
`in accordance with the present invention;
`PIG. 2B is a graphical representation of an image block in
`accordance with the present invention;
`FIG. 3A is a block diagram of a first cmbocliment an
`image encoder system in accordance wilb lbe present inven(cid:173)
`tion;
`FIG. 3B is a block diagram of a second cmbodinlcnt of an
`image encoder system in accordance with the present inven(cid:173)
`tion;
`FIG. 3C is a block diagram of an image block encoder in
`accordance with the present invention;
`FIG. 3D is a data sequence diagram of <ln original image
`in accordance with the present invention;
`FIG. 3E is a data sequence diagram of encoded image data
`of the original image output from the image encoder system
`in accordance with the present invention;
`FIG. 3F is a data sequence diagram of an encoded image
`block from the inlagc block encoder in accordance with the
`present invention;
`FIGS. 4A-4E are flow diagrams iiJustrating an encoding
`process in accordance with the present invention;
`FIG. SA is a block diagram of an image decoder system
`iu accordance with the present invention;
`FIG. SB is a block diagram of a first embodiment of a
`block decoder in accordance with lbe present invention;
`FIG. SC is a block diagram of a second embodiment o f a
`65 block decoder in accordance with the present invention;
`FIG. SD is a logic diagram iiJustrating a first embodiment
`of a decoder unit in accordance with the present invention:
`
`0019
`
`

`
`5,956,431
`
`5
`FIGS. 6A-6B arc flow diagrams illustrating a decoding
`process in accordance with the present invention;
`FIG. 7A is a block diagram of a subsystem for random
`access to a pixel or an image block in accordance with the
`present invention; and
`FIG. 7B is a flow diagram illustrating random access to a
`pi:~:el or an image block in accordance with the present
`invention.
`
`30
`
`DETAILED DESCRIPTION OF 11 IE
`PREFERRED EMBODIMENTS
`FIG. l is a block diagram of a data processing system 105
`constructed in accordance with the present invention. The
`data processing system 10S includes a processing unit 110,
`a memory US. a storage device UO, an input device US. an
`output device 130, and a graphics subsystem l3S. In
`addition, the data processing system 10S includes a data bus
`14S that couples each of the other components 110, 115, 120,
`US, 130, 135 of the data processing system 105.
`1bt: data bus 14S is a conventional data bus and while
`shown as a single line it may be a combination of a processor
`bus. a PCT btL<:>, a graphical bws, and an TSA bus. The
`processing unit 110 is a conventional processing unit such as
`the note! Pentium processor, Suo SPARC processor, or
`Motorola PowerPC proces.sor, for example. TI1e processing
`unit 110 processes data within the data proc~::ssing system
`10S. The memory llS, the storage device UO, tbe input
`device 12S, and the output device 130 arc also conventional
`components as recognized by those skilled in the art. The
`memory US and storage device UO s tore data within the
`data processing system 10S. 1be input device 12S inputs
`data into the system while the output device 130 receives
`data from the data processing system LOS.
`FIG . 2A is a block diagram of an image proces.sing system
`20S constructed in accordance with tbe present invention. Tn
`one embodiment, the image processing system 205 runs
`within the data processing system 10S. The image process(cid:173)
`ing system 20S includes an image encoder system 220 and
`an image decoder system 230. The image processing system 40
`20S may also include a unit for producing an image source
`210 from w hich images are received, and an output240 to
`which processed images are forwarded for storage or further
`processing. The ·image encoder system 220 is coupled to
`receive an image from the image sotLrcc 210. The image 45
`decoder system 230 is coupled to output the image produce<l
`by tbe image processing system 20S. The image encoder
`system 220 is coupled to the image decoder system 230
`throu.gh a data line and may be coupled via a storage device
`120 and/or a memory llS, for example.
`Within the image encoder system 220, the image is broken
`down into individual blocks and processed before being
`forwarded to, e.g., the storage device 140, as compressed or
`encoded image data. When the encoded image data is ready
`for further data processing, the encoded image data is ss
`rorwarded to the image decoder system 230. The image
`decoder system 230 receives the encoded image data and
`decodes it to geoerate an output that is a representation of the
`original image that was received from the image source 210.
`FIGS. 3A and 3B are block diagrams illustrating two 60
`separate embodiments of the image encoder system 220 or
`the present invention. The image encoder system 220
`iocludes an image decomposer 31S, a header converter 321,
`one or more block encoders 318 (318a-318n, where n is the
`otb encoder, n being any positive integer), aod an encoded 65
`image composer 319. T he image decomposer 31S is coupled
`to receive an oribrinal image 310 from a source, such as the
`
`35
`
`6
`image source 210. The image decomposer 315 is also
`coupled to the one or more block encoders 318 and to the
`header converter 321. The header convener 321 is also
`coupled to the encoded image composer 319. Each block
`s encoder 318 is also coupled to the encoded image composer
`319. The encoded image composer 319 is coupled to the
`output 320.
`The image decomposer 315 receives the original image
`310 and forwards information from a header of ihe original
`10 image 310 to the header converter 321. The header converter
`321 modifies the original header to generate a modified
`header, as further described below. The image decomposer
`31S also breaks, or decomposes, the original image 310 into
`R number of image blocks, where R is some integer value.
`15 Tbc number of image blocks an original image 310 is broken
`into may depend on the number of image pixels. For
`example, in a preferred embodiment an image 310 com(cid:173)
`prised of A image pixels by .B image pixels \vlll typically be
`(N4) * (B'4) blocks, where A and Bare integer values. For
`20 example, where an image is 256 pixels by 256 pixels, there
`will be 64x64 blocks. In other words, the image is decom(cid:173)
`posed such that each image block is 4 pixels by 4 pixels (16
`pixels). Tho:;e skilled in the art will recognize that the
`munber of pixels or the image block size may be varied, for
`25 example mxn pixels, where m and n arc positive integer
`values.
`Briefly turning to FIG. 2B, there is illustrated an example
`of a single image block 260 io accordance with the present
`invention. Tbe image block 260 is comprised of pixels 270.
`The image block 260 may be defined as an image region W
`pixels 270 in width by H pixels 270 in height, where Wand
`H arc integer values. Jn a preferred embodiment. tbc image
`block 260 is comprised of W- 4 pixels 270 by T-Ta4 pixels
`270 (4x4).
`Turning back to FIGS. 3A and 3B, each block encoder
`318 receives an image block 260 from the image decom(cid:173)
`poser 315. Each block encoder 318 encodes or compresses
`each image block 260 that it receives to generate an encoded
`or compressed image block. Each t:ncoded image block is
`received by the encoded image composer 319 which orders
`the encoded blocJ,.-s in a data fi le. The data file from tht:
`encoded image composer 319 is concatenated with a modi(cid:173)
`fied header from the header converter 321 to generate an
`encoded image daia file that is forwarded to tbe output 320.
`FtLrther, it is noted that having more than one block encoder
`318a-318n allows for encoding multiple image blocks
`s imultaneously, one image b lock per block encoder
`318a- 318n, within the image encoder system 220 to
`increase image processing efficiency and performance.
`The modified header and the encoded image blocks
`together form the encoded image data tbat representS tbe
`original image 310. The function of each element of the
`image encodt:r system 220, including the block encoder 318,
`will be further described below with respect to FIGS.
`4A-4E.
`The original image 310 may be in any one of a variety of
`formats including red-green-blue (""RGB"), YUV 420, YUV
`422, or a proprietary color space. It may be useful in some
`cases to convert to a different color space before encoding
`the original image 310. It is noted that in one embodiment
`of the preseni invention, each image block 260 is a 4x4 set
`of pixels where each pixel 270 is 24-bitS in size. For each
`pixel 270 there axe 8-bits for a Red(R)-channel, 8-bits for a
`Grecn(G)-channel, and 8-bitS for a Bluc(B)-cbannel in a
`red-green-blue ("ROB") implementation color space.
`Further, each encoded image block is also a 4x4 set of
`
`50
`
`0020
`
`

`
`5,956,431
`
`5
`
`7
`pixels, but, each pixel is only 2-bits in size and bas an
`aggregate size of 4-bits as will be funher described below.
`FIG. 3C is a block diagram illustrating a block encoder
`318 of the present invention in greater detail. The block
`encoder 318 includes a color quantizer 335 and a bitmap
`constntction module 3<W. The color quantizer 335 is coupled
`to the bitmap construction module 340. Further, the color
`quantizer 335 further emphasizes a block type module 345,
`a curve selectioo module 355, and a codeword generation
`module 360. The block type module 3 45 is coupled to the 10
`curve selection module 355. The cnrve selectioo module 355
`is coupled to the codeword generation module 360.
`Each image block 260 of the decomposed original image
`310 is received and initially processed by the color quantizer
`335 before being forwarded to the bitmap construction 15
`module 340 for furthe r processing. The bitmap construction
`module 340 outputs encoded image blocks for the encoded
`image composer 319 to order. The bitmap construction
`module 3<W and the color quantizer 335, including the block
`type module 345, the curve selection modu le 355, and the 20
`codeword generation module 360, are further discussed
`below in FIGS. 4A-4E.
`Briefly, FIG. 30 is a diagram of a data sequence or string
`380 representing the original image 310 that is received by
`the block decomposer 315. The data s tring 380 of the
`original image 310 includes an a-bit header 380a and a b-bit
`image data 380b, where a and b are integer values. The
`header 380a may include information such as the pixel
`width of the image 310, the pixel bcigbt of the image 310,
`and lbe format of the image 310, e.g., the number of bits to
`the pixel in RGB or YUV format, tor ~xample, as well as
`other information. The image data is the data 380b repre(cid:173)
`senting the original image 310 itself.
`FIG. 3E is a diagram of a data sequence or string 385
`representing encoded image data 385 that is generated and
`output 320 by the image encoder