JPEG-LS Explained: Near-Lossless LOCO-I Compression

JPEG-LS is an international standard for lossless and near-lossless image compression based on the LOCO-I (Low Complexity Lossless Compression for Images) algorithm. Developed to bridge the gap between high-performance, computationally heavy algorithms and simpler, less efficient methods, JPEG-LS provides superior compression ratios while maintaining minimal computational overhead. This article explains the fundamentals of JPEG-LS, the core mechanisms of the LOCO-I algorithm, and precisely how it achieves controlled near-lossless compression.

What is JPEG-LS?

JPEG-LS (ISO/IEC 14495-1 / ITU-T Recommendation T.87) is specifically designed for continuous-tone still images, such as medical scans, satellite imagery, and high-fidelity photography. Unlike the traditional DCT-based lossy JPEG standard, JPEG-LS focuses on exact data preservation or strictly bounded reconstruction errors.

Unlike JPEG 2000, which relies on complex wavelet transforms and computationally expensive arithmetic coding, JPEG-LS utilizes a low-complexity framework that can be easily implemented in hardware and low-power devices without sacrificing compression performance.

The LOCO-I Algorithm

The engine behind JPEG-LS is LOCO-I, developed by Hewlett-Packard Laboratories. LOCO-I is designed around the premise that context-based predictive coding can approach the compression performance of much more complex methods if prediction and context modeling are handled effectively.

The algorithm operates in two primary modes:

  1. Regular Mode: Applied to standard, continuously varying image regions using predictive modeling and Golomb-Rice entropy coding.
  2. Run Mode: Applied to flat or low-entropy regions, switching to run-length coding to bypass prediction and accelerate processing.

How LOCO-I Achieves Near-Lossless Compression

Near-lossless compression in JPEG-LS means that every reconstructed pixel is guaranteed to differ from the original pixel by no more than a user-defined absolute error threshold, denoted as \(\delta\) (or NEAR). When \(\delta = 0\), the algorithm operates in pure lossless mode. When \(\delta > 0\), LOCO-I introduces controlled distortion to substantially reduce file size through a four-step pipeline.

1. Context Modeling and Prediction

To predict a target pixel \(x\), LOCO-I examines its causal neighbors (previously encoded adjacent pixels): left (\(a\)), above (\(b\)), and above-left (\(c\)).

It employs a Median Edge Detection (MED) predictor, also known as the LOCO-I predictor:

This simple non-linear predictor handles directional edges without complex matrix calculations.

2. Error Calculation and Quantization

In strictly lossless mode, the prediction error is simply \(e = x - \hat{x}\).

In near-lossless mode (\(\delta > 0\)), the error must be quantized so that the reconstructed value satisfies \(|x - x_{rec}| \le \delta\). The prediction error \(e\) is quantized into a quantized error \(Q(e)\) using uniform scalar quantization:

\[Q(e) = \left\lfloor \frac{e + \delta}{2\delta + 1} \right\rfloor\]

The dequantized prediction error \(\tilde{e}\) used for reconstructing the pixel is:

\[\tilde{e} = Q(e) \times (2\delta + 1)\]

The reconstructed pixel value is then clamped to the valid sample range:

\[x_{rec} = \text{clamp}(\hat{x} + \tilde{e})\]

Crucially, both the encoder and the decoder update their internal state using \(x_{rec}\) rather than the original pixel \(x\). This ensures that both sides remain strictly synchronized without drift.

3. Context-Dependent Bias Correction

Local gradients around pixel \(x\) determine the "context" of the prediction. LOCO-I tracks average prediction errors within each context. If a context exhibits a systematic bias (an average error consistently above or below zero), the algorithm dynamically offsets \(\hat{x}\) before computing the error. This adaptively removes residual correlation from the prediction step.

4. Golomb-Rice Entropy Coding

After quantization and bias correction, the non-negative mapped error values are encoded using Golomb-Rice coding. LOCO-I dynamically estimates the optimal Golomb parameter \(k\) for each context on the fly, eliminating the need for multi-pass statistical analysis. Because Golomb-Rice codes represent values using simple bit-shifts and unary prefixes, this step requires minimal CPU cycles compared to binary arithmetic coding while still yielding near-optimal entropy limits.

Advantages of JPEG-LS Near-Lossless Mode