C++ 中的 Lucas-Kanade 跟踪

2025 年 5 月 13 日 | 阅读 8 分钟

引言

Lucas-Kanade 追踪 是一种计算机视觉算法，用于追踪一系列图像或视频帧中对象的运动。Lucas-Kanade 追踪算法由 Bruce D. Lucas 和 Takeo Kanade 于 1981 年开发，它依赖于光流，即由于对象或摄像机相对对象运动而在视频序列的两个连续帧之间出现的运动。Lucas-Kanade 追踪的主要概念是通过求解一个模拟亮度恒定假设的方程组来估计一个区域（通常是图像块或特征）从一帧到下一帧的位移。

该原理基于图像中一个小窗口内的运动可以通过一个线性函数很好地近似的假设。该算法使用此假设来计算围绕特定特征点窗口内的像素运动，这些特征点通常通过 Harris 角点检测方法或 Shi-Tomasi 角点检测方法来识别。之后，通过计算位移来跨帧追踪这些点。

Lucas-Kanade 追踪的优势在于其效率；它利用了运动的局部近似，因此非常适合实时应用。它遵循迭代过程，并通过多级（金字塔）光流的细化，可以处理更大的位移。因此，该算法在机器人和自动驾驶系统的对象追踪、视频稳定和运动估计等应用中非常受欢迎。

性质

基于光流的追踪
本质上，Lucas-Kanade 追踪基于光流的概念，光流是指图像序列中两个连续帧之间对象的视在运动。该算法基于亮度恒定假设，换句话说，像素的强度在帧之间不发生变化。因此，它计算像素位移以确定运动。这就是为什么 Lucas-Kanade 可以有效地追踪特征点（可能是角点或边缘），因为它们会随着时间在图像中移动。
基于局部窗口的运动估计
Lucas-Kanade 追踪函数基于对特征点周围的小局部窗口或图像块中像素运动的估计。该过程涉及求解线性方程组并模拟像素强度与其运动之间的关系。基于窗口的方法可以保证计算效率，因为它避免了处理整个图像，而只处理感兴趣的区域。局部处理因此使算法能够快速用于实时应用。
迭代细化
Lucas-Kanade 以迭代过程开始，以细化像素位移的估计。初始计算包括一个初始运动估计，并且在每次迭代中进行微小偏差，我们最小化原始输入和偏移输入之间窗口之间的差异。这个过程有助于获得期望的精度，因为这种小的或细微的运动通常无法估计。因此，这可以使算法正确地收敛到对象的正确运动。
金字塔实现
通过使用金字塔方法扩展 Lucas-Kanade 追踪算法，可以追踪帧之间较大的位移。C++ 实现（如 OpenCV）支持这种方法，它在图像的不同分辨率级别上工作，从粗糙到精细。在金字塔表示的情况下，可以在较粗的级别上追踪较大的运动，并将运动估计细化到较小的值。这使其在追踪具有大位移的对象时更加鲁棒和可靠。
特征点追踪
与估计每个像素运动的密集光流相比，Lucas-Kanade 是一种计算效率极高的追踪器。通常，该算法与角点检测算法（如 Shi-Tomasi 或 Harris 角点检测）结合使用，这些算法可以识别图像中最可靠的某些点。之后，这些点会随着后续帧进行追踪。对于需要非常高质量地追踪特定特征的应用，例如对象追踪、运动估计和视频稳定。
对图像质量和运动的敏感性
尽管 Lucas-Kanade 追踪效率很高，但其性能可能会受到某些因素的影响，例如光照变化、噪声和对象的巨大变形。它假定运动是小的且连续的，因此，如果运动或外观出现任何快速或非线性变化，追踪效果就会下降。然而，在实践中，使用金字塔表示和多尺度追踪将有助于捕捉精细和粗略的运动。

程序

1. 安装 OpenCV：您需要 OpenCV 来处理图像处理和光流计算。使用以下命令安装 OpenCV（如果在 Ubuntu 上使用 apt）

2. 如果您在 Windows 上工作，请遵循 OpenCV 的安装指南进行正确设置。

C++ 中 Lucas-Kanade 光流的代码

 
#include <opencv2/opencv.hpp>
#include <iostream>

using namespace cv;
using namespace std;

int main() {
    // Open a video file or webcam
    VideoCapture cap(0);  // Use 0 for webcam, or replace with video file path

    if (!cap.isOpened()) {
        cout << "Error: Could not open the camera or video stream." << endl;
        return -1;
    }

    // Variables to store previous and current frames
    Mat framePrev, frameCurr, grayPrev, grayCurr;
    
    // Take the first frame for initialization
    cap >> framePrev;
    if (framePrev.empty()) {
        cout << "Error: Failed to capture an initial frame." << endl;
        return -1;
    }
    cvtColor(framePrev, grayPrev, COLOR_BGR2GRAY);  // Convert to grayscale

    // Detect good features to track (e.g., corners)
    vector<Point2f> pointsPrev;
    goodFeaturesToTrack(grayPrev, pointsPrev, 100, 0.3, 7);

    // Create mask for drawing
    Mat mask = Mat::zeros(framePrev.size(), framePrev.type());

    while (true) {
        // Capture next frame
        cap >> frameCurr;
        if (frameCurr.empty()) {
            cout << "Error: Failed to capture the next frame." << endl;
            break;
        }
        cvtColor(frameCurr, grayCurr, COLOR_BGR2GRAY);  // Convert to grayscale

        // Calculate optical flow (i.e., track features)
        vector<Point2f> pointsCurr;
        vector<uchar> status;
        vector<float> err;

        // Compute optical flow using Lucas-Kanade method
        calcOpticalFlowPyrLK(grayPrev, grayCurr, pointsPrev, pointsCurr, status, err);

        // Update previous points for the next iteration
        vector<Point2f> pointsPrevNew;
        for (size_t i = 0; i < pointsPrev.size(); i++) {
            if (status[i]) {
                pointsPrevNew.push_back(pointsCurr[i]);
                // Draw the tracked points on the current frame
                circle(frameCurr, pointsCurr[i], 5, Scalar(0, 255, 0), -1);
            }
        }
        pointsPrev = pointsPrevNew;

        // Show the current frame with tracked points
        imshow("Lucas-Kanade Optical Flow", frameCurr);

        // Wait for the user to press a key
        if (waitKey(10) == 27) {  // Exit on pressing ESC
            break;
        }

        // Set current frame as previous frame for the next iteration
        grayPrev = grayCurr.clone();
    }

    // Release the video capture object
    cap.release();
    destroyAllWindows();
    return 0;
}   

您提供的 Lucas-Kanade 光流追踪程序的示例代码将是一种动态可视化，显示如何跨帧追踪某些特征点。它看起来会像这样：

当您运行程序时，它会显示一个摄像头馈送或视频，其中追踪的点用绿色圆圈表示。当对象在视频中移动时，这些点会跟随它们，从而让您直观地追踪运动。

如果您使用的是网络摄像头，输出将是实时视频，其中包含追踪到的特征点。
如果您使用的是视频文件，输出将是相同的，但来自视频流而不是实时馈送。

示例输出可视化

您正试图追踪摄像头前移动的对象（例如您的手）。

特征点：在您的手和手指的边缘处有一些小的红点，这些是检测到的角点或边缘。
运动路径：在手移动期间，每个特征点的先前位置通过绿线连接到其新位置，绿线表示运动方向和运动距离。
动态可视化：红点将根据手上的特征追踪运动，而绿线将追踪已经发生的运动。

复杂度

C++ 中 Lucas-Kanade 追踪的复杂性取决于几个因素，这些因素主要与图像的大小、要追踪的特征点数量以及用于计算光流的窗口大小有关。

1. 时间复杂度

影响时间复杂度的主要因素是：

特征点数量 nnn：通常，Lucas-Kanade 追踪应用于一组需要在帧之间追踪的特征点。
窗口大小 W×WW\\ \\times WW×W：算法在每个特征位置的中心小窗口中计算光流。对于每个特征，算法都会对该窗口中的所有像素求和，因此与单个特征元素相关的复杂度取决于窗口大小。

总体时间复杂度

O(n×W2×k)O(n \times W^2 \times k)O(n×W2×k)

其中

nnn 是要追踪的特征点数量，
W2W^2W2 表示您的窗口大小，并且由于您的窗口被假定为边长为 WWW 的正方形窗口，
kkk 是迭代次数（例如，如果您应用迭代细化，例如在使用金字塔 Lucas-Kanade 时）。

因此，时间复杂度线性地取决于特征点数量和窗口大小。您希望处理的图像维度越高，意味着特征点越多，复杂度就越高。

2. 空间复杂度

图像存储：取决于正在处理的图像的大小。假设每张图像的大小为 H×WH \\\\times WH×W，即 HHH 是高度，WWW 是宽度，那么两个连续帧将需要 O(H×W)O(H \\\\times W)O(H×W) 的空间。
特征点：您需要存储所有特征点的坐标。存储 nnn 个特征点的空间复杂度为 O(n)O(n)O(n)。
窗口存储：对于每个特征，算法都会对该窗口中的所有像素求和，因此与单个特征元素相关的复杂度取决于窗口大小。

总体空间复杂度

O(H×W+n)O(H \times W + n)O(H×W+n)

这主要是由于图像的存储。

结论

1. 关键概念总结

该方法利用 Lucas-Kanade 方法进行光流估计，主要用于追踪视频序列中的特征点。它依赖于连续帧之间的小运动，并使用局部窗口计算光流向量。

2. 实现优势

总的来说，C++ 中的实现因其速度和效率而提供了许多性能优势；特别是在使用 OpenCV 等库的应用中，为计算机视觉应用打开了许多可能性。

3. 准确性和鲁棒性

该方法在追踪方面表现出出色的鲁棒性，尤其是在移动对象的特征没有太多歧义且遮挡程度最小的情况下。这得益于通过最小二乘估计计算出的运动的稳定性。

4. 限制

Lucas-Kanade 方法效率很高，但仍然存在亮度一致性要求以及无法处理大运动或快速变化的场景的问题。它还受到遮挡和无特征区域的影响。

5. 应用

该追踪算法已用于各种应用，例如视频中的对象追踪、运动分析以及机器人技术，并表明它可以用于任何计算机视觉任务。

下一个主题C++ 中的 Strassen 算法

← 上一个下一个 →

C++ 中的 Lucas-Kanade 跟踪

引言

性质