Master's Thesis - 8

For the first time it really seems that I can keep my time plan. I try to reach page 32 today, and if I manage to keep writing one page per day, I will reach the half of the average thesis page number this week, and will indeed manage to be finished with the beginning of October. The theses at my institute indeed range over a number of about 70 pages.

I met with HGFei on Friday, and he said he can fully support my will to be finished soon. There won’t be a serious research or new results in my thesis (except for how the Gabor transform can be computed more easily for separable 2D atoms), but only a summary and visualization of the known results in the 2D case, where of course will be no surprises. Serious research is reserved for dissertations anyway. He wants the results to be suitable for talks or demos.

I proceeded with Chapter 4 about digital images and 2D frequencies rather than with Chapter 3 about finite discrete GA, as it isn’t that mathematical and I wanted to read more on the corresponding things before. I’ll soon have it finished, and maybe I’ll manage to finish the finite discrete GA in the first September week, what is 2 weeks from today.

I already got a little time panic, as I noticed that I wouldn’t make it within September. I’ll need the whole month of September, too. A problem is that Doris wanted to go on a two-week holiday. As she has to take a course anyway, we delayed it to the beginning of October. After that I only want to have to do cosmetic stuff, and no content anymore. I want to have it printed and handed in by the mid of October. And already at the mid or the end of November, there should be the Master exam. I want to be finished by my 30th birthday. This. Must. Work. I can’t afford needing more time, as January 2008 is the last possibility, otherwise I’d have to pay €6,000 back.

On the content: I looked at multi-window Gabor frames, and M. Dörfler’s PhD thesis is a good source. Maybe I can apply her results 1:1 to images, as natural images also dominate in the lower frequencies. The lower frequencies are “area-producing”, already determining the image to a very high degree. Therefore small windows are needed densely in the lower frequency area, resulting in a dense covering here, incorporating many different orientations, yielding only a rough coverage of the image space. The higher frequencies are “contrast-producing” or “border-producing”. Frequency coverage doesn’t have to be that dense here, the exact frequencies are not that interesting, but their location is important. So, a multi-window Gabor system could be of similar type in 2D as it had been taken for 1D music signals by Dörfler.

But multi-window systems shall appear rather late in my thesis. First there are a lot more other things to mention. I made a rough table of contents, giving me a good lead:

• Gabor Frames in as Section 2.3
• Chapter 3: Finite-dimensional discrete Gabor Analysis
• TF-matrices, stuff, frames in
• Gabor matrix
• GA on finite groups and general lattices
• Dual atom on general sampling sets
• Chapter 4: Frequency behavior of digital images (nix Gabor, nix shifts)
• Digital representation of images, RGB, matrix, values
• Understanding 2D frequencies, tensor product of 1D freq
• FFT2, low frequencies dominate, point to multi-windows
• Chapter 5: Image representation by Gabor expansion (Gabor stuff, experiments)
• Atoms can be separable or non-separable
• 2D PF-shifts of an atom, 4D position-freq space
• Separable atom: 2D-dual is tensor of 1D-duals
• Huge frame matrices, applying TF-matrices to image matrices for sep-atoms, proof
• Separable atom, separable lattice, separable dual
• Separable atom, non-separable lattices (1 dim only, both dims), dual
• Non-separable atom, isomorphism 1D-2D, various lattices, dual
• Unassigned
• Multi-window Gabor frames, similar to music signals
• Biological vision

Chapters 3 and 4 should be possible within August, and the rest will be in September.

It is currently completely open if there really will be some “real world” applications of GA to image processing, like serious deblurring, denoising or compression. I’d have to compare it to existing methods, actually. Currently I only plan to compare the various duals and do some thresholding of the Gabor coefficients. If there really will be some multi-window stuff, then maybe only for separable atoms, as I don’t know how I could check the frame quality otherwise.

I’ve written 22 pages covering the basics of time-frequency analysis, walking a path from FT to STFT over frames in Hilbert spaces to Gabor frames in L². I actually wanted to have that done within June. Currently I’m tackling with how to include graphics the right way. Next I want to look at multi-window Gabor analysis and think about how I should proceed to finite-dimensional discrete GA and non-separable lattices. Maybe I can start applying this to images in one month. I definitely want to have my thesis finished within September.

In November 2006 I hoped to be able to finish my Master thesis during spring 2007, having in eye that summer starts on June 21st, 2007. However, I was still working in January and focus on my thesis since February 2007. Four or five months are not enough.

Now I want to finish the introductory and Frame Theory chapters by the end of June. During July I want to write down the chapter about discrete and 2D Gabor analysis. And during August I want to do the chapter about the Octave/MATLAB experiments. This is my time plan to hand in my thesis in September. The Master exam should be due in November.

Why does everything have to take such a long time?

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.