計測自動制御学会東北支部 第 280 回研究集会（2013.5.29）
資料番号 280-10

テンプレートマッチングにおける動的なテンプレート生成
ー統計的な評価関数に基づく遺伝的アルゴリズムによる方法
adaptive template generation in template matching- The method by the genetic algorithm based on a statistical valuation function○二瓶俊彦，萩原義裕，萩原由香里，三好扶,アデルジャンイミティ○Toshihiko Nihei,,Yoshihiro Hagihara, Yukari Hagihara, Tasuku Miyoshi, Adiljan Yimit
岩手大学
Iwate University
キーワード:テンプレートマッチング(template matching),対応点探索(corresponding point search),
カイ二乗分布(chi-squared distribution),遺伝的アルゴリズム(genetic algorithm),オクルージョン(occlusion)
連絡先：〒020-5881 岩手県盛岡市上田 4-3-5 国立大学法人 岩手大学 工学部 機械システム工学科 萩原義裕，
TEL：(019) 621-6400，FAX.：(019) 621-6400，E-mail：dhag@iwate-u.ac.jp
1. 緒言
テンプレートマッチングは，入力画像上でテンプレート画像を走査させることにより、入力画像からテンプレート画像の位置や特徴点を検出する処理である．マッチングの精度を下げる原因として，オクルージョンや不良画素などの問題がある．この問題に対して，テンプレート画像と入力画像を比較し，輝度差の大きい画素を両方の画像から除外し，マッチングを行う方法が提案されている．しかし，対応点探索に応用した場合，画素を除外するしきい値が画像の変化に対応できず，情報量の過不足が生じるため正しいマッチングができなかった．つまり，不良画素を除外するだけでなく，最適なテンプレート画素数を選択しながら対応点検索を行うことで探索精度の向上が期待できる．そこで，我々は確率的性質を考慮したテンプレートマッチングを提案した 1)．
本研究では，残差の確率的性質に基づき探索対象画像ごとに最適なテンプレート画素数とテンプレート形状を自動的に決定する方法について述べる．
我々の手法は，残差の分布が  2 分布に近似できる 2)ことに着目し，探索対象ごとに最適なテンプレートサイズを求めるものである．しかし，テンプレートのサイズを決定するだけでは複雑なオクルージョンに対応することができない場合が当然存在する．テンプレートの形状を変更することができれば，より高精度な対応点推定が可能になることは予想できるが総当たりで画素を選ぶのは当然不可能である．本稿では，遺伝的アルゴリズム（以下，GA）を利用しテンプレー
ト画像内の各画素を，マッチングを行う際に有効，無効を判定することによってテンプレート形状を最適化する手法について述べる．さらにこの手法に基づいて，実画像を用いて有効性を検証した結果について述べる．
2. テンプレートマッチングと残差分布
2. 1 テンプレートマッチング
テンプレートマッチングは 2 枚の画像の類似度を判定するものである．対応点探索による位置決めや特徴点の検出等に有効な手段であり，様々な分野での応用が期待されている．
テンプレートマッチングにおける類似度の主な評価法の一つとして残差法があり，計算処理が少ないことから立体視においては有効とされている．残差 J は式(1)のように表される．
n2J    xi  yi 

画素数である．
残差 J の値は 0 から 2552 n 2 の間をとり，0 に近いほど類似2度が高い．一般に，n が大きければ得られる情報量が多く，正確なマッチングが可能になるが，テンプレート画素数が必要以上に大きいとオクルージョンやゆがみなどの影響が大きくなり，精度が低下することもある．よって，テンプレート画像の選択が重要となる．
2. 2 残差分布の性質とモデル化提案された手法は，残差分布を解析して最適なテンプレートを選択するというものである．
テンプレートマッチングを行う際に用いるテンプレートの各画素の輝度差が独立であれば残差 J に対して J /  2 は自由度 n の  2 分布に従う残差 J の確率密度は式(2)になる
22)．

f (J ) 1

2

n (2J2

ここで  は残差分布の標準偏差を表す， 2 ( x) は自由度 n(1)i 02

ここで， xi , yi は各画素の輝度値， n はテンプレート画像の2nの  2 分布の密度関数であり，つぎの式(3)で与えられる．





xn2

n ( x )   e 2 x 22

1

  n2 / 2  n 2  /2

 2  (3)

(x) はガンマ関数である．この式を用いて残差分布を  2 分布で近似し，モデル化する．
2.3 確率的性質を利用したテンプレート画素数の取得
テンプレートと正しいマッチング位置における残差が未知であるとし，様々なサイズのテンプレートにおける残差分布を推定すると，テンプレート画素数以外にオクルージョンやゆがみなどの影響により異なる分布となる．その中で最も適した分布が分離度の高い分布を示す．正しいマッチング位
置では雑音がなければ残差は 0 であるが，未知の雑音の影響で  m 2 になると仮定する．その残差は 0 から  m 2 までとり得ると考えると，それ以外の位置でのマッチング結果の  m 2 以下の下側確率が小さいものが最もよく分離できるテンプレートであるといえる．  2 分布の下側確率 n ( x 2 ) は次式にて求めることができる．
2(2))

 n ( x 2 )  1   n ( x 2 )dx(4)x2

様々な画素数や形状のテンプレートにおいて，この値が最も小さいテンプレートを選択することによって，最も分離度が高いテンプレートでマッチングすることが可能となる．
なお，実際の残差の分布では，画素間に相関があるのでテンプレート画素数 n 2 と実際の自由度 n 2 の間には開きがある．そこで，実際の自由度 n 2 を残差分布から得られたサン
プル平均 ˆ J ，サンプル分散 ˆ J2 を用いて算出する 2)．

n  2ˆ J ˆ J(5)

これを式(2)の自由度 n 2 の代わりに用いて  分布を実際の残差分布に近似する．
3. 遺伝的アルゴリズムによるテンプレート形状の変形
GA とは生物の遺伝や進化をモデルにして発見的に解を探索するアルゴリズムである．最適化問題の解となる染色体をもつ個体を複数作成し，適応度と呼ばれる評価値によって淘汰が行われる．優れた個体を両親とした交叉や突然変異を一定確率で実行し，世代交代を繰り返すことで高い適応度をもつ個体（実用解）を得る 3)．
提案手法は，テンプレート形状の最適化が目的であるため，個体をテンプレート画像とし，染色体をテンプレート画像と同サイズの二次元配列で表し，1 と 0 で画像の有効，無効を判定する．Fig.1 は染色体(a)と個体(b)である．
適応度には前述した下側確率を利用する．下側確率の逆数を適応度とすることで，分離度の高いテンプレートが優れたテンプレートとされ，テンプレートマッチングを行うために有用な画素が次世代に残されていくことになる．
2(a)(b)
Fig.1 The model of (a) chromosomes and (b) individuals
画素数が多い場合，優れたテンプレートが世代交代の際に破壊され，解の収束が始まりにくくなることがある．そのため，世代で最も適応度が高かったテンプレートを次世代に残す，エリート保存戦略を組み込み，優秀な個体を残しやすくする 4)．
4. 実験
GA を用いてテンプレートの形状を変化させ，テンプレートマッチングを行った．まず，基礎実験として実験画像にはオクルージョンを作成し，GA によりオクルージョンに合わせたテンプレート形状の最適化が可能であるかを調べた．
次に，実際に撮影した画像を用いた対応点探索を行い，従来手法と提案手法を比較した．テンプレート画素数が 49，121，225，441，961 の 5 種類で固定された状態で対応点を探索する方法と，5 種類のテンプレート画像から下側確率が最小のものを選択する方法を提案手法に対する比較対象とした．提案手法は画素数 961 のテンプレート画像に対して，GA を適用することで画素サイズと形状を決定させた．

Fig.2 Experimental images

算出された対応点の正誤は，目視により判定した．Fig.2
は実験に使用したオブジェクトの移動画像である．
5. 結果と考察
GA を用いたテンプレートマッチングの実験の結果，作成されたテンプレートの一例を Fig.3 に示す．Fig3(c)のテンプレート画像から，Fig3(b)のオクルージョンに相当する部分が削除されている．前述のように，提案手法では適応度として下側確率を使用してテンプレートを評価する．したがって，さまざまなテンプレートの中からオクルージョン部分を利用するテンプレートは淘汰される．最終的に解となったテンプレートはオクルージョン部分を持たない，が無効と判断されている Fig3(c)のようなテンプレートなる．逆にいえば，最終的に Fig3(c)のようなテンプレートが得られたということは，提案手法が有効に働いたことの証左といえる．

(a)
(b)
(c)
Fig.3 (a)A conventional template image(b)A template image form GA method (c)A corresponding images
比較実験の結果，従来手法に比べて GA を利用した提案手法の方が多くの場合でふたつの従来手法よりも高い正解率を示した．提案手法は従来手法の概念を完全に含み，さらにこれを拡張したものである．従来手法のうち，最適なテンプレートサイズを選択する手法とより提案手法の正解率が優っているのはそのためであると考えられる．
探索範囲内にオクルージョンがあった場合，GA を用いない提案手法では多くの不正解が確認された．オクルージョンに対しては GA を用いた提案手法によりテンプレート形状を変えることで正解率が向上した．つまり，テンプレート画像の大きさだけでなくオブジェクトに合わせて相違部分の画素を除外することが精度の向上に有効であると考えられる．
6. 結言
残差の分布が  2 分布に近似できるという確率的性質を考慮し，探索対象画像ごとに適切なテンプレート画素数とテンプレート形状を選択する手法の有効性を検証した．
実画像を用いて従来手法と提案手法を比較した結果，Fig.2の画像においては提案手法が従来手法より良好な結果を示した．オクルージョンがあった場合は，GA を用いてテンプレート形状を変えることで精度の向上を図ることができた
今後の課題は処理の高速化である．
7. 参考文献
1) 萩原義裕, 及川慶紀, 萩原由香里, アデルジャンイミテ
ィ, 三好扶, 西川尚宏, ”適応的なテンプレートサイズによるイメージマッチング”画像電子学会誌, Vol.40,No.4, pp.631-641, July.2011.
2) 金谷健一, 金澤靖, ”テンプレートマッチングによる対応探索の自動しきい値設定法”信学論, Vol.J86-A, No.12,pp.1-8, Dec.2003.
3) 安居院猛, 長尾智晴, C 言語による画像処理入門, 昭晃
堂, 187-212, (2002)
4) 北野宏明, 遺伝的アルゴリズム,人口知能学会誌 vol7
No1,pp33(1992)