This is the 23rd day of my participation in Gwen Challenge

What is a corner point?

A corner is an extreme point, that is, a point with a particular attribute. Of course, you can define your own corner properties (set certain entropy values for corner detection). A corner point can be the intersection of two lines or a point on two adjacent things that have different main directions. A corner is usually defined as the intersection of two edges, or the local neighborhood of a corner should have the boundary of two different regions in different directions. Common corners are:

  • The pixel corresponding to the maximum value of the gray gradient;
  • The intersection of two lines or curves;
  • The pixel with the maximum value of the derivative of the first step degree and the maximum change rate of the gradient direction;
  • The pixel point where the first derivative is the largest and the second derivative is zero (indicating the direction of the discontinuous change of the object’s edge).

Why detect corners?

Corner is a very important feature of image, which plays an important role in the understanding and analysis of image and graph. Corner points can effectively reduce the amount of information data while retaining the important features of image graphics, so that the content of information is very high, which effectively improves the speed of calculation, is conducive to reliable image matching, and makes real-time processing possible. Corner point plays an important role in 3d scene reconstruction, motion estimation, target tracking, target recognition, image registration and matching.

Harris corner detection

The recognition of human eye diagonal points is usually done in a local small area or window. If the small window of this feature is moved in all directions, the gray level of the area inside the window changes greatly, then it is considered that the corner point is encountered in the window. If the gray level of the image in the window does not change when this particular window moves in all directions, then there is no corner in the window. If the gray level of the image in the window changes greatly when the window moves in one direction, but does not change in other directions, then the image in the window may be a straight line segment.

Harris corner detection principle is calculated by the formula as follows:


E ( u . v ) = ∑ x . y w ( x . y ) [ I ( x + u . y + v ) – I ( x . y ) ] 2 = ∑ x . y w ( x . y ) [ I ( x . y ) + I x u + I y v + O ( u 2 . v 2 ) – I ( x . y ) ] 2 material ∑ x . y w ( x . y ) [ I x u + I y v ] 2 = ∑ x . y w ( x . y ) [ u 2 I x 2 + 2 u v I x I y + v 2 I y 2 ] = ∑ x . y w ( x . y ) [ u v ] [ I x 2 I x I y I x I y I y 2 ] [ u v ] = [ u v ] ( ∑ x . y w ( x . y ) [ I x 2 I x I y I x I y I y 2 ] ) [ u v ] E(u,v)= \sum_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^2 \\ =\sum_{x,y}w(x,y)[I(x,y)+I_xu+I_yv+O(u^2,v^2)-I(x,y)]^2 \\ \approx\sum_{x,y}w(x,y)[I_xu+I_yv]^2 \\ =\sum_{x,y}w(x,y)[u^2I_x^2+2uvI_xI_y+v^2I_y^2]\\ =\sum_{x,y}w(x,y)\begin{bmatrix}u & v\end{bmatrix}\begin{bmatrix} I_x^2 & I_xIy \\ I_xI_y & I_y^2\end{bmatrix}\begin{bmatrix}u \\ v\end{bmatrix}\\ =\begin{bmatrix}u & v\end{bmatrix}(\sum_{x,y}w(x,y)\begin{bmatrix} I_x^2 & I_xIy \\ I_xI_y & I_y^2\end{bmatrix})\begin{bmatrix}u \\ v\end{bmatrix}

Replace the middle content with M:


E ( u . v ) = [ u v ] M [ u v ] E(u,v)=\begin{bmatrix}u & v\end{bmatrix}M\begin{bmatrix}u \\ v\end{bmatrix}

Among them


M = ∑ x . y w ( x . y ) [ I x 2 I x I y I x I y I y 2 ] I x . I y Respectively are pixels in the window ( x . y ) in x The direction and y The gradient in the direction. M=\sum_{x,y}w(x,y)\begin{bmatrix} I_x^ 2&i_xiy \ i_xi_y&i_y ^ 2end {bmatrix}\ I_x,I_y are the gradient values of pixels (x,y) in the x and y directions in the window respectively.

Where w(x,y) represents the sliding window weight function, which can be a constant or a Gaussian function. E(u,v) represents the change of pixel value measurement coefficient when the sliding window moves in all directions.


M = ∑ ( x . y ) euro W w ( x . y ) [ I x 2 I x I y I x I y I y 2 ] = [ A C C B ] M = \ sum \ limits_ {} (x, y) which W W (x, y) \ begin {bmatrix} I_x ^ 2 & I_xIy \ \ I_xI_y & I_y ^ 2 = {bmatrix} \ \ end begin {bmatrix} A & C \ \ C & B \end{bmatrix}

E(u,v) can be rewritten as:


E ( u . v ) = A u 2 + 2 C u v + B v 2 A = ∑ ( x . y ) euro W w ( x . y ) ∗ I x 2 B = ∑ ( x . y ) euro W w ( x . y ) ∗ I y 2 C = ∑ ( x . y ) euro W w ( x . y ) ∗ I x I y E (u, v) = Au ^ 2 + 2 + Bv cuv ^ 2 \ \ A = \ sum \ limits_ {} (x, y) which W W (x, y) * I_x ^ 2 = \ \ B \ sum \ limits_ {} (x, y) which W W (x, y) * I_y \ \ ^ 2 C = \ sum \ limits_ {} (x, y) which W W (x, y) * I_xI_y \ \

Harris corner point evaluation coefficient R is defined as follows:


R = d e t ( M ) – k ( t r a c e ( M ) ) 2 d e t ( M ) = Lambda. 1 Lambda. 2 t r a c e ( M ) = Lambda. 1 + Lambda. 2 R = det (M), k (trace (M)) ^ 2 \ \ det (M) = lambda _1 lambda _2 \ \ trace (M) = lambda _1 + lambda _2 \ \

Here λ1 and λ2 are two eigenvalues of the matrix M, and k is a specified value. This is an empirical parameter, which requires experiments to determine its appropriate size. Usually, its value is between 0.04 and 0.06, and its existence is only the shape of the regulating function. R depends on the characteristic values of M for corner | R | is large, flat areas | R | is small, the edge of the R is negative;

API

public static void cornerHarris(Mat src, Mat dst, int blockSize, int ksize, double k, int borderType) 
Copy the code
  • Parameter 1: SRC, input the source image. The type must be single-channel 8U or 32F.
  • Parameter two: DST, output the matrix of evaluation coefficient R. The size is the same as SRC and the type is single-channel 32F.
  • Parameter 3: blockSize: specifies the neighborhood size.
  • Parameter 4: ksize, radius of Sobel operator.
  • Parameter 5: k, calculate the weight system of Harris evaluation coefficient R.
  • Parameter 6: borderType, pixel extrapolation flag bit.

The output DST of the method is the matrix of the evaluation coefficient R. Since the evaluation coefficient has a wide range of positive and negative values, normalization is usually required after the calculation. Then, the empirical threshold is compared to determine whether the pixel is Harris corner point. The larger the threshold is, the fewer Harris corners are extracted; the smaller the threshold is, the more Harris corners are extracted.

operation

/** * Harris corner detection * author: yidong * 2020/12/30 */
class HarrisActivity : AppCompatActivity() {
    private val mBinding: ActivityHarrisBinding by lazy {
        ActivityHarrisBinding.inflate(layoutInflater)
    }

    private val gray by lazy {
        this.getBgrFromResId(R.drawable.lena).toGray()
    }

    override fun onCreate(savedInstanceState: Bundle?). {
        super.onCreate(savedInstanceState)
        setContentView(mBinding.root)

        mBinding.ivLena.showMat(gray)
        wrapCoroutine({ showLoading() }, { doCornerHarris() }, { hideLoading() })
    }

    private fun doCornerHarris(a) {
        val dst = Mat()
        val dstNorm = Mat()
        val dstNormal8U = Mat()
        Imgproc.cornerHarris(gray, dst, 2.3.0.04)
        Core.normalize(dst, dstNorm, 0.0.255.0, Core.NORM_MINMAX)
        Core.convertScaleAbs(dstNorm, dstNormal8U)
        Imgproc.threshold(dstNormal8U, dstNormal8U, 120.0.255.0, Imgproc.THRESH_BINARY)
        GlobalScope.launch(Dispatchers.Main) {
            mBinding.ivResult.showMat(dstNormal8U)
        }
    }

    private fun showLoading(a) {
        mBinding.isLoading = true
    }

    private fun hideLoading(a) {
        mBinding.isLoading = false
    }
    
    override fun onDestroy(a) {
        super.onDestroy()
        gray.release()
    }
}
Copy the code

The effect

The white dots in the figure are the detection results of corner points whose evaluation coefficient is greater than 120. Parameters in the code can adjust the tests themselves.

The source code

Github.com/onlyloveyd/…