基于3D Zernike 矩的快速地形匹配算法

王可东，周俊杰

( 北京航空航天大学宇航学院, 北京 100191 )

0 引言

3D Zernike 矩因其具有旋转平移尺度变换不变特性，以及适应性强、鲁棒性好等优点，在模式识别、三维重建等诸多领域已得到广泛研究[1]. 胡修林等[2]首先提出了将3D Zernike 矩应用于地形匹配的思想，但由于3D Zernike 矩的大计算量问题没有得到解决，难以满足实际应用中的实时性要求.

针对3D Zernike 矩计算简化方面，国内外学者已提出了很多有成效的方法. Novotni 等[3]将3D Zernike 矩的计算方法进行整理和完善，形成了经典的3D Zernike 矩计算步骤，即归一化、几何矩计算、3D Zernike 矩计算. 文中还提出了离线计算组合数表的方法，在线计算量得到有效降低.

Pozo 等[4]给出了不同于文献[3]的计算方法，其主要思想是将原计算过程中涉及组合数的6 重循环替换为5 个4 重循环. 该方法虽然在理论上减少了计算量，但由于文献[3]中的组合数计算过程是离线的，故实用价值较低.

Hosny 等[5]将三维模型归一化到单位球的内接立方体中，通过对称性，将3D Zernike 矩计算简化到1/8 的立方体中. 类似地， AL-RAWI[6]利用3D Zernike 伪矩，把三维实体的计算缩减到1/8 的单位球中. 但上述两种算法主要针对三维实体模型，并不适用于地形匹配. 地形实际上为三维曲面，若按照单位球或立方体进行积分运算，结果往往得不偿失. 对于边长为N的方形地图，原本只要计算N2个点，而三维实体则需计算N3/8 个点，时间复杂度增加.

本文从计算地形曲面的3D Zernike 矩的特殊性出发，研究提高匹配算法实时性的方案，具体内容包括两方面：1)分析3D Zernike 矩的计算过程，提出针对地形计算的快速算法，在不做近似处理的情况下，能大幅降低计算量；2)对比构成地形特征向量的奇偶阶描述子，从信息包含、地形特征反映能力、抗噪性和旋转适应性等不同方面分析其优劣，提出只使用奇数阶描述子的匹配算法，并通过仿真实验验证其匹配精度.

1 3D Zernike 定义及计算

文献[3]提供的3D Zernike 算法[3]，具有旋转不变性的描述子定义为

其中

且有

数字高程模型(digital elevation model，DEM)为三维空间曲面，在曲面上的点f(X)=1 ，其他位置f(X)=0. 故几何矩Mr,s,t可简化为

式中：N为曲面包含的点数； (xi,yi,zi) 为曲面点的三维空间坐标. 需注意的是，计算几何矩的数据需要归一化处理.

应用3D Zernike 进行地形匹配时，需要构建地形的特征向量，其定义为

在匹配过程中，需要选择适当的度量指标来衡量各个特征向量之间的距离. 本文选择了Camberra 距离，以消除量纲的影响. 其定义为

2 地形匹配中3D Zernike 快速计算

文献[7]中实验证明，计算模板大小为80×80，阶次取到9 阶的3D Zernike 矩，对大部分地形都能实现较高精度的匹配. 为方便后续研究和讨论，本文所提快速算法均采用大小为80×80 的计算模板，但阶次选择10 阶.

2.1 坐标分离

在地形匹配过程中，由雷达测距系统得到的相对高程模型(relative elevation model，REM)通常可取恒定大小，这意味着实际地形图中的x和y保持不变，描述子Fn,l只是关于地形高程z的函数.

在正式计算3D Zernike 矩之前，还需要对地图坐标进行归一化处理，归一化包括中心化和单位化.中心化是指将坐标原点移至曲面的几何中心；单位化是指将曲面沿中心放缩至单位球内.

由于像素坐标中心化后，得到的点集 (xκ,yκ) 与地图坐标归一化后的点集 (x,y) 呈比例关系，比例系数不妨设为 λ .

图1 给出了坐标转换关系，几何矩可以表示为

图1 坐标转换关系

将xrys从几何矩计算中分离出来，可以简化2/3 的乘方运算和1/2 的乘法运算. 此时则只需要计算z0，…，z10，然后将结果与查表得到的66 组进行组合即可. 另外，几何矩能事先存储，计算便简化为286 次与的组合，大幅提升运算效率.

2.2 对称性

由中心化过程可以得到

并且，采用圆模板或任意对称模板时，坐标x和y存在对称性，具体表现为

1)t=0 时

2)t=0且r和s至少一个为奇数时，有

式(11)可用于简化几何矩计算，结合上文提到的zt与组合，几何矩的计算分类如下

式(12)的分类可以最大程度上减少向量乘法的运算次数. 利用式(12)，10 阶3D Zernike 矩的几何矩可以减少76 次计算，同时减少44 次求和.

2.3 复数运算

这样便将单次复数乘法拆分为两次实数乘法，避免共轭运算.

2.4 小结

表1 计算复杂度比较

表1 列出了影响计算复杂度的4 个主要指标，除了求和运算外，其他指标都有显著降低. 尽管快速算法可能会增加普通乘法运算和数据查表时间，但整体计算复杂度相对降低.

表2 对比了计算100 幅80×80 像素REM 的10 阶3D Zernike 矩所需时间，分别使用传统算法和本文提出的快速算法(仿真平台的处理器为R73700X，运行内存为32 GB).

表2 算法用时对比

由表2 可知，本文提出的快速算法在计算100 幅80×80 像素REM 的10 阶3D Zernike 矩时表现出优异性能. 相较传统算法，快速算法节省约95%的计算时间. 这一显著的计算时间节省不仅源自几何矩的计算解耦和离线运行，还得益于向量乘法和复数乘法运算的拆解. 该算法在保持结果准确性的同时，极大地提升了计算效率，为3D Zernike 矩的实时应用提供了新的可能.

3 描述子奇偶阶分析

文献[7]指出，在一定范围内，匹配精度随着3D Zernike 矩的阶次的增加呈“波动式”提高，具体表现如图2 所示.

图2 匹配精度随3D Zernike 矩阶次变化曲线

将描述子Fn,l按n为奇数或偶数分为奇数阶和偶数阶，图中匹配精度在奇数阶处的提升更大. 例如，当3D Zernike 矩从4 阶变为5 阶时，匹配成功率提升约60%；当3D Zernike 矩从5 阶变为6 阶的时候，匹配率几乎没有提升. 该现象说明，第5 阶的3D Zernike矩加入比第6 阶的3D Zernike 矩加入对比匹配概率提升的效果更为明显.

由此可知，奇数阶与偶数阶描述子对匹配精度的影响可能存在差异. 接下来，本文将从信息包含、地形特征的反映能力、抗噪性和旋转适应性四个方面对两类描述子进行对比分析，并以此建立新的特征向量.

3.1 信息包含

从信息的角度看，只有当t≠0 时，几何矩Mr,s,t中才包含与地形相关的有用信息.是描述子计算的基本单元，为分析几何矩Mrs0对描述子的影响，可将展开，写成不同阶次几何矩的线性组合. 例如：

表3 与 r,s,t 组合的对应关系

表3 与 r,s,t 组合的对应关系

Ωmn,lrstΩmn,lrst 000010 Ω02,0 0002 2010 0320 2000 02 Ω13,1 1100 02 Ω02,2020120200210 Ω12,2 1001 1100 0033 020Ω03,3021 Ω22,2110201200012 001030 Ω03,1 0002 31 Ω13,3 1102 20201210 010300 Ω33,3 1003 20Ω23,3 0121 11100201

通过观察可以发现如下规律：

2) 对奇数阶描述子而言，全部Mr,s0满足式(11)，即高程无关信息为0；而偶数阶中仍包含Mr,s0≠0 的项，影响地形表达能力；

3) 偶数阶描述子当t=0 时，若存在的对称组合，结合式(10)可以将其成对消去；

4) 当n=l=m时，奇数阶和偶数阶都为与坐标z无关.

其中1)、2)两条规律揭示了奇数阶与偶数阶描述子之间的内在差异，规律3)、4)则可以作为快速算法的补充.

随着安防产业技术的日新月异，以往的生态链系统开始逐渐被打破，安防行业从IT化走向DT化，随着产品的同质化现象凸出，整个行业也开始从围绕着产能向用户需求转变，当前产业链的核心已经开始转移，而智能化这是这种迹象的表征。在安防领域，99%以上的数据都是非结构化数据，这是借助人工智能进行视频挖掘的价值所在。很多情况下，深度学习算法的突破，有利于完成如下工作：目标识别、物体检测、场景分割、人物和车辆属性分析等。深度学习技术的突进让安防不再停留在解决用户安全防范的需求，朝着更宽、更广的领域延伸，视频被赋予了更多的价值[2]。

3.2 地形特征反映能力

一般而言，REM 中地形起伏的落差要小于REM 的长度或宽度，即坐标z的值整体上小于x和y.这使得t=0 时的非零几何矩Mr,s0通常比t≠0 时的几何矩Mr,s,t大得多. 在非零几何矩Mr,s0的作用下，偶数阶描述子中有用信息的权重将会被降低，其对地形特征的反映能力下降.

为验证上述推测，我们在4 幅(大小1197×2397)地形起伏情况不同的数字高程图上，每幅随机选取100 个坐标点作为计算中心，计算模板大小为80×80 的10 阶3D Zernike 矩，并对分析结果. 为了便于后续描述，将描述子F2,0,F2,2,···,F10,10按 1,2,···,34 依次编号，详细对应关系如表4 所示.

表4 各阶次描述子编号

为直观显示不同描述子对地图上不同点的区分能力，将每幅图100 个随机位置的描述子变化曲线绘制在一起，如图3～6，横坐标为描述子编号，纵坐标为描述子的值.

图4 最大高度差425 m 地区的描述子值

图5 最大高度差970 m 地区的描述子值

图6 最大高度差1348 m 地区的描述子方差

对于同一描述子的值，离散程度越大，其对地形特征的区分能力越好. 在图3～6 中，随着描述子的阶次增大，描述子的值呈现波动. 与表4 对比可知，处于“波峰”位置的描述子均为偶数阶，而处于“波谷”位置的描述子则均为奇数阶. 在“波峰”位置，描述子线条较为集中，表明整个地图区域内的描述子值变化不大，反映出较低的地形区分度；而在“波谷”位置，描述子线条较为分散，说明整个地图区域内的描述子值变化较大，地形区分度较高. 换言之，相对于偶数阶描述子，奇数阶描述子具备更强的地形区分能力.

为了更直观地呈现奇数阶和偶数阶描述子在地形区分能力上的差异，本文对描述子的方差进行了统计，并将结果展示在图7～10 中. 从图7～10 可观察到，奇数阶描述子的方差普遍较大，而偶数阶描述子的方差较小. 然而，随着地形落差的增加，奇数阶描述子的方差优势逐渐减小.

图7 最大高度差287 m 地区的描述子方差

图8 最大高度差425 m 地区的描述子方差

图9 最大高度差970 m 地区的描述子方差

图10 最大高度差1348 m 地区的描述子方差

上述实验结果说明，由于非零几何矩Mr,s0的影响，偶数阶描述子反映地形的能力，尤其是在高度变化较小的地形中表现相对较弱，这与奇数阶描述子相比存在一定的差距.

3.3 抗噪性

3D Zernike 矩自身表现出很好的抗噪性，然而奇数阶和偶数阶描述子之间仍存在一些差异. 就匹配成功率而言，描述子的抗噪性与其区分度之间存在一定的关联. 奇数阶描述子由于其更分散的分布，在面对相同大小的扰动时具有更强的抗性. 此外，我们还可以通过分析噪声对描述子真值的影响来比较这两种描述子. 前者可以看作是一种相对的抗噪能力，而后者则表示一种绝对的抗噪能力.

图11 描述子误差均值

图12 描述子误差方差

需要说明的是，上述比较是在地形高度落差较大的基础上进行的，此时奇数阶和偶数阶受噪声影响更大. 地形平坦时，虽然偶数阶受噪声影响会降低，但是此时的偶数阶地形表达能力也会相应减弱，所以最终呈现在匹配成功率上仍然没有提升.

3.4 旋转适应性

图13 中提出了地形匹配中的旋转适应性问题，并给出一种圆模板匹配的解决方案. 旋转适应性是指飞行器与地图夹角变化时，匹配精度受计算模板影响程度. 选择圆模板匹配能够消除匹配过程中的区域不一致，提高匹配精度.

图13 旋转问题示意图

由于匹配过程中将使用有转角条件下的特征向量与无转角时的特征向量进行匹配，所以构成特征向量的描述子受转动影响越小，正确匹配的概率就越大. 为直观对比奇偶阶描述子的旋转适应性，分别计算某幅地图上n个不同位置，转角为0°、15°、30°和45°时的描述子. 参考抗噪性分析方法，以0°转角作为真值，研究奇偶阶描述子在基准附近的波动情况. 方差计算结果如图14～16 所示.

图14 转角 15° 时

图15 转角 30° 时

图16 转角 45° 时

由图14～16 可知，在有转角情况下，奇数阶描述子波动比偶数阶描述子更小. 将旋转视为特殊的噪声，则可以类比得到抗旋转性能的分析. 奇数阶描述子在旋转情况下的波动更小，抗旋转性能更强，具有更好的旋转适应性.

3.5 小结

本节详细探讨了从信息包含、地形特征反映能力、抗噪性以及旋转适应性的多个角度来比较奇数阶和偶数阶描述子的性能，旨在明确地说明奇数阶描述子在地形匹配领域所具备的优势. 这种对比分析不仅有助于解释“波动式”上升的匹配精度现象，还为在3D Zernike 矩的阶次增加时所观察到的匹配精度变化提供了深入解释.

与三维重建不同，地形匹配并不需要对完整的3D Zernike 矩信息进行利用. 基于本节的论证，我们得出结论：在考虑降低计算成本和提高匹配精度的双重目标条件下，可以建议当使用高阶3D Zernike 矩进行地形匹配时，仅选取奇数阶描述子来构成特征向量. 这种策略的选择是基于奇数阶描述子在地形特征反映方面的显著优势，以及其在面对噪声干扰时表现出更强的抗性，从而更有可能取得更准确和稳定的匹配结果.

4 仿真验证

本节主要针对前面提出的快速算法，通过仿真实验加以验证.

4.1 奇偶阶描述子的性能差异

为验证奇偶阶描述子的性能差异，在地形标准差σh=216.74 m 的地图上，分别使用全阶、奇数阶和偶数阶描述子构成特征向量，进行匹配实验，实验结果如表5 所示. 实验中假定真实位置和匹配位置都位于网格上，定义误差为0 的匹配为精确匹配，匹配误差大于1 个网格的匹配为误匹配.

表5 噪声标准差5 m 情况下的匹配概率

由表5 可知，在仅采用奇数阶描述子进行地形匹配时，相较于采用完整的全阶描述子，匹配精度并未呈下降趋势，反而呈现出上升的趋势. 这一实证现象深刻地强调了奇数阶描述子在地形匹配任务中的显著潜力与优越性.

进一步深入分析只采用偶数阶描述子进行地形匹配的结果，可以合理推测，偶数阶描述子由于在抗噪性和旋转不变性上的劣势，进而在全阶描述子组合中呈现负面影响. 这种系统的对比分析为选择恰当的描述子阶次提供了理论依据，以实现更为精确和稳定的地形匹配.

4.2 算法综合验证

对使用3D Zernike 矩快速计算方法和使用奇数阶描述子构成特征向量的完整算法的效果进行验证，此时真实位置不再限定在网格上，但匹配位置仍在网格点上.

图17 为一幅地形标准差为44.25 m，大小256×256(像素2)的地图. 我们在其上模拟飞行轨迹，并进行实时地形匹配，其中实时图测量噪声取 σn=5 m .图中实际轨迹与匹配轨迹吻合度良较好. 图18 给出了X向(横向)和Y向(纵向)以网格为单位的匹配误差，匹配基本达到亚网格级.

图17 飞行轨迹及匹配

图18 匹配误差

5 结 论

本文旨在提升基于3D Zernike 矩的地形匹配算法的实时性能，主要通过两个关键方面的研究工作来达成目标.

其一是通过对3D Zernike 矩计算规律的深入分析，提出一种高效的计算策略. 该策略包括分离坐标、利用坐标的对称性以及减少复数运算等技术，以降低3D Zernike 矩计算过程的复杂度. 与现有算法相比，这一快速算法能够将计算时间减少超过90%. 这一改进在保证计算精度的前提下，有效地提升了地形匹配算法的实时性能.

其二是针对匹配精度与3D Zernike 矩阶次之间呈现“波动式”上升的现象，探讨构成地形特征向量的奇偶阶描述子的性能差异. 通过对信息包含、地形特征反映能力、抗噪性以及旋转适应性等四个关键方面的深入分析，凸显了奇数阶描述子对于地形匹配而言所具备的优势. 在此基础上，本文提出了一种新的匹配算法，仅利用奇数阶描述子构成地形特征向量.经过仿真验证，这一算法不仅减少近一半的计算量，还在匹配精度上取得显著提升.

本文所提出的快速算法为基于3D Zernike 矩的地形匹配应用带来了实时性能的提升，为高精度地形辅助导航等领域的应用提供了广阔的前景. 通过本文的研究成果，在实际应用中有望实现更加高效和准确的三维地形匹配.