遺伝的アルゴリズムでドット絵の「Qiitan」を作ってみる

はじめに

われらがQiitaのマスコットキャラクター「Qiitan」。
現在実施中の「Qiita Advent Calendar 2021」に参加すれば、抽選で巨大Qiitanぬいぐるみをもらえるキャンペーンも行っているみたいですね！

今回は、こんな愛くるしい笑顔の「Qiitan」を遺伝的アルゴリズムを使って画像生成することを試みる記事です。

遺伝的アルゴリズムとは

遺伝的アルゴリズムは、新幹線の先端の形状を考えるのに利用されたり、工場でより効率的な生産計画を立てるのに利用されたりするアルゴリズムです。

どういったアルゴリズムかというと、

データ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。

(Wikipediaより引用)

簡単に説明すると、以下の作業を繰り返し、できる限り理想に近い個体を生成するというようなアルゴリズムです。
（⓪事前準備として、ランダムな複数の個体を用意）
　①ある基準をもって個体を評価し、優秀な個体を選別する
　②選別された個体の情報をもとに新たな個体を複数生成する(低確率で突然変異させる)

今回私が行った方法は、まずランダムな画像を256個用意します。
その後、トーナメント形式で2枚ずつ画像を比較して勝敗をつけ4枚の画像となるまで選別します。
そうして残った4枚の画像から次の世代の256枚の画像を作成していきました。

完成品

実装

ソースの全容は以下のリンクから確認できます。

0. 事前準備

まずは、元となる画像を準備します。

画像をドット絵に変えてくれるサイトを利用してドット絵に変換します。
画像サイズが大きいと大変になりそうなので、ピクセル数を50×50としておきます。
※目が小さいとうまく目が生成されてくれなかったので、少し大きめに修正しています。

次に、ランダムな画像を作成します。
0～255の3つの乱数からRGBを指定して色を作成します。
そうしてできる色を1ピクセルずつ配置することでランダムな画像を生成することができます。

コード

static void CreateRandomImg()
{
    var generation = 0;
    Directory.CreateDirectory(string.Format(FOLDER_PATH, generation));

    for (int i = 0; i < 256; i++)
    {
        Bitmap img = new Bitmap(PIXEL_SIZE, PIXEL_SIZE);
        Random rnd = new Random();
        for (int x = 0; x < img.Width; x++)
        {
            for (int y = 0; y < img.Height; y++)
            {
                Color c = Color.FromArgb(rnd.Next(256), rnd.Next(256), rnd.Next(256));
                img.SetPixel(x, y, c);
            }
        }
        img.Save(string.Format(IMAGE_PATH, generation, i));
    }
}

1. 優秀な画像の選別

基準となる画像と生成された画像を1ピクセルずつ色の差を計算して数値化し、合計値が低い画像を優秀な画像と判断していきます。
ここで問題となるのが色の差です。

みなさんは下の画像を見て、色の差をどう感じるでしょうか？
左と真ん中の色の差より、真ん中と右の色の差のほうが大きく感じられたのではないでしょうか？

しかし、単純にRGBの3つの値を3次元の点と考えて距離を数値化した場合、左右2つの色の差は同じ値となってしまいます。
そこで、CIEDE2000という考え方を利用します。
細かい計算の方法はよくわかっていませんが、色の差をより人間の目で見た感覚に近い値として計算されるようです。
この値を利用することで、より人間が似ていると思えるような画像の生成ができるようになります。

コード

static double GetScore(Bitmap img)
{
    var score = 0.0;

    for (int x = 0; x < PIXEL_SIZE; x++)
    {
        for (int y = 0; y < PIXEL_SIZE; y++)
        {
            var lab1 = CIELAB.RGBToLab(ORIGINAL_IMAGE.GetPixel(x, y));
            var lab2 = CIELAB.RGBToLab(img.GetPixel(x, y));
            var ciede = new CIEDE2000(lab1.L, lab1.A, lab1.B);
            score += ciede.DE00(lab2.L, lab2.A, lab2.B);
        }
    }

    return score;
}

次に、トーナメント形式で2枚ずつ画像を比較して勝敗をつけ4枚の画像となるまで選別する方法についてです。
これには「キュー」というデータ構造を利用します。

まず、キューに0～255までの数字を追加します。
そして、2つずつ数字を取り出して、その番号の画像同士を競わせます。
その勝った画像の番号の数字を別のキューに溜めていきます。
キューが空になったら、勝った画像を溜めたキューを元のキューにコピーして、残り画像が4枚になるまでこの作業を繰り返します。

コード

static void SelectWinners(int generation)
{
    Queue<int> que = new Queue<int>();
    Queue<int> queWinners = new Queue<int>();
    for (int i = 0; i < 256; i++) que.Enqueue(i);

    //4枚になるまで選別作業を繰り返す
    while (que.Count > 4)
    {
        while (que.Any())
        {
            var num1 = que.Dequeue();
            var num2 = que.Dequeue();
            var score1 = GetScore(new Bitmap(string.Format(IMAGE_PATH, generation, num1)));
            var score2 = GetScore(new Bitmap(string.Format(IMAGE_PATH, generation, num2)));
            if (score1 <= score2)
            {
                queWinners.Enqueue(num1);
            }
            else
            {
                queWinners.Enqueue(num2);
            }
        }
        que = queWinners;
        queWinners = new Queue<int>();
    }

    Directory.CreateDirectory(string.Format(WINNERS_FOLDER_PATH, generation));
    foreach (var num in que)
    {
        File.Copy(string.Format(IMAGE_PATH, generation, num), string.Format(WINNERS_IMAGE_PATH, generation, num));
    }
}

2. 次の世代の生成

優秀な4枚の画像からランダムに1ピクセルずつ色を選んで次の世代の画像を生成していきます。
その中で1%の確率で突然変異を起こし、ランダムな色から選ぶパターンを用意しておきます。
(突然変異の確率は調整が必要です。)

突然変異がないと、最初に作成されたランダムな画像にない色が作成されなくなります。
突然変異を入れることで、あまり基準の画像と似ていない局所的最適解に陥ることを防ぎます。

コード

static Color CreateColor(List<Bitmap> images, int x, int y)
{
    Random rnd = new Random();

    //1%の確率で突然変異
    if (rnd.Next(100) < 1)
    {
        return Color.FromArgb(rnd.Next(256), rnd.Next(256), rnd.Next(256));
    }

    var imageNo = rnd.Next(4);
    return images[imageNo].GetPixel(x, y);
}

static void CreateNewGenarations(int generation)
{
    //1つ前の世代の、残った4枚を取得
    var images = new List<Bitmap>();
    foreach (var path in Directory.EnumerateFiles(string.Format(WINNERS_FOLDER_PATH, generation - 1), "*"))
    {
        images.Add(new Bitmap(path));
    }

    Directory.CreateDirectory(string.Format(FOLDER_PATH, generation));

    for (int i = 0; i < 256; i++)
    {
        Bitmap img = new Bitmap(PIXEL_SIZE, PIXEL_SIZE);

        for (int x = 0; x < img.Width; x++)
        {
            for (int y = 0; y < img.Height; y++)
            {
                img.SetPixel(x, y, CreateColor(images, x, y));
            }
        }

        img.Save(string.Format(IMAGE_PATH, generation, i));
    }
}

あとは、「1.優秀な画像の選別」と「2.次の世代の生成」の作業をひたすら繰り返して、基準となる画像に似た画像が出来上がるのを待つだけです。

おわりに

遺伝的アルゴリズムと聞くと「なんだか難しそう」と思っていましたが、ちょっとしたものであれば意外と簡単に実装することができました。

遺伝的アルゴリズムは、「目的は分かっているが、方法が分からない」というような場面で活用されるようです。物理エンジンやゲームの攻略などでよく見かけますが、自分なりに活用できる場を見つけて応用できればなーと思いました。

参考

Qiita - 色の距離（色差）の計算方法
YouTube - 【実験】遺伝的アルゴリズムで素敵なモザイクアート作ってみた【理系の休日】