基于Harris-Hist的特征匹配及目標定位算法

張 震,張照崎,苗志濱,朱留存,李修明,麥 冬,張坤倫,周瑞凱

(1. 北部灣大學 先端科學技術研究院,廣西 欽州 535001； 2. 大連理工大學-立命館大學國際信息與軟件學院,遼寧 大連 116085； 3. 廣西機械工業研究院有限責任公司,南寧 530007)

0 引 言

圖像特征提取及特征匹配是計算機視覺、圖像處理和計算機圖形學的研究熱點[1],廣泛應用于目標定位、目標跟蹤[2]、圖像配準[3]、圖像拼接、圖像融合[4-5]和同步定位與地圖繪制(SLAM)[6]等領域. 這類方法首先對圖像中顯著特征進行提取,然后利用提取特征的描述子完成兩幅圖像間特征的匹配,再通過特征匹配關系建立圖像間的幾何變換模型[6-7].

特征點檢測算法多基于灰度的一階或二階導數尋找極值點. Moravec算法[8]是最早的基于梯度算法,其將每個像素點與其鄰域像素點進行相關性計算,具有較低相關性的點認定為特征點,該算法對噪聲較敏感. Harris等[9]對Moravec算法進行改進,提出了經典的Harris特征點檢測算法,但其對圖像旋轉、光線變化、噪聲和視點變換不敏感. Rosten等[10]提出了一種FAST(features from accelerated segment test)特征點檢測算法,若一個像素點圓形鄰域內有足夠多點的灰度值與其差別較大,則認為該點為特征點. FAST算法速度快,但易受噪聲影響. 上述特征點檢測算法都是基于單一尺度的,之后出現了一些能適應尺度變化的特征檢測算法,如尺度不變特征轉換(SIFT)算法[11]和SURF(speed-up robust features)算法[12]等. SURF是SIFT的改進算法,其利用Haar小波近似SIFT方法中的梯度操作,同時利用積分圖技術進行快速計算,使計算速度得到顯著提高. 這類算法需要用Laplace算子或Gauss差分算子構建尺度空間,增加了計算復雜度和匹配識別的難度,實時性較差.

文獻[8-10]主要考慮了特征點檢測,未給出描述子定義算法和匹配算法. SIFT算法在特征點周圍取16×16的鄰域,并將鄰域化分為4×4個小區域,每個小區域統計8個方向梯度,得到128維的向量作為該點的描述子. SURF算法在特征點周圍取一個帶方向的正方形鄰域,再將鄰域劃分為16個子區域,每個子區域統計4個Haar小波特征,得到64維的向量作為該點的描述子. 上述兩種特征描述子信息豐富,但運算代價較高,內存較大. Calonder等[13]提出了BRIEF描述子,該算法思想是在特征點鄰域內隨機挑選若干像素點對,對比各像素點對灰度值大小生成二進制序列作為描述子,極大節省了內存空間. Rublee等[14]對BRIEF描述子進行改造,提出了ORB(oriented FAST and rotated BRIEF)算法,根據角度參數提取BRIEF描述子,使其具有旋轉不變性. 目前，已有許多改進融合算法[15-21],如文獻[15-16]將Harris與SIFT算法相結合對原算法進行了改進,文獻[17]提出基于Harris-SURF特征匹配算法對原算法進行了改進,均取得了較好的實驗結果.

本文應用背景源于機器人視覺伺服定位、抓取,對定位精度和實時性要求較高. 經典的SIFT和SURF算法適應范圍廣、魯棒性好,但運行速度慢. ORB算法運行速度快,但定位精度不高. 本文在特征檢測及匹配定位過程中,同時滿足定位精度和實時性要求. 本文選擇Harris算法[9]提取特征點. 在特征匹配環節,計算特征點圓形鄰域內像素點灰度直方圖(Hist)作為特征描述子,通過計算兩幅圖像中各特征點描述子間的距離實現特征匹配. 最后,根據匹配結果,定位目標在場景圖像中的位置,模型總體流程如圖1所示.

圖1 模型流程Fig.1 Flow chart of model

1 Harris圖像特征點提取算法

1.1 算法原理

Harris算法思想：以待檢測點為中心加窗,獲取窗口內像素強度. 移動窗口后,獲取新窗口內像素強度,并計算移動窗口移動前后的強度差值. 若沿任意方向移動窗口,強度差值均較大,則認為待檢測點為特征點；若沿任意方向移動窗口,強度差值均較小,則認為待檢測點位于圖像平坦區域；若沿某特定方向移動窗口,強度差值很小,而沿其他方向移動窗口,強度插值很大,則認為待檢測點位于圖像邊緣. 根據該思想可得

(1)

其中：W(x,y)為窗口,一般取高斯窗口；u,v是以待測點為中心的偏移量；I為圖像像素值. 將

由Tayloy公式展開并截取,可近似為

(2)

則

(3)

R=detM-k(trM)2,

(4)

根據經驗k=0.04～0.06.

1.2 Harris算法

Harris算法實現步驟如下.

1) 計算圖像每個點的x,y方向梯度Ix,Iy:Ix=Gx?I,Iy=Gy?I;

5) 計算圖像每個點的特征響應強度R=detM-k(trM)2;

6) 根據閾值τ判定是否為特征點.

特征檢測效果如圖2所示,其中：(A)為原始圖像；(B)為原始圖像檢出的特征點；(C),(D)分別為(A)旋轉10°和-10°后檢出的特征點. 實驗中,最大特征響應強度的0.1倍作為閾值,可見Harris特征點具有旋轉不變性.

圖2 特征點檢測結果Fig.2 Detection results of feature points

2 基于灰度直方圖的特征匹配與定位算法

2.1 特征描述子定義

特征描述子應具可區分性,且當圖像發生平移、旋轉等變化時,應保持其不變性. 本文旨在滿足伺服定位、抓取中的定位精度和實時性要求,力求簡化描述子定義,減小匹配代價. 以特征點為中心,計算鄰域內點的灰度直方圖,作為該特征點的描述子. 本文用圓形鄰域取點,以保證描述子具有旋轉不變性,步驟如下.

1) 以特征點為中心取樣.

考慮到數字圖像的離散特性,圓形鄰域取樣公式定義為

(5)

其中: grayx和grayy分別為灰度圖像橫、縱坐標；cornerx和cornery分別為特征點橫、縱坐標；rwindow為取樣窗口半徑. 圖3(A)為按式(5)設計的取樣窗口,窗口大小為21×21,取到圓形鄰域內349個點,取樣窗口大小可根據實際需要進行調整.

2) 根據取樣結果計算灰度直方圖,并做歸一化處理.

以圖2(B)中右上角特殊標記特征點為例,采樣結果如圖3(B)右上角小圖所示. 灰度直方圖計算中,設置Bins數為16,得到16維向量

H=(0,0,0,0,1,5,22,43,11,157,46,8,17,34,5,0),

對該特征向量做歸一化處理,歸一化公式為

(6)

歸一化后向量為

G=(0,0,0,0,0.006,0.042,0.113 8,0.245 5,0.047 9,1,0.221 6,0.095 8,0.101 8,0.179 6,0.036,0),

即為特征點的描述子,歸一化直方圖如圖3(B)所示,圖3(C),(D)分別為圖2(C),(D)中對應特殊標記特征點的歸一化直方圖. 由圖3可見,3個對應角特征點的描述子相似度很高,保持了旋轉不變性.

圖3 特征點的描述子Fig.3 Descriptors of feature points

2.2 特征匹配與目標定位算法

特征匹配的依據是特征點描述子間的相似度,本文采用巴氏距離作為度量標準,巴氏距離定義為

(7)

特征匹配步驟如下：

1) 選擇標準圖像中的任意描述子G[m]；

2) 在場景描述子中尋找G′[n],使得d(G[m],G′[n])最??；

3) 若d(G[m],G′[n])<τ,則認為標準圖像特征點m與場景圖像特征點n匹配.

特征匹配結果如圖4所示,其中每條連線對應的兩點為匹配的特征點.

目標定位過程如下：

1) 根據匹配結果,尋找描述兩組特征點間的變換關系,即估計歸一化單應性矩陣為

(8)

滿足

(9)

2) 根據標準圖像4個頂點坐標,利用式(9)計算對應場景圖像4個頂點坐標,從而定位目標.

目標定位結果如圖4所示,紅色框即為定位的標準圖像在場景圖像中位置,利用式(9)可計算標準圖像每個像素點在目標圖像中的位置.

圖4 旋轉10°(A)和-10°(B)的特征匹配及目標定位結果Fig.4 Results of feature matching and target location for 10° (A) and -10° (B) rotation

3 實驗結果對比分析

圖5和圖6分別為本文算法與SIFT[11],SURF[12],Harris-SIFT[16],Harris-SURF[17],ORB[14]算法的匹配及定位效果對比. 圖5和圖6分別采用peppers圖像、barche圖像作為標準圖像,各自旋轉10°后作為場景圖像. 通過調整算法參數,4種算法特征匹配數量基本相同. 對于特征點分布,本文算法、Harris-SIFT算法、Harris-SURF算法更合理,SIFT算法、SURF算法次之,ORB算法較差. SIFT,SURF,Harris-SIFT,Harris-SURF算法及本文算法定位精度均表現較好,視覺觀察差別較小,明顯優于ORB算法. 下面對圖6中barche圖像做更深入的實驗數據對比,考察4種算法的運行速度和定位精度.

實驗環境：電腦主頻3.6 GHz,內存16 GB,操作系統Windows10 64位,開發平臺VSC++,SIFT,SURF,ORB算法實現調用了OPENCV庫函數. 由于SIFT,SURF算法為非免費資源,無法在RELEASE模式下運行,為具可比性,實驗中統一采用DEBUG模式運行,時間單位為ms. 在RELEASE模式下,運行速度約可提升10倍. 表1為圖6中barche圖像各角度下定位過程運行時間對比. 由表1可見,ORB算法耗時最少；本文算法、Harris-SURF算法、Harris-SIFT算法次之；SURF算法和SIFT算法實時性較差.

平移誤差定義為：定位中估計的4個邊界頂點坐標與場景中對應的4個實際邊界頂點坐標之間距離的最大值. 表2為不同算法在各角度下定位過程平移誤差的對比. 由表2可見,平移定位誤差均值排序為：SIFT算法(0.23)<本文算法(1.20)

表1 不同算法的運行時間(ms)對比

表2 不同算法定位過程平移誤差(像素)的對比

旋轉誤差定義為：定位中估計的4條邊界線與場景對應的4條實際邊界線角度偏差絕對值的最大值. 表3為不同算法在各角度下定位過程旋轉誤差的對比. 由表3可見,旋轉定位誤差均值排序為：SIFT算法(0.04)<本文算法(0.21)

表3 不同算法定位過程旋轉誤差(°)對比

鑒于機器人視覺伺服定位、抓取過程中,相機位置固定、拍攝角度不變、光線穩定,每次觸發拍照時,工件圖像只發生平移和旋轉,不存在尺度變化和仿射變換,故在定位精度實驗中,重點對比了平移和旋轉誤差. SIFT算法定位精度最高,本文算法次之,Harris-SIFT算法和Harris-SURF算法效果較好,SURF算法一般,ORB算法不能滿足精度要求. 在運行速度上,ORB算法實時性最好,本文算法次之,Harris-SIFT算法、Harris-SURF算法實時性較好,SURF算法、SIFT算法難以滿足實時性要求. 因此,本文算法綜合效果最好.

綜上可見,本文算法在特征提取環節繼承了Harris算子定位精度高、具有旋轉不變性的優點,同時也保留了其對尺度變化敏感的不足；在特征匹配環節,提出的描述子定義簡單、易實現,匹配代價小,實時性較好,但對光線變化較敏感.