광류법(Optical Flow)을 이용한 특징점 추적과 LK 알고리즘 이해

비주얼 SLAM이나 컴퓨터 비전 분야에서 카메라의 움직임을 추정할 때, 일반적으로 특징점을 추출하고 기술자(Descriptor)를 생성하여 매칭하는 과정을 거칩니다. 하지만 기술자 계산은 연산 비용이 높고, 텍스처가 부족한 환경에서는 특징점 매칭이 어렵다는 단점이 있습니다. 이를 해결하기 위해 두 가지 대안이 제시됩니다.

  1. 특징점의 위치(Keypoints)만 찾고 기술자 대신 광류법(Optical Flow)을 사용하여 이전 프레임의 점이 다음 프레임의 어디로 이동했는지 추적합니다.
  2. 특징점 자체를 추출하지 않고 픽셀의 밝기 정보를 직접 사용하는 직접법(Direct Method)을 적용합니다.

광류법은 첫 번째 방식에 해당하며, 특징점 매칭 단계를 최적화하여 연산 속도를 높이면서도 기존의 PnP나 대극 기하(Epipolar Geometry) 알고리즘을 그대로 사용할 수 있다는 장점이 있습니다.

Lucas-Kanade(LK) 광류법의 원리

광류법은 밝기 항구성 가정(Brightness Constancy Assumption)을 기반으로 합니다. 이는 "움직이는 물체의 특정 지점의 밝기는 시간이 변해도 일정하다"는 가설입니다.

시간 $t$에서의 픽셀 $(x, y)$의 밝기를 $I(x, y, t)$라고 할 때, $dt$ 시간 후 $(x+dx, y+dy)$로 이동했다면 다음과 같은 식이 성립합니다.

$$I(x, y, t) = I(x+dx, y+dy, t+dt)$$

이 식의 우변을 테일러 급수(Taylor expansion)로 1차 전개하면 다음과 같습니다.

$$I(x+dx, y+dy, t+dt) \approx I(x, y, t) + \frac{\partial I}{\partial x}dx + \frac{\partial I}{\partial y}dy + \frac{\partial I}{\partial t}dt$$

밝기가 변하지 않는다는 조건에 의해 도함수 항들의 합은 0이 되어야 합니다.

$$\frac{\partial I}{\partial x} \frac{dx}{dt} + \frac{\partial I}{\partial y} \frac{dy}{dt} = -\frac{\partial I}{\partial t}$$

여기서 $\frac{dx}{dt}$와 $\frac{dy}{dt}$는 우리가 구하고자 하는 픽셀의 속도 $u, v$이며, $\frac{\partial I}{\partial x}$와 $\frac{\partial I}{\partial y}$는 이미지상의 그래디언트 $I_x, I_y$입니다. 단일 픽셀로는 $u, v$ 두 미지수를 구할 수 없으므로, LK 광류법은 특정 윈도우(예: $w \times w$) 내의 모든 픽셀이 동일한 운동을 한다고 가정하여 최소자승법(Least Squares)으로 해를 구합니다.

가우스-뉴턴법을 이용한 광류 구현

광류 추적은 두 이미지 사이의 밝기 오차를 최소화하는 최적화 문제로 볼 수 있습니다. 아래는 서브픽셀 정밀도를 위해 이선형 보간법(Bilinear Interpolation)을 적용하고 가우스-뉴턴(Gauss-Newton) 방식으로 최적화하는 코드 구조입니다.

// 이선형 보간을 통한 픽셀 값 획득
inline float interpolatePixel(const cv::Mat &img, float px, float py) {
    if (px < 0) px = 0;
    if (py < 0) py = 0;
    if (px >= img.cols - 1) px = img.cols - 2;
    if (py >= img.rows - 1) py = img.rows - 2;

    int ix = static_cast<int>(px);
    int iy = static_cast<int>(py);
    float dx = px - ix;
    float dy = py - iy;

    const uchar* ptr = &img.data[iy * img.step + ix];
    return (1 - dx) * (1 - dy) * ptr[0] +
           dx * (1 - dy) * ptr[1] +
           (1 - dx) * dy * ptr[img.step] +
           dx * dy * ptr[img.step + 1];
}

// 가우스-뉴턴법 기반 단일 레벨 광류 추적
void trackOpticalFlowSingleLevel(
    const cv::Mat &prev_img,
    const cv::Mat &curr_img,
    const std::vector<cv::KeyPoint> &pts_prev,
    std::vector<cv::KeyPoint> &pts_curr,
    std::vector<bool> &is_tracked,
    bool use_inverse_form = true) {

    int patch_radius = 4;
    int max_iters = 10;

    for (size_t i = 0; i < pts_prev.size(); i++) {
        auto kp = pts_prev[i];
        double offset_x = pts_curr[i].pt.x - kp.pt.x;
        double offset_y = pts_curr[i].pt.y - kp.pt.y;

        Eigen::Matrix2d Hessian = Eigen::Matrix2d::Zero();
        Eigen::Vector2d bias = Eigen::Vector2d::Zero();
        double total_loss = 0, prev_loss = 0;

        for (int iter = 0; iter < max_iters; iter++) {
            bias = Eigen::Vector2d::Zero();
            if (!use_inverse_form) Hessian = Eigen::Matrix2d::Zero();
            total_loss = 0;

            for (int x = -patch_radius; x < patch_radius; x++) {
                for (int y = -patch_radius; y < patch_radius; y++) {
                    float error = interpolatePixel(prev_img, kp.pt.x + x, kp.pt.y + y) -
                                  interpolatePixel(curr_img, kp.pt.x + x + offset_x, kp.pt.y + y + offset_y);

                    Eigen::Vector2d J;
                    if (!use_inverse_form) {
                        J = -0.5 * Eigen::Vector2d(
                            interpolatePixel(curr_img, kp.pt.x + offset_x + x + 1, kp.pt.y + offset_y + y) -
                            interpolatePixel(curr_img, kp.pt.x + offset_x + x - 1, kp.pt.y + offset_y + y),
                            interpolatePixel(curr_img, kp.pt.x + offset_x + x, kp.pt.y + offset_y + y + 1) -
                            interpolatePixel(curr_img, kp.pt.x + offset_x + x, kp.pt.y + offset_y + y - 1)
                        );
                    } else if (iter == 0) {
                        J = -0.5 * Eigen::Vector2d(
                            interpolatePixel(prev_img, kp.pt.x + x + 1, kp.pt.y + y) -
                            interpolatePixel(prev_img, kp.pt.x + x - 1, kp.pt.y + y),
                            interpolatePixel(prev_img, kp.pt.x + x, kp.pt.y + y + 1) -
                            interpolatePixel(prev_img, kp.pt.x + x, kp.pt.y + y - 1)
                        );
                        Hessian += J * J.transpose();
                    }

                    bias += -error * J;
                    total_loss += error * error;
                    if (!use_inverse_form) Hessian += J * J.transpose();
                }
            }

            Eigen::Vector2d update = Hessian.ldlt().solve(bias);
            if (std::isnan(update[0])) {
                is_tracked[i] = false;
                break;
            }

            if (iter > 0 && total_loss > prev_loss) break;

            offset_x += update[0];
            offset_y += update[1];
            prev_loss = total_loss;
            if (update.norm() < 1e-3) break;
            is_tracked[i] = true;
        }
        pts_curr[i].pt = kp.pt + cv::Point2f(offset_x, offset_y);
    }
}

다중 레벨 이미지 피라미드(Multi-level Image Pyramid)

기본적인 LK 알고리즘은 픽셀의 이동량이 그래디언트 범위를 벗어날 정도로 클 경우 국소 최적점(Local Minimum)에 빠질 위험이 있습니다. 이를 보완하기 위해 이미지 피라미드를 사용합니다.

이미지 피라미드는 원본 영상을 단계적으로 축소하여 여러 층으로 구성합니다. 최상단(가장 작은 해상도) 층에서 먼저 광류를 계산하여 대략적인 이동량을 파악하고, 이를 다음 하위 층의 초기값으로 전달하는 Coarse-to-Fine 방식을 사용합니다.

  • 상위 레벨: 해상도가 낮아 큰 움직임도 작은 픽셀 변화로 나타나 추적이 용이합니다.
  • 하위 레벨: 상위 레벨의 결과를 바탕으로 세밀한 위치를 조정합니다.
void trackOpticalFlowMultiLevel(
    const cv::Mat &img1,
    const cv::Mat &img2,
    const std::vector<cv::KeyPoint> &kp1,
    std::vector<cv::KeyPoint> &kp2,
    std::vector<bool> &success) {

    int levels = 4;
    double scale_factor = 0.5;
    std::vector<cv::Mat> pyramid1, pyramid2;

    // 피라미드 생성
    for (int i = 0; i < levels; i++) {
        if (i == 0) {
            pyramid1.push_back(img1);
            pyramid2.push_back(img2);
        } else {
            cv::Mat m1, m2;
            cv::resize(pyramid1[i - 1], m1, cv::Size(), scale_factor, scale_factor);
            cv::resize(pyramid2[i - 1], m2, cv::Size(), scale_factor, scale_factor);
            pyramid1.push_back(m1);
            pyramid2.push_back(m2);
        }
    }

    // 최상단 레벨에 맞춰 좌표 스케일 조정
    std::vector<cv::KeyPoint> kp1_scaled, kp2_scaled;
    double top_scale = std::pow(scale_factor, levels - 1);
    for (auto &p : kp1) {
        cv::KeyPoint p_s = p;
        p_s.pt *= top_scale;
        kp1_scaled.push_back(p_s);
        kp2_scaled.push_back(p_s);
    }

    // Coarse-to-fine 추적
    for (int l = levels - 1; l >= 0; l--) {
        success.clear();
        trackOpticalFlowSingleLevel(pyramid1[l], pyramid2[l], kp1_scaled, kp2_scaled, success);

        if (l > 0) {
            for (auto &p : kp1_scaled) p.pt /= scale_factor;
            for (auto &p : kp2_scaled) p.pt /= scale_factor;
        }
    }

    for (auto &p : kp2_scaled) kp2.push_back(p);
}

이러한 피라미드 기반 광류법은 카메라의 급격한 회전이나 빠른 이동 상황에서도 안정적인 특징점 추적 성능을 보장하며, 계산 효율성 덕분에 실시간 SLAM 시스템에서 널리 활용됩니다.

태그: computer-vision optical-flow visual-slam image-pyramid OpenCV

10월 30일 19:44에 게시됨