About TODO Blog RSS Old blog Projects Gallery Notes

Sun, 11 Nov 2007

I completed sky walker prorgamm.

This is a name for my 2d point matching algorithm.
It gets number of points as a map and number of points to find on the given map. It should find them even if graph made of those points is rotated or scaled.

One can find result on this animated gif:



It uses too big error value (i.e. maximum difference between points to say that they are equal, it is needed because of heavy math usage (actually a bit of trivial school trigonometry) with resulted error) to show how it works. There are 400 randomly generated points at the left parts and graph to be found at the right, you can see that it was found 7 times being rotated and scaled.

Algorithm is quite heavy - it requires O(N*N*log2(N)*M) in the worst case, where N is number of points on the original map and M is number of points on the searched graph. But application is highly parallelable - it is possible to stop searching and then later resurrect it from given position or from any other inside the whole map, it is possible that several threads or nodes in cluster can search in the diferent areas of the sky.
Complexity can be greatly reduced with introduction of luminocity.

Main application is to search photographed constellations on the huge sky map.

Sources (requires gtk2) and details can be found on the homepage.

/devel/sky :: Link / Comments (0)

Tue, 06 Nov 2007

Back to pattern matching algorithms.

Recent developments pushed 2D point mapping recognition a bit away, but right now I'm starting to work on it again.
Problem found to be not that complex, but algorithm I have in mind has a complexity of O(n^2), where 'n' is a number of points on the original map, but is extremely parallelable. So I plan to implement it and create a nice eye-candy GUI to play with it.

I was specially impressed by the idea when moved home yesterday and looked at the sky - it was about midnight in Moscow and sky was extremely clean (at least where I live several kilometers from Moscow) - no smog, no clouds, no wind and dust. I found number of well-known constellations (although did not find cynosure) including those one which I think I will not be able to see anymore, I recall I was able to find 'Lady in the Chair' aka Cassiopeia many years ago and found it yesterday.

/devel/sky :: Link / Comments (0)