加速稳健特征
SURF (Speeded Up Robust Features, 加速穩健特徵) 是一个穩健的图像识别和描述算法,首先于2006年发表在ECCV大会上。这个算法可被用于计算机视觉任务,如物件识别和3D重构。他部分的灵感来自于 SIFT 算法。SURF标准的版本比SIFT要快数倍,并且其作者声称在不同图像变换方面比SIFT更加稳健。
SURF使用海森矩陣的行列式值作特徵點偵測並用積分圖加速運算;SURF 的描述子基於 2D 离散小波变换 响应并且有效地利用了积分图。
演算法
SURF演算法的概念及步驟均建立在SIFT之上,但詳細的流程略有不同。SURF演算法包含以下三個步驟:特徵點偵測、特徵鄰近描述、描述子配對。
特徵點偵測
SIFT使用了連續不同尺度的高斯濾波器處理影像,並且經由高斯差來偵測影像中尺度不變的特徵點。
SURF使用了方型濾波器取代SIFT中的高斯濾波器,借此達到高斯糢糊的近似。其濾波器可表示為:
此外使用方型濾波器可利用積分圖大幅提高運算速度,僅需計算位於濾波器方型的四個角落値即可。
SURF使用了斑點偵測的海森矩陣來偵測特徵點,其行列式值代表像素點周圍的變化量,因此特徵點需取行列式值為極大、極小值。除此之外,為了達到尺度上的不變,SURF還使用了尺度σ的行列式值作特徵點的偵測,給定圖形中的一點p=(x, y),在尺度σ的海森矩陣為H(p, σ):
其中矩陣內的 等函數為二階微分後的灰階圖像。
9*9的方型濾波器被作為SURF最底的尺度,近似於σ=1.2的高斯濾波器。
尺度空間描述與特徵點定位
因為影像會在不同的尺度下作比較,特徵點往往會在不同尺度下被偵測到。在SIFT中,由於連續的高斯糢糊處理以及影像的降採樣,在尺度上會型成類似金字塔的概念,例如高斯金字塔。
而SURF中尺度是由方型濾波器的大小決定的,並不是連續的高斯糢糊及降採樣處理。其中最底層的尺度(初始尺度)的方型濾波器大小為9*9,近似於σ=1.2的高斯濾波器。越往上層的尺度濾波器的大小也就跟著增加,例如15*15、21*21、27*27......。
其尺度的轉換公式為:
與SIFT相同,SURF會使用特徵點海森矩陣的行列式值作鄰近資料插補來定位特徵點。
特徵點描述子
為了保留特徵點不變的特性,例如旋轉、尺度上的不變性,需要賦予特徵點一個描述子,使其能保有其不變性且能夠輕易地被區分。大多數的描述子建立的方法為描述特徵點與其相鄰的相素點間的變化,因此描述子往往都是區域性的。
同時描述子的維度也是描述子重要的考量之一,一個維度不足的描述子可能會使能特徵點不易區分,然而維度過大的描述子要耗費的計算也就越複雜。SURF的描述子使用了哈爾小波轉換的概念,並利用積分圖簡化描述子的計算。
方位定向
為了使得特徵點擁有轉動不變性,需要賦予特徵點一個方向。SURF的描述子計算特徵點周圍半徑為6σ個像素點的x,y方向的哈爾小波轉換,其中σ是此特徵點位於的尺度。所得到的小波響應以特徵點為中心的高斯函數作加權,並將其值標於一xy作標平面上作圖。最後在xy作標平面上以π/3為一個區間,將區間內小波響應的x、y分量加總得到一向量,在所有的向量當中最長的(即x、y分量最大的)即為此特徵點的方向。
此外在xy平面上選擇角度的區間大小可由角度的解析度、描述子的獨特程度等因素來作為調整的考量。
描述子量值
選定了特徵點的方向後,其周圍像素點需要以此方向為基準來建立描述子。此時以5*5個像素點為一個子區域,取特徵點周圍20*20個像素點的範圍共16個子區域,計算子區域內的x、y方向(此時以平行特徵點方向為x、垂直特徵點方向為y)的哈爾小波轉換總合 、 與其向量長度總合 、 共四個量值,共可產生一個64維資料的描述子。
描述子配對
替所有的特徵點建立描述子後便能使用描述子達成特徵點的配對,藉此應用在物體辨識、3D模型建立等應用上。
实现
- 原始实现 (闭源)
- OpenSURF (开源) 有详细的文档和参考手册的实现(C++, C#, Java, Android, iPhone)
- OpenSurfCL(页面存档备份,存于互联网档案馆) (开源) OpenSURF 在 OpenCL 上的免费实现(C++, C# Wrapper, JNI)
- OpenCV SURF (开源) SURF 的特征分离实现 (OpenCV 2.0)
- SURFmex Matlab OpenCV的 SURF 接口(MEX)代码。
- OpenSURF Matlab(页面存档备份,存于互联网档案馆) (开源) 到 OpenSURF (Matlab) 的接口
- libmv SURF(页面存档备份,存于互联网档案馆) (开源) 分离与匹配的实现
- Python mahotas(页面存档备份,存于互联网档案馆) (开源) 包含 SURF 实现的计算机视觉包
- Dlib C++ Library(页面存档备份,存于互联网档案馆) (开源) SURF 特征分离的实现
- Pan-o-matic(页面存档备份,存于互联网档案馆) (开源) 包含 SURF 算法的软件
- Parallel SURF[永久失效連結] 基于 Pan-o-matic 的多线程实现
- C# SURF plugin for Multi-Agent Serving System (开源) 分离和匹配的实现
- JavaSurf(页面存档备份,存于互联网档案馆) (开源) java 实现 (平台独立)
- JOpenSURF(页面存档备份,存于互联网档案馆) (开源) java 翻译的 OpenSURF
- ImageJ SURF(页面存档备份,存于互联网档案馆) (开源) 作为 ImageJ 插件,拥有舒适的GUI和输出统计的SURF实现(平台独立)
- ASSURF(页面存档备份,存于互联网档案馆) (开源) 在 Adobe Flash 平台中基于 ActionScript 的SURF实现
- Speeded Up SURF(页面存档备份,存于互联网档案馆) (开源) GPU 实现
- CUDA SURF[永久失效連結] (开源) GPU 使用 CUDA 的实现, 接口与 OpenSURF (C++, CUDA) 类似
- Mathematica(页面存档备份,存于互联网档案馆) 实现
- GPU SURF(页面存档备份,存于互联网档案馆) (开源) GPU 实现
参见
引用
- Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool "SURF: Speeded Up Robust Features"(页面存档备份,存于互联网档案馆), Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346–359, 2008
- Christopher Evans "Notes on the OpenSURF Library", MSc Computer Science, University of Bristol(页面存档备份,存于互联网档案馆)
- P. M. Panchal, S. R. Panchal, S. K. Shah, "A Comparison of SIFT and SURF(页面存档备份,存于互联网档案馆) ", International Journal of Innovative Research in Computer and Communication Engineering Vol. 1, Issue 2, April 2013