FELICS
Encyclopedia
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
.
of the Brown University & Duke University in USA, and presented at the DCC
in Snowbird, Utah
in 1993.
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.
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.
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.
Lossless data compression
Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be reconstructed, in exchange...
image compression
Image compression
The objective of image compression is to reduce irrelevance and redundancy of the image data in order to be able to store or transmit data in an efficient form.- Lossy and lossless compression :...
algorithm
that performs 5-times faster than the original lossless JPEG codec and achieves a similar compression ratio
Data compression ratio
Data compression ratio, also known as compression power, is a computer-science term used to quantify the reduction in data-representation size produced by a data compression algorithm...
.
History
It was invented by P. G. Howard & J. S. Vitter of the computer science departmentof the Brown University & Duke University in USA, and presented at the DCC
in Snowbird, Utah
Snowbird, Utah
Snowbird is an unincorporated area based in Little Cottonwood Canyon in the Wasatch Range of the Rocky Mountains in Salt Lake County, Utah, U.S. It is most famous for Snowbird Ski and Summer Resort, an alpine skiing and snowboarding area, which opened in December 1971.- History :Snowbird is a...
in 1993.
Principle
Like other lossless codecs for continuous-tone images, FELICS operates by decorrelatingDecorrelation
Decorrelation is a general term for any process that is used to reduce autocorrelation within a signal, or cross-correlation within a set of signals, while preserving other aspects of the signal. A frequently used method of decorrelation is the use of a matched linear filter to reduce the...
the image and encoding it with an entropy coder
Entropy encoding
In information theory an entropy encoding is a lossless data compression scheme that is independent of the specific characteristics of the medium....
. 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 thepresent 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.
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
Binary code
A binary code is a way of representing text or computer processor instructions by the use of the binary number system's two-binary digits 0 and 1. This is accomplished by assigning a bit string to each particular symbol or instruction...
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
- JPEG-LSJPEG-LSLossless JPEG refers to a 1993 addition to JPEG standard by the Joint Photographic Experts Group to enable lossless compression. However, it might be used as an umbrella term to refer to all lossless compression schemes developed by the Joint Photographic Expert group...
- PNG
- Exif - Exchangeable image file formatExchangeable image file formatExchangeable image file format is a standard that specifies the formats for images, sound, and ancillary tags used by digital cameras , scanners and other systems handling image and sound files recorded by digital cameras...
- Context Adaptive Lossless Image Codec
- GIMPGIMPGIMP is a free software raster graphics editor. It is primarily employed as an image retouching and editing tool and is freely available in versions tailored for most popular operating systems including Microsoft Windows, Apple Mac OS X, and Linux.In addition to detailed image retouching and...
- Image compressionImage compressionThe objective of image compression is to reduce irrelevance and redundancy of the image data in order to be able to store or transmit data in an efficient form.- Lossy and lossless compression :...
- Image file formatsImage file formatsImage file formats are standardized means of organizing and storing digital images. Image files are composed of either pixels, vector data, or a combination of the two. Whatever the format, the files are rasterized to pixels when displayed on most graphic displays...
- Comparison of graphics file formatsComparison of graphics file formats-General:Ownership of the format and related information.-Technical details:...