Master's Thesis

I used P. Prinz’ toolbox to compute a 2D dual atom on a separable lattice and on a quincunx lattice. It shows that even if both lattices have same redundancy, the dual might be better localized on the quincunx lattice:

In this example, the norm difference of the “quincunx dual” to the original is about 0.1, and that between the “separable dual” and the original is almost 1.0. To achieve more similarity on the separable lattice, one has to take a higher redundancy.

I’m still not sure what the term “separability” actually expresses for 4D lattices: There exist position lattices (on the image space), frequency lattices (on the FT space), and TF-lattices (for both dimensions). If the atom is separable into its two dimensions, then one can compute the two 1D duals and obtain the 2D dual from their tensor product. If one takes two quincunxes for computing those two 1D duals, does this correspond to a non-separable 4D PF-lattice? In the case of 1D signals, a separable TF-lattice means that there’s always the same set of frequencies taken at every position. A quincunx lattice means that there are two different sets of frequencies chosen alternately while walking along the position points. Maybe the same interpretation works for the 2D case. I haven’t analyzed Prinz’ routine yet, but I think that he takes a rectangular (separable) frequency lattice and shifts it alternately by a half of the lattice-point distance while walking along the position spots. Should one try to use a quincunx position lattice? Well, I’ll have to experminent with that.

HGFei asked me to contact Søndergaard, because that topic of non-separability is currently not only “hot” for myself.

I’ve finally improved my script that computes a dilated and rotated 2D Gaussian with respect to low memory consumption. It applies a dilation and rotation matrix to the 2D domain. I published it under the GNU GPLv2, so if you find any improvements, you are forced to share them.

I still have the impression that it is rather slow, but I currently don’t know how to do it better. Of course, it has to be evaluated on 7×7=49 tiles (where tile=interval×interval) instead of just 7 intervals, what means that the computing time will increase significantly even for the non-dilated and non-rotated case. However, it works.

Here’s a comparison of computing time and accuracy:

And some plots using different parameters:

Yesterday I finally wrote a routine which computes a non-separable (dilated and rotated) 2D Gaussian. It takes parameters for horizontal and vertical dilation of the 2D Gaussian which is then rotated by a corresponding parameter. If it is neither dilated nor rotated, it is numerically identical to the pure 2D Gaussian. It has N. Kaiblinger’s gaussnk.m as background when it is computed on an area which is 7 times as large as the desired signal length but then wrapped (summed up) into the smaller region. I won’t publish it yet, as it can be done better; currently I separated the tasks of computing and wrapping, but they could be done at once.

With this I could finally reproduce a graphic from the paper “2D-GA Based on 1D Algorithms”: It shows (1) a non-separable 2D atom with relatively prime height and width, (2) the atom mapped to vector shape, (3) the dual of that vector with regard to some combined time and frequency steps, and (4) the dual vector reshaped to an image.

The question remains about how to finally do GA using these two 2D atoms. The only ways I found so far was either building the 1D Gabor system (of the atom shaped as vector) or computing a sampled STFT by that 1D vector; this works because modulations stay modulations. However, in the case of separable 2D atoms, this can be done in another way, as I’ll show in another article.

I always wondered why it didn’t work to compute the dual Gabor atom by using the image-to-vector methods I explained previously [1,2,3]. Dr. Kaiblinger showed me that the correct way was to use that special isomorphism that walks along the diagonal of the image. Because width and height have to be relatively prime, that path spans the whole image space. And because there are no jumps over pixels, 2D-modulations stay 1D-modulations. This is not yet proved formally, but I can already show first experiments:

Step 50

Step 100

Step 1000

Step 4000

A 2D-frequency is given as a tensor product of two 1D-frequencies with signal lengths p and q, respectively. If their modulation parameters are given as k_p and k_q, then the corresponding 2D-modulation is given by a 1D-modulation of length N and parameter k_N = k_q p − k_p q (mod N) ; as already said, a proof is not given yet.

So those two 2D-frequencies are really identical. The plot of the second one is identical to the first one, so we skip it here.

Now we want to see if the 2D-dual of a separable 2D atom obtained by that isomorphism is identical to the tensor product of the two 1D-duals.