FIT2016（第 15 回情報科学技術フォーラム）RI-001
グラフ信号の局所線形近似によるグラフ形状単純化
Graph Shape Simplification Based on Local Linear Approximation of Graph Signal
佐々木崇元 †
Takayuki Sasaki

谷田隆一 †Ryuichi Tanida

清水淳 †Atsushi Shimizu

1. はじめに地図や画像における境界線や輪郭線は，複数の頂点を辺で繋いだグラフとして表現される．描画や処理に不要な頂点や辺を削減してデータをダウンサイズさせる単純化が広く利用されているが，多数の分岐点やループを持つ複雑なグラフに対しての適用が困難であった．本稿では，これら複雑なグラフの単純化方法を提案する．提案法では頂点の位置情報をグラフ信号と捉え，局所線形な信号に近似して頂点や辺を間引く手順を用いる．実験では地図境界データに対し提案法を適用し，その効果を確認する．

2. グラフ形状の単純化
空間情報学や画像工学等では，座標が定義される複数の頂点を辺で繋いだグラフデータを取り扱う．空間情報学であれば海岸線などの境界線グラフや等高線グラフ，画像工学では関心領域やオブジェクト形状などの輪郭線グラフが代表的である．これらのグラフはその形状が重要で，頂点が密であるほど正確に形状を捉えられるが，応用によっては冗長である．
例えば頂点が表示装置の解像度や処理粒度以上に密である場
合，描画や処理には不要で，保存領域圧迫や処理遅延等の原因になる．
このため，グラフから不要な頂点や辺を取り除き，選別された少ない頂点や辺で形状を近似する手法が用いられる．
以降はこの様な近似をグラフ形状の単純化と呼ぶ．DouglasPeucker のアルゴリズム（DP 法）[1] は近似誤差が減少する様に頂点を順次加える再帰的手続きで，空間情報学，画像工学の両分野で広く利用 [2, 3, 4] されている．また Teh-Chinのアルゴリズム（TC 法）[6] は 8 近傍に連なる離散曲線から重要な頂点を選び出す手法で，スケール，回転不変性を持つ改良法 [7] が提案されている．DP 法，TC 法ともに多角形や連続線分を効果的に単純化することが知られている [5]．
しかし上記の手法は多角形や連続線分のような単純な形状のグラフに適用できるが，分岐やループを多く持つ複雑なグラフに適用するのは容易ではない．例えば図 1 の点線で示すグラフは，頂点や辺を共有する多角形が複数連結して構成されている．このグラフは DP 法や TC 法を直接適用できず，多角形や連続線分に変形する必要がある．そこで各多角形毎に分離して DP 法を適用し，得られた単純化結果を重畳したのが実線のグラフである．各多角形において選別される頂点が異なるため，境界点がずれ，境界線が絡み合っている．図 1
点線のグラフを単純化するには，これらの結果を統合する必要があり，前段の DP 法の各単純化の効果を損なってしまう．
そこで本稿では，上記の様な複雑な構造を持つグラフにも適用可能なグラフ形状単純化方法を提案する．グラフの連結構造を保持したままグラフ形状を変化させ，複数の分岐やループを持つ構造に対しても適用できる単純化を実現する．

3. 局所線形近似に基づく埋め込みグラフ単純化提案手法について説明する．提案手法は，グラフを局所的に線形に整列することで，不要な頂点を容易く選択できる点に着眼する．図 2 ではグラフの連結構造を保ったまま各頂点座標を微小に動かし，1 つの直線上に多くの頂点が並ぶよう† 日本電信電話株式会社

メディアインテリジェンス研究所

図 1: DP 法を複雑なグラフに適用した結果

入力のグラフ局所線形整列させたグラフ
不要な頂点
図 2: グラフの局所線形整列
グラフ形状の局所線形整列

入力の埋め込みグラフ
࣡ୣ୫ୠ = ࣰ, ℰ, ‫۾‬

不要頂点除去局所線形整列した埋め込みグラフ
ᇱ࣡ୣ୫ୠ= ࣰ, ℰ, ‫۾‬′

単純化後の埋め込みグラフ
ᇱᇱ࣡ୣ୫ୠ
= ࣰ′′, ℰ′′, ‫۾‬′′

図 3: 提案する埋め込みグラフ単純化法の概要整列している．本稿ではこの状態を局所線形整列と呼ぶ．このグラフから分岐や角以外の頂点（図中菱型）を除去すれば，グラフを単純化できる．
以上の着眼に基づき，本稿では次の 2 段階の手順でグラフ形状の単純化を行う：1）グラフの連結構造を保持したままグラフ形状を局所線形に整列し，2）グラフから不要な頂点と辺を除去する．

3.1. 提案法の概要
提案法を説明するために，グラフに関する記号を定義する．
グラフの頂点数を N とし，頂点の集合を V = {vi }Ni=1 とする．また各頂点 vi の座標を pi ∈ RD とすると，これを並べた行列 P = [p1 , · · · , pN ]T ∈ RN ×D は全ての頂点座標を表す．また頂点間の接続関係を示す辺の集合を E ⊂ V × Vとする．一般的に，グラフ G は頂点集合 V と辺集合 E の組
G = (V, E) であるが，本稿で取り扱うのは頂点座標 P を加えた Gemb = (V, E, P) である．以降 Gemb を埋め込みグラフと呼ぶ．本稿でこれまで扱ってきたグラフは全て埋め込みグラフである．
図 3 に，提案するグラフ形状単純化方法の概要を示す．前段の処理では，埋め込みグラフ Gemb = (V, E, P) の頂点座標1
第 3 分冊Copyright © 2016 byThe Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2016（第 15 回情報科学技術フォーラム）

‫ܘ‬ଵ

ℝ஽

‫଻ܘ‬

‫ܘ‬ଷ‫ܘ‬ଵ‫଻ݒ‬‫ݒ‬ଵ࣡ = ࣰ, ℰ‫଺ܘ‬‫ݒ‬ହ଺‫ݒ‬ଷ‫ܘ‬ଵ‫ܘ‬ଶ

‫ܘ‬ସ

‫ݒ‬ଵ

‫ݒ‬ସ

݁ଵ

࣡ = ࣰ, ℰ‫ݒ‬ଷ
݁ଶ

‫ݒ‬ଵ

(a) 折れ線࣡ = ࣰ, ℰ(b) 線形
図 5: 2 辺から成る埋め込みグラフの形状

ここからは埋め込みグラフの座標をグラフ信号と捉え，局所線形整列方法を導く．埋め込みグラフの頂点座標 p1 , · · · , pNは D 次元離散信号で，グラフ G の各頂点 v1 , · · · , vN に対応している（図 4）．このため，P はグラフ G に対応するグラフ信号と見なせる．
グラフ信号処理 [8, 9] では，グラフの接続関係 E から導かれる行列を用いて，グラフ信号の解析や信号変換を行う．本稿でもこれに倣い，接続関係から求まる行列を用いて埋め込
みグラフの局所線形性を解析し，局所線形整列した埋め込みグラフへの変換 (V, E, P) 7→ (V, E, P′ ) を行う．

3.3. 行列の階数を用いた局所線形性の解析方法
埋め込みグラフ G の局所線形性を高めるために，この性質を評価する指標値を定義する．
まず簡単のため，図 5(a)(b)(c) に示す埋め込みグラフの形状を考える．各頂点 v1 , v2 , v3 の座標は p1 , p2 , p3 である．2つの辺 e1 = (v1 , v2 )，e2 = (v2 , v3 ) が作る形状は (a) 折れ線，(b) 線形，(c) 縮退の 3 つであり，rank 関数を用いると，(a) 折れ線 ⇔ rank(U) = 2(b) 線形 ⇔ rank(U) = 1(c) 縮退 ⇔ rank(U) = 0は埋め込みグラフ信 [ T]] pTp − pT0  1T 2
p2 = 1T1
p3 − pT2
pT3(1)

初期解 X(0) ∈ RN ×D ，Yv
for n ← 1, 2, · · · do ((0)X̃(n+1) ← proxτ f∈ R2×D for v ∈ V̄ を設定;)∑(n)X(n) − τ v∈V̄ LT;v Yv

X(n+1) ← ρX̃(n+1) + (1 − ρ)X(n) ;for v ∈ V̄ do(())
(n+1)
(n)
← proxσg∗ Yv + σLv 2X̃(n+1) − X(n) ;
Ỹv
(n+1)

Yv

(n+1)

← ρỸv(n)+ (1 − ρ)Yv ;である．ここでインデクス iv は頂点 v を，jv , kv は頂点 v に隣接する 2 つの頂点をインデキシングしている．この隣接差
分信号 Uv の階数和，∑∑
rank(Uv ) =rank(Lv P)(5)v∈V̄

v∈V̄

を指標値として定義すると，埋め込みグラフの局所線形性を解析できる．すなわち，式 (5) の指標値が小さい埋め込みグラフほど折れ曲がりが少なく，局所線形整列している．

3.4. 局所線形整列のための最適化問題
本稿では，式 (5) の指標値を正則化関数として使用し，局所線形整列のための最適化問題∑P′ = arg min ∥P − X∥1 + λrank(Lv X)(6)v∈V̄を定義する．目的関数第 1 項は入力埋め込みグラフ信号 P に対する忠実化項で，∥ · ∥1 : RN ×D → R は要素の絶対値和である．また λ > 0 は 2 つの項のバランスを調整するトレードオフパラメータである．最適化問題 (6) は rank 関数を含む
ため，階数に関する組み合わせ最適化となり，一般には NP困難な問題である．そこで本稿では，問題 (6) を凸緩和し，P′ = arg min ∥P − X∥1 + λである．すなわち，隣接差分信号 U の階数は，隣接する 2 辺が作る形状を判別する指標値となる．
以上を踏まえて一般の埋め込みグラフ Gemb = (V, E, P) に対し，局所線形整列性を評価する指標値を定義する．式 (1)同様に，次数（deg）が 2 の頂点 v に対して隣接差分信号Uv = Lv P, for v ∈ V̄(c) 縮退パラメータ τ, σ > 0, ρ ∈ (0, 2) を設定;

X∈RN ×Dと対応付けられる．ここで U ∈ R
号 P ∈ R3×D の，隣接差分信号で，(2)を定義する．ただし V̄ = {v ∈ V| deg(v) = 2} である．また
行列 Lv ∈ R2×N は 4 つの非零要素を持つ疎行列で，‫ݒ‬ଵ ‫ݒ‬ଶ ‫ݒ‬ଷ݁ଵ ݁ଶ

アルゴリズム 1: 局所線形整列問題 (7) の解法

3.2. 埋め込みグラフのグラフ信号表現

2×D‫ܘ‬ଵ = ‫ܘ‬ଶ = ‫ܘ‬ଷ݁ଵ࣡ = ࣰ, ℰ′
P を変化させて，局所線形整列した埋め込みグラフ Gemb=′′(V, E, P ) を生成する．生成した Gemb は，Gemb と同じ頂点 V′から不要な頂点や辺と辺 E を有する．後段の処理では，Gemb′′を除去し，単純化した埋め込みグラフ Gemb= (V ′′ , E ′′ , P′′ )を求める．各頂点や辺が不要であるかは，辺の成す角度を基準に判別する．
以降では前段の局所線形整列処理について述べ，後段の詳
細は実験の章で説明する．

−1−1ℝ஽‫ܘ‬ଷ‫ݒ‬ଷ݁ଶ‫ݒ‬ଶ‫ݒ‬ଶ

図 4: 埋め込みグラフ信号[1U = LP =0‫ܘ‬ଶ‫ܘ‬ଷ‫ܘ‬ହ‫ܘ‬ଶ ‫ݒ‬

‫ݒ‬ଶ

ℝ஽

ℝ஽

X∈RN ×D∑∥Lv X∥∗(7)v∈V̄

を解く．ここで ∥ · ∥∗ : R2×D → R は行列の特異値和であり，核ノルムと呼ばれる．核ノルムは rank 関数を最も良く近似する凸関数で，行列の低ランク性を推進する正則化関数として機能する [10]．問題 (7) の目的関数第 2 項は信号を区分抽出し核ノルムの和を取る，ブロック核ノルム [11] の一種である．
以上により，局所線形整列のための凸最適化問題 (7) を導出した．問題 (7) を解くことにより，局所線形整列したグラフ信号 P′ を得られる．

(Lv )1iv = (Lv )2iv = −1

(3)

3.5. 最適化問題の解法(Lv )1jv = (Lv )1kv = 1(4)

前節で導出した問題 (7) の解法について述べる．(7) は凸最適化問題であるため局所的最適解が大域的最適解となることが保証される．しかし目的関数の第 1, 2 項ともに勾配が不2
第 3 分冊Copyright © 2016 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2016（第 15 回情報科学技術フォーラム）連続で，勾配法により効率的に解を求められない．そこで本稿では Primal-dual splitting 法（PDS 法）[12] により，近接写像を用いた反復解法を導く．
関数 f : RN ×D → R : X 7→ ∥P − X∥1 と g : R2×D →R : Y ∑7→ λ∥Y∥∗ を定義すると，問題 (7) の目的関数はf (X) + v∈V̄ g(Lv X) と変形できる．PDS 法によれば，アルゴリズム 1 に示す反復計算により，問題 (7) の解 P′ =limn→∞ X(n) が求まる．ここで proxτ f : RN ×D → RN ×D
は関数 f の近接写像で，(Xij + τproxτ f (X) ij = Xij − τPij)

if Pij − Xij > τ
if Pij − Xij < −τotherwise(8)(a)(V1 , E1 , P1 )と計算する．また proxσg∗ : R2×D → R2×D は関数 g のル
ジャンドル変換の近接写像で，[](1)min(sY , λ)0RTproxσg∗ (Y) = QYY (9)(2)0min(sY , λ)と計算する．ただし QY ∈ R2×2 ，RY ∈ R2×D ，sY =(1) (2)[sY , sY ]T ∈ R2 は Y の特異値分解 Y = QY diag(sY ) RTYである．
またパラメータ ρ ∈ (0, 2) は収束速度を制御する加速係数である．ρ > 1 で収束が速まるが，2 の付近では返って収束が遅くなる場合があるため，本稿では ρ = 1.5 とする．続いてパラメータ τ, σ > 0 は，主変数 X と双対変数 Yv の更新速度のバランスを制御するステップサイズである．2 つの値∑は τ σ∥ v LTv Lv ∥ ≤ 1 を満たす範囲で自由に定められるが，このバランスによってアルゴリズムの収束速度が大きく変化する．そこで本稿では，バランスパラメータ α > 0 を導入し，α(10)(11)とする．
以上より，アルゴリズム 1 を用いた最適化問題 (7) の解法を導出した．本稿では，反復更新を Niter 回で打ち切り，局所線形整列した埋め込みグラフへの変換 (V, E, P) 7→ (V, E, P′ )を得る．

4. 実験
提案法の効果を確認するため，地図データを用いた単純化実験を行った．図 6 は入力に用いた埋め込みグラフである．
頂点は全て格子点上に配置され，辺の長さは全て 1 である．
図 6(a) の埋め込みグラフ (V1 , E1 , P1 ) は，頂点数と辺数が等しく |V1 | = |E1 | = 2750 で，単一の多角形から構成される．一方図 6(b) の埋め込みグラフ (V2 , E2 , P2 ) は，頂点数|V2 | = 3811，辺数 |E2 | = 3828 で，DP 法では単純化できない複雑な接続構造を持つ．
以降ではこの入力を用いた 2 つの実験を行う．初めに予備実験を行い，アルゴリズム 1 を効率的に収束させるバランス
パラメータ α と打ち切り回数 Niter を設定する．続いて提案する手法でグラフの単純化実験を行う．なおトレードオフパラメータについては，幾つかの試行から λ = 5.0 を用いた．とした場合が最も収束が速く，相対誤差が 10−6 まで減少するのに必要な反復回数は約 n = 103 回で，他と比較して 3〜1000 倍以上速かった．よって以降の実験では α = 101 ，Niter = 103 を用いる．

4.2. グラフ形状の単純化実験
グラフ形状単純化の結果を示す．図 8 は局所線形整列したグラフ (V1 , E1 , P′1 )，(V2 , E2 , P′2 ) を示している．各頂点は局所線形整列しており，特に図 8(b) の複雑な構造においても適切に整列している．一方で角は丸みを持っている．
続いて図 9 は，図 8 の結果から不要な頂点を除去して単純′′′′′′化したグラフ (V1′′ , E1′′ , P′′1 )，(V2 , E2 , P2 ) を示している．ここでは各辺同士が成す角度が 7π/8[rad] 以上となる頂点を除去している．頂点や辺の数は，|V1′′ | = |E1′′ | = 189（93.13%4.1. パラメータ設定のための予備実験

1010

目的関数値の相対誤差1√ ∑∥ v LTv Lv ∥ασ= √ ∑∥ v LTv Lv ∥τ =(b)(V2 , E2 , P2 )図 6: 実験に用いる入力埋め込みグラフ

10103第 3 分冊0-2グラフ1グラフ2-4α = 10 2
α = 10 110-6α = 10 0-1α = 1010

バランスパラメータに α = 102 , 101 , 100 , 10−1 , 10−2 を用いた場合の収束速度を示す．図 7 は反復回数に対する目的関数値の相対誤差をプロットしている．実験の中では α = 101

210-2

α = 10-80101102103104105

反復回数 n図 7: アルゴリズム 1 による目的関数値の減少

Copyright © 2016 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2016（第 15 回情報科学技術フォーラム）(a)(V1 , E1 , P′1 )(a)(V1′′ , E1′′ , P′′1 )(b)(V2 , E2 , P′2 )図 8: 局所線形整列した埋め込みグラフ(b)(V2′′ , E2′′ , P′′2 )
図 9: 単純化した埋め込みグラフ削減），|V2′′ | = 275（92.78% 削減），|E2′′ | = 282（92.63%削減）となった．
以上より，提案手法はグラフ構造を問わずにグラフ形状を単純化できることを確認した．各頂点を局所線形に整列できたが，角の部分は丸められてしまう．これは式 (6)の rank 関
数を式 (7) の核ノルム ∥ · ∥∗ で緩和したために，低ランク性の制約が弱まったことが原因と考えられる．非凸なシャッテン p ノルム [13] を用いて低ランク性を高めることで改善の可能性がある．

[4] F. He, Q.Qiu and J. Fang, “An Eﬀective Method for RiverGeneralization,” Proc. 21st Int. Conf. on Geoinformatics,pp.1–4, 2013.

5. まとめ[5] E.R. White, “Assessment of Line-generalization Algorithms Using Characteristic Points,” The American Cartographer, vol.12 no.1, pp.17–28, 1985.
[6] C.H. Teh and R.T. Chin, “On the Detection of Dominant
Points on Digital Curves,” IEEE Trans. Pattern Anal.
Mach. Intell., vol.11, no.8, pp.859–872, 1989.
[7] N. Ansari and K. Huang, “Nonparametric dominant point
detection,” Pattern Recogn., vol.24, pp.849–862, 1991.
[8] D. Shuman, S. Narang, P. Frossard, et al., “Signal Processing on Graphs: Extending High-dimensional Data Analysis to Networks and Other Irregular Data Domains,” IEEESignal Process. Mag., vol.30, no.3, pp.83–98, 2013.

本稿では，複雑なグラフにも適用できる単純化方法を提案した．グラフの連結構造を保持したまま形状を局所線形に整列させることで，分岐やループを持つ構造においても容易く不要な頂点を除去できた．実験では地図データに対し提案法を適用し，その効果を確認した．

[9] S. Chen, A. Sandryhaila, J.M.F. Moura, et al., “Signal Recovery on Graphs: Variation Minimization,” IEEE Trans.
on Signal Process., vol.63, no.17, pp.4609–4624, 2015.

参考文献[10] M. Fazel, Matrix Rank Minimization with Applications,Ph.D. dissertation, Stanford University, 2002.

[1] D. Douglas and T. Peucker, “Algorithms for the Reductionof the Number of Points Required to Represent a DigitizedLine or Its Caricature,” Cartographica: Int. J. Geogr. Inf.
Geovisualization, vol.10, no.2, pp.112–122, 1973.

[11] S. Ono, T. Miyata, I. Yamada et al., “Missing Region
Recovery by Promoting Blockwise Low-rankness,” Proc.
2012 IEEE Int. Conf. Acoust. Speech. Signal Process., pp.
1281–1284, 2012.

[2] U. Ramer, “An Iterative Procedure for the Polygonal Approximation of Plane Curves,” Comput. Gr. Image Process. vol.1, no.3, pp.244–256, 1972.

[12] L. Condat, “A Primal-Dual Splitting Method for Convex
Optimization Involving Lipschitzian, Proximable and Linear Composite Terms,” J. Optim. Theory Appl., vol.158,no.2, pp.460–479, 2013.

[3] A. Orzan, A. Bousseau, P. Barla, et al., “Diﬀusion Curves:a Vector Representation for Smooth-shaded Images,’ Commun. ACM, vol.56, no.7, pp.101–108, 2013.

[13] L. Kong, N. Xiu, “Exact Low-rank Matrix Recovery via
Nonconvex Schatten p-minimization,” Asia Pac. J. Oper.
Res., vol.30, no.3, 2013.

4第 3 分冊

Copyright © 2016 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.