# 【JS】实现 O(n) 时间的高斯模糊算法

### 高斯模糊

``````function gaussianBlur(src, dest, width, height, sigma) {
const radius = Math.round(sigma * 3) // kernel size
for (let i = 0; i < width; i++) {
for (let j = 0; j < height; j++) {
let accumulation = 0
let weightSum = 0
const x = Math.min(width - 1, Math.max(0, i + dx))
const y = Math.min(height - 1, Math.max(0, j + dy))
// calc weight
const weight =
Math.exp(
-(Math.pow(dx, 2) + Math.pow(dy, 2)) / (2 * Math.pow(sigma, 2))
) /
(Math.PI * 2 * Math.pow(sigma, 2))
accumulation += src[y * width + x] * weight
weightSum += weight
}
}
dest[j * width + i] = Math.round(accumulation / weightSum)
}
}
}``````

### 方框模糊

``````function simpleBoxBlur(src, dest, width, height, radius) {
for (let i = 0; i < width; i++) {
for (let j = 0; j < height; j++) {
let accumulation = 0
const x = Math.min(width - 1, Math.max(0, i + dx))
const y = Math.min(height - 1, Math.max(0, j + dy))
accumulation += src[y * width + x]
}
}
dest[j * width + i] = Math.round(
accumulation / Math.pow(2 * radius + 1, 2)
)
}
}
}``````

• 计算m:

• 前m次用wl作核的大小，其余的n-m次用wu作核的大小

``````function genKernelsForGaussian(sigma, n) {
const wIdeal = Math.sqrt((12 * Math.pow(sigma, 2)) / n + 1)
let wl = Math.floor(wIdeal)
if (wl % 2 === 0) {
wl--
}
const wu = wl + 2
let m =
(12 * Math.pow(sigma, 2) - n * Math.pow(wl, 2) - 4 * n * wl - 3 * n) /
(-4 * wl - 4)
m = Math.round(m)
const sizes = []
for (let i = 0; i < n; i++) {
sizes.push(i < m ? wl : wu)
}
return sizes
}
function boxBlur(src, dest, width, height, sigma) {
const kernels = genKernelsForGaussian(sigma, 3)
// radius * 2 + 1 = kernel size
simpleBoxBlur(src, dest, width, height, (kernels[0] - 1) / 2)
// 注意这里要颠倒 src 和 dest 的顺序
simpleBoxBlur(dest, src, width, height, (kernels[1] - 1) / 2)
simpleBoxBlur(src, dest, width, height, (kernels[2] - 1) / 2)
}``````

### 水平&垂直模糊

``````// horizontal motion blur
function hMotionBlur(src, dest, width, height, radius) {
for (let i = 0; i < width; i++) {
for (let j = 0; j < height; j++) {
let accumulation = 0
const x = Math.min(width - 1, Math.max(0, i + dx))
accumulation += src[j * width + x]
}
dest[j * width + i] = Math.round(accumulation / (2 * radius + 1))
}
}
}
// vertical motion blur
function vMotionBlur(src, dest, width, height, radius) {
for (let i = 0; i < width; i++) {
for (let j = 0; j < height; j++) {
let accumulation = 0
const y = Math.min(height - 1, Math.max(0, j + dy))
accumulation += src[y * width + i]
}
dest[j * width + i] = Math.round(accumulation / (2 * radius + 1))
}
}
}``````

``````function _mutantBoxBlur(src, dest, width, height, radius) {
}
function mutantBoxBlur(src, dest, width, height, sigma) {
const boxes = genKernelsForGaussian(sigma, 3)
for (let i = 0; i < src.length; i++) {
dest[i] = src[i]
}
_mutantBoxBlur(src, dest, width, height, (boxes[0] - 1) / 2)
_mutantBoxBlur(src, dest, width, height, (boxes[1] - 1) / 2)
_mutantBoxBlur(src, dest, width, height, (boxes[2] - 1) / 2)
}``````

### 终极优化

``````// horizontal fast motion blur
function hFastMotionBlur(src, dest, width, height, radius) {
for (let i = 0; i < height; i++) {
let accumulation = radius * src[i * width]
for (let j = 0; j <= radius; j++) {
accumulation += src[i * width + j]
}
dest[i * width] = Math.round(accumulation / (2 * radius + 1))
for (let j = 1; j < width; j++) {
const left = Math.max(0, j - radius - 1)
const right = Math.min(width - 1, j + radius)
accumulation =
accumulation + (src[i * width + right] - src[i * width + left])
dest[i * width + j] = Math.round(accumulation / (2 * radius + 1))
}
}
}
// vertical fast motion blur
function vFastMotionBlur(src, dest, width, height, radius) {
for (let i = 0; i < width; i++) {
let accumulation = radius * src[i]
for (let j = 0; j <= radius; j++) {
accumulation += src[j * width + i]
}
dest[i] = Math.round(accumulation / (2 * radius + 1))
for (let j = 1; j < height; j++) {
const top = Math.max(0, j - radius - 1)
const bottom = Math.min(height - 1, j + radius)
accumulation =
accumulation + src[bottom * width + i] - src[top * width + i]
dest[j * width + i] = Math.round(accumulation / (2 * radius + 1))
}
}
}
function _fastBlur(src, dest, width, height, radius) {
}
function fastBlur(src, dest, width, height, sigma) {
const boxes = genKernelsForGaussian(sigma, 3)
for (let i = 0; i < src.length; i++) {
dest[i] = src[i]
}
_fastBlur(src, dest, width, height, (boxes[0] - 1) / 2)
_fastBlur(src, dest, width, height, (boxes[1] - 1) / 2)
_fastBlur(src, dest, width, height, (boxes[2] - 1) / 2)
}``````

### 总结

#### 参考

• http://elynxsdk.free.fr/ext-d…
• http://blog.ivank.net/fastest…
• https://www.peterkovesi.com/p…
• https://stackoverflow.com/que…
• https://blog.demofox.org/2015…