# FELICS

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/FELICS
> Markdown URL: https://mediated.wiki/source/FELICS.md
> Source: https://en.wikipedia.org/wiki/FELICS
> Source revision: 1261413039
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Image compression algorithm

For other uses, see [Felix (disambiguation)](/source/Felix_(disambiguation)).

This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "FELICS" – news · newspapers · books · scholar · JSTOR (August 2011) (Learn how and when to remove this message)

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

## History

It was invented by Paul G. Howard and [Jeffrey S. Vitter](/source/Jeffrey_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](/source/HiRISE) on the Mars Reconnaissance Orbiter.[2]

## Principle

Pixel prediction neighborhoods.

Like other lossless codecs for continuous-tone images, FELICS operates by [decorrelating](/source/Decorrelation) the image and encoding it with an [entropy coder](/source/Entropy_encoding). The decorrelation is the context Δ = H − L {\displaystyle \Delta =H-L} where H = m a x ( P 1 , P 2 ) {\displaystyle H=max(P1,P2)} and L = m i n ( P 1 , P 2 ) {\displaystyle L=min(P1,P2)} where P 1 , P 2 {\displaystyle P1,P2} are the pixel's two nearest neighbors ([causal](/source/Causal), already coded and known at the decoder) used for providing the context to code the present pixel P {\displaystyle P} . 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.

The distribution of P within the range [L, H] is nearly uniform with a minor peak near the center ( L + H ) / 2 {\displaystyle (L+H)/2} of this range. When P falls in the range [L, H], P − L is encoded using an adjusted [binary code](/source/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](/source/Geometric_distribution) on each side (p. 3). It is encoded using a [Rice code](/source/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

- [JPEG-LS](/source/JPEG-LS)

- [PNG](/source/Portable_Network_Graphics)

- [Exif](/source/Exif) - [Exchangeable image file format](/source/Exchangeable_image_file_format)

- [GIMP](/source/GIMP)

- [Image compression](/source/Image_compression)

- [Image file formats](/source/Image_file_formats)

- [Comparison of graphics file formats](/source/Comparison_of_graphics_file_formats)

## References

1. **[^](#cite_ref-1)** P. G. Howard and J. S. Vitter, [Fast and Efficient Lossless Image Compression](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.2786), *Proceedings of the 1993 IEEE Data Compression Conference (DCC '93),* Snowbird, UT, April 1993, 351-360.

1. **[^](#cite_ref-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)](https://doi.org/10.1029/2005JE002605), *Journal of Geophysical Research*, 112(E05S02), 2007, 40 pages.

v t e Data compression methods Lossless type Entropy Adaptive coding Arithmetic Asymmetric numeral systems Golomb Huffman Adaptive Canonical Modified Range Shannon Shannon–Fano Shannon–Fano–Elias Tunstall Unary Universal Exp-Golomb Fibonacci Gamma Levenshtein Dictionary Byte-pair encoding Lempel–Ziv 842 LZ4 LZJB LZO LZRW LZSS LZW LZWL Snappy Other BWT CTW CM Delta Incremental DMC DPCM Grammar Re-Pair Sequitur LDCT MTF PAQ PPM RLE Hybrid LZ77 + Huffman Deflate LZX LZS LZ77 + ANS LZFSE LZ77 + Huffman + ANS Zstandard LZ77 + Huffman + context Brotli LZSS + Huffman LHA/LZH LZ77 + Range LZMA LZHAM RLE + BWT + MTF + Huffman bzip2 Lossy type Transform Discrete cosine transform DCT MDCT DST FFT Wavelet Daubechies DWT SPIHT Predictive DPCM ADPCM LPC ACELP CELP LAR LSP WLPC Motion Compensation Estimation Vector Psychoacoustic Audio Concepts Bit rate ABR CBR VBR Companding Convolution Dynamic range Latency Nyquist–Shannon theorem Sampling Silence compression Sound quality Speech coding Sub-band coding Codec parts A-law μ-law DPCM ADPCM DM FT FFT LPC ACELP CELP LAR LSP WLPC MDCT Psychoacoustic model Image Concepts Chroma subsampling Coding tree unit Color space Compression artifact Image resolution Macroblock Pixel PSNR Quantization Standard test image Texture compression Methods Chain code DCT Deflate Fractal KLT LP RLE Wavelet Daubechies DWT EZW SPIHT Video Concepts Bit rate ABR CBR VBR Display resolution Frame Frame rate Frame types Interlace Video characteristics Video quality Codec parts DCT DPCM Deblocking filter Lapped transform Motion Compensation Estimation Vector Wavelet Daubechies DWT Theory Compressed data structures Compressed suffix array FM-index Entropy Information theory Timeline Kolmogorov complexity Prefix code Quantization Rate–distortion Redundancy Symmetry Smallest grammar problem Community Hutter Prize People Mark Adler David A. Huffman Phil Katz

---
Adapted from the Wikipedia article [FELICS](https://en.wikipedia.org/wiki/FELICS) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/FELICS?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.