２次元ワープを併用したオンライン英数字・数学記号認識
田畑 耕一 † 福田 亮治 ‡ 鈴木 昌和 †† 九州大学大学院数理学研究科 〒 812–8581 福岡県福岡市東区箱崎 6−10−1
E-mail:suzuki@math.kyushu-u.ac.jp‡ 大分大学 工学部福祉環境工学科 〒 870-1192 大分市大字旦野原 700
E-mail:rfukuda@cc.oita-u.ac.jp

あらまし

現在開発中の手書きによる数式入力インターフェースにおいて、手書き１文字認識率の向上と、書き手によらないロバストな認識を実現するために、歪んだ文字の認識が課題であった。今回、文字の歪みに強い認識手法として２次元ワープ法を用い、単純化した形でオンライン手書き文字認識に導入し、従来用いていた認識手法と組み合わせることによって、効果を上げる
ことが出来たので報告する。また、複数の認識手法により得られたコストや順位を用いた Voting 方法についての検討も、併せて
報告する。
キーワード

オンライン手書き文字認識、２次元ワープ、Voting 方法

On-Line Recognition of Alphabet, Numeral and Mathematical
Symbols Additionally Using Two-Dimensional Warping
Koichi Tabata†Ryouzi Fukuda‡

Masakazu Suzuki†† Graduate School of Mathematics, Kyushu University 6–10–1 Hakozaki, Higashi-ku, Fukuoka, 812–8581 Japan
E-mail:suzuki@math.kyushu-u.ac.jp‡ Faculty of Engineering Oita University 700 Dannoharu, Oita, 870–1192 Japan
E-mail:rfukuda@cc.oita-u.ac.jp

Abstract

In our handwriting interface under development, one of our subject was the improvement of the rate ofcharacter recognition including deformed characters. In this paper, we apply simpliﬁed Two-Dimensional warping method
as the robust recognition method for solving this problem, and combine it with our recognition method used so far. This
paper reports this eﬀect. Moreover, this paper also reports the examination about the voting method using the cost or orderobtained from two or more recognition methods.
Keywords

On-Line Hand Written Recognition, Two-Dimensional Warping, Voting Method

1

はじめに

今日のネットワークやコンピュータの加速的な進歩に伴い、その数学における用途も、単なる計算だけに留まらず様々な可能性を持っている。例えば、数式処理システ
ムや数式のデータベースに接続した電子ボードなど、数学の授業や講義の新しいスタイルを生み出す可能性がある。また、TEX や MathML といった各種数式フォーマッ
ト、Mathematica のような数式処理システム、Word など各種ワープロに付属の数式入力機能など、コンピュー
タ上で数式を扱う環境も開発されて来ている。
しかし、現在、コンピュータ上で数式を扱うのはまだまだ簡単であるとは言えない。Mathematica や Word な
どの数式入力機能は、直感的で分かりやすいが、メニュー
ボタンなどによる入力操作の煩わしさがスムーズな入力を妨げ、ユーザの思考の流れを中断させることが多い。
TEX は数式をスムーズに入力できるが、使いこなせるよ
うになるまで相当な修練が必要とされる。また、入力された数式の意味を一目見ただけで把握することが難しく、入力の誤りを数式を見ながら訂正することができないという事も挙げられるだろう。
この問題を解決するために、我々は、オンライン手書き
文字認識を用いたユーザーにやさしい数式入力インターフェイスを開発している ([1])。このシステムはリアルタ
イムで手書き数式を認識し、自動的に書き換えを行うイ
ンタラクティブな手書き入力インターフェイスと、様々なフォーマットに対応し、数式の視覚的な編集を可能とするエディタからなる。

した困難に対応する方法として、上述の逐次認識方式を導入し、スムーズな数式入力を実現している。
したがって、この手書き入力インターフェイスにおいては、１数式要素の認識率の向上が重要な課題になってくる。これまで開発してきた手書き文字認識システムでは、方向線素特徴量による認識手法と分割ストロークによる認識手法の２つを用いて手書き文字認識を行ってきた。前者は、文字領域の５×３ブロック内における８方向の方向線素の割合を特徴ベクトルとして認識に用いる手法であり、後者は、一定の規則により分割されたスト
ロークにおける、始点終点方向・外接矩形座標・縦横比を特徴ベクトルとして認識に用いる認識手法である。この
従来手法により丁寧に書かれた文字に対しては良い認識
結果を返す。しかし、書き手の書き癖などによる歪んだ文字にはあまり対応できていなかった。そこで今回、新たな方法として、２次元ワープ法という歪みに強い認識手法を組み合わせることで、解決を試みた。この手法は、その計算量の大きさによりそのままオンラインに導入することは出来ないので、計算量削減のためにアルゴリズ
ムを簡略化して導入した。それでも十分な効果があったので報告する。また、複数認識手法による認識結果候補の Voting 方法についての検討も、併せて報告する。

従来の認識手法2

従来は２つの認識手法を個別に用いて認識を行い、それぞれの認識結果候補における共通結果を、最終的な認識結果の上位にする方法で認識結果を投票していた。この節ではそれら２つの手法について説明する。その投票方法については第 4 節にて述べるためここでは省略する。
方向線素特徴量を用いた認識手法

2.1

図 1: システムの外観
このシステムにおける手書き入力インターフェイスの最大の特徴は、全体の数式を書き終えてから文字認識や数式認識を行うのではなく、ペンを離す度に文字認識を実行し、文字（あるいは記号）として認識されたら直ちに、整形された文字に書き直し、位置を調整して表示してしまう点にある。これを逐次認識方式と呼ぶ（[2]）。数
式認識では、入力ストローク列の文字・記号の単位の切り出しや文字認識の誤り、数式構文中の位置判定の誤りが数式全体の認識を破壊してしまうことが多く、その修正が著しく困難である。また、数式の書き直しや整形に神経を裂かれることは、書き手の思考の中断を生み出すことになり、スムーズな入力の大きな障害になる。こうこの認識手法は、方向線素特徴量をベースにした手法である。文字画像は点列で与えられているので、連続した線分列とも考えられる。方向線素特徴量とは、文字画
像領域のどの領域にどの方向の線分列がどれぐらいの長さ含まれているのかを数値化したものである。文字画像の外接矩形をあらかじめ設定しておいた間隔で小領域に分割し、それら小領域毎に方向線素特徴量を求めていく。
この特徴量の他、始点終点での方向、縦横比等も詳細認識のために特徴量として併せて用いている。

2.1.1

認識に用いるいくつかの特徴量• 方向線素特徴量
ここでは、入力された文字画像の外接矩形を、図 2で示したように縦５×横３＝１５の小領域に分けることにする。ここで言う方向とは、図 3 のような８方向で半時計回りで定義する。したがって、各小領
域の方向線素特徴量は８次元ベクトルになり、全体の画像に対しては８×１５＝１２０次元ベクトルになる。

タとして用意する。このデータからそれぞれの特徴量ベ
クトルの平均を計算したものを用意する。これを文字種のストローク数ごとに分けて並べたものを辞書とする。

2.1.3

図 3: 方向
図 2: 小領域分割の例
以下、詳しく述べる。

lij を点 Pij (xij , yij ) から点 Pij+1 (xij+1 , yij+1 ) を結
ぶ線分とする。lij の方向 (Pij から Pij+1 への向き)
が８方向 (図 3) のどの隣り合う２方向 Di , Di+1 ∈{0, 1, ..., 7} に挟まれるかを調べる。そして、lij とDi , Di+1 との角度差をそれぞれ θ1 , θ2 定め、L = |lij |(lij の長さ) としたとき、この角度差の比を用いてLi =以上の特徴量と辞書を用いて認識を行う。まず、入力された文字データのストローク数により、検索対象とする辞書の文字種を限定し、その中で各文字種の特徴量ベ
クトルと入力文字データの特徴量ベクトルとの距離差を求める。差の小さいものから３位までを認識結果の候補として出力する。

2.2

分割ストロークを用いた認識手法

この認識手法は、入力されたストロークを一定の規則を持ったピークポイントで分割し、その分割されたスト
ローク毎の特徴量を求め、その特徴量の列を用いて認識を行う手法である。

2.2.1

ストロークの分割規則と基本ストロークの定義

入力されたストロークは、縦のピークポイントで分割し、さらに横のピークポイントで入射角反射角の差が 90度より大きい場所では分割する。

Lθ2,
θ1 + θ2

Li+1 =

認識結果候補の決定Lθ1θ1 + θ2
図 4: 方向の振分のようにして lij を２方向に数値化して振り分ける。
lij の中点が小領域 Q 内の点であった場合、このLi , Li+1 を小領域 Q の方向線素特徴量ベクトルにおける、方向 Di , Di+1 に対応する成分の値にそれぞれ加算する。この操作を全ての線分について行い、得られたベクトルの全成分の和が一定値 (ここでは２０００) になるように正規化したものを、文字画
像 A の方向線素特徴量（１２０次元）とする。

縦のピークポイントとは、点列の y 座標値の変化を時間順に見たとき、その正負が入れ替わる点のことである。
正負が入れ替わる部分で y 座標値が同じ点が続く場合は、それらの点を結んだ x 軸に水平な線分の中点をピークポ
イントとする。まずこの点でストロークを分割する。
同様に考えて横のピークポイントは x 座標値の変化の正負が入れ替わる点である。そして、この横のピークポイン−−−−−→
ト P eak(x) = Pij であったとき、ベクトル Pij−1 Pij とベ−−−−−→
クトル Pij Pij+1 のなす角 θx が θx > π2 の場合、P eak(x)によりストロークを分割する（図 5 参照）。
この規則により分割されたストロークの１単位を基本
ストロークと呼ぶことにする。

• ストロークの始点、終点情報
ストロークごとの始点・終点の座標とその方向も、ベクトルとして持つ。このベクトルの次元は文字種のストローク数に依存し、ストローク数が n ならば
n × 6 次元である。
• その他の特徴量
その他、縦横比、ストローク数などの要素も詳細認識のために特徴量に入れた。
2.1.2

辞書の作成

一文字に対して、方向線素特徴量とストローク始点・終点情報を併せたベクトルを特徴量ベクトルと呼ぶことにする。一文字は 120 + 6n 次元の特徴量ベクトルを持つ（n はストローク数)。ストローク数により特徴量ベクトルの次元数は異なる。
各文字種ごとに１００文字程度の学習データを用意する。同じ文字でも異なる書き方があれば、違う文字種デー

図 6: 始点終点方向
図 5: ストローク分割方法

2.2.2

認識に用いるいくつかの特徴量

基本ストロークに対して、始点、終点での方向 (図 6)、
外接矩形、縦横比を求めて、ベクトルを生成する。
このベクトルの次元は基本ストローク数を n とすると、
n × 7 次元である。このベクトルを全ストロークに対してストローク順に並べたものを、この認識手法の特徴ベクトルとする。１文字データのストローク数を N とし、ストローク si の基本ストローク数 (ストローク分割数)
Nを di とすると、特徴ベクトルの次元は i=1 di × 7 で表

認識に用いる特徴量の設定

される。

3.1

また、基本ストロークは、元のストロークの縦のピー
クポイントでは必ず分割されているので、y 方向に関しては単調増加 (アップストローク) か単調減少 (ダウンス
トローク) のどちらかになっている。この性質を用いて基本ストロークを２値 (0, 1) で表し、ストロークを記号列化する。これをストローク順に並べたものを、１文字
データの大分類記号列と呼ぶことにする。この大分類記
号列を用いることにより、辞書検索の効率化を行う。

ま ず、文 字 デ ー タ を
M × M の小領域に分ける。本論文では M = 10としている (図 7 参照)。
この小領域ごとの方向線
素特徴量（2.1.1 を参照）
を８方向 (図 3) にて求め
る。

2.2.3

辞書の作成

各文字種ごとに１００文字程度の学習データを用意する。このとき、同じ文字種内で、予想し得る大分類記号
列がほとんど出つくすよう、注意して学習データを集める。こうして集めた学習データに対して、同じ大分類記
号列かつ同じ文字種であるものについて、特徴量の平均を取る。これを全ストローク分割数ごとに並べたものをこの認識手法の辞書とする。

2.2.4

3

このとき、格子点を p(i, j), (i, j = 0, 1, ..., M ) とし、
p(i − 1, j − 1), p(i − 1, j), p(i, j − 1), p(i, j)(i, j ≥ 1) の４点で囲まれた領域の方向線素特徴量を a(i, j) で表すことにする。a(i, j) は８次元ベクトルである。
これ以降、文字データ A をただの点列ではなく画像として捉えると、理解しやすい。この場合、a(i, j) を画素と思うことにする。この特徴量を元に、２画像

A = {a(i, j)|i, j = 1, 2, ..., M },認識結果候補の決定

以上の特徴量と辞書を用いて認識を行う。まず、入力された文字データの大分類記号列により、検索対象とする辞書の要素を限定し、その中で各文字種の特徴量ベク
トルと入力文字データの特徴量ベクトルとの距離差を求める。差の小さいものから３位までを認識結果の候補として出力する。もし大分類記号列が見つからなかった場
合、同じストローク分割数である全てのデータに対して、
特徴量ベクトルの距離差を求める。この距離差にさらにいくらかの値 (ペナルティ) を追加し、上と同様に距離差の小さいものから３位までを認識結果の候補として出力する。

２次元ワープ法を用いた認識手法

この手法は内田、迫江の論文（[3],[4]）を参考にした手法である。２次元ワープとは、２画像の最大一致を与える２次元−２次元写像のことを呼ぶ。パターン認識の立場から見れば、２次元ワープは画像の変形に適応可能なマッチング処理であると言える。この２次元ワープの最適化問題、すなわち２画像の最大一致を与える２次元
ワープを探索する問題は、動的計画法（ＤＰ）に基づく
アルゴリズムによって解くことができる。しかし、論文[3] におけるＤＰの計算量は、最悪の場合指数オーダーとなり、オンラインのシステムに組み込むには実用的でなく、このままでは用いることはできない。
そこでこの手法の文字の歪みに強いという特色を出来るだけ残しつつ、単純化した形でオンラインに導入する。
以下ではその手法を説明する。

図 7: 小領域に分割された例

B = {b(x, y)|x, y = 1, 2, ..., M }との２次ワープの最適化問題を考える。

3.2

ピボットの紹介と設定方法

画像を横に N 分割する線分を l(i), (i = 0, 1, ..., N )、その分割された段を L(i), (i = 1, 2, ..., N ) とする (図 9)。
L(i), (i ≥ 1) は l(i − 1) と l(i) に挟まれた画像である。
ここでは画像の縦の最小単位が M であるため、N には
N |M の条件が付く。本論文では N = 5 としている。
この l(i) を折り曲げて L(i) を画像 B 上に重ね合わせることを考える。この折り曲げを行う l(i) 上の点を中間ピボットと呼び、(i, j2 ) と表す。また、l(i) の左端 (i, j1 )を左ピボット、右端 (i, j3 ) を右ピボットと呼ぶ。ここで0 = j1 < j2 < j3 = M とする。

図 8: 入力パターン (A)図 9: 標準パターン (B)

ここでは入力パターン A が、対象パターン B であると見たときの A の中心線を予測して、その中心線と l(i)との交点を中間ピボットとして定める事とする (図 8)。
中心線の予測は、入力パターン A の段 L(i) ごとに行う。まず L(i) に含まれる方向線素特徴量を用いて中心線

lp(i) を予測する。簡単のために、画素の１単位を
M

N i


al (i, j) =a(k, j)k=( MN −1)iとして考える。 M
N は L(i) に含まれる画素の行数であるから、al (i, j) は L(i) 画像を横方向に M で分割したときの、j 列目の画素の和 (方向線素特徴量の和) である。
L(i) を左右に分割する線分 lp(i, j) を、格子点 p(( M
N −
i,
j)
を結ぶ線分とし、
j
を
1
≤
j
≤
M
−
1の
1)i, j), p( M
N
範囲で動かしたとき、lp(i, j) で区切られた左右の領域の方向線素特徴量 Llef t (i, j), Lright (i, j) は、

Llef t (i, j) =j

Llef t (i) は８次元ベクトルと見なす。Lright (i) についても同様である。
ここから、Llef t (i) のワープによる像 Ĺlef t (i) を、各ピボットの像によって囲まれた領域の方向線素特徴量と定める。すなわち l(i) 上の、左、中間、右ピボットのワー
プ に よ る 像 を そ れ ぞ れ (xi1 , y1i ), (xi2 , y2i ), (xi3 , y3i ) と 表
i−1
i−1 i−1iiii
し 、４ 点 (xi−11 , y1 ), (x2 , y2 ), (x1 , y1 ), (x2 , y2 )に よ る 四 角 形 領 域 をS(i, lef t)、４ 点i−1 i−1i−1 i−1iii(x2 , y2 ), (x3 , y3 ), (x2 , y2 ), (x3 , y3i ) に よ る 四角形領域を S(i, right) とすると、

al (i, k)Mal (i, k)(1 ≤ j ≤ M − 1) と、対象パターン B の、i 段目の左右の小領域の方向線素特徴量 Blef t (i), Bright (i) との差の和、Blef t (i) − Llef t (i, j) + Bright (i) − Lright (i, j)
が最も小さくなるような j = j́ を各段で求め、

a(i, j)と表せることになる。
この Ĺlef t (i), Ĺright (i) により L(i) のワープによる像´
L(i) を表す。

3.4

とする。
以上で求まった lp(i), lp(i + 1), (1 ≤ i ≤ N − 1) の中点間を結んだ線分と l(i) との交点を、l(i) 上の中間ピボットとして定めるようにする。i = 0 の場合は、l(1) 上の中間ピボット (1, j2 ) と lp(1) の中点を結んだ直線と l(0)との交点、i = N の場合は、l(N − 1) 上の中間ピボット(N − 1, j2 ) と lp(N ) の中点を結んだ直線と l(N ) との交点、をそれぞれ中間ピボットとして定める。

目的関数と画像間の距離

画像 A の段 Llef t (i), Lright (i) のワープによる像と、画像 B の対応する段 Blef t (i), Bright (i) との距離を、前節の表記を用いて次式で定義する。

ˆ Ĺlef t (i), Blef t (i)) = Ĺlef t (i) − Blef t (i)d(
ˆ Ĺright (i), Bright (i)) = Ĺright (i) − Bright (i)d(lp(i) = lp(i, j́)

これより、L(i) のワープによる像 Ĺ(i) と B(i) の距離を

ˆ lef t (i), Blef t (i)) + d(Lˆ right (i), Bright (i))d(i) = d(L
(1)
と定める。
全体の画像に対してのワープの実行においては、距離d を全ての段 i について加算した

ワープ関数

これら、左、中間、右ピボットのワープによる像を用いて、各段 L(i) のワープを考える。
その前に準備として、次の定義をする。
格子上の異なる４点が与えられたとき、この４点を結んでできる四角形領域 S における方向線素特徴量はĹright (i) =pc (i,j) in S(i,right)

k=j+1

3.3

a(i, j)pc (i,j) in S(i,lef t)

k=1

Lright (i, j) =Ĺlef t (i) =a(i, j)pc (i,j) in S

(pc (i, j) は画素 a(i, j) の領域の中心点であり、p in S とは S 内に点 p が含まれることを意味する) で与えられるものとする。
いま、L(i) を Llef t (i) と Lright (i) に分けて考える。
Llef t (i) は、l(i − 1) 及び l(i) 上の左、中間ピボットの４点で表される領域であるが、この領域における方向線
素特徴量により Llef t (i) を表現することにする。つまり、

M


d(i)

(2)

i=1

を目的関数とし、これを最小化するワープ関数を求める。目的関数 (2) の最小値を D(A, B) と表すことにする。
D(A, B) は２次元ワープにより２画像 A, B をマッチングしたときの画像間の距離に相当する。

3.5

ピボットの制約条件

ワープに適切な自由度を与えるために、ピボットの像に関して以下のような制約条件を考える。
左右のピボットは縦方向のみにワープされる。すなわ
ち、

x(i, j1 ) = 1 , x(i, j3 ) = M
とする。

(3)

また、縦方向の像については、

i − w ≤ y(i, j1 ) ≤ i + w
i − w ≤ y(i, j3 ) ≤ i + w(4)のような制限を設ける。本論文では計算量の軽減のため
w = 1 としている。
中間ピボットについては縦横両方向のワープを考える。
その像は、

i − w ≤ x(i, j2 ) ≤ i + w
i − w ≤ y(i, j2 ) ≤ i + w

動的計画法を用いた最適化アルゴリズム

２次元ワープの最適化問題は、制約条件 (4)(5) の下での目的関数 (2) の最小化問題であり、いわゆる多段決定過程を用いて記述できる。このときの段は画像 A の L(i)に対応する。
L(i) のワープによる像は、L(i) を挟む l(i), l(i − 1) 上の左右、中間ピボットのワープによる像で決定される。
そこで、l(i) 上のピボットの像の組を pl(i) と表すと、多段決定過程の第 i 段に属する状態は ( pl(i−1) , pl(i) |i) の組により表される。pl(i) は (4)(5) を満たす範囲で存在するので、この状態は (4)(5) を満たす範囲で存在する。
pl(i) の (4)(5) を満たす範囲での集合を Pl(i) としておく。
段の推移に伴う状態遷移に応じて局所コスト (1) を加算していく。第１段から第 N 段までの状態遷移系列のうち、局所コストの累積値が最小となる系列が、２次元ワープ問題の解に対応する。この最適化状態遷移系列は
図 10 の動的計画法 (ＤＰ) アルゴリズムで探索できる。
ここで、g(pl(i−1) , pl(i) |i) は、状態 ( pl(i−1) , pl(i) |i) に至るまでの、過去のワープ経歴に関する局所コストの最小累積値とする。
これにより画像 A, B 間の距離 D(A, B) を求める。

3.7(ＤＰ漸化式)
3:
for i := 2 to N do
4:
for all pl(i) ∈ Pl(i)5:g(pl(i−1) , pl(i) |i) =min{d(i) + g(pl(i−2) , pl(i−1) |i − 1)}pl(i−1) ∈Pl(i−1)(5)のような制限を設ける。

3.6————————————————————————(初期値設定)1:for all pl(1) ∈ Pl(1)2:g(pl(0) , pl(1) |1) := d(1)

計算量とその効率化 (ビームサーチ)

本節では、図 10 のＤＰアルゴリズムの計算量が画像サ
イズ M に関して多項式オーダーになることを示す。この計算量は、ＤＰ漸化式の計算回数と、ＤＰ漸化式一回当たりの計算量の積で与えられる。
ＤＰ漸化式の計算回数は、図 10 の step5 の繰り返し回数に等しく、全状態数に等しい。W = 2w + 1 と表すと、
両端ピボットには W 、中間ピボットには W 2 の自由度があるから、各 i 段に属する状態数は W ×W 2 ×W = W 4 となる。これと段数 N の積により、漸化式計算回数 O(N W 4 )が得られる。
ＤＰ漸化式１回あたりの計算量は局所コスト (1) の計
2
算量と最小値選択回数の積となる。前者は O( MN ) であり、後者は１状態から遷移可能な状態数に等しいので、
W × W 2 × W = W 4 となる。よって漸化式１回当たり2の計算量は O(W 4 × MN ) となる。

(終了)
6:
D(A, B) :=min

pl(N ) ∈Pl(N )g(pl(N −1) , pl(N ) |N )————————————————————————
図 10: ＤＰアルゴリズム
以上よりＤＰアルゴリズム全体の計算量は O(M 2 W 8 )であり、M 及び W に関して多項式オーダーとなる。
ここからさらに計算量を軽減するために、ビームサー
チという手法を用いる。
ビームサーチとは、動的計画法において、最適経路としての可能性が低いと判断されたものを以後の処理から除外することで探索空間を圧縮し、計算量とメモリ量の低減を同時に実現できる効率化法である (論文 [4])。ここでは、ある段において、一つ前の段から遷移できる状態を、
累積コストの少ない順に１０位までの状態に限定した。
24
24
これにより計算量は O((10 × MN )N W ) = O(M W )まで軽減される。

3.8

辞書の作成

各文字種ごとに１００文字程度の学習データを用意する。同じ文字でも異なる書き方があれば、違う文字種デー
タとして用意する。各文字種ごとに、点列の座標値の平均をとり、平均的なきれいな文字を作成する。この平均的な文字に対して方向線素特徴量 (5 × 2 × 8 = 80 次元) を抽出する。これを全文字種に対して用意したものを、
ストローク数により分けて並べ、辞書を作成する。

3.9

認識結果候補の決定

まず、入力されたストローク数 n の文字データ A から抽出された 10 × 10 × 8 = 800 次元 のベクトルを用いて、外接矩形を 5 × 2 に分割した場合の方向線素特徴量の 5 × 2 × 8 = 80 次元 ベクトルを求め、辞書中の n スト
ローク文字種の特徴ベクトルの中で、ベクトル差の小さいものから最高１０位までを取り出す。この１０位までの候補 B(i) に対して、ＤＰマッチングを行い、画像間の距離 D(A, B(i)) が小さいものから順に３位までを認識
結果候補として出力する。

認識結果候補の Voting 方法

4

この節では、従来の認識結果の複合方法を述べた後、複数の認識手法による認識結果の Voting 方法をいくつか提案する。そして第 5 節にて、単独の認識手法の場合と複数の認識手法を用いた複合認識の場合の文字認識実
験をそれぞれ行い、認識手法が１つの場合と複数の場合、それぞれの Voting 方法の性能等を比較・検討する。
以下では簡単のために、方向線素特徴量による認識手法を L-Method、分割ストロークによる認識手法を DMethod、２次元ワープによる認識手法を W-Method と呼ぶことにする。

4.1

従来の認識結果複合方法(L-Method と D-Method のみ用いる)

L-Method 、D-Method による第 i 位の認識コストをそれぞれ Cl (i), Cd (i) とする。このとき、それぞれの認
識結果の複合コスト Ml (i), Md (i) をMl (i) =1. １つ → その候補を複合認識結果の１位として出力
2. ２つ以上 → 共通の候補同士の複合コストの和を計算しその和が小さいものから順位をつけ出力。
3. 共通の候補が無い場合は L-Method の手法による結果をそのまま複合認識結果とする ([2])。
順位に応じた Voting 方法

この Voting 方法は、各認識候補に順位に応じた得点を持たせ、同じ認識候補同士で得点を足し合わせて (投票して) 高い得点の順に複合認識結果を決める方法である。
ここでは、認識候補が N 位まで用意されている場合に、認識手法によらず第 i 位の候補に (N − i + 1) 点の得点を持たせることにする ([5])。後述の実験では N = 3 と
している。

4.3

数字
ギリシャ文字

信頼度を用いた Voting 方法

ここで言う信頼度とは、認識結果のコストが分かっているときの、その認識結果が正解である条件付確率である。
ある文字データ d の文字 c としての文字認識コストをq(d, c) とする。コストは広い範囲に離散的に値を持つので、一定間隔の区間内のコストを同一視することにする。
具体的には、 q q́ =M(x は y ≤ x である最大の y ∈ {N ∪ 0}) として、これ以降ではコスト q は q́ に変換して考える。M は、それぞれの認識手法毎における正解を与えるコストの最大値をM ax(cost) とすると、

M ax(cost)M=
50

a,b,· · · ,z,A,B,· · · ,Z
0,1,2,· · · ,9α, β, γ, δ, ε, θ, λ, µ, ν, π, φ, ϕ, ω, Φ, Ψ, Ω

特殊記号



, ∞, , √,comma, period

２項演算子+, −, ×, ÷, ±, ∓, |, /, \, ⊕, ∩, ∪関係演算子=, =, ≡, ≡, <, >, ≤, ≥, ⊂, ⊃, ∈, , ∈,/ →lim,log,sin,cos,tan(, ), {, }, [, ]

連文字
括弧類

表 1: 認識対象文字で表される定数である。
ここで d[i] を独立試行で得られたデータ列で、考察する事象に対し出現頻度で確率を近似するに十分な数があるものとする。この d[i] を用いて、P (result(d) = c|q́ = Q́)=Cl (i)Cd (i), Md (i) =Cl (3)Cd (3)と定めておく。
L-Method の候補に対し、D-Method に共通の候補数が4.2

アルファベット#{i : result(d[i]) = c かつq́(d[i], c) = Q́}#{i : q́(d[i], c) = Q́}で近似したものを信頼度とし、これを各認識手法、各文
字種 c[j] ごとに計算してテーブルとして用意しておく。
各認識手法・各認識結果候補は、そのコストと認識結果によりあらかじめ用意されたテーブルから信頼度を得る。この信頼度を持ち票とし、投票をして得点の高い順に３位までを候補として出力する。

4.4

信頼度を用いた Voting 方法

4.3 の Voting 方法に対して、さらに信頼度に順位に応じた重みをつけた持ち票による投票も考える。具体的には、認識候補が N 位まで用意されている場合に、認識手法によらず第 i 位の信頼度に (N − i + 1) をかけたものを得点として持たせて投票する。後述の実験では N = 3としている。

5

認識実験

5.1

認識対象文字と注意する書き方

今現在認識対象としている文字を表 1 で示す。基本的に高校、大学初年度程度の数式に現われる文字・記号を対象としている。特に書く頻度の少ないギリシャ文字などは、対象から外してある。
違う文字同士で区別がつきにくいいくつかの文字に関しては、書き方に制限を加える (表 2)。複数のストロークによって構成される文字については、基本的に書き順は自由である。Ｏや ∞ を書く場合の回転方向は問わない。

5.2

実験データの解説と実験方法

以上の１２１文字について、ペンディスプレイを用いて１０人に３回ずつ書いてもらったデータを実験データとした。
このデータについてP1 =第１位が正解である数
× 100
全データ数

対象文字

制限

C, S (大文字)U, V, W (大文字)X (大文字)P (大文字)Z (大文字)q (小文字)

はじめに縦線をつける
上に横線をつける
上下に横線をつける
下に横線をつける

よる文字はほとんど想定されていなかったため、左傾きの文字の認識はあまり良いとはいえなかった。しかし、W-Method の導入により、左傾きの文字は左に歪んだ文字として捉えられるので、対応が出来る。このデータの複合結果１位も「m」であった。

両端と真ん中に線をつける
最後にはねをつける

表 2: 注意する書き方

P3 =第３位までに正解がある数
× 100
全データ数

を、各認識手法ごと、従来手法 (4.1 の手法)、及びその他の Voting 方法 (4.2-4.4) について求める。4.2-4.4 については２次元ワープを含めない場合と含める場合の両方
を求める。

5.3

実験結果と考察• 認識手法を単独で用いた場合の認識率
認識手法

L-Method
D-Method
W-Method

P1 (%)
92.5
87.6
80.3

P3 (%)
97.2
95.5
92.5

図 11: W-Method 効果１6

図 12: W-Method 効果２

結論

歪みに強い認識手法の導入という観点から、２次元ワープ法による認識手法を導入し、その効果を見るために様々な Voting 方法を用いて認識実験を試みたが、どの Voting
方法を用いても、従来の認識手法に比べ良い結果が得られている点から、２次元ワープ法による認識手法がオン
ライン手書き文字認識にも有用であることが言える。
また、これらの Voting 方法は、本論文に限らず一般的な Voting 方法として用いることができる可能性を持ち、多方面での利用が期待される。

参考文献• 従来手法及び各 Voting 方法を用いた場合の認識率
P1 (%)

P3 (%)

4.1

従来手法

93.8

98.1

4.2

(L+D)
(L+D+W)

93.8
95.0

97.9
98.1

4.3

(L+D)
(L+D+W)

95.7
96.6

99.0
99.3

4.4

(L+D)
(L+D+W)

96.8
97.7

99.0
99.4

２次元ワープを加える前と後での認識率の比較により、２次元ワープを組み込むことが有用であることが分かる。
ここで、最も良い結果だった 4.4 の手法による、WMethod により効果があった具体的な例を挙げてみる。
図 18 は、非常に歪んだ文字の例である。このような文字は、２次元的な伸縮を持つため、ストロークを時系列として眺めただけではその特徴をうまく抽出することは難しい。W-Method は２次元的な情報を用いるため、このような文字でも比較的上位に正しい結果が出力される可能性がある。実際このデータは W-Method の１位に正しい結果が出力されたため、その他の２つの認識手法による結果が悪かったが、複合結果では１位になっている。
図 19 は、左利きの書き手による左に傾いた文字の例である。従来の認識手法においては、左利きの書き手に[1] H.Okamura, T.Kanahori, W.Cong, R.Fukuda,
F.Tamari and M.Suzuki,“Handwriting Interface for
Computer Algebra Systems”, Proc. 4th. AsianTechnology Conference in Mathematics, pp.291-300.
December. 1999.
[2] T.Kanahori, K.Tabata, W.Cong, F.Tamari, and
M.Suzuki, “On-Line Recognition of Mathematical
Expressions Using Automatic Rewriting Method”,
Advances in Multimodal Interfaces —ICMI2000,
Lecture Notes in Computer Science 1948,Springer,
pp. 394-401, 2000.
[3] 内田誠一, 迫江博昭， “区分線形２次元ワープ法の検討”, 電子情報通信学会論文誌 (D-II), vol.J83-D-II,
no.12, pp.2622-2629, Dec. 2000.
[4] 内田誠一, 迫江博昭， “動的計画法に基づく単調２次元ワープ法の検討”, 電子情報通信学会論文誌 (D-II),
Vol.J81-D-II, No.6 pp.1251-1258, June. 1998.
[5] 中野康明, “文字認識・文書理解の最新動向 [V] —認識
後処理と多数決処理— ”, 電子情報通信学会誌, Vol.83,
No.6 pp.467-471, June. 2000.