Make gaussian blur using separable convolution

[angeloskath]

Hi,

I just noticed that Gaussian blur is not implemented using separable convolutions so I implemented it. The speed up is orders of magnitude for large kernels and large images.

Basically on my machine I get a speedup of 20x for a blur radius 30 pixels and a relatively large image as shown below:

$ time bild_0.11 blur gaussian --radius 30 ~/Downloads/cat.jpg ~/Downloads/out.jpg

real    0m29.641s
user    1m28.880s
sys 0m0.320s

$ time bild-fast-gaussian blur gaussian --radius 30 ~/Downloads/cat.jpg ~/Downloads/out.jpg

real    0m1.430s
user    0m5.316s
sys 0m0.036s

$ file ~/Downloads/cat.jpg
/path/to/my/home/Downloads/cat.jpg: JPEG image data, Exif standard: [TIFF image data, little-endian, direntries=1, copyright=Image protected by copyright. Contact  National Geographic Creative at: Telephone:202.857.7537,], baseline, precision 8, 2048x1365, frames 3

Cheers, Angelos

[anthonynsimon]

Looks good! I tried it on my laptop and it's a really great speed up! As a side effect, some other functions that make use of gaussian blur internally like the UnsharpMask will greatly benefit from this.

Before we merge it, could you please take a look at:

1) Please rename the Tranpose function to Transposed since we use that convention for immutable operations.

2) I think the transpose is not returning the correct result for non-square matrices, here's some test cases we could add:

func TestKernelTransposed(t *testing.T) {
    cases := []struct {
        desc     string
        kernel   *Kernel
        expected *Kernel
    }{
        {
            desc: "all zero",
            kernel: &Kernel{[]float64{
                0, 0, 0,
                0, 0, 0,
                0, 0, 0,
            }, 3, 3},
            expected: &Kernel{[]float64{
                0, 0, 0,
                0, 0, 0,
                0, 0, 0,
            }, 3, 3},
        },
        {
            desc: "one element",
            kernel: &Kernel{[]float64{
                0, 0, 0,
                0, 1, 0,
                0, 0, 0,
            }, 3, 3},
            expected: &Kernel{[]float64{
                0, 0, 0,
                0, 1, 0,
                0, 0, 0,
            }, 3, 3},
        },
        {
            desc: "diagonal",
            kernel: &Kernel{[]float64{
                1, 0, 0,
                0, 1, 0,
                0, 0, 1,
            }, 3, 3},
            expected: &Kernel{[]float64{
                1, 0, 0,
                0, 1, 0,
                0, 0, 1,
            }, 3, 3},
        },
        {
            desc: "3x2",
            kernel: &Kernel{[]float64{
                1, 1, 1,
                0, 1, 0,
            }, 3, 2},
            expected: &Kernel{[]float64{
                1, 0,
                1, 1,
                1, 0,
            }, 2, 3},
        },
        {
            desc: "5x1",
            kernel: &Kernel{[]float64{
                1, 1, 1, 0, 1,
            }, 5, 1},
            expected: &Kernel{[]float64{
                1,
                1,
                1,
                0,
                1,
            }, 1, 5},
        },
    }

    for i, c := range cases {
        actual := c.kernel.Transposed()
        if !kernelEqual(actual.(*Kernel), c.expected) {
            t.Errorf("%s case #%d: expected: %#v, actual: %#v", "KernelTransposed "+c.desc, i, c.expected, actual)
        }
    }
}

[angeloskath]

Oh, man you are so right (embarassed :) ). Let me fix these real quick and update the pull request.

[angeloskath]

Overwrote the previous commit. Added your test. I also ran the full tests this time and changed the expected outputs for effects because of the two pass algorithm some values change by 1 as was the case for the blur test.

Cheers, Angelos

[anthonynsimon]

Looks great! Will prepare a release with this.