JPH08504076A

JPH08504076A - テンプレート除去のため画像を位置合せするための方法および装置

Info

Publication number: JPH08504076A
Application number: JP7514168A
Authority: JP
Inventors: ズロトニック，アヴァイド
Original assignee: インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン
Priority date: 1993-11-16
Filing date: 1993-11-16
Publication date: 1996-04-30
Anticipated expiration: 2014-07-12
Also published as: JP2918064B2; EP0679313A1; WO1995014348A1; US5793887A

Abstract

(57)【要約】本発明は、テンプレート除去用の微細位置合せのための改良された方法および装置に関する。この方法には、書き込まれたテンプレート画像と基準テンプレート画像とを、所与の画素列数ｗの垂直バンドに分割するステップと、ＯＣＳアルゴリズムを使用して、本明細書で垂直入力バンドと称する書き込まれたフォームの垂直バンド内の線と基準テンプレート画像の対応するバンド内の線とを相関させるステップと、各線がそれぞれの新位置に移動されている新入力画像を構成するステップとが含まれる。この新画像は、たとえばテンプレート除去などの入力画像として使用される。

Description

【発明の詳細な説明】テンプレート除去のため画像を位置合せするための方法および装置［技術分野］本発明は、画像の位置合せ、具体的には、テンプレートに書き込まれた情報を、空のテンプレートの画像を除去することによって分離できるようにするために、空のテンプレートの画像と書き込まれたテンプレートの画像とを位置合せするための方法および装置に関する。本発明は特に、不変フォームに書き込まれた情報を、画像のうちで情報内容に寄与しない部分とは別に処理しなければならない分野に関する。［背景技術］紙文書の扱いは、現在のオフィス環境において日課となっている。フォームなどの文書の処理をより効率的にしようとする時には、コンピュータやデータ伝送ネットワークなどの近代的なデータ処理手段を利用できるようにするため、文書をディジタル化しなければならない。一旦そのようなシステムで文書を使用できるようになったならば、文書を記憶装置にロードし、後に検索することができる。記憶装置と文書の検索は、これに関する１態様に過ぎず、もう一方の、おそらくより重要な態様は、文書に含まれる情報の取り扱いである。文書に含まれる情報の取り扱いには、通常は、読取り装置による情報の獲得、獲得した情報の機械可読コードへの変換、後におそらくは繰り返されるであろう処理のためのコード化された情報の記憶、情報の実際の処理および、処理の結果の最終的な出力が含まれる。光学スキャナなどの読取り装置による情報の獲得は、十分に高い解像度で行われる必要がある。さもないと、情報内容が不完全になったり、部分的に失われるはずである。読取り装置は通常、大量の走査データをもたらし、この大量のデータが、高速で信頼性のある処理のために強力なコンピュータと、記憶のために大きな記憶容量を必要とする。典型的な例として、Ａ４サイズ（２７９×２１０ｍｍ）の１ページを１００画素／ｃｍ（画素とは、画像要素を表し、白または黒のドットである）で走査すると、約７００Ｋバイトの記憶空間が必要になる。ごくあたりまえの分量の文書でも、法外な量の記憶域が必要になる可能性がある。書き込まれたフォームの画像の大半は、情報内容に寄与しないので、空のフォームである標準部分または一定部分（ＣＰ）と、書き込まれたデータである可変部分（ＶＰ）を分離するために、異なる方法が開発されてきた。この一定部分（ＣＰ）と可変部分（ＶＰ）の分離を、テンプレート除去と称するが、これには、下記の長所がある。・記憶域の節約：フォーム画像の多くは、一定部分（ＣＰ）の単一のコピーに重畳された可変部分（ＶＰ）から再構成できる。通常、可変部分（ＶＰ）のサイズは、全画像のサイズのごく一部に過ぎず、記憶域の９０％を節約することが可能である。・通信の改良：上と同じ理由から、一定部分（ＣＰ）と可変部分（ＶＰ）を分離すると、通信量がかなり節約され、したがって、フォーム処理システムに共通するボトルネックの１つが除去される。・光学文字認識（ＯＣＲ）の精度向上：情況によっては、フォームの一定部分（ＣＰ）が、自動文字認識と干渉する可能性がある。可変部分（ＶＰ）だけにアクセスできれば、この問題のかなりを除去できる。一定部分（ＣＰ）すなわちフォーム自体の除去のための方法は、たとえば、D ．E．Nielsen et al .，著、”Evaluation of Scanner Spectral Response for Insurance Industry Documents”，16/A44 NCI Program，Working Paper No．２、１９７３年５月によって報告され、実施されてきた。この方法は、「ドロップアウト・インク」技法とも称するが、フォームを印刷する時に、通常のスキャナに透明な特殊なカラー・インクを使用するという発想に基づくものである。このタイプの完成されたフォームを走査する場合、基本的なパターン（すなわちＣＰ）は、スキャナには見えなくなり、可変部分（ＶＰ）だけがコンピュータに入力されるはずである。この手法の明らかな短所は、特殊なインク感度を有するスキャナを使用するので、既存のアーカイブにこの手法を適用できないことである。また、特殊インクを使用するのは、確かに面倒であり、コストも高い。「ドロップアウト・インク」技法のもう１つの短所は、フォーム背景は除去したいが、フォームの印刷方法や印刷に使用される色の種類に影響が及ぶことを望まないカスタマが存在することである。書き込まれた情報からフォーム背景を分離するためのもう１つの手法が、欧州特許出願ＥＰ−Ａ−０４１１２３１（米国特許第５１８２６５６号明細書）、表題「Method for Compressing and Decompressing Forms by Means of very large Symbol Matching（超大記号マッチングによるフォームの圧縮伸長のための方法）」に開示されている。この手法によれば、空のフォーム（ＣＰ）のサンプルを事前に走査し、得られたデータをディジタル化し、コンピュータ・メモリに記憶してフォーム・ライブラリを作成する。次に、元の、圧縮しようとする書き込まれたフォーム（Ｆ）を走査し、得られたデータをディジタル化し、空のフォーム（ＣＰ）の表現を検索してこれから減算する。この差が、可変部分（ＶＰ）すなわち書き込まれた情報のディジタル表現になる。そのようなフォーム除去を実行するためには、入力フォーム画像（Ｆ）と空のテンプレート（ＣＰ）の画像を正確に位置合せすることが必要である。入力フォーム画像が、全体的にはテンプレートと位置合せされている、すなわち、オフセット、スキュー、スケールの差がない時であっても、通常は、局所的なゆがみがあり、テンプレート（すなわち一定部分ＣＰ）をドロップ・アウトする前にそのゆがみを直さなければならない。このような局所的なゆがみは、スキャナ動作に一貫性がないか、写真コピーのゆがみの結果であることが多い。最終的な位置決めを計算する、すなわち、画像の可変部分（ＶＰ）に関して一定部分（ＣＰ）を位置合せする方法が、上で述べた欧州特許出願ＥＰ−Ａ−０４１１２３１（米国特許第５１８２６５６号明細書）と、欧州特許出願ＥＰ− Ａ−０４１１２３２（米国特許第５２０４７５６号明細書）、表題「Method for High-Quality Compression of Binary Text Images（２進テキスト画像の高品質圧縮のための方法）」に記載されている。局所歪みが少なく、区分的線形であると仮定して、入力（Ｆ）とテンプレート画像（ＣＰ）の両方を小さなブロックに分解し、ヒストグラム相関を使用して、対応するブロックの相対オフセットを見つける。別個の一貫性保存処理を使用して、異なるブロックに関して計算されたオフセットの間に衝突が発生しないようにする。あるブロックのヒストグラムに十分な情報がない場合には、隣接ブロックのオフセットを使用して、そのブロックの変換を計算する。実際には、上の技法は非常に良好に機能するが、下記のいくつかの特殊な事例には、信頼性の向上が必要である。・１つのフォームのコピーを複数回繰り返すことでゆがみが累算され、既存技法の制限要因に直面することになる。・スキャナによっては、テンプレートと入力の両方として同一のフォームを使用しても、ドロップアウト後にきれいな画像がもたらされない。・非常に密に書き込まれた区域のフォーム再構成でのアーチファクトが報告されており、このアーチファクトは、わずかな位置決め誤差に対して非常に敏感である。・テンプレート走査の品質が低い時に、深刻な位置決め誤差がいくつか報告されている。テンプレート除去のための既知の技法は、非線形ゆがみを有する画像の取り扱いに適していないことがわかっている。［発明の開示］本発明の目的は、既知のテンプレート除去技法の信頼性を高めるために、非線形ゆがみを有する画像の取り扱いを改善することである。本発明のもう１つの目的は、空の基準テンプレート画像（ＣＰ）に対する入力画像（Ｆ）の微細位置合せを達成するために、局所ゆがみを克服することである。本発明のもう１つの目的は、微細位置合せ処理の堅牢さを高めた、テンプレート除去のための方法および装置を提供することである。上記の目的は、最適対応サブシーケンス（ＯＣＳ）・アルゴリズムを使用して微細位置合せ処理の堅牢さを向上させるという点で達成された。本発明による方法には、基準テンプレート画像内の線と書き込まれたテンプレート画像内の線の１方向への射影の対応する対を見つけることによって、前記線基準テンプレート画像内の前記線と書き込まれたテンプレート画像内の前記線とを相関させるステップと、前記投影の方向に垂直な方向での対のそれぞれの線の２つの射影の変位を決定し、前記射影の対の間で一致を達成するために書き込まれたテンプレート画像の各線の画素を移動しなければならない行または列の数を評価するステップと、最後のステップで決定されたとおりに、前記射影の方向に垂直に、書き込まれたテンプレート画像の線の画素をシフトすることによって、新入力画像（２６）を生成するステップとが含まれる。本発明のもう１つの好ましい実施例では、同一のステップを、上の処理の射影の方向に関して９０゜回転した方向で繰り返す。もう１つの実施例では、上記の処理を実行する前に、書き込まれたテンプレート画像と基準テンプレート画像とをバンドに分割する。この方法には、曲がった線に簡単に対処できるという長所がある。［図面の簡単な説明］第１図は、フォーム・ライブラリへの基準テンプレート画像の記憶と検索を示し、本発明による水平微細位置合せを示す流れ図である。第２図は、基準テンプレートの画像と入力テンプレートの画像を示す図である。第３図は、本発明によって垂直バンドに分割された、第２図の基準テンプレート画像と入力テンプレート画像を示す図である。第４図は、第２図の基準テンプレートと、本発明によって得られた新入力画像を示す図である。第５図は、本発明による垂直微細位置合せを示す図である。第６図は、本発明による装置の概略ブロック図である。［発明の好ましい実施例］書き込まれたテンプレートの一定部分（ＣＰ）を除去することをテンプレート除去技法と称するが、その前に、基準テンプレート画像（ＣＰ）と称する空のテンプレートの画像を、書き込まれたテンプレートの画像に対して正確に位置合せしなければならない。特に局所ゆがみ、とりわけ非線形のゆがみが、この微細位置合せの精度に悪影響を及ぼす。書き込まれたテンプレート（Ｆ）に関する一定部分（ＣＰ）の位置合せが良ければ良いほど、テンプレート除去処理の結果も良くなる。微細位置合せ処理全体の堅牢さを改善するために、最適対応サブシーケンス（ＯＣＳ）・アルゴリズムと称するアルゴリズムが採用された。この最適対応サブシーケンス・アルゴリズムは、無限アルファベット・ペナルティ最小化問題（infinite alphabet penalty minimisation problem）であるステレオ・マッチング（stereo matching）に関して既に説明されている。このＯＣＳアルゴリズムによる部分文字列マッチングの問題は、論文”Optimal Correspondence of String Su bsequences”，Y．P．Wang他，IEEE Transaction on Pattern Analysis and Mac hine Intelligence，Vol．12，No．11，１９９０年１１月、pp．1080-1087に記載されている。以下の節では、テンプレート除去のための微細位置合せに関する修正ＯＣＳアルゴリズムすなわち、フォーム認識用最適サブシーケンス対応の使用を詳細に説明する。下での問題の定式化は、関数ｆ（ｉ，ｊ，ａ，ｂ）が、シーケンス要素ａおよびｂの他に引数として指標ｉおよびｊをとる点で、通常とは多少異なることに留意されたい。この表記によって、望ましくない一致を制御する際に多少の柔軟性が得られる。画素の２つのシーケンスすなわち、Ａ＝｛ａ₀，ａ₁，…，ａ_N｝およびＢ＝｛ｂ₀，ｂ₁，…，ｂ_M｝があり、すべての数値引数に関してｆ（ｉ，ｊ，ａ，ｂ） ≧０になる関数ｆ（ｉ，ｊ，ａ，ｂ）があるものとする。この関数ｆ（ｉ，ｊ，ａ，ｂ）を使用して、要素ａと要素ｂの間の一致の質を評価する。ＯＣＳは、和が最大になるインデックス対Ｐ［２］の集合である。前記Ｐ［２］の集合には、Ｐ＝｛（ｊ₀，ｋ₀），（ｊ₁，ｋ₁），…，（ｊ_L，ｋ_L）｝［２］という形でインデックス対が含まれ、０≦ｊ₀＜ｊ₁＜…＜ｊ_L≦Ｎ０≦ｋ₀＜ｋ₁＜…＜ｋ_L≦Ｍであり、Ｌは、要素ＡおよびＢのシーケンスの一致した要素の数である。上のステップの最後に、最大の和［１］とインデックス対のシーケンスＰが、出力として得られる。本明細書で使用されるＯＣＳアルゴリズムは、下で詳細に説明する。ステップ１）ないし４）に従って、行列ｓを計算する。ただしｓ（Ｎ，Ｍ）は、Ａ＝｛ａ₀，ａ₁，…，ａ_N｝およびＢ＝｛ｂ₀，ｂ₁，…，ｂ_M｝に関するＯＣＳ問題のスコアである。１）Ｓ（０，０）＝ｆ（ａ₀，ｂ₀）２）ｆｏｒｉ＝１ｔｏＮ−１ｓ（ｉ，０）＝ＭＡＸ｛ｓ（ｉ−１，０），ｆ（ｉ，０，ａ_i，ｂ₀）｝３）ｆｏｒｊ＝１ｔｏＭ−１ｓ（０，ｊ）＝ＭＡＸ｛ｓ（０，ｊ−１），ｆ（０，ｊ，ａ₀，ｂ_j）｝４）ｆｏｒｉ＝１ｔｏＮ−１ｆｏｒｊ＝１ｔｏＭ−１ｓ（ｉ，ｊ）＝ＭＡＸ｛ｓ（ｉ，ｊ−１），ｓ（ｉ−１，ｊ），ｓ（ｉ −１，ｊ−１）＋ｆ（ｉ，ｊ，ａ_i，ｂ_j）｝ステップ５）ないし９）では、集合Ｐのインデックス対のシーケンスが、次式によって計算される。５）ｉ＝Ｎ−１，ｊ＝Ｍ−１６）ｗｈｉｌｅｉ≧０ａｎｄｊ≧０７）ｉｆｉ＞０ａｎｄｓ（ｉ−１，ｊ）＝ｓ（ｉ，ｊ）ｉ＝ｉ−１ｅｌｓｅ８）ｉｆｊ＞０ａｎｄｓ（ｉ，ｊ−１）＝ｓ（ｉ，ｊ）ｊ＝ｊ−１ｅｌｓｅ９）ｉｆｓ（ｉ，ｊ）＞０Ｐの先頭に（ｉ，ｊ）を挿入ｉ＝ｉ−１ｊ＝ｊ−１ｓ（Ｎ−１，Ｍ−１）が、修正ＯＣＳアルゴリズムの戻り値であり、Ｐは、要求されたインデックスを有する。本発明の数学的背景が、上で詳細に示された。以下の節では、本発明による方法を実例に関して説明する。本発明のステップと、準備ステップ１ないし４を、第１図および第５図の流れ図に示す。第１図に、基準テンプレート（ＣＰ）を走査し（ステップ１）、本発明の微細位置合せ処理のための基準入力として使用するか、フォーム・ライブラリに記憶できることが概略的に示されている。このようなライブラリへの記憶とそこからの検索を、ステップ２、３および４に示す。第２図を参照すると、所与の空の基準テンプレート画像２０（ＣＰ）があり、基準テンプレート画像２０は、１２行の画素と２４列の画素からなる。説明を簡単にするために、この図と後続の図では、基礎となる格子を図示し、黒画素のそれぞれを、「×」として図示する。水平とは画像の行に平行な方向を意味し、垂直とは画像の列に平行な方向を意味することに留意されたい。基準テンプレート画像２０（ＣＰ）の左側には、１行あたりの黒画素の個数が示されている。この数のシーケンスを、Ａ＝｛０，１９，０，０，１９，０，１，２，０，１９，０，０｝と表すことができる。基準テンプレート画像２０は、通常は記憶装置（フォーム・ライブラリまたは作業バッファ）に記憶され、そこから簡単に検索できる（ステップ４）。基準テンプレート画像２０を走査し記憶するステップ１ないし４は、必ずしも第１図に示された他のステップを実行する直前に実行しなくてよい。適切な基準テンプレートを有するデータベースすなわち、異なる空のフォーム（ＣＰ）を含むデータベースの作成と維持は、本明細書では示さない。本発明の第１ステップとして、処理されるテンプレート（通常は書き込まれたテンプレート）を、適当なスキャナによって走査し、このテンプレートの画像２１（Ｆ）を得る。画像２１を、以下では入力画像と称する。このステップは、第１図ではステップ１０として示されており、ディジタル化された入力画像２１自体は、第２図に示されている。このテンプレートの内容すなわち、通常は書き込まれた情報は、本発明による微細位置合せの説明には関係がなく、基準テンプレート（ＣＰ）として既に使用されたものと同様の空のテンプレートを走査した。２つの画像すなわち基準テンプレート画像２０と入力画像２１を比較すると、スキャナによって導入された不正確さのために２つの画像がわずかに異なることがわかる。入力画像２１は、１１行２４列の画素だけを有し、黒画素の一部が失われたり、位置が狂っている。入力画像の１行あたりの黒画素の個数は、画素のシーケンスＢ＝｛０，１８，１，０，１０，８，０，３，０，０，１８｝によって表される。入力画像２１の１行あたりの画素の数と比較した基準テンプレート画像２０の１行あたりの画素数を、表１に示す。入力画像２１の一定部分（ＣＰ）を除去する前に、局所ゆがみを取り除き、入力画像２１を基準テンプレート画像２０に関して正確に位置合せしなければならない。本発明によれば、基準テンプレート画像２０と入力画像２１の両方を、ここで垂直のバンド、すなわち、複数列の画素を含むバンドに分割する。このステップは、第１図のステップ１１によって表される。第３図に示されているように、基準テンプレート画像２０は、２つの垂直基準バンド２２（ＣＰ_A）および２３（ＣＰ_B）に分割される。入力画像２１は、２つの垂直入力バンド２４（Ｆ_A）および２５（Ｆ_B）に分割される。これら４つの垂直バンドの各行の黒画素の個数を、第３図に示す。次に、入力画像２１の垂直入力バンド２４および２５のそれぞれと、基準テンプレート画像２０の垂直基準バンド２２および２３とのマッチングを、修正ＯＣＳアルゴリズムを使用して実行する。このステップは、ステップ１２に示されている。垂直入力バンド２４および２５内の線の水平射影を垂直基準バンド２２および２３内の線に相関させるために、ＯＣＳを使用する。これによって、垂直バンド内の前記線の垂直オフセットを決定する。黒画素のシーケンス（この例ではＡ_A、Ａ_BおよびＢ_A、Ｂ_B）は、垂直バンド内の線の水平投影であり、ｆ（ｉ，ｊ，ａ，ｂ）は、これらの黒画素シーケンスの要素間の一致の質を評価する関数である。表２に、垂直基準バンド２２と垂直入力バンド２４のマッチングを示す。文字「―」は、存在しない項目を示す。これによって、表３の対応する項目を削除することが暗示される。マッチングされた要素の数は、Ｌ＝１０である。垂直バンドＣＰ_BおよびＦ_Bの画素シーケンスＡ_BおよびＢ_Bのマッチングを、表３に示す。マッチングされた要素の数は、やはりＬ＝１０である。上のＯＣＳアルゴリズムに従って、前記垂直入力バンドＦ_AおよびＦ_B内の線の新しい垂直位置が定義される。次に、線成する。この垂直シフトによる再構成は、第１図ではステッそれ以降の全てのステップ、すなわち、テンプレート除去（第１図のステップ１４）に直接に、または、第５図の水平微細位置合せステップに、入力画像として使用される。本発明による微細位置合せは、この時点で終了して、前記力画像として使用するか、第５図のステップ５０ないし５２を実行して、基準テンプレート画像２０（ＣＰ）と新入力画たとえば画素の行に平行か画素の列に平行など、１方向だけの微細位置合せは、たとえば書き込まれたフォームを読み取るのにファクシミリを使用する場合、主に垂直軸に沿ったゆがみが発生するので、このような場合には満足な結果をもたらす可能性がある。この種のゆがみは、モータが機械的に不完全であるために発生する場合がある。水平微細位置合せ（ステップ５０ないし５２）を、以下で説明する。マッチング処理の基本原理は、上の例によって既に説明済みであるから、ステップ５０ないし５２は完全に詳細には説明しない。を、所与の「高さ」ｈ（ｈ＝画素の行の数）を有する水平バンドに分割する。好ましい例では、テンプレートの全長が２４画素しかないので、たとえばｈ＝１２画素／バンドを水平バンドの「高さ」として選択できる。前記新入力画像２６割するステップは、第５図の流れ図のステップ５０に示されている。次に、ＯＳＣアルゴリズムを使用して、水平入力バンド内の線と水平基準バンド内の線とを相関させ、前記バンド内の垂直線の水平オフセットを決定する。Ａ_a およびＡ_bは、水平基準バンド内の線の垂直投影であり、Ｂ_aおよびＢ_bは、水平入力バンド内の線の垂直投影である。このステップは、第５図のステップ５１に示されている。マッチング・ステップ１２に関して説明したように、マッチング関数ｆ（ｉ，ｊ，ａ，ｂ）によって、シーケンスＡ_aとＢ_bの間の一致ならびにＡ_b とＢ_bの間の一致の質を評価する。最後に、第５図のステップ５２に示されるように、水平入力バンド内の垂直線をその最適位置に移動することによって、上のアルゴリズムは、下記の最適化方法によって高速化できる。１．第１のマッチング処理すなわち、垂直バンドによる水平線の位置合せか、第２のマッチング処理すなわち、水平バンドによる垂直線の位置合せのいずれか一方だけを実行する。２．ｉ＜ｊ＋ｍａｘ＿ｄｉｆｆまたはｊ＜ｉ＋ｍａｘ＿ｄｉｆｆになる場合にＳを評価しない。ただし、ｍａｘ＿ｄｉｆｆは、応用例に依存する。３．行ｉ−１の最大値に関してｓ（ｉ，ｊ）が十分大きい場合には、行ｉの残りを評価しない。ただし、「十分大きい」は、応用例に依存する。４．列ｊ−１の最大値に関してｓ（ｉ，ｊ）が十分大きい場合には、列ｊの残りを評価しない。ただし、「十分大きい」は、応用例に依存する。たとえばＡ４のページからなる文書を処理する時、各ページを「幅」ｗ＝２５０画素の垂直バンドに分割し、「高さ」ｈ＝２５０画素の水平バンドに分割すると、よい結果が得られた。本発明のＯＣＳアルゴリズムに使用されるマッチング関数ｆ（ｘ，ｙ）は、修正可能であることに留意されたい。ｆ（ｘ，ｙ）＝｜ｗ −（ｘ−ｙ）｜やｆ（ｘ，ｙ）＝１＋ＭＩＮ（ｘ，ｙ）が、使用可能なマッチング関数の例である。テンプレート除去のためのシステムの例を、第６図に概略的に示す。このシステムには、スキャナ６１、フォーム・ライブラリ６２、作業バッファ６３、および、プロセッサ６４の一部であるかこれによって制御される微細位置合せユニット６５が含まれる。これらの回路および要素の全てが、たとえばＡＴバスとすることのできるバス６６によって相互接続される。本発明によれば、前記フォーム・ライブラリ６２に記憶されているものであってもよい基準テンプレート画像が、プロセッサ６４の要求に基づいて前記微細位置合せユニット６５に供給される。書き込まれたテンプレートを、スキャナ６１によって走査し、その画像を作業バッファ６３に転送する。この作業バッファ６３から、要求があった時に画像を検索できる。微細位置合せユニット６５は、プロセッサ、フォーム・ライブラリ６２および作業バッフア６３との相互作用によって、本発明による諸ステップを実行する。最後に、微レート除去を行うことができる。上の例のように黒画素と黒画素のシーケンスに対する微細位置合せ処理に基づくのではなく、白画素と白画素のそれぞれのシーケンスを使用することも可能である。さらに、特定の情況の下では、画像の分割が不要になる、すなわち、本発明に従って行または列の１つのバンドだけが処理されることに留意されたい。本明細書では、画素の行が、紙の短い辺に平行であるか、その辺に垂直である。行に対して垂直の画素の列に関しても、同じ事があてはまる。本発明の技法は、従来のテンプレート除去技法よりはるかに堅牢である。この技法は、古い技法の失敗例を多数用いてテストされ、圧縮の達成、視覚的品質および速度に関して優れていることが証明されている。

Claims

【特許請求の範囲】１．画素の行および列を含む基準テンプレート画像および書き込まれたテンプレート画像を位置合せする方法であって、ａ）前記基準テンプレート画像内の線および前記書き込まれたテンプレート画像内の線の１方向への射影の対応する対を見つけることによって、前記基準テンプレート画像内の前記線と前記書き込まれたテンプレート画像内の前記線とを相関させるステップと、ｂ）前記射影の方向に垂直な方向での前記対のそれぞれの線の２つの射影の変位を決定し、前記射影の対の間で一致を達成するために前記書き込まれたテンプレート画像の各線の画素をシフトしなければならない行または列の数を評価するステップと、ｃ）決定された変位を使用して、前記射影の方向に垂直に前記書き込まれたテンプレート画像の線の画素をシフトすることによって、新入力画像を生成するステップとを含む方法。２．さらに、ａ）請求項１のステップａ）で選択された射影の方向に垂直な方向の射影を用いて、前記基準テンプレート画像内および前記新入力画像内の線の射影の対応する対を見つけることによって、前記基準テンプレート画像内の前記線と前記新入力画像内の前記線とを相関させるステップと、ｂ）請求項１のステップａ）で選択された前記射影の方向に平行な方向での前記対のそれぞれの線の２つの射影の変位を決定し、前記射影の対の間で一致を達成するために前記新入力画像の各線の画素をシフトしなければならない行または列の数を評価するステップと、ｃ）決定された変位を使用して、請求項１のステップａ）で選択された前記射影の方向に平行に、前記書き込まれたテンプレート画像の線の画素をシフトすることによって、新入を含む、請求項１に記載の方法。３．請求項１のステップａ）ないしｃ）を実行する前に、前記基準テンプレート画像が、複数の画素列を有する基準バンドに分割され、前記書き込まれたテンプレート画像が、複数の画素列を有する対応する入力バンドに分割され、請求項１のステップａ）ないしｃ）が、基準バンドとそれに対応する入力バンドのそれぞれについて別々に実行されることを特徴とする、請求項１に記載の方法。４．請求項２のステップａ）ないしｃ）を実行する前に、前記基準テンプレート画像が、複数の画素行を有する基準バンドに分割され、前記書き込まれたテンプレート画像が、複数の画素行を有する対応する入力バンドに分割され、請求項２のステップａ）ないしｃ）が、基準バンドとそれに対応する入力バンドのそれぞれについて別々に実行されることを特徴とする、請求項２に記載の方法。５．前記行に平行な方向の線の射影が、それぞれの画像またはバンドの各行の黒画素の数を合計することによって決定され、前記列に平行な方向の線の射影が、それぞれの画像またはバンドの各列の黒画素の数を合計することによって決定されることを特徴とする、請求項１、請求項２、請求項３または請求項４に記載の方法。６．前記一致が、最適対応シーケンス・アルゴリズムを使用して決定されることを特徴とする、前の請求項のいずれかに記載の方法。７．前記一致の質を評価するためにｆ（ａ，ｂ）＝１＋ＭＩＮ（ａ，ｂ）またはｆ（ａ，ｂ）＝｜ｗ−（ａ−ｂ）｜およびｆ（ａ，ｂ）＝｜ｈ−（ａ−ｂ）｜というマッチング関数のうちのいずれか一方が使用されることを特徴とする、請求項６に記載の方法。８．前記新入力画像および前記基準テンプレートが、前記書き込まれたテンプレートの内容から前記基準テンプレートの線を分離するためのテンプレート除去の入力として使用されることを特徴とする、請求項１、請求項２、請求項３または請求項４に記載の方法。９．プロセッサと、基準テンプレート画像および入力された書き込まれたテンプレート画像を記憶するための記憶装置とを含む、前記基準テンプレート画像と前記入力テンプレート画像とを位置合せするための装置であって、前記基準テンプレート画像内の線および前記書き込まれたテンプレート画像内の線の１方向への射影の対応する対を見つけることによって、前記基準テンプレート画像内の前記線と前記書き込まれたテンプレート画像内の前記線とを相関させる手段と、前記射影の方向に垂直な方向での前記対のそれぞれの線の２つの射影の変位を決定し、前記射影の対の間で一致を達成するために前記書き込まれたテンプレート画像の各線の画素をシフトしなければならない行または列の数を評価する手段と、変位を決定する手段によって決定された通りに、前記射影の方向に垂直に、前記書き込まれたテンプレート画像の線の画素をシフトすることによって、新入力画像を生成する手段とを含む微細位置合せユニットをさらに含むことを特徴とする装置。１０．さらに、請求項９の相関手段によって選択された射影の方向に垂直な方向の射影を用いて、前記基準テンプレート画像内および前記新入力画像内の線の射影の対応する対を見つけることによって、前記基準テンプレート画像内の前記線と前記新入力画像内の前記線とを相関させる手段と、請求項９の相関手段によって選択された前記射影の方向に平行な方向での前記対のそれぞれの線の２つの射影の変位を決定し、前記射影の対の間で一致を達成するために前記新入力画像の各線の画素をシフトしなければならない行または列の数を評価する手段と、決定された変位を使用して、請求項９の相関手段によって選択された前記射影の方向に平行に、前記書き込まれたテンプレート画像の線の画素をシフトすることによって、新入力を含む、請求項９に記載の装置。１１．前記基準テンプレート画像を複数の画素列を有する基準バンドに分割し、前記書き込まれたテンプレート画像を複数の画素列を有する対応する入力バンドに分割する手段を含む、請求項９に記載の装置。１２．前記基準テンプレート画像を複数の画素行を有する基準バンドに分割し、前記書き込まれたテンプレート画像を複数の画素行を有する対応する入力バンドに分割する手段を含む、請求項１０に記載の装置。１３．さらに、テンプレート除去のための手段を含む、請求項９、請求項１０、請求項１１または請求項１２に記載の装置。