2
$\begingroup$

In many examples of data compression, we take the S largest coefficients of a signal in a sparse basis (eg. 1% of largest DCT coefficients) and set the rest to zero.

How do we practically represent the compressed signal? In the above example, once the smallest coefficients have been set to zero, the signal is directly converted back into the time domain and compared to the original. What if we wanted to store the data?

In other words, how do we concisely store the indexes of the zeroed out coefficients?

$\endgroup$
2
$\begingroup$

Your question is very accurate. Storing the largest (1 % for instance) coefficients only from a sparsifying transform (DCT, wavelet, else) is fool's-gold, since you (more importantly the decoder) don't you where those are located.

And storing their binary indices counterbalances the compression gain for the sparsification. So trade-off should be found between theoretical sparsity and storage. For images, in JPEG, a low-frequency to high-frequency parsing scheme (zig-zag) is used. After quantization, lots of zeroed-out coefficients are compacted with End-Of-block symbols. In JPEG 2000, a multi-scale and bit-wise path is often used, and zeroed-out coefficients are compacted with EZM-SPIHT like coding, that perform sort of vector coding of zero bit-plane.

So, some pre-determined way of parsing coefficients, based on prior knowledge on the signal or image structure, is often useful for actual compression, and applicable to specific class of data.

$\endgroup$
1
$\begingroup$

Ok but this is a very practical problem. Therefore I will state what happens to DCT coefficients in JPEG algorithm:

Once the whole 8-bit graylevel image is divided into adjacent blocks of 8 x 8 = 64 pixels. Each block is independently DCT transformed into 8 x 8 frequency coefficients $Q(u,v)$ and that is further weighted by a mask $W(u,v)$ which implements the quantization. This will set a lot of high frequency coeffcieints in $Q(u,v)$ to zero for a typical image. Whatever, then quantized coefficients are zigzag scanned and converted into a string of 64 quantized coefficients. Then this string is a variety of run length coded according to the number of zeros between two nonzero coeffcients. And last set of consequitive zeros define the end of block symbol EOB. The run length codes are then assigned a predesigned Huffman prefix VLC code. This forms the bitstream associated for the given block. Each block is independtly coded (except the DC level per block which are differential coded from blcok to block). The RLC and Huffman coding stages performs the actual bit reduction mechanism. Where as Quantization stage performs the information reduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.