[[FrontPage]]

*テンプレートマッチング法のパターンの変形に対する耐性の実験的評価 [#q78fe8d5]

#contents
*研究目的 [#p484ef62]
画像の中から特定の文字や模様といったパターンを検出する手法の一つにテンプレートマッチング法がある。

**テンプレートマッチング法とは [#mea7188a]
テンプレートマッチング法[3]とは、入力画像の中からテンプレート画像に似た画像パターンを探し出す手法である。どれだけ似ているかを評価値（類似度・相違度）で表し、評価値をもとに似ているかどうかを判断する。また、探す方法（計算方法）にはさまざまなものがあり、本研究では計算方法の比較・評価を行う。画像を検出する手法としてはSURF[1]のような画像変形に対して強い手法もあるが、テンプレートマッチング法は、処理が単純である・計算速度が速いという特徴を持つことから、ハードウェア性能が制限される環境では特に有用である。
#ref(templateMatching.jpg,center,50%)
CENTER:図1：テンプレートマッチング法のイメージ図

**本研究の課題 [#v589f260]
テンプレートマッチング法を用いる際には、探す画像パターンに変化が生じていた場合を想定して、どの程度の変化なら許容されるかを把握・評価しておく必要があるが、網羅的に実験を行い、評価を行った事例はほとんどなかった。そこで本研究では、代表的な5手法の画像変形に対する耐性を実験的に評価した。

*評価を行った5つの手法 [#u30ca3c8]
評価を行った手法は以下のものである。
-古典的な手法
--SAD(Sum of Absolute Difference)
---画素値の差の絶対値の和で評価値を求める
--SSD(Sum of Squared Difference)
---画素値の差の2乗の和で評価値を求める
--NCC(Normalized Cross Correlation)
---正規化相互相関
---明るさやコントラストに影響されない
-最近提案された手法
--ISC(Increment Sign Correlation)[4]
---増分符号相関
---部分的に起こる大きなノイズや遮蔽に強い
--SRF(Statistical Reach Feature)[5]
---統計的リーチ特徴法
---照明変動、遮蔽、撮影時のノイズに強い

*評価実験 [#r16690a7]
**評価実験の全体の流れ [#j4ec6f9f]
まず、背景画像（テンプレート画像と無関係な画像）とテンプレート画像でテンプレートマッチングを行い、評価値を得る。テンプレート画像ごとにたくさんの評価値が得られるが、この中から最大の評価値を選び、これをしきい値として保持する。次にテンプレート画像と、変形テンプレート画像（テンプレート画像を変化させ、ノイズを付加した画像）でテンプレートマッチングを行い、テンプレートの変形に伴う評価値の変化を求める。評価値の変化としきい値を比較し、正しくマッチングできる変化の範囲（許容範囲）を調べる。求めた許容範囲を各マッチング法で比較し、評価する。
#ref(exp-all.jpg,center,50%)
CENTER:図2：評価の全体の流れ図

**背景画像とテンプレート画像のマッチング（しきい値の計算） [#q4ac3bfe]
***背景画像とテンプレート画像のマッチングで得た評価値がしきい値として使えるワケ [#d51bdb25]
背景画像とテンプレート画像でテンプレートマッチングを行うと、テンプレート画像に似ている画像パターンがない場合の評価値が得られる。これを評価値(a)とする。一方でテンプレート画像と変形テンプレート画像でテンプレートマッチングを行うと、テンプレート画像の変形に伴う評価値の変化が得られる。これを評価値(b)とする。評価値(b)は変形度合に従って悪くなっていくが、このとき、評価値(a)(b)の関係は図3のようになるが、評価値(b) > 評価値(a)である間は正しくマッチングできると判断できる。このような考えのもとに、背景画像とテンプレート画像でテンプレートマッチングを行った結果の評価値をしきい値として使うことにした。
#ref(threshold-and-evalValue.jpg,center,70%)
CENTER:図3：評価値の変化としきい値の関係(横軸はテンプレート画像の変形度合、縦軸は評価値を表す)

***背景画像とテンプレート画像のマッチング方法 [#d0da5fc2]
背景画像とテンプレート画像でのテンプレートマッチングは図4のように行う。まず背景画像と各テンプレート画像でテンプレートマッチングを行う。それにより各テンプレート画像ごとにたくさんの評価値が得られるが、各テンプレート画像ごとに最大の評価値を選び出す。これらをしきい値として使う。
#ref(exp-background.jpg,center,50%)
CENTER:図4：背景画像とテンプレート画像のマッチング

***検出誤りを許容した場合のしきい値の計算 [#mac70ea8]
先ほど求めたしきい値は検出誤りを許容しない場合のしきい値（背景画像中の画像パターンを検出することがないように設定されたしきい値）である。しかし、多少誤検出を起こしても構わないからできるだけ変形テンプレート画像の検出を見逃すことは避けたい、という状況もある。そこで、検出誤りを許容した場合のしきい値も計算することにした。扱った検出誤り率は0%～5%(0.5%刻み)である。
**テンプレート画像と変形テンプレート画像のマッチング（許容範囲の計算） [#r969f367]
テンプレート画像と変形テンプレート画像のテンプレートマッチングは図5のような流れで行う。ここではテンプレート画像をT1、T2・・・とする。T1とT1の変形テンプレート画像、T2とT2の変形テンプレート画像というように、テンプレート画像と変形テンプレート画像でテンプレートマッチングを行う。これにより各テンプレート画像ごとに変形に伴う評価値の変化が得られる。次に評価値の変化と、求めておいたしきい値（検出誤りを許容しないしきい値、検出誤りを許容するしきい値）を比較し、各テンプレート画像ごとの変形の範囲を求める。これらの変形の範囲の平均を求め、この範囲の平均を各手法で比較を行い、評価する。
#ref(exp-template.jpg,center,50%)
CENTER:図5：テンプレート画像と変形テンプレート画像のマッチング

*評価実験で使用した画像 [#x999470b]

**テンプレート画像 [#m52f33c4]
検出すべき対象物となるテンプレート画像は図6、7のようなものを40枚用意した。これらの画像は、画像自体が意味を持つ「文字・標識」テンプレート画像群と画像自体が意味を持たない「模様・プリント基板」テンプレート画像群の2種類に分類した。本研究ではそれぞれのテンプレート画像群に対して実験を行った。
#ref(templateImages-cs.jpg,center,50%)
CENTER:図6：テンプレート画像（文字・標識）
#ref(templateImages-ti.jpg,center,50%)
CENTER:図7：テンプレート画像（模様・プリント基板）

**背景画像 [#p31b0ece]
背景画像は図8のような200枚の画像を用意した。これらの背景画像は町中、室内、森林、機械内部を撮影したもので構成されている。
#ref(backgroundImages.jpg,center,50%)
CENTER:図8：背景画像
**変形テンプレート画像 [#y00d7563]
許容範囲を求める際に使う変形テンプレート画像は、図9、10、11のようなものを用意した。倍率の変化は80%～120%で2%刻み、回転は0°～20°で2°刻み、台形変形は0°～50°で5°刻みとした。ここで、台形変形はある画像をカメラで撮影する際に、「正面から撮影するのか、それとも斜めから撮影するのか」を想定した変形である。
#ref(scale.jpg,center,50%)
CENTER:図9：倍率の変化

#ref(rotate.jpg,center,50%)
CENTER:図10：回転

#ref(trapezoid.jpg,center,50%)
CENTER:図11：台形変形

変形テンプレート画像にはさらに平均0標準偏差2のガウスノイズを付加した。実際の環境で画像を撮影すると、同じ位置、照明条件で撮影しても画像を構成する画素は多少変化する。これを再現するためにこのようなノイズを付加した。

*評価実験の結果・考察 [#g1a01d18]
**「文字・標識」テンプレート画像での結果 [#x57a43a1]
「文字・標識」テンプレート画像で評価実験を行った結果は、図12～15で示すとおりである。ここで、各図の横軸は各種変形の変形度合、縦軸は手法名となっている。ここで、SRFはTpという設定値があるので、Tp=1、20の場合で実験を行った。さらに各手法とも3つの棒グラフがあるが、これは上から検出誤りを許容しない場合、2.5%の検出誤りを許容した場合、5.0%の検出誤りを許容した場合を示している。この棒グラフが長いほど許容範囲が広い、画像変形に対して耐性があることを示す。

これらのグラフを見ると、各画像変形においてSAD、NCCが耐性があり、ISCが耐性が低いことがわかる。そしてこれは検出誤りを許容した際も同様の傾向を示した。
#ref(result-expansion-cs.jpg,center,80%)
CENTER:図12：倍率（拡大）
#ref(result-reduction-cs.jpg,center,80%)
CENTER:図13：倍率（縮小）
#ref(result-rotate-cs.jpg,center,80%)
CENTER:図14：回転
#ref(result-trapezoid-cs.jpg,center,80%)
CENTER:図15：台形変形
**「模様・プリント基板」テンプレート画像での結果 [#e7eae053]
「模様・プリント基板」テンプレート画像での実験結果は図16～18で示すとおりである。こちらの結果も、SAD、NCCが耐性があり、ISC、SRF（Tp=1）が耐性が低いという、「文字・標識」テンプレート画像での結果とほぼ同様のものとなった。
#ref(result-expansion-ti.jpg,center,80%)
CENTER:図16：倍率（拡大）
#ref(result-reduction-ti.jpg,center,80%)
CENTER:図17：倍率（縮小）
#ref(result-rotate-ti.jpg,center,80%)
CENTER:図18：回転
#ref(result-trapezoid-ti.jpg,center,80%)
CENTER:図19：台形変形

以上の結果から、SAD、NCCが画像変形に対して耐性があることが明らかとなった。さらに実験結果のグラフから、各手法の画像変形に対する許容範囲が明らかとなった。
*まとめ [#h8ae238d]
本研究では、テンプレートマッチング法の各手法の画像変形に対する耐性を実験によって評価した。評価実験の結果から、SADやNCCといった古典的な手法が画像変形に対して耐性があることが明らかとなった。また、各手法の画像変形に対する許容範囲も明らかとなった。この許容範囲のデータはマルチテンプレート（あらかじめ変形テンプレート画像を複数用意しておき、それらを使ってテンプレートマッチングを行うこと）を行う際に指標となる（[6]はマルチテンプレートを行った事例の一つである）。たとえば、NCCは回転において10°程度の許容範囲（文字・標識テンプレート画像の場合）があることが分かったので、倍の20°間隔で変形テンプレート画像を用意しておけばよいのではないか、という見当が付けられるようになる。

今後の課題としては、
-マルチテンプレートを実際に行い、本研究で得られた画像変形に対する許容範囲のデータがどの程度有効的かを検証する
-[2]のように画像のモデル化を行い、解析を行うことによって評価を行う

などが挙げられる。
*修士論文発表会で指摘された点 [#w7dd2b2a]
-この実験方法で得られた許容範囲がそのままマルチテンプレートに適応できるのか？（背景画像とのマッチングで得られた評価値をしきい値にするということで大丈夫なのか？）

→今回は、しきい値を求める際にテンプレート画像とは無関係な画像を使ったので、テンプレート画像に似た画像が存在する場合の状況は想定していない。このような状況を考慮するためには、テンプレート画像に似た画像パターンが存在するような画像を背景画像として用意しておく必要があると考えられる。
-テンプレート画像と変形テンプレート画像でマッチングを行う際に、対応する点（画素）との対応付けなどは考慮しないのか？

→本研究は、実際にテンプレートマッチングを用いる状況を想定した実験を行うことで画像変形に対する耐性の評価を行ったので、画素と画素との対応付けなどは一切検証していない。これは今後の課題で述べた「画像のモデル化を行い、解析を行うことによる評価」で検証すべき問題であると考える。
*参考文献 [#xfe9eba1]
[1]Herbart Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool, "SURF : Speeded Up Robust Features", Computer Vision and Image Understanding(CVIU), Vol.110, No.3, pp.346-359, 2008.~
[2]山田貢己, "変形した画像に対する相関マッチングのモデルとその対応点推定への応用", FIT(情報科学技術フォーラム)2003, LI-004, pp.165-167, 2003.~
[3]コンピュータ画像処理, 田村秀行(編著), オーム社, 2001.~
[4]村瀬一朗, 金子俊一, 五十嵐悟, "増分符号相関によるロバスト画像照合", 電子情報通信学会論文誌, D-II, Vol. J83-D-II, No. 5, pp. 1323-1331, 2000.~
[5]尾崎竜史, 佐藤雄隆, 岩田健司, 坂上勝彦, "統計的リサーチ特徴法によるロバスト画像照合", ViEW2008ビジョン技術の実利用ワークショップ, pp. 191-196, 2008.~
[6]朝岡峻一朗, "タンパク質の共焦点レーザー顕微鏡画像と電子顕微鏡画像のレジストレーション手法", 群馬大学工学部情報工学科卒業論文, 2009.~
[[【解説ページへのリンク】>2種類の顕微鏡画像によるレジストレーション手法]]

*学部4年次の研究ページへのリンク [#v801d820]
[[テンプレートマッチング法のパターンの変形に対する耐性の評価]]

*更新履歴 [#y70b484b]
2012/03/01 平野君からのアドバイスをもとに一部修正。~
2012/02/29 本ページ完成。今後は間違いを見つけ次第、修正する方針。~
2012/02/28 一通り記述完了。明日中に見直しして完成版とする予定。~
2012/02/21 本ページ立ち上げ。
トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS