Vol. 45

No. 12

Dec. 2004

情報処理学会論文誌

推薦論文

弾性マッチングと固有変形を用いたオンライン文字認識
三

苫

寛

人†

内

田

誠

一†

迫

江

博

昭†

DP マッチングなど，いわゆる弾性マッチングに基づくオンライン文字認識においては，合わせ過ぎによる誤認識が発生する．たとえば，入力パターンが “1” であっても，マッチングによって水平部
が非線形伸縮しながら対応付けられた結果，“7” に誤認識される場合がある．本論文では，こうした誤認識の低減手法を提案する．合わせ過ぎの発生原因としては，弾性マッチングが本来そのカテゴリ
では起こりえないような変形も補償対象としていることがあげられる．そこで本手法では，あらかじめ各カテゴリに生じやすい変形（固有変形）を統計的手法により求めておき，認識の際のマッチングの結果が固有変形からどれぐらい逸脱しているかを評価する．その逸脱量が大きければ，そのマッチ
ングにより合わせ過ぎが起きていると判断できる．オンライン数字データを用いた認識実験により，本手法の有効性を確認した．

Online Character Recognition Using Elastic Matching andEigen-deformations
Hiroto Mitoma,† Seiichi Uchida† and Hiroaki Sakoe†
In online character recognition based on elastic matching, such as DP matching, many ofmisrecognitions are often due to overfitting, which is the phenomenon that a wrong reference
pattern is closely fitted an input pattern by the matching. In this report, a technique to reduce those misrecognitions is proposed, where frequent deformations of each category, called
eigen-deformations, are employed. In case of overfitting, the matching between the two patterns will not be expressed by the eigen-deformations of the category of the reference pattern.
Thus, the overfitting can be detected by evaluating the divergence of the matching result fromthe eigen-deformations. The results of recognition experiment showed the usefulness of the
proposed technique.

1. は じ め に収できる．

オンライン手書き文字認識における誤認識の要因にによる誤認識がある．たとえば，入力パターンが “1”

従来の DP マッチングの問題点として，合わせ過ぎ

は，筆順変動，画数変動，ストロークの形状変動の 3であっても，DP マッチングにより “7” に誤認識されつがある．このうち形状変動（以下，単に変形と呼ぶ）

る場合がある．これは，マッチングによる時間方向のは 1 ストローク文字にも起こる変動であり，最も基本

非線形伸縮の結果，“1” の最初の短い水平部が “7” の的なものといえる．本論文では，この変形への対処法

水平部に対応づけられてしまったためである．こうしを提案する．

た合わせ過ぎへの単純な対処法として，マッチングの
1),2)

変形の吸収法として，DP マッチングがある．
DP マッチングは弾性マッチング（非線形伸縮）アル

範囲を各カテゴリごとに制約することが考えられる．

ゴリズムの一種であり，音声の時間方向の非線形伸縮

ずしも明らかではない．さらに，DP を用いる限り，マを吸収する目的として音声認識の分野で古くから用い

ルコフ的な変形すなわち隣接筆点間の局所的変形しかられている．オンライン文字データも音声と同じ時系制御できない点も問題として残る．つまり，“1” へのしかしながら，その範囲をどう設定すればよいかは必

列データなので，DP マッチングによりその変形を吸
本論文の内容は 2004 年 3 月の情報処理学会九州支部主催平成
15 年度火の国情報シンポジウムにて報告され，火の国情報シン
ポジウム編集委員により情報処理学会論文誌への掲載が推薦された論文である．

† 九州大学
Kyushu University

2845

2846

Dec. 2004

情報処理学会論文誌

合わせ過ぎを避けるためにカテゴリ “7” の書き出し点

各文字種固有の変形の方向性であり，本論文では標準と右上の角の点の相対位置関係を制約するといったよパターンからの変位として表現される．固有変形は，

うな大局的変形の制御はできない．この限界は，DP(i) DP マッチングによる変位の採集と，(ii) その主成を確率的な枠組みに発展させた Statistical DTW 3) や

分分析，という 2 つのステップにより自動的に求め

HMM 4)〜6) においても同様である．

られる．以下では，それぞれのステップについて詳述

本論文では，各カテゴリ固有の変形特性（以下，固する．

有変形）の利用に基づくオンライン文字認識の高精度

2.1 DP マッチングによる変位の採集化法を提案する．本手法では，各カテゴリに生じる変第 c カテゴリの標準パターン Rc を時系列

形には一定の傾向があるという点に着目する．たとえ

Rc = r 1 , r 2 , . . . , r i , . . . , r I(1)ば，文字 “7” においては，その垂直部の傾き角の変と表し，同様に第 c カテゴリの第 n 番目の学習パター化による変形は頻繁に生じる．すなわち，この変形は“7” の固有変形の 1 つである．一方，書き出し点と右ン T c,n を時系列上の角の点が非常に近くなるような大局的変形，すなと表す．ここで r i および tj は筆点の特徴ベクトル

わち “1” に近づいてしまうような変形は実際にはあまであり，り起こらない．これは，書き手が他の文字との区別をつけるために意識的・無意識的に変形の範囲を規定しT c,n = t1 , t2 , . . . , tj , . . . , tJ

r i = (xri , yir , dri )T

(2)

(3)

tj = (xtj , yjt , dtj )T(4)ているものと考えることができる．したがって，事前のように x 座標，y 座標，および方向を要素とする 3に固有変形が把握できていれば，それからの逸脱とし次元ベクトルとする．なお，正確には r i ，tj ，I ，Jて合わせ過ぎを排除できることになる．なお，後に示をそれぞれ r c,i ，tc,n,j ，Ic ，Jc,n のように記述する

すように，各カテゴリの固有変形は DP と主成分分析

べきだが，以下では誤解のない限りこれらの簡略表現の組合せにより自動的かつ統計的に推定される．

を用いる．

認識処理において固有変形をどのように用いるかに

2 パターン Rc と T c,n 間の弾性マッチング問題は，

ついては，オフライン文字認識の場合7),8) と同様，2次の最適化問題として定義される．

つの方式が考えられる．すなわち，(i) 事後評価によ［目的関数］

る方式と，(ii) 直接組み込みによる方式，が考えられる．本論文では (i) の方式を採用する．この方式では，
まず従来と同じく入力と標準パターンの DP マッチングを行う．次にそのマッチングの結果について固有変形からの逸脱量を求める．これを事後評価量として識別時にペナルティとして用いる．合わせ過ぎが起きれば，この事後評価量は大きくなると考えられるので，
結果的に合わせ過ぎにペナルティを与えることになる．
この方式は，方式 (ii) に比べて考え方が容易であるため，検討の第 1 段階として採用した．

1 
r i − tj(i)  → minimize
I
I

i=1

［制御変数（自然数）］

j(1), . . . , j(i), . . . , j(I)［制約条件］ j(i) − j(i − 1) ∈ {0, 1, 2}
j(1) = 1 j(I) = J

る試みは，木村らによって 1970 年代後半にすでに検ここで記号 x はベクトル x のユークリッドノルム√
xT x である．よく知られているように，この問題討されている9),10) ．この手法はオフライン文字認識には DP を使うことで効率的に解ける．また，目的関数

関するものであり，線分表現された標準パターンと，の最小値を D0 (Rc , T c,n ) とする．すなわち，

線パターン間のマッチングを統計量を使って評価す

細線化された入力パターン間のマッチングを，マハラ

D0 (Rc , T c,n )

ノビス距離を用いて評価している．本手法はこれらの手法を，オンライン文字認識処理の枠組みにおいて発展させたものであるといえる．

2. オンライン手書き文字の固有変形の推定
本章では，オンライン手書き文字の固有変形の推定法について述べる．前述のように，固有変形とは，1 
r i − tj(i) j(1),...,j(i),...,j(I) I
I

=

min

(5)

i=1

とする．この値は，変形吸収後の R c と T c,n のユー
クリッド距離であり，従来から識別関数値として用いられている．
制御変数 j(1), . . . , j(I) は 2 パターンの対応関係を

Vol. 45

No. 122847

弾性マッチングと固有変形を用いたオンライン文字認識表す変数であるが，これを基にすれば標準パターンを基準とした場合の学習パターンの変形を変位ベクトルとして求めることができる12) ．具体的には，T c,n の

2I 次元変位ベクトル v c,n は次のように表現される．

tv c,n = (xr1 − xtj(1) , y1r − yj(1)), . . . ,t), . . . ,(xri − xtj(i) , yir − yj(i)t)(xrI − xtj(I) , yIr − yj(I)

T

(6)

よって，各カテゴリ c について標準パターン Rc とNc 個の学習パターン T c,n 間で DP マッチングを行
えば，Nc 個の変位ベクトル v c,n が求まる．

2.2 主成分分析による固有変形の推定
固有変形は頻出する変形であり，変形のなす分布のreference : 9(c=19)
input
:9

reference : 5(c=8)
:9
input

D0

= 0.789<

D0= 0.844

図 1 合わせ過ぎにより誤認識された文字の例（入力文字 “9”→ 認
識結果 “5”）．括弧内の c の値は図 2 の標準パターン番号 cに対応
Fig. 1 Example of overﬁtting.

分散の大きな方向に対応する．したがって固有変形は，
前ステップで求まった Nc 個の変位ベクトル v c,n を

最終的には “5” に誤認識されている．こうした合わせ

主成分分析することで求まる．

過ぎが発生する原因は，DP マッチング時に各カテゴ

具体的には，まず各カテゴリについて，平均

1 
vc =
v c,n
Nc

和，すなわち DP マッチング距離 D0 が小さくなり，

リの変形の方向特性が考慮されていないためと考えら

Nc

(7)

れる．

n=1

そこで本章では，DP ベースのオンライン文字認識

および共分散行列法において固有変形を利用することで，合わせ過ぎに

1 (v c,n − v c )(v c,n − v c )TNc

よる誤認識を低減する手法について述べる．具体的に

Nc

Σc =

(8)

n=1

は，従来どおり，まず標準パターン Rc とカテゴリ未
知の入力パターン E 間で DP マッチングを行い，距を求める．変位ベクトル v c,n の次元は式 (6) のよう

離 D0 (R c , E) ならびに E の 2I 次元変位ベクトルに 2I で一定しているので，以上の計算が可能となっv を求める．その後にその変位ベクトル v と固有変形 {uc,m | m = 1, . . . , M } の距離を評価する．合わている．なお，式 (7) と同様の平均変位ベクトルの求め方は，文献 11) にも見られる．

せ過ぎを起こした際の変位ベクトル v は，多くの場

次にこの Σc を固有値展開すれば，固有ベクトル合，上位すなわち高頻度の固有変形では表現できない{uc,1 , . . . , uc,m , . . . , uc,M } として固有変形が得られ，固有値 {λc,1 , . . . , λc,m , . . . , λc,M } として各固有変形の寄与の大きさが求まる．ここで，次数 m は固有値のため，両者の差異は大きくなると考えられる．すなわ

大きさ順に対応する．したがって，第 1 固有変形 uc,1

チング距離 D0 (Rc , E) に加えたもの，すなわちが最頻変形であり，また大きな m に対応する固有変

ち，v の距離は大きくなる．本手法では，この事後評価による距離を P (Rc , E) とすると，それを DP マッ

Deigen (Rc , E)
= (1 − α)D0 (Rc , E) + αP (R c , E)

形ほど寄与は小さく，ノイズ的になる．

(9)

3. 固有変形を用いた認識を用いて最短距離法による識別を行う．合わせ過ぎが

従来の DP マッチングの枠組みによるオンライン文

距離 D0 を単独よりも大きくなる．したがってその起きた場合，距離 P の増加により，距離 Deigen は

字認識，すなわち入力パターンと標準パターン間の距

サン入力パターン E はカテゴリ c には認識されに離を D0 を用いて評価することに基づく文字認識におくくなる．この仕組みにより，合わせ過ぎによる誤認

いては，1 章で述べたように合わせ過ぎによる誤認識

識を排除できると考えられる．ここで，α は重み係数が問題となる．図 1 に合わせ過ぎによる誤認識例を（0 ≤ α ≤ 1）である．

示す．この誤認識された入力パターン “9” は，標準パ本論文では，v が平均 v c ，分散 Σc の多次元正規

ターン “5” と不自然に対応付けられている．より詳分布をなすという仮定の下，事後評価距離 P として細には，“5” の円弧部が交差しながら “9” の屈曲部に次式対応付けられている．その結果，各筆点間の距離の総2848

情報処理学会論文誌

P (Rc , E) =1
I

p(Rc , E)(10)Dec. 2004

個のテストパターンに分けられて提供されている．したがって，各文字種平均で学習パターン 749 サンプル，を用いる．ここで p(Rc , E) は次の（2 乗）マハラノ

テストパターン 350 サンプル，総数 10,992 サンプルビス距離である．

から構成されている．以下の実験では，学習パターン
セットを標準パターン設定と固有変形推定に，テスト

p(Rc , E) = (v − v c )T Σ−1c (v − v c )


M

=

m=1

1
λc,m

パターンセットを認識タスクとして用いた．

((v − v c )T uc,m )2 (11)これらすべてのサンプルについて，画数変動の影響をなくすために，ペンアップ部分も接続して 1 文字 1

式 (10) において，このマハラノビス距離の平方根を画とした．その後，文字全体の大きさを縦横比は保持とっているのは，式 (9) において線形加算されるユーしたまま 128 × 128 に線形正規化し，さらに隣接筆点

クリッド距離 (5) とオーダを同じにするためである．

間の距離が一定になるようにリサンプリングを行った．

また I で割っているのは，式 (5) と同じく，式 (11) に本データベースの学習パターンセットとテストパおける標準パターン長の影響を正規化するためである．

ターンセットには同じ筆記者が含まれていなかった．

上位すなわち大きな m に対応する固有ベクトル

具体的には，学習パターンセットは 30 人の筆記者に

uc,m は推定誤差を含みやすいことが知られている．

よって作成されているが，テストパターンセットは完

上位の固有値 {λc,m } は非常に小さな値となるので，

全に別の 14 人の筆記者によって作成されている．こその上位固有ベクトルの推定誤差はマハラノビス距離のため両データセットの筆記特性には差異が見られた．

(11) の値に大きく影響する．さらにゼロに非常に近い固有値については計算誤差の影響を受ける場合もある．このため，本論文では式 (11) の代わりに，次のこの差異が認識実験の結果に及ぼす影響については後

疑似マハラノビス距離13)

ン Rc を作成した．その際，筆順変動がある文字種に対しては，複数の標準パターンを用意した．実験試料



M

m=1

+

1
((v − v c )T uc,m )2
λc,m
M


m=M  +1=

同様，すべての標準パターンにも，1 画化，正規化，リサンプリングを施した．
図 2 は設定した全 21 カテゴリの標準パターンであ

1((v − v c )T uc,m )2λc,M  +1

る．数字 “8” の 4 番目の標準パターン（c = 18）に反映されているように，本データベースの学習パターン

1
v − v c 2
λc,M  +1M

+

4.2 標準パターンの設定
すべての学習パターンを観察し，手動で標準パター

p(Rc , E)
∼

述する．


m=1

(

1
λc,m

−

1
λc,M 

には，かなり特殊な筆順も含まれていた．

)((v − v c )T uc,m )2(12)4.1 節でも述べたように，学習パターンとテストパ
ターンでは筆記者が異なっている．その結果，学習パ
ターンを基準として作成した以上の標準パターンとテを用いる．これにより，前述の誤差の影響を抑え

スト用サンプルとの間には傾向の違いが見られた．たるこ と が で き る ．パラ メ ー タ M  の 決 め方 に はとえば，数字 “8” の 3 番目の標準パターン（c = 17）

様々な方法が考えられる．本論文では累積寄与率に類似したサンプルは，学習パターンセット中には 48M
λ /m=1 c,mM
λm=1 c,m

が，あるしきい値 θ をは個存在したのに対し，テストパターンセット中には皆じめて超えたときの M を用いることとした．後述す無であった．同様に，数字 “8” の 4 番目の標準パター

る認識実験においては，この θ は全カテゴリ共通で
0.9 としている．

セット中でわずかに 1 個であった．

4. 実

ン（c = 18）に類似したサンプルは，テストパターン

4.3 固有変形の推定結果
2 章で述べた固有変形の推定は以下の手順で行った．まず，1 つの標準パターンしか用意しなかった文験

4.1 実 験 試 料
本論文では，Unipen フォーマット14) に従った公開

字（“0”，“2”，“3”，“6”）については，標準パター

15)

ン R c とその文字の全学習パターン T c,n の間の孤立数字データを実験試料として用いた．本データ

で DP マッチングを行い，Nc 個の変位ベクトル

ベースは，あらかじめ 7,494 個の学習パターンと 3,498{v c,1 , . . . , v c,n , . . . , v c,Nc } を採集し，主成分分析にデータベースの 1 つである Ethem Alpaydin Digit

Vol. 45

No. 12弾性マッチングと固有変形を用いたオンライン文字認識

2849

図 2 実験で用いた標準パターン {Rc | c = 1, . . . , 21}．白丸は開始点，c は標準パターン番
号，括弧内の数字は学習パターン数 Nc
Fig. 2 Reference pattern used in the experiment.

より最終的に固有変形 {uc,m } と固有値 {λc,m } を求

同図より，α = 0.45 のときに最高認識率 98.2% がめた．一方，複数の標準パターンを持つ文字（すなわ

得られたことが分かる．一方，従来法による認識率は

ち “1”，“4”，“5”，“7”，“8”，“9”）については，同文字の学習パターンを次の手順で分割した．すなわち，97.4% であり，これに比べると，本手法の結果は 0.8%
（27 サンプル分）の向上となっている．この向上の内各学習パターンについてそれら複数の標準パターンと訳を見ると，35 サンプルの改善と 8 サンプルの改悪でDP マッチングを行い，距離が最も小さくなった標準あった．その詳細については 4.4.2 項で検討する．まパターン用の学習パターンとして分割した．その後，た，本手法において誤認識となった全 64 サンプルに

各標準パターンごとに 1 文字 1 標準パターンの場合とついては，4.4.3 項で考察する．さらに，学習パター

同じ手続きで固有変形と固有値を求めた．図 2 中で各ンとテストパターンで筆記者が異なること（4.1 節参

標準パターンの下に付与した括弧内の数字は，その標照）がこの認識率に及ぼした影響については，4.4.4

準パターンのカテゴリ c に属した学習パターンの数で項で考察する．

ある．このように，1 カテゴリあたりの学習パターン
数は最少でも 48（c = 17）であった．

文献 16) では，本論文と同じデータベースを用いた認識実験がなされ，97.09% の最高認識率が得られたと

図 3 は，寄与の大きな上位 3 つの固有変形 uc,1 ，

報告されている．同文献で提案されているのはニュー

uc,2 ，uc,3 により標準パターン R c を変形させたもラルネットに基づく認識機構を複数組み合わせた手法のである．これらの固有変形は，普段よく見られるであり，本手法とはかなり異なる認識モデルである．

変形になっていることが分かる．たとえば，数字 “0”したがって両者の優劣を認識率だけで決めることはで（c = 1）の第 1 固有変形は，書き出し点の変化である

きない．しかしながら，両者の認識率の差異は，本手と分かる．また，数字 “6”（c = 11）では，第 1 固有法の認識性能の高さを裏付けているといえる．

変形が文字全体の傾きの変化を，第 2 固有変形がルー

なお，ユークリッド距離単独での認識率（α = 0）

プ部の縦方向の変化を，第 3 固有変形がループ部の横とマハラノビス距離単独での認識率（α = 1）には大方向の変化を，それぞれ表していることが分かる．

きな差が見られる．この一因として，マハラノビス距

4.4 認識結果および考察
4.4.1 認 識 率

離の計算で用いる変位ベクトルには方向情報が入って

図 4 に，重み α を変えながら測定した，本手法すをおさえるための配慮である．十分な学習サンプルがいない点があげられる．これは変位ベクトルの次元数

なわち Deigen に基づく最短距離識別法による認識率

得られれば，変位ベクトルに方向特徴の差異も含めるを示す．なお，α = 0 の場合が，従来法すなわち D0

ことで，マハラノビス距離による識別性能を向上させに基づく最短距離識別法に対応する．

られると考えられる．この場合 Deigen は，パターン2850

情報処理学会論文誌

Dec. 2004

図 3 上位 3 つの固有変形 uc,1 ,uc,2 ,uc,3 によって変形された標準パターン
Fig. 3 Reference pattern deformed by the primary eigen-deformations of its category.

間の座標差と方向差という同一の情報をユークリッド

誤認識が抑制されていることが分かった．その具体例

距離とマハラノビス距離という異なる 2 つの距離尺度を図 5 に示す．同図 (a) は誤認識 “1”→“7” が改善さで評価し，それらを合算したものに相当する．

れた例，同図 (b) は誤認識 “9”→“5” が改善された例

4.4.2 改善例および改悪例
従来法では誤認識であったが本手法（α = 0.45）では正しく認識された全 35 サンプル（改善サンプル）

である．なお，同図 (b) の入力パターン “9” は，図 1

を表 1 にまとめる．表中で使用されている “9”→“5”ターン “7” の水平部が不自然に対応付けられている．

のものと同一である．
図 5 (a) では，入力パターン “1” の冒頭部と標準パという表記は，入力パターン “9” が “5” に誤認識さこの合わせ過ぎの結果として従来の D0 による識別でれたことを意味する．それら改善された全 35 サンプ

は入力パターン “1” は “7” に誤認識されている．一

ルを観察したところ，明らかに合わせ過ぎに起因する方，事後評価距離 P を見ると，正解標準パターン “1”Vol. 45

No. 122851

弾性マッチングと固有変形を用いたオンライン文字認識

99

D0 (97.4%)

97
96

Deigen (max: 98.2%)

(a)

95
94
93
92

reference : 7(c=12)
input
:1

91
90
89
0.0

0.2

0.4

0.6

0.8

D0 = 0.858
P= 0.544
Deigen = 0.716

1.0weight α

reference : 1(c=2)
input
:1

>

recognition rate (%)

98>

D0 = 0.889
P= 0.366
Deigen = 0.654

図 4 手書き数字データ（全 3498 サンプル）の認識率
Fig. 4 Recognition rate as the function of weight α.

表 1 本手法により減少した誤認識
Table 1 Decreased misrecognitions.

#misrecog.
D0
Deigen
10
1
16
9
6
0
6
1
9
6
1
0
1
0
1
0
1
0
1
0
total

(b)

#diﬀ
9
7
6
5
3
1
1
1
1
1
35

reference : 9(c=19)
input
:9

reference : 5(c=8)
:9
input

D0 = 0.789
P= 0.427
Deigen = 0.626>

input→
result“9”→“5”“0”→“8”“1”→“7”“2”→“7”“3”→“7”“0”→“6”“4”→“1”“4”→“5”“9”→“1”“9”→“7”>

D0 = 0.844
P= 0.198
Deigen = 0.553

図 5 固有変形の利用による改善例
Fig. 5 Characters correctly recognized by the proposed
technique.

30

input 9 − reference 5(a)25とのマッチングの方で大きくなっている．結果的に，D0 と P の線形和である Deigen による識別では，正解に転じている．
図 5 (b) も，事後評価距離 P の効果により正しい認

1<v,uc,m>λc,mとのマッチングよりも，この不正解標準パターン “7”

20
15
10
5

識結果が得られている．これは “9” が “5” に不自然に

0

対応付けられたために距離 D0 が過小評価され，誤認1

10曲したものではなく本来平滑であることが分かる．したがって，その円弧部が交差しながら入力パターンに対応付けられるような状況はほとんど生じない．これ
が入力パターン “9” とのマッチングにおける事後評価
距離を大きくしたものと考えられる．図 6 は図 5 (b)

30

40

50

60

30

(b)

input 9 − reference 925

1<v,uc,m>λc,mパターン “5” の円弧部に生じる変形は “9” のように屈20

eigen-deformation m

識されていた例である．しかし，図 3 を見ると，標準

20
15
10
5

の 2 つのマッチングにおける各固有変形成分を示したものである．合わせ過ぎが起きている不正解標準パ
ターン “5” とのマッチングでは，下位すなわち低頻度の固有変形のところで比較的大きな値が出ており，これがペナルティとなって P を大きくしていることが
分かる．

0

1

10

20

30

40

eigen-deformation m

5060

図 6 図 5 (b) のマッチングの際の各固有変形成分の大きさ．(a) 入力パターン “9” と標準パターン “5” のマッチング．(b) 入力
パターン “9” と標準パターン “9” のマッチング
Fig. 6 Detail of posterior evaluation.

2852

Dec. 2004

情報処理学会論文誌
表 3 誤認識となった全 64 サンプルの内訳
Table 3 Detail of all misrecognitions.

reason ofmisrecog.

#samplesabnormal start/end point

input sample (upper) andrecog. result (lower, input→result)3

extreme deformation“3”→“9”“3”→“1”“9”→“8”“1”→“2”“4”→“2”“5”→“3”“9”→“7”“0”→“8”“2”→“7”“3”→“5”“9”→“5”“3”→“7”“4”→“9”“5”→“9”“7”→“9”12case 1 (Pcorrect < Pwrong )14case 2 (Pcorrect > Pwrong )35

表 2 本手法により増加した誤認識
Table 2 Increased misrecognitions.

input→
result“7”→“9”“5”→“9”“6”→“8”#misrecog.
D0
Deigen
8
12
5
8
0
1
total

#diﬀ
4
3
1
8

れた．ここで，Pcorrect は正解標準パターンとの事後評価距離，Pwrong は不正解標準パターンとの事後評
価距離である．この case 1 の誤認識の原因の 1 つとしては，
原因 A： 事後評価距離 Pwrong は有効に機能したが距離 D0 の差が元々大き過ぎた，ことが考えられる．したがって，この原因 A による
誤認識の低減には，正解カテゴリとの D0 を不正解

従来法では正しく認識されたが本手法では誤認識さカテゴリとのそれより小さくする，すなわち従来法のれた全 8 サンプル（改悪サンプル）を表 2 にまとめ

誤認識を低減させることが必要となる．具体的には，る．この新たに誤認識された “5” と “7” の入力パター

標準パターンを新たに増やす，もしくは合理的な設定

ンは学習パターンには見られないものであった．その手法（たとえば学習による自動的な標準パターン設定

ため，求まった固有変形ではそれら入力パターンの変法）を採用することにより改善できると考えられる．

形を表現できず，事後評価距離が大きくなり誤認識に

次の case 2 とは条件 Pcorrect > Pwrong を満たす誤なったものと考えられる．

4.4.3 誤認識原因の考察
本手法（α = 0.45）で誤認識となった全 64 サンプ
ル（前出の改悪サンプル 8 を含む）の内訳を，考えら認識である．この case 2 の誤認識の原因は次の 2 つが考えられる．
原因 B： 正解標準パターンに対する事後評価距離

Pcorrect が過剰に大きくなった．

れる原因とともに表 3 に示す．最初の 2 種の誤認識

原因 C： 不正解標準パターンに対する事後評価距離（始端・終端異常ならびに難読文字）計 15 サンプルある．よって以下では，残る 49 サンプルの誤認識をPwrong が十分大きくならなかった．
原因 B と C は排他的ではなく，両方による誤認識も多く存在する．実際，case 2 の 35 サンプルのほとん

中心として考察する．

どはそうした誤認識であった．具体的には，原因 B をは，本手法に限らず一般に認識が非常に困難なものでこれら 49 サンプルは以下のように case 1 と case 2

Pcorrect > P̄correct を満たす場合（P̄correct は Pcorrectに分類される．まず case 1 とは条件 Pcorrect < Pwrongの平均値），原因 C を Pwrong < P̄wrong を満たす場合

を満たす誤認識パターンであり，14 サンプルが含ま（P̄wrong は不正解標準パターン対する P のうちで最Vol. 45

No. 122853

弾性マッチングと固有変形を用いたオンライン文字認識

小のものの平均値）と定義すると，35 サンプル中 32

は 98.3% となった．これは前述の筆記者が異なっていサンプルは両原因によるものであった．

た場合の結果（98.2%）よりも 0.1%（5 サンプル分）

原因 B は，実際にカテゴリに起こっている変形で程度向上している．前節の実験と同じ標準パターンをあるにもかかわらず，それがあまり起こらない変形と使ったためにあまり大幅な認識率の向上にはなかった

判断してまったことを意味する．より具体的には，そものの，前節までの実験では筆記者の不整合が影響しの誤認識されたテストパターンの変形がその正解カていた可能性があったことが分かる．また，重み α にテゴリの上位の固有変形では表現できなかったことをついては，学習パターンで閉じた認識実験においても意味する．したがって原因 B による誤認識を低減さ

テストパターンの認識実験においても，認識率のピーせるには，学習パターンを拡充することが効果的と考クを与えたのは同じ α = 0.55 であった．したがって，えられる．前述のように，公開データベース Ethem

筆記者が一致すると α の不整合も解消するといえる．

Alpaydin Digit のテストパターンセットと学習パター

誤認識となった全 59 サンプルのうち，19 サンプルンセットでは筆記者が異なっており，本実験では特にが case 1 であり，26 サンプルが case 2 であった．前

この不整合がこの原因 B を顕著なものとしていると

節の実験では case 2 が case 1 の 2 倍以上あったのに考えられる．

対し，本実験ではその差は明らかに縮まっている．こ原因 C は，異なるカテゴリにおいても類似した変れは前節でも考察したように，筆記者一致の結果，前形が存在することを意味する．したがって，変形がカ節の原因 B による誤認識を低減できたためと考えら

テゴリごとで異なっていることを前提とした本手法でれる．

は，この原因による誤認識を直接低減することは難し
い．しかしながら，前述のように case 2 に属する誤

5. お わ り に認識のほとんどすべては，原因 B と原因 C の両方に

オンライン文字認識におけるストロークの形状変動

よって発生したものである．さらに，Pcorrect を小さへの一対処法として，カテゴリ固有の変形特性（固有くできれば，相対的に Pwrong の効果を大きくできる

変形）の利用について検討した．実験の結果，主成分可能性がある．以上から，原因 B に対処することで結分析により各カテゴリに実際に生じる変形を適切に表果的に原因 C による誤認識も減らせると考えられる．

現した固有変形が得られることが分かった．また，認4.4.4 筆記者の影響

識実験を通して，従来法では合わせ過ぎにより誤認識

以上の考察においては，テストパターンセットと学となっていたサンプルも本手法では正しく認識するこ習パターンセットで筆記者が異なっており，さらにことができ，合わせ過ぎによる誤認識の抑制効果を確認の不整合が誤認識を誘発していることを指摘してきた．

することができた．

この不整合は重み α の設定にも影響する．実際，学将来的な課題として，固有変形をマッチング過程に習パターンで閉じた認識実験での最適値 α = 0.70 を，

直接組み込む方式の検討があげられる．この方式を採テストパターンの認識実験に用いると，図 4 から，テ用することで，認識精度だけでなく計算量的にも有効

スト用サンプルの認識率は 97.5% と，従来法程度まではないかと考えている．また，本論文では手動で行っで低下することが分かる．

ていた標準パターンの設定についても自動化11),17) がそこで，この筆記者の不整合をなくした場合，すな
わち筆記者集合を学習時と認識時で一致させた場合の必要と考えている．さらに多画文字への適用についても検討する予定である．

実験を行った．具体的には，データベースの全パター

謝辞 本研究の一部は文部科学省科学研究費補助金ンをいったん混合し，再び学習パターン 7494 サンプ（若手 B No.14780293），および総務省戦略的情報通

ルと 3498 個のテストパターンに振り分けた．この振信研究開発推進制度の支援を受けた．

り分けにより学習パターンもテストパターンも等し
く全 44 人分のサンプルを含むことになる．この新たな学習パターンセットをすべて使って固有変形を求めた後，新たなテストパターンの認識実験を行った．なお，実験結果の比較を容易にするため，標準パターンについては前節までの実験と同じ図 2 の 21 個を用いた．
実験の結果，本手法によるテストパターンの認識率

参 考

文

献

1) 藤原塩和，池田克夫，富永善治，清野 武：接線ベクトル列を用いたオンライン手書き文字の認識，情報処理，Vol.17, No.3, pp.191–199 (1976).
2) Yoshida, K. and Sakoe, H.: Online handwritten character recognition for a personal computer system, IEEE Trans.Consumer Electronics, Vol.CE-28, No.3, pp.202–209 (1982).

2854

Dec. 2004

情報処理学会論文誌

3) Bahlmann, C. and Burkhardt, H.: The writer
independent online handwriting recognition
system frog on hand and cluster generative statistical dynamic time warping, IEEE Trans.
PAMI, Vol.26, No.3, pp.299–310 (2004).
4) Hu, J., Brown, M.-K. and Turin, W.: HMM
based on-line handwriting recognition, IEEE
Trans. PAMI, Vol.18, No.10, pp.1039–1045(1996).
5) 伊藤 等，中川正樹：Hidden Markov Modelに基づくオンライン手書き文字認識，信学技報，
PRMU97-85 (1997).
6) 嵯峨山茂樹，中井 満，下平 博：ストローク
HMM に基づくオンライン手書き文字認識方式，
信学技報，PRMU2000-35 (2000).
7) Uchida, S. and Sakoe, H.: Eigen-deformations
for elastic matching based handwritten character recognition, Pattern Recognition, Vol.36,
No.9, pp.2031–2040 (2003).
8) 内田誠一，迫江博昭： カテゴリ固有変形の線形結合モデルに基づく弾性マッチング法，信学論（D-II），Vol.J87-DII, No.2, pp.639–648 (2004).
9) 木村文隆，吉村ミツ，三宅康二，市川真人：ス
トローク構造解析法による自由手書き片仮名文字
認識，信学論（D），Vol.J62-D, No.1, pp.16–23(1979).
10) 木村文隆，堀尾佳弘，塚本隆啓，吉村ミツ，三宅康二：文字の構造情報抽出に用いる対応付けシ
ステムと平仮名文字認識への応用，信学論（D），
Vol.J63-D, No.8, pp.650–657 (1980).
11) 趙 鵬，佐藤幸男，吉村ミツ：オンライン走り
書き文字認識における汎用辞書の作成，情報処理学会論文誌，Vol.34, No.3, pp.418–425 (1993).
12) 若原 徹：局所的 Aﬃne 変換を用いたオンラ
イン手書き文字認識，信学論，Vol.J71-D, No.2,
pp. 379–386, 1988.
13) 栗田昌徳，鶴岡信治，横井茂樹，三宅康二：加重方向ヒストグラムと疑似マハラノビス距離を用いた手書き漢字・ひらがな認識，信学技報，PRL8279 (1982).
14) Guyon, I., Schomaker, L., Plamondon, R.,
Liberman, M. and Janet, S.: UNIPEN projectof on-line data exchange and recognizer benchmarks, Proc. Int. Conf. Pattern Recognition,
pp.29–33 (1994).
15) ftp://ftp.ics.uci.edu/pub/machine-learningdatabases/pendigits/16) Alimoglu, F. and Alpaydin, E.: Combining multiple representations and classiﬁers forpen-based handwritten digit recognition, Proc.
Int. Conf. Document Analysis and Recognition,
Vol.2 of 2, pp.637–640 (1997).
17) Connell, S.D. and Jain, A.K.: Template-based
online character recognition, Pattern Recogni-tion, Vol.34, No.1, pp.1–14 (2001).
(平成 16 年 7 月 13 日受付)
(平成 16 年 10 月 4 日採録)

推薦 文

入力文字図形の文字カテゴリを認識する場合，基本
的には，入力図形と標準文字図形の類似度を計算し，最も類似している文字カテゴリを入力図形の文字カテゴリとする．ところが，オンライン手書き文字認識では，個人の癖などによる形状変形のために，入力図形と正解の標準文字図形との類似度がそれほど高くならない場合があり，誤認識の要因の 1 つとなっている．
これを解決する手法として，非線形伸縮により入力図形を変形し標準図形に合わせる（近づける）DP マッ
チングがある．従来の DP マッチングは，合わせ過ぎによる誤認識の問題があったが，本論文では，入力図
形を標準図形に合わせて変形する際，各文字カテゴリごとに固有の変形特性（固有変形）があることを利用
し，合わせ過ぎの問題を防ぐ手法を提案している．この固有変形も DP と主成分分析の組合せにより自動的に推定される．手法の正当性については問題がなく，実験によりその有効性も示されているため，本論文を推薦するものである．
（火の国情報シンポジウム編集委員 岡崎直宣）
三苫 寛人
平成 16 年九州大学工学部電気情報工学科卒業．同年同大学院システ
ム情報科学府修士課程入学．現在に至る．オンライン文字認識に関する研究に従事．電子情報通信学会会員．
内田 誠一（正会員）
平成 2 年九州大学工学部電子工学科卒業．平成 4 年同大学院修士課程（情報）修了．セコム（株）勤務を経て，現在，同大学院システム情報科学研究院知能システム学部門助教
授．博士（工学）．画像パターンの解析・認識，および音声の認識・合成に関する研究に従事．IEEE，電子情報通信学会，日本音響学会，映像情報メディア学会各会員．

Vol. 45

No. 12弾性マッチングと固有変形を用いたオンライン文字認識

迫江 博昭（正会員）
昭和 41 年九州工業大学制御工学科卒業．昭和 43 年九州大学大学院修士課程（電子）修了．同年日本電気
株式会社入社．平成元年九州大学に移り，現在システム情報科学研究院
知能システム学部門教授．工学博士．音声認識および画像パターン解析の研究に従事．IEEE ASSP SeniorAward，電子情報通信学会業績賞，電子情報通信学会
米沢ファウンダーズメダル受賞記念特別賞および論文
賞，（社）日本発明協会・内閣総理大臣発明賞，九工大嘉村記念賞各受賞．IEEE，電子情報通信学会（フェロー），日本音響学会，映像情報メディア学会各会員．

2855