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.
Seriously, this is a really cool use of technology at work, keeping the spread of information flowing. I wonder if they'll be able to figure out where I live though...
The musings of just another geek and his junk.
There's a PDF link buried in the interview which had me giggling with geekish delight. The phrase
makes me happy.
Also, I'll give credit to waxy.org which is where I read this first.
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
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.
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.
My infrared image of the kitchen floor bacteria is being interpreted as a major new galactic cluster with supermassive black hole.
Her lips were softer than a duck's bill, but her quacks
Use a different font. Slashdot makes available the <tt> tag which works nicely - emoticons often look better in monospace text anyway. I suppose that's probably subjective though; I grew up with monospace text, if you didn't you probably feel the other way. I think we can all agree that people who use the tag and the enter key to format their text as if they were old school are extremely fucking annoying, though.
"You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"