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

Question

我在openCV中编写了一些代码,想要找到一个非常大的矩阵数组的中值(单通道灰度,浮点数).

我尝试了几种方法,例如对数组进行排序(使用std :: sort)并选择中间条目,但在与matlab中的中位函数进行比较时,它非常慢.确切地说 - 在matlab中需要0.25秒才能在openCV中花费超过19秒.

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

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是一种部分排序算法,它重新排列元素,[first, last)使得:

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

此外,您的原始数据是12位整数.您的实现做了一些事情,使得与Matlab的比较成问题:

1. 您转换为浮点(CV_32FC1或双倍或两者)这是昂贵的,需要时间
2. 该代码有一个额外的副本 vector<double>
3. 浮点运算,特别是双数运算的成本高于整数.

假设您的图像在内存中是连续的,这是您应该使用的OpenCV的默认值,CV_16C1之后直接在数据数组上工作reshape()

另一个应该非常快的选择是简单地构建图像的直方图 - 这是图像上的单个传递.然后,处理直方图,找到对应于每一半像素的二进制位 - 这最多只是一次通过二进制位.

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

Answer 2

好.

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

我基本上为原始输入创建了一个直方图,其中包含2 ^ 12 = 4096个二进制位,计算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表格两端的项目.