Eight Points algorithm(Normalized) - 과제 해결

<문제>

Part 1: Normalized 8-Point Algorithm

 

In eight_point_fw, implement the function find_fundamental_matrix. This function takes 2 sets of corresponding key points from the 2 images and computes the fundamental matrix.

 

For stability of the algorithm, we would want to first normalize the points. For this we follow the following steps:

1. Find the centroid of the points (find the mean x and mean y values)
2. Compute the mean distance of all points to the centroid
3. Construct a transformation matrix that transforms from the centroid to the origin and makes the mean distance of the points to the centroid equal to 2

 

You can use the matrix to normalize the points, find the fundamental matrix on the normalized points, and then adjust the matrix to the denormalized points.

 

You can read more here: Eight-point algorithm - Wikipedia.

---

 

Part 2: RANSAC

 

The keypoint detection algorithm that we use as a preprocessing step contains errors and inaccuracies, and therefore could affect the final result of our 8-point algorithm.

 

For a more robust result, you can use the RANSAC algorithm.

 

You should follow these steps and complete the function find_fundamental_matrix_ransac:

1. Sample 8 points from the set of corresponding points
2. Compute the fundamental matrix using those 8 points
3. Find the number of inliers with the current fundamental matrix
4. Repeat step 1 until a certain number of iterations has been reached
5. Return the best fundamental matrix

---

 

<코드>

import numpy as np
import cv2
from PIL import Image
import matplotlib.pyplot as plt
import os
import random # add!

def find_matching_keypoints(image1, image2):
    #Input: two images (numpy arrays)
    #Output: two lists of corresponding keypoints (numpy arrays of shape (N, 2))
    sift = cv2.SIFT_create()
    kp1, desc1 = sift.detectAndCompute(image1, None)
    kp2, desc2 = sift.detectAndCompute(image2, None)

    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(desc1, desc2, k=2)

    good = []
    pts1 = []
    pts2 = []
    for i, (m, n) in enumerate(matches):
        if m.distance < 0.8 * n.distance:
            good.append(m)
            pts2.append(kp2[m.trainIdx].pt)
            pts1.append(kp1[m.queryIdx].pt)

    pts1 = np.int32(pts1)
    pts2 = np.int32(pts2)
    return pts1, pts2

def drawlines(img1,img2,lines,pts1,pts2):
    #img1: image on which we draw the epilines for the points in img2
    #lines: corresponding epilines
    r,c = img1.shape
    img1 = cv2.cvtColor(img1,cv2.COLOR_GRAY2BGR)
    img2 = cv2.cvtColor(img2,cv2.COLOR_GRAY2BGR)
    for r,pt1,pt2 in zip(lines,pts1,pts2):
        color = tuple(np.random.randint(0,255,3).tolist())
        x0,y0 = map(int, [0, -r[2]/r[1] ])
        x1,y1 = map(int, [c, -(r[2]+r[0]*c)/r[1] ])
        img1 = cv2.line(img1, (x0,y0), (x1,y1), color,1)
        img1 = cv2.circle(img1,tuple(pt1),5,color,-1)
        img2 = cv2.circle(img2,tuple(pt2),5,color,-1)
    return img1,img2

def FindFundamentalMatrix(pts1, pts2):
    #Input: two lists of corresponding keypoints (numpy arrays of shape (N, 2))
    #Output: fundamental matrix (numpy array of shape (3, 3))

    #todo: Normalize the points
    def FindCentroid(points):
        x, y = zip(*points)
        l = len(x)
        return sum(x) / l, sum(y) / l

    # 1-1) Find the centroid of the points(점들의 무게 중심을 구한다)
    '''
    https://en.wikipedia.org/wiki/Eight-point_algorithm#The_normalized_eight-point_algorithm
    '''
    pts1_cx, pts1_cy = FindCentroid(pts1)
    pts2_cx, pts2_cy = FindCentroid(pts2)

    # 1-2) Compute the mean distance of all points to the centroid
    #      (모든 점들의 무게 중심을 원점으로 이동시키고, 스케일이 sqrt(2)가 되게 한다)
    '''
     https://github.com/fredzzhang/Normalized-Eight-Point-Algorithm/blob/master/getNormMat2d.m
     https://www.cc.gatech.edu/classes/AY2016/cs4476_fall/results/proj3/html/sdai30/index.html
    '''
    s1 = np.sqrt(2) / (np.sqrt( (np.sum((pts1[:, 0] - pts1_cx) ** 2 + (pts1[:, 1] - pts1_cy) ** 2)) / len(pts1) ))
    s2 = np.sqrt(2) / (np.sqrt( (np.sum((pts2[:, 0] - pts2_cx) ** 2 + (pts2[:, 1] - pts2_cy) ** 2)) / len(pts2) ))

    #1-3) Construct a transformation matrix
    # (변환 행렬을 구한뒤, 점들의 무게 중심을 원점으로 변환한다)
    TransformMatrix1 = np.array([[s1, 0, -s1 * pts1_cx], [0, s1, -s1 * pts1_cy], [0, 0, 1]])
    TransformMatrix2 = np.array([[s2, 0, -s2 * pts2_cx], [0, s2, -s2 * pts2_cy], [0, 0, 1]])

    one = np.ones((len(pts1), 1))
    pts1 = np.append(pts1, one, axis=1).transpose()  # Change pts1 as 을 Homogeneous 형태로 바꾼다.
    pts2 = np.append(pts2, one, axis=1).transpose()

    nPts1 = np.dot(TransformMatrix1, pts1)
    nPts2 = np.dot(TransformMatrix2, pts2)

    #todo: Form the matrix A
    A = np.zeros((len(pts1[1]), 9))
    for i in range(len(pts1[1])):
        A[i, :] = [nPts1[0, i]* nPts2[0, i], nPts1[0, i]*nPts2[1, i], nPts1[0, i],
                   nPts1[1, i]* nPts2[0, i], nPts1[1, i]*nPts2[1, i], nPts1[1, i],
                   nPts2[0, i], nPts2[1, i], 1]
    #todo: Find the fundamental matrix
    U, S, V = np.linalg.svd(A)
    F = V[-1].reshape(3, 3)
    U, S, V = np.linalg.svd(F)
    S[2] = 0  # make rank 2 by zeroing out last singular value
    F_scaled = np.dot(U, np.dot(np.diag(S), V))

    F_scaled = F_scaled /F_scaled[2][2]

    # 1-4) Reverse Nomalization
    F_scaled_Rev = np.dot(TransformMatrix2.transpose(), np.dot(F_scaled, TransformMatrix1))
    return F_scaled_Rev /F_scaled_Rev[2][2]

def FindFundamentalMatrixRansac(pts1, pts2, num_trials = 1000, threshold = 0.01):
    #Input: two lists of corresponding keypoints (numpy arrays of shape (N, 2))
    #Output: fundamental matrix (numpy array of shape (3, 3))

    # todo: Run RANSAC and find the best fundamental matrix
    max_inliers = -np.inf
    best_F = []
    sample_range = pts1.shape[0]
    for t in range(num_trials):
        points_index = random.sample(range(0, sample_range), 8)
        smpPts_1 = []
        smpPts_2 = []
        for point in points_index:
            smpPts_1.append(pts1[point, :])
            smpPts_2.append(pts2[point, :])
        smpPts_1 = np.asarray(smpPts_1)
        smpPts_2 = np.asarray(smpPts_2)

        F = FindFundamentalMatrix(smpPts_1, smpPts_2)

        num_inliers = 0
        one = np.ones((len(pts1), 1))
        pts1_tmp = np.append(pts1, one, axis=1).transpose()  # Change pts1 as 을 Homogeneous 형태로 바꾼다.
        pts2_tmp = np.append(pts2, one, axis=1).transpose()

        for i in range(len(pts1)): # 155
            d1 = abs(np.dot(np.dot(pts1_tmp.transpose()[i], F), pts2_tmp[:,i]))
            if d1 < threshold:
                num_inliers += 1
        if num_inliers > max_inliers:
            max_inliers = num_inliers
            best_F = F
            print(max_inliers)
    return best_F

if __name__ == '__main__':
    #Set parameters
    data_path = './data'
    use_ransac = True

    #Load images
    image1_path = os.path.join(data_path, 'myleft.jpg')
    image2_path = os.path.join(data_path, 'myright.jpg')
    image1 = np.array(Image.open(image1_path).convert('L'))
    image2 = np.array(Image.open(image2_path).convert('L'))


    #Find matching keypoints
    pts1, pts2 = find_matching_keypoints(image1, image2)

    #Builtin opencv function for comparison
    F_true = cv2.findFundamentalMat(pts1, pts2, cv2.FM_8POINT)[0]

    #todo: FindFundamentalMatrix
    if use_ransac:
        F = FindFundamentalMatrixRansac(pts1, pts2)
    else:
        F = FindFundamentalMatrix(pts1, pts2)
        #compute_fundamental_normalized(pts1, pts2)

    # Find epilines corresponding to points in second image,  and draw the lines on first image
    d1 = pts2.reshape(-1, 1, 2)
    lines1 = cv2.computeCorrespondEpilines(pts2.reshape(-1, 1, 2), 2, F_true)
    lines1 = lines1.reshape(-1, 3)
    img1, img2 = drawlines(image1, image2, lines1, pts1, pts2)
    # fig, axis = plt.subplots(1, 2)
    #
    # axis[0].imshow(img1)
    # axis[0].set_title('Image 1')
    # axis[0].axis('off')
    # axis[1].imshow(img2)
    # axis[1].set_title('Image 2')
    # axis[1].axis('off')

    #plt.show()
    plt.subplot(221), plt.imshow(img1)
    plt.subplot(222), plt.imshow(img2)

    # Find epilines corresponding to points in first image, and draw the lines on second image
    lines1_1 = cv2.computeCorrespondEpilines(pts2.reshape(-1, 1, 2), 2, F)
    lines1_1 = lines1_1.reshape(-1, 3)
    img3, img4 = drawlines(image1, image2, lines1_1, pts1, pts2)
    # fig, axis = plt.subplots(1, 2)
    #
    # axis[0].imshow(img1)
    # axis[0].set_title('Image 1')
    # axis[0].axis('off')
    # axis[1].imshow(img2)
    # axis[1].set_title('Image 2')
    # axis[1].axis('off')
    #
    # plt.show()
    plt.subplot(223), plt.imshow(img3)
    plt.subplot(224), plt.imshow(img4)
    plt.show()


'''
    # Find epilines corresponding to points in second image,  and draw the lines on first image
    d1 = pts2.reshape(-1, 1, 2)
    lines1 = cv2.computeCorrespondEpilines(pts2.reshape(-1, 1, 2), 2, F_true)
    lines1 = lines1.reshape(-1, 3)
    img1, img2 = drawlines(image1, image2, lines1, pts1, pts2)
    fig, axis = plt.subplots(1, 2)

    axis[0].imshow(img1)
    axis[0].set_title('Image 1')
    axis[0].axis('off')
    axis[1].imshow(img2)
    axis[1].set_title('Image 2')
    axis[1].axis('off')

    plt.show()

    # Find epilines corresponding to points in first image, and draw the lines on second image
    lines2 = cv2.computeCorrespondEpilines(pts1.reshape(-1, 1, 2), 1, F_true)
    lines2 = lines2.reshape(-1, 3)
    img3, img4 = drawlines(image2, image1, lines2, pts2, pts1)
    fig, axis = plt.subplots(1, 2)

    axis[0].imshow(img1)
    axis[0].set_title('Image 1')
    axis[0].axis('off')
    axis[1].imshow(img2)
    axis[1].set_title('Image 2')
    axis[1].axis('off')

    plt.show()
'''

 

 

참고 사이트

- Computer Vision Project (gatech.edu)

- https://github.com/marktao99/python/blob/master/CVP/samples/sfm.py

- 3D-Reconstruction-and-Epipolar-Geometry/submission.py at master · laavanyebahl/3D-Reconstruction-and-Epipolar-Geometry (github.com)