一種基于特征光流的角點匹配算法*

曹倩倩，蔡光程(.宿州學院數學與統計學院，安徽宿州34000; .昆明理工大學理學院，昆明650500)

一種基于特征光流的角點匹配算法*

曹倩倩1，蔡光程2
(1.宿州學院數學與統計學院，安徽宿州234000; 2.昆明理工大學理學院，昆明650500)

摘要:提出了一種基于特征光流的角點匹配算法.首先，獲取經過均勻化處理的特征角點;然后，考慮角點處的局部光流，求解角點處的光流場，從而得到角點處的粗略光流失量，實現了圖像角點間的近似匹配;最后，把特征光流作為約束條件，根據兩幀圖像角點集之間的坐標關系，排除非正常角點，從而完成對特征角點的精確匹配.仿真實驗表明:算法在減少計算量的同時可以提高匹配精度，進而實現高精度運動目標跟蹤.

關鍵詞:角點匹配;光流估計;仿射變換;運動目標檢測

所謂的特征點匹配［1］，指的是在兩幀圖像的特征點集之間建立某種幾何映射和對應關系.由于在實際操作過程中噪聲、非剛性映射等情況的存在，使得特征點匹配的難度加大.圖像的光流場［2］反映了圖像上每一點灰度的變化趨勢，是帶有灰度值的像素點在平面上運動而產生的瞬時速度場，是一種真實運動場的近似估計.但大多數光流法的計算過程復雜，無法滿足實時性要求，且抗噪性差.算法同時彌補了光流法和特征點匹配法的不足，是一種精度較高且較為穩定的的運動目標檢測算法.

1　光流法的計算

1.1經典的光流法

經典的Horn－Schunck光流法［3］基于亮度常數模型，亮度常數模型表示為

式(1)假設圖像上的特征點當Δt→0時，亮度I保持恒定.其中，u(x，y)和v(x，y)表示特征點處光流的水平分量和垂直分量.根據圖像連續變化假設，將式(1)左邊進行一階Taylor級數展開，得到了光流基本方程:

方程(2)不足以求解出u，v兩個變量的光流場，即只能求出光流沿梯度方向的值.在此基礎上，加上不同的附加約束條件就構成了不同的光流計算法.經典的Horn-Schunck光流法認為同一運動物體引起的光流應該是平滑的，即在給定鄰域內▽2u+▽2v應該盡可能小，從而提出在光流場(u，v)T上的附加約束條件，

盡可能小，根據亮度常數模型:

也要盡可能小.

于是問題歸結為求變分問題

其中，λ為權值.利用變分計算和高斯賽德爾迭代法，可以得到(u，v)T的估值.

1.2改進的光流法

Horn-Schunck光流法在整幅圖像上都加了平滑約束條件，但在實際過程中該約束條件并不適用于垂直于邊界的方向，會模糊運動物體的邊界，但對于灰度變化不是很強烈的地方，則影響不大.因此，在圖像灰度變化強烈的地方不應該加上平滑約束條件.設圖像的梯度方向(即灰度變化最為強烈的方向)為▽I = (Ix，Iy)T，垂直于梯度的方向(即灰度變化不是很強烈的方向)為▽q=(Iy，－Ix)T.現只將平滑約束條件加在垂直于梯度的方向上.

令▽u=(ux，uy)T，▽v=(vx，vy)T，分別向垂直于梯度的方向做投影，得

則其范數的平方和

問題歸結為求變分問題

將式(7)離散化

對式(8)求關于uk，l和vk，l的偏導數，并令其為零，有

由式(9)、(10)可以解出uk，l和vk，l，其遞推形式如下:

改進的光流法與Horn-Schunck光流法的遞推估計式相似.經典的光流法在整個圖像上加平滑約束條件，在用四鄰域表示平均速度時，權值都是0.25;改進的光流法則只在梯度的垂直方向上加平滑約束條件，故在用領域表示平均速度時與灰度值有關.

由于光流場的計算過程中使用了泰勒展開，忽略了二階以上的高階項，因此不可避免地會產生模型誤差.此外，圖像連續變化的假設限制了此算法只能計算運動量較小的序列圖像，這與實際過程中的大多數場景不相符.采用圖像金字塔［4］可以有效地解決這個問題.將圖像分解到低分辨層后，序列幀圖像之間的運動量將變得足夠小，從而滿足光流計算的約束條件，實現對變化較快的序列圖像進行檢測及跟蹤.

2　角點檢測算法

2.1Harris角點檢測算法

Harris角點檢測算法［5，6］是由Chris Harris和Mike Stephens在1988年提出的.算法是在Moravec算法的基礎上發展起來的，是一種常用的點特征提取算法.算法只用了灰度的一階差分及濾波，因此對于圖像旋轉、灰度變化、噪聲影響及視覺變換具有較高的穩定性及魯棒性，且操作簡單.

Harris角點檢測算法的原理是將所處理的圖像窗口w向任意方向移動微小位移(x，y)，則其灰度改變量可定義為

其中，X和Y是一階灰度梯度，對圖像求卷積得

為了提高算法的抗噪性，對圖像窗口w進行高斯平滑，

此外定義A=X2w，B=Y2w，C=(XY)w及矩陣.

Harris認為，矩陣M的兩個特征值λ1和λ2是自相關函數的主曲率［7］.即如果點(x，y)是角點，那么點的兩個特征值都是正值，且是以(x，y)為中心的區域的局部最大值.特征點可用如下響應函數R表示:R = det(M)－k［trace(M)］2

(14)

其中，trace(M)是表示矩陣M的跡，trace(M) =λ1+λ2; det(M)表示矩陣M的行列式的值，det(M) =λ1×λ2; k為實驗值，一般取0.04～0.06，δ的最佳取值區間為0.8～1.2.當點(x，y)的R值大于某一個閾值TR時，點所對應的位置點就是角點.

2.2角點的均勻化處理

為了保證角點的均勻分布，首先對圖像進行分塊，既避免了大面積越界分塊的存在，又使得對較大面積圖像處理時有同樣的效果.然后將每一分塊中被檢測出的角點按其R值大小進行排序，保留R值相對較大的角點.從而，每一分塊中特征顯著的角點被檢測出來并被保留，初步實現了角點分布的均勻性.但仍可能出現角點在局部區域聚簇的現象，故加入鄰近點剔除策略.即選用一個模板對整幅圖像進行處理，如果模板下存在不止一個的角點，只保留其R值最大的角點，從而剔除鄰近點，避免角點聚簇.

3　基于特征光流的角點匹配算法

3.1初始匹配

為方便敘述，不妨將待匹配的兩幀圖像稱為前一幀與當前幀(前一幀的后一幀).首先用Harris角點檢測算法獲得圖像的角點，并對角點進行均勻化處理.然后利用改進的特征光流法，得到角點處的粗略光流失量［8］.由于光流場的解是建立在一定的附加約束上，具有一定程度的不精確性，所以光流u，v反映了圖像在像素點(x，y)處相對于另一幅圖像的粗略運動速度，依據u(x，y)和v(x，y)可以求出兩幀圖像角點集間的近似匹配，即R1(x+u，y+v)與R2(x，y).

3.2校對匹配

3.2.1排除異常光流

由于待匹配的兩幅圖像之間可能存在旋轉，那么對應的角點集之間同樣可能存在旋轉.假設匹配圖像之間的幾何變換關系為仿射變換.根據仿射模型公式建立方程:

3.2.2角點的精確匹配

依次比對各角點對之間的距離差，盡可能地排除誤匹配的角點，進而完成了角點的精確匹配.

4　實驗結果與分析

為驗證算法的有效性及穩定性，對攝像機獲得的視頻序列圖像進行了實驗，所采用的操作軟件為MATLAB7.0，計算機的硬件配置為Pentium2.80主頻，內存為DDRII2G.圖1為視頻序列的連續的兩幀圖像，第104幀(前一幀)和第105幀(當前幀)，圖像大小為640×480.首先采用Harris角點算法對兩幀圖像進行角點檢測，并采取均勻化處理，檢測結果如圖3、4所示，為計算局部角點出的光流做準備，此處角點數取11個;對檢測過后的圖像進行經典的光流場分析，得圖4;再用改進后的光流法對檢測過后的圖像進行光流場分析，得圖5;最后，僅在角點所在的小區域使用改進后的光流法，從而得到的光流場分析如圖6所示.由于原始圖像尺寸過大，為方便分析，圖4、5、6均只顯示了圖像的主要部分，且光流場速度擴大了10倍.

由圖像分析可知，改進后的光流法較好的保留了運動邊界，減少了平滑約束的影響.通過考察連續5幀視頻序列圖像使用兩種光流法的時間也可以看出算法的優勢(表1).表1中的時間數據均為CPU時間.

圖1　視頻序列的第104幀和105幀

圖2　第104幀中的角點結果

圖3　第105幀中的角點結果

圖4　經典的光流法

圖5　改進后的光流法

圖6　角點處的光流場(局部光流)

表1　連續5幀使用兩種光流法的時間比較

5　結論

算法首先用Harris算子提取當前幀和參考幀的角點，并對角點進行均勻化處理;然后將改進后的局部光流法應用在角點所在的局部區域，從而完成了兩幀圖像角點集之間的粗略匹配;最后，把角點處的特征光流作為約束條件，由兩幀圖像角點集之間的坐標關系，排除異常角點，從而完成了角點的校對匹配.仿真實驗說明，算法能夠實現較準確的圖像匹配，且提高了匹配的實時性，對于運動目標跟蹤有一定的應用價值.

參考文獻:

［1］黃波，楊勇，王橋，等.一種自適應的光流估計方法［J］.電路與系統學報，2001，6(4):92-96

［2］金輝，高文.基于特征流的面部表情運動分析及應用［J］.軟件學報，2003，14(12):2098-2105

［3］HORN B K P，SCHUNCK B G.Determining Optical Flow［J］.Artificial Intelligence，1981(17):185-203

［4］衛保國，李晶.一種針對大尺寸運動的快速光流算法［J］.計算機應用研究，2012，29(9):3551-3557

［5］KIM J G，MITTRA S K.A Local Relahod for Optical Flow Estimation［J］.Signal Procssing:Image Communication，1997(11):21-38

［6］TISSAINAYAGAM P，SUTER D.Assessing the Performance of Corner detectors for Point Feature Tracking Applications［J］.Image and Vision Computing，2004(22):663-679

［7］王永明，王貴錦.圖像局部不變性特征與描述［M］.北京:國防工業出版社，2010

［8］楊常清，王孝通，李博，等.基于特征光流的角點匹配快速算法［J］.光電工程，2006，33(4):85-88

Corner Matching Algorithm Based on Feature Optical Flow

CAO Qian-qian1，CAI Guang-cheng2
(1.School of Mathematics and Statistics，Suzhou University，Suzhou 234000，China;
2.Faculty of Science，Kunming University of Science and Technology，Kunming 650500，China)

Abstract:This paper presents a corner matching algorithm based on feature optical flow.Firstly，the homogenized corners are extracted.Secondly，judging from the improved approach of feature optical flow estimation，the local optical flow estimation on the corners can be calculated，rough optical flow vectors are gained and approximate matching of the corners is achieved.Finally，optical flow estimation of corners is acted as constraint condition.According to the coordinate relations between two corner-sets of images，abnormal corners are excluded.In this way，the corners of the two images can be accurately matched.The simulation experiment shows that the presented algorithm can reduce the computational complexity and raise matching precision so as to precisely track moving object.

Key words:corners matching; optical flow estimation; affine transformation; motion object detection

中圖分類號:O151.21

文獻標識碼:A

文章編號:1672－058X(2015) 08－0028－06

doi:10.16055/j.issn.1672－058X.2015.0008.007

收稿日期:2015－01－02;修回日期:2015－03－21.

*基金項目:宿州學院科研平臺開放課題(2013YKF04);宿州學院一般科研項目(2013yyb06);宿州學院一般科研項目(2013yyb07).

作者簡介:曹倩倩(1987-)，女，安徽宿州市人，碩士研究生，從事數字圖像處理研究.