注意：この文章は、『ゼルダの伝説 Breath of the Wild』のネタバレを含みます

ハイラルは広大だわ

と、Nintendo Switch のゲーム、「ゼルダの伝説 Breath of the Wild」をプレイした人は誰もが感じたろうと思います。フィールドがとにかく広い。それゆえ、ハイラルのどこかにあるXをN個見つけてこい、の類のクエストは結構大変なわけです。「鯨の化石を三つ」も時間がかかったし、「イワロックを40体」はまだ終わってません¹。

この手のクエストをやっている時に、ハイラルの白地図があったらチェックした場所を塗り潰しながら探索して効率を上げられるかも、と思ったわけです。

もちろん、ゲームのシステム内に地図はあります。しかし書き込みはできない²し、なにせ広大なので全体を見ると細部がわからないし、拡大すると全体との繋りがわかりずらく、しらみつぶしの探索には不向き。

Zelda BotW の地図 (動画) 四段階に拡大縮小できる

広域	→	→	詳細

なら、最大拡大の地図をキャプチャして貼り合わせればいいのでは、と思いついたのが今年の5月。11月になって当時を思い出しながらこの記事を書いています。旬を逃がした感は否めないですが、誰かの役に立つことを祈って。

最大拡大の地図断片をキャプチャする

Nintendo Swith のコントローラには、画面キャプチャボタンがあって、ゲーム画面を保存してSNSに投稿したりSDカードに保存したりできます。とはいえ、これでハイラル全土をカバーする画像を用意するのは面倒すぎます。

地図を横方向にスクロールしている動画をキャプチャデバイスで録画して、そこから断片を切り出すことにしました。

地図を横スクロール (動画)

動画からの切り出しも動画編集ソフトを使って手動でやっていては手間がかかりすぎます。こういう時はCLIツール。 ffmpeg で
ffmpeg -i 動画ファイル -r フレームレート %04d.png
とすると、断片の静止画が連番で作成されます。さらにキャプチャ画像のうち地図断片として使える部分の切り出しも同時に行うスクリプトがこちら

extract.sh

#!/bin/sh
ffmpeg=ffmpeg
framerate=4

for f
do
    dir=$(basename $f .ts)
    [ -d $dir ] || mkdir $dir

    $ffmpeg -i $f -r $framerate $dir/%04d.ppm

    for p in $dir/*.ppm
    do
        pnmcut -left 150 -top 100 -width 398 -height 510 $p | pnmtopng > $dir/$(basename $p .ppm).png
    done
done

フレームレートを4にすると隣りあった断片に70%程度の重なりができました。フレームレートが低すぎて重なりが薄いと相対位置を検出しにくくなり、高すぎると画像枚数が増えて処理に時間がかかります。³
こうして作成した一連の断片を、以降「行」と呼びます。

pnmcut と pnmtopng は Netpbm のコマンドです。Netpbmには多数のコマンドがあって、画像ファイルをシェルスクリプトで処理する時に重宝します。今回の作業でも多用しました。

パノラマ合成アプリ

さて、切り出した断片をどうやって繋げるか。最初に思いついたのは、パノラマ写真を作るアプリを使う手でした。試してみたのは Hugin と Autopano-sift の組合せ。試しに以下のような縦2列×横3枚の画像を処理してみます。

結果はこうなりました

こうなってほしかった	Huginの合成結果

周辺でゆがんでしまうのは、Hugin がカメラで定点から撮影した画像をつなげるために画像を補正するからのようです。正距円筒とか等立体角とか色々なレンズタイプを選べるのですが、カメラとか光学についての知識がないので、どれを選べばよいのかわからず、試行錯誤しても歪みのない連結画像を得られませんでした。

libsift

打開策を求めて調べていたところ、autopano-sift は、libsift というライブラリを使っているとわかりました。
libsift は、以下のような機能を提供します。

画像の特徴点を見つける
2枚の画像の特徴点を比較して、一致する特徴点を探す

同梱されている実行ファイル showone.exe と showtwo.exe でその働きを視覚化できます。

showone 実行結果

元画像	検出された特徴点

showtwo 実行結果

libsift を使ってみる

というわけで、libsift を使えば、地図の断片をつなぎあわせるプログラムが書けるのはないか、ということで方向転換です。

libsift は C# 用のライブラリなので、作成するプログラムもC#となります。C#は書いたことがありませんでしたが、いい機会なので勉強しながら書いてみることにしました。

まずは横に繋げてみる

横スクロール動画から切り出した画像について、
1. libsift を使って特徴点を検出
2. 隣り合う断片の特徴点を比較して相対位置を求める
3. 断片を貼り合せて横方向の連なりを作成する

上記のスクリプトは横スクロール動画からおよそ150枚の断片を作ります。1行分の全ての断片をこの手順で貼り合せられるのが理想ですが、後述するように接続が検出できない場合があり、複数の「連なり」に分かれることになります。

下図は、23枚の断片を接続した連なりです。

ちゃんとした長方形でなく斜めになっているのは、横スクロールが完全に水平ではなかったせいです。
(アナログスティックをぴったり真横に保持するのは難しい)

特徴点を検出できない地域

前述のように、特徴点を検出できない地域があります。

太線で囲んだあたりは、等高線も少なく色の変化もないので、libsift は特徴点を検出できないか、数が少なくて隣りの断片と一致させられません。

リンクが侵入できない峡谷(青)については諦めてもいいですが、砂漠地方(赤)は必要なので対策を考えます。

コントラストを変更して処理

特徴点の少ないのっぺりした地図でも、画像のコントラストを調整すると検出しやすくなる場合があります。
例として、ゲルド砂漠のこの2枚の断片は、そのままでは接続できません。

鯨の化石の左上にある小丘がキーになって接続できそうですが、libsift が特徴点を抽出できないのです。

そこで、NetPBMの pnmnorm を使って画像のコントラストを強めると、特徴点が検出され、両画像を接続できるようになりました。

調整結果	特徴点

検出結果

この調整を行なっても、接続を検出できないケースは残ります。上の二枚の左隣の場合、下図のような検出結果となり、

検出結果

誤検出に正常検出が埋もれてしまい、正しい相対位置を判別できなくなります。これは、コントラストを強めることによって元動画に演出として入っている淡い縦縞を特徴点として拾ってしまうせいのようです。

人の目にはこの2枚の断片の相対位置が明らかで、検出する方法はあるはずですが、実装には至りませんでした。⁴
問題が起こる場所は地図として重要でない場合が多いし、そもそも海の部分などはどうにもならないので、残念ですが後述の回避策でお茶を濁しました。

連なりを縦に繋げる

横スクロール動画を北から南へ少しずつずらしながら録画して、それぞれの動画から作成した連なりを縦につなげれば地図の完成です。
横の接続の場合は、元が水平スクロール動画なので、順番につなげていけば良かったのですが、縦につなげる時はうまくつながる断片を見付ける手間が必要です。それぞれの行の中の位置が近い断片で一致するはずなので、

1.上の連なりの中から候補の断片を選ぶ
2.その断片の行内の相対位置±5個の範囲で下の連なりの断片を選び、特徴点の一致を検出する
3.最もよく一致したペアを上下の連なりを接続する基準として使用する
4.一致するペアが見付からなければ、上の連なりの別の断片を候補として繰り返す

(これで見付けたペアを、以降「柱」と呼びます)

例として、以下の二つの連なりを縦に接続します。

上下の断片を調べると、下の二つの断片が良く一致します。

上の断片	下の断片	検出結果

検出結果にもとづいて二つの断片を縦につなぐと

これを柱として上下の連なりを接続します。

赤と青の枠は、柱を示しています。⁵

隣接する行の連なりについて、柱を見付けて接続する処理を全ての連なりについて実施すれば、地図の完成です。連なりの接続はグラフ構造になります。

誤差

理想的には、連なりのペアについて柱を一つ見付けて接続すれば、全てがぴったり収まるはずです。しかし実際には、特に長い連なりの場合に顕著ですが、ずれが出てしまいました。模式的に示すとこうです。

元画像を	切ってつなぐと	ずれた

ずれが発生する原因としては、
- 断片を横方向に接続する処理で誤差が蓄積する
- 動画をキャプチャする段階で歪みがある
などが考えられます。 (検証はしていませんが)

対策として、一組の連なりについて柱を複数見付けるようにして、柱のところで辻褄が合うように水平方向の接続を伸ばしたり縮めたりして調整する、という処理を追加しました。

誤接続

下図のように連なりの接続がおかしくなることが、時々起こります。

これは、柱の検出が間違っているせいで、発生します。上の接続での柱はこの部分ですが、誤検出が起きています。

誤接続の柱	libsiftの誤検出

地図上の別の場所に書かれている「ダイアモン川」を結びつけてしまっています。

このように、地名の文字が誤検出を誘発しやすいです。下図もその例です。


地名が違っていても誤検出してしまう場合もあります。

地名以外では、コログや祠のマークも問題になりやすい。

誤接続の対策

libsift が見付けた接続をベリファイする

重なりの部分を上下の断片から切り出して比較します。正しい接続であってもピクセル単位で比較しても完全に一致することはない (地図表示のエフェクトのせいで色合いが変るなど) ので、比較には Netpbmの pnmpsnrを使用しました。

これで、誤接続をある程度はじくことができましたが、

重なりが小さい場合
のっぺりした地形での誤接続

などのように、判定できないケースが残りました。

複数の柱で上下の連なりの相対位置を比較する

同じ連なりのペアに複数の柱がある時、そのうちの一つの柱が誤接続であるなら、相対位置を比較すれば異常な接続が検出できます。

長い連なり同士の接続ではこの方法が有効ですが、柱が一つしかないような接続には効果がありません。

指示ファイルによる除外

誤接続を防ぐのは簡単ではなさそうだったので、特定の断片のペアを接続として使わないように指示するオプションを追加して凌ぐことにしました。

row00300/0101.png row00310/0098.png
row00300/011?.png row00310/010[123].png

誤接続が起きる時は隣接する断片で同じような誤検出が発生することが多いので、ファイルの指定にワイルドカードを書いて行数を減らせるようにしました。

ついでに、水平に繋ぐ時に問題であった接続できない部分についても、このファイル中に指示できるようにしました。

row00040/0150.png row00040/0151.png 121,0
row00040/0151.png row00040/0152.png 106,0
row00040/0152.png row00040/0153.png 121,0
row00040/0153.png row00040/0154.png 106,0

ファイル名だけ書いてあったら接続禁止ペア、数値が付いていたら断片の相対位置として扱います。

その他の問題

隙間

地図を横にスクロールする動画から断片を切り出して使っているわけですが、スクロールを完全に水平にできないのことからいくつか問題が発生しました。一つは二つの行の間に隙間があいてしまうケースです。

この場合はしょうがないので、間を埋めるような横スクロール動画(上図の赤枠部分)を追加して再実行です。

上下逆転

スクロールが水平でないせいで起きたもう一つの問題は、下図のように行の上下関係が逆転するケースです。

上下が逆になっても接続はできますが、さらにもう一つ下の行と隙間ができてしまって繋がらなくなります。

こういう場合のために、行の断片を入れ替える機能を追加しました。

こうなっていたら	断片を入れ替える

速度

ハイラル全体をカバーする断片を得るのに、横スクロール動画が80本ほど必要でした。各行から150枚ほどの断片が採れるので、13000枚弱の断片を貼り合せる作業になります。かなり時間がかかるので、高速化のための工夫をしました。

処理を並列化する
特徴点の検出結果や、断片の接続をキャッシュして再利用する

並列化

C#なので、LINQで書いておけば AsParallel() を挿入するだけでお手軽並列化ができます。
並列化したのは、

各行を横方向に繋ぐ処理
柱を見付ける処理 (複数の場所で柱候補を同時に検索する)

AsParallel()は便利でよいのですが一点だけ、線形なフィルター処理でAsParallelを入れるとアイテムの順番が変ってしまうことがある、という点に嵌りました。仕様なのかバグなのか深追いせず、Sort() を追加して逃げました。

キャッシュファイル

各断片の特徴点は、複数回参照されます。

水平に接続する時、左右の断片と比較する
柱を探す時に、上下の連なりにある複数の断片と比較する

また、全体の作業は、

プログラムを実行して断片をつないでみる
誤接続を見付けて、指示ファイルに追加する
1に戻る

の繰り返しなので、特徴点と断片の接続情報をキャッシュして再利用できればかなり高速化できます。

各断片ごとに、

その断片の特徴点
左隣りの断片との相対位置
上の連なりの断片と柱を組んだ場合の相対位置

をキャッシュファイルに格納しておき、次回からは libsift を呼ばずに済ませられるようにしました。

誤検出対策

全図を作る作業で一番面倒だったのは、誤接続を見付けて指示ファイルを更新して再試行する繰り返しでした。
誤検出を起こした柱を素早く見付けられるように、機能を追加しました

柱の部分を枠で囲って表示する
柱部分だけ取り出した画像ファイルを生成する

柱部分だけの画像を見れば、人間の目には誤接続が明かなので、どの断片を指示ファイルに追加すれば良いか判断できます。誤接続自体が起きないようにできれば一番良かったのですが。

結果

13000個弱の画像をつなぎあわせて、20342×16530 ピクセルの地図を作れました。
1/10 に縮小した画像を示します。

課題

接続不能部分と誤接続

接続できない場所と、誤接続の防止について、今回は指示ファイルに記述するという手作業による対策を取りました。
ハイラルの地図を作るという特定の目的のためのプログラムだったのでそれで良かったのですが、これを汎用のツールにするなら、やはりプログラムで回避できるようにしたいところです。

誤接続になった柱を人間の目でみれば間違いが一目瞭然なので、何らかの手段があるはずだと思います。

ベリファイをもっと真剣にやったら改善するか
SIFT以外のアルゴリズムはどうだろうか
流行りの機械学習とか？

色合いの調整

上に揚げた合成結果に見られるように、虫の這った後のような模様が入ってしまいました。これは、ゲーム中の地図表示に明るさを周期的に変動させるような視覚効果が入っているせいです。これを画像処理で平滑な色合いに修正することはできないものか。Hugin などのパノラマ作成ソフトには、写真ごとの色合いの違いを均す機能がついているようなので、手段はありそうです。

白地図

元々の目的は、書き込みのしやすいハイラルの白地図が欲しいというところだったので、画像から等高線と文字などだけを取り出せればいいのですが。

まとめ

ゲームプレイ動画から静止画を切り出してつなぎあわせることで、一枚の大きな画像を作り出すことができました。
つなぎあわせの過程で遭遇した問題について、多分に場当たり的な対策を施しました。
C#による並列化などを使って、プログラムの実行を高速化してみました。

プログラムのソースコードは、もうちょっと整理できたら Githubに上げたいと思います。

追記

輪郭抽出すれば良いのではというアドバイスを頂いたので、試してみました。

Netpbm に pamedge⁶ というコマンドがあるので、適用してみます。輪郭は抽出できましたが、libsift で検出できる特徴点が大幅に減ってしまったので、さらにpgmenhance を通しました。

上でも使ったゲルド砂漠の化石の断片で例示します。

元の断片

pamedgeの結果	左図の特徴点

pgmenhanceの結果	左図の特徴点

ここまでは良さそうに見えましたが、隣の断片と特徴点をマッチさせると、コントラスト調整の時よりも悪くなってしまいました。

(コントラスト調整によるマッチング)

他の場所でも試してみましたが、輪郭抽出でマッチングが向上するケースはありませんでした。

おもにSplatoon2を始めてしまったせいですが。 ↩
地図上の任意の場所にマークを置けますが、100個に制限されている。 ↩
今にして思えば、もうちょっとレートを下げて枚数を減らせば良かった。 ↩
単にコントラストを強めるのではなく等高線だけ抽出する、とか。あるいは流行りの深層学習？ ↩
この表示はプログラムのデバッグに便利だった。 ↩
Debian では Netpbm のバージョンが古く、pamedge のかわりに pgmedge があったので、ppmtopgm | pgmedge で代用した。 ↩

ハイラル全図を作ってみた