王可東,周俊杰
( 北京航空航天大學(xué)宇航學(xué)院, 北京 100191 )
3D Zernike 矩因其具有旋轉(zhuǎn)平移尺度變換不變特性,以及適應(yīng)性強(qiáng)、魯棒性好等優(yōu)點(diǎn),在模式識(shí)別、三維重建等諸多領(lǐng)域已得到廣泛研究[1]. 胡修林等[2]首先提出了將3D Zernike 矩應(yīng)用于地形匹配的思想,但由于3D Zernike 矩的大計(jì)算量問題沒有得到解決,難以滿足實(shí)際應(yīng)用中的實(shí)時(shí)性要求.
針對(duì)3D Zernike 矩計(jì)算簡化方面,國內(nèi)外學(xué)者已提出了很多有成效的方法. Novotni 等[3]將3D Zernike 矩的計(jì)算方法進(jìn)行整理和完善,形成了經(jīng)典的3D Zernike 矩計(jì)算步驟,即歸一化、幾何矩計(jì)算、3D Zernike 矩計(jì)算. 文中還提出了離線計(jì)算組合數(shù)表的方法,在線計(jì)算量得到有效降低.
Pozo 等[4]給出了不同于文獻(xiàn)[3]的計(jì)算方法,其主要思想是將原計(jì)算過程中涉及組合數(shù)的6 重循環(huán)替換為5 個(gè)4 重循環(huán). 該方法雖然在理論上減少了計(jì)算量,但由于文獻(xiàn)[3]中的組合數(shù)計(jì)算過程是離線的,故實(shí)用價(jià)值較低.
Hosny 等[5]將三維模型歸一化到單位球的內(nèi)接立方體中,通過對(duì)稱性,將3D Zernike 矩計(jì)算簡化到1/8 的立方體中. 類似地, AL-RAWI[6]利用3D Zernike 偽矩,把三維實(shí)體的計(jì)算縮減到1/8 的單位球中. 但上述兩種算法主要針對(duì)三維實(shí)體模型,并不適用于地形匹配. 地形實(shí)際上為三維曲面,若按照單位球或立方體進(jìn)行積分運(yùn)算,結(jié)果往往得不償失. 對(duì)于邊長為N的方形地圖,原本只要計(jì)算N2個(gè)點(diǎn),而三維實(shí)體則需計(jì)算N3/8 個(gè)點(diǎn),時(shí)間復(fù)雜度增加.
本文從計(jì)算地形曲面的3D Zernike 矩的特殊性出發(fā),研究提高匹配算法實(shí)時(shí)性的方案,具體內(nèi)容包括兩方面:1)分析3D Zernike 矩的計(jì)算過程,提出針對(duì)地形計(jì)算的快速算法,在不做近似處理的情況下,能大幅降低計(jì)算量;2)對(duì)比構(gòu)成地形特征向量的奇偶階描述子,從信息包含、地形特征反映能力、抗噪性和旋轉(zhuǎn)適應(yīng)性等不同方面分析其優(yōu)劣,提出只使用奇數(shù)階描述子的匹配算法,并通過仿真實(shí)驗(yàn)驗(yàn)證其匹配精度.
文獻(xiàn)[3]提供的3D Zernike 算法[3],具有旋轉(zhuǎn)不變性的描述子定義為
其中
且有
數(shù)字高程模型(digital elevation model,DEM)為三維空間曲面,在曲面上的點(diǎn)f(X)=1 ,其他位置f(X)=0. 故幾何矩Mr,s,t可簡化為
式中:N為曲面包含的點(diǎn)數(shù); (xi,yi,zi) 為曲面點(diǎn)的三維空間坐標(biāo). 需注意的是,計(jì)算幾何矩的數(shù)據(jù)需要?dú)w一化處理.
應(yīng)用3D Zernike 進(jìn)行地形匹配時(shí),需要構(gòu)建地形的特征向量,其定義為
在匹配過程中,需要選擇適當(dāng)?shù)亩攘恐笜?biāo)來衡量各個(gè)特征向量之間的距離. 本文選擇了Camberra 距離,以消除量綱的影響. 其定義為
文獻(xiàn)[7]中實(shí)驗(yàn)證明,計(jì)算模板大小為80×80,階次取到9 階的3D Zernike 矩,對(duì)大部分地形都能實(shí)現(xiàn)較高精度的匹配. 為方便后續(xù)研究和討論,本文所提快速算法均采用大小為80×80 的計(jì)算模板,但階次選擇10 階.
在地形匹配過程中,由雷達(dá)測距系統(tǒng)得到的相對(duì)高程模型(relative elevation model,REM)通??扇『愣ù笮。@意味著實(shí)際地形圖中的x和y保持不變,描述子Fn,l只是關(guān)于地形高程z的函數(shù).
在正式計(jì)算3D Zernike 矩之前,還需要對(duì)地圖坐標(biāo)進(jìn)行歸一化處理,歸一化包括中心化和單位化.中心化是指將坐標(biāo)原點(diǎn)移至曲面的幾何中心;單位化是指將曲面沿中心放縮至單位球內(nèi).
由于像素坐標(biāo)中心化后,得到的點(diǎn)集 (xκ,yκ) 與地圖坐標(biāo)歸一化后的點(diǎn)集 (x,y) 呈比例關(guān)系,比例系數(shù)不妨設(shè)為 λ .
圖1 給出了坐標(biāo)轉(zhuǎn)換關(guān)系,幾何矩可以表示為
圖1 坐標(biāo)轉(zhuǎn)換關(guān)系
將xrys從幾何矩計(jì)算中分離出來,可以簡化2/3 的乘方運(yùn)算和1/2 的乘法運(yùn)算. 此時(shí)則只需要計(jì)算z0,…,z10,然后將結(jié)果與查表得到的66 組進(jìn)行組合即可. 另外,幾何矩能事先存儲(chǔ),計(jì)算便簡化為286 次與的組合,大幅提升運(yùn)算效率.
由中心化過程可以得到
并且,采用圓模板或任意對(duì)稱模板時(shí),坐標(biāo)x和y存在對(duì)稱性,具體表現(xiàn)為
1)t=0 時(shí)
2)t=0且r和s至少一個(gè)為奇數(shù)時(shí),有
式(11)可用于簡化幾何矩計(jì)算,結(jié)合上文提到的zt與組合,幾何矩的計(jì)算分類如下
式(12)的分類可以最大程度上減少向量乘法的運(yùn)算次數(shù). 利用式(12),10 階3D Zernike 矩的幾何矩可以減少76 次計(jì)算,同時(shí)減少44 次求和.
這樣便將單次復(fù)數(shù)乘法拆分為兩次實(shí)數(shù)乘法,避免共軛運(yùn)算.
表1 計(jì)算復(fù)雜度比較
表1 列出了影響計(jì)算復(fù)雜度的4 個(gè)主要指標(biāo),除了求和運(yùn)算外,其他指標(biāo)都有顯著降低. 盡管快速算法可能會(huì)增加普通乘法運(yùn)算和數(shù)據(jù)查表時(shí)間,但整體計(jì)算復(fù)雜度相對(duì)降低.
表2 對(duì)比了計(jì)算100 幅80×80 像素REM 的10 階3D Zernike 矩所需時(shí)間,分別使用傳統(tǒng)算法和本文提出的快速算法(仿真平臺(tái)的處理器為R73700X,運(yùn)行內(nèi)存為32 GB).
表2 算法用時(shí)對(duì)比
由表2 可知,本文提出的快速算法在計(jì)算100 幅80×80 像素REM 的10 階3D Zernike 矩時(shí)表現(xiàn)出優(yōu)異性能. 相較傳統(tǒng)算法,快速算法節(jié)省約95%的計(jì)算時(shí)間. 這一顯著的計(jì)算時(shí)間節(jié)省不僅源自幾何矩的計(jì)算解耦和離線運(yùn)行,還得益于向量乘法和復(fù)數(shù)乘法運(yùn)算的拆解. 該算法在保持結(jié)果準(zhǔn)確性的同時(shí),極大地提升了計(jì)算效率,為3D Zernike 矩的實(shí)時(shí)應(yīng)用提供了新的可能.
文獻(xiàn)[7]指出,在一定范圍內(nèi),匹配精度隨著3D Zernike 矩的階次的增加呈“波動(dòng)式”提高,具體表現(xiàn)如圖2 所示.
圖2 匹配精度隨3D Zernike 矩階次變化曲線
將描述子Fn,l按n為奇數(shù)或偶數(shù)分為奇數(shù)階和偶數(shù)階,圖中匹配精度在奇數(shù)階處的提升更大. 例如,當(dāng)3D Zernike 矩從4 階變?yōu)? 階時(shí),匹配成功率提升約60%;當(dāng)3D Zernike 矩從5 階變?yōu)? 階的時(shí)候,匹配率幾乎沒有提升. 該現(xiàn)象說明,第5 階的3D Zernike矩加入比第6 階的3D Zernike 矩加入對(duì)比匹配概率提升的效果更為明顯.
由此可知,奇數(shù)階與偶數(shù)階描述子對(duì)匹配精度的影響可能存在差異. 接下來,本文將從信息包含、地形特征的反映能力、抗噪性和旋轉(zhuǎn)適應(yīng)性四個(gè)方面對(duì)兩類描述子進(jìn)行對(duì)比分析,并以此建立新的特征向量.
從信息的角度看,只有當(dāng)t≠0 時(shí),幾何矩Mr,s,t中才包含與地形相關(guān)的有用信息.是描述子計(jì)算的基本單元,為分析幾何矩Mrs0對(duì)描述子的影響,可將展開,寫成不同階次幾何矩的線性組合. 例如:
表3 與 r,s,t 組合的對(duì)應(yīng)關(guān)系
表3 與 r,s,t 組合的對(duì)應(yīng)關(guān)系
Ω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) 對(duì)奇數(shù)階描述子而言,全部Mr,s0滿足式(11),即高程無關(guān)信息為0;而偶數(shù)階中仍包含Mr,s0≠0 的項(xiàng),影響地形表達(dá)能力;
3) 偶數(shù)階描述子當(dāng)t=0 時(shí),若存在的對(duì)稱組合,結(jié)合式(10)可以將其成對(duì)消去;
4) 當(dāng)n=l=m時(shí),奇數(shù)階和偶數(shù)階都為與坐標(biāo)z無關(guān).
其中1)、2)兩條規(guī)律揭示了奇數(shù)階與偶數(shù)階描述子之間的內(nèi)在差異,規(guī)律3)、4)則可以作為快速算法的補(bǔ)充.
隨著安防產(chǎn)業(yè)技術(shù)的日新月異,以往的生態(tài)鏈系統(tǒng)開始逐漸被打破,安防行業(yè)從IT化走向DT化,隨著產(chǎn)品的同質(zhì)化現(xiàn)象凸出,整個(gè)行業(yè)也開始從圍繞著產(chǎn)能向用戶需求轉(zhuǎn)變,當(dāng)前產(chǎn)業(yè)鏈的核心已經(jīng)開始轉(zhuǎn)移,而智能化這是這種跡象的表征。在安防領(lǐng)域,99%以上的數(shù)據(jù)都是非結(jié)構(gòu)化數(shù)據(jù),這是借助人工智能進(jìn)行視頻挖掘的價(jià)值所在。很多情況下,深度學(xué)習(xí)算法的突破,有利于完成如下工作:目標(biāo)識(shí)別、物體檢測、場景分割、人物和車輛屬性分析等。深度學(xué)習(xí)技術(shù)的突進(jìn)讓安防不再停留在解決用戶安全防范的需求,朝著更寬、更廣的領(lǐng)域延伸,視頻被賦予了更多的價(jià)值[2]。
一般而言,REM 中地形起伏的落差要小于REM 的長度或?qū)挾龋醋鴺?biāo)z的值整體上小于x和y.這使得t=0 時(shí)的非零幾何矩Mr,s0通常比t≠0 時(shí)的幾何矩Mr,s,t大得多. 在非零幾何矩Mr,s0的作用下,偶數(shù)階描述子中有用信息的權(quán)重將會(huì)被降低,其對(duì)地形特征的反映能力下降.
為驗(yàn)證上述推測,我們?cè)? 幅(大小1197×2397)地形起伏情況不同的數(shù)字高程圖上,每幅隨機(jī)選取100 個(gè)坐標(biāo)點(diǎn)作為計(jì)算中心,計(jì)算模板大小為80×80 的10 階3D Zernike 矩,并對(duì)分析結(jié)果. 為了便于后續(xù)描述,將描述子F2,0,F2,2,···,F10,10按 1,2,···,34 依次編號(hào),詳細(xì)對(duì)應(yīng)關(guān)系如表4 所示.
表4 各階次描述子編號(hào)
為直觀顯示不同描述子對(duì)地圖上不同點(diǎn)的區(qū)分能力,將每幅圖100 個(gè)隨機(jī)位置的描述子變化曲線繪制在一起,如圖3~6,橫坐標(biāo)為描述子編號(hào),縱坐標(biāo)為描述子的值.
圖4 最大高度差425 m 地區(qū)的描述子值
圖5 最大高度差970 m 地區(qū)的描述子值
圖6 最大高度差1348 m 地區(qū)的描述子方差
對(duì)于同一描述子的值,離散程度越大,其對(duì)地形特征的區(qū)分能力越好. 在圖3~6 中,隨著描述子的階次增大,描述子的值呈現(xiàn)波動(dòng). 與表4 對(duì)比可知,處于“波峰”位置的描述子均為偶數(shù)階,而處于“波谷”位置的描述子則均為奇數(shù)階. 在“波峰”位置,描述子線條較為集中,表明整個(gè)地圖區(qū)域內(nèi)的描述子值變化不大,反映出較低的地形區(qū)分度;而在“波谷”位置,描述子線條較為分散,說明整個(gè)地圖區(qū)域內(nèi)的描述子值變化較大,地形區(qū)分度較高. 換言之,相對(duì)于偶數(shù)階描述子,奇數(shù)階描述子具備更強(qiáng)的地形區(qū)分能力.
為了更直觀地呈現(xiàn)奇數(shù)階和偶數(shù)階描述子在地形區(qū)分能力上的差異,本文對(duì)描述子的方差進(jìn)行了統(tǒng)計(jì),并將結(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ū)的描述子方差
上述實(shí)驗(yàn)結(jié)果說明,由于非零幾何矩Mr,s0的影響,偶數(shù)階描述子反映地形的能力,尤其是在高度變化較小的地形中表現(xiàn)相對(duì)較弱,這與奇數(shù)階描述子相比存在一定的差距.
3D Zernike 矩自身表現(xiàn)出很好的抗噪性,然而奇數(shù)階和偶數(shù)階描述子之間仍存在一些差異. 就匹配成功率而言,描述子的抗噪性與其區(qū)分度之間存在一定的關(guān)聯(lián). 奇數(shù)階描述子由于其更分散的分布,在面對(duì)相同大小的擾動(dòng)時(shí)具有更強(qiáng)的抗性. 此外,我們還可以通過分析噪聲對(duì)描述子真值的影響來比較這兩種描述子. 前者可以看作是一種相對(duì)的抗噪能力,而后者則表示一種絕對(duì)的抗噪能力.
圖11 描述子誤差均值
圖12 描述子誤差方差
需要說明的是,上述比較是在地形高度落差較大的基礎(chǔ)上進(jìn)行的,此時(shí)奇數(shù)階和偶數(shù)階受噪聲影響更大. 地形平坦時(shí),雖然偶數(shù)階受噪聲影響會(huì)降低,但是此時(shí)的偶數(shù)階地形表達(dá)能力也會(huì)相應(yīng)減弱,所以最終呈現(xiàn)在匹配成功率上仍然沒有提升.
圖13 中提出了地形匹配中的旋轉(zhuǎn)適應(yīng)性問題,并給出一種圓模板匹配的解決方案. 旋轉(zhuǎn)適應(yīng)性是指飛行器與地圖夾角變化時(shí),匹配精度受計(jì)算模板影響程度. 選擇圓模板匹配能夠消除匹配過程中的區(qū)域不一致,提高匹配精度.
圖13 旋轉(zhuǎn)問題示意圖
由于匹配過程中將使用有轉(zhuǎn)角條件下的特征向量與無轉(zhuǎn)角時(shí)的特征向量進(jìn)行匹配,所以構(gòu)成特征向量的描述子受轉(zhuǎn)動(dòng)影響越小,正確匹配的概率就越大. 為直觀對(duì)比奇偶階描述子的旋轉(zhuǎn)適應(yīng)性,分別計(jì)算某幅地圖上n個(gè)不同位置,轉(zhuǎn)角為0°、15°、30°和45°時(shí)的描述子. 參考抗噪性分析方法,以0°轉(zhuǎn)角作為真值,研究奇偶階描述子在基準(zhǔn)附近的波動(dòng)情況. 方差計(jì)算結(jié)果如圖14~16 所示.
圖14 轉(zhuǎn)角 15° 時(shí)
圖15 轉(zhuǎn)角 30° 時(shí)
圖16 轉(zhuǎn)角 45° 時(shí)
由圖14~16 可知,在有轉(zhuǎn)角情況下,奇數(shù)階描述子波動(dòng)比偶數(shù)階描述子更小. 將旋轉(zhuǎn)視為特殊的噪聲,則可以類比得到抗旋轉(zhuǎn)性能的分析. 奇數(shù)階描述子在旋轉(zhuǎn)情況下的波動(dòng)更小,抗旋轉(zhuǎn)性能更強(qiáng),具有更好的旋轉(zhuǎn)適應(yīng)性.
本節(jié)詳細(xì)探討了從信息包含、地形特征反映能力、抗噪性以及旋轉(zhuǎn)適應(yīng)性的多個(gè)角度來比較奇數(shù)階和偶數(shù)階描述子的性能,旨在明確地說明奇數(shù)階描述子在地形匹配領(lǐng)域所具備的優(yōu)勢. 這種對(duì)比分析不僅有助于解釋“波動(dòng)式”上升的匹配精度現(xiàn)象,還為在3D Zernike 矩的階次增加時(shí)所觀察到的匹配精度變化提供了深入解釋.
與三維重建不同,地形匹配并不需要對(duì)完整的3D Zernike 矩信息進(jìn)行利用. 基于本節(jié)的論證,我們得出結(jié)論:在考慮降低計(jì)算成本和提高匹配精度的雙重目標(biāo)條件下,可以建議當(dāng)使用高階3D Zernike 矩進(jìn)行地形匹配時(shí),僅選取奇數(shù)階描述子來構(gòu)成特征向量. 這種策略的選擇是基于奇數(shù)階描述子在地形特征反映方面的顯著優(yōu)勢,以及其在面對(duì)噪聲干擾時(shí)表現(xiàn)出更強(qiáng)的抗性,從而更有可能取得更準(zhǔn)確和穩(wěn)定的匹配結(jié)果.
本節(jié)主要針對(duì)前面提出的快速算法,通過仿真實(shí)驗(yàn)加以驗(yàn)證.
為驗(yàn)證奇偶階描述子的性能差異,在地形標(biāo)準(zhǔn)差σh=216.74 m 的地圖上,分別使用全階、奇數(shù)階和偶數(shù)階描述子構(gòu)成特征向量,進(jìn)行匹配實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表5 所示. 實(shí)驗(yàn)中假定真實(shí)位置和匹配位置都位于網(wǎng)格上,定義誤差為0 的匹配為精確匹配,匹配誤差大于1 個(gè)網(wǎng)格的匹配為誤匹配.
表5 噪聲標(biāo)準(zhǔn)差5 m 情況下的匹配概率
由表5 可知,在僅采用奇數(shù)階描述子進(jìn)行地形匹配時(shí),相較于采用完整的全階描述子,匹配精度并未呈下降趨勢,反而呈現(xiàn)出上升的趨勢. 這一實(shí)證現(xiàn)象深刻地強(qiáng)調(diào)了奇數(shù)階描述子在地形匹配任務(wù)中的顯著潛力與優(yōu)越性.
進(jìn)一步深入分析只采用偶數(shù)階描述子進(jìn)行地形匹配的結(jié)果,可以合理推測,偶數(shù)階描述子由于在抗噪性和旋轉(zhuǎn)不變性上的劣勢,進(jìn)而在全階描述子組合中呈現(xiàn)負(fù)面影響. 這種系統(tǒng)的對(duì)比分析為選擇恰當(dāng)?shù)拿枋鲎与A次提供了理論依據(jù),以實(shí)現(xiàn)更為精確和穩(wěn)定的地形匹配.
對(duì)使用3D Zernike 矩快速計(jì)算方法和使用奇數(shù)階描述子構(gòu)成特征向量的完整算法的效果進(jìn)行驗(yàn)證,此時(shí)真實(shí)位置不再限定在網(wǎng)格上,但匹配位置仍在網(wǎng)格點(diǎn)上.
圖17 為一幅地形標(biāo)準(zhǔn)差為44.25 m,大小256×256(像素2)的地圖. 我們?cè)谄渖夏M飛行軌跡,并進(jìn)行實(shí)時(shí)地形匹配,其中實(shí)時(shí)圖測量噪聲取 σn=5 m .圖中實(shí)際軌跡與匹配軌跡吻合度良較好. 圖18 給出了X向(橫向)和Y向(縱向)以網(wǎng)格為單位的匹配誤差,匹配基本達(dá)到亞網(wǎng)格級(jí).
圖17 飛行軌跡及匹配
圖18 匹配誤差
本文旨在提升基于3D Zernike 矩的地形匹配算法的實(shí)時(shí)性能,主要通過兩個(gè)關(guān)鍵方面的研究工作來達(dá)成目標(biāo).
其一是通過對(duì)3D Zernike 矩計(jì)算規(guī)律的深入分析,提出一種高效的計(jì)算策略. 該策略包括分離坐標(biāo)、利用坐標(biāo)的對(duì)稱性以及減少復(fù)數(shù)運(yùn)算等技術(shù),以降低3D Zernike 矩計(jì)算過程的復(fù)雜度. 與現(xiàn)有算法相比,這一快速算法能夠?qū)⒂?jì)算時(shí)間減少超過90%. 這一改進(jìn)在保證計(jì)算精度的前提下,有效地提升了地形匹配算法的實(shí)時(shí)性能.
其二是針對(duì)匹配精度與3D Zernike 矩階次之間呈現(xiàn)“波動(dòng)式”上升的現(xiàn)象,探討構(gòu)成地形特征向量的奇偶階描述子的性能差異. 通過對(duì)信息包含、地形特征反映能力、抗噪性以及旋轉(zhuǎn)適應(yīng)性等四個(gè)關(guān)鍵方面的深入分析,凸顯了奇數(shù)階描述子對(duì)于地形匹配而言所具備的優(yōu)勢. 在此基礎(chǔ)上,本文提出了一種新的匹配算法,僅利用奇數(shù)階描述子構(gòu)成地形特征向量.經(jīng)過仿真驗(yàn)證,這一算法不僅減少近一半的計(jì)算量,還在匹配精度上取得顯著提升.
本文所提出的快速算法為基于3D Zernike 矩的地形匹配應(yīng)用帶來了實(shí)時(shí)性能的提升,為高精度地形輔助導(dǎo)航等領(lǐng)域的應(yīng)用提供了廣闊的前景. 通過本文的研究成果,在實(shí)際應(yīng)用中有望實(shí)現(xiàn)更加高效和準(zhǔn)確的三維地形匹配.