形状の位置合わせを飛躍的に高速化させるアルゴリズムを発見! ~コンピュータグラフィックスなどの分野に貢献~(2020.12.14)

形状の位置合わせを飛躍的に高速化させるアルゴリズムを発見!
~コンピュータグラフィックスなどの分野に貢献~

 金沢大学理工研究域生命理工学系の広瀬修助教は,非線形点群位置合わせ問題を解くための新たな高速化手法を発見し,位置合わせを行うための計算時間を大幅に短縮させることに成功しました。

 非線形点群位置合わせ問題とは,それぞれが点の集まりで表現される2つの類似形状に対して,一方の形状をもう一方に重ね合わせるように形状変化させることで,点と点の対応関係を推定する問題です。この問題は,本人認証のための3次元顔認識や,人物写真からの3次元フェイスモデルの復元など,その応用が非常に多岐にわたるため,コンピュータグラフィックスやコンピュータビジョンの分野で重要視されています。しかしながら,非線形位置合わせの既存手法の多くはそのスケーラビリティに課題があり,数百万点以上で構成される形状に対しては,非線形位置合わせ問題を短い時間で解くことが難しい状況でした。

 同助教は,非線形点群位置合わせ問題に対し,これまで試みられることのなかったガウス過程回帰と呼ばれる予測手法に基づいた近似計算を行うことで,計算コストを飛躍的に軽減させることに成功しました。1400万点以上で構成される形状の組(図1)に対する位置合わせを行った結果,昨年報告した先行手法では24時間以上であった計算時間を2分程度に短縮することが確認されました。また,人間の3Dモデルやスキャンデータで構成される,いくつかの形状の組に対してこの手法を適用できることが数値実験により示されました(図2)。

 これらの知見は将来,人物写真からの3次元顔モデルの復元や本人認証のための3次元顔認識などに利用されることが期待されます。

 本研究成果は,2020年12月14日に機械学習・人工知能分野で最も権威があるとされる国際誌『IEEE Transactions on Pattern Analysis and Machine Intelligence』に掲載されました。また,論文で使用されたコンピュータプログラムが同助教により以下のウェブサイトで公開されています(https://github.com/ohirose/bcpd)。

図1: 1400万点以上で構成される形状の組に対する適用結果

 提案手法は,ダウンサンプリングと呼ばれる点を減らす作業と形状変化ベクトルの補間を組み合わせることで位置合わせを高速化する。(a) 位置合わせの対象となる点群データ。(b) ダウンサンプリング後の点群データ。(c) ダウンサンプル後の点群データに対する位置合わせ。(d) ダウンサンプリングで除去された点に対する形状変化ベクトルの補間。形状変化ベクトルは,ガウス過程回帰と呼ばれる手法により補間される。

 

図2: 開発手法の適用例

 左側の2つの形状が位置合わせの対象となる形状である。この形状データに対し,左端の形状を左から2番目の目標形状に重ねるように形状変化させることで位置合わせを行う。右端は昨年同助教により報告された手法の適用結果で,目標形状に位置合わせされていることが分かる。「BCPD++」で示される4つの形状が,今回開発された手法による結果。左から右に行くにつれ近似計算の精度を向上させている。近似精度がある程度以上の場合は,昨年の手法とほぼ同じ結果が得られていることが分かる。

      

・ IEEE Transactions on Pattern Analysis and Machine Intelligence

・ 研究者情報:広瀬 修