基于改進SIFT算法的交通事故圖像匹配*

李 旋，韓天園，呂凱光，劉永濤

(長安大學 汽車學院，陜西 西安 710064)

0 引言

交通事故現(xiàn)場具有暫時性和復(fù)雜性，通過無人機航拍可以迅速獲得事故現(xiàn)場大范圍場景圖像，有效解決人工勘測造成的交通擁堵和細節(jié)遺漏。為獲得事故現(xiàn)場的全局圖像，需要對無人機航拍得到的圖像進行拼接，圖像拼接的關(guān)鍵在于特征點的提取與匹配。

Lowe[1]提出尺度不變特征變換(Scale-Invariant Feature Transform，SIFT)算法，在圖像特征匹配上能取得較好效果，在此基礎(chǔ)上，針對SIFT算法進行改進的文獻有很多，主要在算法的匹配精度、匹配效率上進行改進[2-6]。國外亦進行了相關(guān)研究[7]。

除此之外，為使算法更加適合某些特定場景，一些學者針對不同應(yīng)用場景對算法進行改進，耿慶田等[8]通過構(gòu)建同心圓鄰域檢測范圍對車標進行提取；張護望等[9]在SIFT的基礎(chǔ)上采用內(nèi)切圓選擇特征描述符對列車軌道板圖像進行識別。近年來基于神經(jīng)網(wǎng)絡(luò)的圖像識別的方法表現(xiàn)出很大優(yōu)勢[10-12]。國外亦進行了相關(guān)研究[13-15]。

對文獻的綜述中發(fā)現(xiàn)，目前針對交通事故現(xiàn)場的圖像匹配研究較少。因此，本文從特征點數(shù)量、特征點匹配精度與效率3個方面出發(fā)，提出1種改進的SIFT算法。通過改進的算法，為事故鑒定提供技術(shù)支撐，從而提高事故認責的準確性。

1 經(jīng)典SIFT算法

1.1 基本原理

經(jīng)典SIFT算法主要包括以下步驟：1)高斯卷積建立尺度空間；2)構(gòu)建高斯差分金字塔檢測極值點，通過遍歷的方式對極值點進行驗證；3)刪除邊緣響應(yīng)和低對比度的極值點；4)通過梯度直方圖確定特征點的方向；5)建立特征描述符。

1.2 算法的不足

算法的好壞主要根據(jù)匹配精度、匹配效率2個指標判斷。針對無人機航拍的交通事故現(xiàn)場圖像，如圖1所示，經(jīng)典SIFT算法主要存在以下3個問題：

圖1 無人機航拍交通事故現(xiàn)場Fig.1 UAV aerial photo of traffic accident scene

1)特征點數(shù)量不足。考慮無人機航拍受到光照、風速等環(huán)境條件影響較大，同時事故現(xiàn)場存在較多方向性較強的路面特征，如斑馬線、車道線等，僅通過SIFT算法提取到的特征點數(shù)量過少。

2)特征描述符維度過高。經(jīng)典SIFT算法是將特征點鄰域劃分為4×4區(qū)域，每個區(qū)域包括8個方向，構(gòu)建特征4×4×8=128維的描述符。在特征點匹配過程中計算量過大，匹配耗時過長。

3)特征點匹配成功率較低。根據(jù)普通圖像上部分特征點距離分布(包括前15個點)，如圖2所示。特征點1，2，3，4均為實際圖像中匹配成功的點，但3，4在SIFT算法下匹配失敗。具體地，觀察多組特征點發(fā)現(xiàn)，當距離的最小值與次最小值之間存在較大變化梯度時，2者的比值才滿足閾值要求，即匹配成功。對于未匹配成功的特征點3和4，距離的最小值與次最小值之間變化梯度較小，2者的比值不滿足閾值要求，因此匹配失敗。僅通過距離的最小值與次最小值比值設(shè)定的單閾值判斷方法，無法準確地對事故現(xiàn)場特征點進行匹配，匹配成功率較低。

圖2 普通圖像上部分特征點距離分布Fig.2 Distance distribution of some feature points on ordinary image

2 改進的算法

針對上述3個問題，在經(jīng)典SIFT算法的基礎(chǔ)上做出如下改進：

1)針對特征點數(shù)量不足的問題。由于Gabor濾波在特征提取過程中能夠提供良好的方向選擇以及尺度選擇特性，同時小波變換對光照變化不敏感，對光照、姿態(tài)具有一定的魯棒性，因此考慮在SIFT特征點的基礎(chǔ)上加入具有尺度、旋轉(zhuǎn)不變性的Gabor特征點，以增加圖像特征點數(shù)量。

2)針對特征描述符維度過高的問題。考慮事故現(xiàn)場局部特征點的非線性特性，同時保持降維后原始特征點的空間鄰域關(guān)系，通過LLE算法對特征點進行降維處理，以降低算法的匹配時長。

3)針對特征點匹配成功率較低的問題。提出1種分區(qū)域的特征點匹配方法，即不同區(qū)域的特征點對應(yīng)適應(yīng)區(qū)域的判斷閾值，以提高特征點匹配的成功率。

2.1 Gabor不變特征提取

2.1.1 2D Gabor濾波

2D Gabor濾波通常表示為1個二維高斯函數(shù)與復(fù)正弦函數(shù)的乘積。如式(1)所示：

(1)

式中：g為結(jié)果函數(shù)；x，y分別為函數(shù)對應(yīng)X，Y方向上的值；σ為尺度系數(shù)；θ為Gabor濾波的方向；σx和σy分別為包絡(luò)函數(shù)X，Y方向上的標準差，決定濾波器作用區(qū)域的大小；j為正整數(shù)(j=1，2，3，…)；W為復(fù)正弦函數(shù)在橫軸上的頻率。

2.1.2 特征提取流程

改進的高斯金字塔結(jié)構(gòu)，如圖3所示。為達到尺度空間的連續(xù)性，每1組對應(yīng)6層尺寸相同但尺度系數(shù)不同的多個方向采樣圖像[1]，如式(2)所示：

圖3 改進的高斯金字塔結(jié)構(gòu)Fig.3 Improved Gaussian pyramid structure

k=log2min(M′,N′)-α

(2)

式中：k為高斯金字塔組數(shù)；M′和N′分別為原始圖像行數(shù)和列數(shù)；α為最頂層圖像的最小行列數(shù)的對數(shù)值。

為保持高斯差分金字塔的尺度空間，即保證尺度系數(shù)σ的連續(xù)性，第k組的第1層尺度系數(shù)σ(k,1)等于第k-1組的倒數(shù)第3層尺度系數(shù)σ(k-1,3)[1]，同1組相同方向不同層的圖像在本組第1層的基礎(chǔ)上進行Gabor平滑產(chǎn)生。采用降采樣過程，即第k組圖像尺寸為第k-1組圖像的1/4。尺度系數(shù)變化如式(3)所示：

(3)

式中：σ(k,l)為尺度變化函數(shù)；l為層索引序號；σ0為高斯模糊初始值，取1.6。[1]

參照SIFT算法提取特征點的思路，本文基于改進的高斯金字塔和多方向多尺度Gabor頻譜特點提取Gabor不變特征流程如下：

1)構(gòu)建多尺度空間下的高斯金字塔，得到多尺度、多方向下的Gabor濾波圖像響應(yīng)值S(x,y,σk,θn)，其中尺度大小按照上述改進高斯金字塔中尺度分布進行變換。

2)考慮Gabor濾波的多方向性，對同一尺度下的不同方向的Gabor濾波乘以不同的權(quán)重系數(shù)αn，將n個方向上的濾波結(jié)果相加，近似得到該尺度σk下與高斯差分濾波相同的各向同性濾波結(jié)果，尺度空間與權(quán)重系數(shù)的計算如式(4)～(5)所示：

(4)

(5)

式中：S(x,y,σk)為尺度空間；n為方向數(shù)；αn為權(quán)重系數(shù)；S(x,y,σk,θn)為圖像響應(yīng)值；σk為不同組下的尺度系數(shù)；θn為濾波的方向；m為圖像中局部特征的個數(shù)；Q為某一局部特征下某一方向的重要度。

3)得到各個尺度下各個方向疊加的濾波結(jié)果，構(gòu)建高斯差分金字塔，通過擬合函數(shù)精確確定關(guān)鍵點的位置和尺度。

2.2 基于LLE的特征降維

LLE算法在降維的同時保持了圖像特征點的局部特征，假設(shè)特征點Wi=(x1,x2,…,xh)，h為高維空間維數(shù)，b為低維空間維數(shù)，具體的算法步驟如下：

1)確定特征點的K個近鄰點。基于歐氏距離將距離特征點最近的K個樣本規(guī)定為該特征點的K個近鄰點。

2)構(gòu)建權(quán)值系數(shù)矩陣ωij。對每個特征點Wi及其K個近鄰點集合Vi，構(gòu)建權(quán)值系數(shù)矩陣ωij，即協(xié)方差矩陣Zi=(xi-xj)T(xi-xj)，對降維誤差函數(shù)τ(ω)求最小值，即可求出權(quán)值系數(shù)矩陣，如式(6)所示：

(6)

3)輸出低維特征。通過特征值分解，求得b個特征值組成的向量矩陣，即輸出低維特征。

2.3 改進的特征點匹配方法

針對特征點匹配成功率較低的問題，提出1種分區(qū)域的特征點匹配方法，如圖4所示。

圖4 改進匹配算法流程Fig.4 Procedure of improved matching algorithm

首先，通過DBSCAN算法，即密度聚類確定特征點屬于圖像中哪一部分，具體步驟如下：

1)給定數(shù)據(jù)集D，包括圖像上所有特征點，初始時刻將所有特征點標記為未訪問狀態(tài)；

2)隨機選取1個未訪問的特征點P，將其標記為訪問狀態(tài)，檢查點P的ε鄰域是否至少包含M個對象。如果不包含，則P被標記為噪聲點。否則為P創(chuàng)建1個新的簇C，并將鄰域內(nèi)所有對象放入候選集N中；

3)通過迭代將N中不屬于其他簇的對象放入C中，同時N中的處于未訪問狀態(tài)下的對象P1被標記為訪問狀態(tài)，并檢查P1的ε鄰域，如果P1的鄰域至少包含M個對象，則將P1領(lǐng)域內(nèi)的對象都添加到C中，直到N為空；

4)從剩下的對象中隨機選擇1個未訪問過的對象，重復(fù)2)和3)，直到所有對象都被訪問。

考慮圖像上的碰撞車輛與其他物體區(qū)域，由于特征點數(shù)量有限，通過迭代判斷距離di/di+1是否小于閾值ε1(實驗發(fā)現(xiàn)ε1=0.85ε時匹配效果最好)。

對于圖像上的車道線、斑馬線區(qū)域，考慮分布的均勻性，通過計算區(qū)域內(nèi)的距離梯度下降一致性程度，設(shè)置閾值集合來判斷該梯度變化趨勢是否滿足要求，以斑馬線區(qū)域為例，具體的步驟如下：

3)通過設(shè)置閾值ξ{ξ1,ξ2,…,ξF}將距離分布的特征點劃分不同的區(qū)域，利用蟻群算法確定各個閾值的大小，斑馬線區(qū)域特征距離區(qū)域劃分，如圖5所示；

圖5 斑馬線區(qū)域特征距離區(qū)域劃分Fig.5 Region division on feature distance of zebra crossing area

上述步驟中，基于蟻群算法的閾值ξ{ξ1,ξ2,…,ξF}確定，假設(shè)距離由小到大取前15個點，將特征點的距離梯度值轉(zhuǎn)換為蟻群算法的路徑，如圖6所示(圖中特征點序號為隨機分布，各個路徑上數(shù)字表示路徑起點和終點)，具體步驟如下：

圖6 基于蟻群算法的區(qū)域閾值確定Fig.6 Determination of region threshold based on ant colony algorithm

1)選取待匹配的特征點1′和對應(yīng)的前15組數(shù)據(jù)，假設(shè)Lxi(1≤i≤15)表示數(shù)據(jù)的集合，且集合中元素隨機分布，b表示集合的數(shù)量(b=F+1，圖中b=3)，Tj(Lxi)表示集合Lxi(1≤i≤15)中第j個元素的信息量，螞蟻的數(shù)量為Z。開始搜索時，不同的螞蟻選擇的的路徑是隨機的；

3 實驗結(jié)果與分析

考慮事故現(xiàn)場圖像信息主要包括車輛信息、斑馬線、車道線等，且SIFT特征描述符由16個8維方向向量組成，本文采用的Gabor濾波組包括8個方向，根據(jù)輸入圖像的尺寸，濾波器組包括4個尺度，LLE降維后的特征描述符為36維特征向量，采用匹配點對的均方根誤差(RMSE)對算法進行評價。

3.1 Gabor特征點尺度、旋轉(zhuǎn)測試

選擇無人機航拍得到的某道路交通事故現(xiàn)場圖像，通過旋轉(zhuǎn)不同角度、進行不同尺度下的平滑對圖像進行匹配。旋轉(zhuǎn)角度、尺度變化下同一圖像特征點數(shù)量、匹配的具體變化情況見表1。考慮Gabor濾波方向、圖像局部特征方向以及旋轉(zhuǎn)角度。旋轉(zhuǎn)角度為22.5°，135°，157.5°時旋轉(zhuǎn)圖像上特征點數(shù)量較多，且匹配成功率較高，這是因為Gabor濾波設(shè)計為8個方向，即22.5的倍數(shù)，越接近濾波器方向特征點提取匹配效果越好；旋轉(zhuǎn)角度為129°時提取匹配效果較22.5°時好，這是因為圖像局部特征，如斑馬線、車道線方向與旋轉(zhuǎn)方向相接近；隨著尺度系數(shù)的增加，旋轉(zhuǎn)圖像提取的特征點數(shù)量減少，但特征匹配成功率幾乎不變；同時考慮旋轉(zhuǎn)與尺度的變化時，特征點的提取匹配效果與上述單獨變化結(jié)果相吻合。上述分析證明本文提出的方法的有效性，即提取的Gabor特征點具有尺度、旋轉(zhuǎn)不變性。

表1 圖像特征點變化情況Table 1 Change of feature points in image

3.2 算法測試檢驗

為檢驗本文提出的算法的有效性，通過無人機航拍得到的多張具有相同局部特征的某道路交通事故現(xiàn)場圖像進行測試。2種算法匹配示意圖，如圖7所示，其中圖7(a)為改進的SIFT算法，圖7(b)為經(jīng)典SIFT算法，特征點主要集中在4個區(qū)域，即碰撞車輛、摩托車、斑馬線、車道線，對應(yīng)序號1，2，3，4，空心圓圈表示圖像中提取的特征點，實心點表示匹配成功的特征點。

圖7 2種SIFT算法比較Fig.7 Comparison on two kinds of SIFT algorithm

2種算法的比較結(jié)果見表2，其中特征點的數(shù)量取待匹配圖像中較小的值。相較于經(jīng)典SIFT算法，改進的SIFT算法提取出的特征點在斑馬線、車道線等紋理局部特征處較多，在碰撞車輛以及摩托車，即1和3區(qū)域中2種算法提取的特征點數(shù)量相接近，這是因為Gabor濾波對圖像的紋理特征較為敏感；改進的SIFT算法在各個區(qū)域匹配成功的特征點數(shù)量更多，匹配成功率達到75.56%，匹配錯誤率為11.47%，均方根誤差為0.226，經(jīng)典SIFT算法匹配成功率為40.42%，匹配錯誤率34.02%，均方根誤差為0.513。

表2 改進的SIFT算法與經(jīng)典SIFT算法比較Table 2 Comparison of improved SIFT algorithm and classical SIFT algorithm

改進的SIFT算法、經(jīng)典SIFT算法、SURF算法、文獻[6]算法在匹配成功率、RMSE、特征點提取時間、特征點匹配時間上的比較結(jié)果見表3。相較于其他3種算法，本文提出的改進算法特征點匹配成功率最高，均方根誤差最小，但是，在特征點的提取時間上，由于本文加入了Gabor特征，提取時間相較于其他算法較長，但描述符的匹配時間卻大大縮短，是經(jīng)典SIFT算法的1/5，文獻[6]算法的1/2，在總的時間消耗上本文提出的改進算法更具有優(yōu)勢。

表3 4種算法對比結(jié)果Table 3 Comparison results of four algorithms

通過以上實驗分析，對714張事故現(xiàn)場圖像進行匹配，重復(fù)上述過程，其中684張圖像在匹配效果與上述實驗結(jié)果一致，算法的適用性達到95.80%，證明本文提出的算法的有效性。

4 結(jié)論

1)圖像旋轉(zhuǎn)角度與Gabor濾波方向越接近，圖像局部特征的方向與旋轉(zhuǎn)角度得到的有效特征點越多，匹配成功率越高；圖像局部特征的方向與旋轉(zhuǎn)角度越接近，得到的有效特征點越多，匹配成功率越高。因此對濾波器進行方向設(shè)置時，應(yīng)綜合考慮Gabor濾波方向、圖像局部特征方向以及旋轉(zhuǎn)角度3個因素。

2)特征點匹配過程中，由于Gabor濾波對圖像的紋理特征較為敏感，因此在斑馬線、車道線處匹配效果明顯增強。改進的SIFT算法無論是在匹配精度還是在匹配效率上都優(yōu)于同類算法，證明本文提出的算法的有效性。

3)改進的算法由于加入了Gabor特征，在特征點提取時間上還有待改進，下一步將在此研究基礎(chǔ)上，降低提取時間。