generate paint strokes from a bitmap image

A project log for If ( ) Then {Paint}

a machine to create canvas paintings of your favorite digital images

John OpsahlJohn Opsahl 07/16/2019 at 03:300 Comments

After completing the six axis cnc mechanical design, I switched gear and focused on developing an algorithm that would generate paint strokes from any bitmap image. This log will describe the details of the algorithm and how I arrived at it. 

At the start of development, I committed to the following requirements:

The purpose of the window frame problem is to define "human" painting style in a mathematical context. The window frame problem goes like this: Suppose you are asked to paint a rectangular window frame (like the one shown below) on canvas. Which brush size and paint strokes do you use?

Regardless of which brush size you use, I propose that 99% of the time, you (and other humans) choose brush strokes that run parallel to the perimeter of the frame. The other 1% of the time you choose brush strokes that run at other angles relative to the perimeter of the frame and would most likely be doing so for artistic effect. The window frame problem is how do you develop an algorithm that will choose brush strokes that run parallel to the perimeter of the frame?

Before I evaluate my brush stroke algorithm against the window frame problem let me explain at a high level how the algorithm works:

  1. Scan across an image (at an angle relative to the horizontal) using a pixel evaluation size that matches the selected brush profile. Brush profile being the area that a brush covers when it contacts the canvas.
  2. If a specified percentage of the pixels in evaluation of the scan (typically 90% or greater) match the current color being painted, mark those as valid areas.
  3. If several valid areas are adjacent to each other along the angle that the image was scanned, connect these valid points to form a brush stroke line.
  4. Repeat steps 1-3 for multiple scan angles between 0 and 180 degrees from the horizontal.
  5. Combine all possible brush stroke lines into a single list (call it brush_strokes_all and order in decreasing length.
  6. Take the first brush stroke line of brush_strokes_all list (i.e. the longest stroke line found during all scans) and put it in another list. Lets call the other list brush_strokes_final.
  7. Take the next brush stroke line of the list and determine if it overlaps any brush stroke lines currently in the brush_strokes_final list. If it doesn't overlap, add the brush stroke line to the brush_strokes_final list. If it does overlap, do nothing and move onto the next brush stroke line in brush_stroke_all.
  8. Repeat step 7 until all brush stroke lines of the brush_stroke_all have been evaluated. The brush_strokes_final is now a list of all the longest possible brush stroke lines that do not overlap.
  9. Void all areas of the image covered by the brush stroke lines in the brush_stroke_final list. 
  10. A few pixel areas the size of the brush profile may still be available at this point due to the no overlap rule. Rerun steps 1-9 until no new brush stroke lines can be created from the image. At this point that algorithm has captured all brush stroke lines needed to cover one color of the image.
  11. Repeat steps 1-10 for all paint colors.

Step 7 is currently my best attempt at solving the window frame problem. It is still an approximate solution because the image would have to be scanned at 0 and 90 degrees from horizontal to capture strokes that are parallel to the perimeter of the frame.  Additionally, if the brush profile is significantly smaller than the frame width of the window frame and the image is scanned at angles close to 0 and 90 degrees from horizontal, the algorithm will find the longest brush stroke lines along the diagonal of each side of the frame (as opposed to the longest lines parallel to the perimeter; see blue strokes of example below). The resulting brush stroke lines from the algorithm sometimes look like a wood grain pattern. I certainly was not expecting to discover something organic looking when trying to paint a rectangular square window frame.

Progressing from low detail to high detail is a feature that I have not yet explored with this algorithm. It should be possible to start with larger brushes for each color and gradually move to smaller brushes for finer detail. My first thought to make a complete solution for this is to modify step 9 of the algorithm. Instead of voiding all area covered by the brush stroke lines, only void the pixels in the area covered by the brush stroke lines that match the paint color. By not voiding the 10% or fewer pixels that don't match in color, the algorithm will be able to define paint strokes at those locations when a smaller brush is used.

There is so much more to develop and refine with this algorithm and other methods for generating paint strokes from bitmap images. I will post the algorithm code to this project after I have cleaned it up and added comments.

Recommended reading on stroke-based painterly rendering algorithms: