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

Bing HAN; Zhong-feng MU; Xiao-feng LE; Xiao-zhi JIA; Xuan-wei SHI; Bei-bei LI

doi:10.3788/OPE.20182610.2565

您当前的位置：

首页 >

文章列表页 >

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

Information Sciences | 更新时间：2020-07-05

- Fast recurrence algorithm for computing sub-Image energy using normalized cross correlation
- Optics and Precision Engineering Vol. 26, Issue 10, Pages: 2565-2574(2018)
- 作者机构：
  
  1.长光卫星技术有限公司, 吉林长春 130033
  2.中国科学院长春光学精密机械与物理研究所, 吉林长春 130033
- 作者简介：
- 基金信息：
- DOI：10.3788/OPE.20182610.2565
  CLC： TP301.6
- Received：10 February 2018，
  
  Accepted：23 April 2018，
  
  Published：25 October 2018
- 稿件说明：
移动端阅览
Bing HAN, Zhong-feng MU, Xiao-feng LE, et al. Fast recurrence algorithm for computing sub-Image energy using normalized cross correlation[J]. Optics and precision engineering, 2018, 26(10): 2565-2574.
DOI：

Bing HAN, Zhong-feng MU, Xiao-feng LE, et al. Fast recurrence algorithm for computing sub-Image energy using normalized cross correlation[J]. Optics and precision engineering, 2018, 26(10): 2565-2574. DOI： 10.3788/OPE.20182610.2565.

摘要

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

Abstract

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.

关键词

Keywords

references

TSAI D M, LIN C T. Fast normalized cross correlation for defect detection[J]. Pattern Recognition, 2003, 24, 2625-2631.

徐伟, 陈彦彤, 朴永杰, 等.基于吉林一号遥感图像的星载目标快速识别系统[J].光学精密工程, 2017, 25(1):255-262.

XU W, CHEN Y T, PIAO Y J, et al.. Target fast matching recognition of on-board system based on Jilin-1 satellite image[J]. Optics and Precision Engineering, 2017, 25(1):255-262. (in Chinese)

张浩鹏.基于互相关计算加速器的实时目标跟踪系统设计与实现[D].浙江大学, 2014. http://cdmd.cnki.com.cn/Article/CDMD-10335-1014193685.htm

ZHANG H P. Design and implementation of real-time target tracking system based on intercorrelation computing accelerators [D]. Zhejiang University, 2014. (in Chinese)

HⅡ A J H, HANN C E, CHASE J G, et al.. Fast normalized cross correlation for motion tracking using basis functions[J]. Computer Methods and Programs in Biomedicine, 2006, 82(2):144-156.

ARMELLONI E, GIOTTOLI C, FARINA A, et al.. Implementation of realtime partitioned convoluti-on on a DSP board[C]. 2003 I EEE Workshop on Applications of Signal Processing to Audio and Acoustics, New Paltz, NY , 2003.10, 19-22. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=1285822

田立, 周付根, 孟偲, 等.互相关跟踪算法的多核DSP快速实现[J].高技术通讯, 2013, 23(12):1248-1253.

TIAN L, ZHOU F G, MENG S, et al.. Fast implementation of multi-core DSP for intercorrelation tracking algorithm[J]. High-tech Communications, 2013, 23(12):1248-1253.(in Chinese)

刘毅飞, 张旭明, 丁明跃.归一化互相关灰度图像匹配的多核信号处理器实现[J].计算机应用, 2011, 31(12):3334-3336.

LIU Y F, ZHANG X M, DING M Y. Implementation of a Multicore Signal Processor for Normali-zed Intercorrelation Grayscale Image Matching[J]. Computer Application, 2011, 31(12):3334-3336.(in Chinese)

JAE C Y, HAN T Y. Fast normalized cross-correlation[J]. Circuits, Systems and Signal Processing, 2009, 28:819-843.

ARIE N, ALLEN T. A new distance measure based on generalized Image Normalized Cross-Correlation for robust video tracking and image recognition[J]. Pattern Recognition Letters, 2013, 34(3).

LEWIS J P, Fast normalized cross-correlation[J]. in Proceedings of Vision Interface, 1995, 120-123.

FRANKLIN C CROW. Summed-area tables for texture mapping[J]. Computer Graphics, 1984, 18(3).

PAUL VIOLA, MICHEAL J JONES, Robust real-time face detection[J]. International Journal of Co-mputer Vision, 2004, 57(2):137-154.

卢宇, 卢荣胜, 郭广平, 等.基于快速归一化算法的拉伸距离动态跟踪测量[J].传感技术学报, 2016, 29(9):1328-1334.

LU Y, LU R S, GUO G P, et al.. Dynamic tracking measurement of stretching distance based on fast normalization algorithm[J]. Journal of sensing technology, 2016, 29(9):1328-1334.(in Chinese)

陈冰倩.基于CPU的归一化互相关算法波前斜率技术研究[D].中国科学院研究生院(光电技术研究所), 2016.

CHEN B Q. Research on wavefront slope based on normalized cross correlation algorithm based on CPU [D]. Graduate University of Chinese Academy of Sciences (Institute of Optoelectronic Technology), 2016.(in Chinese)

Views

236

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

AI问答

Address：No.3888 Dong Nanhu Road, Changchun, Jilin, China Postal code：130033
Tel：0431-86176855 Email：gxjmgc@ciomp.ac.cn
Technical support is provided by Beijing Founder electronics co., LTD 吉ICP备11002662号-17 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰