CDF 9/7 Discrete Wavelet Transform (Convolution)

Question

I'm trying to write a simple self-contained program that does a single level of a discrete wavelet transform on a 1D list, using the CDF 9/7 wavelets, and then reconstructs it. I'm just using the convolution/filter-bank method to get a grasp on how it works. In other words, convolve the list with a filter to get the scale coefficients, convolve the list with a different filter to get the wavelet coefficients, but only do this starting with every other element. Then upsample (i.e. add zeroes in between the elements), apply filters to the wavelet and scale coefficients, add them together, and get the original list.

I can get this to work for the Haar wavelet filter, but when I try to use the CDF 9/7 filter it doesn't produce the same input. The resulting list and the original list do sum to the same thing, however.

I'm sure it's a very stupid error in the convolution, but I just can't figure it out. I've tried a bunch of permutations of the convolution, like centering the filter on the index "i", instead of starting the left edge of it, but nothing has seemed to work... It's probably one of those bugs that will make me slap my head when I figure it out.

Here's the code:

import random
import math
length = 128
array = list()
row = list()
scaleCoefficients = list()
waveletCoefficients = list()
reconstruction = list()

def upsample(lst, index):
    if (index % 2 == 0):
        return 0.0
    else:
        return lst[index/2]

for i in range(length):
    array.append(random.random())

## CDF 9/7 Wavelet (doesn't work?)
DWTAnalysisLowpass = [.026749, -.016864, -.078223, .266864, .602949, .266864, -.078223, -.016864, .026749]
for i in range(len(DWTAnalysisLowpass)):
    DWTAnalysisLowpass[i] = math.sqrt(2.0) * DWTAnalysisLowpass[i]
DWTAnalysisHighpass = [0.0, .091272, -.057544, -0.591272, 1.115087, -.591272, -.057544, .091272, 0.0]
for i in range(len(DWTAnalysisHighpass)):
    DWTAnalysisHighpass[i] = 1.0/math.sqrt(2.0) * DWTAnalysisHighpass[i]

DWTSynthesisLowpass = [0.0, -.091272, -.057544, 0.591272, 1.115087, .591272, -.057544, -.091272, 0.0]
for i in range(len(DWTSynthesisLowpass)):
    DWTSynthesisLowpass[i] = 1.0/math.sqrt(2.0) * DWTSynthesisLowpass[i]
DWTSynthesisHighpass = [.026749, .016864, -.078223, -.266864, .602949, -.266864, -.078223, .016864, .026749]
for i in range(len(DWTSynthesisHighpass)):
    DWTSynthesisHighpass[i] = math.sqrt(2.0) * DWTSynthesisHighpass[i]

## Haar Wavelet (Works)
## c = 1.0/math.sqrt(2)
## DWTAnalysisLowpass = [c,c]
## DWTAnalysisHighpass = [c, -c]
## DWTSynthesisLowpass = [c, c]
## DWTSynthesisHighpass = [-c, c]


## Do the forward transform - we only need to do it on half the elements
for i in range(0,length,2):
    newVal = 0.0
    ## Convolve the next j elements
    for j in range(len(DWTAnalysisLowpass)):
        index = i + j
        if(index >= length):
            index = index - length

        newVal = newVal + array[index]*DWTAnalysisLowpass[j]

    scaleCoefficients.append(newVal)

    newVal = 0.0
    for j in range(len(DWTAnalysisHighpass)):
        index = i + j
        if(index >= length):
            index = index - length

        newVal = newVal + array[index]*DWTAnalysisHighpass[j]

    waveletCoefficients.append(newVal)

## Do the inverse transform
for i in range(length):
    newVal = 0.0
    for j in range(len(DWTSynthesisHighpass)):
        index = i + j
        if(index >= length):
            index = index - length

        newVal = newVal + upsample(waveletCoefficients, index)*DWTSynthesisHighpass[j]

    for j in range(len(DWTSynthesisLowpass)):
        index = i + j
        if(index >= length):
            index = index - length

        newVal = newVal + upsample(scaleCoefficients, index)*DWTSynthesisLowpass[j]

    reconstruction.append(newVal)

print sum(reconstruction)
print sum(array)
print reconstruction
print array

Incidentally, I took the filter values from the appendix here: http://www1.cs.columbia.edu/~rso2102/AWR/Files/Overbeck2009AWR.pdf, but I've seen them used in a bunch of matlab sample code as well.

Answer 1

Actually I solved it myself by comparing the coefficients, and then the reconstruction, with the code from this lifting implementation:

http://www.embl.de/~gpau/misc/dwt97.c

Basically, I 1) Made the boundary conditions symmetric, instead of periodic 2) Had to offset the convolutions (and the upsampling) in certain ways to get it all to line up.

Here's the code in case anyone else runs across the problem. I feel like this is still over-complicating it, especially because it's not really documented anywhere, but at least it works. This also includes the "switch" which I used to test against that reference, and I had to modify the Haar wavelet to make it work.

import random
import math
length = int()
array = list()
row = list()
scaleCoefficients = list()
waveletCoefficients = list()
reconstruction = list()
switch = False

def upsample1(lst, index):
    if (index % 2 == 0):
        return lst[index/2]
    else:
        return 0.0

def upsample2(lst, index):
    if (index % 2 == 0):
        return 0.0
    else:
        return lst[index/2]

## Generate a random list of floating point numbers
if (not switch):
    length = 128
    for i in range(length):
        array.append(random.random())
else:
    length = 32
    for i in range(32):
        array.append(5.0+i+.4*i*i-.02*i*i*i)

## First Part Just Calculates the Filters
## CDF 9/7 Wavelet
DWTAnalysisLowpass = [.026749, -.016864, -.078223, .266864, .602949, .266864, -.078223, -.016864, .026749]
for i in range(len(DWTAnalysisLowpass)):
    DWTAnalysisLowpass[i] = math.sqrt(2.0) * DWTAnalysisLowpass[i]
DWTAnalysisHighpass = [.091272, -.057544, -0.591272, 1.115087, -.591272, -.057544, .091272]
for i in range(len(DWTAnalysisHighpass)):
    DWTAnalysisHighpass[i] = DWTAnalysisHighpass[i]/math.sqrt(2.0)

DWTSynthesisLowpass = [-.091272, -.057544, 0.591272, 1.115087, .591272, -.057544, -.091272]
for i in range(len(DWTSynthesisLowpass)):
    DWTSynthesisLowpass[i] = DWTSynthesisLowpass[i]/math.sqrt(2.0)
DWTSynthesisHighpass = [.026749, .016864, -.078223, -.266864, .602949, -.266864, -.078223, .016864, .026749]
for i in range(len(DWTSynthesisHighpass)):
    DWTSynthesisHighpass[i] = math.sqrt(2.0) * DWTSynthesisHighpass[i]

## Haar Wavelet
## c = 1.0/math.sqrt(2)
## DWTAnalysisLowpass = [c,c]
## DWTAnalysisHighpass = [c, -c]
## DWTSynthesisLowpass = [-c, c]
## DWTSynthesisHighpass = [c, c]

# Do the forward transform. We can skip every other sample since they would
# be removed in the downsampling anyway
for i in range(0,length,2):
    newVal = 0.0
    ## Convolve the next j elements by the low-pass analysis filter
    for j in range(len(DWTAnalysisLowpass)):
        index = i + j - len(DWTAnalysisLowpass)/2
        if(index >= length):
            index = 2*length - index - 2
        elif (index < 0):
            index = -index

        newVal = newVal + array[index]*DWTAnalysisLowpass[j]

    # append the new value to the list of scale coefficients
    scaleCoefficients.append(newVal)

    newVal = 0.0
    # Convolve the next j elements by the high-pass analysis filter
    for j in range(len(DWTAnalysisHighpass)):
        index = i + j - len(DWTAnalysisHighpass)/2 + 1
        if(index >= length):
            index = 2*length - index - 2
        elif (index < 0):
            index = -index

        newVal = newVal + array[index]*DWTAnalysisHighpass[j]

    # append the new value to the list of wavelet coefficients
    waveletCoefficients.append(newVal)

# Do the inverse transform
for i in range(length):
    newVal = 0.0
    # convolve the upsampled wavelet coefficients with the high-pass synthesis filter
    for j in range(len(DWTSynthesisHighpass)):
        index = i + j - len(DWTSynthesisHighpass)/2
        if(index >= length):
            index = 2*length - index - 2
        elif (index < 0):
            index = -index

        newVal = newVal + upsample2(waveletCoefficients, index)*DWTSynthesisHighpass[j]

    # convolve the upsampled scale coefficients with the low-pass synthesis filter, and
    # add it to the previous convolution
    for j in range(len(DWTSynthesisLowpass)):
        index = i + j - len(DWTSynthesisLowpass)/2
        if(index >= length):
            index = 2*length - index - 2
        elif (index < 0):
            index = -index

        newVal = newVal + upsample1(scaleCoefficients, index)*DWTSynthesisLowpass[j]

    reconstruction.append(newVal)

print ("Sums: ")
print sum(reconstruction)
print sum(array)
print ("Original Signal: ")
print array
if (not switch):
    print ("Wavelet Coefficients: ")
    for i in range(len(scaleCoefficients)):
        print ("sc[" + str(i) + "]: " + str(scaleCoefficients[i]))
    for i in range(len(waveletCoefficients)):
        print ("wc[" + str(i) + "]: " + str(waveletCoefficients[i]))
print ("Reconstruction: ")
print reconstruction