現在のロボットは、センサーが収集した実世界の点群データと、テンプレートにある物体、例えば、ウサギの3Dドット表現を比較することにより、物体を識別しようとしている。テンプレートの画像は、ウサギの耳や尻尾など、物体の特徴的な曲線や角度を表現するドット群を含んでいる。既存のアルゴリズムでは、実世界の点群の中から類似した特徴的な姿を抽出し、これをテンプレートの画像と対応付け、回転や移動してテンプレートに揃えながら、点群にこの物体が含まれているかを決定する。しかし、センサーが収集する点群データには、位置や間隔についてのエラーが常に存在するため、多数の誤った対応付けが生じ、最終的に物体を誤って特定、あるいは特定に失敗する。

最先端のアルゴリズムでは、良い対応付けと悪い対応付けを区別できるが、これには“指数関数的な時間”を要し、高速なコンピューター群を使っても常識的な時間内に終わらない。また、迅速な対応付けを行うアルゴリズムもあるが、研究チームによれば、「間違っていることを認識せずに間違う、最悪なアルゴリズム」もある。

研究チームは、点群データの中からテンプレートに類似した物体を抽出し、その後サイズ、位置、方向という3ステップで対応付け、かつ悪い対応付けを排除する手法を開発した。この手法には、点群データとテンプレートの対応付けにおいて、変動するサイズや位置の対応比の最も確からしい値を決定する「適応投票方式」アルゴリズムと、物体を回転してテンプレートの方向に揃える際に「凸緩和」を利用する「凸最適化アルゴリズム」を導入している。

その結果、膨大な点群においても、比較的短時間で物体を特定するとともに、悪い対応付けを排除できるようになり、実際にリビングルームの中でシリアルの箱と野球帽を見つけることに成功した。研究チームは、「将来的に、複雑なセンサーやデータを使う自動運転車で、膨大な点群データを解析できるようになる。更にナビゲーションや家庭用ロボットなどにも応用できる」と、その活用に期待している。

（fabcross for エンジニアより転載）