加上金字塔后，opencv的速度比我的速度从快302倍，降低到0.105倍，也就是我的超opencv接近10倍了， 喜大普奔！FFT是YYDS，在这里金字塔也更加是YYDS。
搜索图尺寸 $1095\ast 680$,模板图尺寸 $89\ast 91$，金字塔层数:4层，向下回溯的邻域大小： $3\ast 3$。

分析

对于很大的搜索图可以采用图像金字塔的方式来减少计算量，金字塔每上一层，分辨率变为原来的1/4(图像高和宽都为下一层的一半)，下采样的层数越多，计算量越小，精度越差。基本的想法是用金字塔下采样，在顶层先做粗定位，然后逐层往下回溯，这样的话可以保持精度，而且减少计算量。

构建金字塔

int BuildPyramidImages(const cv::Mat& src, std::vector<cv::Mat>& py_images, const int level)
{
    if (src.empty()) return error_code::kImageEmpty;
    if (src.type() != CV_8UC1)
    {
        MYCV_ERROR1(error_code::kDoseNotSupportImageType);
        return error_code::kDoseNotSupportImageType;
    }
    if (src.rows < (1 << level) || src.cols < (1 << level))
    {
        std::string stream = "level is too large, src.rows=" + std::to_string(src.rows)
            + ",src.cols=" + std::to_string(src.cols) + ",level=" + std::to_string(level) 
            + ",2^level=" + std::to_string(1 << level);
        MYCV_ERROR2(error_code::kBadInput, stream);
        return error_code::kBadInput;
    }
    
    if (py_images.size() > 0) py_images.clear();

    py_images.emplace_back(src.clone());
    for (int i = 1; i < level; ++i)
    {
        cv::Mat dst;
        cv::GaussianBlur(py_images[i - 1], dst, cv::Size(3, 3), 1, 1);
        cv::resize(dst, dst, cv::Size(), 0.5, 0.5);
        py_images.emplace_back(dst);
    }

    return error_code::kSuccess;
}

金字塔用在NCC中

int NCCPyramid(const cv::Mat& source, const cv::Mat& target, const int level, float& x, float& y, float& score)
{
    // 0 0 0
    // 0 * 0
    // 0 0 0
    constexpr int extd = 1; // 在最优点周围扩展的搜索区域半径
    if (level <= 0 || level > 20)
    {
        MYCV_ERROR1(error_code::kBadInput);
        return error_code::kBadInput;
    }

    if (source.empty() || target.empty())
    {
        MYCV_ERROR1(error_code::kImageEmpty);
        return error_code::kImageEmpty;
    }
    std::vector<cv::Mat> src_py, tar_py;
    CHECK_RET(BuildPyramidImages(source, src_py, level));
    CHECK_RET(BuildPyramidImages(target, tar_py, level));

    x = 0, y = 0, score = 0;
    // 计算顶层的位置
    auto &src = src_py[level - 1];
    auto &tar = tar_py[level - 1];
    NCC(src, tar, x, y, score);
    
    for (int i = level - 2; i >= 0; --i)
    {
        auto &src = src_py[i];
        auto &tar = tar_py[i];

        // 把上层金字塔中的位置向下回溯
        int upx = static_cast<int>(x * 2);
        int upy = static_cast<int>(y * 2);

        // 获取当前层级上的搜索区域
        int tpx = upx - extd;
        int tpy = upy - extd;
        int btx = upx + tar.cols + extd;
        int bty = upy + tar.rows + extd;
        tpx = tpx >= 0 ? tpx : 0;
        tpy = tpy >= 0 ? tpy : 0;
        btx = btx < src.cols ? btx : src.cols;
        bty = bty < src.rows ? bty : src.rows;
        cv::Mat src_roi = src(cv::Rect(cv::Point(tpx, tpy), cv::Point(btx, bty)));

        // 计算NCC
        NCC(src_roi, tar_py[i], x, y, score);

        // 把x,y的位置从src_roi映射回src
        x += tpx;
        y += tpy;
    }

    return error_code::kSuccess;
}