Contents

Intro

• LOCO-I [1] (LOw COmplexity, context-based, lossless Image compression algorithm), also named JPEG-LS (Joint Photographic Expert Group - LosslesS), is a lossless stil image codec based on context-based predictive coding and Golomb Coding.
• Developed by HP, that only offers the executable code in: http://www.hpl.hp.com/loco/locodown.htm

1 Encoder

1. Initialization of the prediction contexts:
   1. Let $Q$ the actual context (there are $1094$ different spatial contexts).
   2. Let $N\left[Q\right]$ the number of times that the context $Q$ has been found.
   3. Let $B\left[Q\right]$ the accumulated prediction error for the context $Q$.
   4. Let $A[Q$ the sumatory of the absolute value of the prediction residues for the context $Q$.
   5. Let $C\left[Q\right]$ the the bias cancellation values for the context $Q$. These values are added to the predictions to try that the predictions residues have a zero average. If this is not satisfied, the compression ratio in reduced severelly because the average of the real Lapace probability distribution of the residues and the modeled probability distribution does not match. For this reason, $C\left[Q\right]$ is proportional to $B\left[Q\right]∕N\left[Q\right]$ that added to the predictions, cancel the bias.
2. Determination of the prediction context $\mathcal{𝒬}$:
   1. Compute the local gradient:
      
      $$\begin{array}{ccc}\hfill g_1& \hfill \leftarrow \hfill & d-a\hfill \\ \hfill g_2& \hfill \leftarrow \hfill & a-c\hfill \\ \hfill g_3& \hfill \leftarrow \hfill & c-b\hfill \\ \hfill g_4& \hfill \leftarrow \hfill & b-e\hfill \end{array}$$

   2. Quantize the gradients:
      $$q_i\leftarrow \left\{\begin{array}{cc}0\hfill & \text{if }{g}_i=0\hfill \\ 1\hfill & \text{if }1\le \left|g_i\right|\le 2\hfill \\ 2\hfill & \text{if }3\le \left|g_i\right|\le 6\hfill \\ 3\hfill & \text{if }7\le \left|g_i\right|\le 14\hfill \\ 4\hfill & \text{otherwise}\hfill \end{array}\right.$$

      for $i=1,2,3$ and

      $$q_4\leftarrow \left\{\begin{array}{cc}0\hfill & \text{if }\left|g_4\right|<0\hfill \\ 1\hfill & \text{if }5\le g_4\hfill \\ 2\hfill & \text{otherwise}.\hfill \end{array}\right.$$

3. Compute the residue $M\left(e\right)$:
   1. The initial prediction:
      $$ŝ\leftarrow \left\{\begin{array}{cc}\text{min}\left(a,b\right)\hfill & \text{if }c\ge \text{max}\left(a,b\right)\hfill \\ \text{max}\left(a,b\right)\hfill & \text{if }c\le \text{min}\left(a,b\right)\hfill \\ a+b-c\hfill & \text{otherwise}.\hfill \end{array}\right.$$

   2. Bias cancellation:
      $$ŝ\leftarrow \left\{\begin{array}{cc}ŝ+C\left[Q\right]\hfill & \text{if }{g}_1>0\hfill \\ ŝ-C\left[Q\right]\hfill & \text{otherwise}.\hfill \end{array}\right.$$

   3. Compute the prediction error:
      $$e\leftarrow \left(s-ŝ\right)\text{ mod }\beta ,$$

      where $\beta$ is the number of bits/pixel. This produces a projection of the residues from the dynamic range $\left[-\alpha +1,\alpha -1\right]$ to $\left[-\alpha ∕2,\alpha ∕2-1\right]$, where $\alpha =2^{\beta }$ is the size of the source alphabet.

   4. Shuffle the residues in order to get an exponiential (with negative exponent) distribution of the probability of the residues:
      $$M\left(e\right)\leftarrow \left\{\begin{array}{cc}2e\hfill & \text{if }e\ge 0\hfill \\ 2\left|e\right|-1\hfill & \text{otherwise}.\hfill \end{array}\right.$$

      After that, the residues are in the range $\left[0,1,\cdots ,2^{\beta }-1\right]$

4. Variable length encoding of $M\left(e\right)$ in the context $Q$:
   1. Output $\leftarrow$ a Rice code for $M\left(e\right)$ using the slope $k=\lceil {log}_2\left(A\left[Q\right]\right)\rceil$.
5. Update the context $Q$:
   1. $B\left[Q\right]\leftarrow B\left[Q\right]+e$.
   2. $A\left[Q\right]\leftarrow A\left[Q\right]+\left|e\right|$.
   3. If $N\left[Q\right]=\mathsf{RESET}$, then: (where $64\le \mathsf{RESET}\le 256$)
      1. $A\left[Q\right]\leftarrow A\left[Q\right]∕2$.
      2. $B\left[Q\right]\leftarrow B\left[Q\right]∕2$.
      3. $H\left[Q\right]\leftarrow N\left[Q\right]∕2$.
   4. $N\left[Q\right]\leftarrow N\left[Q\right]+1$.
   5. Update of $C\left[Q\right]$:
      1. If $B\left[A\right]\le -N\left[Q\right]$, then:
         1. $B\left[Q\right]\leftarrow B\left[Q\right]+N\left[Q\right]$.
         2. If $C\left[Q\right]>-128$, then:
            • $C\left[Q\right]\leftarrow C\left[Q\right]-1$.
         3. If $B\left[Q\right]\le -N\left[Q\right]$, then:
            • $B\left[Q\right]\leftarrow -N\left[Q\right]+1$.
      2. Else:
         1. If $B\left[Q\right]>0$, then:
            • $B\left[Q\right]\leftarrow B\left[Q\right]-N\left[Q\right]$.
            • If $C\left[Q\right]<127$, then:
              • $C\left[Q\right]\leftarrow C\left[Q\right]+1$.
            • If $B\left[Q\right]>0$, then:
              • $B\left[Q\right]\leftarrow 0$.

2 Decoder

1. Idem to Step 1 of the encoder.
2. Idem to Step 2 of the encoder.
3. Decode $M\left(e\right)$.
4. Compute the initial prediction such as in Step 3.a of the encoder.
5. Add the bias to $ŝ$:
   $$ŝ\leftarrow \left\{\begin{array}{cc}ŝ-C\left[Q\right]\hfill & \text{if }{g}_1>0\hfill \\ ŝ+C\left[Q\right]\hfill & \text{otherwise}.\hfill \end{array}\right.$$

6. Recover the original Laplace distribution for the residues:
   $$e\leftarrow M^{-1}\left(M\left(e\right)\right)=\left\{\begin{array}{cc}-M\left(e\right)∕2-1\hfill & \text{si }M\left(e\right)\text{is odd}\hfill \\ M\left(e\right)∕2\hfill & \text{otherwise}.\hfill \end{array}\right.$$

7. $s\leftarrow \left(e+ŝ\right)\text{ mod }\beta$.
8. Update $Q$ as in Step 5 of the encoder.

3 The RLE mode

LOCO-I uses a Rice encoder that can be very redundant if the probability distributions are very narrow. To overcome this drawback, there is a special encoding mode for this situation that is triggered when $a=b=c=d$.

The normal mode is re-started when if $s\ne a$ or the end of a line has been reached.

Let’s go to the lab!

• Download the LOCO-I command line executables from http://www.hpl.hp.com/loco/locodown.htm.
• Fill the table:
   Codec | lena boats pepers zelda Average  
  -------+---------------------------------  
  LOCO-I |

References