基本的复杂性问题 - 卷积

Question

我试图评估的一些基本的图像滤波算法的复杂性。我想知道，如果你能验证这个理论;

有关通过像逆像素滤波器的基本像素操作的数目与输入的大小呈线性增长（像素）和

让所述图像的边的S =长度 设M =＃像素输入

逆是顺序O（M）或O-（S ^ 2）的

在另一方面，一个卷积滤波器具有参数R，其确定所述邻域的大小，以在卷积每个滤波器建立的下一个像素值。

让卷积滤波器的R =半径

卷积是阶为O的（M *（（R + R * 2）^ 2）= O（M *（4R ^ 2）= O（MR ^ 2）

或者我应该让N =以像素为单位的卷积滤波器（邻近）？

的大小

O（M *（N））= O（MN）

最后一个卷积滤波器是线性地依赖于像素的数量和像素的邻域的数目的乘积。

如果你有到这个已被记录它，将不胜感激纸的任何链接。

此致

加文

Answer 1

O（MN）似乎是正确的，如果我明白，对于图像中的每个像素的卷积是像素值的在邻域N的调整，无论N是正方形的。 Ñ可能是最佳拟合的三角形...但提供在附近的像素被调整为图像然后O（MN）更有意义在每个像素中，由于依赖性在源图像中的每个像素调整的像素。

有趣的是，在非正规附近的一些像素可能由附近掩模比其他人更调节，但O（MN）将静置。

如果邻近上的像素P的中央，然后移动到下一个P，其不是在附近（这意味着每个像素被变换一次），那么这并不突出。