`blur` function is too slow

[Aloxaf]

blur is too slow, imageproc::filter::gaussian_blur_f32 is faster than it, but still slow.

Reproduction steps

use image::imageops::blur;
use image::{Rgb, RgbImage};
use imageproc::drawing::draw_filled_circle_mut;
use imageproc::filter::gaussian_blur_f32;
use std::time::Instant;

fn main() {
    let mut image = RgbImage::new(1000, 1000);
    draw_filled_circle_mut(&mut image, (500, 500), 500, Rgb([255, 255, 255]));

    let start = Instant::now();
    blur(&image, 100.0).save("rust_1.png").unwrap();
    dbg!(start.elapsed());

    let start = Instant::now();
    gaussian_blur_f32(&image, 100.0).save("rust_2.png").unwrap();
    dbg!(start.elapsed());
}

result is

[src/main.rs:13] start.elapsed() = 12.362780732s
[src/main.rs:17] start.elapsed() = 3.335411994s

and Pillow

from PIL import Image, ImageDraw, ImageFilter
from time import time

img  = Image.new('RGB', (1000, 1000))
draw = ImageDraw.Draw(img)
draw.ellipse((0, 0, 1000, 1000), fill='#ffffff')

start = time()
img.filter(ImageFilter.GaussianBlur(100)).save('python.png')
print(f'{time() - start}s')

result is 0.1433885097503662s

Here is the final image

rust_1.png (it's a little strange...

rust_2.png

python.png

[197g]

Just to clarify, PIL uses a C version indirectly https://github.com/python-pillow/Pillow/blob/ab9a25d623fdd7f8de3e724b538f5660eac589ae/src/libImaging/BoxBlur.c#L294

It's still somewhat embarrasingly slow.

[Aloxaf]

@HeroicKatora Yes, maybe it would be a good idea to port it rust?

[theotherphil]

Pillow appears to use (a variant on) iterated box filtering, as defined in http://www.mia.uni-saarland.de/Publications/gwosdek-ssvm11.pdf.

There's an open imageproc ticket to implement this: https://github.com/image-rs/imageproc/issues/93

[theotherphil]

I'll have a look at implementing this over the coming weekend.

[Shnatsel]

There is actually a linear-complexity blur already implemented in Rust, where execution time is independent of blur radius: https://github.com/fschutt/fastblur

A copy of it was copied into resvg codebase and polished to match Chrome blur. You can find it in this file, search for box_blur. It should be fairly easy to extract it back into a common crate and/or copy it into image.

[vadixidav]

You may want to take a look at the code here. It was originally based on a different paper, written by the author of AKAZE, ported to rust by someone else, and then modified later by me (so it has been touched by many hands). It makes use of the following papers:

• S. Grewenig, J. Weickert, C. Schroers, A. Bruhn. Cyclic Schemes for PDE-Based Image Analysis. Technical Report No. 327, Department of Mathematics, Saarland University, Saarbrücken, Germany, March 2013
• S. Grewenig, J. Weickert, A. Bruhn. From box filtering to fast explicit diffusion. DAGM, 2010

It is actually not used for guassian blur in akaze itself. I am also not 100% sure it can help speed up guassian blur, but I think it can based on what I have seen in its use in akaze. I am no expert. The way this algorithm works is that it determines a number of diffusion steps that start small and grow bigger as the stability increases (which may not apply to guassian blur?). See this file for how the specialized blur is being applied (with ndarray). I was able to get pretty good speed by writing my filters with ndarray like that. My situation is a bit more specific to this library, but the code is free for you to take.

[RReverser]

Also noticed this while comparing Wasm version of image::imageops::blur and JS implementation of Gaussian blur from https://github.com/nodeca/glur.

At high radius values the difference becomes ridiculous - e.g. for 3872x2592 image and radius 300px the image crate's version executes in 94 seconds, while JS executes in 0.6 seconds (same as for any other radius).

Having linear implementation in image crate would help a lot. fastblur from @Shnatsel's link looks promising, but it would be nice to integrate it into image or imageproc instead of relying on a 3rd-party dependency that is somewhat harder to discover.

[torfmaster]

If anyone is interested: I created a first draft to resolve this issue in https://github.com/image-rs/image/pull/2302 and I am willing to finalize this.