Halftone Circle Pattern Algorithm Implementation

Question

The problem is implementation of specific halftone circle pattern algorithm, which should generate a bitmap image composed of black and white circles reflecting the halftones of the original image. When viewed from a distance, the image should display smooth shading, but up close, it should consist of only pure white or pure black circles.

The most similar result I could find is the halftone screen option in Photoshop:

Image -> Mode -> Bitmap -> Halftone Screen -> Round shape

Below are examples of the source and result images: Source image:

Result image (input DPI: 83, result 300 pixels/centimeter):

As demonstrated, the primarily dark areas contain white circles, while the primarily bright areas have black circles.

The fundamental concept of halftoning involves mapping pixel intensity to the size of the target circle by following these steps:

• Obtain the average intensity of the pixel group in the area.

• Draw the dot such that its surface area is proportional to the average intensity percentage (from white to black).

This approach may produce images like this:

However, this outcome does not align with the goals, as it only consists of circles of one color and features overlapping circles that create undesirable "stars."

On a closer look on Photoshop's algorithm, we can see that the primary challenge lies in the transition areas. When the average pixel intensity between black and white is 50%, the algorithm forms squares and then smoothly transitions from black circles on white areas to white circles on black areas:

Real example of this haltone algorithm:

Looking for assistance with the mathematics and algorithms that could produce a similar output!

Answer 1

Consider the surface of equation $z=(1-x^2)(1-y^2)$ in the domain $[-1,1]\times[-1,1]\times[0,1]$.

The cross-section by the plane $z=0$ is a square, and when you move it up, it progressively turns to a circle.

Now you can rotate the coordinates and work with $x=u+v,y=u-v$ to make the square a diamond. Fill a cell with white when the function exceeds $z$ and black below, and black outside the diamond (or conversely).

A last difficulty is to linearize the scale, i.e. find the $z$ that corresponds to a desired fraction of the area. Analytic integration might be difficult. You can tabulate once for all for different values of $z$ by simple pixel counting, and resort to inverse interpolation. Accuracy is not critical.