JP6235860B2 - 情報処理装置及びその制御方法、プログラム - Google Patents

Description

本発明は、時間的に連続する画像を処理する情報処理技術に関するものである。

コンピュータの計算性能の向上に伴い、領域分割、位置合わせ等、コンピュータビジョンと呼ばれる分野の画像処理技術の実用性が高まっている。

画像の位置合わせでは、時間的に連続する画像から複数の動きベクトルを算出し、これらの動きベクトルから画像の位置ズレ（画像全体の動き）を表現する動きパラメータを算出する。動きベクトルの算出方法は、ブロックマッチングによる動き探索や、特徴点を検出してその対応を算出し、対応点ペアの座標を動きベクトルとする等の方法がある（特許文献１参照）。

また、動きパラメータは、二次元ベクトルやホモグラフィ行列、回転行列（非特許文献１参照）等を用いて表現できる。しかし、検出した動きベクトルは、全てが正しいとは限らず、誤った動きベクトルが含まれることがあるため、誤りを含むデータからモデルを推定するロバスト推定技術が必要となる。ロバスト推定の代表的なアルゴリズムには、ＲＡＮＳＡＣがある（非特許文献２参照）。ＲＡＮＳＡＣは、計算を繰り返しながら最適なモデルを推定する技術である。しかし、ＲＡＮＳＡＣは、データに誤りの量が多い程、または、推定するパラメータの要素数が多い程、多くの繰り返し（以下、イテレーション）を必要とする。以下、この誤ったデータをアウトライア（ｏｕｔｌｉｅｒ）、正しいデータをインライア（ｉｎｌｉｅｒ）と表現する。

画像の位置合わせ技術は、画像ブレ補正（電子防振）、画像合成、符号化、自由視点生成等、様々に応用できる。例えば、連続する複数のフレームに対し、上記の方法でフレーム間の動きを表現する行列の逆行列をそれぞれ作成する。この複数の逆行列を用いて平滑化し、平滑化した行列を用いて、それぞれの画像を幾何変換することにより、動きブレを補正ができる。行列の平滑化は、行列の移動相乗平均を用いて計算することができる。相乗平均の算出に必要な、行列のべき乗根は、例えば、非特許文献３にある方法を用いて計算できる。

特開２００７−３３４６２５号公報

姿勢推定と回転行列、玉木徹、"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" "Algorithms for the matrix pth root"、 "Dario A. Binia、 Nicholas J. Highamb、and Beatrice Meinia"、NumericalAlgorithms (2005)39: 349-378

アウトライアを含む動きベクトルから、画像全体の動きを表現する行列を動きパラメータとして算出する場合、ＲＡＮＳＡＣ等のロバスト推定が必要になる。ＲＡＮＳＡＣはデータのアウトライア率が高い場合、多くのイテレーションを必要とし処理に時間がかかる。

本発明は上記の課題を解決するためになされたものであり、画像処理に係る処理速度及び処理精度を向上することができる情報処理技術を提供することを目的とする。

上記の目的を達成するための本発明による情報処理装置は以下の構成を備える。即ち、時間的に連続する画像を処理する情報処理装置であって、
処理対象画像を分割した分割領域内の動きベクトルに基づいて前記分割領域の代表ベクトルを決定する決定手段と、
前記分割領域内の動きベクトルから、前記分割領域の代表ベクトルに対応する動きベクトルを抽出する抽出手段と、
前記抽出手段で抽出した動きベクトルを用いて、基準画像からの位置ズレを表現する、前記処理対象画像に関する動きパラメータを算出する算出手段と
を備え、
前記決定手段は、前記分割領域に含まれる動きベクトルから取得した動きベクトルとの差が許容誤差内の、前記取得した動きベクトルと同じ分割領域に含まれる動きベクトルの数に基づいて前記代表ベクトルを決定する。

本発明によれば、画像処理に係る処理速度及び処理精度を向上することができる。

装置構成を説明する図である。 電子防振処理を示すフローチャートである。 変換行列の推定処理の詳細を示すフローチャートである。 画像分割の例を説明する図である。 代表ベクトルの算出処理の詳細を示すフローチャートである。 回転行列の推定処理の詳細を示すフローチャートである。 類似動きベクトルの抽出処理の詳細を示すフローチャートである。 類似動きベクトルの抽出処理の詳細を示すフローチャートである。 代表ベクトルの算出処理の詳細を示すフローチャートである。 オブジェクト単位の領域分割を用いる変換行列の推定処理の詳細を示すフローチャートである。 画像がオブジェクト単位で分割された状態と分割領域の番号の例を示す図である。

以下、本発明の実施の形態について図面を用いて詳細に説明する。

＜実施形態１＞
実施形態１では、画像の位置合わせを行うために、時間的に連続する画像から複数の動きベクトルを算出し、これらの動きベクトルから画像全体の動きを表現する動きパラメータを算出する構成について説明する。本実施形態は、画像全体の動き（例えば、位置ズレ）を表現する動きパラメータとして回転行列（非特許文献１参照）を算出することとし、連続する画像から行列を推定して、画像に対して電子防振処理を行う応用例として説明する。

本実施形態では、ディスプレイ（表示装置）が接続された情報処理装置としてのＰＣ（パーソナルコンピュータ）内で、ＣＰＵ（中央演算処理装置）が撮像画像を解析して特徴点を検出するための各処理を行う。以下、ＰＣの構成と各モジュールの動作について、図１（ａ）を参照して説明する。図１（ａ）は、ＰＣの内部構成を説明する図である。

１０１はバスであり、ＰＣ１００内の各種構成要素を相互に接続し、構成要素間のデータの通信経路を司る。１０２はＲＡＭ（書込可能メモリ）であり、ＣＰＵ１０５のワークエリア等の記憶領域として機能する。１０３はグラフィックプロセッサであり、ディスプレイ１０４に画像を表示する際に必要となる計算処理を行うプロセッサである。グラフィックプロセッサ１０３は、行列演算が可能で、行列に従って、回転等の画像の幾何変換を行うことができる。

１０４はディスプレイであり、ユーザＩ／Ｆ１０６から入力されたコマンドや、それに対するＰＣ１００の応答出力等の情報を表示する表示装置である。１０５はＣＰＵであり、オペレーティングシステム（ＯＳ）やアプリケーションプログラム等のコンピュータプログラムに基づいて他の構成要素と協働し、ＰＣ１００全体の動作を制御する。尚、本実施形態では、ＣＰＵが一つであるとして説明するが、これに限定されず、複数のＣＰＵが存在する構成を採用してもよい。その場合の各処理は、マルチスレッド処理による並列動作が可能である。１０６はユーザＩ／Ｆであり、ユーザからの指示やコマンドの入力を受け付けて、プログラムの起動が行われる。ユーザＩ／Ｆ１０６は、タッチパネル、ポインティングデバイス、キーボード等であるが、特定のデバイスに限定されない。また、ユーザＩ／Ｆ１０６が、タッチパネル、ポインティングデバイスの場合は、ディスプレイ１０４上の任意の座標位置でタッチされたか否かの情報を入力することができる。

１０７は不揮発性の外部ストレージであり、大容量メモリとして機能する。本実施形態では、ハードディスク装置（以下、ＨＤと呼ぶ）により実現されるが、ＳＳＤ（フラッシュメモリを使用したソリッドステートドライブ）等の他の記憶装置を用いてもよい。１０８はネットワークＩ／Ｆであり、外部装置とのデータの送受信を中継する。１０９はカメラ等の外部撮像部であり、被写体を撮像して撮像画像を取得することができる。

本実施形態では、実行されるプラグラム及びデータは、外部ストレージ１０７に記録されており、これらをＲＡＭ１０２へ入力し、ＣＰＵ１０５が実行及び処理する構成をとる。プログラム及びデータは、バス１０１を介して入出力が行われる。画像データは、特に説明しない限り、外部ストレージ１０７から入力され、入力時に、ＰＣ１００内部で処理するための内部画像フォーマットに変換するものとする。画像データの入力は、外部撮像部１０９やネットワークＩ／Ｆ１０８から行うことも可能である。

本実施形態における内部画像フォーマットはＲＧＢ画像とするが、これに限定されず、ＹＵＶ画像、モノクロの輝度画像でもよい。また、後述の動き検出は輝度画像で行うものとし、内部画像フォーマットがＲＧＢ画像またはＹＵＶ画像の場合には、変換して動き検出がなされるものとして説明する。ＵＩ（ユーザインターフェース）画面や処理画像結果は、グラフィックプロセッサ１０３を介して、ディスプレイ１０４上に表示することができる。グラフィックプロセッサ１０３は、入力した画像データの幾何変換を行うことが可能で、変換した画像データをＲＡＭ１０２に記憶したり、ディスプレイ１０４に直接出力したりすることも可能である。処理データは、外部ストレージ１０７に記録したり、ＲＡＭ１０２に記憶したりして、他のプログラムと共有することができる。

尚、本実施形態では、電子防振処理を行う情報処理装置をＰＣにより実現する例を説明するが、これに限られない。本実施形態に係る電子防振処理は、撮像装置、組込システム、タブレット端末、スマートフォン等の情報機器を用いて実施することができる。また、全体、または、部分的にハードウェアが実行する構成を採用してもよい。例えば、図１（ｂ）は、撮像装置２００の構成を表している。１１０は撮像部であり、１１１は動き検出部である。尚、図１（ａ）と同一の構成要素については同一の参照番号を付加し、その説明は省略する。図１（ｂ）では、画像を撮像部１１０から入力し、動き検出部１１１は動きベクトルの検出を行う。このように、本実施形態で説明する処理は、撮像装置でも実行可能である。

連続する画像から画像全体の動きを表現する行列を推定して電子防振処理を実行する方法について、図２を参照して具体的に説明する。図２は、電子防振処理を示すフローチャートである。尚、図２のフローチャートは、ＣＰＵ１０５が、外部ストレージ１０７に記録されているプログラムを読み出し実行することで実現される。また、ＣＰＵ１０５は、処理内容に応じて、図１（ａ）あるいは図１（ｂ）に示される各種構成要素と協働して処理を実行する。

以下、フローチャートの説明に関しては、特に説明しない限り、ステップ番号順に、それぞれのステップが実行されるものとして説明する。また、互いに依存関係のない独立した処理については、記載のステップ順に処理を実行する必要はなく、順序を入れ替えて実行したり、複数ＣＰＵが存在する場合には処理を並列に実行することも可能である。同様に、ステップが存在するサブルーチンの位置も限定はなく、処理結果が同じであれば、異なるサブルーチンで処理を実行する構成もとることができ、サブルーチンの構成にも限定はない。

Ｓ２０１０では、ＣＰＵ１０５あるいは動き検出部１１１が、画像を順に入力して動き検出を実行する。本実施形態では、第ｃ−１番フレーム、第ｃ番フレームの輝度画像が入力され、第ｃ−１番フレーム（基準画像）から第ｃ番フレーム（処理対象画像）の変換（動き）を表す動きベクトルが検出されるものとして説明する。入力画像のフレーム番号は０から、処理対象のフレーム番号は１から開始され、本ステップが実行される毎にｃの値がインクリメントされるものとして説明する。

動き検出は、特徴点を検出し、特徴点の特徴量を画像間でマッチングし、その対応位置関係を動きベクトルとすることによって行われる。しかし、動き検出のアルゴリズムは、これに限定されず、例えば、輝度画像を縦３２×横３２画素単位のブロック（分割領域）に分割し、ブロック単位（分割領域単位）で、ブロックマッチングよる動き探索によって行う構成を採用してもよい。本実施形態では、一つの動きベクトルは、始点と終点の座標から構成される有向線分であり、一つの動きベクトルを

と表現する。

但し、Ａ、Ｂは動きベクトルの始点と終点を表す。また、動きベクトルの純粋なベクトル成分を

と表現する。

複数の動きベクトルの集合をＸとし、Ｘの個別の動きベクトルを識別するインデックス番号をｉとすると、各動きベクトルは、

と表現される。このとき、Ｘは、

と表現される。以降、特別な記述がない場合、添え字が共通の

は、同一の動きベクトル、及び、その要素を表すものとして説明する。本実施形態では、各数値は浮動小数点として扱うものとして説明するが、固定小数点として計算する方法を採用してもよい。また、画像の画素を参照する場合、特別な記述がなければ小数部を切り捨てた数値を座標値として画素を参照するものとする。本実施形態では、集合は配列として実装されるものとし、集合の要素を

あるいは、

と表現して、集合の要素である動きベクトルやそのベクトル成分に参照できるものとして説明する。

また、集合の要素数は、集合を｜｜で挟む形式で表現する。例えば、集合Ｘの要素数は、｜Ｘ｜となる。尚、集合は配列として実装することに限定されず、例えば、リストとして実装してもよい。

Ｓ２０２０では、ＣＰＵ１０５が、動き検出結果から変換行列を推定する。変換行列の推定方法の詳細は、図３を用いて後述する。本実施形態では、第ｃ−１番フレームから第ｃ番フレームの変化を表す変換行列をＨ_cとする。本実施形態では、Ｈ_cは３×３の行列である回転行列（非特許文献１参照）として説明する。しかし、行列の形式に限定はなく、アフィン変換行列やホモグラフィ行列等の他の行列であってもよい。

Ｓ２０３０では、ＣＰＵ１０５が、防振行列を生成するために必要な、防振フレーム周期の数以上の変換行列が推定できたかを判定する。防振フレーム周期をｐとすると、ｃ≧ｐが真の場合（Ｓ２０３０でＹＥＳ）、Ｓ２０４０へ遷移し、偽の場合（Ｓ２０３０でＮＯ）、Ｓ２０１０へ遷移する。ｐの値は、例えば、１６であるとするが、ｐの値に限定はなく、長周期のブレを抑制する場合にはｐを大きく設定し、短周期のブレのみ抑制する場合はｐを小さく設定する。

Ｓ２０４０では、ＣＰＵ１０５が、推定した複数の変換行列から防振行列を生成する。防振は、高周波のブレを抑制することが目的であり、変換行列を複数フレームに渡って平滑化したものが防振行列となる。本実施形態では、過去のフレームの変換行列と直前の防振行列から計算する。例えば、第ｃ番フレームの防振行列をＳ_cとすると、Ｓ_cは、

として計算される。尚、行列のべき乗根の計算は近似計算でよく、非特許文献２で説明される方法で計算できる。行列のべき乗根は複数存在する場合があるため、一意の行列が定まる制約を設ける。本実施形態では、行列は回転行列であるため、回転量が最も小さい行列を選択することになる。また、行列のべき乗根が計算できない場合、防振行列Ｓ_cは単位行列であるものとして処理を進める。尚、行列の平滑の方法はこれに限定されない。

Ｓ２０５０では、ＣＰＵ１０５が、防振行列を用いて画像を幾何変換する。本実施形態では、第ｃ−ｐ＋１番フレームのＲＧＢ画像を入力し、ＲＧＢそれぞれのチャネル毎に処理がなされる。

このとき、幾何変換後の画像である出力画像の画素位置を（ｘ_out，ｙ_out）、入力画像の画素位置を（ｘ_in，ｙ_in）、出力画像から入力画像への変換行列を

とすると、（ｘ_out，ｙ_out）から（ｘ_in，ｙ_in）を計算するｐｒｏｊ関数は下記のように表せる。

本ステップでは、出力画像の画素を一画素ずつ走査しながら、Ｍ＝Ｓ^-1としたｐｒｏｊ関数を用いて出力画像の走査対象画素に対応する入力画像の対応画素の位置を計算する。この対応画素の画素値を走査対象画素の画素値として、出力画像の全ての画素値を決定する。尚、（ｘ_in，ｙ_in）は小数値を有するため、バイリニアやバイキュービック等の方法を用いて補間し、より精度の高い画素値を計算する方法を採用してもよい。変換された画像は、ＣＰＵ１０５が、ディスプレイ１０４に表示する、あるいは符号化して外部ストレージ１０７に記録する。

Ｓ２０６０では、ＣＰＵ１０５が、全入力画像の処理が終了したか否かを判定する。終了した場合（Ｓ２０６０でＹＥＳ）、処理を終了し、処理が終了していない場合（Ｓ２０６０でＮＯ）、Ｓ２０１０に遷移して、以後、Ｓ２０１０からＳ２０６０の処理をくり返す。本実施形態では、処理の終了条件として全入力画像の処理が終了したか否かを判定しているが、これに限定されない。例えば、ユーザが処理終了を指示するＵＩ操作が行われたか否かを判定して、処理を終了してもよい。

次に、Ｓ２０２０の変換行列の推定処理の詳細について、図３を参照して説明する。

図３は、変換行列の推定処理の詳細を示すフローチャートである。

Ｓ３０１０では、ＣＰＵ１０５が、対象分割領域を走査して、分割領域内毎に分割領域内の動きベクトルの集合を入力する。

以下、分割領域の走査方法について図４を用いて詳細に説明する。図４は画像分割の例を説明する図である。図４（ａ）は、画像の分割方法と分割領域番号を例示する図である。本実施形態では、分割領域を図４（ａ）に示す数値のようにラスター順に従って走査する。つまり、一回目のＳ３０１０が実行される場合には、番号１の分割領域が処理対象となり、以下、２回、３回と実行される毎に分割領域番号２、３の分割領域が処理対象となる。本ステップでは、この対象分割領域内にベクトルの終点（矢印のついた点）が含まれる動きベクトルを入力する。本実施形態では、この分割領域の番号をｄとし、以下、分割領域ｄのように表現して説明する。また、最大分割数をｄ_maxと表現する。本実施形態では、ｄ_max＝２０である。ｄは１から始まり、Ｓ３０１０が実行される毎にｄがインクリメントされることになる。

図４（ｂ）は、動きベクトルの状態を例示する図である。図４（ｂ）のように、動きベクトルは分割領域をまたぐ場合があるため、本実施形態では、動きベクトルｖの終点が含まれる動きベクトルを分割領域の動きベクトルとして扱う。動きベクトルｖの終点Ｂが、分割領域ｄに含まれるか否かを判定する関数をｉｎ（ｄ，Ｂ）とする。分割領域ｄに含まれるベクトルの集合Ｙ_dは、

と表現される。この記法は、集合Ｘの要素を走査して、「｜」以降で表現された条件を満足する要素を抽出し、抽出された要素の部分集合であるＹ_dを生成することを示している。以下、部分集合の生成は、同様の記法を用いて説明する。尚、部分集合として新しい配列やリストを生成せず、各要素に部分集合であるか否かを示すフラグを設け、要素の抽出時にフラグを設定する構成を採用してもよい。この構成では、処理毎に上位集合の要素を走査して走査対象の要素のフラグの参照することによって、部分集合である要素のみを取得できる。

尚、Ｙ_dは、事前に作成しておき、本ステップで入力のみする構成を採用してもよい。また、本実施形態では、図４のように画像を２０分割したものとして説明しているが、分割方法はこれに限定されない。また、本実施形態では、終点が分割領域に含まれる動きベクトルを入力するとして説明しているが、始点が分割領域に含まれる動きベクトルを入力する構成を採用してもよい。また、分割領域の走査順も、ラスター順に限定されない。さらには、動きベクトルｖの終点Ｂが、分割領域の８近傍の分割領域と自身の領域に含まれる否かを判定する関数をｎｅｉｇｈｂｏｕｒ（ｄ，Ｂ）とすると、

という式を用いて、ベクトルの集合Ｙ_dを作成してもよい。例えば、分割領域番号が９の場合、分割領域の８近傍の分割領域と自身の領域とは、図４（ａ）の太線で囲まれた９つの分割領域になる。但し、近傍領域が画面外に存在する場合には、画面内の領域から、ベクトルの集合Ｙ_dが作成されるものとする。

Ｓ３０２０では、ＣＰＵ１０５が、入力した動きベクトルを用いて代表ベクトル（第一の動きパラメータ）を算出する。本実施形態では、代表ベクトルを算出するサブルーチンを実行するものとする。このサブルーチンの動作については、図５を用いて後述する。尚、本実施形態では、ロバスト推定を用いる図５に示すフローチャートを用いて説明するが、Ｍ推定、最小メジアン法等の他の推定手法を用いてもよい。以下、代表ベクトルを

と表現する。

Ｓ３０３０では、ＣＰＵ１０５が、入力した動きベクトルの集合から代表ベクトルに対応する動きベクトル（類似動きベクトル）を抽出する。本実施形態では、ロバスト推定における許容誤差を設定し、代表ベクトルと入力した動きベクトルのベクトル成分の差分の絶対値が許容誤差以内の動きベクトルを、代表ベクトルに対応する類似動きベクトルとして抽出する。許容誤差の値ｅ₂は、後述のＳ３０５０で使われるＲＡＮＳＡＣ処理の許容誤差のｅ_h（本実施形態では、３を設定する）に対して、下記の式で計算されるものとする。

尚、本実施形態では、ｋ＝５とするが、この値に限定されるものではない。このように、Ｓ３０２０における許容誤差の値ｅ₂は、Ｓ３０５０における許容誤差のｅ_hよりも大きい値が設定される。

また、画像の高さをｉｍａｇｅ＿ｈｅｉｇｈｔ、除数をｄｉｖとして、

という計算式を用いて許容誤差のｅ_hを計算してもよい。尚、本実施形態では、ｋ＝５、ｄｉｖ＝３６０として計算するが、これらの値に限定されるものではない。

このとき、第ｃ番フレームの分割領域ｄの抽出された動きベクトルの集合Ｖ_dは、

として抽出できる。尚、本実施形態では、ベクトルの差分の絶対値に対し許容誤差の判定を行ってベクトルを抽出しているが、他の方法でも抽出できる。例えば、ベクトルの差分のそれぞれの成分に対し個別に許容誤差の判定を行ってもよい。具体的には、

として動きベクトルを抽出できる。許容誤差はそれぞれｅ_2x＝５ｅ_h、ｅ_2y＝３ｅ_h等の値をとる。

Ｓ３０４０では、ＣＰＵ１０５が、全分割領域の処理が終了したか否か判定する。処理が終了している場合（Ｓ３０４０でＹＥＳ）、Ｓ３０５０に遷移する。一方、処理が終了していない場合（ステップＳ３０４０でＮＯ）、Ｓ３０１０に遷移し、以後、Ｓ３０１０からＳ３０４０のステップが繰り返される。

Ｓ３０５０では、ＣＰＵ１０５が、全分割領域から抽出した動きベクトルを入力して回転行列（第二の動きパラメータ）を推定する。本実施形態では、許容誤差ｅ_hを３としてＲＡＮＳＡＣを実行するサブルーチンが呼び出すものとする。サブルーチンの動作説明については図６を用いて後述する。

以下、図３のＳ３０２０における分割領域単位で代表ベクトルを算出するサブルーチンの動作について、図５を用いて説明する。図５は、実施形態１の代表ベクトルの算出処理の詳細を示すフローチャートである。

Ｓ５０００では、ＣＰＵ１０５が、イテレーション数をインクリメントする。尚、イテレーション数は、事前に０で初期化されているものとする。

Ｓ５０１０では、ＣＰＵ１０５が、比較対象となるサンプル全体からランダムに動きベクトルを取得する。本サブルーチンの動作におけるサンプル全体とは、少なくとも１つの対象分割領域に含まれる全ての動きベクトルであり、本実施形態では、一つの動きベクトルｖ_rを取得する。

Ｓ５０２０では、ＣＰＵ１０５が、取得した動きベクトルとサンプル全体の動きベクトルの差を算出し、差が許容誤差内のデータ数をインライア数としてカウントする。以後、このインライア数をｃ_inlierとすると

として計算できる。

Ｓ５０３０では、ＣＰＵ１０５が、現在までのイテレーションでインライア数が最大であるか否か判定する。真である場合（Ｓ５０３０でＹＥＳ）、Ｓ５０４０へ遷移し、偽である場合（Ｓ５０３０でＮＯ）、Ｓ５０５０へ遷移する。尚、例外として、一回目のＳ５０３０の実行では、必ず、Ｓ５０４０へ遷移するものとする。

Ｓ５０４０では、ＣＰＵ１０５が、取得した動きベクトルをベストパラメータとして保存する。本実施形態では、ベストパラメータは、

であり、

として、

を更新する。

Ｓ５０５０では、ＣＰＵ１０５が、イテレーション数が上限数に達したか否かを判定する。上限数に達した場合（Ｓ５０５０でＹＥＳ）、Ｓ５０７０へ遷移する。一方、上限数に達していない場合（Ｓ５０５０でＮＯ）、Ｓ５０６０へ遷移する。

尚、本実施形態では、上限を５０回とする。但し、この回数に限定されるものではない。例えば、入力される画像のフレームレートが６０ｆｐｓの場合、図２のフローチャートは１６ｍｓ以内で完了する必要がある。そのため、ＣＰＵ１０５のスペックや数によって、最適な値が決定される。

Ｓ５０６０では、ＣＰＵ１０５が、イテレーション数が十分であるか否かを判定する。イテレーション数が十分である場合（Ｓ５０６０でＹＥＳ）、Ｓ５０７０に遷移し、不十分である場合（Ｓ５０６０でＮＯ）、Ｓ５０００へ遷移する。この判定は、イテレーション数が（式１１）によって算出されるＮ値を超える場合に十分と判定される。

ｐ_sampleは、正しいサンプル（動きベクトル）が最低一つ存在する確率である。本実施形態では、サンプルが９９％の確率で存在すると仮定し、ｐ_sample＝０．９９とする。ｍは、パラメータの算出に必要な動きベクトルの数である。二次元ベクトルを算出する場合は、ｍ＝１である。また、ホモグラフィ行列や回転行列の場合は、ｍ＝４となる。（式１１）は、同じｒ_inlierであれば、ｍが小さい程、小さいＮ値を導出する式である。つまり、図５のフローチャートでは、ｍが小さい程、イテレーション数が少なくなることになる。（式１１）中のｒ_inlierは、下記の式により算出される。

ここで、ｃ_inlierは、Ｓ５０２０で算出したインライア数である。｜Ｖ_d｜は、Ｓ３０３０で抽出した動きベクトルの要素数である。

Ｓ５０７０では、ＣＰＵ１０５が、ベストパラメータとして戻り値を返す。本実施形態では、Ｓ５０７０が実行される時点での

が返され、これが分割領域の代表ベクトルにあたる。

以下、図３のＳ３０５０における回転行列を推定するサブルーチンの動作について、図６を用いて説明する。

図６は、ＲＡＮＳＡＣを用いる回転行列の推定処理の詳細を示すフローチャートである。基本的な動作フローは、図５の処理と同じであるが、図６では、Ｓ６０１１が追加され、Ｓ５０１０とＳ５０２０が、Ｓ６０１０とＳ６０２０に置き換えられている。

Ｓ６０００では、ＣＰＵ１０５が、イテレーション数をインクリメントする。

Ｓ６０１０では、ＣＰＵ１０５が、入力サンプル全体から４つの動きベクトルを取得する。本実施形態において、入力サンプル全体とは、図３のフローチャートで抽出した動きベクトルの全分割領域に対する集合である。つまり、入力サンプル全体Ｚは、

と表現される。

Ｓ６０１１では、ＣＰＵ１０５が、４つの動きベクトルから行列を算出する。このとき、取得した動きベクトルをｖ_j（但し、ｊは１から４）と表現する。算出する行列はＳ２０２０における

である。本ステップでは、方程式を解いて下記を満足する回転行列のそれぞれの要素を算出する。

尚、回転行列の算出は様々な方法があり、例えば、非特許文献１に記載されている方法を利用できるため、ここでは、詳細な説明は省略する。回転行列の算出方法によっては、サンプルの選び方によって行列が算出できない場合がある。行列算出の失敗を判定して、失敗と判定された場合には、処理をＳ５０００へ遷移させ、再度、処理が行われるものとする。

Ｓ６０２０では、ＣＰＵ１０５が、サンプル全体に対し、動きベクトルの始点を、算出した行列で射影した点と終点との距離を算出し、距離が許容誤差内のデータ数をインライア数としてカウントする。この許容誤差は、前述のｅ_hである。回転行列推定におけるインライア数ｃ_Hinlierは、

として計算できる。

以降は、図５と同様に、イテレーションを繰り返すことにより、回転行列を推定することができる。

一般に、アウトライアの比率（以下、アウトライア率）が高い動きベクトルを入力とし、ＲＡＮＳＡＣを用いて回転行列を推定すると、イテレーション数が多くなるという問題がある。また、ロバスト推定技術の一つで比較的処理が軽いとされ、処理時間が短いＭ推定は、アウトライア率が高い場合には十分な推定性能が発揮できない。

そこで、本実施形態では、行列推定の前に分割領域毎に代表ベクトルを算出し、代表ベクトルに対応する類似の動きベクトルを抽出している。これにより、画像全体の動きを表現する回転行列の推定の入力となる動きベクトルのアウトライアを除去し、ＲＡＮＳＡＣのイテレーション数を減少させる、あるいは、Ｍ推定の推定性能を向上させることができる。代表ベクトルを算出する処理は、複雑な行列演算がないため処理量が非常に少ない。そのため、例えば、ＲＡＮＳＡＣに適用する場合、その前処理として類似動きベクトルを抽出する処理のオーバーヘッドを考慮してもトータルの処理時間の大幅な短縮が可能となる。

また、例えば、６０ｆｐｓの画像では、一つのフレームの処理を１６ｍｓ以内に完了する必要がある。そのため、イテレーション数に上限を設ける必要があるが、この場合でも、本実施形態を用いれば、イテレーション数が上限に達しにくく、安定的に行列を推定できる。これにより、行列を用いて画像を防振する場合、行列推定の失敗の確率が減り、より安定的で自然な防振が可能となる。尚、本実施形態では、画像の防振を行うことを例に、代表ベクトルの決定と類似動きベクトルの抽出処理を実施してから、画像全体の動きを表現する行列の算出方する法について説明している。しかし、算出した画像全体の動き情報を利用するアプリケーションはこれに限定されず、画像合成、符号化、自由視点合成等にも応用できる。

本実施形態では、二次元の代表ベクトルを算出してから回転行列を算出する構成を説明している。しかし、領域を代表する二次元ベクトルを算出してから面（処理対象画像）全体の動きを表現するアフィン変換行列、あるいは、領域を代表するアフィン変換行列を算出してから画像全体の動きを表現する回転行列を算出する構成にも適用できる。アフィン変換行列Ｔは、

と表現される。

アフィン変換行列も、複数の動きベクトルから回転行列を算出する方法と同様の方法で計算できる。しかし、回転行列に比べると要素数が少ない（パラメータの自由度が小さい）ため、行列演算の演算量が少なく、また、ＲＡＮＳＡＣに必要なイテレーション回数も少なく済むため、領域を代表する動き情報推定にも十分利用できる。

また、本実施形態では、代表ベクトルを算出する処理にＲＡＮＳＡＣを用いているが、これに限定されず、Ｍ推定、最小メジアン法、最小二乗法、平均、全探索的なロバスト推定を用いてもよい。全探索は、通常のＲＡＮＳＡＣのフローチャートと同様であるが、サンプルをランダムに選択するステップが、一回のイテレーション毎にサンプルが順に取得されるステップとなり、最大でサンプル数だけイテレーションを実行する構成となる。全探索であっても、代表ベクトルを算出する処理は複雑な行列演算がないため、その処理負荷は３×３のィ行列をロバスト推定により算出する場合に比べ大きくない。また、許容誤差内に収まるインライアの比率から処理を打ち切る処理を持てば、ワーストケース以外、サンプル数のイテレーションを繰り返す必要もない。このような全探索的な手法であっても、アウトライアを含んだ入力データからパラメータを推定できるロバスト性を持たせることができる。

以上説明したように、実施形態１によれば、画像全体の動きパラメータをロバスト推定で算出する際に、事前にインライアを抽出することにより、アウトライア率を低減させて、処理時間を短縮することができる。また、動画処理等の既定時間内に処理を完了させるためにイテレーションの上限回数を設定する場合、イテレーションが上限に達する割合が減少し、推定性能を安定することができる。

＜実施形態２＞
実施形態２では、連続する画像から回転行列を推定して電子防振処理を行う構成について説明する。本実施形態では、実施形態１に対し、図３のＳ３０３０での類似動きベクトルを抽出するステップを実行する代わりに、図７に示す類似動きベクトルを抽出する処理がサブルーチンとして実行される。他の処理は、実施形態１に準ずるものとする。

以下、類似動きベクトル抽出の動作について、図７を参照して説明する。図７は類似動きベクトルの抽出処理の詳細を示すフローチャートである。

Ｓ７０００では、ＣＰＵ１０５が、ベストパラメータである領域の代表ベクトルと差が許容誤差

内の領域内の動きベクトル（類似動きベクトル）を抽出する。

の初期値は１とする。

Ｓ７０１０では、抽出した動きベクトルの数をカウントする。この値を

とすると

と表現できる。

Ｓ７０２０は、ＣＰＵ１０５が、抽出したデータ数が領域内の動きベクトルの所定割合以上であるか否かを判定する。ここで、所定割合は、例えば、２５％である。本実施形態では、代表ベクトルとの差が許容誤差内である動きベクトルの数と領域内の全動きベクトル数の比率をインライア率

と表現する。

このとき、

は、

として計算できる。判定結果が真の場合（Ｓ７０２０でＹＥＳ）、Ｓ７０４０へ遷移し、偽の場合（Ｓ７０２０でＮＯ）、Ｓ７０３０へ遷移する。

Ｓ７０３０では、ＣＰＵ１０５が、許容誤差

を所定倍（例えば、１．５倍）に拡大する。その後、Ｓ７０００へ遷移する。

Ｓ７０４０では、ＣＰＵ１０５が、抽出した動きベクトルをサブルーチンの呼び出し元に返す。この動きベクトルの集合はイテレーションが終了時点の

である。

本実施形態において、回転行列を算出するためのＲＡＮＳＡＣに入力される動きベクトルはＳ７０４０で返された動きベクトルの集合である。

以上説明したように、実施形態２によれば、許容誤差の初期値に小さい値を設定し、許容誤差を大きくしながらイテレーションを繰り返して類似動きベクトルを抽出する。つまり、類似動きベクトルを抽出のための許容誤差が適応的に設定されることになる。これにより、許容誤差が小さすぎて、十分な数の動きベクトルが検出できないという問題を回避することができる。また、本実施形態では、許容誤差を大きくしながらイテレーションを繰り返しているが、逆に初期値に大きい値を設定し値を小さくしていく構成を採用してもよい。この場合の初期値は、本実施形態を防振に適用する場合、防振の最大補正量であり、画像高の１０％等の値が用いられる。

さらには、２つを複合した構成を採用してもよい。例えば、許容誤差を増減させながらインライア率が２０％から３０％の範囲に収まる最適な許容誤差を探索していく構成を採用してもよい。尚、本実施形態では、目標とするインライア率を２５％としているが、これに限定されるものではない。例えば、目標とするインライア率は、ターゲットのアプリケーション、処理速度、入力画像の特性、行列を推定するために用いられるロバスト推定アルゴリズムに応じて適切な値が設定される。

＜実施形態３＞
実施形態３では、連続する画像から回転行列を推定して電子防振処理を行う構成について説明する。本実施形態は、実施形態２の類似動きベクトルの抽出処理の変形例である。

本実施形態において、Ｓ２０２０における動き検出は、特徴点検出を用いるとものとする。特徴点検出による動き検出結果から防振処理を行っても、ブロックマッチングによる動き検出結果から防振処理を行っても、動き検出以外に、基本的な処理の違いはない。但し、特徴点検出の場合、特徴点から生成される動きベクトルの数は一定になりにくい。また、動きベクトルの分布も不均一になることがある。

以下、類似動きベクトル抽出の動作について図８を参照して用いて説明する。図８は類似動きベクトルの抽出処理の詳細を示すフローチャートである。図８は、実施形態２の図７のフローチャートの変形例であるので、図７と同一のステップは同一の参照番号を付加して、その詳細については省略する。

Ｓ８０２０は、ＣＰＵ１０５が、抽出した動きベクトル数が抽出目標数以下であるか否かを判定する。目標数は、例えば、１５である。判定結果が真の場合（Ｓ８０２０でＹＥＳ）、Ｓ７０４０へ遷移し、偽の場合（Ｓ８０２０でＮＯ）、Ｓ７０００へ遷移する。

Ｓ８０３０では、ＣＰＵ１０５が、許容誤差を減少する。これは、例えば、許容誤差を所定倍（例えば、０．７５倍）にすることで実現する。その後、Ｓ７０００へ遷移する。尚、許容誤差の初期値は、予め大きな値、例えば、画像高の１０％の値が設定されているものとする。

以上説明したように、実施形態３によれば、許容誤差を小さくしながらイテレーションを繰り返して類似動きベクトルを抽出する。つまり、類似動きベクトルを抽出のための許容誤差が適応的に設定されることになる。これにより、許容誤差が大きすぎて、アウトライア率の高い不要な動きベクトルを多く抽出しすぎる問題を回避することができる。

また、本実施形態では、許容誤差を小さくしながらイテレーションを繰り返しているが、逆に、初期値に小さい値を設定し許容誤差を大きくしていく構成を採用する、あるいは、２つを複合した構成を採用してもよい。例えば、許容誤差を増減させながら、動きベクトルが１５から３０の範囲に収まるように、最適な許容誤差を探索していく構成を採用してもよい。

尚、本実施形態では、動きベクトルの抽出目標数を１５としているが、これに限定されない。抽出目標数は、ターゲットのアプリケーション、処理速度、入力画像の特性、行列を推定するために用いられるロバスト推定アルゴリズムに応じて適切な値が設定される。３×３行列を推定するＲＡＮＳＡＣでは、３００のサンプルがあれば十分なので、本実施形態では、３００を領域分間数である２０で割った値である１５を抽出目標数としている。

＜実施形態４＞
実施形態４は、代表ベクトルの算出にＲＡＮＳＡＣを用いずに、代表ベクトルを算出する構成について説明する。

以下、代表ベクトルを算出するサブルーチンの動作について、図９を用いて説明する。図９は代表ベクトルの算出処理の詳細を示すフローチャートである。図９は、実施形態１の図５のフローチャートの代わりに実行される。

Ｓ９０１０では、ＣＰＵ１０５が、領域内の動きベクトル全体から平均動きベクトルを算出する。平均動きベクトルは、下記のように計算される。

Ｓ９０２０では、ＣＰＵ１０５が、平均動きベクトルと距離差が許容誤差ｅ_avg以内の動きベクトルを抽出する。ここで、抽出した動きベクトルの集合Ｖ_avgは、下記のように表現できる。

Ｓ９０３０では、ＣＰＵ１０５が、Ｓ９０２０で抽出した動きベクトルの平均動きベクトル（第二の平均動きベクトル）を再度算出する。

Ｓ９０４０では、ＣＰＵ１０５が、第二の平均動きベクトルを戻り値として返す。

この戻り値である

を代表ベクトルとして、実施形態１で説明した処理を実行することにより防振が可能となる。

以上説明したように、実施形態４によれば、代表ベクトルの算出にＲＡＮＳＡＣを用いるため、分割領域内の動きベクトルのアウトライア率が低い場合の利用に限られるものの、高速に代表ベクトルを算出することができる。

＜実施形態５＞
実施形態５は、インテリジェントな領域分割を用いて分割領域毎に代表ベクトルを算出する構成について説明する。

図１０は、オブジェクト単位の領域分割を用いる変換行列の推定処理の詳細を示すフローチャートである。図１０は、実施形態１の図３のフローチャートに対し、Ｓ１００００が追加されている。

Ｓ１００００は、ＣＰＵ１０５が、入力画像をオブジェクト単位で領域分割する。領域分割方法には様々な方法が存在するが、本実施形態では、ｋ−ｍｅａｎｓ法を用いて分割するものとする。分割数は８とする。各分割領域には番号が付けられる。番号の順序は任意である。尚、分割アルゴリズムや分割数はこれに限定されず、他の方式、分割数であってもよい。このようにして画像を分割すると、例えば、図１１のように分割される。図１１は、画像がオブジェクト単位で分割された状態と分割領域の番号の例を示す図である。分割領域の番号の振り方は任意である。

Ｓ３０１０以降は、格子状に区切られた分割領域の代わりに任意の形状の分割領域を対象にする以外は、実施形態１と同様の処理が実行される。

以上説明したように、実施形態５によれば、オブジェクト単位で画像を分割して、そのオブジェクトの領域毎に、代表ベクトルを算出する。同一オブジェクトに含まれる動きベクトルのベクトル成分は同一になる可能性が高いため、同一の許容誤差であっても代表ベクトルに類似のベクトルを抽出する際のインライア率を高めることができる。このため、回転行列推定においては、同一の動きを持つオブジェクトの集合の面積が最も大きい集合に含まれる動きベクトルが、画像全体の動きの主要成分となる傾向が強まる。これは、推定した回転行列を用いて防振を行う場合、広い面積が安定して防振されることになり、防振の安定性を高めることができる。

尚、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステムまたは装置に供給し、そのシステムまたは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。

Claims (16)

1. 時間的に連続する画像を処理する情報処理装置であって、
   処理対象画像を分割した分割領域内の動きベクトルに基づいて前記分割領域の代表ベクトルを決定する決定手段と、
   前記分割領域内の動きベクトルから、前記分割領域の代表ベクトルに対応する動きベクトルを抽出する抽出手段と、
   前記抽出手段で抽出した動きベクトルを用いて、基準画像からの位置ズレを表現する、前記処理対象画像に関する動きパラメータを算出する算出手段と
   を備え、
   前記決定手段は、前記分割領域に含まれる動きベクトルから取得した動きベクトルとの差が許容誤差内の、前記取得した動きベクトルと同じ分割領域に含まれる動きベクトルの数に基づいて前記代表ベクトルを決定することを特徴とする情報処理装置。
2. 時間的に連続する画像を処理する情報処理装置であって、
   処理対象画像を分割した分割領域内の動きベクトルに基づいて前記分割領域の代表ベクトルを決定する決定手段と、
   前記分割領域内の動きベクトルから、前記分割領域の代表ベクトルに対応する動きベクトルを抽出する抽出手段と、
   前記抽出手段で抽出した動きベクトルを用いて、基準画像からの位置ズレを表現する、前記処理対象画像に関する動きパラメータを算出する算出手段と
   を備え、
   前記決定手段は、前記分割領域内のサンプル全体の動きベクトルのうち、前記分割領域内のサンプル全体の動きベクトルの平均動きベクトルとの距離差が許容誤差内の動きベクトルを抽出し、抽出した動きベクトルの平均ベクトルを前記分割領域の代表ベクトルとすることを特徴とする情報処理装置。
3. 前記動きパラメータに基づいて電子防振処理を行う防振手段を更に備える
   ことを特徴とする請求項１または２に記載の情報処理装置。
4. 前記決定手段は、前記分割領域内のサンプル全体の動きベクトルから取得した動きベクトルと前記分割領域内のサンプル全体の動きベクトルとの差を算出し、前記分割領域内のサンプル全体の動きベクトルから取得した複数の動きベクトルのうち、前記算出した差が許容誤差内の動きベクトルの数が最大の動きベクトルを前記分割領域の代表ベクトルとする
   ことを特徴とする請求項１に記載の情報処理装置。
5. 前記抽出手段は、前記分割領域から抽出する動きベクトルの数が前記分割領域内の動きベクトルの所定割合以上となるように、前記抽出する動きベクトルの許容誤差を設定することを特徴とする請求項１乃至４のいずれか１項に記載の情報処理装置。
6. 前記抽出手段は、前記分割領域から抽出する動きベクトルの数が抽出目標数以下となるように、前記抽出する動きベクトルの許容誤差を設定する
   ことを特徴とする請求項１乃至４のいずれか１項に記載の情報処理装置。
7. 前記算出手段は、
   前記処理対象画像内の動きベクトルから選択された一組の動きベクトルから回転行列を算出する第二の算出手段と、
   前記処理対象画像内の動きベクトルのうち、前記処理対象画像内の動きベクトルの始点を前記第二の算出手段により計算された回転行列により変換した点と前記処理対象画像内の動きベクトルの終点との差が所定未満の動きベクトルの個数をカウントするカウント手段を有し、
   前記差が所定未満の動きベクトルの個数に基づいて、複数組の動きベクトルから計算された複数の回転行列の１つを、前記処理対象画像に関する動きパラメータとすることを特徴とする請求項１乃至６のいずれか１項に記載の情報処理装置。
8. 前記抽出手段は、前記分割領域内の動きベクトルから、前記代表ベクトルとの距離が許容誤差内である動きベクトルを、前記対応する動きベクトルとして抽出する
   ことを特徴とする請求項１乃至７のいずれか１項に記載の情報処理装置。
9. 前記動きパラメータは、前記処理対象画像の全体に対する動きパラメータであることを特徴とする請求項１乃至８いずれか１項に記載の情報処理装置。
10. 前記分割領域は、前記処理対象画像をオブジェクト単位で分割した領域である
    ことを特徴とする請求項１乃至９のいずれか１項に記載の情報処理装置。
11. 時間的に連続する画像を処理する情報処理装置の制御方法であって、
    処理対象画像を分割した分割領域内の動きベクトルに基づいて前記分割領域の代表ベクトルを決定する決定工程と、
    前記分割領域内の動きベクトルから、前記分割領域の代表ベクトルに対応する動きベクトルを抽出する抽出工程と、
    前記抽出工程で抽出した動きベクトルを用いて、基準画像からの位置ズレを表現する、前記処理対象画像に関する動きパラメータを算出する算出工程と
    を備え、
    前記決定工程では、前記分割領域に含まれる動きベクトルから取得した動きベクトルとの差が許容誤差内の、前記取得した動きベクトルと同じ分割領域に含まれる動きベクトルの数に基づいて前記代表ベクトルを決定することを特徴とする情報処理装置の制御方法。
12. 時間的に連続する画像を処理する情報処理装置の制御方法であって、
    処理対象画像を分割した分割領域内の動きベクトルに基づいて前記分割領域の代表ベクトルを決定する決定工程と、
    前記分割領域内の動きベクトルから、前記分割領域の代表ベクトルに対応する動きベクトルを抽出する抽出工程と、
    前記抽出工程で抽出した動きベクトルを用いて、基準画像からの位置ズレを表現する、前記処理対象画像に関する動きパラメータを算出する算出工程と
    を備え、
    前記決定工程では、前記分割領域内のサンプル全体の動きベクトルのうち、前記分割領域内のサンプル全体の動きベクトルの平均動きベクトルとの距離差が許容誤差内の動きベクトルを抽出し、抽出した動きベクトルの平均ベクトルを前記分割領域の代表ベクトルとすることを特徴とする情報処理装置の制御方法。
13. 前記動きパラメータに基づいて電子防振処理を行う防振工程を更に備える
    ことを特徴とする請求項１１又は１２に記載の情報処理装置の制御方法。
14. 時間的に連続する画像を処理する情報処理装置の制御をコンピュータに機能させるためのプログラムであって、
    前記コンピュータを、
    処理対象画像を分割した分割領域内の動きベクトルに基づいて前記分割領域の代表ベクトルを決定する決定手段と、
    前記分割領域内の動きベクトルから、前記分割領域の代表ベクトルに対応する動きベクトルを抽出する抽出手段と、
    前記抽出手段で抽出した動きベクトルを用いて、基準画像からの位置ズレを表現する、前記処理対象画像に関する動きパラメータを算出する算出手段と
    して機能させ、
    前記決定手段は、前記分割領域に含まれる動きベクトルから取得した動きベクトルとの差が許容誤差内の、前記取得した動きベクトルと同じ分割領域に含まれる動きベクトルの数に基づいて前記代表ベクトルを決定することを特徴とするプログラム。
15. 時間的に連続する画像を処理する情報処理装置の制御をコンピュータに機能させるためのプログラムであって、
    前記コンピュータを、
    処理対象画像を分割した分割領域内の動きベクトルに基づいて前記分割領域の代表ベクトルを決定する決定手段と、
    前記分割領域内の動きベクトルから、前記分割領域の代表ベクトルに対応する動きベクトルを抽出する抽出手段と、
    前記抽出手段で抽出した動きベクトルを用いて、基準画像からの位置ズレを表現する、前記処理対象画像に関する動きパラメータを算出する算出手段と
    して機能させ、
    前記決定手段は、前記分割領域内のサンプル全体の動きベクトルのうち、前記分割領域内のサンプル全体の動きベクトルの平均動きベクトルとの距離差が許容誤差内の動きベクトルを抽出し、抽出した動きベクトルの平均ベクトルを前記分割領域の代表ベクトルとすることを特徴とするプログラム。
16. 前記コンピュータを、前記動きパラメータに基づいて電子防振処理を行う防振手段として更に機能させることを特徴とする請求項１４または１５に記載のプログラム。

Images