二分木のGIFアニメーションを生成する

趣味で平衡二分木を作ったのですが、（この解説記事ももうすぐ上げます）記事を書くにあたり、下のようなgifアニメなどによる説明があると分かりやすいと思い、それを自動生成するスクリプトを書きました。

二分木のgif画像

適当な実装

本当に適当なgif画像を生成するだけなら、フレームごとの画像をgifにするだけ（ブラウザとかコマンドとか）です。

しかし、このままだと、ルートノードの位置がフレームごとにずれてしまったり、そもそも見切れて下のような見にくいgifとなってしまいます。

ずれてしまったgif画像

これを防ぐためには、すべての画像でルートノードの位置を統一してやる必要があり、今回のスクリプトではこの処理もしています。

それでは具体的な方法を解説していきます。

仕組み

以下にスクリプトのコードを置いておきます。

github.com

dot言語による二分木静止画像の生成

まずは以下のような二分木の静止画像を取得することが必要ですが、dotコマンドというGraphvizパッケージのコマンドを使って生成します。

１フレームの静止画像

これは、二分木を全探索しつつ、dot言語のフォーマットを出力するコードを書くことでできます。

詳しくは私のAVL木のコード（下のリンク）や、他の方の記事を参照するなりしてください。（二分木の記事の中にもしかしたら書くかも）

github.com

ルートノードのずれを補正する

ルートノードがずれていないように見えるためには、すべてのフレームでルートノードの座標が一定になっている必要があります。 また、座標が一定でも、画像のサイズが異なればずれているように見えてしまいます。

そのため、

1. すべての画像のキャンバスサイズを一番大きい画像のサイズに揃える
2. すべてのフレーム画像に対して枠からはみ出たりしないようなルートノードの固定位置を検出
3. すべてのフレーム画像のルートノードが固定位置に固定されるように平行移動

という処理が必要です。

1.画像サイズを揃える

ここでは画像サイズが最大となる画像に揃えるので、まずはそのサイズを探す以下のようなpythonスクリプトを書きます。

#biggest_size.py
#coding:utf-8
from PIL import Image
import os

maxW = 0
maxH = 0

filelist = os.listdir(".")

for f in filelist:
    _,aug = os.path.splitext(f)
    if aug == ".png":
        im = Image.open(f)
        rgb_im = im.convert('RGB')
        size = rgb_im.size

        if size[0] > maxW:
            maxW = size[0]

        if size[1] > maxH:
            maxH = size[1]

print("{},{}".format(maxW,maxH))

カレントディレクトリからpngファイルを探し、Imageパッケージにより画像サイズを取得して最大値を更新して最後に出力しています。

こうして得られた最大サイズに各画像のキャンバスサイズを拡大していきます。

MAX=`python3 ./biggest_size.py`
MAXWIDTH=`echo ${MAX} | sed -e 's/,.*//'`
MAXHEIGHT=`echo ${MAX} | sed -e 's/.*,//'`

for file in *.png
do
  FILE=${file%.*}.bmp
  convert ${file} $FILE
  convert $FILE -gravity west -background white -extent ${MAXWIDTH}x${MAXHEIGHT} $FILE
done

拡大に使っているconvertコマンドは ImageMagickパッケージをインストールすると勝手についてきます。 このコマンドのextentオプションにより、画像の拡大ではなくキャンバスサイズの拡大をしてくれます。

2.枠からはみ出ないような固定位置を検出

枠からはみ出ないような固定位置とは、「左端ノードからルートノードまでのx座標の差が最も大きい画像のルートノードの座標」となり、具体的には以下の図の青点のような座標を指します。

このような座標

このようにすれば確かに左方向にははみ出す画像が無いことは保証されるけど、右方向に関してはどうだろうと思う方もいるかもしれません。

本当はそこも処理しなければなりませんが、今回はAVL木であるのでそこまで問題ではないと考えました。もしそれを任意のケースで保証するなら、ずらすことによるはみ出し分を前項と同じようにキャンバスサイズの拡大をすればいいだけです。

以下のpythonスクリプトで画像の画素値を上から下に見ていくことでルートノード、左から右に見ていくことで左端ノードの座標を検出します。

#calc_offset.py
#coding:utf-8
from PIL import Image
import sys
import os

def searchRoot(rgb_im,size):
    for h in range(size[1]):
        for w in range(size[0]):
            r,g,b = rgb_im.getpixel((w,h))
            if r==0 and g==0 and b==0:
                return w,h


def searchLeft(rgb_im,size):
    for w in range(size[0]):
        for h in range(size[1]):
            r,g,b = rgb_im.getpixel((w,h))
            if r==0 and g==0 and b==0:
                return w,h


maxOffset = 0

ret_w=0
ret_h=0

filelist = os.listdir(".")

for f in filelist:
    _,aug = os.path.splitext(f)
    if aug == ".png":
        im = Image.open(f)
        rgb_im = im.convert('RGB')
        size = rgb_im.size

        w,h = searchLeft(rgb_im,size)
        root_w,root_h = searchRoot(rgb_im,size)

        if root_w - w > maxOffset:
            ret_w = root_w
            ret_h = root_h
            maxOffset = root_w - w


print("{},{}".format(ret_w,ret_h))

3.画像を平行移動

2で取得したオフセットをもとに以下のように各画像をずらしていきます。

OFFSET_W=`python3 ./calc_offset.py`

for file in *.bmp
do
  ROOT=`python3 ./search_root.py ${file}`

  convert ${file} -distort Affine "${ROOT} ${OFFSET_W}" ${file}
done

convertコマンドのAffine変換を使い、それぞれのルートノードの位置が固定点になるように平行移動していきます。

gifにする

最後にconvertコマンドですべての画像をつなげたgifにします。

convert -delay 50 -loop 0 *.bmp anim.gif