Slashdot Mirror
Found In Space (On Flickr)
Jamie stumbled upon a writeup for all you astronomy and photography buffs out there (Perhaps my Dad or Uncle Jim are reading ;). From the writeup "The 'blind astrometry server' is a program which monitors the Astrometry group on Flickr, looking for new photos of the night sky. It then analyzes each photo, and from the unique star positions shown it figures out what part of the sky was photographed and what interesting planets, galaxies or nebulae are contained within. Not only does the photographer get a high-quality description of what's in their photo, but the main Astrometry.net project gets a new image to add to its storehouse of knowledge." Check out the Astrometry.net site for many cool pictures.
I use them all the time; just shot comet Lulin, they did a great job of exact location:
I've fallen off your lawn, and I can't get up.
It's only a matter of time before The Goog aggregates all pictures of the sky in realtime to find killer asteroids & make weather forecasts.
If it is done in polynomial time, then it would by definition be in P which means it would NOT be NP complete unless P=NP.
I think you are trying to ask how it could be done in less than exponential time (which is how fast the fastest algorithms to solve NP complete problems run).
I personally would expect an algorithm to perform the match would run in O(U*US+K*KS+UI*KI*U) where U=the number of unknown (ie flickr pictures), K=the number of known pictures, US=the average size of an unknown picture, K=the size of the average known picture, UI=the number of interesting things in an unknown picture and KI=the number of interesting things in a known picture. However, it would often run faster because it should be fairly easy to disqualify two pictures as containing any of the same interesting features.
http://yetanotherpoliticalrant.blogspot.com
to confuse the shit out of someone with photo of a backlit piece of black card with random pinpricks in it.
Nullius in verba
It's similar to Photosynth in that it finds the stars in the sky, but it only provides location information. It does not provide links (you can't navigate from photo to photo the way you can in photosynth.) Not to say they couldn't add that functionality later.
I think of this more like a real-life version of the "Astrogator" role on the space ships from old sci-fi stories, where they arrive at some spot deep in space, the astrogator looks around at the stars and determines exactly where they are.
John
You can think of our search as randomly trying millions of possibilities and hoping for the best. The reason it's so fast is that we order the random attempts very cleverly and tend to find the answer fast if it is indeed solvable. The algorithm usually terminates because it finds a match or times out; rarely does it exhaust the search space in time. The actual complexity of our system is roughly O(N choose 4) where N is the number of stars in the image. Interestingly, this is polynomial, roughly O(N^4), though probably closer to O(N^5) once verification is added.
In summary: the astrometry problem is not NP-hard when approached like we do.
Disclaimer: I am one of the astrometry.net contributors.
python -c "import string,re;print string.join(map(lambda x:chr(string.atoi(x,36)),re.findall('..','2z2t2x36
When these kinds of services (meaning flicker et al) open up their api to public use there are always some who cant figure out why.
Well folks, this is the reason why.
I betting when the executives at flicker sat down to decide if they were going top open up the api, they had no idea that someone would use it to create a map of the sky.