List of Projects:
1Click飲みRomoCartTempescope色色[:iroiro]Other Projects

2014年11月16日日曜日

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

こんにちは。河本です。
僕はサイゼリヤに行くとまずキッズメニューの間違い探しを解くんですが、
今回は難しすぎたので、大人の力(=画像処理)で解決することにしました。
2014年9月版。みんなもやってみよう!
(以下、間違い探しの答えが出てきます。見たくない人は↑の画像で頑張ってから読もう。)


やり方

いろいろ書いてますが、左面と右面の違う部分を色の差分から見つけてるだけです。
紙の歪みを吸収するために、少しややこしいことをしてます。

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

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

今回は面倒なので、左側は手作業で指定しました。
角を手作業でタグ付けして・・・
こっちは手作業。
射影変換で台形補正します。OpenCVならWarpPerspectiveです。
台形補正しても、紙が曲がってたので少し歪んでる。
次に、左側の画像をテンプレとして使って、右側の画像から紙部分をSURF+マッチングでオブジェクト認識して見つけます。(参考:whoopsidaisies's diary: OpenCVで画像の特徴抽出・マッチングを行う
右面は自動で見つける
そんなわけで、両面の画像ができました。
両方歪んでますが、そもそも紙が曲がってるので射影変換ではこれが限界です。
左面と右面


(3) 局所差分を算出
ざっくり両面の画像が取れましたが、歪みのため単純比較はできません。
例えば、左と右のピクセルの色距離を単純に比較(AbsDiff)するだけでは、こんなことになってしまいます:
左面と右面の同じ位置のピクセルの色の距離。これでは間違い部分は見つけられない。
そこでどうするかというと、
左面の小さい領域を取り出し、
100x100の小さい領域。
再度オブジェクト認識で右面から同じ領域を見つけ、


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

この局所領域を少しずつずらして、ページ全体の差分画像を作り上げます:
(左)差分画像 (右)元のページ
ちゃんと答えのところに大きい差分が出てる。

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

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

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


さいごに

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

サイゼリヤのサイトに過去の間違い探しの画像データが上がってます。元画像なので、精度よく間違い認識できます。答えも載ってるけどな!
歪みが無いので簡単に間違いを認識できる。
・iPhoneアプリにしたり、メニューに直接答えを投影したりとか色々見せ方が考えられますね。暇な時作ります。

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

2014年11月3日月曜日

建物の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)

2014年10月4日土曜日

RomoCart, a hack to turn your living room into a Mario Kart course

(In Japanese here)


RomoCart is the third in our series of home hack projects (TempescopeMoving Windows, Myra) to make your living room a more exciting place to be in.

Here, we used Romo, an educational robot toy that can be controlled using an iPhone app, to recreate the world of Mario Kart in your living room.



By combining Romo and projection mapping, RomoCart lets you race robots around a race course generated in your living room, whilst firing missiles and throwing bananas at opponents.


How it works


RomoCart initially scans your room, and generates an optimal race course based on the layout of your room.
The RGBD camera finds obstacles,
and generates a circuit that best fits the open space.
The system tracks the Romos using the camera, and projects the game environment according to their positions.
We gave Romos some exciting smoke trails...
During the race, players can pick up various items,
Various items and abilities exist, like the "accelerate" item which makes the player move twice as fast.
they can drop bananas, 
Flood the floor with bananas!

and fire missiles at your friends.

Unleash missiles in your living room!
Because the RGBD camera tracks obstacles in real time, you can even step on incoming missiles to protect your Romo.
In RomoCart, even your mum can join in as a Thwomp
We've given special abilities to different objects.
A teddy bear acts as a rotating turret.

and finally, when you cross the finish line, you're welcomed by fireworks.


RomoCart physically turns a part of your home into a racing game.


The System

RomoCart uses 3 pieces of hardware:

Romo

Buy them from Amazon.
Romos have two caterpillar tracks that you can control independently, thus letting you program a "moving iPhone" very easily.

For RomoCart, we built an app "Romote" that receives and executes commands from a PC wirelessly.
We use a gamepad to let users control the Romo, but override their movements with specific actions when, for example, the Romo gets hit by a missile.
We thus use Romo's as an "intelligent radio controlled car".

RGBD Camera


Hang an RGBD camera (like Kinect, or Xtion Pro Live) from your ceiling, to track objects, and auto-generate circuits.
(We recommend Xtion, as it's lighter and works on USB bus power)

Projector


Any projector will do, but you need to be able to get your projector as high up as possible to project onto a sizeable area of your living room.

We used a pico projector "Sanwa PRJ-3", because it's cheap, fairly bright, and can be attached to common tripods, but short throws should work equally well.

In RomoCart, a single Java program receives the depth feed from Xtion, finds objects (including Romo), renders the game environment, and projects it onto the floor.

Algorithms

How do you calibrate the Xtion against projectors?

You want to project the game environment to the correct position with respect to the Xtion's coordinate system.  You need to calibrate the view projection matrix for the projector.
This is a useful link I used to do this.
I'll release the code when I have the time.

How do you auto-generate the circuit from obstacles?

There are many ways of going about this.
I defined a "good" course to be one that vaguely follows the borders of obstacles, while not actually going through them.
I therefore generate a Voronoi diagram using obstacle borders as control points, and find the longest loop.
1:15 in the video should give you a good idea of how it works.
(If you're interested, give me a message)

How do you track the positions of Romo?

We know the input from the gamepad, so we can use that as prior knowledge of Romo's movement.  We calculate a probability for each object in the view being our Romo (using concordance with the movement given from the gamepad, as well as the object's size and height) to find and track our Romo.
This may be a good place to use particle filters, but things worked pretty well using a fairly dumb tracker.

Summary

We presented a system that uses projection mapping and Romo to turn a portion of your room into a Mario Kart-like world.
We showed that by combining very simple hardware and some common tracking algorithms, we can hack our house to be part of an exciting game environment.
All of the source code will be released when we find the time.

We hope this work will persuade others to follow and start similar projects that integrate the real environment with games.





2014年10月3日金曜日

RomoCart:Romoとプロジェクションマッピングで部屋をマリ○カートのサーキットにしてみた




こんにちは、河本です。

最近なにかと話題の教育用ロボット「Romo」を入手出来たので、早速こんなものを作ってみました。
見飽きた部屋をマ○オカート風ゲームのサーキットに変えてしまう、レーシングマニア垂涎のシステムです。

中学生のころ時間も忘れてロケットスタートを極め、バナナを置き、甲羅を投げた思い出を、自分の部屋でまた体験したくはありませんか?

プロジェクションマッピングとロボットを使ってその夢を実現するのが「RomoCart」です。
何言ってるか分からんという方は、まず上記ビデオを見てください。


どんなゲームなの?


RomoCartは、まず部屋のレイアウトをカメラで測定して、最適なコースを自動生成するところから始まります。
部屋の中の障害物を認識し・・・
いいコースを自動生成します。
そしてRomoの位置と向きを認識し、
Romoを認識してスポットライト投影中

レースが始まります。
ゴミ箱や椅子の間をぬってゴールを目指しましょう。
走ると煙が出る!
レース中は色々アイテムを拾ったり、
加速アイテムとかバナナアイテムとか色々あります
バナナを置いたり、
部屋をバナナだらけにしよう

ミサイルを撃ったりしましょう。

居間でミサイルが炸裂
現実拡張型のゲームなので、例えば飛んできたミサイルを踏んで壊すこともできます。
RomoCartではお母さんもドッスンです
物を認識して機能を持たせることもできます。
例えばクマのぬいぐるみを置くと回転砲台になるようにしてみました。
弾幕グマ

そんなこんなを経て、早くゴールを目指しましょう。
部屋に花火が咲きます

マリ○カートの世界を家の中で物理的に再現する、そんな未来のゲームの姿を先取りしてみました。



システム構成

RomoCartで使うのは、3つのハードです:

Romo


教育用ロボット「Romo」です。国内だとOneMeストア買えます。
iPhoneアプリで二つのキャタピラを自由に制御できるので、思うがままに前進・回転・後退させられます。
簡単に「走るiPhone」が作れちゃうナイスなロボットです。

RomoCartでは、PCからネットワーク経由でRomoに指令を出せるリモコンアプリ「Romote」を作り、
PCに繋いだゲームコントローラーから操作できるようにしました。
更にミサイルが当たったりバナナを踏んだりすると、制御をオーバーライドしてスピンさせたり加速させたりしています。
プログラムで制御できるからこそ、ただのラジコンには不可能な表現が実現できます。

ちなみにRomote AppはApp Store公開予定ですが、OneMeでRomoを買うと、無料でソースごと貰えるようにしました。

深度カメラ


KinectでもXtion Pro Liveでも何でもいいので深度カメラを天井に設置しましょう。
個人的には外部電源無しで動くXtionがおすすめです。
RomoCartではこれを使って床の上の物体を認識してRomoの場所をトラッキングしたり、サーキットを自動生成したりしてます。

関係ないですが、天井に深度カメラを常につけておくと、いつでも立体家族写真が撮れて楽しいですよ。

プロジェクター


どんなプロジェクターでもいいんですが、床に投影するためにはなるべく上から距離を稼いで投影しないといけません。
そこでおすすめなのはこいつです:


超小型で三脚の上に付けられるので、上の写真のように天井近くに 設置するのも容易です。

RomoCartでは、XtionのフィードをJavaで書いたプログラムで受け取りRomoの居場所をトラッキングし、プロジェクターでゲーム環境を床に投影して、ゲーム進行を行います。
割と簡単な構成ですね。


アルゴリズム的な話

プロジェクターとXtionってどうやってキャリブレーションするの?

Xtionで測った3次元空間に対して投影する際、プロジェクターのどの座標系に射影できる必要があります。
Xtionとプロジェクターの対応点を沢山(手動でも自動でも)探して射影行列を作り、プロジェクタの位置と姿勢を推定します。
そのあとゲーム環境をJMonkeyEngineでもUnityでもなんでも使って)3Dで描画し、推定したカメラ位置から見た絵を投影します。
このへんのリンクを参考にしてください。
そのうちプログラムを公開します。

部屋のレイアウトからコースの自動生成ってどうやってるの?

いろんな考え方があると思いますが、僕は「いいコース=遮蔽物に沿いつつ、それほど近寄らない経路」という仮定を置き、ボロノイ図から最長ループを探索する、というアルゴリズムを作ってみました。
詳細知りたい人はメッセージください。
文献調べてませんが、色んな方法あると思います。もっといい方法考え着いたら是非教えて下さい。

Romoの位置の認識ってどうやるの?

今回はRomoの挙動が事前にコントローラーの入力から分かっているので、床の上の物体の動きとコントローラーの入力値から尤度を計算して、最も尤度が高い物体をRomoとして認識しています。
他にも粒子フィルタ使ったりとか色々な方法があり得ると思います。
ちなみに位置認識は割と容易ですが、Romoの向きの認識はもっと難易度高いです。面白い問題なので是非チャレンジしてみてください。


おわりに

プロジェクションマッピング+ロボットの構成は熱い!

プロジェクションマッピングというと静止した物体にマッピングするのが一般的ですが、
ロボットの環境を投影するために使うと、ロボットの表現力を幾倍にも高められます。

ラジコンだけではただのラジコンですが、そこに認識+投影を加えると、今まではゲームでしか出来なかった「ミサイルを撃つ」、「滑る床を作る」、「魔法を使う」等の色んなことが現実でも可能になります。
今回はレーシングゲームとして実装しましたが、他にも幅広いゲームや、今までにない表現がプロジェクションマッピング+Romoで出来ますね。

Romoはプログラマーに「足」を与える

ハードウェアを作れないソフトウェア技術者が「リアル」な世界に触れるための道具が少しずつ揃ってきました。
スマホやKinectの普及で現実がセンシングできるようになり、ピコプロジェクターやHMDにより現実への情報提示ができるようになりました。
Romoは更に「動き」を与える新たな道具です。
これまで画面内の世界に生きてきたプログラマーでも、Romoを使えばいとも簡単に現実世界に飛び出て「さわれる」「動かせる」「踏める」システムが作れます。
ぜひ、みなさんもRomoと一緒に現実世界に飛び出てみませんか?