RLGR Entropy Coder

We have developed an efficient entropy coder for integer value data. We refer to this compression algorithm as a Run-Length Golomb-Rice (RLGR) coder. The RLGR coder is very simple to implement, and uses backward adaptation of just a few parameters, based on previously-encoded symbols. That way, the RLGR (opens in new tab)encoder can quickly adapt to the statistics of the symbol source without any overhead of transmitting parameters associated with an estimated probability distribution function for the source symbols.

Our DCC 2006 paper shows that, in the limit of a near-stationary source, the RLGR encoder is nearly optimal (typically within 10%), for a wide range of sources in the class of generalized Gaussians (opens in new tab), which can model source from broadly wide PDFs, such as near uniform, to highly concentrated PDFs, such as Laplacians.

In many practical applications the symbol source is neither stationary nor ergodic, in some cases with rapid changes in local statistics, so the RLGR encoder can outperform other entropy encoders, such as modern adaptive arithmetic encoders.

The RLGR coder is used as the entropy encoder for our PTC image encoder. It is also used by the Windows Remote Desktop Protocol since Windows 7 SP1, as part of the RemoteFX (opens in new tab) protocol.