Traveling salesman portrait in Python

Last week, Antonio S. Chinchón made an interesting post showing how to create a traveling salesman portrait in R. Essentially, the idea is to sample a bunch of dark pixels in an image, solve the well-known traveling salesman problem for those pixels, then draw the optimized route between the pixels to create a unique portrait from the image. Antonio is a fan of Frankenstein, so he created a traveling salesman portrait from an old Frankenstein image.

I liked the idea of the traveling salesman portrait, so I thought it would be a fun exercise to re-create it in Python. Below, I walk through the code line-by-line. If you want the full code snippet, you can find it on my personal projects GitHub repository.

To start, we need an image of someone. For ease of comparison, I decided to use the same image as Antonio. Franky is looking handsome as ever.

Note: We can use any image we want, but this algorithm works best for images with light backgrounds.

Next, we need to convert that image to black and white. PIL makes this operation pretty straightforward.

Now we can use NumPy to identify the black pixels and select a random subset of them:

Now all that’s left to do is solve TSP for those 10,000 pixels. To do that, we first have to define the distance between every pixel. In this case, we’re going to define distance between two pixels as the Euclidean distance between their x,y coordinates in the image. With that definition in mind, we can calculate the distances between all 10,000 pixels:

Great! The result is a giant 10,000 x 10,000 matrix with the Euclidean distances between every pixel. Now we can provide that matrix to an off-the-shelf traveling salesman problem solver:

And voilà! We now have a traveling salesman portrait of the ever-handsome Frankenstein.

Finally, a side-by-side comparison:

If you want to make your own traveling salesman portrait, you can use my Python script on GitHub. Enjoy!

Dr. Randy Olson is the Lead Data Scientist at Life Epigenetics, Inc., where he is bringing advanced data science and machine learning technology to the life insurance industry.