This paper introduces a fast matching algorithm to reduce the computational cost of the matching phase in the correlation algorithm based cellular probe speed estimation [1]. Real-time traffic speed is essential in current intelligent transportation systems for identifying traffic congestion and providing high quality navigation services. The correlation algorithm shows superior performance over the localization algorithm and the handoff algorithm in both highways and local arterial. According to this method, recorded handset''s signal strength profiles are compared with training traces at the same road. The speed scale which determined by the stretch or compression rate of the matched training trace is used to identify the speed of the target mobile probe. However, a critical issue of the current correlation algorithm, the time efficiency, was not investigated and discussed. The major contribution of this paper is to provide an efficient way to utilize the Fast Normalized Cross-Correlation (FNCC) algorithm to significantly reduce the computational consumption of the present correlation algorithm based method from 3N(M − N) additions/subtractions and 2N(M −N) multiplications to 9Mlog(M) additions/subtractions and 6Mlog(M) multiplications. Parameters N and M are size of the testing trace and the training trace, respectively. Experiment results concluded that 97% computational cost of the Pearson product Moment Correlation Co-efficient (PMCC) algorithm based matching method can be saved by implementing the FNCC method.
展开▼
机译:本文介绍了一种快速匹配算法,以减少基于相关算法的蜂窝探针速度估计中匹配阶段的计算成本[1]。在当前的智能交通系统中,实时交通速度对于识别交通拥堵并提供高质量的导航服务至关重要。在高速公路和本地动脉中,相关算法均表现出优于定位算法和交接算法的性能。根据这种方法,将记录的手机的信号强度曲线与同一条道路上的训练轨迹进行比较。由匹配的训练轨迹的拉伸或压缩率确定的速度标度用于标识目标移动探针的速度。但是,目前尚未研究和讨论当前相关算法的关键问题,即时间效率。本文的主要贡献在于提供一种有效的方法来利用快速归一化互相关(FNCC)算法从3N(M-N)加/减和2N(N M -N)乘以9Mlog(M)加/减和6Mlog(M)乘。参数N和M分别是测试轨迹和训练轨迹的大小。实验结果表明,通过实现FNCC方法,可以节省基于Pearson乘积矩相关系数(PMCC)算法的匹配方法的97%的计算成本。
展开▼