(57)【要約】【課題】２つの画像間を対応付ける変換行列をより効率的に導出可能とする。【解決手段】第１の画像と第２の画像とを対応付ける変換行列を導出する画像処理装置において、第１の画像における特徴点と第２の画像における特徴点とを関連付けた特徴点ペアのうち、一定数の特徴点ペアに基づいて変換行列の候補となる複数の候補行列を導出する候補行列導出手段と、複数の候補行列のそれぞれにおける特徴点ペアごとの投影誤差を算出する誤差算出手段と、複数の候補行列のうち特徴点ペアごとの投影誤差に基づいて１つの候補行列を変換行列として決定する決定手段と、を有する。誤差算出手段は、複数の候補行列それぞれについて特徴点ペアごとに順次投影誤差を算出し、所定数の特徴点ペアについての投影誤差を算出した時点で所定の条件を満たす場合、現在対象としている候補行列に対する投影誤差の算出を打ち切る。【選択図】図３
2017059049.tif 000002
【特許請求の範囲】
【請求項１】
第１の画像と第２の画像とを対応付ける変換行列を導出する画像処理装置であって、
前記第１の画像における特徴点と前記第２の画像における特徴点とを関連付けた特徴点ペアのうち、一定数の特徴点ペアに基づいて前記変換行列の候補となる複数の候補行列を導出する候補行列導出手段と、
前記複数の候補行列のそれぞれにおける特徴点ペアごとの投影誤差を算出する誤差算出手段と、
前記複数の候補行列のうち前記特徴点ペアごとの投影誤差に基づいて１つの候補行列を前記変換行列として決定する決定手段と、
を有し、
前記誤差算出手段は、前記複数の候補行列それぞれについて特徴点ペアごとに順次投影誤差を算出し、所定数の特徴点ペアについての投影誤差を算出した時点で所定の条件を満たす場合、現在対象としている候補行列に対する投影誤差の算出を打ち切る
ことを特徴とする画像処理装置。
【請求項２】
前記誤差算出手段は、
前記特徴点ペアのそれぞれについて、前記第１の画像における特徴点の座標を前記候補行列を用いて変換した座標と前記第２の画像における特徴点の座標との距離を前記投影誤差として算出する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記誤差算出手段は、
前記特徴点ペアのそれぞれについて、前記投影誤差が所定閾値以下であるインライアであるか否かを順次判定する判定処理を行い、
前記判定処理において前記所定数の特徴点ペアについての前記投影誤差を算出した時点でインライアと判定された特徴点ペアの割合が所定の割合以下であった場合に、現在対象としている候補行列に対する前記判定処理を打ち切り、
前記決定手段は、前記複数の候補行列のうちインライアの数が最大となる候補行列を前記変換行列として決定する
ことを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記所定の割合は、既に前記判定処理が終了した１以上の候補行列におけるインライアと判定された特徴点ペアの割合のうち最大のものである
ことを特徴とする請求項３に記載の画像処理装置。
【請求項５】
前記所定数は、所定整数の整数倍の値である
ことを特徴とする請求項１乃至４の何れか１項に記載の画像処理装置。
【請求項６】
前記所定数は、２のべき乗の値である
ことを特徴とする請求項１乃至４の何れか１項に記載の画像処理装置。
【請求項７】
前記所定の割合は、インライアと判定された特徴点ペアの割合に応じて設定された値を格納したルックアップテーブル（ＬＵＴ）に基づいて設定される
ことを特徴とする請求項３に記載の画像処理装置。
【請求項８】
前記第１の画像と前記第２の画像とは、撮像装置によって取得された時間的に連続する２つの画像フレームである
ことを特徴とする請求項１乃至７の何れか１項に記載の画像処理装置。
【請求項９】
前記第１の画像と前記第２の画像それぞれにおける特徴点を検出する検出手段と、
前記検出手段により検出された前記第１の画像と前記第２の画像それぞれにおける特徴点を関連付けて前記特徴点ペアを決定するマッチング手段と、
を更に含む
ことを特徴とする請求項１乃至８の何れか１項に記載の画像処理装置。
【請求項１０】
前記候補行列はホモグラフィ行列であり、前記一定数は４である
ことを特徴とする請求項１乃至９の何れか１項に記載の画像処理装置。
【請求項１１】
前記候補行列導出手段は、前記所定数の特徴点ペアをランダムに選択することにより前記複数の候補行列を導出する
ことを特徴とする請求項１乃至１０の何れか１項に記載の画像処理装置。
【請求項１２】
第１の画像と第２の画像とを対応付ける変換行列を導出する画像処理装置の制御方法であって、
前記第１の画像における特徴点と前記第２の画像における特徴点とを関連付けた特徴点ペアのうち、一定数の特徴点ペアに基づいて前記変換行列の候補となる複数の候補行列を導出する候補行列導出工程と、
前記複数の候補行列のそれぞれにおける特徴点ペアごとの投影誤差を算出する誤差算出工程と、
前記複数の候補行列のうち前記特徴点ペアごとの投影誤差に基づいて１つの候補行列を前記変換行列として決定する決定工程と、
を有し、
前記誤差算出工程では、前記複数の候補行列それぞれについて特徴点ペアごとに順次投影誤差を算出し、所定数の特徴点ペアについての投影誤差を算出した時点で所定の条件を満たす場合、現在対象としている候補行列に対する投影誤差の算出を打ち切る
ことを特徴とする画像処理装置の制御方法。
【請求項１３】
請求項１乃至１１の何れか１項に記載の画像処理装置の各手段としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像フレーム間の位置ずれ補正などのために複数の画像を対応付ける技術に関するものである。
【背景技術】
【０００２】
従来から、写真や動画を撮影する際の手ブレや、風などの影響による固定カメラの揺れなどによる画像，映像の乱れを軽減する目的で、撮影後のデジタルデータに対して補正を行う技術が数多く提案されている。また、近年のコンピュータ性能の向上に伴い、これらの処理をリアルタイムで行う要求が高まってきている。
【０００３】
時間的に連続する画像フレームの揺れを補正する技術の代表的な例として画像中の特徴点のマッチングによる位置合わせがある。この技術は、画像中に存在する特徴点を検出し、フレーム間での特徴点マッチングを行い、その特徴点の位置関係からフレーム間の位置ズレを表現する変換行列を算出するものである。この変換行列により、フレーム間の揺れ補正を実現する事が可能となる。変換行列はホモグラフィ行列、回転行列（非特許文献１）などを用いて表現する事ができる。
【０００４】
ところで、マッチングされた特徴点ペアの中には、ミスマッチングによる誤った特徴点ペアが含まれることがある。誤りを含んだ特徴点群から正しいフレームの揺れを表す変換行列を適切に推定するためにはロバスト推定技術が必要となる。ロバスト推定技術の代表的なアルゴリズムとしてＲＡＮＳＡＣ（RANdom SAmple Consensus）と呼ばれる技術がある（非特許文献２）。ＲＡＮＳＡＣは、特徴点群全体から、ランダムに特徴点ペアの一部をサンプリングして変換行列の算出を行い、特徴点全体に対してフレームの揺れをどの程度表しているかを評価する。この一連の処理を何度も繰り返し、その中から最も評価結果の良い変換行列を選択する。これにより、誤りを含んだ特徴点群からフレームの揺れを正しく表す変換行列を推定する事が出来る。
【０００５】
ロバスト推定においては、変換行列による投影誤差が閾値以下である特徴点ペアを「インライア」それ以外を「アウトライア」と呼ぶ。ＲＡＮＳＡＣでは、入力特徴点の点数に対してアウトライアの割合が多いほど、多くの繰り返し処理を必要とする。また、推定する変換行列の要素数が多いほど、多くの繰り返しを必要とする。そこで、特許文献１では、入力特徴点のマッチングを工夫する事により、ＲＡＮＳＡＣによる処理を高速化する技術が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１１−２５９０４４号公報
【非特許文献】
【０００７】
【非特許文献１】姿勢推定と回転行列，玉木徹，"IEICE Technical Report SIP2009-48，SIS2009-23(2009-09)"
【非特許文献２】"Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography"，M.A. Fischler and R.C. Bolles，Communications of the ACM，24(6):381-395，1981
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、算出した変換行列の評価処理するにあたって特徴点群全体に対して投影誤差を算出しインライア数をカウントする場合、処理コストが大きく処理時間も長くなる。上述の特許文献１においてもこの問題は解決できない。
【０００９】
本発明は、このような問題に鑑みてなされたものであり、２つの画像間の位置ずれを補正する変換行列をより効率的に導出可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述の問題点を解決するため、本発明に係る画像処理装置は以下の構成を備える。すなわち、第１の画像と第２の画像とを対応付ける変換行列を導出する画像処理装置において、前記第１の画像における特徴点と前記第２の画像における特徴点とを関連付けた特徴点ペアのうち、一定数の特徴点ペアに基づいて前記変換行列の候補となる複数の候補行列を導出する候補行列導出手段と、前記複数の候補行列のそれぞれにおける特徴点ペアごとの投影誤差を算出する誤差算出手段と、前記複数の候補行列のうち前記特徴点ペアごとの投影誤差に基づいて１つの候補行列を前記変換行列として決定する決定手段と、を有し、前記誤差算出手段は、前記複数の候補行列それぞれについて特徴点ペアごとに順次投影誤差を算出し、所定数の特徴点ペアについての投影誤差を算出した時点で所定の条件を満たす場合、現在対象としている候補行列に対する投影誤差の算出を打ち切る。
【発明の効果】
【００１１】
本発明によれば、２つの画像間の位置ずれを補正する変換行列をより効率的に導出可能とする技術を提供することができる。
【図面の簡単な説明】
【００１２】
【図１】第１実施形態に係る画像処理装置の構成を説明する図である。
【図２】変換行列の推定処理の全体フローチャートである。
【図３】変換行列の評価処理の詳細フローチャートである。
【図４】変形例における変換行列の評価処理の詳細フローチャートである。
【図５】インライア数の確率分布を示す図である。
【図６】異なるサンプル点数における分布を正規化したものを示す図である。
【図７】評価継続の有無を判定するために利用するＬＵＴを例示的に示す図である。
【発明を実施するための形態】
【００１３】
以下に、図面を参照して、この発明の好適な実施の形態を詳しく説明する。なお、以下の実施の形態はあくまで例示であり、本発明の範囲を限定する趣旨のものではない。
【００１４】
（第１実施形態）
本発明に係る画像処理装置の第１実施形態として、撮像部１０１により撮像された画像フレームに対して処理を行う画像処理装置を例に挙げて以下に説明する。
【００１５】
＜装置構成＞
図１は、第１実施形態に係る画像処理装置の構成を説明する図である。詳しくは後述するが、画像処理装置１００は、撮像部１０１により取得された時間的に連続する画像フレームのそれぞれから特徴点を検出する。そして、画像フレーム間で特徴点を対応付けて、画像フレーム間における特徴点の位置ズレを表す変換行列を推定するよう構成されている。
【００１６】
撮像部１０１は、例えばレンズ，センサー，レンズ制御部から成るカメラである。例えば、レンズ制御部は、レンズのズームやフォーカスを制御し、センサーは、レンズから取り込んだ光を受光してＲＧＢ画像データに変換し画像入力部１０２に出力する。なお、ここでは、撮像部１０１は、動画像データを画像入力部１０２に出力することを想定している。なお、動画像データに含まれる各画像フレームのサイズや、動画像データのフレームレートは任意のものが使用され得る。
【００１７】
画像入力部１０２は、撮像部１０１から出力されるＲＧＢ画像データを受信し、バス１０９を介して画像データ格納部１０３へ格納する。ここで、画像入力部１０２は、画像データ格納部１０３へ格納する際、ＲＧＢ画像データを所定の内部画像フォーマットに変換して保存してもよい。また、ここでは、画像入力部１０２に入力される画像データは、ＲＧＢ画像データであるとして説明するが、これに限定されずＹＵＶ画像あるいはモノクロ輝度画像でもよい。
【００１８】
特徴点検出部１０４は、画像データ格納部１０３に記録された画像データを取得し、画像に含まれる１以上の特徴点を検出する。検出した特徴点の情報は、対応する画像データと関連付ける形式で特徴点データ格納部１０５へ格納される。例えば、対応する画像フレームのフレーム番号の情報と関連付けて格納される。
【００１９】
特徴点マッチング部１０６は、検出された特徴点を画像フレーム間で対応付けるマッチングを行う。例えば、時間的に隣接する２つの画像フレーム間でマッチングを行う。そして、マッチング結果に基づいて、当該２つの画像フレーム間で特徴点を関連付ける。関連付けの結果は、例えば複数の特徴点ペアとして特徴点データ格納部１０５へ格納される。なお、マッチングの処理は既存の手法を用いて実施することを想定し、マッチング処理の結果において誤った特徴点ペアが含まれることがある。
【００２０】
変換行列推定部１０７は、画像フレーム間で対応付けされた特徴点の情報を特徴点データ格納部１０５から読み出し、変換行列を推定する。例えば、背景技術で述べたロバスト推定を用いて、位置ずれを最も良く表す変換行列を推定する。変換行列推定部１０７における処理の詳細については図２及び図３を参照して後述する。
【００２１】
画像補正部１０８は、変換行列推定部１０７にて推定された変換行列を用いて、画像データを変換した画像フレームを出力する。すなわち、先行する画像フレームとの位置ずれが補正された画像フレームを出力する。
【００２２】
なお、上述の各機能部は、ＣＰＵがソフトウェアプログラムを実行することにより実現されるほか、全部もしくは一部をハードウェアにより構成され得る。また、画像処理装置１００は、カメラ装置、組込みシステム、タブレット端末、スマートフォン、ＰＣ等の各種機器として構成され得る。
【００２３】
＜変換行列推定部１０７の動作＞
図２は、変換行列推定部１０７において実行される変換行列の推定処理の全体フローチャートである。ここでは、時間的に隣接する２つの画像フレームに対して、当該２つの画像フレーム間の位置ズレを精度良く表す変換行列を効率的に推定する手法について説明する。
【００２４】
なお、以下の説明においては、画像データ格納部１０３に格納された上述の２つの画像フレームに対して、特徴点検出部１０４及び特徴点マッチング部１０６による処理がすでに行われているものとする。すなわち、特徴点データ格納部１０５には、当該２つの画像フレームそれぞれの特徴点を関連付けた複数の特徴点ペアが格納されているものとする。
【００２５】
ステップＳ２０１では、変換行列推定部１０７は、変換行列推定処理の入力である複数の特徴点ペア（例えばＭ個）の中からランダムに一定数の特徴点ペアをサンプリングする。サンプリングする特徴点ペアの数は、求めたい変換行列によって異なる。例えば、求めたい変換行列がホモグラフィ行列である時、サンプリングする特徴点ペアの数は４点となる。
【００２６】
ステップＳ２０２では、変換行列推定部１０７は、サンプリングした一定数の特徴点ペアから連立方程式をたて、その連立方程式を解く事によって変換行列を算出する。すなわち、最終的に出力される変換行列の候補を導出する候補行列導出手段として機能する。例えば、変換行列がホモグラフィ行列である時、求める連立方程式は式（１）のように表すことが出来る。
【００２７】
【数１】
2017059049.tif 000003
【００２８】
ここで、（ｕｎ，ｖｎ）（ただしｎ＝０，１，２，３）は、時間的に連続する２つの画像フレームのうち先行する画像フレームにおける特徴点からサンプリングした４点の特徴点の座標である。また、（ｘｎ，ｙｎ）（ただしｎ＝０，１，２，３）は、上述の４点に対応付けられた後続の画像フレームにおける特徴点の座標である。
【００２９】
また、式（１）の連立方程式を解いた８つの解がそれぞれホモグラフィ行列
2017059049.tif 000004
の要素を表す。
【００３０】
このようにして導出された変換行列を、最終的に出力される変換行列の候補（候補行列）としてＳ２０３の処理に進む。
【００３１】
ステップＳ２０３では、変換行列推定部１０７は、ステップＳ２０２にて算出した変換行列が２つの画像フレーム間の位置ズレをどれだけ精度良く表しているかを評価する。具体的には、算出した変換行列が入力特徴点群に対してインライアをいくつ含んでいるかに基づいて、当該変換行列の投影誤差を評価する。評価の詳細は図３を参照して後述する。
【００３２】
ここで、「インライア」とは、先行する画像フレームの特徴点座標（始点座標）を変換行列で変換した座標（終点座標）と、後続の画像フレームの特徴点座標との距離（投影誤差）が閾値以下である特徴点ペアを意味する。なお、距離（投影誤差）が閾値を超える特徴点ペアは「アウトライア」と呼ぶ。
【００３３】
ステップＳ２０４では、変換行列推定部１０７は、ステップＳ２０３にて判定したインライアの個数と、既に判定した１以上の変換行列におけるインライアの最大数とを比較する。そして、現在対象としている変換行列に対するインライアの個数が最高値を更新した場合にはステップＳ２０５へと進む。一方、現在対象としている変換行列に対するインライアの個数が最高値を更新しなかった場合には、ステップＳ２０６に進む。
【００３４】
ステップＳ２０５では、変換行列推定部１０７は、インライアの個数が最高値を更新した変換行列を、画像フレーム間の位置ズレを最も精度良く表すペスト変換行列として更新（設定）する。
【００３５】
ステップＳ２０６では、変換行列推定部１０７は、ロバスト推定の繰り返しの終了条件を満たすか否かを判定する。終了条件としては、例えば、Ｓ２０１〜Ｓ２０６のループの繰り返し回数、予め設定された処理時間などを用いることができる。終了条件を満たす場合はＳ２０７に進み、満たさない場合はＳ２０１に戻る。
【００３６】
ステップＳ２０７では、変換行列推定部１０７は、Ｓ２０６において終了条件を満たすと判定された時点でのペスト変換行列を出力する。すなわち、Ｓ２０１〜Ｓ２０６のループで処理した１以上の変換行列の中で、投影誤差が最小の変換行列を決定し出力する。
【００３７】
以上説明したように、変換行列推定部１０７は、ロバスト推定処理に基づいて変換行列を推定し出力する。以下では、上述の変換行列の評価処理（Ｓ２０３）における処理高速化の手法について更に説明する。
【００３８】
図３は、変換行列の評価処理（Ｓ２０３）の詳細手順を示すフローチャートである。上述したように、ここでは、Ｓ２０２で算出した変換行列を対象としてインライアの個数を判定し、当該変換行列の投影誤差の評価を行う。
【００３９】
ステップＳ２０３１では、変換行列推定部１０７は、特徴点データ格納部１０５に格納された複数の特徴点ペアの中から１組の特徴点ペアをランダムにサンプリングする。ここでは、サンプリングした特徴点ペアを（ｕｍ，ｖｍ），（ｘｍ，ｙｍ）（ただしｍ＝０）とする。
【００４０】
ステップＳ２０３２では、変換行列推定部１０７は、ステップＳ２０３１にてサンプリングした特徴点ペアのうち先行する画像フレームの特徴点を、Ｓ２０２にて算出した変換行列を用いて変換し、投影誤差を算出（誤差算出）する。
【００４１】
具体的には、先行する画像フレームの特徴点の座標を、Ｓ２０２にて算出したホモグラフィ行列Ｈを用いて投影した座標（ｘ’ｍ，ｙ’ｍ）を算出する。そして、投影誤差Ｅｍを下記の式（２）、式（３）により求める。
【００４２】
【数２】
2017059049.tif 000005
【００４３】
【数３】
2017059049.tif 000006
【００４４】
ステップＳ２０３３では、変換行列推定部１０７は、算出した投影誤差が閾値以内であるかを判定する。具体的には、式（３）により算出される距離が閾値以内であるか否かを判定する。閾値は、例えば、１〜３（画素）のような値が与えられる。投影誤差が所定閾値以下である場合には、Ｓ２０３１にてサンプリングされた特徴点ペアをインライアと判定し、Ｓ２０３４に進む。一方、投影誤差が閾値よりも大きい場合には、当該特徴点ペアをアウトライアであると判定し、Ｓ２０３５に進む。
【００４５】
ステップＳ２０３４では、変換行列推定部１０７は、インライアと判定された特徴点ペアの個数をカウントアップする。
【００４６】
ステップＳ２０３５では、変換行列推定部１０７は、現在対象としている変換行列に対して評価した特徴点ペアの個数（評価点数）が所定数（Ｎ個（Ｎ＜Ｍ））であるかを判定する。所定数は、所定整数の整数倍の値とすることが出来、ここでは、所定整数は２のべき乗である８などが使用される。評価点数が所定数である場合にはＳ２０３６に進み、所定数でない場合はＳ２０３７に進む。
【００４７】
ステップＳ２０３６では、変換行列推定部１０７は、現在のインライア率と、所定のインライア率（インライアの個数の割合）とを比較する。ここでは、所定のインライア率として、現時点での暫定的なベストインライア率を用いる。ここで、現在のインライア率とは、現在対象としている変換行列に対する現時点でのインライアの個数を所定数で除した値である。また、現時点での暫定的なベストインライア率とは、現在対象としている変換行列の評価に先行して評価が行われた他の１以上の変換行列におけるインライア率の最高値である。
【００４８】
比較の結果、現在のインライア率がベストインライア率よりも高い場合には、ステップＳ２０３７に進む。一方、現在のインライア率がベストインライア率以下（所定の割合以下）であった場合には、現在対象としている変換行列に対する評価を打ち切り、ステップＳ２０３８に進む。
【００４９】
ステップＳ２０３７では、変換行列推定部１０７は、特徴点データ格納部１０５に格納された複数の特徴点ペアの全てを評価したか否かを判定する。このようにして、特徴点ペアに対してインライアであるか否かを順次判定する判定処理を行い、すべての特徴点ペアの評価が終了した場合にはＳ２０３８に進む。一方、未評価の特徴点ペアが存在する場合はＳ２０３１に進み、未評価の特徴点ペアを１つ選択し、順次投影誤差を算出する。
【００５０】
ステップＳ２０３８では、変換行列推定部１０７は、現在対象としている変換行列に対するインライアの個数を出力し、変換行列評価処理を終了する。
【００５１】
上述したように変換行列の評価において、特徴点ペアの全てを評価する処理は、ロバスト推定処理の処理時間の中でも大きな割合を占める。そこで、第１実施形態においては、評価処理（Ｓ２０３）の実行中において段階的に評価継続の要否を判定する（Ｓ２０３６）のである。そして、判定インライア数が最高値を更新する見込みのない変換行列に対しては、特徴点ペアの全てを評価することを取りやめるのである。すなわち、当該変換行列に対してその時点で未評価の特徴点ペアについては評価処理を省く。この制御により、処理時間を大きく短縮させる事が可能となる。
【００５２】
なお、上述のＳ２０３６の判定条件においては、現在対象としている変換行列に対して、最高値を更新できる見込みがないと誤判定してしまう可能性が存在する。この誤判定の可能性をさらに低減するために、判定条件にマージンを持たせても良い。例えば、Ｓ２０３６において、「現在のインライア率に０．０５（５％）加えた値」と「暫定のベストインライア率」とを比較するよう構成してもよい。
【００５３】
以上説明したとおり第１実施形態によれば、変換行列（候補行列）の評価処理において、判定インライア数が最高値を更新する見込みがない場合に評価処理を打ち切る。これにより、ロバスト推定の処理時間を短縮する事が可能となる。すなわち、２つの画像間の位置ずれを補正する変換行列をより効率的に導出することが可能となる。
【００５４】
（変形例）
なお、上述の第１実施形態においては、変換行列の評価処理において、評価点数が所定整数の整数倍の値である所定数となったタイミングでのインライア率に基づき、評価処理を継続するか否かを判定する構成について説明した。ただし、他のタイミングで判定を行うよう構成してもよい。
【００５５】
図４は、変形例における変換行列の評価処理の詳細フローチャートである。この例では、Ｓ３０５で、現在対象としている変換行列に対して評価した特徴点ペアの個数（評価点数）が所定数であるかを判定する。ただし、所定数として、２のべき乗の値（例えば、８，１６，３２．．．）を設定しており、評価点数が２のべき乗の値となるごとに、評価処理を継続するか否かを判定している。
【００５６】
（第２実施形態）
第２実施形態では、第１実施形態における評価継続の判定条件（Ｓ２０３６）とは異なる判定条件を用いる形態について説明する。すなわち、インライアの個数が最高値を更新する可能性が低いことを判定可能な他の条件を評価継続の判定条件として使用しても良い。
【００５７】
例えば、３００個の特徴点ペアの内、潜在的な真のインライアが３０個である場合（すなわちインライア率は１０％）を考える。潜在的な真のインライアの数とは、フレーム間の位置ズレを最も精度良く表すベスト変換行列が与えられた時のインライアの数である。ロバスト推定処理ではこのベスト変換行列を推定する事が目的となる。
【００５８】
上述のような３００個の特徴点ペアが与えられ、その中からランダムにサンプリングした４個の点より算出した変換行列を評価する場合を考える。この場合、部分的に評価した特徴点ペアのうちいくつの特徴点ペアがインライアとして判定されるかは超幾何分布（Hypergeometric distribution）に従う。超幾何分布に従う確率密度関数は次式で表される。
【００５９】
【数４】
2017059049.tif 000007
ここで、
Ｎ：全ての特徴点ペアの個数、
ｎ：サンプリングして評価した特徴点ペアの個数、
Ｘ：Ｎに含まれる真のインライアの個数、
ｘ：評価した特徴点ペアに含まれるインライアの個数
である。（式（４）において、Ｃは組合せの数を示す）
例えば、上述のように真のインライアを３０個を含む３００個の特徴点ペアの中からランダムにサンプリング１６点を評価した場合、インライアが１個である確率は式（４）を用いて式（５）のように計算する事ができる。
【００６０】
【数５】
2017059049.tif 000008
【００６１】
図５は、インライア率（真のインライア数の割合）それぞれにおけるインライア数の確率分布を示す図である。ここでは、サンプリング点数が８，１６，３２，６４の４通りの分布をそれぞれ図５（ａ）〜（ｄ）として示している。なお、図５（ａ）〜（ｄ）それぞれにおいて、真のインライア数の割合が１０，３０，５０，７０，９０％の５つの場合に対する分布を示している。
【００６２】
図５から理解されるように、サンプリング点数を増やしていくに従って、インライア数の確率分布はより急峻な分布になっていく事がわかる。
【００６３】
図６は、真のインライア数の割合が１０％の場合について、異なるサンプル点数におけるそれぞれの分布を正規化したものを例示的に示す図である。図６において、８，１６，３２，６４の各サンプル数に対応する分布は、図５（ａ）〜（ｄ）の１０％の分布にそれぞれ対応している。
【００６４】
図６から、サンプリング点数が少ない場合ほど分布がいびつな（ゆがんだ）形状となっていることが分かる。その結果、変換行列の評価継続の判定条件として、第１実施形態（Ｓ２０３６）の条件を利用した場合、誤判定により評価処理が打ち切られる確率が高くなることが理解される。ベストインライア率を更新する可能性のある変換行列に対して全ての特徴点ペアを評価せずに終了してしまう確率が高くなる。この傾向はインライア率が低い場合に顕著である。
【００６５】
逆に、インライア率が高い場合には、ベストインライア率を更新しない可能性のある変換行列に対して、誤判定により、全ての特徴点ペアを評価してしまう確率が高くなる。この結果、無駄な評価処理が多くなり処理時間が増加してしまう。
【００６６】
このような問題を解決するために、例えば、変換行列の評価継続の判定条件としてのインライア数が暫定のベストインライア率に応じて異なるよう構成したルックアップテーブル（ＬＵＴ）を予め用意し判定に利用するよう構成してもよい。
【００６７】
図７は、評価継続の要否を判定するために利用するＬＵＴを例示的に示す図である。ここでは、暫定のインライア率と評価点の数（評価した特徴点ペアの個数）との組み合わせに対して、閾値となるインライア数を示している。特に、閾値となるインライア数は、累積確率が５０％を超えるように設定している。
【００６８】
以上説明したとおり第２実施形態によれば、変換行列の評価継続の判定条件としてのインライア数が暫定のベストインライア率に応じて異なるよう構成したルックアップテーブル（ＬＵＴ）を利用する。これにより、変換行列の評価継続の判定をより正確に行うことが可能となる。
【００６９】
（その他の実施例）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【００７０】
１０１  撮像部；  １０２  画像入力部；  １０３  画像データ格納部；  １０４  特徴点検出部；  １０５  特徴点データ格納部；  １０６  特徴点マッチング部；  １０７  変換行列推定部；  １０８  画像補正部；  １０９  バス
【図１】
2017059049.tif 000009
【図２】
2017059049.tif 000010
【図３】
2017059049.tif 000011
【図４】
2017059049.tif 000012
【図５】
2017059049.tif 000013
【図６】
2017059049.tif 000014
【図７】
2017059049.tif 000015