ニンゲンメモ

タメになりそうでタメにならない日記

位相的データ解析と3D画像認識

職場のNIPS読み会で位相的データ解析の論文

Kwitt, et al., Statistical Topological Data Analysis - A Kernel Perspective, NIPS2015

を取り上げてみたので位相的データ解析(TDA)の話。

ちなみにコチラのブログ

qiita.com

によると、"Deep Learningの次はTDAが来る?"とのことで、とてもhotでsexyな領域ってワケです。

Topological Data Analysis (TDA)

TDAというのはトポロジー*1に根付いたデータ解析のアプローチで、データの持つ幾何的な情報に基づいて識別・分類するというもの。実応用としてはCVや医用画像解析の分野だけでなく、タンパク質構造の分類をやっている人も居るっぽい(バイオインフョ出身なのでこの本とてもきになる)。

www.amazon.co.jp

基本的には

データ → persistence diagram → 識別・分類 

という流れになる。*2

persistent homologyとpersistence diagram

僕なんかが書くより、こちらのブログ

xiangze.hatenablog.com

またはこの動画がとてもオススメ。特にこの動画、8分くらいでとてもわかりやすい。

www.youtube.com

persistence diagramの求め方

点群(point cloud)の場合

点群からpersistence diagramを得るには

  1. 各データ点のまわりを囲う円を考える。円の半径(or 直径)パラメータ tをどんどん大きくしていったときに2円が交わったら2点間にエッジを引く、3円が交わったら3点を結ぶ三角形を塗りつぶすというような形で単体*3を作り、与えられた点群に対して単体的複体(simplical complex)を構成する。
  2. 1つの単体が t=t_bで生まれて(birth)、 t=t_dで無くなる(death)という関係を2次元座標系上の1つの点 (t_b, t_d)として表す。
  3. 最終的に点群の幾何的な情報を抽出した2次元座標上の点集合、persistence diagramを得る。

という流れになる。(詳しくは動画参照)

こういうことをすると、球面上に分布した点群とドーナツ面上に分布した点群の幾何的な情報の差異を、2つのpersistence diagramの違いとして浮き彫りにできる、というワケである。

3次元画像の場合

Heat Kernel Signature(HKS) [Sun, et al. SGP2009]というのを用いてpersistence diagramを得るのがpopularであるとのこと。基本的なコンセプトとしては熱の拡散のしやすさ・しにくさを考えることで形状の違いを見出せるだろうというもの。

 

多様体 \mathcal{M}上で熱拡散の方程式を考えると

 \Delta_{\mathcal{M}} u(x, t) = - \frac{\partial u}{\partial t}

となる(ただし \Delta_{\mathcal{M}}Laplace-Beltrami operator )。この微分方程式の解は

 u(x, t) = \int_{\mathcal{M}} k_t (x, y) u(y, 0) dy

という形である関数

 k_t (x, y) = \sum_{i=0}^{+\infty} \exp (- \lambda_i t) \phi_i (x) \phi_i (y)

を用いて表せる( \lambda_i, \phi_i:  \Delta_{\mathcal{M}}固有値・固有関数)。

この関数(heat kernel)  k_t (x, y)は時間tの間に熱がどれだけ xから yへ移動したかを表しているので、地点 xの熱の伝わりにくさは k_t (x, x)で表せるわけです(Fig. 1)。

f:id:chika0509:20160226232946p:plain

(Fig.1 各3次元画像について k_t (x, x)の値の高低をヒートマップで表した図 ([Sun, et al, SGP2009]より抜粋)。熱が伝わりにくい先っちょの部分は値が大きくなっている)

手順としてはFig. 2のように、

  1. 3次元画像をもとにメッシュ上の点と点どうしの隣接関係をグラフとして表す
  2. グラフ上の各頂点にheat kernelの値 k_t (x, x)を割り振る
  3. 閾値パラメータを -\inftyからどんどん増やしたときにconnected componentsの生成・消失をpersistence diagramとしてプロットする

f:id:chika0509:20160226234215p:plain

(Fig. 2 職場での発表スライドから)

 

このあたり、きちんと解説している文献が見当たらなくて発狂していた

自分なりに解釈してこのFigを書いたつもりだけどわりと自信ない。ツラい。

 

ここまでがデータ(点群or3次元画像)からpersistence diagramを得るまでの話。

 

persistence diagramに対するkernel

ここからはpersistence diagramに基づいて識別・分類する話。

先行研究[Reininghaus, et al. CVPR2015]で、3次元画像データに基づくpersistence diagramに対してkernelを定義して画像の分類タスクをこなしましたというのがあり、

このNIPS2015の論文はそのkernelをちょこっといじくることでkernel embeddingもできるようにしましたよという話。kernel embeddingができると2標本検定ができる!*4ということで実データ実験では脳組織の3次元画像データを用いて例えば生後6ヶ月未満・以降の2グループについて新生児の脳室に幾何的な違いがあるかという問題にアプローチしていたりする。

つぶやき

ニューラルネットの次はTDA、かどうかは正直よくわからない。でも斬新さを感じる。

しかし多様体の形状を反映した関数が欲しいという状況で、熱拡散を持ってくるという発想がすごいと思った。なぜそこでブッツリ学を導入しようと考えられるのか、こういうけんQ、発想力の違いを見せつけられる感があって目からウロコである。

どうでもいいけど画像界隈はいつもこういうかわいみのある画像に包まれながらけんQしてるのかな、楽しそうやなーーって思いました。

f:id:chika0509:20160227002932p:plain

(Fig. 3  [Sun, et al., SGP2009]よりかわいみ画像) 

*1:ドーナツとコーヒーカップは同相(homeomorphic)というアレ。同相というのは、こないだの集合と位相の記事の単語で言うなら、単射かつ全射であって、その逆写像もまた連続となるような連続写像の定義域とその像の関係を指す。

*2:TDAではpersistence diagramではなくbarcodeと呼ばれるプロットで幾何的な情報を表すことも考えられる。barcodeについての解説はやはり動画を参照。

*3:点・線分・三角形・四面体・...といった基本的な図形を n 次元に一般化したもの

*4:もっと他に面白いことできそうだが