2D 特征跟踪 – 第 1 部分：检测

2D 特征跟踪 - 第 1 部分：检测

交通图像上检测到的关键点

你是否曾经想过手机是如何在视频中跟踪你的脸部随着你移动的呢？或者自动驾驶汽车如何保持对道路上其他车辆的跟踪？所有这些惊人的成就都是通过2D特征跟踪实现的，这是一种计算机视觉技术，允许在视频中跟踪对象。

2D 特征跟踪大致分为三个步骤：

关键点检测：此步骤涉及查找图像中的独特点或特征。这些关键点通常不会随比例、照明和旋转的变化而变化，这使得它们对于随着时间的推移跟踪对象非常有用。
特征描述：此步骤涉及为每个关键点创建唯一的描述符。该描述符用于匹配帧之间的关键点，从而允许跟踪对象。
特征匹配：此步骤涉及查找不同帧中关键点之间的匹配。这是通过比较关键点的描述符来完成的。

2D 特征跟踪是一种强大的技术，可用于多种应用，包括：

对象跟踪：这是 2D 特征跟踪最常见的应用。对象跟踪可用于跟踪视频中的人、车辆和其他对象。这是自动驾驶汽车中最常见的用例。
视频稳定：此技术可用于消除视频中的相机抖动。这使得视频更流畅、更容易观看。
运动结构还原：此技术可用于从图像序列重建场景的 3D 结构。

2D 特征跟踪是一个快速发展的领域，新的算法一直在开发中。随着这些算法变得更加准确和高效，它们将在各种应用中发挥更大的作用。

我将从本文中的关键点检测开始，在一系列中等文章中介绍 2D 特征跟踪的所有三个步骤。

如果你有兴趣了解有关 2D 特征跟踪的更多信息，我鼓励你阅读我即将发布的有关特征描述和特征匹配的文章。

关键点检测

要开始跟踪特征，我们必须首先在图像中找到它们。图像中的这些“兴趣点”通常也称为关键点。关键点就像图像的“地标”。它们是最有可能对图像变化（例如旋转、缩放或照明）而言唯一且不变的点。

在本文中，我们将研究几种检测关键点的方法并评估它们的优缺点。我们的重点将是HARRIS、SHITOMASI、FAST、BRISK、ORB、AKAZE 和 SIFT算法。我们将根据它们检测到的关键点数量以及算法运行所需的时间来评估它们的有效性。

大多数关键点类型是通过分析图像上的亮度分布来确定的。亮度变化显着的区域称为高强度梯度，是潜在的关键点。在本次讨论中，我们将重点关注用于建立关键点检测核心概念的 HARRIS 检测器，同时简要介绍其他检测器。

1. Harris 角点探测器

Harris 角点检测器是最早的关键点检测算法之一。它通过寻找不同方向强度的显着变化来识别角点。该算法计算角点响应函数，它是局部强度变化的度量。然后根据该响应函数的阈值选择关键点。

关键点检测的思想是检测图像中可以在两个坐标方向上精确定位的独特结构。角点非常适合此目的，如下图所示。

接下来，为了以编程方式找到图像中的这些角点，我们需要计算沿 x 和 y 方向的强度梯度。与边缘等其他特征相比，角点将在两个方向上显示出强烈的梯度。

这是使用 SSD（平方差之和）完成的，SSD 的数学表达式如下。窗口函数“w”是矩形窗口或高斯窗口，它为下面的像素赋予权重。

将窗口“w”在 x 方向移动 u 并在 y 方向移动 v 后，该方程将旧窗口位置和新窗口位置的“w”内所有像素的平方差相加。

我们必须最大化这个函数 E(u,v) 来进行角点检测。这意味着我们必须最大化第二项。将泰勒展开式应用于上述方程并使用一些数学步骤，我们得到最终方程：

我们的数学变换的结果是一个矩阵M，现在可以方便地分析该矩阵以定位图像中每个像素位置(u, v)周围的局部窗口‘w’中的结构变化。在文献中，矩阵M通常被称为协方差矩阵。

为此，可以将矩阵 M 可视化为椭圆，其轴长和方向由其特征值和特征向量给出。如下图所示，较大的特征向量（用λ符号表示）指向最大强度变化的方向，而较小的特征向量指向最小变化的方向。因此，要识别角点，我们需要在图像中找到具有两个显着大的M特征值的位置。

基于 M 的特征值，Harris 检测器方法评估以下表达式，以得出每个像素位置的角响应测量，其中因子 k 是经验常数，通常在 k = 0.04–0.06 的范围内。

因此，特征值的大小决定了一个区域是角点、边缘还是平坦区域。像素越亮，Harris角响应越高。这个概念以下图的形式表示。

Harris角检测的结果是一个具有这些分数的灰度图像。适当分数的阈值化可以给出图像中的角点。为了定位角点，现在我们必须执行非极大值抑制（NMS）来：

确保我们获得局部邻域中角度最大的像素，并且
防止角点彼此太靠近，因为我们希望角点均匀分布在整个图像中。

非极大值抑制的概念是，取窗口内强度最高的像素点作为角点，其余为零。

下面是Harris角点检测在Open CV中的实现。

你还可以在我的 GitHub Repo 中找到实现：

https://github.com/nikhilnair8490/UdacityProjects/tree/main/Sensor_Fusion_Engineer/Camera/Lesson%204%20-%20Tracking%20Image%20Features/Harris%20Corner%20Detection?source=post_page—–d7a4cae7c22e——————————–

 /**
 * @brief HARRIS keypoint detector
 * 
 * @param keypoints detected keypoints 
 * @param img input grayscale image
 * @param bVis visualization flag
 */
void detKeypointsHarris(std::vector<cv::KeyPoint> &keypoints, cv::Mat &img, double &time, bool bVis)
{
    // Detector parameters
    int blockSize = 2;     // for every pixel, a blockSize × blockSize neighborhood is considered
    int apertureSize = 3;  // aperture parameter for Sobel operator (must be odd)
    int minResponse = 100; // minimum value for a corner in the 8bit scaled response matrix
    double k = 0.04;       // Harris parameter (see equation for details)

    double t = (double)cv::getTickCount();
    // Detect Harris corners and normalize output
    cv::Mat dst, dst_norm, dst_norm_scaled;
    dst = cv::Mat::zeros(img.size(), CV_32FC1);
    cv::cornerHarris(img, dst, blockSize, apertureSize, k, cv::BORDER_DEFAULT);
    //std::cout<< "dst.size() = " << dst << std::endl;
    cv::normalize(dst, dst_norm, 0, 255, cv::NORM_MINMAX, CV_32FC1, cv::Mat());
    cv::convertScaleAbs(dst_norm, dst_norm_scaled);

    // Locate local maxima in the Harris response matrix 
    // and perform a non-maximum suppression (NMS) in a local neighborhood around 
    // each maximum. The resulting coordinates shall be stored in a list of keypoints 
    // of the type `vector<cv::KeyPoint>`.

    // Loop throught the harris response matrix and find maxima
    double maxOverlap = 0.0;
    for (size_t j =0; j <= dst_norm.rows; ++j)
    {
        for (size_t i = 0; i <= dst_norm.cols; ++i)
        {
            int response = (int)dst_norm.at<float>(j,i);
            if (response > minResponse) // only store points above a threshold as keypoints
            {
                cv::KeyPoint newKeyPoint;
                newKeyPoint.pt = cv::Point2f(i,j);
                newKeyPoint.size = 2*apertureSize;
                newKeyPoint.response = response;

                //Find if there is overlap between the new keypoint and the existing keypoints
                bool Overlap = false;
                for (auto it = keypoints.begin(); it != keypoints.end(); ++it)
                {
                    double kptOverlap = cv::KeyPoint::overlap(newKeyPoint, *it);
                    // If there is overlap, check if the new keypoint has a higher response
                    if (kptOverlap > maxOverlap)
                    {
                        Overlap = true;
                        // If the new keypoint has a higher response, replace the old keypoint with the new one
                        if (newKeyPoint.response > (*it).response)
                        {
                            *it = newKeyPoint;
                            break;
                        }
                    }
                }
                // If there is no overlap, add the new keypoint to the list
                if (!Overlap)
                {
                    keypoints.push_back(newKeyPoint);
                }
            }
        }
    }

2. SHITOMASI（Shi-Tomasi角点检测器）：

Shi-Tomasi 角点检测器是一种简单但有效的关键点检测器，基于 Harris 角点检测器。该算法使用梯度矩阵的特征值计算角响应函数。它计算每个像素处 2 x 2 梯度协方差矩阵的最小特征值。角点的两个特征值都高于阈值，使它们脱颖而出。

优点：简单，比Harris角点检测器性能更好，对噪声不太敏感。

缺点：仅限于角点检测，对缩放和旋转不完全不变。

OpenCV 实现：

// Detect keypoints in image using the traditional Shi-Thomasi detector
void detKeypointsShiTomasi(vector<cv::KeyPoint> &keypoints, cv::Mat &img, double &time, bool bVis)
{
    // compute detector parameters based on image size
    int blockSize = 4;       //  size of an average block for computing a derivative covariation matrix over each pixel neighborhood
    double maxOverlap = 0.0; // max. permissible overlap between two features in %
    double minDistance = (1.0 - maxOverlap) * blockSize;
    int maxCorners = img.rows * img.cols / max(1.0, minDistance); // max. num. of keypoints

    double qualityLevel = 0.01; // minimal accepted quality of image corners
    double k = 0.04;

    // Apply corner detection
    double t = (double)cv::getTickCount();
    vector<cv::Point2f> corners;
    cv::goodFeaturesToTrack(img, corners, maxCorners, qualityLevel, minDistance, cv::Mat(), blockSize, false, k);

    // add corners to result vector
    for (auto it = corners.begin(); it != corners.end(); ++it)
    {

        cv::KeyPoint newKeyPoint;
        newKeyPoint.pt = cv::Point2f((*it).x, (*it).y);
        newKeyPoint.size = blockSize;
        keypoints.push_back(newKeyPoint);
    }

3. FAST（加速分段测试的特点）：

FAST 专为速度至关重要的实时应用程序而设计。它通过比较中心像素与其周围像素的强度来识别角点。FAST 测试围绕候选角点像素的圆形图案中的一组像素。如果足够多的连续像素比中心像素更亮或更暗，则将其视为角点。

优点：速度极快，适合实时应用。

缺点：容易出现误报，对缩放和旋转不具有不变性。

OpenCV 实现：

// FAST detector
int threshold = 30; // difference between intensity of the central pixel and pixels of a circle around this pixel
bool bNMS = true;   // perform non-maxima suppression on keypoints
cv::FastFeatureDetector::DetectorType type = cv::FastFeatureDetector::TYPE_9_16;
detector = cv::FastFeatureDetector::create(threshold, bNMS, type);
t = (double)cv::getTickCount();
detector->detect(img, keypoints);
t = ((double)cv::getTickCount() - t) / cv::getTickFrequency();
cout << "FAST with n= " << keypoints.size() << " keypoints in " << 1000 * t / 1.0 << " ms" << endl;

4. BRISK（二进制鲁棒不变可扩展关键点）：

BRISK 旨在将速度与稳健性结合起来。它使用二进制描述符来提高效率。BRISK 通过分析像素周围强度差异的分布来检测关键点。它计算出对旋转和缩放变化具有鲁棒性的模式。然后通过比较围绕关键点的圆圈中的像素对来生成二进制描述符。

优点：对旋转和缩放变化具有鲁棒性，由于二进制描述符而计算速度更快。

缺点：可能不如其他一些探测器准确。

OpenCV 实现：

// BRISK detector
int threshold = 30; //  AGAST detection threshold score
int octaves = 3;   // detection octaves
float patternScale = 1.0f; //apply this scale to the pattern used for sampling the neighbourhood of a keypoint.

detector = cv::BRISK::create(threshold, octaves, patternScale);
t = (double)cv::getTickCount();
detector->detect(img, keypoints);
t = ((double)cv::getTickCount() - t) / cv::getTickFrequency();
cout << "BRISK with n= " << keypoints.size() << " keypoints in " << 1000 * t / 1.0 << " ms" << endl;

5. ORB（定向FAST和旋转BRIEF）：

ORB 将角点检测和特征描述结合在单个算法中。ORB 首先使用类似 FAST 的方法识别角点。然后，它计算定向的BRIEF描述符以捕获关键点特征。该方向有助于提高旋转的不变性。

优点：结合了角点检测和特征描述，在实时应用中表现良好。

缺点：在某些情况下可能不如其他检测器强大。

OpenCV 实现：

// ORB detector
int nfeatures = 5000; // The maximum number of features to retain
detector = cv::ORB::create(nfeatures);
t = (double)cv::getTickCount();
detector->detect(img, keypoints);
t = ((double)cv::getTickCount() - t) / cv::getTickFrequency();
cout << "ORB with n= " << keypoints.size() << " keypoints in " << 1000 * t / 1.0 << " ms" << endl;

6. AKAZE（Accelerated-KAZE）：

AKAZE 是 KAZE 关键点检测器的扩展，旨在实现不同尺度和变换的鲁棒性。AKAZE 使用非线性扩散来增强尺度不变关键点的检测。它采用多尺度方法来捕获不同级别的图像细节的关键点。

优点：在尺度和旋转方面具有鲁棒性，在不同的变换下表现良好。

缺点：与其他一些探测器相比相对较慢。

OpenCV 实现：

// AKAZE detector
detector = cv::AKAZE::create();
t = (double)cv::getTickCount();
detector->detect(img, keypoints);
t = ((double)cv::getTickCount() - t) / cv::getTickFrequency();
cout << "AKAZE with n= " << keypoints.size() << " keypoints in " << 1000 * t / 1.0 << " ms" << endl;

6.SIFT（尺度不变特征变换）：

SIFT 是一种广泛使用的算法，以其对缩放和旋转变化的鲁棒性而闻名。SIFT 通过识别高斯 (DoG) 尺度空间差异中的最大值和最小值来检测关键点。关键点描述符是通过考虑关键点周围各个方向的梯度来生成的。

优点：对尺度、旋转和光照变化具有较强的鲁棒性，被广泛使用且可靠。

缺点：计算略显密集，受专利保护（可能存在使用限制）。

OpenCV 实现：

// SIFT detector
detector = cv::SIFT::create();
//detector = cv::xfeatures2d::SIFT::create(); //Use this for old versions of OpenCV
t = (double)cv::getTickCount();
detector->detect(img, keypoints);
t = ((double)cv::getTickCount() - t) / cv::getTickFrequency();
cout << "SIFT with n= " << keypoints.size() << " keypoints in " << 1000 * t / 1.0 << " ms" << endl;

算法评估

为了比较这些算法，我分析了一系列 10 张图像，这些图像描绘了使用各种算法在交通中行驶的汽车。运行每种算法来检测所有 10 个图像中的关键点，并编译聚合数据以生成图表。你还可以在我的 GitHub 存储库上访问完整的实现。

https://github.com/nikhilnair8490/UdacityProjects/tree/main/Sensor_Fusion_Engineer/Camera/SFND_2D_Feature_Tracking-MidTermProject?source=post_page—–d7a4cae7c22e——————————–

下图显示了所有检测器算法在检测到的关键点数量、执行时间和每毫秒执行时间方面的比较。