数理解析研究所講究録
第 1799 巻 2012 年 111-117111

ラベル選択付最小連結全域部分グラフ問題と化学構造式 OCR への応用
藤芳 明生

鈴木 昌和

茨城大学工学部情報工学科
fuj iyosi@mx.ibaraki.ac.jp

九州大学大学院数理学研究院

msuzuki@kyudai.jp

概要

本稿では，ラベル選択付最小全域木問題を拡張したラベル選択付最小連結全域部分グラフ問題を考える．最小連結全域部分グラフ問題とは，各辺に「繋ぐ場合の重み」と「繋がない場合の重み」の 2 種類を与え，選ばれた辺の「繋ぐ場合の重み」の合計と選ばれなかった辺の「繋がない場合の重み」の合計の和が最小となるような連結全域部分グラフを求める問題である．ラベル選択付最小全域木問題が NP 困難であるため，この問題を拡張したラベル選択付最小連結全域部分グラフ問題も同様に W 困難である．しかし，化学構造式 OCR の認識精度向上に応用するためには，この問題を現実的な時間内に解く必要がある．そこで，入力のグラフの tree-width を 2 以下に制限した場合を考え，線形時間で動作する非常にシンプルなアルゴリズムを提案する．

1

はじめに

日本では，諸外国と同じように，特許申請書は出願から 1 年 6 ケ月後に自動的に公開される．2008 年には，312,443 件の特許申請書が公開された．これらの公開された特許申請書は，特許庁から DVD–ROM で購入することも可能であり，また，特許電子図書館 [1] のWeb ページから自由に検索，ダウンロードすることも可能である．特許申請書のほとんど部分は XML フオーマットの文字列であるが，化学構造式，数式，図，表は TIFF 画像として収録されている．2008 年に公開された特許申請書を調べたところ，化学構造式は，229,969枚の TIFF 画像として収録されていた．化学・製薬産業において，特許中の化学構造式の包括的な検索は必須である．そのため，特許中の化学構造式を含む画像を，すばやく低コストで電子化する化学構造式 OCR の開発が求められている．本稿では，化学構造式 OCR[2,3]の認識精度向上に応用するため，ラベル選択付最小連結全域部分グラフ問題を考える．

ラベル選択付最小連結全域部分グラフ問題は，ラベル選択付最小全域木問題 [4,5] を拡張することで得られる．この問題の例を図 1(a) に示す．ラベル記号の集合は，$\Sigma=\{a, b, c, d\}$である．頂点は点線の長方形で示されており，それぞれの頂点は少なくとも 1 つ以上のラベル候補を持っている．ラベル候補はラベル記号を円で囲って示されている．重み付き辺はラベル候補どうしを結んでおり，各辺には左側に記された「繋ぐ場合の重み」と右側の括弧の中に記された「繋がない場合の重み」の 2 種類の重みが与えられている．2 つの頂点のラベル候補のいずれかの間に重み付き辺が存在するならば，その頂点間のすべてのラベル候補の問には重み付き辺が存在するものとする．例では，いくつかのラベル候補の組み合わせには

112

(c):

図 1: (a) ラベル選択付最小連結全域部分グラフ問題の例，(b) ラベル選択付最小連結全域部分グラフ，(C) 基礎グラフ．

辺が記されていないが，そこには，「繋ぐ場合の重み」が無限大で「繋がない場合の重み」が0 であるような辺が省略されているものと考える．この問題に対するラベル選択付最小連結全域部分グラフを図 1(b) に示す．それぞれの頂点から，正確に一つずつラベル候補が選択されており，選ばれた辺によって連結全域部分グラフが構成されている．選ばれた辺の「繋ぐ場合の重み」の合計と選ばれなかった辺の「繋がない場合の重み」の合計は，すべてのラベル選択と連結全域部分グラフの組み合わせの中で最小となっている．更に，図 1(C) に示すような，基礎グラフという概念も導入する．基礎グラフとは，ラベル候補間に重み付き辺が存在する頂点間を辺で結ぶことでできるグラフである．
ラベル選択付最小全域木問題が NP 困難であるため，この問題を拡張したラベル選択付最小連結全域部分グラフ問題も同様に NP 困難である．ラベル選択付最小連結全域部分グラフ問題において，繋がない場合の重みがすべて O ならば，なるべく繋がない方が良いので，ラベル選択付最小連結全域部分グラフはサイクルを持つことはない．つまり，ラベル選択付最小全域木問題を解いたことになる．
化学構造式 OCR の認識精度向上に応用するためには，この問題を現実的な時間内に解113
表 1: ChEMBL 中の化合物の tree-width.

く必要がある．そこで，基礎グラフの tree-width を 2 以下に制限した場合を考え，線形時間で動作する非常にシンプルなアルゴリズムを提案する．本稿が提案するアルゴリズムは，tree-width が 2 以下のグラフにしか対応できないが，tree-width が 3 以上の場合であっても，一部の辺の処理を後回しにし，tree-width が 2 以下の部分グラフに対してアルゴリズムを適応すれば，化学構造式 OCR への応用には十分であると考える．医薬品及び医薬品候補化合物に限定すれば，それらグラフ表現の tree-width は十分に小さいことが知られている．表 1に，ChEMBL[6] に登録されている 635,933 個の医薬品及び医薬品候補化合物の tree–widthを示す．ほとんどの化合物の tree-width は 2 ないし 3 以下となっていることが確認された．

2諸定義
本章では，本論文で利用される記法，定義を与えるとともに，問題の形式的な再定義を行う．

グラフとは，順序対 $G=(V,E)$ のことである．ここで， は頂点の有限集合，異なる頂$V$点の組を辺と呼び， は辺の有限集合である．グラフが連結であるとは，グラフ上の任意の$E$2 頂点間に道が存在することである．グラフ $G’=(V’,E’)$ がグラフ
$V’=V$ かつあるとは，$E’\subseteq E$$G$の全域部分グラフでとなることである．連結であるような全域部分グラフを連結全域部分グラフと呼ぶ．

をラベルの有限集合とする．本稿では， は最初から決められた定数であると考え$R+$る． を正実数全体の集合とする．グラフ $G=(V,E)$ の重み関数とは，部分関数 :$\Sigma$$|\Sigma|$$w$のことであり，すべての$v_{1},v_{2}\in V$

ならば $w(v_{1},v_{2}, l_{1}, l_{2})=w(v_{2},v_{1},l_{2}, l_{1})$となり，$V\cross V\cross\Sigma\cross\Sigmaarrow R+\cup\{0,\infty\}$

いて，$\{v_{1},v_{2}\}\in E$$w(v_{1},v_{2},l_{1},l_{2})$

定義 1 $G=(V,E)$ をグラフ，$w$ と$\overline{w}$$\overline{w}$$l_{2}\in\Sigma$$\sigma$につならば: $Varrow\Sigma$ のことである．

を $G$ の重み関数とする．
$w$ を繋ぐ場合の重み関数，を繋がない場合の重み関数と呼ぶ． のラベル割り当て$G$$\sigma$に対する連結全域部分グラフ$G’=(V,E’)$ の重ざを次で定義する．
$w(G’)$$l_{1},$$\{v_{1},v_{2}\}\not\in E$は未定義となる． のラベル割り当てとは，関数
$G$と

$=$
$\{v_{1},v\}\in E’\sum_{2}w(v_{1},v_{2},\sigma(v_{1}), \sigma(v_{2}))$$+$$\sum_{\{v_{1},v2\}\in E-E’}\overline{w}(v_{1},v_{2},\sigma(v_{1}), \sigma(v_{2}))$.

114$w$ と定義 2 $G=(V,E)$ をグラフ，を $G$ の重み関数とする．ラベル選択付最小連結全域部分グラフ問題とは，連結全域部分グラフ $G’=(V,E’)$ と $G$ のラベル割り当て の組み合$\overline{w}$$\sigma$$G’$ の重さが最小となるものを見つける問題である．
わせ中で，3NP 困難性

ラベル選択付最小連結全域部分グラフ問題の NP 困難性は，既に NP 困難性が証明されているラベル選択付最小全域木問題 [4,5] をこの問題に還元することで得られる．
定理 1 ラベル選択付最小連結全域部分グラフ問題は $NP$ 困難である．
$w$ を繋ぐ場合の重み関数とする．繋がない場合の重み関数
証明 $G=(V,E)$ をグラフ，は，ならば，すべてのについてらば，すべての$\{v_{1},v_{2}\}\in E$$l_{1},l_{2}\in\Sigma$$l_{1},l_{2}\in\Sigma$について $\overline{w}(v_{1},v_{2},l_{1},l_{2})=0,$なは未定義となるように定義する．連結全を，すべての連結全域部分グラフと のラ$\overline{w}(v_{1},v_{2},l_{1},l_{2})$域部分グラフ $G’=(V, E’)$ とラベル割り当て$G’$ の重さが最小となるものとする．
ベル割り当ての組み合わせ中で，$\sigma$$\overline{w}$$\{v_{1},v_{2}\}\in E$$\overline{w}$$G$の定義より，もし， にサイクルが存在したとすると，サイクル中の辺のどれか 1 つ$G’$を取り除いてできる連結全域部分グラフの (ラベル割り当て$\sigma$に対する) 重さは同じはずである．このとき，取り除かれる辺は，繋ぐ場合の重みも繋がない場合の重みも 0 でなくてならないことを注意する．もしそうでなければ， の重さが最小であるという仮定に矛盾する．よって，重さを変えることなくサイクル中の辺を取り除くことができるので，$G’$ と同$G’$

じ重さの全域木 $T$ を得ることができる．
$w$ を重み関数とした時のラベル選択付最小全域木問
全域木 $T$ は，$G=(V,E)$ をグラフ，題の解である．ゆえに，既に NP 困難性が証明されているラベル選択付最小全域木問題を，口ラベル選択付最小連結全域部分グラフ問題に還元することができた

4線形時間アルゴリズム
本章では，tree-width が高々2 のグラフに対する線形時間アルゴリズムを紹介する．
任意の tree-width が高々2 のグラフは，次に示す変形規則によって単一頂点のグラフに縮約できることが知られている [7]. (図 2 も見よ．)

1. グラフに頂点辺$\{v_{1},v_{2}\}$$v_{2}$と辺が存在し，正確に 1 つの辺$v_{2}$が存在し，正確に 2 つの辺を取り除き，新しい辺に繋がっているとき，頂点$\{v_{1},v_{2}\},$ $\{v_{2},v_{3}\}$$\{v_{1},v_{2}\},$ $\{v_{2},v_{3}\}$

3. 規則 2 によって，頂点しい辺$\{v_{1},v_{2}\}$$v_{2}$とを取り除く．

2. グラフに頂点点$v_{2}$$\{v_{1},v_{3}\}$$v_{1},v_{2}$を加える．

$\{v_{1},v_{3}\}$に繋がっているとき，頂を加える．の間に多重辺ができてしまったら，多重辺を取り除き，新115$’\backslash ’!$$”\backslash /$1.

$rightarrow”$$\supset$$o_{\mathcal{V}_{1}}$$v_{I}$$v_{-}$$\backslash \backslash \backslash !$$”\backslash ,$

2.

$!$

$\backslash ’\backslash \backslash !$$\backslash ’\backslash ,$$\supset$$\prime\prime\overline{v_{I}v_{-},v_{3}}$$rightarrow \mathcal{V}_{1}\mathcal{V}_{-}$’

3.

.

$!$

’

$\prime\prime\backslash \ell\prime l\backslash \prime\prime^{l\backslash }\Leftrightarrow_{\mathcal{V}_{2}}^{\backslash }v_{1}$$\supset$$’.\prime\prime,’\prime\prime\prime’rightarrow^{\backslash \prime}\backslash \prime v_{1}’ v_{-}\backslash$

図 2: 変形規則．
$\Sigma$をラベル記号の集合とする．以下のアルゴリズムは，グラフ $G=(V, E),$$G$の重み関を受け取り， の tree-width が 2 以下であれば，連結全域部分グラフの最小の重さを返し，tree-width が 3 以上であれば，reject を返す．

数 $w,$$G$$\overline{w}$Function 線形時間アルゴリズム
Input: グラフ $G=(V,E),$の重み関数 $w,$
Output: 連結全域部分グラフの最小の重さ，または，reject$G$$\overline{w}$1: for all $v\in V$ do
2:

for all3:$a\in\Sigma$

do$w’(v, a):=0$

end for
5: end for
4:

6: while $|V|>1$ do
7:
次数が 1 または 2 の頂点 $v_{2}\in V$ を見つける

8:
9:
10:
11:

if

$v_{2}$の次数が 1 で，1 つの辺$\{v_{1}, v_{2}\}$に繋がっている then$V:=V-\{v_{2}\}$$E:=E-\{\{v_{1},v_{2}\}\}$

for alldo$a\in\Sigma$

12:$\min:=\infty$

13:
14:

for alldoif $\min>w(v_{1}, v_{2}, a, b)+w’(v_{2}, b)$ then15:$\min:=w(v_{1}, v_{2}, a, b)+w’(v_{2}, b)$$b\in\Sigma$

17:

end ifend forls:$w’(v_{1}, a):= \min$

16:

19:

20:
21:

end forelse if の次数が 2 で，2 つの辺$v_{2}$$V:=V-\{v_{2}\}$22:$E:=E’-\{\{v_{1}, v_{2}\}, \{v_{2},v_{3}\}\}$

23:

for all$a\in\Sigma$

do$\{v_{1},v_{2}\},$ $\{v_{2},v_{3}\}$に繋がっている then

116
24:
25:
26:
27:
28:
29:
30:
31:
32:

for all$c\in\Sigma$

do

34:

minlmin2
dofor allthen$minl>w(v_{1},v_{2},a,b)+w’(v_{2},b)+w(v_{2},v_{3},b,c)$ifminl $:=w(v_{1},v_{2},a,b)+w’(v_{2},b)+w(v_{2},v_{3},b, c)$end ifif $min2>w(v_{1},v_{2},a,b)+w’(v_{2},b)+$ th $(v_{2},v_{3},b,c)$ thenmin2 $:=w(v_{1},v_{2},a,b)+w’(v_{2},b)+\overline{w}(v_{2},v_{3},b,c)$
end ifif $min2>$ th $(v_{1},v_{2},a,b)+w’(v_{2},b)+w(v_{2},v_{3},b,c)$ then35:

min2: $=\overline{w}(v_{1},v_{2},a,b)+w’(v2,b)+w(v_{2},v_{3},b,c)$

33:

36:

37:

38:
39:
40:
41:

$:=\infty$$:=\infty$$b\in\Sigma$

end ifend for
if $\{v_{1},v_{3}\}\in E$ then$minA;=w(v_{1},v_{3},a,c)+ \min 1$$minB:=w(v_{1},v_{3},a,c)+ \min 2$$minC;= \overline{w}(v_{1},v_{3},a,c)+\min 1$$:= \min(minA,minB,minC)$

42:$w(v1^{V_{3},a,c)}$

43:
44:
45:

$w(v3,v_{1},c,a):=w(v_{1},v_{3},a,c)$

46:
47:
48:
49:
50:
51:

$\overline{w}(v_{1},v_{3},a,c):=$万 $( vl,v_{3},a,c)+\min 2$

di $(v_{3},v_{1},c,a):=\overline{w}(v_{1},v_{3},a,c)$

else$E:=E\cup\{\{v_{1},v_{3}\}\}$$w(v_{1},v_{3},a,c):= \min 1$$w(vv,c,a):=w(v_{1},v_{3},a,c)$$\overline{w}(v_{1},v_{3},a,c):=\min 2$$\overline{w}(v_{3},v_{1},c,a):=\overline{w}(v_{1},v_{3},a,c)$

end ifend for53:
end for54:
else if 条件を満たす $v_{2}\in V$ が存在しなかった then55:
return reject56:
end if57:
58: end while52:

59: $v\in V$ とする

60: $\min:=\infty$
do
61: for allthen$\min>w’(v,a)$if
62:$\min:=w’(v,a)$63:
end if64:$a\in\Sigma$

117
65: end for
66: return $\min$5

まとめと今後の課題
化学構造式 OCR の認識精度向上に応用するため，ラベル選択付最小連結全域部分グラフ問題を考案した．ラベル選択付最小連結全域部分グラフ問題は，NP 困難であることを示した．しかし，入力のグラフの tree-width が 2 以下ならば，線形時間で動作する非常にシンプルなアルゴリズムの提案を行った．

現在，提案アルゴリズムを実装し，化学構造式 OCR を開発中である．近日，プロジェク
トのホームページ [8] で公開する予定である．

今後は，化学構造式生成文法を開発し，文法的特長量なども認識精度向上に利用することを検討する．

参考文献[1] 特許電子図書館．http $://www$ . ipdl. inpit. go. jp/.

[2] Akio Fujiyoshi, Koji Nakagawa, and Masakazu Suzuki. Robust method of segmentation
and recognition of chemical structure images in cheminfty. In Pre-Proceedings of the9th IAPR International Workshop on Graphics Recognition (GREC 2011), 2011.
[3] Daniel Karzel, Koji Nakagawa, Akio Fujiyoshi, and Masakazu Suzuki. Inconsistencydriven chemical graph construction in cheminfty. In Pre-Proceedings of the 9th IAPR
Intemational Workshop on Graphics Recognition (GREC 2011), 2011.
[4] 藤芳明生，鈴木昌和．ラベル選択を有する最小全域木問題．2OO9 年度冬の LA シンポジ
ウム．

[5] Akio Fujiyoshi and Masakazu Suzuki. Minimum spanning tree problem with label
selection. IEICE Trans. Inf. ; Syst., Vol. E94-D, No. 2, pp. 233-239, 2011.
$\epsilon$[6] ChEMBL. https $://www$ . ebi. ac. $uk/$ chembl/.
[7] Stefan Arnborg and Andrzej Proskurowski. Characterization and recognition of partial
3-trees. SIAM J. Algebraic Discrete Methods, Vol. 7, No. 2, pp. 305-314, 1986.
[8] ChemInfty. http $://www$ . inftyproj ct. org $/j$ p/ChemInfty/.
$e$