Clustered-dot dithering matrix generation #5
Comments
|
Thanks for reaching out!
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
changed the title
|
Some links from HN:
|
makew0rld
added
enhancement
|
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. |
|
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: Contains more clustered-dot matrices: http://ethesis.nitrkl.ac.in/7814/1/2015_Grayscale_Lalitha.pdf |
|
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). |
|
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: |
|
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. |
|
Thank you! That's helpful. I will take a look at this when I have time. |
|
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). |
|
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 |
|
Note: This halftoning Python code might be helpful: https://github.com/bzamecnik/halftone/blob/main/halftone/__init__.py |
|
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:
This will produce the basic non-diagonal dot pattern. Here is the output when N=4 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 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): And here's what these two matrices look like in practice (images upscaled 200%):
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. |
|
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: 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.
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! |
|
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. |
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.
The text was updated successfully, but these errors were encountered: