Embedded Zero Tree – Algorithm for Image Coding
In the present digital world, we manage and store different types of data like video,music,images, text files etc digitally in our computers which basically are digital systems. In the case of storing any media type we always look forward to minimum size and maximum quality. When we consider the case of storing an image, we always adopt a “compress and store” algorithm, in which the image is first compressed to reduce the space occupied by the image using compression algorithms and then the data is written into the memory for storage. There are already many algorithms available for image compression and storing and they are being used based on the application and importance of the data. Embedded Zero tree Wavelet (EZW) algorithm is an efficient compression algorithm which is comparatively a newcomer in the field of image coding.
INTRODUCTION
EZW algorithm is a lossy compression
algorithm in which bits are generated in a bit stream, according to
their importance. The EZW encoder calculates a best suited threshold value for compress the still image at a specific decomposition level, followed by multilevel decomposition steps using this threshold. Normally the threshold ranges from 6 to 60, for a decomposition level of 8
ENCODING IN EZW
Natural images can be represented as a
square matrix and they have a low pass spectrum. During wavelet
decomposition, the energy in the sub band decreases with the scale goes
lower.
For a still image the lower frequency components (smooth color
variations) are more important than high frequency components (sharp
edges). Here Discrete Wavelets Transforms (DWT) is used for the
separation of lower frequency components from higher frequency
components. Wavelets are used instead of traditional sub band coding and
Discrete Cosine Transforms (DCT), because they are more effective in
localizing edges. After decomposition, the lowest frequency node will
have the highest coefficient value and is considered as the root node of
the tree obtained after the wavelet decomposition. After decomposition
of the still image, two separate lists of wavelet coefficients are obtained.
- Subordinate list: Consist of the magnitudes of significant coefficients.
- Dominant list contains: The coordinates of those coefficients that have not yet been found to be significant in the same relative order as the initial scan
Fig. Flow chart of encoding algorithm.
DOMINANT PASS
During a dominant pass, coefficients with coordinates on the dominant list are compared to the threshold Ti to determine their significance. The initial threshold will be the mean of the magnitude of all the pixel values. Next threshold value will be half of the previous, and this process goes on until the threshold value decreases to 1. If a pixel value with its magnitude less than the current threshold
is found, it is considered as an insignificant value. If there are no
significant values in their descendants (which are wavelet coefficients
of the same orientation in the same spatial location at finer scales are
likely to be insignificant with respect to Threshold) of the insignificant value, then it is coded as zero trees (T). If any one of the insignificant pixels has a significant value (absolute value greater than threshold) in its descendants, it is coded as isolated zero (Z). Then coding of rest significant pixels are done such that the pixel values greater than zero are coded as positive (P) and less than that are coded as negative (N) and are given to subordinate pass for quantization process. For example consider the initial threshold is 32. Then
After coding, we get a coded matrix [P, N, Z, T]
SUBORDINATE PASS
Quantization is a process of
approximating an infinite set of values to a finite, predictable and
small set of values. Subordinate pass quantizes a number of significant
pixel values to a two value alphabet which gives some idea to the
decoder about the range of values where the actual pixel lies. During a
subordinate pass all coefficients on the subordinate list are scanned
and the specifications of the magnitudes available to the decoder are
refined to an additional bit of precision. Subordinate pass includes the
quantization process followed by arithmetic coding.
DECODING
The decoding process is just the
reversal of encoding steps. It consists of a number of steps. First is
an initialization step, where a zero matrix with the same size of the
coded matrix and a threshold value are initialized.
The second step is known as Principal
stage. Here the codes in [P, N, Z, T] matrix is analyzed and values are
assigned to the alphabets. The matrix [P, N, Z, T] consist of codes with
any one of the symbols P, N, Z, T.
-If the symbol is P, then the zero at the corresponding position in the zero matrix will replaced by Tn (where Tn is the nth threshold value)
-If the symbol is N then a -Tn will replace a zero in the zero matrix
These values are again get added with to the list of processed coefficients;
-For Z and T do nothing.
Next stage is secondary stage, where we analyze the secondary matrix obtained from principal stage and modifies each 1 by adding the one- half of the previous threshold, if the coefficient is positive and subtract if coefficient is negative. Avoid zeros
Repeat these steps until the code is exhausted
CONCLUSION
EZW is a new kind of image coding technique which offers a highly compressed image
after coding and high fidelity when decoded. The low size of coded data
offers much easy data transportation and saves lots of storage apace.
Most striking fact about it is that EZW is an advanced as well as
comparatively simple algorithm. This algorithm can be simulated using
MATLAB and implemented in a DSP chip after translating it into a
compilation language.
No comments:
Post a Comment