画像の濃度共起情報に基づく画像照合のための参照画素選択手法

全文

(1)Vol.2009-CVIM-169 No.45 2009/11/27. 情報処理学会研究報告 IPSJ SIG Technical Report. 1. はじめに. 画像の濃度共起情報に基づく画像照合のための参照画素選択手法橋本学†. 奥田晴久††. FA（Factory Automation）や映像セキュリティをはじめとする多くの産業用画像処理の分野において，物体や変化検出のための画像照合は基本的な課題である．モデルと入力画像の類似度を画像間の画素同士の演算で求めるテンプレートマッチング [1][2][3]は，画像中の特徴的な部分の多寡によらず使用でき，基本原理が単純で実装しやすいことから，汎用的な物体検出手法として現在でもよく用いられている．基本原理としては，予め検出したい被写体を写した画像（テンプレート画像と呼ぶ）を準備しておき，入力画像に重ね合わせながら類似度が最大になる位置を決定する．この技術には多くの関連研究があるが，ほとんどは次の 2 つの目的に沿って分類することができる．一つめは照明変動などの外乱に対するロバスト性能の向上を目的とする研究であり，主として外乱下でも安定する類似度尺度が提案されている．例えば輪郭付近や隣接画素間の濃度勾配符号を用いる手法[4][5]は，勾配の符号を表現することにより濃度変化量が類似度に与える影響を抑制している．同様に，各画素の勾配方向をコード化して用いる手法[6]も濃度変化をあえて無視することで明るさ変動に対するロバスト性を持たせている．最近発表された統計的リーチ特徴法（SRF）によるマッチング[7][8] は，テンプレートを離散的な画素群として捉え，注目画素から放射状に伸ばした腕上の複数の画素対を用いることによって，従来の正規化相互相関法より濃度変化に対するロバスト性を向上させている．二つめの流れは，照合の高速化を目的としたものであり，基本的には類似度計算回数（探索回数）の削減に取り組まれている．古くは，異なる縮小率で段階的に解像度を変えたピラミッド画像を用いるいわゆる Coarse-to-Fine 探索に関する一連の研究 [9][10]がある．また類似度尺度として画像間の累積残差を利用する場合には，テンプレート画素のアクセス順序を制御して残差が増加する速度の向上を狙った手法[11]や，類似度計算の途中打ち切りをおこなう手法[12]，局所的な色ヒストグラムを利用する場合には現在の探索位置近傍での類似度計算を効果的に削減するアクティブ探索[13] などが提案されている．正規化相互相関を用いるテンプレートマッチングに対して SSDA のような打ち切りをおこなう手法[14][15]も提案されており，処理時間を左右する画素アクセス回数は全体の 1/10 程度に削減できている．一方，これらとは異なる高速化のアプローチとして，与えられたテンプレート画像から照合に実際に使用する画素（以後，参照画素と呼ぶ）を厳選してデータ数を削減. 鷲見和彦††. 本稿では，テンプレート画像を入力画像と照合する問題において，照合の高速化を目的とし，１枚のテンプレート画像のみを使用してその中から照合に有効な参照画素をできるだけ少なく選択する手法を提案する．安定した照合のためには特徴的な空間配置を持つ画素群を選択することが重要であると考え，一定の位置関係にある複数画素からなる局所パターンの濃度発生頻度を表現した共起ヒストグラムを利用する．共起ヒストグラムは画像全体における当該パターンの発生確率に相当するので，確率が低いパターンを優先的に参照画素として選択する． 4 種類×120 枚のテスト画像による実験により，参照画素数を元のテンプレート画像の全画素数の 0.4～1%に削減しても認識成功率が低下しないことを示した．. A Selection of Reference Points based on Co-occurrence of Multiple Pixels in Template Matching Manabu Hashimoto† Haruhisa Okuda†† and Kazuhiko Sumi†† We propose a method to select very small number of useful pixels from single template image for high-speed template matching. In order to reliable matching, it is important to extract pixels that have unique locations and intensities. For that purpose, co-occurrence histogram of multiple points is useful, because it is including co-occurrence probability information of each pixel. In proposed method, pixels that have co-occurrence will be preferentially selected as reference pixels. Through some experiments using more than 120 test images, it has been proved that approximately 0.4 to 1% of template pixels extracted by the proposed method is able to keep 100% recognition success rate.. †. 1. 中京大学情報理工学部 School of Information Science and Technology, Chukyo University †† 三菱電機（株）先端技術総合研究所 Advanced Technology R&D Center, Mitsubishi Electric Corporation. ⓒ2009 Information Processing Society of Japan.

(2) Vol.2009-CVIM-169 No.45 2009/11/27. 情報処理学会研究報告 IPSJ SIG Technical Report. するアプローチが考えられる．これは Coarse-to-Fine 探索のような探索回数の削減技法と併用できることからも有用な考え方である．本研究の目的は，このアプローチに基づき，照合の信頼性を維持しつつ類似度評価に有用なごく少数の参照画素群を選択する手法を提案することである．なお，工場などでは多くのテンプレート画像を事前に準備することはしばしば困難を伴うことから，本研究では参照画素を決定する際に，テンプレート画像 1 枚のみが与えられていることを前提とする．このアプローチに属する関連研究としては，画素選択の方針によっていくつかの方法がある．例えば，高精度の照合のためには輪郭点付近の情報が重要であるとして輪郭画素のみを使用する手法[15]や，高速性に加えて探索の信頼性を考慮して，類似度マップの形状の良さと選択点数の少なさの両方を勘案して画素を選択する手法[16][17]，画像の局所濃度が極値を持つ画素や明確な濃度境界を挟む 2 画素が選択されるべきとする考え方[18]などがある．また，テンプレートをより小さな画像ブロックの集合と考え，ブロック単位で取捨選択するものとして，照合誤差とブロックの配置を考慮する手法[19]や，テンプレートのモデルとの照合度合いに応じて使用するブロックを決定する手法[20]がある．これらの参照画素選択アルゴリズムは参照画素数の削減率に比例した高速化の効果が期待できるが，選択画素数は例えばテンプレート全画素数の 5%～10%程度[15][17]にとどまっている．そこで本研究では，テンプレート画像における各画素がどの程度強くその画像を特徴づけることに寄与しているのかを評価し，画像を強く特徴づけているユニークな画素を優先的に選択する参照画素選択手法を提案する．ここでは，画像における当該濃度の発生確率が低い画素ほどマッチングに有効なユニークな画素であると考える．各画素の濃度の発生確率は濃度ヒストグラムとして計算できるが，一般にはテンプレート画素数に比べて画像の階調数が相当小さいために同じ濃度値を持つ画素が多く，選択すべき画素の決定が難しい．提案手法では，数点の画素からなる点群パターンを選択の単位と考え，パターンとしての発生確率すなわち濃度共起確率を計算し，共起性が低いパターンを構成する点群を参照画素として優先的に採用する．テンプレート画像の独自性の発現に強く関与する画素が多く使われるので，入力画像中に類似のパターンがあっても一定の信頼性が確保できると期待される．また，共起確率は 0 から 1 までの値に正規化されているため，一定値以下の共起確率を持つ画素のみを選択することも可能であり，テンプレート画像における局所パターンのユニークさの強さによって，選択される画素数が変化する，すなわちテンプレート画像の様相によって抽出される参照画素数も適切に判断され得るという利点を持つ． 2 つの画素に関する共起確率は画像の同時生起行列[21]をもとにして計算される．これは一定の位置関係にある 2 画素の濃度値ペアの発生頻度値を各々の濃度値をインデクスとする 2 次元マトリクスで表現したものであり，共起ヒストグラムとも呼ばれる．画像の空間周波数に関する情報を持つことから，従来より主にテクスチャ解析に利用. されてきたが，近年では画像間変化検出[22]やエッジ検出[23]などにも利用されている．また，n 個の画素からなる点群パターンの共起確率を計算するためには一般には n 次元のヒストグラムが必要であるが，本研究では，これを n-1 個の 2 画素ペアによる共起ヒストグラムをもとに近似的に計算する方法を示す．これにより共起マトリクスの格納容量を低減することができる．なお近年，SIFT[24][25][26]，HOG[27]など画像中の特徴のある点の濃度や周辺領域の濃度勾配分布に基づく特徴量を用いる物体検出手法が研究されており，画像の濃度変化や部分的な形状変形，スケール変化に対応できる実用的手法として実応用にも優れた成果を上げている[28]．これらも画像内の少数点を使用しているという意味では参照データ点数を減らす試みであると捉えることもできるが，1 点あたりの特徴記述長が比較的大きく，特徴点の抽出や特徴量の記述に時間がかかるなどの課題があることから，本研究では実装上の容易さを重視して画素同士の比較による従来のテンプレートマッチングを前提としている．以下，第 2 章では画像の共起ヒストグラムの生成方法と共起確率について述べる．第 3 章では，本稿で提案する濃度共起情報に基づく参照画素選択アルゴリズムと，選択された参照画素のみを用いるテンプレートマッチングアルゴリズムの構成について説明する．第 4 章では，実画像から生成したシミュレーション画像および実際に撮影した多数の実画像データベースによる性能検証結果を示す．. 2. 画素の共起確率の表現 2.1 2 画素ペアの濃度共起ヒストグラム. 画像の共起ヒストグラムは，画像 f(i, j)における 2 つの画素からなる画素対 P と Q それぞれの濃度値 p と q のペアの発生頻度（個数）を，画像全体にわたって求め，濃度値 p ，q を縦横それぞれのインデクスとする 2 次元マトリクス状に並べたものである[21][23]．P，Q の位置ベクトルをそれぞれ vp,= (ip, jp)，vq=(iq, jq) とし，P からみた Q の変位ベクトルを d =（k, l）とすると，この 2 画素からなる画素ペアの共起ヒストグラム h2(p, q, d )は，(1)(2)式で定義される．. h2 ( p, q, d) = ∑ ∑ δ d∈R2. {. (1) 2. } {. }. ⎧ if f ( v p ) = p ∩ f ( v q ) = q ⎨ ⎩else. then δ 2 = 1 δ2 = 0. (2). where, v q = v p + d h2 は画素対における d に依存する関数であるが，以下では特に紛らわしくない限り引. 2. ⓒ2009 Information Processing Society of Japan.

(3) Vol.2009-CVIM-169 No.45 2009/11/27. 情報処理学会研究報告 IPSJ SIG Technical Report. 濃度 p をもつ画素の数である．p は 0 から L-1 までの値をとる．. 数 d を省略して記す．ヒストグラム h2 の添え字 2 は，これが 2 つの画素の共起に関するヒストグラムであることを示すものであり，領域 R2 は点P と Q がともに画像 f に含まれるときの点 P の存在範囲を表している．なお本研究では，画像は 256 階調の濃淡画像を仮定しているので，h2 は 256x256 の 2 次元マトリクスとなり，その要素の総和は領域 R2 の面積と等しい．ここで，h2 の値を h2 の総和が 1 になるように次式(3)で正規化し，共起確率 Ph2 とする． L は共起ヒストグラムの階調数であり，例えば原画像の階調数と同じ 256 である．Ph2 はある画像 f が与えられたとき，その画像において位置変位が d である画素対 P，Q がそれぞれ濃度値 p，q を同時にもつ確率を表しており，共起ヒストグラムと同様に L ×L のマトリクスとして表現できる．なお p は行，q は列のインデクスである．. h1 ( p ) = ∑ ∑ δ d∈R1. ⎧ if f ( v p ) = p ⎨ ⎩else. (4). 1. then δ1 = 1. (5). δ1 = 0. なお，当然ながら h1 の総計は画像 f のサイズ R1 と等しい． L −1. ∑ h ( p) =R 1. (6). 1. p =0. Ph2 ( p, q ) =. h2 ( p, q) L −1 L −1. 2 画素の対に関する共起確率分布を示す(3)式を，各行ごとの合計が 1 になるようにさらに正規化して(7)式で示される Pc(p, q)を得る．. (3). ∑ ∑ h ( p, q ) 2. q =0 p =0. Pc( p, q ) =. 2.2 n 画素からなる点群パターンの共起ヒストグラムと共起確率. Ph2 ( p, q ). (7). L −1. ∑. Ph2 ( p, q ). q =0. i j. Q2. d2 P. Figure 1.. 得られた Pc は，画像 f に関して画素対の始点 P の濃度が p であることがわかっているとき，対になる終点 Q の濃度が q である条件付き確率分布 Pc( q | p )に相当するものであり，これを 0≦ p≦L-1 について並べたものであると考えることができる．また共起確率 Ph2( p, q )とは，始点が p，終点が q の濃度値を同時に持つ画素対がこの画像中に発生する確率であるから，始点の濃度が p である確率 Ph1(p)と Pc( q | p )の積で表される．なお Ph1(p)は，濃度ヒストグラム h1(p)を画像 f の画素数 R1 で除して得られる単一画素の発生確率分布である．同様に始点 P が濃度 p をとり，P との相対変位が {dx | x=0, 1, 2．． n-1} である n 個の終点 Qx の値がそれぞれ同時に qx である共起確率 Ps(p, q0,…,qn-1,d0,…,dn-1)は，(8)式で求めることができる．. Q1. d1 d0. Q0. 図 1．複数の画素からなる点群パターン A local pattern consisting of the target pixels and neighbor pixels.. 2 画素の場合と同様に n 画素からなる点群についても各画素の濃度をインデクスとする共起ヒストグラムを作成でき，Ln のマトリクスになる．図は n=4 の場合の例である．便宜上，点群の中の 1 点を代表点 P，残りの点群を{Qn | n=0, 1,…, n-2}と表す．ここで n が大きい場合には共起ヒストグラムを格納するためのメモリ量が膨大になるため，以下の方法によりメモリ量を削減する．まず準備として一般によく使われている画像の濃度ヒストグラム h1(p)を(4)(5)式のように表しておく．画素単体に対するヒストグラムなので添え字 1 を使用し，前節で定義した共起ヒストグラムに対して単に濃度ヒストグラムと呼ぶことにする．p は画像 f の濃度値であり，h1(p)は画像中で. n −1. Ps( p, q0 ,..., qn −1 , d 0 ,..., d n −1 ) = Ph1 ( p ) ⋅ ∏ Pc( p, q x , d x ). (8). x =0. すなわち，濃度ヒストグラム h1(p)と，あらかじめ設定した n 種類の位置関係にある 2 画素に関する共起ヒストグラムの組 h2(p, qx, dx)（ただし，x=0,1,2,…,n-1）を n 個準備しておくことにより，(n+1)個の画素による共起確率 Ps を計算することができる．この Ps は近似的な共起確率であるが，(n+1)個の画素群の発生頻度を実測して保存する方法に比べて必要なメモリ量は少なくなる．例えば 1 つの始点と n 個の終点からな 3. ⓒ2009 Information Processing Society of Japan.

(4) Vol.2009-CVIM-169 No.45 2009/11/27. 情報処理学会研究報告 IPSJ SIG Technical Report. る n+1 画素の共起確率の表現に必要なメモリセル数は Ln+1 ではなく（ L＋nL2）で済む．. 2 点共起は水平または垂直それぞれの方向に s 画素（s は 1, 2, 4, 8, 16 の 5 種類）離れた計 10 個の画素対の発生確率の和を選択基準とする．3 点共起では 3 画素からなる点群パターン{f(i, j), f(i+s, 0), f(0, j+s)}の発生確率をもとめ，これを 1, 2, 4, 8, 16 の 5 種類の s について加算したものを選択基準とする．いずれも事前に選択すべき参照画素数 D を決めておき，登録画素数が D に達するまで，これらの確率が小さい順に登録する．ただしほぼ同程度の共起確率値を持つ画素が複数存在する場合には，その中からランダムに参照画素を選択する．図 2 は参照画素選択に関する機能モジュールを模式的に示した図である．また図 3 に本アルゴリズムのフローチャートを示す．. 3. 参照画素選択およびテンプレートマッチングアルゴリズム本章では共起確率を用いてテンプレート画像から参照すべき画素を選択するアルゴリズム，および選択された点列を用いた照合アルゴリズムを説明する． 3.1 参照画素選択の方針. 参照画素は，一定の位置関係にある点群パターンの画像内での発生頻度をもとにして選択される．発生頻度は共起確率で表現されるため，まず点群パターンを構成する画素数と位置関係を決定する必要がある．画素数については，少ないほど共起性を考慮する度合いが低くなるため，類似するパターンが画像中に出現する確率が高くなり，パターンとしてはユニークさが減少する．これはテンプレートとして特徴の弱いパターンを使用することを意味する．しかし反対に点数が多すぎると，ユニークさが極めて強くなるので頻度が低下し，選択すべき点群を選ぶことが困難になる．位置関係を決定することは，共起状態が生じている空間周波数の大きさと方向を設定することに相当する．多様な d を設定すれば多様な位置関係を表現できるが，多くの演算時間とメモリが必要になる．. Calculate Ph 1(p). f (i , j ). Co-occurrence histograms. 本節では，前節で選択された少数の参照画素を用いたマッチングのアルゴリズムを説明する．これは離散的なテンプレート画素を用いたマッチング手法 [29]と基本的に同じものである． 0. 1. 2. 3. 4. 0 1. Ph1(L) Ph2 (L). Ps (L) Selection of reference pixels. Select reference pixels based on Ps(p,q0,...,qn-1). 3.3 離散的参照点を用いるテンプレートマッチング. 本研究では，画素間の変位方向については始点から水平，垂直の 2 つの方向とし，距離については，1，2，4，8，16 画素の 5 種類を考慮することにした．また点群パターンの画素数としては 2 点共起，3 点共起の 2 種類を検討することにした． Generation of co-occurrence histograms (Probability distribution). Calculate co-occurrence probability of n-pixles Ps(p,q0,...,qn-1) using Ph 1 and Pc. Calculate co-occurrence probabilities Pc(qx|p) from h 2. 図 3．参照画素選択アルゴリズムのフローチャート Figure 3. Flowchart of an algorithm for selection of reference pixels.. 3.2 共起確率に基づく参照画素の選択. Template image. Generate co-occurrence histograms h 2(p,q,k,l) for various displacements. 5. Reference pixels k. 0. 1. 2. 3. 4. 5. 6. 7. 8. 9. 2. f i (k). 1. 2. 3. 4. 1. 4. 1. 3. 1. 2. 3. f j (k). 1. 1. 1. 1. 2. 2. 3. 3. 4. 4. 4. fv (k). 188. 189. 190. 176. 180. 174. 188. 189. 190. 195. 5. 1-Dimensional template for selected reference pixels. f (i , j ). Selected pixels. Figure 4.. 図 2．参照画素選択アルゴリズムのモジュール構成 Figure 2. Block diagram of an algorithm of reference pixels selection.. 図 4．参照画素を格納した 1 次元点列テンプレートの例 An example of one dimensional template which consists of selected pixels.. テンプレートデータは，共起確率を用いて選択された離散的な画素のみが図 4 図のような 1 次元的な 3 つの配列 fi(k)，fj(k)，fv(k)として格納される．fi は各参照画素の i 座 4. ⓒ2009 Information Processing Society of Japan.

(5) Vol.2009-CVIM-169 No.45 2009/11/27. 情報処理学会研究報告 IPSJ SIG Technical Report. 標値，fj は j 座標値，fv は濃度値であり，k=0, 1, 2．． M-1 である（ M は参照画素数）．テンプレートデータを入力画像に対して (dx, dy) ずらして重ね合わせたときの正規化相互相関による類似度 SCORR(dx, dy)は，次の(9)式で計算される．ここで g(i, j)は入力画像である．文献 [29]ではマッチングに際して回転ずれとスケーリングにも対応しているが，本研究では現時点で平行移動のみを実装した．これを (dx, dy)を動かしながら求め，最大の類似度をとる位置を出力する．類似度尺度としては SAD(Sum of Absolute Difference)など様々な指標が提案されているが，本研究では現在最もよく使われている正規化相互相関を用いることとした．. 4.2 共起ヒストグラムの生成例. 図 6 に示したのは図 5 の Doll と Parts のテンプレート画像について水平に変位を持つ画素対の共起ヒストグラムである．d=(+1, 0), (+4, 0), (+16, 0)の場合を例示した．. frequency q. M −1. ∑{g ( f (k ) + d , f (k ) + d ) ⋅ f (k )} i. SCORR ( d x , d y ) =. x. j. y. v. M −1. p. (9). k =0. Doll. M −1. ∑ f (k ) ∑ g ( f (k ), f (k )) v. k =0. i. d = (+1,0 ). d = (+4,0). d = (+16,0). d = (+1,0). d = (+4,0). d = (+16, 0). j. k =0. 4. 実験と考察 4.1 実験に用いた画像. Parts 128x164. 128x164. 80x128. 図 6．共起ヒストグラムの例 Figure 6. Examples of co-occurrence histogram. 132x118. 459x344. 444x333. 350x240. 640x480. (a) Doll. (b) Doll2. (c) Rabbit. (d) Parts. Doll では，頻度値が濃度の低い部分から高い部分まで比較的分散していることがわかる．また d=(+1, 0)では始点と終点が隣接していることからほとんどの画素対で濃度が類似しており，共起ヒストグラム上では p=q の対角線上にデータが集積している．この傾向が d=(+4, 0)，d=(+16, 0)のように画素対の距離が離れるにしたがって弱まる様子は，徐々にデータが対角線上から周辺に散逸していくことで確認できる．一方，Parts は Doll と同様に d=(+1, 0)ではヒストグラムの対角線上にデータが集積するが，背景部と前景の物体部分のが 2 値画像に近い濃度分布を持っているので 2 つのピークを持つ． p, q が小さい方が背景部である．またこの部品の形状は T 字型であることから輪郭部分の濃度勾配は水平，垂直方向が支配的である．したがって画素対の始点と終点が部品の輪郭を挟む位置関係にあるときには p と q の間には一定の濃度差が生じることから，共起ヒストグラム上では第 3，第 4 のピークが現れ，その傾向は d=(+4, 0)，d=(+16, 0)のように画素対の距離が大きくなると顕著である．なお共起ヒストグラムの各行のデータを水平方向に足し合わせれば，式 (4)(5)で示したような通常の濃度ヒストグラムと等価になる．. 図 5．実験に用いた画像例（上：テンプレート画像，下：入力画像例） Figure 5. Examples of test image. (Top: Template Image, Bottom: Acquired image) 図 5 に実験に用いた画像例を示す．(a)(b)は室内に置かれた人形，(c)は複雑な背景の上に描かれたうさぎのイラスト，(d)はスチール製の L 字および T 字型プレート状部品である．テンプレート画像と入力画像は別々に撮影されたものである．なお画像 (c)は電子情報通信学会パターン認識・メディア理解研究会のアルゴリズムコンテスト 1998 にて公開されているデータ[30]である．. 5. ⓒ2009 Information Processing Society of Japan.

(6) Vol.2009-CVIM-169 No.45 2009/11/27. 情報処理学会研究報告 IPSJ SIG Technical Report. 値の低いものから順に選択する．(3)(4)ともにほぼ同程度の確率値を持つ画素が複数存在する場合はランダムに選択する．ランダム法以外の 3 つの手法では，いずれも画像のエッジ部分に選択画素が多い傾向がある．しかし詳細に見ると，濃度勾配法では明確なエッジ部分のみを選択しているのに対し，提案手法では必ずしもエッジ部分だけでなく，例えば黒色の目の部分の内部や首と胴体のコントラストの低いエッジ部分を選択していることがわかる．提案手法 2 つの比較では， 2 点画素対の共起に基づく提案手法 2 のほうが 3 点共起に基づく手法 1 よりも同時生起性に関する要求が緩いことから，濃度変化の少ない部分を選択する傾向が強いことが確認できる．. 4.3 提案手法により選択された参照画素. 提案手法を含む以下の (1)～(4)の 4 種類の手法を用いて，テンプレート画像から M 点の参照点を選択させた結果を図 7 に示す．（）内の数字は全画素数に対する割合である．. M=50 (0.2%). M=500 (2.4%). (a) Proposed method 1 (3-points co-occurrence). M=2000 (10%). Figure 8.. (1)Random. (2)Gradient. (3)Proposed 1. (b) Proposed method 2 (2-points co-occurrence). 図 8．提案手法における共起確率画像 Co-occurrence probability images by proposed methods.. ところで，式(8)に基づいて各画素を始点とする画素対の共起確率を計算し，その確率値を画素値とする画像を再構成することによって，共起確率画像を生成することができる．画像 Doll と Parts に対する共起確率画像を図 8 に示す．図では共起確率の低い画素から順に高くなるにつれて，青→緑→黄→赤→黒の順に着色してある．Doll の場合は共起制約の強い 3 点共起に基づく手法のほうがより輪郭画素付近を重点的に選択していることがわかる．一方 Parts はもともと画像中の局所コントラストの分布に偏りが大きいために， 2 点共起と 3 点共起で Doll ほどの顕著な差異は認められない． 4.4 テンプレートマッチングの性能評価実験には図 5 のテスト画像を用いた． Doll，Doll2， Rabbit については 1 枚の画像をもとにして不均一照明（シェーディング）と，ランダムノイズを人工的に付加したテスト画像 120 枚を生成した．シェーディングは 45 度方向に sin 関数状の最大±80 レベルの濃度変化を，ノイズは画像の最大 45%の画素に対して濃度値を最大±30 レベル変化させた．図 9 に一例を示す．Parts については実際に照明条件や検出対象物体の位置を変更しながら計 121 枚の画像を撮影した．. (4)Proposed 2. 図 7．4 種類の手法により選択された参照画素 Figure 7. Selected reference pixels by 4 methods.. (1) ランダム法：テンプレート画像からランダムに参照画素を選択する． (2) 濃度勾配法：テンプレート画像の各画素の濃度勾配値を求め，勾配の大きい画素ほど輪郭部を表現していると考えて，優先的に選択する．同じ勾配値を持つ画素が存在するときはランダムに選択する． (3) 3 点共起法（提案手法 1）：始点画素 P， P から水平に s 離れた終点を Q1，垂直に s 離れた終点を Q2 とし，P，Q1，Q2 の計 3 点の共起確率を s を 1,2,4,8,16 の 5 種類変化させて加算した数値の低い順にその始点画素を参照画素とする． (4) 2 点共起法（提案手法 2）：始点画素から水平に s 離れた 2 点画素対と垂直に s 画素離れた 2 点画素対を考え， s=1,2,4,8,16 の計 10 種類の 2 点共起確率の合計 6. ⓒ2009 Information Processing Society of Japan.

(7) Vol.2009-CVIM-169 No.45 2009/11/27. 情報処理学会研究報告 IPSJ SIG Technical Report. みると，ランダム法では M=800，濃度勾配法では M=1000 であるが，3 点共起に基づく方法では M=250 であり，これはテンプレート画像サイズ 128x164=20992 点に対して 1.2%の画素数に相当する．さらに 2 点共起に基づく手法では M=80 点でも Pr=100% であり，約 0.4%の画素数となる．提案手法により参照画素数を大幅に削減可能なことを示している．なお濃度勾配法と提案手法（3 点共起）に関して M=100～ 200 点付近で認識率が不安定になっている理由は，点数が少ない時には勾配値や共起確率の分解能の低さに起因してランダム的な画素選択の比率が高まっていることが一因であると考えられる．図 11 に認識成功時の画像例を示す．. (Magnified) (a)+Shading. (a) Original image. Figure 9.. (a)+Noise. (b) Examples of test images. 図 9．照明変動とノイズを付加したテスト画像 Test images with illumination changes (shading) and random noises.. これらのテスト画像を用いて，選択された画素数 M と認識成功率 Pr の関係を調べた．ここで Pr は， Pr ＝正しい位置から±5 画素以内の位置で検出した画像数／全画像数と定義した． Doll について M と Pr の関係を図 10 に示す．. (a) Doll. Figure 11.. (b) Doll2. (c) Rabbit. (d) Parts. 図 11．さまざまな画像に対する照合結果 Results of matching using reduced template data in various kinds of test images.. 表 1 には，4 種類のテスト画像各々においていくつかの Pr を設定したときに必要な最小限の参照点数を，各テンプレート画像全体画素数に対する比率として %表示したものである．照合には提案手法（2 点共起）を使用した．例えば， Doll では Pr≧ 10% を得るためには 0.29%の点数， Parts では Pr≧50%を得るためには 0.96%の点数が必要なことがわかる．どの画像に関しても，テンプレート画像全体画素数の 1%以下の点数で Pr=100[%]になっていることがわかる．Rabbit が特に少ない点数で足りているのはテンプレート内部に明確な安定パターンが存在することが理由であると推察される．一方，Parts が他の画像より多くの点数を必要とした理由は，照明変動パターンが複雑であることと，微小な回転ずれが発生したことが考えられる．. Table 1. Figure 10.. 表 1．認識成功率を満足するために必要な最小相対画素数 [%] Minimum relative number of reference pixels to satisfy each recognition rate. Requirements for Pr Pr >= 10 Pr >= 50 Pr >= 80 Pr = 100. 図 10．テンプレート画像の参照画素数と認識成功率の関係 Relation between the number of reference pixels and recognition success rate.. 図の横軸は対数目盛となっている．どの手法も M≧1000 では Pr=100[%] であり，点数が少なくなると認識率は低下する．Pr=100[%]を維持するために必要な最少の点数を 7. Doll 0.29 0.38 0.38 0.38. Test image Doll2 Rabbit 0.33 0.15 0.33 0.15 0.33 0.15 0.33 0.15. Parts 0.64 0.96 0.96 0.96. ⓒ2009 Information Processing Society of Japan.

(8) Vol.2009-CVIM-169 No.45 2009/11/27. 情報処理学会研究報告 IPSJ SIG Technical Report. 高速テンプレートマッチング，電子情報通信学会論文誌，Vol.J83-D2, No.9, pp.1861-1869(2000)． 15) 橋本学, 鷲見和彦, 坂上義和, 川戸慎二郎: 輪郭点情報を用いた高速テンプレートマッチングアルゴリズム, 電子情報通信学会論文誌 D-II, Vol.J74-D-II, No.10, pp.1419-1427(1991). 16) 橋本学, 鷲見和彦, 広岡美和子, 奥田晴久: 自己相関マップ最適化に基づく分散テンプレート選択手法, 電子情報通信学会春季全国大会, D-604, pp.330(1995). 17) 斎藤文彦: 遺伝的アルゴリズムを用いた画素選択テンプレートによる画像マッチング, 電子情報通信学会論文誌 D-II, J84-DII, 3, pp.488-499(2001). 18) 松原康晴, 尺長健: 疎テンプレートマッチングとその実時間物体追跡への応用, 情報処理学会論文誌, vol.46, no.SIG9(CVIM11), pp.60-71(2005). 19) T.Kaneko, O.Hori: Feature Selection for Reliable Tracking using Template Matching, Proceedings of IEEE CVPR vol.1, pp.796(2003). 20) D.Cristinacce and T.Cootes: Facial Feature Detection and Tracking with Automatic Template Selection, Proc.of 7th IEEE International Conference on Automatic Face and Gesture Recognition (FG'06), pp.429-434(2006). 21) R.Haralick, K.Shanmugam and I.Dinstein: Textural Features for Image Classification, IEEE Transactions on Systems, Man, and Cybernetics SMC-3 (6), pp.610–621(1973). 22) 喜多泰代: 二次元濃度ヒストグラムを用いた画像間変化抽出, 電子情報通信学会論文誌 D-II, Vol.J90-D, No.8, pp.1957-1965(2007). 23) 藤原孝幸, 山足和彦, 輿水大和, 画像の共起度数からなる特徴量を用いた新しい空間フィルタ, 電気学会論文誌 C, Vol. 127, No.4, pp.546-552(2007). 24) D.G.Lowe: Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision 60(2): 91-110(2004). 25) Y.Ke, R.Sukthankar: PCA-SIFT: a more distinctive representation for local image descriptors, Proc. of the CVPR, Vol.2, pp.506-513(2004). 26) 藤吉弘亘: Gradient ベースの特徴抽出 - SIFT と HOG -, 情報処理学会研究報告 CVIM 160, pp.211-224(2007). 27) N.Dalal, B.Triggs: Histograms of Oriented Gradients for Human Detection, IEEE Computer Vision and Pattern Recognition, pp.886-893(2005). 28) A.Ihara, H.Fujiyoshi, M.Takagi, H.Kumon and Y.Tamatsu: Improved Matching Accuracy in Traffic Sign Recognition by Using Different Feature Subspaces, Proc. of Machine Vision Applications 2009 (MVA2009), 3-26, pp.130-133(2009). 29) M.Hirooka, K.Sumi, M.Hashimoto, H.Okuda and S.Kuroda: Hierarchical Distributed Template Matching, Proc. of SPIE Symposium on Electronic Imaging & Science and Technology, Vol.3029, pp.176-182(1997). 30) 電子情報通信学会パターン認識・メディア理解研究会アルゴリズムコンテスト 1998. http://yindy1.aist-nara.ac.jp/PRMU/contest/data.html. 5. おわりに 1 枚のテンプレート画像が与えられたときに，画像内の複数画素からなるパターンの共起確率に基づいて参照画素を選択する手法を提案した．不均一な濃度変化やランダムノイズを付加した画像群による性能評価実験により，ランダムな画素選択や濃度勾配値に基づくエッジ点重視の画素選択よりも，照合に必要な画素数を大幅に削減できることを示した．併せて，確率分布を格納するためのメモリ容量削減のために， n 画素の共起確率を n-1 個の 2 画素対の共起確率分布から近似的に計算する手法を示した．今後は対象物の幾何学的変形と濃度変化に関するロバスト性能の向上を検討する．. 参考文献 1) A.Rosenfeld and A.C.Kak: Digital Picture Processing, Second Edition, Academic Press, Inc., Vol.2, pp.296-302(1976). 2) A.Goshtasby: Template Matching in Rotated Images, IEEE Trans. on PAMI, Vol.PAMI-7, No.3(1985). 3) .D.Tubbs: A Note on Binary Template Matching, Pattern Recognition, Vol.22, No.4, pp.359-365(1989). 4) K.Sumi, M.Hashimoto, H.Okuda and S.Kuroda: Three-Level Broad-Edge Matching and its Application to Real-time Vision System, IEICE Trans. on Information and Systems, Vol.E78-D, No.12, pp.1526-1532(1995). 5) S.Kaneko, I.Murase and S.Igarashi: Robust image registration by increment sign correlation, Pattern Recognition, Vol.25, No.10, pp.2223-2234(2002). 6) F.Ullah, S.Kaneko and S.Igarashi: Orientation Code Matching for Robust Object Search, IEICE transactions on information and systems E84-D, No.8, pp.999-1006(2001). 7) 尾崎竜史, 佐藤雄隆, 岩田健司, 坂上勝彦: 統計的リーチ特徴法によるロバスト画像照合, ビジョン技術の実利用ワークショップ 2008, pp.191-196(2008). 8) 尾崎竜史, 佐藤雄隆, 岩田健司, 坂上勝彦: 統計的リーチ特徴法によるサンプル学習型画像照合, 第 15 回画像センシングシンポジウム, pp.IS3-27-1-5(2009). 9) S.L.Tanimoto and T.Pavlidis: A Hierarchical Data Structure for Picture Processing, Computer Graphics and Image Processing, Vol.4, No.2, pp.104-119(1975). 10) G.J, Vanderbrug and A.Rosenfeld: Two stage template matching, IEEE Trans. on Computer, C-26, 4, pp.384-393(1977)． 11) R.N.Nagel and A.Rosenfeld, Ordered Search Techniques in Template Matching, Proceeding of the IEEE, Vol.60, No.2, pp.242-244(1972). 12) D.I.Barnea and H.F.Silverman: A class of algorithms for fast digital image registration, IEEE Trans. on Computers, 21, pp.179-186(1972)． 13) 村瀬洋, V.V.Vinod: 局所色情報を用いた高速物体探索アクティブ探索法，電子情報通信学会論文誌，Vol.J81-D2, No.9, pp.2035-2042(1998). 14) 池田光二, 吉田昌司, 中島啓介, 浜田長晴, 依田晴夫: 正規化相関演算の単調関数化による. 8. ⓒ2009 Information Processing Society of Japan.

(9)