为什么 SIFT 用更少的八度层花费更多的时间？

Question

我在 OpenCV 4.5.2 中使用 SIFT 特征检测器。通过调整 cv::SIFT::create() 中的 nOctaveLayers 参数，我从 detectAndCompute():

得到这些结果

nOctaveLayers	KeyPoints	Time Cost (ms)
1	1026	63.41
2	1795	45.07
3	2043	45.74
4	2173	47.83
5	2224	51.86

据我了解，八度层数越少，计算量应该越少，但是为什么只有 1 个八度度层，SIFT 花费的时间要多得多？

我还分别测试了detect()和compute()，当nOctaveLayers为1时，它们都花费了更多的时间，这让我很困惑。

测试图像是here（来自TUM开放数据集）。在此先感谢您的帮助。

[为@Micka编辑]我的测试代码：

const int test_num = 100;
const int layers = 5;
cout << "layers: " << layers << endl;

auto sift = SIFT::create(0, layers);
vector<KeyPoint> kps;
Mat descs;

auto t1 = chrono::high_resolution_clock::now();
for (int i = 0; i < test_num; ++i)
    sift->detectAndCompute(img_src, noArray(), kps, descs);
auto t2 = chrono::high_resolution_clock::now();
cout << "num of kps: " << kps.size() << endl;
cout << "avg time cost: " << chrono::duration<double>(t2 - t1).count() * 1e3 / test_num << endl;

对于每个nOctaveLayers配置，我在代码中更改layers值，重新编译&运行&记录结果。

Answer 1

经过几个小时的分析，我终于找到了原因：GaussianBlur。

SIFT算法的流水线为：

创建初始图像：将源图像的数据类型转换为float，将分辨率加倍，并执行GaussianBlur (sigma=1.56)
构建高斯金字塔
寻找关键点：构建DoG金字塔并寻找尺度space极值
计算描述符

八度数根据图像分辨率计算（参见here）。 nOctaveLayers 控制每个八度音阶的层数（nOctaveLayers + 3 用于高斯金字塔）。

确实，当nOctaveLayers增加时，层数和关键点数都会增加。结果，步骤 3 和 4 的时间成本增加了。但是在并行计算中，这个时间增量并不是很显着（几毫秒）。

相比之下，步骤 2 花费的时间超过总时间的一半。 nOctaveLayers 为 3 时耗时 25.27 毫秒（43.49 毫秒），nOctaveLayers 为 1 时耗时 51.16 毫秒（63.10 毫秒）。那么，为什么会这样？

因为层数越少，GaussianBlur() 的 sigma 增加得更快，这对 GaussianBlur() 消耗的时间至关重要。请参阅下面的测试：

vector<double> sig1 = { 1.6, 2.77128, 5.54256, 11.0851 };
vector<double> sig3 = { 1.6, 1.22627, 1.54501, 1.94659, 2.45255, 3.09002 };
vector<double> sig5 = { 1.6, 0.9044, 1.03888, 1.19336, 1.37081, 1.57465, 1.8088, 2.07777 };

auto blurTest = [](const vector<double>& sigs, const string& label) {
    const int test_num = 100;
    auto t1 = chrono::high_resolution_clock::now();
    for (int i = 0; i < test_num; ++i) {
        vector<Mat> pyr;
        pyr.resize(sigs.size());
        pyr[0] = Mat::zeros(960, 1280, CV_32FC1);
        for (size_t i = 1; i < sigs.size(); ++i)
            GaussianBlur(pyr[i - 1], pyr[i], Size(), sigs[i], sigs[i]);
    }
    auto t2 = chrono::high_resolution_clock::now();
    auto time = chrono::duration<double>(t2 - t1).count() * 1e3 / test_num;
    cout << label << ": " << time << " ms\n";
};

blurTest(sig1, "1");
blurTest(sig3, "3");
blurTest(sig5, "5");

/* output:
1: 45.3958 ms
3: 28.5943 ms
5: 31.4827 ms
*/

当nOctaveLayers为1、3、5时，上面的代码模拟buildGaussianPyramid()。sigma值来自cv::SIFT计算。这解释了为什么当 nOctaveLayers 为 1 时 SIFT 花费更多时间。

为什么 SIFT 用更少的八度层花费更多的时间？

Why SIFT costs more time with fewer octave layers?

opencv

time-complexity

computer-vision

sift