Categories

# Grid Distortion Halftoning

Imagine that we have a screen door, and we want to push around the wires to make an image. It’s not a simple problem! There’s a fixed number of wires in each direction, so how do we properly distribute them?

Let’s define a pair of phase maps for x and y, $\phi_x$ and $\phi_y$. We’ll draw contours of the phase maps where they have integer values, giving spacings:

\begin{aligned} \lambda_x &= \left(\frac{d\phi_x}{dx} \right)^{-1} \\ \lambda_y &= \left(\frac{d\phi_y}{dy} \right)^{-1} \end{aligned}

The lines are drawn with width $w$, so the output darkness is approximately

\begin{aligned} I &= \frac{(\lambda_x-w)(\lambda_y-w)}{\lambda_x \lambda_y}\\ &= \left( w \frac{d\phi_x}{dx}-1 \right) \left( w \frac{d\phi_y}{dy}-1 \right) \end{aligned}

The image has width and height $W_x,W_y$, and $N_x,N_y$ lines in each direction, so we’ll enforce boundary conditions of

\begin{aligned} \phi_x(x=0) &= 0 \\ \phi_y(y=0) &= 0 \\ \phi_x(x=W_x) &= N_x \\ \phi_y(y=W_y) &= N_y \end{aligned}

Additionally, we only want one line per contour level, so enforce

\begin{aligned} \frac{d\phi_x}{dx} &> 0 \\ \frac{d\phi_y}{dy} &> 0 \end{aligned}

With those boundary conditions and output brightness, the problem is fairly well defined. Unfortunately, this sort of system can’t represent every image. The total ink on the page is approximately $W_y N_x w + W_x N_y w-N_x N_y w^2$, so we should choose the parameters to match the input image.

## Analytic Approach

The first approximate solution is found by integrating across the image in each direction to form the phase maps, then scaling them to fit the boundary conditions. Unfortunately, this often leads to unsightly vertical or horizontal artifacts. This can be improved by smoothing in the cross-integration directions, but not entirely fixed.

## Optimization Approach

The next option is to treat this as an optimization problem and throw gradient descent at it. I’ll define an error function as

$\epsilon = \sum(I_{in}-I_{out})^2+k \sum \left( \left(\frac{d\phi_x}{dy}\right)^2 + \left(\frac{d\phi_y}{dx}\right)^2 \right)$

The first term tries to get the right brightness. The second term ensures smoothness, reducing the artifacts. Analytically enforcing the boundary conditions is still a hassle, so it’s easier and more practical to work with the gradients of the phase maps, $\Delta\phi_x(x,y),\Delta\phi_y(x,y)$. With these, we can restrict the values to always be positive, fulfilling the single-line-per-contour condition mentioned earlier. For each row, we integrate across $\Delta\phi_x(x,y)$, then rescale the row to ensure that $\phi_x(x=W_x) = N_x$. And do the same sort of thing for the y-direction.

Start with uniform values of $\Delta\phi_x(x,y)=N_x/W_x$, and similar for y. From there, compute the Jacobian of the error, $J$ due to changing each $\Delta\phi(x,y)$. We find the direction of the gradient to be the pseudoinverse of $J$, and step downhill. This takes some linear search to find a reasonable step size, but it works well! You can see examples above, compared to the simple integration method.

There are two important parameters that I haven’t investigated: the resolution of the phase map, and the smoothing factor. These are varied in the image below. Increasing k results in a smoother result, as expected. A non-zero value seems necessary to reduce artifacts. Also, increasing the resolution of the phase map results in more detail. Good, things make sense! The horizontal axis is the width of the phase map in pixels. The vertical axis is the smoothing factor.

To speed things up, you can start with a low-resolution image, and increase the resolution as it converges (as I did above). Or start with a smoothed version of the initial approach.

Of course, this method has trouble sometimes. For example, if there is too much detail, or alternation of dark and light in a small region, it can’t cope. The temple example shows this well: