Module iter

This module implements the StackBlur struct and the improved version of the Stackblur algorithm.

The improved Stackblur algorithm

As previously stated, this crate implements a modified version of Stackblur, and understanding the original algorithm is key to understanding the improvements that have been made to it.

The original Stackblur is essentially a weighted box-blur. Instead of taking the average of a flat array of pixels, like this:

( 00 + 01 + 02 + 03 + 04 + 05 + 06 ) / 7

it takes a weighted average of the pixels:

             ( 03 +
          02 + 03 + 04 +
     01 + 02 + 03 + 04 + 05 +
00 + 01 + 02 + 03 + 04 + 05 + 06 ) / 16

This is a rough approximation of a Gaussian blur, and in fact it’s already most of the way there to being a complete algorithm on its own. You can just multiply each pixel by something like radius + 1 - center_dist when you make your sum, then divide by radius * (radius + 2) + 1.

But there are two problems with this:

1. That would be O(n(m * 2 + 1)²) complexity, where n is the number of pixels in the image, and m is the radius of the blur. This is basically just as expensive as running a proper convolution filter.

2. How do we handle pixels off the edge of the image?

I’m scared of #1 so I’m going to handle #2 first. What most implementations choose to do is just repeat the edge of the image:

             ( 00 +
          00 + 00 + 01 +
     00 + 00 + 00 + 01 + 02 +
00 + 00 + 00 + 00 + 01 + 02 + 03 ) / 16

But this creates even more problems, because the edge of the blur will be quite biased towards the pixels that aren’t even in the image. This is known as “edge bleeding”, where a single pixel at the edge of a blur can cause very large and ugly artifacts to show up.

The solution, of course, is to not calculate the denominator using that equation from earlier, and instead incrementally update the denominator as pixels are scanned, allowing you to sum a varying number of pixels:

( 00 +
  00 + 01 +
  00 + 01 + 02 +
  00 + 01 + 02 + 03 ) / 10

     ( 01 +
  00 + 01 + 02 +
  00 + 01 + 02 + 03 +
  00 + 01 + 02 + 03 + 04 ) / 13

          ( 02 +
       01 + 02 + 03 +
  00 + 01 + 02 + 03 + 04 +
  00 + 01 + 02 + 03 + 04 + 05 ) / 15

               ( 03 +
            02 + 03 + 04 +
       01 + 02 + 03 + 04 + 05 +
  00 + 01 + 02 + 03 + 04 + 05 + 06 ) / 16

This is one of the improvements made to the Stackblur algorithm that is implemented by this crate.

Now for #1 - the complexity problem. It is possible to make a streaming Stackblur that does not need to read any pixels out of order or more than once, or even know how long the input is. In fact, that’s exactly what this crate does.

First you fill up the cache with radius + 1 pixels in order to be able to make the first sum, then you start producing results until you run out of pixels, then you produce the last radius results using what you have in cache. I don’t have the skill to explain the algorithm in full detail, but it’s open-source so you can look at it if you want.

In this crate the “cache” is not actually the actual heap of values, as that would be too slow. Instead, the “cache” is a list of changes to make to the rate of change of the sum, and the denominator is updated incrementally in response to the number of leading and trailing values changing.

The reason the whole rate of change thing exists is so that adding to the sum and registering it in the cache becomes O(1) instead of O(2n+1) (where n is the radius). It’s basically the most important thing that makes the algorithm constant-time.

Structs

StackBlur

An iterator that implements an improved Stackblur algorithm.