FloydSteinberg performance issue for given colormap

[johnnychen94]

function dither_bw(img)
    alg = DitherPunk.FloydSteinberg()
    img = Gray{N0f8}.(img)
    img_bw = DitherPunk.dither(img, alg, [Gray{N0f8}(0), Gray{N0f8}(1)])
    return Bool.(img_bw)
end

img = testimage("cameraman");
@btime dither_bw($img) # 109.763 ms (5453396 allocations: 86.75 MiB)

vs MATLAB's dither function

img = imresize(imread("cameraman.tif"), [512, 512]);
f = @() dither(img)
timeit(f) * 1000 % 2.8ms

It indicates that DitherPunk can be faster. The massive allocation count looks like type instability to me.

[adrhill]

To apply more efficient binary dithering, simply call dither(img, alg) on a grayscale image without providing a colorscheme.

To return a Matrix{Bool}, you can use dither(Bool, img, alg):

function dither_bw(img)
    alg = DitherPunk.FloydSteinberg()
    img = Gray{N0f8}.(img)
    return DitherPunk.dither(Bool, img, alg)
end

img = testimage("cameraman");
@btime dither_bw($img) # 2.793 ms (17 allocations: 1.50 MiB)

When providing a colorscheme, DitherPunk calls the internal function colordither instead of much faster binarydither!.

[johnnychen94]

Performance comparison between DitherPunk and MATLAB on FloydSteinberg algorithm:

version	matlab(ms)	ditherpunk(ms)
gray - binary	2.7405	1.794
gray - cmap	x	446.576
RGB - binary	x	7.864
RGB - cmap	4.1374	441.121

• gray image: testimage("cameraman")
• RGB image: testimage("peppers_color")
• cmap: 8 colors generated from kmeans of the image
• x: not supported

julia> versioninfo()
Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 12th Gen Intel(R) Core(TM) i9-12900K
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, goldmont)

benchmark codes

```julia # DitherPunk.jl using ImageCore, ImageShow, DitherPunk, TestImages using Clustering alg = FloydSteinberg() img_gray = testimage("cameraman") img_rgb = testimage("peppers_color") # gray - binary @btime dither($img_gray, $alg); # 1.794 ms (5 allocations: 1.25 MiB) # gray - cmap cmap = DitherPunk.get_colorscheme(img_gray, 8) @btime dither($img_gray, $alg, $cmap); # 446.576 ms (30394703 allocations: 558.88 MiB) # rgb - binary @btime dither($img_rgb, $alg); # 7.864 ms (11 allocations: 3.75 MiB) # rgb - cmap cmap = DitherPunk.get_colorscheme(img_rgb, 8) @btime dither($img_rgb, $alg, $cmap); # 441.121 ms (30093620 allocations: 554.28 MiB) ``` ```matlab % matlab img_gray = im2double(imresize(imread("cameraman.tif"), [512, 512])); img_rgb = im2double(imread("peppers_color.tif")); % gray - binary f = @() dither(img_gray); timeit(f) * 1000 % 2.7405 % % gray - cmap % [idx, cmap] = kmeans(img_gray(:), 8); % dither(img_gray, cmap) % % rgb - binary % f = @() dither(img_rgb); % timeit(f) * 1000 % 2.7405 % rgb - cmap [idx, cmap] = kmeans(reshape(img_rgb, 512*512, 3), 8); f = @() dither(img_rgb, cmap) timeit(f) * 1000 % 4.1374 ```