06-02-2013, 03:49 PM
The BinDCT: Fast Multiplierless Approximation of the DCT
1The BinDCT.pdf (Size: 94.95 KB / Downloads: 39)
Abstract
This paper presents a family of fast biorthogonal
block transforms called binDCT that can be implemented
using only shift and add operations. The transform is based on
a VLSI-friendly lattice structure that robustly enforces both
linear phase and perfect reconstruction properties. The lattice
coefficients are parameterized as a series of dyadic lifting steps
providing fast, efficient, in-place computation of the transform
coefficients as well as the ability to map integers to integers. The
new 8 8 transforms all approximate the popular 8 8 DCT
closely, attaining a coding gain range of 8.77–8.82 dB, despite
requiring as low as 14 shifts and 31 additions per eight input
samples. Application of the binDCT in both lossy and lossless
image coding yields very competitive results compared to the
performance of the original floating-point DCT.
INTRODUCTION
BLOCK transforms have long found application in image
and video coding. The current image compression standard
JPEG [1] as well as many high-performance video coding
standards such as MPEG and H.263 all employ the 8 8 discrete
cosine transform (DCT) at its transformation stage. From
an energy compaction standpoint, the DCT is a robust approximation
to the optimal discrete-time Karhunen–Loève transform
(KLT) of a first-order Gauss–Markov process with a positive
correlation coefficient when [2]. Since the KLT is
signal-dependent, and therefore, computationally complex and
expensive, the DCT has proven to be a much better alternative
in practice. It is signal independent and has linear phase, real
coefficients, and fast algorithms.
APPLICATION IN IMAGE CODING
The two novel transforms are evaluated in an image coding
experiment where the floating-point implementation of the
DCT provides the benchmark. To encode the transform coefficients,
we use a progressive transmission zerotree coder, where
each block of transform coefficients is treated analogously to
a wavelet tree, as described in [4]. The DC subband can be
further decomposed using several wavelet iterations. Integer
wavelets can be employed to keep the transform stage entirely
integer-based.
CONCLUSIONS
Compared to the DCT, the novel block transform described
in this paper offers numerous advantages.
1) The binDCT has a fast, elegant implementation utilizing
only shift-and-add operations. No multiplication is
needed. Eight transform coefficients can be computed
using as low as 13 bit shifts and 30 additions.
2) The binDCT can map integers to integers with exact reconstruction.
This property is pivotal in transform-based
lossless coding and allows a unifying lossy/lossless
coding framework.
3) In our software implementation, the binDCT is already
three times faster than the floating-point DCT. Much
higher speed is expected in hardware implementations.
4) The multiplierless property of the binDCT allows efficient
VLSI implementations in terms of both chip area
and power consumption.