How can I trace a path around an image consisting of only black and white lines?

Question

I'm looking for a way to trace a closed curve (i.e. a long list of pixel values all connected by lines in between) that approximates a bitmap image of black and white lines.

The image starts out as an arbitrary bitmap image. I've been using this one for testing.

Then it's converted to greyscale, passed through an edge detection filter, and finally converted to a true monochrome black/white bitmap. The end result of this preprocessing looks like this.

My goal is to trace a closed curve around the white pixels.

My naive approach was to make a list of all the white pixels in the image, then use a greedy travelling-salesman solver to draw a path around them. Which results in a path looking like this.

This works, there's a lot of artifacts but it works. But it's very slow. This relatively simple image takes a couple minutes to process. Any images more complex than this one need to be reduced in quality by a substantial amount before the time taken is reasonable. The resulting path is then almost unrecognizable.

When looking up algorithms for tracing images, I find a lot of things either built into image editing software (I need an algorithm that I can implement in Python), or overkill bitmap-to-vector algorithms designed to preserve color and line thickness.

All I need is a list of pixel values that trace out the lines.

There's got to be a better way than straight up solving travelling-salesman, right?

Answer 1

Depending on the accuracy of the trace you wish to achieve, there are a couple of ways you can do this:

The most straightforward way is to:

1. Convert the image to grayscale
2. Threshold, to achieve a completely binary image
3. Apply a high pass mask to get rid of the constant areas
   • For example $\begin{matrix} 1 & 1 & 1 \\ 1 & -9 & 1 \\ 1 & 1 & 1 \end{matrix}$

The result looks like this:

This technique is not without limitations, because as you can see, Pink Panther's whiskers have been drawn boldly and therefore have been "traced" and the highlight in his left eye has been interpreted as "background", producing an inner trace. To reduce these artifacts you can use a "wider" filter (for example, a $5 \times 5$ square of $1$s with a $-25$ in the middle. This produces a stronger wider trace line), morphological operations or adaptive application of the mask depending on features of the patch you are looking at.

The "path based" tracer you seem to suggest is how active contours work. In this case, you would initialise the active contour on the image rectangle and then iterate it towards the outer edges of the cartoon. Scikit-image has an implementation of active contours.

But based on the work you have done already, you could switch from a "Traveling salesman" route discovery to a convex hull of the points you collect.

The convex hull will trace an outline that encloses the set of points and give it a "cartoonistic" sketch view as well. Again, scipy has a convex hull implementation and so does Octave, from which I am posting this indicative output.

You will need to have the image package loaded for the following code to work and I am re-using the last image of the traced Pink Panther from above to extract the points, but that is just because I had it already, you can simply feed the convex hull the points you have extracted right after thresholding. It might be a lot of data indeed but convex hull is not solving a TSP and returns much quicker.

I = imread("thetracedimage.png");  % Load the image
Z = find(I);  % Find the outline (anything that is nonzero)
[Qy, Qx] = ind2sub(size(I),Z);  % Convert the index values returned by find, to image coordinates (in Qx, Qy) NOTICE ORDER OF X,Y!
H = convhull(Qx, -Qy);  % Obtain the convex hull
% H is the index of the existing points that make up the convex hull and we are assuming that these are connected by lines. To retrieve the actual points:
Fx=Qx(H);
Fy=Qy(H);
% Now plot everything. Notice the reversal of y purely because of the plotting coordinate system that puts 0,0 at the bottom left corner.
plot(Qx, -Qy,'.',Fx,-Fy);axis image;

And this results to:

Which of course is less accurate, but it depends on what you are trying to do and you seem to indicate that the approximate output of the TSP is sort of satisfactory (?).

Hope this helps.