(57)【特許請求の範囲】
【請求項１】
文書表面の濃淡情報を電気信号に変換して画像として入力する画像入力手段と、
読取対象の文字列が記載されるべき領域である読取りフィールドを上記入力画像から切出すフィールド切出し手段と、
上記切出された読取りフィールドから、部分画像を候補パタンとして切り出し、前記候補パタンを辺で表現し、かつ、その候補パタン間の境界を接点で表現するネットワークを切出す手段と、
上記検出された候補パタンを記号として識別する文字識別手段と、
文字列の表記のし方を記号と記号列の書換規則の集合で記憶し、前記書換規則には前記記号列の元になる候補パタンの空間的配置の制約を有する文法情報記憶手段と、
上記識別された複数の記号から書換規則に従って候補構文要素群を生成し、前記候補構文要素の組合せを文候補として出力する構文解析手段と、
前記文候補が文字列として妥当かを評価し、併せて前記候補パタンの組合せの空間的配置に基づき文字列の妥当性を判定する検定手段とを備えることを特徴とする文字列認識装置。
【請求項２】
請求項１の文字列認識装置において、上記文法情報記憶手段に記憶してある表記のし方が数字と数字以外の記号の配列の仕方であることを特徴とする文字列認識装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、帳票などの文書上に記載された金額、日付け、電話番号など数字を中心とする文字列を読取る文字列認識装置にかかわる。
【０００２】
【従来の技術】
数字を主とする文字列の代表例として金額、電話番号、年月日などがある。以下では文字列認識に関わる従来技術を、上記金額を表す文字列の認識を例に説明する。
【０００３】
帳票などに記載する金額を表す文字列には「￥１００−」、「￥１，２００−」、「￥１２，０００，０００−」のようなものがある。
ここでは、
・金額の先頭には「￥」をつける、
・３桁ごとに「，」をつける、
・金額の最後には「−」をつける、
などの規則が用いられている。
【０００４】
こうした文字列を読取る方式としては、一般的には以下のような手順が知られている。
（１）文字切出し…文字として尤もらしい部分画像を切り出す。
（２）文字識別…各々の部分画像の文字カテゴリ（文字コード）を識別する。
（３）文字列照合…文字の識別結果を文字列として解釈する。
【０００５】
上記（１）の文字切出しには、位置、大きさなどの一定の条件を満たす連結成分の組合せを文字行中から取出す方式がしばしば用いられる。この際、文字同士の接触などのため、文字間の境界を検出するのが困難となる場合がある。このような場合には、接触した箇所を検出して切断するとともに、文字切出しに多重仮説検定法（文献１：H.Fujisawa,  Y.Nakano,  and  K.Kurino,”Segmentation  Methods  for  Character  Recognition  :  From  Segmentation  to  Document  Structure  Analysis”Proc.  of  the  IEEE  vol.80,No.7,1992）を用いることで精度を高めることができる。
【０００６】
ここで上記多重仮説検定法とは、一旦複数の文字の切出し方を試行したのち、文字識別の結果を利用して文字の切出し方を決定する方式である。
【０００７】
上記（２）の文字識別には、予め記憶している標準パタン中で最も入力パタンに類似したものを選び出すパタン整合法がよく用いられる。文字識別は通常複数の文字候補とそれらの尤もらしさの評価値を出力する。後段の文字列照合にて、これら複数の文字候補から文字列として解釈して妥当なものを選択する。
【０００８】
上記（３）の文字列照合では、認識対象の文字列が上述の規則に従っているかどうかを検査する。また、帳票上の汚れもしくは文字のかすれなどがある場合、あるいは文字の変形が大きかったり文字同士が接触していたりする場合、文字列の認識を正確に行うことが困難になる。こうした場合、文字切出しや文字識別の精度を向上するために、文字列照合処理によって上記のような規則を利用した文字の切出し方あるいは候補文字の選択をおこなうことが解決策として知られている。
【０００９】
そして上記（３）の手法としては、準定型帳票中のＩ．Ｄ．コードなどを対象にしたもの（文献２：丸川他「表記規則を持つ数字文字列の認識における文字列チェック機能の一検討」１９９４年電子情報通信学会秋期大会Ｄ−３１３，ｐ．３２１）、住所の丁目・番地を対象にしたもの（文献３：緒方他「住所表示番号と棟・部屋番号の連続表記に対する照合方式」信学技報ＰＲＭＵ９９−２１９）、（文献４：大井他「住所読み取りにおける丁目・街区認識方式」信学技報ＮＬＣ９２−９６、１９９２）等がある。
【００１０】
しかし、従来の文字列照合の手法は、対象への依存が大きく、対象を変更することは困難であった。例えば上記文献２あるいは文献４では、それぞれの認識対象に特化した方式であって、他の方式への適用は困難である。また、上記文献３の技術では表記形式の辞書を変更することにより認識対象を変更することができるが、表記の組合わせは膨大な数になることが多く、辞書の変更が容易ではなかった。
【００１１】
また、文脈自由文法を文字列照合に用いると、多くの表記形式を簡潔に記述できることが知られている（文献５：古賀他「地名表記方法および地名文字列認識方法」特願平１１−１８７７５３）。しかし、本発明のように数字を中心とする文字列にこうした手法を適用した例はなかった。
【００１２】
さらに、金額などを高い精度で読取るためには「，」は文字行の下のほうにある、数字同士はほぼ大きさが揃っているが「ー」や「，」は小さいことがある、などといった文字の空間的配置に関する情報を利用することが必要である。しかし、従来の方式ではこうした配置の情報を表記の規則と有効に結び付けることができなかった。
【００１３】
【発明が解決しようとする課題】
本発明が解決しようとする第１の課題は、数字を中心とする文字列の表記上の規則を利用し、高精度かつ高速に文字識別結果を文字列として認識する文字列認識装置を実現することである。本発明が解決しようとする第２の課題は、文脈的な表記上の制約を簡潔に記述することを可能とし、これにより文字列認識装置が容易に様々な認識対象に対応することを可能にすることである。本発明が解決しようとする第３の課題は、文字の空間的配置を文字列の表記のし方と結びつけて扱い、文字列を高い精度で認識することを実現することである。
【００１４】
【課題を解決するための手段】
本発明の文字列認識装置では、数字の文字列の知識を文脈自由文法で記憶する手段を設ける。これにより、数字を中心とする文字列の表記上の制約が簡潔に表現できる。さらに上昇型構文解析法を利用した文字列照合手段を設け、高速かつ高精度に文字識別識別結果を文字列として解釈することを実現する。さらに、文脈自由文法における記号列同士の書換えの規則に併せて文字の空間的配置の制約を記憶する手段を設けるとともに、置換え規則を適用する際に文字の空間的配置が妥当かどうか判定する手段を設ける。
【００１５】
文脈自由文法は、記号列同士の書換えの規則（生成規則）により文字列の表記上の制約を表現するものである。これを利用し、数字と「，」「￥」などの組合せを文法的に定義することにより、数字を中心とした文字列の表記上の制約を簡潔に表現することができる。
【００１６】
また、文字識別結果の解釈の際に用いる上昇型構文解析法は、部分的な記号列を生成規則にしたがって上位の記号に繰返し書換えていくことにより、文字識別結果から最適な文字列の解釈を見い出す方式である。
【００１７】
類似の方式は音声認識の分野ではＣＹＫ法（文献６：中川「確率モデルによる音声認識」電子情報通信学会）として知られている。この方式は、文法的に許容される文字列の組合せの数が多い場合にも、効率よく最適な文字列を選択でき、高精度かつ高速に文字識別結果を解釈できる。もともとこの方式は音声信号のような１次元の入力を対象にしていた。本発明では文字の切出し方を後述する切出し仮説ネットワークと称するネットワークの形式で表現することにより、画像のような２次元の入力を扱えるよう工夫した。
【００１８】
本発明では、さらに生成規則の表記法を工夫し、ある記号列を別の記号に書換える際に、その記号列を構成する文字が満たす空間的配置の制約を記憶できるようにした。これにより、文字列照合処理またはその後段の処理で文字の空間的な配置を検査し、認識精度を高めることを可能とした。
【００１９】
【発明の実施の形態】
本発明の実施形態の一例を図１に示す。本実施例は、文法の人手による作成を支援する文法登録装置１０１、与えられた文法を利用して文書１０４上の文字列を認識する文字列認識装置１０２からなる。
【００２０】
文法登録装置１０１で人手で作成した文法のデータは、通信回線１０３を介して文字列認識装置１０２に送信する。また、ＦＤ（フロッピーディスク）などの記憶媒体を介して複写してもよい。
【００２１】
文法登録装置１０１は通信装置１１０、プロセッサ１１２、ＦＤドライブ１１４、ディスク装置１１５、メモリ１１３、表示装置１１６、キーボード１１７、マウス１１８をバス１１１で接続したものである。
【００２２】
通信装置１１０は通信回線１０３に接続され、文字列認識装置１０２との通信を司る。プロセッサ１１２は文法登録装置１０１全体の制御、文法の作成を支援するプログラム類の実行などを司る。プログラムファイル群１２０と作成した文法情報辞書ファイル１２１はディスク装置１１５に格納し、システム起動時にメモリ１１３に読込む。
【００２３】
人手による文法の編集は、文法辞書編集プログラム１２３により行う。これは、メモリ１１３に格納した文法辞書テーブル１２５内のデータの表示／編集、ディスク装置１１５からの読込み、ディスク装置１１５への書込みなどの機能を有する。編集を行う人は、表示装置１１６に表示された内容を確認しながらキーボード１１７、マウス１１８などの入力装置を用いて入力を行う。
【００２４】
また、編集の過程を支援するため、文法辞書テーブル１２５に格納した文法からどのような文字列が生成されるかを例示する例示プログラム１２４もメモリ１１３に格納しておく。この例示プログラム１２４は文法が妥当かチェックも併せて行う。さらに、作成作業の際の参考にするため、過去の文法の事例を登録してある文法事例ファイル１２２もディスク装置１１５に格納する。ＦＤドライブ１１４は、ＦＤを用いて文法を文字列認識装置１０２に複写する際などに用いる。
【００２５】
文字列認識装置１０２は、通信装置１３０、プロセッサ１３２、スキャナ１３６、ＦＤドライブ１３４、ディスク装置１３５、メモリ１３３をバス１３１で接続したものである。プロセッサ１３２は文字列認識装置１０２全体の制御、文字列認識のプログラム類の実行などを司る。プログラムファイル群１６０と文法登録装置１０１で作成した文法情報辞書ファイル１６１はディスク装置１３５に格納し、システム起動時にメモリ１３３に読込む。
【００２６】
文法登録装置１０１で作成した文法は、通信回線１０３を介して通新装置１３０によりディスク装置１３５に格納するか、あるいはＦＤドライブ１１４を用いてＦＤから複写する。読取り対象の文書１０４はスキャナ１３６により光電変換して入力画像として取込み、メモリ１３３に格納する。入力画像としては通常２値画像を用いる。本明細書でも特に断りがない限り、画像は２値画像であるものとする。
【００２７】
メモリ１３３には、後述するプログラム群、すなわちフィールド切出しプログラム１４１、切出し仮説生成プログラム１４２、構文解析プログラム１４３、標準化プログラム１４４、検定プログラム１４５などを格納する。さらに、メモリ１３３には、文法情報を格納する標準型生成規則テーブル１５０の他に、後述するフィールド画像テーブル１４７、切出し仮説テーブル１４８、構文要素ラティステーブル１４９、文候補テーブル１５１、認識結果テーブル１５２を設ける。
【００２８】
本発明の認識対象である文書１０４の一例を図２に模式的に示す。本実施例での読取り対象の文書は、枠線で領域が区切られた帳票である。区切られた枠の一つ２０１に読取り対象の文字列を記入するよう定められており、枠の座標は予め分かっているものとする。
【００２９】
本発明で数字文字列の表記の規則を表すために用いる文法は、つぎの数１のような形で表される（文献７：Ｊ．Ｅ．ホップクロフト他「言語理論とオートマトン」サイエンス社、ＩＳＢＮ−７８１９−０２５０−２）。
【００３０】
【数１】
0004006176.tif 000002
【００３１】
ここでは、数字および「￥」「，」「−」など、実際に数字文字列中で用いられている文字が終端記号にあたり、それ以外の構文要素（文献によっては文法的類ともいう）が非終端記号にあたる（上記文献７のｐ．１１参照）。生成規則は記号列の生成の規則を表すものである。すなわち、数１中の「→」の左辺の記号から右辺の記号列が生成できることを表している（上記文献７のｐ．１０参照）。
【００３２】
本発明では文脈自由文法を用いるため、左辺は必ず１つの変数となり、また右辺は空文字列であってはならない。さらに文法的に妥当な文字列（「￥１，２３４−」など）が文開始記号にあたる。以下、終端記号には小文字のアルファベット、非終端記号もしくは終端記号を表す変数には大文字のアルファベット、変数の列にはギリシャ文字を用いる。
【００３３】
本発明で用いる文法情報辞書ファイル１２１には、図３に示すようなテキストデータを用いる。ここでは、「：：＝」は前記数１で置換えを意味する「→」に相当し、各行が１つの生成規則に対応する。また終端記号は常に１文字の単語、非終端記号は２文字以上の単語とし、単語および「：：＝」の間は空白で区切る。例えば、図３の１０行目では、記号Ｂｉｎｚｎ（３０１）と記号列「Ｎｚｄ  ０」（３０３）が記号「：：＝」（３０２）で結び付けられており、前者から後者が生成できることを示している。また、このテキストデータで最後、すなわち図３の例では最終行に表れた非終端記号を文開始記号とみなす。この場合は「ａｍｔ」が文開始記号となる。
【００３４】
本発明で用いる文法情報辞書ファイル１２１には、上述のような文法情報と併せて、文字の配置に関する情報を３０４のような形式で格納する。これは、各生成規則を適用する際に、元の文字列に含まれる文字が満たすべき空間的配置に関する制約条件を表している。例えば３０４でａｉ（ｉは１，２，３，……）は「：：＝」の右辺の第ｉ項を表し、「ｅｑｐｓ（ａ１，ａ２）」は、ａ１およびａ２に含まれる文字（すなわち、終端記号に対応する部分画像）のサイズとピッチがほぼ等しいことを表している。ここで用いられる記号類の意味は図１８に示してある。
【００３５】
本発明の文字列認識における処理の流れを図１および図４のデータフロー図で説明する。文字列認識処理４０２は文字列認識装置１０２で実現される処理である。文字列認識処理４０２は、文法情報４０１（図１の文法情報辞書ファイル１６１に格納する）とスキャナ１０４で取り込んだ画像を入力とし、認識結果の文字列を出力とする。文法情報４０１は文法情報編集４００にて予め人手で編集する。文法情報編集４００は図１の文法登録装置１０１にて実現する。
【００３６】
まず、フィールド切出し４０３は、入力画像から読取り対象の領域（読取りフィールド）の画像を切出し、フィールド画像テーブル１４７に出力する処理で、フィールド切出しプログラム１４１にて実現する。切出し仮説生成４０４は、フィールド画像を解析し、大きさ、形状などの情報に基づいて文字として尤もらしい部分画像（候補パタン）を検出する処理で、切出し仮説生成プログラム１４２にて実現し、その結果は後述する切出し仮説ネットワークの形式で切出し仮説テーブル１４８に格納する。
【００３７】
標準化処理４０６は入力の文法情報４０１を後の処理で用いやすい標準型に変換する処理で、標準化プログラム１４４で実現し、結果は標準型生成規則テーブル１５０に格納する。
【００３８】
構文解析４０５は標準化した生成規則と、切出し仮説ネットワークを入力とし、文字識別４０７を利用して文字列を認識する処理で、構文解析プログラム１４３で実現する。また、尤もらしい文開始記号が得られたなら、この文開始記号に対応する文字列の情報などを文候補と称するデータの形式で文候補テーブル１５１に出力する。
【００３９】
検定処理４０８は、得られた文候補が妥当かどうかをさらに詳細に調べ、妥当なものの中からさらに最も確からしいものを認識結果として認識結果テーブル１５２に出力する処理で、検定プログラム１４５で実現する。
【００４０】
つぎに、切出し仮説生成４０４、標準化４０６、文字識別４０７、構文解析４０５、検定４０８の処理について、順をおって説明する。
【００４１】
切出し仮説生成４０４は、フィールド画像を解析し、大きさ、形状などの情報に基づいて文字として尤もらしい部分画像（候補パタン）を検出する処理である。この段階では一意に文字の切出し方を特定できない場合が多い。このため、切出し仮説生成４０４では複数の文字の切出し方の仮説に基づいて候補パタンを検出しておき、後段の処理で正しいものを選択するようにする。
【００４２】
例えば、図２の入力画像の枠２０１の部分を切出して得られる図５に示すフィールド画像からは、図６に示すような候補パタンが検出できる。図５に示すように、フィールド画像には読取り対象以外の文字や汚れも混入することが避けられない。これらの候補パタンの集合は図６に示すようなネットワークで表現できる。以下、このようなネットワークを切出し仮説ネットワークと呼ぶ。
【００４３】
切出し仮説ネットワーク上では、検出された候補パタンが辺、候補パタンの境界が節点で表現されている。また、フィールド中の文字の切出し方の仮説は、切出し仮説ネットワーク中の経路で表現される。
【００４４】
切出し仮説ネットワーク上の候補パタン境界には、整数の識別子を付与する。各候補パタンはつぎの数２のような形式で表現する。また、切出し仮説ネットワーク全体は数３のように表される。
【００４５】
【数２】
0004006176.tif 000003
【００４６】
【数３】
0004006176.tif 000004
【００４７】
標準化処理４０６は、入力の文法情報を後の処理で用いやすい標準型に変換する処理である。ここでの標準形とは、生成規則の右辺が１つの終端記号もしくは２つの記号となっているものである。任意の文脈自由文法Ｇはこのような標準形（Chomskyの標準形）に変換できる（上記文献７のＰ．５６参照）。
【００４８】
図７に、図３から標準型に変換された生成規則の例を示す。なおこの際、空間的配置に関する制約の記述も生成規則と併せて変換する。変換は、以下のように行う。
【００４９】
・標準化した生成規則に関する空間的配置の記述があれば、それをそのまま標準化した生成規則に付加する。
【００５０】
・空間的配置が「ｅｑｐｓ（ａ１，ａ２，ａ３）」のように３つ以上の引き数をもつ関数で表されている場合には、これを２項ずつの記述「ｅｑｐｓ（ａ１，ａ２）」「ｅｑｐｓ（ａ２，ａ３）」に分割し、それぞれに対応する生成規則に付加する。
【００５１】
文字識別４０７は候補パタンを入力とし、尤もらしい終端記号とその評価値を求める処理で、文字識別プログラム１４６で実現する。森「パターン認識」（文献８：ＩＳＢＮ４−８８５５２−０７５−４  Ｃ３０５５、電子情報通信学会）のような方式をここに用いることができる。この段階で尤もらしい終端記号を一意に決定できない場合も多い。このような場合には、終端記号と評価値の対を複数出力する。
【００５２】
つぎに図８から図１４を用いて、構文解析４０５の処理手順を説明する。
【００５３】
図８は構文解析４０５の処理の概略を示すデータフローチャートである。構文解析４０５は、前記従来の技術の項で述べた（３）の文字列照合に相当する処理を司る。
【００５４】
まず、各候補パタンを終端記号として文字識別４０７を利用して評価し、確からしさを求める（８０１）。処理の過程は構文要素ラティスと称する形式で構文要素ラティステーブル１４９に記憶する。
【００５５】
つぎに、得られた構文要素の候補同士の組合せを、標準化した生成規則と照らし合せて評価する（８０２）。この照合処理は、新たな構文要素が見い出されなくなるまで繰り返す。つぎに、得られた構文要素の候補の中に文開始記号が含まれていたなら、これら文開始記号に対応するデータ（文候補）を出力する（８０３）。もし文開始記号が含まれていなければＮＵＬＬポインタを出力する。
【００５６】
候補構文要素はつぎの数４のような形式であらわされる。
【００５７】
【数４】
0004006176.tif 000005
【００５８】
ｌｆｔとｒｉｔは、候補構文要素同士の境界の識別子である。左側の境界の識別子がｌｆｔ、右側の境界の識別子がｒｉｔとする。αは候補構文要素に対応する記号である。ｆは文字識別結果などに基づくこの候補構文要素の確からしさの値である。
【００５９】
αが終端記号の場合には、ｃｓｅＬとｃｓｅＲにそれぞれＮＵＬＬポインタ（メモリアドレスとしてあり得ない値）を代入し、ｐｔｎには対応する候補パタンへのポインタを代入する。この際、ｌｆｔとｒｉｔの値はそれぞれｐｔｎのｌｆｔとｒｉｔと同じ値とする。ｆには文字識別の結果得られる評価値を代入する。αが非終端記号の場合はｃｓｅＬとｃｓｅＲにそれぞれ生成規則の右辺の記号に対応する候補構文要素へのポインタを代入し、ｐｔｎにはＮＵＬＬポインタを代入し、ｌｆｔの値はｃｓｅＬのｌｆｔの値と等しくする。
【００６０】
この際、ｃｓｅＲがＮＵＬＬの場合は、ｒｉｔの値はｃｓｅＬのｒｉｔの値と等しくする。例として、終端記号から生成された候補構文要素（「ｙｅｎ」「ｚｒ」などの非終端記号）群を後に説明する図１３の破線１３０３から１３０４の間に模式的に示す。またｃｓｅＲがＮＵＬＬでない場合は、ｒｉｔの値はｃｓｅＲのｒｉｔの値と等しくする。
【００６１】
構文要素ラティスは、候補パタンネットワークと同様につぎの数５のような形式で表される。
【００６２】
【数５】
0004006176.tif 000006
【００６３】
図１３に、構文要素ラティスの例を模式的に示す。候補パタンネットワーク１３０１上の候補パタンに対応する終端記号の候補構文要素群が破線１３０２と１３０３の間に示してある。また、これら終端記号から見い出された非終端記号が１３０３と１３０４の間に示してある。また、非終端記号の対から登録された候補構文要素群を破線１３０４以下に模式的に示してある。
【００６４】
終端記号の評価（８０１）の処理手順を図９に示す。以下、詳細な処理手順の説明にはアクションダイアグラム（文献９：Ｊ．マーチン「ソフトウエア構造化技法」近代科学社、ＩＳＢＮ４−７６４９−０１２４−２  Ｃ３０５０  Ｐ５５６２Ｅ）を用いる。
【００６５】
ここで、前記数４のｃｓｅのように、複数の要素を持つ変数の特定の要素、例えばｌｆｔを表すには、演算子「．」を用い「ｃｓｅ．ｌｆｔ」のように表すものとする。また、「ｃｓｅ＝（ａ，ｂ，ｃ，ｄ，ｅ，ｆ）」のような表記は、ｃｓｅの各要素にａ，ｂ，ｃ，ｄ，ｅ，ｆを代入することを表すものとする。また「＋＋」は、ある変数の値に１を加算することを示す。
【００６６】
まず、処理の冒頭で登録済み候補構文要素を表す変数ｍの値を０に初期化する。つぎに全ての候補パタンの終端記号としての確からしさを関数ｆで評価する。もしｆの値が基準値ｔｆを超えていればｍの値に１を加算し、この構文要素を候補構文要素の配列ｃｓｅのｍ番目に格納する（９０１）。
【００６７】
この際のｆの評価には文字識別４０７を用いる。つぎに、ｃｓｅに格納したｍ個の候補構文要素各々に関し、記号α（この場合αは全て終端記号）が生成される生成規則が生成規則の集合Ｐにあるかどうかを調べる（９０２）。もしあればｍの値に１を加算し、この生成規則の左辺にあたる候補構文要素に対応する情報をｃｓｅのｍ番目に格納する。
【００６８】
非終端記号の評価（８０２）は、構文要素ラティス中から生成規則で生成される候補構文要素の対を見い出し、この対に対応する候補構文要素を追加していくことを繰返す処理である。この際、処理の手順には以下のような工夫がなされている。
【００６９】
・前回および前々回の繰返し時点での登録済み候補構文要素数ｍ０，ｍ１を参照し、新たな構文要素が追加できたを判定。追加がなければ繰返しを終了する。
【００７０】
・構文要素ラティス上の同じ範囲に複数の候補構文要素がある場合には（すなわちｌｆｔとｒｉｔの値が各々同じ候補構文要素が複数ある場合には）、動的計画法の原理を用い、これらのうちで最も評価値が高いもののみを用いる。
【００７１】
非終端記号の評価（８０２）の処理手順を図１０で説明する。まず処理の冒頭でｍ０，ｍ１をそれぞれ０とｍに初期化する。つぎにループ１００１の中で構文要素ラティス中で隣り合っている（すなわち一方のｌｆｔともう一方のｒｉｔが同じ値になっている）対を全て見い出し（１００２）、さらにこの対を生成する生成規則が標準化生成規則中にないかを調べる（１００３）。
【００７２】
もし該当する生成規則があり、さらにこの候補構文要素の対のいずれかがループ１００１の前回の繰返し以降で登録されたものなら（１００４）、この組合せの評価値を計算し、変数ｆに格納する。ここでは組合せ確からしさとして、２つの候補構文要素の評価値ｆの和を用いる。この際、標準化生成規則に併せて記憶してある文字の空間的配置に関する制約条件を参照し、これを満たさない場合には評価値を０とし、後段の処理でこの部分が低く評価されるようにする。
【００７３】
さらにこの候補構文要素の対と範囲が同じ候補構文要素がすでに登録されていないかどうかを調べる（１００５）。登録されていた場合には、新しい対の方が以前からある候補構文要素より評価値が高い場合にのみ、新しい対に対応する候補構文要素の情報をｃｓｅのｍ番目の要素に格納する。この際、ｍ１以降に登録された候補構文要素で、１００５の判定を満たすものがあるかどうかを判断し（１００６）、あればその候補構文要素に新たな候補構文要素を上書きする。なければｍに１を加算し、配列ｃｓｅのｍ番目に新たな候補構文要素の情報を格納する。１００５の判定で該当する候補構文要素が登録されていない場合には、無条件でｍに１を加算し新しい対に対応する候補構文要素の情報をｃｓｅのｍ番目の要素に格納する。
【００７４】
ループ１００１の最後で、新たに候補構文要素が追加されたかどうかを判定し、追加されていればループ１００１を終了する（１００７）。されていなければ変数ｍ０，ｍ１を更新し、再度繰返しを実行する。
【００７５】
つぎに、図１１により認識結果出力８０３の処理手順を説明する。まず、処理の冒頭で文候補数を表す変数ｃを０に初期化する。つぎに全ての候補構文要素を調べ、文開始記号に対応するものがないかどうか調べる（１１０１）。もしあれば、ｃに１を加算し、関数ｒｅｃｏｖｅｒＳｔｒを呼び出して文開始記号に対応する文字列を再構成し、文候補数ｃを１加算し、候補構文要素や文字列の情報を文候補の配列ｃｎｄのｃ番目の要素に格納する。
【００７６】
ここで、文候補はつぎの数６の形式で表されるデータである。
【００７７】
【数６】
0004006176.tif 000007
【００７８】
文字列再構成の関数ｒｅｃｏｖｅｒＳｔｒの処理手順を図１２に示す。関数ｒｅｃｏｖｅｒＳｔｒは、候補構文要素ｃｓｅ文字ｎの配列ｓｔｒを引き数とし、ｓｔｒにｃｓｅに対応する終端記号の列を格納する関数である。まず、ｃｓｅに対応する記号を調べ、もし終端記号であればこの終端記号を文字列の末尾に追加して処理を終了する。もし、終端記号でなければ、候補構文要素ｃｓｅ．ｃｓｅＬ、ｃｓｅ．ｃｓｅＲを引き数としてｒｅｃｏｖｅｒＳｔｒを再帰的に呼び出す。この際、常にｃｓｅ．ｃｓｅＬを先にｒｅｃｏｖｅｒＳｔｒに渡してｒｅｃｏｖｅｒＳｔｒを呼び出すことにより、正しい順序で文字列がｓｔｒに格納されることになる。
【００７９】
図１３は、構文解析４０５で候補構文要素が登録される過程を模式的に示したものである。１３０１は入力となる候補パタンネットワークを模式的に示す。これから図１０におけるループ１００１の第１回目の繰り返しで登録された候補構文要素を破線１３０２と１３０３の間に示す。以下同様に２回目、３回目の繰返しで登録した候補構文要素が破線１３０３以下に示してある。最終的に登録された文開始記号Ｓに対応する候補構文要素は破線１３０５の下に示してある。
【００８０】
図１４は、文開始記号Ｓに対応する候補構文要素１４０２、１４０３を登録するのに寄与したもの候補構文要素のみに注目し、それらの関係を模式的に表したものである。図中の点線矢印は、候補構文要素を登録する際にどのように生成規則を適用したかを示す。例えば、矢印１４０４と矢印１４０５は、候補構文要素１４０６を登録する際、候補構文要素１４０７と１４０８を参照してｙｎｒ→ｙｅｎ  ｂｉｎｚｎという生成規則を適用したことを示している。
【００８１】
検定処理４０８は構文解析４０５で検出した文候補が妥当な文字列となっているか、さらに詳細に検定する処理である。検定処理４０８の処理の概略を図１５に示す。入力は単数もしくは複数の文候補である。まず、各文候補の元になる候補パタンの位置、大きさの関係が妥当かどうか判定する（１５０１）。もし妥当でなければ、当該文候補を削除する。
【００８２】
つぎに、得られた文字列の内容が妥当かどうか、検定する。ここでは例えば金額の値が異常に大きかったり小さかったりしないかなどを調べ、もし妥当でなければ、当該文候補を削除する（１５０２）。最後に、残った文候補の中から最も評価値が大きいものを選択し、出力する（１５０３）。もし、一つも文候補が残らなかったなら、空文字列を出力する。
【００８３】
配置検定処理の対象の一例を図１６（Ａ）に示す。ここでは、文候補１６０１が候補構文要素１６０２と１６０３から見い出されたものｔであるとする。通常は数字や「￥」などの中央附近にあるべき「−」が、この例では上の方に位置している。検定処理はこうした配置情報の異常を検出し、不正があれば当該文候補を削除する。こうした判定の際には、標準化辞書中に格納された空間的配置に関する制約条件を利用する。
【００８４】
また、図１６（Ｂ）の例で、文字識別が候補パタン１６０４を「，」と識別（すなわち「，」とみなすことに対し文字識別が高い評価値を出力）としたとする。この場合、本来下にあるべきが「，」が上の方にあるため、検定処理はこのように１６０４を「，」とみなす解釈を含む文候補を削除する。
【００８５】
また、同じく図１６（Ｂ）において候補パタン１６０４「１」と文字識別が識別したが他の文字と比べて極端に小さい場合、図１６（Ｃ）において候補パタン１６０５（破線でかこわれている部分）を文字識別が「３」と識別したが他の文字より極端に大きい場合などが、検定で文候補を削除する対象となる。
【００８６】
以上の実施例では、ＣＹＫ法にならい、生成規則を一旦標準化してから構文解析４０５を実行する。一方、標準化せずに構文解析を行うことも可能である。この場合、長さが３以上の記号列を生成する生成規則を、候補構文要素の登録の際に用いることができる。このため、標準化した生成規則を用いる際に比べ、不要な候補構文要素を少なくすることができる。
【００８７】
標準化しない生成規則を構文解析４０５で用いるためには、候補構文要素をつぎの数７のような形式に改める必要がある。
【００８８】
【数７】
0004006176.tif 000008
【００８９】
ここで｛ｃｓｅ１，ｃｓｅ２，，，ｃｓｅｌ｝は生成規則右辺に対応する候補構文要素の列である。これは、前記数４で生成規則右辺に対応する候補構文要素を表していたｃｓｅＬとｃｓｅＲに代わるものである。
【００９０】
処理手順に関しては、終端記号の評価８０１、認識結果出力８０３はそれぞれ図９、図１０の説明のとおりでよい。非終端記号の評価は図１７のような処理手順となる。ここでは説明を簡単にするために、動的計画法に基づく絞り込み（図１０では処理ブロック１００５）を行わない処理を例としている。
【００９１】
まず、ループ１７０１の冒頭で前回繰り返し時点の候補構文要素数ｍ０をｍに代入する。つぎに、生成規則に対応する連続した候補構文要素の列が存在するかどうかを調べる（１７０２）。存在すれば、ｍを１加算し、この候補構文要素の列に対応する新たな候補構文要素を配列ｃｓｅのｍ番目に登録する。ループ１７０１の最後で、もしｍ０＝ｍであれば、すなわちその繰り返しで新たに登録された候補構文要素がなければ、ループを終了する。
【００９２】
図１８は、文法情報辞書ファイル内の記述で言語空間的配置の制約条件を表す関数の意味を示す。
【００９３】
「（  ）」は、当該の生成規則に関し、空間的配置に関する制約がないことを示す。「ｅｑｓ（ａ１，ａ２，，，ａｎ）」は、文字の上端と下端が揃っているかどうかを判定する関数で、ａ１，ａ２，，，ａｎに含まれる文字の上端および下端の座標の最大値と最小値の差が、文字高さの平均の２０％以内であれば真を、そうでない場合には偽となる。
【００９４】
「ｅｑｓｐ（ａ１，ａ２，，，ａｎ）」は、文字のピッチが揃っているかどうか判定する関数で、ｅｑｓ（ａ１，ａ２，，，ａｎ）の条件に加え、ａ１，ａ２，，，ａｎに含まれる文字の重心間の距離の最大値と最小値の差が、平均値の２０％以内であれば真を、そうでない場合には偽となる。
【００９５】
「ｓｍａｌｌ（ａ）」は文字ａが「，」などのように小さい文字かを判定する関数で、ａの（下端から上端まで）の値が、それ以外の文字の平均の４０％以下であれば真を、そうでない場合には偽となる。
【００９６】
「ｌｏｗｅｒ（ａ）」は文字ａが「，」などのように文字行の下の方にある文字かを判定する関数で、ａの上端の値とａ以外の文字の上端の平均の値の差が、ａ以外の文字の高さの平均の４０％以下であれば真を、そうでない場合には偽となる。
【００９７】
「ｍｉｄｄｌｅ（ａ）」は文字ａが「ー」などのように文字行の中の辺りの高さにある文字かを判定する関数で、ａの重心のＹ座標値とａ以外の文字の重心の平均のＹ座標値の差が、ａ以外の文字の高さの平均の４０％以下であれば真を、そうでない場合には偽となる。
【００９８】
「ｎｍｒ（ａ）」は、ａを構成する文字から数字のみを取り出して、他の関数に渡すための関数である。
【００９９】
【発明の効果】
数字の文字列の知識を文脈自由文法で記憶する手段を設けることにより、数字を中心とする文字列の表記上の制約が簡潔に表現できる。また、上昇型構文解析法を利用した文字列照合手段により、高速かつ高精度に文字識別識別結果を文字列として解釈することを実現できる。さらに、文脈自由文法における記号列同士の書換えの規則に併せて文字の空間的配置の制約を記憶する手段を設けるとともに、置換え規則を適用する際に文字の空間的配置が妥当かどうか判定する手段を設けることにより、より高精度で文字列の認識が可能となる。
【図面の簡単な説明】
【図１】本発明の一実施例におけるハードウエアの構成例を示すブロック図。
【図２】読み取り対象の文書の例を示す図。
【図３】文法情報辞書ファイルの例を示す説明図。
【図４】本発明の文字列認識のデータフローの例を示す流れ図。
【図５】本発明におけるフィールド画像の例を示す図。
【図６】切出し仮説ネットワークの例を示す図。
【図７】数字文字列の標準化された生成規則の例を示す説明図。
【図８】構文解析のデータフローの例を示す流れ図。
【図９】終端記号の評価の処理手順の例を示す図。
【図１０】非終端記号の評価の処理手順の例を示す図。
【図１１】認識結果出力の処理手順の例を示す図。
【図１２】文字列再構成関数の処理手順の例を示す図。
【図１３】候補構文要素の登録の過程の例を示す説明図。
【図１４】候補構文要素の登録の過程の例を示す図。
【図１５】検定処理のデータフローの例を示す流れ図。
【図１６】配置検定の対象の例を示す説明図。
【図１７】標準化しない生成規則を用いた非終端記号評価処理手順の例を示す図。
【図１８】空間的配置の制約を表す関数の例を示す説明図。
【符号の説明】
１０１…文法登録装置、１０２…通信回線、１０３…文字列認識装置、１０４…認識対象の文書、４０５…構文解析、４０６…検定。
【図１】
0004006176.tif 000009
【図２】
0004006176.tif 000010
【図３】
0004006176.tif 000011
【図４】
0004006176.tif 000012
【図５】
0004006176.tif 000013
【図６】
0004006176.tif 000014
【図７】
0004006176.tif 000015
【図８】
0004006176.tif 000016
【図９】
0004006176.tif 000017
【図１０】
0004006176.tif 000018
【図１１】
0004006176.tif 000019
【図１２】
0004006176.tif 000020
【図１３】
0004006176.tif 000021
【図１４】
0004006176.tif 000022
【図１５】
0004006176.tif 000023
【図１６】
0004006176.tif 000024
【図１７】
0004006176.tif 000025
【図１８】
0004006176.tif 000026