面向駕駛員注視區域劃分的DBSCAN-MMC方法

孫文財，楊志發，李世武，徐 藝，郭夢竹，魏學新

（吉林大學 交通學院，吉林 長春130022）

駕駛員注視區域劃分是研究駕駛員視覺轉移模式的基礎，合理有效地劃分駕駛員注視區域將有助于尋找駕駛員視覺規律，從而提高駕駛員狀態監測和駕駛行為預測的準確性.使用聚類方法進行駕駛員注視區域劃分可克服傳統注視區域劃分主觀性大的缺點，國內已有學者進行了相關研究并取得了成果：長安大學郭應時等［1-2］使用基于距離的聚類方法，通過改變聚類個數較為合理地完成了駕駛員注視區域的劃分.但駕駛員注視點分布有不規則、較離散的特點，而常規基于距離的聚類方法有僅對“類圓形”數據聚類效果較好、聚類邊界較生硬等缺陷.在聚類領域，基于密度和基于數學形態學聚類方法可進行不規則形狀數據的聚類，國內外學者已對典型密度聚 類 方 法（density based spatial clustering of applications with noise，DBSCAN）和形態學聚類方法進行了研究并取得了一些成果：Ester等［3］最早提出用于解決任意形狀數據聚類問題的DBSCAN算法；Ankerst等［4-9］采用不同方法在DBSCAN 參數選取和聚類精度方面取得了一定進展；Postaire等［10］最早提出數學形態學聚類，經Starovoitov等［11-14］發展優化.但是，DBSCAN 算法仍存在參數值Eps的選取對聚類結果影響較大、改進的DBSCAN 算法時間復雜度提高的問題；數學形態學聚類（mathematical morphology clustering，MMC）則尚存需大量人工干預、智能化程度不高的缺陷.

針對DBSCAN 和MMC存在的問題，為提高駕駛員注視區域劃分效果，本文對MMC 方法進行改進并與DBSCAN 結合使用，提出了面向駕駛員注視區域劃分的DBSCAN-MMC聚類方法.

1 DBSCAN 與MMC聚類方法

1.1 DBSCAN 聚類方法

Ester等［3］提出的DBSCAN 算法為基于密度的典型聚類方法，其中心思想為：若一個點簇可由其中的任何核心對象唯一確定，對于某一點簇中的對象，給定半徑rE的鄰域內數據對象個數必須大于給定值MP.可表述為

1）確定rE鄰域給定數據對象p 的rE鄰域NEps（p）定義為以p 為核心，以rE為半徑的d 維超球體區域，即

式中：D?Rd為d 維實空間上的數據集，dist（p，q）為D 中p 和q 之間的距離.

4）確定密度可達 給定數據集D，存在一個對象鏈pi（i＝1，2，…，n，p1＝q，pn＝p），對于pi∈D，若在條件pi＋1從pi直接密度可達，則稱對象p 從對象q 密度可達.

5）確定密度相連 如果數據集D 中存在一個對象o，使得對象p 和q 是從o 密度可達的，則稱對象p 和q 密度相連.

6）確定簇與噪聲 由任意一個核心點對象開始，從該對象密度可達的所有對象構成一個簇.不屬于任何簇的對象為噪聲.

1.2 MMC聚類方法

數學形態學聚類將用于圖像處理的方法引入聚類分析，其首先將矢量空間數據轉換為柵格，循環使用由小到大的結構元進行閉運算連接相鄰目標，經運算處于同一連通區域的目標劃歸為一類.基于圓形結構元的MMC聚類可表述為［10］

1）初始化圓半徑i＝1；

2）建立半徑為i的圓形結構元Bi；

3）閉運算Yi＝X·Bi；

式中：X 為待聚類數據，Y 為聚類結果（同一類中值相同，不同類值不同）

4）統計連通區域數即聚類數ni，若ni＞1，i＝i＋1，轉（2），否則繼續（5）；

5）根據ni計算最優聚類數nk得到對應的結構元半徑k.

MMC能夠得到與圖像處理相似的效果，即：消弭轉換為柵格的數據點的間隙，使平面距離接近的數據點生成連通區域，MMC 可以任意形狀融合擴展，可充分利用已有聚類區域的位置信息，生成任意形狀的聚類.

2 面向注視區域劃分的DBSCAN-MMC聚類方法

2.1 常規聚類方法存在問題

在使用常規聚類方法對駕駛員注視區域進行劃分的過程中，存在如下問題：

1）駕駛員存在分散注視點且注視點分布并不規則，而常規基于距離的聚類方法對異常點敏感，劃分非圓形區域時區域邊界生硬，無法達到注視區域劃分的目的；

2）單純使用DBSCAN 聚類方法，聚類效果受參數的影響較大，選取較小的rE會產生較多離群點，選取較小的rE會導致不同類的誤合并，且一旦確定rE，將無法對聚類產生的離群點進行進一步劃分；

3）常規MMC需人為確定最終聚類數目，自適應能力不佳，可用性差.

2.2 DBSCAN-MMC方法步驟

為解決上述問題，提出密度方法與數學形態學方法相結合的自適應DBSCAN-MMC方法.方法首先使用結構參數設置rE的取值，通過DBSCAN 得到MMC 聚類的初始點集并確定聚類數目；使用自適應的MMC聚類減少DBSCAN 聚類產生的離群點，并最終完成面向駕駛員注視區域的劃分.具體步驟如下.

1）設注視點在注視區域內均勻分布，則以每一注視點為圓心的圓直徑（如圖1 所示）即為DBSCAN 的鄰域搜索半徑，按式（1）求得rE，設置DBSCAN 鄰域最少對象數MP＝3.

根據鄰域搜索半徑，設置圓形結構元初始半徑rori＝rE／2，設置較小的半徑擴展步長和結構元半徑上限以降低相近區域的邊界劃分生硬的概率，即半徑擴展步長rst＝rE／10，結構元半徑上限rup＝5rE.

式中：l為注視區域長度，h為注視區域高度，cg為注視點數量.

圖1 搜索半徑示意圖Fig.1 Schematic diagram of search radius

2）對注視點數據Gori進行基于DBSCAN 的聚類，核心對象Gcon即為駕駛員注視集中的區域，劃歸類的數目k作為最終聚類數目；

3）以注視集中區Gcon為初始點GMMC進行圓形結構元半徑r＝rori的形態學膨脹，生成連通區所包含的初始注視點簇G1，記錄已被劃歸入連通區的注視點數量C1；

4）以第n-1次計算所得注視點簇Gn-1為第n 次MMC 的初始點，進行圓形結構元半徑為r 的形態學膨脹，將連通區中離群點劃歸為該區域，生成連通區注視點簇Gn，記錄已被劃歸入連通區的注視點數量Cn；

5）判斷第n次計算中是否有被劃歸入連通區的注視點，若Cn-Cn-1＞0，則n＝n＋1，r＝rori，轉3），若Cn-Cn-1＝0，且r＜rup，則r＝r＋rst，n＝n＋1，轉3），若Cn-Cn-1＝0，且r≥rup，繼續步驟6）；

6）將第n 次形態學聚類生成的每個連通區Ii（i＝1，2，…，k）中包含的點劃歸為對應點集，生成最終簇GTi（GTi＝Gn，i），將未被劃歸入聚類區域的點單獨歸為一簇，最終生成k＋1個簇，每一簇即為一個注視區域.

方法流程如圖2所示.

2.3 DBSCAN-MMC方法的優勢

圖2 DBSCAN-MMC聚類方法流程Fig.2 DBSCAN-MMC clustering method flow chart

使用基于劃分的聚類方法時，每次迭代的聚類中心確定后，距離相近的點完全按照與聚類中心的距離被硬性劃歸為不同點簇，導致K-means等基于距離的聚類方法只能發現“類圓形”，若對象點非圓形、聚類中心數目選取不合適即會出現劃分邊界生硬的現象.而DBSCAN-MMC結合基于密度和基于數學形態學的聚類優點，首先經DBSCAN 確定注視密集區，明確聚類中心數量和位置，再經MMC進行任意形狀的區域拓展，可完全規避上述基于劃分的聚類方法的缺陷.

3 實例驗證與結果分析

3.1 基于DBSCAN-MMC的注視區域劃分

分別采集熟練駕駛員進行直線、左轉、右轉3種駕駛行為時的眼動數據，每種駕駛行為采集時長為10s.剔除因系統誤差超出視野外的數據以及眨眼時刻（該時刻眼動儀無法捕捉瞳孔數據，因而注視方向數據誤差較大）的數據，共得到1 151 組有效數據.處理眼動儀向量形式數據得到駕駛員注視視線到其前方1m 處鉛直平面的投影，并以駕駛員正前方視線投影為原點建立坐標系，作為實例驗證的原始數據Gori.注視點對應車輛位置如圖3所示.

圖3 注視點的車輛位置圖Fig.3 Vehicle location of fixation points

使用上述數據進行基于DBSCAN-MMC 的駕駛員注視區域的劃分.

Step1 參數設置 注視區域長度l＝120.99…cm，高度h＝68.01cm，注視點數量cg＝1 151，由式（1）得DBSCAN 的搜索半徑rE＝2.67cm；

設置鄰域最少對象數MP＝3，圓形結構元初始半徑rori＝rE／2＝1.34cm，半徑擴展步長rst＝rE／10＝0.27cm，結構元半徑上限rup＝5rE＝13.37；

Step2 確定注視集中區 對注視點數據Gori進行基于DBSCAN 的聚類，劃歸類的數目k＝10，生成注視集中區Gcon.聚類所得注視點集中位置如圖4所示.圖中H 表示水平方向，0 點為駕駛人正視前方時的橫坐標位置；V 表示鉛直方向，0點為駕駛人正視前方時的縱坐標位置

Step3 初始形態學聚類 以注視集中區Gcon

為初始點GMMC進行圓形結構元半徑r＝1.34cm 的形態學膨脹，生成連通區所包含的初始注視點簇G1，記錄已被劃歸入連通區的注視點數量C1＝1 115.初始膨脹效果如圖5所示.

圖4 DBSCAN 聚類所得注視點集中位置Fig.4 Centralized location of fixation points clustered by DBSCAN

圖5 初始形態學膨脹效果Fig.5 Original effect of morphological dilation

Step4 形態學計算 以第n-1次計算所得注視點簇Gn-1為第n 次MMC 的初始點，進行圓形結構元半徑為r的形態學膨脹，將連通區中離群點劃歸為該區域，生成連通區注視點簇Gn，記錄已被劃歸入連通區的注視點數量Cn；

Step5 過程迭代 判斷第n 次計算中是否有被劃歸入連通區的注視點，若Cn-Cn-1＞0，則n＝n＋1，r＝1.34cm，轉3），若Cn-Cn-1＝0，且r＜13.37cm，則r＝r＋rst，n＝n＋1，轉3），若Cn-Cn-1＝0，且r≥13.37cm，繼續步驟5）；

Step6 迭代終止與結果輸出 當n＝4 時，達到迭代終止條件（C4＝1 134，C4-C3＝0，r＝13.37 cm），將第4次形態學聚類生成的每個連通區Ii（i＝1，2，…，10）中包含的點劃歸為對應點集，將未被劃歸入聚類區域的點單獨歸為一簇，完成11個注視區域的劃分.最終聚類結果如圖6所示.圖中每一種形狀的點所形成的區域即為駕駛員的一個注視區域.

由圖6可見，使用DBSCAN-MMC生成了注視點相對集中的10個注視區域以及注視點相對離散的1個注視區域，參照圖3可解釋所劃分區域的現實意義：

圖6 DBSCAN-MMC聚類效果Fig.6 Effect of DBSCAN-MMC clustering

區域1代表左后視鏡后方注視區域；區域2代表左后視鏡上方注視區域；區域3代表左后視鏡注視區域；區域4、5、8代表注視前方不同距離和不同車道處車輛生成的注視區域；區域6代表后視鏡上方（注視交通信號燈）的注視區域；區域7代表后視鏡處的注視區域；區域9代表右后視鏡上方注視區域；區域10代表右后視鏡注視區域；區域11代表儀表板等處的離散注視區域.

根據聚類結果，將駕駛人視野劃分為A 到I 的9個注視區域：A 為左后視鏡后方注視區域，對應聚類結果中的區域1；B 為左后視鏡上方注視區域，對應聚類結果中的區域2；C 為左后視鏡注視區域，對應聚類結果中的區域3；D 為注視前方不同距離和不同車道處車輛時的區域，對應聚類結果中的區域4、5、8；E 為后視鏡處的注視區域，對應聚類結果中的區域7；F 為后視鏡上方的注視區域，代表聚類結果中的區域6；G 為右后視鏡上方注視區域，對應聚類結果中的區域9；H 為右后視鏡注視區域，對應聚類結果中的區域10；I為儀表板等注視區域，對應聚類結果中的離散注視區域.

3.2 基于常規聚類的注視區域劃分

常規MMC方法中聚類數目、結構元半徑的確定和聚類的終止條件具有較大的主觀性，本文不做討論，下單純使用K-means 和取不同rE的DBSCAN 進行駕駛員注視區域的劃分以說明DBSCAN-MMC的聚類效果.

預設K-means聚類個數分別為k＝5、10、15；DBSCAN 方法的鄰域最小對象數與本文方法相同MP＝3，搜索半徑rE分別取本文設定值2.67cm、較小值1.00cm、較大值5.00cm.

K-means最終聚類效果如圖7所示，DBSCAN最終聚類效果如圖8所示.（每一種顏色的點所形成的區域即為駕駛員的一個注視區域.）

圖7 駕駛人視野區域劃分Fig.7 The region division of driver’s visual field

圖8 K-means聚類效果Fig.8 Effect of K-means clustering

3.3 結果分析

圖9 DBSCAN 聚類效果Fig.9 Effect of DBSCAN clustering

3.3.1 DBSCAN-MMC 與K-means 聚 類 的 比較分析 比較圖6與7可見，使用本文提出的DBSCAN-MMC聚類所劃分出的注視區域邊界緩和，每一區域的形狀隨區域中點的集中程度變化；聚類個數k＝5、10、15 的K-means 聚 類 將DBSCANMMC生成的區域7處的點分別劃歸為2類、5類和7類，且將密度較大、同區域距離相近的左側車窗注視區域1和左后視鏡區域2劃歸為一類，并將右側車窗注視區域8和右后視鏡區域9劃歸為一類.對比表明即使聚類個數正確，在使用K-means進行駕駛員注視區域劃分時也無法克服注視區域邊界生硬、區域劃分不合理等弊端.

根據上述比較判斷K-means聚類效果不及本文提出的DBSCAN-MMC聚類效果.經分析認為原因是：DBSCAN-MMC基于密度聚類確定注視密集區后，使用MMC 進行任意形狀的區域拓展；使用K-means聚類時，每次迭代的聚類中心確定后，距離相近的點會完全按照與聚類中心的距離被硬性劃歸為不同點簇，導致K-means等基于距離的聚類方法只能發現“類圓形”，當對象點非圓形時劃分邊界生硬.

3.1.2 DBSCAN-MMC 與DBSCAN 聚類的比較分析 比較圖6 與DBSCAN 聚類效果圖可見：當DBSCAN 參數設置與DBSCAN-MMC中DBSCAN設置相同時（圖8（a），生成11個點簇），每個區域邊緣處有較多點被劃歸至離散注視區域（深藍色“＊”表示）；當DBSCAN 參數rE設置較小時（圖8（b），生成24個點簇），離散注視區域包含點的數目明顯增加；當DBSCAN 參數Eps設置較大時（圖8（c），生成5個點簇），離散注視區域包含點雖有減少但表示不同現實意義的點（如風擋玻璃中心位置注視區域和左側車窗后視鏡上方注視區域）被劃歸為同一點簇.

根據上述比較判斷，在對駕駛員注視區域進行劃分時，單純DBSCAN 聚類的劃分效果不及本文DBSCAN-MMC 聚類的劃分效果.其原因為：單純使用DBSCAN 聚類時，參數rE的取值對區域邊緣處點的劃歸具有較大影響，當rE選定，將無法如DBSCAN-MMC 對聚類產生的離群點進行基于MMC的進一步劃分.

實例驗證結果表明本文提出的方法充分利用了DBSCAN 和MMC的聚類優勢并較好地解決了2種聚類方法的缺陷.通過比較證明了DBSCAN-MMC在進行駕駛員注視區域劃分時聚類效果優于常規K-means聚類方法和DBSCAN 聚類方法，提高了駕駛員注視區域劃分質量.

4 結 論

本文論述了基于距離聚類方法的缺點和單純的DBSCAN、MMC聚類方法的不足，針對駕駛員注視點離散、注視集中區域不規則特點，提出了一種面向駕駛員注視區域劃分的結合密度聚類和數學形態學聚類的DBSCAN-MMC 聚類方法.使用DBSCANMMC對熟練駕駛員進行直線、左轉、右轉3種駕駛行為時的眼動數據進行了聚類，劃分出了具有實際意義的注視區域，并將使用K-means和DBSCAN方法得到的劃分結果與使用DBSCAN-MMC 方法得到的劃分結果進行對比，分析了DBSCAN-MMC方法的優勢以及K-means、DBSCAN 方法劃分駕駛員注視區域效果不佳的原因.

DBSCAN-MMC聚類方法使用DBSCAN 確定注視密集區和聚類數目，進而使用MMC 對注視密集區進行區域拓展迭代，充分利用了DBSCAN 的密度劃分和MMC 自由拓展的劃分優勢，在一定程度上解決了DBSCAN 參數選取困難與MMC 需大量人工干預、可用性不高的問題，為科學合理地進行駕駛員注視區域劃分提供了可靠的方法.但DBSCAN-MMC聚類僅減少了rE值的選取對最終結果的影響程度，文中各參數值的選取方法是否適用于其他領域的聚類處理尚需進一步研究.

本文所述面向駕駛員注視區域劃分的聚類方法，旨在解決當前駕駛員注視點聚類方法存在的問題，提高駕駛員注視點聚類的合理性與準確性，為駕駛員注視區域劃分與駕駛員注視特征研究提供理論與技術支持.本文實例驗證的數據采集于熟練駕駛員駕駛小型客車的過程，得到的注視區域具有一定的代表性，然而限于作者能力和文章篇幅，未進行車輛類型、駕駛員特征、駕駛熟練程度等客觀因素對駕駛員注視區域劃分結果的影響的分析.但在后續研究中作者將逐一分析上述影響因素，并對駕駛員注視特征與注視規律進行系統、深入的研究.

（

）：

［1］郭應時.交通環境及駕駛經驗對駕駛員眼動和工作負荷影響的研究［D］.Xián：長安大學，2009.GUO Ying-shi.Study on effects of traffic environment and driving experience on driver’s eye movement and workload［D］.Chang’an University，2009.

［2］袁偉.城市道路環境中汽車駕駛員動態視覺特性試驗研究［D］.Xián：長安大學，2008.YUAN Wei.Study on Car Driver’s Dynamic visual characters test on city road［D］.Chang’an University，2008.

［3］ESTER M，KRIEGEL H P，SANDER J，et al.A Density-based algorithm for discovering clusters in large spatial databases with noise［C］∥Proc of 2nd Int’l Conf on Knowledge Discovering in Databases and Data Mining（KDD-96）.Portland：AAAI Press，1996.

［4］ANKERST M，BREUNIG M M，KRIEGEL H P.OPTICS：ordering points to identify the clustering structure［C］∥Alex Delis，Christos Faloutsos，Shahram Ghandeharizadeh eds.Proceedings of the ACM SIGMOD’99 Int Conf on Management of Data.Philaelphia Pennsylvanis：ACM Press，1999：49-60.

［5］LIN C Y，CHANG C C，LIN C C.A new density-based scheme for clustering based on genetic algorithm ［J］.Fundamenta Informaticae，2005，68（4）：315-331.

［6］FENG P J，GE L D.Adaptive DBSCAN-based algorithm for constellation reconstruction and modulation identification［C］∥Proceedings of Radio Science Conference 2004.Beijing：Pub House of Electronics Industry，2004：177-180.

［7］XU X，ESTER M，KRIEGEL H P，et al.A distribution-based clustering algorithm for mining in large spatial databases［C］∥eds.Proceedings of the 14th International Conference On Data Engineering（ICDE’98）.Orlando：IEEE Computer Society Press，1998：324-331.

［8］蔡穎琨，謝昆青，馬修軍.屏蔽了輸入參數敏感性的DBSCAN 改進算法［J］.北京大學學報：自然科學版，2004，40（3）：480-486.CAI Ying-kun，XIE Kun-qing，MA Xiu-jun.An improved DBSCAN algorithm which is insensitive to input parameters［J］.Acta Scientiarum Naturalium Universitatis Pekinensis，2012，36（5）：911-915.

［9］夏魯寧，荊繼武.SA-DBSCAN：一種自適應基于密度聚類算法［J］.中國科學院研究生院報，2009，26（4）：530-538.XIA Lu-ning，JING Ji-wu.SA-DBSCAN：A self-adaptive density2based clustering algorithm ［J］.Journal of the Graduate School of the Chinese Academy of Sciences，2009，26（4）：530-538.

［10］POSTAIRE J G，ZHANG R D C.Lecocq-botte.cluster analysis by binary morphology［J］.IEEE Computer Society，1993，15（2）：170-180.

［11］STAROVOITOV V..A clustering technique based on the distance transform ［J］.Pattern Recognition Letters，1996，17：231-239.

［12］羅會蘭，孔繁勝，楊小兵，等.基于數學形態學的聚類分析［J］.模式識別與人工智能，2006，19（6）：727-733.LUO Hui-Lan，KONG Fan-sheng，YANG Xiao-bing，et al.Cluster analysis based on mathematical morphology［J］.PR＆AI，2006，19（6）：727-733.

［13］羅會蘭，危輝.基于數學形態學的聚類集成算法［J］.計算機科學，2010，37（8）：214-218.LUO Hui-lan，WEI Hui.Clustering ensemble algorithm based on mathematical morphology［J］.Computer Science，2010，37（8）：214-218.

［14］邸凱昌，李德仁，李德毅.從空間數據庫發現聚類：一種基于數學形態學的算法［J］.中國圖象圖形學報，1998，3（3）：173-183.DI Kai-chang，LI De-ren，LI De-yi.A mathematical morphology based algorithm for discovering clusters in spatial databases［J］.Journal of Image and Graphics，1998，3（3）：173-183.