(57)【要約】【課題】文字切出や文字認識の不確定さを伴う文字列認識において、文字列の品質低下に対するロバストな文字列認識処理を提供する。【解決手段】文字切出や文字認識の不確定さを文字列仮説と呼ばれる有向グラフとしてモデル化する。準正規表現に基づいて定義された表記文法と、文字パタンの配置を規定する文字パタン配置辞書を用い、文字列仮説を、文法駆動と半順序構造に対応したビタビアルゴリズムにより解析することで、読取結果である文字列テキストを確定する。文法駆動に対応するためにビタビアルゴリズムをスタック計算方式に拡張し、更に半順序構造に対応するために変数縮約を用いたコスト関数の構造変形処理を採用する。これにより読取対象画像の劣化（ノイズ混入、文字欠落、接触等）に対してロバストな文字列表記解析を実現する。【選択図】図４
2010061403.tif 000002
【特許請求の範囲】
【請求項１】
文書画像データに文字認識処理を実行する文字認識装置であって、
文書画像データを入力する画像入力部と、
文書構造解析に用いられる文書構造辞書と、
文字識別に用いられる文字識別辞書と、
前記文書構造辞書を用いて、前記文書画像データの構造を特定する文書構造解析部と、
前記文字識別辞書を用いて、前記文書構造が特定された文書画像データについて文字認識処理を行い、文字切出パタン候補及び文字切出パタンの識別結果を含む文字列仮説を生成する文字列仮説生成部と、
前記文字列仮説に対して半順序構造に対応したビタビアルゴリズムを適用して、認識された文字列を確定する表記解析部と、
を備えることを特徴とする文字認識装置。
【請求項２】
さらに、準正規表現で定義され、表記される文字列の形態を格納する表記文法辞書と、
文字配置に関する制約条件を格納する文字配置辞書と、を含み、
前記表記解析部は、前記表記文法辞書に含まれる文字列表記文法を前記ビタビアルゴリズムによって解析して、前記文字列仮説によって示される文字認識結果の候補を確定することを特徴とする請求項１に記載の文字認識装置。
【請求項３】
前記表記解析部は、文字列を準正規表現のうち、候補単語を単純に列挙する単語列挙型表記以外の表記方式を前記ビタビアルゴリズムによって解析することを特徴とする請求項２に記載の文字認識装置。
【請求項４】
前記表記解析部は、前記文字列表記文法を解釈する過程において、スタックを用いて表記解析結果を逐次展開することにより、動的計画法におけるコスト計算の計算量を削減することを特徴とする請求項３に記載の文字認識装置。
【請求項５】
前記表記解析部は、前記半順序構造に対応したビタビアルゴリズムによって解析する場合に、前記文字列仮説を半順序構造のコスト関数として表現し、該半順序構造のコスト関数を変数縮約によって順序構造に変換して計算することによって、前記文字列認識結果の候補を確定することを特徴とする請求項１に記載の文字列認識装置。
【請求項６】
文書画像データに文字認識処理を実行する文字認識方法であって、
文書構造解析部が、文書構造解析に用いられる文書構造辞書を用いて、画像入力部から入力された文書画像データの構造を特定するステップと、
文字列仮説生成部が、文字識別に用いられる文字識別辞書を用いて、前記文書構造が特定された文書画像データについて文字認識処理を行い、文字切出パタン候補及び文字切出パタンの識別結果を含む文字列仮説を生成するステップと、
表記解析部が、前記文字列仮説に対して半順序構造に対応したビタビアルゴリズムを適用して、認識された文字列を確定するステップと、
を備えることを特徴とする文字認識方法。
【請求項７】
前記表記解析部は、準正規表現で定義され、表記される文字列の形態を格納する表記文法辞書に含まれる文字列表記文法を前記ビタビアルゴリズムによって解析して、前記文字列仮説によって示される文字認識結果の候補を確定することを特徴とする請求項６に記載の文字認識方法。
【請求項８】
前記表記解析部は、文字列を準正規表現のうち、候補単語を単純に列挙する単語列挙型表記以外の表記方式を前記ビタビアルゴリズムによって解析することを特徴とする請求項
７に記載の文字認識方法。
【請求項９】
前記表記解析部は、前記文字列表記文法を解釈する過程において、スタックを用いて表記解析結果を逐次展開することにより、動的計画法におけるコスト計算の計算量を削減することを特徴とする請求項８に記載の文字認識方法。
【請求項１０】
前記表記解析部は、前記半順序構造に対応したビタビアルゴリズムによって解析する場合に、前記文字列仮説を半順序構造のコスト関数として表現し、該半順序構造のコスト関数を変数縮約によって順序構造に変換して計算することによって、前記文字列認識結果の候補を確定することを特徴とする請求項６に記載の文字列認識方法。
【請求項１１】
請求項６に記載の文字認識方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文字列認識装置及び方法、並びにプログラムに関し、例えば、紙の文書をＯＣＲ装置等によって読み取り、読み取った文書を認識する技術に関するものである。
【背景技術】
【０００２】
法令遵守や文書電子化などの社会的な要求から、様々な業務文書を電子画像として保存し、これを読取る文書読取システムが社会的に求められている。一般に、このようなプロセスを遂行するためにはＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅｃｏｇｎｉｔｉｏｎ）装置が用いられる。すなわち、ＯＣＲ装置を用いて文書を読取り、ＯＣＲ読取結果を修正インタフェース上に表示し、当該読取結果に存在する読取誤りや読取欠損を人手で修正するという一連のプロセスによって、様々な業務文書を電子画像及び読取結果であるテキストとして保存する。
【０００３】
このとき、ＯＣＲ装置及び文書読取システムにとっての重要な課題は、様々なバリエーションのある文書に対する読取精度を高めることである。そのためには文字切出や文字認識の不確定さを判定する処理が必要となる。読取誤りや読取欠損を人手で修正するのでは煩雑であり、処理速度及びコスト面からも実用的ではない。
【０００４】
文字列認識における文字切出及び文字認識の不確定さを補い、文字列画像を文字列テキストに精度良く変換するための手法としては、例えば、文字列表記解析処理が広く使われている。そのアルゴリズムとしては、形態素解析、ＲＴＮ照合（再帰遷移ネットワーク照合）、上昇型構文解析などを使った表記文法の解析が一般的である。
【０００５】
ＯＣＲ装置の一般的な機能及び、それを用いた帳票入力業務の形態については、様々な技術が提案されている。
【０００６】
例えば、特許文献１には、ＯＣＲ装置内の基本的な処理の流れが述べられている。より具体的には、帳票の自動読取りを行う場合、帳票内に記載されている文字コード、文字行、罫線、枠等を抽出し、データ入力が必要な帳票上の特定領域の読取りを行い、これをテキストファイルとして外部記憶装置に出力することが開示されている。
【０００７】
また、特許文献２には、ＯＣＲの読取精度を向上する手段として、ＯＣＲの認識結果に形態素解析を適用する手法が示されている。
【０００８】
さらに、特許文献３には、手書き数字列に対して上昇型構文解析を使った文字列表記解析処理が提案されている。一般に上昇型構文解析は下降型構文解析に比べて計算量が削減できるとされており、数字列等の表記が単純な規則で表現できるものに対して多く適用されている。
【０００９】
いずれの文献も、ＯＣＲ装置を使って、紙文書あるいは文書画像上のデータを読取り精度を向上するための技術を提案している。
【００１０】
一方、ビタビアルゴリズムを用いた照合アルゴリズムは音声認識や文字認識の分野で、解の最適性を保証するロバストなアルゴリズムとして広く利用されている。例えば特許文献４では、音声認識に動的計画法を使って認識を行う手法が提案されている。
【００１１】
【特許文献１】特開平０６−５２１５６号公報
【特許文献２】特開平０５−１０８８９１号公報
【特許文献３】特開２００２−１１７３７４号公報
【特許文献４】特開平７−２１９５７８号公報
【特許文献５】特開平０９−３１９８２４号公報
【特許文献６】特開２０００−２５１０１２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、従来の手法では、形態素解析などのように、表記文法を横型探索で辿り、その解釈結果を解析木として残すため、探索空間の制約などから、文字誤不読や表記文法の不完全さに影響を受けて表記解析が失敗に陥りやすい、また解の最適性が保証されないという問題がある。例えば、特許文献２の方法によれば、確かに、形態素解析等の知識処理を行うことで誤読を訂正することは可能であるが、それでも１００％の訂正は不可能である。また、通常の形態素解析で用いる辞書は新聞等の一般文章を対象としており、特殊な業務用途の文書を精度良く構成するためには、その分野に適合した特殊辞書を追加する必要がある。このため、保守性や計算量の面で問題が残るのである。
【００１３】
また、特許文献４に示されるアルゴリズムは、動的計画法をＨＭＭ（Ｈｉｄｄｅｎ  Ｍａｒｋｏｖ  Ｍｏｄｅｌ）モデルにおける単語照合の最適コストの計算のために使用しており、文法解釈及び最適語彙の選択は別の段階で行っている。従って、動的計画法を文法解釈するように拡張したものではない。
【００１４】
本発明はこのような状況に鑑みてなされたものであり、最適解を保証するビタビアルゴリズムを、表記文法を解釈するように拡張し、ＯＣＲ読取に起こり得る文字識別、文字切出、文字行抽出の誤りが文字列認識に与える悪影響を回避する方法を提案するものである。
【課題を解決するための手段】
【００１５】
上記課題を解決するために、本発明は文字列表記解析のアルゴリズムとして解の最適性を保証するビタビアルゴリズム（以下、ビタビまたはビタビ照合と称する）を採用し、文字列認識に起こり得る不安定要因（ノイズ挿入、文字誤読、不読、欠落、接触）、表記文法への適用と、配置検定の計算に対応する。
【００１６】
即ち、本発明による文字認識処理においては、画像入力部から文書画像データを入力し、文書構造解析部が、文書構造辞書を用いて、入力された文書画像データの構造を特定し、文字列仮説生成部が、文字識別辞書を用いて、文書構造が特定された文書画像データについて文字認識処理を行い、文字切出パタン候補及び文字切出パタンの識別結果を含む文字列仮説を生成する。そして、表記解析部が、文字列仮説に対して半順序構造に対応したビタビアルゴリズムを適用して、認識された文字列を確定する。
【００１７】
表記解析においては、準正規表現で定義され、表記される文字列の形態を格納する表記文法辞書と、文字配置に関する制約条件を格納する文字配置辞書が用いられる。このとき、表記解析部は、表記文法辞書に含まれる文字列表記文法をビタビアルゴリズムによって解析して、文字列仮説によって示される文字認識結果の候補を確定する。
【００１８】
また、表記解析部は、文字列を準正規表現のうち、候補単語を単純に列挙する単語列挙型表記以外の表記方式をビタビアルゴリズムによって解析する。
【００１９】
なお、表記解析部は、文字列表記文法を解釈する過程において、スタックを用いて表記解析結果を逐次展開することにより、動的計画法におけるコスト計算の計算量を削減する
ようにしている。
【００２０】
また、表記解析部は、半順序構造に対応したビタビアルゴリズムによって解析する場合に、文字列仮説を半順序構造のコスト関数として表現し、半順序構造のコスト関数を変数縮約によって順序構造に変換して計算することによって、文字列認識結果の候補を確定するようにしている。
【００２１】
さらなる本発明の特徴は、以下本発明を実施するための最良の形態および添付図面によって明らかになるものである。
【発明の効果】
【００２２】
本発明により、ＯＣＲ装置において生成した文字列仮説に対して、言語と文字パタンの配置尤度とを統合した評価尺度で自動計算を行うことで、様々なバリエーションのある文書画像に対する読取精度の向上が見込める。
【発明を実施するための最良の形態】
【００２３】
本発明は、光学式文字列認識に関し、文字欠落、接触、ノイズ混入、誤不読等による劣化状態にあっても、文字列表記文法と文字パタン配置知識に基づいてこれを解析し、文字列認識を行うロバストな文字列認識手法に関する。
【００２４】
以下、添付図面を参照して本発明の実施形態について説明する。ただし、本実施形態は本発明を実現するための一例に過ぎず、本発明の技術的範囲を限定するものではないことに注意すべきである。また、各図において共通の構成については同一の参照番号が付されている。
【００２５】
なお、本発明の実施形態は、最適解を保証するビタビアルゴリズムを、表記文法を解釈するように拡張し、ＯＣＲ読取に起こり得る文字識別、文字切出、文字行抽出の誤りが文字列認識に与える悪影響を回避する方法を提案する。特に、計算容量と記憶容量を抑えた、表記文法を解釈するビタビアルゴリズムを提案する。ビタビアルゴリズムは最適解を計算できるという利点があるが、それが対象とするコスト関数の形態は単純順序構造に限られていた。また、文字パタンの配置検定と文法解釈をビタビアルゴリズムで統合して行う場合、単純順序構造では問題が定式化できないケースが存在する。そこで、上述の課題に加えて、本実施形態は、半順序構造を持つコスト関数に対して計算ができるビタビアルゴリズムを提案する。
【００２６】
＜文字列認識装置の構成＞
まず、本実施形態が適用されるハードウェア構成について説明する。図１は、本発明の実施形態による文字認識装置（ＯＣＲ装置及び文書読取システム）の概略構成を示す図である。ＯＣＲ装置では、画像撮像部である画像撮像装置０１０１により紙文書を電子データに変換し、それを記憶部である外部記憶装置０１０５及びメモリ０１０６に蓄えて、中央処理部（ＣＰＵ）である中央演算装置０１０７により読取を行う。
【００２７】
本実施形態に係わるＯＣＲプログラム及び証跡管理プログラムは、外部記憶装置０１０５またはメモリ０１０６に蓄えられているか、通信装置０１０９を介して装置に導入され、これら記憶部に記憶される。ＯＣＲプログラムは、撮像された電子データ画像に対して、中央演算装置０１０７が帳票読取処理を行い、証跡管理画像として識別結果を出力する。帳票を読取る場合は、記憶部である外部記憶装置０１０５またはメモリ０１０６に蓄えられた文字識別辞書を参照し、帳票上に書かれた文字パタンを認識する。これらの処理は、操作端末装置０１０２を通して操作者である人間が操作可能であり、処理結果は表示端末装置０１０３を通して表示される。処理結果などの情報は、必要に応じて外部記憶装置
０１０５に蓄積または通信装置０１０９を通して外部装置にデータとして送信される。
【００２８】
上記装置群は、内部バス０１０８によって繋がっている。入力された伝票類はソータ装置０１０４によって、定義された箱に分配・集積される。言い換えるなら、画像撮像装置０１０１とソータ装置０１０４を除けば、通常のパーソナルコンピュータ（ＰＣ）などのコンピュータシステムで構成されうる。
【００２９】
証跡管理プログラムは、上記ＯＣＲ装置から出力された画像、及び認識結果を表示端末装置０１０３に表示する。認識結果は、操作端末装置０１０２を通して操作者である人間によって修正が行われる。そして、証跡管理プログラムは、その修正結果を外部記憶装置０１０５またはメモリ０１０６に蓄える。
【００３０】
＜文字認識の原理及び具体的処理＞
図２及び３は、文字列表記解析処理と文字列仮説の概要を説明するための図である。図２は文字列仮説と表記文法を使った文字列認識の流れを説明した図である。また、図３は、文字列仮説の概念とデータの詳細を示した図である。
【００３１】
図２において、読取対象文字行図２（ａ）から、文字パタンと思われる部分を様々に切出して候補文字パタンを作り、各候補文字パタンを文字識別する。このようにして得られたものが、文字列仮説図２（ｂ）である。より具体的には、文字列の中で、分離されうる箇所を列挙して、分離可能箇所を跨って１つの文字となりうるという仮説を立てる。例えば、図２の例では、「血」が１つの文字であるという仮説が成立するし、「血シ（さんずい）」や「夜イ」が１つの文字であるという仮説も成立する。つまり、文字列仮説は、文字パタン、文字識別の結果得られた順位付けされた識別コード群、文字列仮説中での文字パタン間の接続関係の情報、を最低限持つものということができる。
【００３２】
次に、文字列表記文法（図２（ｃ）：外部記憶装置１０５やメモリ１０６に格納されている）を使って、文字列仮説から読取結果（すなわち、文字列パス：図２（ｄ））を計算する。この例では、「血液」まで決れば、「血液検査」と「血液化学検査」が候補として残り、血漿検査が候補から落とされる。また、この例では文字列表記文法をＯＲ記号（｜）で単語を並べて表現している。すなわち、記号｜の間に挟まれた単語群が表記文法として指定されたことを意味する。文字列表記としては、この表記以外にもトライ、文脈自由文法などを使った方法がある。
【００３３】
図３は、文字列仮説の詳細を説明するための図である。文字列仮説は、文字パタンの候補をアーク（０３０１）とし、文字パタンの境界をノード（０３０２）とする有向グラフとして表現される。各文字パタンには、左右（縦書きであれば上下）のノード（パタン境界）を表す境界ＩＤ番号と、文字識別候補（０３０３）及び識別類似度（０３０４）の情報が含まれる。知識処理は、この文字列仮説と文字列表記文法を入力として、文字列仮説に含まれ得る単語とそのパタン列を見つける処理である。例えば文字列表記文法にある「血液化学検査」という単語は、図３（ｂ）の文字列仮説中に、太丸で示される文字コード及び文字パタン（０３０５）を辿ることで見つけることができる。当該欄に書かれる文字列の表記が事前に定まっている場合、本処理を行うことで文字列コードが確定する。なお、図３（ｂ）の０３０４は正規化する前の数値が示されており、本来なら、図２（ｂ）の尤もらしさ（例えば、夜、０．７）と同様に、「２５５」で正規化して１以下の数値とされるべきものである。
【００３４】
図４は、ＯＣＲ装置における各種処理のブロック図である。最初に紙文書または文書画像が画像入力部（０４０１）に入力される。紙文書の場合には、ＯＣＲ装置でそれを撮像して電子画像データに変換して入力される。文書構造解析部（０４０２）では、文書構造
辞書を用いて、入力された文書画像が、事前に登録された文書のフォーマットに適合するかどうかを調べる。つまり、電子的画像データを基にして、罫線抽出、枠構造解析、読取対象欄の位置推定等の文書構造解析を行う。文書構造辞書には、読取対象である文書画像の罫線座標、枠座標、読取対象欄の属性（氏名記入欄、住所記入欄、閲覧属性情報等）などの情報（文書フォーマット）が含まれる。このとき使う認識処理には従来から知られた技術（特許文献５及び６等参照）を利用する。
【００３５】
そして、文字行抽出部（０４０３）が、文書構造解析の結果を受けて、読取対象である文字行を抽出する。読取り対象領域内に存在する文字行の画像が、それぞれ１行単位で抽出される。読取対象箇所は文書画像全面でも、局所的な矩形エリアでも、どちらでも良い。
【００３６】
次に各文字行画像について、文字列仮説作成部（０４０４）が、文字パタンの切出しと、切り出された各文字パタンの識別を行う。作られた文字列仮説は図３に示したような有向グラフとして表現される。文書構造が入り組む場合は、文字行の仮説が複数立てられ、それぞれに文字パタン候補切出と文字識別を行う。文字識別の処理においては、文字識別辞書を用いる。文字識別辞書には、認識対象である文字パタンの文字コードと構造情報（輪郭方向成分の強度分布、各種統計量等）などが含まれる。文字パタン候補及び識別結果を併せて文字列仮説と称する。
【００３７】
続いて、表記解析部（０４０５）が、文字列仮説をどのように読むかを確定してテキスト列を生成する。表記解析部では、表記される文字列の形態を記した表記文法辞書と、文字配置に関する制約条件を記した文字配置辞書とを用いる。文字列表記知識辞書には、当該文書において出現し得る単語、数字列の表記、並びに単語群の出現可能順序等の情報が含まれる。これにより、文字切出や文字識別の曖昧性を含んだ文字列仮説は、文字列パス、更には文字列テキストに変換される。但し、文字列パスとは、文字コードと当該文字コードに対応する文字候補パタンがペアと成ったものの並びである。
【００３８】
最後に、テキスト出力部（０４０６）から、文書画像を読取った結果をテキストファイルなどに出力する。本発明は０４０５に関してビタビ照合の改良を提案するものである。
【００３９】
以上の説明により、文字列認識処理における表記解析処理の位置付けが理解できたものと思われる。つまり、本発明は、文字列読取の精度向上のために、上記０４０５の表記解析部の改良を提案するものである。そのために、次のアプローチを採用する。
【００４０】
１）読取対象画像の劣化（文字欠落、接触、ノイズ混入、及びその結果起こり得る文字の誤不読等）に対してロバストな文字列表記解析を実現するため、解の最適性を保証するビタビ照合による計算を行う。
【００４１】
２）表記文法の解析に対応するため、上記ビタビ照合を、スタックを使ったアルゴリズムに拡張する。表記文法には準正規表現による辞書記述を認めることで、表記辞書のコンパクトな記述を可能とする。
【００４２】
３）表記文法の解釈と、文字パタンの配置の検定をコスト関数の最適化という観点で統一し、その最適解をビタビ照合で計算する。但し、従来のビタビが単純順序構造を持つコスト関数のみに対応するのに対して、文字パタンの配置検定を行う場合に必要となる半順序構造を持つコスト関数へ対応するようアルゴリズムを拡張する。
【００４３】
ところで、ビタビアルゴリズムを使った文字列照合は、速度がやや遅いという難点があるものの、一般にＮ文字不読・挿入・欠陥を許しての照合が可能で、編集距離（Ｅｄｉｔ
Ｄｉｓｔａｎｃｅ）上で最適な文字列を求められるなど、従来の表記解析処理に無いメリットがある。一般に、表記解析処理では、照合するべき文字列の記述をＲＴＮ文法（Ｒｅｃｕｒｓｉｖｅ Ｔｒａｎｓｉｔｉｏｎ  Ｎｅｔｗｏｒｋ、再帰遷移構造ネットワーク
型文法）を使うが、このＲＴＮ文法の構造に適合してビタビ照合を行うエンジンは存在しない。これはＲＴＮ文法が再帰的な記述を許容するためである。
【００４４】
ビタビ照合では、問題を時系列（１次元系列）上の最適制御問題として捕え、時系列に並ぶ選択肢を引数とする関数漸化式を解く。これを文字列照合の問題に置き換えると、入力文字パタン群を説明するように１次元の文法列上で最適な文法子を選択する問題となるが、ＲＴＮ文法では再帰構造が定義できるため文法列が１次元系列にならない。このため、ＲＴＮ文法には、原理的にビタビが適用できない。
【００４５】
そこで、ビタビで用いる文法構造は、ＲＴＮ文法ではなく、単純な正規表現を使うことにする。但し、ビタビ照合アルゴリズムとの関連で正規表現による表記にも幾つかのレベルを想定しなければならない。このことは次に述べる。
【００４６】
正規表現では、並列｜、集合（）、省略［］（任意文字を表す＊や？は考慮外とする）などの特殊文字と、通常の文字を使って表記を定義する。また、住所辞書や姓名辞書への適応も考えてビタビ照合エンジンで使うと考えられる幾つかの特殊記号がある。抽出したいキーワードは特殊記号と併せて準正規表現を使って記述するが、ここでその記述様式を次の３つに分類する。この分類は次節で述べるビタビ照合アルゴリズムと関係がある。
【００４７】
ａ）単語列挙型表記
単語列挙型表記の例を次に掲げる。この定義の中には「精神療法」「精神分析」「精神分析療法」「精神分析学」という4つの単語が定義されている。
Ｓ（精神療法｜精神分析｜精神分析療法｜精神分析学）Ｅ
この例では単語の定義列はＳで始まり、Ｅで終わるとしている。また、丸括弧の中に4つ
の単語が並列する形で書かれている。
【００４８】
ｂ）トライ型表記
上記４単語の定義をトライ型に書き直すと次のようになる。トライ表記を使うと辞書の定義をコンパクトにできるというメリットがある。
Ｓ（精神（療法｜分析［療法｜学］））Ｅ
【００４９】
ｃ）途中省略・分岐許容型表記
途中省略・分岐許容では、次のような単語中における表記揺れを文法定義で吸収するために使うことができる。 
Ｓ（コンピュータ［ー］（管理｜診断）料）Ｅ
これは「コンピューター」という表記と、「コンピュータ」という表記の揺れを記したものである。また、その後に続く語彙として「管理料」や「診断料」などが存在することを示している。
【００５０】
単純ビタビ照合は、文法レベル１の単語列挙型に対応するものである。これに対して、トライ表記や分岐許容表記を使って辞書容量・照合計算量削減を行うためには、文法レベル２以上への対応が必要である。ＲＴＮ文法は、非終端記号を再帰的に使わない限りにおいては、上記の文法レベル３に該当すると考えられる。ビタビ照合の立場からみると、文法レベル２と文法レベル３の違いは、ある文法子の前段にある文法子群が単数か複数かということに相当する。文法レベル２の場合は前段の文字が単数であるため、以下に述べるようなスタック型の照合テーブルを使うことで照合アルゴリズムが容易に実現できる。また、文法レベル３の場合は、前段文字が複数あるため、複数のスタックを使ったアルゴリ
ズムが必要になる。ここで述べるのは、文法レベル２の照合アルゴリズムについてである。
【００５１】
まず、具体例を基にビタビ照合の計算手順について述べ、その後に定式化を行うこととする。図５（ａ）は照合対象となるネットワーク（候補文字ネットワーク）であり、これに対して辞書に登録された単語「血液検査」を単純ビタビ照合するとする。そのときのパス計算の様子は図５（ｂ）のような、格子状に張り巡らされた路を辿るイメージで表現できる。照合の路の計算は格子状道路の左上隅の点から開始する。まず始めに辞書単語の「血」に着目して、それに照合する所を探すと、パタン（２）と照合できることがわかる。次に「液」に着目するとパタン（６）と照合できることが分かり、かつ前のパタン（２）の照合とつながることがわかる。図５（ｂ）において太線が照合の結果として得られた路であり、太線の縦・横の位置が、それぞれ入力パタンと、それに対応する辞書の文字を表す。以上のように路を辿ってゆくのが、文法レベル１に対応する単純ビタビ照合になる。ビタビ計算では最適なパスが求まるが、単語ごとに格子状道路の設定をクリアして計算しなおすので、計算量が多い。
【００５２】
これに対して、文法レベル２に対応するビタビ計算を表したのが図６である。図６（ａ）は候補文字ネットワークであり、図６（ｂ）にコスト計算の様子を示している。ここでは０６０１に示すように、既に「血液検査」までの照合が終わっている。次に０６０２に示す、「血液化学検査」の単語の「化」の照合に移る。このとき、０６０３にある「血液」と照合した格子状道路の最適パスの計算結果は保存し、新しく０６０４のコストから計算しなおすというのが、文法レベル２に対する照合アルゴリズムのコンセプトとなる。これにより道路上格子上での最適パスの計算を削減することができる。
【００５３】
ここで、厳密な形で表記文法が解釈可能なビタビ照合の処理を定式化する。照合対象のネットワーク（候補文字ネットワーク）をＮ、照合文法をＣで表すとする。照合対象ネットワークは、始点ノード、終点ノード及びエッジの集合として構成され、式１のように表すことができる。
【００５４】
【数１】
2010061403.tif 000003
【００５５】
各記号は、始点ノードｎｓ 、終点ノードｎｅ 、エッジｎを意味する。このエッジは、候補文字ネットワーク上での文字パタンに相当する。照合文法Ｃも同様にグラフ構造を持つ。これを表すと、式２のようになる。
【００５６】
【数２】
2010061403.tif 000004
【００５７】
ここで、各記号は、始点ノードｃｓ、終点ノードｃｅ、エッジｃを意味する。このエッジは文法Ｃ上にある文法子に相当する。
【００５８】
ビタビ照合は２つのグラフ間のマッチングを行うアルゴリズムである。ここで、ある文法子ｃｊを、ある文字パタンｎｑに照合することを考える。この時の照合コストを式３のように表す。
【００５９】
【数３】
2010061403.tif 000005
【００６０】
また、文法子ｃｊの前段の文字はｃｉであるが、これは複数存在し得るとして、その集合を式４のように表すこととする。
【００６１】
【数４】
2010061403.tif 000006
【００６２】
但し、式５はグラフＧについて、ある着目エッジ（パス）ｅの前段に位置するエッジ集合を表すと約束する。
【００６３】
【数５】
2010061403.tif 000007
【００６４】
また、文字パタンｎｑの前段に位置する文字パタンをｎｐで表し、式６のように表す。
【００６５】
【数６】
2010061403.tif 000008
【００６６】
これもまた複数存在し得るとする。この時のビタビ照合コストは次の漸化式（式７）で表せる。
【００６７】
【数７】
2010061403.tif 000009
【００６８】
ここで、Ｍａｔｃｈ（）は、文法子ｃが文字パタンｎの文字候補群の中に含まれるか否かを表すコストである。Ｐａｔｈ（）は文字パタンｎｐ、ｎｑが接続するか否かを表すコスト、Ｎｅｘｔ は文法子ｃｉ、ｃｊが接続するか否かを表すコストである。上記再帰式
を全ての文法子列ｃｊ∈Ｃについて求めることで、最適な文法列が見つかる。これがビタビ照合である。
【００６９】
以上がビタビ照合の基本アルゴリズムになる。これを表記文法に適したものにするためには、ビタビ照合を、スタックを使ったアルゴリズムに拡張する。
【００７０】
次にスタックテーブルを使ったビタビ照合アルゴリズムについて記す。本アルゴリズムが解析対象とする文法は、特殊記号Ｓ、Ｅ、（、）、［、］、｜と、通常の文法子（文字コードのこと、Ｃで表す）から構成される。トライ型文法に適合したビタビ照合アルゴリ
ズムでは、この文法記述列を右から左へと走査し、照合テーブルを適時スタックにプッシュ・ポップすることで計算を行う。
【００７１】
ここで、照合テーブルとは、現在走査中の文法子ｃｊが、候補ネットワーク上の各文字パタンｎｑ∈Ｎに対応すると仮定した場合の最適コスト（及びパス）を保持するテーブルである。文法子ｃｊに対する照合テーブルをＤｐｔ（ｃｊ）で表すならば、式８のようになる。
【００７２】
【数８】
2010061403.tif 000010
【００７３】
最適コストの計算は、文法子ｃｊに対する照合テーブルＤｐｔ（ｃｊ）を先頭の文法子Sから順次計算して行われる。いま着目する文法子ｃｊに対して、照合テーブル を計算するためには、前段の文法子ｃｉに対応する前段照合テーブルＤｐｔ（ｃｉ）が必要である。この前段の照合テーブルはスタックを参照することで得られる。このスタック走査のタイミングは文法子が来たタイミングで行う。具体的な動作は図７に示される。以上のビタビ照合のコスト計算式、及びスタック演算タイミングにより、文法駆動ビタビ型文字列表記処理が説明された。
【００７４】
ビタビ照合では一般に事前にコストネットワークを事前構築して計算を行うが、候補ネットワークＮと文法Ｃのエッジ数の積｜Ｎ｜×｜Ｃ｜に比例した記憶容量が必要となる。上記スタックテーブルを用いると、キーワード抽出エンジンのコンパクト化（辞書容量、計算時容量）が図られる。スタックテーブル型では、この容量が最小で｜Ｎ｜×２、単語パスを記憶する場合でも｜Ｎ｜×最大単語長にまで減らすことが出来る。
【００７５】
上述のような定式化したビタビ照合の計算は、単純順序構造を持つコスト関数の最大化問題として捕らえることができる。関数の構造を示したものが図８である。一般にビタビ照合計算では図８（ａ）に示すような関数構造のコスト計算を行う。図８中で丸で囲まれたｘは変数を表し、各変数が、それぞれの変数に定められた範囲の中から、ある値を取る。変数同士の間には、何らかのコストを定めた関数が存在する。それを表したのが網線が掛けられた四角である。式で書くと、図８（ａ）に対応するコスト関数は、式９のようになる。
【００７６】
【数９】
2010061403.tif 000011
【００７７】
このように変数が順番に並び、隣り合う変数間のみにコスト関数が関わる場合を、コストの単純順序構造と称する。一般のビタビ照合計算では、このような単純順序構造を持つコスト関数について、その最大値（または最小値）となるように変数の取る値を決める。最適解を求めるための計算量は、各変数がＭ個の値をとり、変数がＮ個存在するとするならば、Ｎ×（Ｍの２乗）に比例する。
【００７８】
しかし、文字パタンの配置を考えた場合、このような単純順序構造では済まず、半順序構造を計算対象としなければならないケースがある。半順序構造の例が図８（ｂ）および図８（ｃ）にある。図８（ｂ）は第３変数を跨って、第２変数と第４変数の間にコスト関数が付いている場合。図８（ｃ）は、それを一般化して、隣り合う変数だけでなく、一つ
先の隣り合う変数同士間についてもコスト関数が定められているケースを表す。図８（ｂ）に対応する具体的なコスト関数は式１０のように表される。
【００７９】
【数１０】
2010061403.tif 000012
【００８０】
これを解決するための手段として、包含関係による変数縮約がある。図８（ｃ）を例にコンセプトを述べる。まず、第１変数と第２変数間を結ぶコスト関数は、第１・第２・第３変数に関するコスト関数に包含されると見なして、これを消去する。次に、第２変数と第３変数間を結ぶコスト関数は、第２・第３・第４変数に関するコスト関数に包含されると見なして、これを消去する。第３変数と第４変数間を結ぶコスト関数は、第３・第４・第５変数に関するコスト関数に包含されると見なして、これを消去する。最後に、第４変数と第５変数を結ぶコスト関数は、第３・第４・第５変数に関するコスト関数に包含されると見なして、これを消去する。以上の手続きに従って得られた変数縮約結果が、図８（ｄ）の変換されたコスト構造になる。これに対応するコスト関数は、式１１のように表される。
【００８１】
【数１１】
2010061403.tif 000013
【００８２】
このコスト計算は、隣り合う関数の内の２つの変数をペアで計算して局所的な最適解を求めることで計算できる。このような半順序構造を持つコスト関数について最適解を求めるための計算量は、各変数がＭ個の値をとり、変数がＮ個存在するとするならば、Ｎ×（Ｍの３乗）に比例する。
【００８３】
ここで、半順序構造の変数縮約を一般化すると、次のようになる。
１）一般のビタビアルゴリズムでは、変数（例えば、図５（ｂ）の辞書の文字）と値（例えば、図５（ｂ）の辞書文字に対応する文字パタン）によって、格子状の探索領域を定める。
【００８４】
２）これを半順序構造に拡張するために、コスト関数で用いる変数の組を１つの新規変数と見なす。即ち、変数（ｘ１、ｘ２）がペアであればｙ１、変数（ｘ２、ｘ３）がペアであればｙ２、変数（ｘ１、ｘ２、ｘ３）がペアであればｙ３を新規変数とする。
【００８５】
３）次に新規変数について、元々の変数組みが包含されるものについて、これを消去する。すなわち、ｙ１、ｙ２はｙ３に包含されるのでこれを消去する。
【００８６】
４）続いて、残された新規変数について、新規変数間のコスト関係によるネットワークを構築し、新規変数の順序を入れ替えた場合に、それが１次元状に並ぶ場合ならば、これ以上の縮約を停止する。１次元状の判定は、次のようなグラフ処理によって行う。ここで説明のために、変数ペア（ｘ１，ｘ２，ｘ３）をｙ３、変数ペア（ｘ２，ｘ３，ｘ４）をｙ４、変数ペア（ｘ３，ｘ４，ｘ５）をｙ５とする。このとき変数ペアを共有する間に順序を現す矢印を張り、これを有向グラフとして解析する。変数ｙ３、ｙ４は変数ペア（ｘ２，ｘ３）を共有するので、ｙ３＞ｙ４となる。更に、変数ｙ４、ｙ５は変数ペア（ｘ３
，ｘ４）を共有するのでｙ４＞ｙ５となる。並べると、ｙ３＞ｙ４＞ｙ５となって一列に並び、ｙ３＞ｙ５のような跨った関係が存在しない。このようなケースを１次元状に並ぶとする。
【００８７】
５）そうならない場合、ネットワークが１次元状にならない部分区間を計算し、この間について、更に新しい新規変数について再帰的な変数縮約を行う。つまり、上記のように変数間のに順序を表す有向グラフについて、例えばｙ３＞ｙ４＞ｙ５＞ｙ６＞ｙ７、ｙ５＞ｙ７という遷移がある場合、ｙ５＞ｙ７の部分区間が１次元状にならないので、この部分に対して新しい変数ペア（ｙ５，ｙ７）を導入することで縮約を行う。
【００８８】
ところで、図８（ｃ）のような半順序構造を考えなければならない典型例は、文字パタンの配置検定である。その例が図９に示されている。図９（ａ）から（ｃ）は真ん中に点パタンを含む文字列パタンである。このような点などの記号文字は、文字パタンの形状を見るだけで、それがどのような字種に相当するか（中黒か、ピリオドか、シングルクォーテーションか、あるいはノイズか）を決定することが困難であり、一般には周辺にある文字パタンとの配置関係で字種を決定する必要がある。図９（ａ）は中黒と解釈できる例、図９（ｂ）も同様である。但し、両者の文字間隔は狭い、広いと異なる。文字パタンの配置検定の例で、隣り合う文字パタンとの広さ、狭さによって字種の尤度を変更する方法が良く使われているが、多様な文書バリエーションへの対応を考えると、単純に間隔だけを考えるのではすまない。この例で言えば、中黒は、左右両端の文字パタンとの間隔が等しく、真ん中付近の高さにある文字パタンであれば、尤もらしいと言える。図９（ｃ）はノイズの例である。これは、左右それぞれの隣接パタンとの距離が不均一であることから判定できる。真ん中の点パタンが、中黒かノイズかを判定するということは、図９（ｄ）のように、真ん中のパタンの解釈を「・」（中黒）とするか、「×」（ノイズ）とするかという選択の問題に成る。これをコスト問題として表現したのが図９（ｅ）である。図９（ｅ）の第３変数が、「・」（中黒）という値を取るべきか、「×」（ノイズ）という値を取るべきか、どちらが最適コスト解となるかをビタビによって計算する問題と定式化できる。このとき、左右両隣との文字パタンとの距離が均一な場合は中黒、不均一な場合はノイズと見なすということは、第３変数を中心として、第２・第３・第４変数が関係するコスト関数を設定するということになる。このように半順序構造を対象としたコスト計算が必要となる。
【００８９】
＜実施形態のまとめ＞
以上説明したように、本発明の実施形態によれば、文法駆動と半順序構造に対応したビタビアルゴリズムによる表記文法および文字パタン配置の解析により、ノイズ混入などによる文字列認識不具合要因に対して、解の最適性を保証するロバストな表記解析が可能となる。
【００９０】
なお、本発明は、実施形態の機能を実現するソフトウェアのプログラムコードによっても実現できる。この場合、プログラムコードを記録した記憶媒体をシステム或は装置に提供し、そのシステム或は装置のコンピュータ（又はＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出す。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコード自体、及びそれを記憶した記憶媒体は本発明を構成することになる。このようなプログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどが用いられる。
【００９１】
また、プログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）などが実際の処理の一部又は全部を行い、その処理によって前述し
た実施の形態の機能が実現されるようにしてもよい。さらに、記憶媒体から読み出されたプログラムコードが、コンピュータ上のメモリに書きこまれた後、そのプログラムコードの指示に基づき、コンピュータのＣＰＵなどが実際の処理の一部又は全部を行い、その処理によって前述した実施の形態の機能が実現されるようにしてもよい。
【００９２】
また、実施の形態の機能を実現するソフトウェアのプログラムコードを、ネットワークを介して配信することにより、それをシステム又は装置のハードディスクやメモリ等の記憶手段又はＣＤ-ＲＷ、ＣＤ-Ｒ等の記憶媒体に格納し、使用時にそのシステム又は装置のコンピュータ(又はＣＰＵやＭＰＵ)が当該記憶手段や当該記憶媒体に格納されたプログラムコードを読み出して実行するようにしても良い。
【図面の簡単な説明】
【００９３】
【図１】ＯＣＲ装置および文書読取システムの概略構成を示す図である。
【図２】文字列仮説を使った表記文法処理の概念図である。
【図３ａ】文字列仮説の概念図（１）である。
【図３ｂ】文字列仮説の概念図（２）である。
【図４】ＯＣＲ装置および文書読取システムで行う処理の機能ブロック図である。
【図５】文法レベル１の単純ビタビアルゴリズムを説明するための図である。
【図６ａ】文法レベル２の文法駆動型ビタビアルゴリズムを説明するための図（１）である。
【図６ｂ】文法レベル２の文法駆動型ビタビアルゴリズムを説明するための図（２）である。
【図７】スタックを用いた文法駆動型ビタビアルゴリズムの演算タイミング表である。
【図８】コスト計算構造の概念図である。
【図９】文字パタンの配置検定を説明するための図である。
【符号の説明】
【００９４】
０１０１・・・画像撮像装置、０１０２・・・操作端末装置、０１０３・・・表示端末装置、０１０４・・・ソータ装置、０１０５・・・外部記憶装置、０１０６・・・メモリ、０１０７・・・中央演算装置、０１０８・・・内部バス、０１０９・・・通信装置、０３０１・・・文字列仮説上の文字パタン、０３０２・・・文字列仮説上のパタン境界、０３０３・・・文字列仮説上の文字識別結果、０３０４・・・文字列仮説上の文字識別類似度、０３０５・・・文字列仮説上から検索された単語、０４０１・・・読取処理における画像入力部、０４０２・・・読取処理における文書構造解析部、０４０３・・・読取処理における文字行抽出部、０４０４・・・読取処理における文字列仮説作成部、０４０５・・・読取処理における表記解析部、０４０６・・・読取処理におけるテキスト出力部
【図１】
2010061403.tif 000014
【図２】
2010061403.tif 000015
【図３ａ】
2010061403.tif 000016
【図３ｂ】
2010061403.tif 000017
【図４】
2010061403.tif 000018
【図５】
2010061403.tif 000019
【図６ａ】
2010061403.tif 000020
【図６ｂ】
2010061403.tif 000021
【図７】
2010061403.tif 000022
【図８】
2010061403.tif 000023
【図９】
2010061403.tif 000024