Found In Space (On Flickr) 48
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.
Re:Very cool, but np-complete? (Score:5, Informative)
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.
Re:Very cool, but np-complete? (Score:3, Informative)
I'm guessing its basically just a star-tracker algorithm. I've taken a class on it, but its probably the thing I understand and remember least since I've been in grad school. Basically, they pick out the bright stars, and measure their locations to sub-pixel precision through centroiding, so you're working on a set of coordinates, not an actual image.
Then an algorithm cycles through a star catalog to compare the relative positions and identify the stars. In this case, since the angular size of a pixel is unknown; this has to be figured in as an unknown as well. Unfortunately I can't say how that works, I do know one guy who did his dissertation on a new search algorithm that reduced the computational cost by an order of magnitude.
Really, if you're interested, do a literature search on star tracker technology.