OpenCV 中矩阵的超快速中值（与 MATLAB 一样快）

Question

我正在 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
}

我对函数

medianMat()

本身以及各个部分进行了计时 - 正如预期的那样，瓶颈在于：

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

是一种 部分排序 算法，可重新排列

[first, last)

中的元素，以便：

• 如果

  nth

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

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

您转换为浮点数（CV_32FC1或双精度或两者），这是昂贵且耗时的

1. 代码有一个额外的副本到
vector<double>
2. 浮点运算，尤其是双精度运算的成本高于整数运算。
假设您的图像在内存中是连续的，就像 OpenCV 的默认设置一样，您应该使用

CV_16C1

，并在

reshape()

 之后直接处理数据数组

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

bins

的单次传递。 OpenCV 文档有

几个

教程 关于如何构建直方图。获得直方图后，累积 bin 值，直到达到 3840x2748/2。这个垃圾箱是你的中位数。

好的。

Answer 2

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

我基本上为原始输入创建了一个包含 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; }

从原始数据中查找可能会更快。

Answer 3

由于原始数据有12位值，因此只有 4096 个不同的可能值。这是一张又漂亮又小的桌子！ 一次性遍历所有数据，并统计每个值有多少个 你有。这是一个 O(n) 的操作。那么很容易找到中位数， 只计算桌子两端的

size/2

项。