(57)【要約】【課題】画像同士の位置合わせに用いる変換モデルのパラメータを精度良く計算すること。【解決手段】第１画像Ｐ１が有する第１特徴点ｑ１と、第２画像Ｐ２が有する第２特徴点ｑ２と、第１画像Ｐ１上の点を第２画像Ｐ２上の対応する点へと変換する変換モデルＴＭとを記憶する記憶部１１と、設定された第１閾値Ｔｈ１より特徴量が大きい第１及び第２特徴点ｑ１、ｑ２の集合を用いて変換モデルＴＭに含まれるパラメータＡの推定値Ａ１を計算し、第１閾値Ｔｈ１より小さい第２閾値Ｔｈ２よりも特徴量が大きく、かつ、推定値Ａ１を適用した変換モデルＴＭに対する誤差が設定した範囲内にある第１特徴点ｑ１と第２特徴点ｑ２との組を選択し、選択した組毎にパラメータＡ及び当該パラメータＡの評価値を計算し、評価値に基づいてパラメータＡを決定する演算部１２とを有する、情報処理装置１０が提供される。【選択図】図１
2015179426.tif 000002
【特許請求の範囲】
【請求項１】
第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、前記第１画像上の点を前記第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部と、
設定された第１閾値より特徴量が大きい前記第１及び第２特徴点の集合を用いて前記変換モデルに含まれるパラメータの推定値を計算し、前記第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、前記推定値を適用した前記変換モデルに対する誤差が設定した範囲内にある前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータ及び当該パラメータの評価値を計算し、前記評価値に基づいて前記パラメータを決定する演算部と
を有する、情報処理装置。
【請求項２】
前記演算部は、
前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合から前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータを計算し、当該パラメータと前記推定値との差が設定した許容値よりも小さい場合に前記誤差が前記設定した範囲内にあると判断する
請求項１に記載の情報処理装置。
【請求項３】
前記演算部は、
抽出される前記第１特徴点同士の距離及び抽出される前記第２特徴点同士の距離が第１設定値より大きくなるように抽出した前記第１及び第２特徴点の集合から、前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合を特定する
請求項１又は２に記載の情報処理装置。
【請求項４】
前記演算部は、
前記パラメータの評価値を計算する処理において、当該パラメータの計算に用いていない前記第１特徴点を選択し、当該パラメータを適用した前記変換モデルで当該第１特徴点を変換し、変換後の点と当該第２特徴点との距離が第２設定値より小さい場合に当該パラメータに対する第１投票数を増加させ、選択したすべての前記第１特徴点に関する前記第１投票数の累積値を当該パラメータに対する前記評価値とする
請求項１〜３のいずれか１項に記載の情報処理装置。
【請求項５】
前記演算部は、
前記パラメータの評価値を計算する処理において、当該パラメータに対する前記第１投票数を増加させる際に当該パラメータの計算に用いた前記第１特徴点に対する第２投票数を増加させ、前記第１特徴点を選択する場合に前記第２投票数が小さい順に前記第１特徴点を選択する
請求項４に記載の情報処理装置。
【請求項６】
前記演算部は、
前記推定値の計算に用いていない前記第１特徴点を選択し、前記推定値を適用した前記変換モデルで当該第１特徴点を変換し、変換後の点と当該第２特徴点との距離が前記第２設定値より小さくなる場合に当該第１特徴点に対する第３投票数を増加させ、選択したすべての前記第１特徴点に関する前記第３投票数の累積値を上限値に設定し、前記第２投票数が前記上限値より大きい場合に当該第２投票数で前記上限値を更新し、
前記パラメータの評価値を計算する処理において、当該パラメータによる前記変換後の点と前記第２特徴点との距離が前記第２設定値より大きくなる前記第１特徴点の数が前記上限値に達した場合に、当該パラメータに対する前記評価値の計算を回避する
請求項５に記載の情報処理装置。
【請求項７】
前記演算部は、
前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合から前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に、前記推定値を適用した前記変換モデルで前記第１特徴点を変換し、変換後の点を基準に設定した領域に前記第２特徴点が含まれるか否かを判定し、当該領域に前記第２特徴点が含まれる場合に前記誤差が前記設定した範囲内にあると判断する
請求項１〜４のいずれか１項に記載の情報処理装置。
【請求項８】
第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、前記第１画像上の点を前記第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部から、前記第１特徴点、前記第２特徴点、及び前記変換モデルの情報を取得可能なコンピュータが、
設定された第１閾値より特徴量が大きい前記第１及び第２特徴点の集合を用いて前記変換モデルに含まれるパラメータの推定値を計算し、前記第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、前記推定値を適用した前記変換モデルに対する誤差が設定した範囲内にある前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータ及び当該パラメータの評価値を計算し、前記評価値に基づいて前記パラメータを決定する
パラメータの決定方法。
【請求項９】
第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、前記第１画像上の点を前記第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部から、前記第１特徴点、前記第２特徴点、及び前記変換モデルの情報を取得可能なコンピュータに、
設定された第１閾値より特徴量が大きい前記第１及び第２特徴点の集合を用いて前記変換モデルに含まれるパラメータの推定値を計算し、前記第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、前記推定値を適用した前記変換モデルに対する誤差が設定した範囲内にある前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータ及び当該パラメータの評価値を計算し、前記評価値に基づいて前記パラメータを決定する
処理を実行させる、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、パラメータの決定方法、及びプログラムに関する。
【背景技術】
【０００２】
撮像デバイスとして利用できる身近な携帯機器には、例えば、デジタルカメラ、スマートフォン、及び携帯電話などがある。こうした撮像デバイスの処理能力は年々向上しており、最近では撮像デバイスの内部で高度な画像処理を行うことが可能になってきている。例えば、電子式手ぶれ補正の機能やＨＤＲ（High Dynamic Range）撮影の機能などは、連続して撮像された複数枚の画像に対する高度な画像処理により実現される。
【０００３】
動画撮影時に適用される電子式手ぶれ補正は、連続する動画フレーム間で被写体の位置がずれないように位置を合わせて表示する技術である。また、静止画撮影時に適用される電子式手ぶれ補正は、速いシャッター速度で連続撮影された複数枚の画像を位置合わせして合成する技術である。また、ＨＤＲ撮影は、露出を変えて撮像した複数枚の画像を合成して白飛びや黒つぶれの少ない画像を生成する技術である。ＨＤＲ撮影の場合も画像同士の位置合わせが行われる。
【０００４】
画像同士の位置合わせは、一方の画像に含まれる複数の特徴点と他方の画像に含まれる複数の特徴点とが最も良く適合するように一方の画像を変換する処理に相当する。例えば、手ぶれに伴う画像の並進移動、回転、拡大・縮小などをアフィン変換の変換パラメータで表現し、複数画像の特徴点を用いて変換パラメータを決め、その変換パラメータを適用して画像全体を変換することにより、画像同士の位置合わせが実現される。
【０００５】
変換パラメータを計算する方法としては、例えば、ＲＡＮＳＡＣ（RANdom SAmple Consensus）法がある。但し、ＲＡＮＳＡＣ法による変換パラメータの計算は、ロバスト性に優れる一方で演算量が多い。そのため、ＲＡＮＳＡＣ法に基づく変換パラメータの計算を上記のような撮像デバイスに実行させると処理に時間がかかる。また、考慮する変換の自由度が高く、変換パラメータの種類が多くなるほど、ＲＡＮＳＡＣ法に基づく変換パラメータの計算に長い処理時間がかかる。
【０００６】
このような事情を受け、ＲＡＮＳＡＣ法に基づく変換パラメータの計算を２段階に分けて実行する技術が提案されている。この技術の１段階目では、並進移動に対応する変換パラメータだけを含む変換モデルを用いてＲＡＮＳＡＣ法により画像同士の位置合わせを行い、許容範囲内で一致する特徴点の組み合わせを抽出する。２段階目では、並進移動や回転に対応する変換パラメータを含む変換モデルを用い、１段階目で抽出した特徴点を利用してＲＡＮＳＡＣ法により変換パラメータを計算する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００９−１２２８４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記の技術を適用した場合、計算負荷を低減できる可能性がある。但し、変換パラメータの計算を２段階に分ける技術を適用した場合、回転や拡大・縮小の成分が大きい画像に適用する場合には、１段階目で正しく特徴点の組み合わせが抽出できない可能性がある。この場合、２段階目の処理を実行しても正しい変換パラメータが得られない。また、１段階目の処理に適用する変換パラメータの種類を増加させたり、許容範囲を拡大して１段階目で抽出される特徴点の数を増加させたりすれば、演算量の削減効果が抑制される。つまり、変換パラメータの計算を高速化するに際し、現実的な撮影状況において変換パラメータを精度良く計算することが課題となる。
【０００９】
そこで、１つの側面によれば、本発明の目的は、画像同士の位置合わせに用いる変換モデルのパラメータを精度良く計算することが可能な情報処理装置、パラメータの決定方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００１０】
本開示の１つの側面によれば、第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、第１画像上の点を第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部と、設定された第１閾値より特徴量が大きい第１及び第２特徴点の集合を用いて変換モデルに含まれるパラメータの推定値を計算し、第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、推定値を適用した変換モデルに対する誤差が設定した範囲内にある第１特徴点と第２特徴点との組を選択し、選択した組毎にパラメータ及び当該パラメータの評価値を計算し、評価値に基づいてパラメータを決定する演算部とを有する、情報処理装置が提供される。
【００１１】
また、本開示の他の１つの側面によれば、第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、第１画像上の点を第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部から、第１特徴点、第２特徴点、及び変換モデルの情報を取得可能なコンピュータが、設定された第１閾値より特徴量が大きい第１及び第２特徴点の集合を用いて変換モデルに含まれるパラメータの推定値を計算し、第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、推定値を適用した変換モデルに対する誤差が設定した範囲内にある第１特徴点と第２特徴点との組を選択し、選択した組毎にパラメータ及び当該パラメータの評価値を計算し、評価値に基づいてパラメータを決定するパラメータの決定方法が提供される。
【００１２】
また、本開示の他の１つの側面によれば、第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、第１画像上の点を第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部から、第１特徴点、第２特徴点、及び変換モデルの情報を取得可能なコンピュータに、設定された第１閾値より特徴量が大きい第１及び第２特徴点の集合を用いて変換モデルに含まれるパラメータの推定値を計算し、第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、推定値を適用した変換モデルに対する誤差が設定した範囲内にある第１特徴点と第２特徴点との組を選択し、選択した組毎にパラメータ及び当該パラメータの評価値を計算し、評価値に基づいてパラメータを決定する処理を実行させる、プログラムが提供される。
【発明の効果】
【００１３】
本発明によれば、画像同士の位置合わせに用いる変換モデルのパラメータを精度良く計算することが可能になる。
【図面の簡単な説明】
【００１４】
【図１】第１実施形態に係る情報処理装置の一例を示した図である。
【図２】ＲＡＮＳＡＣ法について説明するための図である。
【図３】ＲＡＮＳＡＣ法によるパラメータの計算について処理の流れを示したフロー図である。
【図４】ＲＡＮＳＡＣ法によるパラメータの計算を画像処理へと適用する例を示した図である。
【図５】第２実施形態に係る情報処理装置が有する機能を実現可能なハードウェアの一例を示した図である。
【図６】第２実施形態に係る情報処理装置の機能について説明するためのブロック図である。
【図７】第２実施形態に係る特徴点情報の一例を示した図である。
【図８】第２実施形態に係る投票数テーブルの一例を示した図である。
【図９】第２実施形態に係るカウンタテーブルの一例を示した図である。
【図１０】第２実施形態に係る前段処理（特徴点ペアの抽出）について説明するための図である。
【図１１】第２実施形態に係る前段処理（投票処理）について説明するための図である。
【図１２】第２実施形態に係る前段処理（推定変換行列の決定）について説明するための図である。
【図１３】第２実施形態に係る後段処理（最大投票数の計算）について説明するための図である。
【図１４】第２実施形態に係る後段処理（特徴点ペアの抽出）について説明するための図である。
【図１５】第２実施形態に係る後段処理（変換行列の比較）について説明するための図である。
【図１６】第２実施形態に係る後段処理（投票処理）について説明するための図である。
【図１７】第２実施形態に係る後段処理（変換行列の決定）について説明するための図である。
【図１８】第２実施形態に係る情報処理装置が実行する処理の全体的な流れを示したフロー図である。
【図１９】第２実施形態に係る情報処理装置が実行する前段処理の流れを示した第１のフロー図である。
【図２０】第２実施形態に係る情報処理装置が実行する前段処理の流れを示した第２のフロー図である。
【図２１】第２実施形態に係る情報処理装置が実行する後段処理の流れを示した第１のフロー図である。
【図２２】第２実施形態に係る情報処理装置が実行する後段処理の流れを示した第２のフロー図である。
【図２３】第２実施形態に係る情報処理装置が実行する後段処理の流れを示した第３のフロー図である。
【図２４】第３実施形態に係る後段処理の概要を示した図である。
【図２５】第３実施形態に係る情報処理装置の機能について説明するためのブロック図である。
【図２６】第３実施形態に係る許容範囲情報の一例を示した図である。
【図２７】第３実施形態に係るペアマップリストの一例を示した図である。
【図２８】第３実施形態に係るペアマップリストの生成方法について説明するための第１の図である。
【図２９】第３実施形態に係るペアマップリストの生成方法について説明するための第２の図である。
【図３０】第３実施形態に係る後段処理（変換行列の決定）について説明するための図である。
【図３１】第３実施形態に係る情報処理装置が実行する後段処理の流れを示した第１のフロー図である。
【図３２】第３実施形態に係る情報処理装置が実行する後段処理の流れを示した第２のフロー図である。
【図３３】第３実施形態に係る情報処理装置が実行する後段処理のうち、ペアマップリストの生成に関する処理の流れを示したフロー図である。
【図３４】第２及び第３実施形態の組み合わせについて説明するための第１の図である。
【図３５】第２及び第３実施形態の組み合わせについて説明するための第２の図である。
【図３６】第２及び第３実施形態の組み合わせに係る後段処理の流れを示したフロー図である。
【発明を実施するための形態】
【００１５】
以下に添付図面を参照しながら、本発明の実施形態について説明する。なお、本明細書及び図面において実質的に同一の機能を有する要素については、同一の符号を付することにより重複説明を省略する場合がある。
【００１６】
＜１．第１実施形態＞
図１を参照しながら、第１実施形態について説明する。図１は、第１実施形態に係る情報処理装置の一例を示した図である。なお、図１に例示した情報処理装置１０は、第１実施形態に係る情報処理装置の一例である。
【００１７】
図１に示すように、情報処理装置１０は、記憶部１１、及び演算部１２を有する。
なお、記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性記憶装置、或いは、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置である。演算部１２は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサである。但し、演算部１２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの電子回路であってもよい。また、演算部１２は、例えば、記憶部１１又は他のメモリに記憶されたプログラムを実行する。
【００１８】
記憶部１１は、第１画像Ｐ１が有する第１特徴点ｑ１と、第２画像Ｐ２が有する第２特徴点ｑ２と、第１画像Ｐ１上の点を第２画像Ｐ２上の対応する点へと変換する変換モデルＴＭとを記憶する。例えば、第１画像Ｐ１、第２画像Ｐ２は、連続して撮影された画像である。また、第１特徴点ｑ１は、特徴量が設定した閾値より大きい点である。例えば、第１画像Ｐ１の画素毎に特徴量を検出し、検出した特徴量が設定した閾値より大きい画素を抽出することで、第１特徴点ｑ１が得られる。
【００１９】
同様に、第２特徴点ｑ２は、特徴量が設定した閾値より大きい点である。例えば、第２画像Ｐ２の画素毎に特徴量を検出し、検出した特徴量が設定した閾値より大きい画素を抽出することで、第２特徴点ｑ２が得られる。特徴量としては、例えば、エッジ検出により得られるエッジの強度（勾配の大きさ）やエッジの方向（勾配方向）がある。勾配方向を利用する場合、注目画素の周囲にある画素のうち注目画素とは勾配方向が異なる画素の数を検出し、その数が設定した閾値より多い注目画素を抽出して特徴点とする。
【００２０】
図１の例では、第１特徴点ｑ１として、第１特徴点ｑ１１、ｑ１２、…、ｑ１６が示されている。第１特徴点ｑ１１、ｑ１２、ｑ１３は、対象物Ｃ１１の特徴部分を示す特徴点である。また、第１特徴点ｑ１４、ｑ１５、ｑ１６は、対象物Ｃ１２の特徴部分を示す特徴点である。
【００２１】
また、図１の例では、第２特徴点ｑ２として、第２特徴点ｑ２１、ｑ２２、…、ｑ２６が示されている。第２特徴点ｑ２１、ｑ２２、ｑ２３は、対象物Ｃ２１の特徴部分を示す特徴点である。また、第２特徴点ｑ２４、ｑ２５、ｑ２６は、対象物Ｃ２２の特徴部分を示す特徴点である。なお、対象物Ｃ１１、Ｃ２１は同じ被写体を表す。また、対象物Ｃ１２、Ｃ２２は同じ被写体を表す。但し、図１の例では、第１画像Ｐ１の撮影時と第２画像Ｐ２の撮影時とで撮影状況（露出の変化や撮影者の手ぶれによる撮像範囲のずれなど）が異なるため、第１特徴点ｑ１と第２特徴点ｑ２とが一致していない。
【００２２】
演算部１２は、設定された第１閾値Ｔｈ１より特徴量が大きい第１特徴点ｑ１及び第２特徴点ｑ２の集合を用いて変換モデルＴＭに含まれるパラメータＡの推定値Ａ１を計算する。変換モデルＴＭとしては、例えば、アフィン変換の変換モデルなどを適用することが可能である。この場合、パラメータＡは、並進移動、回転、拡大・縮小を表す複数のパラメータを含む変換行列となる。
【００２３】
なお、第１特徴点ｑ１及び第２特徴点ｑ２の抽出時に利用した閾値よりも第１閾値Ｔｈ１を高く設定することで、対象物Ｃ１１、Ｃ１２、Ｃ２１、Ｃ２２の特徴を表す特徴点としての信頼度が高い第１特徴点ｑ１及び第２特徴点ｑ２の集合が得られる。そのため、第１閾値Ｔｈ１を利用して特徴点を絞り込む上記の方法を適用すれば、推定値Ａ１の計算に利用する特徴点をランダムに選択する方法に比べて高い推定精度を得ることができる。
【００２４】
推定値Ａ１を計算した演算部１２は、第１閾値Ｔｈ１より小さい第２閾値Ｔｈ２よりも特徴量が大きく、かつ、推定値Ａ１を適用した変換モデルＴＭに対する誤差が設定した範囲内にある第１特徴点ｑ１と第２特徴点ｑ２との組を選択する。また、演算部１２は、選択した組毎にパラメータＡ及び当該パラメータＡの評価値を計算する。そして、演算部１２は、評価値に基づいてパラメータＡを決定する。
【００２５】
上記のように、第２閾値Ｔｈ２が第１閾値Ｔｈ１より小さいことで、推定値Ａ１の計算に利用した第１特徴点ｑ１及び第２特徴点ｑ２よりも多くの特徴点が選択の対象となる。但し、推定値Ａ１を適用した変換モデルＴＭに対する誤差が大きい組については評価値の計算が回避される。
【００２６】
上記のように、推定値Ａ１は、特徴量の大きな特徴点を利用して計算されており、すべての第１特徴点ｑ１及び第２特徴点ｑ２を利用して計算したパラメータＡの値に近いと考えられる。そのため、誤差の大きい組を利用してパラメータＡを計算しても、そのパラメータＡの評価値は小さくなり、パラメータＡの決定に寄与しない。このように、パラメータＡの決定に寄与しない組を候補から除外して評価値の計算を回避することにより、パラメータＡの計算精度を維持しつつ、演算量を低減することができる。
【００２７】
なお、上記の誤差は、第１特徴点ｑ１と第２特徴点ｑ２との組から計算されたパラメータＡと推定値Ａ１との差や、推定値Ａ１を適用した変換モデルＴＭを利用して第１特徴点ｑ１を変換した点と第２特徴点ｑ２との距離に基づいて評価することが可能である。また、評価値の計算方法としては、例えば、ＲＡＮＳＡＣ法に基づく計算に利用される投票処理を適用可能である。この場合、評価値は投票数となり、投票数が最大となるパラメータＡが決定される。なお、図１の例では、候補となるパラメータＡとしてパラメータＡ２１、Ａ２２、…が示され、投票によりパラメータＡ２１が決定されている。
【００２８】
以上、第１実施形態について説明した。
＜２．第２実施形態＞
次に、第２実施形態について説明する。第２実施形態は、ＲＡＮＳＡＣ法に基づく変換パラメータの計算を２段階で実行する方法に関し、計算精度を維持しつつ演算量の削減を実現する仕組みを提案するものである。
【００２９】
［２−１．ＲＡＮＳＡＣ法について］
ここで、図２及び図３を参照しながら、ＲＡＮＳＡＣ法について説明する。なお、図２は、ＲＡＮＳＡＣ法について説明するための図である。また、図３は、ＲＡＮＳＡＣ法によるパラメータの計算について処理の流れを示したフロー図である。
【００３０】
ＲＡＮＳＡＣ法は、多数のデータを良く表す数式モデルを推定する方法の一つである。ＲＡＮＳＡＣ法では、ランダムに取り出したデータの組を用いて数式モデルのパラメータを計算する処理、及びそのパラメータを適用した数式モデルと他のデータとの誤差が許容可能な範囲に含まれるか否かを判定する処理が繰り返し実行される。
【００３１】
データが許容可能な範囲に含まれることをインライヤと呼び、データが許容可能な範囲に含まれないことをアウトライヤと呼ぶ。ＲＡＮＳＡＣ法では、パラメータ毎にインライヤとなるデータの数がカウントされ、カウント数が最も多いパラメータが最適なパラメータに決定される。つまり、決定されたパラメータを適用した数式モデルが、データを良く表す数式モデルの推定結果とされる。
【００３２】
図２には、ｘ−ｙ座標系に配置された複数のデータ（座標点）から数式モデル（ｙ＝ａｘ）のパラメータ（ａ）を推定する方法が例示されている。この例では数式モデルが一次式であるため、２つのデータがあればパラメータを計算することができる。例えば、ランダムに２つのデータ（ｘ１，ｙ１）、（ｘ２，ｙ２）が取り出された場合、パラメータａは、（ｙ２−ｙ１）／（ｘ２−ｘ１）で与えられる。
【００３３】
ランダムに取り出された２つのデータからパラメータａが計算されると、計算されたパラメータａを適用した数式モデル（ｙ＝ａｘ）と他のデータとの距離ｄが計算される。そして、許容範囲（図２の例では２つの鎖線ｌ１、ｌ２間の領域）に含まれるデータの数（インライヤとなるデータの数）がカウントされる。同様に、データの取り出し、パラメータａの計算、及びインライヤとなるデータ数のカウントが繰り返し実行され、最大カウント数のパラメータａが最適なパラメータに決定される。
【００３４】
なお、データの取り出し、パラメータａの計算、及びインライヤとなるデータ数のカウントを繰り返す回数は、下記の式（１）で与えられるサンプリング回数Ｔ以上に設定される。但し、Ｆは数式モデルの自由度を表し、Ｅはアウトライヤとなるデータの割合を表し、Ｐは正しい数式モデルが得られる確率を表す。つまり、繰り返し回数をＴ以上にすれば、確率Ｐ以上で正しい数式モデルが得られる。
【００３５】
【数１】
2015179426.tif 000003
パラメータを推定する方法の一つである最小二乗法の場合、アウトライヤとなるデータがパラメータの推定結果に影響を与えてしまう。一方、ＲＡＮＳＡＣ法の場合、インライヤとなるデータを用いてパラメータが推定されるため、アウトライヤとなるデータがパラメータの推定結果に影響を及ぼさないという利点がある。
【００３６】
ここで、図３を参照しながら、ＲＡＮＳＡＣ法によるパラメータの計算について処理の流れを説明する。
図３に示すように、まず、ランダムに２つのデータが選択される（Ｓ１１）。次いで、Ｓ１１で選択されたデータを用いてパラメータが計算される（Ｓ１２）。次いで、Ｓ１１で選択されたデータを除く残りのデータから１つのデータが抽出される（Ｓ１３）。次いで、Ｓ１３で抽出されたデータがインライヤか否かが判定される（Ｓ１４）。インライヤである場合、処理はＳ１５へと進む。一方、アウトライヤである場合、処理はＳ１６へと進む。
【００３７】
処理がＳ１５へと進んだ場合、Ｓ１２で計算されたパラメータに対する投票が行われる（Ｓ１５）。つまり、パラメータ毎に投票数が設定されており、Ｓ１２で計算されたパラメータの投票数が１増加する。Ｓ１５の処理が完了すると、処理はＳ１６へと進む。
【００３８】
処理がＳ１６へと進んだ場合、Ｓ１１で選択されたデータを除く残りのデータがすべてＳ１３で抽出されたか否かが判定される（Ｓ１６）。残りのデータがすべてＳ１３で抽出されている場合、処理はＳ１７へと進む。一方、Ｓ１３で抽出されていないデータがある場合、処理はＳ１３へと進む。
【００３９】
処理がＳ１７へと進んだ場合、Ｓ１１からＳ１７へと至る一連の処理がＴ回実行されたか（Ｔ回ループしたか）が判定される（Ｓ１７）。ループ回数を示すＴは、例えば、上記の式（１）により与えられる。Ｔ回ループした場合、処理はＳ１８へと進む。一方、Ｔ回ループしていない場合、処理はＳ１１へと進む。
【００４０】
処理がＳ１８へと進んだ場合、投票数が最大のパラメータが出力される（Ｓ１８）。つまり、インライヤとなるデータの数が最大となるパラメータが出力される。Ｓ１８の処理が完了すると、図３に示した一連の処理は終了する。
【００４１】
上記のように、ＲＡＮＳＡＣ法による計算処理は、Ｓ１１からＳ１７へと至る外側のループ処理と、Ｓ１３からＳ１６へと至る内側のループ処理とを含む。内側のループ処理は、パラメータの計算に利用していないすべてのデータを対象に、インライヤとなるか否かの判定を実行して投票を行う処理（以下、投票処理）である。そのため、データの数が増加すると投票処理を実行する回数が飛躍的に増大する。第２実施形態では、計算精度を維持しつつ投票処理の実行回数を低減する仕組みを提案する。
【００４２】
（画像処理への適用例）
ここで、図４を参照しながら、ＲＡＮＳＡＣ法によるパラメータの計算を画像処理へと適用する例について説明する。図４は、ＲＡＮＳＡＣ法によるパラメータの計算を画像処理へと適用する例を示した図である。
【００４３】
画像処理技術としては、複数の画像を利用して画質を向上させる技術や、複数の画像を照合して認証を行う技術などがある。例えば、動画撮影時に適用される電子式手ぶれ補正は、動画フレーム間で位置合わせを行い、重なる領域をクロップして表示することにより手ぶれによる表示画像の乱れを抑制する技術である。また、静止画撮影時に適用される電子式手ぶれ補正は、速いシャッター速度で複数枚の画像を撮像し、画像同士の位置を合わせて合成した上で重なる領域をクロップすることにより、手ぶれや被写体ぶれによる画像の乱れを抑制する技術である。
【００４４】
また、ＨＤＲ撮影は、露出の異なる複数の画像を連続して撮影し、画像同士の位置を合わせて合成した上で重なる領域をクロップすることにより、露光不足や露光過多による白飛びや黒つぶれを抑制したダイナミックレンジの広い画像を生成する技術である。また、静脈認証、光彩認証、顔認証などの認証技術は、テンプレート画像と撮像画像とを照合して本人確認を行う技術である。
【００４５】
上記のような画像処理技術は、いずれも画像同士の位置合わせを利用する。なお、ここで言う画像同士の位置合わせとは、対象となる画像間における並進移動、回転、拡大・縮小などを補正することである。例えば、連続して撮像された画像であっても、被写体ぶれや手ぶれなどの影響で画像間に様々なずれが生じる。ずれが生じた状態で画像同士を重ね合わせても画質の向上や認証精度の向上などの効果は得られない。そこで、画像同士の位置合わせを実行してから表示、合成、認証などの各種処理が実行される。
【００４６】
図４には、連続して撮像された２つの画像Ｐ１、Ｐ２を合成する処理の流れが例示されている。図４の例では、画像Ｐ１に４つの特徴点ｑ１０、…、ｑ１３が含まれ、画像Ｐ２に４つの特徴点ｑ２０、…、ｑ２３が含まれている。画像Ｐ１の座標と画像Ｐ２の座標との関係は、例えば、アフィン変換の変換モデル（下記の式（２）を参照）により表現できる。但し、（ｘ１，ｙ１）は画像Ｐ１上の座標である。また、（ｘ２，ｙ２）は画像Ｐ２上の座標である。また、ｗ１１、ｗ１２、…、ｗ２３は変換パラメータである。
【００４７】
【数２】
2015179426.tif 000004
上記の変換モデルにより画像Ｐ１に含まれる各画素の座標変換を行えば、画像Ｐ２との位置合わせが実現される。例えば、画像Ｐ１を座標変換した画像を画像Ｐ３とすると、２つの画像Ｐ２、Ｐ３を合成することで高画質な画像Ｐ４が得られる。このような画像の合成を精度良く行うには、上記の変換パラメータｗ１１、ｗ１２、…、ｗ２３を精度良く求めることが大事になる。そのため、変換パラメータｗ１１、ｗ１２、…、ｗ２３の計算に対してロバスト性に優れるＲＡＮＳＡＣ法を適用することは好適である。
【００４８】
ＲＡＮＳＡＣ法を適用する場合、特徴点ｑ１０、…、ｑ２２からランダムに取り出した特徴点の組み合わせを用いて変換パラメータｗ１１、ｗ１２、…、ｗ２３が計算され、上述した投票処理が実行される。また、変換パラメータｗ１１、ｗ１２、…、ｗ２３の計算及び投票処理が繰り返し行われ、最大の投票数を得た変換パラメータｗ１１、ｗ１２、…、ｗ２３が画像Ｐ１の座標変換に利用される。但し、実際に画像に含まれる特徴点の数は多いため、第２実施形態では演算量を削減する仕組みを提案する。
【００４９】
（その他の適用例）
ＲＡＮＳＡＣ法によるパラメータの計算は、画像処理以外の用途にも利用可能である。例えば、声紋認証や音声解析などを行う際に音声データの特徴点をマッチングさせる用途で利用できる。この場合、２つの音声データに含まれる特徴点が抽出され、特徴点間の関係を表現した変換モデルのパラメータがＲＡＮＳＡＣ法により計算される。以下では、説明の都合上、画像同士の位置合わせを想定して説明を進めるが、第２実施形態に係る技術の適用範囲はこれに限定されず、ＲＡＮＳＡＣ法を適用可能な任意の分野に及ぶ。
【００５０】
以上、ＲＡＮＳＡＣ法について説明した。
［２−２．ハードウェア］
次に、図５を参照しながら、第２実施形態に係る変換パラメータの計算方法を実現可能な情報処理装置１００のハードウェアについて説明する。なお、情報処理装置１００は、第２実施形態に係る情報処理装置の一例である。また、図５は、第２実施形態に係る情報処理装置が有する機能を実現可能なハードウェアの一例を示した図である。
【００５１】
後述する情報処理装置１００の機能は、例えば、図５に示す情報処理装置のハードウェア資源を用いて実現することが可能である。つまり、情報処理装置１００が有する機能は、コンピュータプログラムを用いて図５に示すハードウェアを制御することにより実現される。
【００５２】
図５に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ（Read Only Memory）９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０とを有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６とを有する。
【００５３】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータなどを格納する記憶装置の一例である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に変化する各種パラメータなどが一時的又は永続的に格納される。
【００５４】
これらの要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、タッチパッド、ボタン、スイッチ、及びレバーなどが用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラが用いられることもある。
【００５５】
出力部９１８としては、例えば、ＣＲＴ（Cathode Ray Tube）、ＬＣＤ（Liquid Crystal Display）、ＰＤＰ（Plasma Display Panel）、又はＥＬＤ（Electro-Luminescence Display）などのディスプレイ装置が用いられる。また、出力部９１８として、スピーカやヘッドホンなどのオーディオ出力装置、又はプリンタなどが用いられることもある。つまり、出力部９１８は、情報を視覚的又は聴覚的に出力することが可能な装置である。
【００５６】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ＨＤＤなどの磁気記憶デバイスが用いられる。また、記憶部９２０として、ＳＳＤ（Solid State Drive）やＲＡＭディスクなどの半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイスなどが用いられてもよい。
【００５７】
ドライブ９２２は、着脱可能な記録媒体であるリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリなどが用いられる。
【００５８】
接続ポート９２４は、例えば、ＵＳＢ（Universal Serial Bus）ポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ（Small Computer System Interface）、ＲＳ−２３２Ｃポート、又は光オーディオ端子など、外部接続機器９３０を接続するためのポートである。外部接続機器９３０としては、例えば、プリンタなどが用いられる。
【００５９】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスである。通信部９２６としては、例えば、有線又は無線ＬＡＮ（Local Area Network）用の通信回路、ＷＵＳＢ（Wireless USB）用の通信回路、光通信用の通信回路やルータ、ＡＤＳＬ（Asymmetric Digital Subscriber Line）用の通信回路やルータ、携帯電話ネットワーク用の通信回路などが用いられる。通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークであり、例えば、インターネット、ＬＡＮ、放送網、衛星通信回線などを含む。
【００６０】
以上、情報処理装置１００のハードウェアについて説明した。
［２−３．情報処理装置の機能］
次に、図６を参照しながら、情報処理装置１００の機能について説明する。図６は、第２実施形態に係る情報処理装置の機能について説明するためのブロック図である。なお、以下の説明において、適宜、図７〜図１７を参照する。
【００６１】
図６に示すように、情報処理装置１００は、記憶部１０１、撮像部１０２、特徴点抽出部１０３、前段処理部１０４、後段処理部１０５、及び画像処理部１０６を有する。
なお、記憶部１０１の機能は、上述したＲＡＭ９０６や記憶部９２０などを用いて実現できる。特徴点抽出部１０３、前段処理部１０４、後段処理部１０５、及び画像処理部１０６の機能は、上述したＣＰＵ９０２などを用いて実現できる。
【００６２】
（記憶部１０１）
記憶部１０１には、特徴点情報１０１ａ、モデル情報１０１ｂ、投票数テーブル１０１ｃ、及びカウンタテーブル１０１ｄが格納される。特徴点情報１０１ａは、画像から抽出された特徴点に関する情報である。モデル情報１０１ｂは、画像の位置合わせに利用する変換モデルに関する情報である。投票数テーブル１０１ｃ、カウンタテーブル１０１ｄは、投票処理の中で投票数を管理するために利用されるテーブルである。
【００６３】
ここで、図７を参照しながら、特徴点情報１０１ａについて、さらに説明する。図７は、第２実施形態に係る特徴点情報の一例を示した図である。
図７の例では、位置合わせの対象となる２つの画像Ｐ１、Ｐ２それぞれから抽出された特徴点に関する情報（座標、特徴量）が特徴点情報１０１ａに含まれている。なお、画像Ｐ１の特徴点と画像Ｐ２の特徴点とは対応付けられていない。特徴量としては、例えば、エッジ検出により得られるエッジの強度（勾配の大きさ）やエッジの方向（勾配方向）がある。エッジの方向を示す特徴量は、例えば、注目画素の周囲にある画素のうち注目画素とは勾配方向が異なる画素の数に基づく指標で表現される。
【００６４】
ここで、モデル情報１０１ｂについて、さらに説明する。
モデル情報１０１ｂには、変換モデルを表現する数式及び変換パラメータの情報が含まれる。変換モデルとしては、例えば、上記の式（１）で表現されるアフィン変換の変換モデルなどが適用可能である。アフィン変換の場合、変換パラメータは変換行列の形式で表現される。この変換行列は６つの変換パラメータを含む。そのため、画像Ｐ１の特徴点と画像Ｐ２の特徴点とのペア（以下、特徴点ペア）を３組用意すれば変換行列を計算することができる。
【００６５】
ここで、図８を参照しながら、投票数テーブル１０１ｃについて、さらに説明する。図８は、第２実施形態に係る投票数テーブルの一例を示した図である。
図８に示すように、投票数テーブル１０１ｃは、変換行列の計算に利用した特徴点ペアと、計算した変換行列に含まれるパラメータと、投票処理の中で当該パラメータに投票された投票数とを対応付けるテーブルである。例えば、図８の例では、３組の特徴点ペア（ｑ１４，ｑ２２）、（ｑ１３，ｑ２２）、（ｑ１１，ｑ２７）について変換パラメータ（０．３１，０．２６，０．６１，０．１８，０．５３，０．１２）が得られている。また、この変換パラメータに対して投票数（１０）が対応付けられている。
【００６６】
ここで、図９を参照しながら、カウンタテーブル１０１ｄについて、さらに説明する。図９は、第２実施形態に係るカウンタテーブルの一例を示した図である。
図９に示すように、カウンタテーブル１０１ｄは、一方の画像に含まれる特徴点と、カウンタ値とを対応付けるテーブルである。図９の例では、画像Ｐ１の特徴点ｑ１０、ｑ１１、…、ｑ１ｎのそれぞれと、カウンタ値とが対応付けられている。カウンタ値は、投票処理の中でインライヤと判定された特徴点ペアに含まれる特徴点をカウントした値である。カウンタテーブル１０１ｄは、投票処理を実行する際にインライヤか否かの判定を行う特徴点の選択順序を制御する際に利用される。
【００６７】
（撮像部１０２、特徴点抽出部１０３）
再び図６を参照する。撮像部１０２は、カメラ機能を提供する要素であり、画像を撮像する。例えば、撮像部１０２は、光学系、撮像素子、アナログ／デジタル変換回路、及び制御回路などを含む。撮像部１０２により撮像された画像（以下、画像Ｐ１、Ｐ２）は、記憶部１０１に格納されると共に、特徴点抽出部１０３に入力される。特徴点抽出部１０３は、入力された画像Ｐ１、Ｐ２のそれぞれから特徴点を抽出し、特徴点情報１０１ａを生成する。特徴点抽出部１０３により生成された特徴点情報１０１ａは記憶部１０１に格納される。
【００６８】
（前段処理部１０４）
前段処理部１０４は、特徴量の大きな特徴点を用いて変換行列の推定値（以下、推定変換行列）を計算する。なお、以下では、前段処理部１０４が実行する処理を「前段処理」と呼ぶ場合がある。前段処理を実行するために、前段処理部１０４は、図６に示すように、パラメータ計算部１４１、及び投票処理部１４２を含む。
【００６９】
パラメータ計算部１４１は、記憶部１０１に格納された特徴点情報１０１ａを参照し、画像Ｐ１から抽出された特徴点のうち、特徴量が大きい順に予め設定された数（Ｘ個）の特徴点を抽出する。また、パラメータ計算部１４１は、画像Ｐ２から抽出された特徴点のうち、特徴量が大きい順に予め設定された数（Ｘ個）の特徴点を抽出する。そして、パラメータ計算部１４１は、抽出した特徴点から特徴点ペアを選択し、変換モデルに含まれる変換行列を計算する。
【００７０】
パラメータ計算部１４１は、選択した特徴点ペアの情報と、計算した変換行列の変換パラメータとを投票数テーブル１０１ｃに記録する。また、パラメータ計算部１４１により計算された変換行列は、投票処理部１４２に入力される。投票処理部１４２は、パラメータ計算部１４１により画像Ｐ１について抽出されたＸ個の特徴点のうち、入力された変換行列の計算に利用されていない特徴点を順次選択し、選択した特徴点がインライヤであるか否かを判定する。
【００７１】
例えば、投票処理部１４２は、入力された変換行列を用いて、選択した画像Ｐ１の特徴点を変換し、変換後の点を基準とする許容範囲内に画像Ｐ２の特徴点が存在するか否かを判定する。許容範囲内に画像Ｐ２の特徴点が存在する場合、投票処理部１４２は、選択した画像Ｐ１の特徴点がインライヤであると判定する。なお、投票処理部１４２は、変換後の点と画像Ｐ２の特徴点との最短距離が許容範囲内にあるか否かを判定し、最短距離が許容範囲内にある場合にインライヤであると判定してもよい。
【００７２】
投票処理部１４２は、インライヤと判定する度に、入力された変換行列の変換パラメータに投票する。つまり、投票処理部１４２は、インライヤと判定した場合に、入力された変換行列の変換パラメータに対応する投票数テーブル１０１ｃの投票数を設定した数（例えば、１）だけ増加させる。Ｘ個の特徴点すべてについて上記の判定が終了した場合、投票処理部１４２は、入力された変換行列に関する投票処理の終了をパラメータ計算部１４１に通知する。この通知を受けたパラメータ計算部１４１は、未選択の特徴点ペアを選択し、変換モデルに含まれる変換行列を計算する。
【００７３】
パラメータ計算部１４１は、選択した特徴点ペアの情報と、計算した変換行列の変換パラメータとを投票数テーブル１０１ｃに記録する。また、パラメータ計算部１４１により計算された変換行列は、投票処理部１４２に入力される。投票処理部１４２は、パラメータ計算部１４１により画像Ｐ１について抽出されたＸ個の特徴点のうち、入力された変換行列の計算に利用されていない特徴点を順次選択し、選択した特徴点がインライヤであるか否かを判定する。そして、投票処理部１４２は、インライヤと判定する度に、入力された変換行列の変換パラメータに投票する。
【００７４】
上記と同様に、パラメータ計算部１４１は、画像Ｐ１、Ｐ２からＸ個ずつ抽出された特徴点から順次特徴点ペアを選択して変換行列を計算する。そして、投票処理部１４２は、計算された変換行列に対して投票処理を実行する。特徴点ペアとして抽出可能なすべての組み合わせを選択し終えた場合、前段処理部１０４は、投票数テーブル１０１ｃを参照し、投票数が最大の変換行列（推定変換行列）を抽出する。前段処理部１０４により抽出された推定変換行列の情報は、記憶部１０１に格納されると共に、後段処理部１０５に入力される。
【００７５】
（後段処理部１０５）
後段処理部１０５は、記憶部１０１に格納された特徴点情報１０１ａに含まれる特徴点のうち、推定変換行列の計算に利用した特徴点の数よりも多くの特徴点を利用して画像Ｐ１、Ｐ２の位置合わせに用いる変換行列を計算する。このとき、後段処理部１０５は、推定変換行列に基づいて、変換行列の計算に用いる特徴点ペアを絞り込む。なお、以下では、後段処理部１０５が実行する処理を「後段処理」と呼ぶ場合がある。後段処理を実行するために、後段処理部１０５は、図６に示すように、パラメータ計算部１５１、候補抽出部１５２、及び投票処理部１５３を含む。
【００７６】
パラメータ計算部１５１は、記憶部１０１に格納された特徴点情報１０１ａを参照し、画像Ｐ１から抽出された特徴点と、画像Ｐ２から抽出された特徴点とのペアである特徴点ペアをランダムに選択し、変換モデルに含まれる変換行列を計算する。このとき、パラメータ計算部１５１は、記憶部１０１に格納されたカウンタテーブル１０１ｄを参照し、投票数が最小の特徴点から順に特徴点を選択してもよい。パラメータ計算部１５１により計算された変換行列は、候補抽出部１５２に入力される。
【００７７】
また、パラメータ計算部１５１は、選択した特徴点ペアの情報と、計算した変換行列の変換パラメータとを投票数テーブル１０１ｃに記録する。このとき、パラメータ計算部１５１は、推定変換行列の計算時に前段処理部１０４が利用した投票数テーブル１０１ｃとは異なる投票数テーブル１０１ｃを用意し、用意した投票数テーブル１０１ｃに特徴点ペアの情報と変換パラメータとを記録する。
【００７８】
候補抽出部１５２は、入力された変換行列と推定変換行列との誤差を計算し、誤差が許容範囲内であるか否かを判定する。例えば、候補抽出部１５２は、変換パラメータの種類（回転、並進移動、拡大・縮小など）毎に、入力された変換行列に含まれる変換パラメータと、推定変換行列に含まれる変換パラメータとの差（差分絶対値など）を計算する。そして、候補抽出部１５２は、計算した差が予め設定された許容値より小さいか否かを判定する。但し、上記の許容値は、変換パラメータの種類毎に設定される。
【００７９】
誤差が許容範囲内である場合、候補抽出部１５２は、入力された変換行列を投票処理部１５３に入力する。この場合、誤差が許容範囲内であると判定された変換行列について、後述する投票処理部１５３による投票処理が実行される。一方、誤差が許容範囲外である場合、候補抽出部１５２は、誤差が許容範囲外である旨をパラメータ計算部１５１に通知する。この場合、誤差が許容範囲外であると判定された変換行列について、後述する投票処理部１５３による投票処理は実行されない。
【００８０】
変換行列が入力された投票処理部１５３は、画像Ｐ１から抽出された特徴点のうち、入力された変換行列の計算に利用されていない特徴点を順次選択し、選択した特徴点がインライヤであるか否かを判定する。
【００８１】
例えば、投票処理部１５３は、入力された変換行列を用いて、選択した画像Ｐ１の特徴点を変換し、変換後の点を基準とする許容範囲内に画像Ｐ２の特徴点が存在するか否かを判定する。許容範囲内に画像Ｐ２の特徴点が存在する場合、投票処理部１５３は、選択した画像Ｐ１の特徴点がインライヤであると判定する。なお、投票処理部１５３は、変換後の点と画像Ｐ２の特徴点との最短距離が許容範囲内にあるか否かを判定し、最短距離が許容範囲内にある場合にインライヤであると判定してもよい。
【００８２】
投票処理部１５３は、インライヤと判定する度に、入力された変換行列の変換パラメータに投票する。つまり、投票処理部１５３は、インライヤと判定した場合に、入力された変換行列の変換パラメータに対応する投票数テーブル１０１ｃの投票数を設定した数（例えば、１）だけ増加させる。さらに、投票処理部１５３は、インライヤと判定した場合に、入力された変換行列の計算に利用された特徴点ペアに含まれる画像Ｐ１の特徴点について、カウンタテーブル１０１ｄのカウント値を増加させる。
【００８３】
すべての特徴点について上記の判定が終了した場合、投票処理部１５３は、入力された変換行列に関する投票処理の終了をパラメータ計算部１５１に通知する。この通知を受けたパラメータ計算部１５１は、未選択の特徴点ペアを選択し、変換モデルに含まれる変換行列を計算する。
【００８４】
パラメータ計算部１５１は、選択した特徴点ペアの情報と、計算した変換行列の変換パラメータとを投票数テーブル１０１ｃに記録する。また、パラメータ計算部１５１により計算された変換行列は、候補抽出部１５２に入力される。候補抽出部１５２は、入力された変換行列に対する判定処理を実行する。投票処理部１５３は、変換行列が入力された場合に、入力された変換行列の計算に利用されていない特徴点を順次選択し、選択した特徴点がインライヤであるか否かを判定する。そして、投票処理部１５３は、インライヤと判定する度に、入力された変換行列の変換パラメータに投票する。
【００８５】
上記と同様に、パラメータ計算部１５１は、画像Ｐ１、Ｐ２から抽出された特徴点から順次特徴点ペアを選択して変換行列を計算する。そして、候補抽出部１５２は、選択された変換行列に対する判定処理を実行する。また、投票処理部１５３は、変換行列が入力された場合に、計算された変換行列に対して投票処理を実行する。これらの処理が予め設定された回数（例えば、上記の式（１）で与えられるＴ）実行された場合、後段処理部１０５は、投票数テーブル１０１ｃを参照し、投票数が最大の変換行列を抽出する。
【００８６】
後段処理部１０５により抽出された変換行列の情報は、画像処理部１０６に入力される。画像処理部１０６は、入力された変換行列を用いて画像Ｐ１に含まれる画素の座標変換を実行する。そして、画像処理部１０６は、変換後の画像Ｐ１、及び画像Ｐ２を利用して予め設定された画像処理を実行する。例えば、画像処理部１０６は、電子式手ぶれ補正、ＨＤＲ画像の生成、各種の認証処理などを実行する。
【００８７】
（前段処理：推定変換行列の計算）
ここで、図１０〜図１２を参照しながら、前段処理について、さらに説明する。
なお、図１０は、第２実施形態に係る前段処理（特徴点ペアの抽出）について説明するための図である。また、図１１は、第２実施形態に係る前段処理（投票処理）について説明するための図である。また、図１２は、第２実施形態に係る前段処理（推定変換行列の決定）について説明するための図である。
【００８８】
図１０に示すように、画像Ｐ１からｎ個（例えば、ｎ＝１００）の特徴点ｑ１０、ｑ１１、…、ｑ１ｎが検出され、画像Ｐ２からｍ個（例えば、ｍ＝８０）の特徴点ｑ２０、ｑ２１、…、ｑ２ｍが検出されている場合について考える。この場合、パラメータ計算部１４１は、画像Ｐ１から検出された特徴点のうち、特徴量が大きい順にＸ個（図１０の例ではＸ＝１０）の特徴点を抽出する。また、パラメータ計算部１４１は、画像Ｐ２から検出された特徴点のうち、特徴量が大きい順にＸ個（図１０の例ではＸ＝１０）の特徴点を抽出する。
【００８９】
特徴量の大きな特徴点は、特徴点としての信頼性が高い特徴点である。また、特徴量の大きな特徴点を抽出することは、特徴点の選択基準となる閾値を上げることに相当する。上記のように、特徴点の数を減らすことで、画像Ｐ１の特徴点と画像Ｐ２の特徴点とを組み合わせて特徴点ペアを生成する際、組み合わせ数を大幅に低減することが可能になる。考え得る特徴点ペアの数が少なくなれば、投票処理部１４２による投票処理の実行回数が少なくなり、処理負荷が低減される。
【００９０】
パラメータ計算部１４１は、抽出した特徴点の中から特徴点の組み合わせを選択して、変換行列を計算するに足りる数の特徴点ペアを生成する。上記の式（２）で与えられるアフィン変換の変換モデルを利用する場合、少なくとも３組の特徴点ペアを利用すれば変換行列を計算することが可能である。そのため、図１０には、３組の特徴点ペアを生成する例を示した。なお、特徴点を抽出する際、特徴点間の距離を考慮してもよい。特徴点間の距離を考慮する方法については後段において述べる。
【００９１】
上記のように特徴点ペアを生成した後、パラメータ計算部１４１は、図１１に示すように、生成した特徴点ペアを利用して変換行列を計算する。なお、ｉ番目に生成された特徴点ペアに対応する変換行列をＲｉ（ｉ＝１，２，…）と表記する。つまり、パラメータ計算部１４１は、変換行列Ｒｉの変換パラメータｒ１１、ｒ１２、…、ｒ２３を計算する。計算された変換行列Ｒｉは、投票処理部１４２による投票処理に利用される。
【００９２】
投票処理部１４２は、パラメータ計算部１４１により抽出された画像Ｐ１の特徴点から１つずつ特徴点を選択し、選択した特徴点の座標を変換行列Ｒｉにより変換する。そして、投票処理部１４２は、変換後の座標と画像Ｐ２の特徴点とが許容範囲内にあるか否かを判定する。
【００９３】
図１１の例では、画像Ｐ１の特徴点ｑ１５に対応する変換後の座標ａと、画像Ｐ２の特徴点ｑ２７とが許容範囲内に収まっている。画像Ｐ１の特徴点ｑ１７についても同様である。一方、画像Ｐ１の特徴点ｑ１６に対応する変換後の座標ｂを基準とする許容範囲内には画像Ｐ２の特徴点が存在しない。この場合、特徴点ｑ１５、ｑ１７はインライヤであると判定され、特徴点ｑ１６はアウトライヤであると判定される。インライヤと判定した場合、投票処理部１４２は、変換行列Ｒｉの投票数を増加させる。
【００９４】
パラメータ計算部１４１により抽出された画像Ｐ１の特徴点（Ｘ個）をすべて選択し終えた場合、投票処理部１４２は、変換行列Ｒｉに対する投票処理の完了をパラメータ計算部１４１に通知する。この通知を受けたパラメータ計算部１４１は、他の特徴点ペアを生成する。そして、再び投票処理部１４２による投票処理が実行される。図１２に示すように、特徴点ペアの抽出、及び投票処理が繰り返し実行される。例えば、取り得るすべての特徴点ペアについて処理が完了するまで処理が繰り返し実行される。但し、繰り返し回数が予め設定されていてもよい。
【００９５】
繰り返し処理が完了すると、図１２に示すような投票数テーブル１０１ｃが得られる。図１２の例では、変換パラメータに対応する変換行列の情報を併せて記載している。例えば、投票処理部１４２は、投票数テーブル１０１ｃのレコードを投票数が多い順にソートし、最上位に位置するレコードに対応する変換行列を抽出する。図１２の例では、変換行列Ｒ３が最大投票数に対応する。そして、投票処理部１４２は、抽出した変換行列（図１２の例ではＲ３）を推定変換行列Ｒに設定する。推定変換行列Ｒの設定が完了すると、前段処理は終了する。
【００９６】
（後段処理：変換行列の決定）
次に、図１３〜図１７を参照しながら、後段処理について、さらに説明する。
なお、図１３は、第２実施形態に係る後段処理（最大投票数の計算）について説明するための図である。また、図１４は、第２実施形態に係る後段処理（特徴点ペアの抽出）について説明するための図である。また、図１５は、第２実施形態に係る後段処理（変換行列の比較）について説明するための図である。また、図１６は、第２実施形態に係る後段処理（投票処理）について説明するための図である。また、図１７は、第２実施形態に係る後段処理（変換行列の決定）について説明するための図である。
【００９７】
図１３に示すように、後段処理部１０５は、処理の過程で参照する指標（最大投票数）の初期値を計算する。この指標は、最終的に採用されない変換行列に対する投票処理を途中で判定するために利用される。例えば、現時点で投票数が最大となる変換行列があり、他の変換行列に対する投票処理の中でインライヤとなる特徴点の数が、現時点で最大の投票数を下回ることが確定した場合、他の変換行列は最終的に採用されない。この場合、他の変換行列に対する投票処理を継続しても無駄である。そこで、無駄な処理を省くために上記の指標（最大投票数）を導入する。
【００９８】
投票処理部１５３は、画像Ｐ１の特徴点から１つずつ特徴点を選択し、選択した特徴点の座標を推定変換行列Ｒにより変換する。このとき、投票処理部１５３により選択される特徴点は、前段処理で利用されたＸ個の特徴点に制限されず、画像Ｐ１から抽出された特徴点すべて、又はＸ個以上の特徴点が利用される。投票処理部１５３は、変換後の座標と画像Ｐ２の特徴点とが許容範囲内にあるか否かを判定する。
【００９９】
図１３の例では、画像Ｐ１の特徴点ｑ１５に対応する変換後の座標ａと、画像Ｐ２の特徴点ｑ２７とが許容範囲内に収まっている。画像Ｐ１の特徴点ｑ１７についても同様である。一方、画像Ｐ１の特徴点ｑ１６に対応する変換後の座標ｂを基準とする許容範囲内には画像Ｐ２の特徴点が存在しない。この場合、特徴点ｑ１５、ｑ１７はインライヤであると判定され、特徴点ｑ１６はアウトライヤであると判定される。インライヤと判定した場合、投票処理部１５３は、最大投票数を増加させる。
【０１００】
最大投票数が計算された後、パラメータ計算部１５１は、図１４に示すように、画像Ｐ１、Ｐ２の特徴点から特徴点の組み合わせをランダムに選択して、変換行列を計算するに足りる数の特徴点ペアを生成する。但し、パラメータ計算部１５１は、推定変換行列Ｒの計算に利用した特徴点ペアとは異なる特徴点ペアを生成する。
【０１０１】
特徴点ペアを生成した後、パラメータ計算部１５１は、図１５に示すように、生成した特徴点ペアを利用して変換行列を計算する。なお、ｉ番目に生成された特徴点ペアに対応する変換行列をＨｉ（ｉ＝１，２，…）と表記する。つまり、パラメータ計算部１５１は、変換行列Ｈｉの変換パラメータｈ１１、ｈ１２、…、ｈ２３を計算する。計算された変換行列Ｈｉは、候補抽出部１５２により利用される。
【０１０２】
候補抽出部１５２は、推定変換行列Ｒの変換パラメータｒ１１、ｒ１２、…、ｒ２３と、変換行列Ｈｉの変換パラメータｈ１１、ｈ１２、…、ｈ２３との差｜ｒｋ−ｈｋ｜（但し、ｋ＝１１，１２，…，２３）をそれぞれ計算する。
【０１０３】
また、候補抽出部１５２は、計算した差｜ｒｋ−ｈｋ｜が予め設定された閾値Ｔｈｋより小さいか否かを判定する。計算した差｜ｒｋ−ｈｋ｜が閾値Ｔｈｋより小さい場合、候補抽出部１５２は、変換行列Ｈｉを候補として投票処理部１５３に入力する。この場合、変換行列Ｈｉは投票処理部１５３による投票処理に利用される。一方、計算した差｜ｒｋ−ｈｋ｜が閾値Ｔｈｋより小さくない場合、候補抽出部１５２は、変換行列Ｈｉを候補外とし、投票処理部１５３に入力しない。この場合、変換行列Ｈｉは投票処理部１５３による投票処理に利用されない。
【０１０４】
変換行列Ｈｉが投票処理部１５３に入力された場合、投票処理部１５３は、画像Ｐ１の特徴点から１つずつ特徴点を選択し、選択した特徴点の座標を変換行列Ｈｉにより変換する。このとき、投票処理部１５３により選択される特徴点は、前段処理で利用されたＸ個の特徴点に制限されず、画像Ｐ１から抽出された特徴点すべて、又はＸ個以上の特徴点が利用される。このとき、投票処理部１５３は、カウンタテーブル１０１ｄを参照し、投票数が小さい順に特徴点を選択する。また、投票処理部１５３は、変換後の座標と画像Ｐ２の特徴点とが許容範囲内にあるか否かを判定する。
【０１０５】
図１６の例では、画像Ｐ１の特徴点ｑ１５に対応する変換後の座標ａと、画像Ｐ２の特徴点ｑ２７とが許容範囲内に収まっている。画像Ｐ１の特徴点ｑ１７についても同様である。一方、画像Ｐ１の特徴点ｑ１６に対応する変換後の座標ｂを基準とする許容範囲内には画像Ｐ２の特徴点が存在しない。この場合、特徴点ｑ１５、ｑ１７はインライヤであると判定され、特徴点ｑ１６はアウトライヤであると判定される。
【０１０６】
インライヤと判定した場合、投票処理部１５３は、変換行列Ｈｉに対する投票数を増加させる。さらに、投票処理部１５３は、変換行列Ｈｉの計算に利用した特徴点ペアに含まれる画像Ｐ１の特徴点についてカウンタテーブル１０１ｄのカウント値を増加させ、カウンタテーブル１０１ｄを更新する。
【０１０７】
また、投票処理部１５３は、現時点でアウトライヤと判定された特徴点の数をカウントする。現時点の最大投票数をＮｍａｘとし、推定変換行列Ｒの計算に利用した画像Ｐ１の特徴点数をｄとした場合に、投票処理部１５３は、アウトライヤと判定された特徴点の数が（ｎ−ｄ−Ｎｍａｘ）より大きいか否かを判定する。アウトライヤと判定された特徴点の数が（ｎ−ｄ−Ｎｍａｘ）より大きい場合、投票処理部１５３は、変換行列Ｈｉに対する投票処理の中止をパラメータ計算部１５１に通知する。
【０１０８】
また、画像Ｐ１の特徴点をすべて選択し終えた場合、投票処理部１５３は、変換行列Ｈｉに対する投票処理の完了をパラメータ計算部１５１に通知する。完了又は中止の通知を受けたパラメータ計算部１５１は、他の特徴点ペアを生成する。そして、再び候補抽出部１５２、投票処理部１５３による処理が実行される。図１７に示すように、特徴点ペアの抽出、変換行列の比較、及び投票処理が繰り返し実行される。例えば、予め設定された繰り返し回数（例えば、上記の式（１）で与えられるＴ）だけ処理が実行される。
【０１０９】
繰り返し処理が完了すると、図１７に示すような投票数テーブル１０１ｃが得られる。図１７の例では、変換パラメータに対応する変換行列の情報を併せて記載している。例えば、投票処理部１５３は、投票数テーブル１０１ｃのレコードを投票数が多い順にソートし、最上位に位置するレコードに対応する変換行列を抽出する。図１７の例では、変換行列Ｈ９が最大投票数に対応する。そして、投票処理部１５３は、抽出した変換行列（図１７の例ではＨ９）を画像Ｐ１の変換に利用する変換行列Ｈに設定する。変換行列Ｈの設定が完了すると、後段処理は終了する。
【０１１０】
（変形例：前段処理で特徴点間の距離を考慮する方法）
ここで、特徴点間の距離を考慮して前段処理に利用する特徴点ペアを抽出する方法（変形例）について、さらに説明する。
【０１１１】
前処理の中で特徴量が大きい順にＸ個の特徴点を抽出する方法については既に説明した。ここでは、特徴量の大きさだけでなく、特徴点間の距離が離れているものを優先的に抽出する方法について説明する。
【０１１２】
例えば、前段処理部１０４は、特徴量が大きい順にＹ個（Ｙ＞Ｘ）の特徴点を抽出し、抽出した特徴点の中から、他の特徴点との間の最短距離が長いものを順に選択してＸ個の特徴点を抽出する。他の例として、注目する画素と周囲の画素との間の距離が大きいほど値が大きくなる重み値を用いて注目する画素の特徴量に重み付けした上で、重み付き特徴量が大きい順にＸ個の特徴点を抽出する方法も考えられる。さらに他の例として、画像を複数の分割領域に分け、分割領域毎に特徴量が大きい順にＺ個（但し、Ｘ＝分割領域数×Ｚ）の特徴点を選ぶ方法も考えられる。
【０１１３】
上記の方法を適用すれば、画像の全体に広く分散している特徴点が優先的に抽出されるため、特徴量の大きな特徴点が局所的に集まっている画像を対象とする場合でも量子誤差を少なくする効果が期待できる。さらに、特徴量の大きな特徴点を含む被写体が動体である場合に、その動体に画面全体が引きずられてしまうことを防止する効果が期待できる。
【０１１４】
以上、情報処理装置１００の機能について説明した。
［２−４．処理の流れ］
次に、図１８〜図２３を参照しながら、情報処理装置１００が実行する処理の流れについて説明する。
【０１１５】
（全体的な処理の流れ）
まず、図１８を参照しながら、処理の全体的な流れについて説明する。なお、図１８は、第２実施形態に係る情報処理装置が実行する処理の全体的な流れを示したフロー図である。
【０１１６】
図１８に示すように、情報処理装置１００は、画像Ｐ１、Ｐ２を取得する（Ｓ１０１）。例えば、情報処理装置１００は、撮像部１０２の機能により、被写体の画像を連続的に撮像して画像Ｐ１、Ｐ２を取得する。但し、情報処理装置１００は、ネットワーク９３２や接続ポート９２４に接続された外部の記憶装置から画像Ｐ１、Ｐ２を取得してもよい。また、情報処理装置１００は、ドライブ９２２を介してリムーバブル記録媒体９２８に記録された画像Ｐ１、Ｐ２を取得してもよい。
【０１１７】
次いで、情報処理装置１００は、特徴点抽出部１０３の機能により、画像Ｐ１、Ｐ２から特徴点（例えば、１００個ずつ）を抽出する（Ｓ１０２）。次いで、情報処理装置１００は、前段処理部１０４の機能により前段処理を実行する（Ｓ１０３）。Ｓ１０３の処理では、推定変換行列が計算される。
【０１１８】
次いで、情報処理装置１００は、後段処理部１０５の機能により後段処理を実行する（Ｓ１０４）。Ｓ１０４の処理では、画像Ｐ１の変換に利用する変換行列が決定される。次いで、情報処理装置１００は、画像処理部１０６の機能により、Ｓ１０４の処理で決定された変換行列を用いて画像処理を実行し（Ｓ１０５）、画像処理後の画像を出力する（Ｓ１０６）。Ｓ１０６の処理が完了すると、図１８に示した一連の処理は終了する。
【０１１９】
（前段処理の流れ）
次に、図１９及び図２０を参照しながら、前段処理の流れについて、さらに説明する。なお、図１９は、第２実施形態に係る情報処理装置が実行する前段処理の流れを示した第１のフロー図である。また、図２０は、第２実施形態に係る情報処理装置が実行する前段処理の流れを示した第２のフロー図である。図１９及び図２０に示した処理は、主に前段処理部１０４により実行される。
【０１２０】
図１９に示すように、前段処理部１０４は、パラメータ計算部１４１の機能により、画像Ｐ１の特徴点から特徴量が大きい順にＸ個（例えば、Ｘ＝１０）の特徴点を抽出する（Ｓ１１１）。次いで、前段処理部１０４は、パラメータ計算部１４１の機能により、画像Ｐ２の特徴点から特徴量が大きい順にＸ個の特徴点を抽出する（Ｓ１１２）。
【０１２１】
次いで、前段処理部１０４は、パラメータ計算部１４１の機能により、Ｓ１１１の処理で画像Ｐ１から抽出した特徴点と、Ｓ１１２の処理で画像Ｐ２から抽出した特徴点とを組み合わせたｄ組の特徴点ペアを生成する（Ｓ１１３）。次いで、前段処理部１０４は、Ｓ１１３の処理で生成したｄ組の特徴点ペアを用いて変換行列Ｒｉを計算する（Ｓ１１４）。但し、変換行列Ｒｉは、Ｓ１１３の処理でｉ番目に生成された特徴点ペアを用いて計算された変換行列を表す。
【０１２２】
次いで、前段処理部１０４は、投票処理部１４２の機能により、画像Ｐ１の特徴点のうち、変換行列Ｒｉの計算に利用していない特徴点を１個選択する（Ｓ１１５）。次いで、前段処理部１０４は、Ｓ１１５の処理で選択した特徴点の座標を変換行列Ｒｉで変換する（Ｓ１１６）。Ｓ１１６の処理が完了すると、処理は図２０のＳ１１７へと進む。
【０１２３】
処理がＳ１１７へと進んだ場合、前段処理部１０４は、投票処理部１４２の機能により、Ｓ１１６の処理による変換後の点との距離が閾値ＴｈＤ（例えば、５ピクセル）以下となる特徴点が画像Ｐ２に存在するか否かを判定する（Ｓ１１７）。変換後の点との距離が閾値ＴｈＤ以下となる特徴点が画像Ｐ２に存在する場合、処理はＳ１１８へと進む。一方、Ｓ１１６の処理による変換後の点との距離が閾値ＴｈＤ以下となる特徴点が画像Ｐ２に存在しない場合、処理はＳ１１９へと進む。
【０１２４】
処理がＳ１１８へと進んだ場合、前段処理部１０４は、投票処理部１４２の機能により、変換行列Ｒｉに投票する（Ｓ１１８）。Ｓ１１８の処理が完了すると、処理はＳ１２２へと進む。
【０１２５】
処理がＳ１１９へと進んだ場合、前段処理部１０４は、投票処理部１４２の機能により、現時点における最大投票数Ｎｍａｘに基づいて（Ｘ−ｄ−Ｎｍａｘ）を計算する（Ｓ１１９）。次いで、前段処理部１０４は、投票処理部１４２の機能により、現時点までにアウトライヤと判定した特徴点の数を計算する（Ｓ１２０）。
【０１２６】
次いで、前段処理部１０４は、投票処理部１４２の機能により、Ｓ１２０の処理における計算結果が（Ｘ−ｄ−Ｎｍａｘ）より大きいか否かを判定する（Ｓ１２１）。計算結果が（Ｘ−ｄ−Ｎｍａｘ）より大きい場合、処理は図１９のＳ１１３へと進む。一方、計算結果が（Ｘ−ｄ−Ｎｍａｘ）より大きくない場合、処理はＳ１２２へと進む。
【０１２７】
処理がＳ１２２へと進んだ場合、前段処理部１０４は、Ｓ１１５の処理で（Ｘ−ｄ）個の特徴点をすべて選択したか否かを判定する（Ｓ１２２）。（Ｘ−ｄ）個の特徴点をすべて選択した場合、処理はＳ１２３へと進む。一方、（Ｘ−ｄ）個の特徴点のうち未選択の特徴点がある場合、処理は図１９のＳ１１５へと進む。
【０１２８】
処理がＳ１２３へと進んだ場合、前段処理部１０４は、Ｓ１１１の処理で画像Ｐ１から抽出した特徴点と、Ｓ１１２の処理で画像Ｐ２から抽出した特徴点とを組み合わせて生成可能なすべての特徴点ペアをＳ１１３の処理で生成したか否かを判定する（Ｓ１２３）。すべての特徴点ペアをＳ１１３の処理で生成した場合、処理はＳ１２４へと進む。一方、Ｓ１１３の処理で生成していない特徴点ペアがある場合、処理は図１９のＳ１１３へと進む。
【０１２９】
処理がＳ１２４へと進んだ場合、前段処理部１０４は、投票数が最大の変換行列Ｒｉを推定変換行列Ｒに設定する（Ｓ１２４）。Ｓ１２４の処理が完了すると、図１９及び図２０に示した一連の処理は終了する。なお、上記の説明では、可能なすべての特徴点ペアを生成する方法を示したが、予め設定した回数の処理を繰り返し、その回数分の特徴点ペアが生成されるように処理を変形することも可能である。
【０１３０】
（後段処理の流れ）
次に、図２１〜図２３を参照しながら、後段処理の流れについて、さらに説明する。なお、図２１は、第２実施形態に係る情報処理装置が実行する後段処理の流れを示した第１のフロー図である。また、図２２は、第２実施形態に係る情報処理装置が実行する後段処理の流れを示した第２のフロー図である。また、図２３は、第２実施形態に係る情報処理装置が実行する後段処理の流れを示した第３のフロー図である。図２１〜図２３に示した一連の処理は、主に後段処理部１０５により実行される。
【０１３１】
図２１に示すように、後段処理部１０５は、投票処理部１５３の機能により、画像Ｐ１の特徴点から、推定変換行列Ｒの計算に利用していない特徴点を１個選択する（Ｓ１３１）。次いで、後段処理部１０５は、投票処理部１５３の機能により、Ｓ１３１の処理で選択した特徴点の座標を推定変換行列Ｒで変換する（Ｓ１３２）。
【０１３２】
次いで、後段処理部１０５は、投票処理部１５３の機能により、Ｓ１３２の処理による変換後の点との距離が閾値ＴｈＤ以下であり、推定変換行列Ｒの計算に利用していない画像Ｐ２の特徴点があるか否かを判定する。（Ｓ１３３）。変換後の点との距離が閾値ＴｈＤ以下であり、推定変換行列Ｒの計算に利用していない画像Ｐ２の特徴点がある場合、処理はＳ１３４へと進む。一方、変換後の点との距離が閾値ＴｈＤ以下となる、推定変換行列Ｒの計算に利用していない画像Ｐ２の特徴点がない場合、処理はＳ１３１へと進む。
【０１３３】
処理がＳ１３４へと進んだ場合、後段処理部１０５は、投票処理部１５３の機能により、推定変換行列Ｒに投票する（Ｓ１３４）。次いで、後段処理部１０５は、投票処理部１５３の機能により、Ｓ１３１の処理で（ｎ−ｄ）個の特徴点をすべて選択したか否かを判定する（Ｓ１３５）。（ｎ−ｄ）個の特徴点をすべて選択し終えている場合、処理はＳ１３６へと進む。一方、（ｎ−ｄ）個の特徴点のうち未選択の特徴点がある場合、処理はＳ１３１へと進む。
【０１３４】
処理がＳ１３６へと進んだ場合、後段処理部１０５は、投票処理部１５３の機能により、Ｓ１３４の処理で投票された推定変換行列Ｒの投票数（総数）をＮｍａｘとする（Ｓ１３６）。次いで、後段処理部１０５は、カウンタテーブル１０１ｄを初期化（カウンタ値を０に設定）する（Ｓ１３７）。
【０１３５】
次いで、後段処理部１０５は、パラメータ計算部１５１の機能により、画像Ｐ１の特徴点と、画像Ｐ２の特徴点とをランダムに抽出し、ｄ組の特徴点ペアを生成する（Ｓ１３８）。次いで、後段処理部１０５は、パラメータ計算部１５１の機能により、Ｓ１３８の処理で生成したｄ組の特徴点ペアを用いて変換行列Ｈｉを計算する（Ｓ１３９）。但し、変換行列Ｈｉは、Ｓ１３８の処理でｉ番目に生成された特徴点ペアを用いて計算された変換行列を表す。Ｓ１３９の処理が完了すると、処理は図２２のＳ１４０へと進む。
【０１３６】
処理がＳ１４０へと進んだ場合、後段処理部１０５は、候補抽出部１５２の機能により、変換行列Ｈｉと推定変換行列Ｒとの差が許容範囲内であるか否かを判定する（Ｓ１４０）。変換行列Ｈｉと推定変換行列Ｒとの差が許容範囲内である場合、処理はＳ１４１へと進む。一方、変換行列Ｈｉと推定変換行列Ｒとの差が許容範囲内でない場合、処理は図２１のＳ１３８へと進む。
【０１３７】
処理がＳ１４１へと進んだ場合、後段処理部１０５は、投票処理部１５３の機能により、画像Ｐ１の特徴点から、変換行列Ｈｉの計算に利用していない特徴点を選択する（Ｓ１４１）。このとき、カウンタテーブル１０１ｄのカウンタ値が小さい順に特徴点が選択される。次いで、後段処理部１０５は、投票処理部１５３の機能により、Ｓ１４１の処理で選択した特徴点の座標を変換行列Ｈｉで変換する（Ｓ１４２）。
【０１３８】
次いで、後段処理部１０５は、投票処理部１５３の機能により、Ｓ１４２の処理による変換後の点との距離が閾値ＴｈＤ以下となる、変換行列Ｈｉの計算に利用していない画像Ｐ２の特徴点があるか否かを判定する（Ｓ１４３）。変換後の点との距離が閾値ＴｈＤ以下となる、変換行列Ｈｉの計算に利用していない画像Ｐ２の特徴点がある場合、処理はＳ１４４へと進む。一方、変換後の点との距離が閾値ＴｈＤ以下となる、変換行列Ｈｉの計算に利用していない画像Ｐ２の特徴点がない場合、処理はＳ１４６へと進む。
【０１３９】
処理がＳ１４４へと進んだ場合、後段処理部１０５は、投票処理部１５３の機能により、変換行列Ｈｉに投票する（Ｓ１４４）。次いで、後段処理部１０５は、投票処理部１５３の機能により、Ｓ１４１の処理で選択した特徴点のカウンタ値を増加させる（Ｓ１４５）。Ｓ１４５の処理が完了すると、処理は図２３のＳ１４９へと進む。
【０１４０】
Ｓ１４３の処理における判定の結果、Ｓ１４６へと処理が進んだ場合、後段処理部１０５は、投票処理部１５３の機能により、（ｎ−ｄ−Ｎｍａｘ）を計算する（Ｓ１４６）。次いで、後段処理部１０５は、投票処理部１５３の機能により、現時点までにアウトライヤと判定した特徴点の数を計算する（Ｓ１４７）。
【０１４１】
次いで、後段処理部１０５は、投票処理部１５３の機能により、Ｓ１４７の処理における計算結果が（ｎ−ｄ−Ｎｍａｘ）より大きいか否かを判定する（Ｓ１４８）。計算結果が（ｎ−ｄ−Ｎｍａｘ）より大きい場合、処理は図２１のＳ１３８へと進む。一方、計算結果が（ｎ−ｄ−Ｎｍａｘ）より大きくない場合、処理は図２３のＳ１４９へと進む。
【０１４２】
処理がＳ１４９へと進んだ場合、後段処理部１０５は、Ｓ１４１の処理で（Ｘ−ｄ）個の特徴点をすべて選択したか否かを判定する（Ｓ１４９）。（Ｘ−ｄ）個の特徴点をすべて選択し終えた場合、処理はＳ１５０へと進む。一方、（Ｘ−ｄ）個の特徴点のうち未選択の特徴点がある場合、処理は図２２のＳ１４１へと進む。
【０１４３】
処理がＳ１５０へと進んだ場合、後段処理部１０５は、変換行列Ｈｉの投票数が最大投票数Ｎｍａｘを超えたか否かを判定する（Ｓ１５０）。変換行列Ｈｉの投票数が最大投票数Ｎｍａｘを超えた場合、処理はＳ１５１へと進む。一方、変換行列Ｈｉの投票数が最大投票数Ｎｍａｘを超えない場合、処理はＳ１５２へと進む。
【０１４４】
処理がＳ１５１へと進んだ場合、後段処理部１０５は、変換行列Ｈｉの投票数で最大投票数Ｎｍａｘを更新する（Ｓ１５１）。Ｓ１５１の処理が完了すると、処理はＳ１５２へと進む。処理がＳ１５２へと進んだ場合、後段処理部１０５は、カウンタテーブル１０１ｄを投票数順にソートする（Ｓ１５２）。
【０１４５】
次いで、後段処理部１０５は、Ｓ１３８以降の処理をＴ回実行したか否かを判定する（Ｓ１５３）。但し、Ｔは、上記の式（１）で与えられる。処理をＴ回実行し終えた場合、処理はＳ１５４へと進む。一方、処理をＴ回実行し終えていない場合、処理は図２１のＳ１３８へと進む。処理がＳ１５４へと進んだ場合、後段処理部１０５は、投票数が最大の変換行列Ｈｉを画像処理に利用する変換行列Ｈに決定する（Ｓ１５４）。Ｓ１５４の処理が完了すると、図２１〜図２３に示した一連の処理は終了する。
【０１４６】
以上、情報処理装置１００が実行する処理の流れについて説明した。上記のように、後段処理にて変換行列Ｈｉと推定変換行列Ｒとの差を評価し、差が許容範囲外である変換行列Ｈｉに対する投票処理を回避することで処理負荷が低減される。さらに、カウント値が小さい特徴点から順に処理が実行されることで、最大投票数Ｎｍａｘを更新する見込みのない変換行列Ｈｉに対する投票処理が早期に回避されることで処理負荷が低減される。その結果、高速に変換行列Ｈを決定することが可能になる。
【０１４７】
以上、第２実施形態について説明した。
＜３．第３実施形態＞
次に、第３実施形態について説明する。
【０１４８】
上記の第２実施形態は、前段処理で推定変換行列Ｒを計算し、後段処理で推定変換行列Ｒと特徴点ペア毎に計算した変換行列Ｈｉとの差に基づいて無駄な投票処理を回避する方法であった。一方、第３実施形態は、図２４に示すように、推定変換行列Ｒを利用して画像Ｐ１の特徴点を変換し、変換後の点を基準とする許容範囲（以下、インライヤ範囲）に収まる画像Ｐ２の特徴点を用いて特徴点ペアを生成する方法を提案する。なお、図２４は、第３実施形態に係る後段処理の概要を示した図である。
【０１４９】
図２４の例では、画像Ｐ１の特徴点ｑ１１、ｑ１２、ｑ１３が推定変換行列Ｒで変換され、それぞれ変換後の点ａ、ｂ、ｃの座標が得られている。この場合、点ａを基準とするインライヤ範囲Ｄａに含まれる画像Ｐ２の特徴点それぞれと、画像Ｐ１の特徴点ｑ１１とのペアが特徴点ペアの候補とされる。また、点ｂを基準とするインライヤ範囲Ｄｂに含まれる画像Ｐ２の特徴点それぞれと、画像Ｐ１の特徴点ｑ１２とのペアが特徴点ペアの候補とされる。さらに、点ｃを基準とするインライヤ範囲Ｄｃに含まれる画像Ｐ２の特徴点それぞれと、画像Ｐ１の特徴点ｑ１３とのペアが特徴点ペアの候補とされる。
【０１５０】
上記のようにして抽出された特徴点ペアの候補から、投票処理の対象とする特徴点ペアが順次選択されて投票処理が実行される。つまり、候補が絞り込まれた上で、その候補の中から特徴点ペアが選択される。そのため、投票処理の実行回数が削減され、後段処理の負荷が低減される。以下、上記のような後段処理を実行可能な情報処理装置２００について説明する。情報処理装置２００は、第３実施形態に係る情報処理装置の一例である。また、上記の第２実施形態に係る情報処理装置１００と実質的に同じ要素については重複説明を避けるため、同一の符号を付して詳細な説明を省略する場合がある。
【０１５１】
［３−１．情報処理装置の機能］
図２５を参照しながら、情報処理装置２００の機能について説明する。図２５は、第３実施形態に係る情報処理装置の機能について説明するためのブロック図である。なお、以下の説明において、適宜、図２６〜図３０を参照する。
【０１５２】
図２５に示すように、情報処理装置２００は、撮像部１０２、特徴点抽出部１０３、前段処理部１０４、画像処理部１０６、記憶部２０１、及び後段処理部２０５を有する。
なお、記憶部２０１の機能は、上述したＲＡＭ９０６や記憶部９２０などを用いて実現できる。特徴点抽出部１０３、前段処理部１０４、後段処理部２０５、及び画像処理部１０６の機能は、上述したＣＰＵ９０２などを用いて実現できる。
【０１５３】
（記憶部２０１）
記憶部２０１には、特徴点情報１０１ａ、モデル情報１０１ｂ、投票数テーブル１０１ｃ、許容範囲情報２０１ａ、及びペアマップリスト２０１ｂが格納される。なお、記憶部２０１には、カウンタテーブル１０１ｄが格納されてもよい。許容範囲情報２０１ａは、特徴量ペアの候補を抽出する際に利用されるインライヤ範囲を決めるための情報である。また、ペアマップリスト２０１ｂは、特徴点ペアの候補が記載されるリストである。
【０１５４】
ここで、図２６を参照しながら、許容範囲情報２０１ａについて、さらに説明する。図２６は、第３実施形態に係る許容範囲情報の一例を示した図である。
図２６に示すように、許容範囲情報２０１ａは、変換パラメータの種類と、変換パラメータの許容範囲とを含む。図２６の例は、上記の式（２）で与えられるアフィン変換の変換パラメータｗ１１、ｗ１２、…、ｗ２３に関するものである。例えば、変換パラメータｗ１１の許容範囲は、［ｗ１１−ｔ１１，ｗ１１＋ｔ１１］（つまり、ｗ１１−ｔ１１≦ｗ１１の許容範囲≦ｗ１１＋ｔ１１）に設定されている。同様に、変換パラメータｗ１２、ｗ１３、…、ｗ２３の許容範囲もそれぞれ設定されている。但し、ｔ１１、ｔ１２、…、ｔ２３は、許容範囲の幅を決める予め設定された設定値である。
【０１５５】
例えば、画像Ｐ１の特徴点ｑ１１を推定変換行列Ｒで変換する場合、推定変換行列Ｒの変換パラメータｒ１１、ｒ１２、…、ｒ２３を上記の幅で動かすと、変換後の点がとる領域（インライヤ範囲）が決まる。図２４の例では、推定変換行列Ｒの変換パラメータｗ１１、ｗ１２、…、ｗ２３を上記の幅で動かすことにより、特徴点ｑ１１に対応するインライヤ範囲Ｄａが決まる。なお、変換後の点を基準に予め設定された半径の円領域や矩形領域をインライヤ範囲とする変形も可能であり、この場合には許容範囲情報２０１ａとして半径や辺の長さを示す情報が予め設定される。
【０１５６】
次に、図２７を参照しながら、ペアマップリスト２０１ｂについて、さらに説明する。図２７は、第３実施形態に係るペアマップリストの一例を示した図である。
図２７に示すように、ペアマップリスト２０１ｂは、候補となる特徴点ペアを特定する情報と、その特徴点ペアに含まれる画像Ｐ１、Ｐ２の特徴点とを記載したリストである。図２７の例では、候補となる特徴点ペアＬ１、Ｌ２、…、Ｌ８が示されている。例えば、特徴点ペアＬ１は、画像Ｐ１の特徴点ｑ１１と、画像Ｐ２の特徴点ｑ２１とを含む。このことは、特徴点ｑ２１が、特徴点ｑ１１を推定変換行列Ｒで変換した点を基準とするインライヤ範囲に含まれる特徴点であることを意味する。他の特徴点ペアＬ２、Ｌ３、…、Ｌ８についても同様である。
【０１５７】
（撮像部１０２、特徴点抽出部１０３、前段処理部１０４、画像処理部１０６）
再び図２５を参照する。撮像部１０２、特徴点抽出部１０３、前段処理部１０４、画像処理部１０６は、第２実施形態と実質的に同じである。前段処理部１０４により計算された推定変換行列Ｒの情報は、記憶部２０１に格納されると共に、後段処理部２０５に入力される。また、後段処理部２０５により決定された変換行列の情報は、画像処理部１０６に入力される。
【０１５８】
（後段処理部２０５）
後段処理部２０５は、記憶部２０１に格納された特徴点情報１０１ａに含まれる特徴点のうち、推定変換行列の計算に利用した特徴点の数よりも多くの特徴点を利用して画像Ｐ１、Ｐ２の位置合わせに用いる変換行列を計算する。このとき、後段処理部２０５は、推定変換行列に基づいて、変換行列の計算に用いる特徴点ペアを絞り込む。後段処理を実行するために、後段処理部２０５は、図２５に示すように、候補抽出部２５１、パラメータ計算部２５２、及び投票処理部２５３を含む。
【０１５９】
候補抽出部２５１は、記憶部２０１に格納された特徴点情報１０１ａを参照し、画像Ｐ１から抽出された特徴点を１つ選択し、選択した特徴点の座標を推定変換行列Ｒにより変換する。また、候補抽出部２５１は、許容範囲情報２０１ａに基づいて、変換後の座標を基準とするインライヤ範囲を計算する。さらに、候補抽出部２５１は、インライヤ範囲に含まれる画像Ｐ２の特徴点を抽出する。
【０１６０】
そして、候補抽出部２５１は、選択した画像Ｐ１の特徴点と、抽出した画像Ｐ２の特徴点のそれぞれとを組み合わせて特徴点ペアの候補を生成する。また、候補抽出部２５１は、生成した特徴点ペアの候補の情報をペアマップリスト２０１ｂに記録する。また、候補抽出部２５１は、画像Ｐ１から抽出された特徴点を１つ選択し、選択した特徴点に対応する特徴点ペアの候補を生成する。これらの処理を繰り返し実行し、候補抽出部２５１は、ペアマップリスト２０１ｂを生成する。
【０１６１】
パラメータ計算部２５２は、ペアマップリスト２０１ｂに記録された特徴点ペアの候補からｄ組の特徴点ペアを選択し、変換モデルに含まれる変換行列を計算する。また、パラメータ計算部２５２は、選択した特徴点ペアの情報と、計算した変換行列の変換パラメータとを投票数テーブル１０１ｃに記録する。投票処理部２５３は、画像Ｐ１から抽出された特徴点のうち、変換行列の計算に利用されていない特徴点を順次選択し、選択した特徴点がインライヤであるか否かを判定する。パラメータ計算部２５２により計算された変換行列は投票処理部２５３に入力される。
【０１６２】
例えば、投票処理部２５３は、入力された変換行列を用いて、選択した画像Ｐ１の特徴点を変換し、変換後の点を基準とする許容範囲（上記のインライヤ範囲と異なる範囲でもよい。）内に画像Ｐ２の特徴点が存在するか否かを判定する。この許容範囲内に画像Ｐ２の特徴点が存在する場合、投票処理部２５３は、選択した画像Ｐ１の特徴点がインライヤであると判定する。
【０１６３】
投票処理部２５３は、インライヤと判定する度に、入力された変換行列の変換パラメータに投票する。つまり、投票処理部２５３は、インライヤと判定した場合に、入力された変換行列の変換パラメータに対応する投票数テーブル１０１ｃの投票数を設定した数（例えば、１）だけ増加させる。すべての特徴点について上記の判定が終了した場合、投票処理部２５３は、入力された変換行列に関する投票処理の終了をパラメータ計算部２５２に通知する。この通知を受けたパラメータ計算部２５２は、未選択の特徴点ペアを選択し、変換モデルに含まれる変換行列を計算する。
【０１６４】
パラメータ計算部２５２は、選択した特徴点ペアの情報と、計算した変換行列の変換パラメータとを投票数テーブル１０１ｃに記録する。また、パラメータ計算部２５２により計算された変換行列は、投票処理部２５３に入力される。投票処理部２５３は、入力された変換行列の計算に利用されていない特徴点を順次選択し、選択した特徴点がインライヤであるか否かを判定する。そして、投票処理部２５３は、インライヤと判定する度に、入力された変換行列の変換パラメータに投票する。
【０１６５】
上記と同様に、パラメータ計算部２５２は、ペアマップリスト２０１ｂから順次特徴点ペアを選択して変換行列を計算する。また、投票処理部２５３は、入力された変換行列に対して投票処理を実行する。これらの処理が予め設定された回数（例えば、上記の式（１）で与えられるＴ）実行された場合、又はペアマップリスト２０１ｂの全特徴点ペアについて処理が実行された場合、後段処理部２０５は、投票数が最大の変換行列を抽出する。
【０１６６】
（後段処理：変換行列の決定）
ここで、図２８〜図３０を参照しながら、後段処理について、さらに説明する。なお、図２８は、第３実施形態に係るペアマップリストの生成方法について説明するための第１の図である。また、図２９は、第３実施形態に係るペアマップリストの生成方法について説明するための第２の図である。また、図３０は、第３実施形態に係る後段処理（変換行列の決定）について説明するための図である。
【０１６７】
いま、画像Ｐ１の特徴点ｑ１１、ｑ１２、…、ｑ１６を含む特徴点ペアのペアマップリスト２０１ｂを生成する方法について考える。以下、推定変換行列Ｒにより特徴点ｑ１１、ｑ１２、…、ｑ１６を変換した点をそれぞれＱ１１、Ｑ１２、…、Ｑ１６と表記する。
【０１６８】
図２８の例では、点Ｑ１１のインライヤ範囲に画像Ｐ２の特徴点ｑ２１が含まれる。そのため、特徴点ペアの候補として、画像Ｐ１の特徴点ｑ１１と、画像Ｐ２の特徴点ｑ２１とのペアがペアマップリスト２０１ｂに記録される。同様に、点Ｑ１２のインライヤ範囲に画像Ｐ２の特徴点ｑ２２が含まれるため、特徴点ペアの候補として、画像Ｐ１の特徴点ｑ１２と、画像Ｐ２の特徴点ｑ２２とのペアがペアマップリスト２０１ｂに記録される。
【０１６９】
点Ｑ１３のインライヤ範囲には画像Ｐ２の特徴点ｑ２３が含まれる。この特徴点ｑ２３は、点Ｑ１５、Ｑ１６のインライヤ範囲にも含まれる。この場合、特徴点ｑ１３、ｑ２３のペア、特徴点ｑ１５、ｑ２３のペア、及び特徴点ｑ１６、ｑ２３のペアがペアマップリスト２０１ｂに記録される。同様に、画像Ｐ２の特徴点ｑ２６は点Ｑ１５、Ｑ１６のインライヤ範囲に含まれるため、特徴点ｑ１５、ｑ２６のペア、及び特徴点ｑ１６、ｑ２６のペアがペアマップリスト２０１ｂに記録される。
【０１７０】
図２８の例では、画像Ｐ２の特徴点ｑ２４、ｑ２７がいずれのインライヤ範囲にも含まれない。そのため、特徴点ｑ２４、ｑ２７に関するペアはペアマップリスト２０１ｂに記録されない。また、点Ｑ１４のインライヤ範囲には、画像Ｐ２の特徴点がいずれも含まれない。そのため、特徴点ｑ１４に関するペアはペアマップリスト２０１ｂに記録されない。上記の処理を実行することで、図２９に示すような特徴点同士の対応関係が得られる。
【０１７１】
図２９に示すように、画像Ｐ１の特徴点ｑ１１（点Ｑ１１に対応）と画像２の特徴点ｑ２１とはペア（特徴点ペアＬ１）となる。また、画像Ｐ１の特徴点ｑ１２（点Ｑ１２に対応）と画像２の特徴点ｑ２２とはペア（特徴点ペアＬ２）となる。また、画像Ｐ１の特徴点ｑ１３（点Ｑ１３に対応）と画像２の特徴点ｑ２３とはペア（特徴点ペアＬ３）となる。一方、画像Ｐ１の特徴点ｑ１４（点Ｑ１４に対応）はペアとならない。
【０１７２】
また、画像Ｐ１の特徴点ｑ１５（点Ｑ１５に対応）と画像２の特徴点ｑ２３とはペア（特徴点ペアＬ４）となる。さらに、画像Ｐ１の特徴点ｑ１５（点Ｑ１５に対応）は画像２の特徴点ｑ２５ともペア（特徴点ペアＬ５）を成す。また、画像Ｐ１の特徴点ｑ１５（点Ｑ１５に対応）は画像２の特徴点ｑ２６ともペア（特徴点ペアＬ６）を成す。
【０１７３】
また、画像Ｐ１の特徴点ｑ１６（点Ｑ１６に対応）と画像２の特徴点ｑ２３とペア（特徴点ペアＬ７）となる。さらに、画像Ｐ１の特徴点ｑ１６（点Ｑ１６に対応）は画像２の特徴点ｑ２６ともペア（特徴点ペアＬ８）を成す。一方、画像Ｐ２の特徴点ｑ２４、ｑ２７はペアとならない。これら特徴点同士の対応関係をまとめると、図３０に示すようなペアマップリスト２０１ｂが得られる。
【０１７４】
ペアマップリスト２０１ｂが得られると、パラメータ計算部２５２は、図３０に示すように、ペアマップリスト２０１ｂから抽出したｄ組の特徴点ペア（図３０の例ではＬ１，Ｌ２，Ｌ３）を用いて変換行列を計算する。そして、投票処理部２５３は、パラメータ計算部２５２が計算した変換行列を対象に投票処理を実行する。これらの処理が繰り返し実行され、最終的に投票数が最大となる変換行列が、画像処理に利用される変換行列Ｈに決定される。上記のように、特徴点ペアの数が絞り込まれることにより、投票処理の回数が減り、処理負荷が低減される。
【０１７５】
以上、情報処理装置２００の機能について説明した。
［３−２．処理の流れ］
次に、図３１〜図３３を参照しながら、情報処理装置２００が実行する処理の流れについて説明する。なお、情報処理装置２００が実行する処理のうち前段処理は第２実施形態と実質的に同じである。そのため、前段処理の流れについては詳細な説明を省略し、後段処理の流れについて説明する。
【０１７６】
（後段処理の流れ）
図３１及び図３２を参照しながら、後段処理の流れについて説明する。なお、図３１は、第３実施形態に係る情報処理装置が実行する後段処理の流れを示した第１のフロー図である。また、図３２は、第３実施形態に係る情報処理装置が実行する後段処理の流れを示した第２のフロー図である。図３１及び図３２に示した一連の処理は、主に後段処理部２０５により実行される。
【０１７７】
図３１に示すように、後段処理部２０５は、投票処理部２５３の機能により、推定変換行列Ｒについて最大投票数Ｎｍａｘを計算する（Ｓ２０１）。Ｓ２０１の処理は、図２１に示したＳ１３１〜Ｓ１３６の処理に相当する。次いで、後段処理部２０５は、候補抽出部２５１の機能により、ペアマップリスト２０１ｂを生成する（Ｓ２０２）。
【０１７８】
次いで、後段処理部２０５は、パラメータ計算部２５２の機能により、ｄ組の特徴点ペアをペアマップリスト２０１ｂから選択する（Ｓ２０３）。次いで、後段処理部２０５は、パラメータ計算部２５２の機能により、Ｓ２０３の処理で選択したｄ組の特徴点ペアを用いて変換行列Ｈｉを計算する（Ｓ２０４）。但し、変換行列Ｈｉは、Ｓ２０３の処理でｉ番目に生成された特徴点ペアを用いて計算された変換行列を表す。
【０１７９】
次いで、後段処理部２０５は、投票処理部２５３の機能により、画像Ｐ１の特徴点から、変換行列Ｈｉの計算に利用していない特徴点を選択する（Ｓ２０５）。次いで、後段処理部２０５は、投票処理部２５３の機能により、Ｓ２０５の処理で選択した特徴点の座標を変換行列Ｈｉで変換する（Ｓ２０６）。Ｓ２０６の処理が完了すると、処理は図３１のＳ２０７へと進む。
【０１８０】
処理がＳ２０７へ進んだ場合、後段処理部２０５は、投票処理部２５３の機能により、Ｓ２０６の処理による変換後の点との距離が閾値ＴｈＤ以下となる、変換行列Ｈｉの計算に利用していない画像Ｐ２の特徴点があるか否かを判定する（Ｓ２０７）。変換後の点との距離が閾値ＴｈＤ以下となる、変換行列Ｈｉの計算に利用していない画像Ｐ２の特徴点がある場合、処理は、Ｓ２０８へと進む。一方、変換後の点との距離が閾値ＴｈＤ以下となる、変換行列Ｈｉの計算に利用していない画像Ｐ２の特徴点がない場合、処理はＳ２０９へと進む。
【０１８１】
処理がＳ２０８へと進んだ場合、後段処理部２０５は、投票処理部２５３の機能により、変換行列Ｈｉに投票する（Ｓ２０８）。Ｓ２０８の処理が完了すると、処理はＳ２１２へと進む。
【０１８２】
処理がＳ２０９へと進んだ場合、後段処理部２０５は、投票処理部２５３の機能により、（ｎ−ｄ−Ｎｍａｘ）を計算する（Ｓ２０９）。なお、ｎは、画像Ｐ１から抽出された特徴点の数である。次いで、後段処理部２０５は、投票処理部２５３の機能により、現時点までにアウトライヤと判定した特徴点の数を計算する（Ｓ２１０）。
【０１８３】
次いで、後段処理部２０５は、投票処理部２５３の機能により、Ｓ２１０の処理における計算結果が（ｎ−ｄ−Ｎｍａｘ）より大きいか否かを判定する（Ｓ２１１）。計算結果が（ｎ−ｄ−Ｎｍａｘ）より大きい場合、処理は図３１のＳ２０３へと進む。一方、計算結果が（ｎ−ｄ−Ｎｍａｘ）より大きくない場合、処理はＳ２１２へと進む。
【０１８４】
処理がＳ２１２へと進んだ場合、後段処理部２０５は、投票処理部２５３の機能により、Ｓ２０５の処理において（ｎ−ｄ）個の特徴点をすべて選択したか否かを判定する（Ｓ２１２）。（ｎ−ｄ）個の特徴点をすべて選択した場合、処理はＳ２１３へと進む。一方、（ｎ−ｄ）個の特徴点のうち未選択の特徴点がある場合、処理は図３１のＳ２０５へと進む。
【０１８５】
処理がＳ２１３へと進んだ場合、後段処理部２０５は、投票処理部２５３の機能により、変換行列Ｈｉの投票数が最大投票数Ｎｍａｘを超えたか否かを判定する（Ｓ２１３）。変換行列Ｈｉの投票数が最大投票数Ｎｍａｘを超えた場合、処理はＳ２１４へと進む。一方、変換行列Ｈｉの投票数が最大投票数Ｎｍａｘを超えていない場合、処理はＳ２１５へと進む。
【０１８６】
処理がＳ２１４へと進んだ場合、後段処理部２０５は、変換行列Ｈｉの投票数で最大投票数Ｎｍａｘを更新する（Ｓ２１４）。Ｓ２１４の処理が完了すると、処理はＳ２１５へと進む。処理がＳ２１５へと進んだ場合、後段処理部２０５は、Ｓ２０３以降の処理をＴ回（例えば、上記の式（１）で与えられるＴ）実行したか否かを判定する（Ｓ２１５）。処理をＴ回実行し終えた場合、処理はＳ２１６へと進む。一方、処理をＴ回実行し終えていない場合、処理は図３１のＳ２０３へと進む。
【０１８７】
処理がＳ２１６へと進んだ場合、後段処理部２０５は、画像処理に利用する変換行列Ｈとして、投票数が最大の変換行列Ｈｉを出力する（Ｓ２１６）。Ｓ２１６の処理が完了すると、図３１及び図３２に示した一連の処理は終了する。なお、上記の説明ではＳ２０３以降の処理をＴ回実行する例を示したが、ペアマップリスト２０１ｂの特徴点ペアがなくなるまでＳ２０３以降の処理を実行するように変形することも可能である。
【０１８８】
（ペアマップリストの生成に係る処理の流れ）
ここで、図３３を参照しながら、上述した後段処理のうち、ペアマップリスト２０１ｂの生成に関する処理の流れについて説明する。なお、図３３は、第３実施形態に係る情報処理装置が実行する後段処理のうち、ペアマップリストの生成に関する処理の流れを示したフロー図である。図３３に示した一連の処理は、上述したＳ２０２の処理に対応し、主に候補抽出部２５１により実行される。
【０１８９】
図３３に示すように、候補抽出部２５１は、画像Ｐ１の特徴点を１個選択する（Ｓ２２１）。次いで、候補抽出部２５１は、Ｓ２２１の処理で選択した特徴点を推定変換行列Ｒで変換する（Ｓ２２２）。次いで、候補抽出部２５１は、Ｓ２２２の処理による変換後の点のインライヤ範囲に含まれる画像Ｐ２の特徴点をすべて抽出する（Ｓ２２３）。
【０１９０】
次いで、候補抽出部２５１は、Ｓ２２３の処理で抽出した特徴点と、Ｓ２２１の処理で選択した特徴点とのペアをペアマップリスト２０１ｂに記載する（Ｓ２２４）。次いで、候補抽出部２５１は、画像Ｐ１の全特徴点を選択したか否かを判定する（Ｓ２２５）。画像Ｐ１の全特徴点を選択し終えた場合、図３３に示した一連の処理は終了する。一方、画像Ｐ１の特徴点のうち未選択の特徴点がある場合、処理はＳ２２１へと進む。
【０１９１】
以上、情報処理装置２００が実行する処理の流れについて説明した。上記のように、インライヤ範囲に基づく特徴点ペアの絞り込みを行うことで投票処理の実行回数を減らすことが可能になり、画像処理に利用する変換行列Ｈの計算負荷を低減することができる。
【０１９２】
以上、第３実施形態について説明した。
＜４．第２及び第３実施形態の組み合わせ＞
ここで、図３４〜図３６を参照しながら、第２実施形態に係る方法と、第３実施形態に係る方法とを組み合わせる仕組みについて説明する。
【０１９３】
なお、図３４は、第２及び第３実施形態の組み合わせについて説明するための第１の図である。また、図３５は、第２及び第３実施形態の組み合わせについて説明するための第２の図である。また、図３６は、第２及び第３実施形態の組み合わせに係る後段処理の流れを示したフロー図である。
【０１９４】
既に説明したように、第３実施形態に係る方法によれば、ペアマップリスト２０１ｂを利用することで処理負荷が低減される。例えば、点Ｑ１１のインライヤ範囲に含まれる特徴点ｑ２１、ｑ２２がある場合、図３４に示すようなペアマップリスト２０１ｂが得られる。この例のように、インライヤ範囲に含まれる特徴点の数が少ない場合、ペアマップリスト２０１ｂに記載される特徴点ペアの数が少ないため、処理負荷の低減効果が大きい。
【０１９５】
一方、図３５に示すように、インライヤ範囲に含まれる特徴点の数が多い場合（図３５の例では特徴点ｑ２１、ｑ２２、…、ｑ２５がインライヤ範囲に含まれる。）、ペアマップリスト２０１ｂに記載される特徴点ペアの数が多くなる。つまり、特徴点が局所的に密集しているような場合、ペアマップリスト２０１ｂを利用することで得られる処理負荷の低減効果が小さくなる。このような場合、第２実施形態に係る方法を適用する方が、より大きな処理負荷の低減効果が得られる可能性がある。
【０１９６】
そこで、図３４に示すような状況では第３実施形態に係る方法を適用し、図３５に示すような状況では第２実施形態に係る方法を適用して処理負荷の低減効果を向上させる組み合わせ方式を提案する。この組み合わせ方式を適用する場合、処理の流れは図３６のようになる。ここで、図３６に示した処理の実行主体を後段処理部３００と呼ぶことにする。
【０１９７】
図３６に示すように、後段処理部３００は、画像Ｐ１の特徴点を推定変換行列Ｒで変換する（Ｓ３０１）。次いで、後段処理部３００は、Ｓ３０１の処理による変換後の点を基準とするインライヤ範囲に含まれる特徴点の数Ｚを計算する（Ｓ３０２）。
【０１９８】
次いで、後段処理部３００は、Ｓ３０２の処理で計算した数Ｚが、予め設定された閾値ＴｈＺより大きいか否かを判定する（Ｓ３０３）。Ｚ≧ＴｈＺの場合、処理はＳ３０４へと進む。一方、Ｚ＜ＴｈＺの場合、処理はＳ３０５へと進む。
【０１９９】
処理がＳ３０４へと進んだ場合、後段処理部３００は、第２実施形態の後段処理を実行する（Ｓ３０４）。一方、処理がＳ３０５へと進んだ場合、後段処理部３００は、第３実施形態の後段処理を実行する（Ｓ３０５）。Ｓ３０４又はＳ３０５の処理が完了すると、図３６に示した一連の処理は終了する。
【０２００】
上記のようにインライヤ範囲に含まれる特徴点の数に応じて第２実施形態の後段処理と第３実施形態の後段処理とを組み合わせることで、状況に応じた好適な処理が実現され、より大きな処理負荷の低減効果を得ることができる。
【０２０１】
以上、第２及び第３実施形態の組み合わせについて説明した。
＜５．付記＞
以上説明した実施形態に関し、さらに以下の付記を開示する。
【０２０２】
（付記１）  第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、前記第１画像上の点を前記第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部と、
設定された第１閾値より特徴量が大きい前記第１及び第２特徴点の集合を用いて前記変換モデルに含まれるパラメータの推定値を計算し、前記第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、前記推定値を適用した前記変換モデルに対する誤差が設定した範囲内にある前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータ及び当該パラメータの評価値を計算し、前記評価値に基づいて前記パラメータを決定する演算部と
を有する、情報処理装置。
【０２０３】
（付記２）  前記演算部は、
前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合から前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータを計算し、当該パラメータと前記推定値との差が設定した許容値よりも小さい場合に前記誤差が前記設定した範囲内にあると判断する
付記１に記載の情報処理装置。
【０２０４】
（付記３）  前記演算部は、
抽出される前記第１特徴点同士の距離及び抽出される前記第２特徴点同士の距離が第１設定値より大きくなるように抽出した前記第１及び第２特徴点の集合から、前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合を特定する
付記１又は２に記載の情報処理装置。
【０２０５】
（付記４）  前記演算部は、
前記パラメータの評価値を計算する処理において、当該パラメータの計算に用いていない前記第１特徴点を選択し、当該パラメータを適用した前記変換モデルで当該第１特徴点を変換し、変換後の点と当該第２特徴点との距離が第２設定値より小さい場合に当該パラメータに対する第１投票数を増加させ、選択したすべての前記第１特徴点に関する前記第１投票数の累積値を当該パラメータに対する前記評価値とする
付記１〜３のいずれかに記載の情報処理装置。
【０２０６】
（付記５）  前記演算部は、
前記パラメータの評価値を計算する処理において、当該パラメータに対する前記第１投票数を増加させる際に当該パラメータの計算に用いた前記第１特徴点に対する第２投票数を増加させ、前記第１特徴点を選択する場合に前記第２投票数が小さい順に前記第１特徴点を選択する
付記４に記載の情報処理装置。
【０２０７】
（付記６）  前記演算部は、
前記推定値の計算に用いていない前記第１特徴点を選択し、前記推定値を適用した前記変換モデルで当該第１特徴点を変換し、変換後の点と当該第２特徴点との距離が前記第２設定値より小さくなる場合に当該第１特徴点に対する第３投票数を増加させ、選択したすべての前記第１特徴点に関する前記第３投票数の累積値を上限値に設定し、前記第２投票数が前記上限値より大きい場合に当該第２投票数で前記上限値を更新し、
前記パラメータの評価値を計算する処理において、当該パラメータによる前記変換後の点と前記第２特徴点との距離が前記第２設定値より大きくなる前記第１特徴点の数が前記上限値に達した場合に、当該パラメータに対する前記評価値の計算を回避する
付記５に記載の情報処理装置。
【０２０８】
（付記７）  前記演算部は、
前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合から前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に、前記推定値を適用した前記変換モデルで前記第１特徴点を変換し、変換後の点を基準に設定した領域に前記第２特徴点が含まれるか否かを判定し、当該領域に前記第２特徴点が含まれる場合に前記誤差が前記設定した範囲内にあると判断する
付記１〜４のいずれかに記載の情報処理装置。
【０２０９】
（付記８）  第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、前記第１画像上の点を前記第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部から、前記第１特徴点、前記第２特徴点、及び前記変換モデルの情報を取得可能なコンピュータが、
設定された第１閾値より特徴量が大きい前記第１及び第２特徴点の集合を用いて前記変換モデルに含まれるパラメータの推定値を計算し、前記第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、前記推定値を適用した前記変換モデルに対する誤差が設定した範囲内にある前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータ及び当該パラメータの評価値を計算し、前記評価値に基づいて前記パラメータを決定する
パラメータの決定方法。
【０２１０】
（付記９）  第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、前記第１画像上の点を前記第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部から、前記第１特徴点、前記第２特徴点、及び前記変換モデルの情報を取得可能なコンピュータに、
設定された第１閾値より特徴量が大きい前記第１及び第２特徴点の集合を用いて前記変換モデルに含まれるパラメータの推定値を計算し、前記第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、前記推定値を適用した前記変換モデルに対する誤差が設定した範囲内にある前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータ及び当該パラメータの評価値を計算し、前記評価値に基づいて前記パラメータを決定する
処理を実行させる、プログラム。
【０２１１】
（付記１０）  第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、前記第１画像上の点を前記第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部から、前記第１特徴点、前記第２特徴点、及び前記変換モデルの情報を取得可能なコンピュータに、
設定された第１閾値より特徴量が大きい前記第１及び第２特徴点の集合を用いて前記変換モデルに含まれるパラメータの推定値を計算し、前記第１閾値より小さい第２閾値よりも特徴量が大きく、かつ、前記推定値を適用した前記変換モデルに対する誤差が設定した範囲内にある前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータ及び当該パラメータの評価値を計算し、前記評価値に基づいて前記パラメータを決定する
処理を実行させるプログラムが格納された、コンピュータにより読み取り可能な記録媒体。
【０２１２】
（付記１１）  第１画像が有する第１特徴点と、第２画像が有する第２特徴点と、前記第１画像上の点を前記第２画像上の対応する点へと変換する変換モデルとを記憶する記憶部と、
一部の前記第１及び第２特徴点を用いて前記変換モデルに含まれるパラメータの推定値を計算し、全部の前記第１及び第２特徴点を対象に前記第１特徴点と前記第２特徴点との組を順次選択して組毎に前記パラメータを計算し、計算した前記パラメータと前記推定値との差が設定した範囲内となる場合に当該パラメータの評価値を計算し、前記評価値が最大となる前記パラメータを特定する演算部と
を有する、情報処理装置。
【０２１３】
（付記１２）  前記コンピュータが、前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合から前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に前記パラメータを計算し、当該パラメータと前記推定値との差が設定した許容値よりも小さい場合に前記誤差が前記設定した範囲内にあると判断する
付記８に記載のパラメータの決定方法。
【０２１４】
（付記１３）  前記コンピュータが、抽出される前記第１特徴点同士の距離及び抽出される前記第２特徴点同士の距離が第１設定値より大きくなるように抽出した前記第１及び第２特徴点の集合から、前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合を特定する
付記８又は１２に記載のパラメータの決定方法。
【０２１５】
（付記１４）  前記パラメータの評価値を計算する処理において、前記コンピュータが、当該パラメータの計算に用いていない前記第１特徴点を選択し、当該パラメータを適用した前記変換モデルで当該第１特徴点を変換し、変換後の点と当該第２特徴点との距離が第２設定値より小さい場合に当該パラメータに対する第１投票数を増加させ、選択したすべての前記第１特徴点に関する前記第１投票数の累積値を当該パラメータに対する前記評価値とする
付記８、１２、１３のいずれかに記載のパラメータの決定方法。
【０２１６】
（付記１５）  前記パラメータの評価値を計算する処理において、前記コンピュータが、当該パラメータに対する前記第１投票数を増加させる際に当該パラメータの計算に用いた前記第１特徴点に対する第２投票数を増加させ、前記第１特徴点を選択する場合に前記第２投票数が小さい順に前記第１特徴点を選択する
付記１４に記載のパラメータの決定方法。
【０２１７】
（付記１６）  前記コンピュータが、
前記推定値の計算に用いていない前記第１特徴点を選択し、前記推定値を適用した前記変換モデルで当該第１特徴点を変換し、変換後の点と当該第２特徴点との距離が前記第２設定値より小さくなる場合に当該第１特徴点に対する第３投票数を増加させ、選択したすべての前記第１特徴点に関する前記第３投票数の累積値を上限値に設定し、前記第２投票数が前記上限値より大きい場合に当該第２投票数で前記上限値を更新し、
前記パラメータの評価値を計算する処理において、当該パラメータによる前記変換後の点と前記第２特徴点との距離が前記第２設定値より大きくなる前記第１特徴点の数が前記上限値に達した場合に、当該パラメータに対する前記評価値の計算を回避する
付記１５に記載のパラメータの決定方法。
【０２１８】
（付記１７）  前記コンピュータが、前記第２閾値よりも特徴量が大きい前記第１及び第２特徴点の集合から前記第１特徴点と前記第２特徴点との組を選択し、選択した組毎に、前記推定値を適用した前記変換モデルで前記第１特徴点を変換し、変換後の点を基準に設定した領域に前記第２特徴点が含まれるか否かを判定し、当該領域に前記第２特徴点が含まれる場合に前記誤差が前記設定した範囲内にあると判断する
付記８、１２〜１４のいずれかに記載のパラメータの決定方法。
【符号の説明】
【０２１９】
１０  情報処理装置
１１  記憶部
１２  演算部
ｑ１、ｑ１１、ｑ１２、ｑ１３、ｑ１４、ｑ１５、ｑ１６  第１特徴点
ｑ２、ｑ２１、ｑ２２、ｑ２３、ｑ２４、ｑ２５、ｑ２６  第２特徴点
Ａ、Ａ２１、Ａ２２  パラメータ
Ａ１  推定値
Ｃ１１、Ｃ１２、Ｃ２１、Ｃ２２  対象物
Ｐ１  第１画像
Ｐ２  第２画像
ＴＭ  変換モデル
Ｔｈ１  第１閾値
Ｔｈ２  第２閾値
【図１】
2015179426.tif 000005
【図２】
2015179426.tif 000006
【図３】
2015179426.tif 000007
【図４】
2015179426.tif 000008
【図５】
2015179426.tif 000009
【図６】
2015179426.tif 000010
【図７】
2015179426.tif 000011
【図８】
2015179426.tif 000012
【図９】
2015179426.tif 000013
【図１０】
2015179426.tif 000014
【図１１】
2015179426.tif 000015
【図１２】
2015179426.tif 000016
【図１３】
2015179426.tif 000017
【図１４】
2015179426.tif 000018
【図１５】
2015179426.tif 000019
【図１６】
2015179426.tif 000020
【図１７】
2015179426.tif 000021
【図１８】
2015179426.tif 000022
【図１９】
2015179426.tif 000023
【図２０】
2015179426.tif 000024
【図２１】
2015179426.tif 000025
【図２２】
2015179426.tif 000026
【図２３】
2015179426.tif 000027
【図２４】
2015179426.tif 000028
【図２５】
2015179426.tif 000029
【図２６】
2015179426.tif 000030
【図２７】
2015179426.tif 000031
【図２８】
2015179426.tif 000032
【図２９】
2015179426.tif 000033
【図３０】
2015179426.tif 000034
【図３１】
2015179426.tif 000035
【図３２】
2015179426.tif 000036
【図３３】
2015179426.tif 000037
【図３４】
2015179426.tif 000038
【図３５】
2015179426.tif 000039
【図３６】
2015179426.tif 000040