RANSAC

Image correspondence pipeline (Panoramas)

1) feature point detection

    - detect corners using the Harris corner detector.

 

2) feature point desription

    - describe features using the Multi-scale oriented patch descriptor.

 

3) feature matching

 

4) combine the images together

 

RANSAC; RANdom SAmple Consensus

1) 개요

    - Iterative method to fit models to data that can contain outliers.

    - RANSAC can hopefully pick the inliers and obtain the correct fit.

    - For all possible lines, select the one with the largest number of inliers.

ref : ProgrammingComputerVision_CCdraft.pdf

 

2) Algorithm

ref : http://www.cs.cmu.edu/~16385/lectures/lecture9.pdf

    (1) randomly sample the number of points (s) required to fit the model

ref : http://www.cs.cmu.edu/~16385/lectures/lecture9.pdf

    (2) solve for model parameters using samples

ref : http://www.cs.cmu.edu/~16385/lectures/lecture9.pdf

    (3) score by the fraction of inliers within a preset threshold (delta) of the model

   

    (4) repreat

 

    (5) choose the model that has the largest set of inliers

 

3) parameters

$$N = \frac{log(1-p)}{log(1-(1-e)^{s})}$$

    (1) number of samples N : choose N with probability p -> at least one sample is free from outliers

    (2) number of sampled points S : minimum number needed to fit the model

    (3) distance threshold delta : zero-mean gaussian noise with std (related to the amount of noise we expect in inliers)

 

4) Advantages

    - simple and general

    - applicable to many different problems

    - often works well in practice

 

5) Disadvantages

    - Parameters to tune

    - Sometimes too many iterations are required

    - Can fail for extremely low inlier ratios

    - we can often do better than brute-force sampling

 

6) Code with SIFT

SIFT

RANSAC

# Image laod
img1 = cv2.imread('631.jpg')
img1 = cv2.cvtColor(img1, cv2.COLOR_BGR2GRAY)

img2 = cv2.imread('632.png')
img2 = cv2.cvtColor(img2, cv2.COLOR_BGR2GRAY)

# SIFT
sift = cv2.xfeatures2d.SIFT_create()

keypoints_1, descriptors_1 = sift.detectAndCompute(img1, None)
keypoints_2, descriptors_2 = sift.detectAndCompute(img2, None)

# RANSAC
FLANN_INDEX_KDTREE = 0
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
search_params = dict(checks = 50)

flann = cv2.FlannBasedMatcher(index_params, search_params)

matches = flann.knnMatch(descriptors_1,descriptors_2,k=2)

# store all the good matches as per Lowe's ratio test.
good = []
for m,n in matches:
    if m.distance < 0.7*n.distance:
        good.append(m)
        
MIN_MATCH_COUNT = 10
if len(good)>MIN_MATCH_COUNT:
    src_pts = np.float32([ keypoints_1[m.queryIdx].pt for m in good ]).reshape(-1,1,2)
    dst_pts = np.float32([ keypoints_2[m.trainIdx].pt for m in good ]).reshape(-1,1,2)

    M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC,5.0)
    matchesMask = mask.ravel().tolist()

    h,w = img1.shape
    pts = np.float32([ [0,0],[0,h-1],[w-1,h-1],[w-1,0] ]).reshape(-1,1,2)
    dst = cv2.perspectiveTransform(pts,M)

    img2 = cv2.polylines(img2,[np.int32(dst)],True,255,3, cv2.LINE_AA)

else:
    print("Not enough matches are found - %d/%d" % (len(good),MIN_MATCH_COUNT))
    matchesMask = None
    
draw_params = dict(matchColor = (0,255,0), # draw matches in green color
                   singlePointColor = None,
                   matchesMask = matchesMask, # draw only inliers
                   flags = 2)

img3 = cv2.drawMatches(img1,keypoints_1,img2,keypoints_2,good,None,**draw_params)

plt.imshow(img3, 'gray')
plt.axis('off')
plt.show()

---

ref.

opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_feature_homography/py_feature_homography.html

www.cs.cmu.edu/~16385/lectures/lecture9.pdf

www.cs.cornell.edu/courses/cs5670/2019sp/lectures/lec09_ransac.pdf