乐趣区

关于javascript:实现-On-时间的高斯模糊算法

原发于我的集体博客 集体博客网站

本文次要是针对高斯含糊算法进行优化,最初在线性工夫内实现高斯含糊成果。当然,该算法并非自己原创,实现过程中也借鉴了一些文章和论文,相干链接都在文末贴出

搭配浏览,我写了一个简略的 Demo,Demo 链接,Demo 代码地址,能够在 Demo 中测试各种含糊成果及其耗时

高斯含糊

高斯含糊能够实现十分平滑的含糊成果,对于每一个像素,它会取它自身及其四周肯定范畴内的像素,去计算含糊后的成果,当然,每个像素在计算过程中所占的权重并不相同,间隔其自身越近,权重越高——这当然是正当的。权重的计算公式如下:

公式中的 σ(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 中尝试(高斯含糊可能耗时较久,急躁期待吧)

原图:

高斯含糊后(sigma=5),5411ms(MBP, 13-inch, 2017, 8G):

方框含糊

最简略的方框含糊 (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):

能够看出,尽管耗时较高斯含糊短,但其成果是很不平滑的。那有没有方法让方框含糊领有高斯含糊一样的品质呢,这篇论文提出了计划

依据论文中所述,能够通过屡次的方框含糊实现高斯含糊,而这屡次方框含糊的核由以下步骤得出:

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

  • 计算 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)
}

成果和高斯含糊基本一致 (227ms):

尽管工夫复杂度与高斯含糊雷同,但失去的半径更小,在 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):

终极优化

以程度含糊为例 (这里为了不便,用二维数组示意)





那很显著,咱们能够通过此优化将工夫复杂度由 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…
退出移动版