(57)【特許請求の範囲】
【請求項１】
剪断変形画像部分を持つ２つの画像断片をレジストレーションし、回転パラメータと第１及び第２の移動パラメータを持つ変換を結果として得る画像レジストレーション方法であって、該変換は回転と、第１及び第２の軸に沿った２次元の移動を記述し、第１の画像断片に適用された時に、第１の画像断片の剪断変形部分を第２の画像断片の対応した剪断変形部分へ写像するものであり、
第１の画像断片を表す第１の２次元２進数配列を入力するステップ、
第２の画像断片を表す第２の２次元２進数配列を入力するステップ、
第１の２次元２進数配列の第１の軸に射影された第１の射影ヒストグラムを生成するステップ、
第２の２次元２進数配列の第２の軸に射影された第２の射影ヒストグラムを生成するステップ、
試しの回転パラメータ及び試しの移動パラメータを第１の射影ヒストグラムに適用して回転及びシフトされた射影ヒストグラムを生成し、回転及びシフトされた射影ヒストグラムを第２の射影ヒストグラムと比較することにより試し回転パラメータ及び試し移動パラメータでの誤差距離を求め、最小の誤差距離を持つ回転及びシフトされた射影ヒストグラムの回転パラメータ及び移動パラメータを変換の回転パラメータ及び第１の移動パラメータに選ぶことによって、回転パラメータ及び第１の移動パラメータの最適値を決定するステップ、
第１及び第２の画像断片中の一方を固定画像断片に選び、他方を浮動画像断片に選ぶステップ、
回転パラメータ及び第１の移動パラメータによって浮動画像断片を固定画像断片に対し変換して中間画像断片を生成するステップ、及び
中間画像断片を固定画像断片にレジストレーションして第２の移動パラメータを求めるステップからなる画像レジストレーション方法。
【請求項２】
請求項１記載の画像レジストレーション方法において、第１の画像断片は固定画像断片であり、第２の画像断片は浮動画像断片であることを特徴とする画像レジストレーション方法。
【請求項３】
請求項１記載の画像レジストレーション方法において、第１の軸は垂直軸であって、水平射影ヒストグラムが得られることを特徴とする画像レジストレーション方法。
【請求項４】
請求項１記載の画像レジストレーション方法において、画像断片は多値画像であり、画像断片を閾値処理することにより２進数配列値を得るステップをさらに有することを特徴とする画像レジストレーション方法。
【請求項５】
請求項１記載の画像レジストレーション方法において、画像断片は第２の軸に平行なラインに沿って符号化されたランレングス符号化ストリームとして記憶され、射影ヒストグラムを生成するステップは各ライン毎に注目色のランレングスを加算するステップからなることを特徴とする画像レジストレーション方法。
【請求項６】
請求項５記載の画像レジストレーション方法において、ラインは１画素高さの水平行又は１画素幅の垂直列であることを特徴とする画像レジストレーション方法。
【請求項７】
請求項１記載の画像レジストレーション方法において、配列は白画素及び黒画素を表す２進数値からなり、射影ヒストグラムは各ラインの黒画素数のヒストグラムであることを特徴とする画像レジストレーション方法。
【請求項８】
請求項１記載の画像レジストレーション方法において、ヒストグラムを回転させるステップは、第１の画像断片の幅に回転角度の正接を掛けたものの関数である分布範囲を決定するステップ、及び、ヒストグラム内の各行の黒画素を、前記決定された分布範囲に均等に配分するステップからなることを特徴とする画像レジストレーション方法。
【請求項９】
請求項１記載の画像レジストレーション方法において、ヒストグラムを回転させるステップは、射影ヒストグラムに基づいて、射影軸に対し垂直な各ラインに画素値が均等に分配され、かつ回転しようとする射影ヒストグラムと等しい射影ヒストグラムを持つ仮の画像断片をシミュレートするステップ、仮の画像断片を回転させるステップ、及び、仮の画像断片から、回転された射影ヒストグラムを生成するステップからなることを特徴とする画像レジストレーション方法。
【請求項１０】
請求項１記載の画像レジストレーション方法において、誤差距離はヒストグラム値間の差の２乗和であることを特徴とする画像レジストレーション方法。
【請求項１１】
最小の誤差距離を、それを超えたら２つの画像断片がうまくレジストレーションされていないと考えられる誤差距離である固定閾値と比較するステップ、及び、レジストレーションが達成されないときに、第１の画像断片と第２の画像断片との間のポイントマッチングにより変換を決定するステップをさらに有することを特徴とする請求項１記載の画像レジストレーション方法。
【請求項１２】
請求項１１記載の画像レジストレーション方法において、ポイントマッチングにより変換を決定するステップは、開始点として、最小の誤差距離を持つ回転された射影ヒストグラムの回転パラメータ及び第１の移動パラメータを選ぶステップの結果を利用することを特徴とする画像レジストレーション方法。
【請求項１３】
請求項１記載の画像レジストレーション方法において、小さい誤差距離を持つ変換候補が複数求まった場合、該複数の変換候補より最良の変換を選択するステップをさらに有することを特徴とする画像レジストレーション方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文書処理の分野に関し、特に、射影ヒストグラムマッチングによる画像レジストレーションの分野に関する。
【０００２】
【従来の技術】
レジストレーションは、同一オブジェクトの２つの画像断片を整列させるプロセスであり、一般に、いくつかの画像断片を整列させて、一つの大きな画像全体を得るために利用される。画像レジストレーションには、航空写真のモザイクの組み立て、３次元モデル建造物の立体画像処理、目標認識、医療診断、文書のマルチパス読み取りや複写等、多くの用途がある。
【０００３】
２つの画像相互のレジストレーションを手作業で行うには、それら画像の重複する部分を整列させればよい。これを行うために、人間は両方の画像を見て、一方の画像の端近傍の特徴と他方の画像中の同じ特徴を目で見つけ、それに従って２つの画像を整列させる。手作業によるレジストレーションは多くの欠点があるが、その一つが面倒で手間がかかることがある。
【０００４】
自動画像レジストレーションシステムは、２つのデジタル化画像断片を入力として受け取り、一方の画像断片のポイントを他方の画像断片中の対応ポイントへ写像する変換Ｔのパラメータを出力する。いくつかの自動画像レジストレーション法が知られている。例えば、Ｌ.Ｇ.Ｂrown，”Ａ  Ｓurvey  of  Ｉmage  Ｒegistration  Ｔechniques，”ＡＣＭ  Ｃomputing  Ｓurveys  24，4（Ｄecember  １９９２），PP.３２５−３７６を参照されたい。レジストレーション法の主要なものに、相関法、ポイント・マッピング法、フーリエ法、エラスティック・モデルベース・マッチング法がある。利用するレジストレーション法は、一般に、具体的な用途、予期される変換のタイプ及びノイズに基づいて選ばれる。
【０００５】
２つの画像Ｉ1，Ｉ2のレジストレーションをする一従来方法は、次式で記述される正規化相互相関と呼ぶ尺度を用いる。
【０００６】
【数１】
0003841321.tif 000002
【０００７】
この正規化自己相関Ｃは、画像Ｉ1を画像Ｉ2に対しｘ方向にｕだけ、ｙ方向にｖだけ移動させた時に、２つの画像Ｉ1，Ｉ2が相互に整合する度合を示す尺度である。そのような移動の都度、２つの画像の積が計算される。この正規化自己相関が最大値となるのは、その２つの画像が、その一方が他方に精密に整合するように移動された時である。このような方法を用いる文書画像レジストレーションアルゴリズムは正確な結果を得ることができるが、それには正規化自己相関の計算に相当な実行時間を必要とする。すなわち、各候補移動毎に２次元画像間の積を計算しなければならない。さらに、本方法は画像間の相対的な回転を考慮に入れない。
【０００８】
本方法は、相当な計算コストがかかることに加え、特徴ポイントが計算される間、それら画像中の少なくと１つの画像の全体をメモリに格納しておく必要があるため、かなりのメモリコストもかかる。したがって、畳み込みマスクによる局所的特徴ポイントを検出する必要がなく、かつ、一つの画像全体を格納するためのメモリを必要としないレジストレーション法の開発が望まれる。
【０００９】
従来技術のある画像レジストレーションシステムはハイブリッド（hybrid）アプローチを用いる。例えば、米国特許出願第０８／５２７，８２６号（１９９５年９月１３日受理）”Ｓimultaneous  Ｒegistration  of  Ｍultiple  Ｉmage  Ｆragments”を参照されたい。ハイブリッド・アプローチの場合、ユーザは、文書の複数のスキャン画像を提示され、そしてドラッグ・アンド・ドロップのインターフェイスを用い手作業で、おおまかなレジストレーションを与える。次に、レジストレーションシステムは、整列はかなり正確であると仮定して、重なり合った画像断片を処理する。ユーザがおおまかな整列を与える効果は、可能な変換の数を減らしてレジストレーションを迅速化することである。しかし、このハイブリッド・アプローチでも人手を介入させなければならない。
【００１０】
以上のことから、改良された自動画像レジストレーションシステムが必要であることが分かる。
【００１１】
【発明が解決しようとする課題】
よって、本発明の目的は、処理に必要な計算量及びメモリ量を大幅に削減可能な改良された自動画像レジストレーション方法を提供することである。本発明のもう一つの目的は、２値画像のみならず多値画像にも適用できる改良された自動画像レジストレーション方法を提供することにある。
【００１２】
【課題を解決するための手段】
本発明によれば、剪断変形画像部分を持つ２つの画像断片をレジストレーションし、回転パラメータと第１及び第２の移動パラメータを持つ変換を結果として得る画像レジストレーション方法が提供される。ここで、該変換は回転と、第１及び第２の軸に沿った２次元の移動を記述し、第１の画像断片に適用された時に、第１の画像断片の剪断変形部分を第２の画像断片の対応した剪断変形部分へ写像するものである。この画像レジストレーションは、第１の画像断片を表す第１の２次元２進数配列を入力するステップ、第２の画像断片を表す第２の２次元２進数配列を入力するステップ、第１の２次元２進数配列の第１の軸に射影された第１の射影ヒストグラムを生成するステップ、第２の２次元２進数配列の第２の軸に射影された第２の射影ヒストグラムを生成するステップ、（ａ）試しの回転パラメータ及び試しの移動パラメータを第１の射影ヒストグラムに適用して回転及びシフトされた射影ヒストグラムを生成し、（ｂ）回転及びシフトされた射影ヒストグラムを第２の射影ヒストグラムと比較することにより試し回転パラメータ及び試し移動パラメータでの誤差距離を求め、（ｃ）最小の誤差距離を持つ回転及びシフトされた射影ヒストグラムの回転パラメータ及び移動パラメータを変換の回転パラメータ及び第１の移動パラメータに選ぶことによって、回転パラメータ及び第１の移動パラメータの最適値を決定するステップ、第１及び第２の画像断片中の一方を固定画像断片に選び、他方を浮動画像断片に選ぶステップ、回転パラメータ及び第１の移動パラメータによって浮動画像断片を固定画像断片に対し変換して中間画像断片を生成するステップ、及び、中間画像断片を固定画像断片にレジストレーションして第２の移動パラメータを求めるステップからなる。
【００１３】
この方法の一実施例によれば、第１の画像断片より水平射影ヒストグラムが計算され、それが第２の画像断片より計算された水平射影ヒストグラムと比較される。この２つのヒストグラムを”整列する”まで操作することにより、変換の回転（θ）パラメータと垂直移動（ｙ）パラメータが求められる。これらの２つのパラメータが分かったならば、画像断片を相互に水平方向にスライドさせることによって、水平移動（ｘ）パラメータは容易に算出される。一変形例では、垂直ヒストグラムを用いて回転と水平移動が最初に求められる。操作されるのはヒストグラムであって画像断片の全体ではないので、画像レジストレーションの実行のために必要な計算量とメモリが非常に少なくてすむ。変換の回転角度を求めるために画像を回転させるのではなく、”ヒストグラム回転”変換によりヒストグラムが変換される。画像レジストレーションの用途が画像断片の大角度の相対回転を予期しないようなものであれば、ヒストグラム回転及び整列プロセスで十分である。画像断片が大きな角度回転している、すなわち画像断片がヒストグラム回転アプローチに従わない可能性がかなりある場合には、画像レジストレーションシステムは、ヒストグラム回転変換プロセスがロックに至ることができないときに、もっと強力な画像レジストレーション処理を行うバックアッププロセスを含んでもよい。
【００１４】
各行が一連のランレングスによって記述されるランレングス符号化（ＲＬＥ）圧縮データを扱うシステムにおいては、画像を完全に伸長することなく水平ヒストグラムを生成できる。これは、ヒストグラムに含めようとする画素色について、各ランレングス中の画素の数をカウントすることによって達成される。普通、ヒストグラムは行毎に黒画素の数をカウントする。
【００１５】
ヒストグラム回転は、２つ又はそれ以上の画像断片を整列させるのに有効であるが、相当数の平行したオブジェクト、例えば線図形や文字行からなる画像のスキュー角度の測定にも有効である。本発明によれば、ヒストグラム回転をスキュー検出に利用することができる。例えば、スキュー角度を測定するために、ヒストグラムを生成し、それをシャープネス・ファクタ（sharpness  factor）を最大にするように回転させ、シャープネス・ファクタが最大となった回転後ヒストグラムの角度がスキュー角度と推定される。
【００１６】
明細書の以下の部分及び添付図面を参照すれば、本発明の性質及び利点はより明確になろう。
【００１７】
【発明の実施の形態】
本発明を実現するための好適実施例を説明するが、初めにいくつかの用語の定義を説明する。
【００１８】
当該技術分野において周知のように、デジタル化画像は画素値の２次元配列によって表現できる。２値画像は、２つの可能な画素値だけが表される画素配列によって表現された画像である。２値画像中の各画素値は、”０”又は”１”の値をとるとみなすことができる。２値画像が白黒画像の場合、”０”は白画素を、”１”は黒画素を表すであろう。ここでは、そのような画素値の組合せを用いて本発明を説明する。しかし、画素の色は任意であり、例えば赤と青の画素からなる２値画像を指すことさえあるかもしれない。画像断片は白の背景に画像特徴（文字、線、ドットなど）が黒画素で描かれた２値画像であると仮定し、説明する。
【００１９】
本発明は、画素が３つ以上の値からなる集合中の１つの値をとることができるような多値画像、例えば２４ビット・カラー画像にも有効である。多値画像は同じ大きさの２値画像に比べ様々な処理段階でより多くの計算を必要とするであろうから、多値画像より２値画像を生成し、多値画像はセーブしておき、代わりに２値画像を操作するのがしばしば望ましい。その後、２値画像のレジストレーションを利用して、セーブしておいた多値画像のレジストレーションをすることができる。したがって、２値画像に関して本発明を説明しても一般性を損なうことはない。
【００２０】
画像レジストレーションは、２つの画像断片が重複している場合すなわち共通の特徴を持っている場合に、それらを整列させるプロセスである。例えば、ある都市を完全に表すための複数ページ（画像断片）を有する地図帳は、各地図ページを隣り合った地図ページと重複させているであろう。その都市のより大きな切れ目のない１枚の地図が必要とされる場合、そのような地図は、画像レジストレーションプロセスで隣接画像ページの共通した重複部分を利用して隣接地図ページを整列させることによって、作ることが出来るだろう。ここに用いられるように、”フル”画像とは、画像断片をレジストレーションして組み立てることによって得られる画像を指す。十分に大きな重複領域が与えられることを一般に想定しているが、最小の重複（３００ドット／インチで１インチ以下）が与えられる場合にも本発明は有効に作用する。
【００２１】
画像断片は、フル画像を載せるのが非現実的な地図帳に用いられる。画像断片が撮影されるアパーチャよりフル画像が大きい場合、例えば、大きな図面を何回かに分けて写真複写する必要がある時、あるいは、景色の写真撮影をしたいが多数の重複した航空写真が必要な場合にも、画像断片が使用される。言うまでもなく、画像断片が重複していさえすれば、つまり、画像断片が一方の画像から他方の画像へレジストレーションすることができる識別可能な特徴を持つ共通部分を有する限り、画像断片がどのようにして作られたかに関係なく、画像レジストレーションは有効に働く。
【００２２】
３つ以上の画像断片を同時にレジストレーションすることもできるが、本明細書を読めば、３つ以上の画像断片のレジストレーションは逐次的に行うことができること、すなわち、第１の画像断片を第２の画像断片にレジストレーションして、より大きな中間画像断片とし、この中間画像断片に第３の画像断片をレジストレーションし、というようにして可能であることが明らかになろう。簡明にするため、以下において、２つの画像断片のレジストレーションに適用する場合についてのみ本発明を説明する。
【００２３】
実際的には、画像断片は座標空間に、より正確には座標平面に配置される。一般に、座標平面上の各画像断片の位置は、画像がどのように作成されるかによって決まる。例えば、２つの画像断片がコピアのスキャン画像であり、８．５"×１１"のアパーチャにより６００ｄｐｉで読み取られ５１００画素×６６００画素の画素配列となる場合には、第１の画像断片の左上コーナーの位置は（０，０）、第２の画像断片の左上コーナーの位置は（５１００，０）となるであろう。それら２つの画像断片に画像レジストレーションプロセスを適用した結果は、それら画像断片を整列させるために座標平面上で第２の画像断片を第１の画像断片に対してどれだけ動かすべきかを記述する式でもよいし、２つの画像断片の継ぎ目のない結合をあらわす一つのより大きな画像でもよい。結果が式であれば、第２の画像断片を第１の画像断片に接合させるための変換は単純なプロセスである。
【００２４】
この第２画像断片を整列させる式は、本明細書では変換Ｔと呼ぶ。第２の画像断片を移動させて第１の画像断片に整合させるようにしたのは、たまたまそのように選んだのであり、それと逆の変換なら、第１の画像断片が第２の画像断片と整列するように移動させられることは明白であろう。その区別が本発明の説明に関係がある場合には、移動させられる画像断片を”浮動”画像断片と呼び、他方の画像断片を”固定”画像断片と呼ぶ。最も一般的なケースでは、変換Ｔは回転、２方向の移動（Ｘ，Ｙ）、２方向の変倍（Ｓｘ，Ｓｙ）、及び２方向の剪断変形（Ｓｈｘ，Ｓｈｙ）からなる。典型的な用途では、スキャン画像はすべて同一平面に作られるため、変倍は１：１であり、剪断変形は存在せず、したがって変換をＴ（θ，ｘ，ｙ）で表現すれば十分である。
【００２５】
ここで、座標平面上の座標はＸ軸座標及びＹ軸座標により記述される。簡単にするため、Ｘ方向及びＹ方向の座標は画素の単位で計量されるが、変換は整数個の画素である必要はない。浮動画像断片が非整数個の画素の変換により変換される場合には、画素は整数座標にしか出現できないという事実があるので、エイリアシング(aliasing)等の周知の近似手法が用いられる。
【００２６】
以上の条件であるならば、画像レジストレーションの課題は、ある座標平面上で２つの画像断片を調べ、その画像平面上でその２つの画像断片の整列をもたらす変換パラメータθ，ｘ，ｙを求めることである。
【００２７】
図１は、ヒストグラム回転のプロセスと、それが本発明でどのように利用されるかを説明するものである。２つの画像断片１０(1)，１０(2)が示されている。この２つの画像断片は同一の画像断片であるが、それぞれ相対的に２度だけ回転しており、また、図示のように平行移動している点が相違する。それぞれの画像断片が水平軸に射影されてもよい。図式的には、ヒストグラムは、画像のすべての黒画素を、他の黒画素とオーバーラップさせないで、つまり列位置を変えずに、画像のボトムまでスライドさせたものに相当する。画像断片１０(1)，１０(2)の射影をとることによりヒストグラム１２(1)，１２(2)がそれぞれ得られる。図４に関連して説明する如く、ヒストグラム１２(1)の２度の”回転”により、回転ヒストグラム１２(1)’が得られる。回転ヒストグラム１２(1)’をヒストグラム１２(2)と比較することにより、２度が画像断片１０(1)，１０(2)相互の正確な回転量であるか判定する。
【００２８】
図２に、本発明による画像レジストレーションの方法が示されている。図２において、ステップはそれぞれ符号（Ｓ１，Ｓ２等々）が付けられており、ステップは特に指示されない限り符号順に実行される。ステップＳ１で、２つの圧縮画像断片ＩＦ１，ＩＦ２が読み込まれる。ＩＦ１は任意に固定画像断片に選ばれ、ＩＦ２は任意に浮動画像断片に選ばれる。
【００２９】
ステップＳ２において、ＩＦ１の水平ヒストグラムＨ１とＩＦ２の水平ヒストグラムＨ２が生成される。２次元の２値画像配列の水平ヒストグラムは、２値画像の各画素行に対し１つのエントリーを持つ、２値画像配列の画素数を示す値の１次元配列にすぎずない。このヒストグラムを黒画素に関するヒストグラムであるとすれば、ヒストグラム配列の第ｉエントリーは２値画像の第ｉ行中の黒画素数である。垂直ヒストグラムも同様に生成されるが、その画素数が各列中の画素数である点が異なる。
【００３０】
画像断片がランレングス符号化により圧縮されている場合には、ヒストグラムを生成するする必要はない。その理由を具体例によって説明する。画像断片が１６列幅で、ある行が”0100111110010000”という画素を持っているとする。その圧縮画像では、当該行は”０１１２５２１４”というように表現されるであろう。ここで、最初の数字は当該行の最初の画素の色を示し、それ以降の数字はすべて当該行の各ランの画素数を示す。その圧縮前の行から、当該行は７個の黒”１”画素を持つことがすぐ分かる。ヒストグラムの当該行に対応するエントリーの場合、圧縮表現”01125214”さえ分かれば、２番目の”１”より初めて１つ置きに数字を加算することにより黒画素の数が求まり（最初の”０”は最初の”１”が１個の白画素からなるランであることを意味する）、その結果は１＋５＋１つまり７となる。
【００３１】
ステップＳ３において、変換パラメータθi，ｙiに関し初期推定が行われる。このステップで、（θi,ｙi）ペアのサーチ空間も決定してもよいであろう。論理的には、誤差距離を保持するため２次元配列ＥＤ[][]がセットアップされるが、その内容については後述する。
【００３２】
ステップＳ４において、Ｈ２がθiだけ”回転”させられ、回転ヒストグラムが生成される。ヒストグラムを回転させる方法は、図４に関連して後述するが、角度θi回転されたＩＦ２の回転からヒストグラム生成をシミュレートする方法である。
【００３３】
ステップＳ５において、Ｈ２がｙiだけシフトされる。好ましくは、サーチ空間内のｙの値は、ｙiを含め、整数であるので、Ｈ２を平行移動させることは、初期インデックスをＨ２のための値を格納している１次元配列に変換するのと同じくらい簡単である。しかし、非整数をｙiとして用いてもよい。Ｈ２が（ｙi＋ａ）だけシフトされると、Ｈ２の特定のセルはその値を（１−ａ）ｙi＋ａｙi（ただし０＜ａ＜１）より取得する。
【００３４】
ステップＳ６において、Ｈ２がＨ１と比較され、誤差距離が計算される。様々な誤差距離のどれを用いてもよい。一実施例では、誤差距離はＨ２とＨ１の対応行間のヒストグラム値の差の２乗和である。これは次式で表される。
【００３５】
【数２】
0003841321.tif 000003
【００３６】
ここで、Ｌは（画像断片並びにヒストグラム配列の）行数である。簡単にするため、画像断片ＩＦ１，ＩＦ２それぞれの行数は同じであると仮定する。行数が異なる場合、Ｈ１，Ｈ２が同数のエントリーつまりＬ個のエントリーを持つように、レジストレーションプロセスの間、行が便宜無視される。例えば、（２）式の指数を２以外の数に置き換えた式など、他の誤差式を用いてもよい。
【００３７】
誤差距離が計算されたならば、それは配列ＥＤのＥＤ[θi][ｙi]で指定される位置に格納される。ステップＳ７において次の（θ，ｙ）ペアが取得され、各（θ，ｙ）ペアについて誤差距離が計算されるまではプロセスはステップＳ４へループバックする。
【００３８】
すべての誤差距離が計算されたならば、画像レジストレーションプロセスはステップＳ８に進み、配列ＥＤより最小の誤差値が見つけられる。そして、その最小誤差値の配列インデックスである（θ，ｙ）ペアが、変換Ｔの回転パラメータ及び垂直移動パラメータとして利用される。あるいは、最初の誤差距離測定セットの結果を利用して遂行すべき（θ，ｙ）ペアを選べば、サーチプロセスはより迅速に終わるかもしれない。
【００３９】
いずれの方法によるにしても、最小誤差距離のインデックスが見つかった後、画像レジストレーションプロセスは先に進む。複数の誤差距離値が最小値に近い場合、２つ以上の候補（θ，ｙ）ペアを後続のステップへ持ち越し、もっと先のあるステップで最適な１つに絞り込んでもよい。ここで説明しているプロセスでは、当該ステップにおいて最適な（θ，ｙ）ペアが１つだけ選ばれたとする。
【００４０】
ステップＳ９で、後述のように画像レジストレーションの”ロック”（lock）の判定が行われる。ロックが検出されたならば、プロセスはステップＳ１０に進み、ＩＦ２が部分変換Ｔp＝Ｔ（θ，０，ｙ）によって変換されて、ステップＳ８で決定されたパラメータから新たな画像断片ＩＦ２'を生成する。
【００４１】
ステップＳ１１において、画像断片ＩＦ１，ＩＦ２'に対する垂直ヒストグラムＶ１，Ｖ２がそれぞれ生成され、そしてステップＳ１２において、水平移動パラメータｘの最適値を決定するため垂直ヒストグラムＶ１，Ｖ２が相対的にシフトされる。ここでの説明から明らかなように、同じ目的のために、ＩＦ２をＩＦ２'に変換する代わりに、ＩＦ１をＴpにより変換してＩＦ１'を生成してもよい。
【００４２】
ステップＳ１３において、画像レジストレーションプロセスは、ＩＦ２をＩＦ１と整列するように変換するであろうθ，ｘ，ｙの決定値を出力する。明らかなように、ＩＦ１とＩＦ２は交換可能であり、パラメータの符号が矛盾しないかぎり、どちらの画像断片を選んで変換してもよい。
【００４３】
変換パラメータが出力されたならば、図２に示されていない若干の後続ステップを実行することができる。例えば、画像レジストレーションプロセスがマルチパス（multi-pass）コピアに関連して実行される場合、記憶された複数の画像断片を操作して単一のレジストレーション後画像として印刷することができる。この単一のレジストレーション後画像は文字認識プロセスのための入力データとして用いられるかもしれない。ここに開示した内容を具体的な用途に適用することにより、変換パラメータ及び画像断片の他の用途が明らかになろう。
【００４４】
ある種の用途では、画像断片はステップＳ８で起こるロックに非常に従順である。ロックが起こるのは、画像断片の正確なレジストレーション位置に近いインデックスが見つかった時である。ロックは最小誤差距離を閾値と比較することによって検出され、この場合、最小誤差距離が閾値より小さい時にロックが起こったとみなされる。黒画素がカラムを横切って非常に不均一に分布する異形のアンバランスな図形は、ロックしにくいかもしれない。そのような画像断片がよく出現する場合には、本発明のハイブリッド型実施例が有効かもしれない。このようなハイブリッド型実施例では、ステップＳ９で画像断片のロックが判定され、ロックが全く検出されないときには、ステップＳ１４で画像断片ＩＦ１，ＩＦ２に対し在来の画像レジストレーションが実行される。ステップＳ１４の結果、３つの変換パラメータがすべて分かるので、プロセスはステップＳ１３に進み、それらパラメータが出力される。
【００４５】
本発明による画像レジストレーションのプロセスを全般的に説明した。ここで図３を参照し、画像レジストレーションを実行するための装置を示し説明する。ここに示す装置は、レジストレーション・プロセッサ２０と画像アライナー（aligner）２２からなる。２つの画像断片２４(1)，２４(2)がレジストレーション・プロセッサ２０に対する入力として示されており、これら画像断片は一般的に２次元画素値配列２５(1)，２５(2)として記憶されている。これらの画像断片２４は、それより大きな画像２６の断片であり、スキャナ２８又はデジタルカメラ３０により画像２６を複数回スキャンした結果かもしれない。様々なエレメント間の信号の相互接続も図３に示されているが、それについては装置の動作によって説明する。
【００４６】
図３に示された動作は次の通りである。画像２６を４回スキャンして画像断片２４(1)〜２４(4)を得る。そして、レジストレーション・プロセッサ２０と画像アライナー２２を利用して、それら画像断片中の２つの画像断片２４(1)，２４(2)を結合して、それより大きな１つの画像２４'とする。この画像２４'を次にフィードバックして、画像断片２４(3)，２４(4)のような他の画像と結合させることができる。
【００４７】
２つの画像断片は、レジストレーション・プロセッサ２０に入力されるとともに、画像アライナー２２にも入力される。レジストレーション・プロセッサ２０は、その入力に基づいて、４つの信号を、典型的にはデジタル値として出力する。これらの４つの信号は、ブーリアン妥当性信号（Ｖ）と、回転パラメータ（θ）、垂直移動パラメータ（ｙ）、水平移動パラメータ（ｘ）である。この４つの信号はほぼ、図２に示した画像整列プロセスに関連して説明したように生成されるが、妥当性信号ＶはステップＳ９（図２参照）でロックが検出されたか否かを示す。これらの信号は画像アライナー２２に出力され、画像アライナー２２はそれらの信号を利用して画像断片２４(1)，２４(2)から画像断片２４'を生成する。妥当性信号Ｖがロックが検出されなかったことを指示するときには、画像アライナー２２は在来の画像レジストレーションプロセスを実行して画像断片２４'を生成する。
【００４８】
望むならば、画像断片２４'を別の画像断片とともにレジストレーション・プロセッサ２０に対する入力として利用して、より大きな画像断片を生成し、最終的に、すべての画像断片をレジストレーションして画像２６を再現することができる。
【００４９】
レジストレーション・プロセッサ２０及び画像アライナー２２として利用されるハードウエアは、それらの機能に拘束されない。レジストレーション・プロセッサ２０及び画像アライナー２２は、専用のハードウエア、すなわち特別に設計された集積回路チップまたはチップの集合によって実現してもよいし、あるいは、完全にソフトウエアによって、すなわち、ここに述べたことに従ってプログラムされた一般的なデジタルコンピュータによって実現してもよい。
【００５０】
図４は、ヒストグラムを回転させるプロセスを説明するものである。図４（ａ）は１つの行だけが黒画素を含んでいる画像のヒストグラムを表している。この画像は、図示しないが、最上部の行１から最下部の行ＬまでのＬ個の行がある。黒画素を有する１つの行は行Ｒであり、これはＮ個の黒画素を持っているのでヒストグラムのビンＲは値Ｎを持ち、その他のビンはすべて０である。図４（ｂ）に示すように、図４（ａ）のヒストグラムを回転させるということは、そのヒストグラムの行Ｒ中のＮ画素をＷ＊ｔａｎ（θ）の範囲に分散させるプロセスにすぎない。ここで、Ｗは画像の幅である。明らかな如く、Ｎ個の黒画素が行Ｒ内に均等に分布しているならば、結果として得られる回転ヒストグラムは、画像を同じ角度回転し回転後の画像からヒストグラムを求めた場合に得られるであろうヒストグラムと同じものである。ヒストグラムのビンに非整数値が許されるときには、Ｎ個の画素をビンＲとＲ−Ｗ＊ｔａｎ（θ）に最も近いビンの間のビンに均等に配分すればよい。非整数値が許されないときには、それら画素を可能な限り均等に分配すればよい。
【００５１】
このヒストグラム回転法は、画像の全画素をあるエッジに移動させてから画像を剪断変形させることと等価である。望むならば、Ｒ＊ｃｏｓ（θ）に最も近いビンとＲ＊ｃｏｓ（θ）−Ｗ＊ｓｉｎ（θ）に最も近いビンの範囲に画素を分配するような、画像回転のより精密なシミュレーションを行ってもよい。
【００５２】
＜実験結果＞
市街地地図からとった図５に示すような画像断片に対しヒストグラム回転を適用した。レジストレーションの回転と垂直移動のパラメータ（θ，ｙ）は、規則的ポイントマッチングによれば（−１．３゜，−７画素）、ヒストグラムマッチングによれば（−１．１゜，−６画素）となった。
【００５３】
以上に述べたことは例示的なものであって、それに限定されるものではない。本明細書の内容を詳しく読めば、当業者には本発明の多くの変形が明らかになろう。本明細書に述べたことは３次元の画像断片レジストレーションにも適用できるであろう。
【００５４】
【発明の効果】
以上の説明から明らかなように、本発明の画像レジストレーション方法は、人手の介入を要することなく自動的に画像のレジストレーションが可能であり、また、画像を操作する代わりに射影ヒストグラムを操作するため、処理に必要な計算量及び量を大幅に減らすことができ、さらに多値画像のレジストレーションにも適用可能である。
【図面の簡単な説明】
【図１】  ヒストグラム回転のプロセスとその利用の説明図である。
【図２】  本発明による画像断片レジストレーションプロセスのフローチャートである。
【図３】  本発明による画像レジストレーションシステムのブロック図である。
【図４】  ヒストグラムの１つのビンを回転させるプロセスを説明するための図である。
【図５】  相互にレジストレーションが可能な２つの画像断片の実例を示す図である。
【符号の説明】
１０(1)，１０(2)  画像断片
１２(1)，１２(2)  水平射影ヒストグラム
１２’  回転された水平射影ヒストグラム
２０  レジストレーション・プロセッサ
２２  画像アライナ
２４(1)〜２４(4)  画像断片
２４’  ２つの画像断片を結合した中間画像断片
２５(1)，２５(2)  画像断片の２次元画素値配列
２６  画像
２６’  再現画像
２８  スキャナ
３０  デジタルカメラ
【図１】
0003841321.tif 000004
【図２】
0003841321.tif 000005
【図３】
0003841321.tif 000006
【図４】
0003841321.tif 000007
【図５】
0003841321.tif 000008