DitherPunk API planning

[adrhill]

Per-channel dithering by default

Currently, to apply per-channel dithering, methods have to be wrapped in the SeparateSpace() meta-method.
Since this can be applied to any algorithm, the API could be made more elegant by applying channel-wise dithering by default:

dither(Gray.(img), FloydSteinberg())  # => binary dithering (black & white output)
dither(RGB.(img), FloydSteinberg())   # => per-channel binary dithering (2^3 color output)

For convenience, a function binary_dither could be provided that first calls Gray.(), then dither.

Conditional dependencies

I'm not sure how well Requires.jl works, but these would come in handy for methods that support custom color palettes. Some examples:

1. Support for ColorSchemes.jl:

   dither(img, FloydSteinberg(), ColorSchemes.PuOr_7.colors)  # current API
   dither(img, FloydSteinberg(), :PuOr_7)                     # this would be much simpler!

2. Braille plots via UnicodePlots could be re-introduced for binary dithering methods.
3. Rough idea: support clustering methods (e.g. from Clustering.jl) for optimized color palettes. The user could then just pass their desired number of colors instead of having to specify a palette.

[johnnychen94]

Some comments and reflinks:

Since this can be applied to any algorithm, the API could be made more elegant by applying channel-wise dithering by default:

introducing per-channel operation by default can hit the performance issue of channelview. This is because per-channel requires a struct of array layout "RR...RGG....GBB...B" and JuliaImages' type abstraction Array{RGB} uses array of struct layout "RGBRGB...RGB". There can be some performance differences speaking of data locality. See also JuliaImages/ImageCore.jl#142 JuliaImages/ImageCore.jl#170

I'm not sure how well Requires.jl works

Requires is okay, though there are two things to note: 1) by using Requires you're giving up controlling the versions of ColorSchemes, 2) introducing Symbols are okay here, but with ColorSchemes.<TAB> users are easier to find out what are available, how do you support similar discoverability with symbols?

To use Requires I can think of a global palette table

const predefined_palettes = Dict{String, Vector{<:Colorant}}()

@requires <UUID> ColorSchemes add_more_palettes!(predefined_palettes)

Rough idea: support clustering methods (e.g. from Clustering.jl) for optimized color palettes.

Is the idea to do clustering with maximal type distance? If so there might be some RGB 2 gray (decolorization) papers to take a look at. I'm not an expert in this field so please allow me to blindly share a paper of my labmate https://link.springer.com/article/10.1007/s11042-021-11172-9 so that you can start the search.

[adrhill]

Thank you for the references!

introducing per-channel operation by default can hit the performance issue of channelview.

We could also implement the same API via MD.
On the topic of performance: I've been thinking that methods like error diffusion that supports custom color palettes should also have a specialized binary dithering implementation. This would require duplicating some code but would greatly boost the performance.

introducing Symbols are okay here, but with ColorSchemes. users are easier to find out what are available

Good point. Maybe we can just support both options? ColorSchemes has a nice catalogue of palettes to visually check out what is available. This is what I personally tend to use.

there might be some RGB 2 gray (decolorization) papers to take a look at

I was thinking about using clustering to obtain optimized RGB color palettes for color quantization:

combined with dithering you get pretty nice results:

A possible interface would be

dither(color_img, FloydSteinberg(); colors=16)  # => returns color image using an optimized palette of 16 colors 
dither(color_img, FloydSteinberg(), 16)         # or maybe even like this?

(Images taken from here and here.)

[adrhill]

There is one more issue that came to my mind:

Currently, calling dither(img, alg(), colorscheme) will return an image in the type of img. Because of this, it currently isn't possible to dither a Gray img in a custom color scheme.

Maybe we can break the convention here and return an image in the type of colorscheme?
Or should we just throw an error and tell the user that the Gray image needs to be converted to <: Color{T,3} first?

[johnnychen94]

Maybe we can break the convention here and return an image in the type of colorscheme?

Agreed. This has proven to be very useful in PaddedViews and MosaicViews. MosaicViews.promote_wrapped_type can help here to promote both wrapper types and eltypes.

julia> img = rand(Gray{Float32}, 4, 4);

julia> T = RGB{N0f8}
RGB{N0f8}

julia> RT = ImageCore.MosaicViews.promote_wrapped_type(eltype(img), T)
RGB{Float32}

julia> RT.(img)

One thing that should be aware here is: if you decide to support Symbols, then eltype(colorscheme) can't be decided until runtime, which means the output type of the function can't be decided until runtime, which means Julia will not be able to infer the dither(gray_img, alg, cs::Symbol) method and thus causes an unnecessary performance regression.

dither(img, colorscheme::Symbol) = dither(img, get_colorscheme(colorscheme))
function dither(img, colorscheme::Vector{T}) where T
    RT = ImageCore.MosaicViews.promote_wrapped_type(eltype(img), T)
    RT.(img)
end


function get_colorscheme(cs::Symbol)
    if cs === :RGB
        return RGB{Float32}[RGB(1, 0, 0), RGB(0, 1, 0), RGB(0, 0, 1)]
    elseif cs === :Gray
         return Gray{Float32}[Gray(0), Gray(1)]
    else
         error("Unsupported color schemes")
    end
end

julia> @code_warntype get_colorscheme(:Gray)
Variables
  #self#::Core.Const(get_colorscheme)
  cs::Symbol

Body::Union{Vector{Gray{Float32}}, Vector{RGB{Float32}}}
1 ─ %1  = (cs === :RGB)::Bool
└──       goto #3 if not %1
2 ─ %3  = Core.apply_type(Main.RGB, Main.Float32)::Core.Const(RGB{Float32})
│   %4  = Main.RGB(1, 0, 0)::Core.Const(RGB{N0f8}(1.0,0.0,0.0))
│   %5  = Main.RGB(0, 1, 0)::Core.Const(RGB{N0f8}(0.0,1.0,0.0))
│   %6  = Main.RGB(0, 0, 1)::Core.Const(RGB{N0f8}(0.0,0.0,1.0))
│   %7  = Base.getindex(%3, %4, %5, %6)::Vector{RGB{Float32}}
└──       return %7
3 ─ %9  = (cs === :Gray)::Bool
└──       goto #5 if not %9
4 ─ %11 = Core.apply_type(Main.Gray, Main.Float32)::Core.Const(Gray{Float32})
│   %12 = Main.Gray(0)::Core.Const(Gray{N0f8}(0.0))
│   %13 = Main.Gray(1)::Core.Const(Gray{N0f8}(1.0))
│   %14 = Base.getindex(%11, %12, %13)::Vector{Gray{Float32}}
└──       return %14
5 ─       Main.error("Unsupported color schemes")
└──       Core.Const(:(return %16))

julia> @code_warntype dither(img, :Gray)
Variables
  #self#::Core.Const(dither)
  img::Matrix{Gray{Float32}}
  colorscheme::Symbol

Body::Union{Matrix{Gray{Float32}}, Matrix{RGB{Float32}}}
1 ─ %1 = Main.get_colorscheme(colorscheme)::Union{Vector{Gray{Float32}}, Vector{RGB{Float32}}}
│   %2 = Main.dither(img, %1)::Union{Matrix{Gray{Float32}}, Matrix{RGB{Float32}}}
└──      return %2

[adrhill]

Thanks a lot for the in-depth answer and for referring me to promote_wrapped_type!

One thing that should be aware here is: if you decide to support Symbols, then eltype(colorscheme) can't be decided until runtime, which means the output type of the function can't be decided until runtime, which means Julia will not be able to infer the dither(gray_img, alg, cs::Symbol) method and thus causes an unnecessary performance regression.

Luckily, I think ColorSchemes.jl only exports RGB ColorSchemes. I will double-check if we could count on this when dispatching on symbols.

Re colorscheme clustering:
A lot of the functionality I was looking for already exists in ColorSchemeTools.jl, so it might be a good idea to just add this as another conditional dependency:
https://juliagraphics.github.io/ColorSchemeTools.jl/stable/tools/#Extracting-colorschemes-from-images

[adrhill]

Maybe we can break the convention here and return an image in the type of colorscheme?

Agreed. This has proven to be very useful in PaddedViews and MosaicViews. MosaicViews.promote_wrapped_type can help here to promote both wrapper types and eltypes.

How would you suggest we deal with dither!(gray_img, alg, rgb_colorscheme)?
I'm guessing in-place updating Gray to RGB is not possible.

[johnnychen94]

When dealing with in-place functions, users are responsible for allocating an appropriate output. An implicit RGB to Gray color conversion will be applied if users call dither!(gray_img, alg, rgb_colorscheme).

julia> img = fill(Gray(1.0), 4, 4);

julia> img[1] = colorant"red"
RGB{N0f8}(1.0,0.0,0.0)

julia> img
4×4 Array{Gray{Float64},2} with eltype Gray{Float64}:
 Gray{Float64}(0.298039)  Gray{Float64}(1.0)  Gray{Float64}(1.0)  Gray{Float64}(1.0)
 Gray{Float64}(1.0)       Gray{Float64}(1.0)  Gray{Float64}(1.0)  Gray{Float64}(1.0)
 Gray{Float64}(1.0)       Gray{Float64}(1.0)  Gray{Float64}(1.0)  Gray{Float64}(1.0)
 Gray{Float64}(1.0)       Gray{Float64}(1.0)  Gray{Float64}(1.0)  Gray{Float64}(1.0)

[adrhill]

Thanks a lot Johnny!