Browse Prior Art Database

TRANSLATION-INVARIANT WAVELET IMAGE CODER

IP.com Disclosure Number: IPCOM000009700D
Original Publication Date: 2000-Jan-01
Included in the Prior Art Database: 2002-Sep-11
Document File: 6 page(s) / 269K

Publishing Venue

Motorola

Related People

Glen P. Abousleman: AUTHOR

Abstract

We propose an image coder that uses a fast algo- rithm for calculating the two-dimensional wavelet transforms for all circular translates of a N X N input image. The optimal translate for the decom- position is selected by using a quadtree search algo- rithm and a scale-separable cost criterion. Once the optimum translate has been identified, a modified wavelet tree is formed. The resulting wavelet coef- ficients are encoded using trellis-coded quantization.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 26% of the total text.

Page 1 of 6

0 M MO7VROLA Technical Developments

TRANSLATION-INVARIANT WAVELET IMAGE CODER

by Glen P. Abousleman

  We propose an image coder that uses a fast algo- rithm for calculating the two-dimensional wavelet transforms for all circular translates of a N X N input image. The optimal translate for the decom- position is selected by using a quadtree search algo- rithm and a scale-separable cost criterion. Once the optimum translate has been identified, a modified wavelet tree is formed. The resulting wavelet coef- ficients are encoded using trellis-coded quantization.

  In the compression of non-stationary, wide-band transients, the performance of wavelet compression algorithms may deteriorate when the signals are not aligned in time properly. This phenomenon of wavelet transforms, namely their sensitivity to trans- lations, has been recognized by the wavelet and sig- nal processing community, and can be addressed using different approaches.

  In the proposed method, we expand on the approach of [I]. Using the algorithm introduced by Beylkin [Z], we compute the wavelet transform for all the circular time shifts of an N X N discrete-time input image in O(NslogN) operations. Using a care- fully chosen cost function, the wavelet coefficients of the time shift with minimal cost are selected as the best representation of the signal using a quad tree search algorithm similar to that presented in [3]. The total complexity of the above algorithm is O(NslogN). The wavelet coefficients together with the translation to which they correspond give a com- plete characterization of the original signal. The wavelet coefficients given by the above decomposi- tion procedure are the same when two signals are merely the circular shifts of each other.

  It is well known that using quadrature mirror til- ter banks (QMFs), we can compute the wavelet decomposition of an N X N image in O(P) opera- tions. Since the coefficients are not shift-invariant,

it appears that the computation of the wavelet expansions for all NZ circular shifts of the image requires O(N4) operations. However, because of the periodically time-varying property of the rate- change operators in the decomposition filter banks for computing the wavelet transform, there are actu- ally only (NslogN) distinct coefficients.

  We now describe a wavelet decomposition that is invariant to translations in the sense that it looks at all translates of the input image, and chooses the best set of wavelet coefficients. It consists of two key steps: an efficient algorithm for computing the wavelet transforms for all translates, and a fast quadtree search algorithm. The input signal is assumed to be circularly extended, so that the size of the transform is kept constant.

Consider the decomposition diagram in Figure
1. The image is first divided into 4 channels. The four subimages are then downsampled by a factor of two both by column and by row. The rate-change operators divide the image into 4 cosets. Given any translat...