ビジュアル情報処理

(1)

コンピュータビジョン特論

Advanced Computer Vision

第5回

最適なエッジ検出器

Canny Edge Detector



良いエッジ検出器とは

• Good Detection: ノイズに強い

• Good Localization: 真のエッジの所を検出

• Single Response:各点に一本のエッジを検出

Canny Edge Detection Tutorial

http://www.pages.drexel.edu/~weg22/can_tut.html

Canny Edge Detector の処理手順

1.

Gaussianフィルタで画像を平滑化

2.

平滑化された画像の微分を計算

3.

勾配の大きさと方向を求める

4.

“Non-maximum Suppression”処理を行う

5.

“Hysteresis Threshold”処理を行う

Canny Edge Detector

１．Gaussianフィルタで画像を平滑化

２．平滑化された画像の微分を計算

I

y

x

g

y

x

g

I

S





(

,

)



(

,

)



2 2 2 2 2 1 ) , (    y x e y x g   



g

I

  

g

I

S















































y x

g

y

g

x

g

I

g

S

y x y x

































_















I

g

I

g

y x

Canny Edge Detector

Derivative of Gaussian

2 2 2 2

2

1 )

,

(





y x

e

y

x

g

 



)

,

(

x

y

g

x

)

,

(

x

y

g

y

Canny Edge Detector

ステップ１と２処理後の結果例

x

S

y

S

I

入力画像

(2)

Canny Edge Detector

ステップ３処理後の結果例

３．勾配の大きさと方向を求める

x y y x y x S S S S S S 1 2 2 tan ) , (       方向大きさ勾配ベクトル入力画像勾配の大きさ

Canny Edge Detector

４．“

Non-maximum Suppression

”処理を行う

勾配（エッジ）方向に沿って、画素はローカル最大か否かをチェック（非最大エッジ抑制）



x,y



 

x,y



x,y



 





 





                 otherwise if 0 , , & , , , , S x y S x y y x S y x S y x S y x M

Canny Edge Detector

４．“

Non-maximum Suppression

”処理を行う

勾配（エッジ）方向に沿って、画素qはローカル最大か

否かをチェック（非最大エッジ抑制）するとき

•内挿画素pとrをチェックすることになる

Canny Edge Detector

勾配方向の量子化

4142 0 tan 4142 2 -: 3 4142 2 | tan | : 2 4142 2 tan 4142 0 : 1 4142 0 tan 4142 0 : 0 : ons) Quantizati ( . θ . . θ . θ . . θ . -        角度を量子化 x y

S

θ



tan

0 1 2 3

内挿画素の問題を解決するため

次のエッジ点

を予測

Assume the marked point is an edge point. Then we construct the tangent to the edge curve (which is normal to the gradient at that point) and use this to predict the next points (here either r or s).

(Forsyth & Ponce)

Canny Edge Detector

Non-Maximum Suppression

の処理結果

2 2 y x S S S   M（細線化） 25  Threshold M ion visualizat For 2値化処理 Step 3 Step 4

(3)

Canny Edge Detector

５．

“Hysteresis Threshold”

処理を行う

Scan the image from left to right, top-bottom. If the gradient at a pixel is

• above “High”, declare it an ‘edge pixel’

• below “Low”, declare it a “non-edge-pixel”

High low Gradient magnitude ‘edge pixel’ •“non-edge-pixel” ヒステリシス閾処理

Canny Edge Detector

５．

“Hysteresis Threshold”

処理を行う

If the gradient at a pixel is

• between “low” and “high”

•Consider its neighbors iteratively then declare it an “edge pixel” if it is connectedto an ‘edge pixel’ directly or via pixels between “low” and “high”.

High low Gradient magnitude ‘edge pixel’ •“non-edge-pixel” ヒステリシス閾処理

Canny Edge Detector

“Hysteresis Threshold”

処理を行う



Connectedness

x x x

4 connected 8 connected 6 connected

x

6 connected

Canny Edge Detector

Hysteresis Threshold

処理結果例

25 regular

M



15

35 



Hysteresis

Low

High

（細線化）

M

Step 5

Effect of



(Gaussian kernel size)

Canny with Canny with original



The choice of depends on desired behavior

• large detects large scale edges (割と低周波数)

• small detects fine features (高周波数まで)

• 注：OpenCVのライブラリ内のは3, 5, 7ができる

Canny Edge Detector

全体像

Input Image gx(x,y) Gradient magnitude gy(x,y) Gradient direction Non-maximum suppression Hysteresis thresholding

(4)

出席チェック4-1

Canny Edge Detectorの処理流れは式を入れながら述べてください。

OpenCVではCanny Edge Detectorのサンプルプログラムがあります。関連パラメータを調整しながら、好きな一枚の画像のエッジを検出してください。レポートには元画像、使ったパラメータ、選定理由と処理後の画像をそれぞれ記述してください。

レポート3

提出期限： ３週間以内（講義の時 OR 私の部屋（A612））

Types of invariance



Illumination

Types of invariance



Illumination



Scale

Types of invariance



Illumination



Scale



Rotation

Types of invariance



Illumination



Scale



Rotation



Affine

Types of invariance



Illumination



Scale



Rotation



Affine



Full Perspective

(5)

SIFT

(

Scale-Invariant Feature Transform

)

http://www.vision.cs.chubu.ac.jp/SIFT/

特徴点の検出・特徴量の記述を行うアルゴリズム

検出した特徴点に対し、

頑健な特徴量の記述が可能

・スケールの変化 ・画像の回転 ・照明条件の変化 ・

スケールとキーポイント検出



キーポイントのローカライズ



オリエンテーションの割り当て



特徴量記述

detection description

処理は2段階に分ける：

Local Features:

Detectors & Descriptors

Detected Interest Points/Regions Descriptors <0 12 31 0 0 23 …> <5 0 0 11 37 15 …> <14 21 10 0 3 22 …> 128次元のベクトル

Difference-of-Gaussian(DoG)

 異なるの平滑化画像の差分によりDoG画像を生成   

L(x,y,)G(x,y,)I(x,y)



D(x,y,)L(x,y,k)L(x,y,)

L(x, y,)  I(x, y)  G(x, y,)  D(x, y,)  k ：入力画像：ガウス関数：DoG画像：増加率ー：平滑化画像  0  k0 平滑化画像 DoG画像入力画像  G(x, y,) 1 22exp x2__y2 22       ) ) , , ( ) , , ( ( ) , , ( ) ) , , , ( ) , , , ( ) , , , ( ( ) , , , ( 2 2 2 2 2 2 2 2 2 2 y y x G x y x G a y x G z t z y x F y t z y x F x t z y x F a t t z y x F                         　　の関連：熱伝導の微分方程式と

スケールとキーポイント検出１

Difference-of-Gaussian(DoG)画像から、極値を検出し、キーポイントと、そのスケール情報を決定   D  k D

 

_k2 D

 

_k3 D

 

_k4 D

DOG画像の実例

Differences



k

スケールとキーポイント検出２

Difference-of-Gaussian(DoG)画像から、極値を検出し、キーポイントと、そのスケールを決定

 

 D

 

k D

 

2 k D

Choose all extrema within 3x3x3 neighborhood.

26近傍の最大・最小値からキーポイントを検出、

(6)

オリエンテーションの割り当て

キーポイントの周辺領域から、勾配強度＊Gaussian重みの勾配方向ヒストグラムを求め、ピークをオリエンテーションとして割り当てる。（ピークは複数個の可能性がある） 0 1.0 0.8 35 Histogram Peak

＊

Gaussian Gradient Feature Point

ＳＩＦＴ特徴量記述（１２８次元）

Gaussian Orientation Gradient Features 4 4 8 Feature Point (１)キーポイントのスケールによって定まる周辺領域を、オリエンテーションに従い回転させる。 (２)周辺領域を、キーポイントからの距離によるガウス窓で重み付け (３)周辺領域を４×４の１６個の小領域に分け、各小領域で８方向の勾配方向ヒストグラムを求める(4X4X8=128) 回転及びスケールに不変な１２８次元の特徴量を得る Orientation Feature Point SIFTにより、FeaturePoint,Orientation,Scaleは、決定済み。

ＳＩＦＴ特徴量記述（１２８次元）

4 回転及びスケールに不変な１２８次元の特徴量を得る 回転スケール変化

ＳＩＦＴ特徴量記述（１２８次元）

128次元の各特徴ベクトルの長さはベクトルの総

和で正規化

→ キーポイントは照明変化に対する影響の

少ない特徴量となる

輝度変化回転スケール変化輝度変化アフィン変化 不変とは言えない

SIFTの対応点探索による画像のマッチング

異なる画像間で抽出されたキーポイントの特徴量を比較することで画像間の対応点探索が可能 • 128次元のSIFT特徴量間のユークリッド距離dを算出  d(vkI 1_,vkI 2₎ _(v i kI 1_v i kI 2₎2 i1 128



dが最小となる点→対応点 → d1/d2の比が十分小さい 画像I1 画像I2 k：キーポイント vk_{：キーポイントの特徴量} d:68 d:47 d:54 d:12

(7)

Correspondence

Images from: M. Brown and D. G. Lowe. Recognising Panoramas. In Proceedings of the )

the International Conference on Computer Vision (ICCV2003

Recognition under occlusion

見え隠れのある物体で識別が可能になる

対応点が3点以上取れば、識別が可能

Image Registration Results

[Brown & Lowe 2003]

パノラマ画像の統合が可能になる

一般物体認識

Bag of Features (BOF)

40 Fei-Fei Li (http://vision.cs.princeton.edu/teaching.html)を改変局所特徴量（特徴ベクトル）

一般物体認識：Bag of Features

41 クラスタリング visual word

一般物体認識：Bag of Features

42 visual wordを次元とする特徴ベクトル共通の「語彙」で様々な画像を表現頻度に基づく重みを記録

(8)

出席チェック4-2

考えられるSIFTを利用した新しいアプリケーションは？

SIFTアプローチの高速化

SURF(

S

peeded

U

p

R

obust

F

eatures)

処理の流れ

1. キーポイント検出子

– キーポイント(特徴点)の検出 – スケール探索

2. 記述子

– オリエンテーション – 特徴量の記述

SURFのキーポイント検出子

処理の流れ

1. 近似ヘッセ行列の算出

• Box filterによる近似 • Integral Imageによる高速化

2. スケールスペースの構築

3. 極値探索によるキーポイント検出

入力画像 近似ヘッセ行列の算出 極値探索キーポイント •box filter •integral image •scale: σ スケールスペースの構築 •scale σの変更 

2次微分の集合



L

ab

はガウシアンの各方向の2次微分を画像I(x)に

畳み込んだ応答値

ヘッセ行列

Lyy Lxx Lxy 

エッジの種類

(a) xy方向の両方の輝度差が大きい (b) xy方向の両方の輝度差が大きいが極性が違う (c) xy方向の片方が輝度差が大きい 

判別式

エッジの種類と判別式

ガウシアンの2次微分は計算コストが高いため判別に時間が掛かる (a) (b) (c)

Box filterによる判別式を近似



近似判別式

0.9倍：近似誤差修正 Lyy Lxx Lxy Dxx Dyy Dxy

近似

(9)



矩形領域の輝度値の和を高速に算出可能



利点

• 領域の数が多い場合 • 領域が重なり合う場合 O

Integral Image

A B C D S S = -B -C +D A 

σを増加し，複数の近似ヘッセ行列を作成

•スケールσ : 1.2, 2.0, 2.8, 3.6 •フィルタサイズ : 9 x 9, 15 x 15, 21 x 21, 27 x 27

スケールスペース

S ca le S ca le

極値探索

キーポイント検出例 

26近傍で極値ならキーポイント

S ca le

SURF

(Speeded Up Robust Features)

1. SURFのキーポイント検出子 2. SURFの記述子

オリエンテーションの算出

6sの領域からオリエンテーションを算出 Haar-Waveletを用いて勾配方向と強度を算出 • オリエンテーション算出領域内をラスタ操作 • x方向とy方向の応答(dx, dy)から勾配方向と強度を算出 4s 4s ９ x y 6s 6s ●勾配方向の分解能は60度 – ６方向のヒストグラムを作成 ●勾配強度の和が最も大きい角度 → オリエンテーション

1. 記述範囲として20sの領域を選択

2. 領域を4×4(=16)ブロックに分割

3. 記述範囲をオリエンテーション方向に回転

方向の正規化

20s 20s

(10)

特徴ベクトル算出

1つのブロックを４分割 分割した同じサイズのHaar-Waveletを作成 • 応答値よりΣdx，Σdy，Σ|dx|，Σ|dy|を算出 → 16分割×4次元＝64次元

速度とマッチングの比較

Detector しきい値特徴点数処理時間 Fast-Hessian（SURF） Hessian-Laplace Harris-Laplace DoG（SIFT） 600 1000 2500 default 1418 1979 1664 1520 120 650 1800 400 Detectorの処理時間 [ms]

速度とマッチングの比較

U-SURF SURF SURF-128 SIFT

255 354 391 1036

Descriptorの処理時間 [ms]

U-SURF SURF

SURF-128 SIFT GLOH PCA-SIFT 正解率 83.8 82.6 85.7 78.1 78.3 72.3 対応点マッチングの正解率 [%]

まとめ：SURF



SIFTより精度がちょっと低い



以下の特徴があるので、高速マッチングが可能

• Integral Imageの利用 • Hessian行列算出にbox filtersの利用 Tracking/SFM

公開されているソースコード

SIFT(実行形式ファイル)：Lowe • http://www.cs.ubc.ca/~lowe/keypoints/ SIFT(C++)：Vedaldi • http://vision.ucla.edu/~vedaldi/code/siftpp/siftpp.html SIFT(MATLAB)：Vedaldi • http://vision.ucla.edu/~vedaldi/code/sift/sift.html PCA-SIFT：Ke • http://www.cs.cmu.edu/~yke/pcasift/ SURF : Herbert • http://www.vision.ee.ethz.ch/~surf/ GPGPUを用いたSIFT : Wu • http://cs.unc.edu/~ccwu/siftgpu/