JPWO2017069001A1

JPWO2017069001A1 - プログラム、情報記憶媒体及び情報処理装置

Info

Publication number: JPWO2017069001A1
Application number: JP2017546498A
Authority: JP
Inventors: 正樹中川; 進亮佐々木
Original assignee: NATIONAL UNIVERSITY CORPORATION TOKYO UNIVERSITY OF AGRICULUTURE & TECHNOLOGY
Current assignee: NATIONAL UNIVERSITY CORPORATION TOKYO UNIVERSITY OF AGRICULUTURE & TECHNOLOGY
Priority date: 2015-10-19
Filing date: 2016-10-07
Publication date: 2018-08-02
Also published as: WO2017069001A1

Abstract

情報処理装置は、入力されたストローク列におけるストローク間のオフストロークの長さに基づいて、ストローク列から行を切出す処理を行う行切出し部と、切出されたｎ（ｎは自然数）行目のストローク列の外接矩形の中心と、ｎ＋１行目のストローク列の外接矩形の中心との垂直方向の距離を求め、求めた距離が所定の閾値よりも小さい場合に、ｎ行目のストローク列とｎ＋１行目のストローク列とを同一行に統合する行統合部とを含む。

Description

本発明は、プログラム、情報記憶媒体及び情報処理装置に関する。

従来、数式を入力する手法として、ＬａＴｅＸなどの専門言語を用いる方法や、数式入力エディタを用いる方法等が用いられてきたが、前者は専門用語を習得する必要があり、後者はメニュー選択と記号選択を繰り返す必要があり、ともに一般人には使い勝手が悪かった。これに対して、タブレットなどに手書きされた数式をコンピュータにより認識させる方法は古くから研究されてきた（例えば、特開２００９−８０６１５号公報）。そして、近年におけるタブレット型ＰＣの急速な普及から一般人に浸透する可能性も増しており、教育現場では、電子黒板やタブレットの導入が急速に進んでいる。

計算式を筆記する場合、数式は複数行にわたって展開や変形が行われるため、数式認識では行切出しが不可欠となる。ところが従来の手書き数式認識システムでは、１行ごとに入力された数式を対象としており、途中式などの複数行にわたる数式の行切出しを行って（複数行の数式における改行を検出して）数式を認識することはできなかった。

本発明は、以上のような課題に鑑みてなされたものであり、その目的とするところは、複数行にわたる手書き数式の行切出しを行うことが可能なプログラム、情報記憶媒体及び情報処理装置を提供することにある。

（１）本発明は、手書き入力された複数行にわたる数式のストローク列から行を切り出す処理を行うためのプログラムであって、前記ストローク列におけるストローク間のオフストロークの長さに基づいて、前記ストローク列から行を切出す処理を行う行切出し部と、切出されたｎ（ｎは自然数）行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形と、ｍ（ｍはｎとは異なる自然数）行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形との位置関係に基づいて、ｎ行目のストローク列とｍ行目のストローク列が同一行であるか否かを判断し、同一行であると判断した場合に、ｎ行目のストローク列とｍ行目のストローク列とを同一行に統合する行統合処理を行う行統合部としてコンピュータを機能させるプログラムに関する。また、本発明は、コンピュータ読み取り可能な情報記憶媒体であって、上記各部としてコンピュータを機能させるためのプログラムを記憶した情報記憶媒体に関係する。また、本発明は、上記各部を含む情報処理装置に関係する。

本発明によれば、ストローク列におけるストローク間のオフストロークの長さに基づいて、ストローク列から行を切出す処理を行った後に、切出されたｎ行目のストローク列の外接矩形（又はストロークの外接矩形）と、ｍ行目のストローク列の外接矩形（又はストロークの外接矩形）との位置関係に基づいて、ｎ行目のストローク列とｍ行目のストローク列が同一行であるか否かを判断し、同一行であると判断した場合に、ｎ行目のストローク列とｍ行目のストローク列とを同一行に統合する処理を行うことで、複数行にわたる手書き数式の行切出しを精度良く行うことができる。

（２）また本発明に係るプログラム、情報記憶媒体及び情報処理装置では、前記行統合部は、
切出されたｎ行目のストローク列の外接矩形と、ｎ＋１行目のストローク列の外接矩形との垂直方向の距離を求め、求めた距離が所定の閾値よりも小さい場合に、ｎ行目のストローク列とｎ＋１行目のストローク列とを同一行に統合する行統合処理を行ってもよい。

本発明によれば、ｎ行目のストローク列の外接矩形と、ｎ＋１行目のストローク列の外接矩形との垂直方向の距離が所定の閾値αよりも小さい場合に、ｎ行目のストローク列とｎ＋１行目のストローク列とを同一行に統合することで、括弧などの書き足しによる誤分割（改行の誤検出）を解消して、複数行にわたる手書き数式の行切出しを精度良く行うことができる。

（３）また本発明に係るプログラム、情報記憶媒体及び情報処理装置では、前記行統合部は、切出されたｎ行目のストローク列に分数罫に対応するストロークが存在するか否かを判定し、当該ストロークが存在すると判定した場合に、当該ストロークの外接矩形の上端とｍ行目のストローク列の外接矩形の下端との垂直方向の距離と、当該ストロークの外接矩形の下端とｍ行目のストローク列の外接矩形の上端との垂直方向の距離とを求め、求めたいずれかの距離が所定の閾値よりも小さい場合に、ｎ行目のストローク列とｍ行目のストローク列とを同一行に統合する行統合処理を行ってもよい。

本発明によれば、ｎ行目のストローク列に含まれる分数罫に対応するストロークを検出し、当該ストロークの外接矩形の上端とｎ−１行目のストローク列の外接矩形の下端との垂直方向の距離が所定の閾値δよりも小さい場合に、ｎ行目のストローク列とｎ−１行目のストローク列とを同一行に統合し、当該ストロークの外接矩形の下端とｎ＋１行目のストローク列の外接矩形の上端との垂直方向の距離が所定の閾値δよりも小さい場合に、ｎ行目のストローク列とｎ＋１行目のストローク列とを同一行に統合することで、分数が複数の行として切出されてしまうことを防止して、複数行にわたる手書き数式の行切出しを精度良く行うことができる。

（４）また本発明に係るプログラム、情報記憶媒体及び情報処理装置では、前記行切出し部は、前記ストローク列におけるストローク間のオフストロークの長さに基づいて、行切出し候補点となるオフストロークを決定し、前記行切出し候補点を用いて複数の行切出し候補を生成し、前記行統合部は、複数の前記行切出し候補のそれぞれについて前記行統合処理を行った後、複数の前記行切出し候補のそれぞれについて数式認識を行って数式の確からしさを求め、数式の確からしさの値が最も大きい前記行切出し候補を選択してもよい。

本発明によれば、複数の行切出し候補のそれぞれについて行統合処理を行った後、複数の行切出し候補のそれぞれについて数式認識を行って数式の確からしさを求め、数式の確からしさの値が最も大きい行切出し候補を選択することで、複数行にわたる手書き数式の行切出しをより精度良く行うことができる。

図１は、本実施形態の認識装置（情報処理装置）の機能ブロック図の一例である。図２は、本実施形態の行切出し手法を模式的に示す図である。図３は、基本方式の第１ステップについて説明するための図である。図４は、基本方式の第２ステップについて説明するための図である。図５は、基本方式の第３ステップについて説明するための図である。図６Ａは、基本方式による誤分割の具体例を示す図である。図６Ｂは、基本方式による誤分割の具体例を示す図である。図７は、第１の行統合処理の一例を示すフローチャートである。図８Ａは、第１の行統合処理の具体例を示す図である。図８Ｂは、第１の行統合処理の具体例を示す図である。図９は、第２の行統合処理の一例を示すフローチャートである。図１０は、第２の行統合処理の一例を示すフローチャートである。図１１は、図９のステップＳ２５の処理の詳細を示すフローチャートである。図１２Ａは、第２の行統合処理の具体例を示す図である。図１２Ｂは、第２の行統合処理の具体例を示す図である。図１２Ｃは、第２の行統合処理の具体例を示す図である。図１３は、数式認識による選択処理について説明するための図である。図１４は、逐次方式における処理の一例を示すフローチャートである。

以下、本実施形態について説明する。なお、以下に説明する本実施形態は、請求の範囲に記載された本発明の内容を不当に限定するものではない。また本実施形態で説明される構成の全てが、本発明の必須構成要件であるとは限らない。

１．構成
図１に本実施形態の認識装置（情報処理装置）の機能ブロック図の一例を示す。なお本実施形態の認識装置は図１の構成要素（各部）の一部を省略した構成としてもよい。

文字入力部１６０は、ユーザが筆記媒体（ペン、指先等）で手書き文字を入力するためのものであり、その機能は、タブレット、タッチパネル等の筆記面などにより実現できる。文字入力部１６０は、筆記媒体が筆記面に触れてから離れるまでの筆記媒体の位置を表す座標データを一定時間間隔で検出し、検出された座標データ列（座標点系列、オンライン手書きパターンと呼ぶ）をストローク（筆画）のデータとして処理部１００に出力する。なお、ストロークの終点から次のストロークの始点までのベクトルをオフストローク（運筆ベクトル）と呼び、ストロークとオフストロークの連続する系列をストローク列と呼ぶ。

記憶部１７０は、処理部１００の各部としてコンピュータを機能させるためのプログラムや各種データを記憶するとともに、処理部１００のワーク領域として機能し、その機能はハードディスク、ＲＡＭなどにより実現できる。

表示部１９０は、処理部１００で生成された画像を出力するものであり、その機能は、文字入力部１６０としても機能するタッチパネル、ＬＣＤ或いはＣＲＴなどのディスプレイにより実現できる。

処理部１００（プロセッサ）は、文字入力部１６０からの座標データやプログラムなどに基づいて、行切出し処理、行統合処理、認識処理、表示制御などの処理を行う。この処理部１００は記憶部１７０内の主記憶部をワーク領域として各種処理を行う。処理部１００の機能は各種プロセッサ（ＣＰＵ、ＤＳＰ等）、ＡＳＩＣ（ゲートアレイ等）などのハードウェアや、プログラムにより実現できる。処理部１００は、行切出し部１１０、行統合部１１２、認識部１１４、表示制御部１２０を含む。

行切出し部１１０は、入力されたストローク列（手書き入力された複数行にわたる数式パターンのストローク列）におけるストローク間のオフストロークの長さに基づいて、前記ストローク列から行を切出す処理を行う。また、行切出し部１１０は、入力されたストローク列におけるストローク間のオフストロークの長さに基づいて、行切出し候補点となるオフストロークを決定し、切出し候補点を用いて複数の行切出し候補を生成してもよい。

行統合部１１２は、行切出し部１１０で切出されたｎ（ｎは自然数）行目のストローク列の外接矩形の中心と、ｎ＋１行目のストローク列の外接矩形の中心との垂直方向の距離を求め、求めた距離が所定の閾値αよりも小さい場合に、ｎ行目のストローク列とｎ＋１行目のストローク列とを同一行に統合する第１の行統合処理を行う。

また、行統合部１１２は、行切出し部１１０で切出されたｎ行目のストローク列に分数罫に対応するストロークが存在するか否かを判定し、当該ストロークが存在すると判定した場合に、当該ストロークの外接矩形の上端とｍ（ｍはｎとは異なる自然数）行目のストローク列の外接矩形の下端との垂直方向の距離と、当該ストロークの外接矩形の下端とｍ行目のストローク列の外接矩形の上端との垂直方向の距離とを求め、求めたいずれかの距離が所定の閾値δよりも小さい場合に、ｎ行目のストローク列とｍ行目のストローク列とを同一行に統合する第２の行統合処理を行ってもよい。

また、行統合部１１２は、行切出し部１１０で生成された複数の行切出し候補のそれぞれについて行統合処理（第１の行統合処理、及び／又は第２の行統合処理）を行った後、複数の行切出し候補のそれぞれについて数式認識を行って数式の確からしさを求め、複数の行切出し候補のうち、数式の確からしさの値が最も大きい行切出し候補を選択して出力してもよい。

認識部１１４は、行切出し部１１０及び行統合部１１２で行切出し処理及び行統合処理が行われたストローク列から、数式認識エンジンにより行ごとに数式を認識する処理を行う。

表示制御部１２０は、入力されたストローク列を表示部１９０に表示させる制御と、認識部１１４により認識された複数行にわたる数式（認識結果）を表示部１９０に表示させる制御を行う。

２．本実施形態の手法
２−１．基本方式
図２は、本実施形態の行切出し手法を模式的に示す図である。本実施形態の手法では、まず、文字列認識における行切出しの方式を基本方式として用いて数式の行切出しを行う。この基本方式は、ストローク列を複数のブロックに分ける処理（ステップＳ１）、行切出し候補点となるオフストロークを決定する処理（ステップＳ２）、行切出し候補点を用いて複数の行切出し候補を生成する処理（ステップＳ３）の３ステップから成る。

基本方式のステップＳ１では、行切出し部１１０は、入力されたストローク列ＳＴに含まれるオフストロークＯＳのうち閾値Ｂを超える長さをもつオフストロークＯＳを検出し、閾値Ｂを超える長さをもつオフストロークＯＳで区切られる連続するストローク列をブロックＢＬとして分ける（図３参照）。図３に示す例では、数式「５＋２＝７」「７＋３＝１０」に対応するストローク列ＳＴが、「５＋」、「２」、「＝」、「７」、「７」、「＋３」、「＝」、「１」、「０」に対応する９個のブロックＢＬに分けられている。閾値Ｂは平均文字サイズを基準として決定され、ここでは、閾値Ｂを平均文字サイズの０．８倍としている。平均文字サイズは入力されたストローク列から求めることができる。すなわち、入力された各ストロークの外接矩形を求め、各外接矩形の垂直（縦）方向又は水平（横）方向の長さが大きい順に各外接矩形をソートすることで、各外接矩形の垂直方向又は水平方向の長さの平均値を求める。そして、求めた平均値を平均文字サイズとする。

基本方式のステップＳ２では、行切出し部１１０は、ブロックＢＬ間のオフストロークＯＳ（前のブロックＢＬの最後のストロークと次のブロックＢＬの最初のストローク間のオフストローク）のうち閾値Ｌを超える長さをもつオフストロークＯＳを検出し、閾値Ｌを超える長さをもつオフストロークＯＳを行切出し候補点ＳＰとして設定する（図４参照）。なお、ここでは閾値Ｌを平均文字サイズの５倍としている。図４に示す例では、５点の行切出し候補点ＳＰ_１〜ＳＰ_５が設定されている。また、図中Ｓは、ストローク列ＳＴの開始点であり、図中Ｅは、ストローク列ＳＴの終了点である。

基本方式のステップＳ３では、行切出し部１１０は、ステップＳ２で得られた全ての行切出し候補点ＳＰ（及び、開始点Ｓ、終了点Ｅ）を用いて行切出し候補ラティスＬＴを生成し（図５参照）、６つのグローバル特徴量を入力としてＭＣＥ（Minimum Classification Error Training）で訓練された線形判別式によって上位複数の経路（上位複数の行切出し候補）を求める。図５に示す例では、「Ｓ」→「ＳＰ_３」→「Ｅ」の経路（すなわち、「５＋２＝７」を１行目とし、「７＋３＝１０」を２行目とする行切出し候補）が、線形判別式とビームサーチによって得られる最適な経路（第１位の行切出し候補）となる。

ここで、基本方式（ステップＳ１〜Ｓ３）によって複数行にわたる数式を行切出しすると、括弧などの書き足しによる誤分割や、分数の誤分割（分数が複数の行として切出されてしまう）が生じる場合がある。図６Ａ、図６Ｂに、基本方式による誤分割の具体例を示す。図６に示す外接矩形ＣＲは、それぞれストローク列から切出された行を示している。図６Ａは、書き足しによる誤分割の例であり、先頭行の「（ｘ^２−９ｘ＋２０）（ｘ−７）」において、「ｘ^２−９ｘ＋２０」が筆記された後に、その左側に開き括弧が筆記され、右側に閉じ括弧が筆記されたことで、開き括弧から閉じ括弧へのオフストロークの長さが閾値Ｌを超えたため、「（ｘ^２−９ｘ＋２０」と「）（ｘ−７）」の２行に過分割されてしまっている。図６Ｂは、分数の誤分割の例であり、分数の分子、分母、分数罫（括線）がそれぞれ１つの行として過分割されてしまっている。

２−２．第１の行統合処理
本実施形態の手法では、括弧などの書き足しによる誤分割を解消するために、基本方式の３ステップの後に、第１の行統合処理（図２のステップＳ４）を追加して実行する。なお、ステップＳ４以降の処理は、ステップＳ３で得られた複数の行切出し候補ごとに行われる。

図７は、第１の行統合処理の一例を示すフローチャートである。まず、行統合部１１２は、行番号を表す変数ｉに１をセットする（ステップＳ１０）。なお、図中のループ開始端（ステップＳ１０）には、「変数＝初期値、終値、増分値」を記載し、ループ終了端（ステップＳ１６）には、「変数」を記載している。ここで、変数ＬＮは、切出された行の総数を表す変数である。

次に、行統合部１１２は、ｉ行目のストローク列の外接矩形の中心とｉ＋１行目のストローク列の外接矩形の中心との垂直方向の距離Ｄｙを算出する（ステップＳ１１）。すなわち、ｉ行目のストローク列の外接矩形の中心のｙ座標とｉ＋１行目のストローク列の外接矩形の中心のｙ座標の差の絶対値を距離Ｄｙとして求める。次に、行統合部１１２は、距離Ｄｙが閾値αよりも小さいか否かを判断する（ステップＳ１２）。なお、閾値αは、平均文字サイズを基準として実験により決定する。距離Ｄｙが閾値α以上である場合（ステップＳ１２のＮ）には、ステップＳ１６に移行する。距離Ｄｙが閾値αよりも小さい場合（ステップＳ１２のＹ）には、行統合部１１２は、ｉ行目のストローク列とｉ＋１行目のストローク列とを同一行に統合し（ステップＳ１３）、変数ＬＮを１だけ減算し（ステップＳ１４）し、変数ｉを１だけ減算する（ステップＳ１５）。以降、変数ｉを１ずつ加算しながら、変数ｉが変数ＬＮに達するまで、ステップＳ１１〜Ｓ１５の処理を繰り返す。

図８Ａ、図８Ｂに、第１の行統合処理の具体例を示す。図８Ａに示す例では、先頭行の数式において括弧の書き足しによる過分割が生じている。まず、図８Ａに示すように、１行目の外接矩形ＣＲ_１の中心Ｃ_１のｙ座標と２行目の外接矩形ＣＲ_２の中心Ｃ_２のｙ座標の差の絶対値（距離Ｄｙ）を求め、距離Ｄｙと閾値αとを比較する。ここでは、１行目と２行目について求めた距離Ｄｙが閾値αよりも小さいため、１行目と２行目を統合して新たな１行目とする。次に、図８Ｂに示すように、新たな１行目の外接矩形ＣＲ_１’の中心Ｃ_１’のｙ座標と新たな２行目の外接矩形ＣＲ_２’の中心Ｃ_２’のｙ座標の差の絶対値（距離Ｄｙ）を求め、閾値αと比較する。ここでは、新たな１行目と新たな２行目について求めた距離Ｄｙが閾値αよりも大きいため、統合せずに次の行に進む。図８Ｂに示す例では次の行（３行目）がないため第１の行統合処理を終了する。このように、第１の行統合処理により、括弧などの書き足しによる誤分割を解消することができる。

２−３．第２の行統合処理
本実施形態の手法では、分数の誤分割を解消するために、第１の行統合処理の後に、第２の行統合処理（図２のステップＳ５）を実行する。なお、第２の行統合処理を行った後に第１の行統合処理を行ってもよく、また、第１の行統合処理と第２の行統合処理のいずれか一方を省略してもよい。

図９、図１０は、第２の行統合処理の一例を示すフローチャートである。まず、行統合部１１２は、行番号を表す変数ｉに１をセットし（ステップＳ２０）、ｉ行目内のブロック番号を表す変数ｊに１をセットし（ステップＳ２１）、ｊ番目のブロック内のストローク番号を表す変数ｓに１をセットする（ステップＳ２２）。ここで、変数ＢＮは、ｉ行目内のブロックの総数であり、変数ＳＮは、ｊ番目のブロック内のストロークの総数である。

次に、行統合部１１２は、ｓ番目のストロークの外接矩形の高さＨと幅Ｗを取得し（ステップＳ２３）、高さＨが閾値βよりも小さく且つ幅Ｗが閾値γよりも大きいか（ｓ番目のストロークが長い水平線分に相当するストロークであるか）否かを判断する（ステップＳ２４）。なお、閾値β、γは、平均文字サイズを基準として実験により決定する。高さＨが閾値βよりも小さく且つ幅Ｗが閾値γよりも大きい場合（ステップＳ２４のＹ）には、行統合部１１２は、ｓ番目のストロークがルート記号の水平線（直線部分）に相当するストロークであるか否かを判断する（ステップＳ２５）。ステップＳ２５の処理の詳細については後述する。ｓ番目のストロークの外接矩形の高さＨが閾値β以上であるか幅Ｗが閾値γ以下である場合（ステップＳ２４のＮ）、及びｓ番目のストロークがルート記号の水平線である場合（ステップＳ２５のＹ）には、ステップＳ３７に移行する。

ｓ番目のストロークがルート記号の水平線に相当するストロークでない場合（ステップＳ２５のＮ）には、行統合部１１２は、ｓ番目のストロークが分数罫に相当（対応）するストロークであると判断し、行番号を表す変数ｋに１をセットする（ステップＳ２６）。次に、行統合部１１２は、変数ｉと変数ｋが一致するか否かを判断し（ステップＳ２７）、一致しない場合（ステップＳ２７のＮ）には、ｋ行目とｓ番目のストロークが水平方向に重なっている（ｘ軸上で離れていない）か否かを判断する（ステップＳ２８）。例えば、ｋ行目のストローク列の外接矩形の右端のｘ座標よりもｓ番目のストロークの外接矩形の左端のｘ座標が大きい場合、又はｓ番目のストロークの外接矩形の右端のｘ座標よりもｋ行目のストローク列の外接矩形の左端のｘ座標が大きい場合に、ｋ行目とｓ番目のストロークが水平方向に重なっていないと判断する。変数ｉと変数ｋが一致する場合（ステップＳ２７のＹ）、及びｋ行目とｓ番目のストロークが水平方向に重なっていない場合（ステップＳ２８のＮ）、ステップＳ３６に移行する。

ｋ行目とｓ番目のストロークが水平方向に重なっている場合（ステップＳ２８のＹ）には、行統合部１１２は、ｓ番目のストロークの外接矩形の上端とｋ行目のストローク列の外接矩形の下端との垂直方向の距離Ｄｔ（ｓ番目のストロークの外接矩形の上端のｙ座標とｋ行目のストローク列の外接矩形の下端のｙ座標の差の絶対値）を算出し（ステップＳ２９）、ｓ番目のストロークの外接矩形の下端とｋ行目のストローク列の外接矩形の上端との垂直方向の距離Ｄｂ（ｓ番目のストロークの外接矩形の下端のｙ座標とｋ行目のストローク列の外接矩形の上端のｙ座標の差の絶対値）を算出する（ステップＳ３０）。次に、行統合部１１２は、距離Ｄｔが閾値δよりも小さいか又は距離Ｄｂが閾値δよりも小さいか否かを判断する（ステップＳ３１）。なお、閾値δは、平均文字サイズを基準として実験により決定する。距離Ｄｔが閾値δ以上であり且つ距離Ｄｂが閾値δ以上である場合（ステップＳ３１のＮ）には、ステップＳ３６に移行する。距離Ｄ及び距離Ｄｂの少なくとも一方が閾値δよりも小さい場合（ステップＳ３１のＹ）には、行統合部１１２は、ｉ行目のストローク列とｋ行目のストローク列とを同一行に統合し（ステップＳ３２）、変数ＬＮを１だけ減算する（ステップＳ３３）。次に、行統合部１１２は、変数ｉが変数ｋよりも小さいか否かを判断し（ステップＳ３４）、変数ｉが変数ｋよりも小さい場合（ステップＳ３４のＹ）には、変数ｋを１だけ減算する（ステップＳ３５）。

以降、変数ｋを１ずつ加算しながら、変数ｋが変数ＬＮを超えるまで、ステップＳ２７〜Ｓ３５の処理を繰り返す。また、変数ｋが変数ＬＮに達した場合、変数ｓを１ずつ加算しながら、変数ｓが変数ＳＮを超えるまで、ステップＳ２３〜Ｓ３６の処理を繰り返す。また、変数ｓが変数ＳＮに達した場合、変数ｊを１ずつ加算しながら、変数ｊが変数ＢＮを超えるまで、ステップＳ２２〜Ｓ３７の処理を繰り返す。また、変数ｊが変数ＢＮに達した場合、変数ｉを１ずつ加算しながら、変数ｉが変数ＬＮを超えるまで、ステップＳ２１〜Ｓ３８の処理を繰り返す。

図１１は、図９のステップＳ２５の処理の詳細を示すフローチャートである。まず、行統合部１１２は、変数ｊに１をセットし（ステップＳ４０）、ｊ番目のブロック内のストローク番号を表す変数ｍに１をセットする（ステップＳ４１）。次に、行統合部１１２は、変数ｍが変数ｓと一致するか否かを判断し（ステップＳ４２）、一致する場合（ステップＳ４２のＹ）、ステップＳ４８に移行する。

ステップＳ４２の条件を満たさない場合には、行統合部１１２は、ｍ番目のストロークの外接矩形の中心がｓ番目のストロークの外接矩形の左端よりも左側に位置する（ｍ番目のストロークの外接矩形の中心のｘ座標≦ｓ番目のストロークの外接矩形の左端のｘ座標）か否かを判断する（ステップＳ４３）。ステップＳ４３の条件を満たす場合には、行統合部１１２は、ｍ番目のストロークの外接矩形の中心とｓ番目のストロークの外接矩形の左端との水平方向の距離（ｍ番目のストロークの外接矩形の中心のｘ座標とｓ番目のストロークの外接矩形の左端のｘ座標との差の絶対値）が閾値Ｐよりも小さいか否かを判断する（ステップＳ４４）。ステップＳ４４の条件を満たす場合には、行統合部１１２は、ｍ番目のストロークの外接矩形の上端とｓ番目のストロークの外接矩形の上端との垂直方向の距離（ｍ番目のストロークの外接矩形の上端のｙ座標とｓ番目のストロークの外接矩形の上端のｙ座標との差の絶対値）が閾値Ｑよりも小さいか否かを判断する（ステップＳ４５）。ステップＳ４５の条件を満たす場合には、行統合部１１２は、ｍ番目のストロークの外接矩形の高さが閾値Ｒよりも大きいか否かを判断する（ステップＳ４６）。なお、閾値Ｐ、Ｑ、Ｒは、平均文字サイズを基準として実験により決定する。ステップＳ４６の条件を満たす場合には、ｓ番目のストロークがルート記号の水平線に相当するストロークであると判断する（ステップＳ４７）。

以降、変数ｍを１ずつ加算しながら、変数ｍが変数ＳＮを超えるまで、ステップＳ４２〜Ｓ４７の処理を繰り返す。また、変数ｍが変数ＳＮに達した場合、変数ｊを１ずつ加算しながら、変数ｊが変数ＢＮを超えるまで、ステップＳ４１〜Ｓ４８の処理を繰り返す。

図１２Ａ、図１２Ｂ、図１２Ｃに、第２の行統合処理の具体例を示す。図１２Ａに示す例では、２行目の数式において、分数の分子及び分数罫で１行、分母で１行として過分割されてしまっている。まず、１行目のストローク列における各ストロークの外接矩形の高さＨ及び幅Ｗをそれぞれ閾値β及び閾値γと比較して、長い水平線分を探す（図９のステップＳ２４）と、１行目では検出されない。同様に、２行目のストローク列において水平線分を探すと、図１２Ａに示すように、２画で筆記されたルート記号の直線部分が水平線分ＬＳ_１として検出される。検出された水平線分ＬＳ_１がルート記号の直線部分であるか否かを判定するために、２行目のストローク列において、水平線分ＬＳ_１との関係において図１１のステップＳ４３〜Ｓ４６の条件を満たすストローク（２画で筆記されたルート記号の先頭部分）があるか否かを判定する。２行目にはステップＳ４３〜Ｓ４６の条件を満たすストロークがあるため、水平線分ＬＳ_１をルート記号の直線部分と判断する。

そして、２行目のストローク列において他の水平線分を探すと、図１２Ｂに示すように、分数罫が水平線分ＬＳ_２として検出される。検出された水平線分ＬＳ_２が２画で筆記されたルート記号の直線部分であるか否かを判定すると、２行目のストローク列において、水平線分ＬＳ_２との関係において図１１のステップＳ４３〜Ｓ４６の条件を満たすストロークがないため、水平線分ＬＳ_２を分数罫と判断する。従って、水平線分ＬＳ_２を含む２行目を他の行と統合するか否かを判定する処理（図９のステップＳ２６〜図１０のステップＳ３６のループ処理）に進む。

水平線分ＬＳ_２は１行目の外接矩形ＣＲ_１とｘ軸上で離れておらず（図９のステップＳ２８のＹ）、また、水平線分ＬＳ_２の外接矩形の上端のｙ座標と１行目の外接矩形ＣＲ_１の下端のｙ座標との差の絶対値が閾値δよりも大きく、且つ水平線分ＬＳ_２の外接矩形の下端のｙ座標と１行目の外接矩形ＣＲ_１の上端のｙ座標との差の絶対値が閾値δよりも大きい（図９のステップＳ３１のＮ）ため、１行目とは統合しない。水平線分ＬＳ_２を含む２行目は対象としないため、３行目について同様に判定すると、図１２Ｃに示すように、水平線分ＬＳ_２は３行目の外接矩形ＣＲ_３とｘ軸上で離れておらず、また、水平線分ＬＳ_２の外接矩形の下端のｙ座標と３行目の外接矩形ＣＲ_３の上端のｙ座標との差の絶対値が閾値δよりも小さい（図９のステップＳ３１のＹ）ため、２行と３行目を統合する（図９のステップＳ３２）。図１２Ｃに示す例では、これ以上対象となる行がないため第２の行統合処理を終了する。このように、第２の行統合処理により、分数の誤分割を解消することができる。分数罫の候補となる長い水平線分は、ルート記号が２画以上で筆記された場合にも出現するが、第２の行統合処理によれば、分数罫を２画で筆記されたルート記号の直線部分と明確に区別して検出することができ、分数の誤分割を精度良く解消することができる。

２−４．数式認識による選択処理
本実施形態の手法では、行統合処理の後に、数式認識による選択処理（図２のステップＳ６）を実行する。なお、数式認識による選択処理を省略してもよい。

行切出し部１１０は、図２のステップＳ３において、例えば第１位候補から第５位候補までの複数の行切出し候補を生成する。行統合部１１２は、それぞれの行切出し候補に対して、第１の行統合処理と第２の行統合処理の少なくとも一方を行った後、図２のステップＳ６において、数式認識を行って各行の数式の確からしさを求め、各行の数式の確からしさの積が最も大きい行切出し候補を選択して、最終的な行切出しの結果とする。

なお、各行の数式の確からしさＰは、次式により求めることができる。

ここで、Ｐ_ｓｅｇｊは、ストロークｊとストロークｊ＋１が２つシンボルに分割される確率を示し、Ｐ_ｒｅｃ（Ｓ_ｉ｜Ｇ_ｉ）は、ストローク列Ｇ_ｉがシンボルＳ_ｉとなる確率を示し、Ｐ_ｒｅｊ（Ｒ_ｋ｜ＳＥ_ｋ）は、文法要素関係Ｒ_ｋによって、２つの文法要素の組ＳＥ_ｋが１つの大きい文法要素にまとめられる確率を示し、Ｐ_Ｇｒａｍは、文法規則がそれぞれ生起する確率を示す。

図１３に、第１の行統合処理が行われた後の、複数の行切出し候補の一例を示す。図１３に示す例では、第１位候補において、分数を含む先頭行の数式が、「４×６」、分数罫、「２×４−６」、「（ｘ＋２）×４」の４行に誤分割されている。また、第２位候補においても、先頭行の数式が誤分割されている。また、第５位候補では正しく行切出しされている。

第１位候補の数式の確からしさは、１行目の「４×６」の確率（数式の確からしさ）をＰ_１、２行目の分数罫の確率をＰ_２、３行目の「２×４−６」の確率をＰ_３、４行目の「（ｘ＋２）×４」の確率をＰ_４とすると、それらを掛け合わせたＰ_１×Ｐ_２×Ｐ_３×Ｐ_４となる。同様に、第２位候補の数式の確からしさは、１行目の確率をＰ_５とすると、Ｐ_５×Ｐ_３×Ｐ_４となり、第５位候補の数式の確からしさは、１行目の確率をＰ_６とすると、Ｐ_６×Ｐ_４となる。確率Ｐ_１〜Ｐ_６のうち、確率Ｐ_２、Ｐ_５は数式としてあり得ないため低い率を示すが、その他の確率Ｐ_１、Ｐ_３、Ｐ_４、Ｐ_５は高い率を示す。従って、図１３に示す例では、確率Ｐ_２、Ｐ_５を含まない第５位候補の確率（Ｐ_６×Ｐ_４）が行切出しの確からしさにおいて最も高い率を示し、第５位候補が最終的な行切出しの結果となる。このように、数式認識による選択処理によっても、分数の誤分割を解消することができる。

上記の例では、複数行にわたる数式が筆記された後に、行切出し処理と数式認識処理を実行する場合について説明したが、数式の筆記途中で（筆画ごとに）行切出し処理と数式認識処理を実行することもできる（逐次方式）。図１４は、逐次方式における処理の一例を示すフローチャートである。まず、ストローク番号を表す変数ｊに１をセットし（ステップＳ５０）、ストローク番号を表す変数ｉに１をセットする（ステップＳ５１）。ここで、変数ＴＳは、ストロークの総数である。次に、ｊ番目からｉ番目のストロークまで行切出しを行い（ステップＳ５２）、ｉ番目のストロークが新しい行の先頭のストロークであるか否かを判断する（ステップＳ５３）。ステップＳ５３の判断は、これまで示した方法により行う。ｉ番目のストロークが新しい行の先頭のストロークでない場合（ステップＳ５３のＮ）には、ステップＳ５６に移行する。ｉ番目のストロークが新しい行の先頭のストロークである場合（ステップＳ５３のＹ）には、変数ｊに変数ｉの値をセットし（ステップＳ５４）、手書き数式逐次認識内のストローク（認識対象となるストローク）をリセットする（ステップＳ５５）。次に、ｊ番目からｉ番目までのストロークから数式を認識する（ステップＳ５６）。以降、変数ｉを１ずつ加算しながら、変数ｉが変数ＴＳを超えるまで、ステップＳ５２〜Ｓ５６の処理を繰り返す。また、上記の例では、行切出し候補点ＳＰを用いて切出された行を処理単位として第１の行統合処理、第２の行統合処理及び数式認識による選択処理を行う場合について説明したが、行に含まれる１つ又は複数のブロックＢＬを処理単位としてこれらの処理を行ってもよい。

３．評価実験
本実施形態の行切出し手法の評価及び学習に利用する複数行の手書き数式パターンとして、筆記者に予め指定した式を書き写してもらう方式と、筆記者に問題を解きながら書いてもらう方式とで、１７人から計２，０８５行の手書き数式パターンを収集した。収集した複数行の手書き数式パターンには、正しい行切出しの情報を付与した。また、パターンを増やすために、収集したパターンから１行分の数式を選択し、その外接矩形を縦方向に一定間隔で、横方向に乱数で変動させることにより、総行数１６，８００行のパターン（人工パターン）を生成した。

収集した２，０８５行のパターンを対象に、経験的に最適と思われる閾値の前後を列挙法により探索し、行切出し精度が一番高くなる値を閾値として設定した。その結果、閾値Ｂを０．７（平均文字サイズの０．７倍）とし、閾値Ｌを５とし、閾値αを０．７とし、閾値δを０．４とした。また、閾値β、γは、数式パターン中の長い水平線分のストロークの外接矩形と高さと幅を満たすように設定し、閾値Ｐ、Ｑ、Ｒは、数式パターン中の２画で筆記されたルート記号の先頭部分のストロークの外接矩形の高さと位置を満たすように設定した。

本実験では、３４分割交差検証法を採用した。分割数が多いのは、検定の効果を高めるためである。筆記者ごとに０から１６までの番号を振り、各人のパターンを同数ずつＡとＢの２つに分割し、一方を評価用のテストセットに残し、他方と他の人の全てのパターンを学習セットとした。学習セットにより基本方式のステップＳ３で用いる線形判別式のパラメータを学習させ、テストセットに対して評価実験を行った。最後に全てのテストセットに対する評価の平均を求めた。また、分割した１〜３４のパターンにそれぞれ人工パターンを加えた評価実験も行った。

評価基準として次に定義する行切出し精度（単位：％）を用いた。

表１に、基本方式（図２のステップＳ１〜Ｓ３）での行切出し精度と、基本方式に第１の行統合処理（図２のステップＳ４）を追加した方式での行切出し精度を示す。

収集パターンに人工パターンを追加しない場合、第１の行統合処理を追加した方式では、基本方式に比べて、行切出し精度が７．６１ポイント向上した。また、収集パターンに人工パターンを追加した場合、第１の行統合処理を追加した方式では、基本方式に比べて、行切出し精度が８．１６ポイント向上した。これらの結果に対してｐａｉｒｅｄ−ｔ検定を実施した。その結果、両側確率でそれぞれ３．４２^−８、１．３６^−７となり、危険率Ｐ＝０．０５で有意差ありと示された。このように、第１の行統合処理を追加した方式によって誤分割を効果的に解消できることが示された。また、括弧などの書き足しによる誤分割が全て解消されたことを確認した。また、収集パターンに収集パターンを含めることで行切出し精度は約１．２〜１．６ポイント向上した。この結果に対してもｐａｉｒｅｄ−ｔ検定を実施し、両側確率で０．０００７となり、危険率Ｐ＝０．０５で有意差ありと示された。

表２に、基本方式に第１の行統合処理を追加した方式での行切出し精度と、基本方式に第１の行統合処理と第２の行統合処理（図２のステップＳ５）の両方を追加した方式での行切出し精度を示す。

収集パターンに人工パターンを追加しない場合、第１の行統合処理と第２の行統合処理の両方を追加した方式では、第１の行統合処理のみを追加した方式に比べて、行切出し精度が０．８ポイント向上した。また、収集パターンに人工パターンを追加した場合、第１の行統合処理と第２の行統合処理の両方を追加した方式では、第１の行統合処理のみを追加した方式に比べて、行切出し精度が０．７５ポイント向上した。これらの結果に対してｐａｉｒｅｄ−ｔ検定を実施した。その結果、両側確率でそれぞれ０．００３３９、０．００３７となり、危険率Ｐ＝０．０５で有意差ありと示された。このように、第１の行統合処理に第２の行統合処理を追加した方式によって分数の誤分割を効果的に解消できることが示唆された。また、ルート記号の直線部分が分数罫と誤認識されることはなかった。

表３に、基本方式での行切出し精度と、基本方式に第１の行統合処理と第２の行統合処理を追加した方式での行切出し精度と、基本方式に第１の行統合処理と第２の行統合処理と数式認識による選択処理（図２のステップＳ６）を追加した方式での行切出し精度を示す。だだし、本実験で用いた手書き数式認識システムでは三角関数を認識することができないため、テストパターンから積分と三角関数の式を除いて評価実験を行った。

第１の行統合処理と第２の行統合処理と数式認識による選択処理を追加した方式では、第１の行統合処理と第２の行統合処理を追加した方式に比べて、行切出し精度が約０．４６ポイント向上した。また、長い分数罫をもつ分数の誤分割に加えて、短い分数罫をもつ分数の誤分割にも効果があることを確認した。このように、数式認識による選択処理を更に追加した方式によって複数行にわたる手書き数式の行切出しの精度がより高くなることを確認した。

なお、本発明は、上述の実施の形態に限定されるものではなく、種々の変更が可能である。本発明は、実施の形態で説明した構成と実質的に同一の構成（例えば、機能、方法及び結果が同一の構成、あるいは目的及び効果が同一の構成）を含む。また、本発明は、実施の形態で説明した構成の本質的でない部分を置き換えた構成を含む。また、本発明は、実施の形態で説明した構成と同一の作用効果を奏する構成又は同一の目的を達成することができる構成を含む。また、本発明は、実施の形態で説明した構成に公知技術を付加した構成を含む。

例えば、基本方式の処理（行切出し処理）の後に、行方向を検出して補正する処理（回転補正）を行ってから、行統合処理を行うようにしてもよい。行方向は、ストローク列から検出した直線状のストロークの向きから求めてもよいし、切出された行における最初のストロークの始点座標と最後のストロークの終点座標から求めてもよい。

また、上記実施形態では、分数の誤分割を解消するために、基本方式に第２の行統合処理を追加する例について説明したが、本発明はこれに限られない。例えば、基本方式に第２の行統合処理を追加することに代えて、基本方式のグループ分け処理（ステップＳ１）を変更して、分数の誤分割を解消するためのブロック統合処理に置き換えてもよい。このブロック統合処理は、行ではなくブロック同士を統合する点で第２の行統合処理と異なるが、それ以外の基本的な動作は第２の行統合処理と同様である。すなわち、ブロック統合処理では、ストローク列を複数のブロックに分ける処理を行った後、ブロック内のストローク列における各ストロークの外接矩形の高さＨ及び幅Ｗをそれぞれ閾値β及び閾値γと比較して長い水平線分のストロークを検出し、検出したストロークがルート記号の直線部分でないと判断されれば、検出したストロークを分数罫に対応するストロークであると判断する。そして、分数罫に対応するストロークと他のブロック（分数罫に対応するストロークを含むブロックとは異なるブロック）がｘ軸上で離れておらず、且つ、分数罫に対応するストロークの外接矩形の上端と当該他のブロックの外接矩形の下端との垂直方向の距離又は分数罫に対応するストロークの外接矩形の下端と当該他のブロックの外接矩形の上端との垂直方向の距離が閾値δよりも小さい場合に、当該他のブロックを分数罫に対応するストロークを含むブロックに統合する。

１００処理部、１１０行切出し部、１１２行統合部、１１４認識部、１２０表示制御部、１６０文字入力部、１７０記憶部、１９０表示部

Claims

手書き入力された複数行にわたる数式のストローク列から行を切り出す処理を行うためのプログラムであって、
前記ストローク列におけるストローク間のオフストロークの長さに基づいて、前記ストローク列から行を切出す処理を行う行切出し部と、
切出されたｎ（ｎは自然数）行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形と、ｍ（ｍはｎとは異なる自然数）行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形との位置関係に基づいて、ｎ行目のストローク列とｍ行目のストローク列が同一行であるか否かを判断し、同一行であると判断した場合に、ｎ行目のストローク列とｍ行目のストローク列とを同一行に統合する行統合処理を行う行統合部としてコンピュータを機能させることを特徴とするプログラム。
請求項１において、
前記行統合部は、
切出されたｎ行目のストローク列の外接矩形と、ｎ＋１行目のストローク列の外接矩形との垂直方向の距離を求め、求めた距離が所定の閾値よりも小さい場合に、ｎ行目のストローク列とｎ＋１行目のストローク列とを同一行に統合する行統合処理を行うことを特徴とするプログラム。
請求項１又は２において、
前記行統合部は、
切出されたｎ行目のストローク列に分数罫に対応するストロークが存在するか否かを判定し、当該ストロークが存在すると判定した場合に、当該ストロークの外接矩形の上端とｍ行目のストローク列の外接矩形の下端との垂直方向の距離と、当該ストロークの外接矩形の下端とｍ行目のストローク列の外接矩形の上端との垂直方向の距離とを求め、求めたいずれかの距離が所定の閾値よりも小さい場合に、ｎ行目のストローク列とｍ行目のストローク列とを同一行に統合する行統合処理を行うことを特徴とするプログラム。
請求項１乃至３のいずれか１項において、
前記行切出し部は、
前記ストローク列におけるストローク間のオフストロークの長さに基づいて、行切出し候補点となるオフストロークを決定し、前記行切出し候補点を用いて複数の行切出し候補を生成し、
前記行統合部は、
複数の前記行切出し候補のそれぞれについて前記行統合処理を行った後、複数の前記行切出し候補のそれぞれについて数式認識を行って数式の確からしさを求め、数式の確からしさの値が最も大きい前記行切出し候補を選択することを特徴とするプログラム。
コンピュータ読み取り可能な情報記憶媒体であって、請求項１乃至４のいずれか１項のプログラムを記憶したことを特徴とする情報記憶媒体。
手書き入力された複数行にわたる数式のストローク列から行を切り出す処理を行う情報処理装置であって、
前記ストローク列におけるストローク間のオフストロークの長さに基づいて、前記ストローク列から行を切出す処理を行う行切出し部と、
切出されたｎ（ｎは自然数）行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形と、ｍ（ｍはｎとは異なる自然数）行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形との位置関係に基づいて、ｎ行目のストローク列とｍ行目のストローク列が同一行であるか否かを判断し、同一行であると判断した場合に、ｎ行目のストローク列とｍ行目のストローク列とを同一行に統合する統合処理を行う行統合部とを含むことを特徴とする情報処理装置。