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

Question

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

我尝试了几种方法，例如对数组进行排序（使用 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 秒……

原文由 CV_User 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

好的。

我实际上在发布问题之前尝试过这个，并且由于一些愚蠢的错误我取消了它作为解决方案的资格……无论如何它是：

我基本上用 2^12 = 4096 个 bin 为我的原始输入创建值的直方图，计算 CDF 并将其标准化，使其从 0 映射到 1，并找到 CDF 中等于或大于 0.5 的最小索引。然后我将此索引除以 12^2，从而找到请求的中值。现在它在 0.11 秒内运行（这是在没有大量优化的调试模式下），不到 Matlab 所需时间的一半。

这是函数（在我的例子中，nVals = 4096 对应于 12 位值）：

 double medianMat(cv::Mat Input, int nVals){

// COMPUTE HISTOGRAM OF SINGLE CHANNEL MATRIX
float range[] = { 0, nVals };
const float* histRange = { range };
bool uniform = true; bool accumulate = false;
cv::Mat hist;
calcHist(&Input, 1, 0, cv::Mat(), hist, 1, &nVals, &histRange, uniform, accumulate);

// COMPUTE CUMULATIVE DISTRIBUTION FUNCTION (CDF)
cv::Mat cdf;
hist.copyTo(cdf);
for (int i = 1; i <= nVals-1; i++){
    cdf.at<float>(i) += cdf.at<float>(i - 1);
}
cdf /= Input.total();

// COMPUTE MEDIAN
double medianVal;
for (int i = 0; i <= nVals-1; i++){
    if (cdf.at<float>(i) >= 0.5) { medianVal = i;  break; }
}
return medianVal/nVals; }

原文由 CV_User 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

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

nth_element 是一种 部分排序 算法，它重新排列 [first, last) 中的元素，这样：

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

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

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

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

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

OpenCV 文档有 几个 关于 如何构建直方图的 教程。获得直方图后，累积 bin 值直到通过 3840x2748/2。这个箱子是你的中位数。

原文由 Adi Shavit 发布，翻译遵循 CC BY-SA 4.0 许可协议