CV03-03:Shi-Tomasi角点检测与强角点处理

作者: 杨强AT南京 | 来源:发表于2020-02-11 00:03 被阅读0次

本文汇总了OpenCV的特征检测API，并补充一个Harris算法之前的Shi-Tomasi算法，提供局部非最大角点抑制处理。这个算法在OpenCV实现就是goodFeaturesToTrack函数。我们实现的算法比OpenCV的算法性能存在差距，但我们的目的从理解出发，理解后可以能很快实现与OpenCV一样的优化。
程序在OpenCV4.2环境下可以运行获得结果。

序言

在OpenCV中特征检测主要提供三种特征检测的实现：
1. 边缘Edge
2. 角点Corner
3. 线与线段Line
4. 圆检测Circle

边缘检测
- Candy检测
  - void cv::Canny (InputArray image, OutputArray edges, double threshold1, double threshold2, int apertureSize=3, bool L2gradient=false)
- Candy检测变形函数（使用x，y差分）
  - void cv::Canny (InputArray dx, InputArray dy, OutputArray edges, double threshold1, double threshold2, bool L2gradient=false)
角点检测
- 特征值与特征向量计算：
  - void cv::cornerEigenValsAndVecs (InputArray src, OutputArray dst, int blockSize, int ksize, int borderType=BORDER_DEFAULT)
- Harris检测算法：基于特征值R响应值计算的判定方法
  - void cv::cornerHarris (InputArray src, OutputArray dst, int blockSize, int ksize, double k, int borderType=BORDER_DEFAULT)
- Shi-Tomasi检测算法：基于特征值的最小特征值判断方法
  - void cv::cornerMinEigenVal (InputArray src, OutputArray dst, int blockSize, int ksize=3, int borderType=BORDER_DEFAULT)
- 强角点检测算法：在Harris与Shi-Tomasi算法上提供更加准确的角点位置的算法。
  - 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)
  - void cv::goodFeaturesToTrack (InputArray image, OutputArray corners, int maxCorners, double qualityLevel, double minDistance, InputArray mask, int blockSize, int gradientSize, bool useHarrisDetector=false, double k=0.04)
    - 可以指定Sobel差分核大小。
- 亚像素级的角点位置检测（更加精确的角点位置计算）
  - void cv::cornerSubPix (InputArray image, InputOutputArray corners, Size winSize, Size zeroZone, TermCriteria criteria)
- 基于复空间导数的检测算法：
  - void cv::preCornerDetect (InputArray src, OutputArray dst, int ksize, int borderType=BORDER_DEFAULT)
线条与线段检测
- 线段检测算法：
  - Ptr< LineSegmentDetector > cv::createLineSegmentDetector (int _refine=LSD_REFINE_STD, double _scale=0.8, double _sigma_scale=0.6, double _quant=2.0, double _ang_th=22.5, double _log_eps=0, double _density_th=0.7, int _n_bins=1024)
- Hough检测算法：
  - void cv::HoughLines (InputArray image, OutputArray lines, double rho, double theta, int threshold, double srn=0, double stn=0, double min_theta=0, double max_theta=CV_PI)
  - void cv::HoughLinesPointSet (InputArray _point, OutputArray _lines, int lines_max, int threshold, double min_rho, double max_rho, double rho_step, double min_theta, double max_theta, double theta_step)
- 概率Hough检测算法：
  - void cv::HoughLinesP (InputArray image, OutputArray lines, double rho, double theta, int threshold, double minLineLength=0, double maxLineGap=0)
圆检测
- Hough检测算法：
  - void cv::HoughCircles (InputArray image, OutputArray circles, int method, double dp, double minDist, double param1=100, double param2=100, int minRadius=0, int maxRadius=0)

角点检测的说明：
- 这里的几个角点检测方法都是基于差分（导数）。

Shi-Tomasi检测算法

计算特征值与特征向量
- 这个特征值与特征向量是差分（Sobel）的协方差矩阵

    void cv::cornerEigenValsAndVecs (
        InputArray src,     // 输入图像
        OutputArray dst,    // 输出的特征值与特征向量，6通道，类型是CV_32FC(6)
                            // 因为没有定义CV_32FC6，所有只能调用宏CV_32FC，指定通道参数。
                            // 6个通道的数据格式分别是，特征值λ1，特征值λ2，特征向量1（u1， u2）特征向量(v1, v2)
        int blockSize,      // 差分和的领域窗口大小（没有采用高斯模糊，而是box模糊）
        int ksize,          // Sobel核大小
        int borderType=BORDER_DEFAULT)

协方差矩阵定义
- $M = \begin{bmatrix} \sum \limits _{S(p)}(\dfrac{dI}{dx})^2 & \sum \limits _{S(p)}\dfrac{dI}{dx} \dfrac{dI}{dy} \\ \sum \limits _{S(p)}\dfrac{dI}{dx} \dfrac{dI}{dy} & \sum \limits _{S(p)}(\dfrac{dI}{dy})^2 \end{bmatrix}$
Shi-Tomasi角点检测算法
- 取最小特征值作为输出就是Shi-Tomasi检测算法；
- OpenCV函数cornerMinEigenVal就是返回最小特征值。
Shi-Tomasi角点检测算法实现代码
- 包含OpenCV的标准实现算法。
- 下面的实现与OpenCV的实现效果完全一样。效果证明，实际上上面求特征值与特征向量的函数还是进行了高斯模糊处理的。

#include <iostream>
#include <cmath>
#include <climits>

#include <opencv2/opencv.hpp>
/*
    Shi_Tomasi角点检测算法
*/

int main(int argc, char **argv){
    cv::Mat img = cv::imread("corner.jpg");
    cv::Mat img_src;
    cv::cvtColor(img, img_src, cv::COLOR_BGR2GRAY);  // OpenCV读取图像的颜色是BGR，灰度是8位图像
    /*
     * 计算特征值与特征向量，
     * void cv::cornerEigenValsAndVecs  (   
     *   InputArray     src,
     *   OutputArray    dst,
     *   int    blockSize,
     *   int    ksize,
     *   int    borderType = BORDER_DEFAULT 
     * )    
     */
    cv::Mat eig_vecs;
    cv::cornerEigenValsAndVecs(img_src, eig_vecs, 5, 9);
    /*
     * 使用特征值实现Harris角点检测与Shi-Tomasi角点检测算法
     */
    cv::Mat harris(eig_vecs.rows, eig_vecs.cols, CV_32FC1);
    cv::Mat shi_tomasi(eig_vecs.rows, eig_vecs.cols, CV_32FC1);
    
    float k =0.04;
    for(int y = 0; y < eig_vecs.rows; y++){
        for(int x = 0; x < eig_vecs.cols; x++){
            cv::Vec6f val = eig_vecs.at<cv::Vec6f>(y, x);
            harris.at<float>(y, x) = val[0] * val[1] - k * (val[0] + val[1]) * (val[0] + val[1]);
            shi_tomasi.at<float>(y, x) = val[0] < val[1] ? val[0] : val[1];
        }
    }
    cv::imwrite("harris.jpg", harris);
    cv::imwrite("shi_tomasi.jpg", shi_tomasi);
    /*
     * OpenCV实现的实现Harris角点检测与Shi-Tomasi角点检测算法
     * 
     */
    cv::Mat harris_cv, shi_tomasi_cv;
    cv::cornerHarris(img_src, harris_cv, 5, 9, 0.04);
    cv::cornerMinEigenVal(img_src, shi_tomasi_cv, 5, 9);
    cv::imwrite("harris_cv.jpg", harris_cv);
    cv::imwrite("shi_tomasi_cv.jpg", shi_tomasi_cv);
    return 0;
}

强角点检测算法

函数定义

void cv::goodFeaturesToTrack(
    InputArray image,                         // 原图像
    OutputArray corners,                      // 输出的角点坐标
    int         maxCorners,                   // 控制输出角点的最大数，对焦点排序吗，取前面maxCorners个角点。
    double      qualityLevel,                 // 
    double      minDistance,                  // 
    InputArray  mask = noArray(),             // 用来控制计算角点的区域
    int         blockSize = 3,                // 滑动窗体的大小
    bool        useHarrisDetector = false,    // 角点的侦测算法
    double      k = 0.04                      // Harris才需要的参数，上面一个参数为false（Shi-Tomasi算法），这个参数无效。
)

重载的参数扩展函数

void cv::goodFeaturesToTrack(
    InputArray    image,
    OutputArray   corners,
    int           maxCorners,
    double        qualityLevel,
    double        minDistance,
    InputArray    mask,
    int           blockSize,
    int           gradientSize,                           // 比另外一个重载函数多的参数，Sobel卷积核大小
    bool          useHarrisDetector = false,
    double        k = 0.04 
)

两个重要参数解释
1. qualityLevel
  - 这个参数是争对最大角点而言的，小于 $\texttt{qualityLevel} \cdot \max_{x,y} qualityMeasureMap(x,y)$ 的角点被放弃，
  - 源代码中基本上是简单暴力使用、：
    - minMaxLoc( eig, 0, &maxVal, 0, 0, _mask );
    - threshold( eig, eig, maxVal*qualityLevel, 0, THRESH_TOZERO );
2. minDistance
  - 会丢弃带最强角点距离小于minDistance的角点。
  - 如果为0或者小于0，就是不限制距离。
3. corners
  - 输出的是角点的坐标数组。（列向量）
  - 维度dims = 2，cols = 1, type = CV_32FC2, depth = CV_32F
  - 可以使用通用类型cv::Mat, 也可以直接使用std::vector<cv::Point2f>类型返回最强角点。
最强角点筛选算法
- 首先需要计算出角点的检测值（注意：源代码中采用了网格算法，可以降低循环次数，这里为了理解，就采用了没有优化的算法）
1. 局部非最大抑制（最强角点）
  1. 计算角点检测值的最大值 maxVal；
  2. 根据qualityLevel条件，对小于maxVal*qualityLevel的角点检测值置0.
  3. 对阈值过滤后的角点检测值做3 * 3的膨胀（这是局部非最大抑制的方法）
  4. 循环判定，所有像素的角点检测值没有膨胀就是最强角点。
2. 距离与最大角点数条件筛选
  1. 对最强角点排序；
  2. 循环排序后的最强角点，最强角点分成两个部分：满足条件的最强角点，待判定的最强角点；
  3. 每次待判定的最强角点循环与满足条件的最强角点计算距离，满足就添加到满足条件的最强角点，否则继续下一个待检测最强角点。
  4. 判定满足条件的最强角点是否超过设置的最大数，超过就终止处理，否则继续。

算法实现代码
- 代码参考了和源代码（其中局部非最大抑制就是参考源代码的，，否则就要全部自己撸代码）
  - 其中使用了源代码中的内存块的使用，以及通过指针的方式来处理，巧妙的坚决了角点检测值与角点坐标的存储问题。
- 代码没有实现遮罩功能，只能对整幅图像处理，对局部图像的无法处理。

void good_features(
    cv::Mat &image, 
    cv::Mat &corners, 
    int maxCorners,                 // 允许为负数，表示所有强角点
    double qualityLevel,  
    double minDistance,             // 允许为负数，表示没有距离
    int blockSize, 
    int gradientSize, 
    bool useHarrisDetector, 
    double k){
    // -------------------------手工实现
    // 1. 计算角点，根据useHarrisDetector选择Harris算法还是Shi-Tomasi算法
    cv::Mat eig;
    if(useHarrisDetector){
        cornerHarris( image, eig, blockSize, gradientSize, k);
    }else{
        cornerMinEigenVal(image, eig, blockSize, gradientSize);
    }

    // 2. 局部非最大抑制
    double maxVal = 0;
    cv::Mat  tmp; 
    // 计算最大特征值  
    cv::minMaxLoc(eig, NULL, &maxVal);   // 第二个参数是返回最小值，使用空指针表示不需要返回
    // qualityLevel参数进行阈值过滤
    cv::threshold( eig, eig, maxVal*qualityLevel, 0, cv::THRESH_TOZERO);
    cv::dilate(eig, tmp, cv::Mat());    // 使用cv::Mat()表示3 * 3的膨胀 ，取周围邻域中最大值作为元素值
    // 循环判定，没有膨胀的就是最强角点

    std::vector<const float*> tmpCorners;  // 这里需要存房角点判别值与坐标，源代码中提供了一个巧妙地方式，直接使用原来eig中地址
                                           // 地址的好处就是既可以计算出坐标，还可以获取角点的判别值。
    cv::Size imgsize = image.size();
    // 循环判定膨胀值是否变化
    for( int y = 1; y < imgsize.height - 1; y++ ){      // 行
        const float* eig_data = (const float*)eig.ptr(y);
        const float* tmp_data = (const float*)tmp.ptr(y);
        for( int x = 1; x < imgsize.width - 1; x++ ){   // 列
            float val = eig_data[x];
            if( val != 0 && val == tmp_data[x])
                tmpCorners.push_back(eig_data + x);    // 存放地址，这是比较精妙的使用方式
        }
    }

    // --- 根据距离、角点最大个数等条件过滤角点
    std::sort( tmpCorners.begin(), tmpCorners.end(), greaterThanPtr());  // 进行降序排序

    std::vector<cv::Point2f> vec_corners;   // 存放结果
    size_t total = tmpCorners.size();   // 上面计算的强角点个数　
    size_t ncorners = 0;                // 计数器（用来记录已经挑选的强角点数量）
    if(minDistance < 1 ){    // 距离没有设置
        for(int i = 0; i < total; i++ ){
            // 计算偏移地址
            int ofs = (int)((const uchar*)tmpCorners[i] - eig.ptr());
            // 根据偏移地址计算强角点的坐标
            int y = (int)(ofs / eig.step);
            int x = (int)((ofs - y*eig.step)/sizeof(float));

            vec_corners.push_back(cv::Point2f((float)x, (float)y));
            ++ncorners;
            // 超过设置的最大值，则终止处理
            if( maxCorners > 0 && ncorners == maxCorners ){
                break;
            }
        }
    }
    else{
        // 过滤掉距离范围内的强角点（源代码采用网格管理，比对所有点进行循环性能要优化）
        /* 
         * 第一个点肯定是强角点，后面的点，必须与选择出来的强角点循环判定距离是否在指定范围内，范围内的抛弃
         * 这个算法是双重全循环，效率比较低，可以采用网格管理（只对网格周边的网格中的元素计算，这样不用所有都编译一次）。
         */
        minDistance *= minDistance;  // 为了不做平方根运算，这里把距离变成平方。 
        for(int i = 0; i < total; i++){
            // 计算坐标
            int ofs = (int)((const uchar*)tmpCorners[i] - eig.ptr());
            int y = (int)(ofs / eig.step);
            int x = (int)((ofs - y*eig.step)/sizeof(float));

            bool is_corrner = true;   // 默认是满足条件的强角点
            if(vec_corners.size() == 0){   // 第一个强角点，直接push
                vec_corners.push_back(cv::Point2f((float)x, (float)y));
                ++ncorners;
            }else{
                // 开始循环判定距离
                for(int j = 0; j < vec_corners.size(); j++){
                    // 计算距离
                    float dx = x - vec_corners[j].x;
                    float dy = y - vec_corners[j].y;
                    if(dx*dx + dy*dy < minDistance ){   
                        is_corrner = false;     // 只要有一个在范围，就不是满足条件的强角点
                        break;
                    }
                }
                if(is_corrner){   // 循环完毕都还是强角点，说明是满足条件的强角点。
                    vec_corners.push_back(cv::Point2f((float)x, (float)y));
                    ++ncorners;
                }
            }
            // 检测是否超过最大角点数限制
            if( maxCorners > 0 && ncorners == maxCorners ){
                    break; // 超过指定的角点数终止处理
            }
        }
    }
    // 返回数据，把vector转换为Mat，并输出
    cv::Mat(vec_corners).convertTo(corners, CV_32F);
}

效果比较
- 我们的实现结果与OpenCV的计算效果完全一样。当然效率要差不少。这种密集型计算，不适合在GPU上采用并发计算来提高效率。
- 运算后的图片这里不贴图了，直接贴实现完整源代码，可以在OpenCV4.2的C++环境下运行

#include <iostream>
#include <cmath>
#include <climits>

#include <opencv2/opencv.hpp>
/*
 * 强角点检测算法
 */
struct greaterThanPtr{    // Functor对象，使用指针形式比较两个值的大小
    bool operator () (const float * a, const float * b) const
    { return (*a > *b) ? true : (*a < *b) ? false : (a > b); }
};

void good_features(
    cv::Mat &image, 
    cv::Mat &corners, 
    int maxCorners, 
    double qualityLevel, 
    double minDistance, 
    int blockSize, 
    int gradientSize, 
    bool useHarrisDetector=false, 
    double k=0.04);

void call_opencv(){
    cv::Mat img = cv::imread("corner.jpg");
    cv::Mat img_src;
    cv::cvtColor(img, img_src, cv::COLOR_BGR2GRAY);  // OpenCV读取图像的颜色是BGR，灰度是8位图像

    /*
     * OpenCV标准的强角点检测算法
     */
    cv::Mat corners;
    // std::vector<cv::Point2f> corners;
    cv::goodFeaturesToTrack(img_src, corners, 150, 0.01, 10, cv::noArray(), 5, 11, false, 0.04);
    std::cout << corners.dims << "," << corners.rows << "," << corners.cols << std::endl;
    std::cout << corners.type() << "->CV_32FC2:" << CV_32FC2 << std::endl;
    std::cout << corners.depth() << "->CV32F:"<< CV_32F << std::endl;
    std::cout << corners.channels() << std::endl;
    for(int i = 0; i < corners.rows; i++){
        cv::circle(img, corners.at<cv::Point2f>(i), 4, cv::Scalar(255, 0, 0, 255), 2, 8, 0);
    }
    cv::imwrite("corner_cv.jpg", img);
}

void call_myimpl(){
    cv::Mat img = cv::imread("corner.jpg");
    cv::Mat img_src;
    cv::cvtColor(img, img_src, cv::COLOR_BGR2GRAY);  // OpenCV读取图像的颜色是BGR，灰度是8位图像
    /*
     * 手工实现强角点检测算法
     */
    cv::Mat corners;
    // std::vector<cv::Point2f> corners;
    good_features(img_src, corners, 150, 0.01, 10, 5, 11, false, 0.04);
    std::cout << corners.dims << "," << corners.rows << "," << corners.cols << std::endl;
    std::cout << corners.type() << "->CV_32FC2:" << CV_32FC2 << std::endl;
    std::cout << corners.depth() << "->CV32F:"<< CV_32F << std::endl;
    std::cout << corners.channels() << std::endl;
    for(int i = 0; i < corners.rows; i++){
        cv::circle(img, corners.at<cv::Point2f>(i), 4, cv::Scalar(255, 0, 0, 255), 2, 8, 0);
    }
    cv::imwrite("corner_good.jpg", img);
}

int main(int argc, char **argv){
    call_opencv();
    std::cout << "------------------------------" << std::endl;
    call_myimpl();
    return 0;
}

void good_features(
    cv::Mat &image, 
    cv::Mat &corners, 
    int maxCorners,                 // 允许为负数，表示所有强角点
    double qualityLevel,  
    double minDistance,             // 允许为负数，表示没有距离
    int blockSize, 
    int gradientSize, 
    bool useHarrisDetector, 
    double k){
    // -------------------------手工实现
    // 1. 计算角点，根据useHarrisDetector选择Harris算法还是Shi-Tomasi算法
    cv::Mat eig;
    if(useHarrisDetector){
        cornerHarris( image, eig, blockSize, gradientSize, k);
    }else{
        cornerMinEigenVal(image, eig, blockSize, gradientSize);
    }

    // 2. 局部非最大抑制
    double maxVal = 0;
    cv::Mat  tmp; 
    // 计算最大特征值  
    cv::minMaxLoc(eig, NULL, &maxVal);   // 第二个参数是返回最小值，使用空指针表示不需要返回
    // qualityLevel参数进行阈值过滤
    cv::threshold( eig, eig, maxVal*qualityLevel, 0, cv::THRESH_TOZERO);
    cv::dilate(eig, tmp, cv::Mat());    // 使用cv::Mat()表示3 * 3的膨胀 ，取周围邻域中最大值作为元素值
    // 循环判定，没有膨胀的就是最强角点

    std::vector<const float*> tmpCorners;  // 这里需要存房角点判别值与坐标，源代码中提供了一个巧妙地方式，直接使用原来eig中地址
                                           // 地址的好处就是既可以计算出坐标，还可以获取角点的判别值。
    cv::Size imgsize = image.size();
    // 循环判定膨胀值是否变化
    for( int y = 1; y < imgsize.height - 1; y++ ){      // 行
        const float* eig_data = (const float*)eig.ptr(y);
        const float* tmp_data = (const float*)tmp.ptr(y);
        for( int x = 1; x < imgsize.width - 1; x++ ){   // 列
            float val = eig_data[x];
            if( val != 0 && val == tmp_data[x])
                tmpCorners.push_back(eig_data + x);    // 存放地址，这是比较精妙的使用方式
        }
    }

    // --- 根据距离、角点最大个数等条件过滤角点
    std::sort( tmpCorners.begin(), tmpCorners.end(), greaterThanPtr());  // 进行降序排序

    std::vector<cv::Point2f> vec_corners;   // 存放结果
    size_t total = tmpCorners.size();   // 上面计算的强角点个数　
    size_t ncorners = 0;                // 计数器（用来记录已经挑选的强角点数量）
    if(minDistance < 1 ){    // 距离没有设置
        for(int i = 0; i < total; i++ ){
            // 计算偏移地址
            int ofs = (int)((const uchar*)tmpCorners[i] - eig.ptr());
            // 根据偏移地址计算强角点的坐标
            int y = (int)(ofs / eig.step);
            int x = (int)((ofs - y*eig.step)/sizeof(float));

            vec_corners.push_back(cv::Point2f((float)x, (float)y));
            ++ncorners;
            // 超过设置的最大值，则终止处理
            if( maxCorners > 0 && ncorners == maxCorners ){
                break;
            }
        }
    }
    else{
        // 过滤掉距离范围内的强角点（源代码采用网格管理，比对所有点进行循环性能要优化）
        /* 
         * 第一个点肯定是强角点，后面的点，必须与选择出来的强角点循环判定距离是否在指定范围内，范围内的抛弃
         * 这个算法是双重全循环，效率比较低，可以采用网格管理（只对网格周边的网格中的元素计算，这样不用所有都编译一次）。
         */
        minDistance *= minDistance;  // 为了不做平方根运算，这里把距离变成平方。 
        for(int i = 0; i < total; i++){
            // 计算坐标
            int ofs = (int)((const uchar*)tmpCorners[i] - eig.ptr());
            int y = (int)(ofs / eig.step);
            int x = (int)((ofs - y*eig.step)/sizeof(float));

            bool is_corrner = true;   // 默认是满足条件的强角点
            if(vec_corners.size() == 0){   // 第一个强角点，直接push
                vec_corners.push_back(cv::Point2f((float)x, (float)y));
                ++ncorners;
            }else{
                // 开始循环判定距离
                for(int j = 0; j < vec_corners.size(); j++){
                    // 计算距离
                    float dx = x - vec_corners[j].x;
                    float dy = y - vec_corners[j].y;
                    if(dx*dx + dy*dy < minDistance ){   
                        is_corrner = false;     // 只要有一个在范围，就不是满足条件的强角点
                        break;
                    }
                }
                if(is_corrner){   // 循环完毕都还是强角点，说明是满足条件的强角点。
                    vec_corners.push_back(cv::Point2f((float)x, (float)y));
                    ++ncorners;
                }
            }
            // 检测是否超过最大角点数限制
            if( maxCorners > 0 && ncorners == maxCorners ){
                    break; // 超过指定的角点数终止处理
            }
        }
    }
    // 返回数据，把vector转换为Mat，并输出
    cv::Mat(vec_corners).convertTo(corners, CV_32F);
}

CV03-03:Shi-Tomasi角点检测与强角点处理

序言

Shi-Tomasi检测算法

强角点检测算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读