(57)【要約】【課題】文字列を少ない文字数に解釈する傾向や、文字列を多い文字数に解釈する傾向を弱めて、認識率を向上させることが可能なプログラム、情報記憶媒体及び文字列認識装置を提供すること。【解決手段】ストローク間のオフストロークのうち、仮切出しポイントとして設定するオフストロークを決定し、前記仮切出しポイントによって切り出された仮切出しユニット毎に文字認識を行い、候補文字列を生成する。前記仮切出しユニットは、隣接する前記仮切出しポイントにより切り出される最小仮切出しユニットを少なくとも１つ含む。前記候補文字列の各候補文字に対応する前記仮切出しユニットに含まれる前記最小仮切出しユニット、および隣接する前記最小切り出しユニット間の連結について、複数項目の確からしさを評価し、前記複数項目の確からしさについて各項目に与える重みの値を設定する。【選択図】図１１
2010039609.tif 000002
【特許請求の範囲】
【請求項１】
手書き入力された文字パタンのストロークから文字列を認識するためのプログラムであって、
ストローク間のオフストロークのうち、仮切出しポイントとして設定するオフストロークを決定する仮切出しポイント決定部と、
前記仮切出しポイントによって切り出された仮切出しユニット毎に文字認識を行い、候補文字列を生成する候補文字列生成部と、
前記候補文字列について複数項目の確からしさを評価し、評価結果に基づき文字列を認識する認識部としてコンピュータを機能させ、
前記仮切出しユニットは、隣接する前記仮切出しポイントにより切り出される最小仮切出しユニットを少なくとも１つ含み、
前記認識部は、
前記候補文字列の各候補文字に対応する前記仮切出しユニットに含まれる前記最小仮切出しユニット、および隣接する前記最小切出しユニット間の連結について、前記複数項目の確からしさを評価し、前記複数項目の確からしさについて各項目に与える重みの値を設定することを特徴とするプログラム。
【請求項２】
請求項１において、
前記認識部は、
前記候補文字列の前記最小仮切出しユニット、および隣接する前記最小切出しユニット間の連結について、言語文脈の確からしさ、文字パタンサイズの確からしさ、文字パタン内分割の確からしさ、文字認識の確からしさ、単一文字パタン位置の確からしさ、ペア文字パタン位置の確からしさ及び前記仮切出しポイントの確からしさを含む複数項目の確からしさを評価することを特徴とするプログラム。
【請求項３】
請求項２において、
前記認識部は、
前記仮切出しポイントを、隣接する文字パタン間の仮切出しポイントとして判断する場合には、前記仮切出しポイントが切出しポイントとして識別される確からしさを評価し、前記仮切出しポイントを、文字パタン内部の仮切出しポイントとして判断する場合には、前記仮切出しポイントが非切出しポイントとして識別される確からしさを評価することを特徴とするプログラム。
【請求項４】
請求項２又は３において、
前記仮切出しポイント決定部は、
前記オフストロークから抽出した多次元の特徴値をサポートベクターマシン（ＳＶＭ）に適用することで、前記仮切出しポイントのＳＶＭ出力値を求め、
前記認識部は、
前記ＳＶＭ出力値に基づき前記仮切出しポイントの確からしさを評価することを特徴とするプログラム。
【請求項５】
請求項１乃至４のいずれかにおいて、
前記認識部は、
遺伝的アルゴリズムにより学習した複数の重みの値を前記複数項目の確からしさに与えることを特徴とするプログラム。
【請求項６】
コンピュータ読み取り可能な情報記憶媒体であって、請求項１乃至５のいずれかのプログラムを記憶したことを特徴とする情報記憶媒体。
【請求項７】
手書き入力された文字パタンのストロークから文字列を認識する文字列認識装置であって、
ストローク間のオフストロークのうち、仮切出しポイントとして設定するオフストロークを決定する仮切出しポイント決定部と、
前記仮切出しポイントによって切り出された仮切出しユニット毎に文字認識を行い、候補文字列を生成する候補文字列生成部と、
前記候補文字列について複数項目の確からしさを評価し、評価結果に基づき文字列を認識する認識部とを含み、
前記仮切出しユニットは、隣接する前記仮切出しポイントにより切り出される最小仮切出しユニットを少なくとも１つ含み、
前記認識部は、
前記候補文字列の各候補文字に対応する前記仮切出しユニットに含まれる前記最小仮切出しユニット、および隣接する前記最小切出しユニット間の連結について、前記複数項目の確からしさを評価し、前記複数項目の確からしさについて各項目に与える重みの値を設定することを特徴とする文字列認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム、情報記憶媒体及び文字列認識装置に関する。
【背景技術】
【０００２】
従来から、与えられた文字列パタンを１文字ごとに分割して切出し候補とし、切出し候補に対応する文字パタンを文字認識して候補文字を出力し、候補文字列を評価して最適な文字列を認識結果として出力するオンライン文字列認識装置が知られている（例えば特許文献１参照）。
【特許文献１】特開平１１−３２８３１６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら従来の文字列認識装置では、文字列を少ない文字数に解釈する傾向や、文字列を多い文字数に解釈する傾向があった。
【０００４】
本発明は、以上のような課題に鑑みてなされたものであり、その目的とするところは、
文字列を少ない文字数に解釈する傾向や、文字列を多い文字数に解釈する傾向を弱めて、認識率を向上させることが可能なプログラム、情報記憶媒体及び文字列認識装置を提供することにある。
【課題を解決するための手段】
【０００５】
（１）本発明は、手書き入力された文字パタンのストロークから文字列を認識するためのプログラムであって、
ストローク間のオフストロークのうち、仮切出しポイントとして設定するオフストロークを決定する仮切出しポイント決定部と、
前記仮切出しポイントによって切り出された仮切出しユニット毎に文字認識を行い、候補文字列を生成する候補文字列生成部と、
前記候補文字列について複数項目の確からしさを評価し、評価結果に基づき文字列を認識する認識部としてコンピュータを機能させ、
前記仮切出しユニットは、隣接する前記仮切出しポイントにより切り出される最小仮切出しユニットを少なくとも１つ含み、
前記認識部は、
前記候補文字列の各候補文字に対応する前記仮切出しユニットに含まれる前記最小仮切出しユニット、および隣接する前記最小切出しユニット間の連結について、前記複数項目の確からしさを評価し、前記複数項目の確からしさについて各項目に与える重みの値を設定することを特徴とする。
【０００６】
また本発明は、上記各部を含む文字列認識装置に関係する。また本発明はコンピュータ読み取り可能な情報記憶媒体であって、上記各部としてコンピュータを機能させるプログラムを記憶した情報記憶媒体に関係する。
【０００７】
本発明によれば、各最小仮切出しユニットと隣接する最小仮切出しユニット間の連結について複数項目の確からしさを評価し、前記複数項目の各項目に適切な重みの値を設定することで、候補文字列の尤度評価を最小仮切出しユニットに基づき行うことができ、文字列候補の文字数に影響されず文字を認識することができる。すなわち、文字列を少ない文字数に解釈する傾向や、文字列を多い文字数に解釈する傾向を弱めて認識率を向上させることができる。
【０００８】
（２）また本発明に係るプログラム及び情報記憶媒体では、
前記認識部は、
前記候補文字列の前記最小仮切出しユニット、および隣接する前記最小切出しユニット間の連結について、言語文脈の確からしさ、文字パタンサイズの確からしさ、文字パタン内分割の確からしさ、文字認識の確からしさ、単一文字パタン位置の確からしさ、ペア文字パタン位置の確からしさ及び前記仮切出しポイントの確からしさを含む複数項目の確からしさを評価するようにしてもよい。
【０００９】
本発明によれば、各候補文字列について上記７項目の確からしさを評価することで、認識率を向上させることができる。
【００１０】
（３）また本発明に係るプログラム及び情報記憶媒体では、
前記認識部は、
前記仮切出しポイントを、隣接する文字パタン間の仮切出しポイントとして判断する場合には、前記仮切出しポイントが切出しポイントとして識別される確からしさを評価し、前記仮切出しポイントを、文字パタン内部の仮切出しポイントとして判断する場合には、前記仮切出しポイントが非切出しポイントとして識別される確からしさを評価するようにしてもよい。
【００１１】
本発明によれば、仮切出しポイントが文字パタン間にあるか、或いは文字パタン内部にあるかによって、それぞれ切出しポイントとして識別される確からしさ、或いは非切出しポイントとして識別される確からしさを評価することによって、文字列を少ない文字数に解釈する傾向や、文字列を多い文字数に解釈する傾向を弱めて認識率を向上させることができる。
【００１２】
（４）また本発明に係るプログラム及び情報記憶媒体では、
前記仮切出しポイント決定部は、
前記オフストロークから抽出した多次元の特徴値をサポートベクターマシン（ＳＶＭ）に適用することで、前記仮切出しポイントのＳＶＭ出力値を求め、
前記認識部は、
前記ＳＶＭ出力値に基づき前記仮切出しポイントの確からしさを評価するようにしてもよい。
【００１３】
本発明によれば、仮切出しポイントを多角的に評価することができる。
【００１４】
（５）また本発明に係るプログラム及び情報記憶媒体では、
前記認識部は、
遺伝的アルゴリズムにより学習した複数の重みの値を前記複数項目の確からしさに与えるようにしてもよい。
【発明を実施するための最良の形態】
【００１５】
以下、本実施形態について説明する。なお、以下に説明する本実施形態は、特許請求の範囲に記載された本発明の内容を不当に限定するものではない。また本実施形態で説明される構成の全てが、本発明の必須構成要件であるとは限らない。
【００１６】
１．構成
図１に本実施形態の文字列認識装置の機能ブロック図の一例を示す。なお本実施形態の文字列認識装置は図１の構成要素（各部）の一部を省略した構成としてもよい。
【００１７】
文字入力部１６０は、ユーザがペンで手書き文字を入力するためのものであり、その機能は、タブレット（筆記面）などにより実現できる。文字入力部１６０は、ペンが筆記面に触れてから離れるまでのペン先の位置を表す座標データを一定時間間隔で検出し、検出された座標データを筆点情報取得部１１０に出力する。
【００１８】
記憶部１７０は、処理部１００や通信部１９６などのワーク領域となるもので、その機能はＲＡＭなどにより実現できる。
【００１９】
情報記憶媒体１８０（コンピュータにより読み取り可能な媒体）は、プログラムやデータなどを格納するものであり、その機能は、光ディスク（ＣＤ、ＤＶＤ）、光磁気ディスク（ＭＯ）、磁気ディスク、ハードディスク、磁気テープ、或いはメモリ（ＲＯＭ）などにより実現できる。処理部１００は、情報記憶媒体１８０に格納されるプログラム（データ）に基づいて本実施形態の種々の処理を行う。即ち情報記憶媒体１８０には、本実施形態の各部としてコンピュータを機能させるためのプログラム（各部の処理をコンピュータに実行させるためのプログラム）が記憶される。
【００２０】
表示部１９０は、本実施形態により生成された画像を出力するものであり、その機能は、ＣＲＴ、ＬＣＤ、タッチパネル型ディスプレイ、或いはＨＭＤ（ヘッドマウントディスプレイ）などにより実現できる。
【００２１】
処理部１００（プロセッサ）は、文字入力部１６０からの座標データやプログラムなどに基づいて、認識処理、表示処理などの処理を行う。この処理部１００は記憶部１７０内の主記憶部１７２をワーク領域として各種処理を行う。処理部１００の機能は各種プロセッサ（ＣＰＵ、ＤＳＰ等）、ＡＳＩＣ（ゲートアレイ等）などのハードウェアや、プログラムにより実現できる。
【００２２】
処理部１００は、筆点情報取得部１１０、仮切出しポイント決定部１１２、候補文字列生成部１１４、認識部１１６、表示処理部１２０を含む。なおこれらの一部を省略する構成としてもよい。
【００２３】
筆点情報取得部１１０は、ペンが筆記面に触れてから離れるまでの座標データ列（筆点座標系列）をストロークのデータとして文字入力部１６０から取得する。また筆点情報取得部１１０は、他の情報処理装置からネットワーク及び通信部１９６を介してストロークのデータを取得するようにしてもよい。
【００２４】
仮切出しポイント決定部１１２は、ストローク間のオフストローク（ペンが筆記面から離れてから再び触れるまでのベクトル）のうち、仮切出しポイントとして設定するオフストロークを決定する。具体的には、オフストロークから距離や交わりを表す特徴値を抽出し、抽出した特徴値に基づき仮切出しポイントとして設定するオフストロークを決定する。
【００２５】
また仮切出しポイント決定部１１２は、前記オフストロークから抽出した多次元の特徴値をサポートベクターマシン（ＳＶＭ）に適用することで、前記仮切出しポイントのＳＶＭ出力値を求めるようにしてもよい。
【００２６】
候補文字列生成部１１４は、前記仮切出しポイントによって切り出された仮切出しユニット（隣接する前記仮切出しポイントにより切り出される最小仮切出しユニットを少なくとも１つ含む仮切出しユニット）毎に文字認識を行い、候補文字列を生成する。
【００２７】
認識部１１６は、前記候補文字列について複数項目の確からしさを評価し、評価結果に基づき文字列を認識する。また認識部１１６は、前記候補文字列の各候補文字に対応する前記仮切出しユニットに含まれる前記最小仮切出しユニット、および隣接する前記最小切出しユニット間の連結について、前記複数項目の確からしさを評価し、前記複数項目の確からしさについて各項目に適切な重みの値を設定する。
【００２８】
また認識部１１６は、前記候補文字列の各前記最小仮切出しユニットと隣接する前記最小切出しユニット間の連結について、言語文脈の確からしさ、文字パタンサイズの確からしさ、文字パタン内分割の確からしさ、文字認識の確からしさ、単一文字パタン位置の確からしさ、ペア文字パタン位置の確からしさ及び前記仮切出しポイントの確からしさを含む複数項目の確からしさを評価するようにしてもよい。
【００２９】
また認識部１１６は、前記仮切出しポイントを、隣接する文字パタン間の仮切出しポイントとして判断する場合には、前記仮切出しポイントが切出しポイントとして識別される確からしさを評価し、前記仮切出しポイントを、文字パタン内部の仮切出しポイントとして判断する場合には、前記仮切出しポイントが非切出しポイントとして識別される確からしさを評価するようにしてもよい。
【００３０】
また認識部１１６は、前記ＳＶＭ出力値に基づき前記仮切出しポイントの確からしさを評価するようにしてもよい。
【００３１】
また認識部１１６は、遺伝的アルゴリズムにより学習した複数の重みの値を前記複数項目の確からしさに与えるようにしてもよい。
【００３２】
表示処理部１２０は、認識部１１６により認識された文字列（認識結果）を表示部１９０に出力する。なお処理部１００は、認識部１１６による認識結果をネットワーク及び通信部１９６を介して他の情報処理装置に送信するようにしてもよい。
【００３３】
通信部１９６は、他の情報処理装置との間で通信を行うための各種制御を行うものであり、その機能は、各種プロセッサ又は通信用ＡＳＩＣなどのハードウェアや、プログラムなどにより実現できる。
【００３４】
なお本実施形態の各部としてコンピュータを機能させるためのプログラム（データ）は、サーバが有する情報記憶媒体からネットワーク及び通信部１９６を介して記憶部１７０、情報記憶媒体１８０に配信してもよい。このようなサーバの情報記憶媒体の使用も本発明の範囲内に含めることができる。
【００３５】
２．本実施形態の手法
次に本実施形態の手法について図面を用いて説明する。
【００３６】
２−１．仮切出しポイントの決定
本実施形態では、入力された各ストロークを、隣接するストローク間の距離や重なりなどの特徴によって、切出しポイント、非切出しポイントと不確定ポイントに分類する。切出しポイントは、２つの文字パタン間にあると判断されたポイントであり、非切出しポイントは、１つの文字パタンの内部にあると判断されたポイントである。また不確定ポイントは、切出しポイントであるか非切出しポイントであるかを決定できないポイントである。本実施形態では、切出しポイントと不確定ポイントとを仮切出しポイントとする。
【００３７】
本実施形態では、入力されたオフストロークから水平方向距離と交差長さの２つの特徴値を抽出する。オフストロークの水平方向距離特徴ｆｄは、次式により求めることができる。
【００３８】
ｆｄ＝ＤＢｘ／ａｃｓ            （１）
ここでａｃｓは平均文字サイズを示し、各ストロークの外接矩形における長い方の辺長をもとめ、全てのストロークについてその辺長をソートし、それらの辺長の中において長い方から３分の１のものに対して平均を取ることによって求めることができる。
【００３９】
またＤＢｘは、図２に示すように、注目するオフストロークの前の全ての外接矩形Ｂｂｐ＿ａｌｌと、注目するオフストロークの後の全ての外接矩形Ｂｂｓ＿ａｌｌとのＸ方向距離を示し、ＤＢｘは、次式により求めることができる。
【００４０】
ＤＢｘ＝Ｂｂｓ＿ａｌｌの左位置Ｘ座標−Ｂｂｐ＿ａｌｌの右位置Ｘ座標            （２）
また、オフストロークの交差長さ特徴ｆｉは、以下のように求める。
【００４１】
すわなち、図３に示すように、注目するオフストロークを基準として、前の全てのストローク列をＳｐ＿ａｌｌとし、後ろの全てのストローク列をＳｓ＿ａｌｌとし、Ｓｐ＿ａｌｌに属する１つのストロークをＳｐとし、Ｓｓ＿ａｌｌに属する１つのストロークをＳｓとし、ＳｐとＳｓとが交差する点をｐとし、ｐからＳｐの右側の端点までのＳｐ上の長さとｐからＳｓの左側の端点までのＳｓ上の長さの短い方をｌｎとし、Ｓｐの長さとＳｓの長さの長い方をｌｄとして、ＳｐとＳｓの交差長さｌｉを、次式により求める。
【００４２】
ｌｉ＝−ｌｎ／ｌｄ            （３）
なお、ＳｐとＳｓが交差していない場合にはｌｉ＝０とする。
【００４３】
次に、交差長さの和Ｌｓｕｍを、ＳｐとＳｓの組み合わせペアの数をｎとして、次式により求める。
【００４４】
【数１】
2010039609.tif 000003
そしてオフストロークの交差長さ特徴ｆｉを、Ｌｓｕｍ＜０の場合には、ｆｉ＝Ｌｓｕｍとし、ｆｄ（水平方向距離特徴）＞０の場合には、ｆｉ＝ｆｄとし、それ以外の場合には、ｆｉ＝０として求める。
【００４５】
図４は、水平方向距離特徴と交差長さ特徴の学習パタンの分布を示す図である。図４において、横軸は水平方向距離特徴ｆｄを示し、縦軸は交差長さ特徴ｆｉを示す。また、実線と黒点は、学習パタンにおける切出しポイント（文字パタン間のオフストローク）の特徴値の分布を示し、グレーの領域は、学習パタンにおける非切出しポイント（文字パタン内部のオフストローク）の特徴値の分布を示す。
【００４６】
本実施形態では、入力されたオフストロークから抽出した水平方向距離特徴と交差長さ特徴が０以上であり、或いはＯＡＢＣＤＥ（学習パタンにおいて切出しポイントが密集する２つの長方形を重ねた形）のエリアに位置する場合に、当該オフストロークを不確定ポイントに分類し、それ以外のオフストロークを非切出しポイントに分類する。
【００４７】
その後、全ての隣接する２つの不確定ポイントについて、２つの不確定ポイント間のストローク列の外接矩形の幅を求め、当該外接矩形の幅／ａｃｓ（平均文字サイズ）が所定の閾値より大きい場合には、当該２つの不確定ポイント間に存在する非切出しポイントの特徴値がＯＦＧＨ（学習パタンにおいて切出しポイントが存在し得る長方形）のエリアに位置する場合に、当該非切出しポイントを不確定ポイントに修正する。
【００４８】
次に、各不確定ポイント（仮切出しポイント）から、交差長さ特徴値ｆｉに加えて、１８個の特徴値と、広さ特徴値を含む２０個の特徴値を抽出する。１８個の特徴値ｆ１〜ｆ１８は、それぞれ次式（５）〜（２２）により求めることができる。
【００４９】
ｆ１＝オフストロークの経過時間                              （５）
ｆ２＝ＤＢｘ／ａｃｓ                                        （６）
ｆ３＝Ｂｂｐ＿ａｌｌとＢｂｓ＿ａｌｌの重なり面積／(ａｃｓ)２        （７）
ｆ４＝Ｄｂｘ／Ｂｂｐ１の幅                        （８）
ｆ５＝Ｄｂｘ／Ｂｂｓ１の幅                        （９）
ｆ６＝Ｄｂｘ／ａｃｓ                            （１０）
ｆ７＝Ｄｂｙ／Ｂｂｐ１の高さ                      （１１）
ｆ８＝Ｄｂｙ／Ｂｂｓ１の高さ                      （１２）
ｆ９＝Ｄｂｙ／ａｃｓ                            （１３）
ｆ１０＝Ｏｂ／(Ｂｂｓ１の幅×高さ)                （１４）
ｆ１１＝Ｏｂ／(ａｃｓ)２                        （１５）
ｆ１２＝Ｄｂｓｙ／ａｃｓ                          （１６）
ｆ１３＝Ｄｂｓ／ａｃｓ                          （１７）
ｆ１４＝Ｄｆｂ／ａｃｓ                          （１８）
ｆ１５＝オフストロークの長さ／ａｃｓ            （１９）
ｆ１６＝オフストロークの正弦値                  （２０）
ｆ１７＝オフストロークの余弦値                  （２１）
ｆ１８＝ｆ２／文字列中の最大ｆ２                （２２）
ここで、Ｂｂｐ１は、１つ前のストロークの外接矩形を示し、Ｂｂｓ１は、１つ後のストロークの外接矩形を示す。またＤＢｙは、Ｂｂp＿ａｌｌとＢｂｓ＿ａｌｌのＹ方向距離（ＤＢｙ＝Ｂｂｓ＿ａｌｌの上位置Ｙ座標−Ｂｂｐ＿ａｌｌの下位置Ｙ座標）を示す。またＤｂｘは、Ｂｂｐ１とＢｂｓ１のＸ方向距離（Ｄｂｘ＝Ｂｂｓ１の左位置Ｘ座標−Ｂｂｐ１の右位置Ｘ座標）を示す。またＤｂｙは、Ｂｂｐ１とＢｂｓ１のＹ方向距離（Ｄｂｙ＝Ｂｂｓ１の上位置Ｙ座標−Ｂｂｐ１の下位置Ｙ座標）を示す。またＯｂは、Ｂｂｐ１とＢｂｓ１の重なり面積を示す。またＤｂｓｙは、Ｂｂｐ１とＢｂｓ１の中心のＹ方向距離（Ｄｂｓｙ＝Ｂｂｓ１の中心のＹ座標−Ｂｂｐ１の中心のＹ座標）を示す。またＤｂｓは、Ｂｂｐ１とＢｂｓ１の中心の距離を示す。またＤｆｂは、Ｂｂｐ＿ａｌｌとＢｂｓ１の上位置Ｙ座標のずれ（Ｄｆｂ＝ａｂｓ（Ｂｂｐ＿ａｌｌの上位置Ｙ座標−Ｂｂｓ１の上位置Ｙ座標)）を示す。
【００５０】
また、広さ特徴値ｆｗは、次式により求めることができる。
【００５１】
ｆｗ＝ｗ／ａｃｓ            （２３）
ここで、ｗは、１つ前の仮切出しポイントから１つ後の仮切出しポイントまでのストローク列の外接矩形の幅である。
【００５２】
本実施形態では、学習パタンに対して、切出しポイントに教師信号１、非切出しポイントに教師信号−１を与えて、オフストロークから抽出した２０個の特徴値（１８個の特徴値ｆ１〜ｆ１８、交差長さ特徴値ｆｉ、広さ特徴値ｆｗ）をＳＶＭに適用し、ＳＶＭモデルを学習しておく。
【００５３】
そして、不確定ポイント（仮切出しポイント）から抽出した上記２０個の特徴値を、学習したＳＶＭに適用することで、不確定ポイントのＳＶＭ出力値を求める。ＳＶＭ出力値が所定の閾値より大きく、且つ広さ特徴値ｆｗが所定の閾値より大きい不確定ポイントを切出しポイントとして確定する。
【００５４】
２−２．候補ラティスの構築
図５に、本実施形態の候補ラティスの一例を示す。
【００５５】
本実施形態では、図５に示すように、仮切出しポイント（不確定ポイントＵＰ及び切出しポイントＤＰ）によりストローク列を切り出し、切り出されたストローク列（仮切出しユニット）毎に文字認識を行って候補文字（認識候補）を並べ、それらをリンクして複数の候補文字列からなる候補ラティスを構築する。
【００５６】
ここで不確定ポイントＵＰは、切出しポイントと非切出しポイントの２通りに仮定され、切出しポイントとして仮定される場合には、切出しユニットの抽出に利用される。例えば図５において、不確定ポイントＵＰを切出しユニットとして仮定した場合に、「明」という手書き文字パタンから２つの仮切出しユニットを抽出し、それぞれ「日、目、月」、「月、口、目、旦」という候補文字を生成する。また不確定ポイントＵＰを非切出しユニットとして仮定した場合には、「明」という手書き文字パタンから１つの仮切出しユニットを抽出して「朋、胴、明」という候補文字を生成する。なお、１つの仮切出しユニットの内部に仮切出しポイントを含まないもの、すなわち隣接する仮切出しポイントによって切り出されたユニットを最小仮切出しユニットとする。
【００５７】
候補ラティスにおいて、各ノードＮＤは文字認識によって1つの仮切出しユニットに関して生成される1つの候補文字を示し、各連結線ＡＬは1つの仮切出しポイントを文字の境として文字列の連接を示す。後述する複数項目の確からしさからなる尤度を評価するスコアは、各連結線ＡＬとノードＮＤに与えられる。本実施形態では、閾値より低い確からしさを持つノードＮＤを削除する。このようにすると、文字列候補パスの数を削減して認識処理を高速化することができる。
【００５８】
２−３．文字列認識
本実施形態では、仮切出しポイントから構築した候補ラティスの各文字列候補パス（候補文字列）について複数項目の確からしさを評価する。
【００５９】
図６（Ａ）に示すように、１つの文字列パタンＸに対して、ある切出しＳ＝Ｓ１Ｓ２．．Ｓｉ．．Ｓｎ（ｎは仮切出しユニットの数）を選択して、ある候補文字列Ｃ＝Ｃ１Ｃ２．．Ｃｉ．．Ｃｎに認識するとする。ここで仮切出しユニットＳｉはＣｉに対応している。図６（Ｂ）に示すように、仮切出しユニットＳｉは、最小仮切出しユニットの列Ｓi１Ｓi２．．Ｓｉj．．Ｓikiからなる。Ｓｉjは、１つの最小仮切出しユニットである。
【００６０】
文字列パタンＸが候補文字列Ｃに認識される条件付き確立Ｐ（Ｃ｜Ｘ）は、次式により求めることができる。
【００６１】
【数２】
2010039609.tif 000004
ここで、最小仮切出しユニットＳｉjは、外接矩形ｂｉｊ、内分割ｑｉｊと位置情報ｐｕｉｊを持ち、隣接する最小仮切出しユニットにおいて、位置関係情報pｂｉｊと仮切出しポイントｇｉｊをもつ。Ｃｉｊは、Ｓｉｊの認識候補の１つであり、文字Ｃｉの全部か一部である。ｂ，ｑ，Ｓ，ｐｕ，ｐｂ，ｇは仮切出しの特徴値の列である。
【００６２】
式（２４）において、分母Ｐ（ｂ，ｑ，Ｓ，ｐｕ，ｐｂ，ｇ）は、文字列候補パスによらない。そこで特徴値間の独立を仮定して、文字列候補パスの尤度ｆ（Ｘ，Ｃ）を、次式のように近似する。
【００６３】
【数３】
2010039609.tif 000005
ここで、Ｃ−１ｉｊとＣ−２ｉｊは、直前の２つの認識候補を示し、ｋｉは仮切出しユニットＳｉに含まれる最小仮切出しユニットの数を示し、Ｌｉｊは、切出しポイントか非切出しポイントであるかを示すラベルである。
【００６４】
Ｃｉｊが文字の一部である場合、式（２５）の第７項目（仮切出しポイントに関わる項目）以外については、求めるのが困難である。これを解決するために、Ｃｉｊをそれを含む文字Ｃｉに置き換えて、式（２５）の第１項目について、次式のように近似する。
【００６５】
【数４】
2010039609.tif 000006
ここで、λ１１とλ１２は重みパラメータを示し、λ１はバイアスを示す。
【００６６】
式（２５）の第７項目については、ラベルＬｉｊを、切出しｓｐと非切出しｎ−ｓｐの２種類に分類してその推定誤差を調節するための重みを付け、それ以外の第２〜第６項目については、式（２６）と同じ方法で近似すると、文字列候補パスの尤度ｆ（Ｘ，Ｃ）は、次式により求めることができる。
【００６７】
【数５】
2010039609.tif 000007
ここで、ｂｉ、ｑｉ、ｐｕｉは、それぞれ仮切出しユニットＳｉの外接矩形、内分割、位置情報に関する特徴ベクトルであり、ｐｂｉは、隣接する仮切出しユニット間の位置関係に関する特徴ベクトルを示し、ｇｉ１、ｇｉｊ（ｊ＝２〜ｋｉ）は、仮切出しポイントの特徴ベクトルを示す。これらの詳細については後述する。またλ１１〜λ７１、λ１２〜λ７２とλは、重みパラメータを示し、後述する遺伝的アルゴリズムを用いて学習されたものである。
【００６８】
式（２７）において、第１項目は言語文脈の確からしさ、第２項目は文字パタンサイズの確かしさ、第３項目は文字パタン内分割の確からしさ、第４項目は、文字認識の確からしさ、第５項目は単一文字パタン位置の確からしさ、第６項目はペア文字パタン位置の確からしさ、第７、第８項目（以下、第７項目という）は仮切出しポイントの確からしさを評価するための項目である。
【００６９】
本実施形態では、式（２７）に示すように、文字列候補パスの尤度は最小切出しユニットに基づいて尤度を積み上げたものであり、文字列候補の文字数に影響されない。従って、文字列を少ない文字数に解釈する傾向や、文字列を多い文字数に解釈する傾向を弱めて認識率を向上させることができる。
【００７０】
本実施形態では、式（２７）によって求めた文字列候補パスの尤度を候補ラティスの各ノードと各連結線に与え、当該候補ラティスに対してビタビ（Ｖｉｔｅｒｂｉ）探索を行うことによって、最適な候補文字列（最適な切出しと文字認識結果）を決定する。
【００７１】
以下、式（２７）の各項目の詳細について説明する。
【００７２】
第１項目のＰ（Ｃｉ｜Ｃｉ−１，Ｃｉ−２）は、Ｃｉ−１，Ｃｉ−２からＣｉへの移転的確率（ｔｒｉ−ｇｒａｍ確率）である。なお、１番目の文字Ｃ１については、ｕｎｉ−ｇｒａｍ確率Ｐ（Ｃ１）、２番目の文字Ｃ２については、ｂｉ−ｇｒａｍ確率Ｐ（Ｃ２｜Ｃ１）により求める。ｔｒｉ−ｇｒａｍ確率を学習するには膨大なテキストが必要なため、Ｐ（Ｃｉ｜Ｃｉ−１，Ｃｉ−２）の代わりに、次式に示すＰ’（Ｃｉ｜Ｃｉ−１，Ｃｉ−２）を用いる。
【００７３】
【数６】
2010039609.tif 000008
ここで、β１、β２、β３、β４は、ｔｒｉ−ｇｒａｍ確率の学習用テキストと異なるテキストによって認識率が最大になるように求める。
【００７４】
第２項目のＰ（ｂｉ｜Ｃｉ）は、文字パタンサイズの条件付き確率である。ｂｉは、平均文字サイズａｃｓで正規化した文字パタン（仮切出しユニット）の外接矩形の幅と高さからなる幾何学的な特徴ベクトルである。
【００７５】
第３項目のＰ（ｑｉ｜Ｃｉ）は、文字パタン内分割の条件付き確率である。ｑｉは、図７に示すｑｉｋ（ｋ＝１〜６）からなる幾何的特徴ベクトルである。ｑｉｋ（ｋ＝１〜３）は各垂直の分割での文字パタンの垂直方向の射影におけるギャップｄｖの長さを平均文字サイズａｃｓで正規化した値であり、ｑｉｋ（ｋ＝４〜６）は各水平の分割での文字パタンの水平方向の射影におけるギャップｄｖの長さを平均文字サイズａｃｓで正規化した値である。各分割において２つ以上のギャップがある場合、これらのギャップの和が使用される。
【００７６】
第４項目のＰ（Ｓｉ｜Ｃｉ）は、仮切出しユニットの条件付き確率である。Ｓｉは、文字パタンとしての仮切出しユニットの特徴ベクトルを示す。Ｐ（Ｓｉ｜Ｃｉ）は、文字認識のスコアから近似することができる。
【００７７】
第５項目のＰ（ｐｕｉ｜Ｃｉ）は、単一文字パタン位置の条件付き確率である。ｐｕｉは、図８（Ａ）に示すように、単一文字パタン位置（ｕｎａｒｙ位置）の２つの要素からなる幾何学的な特徴ベクトルである。２つの要素は、それぞれ文字パタンの上部から文字列の中心線ＣＬまでの距離を平均文字サイズａｃｓで正規化した値と、文字パタンの底部から文字列の中心線ＣＬまでの距離を平均文字サイズａｃｓで正規化した値である。
【００７８】
第６項目のＰ（ｐｂｉ｜Ｃｉ，Ｃｉ−１）は、ペア文字パタン位置の条件付き確率である。ｐｂｉは、図８（Ａ）に示すように、２つの隣接する文字パタン（仮切出しユニット）間におけるペア文字パタン位置（ｂｉｎａｒｙ位置）の２つの要素からなる幾何学的な特徴ベクトルである。２つの要素は、それぞれ隣接する文字パタンの上部同士の距離を平均文字サイズａｃｓで正規化した値と、隣接する文字パタンの下部同士の距離を平均文字サイズａｃｓで正規化した値である。
【００７９】
第７項目のＰ（ｇｉ１｜ｓｐ）は、切出しポイントがｇｉ１を生じる条件付き確率であり、Ｐ（ｇｉｊ｜ｎ−ｓｐ）（ｊ＝２〜ｋｉ）は、非切出しポイントがｇｉｊを生じる条件付き確率である。図８（Ｂ）に示すように、ｇｉ１は、仮切出しユニットＳｉの先頭に位置し、切出しポイントとして識別される仮切出しポイント（隣接する文字パタン間の仮切出しポイント）から抽出した２０次元の幾何学的な特徴ベクトル（２０個の特徴値）であり、ｇｉｊ（ｊ＝２〜ｋｉ）は、仮切出しユニットＳｉの内部に位置し、非切出しポイントして識別される仮切出しポイント（文字パタン内部の仮切出しポイント）から抽出した２０次元の幾何学的な特徴ベクトルである。
【００８０】
このように本実施形態では、切出しポイントして識別される仮切出しポイントのみならず、非切出しポイントして識別される仮切出しポイントについても、非切出しポイントとして識別される確からしさを評価することで、文字列を少ない文字数に解釈する傾向や、文字列を多い文字数に解釈する傾向を弱めて認識率を向上させることができる。
【００８１】
なお本実施形態では、Ｐ（ｇｉ１｜ｓｐ）を、Ｐ（ｏｉ１＝ＳＶＭ（ｇｉ１）｜ｓｐ）により近似し、Ｐ（ｇｉｊ｜ｎ−ｓｐ）（ｊ＝２〜ｋｉ）を、Ｐ（ｏｉｊ＝ＳＶＭ（ｇｉｊ）｜ｎ−ｓｐ）により近似する。ここでは、ｏｉｊはｇｉｊに関するＳＶＭ出力値である。Ｐ（ｏｉ１｜ｓｐ）は切出しポイントに対して、学習パタンで学習したＳＶＭが出力値ｏｉ１を生じる条件付き確率である。Ｐ（ｏｉｊ｜ｎ−ｓｐ）（ｊ＝２〜ｋｉ）は非切出しポイントに対して、学習パタンで学習したＳＶＭが出力値ｏｉｊを生じる条件付き確率である。なお、Ｐ（ｏ１１｜ｓｐ）＝１とする。
【００８２】
以下、説明を簡略化するためにｏｉｊの代わりに符号ｏｉを使用する。図９（Ａ）に示すようにＳＶＭの出力値ｏｉについて、学習パタンからＰ（ｏｉ｜ｓｐ）とＰ（ｏｉ｜ｎ−ｓｐ）を学習することができる。ここで、ＳＶＭの出力値が１か−１に近づくと確率値が激しく降下する。そこで、Ｐ（ｏｉ｜ｓｐ）とP（ｏｉ｜ｎ−ｓｐ）の代わりに、次式に示す累積の関数Ｐ’（ｏｉ｜ｓｐ）とＰ’（ｏｉ｜ｎ−ｓｐ）を使用する。
【００８３】
【数７】
2010039609.tif 000009
図９（Ｂ）に、Ｐ’（ｏｉ｜ｓｐ）とＰ’（ｏｉ｜ｎ−ｓｐ）の確率値を示す。さらに、次式に示すシグモンド関数によってこれらを近似することができる。
【００８４】
【数８】
2010039609.tif 000010
図９（ｂ）に示すＳＶＭの出力値に対して、−１０から１０まで０．０２の間隔でＳＶＭの出力値ｏｋ（ｋ＝１〜Ｎｓ）を取り、確率Ｐ’（ｏｉ｜ｓｐ）とＰ’（ｏｉ｜ｎ−ｓｐ）を得る。ここで、ＮｓはＳＶＭ出力値を取る個数である。そして、最急降下法により次式に示すエラー関数の最小化の尺度に基づいてパラメータα１０，α１１，α２０，α２１を求める。
【００８５】
【数９】
2010039609.tif 000011
２−４．重みパラメータの学習
本実施形態では、学習パタンを利用して遺伝的アルゴリズムにより、式（２７）における複数の重みパラメータ（λ１１〜λ７１、λ１２〜λ７２、λ）を学習する。ここでは、複数の重みパラメータからなる重み系列を１つの染色体とみなす。１つの重みパラメータは染色体の１つの遺伝子である。以下、学習の処理手順について説明する。
【００８６】
まず、Ｎ個の染色体をランダムで０〜１の値に初期化する。Ｎ個の染色体の古い平均評価値ｆｏｌｄを０、繰返し数ｔを１に初期化する。
【００８７】
次に、Ｎ個の染色体の中からランダムで選択した２つの染色体について、ランダムで決定した２位置の中の遺伝子を交叉させることで新しい２つの染色体を生成する。これをＭ個の新染色体が生成されるまで繰り返す。
【００８８】
次に、Ｎ＋Ｍ個の染色体の各遺伝子に確率Ｐｍｕｔで突然変異を起こさせる。具体的には−１〜１のランダム値を加算し、［０，１］に丸める。
【００８９】
次に、各染色体を学習パタンに関する認識率により評価する。ここでは、各染色体の遺伝子は式（２７）における重みに設定される。
【００９０】
次に、各染色体の評価値によりそのルーレット確率を求める。ここでは、評価値が高い染色体ほどルーレット確率が大きくなるようにする。そして、評価値が最高の２つの染色体を選択し、Ｎ個の新染色体を得るまでルーレット確率により染色体を選択する。Ｎ個の新染色体でＮ個の古い染色体を置換する。
【００９１】
次に、Ｎ個の新染色体の平均評価値ｆｎｅｗを求める。もし(ｆｎｅｗ−ｆｏｌｄ＜閾値)がｎｓｔｏｐ回以上発生するかそれともｔ＞Ｔであれば、評価値が最高の染色体を返す。それ以外の場合には、ｆｎｅｗをｆｏｌｄに、ｔをｔ＋１に置換し、前記交叉の処理に戻る。ここでは、Ｎを５０に、Ｍを１００に、Ｐｍｕｔを０．０３に、ｎｓｔｏｐを２５に、Ｔを１００００にセットする。
【００９２】
染色体を評価するために学習パタンに対して手書き文字認識（単文字認識）を適用し、候補ラティスを生成し、そこでＶｉｔｅｒｂｉ探索を行う必要がある。仮切出しと単文字認識は1回だけで済むが、Ｖｉｔｅｒｂｉ探索は重み系列（染色体）ごとに行う必要があるが、多大な処理時間を要することになる。そこで、まず各重みを１にセットし、学習パタンの各文字列からＶｉｔｅｒｂｉ探索を用いて上位１００個の文字列候補パスを選択する。
【００９３】
そして遺伝的アルゴリズムにより重み系列を発生し、これらの選択した文字列候補パスに発生した重み系列を適用して評価を行うことで、可能性の高い重みを選択する。収束したら、学習した新しい重み系列を適用して、学習パタンの各文字列からＶｉｔｅｒｂｉ探索を用いて上位１００個の文字列候補パスを選択する。遺伝的アルゴリズムにより重み系列を学習する。このプロセスをもう1度繰り返す。このようにすることで、重み系列の組み合わせを１つずつ試すことなく、効率よく最適な重みの組み合わせを求めることができる。
【００９４】
３．性能評価結果
性能評価に先立って、データベースを利用してＰ（Ｓｉ｜Ｃｉ）について文字認識のモデルを学習した。またデータベースを利用して文字パタンサイズ、文字パタン内分割、単一文字パタン位置（ｕｎａｒｙ位置特徴）とペア文字パタン位置（ｂｉｎａｒｙ位置特徴）における４つの二次識別関数（ＱＤＦ）を学習した。また新聞データにより言語文脈の確からしさのためのｔｒｉ−ｇｒａｍ表を作った。そして、データベースによりβ１、β２、β３、β４を学習した。
【００９５】
さらに、１００人分の文字列方向と文字方向自由のオンライン日本語手書き文字列データベースから１行ずつの左から右への文字列を抽出した。このうち７５人分のデータから２０次元の仮切出し特徴値を抽出し、これらのデータを利用することで、仮切出しのための閾値、仮切出しポイント確かさしさのためのＳＶＭモデルと式（２７）における重みパラメータを学習した。そして、残った２５人分の文字列データをテストパタンとして本実施形態の方法（式（２７）に示す文字列候補パス評価方法）の性能を評価した。
【００９６】
なお比較対象として、式（３２）、式（３３）に示す文字列候補パス評価方法（方法１、方法２）についても評価した。
【００９７】
【数１０】
2010039609.tif 000012
【００９８】
【数１１】
2010039609.tif 000013
ここで、式（３２）、式（３３）におけるλｉ（ｉ＝１〜７）とλは、本実施形態と同様の重みパラメータであり、遺伝的アルゴリズムにより学習されたものである。式（３２）に示すように、方法１では、最小仮切出しユニットではなく仮切出しユニットに基づいて尤度を積み上げたもので、文字列候補の文字数に影響され、文字列を少ない文字数に解釈する傾向がある。つまり、そこでは、学習した重みパラメータをそのまま各項目に与えており、本実施形態のように、最小切出しユニットに基づいて尤度を積み上げていない。また式（３３）に示すように、方法２では、文字列候補の文字数によって文字列候補パスの尤度を正規化するため、文字列を多い文字数に解釈する傾向がある。また方法１、方法２では、非切出しポイントして識別される確からしさを評価していない。
【００９９】
図１０に、本実施形態の方法、方法１、方法２それぞれの性能評価結果を示す。
【０１００】
なお、図１０に示すｆは、次式に示す文字切出し性能のｆ尺度である。
【０１０１】
【数１２】
2010039609.tif 000014
図１０に示すように、本実施形態の方法では、方法１、方法２に比べて、文字切出し性能と文字認識率が向上していることが確認できる。文字認識率の差は１％程度であるが、９０％を越えた文字認識率をさらに１％向上させることは容易なことではない。
【０１０２】
４．本実施形態の処理
図１１は、本実施形態の文字列認識装置の処理の一例を示すフローチャートである。
【０１０３】
まず、筆点情報取得部１１０は、文字入力部１６０からストロークのデータ（筆点座標系列）を取得する（ステップＳ１０）。
【０１０４】
次に、仮切出しポイント決定部１１２は、各オフストロークから抽出した水平方向距離と交差長さの特徴値に基づいて、不確定ポイント（仮切出しポイント）を決定する（ステップＳ１２）。次に、各オフストロークから抽出した２０個の特徴値を学習したＳＶＭに適用して仮切出しポイントのＳＶＭ出力値を求める（ステップＳ１４）。次に、仮切出しポイントのＳＶＭ出力値に基づき切出しポイントを確定する（ステップＳ１６）。
【０１０５】
次に、候補文字列生成部１１４は、仮切出しポイント（不確定ポイント、切出しポイント）によって切出された仮切出しユニット毎に文字認識を行い、候補ラティスを生成する（ステップＳ１８）。
【０１０６】
次に、認識部１１６は、候補ラティスの各文字列候補パス（候補文字列）について、それぞれ重み付けされた複数項目の確からしさを考慮した尤度を求める（ステップＳ２０）。次に、候補ラティスに対してＶｉｔｅｒｂｉ探索を行って、最適な文字列候補パスを選択する認識処理を行う（ステップＳ２２）。
【０１０７】
なお、本発明は、上述の実施の形態に限定されるものではなく、種々の変形が可能である。本発明は、実施の形態で説明した構成と実質的に同一の構成（例えば、機能、方法及び結果が同一の構成、あるいは目的及び効果が同一の構成）を含む。また、本発明は、実施の形態で説明した構成の本質的でない部分を置き換えた構成を含む。また、本発明は、実施の形態で説明した構成と同一の作用効果を奏する構成又は同一の目的を達成することができる構成を含む。また、本発明は、実施の形態で説明した構成に公知技術を付加した構成を含む。
【図面の簡単な説明】
【０１０８】
【図１】本実施形態の文字列認識装置の機能ブロック図の一例。
【図２】本実施形態の手法について説明するための図。
【図３】本実施形態の手法について説明するための図。
【図４】本実施形態の手法について説明するための図。
【図５】本実施形態の手法について説明するための図。
【図６】本実施形態の手法について説明するための図。
【図７】本実施形態の手法について説明するための図。
【図８】本実施形態の手法について説明するための図。
【図９】本実施形態の手法について説明するための図。
【図１０】性能評価結果を示す図。
【図１１】本実施形態の文字列認識装置の処理の流れを示すフローチャート図。
【符号の説明】
【０１０９】
１００  処理部、１１０  筆点情報取得部、１１２  仮切出しポイント決定部、１１４  候補文字列生成部、１１６  認識部、１２０  表示処理部、１６０  文字入力部、１７０  記憶部、１８０  情報記憶媒体、１９０  表示部、１９６  通信部
【図１】
2010039609.tif 000015
【図２】
2010039609.tif 000016
【図３】
2010039609.tif 000017
【図５】
2010039609.tif 000018
【図６】
2010039609.tif 000019
【図７】
2010039609.tif 000020
【図８】
2010039609.tif 000021
【図９】
2010039609.tif 000022
【図１０】
2010039609.tif 000023
【図１１】
2010039609.tif 000024
【図４】
2010039609.tif 000025