polygen

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):

This one is 100 polygons:

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

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.

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.

Documentation

Index

• Constants
• Variables
• func Asset(name string) ([]byte, error)
• func AssetDir(name string) ([]string, error)
• func AssetInfo(name string) (os.FileInfo, error)
• func AssetNames() []string
• func Compare(img1, img2 image.Image) (int64, error)
• func ConvertToRGBA(img image.Image) (result *image.RGBA)
• func DeriveCheckpointFile(sourceFile, cpArg string, polyCount int) string
• func FastCompare(img1, img2 *image.RGBA) (uint64, error)
• func MustAsset(name string) []byte
• func MustReadImage(file string) image.Image
• func RandomBool() bool
• func RandomInt(min, max int) int
• func RestoreAsset(dir, name string) error
• func RestoreAssets(dir, name string) error
• func Serve(hostPort string, refImg image.Image, previews []*SafeImage)
• func SplitPath(path string) []string
• type ByFitness
  • func (cds ByFitness) Len() int
  • func (cds ByFitness) Less(i, j int) bool
  • func (cds ByFitness) Swap(i, j int)
• type Candidate
• type Checkpoint
• type Evolver
  • func NewEvolver(refImg image.Image, dstImageFile string, checkPointFile string) (*Evolver, error)
  • func (e *Evolver) Run(maxGen, polyCount int, previews []*SafeImage)
• type Page
• type Point
• type Polygon
• type SafeImage
  • func NewSafeImage(img image.Image) *SafeImage
  • func (s *SafeImage) Update(img image.Image)
  • func (s *SafeImage) Value() image.Image
• type Stats
  • func NewStats() *Stats
  • func (s *Stats) Increment(count int)
  • func (s *Stats) Print(best, worst *Candidate, generation, generationsSinceChange int)

Constants

const (
	MutationAlpha            = iota
	MutationColor            = iota
	MutationPoint            = iota
	MutationZOrder           = iota
	MutationAddOrDeletePoint = iota
)

const (
	PopulationCount          = 10
	MaxPolygonPoints         = 6
	MinPolygonPoints         = 3
	PointMutationMaxDistance = 5
	MutationsPerIteration    = 1 // originally had 3, but 1 seems to work best here
)

Variables

var (
	Mutations = []int{MutationColor, MutationPoint, MutationAlpha, MutationZOrder, MutationAddOrDeletePoint}
)

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)