3

我正在尝试评估一些基本图像过滤算法的复杂性。我想知道你是否可以验证这个理论；

对于像 Inverse 这样的基本逐像素过滤器，操作的数量随着输入的大小（以像素为单位）线性增长，并且

令 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)

最终，卷积滤波器线性依赖于像素数和邻域中像素数的乘积。

如果您有任何指向已记录该文件的论文的链接，我们将不胜感激。

亲切的问候，

加文

4

1 回答 1

2

如果我理解对于图像中的每个像素，卷积是邻域 N 中像素值的调整，无论 N 是否为正方形，O(MN) 似乎是正确的。N 可能是最佳拟合三角形......但是如果为图像中的每个像素调整邻域中的像素，那么 O(MN) 更有意义，因为依赖关系在于源图像中每个像素调整的像素。

有趣的是，在非常规邻域中，邻域掩码可能会比其他像素更多地调整一些像素，但 O(MN) 仍然存在。

如果邻域位于像素 P 的中心，然后移动到不在邻域中的下一个 P（意味着每个像素都转换一次），那么这不成立。

于 2009-06-06T12:19:56.153 回答