(57)【特許請求の範囲】
【請求項１】
２つのフレームの画像データに対してサブサンプリングとフィルタリングとを実行することにより階層化画像データを生成する階層化演算手段と、
上記階層化演算手段により生成された階層化画像データに基づいて空間輝度勾配行列とミスマッチベクトルを演算し、上記演算された空間輝度勾配行列及びミスマッチベクトルに基づいてオプティカルフローを演算するオプティカルフロー演算手段とを備えた画像処理装置において、
上記オプティカルフロー演算手段は、上記演算されたオプティカルフローを上位階層から下位階層に伝搬させるときに上記オプティカルフローに所定の上限値を限定して更新することにより、上記オプティカルフローの可動域を所定の可動域に限定し、
上記階層化演算手段及び上記オプティカルフロー演算手段は所定の複数の演算回路を用いてパイプライン処理を実行し、上記画像データのうちのオプティカルフローを演算する所定の領域のオプティカルフローを演算の終了を待たずに、次の領域のオプティカルフローを演算することを開始することを特徴とする画像処理装置。
【請求項２】
上記オプティカルフロー演算手段は、上記演算された空間輝度勾配行列及びミスマッチベクトルについて乗算演算を実行した後、回復法アルゴリズムを用いて除算演算を実行するときに、上記除算演算の演算結果における拡張ビットを削除することを特徴とする請求項１記載の画像処理装置。
【請求項３】
２つのフレームの画像データに対してサブサンプリングとフィルタリングとを実行することにより階層化画像データを生成する階層化演算ステップと、
上記階層化演算ステップにより生成された階層化画像データに基づいて空間輝度勾配行列とミスマッチベクトルを演算し、上記演算された空間輝度勾配行列及びミスマッチベクトルに基づいてオプティカルフローを演算するオプティカルフロー演算ステップとを演算プロセッサ装置により実行する画像処理方法において、
上記オプティカルフロー演算ステップは、上記演算されたオプティカルフローを上位階層から下位階層に伝搬させるときに上記オプティカルフローに所定の上限値を限定して更新することにより、上記オプティカルフローの可動域を所定の可動域に限定し、
上記階層化演算ステップ及び上記オプティカルフロー演算ステップは所定の複数の演算回路を用いてパイプライン処理を実行し、上記画像データのうちのオプティカルフローを演算する所定の領域のオプティカルフローを演算の終了を待たずに、次の領域のオプティカルフローを演算することを開始することを特徴とする画像処理方法。
【請求項４】
上記オプティカルフロー演算ステップは、上記演算された空間輝度勾配行列及びミスマッチベクトルについて乗算演算を実行した後、回復法アルゴリズムを用いて除算演算を実行するときに、上記除算演算の演算結果における拡張ビットを削除することを特徴とする請求項３記載の画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層化された画像データについてオプティカルフローを演算する画像処理装置及び方法に関する。
【背景技術】
【０００２】
オプティカルフローは動画像における連続２フレーム間での画素毎の動きベクトルのことであり、動画像認識処理の要素として使用される。すなわち、オプティカルフローは、画像の動きを表す画素毎の速度ベクトルで表され、この速度ベクトルを求めることにより画素の動きを検出する。白線検知や障害物認識などの車載分野、物体・動体認識やマニピュレーション用動き検出などのロボット分野、マルチメディアコンテンツ配信を高画質／高圧縮で実現するマルチメディア通信分野等における動画像認識に応用されている。特に車載やロボットでは実時間での処理が求められるため、オプティカルフロー計算の高速化は必須である。
【０００３】
従来の階層型ルーカス及びカナデ（Ｌｕｃｕｓ＆Ｋａｎａｄｅ）法によるオプティカルフローの計算を以下に説明する。現フレームの画像をＩ、次フレームの画像をＪとし、位置Ｘ＝（ｘ，ｙ）での画像の輝度値をそれぞれＩ（ｘ，ｙ）、Ｊ（ｘ，ｙ）とする。Ｉ上の点ｕ＝（ｕｘ，ｕｙ）からＪ上の最も類似性の高い点ｖ＝ｕ＋ｄ＝（ｕｘ＋ｄｘ，ｕｙ＋ｄｙ）への移動量ｄ＝（ｄｘ，ｄｙ）がオプティカルフローであり、次式のマッチング誤差関数を最小化するベクトルとして定義される。なお、当該明細書において、数式がイメージ入力された墨付き括弧の数番号と、数式が文字入力された大括弧の数式番号とを混在して用いており、また、当該明細書での一連の数式番号として「式（１）」の形式を用いて数式番号を式の最後部に付与して（付与していない数式も存在する）用いることとする。
【０００４】
【数１】
0004662969.tif 000002
【０００５】
ここで、マッチング誤差関数は整数のウィンドウ（２ｗｘ＋１，２ｗｙ＋１）の近傍画素について計算される。ｗｘ，ｗｙの値としては、主に２、３、４、５、６、７画素が用いられる。
【０００６】
大きな動きに対しても、精度良くオプティカルフローを求めるために、図２０に示すように画像を階層化することが行われている。図２０において、階層レベル０が原画像に対応しており、最も解像度が高い。上位階層の輝度値は例えば図２１に示すフィルタと１／２サブサンプリングによって求められる。これを下位階層から上位階層へと繰り返すことで、さらに上位の階層化画像を得る。階層数として実用的な値は２、３、４である。
【０００７】
階層化を用いたオプティカルフロー導出では、まず最も上位の階層Ｌｍでオプティカルフローが計算される。この計算結果は、１つ下の階層Ｌｍ−１のオプティカルフローの初期値として階層Ｌｍ−１に伝搬され、さらに階層Ｌｍ−１の結果は階層Ｌｍ−２に伝搬される。これを最下位階層まで繰り返すことによって最終的なオプティカルフローを得る。上位階層で算出されたオプティカルフローｇＬを初期予測値とすると、現階層のマッチング誤差関数は次式で定義される。
【０００８】
【数２】
0004662969.tif 000003
【０００９】
ここで、ｄＬ（残差）が現階層で求めるべきオプティカルフローとなる。上位階層で大きな動きｇＬを計算し、現階層で小さな動きｄＬを計算する。この残差オプティカルフローは次のレベルＬ−１の初期ベクトルｇＬ−１として伝搬される。つまり上位階層で得たオプティカルフローｇＬと現階層で得た残差オプティカルフローｄＬを合わせたものが下位階層Ｌ−１でのフローの初期値ｇＬ−１となる。下位階層への伝搬は次式で表される。
【００１０】
［数１］
ｇＬ−１＝２（ｇＬ＋ｄＬ）      （３）
【００１１】
次の階層での残差オプティカルフローｄＬ−１も上記と同様に計算され、この処理が最下位階層まで繰り返し行われ、最終的に式（１）で表されるオプティカルフローｄが求められる。
【００１２】
オプティカルフローの計算では、画素毎に独立した一連の方程式を解く必要があり、ＣＩＦ３０ｆｐｓのシーケンスの場合、数十ＧＯＰＳを超える演算量となる。このため、汎用プロセッサを用いたソフトウェア処理では、実時間処理を維持するために計算範囲を限定し、オプティカルフローの検出精度を落とす必要がある。実時間で全画面処理を高精度で行うためには専用ハードウェアが必要不可欠である。オプティカルフロープロセッサの１つであるＨＯＥプロセッサ（例えば、非特許文献１参照。）では最高解像度ＣＩＦ３０ｆｐｓを達成しているが、チップ面積が大きく、コスト面での負荷が大きい。今後、動画像認識処理において、高解像度な動画像への対応が必須となるため、より高解像度対応で小チップ面積のオプティカルフロープロセッサが必要となる。
【００１３】
高速のオプティカルフロープロセッサを実現するために、ＰＬＫアルゴリズムを用いることが提案されている（例えば、非特許文献２参照。）ＰＬＫアルゴリズムは、急峻な動きに対応するための階層化手法を階層型ルーカス及びカナデ（Pyramidal Lcus & Kanade）法のアルゴリズムに導入したものであり、非特許文献２で公開されている。一般的にオプティカルフローアルゴリズムでは線形近似を用いるため、大きな動きを含むシーケンスではフロー検出精度が低下する。そこで、図２０に示すような階層化手法を用いることにより、大きな移動量を小さな移動量として扱うことができ、大きな動きに対応可能となる。ＰＬＫアルゴリズムは、他のアルゴリズム（例えば、非特許文献３−６参照。）と比較して、演算量が少なく、メモリ使用量が小さく、精度が高いため、本アルゴリズムはＶＬＳＩに実装するアルゴリズムとして適している。
【００１４】
図２２は従来技術に係るＰＬＫアルゴリズムによるオプティカルフロー演算処理（以下、「ＯＰＦ（OPtical Flow)演算」という。）を示すフローチャートである。図２２において、ＰＬＫアルゴリズムによるＯＰＦ演算処理の全体処理（２つのフレームの画像データをメモリに入力した後の処理）は、公知のように、
（ａ）階層化画像生成演算（以下、「ＰＩＣ（Pyramidal Image Creation）演算」という。）処理（ステップＳ２，Ｓ３）と、
（ｂ）空間輝度勾配行列演算（以下、「ＳＧＭ（Spatial Gradient Matrix）演算」という。）処理（ステップＳ４）と、
（ｃ）ミスマッチベクトル演算（以下、「ＭＭＶ（Mismatch Vector）」演算という。)
処理（ステップＳ５）と、
（ｄ）ＯＰＦ演算処理（ステップＳ６）とを含む。
図２２において、ｉｔｒは繰り返し回数のパラメータであり、ｉｔｒｍａｘは繰り返し回数の最大値である。また、Ｌは階層数のパラメータであり、Ｌｍａｘは階層数の最大値である。なお、ステップＳ１では、これらの最大値をセットする初期化処理を行っている。
【００１５】
ＰＬＫアルゴリズムにおいて、座標（ｘ，ｙ）のオプティカルフローであるｕは次式によって計算される。
【００１６】
［数２］
Ｇｕ＝ｂ      （４）
【００１７】
【数３】
0004662969.tif 000004
【数４】
0004662969.tif 000005
【００１８】
ここで、Ｉｘ，Ｉｙ，Ｉｔはそれぞれｘ方向、ｙ方向、ｔ方向の輝度勾配であり、Ｇ、ｂをそれぞれ空間輝度勾配行列、ミスマッチベクトルと呼ぶ。ｗは重み係数である。Ｇ、ｂを注目画素を中心とした小領域（ウィンドウ）内で計算し、式（４）を解くことでオプティカルフローｕを得る。また、Σはウィンドウ内の画素全体における総和演算を表す。これはニュートン・ラプソン法による繰り返し処理が可能であり、求めたオプティカルフローを用いて中心画素の再定義を行い、式（４）を繰り返し計算することにより精度の高い解へと収束させることができる。
【００１９】
【特許文献１】特開平１１−１９５１０８号公報。
【特許文献２】特開２０００−１５５８３１号公報。
【非特許文献１】N. Minegishi, et al., "VLSI Architecture Study of a Real-Time Scalable Optical Flow Processor for Video Segmentation", IEICE transactions on electronics, Vol.E89-C, No.3, pp.230-242, 2006.
【非特許文献２】Jean-Yves Bouguet, "Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm", Open CV Documentation, Intel Corporation Microprocessor Research Laboratories, 1999.
【非特許文献３】T. Yamamoto et al., "Improvement of Optical Flow by Moving Object Detection using Temporal Correlation", Transactions IIITE, Vol.55, No.6, pp.907-911, 2001.
【非特許文献４】B.K.P. Horn et al., "Determining Optical Flow, Artificial Intelligence", Vol.17, pp.185-204, 1981.
【非特許文献５】J.L. Barron et al., "Performance of Optical Flow Techniques, International Journal Computer Vision", Vol.12, No.1, pp.43-77, 1994.
【非特許文献６】B. Lucas et al., "An Iterative Image Registration Technique With An Application to Stereo Vision", Proceedings of DARPA Image Understanding Workshop, pp. 121-130, 1981.
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、オプティカルフローを求めるのに、その更新値に制限を加えていないために、その演算回路内部のキャッシュメモリサイズが大きくなり、演算精度も悪くなる。さらに除算回路の回路規模とサイクル数が大きいという問題点があった。
【００２１】
本発明の目的は以上の問題点を解決し、オプティカルフローの演算において、従来技術に比較して、より短い演算時間で演算可能であって計算コストを軽減でき、しかも演算精度を改善できる画像処理装置及び方法を提供することにある。
【課題を解決するための手段】
【００２２】
第１の発明に係る画像処理装置は、２つのフレームの画像データに対してサブサンプリングとフィルタリングとを実行することにより階層化画像データを生成する階層化演算手段と、
上記階層化演算手段により生成された階層化画像データに基づいて空間輝度勾配行列とミスマッチベクトルを演算し、上記演算された空間輝度勾配行列及びミスマッチベクトルに基づいてオプティカルフローを演算するオプティカルフロー演算手段とを備えた画像処理装置において、
上記オプティカルフロー演算手段は、上記演算されたオプティカルフローを上位階層から下位階層に伝搬させるときに上記オプティカルフローに所定の上限値を限定して更新することにより、上記オプティカルフローの可動域を所定の可動域に限定することを特徴とする。
【００２３】
上記画像処理装置において、上記オプティカルフロー演算手段は、上記演算された空間輝度勾配行列及びミスマッチベクトルについて乗算演算を実行した後、回復法アルゴリズムを用いて除算演算を実行するときに、上記除算演算の演算結果における拡張ビットを削除することを特徴とする。
【００２４】
また、上記画像処理装置において、上記階層化演算手段及び上記オプティカルフロー演算手段は所定の複数の演算回路を用いてパイプライン処理を実行し、上記画像データのうちのオプティカルフローを演算する所定の領域のオプティカルフローを演算の終了を待たずに、次の領域のオプティカルフローを演算することを開始することを特徴とする。
【００２５】
第２の発明に係る画像処理方法は、２つのフレームの画像データに対してサブサンプリングとフィルタリングとを実行することにより階層化画像データを生成する階層化演算ステップと、
上記階層化演算ステップにより生成された階層化画像データに基づいて空間輝度勾配行列とミスマッチベクトルを演算し、上記演算された空間輝度勾配行列及びミスマッチベクトルに基づいてオプティカルフローを演算するオプティカルフロー演算ステップとを演算プロセッサ装置により実行する画像処理方法において、
上記オプティカルフロー演算ステップは、上記演算されたオプティカルフローを上位階層から下位階層に伝搬させるときに上記オプティカルフローに所定の上限値を限定して更新することにより、上記オプティカルフローの可動域を所定の可動域に限定することを特徴とする。
【００２６】
上記画像処理方法において、上記オプティカルフロー演算ステップは、上記演算された空間輝度勾配行列及びミスマッチベクトルについて乗算演算を実行した後、回復法アルゴリズムを用いて除算演算を実行するときに、上記除算演算の演算結果における拡張ビットを削除することを特徴とする。
【００２７】
また、上記画像処理方法において、上記階層化演算ステップ及び上記オプティカルフロー演算ステップは所定の複数の演算回路を用いてパイプライン処理を実行し、上記画像データのうちのオプティカルフローを演算する所定の領域のオプティカルフローを演算の終了を待たずに、次の領域のオプティカルフローを演算することを開始することを特徴とする。
【発明の効果】
【００２８】
本発明に係る画像処理装置及び方法によれば、記演算されたオプティカルフローを上位階層から下位階層に伝搬させるときに上記オプティカルフローに所定の上限値を限定して更新することにより、上記オプティカルフローの可動域を所定の可動域に限定し、好ましくは、上記演算された空間輝度勾配行列及びミスマッチベクトルについて乗算演算を実行した後、回復法アルゴリズムを用いて除算演算を実行するときに、上記除算演算の演算結果における拡張ビットを削除し、より好ましくは、上記階層化演算ステップ及び上記オプティカルフロー演算ステップは所定の複数の演算回路を用いてパイプライン処理を実行し、上記画像データのうちのオプティカルフローを演算する所定の領域のオプティカルフローを演算の終了を待たずに、次の領域のオプティカルフローを演算することを開始する。これにより上記演算プロセッサのキャッシュ容量、除算回路の面積及び処理サイクル数を従来技術に比較して、大幅に削減できる。これにより、演算プロセッサのハードウェアの低消費電力化、高速化、及び省面積化を行うことができる。従って、オプティカルフローの演算において、従来技術に比較してより短い演算時間で演算することができ、オプティカルフローの演算プロセッサを構成したときにそのハードウェアを大幅に小型化できる。
【発明を実施するための最良の形態】
【００２９】
以下、本発明に係る実施形態について図面を参照して説明する。なお、以下の各実施形態において、同様の構成要素については同一の符号を付している。
【００３０】
第１の実施形態．
図１は本発明の第１の実施形態に係るＯＰＦ演算プロセッサ２０の詳細構成を示すブロック図である。また、図２は図１のＯＰＦ演算プロセッサ２０によって実行される、オプティカルフローの演算において画像のウィンドウＢの稼働限定域１０１を設けることを示す画像フレーム１００の図である。第１の実施形態に係るＯＰＦ演算プロセッサ２０は、
（Ａ）オプティカルフローの更新値に上限値を設定し、例えば３画素以上をｘ方向及びｙ方向で切り捨てること、
（Ｂ）オプティカルフロー演算において、画素の処理順序をインターリーブすることにより、パイプライン処理でのアイドル期間を回避すること、
（Ｃ）ＯＰＦ演算回路３０内の除算回路３２（図６参照。）の拡張ビット数を削減すること
を特徴としている。
【００３１】
図１において、ＯＰＦ演算プロセッサ２０を含む演算プロセッサ集積回路は例えばＶＬＳＩで実装され、全体制御用ＣＰＵ１０と、ＣＰＵバス２０ａと、処理すべき動画像データを予め記憶する画像メモリ１１と、メモリバス２０ｂと、ＯＰＦ演算プロセッサ２０と、ＣＰＵバス２０ａに接続された演算結果データメモリ（外部メモリ）１２と、インターフェース１３と、ディスプレイ１４とを備えて構成される。ここで、ＯＰＦ演算プロセッサ２０は、
（ａ）ＣＰＵバス２０ａに接続され、ＣＰＵ１０の制御のもとでＯＰＦ演算プロセッサ２０内の処理シーケンスを制御するシーケンスコントローラ２１と、
（ｂ）メモリバス２０ｂに接続され、画像メモリ１１からの制御のもとでＯＰＦ演算プロセッサ２０内でのアドレスを発生して各回路に出力するアドレス発生器２２と、
（ｃ）画像メモリ１１からの第１のフレーム画像の画像データを記憶するフレームＡメモリ２３と、
（ｄ）画像メモリ１１からの第２のフレーム画像の画像データを記憶するフレームＢメモリ２４と、
（ｅ）メモリ２３，２４に格納された各フレームの画像データに基づいて階層化画像の画像データを演算することにより生成するＰＩＣ演算回路２５と、
（ｆ）ＰＩＣ演算回路２５により生成された階層化された第１の画像データを記憶する階層化画像Ａメモリ２６と、
（ｇ）ＰＩＣ演算回路２５により生成された階層化された第２の画像データを記憶する階層化画像Ｂメモリ２７と、
（ｈ）階層化画像Ａメモリ２６に格納された画像データに基づいて空間輝度勾配行列を演算することにより生成するＳＧＭ演算回路２８と、
（ｉ）階層化画像Ｂメモリ２７に格納された画像データに基づいてミスマッチベクトルを演算することにより生成するＭＭＶ演算回路２９と、
（ｊ）上記演算された空間輝度勾配行列及びミスマッチベクトルに基づいてオプティカルフローを演算するＯＰＦ演算回路３０と
を備えて構成される。ここで、ＰＩＣ演算回路２５と、ＳＧＭ演算回路２８と、ＭＭＶ演算回路２９と、ＯＰＦ演算回路３０とはそれぞれ並列にパイプライン処理を行う。
【００３２】
ＰＩＣ演算回路２５は、メモリ２３，２４に格納された２つのフレームの画像データに基づいて、図２０に示すように、サブサンプリングとガウシアンフィルタリングを行い、階層化画像データを生成してそれぞれメモリ２６，２７に出力して格納する。ＳＧＭ演算回路２８はメモリ２６に格納された階層化画像データに基づいて空間輝度勾配行列Ｇを算出する。ここで、ＳＧＭ演算回路２８では、まず現フレームの階層化画像データから小数点画素の輝度値を補間し、現フレームにおける処理用の小領域であるウィンドウＡを作成する。次に、ウィンドウＡ内でｘ方向及びｙ方向の空間輝度勾配を求める。そして、求めた空間輝度勾配を用いて、画素毎に空間輝度勾配行列の要素を計算する。最後に求められた空間輝度勾配行列の要素を行方向に加算する。これらの処理をウィンドウサイズと同じ回数だけ繰り返すことによりウィンドウ内の総和の空間輝度勾配行列Ｇが導出される。ＭＭＶ演算回路２９はメモリ２７に格納された階層化画像データに基づいてミスマッチベクトルｂを演算する。ＭＭＶ演算回路２９では、まず上位階層のオプティカルフローを用いて、次フレームの階層化画像から移動先の小数点画素の輝度値を補間する。次に、ウィンドウＢを作成し、ＳＧＭ演算回路２８により求めたウィンドウＡとウィンドウＢを用いて時間輝度勾配を求める。そしてＳＧＭ演算回路２８により求められた空間輝度勾配行列と時間輝度勾配から各画素のミスマッチベクトルを計算する。最後にＳＧＭ演算回路２８と同様に計算結果を加算することで、ウィンドウ内の総和のミスマッチベクトルｂが導出される。ＯＰＦ演算回路３０は空間輝度勾配行列Ｇ及びミスマッチベクトルｂに基づいてオプティカルフローｕを算出する。ＯＰＦ演算回路３０では、ＳＧＭ演算回路２８及びＭＭＶ演算回路２９により計算された空間輝度勾配行列Ｇ及びミスマッチベクトルｂを用いて式（４）を解き、オプティカルフローｕを計算する。すなわち、オプティカルフローｕは次式で計算できる。
【００３３】
［数３］
ｕ＝Ｇ−１ｂ      （７）
【００３４】
最後に、算出されたオプティカルフローを、前回の計算で得られたオプティカルフローに加算し、オプティカルフローを更新する。演算されたオプティカルフローｕは演算結果データメモリ１２に格納された後、インターフェース１３を介してディスプレイ１４に出力されて表示される。
【００３５】
従来のＯＰＦプロセッサにおいてリアルタイム処理を実現しようとした場合、キャッシュ容量の増大、サイクル数の増加などの問題からリアルタイム処理と省面積、低消費電力の両立が非常に困難である。これに対して、本発明に係る第１の実施形態では、精度の向上、キャッシュ容量の低減、サイクル数の低減等、リアルタイム処理と省面積、低消費電力を同時に実現するための２つの要素技術を提案する。
【００３６】
本発明に係る第１の実施形態では、ＯＰＦプロセッサ２０の要素技術として、２つの新しい提案手法を提案する。第１の提案手法はオプティカルフロー更新値の上限の設定であり、第２の提案手法はウィンドウインターリーブ手法である。以下、それぞれの新しい提案手法について説明する。
【００３７】
まず、第１の提案手法に係るオプティカルフローの上限の設定について説明する。従来法のＯＰＦプロセッサにおいては、オプティカルフローの大きさに上限を設定していない。このため、雑音などにより、ありえない大きさの更新値が発生した場合でもそのまま演算を進める。これに対し、第１の提案手法ではオプティカルフローの大きさに上限を設定する。すなわち、第１の提案手法では、３以上の長さのオプティカルフローが検出された場合、これを３に切り捨てる（図２）。すなわち、図２において、画像フレーム１００内のウィンドウＢについて次のウィンドウＢをＯＰＦ演算するときに、ウィンドウＢの可動限定域１０１を設定し、その更新値をその範囲に限定する（上限値を設定する）ものである。具体的には図３のフローチャートを用いる。
【００３８】
図３は図１のＯＰＦ演算プロセッサ２０によって実行されるＰＬＫアルゴリズムによるオプティカルフロー演算処理を示すフローチャートである。図３のオプティカルフロー演算処理は、従来技術に係る図２２のオプティカルフロー演算処理に比較して、ステップＳ１１−Ｓ１４の処理を追加したことを特徴としている。ステップＳ６のＯＰＦ演算処理後のステップＳ１１において、上記演算されたオプティカルフローｕのｘ成分ｕｘが３以下であれば、そのままオプティカルフローとして用いるが、３を超える場合は、ステップＳ１２において当該オプティカルフローｕのｘ成分ｕｘを上限値３に更新する。次いで、ステップＳ１３において、上記演算されたオプティカルフローｕのｙ成分ｕｙが３以下であれば、そのままオプティカルフローとして用いるが、３を超える場合は、ステップＳ１４において当該オプティカルフローｕのｙ成分ｕｙを上限値３に更新する。そして、ステップＳ７に進む。ここで、上限値を３に更新しているが、本発明はこれに限らず、所定の上限値であってもよい。
【００３９】
この第１の提案手法は従来法に対し以下の３つの利点を得る。利点の１つめは精度の向上である。正しいオプティカルフローはある一定以上の大きさを示すことはないため、ノイズの影響などで誤って求められた極端に大きいオプティカルフローを許容することは精度の劣化につながる。
【００４０】
図４は従来技術及び第１の実施形態に係るＯＰＦ演算プロセッサ２０のシミュレーション結果であって、各パラメータに対する平均絶対誤差ＭＡＥを示す図である。また、図５は従来技術及び第１の実施形態に係るＯＰＦ演算プロセッサ２０のシミュレーション結果であって、各パラメータに対する平均二乗誤差ＭＳＥを示す図である。図４及び図５において、Ｌは階層数を示し、Ｗはウィンドウサイズを示し、Ｉは繰り返し回数を示す。図４及び図５から明らかなように、上限を設定した場合、ＭＡＥはほぼ変わらず、ＭＳＥは大きく改善されている。
【００４１】
次いで、利点の２つめはキャッシュの容量の削減である。オプティカルフローに上限を設定しない場合、フレーム全体の画素をキャッシュに保持する必要があり、キャッシュ容量が大きくなりやすい。これに対しオプティカルフローの上限を設定した場合、フレームの一部の画素をキャッシュに保持すればよいこととなり、キャッシュ容量を削減することが可能である。フレーム全体を保持する場合１２００キロバイト必要であったキャッシュ容量を９８．５％削減し、１８キロバイトにすることができる。
【００４２】
さらに、利点の３つめは、回復法アルゴリズムを用いたＯＰＦ演算回路３０内の除算回路３２−１乃至３２−４（総称して、符号３２を付す。）におけるサイクル数及び回路規模の削減である。図６は図１のＯＰＦ演算回路３０の構成を示すブロック図である。図６において、ＯＰＦ演算回路３０は、式（４）を用いてオプティカルフローｕを演算するために、３２ビット乗算回路３１と、パイプライン処理のための４個の除算回路３２−１乃至３２−４を備えて構成される。ここで、３２ビット乗算回路３１による乗算後の行列Ｇ’及びベクトルｂ’は次式で表される。
【００４３】
［数４］
Ｇ’＝［ＸＸＸ…Ｘ０００…０］      （８）
ここで、［ＸＸＸ…Ｘ］＝Ｇであり、［０００…０］＝拡張ビットである。
［数５］
ｂ’＝［０００…０ＹＹＹ…Ｙ］      （９）
ここで、［０００…０］＝拡張ビットであり、［ＹＹＹ…Ｙ］＝ｂである。
【００４４】
図７は図６の除算回路３２−１乃至３２−４（３２）の構成を示すブロック図である。ここで、図７の除算回路３２は回復法を用いたアーキテクチャである。図７において、除算回路３２は、マルチプレクサ３３と、２個のレジスタ３４，３５と、減算器３６と、マルチプレクサ３７とを備えて構成される。ここで、マルチプレクサ３３，３７はクロックＣＬに基づいて互いに交互にデータの１つを選択するように切り替える。行列Ｇ’はレジスタ３５を介して減算器３６に入力される一方、ベクトルｂ’はマルチプレクサ３３及びレジスタ３４を介して減算器３６に入力される。減算器３６はレジスタ３４からのデータからレジスタ３５からのデータを減算し、減算結果の符号１ビットを部分商の符号ビットとして出力するとともに、減算結果のデータ（符号を除く。）をマルチプレクサ３７に出力する。マルチプレクサ３７は上述のようにクロックＣＬに従って、入力される２つのデータのうちの１つのデータを選択してマルチプレクサ３３に出力する。
【００４５】
回復法アルゴリズムにおいては、除数をＧ、被除数をｂとした場合Ｇ＞ｂを満たす必要がある。この条件を満たすため、従来技術に係るアーキテクチャにおいては除数ｎビット及び被除数ｎビットに対しそれぞれ拡張ビットｎビットを追加し２ｎビットとする必要がある。これに対し、本実施形態では、オプティカルフローすなわち除算結果の上限を設定することにより、上限以上の値をすべて上限に丸めることができるため（具体的には、各除算回路３２からの除算結果のデータのビット数を制限する。）、拡張ビット数を削減することが可能である。オプティカルフローの上限をｍに制限することにより、拡張ビット数は√（ｍ）となる。回復法を用いたアーキテクチャでは拡張後のビット数が演算サイクル数となるため、演算サイクル数を２ｎからｎ＋√（ｍ）に削減できる。演算ビット数が減るため、回路規模の削減にもつながる。提案手法を用いた場合、回復法アルゴリズムを用いた除算回路３２の回路規模を４７％削減することができる。
【００４６】
次に、第２の提案手法に係るウィンドウインターリーブ手法について説明する。階層的なオプティカルフローを求める場合、従来法のオプティカルフロープロセッサにおいては、上位階層の結果が得られるまで下位階層の演算を開始できず、パイプラインストールが起こるという問題が発生していた。これに対し提案法では、結果が相互に影響しない複数画素の上位階層の結果を連続的に演算し、その後に下位階層の演算を行うウィンドウインターリーブ手法を用いている。図８は従来技術に係るパイプライン処理におけるＯＰＦ演算プロセッサの各演算回路の演算タイミングを示すフロー図である。また、図９は第１の実施形態に係るウィンドウインターリーブ法を用いたパイプライン処理における図１のＯＰＦ演算プロセッサ２０の各演算回路の演算タイミングを示すフロー図である。図８及び図９において、各矩形部分は各回路での画像データを示し、ここで、Ｌ３は階層３を示し、ｐ０は画素列０を示し、ｒｏｗ０は画素行０を示し、以下同様である。
【００４７】
図８及び図９から明らかなように、ＰＩＣ演算回路２５と、ＭＭＶ演算回路２９内のＭＶ演算器と、ＭＭＶ演算回路２９内の加算器と、ＯＰＦ演算回路３０とが並列に処理されるパイプライン処理を実行する。しかしながら、図８から明らかなように、従来技術では、ある画素行のオプティカルフローｕを計算するまで、次の画素行を計算しないために無駄な「アイドル期間」が発生している。これに対して、本実施形態では、図１のシーケンスコントローラ２１及びアドレス発生器２２の制御により、ある画素行のオプティカルフローｕの計算終了を待たずに、次の画素行についてＰＩＣ演算回路２５及びＭＭＶ演算回路２９のＭＶ演算器の処理を開始しており、「アイドル期間」が発生しない。従って、従来技術に比較してパイプラインストールのサイクルを削減することが可能である。これにより、従来技術に比較して、ウィンドウインターリーブ手法を用いることによって必要サイクル数を６５％削減することができる。
【００４８】
以上説明したように、本実施形態によれば、（Ａ）オプティカルフローの更新値に上限値を設定し、例えば３画素以上をｘ方向及びｙ方向で切り捨て、（Ｂ）オプティカルフロー演算において、画素の処理順序をインターリーブすることにより、パイプライン処理でのアイドル期間を回避し、（Ｃ）ＯＰＦ演算回路３０内の除算回路３２の拡張ビット数を削減することにより、ＯＰＦプロセッサ２０のキャッシュ容量、除算回路３２の面積及び処理サイクル数を従来技術に比較して、大幅に削減できる。これにより、ＯＰＦプロセッサ２０のハードウェアの低消費電力化、高速化、及び省面積化を行うことができる。
【００４９】
第２の実施形態．
図１０は従来技術に係るオプティカルフロー演算における第１乃至第４の画素順序の演算方法を示す図であり、図１１は本発明の第２の実施形態に係るオプティカルフロー演算における第１の画素順序の演算方法を示す図である。図１のＰＩＣ演算回路２５によって実行される階層化処理では、下位レベルの画像に対してサブサンプリングを用いて、上位階層の画像を作成しているため、下位階層の座標（２ｘ，２ｙ）で表される画素のオプティカルフローを求める場合に使われる階層化画像は、下位階層の座標（２ｘ＋１，２ｙ）、（２ｘ，２ｙ＋１）、（２ｘ＋１，２ｙ＋１）のときに用いられる階層化画像と同じものになる。そのため、図１０の従来技術では、画面左上から右下まで１行毎に走査して行く処理順序では、偶数行の処理で作成した階層化画像を、再び奇数行で作成し直すことになる。すなわち、図１０において、階層化画像を保存する内部キャッシュメモリ（ＰＩＣ演算回路２５内の内部キャッシュメモリをいう。）の内容が階層化画像Ａ、Ｂ、Ｃと更新されてゆくことになるが、次の奇数行の処理では、再びＡからＣまでの階層化画像を作成する必要が出てくる。そのために処理に重複が生じ、無駄なサイクルとなってしまい、性能の低下や消費電力の増加を招くことになる。これを避けるために１行分の階層化画像Ａ、Ｂ、Ｃを記憶するキャッシュメモリを用意すると、今度は膨大なハードウェアの増加を招くことになる。
【００５０】
これに対して、本発明の第２の実施形態では、例えば図１１に示すような「Ｚ字形状」の画素順序で繰り返しサブサンプリングした後オプティカルフローを求める。同じ階層化画像を使用する隣接４画素単位に行うことになるので、階層化処理の重複が回避され、サイクル数の削減が可能になる。図１２は図１１の第１の画素順序の演算方法（Ｌ＝３のとき）を示す図であり、図１３は図１１の第１の画素順序の演算方法（Ｌ＝４のとき）を示す図であるすなわち、階層数Ｌが２より大きい場合が図１２及び図１３に示されており、４Ｌ−１画素単位の階層繰り返し処理となる。
【００５１】
図１４乃至図１６は図１１の変形例であって、それぞれ本発明の第２の実施形態に係るオプティカルフロー演算における第２乃至第４の画素順序の演算方法を示す図である。図１４では、「Ｕ字形状」の画素順序で繰り返しサブサンプリングした後オプティカルフローを求める。同じ階層化画像を使用する隣接４画素単位に行うことになるので、階層化処理の重複が回避され、サイクル数の削減が可能になる。また、図１５では、「コの字形状」又は「Ｃの字を左右反転した形状」の画素順序でサブサンプリングした後オプティカルフローを求める。同じ階層化画像を使用する隣接４画素単位に行うことになるので、階層化処理の重複が回避され、サイクル数の削減が可能になる。さらに、図１６では、「Ｘ字形状」又は「αの字を左右反転した形状」の画素順序でサブサンプリングした後オプティカルフローを求める。同じ階層化画像を使用する隣接４画素単位に行うことになるので、階層化処理の重複が回避され、サイクル数の削減が可能になる。
【００５２】
次いで、第２の実施形態に係るＯＰＦ演算プロセッサ２０におけるオプティカルフローの上位階層から下位階層への伝搬方法の改善について以下に説明する。
【００５３】
ＰＩＣ演算回路２５による階層化処理では１／２のサブサンプリングを行っているため、階層Ｌでの１画素は、階層Ｌ−１での４画素分の情報量に相当する。図１７は本発明の第２の実施形態に係る第１のオプティカルフローの伝搬方法を示す図である。この伝搬方法では、図１７に示すように、階層Ｌにおいて座標Ｌ（０，０）の１画素から、階層Ｌ−１の４画素の座標に対応するＬ（１，０）、Ｌ（０，１）、Ｌ（１，１）の３種類の内挿画素を作成し、それぞれのオプティカルフローを求め、階層Ｌ−１に伝搬する。すなわち、当該伝搬方法では、以下のようにオプティカルフローを演算している。なお、座標Ｌ（０，０）は階層Ｌの画素座標（０，０）を示し、座標Ｌ−１（０，０）は階層Ｌ−１の画素座標（０，０）を示し、以下同様に表記する。
【００５４】
（１）Ｌ（０，０）のオプティカルフロー導出：Ｌ（０，０）の輝度値Ｉ（０，０）を使って求めて、下位階層に伝搬させる。
【００５５】
（２）Ｌ（１，０）のオプティカルフロー導出：Ｉ（０，０）とＬ（２，０）の輝度値Ｉ（２，０）を使ってＬ（１，０）の輝度値Ｉ（１，０）を次式により内挿する。
［数６］
Ｉ（１，０）＝（１−ｓ）Ｉ（０，０）＋ｓＩ（２，０）      （１０）
ここで、ｓはｘ方向の内挿係数であって、ｓ＝１／２に設定される。これは、２：１サブサンプリングによりＩ（１，０）が存在しないためである。この輝度値を用いてオプティカルフローを計算し、その後下位階層に伝搬させる。
【００５６】
（３）Ｌ（０，１）のオプティカルフロー導出：Ｉ（０，０），Ｉ（０，２）を使って輝度値Ｉ（０，１）を内挿する。
［数７］
Ｉ（１，０）＝（１−ｔ）Ｉ（０，０）＋ｔＩ（０，２）      （１１）
ここで、ｔはｙ方向の内挿係数であって、ｓ＝１／２に設定される。
【００５７】
（４）Ｌ（１，１）のオプティカルフロー導出：Ｉ（０，０）、Ｉ（０，２）、Ｉ（２，０）、Ｉ（２，２）を使って輝度値Ｉ（１，１）を内挿する。
［数８］
Ｉ（１，１）
＝（１−ｓ）（１−ｔ）Ｉ（０，０）＋ｓ（１−ｔ）Ｉ（２，０）
＋（１−ｓ）ｔＩ（０，２）＋ｓｔＩ（２，２）      （１２）
【００５８】
以上説明したように、第１のオプティカルフローの伝搬方法によれば、上位階層で演算した複数のオプティカルフローのうち演算すべき座標に隣接する２つ又は４つの画素のオプティカルフローを内挿することにより演算したオプティカルフローを下位階層に伝搬して下位階層のオプティカルフローを演算する。
【００５９】
図１８は第２の実施形態に係る第２のオプティカルフローの伝搬方法を示す図である。この伝搬方法では、座標Ｌ（１／２，１／２）で内挿画素を１つだけ作成し、その１画素を用いてオプティカルフロー演算を行い、その値をＬ−１（０，０）、Ｌ−１（１，０）、Ｌ−１（０，１）、Ｌ−１（１，１）の４画素に対して共通に伝搬し階層Ｌ−１での初期値とする。すなわち、中心の座標は（１／２，１／２）と考え、Ｉ（１／２，１／２）を内挿により求めて、次式のごとくオプティカルフローを計算する。それを下位階層の４画素共通に用いる。
【００６０】
［数９］
Ｉ（１／２，１／２）
＝（１−ｓ）（１−ｔ）Ｉ（０，０）＋ｓ（１−ｔ）Ｉ（２，０）
＋（１−ｓ）ｔＩ（０，２）＋ｓｔＩ（２，２）      （１３）
ここで、ｓ＝ｔ＝１／４である。
【００６１】
以上説明したように、第２のオプティカルフローの伝搬方法によれば、上位階層で演算した各オプティカルフローを下位階層の複数の画素に共通に伝搬してそれを初期値として当該複数の画素で共通に用いて下位階層のオプティカルフローを演算し、ここで、上記上位階層で演算したオプティカルフローは、上記上位階層の画像領域を互いに隣接する４つの画素を含む領域を単位として分割し、その各領域内の４つの画素のオプティカルフローを内挿することにより、その各領域内の平均座標におけるオプティカルフローを演算した結果のオプティカルフローである。これにより、内挿画素作成のサイクルが１画素分だけに削減でき、オプティカルフロー演算も１画素分のみとなる。この場合、全４画素に対して、等しい距離においてオプティカルフローを計算するため、オプティカルフローの精度を維持しつつサイクル数の削減が可能となり、性能向上が図られる。
【００６２】
図１９は第２の実施形態に係る第３のオプティカルフローの伝搬方法を示す図である。この伝搬方法では、座標Ｌ（０，０）の画素から１画素分のオプティカルフローを求め、その値をＬ−１（０，０）、Ｌ−１（１，０）、Ｌ−１（０，１）、Ｌ−１（１，１）の４画素に対して共通に伝搬し階層Ｌ−１での初期値とする。すなわち、Ｉ（０，０）を用いてオプティカルフローを求め、下位階層の４画素で共通に伝搬させる。
【００６３】
以上説明したように、第２のオプティカルフローの伝搬方法によれば、上位階層で演算した各オプティカルフローを下位階層の複数の画素に共通に伝搬してそれを初期値として当該複数の画素で共通に用いて下位階層のオプティカルフローを演算し、ここで、上記上位階層で演算したオプティカルフローは、上記上位階層の画像領域を互いに隣接する４つの画素を含む領域を単位として分割し、その各領域内の４つの画素のうちの１つの画素のオプティカルフローである。従って、精度は若干劣化するものの内挿画素作成処理が不要となり、さらに他の３画素のオプティカルフロー計算も不要となる。従って、演算器の削減と、更なるサイクル数の削減が可能となり、性能向上及びハードウェアの小型化を図ることができる。
【００６４】
以上説明したように、本実施形態によれば、ＰＩＣ演算回路２５による階層化処理において、同じ階層化画像を使用する隣接４画素単位に行うことになるので、階層化処理の重複が回避され、サイクル数の削減が可能になる。また、上位階層で求めたオプティカルフローを下位階層の複数の画素に共通に伝搬させて下位階層のオプティカルフローの演算を行うので、オプティカルフローを外挿するサイクルやそのための演算回路などのハードウェアが不要となる。従って、従来技術に比較して、オプティカルフローの演算時間を短縮できるとともに、ＯＰＦ演算プロセッサのハードウェアを小型化できる。
【産業上の利用可能性】
【００６５】
以上詳述したように、本発明に係る画像処理装置及び方法によれば、記演算されたオプティカルフローを上位階層から下位階層に伝搬させるときに上記オプティカルフローに所定の上限値を限定して更新することにより、上記オプティカルフローの可動域を所定の可動域に限定し、好ましくは、上記演算された空間輝度勾配行列及びミスマッチベクトルについて乗算演算を実行した後、回復法アルゴリズムを用いて除算演算を実行するときに、上記除算演算の演算結果における拡張ビットを削除し、より好ましくは、上記階層化演算ステップ及び上記オプティカルフロー演算ステップは所定の複数の演算回路を用いてパイプライン処理を実行し、上記画像データのうちのオプティカルフローを演算する所定の領域のオプティカルフローを演算の終了を待たずに、次の領域のオプティカルフローを演算することを開始する。これにより上記演算プロセッサのキャッシュ容量、除算回路の面積及び処理サイクル数を従来技術に比較して、大幅に削減できる。これにより、演算プロセッサのハードウェアの低消費電力化、高速化、及び省面積化を行うことができる。従って、オプティカルフローの演算において、従来技術に比較してより短い演算時間で演算することができ、オプティカルフローの演算プロセッサを構成したときにそのハードウェアを大幅に小型化できる。
【図面の簡単な説明】
【００６６】
【図１】本発明の第１の実施形態に係るＯＰＦ演算プロセッサ２０の詳細構成を示すブロック図である。
【図２】図１のＯＰＦ演算プロセッサ２０によって実行される、オプティカルフローの演算において画像のウィンドウＢの稼働限定域１０１を設けることを示す画像フレーム１００の図である。
【図３】図１のＯＰＦ演算プロセッサ２０によって実行されるＰＬＫアルゴリズムによるオプティカルフロー演算処理を示すフローチャートである。
【図４】従来技術及び第１の実施形態に係るＯＰＦ演算プロセッサ２０のシミュレーション結果であって、各パラメータに対する平均絶対誤差ＭＡＥを示す図である。
【図５】従来技術及び第１の実施形態に係るＯＰＦ演算プロセッサ２０のシミュレーション結果であって、各パラメータに対する平均二乗誤差ＭＳＥを示す図である。
【図６】図１のＯＰＦ演算回路３０の構成を示すブロック図である。
【図７】図６の除算回路３２−１乃至３２−４（３２）の構成を示すブロック図である。
【図８】従来技術に係るパイプライン処理におけるＯＰＦ演算プロセッサの各演算回路の演算タイミングを示すフロー図である。
【図９】第１の実施形態に係るウィンドウインターリーブ法を用いたパイプライン処理における図１のＯＰＦ演算プロセッサ２０の各演算回路の演算タイミングを示すフロー図である。
【図１０】従来技術に係るオプティカルフロー演算における画素順序の演算方法を示す図である。
【図１１】本発明の第２の実施形態に係るオプティカルフロー演算における第１の画素順序の演算方法を示す図である。
【図１２】図１１の第１の画素順序の演算方法（Ｌ＝３のとき）を示す図である。
【図１３】図１１の第１の画素順序の演算方法（Ｌ＝４のとき）を示す図である。
【図１４】本発明の第２の実施形態に係るオプティカルフロー演算における第２の画素順序の演算方法を示す図である。
【図１５】本発明の第２の実施形態に係るオプティカルフロー演算における第３の画素順序の演算方法を示す図である。
【図１６】本発明の第２の実施形態に係るオプティカルフロー演算における第４の画素順序の演算方法を示す図である。
【図１７】本発明の第２の実施形態に係る第１のオプティカルフローの伝搬方法を示す図である。
【図１８】本発明の第２の実施形態に係る第２のオプティカルフローの伝搬方法を示す図である。
【図１９】本発明の第２の実施形態に係る第３のオプティカルフローの伝搬方法を示す図である。
【図２０】従来技術に係るオプティカルフローの演算における階層化を示す図である。
【図２１】従来技術に係るオプティカルフローの演算におけるフィルタリングの一例を示す図である。
【図２２】従来技術に係るＰＬＫアルゴリズムによるオプティカルフロー演算処理を示すフローチャートである。
【符号の説明】
【００６７】
１０…ＣＰＵ、
１１…画像メモリ、
１２…演算結果データメモリ、
１３…インターフェース、
１４…ディスプレイ、
２０…ＯＰＦ演算プロセッサ、
２１…シーケンスコントローラ、
２２…アドレス発生器、
２３…フレームＡメモリ、
２４…フレームＢメモリ、
２５…ＰＩＣ演算回路、
２６…階層化画像Ａメモリ、
２７…階層化画像Ｂメモリ、
２８…ＳＧＭ演算回路、
２９…ＭＭＶ演算回路、
３０…ＯＰＦ演算回路、
３１…３２ビット乗算回路、
３２−１乃至３２−４…除算回路、
３３，３７…マルチプレクサ、
３４，３５…レジスタ、
３６…減算器、
１００…画像フレーム。
【図１】
0004662969.tif 000006
【図２】
0004662969.tif 000007
【図３】
0004662969.tif 000008
【図４】
0004662969.tif 000009
【図５】
0004662969.tif 000010
【図６】
0004662969.tif 000011
【図７】
0004662969.tif 000012
【図８】
0004662969.tif 000013
【図９】
0004662969.tif 000014
【図１０】
0004662969.tif 000015
【図１１】
0004662969.tif 000016
【図１２】
0004662969.tif 000017
【図１３】
0004662969.tif 000018
【図１４】
0004662969.tif 000019
【図１５】
0004662969.tif 000020
【図１６】
0004662969.tif 000021
【図１７】
0004662969.tif 000022
【図１８】
0004662969.tif 000023
【図１９】
0004662969.tif 000024
【図２０】
0004662969.tif 000025
【図２１】
0004662969.tif 000026
【図２２】
0004662969.tif 000027