Fast Normalized Cross-Correlation enhanced floating car data estimation

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. 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.