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

王可東，周俊杰

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

0 引言

3D Zernike 矩因其具有旋轉(zhuǎn)平移尺度變換不變特性，以及適應性強、魯棒性好等優(yōu)點，在模式識別、三維重建等諸多領域已得到廣泛研究[1]. 胡修林等[2]首先提出了將3D Zernike 矩應用于地形匹配的思想，但由于3D Zernike 矩的大計算量問題沒有得到解決，難以滿足實際應用中的實時性要求.

針對3D Zernike 矩計算簡化方面，國內(nèi)外學者已提出了很多有成效的方法. Novotni 等[3]將3D Zernike 矩的計算方法進行整理和完善，形成了經(jīng)典的3D Zernike 矩計算步驟，即歸一化、幾何矩計算、3D Zernike 矩計算. 文中還提出了離線計算組合數(shù)表的方法，在線計算量得到有效降低.

Pozo 等[4]給出了不同于文獻[3]的計算方法，其主要思想是將原計算過程中涉及組合數(shù)的6 重循環(huán)替換為5 個4 重循環(huán). 該方法雖然在理論上減少了計算量，但由于文獻[3]中的組合數(shù)計算過程是離線的，故實用價值較低.

Hosny 等[5]將三維模型歸一化到單位球的內(nèi)接立方體中，通過對稱性，將3D Zernike 矩計算簡化到1/8 的立方體中. 類似地， AL-RAWI[6]利用3D Zernike 偽矩，把三維實體的計算縮減到1/8 的單位球中. 但上述兩種算法主要針對三維實體模型，并不適用于地形匹配. 地形實際上為三維曲面，若按照單位球或立方體進行積分運算，結(jié)果往往得不償失. 對于邊長為N的方形地圖，原本只要計算N2個點，而三維實體則需計算N3/8 個點，時間復雜度增加.

本文從計算地形曲面的3D Zernike 矩的特殊性出發(fā)，研究提高匹配算法實時性的方案，具體內(nèi)容包括兩方面：1)分析3D Zernike 矩的計算過程，提出針對地形計算的快速算法，在不做近似處理的情況下，能大幅降低計算量；2)對比構(gòu)成地形特征向量的奇偶階描述子，從信息包含、地形特征反映能力、抗噪性和旋轉(zhuǎn)適應性等不同方面分析其優(yōu)劣，提出只使用奇數(shù)階描述子的匹配算法，并通過仿真實驗驗證其匹配精度.

1 3D Zernike 定義及計算

文獻[3]提供的3D Zernike 算法[3]，具有旋轉(zhuǎn)不變性的描述子定義為

其中

且有

數(shù)字高程模型(digital elevation model，DEM)為三維空間曲面，在曲面上的點f(X)=1 ，其他位置f(X)=0. 故幾何矩Mr,s,t可簡化為

式中：N為曲面包含的點數(shù)； (xi,yi,zi) 為曲面點的三維空間坐標. 需注意的是，計算幾何矩的數(shù)據(jù)需要歸一化處理.

應用3D Zernike 進行地形匹配時，需要構(gòu)建地形的特征向量，其定義為

在匹配過程中，需要選擇適當?shù)亩攘恐笜藖砗饬扛鱾€特征向量之間的距離. 本文選擇了Camberra 距離，以消除量綱的影響. 其定義為

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

文獻[7]中實驗證明，計算模板大小為80×80，階次取到9 階的3D Zernike 矩，對大部分地形都能實現(xiàn)較高精度的匹配. 為方便后續(xù)研究和討論，本文所提快速算法均采用大小為80×80 的計算模板，但階次選擇10 階.

2.1 坐標分離

在地形匹配過程中，由雷達測距系統(tǒng)得到的相對高程模型(relative elevation model，REM)通?？扇『愣ù笮?，這意味著實際地形圖中的x和y保持不變，描述子Fn,l只是關于地形高程z的函數(shù).

在正式計算3D Zernike 矩之前，還需要對地圖坐標進行歸一化處理，歸一化包括中心化和單位化.中心化是指將坐標原點移至曲面的幾何中心；單位化是指將曲面沿中心放縮至單位球內(nèi).

由于像素坐標中心化后，得到的點集 (xκ,yκ) 與地圖坐標歸一化后的點集 (x,y) 呈比例關系，比例系數(shù)不妨設為 λ .

圖1 給出了坐標轉(zhuǎn)換關系，幾何矩可以表示為

圖1 坐標轉(zhuǎn)換關系

將xrys從幾何矩計算中分離出來，可以簡化2/3 的乘方運算和1/2 的乘法運算. 此時則只需要計算z0，…，z10，然后將結(jié)果與查表得到的66 組進行組合即可. 另外，幾何矩能事先存儲，計算便簡化為286 次與的組合，大幅提升運算效率.

2.2 對稱性

由中心化過程可以得到

并且，采用圓模板或任意對稱模板時，坐標x和y存在對稱性，具體表現(xiàn)為

1)t=0 時

2)t=0且r和s至少一個為奇數(shù)時，有

式(11)可用于簡化幾何矩計算，結(jié)合上文提到的zt與組合，幾何矩的計算分類如下

式(12)的分類可以最大程度上減少向量乘法的運算次數(shù). 利用式(12)，10 階3D Zernike 矩的幾何矩可以減少76 次計算，同時減少44 次求和.

2.3 復數(shù)運算

這樣便將單次復數(shù)乘法拆分為兩次實數(shù)乘法，避免共軛運算.

2.4 小結(jié)

表1 計算復雜度比較

表1 列出了影響計算復雜度的4 個主要指標，除了求和運算外，其他指標都有顯著降低. 盡管快速算法可能會增加普通乘法運算和數(shù)據(jù)查表時間，但整體計算復雜度相對降低.

表2 對比了計算100 幅80×80 像素REM 的10 階3D Zernike 矩所需時間，分別使用傳統(tǒng)算法和本文提出的快速算法(仿真平臺的處理器為R73700X，運行內(nèi)存為32 GB).

表2 算法用時對比

由表2 可知，本文提出的快速算法在計算100 幅80×80 像素REM 的10 階3D Zernike 矩時表現(xiàn)出優(yōu)異性能. 相較傳統(tǒng)算法，快速算法節(jié)省約95%的計算時間. 這一顯著的計算時間節(jié)省不僅源自幾何矩的計算解耦和離線運行，還得益于向量乘法和復數(shù)乘法運算的拆解. 該算法在保持結(jié)果準確性的同時，極大地提升了計算效率，為3D Zernike 矩的實時應用提供了新的可能.

3 描述子奇偶階分析

文獻[7]指出，在一定范圍內(nèi)，匹配精度隨著3D Zernike 矩的階次的增加呈“波動式”提高，具體表現(xiàn)如圖2 所示.

圖2 匹配精度隨3D Zernike 矩階次變化曲線

將描述子Fn,l按n為奇數(shù)或偶數(shù)分為奇數(shù)階和偶數(shù)階，圖中匹配精度在奇數(shù)階處的提升更大. 例如，當3D Zernike 矩從4 階變?yōu)? 階時，匹配成功率提升約60%；當3D Zernike 矩從5 階變?yōu)? 階的時候，匹配率幾乎沒有提升. 該現(xiàn)象說明，第5 階的3D Zernike矩加入比第6 階的3D Zernike 矩加入對比匹配概率提升的效果更為明顯.

由此可知，奇數(shù)階與偶數(shù)階描述子對匹配精度的影響可能存在差異. 接下來，本文將從信息包含、地形特征的反映能力、抗噪性和旋轉(zhuǎn)適應性四個方面對兩類描述子進行對比分析，并以此建立新的特征向量.

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

通過觀察可以發(fā)現(xiàn)如下規(guī)律：

2) 對奇數(shù)階描述子而言，全部Mr,s0滿足式(11)，即高程無關信息為0；而偶數(shù)階中仍包含Mr,s0≠0 的項，影響地形表達能力；

3) 偶數(shù)階描述子當t=0 時，若存在的對稱組合，結(jié)合式(10)可以將其成對消去；

4) 當n=l=m時，奇數(shù)階和偶數(shù)階都為與坐標z無關.

其中1)、2)兩條規(guī)律揭示了奇數(shù)階與偶數(shù)階描述子之間的內(nèi)在差異，規(guī)律3)、4)則可以作為快速算法的補充.

隨著安防產(chǎn)業(yè)技術的日新月異，以往的生態(tài)鏈系統(tǒng)開始逐漸被打破，安防行業(yè)從IT化走向DT化，隨著產(chǎn)品的同質(zhì)化現(xiàn)象凸出，整個行業(yè)也開始從圍繞著產(chǎn)能向用戶需求轉(zhuǎn)變，當前產(chǎn)業(yè)鏈的核心已經(jīng)開始轉(zhuǎn)移，而智能化這是這種跡象的表征。在安防領域，99%以上的數(shù)據(jù)都是非結(jié)構(gòu)化數(shù)據(jù)，這是借助人工智能進行視頻挖掘的價值所在。很多情況下，深度學習算法的突破，有利于完成如下工作：目標識別、物體檢測、場景分割、人物和車輛屬性分析等。深度學習技術的突進讓安防不再停留在解決用戶安全防范的需求，朝著更寬、更廣的領域延伸，視頻被賦予了更多的價值[2]。

3.2 地形特征反映能力

一般而言，REM 中地形起伏的落差要小于REM 的長度或?qū)挾?，即坐標z的值整體上小于x和y.這使得t=0 時的非零幾何矩Mr,s0通常比t≠0 時的幾何矩Mr,s,t大得多. 在非零幾何矩Mr,s0的作用下，偶數(shù)階描述子中有用信息的權重將會被降低，其對地形特征的反映能力下降.

為驗證上述推測，我們在4 幅(大小1197×2397)地形起伏情況不同的數(shù)字高程圖上，每幅隨機選取100 個坐標點作為計算中心，計算模板大小為80×80 的10 階3D Zernike 矩，并對分析結(jié)果. 為了便于后續(xù)描述，將描述子F2,0,F2,2,···,F10,10按 1,2,···,34 依次編號，詳細對應關系如表4 所示.

表4 各階次描述子編號

為直觀顯示不同描述子對地圖上不同點的區(qū)分能力，將每幅圖100 個隨機位置的描述子變化曲線繪制在一起，如圖3～6，橫坐標為描述子編號，縱坐標為描述子的值.

圖4 最大高度差425 m 地區(qū)的描述子值

圖5 最大高度差970 m 地區(qū)的描述子值

圖6 最大高度差1348 m 地區(qū)的描述子方差

對于同一描述子的值，離散程度越大，其對地形特征的區(qū)分能力越好. 在圖3～6 中，隨著描述子的階次增大，描述子的值呈現(xiàn)波動. 與表4 對比可知，處于“波峰”位置的描述子均為偶數(shù)階，而處于“波谷”位置的描述子則均為奇數(shù)階. 在“波峰”位置，描述子線條較為集中，表明整個地圖區(qū)域內(nèi)的描述子值變化不大，反映出較低的地形區(qū)分度；而在“波谷”位置，描述子線條較為分散，說明整個地圖區(qū)域內(nèi)的描述子值變化較大，地形區(qū)分度較高. 換言之，相對于偶數(shù)階描述子，奇數(shù)階描述子具備更強的地形區(qū)分能力.

為了更直觀地呈現(xiàn)奇數(shù)階和偶數(shù)階描述子在地形區(qū)分能力上的差異，本文對描述子的方差進行了統(tǒng)計，并將結(jié)果展示在圖7～10 中. 從圖7～10 可觀察到，奇數(shù)階描述子的方差普遍較大，而偶數(shù)階描述子的方差較小. 然而，隨著地形落差的增加，奇數(shù)階描述子的方差優(yōu)勢逐漸減小.

圖7 最大高度差287 m 地區(qū)的描述子方差

圖8 最大高度差425 m 地區(qū)的描述子方差

圖9 最大高度差970 m 地區(qū)的描述子方差

圖10 最大高度差1348 m 地區(qū)的描述子方差

上述實驗結(jié)果說明，由于非零幾何矩Mr,s0的影響，偶數(shù)階描述子反映地形的能力，尤其是在高度變化較小的地形中表現(xiàn)相對較弱，這與奇數(shù)階描述子相比存在一定的差距.

3.3 抗噪性

3D Zernike 矩自身表現(xiàn)出很好的抗噪性，然而奇數(shù)階和偶數(shù)階描述子之間仍存在一些差異. 就匹配成功率而言，描述子的抗噪性與其區(qū)分度之間存在一定的關聯(lián). 奇數(shù)階描述子由于其更分散的分布，在面對相同大小的擾動時具有更強的抗性. 此外，我們還可以通過分析噪聲對描述子真值的影響來比較這兩種描述子. 前者可以看作是一種相對的抗噪能力，而后者則表示一種絕對的抗噪能力.

圖11 描述子誤差均值

圖12 描述子誤差方差

需要說明的是，上述比較是在地形高度落差較大的基礎上進行的，此時奇數(shù)階和偶數(shù)階受噪聲影響更大. 地形平坦時，雖然偶數(shù)階受噪聲影響會降低，但是此時的偶數(shù)階地形表達能力也會相應減弱，所以最終呈現(xiàn)在匹配成功率上仍然沒有提升.

3.4 旋轉(zhuǎn)適應性

圖13 中提出了地形匹配中的旋轉(zhuǎn)適應性問題，并給出一種圓模板匹配的解決方案. 旋轉(zhuǎn)適應性是指飛行器與地圖夾角變化時，匹配精度受計算模板影響程度. 選擇圓模板匹配能夠消除匹配過程中的區(qū)域不一致，提高匹配精度.

圖13 旋轉(zhuǎn)問題示意圖

由于匹配過程中將使用有轉(zhuǎn)角條件下的特征向量與無轉(zhuǎn)角時的特征向量進行匹配，所以構(gòu)成特征向量的描述子受轉(zhuǎn)動影響越小，正確匹配的概率就越大. 為直觀對比奇偶階描述子的旋轉(zhuǎn)適應性，分別計算某幅地圖上n個不同位置，轉(zhuǎn)角為0°、15°、30°和45°時的描述子. 參考抗噪性分析方法，以0°轉(zhuǎn)角作為真值，研究奇偶階描述子在基準附近的波動情況. 方差計算結(jié)果如圖14～16 所示.

圖14 轉(zhuǎn)角 15° 時

圖15 轉(zhuǎn)角 30° 時

圖16 轉(zhuǎn)角 45° 時

由圖14～16 可知，在有轉(zhuǎn)角情況下，奇數(shù)階描述子波動比偶數(shù)階描述子更小. 將旋轉(zhuǎn)視為特殊的噪聲，則可以類比得到抗旋轉(zhuǎn)性能的分析. 奇數(shù)階描述子在旋轉(zhuǎn)情況下的波動更小，抗旋轉(zhuǎn)性能更強，具有更好的旋轉(zhuǎn)適應性.

3.5 小結(jié)

本節(jié)詳細探討了從信息包含、地形特征反映能力、抗噪性以及旋轉(zhuǎn)適應性的多個角度來比較奇數(shù)階和偶數(shù)階描述子的性能，旨在明確地說明奇數(shù)階描述子在地形匹配領域所具備的優(yōu)勢. 這種對比分析不僅有助于解釋“波動式”上升的匹配精度現(xiàn)象，還為在3D Zernike 矩的階次增加時所觀察到的匹配精度變化提供了深入解釋.

與三維重建不同，地形匹配并不需要對完整的3D Zernike 矩信息進行利用. 基于本節(jié)的論證，我們得出結(jié)論：在考慮降低計算成本和提高匹配精度的雙重目標條件下，可以建議當使用高階3D Zernike 矩進行地形匹配時，僅選取奇數(shù)階描述子來構(gòu)成特征向量. 這種策略的選擇是基于奇數(shù)階描述子在地形特征反映方面的顯著優(yōu)勢，以及其在面對噪聲干擾時表現(xiàn)出更強的抗性，從而更有可能取得更準確和穩(wěn)定的匹配結(jié)果.

4 仿真驗證

本節(jié)主要針對前面提出的快速算法，通過仿真實驗加以驗證.

4.1 奇偶階描述子的性能差異

為驗證奇偶階描述子的性能差異，在地形標準差σh=216.74 m 的地圖上，分別使用全階、奇數(shù)階和偶數(shù)階描述子構(gòu)成特征向量，進行匹配實驗，實驗結(jié)果如表5 所示. 實驗中假定真實位置和匹配位置都位于網(wǎng)格上，定義誤差為0 的匹配為精確匹配，匹配誤差大于1 個網(wǎng)格的匹配為誤匹配.

表5 噪聲標準差5 m 情況下的匹配概率

由表5 可知，在僅采用奇數(shù)階描述子進行地形匹配時，相較于采用完整的全階描述子，匹配精度并未呈下降趨勢，反而呈現(xiàn)出上升的趨勢. 這一實證現(xiàn)象深刻地強調(diào)了奇數(shù)階描述子在地形匹配任務中的顯著潛力與優(yōu)越性.

進一步深入分析只采用偶數(shù)階描述子進行地形匹配的結(jié)果，可以合理推測，偶數(shù)階描述子由于在抗噪性和旋轉(zhuǎn)不變性上的劣勢，進而在全階描述子組合中呈現(xiàn)負面影響. 這種系統(tǒng)的對比分析為選擇恰當?shù)拿枋鲎与A次提供了理論依據(jù)，以實現(xiàn)更為精確和穩(wěn)定的地形匹配.

4.2 算法綜合驗證

對使用3D Zernike 矩快速計算方法和使用奇數(shù)階描述子構(gòu)成特征向量的完整算法的效果進行驗證，此時真實位置不再限定在網(wǎng)格上，但匹配位置仍在網(wǎng)格點上.

圖17 為一幅地形標準差為44.25 m，大小256×256(像素2)的地圖. 我們在其上模擬飛行軌跡，并進行實時地形匹配，其中實時圖測量噪聲取 σn=5 m .圖中實際軌跡與匹配軌跡吻合度良較好. 圖18 給出了X向(橫向)和Y向(縱向)以網(wǎng)格為單位的匹配誤差，匹配基本達到亞網(wǎng)格級.

圖17 飛行軌跡及匹配

圖18 匹配誤差

5 結(jié) 論

本文旨在提升基于3D Zernike 矩的地形匹配算法的實時性能，主要通過兩個關鍵方面的研究工作來達成目標.

其一是通過對3D Zernike 矩計算規(guī)律的深入分析，提出一種高效的計算策略. 該策略包括分離坐標、利用坐標的對稱性以及減少復數(shù)運算等技術，以降低3D Zernike 矩計算過程的復雜度. 與現(xiàn)有算法相比，這一快速算法能夠?qū)⒂嬎銜r間減少超過90%. 這一改進在保證計算精度的前提下，有效地提升了地形匹配算法的實時性能.

其二是針對匹配精度與3D Zernike 矩階次之間呈現(xiàn)“波動式”上升的現(xiàn)象，探討構(gòu)成地形特征向量的奇偶階描述子的性能差異. 通過對信息包含、地形特征反映能力、抗噪性以及旋轉(zhuǎn)適應性等四個關鍵方面的深入分析，凸顯了奇數(shù)階描述子對于地形匹配而言所具備的優(yōu)勢. 在此基礎上，本文提出了一種新的匹配算法，僅利用奇數(shù)階描述子構(gòu)成地形特征向量.經(jīng)過仿真驗證，這一算法不僅減少近一半的計算量，還在匹配精度上取得顯著提升.

本文所提出的快速算法為基于3D Zernike 矩的地形匹配應用帶來了實時性能的提升，為高精度地形輔助導航等領域的應用提供了廣闊的前景. 通過本文的研究成果，在實際應用中有望實現(xiàn)更加高效和準確的三維地形匹配.