README

Polygen uses a genetic algorithm to approximate an image with a small number of polygons.

You can generate a fairly good approximation with surprisingly few polygons. Here's a sample that has only 50 polygons (~380K generations):

starry-night starry-night 50 polygons

This one is 100 polygons:

mona-lisa mona-lisa 100 polygons

A more challenging image- 500 polygons & 680,850 generations:

revolver revolver 500 polygons

The algorithm is pretty simple:

  1. Create an initial string of candidate "DNA" consisting of a set of polygons (a color and a set of points) via random number generation.

  2. Render the DNA to an image (the "phenotype"). Compute its fitness by comparing to the reference image.

  3. Apply random mutations to the candidate (change color, move polygon points, juggle the z-order) to create a population of offspring.

  4. Evaluate the offspring, and if their fitness is better, replace the parent.

  5. Repeat for N generations.

Usage
  1. $ go get github.com/armhold/polygen/...
  2. $ cd $GOPATH/src/github.com/armhold/polygen
  3. polygen -source images/mona_lisa.jpg -poly 50
  4. Let it run until you are happy with the output (in output.png), or until you notice that there is not much change between generations.

Polygen includes a built-in web server, so you can watch the image evolve in more or less realtime. Just point your browser to http://localhost:8080.

logo

Credits

This code is my own, but credit goes to Roger Johansson for the original idea, which he documented here.

The file "mona_lisa.jpg" contains a low-resolution portion of the painting Mona Lisa, by Leonardo da Vinci. It is in the Public Domain.

The file "starry.jpg" contains a low-resolution copy of the painting The Stary Night by Vincent van Gogh. It is in the Public Domain.

The file "Revolver.jpg" contains a low-resolution copy of the cover art for the album Revolver by the artist The Beatles. The cover art copyright is believed to belong to the label, Parlophone/EMI, or the graphic artist(s), Klaus Voormann. It is included under Fair Use.

Expand ▾ Collapse ▴

Documentation

Index

Constants

View Source
const (
	MutationAlpha            = iota
	MutationColor            = iota
	MutationPoint            = iota
	MutationZOrder           = iota
	MutationAddOrDeletePoint = iota
)
View Source
const (
	PopulationCount          = 10
	MaxPolygonPoints         = 6
	MinPolygonPoints         = 3
	PointMutationMaxDistance = 5
	MutationsPerIteration    = 1 // originally had 3, but 1 seems to work best here
)

Variables

Functions

func Asset

func Asset(name string) ([]byte, error)

    Asset loads and returns the asset for the given name. It returns an error if the asset could not be found or could not be loaded.

    func AssetDir

    func AssetDir(name string) ([]string, error)

      AssetDir returns the file names below a certain directory embedded in the file by go-bindata. For example if you run go-bindata on data/... and data contains the following hierarchy:

      data/
        foo.txt
        img/
          a.png
          b.png
      

      then AssetDir("data") would return []string{"foo.txt", "img"} AssetDir("data/img") would return []string{"a.png", "b.png"} AssetDir("foo.txt") and AssetDir("notexist") would return an error AssetDir("") will return []string{"data"}.

      func AssetInfo

      func AssetInfo(name string) (os.FileInfo, error)

        AssetInfo loads and returns the asset info for the given name. It returns an error if the asset could not be found or could not be loaded.

        func AssetNames

        func AssetNames() []string

          AssetNames returns the names of the assets.

          func Compare

          func Compare(img1, img2 image.Image) (int64, error)

            Compare compares images by computing the square root of the total sum of individual squared pixel differences.

            func ConvertToRGBA

            func ConvertToRGBA(img image.Image) (result *image.RGBA)

              from http://blog.golang.org/go-imagedraw-package ("Converting an Image to RGBA"), modified slightly to be a no-op if the src image is already RGBA

              func DeriveCheckpointFile

              func DeriveCheckpointFile(sourceFile, cpArg string, polyCount int) string

                try to make it painless for users to automatically get a checkpoint file. We want the file to be tied both the source file name and the polygon count. If an explicit cpArg is given, we just use that.

                func FastCompare

                func FastCompare(img1, img2 *image.RGBA) (uint64, error)

                  FastCompare compares images by diffing the underlying byte arrays directly. This is more than 10x faster than Compare(), but requires a concrete instance of image.RGBA.

                  func MustAsset

                  func MustAsset(name string) []byte

                    MustAsset is like Asset but panics when Asset would return an error. It simplifies safe initialization of global variables.

                    func MustReadImage

                    func MustReadImage(file string) image.Image

                    func RandomBool

                    func RandomBool() bool

                      RandomBool uses the default random Source to return either true or false.

                      func RandomInt

                      func RandomInt(min, max int) int

                        RandomInt uses the default random Source to return a random integer that is >= min, but < max

                        func RestoreAsset

                        func RestoreAsset(dir, name string) error

                          RestoreAsset restores an asset under the given directory

                          func RestoreAssets

                          func RestoreAssets(dir, name string) error

                            RestoreAssets restores an asset under the given directory recursively

                            func Serve

                            func Serve(hostPort string, refImg image.Image, previews []*SafeImage)

                            func SplitPath

                            func SplitPath(path string) []string

                            Types

                            type ByFitness

                            type ByFitness []*Candidate

                              sorting

                              func (ByFitness) Len

                              func (cds ByFitness) Len() int

                              func (ByFitness) Less

                              func (cds ByFitness) Less(i, j int) bool

                              func (ByFitness) Swap

                              func (cds ByFitness) Swap(i, j int)

                              type Candidate

                              type Candidate struct {
                              	W, H     int
                              	Polygons []*Polygon
                              
                              	Fitness uint64
                              	// contains filtered or unexported fields
                              }

                                Candidate is a potential solution (set of polygons) to the problem of how to best represent the reference image.

                                type Checkpoint

                                type Checkpoint struct {
                                	Generation             int
                                	GenerationsSinceChange int
                                	MostFit                *Candidate
                                }

                                  Checkpoint is used for serializing the current best candidate and corresponding generation count to a checkpoint file.

                                  type Evolver

                                  type Evolver struct {
                                  	// contains filtered or unexported fields
                                  }

                                    Evolver uses a genetic algorithm to evolve a set of polygons to approximate an image.

                                    func NewEvolver

                                    func NewEvolver(refImg image.Image, dstImageFile string, checkPointFile string) (*Evolver, error)

                                    func (*Evolver) Run

                                    func (e *Evolver) Run(maxGen, polyCount int, previews []*SafeImage)

                                      Run runs the Evolver until maxGen generations have been evaluated. At each generation, the candidate images are rendered & evaluated, and the preview images are updated to reflect the current state.

                                      type Page

                                      type Page struct {
                                      }

                                      type Point

                                      type Point struct {
                                      	X, Y int
                                      }

                                        Point defines a vertex in a Polygon.

                                        type Polygon

                                        type Polygon struct {
                                        	Points []Point
                                        	color.Color
                                        }

                                          Polygon is a set of points with a given fill color.

                                          type SafeImage

                                          type SafeImage struct {
                                          	// contains filtered or unexported fields
                                          }

                                            SafeImage is an image protected by a RWMutex. All access should be via the Update() and Value() methods. This allows us to update the candidate images from a goroutine in the Evolver, and display them in the Server.

                                            func NewSafeImage

                                            func NewSafeImage(img image.Image) *SafeImage

                                            func (*SafeImage) Update

                                            func (s *SafeImage) Update(img image.Image)

                                            func (*SafeImage) Value

                                            func (s *SafeImage) Value() image.Image

                                            type Stats

                                            type Stats struct {
                                            	// contains filtered or unexported fields
                                            }

                                              Stats is used by the Evolver for printing runtime statistics.

                                              func NewStats

                                              func NewStats() *Stats

                                              func (*Stats) Increment

                                              func (s *Stats) Increment(count int)

                                                Increments the number of candidates that have been evaluated since last call to Print().

                                                func (*Stats) Print

                                                func (s *Stats) Print(best, worst *Candidate, generation, generationsSinceChange int)

                                                Directories

                                                Path Synopsis
                                                cmd