TOP > 国内特許検索 > プログラム、情報記憶媒体及び情報処理装置 > 明細書

明細書 :プログラム、情報記憶媒体及び情報処理装置

発行国 日本国特許庁(JP)
公報種別 再公表特許(A1)
発行日 平成30年8月2日(2018.8.2)
発明の名称または考案の名称 プログラム、情報記憶媒体及び情報処理装置
国際特許分類 G06K   9/00        (2006.01)
G06K   9/62        (2006.01)
G06K   9/20        (2006.01)
FI G06K 9/00 P
G06K 9/62 G
G06K 9/20 310Y
G06K 9/20 340K
国際予備審査の請求 未請求
全頁数 21
出願番号 特願2017-546498 (P2017-546498)
国際出願番号 PCT/JP2016/079925
国際公開番号 WO2017/069001
国際出願日 平成28年10月7日(2016.10.7)
国際公開日 平成29年4月27日(2017.4.27)
優先権出願番号 2015205354
優先日 平成27年10月19日(2015.10.19)
優先権主張国 日本国(JP)
指定国 AP(BW , GH , GM , KE , LR , LS , MW , MZ , NA , RW , SD , SL , ST , SZ , TZ , UG , ZM , ZW) , EA(AM , AZ , BY , KG , KZ , RU , TJ , TM) , EP(AL , AT , BE , BG , CH , CY , CZ , DE , DK , EE , ES , FI , FR , GB , GR , HR , HU , IE , IS , IT , LT , LU , LV , MC , MK , MT , NL , NO , PL , PT , RO , RS , SE , SI , SK , SM , TR) , OA(BF , BJ , CF , CG , CI , CM , GA , GN , GQ , GW , KM , ML , MR , NE , SN , TD , TG) , AE , AG , AL , AM , AO , AT , AU , AZ , BA , BB , BG , BH , BN , BR , BW , BY , BZ , CA , CH , CL , CN , CO , CR , CU , CZ , DE , DJ , DK , DM , DO , DZ , EC , EE , EG , ES , FI , GB , GD , GE , GH , GM , GT , HN , HR , HU , ID , IL , IN , IR , IS , JP , KE , KG , KN , KP , KR , KW , KZ , LA , LC , LK , LR , LS , LU , LY , MA , MD , ME , MG , MK , MN , MW , MX , MY , MZ , NA , NG , NI , NO , NZ , OM , PA , PE , PG , PH , PL , PT , QA , RO , RS , RU , RW , SA , SC , SD , SE , SG , SK , SL , SM , ST , SV , SY , TH , TJ , TM , TN , TR , TT , TZ , UA
発明者または考案者 【氏名】中川 正樹
【氏名】佐々木 進亮
出願人 【識別番号】504132881
【氏名又は名称】国立大学法人東京農工大学
個別代理人の代理人 【識別番号】100090398、【弁理士】、【氏名又は名称】大渕 美千栄
【識別番号】100090387、【弁理士】、【氏名又は名称】布施 行夫
審査請求 未請求
テーマコード 5B029
5B064
Fターム 5B029BB09
5B029CC28
5B064AB04
5B064AB13
5B064AB17
5B064BA06
5B064DD06
5B064DD13
要約 情報処理装置は、入力されたストローク列におけるストローク間のオフストロークの長さに基づいて、ストローク列から行を切出す処理を行う行切出し部と、切出されたn(nは自然数)行目のストローク列の外接矩形の中心と、n+1行目のストローク列の外接矩形の中心との垂直方向の距離を求め、求めた距離が所定の閾値よりも小さい場合に、n行目のストローク列とn+1行目のストローク列とを同一行に統合する行統合部とを含む。
特許請求の範囲 【請求項1】
手書き入力された複数行にわたる数式のストローク列から行を切り出す処理を行うためのプログラムであって、
前記ストローク列におけるストローク間のオフストロークの長さに基づいて、前記ストローク列から行を切出す処理を行う行切出し部と、
切出されたn(nは自然数)行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形と、m(mはnとは異なる自然数)行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形との位置関係に基づいて、n行目のストローク列とm行目のストローク列が同一行であるか否かを判断し、同一行であると判断した場合に、n行目のストローク列とm行目のストローク列とを同一行に統合する行統合処理を行う行統合部としてコンピュータを機能させることを特徴とするプログラム。
【請求項2】
請求項1において、
前記行統合部は、
切出されたn行目のストローク列の外接矩形と、n+1行目のストローク列の外接矩形との垂直方向の距離を求め、求めた距離が所定の閾値よりも小さい場合に、n行目のストローク列とn+1行目のストローク列とを同一行に統合する行統合処理を行うことを特徴とするプログラム。
【請求項3】
請求項1又は2において、
前記行統合部は、
切出されたn行目のストローク列に分数罫に対応するストロークが存在するか否かを判定し、当該ストロークが存在すると判定した場合に、当該ストロークの外接矩形の上端とm行目のストローク列の外接矩形の下端との垂直方向の距離と、当該ストロークの外接矩形の下端とm行目のストローク列の外接矩形の上端との垂直方向の距離とを求め、求めたいずれかの距離が所定の閾値よりも小さい場合に、n行目のストローク列とm行目のストローク列とを同一行に統合する行統合処理を行うことを特徴とするプログラム。
【請求項4】
請求項1乃至3のいずれか1項において、
前記行切出し部は、
前記ストローク列におけるストローク間のオフストロークの長さに基づいて、行切出し候補点となるオフストロークを決定し、前記行切出し候補点を用いて複数の行切出し候補を生成し、
前記行統合部は、
複数の前記行切出し候補のそれぞれについて前記行統合処理を行った後、複数の前記行切出し候補のそれぞれについて数式認識を行って数式の確からしさを求め、数式の確からしさの値が最も大きい前記行切出し候補を選択することを特徴とするプログラム。
【請求項5】
コンピュータ読み取り可能な情報記憶媒体であって、請求項1乃至4のいずれか1項のプログラムを記憶したことを特徴とする情報記憶媒体。
【請求項6】
手書き入力された複数行にわたる数式のストローク列から行を切り出す処理を行う情報処理装置であって、
前記ストローク列におけるストローク間のオフストロークの長さに基づいて、前記ストローク列から行を切出す処理を行う行切出し部と、
切出されたn(nは自然数)行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形と、m(mはnとは異なる自然数)行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形との位置関係に基づいて、n行目のストローク列とm行目のストローク列が同一行であるか否かを判断し、同一行であると判断した場合に、n行目のストローク列とm行目のストローク列とを同一行に統合する統合処理を行う行統合部とを含むことを特徴とする情報処理装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、プログラム、情報記憶媒体及び情報処理装置に関する。
【背景技術】
【0002】
従来、数式を入力する手法として、LaTeXなどの専門言語を用いる方法や、数式入力エディタを用いる方法等が用いられてきたが、前者は専門用語を習得する必要があり、後者はメニュー選択と記号選択を繰り返す必要があり、ともに一般人には使い勝手が悪かった。これに対して、タブレットなどに手書きされた数式をコンピュータにより認識させる方法は古くから研究されてきた(例えば、特開2009-80615号公報)。そして、近年におけるタブレット型PCの急速な普及から一般人に浸透する可能性も増しており、教育現場では、電子黒板やタブレットの導入が急速に進んでいる。
【発明の概要】
【発明が解決しようとする課題】
【0003】
計算式を筆記する場合、数式は複数行にわたって展開や変形が行われるため、数式認識では行切出しが不可欠となる。ところが従来の手書き数式認識システムでは、1行ごとに入力された数式を対象としており、途中式などの複数行にわたる数式の行切出しを行って(複数行の数式における改行を検出して)数式を認識することはできなかった。
【0004】
本発明は、以上のような課題に鑑みてなされたものであり、その目的とするところは、複数行にわたる手書き数式の行切出しを行うことが可能なプログラム、情報記憶媒体及び情報処理装置を提供することにある。
【課題を解決するための手段】
【0005】
(1)本発明は、手書き入力された複数行にわたる数式のストローク列から行を切り出す処理を行うためのプログラムであって、前記ストローク列におけるストローク間のオフストロークの長さに基づいて、前記ストローク列から行を切出す処理を行う行切出し部と、切出されたn(nは自然数)行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形と、m(mはnとは異なる自然数)行目のストローク列の外接矩形又は当該ストローク列におけるストロークの外接矩形との位置関係に基づいて、n行目のストローク列とm行目のストローク列が同一行であるか否かを判断し、同一行であると判断した場合に、n行目のストローク列とm行目のストローク列とを同一行に統合する行統合処理を行う行統合部としてコンピュータを機能させるプログラムに関する。また、本発明は、コンピュータ読み取り可能な情報記憶媒体であって、上記各部としてコンピュータを機能させるためのプログラムを記憶した情報記憶媒体に関係する。また、本発明は、上記各部を含む情報処理装置に関係する。
【0006】
本発明によれば、ストローク列におけるストローク間のオフストロークの長さに基づいて、ストローク列から行を切出す処理を行った後に、切出されたn行目のストローク列の外接矩形(又はストロークの外接矩形)と、m行目のストローク列の外接矩形(又はストロークの外接矩形)との位置関係に基づいて、n行目のストローク列とm行目のストローク列が同一行であるか否かを判断し、同一行であると判断した場合に、n行目のストローク列とm行目のストローク列とを同一行に統合する処理を行うことで、複数行にわたる手書き数式の行切出しを精度良く行うことができる。
【0007】
(2)また本発明に係るプログラム、情報記憶媒体及び情報処理装置では、前記行統合部は、
切出されたn行目のストローク列の外接矩形と、n+1行目のストローク列の外接矩形との垂直方向の距離を求め、求めた距離が所定の閾値よりも小さい場合に、n行目のストローク列とn+1行目のストローク列とを同一行に統合する行統合処理を行ってもよい。
【0008】
本発明によれば、n行目のストローク列の外接矩形と、n+1行目のストローク列の外接矩形との垂直方向の距離が所定の閾値αよりも小さい場合に、n行目のストローク列とn+1行目のストローク列とを同一行に統合することで、括弧などの書き足しによる誤分割(改行の誤検出)を解消して、複数行にわたる手書き数式の行切出しを精度良く行うことができる。
【0009】
(3)また本発明に係るプログラム、情報記憶媒体及び情報処理装置では、前記行統合部は、切出されたn行目のストローク列に分数罫に対応するストロークが存在するか否かを判定し、当該ストロークが存在すると判定した場合に、当該ストロークの外接矩形の上端とm行目のストローク列の外接矩形の下端との垂直方向の距離と、当該ストロークの外接矩形の下端とm行目のストローク列の外接矩形の上端との垂直方向の距離とを求め、求めたいずれかの距離が所定の閾値よりも小さい場合に、n行目のストローク列とm行目のストローク列とを同一行に統合する行統合処理を行ってもよい。
【0010】
本発明によれば、n行目のストローク列に含まれる分数罫に対応するストロークを検出し、当該ストロークの外接矩形の上端とn-1行目のストローク列の外接矩形の下端との垂直方向の距離が所定の閾値δよりも小さい場合に、n行目のストローク列とn-1行目のストローク列とを同一行に統合し、当該ストロークの外接矩形の下端とn+1行目のストローク列の外接矩形の上端との垂直方向の距離が所定の閾値δよりも小さい場合に、n行目のストローク列とn+1行目のストローク列とを同一行に統合することで、分数が複数の行として切出されてしまうことを防止して、複数行にわたる手書き数式の行切出しを精度良く行うことができる。
【0011】
(4)また本発明に係るプログラム、情報記憶媒体及び情報処理装置では、前記行切出し部は、前記ストローク列におけるストローク間のオフストロークの長さに基づいて、行切出し候補点となるオフストロークを決定し、前記行切出し候補点を用いて複数の行切出し候補を生成し、前記行統合部は、複数の前記行切出し候補のそれぞれについて前記行統合処理を行った後、複数の前記行切出し候補のそれぞれについて数式認識を行って数式の確からしさを求め、数式の確からしさの値が最も大きい前記行切出し候補を選択してもよい。
【0012】
本発明によれば、複数の行切出し候補のそれぞれについて行統合処理を行った後、複数の行切出し候補のそれぞれについて数式認識を行って数式の確からしさを求め、数式の確からしさの値が最も大きい行切出し候補を選択することで、複数行にわたる手書き数式の行切出しをより精度良く行うことができる。
【図面の簡単な説明】
【0013】
【図1】図1は、本実施形態の認識装置(情報処理装置)の機能ブロック図の一例である。
【図2】図2は、本実施形態の行切出し手法を模式的に示す図である。
【図3】図3は、基本方式の第1ステップについて説明するための図である。
【図4】図4は、基本方式の第2ステップについて説明するための図である。
【図5】図5は、基本方式の第3ステップについて説明するための図である。
【図6A】図6Aは、基本方式による誤分割の具体例を示す図である。
【図6B】図6Bは、基本方式による誤分割の具体例を示す図である。
【図7】図7は、第1の行統合処理の一例を示すフローチャートである。
【図8A】図8Aは、第1の行統合処理の具体例を示す図である。
【図8B】図8Bは、第1の行統合処理の具体例を示す図である。
【図9】図9は、第2の行統合処理の一例を示すフローチャートである。
【図10】図10は、第2の行統合処理の一例を示すフローチャートである。
【図11】図11は、図9のステップS25の処理の詳細を示すフローチャートである。
【図12A】図12Aは、第2の行統合処理の具体例を示す図である。
【図12B】図12Bは、第2の行統合処理の具体例を示す図である。
【図12C】図12Cは、第2の行統合処理の具体例を示す図である。
【図13】図13は、数式認識による選択処理について説明するための図である。
【図14】図14は、逐次方式における処理の一例を示すフローチャートである。
【発明を実施するための形態】
【0014】
以下、本実施形態について説明する。なお、以下に説明する本実施形態は、請求の範囲に記載された本発明の内容を不当に限定するものではない。また本実施形態で説明される構成の全てが、本発明の必須構成要件であるとは限らない。

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

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

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

【0018】
表示部190は、処理部100で生成された画像を出力するものであり、その機能は、文字入力部160としても機能するタッチパネル、LCD或いはCRTなどのディスプレイにより実現できる。

【0019】
処理部100(プロセッサ)は、文字入力部160からの座標データやプログラムなどに基づいて、行切出し処理、行統合処理、認識処理、表示制御などの処理を行う。この処理部100は記憶部170内の主記憶部をワーク領域として各種処理を行う。処理部100の機能は各種プロセッサ(CPU、DSP等)、ASIC(ゲートアレイ等)などのハードウェアや、プログラムにより実現できる。処理部100は、行切出し部110、行統合部112、認識部114、表示制御部120を含む。

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

【0021】
行統合部112は、行切出し部110で切出されたn(nは自然数)行目のストローク列の外接矩形の中心と、n+1行目のストローク列の外接矩形の中心との垂直方向の距離を求め、求めた距離が所定の閾値αよりも小さい場合に、n行目のストローク列とn+1行目のストローク列とを同一行に統合する第1の行統合処理を行う。

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

【0023】
また、行統合部112は、行切出し部110で生成された複数の行切出し候補のそれぞれについて行統合処理(第1の行統合処理、及び/又は第2の行統合処理)を行った後、複数の行切出し候補のそれぞれについて数式認識を行って数式の確からしさを求め、複数の行切出し候補のうち、数式の確からしさの値が最も大きい行切出し候補を選択して出力してもよい。

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

【0025】
表示制御部120は、入力されたストローク列を表示部190に表示させる制御と、認識部114により認識された複数行にわたる数式(認識結果)を表示部190に表示させる制御を行う。

【0026】
2.本実施形態の手法
2-1.基本方式
図2は、本実施形態の行切出し手法を模式的に示す図である。本実施形態の手法では、まず、文字列認識における行切出しの方式を基本方式として用いて数式の行切出しを行う。この基本方式は、ストローク列を複数のブロックに分ける処理(ステップS1)、行切出し候補点となるオフストロークを決定する処理(ステップS2)、行切出し候補点を用いて複数の行切出し候補を生成する処理(ステップS3)の3ステップから成る。

【0027】
基本方式のステップS1では、行切出し部110は、入力されたストローク列STに含まれるオフストロークOSのうち閾値Bを超える長さをもつオフストロークOSを検出し、閾値Bを超える長さをもつオフストロークOSで区切られる連続するストローク列をブロックBLとして分ける(図3参照)。図3に示す例では、数式「5+2=7」「7+3=10」に対応するストローク列STが、「5+」、「2」、「=」、「7」、「7」、「+3」、「=」、「1」、「0」に対応する9個のブロックBLに分けられている。閾値Bは平均文字サイズを基準として決定され、ここでは、閾値Bを平均文字サイズの0.8倍としている。平均文字サイズは入力されたストローク列から求めることができる。すなわち、入力された各ストロークの外接矩形を求め、各外接矩形の垂直(縦)方向又は水平(横)方向の長さが大きい順に各外接矩形をソートすることで、各外接矩形の垂直方向又は水平方向の長さの平均値を求める。そして、求めた平均値を平均文字サイズとする。

【0028】
基本方式のステップS2では、行切出し部110は、ブロックBL間のオフストロークOS(前のブロックBLの最後のストロークと次のブロックBLの最初のストローク間のオフストローク)のうち閾値Lを超える長さをもつオフストロークOSを検出し、閾値Lを超える長さをもつオフストロークOSを行切出し候補点SPとして設定する(図4参照)。なお、ここでは閾値Lを平均文字サイズの5倍としている。図4に示す例では、5点の行切出し候補点SP~SPが設定されている。また、図中Sは、ストローク列STの開始点であり、図中Eは、ストローク列STの終了点である。

【0029】
基本方式のステップS3では、行切出し部110は、ステップS2で得られた全ての行切出し候補点SP(及び、開始点S、終了点E)を用いて行切出し候補ラティスLTを生成し(図5参照)、6つのグローバル特徴量を入力としてMCE(Minimum Classification Error Training)で訓練された線形判別式によって上位複数の経路(上位複数の行切出し候補)を求める。図5に示す例では、「S」→「SP」→「E」の経路(すなわち、「5+2=7」を1行目とし、「7+3=10」を2行目とする行切出し候補)が、線形判別式とビームサーチによって得られる最適な経路(第1位の行切出し候補)となる。

【0030】
ここで、基本方式(ステップS1~S3)によって複数行にわたる数式を行切出しすると、括弧などの書き足しによる誤分割や、分数の誤分割(分数が複数の行として切出されてしまう)が生じる場合がある。図6A、図6Bに、基本方式による誤分割の具体例を示す。図6に示す外接矩形CRは、それぞれストローク列から切出された行を示している。図6Aは、書き足しによる誤分割の例であり、先頭行の「(x-9x+20)(x-7)」において、「x-9x+20」が筆記された後に、その左側に開き括弧が筆記され、右側に閉じ括弧が筆記されたことで、開き括弧から閉じ括弧へのオフストロークの長さが閾値Lを超えたため、「(x-9x+20」と「)(x-7)」の2行に過分割されてしまっている。図6Bは、分数の誤分割の例であり、分数の分子、分母、分数罫(括線)がそれぞれ1つの行として過分割されてしまっている。

【0031】
2-2.第1の行統合処理
本実施形態の手法では、括弧などの書き足しによる誤分割を解消するために、基本方式の3ステップの後に、第1の行統合処理(図2のステップS4)を追加して実行する。なお、ステップS4以降の処理は、ステップS3で得られた複数の行切出し候補ごとに行われる。

【0032】
図7は、第1の行統合処理の一例を示すフローチャートである。まず、行統合部112は、行番号を表す変数iに1をセットする(ステップS10)。なお、図中のループ開始端(ステップS10)には、「変数=初期値、終値、増分値」を記載し、ループ終了端(ステップS16)には、「変数」を記載している。ここで、変数LNは、切出された行の総数を表す変数である。

【0033】
次に、行統合部112は、i行目のストローク列の外接矩形の中心とi+1行目のストローク列の外接矩形の中心との垂直方向の距離Dyを算出する(ステップS11)。すなわち、i行目のストローク列の外接矩形の中心のy座標とi+1行目のストローク列の外接矩形の中心のy座標の差の絶対値を距離Dyとして求める。次に、行統合部112は、距離Dyが閾値αよりも小さいか否かを判断する(ステップS12)。なお、閾値αは、平均文字サイズを基準として実験により決定する。距離Dyが閾値α以上である場合(ステップS12のN)には、ステップS16に移行する。距離Dyが閾値αよりも小さい場合(ステップS12のY)には、行統合部112は、i行目のストローク列とi+1行目のストローク列とを同一行に統合し(ステップS13)、変数LNを1だけ減算し(ステップS14)し、変数iを1だけ減算する(ステップS15)。以降、変数iを1ずつ加算しながら、変数iが変数LNに達するまで、ステップS11~S15の処理を繰り返す。

【0034】
図8A、図8Bに、第1の行統合処理の具体例を示す。図8Aに示す例では、先頭行の数式において括弧の書き足しによる過分割が生じている。まず、図8Aに示すように、1行目の外接矩形CRの中心Cのy座標と2行目の外接矩形CRの中心Cのy座標の差の絶対値(距離Dy)を求め、距離Dyと閾値αとを比較する。ここでは、1行目と2行目について求めた距離Dyが閾値αよりも小さいため、1行目と2行目を統合して新たな1行目とする。次に、図8Bに示すように、新たな1行目の外接矩形CR’の中心C’のy座標と新たな2行目の外接矩形CR’の中心C’のy座標の差の絶対値(距離Dy)を求め、閾値αと比較する。ここでは、新たな1行目と新たな2行目について求めた距離Dyが閾値αよりも大きいため、統合せずに次の行に進む。図8Bに示す例では次の行(3行目)がないため第1の行統合処理を終了する。このように、第1の行統合処理により、括弧などの書き足しによる誤分割を解消することができる。

【0035】
2-3.第2の行統合処理
本実施形態の手法では、分数の誤分割を解消するために、第1の行統合処理の後に、第2の行統合処理(図2のステップS5)を実行する。なお、第2の行統合処理を行った後に第1の行統合処理を行ってもよく、また、第1の行統合処理と第2の行統合処理のいずれか一方を省略してもよい。

【0036】
図9、図10は、第2の行統合処理の一例を示すフローチャートである。まず、行統合部112は、行番号を表す変数iに1をセットし(ステップS20)、i行目内のブロック番号を表す変数jに1をセットし(ステップS21)、j番目のブロック内のストローク番号を表す変数sに1をセットする(ステップS22)。ここで、変数BNは、i行目内のブロックの総数であり、変数SNは、j番目のブロック内のストロークの総数である。

【0037】
次に、行統合部112は、s番目のストロークの外接矩形の高さHと幅Wを取得し(ステップS23)、高さHが閾値βよりも小さく且つ幅Wが閾値γよりも大きいか(s番目のストロークが長い水平線分に相当するストロークであるか)否かを判断する(ステップS24)。なお、閾値β、γは、平均文字サイズを基準として実験により決定する。高さHが閾値βよりも小さく且つ幅Wが閾値γよりも大きい場合(ステップS24のY)には、行統合部112は、s番目のストロークがルート記号の水平線(直線部分)に相当するストロークであるか否かを判断する(ステップS25)。ステップS25の処理の詳細については後述する。s番目のストロークの外接矩形の高さHが閾値β以上であるか幅Wが閾値γ以下である場合(ステップS24のN)、及びs番目のストロークがルート記号の水平線である場合(ステップS25のY)には、ステップS37に移行する。

【0038】
s番目のストロークがルート記号の水平線に相当するストロークでない場合(ステップS25のN)には、行統合部112は、s番目のストロークが分数罫に相当(対応)するストロークであると判断し、行番号を表す変数kに1をセットする(ステップS26)。次に、行統合部112は、変数iと変数kが一致するか否かを判断し(ステップS27)、一致しない場合(ステップS27のN)には、k行目とs番目のストロークが水平方向に重なっている(x軸上で離れていない)か否かを判断する(ステップS28)。例えば、k行目のストローク列の外接矩形の右端のx座標よりもs番目のストロークの外接矩形の左端のx座標が大きい場合、又はs番目のストロークの外接矩形の右端のx座標よりもk行目のストローク列の外接矩形の左端のx座標が大きい場合に、k行目とs番目のストロークが水平方向に重なっていないと判断する。変数iと変数kが一致する場合(ステップS27のY)、及びk行目とs番目のストロークが水平方向に重なっていない場合(ステップS28のN)、ステップS36に移行する。

【0039】
k行目とs番目のストロークが水平方向に重なっている場合(ステップS28のY)には、行統合部112は、s番目のストロークの外接矩形の上端とk行目のストローク列の外接矩形の下端との垂直方向の距離Dt(s番目のストロークの外接矩形の上端のy座標とk行目のストローク列の外接矩形の下端のy座標の差の絶対値)を算出し(ステップS29)、s番目のストロークの外接矩形の下端とk行目のストローク列の外接矩形の上端との垂直方向の距離Db(s番目のストロークの外接矩形の下端のy座標とk行目のストローク列の外接矩形の上端のy座標の差の絶対値)を算出する(ステップS30)。次に、行統合部112は、距離Dtが閾値δよりも小さいか又は距離Dbが閾値δよりも小さいか否かを判断する(ステップS31)。なお、閾値δは、平均文字サイズを基準として実験により決定する。距離Dtが閾値δ以上であり且つ距離Dbが閾値δ以上である場合(ステップS31のN)には、ステップS36に移行する。距離D及び距離Dbの少なくとも一方が閾値δよりも小さい場合(ステップS31のY)には、行統合部112は、i行目のストローク列とk行目のストローク列とを同一行に統合し(ステップS32)、変数LNを1だけ減算する(ステップS33)。次に、行統合部112は、変数iが変数kよりも小さいか否かを判断し(ステップS34)、変数iが変数kよりも小さい場合(ステップS34のY)には、変数kを1だけ減算する(ステップS35)。

【0040】
以降、変数kを1ずつ加算しながら、変数kが変数LNを超えるまで、ステップS27~S35の処理を繰り返す。また、変数kが変数LNに達した場合、変数sを1ずつ加算しながら、変数sが変数SNを超えるまで、ステップS23~S36の処理を繰り返す。また、変数sが変数SNに達した場合、変数jを1ずつ加算しながら、変数jが変数BNを超えるまで、ステップS22~S37の処理を繰り返す。また、変数jが変数BNに達した場合、変数iを1ずつ加算しながら、変数iが変数LNを超えるまで、ステップS21~S38の処理を繰り返す。

【0041】
図11は、図9のステップS25の処理の詳細を示すフローチャートである。まず、行統合部112は、変数jに1をセットし(ステップS40)、j番目のブロック内のストローク番号を表す変数mに1をセットする(ステップS41)。次に、行統合部112は、変数mが変数sと一致するか否かを判断し(ステップS42)、一致する場合(ステップS42のY)、ステップS48に移行する。

【0042】
ステップS42の条件を満たさない場合には、行統合部112は、m番目のストロークの外接矩形の中心がs番目のストロークの外接矩形の左端よりも左側に位置する(m番目のストロークの外接矩形の中心のx座標≦s番目のストロークの外接矩形の左端のx座標)か否かを判断する(ステップS43)。ステップS43の条件を満たす場合には、行統合部112は、m番目のストロークの外接矩形の中心とs番目のストロークの外接矩形の左端との水平方向の距離(m番目のストロークの外接矩形の中心のx座標とs番目のストロークの外接矩形の左端のx座標との差の絶対値)が閾値Pよりも小さいか否かを判断する(ステップS44)。ステップS44の条件を満たす場合には、行統合部112は、m番目のストロークの外接矩形の上端とs番目のストロークの外接矩形の上端との垂直方向の距離(m番目のストロークの外接矩形の上端のy座標とs番目のストロークの外接矩形の上端のy座標との差の絶対値)が閾値Qよりも小さいか否かを判断する(ステップS45)。ステップS45の条件を満たす場合には、行統合部112は、m番目のストロークの外接矩形の高さが閾値Rよりも大きいか否かを判断する(ステップS46)。なお、閾値P、Q、Rは、平均文字サイズを基準として実験により決定する。ステップS46の条件を満たす場合には、s番目のストロークがルート記号の水平線に相当するストロークであると判断する(ステップS47)。

【0043】
以降、変数mを1ずつ加算しながら、変数mが変数SNを超えるまで、ステップS42~S47の処理を繰り返す。また、変数mが変数SNに達した場合、変数jを1ずつ加算しながら、変数jが変数BNを超えるまで、ステップS41~S48の処理を繰り返す。

【0044】
図12A、図12B、図12Cに、第2の行統合処理の具体例を示す。図12Aに示す例では、2行目の数式において、分数の分子及び分数罫で1行、分母で1行として過分割されてしまっている。まず、1行目のストローク列における各ストロークの外接矩形の高さH及び幅Wをそれぞれ閾値β及び閾値γと比較して、長い水平線分を探す(図9のステップS24)と、1行目では検出されない。同様に、2行目のストローク列において水平線分を探すと、図12Aに示すように、2画で筆記されたルート記号の直線部分が水平線分LSとして検出される。検出された水平線分LSがルート記号の直線部分であるか否かを判定するために、2行目のストローク列において、水平線分LSとの関係において図11のステップS43~S46の条件を満たすストローク(2画で筆記されたルート記号の先頭部分)があるか否かを判定する。2行目にはステップS43~S46の条件を満たすストロークがあるため、水平線分LSをルート記号の直線部分と判断する。

【0045】
そして、2行目のストローク列において他の水平線分を探すと、図12Bに示すように、分数罫が水平線分LSとして検出される。検出された水平線分LSが2画で筆記されたルート記号の直線部分であるか否かを判定すると、2行目のストローク列において、水平線分LSとの関係において図11のステップS43~S46の条件を満たすストロークがないため、水平線分LSを分数罫と判断する。従って、水平線分LSを含む2行目を他の行と統合するか否かを判定する処理(図9のステップS26~図10のステップS36のループ処理)に進む。

【0046】
水平線分LSは1行目の外接矩形CRとx軸上で離れておらず(図9のステップS28のY)、また、水平線分LSの外接矩形の上端のy座標と1行目の外接矩形CRの下端のy座標との差の絶対値が閾値δよりも大きく、且つ水平線分LSの外接矩形の下端のy座標と1行目の外接矩形CRの上端のy座標との差の絶対値が閾値δよりも大きい(図9のステップS31のN)ため、1行目とは統合しない。水平線分LSを含む2行目は対象としないため、3行目について同様に判定すると、図12Cに示すように、水平線分LSは3行目の外接矩形CRとx軸上で離れておらず、また、水平線分LSの外接矩形の下端のy座標と3行目の外接矩形CRの上端のy座標との差の絶対値が閾値δよりも小さい(図9のステップS31のY)ため、2行と3行目を統合する(図9のステップS32)。図12Cに示す例では、これ以上対象となる行がないため第2の行統合処理を終了する。このように、第2の行統合処理により、分数の誤分割を解消することができる。分数罫の候補となる長い水平線分は、ルート記号が2画以上で筆記された場合にも出現するが、第2の行統合処理によれば、分数罫を2画で筆記されたルート記号の直線部分と明確に区別して検出することができ、分数の誤分割を精度良く解消することができる。

【0047】
2-4.数式認識による選択処理
本実施形態の手法では、行統合処理の後に、数式認識による選択処理(図2のステップS6)を実行する。なお、数式認識による選択処理を省略してもよい。

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

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

【0050】
【数1】
JP2017069001A1_000003t.gif
ここで、Psegjは、ストロークjとストロークj+1が2つシンボルに分割される確率を示し、Prec(S|G)は、ストローク列GがシンボルSとなる確率を示し、Prej(R|SE)は、文法要素関係Rによって、2つの文法要素の組SEが1つの大きい文法要素にまとめられる確率を示し、PGramは、文法規則がそれぞれ生起する確率を示す。

【0051】
図13に、第1の行統合処理が行われた後の、複数の行切出し候補の一例を示す。図13に示す例では、第1位候補において、分数を含む先頭行の数式が、「4×6」、分数罫、「2×4-6」、「(x+2)×4」の4行に誤分割されている。また、第2位候補においても、先頭行の数式が誤分割されている。また、第5位候補では正しく行切出しされている。

【0052】
第1位候補の数式の確からしさは、1行目の「4×6」の確率(数式の確からしさ)をP、2行目の分数罫の確率をP、3行目の「2×4-6」の確率をP、4行目の「(x+2)×4」の確率をPとすると、それらを掛け合わせたP×P×P×Pとなる。同様に、第2位候補の数式の確からしさは、1行目の確率をPとすると、P×P×Pとなり、第5位候補の数式の確からしさは、1行目の確率をPとすると、P×Pとなる。確率P~Pのうち、確率P、Pは数式としてあり得ないため低い率を示すが、その他の確率P、P、P、Pは高い率を示す。従って、図13に示す例では、確率P、Pを含まない第5位候補の確率(P×P)が行切出しの確からしさにおいて最も高い率を示し、第5位候補が最終的な行切出しの結果となる。このように、数式認識による選択処理によっても、分数の誤分割を解消することができる。

【0053】
上記の例では、複数行にわたる数式が筆記された後に、行切出し処理と数式認識処理を実行する場合について説明したが、数式の筆記途中で(筆画ごとに)行切出し処理と数式認識処理を実行することもできる(逐次方式)。図14は、逐次方式における処理の一例を示すフローチャートである。まず、ストローク番号を表す変数jに1をセットし(ステップS50)、ストローク番号を表す変数iに1をセットする(ステップS51)。ここで、変数TSは、ストロークの総数である。次に、j番目からi番目のストロークまで行切出しを行い(ステップS52)、i番目のストロークが新しい行の先頭のストロークであるか否かを判断する(ステップS53)。ステップS53の判断は、これまで示した方法により行う。i番目のストロークが新しい行の先頭のストロークでない場合(ステップS53のN)には、ステップS56に移行する。i番目のストロークが新しい行の先頭のストロークである場合(ステップS53のY)には、変数jに変数iの値をセットし(ステップS54)、手書き数式逐次認識内のストローク(認識対象となるストローク)をリセットする(ステップS55)。次に、j番目からi番目までのストロークから数式を認識する(ステップS56)。以降、変数iを1ずつ加算しながら、変数iが変数TSを超えるまで、ステップS52~S56の処理を繰り返す。また、上記の例では、行切出し候補点SPを用いて切出された行を処理単位として第1の行統合処理、第2の行統合処理及び数式認識による選択処理を行う場合について説明したが、行に含まれる1つ又は複数のブロックBLを処理単位としてこれらの処理を行ってもよい。

【0054】
3.評価実験
本実施形態の行切出し手法の評価及び学習に利用する複数行の手書き数式パターンとして、筆記者に予め指定した式を書き写してもらう方式と、筆記者に問題を解きながら書いてもらう方式とで、17人から計2,085行の手書き数式パターンを収集した。収集した複数行の手書き数式パターンには、正しい行切出しの情報を付与した。また、パターンを増やすために、収集したパターンから1行分の数式を選択し、その外接矩形を縦方向に一定間隔で、横方向に乱数で変動させることにより、総行数16,800行のパターン(人工パターン)を生成した。

【0055】
収集した2,085行のパターンを対象に、経験的に最適と思われる閾値の前後を列挙法により探索し、行切出し精度が一番高くなる値を閾値として設定した。その結果、閾値Bを0.7(平均文字サイズの0.7倍)とし、閾値Lを5とし、閾値αを0.7とし、閾値δを0.4とした。また、閾値β、γは、数式パターン中の長い水平線分のストロークの外接矩形と高さと幅を満たすように設定し、閾値P、Q、Rは、数式パターン中の2画で筆記されたルート記号の先頭部分のストロークの外接矩形の高さと位置を満たすように設定した。

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

【0057】
評価基準として次に定義する行切出し精度(単位:%)を用いた。

【0058】
【数2】
JP2017069001A1_000004t.gif
表1に、基本方式(図2のステップS1~S3)での行切出し精度と、基本方式に第1の行統合処理(図2のステップS4)を追加した方式での行切出し精度を示す。

【0059】
【表1】
JP2017069001A1_000005t.gif
収集パターンに人工パターンを追加しない場合、第1の行統合処理を追加した方式では、基本方式に比べて、行切出し精度が7.61ポイント向上した。また、収集パターンに人工パターンを追加した場合、第1の行統合処理を追加した方式では、基本方式に比べて、行切出し精度が8.16ポイント向上した。これらの結果に対してpaired-t検定を実施した。その結果、両側確率でそれぞれ3.42-8、1.36-7となり、危険率P=0.05で有意差ありと示された。このように、第1の行統合処理を追加した方式によって誤分割を効果的に解消できることが示された。また、括弧などの書き足しによる誤分割が全て解消されたことを確認した。また、収集パターンに収集パターンを含めることで行切出し精度は約1.2~1.6ポイント向上した。この結果に対してもpaired-t検定を実施し、両側確率で0.0007となり、危険率P=0.05で有意差ありと示された。

【0060】
表2に、基本方式に第1の行統合処理を追加した方式での行切出し精度と、基本方式に第1の行統合処理と第2の行統合処理(図2のステップS5)の両方を追加した方式での行切出し精度を示す。

【0061】
【表2】
JP2017069001A1_000006t.gif
収集パターンに人工パターンを追加しない場合、第1の行統合処理と第2の行統合処理の両方を追加した方式では、第1の行統合処理のみを追加した方式に比べて、行切出し精度が0.8ポイント向上した。また、収集パターンに人工パターンを追加した場合、第1の行統合処理と第2の行統合処理の両方を追加した方式では、第1の行統合処理のみを追加した方式に比べて、行切出し精度が0.75ポイント向上した。これらの結果に対してpaired-t検定を実施した。その結果、両側確率でそれぞれ0.00339、0.0037となり、危険率P=0.05で有意差ありと示された。このように、第1の行統合処理に第2の行統合処理を追加した方式によって分数の誤分割を効果的に解消できることが示唆された。また、ルート記号の直線部分が分数罫と誤認識されることはなかった。

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

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

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

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

【0066】
また、上記実施形態では、分数の誤分割を解消するために、基本方式に第2の行統合処理を追加する例について説明したが、本発明はこれに限られない。例えば、基本方式に第2の行統合処理を追加することに代えて、基本方式のグループ分け処理(ステップS1)を変更して、分数の誤分割を解消するためのブロック統合処理に置き換えてもよい。このブロック統合処理は、行ではなくブロック同士を統合する点で第2の行統合処理と異なるが、それ以外の基本的な動作は第2の行統合処理と同様である。すなわち、ブロック統合処理では、ストローク列を複数のブロックに分ける処理を行った後、ブロック内のストローク列における各ストロークの外接矩形の高さH及び幅Wをそれぞれ閾値β及び閾値γと比較して長い水平線分のストロークを検出し、検出したストロークがルート記号の直線部分でないと判断されれば、検出したストロークを分数罫に対応するストロークであると判断する。そして、分数罫に対応するストロークと他のブロック(分数罫に対応するストロークを含むブロックとは異なるブロック)がx軸上で離れておらず、且つ、分数罫に対応するストロークの外接矩形の上端と当該他のブロックの外接矩形の下端との垂直方向の距離又は分数罫に対応するストロークの外接矩形の下端と当該他のブロックの外接矩形の上端との垂直方向の距離が閾値δよりも小さい場合に、当該他のブロックを分数罫に対応するストロークを含むブロックに統合する。
【符号の説明】
【0067】
100 処理部、110 行切出し部、112 行統合部、114 認識部、120 表示制御部、160 文字入力部、170 記憶部、190 表示部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6A】
5
【図6B】
6
【図7】
7
【図8A】
8
【図8B】
9
【図9】
10
【図10】
11
【図11】
12
【図12A】
13
【図12B】
14
【図12C】
15
【図13】
16
【図14】
17