駱 磊，馬榮貴，馬 園

(長安大學 信息工程學院，陜西 西安 710064)

0 引 言

三維光學掃描技術能快速獲取復雜曲面的點云模型[1-2]，應用廣泛。目前車輛輪廓檢測主要使用激光掃描技術[3]，其過程為車輛低速通過龍門架，由安裝在龍門架兩端的測距雷達掃描車輛，獲取三維點云數(shù)據(jù)。由于兩端測距雷達水平方向距離車輛較近，并且高度較高，導致激光對車窗掃描時的入射角過大，測量點嚴重偏離反射面，在車窗處產(chǎn)生特殊噪聲點。文中針對這類特殊噪聲點，提出車窗三維點云數(shù)據(jù)修復算法。

對車窗處的點云數(shù)據(jù)重建有兩方面工作，一是去除特殊噪聲點，二是點云孔洞修復。在去除特殊噪聲點方面，因為這種數(shù)據(jù)的獲取方式現(xiàn)階段只用來獲取車輛的長寬高數(shù)據(jù)，而特殊噪聲點向車體內(nèi)側(cè)凹陷，不影響數(shù)據(jù)的檢測，所以普遍做法是對特殊噪聲點不做處理。因特殊噪聲點與正常點有著相似的性質(zhì)，文中使用點云分割方式去除噪聲點，文獻[4]中使用譜聚類方法將點云模型過分割，對點云數(shù)據(jù)有很好的分割效果，但是存在構(gòu)造相似度矩陣和確定尺度參數(shù)σ等問題，不能很好地適應于文中的車輛三維點云數(shù)據(jù)。文獻[5]中采用主成分分析法和局部二次曲面擬合法對點云模型進行微分幾何信息估算，并利用雙閾值檢測方法對散亂點云的特征信息進行提取，該算法可以將特殊噪聲點分割出來，但是需要確定閾值。文中提出使用聚類算法確定閾值，并用擬合方式分割特殊噪聲點。在點云空洞修復方面，已有很多算法[6-12]，文獻[11]中提出一種基于八鄰域深度差的算法提取點云孔洞邊界，但點云數(shù)據(jù)的獲取方式會導致車輛的三維點云數(shù)據(jù)上下疏密程度不同，不能有效提取出車窗邊界。文獻[12]中提出了一種基于SFM的三維點云孔洞修補算法，可以準確地恢復復雜曲面形狀，但是需要較高精度的SFM數(shù)據(jù)集。文獻[13]中提出了一種基于徑向基函數(shù)的孔洞修補算法，該算法對復雜曲面有很好的修補效果。文中對八鄰域深度差算法進行改進，提取邊界，用徑向基函數(shù)重建車窗數(shù)據(jù)。

綜上所述，文中根據(jù)文獻[4-5]提出結(jié)合聚類算法和曲面擬合的方法去除特殊噪聲點，根據(jù)文獻[11]提出改進的八鄰域深度差方法提取車窗邊界，根據(jù)文獻[12-13]使用基于徑向基函數(shù)的方式對車窗進行數(shù)據(jù)修復。主要創(chuàng)新部分在于結(jié)合了聚類算法和曲面擬合的方法去除特殊噪聲點，并改進了八鄰域深度差方法提取車窗邊界。具體流程如圖1所示。

圖1 車窗點云數(shù)據(jù)修復流程

1 相關數(shù)據(jù)說明

文中采用在龍門架裝載測距雷達的方式，對通過的車輛進行掃描，獲得點云數(shù)據(jù)。雷達測距數(shù)據(jù)經(jīng)過初步提取，去噪，獲得車輛點云數(shù)據(jù)，記點云數(shù)據(jù)集合為P，其中x軸方向為車輛寬度方向，車輛的最右端為0，最左端為最大值；y軸方向為車輛長度方向，車輛的最前端為0，最后端為最大值；z軸方向為車輛高度方向，車輛的最低點為0，最頂點為最大值；坐標系原點為車輛的右前底點，其中所有數(shù)據(jù)的單位均為cm。這里以圖2所示的面包車為例，可以看出車窗處有許多噪聲點，緊鄰著車窗分布，另外點云數(shù)據(jù)由上到下，成密度由稠密逐漸變稀疏：

圖2 汽車三維點云圖

2 車窗數(shù)據(jù)修復

2.1 計算數(shù)據(jù)點法矢

車輛的點云數(shù)據(jù)信息量較小，只有三維坐標信息，為后續(xù)對點云數(shù)據(jù)進行處理，豐富點云數(shù)據(jù)的信息，對數(shù)據(jù)點進行法矢計算，這里用PCA(principal component analysis)算法[9-13]計算數(shù)據(jù)點的法矢。

PCA即主成分分析法，用來計算點云數(shù)據(jù)的法矢。對于道路的點云數(shù)據(jù)集合P，由于它是無序的，所以在對集合P進行處理之前，需要為其建立拓撲關系，文中使用k-d樹(k-dimensional樹的簡稱)[14-16]數(shù)據(jù)結(jié)構(gòu)建立點云之間的拓撲關系。之后用PCA計算法矢，計算方式如下：

設集合P中的點pi的k鄰域點集為Nk(pi)，構(gòu)造關于點pi的3×3協(xié)方差矩陣，如式(1)所示：

(1)

其中，p為數(shù)據(jù)點pi及其k鄰域所構(gòu)成集合的質(zhì)心，矩陣C表示點集Nk(pi)的點的分布情況，即鄰域點與質(zhì)心點p的偏離程度。矩陣C為對稱半正定矩陣，所以有3個非負實數(shù)特征值，設為λ0,λ1,λ2，且λ0≤λ1≤λ2，其對應的特征向量分別為v0，v1，v2。最小特征值λ0對應的特征向量v0即可近似為點pi的法矢ni。

2.2 去除特殊噪聲點

對含有特殊噪聲點的車窗單獨進行處理，為更加清晰地說明特殊噪聲點，這里將車輛側(cè)面與特殊噪聲點分割出來，如圖3(a)所示，其橫坐標為車輛三維數(shù)據(jù)的y軸，其縱坐標為車輛三維數(shù)據(jù)的z軸，通過側(cè)視圖可以看到車窗下方的點云密度較大，是因為本應在車窗處的點由于光學原因，投射到車窗下方。通過車側(cè)面的正視圖如圖3(b)所示，灰圈中的點云數(shù)據(jù)即為特殊噪聲點，這類噪聲點很多，而且連續(xù)，如果不去除非常影響車輛三維重建，具體的噪聲點形式可以通過車輛點云數(shù)據(jù)的一個斷面進行展示，結(jié)果如圖3(c)所示，兩個灰圈中的點則為前面敘述中的特殊噪聲點，呈現(xiàn)向內(nèi)側(cè)下方凹陷的形狀，其距離車輛側(cè)面間隔一小段距離，文中利用這一點，使用聚類提取，擬合曲面的方法，將車輛側(cè)面與特殊噪聲點分割開來。

圖3 車窗處噪聲點說明圖

通常情況下，大貨車、鉤車以及半掛等大型車輛，不像小車整體都有車窗，而是僅車頭部分有車窗，所以在進行數(shù)據(jù)處理的時候，像小車這樣前中后都有車窗的車輛，對其整體進行處理，而特殊大型車輛僅處理車頭部分。聚類算法可以很好地將擁有同一類特性的點進行提取，經(jīng)過分析，車輛側(cè)面擁有相近的x值和相近的法矢，利用x值和法矢即可聚類提取車輛側(cè)面。進一步，對于車輛側(cè)面，如圖3(b)所示，為中間向外微凸的拱形，因為斜向上的法矢和斜向下的法矢之間的差異會比較大，所以僅僅使用法矢不能將整個側(cè)面提取[17-21]，但是這類差異又不是希望考慮的，又因為車輛側(cè)面與其他面相比法矢的x方向差異最為明顯，所以僅用法矢的x方向作為聚類時的數(shù)據(jù)即可。記車輛點云數(shù)據(jù)的x值為聚類數(shù)據(jù)集合的u值，法矢的x方向的值為聚類數(shù)據(jù)集合的v值，即集合Qcluster={(u,v)|u∈P,v∈n}。另外因為x信息與法矢的信息比例不同，所以要對x數(shù)據(jù)進行歸一化，將范圍限定在0到1，則u值的計算公式如式(2)所示：

(2)

其中，X為點云所有x方向數(shù)據(jù)的集合，x為集合X中的一個值。得到標準化的數(shù)據(jù)集合Qcluster后，使用多滑動窗口的均值漂移算法[22-24]確定中心點，其算法如下：

(1)在集合Qcluster中隨機選取n個點作為初始中心點C1,C2,…,Cn，其半徑為r的圓球作為滑動窗口。

(3)計算密度變化量與新密度的比值，如果小于額定值則認為沒有變化，執(zhí)行步驟4，否則再執(zhí)行步驟2。

(4)將所有的窗口作比較，選擇出密度最大的不重疊窗口，將其中心點作為結(jié)果。

因為對數(shù)據(jù)進行了歸一化，所以滑動窗口的半徑可以確定下來，半徑r的取值越大則對車輛側(cè)面數(shù)據(jù)的要求越寬泛，越小則越嚴格。文中r依據(jù)數(shù)據(jù)點的分布密度來確定，即數(shù)據(jù)點到距離其最近的四個點的距離來確定r值，公式如式(3)所示：

(3)

其中，X為點云數(shù)據(jù)中所有x值的集合，Di為數(shù)據(jù)點pi的最近鄰4個點距離的集合。

對中心點數(shù)量的選取，過小則有可能無法確定到真正的高密度中心，過大則影響計算速度。通常情況下n取6到10就可以將密度最大的中心點確定下來，這里為了使結(jié)果準確穩(wěn)定，取n=10。通過確定的聚類中心，可以得到車輛側(cè)面的數(shù)據(jù)范圍，其中Umax表示車輛側(cè)面數(shù)據(jù)的x值上限，Umin表示車輛側(cè)面數(shù)據(jù)的x值下限，Vmax表示道路數(shù)據(jù)法矢的x值上限，Vmin表示道路數(shù)據(jù)法矢的x值下限，計算公式如式(4)所示：

其中，r即為式(4)中確定的聚類窗口半徑，利用上述約束條件，對車輛點云數(shù)據(jù)進行約束，提取出車輛側(cè)面的數(shù)據(jù)信息。

但是通過聚類算法提取出的只是部分車輛側(cè)面數(shù)據(jù)，仍有一些點受噪聲干擾，其法矢的方向并不同于大部分點，所以不會被聚類算法提取，這里使用曲面擬合的方式，對現(xiàn)有的準確的車輛側(cè)面點云數(shù)據(jù)進行數(shù)據(jù)擬合。曲面擬合[25-27]既可以將車輛側(cè)面全部提取出來，也可以避免一些噪聲點的干擾。根據(jù)實際觀察，所有車輛側(cè)面在豎直方向都有一定的彎曲，而水平方向基本較小，所以，這里做擬合函數(shù)x=f(y,z)，其中y、z均為2次擬合，此時R-square=0.873 7，擬合效果符合要求，如果再向上增加擬合次數(shù)，不僅R-square增長較小，而且有可能會出現(xiàn)過擬合情況，所以選用x與y均為2次的曲面擬合。為確認曲面擬合的效果，對多種車輛側(cè)面進行曲面擬合，其擬合結(jié)果如表1所示。

表1 車輛側(cè)面擬合效果對比

使用曲面擬合的方式對車窗進行修復，為驗證曲面擬合的可行性，擬合的效果用R-square和RMSE作為判斷標準，則四種車輛側(cè)面的擬合效果如表1所示。從表1可以看出，四種車輛左右側(cè)面擬合的R-square均大于0.8，而左右側(cè)面擬合的RMSE均小于20 mm，說明使用的擬合函數(shù)可以很好地對車輛側(cè)面進行擬合，且誤差較小。

圖4 車窗處噪聲點說明圖

利用擬合出的曲面，對車輛點云數(shù)據(jù)進行處理，同樣以面包車為例，得到如圖4所示的車輛側(cè)面。如圖4(a)所示，灰色的點為噪聲點，黑色的點為車輛側(cè)面的點，利用曲面擬合的方式，不僅能夠把車窗處的噪聲點去除，而且能夠把在提取車輛數(shù)據(jù)時，摻入的地面點去除，去除效果如圖4(b)所示，可以看出，車輛側(cè)面效果很好，車窗處特殊噪聲點都已經(jīng)去除了。

2.3 提取車窗邊界

8鄰域深度差的方式在提取車窗邊界時存在兩個問題，因為車輛的點云數(shù)據(jù)由左右兩側(cè)龍門架上的測距雷達掃描獲取，所以點云數(shù)據(jù)由上到下的疏密程度是不一樣的，簡單地使用8鄰域深度差的話，會將密度稀疏的點云數(shù)據(jù)作為孔洞邊界提取，所以這里需要將8鄰域深度差算法進行改進。

改進的八鄰域深度差算法首先對點云沿深度方向進行垂直投影，即對三維點云數(shù)據(jù)的yoz平面投影，對投影點進行柵格數(shù)據(jù)組織，統(tǒng)計投影點坐標的最大最小值ymin,ymax,zmin,zmax，根據(jù)柵格的劃分次數(shù)m，計算每個柵格的大小為a*b，其中a，b的計算公式如式(5)、式(6)所示：

(5)

(6)

將各投影點分配到各個柵格并且對其進行編號:首先利用當前投影點的坐標(y,z)和柵格的大小a、b計算該點所在柵格的行r和列c，記該點所在柵格的編號為G(r,c)，其中r,c的計算公式如式(7)、式(8)所示:

(7)

(8)

對于任意柵格G(i,j)，統(tǒng)計柵格內(nèi)投影點的數(shù)目，若投影點數(shù)目為零，則將該柵格的深度值設定為h=0;若柵格內(nèi)投影點數(shù)目大于0，則將該柵格的深度設定為h=1。對于任意深度值不為0的柵格G(i,j)，計算其8鄰域的深度值與其延伸方向的深度值的和s，如果存在結(jié)果s為0，則說明該柵格為邊緣柵格，反之則不是。其中s的計算公式如式(9)所示：

s=h(i+c1,j+c2)+h(i+2c1,j+2c2),c1,c2∈{-1,0,1}

(9)

其中，h(i,j)表示柵格G(i,j)的深度值。

2.4 基于徑向基函數(shù)的孔洞修復

文中利用孔洞邊界點和它的鄰域信息，建立基于徑向基函數(shù)的隱式曲面，空間點云集合Q={q1,q2,…,qn}，分別對應約束值為{h1,h2,…,hn}，如果能構(gòu)造函數(shù)f(r)使得每個點均滿足等式F(qi)=hi，那么方程F(qi)=0就可以表示一個隱式曲面。該隱式曲面要求通過的點稱為插值約束點，而不要求通過的點稱為附件約束點，這里以車窗邊界點及車窗邊界點的5個鄰域車窗點作為插值約束點，記為Q={q1,q2,…,qn}，在插值約束點處沿插值約束點的法矢方向0.3長度處，計算附加約束點Q={qn+1,qn+2,…,q2n}，則表達式如式(10)、式(11)所示：

F(qi)=hi=0,i=1,2,…,n

(10)

F(qi)=hi(i=n+1,n+2,…,2n)(取hi=1)

(11)

結(jié)合式(10)、式(11)構(gòu)建基于徑向基函數(shù)的隱式曲面：

(12)

其中，qj表示建立曲面所需的采樣點，r表示建立曲面時通過的任意散亂點，ωi為對應每個采樣點的權(quán)值，P(r)表示P(r)=p0+p1x+p2y+p3z,φ(r-qi)的徑向基函數(shù)，一般情況下，在對空間散亂點進行插值時經(jīng)常用的基函數(shù)形式φ(r)=|r|3。對于三維空間中的任意兩個散亂點，表達式如式(13)所示：

φ(qi-qj)=|qi-qj|3=((qix-qjx)2+(qiy-qjy)2+(qiz-qjz)2)3/2

(13)

為求解權(quán)值和一階多項式的系數(shù)值，除有兩類約束點所給定的約束值條件，還需要滿足正交條件：

(14)

由此建立線性方程組AX=B。因為稀疏矩陣A是插值約束點和附加約束點的插值條件決定的半正定矩陣，所以該方程有唯一解，X是要求的權(quán)值ωi和一階多項式的稀疏矩陣(p0,p1,p2,p3)，B是約束值為hj的列向量，通過高斯消元法可以求出方程的解。

聯(lián)立式(12)～式(14)，采用高斯消元法解方程組，求解出插值約束點的權(quán)值和一階多項式的系數(shù)，從而到曲面的隱式方程。

(z-qjz)2)3/2+p0+p1x+p2y+p3z

(15)

之后采用梯度下降法對車窗點云數(shù)據(jù)進行填充，梯度下降法的一半形式為：

R1=R0-γ·F

(16)

3 實驗結(jié)果分析

對四種車輛車窗重建的效果如圖5所示，其中灰色部分為重建后車窗的數(shù)據(jù)點，黑色部分為車輛的數(shù)據(jù)點，所在坐標系的單位均為mm。圖5(a)為面包車，一個側(cè)面有三個車窗分別為前中后，這里以前車窗為例進行放大，通過放大圖可以看到，車窗處已經(jīng)沒有特殊噪聲點，且修復效果較好，車窗整體沒有空白處，達到車窗重建的目的；圖5(b)為半掛，可以看到修復效果較好，只是右上角有小塊缺損，因為缺損處有兩個點被提取為車窗邊界點，所以會以此為邊界，而將兩個點上面的部分作為車輛點云數(shù)據(jù)不做處理；圖5(c)為小型鉤車，對于比較方正的車窗，車窗的修復效果很好；圖5(d)為大貨車，有兩個車窗，兩個車窗之間的部分和前方車窗部分，其點云數(shù)據(jù)部分缺損，但仍不影響車窗數(shù)據(jù)的重建且修復效果較好。

圖5 四種車輛車窗修復結(jié)果

4 結(jié)束語

通過上述實驗結(jié)果，可以得到結(jié)論：聚類算法結(jié)合曲面擬合的方法可以很好地去除車窗處由于光學原因產(chǎn)生的特殊噪聲點，改進的8鄰域算法能夠?qū)吔缣崛∮幸欢ǖ目垢蓴_能力，基于徑向基函數(shù)的孔洞修補算法可以很好地重建車窗數(shù)據(jù)。綜上所述，該算法可以對不同類型車輛的車窗進行數(shù)據(jù)重建，且效果良好。但仍有可以改進之處，比如為提高精度，可以先提取出車窗邊框，以車窗周圍點作為擬合點，進行曲面擬合去除噪聲點，理論上可以提高擬合精度，需要后續(xù)進行實驗驗證。