halftoning image processing

Checkerboard Distortion Halftoning

In a previous post, I deformed a grid of lines to halftone an image. I wanted to do the same thing with a checkerboard, but I figured that it would be similarly difficult and would require optimization. So I used the same optimization framework with a checkerboard, applied it to a brightness ramp, and found:

Hm! It looks like halftoning with a checkerboard requires some local twisting. Maybe this is even doable analytically! How can we parameterize this sort of local twisting? Let’s look at some local twisting:

As the central black square twists, its neighboring black squares must turn and grow by the same amount. The maximum size is when they turn 45 degrees, and are flush with each other. The red lines connect the centers of the white squares, and you can see show that the black corners follow those lines. I’ll parameterize the degree of twist as the relative distance that the corners move along that red line, from the midpoint to the end. Let’s call that distance s. The examples above show s=[0, 0.3, 0.6, 0.9], and s=1 would be entirely black.

How does s relate to the darkness? We can again use the red square, and a bit of geometry. If the red square’s width is w, the area of one white triangle in the red square is A_w= (s^2-1)w^2/8, so the average brightness of the square is B=4A_w/w^2= (s^2-1)/2. With that, we can solve for the needed distortion, s=\sqrt{1-2 B}.

Of course, that’s only useful when we twist black squares, making the image darker. If we twist a white square, the image will get brighter. The final wrinkle is that we need to rotate the squares in alternating directions for neighboring rows/columns.

So, combining it all, if we have the corners of the grid at unit-spaced integer values of (X[i,j],Y[i,j]), and the image brightness B[i,j], we can make S[i,j]=\text{sign}(B[i,j]-0.5)* \sqrt{| 2 B[i,j]-1| }. The modified positions are then

\begin{aligned} X_2[i,j] &= X[i,j] + \frac{s}{2}\left( \text{mod}(Y[i,j],2)*2-1 \right) \\ Y_2[i,j] &= Y[i,j] + \frac{s}{2}\left( \text{mod}(X[i,j]+(S[i,j]>0),2)*2-1 \right) \end{aligned}

And now if you draw the grid with those new corners, you get this improved gradient:

And here’s the Mona Lisa and the Girl with Pearl Earring:

This is much faster than gradient descent!

And here’s the animated version!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.