etcetera fluids halftoning image processing

Advection-Diffusion of Ink

I want to have the ink on a photo clump together, leading to a black and white image. This is a sort of flow, so my first thought is to take a look at the advection-diffusion equation. Let’s say that the ink distribution across an image is k, the diffusion factor is D, and the flow field is \mathbf {v}:

\frac{\partial k}{\partial t}=\mathbf {\nabla } \cdot (D\mathbf {\nabla } k)-\mathbf {\nabla } \cdot (\mathbf {v} k)

My general idea is that I want the ink to flow toward larger concentrations of ink, unless a pixel is totally black (k=1). Also, I want the ink at each pixel to stay in the range of (0<k<=1). These constraints are tricky to use (quickly unstable!) on a cartesian grid with forward Euler timestepping, so I’ll make some approximations. The analytic result of the advection is easy to use, so I will, but I’ll use image blurring instead of diffusion.

The general idea is as follows. Make a velocity field so that the ink heads towards more ink. Once a pixel is full of ink (k>1), make its speed zero. Similarly, if a pixel has gone negative, make the speed zero as well. Advect the ink, and then soften the edges with a little diffusion. After that, we deal with regions that have (k<0) or (k>1). Diffuse this excess ink with a large length scale, and step forward in time. Or, in algorithm form, one timestep is:

  1. Generate a velocity field for the flow
    • Blur the ink field with a scale of r_{clump}
    • Extract the direction field, \theta from the gradient of the blurred field.
    • Use the direction field as the velocity field with baseline speed 1, and with speed zero where (k<0) or (k>1)
  2. Advect the ink with that velocity field.
  3. Slightly blur the full ink field, with length scale r_{blur}
  4. Strongly blur any regions that are over/negatively inked, using length scale r_{excess}. That is, the bad amounts of ink where there is too much (k>1) or negative (k<0) ink.

Or, more programmatically:

  1. \theta = orientation(blur(k),r_{clump})
    1. u = \cos(\theta)*(k>0)*(k<1), \, v=\sin(\theta)*(k>0)*(k<1)
  2. k_2 = k - \mathbf {\nabla } \cdot (\mathbf {v} k) *dt
  3. k_3 = \text{blur}(k_2,r_{blur})
  4. k_{next} = k_3 - k_3*(k_3<0) + \text{blur}(k_3*(k_3<0),r_{excess}) - (k_3-1)*(k_3>1) + \text{blur}((k_3-1)*(k_3>1),r_{excess})

How do the results look? Here’s an animation of ink-clumping, starting with a radial ramp:

It clumps successfully! Where the image was lighter, the final ink distribution has thinner tendrils, and thicker ones where it was darker. Good!

How about a fancier version? Here’s the same data, but with some bump mapping to make it look more like shiny black ink!

Pretty! But what are the effects of the three different blur radii? The most important is r_{clump}. This defines the scale at which the ink is drawn together. Large values mean large blobs of ink.

Variation of clumping scale: 3, 6, 12 pixels

Next, r_{blur} defines how sharp the output is. Too small, and the edges are pointy. Too big, and it looks fuzzy.

Variation of blur scale: 0.38, 0.75, 1.50

Finally, r_{excess} ensures that the regions that have too much or too little ink shed that excess. If this is too small, the excess values pile up, resulting in an inaccurate output. If it’s quite big, it blurs the image very slightly.

Variation of excess diffusion scale: 1, 6, 12

By clumping each color channel separately, this works just fine for color images, too!

And some more examples in B&W to show the structures:

In uniform regions, it makes blobby patterns that look like noise, and on smooth gradients, it makes nice branching patterns. I like it!

One reply on “Advection-Diffusion of Ink”

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.