First, background

Can you write a program to detect the location of these sharp points so that you won’t run into them again?

Second, Harris corner detection algorithm

Harris corner detector can be used to detect corner points in images. The basic idea is as follows:

Using the idea of a sliding window, let the small window centered on the current detection point slide nearby. As shown in the figure below, when the sliding window moves in all directions, the gray level of pixels in the window changes greatly, which may be corner points.

Note: If it is a flat point, the pixel basically does not change when the attachment slides. In the leftmost picture below, if it is an edge, it will not change when sliding along the direction of the edge; if it is a corner point, the pixel value will change no matter how it moves.

According to the above idea, we calculated that the change in pixel value E(u,v)E(u, v)E(u,v) E(u,v)E(u, v) generated by moving the window at point (x, y) to point (x+u, y+ V) was denoted as:


E ( u . v ) = ∑ x . y w ( x . y ) [ I ( x + u . y + v ) – I ( x . y ) ] 2 E(u, v) = \sum_{x, y}{w(x, y){[I(x+u, y+v) – I(x, y)]}^2}

W (x,y) is a weighting function, which can be set as a Gaussian function.

According to Taylor’s formula, expand it to the second order at (0, 0), and get:


E ( u . v ) = E ( 0 . 0 ) + ( u . v ) [ E 1 ( 0 . 0 ) E 2 ( 0 . 0 ) ] + 1 2 ( u . v ) [ E 1 . 1 ( 0 . 0 ) E 1 . 2 ( 0 . 0 ) E 2 . 1 ( 0 . 0 ) E 2 . 2 ( 0 . 0 ) ] [ u v ] E(u, v) = E(0, 0) + (u, v) \begin{bmatrix}E_1(0, 0) \\ E_2(0, 0) \end{bmatrix} + {1 \over 2} (u, v) \begin{bmatrix}E_{1, 1}(0, 0) & E_{1, 2}(0, 0) \\ E_{2, 1}(0, 0) & E_{2, 2}(0, 0) \end{bmatrix} \begin{bmatrix}u \\ v \end{bmatrix}

We can calculate:


E ( 0 . 0 ) = 0 E 1 ( 0 . 0 ) = E 2 ( 0 . 0 ) = 0 E 1 . 1 = 2 ∑ x . y w ( x . y ) I 1 ( x . y ) ∗ I 1 ( x . y ) . . . E(0, 0) = 0 \\ E_1(0, 0) = E_2(0, 0) = 0 \\ E_{1, 1} = 2\sum_{x, y} {w(x, y)I_1(x, y)*I_1(x, y)} \\ …

Substitute E(U,V)E(U, V)E(U,V) can be obtained:


E ( u . v ) = 1 2 ( u . v ) [ E 1 . 1 ( 0 . 0 ) E 1 . 2 ( 0 . 0 ) E 2 . 1 ( 0 . 0 ) E 2 . 2 ( 0 . 0 ) ] [ u v ] = ( u . v ) M [ u v ] ∝ M E(u, v) = {1 \over 2} (u, v) \begin{bmatrix}E_{1, 1}(0, 0) & E_{1, 2}(0, 0) \\ E_{2, 1}(0, 0) & E_{2, 2}(0, 0) \end{bmatrix} \begin{bmatrix}u \\ v \end{bmatrix} = (u, v)M\begin{bmatrix}u \\ v \end{bmatrix} \propto M

Matrix M is defined as:


M = ∑ x . y [ I 1 2 I 1 I 2 I 2 I 1 I 2 2 ] M = \sum_{x, y} \begin{bmatrix}I_1^2 & I_1I_2 \\ I_2I_1 & I_2^2 \end{bmatrix} \\

Note: I1I_1I1 stands for I(x,y)I(x, y)I(x,y) with respect to its first parameter XXX, and can also be expressed as IxI_xIx.

Assuming that the corners are perpendicular to each other, i.e., I1∗I2=Ix∗Iy=0I_1 * I_2 = I_x * I_y = 0I1∗I2=Ix∗Iy=0, then


M = [ Lambda. 1 0 0 Lambda. 2 ] M = \begin{bmatrix}\lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} \\

We use λ1,λ2\lambda_1, \lambda_2λ1,λ2 to represent the intensity of pixel variation in the x, YX,yx, y directions respectively. Only when both are very large can we consider that corner points have been detected.

So let’s construct a function to determine if λ1,λ2\lambda_1, \lambda_2λ1,λ2 are both large:


R ( Lambda. 1 . Lambda. 2 ) = ∣ M ∣ – k ( t r ( M ) ) 2 = Lambda. 1 x Lambda. 2 – k ( Lambda. 1 + Lambda. 2 ) 2 R (\ lambda_1 \ lambda_2) = | | M – k (tr (M)) ^ 2 = \ lambda_1 x \ lambda_2 – k (\ lambda_1 + \ lambda_2) ^ 2

KKK is a hyperparameter.

Harris corner detection algorithm steps

  1. Calculate the picture inx, yThe derivative in the directiondx, dy
  2. Calculate the second – order moment matrix in each sliding windowM
  3. Calculate the response function R(λ1,λ2)R(\lambda_1, \lambda_2)R(λ1,λ2)
  4. Determine whether the current point is a corner point according to the threshold

We use the idea in 1, to detect the corner points on the fence in the picture below according to the steps above

4. Harris corner detection algorithm

Img: grayscale win_size: sliding window size k: constant thresh: threshold for judging as corner points
def detect_corners(img:np.ndarray, win_size:int, k:float, thresh:int) :
    # 1. Compute the derivative of the picture in the x, y direction dx, dy
    dy, dx = np.gradient(img)

    Ixx = dx ** 2, Ixy = dy * dx, Iyy = dy ** 2

    offset = win_size//2
    height = img.shape[0]
    width = img.shape[1]

    corners = [] # Record corner coordinates

    for y in range(offset, height-offset):
        for x in range(offset, width-offset):
            # 2. Calculate the second moment matrix 'M' in each sliding window
            win_Ixx = Ixx[y-offset:y+offset+1, x-offset:x+offset+1].sum()
            win_Ixy = Ixy[y-offset:y+offset+1, x-offset:x+offset+1].sum()
            win_Iyy = Iyy[y-offset:y+offset+1, x-offset:x+offset+1].sum()

            det = win_Ixx * win_Iyy - win_Ixy * win_Ixy
            tr = win_Ixx + win_Iyy
            
            $R(\lambda_1, \lambda_2)$
            R = det - k * tr
            
            # 4. Determine whether the current point is a corner point according to the threshold value
            if R > thresh:
                corners.append((x, y))

    return corners
Copy the code

Using the above method we have the above side fence picture to get the detection effect as shown below.

See Detect_Corners for the complete code above