4 ms·

I found a practical example of this last week. For years (literally!) I've been on the lookout for an efficient Javascript blur algorithm. I've attempted to co

I found a practical example of this last week. For years (literally!) I've been on the lookout for an efficient Javascript blur algorithm. I've attempted to code them myself following various online tutorials, or lift the code from others who seemed to have better insights into various algorithmic approaches than me. Because I struggle with complex mathematical concepts, I've tended to steer clear of code that looks nothing like Javascript. Then last week I discovered a blisteringly fast gaussian blur algorithm in a GitHub repository[1] which translated work done by some very clever Intel developers[2] into Javascript. I copy-pasted the code on blind trust into my library code, then tweaked more in hope than knowledge to get it to bed in and play nicely[3] ... and it works! 40px radius gaussian blurs over 800x800px images at 60fps (in a 2D canvas - no webgl gets hurt by this algorithm). I consider myself a well-versed JS coder, yet I've stared at this code until my eyes water: none of it makes sense to me. All I know is that it works by magic, and that makes me happy! [1] - https://github.com/nodeca/glur/blob/master/index.js https://github.com/nodeca/glur/blob/master/index.js [2] - https://software.intel.com/en-us/articles/iir-gaussian-blur-filter https://software.intel.com/en-us/articles/iir-gaussian-blur-... - page redirects if you're not logged in [3] - my tweaked code - https://scrawl-v8.rikweb.org.uk/docs/source/factory/filterEngine.html#section-30 https://scrawl-v8.rikweb.org.uk/docs/source/factory/filterEn...

iainmerrick 5y ago
That is cool! I think I may be able to explain the gist (though not the full details). It uses an IIR filter, or Infinite Impulse Response filter. This is a digital filter (could be either software or hardware) where there’s a feedback loop from the output to the input. The advantage of an IIR is that it can produce a long output (potentially infinite, hence the name) from a single input. The disadvantage is that IIRs can easily get unstable and hard to work with; hence many (most?) applications use FIRs, Finite Impulse Response, where there’s no feedback and the output is strictly bounded. It looks like they’re using an IIR tuned to produce a Gaussian bell curve as the impulse response. By feeding each pixel through the filter in sequence, each pixel produces a bell curve and those get blended together, exactly what you what. So, that tight inner loop consists of reading in the next pixel and blending it with the intermediate results of earlier pixels. Very efficient on a CPU where you can stream the data through, but it wouldn’t work in an OpenGL shader as that expects to work on each pixel in parallel, not sequentially.
- rikroots 5y ago
  Thanks - that explanation helps a bit. But now I'm wondering if the code could be adapted to handle various convolution matrix filters and my brain is threatening to divorce me.

iainmerrick 5y ago

That is cool! I think I may be able to explain the gist (though not the full details). It uses an IIR filter, or Infinite Impulse Response filter. This is a digital filter (could be either software or hardware) where there’s a feedback loop from the output to the input. The advantage of an IIR is that it can produce a long output (potentially infinite, hence the name) from a single input. The disadvantage is that IIRs can easily get unstable and hard to work with; hence many (most?) applications use FIRs, Finite Impulse Response, where there’s no feedback and the output is strictly bounded. It looks like they’re using an IIR tuned to produce a Gaussian bell curve as the impulse response. By feeding each pixel through the filter in sequence, each pixel produces a bell curve and those get blended together, exactly what you what. So, that tight inner loop consists of reading in the next pixel and blending it with the intermediate results of earlier pixels. Very efficient on a CPU where you can stream the data through, but it wouldn’t work in an OpenGL shader as that expects to work on each pixel in parallel, not sequentially.

rikroots 5y ago
Thanks - that explanation helps a bit. But now I'm wondering if the code could be adapted to handle various convolution matrix filters and my brain is threatening to divorce me.