Evolving Line Art

In this article, I want to talk about a really simple technique for evolving line-art from pictures. On top of being an simple example for genetic algorithms, it is also a fun programming project that can be done in short time.

For this project, we are going to use the Hill Climbing algorithm. The algorithm for evolving pictures is like the following.

1. Create two empty images, image 1 and image 2
2. Do a small random modification (like a line) to the first image
3. If the first image is closer to the target than the first one, copy it to image 2
4. Otherwise, copy the second image to image 1
5. Goto 2

I will be using Rust for this project. Fortunately, Rust has really good libraries that we can use to read, manipulate and write image files.

Loading the Target Image

The image crate makes loading files really straightforward. Here’s how to load the file called target.png. We will also create the two temporary images that we need for the algorithm. We will make those

let target = image::open("target.png").expect("Cannot load target image");

let mut img1 = DynamicImage::new_rgb8(target.width(), target.height());
let mut img2 = DynamicImage::new_rgb8(target.width(), target.height());

Extracting the Colours

Normally, picking the colours randomly should work just as well as using the colours from the picture. But if we extract all the colours and pick randomly from those, the algorithm will be able to generate the images faster. To achieve this, we will create a Vector and store all the colours in there.

let mut colours = Vec::new();

for pixel in target.pixels() {
    let rgba = pixel.2.to_rgba();

    if !colours.contains(&rgba) {
        colours.push(rgba);
    }
}

Difference between two images

To determine if an image is closer to our target, we need a function to find the difference of two images. The root_mean_squared_error from the imageproc crate does exactly that.

fn image_diff(img1: &DynamicImage, img2: &DynamicImage) -> f64 {
    imageproc::stats::root_mean_squared_error(img1, img2)
}

This function returns the amount of difference between two images as a float. When we’re building the hill climbing algorithm, our goal is going to be minimising this number.

Drawing random circles

Personally I like the art style of the random lines, but it evolves slowly. One way to speed-up the process and get a different art style is using different shapes. Perhaps the simplest shape that can be drawn is a circle. It only needs a location (x, y) and a radius. Here’s how to draw a random circle with a radius of 5 in your image.

let pos: (i32, i32) = (rng.gen_range(0, target.width() as i32), rng.gen_range(0, target.height() as i32));
let colour = rng.choose(&colours).unwrap();

imageproc::drawing::draw_filled_circle_mut(&mut img1, pos, 5, *colour);

Drawing random lines

For drawing, we are going to be using the imageproc crate again. Here’s how to draw a black line from (10, 10) to (20, 20).

let start = (10f32, 10f32);
let end = (20f32, 20f32);
let color = Rgba([0, 0, 0, 1]);

imageproc::drawing::draw_line_segment_mut(&mut img1, start, end, colour);

Let’s draw a line with a color chosen from our random list.

let mut rng = rand::thread_rng();

let start: (f32, f32) = (rng.gen_range(0.0, target.width() as f32), rng.gen_range(0.0, target.height() as f32));
let end:   (f32, f32) = (rng.gen_range(0.0, target.width() as f32), rng.gen_range(0.0, target.height() as f32));
let colour = rng.choose(&colours).unwrap();

imageproc::drawing::draw_line_segment_mut(&mut img1, start, end, *colour);

The Hill Climbing Algorithm

If you don’t know how it works, I have written about the hill climbing algorithm in my wiki. Basically, it starts with a random solution and repeatedly mutates it in a way that it becomes better and better according an evaluation function we provide.

Let’s write the skeleton of our hill climber. We’ve already created the target image and the temporary images in the previous sections.

loop {
    let pos: (i32, i32) = (rng.gen_range(0, target.width() as i32), rng.gen_range(0, target.height() as i32));
    let colour = rng.choose(&colours).unwrap();

    imageproc::drawing::draw_filled_circle_mut(&mut img1, pos, 5, *colour);

    if image_diff(&target, &img1) < image_diff(&target, &img2) {
        &img2.copy_from(&img1, 0, 0);
    } else {
        &img1.copy_from(&img2, 0, 0);
    }
}

Saving regular snapshots

Since this program can improve the image for a really long time, until it becomes a pixel-perfect copy of the target, we might want to save snapshots if the image we get in regular intervals. This will allow us to check the progress and stop the program once we are satisfied with the results. Let’s save the image every 500 iterations.

if i % 500 == 0 {
    img2.save(&mut File::create(&Path::new("output.png")).unwrap(), image::PNG);
}

And with that, the project is done. Here’s the full code, in a form that compiles and runs. Play around with it, try new shapes and different algorithms. If you implement this in another language, let me know and share your own code with result pictures.

extern crate image;
extern crate imageproc;
extern crate rand;

use std::fs::File;
use std::path::Path;
use rand::Rng;

use image::{DynamicImage, GenericImage, Pixel};

fn image_diff(img1: &DynamicImage, img2: &DynamicImage) -> f64 {
    imageproc::stats::root_mean_squared_error(img1, img2)
}

fn main() {
    let target = image::open("target.png").expect("Cannot load target image");

    let mut img1 = DynamicImage::new_rgb8(target.width(), target.height());
    let mut img2 = DynamicImage::new_rgb8(target.width(), target.height());

    let mut colours = Vec::new();

    for pixel in target.pixels() {
        let rgba = pixel.2.to_rgba();

        if !colours.contains(&rgba) {
            colours.push(rgba);
        }
    }

    let mut rng = rand::thread_rng();

    let mut i = 0;
    loop {
        let pos:   (i32, i32) = (rng.gen_range(0, target.width() as i32), rng.gen_range(0, target.height() as i32));
        let colour = rng.choose(&colours).unwrap();

        imageproc::drawing::draw_filled_circle_mut(&mut img1, pos, 5, *colour);

        if image_diff(&target, &img1) < image_diff(&target, &img2) {
            &img2.copy_from(&img1, 0, 0);
        } else {
            &img1.copy_from(&img2, 0, 0);
        }

        if i % 100 == 0 {
            println!("{}", i);
            img2.save(&mut File::create(&Path::new("output.png")).unwrap(), image::PNG);
        }

        i += 1;
    }
}