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

# 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
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