(57)【特許請求の範囲】
【請求項１】
入力画像内の文字を認識する文字認識処理をコンピュータに実行させる文字認識プログラムであって、
前記入力画像を、当該入力画像内の１文字が所定の数に分割される大きさの、複数の部分入力画像に分割する分割ステップと、
前記分割ステップによって得られた複数の部分入力画像の各々について特徴量を算出する特徴量算出ステップと、
複数の文字画像をそれぞれ前記所定の数に分割した部分文字画像の特徴量と、当該部分文字画像の特徴量がどの文字画像の、どの位置の部分文字画像の特徴量であるかと、前記文字画像によって示される文字種別とを対応付けて記憶した検索テーブルから、前記特徴量算出ステップによって算出された特徴量をキーにして、前記部分入力画像の各々について特徴量が類似する部分文字画像を検索する検索ステップと、
前記検索ステップによって得られた複数の部分文字画像を文字種別毎に集計し、各文字種別内における前記部分文字画像の位置関係と、当該部分文字画像に対応する部分入力画像の前記入力画像内における位置関係との整合性を判定し、部分文字画像の位置関係と整合する部分入力画像の組み合わせを文字候補として抽出する整合性判定ステップと、
前記整合性判定ステップによって抽出された文字候補が、所定数以上の部分入力画像を有する場合に、当該文字候補が有する部分入力画像が前記文字種別によって示された文字の構成要素であると認識する認識ステップと、
をコンピュータに実行させることを特徴とする文字認識プログラム。 
【請求項２】
前記整合性判定ステップは、前記複数の部分入力画像のうち、同一の文字種別の部分文字画像に類似する部分入力画像をノードとし、各ノードに対応する部分文字画像間の相対位置関係と、各ノードに対応する部分入力画像間の相対位置関係とが矛盾しないノード間を接続してグラフを作成するグラフ作成ステップと、前記グラフ作成ステップによって作成されたグラフの完全部分グラフであるクリークを前記文字候補として抽出するクリーク抽出ステップとを含んだことを特徴とする請求項１に記載の文字認識プログラム。 
【請求項３】
前記認識ステップは、前記整合性判定ステップによって抽出された文字候補が、所定数以上の部分入力画像を有する場合、当該部分入力画像の組み合わせに外接する矩形を求め、当該矩形内に前記文字種別によって示された文字が存在すると認識することを特徴とする請求項１または２に記載の文字認識プログラム。 
【請求項４】
前記検索テーブルは、同一の文字画像に対して分割サイズおよび／または分割位置の異なる分割処理を行なった場合にそれぞれ得られる部分文字画像に対して、各部分文字画像の特徴量と、当該各部分文字画像の特徴量がどの文字画像の、どの位置の部分文字画像の特徴量であるかと、前記文字画像によって示される文字種別とを対応付けて記憶することを特徴とする請求項１〜３のいずれか一つに記載の文字認識プログラム。 
【請求項５】
前記検索テーブルは、前記部分文字画像に対して類似する複数の特徴量を対応付け、当該複数の特徴量の各々に対して、前記部分文字画像の特徴量がどの文字画像の、どの位置の部分文字画像の特徴量であるかと、前記文字画像によって示される文字種別とを対応付けて記憶することを特徴とする請求項１〜４のいずれか一つに記載の文字認識プログラム。 
【請求項６】
入力画像内の文字を認識する文字認識装置であって、
前記入力画像を、当該入力画像内の１文字が所定の数に分割される大きさの、複数の部分入力画像に分割する分割手段と、
前記分割手段によって得られた複数の部分入力画像の各々について特徴量を算出する特徴量算出手段と、
複数の文字画像をそれぞれ前記所定の数に分割した部分文字画像の特徴量と、当該部分文字画像の特徴量がどの文字画像の、どの位置の部分文字画像の特徴量であるかと、前記文字画像によって示される文字種別とを対応付けた検索テーブルを記憶する検索テーブル記憶手段と、
前記特徴量算出手段によって算出された特徴量をキーにして前記検索テーブルを参照し、前記部分入力画像の各々について特徴量が類似する部分文字画像を検索する検索手段と、
前記検索手段によって得られた複数の部分文字画像を文字種別毎に集計し、各文字種別内における前記部分文字画像の位置関係と、当該部分文字画像に対応する部分入力画像の前記入力画像内における位置関係との整合性を判定し、部分文字画像の位置関係と整合する部分入力画像の組み合わせを文字候補として抽出する整合性判定手段と、
前記整合性判定手段によって抽出された文字候補が、所定数以上の部分入力画像を有する場合に、当該文字候補が有する部分入力画像が前記文字種別によって示された文字の構成要素であると認識する認識手段と、
を備えたことを特徴とする文字認識装置。 
【請求項７】
入力画像内の文字を認識する文字認識方法であって、
前記入力画像を、当該入力画像内の１文字が所定の数に分割される大きさの、複数の部分入力画像に分割する分割工程と、
前記分割工程によって得られた複数の部分入力画像の各々について特徴量を算出する特徴量算出工程と、
複数の文字画像をそれぞれ前記所定の数に分割した部分文字画像の特徴量と、当該部分文字画像の特徴量がどの文字画像の、どの位置の部分文字画像の特徴量であるかと、前記文字画像によって示される文字種別とを対応付けて記憶した検索テーブルから、前記特徴量算出工程によって算出された特徴量をキーにして、前記部分入力画像の各々について特徴量が類似する部分文字画像を検索する検索工程と、
前記検索工程によって得られた複数の部分文字画像を文字種別毎に集計し、各文字種別内における前記部分文字画像の位置関係と、当該部分文字画像に対応する部分入力画像の前記入力画像内における位置関係との整合性を判定し、部分文字画像の位置関係と整合する部分入力画像の組み合わせを文字候補として抽出する整合性判定工程と、
前記整合性判定工程によって抽出された文字候補が、所定数以上の部分入力画像を有する場合に、当該文字候補が有する部分入力画像が前記文字種別によって示された文字の構成要素であると認識する認識工程と、
を含んだことを特徴とする文字認識方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力画像内の文字を認識する文字認識プログラム、文字認識装置および文字認識方法であって、文字以外のパターンが重畳した文字画像を高精度に認識する文字認識プログラム、文字認識装置および文字認識方法に関するものである。
【背景技術】
【０００２】
従来、文字認識で予め文字パターンやその特徴量を文字種別ごとに辞書として記憶しておき、認識対象画像との比較演算により類似度を求め、類似度の最も高い文字種別を認識結果として出力する手法が用いられてきた。
【０００３】
このように文字パターンの特徴量から文字種別を認識する場合、認識対象画像内で文字が他の文字や記号と接触していると、文字パターンの形状が損なわれて特徴量を正しく算出できず、認識精度が著しく低下する。これに対し、従来の技術では、接触した複数のパターンを分離して、文字認識を行なう技術が知られている。
【０００４】
例えば特許文献１は、互いに接触する複数の文字パターンから構成される文字列パターンに対して、文字列パターンの外内輪郭部で検出した切断線端点の候補から各文字パターンの切断線と見なされる線分を構成する切断線端点のペアを抽出し、このペアの切断線端点を結ぶ線分で文字パターンの切出しを行なうことで、複雑に入り組んで接触している文字列でも正確な文字の切出しを実現する文字認識装置を開示している。
【０００５】
また、特許文献２は、表形式の帳簿類を対象とした文字認識において、認識用辞書として罫線と接触しない文字用の辞書と、罫線と接触した文字用の辞書とを具備するとともに、認識対象領域における文字と罫線との接触の有無を判定し、判定結果に応じて文字認識に使用する辞書を選択することで、帳簿類の文字を高精度に認識する文字認識装置を開示している。
【０００６】
【特許文献１】特開平６−１１１０７０号公報
【特許文献２】特開２００１−２２８８９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した特許文献１では、文字パターン同士の接触している場合や、丸中文字列のように特定形状と文字パターンが接触している場合にしか適用することができない。また、上述した特許文献２においても同様に、文字パターンが罫線と接触している場合にしか適用することができない。
【０００８】
すなわち、上述した従来技術では、文字パターンに対して接触するパターンの形状が不明である場合には、文字認識を十分に行なうことができないという問題点があった。このため、例えば、申込書やアンケートの選択肢欄で文字列や番号を直接手書きでマークさせ、これらの内容をコンピュータで読み取るためには、文字とマークが重複したパターンから正しく文字を認識する必要があるが、ユーザが行うマークは形状もさまざまであり、文字パターンとの接触の仕方もさまざまであるので、従来の技術では十分に認識することができなかった。
【０００９】
そこで、文字パターンとマークの重畳の形状に依存することなく、任意形状のパターンが重複した文字画像を高精度に文字認識する技術の実現が重要な課題となっていた。
【００１０】
本発明は、上述した従来技術における問題点を解消し、課題を解決するためになされたものであり、任意形状のパターンが重複した文字画像を高精度に文字認識する文字認識プログラム、文字認識装置および文字認識方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するために、本発明は、入力画像内の文字を認識する文字認識において、入力画像を複数の部分入力画像に分割し、分割によって得られた複数の部分入力画像の各々について特徴量を算出する。そして、複数の文字画像をそれぞれ複数の部分に分割して得られた各部分における部分文字画像の特徴量と、文字画像内における各部分文字画像の位置関係と、文字画像によって示される文字種別とを対応付けて記憶した検索テーブルを参照し、部分入力画像の各々について特徴量が類似する部分文字画像を検索する。さらに検索によって得られた複数の部分文字画像を文字種別毎に集計し、各文字種別内における部分文字画像の位置関係と、当該部分文字画像に対応する部分入力画像の入力画像内における位置関係との整合性を判定し、部分文字画像の位置関係と整合する部分入力画像の組み合わせを文字候補として抽出する。そして抽出した文字候補が、所定数以上の部分入力画像を有する場合に、当該文字候補が有する部分入力画像が文字種別によって示された文字の構成要素であると認識する。
【００１２】
また、本発明は、上記発明において、複数の部分入力画像のうち、同一の文字種別の部分文字画像に類似する部分入力画像をノードとし、各ノードに対応する部分文字画像間の相対位置関係と、各ノードに対応する部分入力画像間の相対位置関係とが矛盾しないノード間を接続してグラフを作成し、作成したグラフのクリークを文字候補として抽出することを特徴とする。
【００１３】
また、本発明は、上記発明において、抽出された文字候補が、所定数以上の部分入力画像を有する場合、当該部分入力画像の組み合わせに外接する矩形を求め、当該矩形内に文字種別によって示された文字が存在すると認識することを特徴とする。
【００１４】
また、本発明は、上記発明において、検索テーブルは、同一の文字画像に対して分割サイズおよび／または分割位置の異なる分割処理を行なった場合にそれぞれ得られる部分文字画像に対して、各部分文字画像の特徴量と、文字画像内における各部分文字画像の位置関係と、文字画像によって示される文字種別とを対応付けて記憶することを特徴とする。
【００１５】
また、本発明は、上記発明において、検索テーブルは、部分文字画像に対して類似する複数の特徴量を対応付け、当該複数の特徴量の各々に対して、文字画像内における各部分文字画像の位置関係と、文字画像によって示される文字種別とを対応付けて記憶することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、入力画像内で文字パターンと重複していない部分入力画像を使用して文字領域の位置と文字カテゴリとを求めることができるので、任意形状のパターンが重複した文字画像を高精度に文字認識することができるという効果を奏する。
【００１７】
また、本発明によれば、複数の部分入力画像の位置関係をグラフ化し、クリーク抽出によって整合のとれた部分入力画像の組み合わせを求めるので、任意形状のパターンが重複した文字画像を高精度かつ高速に文字認識することができるという効果を奏する。
【００１８】
また、本発明によれば、整合のとれた複数の部分入力画像の組み合わせに外接する矩形を文字領域とすることで、入力画像内で文字の存在する領域を簡易に特定することができるという効果を奏する。
【００１９】
また、本発明によれば、入力画像に対するメッシュ分割のサイズや位置のズレによる認識精度低下を防止し、高精度に文字認識を行なうことができるという効果を奏する。
【００２０】
また、本発明によれば、部分文字画像に対して類似する複数の特徴量を対応付けて検索テーブルに登録することで、部分入力画像に類似する部分文字画像を簡易に検索可能とし、もって文字認識速度を向上することができるという効果を奏する。
【発明を実施するための最良の形態】
【００２１】
以下に、本発明にかかる文字認識プログラム、文字認識装置および文字認識方法の実施例を図面に基づいて詳細に説明する。
【実施例】
【００２２】
本発明にかかる文字認識では、入力画像に対して文字パターンと文字以外のパターンを分離することなく、文字パターンのうち重複のない部分を利用して文字を認識する。すなわち、図４に示すように入力画像内の文字列「１．配偶者」に手書きでマークがされ、文字が繋がってそれぞれの文字を分離することが困難な場合であっても、マークがない部分の特徴から「１．配偶者」の文字が存在することを認識する。
【００２３】
そのために、まず入力画像を分割し、分割によって得られた各部分入力画像の特徴がどの文字のどの部分に類似しているかを求める。そして、同一の文字の異なる部分にそれぞれ類似する複数の部分入力画像の位置関係が、対応する文字内での位置関係と整合が取れている場合に、それらの複数の部分入力画像が文字の一部であると認識する。
【００２４】
図１は、本発明の実施例にかかる文字認識の機能構成を示す機能構成図である。同図に示すように文字認識装置１は、その内部に入力部１１、表示部１２、画像読取部１３、外部インターフェース１４、記憶部１５、制御部２０を有する。
【００２５】
入力部１１は、オペレータからの操作入力を受け付ける処理部であり、例えばキーボードなどによって実現される。また、表示部１２は、オペレータに対して表示出力を行なう装置であり、例えば液晶ディスプレイなどによって実現される。
【００２６】
画像読取部１３は、入力画像を読み取る処理を行なう処理部であり、スキャナなどによって実現される。また外部インターフェース１４は、外部の装置と接続してデータの送受信を行なう処理部である。
【００２７】
記憶部１５は、文字認識装置１が処理中に使用する各種データや、処理によって生成された各種データを記憶する記憶手段であり、同図に示した例では各文字カテゴリの局所的な特徴を示すハッシュテーブル１６を記憶している。ここで、文字カテゴリとは文字種別、文字名を指す。
【００２８】
制御部２０は、文字認識装置１を全体制御する制御部であり、その内部に認識処理部２１およびハッシュテーブル登録部２２を有する。ハッシュテーブル登録部２２は、外部インターフェース１４を介して取得した学習用の文字画像サンプルを用いてハッシュテーブル１６を作成し、記憶部１５に登録する処理を行なう。
【００２９】
認識処理部２１は、画像読取部１３が読み取った入力画像から文字を認識する処理を行なう処理部である。図２は、認識処理部２１の機能構成をさらに詳細に説明する機能構成図である。同図に示したように、認識処理部２１は、その内部にメッシュ分割部３１、特徴算出部３２、正規化処理部３３、文字カテゴリ検索部３４、位置整合性判定部３５および文字判定部３６を有する。
【００３０】
メッシュ分割部３１は、入力画像をメッシュ状に分割して部分入力画像を作成する処理を行なう。特徴算出部３２は、メッシュ分割部３１によって作成された複数の部分入力画像について、その特徴量を算出する処理を行なう。そして、正規化処理部３３は、特徴算出部３２によって算出した特徴量を正規化する処理を行なう。
【００３１】
文字カテゴリ検索部３４は、正規化処理部３３によって正規化された特徴量をキーにハッシュテーブル１６を参照し、部分入力画像の各々について特徴量が類似する文字カテゴリの部分文字画像を検索する。
【００３２】
位置整合性判定部３５は、文字カテゴリ検索部３４によって得られた複数の部分文字画像を文字カテゴリ毎に集計し、各文字カテゴリ内における部分文字画像の位置関係と、入力画像内における部分入力画像の位置関係との整合性を判定して、部分文字画像の位置関係と整合する部分入力画像の組み合わせを文字候補として抽出する処理を行なう。
【００３３】
文字判定部３６は、位置整合性判定部３５によって抽出された文字候補が、所定数以上の部分入力画像を有する場合に、その文字候補が有する部分入力画像が文字種別によって示された文字カテゴリの構成要素であると判定し、表示部１２にその文字カテゴリを表示出力する処理を行なう。
【００３４】
つづいて、文字認識装置１の各処理について詳細に説明する。まず、図３を参照し、ハッシュテーブル登録部２２による処理について説明する。図３は、ハッシュテーブル登録部２２によるハッシュテーブル１６の登録について説明する説明図である。
【００３５】
まず、ハッシュテーブル登録部２２は、外部インターフェース１４を介して学習用の文字画像サンプルを取得し、取得した文字画像をｎ×ｎ（例えばｎ＝５）でメッシュに分割する。そして分割によって得られた各メッシュをその文字画像の部分文字画像とし、メッシュごと（部分文字画像ごと）に特徴を算出する。
【００３６】
この特徴算出について種々の方法を適用することができ、例えば、加重方向指数ヒストグラム（電子情報通信学会論文誌D‘87／7 Vol.Ｊ70-D No.7 pp.1390-1397’加重方向指数ヒストグラム法による手書き漢字・ひらがな認識”など）を適用することができる。この加重方向指数ヒストグラムは、方向指数の個数分の次元を持つベクトルが特徴として得られるものであり、本実施例では４次元の特徴ベクトルを用いる場合を例に説明を行なう。
【００３７】
図３に示した例では、ハッシュテーブル登録部２２は、学習用の文字サンプルである「配」の文字画像を５×５で分割している。そして分割によって得られた各メッシュをｉ行ｊ列の行列と見なし、各メッシュを「配」（１，１）〜「配」（５，５）と識別して各メッシュの特徴ベクトルを算出すると、「配」（１，１）の特徴ベクトルは（２９，８，１３，５）、「配」（１，２）の特徴ベクトルは（３２，１４，１８，２５）、「配」（２，１）の特徴ベクトルは（１２，２，４，３７）となっている。
【００３８】
さらに、同一文字カテゴリについて複数の学習用の文字サンプルがある場合には、同一文字カテゴリに属する学習用サンプル画像数分に関して平均をとることによって個々の文字画像に依存する特徴成分を除去し、文字カテゴリ自体の特徴ベクトルを求める。
【００３９】
その結果、１つの文字カテゴリに対して、ｎ×ｎのメッシュ特徴ベクトルが得られる。また、このメッシュ特徴ベクトルの算出は、各文字カテゴリについてそれぞれ行なう。
【００４０】
次に、ハッシュテーブル登録部２２は、メッシュ特徴ベクトルをハッシュ値に変換し、ハッシュ値から文字カテゴリとメッシュの位置を引けるようにする。メッシュ特徴ベクトルは方向指数の個数分の次元のベクトルであるが、値域を０から９の整数をとるように正規化を行う。この結果、メッシュ特徴ベクトルは１０の方向指数の個数分（＝４）の累乗（＝１００００）通りの値をとることになる。
【００４１】
正規化の方法は任意の方法を用いることができるが、類似の値が同一の値に変換される手法を採用することが好ましい。例えば、所定数で除算して整数商を求め、商が９を越える場合は強制的に９に置き換える、といった手法が好適である。
【００４２】
図３に示した例では、ハッシュテーブル登録部２２は、特徴ベクトルの各次元の値を「４」で除算し、整数商を求めている。その結果、「配」（１，１）の特徴ベクトル（２９，８，１３，５）は（７，２，３，３）に正規化され、「配」（１，２）の特徴ベクトル（３２，１４，１８，２５）は（８，３，４，６）に正規化され、「配」（２，１）の特徴ベクトル（１２，２，４，３７）は（３，０，１，９）に正規化されている。
【００４３】
そして、ハッシュテーブル登録部２２は、正規化したメッシュ特徴ベクトル値に対して、文字カテゴリ名、メッシュの位置(i, j)を対応付けて、ハッシュテーブル１６に登録する。すなわち、メッシュ特徴ベクトル(va, vb, vc, vd)が与えられたとき、(va, vb, vc, vd)に正規化を行なって(Va, Vb, Vc, Vd)に変換し、H=Va×1000+Vb×100+Vc×10+Vdを求め、Hに(文字カテゴリ名, i, j)を記録する。
【００４４】
図３に示した例では、正規化した特徴ベクトルが（７，２，３，３）である「配」（１，１）はハッシュ値（７２３３）に対応付けられ、正規化した特徴ベクトルが（８，３，４，６）である「配」（１，２）はハッシュ値（８３４６）に対応付けられ、正規化した特徴ベクトルが（３，０，１，９）である「配」（２，１）はハッシュ値（３０１９）に対応付けられている。
【００４５】
ハッシュテーブル登録部２２は、以上の処理を全て文字カテゴリについて行なうことで、ハッシュテーブル１６を作成し、記憶部１５に格納する。同図に示した例では、ハッシュ値（７２３３）には「配」（１，１）に加えて「酸」（１，１），「王」（３，２）などが対応付けて登録され、ハッシュ値（３０１９）には「配」（２，１）に加えて「酸」（２，１），「祖」（１，３）などが対応付けて登録され、ハッシュ値（８３４６）には「配」（１，２）に加えて「祖」（３，２），「酉」（１，３）などが対応付けて登録されている。
【００４６】
つづいて、認識処理部２１による処理について説明する。図４は、認識処理部２１による入力画像の特徴算出と文字カテゴリ検索について説明する説明図である。画像読取部１３から入力画像が入力されると、メッシュ分割部３１が図４に示すように入力画像をメッシュに分割する。
【００４７】
この時、メッシュの大きさは、入力画像内の１文字がｎ×ｎで分割される大きさを基準にして設定する。例えば、入力画像の解像度が４００ｄｐｉのとき平均的な文字の大きさを縦横各４０画素として、メッシュの大きさを縦横各８画素と設定すれば、一文字を５×５に相当する大きさでメッシュ分割することができる。その他の解像度の画像に対しては、解像度に比例してメッシュの大きさを設定すればよい。また、周辺の文字の大きさが認識可能である場合には、周辺の文字の大きさに基づいてメッシュの大きさを設定すればよい。
【００４８】
なお、メッシュ分割部３１は、入力画像のメッシュ分割によって得られたメッシュ（部分入力画像）について、それぞれ入力画像のどの位置から切出されたかを記憶部１５に格納して記憶させる。
【００４９】
つぎに、特徴算出部３２は、切出された各メッシュについてそれぞれ特徴ベクトルを求める。この特徴ベクトルの算出には、ハッシュテーブル作成時と同様に、例えば加重方向指数ヒストグラムを用いる。図４に示した例では、入力画像から切出されたメッシュｍ４３の特徴ベクトルは（１３，１，５，６２）、同じくメッシュｍ１０４の特徴ベクトルは（３６，７，３，４）と求められている。
【００５０】
正規化処理部３３は、特徴算出部３２が算出した特徴ベクトルをそれぞれ正規化する処理を行なう。この正規化についてもハッシュテーブル作成時と同様に行ない、例えば、所定数で除算して整数商を求め、商が９を越える場合は強制的に９に置き換える。
【００５１】
図４に示した例では、正規化処理部３３は、特徴ベクトルの各次元の値を「４」で除算し、整数商を求めている。その結果、メッシュｍ４３の特徴ベクトル（１３，１，５，６２）は（３，０，１，９）に正規化され、メッシュｍ１０４の特徴ベクトル（３６，７，３，４）は（９，２，１，１）に正規化されている。
【００５２】
文字カテゴリ検索部３４は、正規化された特徴ベクトルをキーとしてハッシュテーブル１６を参照し、部分入力画像の各々について特徴量が類似する文字カテゴリの部分文字画像を検索する。
【００５３】
その結果、図４に示した例では、メッシュｍ４３に類似する部分文字画像として、ハッシュ値（３０１９）に紐付けられた部分文字画像、すなわち文字カテゴリ「配」の（２，１）、文字カテゴリ「酸」の（２，１）、文字カテゴリ「祖」の（１，３）などが検索結果として得られる。同じく、メッシュｍ１０４に類似する部分文字画像として、ハッシュ値（９２１１）に紐付けられた部分文字画像、すなわち文字カテゴリ「祖」の（４，４）、文字カテゴリ「酸」の（５，３）などが検索結果として得られる。
【００５４】
文字カテゴリ検索部３４が入力画像から切出された全てのメッシュ、すなわち部分入力画像について類似する部分文字画像を検索した後、位置整合性判定部３５は、検索結果として得られた複数の部分文字画像を文字カテゴリ毎に集計する。
【００５５】
図５は、検索結果の文字カテゴリ毎の集計について説明する説明図である。同図に示した例では、メッシュｍ４３，ｍ１０４の検索結果を文字カテゴリの対応する位置に投票して集計している。具体的には、文字カテゴリ「配」について、（２，１）の位置にメッシュｍ４３を投票し、（５，３）の位置にメッシュｍ１０４を投票している。同様に、文字カテゴリ「酸」の（２，１）にメッシュｍ４３を投票し、文字カテゴリ「祖」の（１，３）にメッシュｍ４３、文字カテゴリ「祖」の（４，４）にメッシュｍ１０４を投票している。
【００５６】
つぎに、位置整合性判定部３５は、各文字カテゴリに投票された部分入力画像について、入力画像での位置関係と文字カテゴリ内での位置関係とを比較し、その整合性を判定する。具体的には、位置整合性判定部３５は、同一の文字カテゴリの各位置に投票された部分入力画像をノードとして、文字カテゴリのメッシュ間での関係と入力画像のメッシュ間の関係が保たれるノード同士をパスで結ぶことでグラフを生成する。
【００５７】
図６は、位置整合性判定部３５による部分入力画像のグラフ化処理について説明する説明図である。同図に示した例では、入力画像から切出した部分入力画像であるメッシュｍ２１、メッシュｍ４３、メッシュｍ４４、メッシュｍ１０４、メッシュｍ１０５、メッシュｍ１０８が全て文字カテゴリ「配」に投票されている。
【００５８】
ここで、メッシュｍ２１は文字カテゴリ「配」の（１，１）に投票されている。同様に、メッシュｍ４３は（２，１）に、メッシュｍ４４は（２，２）に、メッシュｍ１０４は（５，４）に、メッシュｍ１０５は（５，５）に、メッシュｍ１０８は（４，４）に投票されている。
【００５９】
位置整合性判定部３５は、「配」に登録された全ての部分入力画像（メッシュｍ２１、メッシュｍ４３、メッシュｍ４４、メッシュｍ１０４、メッシュｍ１０５、メッシュｍ１０８）をノードとし、ノード間の位置関係に基づいてパスを引く。
【００６０】
図７は、ノード間でのパス接続について説明する説明図である。同図を参照し、メッシュｍ４３、メッシュｍ１０５、メッシュｍ１０８の位置関係を例にノード接続について説明する。
【００６１】
まず、メッシュｍ４３とメッシュｍ１０５について考える。入力画像においては、メッシュｍ４３に対して右下方向にメッシュｍ１０５が位置する。また、文字カテゴリ内においてもメッシュｍ４３に対して右下方向にメッシュｍ１０５が位置する。このように、メッシュｍ４３とメッシュｍ１０５との間では、入力画像内での相対位置関係と文字カテゴリ内での相対位置関係との整合が取れている（位置関係が保たれている）ので、メッシュｍ４３とメッシュｍ１０５との間をパスで結ぶ（図６に示すグラフ参照。）。
【００６２】
つぎに、メッシュｍ１０５とメッシュｍ１０８について考える。入力画像においては、メッシュｍ１０５と同じ高さの右方向にメッシュｍ１０８が位置する。これに対し、文字カテゴリ内ではメッシュｍ１０５に対して左上方向にメッシュｍ１０８が位置する。このように、メッシュｍ１０５とメッシュｍ１０８との間では、入力画像内での相対位置関係と文字カテゴリ内での相対位置関係との整合が取れていないので、メッシュｍ１０５とメッシュｍ１０８との間にはパスを引かない（図６に示すグラフ参照。）。
【００６３】
さらに、メッシュｍ４３とメッシュｍ１０８について考える。入力画像においては、メッシュｍ４３に対して右下方向にメッシュｍ１０８が位置する。また、文字カテゴリ内においてもメッシュｍ４３に対して右下方向にメッシュｍ１０８が位置する。このように、メッシュｍ４３とメッシュｍ１０８との間では、入力画像内での相対位置関係と文字カテゴリ内での相対位置関係との整合が取れているので、メッシュｍ４３とメッシュｍ１０８との間にパスを引く（図６に示すグラフ参照。）。
【００６４】
位置整合性判定部３５は、文字カテゴリごとに、投票されたメッシュのすべての２つの関係に対して位置の関係が満たされているかどうかを調べ、グラフを作成する。その後、位置整合性判定部３５は、作成したグラフから完全部分グラフであるクリークを抽出する処理を行なう。この位置整合性判定部３５が抽出するクリークは、部分文字画像の位置関係と整合する部分入力画像の組み合わせであり、入力画像内における文字候補となる。グラフからクリークを抽出するアルゴリズムとしては、種々の方法を用いることができる（例えば、C.Bron and J.Kerbosch Algorithm 457. Finding all cliques of an undirected graph [H]. Comm. ACM. 16(9) (September 1973).など。）。
【００６５】
文字判定部３６は、位置整合性判定部３５が抽出したクリークを評価することで、文字カテゴリが認識対象領域のどことマッチングしたかを識別する。具体的には、クリークのノードの個数がある閾値以上の場合にその対応が正しいとみなして、ノードに対応する対象領域にその文字カテゴリが存在すると判定する。
【００６６】
図８は、クリークの抽出と評価について説明する説明図である。同図に示したように、メッシュｍ２１、メッシュｍ４３、メッシュｍ４４、メッシュｍ１０４、メッシュｍ１０５、メッシュｍ１０８を有するグラフＧ１からクリークを抽出すると、メッシュｍ２１、メッシュｍ４３、メッシュｍ４４、メッシュｍ１０４、メッシュｍ１０５の５つのノードを有するクリークＧ２、メッシュｍ２１、メッシュｍ４３、メッシュｍ４４、メッシュｍ１０８の４つのノードを有するクリークＧ３とが得られる。
【００６７】
ここで、文字判定部３６による判定閾値が５であるとすると、クリークＧ２は閾値以上のノード数を有するので、文字判定部３６は、クリークＧ２の各ノードに対応する入力画像内の領域が文字カテゴリ「配」の文字が存在する文字領域であると判定する。一方、クリークＧ３のノード数は閾値に満たないため、文字判定部３６は、クリークＧ３のノードの組み合わせは「配」の文字ではないと判定する。
【００６８】
より詳細には、文字判定部３６は、閾値以上のノード数を有するクリークについて、各ノードに対応する部分入力画像に外接する矩形を求め、この外接矩形を文字領域と認識する。
【００６９】
図９は、文字判定部３６による文字領域の認識について説明する説明図である。同図に示した例では、文字判定部３６は、クリークＧ２を構成するメッシュｍ２１、メッシュｍ４３、メッシュｍ４４、メッシュｍ１０４、メッシュｍ１０５の外接矩形を文字領域Ａ１として判定し、この文字領域Ａ１に「配」の文字が存在すると認識する。
【００７０】
なお、入力画像に同じ文字が複数ある場合、文字判定部３６は、同一カテゴリの全ての文字から１つのグラフを作成する。その後、グラフからノード数が閾値を超える複数のクリークが抽出され、それぞれのクリークが入力画像内において各々異なる文字領域を構成することとなる。
【００７１】
ここまでの説明では、入力画像と文字カテゴリでの位置関係を明確すべく概念的な図面を用いて各処理部の動作を説明したが、各処理において実際に生成・使用されるデータは装置内での処理に適した形式で記憶部１５に格納される。
【００７２】
例えば、図１０は、位置整合性判定部３５が文字カテゴリ検索部による検索結果から作成する投票結果データである。この投票結果データは、図５を参照して説明した位置整合性判定部３５による集計の結果として得られたものであり、文字カテゴリ、カテゴリ内位置、入力画像メッシュ、の３つの項目を有する表の形式でデータを保持する。
【００７３】
また、図１１は、位置整合性判定部３５が作成するグラフデータである。このグラフデータでは、そのグラフが有する各ノード間について、パスを接続する場合には値「１」を、パスを接続しない場合には値「０」を持つ表の形式でデータを保持している。
【００７４】
つづいて、文字認識装置１による処理の流れを説明する。図１２は、ハッシュテーブル登録における処理動作を説明するフローチャートである。同図に示した処理では、まず、ハッシュテーブル登録部２２が外部インターフェース１４を介し、文字カテゴリ毎に複数のサンプル文字画像データを受け付ける（ステップＳ１０１）。
【００７５】
そして、ハッシュテーブル登録部２２は、受け付けたサンプル文字画像データをメッシュに分割し（ステップＳ１０２）、分割によって得られた各メッシュ、すなわち各部分文字画像について特徴ベクトルを算出する（ステップＳ１０３）。
【００７６】
その後、ハッシュテーブル登録部２２は、文字カテゴリのメッシュ位置毎に特徴ベクトルを平均し（ステップＳ１０４）、平均した特徴ベクトルを正規化する（ステップＳ１０５）。そして、正規化した特徴ベクトルに文字カテゴリとメッシュ位置とを対応付けてハッシュテーブルに登録し（ステップＳ１０６）、処理を終了する。ハッシュテーブル登録部２２は、以上の処理を文字カテゴリ毎に実行してハッシュテーブルを作成する。
【００７７】
図１３は、文字の認識処理における処理動作を説明するフローチャートである。同図に示した処理では、まず、メッシュ分割部３１が画像読取部１３によって読み取られた入力画像をメッシュに分割する（ステップＳ２０１）。つぎに、特徴算出部３２が、分割によって得られた各メッシュ（部分入力画像）について特徴ベクトルを算出する（ステップＳ２０２）。そして、正規化処理部３３が各特徴ベクトルを正規化し（ステップＳ２０３）、文字カテゴリ検索部３４は、各メッシュについて正規化された特徴ベクトルをキーにハッシュテーブルの検索を行なう（ステップＳ２０４）。
【００７８】
位置整合性判定部３５は、この検索結果を用いて文字カテゴリ毎に特徴ベクトルを投票し（ステップＳ２０５）、同一文字カテゴリに投票された入力画像のメッシュ（部分入力画像）をノードとするグラフを作成する（ステップＳ２０６）。このグラフ作成では、既に述べたように、各ノードに対応する部分画像領域の入力画像での位置関係と文字カテゴリ内での位置関係とを比較してノード間のパスを引いておく。
【００７９】
そして、位置整合性判定部３５は、各文字カテゴリのグラフからクリークを抽出する処理を行なう（ステップＳ２０７）。文字判定部３６は、得られたクリークのうち、ノード数が閾値を超えるクリークについて、クリーク構成ノードが占める領域に対応する文字カテゴリが存在すると判定し（ステップＳ２０８）、処理を終了する。
【００８０】
つづいて、ハッシュテーブル登録および文字認識の変形例について説明する。部分入力画像と特徴が類似する部分文字画像を検索する場合、例えば部分文字画像の特徴ベクトルと部分文字画像の特徴ベクトルの距離から類似度を算出し、類似度が閾値以上である場合に互いに類似する、と判定する手法を用いることも可能であるが、ベクトル間の距離を測定することで類似する組み合わせを探索すると演算に時間がかかる。そこで、文字認識装置１は、部分文字画像の特徴ベクトルをハッシュ値に変換し、ハッシュ値から文字カテゴリとメッシュの位置を引けるようにすることで、認識処理を高速化している。
【００８１】
具体的には、文字認識装置１は、特徴ベクトルからハッシュ値を作成する際に、類似の値が同一の値に変換されるよう正規化することで、類似度の算出を簡略化している。なお、上述した例では、特徴ベクトルの各次元の値を所定数で除算して整数商を求め、商が９を越える場合は強制的に９に置き換える手法を採用した場合について説明したが、この手法の変形例について説明する。
【００８２】
図１４は、ハッシュテーブル作成時における正規化の変形例について説明する説明図である。同図に示した例では、整数ａと整数ｂ（ａ＞ｂ）を定めておき、４次元ベクトル値（ｘ１, ｘ２, ｘ３, ｘ４）に対して、（ｘｉ±ｂ）/ａの整数商を求める。この商が９を越える場合は強制的に９に置き換える。
【００８３】
例えば、文字カテゴリ「配」の（２，１）特徴ベクトルが（１２,２,４,３７）であり、ａ＝４、ｂ＝１とすると、ｘ１を正規化した値として（１２＋１）／４＝３と（１２−１）／４＝２、ｘ２を正規化した値として（２＋１）／４＝０と（２−１）／４＝０、ｘ３を正規化した値として（４＋１）／４＝１と（４−１）／４＝０、ｘ４を正規化した値として （３７＋１）／４＝９,（３７−１）／４＝９が得られる。そして、これからできる全組合せを求めると、（３,０,０,９）,（３,０,１,９）,（４,０,０,９）,（４,０,１,９）の４通りの組合せが得られる。この場合、ハッシュテーブルには、文字カテゴリ「配」の（２，１）に対応して４通りの特徴ベクトルをそれぞれ登録する。
【００８４】
このように、ある特徴ベクトルに対して対応させるハッシュ値に幅を持たせ、文字カテゴリとメッシュ位置の組み合わせに複数のハッシュ値を対応させてハッシュテーブルに登録することで、類似度の比較において閾値を下げた場合と同様の効果、すなわち、比較的類似度の低い特徴ベクトルを検索結果として取得する効果を得ることができる。
【００８５】
ところで、サンプル文字画像や入力画像に対してメッシュ分割を行なう際、メッシュの位置によって、メッシュの特徴ベクトルの値は変わる。そこで、ハッシュテーブルを作成する際には、ある程度のずらしたメッシュを考え、サンプル文字のメッシュ特徴ベクトルを多重に登録しておくことが望ましい。入力画像に対しては、ひとつのメッシュでメッシュ特徴ベクトルを計算すればよい。同様に、メッシュの大きさに関しても、複数のサイズを考え、文字のメッシュ特徴ベクトルを多重に登録しておく。
【００８６】
図１５は、１つの文字画像に対して異なる複数のメッシュ分割を行なう場合について説明する説明図である。同図に示した例では文字画像をｎ×ｎに分割する際にｎ＝４，５，６の３つのメッシュサイズで分割している。これに加え、各分割サイズについて、ｘ方向とｙ方向に数画素ずらしたメッシュに関しても同様に特徴を求めている。
【００８７】
分割数ｎでｘ方向ｙ方向にズレのないメッシュ分割を行なって得られた特徴ベクトルを文字カテゴリの（ｎ,０,０）特徴とし、分割数ｎでｘ方向やｙ方向にズレを持つメッシュ分割を行なって得られた特徴ベクトルを（ｎ,ｄｘ,ｄｙ）特徴とする。例えば、ｄｘとｄｙは、メッシュを３等分するように２つの値を設定することにより、（ｎ,０,０）特徴、（ｎ,０,１）特徴、（ｎ,０,２）特徴、（ｎ,１,０）特徴、（ｎ,１,１）特徴、（ｎ,１,２）特徴、（ｎ,２,０）特徴、（ｎ,２,１）特徴、（ｎ,２,２）特徴の９つの特徴が設定される。例えば、１つのメッシュの一辺が６画素のときは、２画素ずつずらすことによりメッシュを３等分できる。
【００８８】
かくして、この例では２７個の（ｎ,ｄｘ,ｄｙ）特徴（ｎ＝４,５,６;ｄｘ＝０,１,２;ｄｙ＝０,１,２）を求めて、それぞれハッシュテーブルに登録する。特徴の値は、メッシュを行列とみなした場合の行数ｉと列数ｊと特徴ベクトル（ｖ１，ｖ２，ｖ３，ｖ４）により、(ｎ,ｄｘ,ｄｙ)−（ｉ,ｊ）−（ｖ１,ｖ２,ｖ３,ｖ４）で表現される。そこで、ハッシュテーブルに登録する際には、特徴ベクトル（ｖ１，ｖ２，ｖ３，ｖ４）から算出したハッシュ値Ｈに(文字カテゴリ名,ｎ,ｄｘ,ｄｙ,ｉ,ｊ)を対応付けて登録すればよい。
【００８９】
このように（ｎ,ｄｘ,ｄｙ）特徴を求めてそれぞれハッシュテーブルに登録した場合の認識処理では、メッシュサイズやメッシュ位置の異なる複数の部分文字画像が検索結果として得られるので、文字カテゴリ上にそれぞれの検索結果を投影して位置関係の整合性を評価する。
【００９０】
図１６は、（ｎ,ｄｘ,ｄｙ）特徴を用いる場合の認識処理について説明する説明図である。同図に示した例では、入力画像上のメッシュｍαに対して（４，０，０）特徴、（５，０，０）特徴のそれぞれで対応する部分文字画像が存在し、入力画像上のメッシュｍβに対して（４，０，１）特徴で対応する部分文字画像が存在する。この場合、文字カテゴリ上で各部分文字画像の位置を投影することで、メッシュｍαについて（４，０，０）での投影像としてｍα’、（５，０，０）での投影像としてｍα’’が得られる。同じくメッシュｍβについて（４，０，１）での投影像としてｍβ’が得られる。
【００９１】
このようにしてメッシュ分割のサイズや位置の異なる特徴ベクトルが混在する場合であっても、文字カテゴリ上に投影することで相互の位置関係を評価することができる。なお、同図に示したように、１つの部分入力画像ｍαから複数の投影像ｍα’，ｍα’’が得られた場合、それぞれの投影像を個別のノードとして取り扱えばよい。
【００９２】
つぎに、本発明の利用例について説明する。図１７は、本発明を利用した画像認識システムの概要構成について説明する概要構成図である。同図に示した画像認識システム１００は、スキャナ１０１と接続され、スキャナ１０１が読み取った画像データＤ１を取得する。画像データＤ１は、選択肢欄で文字列や番号を直接手書きでマークさせた申込書やアンケートであり、文字パターンに手書きマークが重複している。
【００９３】
画像認識システム１００は、その内部に文字認識装置１、差分画像作成部１０２、画像解析部１０３を有する。文字認識装置１は、これまで説明してきたように、画像データＤ１に対して文字認識を行なって、認識結果である画像データＤ２を出力する。この画像データＤ２は、その画像内のどの位置に何の文字が存在するかが示されている。
【００９４】
差分画像作成部１０２は、画像データＤ１と画像データＤ２との差分を取ることで、画像データＤ３を作成する。画像データＤ１は文字に手書きマークが重なっており、画像データＤ２は文字のみが含まれているので、これらの差分である画像データＤ３は手書きマークが抜き出された画像となる。
【００９５】
画像解析部１０３は、画像データＤ３に示された手書きマークの位置と、画像データＤ２に示された文字とその位置から、どの選択肢が選択されているかを出力する。同図に示した例では、画像解析部１０３は、画像データＤ１が「１．配偶者」を選択したものであることを示す解析結果データＤ４を出力することができる。
【００９６】
以上説明してきたように、本実施例にかかる文字認識装置１は、ハッシュテーブル登録部２２が各文字カテゴリの局所的な領域である部分入力画像の特徴を示すハッシュテーブル１６を作成し、認識処理部２１は、入力画像をメッシュ分割して部分入力画像に分割し、各部分入力画像について特徴を算出し、各部分入力画像と特徴が類似する部分文字画像をハッシュテーブルから検索し、部分入力画像の位置関係と部分文字画像の位置関係とを比較し、その整合性を評価して入力画像のどの領域にどの文字が存在するかを認識する。
【００９７】
そのため、文字認識装置１は、入力画像において文字パターンと文字以外のパターンを分離することなく、文字パターンのうち重複のない部分を利用して文字を認識することができ、文字パターンに接触する文字以外のパターンの形状や接触の仕方がいかなるものであっても文字パターンを認識可能である。また、画像をメッシュに分割し、メッシュごとに類似度を求め、それらの位置の整合性から全体の類似度を求めて認識を行うため、画像から文字単位に文字領域を切り出す必要なく認識が可能になる。
【００９８】
なお、本実施例はあくまで一例であり、本発明を限定するものではない。本発明は請求の範囲に記載した技術的思想の範囲内において構成および動作を適宜変更して実施することができるものである。
【００９９】
例えば、本実施例では、文字認識装置１は、ハッシュテーブル登録部２２によるハッシュテーブル登録と認識処理部２１による文字認識とを切り替えて実行するように構成しているが、例えば、他の装置が作成したハッシュテーブルを使用し、文字認識のみを実行するように構成してもよい。
【０１００】
また、部分入力画像や部分文字画像の特徴の算出、特徴が類似する文字カテゴリの検索、部分入力画像や部分文字画像の位置関係の整合性判定などについても、任意の手法を適用することができる。例えば、本実施例においては、ノード間のパスを引く際に、メッシュ間の相対方向によって位置関係の整合性を判定していたが、相対方向に加えてメッシュ間の距離についても位置関係の整合性の判断基準として用いることもできる。
【０１０１】
なお、本発明にかかる文字認識方法は、図１および図２に示した文字認識装置１のように各機能部を専用のハードウェアによって実現することでも実施可能であるが、文字認識プログラムをコンピュータに実行させ、コンピュータのハードウェア資源をそれぞれの機能部として動作させることでも実施することができる。
【０１０２】
図１８は、文字認識プログラムを実行するコンピュータの概要構成を説明する概要構成図である。同図に示したように、コンピュータ４０は、入力装置４１、表示装置４２、画像読取装置４３、外部インターフェース４４、ＣＰＵ（Central Processing Unit）４５、ＲＯＭ（Read Only Memory）４６、ＲＡＭ（Random Access Memory）４７およびＨＤＤ（Hard Disk Drive）４８をバス４９で接続して構成される。ここで、入力装置４１は、図１に示した入力部１１に対応し、表示装置４２は同じく表示部１２に対応し、画像読取装置４３および外部インターフェース４４は同じく画像読取部１３及び外部インターフェース１４に対応する。
【０１０３】
そして、ＲＯＭ４６には、上記の認識処理部２１およびハッシュテーブル登録部２２と同様の機能を発揮する認識処理プログラム５１およびハッシュテーブル登録プログラム５２が予め記憶されている。
【０１０４】
ＣＰＵ４５は認識処理プログラム５１やハッシュテーブル登録プログラム５２をＲＯＭ４６から読み出して実行することで、その機能を実現することができる。例えば図１８に示した例では、ＣＰＵ４５はＲＯＭ４６から認識処理プログラム５１を読み出して認識処理プロセス５４を動作させており、ＣＰＵ４５は認識処理部２１と同様の動作を行うこととなる。
【０１０５】
また、ＨＤＤ４８は、図１８に示したようにハッシュテーブルデータ５３を格納している。このハッシュテーブルデータ５３は、ＣＰＵ４５によって読み出されてＲＡＭ４７上に展開され、図１および図２に示したハッシュテーブル１６として動作する。
【０１０６】
ところで、上記した認識処理プログラム５１やハッシュテーブル登録プログラム５２は、必ずしも最初からＲＯＭ４６に記憶させておく必要は無く、例えば、コンピュータ４０に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「過般用の物理媒体」、または、コンピュータ４０の内外に備えられるハードディスクドライブ（ＨＤＤ）などの「固定用の物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ４０に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておき、コンピュータ４０がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１０７】
（付記１）入力画像内の文字を認識する文字認識処理をコンピュータに実行させる文字認識プログラムであって、
前記入力画像を複数の部分入力画像に分割する分割ステップと、
前記分割ステップによって得られた複数の部分入力画像の各々について特徴量を算出する特徴量算出ステップと、
複数の文字画像をそれぞれ複数の部分に分割して得られた各部分における部分文字画像の特徴量と、前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けて記憶した検索テーブルから、前記特徴量算出ステップによって算出された特徴量をキーにして、前記部分入力画像の各々について特徴量が類似する部分文字画像を検索する検索ステップと、
前記検索ステップによって得られた複数の部分文字画像を文字種別毎に集計し、各文字種別内における前記部分文字画像の位置関係と、当該部分文字画像に対応する部分入力画像の前記入力画像内における位置関係との整合性を判定し、部分文字画像の位置関係と整合する部分入力画像の組み合わせを文字候補として抽出する整合性判定ステップと、
前記整合性判定ステップによって抽出された文字候補が、所定数以上の部分入力画像を有する場合に、当該文字候補が有する部分入力画像が前記文字種別によって示された文字の構成要素であると認識する認識ステップと、
をコンピュータに実行させることを特徴とする文字認識プログラム。
【０１０８】
（付記２）前記整合性判定ステップは、前記複数の部分入力画像のうち、同一の文字種別の部分文字画像に類似する部分入力画像をノードとし、各ノードに対応する部分文字画像間の相対位置関係と、各ノードに対応する部分入力画像間の相対位置関係とが矛盾しないノード間を接続してグラフを作成するグラフ作成ステップと、前記グラフ作成ステップによって作成されたグラフの完全部分グラフであるクリークを前記文字候補として抽出するクリーク抽出ステップとを含んだことを特徴とする付記１に記載の文字認識プログラム。
【０１０９】
（付記３）前記認識ステップは、前記整合性判定ステップによって抽出された文字候補が、所定数以上の部分入力画像を有する場合、当該部分入力画像の組み合わせに外接する矩形を求め、当該矩形内に前記文字種別によって示された文字が存在すると認識することを特徴とする付記１または２に記載の文字認識プログラム。
【０１１０】
（付記４）前記検索テーブルは、同一の文字画像に対して分割サイズおよび／または分割位置の異なる分割処理を行なった場合にそれぞれ得られる部分文字画像に対して、各部分文字画像の特徴量と、前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けて記憶することを特徴とする付記１〜３のいずれか一つに記載の文字認識プログラム。
【０１１１】
（付記５）前記検索テーブルは、前記部分文字画像に対して類似する複数の特徴量を対応付け、当該複数の特徴量の各々に対して、前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けて記憶することを特徴とする付記１〜４のいずれか一つに記載の文字認識プログラム。
【０１１２】
（付記６）入力画像内の文字を認識する文字認識装置であって、
複数の文字画像をそれぞれ複数の部分に分割して得られた各部分における部分文字画像の特徴量と、前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けた検索テーブルを記憶する検索テーブル記憶手段と、
前記入力画像を複数の部分入力画像に分割する分割手段と、
前記分割手段によって得られた複数の部分入力画像の各々について特徴量を算出する特徴量算出手段と、
前記特徴量算出手段によって算出された特徴量をキーにして前記検索テーブルを参照し、前記部分入力画像の各々について特徴量が類似する部分文字画像を検索する検索手段と、
前記検索手段によって得られた複数の部分文字画像を文字種別毎に集計し、各文字種別内における前記部分文字画像の位置関係と、当該部分文字画像に対応する部分入力画像の前記入力画像内における位置関係との整合性を判定し、部分文字画像の位置関係と整合する部分入力画像の組み合わせを文字候補として抽出する整合性判定手段と、
前記整合性判定手段によって抽出された文字候補が、所定数以上の部分入力画像を有する場合に、当該文字候補が有する部分入力画像が前記文字種別によって示された文字の構成要素であると認識する認識手段と、
を備えたことを特徴とする文字認識装置。
【０１１３】
（付記７）前記整合性判定手段は、前記複数の部分入力画像のうち、同一の文字種別の部分文字画像に類似する部分入力画像をノードとし、各ノードに対応する部分文字画像間の相対位置関係と、各ノードに対応する部分入力画像間の相対位置関係とが矛盾しないノード間を接続してグラフを作成し、作成したグラフの完全部分グラフであるクリークを前記文字候補として抽出することを特徴とする付記６に記載の文字認識装置。
【０１１４】
（付記８）前記認識手段は、前記整合性判定手段によって抽出された文字候補が、所定数以上の部分入力画像を有する場合、当該部分入力画像の組み合わせに外接する矩形を求め、当該矩形内に前記文字種別によって示された文字が存在すると認識することを特徴とする付記６または７に記載の文字認識装置。
【０１１５】
（付記９）前記検索テーブルは、同一の文字画像に対して分割サイズおよび／または分割位置の異なる分割処理を行なった場合にそれぞれ得られる部分文字画像に対して、各部分文字画像の特徴量と、前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けて記憶することを特徴とする付記６〜８のいずれか一つに記載の文字認識装置。
【０１１６】
（付記１０）前記検索テーブルは、前記部分文字画像に対して類似する複数の特徴量を対応付け、当該複数の特徴量の各々に対して前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けて記憶することを特徴とする付記６〜９のいずれか一つに記載の文字認識装置。
【０１１７】
（付記１１）入力画像内の文字を認識する文字認識方法であって、
前記入力画像を複数の部分入力画像に分割する分割工程と、
前記分割工程によって得られた複数の部分入力画像の各々について特徴量を算出する特徴量算出工程と、
複数の文字画像をそれぞれ複数の部分に分割して得られた各部分における部分文字画像の特徴量と、前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けて記憶した検索テーブルから、前記特徴量算出工程によって算出された特徴量をキーにして、前記部分入力画像の各々について特徴量が類似する部分文字画像を検索する検索工程と、
前記検索工程によって得られた複数の部分文字画像を文字種別毎に集計し、各文字種別内における前記部分文字画像の位置関係と、当該部分文字画像に対応する部分入力画像の前記入力画像内における位置関係との整合性を判定し、部分文字画像の位置関係と整合する部分入力画像の組み合わせを文字候補として抽出する整合性判定工程と、
前記整合性判定工程によって抽出された文字候補が、所定数以上の部分入力画像を有する場合に、当該文字候補が有する部分入力画像が前記文字種別によって示された文字の構成要素であると認識する認識工程と、
を含んだことを特徴とする文字認識方法。
【０１１８】
（付記１２）前記整合性判定工程は、前記複数の部分入力画像のうち、同一の文字種別の部分文字画像に類似する部分入力画像をノードとし、各ノードに対応する部分文字画像間の相対位置関係と、各ノードに対応する部分入力画像間の相対位置関係とが矛盾しないノード間を接続してグラフを作成するグラフ作成工程と、前記グラフ作成工程によって作成されたグラフの完全部分グラフであるクリークを前記文字候補として抽出するクリーク抽出工程とを含んだことを特徴とする付記１１に記載の文字認識方法。
【０１１９】
（付記１３）前記認識工程は、前記整合性判定工程によって抽出された文字候補が、所定数以上の部分入力画像を有する場合、当該部分入力画像の組み合わせに外接する矩形を求め、当該矩形内に前記文字種別によって示された文字が存在すると認識することを特徴とする付記１１または１２に記載の文字認識方法。
【０１２０】
（付記１４）前記検索テーブルは、同一の文字画像に対して分割サイズおよび／または分割位置の異なる分割処理を行なった場合にそれぞれ得られる部分文字画像に対して、各部分文字画像の特徴量と、前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けて記憶することを特徴とする付記１１〜１３のいずれか一つに記載の文字認識方法。
【０１２１】
（付記１５）前記検索テーブルは、前記部分文字画像に対して類似する複数の特徴量を対応付け、当該複数の特徴量の各々に対して、前記文字画像内における各部分文字画像の位置関係と、前記文字画像によって示される文字種別とを対応付けて記憶することを特徴とする付記１１〜１４のいずれか一つに記載の文字認識方法。
【産業上の利用可能性】
【０１２２】
以上のように、本発明にかかる文字認識プログラム、文字認識装置および文字認識方法は、文字認識に有用であり、特に、文字以外のパターンが重畳した文字画像の認識に適している。
【図面の簡単な説明】
【０１２３】
【図１】本発明の実施例にかかる文字認識装置の機能構成を示す機能構成図である。
【図２】認識処理部２１の機能構成をさらに詳細に説明する機能構成図である。
【図３】ハッシュテーブル登録部２２によるハッシュテーブル１６の登録について説明する説明図である。
【図４】認識処理部２１による入力画像の特徴算出と文字カテゴリ検索について説明する説明図である。
【図５】検索結果の文字カテゴリ毎の集計について説明する説明図である。
【図６】位置整合性判定部３５による部分入力画像のグラフ化処理について説明する説明図である。
【図７】ノード間でのパス接続について説明する説明図である。
【図８】クリークの抽出と評価について説明する説明図である。
【図９】文字判定部３６による文字領域の認識について説明する説明図である。
【図１０】位置整合性判定部３５が文字カテゴリ検索部による検索結果から作成する投票結果データを示す図である。
【図１１】位置整合性判定部３５が作成するグラフデータを示す図である。
【図１２】ハッシュテーブル登録の処理動作を説明するフローチャートである。
【図１３】文字の認識処理における処理動作を説明するフローチャートである。
【図１４】ハッシュテーブル作成時における正規化の変形例について説明する説明図である。
【図１５】１つの文字画像に対して異なる複数のメッシュ分割を行なう場合について説明する説明図である。
【図１６】（ｎ,ｄｘ,ｄｙ）特徴を用いる場合の認識処理について説明する説明図である。
【図１７】本発明を利用した画像認識システムの概要構成について説明する概要構成図である。
【図１８】文字認識プログラムを実行するコンピュータの概要構成を説明する概要構成図である。
【符号の説明】
【０１２４】
１    文字認識装置
１１    入力部
１２    表示部
１３    画像読取部
１４    外部インターフェース
１５    記憶部
１６    ハッシュテーブル
２０    制御部
２１    認識処理部
２２    ハッシュテーブル登録部
３１    メッシュ分割部
３２    特徴算出部
３３    正規化処理部
３４    文字カテゴリ検索部
３５    位置整合性判定部
３６    文字判定部
４０    コンピュータ
４１    入力装置
４２    表示装置
４３    画像読取装置
４４    外部インターフェース
４９    バス
５１    認識処理プログラム
５２    ハッシュテーブル登録プログラム
５３    ハッシュテーブルデータ
５４    認識処理プロセス
１００    画像認識システム
１０１    スキャナ
１０２    差分画像作成部
１０３    画像解析部
Ｄ１，Ｄ２，Ｄ３    画像データ
Ｄ４    解析結果データ
Ｇ１    グラフ
Ｇ２，Ｇ３    クリーク
ｍ２１，ｍ４３，ｍ４４，ｍ１０４，ｍ１０５，ｍ１０８，ｍα，ｍβ    メッシュ
ｍα’，ｍα’’，ｍβ’    投影像
【図１】
0005098504.tif 000002
【図２】
0005098504.tif 000003
【図３】
0005098504.tif 000004
【図４】
0005098504.tif 000005
【図５】
0005098504.tif 000006
【図６】
0005098504.tif 000007
【図７】
0005098504.tif 000008
【図８】
0005098504.tif 000009
【図９】
0005098504.tif 000010
【図１０】
0005098504.tif 000011
【図１１】
0005098504.tif 000012
【図１２】
0005098504.tif 000013
【図１３】
0005098504.tif 000014
【図１４】
0005098504.tif 000015
【図１５】
0005098504.tif 000016
【図１６】
0005098504.tif 000017
【図１７】
0005098504.tif 000018
【図１８】
0005098504.tif 000019