(57)【要約】【課題】文書イメージデコードを改善するためのスタックアルゴリズムを組み込む文書イメージデコードの方法およびシステムを提供すること。【解決手段】　デコードを改善するためにスタックアルゴリズムの適用が反復される。テンプレートマッチングを低減するために部分パスに対して仮の重要度が決定される。重複した仮定を低減するために意味的に等価の仮定が識別される。【選択図】図１２
2004078956.tif 000002
【特許請求の範囲】
【請求項１】
　スタックアルゴリズムを組み込む文書イメージデコードで仮定の探査を低減する方法において、
　第１の部分パスが、既に処理されている第２の部分パスに意味的に等価であるか否かを判定するステップと、
　第１の部分パスが第２の部分パスに意味的に等価である場合、キューを調整するか、または第１の部分パスと第２の部分パスの一方を破棄するステップと
を含むことを特徴とする方法。
【請求項２】
　実行可能なソフトウェアコードを有するコンピュータ記憶媒体において、実行可能なソフトウェアコードが、
　第１の部分パスが、既に処理されている第２の部分パスに意味的に等価であるか否かを判定するための命令と、
　第１の部分パスが第２の部分パスに意味的に等価である場合、キューを調整するか、または第１の部分パスと第２の部分パスの一方を破棄するための命令と
を含むことを特徴とするコンピュータ記憶媒体。
【請求項３】
　スタックアルゴリズムを組み込む文書イメージデコードで仮定の探査を低減するシステムにおいて、
　等価決定回路、ルーチンまたはアプリケーションと、
　キューイング回路、ルーチンまたはアプリケーションと
を備え、
　等価決定回路、ルーチンまたはアプリケーションが、第１の部分パスが、既に処理されている第２の部分パスに意味的に等価であるか否かを判定し、
　キューイング回路、ルーチンまたはアプリケーションが、第１の部分パスが第２の部分パスに意味的に等価である場合、キューを調整するか、または第１の部分パスと第２の部分パスの一方を破棄することを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、文書イメージデコードの方法およびシステムに関する。
【背景技術】
【０００２】
　文書イメージデコード（Ｄｏｃｕｍｅｎｔ　ｉｍａｇｅ　ｄｅｃｏｄｉｎｇ）は、文書構成、印刷、劣化（ｄｅｇｒａｄａｔｉｏｎ）、およびスキャニングのプロセスに関する通信システム表示に基づく文書イメージに含まれるテキストを認識する方法である。
【０００３】
　文書イメージは、確率的な有限状態機械（ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｆｉｎｉｔｅ−ｓｔａｔｅ　ｍａｃｈｉｎｅ）であるマルコフ情報源（Ｍａｒｋｏｖ　ｓｏｕｒｃｅ）を介して遷移することによって生成されたものとみなすことができる。このソースは特別な開始状態から始まり、特別な終了状態で終了する。ソース内の各遷移は、現在のカーソル位置のページにビットマップなどのイメージの部分を入力し、認識された文字を出力し、次の文字を認識する準備として二次元ベクトル変位によってその位置を進める。この遷移は、入力されたイメージ部分と出力文字に関連付けられた文字テンプレートとの一致の程度に基づいて選択される。文字テンプレートの集合には各種余白が含まれる。
【０００４】
　ソースの各遷移には、文字テンプレート、カーソルを進める二次元変位、その遷移に従う事前確率、および認識された文字を含むストリングラベル（ｓｔｒｉｎｇ　ｌａｂｅｌ）から構成される４つのタプル（ｔｕｐｌｅ）が割り当てられている。
【０００５】
　情報源を通過するすべての完全パスは、文書イメージおよび関連する転写を定義する。
【０００６】
　文書イメージが形成された後、認識プロセスに何らかの不確実性をもたらすある形式の無作為な転訛又は改悪の原因となるプロセス（ｒａｎｄｏｍ　ｃｏｒｒｕｐｔｉｏｎ　ｐｒｏｃｅｓｓ）を、文書イメージがその認識プロセス以前に受けているものと仮定する。認識は、注目されているイメージを「最適に」説明する、仮定されたマルコフ情報源の完全パスを見つけることによって行われる。より正確に言えば、文書イメージを認識することは、文書イメージ全体を証拠（ｅｖｉｄｅｎｃｅ）とみなすと最も確率の高いソースの完全パスを探すことを含む。それぞれの完全パスに対する確率は、遷移の事前確率、関連するイメージ化されたテンプレートの尤度、および無作為な転訛又は改悪の原因となるプロセスに基づいて決定される。同一の転写に複数のパスが一致する場合があるので、最も確率の高い完全パスを選択することは最も確率の高い転写を選択することと同じではない。
【０００７】
　転写の確率は、その転写と一致する完全パスのすべての確率を合計することによって適切に決定される。しかし、完全パスの最高の確率を有するメッセージを選択することは、通常、最高の事後確率を有するメッセージを選択することに非常に近いということが経験的に示されている。これは、最大事後確率（Ｍａｘｉｍｕｍ　ａ　ｐｏｓｔｅｒｉｏｒｉ　ｐｒｏｂａｂｉｌｉｔｙ）決定規則に対するビタビ近似値（Ｖｉｔｅｒｂｉ　ａｐｐｒｏｘｉｍａｔｉｏｎ）として知られている。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
　言語モデルが文書イメージデコードに組み込まれている場合、デコード空間が大きくなりすぎてビタビアルゴリズム（Ｖｉｔｅｒｂｉ　ａｌｇｏｒｉｔｈｍ）などの方法でデコードを実行することは難しくなる。また、文書イメージデコードモデルは、「シンスペース（ｔｈｉｎ　ｓｐａｃｅ）」と呼ばれる空白の１ピクセル幅の文字を含んでいる。このシンスペースが、言語モデルを文書イメージデコードに組み込むことを困難にしている。さらに、言語モデルが文書イメージデコードに組み込まれている場合、テンプレートのマッチングは非常に高価になる。
【課題を解決するための手段】
【０００９】
　スタックアルゴリズム（Ｓｔａｃｋ　ａｌｇｏｒｉｔｈｍ）は、各ステップで最も有望なパスを延長することができるように、長さの異なるパスを直接比較する手段を提供する。スタックアルゴリズムは、スコアの高い絶対パスで終了する各部分パスの全体的な可能性の測度に従って最も有望なパスを決定するために優先キュー（ｐｒｉｏｒｉｔｙ　ｑｕｅｕｅ）を使用する。
【００１０】
　本発明は、修正変更されたスタックアルゴリズム（Ｍｏｄｉｆｉｅｄ　Ｓｔａｃｋ　ａｌｇｏｒｉｔｈｍ）を補完し、そのスタックアルゴリズムが同様の重要度を有するパスで使用されることを可能にする修正変更されたスタックアルゴリズムを実行し、かつ／またはそのスタックアルゴリズムが長さの異なるパスで使用されることを可能にする修正変更されたスタックアルゴリズムを実行するシステムおよび方法を提供する。
【００１１】
　本発明は、修正変更されたスタックアルゴリズムが文書イメージデコードで使用されることを可能にし、修正変更されたスタックグラフ（Ｓｔａｃｋ　ｇｒａｐｈ）が探査されることを可能にし、探査された修正変更済みスタックグラフに基づいて文書イメージデコードで望ましいパスを識別し、望ましいパスを識別するために優先順位テーブルを使用することを可能にし、スタックグラフの一部だけを探査することを可能にし、スタックグラフの探査された部分に基づいて望ましいパスを識別し、パスの実現可能な延長を調べることを可能にし、かつ／または調べた実現可能な延長に基づいて望ましいパスを識別する方法およびシステムを提供する。
【００１２】
　本発明は、パスの重要度を決定することを可能にし、決定された重要度に基づいて修正変更されたスタックアルゴリズムのパスの優先順位を識別し、テンプレートマッチング成分の重要度を決定することを可能にし、修正変更されたスタックアルゴリズムの言語モデル成分の重要度を決定することを可能にし、部分パスの重要度を決定することを可能にし、かつ／またはテンプレートマッチング成分の重要度と言語モデル成分の重要度の間にパラメータを定めることによって部分パスの重要度を決定することを可能にする方法およびシステムをさらに提供する。
【００１３】
　本発明は、修正変更されたスタックアルゴリズムを使用する際に意味的に等価な仮定の数を減らすことを可能にし、ある部分パスが別の部分パスに意味的に等価か否かを判定することを可能にし、意味的に等価な仮定を識別することを可能にし、識別された意味的に等価な仮定に基づいて仮定を減らすことを可能にし、修正変更されたスタックアルゴリズムを使用する際に意味的に等価な仮定を更新することを可能にし、かつ／または再実行キューを使用することによって意味的に等価な仮定を更新する方法およびシステムを別個に提供する。
【００１４】
　本発明による方法およびシステムは、ある部分パスが別の部分パスに意味的に等価であると識別することを可能にする。優先順位キューの部分パスと別のパスが意味的に等価である場合に別のパスの方が好適な重要度を有しているならば、優先順位キューの部分パスを破棄することができる。意味的に等価なパスを識別することによって、パス探索の範囲は低減される。
【発明の効果】
【００１５】
　スタックアルゴリズムを組み込む文書イメージデコードで仮定の探査を低減する。
【発明を実施するための最良の形態】
【００１６】
　本発明の方法およびシステムの様々な実施形態例を、図面を参照しながら詳細に説明する。
【実施例】
【００１７】
　文書イメージデコードは光学式文字認識（ＯＣＲ）に対して通信システムを採用する。言語モデルが組み込まれた場合、文書イメージデコードプロセスは、受け取った文書イメージの文字をデコードする際にテンプレートマッチングと言語学的尤度の両方を考慮する。
【００１８】
　言語学的尤度に関して、言語モデルＬによって与えられる統計的特性を伴う元のメッセージＮ＝ｃ１，ｃ２，ｃ３，．．．はチャネルで「送信」される。ｄ番目の言語モデルＬｄでは、各文字にはサイズｄのコンテキスト（ｃｏｎｔｅｘｔ）に基づいて確率が与えられる。例えば現在の文字には、現在の文字の直前に表示されたｄ個の文字のコンテキストに基づいて確率が与えられる。
【００１９】
　図１は、テキストフラグメント（ｔｅｘｔ　ｆｒａｇｍｅｎｔ）１００に適用された場合の文書イメージデコードのフレームワークを示している。テキストフラグメント１００の文書イメージは複数の文字１１０、すなわち黒い文字１１０を含む。
【００２０】
　分かり易くするために、図１に示すテキストフラグメント１００は一次元のテキスト行であるとみなす。テキスト行は、テキスト行のサイズをｘ座標の増加方向に増加させながら、テキストフラグメント１００の左端の点から始まり、テキストフラグメント１００の右端の点で終了する。
【００２１】
　図１の複数の文字１１０のそれぞれは、説明のためにｃｉがラベリングされ、対応するｘ座標値ｘｉに配置される。ここで、ｉ＝１，２，３，．．．はテキストフラグメント１００の文字１１０の指標である。
【００２２】
　図１では、言語モデルＬｄは３番目の文字が文字「ｃ」よりも文字「ｅ」である可能性が高いと認知している可能性がある。これは、３番目の文字の１つまたは複数の前にある文字を考慮して、「Ｔ−ｈ−ｅ」の配列は「Ｔ−ｈ−ｃ」の配列よりも言語学的により可能性が高いからである。
【００２３】
　ｄ番目の言語モデルＬｄを使用するメッセージＮ＝ｃ１，ｃ２，ｃ３，．．．，ｃｉ、．．．の位置ｉに表示される次の文字ｃｉに対する確率Ｐ（ｃｉ）を、次のように示すことができる。
　　Ｐ（ｃｉ｜ｃｉ−ｄ＋１，ｃｉ−ｄ＋２，．．．，ｃｉ−１）　　　　（１）
　上式で、ｃｉは次の文字であり、
ｃｉ−ｄ＋１等はｄ個の前にある文字である。
【００２４】
　レンダリングモデル（Ｒｅｎｄｅｒｉｎｇ　ｍｏｄｅｌ）Ｒを、文書内で文字を位置付けるプロセスを説明するために使用することができる。劣化モデルＤは、認識されるべきテキストフラグメントを含んでいる文書を印刷、コピーおよび／またはスキャンしている間に発生し得るイメージのひずみ（ｄｉｓｔｏｒｔｉｏｎｓ）を説明するために使用することができる。レンダリングモデルＲと劣化モデルＤは、レンダリングされ、劣化した後で受け取った文書イメージＺのソーステキストＮ＝ｃ１，ｃ２，ｃ３，．．．の配列に文字がどのように表示されるかを設定する。したがって、文書イメージデコードプロセスは、受け取ったイメージＺからデコードされるべき最も可能性の高いソースＮ’＝ｃ１，ｃ２，ｃ３，．．．を定義する最も可能性の高いレンダリングプロセスと最も可能性の高い劣化プロセスとを決定する。
【００２５】
　レンダリングモデルＲでは、位置（ｘ，ｙ）に配置された文字ｃｉによって、フロントｆからの文字テンプレートは理想的なイメージＱに置かれると仮定される。このようなモデルは次のように表現することができる。
　　Ｒ（ｃｉ，ｆ，ｘ，ｙ，Ｑ）　　　　（２）
【００２６】
　固定されたベースラインと１つのフォント活字面とを有するテキスト１行に対して、方程式（２）に示したレンダリングモデルＲは次のように単純化することができる。
　　Ｒ（ｃｉ，ｘ，Ｑ）　　　　（３）
【００２７】
　文字間には文字従属スペーシングがある場合がある。Ｒ（ｃｉ，ｘｉ，Ｑ）によってｘ座標の位置ｘｉで文字ｃｉをレンダリングした後、次の文字ｃｉ＋１は、次のように決定される次のｘ座標ｘｉ＋１でレンダリングされる。
　　ｘｉ＋１＝ｘｉ＋ｗ（ｃｉ）
　上式で、ｗ（ｃｉ）は先行文字ｃｉの設定幅である。
【００２８】
　スペーシングｗ（ｃｉ）のサイズはフォントによって異なる場合がある。多くのフォントで、スペーシングｗ（ｃｉ）のサイズは文字ごとに異なる。一方、理想的なイメージＱは、デコードされるべき、受け取ったイメージＺを形成するために、印刷し、スキャニングし、かつ／または文書を使用することによって劣化する場合がある。
【００２９】
　マッチング関数Ｍ（ｃｉ，ｘ，Ｚ）は、受け取った文書イメージＺを形成するために文字ｃｉがＲ（ｃｉ，ｘｉ，Ｑ）によって位置ｘｉでレンダリングされ、次いで劣化関数（ｄｅｇｒａｄａｔｉｏｎ　ｆｕｎｃｔｉｏｎ）すなわちモデルＤ（Ｑ→Ｚ）によって劣化した尤度を決定するために使用することができる。この決定は、劣化した、受け取った文書イメージＺとテンプレートの集合のマッチングに基づいている。
【００３０】
　図１で、３番目の文字１１２がいかなる他の文字のテンプレートとマッチするよりも、文字「ｃ」のテンプレートまたは文字「ｅ」のテンプレートとマッチする可能性の方が高いことを示すために、３番目の文字１１２が複数のテンプレート１５０と比較される場合がある。さらに、ｄ番目の言語モデルＬｄに基づいて、３番目の文字１１２は文字「ｃ」のテンプレートとマッチするよりも文字「ｅ」のテンプレートとマッチする可能性の方が高いことが示される場合がある。
【００３１】
　マッチング関数Ｍ（ｃｉ，ｘ，Ｚ）は、ビットフリップモデル（ｂｉｔ　ｆｌｉｐ　ｍｏｄｅｌ）を含むことができる。ビットフリップモデルでは、黒のピクセルが白になる確率は低く、白のピクセルが黒になる確率も低い。マッチング関数Ｍ（ｃｉ，ｘ，Ｚ）は、黒のピクセルが白になる確率が白のピクセルが黒になる確率に等しい場合は、対称的なビットフリップモデルを含むことができる。マッチング関数Ｍ（ｃｉ，ｘ，Ｚ）は、フルグレースケールモデルも含むことができる。
【００３２】
　受け取った文書イメージＺに関して、元のテキストＭが理想的なイメージＱにレンダリングされ、次いで受け取った文書イメージＺに劣化する方法に関する複数の仮定Ｈが存在する場合がある。各仮定Ｈは確率を有する。文字ｃｉが位置ｘｉに表示されるという仮定Ｈは、Ｈ（ｃｉ，ｘｉ）で表現することができる。特定の文字ｃｉが受け取った文書イメージＺの位置ｘｉに表示されるＨ（ｃｉ，ｘｉ）の確率は、ｄ番目の言語モデルＬｄからの言語学的コンテキストに基づいて先行するｄ個の文字があると仮定すると、特定の文字ｃｉが適切なテンプレートＴ（ｃｉ，ｘｉ，Ｚ）とマッチングする確率と特定の文字ｃｉが次に表示される確率Ｐ（ｃｉ｜ｃｉ−ｄ＋１，ｃｉ−ｄ＋２，．．．，ｃｉ−１）の積である。したがって、仮定Ｈ（ｃｉ，ｘｉ）の確率Ｐ（ｃｉ，ｘｉ）は次の通りである。
　　Ｐ（ｃｉ，ｘｉ）＝Ｍ（ｃｉ，ｘｉ，Ｚ）＊Ｐ（ｃｉ｜ｃｉ−ｄ＋１，ｃｉ−ｄ＋２，．．．，ｃｉ−１）　　　　　（４）
【００３３】
　劣化したイメージＺの全体的なテキスト行が位置ｘ１に文字ストリングｃ１を、位置ｘ２に文字ｃ２を、位置ｘ３に文字ｃ３を、また一般的に位置ｘｉに文字ｃｉを含んでいるという仮定Ｈ’は、次のように示すことができる。
　　Ｈ’＝（ｃ１，ｘ１），（ｃ２，ｘ２），（ｃ３，ｘ３），．．．（ｃｉ，ｘｉ），．．．　　　　　（５）
【００３４】
　方程式（５）で表現された仮定Ｈ’の確率は、各（ｃｉ，ｘｉ）の確率の積である。したがって、Ｈ’の確率は、
【数１】
2004078956.tif 000003
である。
【００３５】
　したがって、仮定Ｈ’の対数確率は、
【数２】
2004078956.tif 000004
である。
【００３６】
　方程式（７）は、次のテンプレートマッチング成分ＴＭ（ｉ）と、
　　ＴＭ（ｉ）＝ｌｏｇＭ（ｃｉ，ｘｉ，Ｚ）　　　　　（８）
言語モデル成分ＬＭ（ｉ）
　　ＬＭ（ｉ）＝ｌｏｇＰ（ｃｉ｜ｃｉ−ｄ＋１，ｃｉ−ｄ＋２，．．．，ｃｉ−１）　　　（９）
を含んでいる。
【００３７】
　次の文字ｃｉ＋１のｘ座標位置が先行文字の設定幅ｗ（ｃｉ）によってのみ定義されるべきであるという必要条件、すなわちｘｉ＋１＝ｘｉ＋ｗ（ｃｉ）は、メッセージ文字ｃｉの所望の位置付けを達成するために、メッセージ文字ｃｉ間に０またはさらに特別な「シンスペース」文字ｔを加えることによって緩和することができる。各シンスペースｔは、例えば１ピクセルの設定幅を有する。１つまたは複数のシンスペースｔを含むという仮定Ｈ”は、次のように表現することができる。
Ｈ”＝（ｃ１，ｘ１），（ｔ１），（ｃ２，ｘ２），（ｔ２），（ｃ３，ｘ３），．．．，　　　（１０）
　上式で、ｔｉは２つの隣接するメッセージ文字ｃｉとｃｉ＋１の間のシンスペース数である。
【００３８】
　仮定Ｈ”は、シンスペース文字に対する追加のテンプレートマッチングの項を有する方程式（７）によって与えられた対数確率を有する。すなわち、仮定Ｈ”の対数確率は、次のように表現することができる。
【００３９】
【数３】
2004078956.tif 000005
【００４０】
　各シンスペース文字ｔに対する対数Ｍ（ｔｉ，ｘｉ，Ｚ）は、同一位置のフルスペースに対するマッチスコア（ｍａｔｃｈ　ｓｃｏｒｅ）の対数の比較可能な部分にほぼ等しいと定義することができる。しかし、マッチング関数Ｍ（ｃｉ，ｘ，Ｚ）が通常のスペース文字を１つまたは複数のシンスペース文字ｔに置き換えないように、これらの追加のマッチングの項はフルスペースのマッチングの項よりも僅かに少ないと定義される。
【００４１】
　シンスペース文字ｔは、一般に、同一メッセージ文字ストリングｃ１，ｃ２，ｃ３，．．．に対する複数の仮定Ｈｔを導入する。この場合、複数の仮定Ｈｔのそれぞれは異なる数のシンスペース文字ｔでのみ異なる。これは、二重の仮定Ｈｔすなわち、意味的に等価の仮定Ｈｔをしばしば生じ、文書イメージデコード関連の費用を増加させる。
【００４２】
　最も可能性のある仮定ＨＬは、デコードの解のために決定し、使用することができる。異なる仮定Ｈが意味的に等価であるか否かを決定するために、その異なる仮定Ｈが比較される。そのような決定を行うためにハッシュテーブルを使用することができる。２つの仮定ＨｉとＨｊが意味的に等価の場合、解に導くためのより大きな見込みを有する仮定Ｈｉは維持され、他の仮定Ｈｊは破棄される。したがって、以下でさらに詳細に説明するように、二重の仮定Ｈ、すなわち意味的に等価な仮定Ｈの数は低減される。
【００４３】
　シンスペース文字ｔはテンプレートＴを分離することを可能にすることもでき、レンダリングモデルＲはテンプレートＴがオーバーラップすることを可能にすることができる。テンプレートをオーバーラップ（ｏｖｅｒｌａｐ）することはテンプレートのマッチングを行全体に対して標準化する方法に影響を与えるが、これは言語モデルが組み込まれた場合の問題の原因となりうる。モデリングが不正確であるために、モデルを結合する際にある種の融通性が求められる。これらの問題を克服するためにパラメータを定める単純な方法を使用することができる。方程式（１１）で定義された対数確率は、次のようにパラメータを定めることができる。
【００４４】
【数４】
2004078956.tif 000006
　上式で、λはパラメータである。
【００４５】
　パラメータλは、テンプレートマッチングと言語モデルの異なる標準化を説明するために、ノイズレベルに関するデータに基づいて経験的に決定することができる。λの通常の範囲は１．１から１．６である。
【００４６】
　最も可能性のある仮定ＨＬを識別するために、異なる仮定Ｈを探査するようスタックアルゴリズムを使用することができる。仮定の探査は、以下でさらに詳細に説明するようにグラフ検索問題（ｇｒａｐｈ　ｓｅａｃｈｉｎｇ　ｐｒｏｂｌｅｍ）として扱われる。
【００４７】
　グラフＧは、複数のエッジＥによって接続された複数の頂点Ｖを含むことができる。したがって、グラフＧは次のように示すことができる。
　　Ｇ＝（Ｖ，Ｅ）　　　　（１３）
【００４８】
　複数のエッジＥの各エッジｅは、複数の頂点Ｖの頂点ｖとｗを接続する。したがって、各エッジｅは次のように示すことができる。
　　ｅ＝（ｖ，ｗ）　　　　（１４）
　上式で、ｖおよびｗはエッジｅによって接続された開始頂点と終了頂点である。
【００４９】
　図２は、スタックグラフ２００を示す。図１に示すテキストフラグメントの場合、スタックグラフ２００は頂点２２０とエッジ２３０とを含む。各エッジ２３０は２つの頂点２２０を接続する。
【００５０】
　各エッジ２３０は文字１１０に関連付けられており、各頂点２２０は文字ストリングに沿ったｘ位置に関連付けられている。テキストフラグメント１００の場合、デコードプロセスは、左端文字１６０の左端エッジ１６２のｘ位置に対応する左端頂点２２１から始まる。デコードプロセスは、１つの頂点から別の頂点に右方向に、すなわち１文字ずつデコードして続行する。デコードプロセスは、右端文字１７０の右端エッジ１７２のｘ位置に相当する右端頂点２２２で終了する。したがって、各頂点２２０は、１つの頂点から後続頂点に移動することによって１つの文字をデコードする場合に、デコードプロセスのデコード状態を表す。
【００５１】
　左端頂点２２１はソース（ｓｏｕｒｃｅ）であり、右端頂点２２２はシンク（ｓｉｎｋ）である。ソース頂点２２１は、テキストフラグメント１００の開始点に関連付けられた頂点２２０の特別なタイプであり、したがってデコードプロセスの最初のデコード状態を表している。一方、シンク頂点２２１は、テキストフラグメントの実現可能な終了点に関連付けられた頂点２２０の特別なタイプであり、したがってデコードプロセスの実現可能な最後のデコード状態を表している。
【００５２】
　各エッジ２３０は１つの頂点２２０から後続頂点２２０への実現可能なパスであり、したがってデコードプロセスで１つの頂点２２０から次の頂点２２０への実現可能なデコードステップである。ソース２２１からシンク２２２への完全パスを形成するエッジのグループ２３１は、仮定Ｈすなわち、デコードプロセスの実現可能な解である。デコードの解は、ソースとシンクの間を接続する複数のエッジを含み、所望の合計の重要度を有する仮定Ｈを求めるスタックグラフによる検索を含むことができる。
【００５３】
　文字１１０は複数の実現可能なエッジ２３０に関連付けることができる。図２では、左端から３番目の文字１１２は、３番目の文字１１２の下で図２に示された４つのエッジ２３２に関連付けられる。これら４つのエッジは、３番目の文字１１２に対する最も可能性のあるデコードを示している。しかし、ｘまたはｇなどのさらに可能性の低いデコードを含む、グラフのすべてのエッジは示していない。また、３番目の文字１１２に関連付けられた４つのエッジ２３２のそれぞれは、２番目の文字１１３と３番目の文字１１２の間のｘ位置に関連付けられた先行頂点２２０に接続される。したがって、スタックグラフは木のような構造を有しており、そこでは１つのデコード状態の各頂点２２０が、１つのエッジを実現可能なテンプレートのそれぞれにマッチさせて、次のデコード状態の実現可能な複数の頂点２２０に分岐する。しかし、デコードのためにノードが等価である場合、それらのノードを接続することができる。例えば図２では、言語モデルが使用されていない時に、ノード２３３がその行の同一ｘ位置に対応する場合はそのノード２３３を結合することができる。ノードが結合される場合、図２の木のようなグラフは非循環グラフ（ａｎｃｙｃｌｉｃ　ｇｒａｐｈ）となる。
【００５４】
　スタックグラフ２００が非循環である場合、デコードプロセスは左から右への単方向で進む。したがって各エッジ２３０は単方向、すなわちエッジ２３０の矢印が示す方向に向いて木のような構造を展開する。
【００５５】
　図２では、各エッジ２３０はスコアインジケータ（ｓｃｏｒｅ　ｉｎｄｉｃａｔｏｒ）２４０に関連付けられている。スコアインジケータは、テンプレートインジケータ２４１と重要度インジケータ２４２とを含む。テンプレートインジケータ２４１は、受け取ったイメージ１００の文字１１０がマッチするテンプレート２５０を示す。重要度インジケータ２４２は、文字１１０とテンプレート１５０の間のマッチの測度すなわち重要度を示す。測度すなわち重要度は、したがって現在のイメージ部分と対応するテンプレートの間の対応の程度すなわちマッチの品質を示す。
【００５６】
　図２では、２番目の文字１１３が文字「ｈ」および「ｂ」に対するテンプレート１５０に最も近似している。２番目の文字が「ｈ」である重要度は０．１２であり、２番目の文字が「ｂ」である重要度は０．０３である。したがって、２番目の文字は「ｈ」である可能性の方が高い。
【００５７】
　２番目の文字が「ｈ」と識別されたパスを辿ると、３番目の文字が「ｅ」である重要度は０．０７であり、３番目の文字が「ｃ」である重要度は０．０５である。したがって、このパスを辿ると３番目の文字は「ｅ」である可能性の方が高い。同様に、２番目の文字が「ｂ」と識別されたパスを辿ると、３番目の文字が「ｅ」である重要度は０．０２であり、３番目の文字が「ｃ」である重要度は０．０１である。したがって、このパスを辿ると３番目の文字は「ｅ」である可能性の方が高い。しかし、文字「ｅ」と「ｃ」のどちらについても、２番目の文字が「ｈ」と識別されたパスに対する確率よりもそれらの確率の方が低い。
【００５８】
　各重要度インジケータ２４２は、テンプレートマッチングの確率の測度と、対応するテンプレートインジケータ２４１の言語内容とを示すことができる。重要度２４２を実施するために対数確率を使用すると便利な場合がしばしばある。
【００５９】
　文字に関連付けられた頂点ｖを次のように示すことができる。
　　Ｋ（ｖ）＝（ｘ，ｃ１，ｃ２，．．．，ｃｄ−１）　　　　　（１５）
【００６０】
　方程式（１５）で、ｘは文字のｘ座標であり、ストリングｃ１，ｃ２，．．．，ｃｄ−１は言語学的コンテキストすなわちｘ座標の左側のｄ−１でデコードされた文字である。方程式（１５）は次の形式で書き直すことができる。
　　Ｋ（ｖ）＝（Ｋｘ（ｖ），Ｋｃ（ｖ））　　　　　（１６）
　上式で、ＫＸ（ｖ）はＫ（ｖ）のＸ座標であり、ＫＣ（ｖ）＝Ｃ１，Ｃ２，．．．，Ｃｄ−１は頂点Ｋ（Ｖ）の言語学的コンテキストである。
【００６１】
　スタックアルゴリズムはグラフ全体を探査する必要はない。その代わりに、スタックグラフの有望な部分だけが探査される。この有望な部分は解を生成する可能性が最も高いスタックグラフの部分であると識別される。スタックグラフの有望な部分だけを探査することは、文書イメージのデコードの効率を考慮している。
【００６２】
　スタックグラフの一部は次の生成関数によって生成することができる。
　　ｇ（ｖ）＝｛ｗ１，ｗ２，ｗ３．．．｜（ｖ，ｗｋ）∈Ｅ｝　　　　（１７）
【００６３】
　方程式（１７）で定義された生成関数ｇは、頂点ｖに始まるすべてのエッジｅ、すなわちデコードプロセスに対するすべての実現可能な次の状態ｗｋを列挙する。Ｋ（ｖ）＝（ｘ，ｃ１，ｃ２，．．．，ｃｄ−１）の場合、Ｋ（ｗｋ）＝（ｘ＋ｗ（ｃｄ），ｃ２，ｃ３，．．．，）が、受け取ったイメージの現在の位置ｘから次の位置ｘ＋ｗ（ｃｄ）までの文字ｃｄをデコードすることに相当するならば、エッジｅは現在の頂点ｖから後続頂点ｗｋまでであると定義することができる。
【００６４】
　パスはエッジによってリンクされた頂点のリストであってよい。したがってパスは次のように示すことができる。
　　ｐ＝｛ｖ０，ｖ１，ｖ２，．．．ｖｎ｜ｅｉ＝（ｖｉ−１，ｖｉ）∈Ｅ｝　（１８）
　上式で、ｖ０，ｖ１，ｖ２，ｖｎ，ｖｉ−１およびｖｉは頂点である。
【００６５】
　スタックグラフを通過する異なるパスは、異なるデコード仮定Ｈに対応させることができる。図３は、スタックグラフ３００の仮定を示す。仮定３１０は、ソース頂点３５０からシンク頂点３９０への完全パスである。仮定３１０は、複数のエッジ３４０、３６２、または３８０を含む。各エッジ３４０または３８０は２つの頂点３４０または３７０を接続する。
【００６６】
　部分パス３２０は仮定３１０の一部である。部分パス３２０はソース頂点３５０から始まり、部分パス３２０の最終頂点３６１で終了する。
【００６７】
　部分パスの接尾部は、部分パスを対応する完全パスに変更する部分パスの残りの部分である。部分パス３２０の接尾部３６０は部分パス３２０の最終頂点３６１から始まり、シンク頂点３９０で終了する。
【００６８】
　上記のように、パスの重要度はパスに対応する仮定Ｈｐの対数確率に等しい。パスの仮定Ｈｐが個々のエッジを含むので、パスの重要度Ｗ（ｐ）は、次のパスを形成する個々のエッジの重要度Ｗ（ｖｉ，ｖｉ＋１）から決定される。
【００６９】
【数５】
2004078956.tif 000007
【００７０】
　各個別エッジの重要度Ｗ（ｖｉ，ｖｉ＋１）は、テンプレートマッチの尤度と言語モデルの尤度とを含むことができる。
　　Ｗ（ｖｉ，ｖｉ＋１）＝ＴＭ（ｉ）＋λＬＭ（ｉ）　　　　　（２０）
または
【数６】
2004078956.tif 000008
【００７１】
　修正変更されたスタックアルゴリズムは、解として所望のパスを求めてスタックグラフを検索する。所望のパスは最適なパスであってよい。例えば所望のパスは、すべてのパスの中で最大の重要度を有するパスであってよい。
【００７２】
　所望のパスを検索するために、修正変更されたスタックアルゴリズムは、完成時に大きな重要度を有するよう部分パスが推定されたポテンシャルに従ってキューに入れられる、優先キューＱｐを使用することができる。所望のパスは、所望の優先順位を有する部分パスとして決定される。部分パスのポテンシャルは、以下にさらに詳細に説明するように、推定された完成時の重要度を加えること、またはその部分パスに対する期待の重要度を減じることによって合わせられる部分パスの重要度であってよい。所望の優先順位の部分パスは、最大の推定ポテンシャルを有する部分パスであってよい。
【００７３】
　優先キューＱｐは、デコードの解を検索する際に反復的に使用することができる。最も有望なパス（すなわち最大ポテンシャルを有する部分パス）が優先キューＱｐから除去される。このパスの最終頂点がシンクである場合、このパスは完全である。それは優先キューで最も有望なパスだったので、それは最適なパスである。したがって、検索は完了する。そうでない場合、その部分パスはすべての実現可能な方法で次の頂点まで延長され、実現可能な次の頂点ごとに、次の頂点までの延長を有する元の部分パスに基づいて新しい部分パスが生成される。実現可能な新しい部分パスのすべてが配置され、優先キューＱｐに入れられる。優先キューＱｐは新しい部分パスを収容するために更新される。次の反復のために新たに列挙された最も有望なパスが優先キューＱｐから除去される。
【００７４】
　連想型マップ（ａｓｓｏｃｉａｔｉｖｅ　ｍａｐ）は、意味的に等価のパスを検出し、優先キューＱｐにあるパスを更新するために使用することができる。ハッシュテーブルは、優先キューＱｐにあるパスを比較し、更新するために使用することができる。ハッシュテーブルは、意味的に等価のパスを検出するためにも使用することができる。優先キューＱｐは、ハッシュテーブルが提供する機能を強化するためにヒープ（ｈｅａｐ）またはフィボナッチヒープ（Ｆｉｂｏｎａｃｃｉ　ｈｅａｐ）を使用して実施することができる。
【００７５】
　新しいパスが、優先キューＱｐに既にある古いパスの頂点まで延長する場合、その新しいパスはその古いパスに意味的に等価である場合がある。３つの異なる状態が考えられる。第１に、古いパスもその頂点で終了し、新しいパスが古いパスの重要度よりもさらに良好な、すなわちさらに大きな重要度を有する場合がある。この場合、古いパスは更新され、優先キューＱｐにある新しいパスに置き換えることができる。
【００７６】
　第２の状態では、古いパスもその頂点で終了し、新しいパスの重要度が古いパスの重要度よりも良好でない場合がある。この場合、新しいパスは破棄することができ、古いパスをその現在の位置で優先キューＱｐに残すことができる。
【００７７】
　第３の「二重延長」状態の場合、新しいパスは古いパスよりも良好な重要度を有するが、古いパスは、新しいパスが古いパスに結合または交差する頂点を通過してその先まで既に延長されている。すなわち、古いパスは少なくとも１回は優先キューから除去されており、少なくとも１つの追加頂点まで延長され、優先キューに再度配置されている。したがって、古いパスを優先キューで容易に更新し、置き換えることはできない。以下でさらに詳細に説明するように、この問題に対処するために、本発明による修正変更されたスタックアルゴリズムに特別な技術が導入される。
【００７８】
　スタックアルゴリズムを使用してスタックグラフを検索する際、図２を参照して上記のように、パスを木のような構成から動的に探査することができる。この木の各頂点を、１つの「後方」ポインタに関連付けることができる。この後方ポインタはパス上の直前の頂点を指し示す。同様に、順方向ポインタを頂点に関連付けることができる。したがって、「二重延長」状態では、古いパスの延長が識別され、置き換えられる。
【００７９】
　別法として、「二重延長」状態では、新しいパスを古いパスと共に優先キューＱｐに単に配置することができる。
【００８０】
　「二重延長」の場合、新しいパスは再実行キューＱｒに入れることができ、延長が古いパスの延長と置き換わるように処理される。再実行キューＱｒは優先キューＱｐと同様に構成することができるが、再実行キューＱｒは二重延長の状態から生成された新しいパスだけを列挙する。さらに、再実行キューＱｒは優先キューＱｐよりも前に処理することができる。
【００８１】
　新しい部分パスが複数の所望の部分パスのどれか１つと意味的に等価か否かを判定するために、新しい部分パスは複数の所望の部分パスと比較される。複数の所望の部分パスは、優先キューＱｐのすべての部分パス、優先キューＱｐのｎ個の最も有望な部分パス、または優先キューＱｐの１つの最も有望な部分パスであってよい。
【００８２】
　優先キューＱｐにあるすべての部分パスは方程式（１９）によって与えられた重要度を有する。確率または尤度は１よりも小さい値を有するので、各文字テンプレートマッチの対数尤度はパスの重要度に負項を寄与する。したがって、文字数がさらに少ないさらに短いパスは、より大きな重要度を有する傾向がある。したがって、長さが異なるパスの優先順位を決定する場合、それらのパスを比較するには調整が望ましい。
【００８３】
　調整された重要度Ｗａ（ｐ）を生成するために、パスの重要度Ｗ（ｐ）を重要度変更関数（ｗｅｉｇｈｔ−ａｌｔｅｒｉｎｇ　ｆｕｎｃｔｉｏｎ）Ｗｅ（ｐ）によって調整することができる。
　　Ｗａ（ｐ）＝Ｗ（ｐ）−Ｗｅ（ｐ）　　　　　（２２）
【００８４】
　方程式（２２）では、調整された重要度Ｗａ（ｐ）は実際の重要度Ｗ（ｐ）と重要度変更関数Ｗｅ（ｐ）の間で異なる。重要度変更関数Ｗｅ（ｐ）はパスに対する期待の重要度を定義する。パスは短いほど、重要度変更関数Ｗｅ（ｐ）に対してより大きな値を有する。その結果、短いパスの方が長いパスと比べて適切に重要度を付けられる。したがって、優先キューＱｐは調整された重要度Ｗａ（ｐ）の値によって順序付けることができる。
【００８５】
　部分パスは、予想重要度に基づいて優先キューＱｐに列挙することができる。部分パスをシンク頂点まで延長した完全パスｐに対する予想重要度Ｗｐは次のように定義される。
　　Ｗｐ（ｐ）＝Ｗ（ｐ）＋Ｗｆ（ｐ）　　　　（２３）
　上式で、Ｗｆ（ｐ）はパスの接尾部の重要度の推定値である。
【００８６】
　上記のように、接尾部は後に発生する完全パスの部分を表す、すなわち部分パスの最終頂点から始まる一群の頂点およびエッジである。したがって、優先キューＱｐは予想重要度Ｗｐ（ｐ）によって順序付けられる。
【００８７】
　Ｗｆ（ｐ）を決定するには、部分パスの最終頂点のｘ座標を使用することができる。したがって、パスの接尾部は、一群のエッジＥ（ｘ，ｐ）と定義される。各エッジＥ（ｘ，ｐ）は２つの頂点を、部分パスの最終頂点のｘ座標以上のｘ座標に接続する。
　　Ｅ（ｘ，ｐ）＝｛ｖｋ∈ｐ｜Ｋｘ（ｖｋ）≧ｘ｝　　　　　（２４）
　上式で、ｘは部分パスの最終頂点のｘ座標である。
【００８８】
　通常、１つの部分パスに対して複数の接尾部があり、完全パスの推定された重要度は最高の重要度を有する接尾部の重要度である。しかし、本発明者らは、（検索の目的で）最高の重要度を有する接尾部を知らない。以下でさらに詳細に説明するように、部分パスの接尾部の重要度ｐｊを推定するには、現在の最良の解であるアルゴリズムｐ’の前回の反復からのパスを使用する。
　　Ｗｆ（ｐｊ）＝Ｗ（Ｅ（ｘｊ，ｐ’））　　　　　（２５）
【００８９】
　上記のように、方程式（２５）の接尾部は、部分パス３２０の最終文字の最終頂点のｘ座標を有する点３６１から始まる。しかし、点３６１は、接尾部の重要度を推定するために使用された前回のパスｐ’では頂点から遠くにある場合がある。したがって、部分パスの優先順位を決定する際に所望の精度を有するために、次のような補間法を使用することができる。
　　Ｗｆ＝Ｗ（Ｅ（ｘｊ，ｐ’））＋Ｉ（ｘｊ，（ｖｋ−１，ｖｋ））　　　（２６）
　上式で、ｖｋは、部分パス３２０の最終頂点３６１のｘ座標ｘｊ以上のｘ座標を有するすべての頂点の中で最小のｘ座標を有するｐ’の頂点である。したがって、図３にエッジ３６２で示したパスｐ上のエッジｅ（ｖｋ−１，ｖｋ）は、最終頂点３６１のｘ座標ｘｊを交差する。したがって、部分パスの最終頂点３６１と次の頂点３６３の間の前回のパスｐ’の部分は、エッジｅ（ｖｋ−１，ｖｋ）を使用した補間法（ｉｎｔｅｒｐｏｌａｔｉｏｎ）によって得られる。
【００９０】
【数７】
2004078956.tif 000009
の場合、線形補間法（ｌｉｎｅａｒ　ｉｎｔｅｒｐｏｌａｔｉｏｎ）を使用することができる。
【００９１】
　デコードの品質を向上させるために、受け取ったイメージが、例えばコーヒーのしみなどによる歪み、または文書の綴じ目付近のコピーの不良のイメージの品質を含んでいる場合は特に、次の反復に対する仮定として１つの反復からの解を使用して、スタックアルゴリズムを反復的に適用することが望ましい。所望の品質の解を近似するために反復プロセスを使用することができる。各反復ｉに対して、次の反復の接尾部の推定値を定義するために、前回の反復ｐ［ｉ−１］の解を使用する場合、一連の解ｐ［１］，ｐ［２］，．．．，ｐ［ｉ］，．．．を得るためにスタックアルゴリズムを反復的に適用することができる。すなわち、
【数８】
2004078956.tif 000010
である。
【００９２】
　方程式（２２）は反復プロセスで使用することができる。すなわち、
　　Ｗａ［ｉ］（ｐｊ）＝Ｗ（ｐｊ）−Ｗｅ［ｉ］Ｉ（ｐｊ）　　（２９）
この結果、前回の反復の解は次の反復の期待値となる。すなわち、
【数９】
2004078956.tif 000011
　上式では、
【数１０】
2004078956.tif 000012
であり、また、
【数１１】
2004078956.tif 000013
である。方程式（２９）〜（３２）に示すように、Ｗｅはｐの尤度の補足部分である。
方程式（２９）は次のように修正変更することができる。
【００９３】
　　Ｗａ［ｉ］（ｐｊ）＝Ｗ（ｐｊ）−αＷｅ［ｉ］Ｉ（ｐｊ）　　　　　（３３）
　上式で、αは所望の品質の解ｐへの収束を促進するパラメータである。
【００９４】
　パラメータαは、例えばα＝１．０１のように１よりも僅かに大きい値であってよい。
【００９５】
　高ノイズの状況下などのある状況では、反復プロセスはエクスプロシブレジーム（ｅｘｐｌｏｓｉｖｅ　ｒｅｇｉｍｅ）に発展する場合がある。より良好なパスｐ［ｉ］が計算されると、それらのパスは、通常はより有利なさらに短いパスの方向で部分パスのポテンシャルの推定値に影響を与える。エクスプロシブレジームでは、仮定を、グラフを通して延長するために十分有望であると識別することはできない。その代わり、多数の短い仮定が処理される。その結果、元々部分スタックグラフだけを対象とした検索が、スタックグラフ全体の完全な消耗的な検索に発展する傾向がある。したがって、全体的な費用は瞬く間に法外な値に跳ね上がる。その結果、スタックグラフを通したパスの検索をエクスプロシブレジームに入れることは、望ましくなく、防止されるべきである。
【００９６】
　本発明による修正変更されたスタックアルゴリズムを使用することは、検索プロセスが反復プロセスのエクスプロシブレジームにいつ入ったかを検出するテストを含むことができる。エクスプロシブレジームに入ったことが検出されると、検索は終了する。そのような状況では、検索が終了する前の最後の成功した反復ステップで決定された解ｐ［ｉ］は、この解が所望の品質と一致していなくても検索プロセスの最終解として保存される。
【００９７】
　本発明による修正変更されたスタックアルゴリズムを使用することは、境界近似法（ｂｏｕｎｄｉｎｇ　ａｐｐｒｏａｃｈ）で仮の重要度を使用することを含むことができる。この境界近似法は、実際のテンプレートマッチ値の上限であるテンプレートマッチの値の安価で高速な決定を使用する。これは、部分パスの最終文字に対するテンプレートマッチの上限を使用して部分パスに対する仮の重要度を定義することによって実施することができる。部分パスは、部分パスの仮の重要度に従って優先キューＱｐに列挙される。部分パスの実際の重要度の高価な決定は、部分パスが、対応する仮の重要度に基づいて、優先キューの最も有望なパスであることが判明した場合にのみ行われる。したがって、この方式は、部分パスに対して決定された仮の重要度に鑑みて最適であると判明していない部分パスの実際の重要度の高価な決定の分量を低減する。
【００９８】
　図４は、パス全体を暫定的にスコアされるように、スコアエッジ３４２に使用される上限を示している。
【００９９】
　したがって、仮のパス重要度は、次のように、部分パスの重要度と延長の上限の重要度の和として部分パスに対して定義される。
【数１２】
2004078956.tif 000014
　上式で、Ｗ’（ｖｎ−１，ｖｎ）≧Ｗ’（ｖｎ−１，ｖｎ）　　　　（３５）
である。
【０１００】
　方程式（３４）に示すように、パスの仮の重要度は、パスの実際のエッジと、少なくとも延長エッジの実際の重要度と同程度の重要度を有する延長エッジとを含む。
【０１０１】
　頂点ｖｎ−１へのパスが次の頂点ｖｎに延長されている場合、エッジ（ｖｎ−１、ｖｎ）のｘ位置に対応するイメージの部分に対するテンプレートマッチ値が既に決定されているか否かを判定することができる。テンプレートマッチ値が既に決定されている場合、以前のマッチングに基づく実際の重要度がパスに割り当てられ、ｖｎ−１からｖｎへの延長を有するパスが優先キューに加えられる。一方、テンプレートマッチ値がまだ決定されていない場合、仮の重要度を生成するために頂点ｖｎ−１とｖｎの間に延長するエッジに対して安価な上限の重要度が使用され、ｖｎ−１からｖｎへの延長を有するパスが仮の重要度と共に優先キューに追加される。延長のために優先キューＱｐから取られた暫定的に重要度を付けたパスだけが実際の重要度で最決定され、再度キューに入れられる。
【０１０２】
　暫定的に重要度を付けたパスは、実際には、ハッシュテーブルの使用によって上記で説明した二重パス低減プロセスなどの二重パス低減プロセスが実行される前に重要度が付けられる。意味的に等価で、実際に重要度が付けられたパスの重要度よりも低い上限を有する新しく延長された仮のパスを破棄することができる。
【０１０３】
　図５は、部分パスの仮の重要度に従って部分パスをキューに入れる方法を概説する流れ図である。ステップＳ１００から始まり、本方法の動作はステップＳ１１０に進み、そこで部分パスが考慮される。次にステップＳ１２０で、部分パスの複数の実現可能な延長エッジの重要度の上限が決定される。次いでステップＳ１３０で、部分パスの仮の重要度が決定される。次にステップＳ１４０で、部分パスは、その部分パスの決定された仮の重要度に従ってキューに入れられる。動作はステップＳ１５０に進み、そこで本方法の動作は終了する。
【０１０４】
　図６は、優先キューで部分パスを探査する方法を概説する流れ図である。ステップＳ２００から始まり、本方法の動作はステップＳ２１０に進み、そこで所望の優先順位の部分パスが優先キューから除去される。次いでステップＳ２２０で、部分パスの仮の重要度に従ってその部分パスが優先キューに入れられているか否かが判定される。入れられていない場合、動作はステップＳ２５０にジャンプする。入れられている場合、動作はステップＳ２３０に進み、そこで仮の重要度の代わりに部分パスの実際の重要度が決定される。次にステップＳ２４０で、部分パスに対して決定された実際の重要度に従ってその部分パスが優先キューに再度入れられる。動作はステップＳ２１０に戻る。
【０１０５】
　ステップＳ２５０で、解を求めて部分パスが探査される。次にステップＳ２６０で、解の探査が成功したか否かが判定される。成功した場合、動作はステップＳ２７０にジャンプし、そこで本方法の動作は終了する。成功しなかった場合、動作はステップＳ２１０に戻る。
【０１０６】
　図７は、重複した仮定を低減する方法を概説する流れ図である。ステップＳ３００から始まり、本方法の動作はステップＳ３１０に進み、そこで少なくとも１つの重複した第２のパスを有する第１の部分パスが選択される。様々な実施形態例で、第２のパスが１つだけ選択される。次にステップＳ３１５で、第２の部分パスが優先キューから選択される。次いでステップＳ３２０で、第１の部分パスが第２の部分パスに意味的に等価であるか否かが判定される。等価である場合、動作はＳ３３５にジャンプする。等価でない場合、動作はステップＳ３２５に進む。
【０１０７】
　ステップＳ３２５で、選択される可能性のある優先キューに次の重複した第２の部分パスがあるか否かが判定される。ない場合、動作はステップＳ３６５にジャンプし、そこで本方法の動作は終了する。ある場合、動作はステップＳ３３０に戻り、そこで次の重複した第２の部分パスが優先キューから選択される。次いで動作はステップＳ３２０に戻る。
【０１０８】
　ステップＳ３３５で、第２の部分パスが延長されているか否かが判定される。延長されていない場合、動作はステップＳ３５０にジャンプする。延長されている場合、動作はステップＳ３４０に進む。ステップＳ３４０で、第１の部分パスは再実行キューに入れられる。次にステップＳ３４５で、再実行キューが処理され、第１の部分パスが延長される。これによって、再実行キューに追加のパスが加えられる場合がある。第２の部分パスのすべての延長が第１の部分パスの延長によって置き変えられると、再実行キューは空になる。動作は次いでステップＳ３６５にジャンプする。
【０１０９】
　ステップＳ３５０で、第１の部分パスの重要度が第２の部分パスの重要度よりも大きいか否かが判定される。大きい場合、動作はステップＳ３６０にジャンプする。大きくない場合、動作はステップＳ３５５に進む。ステップＳ３５５で、第１の部分パスが破棄される。動作は次いでステップＳ３６５にジャンプする。反対にステップＳ３６０で、第２の部分パスは第１の部分パスによって置き換えられる。動作は次いでステップＳ３６５に進み、そこで本方法の動作は終了する。
【０１１０】
　図８は、改善された、すなわち最適なデコードの解を得るためにスタックアルゴリズムを反復的に適用する方法を概説する流れ図である。ステップＳ４００から始まり、本方法の動作はステップＳ４１０に進み、そこで部分パスに対する仮定が現在の仮定として選択される。次にステップＳ４２０で、スタックアルゴリズムが適用される。次いでステップＳ４３０で、スタックアルゴリズムがエクスプロシブレジームにあるか否かが判定される。エクスプロシブレジームにある場合、動作はステップＳ４７０にジャンプする。ない場合、動作はステップＳ４４０に進む。
【０１１１】
　ステップＳ４４０で、スタックアルゴリズムを現在のスタックグラフに適用することによって解が得られる。次にステップＳ４５０で、解が所望の品質か否かが判定される。解が所望の品質でない場合、動作はステップＳ４６０に進み、そこで現在の仮定が解によって置き換えられる。すなわち、解は現在の仮定になる。次いで動作はステップＳ４２０に戻る。解が所望の品質である場合、動作はステップＳ４８０にジャンプする。
【０１１２】
　反対にステップＳ４７０で、前回の仮定が解として使用される。動作は次いでステップＳ４８０に進み、そこで本方法の動作は終了する。
【０１１３】
　図９〜１１は、本発明による修正変更されたスタックアルゴリズムを使用した文書イメージをデコードする方法を概説する流れ図である。ステップＳ５００から始まり、本方法の動作はステップＳ５０５に進み、そこで前回の完全パスＰ’は初期化される。言語モデルを使用せずに別の方法によって得られた完全パスを前回の完全パスＰ’として使用してもよい。前回の完全パスＰ’は、無造作に仮定されたものであってもよい。仮定された前回の完全パスＰ’の品質は最終的な出力に必須のものではない。なぜならば、この仮定された前回の完全パスＰ’は本方法の動作が進むとすぐに置き換えられるからである。
【０１１４】
　次にステップＳ５１０で、新しいパスＰを見つけるためにスタックアルゴリズムが適用される。このステップは図１０を参照しながら以下でさらに詳細に説明する。次いでステップＳ５１５で、スタックアルゴリズムがエクスプロードしたか否かが判定される。スタックアルゴリズムがステップＳ５１０でエクスプロードしたとステップＳ５１５で判定された場合、動作はステップＳ５２０に進み、そこで前回の完全パスＰ’が動作の出力として戻され、本方法の動作は終了する。スタックアルゴリズムがステップＳ５１０でエクスプロードしなかったとステップＳ５１５で判定された場合、動作はステップＳ５２５にジャンプする。
【０１１５】
　ステップＳ５２５で、新しい完全パスＰが所望の品質であるか否かが判定される。新しい完全パスＰが所望の品質である場合、動作はステップＳ５３０に進み、そこで動作は完全パスＰを本方法の動作の出力として戻し、本方法の動作は終了する。一方、新しい完全パスＰが所望の品質でないとステップＳ５２５で判定された場合、動作はステップＳ５３５にジャンプする。ステップＳ５３５で、新しい完全パスＰは前回の完全パスＰ’と置き換わり、動作はステップＳ５１０に戻る。
【０１１６】
　図１０は、図９のステップＳ５１０をさらに詳細に示す。図１０に示すように、動作はステップＳ５４０に進む。
【０１１７】
　ステップＳ５４０で、メインキューがソースノードによって優先キューとして初期化され、再実行キューは空として初期化される。次にステップＳ５４５で、再実行キューが空でない場合は、最も優先順位の高いパスが再実行キューから除去される。再実行キューが空の場合、最も優先順位の高いパスがメインキューから除去される。
【０１１８】
　次にステップＳ５５０で、除去されたパスが暫定的にスコアされたか否かが判定される。除去されたパスが暫定的にスコアされていると判定された場合、動作はステップＳ５５５に進み、そこで除去されたパスが再度スコアされて再度キューに入れられ、動作はステップＳ５４５に戻る。一方、除去されたパスが暫定的にスコアされていないと判定された場合、動作はステップＳ５６０にジャンプする。
【０１１９】
　ステップＳ５６０で、シンクに達しているか否かが判定される。シンクに達している場合、動作はステップＳ５６５にジャンプし、そこで除去されたパスは動作の出力として戻され、本方法の動作は図９のステップＳ５１０に戻る。シンクに達していない場合、動作はステップＳ５７０に進む。
【０１２０】
　ステップＳ５７０で、スタックアルゴリズムがエクスプロシブレジームにあるか否かが判定される。エクスプロシブレジームにある場合、動作はステップＳ７５５にジャンプし、そこで本方法の動作は、スタックアルゴリズムがエクスプロードしたという指示を伴い図９のステップＳ５１０に戻る。エクスプロシブレジームにない場合、動作はステップＳ５８０に進む。
【０１２１】
　ステップＳ５８０で、除去されたパスへのすべての延長が生成され、前回のパスＰ’からの重要度を使用して暫定的にスコアされる。次いでステップＳ５８５で、延長に対する意味的等価が検出され、それに従って、以下で図１１を参照しながらさらに詳細に説明するように延長がキューに入れられる。動作は次いでステップＳ５４５に戻る。
【０１２２】
　図１１は、図１０のステップＳ５８５をさらに詳細に示す。図１１に示すように、動作はステップＳ６００に進む。
【０１２３】
　ステップＳ６００で、ノードへの部分パスが前に処理されているか否かが判定される。処理されている場合、動作はステップＳ６１５に進む。処理されていない場合、動作はステップＳ６１０にジャンプし、そこで部分パスがメインキューに入れられ、動作は図１０のステップＳ５８５に戻る。
【０１２４】
　ステップＳ６１５で、部分パスのスコアが前に処理されたノードのスコアよりも良いか否かが判定される。部分パスのスコアが前に処理されたノードのスコアよりも良い場合、動作はステップＳ６２５に進む。部分パスのスコアが前に処理されたノードのスコアよりも良くない場合、動作はステップＳ６２０にジャンプし、そこで部分パスが破棄され、動作は図１０のステップＳ５８５に戻る。
【０１２５】
　ステップＳ６２５で、前に処理されたノードがまだメインキューにあるか否かが判定される。まだメインキューにある場合、動作はステップＳ６３０に進む。もうメインキューにない場合、動作はステップＳ６３５にジャンプし、そこで部分パスは再実行キューに入れられ、動作は図１０のステップＳ５８５に戻る。
【０１２６】
　ステップＳ６３０で、前に処理されたノードに対するメインキューのキューエントリは部分パスによって置き換えられ、メインキューにあるこのパスの重要度が更新される。その後、本方法の動作は図１０のステップＳ５８５に戻る。
【０１２７】
　図１２は、文書イメージデコードシステム４００の概要を示すブロック図である。文書イメージデコードシステム４００は、入出力（Ｉ／Ｏ）インターフェース４１０、コントローラ４２０、メモリ４３０、グラフ検索回路（ｇｒａｐｈ　ｓｅａｒｃｈｉｎｇ　ｃｉｒｃｕｉｔ）、ルーチンまたはアプリケーション４４０、重要度決定回路（ｗｅｉｇｈｔ　ｄｅｔｅｒｍｉｎｉｎｇ　ｃｉｒｃｕｉｔ）、ルーチンまたはアプリケーション４５０、キューイング回路（ｑｕｅｕｉｎｇ　ｃｉｒｃｕｉｔ）、ルーチンまたはアプリケーション４６０、等価決定回路（ｅｑｕｉｖａｌｅｎｃｅ　ｄｅｔｅｒｍｉｎｉｎｇ　ｃｉｒｃｕｉｔ）、ルーチンまたはアプリケーション４７０、上限決定回路（ｕｐｐｅｒ　ｂｏｕｎｄ　ｄｅｔｅｒｍｉｎｉｎｇ　ｃｉｒｃｕｉｔ）、ルーチンまたはアプリケーション４８０、反復回路（ｉｔｅｒａｔｉｏｎ　ｃｉｒｃｕｉｔ）、ルーチンまたはアプリケーション４９０、および／またはエクスプロシブレジーム検出回路（ｅｘｐｌｏｓｉｖｅ　ｒｅｇｉｍｅ　ｄｅｔｅｒｍｉｎｉｎｇ　ｃｉｒｃｕｉｔ）、ルーチンまたはアプリケーション５００の１つまたは複数を含んでおり、これらはそれぞれに１つまたは複数の制御および／またはデータバスおよび／または１つまたは複数のアプリケーションプログラミングインターフェース４０５によって相互接続されている。
【０１２８】
　文書イメージデコードシステム４００は、プログラミングされた汎用コンピュータで実施される。しかし、図５〜１１に示す流れ図を実施することができる有限状態機械を実現できる任意のデバイスを、文書イメージデコードシステム４００を実施するために使用することができる。
【０１２９】
　Ｉ／Ｏインターフェース４１０は、文書イメージデコードシステム４００の外部と対話する。例えば、Ｉ／Ｏインターフェース４１０はリンク６１０を介してイメージデータソース６００からイメージを受け取る。Ｉ／Ｏインターフェース４１０はまた、リンク７１０を介してデータシンク７００に解を出力する。
【０１３０】
　メモリ４３０は、変更可能な揮発性または不揮発性メモリまたは変更不可能な、すなわち固定されているメモリの任意の適切な組み合わせを使用して実施することができる。メモリ４３０は、Ｉ／Ｏインターフェース４１０が受け取ったイメージデータのような、Ｉ／Ｏインターフェース４１０から受け取った情報を記憶する。メモリ４３０は、文書イメージデコードプロセスの期間中、すなわちその中間ステップで文書イメージデコードシステム４００の回路、ルーチンまたはアプリケーション４４０〜５００の様々な回路、ルーチンまたはアプリケーションからの情報および／またはデータも記憶する。
【０１３１】
　メモリ４３０は、受け取ったイメージを記憶するイメージ部分４３１、スタックグラフの頂点、エッジなどを記憶するグラフィック構成部分４３２、エッジ、パス、接尾部などの重要度および仮の重要度を記憶する重要度部分４３３、優先キューに関する情報を記憶する優先キュー部分４３４、再実行キューに関する情報を記憶する再実行キュー部分４３５、受け取った文書イメージから確認されるテキストストリングなどのデコードの解を記憶する解部分４３６、および／または反復プロセスで使用される所望の品質のような品質に関する必要条件を記憶する品質部分４３６の１つまたは複数を含む。
【０１３２】
　１つまたは複数の制御および／またはデータバスおよび／またはアプリケーションプログラミングインターフェース４０５の１つまたは複数は、文書イメージデコードシステム４００の回路、ルーチンまたはアプリケーション４４０〜５００の様々な回路、ルーチンまたはアプリケーション間で通信およびデータ転送を実現する。コントローラ４２０は、文書イメージデコードシステム４００の回路、ルーチンまたはアプリケーション４４０〜５００の様々な回路、ルーチンまたはアプリケーションに命令を提供する。
【０１３３】
　グラフ検索回路、ルーチンまたはアプリケーション４４０は、部分パスを探査し、スタックグラフで確認されたテキストストリングなどの解を探す。重要度決定回路、ルーチンまたはアプリケーション４５０は、テンプレートマッチング成分、言語モデル成分、補間法および／またはパラメータλおよび／またはαを決定することを含めて、様々なパスに対する重要度を決定する。キューイング回路、ルーチンまたはアプリケーション４６０は、様々なパスを、重要度および仮の重要度などの様々な基準に従って、優先キューおよび再実行キューなどの様々なキューに入れる。
【０１３４】
　等価決定回路、ルーチンまたはアプリケーション４７０は、第１のパスが第２のパスに意味的に等価であるか否かを判定し、第１のパスが第２のパスに意味的に等価である場合、第１のパスを破棄するか、または優先キューの第２のパスを第１のパスで置き換えるかを判断する。上限回路、ルーチンまたはアプリケーション４８０は、部分パスの複数の実現可能な延長されたパスの重要度の上限を決定する。反復回路、ルーチンまたはアプリケーション４９０は、仮定を生成すること、解の品質を確認すること、および仮定を解によって置き換えることを含めて反復プロセスを管理する。エクスプロシブレジーム検出回路、ルーチンまたはアプリケーション５００は、スタックアルゴリズムがエクスプロシブレジームにあるか否かを検出し、スタックアルゴリズムがエクスプロシブレジームにある場合、スタックアルゴリズムのアプリケーションを終了し、最後の成功した解を保持する。
【０１３５】
　ユーザは、受け取った文書イメージから確認されたテキストストリングを生成するために、文書イメージデコードシステム４００を使用することができる。文書イメージデコードシステム４００のＩ／Ｏインターフェース４１０は、リンク６１０を介してイメージデータソース６００から文書イメージデータを受け取り、受け取った文書イメージデータをイメージ部分４３１に記憶する。グラフ検索回路、ルーチンまたはアプリケーション４４０は、受け取った文書イメージからスタックグラフを生成し、生成されたスタックグラフ内で部分パスを検索するために、文書イメージデコードと修正変更されたスタックアルゴリズムとを使用する。重要度決定回路、ルーチンまたはアプリケーション４５０は、部分パスごとの重要度を決定する。キューイング回路、ルーチンまたはアプリケーション４６０は、部分パスの重要度に従って様々な部分パスを優先キューに入れ、更新された優先キューを優先キュー部分４３４に記憶する。グラフ検索の結果は、グラフ構成メモリ４３２に記憶される。決定された重要度は重要度部分４３３に記憶される。
【０１３６】
　上限回路、ルーチンまたはアプリケーション４８０は、部分パスに対して複数の実現可能な延長するエッジの重要度の上限を決定する。新しい部分パスに関して、重要度決定回路、ルーチンまたはアプリケーション４５０は、部分パスの重要度と、部分パスの複数の実現可能な延長するエッジの重要度の上限とに基づいて、部分パスに対する仮の重要度を決定する。キューイング回路、ルーチンまたはアプリケーション４６０は、部分パスの仮の重要度に従って部分パスをキューに入れ、更新された優先キューを優先キュー部分４３４に記憶する。
【０１３７】
　グラフ検索回路、ルーチンまたはアプリケーション４４０は、所望の優先順位の部分パスを優先キュー部分４３４に記憶されている優先キューから除去する。キューイング回路、ルーチンまたはアプリケーション４６０は、部分パスの仮の重要度に従って部分パスがキューに入れられているか否かを判定する。キューイング回路、ルーチンまたはアプリケーション４６０が、部分パスの仮の重要度に従って部分パスがキューに入れられていると判定した場合、重要度決定回路、ルーチンまたはアプリケーション４５０は、その部分パスの実際の重要度を決定する。キューイング回路、ルーチンまたはアプリケーション４６０は、重要度決定回路、ルーチンまたはアプリケーション４５０が決定した部分パスの実際の重要度に従って部分パスを優先キューに再度入れる。
【０１３８】
　一方、キューイング回路、ルーチンまたはアプリケーション４６０が、部分パスの仮の重要度に従って部分パスがキューに入れられていないと判定した場合、グラフ検索回路、ルーチンまたはアプリケーション４４０は、その部分パスに対する解を探査する。その探査が成功した場合、グラフ検索回路、ルーチンまたはアプリケーション４４０は探査を停止する。グラフ検索回路、ルーチンまたはアプリケーション４４０がその探査は成功しなかったと判定した場合、グラフ検索回路、ルーチンまたはアプリケーション４４０は、所望の優先順位を有する次の部分パスを選択し、選択した次の部分パスの探査を繰り返すために優先キュー部分４３４に戻る。
【０１３９】
　等価決定回路、ルーチンまたはアプリケーション４７０は、優先キューの第１の部分パスと第２の部分パスを比較する。等価決定回路、ルーチンまたはアプリケーション４７０は、第１の部分パスが第２の部分パスと意味的に等価か否かを判定する。等価決定回路、ルーチンまたはアプリケーション４７０が、第１の部分パスが第２の部分パスと意味的に等価でないと判定した場合、等価決定回路、ルーチンまたはアプリケーション４７０は、第１の部分パスが各第２の部分パスと比較されるまで優先キューの次の第２の部分パスを選択する。
【０１４０】
　第１の部分パスが現在の選択された第２の部分パスと意味的に等価であると判定されるたび、等価決定回路、ルーチンまたはアプリケーション４７０は、第１の部分パスの重要度を現在の第２の部分パスの重要度と比較する。第１の部分パスの重要度が現在の第２の部分パスの重要度よりも大きくない場合、等価決定回路、ルーチンまたはアプリケーション４７０は第１の部分パスを破棄する。この場合、第１の部分パスが元々優先キューにあった場合、キューイング回路、ルーチンまたはアプリケーション４６０は、優先キューを更新し、更新した優先キューを優先キューメモリ４３４に記憶する。
【０１４１】
　一方、第１の部分パスの重要度が第２の部分パスの重要度よりも大きい場合、等価決定回路、ルーチンまたはアプリケーション４７０は、グラフ構成メモリ４３２に記憶されている情報に基づいて、第２の部分パスが延長されているか否かを判定する。等価決定回路、ルーチンまたはアプリケーション４７０が、第２の部分パスが延長されていると判定した場合、キューイング回路、ルーチンまたはアプリケーション４６０は、第１の部分パスを再実行キューに入れ、再実行キューの情報を再実行キューメモリ４３５に記憶する。等価決定回路、ルーチンまたはアプリケーション４７０が、第２の部分パスが延長されていないと判定した場合、等価決定回路、ルーチンまたはアプリケーション４７０は、第２の部分パスを第１の部分パスによって置き換える。したがって、キューイング回路、ルーチンまたはアプリケーション４６０は、優先キューを更新し、更新した優先キューを優先キューメモリ４３４に記憶する。
【０１４２】
　第１の部分パスが再実行キューに列挙されている場合、グラフ検索回路、ルーチンまたはアプリケーション４４０は、再実行キューに列挙されている第１の部分パスを探査する。重要度決定回路、ルーチンまたはアプリケーション４５０は、延長された第１の部分パスの重要度を決定する。キューイング回路、ルーチンまたはアプリケーション４６０は、延長された第２の部分パスを置き換えるために、延長された第１の部分パスを優先キューに入れ、更新された優先キューを優先キューメモリ４３４に記憶する。
【図面の簡単な説明】
【０１４３】
【図１】デコードのフレームワークを示す図である。
【図２】図１に示すテキストフラグメントのスタックグラフを示す図である。
【図３】スタックグラフの仮定を示す図である。
【図４】部分パスの実現可能な延長を示す図である。
【図５】部分パスをキューに入れる方法の概要を示す流れ図である。
【図６】部分パスを探査する方法の概要を示す流れ図である。
【図７】重複した仮定を低減する方法の概要を示す流れ図である。
【図８】スタックアルゴリズムの適用を反復する方法の概要を示す流れ図である。
【図９】文書イメージデコードの方法の概要を示す流れ図である。
【図１０】文書イメージデコードの方法の概要を示す流れ図である。
【図１１】文書イメージデコードの方法の概要を示す流れ図である。
【図１２】文書イメージデコードシステムのブロック図である。
【符号の説明】
【０１４４】
　４１０　Ｉ／Ｏインターフェース、４２０　コントローラ、４３０　メモリ、４４０　グラフ検索回路・ルーチンまたはアプリケーション、４５０　重要度決定回路・ルーチンまたはアプリケーション、４６０　キューイング回路・ルーチンまたはアプリケーション、４７０　等価決定回路・ルーチンまたはアプリケーション、４８０　上限決定回路・ルーチンまたはアプリケーション、４９０　反復回路・ルーチンまたはアプリケーション、５００　エクスプロシブレジーム検出回路・ルーチンまたはアプリケーション、６００　データソース、７００　データシンク。
【図１】
2004078956.tif 000015
【図２】
2004078956.tif 000016
【図３】
2004078956.tif 000017
【図４】
2004078956.tif 000018
【図５】
2004078956.tif 000019
【図６】
2004078956.tif 000020
【図７】
2004078956.tif 000021
【図８】
2004078956.tif 000022
【図９】
2004078956.tif 000023
【図１０】
2004078956.tif 000024
【図１１】
2004078956.tif 000025
【図１２】
2004078956.tif 000026