Harris Corner Detector

Harris corner detector

1) 개요

    - Locate interest points where the surrounding neighborhood shows edges in more than one direction.

 

2) 방법

$$E(u, v) = \sum_{x, y}\: w(x, y)\: [I(x+u, y+v) - I(x,y)]^{2}$$

    - shift the window function by (u, v) and compare each pixel before and after by SSD.

    - w(x, y) : window function -> gives weights to pixels. (e.g. rectangular, gaussian)

    - I(x+u, y+v) : shifted intensity

    - I(x, y) : intensity

    - Corners can be detected by maximizing E(u, v).

    - Calculating E(u, v) needs much computing power. So, make Taylor series expansion.

$$E(u, v) \approx \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}$$

$$M = \nabla {I} \nabla {I}^{T}=\begin{bmatrix} I_{x} \\ I_{y} \end{bmatrix} \begin{bmatrix} I_{x}&I_{y} \end{bmatrix} =\begin{bmatrix} I_{x}^{2} & I_{x}I_{y} \\ I_{x}I_{y} & I_{y}^{2}\end{bmatrix} $$

$$\overline{M} = W * M,\;\;\; \overline{M} = harris \;matrix$$

    - Use window function for the component-wise convolution.

lambda1, 2 : eigenvalues of harris matrix

    - The eigenvalues will change depending on the local image properties. If the gradients vary in the region, the second eigenvalue of harris matrix will no longer be zero. If the gradients are the same, the eigenvalues will be the same as for M.

    - Depending on the gradients of Image in the region (window function), there are three cases on the image above.

$$R = det(\overline{M}) - k(trace(\overline{M}))^{2}; \;\; det(\overline{M}) = \lambda_{1}\lambda_{2},\;\; trace(\overline{M})=\lambda_{1}+\lambda_{2}$$

    - Actual computation of eigenvalues needs more resources. Use indicator function above.

    - R approx 0 : flat

    - R > 0 : corner

    - R < 0 : edge

$$\frac{det(\overline{M})}{trace(\overline{M})^{2}}$$

    - Use the quotient to get rid of the weighting constant.

 

3) Code

    - Original way

# blur the image first using Gaussian derivative filters to suppress noise sensitivity in the corner detection.
# image with each pixel containing the value of the Harris response function.

from scipy.ndimage import filters

def compute_harris_response(im, sigma = 3):
    '''
    Compute the Harris corner detector response function
    for each pixel in a graylevel image.
    '''
    
    # derivatives
    imx = np.zeros(im.shape)
    filters.gaussian_filter(im, (sigma, sigma), (0, 1), imx)
    imy = np.zeros(im.shape)
    filters.gaussian_filter(im, (sigma, sigma), (1, 0), imy)
    
    # compute components of the Harris matrix
    Wxx = filters.gaussian_filter(imx*imx, sigma)
    Wxy = filters.gaussian_filter(imx*imy, sigma)
    Wyy = filters.gaussian_filter(imy*imy, sigma)
    
    # determinant and trace
    Wdet = Wxx*Wyy - Wxy**2
    Wtr = Wxx + Wyy
    
    return Wdet / Wtr

def get_harris_points(harrisim,min_dist=10,threshold=0.1):
    """
    Return corners from a Harris response image
    min_dist is the minimum number of pixels separating
    corners and image boundary.
    """
    # find top corner candidates above a threshold
    corner_threshold = harrisim.max() * threshold
    harrisim_t = (harrisim > corner_threshold) * 1

    # get coordinates of candidates
    coords = np.array(harrisim_t.nonzero()).T
    
    # ...and their values
    candidate_values = [harrisim[c[0],c[1]] for c in coords]
    
    # sort candidates
    index = np.argsort(candidate_values)
  
    # store allowed point locations in array
    allowed_locations = np.zeros(harrisim.shape)
    allowed_locations[min_dist:-min_dist,min_dist:-min_dist] = 1
    
    # select the best points taking min_distance into account
    filtered_coords = []
    for i in index:
        if allowed_locations[coords[i,0],coords[i,1]] == 1:
            filtered_coords.append(coords[i])
            allowed_locations[(coords[i, 0] - min_dist):(coords[i, 0] + min_dist),
                              (coords[i, 1] - min_dist):(coords[i, 1] + min_dist)] = 0
            
    return filtered_coords

def plot_harris_points(image, filtered_coords):
    '''
    Plots corners found in image.
    '''
    plt.figure()
    plt.gray()
    plt.imshow(image)
    plt.plot([p[1] for p in filtered_coords], [p[0] for p in filtered_coords], '*')
    plt.axis('off')
    plt.show()

 

    - OpenCV

def cornerDetect():
    img = cv2.imread('/Users/sejongpyo/desktop/con.png')
    img2 = img.copy()
    imgray = cv2.cvtColor(img2, cv2.COLOR_BGR2GRAY)

    imgray = np.float32(imgray)
    dst = cv2.cornerHarris(imgray, 2, 3, 0.04)
    dst = cv2.dilate(dst, None) # 검출된 코너 부분 확대
    
    img2[dst > 0.01 * dst.max()] = [0, 0, 255]
    
    cv2.imshow('harris', img2)
    
    cv2.waitKey(0)
    cv2.destroyAllWindows()

---

참고

http://programmingcomputervision.com/

docs.opencv.org/master/d6/d00/tutorial_py_root.html

www.youtube.com/watch?v=veieEffgd5A