GFD(Generalized Fourier Descriptor), Part 1

it is interesting.. GFD is a rotation invariant. In GFD the orginal image is transformed to polar cordinate system. This provides the rotation invariant ability. I will explain how this happens. When we map normal image in cartesian coodinate system to polar coordinates, a rotation in Cartesian coordinate will cause translation/shifting in polar system. Remeber in polar system r, and theta are the axis. So when you rotate original image, R remain same so in effect the coresponding image is shifted(to left/right according to the direction of rotation) in polar system.

Still you may be wondering even if that is the case, why Fourier transform output remains same ? because we are operating on different data.For each rotation , the image is shifted in polar coordinate system.
If you thought like that, you are thinking.. Good.

I will explain the answer to the above puzzle.



If you remember one dimensional Fourier transform you can see that we are finding the dot product of our Image data with a number of Cos,Sin vectors (N diamensional, same as image size). The sin and cos are orthonormal , so the magnitude remains same. Please read my previous post http://cgmath.blogspot.com/2011/12/image-recognition-using-phase-only.html to get an intuitive grasp on DFT.

that is

Magnitude Of DFT[ {1,2,3,4,5,6}] is equal to Magnitude of DFT[ {4,5,6,1,2,3}]

Magnitude is Sqrt( i*i + j*j ) of the complex number.

Thus we get rotation in-variance. Now the next thing is Fourier descriptor. I will post about that after some days. It is simple( Really ? )

Just started with generalized Fourier Descriptor

I started working on a new algorithm for image search. This is based on Fourier descriptor. Image is first converted in to a corresponding polar representation.This representation allows to get complete rotation in-variance. This is Because a rotation in Cartesian plane corresponds to a angle shifts in polar domain. So the DFT remains same. This is a simple and great idea.

I also started working on my Engine to add MD2 animation support. The image processing things takes too much thinking time also sometimes makes me dull. Thats why i started this to feed my interests.MD2 animation is simple to implement also to understand. Bone animation is difficult to understand if you are a beginner/intermediate in computer graphics. You may be wondering about which format should be used like that.. I had a looked that before some years. But at that time i didn't got time to implement it. Now sadly i am not remembering much.I should have implemented it that time.

Image recognition using phase-only correlation

I have been working on image matching program which based on frequency analysis.Phase correlation principle is used here.

The concept is like this

• Get different frequency information from image using DFT
• Do phase correlation of source and templates frequencies (got from source and template images, both are n-dimensional)
• After phase only correlation do inverse Fourier and find the peaks in the real part. that peaks shows the matching positions..

To really understand how this works , you need to know how DFT works. Not just that magic equation.
How it could transform the signal(here image) to freqency data ?infact we can make an intutive represenation of DFT equation in mind. Here it is in without any formulas.

You need to know the vector projetion operation first. If you don't know that my humble opinion is you better learn some basic vector maths right now. (vectors are everywhere.. Beware!!).
In DFT we have an image, which can be represented as an N-Dimensional vector.Then we take the dot product of this N-dimensional vector with an another N-Dimensional vector , lets call it 'Sin' vector, we also take dot product with an another vector, lets call it 'Cos' vector

that is (ImageN . Sin) + i (ImageN . Cos )    : ". is Dot product between vectors "

(Dot product is actually gives the distance in terms of vector, you can conceive it as projecting the image data to n-dimensional sine and cosine vectors which gives the real and imaginary parts). We do this operation for a number of frequencies, so the Sin,Cos Vectors changes giving different n-dimensional vectors.That's how you get the output N complex numbers (Now look refer the original DFT equation)
So what we just said is, we project(DOT) the image data to a number of vectors which are obtained from different sin,cos signals. Another point worth to remember  is Sin and Cos vectors are always ortho normal ). I hopes i just wrote enough theory for DFT so that you can understand it intutively.Visualization is very important.

So back to matching thing., we do DFT of source and template image( both are same size, template can be padded with zero ).  After this apply phase correlation using equation

    (a+ib)(p+iq)* / (| (a+ib)(p+iq)* | )

• (a+ib):  complex number got from source DFT (so for NxN dimensional image , there will be N*N complex numbers,represented as 2D array NxN.)
• (p+iq): complex number got from template DFT, (p+iq)* is conjugate operation.

What this equation does is it gives high values for signals where where peaks and bottoms correctly
aligns each other.


Now we do inverse DFT on the phase only correlated datas, and apply some threshold on the real part inorder to get the peaks which indicates the matched positions

Images from my tests.

Original image (after edge detection)

Template image (template image size must be same as source, so pad remaining area with zeros)

Result after phase only Correlation, see the peaks, You can see some invalid peaks also there (that is another story). I did this with mathematics. With 'mathematica' or 'matlab' implementation is easy. But i had to spend months to really understand the theory.

This method has advantage of being small invariant to smaller rotation and scale. But drawback is it needs higher time for processing due to DFT.This algorithm doesn't consider any shape information for matching, so this can give false results when too much edges present in source image.

That's all for now,this was a quick post. Good Luck with your projects.

A Board game within 3 hours

Yes, I made a board game within 3 hours. I don't know what made me to code it. May be after playing some board games in mobile, I wished to create my own, especially those crystals graphics. I learnt to create some nice looking glass buttons with Gimp, it is just silly task but it is fun.

See game image shown below(the red text indicates the connected cells count to it), the game idea is like whoever first able to make 5 coins in a line(vertical,horizontal or diagonal) will win the game.

I coded the AI for this small game, it was fun and so easy, just count the number of opponent(player1) connected coins and calculate probability for each empty cell. Next is to calculate the probability of player2's connected cell, based on these determined the cell where the computer must put the coin. It works!!, Can be made better by adding some other ideas too(like considering the distance , so that if same probability comes it will choose the cell which is more connected). 

[if you need source code mail me.]

Shape Context Matching

I recently completed my shape context image matching project without much success :(.if you don't know about shape contexts , check out this link SC

The shape context can be created easily, For matching operation a bipartite based graph matching algorithm can be used. It can be done using Hungarian algorithm with complexity is less than the brute force method( O(n^2) ).

But after implementing Hungarian algorithm i am not able to find enough match point pairs between shapes. The problem with Hungarian method is that it can't give you the answer in fixed amount of time. It tries to optimize, sometimes never ending optimizations.

Still I believe it can be corrected(using a different approch to SC creation) , I need to work more. Not getting enough time.

A nice lecture about Hungarian Algorithm can be found at here