Google – Gaussian Flur

Google – Gaussian Flur

高斯模糊，计算一个矩阵在radius范围内的平均值。
input:
1 2
3 4
radius = 1

output:
2.5 2.5
2.5 2.5

[Solution]
Brute Force很好解决，一个个算就好。

不过有种sliding window的解法。

window就是以每个cell为中心，边长为(2*radius + 1)的正方形。具体长什么样可以参考

http://blog.csdn.net/lemon_tree12138/article/details/50425793

实现起来稍微有点复杂，主要edge case比较多。不过时间复杂度要比brute force快不少。

Brute force: O(mn * 8radius) = O(8mn * radius)

sliding window: O(m * (radius + n * 2radius)) = O((2n + m) * radius)

Read full article from Google – Gaussian Flur