Showing results for 
Search instead for 
Did you mean: 

Low computational cost wavelets

The intermediate calculations of the Walsh Hadamard transform are wavelets. And also pooled sums of wavelets etc. So a n=integer power of 2 input vector gets mapped to n* log base 2 (n) set of wavelets, or twice that if you include the (self) inverse WHT wavlets. That's not too much of a dimensional increase and it seems to me it is very like a convolutional neural network scheme.
In 1d the out of place algorithm is super simple to do. You go through the input data pairwise. Placing the sum in the lower half of a new array. The difference in the upper half sequentially. Then scaling by one over the square root of 2. Repeat log base 2(n) times. The 2d version for images is hardly more difficult.

The pairwise sums are low pass filters, the pairwise differences are high pass filters.

The out of place WHT is one of the simplest algorithms in computer science!

There is also a wavelet compression scheme you can do with that.  Look at the input and all the calculations of the WHT and select the highest magnitude (energy) value,note its location and value and set then set it to zero  .  Make the rest of the values consistent with that by doing partial transforms forward and back (inverse.)  Then repeat that process n times.  The total cost is quite high being n WHTs.  For a large image you would need a GPU.  Decoding is cheap.  You just need to put the n values back and complete the transform and inverse transform for each of them.  Cost 1 or 2 WHTs depending on exactly how you do things.  There are some minor technical things you can do to improve the algorithm. 

0 Kudos
0 Replies