the preferred embodiment is a software implementation of the operations shown in fig1 and fig2 . the algorithms can be executed efficiently on a commodity microprocessor as found in personal computers , or a microprocessor or dsp as may be found in consumer products . additionally , special purpose hardware can be designed by a person of ordinary skill in the art to implement the present invention . referring to fig1 a color image is represented by an array of rgb colors , 1 , and is compressed by a number of operations to generate base components , 23 , 24 and 25 , and detail components , 26 and 29 . the base components include three independent parts , a base y component , 25 , a base u component , 23 , and a base v component , 24 . the rgb image is contained in memory either as a single array with one long word per pixel , 120 , or as three independent arrays , one each for red , green , and blue , each with one byte per pixel . for each pixel , the rgb color is transformed into yuv color space . the specific transform used can be any one of numerous transforms known in the art . the traditional transform is defined by the following equation . ## equ3 ## however , since this conventional transformation requires a significant number of multiplication steps per pixel , the transformation described in my copending u . s . patent application ser . no . 07 / 865 , 071 filed apr . 8 , 1992 can be used and is substantially more efficient and preferred . since the compression algorithm of the present invention can also be used to compress color image data that is already in yuv format , the above described color space transformation , 2 , may not be necessary . further , it will be obvious to one skilled in the art that a totally different color space transformation could be used in lieu of 2 to transform from an arbitrary color space to a color space with chrominance and luminance components . after the image has been transformed to yuv color space , the algorithm diverges into two paths . one path generates the base components including the three independent parts a base y component , 25 , a base u component , 23 , and a base v component , 24 . the other path generates the detail components , 26 , 29 . the generation of the base components is described first . the y , 5 , u , 3 , and v , 4 , components are each down sampled in the horizontal and vertical direction by averaging two pixels horizontally and two pixels vertically to generate each pixel in the downsampled component image . for example , referring to fig5 pixel values 40 , 41 , 42 , and 43 are added together , then the sum is divided by four ( shift right two bits ) to generate the pixel 44 in the downsampled image . this same operation is performed on every other group of four pixels for the rest of the y , u and v component images . in fig5 a , six groups of 2 × 2 pixel arrays are each highlighted with a unique shading pattern . the pixels in the resulting down sampled image of fig5 b that are produced by downsampling the highlighted pixels in fig5 c are shown using the same unique shading pattern . these six pixel groups are representative of all the pixels in the image . although a simple box filter is preferred due to computational simplicity , a more sophisticated filter , such as a two dimensional gaussian filter , could be used to good results , particularly if more computation power is available . after down sampling , the u and v components are filtered and down sampled once again , although in this case a gaussian filter is used , and the filtering and down sampling is down only in the horizontal direction . referring to fig1 this is shown in 10 , 8 , and 9 for the y , u , and v components respectively . referring to fig6 for each scan line in the image ( for u and v ), a 1 : 2 : 1 gaussian filter is applied to generate a new scan line with half the number of sample points . the generation of the first output pixel in each scan line , 60 , is handled as a special case since this is a boundary condition . the value of p 0 , 50 , is multiplied by three , 54 , ( by using a left shift and an add operation ), and is added , 56 , to the value of p 1 , 51 . the result is divided by four ( by shifting the result twice to the right ), 58 , to normalize the range to be the same as the input pixels . the next pixel , 61 , and the remainder of the pixels in the scan line are generated by filtering three input pixel values . to calculate p 1 , 59 , the value of pixel p 2 , 52 , is multiplied by two ( by shifting left one bit ), 55 , and added , 57 , with the value of p 1 , 51 , and p 3 , 53 . the result is divided by four ( by shifting right two bits ), 59 , to generate the output pixel , 61 . it is clear from fig6 how this process is repeated on the remainder of the pixels on each scan line . for this filtering and down sampling step , the more sophisticated gaussian filter is preferred over a simple box filter . this is because this filtering step is executed only in one dimension and the improvement in image quality justifies the increased computational expense . a more or less sophisticated filtering approach could be used for this step as well for less expensive systems . referring back to fig1 after filtering and down sampling , each of the y , u , and v components is coded using differential pulse code modulation ( dpcm ). this is a well known technique to take advantage of the predictability of a non - random input source . each of the y , u , and v components are processed independently by the three dpcm blocks 14 , 12 , and 13 respectively , although the operations performed are identical . pulse code modulation ( pcm ) simply refers to the use of digital samples to represent the analog video signal . this is exactly the way the image data is normally stored in a frame buffer in uncompressed form . differential pcm means that , instead of storing the actual sample values , each sample value prediction is based on previous sample values , and the difference between the actual value and the predicted value is used as the new dpcm sample . if there is a lot of regularity in the image , the predicted value will be close to the actual value and the dpcm values will be small . this will allow them to be coded efficiently in the next stage of the compression algorithm . the dpcm is extended to include quantization of the predictor errors , to allow them to be coded more efficiently using huffman coding . in the preferred embodiment , the prediction is very simple ; the predicted value is equal to the previous predicted value minus the quantized error . this approach is currently preferred for computational efficiency . however , a more advanced predictor could also be used , using multiple previous pixel values to estimate the value based on a higher order curve fit . although the dpcm and huffman coding are shown as two independent operations , they are implemented more efficiently in the preferred embodiment by calculating them together . referring to fig7 the y , u , or v component 74 is subtracted from the predicted value for that component 67 by subtract operation 65 . the result 69 is the predictor error and is used to index into a precomputed table 66 to generate the quantized predictor error 73 , the huffman coded quantized predictor error 71 , and the length of the huffman code 72 . the predicted value for the next sample 67 , is calculated by subtracting the quantized predictor error from the predicted value for the current sample 70 . by using the quantized predictor error to calculate the new predicted value , any error due to the quantizing will not accumulate , but instead will be offset from the next sample calculation . the contents of the table used to generate the quantized predictor error and the huffman coded error is shown in fig8 . the range of inputs is shown in the left most column . all entries in this range have the same contents as shown by the remaining three columns in the table . the huffman code length is used to generate the data stream and simplify the coding in the next step of the compression algorithm . for most images , the sample to sample correlation is very high in the base component and the predictor error is typically in the range of - 8 to 7 , resulting in a large percentage of two bit huffman codes . additional compression is achieved by grouping runs of two bit codes . this is done independently for the y , u , and v component huffman code streams . each run of 16 codes from each of the component streams is packed into one of two formats . if a block of 16 codes is comprised entirely of two bit codes , then it is replaced by 17 bits having a leading ` 1 ` and 16 bits , one bit for each of the 16 codes identifying whether the code is ` 01 ` or ` 11 `. otherwise , the block is coded as a leading ` 0 ` followed by the 16 codes . an example of this run coding is provided by fig9 . here , the first block of 16 codes contains all two bit codes and can be further compressed into 16 one bit codes . the second block does not consist of all two bits and is not further compressed . the output of the run coders , 22 , 20 , and 21 , make up the base y , u , and v components of the compressed image data set . the detail components of the compressed data set is generated in a completely different manner from the base components . referring to fig1 the detail component is calculated for the y color component only , and is derived from the full resolution y component image 5 . referring to fig1 , the y component image is grouped into 2 × 2 pixel cells . for each cell , an approximation of the variance and a mask is calculated . the mask indicates whether the pixel value was greater than or less than the average for the cell . referring to fig1 , the average 92 is computed by adding 90 the values of the y component of the four pixels , and dividing by four 91 . for example , in fig1 , the average of the cell in the upper left 84 is calculated by adding the value of pixels p 0 80 , p 1 81 , p 2 82 , and p 3 83 , and then shifting the result right two bits . the remainder of the cell averages are computed in a like manner . note that if a box filter is used to downsample the y component 10 during the calculation of the base component of the compressed image , then the average of the cell was calculated for this purpose . in the preferred embodiment , the downsampled y component image is used for the cell averages to avoid redundant calculations . for each cell , an approximation of the variance is calculated by averaging the absolute value of the difference between the value of each pixel in the cell and the average of the values of all the pixels in the cell . this approximation is referred to as alpha α 104 . referring to fig1 , the pixel value is subtracted from the computed average 92 by the subtract operations 93 , 94 , 95 and 96 . the sign bit 107 , labeled s in fig1 , from each of the subtract operations is saved as a mask 106 . this mask indicates whether the pixel value was greater than or less than the computed average for the cell , 92 . the absolute value 97 , 98 , 99 and 100 , of the result from each of the subtract operations is then averaged to calculate an approximation of the variance , referred to as alpha . this averaging is done by adding 101 the results of the absolute value operations 97 - 100 , and dividing the result by four 102 . the divide by four is performed by shifting the result right two bits . the alpha value is then quantized to four bits 103 to reduce the number of bits required to store it . a rounding operation can be done before quantizing by adding a constant and checking for overflow . the four bit mask value 106 is combined with the four bit quantized alpha 104 to form a one byte detail component for each cell . referring to fig1 a thresholding operation 19 is then performed on the alpha value . if the cell does not contain sufficient high frequency information ( as determined by the magnitude of the alpha value ), the detail component for the cell is discarded . the four bit alpha component 104 is compared with a threshold value that can be modified to suit the compression requirements . if the alpha value is less than the threshold , the alpha 104 and the mask 106 information for that particular cell is not included in the final detail component of the compressed data set . a bit mask is generated 27 to indicate whether the detail information for the cell was retained or discarded . before coding 28 this bit mask 27 contains one bit for each of the 2 × 2 pixel cells in the image . since most of the cells will be discarded , the bit mask 27 can be coded to reduce its size . referring to fig1 , the bit mask 27 is represented as a string of bits describing the cells in normal scan - line order . the bits are grouped into runs of eight bits , for example 110 and 111 . a flag bit is provided for each eight bits . the flag bit is set to zero if all eight bits in the group are zero . after run coding 28 the string of bits contains the flag bits and only those bit groups which contained at least one bit that was set in fig1 , the first group of eight bits 110 is not all zeros , so the flag bit 112 is set and the eight bits are retained in the output bit stream . the second group of eight 111 is all zeros . the output bit stream therefore contains only the flag bit 113 and none of the eight bits from the bit mask . the next bit in the output stream is the flag bit from the next group of eight . the detail component of the compressed data set , then , contains two parts the coded bit mask 29 just described , and an eight bit alpha / mask combination 26 for each cell in the image represented by a one in the bit mask 27 before coding . the image decompression algorithms are shown in fig2 ( a - e ). a total of five different levels of decompression are described . each of these is described below , building on the simpler ones . fig2 a is the simplest algorithm and will typically be executed on low performance computers . this algorithm uses only the base component of the compressed image data set . referring to fig2 a , the y , u , and v components , 25 , 23 , and 24 , are processed during decompression in the same manner as each other . in the compressed image data set , each component is stored in a run encoded format . the first step in the decompression algorithm is to expand the data to a string of huffman coded differential sample values . in fig2 a , this is done by run decode blocks 200 , 201 , and 202 . each of the y , u , and v components is parsed as a serial bit stream . a flag bit at the beginning of each 16 sample values indicates whether all the sample values in the group were coded as two bit huffman codes . if the flag bit is one , the run encoded sample value group contains only one bit for each sample indicating , for each sample , which of the two valid 2 - bit huffman codes defines that particular sample . in this case , the run decoding and huffman decoding is implemented as a single operation . a functional representation of this operation is shown in fig1 . referring to fig1 , the 16 bit code from the one of the y , u , v components 23 , 24 and 25 , is loaded into shift register 300 . the code is shifted out of the register 300 and the serial output 301 is used to select a + 3 if the bit was a zero , or a - 4 if the bit was a one using the multiplexor 302 . these values are the quantized predictor error values which are represented by huffman codes 01 and 11 respectively . the selected value 303 is the huffman decoded value for the sample differential . if the flag bit for the sixteen codes is zero , this indicates that the block of sixteen codes had at least one code that was not a two bit huffman code . in this case , the full huffman code is contained in the code stream and must be decoded . the run decoder simply strips off the flag bit and passes the codes to the huffman decoder . the huffman decoders , 206 , 207 and 208 , convert the huffman codes to sample differentials . in the preferred embodiment , this is done with a table look - up . referring to fig1 , the huffman codes 203 , 204 and 205 , are shifted into their respective shift registers to allow the next eight bits to be used as an index 340 to a table 341 . the table contains the sample differential 303 and the length of the huffman code 342 . this code length is used to advance the bit pointer to the next valid code . the next step is calculating the sample value from the differential which is accomplished by the dpcm decode functions 209 , 210 and 211 in fig2 . the functional representation of this simple step is shown in fig1 . the differential 303 is added to the previous sample value 305 to generate the new value for one of the three color components 203 , 204 and 205 . the chrominance components , u and v are at half of the horizontal resolution of the luminance component . in this simplest decoding method , the u and v components are pixel replicated in the horizontal direction 217 and 218 by using each value from the dpcm decode for two horizontally contiguous pixels in the output image . in the preferred embodiment , a new image is not actually formed . instead , each u and v component sample is used twice for the next stage in the decompression algorithm , which for this decoding method is the yuv to rgb conversion . the y , u , and v components 214 , 212 and 213 respectively , are transformed in to rgb by using an inverse transform 215 from the one used to transform to yuv , 2 in the compression algorithm . an example of such a transformation is shown by the equation below . ## equ4 ## however , since this conventional transformation requires a significant number of multiples per pixel , the transformation described in copending u . s . patent application ( filed herewith ) is substantially more efficient and preferred . since this decompression algorithm may also be used to decompress color image data to another color space , such as directly to yuv , the above described color space transformation 215 may not be necessary . further , a totally different color space transformation could be used in lieu of 215 to transform from yuv or another color space with chrominance and luminance components to an arbitrary color space . this statement also applies to the remainder of the decompression algorithms described below . the yuv to rgb transformation produces a decompressed image that has half of the resolution in both the horizontal and vertical axes from the original . this decompression algorithm may be appropriate for implementation on an inexpensive low end personal computers and low cost consumer products . another decompression algorithm is shown in fig2 b . this algorithm produces an image at the full resolution of the original image . this algorithm follows the same steps as the previous decompression algorithm shown in fig2 a , but has added pixel replication stages 240 , 241 and 242 before the yuv to rgb transformation . this stage replicates the yuv components in both the horizontal and vertical direction . this algorithm requires slightly more computational power than the algorithm shown in fig2 a , and therefore is more appropriate for personal computers and consumer products which have slightly higher computational power , or where the additional image size is important . this added pixel replication stage can be placed after the yuv to rgb conversion as well . this would reduce the number of color space transformations that would need to be done . however , in some preferred embodiments , the yuv information is converted directly to a color index for a pseudo - color frame buffer ( as described in copending u . s . patent application , filed herewith ) instead of being converted to rgb . in this case , the pixel replication must be accomplished in yuv color space . the decompression algorithm shown in fig2 c provides improved image quality over the previously described algorithm shown in fig2 b . in fig2 c , the pixel replication steps 217 , 218 , 240 , 241 and 242 , are replaced with pixel interpolation steps 223 , 224 , 243 , 244 and 245 . this reduces the blockiness in the resulting image by calculating the value of the inserted pixels by interpolating between neighboring pixels . in function blocks 223 and 224 , two pixels are generated for each input pixel along the scan line for the u and v components . the value assigned the new pixel is equal to the average of the two neighboring pixels . the last pixel on the scan line is treated as a special case and is assigned the same value as the last input pixel . fig1 provides a functional representation of the interpolation . for each pixel in the input stream 310 p 0 , p 1 , etc ., two pixels are generated in the output stream 311 p &# 39 ; 0 , p &# 34 ; 0 , p &# 39 ; 1 , p &# 34 ; 1 . referring to fig1 , p &# 39 ; 0 317 is assigned the same value as p 0 312 . the next pixel , p &# 34 ; 0 318 , is generated by averaging p 0 312 and its neighbor p 1 313 . the average is calculated by adding the values using add operation 315 and dividing the result by two 316 . as shown in fig1 , the remaining pixel values are calculated in a like manner except for the last pixel 321 . this last pixel , p &# 34 ; n 321 , is simply assigned the value of the last input pixel p n 314 . referring to fig2 c , the 2 × 2 pixel interpolated replication 243 , 244 and 245 is performed in the same manner as the scan line replication , except that it is done in two passes . this is shown in fig1 . referring to fig1 , the pixels along each scan line are interpolated 256 to double the horizontal resolution . this new image , 253 , 254 and 255 is interpolated again and pixel replicated using the same algorithm as shown in fig1 , but now in the vertical direction 257 . the resulting image 260 , 261 and 262 is now at the same resolution as original image before compression . this new image can now be transformed to rgb 215 as described for the previous decompression algorithms . this algorithm requires somewhat more computational power than the previous algorithms , but results in a higher quality image at the original image size . this approach may be applicable to so called mid range personal computers and consumer products . the decompression algorithm described in fig2 d results in higher quality image reconstruction , particularly if the original image contained significant high frequency information . this algorithm is essentially the same as the algorithm described by fig2 b , except that the y component is improved by adding in detail information contained in the detail component of the compressed image data set . referring to fig2 b , the output of the 2 × 2 pixel replicate of the y component 222 is used directly in the yuv to rgb color space transformation 215 . referring to fig2 d , this algorithm is modified by adding a step in the y image computation referred to as add alpha 232 . this will be described below . the detail component consists of two parts , an array of bytes which describe the alpha component and mask for some of the 2 × 2 pixel cells in the image 26 , and a run coded bit mask which indicates for which cells in the image the alpha and mask information is provided 29 . as described as part of the compression algorithm , the run coded bit map 29 has groups containing a one bit flag , and either zero or eight bits of bit map information . if the flag is zero , the eight bits were zero in the original uncompressed bit map and are not included in the coded bit map . if the flag is one , the eight bits are provided . fig1 shows the coding process to generate the run coded bit mask . the decoding process is simply the reverse . referring the fig2 d , the decoded bit map 231 contains one bit for each 2 × 2 pixel cell in the reconstructed image . this can be better understood by referring back to the description of the compression algorithm and the explanation of the creation of the detail component . fig1 provides an example of the how the pixels in the image are grouped into 2 × 2 pixel cells . for each bit in the decoded bit mask that is a one , the alpha / mask array contains additional detail information for the corresponding cell . each entry in the alpha / mask array has eight bits . four of these bits define a mask which indicates whether the original pixel value was greater or less than the mean of the four pixels that make up the cell . during decompression , this mask is used to determine whether the y component for each pixel should be increased or decreased . the amount of increase or decrease is determined by the number of pixels above and below the mean ( determined by the mask ) and the alpha value which is contained in the other four bits of the alpha / mask array entry . as previously described , alpha is a quantized approximation of the variance of the four pixels . fig1 describes the add alpha block 232 in fig2 d . referring to fig1 , the alpha / mask byte is used as the index into a table , which contains the two offsets to be added to the average for the cell 332 to generate the four output pixel luminance components 265 . for example , for the first pixel p 0 in 265 the mux 333 selects table output 335 if the mask bit in 331 indicates that the original value of the pixel was less than the average value for the cell , and selects 336 if otherwise . the selected value is then added to the average for the cell by 334 . since the base value for the four pixels in the cell are the same , the diagram in fig1 shows only one input 332 instead of separate inputs for the four pixels 222 as is indicated in fig2 d . the pixel replication is actually performed by adding four values to the average 332 . however , the final result is the same whether the pixel replication is done first or during the add alpha operation . the data for the look - up table 330 is derived from the following equations . there are two outputs of the table , designated a and b in the equations . a is selected if the mask bit indicates that the original luminance value for the pixel was less than the average for the cell . b is selected otherwise . in these equations , q is equal to the number of mask bits set . these equations improve the accuracy of the detail component . if three pixels are on one side of the average and the fourth is on the other side , the three pixels will be three times closer to the average than the fourth . the result of adding in the detail component is a significant improvement in the accuracy of the high frequency information in the image . this is particularly important for images with a lot of sharp edges . however , since this algorithm uses more computational resources than the previous algorithms , it is more appropriately used on high performance personal computers and consumer products . this is the final decompression algorithm described , and it provides the highest image quality , but requires the highest computational resources . this algorithm is described by fig2 e . this algorithm is a combination of the algorithm described by fig2 c and fig2 d . this decompression algorithm can be understood by looking at the diagram in fig2 e and reviewing the discussion of the algorithms described by fig2 c and 2d . as with the change from the algorithm described by fig2 b to the one described by fig2 c , the pixel replication steps in the algorithm described by fig2 d are replaced by pixel interpolation steps . the add alpha block 232 in fig2 e performs the same function as in fig2 e , although the description in fig1 is slightly different . fig1 assumes that the base component pixel value for the four pixels was the same and showed only one pixel input 332 . in this algorithm , the pixel values for the four pixels are different . in this case , the add alpha block 232 simply adds the selected output from the look - up table 330 to each of the four luminance values from the base pixel array 262 . although the operations required to implement these algorithms have been represented as independent functional blocks , these operations can also be accomplished in a sequential manner on a commodity microprocessor such as those found in low cost desk top personal computers . further , these operations can be implemented in specialized hardware and performed in a parallel or pipelined fashion if very high performance is required . additionally , these algorithms can be implemented by performing each operation on the entire image before the next operation , or by performing all operations on each pixel before the next pixel , or some combination . lastly , the y , u , and v components can be processed together , or one at a time . while the foregoing invention has been described with reference to its preferred embodiments , various modifications and alterations will occur to those skilled in the art . all such modifications and alterations are intended to fall within the scope of the appended claims .