Color Cell Compression

Last updated February 14, 2022

Color Cell Compression is a lossy image compression algorithm developed by Campbell et al.,^[1]^[2]^[3] in 1986, which can be considered an early forerunner of modern texture compression algorithms, such as S3 Texture Compression and Adaptive Scalable Texture Compression. It is closely related to Block Truncation Coding,^[4] another lossy image compression algorithm, which predates Color Cell Compression, in that it uses the dominant luminance of a block of pixels to partition said pixels into two representative colors. The primary difference between Block Truncation Coding and Color Cell Compression is that the former was designed to compress grayscale images and the latter was designed to compress color images. Also, Block Truncation Coding requires that the standard deviation of the colors of pixels in a block be computed in order to compress an image, whereas Color Cell Compression does not use the standard deviation. Both algorithms, though, can compress an image down to effectively 2 bits per pixel.

Algorithm

Compression

The Color Cell Compression algorithm processes an image in eight steps, although one of the steps (step #6) is optional. It is assumed here that the input is a 24 bits/pixel image, as assumed in the original journal article, although other bit depths could be used.

For each 8-bit RGB octet triple contained in each 24-bit color value in the input image, the NTSC luminance ${\textstyle y}$ is computed using the following formula:^[1]^[2]^[3] $y=0.30\times red+0.59\times green+0.11\times blue$
The image is now subdivided into 4-pixel by 4-pixel blocks, and, the arithmetic mean of the luminance of each pixel in the block is used to select a representative luminance value.^[1]^[2]^[3]
Each block of pixels is then divided into two groups. One group consists of pixels in the current block where each pixel's luminance is greater than or equal to the representative luminance for the current block. The second group of pixels consists of pixels in the current block where each pixel's luminance is less than the representative luminance for the current block. Whether a pixel in the current block belongs to a certain group is determined by a binary "0" or a "1" value in another, separate, 16-entry bitmap.^[1]^[2]^[3]
Two representative 24-bit colors are now selected for each block of pixels by computing two arithmetic means. The first arithmetic mean is the arithmetic mean of all of the pixels belonging to the first group of pixels where the luminance of each pixel is a "1" in the luminance bitmap. The second 24-bit representative color is selected similarly, by taking the arithmetic mean of all the 24-bit color pixels in the second group where each pixel corresponds to a "0" in the luminance bitmap.^[1]^[2]^[3]
The luminance bitmap is stored in a temporary location and then the two 24-bit representative colors for the current block are appended to the bitmap. At this stage, the image has been compressed into a 16-entry bitmap with two 24-bit binary values appended. The total size of the compressed block is now 16 bits for the luminance bitmap, and two 24-bit binary quantities for each representative color, yielding a total size of 64 bits, which, when divided by 16 (the number of pixels in the block), yields 4 i.e. 4 bits per pixel.^[1]^[2]^[3]
Each compressed block of pixels is modified by truncating each of the two 24-bit representative colors to 15 bits. This step is optional, and the algorithm can terminate at this point, if desired, as the compressed blocks at this stage have a total size of ${\textstyle 16+2\times 15=46}$ bits, which, when divided by 16, yields 2.875 bits per pixel. If this step is performed, then the 15-bit truncated color values can be used in the next step to create a smaller histogram. Also, since each 15-bit binary color vector is presumably stored in a 16-bit word, then the 16th bit can be used to improve the image quality by specifying which one of two lookup tables should be used.^[1]^[2]^[3]
A histogram of all the 24-bit colors in the original 24-bit color image, or the truncated 15-bit color vectors, is created. In a naïve implementation, the histogram is consulted to choose 256 of the most frequently used colors which are then put into a 256-entry array, where each entry consists of three octets of a 24-bit per pixel color value. The histogram method of selecting the most appropriate colors for the original 24-bit per pixel color image can instead be replaced by a vector quantization class algorithm such as the median cut algorithm or K-means clustering ^{[ citation needed ]} which usually yields better results.^[1]^[2]^[3]
The final step consists of taking the current block of pixels and determining which 24-bit per pixel color in the 256-entry lookup table most closely match the two representative colors for each block. The two 8-bit indices pointing to colors in the lookup table are now appended to the 16-bit luminance bitmap. This yields a total compressed size of ${\textstyle 16+8+8=32}$ bits, which, when divided by 16, yields 2 bits per pixel.^[1]^[2]^[3]

Decompression

Decompression is very easy and straightforward. To reconstruct each compressed 4-pixel by 4-pixel block, the 16-bit luminance bitmap is consulted for each block. Depending on whether an element of the bitmap is 1 or 0, one of the two 8-bit indices into the lookup table is selected and then dereferenced and the corresponding 24-bit per pixel color value is retrieved.^[1]^[2]^[3]

Performance and image quality

In spite of its very simple mechanism, the algorithm yields surprisingly good results on photographic images,^[1]^[2]^[3] and it has the advantage of being very fast to decode with limited hardware. Although far surpassed in compression ratio by later block-transform coding methods such as JPEG, it has the advantage of very simple decompression and fast random access into the compressed image.

Apple Video (RPZA) and S3 Texture Compression employ the same principle of encoding 4×4-pixel blocks based on two representative colors. They refine CCC by expanding each entry in the luminance bitmap to two bits, where the additional two values represent a weighted average: one-third of one color and two-thirds of the other. To work around S3's patent, the Super Simple Texture Compression (S2TC) library was created to encode CCC data in a format compatible with S3TC decoders and to reinterpret S3TC as CCC with minor quality loss.

Related Research Articles

JPEG is a commonly used method of lossy compression for digital images, particularly for those images produced by digital photography. The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality. JPEG typically achieves 10:1 compression with little perceptible loss in image quality. Since its introduction in 1992, JPEG has been the most widely used image compression standard in the world, and the most widely used digital image format, with several billion JPEG images produced every day as of 2015.

Portable Network Graphics is a raster-graphics file format that supports lossless data compression. PNG was developed as an improved, non-patented replacement for Graphics Interchange Format (GIF) — unofficially, the initials PNG stood for the recursive acronym "PNG's not GIF".

PCX, standing for PiCture eXchange, is an image file format developed by the now-defunct ZSoft Corporation of Marietta, Georgia, United States. It was the native file format for PC Paintbrush and became one of the first widely accepted DOS imaging standards, although it has since been succeeded by more sophisticated image formats, such as BMP, JPEG, and PNG. PCX files commonly stored palette-indexed images ranging from 2 or 4 colors to 16 and 256 colors, although the format has been extended to record true-color (24-bit) images as well.

Raster graphics Matrix-based data structure

In computer graphics and digital photography, a raster graphic is a mechanism that represents a two-dimensional image as a rectangular matrix or grid of square pixels, viewable via a computer display, paper, or other display medium. A raster is technically characterized by the width and height of the image in pixels and by the number of bits per pixel. Raster images are stored in image files with varying dissemination, production, generation, and acquisition formats.

Halftone is the reprographic technique that simulates continuous-tone imagery through the use of dots, varying either in size or in spacing, thus generating a gradient-like effect. "Halftone" can also be used to refer specifically to the image that is produced by this process.

The BMP file format, also known as bitmap image file, device independent bitmap (DIB) file format and bitmap, is a raster graphics image file format used to store bitmap digital images, independently of the display device, especially on Microsoft Windows and OS/2 operating systems.

In digital photography, computer-generated imagery, and colorimetry, a grayscale image is one in which the value of each pixel is a single sample representing only an amount of light; that is, it carries only intensity information. Grayscale images, a kind of black-and-white or gray monochrome, are composed exclusively of shades of gray. The contrast ranges from black at the weakest intensity to white at the strongest.

In image processing and photography, a color histogram is a representation of the distribution of colors in an image. For digital images, a color histogram represents the number of pixels that have colors in each of a fixed list of color ranges, that span the image's color space, the set of all possible colors.

Smacker video is a video file format developed by RAD Game Tools, and primarily used for full-motion video in video games. Smacker uses an adaptive 8-bit RGB palette. RAD's format for video at higher color depths is Bink Video. The Smacker format specifies a container format, a video compression format, and an audio compression format. Since its release in 1994, Smacker has been used in over 2300 games. Blizzard used this format for the cinematic videos seen in its games Warcraft II, StarCraft and Diablo I.

S3 Texture Compression (S3TC) is a group of related lossy texture compression algorithms originally developed by Iourcha et al. of S3 Graphics, Ltd. for use in their Savage 3D computer graphics accelerator. The method of compression is strikingly similar to the previously published Color Cell Compression, which is in turn an adaptation of Block Truncation Coding published in the late 1970s. Unlike some image compression algorithms, S3TC's fixed-rate data compression coupled with the single memory access made it well-suited for use in compressing textures in hardware-accelerated 3D computer graphics. Its subsequent inclusion in Microsoft's DirectX 6.0 and OpenGL 1.3 led to widespread adoption of the technology among hardware and software makers. While S3 Graphics is no longer a competitor in the graphics accelerator market, license fees have been levied and collected for the use of S3TC technology until October 2017, for example in game consoles and graphics cards. The wide use of S3TC has led to a de facto requirement for OpenGL drivers to support it, but the patent-encumbered status of S3TC presented a major obstacle to open source implementations, while implementation approaches which tried to avoid the patented parts existed.

FXT1 is a texture compression scheme for 3D graphics, invented by the hardware vendor 3dfx Interactive and offered as an open source rival standard to S3TC in September 1999, a year after S3TC had been adopted by Microsoft as part of DirectX. Limited vendor hardware support has been a barrier to its acceptance. Notably, despite being open source, FXT1 was not adopted by Nintendo for the GameCube, nor by Sony for the PlayStation 3, in both cases losing out to the established S3TC standard. Another possible reason for its lack of adoption is that the CC_MIXED mode probably infringes the S3TC patent.

The ICO file format is an image file format for computer icons in Microsoft Windows. ICO files contain one or more small images at multiple sizes and color depths, such that they may be scaled appropriately. In Windows, all executables that display an icon to the user, on the desktop, in the Start Menu, or in Windows Explorer, must carry the icon in ICO format.

Image file formats are standardized means of organizing and storing digital images. An image file format may store data in an uncompressed format, a compressed format, or a vector format. Image files are composed of digital data in one of these formats so that the data can be rasterized for use on a computer display or printer. Rasterization converts the image data into a grid of pixels. Each pixel has a number of bits to designate its color. Rasterizing an image file for a specific device takes into account the number of bits per pixel that the device is designed to handle.

Microsoft Video 1 or MS-CRAM is an early lossy video compression and decompression algorithm (codec) that was released with version 1.0 of Microsoft's Video for Windows in November 1992. It is based on MotiVE, a vector quantization codec which Microsoft licensed from Media Vision. In 1993, Media Vision marketed the Pro Movie Spectrum, an ISA board that captured video in both raw and MSV1 formats.

Block Truncation Coding (BTC) is a type of lossy image compression technique for greyscale images. It divides the original images into blocks and then uses a quantizer to reduce the number of grey levels in each block whilst maintaining the same mean and standard deviation. It is an early predecessor of the popular hardware DXTC technique, although BTC compression method was first adapted to color long before DXTC using a very similar approach called Color Cell Compression. BTC has also been adapted to video compression.

In computer graphics, color quantization or color image quantization is quantization applied to color spaces; it is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as visually similar as possible to the original image. Computer algorithms to perform color quantization on bitmaps have been studied since the 1970s. Color quantization is critical for displaying images with many colors on devices that can only display a limited number of colors, usually due to memory limitations, and enables efficient compression of certain types of images.

In computing, a bitmap is a mapping from some domain to bits. It is also called a bit array or bitmap index.

Image editing Processes of altering images, digital or traditional photos, adding, pasting, cutting words

Image editing encompasses the processes of altering images, whether they are digital photographs, traditional photo-chemical photographs, or illustrations. Traditional analog image editing is known as photo retouching, using tools such as an airbrush to modify photographs or editing illustrations with any traditional art medium. Graphic software programs, which can be broadly grouped into vector graphics editors, raster graphics editors, and 3D modelers, are the primary tools with which a user may manipulate, enhance, and transform images. Many image editing programs are also used to render or create computer art from scratch.

Apple Video is a lossy video compression and decompression algorithm (codec) developed by Apple Inc. and first released as part of QuickTime 1.0 in 1991. The codec is also known as QuickTime Video, by its FourCC RPZA and the name Road Pizza. When used in the AVI container, the FourCC AZPR is also used.

QuickTime Graphics is a lossy video compression and decompression algorithm (codec) developed by Apple Inc. and first released as part of QuickTime 1.x in the early 1990s. The codec is also known by the name Apple Graphics and its FourCC SMC. The codec operates on 8-bit palettized RGB data. The bit-stream format of QuickTime Graphics has been reverse-engineered and a decoder has been implemented in the projects XAnim and libavcodec.

References

1 2 3 4 5 6 7 8 9 10 11 Campbell, G.; Defanti, T. A.; Frederiksen, J.; Joyce, S. A.; Leske, L. A. (1986). "Two bit/pixel full color encoding". Proceedings of the 13th annual conference on Computer graphics and interactive techniques - SIGGRAPH '86. p. 215. doi:10.1145/15922.15910. ISBN 978-0-89791-196-2.
1 2 3 4 5 6 7 8 9 10 11 Pins, Markus (1991). Extensions of the Color-Cell-Compression-Algorithm. Computer Animation '91. pp. 241–251. doi:10.1007/978-4-431-66890-9_17. ISBN 978-4-431-66892-3.
1 2 3 4 5 6 7 8 9 10 11 Lamparter, Bernd Effelsberg, Wolfgang (June 2005). eXtended Color Cell Compression : A Runtime-efficient Compression Scheme for Software Video. Multimedia: Advanced Teleservices and High-Speed Communication Architectures. Lecture Notes in Computer Science. Vol. 868. pp. 181–190. doi:10.1007/3-540-58494-3_16. ISBN 978-3-540-58494-0.{{cite book}}: CS1 maint: multiple names: authors list (link)^{[ permanent dead link ]}
↑ Wennersten, P.; Ström, J. (2009). "Table-based Alpha Compression" (PDF). Computer Graphics Forum. 28 (2): 687. doi:10.1111/j.1467-8659.2009.01409.x.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[ccc-1] 1 2 3 4 5 6 7 8 9 10 11 Campbell, G.; Defanti, T. A.; Frederiksen, J.; Joyce, S. A.; Leske, L. A. (1986). "Two bit/pixel full color encoding". Proceedings of the 13th annual conference on Computer graphics and interactive techniques - SIGGRAPH '86. p. 215. doi:10.1145/15922.15910. ISBN 978-0-89791-196-2.

[ccc2-2] 1 2 3 4 5 6 7 8 9 10 11 Pins, Markus (1991). Extensions of the Color-Cell-Compression-Algorithm. Computer Animation '91. pp. 241–251. doi:10.1007/978-4-431-66890-9_17. ISBN 978-4-431-66892-3.

[ccc3-3] 1 2 3 4 5 6 7 8 9 10 11 Lamparter, Bernd Effelsberg, Wolfgang (June 2005). eXtended Color Cell Compression : A Runtime-efficient Compression Scheme for Software Video. Multimedia: Advanced Teleservices and High-Speed Communication Architectures. Lecture Notes in Computer Science. Vol. 868. pp. 181–190. doi:10.1007/3-540-58494-3_16. ISBN 978-3-540-58494-0.{{cite book}}: CS1 maint: multiple names: authors list (link)^{[ permanent dead link ]}

[btc-4] Wennersten, P.; Ström, J. (2009). "Table-based Alpha Compression" (PDF). Computer Graphics Forum. 28 (2): 687. doi:10.1111/j.1467-8659.2009.01409.x.

[1]

[2]

[3]

[4]