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

原发于我的个人博客 个人博客网站

本文主要是针对高斯模糊算法进行优化，最后在线性时间内实现高斯模糊效果。当然，该算法并非本人原创，实现过程中也借鉴了一些文章和论文，相关链接都在文末贴出

搭配阅读，我写了一个简单的Demo，Demo链接，Demo代码地址，可以在Demo中测试各种模糊效果及其耗时

高斯模糊

高斯模糊可以实现非常平滑的模糊效果，对于每一个像素，它会取它本身及其周围一定范围内的像素，去计算模糊后的效果，当然，每个像素在计算过程中所占的权重并不相同，距离其本身越近，权重越高——这当然是合理的。权重的计算公式如下：

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

公式中的σ(sigma)是人为定值的，值越大，生成的图像越模糊

当然，并非所有像素都会互相影响，以当前像素为圆心，取一个半径，在这个半径以内的像素才会影响该像素的模糊效果。这个半径与sigma成正比，不过没有统一的公式，在这个提问下，有回答说NVidia采用的是radius=sigma*3的计算方式，我在这也使用了这个公式

下面是其基本实现，时间复杂度为O(nrr)，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
for (let dx = -radius; dx <= radius; dx++) {
for (let dy = -radius; dy <= radius; dy++) {
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)
}
}
}

效果如下，也可以去 Demo 中尝试(高斯模糊可能耗时较久，耐心等待吧)

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

高斯模糊后(sigma=5)，5411ms(MBP, 13-inch, 2017, 8G)：
【JS】实现 O(n) 时间的高斯模糊算法

方框模糊

最简单的方框模糊(box blur)没有权重，只要在半径内，权重都是相同的

function simpleBoxBlur(src, dest, width, height, radius) {
for (let i = 0; i < width; i++) {
for (let j = 0; j < height; j++) {
let accumulation = 0
for (let dx = -radius; dx <= radius; dx++) {
for (let dy = -radius; dy <= radius; dy++) {
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)
)
}
}
}

radius=15的效果(775ms)：
【JS】实现 O(n) 时间的高斯模糊算法

可以看出，虽然耗时较高斯模糊短，但其效果是很不平滑的。那有没有办法让方框模糊拥有高斯模糊一样的品质呢，这篇论文提出了方案

根据论文中所述，可以通过多次的方框模糊实现高斯模糊，而这多次方框模糊的核由以下步骤得出：

  • 由下图公式(n为模糊次数)计算得出wideal，再计算wl和wu，wl为第一个小于等于wideal的奇数，wu是第一个大于等于wideal的奇数(很明显wu = wl+2)(要求奇数的原因是size=radius*2+1)

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

  • 计算m:

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

  • 前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)
}

效果和高斯模糊基本一致(227ms)：
【JS】实现 O(n) 时间的高斯模糊算法
虽然时间复杂度与高斯模糊相同，但得到的半径更小，在sigma=5，n=3的情况下，radius=[4, 4, 5]，高斯模糊则是15；同时还不用计算复杂的weight，所以从实际结果上看，速度要优于比高斯模糊

水平&垂直模糊

在这篇文章中提到 方框模糊可以用水平模糊+垂直模糊替代实现。要实现水平/垂直模糊很简单, 只需考虑水平/垂直线上的像素即可：

// 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
for (let dx = -radius; dx <= radius; dx++) {
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
for (let dy = -radius; dy <= radius; dy++) {
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))
}
}
}

应用此优化的模糊算法，时间复杂度可以优化到O(nr)：

function _mutantBoxBlur(src, dest, width, height, radius) {
hMotionBlur(dest, src, width, height, radius)
vMotionBlur(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)
}

效果如下(82ms)：
【JS】实现 O(n) 时间的高斯模糊算法

终极优化

以水平模糊为例(这里为了方便，用二维数组表示)
【JS】实现 O(n) 时间的高斯模糊算法
而
【JS】实现 O(n) 时间的高斯模糊算法
则
【JS】实现 O(n) 时间的高斯模糊算法
那很明显，我们可以通过此优化将时间复杂度由O(nr)降到O(n)，最终的代码:

// 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) {
hFastMotionBlur(dest, src, width, height, radius)
vFastMotionBlur(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)
}

效果(20ms)：

总结

先后通过多次方框模糊、水平+垂直模糊代替方框模糊、对水平/垂直模糊计算过程的优化，逐步将高斯模糊的耗时降低，最后得到了只与图片大小相关的O(n)时间复杂度算法

参考

  • 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...

以上是 【JS】实现 O(n) 时间的高斯模糊算法 的全部内容， 来源链接： utcz.com/a/90055.html

回到顶部