归一化互相关中计算基准子图能量的快速递推

景象匹配对匹配算法的运行速度和内存占用均要求较高。为提升归一化互相关算法的运行速度并降低其内存占用率,本文重点对其中的基准子图能量计算步骤进行了加速研究。经过详细分析,积分图法具有灵活、快速的优点,但缺陷为其在快速计算的同时需花费较大内存,并不适合直接应用在嵌入式系统中。本文提出了一种快速递推算法。该算法利用相邻像素值的能量进行连续递推,计算时可以不必像积分图法那样给所有的图像能量都分配空间,只需预留1行的像素空间便能完成整个能量计算过程。实验结果表明:在时间花费方面,快速递推法具有和积分图法相当的运算速度,耗时均只为传统归一化互相关算法的1/2;在内存占用率方面,快速递推法约为积分图法的1/3以下,且实时图尺寸越大,快速递推法占用的内存越小。综上所述,在归一化互相关算法中利用经典积分图法和本文提出的快速递推法计算基准子图能量,均较传统NCC算法有所加速,两种算法各具优点,经典积分图法快速、灵活,适用于对速度要求高,但对内存占用率要求不太高的应用场景;而快速递推法快速、省内存,更适用于嵌入式系统的应用。

Fast recurrence algorithm for computing sub-Image energy using normalized cross correlation

Scene matching requires higher matching speed and memory usage. In order to improve the running speed of the normalized cross correlation algorithm and reduce its memory occupancy rate,this paper focus on researching the steps of fast calculating sub-image's energy. After detailed analysis, the integral graph method has the advantages of flexible and rapid, but the defect is that it needs to spend a lot of memory at the same time, while it is not suitable for the embedded system. Therefore, a fast recurrence method was proposed. In this method, the energy of adjacent pixel values is used to continuously recursive compute. It is not necessary to allocate space for all image energy as the integral image method in the calculation process. Only one row of space can be reserved for the entire energy calculation process in fast recurrence method, which greatly saves the memory usage. The fast recurrence method has the equivalent calculation speed with the integral image method, and the time consuming is only 1/2 of the traditional normalization cross correlation algorithm. In the memory occupancy rate, the fast recurrence method is less than 1/3 of the integral image method, and the larger the size of the real-time graph, the less memory occupied by the fast delivery method. In the normalized cross correlation algorithm, the classical integral graph method and the fast recursive method proposed in this paper are used to calculate the energy of the sub-image's energy, which are both faster than the traditional NCC algorithm. The two algorithms have their advantages. The classical integration image method is fast and flexible, which is suitable for the application scene with high speed requirements, but the memory occupancy rate is not very high. The fast recursive method is fast and saves memory, and is more suitable for the application of embedded systems.