B-Spline-ORB特征點提取算法

摘要：針對傳統ORB算法尺度不變性較差的問題，提出了基于圖像金子塔的ORB算法。首先研究了高斯圖像金字塔和B-spline圖像金字塔，通過實驗對兩種圖像金字塔進行了探討。實驗表明，3階B-spline圖像金字塔的圖像所包含的圖像信息要高于相同層上高斯圖像金子塔的圖像所包含的信息。其次，在圖像尺度發生變化的前提下，通過實驗對傳統ORB算法、基于高斯圖像金字塔的ORB算法和基于B-spline圖像金字塔的ORB算法進行了探討。實驗表明，基于3階B-spline圖像金字塔的ORB算法相比較傳統ORB算法所提取的特征點配準率提高了40%。同時，相較基于高斯圖像金字塔的ORB算法，本文提出的改進算法在匹配準確率和運行速度上也有所提升。

關鍵詞：特征點提取;圖像金字塔;ORB算法;B-Spline

DOI：10.15938/j.jhust.2022.03.013

中圖分類號： TP751.1文獻標志碼： A文章編號： 1007-2683（2022）03-0097-08

B-Spline-ORB Feature Point Extraction Algorithm

LIU Ming-zhu，CHEN Rui，CHEN Jun-yu，SUN Xiao-ming

（Heilongjiang Provincial Key Lab of Measurement and Control Technology and Instruments，

Harbin University of Science and Technology， Harbin 150080， China）

Abstract：Aiming at the problem of poor scale invariance of traditional ORB algorithms， this paper proposes an ORB algorithm based on image golden tower. Firstly， Gauss image pyramid and B-Spline image pyramid are studied， and the two image pyramids are discussed through experiments. Experimental results show that the image information of the third order B-Spline image pyramid is higher than that of the Golden Tower of Gauss image on the same layer. Secondly， the traditional ORB algorithm， the ORB algorithm based on Gaussian image pyramid and the ORB algorithm based on B-Spline image pyramid are discussed through experiments under the premise of changing image scale. Experimental results show that the registration rate of feature points extracted by ORB algorithm based on third-order B-Spline image pyramid is 40% higher than that of traditional ORB algorithm. At the same time， compared with the ORB algorithm based on gaussian image pyramid， the improved algorithm proposed in this paper has improved the matching accuracy and running speed.

Keywords：feature point extraction;" image pyramid;" ORB algorithm;" B-Spline

0引言

近年，隨著科學技術的迅速發展，圖像匹配[1-4]技術成為目標檢測與識別、自動駕駛和圖像拼接等圖像處理研究中非常重要的一個部分。圖像匹配過程中，首先要找出圖像中的特征信息，之后在待匹配圖像中尋找到與之相符合的匹配點對。當前特征提取算法有SIFT算法[5-6]、SURF算法[7]和ORB（oriented FAST and rotated BRIEF）算法[8]。ORB算法是當今比較成熟的算法，該算法是FAST算法和BRIEF描述符相結合的產物。ORB算法提取特征點的速度快，但是該算法在尺度發生變化的圖像上，特征點的匹配精確度差。在保持ORB算法特征點提取速度基礎上，更好的改善尺度不變性。本文提出了一種ORB算法的改進算法——B-Spline-ORB算法，該算法采用B-Spline圖像金字塔的方法來彌補ORB的尺度不變性差的特點。經測試表明，本文提出的方法除能保持傳統ORB算法的高速提取的特性，對尺度發生變換的圖像能有效的提高匹配準確率。

1ORB特征點提取算法

ORB算法使用一種基于灰度質心法的FAST（features from accelerated segment test）算法來檢測特征點，再利用Harris角點的度量方法，挑選N個特征點，最后用改進的BRIEF描述子進行描述。

1.1FAST角點檢測

2006年FAST算法被首次提出[9-10]。其原理是從圖中選取一個待檢測點P，使用IP表示點P的灰度值;以該點為圓心取一個半徑為3的圓，在這個圓的邊界上選16個點，如圖1所示，設定一個閾值th;將這16個點的灰度值依次與待檢測點P的灰度值相比較，如果這16個點中有n個點的灰度值比點P的灰度值IP大th，或者有n個點的灰度值比點P的灰度值IP小th，那么點P就被認定為特征點。在文[11]中ORB算法的n值取為9。

ORB算法使用灰度質心法，來改善FAST所提取的特征點不具有方向性的問題。灰度質心法的原理是：首先計算得到特征點鄰域范圍內的灰度質心。最終得到一個由該特征點指向灰度質心的向量。定義該向量的方向為特征點方向。

對于任意一個特征點p（x，y），定義p（x，y）的鄰域像素的矩為：

mi，j=∑rx=-r∑ry=-rxiyjI（x，y）（1）

式中：I（x，y）為點p（x，y）處的灰度值，i，j∈（0，1）;r=3為鄰域半徑。

圖像的質心為

C=m10m00m01m00（2）

FAST特征點的方向為

θ=arctan（m01m10）（3）

1.2角點響應函數

Harris角點檢測算法中定義在圖像的局部中變化最大的點為角點。設灰度圖像在某一點（x，y）處的灰度為I（x，y），以該點為中心的矩形窗口W在任意方向上平移（u，v）后產生的灰度變化E（u，v）可表示為

E（u，v）=∑（x，y）∈Ww（x，y）[I（x+u，y+v）-I（x，y）]2（4）

將式（4）I（x+u，y+v）進行泰勒公式展開后帶入原式中得：

E（u，v）=∑（x，y）w（x，y）[u，v]I2xIxIy

IyIxI2yu

v=

[u，v]Mu

v（5）

度量Harris角點響應的變量R定義為

R=detM-k（trace（M））2（6）

式中k是一個經驗值，在文[12]中給出k在0.04～0.06的范圍內效果最佳。

M=∑（x，y）∈Ww（x，y）I2xIxIy

IxIyI2y（7）

式中：w（x，y）為滑動窗;x和y為窗口W對應的像素坐標;Ix和Iy為窗口內像素點（x，y）在x方向和y方向上的梯度值。

度量Shi-Tomasi角點響應[13]的變量F定義

F=min（λ1，λ2）（8）

式中λ1和λ2為式（5）矩陣M的特征值。

1.3Steer BRIEF描述子

BRIEF描述子采用一種二進制的描述方法。在特征點周圍選取nd個點對，文[14]nd選取得值為256，將這nd個點對，通過點對的比較準則τ進行比較。

τ（p;x，y）=1I（p;x）lt;I（p;y）

0I（p;x）≥I（p;y）（9）

其中：I（p;x）為p區域中點x的灰度值;I（p;y）為區域p中點y的灰度值。

最后將這些點對比較的結果組合為特征點的描述符：

fnd（p）=∑1≤i≤nd2i-1τ（p;x，y）（10）

ORB算法中將這nd個點對（xi，yi），i=1，2，…，nd組成2×nd矩陣S：

S=x1x2…xnd

y1y2…ynd（11）

使用式（3）鄰域方向θ與對應的旋轉矩陣Rθ如式（12）所示。

Rθ=cosθsinθ

-sinθcosθ（12）

構建S的一個校正版本Sθ：

Sθ=RθS（13）

最終得到Steer BRIEF描述子：

gnd（p，θ）=fnd（p）|（xi，yi）∈Sθ（14）

1.4ORB實驗測試分析

本文選取了100幅圖像對ORB進行測試，其中包括相同尺度圖像50幅，不同尺度圖像50幅，圖2（c）、圖3（c）所示分別為選取的具有代表性的兩幅圖像，通過特征匹配測試結果，來說明ORB算法特征點的尺度不變性。

由圖2（c）可以看出當圖像中的物體在同一尺度下時，傳統ORB算法所提取的特征點的正確匹配率高。從圖3（c）可以很明顯的看出當圖像中的物體出現尺度變化時，ORB算法所提取到的特征點的正確匹配率變差，說明ORB算法在尺度變化較大的圖像中所提取到的特征點的尺度不變性較差。

因此，本文提出利用圖像金子塔與ORB算法相結合以改善傳統ORB的尺度不變性差的特點。

2基于圖像金字塔的ORB算法

圖像的多尺度處理是指對圖像的多尺度表達。很多時候我們無法從單一的尺度中獲得全部的特征，但是在其某種尺度下就很容易發現。其中圖像金字塔就是多尺度表達的方法之一。通過使用圖像金字塔技術，可以獲取更多圖像信息，從而提高圖像特征匹配的正確率。

2.1基于圖像金字塔的ORB算法流程

本文針對ORB算法[15-16]不具有尺度不變特性這一缺點，將傳統ORB算法與金字塔方法結合來改善原算法尺度不變性差的，本文提出算法流程如圖4所示。

首先將輸入的圖像構造相應的圖像金字塔，其次提取金字塔每層圖像的特征點;然后根據特征點的角點響應值進行排序，選取前N個特征點;最后得出相應的描述子。

本文選取兩類圖像金子塔進行了算法的搭建，高斯與B-Spline圖像金字塔。經測試分析，兩種類型圖像金字塔均可改善尺度變化類型圖像的特征點提取效果。

2.2高斯圖像金字塔結構及處理過程

圖像金字塔模型是一種可以對圖像進行多尺度描述的方法。首先對圖像平滑濾波，然后進行降采樣。

高斯圖像金字塔的建立過程如下圖5所示：

Gk+1（x，y）=W（m，n）*Gk（x，y）（15）

其中：Gk+1（x，y）表示第k+1層高斯平滑圖像;Gk（x，y）表示第k層高斯平滑圖像。

W（m，n）表示半徑為5的高斯濾波器，其濾波參數如式（16）所示：

W（m，n）=127314741

41626164

72636267

41626164

14741（16）

2.3B-SPLINE金字塔基本結構

除如上高斯核外，B-spline函數也可以很好的逼近高斯函數，并且B-spline圖像金字塔[17-18]為圖像提供了更加豐富高效的多尺度信息。

在B-spline金字塔算法中，各個層上的圖像像素點的灰度值表示為

gn（i）（x，y）=∑∞k=-∞αi（k）βon（x-2ik，y-2ik）（17）

式中：x和y分別代表像素點的橫縱坐標;n為B-spline的階數;i為圖像金字塔的層數;αi（k）為樣條系數數組[19];βon（x，y）代表尺度函數[20]：

βon（x，y）=∑∞k=-∞（b2n+1）-1（k）βn（x-k，y-k）（18）

式中：bn（k）為n階B-spline函數的脈沖響應;βn（x，y）為二維B-spline基函數。

第一層圖像的樣條系數如下，

α（0）（k）=b2n+1*（bn）-1*gn（1）（k）k∈Z（19）

后續層的樣條系數為：

α（i）（k）=12[un2*α（i-1）]↓2（k）k∈Z（20）

式中

un2（k）=12nn+1

k+（n+1）/2|k|≤（n+1）/2

0其他（21）

2.4兩種圖像金子塔測試及對比分析

本文針對高斯圖像金字塔和B-spline圖像金字塔進行對比分析。其中圖6（a）至圖6（d）是高斯圖像金子塔的第1層至第4層，圖7、圖8和圖9的（a）至（d）分別對應的是1階、2階和3階B-spline圖像金字塔圖像金子塔的第1層至第4層。

從圖6～9的圖像處理結果可以看出在相同圖像金子塔層數下的圖像，3階B-spline圖像金字塔算法的處理效果要比1階B-spline圖像金字塔算法的處理效果、2階B-spline圖像金字塔算法的處理效果和高斯圖像金字塔的處理效果好很多。

使用圖像信噪比SNR性能指標的計算方法來對兩種圖像金子塔的處理效果進行評價。SNR是用于比較被評價圖像與原圖像質量的參數，SNR的數值越高，圖像的質量越好。

SNR=10log10∑mi=1∑nj=1g（i，j）2∑mi=1∑nj=1[g（i，j）-f（i，j）]2（22）

其中：m和n分別為圖像長度和寬度上的像素個數;g（i，j）和f（i，j）分別為原始圖像和處理后的圖像在點（i，j）處的灰度值。

兩種圖像金子塔的SNR的評價結果如表1所示。

通過表1可以看出3階B-spline圖像金字塔算法的信噪比要比其他結構圖像金字塔的信噪比高。表明了3階B-spline圖像金字塔比1階、2階B-spline圖像金字塔和高斯圖像金字塔能保留更多的圖像信息，因此3階B-spline圖像金字塔結構在特征提取方面根據有優越性。故而，本文測試過程中均采用3階B-Spline圖像金字塔。

3基于圖像金字塔ORB的特征點匹配效果及分析3.1最近鄰FLANN算法特征點匹配方法及實現

本文首先采用快速近似最近鄰FLANN[21-23]算法對圖像進行雙向匹配以提高搜索效率和匹配精度。

設參考圖像中的特征點x在待配準圖像中最近鄰特征點為m，次近鄰特征點為n，點x，m， n的特征向量分別為 Fx、Fm和Fn，則FLANN近鄰匹配算法首先要分別計算點m、n和點x的漢明距離Dmx和Dnx;然后計算距離的比值T=Dmx/Dnx;如果Tlt;0.75，則點x與點n匹配成功，否則匹配失敗。

由于FLANN近鄰匹配采用的是距離比值法，一個特征點匹配出多個特征點的可能，所以本文分別使兩幅圖像相互的匹配，只保留兩次搜索匹配的結果一致的特征點，其余全部剔除，故得到一一對應的匹配結果。近鄰FLANN雙向匹配偽代碼為：

輸入：

descrip1——圖像描述子

descrip2——圖像描述子

輸出：

match_21 = 返回雙向匹配時同時特征存在的特征點對

match_12 = flann.knnMatch（descrip1， descrip2）

match_21 = flann.knnMatch（descrip2， descrip1）

for （遍歷match_12中的特征點對）

for （ 遍歷match_21中的特征點對）

if （match_12中不存在match_21中特征點對）

在match_21中刪除該特征點對

else

continue

返回 match_21

3.2圖像金子塔ORB特征點匹配測試及結果分析

本文分別對基于高斯圖像金字塔ORB算法和基于B-spline圖像金字塔ORB算法在尺度為20%、50%和70%的圖像下進行了仿真測試。其中特征點匹配采用FLANN近鄰雙向匹配的方法。具體的實驗參數為：特征點檢測數量為600;傳統ORB選擇的方法是Harris，本文改進的ORB算法選擇的角點度量是Shi-Tomasi和8層的高斯與B-Spline圖像金字塔結構。

測試圖像的相關數據如下：原始圖像的分辨率為400×300;尺度變化20%圖像的分辨率為320×240;尺度變化50%圖像的分辨率為200×150;尺度變化70%圖像的分辨率為120×90。

本文實驗硬件環境為：①處理器：Intel（R） Core（TM） i7-4720HQ CPU @ 2.60GHz ;②內存：8GB;③操作系統：64位windows10。

本文實驗軟件環境為：①編程語言：c++;②IDE：Visual Studio;③相關庫：OpenCV。

由圖11、圖14和圖17中可以看出基于高斯圖像金子塔的ORB算法的尺度不變性得到了一定的改善，特征點更加密集。

有圖12，圖15和圖18中可以看出基于B-Spline圖像金字塔的ORB算法的尺度不變性相比較于高斯圖像金字塔的ORB算法得到了更好的改善，特征點更加密集，得到更多的匹配的特征點。

表2、表3和表4分別列出了3種方法在不同尺度時特征點匹配結果。從表2、表3和表4中的數據結果中可以看出，當圖像尺度變化了20%時，基于高斯圖像金字塔ORB算法和B-spline圖像金字塔ORB算法與傳統ORB算法相比較，圖像的配準率分別提升了35.796%和39.049%;當圖像尺度變化了50%時，基于高斯圖像金字塔ORB算法和B-spline圖像金字塔ORB算法與傳統ORB算法相比較，圖像的配準率分別提升了38.45%和41.551%;當圖像尺度變化了70%時，基于高斯圖像金字塔ORB算法和B-spline圖像金字塔ORB算法與傳統ORB算法相比較，圖像的配準率分別提升了33.844%和39.791%。高斯圖像金字塔ORB算法和B-spline圖像金字塔ORB算法雖然在運行時間上要比傳統的ORB算法要長，但是在特征點匹配的正確率上得到了很大的提升，并且B-spline圖像金字塔的ORB算法相比高斯圖像金字塔的ORB算法在運行時間上和匹配準確率上要好。

通過以上測試可以看出當圖像尺度發生變化時，基于B-Spline圖像金塔的ORB算法相比較傳統的ORB算法的配準率提升40%;相比較基于高斯圖像金塔的ORB算法的配準率提升4%并且運行時間更快。綜上，基于B-Spline圖像金子塔的ORB算法更優。

4結論

本文提出基于B-spline圖像金字塔的ORB算法，實現對傳統ORB算法尺度不變性和匹配準確率方面改進，并將結果與傳統ORB算法和基于高斯圖像金字塔的ORB算法進行比較，證明了本文所提出的基于B-spline圖像金字塔的ORB算法在尺度不變性和匹配準確率方面要優于傳統ORB算法和基于高斯圖像金字塔的ORB算法。

參 考 文 獻：

[1]王愛麗，胡長雨，韓闖.基于ORB特征的復雜場景下的增強現實[J].哈爾濱理工大學學報，2018，23（2）：23.

WANG Aili，HU Changyu，HAN Chuang. Augmented Reality in Complex Scenarios Based on ORB Features[J]. Journal of Harbin University of Science and Technology， 2018，23（2）：23.

[2]YING L I， GONG G， SUN L. A Fast， Accurate and Dense Feature Matching Algorithm for Aerial Images[J]. Jourbal of Systems Engineering and Electroncls， 2020， 31（6）：12.

[3]YE Y， BRUZZONE L， SHAN J， et al. Fast and Robust Matching for Multimodal Remote Sensing Image Registration[J].IEEE Transactions on Geoscience and Remote Sensing， 2019（99）：1.

[4]王衛兵，白小玲，徐倩.SURF和RANSAC的特征圖像匹配[J].哈爾濱理工大學學報，2018，23（1）：117.

WANG Weibing， BAI Xiaoling， XU Qian. Feature Images of SURF and RANSAC Match[J]. Journal of Harbin University of Science and Technology， 2018，23（1）：117.

[5]LOWE D G. Object Recognition from Scale-invariant Keypoints[J]. Proc. INT′l Cnof. Conputer Vision， 1999：1150.

[6]LOWE D G . Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision， 2004， 60（2）：91.

[7]BAY H， TUYTELAARS T， VAN GOOL L. SURF： Speeded Up Robust Features[C]//European Conference on Computer Vision. Springer， Berlin， Heidelberg， 2006：404.

[8]RUBLEE E， RABAUD V， KONOLIGE K， et al. ORB： An Efficient Alternative to SIFT or SURF[C]//International Conference on Computer Vision. Barcelona， Spain. 2012：2564.

[9]ROSTEN E， DRUMMOND T. Machine Learning for High-Speed Corner Detection[J]//Proceedings of the 9th European Conference on Computer Vision， May， 2006：430.

[10]ROSTEN， EDWARD， PORTER. Faster Better： A Machine Learning Approach to Corner Detection[J]. IEEE Transactions on Pattern Analysis amp; Machine Intelligence， 2010，32（1）：105.

[11]姚海芳， 郭寶龍.一種基于ORB的特征匹配算法[J].電子設計工程，2019，27（16）：175.

YAO Haifang， GUO Baolong. Electronic Design Engineering. a Feature Matching Algorithm Based on ORB[J].Electronic Design Engineering， 2019，27（16）：175.

[12]HARRIS C G， STEPHENS M J. A Combined Corner and Edge Detector[C]//Proceedings of Fourth Alvey Vision Conference. Manchester，UK. 1988. 147.

[13]黃遠征， 尹春麗， 劉波. 基于改進的快速Shi-Tomasi特征點檢測算法的圖像拼接算法[J]. 機械設計與研究， 2018， 34（4）：70.

HUANG Yuanzheng， YIN Chunli， LI Bo. Image Mosaic Algorithm Based on Improved Fast Shi-Tomasi Feature Point Detection Algorithm[J]. Machine Design amp; Research， 2018， 34（4）： 70.

[14]嚴利民， 張婷婷.一種改進A-KAZE算法的特征點匹配方法[J].微電子學與計算機，2019，36（12）：64.

YAN Limin， ZHANG Tingting. An Improved Feature Point Matching Method of A-KAZE Algorithm[J]. Microelectronics amp; Computer， 2019， 36（12）： 64.

[15]WANG M， NIU S， YANG X. A Novel Panoramic Image Stitching Algorithm Based on ORB[C]//2017 International Conference on Applied System Innovation （ICASI）. IEEE， 2017：818.

[16]WANG Jian， YU Ming， REN Hong′e. Improved ORB Algorithm Used in Image Stitching[J]. Chinese Journal of Liquid Crystals and Displays， 2018， 33 （6）： 520.

[17]UNSER M. B-Spline Signal Processing： Part II-Efficient Design and Applications[J]. Trans. IEEE， 1993， 41.

[18]雷明， 楊丹， 張小洪， 等.基于協方差矩陣的B-樣條多尺度表示的角點檢測[J].光電工程，2008（2）：45.

LIE Ming， YANG Dan， ZHANG Xiaohong， et al. Corner Detection Based on B-spline Multi-scale Representation of Covariance Matrix[J]." Opto-Electronic Engineering， 2008（2）： 45.

[19]徐玲， 王成良， 馮欣， 等.多尺度積的協方差矩陣行列式的角點檢測方法[J].計算機工程與應用，2011，47（2）：160.

XU Ling， WANG Chengliang， FENG Xin， et al. Corner Detection Method of Multi-scale Product Covariance Matrix Determinant[J]. Computer Engineering and Applications，2011，47（2）：160.

[20]樊英平， 邢輝， 孟曉軍. 樣條尺度空間與Canny算子結合的弱邊緣檢測算法研究[J]. 現代電子技術， 2015（9）：57.

FAN Yingping， XING Hui， MENG Xiaojun. Research on Weak Edge Detection Algorithm Combining Spline Scale Space and Canny Operator[J]. Modern Electronics Technique， 2015（9）：57.

[21]周志偉， 袁鋒偉， 張亢， 等. SURF與FLANN算法結合的圖像匹配方法[J].智能計算機與應用，2019，9（6）：160.

ZHOU Zhiwei， YUAN Fengwei， ZHANG Kang， et al. Image Matching Method Combined with FLANN Algorithm[J]. Intelligent Computer and Applications，2019，9（6）：160.

[22]王金龍， 周志峰.基于SIFT圖像特征提取與FLANN匹配算法的研究[J].計算機測量與控制，2018，26（2）：175.

WANG Jinlong， ZHOU Zhifeng. Research Based on SIFT Image Feature Extraction and FLANN Matching Algorithm[J]. Computer Measurement amp; Control，2018，26（2）：175.

[23]廖勇， 黃偉宏， 鐘蕓.基于FAST特征檢測和FLANN特征點匹配算法的隧道展布圖拼接方法研究[J].交通節能與環保，2021，17（2）： 137.

LIAO Yong， HUANG Weihong， ZHONG Yun. Research on the Splicing Method of Tunnel Spread Map Based on FAST Feature Detection and FLANN Feature Point Matching Algorithm[J]. Energy Conservation amp; Environmental Protection in Transportation， 2021， 17（2）： 137.

（編輯：溫澤宇）