基于动态时间规整的酒驾识别研究

陈平生

(绍兴职业技术学院，浙江 绍兴312000)

0 引言

我国的汽车拥有量逐渐提高，根据中国汽车工业协会2013年1月11日发布的数据，2012年汽车的产销双双超过1900万辆，增幅高于上年.汽车带给人们极大便利的同时也带来了很多隐患.据统计[1]，在2012年9-10月的国内生产安全事故统计分析中，交通事故所占的比例达64.94%，死亡人数占总死亡人数的60.26%，受伤人数占到总受伤人数的79.15%.在这些交通事故中，酒驾占了相当的比重.2011年5-12月，全国就查处酒后驾驶机动车20多万起.醉酒驾车对驾驶者本人和社会生命财产安全带来巨大威胁[2].因此，迫切需要准确并有效的酒驾识别技术.

根据文献报道，现有的酒驾检测技术主要有：(1)基于酒精传感器的检测[3]，不过这种设备有天然的缺陷，即当酒驾者在不清醒的状态下，几乎不会主动使用这类产品.(2)基于视觉观测的方式[4,5]，根据两台固定相机捕捉到的驾驶员的头部行为，利用HMM等模式识别方法进行判断.这种方式设计的算法过于复杂，并且需要专用的高精度仪器，不具备大规模推广的价值.(3)利用加速度传感器来获取汽车行为，通过分析获得的数据，判断是否是酒驾[6].在这种思路的基础上，本文提出了一种基于动态时间规整算法的新型酒驾行为识别模式.

1 酒驾行为模式分析

根据美国国家公路交通安全管理局发布的报告[7]，研究者发现酒驾行为具备一定的模式，醉酒驾驶无法保持车道位置，往往会发生漂移、反复变道、迂回、突然大转弯调头等现象；无法做到匀速驾驶，例如突然加速或者减速，胡乱刹车或过快停车等.一般来说，当一辆汽车无法保持车道位置时，醉酒驾驶的可能性为50.75%，当汽车无法控制速度的情况发生，则醉酒驾驶的可能性为45.70%.当观察到一辆汽车同时具备上述两种行为时，根据概率公式：

P=1-1-PA1-PB

(1)

则酒驾的可能性则高达70%.在醉酒驾驶中，会反复出现上述情况，如此，根据汽车行为来判别是否酒驾的准确率就会大大提高.

2 系统和算法设计

2.1 系统设计

智能手机自带侧向和纵向加速传感器，加速传感器可采集汽车行驶过程中侧向和纵向的加速度.系统对侧向和纵向加速度进行分析，与酒驾模式特征数据进行匹配，匹配成功则发出警示信号，更新酒驾模式特征数据库，匹配不成功则继续采集加速度信息.酒驾识别系统(参见图1)主要由四部分组成[6]：

图1 酒驾识别系统流程图

图2 Android默认传感器坐标轴(图片来自android api)

第一部分是硬件准备部分，包括传感器的自检，位置校正.主要目的是确定硬件能正常工作，并校正系统的xyz轴.这里x轴的定义是沿着屏幕的水平方向从左向右，如果手机不是正方形的话，较短边水平放置，而较长边垂直放置，这里垂直方向便是y轴；手机平放在水平面上，垂直向上的是z轴，如图2所示[8].如果手机一开始是随意放置的，可以通过方向传感器来校正xyz轴.方向传感器可以读取这三个方向的角度偏差.依次记录下这三个值θx，θy，θz，然后根据公式2：

(2)

便可获得校正之后的坐标系.然后启动实时监控模块.

第二部分是数据采集，采用监听的速度是200 000(api参数)，即每200毫秒采集一次.这里选择200毫秒的原因是绝大多数的手机对过高采样频率的支持程度有待改善，在测试过程中发现，当每秒采样超过10次时，传感器就会变得不够稳定，而当每秒采样超过20次时，传感器有很大概率会停止工作.

第三部分是根据DTW算法，判断是否酒驾.

第四部分是警报模块.如果算法判定当前是酒驾行为，则发出刺耳的警报，吸引驾驶员注意，并提醒驾驶员采取相应的措施来避免事故发生.

2.2 DTW算法描述[9]

动态时间规整(Dynamic Time Warping, DTW)算法是把时间规整和距离测度计算结合起来的一种非线性规整技术[10,11].DTW主要用来衡量基于时间的两个序列之间的相似度.例如，它可以用来发现步行模式，即便一个人走得相对较快而另一个人走得相对慢速，或者两人在行走过程中发生加速或者减速的情况.任何可以用线性表示的数据都可以使用DTW进行分析.

通常，DTW算法是一种找到两个包含约束条件的给定顺序的序列中最佳匹配的算法.其中，给定顺序的序列通常是基于时间的维度.在该系统当中，加速度传感器采集到的数据正是基于时间序列的离散数据，因此可以应用DTW算法，比较实时采集的加速度传感器数据和存放在个性化模式数据库中的已归类数据，来准确判断当前是否在酒驾状态.如果系统判断当前处于酒驾状态，则警报器发出警报示警，否则就继续运行.

DTW算法的输入是两组时间序列Q和C，其中Q的长度为n，C的长度为m，它们表示为：

Q=q1,q2,…,qi,…,qn

(3)

C=c1,c2,…,cj,…,cm

(4)

将这两个序列用一个n*m的矩阵关联起来.矩阵的每一个元素(ith,jth) 表示Q中的第i个元素和C中的第j个元素之间的距离d(qi,cj)(多数情况下使用欧氏距离，因此d(qi,cj)=(qi-cj)2).接着定义一条由矩阵元素组成的W，用来作为Q和C之间的映射路径.令wk为W的第K个元素，wk=i,jk，因此，可得到如下公式：

W=w1,w2,…,wk,…,wpmaxm,n≤K

该映射路径受到以下三个条件的制约：

边界制约：w1=1,1，wk=m,n，整条映射路径必须连接矩阵的左上角和右下角.

连续性：对于给定的wk=a,b和wk-1=a′,b′，必须要满足a-a′≤1 和b-b′≤1 .其中，wk表示Q和C两个时间序列路径的第k个元素，a和b分别表示Q和C两个序列上的第a个元素和第b个元素.这些约束是为了确保映射路径只能经过相邻的矩阵元素.

单调性：对于给定的wk=a,b和wk-1=a′,b′，需要满足a-a′≥0 和b-b′≥0 .其中参数的意义同连续性中的描述.这个约束是为了保证所获得的W是单调的.

利用动态规划(DP)的思想，可以在较好的时间复杂度内获得W路径.用γi,j来标记累积路径，用di,j表示矩阵中当前单元的距离，做如下循环便可以获得最佳路径W：

γi,j=dqi,cj+minγi-1,j-1,γi-1,j,γi,j-1.

2.3 应用DTW判别酒驾行为

通过手机加速度传感器采集的数据是一组基于时间序列向量.正常的汽车驾驶过程中，汽车的纵向加速度值只是在0附近作非常细微的变化，几乎呈一条直线.而在酒驾过程中，由于驾驶员无法很好地控制自己的行为[6]，常常会出现突然且毫无规律的加速或减速操作.图3是上述两种情况的折线示意图.

图3 正常和模拟酒驾行车纵向加速度示意图

将正常行车获得的加速度序列记为D0，模拟酒驾行车获得的加速度序列记为C，基于DTW的酒驾行为识别算法描述如下：

算法输入：模拟行车加速度时序C，系统内置加速度时序D0(即正常模式)，D1,D2,…,Dt(各种酒驾模式).

算法输出：Yes/No.

算法伪代码：

1 DTWDistance(C, D[s]) {

2 DTW = array [0..n, 0..m]

3 for i = 1 to m

4 DTW[0, i] = ∞

5 for i = 1 to n

6 DTW[i, 0] = ∞

7 DTW[0, 0] = 0

(1)在堆载作用下，产生竖向位移，土体因为相对沉降差而产生负摩阻力；土体在沉降的过程中产生水平向的变形和位移，对邻近桩基施加水平推力。

8 for i = 1 to m

9 for j := 1 to m

10 cost= d(C[i], D[s][j])

11 DTW[i, j] = cost + minimum(

DTW[i-1, j ], DTW[i , j-1], DTW[i-1, j-1])

12 return DTW[n, m]

}

13 pattern = array [0 , t]

14 for s = 0 to t

15 pattern[s] = DTWDistance(C , D[s])

16 closest = pattern.min

17 if(closest == C)

18 return yes;

19 else

20 return no.

应用酒驾判断算法，可以判断当前是否处于酒驾状态.图4是算法中DTW部分的矩阵以及最佳路线示意图.

图4 正常行车和模拟酒驾行车DTW最佳路线图示意图

根据伪代码的算法描述，知道wk=m,n便是所求得的DTW距离.

重复上述步骤，依次计算酒驾序列和内置的多种酒驾模型序列的DTW距离，并在这些距离中选出一个最接近的，从而判断当前是否处于酒驾状态.

为了能更加及时发现酒驾行为，默认设置2秒为一个判断周期，每次输入的时间序列为5秒，共25个数据.但是由于手机硬件的原因，5秒中并不一定能保证得到25个数据.不过这并不影响该算法.

当算法最终返回一个结果，如果返回的是YES，则指示报警器示警，否则继续循环执行上述过程，直到程序终止运行.

3 系统开发和测试

3.1 系统开发环境

该系统采用的开发环境为Android SDK 4.2，使用装有ADT的Eclipse作为集成开发环境.采用了高版本的SDK，为了尽可能使程序兼容更多的设备，最低系统版本设置为2.2.本次测试使用的手机为Samsung galaxy s3，HTC G17和中兴U795，基本涵盖android手机中的高中低端机器.

3.2 测试和评估

根据前面的分析可知，利用智能手机的侧向和纵向加速度传感器来获得汽车行驶数据.在车上放置了三款分别为高中低端手机，由资深驾驶员驾车模拟.共测试了77组正常数据，23组异常车道行为数据，19组异常速度控制数据，其中的异常行驶尽可能模仿酒驾行驶.测试结果分析中定义了两种错误，分别是FN(False Negative，即酒驾过程未给出示警)和FP(False Positive，即正常驾驶给出酒驾示警).实验结果如表1所示.

表1 酒驾识别系统测试结果

通过以上数据可以发现，对于FN错误，高端机表现得非常出色，没有错误判断，中端机器出现1次异常车道行为漏判，低端机出现了2次异常车道行为和1次异常速度控制行为的漏判；而对于FP错误，低端机的表现反而比高端机要好.究其原因，应该和高端机器采用较好的传感器零件相关，对车况表现更加敏感所致.对于FN和FP错误，FN错误显然更加严重，而该系统在FN错误率上有着较为优秀的表现，基本不会漏判.由于酒驾行驶过程中，不可能只出现一次异常行为.假设每次出现异常行为的概率是相互独立的，那么连续两次漏判的概率为0.25%，如此低概率几乎可以杜绝漏报的可能.

4 结论

本文主要对基于动态时间规整的酒驾行为识别方法进行了研究.通过对酒驾行为模式的分析，设计了基于智能手机的酒驾识别系统.即利用智能手机采集的侧向和纵向加速度信息，与酒驾特征数据进行匹配，判断是否处于酒驾状态.实验结果验证了算法的有效性和系统的适应性.

参考文献：

[1]李生才,笑蕾.2012年9—10月国内生产安全事故统计分析[J].安全与环境学报,2012,12(6):269-272.

[2]周明欣.“7个月20万起酒驾”令人忧[J].安全与健康,2012(12),20.

[3]潘祖军,朱文胜,岳睿.汽车用酒精传感器的分析[J].北京汽车.2007(1):39-41.

[4]Zhu Zhiwei,Qiang Ji.Real time and non-intrusive driver fatigue monitoring[C].Intelligent Transportation Systems,2004.Proceedings.The 7th International IEEE Conference on.IEEE,2004:657-662.

[5]Alexandra Branzan Albu,Ben Widsten,Tiange Wang,et al.A computer vision-based system for real-time detection of sleep onset in fatigued drivers[C].Intelligent vehicles symposium,2008 IEEE.IEEE,2008:25-30.

[6]Jiangpeng Dai,Jin Teng,Xiaole Bai,Zhaohui Shen and Dong Xuan.Mobile phone based drunk driving detection[C].Pervasive Computing Technologies for Healthcare (PervasiveHealth),2010 4th International Conference on-NO PERMISSIONS.IEEE,2010:198-205.

[7]U.S.NHTSA,The Visual Detection of DWI Motorists,http://www.nhtsa.dot.gov/people/injury/alcohol/dwi/dwihtml/index.htm.

[8]Google,Inc.Android Api[OL].[2013-02-03].https://developer.android.com/reference/android/hardware/SensorEvent.html#values.

[9]Keogh,Eamonn J.,Michael J.and Pazzani.Derivative dynamic time warping[C].the 1st SIAM Int.Conf.on Data Mining (SDM-2001),Chicago,IL,USA.2001:1-11.

[10]朱淑琴,赵瑛.DTW语音识别算法研究与分析[J].微计算机信息.2012,28(5):150-151,163.

[11]Berndt D.and James Clifford.Using dynamic time warping to find patterns in time series[J].KDD workshop.1994,10(16):359-370.

Abstract： In view of drunk driving detection, a new algorithm based on dynamic time warping is proposed, combining the data collected by the longitudinal and lateral acceleration of smartphone, dynamically matching the drunk-driving schema and finally judging whether the car is under the state of drunk driving. The experimental results show that this method is effective and practical.

Keywords：dynamic time warping; drunk driving detection; acceleration sensor; smartphone