Slashdot Mirror
Automatic 3D Reconstruction of Scenes
Neil Halelamien writes "New Scientist reports on a piece of software by MDRobotics called instant Scene modeler (iSM), which automatically generates 3D reconstructions of scenes, using a few hundred frames from a pair of ordinary video cameras. The software uses David Lowe's SIFT vision algorithm to quickly locate common features between sequential images, for use in the reconstruction; SIFT has also been useful for generating panoramas and object recognition. MDRobotics has a demo page showing the software being used for crime scene reconstruction, along with animated GIFs of input video and the resulting 3D model."
Since slashdot will probably burn out the web server hosting images: http://www.mdrobotics.ca.nyud.net:8090/ism/behind. htm
--
Free iPod? Try a free Mac Mini
Or a free Nintendo DS, GC, PS2, Xbox
Wired article as proof
Here, and here. Lin/Win/Mac versions.
From one of the links: The SIFT algorithm is restricted by patents in the United States and hence this software is not completely free to use. For details see the LICENSE file included in the distribution, before you start to use this software.
Hopefully, they're liberal about the patent and will let noncommercial nonresearch applications use the algorithm. Otherwise, we would have to wait for the really interesting software to come out.
A C# implementation with support for Mono is available to play with for anyone who is interested: http://user.cs.tu-berlin.de/~nowozin/libsift/
--
Free iPod? Try a free Mac Mini
Or a free Nintendo DS, GC, PS2, Xbox
Wired article as proof
I have been waiting for the results for quite some time and they surely look impressive. I might add that the underlying concept is not very hard to understand and one could even make a simple 3-D model of distant objects (like e.g. buildings in your city) using only two eyes, paper, pencil and some basic trigonometry.
/|
Look at this model:
A---B
|\
| C |
|/ \|
D---E
Where D and E are your two eyes, two cameras, or two positions from which you look at the object C that appears to be eclipsing A and B respectively. The distance between any of those points and their relative 3-D positions can be calculated when you know some of the distances (e.g. DE and AD) with very high precision.
Recommended Wikipædia reading for anyone interested: Parallax, Triangulation, Stationary point, Pythagorean theorem, Euclidean geometry, Astrometry, Binocular vision, Stereoscopy. Have fun.
Sincerely,
Pan Tarhei Hosé, PhD.
"Homo sum et cogito ergo odi profanum vulgus et libido."
Olympus has had this functionality in their Camedia cameras for a few years now. The panorama stitching is actually pretty easy. You put it into pano mode, and the camera then uses the initial exposure/shutter setting for the entire series, and puts little bars on the sides of the LCD to tell you were to do the overlap. The (otherwise crappy) Camedia Master software recognizes that it is a series, and stitches pretty quickly and seamlessly. That function only works with original Olympus SM cards, though.
Autopano and Autopano-sift. I have't had good experiences with the SIFT-based software. They always tend to pick the most inappropriate points, like trees/leaves (that move between shots) and the middle of objects (where there aren't many features). I almost always have to go through and remove the bad points, adding in my own reliable ones (corners, unique features, etc). I just don't use them anymore because I actually spend less time if I do all the points myself manually. The GUI of Hugin usually saves me plenty of time already. It does a good job of picking the matching point when I click on one photo. That's all I need anymore.
I would recommend that you look at Hugin (http://hugin.sourceforge.net/) which is a frontend for Panorama tools. Also Autopano (http://autopano.kolor.com/) is a great tool for panorama creations. It does the stitching automatically, and Hugin can be used with it.
Available for Linux/Win32 and OSX.
The best 3D reconstruction method know so far is described in: http://www.wisdom.weizmann.ac.il/~wexler/papers/ic cv03.html
There is an open source equivalent.
It's called Autopano, and IIRC it also uses the SIFT algorithm. Try Hugin (Windows, Linux, OS X), it's able to call it autopano, and automatically get tons of stitching points, and it does quite a good job without tweaking... Especially if you took care in taking the pictures.
Constitutional rights may be respected, repealed, or modified; but they must never be ignored.
Doing a bit more research you will find that the University of British Columbia has applied for a patent on the SIFT algorithm in the United States, although it's happy to allow non-commercial applications of the algorithm, and happy to use other open source projects in it's implementation.
Although as it's from a University, and the patenter allows fre-as-in-beer non - commercial use this looks like a defensive patent to me, this immideatly puts the kibbosh on any GNU GPL/LGPL project using it
/usr/games/fortune > ~/.signature
Did you happen to see the link to autopano-sift? That's GPL'd, I believe.
Actually, now I'm even less impressed. The MDRobotics iSM uses a stereo camera system. I had thought it was a 3D-from-video method (particularly since it uses SIFT). I find those much more useful because I can use it with my home video cam. Making 3D models from a stereo-cam requires special equipment and has been done by everyone and their dog. I'm not so clear on why this is new or that interesting.
That is the third time an article on Slashdot has described something I had hoped I could do my masters thesis on.
First was the decentralized bittorrent network.
Then was the method by which angle changes in camera shots can be deduced by comparing the images (the jigsaw puzzle solver). That was probably an infantile persuit anyway.
And now this.
I will go ahead and spill the next idea along the same lines as the last two projects:
What if you were to put a light collector that could detect angle and intensity of light on top of a camera. Then, when your camera is filming your scene you are also recording the manner in which ambient light is reaching your scene. Later, using you 3D scene reconstruction, you can throw in new objects such as creatures and whatnot and use the data from you light collector to apply correct lighting to the new objects you introduce.
I would imagine someone is about to release this technology and we will see an article about it on Slashdot in a couple weeks. Look forward to it.
Direct away from face when opening.
I agree with you that 3D from uncalibrated images (which is basically what you're looking for) would have been cooler, but science is not quite there yet. Lots of research is done on autocalibration, and lots of research is done on reconstruction based on calibrated images (I've just finished a Master thesis in 3D vision on that topic :) ), but as far as I know no one has been able to put two and two together with convincing results yet. And even because something is stereoscopy-based doesn't mean it's worthless.
First, creating reliable stereoscopic depth maps is far from being a done deal. Researchers are still struggling with doing good stereoscopy in less-than-perfect conditions, like in presence of occlusion, specularities, large scale scenes, etc... (I'll point you to the Middlebury Stereo Page for an overview of current research in the domain).
But even if you can generate nice stereo depth maps, stitching them together to create a fully coherent 3D scene is a big challenge too. So no, unfortunately, 3D scenes from stereo is not a done deal.