hirax.net::Keywords::「ウォーリー」のブログ

■「ウォーリーを探し出す」Mathematicaコードが「してること」　

　「Mathematicaでウォーリーを探せ！」（"How do I find Waldo with Mathematica?"）が面白かったので、Mathematicaのコードが何をしているかを眺めてみました。

　まずは、Mathematicaコードに簡単な注釈を書き加えてみました。それが下のラクガキです（エッジ検出のテンプレートを間違って4x5で描いてしまいました。正しくは4x4です）。

　このMathematicaコードは、次のような処理を行います。ウォーリーを見つけるために用いられているのは、「（赤色に対する）横エッジ検出」です。

1. 所定のURLから現画像(waldo)を読み込む（Import)
2. 現画像(waldo)をRGBそれぞれの画像として分解
3. RGB画像から（R-G-B)という演算を行い、赤色の量を示す赤画像（マトリクス）を作成
4. 横（水平）エッジ検出用テンプレート（4x4）を作成。テンプレートは上半分＝１、下半分＝０
5. 赤画像の各領域と横（水平）エッジ検出用テンプレート間で”相関”（実際にはベクトル間距離）を算出
6. ”相関”画像を閾値をもとに２値化
7. ”相関”画像は実際には”距離”を使っているので、「値が小さい方がマッチしている」ので、値を反転(ColorNegate）
8. 膨張処理用に円形のカーネルを作成(DiskMatrix)
9. ２値化された（マッチするほど値が大きい）”相関”画像を円形カーネルを使って膨張処理（Dilation）
10. 非マッチ部は0.5・マッチ部は1.0にサチらせたマスク画像作成（ImageAdd部）
11. 原画像（waldo）とマスク画像を乗算し、完成！

　ウォーリーを見つけ出すために使われた③④⑤あたりの「（赤色に対する）横エッジ検出」処理が、シンプルだけれどもなかなか上手く動いているようで、とても面白く感じられます。エッジ検出用のテンプレートのサイズも、4x4という大きさは「必要十分」で上手い…と感心させられます。

　ところで、このMathematicaコードでは、「赤白の横線部があると、ウォリーでなくともマッチしてしまう」でしょう。もしも、より確実にウォーリーだけを見つけ出そうとしたら、一体どんなコードを書けば良いのでしょうか？（この続きが『「ウォーリーを探す出す」多重解像度解析コードを書いてみる!?』です）

■「ウォーリーを探す出す」多重解像度解析コードを書いてみる!?　

　「ウォーリーを探し出す」Mathematica コードがとても面白く・参考になりました。そして、もしも「ウォーリーを探し出す」コードを書こうとしたならば、自分ならどんな風に書くだろう？と考えました。…そこで、試しに、書いてみることにしました。

　まずは、画像を読み込みます。

waldo=Import["hoge"]

　そして、ウォーリーを見つけるには、「やはり、赤白シャツを頼りにすべし」というわけで、赤白模様を検出するための単チャンネルを作成します。ここで、2{1,-1,-1}.#&は、R-G-Bを計算する純（無名）関数です（Stack Over Flow のコードと同処理です。カスタマイズできるように純関数にしています）。

red=ImageApply[2{1,-1,-1}.#&,waldo]

　次は、ウォーリーを探す部分です。Stack Over Flow で書かれていたコードは「横方向の赤白線の上エッジ検出」を行い、「強いエッジがある部分にウォーリーがいる」という推定を行います。
　しかし、その推定では、「ウォーリーが着ているシャツは、赤白横線が何本も入っている」とか「その赤白横線は、胴の形に添った形状をしている」といった情報は用いられていません。
　そこで、「胴の形をした赤白横線模様」を作り、さらにその「模様」を用いた多重解像度解析（ウォーリーの大きさは未知ですから）をすることによりウォーリーの位置を推定する、というコードを書いてみました。

mask=Fold[ImageAdd,#[[1]],Rest[#]]&@Table[
h=a;w=Floor[h/2];
corr = ImageApply[ 4 Abs[# - .5] &,
ImageCorrelate[red,
Image@ Table[Cos@y, {y, 1, 6 Pi, 6 Pi/h}, {h}],
NormalizedSquaredEuclideanDistance ]];
ImageApply[ #/(30 - 5) &,
Dilation[ImageApply[ If[# > .8, 1, 0] &, corr],
ConstantArray[1, 4 {h, w}]] ] , {a, 5, 30}]

　このコードでは、多重解像度解析を行った上で、ありとあらゆる解像度、すなわち、ありとあらゆる大きさのウォーリーがいる（だろう）位置を、一枚のマスク画像へと焼き付けます。

　そして、焼き付けた（推定した）「ウォーリーが立っている位置のマスク画像」を用いて、原画像からウォーリーを浮き上がらせてみます。それが、以下の（Stack Over Flowそのままの）最後のコードです。

ImageMultiply[waldo,
ImageAdd[ColorConvert[mask, "GrayLevel"], .5]]

　試しに、「ウォーリーをさがすとはどういうことか」で使われていたサンプル画像に処理をかけてみると、次のようになります。これが、「ウォーリーを探す出す」多重解像度解析コードです!?

　

---

　赤白模様の「壁」などにマッチしないようにしたい場合のために、下記のようなフィルタリングを加えると良いかもしれません（今回はコードを短くするために割愛しました）。

corr2 = ImageApply[ 4 Abs[# - .5] &,
ImageCorrelate[corr,
Image@ Table[
If[x^2 + y^2 < h, 1, 0], {y, -h, h}, {x, -h, h}],
NormalizedSquaredEuclideanDistance ] ];

■科学が解き明かす「ウォーリーを探せ」の必勝法　

　「ウォーリーを探せ（原典版７冊）」でウォーリーが出現する場所の分布を調べてみると、面白いことに偏りがあります。そこで、効率的に素早くウォーリーを探すにはどうしたら良いかという探索最適化を、これまでの研究者たちの研究報告を踏まえて（これが結構あるんです）、研究してみたのがWolfram BLOG の Find Waldo Fasterです。ちなみに、これまで報告されている研究結果においては、上限端と（上下の）中央を除いた２箇所で横方向に対してウォーリーを探す、というのが最適解とされていました。たとえば、下のアニメーションは、見開きページのウォーリーが隠れてる場所が、上限端と（上下の）中央を除いた２箇所辺りに集中している…ということを示した例になります。

　今回の最新最適解は、ページ上下は探さなくて良くて、左右の見開きページに渡って2.8インチ（７ｃｍ）幅の逆V字を描くように探していけばウォーリーを素早く見つけ出すことができる…というものになっています。

　ちなみに、左右ページでのウォーリー出現分布、なぜか上下反転した類似形状になっているようにも見えます。描く上での事情なのか、探しにくさを考えたためなのか、あるいは印刷安定性を考えたせいなのか…そんなことを考えてみたりするのも、何だかとても面白いです。