Tuesday, December 13, 2011

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.

Sunday, June 26, 2011

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.]

Wednesday, May 11, 2011

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

Sunday, February 13, 2011

Face Detection using PCA.

I have been working on my image processing library to support face detection. I started with basic method PCA ( Principal component analysis). Basically you need to have a set of images(20-50) with different lighting conditions etc. The next step is to create covariance matrix out of it and find the eigen vector. Then simply project the the image you need to check in to Eigen vectors and find the distance between them.Do some thresholding to classify it.One important thing is you don't have to take all eigen vectors,may be its better to sort (descending ) based on Eigen value and take only first 'N' vectors.

See the video
video

The difficult part in PCA may be to find the eigne vectors , QA algorithm seems a good choice. The current problem with running time.It takes almost 1 second to process 200X201 image. Roughly O(n^3) complexity. I am plan to implement it in CUDA,so that it can be used for real time detection.