I|||||||||||||||||||||||l||||l|||||||||||||||||l|||||||||l||||||||||||||l||
`USOO668'i'4l0l£1
`
`(12) United States Patent
`Brown
`
`(10) Patent N0.:
`(45) Date n1’ Patent:
`
`US 6,687,410 B1
`Feb. 3, 2004
`
`(iraffagnino
`2121.11.11]
`61211111 Proctor 1:1.
`:11.
`8.-'2tJU(J Adiletta ctal.
`5121101 Cltaddha
`8121.11.11
`dc Ouciroz ct al.
`8121.11.11 Wang
`1.1211112 Chaddha
`
`..
`
`
`
`3821236
`3751241]
`3821236
`3481412
`38212'r'(J
`3481611?
`3?5;‘241J.l1‘i
`
`1i,1.131,93"1 A *
`6,11".-"2,83l1 A *
`6,lUl,2?6 A "
`6,233,017 B1 *
`15,275,621} 132 *
`15,281,942 B1 *
`6,331,881 B1 *
`
`FOREIGN PATENT DOCUMENTS
`
`W0
`
`W0 93 14601]
`
`7.-"1993
`
`D'l‘HE.R PUBLICATIONS
`
`IBM Technical 1)isclosure Bulletin, IBM (Iorp., New York,
`vol. 34 No.
`1, Jun., 1999 (Jun. 1991), pp. 289-291,
`XPOt.1U21U22U, ISSN: 0018-8689 p. 291, line 5—last line.
`
`* cited by examiner
`
`Priittntjv E.trmt:'ner—.Io.se L. Course
`
`(57)
`
`ABSTRACT
`
`The present invention is a compression scheme for com-
`pressing audio and video data. An image is divided into
`blocks of pixels. In one test, if all of the pixels are approxi-
`mately equal to the corresponding pixels in the previous
`block, then no data is sent for that block. In a seeunLl1esl,if
`all of the pixels in a block are approximately equal to a mean
`pixel value, then only one color value is transmitted. In a
`thircl
`test,
`if quantization of the pixels via compantling
`results in an acceptable representation, the quantization is
`performed. The present invention uses quantization codes.
`that are proportional to the logarithm ofthe magnitude olthe
`range quantized, computation of a magnitude byte that
`permits rapid discovery of the number of hits used for
`quantization of a block, recursive packing and unpacking of
`quantized pixel data, and two-dimensional paths through the
`block.
`
`14 Claims, '1' Drawing Sheets
`
`DSFIIE i|.D¢K G PLIELS
`3-H
`
`PERFORM TEST A
`ifl
`
`
`
`1
`
`Google Inc.
`(3000 1025
`[PR of US Pat. No. 1,974,339
`
`(54) METHOD AND APPARATUS FOR
`COMPRESSION AND DECOMPRESSION OF
`DATA
`
`(75)
`
`Inventor: Russell A. Ilruwn, Palo Alto, CA (US)
`
`(73) Assignee: Sun Micmsystems, Inc., Palo Alto, CA
`(US)
`
`( *1 Notice:
`
`Subject to any disclaimer, the term olithis
`patent is extended or adjusted under 35
`U.S.C.‘. 154(1)) by 0 days.
`
`(2-1) App]. No.: o9;499,2152
`
`(22
`
`Filed:
`
`Feb. 7, 20110
`
`Gl]6K 9,136
`Int. (:1?
`(51)
`3821239
`(52) U.S. Cl.
`3821232, 236,
`(58) Field of Search
`38?J238—24[1, 242, 248, 250; 3581432, 433;
`348f384.l, 394.l—395.l, 4UU.l—4(l4.l, 4U7.l—4l6.l,
`420.1, 421 .1, 425.2, 430.-1, 431 .1, 375,-'24n.n2—24n.o3,
`240.1 1-240. 1 6, 24018-2-’-10.2, 240. 22-24-0.25;
`341.-"51, 63, 65, 67, 79. 107; 7081203, 300,
`3117-3118, 313, 316-317, 4110-4115
`
`
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`358.1133
`382,-1233
`3821253
`348,391
`3821232
`
`3481699
`
`211980 Kcnichi et :11.
`1,-“I991 Watanabe ct al.
`S,-“[097 Knowles el al.
`2.11998 Manda el al.
`4,-“I998 Music
`511998 Suzuki ct al.
`12.11993 Peak
`111999 Lee
`li‘2|'J1'JCI Sun
`21200:] Pau
`
`..
`
`
`
`4,809_.(1f)'1' A
`4,984,076 A "
`5,661,822 A *
`5,721,':'91 A *
`5,739,861 A *
`5,754,698 A *
`s,a4'1_.ms A
`5,352,251 A
`15,014,181 A *
`6.03.295 A
`
`
`
`

`
`U.S. Patent
`
`Feb. 3, 2004
`
`Sheet 1 of 7
`
`US 6,687,410 B1
`
`DEFINE BLOCK OF PIXELS
`10.1
`
`PERFORM TEST A
`122
`
`NO DATA
`TRANSMISSION
`19.4.
`
`TEST A sA11sI=IED?
`Jfl
`
`
`
`PERFORM TEST 3
`
`10.5
`
`
`
`
`
`APPLY
`com-Ressson
`
`
`
`111?.
`
`TEST B
`
`SATISFIED?
`
`M
`APPLY
`
`COM PRESSiON
`
`1.12
`
`
`
`
`
`TEST C
`SATISFIED?
`199.
`
`
`
`
`
`
`BLOCK
`UNCOMPRESSED
`1.1.1.
`
`FIGURE 1
`
`PERFORM TEST C
`10!
`
`

`
`U.S. Patent
`
`Feb. 3, 2004
`
`Sheet 2 01'?
`
`US 6,687,410 B1
`
`GET NEXT PIXEL BLOCK
`
`2&0.
`
`
`
`TEST PIXEL EQUALITY
`
`am
`
`ALL PIXELS EQUAL?
`
`
`
`
`SET LAST
`
`TRANSMITTED BLOCK
`AS PREVIOUS BLOCK
`
`Z93.
`
`CALCULATE BLOCK
`VARIANCE
`
`
`
`223.
`
`
`UPDATE
`WITHIN
`COUNTER
`THRESHOLD?
`
`E
`
`2§§
`
`
`
`
`
`
`GO TO TEST 8
`
`
`
`
`31
`
`FIGURE 2
`
`

`
`U.S. Patent
`
`Feb. 3, 2004
`
`Sheet 3 of 7
`
`US 6,687,410 B1
`
`OBTAIN NEXT PIXEL
`BLOCK
`
`3_0_Q
`
`3.93.
`
`
`
`no Lust SQUARES
`
`£113
`
`
`TEST
`SATISFIED?
`
`E.
`
`
`
`60 TO TEST c
`
`
`
`.3.9_§
`
`FIGURE 3
`
`
`
`
`ALL PIXELS EQUAL?
`
`OUTPUT CODE
`
`

`
`U.S. Patent
`
`Feb. 3, 2004
`
`Sheet 4 01'?
`
`US 6,687,410 B1
`
`
`
`FIGURE 4
`
`

`
`U.S. Patent
`
`Feb. 3, 2004
`
`Sheet 5 of 7
`
`US 6,687,410 B1
`
`
`
`FIGURE 5
`
`

`
`U.S. Patent
`
`Feb. 3, 2004
`
`Sheet 6 of 7
`
`US 6,687,410 B1
`
`

`
`U.S. Patent
`
`Feb. 3, 2004
`
`Sheet 7 01'?
`
`US 6,687,410 B1
`
`
`
`
`OBTAIN NEXT PIXEL
`BLOCK
`
`19.0
`
`SET HAGNITUDE BYTE
`TO ZERO
`
`
`
`E
`
`
`
`
`
`
`
`OUTPUT PACKEO
`CODES AND INITSAL
`
`BYTE
`
`22%
`
`
`
`IQ.
`
`PRODUCE CODES
`
`CALCULATE
`
`VARIANCE
`
`I91
`
`
`
`
`
`PACK QUANTIZATION
`CODES
`
`
`7.01
`
`
`
`
`TEST
`
`SA'l1SFIED?
`Z29
`L03.
`
`
`EXAMINE MAGNITUDE
`BYTE
`
`OUTPUT 3 BITS PER
`PIXEL
`
`I95
`
`FIGURE 7
`
`

`
`US 6,6814 10 B1
`
`1
`METHOD AND APPARATUS FOR
`COMPRESSION AND DECOMPRESSION OF
`DATA
`
`BACKGROUND
`
`1. Field of the Invention
`
`This invention relates to the field of data compression.
`Portions of the disclosure of this patent document contain
`material that is subject to copyright protection. The copy-
`right owner has no objection to the facsimile reproduction
`by anyone of the patent document or the patent disclosure as
`it appears in the Patent and Trademark Office tile or records,
`but otherwise reserves all copyright rights whatsoever. Sun,
`Sun Mierosystems, and MAJC, are trademarks or registered
`trademarks of Sun Microsystems, Inc. in the United States
`and other countries.
`
`2. Background
`Computer systems are increasingly being used to play
`back multimedia (audio and video) files. Current computer
`systems are often unable transfer data quickly enough from
`storage to allow adequate playback. To solve this problem,
`the multimedia data is compressed for transmission and
`decompressed for playback. However, some compression -
`schemes are not suitable for environments where there is
`
`10
`
`2
`In a third test, it is determined if quantization of the pixels
`via eompanding result in an acceptable representation ofthe
`pixel values. If so, the quantization is used.
`The present
`invention uses quantization (companding)
`codes that are proportional to the logarithm of the magnitude
`of the range quantiaed, computation of a magnitude byte that
`permits rapid discovery of the number of bits used for
`quantization of a block, recursive packing and unpacking of
`quantized pixel data, and two-dimensional paths (even 4
`parallel paths) through the 4 by 4 or 8 by 8 block. In the case
`of image processing, the eornpanding algorithm is initialized
`for each block using one byte of pixel data, which represents
`the unquantized representation of the initial pixel of the
`block. Quantization [companding) proceeds on a pixel-by-
`- pixel basis for each pixel in the block. Thus there are only
`a finite number of pixels processed for a given block before
`the quantization algorithm is reset using the unquanlized
`representation of the initial pixel of the next block. Because
`only a finite number of pixels is processed, there is a high
`probability that only a limited range of quantization codes
`will be used for a given block. Therefore,
`there is an
`excellent chance that
`the quantization codes for a given
`block will fit into one or two bits, not the maximum of four
`bits. This et‘Iect permits compression of the quantization
`codes via the recursive packing algorithm.
`BRIEF DESCRIPIION OF THE DRAWINGS
`
`little processing power available.
`Computers are often used to process, play back, and
`display video data. This video data may come from sources
`such as storage devices, on-line services, VCRs, cable
`systems, broadcast
`television tuners, etc. Video data is
`memory intensive, that is, video data requires large amounts
`of memory for storage and use by a computer system.
`To reduce the transmission bandwidth and memory
`requirements when working with video data, various com-
`pression schemes have been developed so that less storage
`space is needed to store video information and a smaller
`bandwidth is needed to transmit it. Prior art video compres-
`sion schemes include Motion JPEG, MPEG-1, MPEG-2,
`Indeo, Quicktime, True Motion-S, CinePak, etc.
`Many prior art compression schemes rely on fast process-
`ing or powerful processors to decompress image or audio
`data. Many current systems exist where there is very little
`processing power available at
`the point of display. For
`example, a so called “thin” client that is part of a computer
`system may lack sophisticated processing power. A scheme
`is required that can compress and decompress data with little
`computational efi°ort.
`SUMMARY OF TIIE INVENTION
`
`The present invention is a eomprcssion—scheme for com-
`pressing audio and video data. For image compression, an
`image is divided into blocks of pixels. The blocks may be
`4x4 pixels, 5x5 pixels, 3x8 pixels, etc. A number of algo-
`rithms are used on each block to determine the best method
`ofcompressing that block ofpixels. In one embodiment, the
`invention perfonns tests on the blocks. In one embodiment,
`the pixels of the block are compared to analogous pixels in
`a previous block. For example, the top left pixel of a block
`is compared to the top left pixel of the previous block and
`so on. If all of the pixels are approximately equal to the
`corresponding pixels in the previous block,
`then no data
`need be sent for that block, instead, the previous data can be
`used. In a second test, it is determined if all of the pixels in
`a block are approximately equal to a mean pixel value. If so,
`then only one color value need be transmitted for the block.
`
`FIG. 1 is a flow diagram illustrating the operation of one
`embodiment of the present invention.
`FIG. 2 is a flow diagram illustrating the operation of one
`embodiment of test A of the present invention.
`FIG. 3 is a flow diagram illustrating one embodiment of
`test B of the present invention.
`FIG. 4 is a diagram of the path taken by the compander
`through a block of pixels.
`FIG. 5 illustrates alternate paths taken by the compander
`in the present invention.
`FIG. ti is a block diagram of a compander.
`FIG. 7 is a flow diagram illustrating one embodiment of
`test C of the present invention.
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`A compression scheme for multimedia data is described.
`In the following description, numerous specific details are
`set forth in order to provide a more detailed description of
`the invention. It will be apparent, however, to one skilled in
`the art, that the present invention may be practiced without
`these specific details. In other instances, well known details
`have not been provided so as to not unnecessarily obscure
`the invention.
`
`The present invention is directed to a compression scheme
`for multimedia data. In an embodiment
`that compresses
`video data, compression is applied to each video frame of
`the video data. Each frame consists of lines of pixels. The
`pixels are grouped into blocks of pixels. The pixels are then
`subjected to a series of tests to determine if a simple or less
`computationally intensive compression scheme can be
`applied to the block. The tests are simply the attempted
`application of increasingly more complex compression tech-
`niques. If a test
`is successful,
`that
`is, if the attempted
`compression results in adequate compression and acceptable
`quality, then no more testing is done and that compression
`scheme is applied to the block. If a test fails for lack of
`adequate. compression or quality,
`then the next
`test
`in
`sequence is attempted.
`
`4-0
`
`45
`
`50
`
`_
`
`E0
`
`65
`
`

`
`3
`The tests are attempted until adequate compression and
`quality are accomplished, or until
`the last
`test has been
`reached. The invention has the advantage of reducing the
`computation required for compression and for achieving
`greater compression rates than single algorithm schemes
`without loss of quality. A flow diagram of the operation of
`the invention is illustrated in FIG. I. At step 101 a block of
`pixels is defined. This block may he 4x4, 5x5, 8x8, or any
`other suitable block size. At step 102 a first
`test A is
`performed on the block. At decision block 103 it is deter-
`mined whether the test
`is satisfied for compression and
`quality. If so, the system sends no data at step 104 and
`returns to step 101.
`If the decision at block 103 is not satisfied, the system
`applies a second test B at step 105. At decision step 106 it
`is determined whether the test is satisfied for compression
`and quality. If so, that compression scheme is applied at step
`107 and the system returns to step 101.
`If the decision at step 106 is not satisfied, the system
`performs test C‘ on the block at step 108. At decision block
`109 it
`is determined if the test
`resulted in appropriate
`compression and quality. If so. the scheme is applied at step
`110 and the system retrieves the next block at step 101. If
`not, the block is uncompressed (step 111).
`Although the system of FIG. 1 shows the use of three tests
`for compression, the present invention can be used with any
`number of tests as appropriate. The number of tests used
`may impact the speed of compression and decompression.
`Where that is ofconcern, fewer tests may be used. However,
`the present
`invention contemplates an asymmetrical
`compressionidecompression scheme, where compression
`might take longer than decompression.
`
`In one embodiment of the invention, gamma corrected
`RGB color components for each pixel are transformed to ‘
`obtain Y, Cb, and Cr components. Y, Cb, and Cr are
`compressed independently to produce compression data for
`the block of pixels. For each of Y, Cb, and Cr, the compres-
`sion scheme produces six different compression codes that
`vary according to the block under consideration. Thus, for
`each pixel within a block,
`there are three outputs, each
`consisting of a compression code followed by a variable
`number of bytes of compressed data.
`The compression codes of this embodiment of the present
`invention (applied to a 4x4 block of pixels) are as follows:
`
`4-0
`
`45
`
`Contpressinn Code
`
`Interpretation
`
`Bytes
`
`50
`
`0
`I
`2
`3-
`4
`:3
`
`0 bits per pixel
`H2 hit per pixel
`I hit per pixel
`3 bits per pixel
`4 bits per pixel
`8 bits per pixel
`
`0
`I
`3
`5
`9
`16
`
`US 6,6814 10 B1
`
`4
`
`Test A
`In one embodiment of the invention, test A determines
`whether each pixel in the block being tested is approxi-
`mately equal to the corresponding pixel in a previous block.
`For purposes of this discussion, the block being tested is
`referred to as the “present block” and the block to which it
`is compared is referred to as a "previous block". The
`previous block may be a block in a previous frame (such as
`a block in the corresponding block position as the present
`block). Allematively, the previous block may be a block in
`the same frame as the present block, such as the immediately
`preceding block.
`In test A, a variance is calculated between the present
`block and the previous block. This previous variance may be
`calculated as:
`
`10
`
`V_a=2(Pr'—tn'J:
`where p,. represents the present pixel value and b,. represents
`the previous pixel value.
`If the previous variance VP falls below a threshold
`referred to as the “previous variance threshold”, then the
`previous block of pixels is an adequate approximation of the
`present block of pixels and it can be substituted for the
`present block. This is very efficient encoding since no block
`data need be transmitted for the present block.
`The present invention provides additional optimization in
`this embodiment. If all three color components (Y, Cb, Cr)
`pass the variance test A, there is an assumption that the block
`of data is probably part of an image background that does
`not change much between subsequent frames of the image
`sequence. It is also likely that this block of pixels is adjacent
`to other blocks of pixels that represent other relatively
`invariant parts of the image background. When this occurs,
`the invention initializes a counter to one, and for each
`subsequent, adjacent block for which all three colors pass
`the variance test, the counter is incremented by one. This
`creates a run length limited (RLL) optimization of test A.
`Whereas use of the opcode byte permits each block to be
`represented by one byte, the RM. optimization permits the
`representation of many blocks by only two bytes, where the
`first byte specifies the run length encoding and the second
`byte represents the length of the run. Ifonly the second byte
`were used to indicate run length, only 255 blocks could be
`included in a run. This limitation is overcome by using part
`of the opcode byte to encode the most significant bits of the
`run length value.
`The opcode byte contains three compression codes
`encoded in radix-6 format. Because each compression code
`can assume a value of 0 through 5, the opcode byte assumes
`values of 0 through 215, leaving 40 unused values in the
`opcode byte. These unused values can be taken advantage of
`to encode the MSB’s of the run length. Letting o represent
`the value of the opcode byte and c represent the value of the
`count byte, then the values maybe obtained from the count
`value via:
`
`o-(mu I'll) >8}-t-21 6
`c=c0mt.r— [ I_’r.‘armI> =8) <-<8]
`
`The present invention combines the three compression
`codes into one “opcode” byte,
`followed by a variable
`number of bytes of compressed data for each of Y, Cb, and
`Cr.
`
`The opcode byte is constructed by packing the three
`compression codes in radix-6 format. Letting (Ty,
`(.‘,._.,.,, and
`CC, represent
`the compression codes for Y, Cb, and Cr
`respectively, the opcode byte 0 is constructed as:
`
`O=fi[6CI’.+C(_-&J+CC,
`
`where >> represents the right shift operator and >>8 is
`equivalent to division by 256, and where << represents the
`left shift operator and <48 is equivalent to multiplication by
`256. When the opcode byte and the count byte have been
`calculated as above, then the count value may be obtained
`from these two bytes by:
`count-[(0-316_t<<8]+n
`
`E0
`
`65
`
`This approach allows the encoding of a run length of
`10,239.
`
`10
`
`

`
`US 6,6814 10 B1
`
`10
`
`-
`
`5
`The lirst test of this embodiment of the present invention
`looks for blocks that are approximately identical, that
`is,
`their variance is within some threshold value. If a series of
`blocks have pixel values that vary slowly, each present
`block, when compared with a previous block, may satisfy
`the conditions of test A. However, when test A is satisfied,
`the same block is used again and again by the decoder. In
`some situations, that could lead to propagation of error.
`Consider where 100 consecutive blocks vary from each
`other by some small value. If test A is not satisfied for the
`tirst block, the pixel values of that block are transmitted. The
`first block now becomes the previous block and the next
`block becomes the present block. If a comparison of the
`present and previous blocks now satisfies test A, the result
`is to send no data, because the decoder can use the previ-
`ously sent block (that is, the first block.) If this situation
`were to repeat for 100 blocks, the first block would be used
`by the decoder for all of the 100 blocks, even though after
`"100 repeats the difference in pixel values between the first
`block and the present block is 100 times the difference
`between any two consecutive blocks. In this situation, the
`decoder uses the first block for the present block even
`though the large difference between the two blocks does not
`satisfy the conditions of test A.
`The problem can be eliminated by designating the most
`recently transmitted block as the previous block. With this
`approach, each present block is compared to the block
`actually transmitted (in the above example, the first block.)
`In this manner, gradual changes in pixel values will even-
`tually exceed the threshold for test Aand result in transmis-
`sion of the present block (and correspondingly replace the
`previous block with the newly transmitted block.)
`It should be noted that,
`in one embodiment of the
`invention, test Acan include a check for exact equality of a
`pixel of one block and a cort‘espot1ding pixel of another .
`block. Exact equality is subsumed in the test for approximate
`equality, but
`the exact equality test has relatively low
`computational cost and can result
`in higher compression
`speeds, particularly for synthetic graphic images.
`FIG. 2 is a flow diagram of one embodiment oftest A. At
`step 200, the pixel block to be examined is obtained. At step
`201 the pixels are tested for equality with corresponding
`pixels of another block. At decision block 202, if all pixels
`are equal, compression code 0 is transmitted at step 208.
`If the pixels are not equal at block 202 the block variance
`is calculated at step 203. At decision block 204 it
`is
`determined if the variance is within the desired threshold. If
`
`4-0
`
`45
`
`not, the system moves to test B at step 207.
`If the variance threshold is met at step 204, compression
`code 0 is transmitted at step 208. At step 209,
`the last
`transmitted block is set as the previous block as the system
`returns to step 200.
`Test B
`then a second type of
`test,
`If the block fails the first
`comparison (test B) is applied. Test I3 is actually a two part
`test. First, test B determines whether all pixels within the
`block are equal
`to one another.
`If so,
`the compression
`algorithm outputs compression code 1, followed by one byte
`representing the constant value of the color component
`within the block.
`If all of the pixels in the block are not equal, then the
`least—squares variance v“, is computed for the block to see
`if all of the pixels in the block are approximately equal to
`some mean value as follows:
`
`where N is the number of pixels in the block and p,.
`represents the pixel values. If the least-squares variance is
`less than a low-variance threshold, then the mean pixel value
`
`50
`
`_
`
`E0
`
`65
`
`ll
`
`6
`for the block is a reasonable approximation to the value of
`all pixels within the block. In this case, the algorithm outputs
`compression code 1, followed by one byte representing the
`mean pixel value for the block. Note that a positive least-
`squares variance test
`is the second instance where the
`compression algorithm outputs compression code 1 fol-
`lowed by one byte of data. The first instance was the case
`where all pixels were equal to one another within the block.
`The least-squares variance test is a more general test that
`subsumes the case where all pixels are equal. Thus, it is
`possible to eliminate the test for equality of pixels, and allow
`this condition to be detected as a least-squares variance of
`zero. However, the equality test has a low computational
`cost and could result
`in higher compression speeds for
`images with traditional amounts of single color back-
`grounds. This feature may, for example, be enabled when
`compressing synthetic images, as they are more likely to
`have regions of constant pixel values. The feature may be
`disabled when compressing video images, which may lack
`such uniform backgrounds.
`FIG. 3 is a How diagram illustrating one embodiment of
`test B. At step 300, the next pixel block to be examined is
`obtained. At step 301 an equality test is performed to see if
`all of the pixels in the block are equal. If so, compression
`code 1 is transmitted at step 302 and the system returns to
`step 300.
`If all of the pixels are not equal then the least squares
`variance test is applied at step 303. If the variance test is
`satisfied at decision block 304, the system outputs compres-
`sion oode 1 at step 302 and returns to step 300. If the
`variance test is not satisfied, the system proceeds to test C at
`step 305.
`Test C
`
`If the least-squares variance is greater than the low-
`variance threshold,
`then the simple cases have been
`exhausted, and the pixels within the block are subjected to
`Test (i. For each 8-bit pixel value, the quantizer produces a
`4-bit quantization code that represents the quantized differ-
`ence between the pixel value and the value of the previous
`pixel within the block. (Note that
`the definition of the
`previous pixel can mean a number of things).
`Consider the following quantization algorithm:
`for each block
`
`lastm value=tirst,3 pixel
`for each pixel” value p in block
`diff-p—last 13 value
`qu value=quant[diff]
`last” value-clamp[last_ value
`+d,3 quant[q_vatue]]
`emit qm value
`end
`end
`The quantization algorithm is implemented using two
`table lookups. The quantfditf] operation is accomplished via
`a
`lookup table addressed by a 9-bit signed difference
`between successive pixel values. The clamp[last13 value+
`dquant[q,3 value]] operation is accomplished via a lookup
`table addressed by a 12-bit value that
`is obtained by cat-
`enating the 4-bit q,3 value with the 8-bit last” value.
`An extension of the above quantization algorithm permits
`estimation of the coarseness of the quantization. As the
`quantizer creates the quantized values for a particular block,
`it creates the quantization variance vq:
`
`"'.7'2(I7;"fJ'i'i:
`where p, represent the original pixel values and (:1, represent
`the quantized pixel values. If the quantization variance
`
`

`
`7
`the quantization will
`exceeds a high-variance threshold,
`introduce too much error into the pixel representation, and
`hence the quantized data must not be used. In this case, the
`compression algorithm outputs compression code 5, fol-
`lowed by 16 bytes representing the 16 unquantized pixel
`values for the 4x4 block (or 64 bytes for an 8><8 block.) Prior
`to comparison to the low— or high-variance thresholds,
`respectively,
`the least-squares variance and quantization
`variance can be normalized to the square of the mean pixel
`value for the block. The normalized variance expresses a
`constant ratio between the least-squares error and the mean
`pixel value for the block. Because the human visual system
`is sensitive to ratios of light intensity, this approach models
`the threshold test after the physiologic response of the
`human visual system.
`Returning now to the discussion of quantization, if the
`quantization variance does not exceed the high-variance
`threshold, then the quantized pixel values will be output.
`However, often it is possible to output fewer than four bits
`per pixel of quantized data. In order to output fewer than
`[our bits, it is necessary to define quantization codes such
`that there is a correlation between the number ofbits used by
`a particular quantization code, and the magnitude of the
`difference that is quantized. Such a definition is:
`
`|)i1Tercnce
`
`-255 to -91
`-90 to -71
`-"EU to -51
`-50 to -31
`-30 [CI -16
`-15 to -8
`-7 to -3
`-'3 to U
`1 to 2
`.1 to 7
`S to 15
`16 to St]
`31 in 50
`5] [0 70
`Ti
`to 90
`91 to 255
`
`codc
`
`14
`12
`10
`8
`6
`4
`2
`0
`J
`3
`5
`'.-'
`9
`H
`13
`15
`
`4-0
`
`This coding can be important, because for many blocks
`the interpixel variation is sufficiently small that any quan-
`tization code produced for these blocks may he represented
`using two bits, or even one bit.
`A test of the number of bits required to represent any
`quantization code for a particular block may be implemented
`as follows. Prior to producing the quantization codes, the
`quantizer initializes a magnitude byte to zero. As the quan-
`tizer creates each quantization code, it inclusively ORs the
`code into this magnitude byte. When the quantizer has
`finished creating quantization codes for all pixels of the
`block,
`the magnitude byte contains a value that may be
`bit-tested to determine the maximum number of bits _
`
`45
`
`S0
`
`required to represent any quantization code for the block.
`Once the number of bits required to represent any quan-
`tization code for the block is determined. the compression
`algorithm packsthc quantization codes as two, four, or eight
`pixels per byte, oorresponding to four, two or one bit per
`pixel, respectively. It is possible to pack the quantization
`codes as follows.
`A 4-><4 block contains 16 quantization codes. The quan-
`tizer plaoes these 16 codes into an array of 16 unsigned
`characters, with each code occupying the four
`least-
`significant bits of a character. Using the union type available
`in C,
`it
`is possible to simultaneously represent
`the
`
`60
`
`65
`
`12
`
`US 6,687,410 B1
`
`8
`16-element character array as an array of eight shorts, four
`integers, or two long longs:
`
`typ-tzdcf union block {
`unsigned char e[1ti]:
`unsigned short s[3]:
`unsigned int i[4]'.
`unsigned long long ll[2]:
`} Block:
`
`10
`
`Then with a variable b of type Block, it is possible to pack
`the quantization codes recursively into the two-, four- and
`eight—pixels—per—byte representations as follows:
`
`37-!t'[0]=((b-If[D]<<4]|(b-H[1]);
`
`b—"iT0]=((b—'fIl}]}<<3)|{b—'tTl]]1
`
`I5"-*il3l=[(-'7"-9ll3]J<<1Ji(b"-Till}:
`
`The first of the above operations packs the codes as two
`pixels per byte, the second packs them as four pixels per
`byte, and the third packs them as eight pixels per byte. The
`worst case, where quantization codes are to be packed eight
`bits per pixel, requires only three shifts and three inclusive
`ORs per 4x4 block, making for an etlicient scheme. This
`scheme may be adapted without difficulty to other block
`sizes, for example, and 8x8 block.
`These recursive packing operations affect the ordering of
`the quantization codes within the 16-element array. If the
`codes were initially arranged in the following order in the
`array for a 4x4 block:
`01234S6789101112131=t-15
`
`then the recursive packing operations shuffles the codes
`successively as the packing operation proceeds from four to
`two to one bit per pixel, as shown below:
`08192103 1] 4125 136 14715
`04812 1591326 101437 11 15
`024-681012l41357911 1315
`This permutation of the order of the codes is acceptable, so
`long as the decoder unpacks the codes in the proper order.
`For a 4x4 block, the four-, two- and one-bit-per-pixel
`representations require eight, four and two bytes, respec-
`tively. To these bytes is appended one additional byte which
`represents the unquantized value of the first pixel
`in the
`block. This byte provides an accurate starting point for the
`decoder at
`the beginning of each block. This approach
`makes the decoder less sensitive to bit errors that may arise
`due to transmission noise affecting the encoded image data.
`Additionally, this approach increases the probability that the
`quantized pixel data may be represented using less than four
`bits per pixel.
`Depending upon which packing representation is used,
`the compression algorithm outputs a compression code (4, 3,
`or 2) followed by one byte representing the value of the lirst
`pixel of the block, followed by eight, four or two bytes of
`quantized pixel data {for a 4x4 block.)
`FIG. 7 is a flow diagram illustrating one embodiment of
`test C. At step 700 the next pixel block to be examined is
`obtained. At step 701 the magnitude byte is initialized to
`zero. At step 702 the companding algorithm produces the
`4-bit quantization codes. Also at this step, each quantization
`code is inclusively ORed into the magnitude byte. At step
`703 the quantization variance VP is calculated from the
`original pixel values p,. and the quantized pixel values q,..
`Note that this step may be performed contemporaneously
`with step 702.
`
`

`
`US 6,6814 10 B1
`
`9
`At step 704 the quantization variance is examined. If the
`quantization variance exceeds the high—varianoe threshold,
`then 8 bits per pixel are output
`in step 705, and control
`transfers back to step 700 to process the next block of pixels.
`If, however, the quantization variance does not exceed this
`threshold, then the 4-bit quantization codes will be packed
`and outputted. In step 706 the magnitude byte is examined
`to determine the number of bits required to represent the
`quantization codes (4, 2, or I). In step 707 the quantization
`codes are packed via the recursive packing algorithm. In step
`708,
`the 8 bit value of the initial pixel of the block is
`outputted, followed by the packed quantization codes. Con-
`trol then transfers back to step 700 to process the next block
`of pixels.
`Prior Pixel
`The quantizer quantizes the difference between succes-
`sive pixels. A block of pixels is two-dimensional. For this
`reason, the quantixier is directed to follow a path through the
`block, such as the path from point a to point b shown in FIG.
`4 for a 4x4 block.
`
`10
`
`.
`
`10
`In order to update the value of the last pixel 1,, the encoder
`performs the same operations that are to be performed by the
`decoder. The dashed box encloses these operations.
`Specifically, the 4-bit quantized value q,. is dequantized to
`obtain a 9-bit value. This 9-bit dequ antized value is added to
`the 8-bit value of the last pixel l,- to obtain a 10-bit value.
`This 10-bit value occurs because the 4-bit quantized value q_.
`is not a fully accurate representation of the 8-bit pixel value
`p,., and so the value obtained by addition of the 9-bit
`dequantized value to the 8-bit value of the last pixel 1, may
`be less than 0 or greater than 255 (the allowed range for an
`8-bit number.) Therefore, the 10-bit value is passed through
`a low-pass filter {I.PF) which clamps it to the range of U to
`255. The resulting 8-bit value becomes the updated value for
`1,-. These techniques are known in the prior art. An imple-
`mentation of a compandcr in an alternate embodiment uses
`loo