1
$\begingroup$

I'd like to know if a technique I have in mind is already used and has a name I can look up, and whether it is likely to work and be useful!

My aim is to produce a discrete wavelet transform that is not over complete but shares properties with an invertible Laplacian pyramid. I believe it would be well suited to applications that currently perform processing on Laplacian pyramid layers and then invert the pyramid to acquire a modified signal (but I could well be completely wrong).

Basically, it's a wavelet transform for >1 dimension that has:

  • A single detail band with an isotropic spectrum at each scale, for any number of dimensions n. In contrast to 2^n - 1 anisotropic detail bands as for the typical Tensor product wavelet transform.
  • Sub octave scaling for n>1. Typical discrete wavelet transforms have scales that are linearly an octave apart. This scheme scales the nth dimension in octaves resulting in a linear scaling of 2^(1/n).

Background

A single pass of a 1d wavelet transform turns an n point signal in to 2 n/2 signals: L the low pass signal and H the high pass signal. Further passes are then applied to L.

For higher dimensional signals it is usual to filter the signal in 1d along each axis forming a Tensor product of 1d transforms. In the 2d case this yields 3 detail bands and 1 low pass band for each level of the transform. In 3d, 7 detail bands are generated and 1 low pass band.

The multiple detail bands that come from this process have individual anisotropic spectra. This can be useful in some applications (compression, de-noising, feature finding), but not useful in other situations where it would be preferable for the detail band spectrum to be isotropic. In particular, applications that use an invertible Laplacian pyramid to perform analysis & modification at multiple scales, and then reconstruct an updated image by inverting the pyramid.

Alternative

Start with a signal S in 2 dimensions. The idea extends to more dimensions, but 2 is easier to describe.

Sub Sampling

Consider for a moment the colouring of a continuous chess or checkers board.

Each square on the board is a sample from our signal. We can take just the black or just the white squares. If we do this, we get two new signals, each taking half the samples of the original. If you rotate either of these sub signals by 45º, you end up again with samples that lie on the cartesian grid, so you can perform this sub sampling process recursively.

It's worth a quick not that if you just do this, you'll get a pyramid of (horribly aliased) images. At each level of the pyramid the sample count will halve. The usual case for the wavelet transform in 2d is that the sample count quarters with each level. In the wavelet transform the sub bands are arranged in octaves, but here they are sqrt(2) apart for 2d. For 3d they would be 2^(1/3) apart, and for nD, 2^(1/n).

Lifting

How to turn the horribly aliased signals in to successive detail bands and a low pass residual?

I'm going to wave my hands even more furiously now. The Wavelet Lifting scheme does a split quite a bit like the black white chess split, but in 1d. It then performs a predict step and an update step.

The predict step tries to predict the samples that are going to become the detail, by using the samples that are going to become the low pass. The update step uses the modified detail samples to smooth the low pass signal before the next iteration.

Intuitively, it seems to me that it would be easy enough to predict all the white squares on a chess board using the black ones. Simply averaging the adjacent neighbours and subtracting would do the trick, but a much better filter could also be derived.

Additionally, it seems reasonable that the modified white squares could then be used to update the black squares to remove the high frequency signal that would otherwise be aliased in it – just as the lifting scheme does.

If you applied this transform recursively, you'd end up with a series of detail bands at half octave intervals. It would be invertible (because the lifting scheme is), and the detail bands would be relatively isotropic.

Summary

That's about it! There's obviously a bit of actual work needed requiring mathematical ability way beyond me to turn this in to something that might or might not work :-)

I've no idea if this has is known (very likely, if it works and is useful), or whether it would work or be useful (probably not if it's unknown), but I'd love to hear, either way!

Thanks.

$\endgroup$
  • $\begingroup$ Have you looked on Edge Avoiding Wavelets? Isn't it the same? $\endgroup$ – Royi Jan 1 '15 at 12:46
  • $\begingroup$ They look very cool, thanks. They go a lot further than what I was describing, but make sure of Red Black wavelets which are pretty much exactly what I was talking about. I've added an answer with links. Thank you! $\endgroup$ – Benjohn Jan 1 '15 at 13:35
1
$\begingroup$

Your description sounds very similar to the "Red Black" Wavelet Transform.

It is a useful transform, and is used for instance in "Edge Avoiding Wavelets".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.