Images to vectors and back

Tuesday, April 3. 2007

Images to vectors and back

Regarding the previous questions I noticed that GA on LCA groups is too general for my concerns and that the study of GA on finite abelian groups is enough.

In a certain paper HGFei published a result that for p×q-images where p and q are relatively prime there is an isomorphism to a vector of length N=pq. The theory considers the groups $\bbZ_p\times\bbZ_q$ and $\bbZ_N$ where $\bbZ_k:=\bbZ/k\bbZ$ . One explicit mapping from the matrix indices $\left(\begin{smallmatrix}j\\ k\end{smallmatrix}\right)$ to the corresponding vector indices is given by

$\iota\colon \bbZ_p\times\bbZ_q \to \bbZ_N, \quad \left(\begin{matrix}j\\ k\end{matrix}\right) \mapsto \beta qj + \alpha pk \pmod N$

where α and β are integers chosen such that

$\alpha p+\beta q \equiv 1 \pmod N$ .

My 480×480 zebra-image doesn’t have a height and width that are relatively prime, so I simply drop one pixel of height:

CODE:

> im=img(2:480,:); > size(im) ans = 479 480 > gcd(479,480) ans = 1

Just for a first test I set α=p and β=q and define a primitive mapping function. (I’ll have to find a quicker transform, as in my tests the switching takes too long. But this could be due to the actually large test image. In addition, I currently only manage to do the backward step by storing the indices in an index matrix.)

CODE:

> function ii=ma2ve(j,k) > p=479; q=480; a=p; b=q; > ii = mod(b*q*j+a*p*k , p*q); > if ii==0; ii=p*q; end > endfunction > ma2ve(1,1) ans = 1 > ma2ve(1,2) ans = 229442 > p*q ans = 229920

I have to return N instead of 0 to have a correct index value. Although the mapping is actually an isomorphism I didn’t know how to go back to the tuple (j,k), so I store the indices in an index matrix while building the image vector:

CODE:

> idx=zeros(p,q); imv=zeros(1,N); > tic; for ii=1:p; for jj=1:q; > idx(ii,jj) = ma2ve(ii,jj); > imv(idx(ii,jj)) = im(ii,jj); > end; end; toc Elapsed time is 58.358711 seconds.

58 seconds!? However, the image looks like this as a vector:

CODE:

> plot(imv)

(zoomed)

I try another way of visualizing that vector: I compare a plot of the index matrix with a p×q-reshaped (line-by-line) version of the vector:

CODE:

> imagesc(idx) > imagesc(reshape(imv,q,p)’) %p is the height of the image

This gives one an idea about how the image values are scattered over the vector in this case: Seeing the vector as a sequence, it starts to walk through the image by going on a diagonal. It is important to notice that there is no way to have the reshaped version of the vector look like the original image, as there would be no possibility for “spanning” the complete image because this requires horizontal and vertical “jumps” during the index transform. Therefore this conversion can never be obtained by a simple reshape.

For testing the inverse of this isomorphism, I want to check whether the FFT of that vector corresponds to the FFT2 of the original image:

CODE:

> tic; Fv=fft(imv); toc Elapsed time is 1.120667 seconds. > tic; Fim=fft2(im); toc %for comparing speed Elapsed time is 0.141670 seconds. > plot(fftshift(abs(Fv)))

(zoomed)

I invert the index transform by the use of the index matrix and visualize the resulting image:

CODE:

> Fvim=zeros(p,q); > tic; for ii=1:p; for jj=1:q; > Fvim(ii,jj)=Fv(idx(ii,jj)); > end; end; toc Elapsed time is 8.330673 seconds. > Fdisp=abs(Fvim)/abs(max(Fvim(:))); %scaled for display > imagesc(fftshift(Fdisp), [0 0.01])

And this indeed looks similar to the plot of the FFT2 of the zebra we have already seen before—Unfortunately, it only looks similar by chance, and it’s not identical and even less identical for other parameters. However, I only did it for testing the matrix-to-vector transform.

One of my next tasks will be to try a Gabor transform and an inverse Gabor transform of an image and see if it reconstructs the image completely. Also I still have to create scripts for building non-separable 2D-window functions like a Gaussian which is stretched in an arbitrary direction, as the presented matrix-to-vector conversion allows the computation of a dual even for non-separable windows.

Posted by Stephan Paukner in Master's Thesis at 08:33 | Comments (0) | Trackbacks (3)

Defined tags for this entry: mathematics, matlab, octave

Trackbacks

Trackback specific URI for this entry

Logbook of Stephan Paukner on : Images to vectors: Quick index matrix

I found a quicker way to compute the index matrix I mentioned: >&#160;tic;&#160;&#91;jj&#160;kk&#93;=meshgrid&#40;1&#58;p,1&#58;q&#41;;&#160;toc Elapsed&#160;time&#160;is&#160;0.080879&#160;seconds. >&#160;size&#40;jj&#41;,&#160;size&#40;kk&#41; ans&#

Logbook of Stephan Paukner on : Images to vectors: Algorithm

Given an image im of size p×q with gcd(p,q)=1.Find a number s that is not divided by the divisors of N=pq.Index vector, method 1:idx = mod(1:s:N*s, N);nil = find(idx==0); idx(nil)=N;Index vector, method 2 (preferred):idx = mod((1:s:N*s)-1, N)+1;imv(idx) =

Logbook of Stephan Paukner on : Images to vectors: Correct isomorphism

I always wondered why it didn&#8217;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

Comments

Display comments as (Linear | Threaded)

No comments

Add Comment

Name

Homepage

Comment

In reply to

Phone*

What is nine minus four?

Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.

Standard emoticons like :-) and ;-) are converted to images.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA