噓 rick95190: 12/29 02:58
SUR 51，以此類推，可參考圖2.8。由上可以整理出每一階層與尺度之關係如式2.13
s 2.13，L 為遮罩尺寸，o 為階索引，s 為層索引，pprox 為近似尺度。
F 演 15、21 21、27 27 層，第一階每層遮罩尺寸之 15、27 27、39 39、
51 邊長相差6 個像素。
第二階的第一層為上一階兩相鄰層遮罩尺寸邊長之差，而每層遮罩尺寸為上一階兩
相鄰層遮罩尺寸邊長之差的兩倍。因此，第二階依序為15 算法 5 3 或5 5 或... 等) 的摺積僅需要5
個運算子。由此可見積分影像的運用改善了建立高斯金字塔時的運算時間。
9、15
需要26 個運算子... 等)，而積分影像與遮罩(3
加速強健特徵(S 3 遮罩(Mask) M 為例(圖2.3)，原始影像I 與積分影像Ipeeded-Up Robust Features, SURF) 演算法，由Bay[2][3] 等人
以尺度不變特徵轉化(Scale Invariant Feature Transform, SIFT) 為基礎於2006 年所
提出，用於偵測影像上的特徵點， 3 遮罩的摺積運算需要10 個運算子(如為5 具有影像平移、縮放及旋轉不變性。主要包含
興趣點偵測器(Interest Point Detector) 及特徵描述子(Feature Descriptor)。以下對
SURF 演算法做詳細的說明。
積分影像
積分影像(Integral Image) 的概念是由Viola 和Jones[4] 所提出，用於加速矩形
特徵之運算。圖2.1，點(4; 4) 位置之積分值代表左圖中灰色區域之灰階值總和，積
分影像轉換公式如式2.1 所示。I 表示積分前影像，I 表示積分後影像，(x; y) 表示
影像像素(Pixel) 位置
整張圖的積分影像建立完成後，只需要四個運算便可快速計算影像中任意矩形
區域之面積。如圖2.2，A、B、C、D 分別代表原影像中四個矩形區域。積分影像
中，點1 之積分值為區域A 之灰階值總和，點2 之積分值為區域A+ 區域B 之灰
階值總和，點3 之積分值為區域A+ 區域C 之灰階值總和，點4 之積分值為區域A
+ 區域B+ 區域C+ 區域D 之灰階值總和。我們可以利用積分影像中點1、2、3、4
來計 15(如圖2.7所示)。以此類推，第一階(影像金字塔之初始階) 依序可以分為算區域D 之灰階值總和，因此，區域D=4-3-2+1。
9
SURF 演算法運算速度快速是因為在建立高斯金字塔時，利用積分影像的特性，
先將原始影像轉換為積分影像，再與近似的Hessian 矩陣作摺積(Convolution)，得
到近似的高斯模糊影像。因此，大幅縮短了以往在建立高斯金字塔時的運算時間。
以一個等值的3
分別與遮罩作摺積，其數學式分別為式2.2與式2.3，(x; y) 表示像素座標，a; b 為遮
罩座標。可以發現，原始影像與3
基於Hessian 矩陣的興趣點檢測
Hessian 矩陣為二階偏導數所組成的方塊矩陣，其特性是行列式值可用來檢
測函數臨界點為極值點還是鞍點(Saffle point)。一連續二階偏導數函數f(x; y), 其
Hessian 矩陣與行列式特性可表示如下:
9 的遮罩近似= 1:2 的高斯二階偏導數，並且用它做為尺度空間裡最低
尺度。以Dxx、Dxy、Dyy 表示遮罩與積分影像進行摺積的結果，Happrox 表示近似的
Hessian 矩陣，則Hessian 矩陣與DoH 便可簡化如下:
9 遮罩為例，l0 為3。而為了使逐步增加尺寸
的遮罩維持其結構比例，下一層以l0 為基礎增加2 個像素，即l0 為5，遮罩尺寸
為15
為Frobenius 範數，其用處
為平衡簡化後的盒子濾波器。理論上，w 會隨著尺度而有所改變，而根據SURF
作者實驗後認為w 定義為一常數對結果並不會產生太大的影響。而實際上在
計算濾波器響應值時還需對濾波器尺寸做正規化處哩，這樣才能保證任意大小
的濾波器其Frobenius 範數是統一的，以達到尺度不變性。盒子濾波器權重值
為vn 2 f1;A而根據SURF
作者實驗後認為w 定義為一常數對結果
9
遮罩Dyy，共有3 個波瓣(兩正(白色)，一負(黑色))，任一波瓣之短邊即為l0)，它
為盒子濾波器遮罩尺寸的1
3。以9
由式2.10 s 2.11中，可以得知計算Dxx 與Dyy 時各需要用到12 次加減法運算
與4 次乘法運算，計算Dxy 時需要16 次加減法運算與5 次乘法運算。因此，積分
影像的運用，使得運算量與遮罩的大小是無關的。
尺度空間表示法
為了要達到尺度不變性，要在不同尺度下尋找興趣點，因此需要建立尺度空間。
一般透過高斯影像金字塔來建立尺度空間，此方法透過不同的高斯函數與影像作
摺積後，再進行縮減取樣(Downsampling)，以獲得更高一層的金字塔影像。此方法
非常的耗時，因此，SURF 演算法藉由逐步增加盒子濾波器尺寸與積分影像摺積，
並且計算Hessian 矩陣行列式取得斑點響應圖(Blob Response Map) 來建立尺度空間
(如圖2.6 所示)。
尺度空間由若干階(Octaves) 所組成，每階又包含若干層，代表逐步增加的盒
子濾波器尺寸與同一個輸入影像所建立的若干斑點響應圖。由於積分影像的離散化，
兩層之間的最小尺度變化量取決於高斯二階偏導數在導數方向(x 或y) 上的正或負
波瓣(Lobes) 長度l0(波瓣，即盒子濾波器中不同顏色的區域，可參考圖2.7中9
因此，可用Hessian 矩陣行列式值(Determinant of Hessian, DoH) 於影像斑點
檢測(Blob Detection)。斑點通常是指影像中與周圍顏色或灰階值有差別之區域；以
7
真實世界為例，一顆樹是一個斑點，一片草地也是一個斑點等。給定一影像I 中一
點X = (x; y)，在點X 處，尺度(Scale) 為A其Hessian 矩陣H(X; 定義如下:
然而，在建立尺度空間時，離散化後之高斯二階偏導數與影像直接作摺積運
算將相當耗時且複雜，所以Bay 等人將此運算轉換為積分影像與盒子濾波器(Box
Filter) 作運算，並對高斯二階偏導數進行簡化，簡化後的遮罩僅由幾個矩形區域組
成，並且給予權重值(如圖2.5所示)。因此，在計算不同尺度下的DoH 僅需要改變
Box Filter 的尺寸，並且維持其結構比例即可。
以9
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.117.95.130