如何在2d数组中找到最常见的int？

Question

好的,所以我刚开始考虑如何为Paint.NET实现一个新的图形插件,我需要知道如何在二维的整数数组中找到最常见的整数.是否有内置的C#方式来做到这一点？或者,有没有人有一个光滑的方式来做到这一点？

该数组看起来像这样:

300 300 300 300 300 300 300
  0 150 300 300 300 300 300
  0   0 150 300 300 300 300
  0   0   0   0 300 300 300
  0   0   0   0 150 300 300
  0   0   0   0   0 150 300
  0   0   0   0   0   0 300

我需要知道300是阵列中最常见的数字.如果没有"最常见",则只返回中心数(数组减少将始终为奇数x奇数)0.

我将使用"强力"算法实现这一点,除非你的专家可以更快地提出一些东西.

任何帮助将非常感谢.

谢谢!

编辑:更多信息......

这些值几乎总是非常多样化(比我的示例数组更加多样化).值将在0-360的范围内.根据算法的速度,阵列的大小将是5x5到大约17x17.对于大图像中的每个像素,结果将计算一次......因此更快更好.;)

Answer 1

你切片它至少是O(n*m) - 你将不得不至少看一次每个细胞.节约的地方是在寻找最常见之前累积每个值的计数; 如果你的整数在相对较小的范围内变化(它们是uint16,让我们说),那么你可以简单地使用平面数组而不是地图.

我猜你还可以保留当前最高和最接近的"最常见"和早期候选人的运行计数x,y,只要你小于(n*m) - (xy)的细胞留给看看,因为在那一点上,亚军不可能超过最佳候选人.

像这样的整数运算速度非常快; 即使对于百万像素图像,强力算法也应该只需要几毫秒.

我注意到你已经编辑了你的原始问题,说像素值从0..255 - 在这种情况下,绝对是一个简单的平面阵列; 它足够小,可以轻松放入l1 dcache中,并且可以快速查找平面阵列中的查找.

[编辑]:一旦你建立了直方图阵列,处理"没有最常见的数字"的情况就非常简单了:所有你要做的就是遍历它以找到"最多"和"第二大"常用数字; 如果它们同样频繁,那么根据定义,没有一个最常见的.

const int numLevels = 360; // you said each cell contains a number [0..360)
int levelFrequencyCounts[numLevels]; // assume this has been populated such that levelFrequencyCounts[i] = number of cells containing "i"
int mostCommon = 0, runnerUp = 0;
for (int i = 1 ; i < numLevels ; ++i)
{
  if ( levelFrequencyCounts[i] > levelFrequencyCounts[mostCommon] )
  {
    runnnerUp = mostCommon;
    mostCommon = i;
  }
}

if ( levelFrequencyCounts[mostCommon] != levelFrequencyCounts[runnerUp] )
{
   return mostCommon;
}
else
{
   return CenterOfInputData; // (something like InputData[n/2][m/2])
}

Answer 2

查看 Paint.NET 中的 LocalHistogramEffect 代码，特别是 LocalHistorgramEffect.RenderRect。

我遍历输入图像，维护每个源像素与目标像素的“r”像素的强度直方图。当遍历输出像素时，它将前沿添加到直方图并减去后沿。它可以很好地处理所有边缘情况，而且速度相当快。它是“中值”、“散焦”、“轮廓”和“消除噪音”效果的基础。

调整它来支持 Hue 而不是 RGB 强度将是相当简单的。

性能非常好，就您的目的而言，它的运行时间为 O(r^2+w r+n w)，其中 r 是半径，w 是图像的宽度，n 是直方图中的级别数。

-t杰克逊