画像処理装置、画像変換方法及びプログラム
【課題】複雑な計算を必要とせずに、各画像を位置合わせするための変換式または特徴点対応のインライア集合を高速に求める。
【解決手段】少なくとも２つの画像を取得し（ステップＳ１００）、第１の画像から一定の制約の下で直線上に並んだ特徴点を選択すると共に、この選択された特徴点を第２の画像上で追跡する（ステップＳ１０１〜Ｓ１０２）。この追跡により追跡された各特徴点から所定数の点を選び、これらの点を元に第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する（ステップＳ１０３〜Ｓ１０６）。そして、各評価点と第２の画像上で追跡された各特徴点との適合性を評価し（ステップＳ１０７〜Ｓ１１０）、最も適合性の高かった点の集まりを用いて画像間の変換式を算出する（ステップＳ１１２）。
【解決手段】少なくとも２つの画像を取得し（ステップＳ１００）、第１の画像から一定の制約の下で直線上に並んだ特徴点を選択すると共に、この選択された特徴点を第２の画像上で追跡する（ステップＳ１０１〜Ｓ１０２）。この追跡により追跡された各特徴点から所定数の点を選び、これらの点を元に第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する（ステップＳ１０３〜Ｓ１０６）。そして、各評価点と第２の画像上で追跡された各特徴点との適合性を評価し（ステップＳ１０７〜Ｓ１１０）、最も適合性の高かった点の集まりを用いて画像間の変換式を算出する（ステップＳ１１２）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、平面から平面への特徴点群の対応をもとに、その妥当な射影変換（ホモグラフィ）を求める画像処理装置、画像変換方法及びプログラムに関する。
【背景技術】
【０００２】
例えば、デジタルカメラ等の撮像装置では、パノラマ合成や手振れ補正などの目的で、複数の連続した画像を重ね合わせて処理することがある。ここで、画像間の特徴点の対応を定める手法として、ＲＡＮＳＡＣ（random sampling consensus）と呼ばれるロバスト化のアルゴリズムが知られている。これは、特徴点対応に誤りが含まれている場合に、アウトライア（外れ値）を除外するための計算手法であり、具体的には以下のような手順を有する。
【０００３】
すなわち、まず、ランダムに抽出した特徴点対応の小さな部分集合を用いて、仮の変換パラメータ（ここでは、射影変換行列）を求め、その変換パラメータによって変換した特徴点の座標が実際の対応点の座標と適合するか否かを判別し、その適合点数をカウントする。
【０００４】
ループにより、このランダム抽出を多数回繰り返して、適合点数が最も多かった時の適合点の集合を最終的なインライアとし、それ以外はアウトライアとして除外する。この場合、精度が必要でなければ、最終的なインライアを求めたときの変換パラメータをそのまま答えとしても良い。高精度を求めるならば、得られた最終的なインライア集合を用いてより大規模な非線形最小化アルゴリズム等によって変換パラメータを再算出することができる（例えば、非特許文献１参照）。
【０００５】
今、画像Ａと画像Ｂとの位置合わせする場合を例にして具体的に説明すると、以下のような処理手順となる。
【０００６】
図１３は従来方式による画像間の位置合わせのための処理手順を示すフローチャートである。なお、このフローチャートで示す処理は、一般的な電子計算機によって実行されるものとする。
【０００７】
まず、画像Ａと画像Ｂから複数の特徴点を抽出し（ステップＳ１１）、これらの特徴点の中の任意の４点を選び（ステップＳ１２，Ｓ１３）、これらの４点の組から画像Ａと画像Ｂを位置合わせするための変換行列（射影変換の行列式）を求める（ステップＳ１４）。この時点では、まだ適合するかどうか分からないので、仮の変換行列である。
【０００８】
ここで、画像Ａに変換行列を適用し（ステップＳ１５）、画像Ａ上の各特徴点を射影変換した座標と、それに対応する画像Ｂ上の各特徴点の座標との距離を計算する（ステップＳ１６）。その結果、両者間の距離が所定値以上の特徴点を不適合点つまりアウトライアとして除外し（ステップＳ１７）、残った適合点の総和を今回のスコアとして記録する（ステップＳ１８）。
【０００９】
このようにして、ランダムに４点を選びながら、前記同様の処理を所定回数繰り返し（ステップＳ１９）、最もスコアが良かった回の適合点を用いて変換行列を計算し、これを用いて、画像Ａと画像Ｂとの位置合わせを行う（ステップＳ２０）。
【非特許文献１】「特徴点の位置分布に基づくランダムサンプリングによる平面領域のロバストな検出法」、電子情報通信学会論文誌 D-II Vol. J88-D-II No.2 pp.313-324
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述したように、ＲＡＮＳＡＣでは、特徴点の部分集合をランダム抽出し、仮の変換行列を求めて適合点数をカウントするといった処理を繰り返すことになる。通常、この繰り返しのループは数十回以上となる。仮の変換行列を求めるために最も簡易な線形アルゴリズムを用いたとしても、ループ数が多いために計算量が非常に多くなり、処理に時間がかかる、あるいはハードウェア構成が大かがりになるなどの問題がある。
【００１１】
本発明は前記のような点に鑑みなされたもので、複雑な計算を必要とせずに、各画像を位置合わせするための変換式または特徴点対応のインライア集合を高速に求めることのできる画像処理装置、画像変換方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の請求項１に係る画像処理装置は、少なくとも２つの画像を取得する画像取得手段と、この画像取得手段によって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する特徴点選択手段と、この特徴点選択手段によって選択された特徴点を第２の画像上で追跡する追跡手段と、この追跡手段によって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する評価点生成手段と、この評価点生成手段によって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する評価手段と、この評価手段によって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する変換式算出手段とを具備したことを特徴とする。
【００１３】
また、本発明の請求項２は、請求項１記載の画像処理装置において、前記評価点生成手段は、前記追跡手段によって得られた各特徴点の中で四角形の頂点をなす４点を抽出し、その４点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成することを特徴とする。
【００１４】
また、本発明の請求項３は、請求項２記載の画像処理装置において、前記評価点生成手段は、前記四角形の頂点をなす４点から前記四角形の内点を求める第１の追加処理手段と、この第１の追加処理手段によって得られた内点と前記四角形の辺との交点である境界点を求める第２の追加処理手段と、この第２の追加処理手段によって得られた境界点と前記四角形の頂点との延長線と前四角形の辺の延長線との交点である外点を求める第３の追加処理手段とを備え、前記各追加処理手段によって得られた内点、境界点、外点を評価点として追加することを特徴とする。
【００１５】
また、本発明の請求項４は、請求項１記載の画像処理装置において、前記変換式算出手段によって得られた変換式に基づいて前記第１の画像と前記第２の画像を位置合わせてして所定の画像を生成する画像処理手段とをさらに具備したことを特徴とする。
【００１６】
本発明の請求項５に係る画像変換方法は、少なくとも２つの画像を取得する第１のステップと、この第１のステップによって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する第２のステップと、この第２のステップによって選択された特徴点を第２の画像上で追跡する第３のステップと、この第３のステップによって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する第４のステップと、この第４のステップによって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する第５のステップと、この第５のステップによって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する第６のステップとを備えたことを特徴とする
また、本発明の請求項６に係るプログラムは、コンピュータによって読み取り可能な記録媒体に記録されたプログラムであって、前記コンピュータに、少なくとも２つの画像を取得する第１の機能と、この第１の機能によって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する第２の機能と、この第２の機能によって選択された特徴点を第２の画像上で追跡する第３の機能と、この第３の機能によって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する第４の機能と、この第４の機能によって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する第５の機能と、この第５の機能によって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する第６の機能とを実現させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、複雑な計算を必要とせずに、各画像を位置合わせするための変換式または特徴点対応のインライア集合を高速に求めることができる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照して本発明の実施形態を説明する。
【００１９】
（第１の実施形態）
図１は本発明の第１の実施形態に係る画像処理装置をデジタルカメラに適用した場合の外観構成を示す図であり、図１（ａ）は主に前面の構成、同図（ｂ）は主に背面の構成を示す斜視図である。
【００２０】
このデジタルカメラ１は、略矩形の薄板状ボディ２の前面に、撮影レンズ３、セルフタイマランプ４、光学ファインダ窓５、ストロボ発光部６、マイクロホン部７などを有し、上面の（ユーザにとって）右端側には電源キー８及びシャッタキー９などが設けられている。
【００２１】
電源キー８は、電源のオン／オフ毎に操作するキーであり、シャッタキー９は、撮影時に撮影タイミングを指示するキーである。
【００２２】
また、デジタルカメラ１の背面には、撮影モード（Ｒ）キー１０、再生モード（Ｐ）キー１１、光学ファインダ１２、スピーカ部１３、マクロキー１４、ストロボキー１５、メニュー（ＭＥＮＵ）キー１６、リングキー１７、セット（ＳＥＴ）キー１８、表示部１９などが設けられている。
【００２３】
撮影モードキー１０は、電源オフの状態から操作することで自動的に電源オンとして静止画の撮影モードに移行する一方で、電源オンの状態から繰返し操作することで、静止画モード、動画モードを循環的に設定する。静止画モードは、静止画を撮影するためのモードである。また、動画モードは、動画を撮影するためのモードである。
【００２４】
前記シャッタキー９は、これらの撮影モードに共通に使用される。すなわち、静止画モードでは、シャッタキー９が押下されたときのタイミングで静止画の撮影が行われる。動画モードでは、シャッタキー９が押下されたときのタイミングで動画の撮影が開始され、シャッタキー９が再度押下されたときにその動画の撮影が終了する。
【００２５】
再生モードキー１１は、電源オフの状態から操作することで自動的に電源オンとして再生モードに移行する。
【００２６】
マクロキー１４は、静止画の撮影モードで通常撮影とマクロ撮影とを切換える際に操作する。ストロボキー１５は、ストロボ発光部６の発光モードを切換える際に操作する。メニューキー１６は、連続撮影モードを含む各種メニュー項目等を選択する際に操作する。リングキー１７は、上下左右各方向への項目選択用のキーが一体に形成されたものであり、このリングキー１７の中央に位置するセットキー１８は、その時点で選択されている項目を設定する際に操作する。
【００２７】
表示部１９は、バックライト付きのカラー液晶パネルで構成されるもので、撮影モード時には電子ファインダとしてスルー画像のモニタ表示を行う一方で、再生モード時には選択した画像等を再生表示する。
【００２８】
なお、図示はしないがデジタルカメラ１の底面には、記録媒体として用いられるメモリカードを着脱するためのメモリカードスロットや、外部のパーソナルコンピュータ等と接続するためのシリアルインタフェースコネクタとして、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）コネクタ等が設けられている。
【００２９】
図２はデジタルカメラ１の電子回路構成を示すブロック図である。
【００３０】
このデジタルカメラ１には、光学レンズ装置２１、イメージセンサ２２、メモリ２３、表示装置２４、画像処理装置２５、操作部２６、コンピュータインタフェース部２７、外部記憶ＩＯ装置２８、プログラムコード記憶装置２９、ＣＰＵ３０、メモリカード３１が備えられている。
【００３１】
光学レンズ装置２１は、撮影レンズ３を構成する図示せぬフォーカスレンズおよびズームレンズを含むレンズ光学系とその駆動部とを備えたものであり、イメージセンサ２２上に、撮影対象からの光を集光させて像を結像させる。
【００３２】
イメージセンサ２２は、結像した画像を、デジタル化した画像データとして取り込むためのものであり、例えば、ＣＣＤ（Charge Coupled Device：電荷結合素子）等によって構成される。イメージセンサ２２は、ＣＰＵ３０によって制御され、シャッタキー９が押下されなければ、プレビュー用の解像度の低いデジタルの画像データを生成し、この画像データを秒間３０枚程度の間隔で、定期的にメモリ２３に送出する。また、イメージセンサ２２は、シャッタキー９が押下されると、解像度の高い画像データを生成し、生成した画像データをメモリ２３に送出する。また、イメージセンサ２２は、ＣＰＵ３０によって撮像感度（ＩＳＯ感度）の設定可能である。
【００３３】
メモリ２３は、イメージセンサ２２からの低解像度のプレビュー画像、高解像度の画像データまたは画像処理装置２５が画像処理する元画像のデータ、処理後の画像データを一時記憶するものである。メモリ２３は、一時記憶した画像データを表示装置２４または画像処理装置２５に送り出す。
【００３４】
表示装置２４は、液晶モニタである表示部１９に画像を表示させるためのものである。表示装置２４は、メモリ２３が一時記憶した低解像度のプレビュー画像または解像度の高い画像を表示部１９に表示する。
【００３５】
画像処理装置２５は、メモリ２３に一時記憶された画像データに対して、画像データの圧縮等の画像処理を行うためのものである。
【００３６】
操作部２６は、シャッタキー９の他に、電源キー８、撮影モードキー１０、再生モードキー１１、マクロキー１４、ストロボキー１５、メニューキー１６、リングキー１７、セットキー１８などから構成され、それらのキー操作に伴う信号は直接ＣＰＵ３０へ送出される。
【００３７】
コンピュータインタフェース部２７は、デジタルカメラ１がＰＣ４０に接続されたときに、ＵＳＢのストレジクラスドライバとして動作するものである。これにより、ＰＣ４０は、デジタルカメラ１に接続されると、メモリカード３１をコンピュータの外部記憶装置として取り扱う。
【００３８】
外部記憶ＩＯ装置２８は、メモリカード３１との間で、画像データ等の入出力を行うものである。メモリカード３１は、外部記憶ＩＯ装置２８から供給された画像データ等を記憶するものである。
【００３９】
プログラムコード記憶装置２９は、ＣＰＵ３０が実行するプログラムを記憶するためのものであり、ＲＯＭやフラッシュメモリなどによって構成される。
【００４０】
ＣＰＵ３０は、プログラムコード記憶装置２９に格納されているプログラムに従って、システム全体を制御するものである。なお、メモリ２３は、ＣＰＵ３０の作業メモリとしても用いられる。
【００４１】
操作部２６のスイッチ・キーが押下されることにより、操作部２６から操作情報が送信されると、ＣＰＵ３０は、この操作情報に基づいて、イメージセンサ２２、メモリ２３、表示装置２４、画像処理装置２５等を制御する。
【００４２】
具体的には、操作部２６から撮影モードキー１０が押下された旨の操作情報が送信されると、ＣＰＵ３０は各部を撮影モードに設定する。この状態で、シャッタキー９が押下されなければ、イメージセンサ２２をプレビューモードに設定し、シャッタキー９が押下されれば、解像度の高い撮影対象画像を読み込む高解像度モードに設定する。その際、メニューキー１６の操作により連続撮影モードが設定されていれば、シャッタキー９の押下に伴い、所定枚数分の画像の読み込み処理が所定時間間隔で実行される。
【００４３】
また、再生モードキー１１が押下された旨の操作情報が送信されると、ＣＰＵ３０は、各部を再生モードに設定する。
【００４４】
また、ＣＰＵ３０は、外部記憶ＩＯ装置２８を介してメモリカード３１に、プレビュー画像、高解像度の画像のデータを記録したり、メモリカード３１から、記録された画像データを読み出したりする。ＣＰＵ３０は、メモリカード３１には、例えばＪＰＥＧ(Joint Photographic Experts Group)フォーマットで圧縮した画像データを記録する。
【００４５】
ＣＰＵ３０は、メモリ２３に画像データを一時記憶する際、プレビュー画像、高解像度の画像データを異なる記憶領域に記録する。また、ＣＰＵ３０は、メモリカード３１には、画像データを画像ファイルに分けて記録する。
【００４６】
また、ＣＰＵ３０は、外部記憶ＩＯ装置２８を介してメモリカード３１に、プレビュー画像、高解像度の画像のデータを記録したり、メモリカード３１から、記録された画像データを読み出したりする。ＣＰＵ３０は、メモリカード３１に画像データを格納する画像ファイルを作成する。
【００４７】
図３はＣＰＵ３０の機能構成を示すブロック図である。ＣＰＵ３０を機能的に示すと、画像取得部３０ａ、特徴点選択部３０ｂ、追跡部３０ｃ、評価点生成部３０ｄ、評価部３０ｅ、変換式算出部３０ｆ、画像処理部３０ｇからなる。
【００４８】
画像取得部３０ａは、図４に示すように、連続撮影などにより得られた少なくとも２つの画像Ａ，Ｂを取得する。この場合、画像Ａは基準画像としてメモリ２３の第１のバッファ２３ａに格納され、画像Ｂは被追跡画像としてメモリ２３の第２のバッファ２３ｂに格納される。
【００４９】
特徴点選択部３０ｂは、画像取得部３０ａによって得られた画像Ａから一定の制約の下で直線上に並んだ特徴点を選択する。
【００５０】
追跡部３０ｃは、特徴点選択部３０ｂによって選択された各特徴点を画像Ｂ上で追跡する。
【００５１】
評価点生成部３０ｄは、追跡部３０ｃによって追跡された各特徴点から所定数の点を選び、これらの点を元に画像Ｂ上で直線上に並んだ特徴点を評価点として再帰的に生成する。詳しくは、この評価点生成部３０ｄは、追跡部３０ｃによって得られた各特徴点の中で四角形の頂点をなす４点を抽出し、その４点を元に画像Ｂ上で直線上に並んだ特徴点を評価点として再帰的に生成する。また、この評価点生成部３０ｄは、四角形の頂点をなす４点から前記四角形の内点を求める第１の追加処理部３０ｄ−１と、この第１の追加処理部３０ｄ−１によって得られた内点と前記四角形の辺との交点である境界点を求める第２の追加処理部３０ｄ−２と、この第２の追加処理部３０−２によって得られた境界点と前記四角形の頂点との延長線と前四角形の辺の延長線との交点である外点を求める第３の追加処理部３０ｄ−３とを備え、前記各追加処理部３０ｄ−１〜３０ｄ−３によって得られた内点、境界点、外点を評価点として追加する。
【００５２】
評価部３０ｅは、評価点生成部３０ｄによって生成された各評価点と画像Ｂ上で追跡された各特徴点との適合性を評価する。
【００５３】
変換式算出部３０ｆは、評価部３０ｅによって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する。
【００５４】
また、画像処理部３０ｇは、変換式算出部３０ｆによって得られた変換式に基づいて画像Ａと画像Ｂを位置合わせてして所定の画像を生成する。前記所定の画像とは、例えばパノラマ画像や手振れ補正した画像などである。
【００５５】
次に、具体的な処理手順を説明する前に、理解を容易にするため、図５乃至図８を参照して、本方式について説明しておく。
【００５６】
処理の全体はＲＡＮＳＡＣアルゴリズムに基づく。仮の変換行列を繰り返し計算する従来例のＲＡＮＳＡＣとの違いは、特徴点の配置に次に述べるような制約を設けることと、適合点の判定方法で用いる「変換によって移る座標」の算出を、従来のように変換パラメータ（射影変換行列）を求めることで行うのではなく、４組の特徴点から再帰的に求められる各点の座標から直接判定することである。
【００５７】
なお、後述するように再帰的に各点の座標を求めていくため、計算誤差が蓄積する懸念はあるが、ＲＡＮＳＡＣによってインライア集合を求めるのに十分な精度があれば良く、最終的なパラメータを算出するにはループを出てから再計算すれば良いので、大きな問題とはならない。
【００５８】
（１）特徴点座標の制約
（入力の制約）
まず、特徴点を選出するに際し、以下のような制約を置く。
【００５９】
一方の平面である基準平面上の各特徴点の座標は、正方格子状に所定の座標に固定的に設定するものとしている。ここで、特徴のないパターンの上にある特徴点は特徴点対応集合から除去してかまわない。
【００６０】
他方の平面を被追跡平面と呼び、その上の各特徴点の座標は、基準平面上の特徴点座標にある特徴パターンが、どの座標に移動したかを追跡アルゴリズム（ブロックマッチングや勾配法）によって推定した座標によって構成するものとする。
【００６１】
これらの特徴点対応がｎ組、すなわち、
（（ｘ0 ，ｙ0 ），（ｘ″0 ，ｙ″0 ）），（（ｘ1 ，ｙ1 ），（ｘ″1 ，ｙ″1 ）），…，（（ｘn-1 ，ｙn-1 ），（ｘ″n-1 ，ｙ″n-1 ））
の要領で、対の配列として構成されているものとする。
【００６２】
なお、（ｘ，ｙ）は基準平面上の特徴点の座標、（ｘ″，ｙ″）は被追跡平面上で追跡した特徴点の座標を表している。また、後述する（ｘ′，ｙ′）は被追跡平面上の特徴点の座標を表している。
【００６３】
（部分集合の抽出）
従来例のＲＡＮＳＡＣによるランダムな部分集合の抽出は、４組の特徴点を使うアルゴリズムであれば、４個の特徴点をランダムに選んで行う。特徴点が重複したり、退化条件（一直線に並ぶなど）の場合は意味がなく、再度抽出し直すが、本方式では、さらに制約を強くする。
【００６４】
すなわち、４組の特徴点を選択するが、基準平面（画像Ａ）における４点の配置が、矩形の各頂点をなし、その１辺の長さが、前述した格子配置の間隔の２m（但し、ｍは任意の正整数）となっているものを選ぶ。
【００６５】
具体的な方法としては、例えば、左上座標とｍをランダムに決めることで選んでも良いし、制約が強く組み合わせ数が少ないため、ループによって順次すべての組み合わせを選択していっても良い。当然ながら、存在しない特徴点の座標を含んでしまった場合は破棄して次の組み合わせに進む。
【００６６】
図５に基準平面における特徴点の部分集合の抽出例を示す。黒点は特徴点座標を示す。図中の点線枠で示した正方形の各頂点を構成する４点の組みが抽出対象となる。
【００６７】
（２）変換によって移る座標の導出方法
ここが本実施形態の特徴となる。
【００６８】
通常、正方形配置の４点の特徴点対応から射影変換は一意に決まる（射影変換が退化するような例外的な対応点が存在する場合を除く）。本実施形態では、この時点で基準平面（画像Ａ）から被追跡平面（画像Ｂ）への射影変換のパラメータ（変換行列）を求めることはしないが、便宜的に変換Ｈとして名前をつけて説明する。
【００６９】
４点の周囲の他の特徴点対応について、以下に述べるように、基準平面上の特徴点の座標（ｘi ，ｙi ）が変換Ｈによって被追跡平面に移される座標（ｘ′i ，ｙ′i ）を求める。求めた後の処理は、一般のＲＡＮＳＡＣと同様で、追跡座標（ｘ″i ，ｙ″i ）との距離を調べて適合性を判定することができる。
【００７０】
座標（ｘ′i ，ｙ′i ）を変換Ｈの成分を求めることなく、直接に求めることができる理由は、特徴点相互の位置関係が制約されているために、射影変換の性質「直線を直線に移す」を利用できるからである。すなわち、基準平面から抽出した４つの特徴点を結ぶ６個の直線は、そのまま被追跡平面から抽出した４つの特徴点がなす６個の直線に移る。さらに、「直線の交点は直線の交点に移る」ことが言える。したがって、変換によって移る交点の座標が求められるという原理である。
【００７１】
ここで示した導出方法を再帰的に適用して、全ての特徴点変換座標を求めるが、初期の抽出４点に関しては、基準平面の点ａ，ｂ，ｃ，ｄから、変換Ｈを用いて移る点ａ′，ｂ′，ｃ′，ｄ′と、追跡された点ａ″，ｂ″，ｃ″，ｄ″は同じ座標となる。それ以外の導出された点では同じ座標とは限らない。
【００７２】
ここで、前記４点の周囲の他の特徴点として、内点、境界点、外点を導出する方法について説明する。
【００７３】
（３）内点の変換座標の導出
まず、内点を導出する方法について説明する。内点とは、ここでは基準画像の選択矩形の中心点のことを指している。
【００７４】
図６は内点の変換座標の導出方法を説明するための図である。図６（ａ）が基準平面の位置関係、同図（ｂ）が被追跡平面の位置関係の例である。なお、図には、追跡された座標ｅ″の例も示した（ｅ′とｅ″の距離を測れば適合点か否かを判別できる）。但し、以後の処理で、再帰的処理のためにｅ′を求める場合には、ｅ″は必ずしも存在しない。特徴点が除外されていて追跡が行われなかったり、再帰的処理の中間結果として導出する場合には、特徴点格子幅より小さい幅単位になっていることもあって良い。図７、図８についても同様である。
【００７５】
基準平面の正方形頂点ａ，ｂ，ｃ，ｄを被追跡平面の点ａ′，ｂ′，ｃ′，ｄ′に移す変換Ｈを用いて、ちょうど中央の点ｅが、被追跡平面に変換される座標ｅ′を、以下のように求めることができる。
【００７６】
点ｐの平面座標（ｘp ，ｙp ）の内部表現を、（ｘp ，ｙp ，１）のように拡張ベクトルで表現する。なお、後で無限遠点も扱うが、平面原点から見て、（ｘp ，ｙp ）方向の無限遠点は（ｘp ，ｙp ，０）のように表現する。同次座標と捉えても良い。
【００７７】
ここで、基準平面上の点ｅは、点ａと点ｄを通る直線と、点ｂと点ｃを通る直線の交点である。したがって、変換Ｈによって移される被追跡平面上の点ｅ′は、点ａ′とｄ′を通る直線と、点ｂ′と点ｃ′を通る直線の交点を求めれば良い。この計算は、「２点を通る直線を求める方法」と、「２直線の交点を求める方法」を用いれば容易に構成できる。後の処理でも、この２つの方法をサブルーチンとして使う。
【００７８】
「２点を通る直線を求める方法」
平面上の２点ｐ，ｑを通る直線は、次の（１）式で表される。
【００７９】
（ｘ′p −ｘ′q ）（ｙ′−ｙ′q ）＝（ｙ′p −ｙ′q ）（ｘ′−ｘ′q ）
…（１）
前記（１）式において、同類項をまとめれば、直線：α1 ｘ′＋α2 ｙ′＋α3 ＝０となる。
【００８０】
なお、後で、ｐ，ｑのうち１点が無限遠点となる場合が出てくるが、その時は、無限遠点の方向に方向ベクトルを持ち、平面上の点（無限遠点でないほうの点）を通る直線を求めればよい。
【００８１】
「２直線の交点を求める方法」
２直線の交点は、直線：α1 ｘ′＋α2 ｙ′＋α3 ＝０、直線：β1 ｘ′＋β2 ｙ′＋β3 ＝０とすると、次式の線形方程式の解を求めればよい。
【数１】
【００８２】
但し、２直線が平行である場合（数値計算上は、ほぼ平行な場合）は、直線の延長上の無限遠点、例えば（α2，−α1，０）ないし（β2，−β1，０）を解と決める。
【００８３】
（４）境界点の変換座標の導出
次に、境界点を導出する方法について説明する。境界点とは、ここでは基準画像の選択矩形の各辺の中点のことを指している。
【００８４】
図７は境界点の変換座標の導出方法を説明するための図である。図７（ａ）が基準平面の位置関係、同図（ｂ）が被追跡平面の位置関係の例である。なお、正方形を構成する４辺のどの辺を選んでも全く対称的なので、ここでは右辺上の点ｆを例にして説明する。
【００８５】
基準平面の正方形頂点ａ，ｂ，ｃ，ｄを被追跡平面の点ａ′，ｂ′，ｃ′，ｄ′に移す変換Ｈを用いて、任意の辺の中点が、被追跡平面のどの座標に変換されるかを、以下のように求めることができる。
【００８６】
今、中央の点ｅに対応する点ｅ′が求められているとする。まず、点ａ′と点ｂ′を通る直線と、点ｃ′と点ｄ′を通る直線の交点ｗ′を前述の方法によって求める。前述の通り、直線が平行ならば、ｗ′は無限遠点である。
【００８７】
次に、点ｂ′と点ｄ′を通る直線と、ｅ′とｗ′を通る直線の交点を前述の方法によって求める。この交点が境界点ｆである。
【００８８】
同様にして、すべての辺の中点を求めると、各辺の長さが半分の４個の小正方形の頂点の変換座標が求められる。なお、これらの小正方形の変換に対して、再帰的に、内点座標の導出と境界点座標の導出を適用していけば、もとの正方形の内部及び境界のすべての格子状特徴点の変換座標が求めることができる。
【００８９】
（５）外点の変換座標の導出
次に、外点を導出する方法について説明する。外点とは、ここでは基準画像の選択矩形の頂点から矩形辺長だけ離れた格子点のことを指している。
【００９０】
図８は外点の変換座標の導出方法を説明するための図である。図７（ａ）が基準平面の位置関係、同図（ｂ）が被追跡平面の位置関係の例である。なお、正方形を構成する４辺のどの辺・方向を選んでも全く対称的なので、ここでは下辺を右側に延長した点ｇを例にして説明する。
【００９１】
基準平面の正方形頂点ａ，ｂ，ｃ，ｄを被追跡平面の点ａ′，ｂ′，ｃ′，ｄ′に移す変換Ｈを用いて、任意の辺上を辺の長さだけ外に延長した点が、被追跡平面のどの座標に変換されるかを、以下のように求めることができる。
【００９２】
今、右辺の中点ｆに対応する点ｆ′が求められているとする。変換Ｈによって移される点ｇ′は、変換Ｈによって移される点ａ′，ｂ′，ｃ′，ｄ′の座標から、点ａ′と点ｇ′を通る直線と、点ｃ′と点ｄ′を通る直線の交点を求めれば良い。この交点が外点である。
【００９３】
この方法で、外側の隣接点のすべてを求めることができ、もとと同じ大きさの４個の正方形の頂点の座標が求められる。以上の方法を再帰的に適用して、順次、隣接点とその内部・境界をたどっていけば、画面上の全ての特徴点の変換座標を求めることができる。
【００９４】
以下に、具体的な処理手順について説明する。
今、連続した２つの画像Ａと画像Ｂを位置合わせする場合を想定する。画像Ａで直線上に並んだ特徴点は、カメラの回転などによって歪んだ画像Ｂ上でも直線上に並んでいるはずである。したがって、画像Ａで直線上に並んでいた特徴点を画像Ｂ上で追跡してみて、これが画像Ｂ上で直線上になければ、異常な動きをしている特徴点として除外できる。
【００９５】
ここで、直線が直線に移ることは保証されているが、直線自体の角度は変化しうるし、直線各部の長さも変化する。そこで、画像Ｂ上で評価用の適切な直線をいかに引くかという問題を「４点を基準にして内点を作り、境界点を作り、外点を作る」という手法を繰り返すことで解決するものである。
【００９６】
図９は第１の実施形態における画像間の位置合わせの処理手順を示すフローチャートである。また、図１０は図９に含まれる評価対象追加処理を示すフローチャートである。なお、これらのフローチャートで示す各処理は、プログラムコードの形態でプログラムコード記憶装置２９に記憶されている。コンピュータであるＣＰＵ３０は、このプログラムを読み込むことにより、以下のような処理を実行する。
【００９７】
図９のフローチャートに示すように、ＣＰＵ３０は、連続した２つの画像Ａと画像Ｂを取得する（ステップＳ１００）。なお、この画像Ａ，Ｂは、連続撮影などによってイメージセンサ２２から直接取得することでも良いし、メモリカード３１などを通じて外部から提供されるものであっても良い。画像Ａは基準画像として、図３に示したメモリ２３の第１のバッファ２３ａに格納され、画像Ｂは被追跡画像として、第２のバッファ２３ｂに格納される。
【００９８】
画像Ａと画像Ｂが得られると、まず、ＣＰＵ３０は、図５に示したように基準画像である画像Ａ上から格子状の特徴点を選択、つまり、直線上に並んだ特徴点の集まりを選択する（ステップＳ１０１）。続いて、ＣＰＵ３０は、画像Ａ上の格子点（特徴点）に対応する画像Ｂ上の特徴点をブロックマッチングまたは勾配法などを用いて追跡する（ステップＳ１０２）。そして、この追跡処理によって得られた画像Ｂ上の特徴点の中から任意の４点を選び、これを仮想格子点とする（ステップＳ１０３）。この４点は、図６（ｂ）に示した点ａ′，ｂ′，ｃ′，ｄ′に相当し、四角形の頂点をなす。
【００９９】
なお、ここで言う「仮想格子点」とは、画像Ａの特徴点から変換Ｈによって画像Ｂに移される点のことであり、評価点として用いられる。この時点では、まだ４点しかないので、この４点を元に下記のような方法によって増やしていく。
【０１００】
すなわち、ＣＰＵ３０は、この４点を元に、直線を引く操作と交点を求める操作を画像Ｂ上で繰り返すことにより、仮想格子点を追加していく（ステップＳ１０４）。
【０１０１】
詳しくは、図１０のフローチャートに示すように、ＣＰＵ３０は、ステップＳ１０３で選んだ画像Ｂ上の４点を元に内点を求め（ステップＳ２０１）、続いて、その内点を手かがりにして境界点を求め（ステップＳ２０２）、さらに、その境界点を手かがりにして外点を求める（ステップＳ２０３）。なお、これらの点の求め方については、図６乃至図８で説明した通りであるため、ここでは省略する。
【０１０２】
このように、ステップＳ１０３で得られた４点を元に内点、境界点、外点の順で求めていく。これにより、内点１つ、境界点４つ、外点８つの計１３個の点が仮想格子点（評価点）が生成されることになる。これらの点は、ステップＳ１０３で得られた４点から変換Ｈによって、画像Ａから画像Ｂに移された特徴点座標を意味している。
【０１０３】
続いて、ＣＰＵ３０は、前記追加された点から四角形の頂点をなす４点を新たに選び（ステップＳ１０６）、その４点を元に前記同様の処理を繰り返して仮想格子点を順次追加していく（ステップＳ１０４）。
【０１０４】
仮想格子点の数が画像Ａ上の格子点の数に達すると、つまり、仮想格子点が画像Ｂの全体に生成されると（ステップＳ１０５のＹｅｓ）、ここでのループが終了する。この場合、最終的に画像Ａ上の格子点の数まで追加処理を繰り返しても良いし、予め決められた数に達した時点で終了しても良い。精度を求めるのであれば、格子点の数になるまで追加処理を繰り返すことが好ましい。
【０１０５】
次に、ＣＰＵ３０は、画像Ｂ上で、それぞれに対応する仮想格子点と追跡点との間の距離を計算する（ステップＳ１０７）。つまり、画像Ａの各特徴点から変換Ｈによって画像Ｂに移される各点と、画像Ａの各特徴点からステップＳ１０２の追跡処理で求められた各点とを比較して、両者間の位置ずれを求める。
【０１０６】
そして、ＣＰＵ３０は、両者の距離が所定値以下であった場合、つまり、仮想格子点と追跡点との位置ずれが許容範囲内であれば、そのときの追跡点を適合点と判断し、その座標をメモリ２３の所定の領域に記録しておくと共に（ステップＳ１０８）、適合点の総和を今回のスコアとして求め、図１１に示すスコア管理テーブル３２に記録する（ステップＳ１０９）。
【０１０７】
例えば、仮想格子点の数が１００個あったとして、その中の２０個の点が不適合であった場合には、その回のスコアとして８０点がスコア管理テーブル３２に記録される。なお、このスコア管理テーブル３２は、メモリ２３に設けられている。
【０１０８】
続いて、ＣＰＵ３０は、再び画像Ｂ上の特徴点からスタート点となる別の４点を仮想格子点として選ぶ（ステップＳ１１０のＮｏ→Ｓ１０３）。そして、前記同様に、その４点を元に直線を引く操作と交点を求める操作を繰り返して仮想格子点を増やしていき、仮想格子点の数が格子点の数に達した時点で、仮想格子点と追跡点との距離に基づいて適合性を判断し、適合点として得られた数の総和を今回のスコアとしてスコア管理テーブル３２に記録する（ステップＳ１０４〜Ｓ１０９）
以上の処理を所定回数繰り返す。
所定回数分のスコアが得られると（ステップＳ１１０のＹｅｓ）、ＣＰＵ３０は、その中で最もスコアが高かった回の適合点を前記メモリ２３の所定の領域から読み出し、その適合点の集合を用いて画像Ａと画像Ｂの変換行列（射影変換の行列式）を計算する（ステップＳ１１１）。
【０１０９】
図１１の例では、５回までのスコアが記録されており、その中で最もスコアの高い２回目で抽出された適合点が変換に最適な点として選択されることになる。なお、変換行列の求め方については従来と同様であるため、ここではその説明を省略するものとする。
【０１１０】
このようにして変換行列が得られると、以後、ＣＰＵ３０は、その変換行列を用いて画像Ａと画像Ｂを位置合わせてして、予め設定された撮影モードに従って、例えばパノラマ画像を生成したり、手振れを補正した画像を生成するなどの所定の画像処理を行う（ステップＳ１１２）。なお、この変換行列を用いた画像処理については公知であるため、ここでは、その詳しい説明は省略する。この画像処理によって得られた画像は、ＪＰＥＧ等の所定の方式で圧縮された後、例えばメモリカード３１などに記録保存される。
【０１１１】
このように、一定の制約の下で直線上に並んだ特徴点を選択し、その特徴点を元に「２点を通る直線を求める計算」と「２直線の交点座標を求める計算」を繰り返して、評価対象とする点を再帰的に求めていくことで、その中で適合性の高い点の集まりを用いて画像間の変換式を簡易に算出することが可能となる。したがって、従来のように仮の変換式を何度も繰り返し求める方法に比べて、計算量を大幅に削減でき、ハードウェア構成も簡素化して画像間の変換式を高速に求めることができる。
【０１１２】
また、このようにして得られた変換式をカメラの画像合成に適用することで、例えばパノラマ画像や手振れ補正した画像などを簡単に作成することができる。
【０１１３】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。
【０１１４】
前記第１の実施形態では、画像Ａ上の全特徴点に対して一括して追跡処理を行い、以後の処理は画像Ｂだけで行うようにしたが、第２の実施形態では、画像Ａ上で特徴点を追加しながら、画像Ｂ上でその特徴点に対応させて評価点を追加するようにしものである。
【０１１５】
なお、装置構成については、前記第１の実施形態と同様であるため、ここでは処理手順についてのみ説明する。
【０１１６】
図１２は第２の実施形態における画像間の位置合わせの処理手順を示すフローチャートである。なお、このフローチャートで示す各処理は、プログラムコードの形態でプログラムコード記憶装置２９に記憶されている。コンピュータであるＣＰＵ３０は、このプログラムを読み込むことにより、以下のような処理を実行する。
【０１１７】
図１２のフローチャートに示すように、ＣＰＵ３０は、連続した２つの画像Ａと画像Ｂを取得する（ステップＳ３００）。なお、この画像Ａ，Ｂは、連続撮影などによってイメージセンサ２２から直接取得することでも良いし、メモリカード３１などを通じて外部から提供されるものであっても良い。画像Ａは基準画像として、図３に示したメモリ２３の第１のバッファ２３ａに格納され、画像Ｂは被追跡画像として、第２のバッファ２３ｂに格納される。
【０１１８】
画像Ａと画像Ｂが得られると、まず、図５で説明したように、ＣＰＵ３０は、基準画像である画像Ａ上の特徴点から一定の制約の下に直線上に並んだ２点を２組、合わせて４点を選ぶ（ステップＳ３０１）。この４点は、図６（ａ）に示した点ａ，ｂ，ｃ，ｄに相当し、四角形（画像Ａ上では矩形）の頂点をなす。
【０１１９】
続いて、ＣＰＵ３０は、画像Ａ上の４点に対応する画像Ｂ上の４点をブロックマッチングまたは勾配法などを用いて追跡する（ステップＳ３０２）。この場合、画像Ｂはカメラの回転などによって歪んでいる可能性があるため、追跡処理によって得られた画像Ｂ上の４点は矩形になるとは限らない。
【０１２０】
ここで、画像Ａに対し、ＣＰＵ３０は、前記ステップＳ３０１で選んだ４点の組み元に、直線を引く操作と交点を求める操作を繰り返すことにより、特徴点を追加していく（ステップＳ３０３）。なお、この追加処理については図１０と同様である。すなわち、画像Ａ上で、ステップＳ３０１で得られた４点を元に内点、境界点、外点を求めていく。
【０１２１】
画像Ｂについても同様であり、ＣＰＵ３０は、ステップＳ３０２の追跡処理で得られた４点を元に直線を引く操作と交点を求める操作を繰り返すことにより、評価点を追加していく（ステップＳ３０６）。なお、「評価点」とは、前記第１の実施形態で説明した「仮想格子点」と同様の意味であり、画像Ａの特徴点から変換Ｈによって画像Ｂに移される点のことである。
【０１２２】
さらに、ＣＰＵ３０は、画像Ａから前の処理で追加された点から四角形（画像Ａでは矩形）の頂点をなす４点を新たに選び（ステップＳ３０５）、その４点を元に前記同様の処理を繰り返して特徴点を順次追加していく（ステップＳ３０３）。画像Ｂについても同様であり、画像Ｂから前の処理で追加された点から四角形の頂点をなす４点を新たに選び（ステップＳ３０８）、前記同様の処理を繰り返して評価値を順次追加していく（ステップＳ３０６）。
【０１２３】
なお、ステップＳ３０５の処理とステップＳ３０８の処理はリンクしており、画像Ａ上で新たな４点を選んだ場合に、当然のことながら、画像Ｂ上では、その画像Ａ上の４点と対応関係にある４点を選ぶことになる。
【０１２４】
画像Ａ、Ｂ上で追加された点がそれぞれに所定数に達すると（ステップＳ３０４のＹｅｓ，ステップＳ３０７のＹｅｓ）、ここでのループが終了する。この場合、最終的に画像Ａ上の特徴点のすべてを選び出すまで、追加処理を繰り返しても良いし、予め決められた数に達した時点で終了しても良い。精度を求めるのであれば、特徴点のすべてを選び出すまで、追加処理を繰り返すことが好ましい。
【０１２５】
次に、ＣＰＵ３０は、画像Ａ上の特徴点に対応する画像Ｂ上の特徴点を追跡する（ステップＳ３０９）。そして、ＣＰＵ３０は、画像Ｂ上で、それぞれに対応する評価点と追跡点との距離を計算する（ステップＳ３１０）。つまり、画像Ａの各特徴点から変換Ｈによって画像Ｂに移される各点（第２のループで得られる各点）と、画像Ａの各特徴点（第１のループで得られる各点）からステップＳ３０９の追跡処理で求められた各点とを比較して、両者間の位置ずれを求める。なお、第１のループとはステップＳ３０３〜Ｓ３０５の繰り返し処理、第２のループとはステップＳ３０６〜Ｓ３０８の繰り返し処理のことを示す。
【０１２６】
そして、ＣＰＵ３０は、両者の距離が所定値以下であった場合、つまり、評価点と追跡点との位置ずれが許容範囲内であれば、そのときの追跡点を適合点と判断し、その座標をメモリ２３の所定の領域に記録しておくと共に（ステップＳ３１１）、そのときに得られた適合点の総和を今回のスコアとして求め、図１１に示すスコア管理テーブル３２に記録する（ステップＳ３１２）。
【０１２７】
続いて、ＣＰＵ３０は、再び画像Ａからスタート点となる別の４点を選び（ステップＳ３１３のＮｏ→３０１）、その４点に対応する画像Ｂ上の４点を追跡する（ステップＳ３０２）。そして、前記同様に、画像Ａ上で、その４点を元に直線を引く操作と交点を求める操作を繰り返して特徴点を増やしていく（ステップＳ３０３〜Ｓ３０５）。画像Ｂについても同様であり、画像Ａで選んだ４点に対応した４点を元に直線を引く操作と交点を求める操作を繰り返しながら、評価点を増やしていく（ステップＳ３０６〜Ｓ３０７）。
【０１２８】
そして、ＣＰＵ３０は、画像Ａ上の特徴点に対応する画像Ｂ上の特徴点を追跡し、前記同様に、画像Ｂ上で評価値と追跡点との距離に基づいて適合性を判断し、適合点として得られた数の総和を今回のスコアとしてスコア管理テーブル３２に記録する（ステップＳ３０９〜Ｓ３１２）
以上の処理を所定回数繰り返す。
【０１２９】
所定回数分のスコアが得られると（ステップＳ３１３のＹｅｓ）、ＣＰＵ３０は、その中で最もスコアが高かった回の適合点を前記メモリ２３の所定の領域から読み出し、その適合点の集合を用いて画像Ａと画像Ｂの変換行列（射影変換の行列式）を計算する（ステップＳ３１４）。
【０１３０】
このようにして変換行列が得られると、以後、ＣＰＵ３０は、前記変換行列を用いて画像Ａと画像Ｂを位置合わせてして、予め設定された撮影モードに従って、例えばパノラマ画像を生成したり、手振れを補正した画像を生成するなどの所定の画像処理を行う（ステップＳ３１５）。
【０１３１】
このように、画像Ａ上で特徴点を追加しながら、画像Ｂ上でその特徴点に対応させて評価点を追加するような方法であっても、前記第１の実施形態と同様の効果を得ることができる。
【０１３２】
なお、本発明の用途はＲＡＮＳＡＣに限定されない。例えば、特殊なマーカを用いるなどして絶対に信頼できる４点があった時に、その他の誤りを含む対応点の中からアウトライアを高速に除去する場合にも使える。
【０１３３】
また、前記各実施形態では、デジタルカメラに例にして説明したが、デジタルカメラの他に、例えばパーソナルコンピュータなど、画像を扱える装置であれば、そのすべてに適用可能である。この場合、図２に示すように、デジタルカメラ１とＰＣ４０とを接続し、デジタルカメラ１で連続撮影された各画像をＰＣ４０に転送し、ＰＣ４０側で図９および図１０に示したような処理を実行するといった構成にしても良い。
【０１３４】
要するに、本発明は前記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記各実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【０１３５】
また、上述した各実施形態において記載した手法は、コンピュータに実行させることのできるプログラムとして、例えば磁気ディスク（フレキシブルディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ等）、半導体メモリなどの記録媒体に書き込んで各種装置に適用したり、通信媒体により伝送して各種装置に適用することも可能である。本装置を実現するコンピュータは、記録媒体に記録されたプログラムを読み込み、このプログラムによって動作が制御されることにより、上述した処理を実行する。
【図面の簡単な説明】
【０１３６】
【図１】図１は本発明の第１の実施形態に係る画像処理装置をデジタルカメラに適用した場合の外観構成を示す図であり、図１（ａ）は主に前面の構成、同図（ｂ）は主に背面の構成を示す斜視図である。
【図２】図２は同実施形態におけるデジタルカメラの電子回路構成を示すブロック図である。
【図３】図３は同実施形態におけるデジタルカメラのＣＰＵの機能構成を示すブロック図である。
【図４】図４は同実施形態におけるデジタルカメラの処理対象とする２つの連続した画像の一例を示す図である。
【図５】図５は同実施形態における基準平面における特徴点の部分集合の抽出例を示す図である。
【図６】図６は同実施形態における内点の変換座標の導出方法を説明するための図である。
【図７】図７は同実施形態における境界点の変換座標の導出方法を説明するための図である。
【図８】図８は同実施形態における外点の変換座標の導出方法を説明するための図である。
【図９】図９は同実施形態における画像間の位置合わせの処理手順を示すフローチャートである。
【図１０】図１０は同実施形態における評価対象追加処理を示すフローチャートである。
【図１１】図１１は同実施形態におけるすスコア管理テーブルの一例を示す図である。
【図１２】図１２は本発明の第２の実施形態における画像間の位置合わせの処理手順を示すフローチャートである。
【図１３】図１３は従来方式による画像間の位置合わせの処理手順を示すフローチャートである。
【符号の説明】
【０１３７】
１…デジタルカメラ、２…ボディ、３…撮影レンズ、４…セルフタイマランプ、５…光学ファインダ窓、６…ストロボ発光部、７…マイクロホン部、８…電源キー、９…シャッタキー、１０…撮影モード（Ｒ）キー、１１…再生モード（Ｐ）キー、１２…光学ファインダ、１３…スピーカ部、１４…マクロキー、１５…ストロボキー、１６…メニュー（ＭＥＮＵ）キー、１７…リングキー、１８…セット（ＳＥＴ）キー、１９…表示部、２１…光学レンズ装置、２２…イメージセンサ、２３…メモリ、２４…表示装置、２５…画像処理装置、２６…操作部、２７…コンピュータインタフェース部、２８…外部記憶ＩＯ装置、２９…プログラムコード記憶装置、３０…ＣＰＵ、３０ａ…画像取得部、３０ｂ…特徴点選択部、３０ｃ…追跡部、３０ｄ…評価点生成部、３０ｄ−１…第１の追加処理部、３０ｄ−２…第２の追加処理部、３０ｄ−３…第３の追加処理部、３０ｅ…評価部、３０ｆ…変換式算出部、３０ｇ…画像処理部、３１…メモリカード、３２…スコア管理テーブル、４０…ＰＣ。
【技術分野】
【０００１】
本発明は、平面から平面への特徴点群の対応をもとに、その妥当な射影変換（ホモグラフィ）を求める画像処理装置、画像変換方法及びプログラムに関する。
【背景技術】
【０００２】
例えば、デジタルカメラ等の撮像装置では、パノラマ合成や手振れ補正などの目的で、複数の連続した画像を重ね合わせて処理することがある。ここで、画像間の特徴点の対応を定める手法として、ＲＡＮＳＡＣ（random sampling consensus）と呼ばれるロバスト化のアルゴリズムが知られている。これは、特徴点対応に誤りが含まれている場合に、アウトライア（外れ値）を除外するための計算手法であり、具体的には以下のような手順を有する。
【０００３】
すなわち、まず、ランダムに抽出した特徴点対応の小さな部分集合を用いて、仮の変換パラメータ（ここでは、射影変換行列）を求め、その変換パラメータによって変換した特徴点の座標が実際の対応点の座標と適合するか否かを判別し、その適合点数をカウントする。
【０００４】
ループにより、このランダム抽出を多数回繰り返して、適合点数が最も多かった時の適合点の集合を最終的なインライアとし、それ以外はアウトライアとして除外する。この場合、精度が必要でなければ、最終的なインライアを求めたときの変換パラメータをそのまま答えとしても良い。高精度を求めるならば、得られた最終的なインライア集合を用いてより大規模な非線形最小化アルゴリズム等によって変換パラメータを再算出することができる（例えば、非特許文献１参照）。
【０００５】
今、画像Ａと画像Ｂとの位置合わせする場合を例にして具体的に説明すると、以下のような処理手順となる。
【０００６】
図１３は従来方式による画像間の位置合わせのための処理手順を示すフローチャートである。なお、このフローチャートで示す処理は、一般的な電子計算機によって実行されるものとする。
【０００７】
まず、画像Ａと画像Ｂから複数の特徴点を抽出し（ステップＳ１１）、これらの特徴点の中の任意の４点を選び（ステップＳ１２，Ｓ１３）、これらの４点の組から画像Ａと画像Ｂを位置合わせするための変換行列（射影変換の行列式）を求める（ステップＳ１４）。この時点では、まだ適合するかどうか分からないので、仮の変換行列である。
【０００８】
ここで、画像Ａに変換行列を適用し（ステップＳ１５）、画像Ａ上の各特徴点を射影変換した座標と、それに対応する画像Ｂ上の各特徴点の座標との距離を計算する（ステップＳ１６）。その結果、両者間の距離が所定値以上の特徴点を不適合点つまりアウトライアとして除外し（ステップＳ１７）、残った適合点の総和を今回のスコアとして記録する（ステップＳ１８）。
【０００９】
このようにして、ランダムに４点を選びながら、前記同様の処理を所定回数繰り返し（ステップＳ１９）、最もスコアが良かった回の適合点を用いて変換行列を計算し、これを用いて、画像Ａと画像Ｂとの位置合わせを行う（ステップＳ２０）。
【非特許文献１】「特徴点の位置分布に基づくランダムサンプリングによる平面領域のロバストな検出法」、電子情報通信学会論文誌 D-II Vol. J88-D-II No.2 pp.313-324
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述したように、ＲＡＮＳＡＣでは、特徴点の部分集合をランダム抽出し、仮の変換行列を求めて適合点数をカウントするといった処理を繰り返すことになる。通常、この繰り返しのループは数十回以上となる。仮の変換行列を求めるために最も簡易な線形アルゴリズムを用いたとしても、ループ数が多いために計算量が非常に多くなり、処理に時間がかかる、あるいはハードウェア構成が大かがりになるなどの問題がある。
【００１１】
本発明は前記のような点に鑑みなされたもので、複雑な計算を必要とせずに、各画像を位置合わせするための変換式または特徴点対応のインライア集合を高速に求めることのできる画像処理装置、画像変換方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の請求項１に係る画像処理装置は、少なくとも２つの画像を取得する画像取得手段と、この画像取得手段によって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する特徴点選択手段と、この特徴点選択手段によって選択された特徴点を第２の画像上で追跡する追跡手段と、この追跡手段によって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する評価点生成手段と、この評価点生成手段によって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する評価手段と、この評価手段によって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する変換式算出手段とを具備したことを特徴とする。
【００１３】
また、本発明の請求項２は、請求項１記載の画像処理装置において、前記評価点生成手段は、前記追跡手段によって得られた各特徴点の中で四角形の頂点をなす４点を抽出し、その４点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成することを特徴とする。
【００１４】
また、本発明の請求項３は、請求項２記載の画像処理装置において、前記評価点生成手段は、前記四角形の頂点をなす４点から前記四角形の内点を求める第１の追加処理手段と、この第１の追加処理手段によって得られた内点と前記四角形の辺との交点である境界点を求める第２の追加処理手段と、この第２の追加処理手段によって得られた境界点と前記四角形の頂点との延長線と前四角形の辺の延長線との交点である外点を求める第３の追加処理手段とを備え、前記各追加処理手段によって得られた内点、境界点、外点を評価点として追加することを特徴とする。
【００１５】
また、本発明の請求項４は、請求項１記載の画像処理装置において、前記変換式算出手段によって得られた変換式に基づいて前記第１の画像と前記第２の画像を位置合わせてして所定の画像を生成する画像処理手段とをさらに具備したことを特徴とする。
【００１６】
本発明の請求項５に係る画像変換方法は、少なくとも２つの画像を取得する第１のステップと、この第１のステップによって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する第２のステップと、この第２のステップによって選択された特徴点を第２の画像上で追跡する第３のステップと、この第３のステップによって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する第４のステップと、この第４のステップによって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する第５のステップと、この第５のステップによって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する第６のステップとを備えたことを特徴とする
また、本発明の請求項６に係るプログラムは、コンピュータによって読み取り可能な記録媒体に記録されたプログラムであって、前記コンピュータに、少なくとも２つの画像を取得する第１の機能と、この第１の機能によって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する第２の機能と、この第２の機能によって選択された特徴点を第２の画像上で追跡する第３の機能と、この第３の機能によって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する第４の機能と、この第４の機能によって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する第５の機能と、この第５の機能によって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する第６の機能とを実現させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、複雑な計算を必要とせずに、各画像を位置合わせするための変換式または特徴点対応のインライア集合を高速に求めることができる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照して本発明の実施形態を説明する。
【００１９】
（第１の実施形態）
図１は本発明の第１の実施形態に係る画像処理装置をデジタルカメラに適用した場合の外観構成を示す図であり、図１（ａ）は主に前面の構成、同図（ｂ）は主に背面の構成を示す斜視図である。
【００２０】
このデジタルカメラ１は、略矩形の薄板状ボディ２の前面に、撮影レンズ３、セルフタイマランプ４、光学ファインダ窓５、ストロボ発光部６、マイクロホン部７などを有し、上面の（ユーザにとって）右端側には電源キー８及びシャッタキー９などが設けられている。
【００２１】
電源キー８は、電源のオン／オフ毎に操作するキーであり、シャッタキー９は、撮影時に撮影タイミングを指示するキーである。
【００２２】
また、デジタルカメラ１の背面には、撮影モード（Ｒ）キー１０、再生モード（Ｐ）キー１１、光学ファインダ１２、スピーカ部１３、マクロキー１４、ストロボキー１５、メニュー（ＭＥＮＵ）キー１６、リングキー１７、セット（ＳＥＴ）キー１８、表示部１９などが設けられている。
【００２３】
撮影モードキー１０は、電源オフの状態から操作することで自動的に電源オンとして静止画の撮影モードに移行する一方で、電源オンの状態から繰返し操作することで、静止画モード、動画モードを循環的に設定する。静止画モードは、静止画を撮影するためのモードである。また、動画モードは、動画を撮影するためのモードである。
【００２４】
前記シャッタキー９は、これらの撮影モードに共通に使用される。すなわち、静止画モードでは、シャッタキー９が押下されたときのタイミングで静止画の撮影が行われる。動画モードでは、シャッタキー９が押下されたときのタイミングで動画の撮影が開始され、シャッタキー９が再度押下されたときにその動画の撮影が終了する。
【００２５】
再生モードキー１１は、電源オフの状態から操作することで自動的に電源オンとして再生モードに移行する。
【００２６】
マクロキー１４は、静止画の撮影モードで通常撮影とマクロ撮影とを切換える際に操作する。ストロボキー１５は、ストロボ発光部６の発光モードを切換える際に操作する。メニューキー１６は、連続撮影モードを含む各種メニュー項目等を選択する際に操作する。リングキー１７は、上下左右各方向への項目選択用のキーが一体に形成されたものであり、このリングキー１７の中央に位置するセットキー１８は、その時点で選択されている項目を設定する際に操作する。
【００２７】
表示部１９は、バックライト付きのカラー液晶パネルで構成されるもので、撮影モード時には電子ファインダとしてスルー画像のモニタ表示を行う一方で、再生モード時には選択した画像等を再生表示する。
【００２８】
なお、図示はしないがデジタルカメラ１の底面には、記録媒体として用いられるメモリカードを着脱するためのメモリカードスロットや、外部のパーソナルコンピュータ等と接続するためのシリアルインタフェースコネクタとして、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）コネクタ等が設けられている。
【００２９】
図２はデジタルカメラ１の電子回路構成を示すブロック図である。
【００３０】
このデジタルカメラ１には、光学レンズ装置２１、イメージセンサ２２、メモリ２３、表示装置２４、画像処理装置２５、操作部２６、コンピュータインタフェース部２７、外部記憶ＩＯ装置２８、プログラムコード記憶装置２９、ＣＰＵ３０、メモリカード３１が備えられている。
【００３１】
光学レンズ装置２１は、撮影レンズ３を構成する図示せぬフォーカスレンズおよびズームレンズを含むレンズ光学系とその駆動部とを備えたものであり、イメージセンサ２２上に、撮影対象からの光を集光させて像を結像させる。
【００３２】
イメージセンサ２２は、結像した画像を、デジタル化した画像データとして取り込むためのものであり、例えば、ＣＣＤ（Charge Coupled Device：電荷結合素子）等によって構成される。イメージセンサ２２は、ＣＰＵ３０によって制御され、シャッタキー９が押下されなければ、プレビュー用の解像度の低いデジタルの画像データを生成し、この画像データを秒間３０枚程度の間隔で、定期的にメモリ２３に送出する。また、イメージセンサ２２は、シャッタキー９が押下されると、解像度の高い画像データを生成し、生成した画像データをメモリ２３に送出する。また、イメージセンサ２２は、ＣＰＵ３０によって撮像感度（ＩＳＯ感度）の設定可能である。
【００３３】
メモリ２３は、イメージセンサ２２からの低解像度のプレビュー画像、高解像度の画像データまたは画像処理装置２５が画像処理する元画像のデータ、処理後の画像データを一時記憶するものである。メモリ２３は、一時記憶した画像データを表示装置２４または画像処理装置２５に送り出す。
【００３４】
表示装置２４は、液晶モニタである表示部１９に画像を表示させるためのものである。表示装置２４は、メモリ２３が一時記憶した低解像度のプレビュー画像または解像度の高い画像を表示部１９に表示する。
【００３５】
画像処理装置２５は、メモリ２３に一時記憶された画像データに対して、画像データの圧縮等の画像処理を行うためのものである。
【００３６】
操作部２６は、シャッタキー９の他に、電源キー８、撮影モードキー１０、再生モードキー１１、マクロキー１４、ストロボキー１５、メニューキー１６、リングキー１７、セットキー１８などから構成され、それらのキー操作に伴う信号は直接ＣＰＵ３０へ送出される。
【００３７】
コンピュータインタフェース部２７は、デジタルカメラ１がＰＣ４０に接続されたときに、ＵＳＢのストレジクラスドライバとして動作するものである。これにより、ＰＣ４０は、デジタルカメラ１に接続されると、メモリカード３１をコンピュータの外部記憶装置として取り扱う。
【００３８】
外部記憶ＩＯ装置２８は、メモリカード３１との間で、画像データ等の入出力を行うものである。メモリカード３１は、外部記憶ＩＯ装置２８から供給された画像データ等を記憶するものである。
【００３９】
プログラムコード記憶装置２９は、ＣＰＵ３０が実行するプログラムを記憶するためのものであり、ＲＯＭやフラッシュメモリなどによって構成される。
【００４０】
ＣＰＵ３０は、プログラムコード記憶装置２９に格納されているプログラムに従って、システム全体を制御するものである。なお、メモリ２３は、ＣＰＵ３０の作業メモリとしても用いられる。
【００４１】
操作部２６のスイッチ・キーが押下されることにより、操作部２６から操作情報が送信されると、ＣＰＵ３０は、この操作情報に基づいて、イメージセンサ２２、メモリ２３、表示装置２４、画像処理装置２５等を制御する。
【００４２】
具体的には、操作部２６から撮影モードキー１０が押下された旨の操作情報が送信されると、ＣＰＵ３０は各部を撮影モードに設定する。この状態で、シャッタキー９が押下されなければ、イメージセンサ２２をプレビューモードに設定し、シャッタキー９が押下されれば、解像度の高い撮影対象画像を読み込む高解像度モードに設定する。その際、メニューキー１６の操作により連続撮影モードが設定されていれば、シャッタキー９の押下に伴い、所定枚数分の画像の読み込み処理が所定時間間隔で実行される。
【００４３】
また、再生モードキー１１が押下された旨の操作情報が送信されると、ＣＰＵ３０は、各部を再生モードに設定する。
【００４４】
また、ＣＰＵ３０は、外部記憶ＩＯ装置２８を介してメモリカード３１に、プレビュー画像、高解像度の画像のデータを記録したり、メモリカード３１から、記録された画像データを読み出したりする。ＣＰＵ３０は、メモリカード３１には、例えばＪＰＥＧ(Joint Photographic Experts Group)フォーマットで圧縮した画像データを記録する。
【００４５】
ＣＰＵ３０は、メモリ２３に画像データを一時記憶する際、プレビュー画像、高解像度の画像データを異なる記憶領域に記録する。また、ＣＰＵ３０は、メモリカード３１には、画像データを画像ファイルに分けて記録する。
【００４６】
また、ＣＰＵ３０は、外部記憶ＩＯ装置２８を介してメモリカード３１に、プレビュー画像、高解像度の画像のデータを記録したり、メモリカード３１から、記録された画像データを読み出したりする。ＣＰＵ３０は、メモリカード３１に画像データを格納する画像ファイルを作成する。
【００４７】
図３はＣＰＵ３０の機能構成を示すブロック図である。ＣＰＵ３０を機能的に示すと、画像取得部３０ａ、特徴点選択部３０ｂ、追跡部３０ｃ、評価点生成部３０ｄ、評価部３０ｅ、変換式算出部３０ｆ、画像処理部３０ｇからなる。
【００４８】
画像取得部３０ａは、図４に示すように、連続撮影などにより得られた少なくとも２つの画像Ａ，Ｂを取得する。この場合、画像Ａは基準画像としてメモリ２３の第１のバッファ２３ａに格納され、画像Ｂは被追跡画像としてメモリ２３の第２のバッファ２３ｂに格納される。
【００４９】
特徴点選択部３０ｂは、画像取得部３０ａによって得られた画像Ａから一定の制約の下で直線上に並んだ特徴点を選択する。
【００５０】
追跡部３０ｃは、特徴点選択部３０ｂによって選択された各特徴点を画像Ｂ上で追跡する。
【００５１】
評価点生成部３０ｄは、追跡部３０ｃによって追跡された各特徴点から所定数の点を選び、これらの点を元に画像Ｂ上で直線上に並んだ特徴点を評価点として再帰的に生成する。詳しくは、この評価点生成部３０ｄは、追跡部３０ｃによって得られた各特徴点の中で四角形の頂点をなす４点を抽出し、その４点を元に画像Ｂ上で直線上に並んだ特徴点を評価点として再帰的に生成する。また、この評価点生成部３０ｄは、四角形の頂点をなす４点から前記四角形の内点を求める第１の追加処理部３０ｄ−１と、この第１の追加処理部３０ｄ−１によって得られた内点と前記四角形の辺との交点である境界点を求める第２の追加処理部３０ｄ−２と、この第２の追加処理部３０−２によって得られた境界点と前記四角形の頂点との延長線と前四角形の辺の延長線との交点である外点を求める第３の追加処理部３０ｄ−３とを備え、前記各追加処理部３０ｄ−１〜３０ｄ−３によって得られた内点、境界点、外点を評価点として追加する。
【００５２】
評価部３０ｅは、評価点生成部３０ｄによって生成された各評価点と画像Ｂ上で追跡された各特徴点との適合性を評価する。
【００５３】
変換式算出部３０ｆは、評価部３０ｅによって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する。
【００５４】
また、画像処理部３０ｇは、変換式算出部３０ｆによって得られた変換式に基づいて画像Ａと画像Ｂを位置合わせてして所定の画像を生成する。前記所定の画像とは、例えばパノラマ画像や手振れ補正した画像などである。
【００５５】
次に、具体的な処理手順を説明する前に、理解を容易にするため、図５乃至図８を参照して、本方式について説明しておく。
【００５６】
処理の全体はＲＡＮＳＡＣアルゴリズムに基づく。仮の変換行列を繰り返し計算する従来例のＲＡＮＳＡＣとの違いは、特徴点の配置に次に述べるような制約を設けることと、適合点の判定方法で用いる「変換によって移る座標」の算出を、従来のように変換パラメータ（射影変換行列）を求めることで行うのではなく、４組の特徴点から再帰的に求められる各点の座標から直接判定することである。
【００５７】
なお、後述するように再帰的に各点の座標を求めていくため、計算誤差が蓄積する懸念はあるが、ＲＡＮＳＡＣによってインライア集合を求めるのに十分な精度があれば良く、最終的なパラメータを算出するにはループを出てから再計算すれば良いので、大きな問題とはならない。
【００５８】
（１）特徴点座標の制約
（入力の制約）
まず、特徴点を選出するに際し、以下のような制約を置く。
【００５９】
一方の平面である基準平面上の各特徴点の座標は、正方格子状に所定の座標に固定的に設定するものとしている。ここで、特徴のないパターンの上にある特徴点は特徴点対応集合から除去してかまわない。
【００６０】
他方の平面を被追跡平面と呼び、その上の各特徴点の座標は、基準平面上の特徴点座標にある特徴パターンが、どの座標に移動したかを追跡アルゴリズム（ブロックマッチングや勾配法）によって推定した座標によって構成するものとする。
【００６１】
これらの特徴点対応がｎ組、すなわち、
（（ｘ0 ，ｙ0 ），（ｘ″0 ，ｙ″0 ）），（（ｘ1 ，ｙ1 ），（ｘ″1 ，ｙ″1 ）），…，（（ｘn-1 ，ｙn-1 ），（ｘ″n-1 ，ｙ″n-1 ））
の要領で、対の配列として構成されているものとする。
【００６２】
なお、（ｘ，ｙ）は基準平面上の特徴点の座標、（ｘ″，ｙ″）は被追跡平面上で追跡した特徴点の座標を表している。また、後述する（ｘ′，ｙ′）は被追跡平面上の特徴点の座標を表している。
【００６３】
（部分集合の抽出）
従来例のＲＡＮＳＡＣによるランダムな部分集合の抽出は、４組の特徴点を使うアルゴリズムであれば、４個の特徴点をランダムに選んで行う。特徴点が重複したり、退化条件（一直線に並ぶなど）の場合は意味がなく、再度抽出し直すが、本方式では、さらに制約を強くする。
【００６４】
すなわち、４組の特徴点を選択するが、基準平面（画像Ａ）における４点の配置が、矩形の各頂点をなし、その１辺の長さが、前述した格子配置の間隔の２m（但し、ｍは任意の正整数）となっているものを選ぶ。
【００６５】
具体的な方法としては、例えば、左上座標とｍをランダムに決めることで選んでも良いし、制約が強く組み合わせ数が少ないため、ループによって順次すべての組み合わせを選択していっても良い。当然ながら、存在しない特徴点の座標を含んでしまった場合は破棄して次の組み合わせに進む。
【００６６】
図５に基準平面における特徴点の部分集合の抽出例を示す。黒点は特徴点座標を示す。図中の点線枠で示した正方形の各頂点を構成する４点の組みが抽出対象となる。
【００６７】
（２）変換によって移る座標の導出方法
ここが本実施形態の特徴となる。
【００６８】
通常、正方形配置の４点の特徴点対応から射影変換は一意に決まる（射影変換が退化するような例外的な対応点が存在する場合を除く）。本実施形態では、この時点で基準平面（画像Ａ）から被追跡平面（画像Ｂ）への射影変換のパラメータ（変換行列）を求めることはしないが、便宜的に変換Ｈとして名前をつけて説明する。
【００６９】
４点の周囲の他の特徴点対応について、以下に述べるように、基準平面上の特徴点の座標（ｘi ，ｙi ）が変換Ｈによって被追跡平面に移される座標（ｘ′i ，ｙ′i ）を求める。求めた後の処理は、一般のＲＡＮＳＡＣと同様で、追跡座標（ｘ″i ，ｙ″i ）との距離を調べて適合性を判定することができる。
【００７０】
座標（ｘ′i ，ｙ′i ）を変換Ｈの成分を求めることなく、直接に求めることができる理由は、特徴点相互の位置関係が制約されているために、射影変換の性質「直線を直線に移す」を利用できるからである。すなわち、基準平面から抽出した４つの特徴点を結ぶ６個の直線は、そのまま被追跡平面から抽出した４つの特徴点がなす６個の直線に移る。さらに、「直線の交点は直線の交点に移る」ことが言える。したがって、変換によって移る交点の座標が求められるという原理である。
【００７１】
ここで示した導出方法を再帰的に適用して、全ての特徴点変換座標を求めるが、初期の抽出４点に関しては、基準平面の点ａ，ｂ，ｃ，ｄから、変換Ｈを用いて移る点ａ′，ｂ′，ｃ′，ｄ′と、追跡された点ａ″，ｂ″，ｃ″，ｄ″は同じ座標となる。それ以外の導出された点では同じ座標とは限らない。
【００７２】
ここで、前記４点の周囲の他の特徴点として、内点、境界点、外点を導出する方法について説明する。
【００７３】
（３）内点の変換座標の導出
まず、内点を導出する方法について説明する。内点とは、ここでは基準画像の選択矩形の中心点のことを指している。
【００７４】
図６は内点の変換座標の導出方法を説明するための図である。図６（ａ）が基準平面の位置関係、同図（ｂ）が被追跡平面の位置関係の例である。なお、図には、追跡された座標ｅ″の例も示した（ｅ′とｅ″の距離を測れば適合点か否かを判別できる）。但し、以後の処理で、再帰的処理のためにｅ′を求める場合には、ｅ″は必ずしも存在しない。特徴点が除外されていて追跡が行われなかったり、再帰的処理の中間結果として導出する場合には、特徴点格子幅より小さい幅単位になっていることもあって良い。図７、図８についても同様である。
【００７５】
基準平面の正方形頂点ａ，ｂ，ｃ，ｄを被追跡平面の点ａ′，ｂ′，ｃ′，ｄ′に移す変換Ｈを用いて、ちょうど中央の点ｅが、被追跡平面に変換される座標ｅ′を、以下のように求めることができる。
【００７６】
点ｐの平面座標（ｘp ，ｙp ）の内部表現を、（ｘp ，ｙp ，１）のように拡張ベクトルで表現する。なお、後で無限遠点も扱うが、平面原点から見て、（ｘp ，ｙp ）方向の無限遠点は（ｘp ，ｙp ，０）のように表現する。同次座標と捉えても良い。
【００７７】
ここで、基準平面上の点ｅは、点ａと点ｄを通る直線と、点ｂと点ｃを通る直線の交点である。したがって、変換Ｈによって移される被追跡平面上の点ｅ′は、点ａ′とｄ′を通る直線と、点ｂ′と点ｃ′を通る直線の交点を求めれば良い。この計算は、「２点を通る直線を求める方法」と、「２直線の交点を求める方法」を用いれば容易に構成できる。後の処理でも、この２つの方法をサブルーチンとして使う。
【００７８】
「２点を通る直線を求める方法」
平面上の２点ｐ，ｑを通る直線は、次の（１）式で表される。
【００７９】
（ｘ′p −ｘ′q ）（ｙ′−ｙ′q ）＝（ｙ′p −ｙ′q ）（ｘ′−ｘ′q ）
…（１）
前記（１）式において、同類項をまとめれば、直線：α1 ｘ′＋α2 ｙ′＋α3 ＝０となる。
【００８０】
なお、後で、ｐ，ｑのうち１点が無限遠点となる場合が出てくるが、その時は、無限遠点の方向に方向ベクトルを持ち、平面上の点（無限遠点でないほうの点）を通る直線を求めればよい。
【００８１】
「２直線の交点を求める方法」
２直線の交点は、直線：α1 ｘ′＋α2 ｙ′＋α3 ＝０、直線：β1 ｘ′＋β2 ｙ′＋β3 ＝０とすると、次式の線形方程式の解を求めればよい。
【数１】
【００８２】
但し、２直線が平行である場合（数値計算上は、ほぼ平行な場合）は、直線の延長上の無限遠点、例えば（α2，−α1，０）ないし（β2，−β1，０）を解と決める。
【００８３】
（４）境界点の変換座標の導出
次に、境界点を導出する方法について説明する。境界点とは、ここでは基準画像の選択矩形の各辺の中点のことを指している。
【００８４】
図７は境界点の変換座標の導出方法を説明するための図である。図７（ａ）が基準平面の位置関係、同図（ｂ）が被追跡平面の位置関係の例である。なお、正方形を構成する４辺のどの辺を選んでも全く対称的なので、ここでは右辺上の点ｆを例にして説明する。
【００８５】
基準平面の正方形頂点ａ，ｂ，ｃ，ｄを被追跡平面の点ａ′，ｂ′，ｃ′，ｄ′に移す変換Ｈを用いて、任意の辺の中点が、被追跡平面のどの座標に変換されるかを、以下のように求めることができる。
【００８６】
今、中央の点ｅに対応する点ｅ′が求められているとする。まず、点ａ′と点ｂ′を通る直線と、点ｃ′と点ｄ′を通る直線の交点ｗ′を前述の方法によって求める。前述の通り、直線が平行ならば、ｗ′は無限遠点である。
【００８７】
次に、点ｂ′と点ｄ′を通る直線と、ｅ′とｗ′を通る直線の交点を前述の方法によって求める。この交点が境界点ｆである。
【００８８】
同様にして、すべての辺の中点を求めると、各辺の長さが半分の４個の小正方形の頂点の変換座標が求められる。なお、これらの小正方形の変換に対して、再帰的に、内点座標の導出と境界点座標の導出を適用していけば、もとの正方形の内部及び境界のすべての格子状特徴点の変換座標が求めることができる。
【００８９】
（５）外点の変換座標の導出
次に、外点を導出する方法について説明する。外点とは、ここでは基準画像の選択矩形の頂点から矩形辺長だけ離れた格子点のことを指している。
【００９０】
図８は外点の変換座標の導出方法を説明するための図である。図７（ａ）が基準平面の位置関係、同図（ｂ）が被追跡平面の位置関係の例である。なお、正方形を構成する４辺のどの辺・方向を選んでも全く対称的なので、ここでは下辺を右側に延長した点ｇを例にして説明する。
【００９１】
基準平面の正方形頂点ａ，ｂ，ｃ，ｄを被追跡平面の点ａ′，ｂ′，ｃ′，ｄ′に移す変換Ｈを用いて、任意の辺上を辺の長さだけ外に延長した点が、被追跡平面のどの座標に変換されるかを、以下のように求めることができる。
【００９２】
今、右辺の中点ｆに対応する点ｆ′が求められているとする。変換Ｈによって移される点ｇ′は、変換Ｈによって移される点ａ′，ｂ′，ｃ′，ｄ′の座標から、点ａ′と点ｇ′を通る直線と、点ｃ′と点ｄ′を通る直線の交点を求めれば良い。この交点が外点である。
【００９３】
この方法で、外側の隣接点のすべてを求めることができ、もとと同じ大きさの４個の正方形の頂点の座標が求められる。以上の方法を再帰的に適用して、順次、隣接点とその内部・境界をたどっていけば、画面上の全ての特徴点の変換座標を求めることができる。
【００９４】
以下に、具体的な処理手順について説明する。
今、連続した２つの画像Ａと画像Ｂを位置合わせする場合を想定する。画像Ａで直線上に並んだ特徴点は、カメラの回転などによって歪んだ画像Ｂ上でも直線上に並んでいるはずである。したがって、画像Ａで直線上に並んでいた特徴点を画像Ｂ上で追跡してみて、これが画像Ｂ上で直線上になければ、異常な動きをしている特徴点として除外できる。
【００９５】
ここで、直線が直線に移ることは保証されているが、直線自体の角度は変化しうるし、直線各部の長さも変化する。そこで、画像Ｂ上で評価用の適切な直線をいかに引くかという問題を「４点を基準にして内点を作り、境界点を作り、外点を作る」という手法を繰り返すことで解決するものである。
【００９６】
図９は第１の実施形態における画像間の位置合わせの処理手順を示すフローチャートである。また、図１０は図９に含まれる評価対象追加処理を示すフローチャートである。なお、これらのフローチャートで示す各処理は、プログラムコードの形態でプログラムコード記憶装置２９に記憶されている。コンピュータであるＣＰＵ３０は、このプログラムを読み込むことにより、以下のような処理を実行する。
【００９７】
図９のフローチャートに示すように、ＣＰＵ３０は、連続した２つの画像Ａと画像Ｂを取得する（ステップＳ１００）。なお、この画像Ａ，Ｂは、連続撮影などによってイメージセンサ２２から直接取得することでも良いし、メモリカード３１などを通じて外部から提供されるものであっても良い。画像Ａは基準画像として、図３に示したメモリ２３の第１のバッファ２３ａに格納され、画像Ｂは被追跡画像として、第２のバッファ２３ｂに格納される。
【００９８】
画像Ａと画像Ｂが得られると、まず、ＣＰＵ３０は、図５に示したように基準画像である画像Ａ上から格子状の特徴点を選択、つまり、直線上に並んだ特徴点の集まりを選択する（ステップＳ１０１）。続いて、ＣＰＵ３０は、画像Ａ上の格子点（特徴点）に対応する画像Ｂ上の特徴点をブロックマッチングまたは勾配法などを用いて追跡する（ステップＳ１０２）。そして、この追跡処理によって得られた画像Ｂ上の特徴点の中から任意の４点を選び、これを仮想格子点とする（ステップＳ１０３）。この４点は、図６（ｂ）に示した点ａ′，ｂ′，ｃ′，ｄ′に相当し、四角形の頂点をなす。
【００９９】
なお、ここで言う「仮想格子点」とは、画像Ａの特徴点から変換Ｈによって画像Ｂに移される点のことであり、評価点として用いられる。この時点では、まだ４点しかないので、この４点を元に下記のような方法によって増やしていく。
【０１００】
すなわち、ＣＰＵ３０は、この４点を元に、直線を引く操作と交点を求める操作を画像Ｂ上で繰り返すことにより、仮想格子点を追加していく（ステップＳ１０４）。
【０１０１】
詳しくは、図１０のフローチャートに示すように、ＣＰＵ３０は、ステップＳ１０３で選んだ画像Ｂ上の４点を元に内点を求め（ステップＳ２０１）、続いて、その内点を手かがりにして境界点を求め（ステップＳ２０２）、さらに、その境界点を手かがりにして外点を求める（ステップＳ２０３）。なお、これらの点の求め方については、図６乃至図８で説明した通りであるため、ここでは省略する。
【０１０２】
このように、ステップＳ１０３で得られた４点を元に内点、境界点、外点の順で求めていく。これにより、内点１つ、境界点４つ、外点８つの計１３個の点が仮想格子点（評価点）が生成されることになる。これらの点は、ステップＳ１０３で得られた４点から変換Ｈによって、画像Ａから画像Ｂに移された特徴点座標を意味している。
【０１０３】
続いて、ＣＰＵ３０は、前記追加された点から四角形の頂点をなす４点を新たに選び（ステップＳ１０６）、その４点を元に前記同様の処理を繰り返して仮想格子点を順次追加していく（ステップＳ１０４）。
【０１０４】
仮想格子点の数が画像Ａ上の格子点の数に達すると、つまり、仮想格子点が画像Ｂの全体に生成されると（ステップＳ１０５のＹｅｓ）、ここでのループが終了する。この場合、最終的に画像Ａ上の格子点の数まで追加処理を繰り返しても良いし、予め決められた数に達した時点で終了しても良い。精度を求めるのであれば、格子点の数になるまで追加処理を繰り返すことが好ましい。
【０１０５】
次に、ＣＰＵ３０は、画像Ｂ上で、それぞれに対応する仮想格子点と追跡点との間の距離を計算する（ステップＳ１０７）。つまり、画像Ａの各特徴点から変換Ｈによって画像Ｂに移される各点と、画像Ａの各特徴点からステップＳ１０２の追跡処理で求められた各点とを比較して、両者間の位置ずれを求める。
【０１０６】
そして、ＣＰＵ３０は、両者の距離が所定値以下であった場合、つまり、仮想格子点と追跡点との位置ずれが許容範囲内であれば、そのときの追跡点を適合点と判断し、その座標をメモリ２３の所定の領域に記録しておくと共に（ステップＳ１０８）、適合点の総和を今回のスコアとして求め、図１１に示すスコア管理テーブル３２に記録する（ステップＳ１０９）。
【０１０７】
例えば、仮想格子点の数が１００個あったとして、その中の２０個の点が不適合であった場合には、その回のスコアとして８０点がスコア管理テーブル３２に記録される。なお、このスコア管理テーブル３２は、メモリ２３に設けられている。
【０１０８】
続いて、ＣＰＵ３０は、再び画像Ｂ上の特徴点からスタート点となる別の４点を仮想格子点として選ぶ（ステップＳ１１０のＮｏ→Ｓ１０３）。そして、前記同様に、その４点を元に直線を引く操作と交点を求める操作を繰り返して仮想格子点を増やしていき、仮想格子点の数が格子点の数に達した時点で、仮想格子点と追跡点との距離に基づいて適合性を判断し、適合点として得られた数の総和を今回のスコアとしてスコア管理テーブル３２に記録する（ステップＳ１０４〜Ｓ１０９）
以上の処理を所定回数繰り返す。
所定回数分のスコアが得られると（ステップＳ１１０のＹｅｓ）、ＣＰＵ３０は、その中で最もスコアが高かった回の適合点を前記メモリ２３の所定の領域から読み出し、その適合点の集合を用いて画像Ａと画像Ｂの変換行列（射影変換の行列式）を計算する（ステップＳ１１１）。
【０１０９】
図１１の例では、５回までのスコアが記録されており、その中で最もスコアの高い２回目で抽出された適合点が変換に最適な点として選択されることになる。なお、変換行列の求め方については従来と同様であるため、ここではその説明を省略するものとする。
【０１１０】
このようにして変換行列が得られると、以後、ＣＰＵ３０は、その変換行列を用いて画像Ａと画像Ｂを位置合わせてして、予め設定された撮影モードに従って、例えばパノラマ画像を生成したり、手振れを補正した画像を生成するなどの所定の画像処理を行う（ステップＳ１１２）。なお、この変換行列を用いた画像処理については公知であるため、ここでは、その詳しい説明は省略する。この画像処理によって得られた画像は、ＪＰＥＧ等の所定の方式で圧縮された後、例えばメモリカード３１などに記録保存される。
【０１１１】
このように、一定の制約の下で直線上に並んだ特徴点を選択し、その特徴点を元に「２点を通る直線を求める計算」と「２直線の交点座標を求める計算」を繰り返して、評価対象とする点を再帰的に求めていくことで、その中で適合性の高い点の集まりを用いて画像間の変換式を簡易に算出することが可能となる。したがって、従来のように仮の変換式を何度も繰り返し求める方法に比べて、計算量を大幅に削減でき、ハードウェア構成も簡素化して画像間の変換式を高速に求めることができる。
【０１１２】
また、このようにして得られた変換式をカメラの画像合成に適用することで、例えばパノラマ画像や手振れ補正した画像などを簡単に作成することができる。
【０１１３】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。
【０１１４】
前記第１の実施形態では、画像Ａ上の全特徴点に対して一括して追跡処理を行い、以後の処理は画像Ｂだけで行うようにしたが、第２の実施形態では、画像Ａ上で特徴点を追加しながら、画像Ｂ上でその特徴点に対応させて評価点を追加するようにしものである。
【０１１５】
なお、装置構成については、前記第１の実施形態と同様であるため、ここでは処理手順についてのみ説明する。
【０１１６】
図１２は第２の実施形態における画像間の位置合わせの処理手順を示すフローチャートである。なお、このフローチャートで示す各処理は、プログラムコードの形態でプログラムコード記憶装置２９に記憶されている。コンピュータであるＣＰＵ３０は、このプログラムを読み込むことにより、以下のような処理を実行する。
【０１１７】
図１２のフローチャートに示すように、ＣＰＵ３０は、連続した２つの画像Ａと画像Ｂを取得する（ステップＳ３００）。なお、この画像Ａ，Ｂは、連続撮影などによってイメージセンサ２２から直接取得することでも良いし、メモリカード３１などを通じて外部から提供されるものであっても良い。画像Ａは基準画像として、図３に示したメモリ２３の第１のバッファ２３ａに格納され、画像Ｂは被追跡画像として、第２のバッファ２３ｂに格納される。
【０１１８】
画像Ａと画像Ｂが得られると、まず、図５で説明したように、ＣＰＵ３０は、基準画像である画像Ａ上の特徴点から一定の制約の下に直線上に並んだ２点を２組、合わせて４点を選ぶ（ステップＳ３０１）。この４点は、図６（ａ）に示した点ａ，ｂ，ｃ，ｄに相当し、四角形（画像Ａ上では矩形）の頂点をなす。
【０１１９】
続いて、ＣＰＵ３０は、画像Ａ上の４点に対応する画像Ｂ上の４点をブロックマッチングまたは勾配法などを用いて追跡する（ステップＳ３０２）。この場合、画像Ｂはカメラの回転などによって歪んでいる可能性があるため、追跡処理によって得られた画像Ｂ上の４点は矩形になるとは限らない。
【０１２０】
ここで、画像Ａに対し、ＣＰＵ３０は、前記ステップＳ３０１で選んだ４点の組み元に、直線を引く操作と交点を求める操作を繰り返すことにより、特徴点を追加していく（ステップＳ３０３）。なお、この追加処理については図１０と同様である。すなわち、画像Ａ上で、ステップＳ３０１で得られた４点を元に内点、境界点、外点を求めていく。
【０１２１】
画像Ｂについても同様であり、ＣＰＵ３０は、ステップＳ３０２の追跡処理で得られた４点を元に直線を引く操作と交点を求める操作を繰り返すことにより、評価点を追加していく（ステップＳ３０６）。なお、「評価点」とは、前記第１の実施形態で説明した「仮想格子点」と同様の意味であり、画像Ａの特徴点から変換Ｈによって画像Ｂに移される点のことである。
【０１２２】
さらに、ＣＰＵ３０は、画像Ａから前の処理で追加された点から四角形（画像Ａでは矩形）の頂点をなす４点を新たに選び（ステップＳ３０５）、その４点を元に前記同様の処理を繰り返して特徴点を順次追加していく（ステップＳ３０３）。画像Ｂについても同様であり、画像Ｂから前の処理で追加された点から四角形の頂点をなす４点を新たに選び（ステップＳ３０８）、前記同様の処理を繰り返して評価値を順次追加していく（ステップＳ３０６）。
【０１２３】
なお、ステップＳ３０５の処理とステップＳ３０８の処理はリンクしており、画像Ａ上で新たな４点を選んだ場合に、当然のことながら、画像Ｂ上では、その画像Ａ上の４点と対応関係にある４点を選ぶことになる。
【０１２４】
画像Ａ、Ｂ上で追加された点がそれぞれに所定数に達すると（ステップＳ３０４のＹｅｓ，ステップＳ３０７のＹｅｓ）、ここでのループが終了する。この場合、最終的に画像Ａ上の特徴点のすべてを選び出すまで、追加処理を繰り返しても良いし、予め決められた数に達した時点で終了しても良い。精度を求めるのであれば、特徴点のすべてを選び出すまで、追加処理を繰り返すことが好ましい。
【０１２５】
次に、ＣＰＵ３０は、画像Ａ上の特徴点に対応する画像Ｂ上の特徴点を追跡する（ステップＳ３０９）。そして、ＣＰＵ３０は、画像Ｂ上で、それぞれに対応する評価点と追跡点との距離を計算する（ステップＳ３１０）。つまり、画像Ａの各特徴点から変換Ｈによって画像Ｂに移される各点（第２のループで得られる各点）と、画像Ａの各特徴点（第１のループで得られる各点）からステップＳ３０９の追跡処理で求められた各点とを比較して、両者間の位置ずれを求める。なお、第１のループとはステップＳ３０３〜Ｓ３０５の繰り返し処理、第２のループとはステップＳ３０６〜Ｓ３０８の繰り返し処理のことを示す。
【０１２６】
そして、ＣＰＵ３０は、両者の距離が所定値以下であった場合、つまり、評価点と追跡点との位置ずれが許容範囲内であれば、そのときの追跡点を適合点と判断し、その座標をメモリ２３の所定の領域に記録しておくと共に（ステップＳ３１１）、そのときに得られた適合点の総和を今回のスコアとして求め、図１１に示すスコア管理テーブル３２に記録する（ステップＳ３１２）。
【０１２７】
続いて、ＣＰＵ３０は、再び画像Ａからスタート点となる別の４点を選び（ステップＳ３１３のＮｏ→３０１）、その４点に対応する画像Ｂ上の４点を追跡する（ステップＳ３０２）。そして、前記同様に、画像Ａ上で、その４点を元に直線を引く操作と交点を求める操作を繰り返して特徴点を増やしていく（ステップＳ３０３〜Ｓ３０５）。画像Ｂについても同様であり、画像Ａで選んだ４点に対応した４点を元に直線を引く操作と交点を求める操作を繰り返しながら、評価点を増やしていく（ステップＳ３０６〜Ｓ３０７）。
【０１２８】
そして、ＣＰＵ３０は、画像Ａ上の特徴点に対応する画像Ｂ上の特徴点を追跡し、前記同様に、画像Ｂ上で評価値と追跡点との距離に基づいて適合性を判断し、適合点として得られた数の総和を今回のスコアとしてスコア管理テーブル３２に記録する（ステップＳ３０９〜Ｓ３１２）
以上の処理を所定回数繰り返す。
【０１２９】
所定回数分のスコアが得られると（ステップＳ３１３のＹｅｓ）、ＣＰＵ３０は、その中で最もスコアが高かった回の適合点を前記メモリ２３の所定の領域から読み出し、その適合点の集合を用いて画像Ａと画像Ｂの変換行列（射影変換の行列式）を計算する（ステップＳ３１４）。
【０１３０】
このようにして変換行列が得られると、以後、ＣＰＵ３０は、前記変換行列を用いて画像Ａと画像Ｂを位置合わせてして、予め設定された撮影モードに従って、例えばパノラマ画像を生成したり、手振れを補正した画像を生成するなどの所定の画像処理を行う（ステップＳ３１５）。
【０１３１】
このように、画像Ａ上で特徴点を追加しながら、画像Ｂ上でその特徴点に対応させて評価点を追加するような方法であっても、前記第１の実施形態と同様の効果を得ることができる。
【０１３２】
なお、本発明の用途はＲＡＮＳＡＣに限定されない。例えば、特殊なマーカを用いるなどして絶対に信頼できる４点があった時に、その他の誤りを含む対応点の中からアウトライアを高速に除去する場合にも使える。
【０１３３】
また、前記各実施形態では、デジタルカメラに例にして説明したが、デジタルカメラの他に、例えばパーソナルコンピュータなど、画像を扱える装置であれば、そのすべてに適用可能である。この場合、図２に示すように、デジタルカメラ１とＰＣ４０とを接続し、デジタルカメラ１で連続撮影された各画像をＰＣ４０に転送し、ＰＣ４０側で図９および図１０に示したような処理を実行するといった構成にしても良い。
【０１３４】
要するに、本発明は前記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記各実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【０１３５】
また、上述した各実施形態において記載した手法は、コンピュータに実行させることのできるプログラムとして、例えば磁気ディスク（フレキシブルディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ等）、半導体メモリなどの記録媒体に書き込んで各種装置に適用したり、通信媒体により伝送して各種装置に適用することも可能である。本装置を実現するコンピュータは、記録媒体に記録されたプログラムを読み込み、このプログラムによって動作が制御されることにより、上述した処理を実行する。
【図面の簡単な説明】
【０１３６】
【図１】図１は本発明の第１の実施形態に係る画像処理装置をデジタルカメラに適用した場合の外観構成を示す図であり、図１（ａ）は主に前面の構成、同図（ｂ）は主に背面の構成を示す斜視図である。
【図２】図２は同実施形態におけるデジタルカメラの電子回路構成を示すブロック図である。
【図３】図３は同実施形態におけるデジタルカメラのＣＰＵの機能構成を示すブロック図である。
【図４】図４は同実施形態におけるデジタルカメラの処理対象とする２つの連続した画像の一例を示す図である。
【図５】図５は同実施形態における基準平面における特徴点の部分集合の抽出例を示す図である。
【図６】図６は同実施形態における内点の変換座標の導出方法を説明するための図である。
【図７】図７は同実施形態における境界点の変換座標の導出方法を説明するための図である。
【図８】図８は同実施形態における外点の変換座標の導出方法を説明するための図である。
【図９】図９は同実施形態における画像間の位置合わせの処理手順を示すフローチャートである。
【図１０】図１０は同実施形態における評価対象追加処理を示すフローチャートである。
【図１１】図１１は同実施形態におけるすスコア管理テーブルの一例を示す図である。
【図１２】図１２は本発明の第２の実施形態における画像間の位置合わせの処理手順を示すフローチャートである。
【図１３】図１３は従来方式による画像間の位置合わせの処理手順を示すフローチャートである。
【符号の説明】
【０１３７】
１…デジタルカメラ、２…ボディ、３…撮影レンズ、４…セルフタイマランプ、５…光学ファインダ窓、６…ストロボ発光部、７…マイクロホン部、８…電源キー、９…シャッタキー、１０…撮影モード（Ｒ）キー、１１…再生モード（Ｐ）キー、１２…光学ファインダ、１３…スピーカ部、１４…マクロキー、１５…ストロボキー、１６…メニュー（ＭＥＮＵ）キー、１７…リングキー、１８…セット（ＳＥＴ）キー、１９…表示部、２１…光学レンズ装置、２２…イメージセンサ、２３…メモリ、２４…表示装置、２５…画像処理装置、２６…操作部、２７…コンピュータインタフェース部、２８…外部記憶ＩＯ装置、２９…プログラムコード記憶装置、３０…ＣＰＵ、３０ａ…画像取得部、３０ｂ…特徴点選択部、３０ｃ…追跡部、３０ｄ…評価点生成部、３０ｄ−１…第１の追加処理部、３０ｄ−２…第２の追加処理部、３０ｄ−３…第３の追加処理部、３０ｅ…評価部、３０ｆ…変換式算出部、３０ｇ…画像処理部、３１…メモリカード、３２…スコア管理テーブル、４０…ＰＣ。
【特許請求の範囲】
【請求項１】
少なくとも２つの画像を取得する画像取得手段と、
この画像取得手段によって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する特徴点選択手段と、
この特徴点選択手段によって選択された特徴点を第２の画像上で追跡する追跡手段と、
この追跡手段によって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する評価点生成手段と、
この評価点生成手段によって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する評価手段と、
この評価手段によって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する変換式算出手段と
を具備したことを特徴とする画像処理装置。
【請求項２】
前記評価点生成手段は、前記追跡手段によって追跡された各特徴点の中で四角形の頂点をなす４点を抽出し、その４点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成することを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記評価点生成手段は、
前記四角形の頂点をなす４点から前記四角形の内点を求める第１の追加処理手段と、
この第１の追加処理手段によって得られた内点と前記四角形の辺との交点である境界点を求める第２の追加処理手段と、
この第２の追加処理手段によって得られた境界点と前記四角形の頂点との延長線と前四角形の辺の延長線との交点である外点を求める第３の追加処理手段とを備え、
前記各追加処理手段によって得られた内点、境界点、外点を評価点として追加することを特徴とする請求項２記載の画像処理装置。
【請求項４】
前記変換式算出手段によって得られた変換式に基づいて前記第１の画像と前記第２の画像を位置合わせてして所定の画像を生成する画像処理手段と
をさらに具備したことを特徴とする請求項１記載の画像処理装置。
【請求項５】
少なくとも２つの画像を取得する第１のステップと、
この第１のステップによって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する第２のステップと、
この第２のステップによって選択された特徴点を第２の画像上で追跡する第３のステップと、
この第３のステップによって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する第４のステップと、
この第４のステップによって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する第５のステップと、
この第５のステップによって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する第６のステップと
を備えたことを特徴とする画像変換方法。
【請求項６】
コンピュータによって読み取り可能な記録媒体に記録されたプログラムであって、
前記コンピュータに、
少なくとも２つの画像を取得する第１の機能と、
この第１の機能によって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する第２の機能と、
この第２の機能によって選択された特徴点を第２の画像上で追跡する第３の機能と、
この第３の機能によって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する第４の機能と、
この第４の機能によって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する第５の機能と、
この第５の機能によって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する第６の機能と
を実現させることを特徴とするプログラム。
【請求項１】
少なくとも２つの画像を取得する画像取得手段と、
この画像取得手段によって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する特徴点選択手段と、
この特徴点選択手段によって選択された特徴点を第２の画像上で追跡する追跡手段と、
この追跡手段によって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する評価点生成手段と、
この評価点生成手段によって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する評価手段と、
この評価手段によって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する変換式算出手段と
を具備したことを特徴とする画像処理装置。
【請求項２】
前記評価点生成手段は、前記追跡手段によって追跡された各特徴点の中で四角形の頂点をなす４点を抽出し、その４点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成することを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記評価点生成手段は、
前記四角形の頂点をなす４点から前記四角形の内点を求める第１の追加処理手段と、
この第１の追加処理手段によって得られた内点と前記四角形の辺との交点である境界点を求める第２の追加処理手段と、
この第２の追加処理手段によって得られた境界点と前記四角形の頂点との延長線と前四角形の辺の延長線との交点である外点を求める第３の追加処理手段とを備え、
前記各追加処理手段によって得られた内点、境界点、外点を評価点として追加することを特徴とする請求項２記載の画像処理装置。
【請求項４】
前記変換式算出手段によって得られた変換式に基づいて前記第１の画像と前記第２の画像を位置合わせてして所定の画像を生成する画像処理手段と
をさらに具備したことを特徴とする請求項１記載の画像処理装置。
【請求項５】
少なくとも２つの画像を取得する第１のステップと、
この第１のステップによって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する第２のステップと、
この第２のステップによって選択された特徴点を第２の画像上で追跡する第３のステップと、
この第３のステップによって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する第４のステップと、
この第４のステップによって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する第５のステップと、
この第５のステップによって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する第６のステップと
を備えたことを特徴とする画像変換方法。
【請求項６】
コンピュータによって読み取り可能な記録媒体に記録されたプログラムであって、
前記コンピュータに、
少なくとも２つの画像を取得する第１の機能と、
この第１の機能によって得られた第１の画像から一定の制約の下で直線上に並んだ特徴点を選択する第２の機能と、
この第２の機能によって選択された特徴点を第２の画像上で追跡する第３の機能と、
この第３の機能によって追跡された各特徴点から所定数の点を選び、これらの点を元に前記第２の画像上で直線上に並んだ特徴点を評価点として再帰的に生成する第４の機能と、
この第４の機能によって生成された各評価点と前記第２の画像上で追跡された各特徴点との適合性を評価する第５の機能と、
この第５の機能によって最も適合性の高かった点の集まりを用いて画像間の変換式を算出する第６の機能と
を実現させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００８−２７６６２１（Ｐ２００８−２７６６２１Ａ）
【公開日】平成２０年１１月１３日（２００８．１１．１３）
【国際特許分類】
【出願番号】特願２００７−１２１１４７（Ｐ２００７−１２１１４７）
【出願日】平成１９年５月１日（２００７．５．１）
【出願人】（０００００１４４３）カシオ計算機株式会社 (8,748)
【Ｆターム（参考）】
【公開日】平成２０年１１月１３日（２００８．１１．１３）
【国際特許分類】
【出願日】平成１９年５月１日（２００７．５．１）
【出願人】（０００００１４４３）カシオ計算機株式会社 (8,748)
【Ｆターム（参考）】
[ Back to top ]