(57)【特許請求の範囲】
【請求項１】
プロセッサによって制御されるマシンを作動させテキスト行イメージをデコードする方法であって、
前記テキスト行イメージの各イメージ位置を順に処理対象として、スキップモードスイッチをオフとした状態の処理またはスキップモードスイッチをオンとした状態の処理を実行することを複数回の反復により繰り返し、
前記スキップモードスイッチをオフとした状態の処理は、
前記テキスト行イメージの開始位置から前記処理対象のイメージ位置までにおいて、文字テンプレートのシーケンスと前記テキスト行イメージのイメージ領域との一致の測定値を示す最大累積評点を計算する第１計算ステップと、
前記処理対象のイメージ位置において計算される前記最大累積評点と、前回の反復により前記処理対象のイメージ位置で求められた先行最大累積評点との間の評点変化値を計算する第２計算ステップと、
前記評点変化値を前回の反復により前記処理対象のイメージ位置で求められた先行評点変化値と比較し、前記テキスト行イメージの少なくとも所定数の連続するイメージ位置に対して前記評点変化値が実質上一定である場合、前記スキップモードスイッチをオンとする比較ステップと、
を含み、
前記第１計算ステップは、推定一致評点を用いて前記最大累積評点を計算するステップを含み、前記各推定一致評点は文字テンプレートと前記テキスト行イメージのイメ−ジ領域との一致の推定測定値を示し、
前記スキップモードスイッチをオンとした状態の処理は、前回の反復により前記処理対象のイメージ位置において計算された先行最大累積評点に前記評点変化値を加えることによって今回の反復における前記最大累積評点を計算する第３計算ステップを含み、
各反復後、前記テキスト行イメージの各イメージ位置に対して前記第１計算ステップまたは前記第３計算ステップにより計算された前記最大累積評点に対応する文字テンプレートのシーケンスを、当該反復における前記テキスト行イメージの推定最適表現形式として生成し、
各反復後、さらに、当該反復における前記推定最適表現方式に含まれる文字テンプレートを示すイメージ位置のそれぞれに対して実際の一致評点を計算する再評点付けオペレーションを実行し、前記実際の一致評点は、後続の反復の前記第１計算ステップにおいて前記最大累積評点を計算するために利用され、
前記複数回の反復のうち１回目の反復では、前記テキスト行イメージの各イメージ位置に対して前記スキップモードスイッチをオフとした状態の処理が行われ、
前記複数回の反復のうち２回目以降の反復では、前記スキップモードスイッチをオンとした状態で、前記テキスト行イメージの各イメージ位置を順に処理対象として前記最大累積評点を求める処理を開始し、今回の反復と前回の反復との間に行われた再評点付けオペレーションにより前記実際の一致評点が計算されたイメージ位置が処理対象となったときに、前記スキップモードスイッチをオフとする、
ことを特徴とする方法。
【請求項２】
請求項１に記載の、プロセッサによって制御されるマシンを作動させテキスト行イメージをデコードする方法において、前記テキスト行イメージは、グラフ構造として表示され、前記テキスト行イメージの連続するイメージ位置であって、前記スキップモードスイッチがオンとされるイメージ位置の総数は前記グラフデータ構造において切断集合を形成することを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、広くは、確率的有限状態ネットワーク、たとえばマルコフソースをもちいるイメージデコーディングおよびイメージ認識技法に関する。より詳しくは、本発明は、確率的有限状態ネットワークを用いる、テキスト行イメージのデコーディングの効率を改善する技法を提供するものである。
【０００２】
【従来の技術】
米国特許第５，３２１，７７３号（以下、’７７３ＤＩＤ特許と呼ぶ）には、ドキュメントイメージデコーディング（以下、ＤＩＤと呼ぶ）として知られるドキュメント認識技法が開示されており、この技法は古典的通信理論を基礎としている。ＤＩＤモデルは、確率的メッセージソース、イメージャ、チャネルおよびデコーダを含む。
【０００３】
メッセージソースおよびイメージャの機能は、結合されて単独の複合イメージソースとされマルコフソースとしてインプリメントされる。マルコフソースは、特定のクラスのドキュメントイメージに発生する空間配置およびイメージ構成要素を正規の文法として記述する確率的有限状態ネットワークである。有限状態ネットワークは、ノードの集合および各ノードに向かう有向遷移の集合を含む。ネットワーク内の任意の先行点及び後続点の２点間の有向遷移は、文字テンプレート、ラベルまたはメッセージ文字列、遷移確率、およびテンプレートの集合幅である水平距離を示す二次元整数ベクトル変位を含む属性の集合と関連している。
【０００４】
テキストイメージをデコードすることは、そのイメージを表現するパスであり、そのイメージを作成した可能性が最も高いパスを、有限状態ネットワークを通じて検索することを含む。デコーディングは、ダイナミックプログラミングオペレーションによって実行され、通常、ビタビ（Ｖｉｔｅｒｂｉ）アルゴリズムとしてインプリメントされる。
【０００５】
デコーディングは、ネットワーク内の遷移のテンプレートが、イメージポイント付近においてデコードされることになっているイメージの領域と一致する確率の計算を含む。テンプレート−イメージ確率は、テンプレート−イメージ一致評点によって表され、この評点は特定のテンプレートとイメージポイントにおけるイメージ領域の一致の測定値を示す。モデルによって定められるイメージの複雑さ（すなわち、遷移の数）および突き合わせるべきテンプレートの数が、計算時間に関する主要因子である。
【０００６】
２つの因子が、デコーディングの複雑さおよび計算時間に影響を及ぼす。第１因子は、水平テキスト行の基準線の検出であり、実際には、イメージ内の各行の画素は、可能性のある水平テキスト行の基準線として評価（デコード）される。
【０００７】
デコーディングの複雑さの第２因子は、テンプレート−イメージ一致評点である。各テンプレートは、テキスト行デコーディング中、イメージ内の水平行の画素の各位置において突き合わされる。実際の基準線の位置が正確に知られていない場合、各テンプレートは、５ヶ所程度の垂直画素位置において突き合わせることもできる。
【０００８】
米国特許第５，５２６，４４４号（以下、‘４４４ＩＣＰ特許と呼ぶ）には、ＤＩＤシステムを用いるデコーディングの計算効率を改善する幾つかの技法が開示されている。
【０００９】
特に、‘４４４ＩＣＰ特許には、反復完成パス（Ｉｔｅｒａｔｅｄ  Ｃｏｍｐｌｅｔｅ  Ｐａｔｈ）（以下、ＩＣＰと呼ぶ）アルゴリズムと呼ばれる動的アルゴリズムが開示されている。このアルゴリズムは、大部分の水平行画素の完全ビタビデコーディングを、その行に関する評点の単純な上限の計算によって置換する。
【００１０】
発明の名称“Ｄｏｃｕｍｅｎｔ  Ｉｍａｇｅ  Ｄｅｃｏｄｉｎｇ  ｕｓｉｎｇＴｅｘｔ  Ｌｉｎｅ  Ｃｏｌｕｍｎ  Ｂａｓｅｄ  Ｈｅｕｒｉｓｔｉｃ  Ｓｃｏｒｉｎｇ”を有する同時出願の特許には、実際のテンプレート−イメージ一致評点の代わりに列基準上限動的評点を最初に計算して用いることによって、個別テキスト行のデコーディング時間を減少させる技法が開示されている。上限動的評点の使用によって、ダイナミックプログラミングオペレーションのためテキスト行のデコーディングを反復することが必要となる。デコーディングを反復後、実際のテンプレート−イメージ一致評点は、その反復に対して最適と推定されるパス上にあると認められるノードの入力側分岐に関して計算（再評点付け）される。このテキスト行のデコーディングは、最適のパス上のノードの入力側分岐に対する全ての動的評点が実際のテンプレート−イメージ一致評点によって置換されるまで、反復される。列基準上限動的評点の使用によって実現される計算効率の一部は、同じテキスト行のデコーディングの反復を追加する必要があることによって相殺される。
【００１１】
【発明が解決しようとする課題】
したがって、テキスト行デコーディング時間の更なる節減を実現するため、個別テキスト行をデコードする場合、ダイナミックプログラミング処理のオペレーションを改善することが望まれる。
【００１２】
【課題を解決するための手段】
本発明は、上限動的評点を用いるテキスト行デコーディングの実験結果および観察によって、誘導される。各デコーディング反復の計算費用のかかる部分は、所定のイメージ位置に関する最大累積パス評点の計算である。
【００１３】
現行のデコーディング反復に入力される評点データの値は、先行推定最適パス上の１つ以上の直前の分岐が再評点付け直後であるノードにおいてのみ、先行する反復期間の評点データ値と異なる。そのパスの後続のノードの位置に対する再評点付けされたノードの影響は、それが発生した行の一部に限定されると予測することは妥当である。最適パスの他のイメージ領域内のノードの位置は、ネットワーク内の分岐の再評点付けがこれらのイメージ領域において発生しない場合、デコーディング反復中は変更することはできない。
【００１４】
この観察は、切断集合（ｃｕｔ  ｓｅｔ）として知られるグラフ理論の特性を利用するものである。切断集合は、分離された２つの部分間の接続のみが必ず切断集合を通って進むような様式によって、グラフの２部分を分離するノードの部分集合である。文字テンプレートの最大集合幅に及ぶノードのシーケンスが、イメージを表すトレリスのデコーディングにおいて切断集合を形成する。以前に再評点付けされた分岐の結果として、現行と先行デコーディング反復の間の累積パス評点の値の変化は、十分な数のイメージ位置に対して一定であると認められた場合、その一定の変化値は、少なくとも次の再評点付けされた分岐に遭遇するまで一定であることが保証され、その点までの全ての後続イメージ位置は、その切断集合に含まれる。
【００１５】
本明細書において開示される改善されたデコーディングオペレーションは、このような局所的変化の可能性を活用するものである。所定のイメージ位置において再評点付けされた分岐に由来する新しい累積パス評点の変化は、文字テンプレートの最大集合幅より大きいイメージ位置のシーケンスに関して同一であると観察されると判断される場合、デコ−ダは、別の再評点付けされた分岐に遭遇するまで、後続のイメージ位置に対する現行のパス評点として、先行累積パス評点に変化量を加えたものを採用するのみである。このことによって、累積パス評点を計算しなければならない、テキスト行上のイメージ位置の数が減少し、その結果、デコーディング過程の反復に起因する追加計算オーバーヘッドが減少する。
【００１６】
この新しい動作モードは、スキップモード（ｓｋｉｐ  ｍｏｄｅ）と呼ばれる。
【００１７】
スキップモードデコーディングオペレーションは、下記の動作特性を有する任意の計算環境において有用である。（ｉ）解決されつつある問題は、ダイナミックプログラミングオペレーションと、トレリス、トレリス類似、またはグラフデータ構造の形態による問題のデータ構造表現との使用に関連し、この場合、ダイナミックプログラミングオペレーションによって、累積評点が出力として生成され、この出力から、グラフまたはトレリスを通るパスを誘導することができる。および（ｉｉ）デコーディングデータ構造内の分岐に標識付される評点は、推定されたまたは変化する評点であり、これらの評点はデコーディング中、時の経過と共に変化する。
【００１８】
【発明の実施の形態】
図１は、本発明によるテキスト行デコーダ２００の入力および出力データ構造を示すブロック図である。イメージソースモデル８００は、単独のテキスト行イメージのクラスの空間配置を、確率的有限状態ネットワークとして表現する。
【００１９】
モデル８００は、文字テンプレートのライブラリ２０を備える。各文字テンプレートデータは、文字のビットマップイメージと、その文字を独特に識別する文字ラベルとを示す。各テンプレートは、テキスト行内における集合の変位を示す集合幅を有する。
【００２０】
テキスト行イメージ１０は、マルコフソース８００によって記述されるドキュメントのクラスのイメージであり、イメージグリフとも呼ばれる文字イメージを含む。本明細書において用いられる用語グリフは、単独のインスタンス、またはたとえば、イメージによって具体化される文字のインスタンスである。
【００２１】
ダイナミックプログラミングデコーディングオペレーション２００によって、テキスト行イメージ１０に関するイメージグリフの表現形式３０が、出力として生成される。デコーディングは、以下に述べる技法によって変形された標準ダイナミックプログラミングオペレーションを用いて、本発明に従って実行される。
【００２２】
ＤＩＤフレームワークにおいて、テキスト行イメージ１０、すなわちデコードすべきイメージは、イメージモデル８００を通るパスによって表現される。イメージモデル８００は、イメージモデルのノードと、イメージ平面の座標とによって索引付けされるデコーディングトレリスとして表現される。デコーディングは、デコーディングトレリスを通る最適パスの検出を含む。ノードは、（状態、位置）対であり、一次元デコーディングトレリスの場合、ノードはｘ位置によって独特に定められる。トレリスによって得られる分岐によって、表現形式出力の文字が決定される。すなわち、表現形式３０は、パスの分岐に関連するテンプレートを識別する文字ラベルから形成される。破壊されたイメージに関する確率分布は、チャネルモデル（図示してない）から誘導され、ある確率をもってあるイメージを予測する。イメージ１０のデコーディングは、イメージ平面の各点において、帰納的に決定される可能性関数の集合の計算を含む。可能性関数は、イメージ１０であるデータの特定の集合について評価される確率分布を示す。各個別ノード計算によって、遷移のテンプレートがイメージ点の付近においてデコードされるべきイメージの領域と一致する確率が計算される。このテンプレート−イメージ確率は、テンプレート−イメージ一致評点によって表され、この評点は、イメージ点において、特定のテンプレートとイメージ領域の一致の測定値を示す。したがって、所定のイメージ位置において所定の文字テンプレートに関するトレリスの分岐は、そのイメージ位置におけるその文字に関するテンプレート−イメージ一致評点によって標識付けされる。テンプレート−イメージ一致評点を用いて各イメージ位置における最大累積パス評点を生成することは、区分様式によって区分の可能性を蓄積する方法である。イメージモデルを表すトレリスをデコードすることに関して、トレリスの分岐を標識付けするテンプレート−イメージ一致評点は、可能性用語である。
【００２３】
帰納的ビタビ手順の最初の段階は、各イメージ位置およびあらゆるノードに通じる各遷移に関して反復するステップと、遷移を通過後、ノードおよびイメージにおいて終了する最適のパスの可能性を計算するステップと、を含む。ビタビデコーダによって、イメージネットワークの各ノードについて、累積ノード評点アレイおよびバックポインタアレイが生成される。ノードに関する評点は、イメージの各位置において、位置合わせされるそのノードに関する数字で表した一致評点を含む。各ノードに関するバックポインタアレイによって、ノードに入る全ての分岐の中で、ノードに通じる可能性の最も高い分岐、すなわち、各イメージ位置において評点を最大とする分岐が識別される。
【００２４】
ビタビ手順は、最適パスのエンドポイントが明白に識別されるまで、順方向で実行される。ビタビの逆方向段階は、最適パスの一部として識別されたノードを経由して逆方向に追跡して実際の最適パスを最後まで追跡することを含む。最適パス上のノードによって、文字の位置が決定される。最適パスに関するソースモデルにおいて、開始ノードから最終ノードまで、各ノード間の遷移に関する文字テンプレートのシーケンスは、連結されてデコードされるイメージのメッセージ、または遷移を形成する。
【００２５】
本発明の変形「スキップモード」ダイナミックプログラミングオペレーションは、デコーディングトレリスにおいて分岐に関して標識付けされるテンプレート−イメージ一致評点が、実際の固定テンプレート−イメージ一致評点とは対照的に、推定評点または変化する評点である場合、どんな状況下においても作動する。本説明によれば、デコーディングトレリスの分岐は、ヒューリスティック評点によって標識付けされる。
【００２６】
ヒューリスティック評点は、イメージおよびテンプレートの列にあるＯＮ状態の前景画素の数に関する情報を示し、実際のテンプレート−イメージ一致評点に関する上限評点である。
【００２７】
図２は、改善されたダイナミックプログラミング発明の主要過程の概略フローチャートであり、オペレーション２０８、２１０、および２８０を示す。完全なダイナミックプログラミングデコーディングの少なくとも１回の反復が、処理ステップ２０８において、ヒューリスティック評点によって標識付けされた分岐を有するデコーディングトレリスを用いて、最初に実行される。最初の反復に続いて、行デコーディング後処理２８０が実行される。オペレーション２１０によって、スキップモード処理を含む行デコーディングの１回の反復が行われる。手順２８０によって、デコーディングの各反復が完了後の処理が取り扱われる。テキスト行デコーディングは、処理ステップ２９６内の条件が満足されたとき、完了する。最終反復において計算直後の推定最適パス、すなわち現行パスと呼ばれるパスが、直前のパスと同一である場合、または現行最適パスに存在すると識別されるデコーディングトレリスのノードに通じるすべての入力側分岐に関して実際のテンプレート−イメージ一致評点を用いる再評点付けが完了した場合、デコーディングは終了する。デコーディングが終了すると、出力表現形式は、処理ステップ２９８において利用可能となる。
【００２８】
オペレーション２１０によって、ノード評点、たとえば、テキスト行イメージの各ｘ位置に対する１つの累積パス評点のアレイ、およびバックポインタアレイが生成される。デコーディングの反復の終了時に、逆方向追跡プロセッサ２８２（図３）は、バックポインタアレイを用いて、イメージネットワーク８００の全域において現行推定最適パスを構成するノードを決定する。メッセージストリング、または表現方式は、このパスから形成される。表現形式は、推定最適パスのノードに通じる分岐上にあるテンプレートに関連する連結された文字ラベルの順序付きシーケンスからなる。推定最適パスのノードのイメージ位置ｘ2は、ＣＮｏｄｅｓと呼ばれるアレイに記憶される。
【００２９】
図３の処理ステップ２８３から２９２までによって表される処理ループにおいて、行デコーディング後処理２８０によって、推定最適パスの各ノードに対する実際のテンプレート−イメージ一致評点を計算する幾つかのオペレーションが実行される。これらのオペレーションは、一括して「最適パスのノードの再評点付け」と呼ばれる。これは、最適パスノードによって、これらのノードの水平イメージ位置およびこれらのノードに直接隣接する水平または垂直イメージ位置においてのみ識別されるテンプレートに関連するデコーディングトレリスの分岐のみに対して実際のテンプレート−イメージ一致評点を生成することに対する短縮専門用語である。ノード位置の近隣について計算される実際のテンプレート−イメージ一致評点の最大値が、そのノードに対するデコーディングトレリスの分岐に配置され、その分岐のヒューリスティック評点を置換する。行デコーディング後の期間のみに実際のテンプレート−イメージ一致評点を生成することは、通常、費用のかからない計算である。再評点付けは、全てのＷテキスト行位置に対してではなく、識別されたノードのテキスト行位置に対してのみ、また全てのノード位置における全てのテンプレートに対してではなく、ノードに通じる遷移のラベルによって識別される文字テンプレートに対してのみ、実行される。各デコーディング反復によって、ノードの入力側分岐に関する実際の評点を有するノードをより多く有する推定最適パスが生成される場合、計算する必要がある実際の評点はより少なくなる。
【００３０】
ＣＮｏｄｅアレイ指標ｎは、処理ステップ２８３において１に設定され、ループ処理が開始される。最初に、処理ステップ２８４において、推定最適パスから導かれる表現方式による文字ラベルによって識別される各文字テンプレートに対して、そのテンプレートに対する実際のテンプレート−イメージ一致評点が、そのノードのイメージ位置において計算される。実際の評点は、イメージの２次元部分とノード位置に配置される２次元（２Ｄ）文字テンプレートイメージの間においてＡＮＤオペレーションを実行し、次に、得られるＯＮ画素を合計することによって、計算される。
【００３１】
処理ステップ２８６および２８８における追加再評点付けタスクは、そのノードにおいて一致すると推定されたテンプレートは垂直または水平に１つまたは２つの画素を取り除いた位置にあるイメージに関してより高い実際の一致評点を実際に生成するという前提に基いている。ノードの周辺のこの領域は、ノードを表すイメージ位置の周辺においてイメージ位置の方形、水平、および垂直近隣領域を形成する。別の実施形態によれば、近隣領域は削除することが可能であり、再評点付けは元のノードのみに限定することができる。
【００３２】
再評点付けタスク２８６において、実際のテンプレート−イメージ評点は、推定パスノード位置として識別されるｘ位置の周辺のテキスト行上のある数のｘ画素位置のそれぞれの幅についても計算される。たとえば、合計で５ヶ所のｘ位置についての再評点付けで十分である。
【００３３】
デコーディングが実行されるテキスト行イメージの基準線は、必ずしも真の基準線ではないので、再評点付けオペレーション２８８によって、各文字テンプレートを突き合わせるための最適の垂直基準線位置の位置決めが支援される。推定最適パスの一部として識別されたあらゆるノードにおいて、そのノードのｘ位置におけるテンプレートは、幾つかの異なる垂直（ｙ）位置においてテキスト行イメージと突き合わされ、実際のテンプレート−イメージ評点が計算される。実際のテンプレート−イメージ評点は、タスク２８６において識別される隣接するｘ画素位置の幅内の各ｘ位置に対するｙ画素位置の各幅についても計算される。図３の再評点付けタスク２８６および２８８において、実際のテンプレート−イメージ評点は、推定パスノード位置として識別されるｘ位置を囲む小さな方形のイメージ位置の各画素位置について計算される。
【００３４】
次に、図３の処理ステップ２８９において、イメージ位置に隣接する方形内の全ての位置に対するテンプレートについて計算された全てのこれらの実際のテンプレート−イメージ一致評点から、最大の評点が選択される。この最大評点は、このノードに対する入力側分岐について使用すべき実際のテンプレート−イメージ一致評点を示す。また、行デコーディング後オペレーション２８０によって、処理ステップ２８９において、そのテンプレート−イメージ位置対に対する評点に関する実際の評点フラグがオンとされ、そのトレリスにはその分岐に関する実際の評点が存在することが示される。行デコーディング後オペレーション２８０は、再評点付け直後のフラグを用いて、この現行デコーディング反復の結果として、実際の評点が計算された直後であるトラックを維持する。その結果、オペレーション２８０の開始時に、全ての再評点付け直後のフラグはオフとされ、最大の実際のテンプレート−イメージ一致評点が選択されるとき、処理ステップ２８９において、その関連する再評点付け直後のフラグはオンとされる。
【００３５】
再評点付け処理の完了後、処理ステップ２９０において、問い合わせが作成され、ＣＮｏｄｅアレイ内の全てのノードが処理されたかが判断される。処理されていない場合、制御は処理ステップ２９２に進み、処理ステップ２９２において、ノードアレイ指標は増分され、処理制御は処理ステップ２８４に進み、次のノードに対する再評点付けが実行される。全てのノードが処理された場合、制御は、処理ステップ２９４に進む。テキスト行上のあらゆるイメージ位置に対する現行推定最適パスおよび現行ノード評点は、ノード位置の先行パス、ＰＮｏｄｅｓ、およびノード評点の先行集合、ＰＳｃｏｒｅｓとして記憶され、この両者は、次のデコーディングの反復のため、オペレーション２１０にアクセスすることができる。
【００３６】
次に、処理制御は、処理ステップ２９６（図３）のテストに進み、デコーディングは終了すべきかまたは継続すべきかを判断する。デコーディングが完了すると、表現方式出力は、プリンティングのため、または他のオペレーションによってさらに処理するため使用することができる。
【００３７】
スキップモード処理とスキップモード処理に関するテストを含むオペレーション２１０の詳細を、図４のフローチャートに示す。オペレーション２１０の出力には、ノード評点およびバックポインタアレイが含まれる。テキスト行イメージのあらゆる位置ｘに対して、そのイメージ位置に通じるすべてのパスの中から最大パス評点を示す累積パス評点が必ず存在する。本発明によって、従来のテキスト行デコーディングオペレーションは変形され、２つの処理モードがテキスト行イメージの位置ｘを処理するために利用可能とされる。第１の処理モードは、完全ダイナミックプログラミングオペレーションを実行して、位置ｘにおける最大累積パス評点を計算する。第２処理モードは、スキップモードを実行して、この場合、ｘ位置における累積パス評点は、位置ｘにおける先行パス評点に、パス評点変化値を加えたものである。
【００３８】
スキップモード処理は、その後のデコーディング反復の間、所定のイメージ位置に対する累積パス評点は、その位置が先行する反復において再評点付け直後である入力側分岐を有するノードの位置である場合、またはその位置が前述したノードに続く位置である場合のみ、その位置に対する先行反復の累積パス評点から変化するという観察に基づく。さらに、先行の推定パス上のノードの入力側分岐が再評点付け直後である場合であっても、この領域のテキスト行のパスは、この反復において、パスが先行の反復において沿った同じノードに沿って継続されることは事実である。すなわち、ノードの再評点付けによって生成される累積パス評点の変化は、そのテキスト行上のイメージ位置の後続の一部の部分に対する累積パス評点のみに伝搬する。テキスト行の一部の部分に対するデコーディング反復中にこの条件を検出できることは、各イメージ位置において完全な帰納的ダイナミックプログラミングを実行する必要はないことを意味する。むしろ、スキップモードの条件が満足された場合、現行累積パス評点の計算は、他の再評点付け直後の分岐が存在しない場合、先行評点に対する評点変化を、再評点付け分岐後のこれらの後続のイメージ位置に対して伝搬することによって実行することができる。
【００３９】
オペレション２１０は、処理ステップ２１２における初期化タスクによって開始される。より詳しくは、データ変数ΔＳｃｏｒｅ１およびΔＳｃｏｒｅ２は、ゼロに設定される。ΔＳｃｏｒｅ２は、テキスト行のデコーディング中にオペレーション２１０が追跡する累積パス評点に関する変化値を含む。ΔＳｃｏｒｅ１は、処理中の現行イメージ位置における累積パス評点に関する変化値を含む。さらに、ＳＫＩＰＭＯＤＥと呼ばれる処理スイッチはオンに設定され、デコーダは、スキップモード処理によって開始されることが望ましいことを示す。これによって、デコーディングテレリス内に再評点付け分岐が存在しない場合、テキスト行の開始部分の完全デコーディングはスキップすることが可能となる。処理ステップ２１４および２３６によって、ループは、テキスト行上のあらゆるイメージ位置ｘを処理するように制御される。制御は、テキスト行の終了時に、行デコーディング後オペレーション２８０に進む。
【００４０】
最初に、ＳＫＩＰＭＯＤＥフラグをテストして、それがオンであるかを確認する。オンである場合、制御は、処理ステップ２２０のテストに進む。オンでない場合、処理モードは完全デコーディングモードであり、制御は、処理ステップ２３０に進む。テスト２２０は、行の各イメージ位置ｘにおいて、オンとなっており位置ｘにおいてテレリスの入力側分岐は再評点付け直後であることを示す関連する再評点付け直後のフラグを有するノードが、この位置に存在するかを、検査して判断する。存在しない場合、ＳＫＩＰＭＯＤＥはオンであると事前に判定されたので、それ故、位置ｘにおいて入力側の再評点付け直後の分岐は存在せず、スキップモード処理は、このイメージ位置に対して有効である。制御は処理ステップ２３４に進み、ここにおいて、現行評点、先行評点であるべき位置ｘiに対するＣＳｃｏｒｅi、ＰＳｃｏｒｅiプラスΔＳｃｏｒｅ２に記憶される変化値を計算する。処理ステップ２３０において、累積パス評点の完全計算を実行することは、このイメージ位置の場合、回避される。行の開始時において、ＳＫＩＰＭＯＤＥはオンであり、再評点付け直後の分岐が検出されない限り、デコーダは、現行評点、先行評点であるべき位置ｘiに対するＣＳｃｏｒｅi、ＰＳｃｏｒｅiプラスΔＳｃｏｒｅ２に記憶されるゼロ変化値を計算する。次に、処理制御は、処理ステップ２３６の行テストの終了に進み、さらにループの開始に戻り、次のイメージ位置に進む。
【００４１】
テスト２２０によって、位置ｘiはデコーディングトレリス内にそれに関連する再評点付け直後の入力側分岐を有することが検出される場合、制御は、ＳＫＩＰＭＯＤＥがオフである処理ステップ２２２に進む。次に、制御は処理ステップ２３０に進み、ここにおいて、デコーダは、今度は、完全デコーディングモードになる。処理ステップ２３０において、帰納的ダイナミックプログラミングオペレーションによって、現行イメージ位置に対する累積パス評点が計算される。累積パス評点の実際の計算の記述は、‘４４４ＩＣＰ特許の第７〜９欄および同特許の添付図２０〜２１の記述に認めることができる。
【００４２】
次に、制御は、処理ステップ２４２、２５０、２５２、２５４、２５６、および２５８の一連の関数に進み、スキップモード処理に対する基準は、ＳＫＩＰＭＯＤＥフラグがオンとされるような、位置ｘi処理の結果として満足されるかをテストする。完全ダイナミックプログラミングデコーディングは、ＳＫＩＰＭＯＤＥがオフである限り、継続される。
【００４３】
デコーディングオペレーションがスキップモードである場合、ｘiにおける現行累積パス評点は、ｘiにおける先行累積パス評点プラスΔＳｃｏｒｅ２に記憶される変化値であると計算されることを想起されたい。しかし、累積パス評点変化の伝搬は、変化量が、テンプレートライブラリにある文字テンプレートの最大集合幅より大きい一連のイメージ位置に対して事実上一定である場合のみ発生することができる。このルールによって、すべての先行ノードに対して、後続ノードの累積パス評点は同じ量だけ変化し、その結果、たとえどの入力側分岐が選択されても、後続ノードに対する累積パス評点も必ずその量だけ変化することが保証される。スキップモードオペレーションに関してテストする処理によって、評点値変化が計算され、如何に多数のイメージ位置に対して、評点値変化が同じであるかが追跡され、必要条件が満足される場合、ＳＫＩＰＭＯＤＥスイッチがオンとされる。評点値変化およびＩｃｏｕｎｔ、すなわちイメージ位置の数を追跡するカウンタは、評点値変化が先行する評点値変化と異なることが検出される場合、リセットされる。
【００４４】
オペレーション２１０によって、処理ステップ２４２において、位置ｘiにおいて現行（Ｃｓｃｏｒｅi）と先行累積パス評点（Ｐｓｃｏｒｅi）の間において累積パス評点の現行変化値ΔＳｃｏｒｅ１が計算される。次に、処理ステップ２５０においてテストが実行され、現行イメージ位置に対する評点値変化ΔＳｃｏｒｅ１が、ΔＳｃｏｒｅ２に記憶される、追跡中の評点値変化に等しいかが判断される。評点変化値が等しい場合、処理ステップ２５２においてカウンタは増分され、またテスト２５４によって検査して、カウンタが最大文字テンプレート集合幅のイメージ位置の数を越えるか判断される。テスト２５４が否定的である場合、処理制御は、ＳＫＩＰＭＯＤＥスイッチを変更することなく、行テストの終了に進む。テスト２５４が肯定的である場合、同じ一定の変化値を有するイメージ位置の必要数が計数され、ＳＫＩＰＭＯＤＥがオンとされる。次に、処理制御は、行テストの終了に進む。  テスト２５０が失敗した場合、現行累積パス評点に対して計算される評点変化値は、追跡中の評点変化値とは異なる。これは、現行デコーディング反復と先行デコーディング反復の間の評点変化値は、一定に保持されないことを示し、このイメージ位置はスキップモードテストに有用であるには適しないことを示す信号である。次に、カウンタは、処理ステップ２５８において、ゼロにリセットされ、ΔＳｃｏｒｅ１の新しい変化値が、今度は、今後の処理において追跡すべき変化値であり、したがって、ΔＳｃｏｒｅ２に記憶される。次に、処理制御は、処理ステップ２３６の行テストの終了に進む。
【００４５】
スキップモード処理をオンとするため、累積パス評点の変化は、ある程度の数のイメージ位置に対して一定の固定された量であることを必要とすることは、厳密に言えば必要でないある作動環境が存在する場合がある。累積パス評点の変化は、「事実上一定」とすることができる。すなわち、変化は、小さな範囲内、たとえば累積パス評点合計の非常に小さい割合とすることができる。たとえば、累積パス評点が１００，０００範囲である場合、累積パス評点の変化は、一定の変化から１０以下だけ逸脱する場合があるが、依然としてスキップモード処理をオンとすべきか判定するためには許容される。したがって、処理ステップ２５０のテストは、異なる表現となる。この代替方法の実施形態は、注意して用いるべきであり、最終のデコーディング出力の正確さが損なわれないことを、実験テストによって確認する必要がある。
【００４６】
ＳＫＩＰＭＯＤＥがオンとされると、デコーディングトレリスにおいて入力側の再評点付け直後の分岐と遭遇しない限り、評点変化値は現行累積パス評点に伝搬することができることが、オペレーション２１０によって明らかになる。評点変化値ΔＳｃｏｒｅ１が追跡中の値ΔＳｃｏｒｅ２と同じでないと、直ぐに、カウンタはゼロにリセットされ、スキップモード処理に対する追跡は次のイメージ位置と同時に再度開始される。このイメージ位置は、再評点付け直後の入力側分岐を有するノードであるので、ＳＫＩＰＭＤＥスイッチがオフとされている処理ステップ２２２において、カウンタＩｃｏｕｎｔをゼロにリセットすることも可能であるが、この場合は必要とされない。カウンタを制御するために重要なテストは、現行イメージ位置に対して計算された直後の現行評点変化値は、追跡中の評点変化値と同じであるかである。再評点付け直後の分岐が存在する場合、新しい評点変化値は、以前の変化値と異なる可能性が最も高いが、異ならない場合もある。新しい評点変化値が、再評点付け直後の分岐であるにも関わらず以前の変化値と同じである場合、これは、累積パス評点に対する、デコーディングトレリスの以前の再評点付け直後の分岐の影響は、トレリスの最も最近の再評点付け直後の分岐を通じて継続中であり、その結果、スキップモード処理状態に対して引き続き有用であることができることを示す。処理ステップ２５８においてカウンタをリセットするのみで、十分である。
【００４７】
前述した形式のマルコフソースを用いるテキスト行ドキュメントイメージデコーディングは、テキスト行の基準線を位置決めする従来のイメージ処理方法を用いてインプリメントすることができる。入力イメージがデスキュー（ｄｅｓｋｅｗ）され、テキストブロックおよびテキスト行が識別された後、テキスト行基準線は、テキスト行の水平画素投射を用いて識別することができる。
【００４８】
本発明は、図５のマシン１００の一般の構成要素、特性、および構成を有する任意のマシンにおいて用いることができる。マシン１００は、本発明を実行することを目的として構成して最適化することが可能であり、あるいはマシンに記憶されるコンピュータプログラムによって選択的に作動または再構成される汎用コンピュータを構成することができる。マシン１００の物理的構成要素が結合される実際の様式には、一部またはすべての構成要素間のハードウェア物理的結合、ならびに有線または無線通信機能による結合、たとえばリモートまたはローカル通信ネットワークによる結合および赤外線結合および無線結合が含まれる。
【００４９】
マシン１００は、デコーディングトレリスの分岐に関する推定評点を用いて反復テキスト行デコーディングを実行するテキスト行イメージデコーディングオペレーション２００（図２）を実行するように構成することができる。入力イメージは、信号ソース１５８から供給され、信号ソース１５８は、イメージ取り込み装置、たとえばイメージスキャナまたはディジタルカメラ、メモリデバイス、通信チャネル、データバス、オペレーションを実行する他のプロセッサ、またはビットマップイメージ信号の任意の他の適切なソースとすることができる。信号ソース１５８によって供給される入力イメージは、入力回路網１５６を介してプロセッサ１４０に送られ、またデータメモリ１１４に記憶することができる。マシン１００は、イメージを表示できる従来のディスプレイ装置（図示してない）または印刷装置を備えることができるが、備える必要はない。
【００５０】
プロセッサ１４０は、プログラムメモリ１１０にアクセスすることによって作動され、指令を検索し、次いで、実行する。マシン１００が、図２の反復テキスト行デコーディングオペレーション２００を実行し入力テキスト行イメージから表現形式を生成するように構成される場合、プログラムメモリ１１０は、図２のオペレーション２０８、２１０、および２８０を実行するデコーディング指令を含む。たとえば、プログラムメモリ１１０は、スキップモード処理を実行するサブルーチン２１０を含む。
【００５１】
指令を実行中、プロセッサ１４０は、データメモリ１１４にアクセスしてそのオペレーションを実行するため必要なデータを獲得または記憶することができる。たとえば、プロセッサ１４０は、反復テキスト行デコーディングオペレーション中に先行デコーディングパスおよび評点アレイ７０をデータメモリ１１４に記憶する。
【００５２】
図５には、マシン１００において使用することができるソフトウェアプロダクト１６０も示されている。ソフトウェア１６０は、記憶媒体アクセス回路網１５０を介してアクセスすることができるデータ記憶媒体１７０を含む。ソフトウェアプロダクト１６０は、データ記憶媒体１７０およびプロダクトを記述する適切な文書を含むソフトウェアパッケージの形態で、市場において消費者に提供される。
【００５３】
記憶媒体アクセス回路網１５０は、データ記憶媒体１７０がリモート配置記憶装置、たとえばサーバの一部として記憶される場合、データ記憶媒体１７０の指令データにアクセスするため、通信アクセスソフトウェアおよび回路網を含むことができる。ソフトウェアプロダクト１６０は、本発明の方法を実行するための指令データを表示するデータストリームの形態で、市場においてまたは他の方法によって使用者に提供することが可能であり、このデータストリームは、通信機能によってリモート配置記憶装置から利用者に伝送することができる。データ記憶媒体１７０は、図２のオペレーション２００を実行するための指令を記憶する。
【００５４】
この指令データは、反復テキスト行デコーディングを実行する必要がある場合に実行するため、プロセッサ１４０に提供される。記憶データは、スキップモード処理指令１６４を含む。スキップモード処理指令１６４がプロセッサ１４０に伝送され、プロセッサ１４０が指令を実行する場合、図４のフローチャートに示すように、マシンが作動され、スキップモードをオンとすべきかを判定するためオペレーションが実行される。
【図面の簡単な説明】
【図１】  本発明によるテキストイメージ行デコーダの入力および出力データ構造のブロック図である。
【図２】  イメージテキスト行のデコーディングのためのダイナミックプログラミングオペレーションの一般機能を示すフローチャートである。
【図３】  ダイナミックプログラミングオペレーションのデコーディング後の機能の詳細を図解するフローチャートである。
【図４】  イメージテキスト行のデコーディングの１回反復中のプロセスフローの詳細を示すフローチャートであり、スキップモード処理を示す図である。
【図５】  本発明を用いることができる適切に形成されたマシンを示す簡単なブロック図であり、さらに本発明によるソフトウェアプロダクトおよびソフトウェアプロダクトとマシンの併用を示す図である。
【符号の説明】
１０  テキスト行イメージ、２０  文字テンプレートライブラリ、３０  テキスト行表現形式、７０  評点アレイ、１００  マシン、１１０  プログラムメモリ、１１４  データメモリ、１５０  記憶媒体アクセス回路網、１５６  入力回路網、１５８  信号ソース、１６０  ソフトウェアプロダクト、１６４  スキップモード処理指令、１７０  データ記憶媒体、２００  テキスト行デコーダ、２８２  逆方向追跡プロセッサ、８００  イメージソースモデル。
【図１】
0004624592.tif 000002
【図２】
0004624592.tif 000003
【図３】
0004624592.tif 000004
【図４】
0004624592.tif 000005
【図５】
0004624592.tif 000006