面向驾驶员注视区域划分的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.