(57)【特許請求の範囲】
【請求項１】
ハードコピー・ドキュメント上に表現されるべき、人間により可読である情報を有する第１のチャネルを提供する記号データの一次セットを識別するステップと、
前記ハードコピー・ドキュメント上に表現されるべき、機械により可読である情報を有する第２のチャネルを提供する符号化データの二次セットを前記記号データの一次セットから計算するステップと、
を含み、c1, c2, c3, …, ci-1, ci, ci+1, …, cnと順序付けられた記号のセットを有する前記記号データの一次セットの選択された行に対して、前記計算するステップがさらに、
少なくとも前記選択された行のカレント記号ciと、先に計算されたハッシュhi-1と、の関数であるハッシュhiを生成する状態変更関数Hによって、前記選択された行の各記号のハッシュを順次計算するステップと、
少なくとも計算された前記ハッシュhiの関数であるガード値giを生成するガード抽出関数Gによって、前記選択された行の各記号のための１セットのガード値を計算し、該ガード値によって該二次セットを増補するステップと、
を含み、
前記二次チャネルは符号化され、
c1, c2, c3, …, ci-1, ci, ci+1, …, cnは文字である、
ハードコピー・ドキュメントのための画像データ生成方法。
【請求項２】
前記抽出関数Gは、前記計算された前記ハッシュhiと、ビット・セレクタqiと、の関数であるガード値giを生成する、請求項１に記載の方法。
【請求項３】
ハードコピー・ドキュメント上に表現されるべき、人間により可読である情報を有する第１のチャネルを提供する記号データの一次セットを識別するための手段と、
前記ハードコピー・ドキュメント上に表現されるべき、機械により可読である情報を有する第２のチャネルを提供する符号化データの二次セットを前記記号データの一次セットから計算するための手段と、
を含み、c1, c2, c3, …, ci-1, ci, ci+1, …, cnと順序付けられた記号のセットを有する前記記号データの一次セットの選択された行に対して、前記計算するための手段がさらに、
少なくとも前記選択された行のカレント記号ciと、先に計算されたハッシュhi-1と、の関数であるハッシュhiを生成する状態変更関数Hによって、前記選択された行の各記号のハッシュを順次計算するための手段と、
少なくとも計算された前記ハッシュhiの関数であるガード値giを生成するガード抽出関数Gによって、前記選択された行の各記号のための１セットのガード値を計算し、該ガード値によって該二次セットを増補するための手段と、
を含み、
前記二次チャネルは符号化され、
c1, c2, c3, …, ci-1, ci, ci+1, …, cnは文字である、
ハードコピー・ドキュメントのための画像データ生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、概してドキュメント画像符号化及び復号化に関し、より詳細には、光学文字認識（ＯＣＲ）の精度を向上させるための方法及び装置に関する。
【０００２】
【従来の技術】
入力スキャナは、ハードコピー・ドキュメントを電子ドキュメント処理システムにアップロードするために開発された。これらのスキャナは一般に、ハードコピー・ドキュメントの外観をラスタ・フォーマットのデジタル・データストリームに変換し、それによって、ハードコピー・ドキュメントの外観を表すビットマップ表現をもたらす。ScanSoft社により製作されるTextbridge等のＯＣＲシステムは、ビットマップ・ドキュメントの外観を、対応する記号的な符号に変換する。残念ながら、特定のビットマップ・パターンと、対応するドキュメント符号化（例えばASCII）との間の相関関係を推測する際に、ＯＣＲシステムはエラーを起こすことから免れない。
【０００３】
この問題は、混同される可能性（確率）の高い文字（例えば１、｜及びＩ）に対して明確に異なる印刷特徴を与えるＯＣＲ−Ｂフォント等の特殊なフォントをデザインすることにより対処されている。これは、ＯＣＲシステムが、ビットマップ・パターンと、それに対応するドキュメント符号化との間の相関関係をより正確に推測することを可能にする。更に、Plumb他は、「ＯＣＲを介してソース・コードをパブリッシュするためのツール（Tools for Publishing Source Code via OCR）」（1997年）において、スペース及びタブをプリント可能な文字に置換することによる、ハードコピー・ドキュメントの一次チャネルの印刷を開示している。また、米国特許第4,105,997号は、ＯＣＲの最中に、エラーの位置を確認するためにドキュメント内のテキストのチェックサムを用いる方法を開示している。
【０００４】
この問題はまた、米国特許第5,486,686号でも言及されている。この特許は、人間が読むことが可能なドキュメントのハードコピー表現が、このドキュメント及び／又はそのコンテンツの全部又は一部の電子表現と一体化されるドキュメント処理システムを開示している。この電子表現は、ドキュメントに関する情報又はドキュメントから計算される情報を符号化する「アシスト・チャネル」を提供する。アシスト・チャネルは、プリント可能であり且つ機械で読み取ることができるコードを用いて定義される。例示された一例において、アシスト・チャネルは、ドキュメントの下部で小さいグリフ・コードを用いて定義されることが可能である。
【０００５】
より詳細には、ハードコピー・ドキュメントの「アシスト・チャネル」は、一次チャネルのコンテンツを復号化する際にＯＣＲアプリケーションを支援するサイド情報の機械可読な符号化である。ハードコピー・ドキュメントの「一次チャネル」は、人間が読むことが可能なドキュメントの情報を含む。変更されることができず、ＯＣＲ処理でややエラーを起こしやすい一次チャネルは、ドキュメントの大部分の情報コンテンツを保持する。アシスト・チャネルの１つの用途は、例えば、米国特許第5,625,721号、第5,748,807号、及び第6,047,093号に開示されるように、一次チャネルのコンテンツを復号化する際に、ＯＣＲアプリケーションの誤りを確認するのを支援する情報を符号化することである。
【０００６】
【発明が解決しようとする課題】
アシスト・チャネルを用いてＯＣＲ処理を向上させるこれらの進歩を伴ってさえも、アシスト・チャネルで符号化される情報量と、この符号化された情報を与えられた場合のＯＣＲシステムの精度の向上との間のトレードオフのバランスを保ち、改善するアシスト・チャネルの符号化を提供することが、引き続き好ましい。ある極端な例では、アシスト・チャネルは一次チャネルと同程度多くの情報（即ち、冗長な情報）を含むことができる。別の極端な例では、アシスト・チャネルは、ドキュメントのコンテンツの単一のチェックサムのみを含むことができる。従って、ＯＣＲ処理中の一次チャネルの誤りを補正するが、一次チャネルに比べて依然としてコンパクトであるアシスト・チャネルの符号化を提供することが好ましい。
【０００７】
【課題を解決するための手段】
本発明では、ハードコピー・ドキュメント上の表現のための画像データを生成するための方法及び装置が提供される。ハードコピー・ドキュメント上に表現されるべき、人間が読むことが可能な情報を有する第１のチャネルを提供する記号データの一次セットが識別される。符号化データの二次セットは、記号データの一次セットを用いて計算される。符号化データの二次セットは、ハードコピー・ドキュメント上に表現される、機械により可読である情報を有するアシスト・チャネルを提供する。
【０００８】
本発明の一態様では、アシスト・チャネルが、ｃ1、ｃ2、ｃ3、...、ｃi-1、ｃi、ｃi+1、...、ｃnと順序付けられた記号のセットを有する前記記号データの一次セットの選択された行のために、少なくとも前記選択された行のカレント記号ｃiと、先に計算されたハッシュｈi-1と、の関数であるハッシュｈiを生成する状態変更関数Ｈによって、選択された行の各記号のハッシュを順次計算するステップと、少なくとも計算された前記ハッシュｈiの関数であるガード値ｇiを生成するガード抽出関数Ｇによって、選択された行の各記号のための１セットのガード値を計算するステップと、により符号化され、計算されたガード値のセットは、選択された行のための符号化データの二次セットを定義する。
【０００９】
【発明の実施の形態】
Ａ．アシスト・チャネル動作環境
図１及び２は、ドキュメントが、電子ドメイン（領域）とハードコピー・ドメインとの間で授受される本発明の一般的な動作環境を示す。図１は、ディスプレイ１０４等に表示及び／又は生成される電子ドキュメント１０２と、プリンタ１０８によって用紙等の物理的な媒体上に表現されるハードコピー・ドキュメント１０６とを示す。電子アシスト・チャネル１１０は、電子ドキュメント１０２を生成及び／又は編集するために使用される電子ドキュメント処理システム（図示せず）から画像データを受信し、出力として増補された画像データ１２２を生成する。
【００１０】
電子アシスト・チャネル１１０への画像データ入力は、本願明細書において、電子ドキュメント１０２の画像データ１１４を含む一次チャネル１１２のデータとして定義される。電子アシスト・チャネル１１０の符号化／圧縮モジュール１１６は、アシスト・チャネル１１８を生成する。電子アシスト・チャネル１１０のマージ・モジュール１２０は、増補された画像データ１２２を生成するために一次チャネル１１２とアシスト・チャネル１１８とを組み合わせる。図１に示されるこの実施の形態において、増補された画像データ１２２の一次チャネル１１２及びアシスト・チャネル１１８はそれぞれ、ハードコピー・ドキュメント１０６上で１２４及び１２６として表現される。一次チャネル・データ１２４は人間が読むことが可能な情報であるように最適化され、アシスト・チャネル・データ１２６は機械により可読である情報であるように最適化される。
【００１１】
図２は、一次チャネルのデータ１２４及びアシスト・チャネルのデータ１２６が表現されたハードコピー・ドキュメント１０６を、ハードコピー・ドメインから電子ドメインにアップロードする流れを示す。本発明の一態様では、ハードコピー・アシスト・チャネル２０４が、スキャナ２０８からビットマップ画像データ２０６を受信する。ハードコピー・アシスト・チャネル２０４の画像抽出モジュール２１０は、アシスト・チャネル１１８のデータとビットマップ一次チャネル２１４のデータとを分離する。ハードコピー・アシスト・チャネル２０４の復号化／圧縮解除モジュール２１２は、デコーダ・モジュール２１６で用いられるアシスト・チャネル１１８のデータを準備する。
【００１２】
デコーダ・モジュール２１６は、一次チャネル・データ１１２を生成するために、ビットマップ一次チャネル２１４上で復号化及び圧縮解除されたアシスト・チャネル２１９を用いて、光学文字認識（ＯＣＲ）を実行する。アシスト・チャネル２１９を用いて、正確に再構成されると、一次チャネル・データ１１２は、画像データ１１４としてディスプレイ１０４上に表示されることができる。従って、アシスト・チャネル・モジュール１１０及び２０４は、ハードコピー・ドメインと電子ドメインとの間でデータを変換するハードコピー・ドキュメント画像データのＯＣＲ処理の実行を援助する。
【００１３】
図１及び２に示されるアシスト・チャネル・モジュール１１０及び２０４を実行するための動作配置が多数存在することは、当業者により理解されるであろう。ある実施の形態では、アシスト・チャネル・モジュール１１０及び２０４は、ディスプレイ１０４又はプリンタ１０８と一体的に動作するか、又はディスプレイ１０４及びプリンタ１０８とは別々に動作するコンピュータ・システムに埋設されている。他の実施の形態では、アシスト・チャネル・モジュール１１０及び２０４は、１つ又は複数のコンピュータ・システム上で互いに一体化されるか、又はそれぞれ別々に動作する。
【００１４】
Ｂ．アシスト・チャネル・コーディング
概要として、アシスト・チャネル・コーディングは、一次チャネルのＯＣＲ処理の際に欠けている、即ち必要とされるであろう情報のみを有するように、アシスト・チャネル内の一次チャネルの情報コンテンツを圧縮する。即ち、重複一次チャネルを圧縮するために使用されることが可能な技術とは異なり、アシスト・チャネルは、アシスト・チャネルのコンテンツを最小限に抑えることによって、符号化効率を向上させる。また、一次及び二次チャネルが、段階的に情報を配信するように設計されるプログレッシブ方式の符号化（又はピラミッド符号化）とは異なり、アシスト・チャネル・コーディングは、データの固定チャネルから始まり、ハードコピー・ドメインから電子ドメインへの変換の際に遭遇するエラー又は脱落を補正するデータによって、そのデータを増補する。
【００１５】
以下のセクションＣ、Ｄ及びＥにおいて、アシスト・チャネル・データを符号化及び復号化する３つの異なる方法が開示される。概要として、図３乃至１６は、分離コーディングを使用するアシスト・チャネル符号化／復号化を示し、図１７乃至２２は、ブロック・コーディングを使用するアシスト・チャネル符号化／復号化を示し、そして、図２３乃至２８は、畳み込みコーディングを使用するアシスト・チャネル符号化／復号化を示す。セクションＦは、これらの復号化技術を適用することができる「リライト・モデル」を使用する代替の動作環境を説明する。
【００１６】
Ｃ．アシスト・チャネル分離コーディング
本願明細書では「分離コーディング」と呼ばれるアシスト・チャネル・コーディングの第１の方法は、ＯＣＲ処理の最中に、最も混同されそうな一次チャネル内の記号（即ち、等価クラス）を異なるグループに分類する。好適には、容易に圧縮されることが可能な等価クラスへの文字の分類は、アシスト・チャネルにおいて符号化されるが、同様に圧縮され得ない実際の文字コードは、アシスト・チャネルにおいて符号化されない。一次チャネルの走査された表現を復号化する場合、テンプレート・ライブラリからの許容記号マッチは、ＯＣＲ処理の間は、アシスト・チャネルにおいて符号化された分類を満たすものに制限され、これによりＯＣＲ信頼性が向上する。
【００１７】
Ｃ．１  アシスト・チャネル分離符号化
図３は、分離符号化を実行するための概略ステップのフロー・ダイアグラムである。概して、分離コーディングは、符号化の定義と、この符号化の適用との２つの別の動作に分割されることができる。一連のステップ３０４により示される、符号化を定義するための動作は、ＯＣＲ処理の最中に最も混同されそうな一次チャネル内の文字又は記号を区別する等価クラスを有する集合の生成を含む。ステップ３０４で作成／取得される符号化を適用するための、一連のステップ３１２により識別される動作は、一次チャネル内の文字又は記号を、定義された等価クラスの集合内のある等価クラスに割り当てることを含む。
【００１８】
概要として、符号化を定義するためのステップ３０４での動作は、符号化を適用するためのステップ３１２での動作と共に実行されてもよいし、符号化適用ステップ３１２の動作とは独立して実行されてもよい。実際は、ステップ３１２は、一次チャネルのためにアシスト・チャネルが生成される度に毎回実行される必要があるのに対し、ステップ３０４は、特定の一次チャネルのためにアシスト・チャネルが何度生成されようと、１回だけ実行されればよい。以下で更に詳細に論じられるように、符号化は、ステップ３１２で適用される度に定義される必要はない。
【００１９】
より詳細には、ステップ３０６で、１セットの電子ドキュメントの一次チャネルに現れるであろう（英数字）記号（即ち、記号データ）のアルファベットが識別される。続いてステップ３０８で、記号内の識別されたアルファベットは、エントロピーを最小限に抑え且つ利得を最大にする複数のグループに分割される。
即ち、ステップ３０８で、記号内のアルファベットは、（ａ）アシスト・チャネルを構成する情報量（即ち、エントロピー）を最小限に抑え、且つ（ｂ）ＯＣＲ処理の最中に混同される可能性の高い２つの文字が、異なる等価クラスに配置される確率（即ち、利得）を最大にする、ような方法で、複数の等価クラス（即ち、グループ）のうちの１つにマップされる。
【００２０】
図４は、英数字記号の識別されたアルファベットを複数のグループに分割するための図３に示されるステップ３０８を、更に詳細に説明するフロー・ダイアグラムである。ステップ４１０では、記号の識別されたアルファベットの各文字に対応するノードと、各ノードを相互接続するアークとを含むグラフが定義される。図５は、４つの記号の識別されたアルファベット「ｅ」、「ｐ」、「ｂ」及び「ｃ」と、その文字が発生するであろう確率を記録する、それぞれに対応するノード５０２、５０４、５０６及び５０８とを有するグラフ５００の例を示す。各ノードは、別のノードへのアークを有しており、このアークは、ある文字が他の文字と区別される利得を記録する。例えば、ノード５０２はノード５０４、５０６及び５０８へのそれぞれのアーク５１０、５１２及び５１４を有しており、これらのアークは、個々が他と区別されて異なる等価クラスに分類されるその利得を記録する。
【００２１】
図４のステップ４１２では、ステップ４１０で定義されたノード及びアークに値が割り当てられる。より詳細には、各ノードには、ある文字がドキュメント内で発生するであろう確率により定義される値が割り当てられる。各アークには、そのアークの両端の文字がＯＣＲ処理の最中に混同される可能性によって定義される値が割り当てられる。ステップ４１４では、全てのノードが単一のグループに集められ、ノードのカレント・パーティション（分割）を定義する。カレント・パーティションは、エントロピーを最小限に抑え、且つ利得を最大にするように、ステップ４１６、４１８、４２０及び４２２で調整される。
【００２２】
ステップ４１６では、グラフのカレント・パーティションにおける全ての可能な変更が識別される。実施の一形態において、可能な変更は、（ａ）任意の既存のグループに属する任意のノードを有する新しいグループを形成すること、及び（ｂ）あるノードをあるグループから別のグループへ移動すること、により識別される。ステップ４１８では、ステップ４１６で識別された可能な候補のそれぞれごとに、利得における変化（Δ）及びエントロピーにおける変化（Δ）が計算される。各候補は、新しいパーティションを定義する１つ又は複数の可能な変更を含む。ステップ４２０では、カレント・パーティションが、利得における変化及びエントロピーにおける変化の比率を最大にするパーティションであるように選択される。
【００２３】
より詳細には、ステップ４２０では、ＯＣＲエラーの減少率とアシスト・チャネルの情報コンテンツのサイズとの比率が最大になるように、カレント・パーティションは、ステップ４１６で識別された変更により定義されるそれらの候補の中から選択される。図５を再度参照すると、グラフ５００のカレント・パーティションは、グループ５１６及び５１８を含む。ステップ４２２で、所望の利得又はエントロピーが達成されると、カレント・パーティションが、エントロピーを最小限に抑え、且つ利得を最大にする記号の識別されたアルファベットを有するパーティションであると判断され、ステップ３０８のルーチンは終了する。
【００２４】
図６は、利得を最大にしつつ、エントロピーを最小限に抑えるカレント・パーティションを識別するための反復処理を示すグラフである。まず最初に、カレント・パーティションは、グラフ上の点６００により表される（ステップ４１４）。候補の第１のセット６０２が識別された（ステップ４１８）後、エントロピーと利得との比率を最大にする候補６０４が選択される（ステップ４２０）。このプロセスは、候補６１２が所望の利得又はエントロピーと共に識別される（ステップ４２２）まで、候補６０６、６０８及び６１０に対して反復的に続けられる。このプロセスが、例えば仮想の候補６１４等の候補が前のカレント・パーティション６１６に比べて、局所的に負の比率をもたらすような例を、考慮に入れるであろうことは、当業者により理解されるであろう。従って、図６に示される例において、このような候補を選択することは、プラスの傾斜を有する候補６０８のいずれかを選択するよりも好ましい。
【００２５】
図３を再度参照すると、英数字記号の識別されたアルファベットが、利得を最大にしつつ、エントロピーを最小限に抑えるグループに、ステップ３０８で分割されると、ステップ３１０が実行される。ステップ３１０では、ステップ３０８で作成されるパーティションの複数のグループのそれぞれに、識別子が割り当てられる。図７は、１セットの記号が３つのグループ７０２、７０４及び７０６に分類される（ステップ３０８）パーティション７００を示す。グループ７０２、７０４及び７０６には、それぞれ識別子７０８、７１０及び７１２が割り当てられる（ステップ３１０）。パーティション７００は、参照番号７１４、７１６及び７１８により識別される、ＯＣＲ処理によって混同される可能性が高い記号「ｅ」、「ｏ」及び「ｃ」を、それぞれグループ７０２、７０４及び７０６に分離することによって、利得を最大にする。更に、パーティション７００は、ドキュメント内で発生する可能性が最も高い記号を最大のグループ７０２に集めるように３つのグループを定義することによって、エントロピーを最小限に抑える。
【００２６】
ASCII文字セットのパーティションの例が、表１に列挙されており、この表１において、ASCII文字セットは９グループの文字に分類される。上述されたように、ＯＣＲ処理の最中に混同され易い文字、「ｅ」、「ｃ」及び「ｏ」は、利得を最大にするために、識別子（即ち、ＩＤ）Ｚ１、Ｚ２及びＺ４を有するグループ、即ちクラスにそれぞれ分類される。更に、Ｚ１として識別される第１、且つ最大のグループ内の最も発生する可能性の高い文字は、エントロピーを最小限に抑え、それによって、アシスト・チャネルの情報コンテンツ量を最小限に抑える。
【表１】
0004582952.tif 000002
【００２７】
ステップ３０４は、ステップ４１６で局所的変化のみを調べるので、パーティションを定義するためのこの技術は、必ずしも利得及びエントロピーの間の大域的に最適なトレードオフに到達しないであろう。アニーリング法又は分岐限定法等のアルゴリズム技術が、より適切な解を見いだすために使用され得る一方で、これらのアプローチは、ステップ３０４で説明される技術よりも幾分か改善された解を提供するものの、解を見いだすためにかなり多くの時間を必要とする。結果として、ステップ３０４は、グラフ分割を識別するための本アプリケーションに非常によく適している。
【００２８】
定義ステップ３０４が完了すると、適用ステップ３１２が実行される。先ずステップ３１４では、ステップ３０２で受信された一次チャネルの各記号を、各記号が割り当てられるグループに対応する識別子と関連付けることにより、アシスト・チャネルが作成される。図８は、ステップ３０２で受信された一次チャネル８００の例を示す。図９は、図７に示されるパーティション７００を使用して作成される、図８に示される一次チャネルのためのアシスト・チャネル９００を示す。具体的には、一次チャネル８００の参照番号８０２及び８０４によって識別される最初の２つの記号「Ａ」及び「ｎ」は、識別子７０８（即ち、「ａ」）及び７１０（即ち、「ｂ」）を有するグループ７０２及び７０４に分類され、それらの記号はそれぞれ、図９の参照番号９０２及び９０４により識別される。
【００２９】
ステップ３１６では、ステップ３１４で作成されたアシスト・チャネルが、例えば、算術に基づく符号化、ジブ−レンペル（Ziv-Lempel）の符号化又はラン・レングス符号化を用いて圧縮される。これらの及び他の圧縮技術は、Cover他による「情報理論の構成要素（"Elements of Information Theory"）」（ジョン・ワイリー・アンド・サンズ、1991年8月12日（ISBN：0471062596））で開示されている。アシスト・チャネルがステップ３１６で圧縮されると、アシスト・チャネルはステップ３１８で符号化される。実施の一形態において、アシスト・チャネルは、データ・グリフを用いて符号化される。図１０は、データ・グリフを用いて符号化されるアシスト・チャネル１０１０の例を示す。
【００３０】
ここで参照されるデータ・グリフは、デジタル情報を２値の１と０との形式で符号化し、これらの値はその後、非常に小さい直線マークの形で表現される。一般に、各小型マークは、２値データのディジット（桁）を表す。特定のディジットが、２値の１であるか０であるかは、特定のマークの線の向きに依存する。例えば、実施の一形態において、左上から右下に向けられたマークは０を表し、左下から右上に向けられたマークは１を表すことが可能である。
【００３１】
図１及び２に示されるアシスト・チャネル１２６を形成するデータ・グリフの個々のマークは、多数のこのようなマークが共に用紙にプリントされる場合に、均等なグレー・ハーフトーン領域を何気なく見る人に、好ましくは全体的な視覚効果をもたらすように、プリント装置の最大解像度と相関的なサイズである。米国特許第5,091,966号、第5,128,525号、第5,168,147号、第5,221,833号、第5,245,165号、第5,315,098号、第5,449,895号及び第5,486,686号は、データ・グリフの使用法、符号化及び復号化技術に関する更なる情報を提供している。
【００３２】
図３を再度参照すると、ステップ３２０では、符号化されたデータ・グリフが一次チャネルと連結され、増補データを生成する。連結されたチャネル（即ち、増補データ）は、ハードコピー・ドキュメント上に表現される。図１に示すように、実施の一形態において、増補データ１２２は、一次チャネル１２４及びアシスト・チャネル１２６としてハードコピー・ドキュメント１０６上にプリンタ１０８によって表現される。
【００３３】
ステップ３０２で受信される一次チャネルに対して適用ステップ３１２が実行される度に、定義ステップ３０４が実行される必要のないことは、当業者により理解されるであろう。代わりに、定義ステップ３０４は、任意の数の一次チャネルに対して一度だけ実行されればよい。或いは、ステップ３０２で受信する英数字記号のアルファベット又はフォントが変わる度に、定義ステップ３０４が断続的に実行されてもよい。
【００３４】
別の実施の一形態において、定義ステップ３０４は、異なる種類のドキュメント、フォント又はマシンに対して１回実行される。例えば、定義ステップは、フォント書体ごとに１回実行され、ステップ３１２で繰り返し適用されることが可能である。また、例えば、ドキュメントの種類には、ドキュメントのジャンル（例えば、オフィス文書、法律文書、メモ、画像等）による分類を含んでもよい。
更なる例として、マシンの種類には、特定のスキャナ及びプリンタ、又は特定のクラスのスキャナ及びプリンタを含む。例えば、実施の一形態において、定義ステップ３０４は、特定のスキャナ及び／又はプリンタのために実行されることが可能であり、それにより、特定のスキャナ及び／又はプリンタの特定の誤りに対する符号化方式の感度を高める。
【００３５】
Ｃ．２  アシスト・チャネル分離復号化
図１１は、図２に示されるアシスト・チャネル１２６により増補されるハードコピー・ドキュメント１０６の一次チャネル１２４を復号化するためのハードコピー・アシスト・チャネル（２０４）によって実行されるステップのフロー・ダイアグラムを示す。先ずステップ１１０２で、ハードコピー・ドキュメント１０６のビットマップ画像２０６が、例えばスキャナ２０８を使用して取得される。
ステップ１１０４では、画像抽出モジュール２１０が、ビットマップ画像２０６からアシスト・チャネルを抽出し、アシスト・チャネル１１８を復号化／圧縮解除モジュール２１２に供給する。更に、画像抽出モジュール２１０は、一次チャネル１２４のビットマップ表現であるビットマップ一次チャネル２１４を、ビットマップ画像２０６から抽出する。
【００３６】
ステップ１１０６では、アシスト・チャネル（１１８）が、モジュール２１２によって復号化される。例えば、アシスト・チャネルがデータ・グリフを用いて符号化される場合、これらのデータ・グリフは、それらのデジタル表現にステップ１１０６で復号化される。アシスト・チャネル（この時点ではデジタル形式である）は、ステップ１１０８でモジュール２１２によって圧縮解除され、復号化及び圧縮解除されたアシスト・チャネル２１９をデコーダ・モジュール２１６に供給する。
【００３７】
ステップ１１１０からの一連のステップでは、デコーダ・モジュール２１６が、ビットマップ一次チャネル２１４の連続行と、復号化及び圧縮解除されたアシスト・チャネル２１９の対応する連続行とをモジュール２１０及び２１２のそれぞれから、入力として取得する。ステップ１１１０で受信されたチャネル２１４及び２１９の連続行のそれぞれに対して、一次チャネル２１４の全ての行がステップ１１１８で処理されたことが判断されるまで、ステップ１１１２、１１１４及び１１１６が実行される。ステップ１１１８で全ての行が処理されたと判断されると、一次チャネルの復号化はステップ１１２０で完了する。デコーダ・モジュール２１６がステップ１１２０で処理を終了すると、復号化された一次チャネル１１２は、ドキュメント１０２内の１１４としてディスプレイ１０４上に電子形式で表示されることが可能である。
【００３８】
ビットマップ一次チャネル２１４の行を復号化するためのステップ１１１２、１１１４及び１１１６をここで詳細に参照する。ステップ１１１２では、一次チャネルの行のグラフが、プロダクト・グラフの第１の次元を定義するように決定される。ステップ１１１４では、アシスト・チャネルの対応する行のグラフが、プロダクト・グラフの第２の次元を定義するように決定される。最後にステップ１１１６で、一次チャネルのグラフと、アシスト・チャネルのグラフとの積の最短経路が、観察される一次チャネルを生成するために決定される。
【００３９】
実施の一形態において、ステップ１１１２は（ビットマップ一次チャネル２１４の「テキスト」の各行ごとに）、ドキュメント画像復号化（ＤＩＤ：Document Image Decoding）として当該技術において公知のドキュメント復号化技術を使用して、デコーダ・モジュール２１６により実行される。一般にＤＩＤは、ダイナミック・プログラミング又はビタービ（Viterbi）アルゴリズムを用いて達成される。ダイナミック・プログラミングは、有限状態のネットワークの全体にわたる、観察される画像を表す経路（即ち、一次チャネル１１２）、即ち、観察される画像を生成する可能性が最も高い経路（即ち、ビットマップ一次チャネル２１４から導き出し得る観察される可能性の最も高い画像）の検索を含む。
【００４０】
ダイナミック・プログラミングの更なる詳細は、Aho、Hopcroft及びUllmanによる「コンピュータ・アルゴリズムの設計及び解析（The Design and Analysis of Computer Algorithms）」（コンピュータ・サイエンス及び情報処理に関するアディソン‐ウェズリー・シリーズ）（アディソン‐ウェズリー出版、ISBN：0201000296、1974年6月）に開示されている。更に、ＤＩＤの更なる詳細は、米国特許第5,321,773号、第5,526,444号、第5,689,620号、及び第5,594,809号において開示されている。
【００４１】
図１２を、ここで参照する。図１２は、ビタービ・アルゴリズムを用いて一次チャネルのグラフの最短経路を計算するためのステップを説明するフロー・ダイアグラムである。先ず、グラフがステップ１２００で定義され、定義されたグラフの最短経路がステップ１２０１で計算される。図１２は、アシスト・チャネルの助けなしで動作するＤＩＤデコーダを説明する。アシスト・チャネルを含めるには、ステップ１２００で定義されるグラフは、最短経路が計算される前に、プロダクト・グラフを計算することにより変更される。図１１のステップをここで参照すると、ステップ１２００は、一次チャネルのためのグラフを決定するためのステップ１１１２で実行される。更に、ステップ１２０１は、一次及びアシスト・チャネルのグラフの積を定義しているグラフの最短経路を決定するためのステップ１１１６で実行される。
【００４２】
グラフの定義は、ビットマップ一次チャネル２１４の行に沿って、ピクセルごとにグラフのノードを定義することにより、ステップ１２０２で開始される。例えば、図１３は、グラフ生成を１３０１に示し、最短経路計算を１３０３に示す。グラフ生成は、図８に示される一次チャネル８００の行の文字８０２のビットマップ表現のためのノード１３０２によりグラフ１３００を定義することから始まる。ステップ１２０３では、各ノードにおける全ての可能なアークが、テンプレート・ライブラリを用いて列挙される。ステップ１２０４では、テンプレート・ライブラリ内の文字を画像内の文字とマッチング（照合）することによって、アークの得点が、列挙された各アークで計算される。
【００４３】
より詳細には、アークの得点は、マッチング関数を使用して、列挙された各アークごとに計算される。この計算は、ライブラリ内の特定のテンプレートと、ノードにより定義される画像ポイントでの画像領域とのマッチングの測定である。
マッチング関数を選択する際には、いくらかのフレキシビリティがあるが、マッチング関数は通常、マッチングの負の対数確率に密接に比例する。これは、よりよいマッチングに対してアークの得点がより小さくなること、及び最短経路が行全体の最適な解釈を識別すること、を可能にする。マッチング関数の例は、Kopec他による「マルコフ・ソース・モデルを用いたドキュメント画像復号化（Document Image Decoding Using Markov Source Models）」（パターン解析及び機械知能に関するIEEE論文集第１６巻６号、1994年6月、第602〜617頁）に開示されている。
【００４４】
アークの得点及びテンプレートは、別のノードへのアークの形で記録される。
例えば図１３に示すように、アーク１３１４は、テンプレート１３１０（即ち、「Ａ」）及びアークの得点１３１２（即ち、「１０」）によって、ノード１３０６と１３０８との間に定義される。より詳細には、アークは一致の質によって重み付けされ（得点が低いほど、より一致する）、その一致により識別されるテンプレートの幅だけ離された位置のノード同士を連結する。
【００４５】
隣接するテンプレート同士の間の間隔にわずかなシフトをもたらすために、スペーサ・アーク（図１３では参照番号１３１６で示される）が定義される。例えば、得点（図示せず）を有することが可能なスペーサ・アーク１３１８は、テンプレート１３１０の終端ノード１３０８と、ノード１３２０から開始し得る図８に示される文字８０４のための次のテンプレートとの間の間隔を満たし得る。
【００４６】
ステップ１２０６では、記録１３２２が、図示されるように（図１３の最短経路計算１３０３に示すように）各ノード１３０２ごとの累積得点１３２４及びバックポインタ１３２６により定義される。ステップ１２０８では、行の最後のノード１３２８を除く全てのノード１３０２の記録１３２２は、無限大の得点（即ち、最悪の得点又は経路）及びNIL（ニル）バックポインタによって初期化される。行の最後のノード１３２８に関する記録のための得点は、ステップ１２０８で０（即ち、最高の得点又は経路）に初期化される。
【００４７】
ステップ１２１０及び１２１２では、ビタービ・アルゴリズムの２つのパスが実行される。ステップ１２１０で実行されるビタービ・アルゴリズムの第１のパス（即ち、フォワードパス）の最中に、各ノード（即ち、ピクセル位置）に至る確率の最も高い経路（即ち、最もよい得点）が、先に計算された全ての位置への確率の最も高い（即ち、最短の）経路を使用することにより識別される。第１のパスは、各ノードのための最適な経路の終端点が識別されるまで、実行される。
図１４及び１５に関連する以下の記述において、この例では、部分的に最短の経路をグラフの後部から構築することが有用であり、従って、ビタービ・アルゴリズムの第１及び第２のパスの一般的な方向を逆転させることは、当業者により理解されるであろう。
【００４８】
図１４は、ノード１４０２により定義されるグラフ１４００のビタービ・アルゴリズムのフォワードパス計算の例を示す。フォワードパスは、矢印１４０４（即ち、順方向又は第１の方向）により示される方向で、ノード１４０３からノード１４０１まで実行される。簡潔に示すために、ノード１４１０及び１４１２からそれぞれ開始し、ノード１４１４で終端するアーク１４０６及び１４０８のための得点１４１６及び１４１８と、テンプレート１４２０及び１４２２のみが示される。ステップ１２１０でノード１４１４のための最短経路を計算する際に、ノード１４１０及び１４１２のそれぞれの記録１４２４及び１４２６において、得点及びバックポインタが、より短い経路を定義するようにノード１４１４への点数に更新されるべきか否かの判断が成される。もし更新される場合、ノード１４１０の新しい得点は１９（即ち、１２＋７）であり、ノード１４１２の新しい得点は１０（即ち、３＋７）である。更新されると、ノード１４１０の得点は改善される（即ち、１９は５０よりも適切である）ので、ノード１４１４への新しい得点及びバックポインタにより記録は更新される（図１５参照）。対照的に、ノード１４１４からの新しい得点に更新されても、ノード１４１２の得点は改善されない。従って、この記録は更新されない（即ち、１０は８よりも不適切である）。
【００４９】
ステップ１２１２で実行されるビタービ・アルゴリズムの第２のパス（即ち、バックワードパス）では、第１のパスの間に構成されたグラフが、グラフ全体を通して実際に最適な経路（即ち、最短経路）を識別するために、グラフの第１のノードから逆方向にたどられる。図１５は、図１４で作成されるグラフ１４００のバックトレーシングの例を示す。バックトレーシングは、矢印１５０３により示される方向に、図１５で実行される。多くの異なる経路が存在し得るが、最適な経路は、第１のパスの間に処理される最後のノードのバックポインタ（即ち、ノード１４０１のバックポインタ１５０４）から始まるグラフ全体を通して、経路を逆方向にたどることにより定義される。ノード１４０１のバックポインタ１５０４からのバックポインタ（例えば、１５０４、１５０６、１５０８、１５１０、１５１２）を有する経路は、ある文字のテンプレート（例えば、テンプレート１４２０）を指定する１セットのアークを識別する（例えば、バックポインタ１５０８はアーク１４０６を識別する）。アークのこのセットは、一次チャネルの記号に一致するテンプレートを識別する。即ち、プロダクト・グラフの第１の次元における最短経路は、アシスト・チャネル２１９の助けなしに構成される出力文字列を定義する。
【００５０】
プロダクト・グラフにアシスト・チャネルを組み入れるためには、プロダクト・グラフが定義されるまで、最短経路１２０１の計算は保留される。ステップ１１１４で、アシスト・チャネル２１９のグラフが決定され、プロダクト・グラフの第２の次元を定義する。より詳細には、ステップ１１１４では、ノードがアシスト・チャネルで符号化される各識別子７０８で定義される。あるノードから次のノードへのアークは、識別子の値を与えられる。更に、各ノードは、最短経路の計算中に、スペーサ・アーク１３１６の存在を許容するために、それ自体に戻るアーク（即ち、例えば、アーク１６３０等の自己回帰アーク）を含む。
【００５１】
最後にステップ１１１６では、プロダクト・グラフの最短経路が、ステップ１１１２及び１１１４で定義される一次元のグラフを用いて定義される。即ち、ステップ１１１６は、ビットマップ一次チャネル２１４及びアシスト・チャネル２１９を用いてプロダクト・グラフ全体を通して最短の経路を識別し、観察される画像（即ち、一次チャネル１１２）を定義する。ステップ１１１０、１１１２、１１１４及び１１１６は、ビットマップ一次チャネル２１４の各行に対して、ステップ１１１８で繰り返される。一次チャネルの全ての行がステップ１１２０で処理されると、一次チャネル１１２は、ディスプレイ１０４上に、例えば、ドキュメント１０２内の画像データ１１４として表示されることが可能である。
【００５２】
図１６は、図１１のステップ１１１６でのプロダクト・グラフの最短経路計算の例を示す。図１６に示されるプロダクト・グラフ１６００は、第１の次元１６０２（図１１のステップ１１１２で生成されるグラフにより定義される）及び第２の次元１６０４（図１１のステップ１１１４で生成されるグラフにより定義される）を含む。プロダクト・グラフの第１の次元１６０２は、図８に示される一次チャネル８００のテキストのビットマップ行を表し、プロダクト・グラフの第２の次元１６０４は、図９に示されるアシスト・チャネル９００の対応する行を表す。
【００５３】
図１６に示されるプロダクト・グラフ１６００は、例示のために、一次チャネルの最初の４つの記号（即ち、８０２、８０４、８０６及び８０８）、アシスト・チャネルの最初の４つの識別子（即ち、９０２、９０４、９０６及び９０８）、及びわずかなテンプレートの一致のみを含む。比較目的のために、プロダクト・グラフ１６００は、結果として生じる出力文字列１６０８と、１セットのアーク１６１０、１６１２、１６１４及び１６１８を含む１つの次元１６０２におけるビットマップ一次チャネルのグラフの最短経路の計算により生成される出力文字列の両方を示す。単一の次元１６０２におけるグラフ１６００の最短経路の計算は、アシスト・チャネルからの入力なしで実行され、文字「Ａｈ  ａ」を含む出力文字列１６０６を生成する。
【００５４】
プロダクト・グラフ１６００は、次元１６０２に沿って画像における位置を、そして次元１６０４に沿って対応するアシスト・チャネルにおける位置を識別するノード１６４０を含む。また、プロダクト・グラフ１６００は、アシスト・チャネルと合致しているはずのアークを含む。即ち、テンプレート・ラベルを有する第１の次元における各アーク、及び分類ラベルを有する第２の次元における各アークにとって、テンプレートが正しいクラスである場合には、対応するアークがプロダクト・グラフに存在する。第２の次元１６０４に沿ったアーク１６２２、１６２４、１６２６及び１６２８はそれぞれ、７０２、７０４、７０２及び７０２の記号グループを識別する識別子９０２、９０４、９０６及び９０８に対応する。プロダクト・グラフ１６００が定義されると、プロダクト・グラフの最短経路の計算は、文字「Ａｎ  ａ」を含む出力文字列１６０８を生成する。
【００５５】
図１６に示されるように、支援されない復号化された一次チャネル１６０６の出力は、プロダクト・グラフ１６００においてアシスト・チャネルを使用して訂正される。ノード１６４６でプロダクト・グラフ１６００を定義する際に、計算された得点が１５であるアーク１６１２のテンプレート「ｈ」は、アシスト・チャネルにより除外される。ビットマップ一次チャネルのグラフからのアーク１６１２は、アーク１６２４によって定義されるアシスト・チャネルの第２のエントリを満たさないので、プロダクト・グラフから除外される。即ち、アーク１６１２により識別されるテンプレートは、アーク１６２４の識別子７１０により指定されるグループ７０４ではなく、グループ７０２に分類される。従って、図１６に示されるテンプレートに関しては、より高い１９という得点を有し、且つアシスト・チャネルの第２のエントリ（即ち、アーク１６２４）を満たすアーク１６２０のテンプレート「ｎ」のみが、プロダクト・グラフにおける位置１６４２で有効なアークとして許容される。
【００５６】
より詳細には、図１６は、図１１に示されるステップを参照しながら、図８に示される一次チャネル８００の走査された表現から、復号化された一次チャネル１６０８を生成するプロダクト・グラフ１６００を示す。まず最初に、一次チャネルのグラフが、第１の次元１６０２において決定される（ステップ１１１２）。続いて、アシスト・チャネルのグラフは、第２の次元（１６０４）において決定される（ステップ１１１４）。先ず、プロダクト・グラフは、一次チャネルのグラフ及びアシスト・チャネルのグラフを組み合せることにより定義される（ステップ１１１６）。一次チャネルのグラフと、アシスト・チャネルのグラフとの積の最短経路を決定することは、出力文字列１６０８を生成する（ステップ１１１６）。
【００５７】
簡潔さのために、プロダクト・グラフ１６００を定義しているアーク及びノードのほんの一部が、図１６に示されていることは、当業者により理解されるであろう。グラフの最短経路を計算するための図１２のステップ１２０１に従う実施の一形態において、プロダクト・グラフ１６００の最短経路は、下から上へ、且つ右から左への順序で第１のパスを実行することにより計算される。本実施の形態では、プロダクト・グラフの第１のパスは、プロダクト・グラフの最も下に位置するノードが、最も右のノードに優先するとみなす。第２のパスは、プロダクト・グラフ１６００の左上のノード１６４４により定義される経路を選択することにより実行される。
【００５８】
簡潔さのために、プロダクト・グラフ１６００は、各ノード１６４０から延伸し、且つテンプレート・ライブラリからのテンプレートと、ビットマップ一次チャネルとの間で、アシスト・チャネルの条件を満たす全ての可能な一致を識別する、多数のアークを示すわけではないことは、当業者により理解されるであろう。代替の実施の形態において、プロダクト・グラフ１６００を定義するアークの数は、プロダクト・グラフの対角線の周辺に配置されたノードから延伸するアークのみを含むことによって、減じられる。十分な量の分散を許容することにより、この代替の実施の形態は、アシスト・チャネルが画像内の１行にわたって均等な割合で用いられると想定される。
【００５９】
Ｄ．アシスト・チャネル・ブロック・コーディング
本願明細書において「ブロック・コーディング」と呼ばれる、アシスト・チャネル・コーディングの第２の方法は、ハードコピー・ドキュメントの一次チャネルの文字を垂直な列にグループ化する。ガード・ディジット（即ち、エラー訂正符号）は、各垂直ブロックごとに計算され、ハードコピー・ドキュメントのアシスト・チャネルにおいて符号化される。好適には、アシスト・チャネルによる一次チャネルの復号化は、垂直ブロックごとに同期をとられる。即ち、一次チャネルのアシスト・チャネルとの同期は、一次チャネルの各垂直ブロックで発生するので、テキスト行のＯＣＲ処理の最中に発生し得る同期はずれは、最小限に抑えられる。
【００６０】
Ｄ．１  アシスト・チャネル・ブロック符号化
図１７は、アシスト・チャネルのブロック符号化を実行するためのステップのフロー・ダイアグラムである。実施の一形態において、これらのステップは、図１に示される電子アシスト・チャネル１１０によって実行される。ステップ１７０２で、符号化／圧縮モジュール１１６は、データの一次チャネル１１２を受信する。例えば、図１８はデータの一次チャネル１８００の例を示す。ステップ１７０４で、列グループのサイズが指定される。列グループのサイズは、固定されていても、列グループごとに異なっていてもよい。より詳細には、列グループのサイズは、何個の記号（例えば、文字）が、一次チャネルの各行に沿って列グループを定義するかを識別する。ステップ１７０６では、列グループ当たりのガード・ディジットの数が指定される。より多くのガード・ディジットがステップ１７０６で指定されると、ガード・ディジットが訂正可能なエラーの数はより多くなる一方で、アシスト・チャネルがより大きくなるであろうことは、当業者により理解されるであろう。
【００６１】
ステップ１７０８では、一次チャネルの記号データ（例えば、文字）の行数が決定される。続いてステップ１７１０では、記号データの各行の長さが決定される。ステップ１７１２では、記号データの一次チャネルが、指定された列グループのサイズに従って、垂直ブロックに分割される。ステップ１７１４では、ステップ１７０６で指定された数の列グループ当たりのガード・ディジットが、ステップ１７１２で生成された各垂直ブロックごとに計算される。実施の一形態において、ガード・ディジットは、エラーを訂正するリード・ソロモン符号を適用することにより計算される。リード・ソロモン符号の計算は、Peterson他による「エラー訂正符号（Error-Correcting Codes）」（ＭＩＴ出版、1972年）において開示されており、公知である。
【００６２】
例えば、２8個の記号アルファベットを伴う５個のエラーを訂正するリード・ソロモン符号が適用される場合、アシスト・チャネルの最大ブロック・サイズは、１０個のガード・ディジット（即ち、チェック・ディジット）を含む２５５ディジットである。更に、４０行のテキスト（即ち、記号データ）が、列グループのサイズが２である列にグループ化されると仮定する。すると、この例は、２8個の記号アルファベットにわたるリード・ソロモン符号のための２５５ディジットである最大ブロック・サイズよりもかなり小さい９０文字（即ち、４０×２＋１０＝９０）のブロック・サイズを必要とする。この符号化方式を用いる場合、ガード・ディジットのサイズは、１文字当たり１ビット（即ち、８文字に対して１ガード・ディジットである圧縮比）である。そして、ブロック当たりのＯＣＲエラーが５個以下である限り、このページはエラーなしに復号化されるであろう。
【００６３】
図１９は、ガード・ディジットが、図１８に示される一次チャネルの記号データの指定された垂直ブロックのために計算される例を示す。より詳細には、図１９において、一次チャネルの記号データは、参照番号１９０２により示されるように２記号幅のブロック・サイズを有する垂直ブロックに分割される（ステップ１７１２）。記号データの各垂直ブロックごとに、対応するガード・ディジット１９０４が計算される（ステップ１７１４）。一次チャネルの行（例えば、行１９０６）が、別の行（例えば、行１９０８）ほど長くない場合には、空記号（例えば、空記号１９１０）が、その列のガード・ディジット（例えば１９１２）を計算するためにその行に加えられる。
【００６４】
各垂直ブロックごとのガード・ディジットがステップ１７１４で計算されると、アシスト・チャネルのためのデータがアセンブルされ圧縮される。図２０は、図１８に示される一次チャネルの例のためにステップ１７１６でアセンブルされるデータ２００２を示す。より詳細には、データ２００２は、列グループのサイズ２００４、列グループ当たりのガード・ディジット数２００６、ガードされる記号データの行数２００８、行長さのベクトル２０１０、及びガード・ディジット２０１２を含む。実施の一形態において、データ２００２の幾つか（例えば、行長さのベクトル２０１０）は、無損失の圧縮技術を用いてステップ１７１４で圧縮される。
【００６５】
アシスト・チャネルがステップ１７１６で圧縮されると、アシスト・チャネルはステップ１７１８で符号化される。実施の一形態において、アシスト・チャネルは、例えば図１０に示されるように、データ・グリフを用いて符号化される。
ステップ１７２０では、符号化されたアシスト・チャネルが一次チャネルと連結されて、例えばプリンタ１０８を用いてステップ１７２２でプリントされる。
【００６６】
一次チャネルが符号化される方法が変更され得ることは、当業者により理解されるであろう。実施の一形態において、一次チャネルは、一定のサイズ及び一定のガード・ディジット数をそれぞれ有する列グループに分割される。代替の実施の形態において、一次チャネルは、各列グループごとに異なるサイズ及び／又は異なるガード・ディジット数を割り当てられる列グループに分割される。例えば、ある行は最後の列に至る前に終了する可能性があるために、最後の列はより少数の文字を有し得る。従って、ガード・ディジット数は、最後の列ではおそらく異なるであろう。また、その列の情報が、より高い復号化精度を必要とすると先験的に判断される場合（例えば、金額情報を含む銀行小切手の列）、特定の列のためのガード・ディジット数をより大きくしてもよい。
【００６７】
Ｄ．２  アシスト・チャネル・ブロック復号化
図２１は、走査されたハードコピー・ドキュメントを復号化するために、ブロック符号化されたアシスト・チャネルを用いて、ハードコピー・アシスト・チャネルにより実行されるステップを説明するフロー・ダイアグラムである。図２に示されるように、先ずステップ２１０２では、ハードコピー・ドキュメント１０６のビットマップ画像２０６が、スキャナを使用して取得される。この例において、ハードコピー・ドキュメント１０６は、一次チャネル１２４及びブロック符号化されたアシスト・チャネル１２６を含む。ステップ２１０４では、画像抽出モジュール２１０が、アシスト・チャネル１１８及びビットマップ一次チャネル２１４をビットマップ画像２０６から抽出する。アシスト・チャネル１１８は、ステップ２１０６で復号化され、モジュール２１２によりステップ２１０８で圧縮解除される。ステップ２１０９では、ビットマップ一次チャネルが、行長さのベクトル２０１０の行長さを用いて位置合わせされ、一次チャネルの行をアシスト・チャネルのガード・ディジットと同期させる。続いて、圧縮解除されたアシスト・チャネル２１９及びビットマップ一次チャネル２１４は、ステップ２１１０、２１１２、２１１４、２１１６、２１１８、２１２０、２１２２、２１２４、２１２６及び２１２８を実行するデコーダ・モジュール２１６に入力される。
【００６８】
ステップ２１１０では、ＯＣＲ解釈の候補が、アシスト・チャネルの支援を借りずに、一次チャネルの各行ごとの最短経路計算を介して算出される。実施の一形態において、この最短経路計算は、上述のセクションＣで詳細に論じられたドキュメント画像デコーダ（ＤＩＤ）を用いて、各行ごとに実行される。より詳細には、ＤＩＤは、図１２で説明されるステップを実行し、図１４及び１５に示されるようなノード及びアークを伴うグラフを通して最短の経路を生成する。２つのパスのうちの第２のパスにおいて、グラフ全体を逆方向にたどることにより識別される最短経路は、各行の「アシスト無し」のＯＣＲ解釈の候補を提供する。
【００６９】
ステップ２１１２では、カレント・メッセージのベクトルが、ＯＣＲ解釈の候補を有する第１の列グループを用いて特定される。列グループの寸法は、列グループのサイズ及びガードされたテキストの行数を用いて、アシスト・チャネルにおいて定義される。ステップ２１１４では、カレント・メッセージのベクトルに対応するガード・ディジットが、アシスト・チャネルから取得される。ステップ２１１６では、ステップ２１１４で取得されたガード・ディジットが用いられ、ステップ２１１０で計算されたＯＣＲ解釈の候補にエラーが存在するか否かがチェックされる。エラーが存在する場合は、カレント・メッセージのベクトルは、ガード・ディジット（例えば、リード・ソロモン符号）を使用してステップ２１１８で訂正され、存在しない場合は、ステップ２１２２が実行される。
【００７０】
ステップ２１２０では、ステップ２１１８で訂正を必要とされた一次チャネルの各行の、残りのメッセージのベクトルが識別される。ステップ２１１６でチェックされない残りのメッセージのベクトルに対して、ステップ２１１０で実行された最短経路計算が解釈し直され、新しい又は変更されたＯＣＲ解釈の候補を生成する。一次チャネルの各行の残りの再解釈は、図２２を参照して、以下で十分に説明される。最後に、全てのガード・ディジットが処理されている場合は、復号化はステップ２１２６で終了し、処理されていない場合は、復号化処理は、カレント・メッセージをＯＣＲ解釈の候補を有する次の垂直ブロックに指定することにより、ステップ２１２４で続けられる。ステップ２１２４が完了すると、ステップ２１１４がカレント・メッセージ及び（変更された）ＯＣＲ解釈の候補に対して繰り返される。
【００７１】
図２２は、図１８に示される一次チャネル１８００の一部１８０２のために実行される最短経路計算の再解釈の詳細な例を示す。より詳細には、図２２は、ＯＣＲ処理においてエラーが識別された際に、ＯＣＲ解釈の候補２２０６を解釈し直し、再編成するためにアシスト・チャネルを使用する方法を示す。まず最初に、ＯＣＲ解釈の候補２２０６は、矢印２２０２によって概略的に示されるように、抽出されたビットマップ一次チャネル２２０４から、ドキュメント画像デコーダを用いて計算される（ステップ２１１０）。抽出されたビットマップ一次チャネル１８００の一部１８０２のみが、図２２に示されていることに留意すべきである。
【００７２】
続いて、図１９に示される第１の列グループ１９２０のためのガード・ディジット１９１８が用いられ、矢印２２０９によって概略的に示されるように、この列グループのための復号化されたＯＣＲ解釈の候補の中にエラーが存在するか否かが決定される（ステップ２１１６）。図１９に示される列グループ１９２０の一部１９２２のみが、部分２２０８として図２２で識別されていることに留意すべきである。部分２２１０を含む列グループを評価するためにガード・ディジットを使用する場合、この列グループに対応するガード・ディジットは、ビットマップの部分２２０８を復号化する際のエラーを識別し、訂正された復号化部分２２１２をもたらすために用いられる（ステップ２１１８）。
【００７３】
第１の列グループの処理後、訂正された全ての行が解釈し直され、矢印２２１３によって概略的に示されるように、新しいＯＣＲ解釈の候補が提供される（ステップ２１２０）。図２２では、訂正された復号化部分２２１２を考慮して、ＯＣＲ解釈の候補２２０６を解釈し直した後に、新しいＯＣＲ解釈の候補２２１４が提供される。図１５に関連して上述されたＤＩＤを使用することにより、復号化エラーを考慮したＯＣＲ解釈の候補２２０６の再解釈は、図１５及び２２で参照番号１５２０、１５２２及び１５２８によりそれぞれ識別されるように、文字「ｄ」を訂正し、文字「ｏｌ」に置換する。新しい文字１５２２のために、グラフ１４００は、図１５に示されるように新しいテンプレートがノード１５２４で終了するように再編成される。ノード１５２４から逆方向にたどることにより、新しいセットのテンプレートを特定する新しいセットのアークを識別するバックポインタ（例えば、１５２６、１５０８、１５１０、１５１２）を有する新しい経路が解釈し直され、これにより、図２２に示される新しいＯＣＲ解釈の候補２２１４が得られる。
【００７４】
ＤＩＤグラフの再解釈が成されると、新しいＯＣＲ解釈の候補２２１４はこの時点で、図１５及び２２に示される新しいテンプレート１５２８を識別する。新しいＯＣＲ解釈の候補２２１４のエラー識別及び訂正は、部分２２３０を含む次の列グループに対して実施される。ＯＣＲ解釈２２０６の部分２２１０に対して実行されたと同様に、ＯＣＲ解釈２２１４の画像部分２２３０は、先ずエラーを調べられ、矢印２２３２により示されるように、必要に応じて訂正される。続いて、エラーが識別されて、画像部分２２３４で訂正されたと仮定すると、ＯＣＲ解釈２２１４は、矢印２２３８により示されるように、新しいＯＣＲ解釈２２３６として解釈し直される。ＯＣＲ解釈の各列グループが、図２１に示されるフロー・ダイアグラムに従って分析され終わるまで、図２２に示されるプロセスが続けられる。
【００７５】
ＯＣＲ出力行を解釈し直すために、様々な技術を用いることが可能であることは、当業者により理解されるであろう。特に、任意のＯＣＲシステムの文字列出力は、訂正された接頭部とオリジナルのＯＣＲ解釈との間の文字列編集の隔たり（即ち、ある文字列を別の文字列に等しくするために必要とされる変更の回数）を最小限に抑えるために、部分的に訂正された行に合せて再調整されることが可能である。
【００７６】
１ページ又は複数ページのハードコピー・ドキュメントのためのエラー訂正コードを、垂直なパーティション（サイズは異なり得る）に沿って計算することは、テキスト及び／又はページの各行の初め及び終わりに、当然ながら同期点を追加する。図２２に示されるように、エラーの検出及び訂正が、テキストの復号化された行全体で進められる際に、前のブロック２２１２の成功した訂正は、次のブロック２２３０の訂正と同期がとられる。好適には、一次チャネルの垂直列グループごとにガード・ディジットを計算することにより、デコーダ・モジュール２１６は、各列グループで同期がとられる。行に沿って複数の同期点を提供する垂直列グループを用いない場合、ＯＣＲデコーダは、誤って異なる幅の文字を照合し、エラー訂正符号との位置がずれるおそれがある。更に、適切な同期を伴わないＯＣＲデコーダは、アシスト・チャネルのエラー訂正能力を上回るおそれのある連続するエラー文字列を生成し得る。
【００７７】
更に、より多くのテキスト行が記号ブロックごとにガードされると、より大きい圧縮がアシスト・チャネルにより達成されることは、当業者によって理解されるであろう。また、ブロック・コーディングは、十分な数の同期点を提供するために、多数の記号行を必要とすることは、当業者により理解されるであろう。即ち、ほんの数行しか存在しない場合は、これらの行の中央に位置する１セットの同期点が、アシスト・チャネルのデータ２００２に加えられることが可能である。ガード・ディジットのための１セットの同期点の中の同期点は、１ページ又は複数ページ上で、同じ又は異なるテキスト行の第１の列グループの位置を識別する。これは、１列を超える列が、同一セットのガード・ディジットによってガードされることを可能にする。例えば、多数のテキストの列／欄を有するページ（例えば新聞）は、複数の列／欄におけるメッセージ・ディジットの行の開始を識別する１セットの同期点を記述することによって、符号化されることが可能である。或いは、ページ当たり数行のみを有する複数のページを有するドキュメントにおける各行の開始は、異なるページ上で行の開始を識別する１セットの同期点によって記述されることが可能である。
【００７８】
Ｄ．３  拡張アシスト・チャネル・ブロック・コーディング
ブロック・エラー・コーディングは、ＯＣＲ処理でエラーを識別して訂正する間、改善された同期を提供するが、ブロック・エラー・コーディングは、ＯＣＲ処理の最中に生じる可能性の高いエラーに関する情報を一切使用しない。このセクションでは、ＯＣＲ処理の最中に生じる可能性の高いエラーに関する情報を用いる拡張アシスト・チャネル・ブロック・コーディングに関する２つの代替の実施の形態が示される。
【００７９】
実施の一形態において、復号化は、最も近いメッセージのベクトルよりも寧ろ、オリジナル・メッセージのベクトルである可能性が最も高いメッセージのベクトルを、図２１のステップ２１１８で、検出することにより実行されることが可能である。例えば、カレント・メッセージのベクトルの訂正は、正しくなさそうな単一の訂正よりも寧ろ、「ｃ」を「ｏ」に変え、「Ｉ」を「１」に変えるといった、２つの訂正をすることにより実行され得る。本実施の形態において、アシスト・チャネルのビット当たりのエラー訂正の有効性が改善される。この実施の形態の不利な点は、ブロック・コードの最大尤度による復号化が計算処理的に難しいということである。
【００８０】
計算処理的にそこまでの労力を必要としない別の実施の形態において、分離符号化エラー訂正が、文字コードを再符号化することにより実行される。発生する可能性の最も高いＯＣＲエラーに、発生する可能性のより低いＯＣＲエラーよりも多くのガード・ディジットが割り当てられるように、文字コードが再符号化される。即ち、より多くのエラー訂正が、ＯＣＲ処理の最中にエラーをより受け易いビットに適用される。例えば、表２は、上述の技術を用いて作成される、４つの等価クラスを有する分離コードを示す。４つの等価クラス又はグループ・コード（即ち、ＧＣ）は、プリントされた文字が高位の２ビットによって、符号化されることを可能にする。各グループ・コードは、文字コード（即ち、ＣＣ）又はグループに特有の文字コードの一意の等価クラスを識別する。
【表２】
0004582952.tif 000003
【００８１】
文字を分類する等価クラスを識別する高位の２ビットは、ＯＣＲ処理の最中に、低位のビットのみの場合よりも、変更される可能性が非常に高い。従って、より強力なエラー訂正が、図１９に示される垂直配置において、高位のビットに適用される。
【００８２】
ブロック・コーディングの例として図１７に示されるようにハードコピー・ドキュメントを符号化する場合、この実施の形態は、表２に記載の符号化方式のために、グループ・コード当たりのガード・ディジット数及び文字コード当たりのガード・ディジット数を特定するステップを、ステップ１７０６で実行することを含む。例えば、グループ・コードを用いない５-ディジットのエラー訂正符号で用いられるのとほぼ同じ空間で、この符号化方式は、８-ディジットのエラー訂正符号が高位（「グループ・コード」）の２-ビットに適用されることを可能にし、２-ディジットのエラー訂正符号が低位（「文字コード」）の６-ビットに適用されることを可能にする。
【００８３】
更に、図１７に示されるようにハードコピー・ドキュメントを符号化する際に、オリジナルの文字コードは、それらのグループ・コード及び文字コード表現（即ち、ｇｃ．ｃｃ）に再符号化される。例えば、文字「Ａ」は、例えばASCIIコードからコード「＜０１＞＜００００００＞」に再符号化される。従って、図１９の垂直配置に関すると、参照番号１９１８によって識別されるＧ１のためのガード・ディジットは、垂直列グループ１９２０のためのグループ・コードを保護する第１のセットのガード・ディジットと、垂直列グループ１９２０のための文字コードを保護する第２セットのガード・ディジットとを含む。
【００８４】
復号化する場合、デコーダ・モジュールは、先ず、特定の等価クラスに訂正された高位のビットを有する行上で最適な解を検出することを強いられる。続いて、デコーダ・モジュールは、訂正された高位ビットの低位のビットを訂正する。
低位のビットを用いた訂正は、識別された等価クラスの範囲内の文字のみの訂正に制約される。換言すると、先ず、復号化された行は、チェック・ディジットの高位のビットを用いて修正される。続いて、この行は、チェック・ディジットの低位のビットを用いて、更に修正される。より詳細には、図２１は、本実施の形態において、ステップ２１１６、２１１８及び２１２０を有する、高位のビットのための「外側ループ」と、低位のビットのための「内側ループ」とを含むように変更される。
【００８５】
代替の実施の形態において、高位及び低位のガード・ディジットの列グループのサイズ２００４は変化する。この代替の実施の形態の一態様において、ガード・ディジットの高位のビットは、ガード・ディジットの低位のビット（例えば、より小さい列グループ・サイズである２）よりも大きいサイズ（例えば、より大きい列グループ・サイズである４）を有する列にグループ化される。この符号化フォーマットは、より大きい記号アルファベットを用いて符号化するために、異なる列の高位のビットを一緒にグループ化する。これによりリード・ソロモン・コーディングのエラー訂正を最大に利用している。
【００８６】
Ｅ．アシスト・チャネル畳み込みコーディング
本願明細書では「畳み込みコーディング」と呼ばれる、アシスト・チャネル・コーディングの第３の方法は、一次チャネルの１行の文字の各文字ｃiを連続的にハッシュして、ハッシュ関数の繰返しを計算する。より詳細には、テキスト行の各位置で、カレント・ハッシュはカレント文字コードと組み合せられ、再びハッシュされる。それにより、各文字がテキスト行におけるその文字位置の右の全てのハッシュ値に影響を及ぼす、ハッシュ値の連鎖を生成する。この連鎖内の各ハッシュ値は、（例えば、各ハッシュ値の１ビットを選択することにより）サンプリングされ、アシスト・チャネルにおいて符号化される。続いて、一次チャネルの走査された表現を復号化する際に、テンプレート照合検索は、一致する対応ハッシュ値のサンプル値を生成する解釈に制限される。行における如何なるエラーも、その行の残りのためのハッシュ値の連鎖を変えてしまう可能性が高く、その結果、サンプル値が一致する可能性は低いと推測されるので、適切な一致が識別される迄に調べられる不正確な解釈の数は制限される。
【００８７】
Ｅ．１  アシスト・チャネル畳み込み符号化
図２３は、アシスト・チャネルの畳み込み符号化を実行するためのステップを示すフロー・ダイアグラムである。実施の一形態において、これらのステップは、図１に示される電子アシスト・チャネル１１０により実行される。ステップ２３０２では、データの一次チャネルが、例えば符号化／圧縮モジュール１１６で受信される。データの一次チャネルは、プリンタ等によりハードコピー・ドキュメント上に生成されることが可能な任意の英数字記号を含み得る。ステップ２３０４では、文字データの一次チャネルのカレント行が選択される。ステップ２３０６、２３０８、２３１０、２３１２、２３１４及び２３１６では、一次チャネルの各行が、畳み込み符号化に従って符号化される。
【００８８】
先ずステップ２３０６で、一次チャネルの選択された行（文字ｃ1、ｃ2、ｃ3、...を有する）の最初の文字が、カレント文字ｃiとして識別される。続いてステップ２３０８で、状態変更関数hi=H(hi-1,c[1,i])が繰返し計算される。この式で、ｈ0＝０、ｈi-1は連鎖内の前の値であり、そして、ｃiはカレント文字である。たとえ状態変更関数H(hi-1,c[1,i])が、先行する文字（即ち、c[1,i]=c1,c2,c3,...ci）の何れかに依存し得るとしても、状態変更関数はしばしば、H(hi-1,ci)のような単純な形式を有する。実施の一形態において、状態（state）関数は、Johannesson他による「畳み込みコーディングの基本（Fundamentals Of Convolutional Coding）」（IEEE、1999年、ISBN：0-7803-3483-3）に記載されるように、単純なシフト・レジスタを用いて実施される。代替の実施の形態において、Bruce Schneierによる「応用暗号手法（Applied Cryptography）」（ジョン・ワイリー・アンド・サンズ、ISBN：0-471-11709-9）に記載されるように、より多くの複雑なハッシュ関数が、ＭＤ５のように実施されることができる。ハッシュ関数を選択する際に、異なる入力が同一出力を有する確率が極めて小さい（例えば、２-32）ように、ハッシュ関数が十分に大きい範囲（例えば、２32を超える）を有することが好ましい。
【００８９】
ステップ２３１０で、カレント行の最後の文字に達していない場合は、ステップ２３１２でガード抽出関数gi=G(hi,c[1,i])が用いられ、カレント文字ｃiの状態変更関数のためのガード値（即ち、ｇi）が計算される。たとえガード抽出関数G(hi,c[1,i])が、全ての先行する文字（即ち、ｃ1、ｃ2、ｃ3、...、ｃi）に依存可能であるとしても、ガード抽出関数はしばしば、G(hi,qi)のような単純な形式を有する。この式において、任意の数の先行する文字（即ち、ｃ1、ｃ2、ｃ3、...、ｃi）に依存し得るｑiは、ガード値のビット数を識別するビット・セレクタである。ガード抽出関数Ｇの入力は、ｈi（例えば、カレント文字のハッシュ）及びc[1,i]（即ち、カレント文字を含む先行する文字）を含む。次にステップ２３１４で、カレント文字がカレント行の次の文字になるように割り当てられ、ステップ２３０８が繰り返される。
【００９０】
図２４は、ｑi＝１である場合の、一次チャネル２４０６のカレント行（即ち、「Ｔｈｉｓ」）のための状態変更関数及びガード抽出関数を計算する簡略化された実施の形態を示す。一次チャネル２４０６の各文字は、文字コード２４０８（即ち、ｃ1、ｃ2、ｃ3、及びｃ4）により表される。本実施の形態において、ガード抽出関数は、その全体（即ち、全てのビット）を選択される最後のガード値（即ち、ｇn）を除く、連鎖内の全てのガード値のために、一方向のハッシュ関数２４０４（即ち、ｈi）の出力の低位のビット（即ち、ｑi＝１）を常に選択するようにハードコーディングされる。この実施の形態は、ガード抽出関数に対する出力として生成されるガード値２４１０が、特定の符号化方式のために固定されることが可能であることを示す。
【００９１】
図２５は、一次チャネルの行における各対応する文字コード２５０３のためのガード値２５０１をステップ２３１６で生成するために、ステップ２３０８で実行される繰返し計算のより一般化された表現を示す。本実施の形態において、ガード抽出関数G(hi,c[1,i])２５０２は、対応する状態変更関数２５０４（即ち、hi=H(hi-1,ci)）から入力を受信する。カレント文字ｈiの状態変更関数２５０４の出力から選択されるビット数は、文字c[1,i]の値における累積的な不確実性に依存する（即ち、より確実なほど、選択されるビット数は少ない）。この不確実性は、値ｑiにより各ガード値ごとに定量化され、この値ｑiは、ガード値（単数又は複数）ｇiを定義するために各状態ｈiから可変の数を選択するために用いられる。
【００９２】
図２３を再度参照する。ステップ２３１０で、カレント行の最後の文字に達した場合は、ガード値ｇnがステップ２３１１で計算される。次にステップ２３１６で、アシスト・チャネルが、計算されたガード抽出関数（即ち、ｇ1、...、ｇn）によって、カレント行から増補される。ステップ２３１８で、選択された行が一次チャネルの最後の行でない場合は、カレント行はステップ２３２０で一次チャネルの次の行になるように割り当てられ、ステップ２３０６が繰り返される。最後の行である場合は、アシスト・チャネルは、例えば図１０に示されるようにデータ・グリフ等を用いて機械で読み取り可能な情報としてステップ２３２４で符号化される。最後にステップ２３２６で、一次チャネル及びアシスト・チャネルは連結され、例えば図１に示されるプリンタ１０８を用いてハードコピー・ドキュメント上に表現される。
【００９３】
Ｅ．２  アシスト・チャネル畳み込み復号化
図２６は、走査されたハードコピー・ドキュメントを、畳み込み符号化されたアシスト・チャネルを用いて復号化するために、図２に示されるハードコピー・アシスト・チャネルにより実行されるステップを説明するフロー・ダイアグラムを示す。先ずステップ２６０２で、ビットマップ画像２０６が、ハードコピー・ドキュメント１０６のスキャナを用いて取得される。この例では、ハードコピー・ドキュメント１０６は、一次チャネル１２４及び畳み込み符号化されたアシスト・チャネル１２６を含む。ステップ２６０４では、画像抽出モジュール２１０が、アシスト・チャネル１１８及びビットマップ一次チャネル２１４をビットマップ画像２０６から抽出する。アシスト・チャネル１１８は、モジュール２１２により、ステップ２６０６で復号化される。続いてステップ２６１０で、ビットマップ一次チャネルの各行は、復号化されたアシスト・チャネルを用いて復号化される。デコーダ・モジュール２１６がステップ２６１２で完了すると、復号化された一次チャネル１１２は、ドキュメント１０２の参照符号１１４で示されるディスプレイ１０４上に電子形式で表示されることが可能である。
【００９４】
図２７は、図２６に示されるステップ２６１０を更に詳細に説明するフロー・ダイアグラムである。ステップ２７０２では、優先順位付き待ち行列が、一次チャネルのカレント行のために、空の候補Ｃ＝(ｃ'＝φ、ｈ'＝０、ｓ'＝０、ｋ'＝０）によって初期化される。この式において、ｃ'＝ｃ1'ｃ2'...、ｃi-1'は、テキストのカレント行の接頭部の可能な解釈であり、ｈ’は、可能な解釈ｃ’を処理した後の状態変更関数の値であり、得点ｓ’は、一次チャネルの行の可能な解釈ｃ’の品質を測定し、そしてｋ’は、カレント候補のためのカレント・ガード値の位置である。
【００９５】
ステップ２７０４では、最も高い得点を有する候補が、優先順位付き待ち行列から取り出され、カレント候補Ｃbestとして定義される。行の接頭部のＣbestの解釈は、ｃ'＝ｃ1'ｃ2'...、ｃi-1'である。ステップ２７０８では、カレント候補Ｃbestの行の接頭部ｃ'＝ｃ1'ｃ2'...ｃi-1'の全ての拡張文字ｃi'（即ち、復号化文字）が識別される。更に、ステップ２７０４では、ｈi-1'をこの候補のカレント・ハッシュとし、ｓi-1'を候補のカレント得点とし、そして、ｋ’をアシスト・チャネルの最初の一致しないガード値の位置とする。更にステップ２７０８では、各可能な拡張文字ｃi'が、一次チャネルのカレント行の残りの部分に対して得点され、これにより、新しい得点ｓi'＝ｓi-1'＋Ｓ(ｃi')を取得する。ステップ２７１０では、状態変更関数hi'=H(hi',ci'[1,i])及びガード抽出関数gi'=G(hi',c'[1,i])のための値が、ステップ２７０８で識別される各拡張文字ci'ごとに計算される。
【００９６】
ステップ２７１２では、位置ｋiから始まるアシスト・チャネルのガード値ｇiに等しい、ステップ２７１０で計算されたガード抽出関数ｇi'を有する、ステップ２７０８で識別された拡張文字ｃi'のそれぞれが、候補Ｃnext(ｃ'＝ｃ1'ｃ2'...ｃi'、ｈi'、ｓi'、ｋi'）として、優先順位付き待ち行列に加えられる。ステップ２７１４では、計算されたガード値ｇi'が、カレント行のためのアシスト・チャネルの最後のガード値ｇnに等しい場合、一次チャネルのカレント行の終わりに達したことを意味するので、ステップ２７１６が実行される。ｇnに等しくない場合は、ステップ２７０４が次の最良の候補のために繰り返される。ステップ２７１６で、ビットマップ一次チャネルの全ての行が処理されているならば、ステップ２６１０はステップ２６１２に進む。そうでない場合、カレント行はステップ２７１８で次の行間隔へ進み、ステップ２７０２が繰り返される。
【００９７】
図２８は、図２７に示されるステップに従って、図２４に示される一次チャネルのカレント行２４０６を復号化する方法のグラフ図２８０２を示す。先ず、空の候補２８０３によりグラフが定義される。第１の文字空間のための拡張文字２８０４乃至２８０７が識別される。拡張文字２８０４乃至２８０７の中で、拡張文字２８０４及び２８０７のガード値がアシスト・チャネルのガード値と一致した（即ち、ｇi'＝ｇi）ので、拡張文字２８０４及び２８０７のみが優先順位付き待ち行列に加えられる点に留意すべきである。続いて、拡張文字２８０７が最高の計算された得点を有したので、次の繰返しでは、拡張２８０７が選択される。一次チャネル２４０６のビットマップは、図２７に示されるステップを４回繰返すことによって復号化される。各繰返しの開始時に選択される優先順位付き待ち行列の最良の候補は、参照番号２８０７、２８１０、２８１２及び２８１４により識別される。Johannesson他による「畳み込みコーディングの基本」（IEEE、1999年、ISBN：0-7803-3483-3）に開示されているように、系統的な復号化技術以外の畳み込み復号化技術が、Viterbi等の発明、即ちリスト復号化技術を実行するために用いられることが可能であることは、当業者により理解されるであろう。
【００９８】
Ｅ．３  変調アシスト・チャネル畳み込みコーディング
図２９は、図２５に示される畳み込みコーダーを、本願明細書では「変調畳み込みコーディング」と呼ばれる、一体化された分離コーダー２９０２と分離コード・コンプレッサ２９０４と共に示す。本実施の形態において、アシスト・チャネルは、ハードコピー・ドキュメントにプリントされた記号を、一次チャネルの各文字の文字コードのハッシュから導き出されるガード値を用いて分離コードの圧縮をスクランブルすることによって保護する。復号化する際に、スクランブルを解かれた分離コードは、テンプレート照合検索の実行時のエラーを容易に回避することを可能にする。
【００９９】
図２５に示される実施の形態に類似して、状態変更関数２５０４及びガード抽出関数２５０２は、ガード値２５０１（即ち、ｇ1、...、ｇn）を生成する。しかしながら、対照的に、図２９に示される実施の形態は、圧縮された分離コード２９０８（即ち、ｃｄ1、...、ｃｄn）の処理結果を、ガード値２５０１（即ち、ｇ1、...、ｇn-1）を用いてスクランブルする。圧縮された分離コード２９０８は、ガード値ｇnと共にアシスト・チャネルにおいて符号化される。
【０１００】
即ち、上述の畳み込みコーディングに類似して、状態変更関数２５０４は、状態変更関数hi=H(hi-1,ci)の反復を介して生成される。しかしながら、この状態変更関数をサンプリングし、その結果をアシスト・チャネルにおいて符号化するよりも寧ろ、状態変更関数のサンプルは、分離コーディングに基づくアシスト・チャネルのコーディングを変更するために用いられる。状態変更関数がアシスト・チャネルを変更するために用いられる方法は、分離コーディングが圧縮される方法に依存する。
【０１０１】
図２９に示されるように、文字コード２５０３は分離コーダー２９０２に入力され、この分離コーダー２９０２は、出力として分離コード２９０６を生成する。実施の一形態において、分離コーダー２９０２は、上述のセクションＣで説明された方法で一次チャネルの文字コードを符号化する。実施の一形態の分離コード・コンプレッサ２９０４は、変更された算術に基づく符号化技術を用いて分離コード２９０６を圧縮する。この例は、Witten他により、「データ圧縮のための算術コーディング（Arithmetic Coding for Data Compression）」（Comm. ACM第３０巻６刷、第520〜540頁、1987年）において記述されている。本実施の形態において、分離コードの等価クラス・ラベルは、等価クラスの公算に基づく算術符号化技術によって圧縮される。
【０１０２】
より詳細には、拡張された畳み込みアシスト・チャネルの符号化は、一次チャネルの各行の第１の符号化及び第２の符号化を必要とする。第１の符号化は、一次チャネルの所定のテキスト文字列ｃ1、ｃ2、ｃ3、...、ｃnに対して実行され、このテキスト文字列の文字を等価クラスｚ1、ｚ2、ｚ3、...、ｚm（例えば、図７のグループ・ラベルａ、ｂ、ｃ）に分類し、ｄ1がｚ1、ｚ2、ｚ3、...、ｚmの１つであるようなクラス・ラベルの減少された文字列ｄ1、ｄ2、ｄ3、...、ｄnを取得する。算術コンプレッサは、区間に関する計算として記述されることが可能であり、Ｐ（ｚi）が、ｚiとラベル付けされた等価クラスの確率である場合、区間［０，１］は、部分区間（サブインターバル）［ｓ0，ｓ1］、［ｓ1，ｓ2］、...に分割される。この場合、ｓiは確率の累積和である。即ち、ｓi＝Σj≦iＰ（ｚi）。これは、ｉ番目の等価クラスに対応するｉ番目の部分区間の幅Ｐ（ｚi）を提供する。一般性を損失することなく、区間は、最大の（最も可能性の高い）ものから最小のものに順序づけられると仮定される。クラス・ラベルの文字列ｄ1、ｄ2、ｄ3、...、ｄnは、以下の反復により圧縮される。
【数１】
0004582952.tif 000004
【０１０３】
選択演算子Ｓは、以下の式により示されるｄiの等価クラスのための区間が区間［０，１］に対するのと同じ比率で、カレント区間［ｘ，ｙ］内の区間［ｘ',ｙ'］を選択する。このように、区間ｒ1は、クラス・ラベルの文字列ｄ1、ｄ2、ｄ3、...、ｄnを一意に決定し、log(P(d1)P(d2)P(d3)...P(di))+1ビットの上限が特定されることを必要とする。
【数２】
0004582952.tif 000005
【０１０４】
第２の符号化は、対応する状態変更関数ｈ1、ｈ2、ｈ3、...、ｈnを計算するために、一次チャネルの所定のテキスト文字列ｃ1、ｃ2、ｃ3、...、ｃnに対して実行される。実施の一形態において、ｈiは、Ｇ(ｈi)が０又は１に等しい確率が同じであるような、２値関数Ｇによりサンプリングされる。続いて、図２９に示すように、状態変更関数の出力が、選択区間を並べ替えることによって、算術エンコーダ２９０４を変更するために用いられる。区間［０，１］の部分区間［ｓ0，ｓ1］、［ｓ1，ｓ2］、...、への分割のために、［μ(ｓ0),μ(ｓ1)］、［μ(ｓ1),μ(ｓ2)］、［μ(ｓ2),μ(ｓ3)］、...が［０，１］を包括するパーティションであり、区間長さが||μ(ｓi+1)−μ(ｓi)||＝||ｓi+1−ｓi||として保持されるように、順列μが定義される。順列演算子は、単一のビットに依存するように定義され、次式のような状態変更関数により提供される。
【数３】
0004582952.tif 000006
【０１０５】
順列μは、可能な限り大きい同期はずれをもたらすように選択される。第１の区間が１／２より大きい場合、逆順列μ(ｘ)＝１−ｘは十分である。最大の区間が１／２未満である場合、順列の画像において区間自体が重ならないように、順列を選択することが好ましい。演算子Ｒ(ｇ,[ａ，ｂ])を用いると、算術圧縮反復は、以下のように書き直されることができる。
【数４】
0004582952.tif 000007
【０１０６】
図３０は、ガード値２５０１を用いて分離コード２９０６の圧縮２９０４をスクランブルする例を示す。図３０において、分離コード（又はクラス）ラベル「ａ」「ｂ」及び「ｃ」の文字列が０及び１との間の実数により符号化される。クラス・ラベル「ａ」「ｂ」及び「ｃ」のそれぞれに対して割り当てられる確率は、区間３００２を定義するためには、１／２対１／３対１／６の割合（即ち、０〜０．５、０．５〜０．８３３、０．８３３〜１．０）である。図３０に示されるこの例は、符号化されているクラス・ラベルの文字列は、「ｂ」から始まり、「ａ」が続くと仮定する。「ｂ」クラス・ラベルから開始すると、選択される区間は、[０．５，０．８３３]である。次の区間は、区間３００４及び区間３００６の何れかから選択される。これらの区間は、計算された単一ビットのガード値ｇ1が１に等しいか０に等しいかに従って、切り替えられる。分離コード「ａ」が続くことにより、次の区間は、３０１２でガード値ｇ1が０に等しいか１に等しいかに従って、それぞれ３００８又は３０１０の値の範囲により定義され、これにより、ガード値に基づいて、分離コードの圧縮をスクランブルする。
【０１０７】
図３１は、スクランブルされた畳み込み符号化アシスト・チャネルを用いて、一次チャネルの各行を復号化するための図２６に示されるステップ２６１０の詳細を説明するフロー・ダイアグラムである。図２７に示されるステップ２７０２に類似して、ステップ３１０２は、優先順位付き待ち行列を空の候補Ｃ0によって初期化する。続いてステップ３１０４では、Ｃbestとして定義される候補が、コンプレッサ２９０４のカレント状態がｒi-1'として記録されること以外はステップ２７０４と同様に、優先順位付き待ち行列から取り出される。ステップ３１０６では、分離コード・ラベルｄi'が、アシスト・チャネルからの圧縮された分離コード・ラベルｃｄi、コンプレッサの前の状態ｒi-1、及び前のガード値ｇi-1を用いて圧縮解除される。分離コード・ラベルｄi'は、行の接頭部ｃ'の次の拡張文字のために計算される分離クラスである。
【０１０８】
ステップ３１０８では、Ｃbestの全ての拡張文字ｃi'が識別される。ｃi'は、ｄiとラベル付けされた計算された分離クラスに属する。更にステップ３１０８では、識別される可能な拡張文字ｃi'のそれぞれが、一次チャネルのカレント行の残りの部分に対して得点され、これにより、新しい得点ｓi'＝ｓi-1'＋Ｓ(ｃi')を取得する。最後にステップ３１１２では、全ての識別された拡張文字ｃi'のための候補Ｃnextが、優先順位付き待ち行列に加えられる。ステップ３１１４、３１１６及び３１１８は、図２７に示され上述されたステップ２７１４、２７１６及び２７１８に対応することに留意されたい。
【０１０９】
このように、計算されたガード値が、アシスト・チャネルのガード値と一致しない候補を、優先順位付き待ち行列から削除する図２７に示される復号化技術とは異なり、図３１の復号化技術は、正しい分離クラスに属さない候補を削除する。しかしながら、図２７及び３１のアルゴリズムは、特定候補の復号化エラーにが、その候補の全ての拡張文字に不十分な得点をもたらすであろうという点で、類似している。図３１において、候補におけるエラーの後、ステップ３１０６で圧縮解除された分離クラスｄiは、正しいというよりも寧ろ、ほぼランダムであろう。従って、ステップ３１０８で最適な拡張文字が調査されないかなりの確率が存在し、結果として、エラーを含んでいる候補の拡張文字の得点を低下させる。
【０１１０】
状態変更関数の計算を種々の圧縮アルゴリズムと連結することが可能であることは、当業者により理解されるであろう。このアプローチの背後にある一般的な観念は、状態変更関数の値が、達成される圧縮の質に影響を及ぼさないがエラー発生後に圧縮解除の結果をスクランブルするように、圧縮アルゴリズムの機能を変更するというものである。例えば、ジブ−レンペル−ウェルチ（Ziv-Lempel-Welch）の（ＬＺＷ）コンプレッサは、コーディングの前にコンプレッサのディクショナリ・インデックスを用いて、状態変更関数ｈi-1のビットのサブセットをＸＯＲする（排他的論理和をとる）ことによって、圧縮をスクランブルするように変更されてもよい。
【０１１１】
Ｆ.リライト・モデルを用いた代替動作環境
セクションＡで説明された動作環境では、ＤＩＤ様式のデコーダの最短経路は、アシスト・チャネルの情報を考慮するように変更される。このように、デコーダは、アシスト・チャネルの情報と整合している一致する解を識別することによって最短経路を検出するように変更される。即ち、図２に示されるデコーダの動作環境で実行される最短経路計算は、アシスト・チャネルにより訂正される復号化エラーと整合している最短経路を検出するように増分的に適用されることが可能である。
【０１１２】
図３２は、図２に示されるハードコピー・アシスト・チャネル２０４の代替の実施の形態を示す。この代替の実施の形態において、アシスト・チャネルは、デコーダ・モジュール３２０４とは独立して動作する。従って、この代替の実施の形態において、アシスト・チャネルは、如何なる特定のＯＣＲ復号化プロセスとも一体化される必要はない。その代わりに、アシスト・チャネルは、ビットマップ画像の最初の復号化を実行する任意のＯＣＲエンジンとは独立してデコーダ・エラーをモデル化するリライト・モジュールへ入力される。
【０１１３】
図２に示される実施の形態に類似して、図３２の画像抽出モジュール２１０は、ビットマップ画像データ２０６を受信し、アシスト・チャネル１１８のデータとビットマップ一次チャネル２１４のデータとを切り離す。しかしながら、本実施の形態では、デコーダ・モジュール３２０４は、復号化及び圧縮解除されたアシスト・チャネル２１９からのサポートなしに、ビットマップ一次データ２１４を復号化し、一次データの候補３２０２を生成する。また、本実施の形態では、リライト・モジュール３２００が、一次データの候補３２０２と、復号化及び圧縮解除されたアシスト・チャネル２１９とを入力として受け取り、データ１１２の一次チャネルを生成する。
【０１１４】
作動時に、リライト・モジュール３２００は、イベント・ライブラリを用いて一次データの候補３２０２のグラフを定義する。イベント・ライブラリは、ＯＣＲ処理の最中に発生し得る様々な失敗イベントの確率を測定することにより、デコーダ・モジュール３２０４にＯＣＲエンジンのための失敗モデルを構築するために用いられる。これらの失敗イベントは、一般的（即ち、全てのＯＣＲエンジンで発生する傾向がある）であっても、特殊（即ち、所定のＯＣＲエンジンでのみ発生する傾向がある）であってもよい。例えば、図３３は、特殊な規則３３０４と、如何なる場合にも対応可能な規則３３０８を含む、より汎用的な規則３３０６とを明記するイベント・ライブラリ３３０２を示す。重み３３１０が各規則に割り当てられる。重みが小さいほど、そのイベントがデコーダ・モジュールで発生する確率が高い。その結果として、識別変換３３１２（即ち、変換を行わない）は、最も小さい重みを割り当てられるか、又はそのような変換の内の１つであり得る。失敗イベントの１つの例はイベント３３１４（即ち、ｒｎ→ｍ）であり、これは原形の損失（即ち、「ｒｎ」）及びその誤りの訂正（即ち、「ｍ」）を定義する。
【０１１５】
実施の一形態において、失敗モデルは、その状態に戻る遷移のみを有する単一の状態を含む単純な構造を有する重み付けされた有限状態トランスデューサである。本実施の形態において、重み付けされた有限状態トランスデューサの単純さのために、失敗モデルを、重み付けされた有限状態トランスデューサの十分に一般化された定式化により処理することは必要でない。代替の実施の形態において、Jones他により「ベイズ流ＯＣＲポスト・プロセッサにおける複数の知識ソースの一体化（Integrating Multiple Knowledge Sources in A Bayesian OCR Post-Processor）」、（ＩＣＤＡＲ  '９１  サン‐マロ（フランス）の会報第２巻、第925〜933頁）において説明されているような、言語モデルを組み入れる重み付けされた有限状態トランスデューサのより一般化された定式化が用いられる。
この重み付けされた有限状態トランスデューサのより一般化された定式化は、リライト・モジュールが、デコーダ・モジュールのＯＣＲエンジンに組み込まれた任意の言語モデルにアクセスすることができないことを考慮する。
【０１１６】
イベント・ライブラリ３３０２において定義される失敗モデルを用いて、リライト・モジュール３２００は、デコーダ・モジュール３２０４により復号化された一次データの候補３２０２を、アシスト・チャネル２１９の援助を受けてリライトする（書き直す）。実施の一形態において、リライトは、失敗モデル及びアシスト・チャネルを使用して、一次データの候補３２０２の最短経路を（ビタービ・アルゴリズムを用いたダイナミック・プログラミングを用いて）計算することにより実行される。このリライト動作は、最も可能性の高い一次チャネル・データ１１２を検出する。換言すると、この最短経路計算は、上述されたデコーダ・モジュール２１６で動作するＤＩＤ  ＯＣＲエンジンで行われる最短経路計算のための代用物をもたらす。そして、これにより、アシスト・チャネルが、デコーダ・モジュール３２０４で動作可能な任意のＯＣＲエンジンに適用されることを可能にする。
【０１１７】
図１２に関連して上述されたように、最短経路の計算は、グラフを定義するステップ及び最短経路を計算するステップを含む。ＤＩＤ  ＯＣＲエンジンの本実施の形態におけるグラフを定義するステップは、図３４の参照番号３４００で明記される。ステップ３４００を用いてグラフが定義されると、グラフの最短経路が、上記に詳述された図１２に示されるステップ１２０１を用いて計算される。
【０１１８】
グラフを定義するための図３４に示されるステップ３４００は、一次データの候補３２０２からテキスト行の各文字（又は、記号）の位置で、グラフ内のノードを定義するステップ３４０２を含む。換言すると、グラフのノードは、一次データの候補の各テキスト位置に対応する。ステップ３４０４では、各ノードごとに、イベント・ライブラリ３３０２がサーチされ、イベントの左側がそのノード（即ち、カレント・ノード）から開始する文字列と一致する場合には、アークが加えられる。アークの得点は、そのイベントの重みである。アークの宛先ノードの位置は、カレント・ノードの位置に、一致したイベントの左側の文字数を加えた位置に等しい。
【０１１９】
図３５は、図３４で説明されるステップに従って定義されるグラフの例を示す。ＯＣＲ解釈の候補３５０５は、抽出されたビットマップ一次チャネル３５０３から、例えばＤＩＤ  ＯＣＲエンジンを用いて計算される。ＯＣＲ解釈の候補３５０５における各文字位置３５０６で、グラフ３５０２のノード３５０４が定義される（ステップ３４０２）。あるノードで開始する文字の位置により定義される文字列が、イベント・ライブラリの文字列と一致する場合、アークがグラフのノード間に引かれ、リライト及び得点を割り当てられる。例えば、アーク３５０８は、ＯＣＲ解釈の候補３５０５の文字列「ｒｎ」と、イベント・ライブラリ３３０２の文字列３３１４との間の一致のために、得点及びリライト（即ち、「ｍ」）を与えられる（ステップ３４０４）。グラフ３５０２の最短アークは、イベント・ライブラリにおいて定義される識別変換３３１２であることに留意すべきである。
【０１２０】
代替の実施の形態において、デコーダ・モジュール３２０４は、リライト・モジュール３２００に配信される一次データの候補３２０２と共に、確実性予測等の他のＯＣＲデータを含む。実施の一形態において、これらの確実性予測は、ステップ３４０４でアークの得点に組み入れられる。従って、デコーダ・モジュール３２０４及びリライト・モジュール３２００は、互いに独立して動作するが、リライト・モジュール３２００は、デコーダ・モジュール３２０４に提供され得る他の統計情報を利用することができる。
【０１２１】
図３６は、図３５で定義されるグラフの、図１１及び１２で説明されるステップ１２０１による復号化を示す。図３６に示される例において、プロダクト・グラフ３６００は、図１６で定義されるプロダクト・グラフに類似の方法で定義される。分離コードを用いて符号化されたアシスト・チャネルを用いて、一次チャネルを復号化するための図１１で説明されるステップは、ＯＣＲ解釈の候補をリライトするために適用されることができる。但し、ステップ１１１０で取得される一次チャネルの各行は、ビットマップ一次チャネル２１４ではなく、ＯＣＲ解釈３５０５の行に対応する。
【０１２２】
例示のために、図３６に定義されるグラフの復号化の例は、図３５の最初の４つの記号のみを説明する。また、簡潔さのために、プロダクト・グラフ３６００の形成方法を示す極くわずかのアークが図３６に示される。上記に詳述された分離復号化に従って、プロダクト・グラフ３６００の第１の次元３６０２が定義される。リライト・モジュール３２００が、第１の次元３６０２におけるグラフの最短経路計算でなく、寧ろプロダクト・グラフにおける最短経路計算を実行することは、当業者により理解されるであろう。
【０１２３】
図３６に示されるように、アシストされずに復号化された一次チャネル３６０６の出力（即ち、一次データの候補３２０２である文字「Ｆｄｂｗ」）は、プロダクト・グラフ３６００のアシスト・チャネルを用いて訂正され、訂正された出力３６２０（即ち、一次チャネル・データ１１２である文字「Ｆｏｌｌｏｗ」を生成する。プロダクト・グラフを定義する際に、リライト・モジュール３２００は、ＯＣＲ解釈の候補３６０２における文字位置、及び対応するアシスト・チャネル３６０４における位置の両方を識別する。図３６に示されるアシスト・チャネルの例は、図７に示される３つのグループに分類される分離コードを用いて定義される。プロダクト・グラフ３６００を定義する際に、文字「ｄ」が、アーク３６１０でアシスト・チャネルの第２の位置により要求されるように、分離グループ「ｂ」にではなく、分離グループ「ａ」に分類されるので、アーク３６０８はプロダクト・グラフから除外される。しかしながら、アーク３６１２はアシスト・チャネルの第４の位置３６１３に該当するが、次のアーク３６１４がアシスト・チャネルの第５の位置３６１５に該当しないことに留意すべきである。プロダクト・グラフ３６００が定義されると、プロダクト・グラフの最短経路の計算は、文字「Ｆｏｌｌｏｗ」を含む出力文字列３６２０を生成する。
【０１２４】
リライト・モジュールが、図３６に示されるような分離コーディングを用いたオペレーションに限定される必要はないことは、当業者により理解されるであろう。代わりに、リライト・モジュールは、図２に示される動作環境に関連して上述されたように、ブロック・コーディング及び畳み込みコーディングに従って動作することが可能である。また、図２に示されるデコーダ・モジュール２１６により実行される畳み込みコーディングが、グラフ（例えば、図１６に示されるグラフ１６０２）をツリー（例えば、図２８に示されるツリー２８０２）に変更するのと同様に、畳み込みリライト・モジュールと共に動作する図３２に示されるリライト・モジュール３２００が、図３６に示されるグラフ３６０２をツリーに変更し得ることを、当業者は理解するであろう。
【０１２５】
デコーダ３２０４によって復号化される一次チャネルの文字又は記号は、失敗モデルにより識別される他のいかなるイベントよりも正しい可能性が高いはずなので、リライト処理がアシスト・チャネルの援助を伴って実行されない限り、リライト・モジュールによる一次データの候補のリライトは、無意味（即ち、識別変換）になる可能性が高いことは、当業者により更に理解されるであろう。結果として、アシスト・チャネルが、一次データの候補に現れる文字を、次の最適な解釈により制限するか、又は訂正した場合、失敗モデルは有用になる。一次データの候補のこのような制限又は訂正は、リライト・モジュールにより識別される誤り（例えば、ｒｎ→ｍ）によって暗示される、図３６に示されるようなデータの再同期化を含むことができる。
【０１２６】
要約すると、図３２に示される、デコーダ・モジュールに依存しないＯＣＲ誤りを訂正するためにアシスト・チャネルを用いるリライト・モジュールを含む、より一般化されたハードコピー・アシスト・チャネルは、図２に示される一体化されたハードコピー・アシスト・チャネルよりも効率が悪い可能性がある。ＯＣＲデコーダにより用いられる統計情報の全てが、リライト・モジュールに把握されるわけではないために、一般化されたハードコピー・アシスト・チャネルで、非効率性が生じる。即ち、図２のアシスト・チャネルと一体化されるＤＩＤ  ＯＣＲエンジンは、復号化されているビットマップ一次チャネルに特有の、他の解釈に関するより多くの統計情報を用いることができる。対照的に、図３２に示されるリライト・モジュールは、任意の一般のドキュメントで発生するＯＣＲ誤りの失敗モデル統計情報内の情報のみ利用可能である。しかしながら、図３２に示される一般化されたハードコピー・アシスト・チャネルの主たる利点は、デコーダ・モジュールでのオペレーションのために選択されるＯＣＲエンジンとは独立しているリライト・モジュールにおいて、任意のアシスト・チャネル復号化技術（即ち、分離コーディング、ブロック・コーディング、又は畳み込みコーディング）が、動作可能なことである。上述されたＤＩＤ  ＯＣＲエンジンの他に、デコーダ・モジュールで動作可能な他のＯＣＲエンジンには、ScanSoft社（www.scansoft.com）により製作されたテキスト・ブリッジ・プロ・ミレニアム（TextBridge Pro Millennium）のＯＣＲエンジンを含むことは、当業者により理解されるであろう。
【図面の簡単な説明】
【図１】ディスプレイ上に表示及び／又は生成される電子ドキュメントの授受を示す（ブロック）図である。
【図２】ハードコピー・ドキュメント上に表現される一次チャネル及びアシスト・チャネルからのデータと共に、ハードコピー・ドメイン及び電子ドメインの間でのハードコピー・ドキュメントの授受を示す（ブロック）図である。
【図３】本発明の分離符号化を実行するための一般的なステップを有するフロー・ダイアグラムである。
【図４】図３に示されるステップ３０８を更に詳細に説明するフロー・ダイアグラムである。
【図５】４つの記号「ｅ」、「ｐ」、「ｂ」及び「ｃ」の識別されたアルファベットのグラフの例を、その文字が発生する可能性を記録する、記号に対応するノードと共にに示す図である。
【図６】利得を最大にする一方で、エントロピーを最小にするカレント・パーティションを識別するための反復プロセスを示すグラフである。
【図７】１セットの記号が３グループに分類されるパーティションを示す図である。
【図８】一次チャネルの例を示す図である。
【図９】図７に示されるパーティションを使用して作成される図８に示される一次チャネルのためのアシスト・チャネルを示す図である。
【図１０】データ・グリフを使用して符号化されるアシスト・チャネルの例を示す図である。
【図１１】アシスト・チャネルによって増補されるハードコピー・ドキュメントの一次チャネルを復号化するために、ハードコピー・アシスト・チャネルにより実行されるステップのフロー・ダイアグラムである。
【図１２】一次チャネルのグラフの最短経路を計算するためのステップを説明するフロー・ダイアグラムである。
【図１３】図８に示される一次チャネル８００の行の文字８０２のビットマップ表現のためのノードを有するグラフを示す図である。
【図１４】ビタービ・アルゴリズムを用いたフォワードパス計算の例を示す図である。
【図１５】図１４で作成されるグラフと逆方向にトレースする（即ち、ビタービ・アルゴリズムのバックワードパス計算）例を示す図である。
【図１６】プロダクト・グラフの最短経路計算の例を示す図である。
【図１７】アシスト・チャネルのブロック符号化を実行するためのステップのフロー・ダイアグラムである。
【図１８】データの一次チャネルの例を示す図である。
【図１９】図１８に示される一次チャネルの記号データの特定の垂直ブロックごとに、ガード・ディジットが計算される例を示す図である。
【図２０】図１８に示されるデータの一次チャネルの例のために集められたデータを示す図である。
【図２１】ブロック符号化されたアシスト・チャネルを有する走査されたハードコピー・ドキュメントを復号化するために、ハードコピー・アシスト・チャネルにより実行されるステップを説明するフロー・ダイアグラムである。
【図２２】図１８に示される一次チャネルの一部に対して実行される最短経路計算の再解釈の詳細な例を示す図である。
【図２３】アシスト・チャネルの畳み込み符号化を実行するためのステップを示すフロー・ダイアグラムである。
【図２４】ガード値のビット数ｑi＝１である場合の、一次チャネルのカレント行（即ち、「Ｔｈｉｓ」）のための状態変更関数及びガード抽出関数の計算の簡略化された実施の形態を示す図である。
【図２５】一次チャネルの行内の対応する文字コードのそれぞれごとにガード値を生成するために実行される反復計算のより一般化された表現を示す図である。
【図２６】畳み込み符号化されたアシスト・チャネルを有する走査されたハードコピー・ドキュメントを復号化するために、図２に示されるハードコピー・アシスト・チャネルにより実行されるステップを説明するフロー・ダイアグラムである。
【図２７】図２６に示されるステップ２６１０をより詳細に説明するフロー・ダイアグラムである。
【図２８】図２７に示されるステップに従って、図２４に示される一次チャネルのカレント行を復号化する方法を示すグラフ図である。
【図２９】本願明細書で「変調された畳み込みコーディング」と呼ばれる、一体化された分離コーダー及び分離コード・コンプレッサを有する図２５に示される畳み込みコーダーを示す図である。
【図３０】ガード値を用いた算術符号化により圧縮される分離コードのスクランブリングの例を示す図である。
【図３１】スクランブルされた畳み込み符号化アシスト・チャネルを用いて一次チャネルの各行を復号化するための図２６に示されるステップ２６１０の詳細を説明するフロー・ダイアグラムである。
【図３２】図２に示されるハードコピー・アシスト・チャネルの代替の実施の形態を示す（ブロック）図である。
【図３３】デコーダ・モジュールのＯＣＲエンジンのための失敗モデルを構築するために用いられるイベント・ライブラリを示す図である。
【図３４】図３３に示されるイベント・ライブラリを用いて、図３２に示されるリライト・モジュールにより実行されるグラフを定義するためのステップを説明するフロー・ダイアグラムである。
【図３５】図３４で説明されるステップに従って定義されるグラフの例である。
【図３６】図１２で説明されるステップ１２０１で定義されるグラフの復号化の例を示す図である。
【符号の説明】
１０２    電子ドキュメント
１０４    ディスプレイ
１０６    ハードコピー・ドキュメント
１０８    プリンタ
１１０    電子アシスト・チャネル
１１２    一次チャネル
１１６    符号化／圧縮モジュール
１１８    アシスト・チャネル
１２０    マージ・モジュール
１２２    増補画像データ
１２４    一次チャネル・データ
１２６    アシスト・チャネル・データ
２０４    ハードコピー・アシスト・チャネル
２０６    ビットマップ画像データ
２０８    スキャナ
２１０    画像抽出モジュール
２１２    復号化／圧縮解除モジュール
２１４    ビットマップ一次チャネル
２１６    デコーダ・モジュール
【図１】
0004582952.tif 000008
【図２】
0004582952.tif 000009
【図３】
0004582952.tif 000010
【図４】
0004582952.tif 000011
【図５】
0004582952.tif 000012
【図６】
0004582952.tif 000013
【図７】
0004582952.tif 000014
【図８】
0004582952.tif 000015
【図９】
0004582952.tif 000016
【図１０】
0004582952.tif 000017
【図１１】
0004582952.tif 000018
【図１２】
0004582952.tif 000019
【図１３】
0004582952.tif 000020
【図１４】
0004582952.tif 000021
【図１５】
0004582952.tif 000022
【図１６】
0004582952.tif 000023
【図１７】
0004582952.tif 000024
【図１８】
0004582952.tif 000025
【図１９】
0004582952.tif 000026
【図２０】
0004582952.tif 000027
【図２１】
0004582952.tif 000028
【図２２】
0004582952.tif 000029
【図２３】
0004582952.tif 000030
【図２４】
0004582952.tif 000031
【図２５】
0004582952.tif 000032
【図２６】
0004582952.tif 000033
【図２７】
0004582952.tif 000034
【図２８】
0004582952.tif 000035
【図２９】
0004582952.tif 000036
【図３０】
0004582952.tif 000037
【図３１】
0004582952.tif 000038
【図３２】
0004582952.tif 000039
【図３３】
0004582952.tif 000040
【図３４】
0004582952.tif 000041
【図３５】
0004582952.tif 000042
【図３６】
0004582952.tif 000043