計測自動制御学会東北支部  周年記念学術講演会
 年  月  日， 日 日本大学工学部

講演番号：C05

オプティカルフローの実時間検出システム○福士将 

堀口進 （東北大学）

                                                                         Æ             !                           Æ                  !                        !                 "#$%                  &''&''    (')!         * +    !     *      * "#$%

 まえがき動画像から運動物体の速度情報を計測する研究は，工学や医学をはじめ多くの分野で行われている．例えば，気流等の可視化された流れ場の解析や，臓器や血管中の血流の解析等がある．また，計測された速度情報を利用した，監視システムや物体追跡の研究が盛んに行われており，近年では，ロボットビジョンやオートナビゲーションにおいて，知能情報処理の研究も行われている．
一般に，観測者と物体の間の相対的な運動によって生じる画面上の見かけの速度ベクトル場は，オプティカルフローとして知られている．オプティカルフローの計算法はこれまで数多く提案されており，それらは，
 ら  の分類によると，勾配法，ブロックマッチング法，エネルギーに基づく方法，位相に基づく方法の  種類に大別されている．いずれの手法においても，一般に，オプティカルフローの検出にはリアルタイム処理では許容されないほど時間がかかるため，リアルタイム性が要求されるアプリケーションでは，専用ハードウェアによる処理の高速化が不可欠となる．
   ら   は，  個の （   ）が集積された画像処理チップを  個用いて，空間的局所最適化法  によりオプティカルフローを検出するハードウェアを開発した．小室ら  は，ロボットビジョン向けに，センサと  を一体化した超並列ビジョンチップを開発し，探索領域を制限したブロックマッチング法により  のフレームレートでオプティカルフローを計算可能なことを報告している．近年，  ら  は， !   というパイプラ
イン画像処理プロセッサを用い，専用命令により空間的局所最適化法の高速化を行っている．
本報告では，勾配法の一種として知られている空間的局所最適化法に注目し，並列パイプライン処理により高速計算が可能なプロセッサを提案する．また，"#$を用いてハードウェアとして試作実装した結果を報告する．空間的局所最適化法では，局所領域内での重み付き局所和の計算に多くの時間がかかる．そこで，隣接する局所領域間で途中の計算結果を再利用することにより処理時間の短縮を図る．提案するプロセッサは，61必要な局所領域のサイズに応じて計算並列度を変更可能であり，さらに多数の  による大規模並列処理への拡張も容易であるという特徴を持つ．
以下， 節で対象とする空間的局所最適化法を説明する． 節で本報告で提案するプロセッサの構成を説明
し， 節では，プロセッサを "#$ 上に実装し，回路規模や処理時間を評価した結果を述べる．最後に  節で本報告をまとめる．

 オプティカルフロー
 勾配法

勾配法は空間輝度勾配と時間輝度勾配，オプティカルフローの三者間の関係を表す拘束式を用いて，オプティカルフローを解析的に求める手法である．いま，時刻 においてフレーム上の点 % & の輝度値を  %  &とし，この点を含むある物体が，微小時間の間に移動したとする．移動の前後で物体上の点の輝度が不変であると仮定すると，次式が成立する．

'   '  ( %&ここで，)  は点 % & におけるフローベクトル  の 成分と  成分であり， )  は  方向)  方向の空間輝度勾配， は時間輝度勾配である．式 %& はオプティ 

カルフローの拘束式と呼ばれており，勾配法に属する手法で共通なものである．

空間的局所最適化法*+ と ,!  によって提案された空間的局所最適化法は，精度が良く，かつ計算量も比較的少ない手法として知られている ．この手法では，式 %& の拘束式を解くために，点 % & を中心とするサイズ  の局所領域   内ではフローベクトル  は一定であるという仮定をおく．この仮定の下で，次式で表される 乗誤差を最小にすることにより， を決定する．
(

¾% &%  '   '  &%&

ここで， % & は   の中心により大きな重みをかけるような重み関数であり，通常， 次元ガウス関数

xPE3PE3PE3...

PE2PE3PE3...

PE3...

PE2PE3PE3...

PE3...

PE2PE3PE3...

PE3...

PE2PE3PE3...

    %& %&  % &  

PE3...

...

PE2PE2PE1PE2PE2PE1PE2PE2PE1PE2PE2PE1PE2PE2...

...

PE1PE2PE2PE2PE3PE3...

phase3pIn1p8bit

In2式 %&) %& により点 % & における  が計算され，この計算を  フレーム内の全画素に対して繰り返す．さらに，この一連の計算をフレームレート（フレーム0秒）で繰り返し行う必要があるため，他の手法よりも計算量が少ないとはいえ，ソフトウェアによるリアルタイム処理は困難である．

18bit

g(j)
QIn3
In4

reg
mux%& -25bit

%5&  - オプティカルフロー検出プロセッサ65bit

 計算の削減

32bit

重み付けの計算を行方向と列方向に分解可能なことに着目して，近隣の局所領域間で途中の計算結果の再利用を図る． % & を 次元ガウス関数， %& を  次元ガウス関数とすると，たとえば   内における の計算は次式のように変形できる．

mux

 ¾



¾

%&

 ¾

% &  %  &bufreg
mux
bufbufg(i)%&reg%& -ただし，
 である．
ここで，式 %& の右辺の  ¾ % &  を， 列目の列方向重み付き局所和として Ü¾ % & で表す．"-  に示すように， (  とした場合，  で計算される  ¾ % &〜  ¾ %& は，隣接する   でも計算さÜÜれることが分かる．すなわち，重み付けを行と列方向に分解する場合，計算点の  座標のみを連続して変化させながら  を計算することにより，大部分の計算を削減することが可能である．これは   だけでなく，他の  ，  ，  ，  も同様にあてはまる．以降の記述を簡略化するために， ，  ，  ，  に対する 列目の列方向重み付き局所和も同様に  Ý¾ % &) Ü Ý % &)  Ü Ø % &)  Ý Ø % & で表す．

bufbuf%  &  %  & (PE3"- . 234/ !   3 -reg   (      %&( PE1...

が用いられる．最小 乗法により，式 % & を最小にする  は次式で与えられる ．

phase2...

"- . +!  /   ! +   !  -phase1

PE4...

mCS Ix 2 (1) CS Ix 2 (2) CS Ix 2 (3) CS Ix 2 (4) CS Ix 2 (5)

...

r



PE2

PE4

R ( x +1, y,5 )
(x,y)

PE4

...

R ( x , y,5 )...

phase4
...

y

mux
reg

reg%!& "- . 6++ 7 )  ) ) !  % .
   ) +. +3 ) 5+7. 5+8   9&"- に提案するプロセッサの構成を示す．計算処理のフェーズ毎にフェーズ 〜 の  つのブロックからなり，各ブロックは，"- %&〜%!& に示されるように，それぞれ構成の異なる複数の  からなる．各ブロックは直列に接続され，入力される輝度値のデータに対してパイプライン処理を行う．
このプロセッサは回路規模に関するパラメータとして  と  を持つ． はフェーズ 〜 のブロックに存在する  の行数であり，処理可能な局所領域の最大サイズを表す． はフェーズ 〜 のブロックに存在する
 の列数であり，並列に処理可能な最大行数を表す．

プロセッサの構成

本報告では，入力画像は 1 階調のグレースケールとし，各輝度値を 〜  の値をとる  ビット固定小数点形式で表す．また，計算精度を保つために，必要に応じてビット数を拡張するものとする．

各フェーズで行う処理を以下に示す．

62

654

3

2

1clockI (1,2 ,t )I (2,1 ,t )I (1,2 ,t )I (2,1 ,t )I (2,1 ,t )I (1,1 ,t )I (1,2 ,t )I (1,1 ,t )In1In2In3In4

I x I y (1,1 ,t )Q

I (1,1 ,t )I (1,2 ,t )I (1,1 ,t )I (2,3 ,t )I (2,2 ,t )I (2,3 ,t )I (2,2 ,t )I (1,1 ,t )I (1,1 ,t +1)
I (1,1 ,t )I (1,1 ,t )I (1,1 ,t +1)
I (1,1 ,t )I y (1,1 ,t ) 2

I x (1,1 ,t ) 2

I y I t (1,1 ,t )I x I t (1,1 ,t )I (3,2 ,t )I (2,3 ,t )I (3,2 ,t )I (3,2 ,t )I (2,2 ,t )I (3,2 ,t )I (2,2 ,t )I x (2,2 ,t ) 2I (2,2 ,t )I (2,2 ,t +1)
I (2,2 ,t )I y I t (2,2 ,t )I (2,2 ,t )I (2,2 ,t +1)
I (2,2 ,t )I x I t (2,2 ,t )I (2,2 ,t )I (2,3 ,t )I (2,2 ,t )1st PE1

2nd PE1I x I y (2,2 ,t )...

I y (2,2 ,t ) 2I (1,1 ,t )I (2,1 ,t )I (1,1 ,t )I ( r , r +1 ,t )I ( r , r,t )I ( r , r +1 ,t )I ( r , r,t )I y ( r , r,t ) 2

I ( r +1, r,t )I ( r , r,t )I ( r +1, r,t )I ( r , r,t )I x ( r , r,t ) 2

I ( r , r +1 ,t )I ( r +1, r,t )I ( r , r,t )I ( r,r,t +1)
I ( r , r,t )I ( r , r,t )I ( r , r,t +1)
I ( r , r,t )I y I t ( r , r,t )I x I t ( r , r,t )I ( r +1, r,t )I ( r , r,t )I ( r +1, r +1 ,t )I ( r , r,t )rth PE1I x I y ( r , r,t )"- . : 7 ! 3+フェーズ  空間輝度勾配  ， ，時間輝度勾配  を計算し，それらの積   )  )   )   ，  を計算する．
計算に必要なデータは図  に示すタイミングで各 に入力され， では減算と乗算を含めて  クロックで計算を行い，結果がレジスタに格納される．この処理は各  で独立して行う．各  では  クロック毎に   ，  ，  )   ， の順で計算が終了し，それらは順次フェーズ のブロックへと入力される．

データ数が多いために "-  には Ü Ø % & のみを示しているが，実際にはこの他に Ü Ø % &) Ý Ø % &) ¾ % &)  ¾ % & も続いて格納されている．
ÜÝフェーズ   種類の列方向重み付き局所和  Ü Ý % &)% &)  Ý Ø % &  Ü¾ % &) Ý¾ % & を計算する．
 行の  により，局所領域  行分の重み乗算と累算をパイプライン式に計算する． クロック後に  ÜÝ % &がフェーズ  のブロックへと出力され，以降，フェーズ
 での出力順に，Ü Ø % &) Ý Ø % &  Ü¾ % &) Ý¾ % &が  クロック毎に出力される．

 Ü Ø  )フェー ズ   種 類 の 重 み 付 き 局 所 和  )  ) )
 を計算する．
フェーズ で計算された列方向重み付き局所和の行方向重み付き局所和を計算する．この計算は，フェーズ と同様に， 行の  により重み乗算と累算をパイプライン式に計算することにより行う．
フェーズ のブロックから入力される列方向重み付き局所和は，近隣の局所領域の計算で再利用するために，各  のバッファメモリに格納される．局所領域のサイズを  (  とした場合の， 行目から   行目の 内のバッファに格納されるデータを "-  に示す．

mth PE3m-1th PE3m-2th PE3m-3th PE3m-4th PE3

g (1) CS IxIy (1)g (1) CS IxIy (2)g (1) CS IxIy (3)g (1) CS IxIy (4)g (1) CS IxIy (5)g (2) CS IxIy (1)g (2) CS IxIy (2)g (2) CS IxIy (3)g (2) CS IxIy (4)g (2) CS IxIy (5)g (3) CS IxIy (1)g (3) CS IxIy (2)g (3) CS IxIy (3)g (3) CS IxIy (4)g (3) CS IxIy (5)g (4) CS IxIy (1)g (4) CS IxIy (2)g (4) CS IxIy (3)g (4) CS IxIy (4)g (4) CS IxIy (5)g (5) CS IxIy (1)g (5) CS IxIy (2)g (5) CS IxIy (3)g (5) CS IxIy (4)g (5) CS IxIy (5)

納された時点で，  の計算に必要なデータが全て揃う．バッファメモリから加算器に入力するデータを適切に選択し，加算のタイミングを調整することで，%&Ü Ý %& が格納された次のクロックで  の累算を終了して，フェーズ  のブロックへと出力させることができる．以降， クロック毎に  )
  )
 ) の順でフェーズ  に出力される．

 



   行目の  のバッファに %& Ü Ý %& が格

ここで，隣接する点 % '  & での計算に必要な%&Ü Ý % & 等のデータはすでに各  のバッファに格納されているため，  行目の  に %&Ü Ý %1&が格納された時点で，点 % '  & での   が計算可能である．すなわち，点 % & での  種類の重み付き局所和の出力に引き続き，点 % '  & での出力が開始可能である．

重みの値は，局所領域のサイズが通常よく用いられる (  の場合， % & (        で近似できる 1．これらの値に適当な係数をかけても式 %&)%& の計算結果は変わらないため， % & (     の整数値を用いる．

 器は配列型除算器であり，データの入力から信号遅延分の時間で除算結果が求まる．
計算で必要とされる局所領域のサイズ  はアプリケーションにより異なる可能性があるが，本プロセッサでは最大  まで対応可能である．局所領域の  列を単位としてデータが入力されるため，点 % & での計算には，フェーズ  の  行の ，フェーズ と  の  行 列の ，そしてフェーズ  の  列の  が使用される．
決められた  に対して，プロセッサ内の  の行数が多い場合 %  &，フェーズ  の  行の  と，フェーズ 〜 の  列の  を利用して，隣接する点 %  '&での計算を行うことが可能である．すなわち，"に示すプロセッサでは，%)   ' & 行でフローベクトルを並列に計算可能である．

"- . ;  5+8   963% & 上でのフローベクトル  を計算する．
計算に必要なデータが  )
  )
  ) )
 の順で入力されるため，式 %&，%& に従ってフローベクトルを計算する． の 個の除算
フェーズ :5 . !/   7  3  5<     !         ,-. ,/0/0.
,1)!.
//'234
/3''&/
/(2( 30'0
'/2
2 5360
2'/320 /32/
&/6220  を用いた試作システムと評価
 実装環境

プロセッサのパラメータを  ( 1  (   (  として， ;* により "- に示したプロセッサの回路設計を行い，"#$ 上に実装した．本報告での実装環境を以下に示す．

"- 1.      7+ 7 7 /!% (  &:5 . 3  7  + 3+  ,1 7 8 .
9   :;/(//<  :6;/3&     /60/

 "#$ ボード. 2= %=$**$: 社&
 "#$ チップ. >  %> 社&
 設計ツール. ?6 1- %> 社&
 波形シミュレータ. ! 6 > -1%!  :  9 社&セッサは従来法よりも高いスループットを実現可能なことが分かる．

 と "#$ ボード間の通信機能は実装されていないため，プロセッサの動作確認は波形シミュレータから得られる出力波形により行った．
 まとめ

回路規模の評価

使用した回路設計ツールのレポートファイルにより，"#$ 内の使用リソース量を評価する．:5  は，
"#$ 内のスライス数と全スライス数に対する割合，
内蔵  ビット乗算器数，および，最大動作周波数を各フェーズ毎に示したものである．フェーズ  と  で多くのスライスを消費しているが，これは，それそれバッファメモリと配列型除算器を持つことが原因である．プ
ロセッサ全体の最大動作周波数は，約  - であるという結果が得られた．

 処理時間の評価
フレームサイズを   とした場合の処理に必要なクロック数を導出し，プロセッサの処理時間を評価する．画像フレーム上の各行頭の点では，データの再利用ができないために，フローベクトルが出力されるまで 1 ' @ クロックかかる．以降は  クロック毎に各点でのフローベクトルが出力される．これらの処理は
%  '  & 行で並列に行われるため，計算に必要クロック数は次式で表すことができる．

参考文献:/; 9 = > *  9 "   + + > * +  ?7 #       "  * @ A 9   <  B *  /*/*  2(4&&* /552
:; 1 9    1 $  * CB    #    "  <      = +@1% @B@#D* #    <   %     1  #    0'40&* /556:(; > =    E* C% @   @ F       % %     +  B D* #   %F#% @ G     * //4/('* /50/
:2; 小室 孝* 鈴木 伸介* 石井 抱* 石川 正俊* C汎用プロセッ
シングエレメントを用いた超並列・超高速ビジョンチップの設計D* 信学論 ,@.*  90/@*  * &'4&3*/550
:6; 1 B <   % < <  * CF   @          "  %   D* #   /3  @ A <   #  F   *  2*
 2'2(42'23* ''
:3; # 9 >  C" "       @ # D <   B   @ # *  /3*
 '46/* /50/( %1%'@''&&

本報告では，オプティカルフローの高速検出プロセッサを実現することを目的に，空間的局所最適化法の高速並列パイプライン処理法を提案し，ハードウェアとして "#$ 上に実装した．このプロセッサは，重み付き局所和の繰り返し計算において，計算結果を再利用するアプローチにより高速並列パイプライン処理を実現する．局所領域のサイズの変更にも対応でき，さらに，計算並列度を簡単に上げることができるという特徴を持つ．処理時間の評価により，サイズ A A のフレームを  で処理可能であり，さらに従来のプロセッサよりもスループットが高いことが示された．
今後の課題は，試作システムにおいて， と "#$間の通信プログラムを作成し，実画像データを処理させることである．

%1&

クロック周波数を  とすると， フレームあたりの処理時間は   となる．今回設計した  ( 1  (   ( のパラメータを用い， ( とした場合の処理時間を "- 1 に示す．=:6 のように  の処理を想定する場合， フレームあたりの処理時間が  以下であればよいため，実装したシステムではサイズ約A A 以下のフレームを処理可能である．
ここで，同じ空間的局所最適化法を採用している従来法  ， とスループットを比較する．従来法とスループットを比較する．:5
から，提案するプロ

64