Difference between revisions of "Short Notes on Wavelets"
From PaskvilWiki
(→Integer Haar Wavelets, Python implementation) |
(→numpy Version) |
||
| (5 intermediate revisions by one user not shown) | |||
| Line 1: | Line 1: | ||
== Integer Haar Wavelets, Python implementation == | == Integer Haar Wavelets, Python implementation == | ||
| + | |||
| + | The code provide 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. | This is a trivial implementation of Haar integer-to-integer wavelets. | ||
| + | |||
| + | The ''d'' array (''list'' or ''numpy.array'') '''has''' to be power of 2. | ||
| + | |||
Note that resulting values typically use 1 more bit than original ones - if source values are in [0..N) interval, then resulting values are in (-N, N) interval. | Note that resulting values typically use 1 more bit than original ones - if source values are in [0..N) interval, then resulting values are in (-N, N) interval. | ||
| − | + | ==== Using Lists ==== | |
<pre>def haar_int_fwd_1d(d): | <pre>def haar_int_fwd_1d(d): | ||
| Line 23: | Line 32: | ||
hp = [i + j for i, j in zip(lp, odd)] | hp = [i + j for i, j in zip(lp, odd)] | ||
return [x for t in zip(lp, hp) for x in t]</pre> | return [x for t in zip(lp, hp) for x in t]</pre> | ||
| + | |||
| + | ==== Using numpy Array's ==== | ||
| + | |||
| + | <pre>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)))</pre> | ||
| + | |||
| + | === 2D Extension === | ||
| + | |||
| + | The list-based version is not provided. | ||
| + | |||
| + | ==== numpy Version ==== | ||
| + | |||
| + | This is highly '''un'''-optimized - it creates copy for each step of transformation, and both directions of 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! | ||
| + | |||
| + | <pre>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)</pre> | ||
Latest revision as of 12:11, 27 February 2017
Contents
Integer Haar Wavelets, Python implementation
The code provide 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 d array (list or numpy.array) has to be power of 2.
Note that resulting values typically use 1 more bit than original ones - if source values are in [0..N) interval, then resulting values are in (-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 Array's
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 copy for each step of transformation, and both directions of 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)
