wavelets

integer Haar wavelets, Python implementation

the code provided is in no way optimized for speed - it's creating too many temporaries and duplicates

this code is for illustration only, and optimization for speed is left to the reader as an exercise

1D case

this is a trivial implementation of Haar integer-to-integer wavelets

the length of the d array (list or numpy.array) has to be a power of 2

note that the resulting values typically use 1 more bit than the original ones - if the source values are in the [0..N) interval, then the resulting values are in the (-N, N) interval

using lists

def haar_int_fwd_1d(d):
    if len(d) == 1:
        return d
    even = d[::2]
    odd = d[1::2]
    hp = [j - i for i, j in zip(even, odd)]
    lp = [i + (w >> 1) + (w % 2) for i, w in zip(even, hp)]
    return haar_int_fwd_1d(lp) + hp
    
def haar_int_inv_1d(d):
    if len(d) == 1:
        return d
    even = haar_int_inv_1d(d[:len(d) >> 1])
    odd = d[len(d) >> 1:]
    lp = [i - (j >> 1) - (j % 2) for i, j in zip(even, odd)]
    hp = [i + j for i, j in zip(lp, odd)]
    return [x for t in zip(lp, hp) for x in t]

using numpy arrays

import numpy as np

def haar_int_fwd_1d_np(d):
    if len(d) == 1:
        return d
    hp = d[1::2] - d[::2]
    lp = d[::2] + (hp >> 1) + (hp % 2)
    return np.concatenate((haar_int_fwd_1d_np(lp), hp))

def haar_int_inv_1d_np(d):
    if len(d) == 1:
        return d
    lp = haar_int_inv_1d_np(d[:len(d) >> 1]) 
    hp = d[len(d) >> 1:] 
    even = lp - (hp >> 1) - (hp % 2)
    return np.ravel(np.column_stack((even, even + hp)))

2D extension

the list-based version is not provided

numpy version

this is highly un-optimized - it creates a copy for each step of the transformation, and both directions of the transformation use np.apply_along_axis, which i suspect builds the new array row by row

both versions could be parallelised and made into in-place transforms. enjoy!

def haar_int_fwd_2d_np(d):
    tmp = np.apply_along_axis(haar_int_fwd_1d_np, 0, d)
    return np.apply_along_axis(haar_int_fwd_1d_np, 1, tmp)

def haar_int_inv_2d_np(d):
    tmp = np.apply_along_axis(haar_int_inv_1d_np, 1, d)
    return np.apply_along_axis(haar_int_inv_1d_np, 0, tmp)