（8） HS corner detection

1. The basic theory

When processing feature descriptors suitable for multiple images , There are two main feature detection methods , One is angle based detection , The other is to process all areas in the image . Here we mainly discuss angle based detection .

1988 year ,Harris and Stephens An angle detection algorithm is proposed , HS Angle detector , See paper A Combined Corner and Edge Detector.

HS The principle of the detector is as follows , There are three cases of gray changes ,1 Is that the gray level does not change in all directions , 2 It changes in a certain direction , But in the other direction, the grayscale remains unchanged ,3 It's a change in both directions .HS The angle detector uses mathematical formulas to distinguish these three situations .

f Represents an image ,f(s, t) By (s, t) A small piece of image defined by the value of patch,f(s+x, t+y) Is the same size but moved (x,y) Small image of patch, The weighted sum of the squares of the differences between the pixel values of each pixel of the two image blocks is expressed as ：

$C(x,y)=\sum \sum \omega (s,t)[f(s+x,t+y)-f(s,t){]}^2$

$\omega (s,t)$ Is a weighting function . Where there are corners , namely C(x,y) Taking the maximum . Take a pixel , Calculate in its adjacent pixels $C(x,y)$.

take $f(s+x,t+y)$ Represents the approximation of Taylor expansion ,

$f(s+x,t+y)\approx f(s,t)+x{f}_x(s,t)+y{f}_y(s,t)$

then ：

$C(x,y)=\sum \sum \omega (s,t)[x{f}_x(s,t)+y{f}_y(s,t){]}^2$

The above equation can be expressed in matrix form ：

$C(x,y)=[x,y]M\left[\begin{array}{c}x\\ y\end{array}\right]$

among ,

$M=\sum \sum \omega (s,t)A$

$A=\left[\begin{array}{cc}{f}_x^2& f_x{f}_y\\ f_x{f}_y& f_y^2\end{array}\right]$

$M$ Sometimes called Harris matrix .

matrix $M$ The feature vector of points to the largest data expansion direction , And the corresponding eigenvalue is directly proportional to the amount of data expansion in the direction of the eigenvector . So we can know , Two small eigenvalues represent almost constant grayscale , A small eigenvalue and a large eigenvalue indicate the existence of a vertical or horizontal boundary , Two large eigenvalues indicate the existence of an isolated point or angle .

However , Because the computation cost of solving eigenvalues is large ,HS The angle detector does not use eigenvalues , Instead, it makes use of the properties of the square matrix , The trace is equal to the sum of the eigenvalues of the matrix , The determinant is equal to the product of eigenvalues ,

$R={\lambda }_x{\lambda }_y-k({\lambda }_x+{\lambda }_y{)}^2=det(M)-ktrac{e}^2(M)$

$k$ It's a constant , Usually take $(0,0.25)$.

When both eigenvalues are large , R Take the larger positive value , A larger eigenvalue and a smaller eigenvalue ,R Take a larger negative value , Both eigenvalues are small ,R The absolute value of is small

k It can be regarded as a sensitive factor ,k The smaller, the more corners you find

Shi-Tomasi Corner detector

1994 year ,Jianbo Shi and Carlo Tomasi Put forward Good features to track
Use it directly $R=min({\lambda }_x,{\lambda }_y)$ As a measure , Super parameters are avoided $k$

2.OpenCV API

2.1cornerHarris

void cv::cornerHarris(
    InputArray 	src,
    OutputArray 	dst,
    int 	blockSize,
    int 	ksize,
    double 	k,
    int 	borderType = BORDER_DEFAULT 
)	

• src： Input ,8 Bit single channel image , grayscale
• dst： Storage Harris Data of test results , data type CV_32FC1
• blockSize: Calculation C(x,y) Size of time neighborhood
• ksize: Use Sobel When the operator calculates the gradient , The size of the convolution kernel
• k: Calculation R Super parameter of time , That is, the mediation factor of the sensitivity of the detection angle , Small makes many angles , The bigger the horn, the less
• borderType: How to deal with boundary pixels

2.2 goodFeaturesToTrack

void cv::goodFeaturesToTrack	(	
    InputArray 	image,
    OutputArray 	corners,
    int 	maxCorners,
    double 	qualityLevel,
    double 	minDistance,
    InputArray 	mask = noArray(),
    int 	blockSize = 3,
    bool 	useHarrisDetector = false,
    double 	k = 0.04 
)

What this function does ,

1. First use cornerHarris Calculate the measurement of each corner

2. In each pixel 3x3 The neighborhood range of performs maximum suppression

3. Each corner corresponds to Harris The minimum eigenvalue of the matrix is less than $qualityLevel\ast max(qualityMeasureMap(x,y))$, This corner will be discarded

4. According to quality measure Descending order

5. Remove those with distances less than maxDistance The corner of

• image： Single channel image
• corners： The output vector of the angle
• maxCorners: The maximum number of detected corners is supported
• qualityLevel: Control the quality level of the angle , For example, the best is 1500, qualityLevel by 0.01, be quality measure Less than 1500*0.01 What you want will be abandoned
• minDistance: The minimum distance between corners
• mask: Mask , Controls which part of the image to detect corners
• blockSize: The neighborhood size used in calculating the gradient correlation matrix , Reference resources cornerEigenValsAndVecs
• useHarrisDetector: Whether to use Harris Corner detection
• k:Harris Super parameter of corner detection

3. Example

#include <opencv2/imgproc.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgcodecs.hpp>
#include <iostream>

using namespace cv;
using namespace std;

Mat src, src_gray;


int maxCorners = 23;
int maxTrackbar = 100;
RNG rng(12345);

int thresh = 200;
int max_thresh = 255;
const char* source_window = "Source image";
const char* corners_window = "Corners detected";

void cornerHarris_demo( int, void* );
void goodFeaturesToTrack_Demo( int, void* );

int main( int argc, char** argv )
{
    
    CommandLineParser parser( argc, argv, "{@input | building.jpg | input image}" );
    src = imread( samples::findFile( parser.get<String>( "@input" ) ) );
    if ( src.empty() )
    {
    
        cout << "Could not open or find the image!\n" << endl;
        cout << "Usage: " << argv[0] << " <Input image>" << endl;
        return -1;
    }
    cvtColor( src, src_gray, COLOR_BGR2GRAY );
    namedWindow( source_window );
    createTrackbar( "Threshold: ", source_window, &thresh, max_thresh, cornerHarris_demo );
    imshow( source_window, src );
    // cornerHarris_demo( 0, 0 );
    goodFeaturesToTrack_Demo( 0, 0 );
    waitKey();
    return 0;
}

void cornerHarris_demo( int, void* )
{
    
    int blockSize = 2;
    int apertureSize = 3;
    double k = 0.04;
    Mat dst = Mat::zeros( src.size(), CV_32FC1 );
    cornerHarris( src_gray, dst, blockSize, apertureSize, k );
    Mat dst_norm, dst_norm_scaled;
    normalize( dst, dst_norm, 0, 255, NORM_MINMAX, CV_32FC1, Mat() );
    convertScaleAbs( dst_norm, dst_norm_scaled );
    for( int i = 0; i < dst_norm.rows ; i++ )
    {
    
        for( int j = 0; j < dst_norm.cols; j++ )
        {
    
            if( (int) dst_norm.at<float>(i,j) > thresh )
            {
    
                circle( dst_norm_scaled, Point(j,i), 5,  Scalar(0), 2, 8, 0 );
            }
        }
    }
    namedWindow( corners_window );
    imshow( corners_window, dst_norm_scaled );
    imwrite("corner_grid.png", dst_norm_scaled);
}


void goodFeaturesToTrack_Demo( int, void* )
{
    
    maxCorners = MAX(maxCorners, 1);
    vector<Point2f> corners;
    double qualityLevel = 0.01;
    double minDistance = 10;
    int blockSize = 3, gradientSize = 3;
    bool useHarrisDetector = false;
    double k = 0.04;
    Mat copy = src.clone();
    goodFeaturesToTrack( src_gray,
                         corners,
                         maxCorners,
                         qualityLevel,
                         minDistance,
                         Mat(),
                         blockSize,
                         gradientSize,
                         useHarrisDetector,
                         k );
    cout << "** Number of corners detected: " << corners.size() << endl;
    int radius = 8;
    for( size_t i = 0; i < corners.size(); i++ )
    {
    
        circle( copy, corners[i], radius, Scalar(0, 0, rng.uniform(0, 256)), FILLED );
    }
    namedWindow( source_window );
    imwrite("corner_grid_st.png", copy);
    imshow( source_window, copy );
}