Home
ulavalSFM is a set of linux scripts and softwares to prepare structure from motion in parallel. It consists of three parts, pre-computation on images, Lowe's sift points search and matching of those points. You'll find explanations below to install dependencies, ulavalSFM and how to run it. A ultra-script will helps you install all the dependencies. Another will helps you run all softwares in one command. The extern softwares used to make a complete reconstruction are BundlerSFM, CMVS, PMVS2.
If you want to read about Structure From Motion, here's a list of great papers :
- http://grail.cs.washington.edu/rome/rome_paper.pdf
- http://phototour.cs.washington.edu/Photo_Tourism.pdf
- http://phototour.cs.washington.edu/ModelingTheWorld_ijcv07.pdf
Complete the computation when it's done.
On a given image, a Scale-invariant feature transform (sift) is a point of interest with characteristics that will be mostly identical in another image that consists of the geometric transformation of the first.
You can learn more on Lowe's sift points on this website and on its wikipedia page. Here's the website of the Lowe's keypoints detector.
With openCV 3.0, it's pretty easy to detect sift point on an image. In fact, it takes me three lines of code. I create the detector with this line :
Ptr<SIFT> ptrSIFT = SIFT::create();and I detect those points thanks to those lines :
ptrSIFT->detect(img, keypoints);
ptrSIFT->compute(img, keypoints, des);I had to isolate a part of the algorithm and distribute it to the worker cores. I choose to distribute the detection of sift points, because it's already an independent task. Each core begin to compute its starting index and ending index in preparation to execute a single loop, where an index represents an image to compute. Here's the algorithm I use to compute the right indexes :
/*
id => id of the core
size => number of cores
dir => working directory infos
start => starting index
ending => ending index
*/
int numimages = dir.getNBImages();
int distFactor = numimages / size;
int distError = numimages % size;
if (id < distError)
*start = id * (distFactor + 1);
*end = (id + 1) * (distFactor + 1);
else
*start = id * distFactor + distError;
*end = *start + distFactor;Each working core are used to write in the files, since there's a file output for each image describing its sift points.
There's one file for each computed images. The format is the Lowe's format, that is:
File Header :
2 int [ Number of points ] [ Descriptor size ]\n
First point :
4 float for point header [ y coordinate ] [ x coordinate ] [ scale ] [ angle in rad ]\n
128 int with this disposition for descriptor
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]\n
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]\n
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]\n
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]\n
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]\n
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]\n
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]\n
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]\n
Second point :
Same format than first point
etc...
Note that I use size instead of scale in my files, because openCV does not give scale. It does not change anything for structure from motion, but it might change something if you use my sift points files for something else.
This phase is about matching the sift points we have found and thus find links between images.
The trivial algorithm :
The trivial algorithm begins by taking each pairs of images and read their sift points files. After that, the algorithm searches for the nearest neighbor in the second image of each point in the first image. The nearest neighbor is find in the sift's descriptor 128 dimensional space. Using a function that will minimize the euclidean distance between the two keypoints, it's easy to find the right neighbor. Problem is this algorithm always finds a nearest neighbor, but sometimes the nearest neighbor is far and the result is not accurate.
The algorithm used :
The algorithm used computed the matches on each pairs in one direction only. For instance, It means that the pair 0-1 is computed, but not 1-0. It uses the FLANN implemented by openCV. The FLANN constructs a k-d tree to divide the 128 space in different zones. The search is then much more efficient. The key to eliminate most of bad matches is to find the two nearest instead and calculate the distance ratio between both. If the ratio exceed 0.6, the match is pruned. David Lowe suggest a ratio of 0.8 in his 2004 paper Distinctive image features from scale-invariant keypoints, but other softwares like BundlerSFM use 0.6 and it shows great results. For compatibility purpose, it's been chosen to use 0.6.
Only few lines of code are needed to find the nearest neighbor thanks to openCV :
FlannBasedMatcher matcher(makePtr<flann::KDTreeIndexParams>(), makePtr<flann::SearchParams>(64));
vector<vector<DMatch> > two_matches;
matcher.knnMatch(img2.des, img1.des, two_matches, 2);
//Loop to prune bad matches
for(int i = 0; i < img2.des.rows; i++)
{
if(two_matches[i][0].distance < 0.6 * two_matches[i][1].distance)
{
container.NM++;
container.matches.push_back(two_matches[i][0]);
}
}I choose to distribute pairs over my worker cores using this distribution :
/*
id => id of the core
size => number of cores
dir => working directory infos
start => starting index
ending => ending index
*/
int numimages = dir.getNBImages();
numimages = numimages * (numimages - 1) / 2;
int distFactor = numimages / size;
int distError = numimages % size;
if (id < distError)
*start = id * (distFactor + 1);
*end = (id + 1) * (distFactor + 1);
else
*start = id * distFactor + distError;
*end = *start + distFactor;When each core computes its distribution, it starts a double loop. The distribution tells it where to start and where to stop. To eliminate the communication during computation, the writing is done only at the end. Each core waits its turn to write in the file containing all the match. Core 0 begins and then send a message to the next core that he just freed the file. It goes like this until last core write in the file.
There's one file all the match information. The format is the same BundlerSFM uses :
First pair :
2 int for images index
[ image 1 ] [ image 2 ]\n
1 int for number of matches [ x ]
x match descriptors
[ keypoint index image 1 ] [ keypoint index image 2 ]\n
[ '' ] [ '' ]\n
[ '' ] [ '' ]\n
...
Second pair :
Same format than first pair
etc...