opencv中矩阵的超快中值（与matlab一样快）

我正在 openCV 中编写一些代码，想要找到一个非常大的矩阵数组（单通道灰度、浮点数）的中值。

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

我的输入图像最初是尺寸为 3840x2748（约 10.5 兆像素）的 12 位灰度图像，转换为浮点数（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

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

Thanks!

EDIT我尝试过使用 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 秒......

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

对于 C++ 你应该使用std::nth_element() http://en.cppreference.com/w/cpp/algorithm/nth_element并取中间的迭代器。这是一个 O(n) 操作：

nth_element is a 部分排序重新排列元素的算法[first, last)这样：

• 所指向的元素nth更改为该位置会出现的任何元素if [first, last)已排序.
• 这个新的第 n 个元素之前的所有元素都小于或等于新的第 n 个元素之后的元素。

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

1. 您转换为浮点数（CV_32FC1或双精度或两者），这是昂贵的并且需要时间
2. 该代码有一个额外的副本vector<double>
3. 对浮点数（尤其是双精度数）的运算比对整数的运算成本更高。

假设您的图像在内存中是连续的，这是您应该使用的 OpenCV 的默认值CV_16C1，然后直接处理数据数组reshape()

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

OpenCV 文档有several http://docs.opencv.org/doc/tutorials/imgproc/histograms/histogram_calculation/histogram_calculation.html#histogram-calculation 教程 http://docs.opencv.org/doc/tutorials/imgproc/histograms/histogram_equalization/histogram_equalization.html#histogram-equalization on http://docs.opencv.org/doc/tutorials/imgproc/histograms/histogram_comparison/histogram_comparison.html#histogram-comparison如何构建直方图。获得直方图后，累积 bin 值，直到达到 3840x2748/2。这个垃圾箱是你的中位数。