基于DBSCAN聚类算法的图像消失点计算方法

袁 鹏，陈国良

(武汉理工大学 机电工程学院，湖北 武汉 430070)

基于道路交通视频场景的摄像机自动标定方法中最常见的就是基于消失点的标定方法，该方法利用图像中的消失点信息进行相机模型的参数计算以及标定。1990年，Caprile和Torre首先提出利用消失点进行摄像机标定[1]。

道路环境下，背景信息复杂，可靠的检测消失点成为相关研究的重要目标。Lv[2]等提出利用视频中行人头部、脚部定位点连线作为垂直于地面的直线，据此进行消失点的估计，完成摄像机自标定。然而，交通视频场景下行人特征并不稳定。文献[3]通过道路线路或者车道线来获取消失点。 陈珂[4]通过车道线与垂直于道路的路灯来进行特定场景下的标定，并应用于车速检测。这些方法需要获得清晰的车道线或者其他标志物，对于结构化道路比较适用。在非结构化道路或者不能检测出清晰标志物的场景，这些方法将不再适用。

文献[5]假设车辆在一定程度上是沿直线行驶的，通过跟踪车辆轨迹以及建立边缘背景模型检测车辆边缘方向的直线来进行消失点的获取,分别获得指向对应消失点的直线信息。

为了在一定程度上消除虚假消失点的干扰，王伟等[6]利用道路场景中冗余信息构造非线性约束条件，对标定参数进行迭代求最优，减少标定误差。Wang[7]等通过均值漂移聚类(mean shift clustering)算法结合拉普拉斯线性算法回归对消失点进行处理，但是均值漂移聚类算法无法排除大量噪声点。文献[5]对得到的指向消失点的直线数据通过基于平行坐标系(PClines)的级联霍夫变换(cascaded hough transform, CHT)将实投影平面上的点转化为钻石空间(diamond space)上的点，再进行投票获得两个正交消失点。投票方法只选取了票数最高的点作为消失点，这在难以检测车辆直线特征的道路场景下可能存在较大误差。

笔者针对文献[5]在车辆较少的场景中表现不佳，提出改进的DBSCAN密度聚类算法(density-based spatial clustering of applications with noise， DBSCAN)[8]，通过对消失点进行聚类，找到较准确的消失点。并针对DBSCAN密度聚类算法难以处理消失点数据不均匀的问题，提出邻域距离阈值自适应降低算法，并通过实验证明相关算法的可行性。

1 消失点的描述

消失点是世界坐标系中相互平行的直线经过投影变换之后在图像坐标系中的交点。

图1中ABCD为矩形，经过投影变换到图像坐标系中，得到A′B′C′D′,现实中的平行线AB，CD与AD，BC分别在图像坐标系中相交于VP2和VP1。VP1与VP2即为消失点。在AB，CD与AD，BC相互垂直的情况下，VP1与VP2为一对正交消失点。

图1 消失点示意图

道路场景下，最常见的一对正交消失点为沿道路方向消失点以及道路平面内垂直于道路的消失点，分别表示为VP1，VP2。VP1通常为道路车道或分道线的交点，VP2常利用车辆边缘求得。

垂直于道路的消失点VP3将由消失点的性质计算得出。Caprile和Torre证明消失点具有3个性质：

(1)平行于同一平面的直线与对应的消失点都分布在同一条消失线上；

(2)摄像机的像主点位于以3个正交消失点为顶点所构成的三角形的垂心上。

(3)若已知3个正交消失点中的一个消失点以及过该消失点的直线，即消失线，可以求得其他两个正交消失点的坐标。

由图2可知，当已知正交消失点VP1,VP2，以及主点坐标P时，由性质(2)可以计算VP3坐标。具体过程如下：过主点P作VP1,VP2连接线l1的垂线l2，过VP1作主点P,VP2连接线l3的垂线l4，l2与l4的交点即为对应的正交消失点VP3。

图2 正交消失点与像主点示意图

2 消失点计算

2.1 沿道路方向的消失点(VP1)

在道路场景下车道线的获取并不稳定，且在检测到车道线的情况下仅通过车道线来获取消失点缺乏鲁棒性。车辆轨迹是交通视频数据中比较容易获得的特征信息，理想情况下，车辆轨迹集中的轨迹相互平行且指向沿道路消失点。对道路方向的消失点检测步骤如下：

步骤1利用Shi-Tomasi角点检测[9]方法检测视频帧中的角点。

步骤2利用Kanade-Lucas-Tomasi角点跟踪算法进行轨迹跟踪，获得轨迹集合。

步骤3利用基于平行坐标系的级联霍夫变换将直线转换到钻石空间投票即获得消失点VP1。

由于车辆轨迹获取的直线长度比较长，且大部分都能准确指向消失点，故消失点VP1可以直接利用基于平行坐标系的霍夫变换投票求取。为避免车辆变道等对轨迹线方向的干扰，对多辆车进行角点检测与跟踪，获取较多轨迹样本。

2.2 道路平面内垂直于道路的消失点(VP2)

VP2方向上的直线一般采取对车辆边缘进行直线检测的方式。边缘和直线检测的精度，用于投票选出VP2的直线方向等多种因素都会对VP2精度产生影响。视频中车辆较少或难以检测车辆边缘时，直接对候选直线进行钻石空间投票会出现较大误差。选择不对候选直线进行投票选择最大值作为VP2，而是采用直线交叉求解交点，获得消失点候选点集之后再做处理，减小偶然误差的影响。步骤如下：

步骤1利用混合高斯背景建模法(gaussian mixture background modeling, GMM)，结合阴影检测算法HSV(hue,saturation,value)去除阴影部分，获得车辆前景掩膜mask，经过形态学处理与运算等手段，得到车辆的真实前景Matfore。

步骤2对Matfore进行Canny边缘检测，之后利用亚像素直线检测算法LSD(line segment dector)进行直线检测。利用长度，角度以及VP1等限制条件对直线进行筛选。

步骤3对直线交叉求交点，得到消失点VP2的候选集合为ΩVP2。通过后续的算法对候选集合进行求解以获得较为精确的消失点VP2。

背景信息中含有大量各个方向的直线干扰，故直接对读取的视频帧进行边缘检测将会出现大量干扰。通过背景建模算法，获取原图像中的前景轮廓，保留汽车上的边缘信息，剔除背景干扰。设前景像素为M(x,y)，前景掩膜mask(x,y)利用二值化去除阴影区域，由式(1)计算车辆前景边缘信息Mcar(x,y)。

(1)

考虑到混合高斯背景建模获取的前景信息比较完整，能够提高直线检测的概率，且算法比较成熟，运算速度快，能达到实时处理速度。故采用GMM算法，并结合HSV阴影检测去除阴影。

对前景掩膜mask(x,y)进行滤波、填充空洞等手段之后，前景区域更加完整。然后由式(1)得到保留有车辆边缘信息的Mcar(x,y)。对Mcar(x,y)进行边缘检测，即可得到前景边缘信息，采用Canny算子进行边缘检测。

对边缘检测图像利用LSD亚像素直线检测算法检测直线，提高直线检测精度。并通过方向、角度和长度等条件调整检测到的直线。

按照步骤3计算候选消失点并保存到VP2的候选集合ΩVP2中。

2.3 消失点精度改进算法

为找到消失点数据分布密集区域，利用基于密度的聚类算法DBSCAN算法对消失点数据进行处理，寻找高可靠度的消失点区域。DBSCAN算法用参数(,MinPts)来描述邻域的样本分布紧密程度。表示某一样本的邻域距离阈值，MinPts描述某一样本的距离为的邻域中样本个数的阈值。该算法的主要思想为：对于一个未被聚类点，如果邻域内包含的样本数不小于指定的MinPts，则该点为核心点。对邻域内的点不断进行上述过程，直到所有的点被遍历到。

=k×

(2)

式中：k为减小的比例系数。

(3)

式中:loop为迭代次数。

对于上述迭代过程，由于DBSCAN数据的去噪特性，能够在迭代过程中不断筛选密度过低的噪声区域。消失点数据存在大量数值较小的数据，且分布较密集，在邻域距离阈值较大时，这类区域通常被划分为一个聚类簇，包含最多的有效点，设此聚类簇为Dmax。因此在上述迭代过程中，可以通过控制Dmax含有的数据点占总数据点数的比例来控制迭代的次数。设该比例为λ，当λ减小到一定范围，既能够排除一定的噪声点，又可避免可能有效的聚类簇被判别为噪声。λ定义如下：

(4)

式中:NDmax为最大聚类簇中包含的样本数量；Ntotal为样本总数量。

迭代结束后，排除一部分噪声数据，得到处理后的ΩVP2。在实际计算中，消失点VP3的值通常比较大，因此利用VP3对ΩVP2再次进行筛选。

对ΩVP2集合中的每个候选点以及VP1值利用消失点性质(2)计算对应的消失点VP3，保存集合为ΩVP3。

对ΩVP3进行聚类，设ΩVP3中点属于聚类簇的集合为Ωcluster，按照式(5)对VP2进行筛选：

(5)

式中:PVP2为true代表计算得到该VP3点的对应VP2值应该纳入最终的VP2候选集合中，否则不加入；yc为某点所属聚类簇的质心的纵坐标，ymean为所有聚类簇的质心的纵坐标的均值。

后续对集合ΩVP2中的消失点分别再次进行聚类，并得到每个聚类簇的质心，对所有质心取中位数作为消失点VP2。

3 实验结果及评估

利用文献[10]提供的BrnoCompSpeed数据集进行实验。BrnoCompSpeed数据集由布尔诺理工大学提供，包含交通监控摄像头记录的视频和元数据。该数据集在高速公路环境下拍摄，通过记录的元数据可以计算Ground Truth。BrnoCompSpeed数据集如图3所示。

图3 BrnoCompSpeed数据集

由2.1节获取车辆轨迹之后，由钻石空间投票获取消失点VP1。

图4为车辆轨迹经钻石空间投票方法所获得的VP1与真实的VP1值。可知该方法的准确率较高。在静态背景条件下，由KLT(kanade lucas tomasis)跟踪车辆轨迹的方法比较适用。但在光照变化明显，背景抖动等情况下，该方法将出现大量误差，甚至无法正常工作。此时则需要其他方法来正确获取车辆轨迹。

图4 轨迹投票结果

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

图5 参数自调整时VP2候选点DBSCAN聚类图

图5为MinPts=3，λ=0.9时调整时部分聚类结果，Noise代表噪声点，C#代表聚类簇，epsilon代表参数。实验证明，设置λ=0.8～0.9时算法的结果比较准确，且结果变化相差较小，因此λ值可以在相对固定的情况下对VP2候选点进行去躁。固定MinPts为3，在初始选取为较大值10 000时，经过DBSCAN聚类参数多次自调整后，大约经过20余次迭代即可排除大部分噪声消失点。

将最后一次迭代之后的有效VP2候选消失点集，以及经过投票之后的VP1，按照消失点性质(2)计算VP3，得到VP3集合。最终，由式(5)筛选出对应的VP2集合，去除噪点数据，得到各个聚类簇的质心，VP2选取为所有质心的中位数。

由于DBSCAN聚类算法在数据量较多时表现不佳，故在直线数据较多时，算法的运行时间会大幅度增加。但在获取直线特征数据较少时，算法能够在较短时间内检测出消失点并计算参数，检测的误差也低于文献[5]的方法。因为文献[5]的方法直接票选最高得票点为消失点，在数据样本较少时增大了误差。而笔者提出的方法给予可能正确但票数较少的消失点参与最终计算过程的机会。在数据较多时，已有大多数准确的直线特征参与计算，算法耗时大幅度增加，精确度下降。此时采用钻石空间投票方式更为合适。

4 结论

基于消失点的相机标定方案，针对某些道路交通视频场景获得用于检测消失点的特征较少时，检测消失点误差较大的问题，提出结合基于平行坐标系的级联霍夫变换和DBSCAN密度聚类算法分别计算道路交通视频中两个正交消失点，并通过改进DBSCAN聚类算法的预设参数，使其自动调整到合适阈值范围内。这种方法能够在道路环境下检测到的直线特征较少时适用，当直线数据丰富时，计算量及误差都会增大，此时可采用投票等方法进行检测。