Growing Neural Gasの基礎と点群処理
岡山大学 学術研究院自然科学学域
助教 戸田 雄一郎

"%!
" $" ! $# !" %& ! %" ! " %" %# !" $" $& !
&' ()*+,-*,./+,01 0' $ /12!% ,3# *433# +5/1 67# 84 ./1 9)2:4# +5/+ ;,14 <= /12# ;,14# >?# ,3# .@03342A
B4C+7#84 @4(0D4#+54#*01:4@#42:4#";,14#<= 0@ >?!A#

Growing Neural Gas

・自己組織化マップの拡張手法であるGrowing Neural Gasは，エッジの追加や削除を行う手法が組み込まれており，冗長なエッジやノードが発生しにくい手法
・そのため，与えられたデータ構造に従った位相構造の学習及び位相構造に基づくクラスタリングが可能となる()* +,-.)/01, 2,)3-4(5* 6/.,37,-.89/ 2,)3-4:80;3, <=>?>@A !10938.4B
NodeEdge Addition

3.3.3 Evaluation of GNG-TSelf-Organizing Maps

const!

E5,3 34.+,01 35083#F/3,.#4C-4@,(41+/*#@43)*+3#0' .0(-/@,301 8,+5 G>H7 GBG /12 GBGIE 0'.013+@).+,01 0' +5@44 @,1:2/+/ Gas
2,3+@,F)+,01 "J,:A$"/!!A G>H7GBG /12 GBGIE 3+)2,42 +54
Neuralconst+0-0*0:K 0'# ,1-)+# 3,:1/*3A# E54# -/@/(4+4@3# )342 ,1 G>H# 3,()*/+,013 84@4L# '#())*+5M6A6N7+/M6A66O7 $#,-)7 %#)-))).*
GBG#/12 GBGIE# 3,()*/+,013#84@4L# '#/))*+5M6A6$7 +/M6A66O7NG ,1withCHLconst$#)-.7 %#)-))).*0#,))AJ,:)@4 $ "F!7 ".! /12 "2! 35083 ',1/* 3+/:43 0' / 3,()*/+,01 /'+4@ $6666/2/-+/+,01 3+4-3 '0@ / +5@44@,1: 2/+/Cell
2,3+@,F)+,01
FK G>H7 growth
GBG /12 GBGIEA &1 ',:A$ "F!7 G>HGrowing
Structure+0-0*0:K .0)*21P+ @4'*4.+ ,1-)+ 2,3+@,F)+,017 /127 ,1 ',:A$ ".!7 GBG .0)*21P+ .013+@).+ +@,/1:*4.0(-*4+4*K7 /12 0+54@ 5/127 ,1 ',:A$ "2!7 GBGIE .0)*2 .013+@).+ +@,/1:*43 .0(-*4+4*KA

Edge Deletion

Triangulation

!

!
!
!
"!

-Growing Neural Gas()* 6/C;. #87.385;.89/

Input data

growth(5*>"2SOM

"""

!
!
"GCS

GNG

Growing Neural Gas
初期化
二つのノードの参照ベクトルh1とh2をランダムに生成し，結合関係c1,2 = 1，エッジの年齢g1,2=0とする．
h2
c1,2 = 1g1,2=0

h1

勝者ノードの選択
入力ベクトルvを計測データからランダムに1つ取得する．
入力ベクトルvに対する第1勝者ノードs1と第2勝者ノードs2を選択する．

hs2

s2 = arg min kv
i2A\s1hi kv

s1 = arg min kv
i2A

hs1

hi k

Growing Neural Gas
エッジと積算誤差の更新
・ノードs1について入力データvとの二乗誤差を積算誤差Es1に加算する．
・ノードs1と結合関係がある全てのエッジの年齢をインクリメントする．
・エッジの年齢を0にリセットし，ノードs1とs2との間にエッジが存在しなければ，新たにエッジを作成する．
・事前に設定した閾値gmaxを超える年齢のエッジを削除する（ci,j=0）．
・その結果，他のノードと結合関係を持たないノードは，そのノードを削除する．
hs2

cs1,s2 = 1
gs1,s2=0v

gs1,i!gs1,i+1v

hs2

hs1 Es1

Es1 + kv

hs1 k2

gs1,i > gmax
cs1,i = 0

ノードの更新ノードs1及びノードs1と結合関係があるノードの参照ベクトルを更新する．
v

hs1

h s1
hj

hs1 + ⌘1 (v hs1 )hj + ⌘2 (v hj ) if cs1 ,j = 1

hs1

Growing Neural Gas
ノードの追加("回ごと)・積算誤差が最大のノードuを選択する．
・ノードuと結合関係のあるノードの中で最も積算誤差の大きいノードをfとし，uとfを結合するエッジを2分するようにノードrを挿入する．
・ノードu, f間のエッジを削除し（cu,f = 0), ノードu, r及びr, f間にエッジを追加する（cu,r = 1，cr,f = 1）.
・ノードu, fの積算誤差を減衰率!を用いて更新する．
・ノードu, fの積算誤差の平均をノードrの積算誤差とする．
hfhrEE↵Euhuu = arg max Ei

uEfEf ↵Ef
Er = 0.5(Eu + Ef )i2A

積算誤差の減衰全てのノードの誤差を減衰率#により減衰させる．

Ei

EiEi

(8i 2 A)u

Growing Cell Structureにおけるノードの追加指標
・成長型の競合学習で、常にk-dimensionとなる位相構造を構築しながら成長していく学習アルゴリズム
GCSの目的・位相構造と入力ベクトル空間が近い構造を持つように学習する
・データの確率密度分布に近い構造を学習する
この2つの目的は同時に達成できるか？

GCSのノードの追加条件
・GCSにおいては、積算されていくノードの追加指標を”resource”と呼び、以下の式において定義をしている

Es 1

Es1 + kv2

h s1 kOr

Es1

Es1 + 1

Growing Neural Gasと積算誤差
Es 1

Es1 + kv

hs1 k2

GNGでは、入力ベクトルと第1勝者ノードの参照ベクトルの距離の二乗の累積値が、ノード追加の条件として使用される積算誤差は妥当か？

データ数:5000
データ数:5000
どのように、位相構造を学習したいかは目的によって異なる

Growing Neural Gasと積算誤差
Es 1

Es1 + kv

Es1

Es1 + 12h s1 kGrowing Neural Gasの問題点？

非定常データに対してGNGを適用すると現時刻にデータが存在しない位置にノードが残ってしまう動的(非定常)データへの適用問題点？

解決策

GNGのノードを記憶として捉える場合に悪くない性質であるが、時系列データを処理したい場合には困った性質となるノードを削除する基準を決めて、動的にノードの数をコントロールする学習アルゴリズムを考える

Growing Neural Gas with Utility
非定常データに適用するためにFritzkeによって提案されている
GNG with Utility (GNG-U) を用いる
第1勝者ノードのユーティリティ値Us1 を更新

削除のための指標

Us1

Us1 + ||vhs2 ||2||v

hs1 ||2

ユーティリティ値の減衰

U c ! U c " #U c
削除の基準

q = arg max Ec

減衰率"により積算誤差と同様に減衰させる

最小のユーティリティ値が低く、最大の積算誤差が大きい場合、ノードを削除する

ci = arg min U cc

Eq U i > k

基準は固定のしきい値kによって決定される

Growing Neural Gasの問題点（その2）？
これまでの入力ベクトルは位置座標のみで構成されいたどうなる？

色付き点群

適用結果

問題点？

入力ベクトルが異なる複数の属性で構成されている場合、位置情報の幾何的な空間構造を保持することができない

解決策①

入力ベクトルの属性に重みを付けて、重要な要素を重点的に学習する方法論を考える

関連重要度を用いた色付き点群の学習
重み（関連重要度）のベクトルを定義し、勝者ノードの選択と積算誤差の計算時に重み付き距離尺度を用いるだけで良い
勝者ノードの選択

積算誤差の計算( )U ! U + w "(v # h ) # w "(v # h )( )s = arg min w " ( v # h )Es1 ! Es1 + w " v # hs1

s1 = arg min w " v # hii!A2

2

s1

ii!A\s1

Original 3D point cloudvi = (vi,x ,vi,y ,vi,z ,vi,R ,vi,G ,vi,B )

2

T

s1

s2

Without Related importancew = (1, 1, 1, 1, 1, 1)

T

s1

2

w: Related importance vector
v: Input vector
hi: The ith node position*: Element wise production

With Related importancew = (1, 1, 1, 0, 0, 0)T

各属性の重みをどう設計するかは非常に難しい問題である

関連重要度を用いた色付き点群の学習

位置:1.0 色:1.0

位置:0.8 色:0.2

位置:1.0 色:0.0

位置:0.5 色:0.5

位置:0.0 色:0.0

各属性の重みをどう設計するかは非常に難しい問題である

GNG with Different Topologies (GNG-DT)

3D point cloud空間

部屋の一部（クラスタ数:1）

色

赤，青，白（クラスタ数:3）

形状

4つの面，円柱（クラスタ数:5）

オブジェクト

箱，缶，机，壁（クラスタ数:4）

・・・

RGB-Dカメラから計測された未知の点群データをクラスタリングする際には，物体の色や形状などの属性情報ごとに得られるクラスタの結果が異なる

GNG with Different Topologies (GNG-DT)

従来のGNGにおける単一の位相構造の構築ではなく，複数の位相構造を保持による点群処理のための新たな知覚システムの構築

GNG with Different Topologies (GNG-DT)
変数定義
入力ベクトルの属性：S in = {pos, col, . . . }参照ベクトルの属性：S ref = {pos, col, nor, . . . }入力ベクトル：v = (vpos, vcol, . . . )col nor
参照ベクトル：hi = (hpos,hi , hi , . . . )ioo
属性oの位相構造：C o = {c1,2, . . . , ci,j,...}

距離定義
属性oにおける入力ベクトルとi番目の参照ベクトルとの距離を以下のように定義する．

dio = | | vo − hoi | |GNG with Different Topologies (GNG-DT)
距離尺度
点群の学習では，幾何的な構造を保持することが，最も重要な役割となる．
よって，GNG-DTでは勝者ノードと積算誤差の累積における距離尺度として，位置情報(pos)のみを用いる
勝者ノードの選択s1 = arg min diposi∈A

s2 = arg min diposi∈A\s1

積算誤差の累積2
Es1 ← Es1 + (dspos)1

位置:1.0 色:0.0

GNG with Different Topologies (GNG-DT)
ノードの更新
第1勝者ノードs1は従来どおり更新し，近傍ノードは各属性の位相構造を利用し更新する

h s1

hs1 + ⌘1 (vh s1 )hoj

hoj + ⌘2 (vhoj )if cos1 ,j = 1

エッジの更新
位置情報

位置情報の位相構造(Cpos)は，従来どおり，勝者ノードs1, s2の間にエッジが存在しない場合，追加をする．
その他の属性情報

その他の属性情報の位相構造(Co)は，以下の式により，更新する⇢

cos1 ,s2 = 1
cos1 ,s2 = 0

if khos1 hos2 k < ⌧ ootherwise複数の位相構造と組み合わせ

位置情報(Cpos)

法線情報(Cnor)

前提知識の利用

色情報(Ccol)法線情報(Cnor)

面情報(Cpos)

位置情報(Cpos)

ノードの引き算

色と法線情報(Ccol・Cnor)
オブジェクト情報GNG-DTのRGB-Dカメラへの適用

3次元点群における形状特徴量
3次元点群における形状特徴量は，局所的な面要素を構築し主成分分析をすることによって求めることができる．
局所面の共分散行列Ciの計算
k

Ci = " h j ! oi
j=1(T) (h ! o )jikhi + " wi, j # h j
oi =j=1
k1+ " wi, j$ h !h 2'ij),wi, j = exp & !
2s&%)(

j=1

Local surface

固有ベクトルvj と固有値"j の計算
Normal vector niCurvaturev3 ( 1ri =3)2
31+2+33次元点群における形状特徴量
形状特徴量と固有値・ベクトルの関係

λ1v1λ3v3λ2v2λ3v3λ1v1λ3v3λ2v2λ1 ≫ λ2 ≈ λ3λ3v3λ1v1λ2v2λ1 ≈ λ2 ≫ λ3λ1v1λ2v2λ1 ≈ λ2 ≈ λ3

λ1 − λ2
s1d =λ1λ3λ2 − λ3
s3d =
s2d =
λ1λ1