(57)【要約】【課題】文字の接触パターンを精度よく判定すること。【解決手段】文字認識装置（コンピュータ）１は、比較手段２および判定手段３として機能する。比較手段２は、一文字であると判定された判定対象パターンの構造を、記憶部４に記憶された一文字パターンの構造と比較する。判定手段３は、比較手段２の比較結果に加え、サイズ情報（パターンの高さに対する幅の比）を用いて、判定対象パターンを一文字であるか否かを判定する。【選択図】図１
2010198308.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
一文字であると判定された判定対象パターンの構造を、記憶部に記憶された一文字パターンの構造と比較する比較手順、
前記比較手順の比較結果に基づいて、前記判定対象パターンが複数の文字を含むパターンか否かを判定する判定手順、
を実行させることを特徴とする文字認識プログラム。
【請求項２】
前記比較手順は、前記判定対象パターンの構造に一致する前記一文字パターンの割合を類似度として算出し、
前記判定手順は、前記類似度がある閾値以下の前記判定対象パターンを複数の文字を含むパターンであると判定することを特徴とする請求項１記載の文字認識プログラム。
【請求項３】
前記比較手順は、前記一文字パターンから作成したグラフの頂点の隣接関係を、前記判定対象パターンから作成したグラフの頂点の隣接関係に対応付けることにより、前記類似度を算出することを特徴とする請求項２記載の文字認識プログラム。
【請求項４】
前記比較手順は、前記判定対象パターンから作成したグラフの頂点間の辺の長さの合計値に対する、前記判定対象パターンから作成したグラフにおける前記一文字パターンから作成したグラフに一致した頂点間の辺の長さの合計値の割合を、前記類似度として算出することを特徴とする請求項２記載の文字認識プログラム。
【請求項５】
前記コンピュータに、さらに、前記判定対象パターンの縦横比を求めるサイズ計算手順を実行させ、
前記判定手順は、前記判定対象パターンの高さに対する幅の比と比較手段の比較結果とに基づいて、前記判定対象パターンが他の文字と接触しているか否かを判定することを特徴とする請求項１記載の文字認識プログラム。
【請求項６】
コンピュータが、
一文字であると判定された判定対象パターンの構造を、記憶部に記憶された複数の一文字パターンの構造と比較し、
比較結果に基づいて、前記判定対象パターンが複数の文字を含むパターンか否かを判定する、
ことを特徴とする文字認識方法。
【請求項７】
一文字であると判定された判定対象パターンの構造を、記憶部に記憶された複数の一文字パターンの構造と比較する比較部と、
前記比較部の比較結果に基づいて、前記判定対象パターンが複数の文字を含むパターンか否かを判定する判定部と、
を有することを特徴とする文字認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は文字認識プログラム、文字認識方法および文字認識装置に関する。
【背景技術】
【０００２】
手書き文字や印字された文字を光学的に読み取り、予め記憶されたパターンと照合することにより、読み取った文字を特定させるＯＣＲ（Optical Character Reader）機能が知られている。
【０００３】
読み取り対象となる文字列には、他の文字と接触している接触文字と、一文字である孤立文字とが混在している場合がある。
一般的なＯＣＲ機能は、認識の効率を向上させるためや、文字の切り出し候補の増大による切り出し誤りの発生を回避するために、他の文字と接触している可能性のある接触パターンと一文字である可能性の高い孤立文字パターンとを判定する機能を所持する。
【０００４】
孤立文字パターンと判定された候補（孤立文字パターン候補）に対しては、そのまま一文字認識が実行される。
一方、接触パターンと判定された候補（接触パターン候補）に対しては、セグメンテーション（切り出しおよび認識）が行われる。
【０００５】
接触パターン候補を判定する方法としては、例えば、判定対象とするパターンの文字列方向の長さが閾値以上のものを接触パターン候補と判定する方法や、パターンの幅をＷ、高さをＨ、定数をＫとしたときＷ／Ｈ＞Ｋ（横書きの場合）の場合を接触パターン候補と判定する方法等が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平３−３７７８２号公報
【特許文献２】特開平８−１６７２０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前述した方法は、接触パターンは孤立文字パターンと比較して文字列方向の長さが一般的に大きくなっているという性質を利用している。
しかしながら、接触パターンであっても文字列方向の長さや、パターンの縦横比（Ｗ／Ｈ）では孤立文字パターンと区別できないケースが存在し、接触パターン候補の判定漏れを起こして文字認識誤りの一因となっている。
【０００８】
これらの判定漏れに対して閾値を下げれば、ある程度、接触パターン候補であるとの判定が可能であるが、接触パターン候補の数がその分増加する。このため、切り出す文字の数が増大して誤ったセグメンテーション結果を選択してしまう場合がある。
【０００９】
本発明はこのような点に鑑みてなされたものであり、文字の接触パターンを精度よく判定する文字認識プログラム、文字認識方法および文字認識装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、文字認識プログラムが提供される。この文字認識プログラムは、コンピュータに、比較手順および判定手順を実行させる。
比較手順は、一文字であると判定された判定対象パターンの構造を、記憶部に記憶された一文字パターンの構造と比較する。
【００１１】
判定手順は、比較手順の比較結果に基づいて、判定対象パターンが複数の文字を含むパターンか否かを判定する。
このような文字認識プログラムによれば、比較手順により、一文字であると判定された判定対象パターンの構造が、記憶部に記憶された一文字パターンの構造と比較される。判定手順により、比較手順の比較結果に基づいて、判定対象パターンが複数の文字を含むパターンか否かが判定される。
【発明の効果】
【００１２】
開示の文字認識プログラムによれば、文字の接触パターンを精度よく判定することができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態の文字認識装置の概要を示す図である。
【図２】文字認識装置のハードウェア構成例を示す図である。
【図３】文字認識装置の機能を示すブロック図である。
【図４】文字認識辞書のデータ構成を示す図である。
【図５】変形モデルグラフのデータ構成を示す図である。
【図６】変形モデルグラフ生成部の構成を示す図である。
【図７】グラフの整形を説明する図である。
【図８】変形モデルグラフ表示部の処理を説明する図である。
【図９】接触パターン候補判定部の構成を示す図である。
【図１０】接触パターン候補判定処理を示すフローチャートである。
【図１１】マッチングを実行したときの例を示す図である。
【図１２】最大マッチング度を説明する図である。
【図１３】グラフの各辺の長さを示す図である。
【図１４】変形モデルグラフのマッチング度を示す図である。
【図１５】変形モデルグラフのマッチング度を示す図である。
【発明を実施するための形態】
【００１４】
以下、実施の形態を、図面を参照して詳細に説明する。
まず、実施の形態の文字認識装置について説明し、その後、実施の形態をより具体的に説明する。
【００１５】
図１は、実施の形態の文字認識装置の概要を示す図である。
文字認識装置（コンピュータ）１は、比較手段２および判定手段３として機能する。
比較手段２は、一文字であると判定された判定対象パターンの構造を、記憶部４に記憶された一文字パターンの構造と比較する。この一文字パターンの構造は、判定対象パターンが一文字である場合にその文字を識別するために予め用意されたパターンの構造である。また、記憶部４は、文字認識装置１内に設けられていてもよいし、文字認識装置１の外部に設けられていてもよい。
【００１６】
図１では、例えば、一文字枠が印刷されていない枠なし領域に自由に記入された、手書き数字「６」に数字「２」が接触した判定対象パターン５が図示されている。
この判定対象パターン５は、数字「６」に数字「２」が接触したパターンであるにもかかわらず、一文字であると判定されたパターンである。この判定対象パターン５が、後述するルールにより整形され、頂点と辺とを有する構造６になっている。
【００１７】
図１では、記憶部４には、数字が「６」であることを識別する三つ（複数）の一文字パターンの構造４ａ、４ｂ、４ｃが記憶されている。
比較手段２は、構造６を、一文字パターンの構造４ａ、４ｂ、４ｃとそれぞれ比較する。例えば、構造６が、構造４ａ、４ｂ、４ｃと同型部分を含むか否かを比較する。
【００１８】
図１では、構造６が、構造４ｂと同型部分を含んでいるか否かを比較している。そして、構造６に一致する構造４ｂの割合を類似度として算出する。
判定手段３は、比較手段２の比較結果に基づいて、判定対象パターンを一文字であるか否かを判定する。
【００１９】
図１では、比較手段２の比較結果である類似度「０．６７」に加え、サイズ情報（パターンの高さに対する幅の比）を用いて判定対象パターン５が一文字であるか否かを判定する。例えば、類似度「０．６７」が予め定められた閾値以上であり、かつ、前述した比が
予め定められた閾値以上である場合に、判定対象パターン５が一文字であると判定する。一方、そうでなければ、接触パターンであると判定する。
【００２０】
図１では、判定対象パターン５が接触パターンであると判定されている。
このような文字認識装置１によれば、構造を比較することで、文字の接触パターンを精度よく判定することができる。
【００２１】
以下、実施の形態をより具体的に説明する。
図２は、文字認識装置のハードウェア構成例を示す図である。
文字認識装置１０は、ＣＰＵ（Central Processing Unit）１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０９を介してＲＡＭ（Random Access Memory）１０２、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、１０６、外部補助記憶装置１０７、および通信インタフェース１０８が接続されている。
【００２２】
ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。ＨＤＤ１０３には、ＯＳやアプリケーションプログラムが格納される。また、ＨＤＤ１０３内には、プログラムファイルが格納される。
【００２３】
グラフィック処理装置１０４には、モニタ１０４ａが接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１０４ａの画面に表示させる。入力インタフェース１０５には、キーボード１０５ａとマウス１０５ｂとが接続されている。入力インタフェース１０５は、キーボード１０５ａやマウス１０５ｂから送られてくる信号を、バス１０９を介してＣＰＵ１０１に送信する。
【００２４】
入力インタフェース１０６は、イメージスキャナ１０６ａに接続されている。入力インタフェース１０６は、イメージスキャナ１０６ａから送られてくる信号（例えば帳票画像を電子データに変換した画像信号）を、バス１０９を介してＣＰＵ１０１に送信する。
【００２５】
外部補助記憶装置１０７は、記録媒体に書き込まれた情報を読み取ったり、記録媒体に情報を書き込んだりする。外部補助記憶装置１０７で読み書きが可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等が挙げられる。磁気記録装置としては、例えば、ＨＤＤ、フレキシブルディスク（ＦＤ）、磁気テープ等が挙げられる。光ディスクとしては、例えば、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等が挙げられる。光磁気記録媒体としては、例えば、ＭＯ（Magneto-Optical disk）等が挙げられる。
【００２６】
通信インタフェース１０８は、ネットワーク３０に接続されている。通信インタフェース１０８は、ネットワーク３０を介して、他のコンピュータとの間でデータの送受信を行う。
【００２７】
以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。このようなハードウェア構成の文字認識装置１０内には、以下のような機能が設けられる。
【００２８】
図３は、文字認識装置の機能を示すブロック図である。
文字認識装置１０は、２値化部１１と、行切り出し部１２と、ラベリング部１３と、文字認識用辞書格納部１４と、文字認識部１５と、変形モデルグラフ生成部１６と、変形モデルグラフ格納部１７と、接触パターン候補判定部１８と、接触パターンセグメンテーション部１９と、出力部２０とを有している。
【００２９】
２値化部１１は、イメージスキャナ１０６ａが帳票画像を電子データに変換した画像を２値化する。
行切り出し部１２は、２値化部１１によって２値化された帳票画像から文字の行（文字行）を切り出す。以下、切り出された文字行に含まれる文字のパターンを「判定対象パターン」と言う。
【００３０】
ラベリング部１３は、判定対象パターン内の異なる連結成分をラベル（番号）付けする。このとき、必要があれば、連結成分の外接矩形の重なりを調べてラベルを統合する。
文字認識用辞書格納部１４は、文字認識に使用する文字認識用辞書を格納している。
【００３１】
文字認識部１５は、文字認識用辞書格納部１４に格納されている文字認識用辞書を読み込み、各ラベルに対応する判定対象パターンに対して文字認識を実行する。
変形モデルグラフ生成部１６は、接触パターン候補判定に使用する文字種毎の変形モデルグラフを生成し、変形モデルグラフ格納部１７に格納する。なお、変形モデルグラフおよびその生成方法については、後に詳述する。
【００３２】
接触パターン候補判定部１８は、文字認識部１５が実行した文字認識により得られた判定対象パターンの文字認識結果に対し、変形モデルグラフ格納部１７に格納されている変形モデルグラフを使用して、判定対象パターンが接触パターン候補か否かを判定する。
【００３３】
接触パターンセグメンテーション部１９は、接触パターン候補と判定された判定対象パターンに対しては接触箇所を判定して切り出し・認識結果を求める。
出力部２０は、判定対象パターンの文字認識結果をモニタ１０４ａに出力する。
【００３４】
次に、文字認識用辞書格納部１４に格納されている文字認識辞書のデータ構成を説明する。
図４は、文字認識辞書のデータ構成を示す図である。
【００３５】
データがテーブル化されて格納されている。
データテーブル１４ａは、文字種毎に、変形モデルグラフの数が設定されている。そして、変形モデルグラフ毎に、変形モデルグラフを識別する番号が付されており、変形モデルグラフ毎に、モデルの頂点数、モデルの辺数、モデルの頂点隣接行列、モデルの頂点と辺の接続行列が設定されている。
【００３６】
ここで、モデルの頂点隣接行列は、頂点間の隣接関係を「１」と「０」で表す行列であり、例えば、頂点数が「ｎ」のときｎ行ｎ列の行列である。
また、モデルの頂点と辺の接続行列は、頂点と辺の接続関係を「０」と「１」で表す行列であり、例えば、頂点数が「ｎ」で辺数が「ｍ」のとき、ｎ行ｍ列の行列である。
【００３７】
次に、変形モデルグラフ格納部１７に格納されている変形モデルグラフのデータ構成を説明する。
図５は、変形モデルグラフのデータ構成を示す図である。
【００３８】
データテーブル１７ａは、文字種毎に、テンプレート（辞書）の数を示すテンプレート数が設定されている。そして、テンプレート毎に、ベクトルの成分を識別する情報が設定されている。
【００３９】
次に、変形モデルグラフ生成部１６の構成を詳しく説明する。
図６は、変形モデルグラフ生成部の構成を示す図である。
変形モデルグラフ生成部１６は、文字種指定受付部１６１と、データ読込部１６２と、文字線幅推定部１６３と、細線化部１６４と、グラフ化部１６５と、グラフ整形部１６６と、変形モデルグラフ生成・登録部１６７と、変形モデルグラフ表示部１６８と、削除指定受付部１６９と、不正変形モデルグラフ削除部１７０とを有している。
【００４０】
文字種指定受付部１６１は、変形モデルグラフを作成したい文字種の、ユーザによる指定（入力）を受け付ける。
データ読込部１６２は、文字種指定受付部１６１が受け付けた文字種の２値の学習用の一文字画像データを、例えば、予め用意されたデータベースから読み込む。以下、一文字画像データに含まれる文字のパターンを「一文字パターン」と言う。
【００４１】
文字線幅推定部１６３は、一文字パターンの文字線の幅を推定する。
細線化部１６４は、一文字パターンを細線化する。
グラフ化部１６５は、細線化部１６４が細線化した一文字パターンに対し、頂点と、頂点間の辺とを抽出する。そして抽出した辺および頂点の、接続関係および隣接関係を求めることで一文字パターンをグラフ化する。
【００４２】
グラフ整形部１６６は、各文字種の変形モデルグラフ数の増大とそれによるマッチング回数の増大を防ぐため、グラフ化部１６５によってグラフ化されたグラフを一定のルールで整形する。
【００４３】
変形モデルグラフ生成・登録部１６７は、一つ目の一文字パターンに対応するグラフを無条件に変形モデルグラフとして登録し、二つ目以降の一文字パターンに対応するグラフについては、登録済みの変形モデルグラフの全てとのマッチングを行う。そして、マッチング条件に合わない場合は、異なる変形であるとして新たな変形モデルグラフとして登録する。なお、この処理については、後に詳述する。
【００４４】
変形モデルグラフ表示部１６８は、指定文字種の変形モデルグラフとして登録された全変形モデルグラフ図と各変形モデルグラフ図の近傍に削除用チェックボックスを表示する。
【００４５】
削除指定受付部１６９は、マウス１０５ｂ等を使ったユーザによるチェックボックスへのチェックによって指定される削除情報を受け付ける。
不正変形モデルグラフ削除部１７０は、削除指定受付部１６９が受け付けた削除情報に基づいて、削除指定された変形モデルグラフに対応するデータを登録された変形モデルグラフデータから削除する。また、残っている変形モデルグラフのモデル番号を修正する。
【００４６】
次に、変形モデルグラフ生成部１６の処理について詳しく説明する。
＜グラフ化部＞
グラフ化部１６５は、細線化部１６４で得られた細線化された一文字パターンを、グラフで表現する。具体的には、まず、細線化された一文字パターンから頂点座標と次数を求める。次に、頂点間の辺を追跡し、辺の各点の座標、辺の長さ、接続する頂点番号を求める。また、各頂点に接続する辺の番号を求める。
【００４７】
これらの辺と頂点情報を使って、頂点隣接行列を計算する。隣接行列は、頂点数×頂点数の行列であり、頂点間が辺で結ばれていれば「１」、結ばれていなければ「０」の値を持つ。これらは、グラフ理論の一般的な定義に等しい。
【００４８】
グラフ化部１６５は、具体的に以下のようなデータを計算し、得られたデータをそれぞれに用意されている構造体に格納する。
（１）グラフ情報
グラフを構成する辺・頂点の数、頂点隣接行列、辺と頂点の接続行列を計算し、グラフ情報構造体に格納する。
（２）辺情報
各辺の、長さ、接続する２頂点の番号、辺の軌跡の座標を計算し、辺情報構造体に格納する。
（３）頂点情報
各頂点の、座標、次数、接続する辺の番号を計算し、頂点情報構造体に格納する。
【００４９】
この構造体は、例えば、次のような構造でもよい。
＜辺情報構造体＞
struct Edge＿inf｛
short *vertexNo;     接続する頂点番号配列
short *xcood;        辺の各点（軌跡）のｘ座標配列ポインタ
short *ycood;        辺の各点（軌跡）のｙ座標配列ポインタ
short length;        辺の長さ
short vn1, vn2;      辺に接続する２頂点の番号
｝;
＜頂点情報構造体＞
struct Vertex＿inf｛
short x, y;          頂点座標のｘ、ｙ座標
short degree;        頂点の次数
short *edgeNo;       接続する辺番号配列ポインタ
short counter;       辺追跡時のカウンタ
｝;
＜グラフ情報構造体＞
struct Graph＿inf｛
struct Edge＿inf     *edge;       辺情報構造体ポインタ
short               edgeNo;       辺の数
struct Vertex＿inf   *vertex;     頂点情報構造体ポインタ
short              vertexNo;      頂点数
short              *smatrix;      接続行列ポインタ
short              *bmatrix;      隣接行列ポインタ
｝;
＜グラフ整形部＞
グラフ整形部１６６は、一文字パターンから得られたグラフを整形する。
【００５０】
グラフの整形は、Vilatov, Gitis, and Kil, “Graph-based Handwritten Digit String Recognition”(1995), Proc. of ICDAR, pp. 845-848の5.1に記述されているグラフ変形の手法を参考にしている。グラフのループに次数２の頂点を追加する部分が、上記文献の手法とは異なる。
【００５１】
整形のルールは以下の通りである。
図７は、グラフの整形を説明する図である。
グラフ整形部１６６は、グラフ化部１６５が求めた辺・頂点の構造体を削除・分割・追加する処理を行い、隣接行列・接続行列を再計算する。
【００５２】
具体的には、まず、図７（ａ）に示すように、細線化部１６４が施した処理の結果、文字線の凹凸により一文字パターンのグラフに突起（ヒゲ）が生じることがあるため、この突起を削除する必要がある。
【００５３】
具体的には、一文字パターンのグラフから、一定長さ以下の辺で、次数（degree）が「１」の頂点（端点）に接続する辺を全て削除する。ここでは、予め計算しておいた文字線幅程度とする。
【００５４】
図７（ｂ）に示す例では、辺ｅ３が削除対象に該当する、この辺ｅ３は、次数が「３」の頂点ｖ２と次数が「１」の頂点ｖ３とに接続している。
この場合、次数が「１」の頂点ｖ３を削除する。頂点ｖ３を削除した後、次数が「１」でない方の頂点の次数を「１」減らす。すなわち、図７（ｃ）に示すように、辺ｅ３に対応する辺情報構造体を除き、頂点ｖ２に対応する頂点情報構造体のメンバーの次数を「３」から「２」にする。更に、接続する辺番号配列から削除した辺番号を除く。これは、接続する辺の数が減るためである。
【００５５】
次に、一文字パターンのグラフから、前述の処理で発生した次数が「２」の頂点を全て除く。
図７（ｄ）に示す例では、頂点ｖ２を除き、辺ｅ２と辺ｅ４とを統合し辺ｅ２とする。すなわち、頂点ｖ２に対応する頂点情報構造体構造体を除き、辺ｅ２と辺ｅ４の辺情報構造体を統合して一つにする。
【００５６】
次に、２頂点に接続する辺が必ず一つとなるよう、ループの部分に次数が「２」の頂点を２個任意の位置に追加する。よって、ループの部分の辺は三つに分割される。
図７（ｅ）に示す例では、ループに次数が「２」の頂点ｖ２、ｖ３を付加し、辺ｅ１を辺ｅ１ａ、ｅ３、ｅ４に分割する。すなわち、頂点ｖ２、ｖ３に対応する頂点情報構造体を作成し、その位置座標を辺ｅ１の辺情報構造体の辺の各点の任意の２点とする。これによって、辺ｅ１に対応する辺情報構造体を三つに分割し、辺ｅ１ａ、ｅ３、ｅ４に対応する辺情報構造体を作成する。
【００５７】
最後に、得られた辺情報構造体、頂点情報構造体から、隣接行列、接続行列を再計算する。
次に、変形モデルグラフ生成・登録部１６７の処理を詳しく説明する。
【００５８】
＜変形モデルグラフ生成・登録部＞
変形モデルグラフ生成・登録部１６７は、整形されたグラフの最初（１番目）の作成対象パターンにおいては、無条件に、その文字種の変形モデルグラフとして登録し、対象文字種の変形モデルグラフの数を「１」とする。
【００５９】
２番目以降の作成対象パターンは、グラフ整形までは１番目の作成対象パターンと同様の処理を行う。ただし、変形モデルグラフ生成・登録部１６７では登録済みの変形モデルグラフと、２番目以降の作成対象パターンのグラフとの同型判定を行い、同型でないものを新たな変形モデルグラフとして登録し、変形モデルグラフ数を「１」増加させる。なお、同型とは、変形モデルグラフと作成対象パターンのグラフとが完全に一致する場合である。
【００６０】
＜変形モデルグラフ表示部＞
図８は、変形モデルグラフ表示部の処理を説明する図である。
全ての作成対象パターンに対する処理が終了し、変形モデルグラフ生成・登録が終了した後、変形モデルグラフ表示部１６８は、図８に示すように、指定された文字種（図８では「６」）の変形モデルグラフとして登録された全変形モデルグラフの図と、削除用チェックボックスを表示する。
【００６１】
これは、汚れ等のノイズを有するパターンが学習用の作成対象パターンに混在している場合や、他の文字種のパターンが誤って混在している場合等は、不正な変形モデルグラフが生成されるため、これを除く必要があるからである。
【００６２】
前述したように、削除指定受付部１６９は、ユーザのマウス１０５ｂ等の操作により、不正な変形モデルグラフの削除用チェックボックスへのチェックを受け付けると、その変形モデルグラフを削除対象に指定する。
【００６３】
不正変形モデルグラフ削除部１７０は、削除対象に指定された変形モデルグラフに対応するデータを、変形モデルグラフ生成・登録部１６７が登録した変形モデルグラフから削除し、同時に残っている変形モデルグラフのモデル番号を修正する。
【００６４】
図８では、変形モデルグラフ生成・登録部１６７が、文字種「６」について四つの変形モデルグラフを生成した場合を図示している。
図８において左から三つ目の変形モデルグラフは、文字種の異なる一文字画像が誤って混在してしまったものであり、また、左から四つ目の変形モデルグラフは、ノイズがのったパターンから生成された変形モデルグラフである。
【００６５】
ユーザの操作により、三つ目、四つ目の変形モデルグラフのチェックボックスへのチェックを受け付けると、変形モデルグラフ生成・登録部１６７が登録した変形モデルグラフから対応する変形モデルグラフが削除される。この結果、一つ目、二つ目の変形モデルグラフが、文字種「６」の変形モデルグラフとして決定される。なお、図１に示す一文字パターンの構造４ａ、４ｂ、４ｃは、削除されて残った変形モデルグラフに対応する。
【００６６】
次に、接触パターン候補判定部１８の構成を説明する。
図９は、接触パターン候補判定部の構成を示す図である。
接触パターン候補判定部１８は、変形モデルグラフ読込部１８１と、サイズ計算部１８２と、文字線幅推定部１８３と、細線化部１８４と、グラフ化部１８５と、グラフ整形部１８６と、モデル・マッチング部１８７と、判定部１８８とを有している。
【００６７】
変形モデルグラフ読込部１８１は、文字認識結果の一位文字種（最も可能性が高いと判断された文字種）に対応した変形モデルグラフを読み込む。例えば、文字認識結果の一位文字種が「６」であれば、「６」の変形モデルグラフを読み込む。
【００６８】
サイズ計算部１８２は、判定対象パターンの幅・高さ・縦横比を求める。
文字線幅推定部１８３は、判定対象パターンの文字線の幅を推定する。
細線化部１８４、グラフ化部１８５およびグラフ整形部１８６は、それぞれ、細線化部１６４、グラフ化部１６５およびグラフ整形部１６６と同様の機能を有している。
【００６９】
すなわち、細線化部１８４は、判定対象パターンを細線化する。
グラフ化部１８５は、細線化したパターンに対し頂点・頂点間の辺を抽出する。そして、抽出した辺および頂点の、接続関係および隣接関係を求めることでグラフ化する。
【００７０】
グラフ整形部１８６は、グラフ化部１８５がグラフ化したグラフを一定のルールで整形する。
モデル・マッチング部１８７は、文字認識結果の一位文字種に対応する変形モデルグラフの全てとグラフ整形部１８６が整形したグラフとのマッチングを行う。具体的には、グラフ整形部１８６が整形したグラフと、各々の変形モデルグラフとの類似度を計算し、その中で最大のマッチング度（最大類似度）を求める。
【００７１】
判定部１８８は、モデル・マッチング部１８７で計算した変形モデルグラフのマッチング度と、サイズ計算部１８２で計算した判定対象パターンの縦横比とに基づいて、判定対象パターンが、接触パターン候補か否かを判定する。
【００７２】
次に、接触パターン候補判定部１８の処理（接触パターン候補判定処理）を説明する。
図１０は、接触パターン候補判定処理を示すフローチャートである。
まず、変形モデルグラフ読込部１８１が、文字認識部１５による一文字認識結果を受け取る（ステップＳ１）。
【００７３】
次に、変形モデルグラフ読込部１８１が、変形モデルグラフ格納部１７から文字認識結果の一位文字種に対応した変形モデルグラフを読み込む（ステップＳ２）。
次に、サイズ計算部１８２、文字線幅推定部１８３、細線化部１８４、グラフ化部１８５、およびグラフ整形部１８６がそれぞれの処理を行うことにより、判定対象パターンを整形したグラフを生成する（ステップＳ３）。
【００７４】
次に、モデル・マッチング部１８７が、最大マッチング度を計算する（ステップＳ４）。
次に、判定部１８８が、得られた最大マッチング度と縦横比とに基づいて判定対象パターンが、接触パターン候補か否かを判定する（ステップＳ５）。
【００７５】
接触パターン候補である場合（ステップＳ５のＹｅｓ）、判定対象パターンが接触パターン候補であると判断する（ステップＳ６）。
一方、接触パターン候補ではない場合（ステップＳ５のＮｏ）、判定対象パターンが一文字候補であると判断する（ステップＳ６）。
【００７６】
以上で、接触パターン候補判定処理の説明を終了する。
次に、ステップＳ４におけるモデル・マッチング部１８７の処理（モデル・マッチング処理）およびステップＳ５における判定部１８８の処理（判定処理）を具体的に説明する。
【００７７】
＜モデル・マッチング処理＞
ここでは一例として、Ullmann, "An Algorithm for Subgraph Isomorphism", Journal of the Association for Computing Machinery (1976), Vol. 23, No. 1, pp.31-42に記載されている、部分グラフ同型判定によるマッチングの手法を用いる。この手法は、入力パターンのグラフが、ある変形モデルグラフと同型部分を部分グラフに含むかどうかを調べる手法である。
【００７８】
モデルグラフの構築には様々な手法があるが、本実施の形態では、一つの変形モデルグラフは、次に示す情報から構成される。すなわち、モデル番号、モデルの持つ辺の数、モデルの持つ頂点数、モデルの頂点接続行列、モデルの頂点と辺の隣接行列、モデルの属する文字種である。この変形モデルグラフとして、例えば、以下の構造体struct Model＿infに示す隣接関係のみの情報を持つグラフを使用してもよい。
struct Model＿inf ｛
short      modelID;     モデル番号
short      edgeNo;      辺の数
short      vertexNo;    頂点数
short      *smatrix;    接続行列ポインタ
short      *bmatrix;    隣接行列ポインタ
short       category;   モデルの属する文字種
｝;
モデル・マッチング部１８７は、判定対象パターンから作成されたグラフの頂点隣接行列と、変形モデルグラフの頂点隣接行列とを用いてマッチングを実行する。具体的には、判定対象パターンから作成されたグラフと変形モデルグラフとの同型部分を計算する。そして、マッチングの結果として対応付け行列を得る。
【００７９】
ここで、一つの変形モデルグラフは、判定対象パターンから作成されたグラフの複数の部分と同型となることがある。よって、マッチングの結果は、対象とする変形モデルグラフのモデル番号、マッチした数を示すマッチング数、および、判定対象パターンから作成されたグラフにマッチした変形モデルグラフの頂点の対応付け行列となる。
【００８０】
図１１は、マッチングを実行したときの例を示す図である。
以下、判定対象パターンから作成されたグラフを「Ｇ」、判定対象パターンの文字認識結果の一位文字種Ｃに対する変形モデルグラフ数を「ＮC」、変形モデルグラフをｇCi（ｉ＝１、・・・、ＮC）とする。
【００８１】
図１１では、グラフＧを判定対象パターンの文字認識結果の一位文字種Ｃが「６」の変形モデルグラフと比較している。
図１１（ａ）に示すグラフＧの頂点隣接行列Ｓｐと図１１（ｂ）に示す変形モデルグラフｇ61の頂点隣接行列Ｓｍを下式（１）、（２）に示す。
【００８２】
【数１】
2010198308.tif 000003
【００８３】
【数２】
2010198308.tif 000004
【００８４】
頂点隣接行列Ｓｐのサイズは、グラフＧの頂点数×頂点数となっており、頂点隣接行列Ｓｍのサイズは、変形モデルグラフｇ61の頂点数×頂点数となっている。また、各行列の値は、頂点間が辺で結ばれている場合は「１」をとり、そうでない場合は「０」をとる。例えば、図１１に示すグラフＧの頂点ｖ１（１行目）は、頂点ｖ２にのみ辺で結ばれているため、２列目だけが「１」であり、それ以外の列は「０」である。また、頂点ｖ２（２行目）は、頂点ｖ１、ｖ３、ｖ５に辺で結ばれているため、１列目、３列目、５列目が「１」であり、それ以外の列は「０」である。
【００８５】
対応付け行列は、行数が変形モデルグラフの頂点数、列数が対象のグラフの頂点数に対応する。頂点間が対応付けられるときは「１」を、対応付けられないときは「０」を表す行列である。
【００８６】
図１１（ａ）に示すグラフＧと、図１１（ｂ）に示す変形モデルグラフｇ61との部分グラフ同型判定を行った結果、図１１（ｃ）に示すマッチング結果が得られる。図１１（ｃ）中、太い辺が変形モデルグラフｇ61とマッチした部分である。
【００８７】
図１１（ｃ）は、頂点Ｖ１が、頂点ｖ１に対応し、頂点Ｖ２が、頂点ｖ２に対応し、頂点Ｖ３が、頂点ｖ３に対応し、頂点Ｖ４が、頂点ｖ５に対応しているマッチング結果を示している。
【００８８】
図１１には図示していないが、頂点Ｖ１が、頂点ｖ１に対応し、頂点Ｖ２が、頂点ｖ２に対応し、頂点Ｖ３が、頂点ｖ５に対応し、頂点Ｖ４が、頂点ｖ３に対応しているマッチング結果も得られる。
【００８９】
同様に、図１１（ｃ）は、頂点Ｖ１が、頂点ｖ６に対応し、頂点Ｖ２が、頂点ｖ５に対応し、頂点Ｖ３が、頂点ｖ２に対応し、頂点Ｖ４が、頂点ｖ３に対応しているマッチング結果を示している。
【００９０】
図１１には図示していないが、頂点Ｖ１が、頂点ｖ６に対応し、頂点Ｖ２が、頂点ｖ５に対応し、頂点Ｖ３が、頂点ｖ３に対応し、頂点Ｖ４が、頂点ｖ２に対応しているマッチング結果も得られる。
【００９１】
このように、図１１に示す例ではマッチング数は「４」となる。この結果得られる対応付け行列Ｍ１〜Ｍ４を式（３）〜式（６）に示す。行列Ｍ１は、１番目（ｋ＝１）の部分グラフ同型判定により得られたマッチング結果の対応付け行列である。行列Ｍ２は、２番目（ｋ＝２）の部分グラフ同型判定により得られたマッチング結果の対応付け行列である。行列Ｍ３は、３番目（ｋ＝３）の部分グラフ同型判定により得られたマッチング結果の対応付け行列である。行列Ｍ４は、４番目（ｋ＝４）の部分グラフ同型判定により得られたマッチング結果の対応付け行列である。
【００９２】
【数３】
2010198308.tif 000005
【００９３】
【数４】
2010198308.tif 000006
【００９４】
【数５】
2010198308.tif 000007
【００９５】
【数６】
2010198308.tif 000008
【００９６】
マッチング結果、すなわち、マッチしたモデル番号、マッチング数、マッチング数個の頂点対応付け行列は、それぞれマッチング結果用構造体に格納される。このマッチング結果用構造体としては、例えば、次のstruct Matched＿resultに示す構造体に格納してもよい。
struct Matched＿result ｛
short      modelID;    モデル番号
short      No;         マッチング数
short    **mmatrix;     No個の頂点の対応付け行列
｝;
次に、モデル・マッチング部１８７は、得られたマッチング結果に基づいて、文字認識結果の一位文字種のモデルに対する各マッチング度を求め、変形モデルグラフそれぞれのマッチング度の最大値を求める。更に、その最大値が最も大きい変形モデルグラフを求めて、その変形モデルグラフの最大値を最大マッチング度とする。
【００９７】
図１２は、最大マッチング度を説明する図である。
最大マッチング度を説明するために、「６」の他の変形モデルグラフｇ62を図示している。
【００９８】
まず、文字認識結果の一位文字種のモデルに対する各マッチング度を求める処理を説明する。
グラフＧとｉ番目の変形モデルグラフｇCiとのマッチング数がｎiであったとき、グラフＧと変形モデルグラフｇCiのｋ番目の部分グラフ同型のマッチング度を「ｍCik（ｋ＝１、・・・、ｎi）」とする。
【００９９】
マッチング度ｍCikは、グラフＧの持つ辺か頂点の数が、文字種Ｃのｉ番目の変形モデルグラフｇCiの持つ辺または頂点の数より小さい場合は「−１」、そうでない場合は、グラフＧの各辺の長さの総和に対し、文字種Ｃのｉ番目の変形モデルグラフｇCiのｋ番目の部分グラフ同型でマッチングした辺の長さの和の比で定義する。
【０１００】
よって、変形モデルグラフｇCiとマッチしたｋ番目の部分グラフ同型に対応する辺の長さの総和を「ｌik」、グラフＧの辺の長さの総和を「Ｌ」とすると、下式（７）、（８）に示す関係となる。
【０１０１】
ｍCik＝ｌik／Ｌ・・・（７）
０≦ｍCik≦１，ｍCik＝−１・・・（８）
ここで、グラフＧの各辺の長さは、予め求めてある。また、辺と頂点の接続関係も予め求められている。例えば、頂点Ｖ１と頂点Ｖ２の間に辺ｅ１があることが予め分かっている。従って、これらの値を代入することにより、マッチング度ｍCikが求まる。
【０１０２】
図１３は、グラフの各辺の長さを示す図である。
図１３に示すように、辺のラベル毎に長さが格納されている。
図１４、図１５は、それぞれ、各変形モデルグラフのマッチング度を示す図である。
【０１０３】
前述したように、変形モデルグラフｇ61が、グラフＧの部分グラフとの部分グラフ同型判定の手法を使ったときのマッチング数は「４」である。従って、マッチング番号（ｋ）毎にマッチした辺の長さを算出する。
【０１０４】
例えば、対応付け行列Ｍ１より、対応付けられた頂点は、頂点ｖ１、ｖ２、ｖ３、ｖ５であることが分かる。従って、マッチした辺の長さの総和ｌ11は、頂点ｖ１、ｖ２間の辺ｅ１、頂点ｖ２、ｖ３間の辺ｅ２、頂点ｖ３、ｖ５間の辺ｅ３、および、頂点ｖ５、ｖ２間の辺ｅ４の和（＝５４）となる。
【０１０５】
マッチング度ｍ611は、ｌ1k／Ｌ＝５４／（２２＋１０＋１２＋１０＋７＋１３＋７）＝０．６７となる。
同様に、変形モデルグラフｇ62が、グラフＧの部分グラフとの部分グラフ同型判定の手法を使ったときのマッチング数は７である。従って、マッチング番号（ｋ）毎にマッチした辺の長さを算出する。
【０１０６】
そして、マッチング度ｍCikの最大のものを、グラフＧと変形モデルグラフｇCiのマッチング度ＭＤ（Ｇ，ｇCi）と定義する。全ての変形モデルグラフｇCi（ｉ＝１、・・・、ＮC）に対し、マッチング度ＭＤ（Ｇ，ｇCi）を求め、その最大値をグラフＧに対する文字種Ｃの変形モデルグラフの最大マッチング度ＭＤC（Ｇ）とする。式で表すと下式（９）〜（１１）のようになる。
【０１０７】
【数７】
2010198308.tif 000009
【０１０８】
【数８】
2010198308.tif 000010
【０１０９】
【数９】
2010198308.tif 000011
【０１１０】
図１４に示す例では、マッチング度ＭＤ（Ｇ，ｇ61）＝ｍａｘ｛０．６７，０．６７，０．４８，０．４８｝＝０．６７となる。
また、図１５に示す例では、マッチング度ＭＤ（Ｇ，ｇ62）＝ｍａｘ｛０．２７，０．１２，０．１５，０．１２，０．０９，０，１６，０．０９｝＝０．２７となる。
【０１１１】
次に、それらの最大値の中から最大を与えるモデル番号を求める。求めたマッチング度０．６７と０．２７とを比較すると０．６７が大きいので、モデル番号は「２」となる。
すなわち、ａｒｇｍａｘ＝｛ＭＤ（Ｇ，ｇ61），ＭＤ（Ｇ，ｇ62）｝＝ａｒｇｍａｘ｛０．２７，０．６７｝＝２となる。
【０１１２】
よって、グラフＧと変形モデルグラフｇ61、ｇ62との最大マッチング度ＭＤ6（Ｇ）＝ＭＤ（Ｇ，ｇ62）＝０．６７となる。
＜判定処理＞
判定部１８８は、モデル・マッチング部１８７で計算したグラフＧに対する文字種Ｃの変形モデルグラフの最大マッチング度ＭＤC（Ｇ）と、サイズ計算部１８２で計算した対象とするパターンの縦横比Ｒとに基づいて、接触パターン候補を判定する。
【０１１３】
パターンの縦横比は、パターンの高さＨに対するパターンの幅Ｗの比Ｗ／Ｈとする。横書きの場合は、最大マッチング度ＭＤC（Ｇ）とのマッチング度が閾値ＭＤｔｈ以下で、かつ、「０」より大きい、または、縦横比Ｒが閾値Ｒｔｈ以上を接触パターン候補と判定する。
【０１１４】
すなわち、認識結果の文字種Ｃが正しいとすればマッチング度が大きい。よって、接触パターンは逆にマッチング度が小さくなる。よって、マッチング度が閾値ＭＤｔｈ以下を接触パターン候補とする。但し、マッチングが「０」の変形モデルグラフよりグラフＧのサイズが小さい場合は、接触パターン候補から除外する。
【０１１５】
但し、マッチング度にかかわらず、例えば横書きのとき縦横比Ｒが大きい（横長である）場合は、接触パターンの可能性ありとする。式で表すと、次式（１２）となる。
（ＭＤC（Ｇ）≦ＭＤｔｈ）∧（ＭＤC（Ｇ）＞０）∨（Ｒ＞Ｒｔｈ）・・・（１２）
判定部１８８は、最大マッチング度ＭＤC（Ｇ）が小さいほど、その認識結果が信用できず接触パターンの可能性が高いと判定する。
【０１１６】
以上述べたように、文字認識装置１０によれば、一文字認識を実行して得られたカテゴリを、変形モデルとのマッチングを行うことで、そのカテゴリであることの正しさを構造的にチェックするようにした。これにより、候補数を増加させることなく文字の接触パターンを精度よく判定することができる。
【０１１７】
また、変形モデルグラフ生成部１６では、グラフ同型判定等を利用して自動的に初期変形モデルグラフを生成し、初期変形モデルグラフをモニタ１０４ａに表示してユーザに取捨選択を促すようにした。これにより、不適切な変形モデルグラフを除去することができるため、接触パターン候補の判定の精度を高めることができる。
【０１１８】
なお、文字認識装置１０が行った処理が、複数の装置によって分散処理されるようにしてもよい。例えば、一つの装置で変形モデルグラフを生成しておき、他の装置が、そのモデルグラフを用いて接触パターンの判定を行うようにしてもよい。
【０１１９】
以上、本発明の文字認識プログラム、文字認識方法および文字認識装置を、図示の実施の形態に基づいて説明したが、本発明はこれに限定されるものではなく、各部の構成は、同様の機能を有する任意の構成のものに置換することができる。また、本発明に、他の任意の構成物や工程が付加されていてもよい。
【０１２０】
また、本発明は、前述した実施の形態のうちの、任意の２以上の構成（特徴）を組み合わせたものであってもよい。
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、文字認識装置１０が有する機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等が挙げられる。磁気記録装置としては、例えば、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープ等が挙げられる。光ディスクとしては、例えば、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等が挙げられる。光磁気記録媒体としては、例えば、ＭＯ（Magneto-Optical disk）等が挙げられる。
【０１２１】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１２２】
文字認識プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【符号の説明】
【０１２３】
１、１０  文字認識装置
２  比較手段
３  判定手段
４  記憶部
４ａ、４ｂ、４ｃ、６  構造
５  判定対象パターン
１１  ２値化部
１２  行切り出し部
１３  ラベリング部
１４  文字認識用辞書格納部
１４ａ、１７ａ  データテーブル
１５  文字認識部
１６  変形モデルグラフ生成部
１７  変形モデルグラフ格納部
１８  接触パターン候補判定部
１９  接触パターンセグメンテーション部
２０  出力部
１６１  文字種指定受付部
１６２  データ読込部
１６３  文字線幅推定部
１６４  細線化部
１６５  グラフ化部
１６６  グラフ整形部
１６７  変形モデルグラフ生成・登録部
１６８  変形モデルグラフ表示部
１６９  削除指定受付部
１７０  不正変形モデルグラフ削除部
１８１  変形モデルグラフ読込部
１８２  サイズ計算部
１８３  文字線幅推定部
１８４  細線化部
１８５  グラフ化部
１８６  グラフ整形部
１８７  モデル・マッチング部
１８８  判定部
【図１】
2010198308.tif 000012
【図２】
2010198308.tif 000013
【図３】
2010198308.tif 000014
【図４】
2010198308.tif 000015
【図５】
2010198308.tif 000016
【図６】
2010198308.tif 000017
【図７】
2010198308.tif 000018
【図８】
2010198308.tif 000019
【図９】
2010198308.tif 000020
【図１０】
2010198308.tif 000021
【図１１】
2010198308.tif 000022
【図１２】
2010198308.tif 000023
【図１３】
2010198308.tif 000024
【図１４】
2010198308.tif 000025
【図１５】
2010198308.tif 000026