5
$\begingroup$

I am currently reading "A parametric texture model based on joint statistics of complex wavelet coefficients", by Portilla and Simoncelli. In this article, they use the "steerable pyramid" to represent the image. This uses a set of filters to decompose the image in a set of something around 16 subbands in the frequency domain, varying in spatial frequency and orientation.

Problem: They mention (page 55) that their decomposition forms a "tight frame". I know the definition of a tight frame in general linear algebra setting, or say orthogonal wavelet decomposition. However, in those cases the set of vectors that form the frame has cardinality of at least the dimension of the space considered. It seems highly unlikely that the space of images they want to consider is at most 16, and thus highly unlikely that this is what they mean. Can anybody tell me what is meant by the notion of a "tight frame" in this case?

Background: I am a mathematician that recently started working in neuroscience and now reading the mentioned article, published in the international journal of computer vision. Therefore the problem is probably just a matter of different languages used in different fields.

Thanks a lot!

$\endgroup$
  • $\begingroup$ By now, i solved it myself. If anyone has the same sort of question: comment on this question and i'll post the answer. $\endgroup$ – Joachim May 27 '14 at 11:50
  • $\begingroup$ I'm curious! Can you post the answer? Thank you! $\endgroup$ – visoft Aug 31 '14 at 13:44
  • $\begingroup$ @visoft i just did and hope it suffices since i wrote it quickly. Let me know how you like it! :) $\endgroup$ – Joachim Sep 1 '14 at 15:41
2
$\begingroup$

Since visoft requested i post the solution, here goes. It has been a while so not all the details are still fresh so feel free to ask anything if things are unclear!

Let's say we have an image $I$ and apply a filter, which is given by convolution by some $F$. The pixel values of $I$ convolved with $F$ are all the output of the inner product of $I$ with a translated (and less importantly: mirrored) version of $F$.

What i missed at the time was that each pixel should be seen as a coefficient of the new representation of the image. So instead of the 16 subbands i mentioned, the number of coefficients of our new representation is 16 times the number of pixels in the image.

Some notation: for pixel number $(a,b)$, let us write $F_{(a,b)}$ for $F$ translated $(a,b)$ steps (and mirrored) and $(I * F)(a,b)$ for the $(a,b)$-th pixel of $I$ convolved with $F$.

Also, let us call all the translated versions of $F$ our basisfunctions. One can check from the definition of convolution that if we convolve our filter output again with $F$, this results in multiplying every basisfunction $F_{(a,b)}$ by the coefficient $(I * F)(a,b)$ and adding them up. This results in \begin{align*} I * F * F &= \sum_{(a,b)} (I * F)(a,b) \cdot F_{(a,b)}\\ &= \sum_{(a,b)} \langle I, F_{(a,b)}\rangle \cdot F_{(a,b)} \end{align*} where the last equality follows by definition of convolution.

From this, one easily recognizes something that comes up using an orthogonal basis. Now the collection of $F_{(a,b)}$ for all $(a,b)$ is called a tight frame if the above mathematical expression is equal to $I$ itself! It is thus very similar to an orthogonal basis, except that one does not need the set $\{F_{(a,b)}\}_{(a,b)}$ to be linearly independent (if you are very sharp you will note that in this particular case it most likely will be linearly independent, but see the following).

In the paper, actually about 16 of these $F's$ are used. Let's number them $F_1$ up to $F_n$. This is called a tight frame if the following holds: $$ I = \sum_n \sum_{(a,b)} \langle I, F_{n,(a,b)} \rangle \cdot F_{n,(a,b)} $$

This expression is equal to (check this): $$ I = \sum_n (I * F_n * F_n). $$

Since convolution is equivalent to multiplication in the fourier domain, one can check this by going to the fourier domain, squaring all the $F_n$ pointwise and adding them up. That's simple to do. If that adds to an image that is equal to 1 in every pixel, we are dealing with a tight frame.

So concluding, i missed two things: convolving with one $F$ gives as much coefficients as there are pixels in the image, and convolving twice actually multiplies the basisfunctions with the coefficients and adds them up.

As I said, I wrote this quickly and it has been a while, so if anything is unclear feel free to ask again!

$\endgroup$
  • $\begingroup$ Wow! Thanks! I just saw it but I will digest it later :) $\endgroup$ – visoft Sep 1 '14 at 19:49

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.