電子情報通信学会論文誌 2013/7 Vol. J96–D No. 7を意味しているわけではない．実際，文献 [2] で指摘
大局的特徴に対する DP マッチングされているとおり，例えば “0” の筆記では，筆記者は稔†（正員：シニア会員）

始終端間の関係を意識している．したがって筆記は局森

内田 誠一††（正員：シニア会員）
坂野

DP Matching for Global Features
Minoru MORI† , Seiichi UCHIDA†† , Senior Members,and Hitoshi SAKANO††† , Member††††††

所特徴だけは表現できない．
提案手法の着眼点は，本来任意の 2 時刻間で定義さ鋭†††（正員）れる大局的特徴に対し，適当な制限を加えることで，DP マッチングでも扱えるようにすることである．具
体的には，大局的特徴群の中から，全順序性をもった

日本電信電話株式会社 NTT コミュニケーション科学基礎研究所，厚木市

NTT Communication Science Laboratories, NTT Corpora-部分集合を事前に最適選択し，その順序に従った形式

tion, Atsugi-shi, 243–0198 Japan的なマルコフ性によって，DP マッチングアルゴリズ

九州大学大学院システム情報科学研究院，福岡市

Kyushu University, Fukuoka-shi, 819–0395 Japanムを再構築する．なお，この最適選択についても，DP

日本電信電話株式会社 NTT コミュニケーション科学基礎研究所，京都府を利用する．すなわち本論文では，マッチングとそのNTT Communication Science Laboratories, NTT Corpora-事前準備という異なる 2 局面において，それぞれ DP

tion, Kyoto-fu, 619–0237 Japanを利用することに注意する．オンライン数字データを用いた評価実験で，提案手法により認識精度を向上可
あらまし 時系列データの離れた時刻間の関係を抽出した大局的特徴を利用可能な DP マッチングの処理能であることを確認する．

2. 大局的特徴を用いた DP マッチングスキームを提案する．具体的には，任意の 2 時刻間で提案手法は，三つの要素技術からなる．一つ目は，定義される大局的特徴群から，マルコフ性を満たしつ文字からの大局的特徴抽出処理である．二つ目は，大つ識別能力も備える特徴を選択することで，大局的特局的特徴を用いた DP マッチングである．三つ目は，徴への DP マッチング適用を実現する．オンライン数

上記 DP マッチングで利用可能な大局的特徴の選択処

字データを用いた評価実験で，提案手法の有効性を確理である．以下，順に説明する．

2. 1 大局的特徴の抽出認した．
キーワード DP マッチング，特徴抽出，特徴選択，大局的構造，オンライン文字認識

大局的特徴として，筆者らが提案した特徴抽出法 [2]を用いる．この大局的特徴は，ストローク上の任意の1. ま え が き

2 点間の相対ベクトルとして定義される．以下，全て

本論文では，時系列パターンの認識における離れたのパターンは I 点にリサンプリングされているもの

2 時刻間の関係を抽出した大局的特徴（例えば [1], [2]とする．このとき，I C2 の 2 点間の組合せから，相対等）の一利用形態について提案する．非マルコフ的特ベクトル (dx, dy) を大局的特徴として計算する．ここ

徴ともいえる同特徴は，パターンのマルコフ性を仮定

で，I C2 = I(I − 1)/2 個の大局的特徴の中には，従来した非線形照合処理である通常の DP（動的計画法）の局所方向がサブセットとして含まれる．この大局的マッチングや HMM では直接利用できない．このた特徴は，シンプルだが各文字クラスの特徴的な形状をめ，大局的特徴はその重要性の反面，従来ほとんど利表現する高い能力があり，文字ストローク上の時間的用されていない．本論文では，大局的特徴の有効性をに離れた 2 点間の関係を定義することが可能である．

明らかにするとともに，その組込みを可能とした新たな DP マッチングの枠組みを提案する [3]．

2. 2 大局的特徴を用いた DP マッチング
図 1 に，大局的特徴を用いた DP マッチングの処

以下本論文では，時系列パターン認識の例として，理概要を示す．ここで，P は参照パターン，E は入力

オンライン文字認識を用いて議論する．オンライン文パターンである．参照パターン P で使用される大局字認識の従来法においても，ストローク上の各点の xy的特徴は事前に定められており，k 番目の大局的特徴

座標 [4] や隣接する 2 点間の相対ベクトルから定義さを定義する始端及び終端を各々Sk , Tk (k = 1, . . . , K)れる局所方向 [5], [6] などの局所的すなわちマルコフ的とする．ここで，K は使用される大局的特徴の個数で特徴の利用が主であった．しかしこれらの特徴の利用ある．このとき，大局的特徴を用いた DP マッチング

は，DP マッチングや HMM を用いるための便宜的なでは，P 上の大局的特徴 Sk , Tk の E における対応先ものであり，大局的特徴に対する局所的特徴の有用性

s(k), t(k) を順次最適化する．すなわち，従来の DP1654

電子情報通信学会論文誌

c 一般社団法人電子情報通信学会 2013
D Vol. J96–D No. 7 pp. 1654–1657 レ タ ー

ここで，dg (k) は k 番目の大局的特徴間の距離値であり，以下で定義される．

dg (k) = d(S(k) − T (k), s(k) − t(k))(2)

また，dxy (k) は k 番目の大局的特徴を定義する両端点の xy 座標特徴間の距離値

dxy (k) = d(S(k), s(k)) + d(T (k), t(k))(3)

である．d(, ) はユークリッド距離を表す．重みパラ
図1

大局的特徴を用いた DP マッチングによる対応付けの例
Fig. 1 Procedure of DP matching using global feature.

メータ α は，両距離値を結合する重みパラメータである．最小の値となる D が，入力パターンと着目参照パターン間の距離値として用いられる．なお，本 DPマッチングは，k − (s, t) の三次元空間での最適経路問
題を扱うことになる．計算量はたかだかこの空間のサイズである O(KI 2 ) となる．
最小化の際の制約条件は，以下のとおりである．

2. 3 で述べる特徴選択法を用いれば，図 2 (a) のように Sk−1 = Sk 若しくは Tk−1 = Tk のどちらかが成り立つ．今，図 1 のように前者が成り立つ場合，その同
図 2 DP マッチングで許容される大局的特徴の例
Fig. 2 Examples of the selection results for the globalfeature.

マッチングが始端から終端の時間順序に沿った最適化であるのに対し，大局的特徴を用いた DP マッチング
では始端及び終端の両方向からの同時最適化となる．
なお，類似の最適化処理は，文献 [7] にも見られる．

DP マッチ ン グ に よ る 大 局 的 特 徴 の 最 適 対 応付 け の ア ル ゴ リ ズ ム は ，以 下 の と お り で あ る ．
最 適 化 す べ き 変 数 集 合 は ，図 1 に 示 す よ う に ，{(s(k), t(k)) | k = 1, . . . , K} である．これら変数集合
を，(s(1), t(1)), . . . , (s(k), t(k)), . . . , (s(K), t(K)) の順に逐次決定する過程を考える．目的関数は，対応する特徴間のユークリッド距離 K 個の総和である．それを最小化するべく各変数の値すなわち対応関係を決定することになる．
ここで，図 2 (a) のように大局的特徴 (Sk , Tk ) が設定されていれば，(s(k), t(k)) の決定には (s(k − 1), t(k −1)) の値しか影響しない．したがって，この決定過程はマルコフ決定過程となり，その最適解は DP で求まる．具体的には，以下の Sk 及び Tk を制御変数とする制約付き最小化問題を DP を用いて解くことになる．

D = minK
k=1(α · dg (k) + (1 − α) · dxy (k))(1)一性を対応先でも保持するべく，s(k − 1) = s(k) と制約する．更に，t 側については，DP マッチングで広く用いられる単調連続性に倣い，0 ≤ t(k − 1) − t(k) ≤ 2と制約する．逆の場合も同様である．
ところで，図 2 (c) のように大局的特徴が設定されると，上記の DP 最適化が不可能となる．これは k の決定に k − 1 以外の値が影響してしまい，マルコフ決定過程とならないことから明らかである．このように，
全 I(I − 1)/2 個の大局的特徴，若しくは任意に選択した大局的特徴群を，参照パターンとして利用可能なわけではない．利用可能なのは，全順序性を保った大局的特徴の列，すなわち図 2 (a) 及び (b) の例のように，両端点が始端及び終端から単調に増加及び減少するような場合に限られる．なお，2. 3 で述べる方法に基づいて極力多くの大局的特徴を用いようとする場合，使用されないサンプル点が P 上に存在する図 2 (b) のような場合は生じない．

2. 3 大局的特徴の最適な特徴選択
本節では，参照パターンとして設定可能な大局的特徴の選択法について述べる．選択に際しては，第一に，前節で述べたようにマルコフ性制約を満たす必要がある．第二には，その制約を満たす範囲で，識別に有効な特徴をなるべく多く選択する必要がある．後者について本論文では，各大局的特徴のクラス間分離度（F比）を用いる．F 比は，クラス内分散とクラス間分散
1655

電子情報通信学会論文誌 2013/7 Vol. J96–D No. 7の比として求められ [8]，F 比が大きいほどクラス間この最適特徴選択問題も，DP を用いて解ける．その概要は，図 3 の最適経路問題として説明される．同図の分離度が高く識別に有効である．
以上により，大局的特徴の選択問題は，全 I(I −1)/2の平面上の格子点 (Sk , Tk ) には，大局的特徴 (Sk , Tk )個の大局的特徴から，マルコフ的制約すなわち全順序の F 比が与えられている．そして，パターン P の始性を満たしながら，それらの F 比の合計を最大とする端と終端を結ぶ大局的特徴 (S1 , T1 ) = (1, I) を開始点大局的特徴の列を求める問題となる．全順序性は，以として，Sk = Tk − 1 を満たす状態（図中の対角線）下の制約条件で表現される．に到達する経路のうちで，経路上の F 比の合計値が最Sk ≥ Sk−1 , Tk ≤ Tk−1for all k(4)また，fk を k (= 1, . . . , K) 番目の大局的特徴の F 比としたとき，識別に有効な特徴をなるべく多く選択することは，目的関数 J =K

k=1 fk =K

k=1 f (Sk , Tk )を {Sk , Tk } 及び K について最大化することに相当する．ところで，なるべく多く特徴を選択するということは，なるべく密に大局的特徴を用いることに相当す大となるものを見つける問題となる．ただし，制約条件 (5) があるため，S を一つ増やすか，T を一つ減らすという進み方となる．このように，特徴選択問題は極めて一般的な最適経路問題に帰着し，一般的な DPにより O(I 2 ) の計算量で最適解が得られる．

3. 評 価 実 験
3. 1 実 験 条 件提案手法の有効性を評価した．評価データには，る．したがって，最適解として図 2 (b) のような大局UNIPEN データベース [9] のオンライン数字データを的特徴列に含まれないサンプル点がある状況はあり得使用した．“0”-“9” の各クラスで，2,000 サンプルをず，同図 (a) のような解が必ず得られる．すなわち，
条件 (4) は実質的に以下と等価となる．

Sk = Sk−1 , Tk = Tk−1 − 1, or
Sk = Sk−1 + 1, Tk = Tk−1

学習データに，学習データとは異なる 2,000 サンプルを評価データとして使用した．前処理として，各文字(5)を縦横比を保持しつつ 128 × 128 の大きさに正規化し，正規化後の文字パターンを I = 40 となるようにリサンプリングした．最終的に，前処理後の文字パターンから，局所的特徴として I 個の xy 座標特徴，及びI C2 = I(I − 1)/2 個の大局的特徴を抽出した．識別関数には，1-Nearest Neighbor 法を用いた．

3. 2 実 験 結 果
図 4 に，数字 10 クラスの評価データに対する認識結果を示す．縦軸が認識率を，横軸が重みパラメータα の値を表す．ここで，α = 0 のときが従来手法のみで得られる認識率である．図 4 から，提案手法と従来

図 3 大局的特徴を用いた参照パターンに利用可能な特徴
選択処理の概要
Fig. 3 Feature selection procedure for reference pattern using global features.

1656

図 4 重みパラメータ α 別の認識精度
Fig. 4 Recognition accuracy (vs. α).

レ タ ー

手法の統合により，従来手法の 94.5% から 95.5% にいて評価実験では，提案手法は従来の局所的特徴を用改善している．各クラス別の分析では，提案手法の利いた DP マッチングと協調することで認識精度が向上

用により，クラス “1” での改善 (88% → 90.5%)，ク可能なことを示した．今後の課題には，大局的特徴とラス “4” での改善 (89.5% → 92%)，及びクラス “7”

して 3 点間以上の関係を記述した特徴の検討，及び提での改善 (96% → 98.5%) が顕著であった．この改善案手法のアルファベットやかな・漢字等の数字以外の理由には，例えばクラス “1” 及び “7” におけるスト文字における評価がある．
文

ロークの開始点付近における類似形状間の差が，より強調されたことが挙げられる．

[1]

information in online handwriting representation,”

一方，クラス “5” では認識率が低下した (97.5% →95.5%)．その理由には，クラス “5” では，ストローク

ICIAP’09, pp.132–142, 2009.
[2]

順が異なるサンプルが散見され，提案した大局的特徴が従来の xy 座標特徴より，ストローク順の変動に対[3]

森 稔，内田誠一，坂野 鋭，“大局的構造情報を用いたオンライン数字認識，” 信学技報，PRMU2011-102, 2011.
森 稔，内田誠一，坂野 鋭，“大局的構造情報に対するDP マッチング，” 画像の認識・理解シンポジウム，IS1-47,して影響を受けやすいことがある．また，提案手法に対する重みを大きくした場合には，認識率が低下し従献

S. Izadi and C.Y. Suen, “Integration of contextual

2012.
[4]

K. Ikeda, T. Yamamura, Y. Mitamura, S. Fujiwara,

来手法を下回る認識性能しか得られなかった．この理

Y. Tominaga, and T. Kiyono, “On-line recognition

由は，クラス “5” における認識率の低下原因として述of hand-written characters utilizing positional andstroke vector sequences,” Pattern Recognit., vol.13,

べたように，大局的特徴がストローク順の変動に対して影響を受けやすく，重みを大きくするにつれて，そno.3, pp.191–206, 1981.
[5]の影響が大きくなったためである．

state of the art in on-line handwriting recognition,”

4. む す び
大局的特徴を利用可能とする DP マッチングの処理

IEEE Trans. Pattern. Anal. Mach. Intell., vol.12,
no.8, pp.787–808, 1990.
[6]

スキームを提案した．時系列データの離れた時刻間のpp.115–125, 2006.
[7]

誤った対応付けを回避できる可能性がある．提案したDP に基づいた特徴選択手法は，大局的特徴群から時能とする．選択した大局的特徴を用いた DP マッチン

上田修功，間瀬健二，末永康仁，“弾性輪郭モデルとエネ” 信学論（D-II），
ルギー最小化原理による輪郭追跡手法，
vol.J75-D-II, no.1, pp.111–120, Jan. 1992.

[8]

石井健一郎，上田修功，前田英作，村瀬いパターン認識，オーム社，1998.

[9]

I. Guyon, L. Schomaker, R. Plamondon, M. Liber-間軸上の不整合を回避しつつ，各特徴の F 比を用い，より識別性能の高い特徴を参照パターンとして選択可

C. Bahlmann, “Directional feature in online handwriting recognition,” Pattern Recognit., vol.39, no.1,

関係を抽出した大局的特徴は，従来のマルコフ性の制約下における局所情報を用いた際にしばしば生じる

C.C. Tappert, C.Y. Suen, and T. Wakahara, “The洋，わかりやすman, and S. Janet, “Unipen project of on-line dataexchange and recognizer benchmarks,” ICPR’94,

グは，文字パターン間の大局的な対応付けに基づいた

pp.29–33, 1994.

マッチングを実現する．オンライン数字パターンを用（平成 24 年 11 月 28 日受付，25 年 3 月 7 日再受付）

1657