サイゼリヤの間違い探しが難しすぎたので大人の力で解決した

こんにちは。河本です。

僕はサイゼリヤに行くとまずキッズメニューの間違い探しを解くんですが、

今回は難しすぎたので、大人の力（＝画像処理）で解決することにしました。

2014年9月版。みんなもやってみよう！

（以下、間違い探しの答えが出てきます。見たくない人は↑の画像で頑張ってから読もう。）

やり方

いろいろ書いてますが、左面と右面の違う部分を色の差分から見つけてるだけです。

紙の歪みを吸収するために、少しややこしいことをしてます。

(1) 間違い探しページの写真を撮る
↑の写真です。普通にiPhoneで撮りました。

(2) ページ領域を抽出する
画像からページの部分を見つける必要があります。

今回は面倒なので、左側は手作業で指定しました。
角を手作業でタグ付けして・・・

こっちは手作業。

射影変換で台形補正します。OpenCVならWarpPerspectiveです。

台形補正しても、紙が曲がってたので少し歪んでる。

次に、左側の画像をテンプレとして使って、右側の画像から紙部分をSURF＋マッチングでオブジェクト認識して見つけます。（参考：whoopsidaisies's diary: OpenCVで画像の特徴抽出・マッチングを行う）

右面は自動で見つける

そんなわけで、両面の画像ができました。
両方歪んでますが、そもそも紙が曲がってるので射影変換ではこれが限界です。

左面と右面

(3) 局所差分を算出
ざっくり両面の画像が取れましたが、歪みのため単純比較はできません。
例えば、左と右のピクセルの色距離を単純に比較（AbsDiff）するだけでは、こんなことになってしまいます：

左面と右面の同じ位置のピクセルの色の距離。これでは間違い部分は見つけられない。

そこでどうするかというと、
左面の小さい領域を取り出し、

100x100の小さい領域。

再度オブジェクト認識で右面から同じ領域を見つけ、

見つけた領域の左面と右面を比較、差分抽出（absDiff→threshold→erode→dilate）します。
文字の輪郭はどうしても差分ノイズが乗りますが、erodeで大体消えます。

この局所領域を少しずつずらして、ページ全体の差分画像を作り上げます：

（左）差分画像　（右）元のページ

ちゃんと答えのところに大きい差分が出てる。

(4) 間違い部分の抽出
最後に差分画像から輪郭抽出（findContours）して、「間違い」を探します。
見つけた領域を元の画像に描画したのが以下です：

誤認識は3つあります。
また、一個だけ見つけられていないのがありますね。（どこでしょう？）
実際には二値化のステップの閾値を下げれば見つけられますが、そのぶん誤認識も増えます。
今回の問題では、精度を下げてでも再現率を上げた方がいいですね。

というわけで、一番最初にページ領域を手作業でタグ付けする部分以外は、全自動で間違い探しを解くことができました。

さいごに

・最初にテンプレを手作業で作らないといけないのは、いろいろ自動化する方法があります。例えば「同じような画像が２つ並んでる一番大きい領域を探す」みたいなことをしたり、机を見つけて除外するとかすればいいんですが、ちょっと汎用性が落ちそうなので今回は止めました。

・サイゼリヤのサイトに過去の間違い探しの画像データが上がってます。元画像なので、精度よく間違い認識できます。答えも載ってるけどな！

歪みが無いので簡単に間違いを認識できる。

・iPhoneアプリにしたり、メニューに直接答えを投影したりとか色々見せ方が考えられますね。暇な時作ります。

・OpenCVが使えれば世の中の大抵の問題は解決できる。

---

他の分析エントリ

- 山手線リアルタイム混雑情報で遊んでみよう
- 140文字の「重み」を言語毎に比較してみた
- 世界で一番住みやすい場所を計算してみた
- 建物のWifiをホッピングして東京から大阪まで通信できるか
- Topcoderに一番有利な時間帯を調べてみた
- Wikipediaのデータで人生解析をしてみよう
- 明日の天気を過去の似た日から合成して可視化してみよう
- 「頭痛」を含むツイートと気圧の関係を調べてみた

建物のWifiをホッピングして東京から大阪まで通信できるか

日本ほど建物密度が高い国なら、Wifiだけでどこまでも行けるはず・・！
（Satellite Image taken from TerraMetrics for educational purposes)

こんにちは。河本です。
最近ネットの自由を脅かす様々なニュースが話題になってますね。
NSA職員が傍受したヌード写真で遊んでたり、
英国がネット検閲に力入れ始めたり、
ハンガリー政府が「インターネット税」の導入を決めたり。
現行のインターネットは、施政者の息がかかった電気通信事業者のインフラ無しでは繋ぐことすら出来ません。
これはしょうがないことなのでしょうか？

ところでネットワークの種類にWANETというものがあります。
簡単に言うと、短距離の無線ノード同士を接続することで、バケツリレー的にデータを遠くまで運ぶ技術です。
中央の統制者が居ないため、検閲しにくく、インターネット従量課税なんてアホなこともできません。

そこで今回は、もし住宅に置かれたWifi基地局同士を繋いで純度100%の「草の根インターネット」を作ったら、東京からどれぐらい遠くまで通信できるのか、を検証してみたいと思います。

各戸に短距離無線しか無くても、複数の家を中継すれば遠いところまで通信できる

前提条件
・国内の全ての建物に1台の無線基地局が置かれている
・基地局は通信圏内にある他の基地局と相互接続されている
・通信距離は色々実験する（Wifi：~100m　ブーストしたWifi：3200m）

今回は「そもそも接続可能なのか」という観点だけを考えるので、伝送速度やロバスト性などは考えないとする。

建物データの取得
この検証のためには、国内の全ての建物の位置を取得する必要がありますが、そんなデータはどこにも公開されていません。

そこで今回は、Google Mapsから画像認識してクローリングしてきました。
怒られそうなので詳細は省きますが、このように建物の中心点と大きさを認識します：

建物認識の結果
（Satellite Image taken from TerraMetrics for educational purposes)

こんな感じで全国4000万戸の建物を抽出しました。

下の図は国内の全建物の密度を示してます。東京と大阪が濃いですね。

国内の建物分布
(Satellite Image taken from TerraMetrics for educational purposes)

Wifiを使う場合の通信範囲
各家に通常のWifi基地局（通信半径100m）しか無い場合に、東京駅からホッピングで通信できる理論的な範囲（＝100m以内にある建物同士を繋いで行った時に、東京駅からカバーできる領域）を計算してみました。

ノード間通信距離100mのWANETで東京駅からWifiのホッピングで通信可能な範囲

意外と狭いですね。
通信領域内の建物は246万戸、全体の5%程度の建物しか含まれません。
東京の半分と埼玉県の一部分しか入っていません。
大阪と通信するなんて、夢のまた夢でした。

よく見ると、荒川と多摩川に塞き止められていることがわかります。
Wifiの通信距離では、川を越えられないんですね。

荒川を越えられなかった。（赤点：東京駅から通信できる建物。対岸には赤点が存在しない。）

次に、必要なホップ数を見てみましょう。
下の図では、東京駅から通信する際に中継する建物の数を表しています。
最大（東吾野あたりまで）で700ホップも必要なことがわかります。
今回は通信の性能の話はしませんが、スループットを出すのも大変そうですね。

ノード間通信に必要なホップ数。都内はだいたい100ホップぐらいで行ける。

というわけで、一般的なWifi基地局では、都内ですら通信できない場所があるという、残念な結果になりました。

Wifiをブーストした場合の通信範囲
普通のWifi（IEEE 802.11 a/b/g/n）で通信できる距離は、国内では100mだけですが、
せっかくなのでブースターを使って通信距離を伸ばした場合に、どれぐらい範囲が広がるか実験してみましょう。（日本では違法です）
このブースターは3.2kmまで行けるなどと言っているので、
200m, 500m, 1000m, 2000m, 3200mで実験してみました。

各建物の通信距離が200mの場合

ノード間通信距離200mのWANETで東京駅から建物をホッピングして通信できる範囲

通信可能な建物は798万戸、全体の17%です。
急に広がりましたね。一番北は群馬まで届いています。
興味深いのが、荒川と多摩川の越え方です。
通信距離が200mあっても川の本流では越えられていないため、川が細くなる場所まで大回りしてのルートが取られています。
一方、江戸川と相模川はそれでも越えられていない様子です。


各建物の通信距離が500mの場合

ノード間通信距離500mのWANETで東京駅から建物をホッピングして通信できる範囲

通信できる建物は1320万戸、全体の28%です。
川は難なく越えられるようになりました。
北はいわきまで届いています。
しかし伊豆半島の田舎っぷりには負けてしまった様子です。 

各建物の通信距離が1000mの場合

ノード間通信距離1000mのWANETで東京駅から建物をホッピングして通信できる範囲

通信可能な建物は3202万戸、全体の68%です。
一気に通信範囲が全国レベルに広がりました。
大阪ばかりか、九州まで到達できたのは驚きですね。
九州まで行くのに1200ホップ程度で済んでいることも予想外でした。

一方、北のいわきはどうしても越えられていないようです。

また、伊豆付近の接続エリアが疎なのが気になりますね。
このへんを空爆されたら西と東の通信が遮断されそうです。


各建物の通信距離が2000mの場合

ノード間通信距離2000mのWANETで東京駅から建物をホッピングして通信できる範囲

通信可能な建物は3258万戸、全体の70%です。
さっきから50万戸ぐらいしか増えてません。
鳥取まで開通したぐらいの変化でしょうか。


各建物の通信距離が3200mの場合

ノード間通信距離3200mのWANETで東京駅から建物をホッピングして通信できる範囲

通信可能な建物は3380万戸、全体の72%です。
2000mとほとんど違いがわかりません。長野県の山間部にもネットが開通したぐらいです。
九州まで350ホップで通信できるようになったのは嬉しいですが、相変わらずいわきが越えられていません。。。

まとめ
・一般的なWifiをホッピングするだけで23区内は通信できる（かも）。その外には行けない。

・1000mぐらい通信距離があれば全国レベルのネットワークが貼れる
　→全部の家に1000mの基地局を置く必要はないかもしれない。例えば川の手前とかに置くだけで、残りは通常のWifiで十分かもしれない。（未検証）

・完全に自由が守られた国では、こんなネットワークは無駄かもしれません。でも広域災害が起きたり、日本のインターネットへの締め付けが強くなってきたときに「市民がいかにして自らを守るか」を市民レベルで常に考えていくことに価値があると思います。
・例えば独裁国家にこっそり無線基地局をばらまいて、検閲不可能なネットワークを無理やり張っちゃったりしたら面白いよね。

・地図とか衛星写真を画像認識すると色々解析できて面白い。

・いわきの闇は深い。

おしまい。

(Satellite Image taken from TerraMetrics for educational purposes)

---

他の分析エントリ

- 山手線リアルタイム混雑情報で遊んでみよう
- 140文字の「重み」を言語毎に比較してみた
- 世界で一番住みやすい場所を計算してみた
- サイゼリヤの間違い探しが難しすぎたので大人の力で解決した
- Topcoderに一番有利な時間帯を調べてみた
- Wikipediaのデータで人生解析をしてみよう
- 明日の天気を過去の似た日から合成して可視化してみよう
- 「頭痛」を含むツイートと気圧の関係を調べてみた