足球機器人視覺目標識別的PCA-SIFT算法

李彤斐， 楊馬英

(浙江工業大學信息工程學院，浙江杭州310023)

Robocup即機器人世界杯足球錦標賽，是目前國際上最具影響的世界杯機器人足球賽［1］。為了能讓一個機器人球隊像人類一樣進行足球比賽，包含了很多領域技術的融合，比如機械電子學、機器人學、傳感器信息融合、智能控制、通信、計算機視覺、計算機圖形學、人工智能等。

計算機視覺相當于足球機器人的眼睛，為了讓機器人定位自身和其他目標并實現合作與對抗，圖像的特征提取以及目標識別是極為關鍵的一步。特征提取有基于邊緣、角、區域和脊的方法。目前已經成熟的特征提取算法有:(1)Hough變換［2］;(2)Harris角點檢測［3］;(3)SIFT 算法［4］;(4)SURF算法［5］;(5)Mean Shift算法［6］等。Hough 變換于1962年由Paul Hough提出，對圓和直線比較敏感;Harris角點檢測在1988年由Harris等人提出，是基于模板的角點檢測算法，具有旋轉不變性。SIFT算法由D.G.Lowe 1999年提出，其特征能對旋轉、尺度縮放、仿射變換、視角變化、光照變化等圖像變化因素保持一定的不變性，而對物體運動、遮擋、噪聲等因素也保持較好的可匹配性，從而可以實現差異較大的兩幅圖像之間的特征匹配，可以說應用范圍非常廣泛，也比較全面。SURF算法由Herbert Bay和Luc Van Gool等人在2006年提出，是SIFT算法的快速算法［7］。Mean Shift算法中的Mean Shift概念最早是由Fukunaga等人于1975年在一篇關于概率密度梯度函數的估計中提出來的，后由Comaniciu等人發展，在圖像平滑和圖像分割中Mean Shift都得到了很好的應用［8］。

考慮到球場上待識別的物體不只是球、門柱，為了更好地幫助決策系統作出攻守策略判斷，識別比賽雙方機器人也是非常關鍵的環節，同時比賽場地存在光照條件變化、場外物體干擾等，移動目標的視頻圖像也會出現扭曲、模糊等情形，所以認為SIFT算法的全面性能滿足類人機器人足球比賽圖像處理和目標識別的要求。但是SIFT算法的實時性比較差，這會直接影響到機器人的決策。因此文中借鑒了Yan Ke和 Rahul Sukthankar提出的PCA-SIFT方法［9］。將主成分分析(PCA)算法用于對SIFT算法描述子進行降維，生成低維的PCA-SIFT描述子，并用最近鄰法進行特征點匹配，實現機器人場地目標識別。

1 背景知識

1.1 尺度不變特征變換算法原理

尺度不變特征變換(SIFT)算法的計算過程如下:首先構造一個尺度空間，即圖像金字塔，并對其差分計算;然后粗略地檢測差分金字塔空間中的極值點;再去除一些邊緣響應等干擾，以進行精確定位;最后計算每個極值點的梯度值和梯度方向，形成描述子。具體各步驟的描述如下:

1)構造尺度空間 圖像的尺度空間L(x，y，σ)，定義為一個變化尺度的高斯函數G(x，y，σ)與原圖像I(x，y)的卷積

m，n表示高斯模板的維度。

為了高效地檢測極值點，Lowe用高斯差分算子代替拉普拉斯算子進行極值檢測:

在實際計算中，使用高斯金字塔每組中相鄰上下兩層圖像相減，得到高斯差分圖像(DOG)，如圖1所示。

圖1 高斯圖像金字塔到差分高斯圖像金字塔的變換Fig.1 Transformation from Gaussian image pyramid to differential Gaussian image pyramid

2)檢測尺度空間極值點 這里指的是初步確定的關鍵點，即差分高斯金字塔內的局部極值點。如圖2所示，共要比較26個相鄰點。

圖2 DoG空間極值檢測Fig.2 Space extremum detection of DoG

3)精確定位極值點 由于DoG值對噪聲和邊緣較敏感，因此，在上面DoG尺度空間中檢測到的局部極值點還要進行進一步的檢驗才能精確定位。

為了提高關鍵點的穩定性，需要對DoG空間函數進行擬合:

4)為每個關鍵點指定方向參數 通過計算每個極值點的梯度值來確定方向。像素點的梯度表示:

梯度幅值:

梯度方向:

完成關鍵點的梯度計算后，使用直方圖統計領域內像素的梯度和方向。梯度直方圖將0～360°的方向范圍分為36個柱，其中每柱10°。如圖3所示，直方圖的峰值方向代表了關鍵點的主方向。

圖3 關鍵點方向Fig.3 Direction histogram of key points

5)關鍵點描述子生成 首先，確定計算描述子所需的圖像區域。其次，將坐標軸旋轉為關鍵點的方向，以確保旋轉不變性。再將領域內的采樣點分配到8個方向上，計算其權值。插值計算每個種子點8個方向的梯度。如上統計的4×4×8=128個梯度信息即為該關鍵點的特征向量。

1.2 PCA方法概述

PCA是對數據空間降維進行多元統計分析的方法。它計算主成分的目的是將高維數據投影到較低維空間，一般步驟如圖4所示。

圖4 PCA方法降維的一般步驟Fig.4 PCA-based dimensionality reduction steps

2 改進的SIFT算法

因為傳統的SIFT算法產生的關鍵點的描述子包含128維的梯度信息，特征匹配時計算量相當龐大，直接影響到算法實時性。文中提出改進的PCA-SIFT目標識別算法，使用PCA方法將128維描述子降維，以提高匹配速度。

改進的SIFT算法主要工作分為3部分，分別如以下各小節描述。

2.1 生成SIFT特征點描述子

改進的SIFT算法中，首先要生成128維的SIFT特征點描述子，這里用的是傳統SIFT算法:分別預處理原圖像與待匹配的圖像，若不為灰度圖像就轉為灰度圖像;然后構造尺度空間，并生成差分圖像金字塔;檢測尺度空間極值點，為每個極值點確定方向參數;最后生成128維的SIFT特征點描述子。特征向量形成后，為了去除光照變化的影響，需要對它們進行歸一化處理。

其中，檢測以及精確定位極值點時，為了找到這些點，每一個像素點都要與它的相鄰點比較，判斷該點是否為極值點。中間的檢測點和它同尺度的8個相鄰點與上下相鄰尺度對應的9×2個點，共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。為了提高關鍵點的穩定性，需要對DOG空間函數進行擬合:

其極值點

在計算過程中，分別對圖像的行、列及尺度進行修正，去除那些對比度較低的不穩定極值點。

對于DoG產生的邊緣響應的點，用Hessian矩陣計算主曲率:

DoG的主曲率和H的特征值成正比，為了避免直接計算這些特征值，令特征值為α，β，(α ＞ β)則

時，將關鍵點保留，反之剔除。

2.2 PCA對SIFT特征描述子降維

改進的SIFT算法第2步是用PCA方法對SIFT特征描述子進行降維。具體步驟如下:

1)輸入兩幅待匹配圖像中所有關鍵點(設為n個)的128維SIFT特征描述符，將輸入的這n個特征描述符作為樣本，寫出樣本矩陣為［x1，x2，…，xn］T，其中xi表示第i個特征點的128維特征向量。

2)計算n個樣本的平均特征向量:

4)構建協方差矩陣

5)求協方差矩陣的128個特征值λi和128個特征向量ei。

6)將求出的128個特征值按從小到大的順序進行排列λ1≥λ2≥…≥λ128和對應的特征向量［e1，e2，…，e128］。

7)選取對應t個最大特征值的特征向量作為主成分方向。

8)構造一個128×t的矩陣A，它的列由t個特征向量組成。

9)把原始的128維描述符根據下式投影到所計算出的n維子空間M中，就可以得到PCA-SIFT的描述符 y1，y2，…，yn了，即 yi=xi× A。

實驗中，矩陣A的大小為128×t，xi的大小為1 ×128，即xi×A的大小為1×t，即每一個yi就是一個t維的特征描述子，也就是把傳統的128維SIFT描述子降成了t維的PCA-SIFT描述子。

2.3 特征點匹配

在提取完特征點之后，改進的SIFT算法第3步，即特征點匹配。這里選用最近鄰的方法進行匹配。對于待匹配圖像中的一個特征點，把它逐一與已知圖像中的特征點計算歐氏距離，找出距離最近與次近的點，當最近點與次近點的比值小于一個閾值時，認為這兩點是匹配的。計算時運用以下公式:

其中，D1為最近點距離，D2為次近點距離。

3 實驗及結果

實驗需要在機器人足球比賽場地抓取一些圖像(像素為500×836)。如圖5所示，左側全部為原圖，右側分別為扭曲后、光照變暗以及用于識別比賽雙方機器人的圖像。

圖5 待處理的3對圖像Fig.5 Three pairs of images to be processed

實驗配備的計算機為Mobile AMD Sempron(tm)Processor 3200+ 處理器，內存為1.60 GHz，960 MB。仿真平臺為 Matlab7.0.1。

針對上述存在圖像扭曲、光照變化以及雙方機器人的圖像，分別運用SIFT算法與PCA-SIFT算法提取特征點，并用最近鄰法進行匹配，觀察算法的計算效率與匹配結果。計算中PCA-SIFT的參數t取10，匹配算法的參數 r取0.6。

圖6 為圖像扭曲后與原圖的匹配效果。可以發現(b)圖明顯比(a)圖的匹配對數少，即經過改進的PCA-SIFT算法有明顯的降維作用，但是(b)圖正確匹配率不如(a)圖高，說明改進的PCA-SIFT算法在圖像扭曲的情況下效果不是很好。

圖7 為雙方機器人的識別效果。圖中機器人分別與原圖的我方機器人進行匹配(用線條連接兩幅圖像中認為匹配的點)。匹配度高的一方為我方機器人，反之為對方機器人。可以發現，圖7(a)，(c)顯然比圖7(b)，(d)的匹配對數多，此時認為圖像中左側機器人為我方機器人，右側機器人為對方機器人。

從表1統計的數據可以發現，PCA-SIFT算法在圖像扭曲與雙方機器人識別方面于SIFT算法相比較，匹配對數明顯下降，有很顯著的降維作用;而在光照變化的條件下降維不太明顯。另外，在雙方機器人識別方面，圖7b，d比圖7a，c的匹配對數少很多，可以判斷圖7b，d為對方機器人。

從表2統計的數據中可以發現，在3種條件下PCA-SIFT都能保持較好的匹配率，特別是在光照變化和雙方機器人識別方面占有優勢。另外，用匹配率的數據同樣可以判斷是否為我方機器人，本實驗數據顯示對方機器人的匹配率為零，則匹配率不為零的為我方機器人。

受限于計數器的精度，文中采集的圖像均為500×836 像素，而在Robocup比賽中機器人抓圖得到的圖像像素較低，所以相對而言統計出來的匹配時間較長。從表3可以發現，PCA-SIFT算法普遍比SIFT算法快，特別是在光照變化的條件下省下的時間比較多。

表1 不同條件下2種算法的匹配對數Tab.1 Number of matching pairs單位:對

表2 正確匹配率Tab.2 Correct matching rate單位:對 /對

表3 不同條件下2種算法的匹配時間Tab.3 Matching time under different conditions單位:s

綜合以上結果，可以得出結論:SIFT算法用于機器人足球的場景來識別比較復雜的目標時有很好的識別率;經過改進的SIFT算法，即PCA-SIFT算法較SIFT算法有降維加速計算的效果，同時能保持較高的匹配率，且在識別雙方機器人方面有較強的優勢。

4 結語

文中提出改進的PCA-SIFT目標識別算法，將經典SIFT算法與PCA方法相結合，獲取低維的PCA-SIFT描述子，之后用最近鄰方法完成特征點匹配。該方法與傳統SIFT算法在多種場景條件下作了對比，實驗證明在機器人足球比賽場景下經過改進的PCA-SIFT目標識別算法既保持了匹配率，又縮短了匹配時間，是一種機器人足球比賽適用的提取方法。

［1］Vadakkepat P，Sin N B，Goswami D.Soccer playing humanoid robots:processing architecture，gait generation and vision system［J］.Robotics and Autonomous Systems，2009，57:776-785.

［2］梁霄穎，李永新，張杰，等.Hough變換在足球機器人視覺處理中的應用［J］.機械設計與制造，2008(1):167-169.LIANG Xiao-ying，LI Yong-xin，ZHANG Jie，et al.Applications of Hough transform in soccer robot vision processing［J］.Mechanical Design and Manufacture，2008(1):167-169.(in Chinese)

［3］Harris C，Stephens M.A combined corner and edge detector［C］//Manchester:Proceedings of the 4th Alvey Vision Conference.Manchester，UK:The University of Sheffield Printing Unit，1988:147-151.

［4］Lowe D G.Distinctive image features from scale-invariant key-points［J］.International Journal of Computer Vision，2004，17(1):43-76.

［5］Bay H，Gool V.SURF:speeded up robust features［C］//European Conference on Computer Vision.Graz，Austria:Springer-Verlag，2006，1:404-417.

［6］Comaniciu D，Meer P.Mean shift:a robot approach toward feature space analysis［J］.IEEE Transaction on Panttern Analysis and Machine Intelligence，2002(5):603-619.

［7］Khan N Y，McCane B，Wyvill G.SIFT and SURF performance evaluation against various image deformations on benchmark dataset［C］//International Conference on Digital Image Computing:Techniques and Applications.Queensland，Australia:IEEE Computer Society，2011，9:501-506.

［8］ZHOU H Y，YUAN Y，SHI C.Obiect tracking using SIFT features and mean shift［J］.Computer Vision and Image Understanding，2009，113:345-352.

［9］Ke Y，Sukthankar R.PCA-SIFT:a more distinctive representation for local image descriptors［C］//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC:IEEE Computer Society，2004.