🖼️

四分木の中で最も複雑な領域を分割し続けるアートの作り方

2022/07/21に公開

JavaScript

この記事では上記動画のような四分木の中で最も複雑な領域を分割し続けるアルゴリズムについて解説を行う。実装例としてTypeScript + p5.jsのコードも載せている。

アルゴリズム

まず元画像を用意する。

用意した画像を数学の象限のように4分割する。そして、分割した領域ごとにその領域の平均色で塗りつぶす。

分割したそれぞれの領域で、元画像の複雑さをスコアとして数値化する。

スコアが一番高い、つまり一番複雑な領域である左下を更に4分割する。

後の手順は前述の繰り返しで、分割した領域を平均色で塗りつぶし、それぞれの領域の複雑さをスコアとして表し、最も高いスコアの領域を更に分割していく。

ただし、分割対象となるのは今分割した左下領域だけではなく、それに加えて先程分割されなかった残りの3つの領域も含める。

どうやって平均色を求めるのか？

対象領域の各ピクセルをRGBに分解し、それぞれの総和をピクセル数で割ると平均色が求められる。

どうやって複雑さをスコアとして表すのか？

これには色々な手法が考えられるが、今回は2つの方法を採用する。

標準偏差

統計で利用される標準偏差は、各データとそのデータ群の平均値をもとに計算する方法で、一般に標準偏差が大きいとデータの散らばり度合いが大きく、逆に標準偏差が小さいとデータの散らばり度合いが小さい、つまり平均値の近くにデータが集まる傾向がある。

この標準偏差を各領域の複雑さとして利用したい。平均値は前述した平均色をそのまま利用すればいいので都合がいい。

$σ = \sqrt{\dfrac{(x_1-μ)^2+(x_2-μ)^2+...+(x_n-μ)^2}{n}}$

標準偏差 $σ$ を求める式は上記であり、 $x_1, x_2, ... x_n$ が領域内の各ピクセル、 $μ$ が平均色、 $n$ がピクセル数になる。

const error = (hist.reduce((prev, cur, i) => prev + cur * (i - avg) ** 2, 0) / num) ** 0.5;

領域のサイズ

筆者が試した限り、大体が上記の標準偏差をスコアにするだけで事足りるが、大きい領域が残ると見栄えが悪くなるケースがあるので、補助的に領域のサイズが大きいほどスコアも高くなるようにしたい。

const areaPower = 0.2;
const calcArea = (rect: Rect): number => {
  return (rect.right - rect.left + 1) * (rect.bottom - rect.top + 1);
};

calcArea(rect) ** areaPower;

領域のサイズを求める calcArea() で、領域のサイズそのものをスコアにする。そして areaPower という指数を用意することで、領域のスコアの影響を調整できるようにする。

そもそも、この指標が必要なければ areaPower に 0 を入れればいい。

ある領域が分割されすぎる場合があるのでは？

if (rect.right - rect.left + 1 <= minSize || rect.bottom - rect.top + 1 <= minSize) {
  score = -INF;
}

これ以下のサイズで分割されたくないという場合は、そのサイズを定数 minSize に入れておき、領域の幅か高さがその値以下になればスコアに固定のマイナス値を入れればいい。

どうやってスコアを管理して取り出すのか？

配列に領域情報を入れておき、そこから最もスコアが高い領域を探し出すのがシンプルだが、計算量が $O(N)$ になるのと、毎回分割する際に領域を1つ取り出して、そこから4つ増やすことになるので、後になればなるほど計算時間が増えることになる。

なので、代わりに優先度付きキューを使った方がいい。下記ではTypeScriptの実装例を載せているが、JavaScriptにはヒープの関数などが用意されていないので、npmに登録されている heap-js を利用している。

https://www.npmjs.com/package/heap-js