これは 日本情報クリエイト Engineers Advent Calendar 2016 の11日目の記事です。
はじめに
「入社1年目だから」というのは言い訳にはなりませんが、
諸先輩社員の皆さんのようにギークな内容を書く自信がないので、
とりあえず動くものを作ってお茶を濁そうアピールしようと思い、
表題のとおり、ストリートビューならぬ「間取リートビュー」なるものを作ってみることにしました。
今回は設計編です。
目的
Google ストリートビューのような操作性で、家の中を歩き回れるアプリの作成が最終的な目標ですが、その前準備として、抽象的な表現の仕方を定義（モデル化）します。
思想
- 自分の中にあるもので本質的な仕組みを考えてみる（どんと来い、車輪の再発明）
- 手間を惜しむための手間を惜しまない（実装を楽にしたい）
- 古典的なアルゴリズムや数学的表現はどんどん活用する
設計
基本
- 家の中を歩くルート（道すじ）の表現には、無向グラフを使います。
- 無向グラフの各ノードは写真を撮るポイント（位置）に対応し、各エッジはノード間の移動可能な隣接関係を示します。
- また、各ノードには座標の情報を持たせます。（後々、何かと便利だとろうという算段です）
- すなわち、家の中を歩き回ることを、定義したグラフを辿ることで表現します。
やったー！意外に簡単じゃないですか。
これでブラウザ上で家の中を自由に右へ左へ…あれ？
グラフを俯瞰している状態では、どこにノードがあるのか一目瞭然ですが、
ペグマンのように自分がノード上にいる場合「今来た道に対して、どちらの方向か」という情報が欲しくなります。
すぐに思いつく解決策として、
各ノードに「隣接するノードの、今来た道に対する相対的な方角」を持たせる、
方法を思いつきましたが、それは非常に手間です。
ここで基本に戻りましょう。各ノードは自身の座標の情報を持っているのでした。
これを使わない手はありません。
ノード間の位置関係の表現
ノード $\mu, \nu$ を例に考えます。
$\mu$ から見た $\nu$ の位置を表すには、
それぞれの座標ベクトル ${\bf c}_{\mu}=(x_{\mu}, y_{\mu}), {\bf c}_{\nu}=(x_{\nu}, y_{\nu})$ を使い、
${\bf v}_{\mu\nu} = {\bf c}_{\nu} - {\bf c}_{\mu}$ を計算すれば良さそうです。
画像の初期アングル
ある部屋に南から進入した場合、正面は北です。同様に南西から侵入した場合、正面は北東です。このように、どのノードから移動してきたかによって、画像のアングルを決めてあげなければいけません。
そのために、基準として東西を結ぶ線を $x$ 軸と決め、画像は常に東を向いて撮影することにしましょう。$\mu$ の直前のノード $\lambda$ とすると、 ${\bf v}_{\lambda\mu}$ と $x$ 軸のなす角度分だけ画像のアングルを回転させてやればOKです。
これで、必要最低限の情報を表現する方法が固まりました。（よかった、よかった）
グラフを利用した効率的な撮影法（今後の課題）
本家ストリートビューを見ていると、本当に路地の隅々まで網羅的に撮影されていることに驚きます。
余談ですが、最近、筆者は自動車を購入しまして、燃費の何たるかが身に沁みている今日此の頃なのですが、
そこへいくとストリートビュー車は、さぞ効率的に道という道を走ってるんだろうと想像します。
前置きが長かったですが、間取リートビューでも家の中を効率的に（最短経路で）撮影したい！というだけの話です。これにより、次のようなメリットが考えられます。
- 広い家やビル、庭の撮影などのケースが出てきた場合に、短時間で撮影が可能に
- 大量の画像を撮影した際に、ノードと画像の対応付けが容易に（撮影順が決まるため）
要は「各ノードを1度だけ通る移動コストが最小なルートを求め」たいのですが、これはまさしく 巡回セールスマン問題 と同じNP困難な問題です。全探索を行う場合のオーダーは $O(n!)$ となり、家の規模によっては容易に計算時間が宇宙の年齢を超えてしまいます。
…が、今回はこちらについては扱いません。。興味のある方は Let's google it!
まとめ
- ストリートビューならぬ「間取リートビュー」を設計
- 家の中を歩き回るルートは無向グラフで表現
- 各ノードは座標を持ち、その位置関係はベクトルを計算することで表現
- 各ノードの巡回（撮影）順は今回は任意。
あとがき
あとは実装するだけです。会社から RICOH THETA Sもお借りしてきました。
実は当初、ノード間の位置関係を表すために、もう2つ複雑怪奇な数式が出てきていたのですが、ノートにメモをとっているうちに、それらが不必要なのだと気づきました。手書きのアウトプットって大事ですね。
それから、もう少し説明の画を増やします。。（反省）