(57)【要約】【課題】より少ない階層数で位置合わせを行うことで、処理負荷を減少させてサブ画素での位置合わせをすることができるようにした画像処理装置を提供する。【解決手段】画像処理装置の画像入力手段は、２枚の画像を入力し、相違度最小座標算出手段は、前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出し、制御手段は、レイヤ値が所望のレイヤ値であれば、前記相違度最小座標算出手段によって算出した相違度最小座標を出力させる。【選択図】図１
2008217053.tif 000002
【特許請求の範囲】
【請求項１】
２枚の画像を入力する画像入力手段と、
前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出する相違度最小座標算出手段と、
レイヤ値が所望のレイヤ値であれば、前記相違度最小座標算出手段によって算出した相違度最小座標を出力させる制御手段
を具備することを特徴とする画像処理装置。
【請求項２】
２枚の画像を入力する画像入力手段と、
前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出する相違度最小座標算出手段と、
レイヤ値が所望のレイヤ値でなければ、任意の数に減らしたレイヤ値のグリッドから相違度最小座標を前記相違度最小座標算出手段に算出させる制御手段
を具備することを特徴とする画像処理装置。
【請求項３】
前記制御手段は、前記相違度最小座標算出手段によって算出された相違度最小座標を次の減少させたレイヤ値で量子化する
ことを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
グリッドはレイヤ値の画素分だけ互いに離れた画素とする
ことを特徴とする請求項１、２又は３に記載の画像処理装置。
【請求項５】
前記相違度最小座標算出手段は、グリッドの中心の相違度が最小となるグリッドにおいて相違度最小座標を算出する
ことを特徴とする請求項１、２、３又は４に記載の画像処理装置。
【請求項６】
前記制御手段は、前記相違度最小座標算出手段によってグリッドの中心の相違度が最小となるグリッドを決定するためにレイヤ内で探索を行う
ことを特徴とする請求項５に記載の画像処理装置。
【請求項７】
前記制御手段が行うレイヤ内でのグリッドの探索は、レイヤ値の画素分だけ離れた画素の相違度のなかで、中心の画素の相違度が最小となる場合に終了する
ことを特徴とする請求項６に記載の画像処理装置。
【請求項８】
前記制御手段が行うレイヤ内でのグリッドの探索は、レイヤ値の画素分だけ離れた画素の相違度のなかで、中心の画素の相違度が最小でない場合、相違度が最小の座標を中心にレイヤ値の画素分だけ離れた画素の相違度で未算出の相違度を算出する
ことを特徴とする請求項６に記載の画像処理装置。
【請求項９】
前記制御手段は、前記相違度最小座標算出手段によって算出された相違度最小座標の位相で補間画像を生成し、
前記相違度最小座標算出手段は、前記制御手段によって生成された該補間画像と相違度最小座標から次のレイヤでのグリッドの相違度を算出し、該レイヤの相違度最小座標を算出する
ことを特徴とする請求項１又は２に記載の画像処理装置。
【請求項１０】
画像処理システムを、
２枚の画像を入力する画像入力手段と、
前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出する相違度最小座標算出手段と、
レイヤ値が所望のレイヤ値であれば、前記相違度最小座標算出手段によって算出した相違度最小座標を出力させる制御手段
として機能させることを特徴とする画像処理プログラム。
【請求項１１】
画像処理システムを、
２枚の画像を入力する画像入力手段と、
前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出する相違度最小座標算出手段と、
レイヤ値が所望のレイヤ値でなければ、任意の数に減らしたレイヤ値のグリッドから相違度最小座標を前記相違度最小座標算出手段に算出させる制御手段
として機能させることを特徴とする画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理プログラムに関する。
【背景技術】
【０００２】
複数の画像同士で似たテクスチャーを重ね合わせるパノラマ画像の生成や、Ｓｕｐｅｒ  ｒｅｓｏｌｕｔｉｏｎ技術を用いた画像の高解像度化、また動画像圧縮における動き補償処理のために、高速・高精度な画像の位置合わせ技術が必要不可欠である。
特に、位置合わせの精度をサブ画素の精度とし、かつ高速な処理が求められている。
【０００３】
例えば、特許文献１には、画像が撮像装置の特性やノイズなどの影響で変形を受けていても精度が低下しない、サブピクセル精度の位置合わせ手法を提供することを課題とし、フィッティング範囲設定手段において、入力画像の微分値の大きな画素の連なりをフィッティング範囲と設定し、関数フィッティング手段において、各フィッティング範囲に対し、単峰性の関数をフィッティングしエッジ位置をサブピクセル精度で求め、次に、ピクセル精度位置合わせ手段において位置合わせを行う。対応候補曲線生成手段において、ある一方の画像上のエッジ点に対して、他方の画像上の対応する複数のエッジ点を曲線で結び対応候補曲線とし、位置ずれ算出手段において、全ての対応候補曲線が交差する点、若しくは最も密集する点を求め、その座標を一方の画像からもう一方の画像に対するサブピクセル精度の変位とみなすことが開示されている。
【０００４】
また、これらに関連する技術として、例えば、特許文献２には、画像の位置合わせをサブピクセル精度で行う技術が記載されている。すなわち、Ｎ次元類似度を考慮することで、画像間対応パラメータを少ない計算量で安定かつ高速に高精度で同時に推定できるようにした、画像のサブピクセルマッチングにおける多パラメータ高精度同時推定方法及び多パラメータ高精度同時推定プログラムを提供することを課題とし、離散的な位置で得られた画像間のＮ次元類似度値が、ある１つのパラメータ軸に対して平行な直線上で最大又は最小となるサブサンプリング位置を求め、求められた前記サブサンプリング位置に最も近似するＮ次元超平面を各パラメータ軸毎に求め、求められた超平面の交点からサブサンプリンググリッド推定位置を求めることが開示されている。
【特許文献１】特許第２８９７７７２号公報
【特許文献２】再表２００４−０６３９９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
画像の高解像度化のためにサブ画素の高精度な位置合わせをしようとすると、１画素毎の相違度を算出するため膨大な処理時間がかかるのが問題となる。また階層的に探索する方式では、あらかじめ決められた階層数だけ相違度の算出と補間処理が必要となることで処理時間が増大し、階層数を少なくすると精度が悪くなるという問題があった。
本発明は、このような背景技術の状況のなかでなされたもので、より少ない階層数で位置合わせを行うことで、処理負荷を減少させてサブ画素での位置合わせをすることができるようにした画像処理装置及び画像処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００６】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
［１］  ２枚の画像を入力する画像入力手段と、
前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出する相違度最小座標算出手段と、
レイヤ値が所望のレイヤ値であれば、前記相違度最小座標算出手段によって算出した相違度最小座標を出力させる制御手段
を具備することを特徴とする画像処理装置。
【０００７】
［２］  ２枚の画像を入力する画像入力手段と、
前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出する相違度最小座標算出手段と、
レイヤ値が所望のレイヤ値でなければ、任意の数に減らしたレイヤ値のグリッドから相違度最小座標を前記相違度最小座標算出手段に算出させる制御手段
を具備することを特徴とする画像処理装置。
【０００８】
［３］  前記制御手段は、前記相違度最小座標算出手段によって算出された相違度最小座標を次の減少させたレイヤ値で量子化する
ことを特徴とする［１］又は［２］に記載の画像処理装置。
【０００９】
［４］  グリッドはレイヤ値の画素分だけ互いに離れた画素とする
ことを特徴とする［１］、［２］又は［３］に記載の画像処理装置。
【００１０】
［５］  前記相違度最小座標算出手段は、グリッドの中心の相違度が最小となるグリッドにおいて相違度最小座標を算出する
ことを特徴とする［１］、［２］、［３］又は［４］に記載の画像処理装置。
【００１１】
［６］  前記制御手段は、前記相違度最小座標算出手段によってグリッドの中心の相違度が最小となるグリッドを決定するためにレイヤ内で探索を行う
ことを特徴とする［５］に記載の画像処理装置。
【００１２】
［７］  前記制御手段が行うレイヤ内でのグリッドの探索は、レイヤ値の画素分だけ離れた画素の相違度のなかで、中心の画素の相違度が最小となる場合に終了する
ことを特徴とする［６］に記載の画像処理装置。
【００１３】
［８］  前記制御手段が行うレイヤ内でのグリッドの探索は、レイヤ値の画素分だけ離れた画素の相違度のなかで、中心の画素の相違度が最小でない場合、相違度が最小の座標を中心にレイヤ値の画素分だけ離れた画素の相違度で未算出の相違度を算出する
ことを特徴とする［６］に記載の画像処理装置。
【００１４】
［９］  前記制御手段は、前記相違度最小座標算出手段によって算出された相違度最小座標の位相で補間画像を生成し、
前記相違度最小座標算出手段は、前記制御手段によって生成された該補間画像と相違度最小座標から次のレイヤでのグリッドの相違度を算出し、該レイヤの相違度最小座標を算出する
ことを特徴とする［１］又は［２］に記載の画像処理装置。
【００１５】
［１０］  画像処理システムを、
２枚の画像を入力する画像入力手段と、
前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出する相違度最小座標算出手段と、
レイヤ値が所望のレイヤ値であれば、前記相違度最小座標算出手段によって算出した相違度最小座標を出力させる制御手段
として機能させることを特徴とする画像処理プログラム。
【００１６】
［１１］  画像処理システムを、
２枚の画像を入力する画像入力手段と、
前記画像入力手段によって入力された画像を対象として、レイヤ値に基づくグリッドの相違度から相違度最小座標を算出する相違度最小座標算出手段と、
レイヤ値が所望のレイヤ値でなければ、任意の数に減らしたレイヤ値のグリッドから相違度最小座標を前記相違度最小座標算出手段に算出させる制御手段
として機能させることを特徴とする画像処理プログラム。
【発明の効果】
【００１７】
本発明にかかる画像処理装置及び画像処理プログラムによれば、本構成を有していない場合に比較して、より少ない階層数で位置合わせを行うことで、処理負荷を減少させてサブ画素での位置合わせをすることができる。
【発明を実施するための最良の形態】
【００１８】
＜実施の形態における背景技術＞
まず、実施の形態の理解を容易にするために、実施の形態における背景技術及びその背景技術を実現した場合の状況について説明する。
前述した特許文献１には、整数位置３点の相違度を用いて、３点を通る２次曲線を引いて、その２次曲線を最小化する位置を求める手法が記載されている。
つまり、サブ画素の精度で２画像間の位置合わせを行う方式として、画像間の位置と相違度の関係が下に凸の２次曲線となる性質（図１８（Ｂ）参照）を利用し、この凸となる相違度最小座標を求めるために、周辺の相違度から近似的に推測して求める方式が提案されている。
しかし、凸となる相違度が最小となる周辺を特定するためには、画像間をずらしながら１画素単位に相違度を算出し、その相違度が最小となる位置を特定する必要がある。相違度は画像間の最小自乗誤差、絶対誤差、相関係数、などがあるが、ある位置での相違度を算出するために２画像についてラスタスキャンを行う必要がある。すなわち、全画素の走査順での相違度の算出が必要となる。
仮に、５１２画素×５１２画素の２画像の位置合わせを行う場合（図１８（Ａ）参照）、重なりが１画素から１画素単位にずらして相違度を算出するとなると、（５１１＋５１２＋５１１）×（５１１＋５１２＋５１１）＝２，３５３，１５６回の膨大な２画像の画素間の計算が必要（図１８（Ｃ）参照）となり、実用的ではない状況である。
【００１９】
また、特許文献２には、Ｘ軸に水平な複数の直線上で相違度が最小となる点を結ぶ直線を求め、Ｙ軸に水平な複数の直線上で相違度が最小となる点を結ぶ直線を求め、２つの直線の交点を推定値とし、そのために２５個の相違度値が必要となることが記載されている。
つまり、２画像間のサブ画素精度での位置合わせを高速に行うために、相違度計算の回数を簡略化する目的から階層的に行う方式が提案されている。
この方式では、ある階層で３×３の９画素で最小相違度の画素を中心に次の階層でより狭い範囲の最小相違度座標を求めていく。
したがって、あらかじめ決められたグリッド上でのみ相違度を算出するため、高精度にするためには階層数が多数になる。またサブ画素の階層では階層毎に補間画像を生成する。
仮に、０．１画素以下の精度で位置を合わせる場合、もれなく探索するためには０．５画素ステップで階層的に絞り込む必要がある。このため４画素から始めた場合、４画素から０．０６２５画素までの７段階の階層が必要となる（図１９参照）。この間、９回＋６段階×８回＝５７回の相違度の算出と３回の補間画像の生成処理が必要となり、処理時間は、依然として実用的ではない状況である。なお、図１９は、階層の状況を示しており、白の四角が４画素の段階の階層であり、以下、白三角が２画素、黒丸が１画素、黒四角が０．５画素、黒三角が０．１２５画素、白丸が０．０６２５画素（なお、０．２５画素は省略）を表している。
【００２０】
＜基本アーキテクチャ＞
２画像間の相違度（縦軸方向）と画像間の位置（横軸方向）をグラフにとると、下に凸となるグラフとなる（例えば、図１８（Ｂ）参照、２次元になった場合は２次局面のグラフとなる）。この性質を利用し、図１（Ａ）に示すＳ０からＳ８のように９点の相違度を通る２次曲面を推定し、相違度の最小座標を求めることができる。
この方式の９点をｎ画素幅で算出することで、精度が悪くても相違度最小座標の荒振るいをすることが可能となる。ここで、ｎはレイヤ値である。したがって、グリッドはレイヤ値だけ互いに離れた３×３の９画素となる。
求められた相違度最小座標に基づいて、さらにｎ−ｍ画素幅の９点で相違度最小座標を算出することでさらに精度が高い座標が得られる（図１（Ｂ）参照）。
これらｎ，ｍは画像にあわせて最適な値を算出し、繰り返し数を設定することで、高い精度を維持しながら処理時間を低減することができる。
以下、相違度最小座標を求めるための座標をグリッドという。つまり、図１（Ａ）に示した相違度最小座標を求めるＳ０〜Ｓ８の９座標がグリッドとなる。通常はグリッドの座標間を１画素とすることで、サブ画素の精度で相違度最小座標を算出する。またこのｎをレイヤと呼ぶ。
【００２１】
＜第１の実施の形態＞
以下、図面に基づき本発明を実現するにあたっての好適な各種の実施の形態を説明する。
図２は、第１の実施の形態の概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはプログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、プログラム、システム及び方法の説明をも兼ねている。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示等）を含む。
また、システムとは、複数のコンピュータ、ハードウェア、装置等がネットワーク等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。
【００２２】
第１の実施の形態は、レイヤ値の決定モジュール２１、レイヤのグリッドの相違度算出モジュール２２、相違度最小座標算出モジュール２３、量子化モジュール２４を有している。
レイヤ値の決定モジュール２１は、図２に示すように、レイヤのグリッドの相違度算出モジュール２２、量子化モジュール２４と接続されており、あらかじめレイヤ情報としてのレイヤの初期値（ｎ）と推移値（ｍ）を決定する。それらをレイヤのグリッドの相違度算出モジュール２２、量子化モジュール２４へ渡す。ただし、レイヤ情報の値は固定的な値としてもよいし、動的で可変的な値としてもよい。
レイヤのグリッドの相違度算出モジュール２２は、図２に示すように、レイヤ値の決定モジュール２１、量子化モジュール２４、相違度最小座標算出モジュール２３と接続されており、２枚の画像を入力し、レイヤ値の決定モジュール２１からレイヤ情報を受け取り、このレイヤ値及び画像データに基づいてレイヤのグリッドの相違度を算出する。その算出した相違度を相違度最小座標算出モジュール２３へ渡す。なお、画像を入力するとは、具体的には、スキャナによって画像を入力すること、ファックスによって通信回線を介して外部機器から画像を入力すること、記憶媒体から画像を入力すること等がある。
【００２３】
相違度最小座標算出モジュール２３は、図２に示すように、レイヤのグリッドの相違度算出モジュール２２、量子化モジュール２４と接続されており、レイヤのグリッドの相違度算出モジュール２２によって算出されたグリッドの相違度に基づいてそのレイヤの相違度最小座標を算出する。そして、相違度最小座標を量子化モジュール２４へ渡す。又は、量子化モジュール２４による制御によって、相違度最小座標を画像合成する処理部へ渡す。相違度最小座標算出モジュール２３による処理については、図５、図６、図７を用いて後述する。
量子化モジュール２４は、図２に示すように、レイヤ値の決定モジュール２１、レイヤのグリッドの相違度算出モジュール２２、相違度最小座標算出モジュール２３と接続されており、レイヤ値の決定モジュール２１からレイヤ情報、相違度最小座標算出モジュール２３によって算出された相違度最小座標を受け取り、座標値の量子化値をレイヤのグリッドの相違度算出モジュール２２へ渡す。つまり、レイヤが目標レイヤ（例えば、レイヤ＝１）でなければ、相違度最小座標算出モジュール２３によって算出された相違度最小座標値を次のレイヤで量子化を行い、再びそのレイヤのグリッドの相違度を算出するレイヤのグリッドの相違度算出モジュール２２へフォールバックする。目標レイヤで相違度最小座標値が算出されたら、その値を出力する。量子化モジュール２４による処理については、図４を用いて後述する。
【００２４】
図３に示すフローチャートを用いて、第１の実施の形態による処理、働き（動作）を説明する。
ステップＳ３０２では、レイヤ値の決定モジュール２１がレイヤ値（ｎ）を決定する。つまり、変数ｎにレイヤ値を代入する。
ステップＳ３０４では、レイヤのグリッドの相違度算出モジュール２２が、ステップＳ３０２又はステップＳ３１０で決定されたレイヤ（ｎ）のグリッドを決定する。
ステップＳ３０６では、相違度最小座標算出モジュール２３が、ステップＳ３０４で決定されたレイヤ（ｎ）の相違度最小座標を算出する。
【００２５】
ステップＳ３０８では、量子化モジュール２４が目標としているレイヤであるか否かを判断する。かかる判断において、目標レイヤとなっている場合はステップＳ３１４の処理へ進み、目標レイヤとはなっていない場合はステップＳ３１０の処理へ進み、ステップＳ３０４、ステップＳ３０６の処理を繰り返す。
ステップＳ３１０では、量子化モジュール２４が次のレイヤを決定する。つまり、現在のレイヤ（ｎ）から推移値（ｍ、又はレイヤ値変更値）を減算し、次のレイヤ（ｎ）とする。より具体的には、変数ｎに現在のレイヤ（ｎ）−推移値（ｍ）を代入する。
ステップＳ３１２では、量子化モジュール２４がステップＳ３１０で決定されたレイヤ（ｎ）で、相違度最小座標を量子化する。そして、ステップＳ３０４の処理へ戻る。
ステップＳ３１４では、目標レイヤに達しているので、量子化モジュール２４は相違度最小座標算出モジュール２３によって算出された相違度最小座標を、画像を合成等する処理部へ送出する。
【００２６】
図４を用いて、量子化モジュール２４等による相違度最小座標の量子化処理についてより詳細に説明する。
例えば、レイヤｎ＝３において算出された相違度最小座標を、レイヤｎ＝１で量子化する手順を以下に説明する。推移値ｍ＝２とする。
レイヤｎ＝３で求められたグリッド（図４に示す白丸）の９点の相違度を用いて算出した相違度最小座標（図４に示す黒丸）に対して、最も近いレイヤｎ＝１のグリッド（図４に示す黒三角）を算出し、これを量子化座標としてレイヤのグリッドの相違度算出モジュール２２へ送出する。
その後、次の処理によって、量子化された相違度最小座標（図４に示す黒三角）を中心にレイヤｎ＝１の９点のグリッド（図４に示す白三角）の相違度に基づいて、相違度最小座標を算出する。
【００２７】
相違度最小座標算出モジュール２３による処理である相違度が最小となる座標を算出する方法は、次に示すようないくつかの手法がある。
（１）手法１（特許文献１に記載されている技術）
図５に示すように整数位置の３点の値がわかっているとき、その３点を通る２次曲線を引いて、その２次曲線を最小化する位置（最適値）を求めるものである。
（２）手法２（特許文献２に記載されている技術）
ある横線上で相違度を最小化するｘの値を求める。そして、複数の横線上でこのようなｘの値を求める。この点（図６の白丸）を通る直線を引く。
さらに、ある縦線上で相違度を最小化するｙの値を求める。そして、複数の縦線上でこのようなｙの値を求める。この点（図６の黒丸）を通る直線を引く。
このように求めた２つの直線の交点を求める最適値とするものである。
（３）手法３
相違度が最小となる座標を求めるためのグリッドの９点をおおよそ通る２次曲面を推定し（図７の破線で示すのが推定２次曲面）、この曲面が最小となる（ｘ，ｙ）の値を求める。つまり、入力された画像を整数グリッド上で変換し、相違度を求める関数を近似する２次曲面の係数を算出し、算出された係数のサブ量子化精度での推定を行うものである。そして、近似の場合に各整数グリッド位置に関する重み付けを行い、その重み付けは、各整数グリッドを中心とするボロノイ分割領域の面積又は超体積であるようにしてもよい。
【００２８】
＜第２の実施の形態＞
図８〜図１３を用いて、第２の実施の形態を説明する。
図９に示すようにＳ０からＳ８（Ｓ０は９点の中心に位置する）のグリッドのなかでＳ０が最小となるグリッドを最小グリッドと呼ぶ。この最小グリッドの相違度を用いて相違度最小座標を算出することは内挿になることから、より精度が高くなる。第２の実施の形態は、最小グリッドを求め、この最小グリッドを用いることでより精度が高くなる。
第２の実施の形態は、レイヤ値の決定モジュール８１、レイヤの最小グリッドの相違度算出モジュール８２、相違度最小座標算出モジュール８３、量子化モジュール８４を有している。
レイヤ値の決定モジュール８１は、図８に示すように、レイヤの最小グリッドの相違度算出モジュール８２、量子化モジュール８４と接続されており、第１の実施の形態のレイヤ値の決定モジュール２１と同様である。
レイヤの最小グリッドの相違度算出モジュール８２は、図８に示すように、レイヤ値の決定モジュール８１、量子化モジュール８４、相違度最小座標算出モジュール８３と接続されており、２枚の画像を入力し、レイヤ値の決定モジュール８１からレイヤ情報を受け取り、このレイヤ値及び画像データに基づいてレイヤの最小グリッドが決定され、その最小グリッドの相違度を算出する。その算出した相違度を相違度最小座標算出モジュール８３へ渡す。
【００２９】
相違度最小座標算出モジュール８３は、図８に示すように、レイヤの最小グリッドの相違度算出モジュール８２、量子化モジュール８４と接続されており、第１の実施の形態の相違度最小座標算出モジュール２３と同様である。ただし、レイヤの最小グリッドの相違度算出モジュール８２によって算出された最小グリッドの相違度に基づいて相違度最小座標を算出する。
量子化モジュール８４は、図８に示すように、レイヤ値の決定モジュール８１、レイヤの最小グリッドの相違度算出モジュール８２、相違度最小座標算出モジュール８３と接続されており、第１の実施の形態の量子化モジュール２４と同様である。ただし、対象となるグリッドは最小グリッドである。量子化モジュール８４による処理については、図１１を用いて後述する。
【００３０】
図１０に示すフローチャートを用いて、第２の実施の形態による処理、働き（動作）を説明する。
ステップＳ１００２では、レイヤ値の決定モジュール８１がレイヤ値（ｎ）を決定する。つまり、変数ｎにレイヤ値を代入する。
ステップＳ１００４では、レイヤの最小グリッドの相違度算出モジュール８２が、ステップＳ１００２又はステップＳ１０１０で決定されたレイヤ（ｎ）のグリッドから最小グリッドを探索し決定する。最小グリッドの探索については、図１２，図１３を用いて後述する。
ステップＳ１００６では、相違度最小座標算出モジュール８３が、ステップＳ１００４で決定されたレイヤ（ｎ）の相違度最小座標を算出する。
【００３１】
ステップＳ１００８では、量子化モジュール８４が目標としているレイヤであるか否かを判断する。かかる判断において、目標レイヤとなっている場合はステップＳ１０１４の処理へ進み、目標レイヤとはなっていない場合はステップＳ１０１０の処理へ進み、ステップＳ１００４、ステップＳ１００６の処理を繰り返す。
ステップＳ１０１０では、量子化モジュール８４が次のレイヤを決定する。つまり、現在のレイヤ（ｎ）から推移値（ｍ）を減算し、次のレイヤ（ｎ）とする。より具体的には、変数ｎに現在のレイヤ（ｎ）−推移値（ｍ）を代入する。
ステップＳ１０１２では、量子化モジュール８４がステップＳ１０１０で決定されたレイヤ（ｎ）で、相違度最小座標を量子化する。そして、ステップＳ１００４の処理へ戻る。
ステップＳ１０１４では、目標レイヤに達しているので、量子化モジュール８４は相違度最小座標算出モジュール８３によって算出された相違度最小座標を、画像を合成等する処理部へ送出する。
【００３２】
図１１を用いて、量子化モジュール８４等による相違度最小座標の量子化処理についてより詳細に説明する。
例えば、レイヤｎ＝３において算出された相違度最小座標を、レイヤｎ＝１で量子化する手順を以下に説明する。推移値ｍ＝２とする。
レイヤｎ＝３で求められた最小グリッド（図１１に示す白丸）の９点の相違度を用いて算出した相違度最小座標（図１１に示す黒丸）に対して、最も近いレイヤｎ＝１のグリッド（図１１に示す黒三角）を算出し、これを量子化座標としてレイヤの最小グリッドの相違度算出モジュール８２へ送出する。
その後、次の処理によって、量子化された相違度最小座標（図１１に示す黒三角）を中心にレイヤｎ＝１の９点のグリッド（図１１に示す白三角）が最小グリッドかどうかの判定を行う。そして、相違度最小座標を算出する。
【００３３】
あるレイヤにおける相違度の最小グリッドの探索手順について、図１２に示すフローチャート、図１３を用いて、より詳細に説明する。
ステップＳ１２０２では、レイヤの最小グリッドの相違度算出モジュール８２が、初期のグリッドについての相違度を算出する。
以下、注目する９点のグリッドが図１３に示す３つのケースのいずれであるかによって処理を異ならせる。
ステップＳ１２０４では、注目する９点のグリッドがケース１であるか否かを判断する。ケース１である場合は終了し（ステップＳ１２１２）、ケース１でない場合はステップＳ１２０６の処理へ進む。つまり、注目する９点のグリッド（最初は初期のグリッド）の相違度のなかで最も小さい値が９点の中心だった場合（図１３（Ａ）に示すケース１の灰色の丸）は、この９点のグリッドが最小グリッドになるため、終了する。つまり、レイヤ値の画素分だけ離れた画素の相違度のなかで、中心の画素の相違度が最小となる場合に終了する。
【００３４】
ステップＳ１２０６では、注目する９点のグリッドがケース２であるか否かを判断する。ケース２である場合はステップＳ１２１０の処理へ進み、ケース２でない場合はステップＳ１２０８の処理へ進む。つまり、ケース１でない場合、９点のグリッドのなかで中心の４近傍（図１３（Ｂ）に示すケース２の灰色の丸）のうちの１点のグリッドの相違度が最小（例えば、図１３（Ｂ）に示すケース２の太線の灰色の丸）であるか否か（ケース２であるか否か）を判断する。
ステップＳ１２１０では、ステップＳ１２０６でケース２であると判断されたので、そのケース２の相違度最小座標の外側を探索する。相違度最小の座標を中心にレイヤ値の画素分だけ離れた画素の相違度で未算出の相違度を算出する。つまり、この相違度最小座標を中心にした９点の相違度のうち、ステップＳ１２０２では算出されていないグリッド（図１３（Ｂ）に示すケース２の３つの黒丸）の相違度を算出する。そして、ステップＳ１２０４の処理へ戻る。
【００３５】
ステップＳ１２０８では（ケース１でも２でもない場合）、ケース３の相違度最小座標の外側を探索する。相違度最小の座標を中心にレイヤ値の画素分だけ離れた画素の相違度で未算出の相違度を算出する。つまり、９点のグリッドのなかで中心に対して斜めの位置（図１３（Ｃ）に示すケース３の灰色の丸）の１つが相違度最小だった場合（例えば、図１３（Ｃ）に示すケース３の太線の灰色の丸）は、この相違度最小座標を中心にした９点の相違度のうち、ステップＳ１２０２では算出されていないグリッド（図１３（Ｃ）に示すケース３の５つの黒丸）の相違度を算出する。そして、ステップＳ１２０４の処理へ戻る。
【００３６】
＜第３の実施の形態＞
図１４〜図１６を用いて、第３の実施の形態を説明する。
前述の実施の形態と異なるところは、次のレイヤで相違度最小座標の量子化を行わず、算出された相違度算出座標の位相で補間画像を生成して、その次のレイヤの相違度最小座標を求める点である。第３の実施の形態は、対象によるが他の実施の形態よりも処理負荷が少なくなる場合がある。
第３の実施の形態は、レイヤ値の決定モジュール１４１、レイヤのグリッドの相違度算出モジュール１４２、相違度最小座標算出モジュール１４３、補間画像作成モジュール１４４を有している。
レイヤ値の決定モジュール１４１は、図１４に示すように、レイヤのグリッドの相違度算出モジュール１４２、補間画像作成モジュール１４４と接続されており、第１の実施の形態のレイヤ値の決定モジュール２１と同様である。
レイヤのグリッドの相違度算出モジュール１４２は、図１４に示すように、レイヤ値の決定モジュール１４１、補間画像作成モジュール１４４、相違度最小座標算出モジュール１４３と接続されており、第１の実施の形態のレイヤのグリッドの相違度算出モジュール２２又は第２の実施の形態のレイヤの最小グリッドの相違度算出モジュール８２と同様である。
【００３７】
相違度最小座標算出モジュール１４３は、図１４に示すように、レイヤのグリッドの相違度算出モジュール１４２、補間画像作成モジュール１４４と接続されており、第１の実施の形態の相違度最小座標算出モジュール２３と同様である。
補間画像作成モジュール１４４は、図１４に示すように、レイヤ値の決定モジュール１４１、レイヤのグリッドの相違度算出モジュール１４２、相違度最小座標算出モジュール１４３と接続されており、相違度最小座標算出モジュール１４３によって算出された相違度最小座標を受け取り、座標値及び補間画像をレイヤのグリッドの相違度算出モジュール１４２へ渡す。つまり、レイヤが目標レイヤ（例えば、レイヤ＝１）でなければ、相違度最小座標算出モジュール１４３によって算出された相違度最小座標値の位相に基づいて補間画像を生成し、相違度最小座標及び補間画像に基づいてレイヤのグリッドの相違度を算出するレイヤのグリッドの相違度算出モジュール１４２へフォールバックする。目標レイヤで相違度最小座標値が算出されたら、その値を出力する。補間画像作成モジュール１４４による補間画像の生成処理については、図１６を用いて後述する。
【００３８】
図１５に示すフローチャートを用いて、第３の実施の形態による処理、働き（動作）を説明する。
ステップＳ１５０２では、レイヤ値の決定モジュール１４１がレイヤ値（ｎ）を決定する。つまり、変数ｎにレイヤ値を代入する。
ステップＳ１５０４では、レイヤのグリッドの相違度算出モジュール１４２が、ステップＳ１５０２又はステップＳ１５１０で決定されたレイヤ（ｎ）のグリッドを決定する。
ステップＳ１５０６では、相違度最小座標算出モジュール１４３が、ステップＳ１５０４で決定されたレイヤ（ｎ）の相違度最小座標を算出する。
【００３９】
ステップＳ１５０８では、補間画像作成モジュール１４４が目標としているレイヤであるか否かを判断する。かかる判断において、目標レイヤとなっている場合はステップＳ１５１４の処理へ進み、目標レイヤとはなっていない場合はステップＳ１５１０の処理へ進み、ステップＳ１５０４、ステップＳ１５０６の処理を繰り返す。
ステップＳ１５１０では、補間画像作成モジュール１４４が次のレイヤを決定する。つまり、現在のレイヤ（ｎ）から推移値（ｍ）を減算し、次のレイヤ（ｎ）とする。より具体的には、変数ｎに現在のレイヤ（ｎ）−推移値（ｍ）を代入する。
ステップＳ１５１２では、補間画像作成モジュール１４４がステップＳ１５１０で決定されたレイヤ（ｎ）で、相違度最小座標の位相で補間画像を生成する。そして、ステップＳ１５０４の処理へ戻る。
ステップＳ１５１４では、目標レイヤに達しているので、補間画像作成モジュール１４４は相違度最小座標算出モジュール１４３によって算出された相違度最小座標を、画像を合成等する処理部へ送出する。
【００４０】
図１６を用いて、相違度最小座標の位相による補間画像の生成処理について説明する。
例えば、レイヤｎ＝３における相違度最小座標の位相から補間画像を生成し、レイヤｎ＝１のグリッドの相違度を算出する手順を以下に説明する。推移値ｍ＝２とする。
レイヤｎ＝３で求められたグリッド（図１６に示す白丸）の９点の相違度を用いて算出した相違度最小座標（図１６に示す黒丸）に対して、この座標値を位相とする補間画像を生成する（図１６の細い点線による格子を参照）。
その後、次の処理によって、レイヤｎ＝１のグリッド（図１６に示す三角）を用いて、このグリッドの相違度を算出する。
【００４１】
＜実施の形態の具現＞
以上の実施の形態によって、サブ画素単位の精度を維持したまま、高速に２画像間の位置合わせが可能となる。
例えば、５１２画素×５１２画素の２画像の位置合わせを行う場合、背景技術では２，３５３，１５６回の画素間の計算が必要だったが、例えばｎ＝２５５、ｍ＝２５４（次のｎを１、つまり２階層の例である）とすると画素間の計算は９点×２階層＝１８回となり、１３０，７３０倍の高速化が望めることになる。
実際は、ｎの初期値が大きいと次の階層の相違度最小座標の精度が落ち、最小グリッドの探索処理が増えることになる。このため、より精度を高めるために、ｎ＝４、ｍ＝３としても１階層目１２８×１２８点＝１６，３８４回（実際には探索処理が最小グリッドまで最短に到達するためもっと少ない）と、２階層目の９回との合計１６，３９３回となり１４３倍以上の高速化となる。
また背景技術に示した階層化の方式と比較しても０．１画素の精度とすると、ｎ＝４から始めたとして、階層化方式は９回＋６段階×８回＝５７回の算出及び３回の補間画像の生成が必要となり、特に補間画像の生成に処理時間がとられる。本実施の形態ではｎ＝４，ｍ＝３として９回＋９回＝１８回の算出のみで終わることになる。
また、前記のようにレイヤを制御することで、トレードオフとなる位置精度と処理時間のなかで最適な制御を行うことができるようになる。
また、以上の実施の形態において、画像の中心を初期のグリッドとして決定するようにしてもよい。また、画像内の最も画素値が多い画素の重心を初期のグリッドとして決定するようにしてもよい。このようにすることによって、階層を減らして、より早く収束させることができるようになる。
【００４２】
＜ハードウェア構成例等＞
図１７を参照して、前述した実施の形態のハードウェア構成例について説明する。図１７に示す構成は、例えばパーソナルコンピュータ（ＰＣ）などによって構成されるものであり、スキャナ等のデータ読み取り部１７１７と、プリンタなどのデータ出力部１７１８を備えたハードウェア構成例を示している。
【００４３】
ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１７０１は、前述の実施の形態において説明した各種のモジュール、すなわち、レイヤのグリッドの相違度算出モジュール２２、相違度最小座標算出モジュール２３、量子化モジュール２４等の各モジュールの実行シーケンスを記述したコンピュータ・プログラムにしたがって処理を実行する制御部である。
【００４４】
ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１７０２は、ＣＰＵ１７０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１７０３は、ＣＰＵ１７０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス１７０４により相互に接続されている。
【００４５】
ホストバス１７０４は、ブリッジ１７０５を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス１７０６に接続されている。
【００４６】
キーボード１７０８、マウス等のポインティングデバイス１７０９は、操作者により操作される入力デバイスである。ディスプレイ１７１０は、液晶表示装置又はＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）などからなり、各種情報をテキストやイメージ情報として表示する。
【００４７】
ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）１７１１は、ハードディスクを内蔵し、ハードディスクを駆動し、ＣＰＵ１７０１によって実行するプログラムや情報を記録又は再生させる。ハードディスクは、入力された画像や合成された画像などが格納される。さらに、その他の各種のデータ処理プログラム等、各種コンピュータ・プログラムが格納される。
【００４８】
ドライブ１７１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体１７１３に記録されているデータ又はプログラムを読み出して、そのデータ又はプログラムを、インタフェース１７０７、外部バス１７０６、ブリッジ１７０５、及びホストバス１７０４を介して接続されているＲＡＭ１７０３に供給する。リムーバブル記録媒体１７１３も、ハードディスクと同様のデータ記録領域として利用可能である。
【００４９】
接続ポート１７１４は、外部接続機器１７１５を接続するポートであり、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を持つ。接続ポート１７１４は、インタフェース１７０７、及び外部バス１７０６、ブリッジ１７０５、ホストバス１７０４等を介してＣＰＵ１７０１等に接続されている。通信部１７１６は、ネットワークに接続され、外部とのデータ通信処理を実行する。データ読み取り部１７１７は、例えばスキャナであり、ドキュメントの読み取り処理を実行する。データ出力部１７１８は、例えばプリンタであり、ドキュメントデータの出力処理を実行する。
【００５０】
なお、図１７に示すハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図１７に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えば特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ：ＡＳＩＣ）等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図１７に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、複写機、ファックス、スキャナ、プリンタ、複合機（多機能複写機とも呼ばれ、スキャナ、プリンタ、複写機、ファックス等の機能を有している）などに組み込まれていてもよい。
【００５１】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組合せ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【図面の簡単な説明】
【００５２】
【図１】本実施の形態の概念的な説明図である。
【図２】第１の実施の形態の構成例についての概念的なモジュール構成図である。
【図３】第１の実施の形態による処理例を示すフローチャートである。
【図４】第１の実施の形態による相違度最小座標の量子化についての概念的な説明図である。
【図５】相違度最小座標を算出する手法の１つを示す説明図である。
【図６】相違度最小座標を算出する手法の１つを示す説明図である。
【図７】相違度最小座標を算出する手法の１つを示す説明図である。
【図８】第２の実施の形態の構成例についての概念的なモジュール構成図である。
【図９】グリッドの一例を示す説明図である。
【図１０】第２の実施の形態による処理例を示すフローチャートである。
【図１１】第２の実施の形態による相違度最小座標の量子化についての概念的な説明図である。
【図１２】第２の実施の形態による最小グリッドを探索する処理例を示すフローチャートである。
【図１３】最小グリッドを探索する処理例の説明図である。
【図１４】第３の実施の形態の構成例についての概念的なモジュール構成図である。
【図１５】第３の実施の形態による処理例を示すフローチャートである。
【図１６】第３の実施の形態による相違度最小座標の量子化についての概念的な説明図である。
【図１７】実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【図１８】背景技術を示す説明図である。
【図１９】背景技術を示す説明図である。
【符号の説明】
【００５３】
２１…レイヤ値の決定モジュール
２２…レイヤのグリッドの相違度算出モジュール
２３…相違度最小座標算出モジュール
２４…量子化モジュール
８１…レイヤ値の決定モジュール
８２…レイヤの最小グリッドの相違度算出モジュール
８３…相違度最小座標算出モジュール
８４…量子化モジュール
１４１…レイヤ値の決定モジュール
１４２…レイヤのグリッドの相違度算出モジュール
１４３…相違度最小座標算出モジュール
１４４…補間画像作成モジュール
【図１】
2008217053.tif 000003
【図２】
2008217053.tif 000004
【図３】
2008217053.tif 000005
【図４】
2008217053.tif 000006
【図５】
2008217053.tif 000007
【図６】
2008217053.tif 000008
【図７】
2008217053.tif 000009
【図８】
2008217053.tif 000010
【図９】
2008217053.tif 000011
【図１０】
2008217053.tif 000012
【図１１】
2008217053.tif 000013
【図１２】
2008217053.tif 000014
【図１３】
2008217053.tif 000015
【図１４】
2008217053.tif 000016
【図１５】
2008217053.tif 000017
【図１６】
2008217053.tif 000018
【図１７】
2008217053.tif 000019
【図１８】
2008217053.tif 000020
【図１９】
2008217053.tif 000021