FELICS

Last updated

FELICS, which stands for Fast Efficient & Lossless Image Compression System, is a lossless image compression algorithm that performs 5-times faster than the original lossless JPEG codec and achieves a similar compression ratio. [1]

Contents

History

It was invented by Paul G. Howard and Jeffrey S. Vitter of the Department of Computer Science at Brown University in Providence, Rhode Island, USA, and was first presented at the 1993 IEEE Data Compression Conference in Snowbird, Utah. It was successfully implemented in hardware and deployed as part of HiRISE on the Mars Reconnaissance Orbiter. [2]

Principle

Pixel prediction neighborhoods. Pixel-prediction.svg
Pixel prediction neighborhoods.

Like other lossless codecs for continuous-tone images, FELICS operates by decorrelating the image and encoding it with an entropy coder. The decorrelation is the context where and where are the pixel's two nearest neighbors (causal, already coded and known at the decoder) used for providing the context to code the present pixel . Except at the top and left edges, these are the pixel above and the pixel to the left. For example, the neighbors of pixel X in the diagram are A and B, but if X were at the left side, its neighbors would be B and D.

P lies within the closed interval [L, H] roughly half the time. Otherwise, it is above H or below L. These can be encoded as 1, 01, and 00 respectively (p. 4). The following figure shows the (idealized) histogram of the pixels and their intensity values along the x-axis, and frequency of occurrence along the y-axis. FELICS predictor.png

The distribution of P within the range [L, H] is nearly uniform with a minor peak near the center of this range. When P falls in the range [L, H], P L is encoded using an adjusted binary code such that values in the center of the range use floor(log2(Δ + 1)) bits and values at the ends use ceil (log2(Δ + 1)) bits (p. 2). For example, when Δ = 11, the codes for P L in 0 to 11 may be 0000, 0001, 0010, 0011, 010, 011, 100, 101, 1100, 1101, 1110, 1111.

Outside the range, P tends to follow a geometric distribution on each side (p. 3). It is encoded using a Rice code with parameters chosen based on previous choices. For each Δ and each possible Rice code parameter k, the algorithm keeps track of the total number of bits that would have been used to encode pixels outside the range. Then for each pixel, it chooses the Rice code with the based on Δ at the pixel.

Improvements

FELICS improvements include methods for estimating Δ and estimating k. For instance, Howard and Vitter's article recognizes that relatively flat areas (with small Δ, especially where L = H) may have some noise, and compression performance in these areas improves by widening the interval, increasing the effective Δ. It is also possible to estimate the optimal k for a given Δ based on the mean of all prediction residues seen so far, which is faster and uses less memory than computing the number of bits used for each k.

See also

Related Research Articles

In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression reduces bits by identifying and eliminating statistical redundancy. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information. Typically, a device that performs data compression is referred to as an encoder, and one that performs the reversal of the process (decompression) as a decoder.

<span class="mw-page-title-main">JPEG</span> Lossy compression method for reducing the size of digital images

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.

<span class="mw-page-title-main">Lossy compression</span> Data compression approach that reduces data size while discarding or changing some of it

In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size for storing, handling, and transmitting content. The different versions of the photo of the cat on this page show how higher degrees of approximation create coarser images as more details are removed. This is opposed to lossless data compression which does not degrade the data. The amount of data reduction possible using lossy compression is much higher than using lossless techniques.

Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy. By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates.

<span class="mw-page-title-main">Image compression</span> Reduction of image size to save storage and transmission costs

Image compression is a type of data compression applied to digital images, to reduce their cost for storage or transmission. Algorithms may take advantage of visual perception and the statistical properties of image data to provide superior results compared with generic data compression methods which are used for other digital data.

<span class="mw-page-title-main">Arithmetic coding</span> Form of entropy encoding used in data compression

Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic encoding, frequently used characters will be stored with fewer bits and not-so-frequently occurring characters will be stored with more bits, resulting in fewer bits used in total. Arithmetic coding differs from other forms of entropy encoding, such as Huffman coding, in that rather than separating the input into component symbols and replacing each with a code, arithmetic coding encodes the entire message into a single number, an arbitrary-precision fraction q, where 0.0 ≤ q < 1.0. It represents the current information as a range, defined by two numbers. A recent family of entropy coders called asymmetric numeral systems allows for faster implementations thanks to directly operating on a single natural number representing the current information.

<span class="mw-page-title-main">JPEG 2000</span> Image compression standard and coding system

JPEG 2000 (JP2) is an image compression standard and coding system. It was developed from 1997 to 2000 by a Joint Photographic Experts Group committee chaired by Touradj Ebrahimi, with the intention of superseding their original JPEG standard, which is based on a discrete cosine transform (DCT), with a newly designed, wavelet-based method. The standardized filename extension is .jp2 for ISO/IEC 15444-1 conforming files and .jpx for the extended part-2 specifications, published as ISO/IEC 15444-2. The registered MIME types are defined in RFC 3745. For ISO/IEC 15444-1 it is image/jp2.

Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values.

Lossless JPEG is a 1993 addition to JPEG standard by the Joint Photographic Experts Group to enable lossless compression. However, the term may also be used to refer to all lossless compression schemes developed by the group, including JPEG 2000 and JPEG-LS.

JPEG XR is an image compression standard for continuous tone photographic images, based on the HD Photo specifications that Microsoft originally developed and patented. It supports both lossy and lossless compression, and is the preferred image format for Ecma-388 Open XML Paper Specification documents.

FFV1 is a lossless intra-frame video coding format. It can use either variable-length coding or arithmetic coding for entropy coding. The encoder and decoder are part of the free, open-source library libavcodec in the project FFmpeg since June 2003. FFV1 is also included in ffdshow and LAV Filters, which makes the video codec available to Microsoft Windows applications that support system-wide codecs over Video for Windows (VfW) or DirectShow. FFV1 is particularly popular for its performance regarding speed and size, compared to other lossless preservation codecs, such as M-JPEG2000. The European Broadcasting Union (EBU) lists FFV1 under the codec-family index "31" in their combined list of video codec references.

<span class="mw-page-title-main">Intra-frame coding</span>

Intra-frame coding is a data compression technique used within a video frame, enabling smaller file sizes and lower bitrates, with little or no loss in quality. Since neighboring pixels within an image are often very similar, rather than storing each pixel independently, the frame image is divided into blocks and the typically minor difference between each pixel can be encoded using fewer bits.

<span class="mw-page-title-main">Progressive Graphics File</span> File format

PGF is a wavelet-based bitmapped image format that employs lossless and lossy data compression. PGF was created to improve upon and replace the JPEG format. It was developed at the same time as JPEG 2000 but with a focus on speed over compression ratio.

<span class="mw-page-title-main">WebP</span> Image file format

WebP is a raster graphics file format developed by Google intended as a replacement for JPEG, PNG, and GIF file formats. It supports both lossy and lossless compression, as well as animation and alpha transparency.

A video coding format is a content representation format for storage or transmission of digital video content. It typically uses a standardized video compression algorithm, most commonly based on discrete cosine transform (DCT) coding and motion compensation. A specific software, firmware, or hardware implementation capable of compression or decompression to/from a specific video coding format is called a video codec.

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.

Display Stream Compression (DSC) is a VESA-developed video compression algorithm designed to enable increased display resolutions and frame rates over existing physical interfaces, and make devices smaller and lighter, with longer battery life. It is a low-latency algorithm based on delta PCM coding and YCGCO-R color space.

JPEG XL is a royalty-free raster-graphics file format that supports both lossy and lossless compression. It is designed to outperform existing raster formats and thus become their universal replacement.

JPEG XS is an interoperable, visually lossless, low-latency and lightweight image and video coding system used in professional applications. Applications of the standard include streaming high quality content for virtual reality, drones, autonomous vehicles using cameras, gaming, and broadcasting. In this respect, JPEG XS is unique, being the first ISO codec ever designed for this specific purpose. JPEG XS, built on core technology from both intoPIX and Fraunhofer IIS, is formally standardized as ISO/IEC 21122 by the Joint Photographic Experts Group with the first edition published in 2019. Although not official, the XS acronym was chosen to highlight the eXtra Small and eXtra Speed characteristics of the codec. Today, the JPEG committee is still actively working on further improvements to XS, with the second edition scheduled for publication and initial efforts being launched towards a third edition.

References

  1. P. G. Howard and J. S. Vitter, Fast and Efficient Lossless Image Compression, Proceedings of the 1993 IEEE Data Compression Conference (DCC '93), Snowbird, UT, April 1993, 351-360.
  2. A. S. McEwen, E. M. Eliason, J. W. Bergstrom, N. T. Bridges, C. J. Hansen, W. A. Delamere, J. A. Grant, V. C. Gulick, K. E. Herkenhoff, L. Keszthelyi, R. L. Kirk, M. T. Mellon, S. W. Squyres, N. Thomas, and C. M. Weitz, Mars Reconnaissance Orbiter's High Resolution Imaging Science Experiment (HiRISE), Journal of Geophysical Research, 112(E05S02), 2007, 40 pages.