Choosing the image pair to use first

Given we have more than just two image views of the scene, we must choose which two views we will start the reconstruction from. In their paper, Snavely et al. suggest to picking the two views that have the least number of homography inliers. A homography is a relationship between two images or sets of points that lie on a plane; the homography matrix defines the transformation from one plane to another. In case of an image or a set of 2D points, the homography matrix is of size 3x3.

When Snavely et al. look for the lowest inlier ratio, they essentially suggest that you calculate the homography matrix between all pairs of images and pick the pair whose points mostly do not correspond with the homography matrix. This means that the geometry of the scene in these two views is not planar, or at least, not the same plane in both views, which helps when doing 3D reconstruction. For reconstruction, it is best to look at a complex scene with non-planar geometry, with things closer and farther away from the camera.

The following code snippet shows how to use OpenCV's findHomography function to count the number of inliers between two views whose features were already extracted and matched:

    int findHomographyInliers( 
    const Features& left, 
    const Features& right, 
    const Matching& matches) { 
      //Get aligned feature vectors 
      Features alignedLeft; 
      Features alignedRight; 
      GetAlignedPointsFromMatch(left, right, matches, alignedLeft, 
      alignedRight); 

      //Calculate homography with at least 4 points 
      Mat inlierMask; 
      Mat homography; 
      if(matches.size() >= 4) { 
        homography = findHomography(alignedLeft.points,  
                                    alignedRight.points, 
                                    cv::RANSAC, RANSAC_THRESHOLD, 
                                    inlierMask); 
      } 

      if(matches.size() < 4 or homography.empty()) { 
        return 0; 
      } 

      return countNonZero(inlierMask); 
    }

The next step is to perform this operation on all pairs of image views in our bundle and sort them based on the ratio of homography inliers to outliers:

    //sort pairwise matches to find the lowest Homography inliers 
    map<float, ImagePair>pairInliersCt; 
    const size_t numImages = mImages.size(); 

    //scan all possible image pairs (symmetric) 
    for (size_t i = 0; i < numImages - 1; i++) { 
      for (size_t j = i + 1; j < numImages; j++) { 

        if (mFeatureMatchMatrix[i][j].size() < MIN_POINT_CT) { 
          //Not enough points in matching 
          pairInliersCt[1.0] = {i, j}; 
          continue; 
       } 

        //Find number of homography inliers 
        const int numInliers = findHomographyInliers( 
          mImageFeatures[i], 
          mImageFeatures[j], 
          mFeatureMatchMatrix[i][j]); 

        const float inliersRatio =  
                    (float)numInliers /  
                    (float)(mFeatureMatchMatrix[i][j].size()); 

        pairInliersCt[inliersRatio] = {i, j}; 
      } 
    }

Note that std::map<float, ImagePair> will internally sort the pairs based on the map's key: the inliers ratio. We then simply need to traverse this map from the beginning to find the image pair with least inlier ratio, and if that pair cannot be used, we can easily skip ahead to the next pair. The next section will reveal how we use these cameras pair to obtain a 3D structure of the scene.