(57)【特許請求の範囲】
【請求項１】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段とを備え、
前記位置合わせ手段は、全特徴点については動きベクトルの全ての方向成分を用い、半特徴点については動きベクトルの特徴方向成分のみを用いることを特徴とする画像処理装置。
【請求項２】
前記半特徴点検出手段で検出された半特徴点の無特徴方向の動きベクトルを定数として特徴方向の動きにのみを用いることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段とを備え、
前記半特徴点検出手段で検出された半特徴点を勾配法により追跡する際に、追跡ベクトルｄに関する方程式Ｇｄ＝ｅをＧの最大固有値λの固有ベクトルｕの方向に制約した
ｄ＝〔（１／λ）ｕT ｅ〕
を代表解として選ぶことを特徴とする画像処理装置。
【請求項４】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記半特徴点検出手段で検出された半特徴点を順位付けする順位付け手段を備え、
前記順位付け手段は、勾配共分散行列またはオプティカルフローを求める勾配法の係数行列の最大固有値と最小固有値を用いることを特徴とする画像処理装置。
【請求項５】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記半特徴点検出手段で検出された半特徴点を順位付けする順位付け手段と備え、
前記順位付け手段は、最大曲率又はその近似値を用いて順位付けすることを特徴とする画像処理装置。
【請求項６】
前記半特徴点検出手段で検出された半特徴点を選別する選別手段をさらに備え、前記選別手段は、前記順位付け手段による順位付けにもとづき前記半特徴点を選別することを特徴とする請求項４または５に記載の画像処理装置。
【請求項７】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記半特徴点検出手段で検出された半特徴点を選別する選別手段とを備え、
前記選別手段は、半特徴点を選別する際に他の全特徴点または半特徴点との最小距離を全特徴点間の最小距離よりも大きくして選別することを特徴とする画像処理装置。
【請求項８】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記変換式算出手段は、射影変換行列Ｈ＝（ｈij）の各要素を列ベクトルとして並べて
【数１】
0004595733.tif 000038
とおき、
特徴点追跡処理により第一の画像の座標（ｘ，ｙ）が第二の画像の座標（Ｘ，Ｙ）に対応している時、全特徴点１つにつき
【数２】
0004595733.tif 000039
及び
【数３】
0004595733.tif 000040
の２個の線形な条件を作り、
且つ、半特徴点１つにつき
【数４】
0004595733.tif 000041
（但し（ｕx,ｕy）はこの半特徴点における特徴方向の単位ベクトル）
の１個の線形な条件を作り、これらの条件を８個以上揃えた上、それらの条件をベクトルの行に並べた線形方程式を解いて前記射影変換行列Ｈの成分を求めることを特徴とする画像処理装置。
【請求項９】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記変換式算出手段は、平行移動変換のモデルを
【数５】
0004595733.tif 000042
の座標変換とし、
【数６】
0004595733.tif 000043
とするとき、全特徴１個に関して
【数７】
0004595733.tif 000044
の２個の線形な条件と、
半特徴１個に関して
【数８】
0004595733.tif 000045
の１個の線形な条件を作り、これらの条件を２個以上揃えて方程式の解を求めることを特徴とする画像処理装置。
【請求項１０】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記変換式算出手段は、ユークリッド相似変換のモデルを
【数９】
0004595733.tif 000046
の座標変換とし、
【数１０】
0004595733.tif 000047
とするとき、全特徴１個に関して
【数１１】
0004595733.tif 000048
の２個の線形な条件と、
半特徴１個に関して、
【数１２】
0004595733.tif 000049
の１個の線形な条件を作り、これらの条件を４個以上揃えて方程式の解を求めることを特徴とする画像処理装置。
【請求項１１】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記位置合わせ手段は、算出した座標変換式の正しさを、追跡された動きベクトルと、求められた座標変換によるオフセットベクトルとの比較を各々のベクトルを特徴方向に射影した１次元の比較で評価する評価手段をさらに備え、
前記評価手段の判断にもとづき前記座標変換式の取捨選択することを特徴とする画像処理装置。
【請求項１２】
前記評価手段は、追跡による動きベクトルと、候補の座標変換式によって移されたオフセットベクトルとを特徴方向に射影して比較することを特徴とする請求項１１に記載の画像処理装置。
【請求項１３】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記位置合わせ手段は、算出した座標変換式の正しさを、第一の画像及び第二の画像の半特徴点周辺のウィンドウの画素値を比較して相違度を調べることで評価する評価手段をさらに備え、前記評価手段の判断にもとづき前記座標変換式の取捨選択することを特徴とする画像処理装置。
【請求項１４】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記位置合わせ手段は、算出した座標変換式の正しさを、半特徴点に関わる評価より、全特徴点に関わる評価を強く重みを付けることで評価する評価手段をさらに備え、前記評価手段の判断にもとづき前記座標変換式の取捨選択することを特徴とする画像処理装置。
【請求項１５】
入力された画像内の特徴点を検出する画像処理装置において、
前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、
前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、
前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記変換式算出手段は、座標変換式の算出法としてＲＡＮＳＡＣを用いるとともに、半特徴点を含んで算出された座標変換式に対し、サポート数を算出するよりも前に、求められた座標変換式の歪みを検査し、異常な座標変換式を除外することを特徴とする画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置に関し、詳しくは、ＣＣＤやＣＭＯＳなどの撮像デバイスを用いて被写体像を電気的に撮影し記録するデジタルカメラ等の撮像装置に適用する画像処理装置に関する。
【背景技術】
【０００２】
デジタルカメラ等の撮像装置を用いて夜景等の暗い被写体を撮影する場合、絞りの開放やシャッター速度を遅くすることに加え、撮影感度、つまり、ＣＣＤやＣＭＯＳなどの撮像デバイスの信号増幅度を高めることが効果的であるが、撮影感度を上げ過ぎると、撮像デバイスの内部雑音等のノイズが増えてしまい、見苦しい画像になる。
【０００３】
そこで、例えば、特許文献１には、同一の被写体を連続して撮影した複数の画像を重ね合わせて合成すると、その合成画像内の被写体部分は画像枚数分だけ倍加されるのに対して、ランダムなノイズ成分は平均化されるという知見の元、連続して撮影された複数の画像を合成することによってノイズの抑制を図るようにした技術（以下、従来技術という）が記載されている。これによれば、ノイズを抑えて撮影感度を高めることができるので、暗い被写体の撮影性能を向上できる。
【０００４】
ところで、暗い被写体を撮影する場合のシャッター速度は一般的に遅いため、手ぶれの可能性があるし、また、同一の被写体を連続して撮影する際には、各々の撮影時点で構図の微妙な移動が生じる可能性もある。
【０００５】
したがって、単に「同一の被写体を連続して撮影した複数の画像を重ね合わせて合成する」だけでは不十分であり、重ね合わせの精度向上、すなわち、対象となる各画像の位置合わせを厳密に行う必要がある。この点について、従来技術では、同一の被写体を連続して撮影した複数の画像の“特徴点”を取り出し、各画像の特徴点が重なり合うように位置合わせ（座標変換）するとしている。
【０００６】
ここで、従来技術の“特徴点”は「輝度の高い点」とされているが、より一般的には、いずれの方向に動かしても画素値の変化が大きいために動きベクトル（オプティカルフロー）を確定できる点のことである。
【特許文献１】特開２００４−３５７０４０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記の従来技術にあっては、以下の点で改善すべき課題がある。
図１７は、従来技術の不都合を説明するための被写体の一例を示す図である。この被写体例は、背景に空１、左側に多数の窓２を有するビル３、右側に電柱４、上から右下にかけて電柱４に張り渡された電線５、６を含んでいる。なお、図中の左側の点線枠７は画像合成の不都合を生じない撮影構図（以下、第一の構図７という）、図中の上側の点線枠８は不都合を生じる撮影構図（以下、第二の構図８という）を表している。
【０００８】
図１８（ａ）は、第一の構図７における特徴点を示す図、図１８（ｂ）は、第二の構図８における特徴点を示す図である。上記の従来技術にあっては、画像内の輝度の高い点を特徴点として取り出すので、第一の構図７及び第二の構図８のいずれにおいても輝度の高い点、すなわち、ビル３の外壁のコーナや窓２のコーナなどが特徴点（図中の黒丸参照）として取り出される。
【０００９】
第一の構図７と第二の構図８の違いは、特徴点の偏りにある。つまり、第一の構図７では、各特徴点が画面内に偏り無く配置されているのに対して、第二の構図８では、各特徴点が画面内の一部（図では画像の左下隅）に偏って配置されている点で相違する。
【００１０】
ここで、同一の被写体を連続して撮影した複数の画像を合成する際の位置合わせは、原理上は画像の一カ所（例えば、画像の中央等）で行えばよいが、実用的に見れば、撮影レンズの周辺収差による画像の歪み、画像分解能の限界、光源の変動、被写体自体の変形など位置決めに微少な誤差が入り込む要因（以下、位置決め誤差要因）が多々あるため、画像内の様々な場所での位置合わせは不可欠である。
【００１１】
さて、かかる事実を踏まえて、上記の第一の構図７３と第二の構図８に注目すると、第一の構図７は画像内に偏り無く特徴点が存在するので、複数の画像を合成する際の位置合わせを支障無く行うことができる。しかし、第二の構図８については、画像内の一部にしか特徴点が存在しないため、複数の画像を合成した場合には当該部分（特徴点が存在する部分）の位置合わせしか正確に行うことができない。このため、残りの部分（空１や電線５、６が写っている部分）については、遠く離れた特徴点の情報を参考にして間接的に位置合わせせざるを得ない。したがって、上記の位置決め誤差要因により、残りの部分（空１や電線５、６が写っている部分）にずれを生じることがあるという不都合がある。
【００１２】
そこで、本発明の目的は、画像内のあらゆる部分から偏り無く特徴点を取り出すことができ、画像合成の際の位置合わせの正確性を向上できるようにした画像処理装置を提供することにある。
【課題を解決するための手段】
【００１３】
請求項１記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段とを備え、前記位置合わせ手段は、全特徴点については動きベクトルの全ての方向成分を用い、半特徴点については動きベクトルの特徴方向成分のみを用いることを特徴とする画像処理装置である。
請求項２記載の発明は、前記半特徴点検出手段で検出された半特徴点の無特徴方向の動きベクトルを定数として特徴方向の動きにのみを用いることを特徴とする請求項１に記載の画像処理装置である。
請求項３に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段とを備え、前記半特徴点検出手段で検出された半特徴点を勾配法により追跡する際に、追跡ベクトルｄに関する方程式Ｇｄ＝ｅをＧの最大固有値λの固有ベクトルｕの方向に制約したｄ＝〔（１／λ）ｕT ｅ〕を代表解として選ぶことを特徴とする画像処理装置である。
請求項４に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記半特徴点検出手段で検出された半特徴点を順位付けする順位付け手段を備え、前記順位付け手段は、勾配共分散行列またはオプティカルフローを求める勾配法の係数行列の最大固有値と最小固有値を用いることを特徴とする画像処理装置である。
請求項５に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記半特徴点検出手段で検出された半特徴点を順位付けする順位付け手段と備え、前記順位付け手段は、最大曲率又はその近似値を用いて順位付けすることを特徴とする画像処理装置である。
請求項６に記載の発明は、前記半特徴点検出手段で検出された半特徴点を選別する選別手段をさらに備え、前記選別手段は、前記順位付け手段による順位付けにもとづき前記半特徴点を選別することを特徴とする請求項４または５に記載の画像処理装置。
請求項７に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記半特徴点検出手段で検出された半特徴点を選別する選別手段とを備え、前記選別手段は、半特徴点を選別する際に他の全特徴点または半特徴点との最小距離を全特徴点間の最小距離よりも大きくして選別することを特徴とする画像処理装置である。
請求項８に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記変換式算出手段は、射影変換行列Ｈ＝（ｈij）の各要素を列ベクトルとして並べて
【数１３】
0004595733.tif 000002
とおき、
特徴点追跡処理により第一の画像の座標（ｘ，ｙ）が第二の画像の座標（Ｘ，Ｙ）に対応している時、全特徴点１つにつき
【数１４】
0004595733.tif 000003
及び
【数１５】
0004595733.tif 000004
の２個の線形な条件を作り、
且つ、半特徴点１つにつき
【数１６】
0004595733.tif 000005
（但し（ｕx,ｕy）はこの半特徴点における特徴方向の単位ベクトル）
の１個の線形な条件を作り、これらの条件を８個以上揃えた上、それらの条件をベクトルの行に並べた線形方程式を解いて前記射影変換行列Ｈの成分を求めることを特徴とする画像処理装置である。
請求項９に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記変換式算出手段は、平行移動変換のモデルを
【数１７】
0004595733.tif 000006
の座標変換とし、
【数１８】
0004595733.tif 000007
とするとき、全特徴１個に関して
【数１９】
0004595733.tif 000008
の２個の線形な条件と、
半特徴１個に関して
【数２０】
0004595733.tif 000009
の１個の線形な条件を作り、これらの条件を２個以上揃えて方程式の解を求めることを特徴とする画像処理装置である。
請求項１０に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、
前記変換式算出手段は、ユークリッド相似変換のモデルを
【数２１】
0004595733.tif 000010
の座標変換とし、
【数２２】
0004595733.tif 000011
とするとき、全特徴１個に関して
【数２３】
0004595733.tif 000012
の２個の線形な条件と、
半特徴１個に関して、
【数２４】
0004595733.tif 000013
の１個の線形な条件を作り、これらの条件を４個以上揃えて方程式の解を求めることを特徴とする画像処理装置である。
請求項１１に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、前記位置合わせ手段は、算出した座標変換式の正しさを、追跡された動きベクトルと、求められた座標変換によるオフセットベクトルとの比較を各々のベクトルを特徴方向に射影した１次元の比較で評価する評価手段をさらに備え、前記評価手段の判断にもとづき前記座標変換式の取捨選択することを特徴とする画像処理装置である。
請求項１２に記載の発明は、前記評価手段は、追跡による動きベクトルと、候補の座標変換式によって移されたオフセットベクトルとを特徴方向に射影して比較することを特徴とする請求項１１に記載の画像処理装置である。
請求項１３に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、前記位置合わせ手段は、算出した座標変換式の正しさを、第一の画像及び第二の画像の半特徴点周辺のウィンドウの画素値を比較して相違度を調べることで評価する評価手段をさらに備え、前記評価手段の判断にもとづき前記座標変換式の取捨選択することを特徴とする画像処理装置である。
請求項１４に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、前記位置合わせ手段は、算出した座標変換式の正しさを、半特徴点に関わる評価より、全特徴点に関わる評価を強く重みを付けることで評価する評価手段をさらに備え、前記評価手段の判断にもとづき前記座標変換式の取捨選択することを特徴とする画像処理装置である。
請求項１５に記載の発明は、入力された画像内の特徴点を検出する画像処理装置において、前記画像の画素配列面に沿っていずれの方向に動かしても画素値の変化が大きい点を全特徴点として検出する全特徴点検出手段と、前記画像の画素配列面に沿ってある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を半特徴点として検出する半特徴点検出手段と、前記全特徴点検出手段で検出された全特徴点及び前記半特徴点で検出された半特徴点に基づいて位置合わせのための座標変換式を算出する変換式算出手段と、前記変換式算出手段により算出された座標変換式にもとづき前記入力された画像を変換し、位置合わせを行う位置合わせ手段と、を備え、前記変換式算出手段は、座標変換式の算出法としてＲＡＮＳＡＣを用いるとともに、半特徴点を含んで算出された座標変換式に対し、サポート数を算出するよりも前に、求められた座標変換式の歪みを検査し、異常な座標変換式を除外することを特徴とする画像処理装置である。
【発明の効果】
【００１４】
請求項１記載の発明によれば、全特徴点に加えて半特徴点を抽出し追跡することができ、例えば、画面の一部に全特徴の不在部分（非検出部分）が存在していた場合であっても、その不在部分を半特徴で補い、評価点の無特徴方向の動きを除外することで、より正確な位置合わせを行う事ができる。
請求項２記載の発明によれば、評価点の特徴方向のみを探索することによって、探索が安定し、探索の収束が早くなると共に、反復毎にズレが拡大することによる誤追跡が減少する。
請求項３記載の発明によれば、特徴抽出及び全特徴追跡と同じ行列Ｇの係数から、半特徴の追跡を行うことができ、計算量の節約になる。
請求項４記載の発明によれば、公知の勾配法の追跡に用いる行列Ｇから半特徴点を検出できるので、計算量を節約できるし、その評価値を用いて特徴点の順位付けを行うので、追跡の安定化が保証される。
請求項５記載の発明によれば、勾配の大きさを評価する具体的手法として、半特徴については最大曲率（の近似）を用いるので、その評価値を用いて特徴を順位付けすることにより、追跡の安定性が保証される。
請求項６記載の発明によれば、単方向のエッジでない評価点、例えば、たまたまノイズの多い平坦部などを、誤って半特徴に含めてしまうことを防止できる。
請求項７記載の発明によれば、半特徴点を選別する際に、他の特徴点（全特徴点または半特徴点）との最小距離を、全特徴点間の最小距離よりも広くすれば、拘束条件として無意味な特徴の増加を防止できる。
請求項８記載の発明によれば、射影変換行列を求めることが可能になる。
請求項９記載の発明によれば、平行移動変換のモデルを用いて解を求めることが可能になる。
請求項１０記載の発明によれば、ユークリッド相似変換のモデルを用いて解を求めることが可能になる。
請求項１１記載の発明によれば、半特徴点を用いて座標変換式を評価・確認する際に、無特徴方向の誤差を無くすことができる。
請求項１２記載の発明によれば、ベクトルの比較はウィンドウ内画素値比較に比べて計算量が少ないので、ＲＡＮＳＡＣのループ回数を多くすることができ、より良い変換式を探索することができる。
請求項１３記載の発明によれば、画素値の比較によるため、視覚的に目立つ二重映りを除外することができる。
請求項１４記載の発明によれば、全特徴と半特徴の情報量の違いに対応した適正な重み付けを行うことができ、全特徴との一致性を高めることができる。また、全特徴は２次元の情報を持つのに対し、半特徴は１次元の情報しか持たないので、仮に全特徴と半特徴の数が均衡している場合には、精度のよい全特徴を優先させることにより、より安定した変換式を選択することができる。
請求項１５記載の発明によれば、全特徴点のみの場合の悪条件（３点以上が同一直線上に並ぶ）よりも起きやすい、半特徴点の悪条件、たとえば、同一あるいは平行の直線上に存在する複数の半特徴点から求められた線形従属に近い射影変換行列Ｈを排除できる。

【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施形態を、図面を参照しながら説明する。なお、以下の説明における様々な細部の特定ないし実例および数値や文字列その他の記号の例示は、本発明の思想を明瞭にするための、あくまでも参考であって、それらのすべてまたは一部によって本発明の思想が限定されないことは明らかである。また、周知の手法、周知の手順、周知のアーキテクチャおよび周知の回路構成等（以下「周知事項」）についてはその細部にわたる説明を避けるが、これも説明を簡潔にするためであって、これら周知事項のすべてまたは一部を意図的に排除するものではない。かかる周知事項は本発明の出願時点で当業者の知り得るところであるので、以下の説明に当然含まれている。
【００１６】
図１は、本実施形態の画像処理装置の概略構成図である。この図において、基準画像１０及び被追跡画像１１は、同一の被写体を連続して撮影した複数の画像である。なお、ここでは２枚の画像（基準画像１０及び被追跡画像１１）を例にするが、この枚数は画像合成に必要な最低の数を意味する。また、“同一の被写体を連続して撮影した複数の画像”とは、同一の被写体に対して通常のシャッター操作を複数回行い、それぞれのシャッター操作毎に撮影された各画像のことをいい、または、一度のシャッター操作で複数枚の画像を連続的に撮影する連写撮影画像のことをいい、あるいは、動画（ムービー）撮影の各フレーム画像のことをいう。
【００１７】
画像処理装置１２は、オプティカルフロー検出部１３、ＲＡＮＳＡＣ部１４及び画像合成部１５を含み、さらに、オプティカルフロー検出部１３は、ピラミッド化部１３ａ、特徴点抽出部１３ｂ及び特徴点追跡部１３ｃを含み、ＲＡＮＳＡＣ部１４は、ランダム選択部１４ａ、Ｈ計算部１４ｂ及びサポート計算部１４ｃを含み、画像合成部１５は、加算部１５ａ及び対応位置計算部１５ｂを含む。
【００１８】
オプティカルフロー検出部１３のピラミッド化部１３ａは、基準画像１０と被追跡画像１１とを取り込み、それらの解像度を段階的に落として粗い画像から精細な画像へと順次に階層化（ピラミッド化）した画像を生成する。オプティカルフロー検出部１３の特徴点抽出部１３ｂは、従来の「特徴点」、すなわち、いずれの方向に動かしても画素値の変化が大きい点（本明細書ではこの点のことを「全特徴点」または「全特徴」という）を抽出することに加え、ある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点（本明細書ではこの点のことを「半特徴点」または「半特徴」という）を抽出する。
【００１９】
全特徴点の一例は、ウィンドウに収まる小物体、大きな物体の角（コーナー）、いずれの方向に動かしても変化する特定の模様などである。一方、半特徴の一例は、大きな物体のコーナーを除くエッジ、細い線状の物体、単方向にしか変化がない模様などであり、典型的には直線上の点である。なお、厳密には半特徴は直線上の点のみに限らない。ウィンドウによって局所的に捉えられる場合には、半径の大きな円弧上の点や、曲率の小さな曲線上の点なども半特徴点に含まれる。
【００２０】
半特徴において、画素値の変化が大きい方向のことを「特徴方向」ということにする。この特徴方向は、後述の説明における「最大固有値の固有ベクトル方向」に一致する。また、同じく半特徴において、画素値の変化が小さい方向のことを「無特徴方向」ということにする。この無特徴方向は、後述の説明における「最小固有値の固有ベクトル方向」に一致する。
【００２１】
オプティカルフロー検出部１３の特徴点追跡部１３ｃは、特徴点抽出部１３ｂで抽出した全特徴点及び半特徴点の追跡処理を行い、その追跡結果をＲＡＮＳＡＣ部１４に出力する。
【００２２】
ＲＡＮＳＡＣ部１４のランダム選択部１４ａは、追跡済み特徴点の組（全特徴点の組及び半特徴点の組）を無作為に選択し、Ｈ計算部１４ｂは、その選択された特徴点の組に対応した座標変換式の候補を算出し、サポート計算部１４ｃは、その式に従って全ての特徴点（全特徴点及び半特徴点）を座標変換したときに追跡結果とどれだけ一致するかを評価（たとえば、差が一定距離内に収まる特徴（適合点）の個数＝サポート数）する。ＲＡＮＳＡＣ部１４は、こうした動作を繰り返し、最もよい評価値を得たときの座標変換式を最終結果として、画像合成部１５に出力する。
【００２３】
画像合成部１５の対応位置計算部１５ｂは、ＲＡＮＳＡＣ部１４からの座標変換式に従って基準画像１０と被追跡画像１１との位置合わせに必要な対応位置計算を行い、加算部１５ａは、その対応位置計算の結果に従って基準画像１０と基準画像１０に合わせて変形した被追跡画像１１の画素毎の加算あるいは平均画像（合成画像１６）を生成出力する。
【００２４】
特徴点の抽出（検出）について説明する。
図２は、特徴点抽出部１３ｂの動作フローチャートを示す図である。このフローチャートは、順次に実行される三つのループを含む。最初のループ（以下、ループＡという）は、特徴の評価点（一定間隔の座標）毎に繰り返し行われるループであり、このループＡを行うたびに、勾配共分散行列Ｇ（以下、単に行列Ｇという）の２つの固有値を計算する（ステップＳ１）。
【００２５】
ここで、行列Ｇの二つの固有値について説明する。全特徴、つまり、従来からの特徴は、特徴の候補点（評価点）を中心とする画素値のウィンドウをとり、そのウィンドウ内の各点が同じ動き（フロー）を持つという条件（局所拘束条件）を満たすとすると、ウィンドウ内の点ｐijについて、
【００２６】
【数２５】
0004595733.tif 000014
【００２７】
【数２６】
0004595733.tif 000015
【００２８】
が成り立ち、式２５を移項して、
【００２９】
【数２７】
0004595733.tif 000016
【００３０】
となる。式２７のｆ（ｐij）は基準画像１０を表し、ｆ（ｐi＋ｄx,j＋ｄy）（添え字の表記は式２７を参照のこと。）は被追跡画像１１を表す。このスカラー方程式が、同じフロー（ｄx  ｄy）T について、ウィンドウ内の全ての点ｐijで近似的に成立すると考える。ウィンドウサイズがＮ×Ｎ画素とすれば、未知数は（ｄx  ｄy）T の２次元に対して、方程式の数はＮ2
個ある（過剰条件）ので、最小二乗解を求める。一般に誤差（残差）||Ａｘ−ｂ||を最小化するｘは、正規方程式ＡT
Ａｘ＝ＡT ｂの解である。ＡT Ａは、ここではＮ×２行列と２×Ｎ行列の積であるが、
【００３１】
【数２８】
0004595733.tif 000017
【００３２】
とおき、変形すると、以下のように直接に２×２行列の和の形にすることができる。
【００３３】
【数２９】
0004595733.tif 000018
【００３４】
ｐにおける画素残差値をｅ（ｐ）とすると、この式の右辺は、
【００３５】
【数３０】
0004595733.tif 000019
【００３６】
と書くことができ、
【００３７】
【数３１】
0004595733.tif 000020
【００３８】
が得られる。式３１において、ｅは二つの画像（基準画像１０と被追跡画像１１）の同一評価点の画素値の差の大きさを表し、未知ベクトルｄは同評価点の動き（追跡ベクトル）を表している。
【００３９】
行列Ｇの固有値の性質として、以下のことが言える。まず、２つの固有値はいずれも非負の値を持つ。また、明らかに行列Ｇの固有値の一つでも０に近ければ、０に近い固有値に対する固有ベクトルの摂動が大きくなるため、式３１を安定して解くことができない。実際は、ウィンドウ内の画素値が特定の方向に対してほぼコンスタントに揃うとき、この状態（明らかに行列Ｇの固有値の一つが０に近くなる状態）になる。このことは開口問題（aperture  problem）とも呼ばれ、最小固有値が大きいほど、式３１の解は誤差の点で安定に求められることを意味する。さらに、行列Ｇの固有値は、ウィンドウ内各点の勾配を、固有ベクトル方向に射影した長さの二乗和であり、大きい方の固有値（最大固有値）に対応する固有ベクトルは、そのような和を最大化する方向になっており、一方、小さい方の固有値（最小固有値）に対応する固有ベクトルは、それに直交する方向（最小化する方向）になっている。
【００４０】
本発明に特有の「半特徴」についても、全特徴と同様のアルゴリズムを適用するが、全特徴の式３１のｄとして、次式３２に示す所定の制約条件を加えた解を選ぶ点で相違する。
【００４１】
【数３２】
0004595733.tif 000021
【００４２】
図３は、所定の制約条件の説明図である。この図及び式３２において、ｄは追跡ベクトル、１／λは勾配の調整量、ｕは単位固有ベクトル、ｕTｅは単位固有ベクトルｕと残差ベクトルｅの内積、つまり、単位固有ベクトルｕの方向に対する残差ベクトルｅの成分（スカラー量）である。この式３２により、前式３１（行列Ｇが線形従属のため不定解になる）を、最大固有値λの単位固有ベクトルｕ方向に制約したときの代表解が得られる。
【００４３】
なお、上記の制約に限らず、例えば、半特徴の追跡結果から動きベクトルの無特徴方向の成分を無視し（または未知・不定・自由とし）、特徴方向の成分だけを有効とするようにしてもよく、あるいは、半特徴の追跡において、無特徴方向の動きを定数（例えば０）として、特徴方向の動きのみに制約してブロックマッチング法などにより探索してもよい。
【００４４】
このほかに、半特徴に関しては、例えば、半特徴を順位付けする評価値として、画素をある方向に動かしたときの画素値の変化が最大となる方向の勾配の大きさ（または変化率の大きさ）を用いてもよい。つまり、少なくとも一つの方向に対しては明確な差分が出る評価点を半特徴として選択してもよい。
【００４５】
また、半特徴点を選別する際に、画素をある方向に動かしたときの画素値の変化が最大となる方向の勾配の大きさ（または変化率の大きさ）を、画素値の変化が最小となる方向の勾配の大きさ（または変化率の大きさ）で割った比が小さいものを半特徴候補から除外し、あるいは、評価値を下げてもよい。
【００４６】
また、半特徴を検出する際の勾配の大きさを評価する具体的手法として、前式２９の行列Ｇの固有値を用いてもよい。すなわち、画素をある方向に動かしたときの画素値の変化が最大となる方向の勾配の大きさを最大固有値とし、画素をある方向に動かしたときの画素値の変化が最小となる方向の勾配の大きさを最小固有値としてもよい。
【００４７】
また、勾配の大きさを評価する手法として、半特徴については最大曲率（の近似）を用いてもよい。
【００４８】
座標（ｘ，ｙ）に関する画素値（輝度）の主曲率ｋ1 ，ｋ2
は、直接に近傍画素の平均化後の２階差分あるいは近傍画素を多項式近似に当てはめた係数を用いて各方向を調べるか、または、平均曲率ｈ＝（ｋ1 ＋ｋ2
）／２、ガウス曲率Ｋ＝ｋ1 ｋ2
と、画素値（輝度）の１階微分値Ｐx，Ｐy、２階微分値Ｐxx，Ｐyy，Ｐxyとの関係（次の式３３及び式３４参照）を用いて導くことができる。なお、上式の微分の計算法についても、平滑化後の近傍から差分をとるか、近傍画素値を多項式近似に当てはめた係数から求めるなどの方法を用いることができる。
【００４９】
【数３３】
0004595733.tif 000022
【００５０】
【数３４】
0004595733.tif 000023
【００５１】
また、半特徴点を選別する際に、他の特徴点（全特徴点または半特徴点）との最小距離を、全特徴点間の最小距離よりも広くしてもよい。比較的近い距離にある二つの半特徴点は、同じ物体の同じ方向のエッジに属することが多く、したがって、固有ベクトルの線形従属性が強く、画像全体の動きを制約する条件として重複し、増やしても効果が薄い（ＲＡＮＳＡＣや最小二乗法などを適用すると却って弊害を招くことがある）からである。
【００５２】
図４及び図５は、ループＡの概念図である。まず始めに、図４に示すように、所定の大きさ（たとえば、７×７画素〜３１×３１画素程度）のウィンドウ１７を適用して基準画像１０に初期位置の評価点１８を設定する。次いで、ループＡを繰り返すたびに、ウィンドウ１７を所定量（たとえば、１／２ウィンドウ幅）ずつ移動していき、最終的に基準画像１０の最終画素に到達するとループＡを終了する。
【００５３】
再び、図２において、２番目のループ（以下、ループＢという）は、ループＡの後に実行されるループであって、固有値一定以上かつ特徴点個数未達（特徴点数が所定の個数に満たない）の間継続するループである。このループＢを行うたびに、最小固有値最大の評価点を「全特徴点」として選択し（ステップＳ２）、選択された評価点近傍の他の評価点を評価候補から除外する（ステップＳ３）。
【００５４】
図６〜図９は、ループＢの概念図である。まず、図６に示すように、基準画像１０の各評価点の固有値データを順次に比較していき、図７に示すように、最小固有値が最大である評価点を「全特徴点」として選択する。ここでは、便宜的に上から３行目、左から７列目の評価点を全特徴点１９として選択する。次いで、図８に示すように、選択した全特徴点１９の周囲（特徴評価点間距離の数倍程度）の一定範囲２０に入っている評価点（破線の○印；ただし、破線の○印の数は便宜例である。）を除外する。次いで、図９に示すように、残った評価点の中で最小固有値が最大である評価点を「全特徴点」として選択する。ここでは、便宜的に上から６行目、右から５列目の評価点を全特徴点２１として選択する。以下、この動作を繰り返して全特徴点をすべて選択する。
【００５５】
再び、図２において、ループＢを抜けると、次に、特徴点個数未達（特徴点数が所定の個数に満たない）であるか否かを判定する（ステップＳ４）。特徴点個数未達でない場合は、そのままフローチャートを終了し、特徴点個数未達の場合は、特徴点間距離しきい値（図８の一定範囲２０の広さのこと）を２倍に増大（ステップＳ５）した後、第３のループ（以下、ループＣという）を実行する。このループＣでは、ループを実行するたびに、固有値比一定以上の中で最大固有値最大の評価点を「半特徴点」として選択し（ステップＳ６）、選択された評価点近傍の他の評価点を評価候補から除外する（ステップＳ７）という処理を繰り返し、評価値が一定以上かつ特徴点個数未達の間ループを継続してフローチャートを終了する。
【００５６】
このように、本実施形態の特徴点抽出部１３ｂは、従来の特徴点、すなわち、いずれの方向に動かしても画素値の変化が大きい「全特徴点」を検出することに加え、全特徴点が不足するときに、ある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい「半特徴点」を検出することがポイントである。
【００５７】
次に、特徴点追跡（トラッキング）について説明する。
図１０は、特徴点追跡部１３ｃの動作フローチャートを示す図である。このフローチャートは、第一のループ（以下、ループＤという）と、このループＤの内部でネストする第二のループ（以下、ループＥ）を含む。
【００５８】
このフローチャートを開始すると、まず、グローバル動き探索を実行し（ステップＳ１１）、その後、ループＤを開始する。グローバル動き探索とは、基準画像１０と被追跡画像１１の双方の縮小画像（例えば、１／４画像）を作り、基準画像１０の中心部に設けたウィンドウと、最もウィンドウ残差が小さくなる被追跡画像１１内の位置をブロックマッチングで探索し、グローバル動きベクトルを得る処理のことをいう。そのグローバル動きベクトルを以降の初期値ベクトルとしている。これにより、動きが大きい場合も、半特徴の追跡において、探索方向が制約されて真の方向からずれていても、エッジを一致させることができる。無特徴方向が多少ずれていても一致するため、反復は２次元正方行列Ｚを残差ベクトル（前記のウィンドウ残差にウィンドウ勾配値をかけた２次元ベクトル）に乗算することで行っている。
【００５９】
２次元正方行列Ｚは、全特徴の場合、行列Ｇの逆行列（Ｇ-1）とし、従来と変わらないが、半特徴の場合、２次元正方行列Ｚは行列Ｇのノルム最小型一般逆行列（Ｇ- ）とする。具体的には、最大固有値λと、それに対応する固有ベクトルｕ＝（ｕx ｕy）T を用いて、
【００６０】
【数３５】
0004595733.tif 000024
【００６１】
となる。この式３５は、前式３２と等価である。
【００６２】
ループＤは、基準画像１０の特徴点毎に実行される。このループＤでは、前記のグローバル動きベクトルで動きベクトルを初期化し（ステップＳ１２）、その動きベクトルの特徴が「全特徴」であるか否かを判定する（ステップＳ１３）。そして、全特徴である場合は、２次元正方行列Ｚに「Ｇ-1」をセットし（ステップＳ１４）、全特徴でない場合、つまり、半特徴である場合は、２次元正方行列Ｚに「Ｇ-
」をセットする（ステップＳ１５）。
【００６３】
次いで、ループＥを実行する。このループＥでは、誤差ベクトルｅを算出し（ステップＳ１６）、追跡ベクトルｄにＺｅをセットし（ステップＳ１７）、動きベクトルを更新（ｄ加算）（ステップＳ１８）した後、解の更新距離がしきい値（許容誤差を示す所定の微小な値）以下になるまでループＥを反復する。そして、解の更新距離がしきい値以下になると、ループＥを抜けて、特徴点ループ終端になるまで、以上の処理を繰り返す。
【００６４】
このように、本実施形態の特徴点の抽出（検出）と追跡によれば、全特徴に加えて半特徴を抽出し追跡するので、例えば、画面の一部に全特徴の不在部分（非検出部分）が存在していた場合であっても、その不在部分を半特徴で補うことができるようになる。つまり、従来技術においては、全特徴として検出されなかった評価点は全て破棄していたが、本実施形態では、それらの破棄対象の評価点の中から、ある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい点を「半特徴点」として検出するようにし、その半特徴点を活用するようにしたから、画面全域に渡って特徴点（全特徴点及び半特徴点）を網羅できるようになり、その結果、従来技術では正確な位置合わせが困難であった、例えば、図１８（ｂ））における特徴点不在部分（電線５、６が写っている部分）であっても、被写体（この場合は電線５、６）上の半特徴点を利用して画像の位置ズレを正確に修正することが可能になる。
【００６５】
図１１は、全特徴と半特徴の概念図である。この図の（ａ）において、画像２２には二つのコーナを持つ第一の被写体２３と、直線上の第二の被写体２４が写っている。すでに説明したように、全特徴点は、いずれの方向に動かしても画素値の変化が大きい評価点のことであり、半特徴点は、ある方向に動かしても画素値の変化がほとんどないが、別の方向に動かすと画素値の変化が大きい評価点のことであるから、この画像２２においては、第一の被写体２３の二つのコーナが全特徴点（黒丸印）２５となり、第一の被写体２３の各エッジの直線部分の任意の点と、第二の被写体２４の直線部分の任意の点とが、それぞれ半特徴点（白丸印）２６となる。
【００６６】
すなわち、全特徴点２５は、この図の（ｂ）に示すように、いずれの方向（図ではその代表として４５度ずつの方向を白抜き矢印で示している）に動かしても画素値の変化が大きい点であり、半特徴点２６は、この図の（ｃ）〜（ｅ）に示すように、ある方向（線２７〜２９に沿った方向）に動かしても画素値の変化がほとんどないが、別の方向（線２７〜２９と直交する方向）に動かすと画素値の変化が大きい点である。
【００６７】
また、例えば、半特徴の追跡結果から動きベクトルの無特徴方向の成分を無視し（または未知・不定・自由とし）、特徴方向の成分だけを有効とするように構成すれば、評価点の無特徴方向の動きを除外することができ、従来のアルゴリズムを適用して半特徴を検出する場合の誤差を排除できる。
【００６８】
図１２は、無特徴方向の成分を無視した半特徴の概念図である。この図において、実線矢印３０、３１は、それぞれ全特徴２５と半特徴２６の追跡結果の動きベクトルである。全特徴２５の追跡アルゴリズムは、従来のものと同じでも構わないが、半特徴２６については、対応する動きベクトル３１を無特徴方向に射影したベクトル３２を結果とする。
【００６９】
また、半特徴の追跡において、無特徴方向の動きを定数（例えば０）として、特徴方向の動きのみに制約して探索してもよい。評価点の特徴方向のみを探索することによって、探索が安定し、探索の収束が早くなると共に、反復毎にズレが拡大することによる誤追跡が減少する。
【００７０】
図１３（ａ）は、無特徴方向の動きを特徴方向の動きのみに制約した半特徴の概念図である。この図において、実線矢印３０、３３は、それぞれ全特徴２５と半特徴２６の追跡結果の動きベクトルである。半特徴２６の動きベクトル３３については、最初から特徴方向のみに制約して解を求める。すなわち、図１２の動きベクトル３２と図１３（ａ）の動きベクトル３３は実質同一である。
【００７１】
図１３（ｂ）は、追跡結果を示す図であり、動きに合わせて二つの画像（基準画像１０と被追跡画像１１）を重ね合わせて生成した合成画像１６を示す図である。図中の×印記号で追跡結果を表している。この図からも明らかなように、仮に、画面の一部に全特徴の不在部分（非検出部分）が存在していた場合であっても、その不在部分を半特徴２６で補うことができるようになり、それゆえ、画面全域に渡って特徴点（全特徴点２５及び半特徴点２６）を網羅できるようになり、その結果、従来技術では正確な位置合わせが困難であった、例えば、図１８（ｂ））における特徴点不在部分（電線５、６が写っている部分）であっても、被写体（この場合は電線５、６）上の半特徴点を利用して画像の位置ズレを正確に修正することが可能になるのである。
【００７２】
なお、半特徴に関しては、例えば、半特徴を順位付けする評価値として、画素をある方向に動かしたときの画素値の変化が最大となる方向の勾配の大きさ（または変化率の大きさ）を用いてもよく、つまり、少なくとも一つの方向に対しては明確な差分が出る評価点を半特徴として選択してもよい。このようにすると、単方向の動きが正確に求まりやすく、差が明確なものを半特徴として選択できる。
【００７３】
また、半特徴点を選別する際に、画素をある方向に動かしたときの画素値の変化が最大となる方向の勾配の直接の大きさ（または変化率の大きさ）を、画素値の変化が最小となる方向の勾配の大きさ（または変化率の大きさ）で割った比が小さいものを半特徴候補から除外し、あるいは、評価値を下げるようにすれば、単方向のエッジでない評価点、例えば、たまたまノイズの多い平坦部などを、誤って半特徴に含めてしまうことを防止できる。
【００７４】
また、公知の勾配法において追跡に用いる行列Ｇを用いて、画素をある方向に動かしたときの画素値の変化が最大となる方向の勾配の大きさをＧの最大固有値とし、画素をある方向に動かしたときの画素値の変化が最小となる方向の勾配の大きさをＧの最小固有値としてもよく、このようにすると、追跡に用いる行列Ｇから半特徴点を検出できるので、計算量を節約できるし、その評価値を用いて特徴点の順位付けを行うので、追跡の安定化が保証される。
【００７５】
また、勾配の大きさを評価する具体的手法として、半特徴については最大曲率（の近似）を用いるようにすれば、その評価値を用いて特徴を順位付けするので、追跡の安定性が保証される。
【００７６】
また、半特徴点を選別する際に、他の特徴点（全特徴点または半特徴点）との最小距離を、全特徴点間の最小距離よりも広くすれば、拘束条件として無意味な特徴の増加を防止できる。
【００７７】
また、前記の式３２を半特徴に適用すれば、特徴抽出及び全特徴追跡と同じ行列Ｇの係数から、半特徴の追跡を行うことができ、計算量の節約になる。
【００７８】
なお、以上の説明においては、特徴点の検出に勾配法を使用しているが、これに限定されず、例えば、ブロックマッチングなどの他の手法を用いてもよい。または、特徴の選択や順位付けを行わずに、単に全特徴と半特徴とに分類するだけであってもよい。
【００７９】
＜座標変換に関する補足説明＞
対応位置計算部１５ｂ（図２参照）で用いられる、位置合わせのための座標変換には、射影変換（自由度８）、アフィン変換（自由度６）、ユークリッド相似変換（自由度４）、剛体運動変換（自由度３）、平行移動変換（自由度２）などのモデルがある。自由度の小さい変換は一般に適用範囲が狭くなるが、計算負荷が軽くなる、誤差による不安定性が減少するなどの利点もあり、適宜適切なものを選択する。
【００８０】
一般に、座標変換式は、正方向（基準画像１０→被追跡画像１１）、逆方向（被追跡画像１１→基準画像１０）のいずれを求めてもよい（片方からその逆変換を求めることは容易にできる）。本実施形態のこれ以後の処理は、特徴方向を求めたのは基準画像１０の座標系においてであるから、逆方向（被追跡画像１１→基準画像１０）の変換を求めること、すなわち基準画像１０の座標系に対して適用することが厳密にはより正しい。しかしながら、正方向（基準画像１０→被追跡画像１１）の変換を求める場合にも、以後に記述した処理をそのまま適用することが多くの場合可能である。その理由は、平行移動モデルのような回転成分を含まないモデルではどちらでも同じになるし、それ以外の回転成分を含むモデルでも（回転が小さいと仮定できる場合は）各方程式は近似的には成り立つからである。よって、これ以後の説明では一般化して、基準画像１０、被追跡画像１１のいずれか一方を第一の画像Ｉ1 と呼び、他方を第二の画像Ｉ2 と呼ぶことにする。
【００８１】
本実施形態では、ＲＡＮＳＡＣ（ＲＡＮｄｏｍ  ＳＡｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ）により座標変換式の係数（パラメータ）を求めている。ＲＡＮＳＡＣとは、パラメータ推定の一手法であり、少数の点から求めたパラメータ推定の候補に対して、多数の点の中からその推定に適合する点の数や適合の正確性の度合い、すなわち、サポート数を算出し、サポート数の多い推定候補を最終の推定結果として採用する方法のことである。
【００８２】
図１４は、ＲＡＮＳＡＣ部１４の動作フローチャートを示す図である。このフローチャートは、第一のループ（以下、ループＦという）と、このループＦの内部でネストする第二のループ（以下、ループＧ）を含む。
【００８３】
このフローチャートを開始すると、まず、ループＦを所定回数実行する。このループＦでは、まず、ネストされたループＧを実行する。ループＧでは、ランダムに特徴を選び出し（ステップＳ２１）、その特徴の種別を判定する（ステップＳ２２）。そして、ランダムに選び出した特徴が「全特徴」であれば、条件２個（後述の式３７及び式３８参照）を作成し（ステップＳ２３）、「半特徴」であれば、条件１個（後述の式３９参照）を作成する（ステップＳ２４）。次いで、８条件が揃うまでループＧを反復し、８条件揃うと、方程式を解いて変換式（射影変換行列Ｈ）を得る（ステップＳ２５）。そして、射影変換の歪み（Ｈの歪み）の大小を検査し（ステップＳ２６）、歪み小の場合にだけ後述の「サポート計算」を実行する（ステップＳ２７）とともに、サポート数が最大サポート数を越えているか否かを判定し（ステップＳ２８）、越えている場合には、最大サポート数の更新とＨ保存を行い（ステップＳ２９）、ループ終端に達したときに、保存されていた最適なＨを出力して（ステップＳ３０）、フローチャートを終了する。
【００８４】
ここで、オプティカルフロー検出部１３で、全特徴と半特徴を含む特徴点が抽出・追跡され、各半特徴の特徴方向を表す単位ベクトルｕ＝（ｕx  ｕy）T
が、例えば、行列Ｇの最大固有値に対応する単位ベクトル（ｕx2＋ｕy2＝１）として求められている。
ここで、射影変換モデルを採用した場合の射影変換行列Ｈを求める方程式は、Ｈ＝（ｈij）の各要素を列ベクトルとして並べて、
【００８５】
【数３６】
0004595733.tif 000025
【００８６】
とおき、特徴点追跡処理によって、第一の画像Ｉ1の座標（ｘ，ｙ）が第二の画像Ｉ2の座標（Ｘ，Ｙ）に対応している時、全特徴１点につき次の式３７、式３８に示す２個の線形な条件を作り、
【００８７】
【数３７】
0004595733.tif 000026
【００８８】
【数３８】
0004595733.tif 000027
【００８９】
また、半特徴１点につき次の式３９に示す１個の線形な条件を作る。
【００９０】
【数３９】
0004595733.tif 000028
【００９１】
そして、条件が８個揃ったら、方程式をガウス消去法等で解き、射影変換行列Ｈを求める。あるいは、８個以上の方程式から最小二乗解を求めてもよい。すなわち、８個またはそれ以上の条件をベクトルの行に並べた次式４０の線形方程式
【００９２】
【数４０】
0004595733.tif 000029
【００９３】
を解いてＨの成分を求める。このようにすると、射影変換行列を求めることが具体的に可能になる。
【００９４】
ここで、射影変換の歪み（Ｈの歪み）の検査は、例えば、画像の境界４点の座標をＦH で移したとき、変換前後の４点のなす長方形の各辺の長さの比及び角が９０度からどれだけ離れているか（歪んでいるか）を調べることによって行う。著しく元の長方形から離れている時は、サポート計算（ステップＳ２７）を省略し、直ちに次順の候補の処理に移る。
【００９５】
このように、サポート計算を行う前に、半特徴を含んで算出された射影変換行列Ｈに対し、求められた変換の歪みの検査（長さや角度の変形が一定限度を超えないかの検査）を行って、異常な射影変換行列Ｈを除外する処理を入れている理由は、同一あるいは平行の直線上に存在する複数の半特徴点から求められたＨは悪条件（線形従属に近い）であり、全特徴のみの場合の悪条件（３点以上が同一直線上に並ぶ）より起こりやすいからである。
【００９６】
ここで、射影変換以外の座標変換式について２つのモデル（平行移動モデル、ユークリッド近似モデル）を例示する。
まず、平行移動変換のモデルは、次式Ａのような座標変換であり、
【００９７】
【数４１】
0004595733.tif 000030
【００９８】
【数４２】
0004595733.tif 000031
【００９９】
とおけば、全特徴１個に関して次式Ｃの２個の線形な条件（方程式）と、
【０１００】
【数４３】
0004595733.tif 000032
【０１０１】
半特徴１個に関して次式Ｄの１個の線形な条件（方程式）
【０１０２】
【数４４】
0004595733.tif 000033
【０１０３】
が得られ、変換の自由度は２であるから、２個以上の条件を揃えて方程式の解を求めることができる。
また、ユークリッド相似変換のモデルは、次式Ｅのような座標変換であり、
【０１０４】
【数４５】
0004595733.tif 000034
【０１０５】
【数４６】
0004595733.tif 000035
【０１０６】
とおけば、全特徴１個に関して次式Ｇの２個の線形な条件（方程式）と、
【０１０７】
【数４７】
0004595733.tif 000036
【０１０８】
半特徴１個に関して次式Ｈの１個の線形な条件（方程式）が得られ、
【０１０９】
【数４８】
0004595733.tif 000037
【０１１０】
変換の自由度は４であるから、４個以上の条件を揃えて方程式の解を求めることができる。
【０１１１】
図１５は、サポート計算の動作フローチャートを示す図である。このフローチャートでは、サポート数を初期化（ステップＳ３１）した後、追跡済特徴に対してループ（以下、ループＨという）を実行する。このループＨでは、まず、座標変換式による変換を実行し（ステップＳ３２）、特徴種別を判定する（ステップＳ３３）。そして、特徴種別が「全特徴」であれば全特徴の適合点判定を実行し（ステップＳ３４）、全特徴適合点であればサポート数に重み“２”を加算する（ステップＳ３５）。または、特徴種別が「半特徴」であれば半特徴の適合点判定を実行し（ステップＳ３６）、半特徴適合点であればサポート数に、全特徴適合点の場合よりも小さな重み“１”を加算する（ステップＳ３７）。次いで、サポート数を更新し（ステップＳ３８）、ループ終端に達した場合にサポート数を返して（ステップＳ３９）、フローチャートを終了する。
【０１１２】
このように、本実施形態では、座標変換式を算出するにあたり、追跡された動きベクトルと、求める座標変換によるオフセットベクトルとの比較となる束縛条件として、各々のベクトルを特徴方向に射影した１次元の束縛条件（前記の式３７〜式３９参照）としている。このようにすると、たとえ、全特徴が不足していたとしても、様々な特徴方向の半特徴が存在しさえすれば、座標変換の解を安定して得ることができる。
【０１１３】
また、本実施形態では、座標変換の正しさを評価し確認するための手法としてＲＡＮＳＡＣを用いているが、これに限定されない。追跡された動きベクトルと、求められた座標変換によるオフセットベクトルとの比較を、各々のベクトルを特徴方向に射影した１次元の比較とするものであればよい。いずれにしても、半特徴点を用いて座標変換式を評価・確認する際に、無特徴方向の誤差を無くすことができる。
【０１１４】
図１６は、全特徴と半特徴の整合判定概念図である。この図において、コーナーに全特徴２５、エッジに半特徴２６がある場合、追跡によって得られた動きベクトル３４、３５を実線で表し、候補の座標変換によるオフセットベクトル３６、３７を点線で表している。半特徴２６に付けられた太い矢印は、特徴方向の単位ベクトル３８である。全特徴２５は、単に２つのベクトル３４、３６によって移される座標が一定距離以内にあるかどうかを判定すればよい。これに対して、半特徴２６では、この場合、２つのベクトル３５、３７の向きも大きさも異なるが、特徴方向に射影する（特徴方向の単位ベクトル３８と内積した量をとる）とほぼ等しく、この半特徴２６の追跡と座標変換は整合していると判定できる。
【０１１５】
すなわち、ＲＡＮＳＡＣに半特徴を用いるにあたり、追跡による動きベクトルと、候補の座標変換式によって移された座標へのオフセットベクトルを、特徴方向に射影して比較し、ほぼ等しいならば適合点と判別するようにすれば、ベクトルの比較はウィンドウ内画素値比較に比べて計算量が少ないので、ＲＡＮＳＡＣのループ回数を多くすることができ、より良い変換式を探索することができる。
【０１１６】
また、特徴方向への射影を用いない別の方法として、画素値比較による適合判定も可能である。ＲＡＮＳＡＣに半特徴を用いるにあたり、第一の画像Ｉ1及び第二の画像Ｉ2の半特徴周辺のウィンドウの画素値を比較（相違度として差分絶対値和、差分自乗和等）し、相違が少なければ、適合点と判別するようにすれば、画素値の比較によるため、視覚的に目立つ二重映りを除外することができる。
【０１１７】
また、ＲＡＮＳＡＣのサポート計算において、サポート数として全特徴の適合点数Ｎf に、半特徴の適合点数Ｎs
よりも強い（大きい）重み値、例えば、２Ｎf ＋Ｎs のような重み値を用いるようにすれば、全特徴と半特徴の情報量の違いに対応した適正な重み付けを行うことができ、全特徴との一致性を高めることができる。また、全特徴は２次元の情報を持つのに対し、半特徴は１次元の情報しか持たないので、仮に全特徴と半特徴の数が均衡している場合には、精度のよい全特徴を優先させることにより、より安定した変換式を選択することができる。
【０１１８】
本発明は、部分的に重なる数枚以上の画像をつなぎ合わせて１枚の大きな範囲の画像を合成するパノラマ合成に応用することも可能である。２枚の画像の重なり領域をブロックマッチング等によって検出し、その後、本発明の手法を用いて、重なり領域内の特徴点を抽出・追跡し、座標変換を求めることができる。なお、合成処理においては単なる画素値の平均ではなく、境界が目立たないようにブレンディング処理等を行うことが望ましい。
【０１１９】
また、本発明は、動画における手振れ補正（電子式手振れ補正）にも応用可能である。すなわち、動画撮影あるいは再生において、手振れによる画面全体の動きベクトルを算出しそれを打ち消すように各フレームあるいはフィールドを平行移動することによって手振れを抑えて安定した動画を生成することができる。より具体的には、本発明の手法を用いて、特徴点抽出・追跡に続いて平行移動モデル等による座標変換によって求めると、画面の支配的な動きベクトルを得たことになる。画像を加算合成する代わりに新しいフレームあるいはフィールドを得られた動きベクトルによって平行移動した画像で逐次置換するようにすれば、手振れを抑えた動画を生成することができる。
【図面の簡単な説明】
【０１２０】
【図１】本実施形態の画像処理装置の概略構成図である。
【図２】特徴点抽出部１３ｂの動作フローチャートを示す図である。
【図３】所定の制約条件の説明図である。
【図４】ループＡの概念図（１／２）である。
【図５】ループＡの概念図（２／２）である。
【図６】ループＢの概念図（１／４）である。
【図７】ループＢの概念図（２／４）である。
【図８】ループＢの概念図（３／４）である。
【図９】ループＢの概念図（４／４）である。
【図１０】特徴点追跡部１３ｃの動作フローチャートを示す図である。
【図１１】全特徴と半特徴の概念図である。
【図１２】無特徴方向の成分を無視した半特徴の概念図である。
【図１３】無特徴方向の動きを特徴方向の動きのみに制約した半特徴の概念図及び追跡結果を示す図である。
【図１４】ＲＡＮＳＡＣ部１４の動作フローチャートを示す図である。
【図１５】サポート計算の動作フローチャートを示す図である。
【図１６】全特徴と半特徴の整合判定概念図である。
【図１７】従来技術の不都合を説明するための被写体の一例を示す図である。
【図１８】第一の構図７と第二の構図８における各々の特徴点を示す図である。
【符号の説明】
【０１２１】
１０  基準画像（第一の画像または第二の画像）
１１  被追跡画像（第一の画像または第二の画像）
１２  画像処理装置
１３  オプティカルフロー検出部（全特徴点検出手段、半特徴点検出手段）
１４  ＲＡＮＳＡＣ部（順位付け手段、選別手段、変換式算出手段、評価手段）
１５  画像合成部（位置合わせ手段）
２５  全特徴点
２６  半特徴点
【図１】
0004595733.tif 000050
【図２】
0004595733.tif 000051
【図３】
0004595733.tif 000052
【図４】
0004595733.tif 000053
【図５】
0004595733.tif 000054
【図６】
0004595733.tif 000055
【図７】
0004595733.tif 000056
【図８】
0004595733.tif 000057
【図９】
0004595733.tif 000058
【図１０】
0004595733.tif 000059
【図１１】
0004595733.tif 000060
【図１２】
0004595733.tif 000061
【図１３】
0004595733.tif 000062
【図１４】
0004595733.tif 000063
【図１５】
0004595733.tif 000064
【図１６】
0004595733.tif 000065
【図１７】
0004595733.tif 000066
【図１８】
0004595733.tif 000067