Difference between revisions of "TSP art"

From Evil Mad Scientist Wiki
Jump to: navigation, search
(Steer readers to the StippleGen docs; refer to old doc chain for those wishing to understand more of the mechanics or interested in an alternate tool chain)
(Added references)
Line 12: Line 12:
 
Sounds like we want a means of reproducing an image by drawing continuous paths, and preferrably as few distinct paths as possible....
 
Sounds like we want a means of reproducing an image by drawing continuous paths, and preferrably as few distinct paths as possible....
  
Welcome to "TSP art" in which an image's tonal quality is reproduced with a '''single''', continuous path.  This single path meanders over the entire canvas.  Like stippling, segments of this path appear more frequently in regions of the canvas which correspond to darker regions in the original image.  And, fewer segments of the path in lighter regions.  But how and where do we choose to draw this path?  By treating this question as a [http://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling Salesman Problem (TSP)], a suitable path may be determined.  To do so, we first produce a stippled representation of the image.  We then  ask, "What is the shortest possible path that visits each and every stipple exactly once and then returns to the starting point?"  That is precisely the Travelling Salesman problem with cities in the salesperson's journey replaced by stipples on our canvas.  Determining an answer to the TSP is actually very hard (NP-hard).  But, even fast approximate answers work well for TSP art.  See the image at the top of this page for an example.
+
Welcome to "TSP art" in which an image's tonal quality is reproduced with a '''single''', continuous path.  This single path meanders over the entire canvas.  Like stippling, segments of this path appear more frequently in regions of the canvas which correspond to darker regions in the original image.  And, fewer segments of the path in lighter regions.  But how and where do we choose to draw this path?  By treating this question as a [http://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling Salesman Problem (TSP)], a suitable path may be determined.  To do so, we first produce a stippled representation of the image.  We then  ask, "What is the shortest possible path that visits each and every stipple exactly once and then returns to the starting point?"  That is precisely the Travelling Salesman problem with cities in the salesperson's journey replaced by stipples on our canvas.  Determining an answer to the TSP is actually very hard (NP-hard).  But, even fast approximate answers work well for TSP art.  See the image at the top of this page for an example.  This form of artwork was first developed by [http://www.oberlin.edu/math/faculty/bosch/tspart-page.html Robert Bosch], who is also responsible for applying it to the results of stippled images [5,6].
  
 
* [[StippleGen|Using StippleGen to Generate TSP art]]
 
* [[StippleGen|Using StippleGen to Generate TSP art]]
Line 32: Line 32:
 
[3] A brief introduction to stippling can be found in the Wikipedia article [http://en.wikipedia.org/wiki/Stipple Stipple].<br/>
 
[3] A brief introduction to stippling can be found in the Wikipedia article [http://en.wikipedia.org/wiki/Stipple Stipple].<br/>
 
[4] To prevent mushrooming of your pen tips, select a reasonable value for your Eggbot's "pen lowering speed" in the "Timing" tab of the "Eggbot Control" extension.<br/>
 
[4] To prevent mushrooming of your pen tips, select a reasonable value for your Eggbot's "pen lowering speed" in the "Timing" tab of the "Eggbot Control" extension.<br/>
 +
[5] "Continuous Line Drawings via the Traveling Salesman Problem" (Robert Bosch and Adrianne Herman), ''Operations Research Letters'' '''32''' (2004) 302-303.<br/>
 +
[6] "TSP Art" (Robert Bosch and Craig S. Kaplan), ''Proceedings of Bridges 2005'' (2005) 303-310.<br/>
 +
 +
 
[#] Starry Night by Vincent van Gogh.  Digital copy of Starry Night converted to a CMYK color space and then each color layer separated.  Each individual layer was stippled with Gimp as per [[Producing a stippled image with Gimp]] and then TSP solutions for each stippled layer produced following the directions from [[Generating TSP art from a stippled image]].  The four resulting SVG files were then combined to make the resulting (scaled down) image shown above.  A larger copy may be seen at http://www.flickr.com/photos/46175218@N02/5348523884/in/photostream/.
 
[#] Starry Night by Vincent van Gogh.  Digital copy of Starry Night converted to a CMYK color space and then each color layer separated.  Each individual layer was stippled with Gimp as per [[Producing a stippled image with Gimp]] and then TSP solutions for each stippled layer produced following the directions from [[Generating TSP art from a stippled image]].  The four resulting SVG files were then combined to make the resulting (scaled down) image shown above.  A larger copy may be seen at http://www.flickr.com/photos/46175218@N02/5348523884/in/photostream/.

Revision as of 18:37, 2 October 2012

eggbottiny.jpg This wiki page is part of the documentation for the Egg-Bot kit.
Click here to return to the Egg-Bot overview.


mona-lisa-tsp.png

Monochrome likenesses of images can be made by processes of dithering, halftoning, or stippling as well as other techniques. The images below depict an original color image followed from left to right by a dithered image, a halftone screened image, and a stippled image [1, 2, 3].

mona-quartet.jpg

However, to produce an image on the Eggbot, we want a process that not only generates a pleasing likeness of the image, but also recognizes the Eggbot's mechanical nature. Pen plotters such as the Eggbot excel at drawing long, continuous paths but are mediocre at drawing thousands of small, shaded fills (dithers, halftone screens). Pen plotters are somewhat better suited to drawing thousands of small circles and points (stipples). With stippling, an image's grayscale tonal quality is reproduced by drawing more stipples in darker regions of the image and fewer where the image is lighter. That is, the density of stipples in a given region of the canvas increases with increasing darkness in the same region of the original image. Unfortunately, even stippling can be challenging as the many pen up and down operations are slow relative to drawing connected segments of lines. Moreover, if care is not taken, the tip of the drawing pen can mushroom out after many pen down operations [4].

Sounds like we want a means of reproducing an image by drawing continuous paths, and preferrably as few distinct paths as possible....

Welcome to "TSP art" in which an image's tonal quality is reproduced with a single, continuous path. This single path meanders over the entire canvas. Like stippling, segments of this path appear more frequently in regions of the canvas which correspond to darker regions in the original image. And, fewer segments of the path in lighter regions. But how and where do we choose to draw this path? By treating this question as a Travelling Salesman Problem (TSP), a suitable path may be determined. To do so, we first produce a stippled representation of the image. We then ask, "What is the shortest possible path that visits each and every stipple exactly once and then returns to the starting point?" That is precisely the Travelling Salesman problem with cities in the salesperson's journey replaced by stipples on our canvas. Determining an answer to the TSP is actually very hard (NP-hard). But, even fast approximate answers work well for TSP art. See the image at the top of this page for an example. This form of artwork was first developed by Robert Bosch, who is also responsible for applying it to the results of stippled images [5,6].

For those wishing to understand more about the mechanics of generating TSP art using an older, alternate tool chain, review these pages:

starrynight.jpg

Notes

[*] Mona Lisa by Leonardo da Vinci. TSP art of Mona Lisa produced with linkern, a part of the Concorde TSP package. Dithered and halftone screened images produced with Gimp. Stippled image produced with Adrian Secord's weighted Voronoi stippler.
[1] See the "Digital photography and image processing" section of the Wikipedia article Dither.
[2] For an explanation of halftoning, please see the Wikipedia article Halftone. Often, digital halftoning is an application of an ordered error diffusion dither.
[3] A brief introduction to stippling can be found in the Wikipedia article Stipple.
[4] To prevent mushrooming of your pen tips, select a reasonable value for your Eggbot's "pen lowering speed" in the "Timing" tab of the "Eggbot Control" extension.
[5] "Continuous Line Drawings via the Traveling Salesman Problem" (Robert Bosch and Adrianne Herman), Operations Research Letters 32 (2004) 302-303.
[6] "TSP Art" (Robert Bosch and Craig S. Kaplan), Proceedings of Bridges 2005 (2005) 303-310.


[#] Starry Night by Vincent van Gogh. Digital copy of Starry Night converted to a CMYK color space and then each color layer separated. Each individual layer was stippled with Gimp as per Producing a stippled image with Gimp and then TSP solutions for each stippled layer produced following the directions from Generating TSP art from a stippled image. The four resulting SVG files were then combined to make the resulting (scaled down) image shown above. A larger copy may be seen at http://www.flickr.com/photos/46175218@N02/5348523884/in/photostream/.