基本复杂性问题 - 卷积
我正在尝试评估一些基本图像过滤算法的复杂性。 我想知道你是否可以验证这个理论；
对于像 Inverse 这样的基本逐像素过滤器，操作数量随着输入的大小（以像素为单位）线性增长，并且
让 S = 图像边的长度 令 M = # 个像素输入
Inverse 的阶数为 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)
卷积滤波器线性依赖于像素数和邻域中像素数的乘积。
最终， 如果有任何已记录此内容的论文的链接，我们将不胜感激
。
，加文
I'm trying to evaluate the complexity of some basic image filtering algorithms. I was wondering if you could verify this theory;
For a basic pixel by pixel filter like Inverse the number of operations grows linearly with the size of the input (In pixels) and
Let S = Length of the side of the image
Let M = # pixels input
Inverse is of order O(M) or O(S^2).
A convolution filter on the other hand has a parameter R which determines the size of the neighborhood to convolve in establishing the next pixel value for each filter.
Let R = Radius of convolution filter
Convolution is of order O(M*((R+R*2)^2) = O(M*(4R^2) = O(MR^2)
Or should I let N = the size of the convolution filter (Neighbourhood) in pixels?
O(M*(N)) = O(MN)
Ultimately a convolution filter is linearly dependent on the product of the number of pixels and the number of pixels in the neighbourhood.
If you have any links to a paper where this has been documented it would be greatly appreciated.
Kind regards,
Gavin
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果我理解对于图像中的每个像素，卷积是邻域 N 中像素值的调整，无论 N 是平方的，O(MN) 似乎是正确的。 N 可能是最佳拟合三角形...但是如果邻域中的像素针对图像中的每个像素进行调整，则 O(MN) 更有意义，因为依赖性在于源图像中每个像素调整的像素。
有趣的是，在非规则邻域中，某些像素可能比其他像素更多地被邻域掩模调整，但 O(MN) 仍然成立。
如果邻域位于像素 P 的中心，然后移动到不在邻域中的下一个 P（意味着每个像素变换一次），那么这是不成立的。
O(MN) seems right if I understand that for each pixel in the image the convolution is the adjustment of pixel values in the neighbourhood N, regardless of N being square. N could be best-fit triangle ... but providing the pixels in the neighbourhood are adjusted for each pixel in the image then O(MN) makes more sense, because the dependency is in the pixels adjusted per pixel in the source image.
Interestingly, in a non-regular neighbourhood some pixels may be adjusted by the neighbourhood mask more than others, but O(MN) will still stand.
If the neighbourhood is central on a pixel P and then moved to the next P which was not in the neighbourhood (meaning each pixel is transformed once) then this doesn't stand.