平成7年度 研究報告 大分県産業科学技術センター

カラー画像テンプレートマッチングとその高速化
佐藤辰雄
機械電子部

Template−matChinglI−COioトimage）andits臨stalgorithm
TatsuoSATO
Mechanics＆EleetroniesDivision

要旨
テンプレートマッチングは，何らかの方法により画像間の距離を定義し，どれだけ近いか（一致しているか）を調べるもので，その手法としては正規化相関が良く知られている．また，この手法はあらかじめわかっているマークなどを用いれば位置合わせを可能にするため，印刷などの用途での位置合わせに多く実用されている．ところがこの正規化
相関は白黒画像について定義されており，例えば金属の表面などのように濃淡の微妙な場合にはうまく行かないことが多い．
この問題を解決すべく，性能向上や適用範囲の拡大をするためには，限られた解像度で情報量を多くする意味からカラー画像への拡張が有効と考えられる．そこで本研究では，正規化相関を多次元に拡張することでカラー画像に適用し，実験でその有効性を確かめた．
また，正規化相関は計算量が非常に多いため，処理が遅いという問題がある．この点についてその高速アルゴリズムについても検討し，そのいくつかについて実験して，高速化の見通しを得た，

1．はじめに係数〉はよく知られている．

一方入力に用いられるCCDの画素数などによって制画像処理やパターン認識は自動化装置や無人監視約された解像度の範囲でマッチング精度や対象物の適のためのセンサとして産業ニーズは非常に高くなってお用範囲を改善するには，入力の情報量を何らかの方法り，また市販の装置も様々に開発されてきている．そので増やす必要がある．

中でもテンプレートマッチングは古くから研究されてきており，いろいろな手法がある．

その方法の一つにカラー画像が考えられる．しかし正規化相関はそのままではカラー画像には適用できない．

はじめの頃は取り込んだ画像を2値化し，2値画像のカラー画像とモノクロ画像との本質的な違いを考えると，上でマッチングが行われていたが，現在では半導体やモノクロ画像はスカラー量の2次元マップであるが，カLSIの技術とマイクロコンピュータの進歩に伴いハードラー画像は（r，g，b）3次元のベクトルの2次元空間マップ

ウェアもソフトウェアもローコスト化してきたため，また実であることがあげられる．そこで本研究では正規化相関際に使ってみると対象物と背景とをうまく分離するようなの手法を多次元に拡張しカラー画像への適用をはかっ2値化ができなかったり環境が少し変わっただけで照明た．

やスレッショルドなどを調整し直したりといった厄介な問

これによりモノクロ濃淡画像では照明や光学フィル題をさけるため，さらにマッチング精度や適用範囲の改ターなどを工夫しなければならなかったり，それでもコン善のため，モノクロの濃淡画像を使うことも多くなってき

トラスト比が低くてうまくマッチングがとりづらい様な場面た．またその応用分野としては位置決めや探索の用途で，もし色が違ってさえいれば適用可能となる．その意がもっとも一般的なようである．

味で適用範囲が広がると考えられ，またカラー画像を使実現手法はいろいろなものが提案1）2）されているが，そのなかでも相互相関に基づく正規化相関（相互相関うことで情報量が増えることからマッチングの精度の改善も期待できる．

鵬13綱

平成7年度 研究報告 大分県産業科学技術センター

2．テンプレ鵬卜∇ツテンゲ

3．実験と結果
実験は画像取り込みボードを付加した汎用ワークス

テンプレートマッチングは，入力パターンと、あらかじめ記憶してある標準パターンとを重ね合わせ、最もよくテーションにCCDカメラを接続したものを使い，カメラを一致する入力パターンを調べる手法である．

屋外の景色を撮影するように固定して640×480画素の画像を午前中1枚午後1枚の計2枚取り込み，最初の一一致の度合いを表現するためには。ノ〈ターン間の距離を定義する必要があり，ユ…

クリッド距宗匡を用いる場

枚からその一部（30×30画素）を切り出してテンプレートとし〉もう一枚の画像の中で一致する場所を探して∴切合や，マハラノビス拒軽を用いる方法などが検討されてり出したテンプレートの座標と一致するかどうかを調べきた，それらの一つに∴正規化相関がある．

ナナ
午前中はよく晴れており，午後は薄曇りとなったので，2．1正規化相関

見かけ上はほぼ同じ写真のように見えるが，明るさやコ正規化相関は，ノミターンとしては画像そのものを直接ントラストなどの面で少し異なっていると思われる．

扱う方法であり，白黒濃淡画像や2値画像について定また（3）式では正規化相関の値が負の値を取ることが義されている。
いま一画面の座標を（揖，V）でクまた重ね合わせる位置あるが，これはちょうどネガ画像とのマッチングに相当し、を（U，V）で表し，入力画像を∫（以，V），テンプレ十、画て0にした．その方がマッチング結果を画像表示すると像をg（㍍，V）とすると，正規化相関はきに見安い写真が得られたためである．探索手法につ

負の値はこの実験では必要ないので負になったらすべ

いては今回は特に考えず，単純に一番大きなスコアが：二：：二二・・− −・

得られた点の座標を凰潰しに調べる方法を採った．

∑∑u■（ ＋ぴ，…ソト毎十Lr，t・＋り〉：

実験に使った画像の例を図1に，カラー画像による、iマッチング結果を図2に，同じ画像を白黒に変換して，従来の正規化相関を行った結果を図3に示す。と表される．

またこれらについての探索結果はすべて切り出した点の座標値と同じになっており，マッチングは良好であ2．2カラー化ると考えられる．

このように定義された正規化相関の手法をカラー画像に適用するには何らかの拡張が必要である．ここではカラー画像のデータ表現に着目し，多次元への拡張を試みた．

カラー画像ではそれぞれの画素の値は三原色の明るさで表されている．そこでこれらをまとめればベクトルとして表現できる．すなわち∫（毘，V）…（r（揖，γ），g（揖，V），わ（毘，V））（2）

これを（1）式に適用すればよい．ここでベクトルの積は内積をとることにする．すると正規化相関は次のように表せる、

図1テンプレート画偉（図中の赤い枠はテンプレー∑∑徳（勘再一宮（ ，V）〉・く′頼＋ぴ，V＋V）−f（〟＋L′，t，・V）〉∑∑lg（′樟ト音（〟，tりl2

トとして切り出した部分，〉∑∑匪両廿勅」（￡汗U，t・十V）ま三（3）−14−平成7年度 研究報告 大分県産業科学技術センター∧「−1

X（た）＝∑ズ（円価悪，友＝0，i，‥・，Ⅳ−1／7＝0

ズ（れ）＝Ⅳ【王∑x（た）附ん，閃＝軋…，Ⅳ−iーノ拗／∧7）

Ⅳ」＼「＝ピ∴この変換を高速に実現するアルゴリズムの一つがFFTである．高速アルゴリズムはこの他にもいくつかが知られている．

図2 カラー画像によるマッチング結果

このFFT（DFT）を用いれば，次の手順で相関関数が高速に計算できる．

−−……−→＼−・−・−・き＿＿＿＿＿斗図卓 FFTを用いた相関関数計算手順

ヰ．3 放論変換（NTT〉

図3 白黒濃淡画像によるマッチング結果
DFTが複素指数関数の単位根を用いた変換として定義されるのに対して，NTTは1の原始ノV東根（整数）を用

4．高速化

いた変換で，すべての演算は整数を法として定義され4．1畳み込み（C￠〝y￠ん亡ゐ打）と相関関数（C￠〝拶由めの）る．

＼−！

相関関数と畳み込みは次のような関係である．

ガ（た）＝∑∬（めα玩（modP）／：＝し1㊥相関ゐ〃ズ′棚（7）ノV−】（4）ズ（乃）＝Ⅳ￣】∑x（克）α￣Å〃（modタ）◎畳込み簑ゐ〃ガト刀々＝0（5）

これを用いた畳み込みは次の手順で実現される。
，両者は入力数列のうちの添字式の符号が違うだけ。計算するときにその順番を逆順に並べ替えれば 同じアルゴリズムでよい

・従って相関関数は畳込み演算として計算できる

4．2高速フーリエ変換−…・・ゝ−−−、−−1−−ふ

醜聖ヶ百 ／

逆変換
ダ×G

F→G，ハt晶．，

図5 教諭変換による相関関数計算手順
その特徴は以下の通り．

離散フーリエ変換（DFT）は複素指数関数の単位根を用いて次のように定義される・丸め誤差が生じない。原始∧′乗根を2のべき乗にとれば乗算がシフト演算【15−平成7年度 研究部告 大分県産業科学技術センター．＼ l】に置き換えられ，高速になる．

y′（z）≡∑仇〜（z）ズト〝∫（z）mod（Z〃−1）。変換の長さを2のべき乗にとればFFT型のアルゴリ〝J＝0ズムが利用できて高速にできる．

．＼■一l仇（z）＝∑力叩′Z乃，∽＝0∵‥，Ⅳ一1・変換長を自由にとれず，演算語長によって変換長Ji＝tlが制限される．
・オーバフロー．＼■l一が重大な誤差となるため，ダイナミック方′（z）＝∑ガム・，rZ∫，r＝0，…，〃−1レンジの制約がきつい．

、＼＝し）

（9）

①〟8′ぶ8〃冊数変換

Jけer脚刀e数（2クー1，グ：素数）を法とするNTTをここでヅ〟，Jは八個の多項式ノけe′，∫eJ7／7e数変換と呼ぶ．

〃−1y∫（z）＝∑プ〟．′Z〟，g＝0，…，Ⅳ−1（10）その特徴は以下の通り．

〟＝0●（2クー1）を法とする演算はよく知られた1の補数演からz〟の係数として得られる・算であり，2進ハードウェアで容易に実現できる．

ここでこの計算のために，P（z）を法とした多項式演算

・FFTのような高速アルゴリズムが無い．に基づく多項式変換を定義する．

・pビットの場合，βと2βの2種類の変換長しかとれない．

ノ′−1

吏員（z）≡∑ガレ（z）rÅ modP（z）ゑ＝0，…，クー1②Fe′爪∂f数変換（FNT）′＝しlFe′・m∂∫数（22′＋1）を法とするNTTをFeノー爪βr数変

ズ】．r（z）≡Xr（z） mod P（z）
（11）換と呼ぶ．
同様に逆変換は③複素数論変換
拡張体Gダ（留2）上での数論変換を複素数論変換

ガレ（z）≡音ん（z）z一正

modP（z），と呼ぶ．
￣戒…（〝￣1）￣rたzz

r＝0，。‥ ，ダー1

④疑似放論変換（12）

疑似傭r甜〃乃e数2〝−1，p：合成数や，疑似Fe′−爪∂J数（2し■＋1，V≠2′）を法とする数論変換を疑似教諭変換と呼ぶ．

で定義される．
このときサイズク×グの二次元畳込みは次のように計算される．

ヰ．4 多項式変換

多項式を法とする多項式の演算は環をなし，多項式環と呼ばれる。数論変換を多項式環上の演算に基づいて拡張したとき，これを多項式変換と呼ぶ．
サイズ〃×Ⅳの二次元巡環畳み込み，
ノV−Ⅰ∧′−！

プ〟，∫＝∑∑れ溝−れ，ト〝ヱ 昆，g＝0，…，Ⅳ−i〝5＝0習＝0（8）がある時，次のように多項式代数で表現すれば一次元多項式の畳み込みと見なせる．

−16−

平成7年度 研究報告 大分県産業科学技術センター

変位量に従って単調に減少する．したがって，相互相関も，マッチング点の近傍ではほぼ単調に減少すると考えられる．

このことから，マッチング点の近傍では直線近似可能で，下図のようなあてはめを行い，その頂点の位置をサブピクセルサイズの分解能で求めればよい．

この点の座標をサフセルサイズで求める．
図7サブピクセルサイズでの位置探索手順

6．まとめと今後の課題①正規化相関を拡張してカラー画像に適用し，白黒画像の場合より性能が優れていることを確認した．

②相関関数の高速計算アルゴリズムについて，FFT法，数論変換，多項式変換等研究し高速化を確認した‥③ 実験の結果，FFT法で約5倍の高速化が確認でき・＼・

図6 多項式変換を用いた相関関数計算手順た．

④ 多項式変換では多くのアルゴリズムがあり更に高速にするため他のアルゴリズムを研究する
4．5実験と結果⑤実用化のためサブピクセルサイズ位置探索について研究する

実験は，これまでと同じ画像について行い，計算時問を計測した。ただし，カラー画像については，プログラム作業が間に合わなかったため白黒画像で行った．

なお，本研究は大分県地域人材不足対策技術開発研究事業の中で行ったものである。

その結果，計算時間は以下の通りとなり，高速化できることが確認された．

参考文献

表1計算時間比較
FFTを用い 多項式変換た計算
逐次計算を用いた計算 21分51秒 4分7秒 （未計測）1）佐藤辰雄，阿南正明：′′ヵラー画像のテンプレート
マッチング′′，信学技韓，PRしJ94−47（1994−10）
2）佐川雅彦，貴家仁志： 高速フーリエ変換とその応用′′，昭晃堂，（1993）

5．サブピクセルサイズでの位置探索

3）佐藤辰雄，三浦喜穂孝，遠藤勉： 正規化相関の高速計算法に関する検討 ，電子情報通信学会
1996年総合大会，（1996−3）

自己相関関数は偶関数で，変位量が小さい範囲では−17−