修士論文 要旨

グラフ構造を有する高次元データからの情報抽出のための手法開発
黒河 天

数理情報学専攻 48166211

長尾 大道 准教授

指導教員

1 はじめに
本研究では，２種類のグラフ構造を有する高次元データを取り扱う．
第１部では，結晶構造や生物組織の顕微鏡写真に代表される多角形充填構造を有する画像データを扱う．既存の領域分割手法によって多角形充填画像を多角形の図 1: 平面に埋め込まれた無向グラフ（点線）とその帯グラフ

境界領域と内部領域に分割するとき，領域としての境界（実線で囲まれた領域）部分は得られるが，境界線そのものや各多角形は得られない．そこで我々は，多角形充填画像のグラフ構造に着目した生成モデルであるグラフフィッティングモデル

フィッティングモデル (graph fitting model, GFM) に従うという．

を導入し，同モデルの最尤推定に基づいて境界線を直接領域 ΓG (ε) を境界，それ以外の領域をバルクという．

抽出する方法を提案する．
第２部では，RGB 画像や地震計ネットワークの観測確率変数 ξm,n を第 m 行・第 n 列のピクセルの画素値値に代表されるグラフ上の多変量信号を扱う．多変量とみなすと，GFM に従う ξ の実現値は観測画像とみなグラフ信号のスペクトル密度行列の推定法を議論し，多せる．すなわち GFM は，境界ピクセルの画素値とバル変量グラフ信号の最適圧縮フィルタであるグラフフー

クピクセルの画素値が異なる正規分布からサンプルさリエ主成分分析を提案する．

れるような画像の生成モデルである．

本稿および発表では，第１部の内容のみを紹介する．

2.2

対数尤度の連続近似({パラメータ θ =2 提案モデル

推定を考える．GFM に従う ξ の負の対数尤度は2.1 定義
頂点集合 V = {1, . . . , I}，辺集合 E なる無向グラフを

G = (V, E) とする．点集合 (x1 , y1 ) , . . . , (xI , yI ) ∈ R2− log p(ξ | θ)∑=−−

して２頂点 (xi , yi ) と (xj , yj ) を結ぶ線分を中心線とする幅 2ε の帯を Γij (ε) と表す．帯の和集合 ΓG (ε) ==ことを X ∼ N µ, σ2)と表す．多角形充填画像の生成モデルであるグラフフィッティングモデルを提案する．
定 義 1 (グ ラ フ フ ィ ッ テ ィ ン グ モ デ ル). 確 率 変 数

ξ1,1 , ξ1,2 , . . . , ξM,N が互いに独立かつ{ ()2N µbound , σbound()ξm,n ∼
2
N µbulk , σbulk

if (m, n) ∈ ΓG (ε) ,if (m, n) ∈/ ΓG (ε)
M,Nを満たすとき，確率変数 ξ = (ξm,n )m=1,n=1 はグラフ()
2log n ξm,n µbulk , σbulk∑fm,n + const.

(m,n)∈ΓG(ε)()()と表せる．n · µ, σ 2 は N µ, σ 2 の密度関数であり，ある確率変数 X が平均 µ，分散 σ 2 なる正規分布に従う(∑(m,n)∈Γ/ G(ε){i,j}∈E Γij (ε) を G の半幅 ε の帯グラフとよぶ．無向グラフの平面埋め込みとその帯グラフを図 1 に示す．

()
2log n ξm,n µbound , σbound(m,n)∈ΓG(ε)

および ε > 0 が与えられたとき，任意の i, j ∈ V に対∪} )(xi , yi )Ii=1 , ε なる GFM の最尤

fm,n =(ξm,n − µbound )2(ξm,n − µbulk )21σ2−+ log bound22222σbound2σbulkσbulkとする．総和∑(m,n)∈ΓG(ε) fm,n は頂点座標や半幅について連続でないため，微分可能な関数∫˜ =J(θ)Ψ dS(1)

ΓG(ε)

で 近 似 す る ．Ψ :R2 → R は ( 1/2 , M + 1/2 ] ×( 1/2 , N + 1/2 ] 上で f⌈x− 1/2 ⌉,⌈y− 1/2 ⌉ を，それ以外で 0 をとる２次元スカラー場である．ただし，⌈x⌉ は実グラフ構造を有する高次元データからの情報抽出のための手法開発 (黒河 天)

数 x 以上の最小の整数である．この近似は画素を細かくする極限で一致する．

3 階段スカラー場の帯グラフ積分の最小化
式 (1) を，帯同士の３次以上の交叉を無視して関数J (θ) =

∑ ∫{i,j}∈EΓij(ε)Ψ dS −∑∑i∈V {j,k}⊆Ni∫Ψ dS(a)(b)∆i,jk(ε)

図 3: GFM の (a) 生成画像および (b) 100 通りの初期頂点座で近似する．Ni は頂点 i ∈ V の近傍である．∆i,jk (ε)

標．(b) のひとつながりの線が１つの初期グラフ埋め込みを

は図 2 に示す凧型である．領域 Γij (ε) および ∆i,jk (ε)

表す．

を適切にパラメータづけることで，目的関数 J とその∂J ∂J ∂J∂J ∂J勾配を計算できる．J , ∂x, ∂yI , ∂ε の時,, . . . , ∂x1 ∂y1I

間計算量は O(|V | + ε |E| + εL) となる．

数値実験の結果，KNOWN および PI-GMRF は頂点座標を画像の横幅の 1% ほどの誤差で，半幅を 0.1% に満たない誤差で精度よく推定できた．PI-GMM による推定誤差は頂点座標，半幅ともに画像の横幅の 1% から3% 程度になった．一方で，ESTIMATE の計算は不安定化し，推定誤差が 1013 ∼ 1015 倍までに増大した．

4.2

領域分割の判別精度

第 4.1 小節の KNOWN，PI-GMRF，PI-GMM，ES(a)(b)

図 2: 凧型 ∆i,jk (ε)．実線は帯 Γij (ε) および Γik (ε) の境界を，破線は凧型 ∆i,jk (ε) の境界を表す．

TIMATE に基づく領域分割の誤判別率を大津法 (Otsu,1979)，混合正規分布の最尤推定，ガウス・マルコフ確率場の最大事後確率推定 (Besag, 1986) と比較した．

KNOWN と PI-GMRF の平均誤判別率は 1% ほどに抑えられ，ガウス・マルコフ確率場の最大事後確率推定の4 数値実験
4.1 最尤推定の精度
GFM の 生 成 画 像 か ら 頂 点 座 標 と 半 幅 を 近 似 最尤 推 定 し ，推 定 誤 差 を 測 定 し た ．頂 点 座 標 の 初 期誤判別率に匹敵した．PI-GMM の平均誤判別率は 5%から 10% ほどになり，混合正規分布の最尤推定や大津法の誤判別率を下回った．

参考文献

値 は 真 の 頂 点 座 標 を ガ ウ ス ノ イ ズ で 動 か し た 100
通 り と し ，半 幅 の 初 期 値 は 真 値 を 含 む 3 通 り と した．生成画像と初期頂点座標を図 3 に示す．提案手法 と し て ，KNOWN，PI-GRMF，PI-GMM，ESTI-MATE の４種類を用意した．KNOWN はパラメータ22µbound , σbound, µbulk , σbulkを既知として最適化を行っ22た．PI-GMRF は µbound , σbound, µbulk , σbulkに混合正規分布の EM アルゴリズム (Zhang et al., 2001) に基づく推定値をプラグインして最適化を行った．PI-GMM
22は µbound , σbound, µbulk , σbulkに混合正規分布の EM アルゴリズムに基づく推定値をプラグインして最適化を2行った．ESTIMATE は µbulk , σbulkに PI-GMM と同2じ推定値をプラグインし，µbound , σboundを変数に含めて最適化を行った．最適化には逐次２次計画法 (Boggs,1996) を用いた．

Y. Zhang, M. Brady, and S. Smith, “Segmentationof brain MR images through a hidden Markov random field model and the expectation-maximization
algorithm,” IEEE Trans. Med. Imaging, vol. 20,no. 1, pp. 45–57, 2001.
P. T. Boggs, “Sequential quadratic programming,”
Acta Numer., vol. 4, no. 1, pp. 1–51, 1996.
N. Otsu, “A threshold selection method from graylevel histograms,” IEEE Trans. Syst. Man. Cybern., vol. 9, no. 1, pp. 62–66, 1979.
J. E. Besag, “On the statistical analysis of dirty pictures,” J. R. Stat. Soc. Ser. B, vol. 48, no. 3, pp.
259–302, 1986.