SFM Scanner

thingiverse

Structure from motion is a class of algorithms that take information about point correspondences between images and use them to reconstruct 3D scenes. While some pretty serious math is involved, no specialist hardware is required aside from a camera. We've seen lots of structure from motion based 3D scanning solutions already this year, the best known being http://my3dscanner.com/, but all of them are closed source. This is hard to deal with when I see cool things like Qi Pan's ProFORMA software (http://www.youtube.com/watch?v=vEOmzjImsVc&fmt=22) but can't use them or look at how they work. There's been plenty of good open source innovation in laser based 3D scanners, but very little on the software side of scanning, which kind of surprises me given that software is usually the area that people think of as conducive to an open source approach. So for my computational photography final project last semester I set out to make an open source SFM scanner in Matlab, since a lot of toolkits were already available to do the heavy math part. Unfortunately I won't have much time to work on it this summer, so I decided to release the code now to see if anyone could do anything with it. The program starts with either user input images or input from a webcam, extracts feature points using David Lowe's SIFT, attempts to remove outliers using the MAPSAC algorithm from Philip Torr's toolkit, then uses Vincent Rabaud's toolkit to reconstruct the 3D positions of the points. From there Liugi Giaccari's implementation of the Crust algorithm is used to find a surface mesh automatically, and a function by Andreas Richter I found on the Matlab file exchange to export an STL file. The end result is that you can (theoretically) go from photo capture to STL output without any user intervention. In practice you might be better off exporting the point cloud and meshing it with Meshlab or some other program. As of now I have only written a function to extract structure from 2 images using the normalized 8 point algorithm. I think this might require a stereo camera setup, which you might be able to approximate using just one webcam. More importantly, SIFT is not a very good detector for getting dense sets of features, and 2 images will not give you much to work with, so results as of now will be poor to unrecognizable. Fortunately all the code is pretty modular, so switching in a new feature detector or making other modifications should work fine after transposing a matrix or changing some variables. Vincent's toolbox can use quite a few different methods, most of which are much better than the 8 point algorithm, but it needs either calibration data or more than 2 input images. Implementing affine and metric upgrades would be even better. I'm hopeful that this project will progress to the point where it is possible to make use of these methods, and I'll try to answer any questions anyone trying to add to what's there now might have. If you're interested in more detail on how everything was done you can read my final project report, attached below. Instructions The program is fairly easy to use once you've installed everything, but downloading all the toolkits and dependencies can get confusing. I was going to package them up, but they're all under different licenses so I thought it best to just provide links. You will need: Matlab (I used v2010a), the Image Processing toolkit, and the data acquisition toolkit (if you're using a webcam). sfm with sift.zip (uploaded to this Thingiverse page) Vincent Rabaud's SFM toolbox: http://code.google.com/p/vincents-structure-from-motion-matlab-toolbox/ Philip Torr's SAM toolkit: http://www.mathworks.com/matlabcentral/fileexchange/4576 Visual Studio 2008 express (for compiling the toolkits): http://msdn.microsoft.com/en-us/express/future/bb421473 Vincent Rabaud's toolbox also requires: Piotor's image and video toolbox (http://vision.ucsd.edu/~pdollar/toolbox/doc/index.html) Yalmip (http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php) Sedumi (http://sedumi.mcmaster.ca/) GlotiPoly (http://www.laas.fr/~henrion/software/gloptipoly3/) You can leave all the toolkits in their own folders, just make sure you've added them to your Matlab path before running. Instructions for installing and compiling everything can be found in the respective documentation, but I think Vincent's toolbox is the only thing that needs compiling, and all you have to do is run toolboxSfmcompile in Matlab. Once that's all set up, make sure everything required has been added to the Matlab path, and open the "sfm with sift" folder in matlab (because of a quirk with SIFT things won't run properly unless you're in that folder). Then run twoImSFM2STL, either with 2 images as arguments or with now arguments if you want to use a webcam. Follow the instructions and the program should export an STL file called "output.stl" which can be opened in replicatorG. As I said, you may have better luck trying to mesh the object manually, but you'll need to find your own way of exporting the point cloud.