Genetic Algorithms to find images made of triangles.

.jshintrc

{
    "undef": true,
    "strict": false,
    "browser": true,
    "loopfunc": true,
    "asi": false,
    "eqeqeq": true,
    "evil": false,
    "shadow": false,
    "unused": true,
    "quotmark": false,

    "globals": {
        "_": false,
        "asyncTest": false,
        "BrowserDetect": true,
        "console": false,
        "deepEqual": false,
        "equals": false,
        "$": false,
        "k": false,
        "module": false,
        "ok": false,
        "process": false,
        "setImmediate": false,
        "setInterval": false,
        "ShowFor": false,
        "start": false,
        "test": false,
        "tests": false,
        "window": false
    }
}

app.js

/* global Stats:true */
(function() {
'use strict';

var url = 'mona.jpg';
// var url = 'fx.jpg';
// var url = 'colors.jpg';

// size of canvases
var WIDTH = 128;
var HEIGHT = 160;
// number of canvases
var NUM_INDIVS = 82;
// number of shapes
var NUM_TRIANGLES = 50;
// GA stuff
var keepBest = 1;
var mutBest = 1;
var mutRand = 3;
var newcomerChance = 0.3;
var mutAmt = 0.1;
var mutChance = 0.05;
var mutateKids = true;

var worstScore = hypot(255, 255, 255, 255) * WIDTH * HEIGHT;

var target;
var progress;
var population;
var canvases;
var pre = document.getElementById('status');
var img;
var stats = new Stats();
stats.setMode(1);
stats.domElement.style.position = 'absolute';
stats.domElement.style.right = '0px';
stats.domElement.style.bottom = '0px';
document.body.appendChild( stats.domElement );

function hypot() {
  var n = arguments.length;
  var sum = 0;
  for (var i=0; i<n; i++) {
    sum += Math.pow(arguments[i], 2);
  }
  return Math.sqrt(sum);
}

function rand(n, o) {
  return (Math.random() * n | 0) + (o || 0);
}


function Canvas(w, h) {
    this.el = document.createElement('canvas');
    this.el.width = w;
    this.el.height = h;
}
Canvas.prototype = {
    clear: function() {
        this.ctx.clearRect(0, 0, this.width, this.height);
    },
    diff: function(other) {
      if (this.width !== other.width || this.height !== other.height) {
        throw new Error("Can't diff canvases of different sizes.");
      }

      var i, rd, gd, bd, ad;
      var sum = 0;
      var step = 1;

      var thisImg = this.imgData.data;
      var otherImg = other.imgData.data;

      for (var y = 0; y < this.width; y+=step) {
        for (var x = 0; x < this.height; x+=step) {
          i = (y * WIDTH + x) * 4;
          rd = thisImg[i] - otherImg[i];
          gd = thisImg[i+1] - otherImg[i+1];
          bd = thisImg[i+2] - otherImg[i+2];
          ad = thisImg[i+3] - otherImg[i+3];
          sum += hypot(rd, gd, bd, ad);
        }
      }

      return sum;
    },

    get width () {
      return this.el.width;
    },
    set width (w) {
      this.el.width = w;
    },

    get height () {
      return this.el.height;
    },
    set height (h) {
      this.el.height = h;
    },

    get ctx () {
        if (this._ctx === undefined) {
          this._ctx = this.el.getContext('2d');
        }
        this._imgData = undefined;
        return this._ctx;
    },

    get imgData() {
      if (this._imgData === undefined) {
        this._imgData = this.ctx.getImageData(0, 0, this.width, this.height);
      }
      return this._imgData;
    },
    set imgData(id) {
      this.ctx.putImageData(id, 0, 0);
      this._imgData = id;
    }
};


function Individual(canvas, dna) {
  this.canvas = canvas;
  this._fitness = null;
  var i;

  this.one_traits = ['h', 's', 'l'];
  this.tri_traits = [
    'sort',
    'h', 's', 'l', 'a',
    'x1', 'y1','x2', 'y2', 'x3', 'y3',
  ];

  var gene = Math.random;
  if (dna === 0) {
    dna = undefined;
    gene = function() { return 0.5; };
  }

  if (dna) {
    this.dna = dna;
  } else {
    this.dna = [];
    for (i = 0; i < this.one_traits.length; i++) {
      this.dna.push(gene());
    }
    for (i = 0; i < this.tri_traits.length * NUM_TRIANGLES; i++) {
      this.dna.push(gene());
    }
  }

  this.triangles = (this.dna.length - this.one_traits.length) / this.tri_traits.length;
}
Individual.prototype = {
  trait: function(name, scale, index) {
    var i, base;
    if (index === undefined) {
      i = this.one_traits.indexOf(name);
    } else {
      i = this.tri_traits.indexOf(name);
      base = this.one_traits.length + this.tri_traits.length * index;
    }
    if (i === -1) {
      return undefined;
    }
    return this.dna[base + i] * scale;
  },

  triangle: function(index) {
    var obj = {};
    var base = index * this.tri_traits.length + this.one_traits.length;
    for (var i = 0; i < this.tri_traits.length; i++) {
      obj[this.tri_traits[i]] = this.dna[base + i];
    }
    return obj;
  },

  draw: function() {
    this.canvas.clear();
    var width = WIDTH * 1.2;
    var left = WIDTH * 0.1;
    var height = HEIGHT * 1.2;
    var top = HEIGHT * 0.1;
    var h, s, l, a, x1, y1, x2, y2, x3, y3;

    var ctx = this.canvas.ctx;

    h = this.trait('h', 360);
    s = this.trait('s', 100);
    l = this.trait('l', 100);

    ctx.strokeStyle = null;
    ctx.fillStyle = 'hsl(' + h + ',' + s + '%,' + l + '%)';
    ctx.fillRect(0, 0, WIDTH, HEIGHT);

    var tris = [];
    for (var i = 0; i < NUM_TRIANGLES; i++) {
      tris.push(this.triangle(i));
    }
    tris.sort(function(a, b) {
      if (a.sort > b.sort) {
        return 1;
      } else if (a.sort < b.sort) {
        return -1;
      } else {
        return 0;
      }
    });

    var t;
    for (i = 0; i < tris.length; i++) {
      t = tris[i];
      h  = t.h * 360 | 0;
      s  = t.s * 100 | 0;
      l  = t.l * 100 | 0;
      a  = t.a * 1;
      x1 = t.x1 * width - left | 0;
      y1 = t.y1 * height - top | 0;
      x2 = t.x2 * width - left | 0;
      y2 = t.y2 * height - top | 0;
      x3 = t.x3 * width - left | 0;
      y3 = t.y3 * height - top | 0;

      ctx.fillStyle = 'hsla(' + h + ',' + s + '%,' + l + '%,' + a + ')';
      ctx.beginPath();
      ctx.moveTo(x1, y1);
      ctx.lineTo(x2, y2);
      ctx.lineTo(x3, y3);
      ctx.lineTo(x1, y1);
      ctx.fill();
    }
  },

  clone: function() {
    return new Individual(this.canvas, this.dna.slice());
  },

  breed: function(other, canvas) {
    var newDNA = [];
    var r = Math.random();
    for (var i = 0; i < this.dna.length; i++) {
      if (Math.random() < 0.1) {
        r = Math.random();
      }
      newDNA.push(r > 0.5 ? this.dna[i] : other.dna[i]);
    }
    // var split = rand(this.dna.length);
    // var newDNA = this.dna.slice(0, split).concat(other.dna.slice(split));
    return new Individual(canvas || this.canvas, newDNA);
  },

  mutate: function() {
    var r;
    for (var i = 0; i < this.dna.length; i++) {
      if (Math.random() < mutChance) {
        r = (Math.random() - 0.5) * mutAmt;
        this.dna[i] = (this.dna[i] + r) % 1;
      }
    }
  },

  get fitness () {
    if (this._fitness === null) {
      this._fitness = this.canvas.diff(target);
    }
    return this._fitness|0;
  },
};


function pickByFitness(population) {
  var total = 0;
  population.forEach(function(indiv) {
    total += worstScore - indiv.fitness;
  });
  var choice = rand(total);
  for (var i = 0; i < population.length; i++) {
    choice -= (worstScore - population[i].fitness);
    if (choice <= 0) {
      return population[i];
    }
  }
  console.log('fallback', choice, total);
  return population[i - 1];
}


function drawDiffCanvas(best) {
  var id1 = target.imgData;
  var id2 = best.imgData;
  var d;

  var scale = hypot(256, 256, 256, 256) * 2;
  for (var i = 0; i < id1.data.length; i+=4) {
    d = hypot(id1.data[i + 0] - id2.data[i + 0],
              id1.data[i + 1] - id2.data[i + 1],
              id1.data[i + 2] - id2.data[i + 2],
              id1.data[i + 3] - id2.data[i + 3]) / scale;
    id2.data[i + 0] = Math.abs(id1.data[i + 0] - id2.data[i + 0]) + d | 0;
    id2.data[i + 1] = Math.abs(id1.data[i + 1] - id2.data[i + 1]) + d | 0;
    id2.data[i + 2] = Math.abs(id1.data[i + 2] - id2.data[i + 2]) + d | 0;
    id2.data[i + 3] = 255;
  }
  progress.imgData = id2;
}


function init() {
  var canvas;

  target = new Canvas(WIDTH, HEIGHT);
  progress = new Canvas(WIDTH, HEIGHT);
  document.body.appendChild(target.el);
  document.body.appendChild(progress.el);

  population = [];
  canvases = [];
  for (var i = 0; i < NUM_INDIVS; i++) {
    canvas = new Canvas(WIDTH, HEIGHT);
    population.push(new Individual(canvas));
    canvases.push(canvas);
    document.body.appendChild(canvas.el);
  }

  target.ctx.drawImage(img, 0, 0, img.width, img.height, 0, 0, WIDTH, HEIGHT);

  generation();
}

img = new Image();
img.onload = init;
img.src = url;

var gen = 0;
function generation() {
  stats.begin();
  var i;
  for (i = 0; i < population.length; i++) {
    population[i].draw();
  }

  population.sort(function(a, b) {
    if (a.fitness > b.fitness) {
      return +1;
    } else if (a.fitness < b.fitness) {
      return -1;
    } else {
      return 0;
    }
  });

  pre.innerHTML = 'generation: ' + gen + '\n' +
                  'best score: ' + population[0].fitness + '\n' +
                  'error: ' + Math.floor(population[0].fitness / worstScore * 100) + '%';

  drawDiffCanvas(population[0].canvas);

  var daddy, mommy, kid;
  // Keep `keepBest` of the top population.
  var newPopulation = population.slice(0, keepBest);

  // Add copies of the top `mutBest`, mutated.
  for (i = 0; i < mutBest; i++) {
    kid = population[i].clone();
    kid.mutate();
    newPopulation.push(kid);
  }

  // Add copies of `mutRand` from the population, mutated.
  for (i = 0; i < mutRand; i++) {
    kid = population[rand(population.length)].clone();
    kid.mutate();
    newPopulation.push(kid);
  }

  // Add a random new comers.
  if (Math.random() < newcomerChance) {
    newPopulation.push(new Individual(canvases[0]));
  }

  // Fill in the rest of the generation by breeding.
  while (newPopulation.length < population.length) {
    daddy = pickByFitness(population);
    mommy = pickByFitness(population);
    kid = daddy.breed(mommy);
    if (mutateKids) kid.mutate();
    newPopulation.push(kid);
  }

  for (i = 0; i < newPopulation.length; i++) {
    newPopulation[i].canvas = canvases[i];
  }

  population = newPopulation;

  gen++;
  setTimeout(generation, 0);
  stats.end();
}

})();

colors.jpg

fx.jpg

genes.html

mona.jpg