c++ - opencv中矩阵的超快中位数(与matlab一样快)

Question

我在openCV中写了一些代码，想找到一个非常大的矩阵数组(单 channel 灰度， float )的中值。

我尝试了几种方法，例如对数组进行排序(使用 std::sort)和选择中间条目，但与 matlab 中的中值函数相比，它非常慢。准确地说，在 matlab 中需要 0.25 秒的内容在 openCV 中需要超过 19 秒。

我的输入图像最初是 12 位灰度图像，尺寸为 3840x2748(约 10.5 兆像素)，转换为浮点 (CV_32FC1)，其中所有值现在都映射到范围 [0,1] 并在某个点我通过调用请求中值的代码:

double myMedianValue = medianMat(Input);

函数medianMat在哪里:

double medianMat(cv::Mat Input){    
    Input = Input.reshape(0,1); // spread Input Mat to single row
    std::vector<double> vecFromMat;
    Input.copyTo(vecFromMat); // Copy Input Mat to vector vecFromMat    
    std::sort( vecFromMat.begin(), vecFromMat.end() ); // sort vecFromMat
        if (vecFromMat.size()%2==0) {return (vecFromMat[vecFromMat.size()/2-1]+vecFromMat[vecFromMat.size()/2])/2;} // in case of even-numbered matrix
    return vecFromMat[(vecFromMat.size()-1)/2]; // odd-number of elements in matrix
}

我自己对函数 medinaMat 以及各个部分进行了计时 - 正如预期的那样，瓶颈在于:

std::sort( vecFromMat.begin(), vecFromMat.end() ); // sort vecFromMat

这里有人有有效的解决方案吗？

谢谢!

编辑 我尝试使用 Adi Shavit 的答案中给出的 std::nth_element 。

函数 medianMat 现在读作:

double medianMat(cv::Mat Input){    
    Input = Input.reshape(0,1); // spread Input Mat to single row
    std::vector<double> vecFromMat;
    Input.copyTo(vecFromMat); // Copy Input Mat to vector vecFromMat
    std::nth_element(vecFromMat.begin(), vecFromMat.begin() + vecFromMat.size() / 2, vecFromMat.end());
    return vecFromMat[vecFromMat.size() / 2];
}

运行时间已从超过 19 秒降至 3.5 秒。这仍然远不及使用中值函数在 Matlab 中的 0.25 秒...

Answer 1

排序并取中间元素并不是找到中位数的最有效方法。它需要 O(n log n) 次操作。

对于 C++，您应该使用 std::nth_element() 并取中间迭代器。这是一个 O(n) 操作:

nth_element is a partial sorting algorithm that rearranges elements in [first, last) such that:

• The element pointed at by nth is changed to whatever element would occur in that position if [first, last) was sorted.
• All of the elements before this new nth element are less than or equal to the elements after the new nth element.

另外，您的原始数据是 12 位整数。您的实现做了一些使与 Matlab 的比较有问题的事情:

1. 您已转换为 float (CV_32FC1 或 double 或两者兼有)，成本高且需要时间
2. 代码有一个额外的拷贝到 vector<double>
3. 浮点运算，尤其是 double 运算的成本高于整数。

假设您的图像在内存中是连续的，就像 OpenCV 的默认设置一样，您应该使用 CV_16C1 , 并在 reshape() 之后直接处理数据数组

另一个应该非常快的选项是简单地构建图像的直方图 - 这是图像的单次传递。然后，处理直方图，找到对应于每边一半像素的 bin - 这最多是 bins 的一次传递。

OpenCV 文档有 several tutorials on如何建立直方图。获得直方图后，累积 bin 值直到通过 3840x2748/2。这个箱子是你的中位数。