画像処理ボード上での高速テンプレートマッチングの実装と検証高性能計算研究室 B4 川本隆志 2005/2/24 １．研究背景・研究目的４．簡易テンプレートマッチングの設計２．実装ターゲットボードと設計環境５．高速テンプレートマッチングの設計３．テンプレートマッチングの定義６．ボード上での検証と性能評価 1 研究背景 • システムLSIの回路規模の拡大 • ハードウェア記述言語によるトップダウン設計 • フラットパネル・ディスプレイの需要の高まり – 市場規模 1998年：約100億ドル→2004年：約400億ドル（米DisplaySearchデータ）研究目的 • 産学共同研究におけるガラス外観検査装置の開発 • FPGAを用いた画像処理（テンプレートマッチング）の高速化 2 実装ターゲットボード（TSUNAMI） SRAM SDRAM External I/O Mezzanine I/O Card Altera Stratix FPGA SRAM SDRAM Local Bus Configuration PLD Address Decode PLD PLX PCI9656 Device PCI Bus 設計環境 • Altera社の統合開発環境ツールQuartusIIとシミュレーションツール ModelSimを使用 • ハードウェア記述言語VHDLで設計 3 テンプレートマッチングとは重ね合わせることにより比較照合対象画像テンプレート一致しているかどうかを判断設計したテンプレートマッチングの種類 • 簡易テンプレートマッチング – 一般的な定義に忠実な手法 • 高速テンプレートマッチング – 十字型の特徴に着目した、比較照合の少ない手法 4 簡易テンプレートマッチングの手法対象画像（2値化） …… 1画素ずつずらしながら切り出していく全ての画素に対して、対応する画素の差を取る切り出し部分テンプレート（2値化）画素毎の差を積算し、その部分の相違度とする 5 簡易テンプレートマッチングの構成対象画像： 1024x1024画素テンプレート：8x8 画素タイミングジェネレータ開始信号対象画像メモリアドレスジェネレータ一時メモリアドレスジェネレータ対象画像メモリ－一時メモリ制御ユニットテンプレートメモリアドレスジェネレータ 8ビットセレクタテンプレートメモリ結果アキュムレータマッチング座標最小相違度保持ユニットマッチング処理ユニット 6 改良アルゴリズムを用いた高速化（１） • マッチング処理の回数を減らす 7 改良アルゴリズムを用いた高速化（２） • 切り出す回数を少なくするマッチング部分に近づいている可能性があるときだけ少しずつずらす大きくずらしながら切り出すことで比較照合の回数を少なくする 8 高速テンプレートマッチングの構成対象画像： 1024x1024画素 SRAM テンプレート： 32x32画素レジスタ FPGA外部レジスタ FPGA内部レジスタレジスタ結果書き戻しユニット開始信号タイミングジェネレータ SRAM リ－ドアドレスジェネレータ相違度計算ユニットワードセレクタブロックセレクタ一時メモリ制御ユニットテンプレートメモリ結果アキュムレータマッチング座標最小相違度保持ユニットマッチング処理ユニット 9 終了信号ボード上での実装と検証の方法 QuartusII ホストPC 回路構成情報 TSUNAMI専用API 回路構成情報開始信号レジスタ FPGA 終了割り込み信号画像マッチング座標マッチング座標画像 SRAM TSUNAMIボード 10 実行クロック数の比較と性能評価 • TSUNAMIボード上での正常な動作を確認実行条件マッチング候補数 1個 2個 3個 4個 5個 6個簡易版C プログラム 39,480,000 39,480,000 39,480,000 39,480,000 39,480,000 39,480,000 高速版C 高速版VHDL 高速版VHDL プログラム（シミュレーション）（TSUNAMI） 167,132 34,898 270,246 277,810 44,042 464,103 384,440 68,354 685,894 489,132 77,498 868,199 576,184 89,898 1,078,680 676,816 99,042 1,249,433 • 簡易Cに対して高速Cが最小で約236分の1 • 高速Cに対して、VHDLシミュレーションの結果が最小で約7分の1だが、 TSUNAMI上での結果は最大で約1.9倍となった – TSUNAMIボード上のSRAMの1回のリードアクセス（32ビット）に10クロック程度もかかることが原因ボードに依存しない部分の高速化についてはソフトに対して数倍の性能向上が得られた 11 まとめ • ガラス外観検査装置の開発のためのテンプレートマッチングの設計 • 改良アルゴリズムによる高速化 • 高速テンプレートマッチングのFPGA上への実装と検証・性能評価今後の課題 • 画像サイズが可変の場合に対応させる • アフィン変換の機能を追加 12