Unknown Name - 0

Introduction

This post describes a simple algorithm of vectorizing raster images. By vectorizing, I understand finding regions of various brightness or colours and returning polygon coordinates for these regions. The algorithm was created for my experimental photo to stencil converter, the stencil has to be laser-cut so one of the requirements for the algorithm was to find closed non-intersecting polygons rather than just lines.

The first step is to binarize the image, i.e., convert all color values into black or white. All pixels brighter than a threshold are converted to white, all other pixels become black. You can change this algorithm and binarize based on colors or whatever criteria you want. The only requirement is that in the end, you need an image with just 2 colors: black and white.

The next step is to find border between the black and white regions. All you have to do is compare each pixel with its left, bottom and left-bottom neighbours. If neighbour color is different, then we are on the border. By highlighting all borders, we get something like this:

It almost looks OK but it is not a vector yet. The next step is to trace lines point by point. For each point, we find the next neighbour, then for that neighbour, we find the next neighbour and so on. The problem is that each point may have more than 2 neighbours and we need to decide which one to select as our preferred direction. We do it by testing all points around the current one in counter-clockwise direction, like so:

As a result, we resolve ambiguity and get nice and smooth non-intersecting lines:

You may want to perform final cleanup on the collection of lines you get. We filter by length removing too short lines; we remove non-closed lines; we apply union operation to polygons because stencil must be a simple-connected region. The type of cleanup you perform depends on your application, so I'm leaving it up to you.

A simple WinForms app in the attachment allows you to select an image, adjust the binary threshold level and generate .SVG file.