画像処理ボード上での 高速テンプレートマッチングの 実装と検証 高性能計算研究室　B4　川本隆志 2005/2/24 １．研究背景・研究目的 ２．実装ターゲットボードと設計環境 ３．テンプレートマッチングの定義 ４．簡易テンプレートマッチングの設計 ５．高速テンプレートマッチングの設計 ６．ボード上での検証と性能評価

研究背景 研究目的 システムLSIの回路規模の拡大 ハードウェア記述言語によるトップダウン設計 フラットパネル・ディスプレイの需要の高まり 市場規模　1998年：約100億ドル→2004年：約400億ドル（米DisplaySearchデータ） 研究目的 産学共同研究におけるガラス外観検査装置の開発 FPGAを用いた画像処理（テンプレートマッチング）の高速化

実装ターゲットボード（TSUNAMI） 設計環境 Altera Stratix FPGA SRAM SRAM SDRAM SDRAM External I/O Mezzanine I/O Card Local Bus Configuration PLD Address Decode PLD PLX PCI9656 Device PCI Bus 設計環境 Altera社の統合開発環境ツールQuartusIIとシミュレーションツールModelSimを使用 ハードウェア記述言語VHDLで設計

テンプレートマッチングとは 設計したテンプレートマッチングの種類 簡易テンプレートマッチング 高速テンプレートマッチング 重ね合わせることにより比較照合 テンプレート 対象画像 一致しているかどうかを判断 設計したテンプレートマッチングの種類 簡易テンプレートマッチング 一般的な定義に忠実な手法 高速テンプレートマッチング 十字型の特徴に着目した、比較照合の少ない手法

簡易テンプレートマッチングの手法 …… 対象画像（2値化） 1画素ずつ ずらしながら 切り出していく 全ての画素に対して、対応する画素の差を取る 切り出し部分 1 1 1 1 1 テンプレート（2値化） 画素毎の差を積算し、その部分の相違度とする

簡易テンプレートマッチングの構成 対象画像 メモリアドレス ジェネレータ 対象画像 メモリ 8ビット セレクタ － 一時メモリ アドレス 対象画像：1024x1024画素 テンプレート：8x8画素 対象画像 メモリアドレス ジェネレータ 対象画像 メモリ 8ビット セレクタ － 一時メモリ アドレス ジェネ レータ 一時メモリ タイミング ジェネ レータ 結果 アキュムレータ 開始信号 マッチング座標 制御 ユニット 最小相違度 保持ユニット テンプレート メモリ アドレス ジェネレータ テンプレート メモリ マッチング処理ユニット

改良アルゴリズムを用いた高速化（１） 111......111 ???......??? 明らかに マッチして いない マッチング処理の回数を減らす マッチング処理を 行う 中央のラインの いずれかのビットが1 111......111 ???......??? 切り出し部分 明らかに マッチして いない マッチング処理を 行わない 中央のラインの 全てのビットが0

改良アルゴリズムを用いた高速化（２） 対象画像 切り出す回数を少なくする マッチング部分に 近づいている可能性が あるときだけ 少しずつずらす 対象画像 切り出し部分 大きくずらしながら 切り出すことで 比較照合の回数を 少なくする 1 1

高速テンプレートマッチングの構成 SRAM 開始信号 対象画像：1024x1024画素 テンプレート：32x32画素 FPGA外部 レジスタ レジスタ FPGA内部 レジスタ レジスタ 結果書き戻し ユニット 終了信号 マッチング座標 相違度 計算ユニット SRAM リ－ド アドレス ジェネ レータ タイミング ジェネ レータ ワード セレクタ 結果 アキュムレータ ブロックセレクタ 開始信号 一時 メモリ 最小相違度 保持ユニット 制御 ユニット テンプレート メモリ マッチング処理ユニット

ボード上での実装と検証の方法 ホストPC ④ ⑥ ② ③ ⑦ ⑤ TSUNAMIボード QuartusII ① TSUNAMI専用API 回路構成情報 TSUNAMI専用API ④ ⑥ ② ③ ⑦ 開始 信号 終了割り込み信号 回路構成情報 画像 マッチング座標 FPGA マッチング座標 SRAM レジスタ 画像 ⑤ TSUNAMIボード

実行クロック数の比較と性能評価 ボードに依存しない部分の高速化についてはソフトに対して数倍の性能向上が得られた TSUNAMIボード上での正常な動作を確認 簡易Cに対して高速Cが最小で約236分の1 高速Cに対して、VHDLシミュレーションの結果が最小で約7分の1だが、TSUNAMI上での結果は最大で約1.9倍となった TSUNAMIボード上のSRAMの1回のリードアクセス（32ビット）に10クロック程度もかかることが原因 ボードに依存しない部分の高速化についてはソフトに対して数倍の性能向上が得られた

まとめ 今後の課題 ガラス外観検査装置の開発のためのテンプレートマッチングの設計 改良アルゴリズムによる高速化 高速テンプレートマッチングのFPGA上への実装と検証・性能評価 今後の課題 画像サイズが可変の場合に対応させる アフィン変換の機能を追加