基本复杂性问题 - 卷积

我试图评估一些基本的图像过滤算法的复杂性。我想知道你是否可以验证这个理论;基本复杂性问题 - 卷积

对于由像逆像素滤波器操作的数目与输入的大小呈线性增长（像素）和

基本像素

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

逆是O（M）或O（S^2）的次序。

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

设R =半径卷积滤波器的

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

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

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

最终的卷积滤波器是线性取决于像素数量和邻域像素数量的乘积。

如果你有任何链接到这里已被记录的文件，将不胜感激。

此致

加文

来源

2009-06-06 gav

作业？无论如何，你最后的大噢，对我来说看起来很好。 – 2009-06-06 11:50:35

这是我撰写的关于移动设备限制的论文的一些背景。我正在为android手机制作图像过滤应用程序，我希望这将决定瓶颈的位置。我使用构建到树中的20个基本节点，这20个节点包含许多点操作，如Add，Or和Subtract。我也有一个卷积滤波器和一个中值滤波器，这是发生瓶颈的地方，我只是想将其正式化。对树叶的输入始终是相同的图像，它被转换并组合以获得根的输出。干杯 – gav 2009-06-06 12:07:06

O（MN）似乎是正确的，如果我明白，对于图像中的每个像素的卷积是像素值的在邻域N的调整，无论N为正方形的。 N可能是最佳拟合三角形...但是为邻近像素提供图像中的每个像素的调整，那么O（MN）更有意义，因为依赖性在源图像中每像素调整的像素中。有趣的是，在非规则邻域中，一些像素可能会被邻域掩码调整得比其他像素更多，但是O（MN）仍然会保持不变。

如果邻域在像素P上居中，然后移动到不在邻域内的下一个P（意味着每个像素被转换一次），那么这就不成立。

来源

2009-06-06 12:19:56

基本复杂性问题 - 卷积

回答

相关问题