角點檢測技術綜述①

朱思聰,周德龍

(浙江工業大學 計算機科學與技術學院,杭州 310023)

角點檢測是機器視覺和計算機視覺領域的基本課題.關于角點目前還沒有精準的數學定義,通常將以下幾種點稱為角點:一是兩條邊緣以上的交點,二是圖像上各個方向亮度變化足夠大的點,三是邊緣曲線上的曲率極大值點.角點有時也稱為興趣點和特征點,在簡化圖像信息數據的同時,還在一定程度上保留了圖像較為重要的特征信息,從而方便了圖像數據的處理.因此,角點檢測在三維場景重建、運動估計、視覺跟蹤[1]以及圖像配準與圖像匹配[2]等計算機視覺領域有著廣泛的應用.

本文對現有的角點檢測方法進行了分類及闡述,主要分為基于灰度強度的方法、基于邊緣輪廓[3]的方法,并將其余類別的角點檢測方法也進行了匯總.本文第3部分對現有的角點檢測算法的測評技術也進行了匯總.除此之外,本文還搜集了一些最新的角點檢測算法在工程中的實際應用案例以供參考.

1 角點檢測算法現狀分析

根據實現原理不同,現有的角點檢測算法大致可以分為3類:基于灰度強度的方法,基于邊緣輪廓的方法和基于二值圖像的角點檢測.其中針對二值圖像的角點檢測方法并不流行.因此,本節主要針對前兩類方法詳細闡述大部分典型角點檢測算法的核心思想及部分關鍵的特征提取步驟.

1.1 基于灰度圖像的角點檢測

基于灰度圖像強度的角點檢測技術又可大致分為3類,分別是基于梯度、基于模板和基于模板梯度組合.其中基于梯度的方法是通過邊緣曲率的計算數值大小來判斷角點是否存在但是該方法對噪聲十分敏感.另一種基于模板的角點檢測方法考慮了像素鄰域點的灰度值變化,將與鄰近點灰度值差異明顯的點定義為角點.相比于直接對灰度圖像的像素進行處理,還有一類方法綜合了灰度曲率以及模板策略進行角點檢測.

1.1.1 Moravec角點檢測技術

1977年,Moravec[4]提出了Moravec角點檢測算子,其基本思想是通過在圖像上移動一個二值矩形窗口來查找最小灰度值變化的最大值.這種方法的缺點是響應值非各向同性,對噪聲和邊緣敏感,對旋轉不具備不變形.Moravec算子作為第一個被廣泛使用的角點檢測算法,開創了角點檢測的新時代.

1.1.2 Harris角點檢測技術及相關改進方法

受Moravec角點檢測算法啟發,Harris和Stephens[5]在1988年提出了著名的Harris角點檢測算子,該方法首先計算Harris矩陣M(二階矩矩陣或自相關矩陣),然后計算該矩陣的特征值 λ1,λ2,這兩個特征值表征了Harris矩陣主曲率,再通過構建如下的Harris角點量測函數R來確定角點:

最后對R進行非極大值抑制,所得角點位置在局部梯度最大值處.Harris角點檢測方法不僅對噪聲不敏感、具有平移和旋轉不變性、具有高重復性和高信息量,而且在不同光照條件下具有良好的穩定性,但是該方法不適用于對尺度變化要求高的場合.2014年,Qiao等人[6]提出了一種改進的 Harris亞像素角點檢測算法,提高了控制點圖像的定位精度針對Harris角點檢測算法存在對含有噪聲的圖像角點檢測不準確的問題,盧偉家[7]提出在Harris算法設置的局部移動窗口中加入一種加權系數自適應的加權均值濾波,該方法可有效減少偽角點的形成,同時具有良好精確度和檢測速度.2017年,Wang等人[8]針對角點檢測算法在提取角點時必須給出合適的閾值問題,提出了一種基于迭代閾值的自適應Harris角點檢測算法.

1.1.3 基于SUSAN的角點檢測技術

另外一種有名的角點檢測算法是1997年Smith和Brady[9]提出的同值分割吸收核(SUSAN,Smallest Univalue Segment Assimilating Nucleus),該算法利用像素鄰域的一個圓形模板,判斷該點是否屬于USAN區域,判別函數如下:

使用如下角點響應函數計算函數值:

如果該函數值大于某個閾值且為局部極大值,則認為該點是角點,其中統計圓形模板中和核心點有相似亮度值的像素個數n公式如下:

該算法具有速度快、定位精度高、高重復性、平移和旋轉不變性.但許多特征位于邊緣結構而不是真正的角點處,另外對噪聲敏感和缺少信息量,且在處理模糊圖像時性能較差.在經典SUSAN算法的基礎上,He等人[10]采用角點預檢測來消除偽角,減少計算量,從而提高算法速度.針對傳統SUSAN算子只能在單一尺度下檢測圖像中角點的不足,王冠群等人[11]提出一種基于高斯變換的多尺度SUSAN角點檢測方法.該方法利用高斯變換獲得待檢測圖像的多尺度分層圖像,以構建高斯金字塔,結合自適應閾值的SUSAN算子檢測出不同尺度下的角點作為候選角點,將其還原到原始圖像中的相應位置構成候選角點集,在候選角點集中經小鄰域信息篩選獲得最終角點,實驗結果表明,該方法不僅能夠在不同尺度下有效獲取有用的角點信息,而且提高SUSAN算子正確率的同時,降低了角點的偽檢率.

1.1.4 FAST角點檢測技術

1998年Trajkovic和Hedley[12]提出了一種快速角點檢測算子,其基本思想是研究在某點鄰域內通過該點的任意一條直線上的灰度變化情況.首先計算出水平和垂直方向灰度變化值,然后構建一個角點度量函數來判斷角點.2006年Rosten和Drummond[13]提出了高速角點檢測算子,其基本思想是利用機器學習來加速角點檢測過程.上述兩種算法也都對圖像尺度變化敏感.近年來,針對當前FAST角點檢測算法只能檢測單一類型的角點,并且單一閾值作用于整幅圖像很難取得理想的效果等問題,Park等人[14]為了解決可穿戴設備的圖像分辨率與系統功耗之間存在權衡這一問題,提出了一種新的快速角點檢測方法,它在計算性能和可重復性方面優于以前的算法.

1.2 基于輪廓曲線的角點檢測

相對于基于梯度和基于模板的檢測器,基于輪廓的檢測器在角點檢測前先進行邊緣輪廓檢測[15],在輪廓上而不是整幅圖像上檢測角點,因此有著極低的錯誤檢概率.該方法的角點測度被定義在輪廓上并且區分于輪廓上的光滑像素點.

1.2.1 基于Freeman鏈碼的角點檢測技術

二維線條圖像可以用方向Freeman鏈碼表示,這種檢測方法先分割圖像,然后提取圖像邊界的Freeman鏈碼,將方向改變速率大的點標記為角點.Freeman鏈碼是指相鄰兩像素連線的八種可能方向值,稱為八方位鏈碼.該方法計算步驟簡潔,但是檢測效果強依賴于圖像分割的質量.并且由于需要計算夾角,對于噪聲敏感,在進行檢測時必須對圖像進行去噪預處理.

2014年,曾接賢等人[16]提出了一種曲率尺度空間與鏈碼方向統計相結合的角點檢測方法.2017年,Rachmawati等人[17]提出了一種將高速角點檢測與Freeman鏈碼相結合的多邊形逼近技術.該方法利用一組圖像角點構造了一串有序線段的近似多邊形,該近似多邊形可以進一步用于形狀表示和分析領域,作為數字圖像的輪廓描述.2018年,劉相湖等人[18]提出了一種對Freeman鏈碼分析的角點檢測算法,該方法對Freeman鏈碼發生變化時,通過分析其連續前后多個點的鏈碼是否符合一定的規則來判定角點.

1.2.2 基于CSS的角點檢測算法

Mokhtarian等人[19]提出了曲率尺度空間(Curvature-Scale-Space,CSS)的角點檢測器,不同角度下的局部曲率被用于角點檢測,角度下追蹤角點并改善定位準確性.CSS角點檢測算法對輪廓的局部變化和噪聲高度敏感而且很難選擇合適的高斯尺度平滑輪廓和角點閾值.Zhong等人[20]提出了直接曲率尺度空間(DCSS),方法是將平面曲線的曲率與高斯核直接轉換而產生的CSS.他們從理論上分析了DCSS在平面曲線拐角檢測中的應用.研究了孤立的單角和雙角模型的尺度空間行為,定義了若干模型屬性,使DCSS圖像能夠轉化為樹型組織,從而能夠在多尺度意義上進行角點檢測.2016年,李偉生等人[21]提出了一種基于曲率多尺度的自適應角點檢測算法AMCP (Adaptive Multi-scale Curvature Polynomial),該算法結合了尺度多項式的方法,并構造局部曲率顯著度LCCS (Local Corners Curvature Saliency),從而用自適應的閾值代替全局閾值,極大地增強了算法應對尺度,旋轉等變化的魯棒性.

1.2.3 利用弦到點的距離累加的角點檢測算法

2008年,Awrangjeb等人[22]提出了利用弦到點的距離累加(CPDA)的角點檢測算法,該方法在對圖像中的角點進行定位的同時產生最小的定位誤差,該算法有效的避免了CSS算法中存在的主要問題,卻存在著以下問題:一是鄰近角點被合并,二是鈍形角點被誤刪除,三是無法有效剔除圓形角點.2014年,Jin等人[23]針對基于弦對點距離積累、定位精度低、檢測時間復雜度高等缺點,采用先得到單尺度下的候選角點,保持相鄰角點,然后計算了多尺度下候選角的特征值,有效地消除了偽角.2017年,Hossain等人[24]提出了一種基于CPDA改進的角點檢測算法CADT.該方法的預處理和改進步驟與CPDA相似,但是有效的減少了定位誤差和提高了平均重復性,降低了角點的偽檢率.

1.2.4 基于角度(Angle)的角點檢測算法

基于Angle的角點檢測算法出根據邊緣點與左右鄰域內的其他點形成的夾角最小值來標志該邊緣點,把Angle值固定在一定的范圍之內,其值大小與角點的尖銳度成正比,可以有效避免了基于CSS,CPDA 的算法中存在的問題.但是還存在以下不足:不能檢測出鄰近角點,無法有效去除圓形角點、虛假角.2012年,Sadat等人[25]結合了角探測器CPDA和高曲率點探測器IPAN99,為不同的圖像變換提供了魯棒的角點位置.2017年,金亦挺等人[26]提出基于角度累加的角點檢測算法,在獲取圖像邊緣后定義反映邊緣點特征的角度累加概念,并在“單弦”下計算邊緣點角度累加值,以此作為角點初始響應,獲取到候選角點;然后構造候選角點的局部自適應閾值來去除圓形角點,并通過實驗來確定其支撐鄰域范圍和比例系數;再在“三弦”下獲取角點特征值,構造全局閾值來去除偽角點;最后對曲線端點和T 交叉點進行檢測,得到最終角點檢測結果.

1.2.5 多尺度Gabor濾波器的角點檢測

2004年,Gao等人[27]提出的基于Gabor小波的角點檢測算子.多尺度Gabor濾波器的角點檢測算法克服了在不同圖像上的尺度選擇問題.該算法首先對圖像進行邊緣輪廓的提取,進而用一組構建好的4個尺度8個方向Gabor濾波器的虛部對圖像進行平滑處理,并計算每個像素在其相同尺度下各個方向上Gabor濾波器虛部響應的歸一化的和.最后將每個邊緣像素點在所有尺度下的乘積作為新的角點測度,當角點測度大于預設閾值時,則認定該點為角點.2014年,Zhang等人[28]研究提出了一種基于輪廓的角點檢測器,該檢測方法利用Gabor濾波器虛部在輪廓上的幅值響應.與傳統的通過分析邊緣輪廓形狀和搜索平面曲線上的局部曲率極大值來檢測角點的方法不同,該角點檢測器結合了邊緣輪廓的像素及其相應的灰度變化信息.2016年,田子怡等人[29]也提出了提出了一種基于邊緣輪廓線的多尺度Gabor濾波器的角點檢測算法.2017年,高華[30]提出了一個既利用到圖像邊緣輪廓信息又利用到圖像灰度信息的基于Log-Gabor梯度方向一致性的角點檢測算法,以提高角點檢測器的檢測性能.

1.3 其他的角點檢測技術

此外許多研究人員也各自提出或改進了基于角點的檢測算子.2008年,He和Yung[31]提出了一種使用自適應曲率閾值從初始列表中刪除圓角的角點檢測方法.劉文進等人[32]提出一種基于AP聚類角點提取優化的雙邊濾波(BF)角點檢測改進算法.2015年,孔祥楠等人[33]

提出了一種基于各向異性高斯方向導數表示的角點檢測器和分類器.該角點檢測器融合了基于輪廓和灰度強度的檢測思想,提出了一種像素處表示是定向角度的函數,從而表征了像素周圍的局部方向灰度變化.2016年,Xing等人[34]基于局部區域的自適應閾值,提出了一種新的帶填充環和外環的掩碼來檢測圖像中的角點.該方法先利用內填充圓作為響應函數,對圖像角領域、目標邊緣以及平坦區域等非角區域進行濾波.然后利用復雜的響應函數,同時考慮內圈和外環的邊緣,并采取相關算法檢測位于薄帶、噪聲和突出像素上的虛假角點.2017年,Cho等人[35]提出了一種新的基于非角度測量的角點檢測方法.該非角函數消除了位于平坦區域的像素并刪除了沿任意方向沿邊緣的像素.

各種角點技術綜合性能總結以及優缺點在表1有詳細的展示.

2 角點檢測算法的測評技術

由于角點沒有精準的定義,因此角點的確認是一個非常主觀的二值化過程.一般由算法測評者根據實際應用需求自行給出,由此影響了測評結果的客觀性.現有的測評技術主要依賴于理論分析,基于標定的參考角點,以及基于一致性判定,常用的主要為后兩者 其中比較經典的基于標定的參考角點方法由2003年Rockett[36]提出.該方法通過一組具有參考角點的圖像集,然后對圖形進行不同算法的角點檢測,利用ROC曲線對檢測器的性能進行評價.

表1 各種角點技術綜合性能總結

本文主要針對基于一致性[37]的判定的角點檢測評價技術進行詳細介紹.主要有兩個指標:一是角點重復率,二是角點定位誤差.該方法先是對給定圖片進行角點的提取,角點數記為Nc.然后對圖形進行如下操作:旋轉變換,尺度變化,仿射變換,Jpeg壓縮等.提取變化后的角點數量Nm,最后對兩者進行匹配得到配對數Nr.其中,角點重復率函數如下:

角點定位誤差函數如下:

為了避免數據展示的冗雜,本文選取了一定數量的圖片,以及幾種角點檢測算法,對其性能進行了評測,大致展示了這幾種算法的角點重復率及角點定位誤差.實驗數據部分采用了CPDA,He ＆Yung,CSS,FastCPDA等較為新穎的角點檢測算法進行了測試.其中CPDA利用弦到點的距離累加;He ＆Yung使用自適應曲率閾值從初始列表中刪除圓角;CSS利用了曲率尺度空間;FastCPDA是一種改進算法.具體結果如圖1和圖2所示.具體細節鑒于篇幅不再贅述.所展示的圖片檢測效果則是采取了幾種常見的角點檢測算子以供參考,如圖3和圖4所示.

圖1 角點重復率示意圖

圖2 角點定位誤差示意圖

圖3 角點較少圖像的檢測示例

圖4 角點較多圖像的檢測示例

3 角點檢測算法的實際應用

洪磊等人[38]針對Hessian算子在棋盤格角點檢測過程中邊緣局部區域角點檢測失敗的問題,提出一種恢復角點識別的修正算法.Lin等人[39]提出了兩種新的三維網格數據角點檢測算法,分別研究了在多尺度空間中曲面的幾何性質以及利用簡單三角形原理檢測網格角點的方法.謝志峰等人[40]在深度神經網絡的煙碼智能識別方法中采用角點檢測進行圖像塊的切割.Li等人[41]針對高光譜圖像提出了極限約束空間譜角(ECSSC)的定義并設計了一種基于ECSSC和并行計算的圖像級HSI分類框架.該算法能夠從HIS角點特征中檢測出豐富的角點特征,具有較高的重現性,基于ECSSC的圖像級HSI檢測精度明顯高于現有的算法.Wang等人[42]針對傳統角點檢測在視頻圖像復雜場景中角點檢測精度低、實時性差的問題,提出了一種基于ORB特征提取和群SAC算法的快速角點檢測算法.該算法應用于光照變化、尺度變化、旋轉變化、遮擋圖像等復雜場景的視頻圖像中具有較高的精度和較低時間復雜度,具有較強的魯棒性.劉妍等人[43]提出了一種基于SAR快速角點檢測的SAR圖像配準方法,該方法是一種自定義的基于加速段測試(FAST)特征的SAR圖像配準方法.該方法表明了快速合成孔徑雷達能夠檢測出足夠數量的角點,具有較高的重復性和穩定性,在應用于圖像配準時也能得到較好的配準結果.

4 結論與展望

本文對現有的角點檢測技術進行了分類和歸納,詳細闡述典型角點檢測算法的關鍵步驟,表1對基本的角點檢測算法進行了歸納和總結.本文也對近幾年來各類角點檢測算法發展與改進提出了一點建議.

總的來說,角點檢測算法的研究改進工作主要有以下幾個方面:(1)根據實際工程的需求出發,角點檢測技術的一些指標如快速性、準確性、魯棒性等有著不同的定量指標,所以選取的角點檢測算法需要從業人員進行全局的分析.(2)從算法角度來看,直接基于灰度圖像強度的角點檢測基本上是全局搜索,可以進行局部搜索優化算法;基于邊緣輪廓的角點檢測一般采用了多分辨分析并行處理,從灰度圖像得到邊緣輪廓曲線要經過兩次以上的全局搜索,計算復雜度高,對此進行算法復雜度的優化,可以提高檢測的檢測度.(3)角點檢測測評技術的研究亟待完善,現在還沒有公認的大規模關于角點檢測的數據集,而且角點測評技術的維度也十分有限.后續研究者可以在這兩方面著力研究.

除此之外,本文還搜集了一些最新的角點檢測算法在工程中的實際應用案例.角點檢測在三維場景重建、運動估計、視覺跟蹤、機器人定位、視覺跟蹤、圖像全景拼接以及圖像配準與匹配等領域有著廣泛的應用前景.角點檢測技術仍在發展,本文羅列的一些較新的方法及經典方法的改進策略,意在期望更多研究人員推動這一課題更快發展.文章中必然存在的一些不當的問題,我們歡迎對這些觀點進行批判和糾正.