Basura

Low-Complexity Reversible Integer-to-Integer Wavelet Transforms for Image
Coding*
Michael D. Adams and Faouzi Kossentini
Dept. o Elec. and Comp. Engineering, University of British Columbia
f
Vanciuvel;B . c.,Canada V6T 1 24
mdadams@ece.ubc.caandfaouzi@ece.ubc.ca
-

.

Abstract
A simple exhaustive search technique is explored as a means
to design low-complexity reversibleinteger-to-integer wavelet
transforms f o r image coding applications. Several new transforms found with this approach are employed in an image
coder in order to demonstrate their effectiveness.

1. Introduction

1. Both analysis filters are of odd length and have sym-

There has been a growing interest in reversible integerto-integer wavelet transforms for image coding applications
[ 1-71. Suchtransforms are invertible in finite-precisionarithmetic (i.e., reversible), map integers to integers, and approximate the linear wavelet transforms from which they are derived. In this paper, we employ a simple exhaustive search
technique to find good low-complexity reversible integer-tointeger transforms for image coding applications. The transforms obtained are then employed in an image codingsystem
to demonstrate their effectiveness.

2. Transforms
The fundamental building block of a wavelet transform is
the uniformly maximally-decimatedfilter bank (UMDFB).n
I
order to design a wavelet transform, we need only construct
its corresponding UMDFB. To obtain transforms that can be
made reversible and map integers to integers, we need to realize the UMDFB using the lifting framework[8,9]. W hen this
framework is employed, a UMDFB is realized in its polyphase
form with the polyphase filtering performed by a ladder network. This leads to the general structure shown in Figure 1.
It is easy to see that the perfect reconstruction (PR) property is always satisfied by this type of structure. By rounding the outputs of the ladder step filters to integers, we obtain
reversibleinteger-to-integer mappings. Since the synthesis
side of the UMDFB is completely determined by the analysis
side, in the discussion which follows, only the analysis side
is considered. As a matter of notation, we denote the lowpass
and highpass analysis filter transfer functions as H o(z) and
H1 ( z ) , respectively. The number of ladder steps is denoted
*This work was supported by both theNatural Sciences and Engineering
Research Council of Canada, and Image Power Inc.

0-7803-5582-2/99/$10.00 01999 IEEE

as N . The kth ladder step filter has transfer function A k ( z)
and length L k .
Since we are concerned with the application of image
coding, it is desirable to constrain the UMDFBs of interest
to those with linear-phase filters. In the case of 2-channel
FIR PR UMDFBs,there are two possibilities for linear-phase
filters which are of practical interest:

177

metric impulse responses.
2. Both analysis filters are of even length, with the lowpass and highpass analysis filters having symmetric and
antisymmetric impulse responses, respectively.
All UMDFBs of the first type can be generated (up to a scaling and delay factor) by choosing the A k ( z) as

wherethe L k are even. A subset of the UMDFBs of the second type can be generated by choosing the A k ( z) as

k=O

where the L k are odd.

3. Design Method
To date, many criteria have been suggested for Uh4DFB
design. For image coding applications, however, the following criteria have proven to be particularly useful: coding gain,
analysis filter frequency selectivity, the number of vanishingmoments of the analyzing and synthesizing wavelet functions, and the smoothness of the synthesizing scaling and
wavelet functions. Moreover, experimental results suggest
that UMDFBs which are effective for image coding generally
satisfy the following conditions:

I Ho(ejo)l # 0 and I Ho(ej")l = 0 ,
\ H l ( e j H ) l# 0 and I Hl(g0)( 0 ,
=

(3a)

... -

r

r

Figure 1: Lifting...