複数の円のオブジェクトだけで画像の近似を得る。

この記事は異世界行ったら本気だすぴょこりんクラスタ Advent Calendar 2021のためにかきました。

はじめに

タイトルの通り「複数の円オブジェクトだけで画像の近似をつくる」です。

皆様は「遺伝的アルゴリズムで最高にエッチな画像を産み出そう！」ってヤツ覚えてますでしょうか。今日のネタはinspired by アレです。

元の問題設定から、まずモデルの複雑性を下げて問題設定を簡単にしています。元の問題では矩形と楕円が扱えましたが、本記事では円のみを取り扱います。加えて、透明度も元の問題設定では扱っていましたが、ここではこれも扱いません。

更にもっと根本的な話として、みんなの想像する「最高にエッチな画像」ではなく具体の画像を対象としているので、まぁその点だいぶ収束も安定することでしょう。

モデルとアルゴリズム

k個の円があると仮定して話を進めます。これを特定の画像の近似になるように円のパラメータを調整する、という問題になります。

円はパラメータとして、中心の座標(x,y), 半径rad、そして色 (r,g,b)が決まれば一意に定まります。なのでこれら6つのパラメータを持つ円がk個あるので、6×kのパラメータのもとで最適化をする問題になります。

目的関数としては、リファレンスの画像に似せたいので、リファレンス画像との二乗誤差を目的関数としましょう。

そして、探索方法としては、それぞれのパラメータに対して、ほかのパラメータを固定し、「現在のパラメータから-n～nずらした場合の目的関数の値を算出し、それが最小になるパラメータを採用、更新する」というのを愚直に順番に6×k個の各パラメータごとに更新していく、ということをします。

更新のたびに少なくとも目的関数は現状と同じか、小さくなることが保証されるので、局所解に落ちるはずです。

簡単なデータで実験

試しに以下の画像に近づける、という感じでこのアルゴリズムを動かしてみます。

k=80、n=5でいきます。

初期値：

初期値は以下の画像です。果たして前の画像に近づくのでしょうか。

反復回数=5

反復回数=10

密だった画像に白が目立ってきた気がしますね。

反復回数=15

反復回数=20

さらに疎になってきました。もうリファレンスの画像にかなり近いですね。

反復回数=24

もとのリファレンス画像と見比べてみると、なかなかそっくりなところまで来たんじゃないでしょうか。簡単なアルゴリズムでもこれ位はいけるんですね。

これは実画像への適用も期待できそうです。

実画像に対しての適用

240×240の画像にk=500, n=20で試してみました。加えて初期値の半径を小さめにとるという感じにしてみました。あえて何をリファレンスにしたかは言いませんが、皆さん見たことがある画像のはずです。

初期値

反復回数=1 既にリファレンス画像わかりますね。

反復回数=5 約束された勝利。

反復回数=10 ほぼサチったって感じですかね。

一応反復時の目的関数の推移も取ってあります。 数値的にもいい具合にサチった感じですね。

一応貼っておくとリファレンス画像はこれ。

おわりに

思いのほかうまく行っちゃって楽しかった。収束したときの画像よりも1反復の時点での画像が魅力的なのが気になる（？）。gifアニメにしたり、途中で止めたり、目的関数に別の制約を入れたりしても楽しそう。

[おまけ] 円の数によるバリエーション

ご参考まで。高度に抽象化された僕のアイコンたち。

k=2

k=10

k=30

k=80

k=200

k=1000