You may also consult the Project Page and the Interactive Session Tutorial.
What is TSP_PictureMaker?
TSP_PictureMaker
is a module library for converting a picture to a a depiction created by an approximate solution
to the Travelling Salesman Problem (TSP). As an example, the code in example.py
takes the following picture of a tiger's head:
and converts it to the following picture
The process to make the final picture are as follows:
- The vertices for the TSP are created by dithering the input image and using the result black pixels as vertices.
- An intial greedy guess for the solution to the TSP is made.
- The greedy guess is improved by applying a modification of simulated annealing that is based on a decaying size scale.
- Further improvements are made by applying another modification of simulated annealing based on nearest neighbors.
Example Code
example.py
An example of using the functions to convert tigerHeadResize.png into a TSP picture.
Package Description
The name of the package is tsp_draw
. It contains the following modules:
dithering
Class and functions for applying dithering to an image.
graphics
Functions for plotting results, saving images, and preprocessing of input images.
jobs
Functions for dealing with running batches of the annealing steps for different types of annealers.
neighbors
Contains annealer that uses k-nearest neighbors as vertex pool.
processVertices
Functions for getting the vertices from the dithered image and for preprocessing them, including the initial greedy guess.
sizeScale
Contains annealer that uses a vertex pool based on a lower bound of the distance to the either of the vertex's initial neighbors in the initial cycle.
Description of Library's Process
For a discussion of how the process works, please see this blog post by Matthew McGonagle.