Stippling and TSP art in R: emulating StippleGen

Stippling is the creation of a pattern simulating varying degrees of solidity or shading by using small dots (Wikipedia).StippleGen is a piece of software that renders images using stipple patterns, which I discovered on Xi’an’s blog a couple days ago.

Stippled version of a sketch by Paul Cézanne, rendered in R

StippleGen uses an algorithm by Adrian Secord (described here) that turns out to be related to a problem in spatial statistics, specifically how to mess with high-order statistics of point processes while controlling density. The algorithm is a variant of k-means and is extremely easy to implement in R.

library(imager)
library(dplyr)
library(purrr)

stipple <- function(im,nPoints=1e3,gamma=2,nSteps=10)
{
    dens <- (1-im)^gamma
    xy <- sample(nPix(im),nPoints,replace=TRUE,prob=dens) %>% coord.index(im,.) %>% select(x,y)
    for (ind in 1:nSteps)
    {
        xy <- cvt(xy,dens)
        plot(im); points(xy,col="red")
    }
    xy
}

plot.stipple <- function(im,out,cex=.25)
{
    g <- imgradient(im,"xy") %>% map(~ interp(.,out))
    plot(out,ylim=c(height(im),1),cex=cex,pch=19,axes=FALSE,xlab="",ylab="")
}

##Compute Voronoi diagram of point set xy,
##and return center of mass of each cell (with density given by image im)
cvt <- function(xy,im)
{
    voronoi(xy,width(im),height(im)) %>% as.data.frame %>%
        mutate(vim=c(im)) %>%
        group_by(value) %>%
        dplyr::summarise(x=weighted.mean(x,w=vim),y=weighted.mean(y,w=vim)) %>%
        select(x,y) %>%
        filter(x %inr% c(1,width(im)),y %inr% c(1,height(im)))
}

##Compute Voronoi diagram for points xy over image of size (w,h)
##Uses a distance transform followed by watershed 
voronoi <- function(xy,w,h)
{
    v <- imfill(w,h)
    ind <- round(xy) %>% index.coord(v,.)
    v[ind] <- seq_along(ind)
    d <- distance_transform(v>0,1)
    watershed(v,-d,fill_lines=FALSE)
}

#image from original paper
im <- load.image("http://dahtah.github.io/imager/images/stippling_leaves.png")
out <- stipple(im,1e4,nSteps=5,gamma=1.5)
plot.stipple(im,out)

TSP art is a variant where you solve a TSP problem to connect all the dots.

library(TSP)
##im is the original image (used only for its dimensions)
##out is the output of the stipple function (dot positions)
draw.tsp <- function(im,out)
{
    tour <- out %>% ETSP %>% solve_TSP
    plot(out[tour,],type="l",ylim=c(height(im),1),axes=FALSE,xlab="",ylab="")
}

##Be careful, this is memory-heavy (also, slow)
out <- stipple(im,4e3,gamma=1.5)
draw.tsp(im,out)

I’ve written a more detailed explanation on the imager website, with other variants like stippling with line segments, and a mosaic filter.