ニテンイチリュウ : Image Evolution 経由で知った Image Evolution を試してみた。50個の半透明なポリゴンを塗り重ねてモナリザに近づけてみよう、という試みだ。

仕組みは単純。ランダムに配置したポリゴンをランダムに変形させたり色を変えたりしてみて、モナリザの画像の色に近づけば採用、そうでなければ止める。これだけ。微分してとか、輪郭抽出してとか、そういう賢いことは何もやらない。単に力任せにシミュレーションし続けている。

手元の環境で動かしたらこんな感じになった。

壮大なる CPU の無駄使い。だが面白い。

いちおう Flash も貼っておく。が、猛烈にブラクラなので扱いは慎重に。

高速化のために、BitmapData.compare() といったビルトインのメソッドを使っているので、Firefox 3 で canvas 版 よりも10倍ぐらい速く動いた。オリジナルの C# 版 は、さらに3倍ぐらい速い。しかもポリゴン数や節点数もランダムに動かしてるので、より精度が高いような気がする。

ソースコードは以下に(189行)。

package{
import flash.display.*;
import flash.text.*;
import flash.geom.*;
import flash.filters.ColorMatrixFilter;
import flash.utils.setInterval;

[SWF(backgroundColor="#eeeeee")]
public class Evolve extends Sprite{
    [Embed(source='mona_lisa_crop.jpg')]
    private var MonaLisa:Class;
    private var imgWidth:int;
    private var imgHeight:int;

    private const POLYGONS:int = 50;
    private var polygons:Array = [];
    private var mutating:Boolean = false;

    private var monotoneFilter:ColorMatrixFilter = new ColorMatrixFilter([
            1 / 3, 1 / 3, 1 / 3, 0, 0, 
            1 / 3, 1 / 3, 1 / 3, 0, 0, 
            1 / 3, 1 / 3, 1 / 3, 0, 0, 
                0,     0,     0, 1, 0 ]);
    private var pt0:Point = new Point(0, 0);
    private var rect:Rectangle;

    private var bestBmd:BitmapData;
    private var testBmd:BitmapData;
    private var inputBmd:BitmapData;
    private var debugBmd:BitmapData;

    private var canvas:Sprite;

    private var score:uint;
    private var scoreMax:uint;
    private var mutations:uint = 0;
    private var candidates:uint = 0;
    private var totalTime:Number = 0;
    private var time:Date;
    private var scoreText:TextField;

    public function Evolve(){
        stage.scaleMode = "noScale";
        stage.align = "TL";

        // init image
        var bmp:Bitmap = new MonaLisa();
        inputBmd = bmp.bitmapData;
        addChild(bmp);
        imgWidth = bmp.width;
        imgHeight = bmp.height;
        rect = inputBmd.rect;
        score = scoreMax = rect.width * rect.height * 255;

        // init buffer
        bestBmd = inputBmd.clone(); bestBmd.fillRect(rect, 0x000000);
        testBmd = inputBmd.clone(); testBmd.fillRect(rect, 0x000000);
        debugBmd = inputBmd.clone();
        addChild(new Bitmap(bestBmd)).x = bmp.width + 10;

        // init data and canvas
        canvas = new Sprite();
        for(var i:int = 0; i < POLYGONS; i++){
            polygons[i] = new Polygon();
            canvas.addChild(new Sprite());
        }
        drawTest();
        testToBest();

        // init ui
        var tf:TextField = new TextField();
        tf.text = "click to start";
        tf.y = bmp.height + 10;
        tf.scaleX = tf.scaleY = 3;
        addChild(tf);
        stage.addEventListener("click", function(event:*):void{
            mutating = !mutating;
            time = (mutating ? new Date() : null);
            tf.text = (mutating ? "Now Simulating..." : "click to start");
        });
        scoreText = new TextField();
        scoreText.autoSize = "left";
        scoreText.y = bmp.height + 60;
        scoreText.scaleX = scoreText.scaleY = 3;
        addChild(scoreText);

        // start timer
        setInterval(update, 10);
    }

    private function update():void{
        if(!mutating) return;
        var t:Date = new Date();
        totalTime += (t.getTime() - time.getTime()) / 1000;
        time = t;

        for(var i:int = 0; i < 10; i++) update1();
        scoreText.text = (int((1 - score / scoreMax) * 10000) / 100)
             + "%\n" + mutations + " / " + candidates + "\n"
             + (int(totalTime * 10) / 10) + "s";
    }

    private function update1():void{
        var index:int = Math.random() * POLYGONS;
        var backup:Polygon = polygons[index].clone();
        polygons[index].mutate();
        drawTest();

        var diffBmd:BitmapData = testBmd.compare(inputBmd) as BitmapData;
        diffBmd.applyFilter(diffBmd, rect, pt0, monotoneFilter);
        var testScore:uint = 0;
        for(var i:int = 0; i < 0x100; i++){
            testScore += diffBmd.threshold(diffBmd, rect, pt0, "==", i, i, 0xff) * i;
        }

        if(score > testScore){
            score = testScore;
            testToBest();
            mutations++;
        }else{
            polygons[index] = backup;
        }
        candidates++;
    }

    private function drawTest():void{
        canvas.graphics.clear();
        for(var i:int = 0; i < POLYGONS; i++){
            polygons[i].draw(canvas, imgWidth, imgHeight);
        }

        testBmd.fillRect(rect, 0x000000);
        testBmd.draw(canvas);
    }

    private function testToBest():void{
        bestBmd.copyPixels(testBmd, rect, pt0);
    }
}
}

import flash.display.*;
import flash.geom.*;

class Polygon{
    private const POINTS:int = 6;

    public var points:Array = [];
    public var color:uint;
    public var alpha:Number;

    public function Polygon(polygon:Polygon = null){
        for(var i:int = 0; i < POINTS; i++)
            points[i] = (polygon ? polygon.points[i].clone() : new Point(Math.random(), Math.random()));
        color = (polygon ? polygon.color : 0xffffff * Math.random());
        alpha = (polygon ? polygon.alpha : .1);
    }

    public function clone():Polygon{
        return new Polygon(this);
    }

    public function mutate():void{
        (Math.random() < 0.5 ? mutateColor() : mutatePosition());
    }

    private function mutateColor():void{
        switch(int(Math.random() * 4)){
            case 0: color = (color & 0x00ffff) + int(Math.random() * 255) * 0x010000; break;
            case 1: color = (color & 0xff00ff) + int(Math.random() * 255) * 0x000100; break;
            case 2: color = (color & 0xffff00) + int(Math.random() * 255) * 0x000001; break;
            case 3: alpha = Math.random(); break;
        }
    }

    private function mutatePosition():void{
        var p:int = Math.random() * POINTS;
        if(Math.random() < .5) points[p].x = Math.random();
        else                   points[p].y = Math.random();
    }

    public function draw(canvas:Sprite, w:Number, h:Number):void{
        canvas.graphics.beginFill(color, alpha);
        canvas.graphics.moveTo(points[0].x * w, points[0].y * h);
        for(var i:int = 1; i < POINTS; i++)
            canvas.graphics.lineTo(points[i].x * w, points[i].y * h);
        canvas.graphics.endFill();
    }
}