(57)【要約】【課題】確率的なアプローチを採用することで、手書き数式を認識することを目的とする。ストローク認識と構造認識とが密接に関連しているという立場に立脚して、手書き数式を認識する。【解決手段】手書き数式を読み込む入力手段と、数式を構成するストローク候補のストローク尤度を算出する手段と、入力された数式を、複数のストローク候補から構成される複数の数式候補で表現する手段と、入力された手書き数式を構成する数式部品間の位置関係に関する構造尤度を、確率文脈自由文法を用いて算出する手段と、算出されたストローク尤度及び構造尤度を用いて各数式候補の尤度を算出する手段と、算出された各数式候補の尤度に基づいて数式を決定する手段と、からなる。【選択図】図１
2007072718.tif 000002
【特許請求の範囲】
【請求項１】
手書き数式を読み込む入力手段と、
数式を構成するストローク候補のストローク尤度を算出する手段と、
入力された数式を、複数のストローク候補から構成される複数の数式候補で表現する手段と、
入力された手書き数式を構成する数式部品間の位置関係に関する構造尤度を、確率文脈自由文法を用いて算出する手段と、
算出されたストローク尤度及び構造尤度を用いて各数式候補の尤度を算出する手段と、
算出された各数式候補の尤度に基づいて入力された手書き数式を決定する手段と、
からなる、手書き数式の認識装置。
【請求項２】
数式を決定する手段は、尤度が最大の数式候補を数式とするものである、請求項１に記載の手書き数式の認識装置。
【請求項３】
数式を決定する手段は、
尤度が大きい複数の数式候補を抽出する手段と、
抽出された複数の数式候補から１つの数式候補を選択させる手段と、
からなる、請求項１に記載の手書き数式の認識装置。
【請求項４】
前記構造尤度算出手段は、
観測された各ストロークの外接矩形と、当該ストロークの生成規則の候補ごとに、当該ストローク生成規則候補に基づいて、当該ストロークが書かれようとした領域の尤度分布を算出する手段と、
算出された尤度分布を各ストロークの位置特徴量として、ストロークを含む数式部品間の位置関係により適用確率が決定される確率文脈自由文法により構造尤度を算出する手段と、
を有する、請求項１乃至３いずれかに記載の手書き数式の認識装置。
【請求項５】
前記構造尤度算出手段は、各数式部品毎に、
数式部品がストローク数式部品の場合には、観測された数式部品の外接矩形と当該数式部品の生成規則に基づいて、
数式部品がストローク以外の数式部品の場合には、当該数式部品を構成する各数式部品が書かれようとした領域と、当該数式部品の生成規則に基づいて、
当該数式部品が書かれようとした領域の尤度分布を算出する、請求項１乃至４いずれかに記載の手書き数式の認識装置。
【請求項６】
前記ストローク数式部品が書かれようとした領域の尤度分布は、前記外接矩形の縦中心、縦サイズ、横始点、横終点のパラメータと、各ストローク生成規則毎に設定された確率変数とから算出される、
請求項４，５いずれかに記載の手書き数式の認識装置。
【請求項７】
前記装置は、複数の数式生成規則からなる文脈自由文法、および、数式部品間の位置関係によって決定される各数式生成規則の適用確率を格納する手段を有している、請求項１乃至６いずれかに記載の手書き数式の認識装置。
【請求項８】
手書き数式を読み込む入力ステップと、
数式を構成するストローク候補のストローク尤度を算出するステップと、
入力された数式を、複数のストローク候補から構成される複数の数式候補で表現するステップと、
入力された手書き数式を構成する数式部品間の位置関係に関する構造尤度を、確率文脈自由文法を用いて算出するステップと、
算出されたストローク尤度及び構造尤度を用いて各数式候補の尤度を算出するステップと、
算出された各数式候補の尤度に基づいて入力された手書き数式を決定するステップと、
からなる、手書き数式の認識方法。
【請求項９】
数式を決定するステップは、尤度が最大の数式候補を数式とするものである、請求項８に記載の手書き数式の認識方法。
【請求項１０】
数式を決定するステップは、
尤度が大きい複数の数式候補を抽出するステップと、
抽出された複数の数式候補から１つの数式候補を選択させるステップと、
からなる、請求項８に記載の手書き数式の認識方法。
【請求項１１】
前記構造尤度算出ステップは、
観測された各ストロークの外接矩形と、当該ストロークの生成規則の候補ごとに、当該ストローク生成規則候補に基づいて、当該ストロークが書かれようとした領域の尤度分布を算出するステップと、
算出された尤度分布を各ストロークの位置特徴量として、ストロークを含む数式部品間の位置関係により適用確率が決定される確率文脈自由文法により構造尤度を算出するステップと、
を有する、請求項８乃至１０いずれかに記載の手書き数式の認識方法。
【請求項１２】
前記構造尤度算出ステップは、各数式部品毎に、
数式部品がストローク数式部品の場合には、観測された数式部品の外接矩形と当該数式部品の生成規則に基づいて、
数式部品がストローク以外の数式部品の場合には、当該数式部品を構成する各数式部品が書かれようとした領域と、当該数式部品の生成規則に基づいて、
当該数式部品が書かれようとした領域の尤度分布を算出する、請求項８乃至１１いずれかに記載の手書き数式の認識方法。
【請求項１３】
前記ストローク数式部品が書かれようとした領域の尤度分布は、前記外接矩形の縦中心、縦サイズ、横始点、横終点のパラメータと、各ストローク生成規則毎に設定された確率変数とから算出される、
請求項１１，１２いずれかに記載の手書き数式の認識方法。
【請求項１４】
手書き数式を認識するために、コンピュータを、請求項１乃至７に記載のいずれかの手段として機能させるためのコンピュータプログラム。
【請求項１５】
手書き数式を認識するために、コンピュータを、請求項１乃至７に記載のいずれかの手段として機能させるためのコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１６】
手書き数式を読み込む入力手段と、
数式を構成する終端数式部品候補の終端数式部品尤度を算出する手段と、
入力された数式を、複数の終端数式部品候補から構成される複数の数式候補で表現する手段と、
入力された手書き数式を構成する終端数式部品及び非終端数式部品を含む数式部品間の位置関係に関する構造尤度を、確率文脈自由文法を用いて算出する手段と、
算出された終端数式部品尤度及び構造尤度を用いて各数式候補の尤度を算出する手段と、
算出された各数式候補の尤度に基づいて入力された手書き数式を決定する手段と、
からなる、手書き数式の認識装置。
【請求項１７】
前記終端数式部品は、ストロークである、請求項１６に記載の手書き数式の認識装置。
【請求項１８】
前記終端数式部品は、シンボルである、請求項１６に記載の手書き数式の認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、手書き数式の認識装置及び方法に関するものである。
【背景技術】
【０００２】
現在コンピュータへの数式入力は、TeXやmatlabなどの専用言語によるテキスト記述やマウスで操作する数式エディタ等が主である。しかしこれらの入力方法はトレーニングが必要であり直感的ではない。ペンタブレット等による直感的な数式の入力が実現されれば、論文等への数式入力、数式検索や数値計算ソフトの入力インタフェースなど教育研究分野において幅広い応用の可能性がある。
【０００３】
オンライン手書き数式認識に関しては多くの既存研究がある（非特許文献１）。これらの研究では数式の認識をシンボル認識と構造認識の２段階に分けて行う。まず入力ストローク系列をシンボル単位に分割してシンボル認識を行う。そして認識されたシンボル同士をそれぞれの位置関係を用いたルールにより結合し数式を構成する。
【０００４】
ところが、数式は必ず厳密な文法に沿って記述されるが、数１に示すように手書き数式はその揺らぎのため必ずしも一通りに解釈されるとは限らない。数１は、数式認識の曖昧性を示す例であって、２ｘなのか２ｘなのかは人間にとってすら必ずしも明らかではない。
【数１】
2007072718.tif 000003
【０００５】
またルールベースを用いた既存手法においてはストローク認識と構造認識は完全に分離した問題として扱われていたが、数２に示すように構造の認識とストロークの認識は切り離すことができない問題である。数２は、構造の変化がストローク認識に影響を与える例であり、中央部分は左式では括弧“)(”である可能性があるが、右式では“x”と解釈するのが自然である。
【数２】
2007072718.tif 000004
【非特許文献１】K.F.Chan,D.Y.Yeung: “Mathematical Expression Recognition: A Survey” ‘Int. J.DocumentAnal., vol.3,no.1,pp.3.15,2000.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、従来のルールベースのアプローチに対し、確率的なアプローチを採用することで、手書き数式を認識することを目的とするものである。本発明の他の目的は、ストローク認識と構造認識とが密接に関連しているという立場に立脚して、手書き数式を認識することにある。
【課題を解決するための手段】
【０００７】
本発明は、手書き数式認識においては、様々な数式候補の中で尤度が最大となるものを求めるという確率的な認識が本質的であると考え、ストローク尤度と構造尤度の積を最大化する数式候補を求める問題として定式化する点に特徴を有する。ストローク尤度と構造尤度の積が最大となる数式候補を求めるにあたり、ストローク尤度は既存手法のモデルで計算することができ、構造尤度は確率文脈自由文法により計算することができる。また、本発明に係る構造尤度の計算においては、数式部品同士の位置関係により、数式生成規則の適用確率が決定される。１つの好ましい態様では、数式部品同士の位置関係を評価するための位置特徴量として、数式部品が書かれようとした領域（隠れ筆記領域）の尤度分布が用いられる。また、観測された各ストロークの外接矩形を位置特徴量として構造尤度を算出してもよい。数式候補の尤度は、CYK-algorithmにより効率的に計算可能である。本発明に係る手書き認識は、手書き数式認識装置、手書き数式認識方法、手書き数式をコンピュータに実行させるためのコンピュータプログラムあるいは当該プログラムを記録したコンピュータ読み取り可能媒体として構成される。以下に本発明の具体的な構成を説明する。
【０００８】
本発明に係る手書き数式認識装置は、手書き数式を読み込む入力手段と、数式を構成するストローク候補のストローク尤度を算出する手段と、入力された数式を、複数のストローク候補から構成される複数の数式候補で表現する手段と、入力された手書き数式を構成する数式部品間の位置関係に関する構造尤度を、確率文脈自由文法を用いて算出する手段と、算出されたストローク尤度及び構造尤度を用いて各数式候補の尤度を算出する手段と、算出された各数式候補の尤度に基づいて数式を決定する手段と、からなる。１つの態様では、数式を決定する手段は、尤度が最大の数式候補を数式とするものである。他の態様では、数式を決定する手段は、尤度が大きい複数の数式候補を抽出する手段と、抽出された複数の数式候補から１つの数式候補を選択する手段と、からなる。
【０００９】
１つの好ましい態様では、前記構造尤度算出手段は、観測された各ストロークの外接矩形と、当該ストロークの生成規則の候補ごとに、当該ストローク生成規則候補に基づいて、当該ストロークが書かれようとした領域の尤度分布を算出する手段と、算出された尤度分布を各ストロークの位置特徴量として、ストロークを含む数式部品間の位置関係により適用確率が決定される確率文脈自由文法により構造尤度を算出する手段と、を有する。１つの好ましい態様では、外接矩形を評価するのは数式部品の中でもストロークのみなので、ストロークについては、その隠れ筆記領域尤度分布が、実際の外接矩形と、ストローク生成規則(終端記号生成規則)の候補(＝そのストロークが何であるかの候補)、の二つにより決まり(P(b|a,F))、そのほかの数式部品については、その数式部品の生成規則(非終端記号生成規則)により決まる(P(al,ar|ap,R))。
【００１０】
１つの好ましい態様では、前記ストローク数式部品が書かれようとした領域の尤度分布は、前記外接矩形の縦中心、縦サイズ、横始点、横終点のパラメータと、各ストローク生成規則毎に設定された確率変数とから算出される。前記装置は、複数の数式生成規則からなる文脈自由文法、および、数式部品間の位置関係によって決定される各数式生成規則の適用確率を格納する手段を有している。
【００１１】
本発明に係る手書き数式認識方法は、手書き数式を読み込む入力ステップと、数式を構成するストローク候補のストローク尤度を算出するステップと、入力された数式を、複数のストローク候補から構成される複数の数式候補で表現するステップと、入力された手書き数式を構成する数式部品間の位置関係に関する構造尤度を、確率文脈自由文法を用いて算出するステップと、算出されたストローク尤度及び構造尤度を用いて各数式候補の尤度を算出するステップと、算出された各数式候補の尤度に基づいて入力された手書き数式を決定するステップと、からなる。手書き数式認識方法のより具体的な構成については、上記手書き認識装置に係る記載、及び、後述の実施の形態に記載されている。
【００１２】
本発明に係る手書き数式認識装置は、具体的なハードウェアとしては、入力手段、出力手段、記憶手段、演算手段、表示手段を備えたコンピュータから構成される。したがって、本発明に係る手書き数式認識は、手書き数式を認識するために、コンピュータを、手書き数式を読み込む入力手段と、数式を構成するストローク候補のストローク尤度を算出する手段と、入力された数式を、複数のストローク候補から構成される複数の数式候補で表現する手段と、入力された手書き数式を構成する数式部品間の位置関係に関する構造尤度を、確率文脈自由文法を用いて算出する手段と、算出されたストローク尤度及び構造尤度を用いて各数式候補の尤度を算出する手段と、算出された各数式候補の尤度に基づいて数式を決定する手段と、して機能させるためのコンピュータプログラム、あるいは、当該コンピュータプログラムを記憶したコンピュータ読み取り可能な媒体として構成される。手書き数式認識を実行するためのコンピュータプログラムのより具体的な構成については、上記手書き認識装置に係る記載を援用することができる。
【００１３】
また、本発明では、基本的にストロークを最小単位として扱うが、シンボルを最小単位として扱うことも可能である。ストローク、シンボルは確率文脈自由文法における終端数式部品であり、したがって、本発明が採用した他の技術手段は、手書き数式を読み込む入力手段と、数式を構成する終端数式部品候補の終端数式部品尤度を算出する手段と、入力された数式を、複数の終端数式部品候補から構成される複数の数式候補で表現する手段と、入力された手書き数式を構成する終端数式部品及び非終端数式部品を含む数式部品間の位置関係に関する構造尤度を、確率文脈自由文法を用いて算出する手段と、算出された終端数式部品尤度及び構造尤度を用いて各数式候補の尤度を算出する手段と、算出された各数式候補の尤度に基づいて入力された手書き数式を決定する手段と、からなる。この技術手段も、手書き数式認識装置、手書き数式認識方法、手書き数式をコンピュータに実行させるためのコンピュータプログラムあるいは当該プログラムを記録したコンピュータ読み取り可能媒体として構成される。1つの態様では、手書き数式入力を分割する最小単位がストロークであり、前記終端数式部品は、ストロークである。他の態様では、手書き数式入力を分割する最小単位がシンボルであり、前記終端数式部品は、シンボルである。
【００１４】
ここで、本発明を理解するのに必要な用語について説明する。
数式部品：ストローク数式部品とそれ以外の数式部品(文字、項、因数などをいい、本明細書では、上位数式部品と定義する)をいう。非終端記号生成規則に関わるものはすべて数式部品である。また終端記号生成規則においては左辺がストローク数式部品で、右辺は実際のストローク(これ自体は数式部品ではない)である。
親数式部品：各生成規則について、左辺にある数式部品(１つ)を親数式部品という。
子数式部品：各火終端記号生成規則について、右辺にある数式部品をいう(単数または複数である。生成規則がチョムスキー標準形で表されていれば常に２つである。)
ストローク：「ストローク」は実際の入力(サンプル点列)のペンダウンからペンアップまでを指す「入力ストローク・実際のストローク」の意味と、入力ストロークの認識候補としての「ストローク数式部品」の意味がある。入力ストロークは実際のサンプル点列であり、ストローク数式部品はシンボリックな情報である。終端記号生成規則により、ストローク数式部品から入力ストロークが生成される。
ストロークの生成規則：ストローク数式部品から、入力ストロークが生成される終端記号生成規則をいう。
ストロークの生成規則の候補：入力ストロークそれぞれについて、複数のストローク認識候補が有り得る。すなわちその入力ストロークが生成された終端記号生成規則は一意に特定することはできず、複数の終端記号生成規則候補を同時に考える必要がある。つまりある入力ストロークについて、それがマイナス→入力ストローク、という終端記号生成規則から生成されたかもしれないし、プラスの横棒→入力ストローク、という終端記号生成規則から生成されたかもしれない、と考える。それぞれの規則が適用された尤度はストローク尤度計算により行われる。
ストローク列：入力を入力ストロークの列と見た場合の表現である。
シンボル：数式部品の一部である。いわゆる「文字」である。単独で意味を持つ最小単位である。
終端数式部品：終端記号生成文法の親数式部品のことを指す。終端数式部品から、入力ストロークは生成される。本手法においてはストローク数式部品である。尚、必ずしもストロークを最小単位とはしない数式認識も可能である。何らかの前処理によって数式をばらばらのシンボルに分割することができれば、シンボルを最小単位にして同じような認識が行える。その場合、終端数式部品はシンボルとなる。
非終端数式部品：上位数式部品と言ったものと同じである。ストローク数式部品以外の数式部品(シンボルを最小単位とする場合は、シンボル数式部品以外の数式部品)をいう。これから直接入力ストロークを生成する生成規則はない。
隠れ筆記領域の尤度分布：数式部品には、その数式部品が占める部分をあらわす隠れ筆記領域というのが存在し、この「数式部品が書かれようとした領域」を隠れ筆記領域という。例えば、数式部品同士が「横」の位置関係にあるというのは、それぞれの数式部品の隠れ筆記領域が横に接続していると考える。ストローク数式部品（終端数式部品）からは入力ストロークが生成されるが、生成される入力ストロークの位置（外接矩形）はそのストローク数式部品の隠れ筆記領域に依存して、確率的に決まる。したがってある入力ストロークの観測とその入力ストローク生成規則候補が得られたとき、それを生成したストローク数式部品の隠れ筆記領域の尤度分布を得ることができる。隠れ筆記領域の尤度分布は、外接矩形が得られたときの隠れ筆記領域の確率分布として算出することができる。
【発明の効果】
【００１５】
本発明の手書き数式の認識は、従来の認識手法に比べて、特に、構造認識において有利である。また、ストローク認識誤りを構造認識プロセスで補正することも可能であり、結果として、より正確な手書き数式の認識ができる。
【発明を実施するための最良の形態】
【００１６】
［Ａ］手書き数式認識の基本構成
本発明は、確率文脈自由文法による確率的なオンライン手書き数式認識に関するものであり、時系列的に入力された手書き数式情報から数式を認識する。本発明では、数式の認識を、ストローク尤度と構造尤度の積を最大化する数式候補を求める問題として定式化する。図１に示すように、手書き数式認識手法は、各ストロークの尤度計算と、数式部品（ストロークやシンボル）の位置関係による構造尤度計算と、からなる。
【００１７】
ストローク尤度とは、ストロークモデルから実際にその手書きストロークが生成される確率であり、ストローク尤度は既存のモデルベースの文字認識手法により尤度計算を行うことができる。図３に基づいて言うと、ストローク尤度は、どれくらいの確率で「そのストロークである」のかということであり、３つの手書きシンボルについて、ストローク”a”である尤度を示している。さらに、ストローク尤度について図２に基づいて説明すると、時系列にしたがって、第１ストロークがルート記号（候補）である尤度は０．２であり、v（候補）である尤度は０．２であり、分数線（候補）である尤度は０．１である。第２ストロークがa（候補）である尤度は０．２であり、d（候補）である尤度は０．１である。第３ストロークが2（候補）である尤度は０．２であり、z（候補）である尤度は０．１である。第４ストロークがマイナス記号（候補）である尤度は０．２であり、プラス記号の横棒−（候補）である尤度は０．１である。第５ストロークが1（候補）である尤度は０．２であり、プラス記号の縦棒｜（候補）である尤度は０．１である。第６ストロークが6（候補）である尤度は０．２であり、Gの1画目（候補）である尤度は０．１である。
【００１８】
構造尤度とは、数式候補から実際にそのストローク同士の位置関係が生成される確率である。図３に基づいて言うと、構造尤度とは、どれくらいの確率で「その構造であるのか」ということであり、シンボルa,bからなる３つのパターンについて、２つのシンボルが「横につながっている尤度」を示している。構造尤度は後述する確率文脈自由文法(Stochastic Context-Free Grammar:SCFG)によりモデル化することで、計算が可能である。
【００１９】
本発明では、考えられる様々な数式候補の中で、ストローク尤度×構造尤度を最大化する数式候補を求め、尤度が最大の数式候補を、手書き数式として認識する。図３に示すように、図２のように互いに直交状に交差する二つのストロークがあった場合に、ストローク尤度だけで見ると、第４ストロークがマイナス記号（候補）である尤度は０．２であり、プラス記号の横棒−（候補）である尤度は０．１であり、また、第５ストロークが1（候補）である尤度は０．２であり、プラス記号の縦棒｜（候補）である尤度は０．１である。しかしながら、-1（候補）となる構造尤度が低く、+（候補）となる構造尤度が高いため、ストローク尤度とシンボルの構造尤度との積において、+としての候補が優位となる。
【００２０】
［Ｂ］確率文脈自由文法による数式構造のモデル化
文脈自由文法(Context-Free Grammar:CFG)はA→B,AB→C,ABC→D等の形で記述される文法で、数式のように再帰性をもつ言語の生成・解析に適する。例えば図５にあるような単純な数個の数式生成規則を繰り返し適用することにより、a,b,cの3文字からなる様々な数式(例えばａｂａｂｃなど)が解析可能である。
【００２１】
確率文脈自由文法SCFGはCFGにおける生成規則が適用確率をもつ文法である。適用確率は、数式部位品同士の位置関係により決定される。例えば、図５において上から3番目の生成規則の適用確率は、「いかに文字に対して式の位置が右上らしいか」により定まる。このように手書き数式の構造尤度は、数式部品間の位置関係により適用確率が定まるSCFGによりモデル化ができる。SCFGによる構造尤度はCYK-algorithmにより効率的に計算可能である。
【００２２】
［Ｃ］数式文法
数式文法は、ストローク（終端）数式部品から実際のストロークを生成する終端記号生成規則と、ストローク以外の（非終端）数式部品から単数または複数の、別の数式部品を生成する非終端記号生成規則からなる。
［Ｃ−１］非終端記号生成規則
数式文法は、例えば多項式を扱う場合は、図６に示すような文脈自由文法を用意すれば十分である。文脈自由文法を構成する各数式生成規則は、数式部品間の位置関係により適用される確率が設定されている。図６に示す文脈自由文法をチョムスキー標準形に等価変換したもののうち、図１２の数式生成にかかわるものを挙げると、図７に示す５つとなる。
【００２３】
［Ｃ−２］終端記号生成規則
終端記号生成規則Fは、ストローク数式部品∈ＳＴから実際の手書きストロークを生成する規則である。図１２に関連する終端記号生成規則は、図８に示す５つである。
【００２４】
［Ｄ］位置特徴量としての隠れ筆記領域の尤度分布
数式部品間の位置関係の評価は単純な問題ではない。従来、位置関係の特徴量として一般に用いられる外接矩形では図９のように多様なシンボル形状を統一的に扱うことはできず、文字カテゴリごとに場合分けする必要が生じる。また、数式にはアルファベット以外にもアクセント、ドット、カンマ等特殊な形状のシンボルが多いため場合分けの数が多くなり、結果としてSCFGの規則が複雑化してしまう。図９は、外接矩形の限界を示す例であり、ｑｘとｄｘのシンボル同士の位置関係は異なるが、外接矩形は等しい（非特許文献１より引用）。
【００２５】
本発明では、この問題を回避するため、様々な数式部品（シンボルやストローク）を統一的に扱う特徴量とし隠れ筆記領域の尤度分布を用いる。隠れ筆記領域は、実際に書かれた数式部品（シンボルやストローク）が「どこに書かれようとしたのか」を表すものであり、この「書かれようとした領域」の尤度分布を算出する。先ず、隠れ筆記領域の背景としての数式の生成モデルを説明する。図１７に示すように、数式“abcd”は、人間の数式生成モデルを仮定して、以下のように書かれると考える。
(1)はじめに数式全体の中心と縦サイズを決定する。
(2)最初の文字”a”の始点と終点を決定。“a”の書かれようとする領域が定まる。
(3)その領域に”a”が書かれる。実際に書かれる場所は確率的な揺らぎを持つ。
(4)次に”b”の終点を決定する。“b”の書かれようとする領域が定まる。
(5)その領域に”b”が書かれる。”b”は領域の上方に書かれがちである。
(6)同様に”c”が書かれる。
(7)“d”の中心と縦サイズは、“c”の縦中心と縦サイズから確率的に決定される。
(8)“d”の終点を決定し、その領域に”d”が書かれる。
すなわち、我々は数式を、横方向に一貫性を持った、隠れたマス目にそって書いている、という仮定である。そして、構造尤度を「この生成モデルから生成された確率」であると考える。
【００２６】
上記のような数式生成モデルを仮定した上で、そのモデルにおける「数式部品を書こうとする矩形領域」を、隠れ筆記領域とする。このモデルにおいて、各ストロークは、それぞれのストローク数式部品の隠れ筆記領域に対して、確率的な揺らぎを持って書かれると仮定する。言い換えると、各ストロークが実際に書かれる位置・大きさ（この２つを外接矩形で表すことができる）は、それぞれのストローク数式部品の隠れ筆記領域から確率的に決定される。また、各数式部品の隠れ筆記領域同士は、一定の位置関係を持っている。例えば数式部品ABCが、A→B+Cの規則により生成されたときは（たとえばA:2(x+1)、B:2、C:(x+1)など）、AとBとCの各隠れ筆記領域は、一定の位置関係（”横“）を持つ。
【００２７】
図１１は、隠れ筆記領域の概念図である。数式abcは上の図ような矩形領域に確率的なゆらぎを持って書かれると考える。このときaやcと比べてbは長方形領域の上方に書かれがちである。一方、実際に下の図のように書かれた文字がある場合、逆にその文字の「書かれようとした矩形領域」である「隠れ筆記領域」は尤度分布を持つ。この「隠れ筆記領域書」の尤度分布を位置特徴量として、全ての数式部品（シンボル）の位置を統一的に扱う。隠れ筆記領域の尤度分布によりアルファベット、ドット、カンマやアクセントを全て同じ特徴量で扱うことができると考えられる。
【００２８】
隠れ筆記領域の尤度分布について、さらに、詳述する。あるストロークが書かれたとき、書かれようとした領域の尤度分布は、書かれたストロークの外接矩形と、そのストロークの生成規則F(何のストロークを意図して書かれたのか)が得られた時の隠れ筆記領域の条件付確率分布である。ある隠れ筆記領域は４つのパラメータa=(ac,as,ab,ae)で表すことができる。ここで、ac：縦中心、as：縦サイズ、ab：横始点、ae：横終点、である。その確率分布P(a)を表す場合は、4次元ベクトルa=(ac,as,ab,ae)の、4次元空間内での確率分布を表す必要がある。ここで4次元空間内での対角共分散の正規分布(すなわちac,as,ab,aeがそれぞれ独立に正規分布をなす)を仮定すると、P(a)を表すパラメータはその平均ベクトルと共分散行列μa=(μac,μas,μab,μae)、σa=diag(σac,σas,σab,σae)によって表される。実際の各ストロークの外接矩形b=(bc,bs,bb,be）は、隠れ筆記領域a=(ac,as,ab,ae)から確率的にP(b|a,F)に従い得られると考える。逆に各ストロークの外接矩形bが得られたときに、隠れ筆記領域aの確率分布は、P(b|a,F)をaの関数と見ることで得られる。この関数があらかじめ各ストローク生成規則に対して用意してある。各ストロークからどのような隠れ筆記領域の尤度分布が生成されるかを、予め学習しておく。入力ストロークの外接矩形が同じであっても、ストロークの認識結果（生成規則）によって隠れ筆記領域の尤度分布は変化する。例えば、外接矩形が同じであっても、ストローク生成規則候補が“ａ→(実際のストローク)”である場合と“ｄ→(実際のストローク)”である場合とでは、隠れ筆記領域の尤度分布は異なる。実際の各ストロークの外接矩形ｂのパラメータ(bc,bs,bb,be、ここで、ｂc：縦中心ｂs：縦サイズ、ｂb：横始点、ｂe：横終点、である)に対して、隠れ筆記領域ａの尤度分布のパラメータ（確率変数)が、ac=bc+Pc, as=
bs+Ps，ab=bb+Pb, ae=be+Peにより決まると考え、各ストロークについてPc,Ps,Pb,Peを学習しておき、観測された数式部品の外接矩形に基づいて、当該数式部品が書かれようとした領域の尤度分布を算出するための関数を格納しておく。
【００２９】
［Ｅ］数式部品の隠れ筆記領域を用いた構造尤度計算
［Ｅ−１］各種定義
ストローク数式部品の集合を、
【数３】
2007072718.tif 000005
とし、ストローク数式部品を含む全数式部品の集合を、
【数４】
2007072718.tif 000006
とする。また、数式部品同士の位置関係集合を、
【数５】
2007072718.tif 000007
とする。
【００３０】
数式生成規則のうち、非終端記号生成規則の集合を集合Ｒとする。各非終端記号生成規則の持つ情報は、Ｒ(∈Ｒ）＝（Ｒｐ∈ＭＰ，Ｒｌ∈ＭＰ，Ｒｒ∈ＭＰ，ＲＲＰ∈ＲＰ）である。ここで、Ｒｐ，Ｒｌ，Ｒｒ，ＲＲＰは順に、親数式部品名、子数式部品名（左）、子数式部品名（右）、子数式部品の満たす位置関係を示す。
【００３１】
終端記号生成規則の集合をＦとする。各終端記号生成規則の持つ情報は、Ｆ（∈Ｆ）＝（Ｆｐ∈ＳＴ）である。規則の一覧例を図６に記載する。
【００３２】
観測される手書き数式の各ストロークについて、第i番目のストローク形状データ（サンプル座標列情報）をｔｉ、その外接矩形ｂｉとして表現し、観測される手書き数式を、
【数６】
2007072718.tif 000008
と表す。ここでＮは観測のストローク総数である。
【００３３】
任意の数式候補Ｈは、入力数式、
【数７】
2007072718.tif 000009
の場合には、図１２のような木構造で表現される。この木構造は数式生成規則の入れ子形式、たとえば
【数８】
2007072718.tif 000010
のように記述することができる。
【００３４】
［Ｅ−２］数式部品の「筆記領域」
各数式部品の背後には図１３のように矩形の隠れ筆記領域が存在すると仮定する。数式生成規則Ｒｉの親数式部品Ｒｉｐの筆記領域を、
【数９】
2007072718.tif 000011
と表す。ここで、ａｉｃ，ａｉｓ，ａｉｂ，ａｉｅは、図１４に示す各座標と長さとする。
【００３５】
次に、各位置関係について、親数式部品筆記領域がａｐであるとき子数式部品筆記領域がａｌ，ａｒである確率、
【数１０】
2007072718.tif 000012
を定める。
【００３６】
［Ｅ−２−１］位置関係：横
位置関係が横である、という条件を以下の式により記述する。
【数１１】
2007072718.tif 000013
すなわち、
【数１２】
2007072718.tif 000014
と表せる（δ（ｘ）はDiracのDelta関数）
【００３７】
［Ｅ−２−２］位置関係：右上
位置関係が右上である、という条件を以下の式により記述する。
【数１３】
2007072718.tif 000015
ここで、ｑ右上１，ｑ右上２は、それぞれあらかじめ与えられた正規分布
【数１４】
2007072718.tif 000016
に従う。したがって、
【数１５】
2007072718.tif 000017
となる。
【００３８】
［Ｅ−２−３］その他の位置関係
右下その他の位置関係についても同様に、
【数１６】
2007072718.tif 000018
の形、もしくは、あらかじめ与えられた正規分布
【数１７】
2007072718.tif 000019
に従う確率変数ｑを導入し、
【数１８】
2007072718.tif 000020
のように記述する。
【００３９】
［Ｅ−３］終端記号生成規則の適用確率
ストローク出力ｔ，ｂが、そのストロークの筆記領域と終端記号生成規則ａ，Ｆにより生成された確率Ｐ（ｔ，ｂ｜ａ，Ｆ）を以下のように定義する。
【数１９】
2007072718.tif 000021
右辺第一項はストローク形状ｔがストロークＦｐである確率（ストローク尤度）であり、既存の文字認識手法により計算可能である。右辺第二項は終端記号生成規則Ｆによりストロークが筆記領域ａに生成された場合の、実際のストローク外接矩形ｂの確率分布である。この確率をａ−ｂの正規分布
【数２０】
2007072718.tif 000022
により定義する。
【００４０】
［Ｅ−４］尤度の計算
数式候補Ｈから観測（ｔ，ｂ）を得る尤度の計算方法を、図１２の例において示す。各数式部品の筆記領域をａｉとすると、
【数２１】
2007072718.tif 000023
となる。積分記号右下の文字はどの文字についての積分かを表したものである。Π11i=1Ｐ（ｔｉ｜ＲＭＰ）は、ストローク尤度であり、既存の文字認識手法で計算可能である。また、残りの部分は構造尤度の式であるが、これは各文字部品の筆記領域の確率分布Ｐ（ａｉ）において、ａｉｃ，ａｉｓ，ａｉｂ，ａｉｅを独立に扱う近似
【数２２】
2007072718.tif 000024
を行うことにより以下のように逐次計算が可能である。
【００４１】
（１）はじめに、
【数２３】
2007072718.tif 000025
の部分を計算する。
(a)P(b2|a2,R2)，P(b3|a3,R3)は、b2,b3が与えられた時は、それぞれa2,a3の正規分布である。
(b)P(a2,a3|a7,R7）が式１のように与えられていれば、すなわち、
【数２４】
2007072718.tif 000026
と記述されていれば、
【数２５】
2007072718.tif 000027
となる。ここで、正規分布関数の積は正規分布関数であり、さらに、正規分布関数とdelta関数の畳み込みも正規分布関数であるから、Ｐ（ａ２），Ｐ（ａ３）が正規分布であることよりＰ（a2,a3|a7,R7）は、ａ7の正規分布関数となる。
(c)Ｐ（a2,a3|a7,R7）が式２のように与えられていれば、すなわち、
【数２６】
2007072718.tif 000028
と記述されているときも同様に、
【数２７】
2007072718.tif 000029
となり、ここで、P(a2),P(a3),P(q)が正規分布であることより、やはりＰ（a2,a3|a7,R7）はa7の正規分布関数となる。
(d)よって
【数２８】
2007072718.tif 000030
は、ａ７の正規分布関数Ｐ（ａ７）となる。
【００４２】
（２）したがって、その１つ外側の積分は、
【数２９】
2007072718.tif 000031
となる。ここで、Ｐ（ａ７）、Ｐ(b4|a4,R4)がともに正規分布であることから、先ほどと同様に、この積分値は正規分布Ｐ（ａ８）となる。
【００４３】
（３）以下同様に積分計算を外側に向かって行うことにより、構造尤度は、∫Ｐ(ａ１１)ｄａ１１となり、この積分計算で構造尤度が求められる。
【００４４】
［Ｅ−５］CYK-algorithmによる尤度の計算
数式候補の尤度の計算は、CYK-algorithmにより効率的に解析することができる。図１５、図１６に尤度計算の例を示す。図１５は、４ストロークの時系列が、“２”→“ａ”→“２”→“ルート記号”である場合を示す。例えば、“２ａ”である尤度は、０．１（２の尤度）Ｘ０．２（ａの尤度）×０．０５（横連結尤度）＝０．００１である。“２ａ“である尤度は、０．１（２の尤度）Ｘ０．２（ａの尤度）×０．０２５（右上連結尤度）＝０．００１である。４ストローク全体としては、√２ａ２（候補）の尤度が０．００００００１、√２ａ２（候補）の尤度が０．０００００００５である。図１６は、４ストロークの時系列が、”（“→”５の部分“→”５の部分“→“）”である場合を示す。4ストローク全体としては、（５）（候補）である尤度が０．００００００１であり、１５１（候補）である尤度が０．０００００００５である。
【００４５】
［Ｆ］動作確認実験
［Ｆ−１］隠れ筆記領域の尤度分布の有効性の確認
IEEE Transactionの中で中程度の複雑さを持つと思われる8数式(ストローク数30〜60)同一筆者による各10回ずつ計80の手書き数式を評価データとし、ストロークの認識が完全に行われた条件下で構造認識実験を行った。各ストロークの隠れ筆記領域の尤度分布を定めるパラメータはヒューリスティックに決定し、数式文法は図５のものの他に分数と平方根およびアクセントを許容した。その結果80数式中63数式の構造が完全に認識された。また誤りはサブスクリプトのミス等の局所的なもののみであり、パラメータのチューニングによりさらに精度の向上が可能であると考えられる。この実験により隠れ筆記領域の尤度分布が構造尤度計算の特徴量として有効であることが確認された。
【００４６】
［Ｆ−２］システム全体の動作確認実験
ストローク尤度を手動で設定することで、システム全体の動作を確認した。［Ｆ−１］で用いた8数式各1回ずつ計8の手書き数式を評価データとし、ストロークの認識誤りの構造認識による補正を確認するため、各ストロークのストローク尤度1位候補を全てアルファベットの''a''、2位を正解ストロークとし、数式の認識を行った。その結果最終的に正解ストロークが多数認識結果に含まれた。この実験により、ストローク認識誤りが構造認識において補正されうることが確認された。また、上記実験ではストローク尤度を人手で与えたが、ストローク尤度計算に隠れマルコフモデルHMMを用いてもよい。
【産業上の利用可能性】
【００４７】
本発明は、オンライン手書き数式認識として利用され得るものであり、具体的には、教育、論文作成、数式検索のインタフェース、数値計算ソフトのインタフェース等に利用可能である。
【図面の簡単な説明】
【００４８】
【図１】手書き数式認識の全体構成を説明する図である。
【図２】ストローク候補のストローク尤度を説明する図である。
【図３】ストローク尤度と構造尤度の関係を説明する図である。
【図４】確率文脈自由文法を説明する図である。
【図５】数式を生成する確率文脈自由文法の例を示す図である。
【図６】数式を生成する確率文脈自由文法の例を示す図である。
【図７】図６に示す文法をチョムスキー標準形に等価変化したもので、図１２の数式生成に関係する規則を示す図である。
【図８】図１２に関連する終端記号生成規則を示す図である。
【図９】外接矩形の限界を示す例である。
【図１０】数式部品間の位置関係の評価を説明する図である。
【図１１】隠れ筆記領域の概念図である。
【図１２】手書き数式と、それに対する正解数式候補の木構造の対応を示す図である。
【図１３】数式部品と隠れ筆記領域を示す図である。
【図１４】隠れ筆記領域のパラメータを示す図である。
【図１５】CYK-algorithmを用いた尤度計算の例を示す図である。
【図１６】CYK-algorithmを用いた尤度計算の例を示す図である。
【図１７】人間の数式生成モデルを説明する図である。
【図１】
2007072718.tif 000032
【図２】
2007072718.tif 000033
【図３】
2007072718.tif 000034
【図４】
2007072718.tif 000035
【図５】
2007072718.tif 000036
【図６】
2007072718.tif 000037
【図７】
2007072718.tif 000038
【図８】
2007072718.tif 000039
【図９】
2007072718.tif 000040
【図１０】
2007072718.tif 000041
【図１１】
2007072718.tif 000042
【図１２】
2007072718.tif 000043
【図１３】
2007072718.tif 000044
【図１４】
2007072718.tif 000045
【図１５】
2007072718.tif 000046
【図１６】
2007072718.tif 000047
【図１７】
2007072718.tif 000048