A lossless compression with low complexity transform
The previous paper (Weinberger, 1996) has combined the simplicity of Rice-Golomb coding, which are
adaptively chosen, and an embedded alphabet extension for coding of low-entropy image regions with
the compression potential of context model. The algorithm uses a non-linear predictor with rudimentary
edge detecting capability, and is based on a very simple context model, determined by quantized
gradients and very suitable to low-complexity application. The compression ratio similar or superior to
those obtained state-of-the-art schemes based on arithmetic coding. However, it is within a few
percentage point of the best available compression ratio, at a much lower complexity level.
This paper presents the transformed image lossless coding, which source image was transformed with
DCT (Discrete Cosine Transform) (Gonzales, 1993) to decorrelate and reduce the interpixel redundancy.
The lossy compression can be done at the step by quantizing. The threshold matrix that is used for.quantizing and dequantizing, they were selected depending on the source image and compression
performance. This matrix, finally, was sent as image header.
Transform Image
In the baseline system, it is often called the sequential baseline system, the input and output data
precision are limited to 8 bits, whereas the quantized DCT values are restricted to 11 bits. The
compression itself is performed in three sequential steps: DCT computation, quantization, a variable-length
code assignment.
The image is first subdivided into 8x8 blocks pixel. Subimage is encountered, its 64 pixels are level
shifted by subtracting the quantity 2
n-1, where 2
nis the maximum number of gray levels. The 2-D discrete
cosine transform of the block is then computed, quantized and reordered, to form a 2-D of quantized
coefficients.
The remapped 2-D of quantized coefficients which is generated by mapping the pixel (i,j) of subimage
(u,v) to subimage (i,j) with pixel (u,v) that easily done by interchange between index of subimage and
pixel for 64*64 pixel image.
Figure 2 Transformed coefficient mapping
The Rice-Golomb coding procedure is designed to take advantage of the long runs of zeros that normally
result from the reordering. The nonzero coefficients are coded using a variable-length code.
Figure 3: Simplified diagram of proposed encoder.
Context Based Lossless compression
1. Prediction
The prediction and modeling units in (Weinberger, 1996) are based on the causal template, where x
denotes the current pixel, and a, b, c and d are neighboring pixel as shown in the Figure 4.
Figure 4 Preassigned pixels and causal template for context modeling and prediction
The inner box represents the actual image, while the shaded area represents the implied values for Rb,
Rc and Rd when the sample Ix is in the first line, for Ra and Rc when the sample Ix is in the first column,
and for Rd when the sample Ix is in the last column. From the values of the reconstructed samples at a, b,
c and d, the context first determines if the information in the sample x should be encoded in the regular
or run mode:
- The run mode is selected when the context estimates that successive samples are very
likely to be either identical. The context modeling procedure selects the run mode and the
encoding process skips the prediction and error encoding procedures. In run mode, the
encoder looks, starting at x, for sequence of consecutive samples with values identical to the
reconstructed value of the sample at a. This run is ended by a sample of a different value or
by the end of the current line, whichever comes first. The length information, which also
specifies one of the above two run-ending alternatives, is encoded using a Golomb coding.
- The regular mode is selected when the context estimates samples are not very like to be
identical. The predictor combines the reconstructed values of the three neighborhood
samples at position a, b, and c to form a prediction of the sample at position x as shown in
Figure 3. The error prediction is computed as the difference between the actual sample
value at position x and its predicted value. This error prediction is then corrected by a
context-dependent term to compensate for systematic biases in prediction. The corrected
error prediction is then encoded using a derived procedure form Golomb coding.
2. Context Determination
The first step in the context determination procedure shall be compute the local gradient values, D1, D2,
D3 of the neighborhoods in the following:
The next step is mode selection, if the local gradients are all zero the encoder shall enter the run mode,
otherwise the encoder shall enter the regular mode.
The local gradient quantization and merging will be preformed by using the non-negative thresholds T1,
T2 and T3 to obtain the vector (Q1, Q2, Q3) representing the context for the sample x.
Figure5. A threshold coding quantization curve.
3. The edge-detecting predictor
To estimate P
x of the value at the sample of x, the using encoded shall be determined from the values
R
a, R
b and R
c at the positions a, b, and c by the following condition,
The predictor can be interpreted as picking a in many cases where a vertical edge exists left of the
current location, b in many cases of an horizontal edge above the current location, or a plane predictor
a+b-c if no edge has been detected.
4. The prediction correction
After Px is computed, the prediction shall be corrected according to the sign of context vector (Q1,Q2,Q3)
with the prediction correction value C[ Q], it is derived from the bias cancelation procedure.
Then, the prediction error can be computed and encoded by Golomb’s coding.
