Bilateral FilterBilateral FilterBilateral FilterBilateral Filter

全文

(1)平成 23 年度修士論文. Bilateral Filter を用いた SIFT の性能改善に関する検討の性能改善に関する検討. 早稲田大学大学院早稲田大学大学院基幹理工学研究科基幹理工学研究科情報理工学専攻 5110B1295110B129-8 山崎智章指導甲藤二郎教授 2012 2012 年 1 月 31 日. 指導教授印. 受付印.

(2) 目次第 1 章序論.......................................................................................................... 序論........................................................................................................... ........................................................................................................... ..3 ..3 1.1 研究背景...................................................................................................... ..3 1.2 研究目的...................................................................................................... ..3 1.3 本論文の構成............................................................................................... ..3 第 2 章関連研究.................................................................................................... 関連研究.................................................................................................... ..4 ..4 2.1 特徴量抽出手法........................................................................................... ..4 2.2. SIFT(Scale-Invariant Feature Transform)............................................... ..4. 2.3. SIFT のアルゴリズム.................................................................................. ..4. 2.3.1 スケールと特徴点検出............................................................ .............. ..6 2.3.2 特徴点のローカライズ.......................................................................... 14 2.3.3 オリエンテーションの算出................................................................... 17 2.3.4 特徴量の記述........................................................................................ 19 2.4. SIFT の拡張................................................................................................ 21. 2.4.1 PCA-SIFT............................................................................................. 21 2.4.2 BSIFT................................................................................................... 22 2.5. 対応点探索.................................................................................................. 23. 第 3 章提案手法....................................................................... .................................................................................................... ............................. 24 提案手法....................................................................... 3.1 エッジ上の特徴点における誤対応.............................................................. 24 3.1.1 開口問題............................................................................................... 24 3.1.2 特徴点の誤対応..................................................................................... 25 3.2. DoB(Difference-of-Bilateral)...................................................................... 27. 3.3 Bilateral Filter............................................................................................ 27 第 4 章提案手法による SIFT の特性と対応点探索実験の特性と対応点探索実験............... 実験.................... ....................... ........................ ................... 30 4.1 実験環境…………………………………………………………………………..30 4.2. DoB 画像..................................................................................................... 30. 4.3. 特徴点の比較............................................................................................... 32. 4.3.1 特徴点の絞込み…………………………………………………………….. 32 4.3.2 同特徴点数における特徴点の比較……………………………………….. 33 4.4 σr の変動による特徴点への影響……………………………………………… 34 4.5. 勾配方向ヒストグラムの比較…………………………………………………..36. 4.6 特徴ベクトルの比較……………………………………………………………..37 4.7 画像変化に対する頑健性………………………………………………………..38 4.8 対応点探索実験…………………………………………………………………..41. 1.

(3) 4.9 対応点探索精度の向上................................................................................. 42 4.10 エッジ上の特徴点...................................................................................... 43 4.11. 処理時間の計測.......................................................................................... 46. 第 5 章高速化実装…………………………………………………………………… 高速化実装……………………………………………………………………... ……………………………………………………………………... 47 5.1. GPGPU による高速化………………………………………………………….. 47. 5.1.1 GPGPU……………………………………………………………………… 47 5.1.2 CUDA……………………………………………………………………….. 48 5.1.3 CUDA のプログラミングモデル…………………………………………. 48 5.2 実験………………………………………………………………………………..50 5.2.1 Bilateral Filter 実装………………………………………………………. 50 5.2.2 SIFT への組込み…………………………………………………………… 51 第 6 章一般物体認識への応用………… 一般物体認識への応用……………………………………………………… ……………………………………………………….. …………………………………………….. 53 6.1 一般物体認識……………………………………………………………………. 53 6.2 実験概要…………………………………………………………………………. 54 6.3 実験結果…………………………………………………………………………. 55 6.4 閾値によるカテゴリごとの識別率の変化……………………………………. 58 第 7 章総括........................................................... .............................................................................. .......................................... 総括........................................................... ................................................ ............................. 59 7.1 まとめ.......................................................................................................... 59 7.2 今後の課題................................................................................................... 59 参考文献..................................................................................... 参考文献.................................................................................................................. .................................................................................................................. 60 謝辞............................................................................................. 謝辞..................................................................................................... .......................................................................................................................... .............................62 発表文献リスト………………………………………………………………………… 発表文献リスト…………………………………………………………………………... …………………………………………………………………………... 63. 2.

(4) 第 1 章序論 1.1 研究背景近年、コンピュータの発展に伴い、大量データを扱う画像処理技術が可能となり、デジタルカメラに搭載されている顔検出・認識に代表されるように、画像認識技術が実世界へ応用されつつある。画像検索、物体認識/検出、動画像での目標追跡、ステレオ対応等、様々な技術もこれに当たるだろう。これらの技術の実現には、画像から対応付けの指標となるような何らかの特徴を抽出する必要がある。本論文では、物体や場面は同じだが、サイズ・角度・ノイズ・明るさ等の面で異なった画像に適するような特性を持つ、画像特徴について扱う。. 1.2 研究目的上述したような要求を満たす代表的な特徴量抽出手法として、Scale-Invariant Feature Transform (SIFT) [1] がある。本論文は、SIFT の問題点を示し、精度の面から SIFT の改善手法を提案するとともに、その応用例として一般物体認識の特性改善について検討する。. 1.3 本論文の構成第 1 章である本章では、研究の背景及び目的を述べた。続く第 2 章では、関連技術として、特徴量抽出手法である SIFT のアルゴリズムと一般物体認識について説明する。第 3 章では、SIFT の問題点を述べ、それに対する改善手法を提示すると共に、必要となる背景技術に関して説明する。第 4 章では、提案手法の実装実験及び、従来手法との比較実験について報告する。第 5 章では、GPU 実装により本手法の高速化を行い、その結果について報告する。第 6 章では、本手法の応用例の一つとして、一般物体認識において識別率を比較し、本手法の有効性を確認する。最後に第 7 章において、本論文の総括と今後の課題について述べる。. 3.

(5) 第 2 章関連技術 2.1 特徴量抽出手法画像の照合に用いられる特徴量は大きく大域特徴量(global feature)と局所特徴量(local feature)に分類できる。大域特徴量とは、画像全体から抽出される特徴量であり、一例としては、Content-Based Image Retrieval(CBIR)に用いられるカラーヒストグラムが挙げられる。一方、局所特徴量とは、画像の一部分から抽出される特徴量である。局所特徴量を抽出するには、どの領域から特徴量を取り出すのかを決定し、その領域から特徴量を抽出するという 2 段階の処理が必要となる。前者を担うプログラムを detector、後者を担うプログラムを descriptor と呼ぶ。大域、局所の両者とも特徴はベクトルとして表現される。この特徴ベクトルの対応を取ることによって、画像の照合が可能となる。次に、大域特徴量と局所特徴量の比較について述べる。局所特徴量の detector に対応する処理が、大域特徴量の抽出では不要であるため、大域特徴量の抽出は計算量的に有利である。また、特徴量が画像 1 枚あたり 1 つであるため、画像の索引付けに用いるデータ量としても大幅に少なくてすむという利点もある。一方で、画像の一部分が隠れ(occlusion) によって得られない場合、大域特徴量では同じ値を得ることは不可能となる。しかし、局所特徴量を用いる場合は、occlusion によって得られない特徴量があっても、隠れていない部分から同じ特徴量を得ることができるという利点がある。局所特徴量に分類される、最も著名なものは SIFT(Scale-Invariant Feature Transform) であろう。次の項では、SIFT について説明する。. 2.2 SIFT(ScaleSIFT(Scale-Invariant Feature Transform) 1988 年、Harris らは特徴点としてコーナーを検出する手法として、Harris Corner Detector[2]を提案した。1994 年には、Lindeberg がスケールスペースを用いることで画像の構造を解析し、blob の検出と自動スケール選択を行う手法[3]を提案した。また、1997 年、 Schmid らは Harris Corner Detector によって検出された特徴点に対し、その画素値や微分値から算出した値を特徴量とし、画像の回転に頑健な局所特徴量を記述する手法[4]を提案した。これにより、回転変化が生じても、画像間のマッチングや認識を行うことが可能となった。しかし、Schmid らの手法に用いられている Harris Corner Detector は、画像のスケール変化に敏感であるため、拡大・縮小等の異なるスケールの画像間ではマッチングが困難である。そこで、Lowe は Schmid らの「局所領域の特徴量記述」という考えを拡張し、スケールスペースを用いることで、画像のスケール変化や回転に不変は特徴量を記述する. 4.

(6) SIFT(Scale-Invariant Feature Transform)を提案した。スケールスペースとは、画像 I(x, y) をある量 t だけ平滑化した画像 I(x, y; t)を考え、この 3 次元空間で画像を理解しようという考え方である。具体的な手法は後述する。 SIFT は、回転・スケール変化等に不変な特徴量を記述するため、画像のマッチングや物体認識等に広く用いられている。さらに、PCA(Principal Component Analysis)を用いて勾配情報を部分空間へ射影し、精度を向上させる PCA-SIFT[5]や、SIFT の特徴量記述時における背景の影響を軽減する BSIFT[6]等の SIFT を拡張した手法が多く提案されている。. 2.3 SIFT のアルゴリズム SIFT の処理は、特徴点の検出(detection)と特徴量の記述(description)の 2 段階からなり、各処理は以下の流れとなる。. 1. スケールと特徴点検出 detection 2. 特徴点のローカライズ. 3. オリエンテーションの算出 description 4. 特徴量の記述. 1. スケールと特徴点検出 DoG 処理によりスケールと特徴点を検出する。 2. 特徴点のローカライズ検出された特徴点から、特徴点として相応しくない点を削除し、その後サブピクセル推定を行う。 3. オリエンテーションの算出回転に不変な特徴を得るために、特徴点のオリエンテーションを求める。 4. 特徴点の記述オリエンテーションに基づいて、各特徴点の特徴量を記述する。各処理の詳細は以下に述べる。. 5.

(7) 2.3.1 スケールと特徴点検出この処理では、DoG 画像群を用いてスケールスペースにおける極値探索を行うことで、特徴点の位置とスケールを決定する。. ⅰ. LoG によるスケール探索 Koenderink[7]や Lindeberg[3]により、特徴点のスケール探索にはガウス関数が有効であることが報告されている。Lindeberg は、ガウシアンカーネルを用いたスケールスペースとして LoG(Scale-normalized Laplacian-of-Gaussian)を提案している。LoG は、画像にスケールσを変化させながら LoG オペレータ(図 1)を適用し、その極大位置を特徴点のスケールと決定する。LoG オペレータは式(1)で表される。. 図 1. LoG オペレータ[9]. LoG = f (σ ) = −.  x2 + y2 x 2 + y 2 − 2σ 2  − exp 2πσ 6 2σ 2 .   . σはガウシアンフィルタのスケール、x,y は注目画素からの距離である。. 6. (1).

(8) LoG は計算コストが高いという問題があり、Lowe によってより効率的な極値検出として、 DoG(Difference-of-Gaussian)[8]を用いる手法が提案されている。DoG と LoG の関係は次式の拡散方程式から導かれる。. ∂G = σ∇ 2 G ∂σ. (2). ここで、G はガウス関数を表し、右辺はガウス関数の 2 次微分(= LoG)である。式(2)は次式のように表すことができる。. ∂G G ( x, y, kσ ) − G ( x, y, σ ) ≈ ∂σ kσ − σ. (3). 式(2)と式(3)から次式が成り立つ。. σ∇ 2 G =. ∂G G ( x, y, kσ ) − G ( x, y, σ ) ≈ ∂σ kσ − σ. (4). 従って、次式が得られる。. (k − 1)σ 2 ∇ 2 G ≈ G(x, y, kσ ) − G(x, y, σ ). (5). ここで、 σ ∇ G は LoG を表しているので、式(5)は DoG が LoG の近似であることを表し 2. 2. ている。LoG と DoG では、得られる結果はほぼ同じだが、DoG のほうが計算効率が良いので、SIFT では DoG を用いている。. 7.

(9) of--Gaussian 処理 ⅱ. DifferenceDifference-of 特徴点の候補は、スケールの異なるガウス関数 G ( x, y, σ ) と入力画像 I(u, v ) を畳み込んだ. 平滑化画像 L(u , v, σ ) の差分(DoG)画像から求める。平滑化画像とガウス関数は、それぞれ以下の式のとおりである。. L(u, v, σ ) = G ( x, y, σ ) ∗ I (u, v ) G ( x, y , σ ) =.  x2 + y2  − exp 2πσ 2 2σ 2  1. (6).   . (7). DoG 処理の結果画像を D(u , v, σ ) とすると、DoG 画像は次式で計算できる。. D(u , v, σ ) = (G ( x, y, kσ ) − G ( x, y, σ )) ∗ I (u , v ) = L(u , v, kσ ) − L(u , v, σ ). (8). この処理を σ 0 から k 倍ずつ大きくした異なるスケール間で行い、図 2 に示すような複数の DoG 画像を生成する。 σ が一定の割合で増加し続けると、ガウシアンフィルタのウィンドウサイズが大きくなり、処理できない端領域の拡大と計算コストの増加の問題が発生する。この問題に対し、SIFT では画像のダウンサンプリングを行うことにより、σ の変化の連続性を保持した平滑化処理を実現している。. 図 2. DoG 画像生成の流れ[9]. 8.

(10) ⅲ.σの連続性を保持した平滑化処理. σ の連続性を保持した効率的な平滑化処理を図 3 に示す。まず、入力画像を初期値である σ 0 で平滑化を行い、平滑化画像 L1 (σ 0 ) を得る。次に σ 0 を k 倍した値 kσ 0 で平滑化を行い、 L1 (kσ 0 ) を得る。同じように、 σ の異なる複数の平滑化画像を得る。ここまでの処理を 1 セットとし、これを 1 オクターブと呼ぶ。次に、複数生成された平滑化画像の中から 2σ 0 で平滑化された画像 L1 (2σ 0 ) を 1/2 のサイズにダウンサンプリングする。1 オクターブにおける処理回数については増加率 k の設定と共に後述する。. 図 3. 平滑化処理の流れ[9]. 9.

(11) 1/2 のサイズにダウンサンプリングされた画像 L2 (σ 0 ) と、 2σ 0 で平滑化を行った画像. L1 (2σ 0 ) には以下のような関係が成り立つ。 L1 (2σ 0 ) ≈ L2 (σ 0 ). (9). この関係を利用することで、 σ の最大値を制限することができるため、ガウシアンフィルタのウィンドウサイズによる計算量の増加を防ぐことができる。. ⅳ. 増加率 k. σ の増加率 k は、1 オクターブにおけるスケールスペースの分割数により決定する。スケールスペースの分割数を s とした場合、1 オクターブでは、スケールスペースは σ 0 から 2σ 0 1 s. まで増加するため、 σ の増加率 k は k = 2 となる。図 4 に示す DoG 処理の例では、 s = 2 1 2. であるため、 k = 2 =. 2 となる。極値探索には DoG 画像を 3 枚 1 組で処理する必要があ. るため、s 枚の極値検出の対象となる画像を得るためには、s + 2 枚の DoG 画像が必要となる。さらに、 s + 2 枚の DoG 画像を得るためには、 s + 3 枚の平滑化画像が必要になる。従って、 1 オクターブにおける平滑化の回数は s + 3 回となる。 [1]では、実験から分割数 s = 3 、初期値 σ 0 = 1.6 のとき、最適な特徴点を得ることができると報告されている。 1 枚の入力画像に対するオクターブ数は、入力画像のサイズに依存する。入力画像は、処理が進むにつれ、1/2 のサイズのダウンサンプリングを重ねる。ダウンサンプリングを続けた結果、画像の一辺のサイズがある値以下になったとき処理を終了する。この値は任意で設定することができ、値が大きければ少ないオクターブ数になり、小さければ多いオクターブ数になる。. 10.

(12) 図 4. 極値検出対象画像生成の流れ(s=2, k=√2 の場合)[9]. 11.

(13) ⅴ. DoG 画像からの極値検出 DoG は異なるスケールによる平滑化画像の差分であるため、DoG の値が大きくなる σ では、スケールの変化領域に情報量を多く含んでいると言える。そこで、DoG 画像から極値を検出し、特徴点とスケールを決定する。極値の検出は、図 5 のように 3 枚 1 組で行う。 DoG 画像の注目画素と、その周りの 26 近傍を比較し、極値であった場合、その画素を特徴点の候補として検出する。このとき極値検出は、σ の値の小さい DoG 画像から行う。一度極値が検出された画素は、より大きなスケールで極値が検出されても特徴点候補としない。この処理をスケールの異なる DoG 画像の全画素に対して行う。次に、スケールスペースの極値の性質について述べる。画像中のある座標におけるスケール変化と DoG 出力値の推移を図 6 に示す。赤い円で示すスケールサイズのとき、DoG 出力が最大(極大値)となっていることが、右のグラフからわかる。また、画像サイズを 2 倍に拡大した場合でも、赤い円で示すスケールにて DoG 値が最大となり、画像の同じ部分を囲むスケールが選択されることがわかる。このとき、元画像のスケールを σ 1 、2 倍に拡大した画像のスケールを σ 2 とすると、 σ 2 = 2σ 1 の関係が成り立つ。即ち、画像サイズが 2 倍になると、特徴点のスケールも比例して 2 倍となる。このように、SIFT は特徴を最も含むスケール σ を自動的に決定するため、空間的に同範囲の領域から特徴量を記述することで、拡大・縮小に不変な特徴量となる。. 図 5. 極値検出の流れ[9]. 12.

(14) 図 6. スケールと DoG 出力の関係[9]. 13.

(15) 2.3.2 特徴点のローカライズ検出された特徴点候補の中には、DoG 出力値が小さい点や、エッジ上の点が含まれており、これらの点はノイズや開口問題に影響を受けやすいという問題がある。そこで、特徴点候補の中から、主曲率とコントラストにより安定した特徴点に絞り込む。さらに、特徴点のサブピクセル推定により、位置とスケールを算出する。. ⅰ. 主曲率による特徴点の絞込みここでは、エッジ上に存在する特徴点候補の削除方法について述べる。特徴点候補における 2 次元ヘッセ行列 H を以下の式により計算し、主曲率を求める。.  D xx H =  D xy. D xy  D yy . (10). 行列内の導関数は、特徴点候補の位置での DoG 出力値の 2 次微分から得られる。ここで、ヘッセ行列から求められる第 1 固有値を α 、第 2 固有値を β (ただし α > β )とする。このときヘッセ行列の対角成分の和 Tr (H ) と行列式 Det ( H ) は次のように計算できる。. Tr ( H ) = D xx + D yy = α + β. (11). Det ( H ) = D xx D yy − (D xy ) = αβ. (12). 2. さらに、 γ を第 1 固有値と第 2 固有値の比率とし、 α = γβ とすると次式のようになる。. Tr (H ) (α + β ) = (γβ + β ) = (γ + 1) = Det (H ) αβ γ γβ 2 2. 2. 2. 2. (13). この値は固有値そのものではなく、固有値の比率で決まる。従って、固有値を求めずにエッジ上の点であるか否かを判別することが可能となる。この値を次に示す式によって閾値処理を行うことで、不要な特徴点候補を削除する。. 2 (γ + 1) Tr (H ) < th Det (H ) γ th. 2. (14). 14.

(16) 式(14)を満足するような点を、新たな特徴点候補とする。閾値は γ th により決定する。この処理は、Harris Corner Detector に良く似たもので、固有値の比率が閾値より大きい点、即ちエッジ上に存在する点は、開口問題の影響を受けるため削除される。[1]では γ th = 10 を採用しており、閾値は 12.1 となる。. ⅱ. 特徴点のサブピクセル位置推定ここでは、3 変数 ( x, y, σ ) の 2 次関数を適用することで、特徴点候補のサブピクセル位置とスケールを算出する。ある点 x = ( x, y, σ ) での DoG 画像 D ( ) をテイラー展開すると次 T. x. 式のようになる。. D ( x) = D +. ∂D T 1 ∂2D x + xT x ∂x 2 ∂x 2. (15). 式(15)について x に関する偏導関数を求め、0 とすると次式が得られる。. ∂D ∂ 2 D + xˆ = 0 ∂x ∂x 2. (16). このとき x̂ は特徴点候補(極値)のサブピクセル位置を表している。よって、式(16)を変形して次式を得る。. ∂2D ∂D xˆ = − 2 ∂x ∂x. (17). 式(17)は次のように表すことができる。. ∂2 D  2  ∂2x ∂ D  ∂xy  2 ∂ D  ∂xσ. ∂2D ∂xy ∂2D ∂y 2 ∂2D ∂yσ. ∂2D  ∂xσ  ∂2D ∂yσ   ∂2D ∂σ 2 .  ∂D   ∂x  x    y  = −  ∂D     ∂y  σ   ∂D     ∂σ . 15. (18).

(17) 式(18)を特徴候補点のサブピクセル位置 x̂ を得るために、以下のように変形する。. x  y   σ . ∂2D  2  ∂2x ∂ D = −  ∂xy  2 ∂ D  ∂xσ. ∂2D ∂xy ∂2D ∂y 2 ∂2D ∂yσ. ∂2D  ∂xσ  ∂2D ∂yσ   ∂2D ∂σ 2 . −1.  ∂D   ∂x   ∂D     ∂y   ∂D     ∂σ . (19). ˆ = (x, y, σ ) を算出する。式(19)を解くことにより、特徴候補点のサブピクセル位置 x ⅲ. コントラストによる特徴点の絞り込みここでは、サブピクセル位置での DoG 出力を算出し、コントラストにより特徴点の絞り込みを行う方法について述べる。まず、式(19)は次式のように表される。. ∂2D xˆ = − 2 ∂x. −1. ∂D ∂x. (20). 式(20)を式(15)に代入し、次式を得る。. D(xˆ ) = D +. 1 ∂D T xˆ 2 ∂x. (21). D は DoG 関数を表し、 x̂ はサブピクセル位置であるため、式(21)はサブピクセル位置での DOG 出力値となる。この DoG 値から特徴点を削除するか否かの判別を行う。[1]では、閾値として 0.03 を用いている。サブピクセル位置での DoG 出力の絶対値が閾値より小さい場合(コントラストが低い場合)は、ノイズに影響されやすいため削除する。. 16.

(18) 2.3.3 オリエンテーションの算出検出した特徴点に対して、description の第 1 段階であるオリエンテーションの算出を行う。オリエンテーションとは、特徴点における方向を表し、特徴量記述の際にオリエンテーションにより向きの正規化を行うことで、回転に不変となる。特徴点のオリエンテーションを求めるには、まず特徴点が検出された平滑化画像 L(u, v ) の勾配強度 m(u, v ) と、勾配方向 θ (u, v ) を以下の式により求める。. m(u, v ) =. f u (u, v ) + f v (u, v ) 2. θ (u, v ) = tan −1. 2. f v (u, v ) f u (u, v ). (22) (23).  f u (u , v ) = L(u + 1, v ) − L(u − 1, v )   f v (u, v ) = L(u, v + 1) − L(u, v − 1). (24). 局所領域における勾配強度 m( x, y ) と勾配方向 θ (x, y ) から図 7 に示すような重み付方向ヒストグラム h を以下の式により作成する。. hθ ′ = ∑∑ w( x, y ) ⋅ δ [θ ′, θ ( x, y )] x. (25). y. w( x, y ) = G ( x, y, σ ) ⋅ m( x, y ). (26). ここで、 hθ は、全方向を 36 方向に量子化したヒストグラムである。 w( x, y ) はある局所領域の画素 ( x, y ) での重みであり、特徴点が持つスケールサイズのガウス窓 G ( x, y, σ ) と勾配. 強度 m( x, y ) から求める。 δ は Kronecker のデルタ関数を表し、勾配方向 θ (x, y ) が量子化した方向 θ ′ に含まれるとき 1 を返す。また、このときのガウス窓による重み付けにより、. 特徴点に近い特徴量がより強く反映される。この 36 方向のヒストグラムの最大値から 80% 以上となるピークを特徴点のオリエンテーションとして割り当てる。図 7 の例では特徴点に割り当てられるオリエンテーションは 1 方向のみだが、図 8 のようにコーナー等の特徴点では 2 方向となり、 2 つのオリエンテーションを持つ。このように、 1 つの特徴点に対して複数のオリエンテーションが割り当てられる場合もある。. 17.

(19) 図 7. ヒストグラム作成の流れ[9]. 図 8. 2 方向のオリエンテーションを持つ特徴点[9]. 18.

(20) 2.3.4 特徴量の記述検出したオリエンテーションを基に、description の第 2 段階である特徴量の記述を行う。まず図 9 に示すように、座標軸を特徴点のオリエンテーション方向に回転させる。特徴量の記述には、特徴点周辺の領域が持つ勾配情報を用いる。使用する勾配情報は特徴点を中心とし、その特徴点が持つスケールを半径とした円領域内から求める。周辺領域を一辺 4 ブロックの計 16 ブロックに分割し、図 10 に示すようにブロックごとに 8 方向の勾配方向ヒストグラムを作成する。この勾配方向ヒストグラムは、特徴点のオリエンテーションを算出したときに作成したヒストグラムと同様の手法で求める。. 図 9. オリエンテーション方向への座標軸の回転[9] 図 10 の例では、4×4＝16 ブロックごとに各 8 方向のヒストグラムを作成するため、4× 4×8＝128 次元の特徴ベクトルとして特徴量を記述する。このように、特徴点が持つオリエンテーション方向に座標軸を合わせた領域で特徴を記述するため、回転に不変な特徴量となる。また、128 次元の各特徴ベクトルの長さはベクトルの総和で正規化する。これにより、照明変化に対して影響の少ない特徴量となる。. 図 10. ブロック単位での特徴量記述[9]. 19.

(21) 図 11 に、実際に画像に特徴量を記述した例を示す。画像には特徴点の位置と、オリエンテーションの方向を描画している。. 図 11. SIFT による特徴量記述例. 20.

(22) 2.4 SIFT の拡張 2.4.1 PCAPCA-SIFT PCA-SIFT[5]は、SIFT で検出した局所領域の勾配情報に対して主成分分析(PCA)を適用し、SIFT 特徴の頑健性や識別性を向上させる手法である。PCA-SIFT では、特徴点の検出とオリエンテーションの算出までの処理は SIFT と全く同じであり、特徴量記述のみが異なる。前述したように、SIFT では特徴点のスケールに対応した領域を 4×4 のブロックに分割し、ブロックごとに 8 方向の方向ヒストグラムを作成することで 128 次元の特徴量を記述する。一方、PCA-SIFT では、特徴点のスケールに対応した領域を 41×41 のパッチにリサンプリングする。リサンプリングしたパッチの水平・垂直方向の勾配を算出し、39×39 ×2 ＝3,042 次元の特徴量を得る。求めた 3,042 次元の特徴量に PCA を適用し、次元圧縮を行う。 PCA に用いる射影行列は、あらかじめ学習画像を用いて算出しておく。[5]では、21,000 個の特徴点から算出したパッチを用いて射影行列を求めている。圧縮する次元数は、実験により 36 次元が最も有効であることが報告されている。ノイズが加えられた画像、回転・スケール変化がある画像、視点の変化がある画像、輝度を低減させた画像に対して、SIFT と PCA-SIFT の比較実験の結果、どの場合においても PCA-SIFT の性能が SIFT の性能を上回っていることが報告されている。また、 PCA-SIFT の特徴量は低次元に圧縮されているため、SIFT よりも高速にマッチングを行うことが可能である。. 21.

(23) 2.4.2 BSIFT(Background BSIFT(Background and Scale Invariant Feature Transform) SIFT は対象物体以外の背景画素を含んだ特徴量記述を行うため、背景の影響を受けやすいという問題がある。これは特徴点検出と特徴量記述に使用するガウス窓が、物体領域と背景領域を含むからである。Stein らは、物体と背景の境界情報を用いることで、物体領域のみの情報による特徴点の検出と特徴量を記述する手法である BSIFT[6]を提案している。 BSIFT では、境界情報が重要であり、物体の境界情報が既知であるか、もしくはデプス画像等から境界情報が得られた画像を対象とする。. ⅰ. Background Invariant Detection SIFT は DoG の極値を特徴点として検出する。しかし、この方法では背景情報を含めて特徴点の検出を行う。そのため、同一物体でも異なる位置に特徴点が検出される場合がある。そこで、BSIFT では DoG のための平滑化として、ガウス関数ではなく以下の式を用いる。. I k +1 (u, v) ← I k (u, v) + τ∇ 2 I k (u, v). (27). ∂ I ∂ I + ∂u 2 ∂v 2. (28). 2. ∇ 2 I (u, v) =. 2. k は繰り返し回数である。式(28)は、ラプラシアンフィルタであり、式(27)は 2 次微分を用いた平滑化である。式(27)を用いることで、物体の境界に注目した平滑化を行うことができる。ここで τ を 0 に近づけたとき、 σ =. 2kτ でのガウシアンフィルタによる平滑化と. 同等の結果となる。[6]では、 τ ＝0.2 としている。. ⅱ. Background Invariant Description SIFT による特徴量の記述では、特徴点を中心としたガウス分布を重みとして、輝度勾配ヒストグラムを作成する。しかし、この方法では背景画素の情報も含んだ特徴を記述してしまう。特に境界付近においては背景の影響が大きいため、マッチング失敗の原因となる。そこで、BSIFT では特徴点を中心としたガウス分布と、境界情報を用いて距離変換した値を掛け合わせ、これを重み分布とする。図 12 にガウス分布と境界情報を用いた重み分布を示した。これを適用することにより、背景領域の影響を軽減した SIFT 特徴量を得ることができる。. 22.

(24) 2.5 対応点探索 SIFT により異なる画像間で抽出された各特徴点の特徴量を比較することで、画像間の対応点探索が可能となる。以下に対応点探索の流れを示す。画像 I 1 中のある特徴点 k I1 と、画像 I 2 中のある特徴点 k I 2 の特徴量をそれぞれ v. k I1. 、v. kI2. と. すると、特徴量間のユークリッド距離 d は次式により算出される。. (. k. d v I1 , v. kI 2. ) = ∑ (v 128. k I1 i. k. − vi I 2. ). 2. (29). i =1. 式(29)により、ある特徴点に対して、異なる画像中に含まれる全特徴点との特徴量間の距離. d を算出し、その中で最も d が最小となる点同士を対応点として検出する。実際に特徴点の対応点探索を行った結果を図 12 に示す。. 図 12. SIFT 特徴量を用いた対応点探索. 23.

(25) 第 3 章提案手法 3.1 エッジ上の特徴点における誤対応 3.1.1 開口問題ここでは、エッジ上に特徴点があるときに問題となる開口問題について述べる。SIFT のような局所特徴量においては、エッジ上の特徴点は似たパターンの領域が多く存在する可能性がある。このような場合、局所特徴量では図 13 に示すように、どれが正解の対応点か判断できないという問題が生じる。このことを穴から覗いたような局所領域での問題という意味で、開口問題(aperture problem)、窓問題、覗き穴問題などと呼ぶ。. 図 13. 開口問題(aperture problem). 24.

(26) 3.1.2 3.1.2 特徴点の誤対応特徴点の誤対応前述したように、SIFT では特徴点の検出を行った後、主曲率によりエッジ上に存在する不要な特徴点を削除している。しかし、実際にはエッジ上の特徴点全てを削除することはできていない。図 14 に赤い円で示すように、エッジ上の特徴点が少なからず残っている。図 15 には、この状態で対応点探索を行った例を示した。図 14 に示したエッジ上の特徴点で誤対応が起きているのがわかる。SIFT の画像マッチング等への応用を考えると、多くの対応点の中での 1,2 個の誤対応の場合は問題とはなりにくい。しかし、対応点が少ない場合は、少ない誤対応でもマッチング精度に関わる問題となる。次章では、このような問題を緩和するための手法を提案し、必要となる背景技術についても説明する。. 図 14. エッジ上の特徴点. 25.

(27) 図 15. エッジ上特徴点の誤対応例. 26.

(28) 3.2 DoB(DifferenceDoB(Difference-of-Bilateral) 前述した通り、SIFT では特徴点候補の絞り込みを行っているのにも関わらず、エッジ上の特徴点による誤対応が生じている。これは、図 14 からもわかるように、主曲率による特徴点の絞り込みにおいて、充分にエッジ上の特徴点が排除されていないためだと推測される。主曲率を求める際に用いられる 2 次元ヘッセ行列（式(10)）内の導関数は、特徴点候補位置での DoG 出力値の 2 次微分である。このことから、エッジ判定は DoG 画像上で行われていると言える。従って、DoG 画像上でエッジの判別をしやすくすることで、エッジ上の特徴点が排除されやすくなると考えられる。そこで、本稿では DoG 処理に用いられる平滑化処理に注目する。既存手法では、この平滑化に Gaussian フィルタを用いている。これに替わり、エッジを保存した平滑化を行う Bilateral フィルタ[10]を用いることで、エッジ判定の改善を図ることを提案する。本稿では、この処理を DoG と区別するために、 DoB(Difference-of-Bilateral)と呼ぶこととする。. 3.3 3.3 Bilateral Filter 一般的な画像では、注目画素に近い画素の輝度値は注目画素の輝度値と近く、注目画素から遠くなればなるほど、注目画素の輝度値とは差が大きくなる場合が多い。このことを考慮し、Gaussian フィルタでは、注目画素に近いほど平均値を計算するときの重みを大きくし、遠くなるほど重みを小さくなるよう、ガウス関数（式(7)）を用いている。 Bilateral フィルタは、画素間の距離だけで重みを決定するのではなく、輝度の差も考慮し、変化の大きいところは重みを小さくすることによってエッジを残す。. f (i, j ) を入力画像、 g (i, j ) を出力画像とすると、その処理は次式で表される。 m2 + n2 ( f (i, j ) − f (i + m, j + n)) 2 ) exp( − ) ∑∑ 2σ d2 2σ r2 n = − w m= − w g (i, j ) = w w m2 + n2 ( f (i, j ) − f (i + m, j + n)) 2 exp( − ) exp( − ) ∑∑ 2σ d2 2σ r2 n=− w m =− w w. w. f (i + m, j + n) exp(−. i, j は処理点を、 m, n は処理点の近傍画素までの距離、 w はフィルタサイズを表す。式(30) は、画像を平坦化する項とエッジの平滑化を抑制する項により構成されている。.  m2 + n2 exp − 2σ d2 .   は距離について重み付けを行い、画像を平滑化する項であり、 . 27.

(29)  ( f (i, j ) − f (i + m, j + n ))2   はエッジの平滑化を抑制する項である。 exp 2  2 σ r   ここで、 σ d は空間に対する標準偏差を表し、この値が大きくなるとフィルタのぼかし効果が大きくなる。 σ r は輝度に対する標準偏差を表し、この値が小さくなるとエッジが強く残る。図 16 に、パラメータを変えて Bilateral フィルタを適用した結果を示す。参考に、 Gaussian フィルタをパラメータを変えて適用した結果を図 17 に示した。σ r を大きくすると、Gaussian フィルタの結果に近づいていくのがわかる。. 図 16. パラメータによる Bilateral フィルタ効果の変化. 28.

(30) 図 17. パラメータによる Gaussian フィルタ効果の変化. 29.

(31) 第 4 章提案手法提案手法によるによる SIFT の特性と特性と対応点探索実験対応点探索実験 4.1 実験環境実験に用いたプログラムは、Rob Hess 氏[11]の OpenCV での SIFT 実装コードを元に作成した。以下の実験において、特に記述がない場合の基本的なパラメータは次に示すとおりである。表 1. 主なパラメータスケールσ初期値. 1.6. 低コントラスト点削除閾値エッジ上点削除閾値. 0.04 10. 4.2 DoB 画像図 18 に、平滑化処理に Bilateral フィルタを用いて生成した DoB 画像群の一部を示す。ただし、生成された DoB 画像は差分(白い部分)が弱く、見づらいため、図 18 に示した画像は差分値を強調したものである。また、図 19 には、DoG 画像と DoB 画像の比較を示した。上下は隣り合ったスケールの画像である。DoB 画像は DoG 画像に比べてエッジがはっきりとしているのがわかる。. 30.

(32) 図 18. DoB 画像群一例. 図 19. DoG 画像と DoB 画像の比較. 31.

(33) 4.3 特徴点の比較 4.3.1 特徴点の絞込み提案手法により記述された特徴点の変化を比較する。2.3.2 で述べたように、検出された特徴点には閾値処理を行い、エッジ上の特徴点と低コントラストの特徴点は排除する。図 20 に各閾値処理による特徴点の絞込みの様子を示す。提案手法において検出される特徴点数は、従来手法と比較して大幅に増加している。閾値処理による特徴点の絞込みに注目すると、提案手法において不利な特徴点が効果的に排除されていることがわかる。. 図 20. 特徴点の絞込み. 32.

(34) 4.3.2 同特徴点数における特徴点の比較従来手法、提案手法それぞれにおいて、エッジ上特徴点の排除、低コントラスト特徴点の排除の各閾値を調整し、ほぼ同数の特徴点数とした上で、その分布を比較した。図 21 にその結果を示す。従来手法と比べて提案手法では、閾値を高くしほぼ同数の特徴点としているため、特徴点のマッチングにおいて、より有効な特徴点が残っていると言える。（用途によってどのような特徴点分布が有効かは異なると思われる。後述する一般物体認識実験の項でも考察を行う。）. 図 21. 特徴点の比較（閾値調整）. 33.

(35) 4.4 σr の変動による特徴点への影響 3.3 で示した式中のσr を様々に設定し、検出される特徴点にどのような影響があるか実験を行った。σd については従来手法と同じ値を初期値として設定している。スケールスペース構築のため変動させるパラメータはσd であり、σr は一定値をとる。図 22, 23 に結果を示した。σr が大きくなるにつれ特徴点数は減少する。このとき、排除されるエッジ上の特徴点は増加し、排除される低コントラストの特徴点は減少する。. 4000 3500 3000. 特徴点数. 2500 特徴点数エッジ上点低コントラスト点. 2000 1500 1000 500 0 0. 0.2. 0.4. 0.6. 0.8. sigma. 図 22. σr と特徴点数の関係. 34. 1.

(36) 図 23. 各σr における特徴点. 35.

(37) 4.4 勾配方向ヒストグラムの比較勾配方向ヒストグラムの比較従来手法と提案手法について、特徴点のオリエンテーションを算出する際に作成される、全方向を 36 方向に量子化した勾配方向ヒストグラムの比較を行う。図 24 に、各手法における同一座標の特徴点の方向ヒストグラムの例を示す。このヒストグラムの最大値から 80%以上のピークがその特徴点のオリエンテーションとして割り当てられる。各手法共にピークが表れている方向は同じであり、割り当てられるオリエンテーションは変わらないことがわかる。. 図 24. 勾配方向ヒストグラムの比較. 36.

(38) 4.6 特徴ベクトルの比較従来手法と提案手法において、記述される特徴量の比較を行う。図 25 に、同一座標の特徴点において記述された特徴量の例を示す。画像中左上の円の中心が特徴点の位置であり、円は特徴を記述する範囲であるスケールを表す。また、円の中心から伸びる直線の方向は、その特徴点のオリエンテーションである。提案手法では、従来手法に対して大きいスケールが選択されている。また、記述された特徴量については、(a), (b)間のユークリッド距離は 254.2 と大きく、異なる特徴量が記述されていると言える。. 図 25. 特徴ベクトルの比較. 37.

(39) 4.7 画像変化に対する頑健性提案手法での、回転、スケール変化、照明変化、圧縮、アフィン変化による特徴量の影響について実験を行った。元画像に対して、回転・スケール変化・照明変化・JPEG 圧縮・アフィン変化の 5 種類の画像を用意し、ある特徴点一点に注目して画像変化に対する特徴量への影響について比較する。図 26 に各変化に対する 128 次元の SIFT 特徴量を示す。(b), (c), (d), (e)に示す画像変化に対する特徴量と原画像の特徴量とのユークリッド距離はどれも小さく、同じような特徴が記述できていると言える。しかし、(f)に示すアフィン変化の場合は、ユークリッド距離が大きくなっている。歪みの変化が含まれる場合は、スケールと方向を正規化して特徴を記述するだけでは不十分である。従来手法においても同様に、微小なアフィン変化にはある程度頑健であるが、不変ではない。. 38.

(40) 図 26. 画像変化に対する特徴量の頑健性. 39.

(41) 表 2. 各画像変化における特徴量間のユークリッド距離画像変化. ユークリッド距離. (a)回転. 60.6. (b)拡大. 42.5. (c)照明変化. 6.2. (d)JPEG 圧縮. 68.3. (e)アフィン変換. 258.2. 図 27. 各画像変化における特徴量間のユークリッド距離. 40.

(42) 4.8 対応点探索実験ここでは提案手法により、記述された特徴量にどのような変化があるかを確認する。また、図 14,15 と比較することにより、本手法の有効性を示す。図 28 は、特徴量の位置とベクトルを描画した画像である。このとき、特徴点数は従来手法が 2,038 個、提案手法が 5,672 個であった。特徴点の数が増加しているのは、輝度に関しても重み付けを行う平滑化処理を行っているため、DoB 画像の情報量が増えたためだと考えられる。次に、図 29 に対応点探索を行った結果を示す。従来手法で誤対応となっていたエッジ上の対応点は見られなくなり、対応点数も増加している。. 図 28. 特徴量の比較. 図 29. 対応点探索結果の比較. 41.

(43) 4.9 4.9 対応点探索精度の向上ある画像と、その画像から一部分を切り出し、2 倍に拡大した画像の間で対応点探索を行った実験結果を報告する。実験は同様の方法で作成した 10 組の画像で行った。表 3 に実験結果を示す。図 30 はこの実験結果の一例である。表 3. 対応点探索における対応点数と計算時間従来手法 No.. 提案手法. 対応点数. 誤対応点. 計算時間. 対応点数. 誤対応点. 計算時間. (個). (個). (ms). (個). (個). (ms). 1. 0. 0. 365. 2. 0. 3,566. 2. 1. 1. 378. 2. 0. 3,589. 3. 7. 1. 471. 24. 1. 4,422. 4. 2. 1. 396. 6. 0. 4,194. 5. 1. 0. 350. 5. 0. 4,113. 6. 1. 1. 368. 6. 1. 4,118. 7. 6. 4. 397. 16. 1. 4,207. 8. 6. 1. 428. 12. 0. 4,305. 9. 8. 1. 620. 28. 0. 6,108. 10. 2. 1. 612. 6. 0. 5,095. 3.4. 1. 438.5. 10.7. 0.3. 4,371.7. 平均. 図 30. 実験結果の一例(No.7). 42.

(44) 対応点数は約 3 倍に増え、誤対応点数は 3 分の 1 に減ったことがわかる。また、従来手法では、対応点数に対して誤対応の占める割合が約 29.4％であるのに対し、提案手法では約 2.8％と改善されている。しかし、計算時間はおよそ 10 倍に増加している。. 4.10 エッジ上の特徴点エッジ上の特徴点の削除処理について、さらに詳しく実験を行った。図 31 に示す 10 枚の画像について、エッジ上特徴点の削除処理の際に、閾値処理に使用した固有値の比率（p.13, 式(14)の左辺の値）を比較する。画像サイズは全て 256×256 に揃え、削除された点の式(14) における γ th は 10、閾値は 12.1 で実験を行った。表 4 に、削除された点の固有値の比率と、特徴点として採用された点の固有値の比率の、それぞれ最大値と最小値を示す。まず平均値を見ると、固有値の比率の最大値は約 1.3 倍に上昇している。この値だけではエッジ上の点が削除されやすくなったとは言えないが、エッジ上の点の値が全体的に上昇していると推測するならば、エッジ上の特徴点が削除されやすくなったと言える。図 33 では、画像によって結果が大きく変わっている。. 図 31. 実験に用いた画像 10 枚. 43.

(45) 表 4. 閾値処理の際の固有値比率従来手法 Edge like. Total. points. features. Edge(max). Edge(min). Keypoint(max). Keypoint(min). a. 125.77. 12.11. 12.09. 4.00. 198. 293. b. 241.32. 12.14. 11.95. 4.00. 43. 459. c. 43.79. 12.20. 11.95. 4.00. 30. 422. d. 288.16. 12.11. 11.90. 4.00. 72. 519. e. 57.52. 12.14. 12.07. 4.00. 23. 495. f. 174.78. 12.22. 12.10. 4.00. 84. 717. g. 121.39. 12.16. 12.07. 4.00. 59. 471. h. 321.22. 12.56. 12.06. 4.00. 123. 300. i. 339.89. 12.16. 12.09. 4.01. 115. 311. j. 166.83. 12.23. 12.09. 4.00. 136. 600. 平均. 188.06. 12.20. 12.04. 4.00. 88.3. 458.7. 提案手法 Edge like. Total. points. features. Edge(max). Edge(min). Keypoint(max). Keypoint(min). a. 604.78. 12.11. 12.03. 4.00. 463. 1149. b. 199.59. 12.11. 12.05. 4.00. 235. 4697. c. 120.11. 12.15. 12.09. 4.00. 47. 645. d. 378.82. 12.16. 12.08. 4.00. 209. 1821. e. 98.80. 12.11. 12.04. 4.00. 165. 5607. f. 146.97. 12.11. 12.05. 4.00. 184. 3188. g. 128.24. 12.13. 12.08. 4.00. 135. 2290. h. 325.28. 12.13. 12.06. 4.00. 386. 1255. i. 143.25. 12.12. 12.09. 4.01. 245. 638. j. 362.18. 12.11. 12.08. 4.00. 615. 4064. 平均. 250.80. 12.13. 12.07. 4.00. 268.4. 2535.4. 44.

(46) 300. 250. 固有値比率. 200. 提案手法従来手法. 150. 100. 50. 0 Edge(max). Edge(min). Key(max). Key(min). 図 32. 閾値処理の際の固有値比率 700 600. 固有値比率. 500 400. 提案手法従来手法. 300 200 100 0 a. b. c. d. e. f. g. 画像. 図 33. 各画像ごとの比較. 45. h. i. j.

(47) 4.11 処理時間の計測提案手法における計算時間増大の原因を特定するため、処理ごとの計算時間を計測した。従来手法についても同様に計測し、処理時間の比較を行った。計測には 256*256 の画像を用いた。表 5 に同じ条件での計測 10 回の平均値を示す。実験の結果、フィルタ処理部分において処理時間の増加が特に著しいことがわかった。特徴量の記述処理においても処理時間が増加しているが、オリエンテーション算出や特徴量の記述といった処理は、特徴点の個数分の計算を行っているため、検出される特徴点の増加によるものと考えられる。表 5. 各処理時間の計測 (単位: ms) 従来手法. 提案手法. 293. 1149. 63. 1308. (61). (1306). 4. 4. 3. 特徴点のローカライズ. 29. 39. 4. オリエンテーション算出. 17. 77. 5. 特徴量の記述. 83. 349. 275. 1934. 特徴点数(個) 1. 平滑化画像群生成 (内、フィルタ処理) 2. 差分画像群生成. Total. 1400. 処理時間(ms). 1200 1000 800. 従来手法提案手法. 600 400 200 0 1. 2. 3. 4. 5. 処理内容図 34. 各処理内容に対する処理時間 (処理内容の番号は表 3 に従う). 46.

(48) 第 5 章高速化実装 5.1 GPGPU による高速化 5.1.1 GPGPU 近年、GPU は高性能化を続け、GPU を汎用計算に利用する GPGPU(General-purpose computing on graphics processing units)が注目を集めている。図 35 は CPU と GPU の性能差を表したグラフである。性能は 1 秒あたりの浮動小数点演算性能として表している。 2003 年頃は CPU と GPU の性能差は僅かだが、高性能化が進むに連れ、その差は大きくなっていき、2008 年には 10 倍程度に広がっている。そこで、本研究では処理時間増加が著しいフィルタ処理部分に GPGPU を用いることで、高速化を図る。. 図 35. CPU と GPU の性能比較[12]. 47.

(49) 5.1.2 CUDA GPGPU には、様々な方法が提案されている。その中でも近年注目を集めているのは NVIDIA 社が提供する「CUDA (Compute Unified Device Architecture)」である。CUDA は C/C++言語で GPU プログラミングを行う統合開発環境である。従来、GPU プログラミングを行うためには GLSL (OpenGL Shading Language) のようなシェーダ言語を使用する必要があった。しかし、シェーダ言語では、グラフィックスパイプラインを意識したプログラミングを行う必要があり、グラフィックス処理に合わせたアルゴリズムの変更を余儀なくされた。これに対し、 CUDA では通常の C/C++言語の関数を呼び出すように GPU を利用できる。このため、GPU プログラミングに特化した知識は不要であり、既存のアルゴリズムの移植も容易であるという特徴がある。今回は、CUDA を用いてフィルタ部分の GPGPU 実装を行った。. 5.1.3 CUDA のプログラミングモデル CUDA は GPU を、多数のスレッドが高い並列性をもって処理を行うデバイスとして扱う。 GPU は多数の演算コアを持ち、数百ものスレッドを並列に処理することが可能なため、 CUDA にはスレッドを階層的に管理する仕組みが導入されている。 CUDA がモデル化するデバイスは SM(Streaming Multiprocessor)と、SP(Streaming Processor)から構成される。デバイスは複数の SM を持ち、それぞれの SM が複数の SP を持つという二段階の並列性がある。各 SP 上でスレッド化されたカーネル(デバイス側で動作させる関数)を並行動作させることでアプリケーションの高速化が実現できる。 CUDA の並列プログラミングモデルにおける「スレッド」とは、一般的なマルチスレッドの「スレッド」という用語とは意味が異なり、ここで言うスレッドとは、各 SP で実行される処理単位のことだけを指す。カーネルを呼び出すと、そのカーネルは GPU 上で複数のスレッドとなって並列動作する。全てのスレッドは同じコードを実行し、各スレッドはメモリアドレスを計算し、制御を決定するための ID を持つ。 CUDA では、図 37 に示すようにブロックとグリッドの 2 つの階層でスレッドを管理する。具体的には、スレッドのまとまりをブロックと呼び、ブロックのまとまりをグリッドと呼ぶ。CUDA ではグリッドを 1 つの単位として処理を実行する。実際には、処理毎にスレッドとブロックの数を決定して処理を実行することになる。. 48.

(50) 図 36. スレッドの処理[18]. 図 37. 階層的なスレッド管理[18]. 49.

(51) 5.2 実験 5.2.1 Bilateral Filter 実装まず、Bilateral Filter のみを画像に適用するプログラムを作成し、比較を行った。プログラムは OpenCV の cvSmooth()関数を用いたものと、CUDA で実装したものの 2 つを用意し、画像の解像度を変えて、それぞれの処理速度の計測を行った。CUDA での実装は、フィルタ処理における画素値算出を画素ごとにスレッドで並列計算させる方法で実装を行った。実験には NVIDIA GeForce GTX260 を使用した。図 38 にフィルタ処理を 100 回行った場合の各解像度での処理時間を示す。 CUDA は OpenCV と比べ、解像度 128×128 で約 4 倍、320×320 で約 8 倍、512×512 では約 10 倍高速という結果となった。この結果は、CPU 上のメモリと GPU 上のメモリ間のデータの受け渡し等も含めた処理時間であり、GPU で実行されるフィルタ処理自体は 0.03ms 程である。これは、画素単位で並列処理しているため、解像度が変化しても一定である。. 8000. 処理時間(ms). 7000 6000 5000. OpenCV CUDA. 4000 3000 2000 1000 0 0. 50000 100000 150000 200000 250000 300000. 画素数図 38. Bilateral Filter 処理速度比較(OpenCV vs CUDA). 50.

(52) 5.2.2 SIFT への組込み CUDA で実装した Bilateral Filter を SIFT に組込み、提案手法の高速化を行った。高速化前後での処理時間の比較結果を表 6, 及び図 39 に示す。低解像度ではフィルタ回数も少なく、処理を行う画素数も少ないため高速化の効果が薄いが、512×512 の画像では全体で約 6 倍、フィルタ処理部分は約 14 倍の高速化に成功した。高速化以前では、Bilateral Filter の処理時間が全体の処理時間の大半を占めていたが、高速化後では全体の 40%程に止まっている。また、従来手法についても Gaussian Filter 部分を CUDA で実装し、処理速度の比較を行った。従来手法と提案手法の処理速度比較結果を、CPU 動作の場合を図 40 に、GPU 動作の場合を図 41 に示す。CUDA を用いてフィルタ部分の実装を行うことで、提案手法の処理時間を従来手法に近づけることができた。表 6. SIFT 処理速度比較処理時間(ms). 解像度. 総フィルタ回数. 64*64. 25. 129(85). 186(106). 128*128. 30. 471(335). 296(139). 192*192. 30. 991(745). 371(152). 256*256. 35. 1737(1318). 518(210). 320*320. 35. 2660(2052). 631(242). 384*384. 35. 3752(2967). 753(275). 448*448. 35. 5009(4035). 880(323). 512*512. 40. 6410(5270). 1026(390). OpenCV. CUDA. ※括弧内はフィルタ処理時間. 7000. 処理時間(ms). 6000 5000. OpenCV 〃(フィルタ処理) CUDA 〃(フィルタ処理). 4000 3000 2000 1000 0 0. 100000. 200000. 300000. 画素数. 図 39. SIFT 処理速度比較(OpenCV vs. CUDA). 51.

(53) 7000. 処理時間(ms). 6000 5000. 提案手法〃(フィルタ処理) 従来手法〃(フィルタ処理). 4000 3000 2000 1000 0 0. 100000. 200000. 300000. 画素数図 40. SIFT_CPU 処理速度比較(Bilateral vs. Gaussian). 1200. 処理時間(ms). 1000 800. 提案手法〃(フィルタ処理) 従来手法〃(フィルタ処理). 600 400 200 0 0. 100000. 200000. 300000. 画素数図 41. SIFT_GPU 処理速度比較(Bilateral vs. Gaussian). 52.

(54) 第 6 章一般物体認識への一般物体認識への応用への応用 6.1 6.1 一般物体認識ある特定の制約下で撮影された画像ではなく、制約のない「一般的」な画像に対して、計算機が画像中に含まれる物体を一般的な名称、たとえば「鞄」「靴」「椅子」などの名称で認識することを一般物体認識(generic object recognition)と呼ぶ。本研究では、一般物体認識には Bag-of-Keypoints[13] と呼ばれる手法を用いる。 Bag-of-Keypoints は局所領域の特徴量のみで認識を行う手法である。局所特徴の特徴ベクトルをベクトル量子化することで、画像を局所特徴の集合と捉える。このベクトル量子化された特徴は visual word と呼ばれ、画像はこの visual word の出現頻度ヒストグラムで表現される。ここでは、局所特徴を SIFT 特徴量で表し、全ての特徴量を k-means クラスタリングして codebook（visual word の集合）を作成し、さらにこの codebook を用いて学習画像、テスト画像両方の特徴量をベクトル量子化する。この結果から SVM (Support Vector Machine)を用いて学習と識別を行う。SVM は高い性能を持ったクラス分類手法であり、様々な画像認識問題に応用されている。図 42 に本研究で用いる一般物体認識のプログラムの概要を示す。. 図 42. Bag-of-Keypoints による一般物体認識の流れ. 53.

(55) 6.2 実験概要一般物体認識に用いる特徴量として、従来手法、提案手法のそれぞれにおける SIFT 特徴量を用いた場合について、その識別率の比較を行った。実験項目は主に以下の 3 項目である。 A) 各パラメータ固定での識別率比較 B) (A)におけるカテゴリごとの識別率と特徴点数 C) 閾値による識別率の変動学習画像には Caltech-256[19]の 20 カテゴリを用いて実験を行う。学習画像、テスト画像ともに各 40 枚を用いる。一般物体認識のプロセスにおけるクラスタリング手法には k-means を用い、 SVM 識別器によって識別を行う。 Visual Word 数は 100 ごとに 100~1000 まで実験を行い、そのうち最も識別率の高かったものを、その手法を用いた場合の識別率として採用した。(C)における閾値とは、エッジ上の特徴点排除, 低コントラストの特徴点排除のそれぞれの処理に用いる 2 つの閾値とし、それぞれの閾値を変化させたときの識別率を比較する。識別率は 20 カテゴリの平均識別率である。(A), (B)では、各閾値を従来手法での推奨値とされる 10.0, 0.4 とした。. 54.

(56) 6.3 実験結果 (A)～(C)の実験結果を以下の図 43~46 に示す。 A) 各パラメータ固定での識別率比較 0.45 0.4 0.35. 識別率. 0.3 0.25. Bilateral Gaussian. 0.2 0.15 0.1 0.05 0 1000. 900. 800. 700. 600 500 Visual Words. 400. 300. 200. 100. 図43. 識別率の比較. B) (A)におけるカテゴリごとの識別率と特徴点数 0.7. 10000 9000. 0.6 8000. 識別率. 0.5. 7000 6000. 0.4. 5000 0.3. 4000 3000. 0.2. 2000 0.1 1000 0. 0 1. 2. 3. 4. 5. 6. 7. 8. 9 10 11 12 13 14 15 16 17 18 19 20 カテゴリ No.. 図44. カテゴリごとの識別率と特徴点数. 55. 特徴点数(DoG) 特徴点数(DoB) 識別率(DoG) 識別率(DoB).

(57) C) 閾値による識別率の変動. 図45. 閾値による識別率の変動 (左: 従来手法, 右: 提案手法). 図 46. 閾値による特徴点数の変動 (左: 従来手法, 右: 提案手法). 実験結果(A)では、どの Visual Word 数の結果であっても、提案手法は従来手法に比べて識別率が高い結果となっている。一方で、実験結果(B)のカテゴリごとの識別率の結果を見ると、従来手法よりも識別率が劣るカテゴリも存在する。また実験(C)では、提案手法における識別率の変動が従来手法と比較して大きいことから、提案手法では閾値設定の影響が大きいことがわかる。さらに、図 46 に示した特徴点数を考慮すると、特徴点数よりも閾値設定が識別率に大きく影響していると言える。. 56.

(58) さらに、図 44 に示したカテゴリごとの識別率について、いくつかのカテゴリの画像例とその特徴点分布を図 47 に示し、カテゴリ内の画像の傾向と識別率の関係を考察する。図中(a), (b), (c)は識別率が高いカテゴリであり、特徴点がそのカテゴリ共通の特徴である部分に多く分布している傾向がある。例えば、(a)はバスケットゴールのカテゴリでネットの部分、(c)ではチェス盤のカテゴリで盤面のチェスパターンに特徴点が多いというように、多く分布した特徴点が有効に働くと考えられる画像のカテゴリである。(b)はこのキャラクターのカテゴリであり、特徴点は輪郭に多く分布している。このキャラクターは多くの場合、正面からのみ描かれるため、輪郭上の特徴点は有効に働くものと考えられる。次に、(d), (e)は識別率が低いカテゴリである。まず、(d)は CD のカテゴリで、(b)とは対照的にその盤面に特徴点が多く検出される。しかし、このカテゴリで識別に有効に働く特徴は CD の輪郭の特徴であり、盤面は画像によって様々であるため、多く特徴点が分布しているほど識別率は低くなると考えられる。(e)も同様に、蛙の模様がカテゴリ内の画像に共通のものではないため、特徴点数が多いにも関わらず識別率が低い結果となっている。以上の結果から、画像内で特徴点が集中する部分が、識別に有効に働くかどうかが識別率を左右すると考えられる。. 図 47. カテゴリ内の画像と識別率の関係. 57.

(59) 6.4 6.4 閾値によるカテゴリごとの識別率の変化図 45, 46 に各閾値による識別率の変化を示したが、これは 20 カテゴリの平均識別率である。図 48, 49 に、このときのカテゴリごとの識別率を示した。どちらの閾値においても、最も識別率が高くなる閾値設定はカテゴリによって異なる。画像の傾向から、そのカテゴリに適した閾値設定を推測することで、常に最も高い識別率となる閾値を適応的に選択することが出来れば、さらなる改善が見込めると思われる。 0.8 0.7 0.6. 識別率. 0.5 2 6 10. 0.4 0.3 0.2 0.1 0 1. 2. 3. 4. 5. 6. 7. 8. 9. 10 11 12 カテゴリNo.. 13. 14. 15. 16. 17. 18. 19. 20. 図 48. 閾値によるカテゴリ別識別率 (コントラスト閾値 0.04、エッジ閾値 2, 6, 10). 0.8 0.7 0.6. 識別率. 0.5 0.04 0.06 0.08. 0.4 0.3 0.2 0.1 0 1. 2. 3. 4. 5. 6. 7. 8. 9. 10 11 12 カテゴリNo.. 13. 14. 15. 16. 17. 18. 19. 20. 図 49. 閾値によるカテゴリ別識別率 (コントラスト閾値 0.04, 0.06, 0.08、エッジ閾値 10). 58.

(60) 第 7 章総括 7.1 まとめ本研究では、Bilateral Filter を用いた SIFT の性能改善についての提案、及びその評価と応用に関して実験を行った。まず従来研究として、SIFT のアルゴリズムについて説明し、 SIFT の平滑化処理に、Gaussian フィルタに替わり Bilateral フィルタを適用することを提案した。また、実験によりエッジ上の特徴点の誤対応の減少を確認し、本手法の効果を示した。さらに、輝度についても重み付けをしているため、差分画像間の情報量が増え、多くの特徴が抽出される結果となった。しかし、計算量の観点から見ると問題があり、高速化が必要とされた。そこで、本論文では CUDA による高速化実装を行った。その結果、提案手法の有効性は損なうことなく、従来手法と同程度まで計算速度を近づけることができた。さらに、一般物体認識における識別率を比較し、提案手法により抽出された特徴量を用いた場合、全体的に識別率が向上することを確認した。. 7.2 今後の課題本手法では、従来手法に比べて特徴点数が大幅に増加し、画像間のマッチング等の用途においては SIFT の性能向上が見込める。しかし、一般物体認識の実験では、特徴点数が多いことは必ずしも有利ではなく、適切な閾値の設定が識別率に影響を及ぼすことがわかった。画像のエッジや細部の状態によってクラス分けを行い、各々のクラスごとに適切なパラメータを推測することによって、画像の傾向によって適応的にパラメータを設定することが出来れば、一般物体認識においても、その他の用途においても提案手法がより有効に働くと考えられる。. 59.