{"id":899,"date":"2018-09-30T02:11:47","date_gmt":"2018-09-30T02:11:47","guid":{"rendered":"http:\/\/muthu.co\/?p=899"},"modified":"2021-05-24T02:58:14","modified_gmt":"2021-05-24T02:58:14","slug":"harris-corner-detector-implementation-in-python","status":"publish","type":"post","link":"http:\/\/write.muthu.co\/harris-corner-detector-implementation-in-python\/","title":{"rendered":"Harris Corner Detector implementation in python"},"content":{"rendered":"\n
\n
\n
\n

The Harris corner detection algorithm also called the Harris & Stephens corner detector is one of the simplest corner detectors available. The idea is to locate interest points where the surrounding neighbourhood shows edges in more than one direction. The basic idea of algorithm is to find the difference in intensity for a displacement of (u,v)<\/em> in all directions which is expressed as below:<\/p>\n

\"\"<\/a><\/figure>

Window function is either a rectangular window or a gaussian window which gives weights to pixels at (x,y)<\/em>. The above equation can be further approximated using Tayler expansion which gives us the final formula as:<\/p>\n

\"\"<\/a><\/figure>

<\/p>\n

where,<\/p>\n

\"\"<\/a><\/figure>

<\/p>\n

Ix<\/em> and Iy<\/em> are image derivatives in x<\/em> and y<\/em> directions respectively. One can compute the derivative using the sobel kernel.<\/p>\n

Then we finally find the Harris response R given by:<\/p>\n

\"\"<\/a><\/figure>

where,<\/p>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

\"\"<\/a><\/figure><\/div>\n\n\n\n

where A, B and C are shifts of window defined by w. <\/em>The lambdas are the Eigen values of M.<\/p>\n\n\n\n

We find the corners using the value of R.<\/p>\n\n\n\n

\"\"<\/a><\/figure><\/div>\n\n\n\n

Process of Harris Corner Detection Algorithm<\/h4>\n\n\n\n
  1. Color image to Grayscale conversion<\/li>
  2. Spatial derivative calculation<\/li>
  3. Structure tensor setup<\/li>
  4. Harris response calculation<\/li>
  5. Find edges and corners using R<\/li><\/ol>\n\n\n\n

    You can find the entire source code in this notebook<\/a>. I am explaining the various parts of the same code here on, so its better you keep that open too for better understanding.<\/p>\n\n\n\n

    Lets take a small image and find edges and corners. For my sample implementation, I am taking the below image:<\/p>\n\n\n\n

    \"\"<\/a><\/figure><\/div>\n\n\n\n

    Step 1: Covert the image to Grayscale<\/h3>\n\n\n\n
    from skimage.io import imread\nfrom skimage.color import rgb2gray\n\nimg = imread('resources\/box.jpg')\nimggray = rgb2gray(img)<\/code><\/pre>\n\n\n\n
    output:<\/strong><\/p>\n\n\n\n
    \"\"<\/a><\/figure><\/div>\n\n\n\n
    You cannot see much difference but at the array level this is what I have:<\/p>\n\n\n\n
    \"\"<\/a><\/figure><\/div>\n\n\n\n
    Step 2: Spatial derivative calculation<\/h3>\n\n\n\n
    from scipy import signal as sig\nimport numpy as np\n\ndef gradient_x(imggray):\n    ##Sobel operator kernels.\n    kernel_x = np.array([[-1, 0, 1],[-2, 0, 2],[-1, 0, 1]])\n    return sig.convolve2d(imggray, kernel_x, mode='same')\ndef gradient_y(imggray):\n    kernel_y = np.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]])\n    return sig.convolve2d(imggray, kernel_y, mode='same')\n\nI_x = gradient_x(imggray)\nI_y = gradient_y(imggray)<\/code><\/pre>\n\n\n\n
    I am using the Sobel filter<\/a> to find the derivatives. For the sake of simplicity, I am using the image as it is. The open-source implementations of the sobel derivative will convert the image to float before running convolution. You can check the source here.<\/a><\/p>\n\n\n\n
    Step 3: Structure tensor setup<\/h3>\n\n\n\n
    Ixx = ndi.gaussian_filter(I_x**2, sigma=1)\nIxy = ndi.gaussian_filter(I_y*I_x, sigma=1)\nIyy = ndi.gaussian_filter(I_y**2, sigma=1)<\/code><\/pre>\n\n\n\n
    Step 4: Harris response calculation<\/h3>\n\n\n\n
    As described in the formulas above, we can easily calculate the response as shown in the code below.<\/p>\n\n\n\n
    k = 0.05\n\n# determinant\ndetA = Ixx * Iyy - Ixy ** 2\n# trace\ntraceA = Ixx + Iyy\n    \nharris_response = detA - k * traceA ** 2<\/code><\/pre>\n\n\n\n
    We can find the Harris response by using the Summation as well. We first calculate the sum of squares of our gradient at each pixel by shifting a window over all the pixels in our image. The window is shifted according to the offset which you decided based on your image.<\/p>\n\n\n\n
    for y in range(offset, height-offset):\n    for x in range(offset, width-offset):\n        Sxx = np.sum(Ixx[y-offset:y+1+offset, x-offset:x+1+offset])\n        Syy = np.sum(Iyy[y-offset:y+1+offset, x-offset:x+1+offset])\n        Sxy = np.sum(Ixy[y-offset:y+1+offset, x-offset:x+1+offset])<\/code><\/pre>\n\n\n\n
    Take a look at the below trace to get a rough idea of how the window shifting works. This is done for all Ixx, Iyy and Ixy.<\/p>\n\n\n\n
    \"Harris<\/a><\/figure><\/div>\n\n\n\n
    Using the sum of squares of each window we find the harris response R at each pixel.<\/p>\n\n\n\n
    #Find determinant and trace, use to get corner response\ndet = (Sxx * Syy) - (Sxy**2)\ntrace = Sxx + Syy\nr = det - k*(trace**2)<\/code><\/pre>\n\n\n\n
    k<\/em> is the sensitivity factor to separate corners from edges, typically a value close to zero, for my analysis I have taken k=0.04. Small values of k result in detection of sharp corners. The response R is an array of peak values of each row in the image. We can use these peak values to isolate corners and edges as I will describe in the next step.<\/p>\n\n\n\n
    Step 5: Find edges and corners using R<\/h3>\n\n\n\n
    1. Edge : r < 0<\/li>
    2. Corner : r > 0<\/li>
    3. Flat: r = 0<\/li><\/ol>\n\n\n\n
      img_copy_for_corners = np.copy(img)\nimg_copy_for_edges = np.copy(img)\n\nfor rowindex, response in enumerate(harris_response):\n    for colindex, r in enumerate(response):\n        if r > 0:\n            # this is a corner\n            img_copy_for_corners[rowindex, colindex] = [255,0,0]\n        elif r < 0:\n            # this is an edge\n            img_copy_for_edges[rowindex, colindex] = [0,255,0]<\/code><\/pre>\n\n\n\n
      \"harris<\/a><\/figure><\/div>\n\n\n\n
      You can see too make corners detected in the image, because the algorithm identifies the corner regions. To find the local maxima of the peaks we can use a peak finding algorithm provided in skimage.<\/p>\n\n\n\n
      corners = corner_peaks(harris_response)\nfig, ax = plt.subplots()\nax.imshow(img, interpolation='nearest', cmap=plt.cm.gray)\nax.plot(corners[:, 1], corners[:, 0], '.r', markersize=3)<\/code><\/pre>\n\n\n\n
      The output from the above code is as below:<\/p>\n\n\n\n
      \"\"<\/a><\/figure><\/div>\n\n\n\n
      The standard implementation provided in skimage or opencv used different variants of guassian filters and kernels to identify the corners so they may differ in their output. Below code is from skimage to detect corners. The output is quite close to what we have derived.<\/p>\n\n\n\n
      #Harris corner detection using skimage library\nfrom skimage.feature import corner_harris, corner_peaks\ncoords = corner_peaks(skimage_harris_response)\n\nfig, ax = plt.subplots()\nax.imshow(img, interpolation='nearest', cmap=plt.cm.gray)\nax.plot(coords[:, 1], coords[:, 0], '.r', markersize=3)<\/code><\/pre>\n\n\n\n
      \"skimage<\/a><\/figure><\/div>\n\n\n\n
      References:<\/h2>\n\n\n\n