热点推荐词:

常见问题

基于车牌识别流数据的车辆伴随模式发现方法

文字:[大][中][小] 手机页面二维码 2019/3/8     浏览次数:    
  基于车牌识别流数据的车辆伴随模式发现方法
  摘要:针对伴随车辆检测这一新兴的智能交通应用,在一种特殊的流式时空大数据——车牌识别流式大数据(ANPR)下,重新定义了Platoon伴随模式,提出PlatoonFinder算法,即时地在车牌识别数据流上挖掘Platoon伴随模式.主要贡献包括:第一,将Platoon伴随模式发现问题映射为数据流上的带有时空约束的频繁序列挖掘问题,与传统频繁序列挖掘算法仅考虑序列元素之间位置关系不同,该算法能够在频繁序列挖掘的过程中有效处理序列元素之间复杂的时空约束关系;第二,该算法融入了伪投影等性能优化技术,针对数据流的特点进行了性能优化,能够有效应对车牌识别流式大数据的速率和规模,从而实现车辆Platoon伴随模式的即时发现.通过在真实车牌识别数据集上的实验分析表明:PlatoonFinder算法的平均延时显著低于经典的Aprior和PrefixSpan等频繁模式挖掘算法,也低于真实情况下交通摄像头的车牌识别最小时间间隔.因此,所提出的算法可以有效地发现伴随车辆组及其移动模式
  关键词:流式时空大数据;大数据分析;伴随模式

  频繁序列挖掘智能交通系统(intelligenttransportationsystem,简称ITS)是软件工程技术的典型应用领域.随着大数据时代的到来,智能交通应用必然会产生重大变化,新型交通应用系统的研发和部署,也必将对大数据软件工程技术的发展起到极大促动.目前,各种交通信息采集技术广泛应用于城市交通,持续地产生海量且实时的时空数据.这些海量数据是交通的规划、管控、预测、引导的信息源和基础,同时也带来了新的问题和困境:海量实时时空数据的潜在价值还没有得到有效的分析、挖掘和应用.为此,本文重点关注一类典型的交通大数据——车牌识别流式大数据(automaticnumberplaterecognitiondata,简称ANPR)的实时分析和挖掘方法.车牌识别数据源自城市道路路口安装的交通摄像头,提供了全天候的车辆行驶位置监视能力.本文将在车牌识别流式大数据基础上,瞄准伴随车辆即时检测这一新兴的智能交通应用,聚焦于伴随车辆检测的核心算法和软件实现。

  1引言
  当前,记录对象移动模式的时空数据在规模上迅速膨胀.在时空数据中发现移动对象的移动模式具有重要的研究价值.车辆是日常生活中最常见的移动对象之一.在一段时间内,一起移动的车辆组群所具有的移动模式通常被称为车辆伴随模式.近年来,车辆伴随模式的发现逐渐成为国内外学者关注的热点研究问题,相关的研究成果已经被广泛应用到智能交通等领域当前,移动车辆伴随模式的发现研究大多基于GPS数据.GPS数据由安装在车辆上的GPS设备按照固定的时间间隔产生并回传.没有安装GPS设备或者设备没有开启的车辆不会产生GPS数据.在某些特殊场合下如车辆跟踪、犯罪嫌疑人出逃等,嫌疑人通常会关闭甚至拆掉GPS设备以防止被公安机关发现并拦截.这使得基于GPS数据实现的车辆伴随模式发现方法无法满足上述场景的需求与GPS数据不同,车牌识别数据源自城市道路路口安装的交通摄像头,这些摄像头能够不间断采集过往车辆的信息,包括车牌号码和采集时间.这些信息以流数据的形式传输到交通管理部门的数据中心,用于进一步的分析和挖掘.车牌识别数据提供了全天候的车辆行驶位置监视能力,是交通大数据的一类典型代表.当前,我国大型城市安装的交通摄像头已经超过5000台,且数量仍在持续增加.摄像头采集车辆信息的速率取决于摄像头的拍摄频率,最高可以达到每秒采集一次,即,高峰时期流式车牌识别数据的速率可达5000条每秒.假设每台摄像头每天采集车辆信息的平均速率为高峰期的1/3,则每天采集数据的总数可以达到1.44亿条,一年的数据量可以达到PB级基于GPS数据,现有研究工作已经抽象并总结了多种典型的车辆伴随模式,包括等.这些模式的目的都是为了发现一段时间内一起移动的车辆群组但是不同模式对于伴随车辆的时空约束定义有较大不同.在时间约束上,Flock和Convoy模式要求伴随车辆经过的时间点具有连续性;Swarm和TravelingCompanion对时间点的连续性没有要求;Platoon模式要求车辆组群在若干时间段内一起移动.每个时间段由不少于?个连续的时间点组成,且时间点总数不少于k.Platoon模式实质上是一种比上述几种模式更为通用的伴随模式,?的不同取值可以得到上述几种不同的伴随模式.例如,设模式实际经过了l个时间点,当?>l/2时,Platoon模式的时间约束与Flock/Convoy一致,当?=1时模式的时间约束与Swarm/TravelingCompanion一致[8].此外,在空间约束方面,Flock要求车辆处于圆盘形的地理区域,而其他工作将这一约束放松至密度可达本文的前期工作是基于历史车牌识别数据和流式车牌识数据开展了TravelingCompanion伴随模式的发现研究.首先,基于历史车牌识别数据,通过借鉴频繁项集挖掘经典算法Apriori算法设计了基于Spark的并行伴随车辆发现算法,并将其应用于社区拼车.随后,我们又尝试从流式车牌识别数据中即时发现伴随车辆.为实现这一目标,我们提出了点伴随的概念,用于描述一起通过单个摄像头的车辆组群,并设计了点伴随检测的并行优化算法在前期工作的基础上,本文聚焦于车牌识别数据流上的Platoon伴随模式的发现问题,将其映射为带有时空约束的频繁序列挖掘问题,并提出了相应的伴随车辆发现算法PlatoonFinder,以在车辆通过交通摄像头时即时发现并输出车辆的Platoon伴随模式.算法的主要贡献包括基于车牌识别流式大数据的特点,本文在借鉴相关工作的基础上重新定义了Platoon伴随模式与传统的频繁序列挖掘算法相比,PlatoonFinder算法在计算频繁序列时考虑了自定义的时空约束:首先,要求频繁序列的每个元素在序列数据库中以足够接近的时间出现;第二,要求频繁序列由若干子序列组成,每个子序列的元素在序列数据库中相邻出现本文一方面压缩了参与计算的序列数据库,另一方面在构建数据库时融入了伪投影技术,从而降低了计算复杂度,提升了算法的性能.实验结果表明,PlatoonFinder算法的平均延时明显低于真实情况下车牌识别数据之间的最小时间间隔。
  2相关工作
  伴随模式发现
  研究人员进行了大量针对伴随模式的研究与探索,提出了不同条件下的伴随模式定义及挖掘算法.以提出的时间为顺序,典型的工作包括Flock[1?3],Convoy[4,5],Swarm[6],TravelingCompanion[7],Platoon[8]等.Flock和定义了一种强时空约束的伴随模式.Flock要求车辆组群在不少于k个连续时间点上处于一个足够小的圆形地理空间内(k可称为时间点总数阈值).Convoy将Flock的空间约束扩展为密度可达的地理空间.Swarm和可以视作同一种伴随模式[7].该模式放宽了Convoy的时间约束,要求车辆组群在k个时间点(不一定连续)上处于密度可达的地理空间内.因此,如果一组车辆组群的移动模式符合Flock模式,则一定符合模式,也一定符合Swarm和TravelingCompanion模式.Platoon伴随模式也要求车辆组群在k个时间点上处于密度可达的地理空间.具体的说,Platoon模式是指车辆组群在若干个长度至少为?(?为正整数)的连续时间点下处于某种地理位置区域内,且时间点的总和不少于k个.不妨设Platoon模式实际的时间点总数为l,满足≥k.Platoon伴随模式是更通用的模式,用户可以通过设定?值得到上述伴随模式.当?>l/2,得到的是Convoy模式;而当?=1时,得到的是Swarm/TravelingCompanion模式[8].此外,Platoon伴随模式可以根据设定的阈值细化出不同于上述各种的模式.例如1<?<l/2时,可以得到局部时间连续的伴随模式.因此,Platoon伴随模式既可以根据不同场景挖掘Convoy模式和Swarm/TravelingCompanion模式,也可以根据不同需求挖掘出局部时间连续模式和全局时间连续模式.这些是Flock,Convoy,Swarm,TravelingCompanion等任何一个模式无法实现的。
  除了上述伴随模式发现工作,还有相当一部分研究人员专注于移动对象的聚类[11?14].Kalnis试图找到两个连续的时间戳内有大部分的重叠移动对象[11].Li等人采用微聚类(micro-clustering),在对移动对象进行聚类时既考虑了移动对象的当前位置又考虑了短期内未来的位置[12].Kriegel等人利用了模糊距离函数进行移动对象的聚类[13].Jensen等人提出了一种增量式的方法在一段时间内对移动对象进行聚类,减少了计算开销此外,近年来,更多人开始关注大规模轨迹数据的研究.Zheng使用一系列的技术手段,力求提高在大规模静态轨迹数据集中对移动对象组群聚类的性能[15].Zhang提出一种聚类检索算法,通过查找一个由移动对象组群组成的时空图来检索移动对象的聚类模式[16].Yoo尝试使用MapReduce框架来达到更优的处理效率,同时也提出了一种划分策略来避免数据之间关系的丢失然而,上述的大部分研究方法针对静态GPS数据设计,无法直接应用于流数据的处理.流数据具有实时到达、不可预知、没有边界等特点,流数据的这些特性导致了流数据难以存储且对实时性要求很高.显然,静态数据方法无法满足这些需求.但在交通领域的应用中,数据通常都是以流的形式提供的.因此,近年来,越来越多的学者开始研究流式交通数据的处理.除了Tang提出的流式轨迹数据上TravelingCompanion模式的发现框架外,Yu针对流式轨迹数据研究了一种基于密度的聚类算法,尝试实时地发现轨迹组群[18,19].本文聚焦于一种特殊的流式交通数据——流式车牌识别数据,根据前文的分析,这种数据的到达率可以到达5000条/秒甚至更高,且高峰时期每台交通摄像头可以每秒产生一条数据.因此,本文面临的问题是如何在如此高的数据到达速率下即时发现伴随车辆,即:每当车辆通过交通监控摄像头时,本文的方法能够快速发现该车辆的伴随车辆,并将结果输出出来.根据流式车牌识别数据的特性,本文方法的延时应该低于真实数据之间的最小时间间隔(1s),以避免因数据堆积导致的延时急剧增加.而目前,所有的相关工作都针对的是流式GPS数据并且取得了很大的进步,虽然无法解决本文的问题,但为本文的研究提供了坚实的基础2.2频繁序列挖掘
  频繁序列挖掘算法可以分为两类:基于Apriori的算法(Apriori-basedalgorithms)和基于投影数据的算法基于Apriori的典型算法包括等,这类算法的缺点是需要构建规模庞大的候选集;基于投影数据的典型算法包括和BIDE[27]等,这类算法通过构造投影数据库而非候选集,显著提升了算法的性能.此外,研究人员开始关注带有约束的频繁序列挖掘问题.Helen等人提出了多维频繁序列的概念并提出了相应的挖掘算法[28].多维频繁序列数据库与传统序列数据库的区别在于,前者除了有SID和序列之外还包含若干属性.Pei等人归纳了频繁序列挖掘中存在的7个约束,包括项约束(如用户只对某些项感兴趣)、长度约束(用户对频繁序列的长度约束)、超集约束(是否存在频繁序列???)、聚合约束(如频繁序列的各项和、平均值、最大最小值、方差等的约束)、正则表达式约束(对某些项的条件约束)、持续时间约束(频繁序列的各项必须在某个时间段内出现)以及间隔约束(频繁序列相邻项的时间间隔约束)[29].而本文涉及的时间约束并没有包含在以上7种约束之内.另外,Chueh深入研究了带有时间间隔约束的频繁序列挖掘问题并提出了相关算法

  为了提高算法性能,部分学者对频繁序列挖掘算法进行了并行优化.Demiriz基于SPADE提出了分析网站点击流的并行化算法webSPADE.Guralnik等人提出了基于分布式内存的频繁序列挖掘并行算法等人提出了一种基于分布式内存系统的闭频繁序列挖掘并行算法PFCSeq.每个处理程序独立挖掘本地的闭频繁序列,处理器之间交互的减少,显著降低了算法的时间消耗.Qiao等人提出了一种轨迹序列挖掘算法该算法使用了前缀投影技术、并行技术和候选集剪枝技术降低计算开销[34].Yu等人利用框架将BIDE算法并行化.Kessl提出了一种基于概率模型的静态负载均衡并行算法挖掘频繁序列以上工作都是频繁序列挖掘领域的典型工作,为本文的算法奠定了良好的基础.本文的定理1即是根据算法的公共前缀引和偏序引理而得.然而,以上工作并没有涉及本文提出的时空约束:没有考虑频繁序列各元素在序列中的相邻位置关系,没有考虑频繁序列各元素在不同序列中出现的时间间隔.因此,本文在借鉴已有工作的基础上设计了能够挖掘带有时空约束的频繁序列算法.该算法为基于车牌识别流式大数据的Platoon伴随模式发现而设计,在未来的工作中,我们将进一步研究带有时空约束的频繁序列挖掘通用算法,使之得到更广泛的应用.此外,在未来的工作中,我们还将尝试利用并行等优化手段进一步提高算法的性能。


本文由 安徽车牌识别系统 整理编辑。

返回上一步
打印此页
在线咨询
在线客服:
133 3565 4420

请扫描二维码访问手机站

[向上]