Dither.dx

[niklasschmitz]

A fun hack together with @adrhill exploring basic image dithering in dex:

Full copy-pasteable code:

' # Dither.dx

import plot
import png

' # Round 0: Creating a test image

Height = Fin 100
Width = Fin 300
key = new_key 1234
img_ = for i:Height. for j:Width. n_to_f ((ordinal i) + (ordinal j))
img = img_ / (n_to_f (size Height + size Width))

:t img
:html matshow img
' # Round 1: Threshold dithering

def dither_threshold {h w} (img: h=>w=>Float) : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > 0.5

:html matshow $ dither_threshold img

' # Round 2: Noise dithering

def dither_noise {h w} (k:Key) (img: h=>w=>Float)  : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > (rand (ixkey2 k i j))

:html matshow $ dither_noise key img

' # Round 3: Ordered dithering

def dither_ordered {h w mh mw} (mat: mh=>mw=>Float) (img: h=>w=>Float) : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > mat.(asidx (mod (ordinal i) (size mh))).(asidx (mod (ordinal j) (size mw)))

bayer = [[1.0,  9,  3, 11], 
         [ 13,  5, 15,  7],
         [  4, 12,  2, 10],
         [ 16,  8, 14,  6]] / 17.0

:html matshow $ dither_ordered bayer img

halftone = [[14.0,  10,  6, 13, 19, 23, 27, 20],
            [   7,   2,  1,  9, 26, 31, 32, 24],
            [  11,   3,  4,  5, 22, 30, 29, 28],
            [  15,   8, 12, 16, 18, 25, 21, 17],
            [  19,  23, 27, 20, 14, 10,  6, 13],
            [  26,  31, 32, 24,  7,  2,  1,  9],
            [  22,  30, 29, 28, 11,  3,  4,  5],
            [  18,  25, 21, 17, 15,  8, 12, 16]] / 33.0

:html matshow $ dither_ordered halftone img

' # Dithering a real image

def pixel (x:Char) : Float32 =
  r = w8_to_i x
  i_to_f case r < 0 of
    True -> 256 + r
    False -> r

IHeight = Fin 512
IWidth = Fin 512
Full = Fin ((size IHeight) * (size IWidth))
(AsList _ imgbytes) = unsafe_io do read_file "examples/cameraman.bytes"

raw = unsafe_cast_table Full (for i:Full. imgbytes.((ordinal i) @ _))
img_cameraman = for i:IHeight j:IWidth. (pixel raw.((ordinal (i, j)) @ Full)) / 255.0

:html matshow img_cameraman

:html matshow $ dither_threshold img_cameraman
:html matshow $ dither_noise key img_cameraman
:html matshow $ dither_ordered bayer img_cameraman
:html matshow $ dither_ordered halftone img_cameraman

Dither.dx

import plot
import png

Round 0: Creating a test image

Height = Fin 100
Width = Fin 300
key = new_key 1234
img_ = for i:Height. for j:Width. n_to_f ((ordinal i) + (ordinal j))
img = img_ / (n_to_f (size Height + size Width))

:t img
:html matshow img

Round 1: Threshold dithering

def dither_threshold {h w} (img: h=>w=>Float) : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > 0.5

:html matshow $ dither_threshold img

Round 2: Noise dithering

def dither_noise {h w} (k:Key) (img: h=>w=>Float)  : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > (rand (ixkey2 k i j))

:html matshow $ dither_noise key img

Round 3: Ordered dithering

def dither_ordered {h w mh mw} (mat: mh=>mw=>Float) (img: h=>w=>Float) : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > mat.(asidx (mod (ordinal i) (size mh))).(asidx (mod (ordinal j) (size mw)))

bayer = [[1.0,  9,  3, 11], 
         [ 13,  5, 15,  7],
         [  4, 12,  2, 10],
         [ 16,  8, 14,  6]] / 17.0

:html matshow $ dither_ordered bayer img

halftone = [[14.0,  10,  6, 13, 19, 23, 27, 20],
            [   7,   2,  1,  9, 26, 31, 32, 24],
            [  11,   3,  4,  5, 22, 30, 29, 28],
            [  15,   8, 12, 16, 18, 25, 21, 17],
            [  19,  23, 27, 20, 14, 10,  6, 13],
            [  26,  31, 32, 24,  7,  2,  1,  9],
            [  22,  30, 29, 28, 11,  3,  4,  5],
            [  18,  25, 21, 17, 15,  8, 12, 16]] / 33.0

:html matshow $ dither_ordered halftone img

Dithering a real image

For this we currently need to convert a chosen image to raw bytes first. Here's the Julia code we used to convert the common cameraman test image.

using TestImages
img = testimage("cameraman")
uints = map(x -> floor(UInt8, x.val*255), img)
open("cameraman.bytes", "w+") do io
    for r in eachrow(uints)
        foreach(c -> write(io, c), r)
    end
end

Back to dex:

def pixel (x:Char) : Float32 =
  r = w8_to_i x
  i_to_f case r < 0 of
    True -> 256 + r
    False -> r

IHeight = Fin 512
IWidth = Fin 512
Full = Fin ((size IHeight) * (size IWidth))
(AsList _ imgbytes) = unsafe_io do read_file "examples/cameraman.bytes"

raw = unsafe_cast_table Full (for i:Full. imgbytes.((ordinal i) @ _))
img_cameraman = for i:IHeight j:IWidth. (pixel raw.((ordinal (i, j)) @ Full)) / 255.0

:html matshow img_cameraman

:html matshow $ dither_threshold img_cameraman

:html matshow $ dither_noise key img_cameraman

:html matshow $ dither_ordered bayer img_cameraman

:html matshow $ dither_ordered halftone img_cameraman

[apaszke]

Whoah, that's super cool! Would you like to submit the code as an example? It would be best to add some extra commentary around the different methods, but this is already great.

By the way, for image loading, you could consider either PPM (@duvenaud has an implementation that loads PPM images in #524). I was also thinking of writing a QOI image loader, since the format seems super simple and shouldn't be too difficult to write in Dex (+ it's lossless and usually achieves PNG-like compression ratios).

[niklasschmitz]

Thanks Adam! The PPM loader looks helpful here too, and TIL about QOI which looks interesting. Glad to contribute the code as an example, we'll add some commentary and open a PR within a few days.

[dougalm]

Lovely! TIL about ordered dithering. Now I see where that "vintage comic book" look comes from. +1 to Adam's suggestion to submit it as a code example if you have time.

The expression asidx (mod (ordinal i) (size mh)) is safe as a whole even though it uses the unsafe asidx (perhaps we should say "partial" rather than "unsafe"). It's a common pattern and I wonder if we should wrap it up in a safe/total API and put it in the prelude, alongside similar things like reflect. Perhaps:

def wrap {n} [Ix n] (n:Type) (i:Nat) : n = unsafe_from_ordinal n (mod i (size n))

Then dither_ordered would just be:

def dither_ordered {h w mh mw} (mat: mh=>mw=>Float) (img: h=>w=>Float) : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > mat.(wrap _ (ordinal i)).(wrap _ (ordinal j))

and there'd be no runtime error path at all.

[niklasschmitz]

Thanks @dougalm for the wrap suggestion! Agree that this seems generally useful to have and also improves readability here. Slightly tweaking the signature definition this works:

def wrap (n:Type) [Ix n] (i:Nat) : n = 
   unsafe_from_ordinal n  $ mod i (size n)

Another possible variation is to move the (ordinal i) conversion inside the wrap

def wrap {m} (n:Type) (i:m) [Ix m, Ix n] : n = 
  unsafe_from_ordinal n  $ mod (ordinal i) (size n)

which allows us to write

def dither_ordered {mh mw h w} (mat: mh=>mw=>Float) (img: h=>w=>Float) : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > mat.(wrap mh i).(wrap mw j)

We'll add it upcoming PR, let us know if you have a preference between the two wraps.

[dougalm]

Although the second wrap (the one that includes ordinal i) makes things more compact in this case, I think I prefer the first one because it's the smallest piece of logic while still being safe. It's easy to go from the first wrap version to the second by adding ordinal at the call site, but you can't go the other way around without using unsafe functions.

[adrhill]

Hi guys, glad you like it!

Implementing the example above, we ran into issues trying to apply partial application involving implicit arguments:

def wrap {m} (n:Type) (i:m) [Ix m, Ix n] : n = 
  unsafe_from_ordinal n  $ mod (ordinal i) (size n)

def dither_ordered {mh mw h w} (mat: mh=>mw=>Float) (img: h=>w=>Float) : (h=>w=>Float) =
    for i j. b_to_f $ img.i.j > mat.(wrap mh i).(wrap mw j)

bayer = [[1.0,  9,  3, 11], 
         [ 13,  5, 15,  7],
         [  4, 12,  2, 10],
         [ 16,  8, 14,  6]] / 17.0

dither_bayer = dither_ordered bayer

Type error:Ambiguous type variable

dither_bayer = dither_ordered bayer
               ^^^^^^^^^^^^^^

I can open an issue, in case this isn't tracked already.

[dougalm]

Yes, that's a known issue (see #867), sorry. It will work if you provide the type signature for dither_bayer but that's a lot of work for the one-liner partial application. Quite early on we made the decision to not do any generalization of top-level lets (i.e. turn those ambiguous type variables into universally quantified ones) because it was simpler and avoids problems like Haskell's "dreaded" monomorphism restriction. But we should revisit that choice.