Process of Creating a Stipple Drawing

The Creation of a digital Stipple Drawing is an interactive process. In the beginning we create an initial point distribution and then we add points, remove them, and change existing points' locations, until we are satisfied with the result. This we do with the help of a few tools:

Pulse Density Modulation

Pulse Density Modulation (PDM) is a Halftoning technique: A process whose input is a grayscale image and whose output is a halftone - a two-tone image, black and white. When creating a Stipple Drawing, we use the PDM once on the original image, in order to get an inital dot scatter that we can then edit.
Starting from the upper left corner, we do a sum over every pixel in the picture, according to a unique pattern (shown below), until we reach a certain predesignated number, the "pulse size". The coordinate of the pixel at which we passed the pulse size is marked as the location of a dot. At this point, the pulse size is substracted from the sum, so that we are left with the residue, and the process continues. Once we are done summing over every pixel, the process is complete. We have a list of coordinates that, if we place dots there, give us an approximation of the original grayscale image. Pulse size is a parameter which enables us control over the visual style of the output, where a smaller pulse size gives us results closer to a photorealistic presentation of original image, while a larger one gives a more stylized result.
Since our Stipple Drawings are black dots on white background, we consider black to have the maximal value and white to be equal to zero during the summation.

The PDM Summation pattern, on a micro scale (left) and macro scale (right). The area of the pattern outside the image is summed as 0, and thus has no effect on the result.

Here we see the famous Lenna as an example for the PDM process, input and output:

Pulse Density Modulation: The original grayscale on the left, and the resulting halftone on the right.

Voronoi Iterations

Voronoi Relaxation is an iterative process applied to a dot scatter that changes the location of each dot. In our project, we use it as a tool to remove patterns from the original dot scatter, to create clear separation between visually distinct areas of the picture and even to create effects of light or texture.
In order to explain the process of Voronoi Relaxation, we first need to describe what a Voronoi Diagram is:

Voronoi Diagrams

A Voronoi Diagram is a decomposition of the metric space determined by distances to a specified discrete set of coordinates. The space is divided into Voronoi cells, each of which surrounds on of the coordinates and encloses the area for which there is no other coordinate closer than the one in this cell. The set of coordinates is called generators. The borders between Voronoi cells are straight lines which are of equivalent distance to two generators. Here is an example of a Voronoi Diagram:

In our project we deal with Bounded Voronoi Diagrams. Regular unbounded ones are applied to an infinite space, and as a result, some of the Voronoi cells stretch to infinity. Bounded Diagrams have a predetermined boundary, like the edge of an image, for an example. Generators outside the boundary are ignored and Voronoi cells which protude past that boundary are clipped to fit in. The implementation of a function creating a Bounded Voronoi diagram was a significant part of our project.

A single iteration of Voronoi Relaxation gets a dot scatter and a boundary as an input. From those it creates a Bounded Voronoi diagram using the dots as generators. Then it moves each dot to the Center of Mass of its Voronoi cell. This process can be repeated until the result is satisfactory. The boundary is significant in that it shapes the result, quite literally, by influencing the form of the outer Voronoi cells and constraining dots inside of it. The boundaries in our project are visually distinct segments, marked by the creator of the Stipple Drawing. An example of the results of Voronoi Relaxation, on the image of the eye of a grasshopper:

Original Scatter	One Iteration
Three Iterations	Five Iterations

The GUI

Since the creation of a Stipple Drawing is a highly interactive process, implementing the necessary functions is not enough. The final goal of our project was to create a Graphical User Interface, an interactive tool, with which anyone can create a Stipple Drawing in a quick and efficient manner. We chose the Matlab environment for its high versatility and existing toolbox for image manipulation. Through iterations of development and use, we created a comfortable and user-friendly interface. Here is a list of the main features of the GUI:

Parametric Pulse Density Modulation
Interactive Segmentation via Dedicated Editor
Two methods of Voronoi Relaxation
Manual Point Density Adjustment
Exact Placement and Removal of Individual Dots
Undo/Redo Support and Autosaves
Saving Progress for later Continuation
Exporting to Image Files (PNG, BMP, JPEG) or Scaled Vector Graphics (SVG)
User Friendliness - Fun to Use!

The application and the source code are available on the CGM Labs website to users within the Technion network. Here are two screenshots to conceptualize the use of the application: