(57)【特許請求の範囲】
【請求項１】
プロセッサ制御型マシンを用いてテキスト行画像を復号する方法であって、前記マシンはプロセッサと、データを記憶するメモリ装置とを含み、前記メモリ装置に記憶されているデータは、前記プロセッサが前記マシンを操作するために実行する命令データを含み、前記プロセッサは、前記メモリ装置に記憶されている命令データにアクセスしそれを実行するために前記メモリ装置に接続されているマシンを用いた復号方法において、
（ａ）それぞれが文字記号を示す複数の画像グリフを含むビットマップ画像領域を示す入力テキスト行画像を受け取るステップと、
（ｂ）前記マシンの前記メモリ装置に記憶されている複数の文字テンプレート及び文字ラベルを取得するステップであって、前記各文字テンプレートは文字記号の二次元ビットマップ画像を示すとともに、前記各文字テンプレート、当該文字テンプレートによって表される文字記号を識別するための文字ラベルに対応づけられているところのステップと、
（ｃ）入力テキスト行画像の画像部分の列内の画像前景画素の画素カウント値を用いて一次元画像アナログデータ構造を作成するステップと、
（ｄ）複数の文字テンプレートのそれぞれの文字テンプレートの列内のテンプレート前景画素の画素カウント値を用いて複数の一次元テンプレートアナログデータ構造を作成するステップと、
（ｅ）前記一次元画像アナログデータ構造と前記複数の一次元テンプレートアナログデータ構造とを用いて複数のテンプレート画像発見的スコアを算出するステップであって、これら各テンプレート画像発見的スコアのそれぞれが、前記複数の文字テンプレートのうちの１つと前記入力テキスト行画像の画像部分の二次元領域との一致度の推定値を示すところのステップと、
（ｆ）複数の節と、前記入力テキスト行画像内の文字記号群の予測される空間配置のモデルを示すそれら各節間の遷移と、を含む確率的有限状態ネットワークを示す復号トレリス・データ構造を使用して動的計画法演算を実行するステップであって、前記動的計画法演算では、前記複数の文字テンプレートの各々と前記入力テキスト行画像の画像部分の二次元領域との一致度を表す複数の実テンプレート画像一致スコアの代わりに前記複数のテンプレート画像発見的スコアを用いて前記入力テキスト行画像を復号し、その中に含まれる画像グリフによって表される文字記号の文字ラベルを生成するところのステップと、
を含む方法。
【請求項２】
前記複数のテンプレートアナログデータ構造を作成するステップ（ｄ）が、前記文字テンプレート内の各列ごとのテキスト列前景画素のカウント値を示す一次元テンプレート画素カウント・データ構造を、前記各文字テンプレートごとに作成するステップを含み、
前記一次元画像アナログデータ構造を作成するステップ（ｃ）が、前記画像部分内のそれぞれの列内の画像列前景画素のカウント値を含む１Ｄ画像画素カウント・データ構造を作成するステップを含み、
前記複数のテンプレート画像発見的スコアのそれぞれを算出するステップ（ｅ）が、各々が前記文字テンプレートの１つの列内のテンプレート列前景画素のカウント値と、前記画像部分の１つの列内の画像列前景画素のカウント値と、の最小値であるところの複数の最小画素カウント値の和を算出するステップを含む、
請求項１に記載の方法。
【請求項３】
各文字テンプレートが少なくとも１つの前景テンプレート・レベルおよび背景テンプレート・レベルを含み、各前景テンプレート・レベルが、複数の前景画素を含むとともに、当該前景テンプレート・レベルに関連するテンプレート・レベル重み付け因子を示し、
前記複数の一次元テンプレートアナログ構造のそれぞれが、前記文字テンプレートの各前景テンプレート・レベルごとに、そのレベルに関連付けされたテンプレート・レベル重み付け因子によって重み付けされたそれぞれの列ごとの前景画素テンプレート・レベル列カウント値を示す情報を含み、
前記一次元画像アナログデータ構造が、前記画像部分のそれぞれの列内の画像前景画素のカウント値群を示す一次元画像画素カウント・データ構造であり、
前記ステップ（ｅ）にて前記複数のテンプレート画像発見的スコアのそれぞれを算出する際に、前記一次元画像画素カウント・データ構造および一次元テンプレートアナログデータ構造を使用して複数の列画素カウント値の和を算出する、
請求項１に記載の方法。
【請求項４】
請求項１に記載の方法であって、
前記ステップ（ｆ）は、
前記復号トレリス・データ構造の各遷移に対して、当該遷移に関連する文字記号に応じて、前記文字テンプレートと前記入力テキスト行画像の画像部分の二次元領域との一致度を表す実テンプレート画像一致スコアの代わりに、当該文字テンプレートについてのテンプレート画像発見的スコアを割り当てるステップと、
動的計画法演算とその後に続く再スコアリング演算との反復シーケンスを、停止条件が満たされるまで実行するステップであって、前記動的計画法演算により、遷移に割り当てられた前記テンプレート画像発見的スコアを用いて前記復号トレリス・データ構造によって節および遷移の完全な道が作成され、前記再スコアリング演算により、前記テンプレート画像発見的スコアを有する前記完全な道内の各節に実テンプレート画像一致スコアが計算されて割り当てられ、前記復号トレリス・データ構造が、動的計画法演算の後続の反復で利用できる前記実テンプレート画像一致スコアを有するようになされる、ところのステップと、
を含む、方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全般的には、マルコフ情報源などの確率的有限状態ネットワークを使用する画像復号認識技法に関する。特に、本発明は、テキスト行画像を復号する際にダイナミック・プログラミング（動的計画法）操作で使用できる発見的（ヒューリスティック）スコアを作成する技法を提供する。
【０００２】
【従来の技術】
米国特許第５３２１７７３号は、従来の通信理論に基づく文書画像復号（以下、ＤＩＤと略す。ＤＩＤは、Document Image Decodingの略）と呼ばれる文書認識技法を開示している。ＤＩＤモデルは、確率的メッセージ情報源、イメージャ、チャネル、およびデコーダを含む。確率的メッセージ情報源は、従来の確率分布に従って１組の候補文字列から有限文字列Ｍを選択する。イメージャは、メッセージを理想的なバイナリ画像Ｑに変換する。チャネル・モデルは、スキュー（斜め歪み）、ブラー（ぼけ）、付加的ノイズ（additive noise）など、印刷および走査による歪みを導入することによって、理想画像を観測画像Ｚにマッピングする。最後に、デコーダは、観測画像Ｚを受信し、ア・ポステオリ（後験的）な（ＭＡＰ）決定基準に従って最初のメッセージの推定値Ｍ＾（Ｍの上に“＾”（ハット）が乗ったものと解されたい。文字コードの制限上、このように表記する）を作成する。最初のメッセージの推定値Ｍ＾は、観測されるメッセージＺのトランスクリプション（転写）と呼ばれることが多い。
【０００３】
メッセージ情報源およびイメージャの機能が組み合わされることで、マルコフ情報源として実現される単一の合成情報源となる。マルコフ情報源とは、正規文法として特定のクラスの文書画像に生じる二次元（２Ｄ）空間レイアウト（配置）および画像構成要素群の全体を記述する確率論的有限状態オートマトンである。一般的なマルコフ情報源モデルは、１組の節（ノード）と、各節への１組の有向遷移とを含む有限状態ネットワークを備える。２つの顕著な節はそれぞれ、初期状態および最終状態を示す。画像はネットワーク内を通る道（パス）として表わされる。ネットワーク内の任意の先行要素状態と後続要素状態との間の有向遷移は、１組の属性に関連付けされている。これら属性の組には、遷移確率と、英語の記号または文字を識別するためのメッセージ文字列と、ページ画像で使用されるフォントで表された文字テンプレートと、道が次に取り出す画像内の（ｘ，ｙ）位置を示すベクトル変位を含む。このベクトル変位は、（ｗt，０）とラベル付けされる。変位（ｗt，０）は、テンプレートの「設定幅」である水平距離ｗを示す。テンプレートの設定幅は、この遷移に関連するテンプレートが画像内で占有するテキスト行上の水平（ｘ方向）距離を指定する。
【０００４】
米国特許第５３２１７７３号は、観測画像の復号処理において、初期状態から最終状態へと、モデルの節および画像平面の座標によってインデックスが付された三次元（３Ｄ）復号トレリス（菱形）・データ構造を通して最良の（ＭＡＰ）道を見つけることを開示している。復号では、二次元形式のビタビ（ダイナミック・プログラミング：動的計画法）アルゴリズムを使用して、画像平面の各点で、再帰的に定義された１組の尤度関数が算出される。ビタビ手順の前進フェーズでは、画像内の各画素位置ごとに、各文字テンプレートを印刷することで得られる道群の中から、すでに算出されているすべての位置に到着するための最も可能性の高い道群を使用することによって、その位置に到着する可能性の最も高い道が識別される。
【０００５】
最良の道の尤度を算出する場合、ある確率を有するある画像を予測するチャネル・モデルから導かれた確率分布が使用される。観測画像Ｚを復号する場合、画像平面の各点で、再帰的に定義された１組の尤度関数が算出される。各々の節の計算では、遷移のテンプレートが、画像点の近傍で、復号すべき画像の領域に対応している確率が算出される。このテンプレート画像確率は、画像点での特定のテンプレートと画像領域との一致（整合性）の度合いを示すテンプレート画像一致スコアによって表される。画像モデルを表す復号トレリスでは、テンプレート画像一致スコアはトレリス内の枝をラベル付けする。
【０００６】
最良の道上のソース・モデル内の開始節から終了節までの各節間の遷移に関連する文字テンプレートの系列は、復号画像のメッセージまたはトランスクリプションを形成するように連結される。
【０００７】
モデルによって定義される画像のサイズおよび複雑さ（すなわち、遷移の数）と、マッチング処理すべきテンプレートの数は計算時間の主要な因子である。
【０００８】
計算時間に影響を与える重要な因子は実テンプレート画像スコアの計算である。ここで、各テンプレートは、当該画像中の各画像位置に整合している。
【０００９】
復号効率を改善する必要があることを認識した米国特許第５５２６４４４号（以下、ＩＣＰ特許第５５２６４４４号と呼ぶ）は、各テキスト行を復号するのに必要な時間を削減する繰り返し完全パス（Ｉｔｅｒａｔｅｄ  ＣｏｍｐｌｅｔｅＰａｔｈ：以下、ＩＣＰと略す）と呼ばれる発見的アルゴリズムを開示する。
復号時には、ＩＣＰによって、各節への削減された１組の遷移群のみに対して水平モデルが実行される（すなわち、実テンプレート画像一致スコアが算出される）。ここで、各節への削減された遷移の数は、その節へのすべての可能な遷移の数よりもかなり小さい。
【００１０】
ＩＣＰは、画素の水平行の大部分の全ビタビ復号を、その行のスコアの単純上界の計算で置き換える。この上界スコアは発見的関数から導かれる。したがって、水平テキスト行が生じる可能性があることを垂直モデルが示す画像の各領域ごとに、各行がテキスト・ベースラインであるかのようにこの領域内の各画素行に対して全ビタビ復号を実行するのではなく、まず、各水平行ごとに発見的スコアを導く。
【００１１】
【発明が解決しようとする課題】
ＩＣＰアルゴリズムは全体的な復号時間を顕著に改善したが、ＤＩＤ法を使用した単一列（単一コラム）のテキストだけの単一のページの文書認識は依然として商業的に実際的なものではなかった。復号時間は、発見的スコアの代わりに実スコアが算出されるときに、個々の水平テキスト行に対して全ビタビ復号を実行することに費やされる。ＩＣＰ特許第５５２６４４４号で開示された技術的進歩によって実現される改良は、顕著なものであるが、個々のテキスト行の効率的な復号に対処するものではなかった。個々のテキスト行の復号時間をさらに短縮することが望ましい。
【００１２】
【課題を解決するための手段】
本発明の技法は、実スコアよりも計算するのが簡単であると共に復号計算において実スコアを十分正確に表す発見的スコアを使用することで、テキスト行の全ビタビ復号中に実テンプレート画像一致スコアを算出することを不要にすることができるという観測に基づくものである。
【００１３】
本発明は、列画素カウントに基づく新しい上界発見的テンプレート画像一致スコアを算出し、画像情報源としての確率的有限状態ネットワークと、復号を実行するためのビタビ手順などの動的計画法（ダイナミック・プログラミング）演算とを使用する任意の全ページ・デコーダまたは全ライン・デコーダでのテキスト行の復号時に、この新しいヒューリスティックを使用する技法を導入する。
【００１４】
本発明のスコアリング・ヒューリステッィクには２つの重要な利点がある。発見的（ヒューリスティック）列ベースのスコアリング（スコア付け演算）により、文書画像モデルを表す確率的有限状態ネットワーク内の行内節の真の上界スコアが作成され、これにより行復号時にこの発見的スコアを使用することにより、算出する必要のある実テンプレート画像一致スコアの数を、行復号の精度を犠牲にすることなく減らすことができる。
【００１５】
また、この発見的（ヒューリスティック）スコアを使用すると、実テンプレート画像スコアの二次元計算は主として、より簡単な、この発見的スコアの一次元計算になる。列ベースの発見的スコアのより簡単であるが正確な計算により、従来の復号方法が必要とする、計算コストのかかる非常に多数の実テンプレート画像スコアがこの発見的スコアで置き換えられるので、計算効率が顕著に向上する。列ベースの発見的スコアは、文字テンプレートの列内のＯＮ画像および画像の列内のＯＮ画像の数に関する情報を表す一次元データ構造を使用して算出される。
【００１６】
【発明の実施の形態】
この実施の形態の技法は、ある定義を考慮したときに最も良く理解される。すなわち、「グリフ」という用語は、本明細書では、画像内に実現される文字の単一のインスタンス、すなわち例を指す。
【００１７】
この実施の形態では、文字テンプレート・データ構造のライブラリが使用される。テンプレート２１（図２）などの各テンプレート・データ構造は、文字のビットマップ画像を示す。文字には、その文字を一意に識別するための文字ラベルが対応づけられている。
【００１８】
テンプレートは、寸法ｍ×ｎの画素群を有し、さらに、テンプレート２１ではクロスバー（十字形）によって示された原点と、文字の設定幅ｗとを有する。各テンプレートのテンプレート原点は、各テンプレート内の同じ位置に指定されている。図２では文字テンプレートが２Ｄ画素アレイとして示されているが、これはテンプレートを表すことのできるデータ構造の一つのタイプである。テンプレートは、垂直ストローク、ジョイン（join：接合部）、アセンダ（英文組版で“ｘ”より上に伸びた部分）、ディセンダ（英文組版でベースラインより下に伸びた部分）、湾曲部などのようなビットマップ文字の各断片を連結することによって作成するか、あるいは完全な文字テンプレートを表す明示的な２Ｄ画素アレイを出力として作成する形式モデルによって表すこともできる。
【００１９】
ビットマップ文字テンプレートの「サポート」または「前景」は、テンプレートが背景と異なる１組の画素位置群である。白い背景上に黒いテキストを含む文書では、テンプレート・サポートは１組の黒い（「ＯＮ」）テンプレート画素群である。文字テンプレートは、黒以外の色の前景画素を有するテンプレートとして定義することもでき、あるいは黒い背景上に白いテキストを示す「反転ビデオ」テンプレートであってもよい。
【００２０】
テンプレートのサポート領域および背景領域は、いくつかの異なるレベルに分離し、それぞれの画像発生確率を割り当てることができる。サポート領域および背景領域が２つの異なるレベル（１つが黒い背景画素のレベル、もう１つが白い背景画素のレベル）であるに分離されるテンプレートを、本明細書では「バイレベル（bi-level）」テンプレートと呼ぶ。このテンプレートは、最大で２つの画素レベルを示す。バイレベル・テンプレートは、いくつかの黒い前景画素に関してそれぞれの異なる発生確率を示す、２つ以上の黒前景画素レベルを含むマルチレベル・テンプレートと区別することができる。
【００２１】
本発明では、発見的スコアを算出するために特殊なデータ構造、すなわち、上界発見的スコアを効率的に算出することを可能にする文字テンプレート・データ構造および画像テキスト行データ構造から導かれる、より簡単な一次元サロゲート（代用物）が作成される。このようなサロゲート・データ構造は「テンプレート・アナログ・データ」構造および「画像アナログデータ」構造と呼ばれ、各データ構造は、それぞれの情報源データ構造に存在する前景列画素カウント値に関する情報を示す。
【００２２】
図１の演算２００によって、テンプレート・ライブラリ２０内の各バイレベル・テンプレートまたは標準テンプレートごとに１組の一次元（１Ｄ）１×ｍテンプレート列アレイ（配列）群４０が作成される。テンプレート列アレイ内の各データ項目は、テンプレート内の１列の画素に対応し、そのテンプレート画素列内のＯＮ画素の数を示す。図２は、テンプレート・ライブラリ内のテンプレート２１、２２、２３、および２４のテンプレート列アレイ群４０の作成を概略的に示している。この例では、アレイ群４０は、個々のテンプレート２１〜２４にそれぞれ対応するテンプレート列アレイ４２，４４，４６，４８を含んでいる。テンプレート列アレイ群４０を作成するプロセスの擬似コードは以下のとおりである。
【００２３】
0004624593.tif 000002
【００２４】
演算３００では、観測画像Ｚと呼ばれる、復号すべき画像内の幅Ｗの画像領域を入力として使用して、１×Ｗ画像テキスト行列アレイ６０が作成される。図３は、入力画像の画像領域５０に関する画像テキスト行列アレイ６０の作成を概略的に示している。画像テキスト行列アレイ６０は、以下では画像アレイ６０と呼ばれ、テキストのベースライン上にあるか、あるいはその近傍にあるとみなされる画像Ｚ内のある水平画素行ｙに対して作成される。画像アレイ６０内の各データ項目は、Ｚ内の画像幅分の画像領域の中の画素列に対応し、その画素列内のＯＮ画素の数を示す。画像領域５０は寸法ｎ×Ｗを有し、この場合、ｎはテンプレート・ライブラリ内のテンプレートの高さを示す。画像アレイ６０を作成するプロセスの擬コードは以下のとおりである。
【００２５】
0004624593.tif 000003
【００２６】
復号は、テンプレート列アレイ４０および画像アレイ６０を使用して作成された発見的スコアを用いて開始し、実テンプレート画像一致スコアは必要に応じて算出される。また、発見的スコアは、画像ベースラインの周りにテンプレートを垂直に位置決めした場合のいかなる場合にも有効である。
【００２７】
発見的列ベース・スコアリングを使用したテキスト行の復号は、実テンプレート画像一致スコアではなく発見的列ベース・スコアを使用してテキスト行を通る最良の道を識別することによって、ビタビ復号手順を実行することから成る。ビタビ・デコーダは、テンプレート・ライブラリ内のすべてのテンプレートに画素位置ｘiで観測画像との最良の一致を示す水平テキスト行内の各画素位置ｘiごとのスコアを必要とする。列ベースの発見的スコアは、テキスト行復号が開始される前に算出される。図１の演算４００では、画像アレイ６０および１組のテンプレート列アレイ群４０を入力として使用して列ベースの発見的スコア７０が作成される。発見的スコア・アレイ７０はｋ×ｗのアレイであり、この場合、ｋは情報源モデル内のテンプレートの総数であり、ｗは、復号中の画像テキスト行またはその一部の幅である。列ベースの発見的スコアは、画像テキスト行のあらゆる画像位置ｉで、あらゆるテンプレートについて算出され、すべてのスコアは、動的計画法（ダイナミック・プログラミング）復号演算で使用できるように記憶される。
【００２８】
図４は、発見的スコア７０がどのように作成されるかを概略的に示している。
画像アレイ６０内の各アレイ要素ＩＣiは、テキスト行画像内の画素位置ｘiに関する列ベースの画素カウントを表す。１組のｋ個のテンプレート列アレイ群４０内の各テンプレート列アレイ４５は、その各エントリ４３が当該テンプレート内のその列に関する列ベースの画素カウントを表す１×ｍアレイである。演算４００では、復号中のテキスト行画像内の各画素位置での各テンプレートごとに１つのスコア、合計ｋ×ｗ個のスコアが作成される。図４は、ｋ×ｗ発見的スコア・アレイ７０に記憶されたこの１組の発見的スコアを示している。テキスト行画像内の画素位置ｘiの発見的スコアを示すアレイ７０内のスコアＳk(i)を作成する場合、各テンプレート列アレイ内の各エントリが、文字テンプレートの幅にわたって、アレイ要素ＩＣ1から始まる画像アレイ６０内の連続する同じ数のエントリと１つずつ比較される。図４は、双方向矢印を含む線を使用してこの比較を表している。比較された各エントリ対の最小値（すなわち小さい方の値）が取り出され、そのテンプレートのスコアを示す連続和に加えられる。最小値のすべての和から得た最終テンプレート・スコアがスコア・アレイ７０内のエントリＳk(i)になる。１組のアレイ群４０内の各テンプレート列アレイは、同様に、エントリＩＣiから始まる画像アレイ６０内の１組のアレイ・エントリと比較される。上述の演算４００の擬似コードは以下のとおりである。
【００２９】
0004624593.tif 000004
【００３０】
発見的スコアを算出する際、特定の比較演算に関して短すぎるか、あるいは長過ぎるデータ構造は、計算を容易にするための必要に応じて、ゼロでパディングする（埋める）ことによって必要な長さに延ばされるか、あるいは必要な長さに打ち切られる。列ベースの発見的スコアは、実テンプレート画像一致スコアの真の上界スコアである。実テンプレート画像一致スコアでは、各テンプレート列の寄与は、テンプレート画像ＡＮＤ演算の後にＯＮになる列内の画素の数である。
ＡＮＤ演算によって、このＯＮテンプレート列画素数が、テンプレート列内のＯＮ画素の数、すなわち突き合わせている画像列内のＯＮ画素の数を超えることはなくなる。したがって、テンプレート内のＯＮ列画素の数と画像内のＯＮ列画素の数との間での最小値（小さい方）は、テンプレートと画像の間の実一致スコアの真の上界である。
【００３１】
列ベースの発見的スコアリングは、マルチレベル・テンプレートを使用するシステムでのテキスト行復号に適用することができる。マルチレベル・テンプレートを使用した復号は、バイレベル・テンプレートまたは標準テンプレートを使用した場合よりも正確なトランスクリプション結果を与える。
【００３２】
マルチレベル・テンプレート６２０（図５）は、前景画素および背景画素を観測画像内のそれらの発生確率に従ってそれぞれの異なる画素グループに分類する。各画素グループが、テンプレート・レベルである。図５は、一例として５レベルのテンプレートを、５つの矩形を積み重ねた集まりとして示している。ここで各矩形はそれぞれ、寸法ｍ×ｎを有し、指定された画素を含む１つのテンプレート・レベルを示す。
【００３３】
単一レベルのテンプレートの各列内の黒画素および白画素は、マルチレベル・テンプレートでは、複数のテンプレート・レベルにわたって分散する。１つの画素が複数のレベルに属することはできず、各画素はあるレベルにだけ存在し、したがって、各画素は１つのレベルにだけ、１度だけ現れる。
【００３４】
テンプレート・レベルは３種類のうちの１つとして指定することができる。第１の種類である黒画素テンプレート・レベルは、文字画像内の黒画素のうち、背景画素であるよりも前景画素（黒）である方の確率が高い画素のセットを含み、実テンプレート画像一致スコアの算出時に正の重みが関連付けされる。テンプレート・レベル６２１、６２２、６２３は、各レベルにおいてラベル６３１「ｂｌ」（blackの略）で示されているように黒画素テンプレートとして指定されている。第２の種類である白画素テンプレート・レベルは、文字画像内の白画素のうち、背景画素であるよりも白画素である確率の方が高い画素のセットを含み、負の重みが関連付けされる。図５のテンプレート６２０は、ラベル６３３「ｗｈ」で示（whiteの略）されているように１つの白画素テンプレート・レベル６２４を含む。第３の種類背景テンプレート・レベルは、文字画像の「サポート」のいかなる部分も形成しない背景画素のセットである。背景テンプレート・レベルはテンプレート画像一致スコアリング・プロセスに関与しない。図５のテンプレート・レベル６２５は、ラベル６３４「ｂｋ」（backgroundの略）で示されているように背景画素テンプレートとして指定されている。一般に、マルチレベル・テンプレートは、少なくとも２つの黒前景画素レベルおよび１つの背景中立画素レベルを含む。
【００３５】
またマルチレベル文字テンプレートは、各レベル毎に関連づけて、観測画像内の文字画像に現れる当該レベルの画素群の確率を示す確率または重みを有する。図５は、レベルの番号を示す下付き文字を有するｗで指定されたボックスとして確率６５０を示している。
【００３６】
ｎレベルのマルチレベル・テンプレートの実スコアを算出するには、黒及び白のテンプレート・レベル群のそれぞれと画像との（ｎ−１）回のマッチング処理が必要があり、この計算において中立（背景）レベルは使用されない。図５の５レベル・テンプレート６２０の実スコアを算出するには、テンプレートと画像の４回のテンプレート画像マッチング計算と、各テンプレート・レベルでの各和の適切な重み付け（正または負）とが必要である。
【００３７】
白画素テンプレート・レベルは、その確率に対応する負の重みを有し、これにより、実テンプレート画像一致スコアを算出する際にこのレベルを使用した場合、一致スコアが低くなるか、あるいはスコアに対して影響がないかのいずれかである。
【００３８】
マルチレベル・テンプレートの発見的スコアを算出するプロセスは、観測画像内のＯＮ画素をテンプレートの様々なレベルに割り当てることを暗黙的に考慮して構成されている。マルチレベル・テンプレートを使用した発見的スコアも列ベースのスコアである。スコアリング・プロセスは、計算効率が高いと共に、発見的スコアを真の上界スコアになるように最大にする。
【００３９】
テンプレート６２０（図５）は、テンプレート列内に総数でｎ個のＯＮ画素およびＯＦＦ画素を含む。この場合、ｎは列の高さを画素単位で表した場合の値である。このｎ個の画素は、様々なテンプレート・レベルに割り当てられるか、すなわちこれらのテンプレート・レベル間で分散される。
【００４０】
所与のテンプレートに関する列ベースのテンプレート画像発見的スコアは、観測画像列（観測画像内の列）内のＯＮ画素が、最高の確率を有する黒テンプレート・レベル列群に割り当てられたときに最大になる。これは、それら各黒テンプレート・レベル列ごとにその最大ＯＮ画素数に達するまでである。次が中立背景レベルに割り当てられたときであり最後が白テンプレート・レベルに割り当てられたときである。このようにして各テンプレート・レベルの各列に画像列画素群を割り当てることを、テンプレート・レベルの「充填（fill）」と言うことができる。発見的スコアは、観測画像列内のＯＮ画素が黒テンプレート・レベルに割り当てられた黒画素を充填したときに高くなり、観測画像列内のＯＮ画素が、白テンプレート・レベルに割り当てられた白画素を充填したときに低くなる。
【００４１】
【表１】
0004624593.tif 000005
【００４２】
表１は、図５の５レベル・テンプレート６２０を使用した、テンプレート列内の画素と画像列内の画素との一致に関する列ベースの発見的スコアを算出するために使用されるサンプル・データを示している。表１は、確率値の降順に配列された５つのテンプレート・レベル６２０を示している。表１において、背景テンプレート・レベル６２５の確率の絶対値が、白テンプレート・レベル６２４の確率の絶対値よりも高く、したがって画素割付けの実行時に先に「充填される」ので、レベル６２５がレベル６２４の前に位置することに留意されたい。テンプレート６２０は、この例では画素高さが２５画素であるものと仮定している。各テンプレート・レベルにはいくつかのＯＮ画素またはＯＦＦ画素が割り当てられる。たとえば、テンプレート・レベル６２３は９つのＯＮ画素を含む。画素列黒画素カウント・データの３つの例が表１に示されている。第１の例では、観測画像列内に１５個ないし２１個の黒画素がある。これらの黒画素は、合計で１５個の黒画素によって黒テンプレート・レベル６２１、６２２、および６２３を完全に充填する。最大で６個の、観測画像列内の他の黒画素は、背景レベル６２５を充填する。この観測画像列の発見的スコアは以下のように算出される。
【００４３】
［数１］
Ｓｃｏｒｅ(15...21)＝２＊ｗ621＋４＊ｗ622＋９＊ｗ623    （１）
背景レベル６２５は発見的スコアを算出する際には使用されず、観測画像列内の黒画素１６から２１は発見的スコアに対して無効である。
【００４４】
表１の第２の観測画像の例において、２３個の黒画素は、合計で１５個の黒画素によって黒テンプレート・レベル６２１、６２２、および６２３を充填する。
観測画像列内の他の６個の黒画素は背景レベル６２５を完全に充填する。残りの２個の黒画素は白テンプレート・レベル６２４を部分的に充填する。この観測画像列の発見的スコアは以下のように算出される。
【００４５】
［数２］
Ｓｃｏｒｅ(23)＝２＊ｗ621＋４＊ｗ622＋９＊ｗ623＋２＊ｗ624（ただしｗ624＜０）    （２）
【００４６】
１１個の黒画素を有する、表１内の第３の観測画像列の例の発見的スコアは以下のように算出される。
【００４７】
［数３］
Ｓｃｏｒｅ(11)＝２＊ｗ621＋４＊ｗ622＋５＊623    （３）
上述の、列ベースの発見的スコアを算出する擬似コードは以下のとおりである。
【００４８】
0004624593.tif 000006
【００４９】
観測画像列内で取り得るすべての黒画素数について、観測画像列とマルチレベル・テンプレート内の列との一致に関する列ベースの発見的スコアを事前に算出し、テーブルに格納しておくことができ、この場合、観測画像列内の黒画素数は、そのテーブルの索引インデックスとして働く。上記の擬似コードに示されたプロセスに従って算出されるスコアから成る個の１×ｎテーブルの組が、テンプレート・ライブラリ内の各ｍ×ｎマルチレベル・テンプレートごとに作成される。
【００５０】
確率論的有限状態ネットワークがマルチレベル・テンプレートを用いるときのテキスト行のデコードに必要な発見的スコアの計算のための擬似コードを以下に示す。
【００５１】
0004624593.tif 000007
【００５２】
この擬似コードは、ｋ×ｗ個の出力スコア・アレイを作成する。この場合、ｋは情報源モデル内のテンプレートの総数であり、ｗは、復号中の画像テキスト行またはその一部の幅である。
【００５３】
さらなる効率化を実現するに、テンプレート列アレイと画像列アレイとの間で２分の１の比較および加算しか必要とされない場合に、単一の発見的スコアの計算を係数２で圧縮する（２分の１にする）ことができる。これは、２つの隣接する画素列内の前景画素の和である前景画素カウントを含む画像列アレイ群およびテンプレート列アレイ群を作成することによって実現することができる。
【００５４】
図６は、テンプレート列アレイ４６内の２つの列画素カウントから成る群を合計して単一の組合せ列画素カウントを作成する方法を示す、１Ｄテンプレート画素和データ構造８６を概略的に示している。データ構造８６は、データ構造４６と同じ１×ｍデータ構造であるように示されている。一つの実装では、図２のテンプレート列アレイがまず算出され、次いで、隣接する列前景画素のカウントが合計され、テンプレート列アレイ・データ構造のエントリ群の２分の１に（すなわち、１エントリおきに）格納される。もちろん他の実装方式も可能である。
【００５５】
１Ｄ画像画素和データ構造を算出する場合、画像アレイ６０内のあらゆる２つの隣接する列画素カウントが合計され単一の組合せ列画素カウントが作成される。画像画素和データ構造内の各組合せカウントは、画像アレイ６０内の互いに隣接する列画素カウント同士数の和を表し、ここで和をとる列画素カウントのペアは、隣接するペアと一部が重なる。
【００５６】
列ベースの発見的スコアを作成する場合、テンプレート画素和データ構造内の組合せ列画素カウントが画像画素和データ構造内の対応する組合せ画素カウント和と突き合され、最小画素カウント（小さい方のカウント）が求められる。次いで、これらの最小値が合計されスコアが作成される。
【００５７】
テキスト行画像内のあらゆる画像位置ｉでの発見的スコアの計算を不要にすることによって、計算をさらに削減することができる。ある画像位置の上界発見的スコアを隣接する次の画像位置の上界発見的スコアとして使用することによって、他の上界発見的スコアを算出することができる。
【００５８】
より少ない数の計算によって発見的スコアを作成する上述の概念およびプロセスは、マルチレベル・テンプレートのスコアの作成に適用することもできる。
【００５９】
ビタビ手順を列ベースの発見的スコアリングと共に使用してテキスト行画像を復号する主要な関数を図７のフローチャートに示す。発見的スコアを使用した復号では通常、数回の反復が必要である。復号の反復により、ボックス５１０で、テキスト行を通る節の最良の道が推定される。この最良の道での節同士の間の遷移は、現時点でのテキスト行の推定メッセージ（トランスクリプション）を含む文字ラベル群を示す。次のビタビ反復が開始される前に、ボックス５３０で、推定された最良の道の一部として識別された各節について実テンプレート画像一致スコアが算出される。このプロセスを最良の道の再スコアリングと呼ぶ。
【００６０】
次いで、推定された最良の道の各節の再スコアリングが完了すると、ボックス５４０で、各節毎に、その節のｘ位置でのいくつかの異なる垂直（ｙ）位置において、推定された最良の道の一部として識別された各テンプレートがテキスト行画像と突き合される。各ｙ画像位置ごとに実テンプレート画像一致スコアが作成される。各テンプレートに関して算出される最大実スコアが各節のｙ画像位置を示す。推定された最良の道に沿った各節位置での単一のテンプレートの実スコアが算出され、ベースラインの最良の位置が判定される。
【００６１】
次いで、ボックス５１０で、すでに推定されている最良の道の再スコアリングされた節の実スコアを使用すると共に、他のすべての画像位置に列ベースの発見的スコアを使用して、テキスト行のビタビ復号が繰り返される。最良の道に沿ったすべての節が再スコアリングされるか、あるいは現在のビタビ位置が前の反復で見つかった最良の道と同じになったことがボックス５４８のテストで示されるまで、テキスト行の復号が反復される。
【００６２】
実験結果は、フルページ（２Ｄ）ビタビ・デコーダにおける列ベースの発見的スコアリングを使用したテキスト行の復号の場合、全体の計算時間が係数４０で圧縮されることを示している。この利得は２つの部分において得られる。第１に、実験結果は、主として、行復号のために実スコアではなく発見的スコアを算出することによる時間短縮のために、単一のテキスト行を復号するのに必要な計算時間が係数８だけ短縮されることを示している。第２に、列ベースの発見的スコアリングは、５つの垂直ベースライン位置について実テンプレート画像一致スコアを作成することを不要にする。各ベースライン位置について実テンプレート画像一致スコアを求めることは、フルページ（２Ｄ）ビタビ復号では、実ベースラインが不明であるために必要になるものであるが、これが本実施形態の手法では不要になる。列ベースの発見的スコアリングでは、ベースラインの最良の垂直位置の上界が自動的に与えられる。
【００６３】
本実施形態の手法は、図８のプロセッサ制御型マシン１００と共通の構成要素、特性、および構成を有するあらゆるマシンで実現することができる。
【００６４】
マシン１００は、本実施形態の手法を実施するために特別に構成し最適化したものでもよいし、記憶したコンピュータ・プログラムによって選択的に活動化または再構成される汎用コンピュータを備えたものでもよい。
【００６５】
マシン１００の物理的構成要素を実際に接続する方法には、いくつかまたはすべての構成要素間のハード配線物理接続と、リモート通信網またはローカル通信網ならびに赤外線接続および無線接続などによる、有線通信設備または無線通信設備を介した接続を含めることができる。
【００６６】
マシン１００は、例えば、図１の演算２００、３００、４００、および５００を実行して、テンプレート列アレイおよび画像領域列アレイを使用した列ベースの発見的スコアを算出し、この発見的スコアを使用してテキスト行画像復号を実行するように構成される。あるいは、マシン１００は、マルチレベル・テンプレートについて作成されたテンプレート・スコア・テーブルを使用して列ベースの発見的スコアを算出する演算を行うように構成することができる。入力観測画像は、信号源１５８、すなわちたとえば、画像スキャナやデジタル・カメラなどの撮像装置、メモリ装置、通信チャネル、データ・バス、演算を実行する他のプロセッサ、他の適切なビットマップ画像信号源など、から与えることができる。信号源１５８から与えられた入力画像は、入力回路１５６を介してプロセッサ１４０に転送され、データ・メモリ１１４に記憶することができる。マシン１００には、画像を表示できる従来型の表示装置（図示せず）、または印刷装置を含めることもできるが、このことは必須ではない。
【００６７】
プロセッサ１４０は、プログラム・メモリ１１０にアクセスして命令を取り出し、この命令を実行することによって動作する。マシン１００が、図１に示された演算を実行するように構成されている場合、プログラム・メモリ１１０は、列ベースの発見的スコアリングを使用したテキスト行復号を実行するために図１の演算５００を実施するテキスト行復号命令を含む。プログラム・メモリ１１０は、このような演算に関して、既に例示した擬似コードで示された処理内容に従って、テンプレート列アレイ４０、画像アレイ６０、および発見的列ベース・スコア７０を作成する命令サブルーチンを含む。
【００６８】
プロセッサ１４０は、命令の実行時に、データ・メモリ１１４にアクセスし、演算を実行するのに必要なデータを得るか、あるいは格納する。たとえば、プロセッサ１４０は、計算済みの発見的スコア７０をデータ・メモリ１１４に格納する。
【００６９】
図８は、マシン１００でソフトウェア・プロダクト１６０を使用できることも示している。ソフトウェア・プロダクト１６０は、記憶媒体アクセス回路１５０からアクセスできるデータ記憶媒体１７０を含む。ソフトウェア・プロダクト１６０は、データ記憶媒体１７０と、このプロダクトについて説明した適切な文書とを含む収縮包装（シュリンクラップ）パッケージの形で市販することができる。
【００７０】
記憶媒体アクセス回路１５０は、データ記憶媒体１７０が、サーバなどリモートに位置する記憶装置の一部として記憶されているときに、データ記憶媒体１７０上の命令データにアクセスするために通信アクセス・ソフトウェアおよび回路を含む。ソフトウェア・プロダクト１６０は、リモートに位置する記憶装置から通信設備を介してユーザに送信される、本実施形態の方法を実施するための命令データを示すデータ・ストリーム、の形で市販するか、あるいはその他の方法でユーザによって利用できるようにすることができる。
【００７１】
データ記憶媒体１７０は、列ベースの発見的スコアリングを使用したテキスト行復号が使用されるときに実行できるようにプロセッサ１４０に供給される図１の演算２００、３００、４００、および５００を実行するための命令データ１６６および１６８、またはマルチレベル・テンプレートに関する演算を実行するための命令データを記憶する。
【図面の簡単な説明】
【図１】  列ベースの発見的スコアリングを使用して画像テキスト行を復号する復号演算を示すフローチャートである。
【図２】  １組のテンプレートに関して作成された、一次元列ベースの、１組のテンプレート画素カウント・アレイの概略図である。
【図３】  入力画像の水平画像領域に関して作成された、一次元列ベースのテンプレート画素カウント・アレイの概略図である。
【図４】  列ベースの発見的スコアを算出する方法を説明するための概略図である。
【図５】  本発明の第２の実施形態で使用される種類のマルチレベル文字テンプレートの概略図である。
【図６】  複数のテンプレート画素カウント列が合計される発見的スコアリングの変形例の概略図である。
【図７】  列ベースの発見的スコアリングが使用されるときに画像テキスト行復号手順の変形例を示すフローチャートである。
【図８】  本発明を実施できるように構成されたマシンを示し、本発明に係るソフトウェア・プロダクトと、このプロダクトを上記のマシンと共に使用する方法とをさらに示す簡略化されたブロック図である。
【符号の説明】
２１，２２，２３，２４  テンプレート、４０  テンプレート列アレイ群、４２，４４，４６，４８  テンプレート列アレイ。
【図１】
0004624593.tif 000008
【図２】
0004624593.tif 000009
【図３】
0004624593.tif 000010
【図４】
0004624593.tif 000011
【図５】
0004624593.tif 000012
【図６】
0004624593.tif 000013
【図７】
0004624593.tif 000014
【図８】
0004624593.tif 000015