(57)【特許請求の範囲】
【請求項１】
デジタル画像整列システムにおいて、完全な画像の３つ以上のオーバーラップした画像断片を最適に継ぎ合わせ該完全な画像を復元する装置であって、
該３つ以上の画像断片中の２つ以上のオーバーラップした画像断片間の整列誤差を、第１の予め決めた基準に従って測定する手段、
該２つ以上の画像断片中の選択された２つのオーバーラップした画像断片間の整列を、それら画像断片間の整列誤差を減らすよう精密調整する精密調整手段、
該予め決めた基準に従って該３つ以上の画像断片のすべてのオーバーラップするペア間の総整列誤差を累積する、該測定手段と結合された累積手段、
及び
該オーバーラップした画像断片の連続したペアに対し該精密調整手段を繰り返し適用して該総整列誤差を最適化する、該累積手段及び該精密調整手段と結合された全体最適化手段を具備する画像断片継ぎ合わせ装置。
【請求項２】
請求項１記載の画像断片継ぎ合わせ装置において、該第１の予め決めた基準はＬ１ノルムであることを特徴とする画像断片継ぎ合わせ装置。
【請求項３】
請求項１記載の画像断片継ぎ合わせ装置において、該第１の予め決めた基準は相互相関スコアであることを特徴とする画像断片継ぎ合わせ装置。
【請求項４】
請求項１記載の画像断片継ぎ合わせ装置において、該全体最適化手段は、該画像断片のオーバーラップした各ペアに対し、該累積手段により測定される該総整列誤差が向上しなくなるまで、該精密調整手段を繰り返し適用させる手段を含むことを特徴とする画像断片継ぎ合わせ装置。
【請求項５】
請求項１記載の画像断片継ぎ合わせ装置において、該精密調整手段は、該正確に２つの画像断片中の第１の画像断片内のオーバーラップ領域において、該正確に２つの画像断片中の第２の画像断片の領域とマッチングするための複数の重要点を検出する重要点検出手段を含むことを特徴とする画像断片継ぎ合わせ装置。
【請求項６】
請求項５記載の画像断片継ぎ合わせ装置において、該重要点検出手段は、該第１画像断片内の該オーバーラップ領域の画素に対し分散オペレータを適用する手段を含むことを特徴とする画像断片継ぎ合わせ装置。
【請求項７】
請求項５記載の画像断片継ぎ合わせ装置において、該重要点検出手段は、１）該第１画像断片内の該オーバーラップ領域上にセルの格子を重ねる手段、２）該第１画像断片内の該オーバーラップ領域の各画素に対し分散オペレータを適用して重要度レベルが予め定めた閾値を超える画素を検出する手段、３）重要度レベルが予め定められた閾値を超える画素を含むそれぞれの該セル内の最大の重要度を持つ画素を重要点候補として選ぶ手段、４）該重要点候補中の最大の重要度レベルを持つ重要点候補を第１の重要点として選ぶ手段、及び、５）該重要点候補中の該第１の重要点から最も遠い重要点候補を第２の重要点として選ぶ手段を含むことを特徴とする画像断片継ぎ合わせ装置。
【請求項８】
請求項５記載の画像断片継ぎ合わせ装置において、該精密調整手段は、該複数の重要点のそれぞれについて、重要点を囲む領域に対する該第２画像断片の領域の複数の可能性のある整列の整列誤差を、第２の予め定めた基準に従って測定する手段を含むことを特徴とする画像断片継ぎ合わせ装置。
【請求項９】
請求項８記載の画像断片継ぎ合わせ装置において、該第２の予め定めた基準は該第１の予め定めた基準と同一であることを特徴とする画像断片継ぎ合わせ装置。
【請求項１０】
請求項８記載の画像断片継ぎ合わせ装置において、該第１の予め定めた基準は該第２の予め定めた基準と異なることを特徴とする画像断片継ぎ合わせ装置。
【請求項１１】
請求項８記載の画像断片継ぎ合わせ装置において、該精密調整手段は可能性のある各整列の整列誤差を１画素ずつ測定し、かつ、該精密調整手段は個々の整列に関する測定を整列誤差が閾値を超えた時に終了させる手段をさらに含むことを特徴とする画像断片継ぎ合わせ装置。
【請求項１２】
請求項８記載の画像断片継ぎ合わせ装置において、該精密調整手段は、各重要点について該複数の可能性のある整列中の測定された整列誤差が最小の整列を平行移動マッチ候補のグループとして選ぶことにより、各重要点毎に１つの平行移動マッチ候補のグループを得る手段をさらに含むことを特徴とする画像断片継ぎ合わせ装置。
【請求項１３】
請求項１２記載の画像断片継ぎ合わせ装置において、該精密調整手段は、該グループ間で平行移動マッチ候補を比較して、平行移動マッチ候補の組を１つ以上選ぶ手段をさらに含み、各組は各グループの平行移動マッチ候補を含み、該１つ以上の組はそれぞれ、その間に該複数の重要点間の幾何学的関係とほぼ同様の幾何学的関係を持つことを特徴とする画像断片継ぎ合わせ装置。
【請求項１４】
請求項１３記載の画像断片継ぎ合わせ装置において、該精密調整手段は、平行移動マッチ候補の組が２つ以上選ばれたときには、該２つ以上の平行移動マッチ候補の組に属する画素の重心の組を該精密整列へ変換し、また、平行移動マッチ候補の組が１つしか存在しないときには、該１つの平行移動マッチ候補の組を該精密整列へ変換する手段をさらに含むことを特徴とする画像断片継ぎ合わせ装置。
【請求項１５】
請求項８記載の画像断片継ぎ合わせ装置において、該精密調節手段は、１）該複数の重要点のそれぞれを取り囲む該第１画像断片の領域の平均画素値を求める手段をさらに含み、該領域はそれらの平均画素値が該第１画像断片に対する回転整列から独立であるように選ばれた形状を持ち、また、該精密調整手段は、２）各重要点に対する該複数の選択された整列内に、該重要点に整列する該第２画像断片の領域の平均画素値が該重要点を囲む該領域の平均画素値とほぼ同じ平均画素値を持つ整列だけを含める手段をさらに含むことを特徴とする画像断片継ぎ合わせ装置。
【発明の詳細な説明】
【０００１】
【発明の属する分野】
本発明は、画像の断片を継ぎ合わせて完全な画像を組み立てる技術に係り、特に多数の画像断片を精密に継ぎ合わせる技術に関する。
【０００２】
【従来の技術】
今日、画像処理装置は、例えば画像の印刷物を読み取ってその画像のデジタル表現を得ることにより、コンピュータによる画像の取り込みを可能にする。また、画像のデジタル表現を印刷して画像のハードコピーを作ることができる。コピー機、ファクス装置及びスキャナは画像処理装置の例である。これらの装置は、今日、操作者が取り込まれた画像を縮小や拡大、コントラスト、解像度又は色の調整等々により処理できるようにする高度な技術を利用している。今日の基本的な画像処理装置は、標準サイズの画像、例えば８．５インチ×１１インチの紙片に印刷された画像の処理には申し分ないが、特大の画像を装置に取り込むためには画像断片に分割しなければならず、そして、それら画像断片を印刷又は他の処理のために再び組み立てる必要がある場合に問題が起こる。
【０００３】
例えば、コピー機に関する問題は、地図やポスターのような特大画像をコピーしようとする場合に起こる。その理由は、コピー機の構造は、普通、読み取り機構の１回の動作で特大画像の一部つまり断片しか読み取ることができないためである。すなわち、コピー機のユーザは、手作業で特大画像を位置決めし、その地図又はポスターの部分部分を何度も読み取らせる必要があるということである。ユーザは目視によって、しばしば位置合わせ用マークの助けもなしに、コピー機のプラテン上で特大画像を位置合わせしなければならないため、結果として得られるのは、複数の紙片に分かれた特大画像の不揃いな断片の雑然とした集合である。最悪の場合、ユーザはその後に、各ページの縁を切り落としてテープで継ぎ合わせることにより、手作業で画像断片を組み立てなければならない。
【０００４】
同様に、ファクス装置は一定の比較的小寸法の紙片しか受け付けない。特大文書の幅がファクス装置の受付可能な幅を超える場合には、その文書を、それより小さな紙片の画像に分割しなければならない。そして、この特大文書画像は、何枚かの画像として受信側ファクス装置へ送信される。受信側ファクス装置のユーザは、同様の手順により複数の文書断片を継ぎ合わせて特大文書画像を得る。
【０００５】
自動的に画像断片を整列させ元の画像を復元するプロセスは画像レジストレーションとして知られている。従来、いくつかの画像レジストレーション手法が、主としてリモートセンシング分野に適用することを目的として、例えば、異なった衛星位置で撮影された複数の写真から大きなエリアの合成衛星画像を作成することを目的に開発された。
【０００６】
しかし、これらの手法は、オフィスのコピー機の環境にはうまく適用できない。一方では、応答時間の長さがコピー機の応用には受け入れることができない。他方では、リモートセンシング用の画像レジストレーション手法は画像断片を整列させるために画像断片を相対的に移動及び回転させる必要があるのみならず、アスペクト、スケール、コントラスト変動、その他の非線形エフェクト(effects）を修正しなければならない。
【０００７】
オフィス環境のために開発された画像レジストレーション手法は、いずれも１つ以上の欠点がある。ある手法は、元の大判文書に特別にマークを設けなければならない。別の手法によれば、大判文書は複数の部分に分割されて順に読み取られ、次に画像断片のペアが順に相互に位置合わせされる。
【０００８】
この手法は、３つ以上のオーバーラップした画像断片を整列させなければならない場合には専門家的な品質を得られない。図１の場合を考える。この場合、４つのオーバーラップした画像断片２，４，６，８が従来の手法によって相互に整列されている。本質的に、従来手法は、画像断片２を画像断片４と整列させ、画像断片４を画像断片６に整列させ、画像断片６を画像断片８に整列させるというペア単位の整列法を使う。画像断片２，４のペア、画像断片４，６のペア、画像断片６，８のペアの整列は満足できる。しかし、画像断片２と画像断片８の間の整列は満足できない。それは、ペア単位の整列におけるごくわずかな誤差が、画像断片２，８間の整列誤差が目立つほど累積するからである。適用分野の多くは３つ以上の画像断片を継ぎ合わせる必要があるので、このように整列誤差が複数の画像断片へ伝搬することは従来技術の重大な欠点である。
【０００９】
【発明が解決しようとする課題】
したがって、本発明の基本的な目的は、３つ以上の断片に分割された画像を高精度に復元するための改良した装置を提供することである。本発明の１つの目的は、３つ以上の画像断片を精度よく整列させるための改良した装置を提供することである。
【００１０】
【課題を解決するための手段】
本発明によれば、画像の３つ以上の断片が整列されてその画像が組み立てられ、かつ、オーバーラップした画像断片の各ペア間は高品質に整列される。画像レジストレーション操作は迅速に遂行される。本発明は、例えば大判文書の読み取り、コピー、ファクシミリ伝送に適用できる。
【００１１】
本発明によれば、１つの完全な画像の３つ以上のオーバーラップした画像断片を最適に継ぎ合わせて、その完全な画像を復元するための装置が提供される。この装置は、３つ以上の画像断片中の２つ以上のオーバーラップした画像断片間の整列誤差を、第１の予め定められた基準に従って測定する手段、２つ以上の画像断片中から選ばれた２つのオーバーラップした画像断片間の整列を精密調整してその２画像断片間の整列誤差を減少させる手段、３つ以上の画像断片の全てのオーバーラップするペア間の総整列誤差を前記予め定めた基準に従って累積する、前記測定手段と結合された手段、この累積手段及び前記精密調整手段と結合され、オーバーラップした画像断片のペアに対し順に前記精密調整手段を繰り返し適用して前記総整列誤差を最適化する全体最適化手段からなる。
【００１２】
本発明の一実施例によれば、大判文書又はパノラマ写真は、スキャナや他の画像取り込み装置により、オーバーラップした断片として取り込まれる。そして、ユーザは、ディスプレイとポインティングデバイスを含むユーザインターフェイスを利用して、ディスプレイ上で画像断片を大まかに整列させる。この種の画像断片操作の一例が、本出願の譲受人に譲渡された米国特許出願第０８／４４６，１９６号に述べられており、当該米国特許出願の内容は引用によって全面的に本明細書に組み込まれる。
【００１３】
画像断片がユーザによってほぼ整列されたならば、自動画像レジストレーションが引き継ぐ。オーバーラップした画像断片のペアのリストが作られる。各画像断片ペアの整列が順に精密調整される。本発明の範囲内で、どのような手法が画像断片ペアの整列に用いられてもよい。画像断片の各ペアが整列されている時に、全ペアの総整列誤差がモニタされる。総誤差を増加させるような新たなペア単位の整列はリジェクトされる。総整列誤差がそれ以上改善されなくなった時に、精密調整のプロセスは終了する。
【００１４】
このような本発明により提供される最適化プロセスは、ある画像断片ペアの整列の改善が他の画像断片ペアの整列を犠牲にしないことを保証する。したがって、全ての画像断片ペアに対し十分なレジストレーション品質が保証される。
【００１５】
本発明はまた、２つのオーバーラップした画像断片の整列を精密調整する効率的な手法を提供する。一般的に、このような手法は、可能性のある整列の空間上でベストマッチ（best match）を探索する必要がある。本発明は、探索空間を制限することにより精密調整プロセスを加速するために適用できる手法をいくつか提供する。
【００１６】
本発明により提供されるそのような手法の一つは、可能性のある精密整列の探索範囲を限定するために、第１の画像断片中のテンプレート領域又は重要（interest）点を特定する手法である。この第１の画像断片の上に格子又はセルがオーバーレイされる。画像の各画素に対し重要度オペレータ（interest operator）が適用され、各画素の重要度レベル（interest level）が得られる。所定の閾値を超えるレベルを持つ各セルについて、セル内で最大の重要度レベルを持つ画素が重要点候補に選ばれる。このようにして、各セルは１個又は０個の重要点候補を持つ。これらの重要点候補より、最大の重要度レベルを持つ候補が第１の重要点に選ばれる。第１の重要点から最も遠い重要点候補が第２の重要点に選ばれる。さらに若干数の重要点を、同様の基準又は他の基準によって重要点候補から選んでもよい。
【００１７】
本発明はまた、各画素の重要度レベルを検出する改良手法も提供する。この改良された測定法によれば、垂直軸又は水平軸の方向に半径ｒ画素だけ離れた画素間の画素値の分散が求められ、次に２ｒ画素離れた画素に対する画素値の分散と３ｒ画素離れた画素に対する画素値の分散が算出される。このように３つの分散が求められ、それら分散の平均が評価される画素に対するＭoravecの分散として求められる。勿論、本発明によれば、最終的な判定に利用される分散の数は３以外でもよい。
【００１８】
本発明はまた、第１のオーバーラップした画像断片における重要点が特定された後でも、可能性のある精密整列の探索範囲を限定する手法を提供する。各重要点毎に、第１の画像断片中の各重要点を囲む領域の平均（画素値）が計算される。領域形状は、その領域の平均（画素値）が第１の画像断片に対する相対的回転に関し不変であるように選ばれ、例えば円又は円環である。各重要点毎に、この平均（画素値）を用いて第２の画像断片上の可能な平行移動整列の探索範囲を限定する。第２の画像断片の各画素について、同様構造の領域の平均画素値が計算される。この平均画素値と、重要点を囲む領域について決定された平均画素値との差が閾値割合を超えるときは、第２の画像断片上の当該画素に対する重要点の並行移動整列は可能な整列としては廃棄することができる。領域形状のゆえに、この時点で回転整列を別にチェックする必要はない。このような本発明の性質は、２つのオーバーラップした画像断片の整列の精密調整の効率を大幅に向上させる。
【００１９】
好適な実施例においては、２つのオーバーラップした画像断片の可能性のある整列の最初の評価は、Ｄ.Ｉ.Ｂarnea and Ｈ.Ｆ.Ｓilverman，”Ａ Ｃlass of Ａlgorithms for Ｆast Ｄigital Ｉmage Ｒegistration，”ＩＥＥＥ Ｔrans．on Ｃomputers，Ｖol．c-２１，１９７２，pp.１７９-１８６（以下、［Ｂarnea７２］と略記する）に述べられているところにほぼ従って行われる。［Ｂarnea７２］の内容は引用により全面的に本明細書に組み込まれる。各重要点は別々に整列される。可能性のある整列に関する整列誤差は、予め定められた整列誤差基準に従って測定される。好適な実施例においては、いわゆるＬ１基準が整列誤差の測定に用いられる。誤差は、１画素ずつ、重要点を囲む領域と第２の画像断片上の同様サイズの領域との間で計算される。ある整列に関する累積誤差がある閾値を超えたならば、その整列が精密整列として最終的に選択される可能性はないので、当該整列のための計算は終わらせてよい。この閾値は、前の整列について計算された誤差、及び、現在の整列誤差評価が目下どのくらい進んでいるかを考慮してもよい。
【００２０】
可能性のある整列の探索結果は好ましくは、測定した誤差が閾値未満となる整列に関する重要点別のリストの集合である。各整列は、重要点に沿って一列に並ぶ第２の画像断片上の画素位置として表すことができる。
【００２１】
本発明によれば、精密な整列は、第１の画像断片上に配された重要点間の幾何学的関係を考慮して選ばれるであろう。良好な整列を得るためには、第１の画像断片の重要点に対し整列する第２の画像断片上の画素は、それらの間の幾何学的関係が重要点と同じでなければならない。２つの重要点が好適な関係であれば、それら重要点間のユークリッド距離は、それら重要点に対し整列する第２の画像断片上の画素間のユークリッド距離と当然に一致する。
【００２２】
このような関係が当てはまる整列を見つけるために、各重要点に関するリストを探索して、重要点間と同じ幾何学的関係を持つ画素グループを探す。だた１つの画素グループだけが、この基準に所定の許容誤差内で合致する場合には、その画素グループが新たな精密整列を決定するために用いられる。２つ以上の画素グループがこの基準に所定の許容誤差内でマッチする場合には、接近した画素の塊の重心が精密整列を決定するための基準として用いられる。
【００２３】
以下の詳細な説明を添付図面と関連させて読めば、本発明はより一層明瞭になろう。
【００２４】
【発明の実施の形態】
［本発明の実施に適したシステム］
図２は本発明に利用するのに適したコンピュータシステムの基本サブシステムを示す。図２において、コンピュータシステム１０はバス１２によってサブシステム、例えば中央処理装置１４、システムメモリ１６、入出力（Ｉ／Ｏ）コントローラ１８、パラレルポート２２を経由したプリンタのような外部装置、ディスプレイアダプタ２６を経由したディスプレイスクリーン２６、シリアルポート２８、キーボード３０、固定ディスクドライブ３２及びフロッピーディスク３３Ａを受け入れ可能なフロッピーディスクドライブ３３を相互接続してなる。他の多くの装置も接続でき、例えば読み取り装置３４を外部インターフェイス３６を介して、マウス３８をシリアルポート２８を介して、またタッチスクリーン４０を直接的に接続することができる。他の多くの装置又はサブシステム（図示されていない）も同様の方法で接続してもよい。また、後述のように、本発明を実施するためには必ずしも図２に示された装置の全部が用意されなければならないわけではない。それらの装置及びサブシステムは、図２に示された方法とは異なった方法で相互接続されてもよい。図２に示したようなコンピュータシステムの動作は当該技術分野においてよく知られているので、本明細書では詳しくは述べない。本発明を実施するためのソースコードは、システムメモリ１６に実行可能に配置され、あるいは固定ディスク３２又はフロッピーディスク３３Ａのような記憶媒体上に格納される。
【００２５】
図３は好適な実施例のための構成３００を表しており、これはスキャナ３０２、メモリ３０４、ＣＰＵ（中央処理装置）３０６、ディスプレイ３０８、タッチスクリーン３１０及びプリンタ３１２からなっている。この構成３００は、ファクス装置又はスキャナのハードウエアの一部分であってもよい。現在のところ好適な実施例では、スキャナ３０２はＲicoh ＩＳ６０ ６００dpiグレースケールスキャナである。プリンタ３１２は６００dpi，８ページ／分のレーザプリンタである。ＣＰＵ３０６はＳun Ｓparc １０ ワークステーションである。特大の画像を少しずつ読み取らなければならないため、特大画像の多数のオーバーラップした断片が入力され互いに位置合わせされねばならない、どのようなシステムにも本発明を利用できる。
【００２６】
ディスプレイ３０８は液晶ディスプレイ（ＬＣＤ）スクリーンでも、陰極線管（ＣＲＴ）スクリーンでも、その他の種類のディスプレイスクリーン又はパネルでもよい。このディスプレイスクリーンは、ＣＲＴスクリーンもしくはモニタを採用したパーソナルコンピュータ又はワークステーションのような標準的なコンピュータに用いられているディスプレイスクリーンと同様なものである。様々な種類のユーザ入力装置を本発明に利用できる。例えば、図３にはタッチスクリーンが示されているが、ユーザがディスプレイスクリーンに表示されたポインタを手の動きに従って動かすことができるようにするマウスは、標準的なユーザ入力装置である。マウスは一般に、その表面に１つ以上のボタンがあり、ユーザはマウスを移動させることによってスクリーン上のあるオブジェクトを指し示すことができ、そして、マウスの１つ以上のボタンを押すことによって、そのオブジェクトを選択し、あるいは活動化させることができる。タッチスクリーンによれば、ユーザはスクリーン上のオブジェクトを指さして一つのオブジェクトを選択し、スクリーン上の別の位置を指さすことによって、その選択されたオブジェクトを移動させることができる。マウス又はタッチスクリーンを利用して活動化させるための様々なボタンとコントロールが、スクリーン上に表示されるであろう。
【００２７】
［多数の画像断片の整列］
図４は、本発明の一実施例に従って多数のオーバーラップした画像断片を整列させるステップを記述したフローチャートである。ステップ４０２において、好適な実施例のシステムは画像の断片を取り込む。この取り込みは、例えば、一つの大判文書に対しスキャナ３０２を連続的に利用することによって行われる。画像断片は、近くのファクシミリ通信装置によって読み取ってもよいし、遠方のファクシミリ通信装置より受信してもよい。どのような方法であっても画像断片が取り込まれると、システムメモリ１６内のそれらの電子的表現をその後の処理に利用できる。一般的に、画像断片はそれぞれ画素値が電子的に記憶された画素の配列として表現される。
【００２８】
ステップ４０４において、ユーザは好ましくはユーザインターフェイスを利用して、元の画像を復元するように画像断片を相互に大ざっぱに整列させる。ユーザは、画像断片を操作するために例えばマウス３８又はタッチスクリーン４０を利用する。画像断片の現在位置に関するフィードバックはディスプレイスクリーン２４上で分かる。好適な実施例において利用される画像断片操作プロセスの完全な説明は、米国特許出願０８／４４６，１９６号に見ることができる。
【００２９】
ユーザによる整列の目的は、その後の自動化した整列を簡単にすることである。自動化レジストレーションが実行される時に、好適な実施例のシステムはどの断片がオーバーラップしているか既に知っている。断片の配置が、最高のレジストレーションからある閾距離内にあることも分かっている。好ましくは、この距離は１インチ、つまり１００ｄｐｉで１００画素である。それには莫大な計算を必要とするかもしれないが、本発明の範囲内で画像断片を全自動で整列させることができるであろう。ステップ４０４が完了した時に、画像断片が電子的に保存されるのみならず、ユーザによって決められた、それらの大雑把な整列も保存される。
【００３０】
ステップ４０６において、好適な実施例のシステムは画像断片を自動的に整列させる。ステップ４０６の操作については図５乃至図１１に関連して詳細に述べられる。整列プロセスはステップ４０８で終わり、その先の処理に利用できる完全な再組立された画像が残る。
【００３１】
本発明によれば、整列プロセスは画像全体に関する総誤差情報を、オーバーラップした画像断片のすべてのペア間の精密なレジストレーションを得るために利用する。したがって、連続した画素断片ペア間の誤整列の伝播により生じる図１に見られるようなアーティファクト(artifact）を避けられる。
【００３２】
このように好適な実施例は、個々の画素断片ペア間の整列誤差及び画像全体についての整列誤差の両方を最適化する。好適実施例の画像断片整列プロセスを詳細に説明する前に、画像又は画像の部分の相互間の整列を評価するために利用できる基準を説明するのが有益であろう。
【００３３】
一つの基準は相互相関である。Ｍ×Ｎサイズの２つのウインドウＡ，Ｂ間の正規化した相互相関の計算は次式で表される。
【００３４】
【数１】
0004125393.tif 000002
【００３５】
ただし、ａ（ｘ，ｙ）とｂ（ｘ，ｙ）はある座標におけるウインドウＡ，Ｂの画素値を表す。ウインドウＡ，Ｂ間の最適な整列すなわちマッチの場合には、σの値は＋１にごく近い。しかし、相互相関のスコアは非常に計算が集中的である。
【００３６】
好適な実施例は、整列誤差を測定するために、いわゆるＬ１ノルムを代わりに使用する。これは、ウインドウＡ，Ｂに対し、次式で表されるεを求めることによりなされる。
【００３７】
【数２】
0004125393.tif 000003
【００３８】
εの値が小さいほど、マッチが良好である。このＬ１ノルムは、加算しか含まず、相互相関に必要な乗算も除算も含まないので、計算が非常に簡単である。２つのオーバーラップした画像断片間の整合誤差の測定へのＬ１ノルムの応用は、［Ｂarnea７２］に述べられている。
【００３９】
本発明の一実施例の画像断片整列法について、まず図５乃至図１１のフローチャートを参照して説明する。つぎに、大判文書である地図の画像を得る特定の例に対する本発明の適用について、図１２乃至２３を参照して説明する。
【００４０】
図５は、本発明の一実施例に従って複数のオーバーラップした画像断片を位置合わせするステップを記述したフローチャートである。ステップ５０２において、好適実施例は、図４のステップ４０４でユーザにより確認された大まかな整列に応じた画像断片間のオーバーラップのリストを作る。
【００４１】
ステップ５０４において、整列は好ましくはオーバーラップ領域のサイズの順にソートされる。最大のオーバーラップに関係したオーバーラップ・ペアのメンバーたる一方の断片が、もう一方の断片に対する基準フレームに選ばれる。
【００４２】
ステップ５０６は、ステップ５０２で作成されたリスト上のすべてのオーバーラップを処理するループを開始する。このループの最初のパスでは、リスト上の最初のオーバーラップした画像断片ペアが処理のために選ばれる。ステップ５０８において、この２つのオーバーラップした画像断片の整列は、より良好な整列を見つけるため精密調整される。この整列ステップは、これら２つのオーバーラップした画像断片だけに対し行われる。２つのオーバーラップした画像断片の整列を向上させるために、多くの手法が利用可能である。好適な実施例に利用される手法は、図６乃至図１１を参照して説明する。
【００４３】
ステップ５０８で改善した整列が見つけられるが、この改善した整列は必ずしもオーバーラップした画像断片に適用されるとは限らない。ステップ５０８でオーバーラップした画像断片ペアに対する改善した整列を生成したならば、ステップ５１０において、この改善した整列に対する整列誤差が、好ましくは前述のＬ１基準により算出される。そして、全ての画像断片ペアにつきＬ１基準により測定された総整列誤差は、ステップ５１２において、ステップ５０８で見つけた改善した整列を反映させるべく調整される。リストの最初のパスでは、改善した整列値は単純に、初めて展開されている総誤差測定値に足される。２回目以降のパスでは、全てのオーバーラップ・ペアの整列が計算されて合計される。改善した整列によって影響を受けるオーバーラップのみ、それらの整列誤差が再計算される必要がある。
【００４４】
ステップ５１４において、好適な実施例の手順は総整列誤差が良くなったか、あるいは、今回が処理の流れの決定とは無関係な整列誤差の増加をもたらす最初のパスであるかチェックする。当該新しい整列を取り込むことにより総整列誤差が改善された場合、又は今回が実際にリストの最初のパスである場合は、処理はステップ５１６に進み、ステップ５０８で見つけられた改善した整列が、そのペアの第２の画像断片を平行移動及び回転させることにより確認される。今回がリストの最初のパスでなく、かつ、当該改善された整列を取り込みことにより総整列誤差が増加する場合には、ステップ５０８で見つけた改善した整列は当該画像断片ペアには適用されず、そしてステップ５１８において、当該精密調整された整列はその以前の状態に調整し直される。
【００４５】
ステップ５１６又はステップ５１８を実行すると、選択された画像断片ペアの処理はペアのリストの今回パスに関して終了した。ステップ５２０において、好適な実施例はリスト上の最後のオーバーラップ・ペアの処理が今済んだか、つまり、リスト上のすべてのペアの整列の精密調整が済んだか判定する。リスト上に他のペアが残っているならば、ステップ５０６へ進み次のオーバーラップした画像断片ペアの処理が始まる。
【００４６】
次に検討されるべきオーバーラップは、好ましくは１つの画像断片と基準断片たるフレームつまり既に位置合わせ済みの別の画像断片との間の次に最も大きなオーバーラップであろう。そのようなペアが全て位置合わせされたならば、他のペアを調べることができる。これらのルールはある特定の順番を完全に決めるわけではなく、本発明の範囲内でどのような順番を用いてもよいが、用いる順番によって結果が多少変わる。
【００４７】
リスト上の最後のオーバーラップ画像断片ペアが処理されたならば、ステップ５２２に進み、好適な実施例はリストの当該パスで総誤差に改善があったか調べる。ステップ５２２において総誤差が改善されたと判明したときには、好適な実施例はステップ５２６で最初の画像断片ペアへセットし直し、ステップ５０６から始まるループを再開する。
【００４８】
ステップ５２２において総誤差が改善されなかったと判明したときには、最適化はステップ５２４で終了し、各画像ペアの最終的な整列に基づいて完全な画像が作られる。この完全な画像のオーバーラップ領域における画素値の決定には多くの手法を利用できる。好適な実施例によれば、整列後の画像断片がオーバーラップする場合、最初に読み取られた断片に対応した画素値が完全な画像のために用いられる。
【００４９】
このように、図５は、総整列誤差を制御しながら、オーバーラップした画像ペアの整列を連続的に精密調整することによって総整列誤差を最適化する手順を記述している。図５の手順の多くの修正が本発明の範囲内で可能であることは明白である。例えば、オーバーラップ・ペアのリストは、オーバーラップ面積ではなく誤差寄与の観点から順序つけることもできるであろう。反復回数を一定にすることもできるであろう。あるいは、Ｓ．Ｋirkpatrick，Ｇ．Ｇelatt，Ｍ．Ｐ．Ｖecchi，”Ｏptimization by Ｓimulated Ａnnealing”，Ｓcience，Ｖol．２２０，Ｎumber ４５９８，pp．６７１-６８０，Ｍy １９８３(［Ｋirpatrick８３］と略記）に述べられている模擬アニーリング手法によって、総誤差を増加させるようなオーバーラップ画像断片の特定の改善整列を容認するように最適化プロセスを変更すこともできるであろう。この文献［Ｋirkpatrick８３］の内容は、引用により本明細書に組み込まれる。
【００５０】
［オーバーラップした画像断片のペアの整列］
図６は、本発明の一実施例に従って第１と第２のオーバーラップした画像断片の位置合わせを記述したフローチャートである。図６の手順は、多数のオーバーラップした画像断片のレジストレーションの１ステップとして利用でき、例えば図５のステップ５０８を実現する。しかし、図６の手順は、２つのオーバーラップした画像断片を自動的に位置合わせしなければならない他のシチュエーションでも利用可能である。
【００５１】
ステップ６０２において、好適な実施例はオーバーラップの第１の画像断片上のいわゆる重要点を探索する。重要点とは、容易なマッチングを可能にする明瞭な特徴を持つ領域内にある画像中の画素で、記号、文字等何でもよい。重要点の近傍領域だけのマッチングに集中することによって、処理時間が大幅に減る。重要点を見つけるための多くの手法が当業者には知られている。重要点検出手法の概説は、Ｌu Ｙan，”Ｉnterest Ｏperator and Ｆast Ｉmplementation，”ＰＲ４３８（［Ｙan８８］と略記）に見ることができ、この文献［Ｙan８８］の内容は引用により本明細書に組み込まれる。好適な重要点検出手法は、図８及び図９に関連して説明する。好ましくは、２つの重要点が第１のオーバーラップ画像断片において検出され、その後の処理は、これらの２つの重要点を囲む領域とマッチする第２の画像断片中の領域の検出に集中する。
【００５２】
ステップ６０４において、好適な実施例はステップ４０４で作られたユーザ整列に従って、マッチが探索される第２画像断片の領域を限定する。各重要点毎に、平行移動の可能な範囲は、重要点に現在整列されている第２画像断片上の画素を囲む予め定められた領域に限定される。
【００５３】
ステップ６０６において、重要点を取り囲む領域の平均画素値の評価に基づいて探索領域がさらに絞られる。各重要点毎に、重要点を取り囲む領域の平均画素値が算出される。領域の形状は、画像に対する領域の回転が平均画素値の評価と無関係になるように選ばれる。領域は好ましくは円形であるが、円環等の他の形状も可能である。
【００５４】
第２画像断片のオーバーラップ領域内の各画素について、好適実施例は画素を取り囲む同様サイズの領域の平均画素値を計算する。この平均画素値は重要点について求められた平均画素値と比較される。各重要点に関し、第２画素断片画素の周囲の平均画素値が、重要点を取り囲む領域について測定された平均画素値の許容誤差（好適実施例では１０％）の範囲内であれば、その第２画像断片画素は該重要点に対するマッチ候補を求めるための基準として保存される。ステップ６０６の結果は、マッチ候補を求めるための基準として役立つ第２画像断片上の画素の、各重要点別のリストである。このようにして、マッチ候補の探索範囲は大幅に縮小される。
【００５５】
連続した円形領域の平均の計算を簡単にするため、図７に示すような円形領域についてローリング(rolling）平均が計算される。図７は、旧ウインドウ６１４、すなわち平均画素値を計算済みの第２画像断片上の円形領域と、平均画素値がまだ計算されていない新ウインドウ６１６を表している。後方の月形６１８は、旧ウインドウ６１４内に位置するが、新ウインドウ６１６内には位置しない。前方の月形６２０は新ウインドウ６１６内に位置するが、旧ウインドウ６１４の中には位置しない。新ウインドウの平均は次式により計算できる。
【００５６】
【数３】
0004125393.tif 000004
【００５７】
ただし、Ｎは領域つまりウインドウ内の画素数であり、μは平均であり、ＦとＲはそれぞれ前方の月形６２０と後方の月形６１８である。このように、前方と後方の月形について画素和を計算するだけでよい。
【００５８】
ステップ６０８において、最良の整列を見つけるため、各重要点に対し残っている、可能性のあるマッチ候補が探索される。各マッチ候補は、２つのオーバーラップした画像断片間の回転整列及び平行移動整列の組合せを表す。ステップ６０６により生成されたリストに含まれる各画素は、１つの可能な平行移動整列、つまり第１画像断片上の重要点への第２画像断片上の当該画素の整列を表す。回転整列は、好ましくは、現在の回転整列から各方向へ１０゜（ユーザが決めることであるが）の範囲内で１゜刻みで探索される。
【００５９】
ステップ６０８の探索は、［Ｂarnea７２］に述べられているラインに沿って実行される、つまり、いわゆる逐次類似検出アルゴリズム（ＳＳＤＡ）である。マッチの探索は、各重要点毎に別々に行われる。調べようとする各整列について、好ましくはＬ１基準を使って、重要点を囲むテンプレート領域と、それに対応する形状とサイズが類似した第２画像断片上の領域との間の整列誤差が測定される。このテンプレート領域は好ましくは直径が１６画素である。前述のように、Ｌ１は多数の画素に関する和として計算される。ＳＳＤＡ手法によれば、この和がモニタされ、ある閾値を超えると、当該整列は精密整列たり得ないとしてその計算は終了する。好ましくは、この閾値は固定され、領域の画素の１５％（残りの画素は同一）分の最大誤差に相当する。あるいは、誤差増加の閾値曲線、もしくは前に測定された整列誤差に応じて変化する閾値が用いられてもよい。
【００６０】
この探索手法に関しては、本発明の範囲内で多くの変形手法を利用してよいであろう。例えば、処理がかなり遅くなるが、Ｌ１基準に代えて相互相関基準を利用することもできる。なお、探索に使われる基準は、オーバーラップ領域全体の整合誤差、すなわち図５に関連して述べたように多くの画像断片についての総整列誤差の測定に使われる基準と同じである必要はない。また、テンプレート領域は、整列誤差計算を高速化するため、まばらなウインドウ、つまり一部の画素が削除された重要点を取り囲む領域にすることもできる。
【００６１】
ステップ６０８の探索の結果は、ある閾値を下回る整列誤差を持つ重要点に対する平行移動マッチ候補の、重要点毎のリストである。普通、１リストあたり３つ又は４つの整列があるであろう。これらの整列を見つけるために回転と平行移動の両方が変えられるが、これらの整列の平行移動成分だけが保存される。図１１に関連して説明されるが、精密整列の回転成分は、別の方法で得られる。一つの重要点に対する各整列の平行移動成分は、その重要点に整列する第２画像断片の画素の位置として表すことができる。
【００６２】
ステップ６１０において、ステップ６０８で見つかった整列候補より、一つの精密整列が選ばれる。本発明の好適実施例によれば、整列のグループを探すことにより、平行移動成分が重要点間の幾何学的関係と同じ幾何学的関係を持つ整列が、各重要点毎に１つずつ選ばれる。この幾何学的マッチング手順は図１１に関連して述べる。多数画像断片マッチングの場合には、この精密整列がステップ５０８に関連して言及した改善された整列となる。ただ２つの画像断片を整列させようとする場合には、その断片の一方又は両方を適宜シフトすることにより、精密整列を直ちに用いることができる。ステップ６１２において、２つの画像断片のための精密整列を見つけるプロセスは終了する。
【００６３】
図８は、本発明の一実施例に従ってオーバーラップした第１の画像断片上の重要点を検出するステップを記述したフローチャートである。図８のフローチャートのステップは、図６のステップ６０２の具体例に相当する。ステップ７０２において、好適な実施例は第１画像断片のオーバーラップ領域をセル格子に分割する。ステップ７０４において、分散ペレータが各画素に対し適用され、マッチングのための画素の重要度レベルの数値インデックスが求められる。好適実施例において、適用される分散オペレータは本発明に従って強化されたＭoravecオペレータである。この本発明の強化Ｍoravecオペレータについては図９に関連して述べる。本発明の範囲内において、様々の適当な分散オペレータを適用することができる。従来のＭoravecオペレータを含む分散オペレータに関する概説は［Ｙan８８］に見ることができる。
【００６４】
ステップ７０６において、重要度レベルが予め決められた閾値を超えない画素は、可能性のある重要点候補としては棄てられる。ステップ７０８において、各格子セルを単一の重要点に限定することにより、重要点候補はさらに絞り込まれる。かしくて、各格子セルに１個又は０個の重要点が含まれる。そしてステップ７１０において、重要点候補より、ステップ７０４で決定された最高の重要度レベルを持つ重要点候補が第１の重要点に選ばれる。ステップ７１２において、第１の重要点より最も遠い重要点候補が第２の重要点に選ばれる。ステップ７１４で重要点決定プロセスは終了する。
【００６５】
図９は、本発明の一実施例に従い第１のオーバーラップ画像断片上の特定の画素に修正Ｍoravec分散オペレータを適用するステップを記述したフローチャートである。図９に示したステップは図８のステップ７０４の具体例に相当する。
【００６６】
図１０は、修正Ｍoravecオペレータの決定に好んで用いられる画素を表している。直交軸７５０は、修正Ｍoravec分散オペレータを計算すべく選択された画素７５２で交差する。第１組の４画素７５４は、直交軸方向に選択画素７５２からｒ画素離れている。ここで、３ｒがステップ６０８で用いられたテンプレート領域の半径である。第２組の４画素７５６は、選択画素７５２から２ｒ画素離れている。第３組の画素７５８は、選択画素７５２から３ｒ画素離れている。
【００６７】
ステップ７１６において、好適実施例は画素７５４の画素値の分散を求める。ステップ７１８において、好適実施例は画素７５６の画素値の分散を求める。ステップ７２０において、好適実施例は画素７５８の画素値の分散を求める。ステップ７２２において、修正Ｍoravec分散オペレータが計算され、これら３つの分散の平均となる。分散計算プロセスはステップ７２４で終了する。本発明の範囲内で異なった数の分散を計算し平均をとってもよいことは当然である。
【００６８】
図１１は、本発明の一実施例に従って、第１と第２の画像断片間の精密整列を見つけるために第１の画像断片上の重要点のマッチ候補のリストの幾何学的関係を第２の画像断片の画素に適用するステップを記述したフローチャートである。図１１のフローチャートのステップは、図６のステップ６１０の具体例に相当する。
【００６９】
ステップ８０２において、好適実施例は重要点間のユークリッド距離（画素幅）を±０．１画素までの精度で測定する。ステップ８０４において、好適実施例は、第２画像断片上において、第１重要点に対する平行移動マッチを表す画素と第２重要点に対する平行移動マッチを表す画素との可能な全てのペアのついてのユークリッド距離を測定し、重要点間のユークリッド距離と±１．１画素幅範囲まで同じユークリッド距離を持つ画素ペアを探す。
【００７０】
このユークリッド距離基準を満足する平行移動マッチ候補のペアは、次に、２画像断片間の精密整列を見つけるために利用される。ステップ８０６は、ユークリッド距離基準を満たす画素ペアが２つ以上存在するか判定する。ユークリッド距離基準を満たす画素ペアが１つしかなければ、そのままステップ８０８へ進む。ユークリッド距離基準を満たす画素ペアが２つ以上あるときは、ステップ８１０において第１重要点に対応した残存画素及び第２重要点に対応した残存画素の重心を求める。そして、得られた重心ペアの画素は、第１重要点及び第２の重要点に対する平行移動マッチ候補として役立つ。
【００７１】
ステップ８０８において、平行移動マッチ候補ペアに従って精密整列が生成される。当業者は、第１重要点に対する平行移動マッチ候補の残っているものだけで第１画像断片及び第２画像断片間の精密整列の平行移動成分が決まることに気付くであろう。そして、第１画像断片上の第１と第２の重要点を結ぶ仮想直線と、平行移動マッチ候補の残存ペアを表す画素間の仮想直線との間の角度を計算することにより、回転成分が決定される。そして、この幾何学的マッチングプロセスはステップ８１２で終わる。
【００７２】
［画像断片整列の例］
図１２乃至図２３は新聞の１ページの複写に本発明がどのように適用できるかを表している。図１２は、新聞の１ページのオーバーラップした読み取り画像を表す。４つの８×１０インチの画像断片９０２，９０４，９０６，９０８は、スキャナ３０２のようなデスクトップ・スキャナによって読み取られた。これら読み取り画像はそれぞれ、隣り合う読み取り画像と２５％以上オーバーラップするように読み取られた。画像は１００ｄｐｉで読み取られた。図１２は、ユーザにより初期整列された後に表示される画像断片９０２，９０４，９０６，９０８を表している。矢印９１０，９１２は２つのオーバーラップ断片間のレジストレーション誤り領域を指している。
【００７３】
図１３は、本発明の一実施例に従って整列された画像断片９０２，９０４，９０６，９０８を表している。これら４画像断片の位置合わせのための処理時間は、５０ＭＢのメインメモリを備えた５０ＭＩＰＳのＳun Ｓparc 10 ワークステーションを使って、おおよそ４５〜５０秒であった。この時間の約３０％は、画像断片を正しい場所へ回転及び移動させるために費やされる。同じ画像断片セットのための処理時間は、最初のユーザによる配置によって５％ほど変化するかもしれない。レジストレーションは、垂直水平方向が１画素以内まで、また回転が０．１゜以内まで正確に測定された。
【００７４】
図１４乃至図２３は、本発明の一実施例に従ってどのように２つの画像断片が相互に整列されるかを表している。図１４は、図１２に示したマップ中の画像断片９０２を表す。図１５は、図１２に示したマップ中の画像断片９０４を表す。画像断片９０２，９０４の整列は、４画像断片全ての精密調整の１ステップとして本発明に従って精密調整されなければならない。
【００７５】
図１６は、図９に関連して述べたように重要点を検出するための格子１１０２がオーバーレイされた画像断片９０２のオーバーラップ部分を表している。格子１１０２の各セルには重要点候補が１つあるか、または１つもない。最初に選択される重要点１１０６は最高の重要度レベルを持つ重要点候補である。次に選択される重要点１１０８は最初に選択された重要点１１０６から最も遠い重要点候補である。
【００７６】
図１７は画像断片９０２上の第１の重要点１１０６を囲むテンプレート領域１１１０を示す。図１８は画像断片９０２上の第２の重要点を囲むテンプレート領域１１１２を示す。これらが第２の画像断片９０４上において探索されるべきテンプレート領域である。
【００７７】
図６と関連して述べたように、各重要点に関し、マッチ探索領域は重要点へ目下整列されるところの第２画像断片上の画素を囲む領域にまず限定される。図１９は、第１重要点１１０６とのマッチングに使われる第２画像断片の縮小された探索領域１１１４を表している。図２０は、第２重要点１１０８とのマッチに使われる第２画像断片の縮小された探索領域１１１６を表している。
【００７８】
図６に関連して述べたように、次の探索領域限定ステップは、重要点を囲むテンプレート領域の平均を求め、異なった平均を持つ第２画像断片の領域を削除することである。図２１は、第１重要点に対する整列候補としての論点から除かれた画素を黒でマークした縮小探索領域１１１４を表している。図２２は、第２重要点１１０８に対する整列候補としての論点から除かれた画素を黒でマークした縮小探索領域１１１６を表している。
【００７９】
図２３は、本発明の好適実施例に従って探索により生成された各重要点に対する整列候補を記入した画像断片９０４のオーバーラップ部分を表している。第１重要点１１０６は整列候補１１１８，１１２０を持つ。第２重要点は整列候補１１２６を持つ。図１１の幾何学的探索を行うと、整列１１２０，１１２６だけが残る。それは、整列１１２０，１１２６間のユークリッド距離は、重要点１１０６，１１０８間のユークリッド距離に十分に近いからである。そして、これらの整列は重要点に対する整列候補となって、画像断片９０２，９０４間の精密整列を決定するための基準となる。
【００８０】
以上、本発明を特定の典型的実施例に関して説明した。しかし、特許請求の範囲に定義された本発明の範囲から逸脱することなく、様々な修正及び変形をなし得ることは明白であろう。
【００８１】
例えば、本発明を実施するため様々なプログラミング言語及び技法を使うことができる。本発明におけるタスクを達成するため提示した特定のロジックを、本発明の範囲から逸脱せずに修正してもよい。
【００８２】
さらに、本明細書において説明したフローチャートは、本発明の方法を遂行するステップの単なる大まかな論理的な流れを説明するためのものであり、本発明の範囲を逸脱することなく、フローチャートに対しステップを追加し又は削除してもよい。また、フローチャート中のステップの実行順序を、本発明の範囲を逸脱することなく、変更してもよい。フローチャートによって記述した方法の実行に関しさらに検討すれば、ステップの選択及び順序を変更する必要があるかもしれない。
【００８３】
一般に、本明細書中のフローチャートは、コンピュータシステムで走るソフトウエアルーチンにより実行される１つ以上のステップからなる。これらのルーチンは、当該技術分野で知られている任意の手段によって実現してよい。例えば、”Ｃ”、パスカル、フォートラン、アセンブリ言語等々のコンピュータプログラム言語をいくつ使用してもよい。さらに、手続き型技法、オブジェクト指向技法又は人工知能技法のような様々なプログラミング技法を採用してよい。
【００８４】
フローチャートのステップを、１つ以上のソフトウエアルーチン、プロセス、サブルーチン、モジュール等々によって実現してよい。割り込み、ポーリング、その他の実行機構のような、ソフトウエアによるステップの実行順序に影響を与える事柄もある。マルチプロセシングやマルチタスキングの環境なら、複数のステップを”同時に”実行できるであろう。
【００８５】
このような多くの変更もしくは修正は当業者には容易に理解されよう。したがって、本明細書及び図面は、限定的にではなく説明的な意味でとらえられるべきであり、本発明は特許請求の範囲の記載によってのみ限定される。
【００８６】
【発明の効果】
以上、詳細に説明したように、本発明によれば、オーバーラップした３つ以上の画像断片を全体として最適に継ぎ合わせて、３つ以上の断片に分割された元の画像を高品質に復元することができる。３つ以上の画像断片の整列を効率的に行うことができる。オーバーラップした画像断片のペア間の高精度な整列が可能である。オーバーラップした画像断片のペア間の整列の精密調整を効率的に行うことができる、等々の効果を得られる。
【図面の簡単な説明】
【図１】従来技術によるオーバーラップ画像断片の整列結果を表す図である。
【図２】本発明に利用するのに適したコンピュータシステムの基本サブシステムを示すブロック図である。
【図３】好適な実施例のためのサブシステムの構成を示す図である。
【図４】本発明の一実施例により多数のオーバーラップした画像断片を整列させるステップを記述したフローチャートである。
【図５】本発明の一実施例により多数のオーバーラップした画像断片を位置合わせするステップを記述したフローチャートである。
【図６】本発明の一実施例により第１と第２のオーバーラップした画像断片を位置合わせするステップを記述したフローチャートである。
【図７】本発明の一実施例により第２のオーバーラップした画像断片の探索領域を限定するために画像のウインドウの平均を計算する方法を示す図である。
【図８】本発明の一実施例により図６中のオーバーラップした画像断片中の第１の画像断片上の重要点を検出するステップを記述したフローチャートである。
【図９】本発明の一実施例により第１のオーバーラップした画像断片の画素に対し修正Ｍoravec分散オペレータを適用するステップを記述したフローチャートである。
【図１０】本発明の一実施例により修正Ｍoravec分散オペレータの計算に用いられる画素を表す図である。
【図１１】本発明の一実施例により第１の画像断片上の重要点の対応候補のリストの幾何学的関係を第２の画像断片の画素に適用して第１と第２の画像断片間の精密整列を見つけるステップを記述したフローチャートである。
【図１２】４つのオーバーラップした画像断片のユーザによる整列の例を示す図である。
【図１３】本発明の一実施例により整列された図１２の画像断片を示す図である。
【図１４】図１２中の一つの画像断片を拡大して示す図である。
【図１５】図１２中の一つの画像断片を拡大して示す図である。
【図１６】画像断片のオーバーラップ部分に重要点検出のためのセル格子をオーバーレイした状態を示す図である。
【図１７】第１重要点を囲むテンプレート領域を示す図である。
【図１８】第２重要点を囲むテンプレート領域を示す図である。
【図１９】第１重要点とのマッチングに用いられる探索領域を示す図である。
【図２０】第２重要点とのマッチングに用いられる探索領域を示す図である。
【図２１】図１９の探索領域を、第１重要点との整列候補から除外された画素を黒で塗りつぶして示す図である。
【図２２】図２０の探索領域を、第２重要点との整列候補から除外された画素を黒で塗りつぶして示す図である。
【図２３】重要点に対する整列候補をマークした画像断片のオーバーラップ部分を示す図である。
【符号の説明】
１０  コンピュータシステム
１２  バス
１４  中央処理装置
１６  システムメモリ
１８  入出力コントローラ
２０  外部装置
２２  パラレルポート
２４  ディスプレイスクリーン
２６  ディスプレイアダプター
２８  シリアルポート
３０  キーボード
３２  固定ディスクドライブ
３３  フロッピーディスクドライブ
３３Ａ  フロッピーディスク
３４  読み取り装置
３６  外部インターフェイス
３８  マウス
４０  タッチスクリーン
３０２  スキャナ
３０４  メモリ
３０６  ＣＰＵ（中央処理装置）
３０８  ディスプレイ
３１０  タッチスクリーン
３１２  プリンタ
９０２，９０４，９０６，９０８  画像断片
１１０２  セル格子
１１０４，１１０６，１１０８  重要点候補
１１１０，１１１２  テンプレート領域
１１１４，１１１６  探索領域
１１１８，１１２０，１１２６  整列候補
【図１】
0004125393.tif 000005
【図２】
0004125393.tif 000006
【図３】
0004125393.tif 000007
【図４】
0004125393.tif 000008
【図５】
0004125393.tif 000009
【図６】
0004125393.tif 000010
【図７】
0004125393.tif 000011
【図８】
0004125393.tif 000012
【図９】
0004125393.tif 000013
【図１０】
0004125393.tif 000014
【図１１】
0004125393.tif 000015
【図１２】
0004125393.tif 000016
【図１３】
0004125393.tif 000017
【図１４】
0004125393.tif 000018
【図１５】
0004125393.tif 000019
【図１６】
0004125393.tif 000020
【図１７】
0004125393.tif 000021
【図１８】
0004125393.tif 000022
【図１９】
0004125393.tif 000023
【図２０】
0004125393.tif 000024
【図２１】
0004125393.tif 000025
【図２２】
0004125393.tif 000026
【図２３】
0004125393.tif 000027