Preface
SPECK is a well known wavelet-based hierarchical image entropy coder. I implemented the algorithm described in this paper in MATLAB for my Enginyeering Graduate Final Project. This was in June 2009 in the Image and Video Processing Group in the Communications and Signal Theory Department in the Technical University of Catalonia under the supervision of Prof. Philippe Salembier in collaboration with Julio C. Rolon.
Introduction
SPECK algorithm was published in this paper. It’s the evolution of the SPIHT, but without taking benefit of the inter-subband correlation. Its aim is to efficiently code large blocks of zeros, quickly identifying those pixels with a large amount of information. The significance of the coefficients is measured by their energy. So, the greater is the pixel’s magnitude, the soonest we should start transmitting that pixel. You can download the code.
Definition
Principle
In order to efficiently sort and transmit the information (e.g.: an image), the hierarchical structure containing the coefficients is partitioned in two sets: S and I. The S set corresponds to the approximation level of the hierarchical subband decomposition. The I set corresponds to the rest of the coefficients. Due to the DWT structure expected at the input of the SPECK, the S set has higher energy coefficients than the I set. This is the reason why the search for important coefficients starts in the S set.
But how could we decide if a set is important or it is not? Starting with the most significant bit plane, the algorithm compares the coefficients in the set under the evaluation, against the bit plane. If the bitplane is significant, the algorithm outputs 1, else it outputs 0.
In case A is significant, the algorithm splits the set into four subsets and iterates the process up to the coefficient level if necessary. This procedure quickly finds out where significant coefficients are. When the S set is fully scanned, SPECK tests the I set significance. In case it is significant, the I set is split as in figure and each subset is processed as an S set. Finally, when a coefficient is marked as significant, the encoder sends its sign.
When the whole image is scanned, SPECK rescans the image testing with respect the next lower bit plane (maintaining partitions). Insignificant sets and coefficients are tested and those coefficients found significant with respect to previous bit planes are refined (that is, the encoder sends 0 or 1 depending on its binary representation).
SPECK Lists
SPECK algorithm maintains 4 dynamic lists (in fact, in the original article only 2 lists are maintained. This 2 additional lists (LIP and LNP) have no effect on the algorithm’s performance, but the implementation becomes easier.):
- LIS: List of Insignificant Sets
- These are all sets marked as not significant.
- LIP: List of Insignificant Pixels
- These are all coefficients marked as not significant.
- LNP: List or Newly significant Pixels
- These are all coefficients found significant in that bit plane.
- LSP: List of Significant Pixels
- These are all coefficients found significant in previous bit planes.
Subroutines
Those lists are maintained by both, the encoder and the decoder. The bit stream order is related to the lists order. For example, in the refinement step, bits are sorted in the same order as LSP is and in the sorting step, the significance bits are sorted in the same order than the LIP and the LIS. There are four routines in the algorithm:
- ProcessS
- This routine determines and outputs the significance of a set/coefficient. In case a set becomes significant,
ProcessScalls toCodeS. In case a coefficient become significant, its sign is output. - CodeS
- It splits the block in four sub-blocks and applies to each block the
ProcessSroutine. - ProcessI
- This routine determines and outputs the significance of the I set, if any. In case of significance, it calls
CodeI. - CodeI
- It splits the I set into four subsets as show the image and applies to each subset the routine
ProcessS. After that, it callsProcessI.
Example
This link points to a detailed example when applying the SPECK algorithm to the image with the following coefficients:
