滑动窗应用场合下的2维几何矩快速算法
摘 要 传统的2维几何矩算法着眼于单个矩形窗口,但当关心的矩形区域在大地图上滑动时,传统算法效率不高。为提高2维几何矩运算速度,提出了一种新的快速迭代算法。由于该算法能够充分利用相邻滑动窗重叠的像素信息,从而可以大大提高2维几何矩的计算效率。该算法所需的乘法和加法运算复杂度完全与滑动窗尺寸N×L无关,都为O(1)。与传统算法的2维几何矩运算复杂度O(N×L)相比,该算法运算速度可以比传统算法提高接近N×L倍。计算机仿真结果验证了该结论。该速度可以满足大多数实时应用的需要。
关键词 几何矩 滑动窗 快速算法 2维
众所周知, (非中心)几何矩( geometricmoment)[1]是重要的图像区域特征描述算子。由于它提出的时间早、形式简单,而且利用几何矩可以快
速构造出许多常用的不变矩函数,如Hu矩[1],Zernike矩[2]等,因此研究几何矩的快速算法具有普遍意义,即一旦几何矩的快速算法确定,其他不变矩的快速算法也随之确定。
2维几何矩在矩形窗口中的定义。国内外对单窗口情况研究比较充分,已提出了众多快速算法,如Delta方法[3]、格林定律法[4]、基于多边形和三角形的方法[5]、基于图像变换的方法[6]以及基于IIR滤波法[7]等。但在地形匹配等诸多应用领域,常常将矩形匹配模板在大图像中滑动,用于提取覆盖区域内的矩信息,该匹配模板就被称作滑动窗。当窗口在图像中滑动时,相邻窗口具有大量的重叠像素,但新窗口内的“新息”比较少。尽管信息内在的冗余性决定了在滑动窗应用场合必定存在矩函数快速算法,但是这个研究领域却鲜有人涉足,仅有Martinez等人做过一些探索[8]。Martinez等人提出几何矩与线性矩( linearmoment)不仅具有对应关系,并且已推导出相邻滑动窗线性矩的迭代更新公式。其算法的乘法复杂度为O(N),加法复杂度为O(1),其中N为窗口尺寸。
Martinez等人的文章晦涩难懂,结论也不便运用。本文对滑动窗应用场合中几何矩快速计算问题进行了新的探索。Canterakis在研究2维Zernike矩快速计算问题时,已得到了2维几何矩的一个变换公式[2],而本文则从Canterakis的研究成果出发,重点研究了其变换公式中一个关键变量在相邻滑动窗中的迭代关系,提出了2维几何矩快速算法,并给出了详细运算流程。通过性能分析可见,该算法的乘法和加法复杂度都与窗口尺寸无关,都为O(1)。但是与传统的单窗口算法相比,该算法需要使用额外的存储空间,其存储量与图像的最短边长成正比。该算法是用空间换取时间,特别适用于存储空间足够,但却关心运算速度的应用场合。计算机仿真表明,该算法的运算速度完全能够满足大多数实时应用的需要。
计算机仿真的目的有以下两个:一是验证计算的正确性;二是展现本文提出的新算法的时间优越性。为此,将该新算法与利用定义式(2)和式(3)在
单窗口内直接计算2维几何矩的传统算法相比较。显然,传统算法的乘法和加法时间复杂度都是O(N×L)。实验中,使用512×512大小的数字地形图作为图像扫描区域。滑动窗大小为N×N,N的取值可变。用本文及传统两种算法计算每个滑动窗内5+4阶的2维几何矩矩阵m5,4,a,b。实验表明,使用两种算法获得的m5,4,a,b在数值上完全相同,从而检验了本文算法的正确性。图3为两种算法在计算单窗口2维几何矩时的平均运算时间随窗口尺寸N变化的关系曲线。根据图3可以定量比较两种算法在运算速度上的差距。如图3所示,当N=250pixe时,使用传统算法需要用时2•297s,而使用本文算法仅需要用时0•13ms。与传统算法相比,本文算法的运算速度提高了4个数量级,接近N2倍。该运算速度显然能够满足大多数实时应用的需要。
本文从信息论角度出发,阐述了在滑动窗应用场合下,必定存在矩函数的快速迭代算法,并且对2维几何矩快速算法进行了研究。与传统的单窗口算法相比,本文提出的快速算法是用存储空间换取运算速度。该算法的乘法和加法复杂度都为O (1),且与窗口尺寸无关,其所需要的存储量与图像的最短边长成正比。计算机仿真验证了算法的正确性,并且表明其运算速度能够满足大多数实时应用的需要。该算法尤其适合在存储空间足够,但关心运算速度的场合中使用。
|
