基于DBSCAN聚類算法的圖像消失點(diǎn)計(jì)算方法

袁 鵬，陳國良

(武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070)

基于道路交通視頻場(chǎng)景的攝像機(jī)自動(dòng)標(biāo)定方法中最常見的就是基于消失點(diǎn)的標(biāo)定方法，該方法利用圖像中的消失點(diǎn)信息進(jìn)行相機(jī)模型的參數(shù)計(jì)算以及標(biāo)定。1990年，Caprile和Torre首先提出利用消失點(diǎn)進(jìn)行攝像機(jī)標(biāo)定[1]。

道路環(huán)境下，背景信息復(fù)雜，可靠的檢測(cè)消失點(diǎn)成為相關(guān)研究的重要目標(biāo)。Lv[2]等提出利用視頻中行人頭部、腳部定位點(diǎn)連線作為垂直于地面的直線，據(jù)此進(jìn)行消失點(diǎn)的估計(jì)，完成攝像機(jī)自標(biāo)定。然而，交通視頻場(chǎng)景下行人特征并不穩(wěn)定。文獻(xiàn)[3]通過道路線路或者車道線來獲取消失點(diǎn)。 陳珂[4]通過車道線與垂直于道路的路燈來進(jìn)行特定場(chǎng)景下的標(biāo)定，并應(yīng)用于車速檢測(cè)。這些方法需要獲得清晰的車道線或者其他標(biāo)志物，對(duì)于結(jié)構(gòu)化道路比較適用。在非結(jié)構(gòu)化道路或者不能檢測(cè)出清晰標(biāo)志物的場(chǎng)景，這些方法將不再適用。

文獻(xiàn)[5]假設(shè)車輛在一定程度上是沿直線行駛的，通過跟蹤車輛軌跡以及建立邊緣背景模型檢測(cè)車輛邊緣方向的直線來進(jìn)行消失點(diǎn)的獲取,分別獲得指向?qū)?yīng)消失點(diǎn)的直線信息。

為了在一定程度上消除虛假消失點(diǎn)的干擾，王偉等[6]利用道路場(chǎng)景中冗余信息構(gòu)造非線性約束條件，對(duì)標(biāo)定參數(shù)進(jìn)行迭代求最優(yōu)，減少標(biāo)定誤差。Wang[7]等通過均值漂移聚類(mean shift clustering)算法結(jié)合拉普拉斯線性算法回歸對(duì)消失點(diǎn)進(jìn)行處理，但是均值漂移聚類算法無法排除大量噪聲點(diǎn)。文獻(xiàn)[5]對(duì)得到的指向消失點(diǎn)的直線數(shù)據(jù)通過基于平行坐標(biāo)系(PClines)的級(jí)聯(lián)霍夫變換(cascaded hough transform, CHT)將實(shí)投影平面上的點(diǎn)轉(zhuǎn)化為鉆石空間(diamond space)上的點(diǎn)，再進(jìn)行投票獲得兩個(gè)正交消失點(diǎn)。投票方法只選取了票數(shù)最高的點(diǎn)作為消失點(diǎn)，這在難以檢測(cè)車輛直線特征的道路場(chǎng)景下可能存在較大誤差。

筆者針對(duì)文獻(xiàn)[5]在車輛較少的場(chǎng)景中表現(xiàn)不佳，提出改進(jìn)的DBSCAN密度聚類算法(density-based spatial clustering of applications with noise， DBSCAN)[8]，通過對(duì)消失點(diǎn)進(jìn)行聚類，找到較準(zhǔn)確的消失點(diǎn)。并針對(duì)DBSCAN密度聚類算法難以處理消失點(diǎn)數(shù)據(jù)不均勻的問題，提出鄰域距離閾值自適應(yīng)降低算法，并通過實(shí)驗(yàn)證明相關(guān)算法的可行性。

1 消失點(diǎn)的描述

消失點(diǎn)是世界坐標(biāo)系中相互平行的直線經(jīng)過投影變換之后在圖像坐標(biāo)系中的交點(diǎn)。

圖1中ABCD為矩形，經(jīng)過投影變換到圖像坐標(biāo)系中，得到A′B′C′D′,現(xiàn)實(shí)中的平行線AB，CD與AD，BC分別在圖像坐標(biāo)系中相交于VP2和VP1。VP1與VP2即為消失點(diǎn)。在AB，CD與AD，BC相互垂直的情況下，VP1與VP2為一對(duì)正交消失點(diǎn)。

圖1 消失點(diǎn)示意圖

道路場(chǎng)景下，最常見的一對(duì)正交消失點(diǎn)為沿道路方向消失點(diǎn)以及道路平面內(nèi)垂直于道路的消失點(diǎn)，分別表示為VP1，VP2。VP1通常為道路車道或分道線的交點(diǎn)，VP2常利用車輛邊緣求得。

垂直于道路的消失點(diǎn)VP3將由消失點(diǎn)的性質(zhì)計(jì)算得出。Caprile和Torre證明消失點(diǎn)具有3個(gè)性質(zhì)：

(1)平行于同一平面的直線與對(duì)應(yīng)的消失點(diǎn)都分布在同一條消失線上；

(2)攝像機(jī)的像主點(diǎn)位于以3個(gè)正交消失點(diǎn)為頂點(diǎn)所構(gòu)成的三角形的垂心上。

(3)若已知3個(gè)正交消失點(diǎn)中的一個(gè)消失點(diǎn)以及過該消失點(diǎn)的直線，即消失線，可以求得其他兩個(gè)正交消失點(diǎn)的坐標(biāo)。

由圖2可知，當(dāng)已知正交消失點(diǎn)VP1,VP2，以及主點(diǎn)坐標(biāo)P時(shí)，由性質(zhì)(2)可以計(jì)算VP3坐標(biāo)。具體過程如下：過主點(diǎn)P作VP1,VP2連接線l1的垂線l2，過VP1作主點(diǎn)P,VP2連接線l3的垂線l4，l2與l4的交點(diǎn)即為對(duì)應(yīng)的正交消失點(diǎn)VP3。

圖2 正交消失點(diǎn)與像主點(diǎn)示意圖

2 消失點(diǎn)計(jì)算

2.1 沿道路方向的消失點(diǎn)(VP1)

在道路場(chǎng)景下車道線的獲取并不穩(wěn)定，且在檢測(cè)到車道線的情況下僅通過車道線來獲取消失點(diǎn)缺乏魯棒性。車輛軌跡是交通視頻數(shù)據(jù)中比較容易獲得的特征信息，理想情況下，車輛軌跡集中的軌跡相互平行且指向沿道路消失點(diǎn)。對(duì)道路方向的消失點(diǎn)檢測(cè)步驟如下：

步驟1利用Shi-Tomasi角點(diǎn)檢測(cè)[9]方法檢測(cè)視頻幀中的角點(diǎn)。

步驟2利用Kanade-Lucas-Tomasi角點(diǎn)跟蹤算法進(jìn)行軌跡跟蹤，獲得軌跡集合。

步驟3利用基于平行坐標(biāo)系的級(jí)聯(lián)霍夫變換將直線轉(zhuǎn)換到鉆石空間投票即獲得消失點(diǎn)VP1。

由于車輛軌跡獲取的直線長(zhǎng)度比較長(zhǎng)，且大部分都能準(zhǔn)確指向消失點(diǎn)，故消失點(diǎn)VP1可以直接利用基于平行坐標(biāo)系的霍夫變換投票求取。為避免車輛變道等對(duì)軌跡線方向的干擾，對(duì)多輛車進(jìn)行角點(diǎn)檢測(cè)與跟蹤，獲取較多軌跡樣本。

2.2 道路平面內(nèi)垂直于道路的消失點(diǎn)(VP2)

VP2方向上的直線一般采取對(duì)車輛邊緣進(jìn)行直線檢測(cè)的方式。邊緣和直線檢測(cè)的精度，用于投票選出VP2的直線方向等多種因素都會(huì)對(duì)VP2精度產(chǎn)生影響。視頻中車輛較少或難以檢測(cè)車輛邊緣時(shí)，直接對(duì)候選直線進(jìn)行鉆石空間投票會(huì)出現(xiàn)較大誤差。選擇不對(duì)候選直線進(jìn)行投票選擇最大值作為VP2，而是采用直線交叉求解交點(diǎn)，獲得消失點(diǎn)候選點(diǎn)集之后再做處理，減小偶然誤差的影響。步驟如下：

步驟1利用混合高斯背景建模法(gaussian mixture background modeling, GMM)，結(jié)合陰影檢測(cè)算法HSV(hue,saturation,value)去除陰影部分，獲得車輛前景掩膜mask，經(jīng)過形態(tài)學(xué)處理與運(yùn)算等手段，得到車輛的真實(shí)前景Matfore。

步驟2對(duì)Matfore進(jìn)行Canny邊緣檢測(cè)，之后利用亞像素直線檢測(cè)算法LSD(line segment dector)進(jìn)行直線檢測(cè)。利用長(zhǎng)度，角度以及VP1等限制條件對(duì)直線進(jìn)行篩選。

步驟3對(duì)直線交叉求交點(diǎn)，得到消失點(diǎn)VP2的候選集合為ΩVP2。通過后續(xù)的算法對(duì)候選集合進(jìn)行求解以獲得較為精確的消失點(diǎn)VP2。

背景信息中含有大量各個(gè)方向的直線干擾，故直接對(duì)讀取的視頻幀進(jìn)行邊緣檢測(cè)將會(huì)出現(xiàn)大量干擾。通過背景建模算法，獲取原圖像中的前景輪廓，保留汽車上的邊緣信息，剔除背景干擾。設(shè)前景像素為M(x,y)，前景掩膜mask(x,y)利用二值化去除陰影區(qū)域，由式(1)計(jì)算車輛前景邊緣信息Mcar(x,y)。

(1)

考慮到混合高斯背景建模獲取的前景信息比較完整，能夠提高直線檢測(cè)的概率，且算法比較成熟，運(yùn)算速度快，能達(dá)到實(shí)時(shí)處理速度。故采用GMM算法，并結(jié)合HSV陰影檢測(cè)去除陰影。

對(duì)前景掩膜mask(x,y)進(jìn)行濾波、填充空洞等手段之后，前景區(qū)域更加完整。然后由式(1)得到保留有車輛邊緣信息的Mcar(x,y)。對(duì)Mcar(x,y)進(jìn)行邊緣檢測(cè)，即可得到前景邊緣信息，采用Canny算子進(jìn)行邊緣檢測(cè)。

對(duì)邊緣檢測(cè)圖像利用LSD亞像素直線檢測(cè)算法檢測(cè)直線，提高直線檢測(cè)精度。并通過方向、角度和長(zhǎng)度等條件調(diào)整檢測(cè)到的直線。

按照步驟3計(jì)算候選消失點(diǎn)并保存到VP2的候選集合ΩVP2中。

2.3 消失點(diǎn)精度改進(jìn)算法

為找到消失點(diǎn)數(shù)據(jù)分布密集區(qū)域，利用基于密度的聚類算法DBSCAN算法對(duì)消失點(diǎn)數(shù)據(jù)進(jìn)行處理，尋找高可靠度的消失點(diǎn)區(qū)域。DBSCAN算法用參數(shù)(,MinPts)來描述鄰域的樣本分布緊密程度。表示某一樣本的鄰域距離閾值，MinPts描述某一樣本的距離為的鄰域中樣本個(gè)數(shù)的閾值。該算法的主要思想為：對(duì)于一個(gè)未被聚類點(diǎn)，如果鄰域內(nèi)包含的樣本數(shù)不小于指定的MinPts，則該點(diǎn)為核心點(diǎn)。對(duì)鄰域內(nèi)的點(diǎn)不斷進(jìn)行上述過程，直到所有的點(diǎn)被遍歷到。

=k×

(2)

式中：k為減小的比例系數(shù)。

(3)

式中:loop為迭代次數(shù)。

對(duì)于上述迭代過程，由于DBSCAN數(shù)據(jù)的去噪特性，能夠在迭代過程中不斷篩選密度過低的噪聲區(qū)域。消失點(diǎn)數(shù)據(jù)存在大量數(shù)值較小的數(shù)據(jù)，且分布較密集，在鄰域距離閾值較大時(shí)，這類區(qū)域通常被劃分為一個(gè)聚類簇，包含最多的有效點(diǎn)，設(shè)此聚類簇為Dmax。因此在上述迭代過程中，可以通過控制Dmax含有的數(shù)據(jù)點(diǎn)占總數(shù)據(jù)點(diǎn)數(shù)的比例來控制迭代的次數(shù)。設(shè)該比例為λ，當(dāng)λ減小到一定范圍，既能夠排除一定的噪聲點(diǎn)，又可避免可能有效的聚類簇被判別為噪聲。λ定義如下：

(4)

式中:NDmax為最大聚類簇中包含的樣本數(shù)量；Ntotal為樣本總數(shù)量。

迭代結(jié)束后，排除一部分噪聲數(shù)據(jù)，得到處理后的ΩVP2。在實(shí)際計(jì)算中，消失點(diǎn)VP3的值通常比較大，因此利用VP3對(duì)ΩVP2再次進(jìn)行篩選。

對(duì)ΩVP2集合中的每個(gè)候選點(diǎn)以及VP1值利用消失點(diǎn)性質(zhì)(2)計(jì)算對(duì)應(yīng)的消失點(diǎn)VP3，保存集合為ΩVP3。

對(duì)ΩVP3進(jìn)行聚類，設(shè)ΩVP3中點(diǎn)屬于聚類簇的集合為Ωcluster，按照式(5)對(duì)VP2進(jìn)行篩選：

(5)

式中:PVP2為true代表計(jì)算得到該VP3點(diǎn)的對(duì)應(yīng)VP2值應(yīng)該納入最終的VP2候選集合中，否則不加入；yc為某點(diǎn)所屬聚類簇的質(zhì)心的縱坐標(biāo)，ymean為所有聚類簇的質(zhì)心的縱坐標(biāo)的均值。

后續(xù)對(duì)集合ΩVP2中的消失點(diǎn)分別再次進(jìn)行聚類，并得到每個(gè)聚類簇的質(zhì)心，對(duì)所有質(zhì)心取中位數(shù)作為消失點(diǎn)VP2。

3 實(shí)驗(yàn)結(jié)果及評(píng)估

利用文獻(xiàn)[10]提供的BrnoCompSpeed數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。BrnoCompSpeed數(shù)據(jù)集由布爾諾理工大學(xué)提供，包含交通監(jiān)控?cái)z像頭記錄的視頻和元數(shù)據(jù)。該數(shù)據(jù)集在高速公路環(huán)境下拍攝，通過記錄的元數(shù)據(jù)可以計(jì)算Ground Truth。BrnoCompSpeed數(shù)據(jù)集如圖3所示。

圖3 BrnoCompSpeed數(shù)據(jù)集

由2.1節(jié)獲取車輛軌跡之后，由鉆石空間投票獲取消失點(diǎn)VP1。

圖4為車輛軌跡經(jīng)鉆石空間投票方法所獲得的VP1與真實(shí)的VP1值?？芍摲椒ǖ臏?zhǔn)確率較高。在靜態(tài)背景條件下，由KLT(kanade lucas tomasis)跟蹤車輛軌跡的方法比較適用。但在光照變化明顯，背景抖動(dòng)等情況下，該方法將出現(xiàn)大量誤差，甚至無法正常工作。此時(shí)則需要其他方法來正確獲取車輛軌跡。

圖4 軌跡投票結(jié)果

由2.2求取VP2的值如圖5所示。

圖5 參數(shù)自調(diào)整時(shí)VP2候選點(diǎn)DBSCAN聚類圖

圖5為MinPts=3，λ=0.9時(shí)調(diào)整時(shí)部分聚類結(jié)果，Noise代表噪聲點(diǎn)，C#代表聚類簇，epsilon代表參數(shù)。實(shí)驗(yàn)證明，設(shè)置λ=0.8～0.9時(shí)算法的結(jié)果比較準(zhǔn)確，且結(jié)果變化相差較小，因此λ值可以在相對(duì)固定的情況下對(duì)VP2候選點(diǎn)進(jìn)行去躁。固定MinPts為3，在初始選取為較大值10 000時(shí)，經(jīng)過DBSCAN聚類參數(shù)多次自調(diào)整后，大約經(jīng)過20余次迭代即可排除大部分噪聲消失點(diǎn)。

將最后一次迭代之后的有效VP2候選消失點(diǎn)集，以及經(jīng)過投票之后的VP1，按照消失點(diǎn)性質(zhì)(2)計(jì)算VP3，得到VP3集合。最終，由式(5)篩選出對(duì)應(yīng)的VP2集合，去除噪點(diǎn)數(shù)據(jù)，得到各個(gè)聚類簇的質(zhì)心，VP2選取為所有質(zhì)心的中位數(shù)。

由于DBSCAN聚類算法在數(shù)據(jù)量較多時(shí)表現(xiàn)不佳，故在直線數(shù)據(jù)較多時(shí)，算法的運(yùn)行時(shí)間會(huì)大幅度增加。但在獲取直線特征數(shù)據(jù)較少時(shí)，算法能夠在較短時(shí)間內(nèi)檢測(cè)出消失點(diǎn)并計(jì)算參數(shù)，檢測(cè)的誤差也低于文獻(xiàn)[5]的方法。因?yàn)槲墨I(xiàn)[5]的方法直接票選最高得票點(diǎn)為消失點(diǎn)，在數(shù)據(jù)樣本較少時(shí)增大了誤差。而筆者提出的方法給予可能正確但票數(shù)較少的消失點(diǎn)參與最終計(jì)算過程的機(jī)會(huì)。在數(shù)據(jù)較多時(shí)，已有大多數(shù)準(zhǔn)確的直線特征參與計(jì)算，算法耗時(shí)大幅度增加，精確度下降。此時(shí)采用鉆石空間投票方式更為合適。

4 結(jié)論

基于消失點(diǎn)的相機(jī)標(biāo)定方案，針對(duì)某些道路交通視頻場(chǎng)景獲得用于檢測(cè)消失點(diǎn)的特征較少時(shí)，檢測(cè)消失點(diǎn)誤差較大的問題，提出結(jié)合基于平行坐標(biāo)系的級(jí)聯(lián)霍夫變換和DBSCAN密度聚類算法分別計(jì)算道路交通視頻中兩個(gè)正交消失點(diǎn)，并通過改進(jìn)DBSCAN聚類算法的預(yù)設(shè)參數(shù)，使其自動(dòng)調(diào)整到合適閾值范圍內(nèi)。這種方法能夠在道路環(huán)境下檢測(cè)到的直線特征較少時(shí)適用，當(dāng)直線數(shù)據(jù)豐富時(shí)，計(jì)算量及誤差都會(huì)增大，此時(shí)可采用投票等方法進(jìn)行檢測(cè)。