Clustered-dot dithering matrix generation

robert-aleksic commented 3 years ago

Hi, I saw the post in your blog re dithering, where you asked if one know how to do clustered dithering to contact you. Dithering you mentioned is usally called halftone dithering and have long history in silk printing and offset printing. You can find many resources on it on the net, but what you have to do is sample your image withe some frequency in 256 levels of gray, and then replace each sample by 16x16 matrix of pixels representing 256 levels of gray. It can be also be done with lines instead of dots resulting in line raster, where you vary width of the line with intensity. It is also not bad idea to do bluring and unsharp masking before sampling which is equivalent of applying lowpas 2d filter before sampling as in Niquist theorem where you first filter the signal before sampling to avoid artifacts. If you want to do quick experiment, just replace each pixel with 8x8 pixels representing black dots on white background for levels below 50% and white dots on black background for leves above 50%. If you need any help feel free to contact me at robert.aleksic at gmail.com. cheers robby

p.s. if you want to do it in color, you separate your image to components like CMYK for ofset printing and then apply all four images one on on top of the other, with varying angles of raster to obtaine nice rosette like here: https://cdn2.hubspot.net/hubfs/2296165/Imported_Blog_Media/CMKdot-1.jpg. Black component is created to avoid usage of to much ink and preserve gray balance, but that is another topic - color calibration.

makew0rld commented 3 years ago

Thanks for reaching out!

replace each sample by 8x8 matrix of pixels representing 256 levels of gray

This is the part I'm not sure about. How can I generate this matrix? I already have matrices like this in the code and use them, but it's generating them that I'm not sure about.

I'll use this thread to track clustered-dot dithering matrix generation in general.

makew0rld commented 3 years ago

Some links from HN:

https://github.com/gabrielarchanjo/marvin-framework/blob/f5008c70859198b80bb430f97aa1db9c66c9548e/marvinproject/dev/MarvinPlugins/src/org/marvinproject/image/halftone/circles/Circles.java

https://dl.acm.org/doi/pdf/10.1145/127719.122727?casa_token=r7RLX2FwCCkAAAAA:accvlG1_tRYkdMpDpsxL3OoNkuFpNNNUxizbFE026c-utxJDibQxb-fnJ6Vann2UJfDVn61oKeN7eS4

(ordered dither): This algorithm is generally identified as a dispersed-dot technique [Limb 69], but if the intensity threshold levels are spatially concentrated it results in a clustered-dot dithering.

robert-aleksic commented 3 years ago

since you have 256 pixels, you can have 0-127 with white dots on black background and 127-255 as inverse images. 0 is all black and then you can proceed by adding one white dot in each step, starting from center in spiral fashion. Other solution would be to render circles of appropriate sizes on 8x8 matrix. This is certainly oversipmlification but you can start with circle and then count number of white dots and add/remove some at the circle edge randomly.You can find more on halftone dithering here: https://en.wikipedia.org/wiki/Halftone

If you want to do it properly then you should have few parameters like halftone screen frequency and angle, as well as final image resoulution. In offset printing for example, screen frequiency is in 150's lines per inch magnitude, and final resolution in 2000 dots pre inch, and matrix 16x16 is usually used so that you can render circles from the center much more realistically.

Proper approach for level l (0..127) in x by x pixels square, shoud be propably to render cicrcle of radius r, such that r^2*pi/x^2 = l/256; then count white pixels and adjust to l pixels by adding/removing them randomly on the edge of circle.

If you want to go as precise as possible then you can render antialliased circle on gray scale matrix, leave the dots inside the circle white, and turn on some of gray one's on the circle border to white and remove others so that nuber of white dots / number of all dots = l/256.

makew0rld commented 3 years ago

Thanks. I admit I don't totally get what you mean, but I think I just need to read it again more in depth.

Some more links from HN:

https://stackoverflow.com/questions/10572274/how-to-create-cmyk-halftone-images-from-a-color-image/10575940#10575940

Contains more clustered-dot matrices: http://ethesis.nitrkl.ac.in/7814/1/2015_Grayscale_Lalitha.pdf

robert-aleksic commented 3 years ago

Sorry I made a mistake. Halftone matrix have to be 16x16 to have 256 levels of gray, 8x8 can give you at most 64 levels of gray.

Think of it as simple bit map representing circles of various sizes. If, for example, you have circle occupying 64 pixels it coresponds to 25% of black (level 64 in 0..255).

robert-aleksic commented 3 years ago

Hi, I had some spare time so I wrote you the code. It is in pascal which I use most, but should be fairly simple to understand. Here is the code and output. If you want to run it yourself, you can instal fpc, compile and run it.

program halftones;

const
  maxw = 100;
  maxlevels = maxw * maxw;

  step = 0.1;

type
  bitmap = array [0..maxw-1,0..maxw-1] of boolean;
  shape  = record
             cx,cy,r : real;
             num     : integer
           end;

var
  interactive : boolean;
  levels, width : integer;

  g : array [0..maxlevels-1] of bitmap;
  c : array [0..maxlevels-1] of shape;

  last, steps : integer;

  function empty : bitmap;
  var i,j : integer;
  begin
    for i := 0 to width-1 do
      for j := 0 to width-1 do
        empty[i,j] := false
  end;

  function inverted (b:bitmap) : bitmap;
  var i,j : integer;
  begin
    for i := 0 to width-1 do
      for j := 0 to width-1 do
        inverted[i,j] := not b[i,j]
  end;

  procedure out (l:integer);
  var i,j : integer;
  begin
    writeln ('level: ',l);
    with c[l] do writeln ('shape: ',cx:5:1,cy:5:1,r:5:1);
    for i := 0 to width-1 do
    begin
      write (' ':2);
      for j := 0 to width-1 do
        if g[l][i,j] then write ('x') else write ('.');
      writeln
    end;
    writeln
  end;

  function dotsinshape (s:shape) : integer;
  var i,j,n : integer;
  begin
    with s do
    begin
      n := 0;
      for i := -round(r)-1 to round (r)+1 do
        for j := -round(r)-1 to round (r)+1 do
          if sqr(i-cx) + sqr(j-cy) <= sqr(r)
          then n := n+1
     end;
     dotsinshape := n
  end;

  procedure render (l:integer; var b:bitmap);
  var off:real; n,i,j : integer;
  begin
    off := width/2;
    g[l] := empty;
    n := 0;
    if l<>0
    then for i := 1 to width-1 do
           for j := 1 to width-1 do
             if n<l
             then with c[l] do
                  if sqr (i-off-cx) + sqr (j-off-cy) <= sqr(r)
                  then begin
                           g[l][i-1,j-1] := true;
                           n := n+1
                         end
  end;

var
  s : shape;
  i,j : integer;

begin

  interactive := paramcount = 1;

  if not interactive
  then levels := 100
  else begin
         write ('Levels? ');
         readln (levels);
       end;

  width := round (sqrt(levels));
  if sqr(width) < levels then width := width+1;
  last  := (levels-1) div 2;
  steps := round (1/step);

  writeln ('Generating halftones for ',levels,' levels; width= ',width, ', steps= ',steps);

  // find circles which will be rendered with 'level' number of pixels
  for i := 0 to last do
    c[i].r := -1;

  for i := 0 to steps do
    for j := 0 to steps do
    begin
      with s do
      begin
        r := step;
        cx := step*i;
        cy := step*j
      end;
      while s.r <= (width/2) do
      begin
        s.num := dotsinshape (s);
        if s.num <= last
        then if c[s.num].r = -1
             then c[s.num] := s
             else
        else if (c[last].r=-1) or (c[last].num>s.num)
             then c[last] := s;
        s.r := s.r+step
      end
    end;

  // patch missing circles with next bigger one
  j := 0;
  for i := 0 to last do
    if c[i].r=-1
    then begin
           j := i+1;
           while c[j].r=-1 do j := j+1;
           c[i] := c[j]
         end;

  // render circles for first half of levels and invert for others
  g[0] := empty;
  for i := 1 to levels-1 do
    if i <= last
    then render (i,g[i])
    else g[i] := inverted (g[levels-1-i]);

  if not interactive
  then for i := 0 to levels-1 do out (i)
  else repeat
         write ('level? '); readln (i);
         if i<>-1 then out (i)
       until i=-1

end.

and here is output:

Generating halftones for 100 levels; width= 10, steps= 10
level: 0
shape:   0.0  0.2  0.1
  ..........
  ..........
  ..........
  ..........
  ..........
  ..........
  ..........
  ..........
  ..........
  ..........

level: 1
shape:   0.0  0.0  0.1
  ..........
  ..........
  ..........
  ..........
  ....x.....
  ..........
  ..........
  ..........
  ..........
  ..........

level: 2
shape:   0.0  0.1  1.0
  ..........
  ..........
  ..........
  ..........
  ....xx....
  ..........
  ..........
  ..........
  ..........
  ..........

level: 3
shape:   0.1  0.1  1.0
  ..........
  ..........
  ..........
  ..........
  ....xx....
  ....x.....
  ..........
  ..........
  ..........
  ..........

level: 4
shape:   0.0  0.1  1.1
  ..........
  ..........
  ..........
  ....x.....
  ....xx....
  ....x.....
  ..........
  ..........
  ..........
  ..........

level: 5
shape:   0.0  0.0  1.1
  ..........
  ..........
  ..........
  ....x.....
  ...xxx....
  ....x.....
  ..........
  ..........
  ..........
  ..........

level: 6
shape:   0.0  0.4  1.2
  ..........
  ..........
  ..........
  ....xx....
  ....xx....
  ....xx....
  ..........
  ..........
  ..........
  ..........

level: 7
shape:   0.0  0.1  1.4
  ..........
  ..........
  ..........
  ....xx....
  ...xxx....
  ....xx....
  ..........
  ..........
  ..........
  ..........

level: 8
shape:   0.0  0.4  1.6
  ..........
  ..........
  ..........
  ....xx....
  ...xxxx...
  ....xx....
  ..........
  ..........
  ..........
  ..........

level: 9
shape:   0.0  0.0  1.5
  ..........
  ..........
  ..........
  ...xxx....
  ...xxx....
  ...xxx....
  ..........
  ..........
  ..........
  ..........

level: 10
shape:   0.0  0.1  1.9
  ..........
  ..........
  ..........
  ...xxx....
  ...xxxx...
  ...xxx....
  ..........
  ..........
  ..........
  ..........

level: 11
shape:   0.1  0.1  2.0
  ..........
  ..........
  ..........
  ...xxx....
  ...xxxx...
  ...xxx....
  ....x.....
  ..........
  ..........
  ..........

level: 12
shape:   0.0  0.3  2.0
  ..........
  ..........
  ..........
  ...xxxx...
  ...xxxx...
  ...xxxx...
  ..........
  ..........
  ..........
  ..........

level: 13
shape:   0.0  0.0  2.0
  ..........
  ..........
  ....x.....
  ...xxx....
  ..xxxxx...
  ...xxx....
  ....x.....
  ..........
  ..........
  ..........

level: 14
shape:   0.0  0.2  2.1
  ..........
  ..........
  ....x.....
  ...xxxx...
  ...xxxx...
  ...xxxx...
  ....x.....
  ..........
  ..........
  ..........

level: 15
shape:   0.1  0.2  2.2
  ..........
  ..........
  ....x.....
  ...xxxx...
  ...xxxx...
  ...xxxx...
  ....xx....
  ..........
  ..........
  ..........

level: 16
shape:   0.0  0.3  2.2
  ..........
  ..........
  ....xx....
  ...xxxx...
  ...xxxx...
  ...xxxx...
  ....xx....
  ..........
  ..........
  ..........

level: 17
shape:   0.0  0.1  2.2
  ..........
  ..........
  ....xx....
  ...xxxx...
  ..xxxxx...
  ...xxxx...
  ....xx....
  ..........
  ..........
  ..........

level: 18
shape:   0.1  0.2  2.3
  ..........
  ..........
  ....xx....
  ...xxxx...
  ..xxxxx...
  ...xxxx...
  ...xxx....
  ..........
  ..........
  ..........

level: 19
shape:   0.0  0.1  2.3
  ..........
  ..........
  ...xxx....
  ...xxxx...
  ..xxxxx...
  ...xxxx...
  ...xxx....
  ..........
  ..........
  ..........

level: 20
shape:   0.1  0.3  2.5
  ..........
  ..........
  ...xxx....
  ...xxxx...
  ..xxxxx...
  ..xxxxx...
  ...xxx....
  ..........
  ..........
  ..........

level: 21
shape:   0.0  0.0  2.3
  ..........
  ..........
  ...xxx....
  ..xxxxx...
  ..xxxxx...
  ..xxxxx...
  ...xxx....
  ..........
  ..........
  ..........

level: 22
shape:   0.0  0.5  2.5
  ..........
  ..........
  ...xxxx...
  ...xxxx...
  ..xxxxxx..
  ...xxxx...
  ...xxxx...
  ..........
  ..........
  ..........

level: 23
shape:   0.0  0.1  2.8
  ..........
  ..........
  ...xxxx...
  ..xxxxx...
  ..xxxxx...
  ..xxxxx...
  ...xxxx...
  ..........
  ..........
  ..........

level: 24
shape:   0.0  0.2  2.8
  ..........
  ..........
  ...xxxx...
  ..xxxxx...
  ..xxxxxx..
  ..xxxxx...
  ...xxxx...
  ..........
  ..........
  ..........

level: 25
shape:   0.0  0.0  2.9
  ..........
  ..........
  ..xxxxx...
  ..xxxxx...
  ..xxxxx...
  ..xxxxx...
  ..xxxxx...
  ..........
  ..........
  ..........

level: 26
shape:   0.0  0.1  2.9
  ..........
  ..........
  ..xxxxx...
  ..xxxxx...
  ..xxxxxx..
  ..xxxxx...
  ..xxxxx...
  ..........
  ..........
  ..........

level: 27
shape:   0.1  0.1  3.0
  ..........
  ..........
  ..xxxxx...
  ..xxxxx...
  ..xxxxxx..
  ..xxxxx...
  ..xxxxx...
  ....x.....
  ..........
  ..........

level: 28
shape:   0.0  0.2  3.0
  ..........
  ..........
  ..xxxxx...
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxx...
  ..........
  ..........
  ..........

level: 29
shape:   0.0  0.0  3.0
  ..........
  ....x.....
  ..xxxxx...
  ..xxxxx...
  .xxxxxxx..
  ..xxxxx...
  ..xxxxx...
  ....x.....
  ..........
  ..........

level: 30
shape:   0.0  0.2  3.1
  ..........
  ....x.....
  ..xxxxx...
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxx...
  ....x.....
  ..........
  ..........

level: 31
shape:   0.0  0.1  3.1
  ..........
  ....x.....
  ..xxxxx...
  ..xxxxxx..
  .xxxxxxx..
  ..xxxxxx..
  ..xxxxx...
  ....x.....
  ..........
  ..........

level: 32
shape:   0.0  0.3  3.1
  ..........
  ....xx....
  ..xxxxx...
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxx...
  ....xx....
  ..........
  ..........

level: 33
shape:   0.0  0.2  3.2
  ..........
  ....xx....
  ..xxxxx...
  ..xxxxxx..
  .xxxxxxx..
  ..xxxxxx..
  ..xxxxx...
  ....xx....
  ..........
  ..........

level: 34
shape:   0.0  0.4  3.3
  ..........
  ....xx....
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ....xx....
  ..........
  ..........

level: 35
shape:   0.0  0.1  3.2
  ..........
  ...xxx....
  ..xxxxx...
  ..xxxxxx..
  .xxxxxxx..
  ..xxxxxx..
  ..xxxxx...
  ...xxx....
  ..........
  ..........

level: 36
shape:   0.1  0.4  3.4
  ..........
  ....xx....
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ...xxxx...
  ..........
  ..........

level: 37
shape:   0.0  0.0  3.2
  ..........
  ...xxx....
  ..xxxxx...
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  ..xxxxx...
  ...xxx....
  ..........
  ..........

level: 38
shape:   0.0  0.5  3.4
  ..........
  ...xxxx...
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ...xxxx...
  ..........
  ..........

level: 39
shape:   0.0  0.4  3.4
  ..........
  ...xxxx...
  ..xxxxxx..
  ..xxxxxx..
  .xxxxxxx..
  ..xxxxxx..
  ..xxxxxx..
  ...xxxx...
  ..........
  ..........

level: 40
shape:   0.0  0.5  3.5
  ..........
  ...xxxx...
  ..xxxxxx..
  ..xxxxxx..
  .xxxxxxxx.
  ..xxxxxx..
  ..xxxxxx..
  ...xxxx...
  ..........
  ..........

level: 41
shape:   0.0  0.1  3.6
  ..........
  ...xxxx...
  ..xxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  ..xxxxxx..
  ...xxxx...
  ..........
  ..........

level: 42
shape:   0.0  0.3  3.7
  ..........
  ...xxxx...
  ..xxxxxx..
  .xxxxxxx..
  .xxxxxxxx.
  .xxxxxxx..
  ..xxxxxx..
  ...xxxx...
  ..........
  ..........

level: 43
shape:   0.1  0.1  3.7
  ..........
  ...xxxx...
  ..xxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  ..xxxxx...
  ..........
  ..........

level: 44
shape:   0.0  0.3  3.8
  ..........
  ..xxxxx...
  ..xxxxxx..
  .xxxxxxx..
  .xxxxxxxx.
  .xxxxxxx..
  ..xxxxxx..
  ..xxxxx...
  ..........
  ..........

level: 45
shape:   0.0  0.0  3.7
  ..........
  ..xxxxx...
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxx..
  ..xxxxx...
  ..........
  ..........

level: 46
shape:   0.0  0.1  3.9
  ..........
  ..xxxxx...
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxxx.
  .xxxxxxx..
  .xxxxxxx..
  ..xxxxx...
  ..........
  ..........

level: 47
shape:   0.1  0.1  4.0
  ..........
  ..xxxxx...
  .xxxxxxx..
  .xxxxxxx..
  .xxxxxxxx.
  .xxxxxxx..
  .xxxxxxx..
  ..xxxxx...
  ....x.....
  ..........

level: 48
shape:   0.0  0.2  4.0
  ..........
  ..xxxxx...
  .xxxxxxx..
  .xxxxxxxx.
  .xxxxxxxx.
  .xxxxxxxx.
  .xxxxxxx..
  ..xxxxx...
  ..........
  ..........

level: 49
shape:   0.0  0.0  4.0
  ....x.....
  ..xxxxx...
  .xxxxxxx..
  .xxxxxxx..
  xxxxxxxxx.
  .xxxxxxx..
  .xxxxxxx..
  ..xxxxx...
  ....x.....
  ..........

level: 50
shape:   0.0  0.0  0.0
  xxxx.xxxxx
  xx.....xxx
  x.......xx
  x.......xx
  .........x
  x.......xx
  x.......xx
  xx.....xxx
  xxxx.xxxxx
  xxxxxxxxxx

level: 51
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xx.....xxx
  x.......xx
  x........x
  x........x
  x........x
  x.......xx
  xx.....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 52
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xx.....xxx
  x.......xx
  x.......xx
  x........x
  x.......xx
  x.......xx
  xx.....xxx
  xxxx.xxxxx
  xxxxxxxxxx

level: 53
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xx.....xxx
  x.......xx
  x.......xx
  x........x
  x.......xx
  x.......xx
  xx.....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 54
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xx.....xxx
  x.......xx
  x.......xx
  x.......xx
  x.......xx
  x.......xx
  xx.....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 55
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xx.....xxx
  xx......xx
  x.......xx
  x........x
  x.......xx
  xx......xx
  xx.....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 56
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxx....xxx
  xx......xx
  x.......xx
  x.......xx
  x.......xx
  x.......xx
  xx.....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 57
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxx....xxx
  xx......xx
  x.......xx
  x........x
  x.......xx
  xx......xx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 58
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxx....xxx
  xx......xx
  x.......xx
  x.......xx
  x.......xx
  xx......xx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 59
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxx....xxx
  xx......xx
  xx......xx
  x........x
  xx......xx
  xx......xx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 60
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxx....xxx
  xx......xx
  xx......xx
  x.......xx
  xx......xx
  xx......xx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 61
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxx....xxx
  xx......xx
  xx......xx
  xx......xx
  xx......xx
  xx......xx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 62
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxx...xxxx
  xx.....xxx
  x.......xx
  x.......xx
  x.......xx
  xx.....xxx
  xxx...xxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 63
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxx..xxxx
  xx......xx
  xx......xx
  xx......xx
  xx......xx
  xx......xx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 64
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxx...xxxx
  xx.....xxx
  xx......xx
  x.......xx
  xx......xx
  xx.....xxx
  xxx...xxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 65
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxx..xxxx
  xx......xx
  xx......xx
  xx......xx
  xx......xx
  xx......xx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 66
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxx..xxxx
  xx.....xxx
  xx......xx
  x.......xx
  xx......xx
  xx.....xxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 67
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxx..xxxx
  xx.....xxx
  xx......xx
  xx......xx
  xx......xx
  xx.....xxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 68
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxx.xxxxx
  xx.....xxx
  xx......xx
  x.......xx
  xx......xx
  xx.....xxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 69
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxx.xxxxx
  xx.....xxx
  xx......xx
  xx......xx
  xx......xx
  xx.....xxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 70
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxx.xxxxx
  xx.....xxx
  xx.....xxx
  x.......xx
  xx.....xxx
  xx.....xxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 71
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xx.....xxx
  xx......xx
  xx......xx
  xx......xx
  xx.....xxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 72
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xx.....xxx
  xx.....xxx
  xx......xx
  xx.....xxx
  xx.....xxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 73
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xx.....xxx
  xx.....xxx
  xx......xx
  xx.....xxx
  xx.....xxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 74
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xx.....xxx
  xx.....xxx
  xx.....xxx
  xx.....xxx
  xx.....xxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 75
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxx....xxx
  xx.....xxx
  xx......xx
  xx.....xxx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 76
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxx....xxx
  xx.....xxx
  xx.....xxx
  xx.....xxx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 77
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxx....xxx
  xxx....xxx
  xx......xx
  xxx....xxx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 78
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxx...xxxx
  xx.....xxx
  xx.....xxx
  xx.....xxx
  xxx...xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 79
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxx...xxxx
  xxx....xxx
  xx.....xxx
  xx.....xxx
  xxx...xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 80
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxx...xxxx
  xxx....xxx
  xx.....xxx
  xxx....xxx
  xxx...xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 81
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx..xxxx
  xxx....xxx
  xx.....xxx
  xxx....xxx
  xxx...xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 82
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx..xxxx
  xxx....xxx
  xx.....xxx
  xxx....xxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 83
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx..xxxx
  xxx....xxx
  xxx....xxx
  xxx....xxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 84
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx.xxxxx
  xxx....xxx
  xxx....xxx
  xxx....xxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 85
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx.xxxxx
  xxx....xxx
  xxx....xxx
  xxx....xxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 86
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx.xxxxx
  xxx...xxxx
  xx.....xxx
  xxx...xxxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 87
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxx....xxx
  xxx....xxx
  xxx....xxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 88
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxx...xxxx
  xxx....xxx
  xxx...xxxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 89
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxx...xxxx
  xxx....xxx
  xxx...xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 90
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxx...xxxx
  xxx...xxxx
  xxx...xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 91
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx..xxxx
  xxx....xxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 92
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx..xxxx
  xxx...xxxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 93
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx..xxxx
  xxxx..xxxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 94
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx.xxxxx
  xxx...xxxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 95
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx.xxxxx
  xxxx..xxxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 96
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx..xxxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 97
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx..xxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 98
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxx.xxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

level: 99
shape:   0.0  0.0  0.0
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx

robert-aleksic commented 3 years ago

It is completely unoptimised and with rough edges everywhere but serves the purpose to ilustrate the principle. It brute force search for circles which will be rendered with adequate number of black dots, and afterwards just render those circles.

makew0rld commented 3 years ago

Thank you! That's helpful. I will take a look at this when I have time.

robert-aleksic commented 3 years ago

if you want to dig dipper into halftoning technology 1987 digital halftoning from mit press (Robert Ulichney) and 2008 modern digital halftoning, 2nd ed (Daniel L. Lau and Gonzalo R. Arce) are must, and if you want to get better insight in digital signal processing any univrsity course book is good introduction. It is very hard to do proper image processing without those techniques (just try to make a analog clock simulation with continous smooth moving seconds hand and you'll se why).

robert-aleksic commented 3 years ago

i looked a little into your code, you can create matrices you are using for convolution by summing up halftone single level matrices, something like m := zeroes; for l := 0 to levels-1 do append (m,g[l]). Those matrices you are using are just filter response to pulse signal, also known as filter response matrix, you can find more about them in second book I have previously recomended.

makew0rld commented 3 years ago

Note: This halftoning Python code might be helpful: https://github.com/bzamecnik/halftone/blob/main/halftone/__init__.py

matejlou commented 1 year ago

Hi there, I came across this repo while doing research for my own dithering implementation. I thought I'd take a stab at a clustered-dot/halftone matrix generation algorithm and I believe I have a pretty simple but effective solution. I'll be using it in my own project and I hope it can be useful for this one as well. The algorithm goes as follows:

Define an empty 2D grid of size N*N
Define the dot origin as the centre of this grid (N/2)
For every cell in the grid, calculate the (squared) distance between the cell centre and the dot origin
Sort the distances in ascending order
Map the sorted index of each distance back to the original sampled cell.

This will produce the basic non-diagonal dot pattern. Here is the output when N=4

[12  6  8 14]
[ 4  0  2 10]
[ 5  1  3 11]
[13  7  9 15]

With a few more steps we can get the diagonal variant. This is done by creating four sub-matrices derived from the initial output matrix M as follows:

Top Left: Same as M Top Right: M, but with values reversed and offset by the size of M Bottom Left: Same as Top Right Bottom Right: Same as Top Left

If you want to avoid duplicate values and use the full possible range, simply alternate odd and even values between each pair of similar sub-matrices. Here is the output (still N=4):

[24 12 16 28 40 52 48 36]
[ 8  0  4 20 56 64 60 44]
[10  2  6 22 54 62 58 42]
[26 14 18 30 38 50 46 34]
[41 53 49 37 25 13 17 29]
[57 65 61 45  9  1  5 21]
[55 63 59 43 11  3  7 23]
[39 51 47 35 27 15 19 31]

And here's what these two matrices look like in practice (images upscaled 200%):

renderHALFTONE renderHALFTONE_DIAG

One thing to note is that - as we're dealing with circles - some of the distances are going to be equal, so the order of these ties will likely vary depending on the implementation. Maybe it's possible to specify how to handle ties during the sort procedure in order to produce more appealing distributions, but I haven't really taken the time to think about that yet :)

I hope this is useful to you or to anybody else who might be looking up this topic. I have a basic Python implementation that I used to produce the matrices here and I'm happy to share it if you'd like further clarification.

matejlou commented 1 year ago

I'm going to add a little addendum as I've realised that with a small tweak you can produce more symmetric distributions.

Instead of sampling the distance for every cell in the grid, just sample the distance for one quadrant, (N/2)*(N/2). You can derive the 3 remaining quadrants by rotating the first quadrant at 90 degree increments. Finally, for every quadrant, multiply each value by 4 and add an offset from 0 to 3, incrementing clockwise or anti-clockwise.

The result of this is a dot pattern that expands while preserving rotational symmetry, which I feel makes for a more balanced look. Here is the output for N=4 once again:

[12  8  5 13]
[ 4  0  1  9]
[11  3  2  6]
[15  7 10 14]

And in practice below. If you compare this pattern to the one in my previous comment you might notice that the vertical line artifacts have been removed. Which one you prefer may come down to personal preference.

renderHALFTONE_ROT

This technique is also extensible to odd values of N with some minor changes, but I will leave that as an exercise to the reader!

makew0rld commented 1 year ago

Thanks for sharing this! I don't plan on implementing this in library anytime soon, but I appreciate having this here for me in the future and others to use.

One thing I would note is that the gradient should begin with pure black and end with pure white. Not sure how you're rendering those images, so it could be an issue with that code, but it could also be an issue with the matrix values you've generated.

makew0rld / dither

Clustered-dot dithering matrix generation #5