『ねこもに』のパーティクルフィルターアルゴリズムを書き、特許出願してみた

『ねこもに』は、当社オープンストリームが開発中の新商品である。来年春の発売を目指している。現在開催中のCEATECにて発表・出展し、概ね好評をいただいているようだ。

ねこもには、スマホとBluetoothを使ったシステムだ。猫の首輪にBluetooth(BLE)発信機を取り付けて、専用のスマホアプリを使って猫を探したりできる。

このシステムの肝となるのが、猫の場所を見つけるアルゴリズムである。よく誤解されるのだが、 このアルゴリズムは、iBeacon のような ON/OFF表現ーー『近くに居る・居ない』ーーで猫を見つけるのではない。二次元マップ空間上で、連続値的に猫の存在確率分布を計算して推定しているのである。その部分はちょっとした工夫をしていて、ざっと調べたところ類似の前例が見つからなかったので、現在特許を出願している。

今回、このアルゴリズムの数理的な部分は私が考案させてもらった。たまたま、この方面の知識と経験があったからである。もちろん、突然思いついた訳ではなく、ねこもにという商品のコンセプトが先にあって、その解決策を考えていくうちに発想できたものである。

『ねこもに』のコンセプトは、当社のねこもにチームが発案し、毎年開催している社内コンペに勝ち抜いたものである。猫への愛情にあふれた、なかなか良いアイデアである。ただ、最初にその構成案を聞いたときには、これはちょっと無理じゃないのかな？と思った。情報処理のモデルを単純に考えると、典型的な不良設定問題になっていたからだ。

ご存知の通り、不良設定問題とは、与えられた入力情報だけでは答えが一つに定まらない、というタイプの数学的問題である。

BLEは、個体を識別するIDの他は、電波強度＝距離しか検知できないデバイスである。つまり、BLE自身は一次元センサーであって、二次元的な位置を計測する機能はない。

これでどうやって猫の位置を精度良く推定しようか？・・・離散的なON/OFF表現のメッシュマップでもできるけど、それだと、メッシュの分解能以上の精度を出すのは難しいし、広域をサポートしようとすると、メッシュのデータを保持するメモリ容量も膨大なものになる・・・考えるうちに気がついたのはモーションステレオとの類似性である。

モーションステレオは、単眼カメラでステレオ視を実現する画像処理技術である。単眼カメラは二次元センサーであり、ステレオ視は奥行きを含めた三次元情報の復元が目的である。つまりここでも、一つ次元が少ないセンサーから、一つ次元の高い情報を再構成している。その点でねこもにの課題と似ていることに気づいた。（気づいたときはちょっと嬉しかった）

モーションステレオでは、カメラを移動させながら複数の画像を撮影して、奥行き推定を行う。同様にねこもにでも、スマホを移動させながら、BLEとの距離複数回計測して推定に使えば良いだろう、これが基本コンセプトになった。

もう一つの問題がある。それはBLEの距離値の誤差がけっこう大きいことである。BLEから得られる距離値は、周囲の環境の影響を受けたりして、平気で数メートル〜数十メートルぐらいの誤差がでるときがある。画像のモーションステレオなら、それなりに良いレンズなどを揃え、適切なキャリブレーションを実施すれば、ほとんど入力誤差を考慮する必要がないが、BLEは誤差だらけであり、誤差を考慮しないとまともな答は出ないのは明白であった。

センサーから誤差の影響を減らしたいとなれば、誰もが考えるのがフィルター理論の適用であろう。私もまずは古典的なカルマンフィルターを考えたが、５秒後に却下した。カルマンフィルターでは、対象物体の運動を線型な方程式で表現できないといけない。気まぐれな猫の運動を線型な方程式で記述できるわけがないｗ。そうなると・・・パーティクルフィルターを使うのが常識であろう。

というわけで、ねこもにでは、パーティクルフィルターを使うことで、誤差込みの距離センサー値を複数回重ねあわせて、二次元位置を逐次推定するモデルを使うことに落ち着いた。

パーティクルフィルターを位置推定に使う特許や論文は沢山あるのだが、ほとんどがGPSや移動台車のデッドレコニングなどへの適用例であり、ねこもにのようなアプローチは意外に見つからなかった。なので特許を出願したわけである。

実際のソフトウェア実装の話も書こうと思ったが、かなり長くなったので、また別の機会にしよう。