我正在尝试评估一些基本图像过滤算法的复杂性。我想知道你是否可以验证这个理论；
对于像 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)
最终，卷积滤波器线性依赖于像素数与邻域像素数的乘积。
如果您有任何指向记录此内容的论文的链接，我们将不胜感激。
亲切的问候，
加文
最佳答案
O(MN) 似乎是正确的，如果我理解对于图像中的每个像素，卷积是邻域 N 中像素值的调整，而不管 N 是正方形。 N 可能是最适合的三角形......但是如果为图像中的每个像素调整邻域中的像素，那么 O(MN) 更有意义，因为依赖性在于源图像中每个像素调整的像素。
有趣的是，在一个非常规邻域中，一些像素可能比其他像素更多地被邻域掩码调整，但 O(MN) 仍然有效。
如果邻域位于像素 P 的中心，然后移动到不在邻域中的下一个 P(意味着每个像素都变换一次)，那么这不成立。
关于analysis - 基本复杂性问题 - 卷积，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/959524/