董純柱*①② 殷紅成①② 王 超②

?

基于射線管分裂方法的SAR場(chǎng)景快速消隱技術(shù)

董純柱殷紅成王 超

(中國(guó)傳媒大學(xué)信息工程學(xué)院 北京 100024)(電磁散射重點(diǎn)實(shí)驗(yàn)室 北京 100854)

SAR場(chǎng)景模型常采用非均勻三角網(wǎng)格描述，使得傳統(tǒng)的基于Z-Buffer技術(shù)的消隱算法難以在保持較高的消隱精度的同時(shí)兼顧消隱效率。該文提出了一種基于射線管分裂方法的SAR場(chǎng)景快速消隱技術(shù)，將復(fù)雜SAR場(chǎng)景的消隱問(wèn)題分解為兩個(gè)簡(jiǎn)單過(guò)程：一是對(duì)場(chǎng)景三角網(wǎng)格在發(fā)射平面上的投影點(diǎn)云做2維Delaunay三角網(wǎng)格劃分，二是基于射線管分裂方法對(duì)新生網(wǎng)格可見(jiàn)性進(jìn)行判斷和拓?fù)渲貥?gòu)。典型飛機(jī)目標(biāo)和草地上T-72坦克的消隱結(jié)果驗(yàn)證了該方法的準(zhǔn)確性和高效性。

消隱算法；射線管分裂方法；Delaunay三角剖分；Z-Buffer算法；SAR場(chǎng)景

1 引言

對(duì)基于模板匹配的SAR圖像解譯而言，SAR圖像中特有的透視收縮、疊掩和陰影等幾何畸變特性是重要且穩(wěn)定的識(shí)別特征。在低擦地角(10°～30°)條件下，高分辨率SAR圖像表現(xiàn)出尤為明顯和完整的陰影特征。地面目標(biāo)SAR圖像的陰影主要由地面目標(biāo)的自遮擋陰影和目標(biāo)-環(huán)境間的互遮擋陰影兩部分組成。為準(zhǔn)確仿真地面目標(biāo)的散射特性和SAR圖像中的陰影特征，不可避免地要事先確定在給定入射方向上地面目標(biāo)以及環(huán)境表面的可見(jiàn)和不可見(jiàn)區(qū)域，即進(jìn)行面消隱處理。

目前，常用的面消隱算法包括Z-Buffer算法、區(qū)間掃描線算法、BSP樹算法、區(qū)域細(xì)分算法、射線投射算法等。其中，以Z-Buffer算法和射線投射算法的應(yīng)用最為廣泛。借助顯卡(GPU)強(qiáng)大的渲染和并行計(jì)算能力，Z-Buffer算法和射線投射算法能夠以秒級(jí)實(shí)現(xiàn)單個(gè)角度上百萬(wàn)量級(jí)均勻三角網(wǎng)格模型的消隱運(yùn)算。然而，在高分辨條件下，若采用均勻三角網(wǎng)格對(duì)復(fù)雜目標(biāo)和幾百米甚至幾公里的環(huán)境表面進(jìn)行剖分，將產(chǎn)生千萬(wàn)甚至上億量級(jí)的網(wǎng)格面元，消隱運(yùn)算效率極低。為了提高SAR場(chǎng)景模型的消隱效率，必須大幅度減少網(wǎng)格面元的數(shù)量。一種可行的方法是采用非均勻三角網(wǎng)格(或TIN網(wǎng)格)對(duì)SAR場(chǎng)景模型進(jìn)行剖分，在不明顯降低模型精度的條件下產(chǎn)生最少數(shù)量的面元網(wǎng)格。因此，解決非均勻三角網(wǎng)格模型的快速消隱問(wèn)題是實(shí)現(xiàn)SAR場(chǎng)景快速消隱的關(guān)鍵。

本文融合區(qū)域細(xì)分算法和射線投射算法思想，在基于kD-tree的非均勻三角網(wǎng)格模型GPU快速射線追蹤的基礎(chǔ)上，將非均勻三角網(wǎng)格模型描述的SAR場(chǎng)景消隱問(wèn)題分解為對(duì)場(chǎng)景網(wǎng)格在發(fā)射平面上的投影點(diǎn)云做2維Delaunay三角剖分，以及基于射線管分裂方法對(duì)新生網(wǎng)格可見(jiàn)性進(jìn)行判斷和拓?fù)渲貥?gòu)兩個(gè)簡(jiǎn)單過(guò)程，實(shí)現(xiàn)了復(fù)雜場(chǎng)景的精確快速消隱計(jì)算。以飛機(jī)和草地上T-72坦克為例，消隱計(jì)算結(jié)果表明，本文方法能夠?qū)崿F(xiàn)復(fù)雜SAR場(chǎng)景實(shí)時(shí)/準(zhǔn)實(shí)時(shí)的準(zhǔn)確消隱，為快速獲取SAR圖像陰影等幾何畸變特性以及目標(biāo)-環(huán)境的電磁散射特性提供了高效預(yù)處理工具。

2 基于射線管分裂方法的SAR場(chǎng)景快速消隱

考慮到SAR場(chǎng)景是由非均勻三角網(wǎng)格描述的，基于射線管分裂方法的SAR場(chǎng)景快速消隱計(jì)算主要包括如下3個(gè)步驟：

(1) 發(fā)射面點(diǎn)云數(shù)據(jù)生成：沿入射方向?qū)AR場(chǎng)景進(jìn)行自遮擋判斷，并將自遮擋可見(jiàn)頂點(diǎn)投影到發(fā)射面上形成2維點(diǎn)云數(shù)據(jù)；

(2) 點(diǎn)云數(shù)據(jù)三角網(wǎng)格剖分：構(gòu)建發(fā)射面點(diǎn)云數(shù)據(jù)2維凸包，并實(shí)現(xiàn)帶凸包的Delaunay三角剖分，形成初始射線管；

(3) 網(wǎng)格模型可見(jiàn)性判斷及拓?fù)渲貥?gòu)：根據(jù)射線管與目標(biāo)的相交情況，對(duì)射線管執(zhí)行自動(dòng)分裂，并根據(jù)細(xì)分射線管與場(chǎng)景網(wǎng)格的相交關(guān)系重構(gòu)場(chǎng)景可見(jiàn)三角網(wǎng)格。

2.1 發(fā)射面點(diǎn)云數(shù)據(jù)生成

為加速反射面點(diǎn)云生成過(guò)程，沿入射方向?qū)θ蔷W(wǎng)格進(jìn)行自遮擋判斷，即判斷三角形面元正法向與入射方向夾角的余弦

其中，為可見(jiàn)頂點(diǎn)個(gè)數(shù)，發(fā)射平面上的點(diǎn)由遠(yuǎn)離場(chǎng)景的固定點(diǎn)和面法向確定，如下：

式中，為場(chǎng)景模型的幾何中心，為場(chǎng)景模型包圍球的直徑。

2.2點(diǎn)云數(shù)據(jù)三角網(wǎng)格剖分

為能夠?qū)Πl(fā)射面點(diǎn)云數(shù)據(jù)進(jìn)行帶凸包的2維Delaunay三角剖分，首先需要建立如圖4所示的發(fā)射面局部坐標(biāo)系，并將3維點(diǎn)云數(shù)據(jù)轉(zhuǎn)換為局部坐標(biāo)系下的2維點(diǎn)云數(shù)據(jù)，其中

計(jì)算2維有限點(diǎn)云數(shù)據(jù)2維凸包(Convex Hull)的算法很多[3,4]，這里不再贅述。本文采用時(shí)間復(fù)雜度為的分而治之算法[8]實(shí)現(xiàn)發(fā)射面點(diǎn)云數(shù)據(jù)2維凸包的快速構(gòu)建，其中為凸包頂點(diǎn)個(gè)數(shù)。

三角剖分的一般要求是不存在長(zhǎng)而薄的三角形(Slivers)。Delaunay三角剖分是一種使最小角具有最大值的方法，能夠最大限度地減少狹長(zhǎng)三角形的數(shù)量。為改進(jìn)凸包邊界附近的三角形的性態(tài)，在進(jìn)行Delaunay三角剖分前，先求取如圖4所示的2維凸包的最小包圍矩形；然后按對(duì)構(gòu)成包圍矩形的4條邊界,,和進(jìn)行均勻細(xì)分，生成細(xì)分邊界點(diǎn)，其中為細(xì)分邊界點(diǎn)個(gè)數(shù)，且

2.3網(wǎng)格模型可見(jiàn)性判斷及拓?fù)渲貥?gòu)

為實(shí)現(xiàn)對(duì)非均勻網(wǎng)格描述的SAR場(chǎng)景模型的精確消隱處理，首先需要基于發(fā)射面點(diǎn)云數(shù)據(jù)Delaunay三角剖分結(jié)果生成初始射線管，在GPU上采用OptiX射線追蹤引擎完成射線管頂點(diǎn)射線的自動(dòng)射線追蹤，并根據(jù)射線管頂點(diǎn)射線與非均勻網(wǎng)格的相交關(guān)系進(jìn)行自動(dòng)射線管分裂。本文采用的射線管自動(dòng)分裂方法如圖1(c)所示，閾值,，并且和越小，消隱精度越高，計(jì)算量也越大。精度和效率折中考慮，和經(jīng)驗(yàn)值分別為和6°。對(duì)于每次分裂得到的4個(gè)細(xì)分射線管僅需追蹤由原始射線管3邊中點(diǎn)生成的3根新增射線。完成所有射線管的自動(dòng)分裂計(jì)算后，即可獲得全部可見(jiàn)射線管在網(wǎng)格模型面元上的第1個(gè)交點(diǎn)數(shù)據(jù)集。其中，為全部可見(jiàn)射線管個(gè)數(shù)；為可見(jiàn)射線管與面元模型的第1個(gè)交點(diǎn)個(gè)數(shù)；,和為可見(jiàn)射線管第1個(gè)交點(diǎn)索引，且。因此，重建的消隱處理后的SAR場(chǎng)景的可見(jiàn)三角網(wǎng)格模型由線性表表示為

(a) 1000個(gè)2維點(diǎn)云三角剖分結(jié)果 (b) 2維點(diǎn)云三角剖分效率

射線管頂點(diǎn)射線與非均勻網(wǎng)格的相交具體包括下面4種情況：

(1) 若3根射線與網(wǎng)格模型無(wú)交點(diǎn)或射線管的面積小于閾值，判定為無(wú)效射線管，直接丟棄；

(2) 若3根射線的第1個(gè)交點(diǎn)均位于同一面元上，判斷為全部可見(jiàn)射線管，不再分裂；

(3) 若3根射線的第1個(gè)交點(diǎn)位于同一部件的不同面元上，且面元法向間夾角小于閾值，判斷為全部可見(jiàn)射線管，不再分裂；

(4) 除上述3種情形外，都判斷為部分可見(jiàn)射線管，需要進(jìn)行分裂。

3 算例和分析

下面用飛機(jī)目標(biāo)和地面上T72坦克的消隱計(jì)算實(shí)例驗(yàn)證本文方法的正確性、高效性和實(shí)用性。仿真硬件平臺(tái)為搭載NVIDIA Quadro FX 5800 4GB GDDR3顯存圖形卡的HP Z800工作站。

3.1飛機(jī)目標(biāo)

如圖6(a)所示，飛機(jī)總體尺寸為20.09 m×13.2 m×2.33 m，其非均勻三角網(wǎng)格模型由423個(gè)頂點(diǎn)和842個(gè)三角形面元構(gòu)成。圖6(b)為取=43.3 mm,，沿入射，經(jīng)消隱重構(gòu)的由44,139個(gè)頂點(diǎn)和64,272個(gè)三角形面元構(gòu)成的可見(jiàn)網(wǎng)格模型，消隱處理時(shí)間為1.033 s。如果將飛機(jī)按10 mm尺寸剖分(三角形面積約為)，將生成由2,608,529頂點(diǎn)和5,217,248面元構(gòu)成的均勻三角網(wǎng)格模型，而在同樣角度下采用基于硬件的Z-Buffer算法消隱計(jì)算時(shí)間為0.841 s，消隱結(jié)果如圖6(c)所示?？梢?jiàn)，本文算法能夠在達(dá)到硬件Z-Buffer算法消隱效率和精度的同時(shí)，重構(gòu)更少面元數(shù)量(約為均勻剖分時(shí)的1.23%)的可見(jiàn)三角網(wǎng)格模型供后續(xù)電磁散射計(jì)算使用，并在完成SAR場(chǎng)景消隱處理的同時(shí)完成了場(chǎng)景的射線追蹤，因此必將顯著提高SAR場(chǎng)景電磁特性預(yù)估效率。

3.2 草地上T-72坦克

對(duì)SAR場(chǎng)景消隱重構(gòu)可見(jiàn)三角網(wǎng)格模型的一個(gè)最直接的應(yīng)用是高效仿真用于陰影區(qū)邊界確定和姿態(tài)估計(jì)的非相干陰影模板圖像。圖7給出了采用本文方法快速獲取的草地上T-72坦克在73°入射角0.2 m分辨率128×128像素、方位角間隔為45°的非相干陰影模板圖像，其中目標(biāo)、地面和陰影區(qū)域的像素亮度分別為255, 127和0。T-72場(chǎng)景由18, 309頂點(diǎn)和35, 317三角形面元構(gòu)成，其單幅圖像的仿真時(shí)間僅為0.2 s, 1～2 min即可完成方位角間隔1°全方位模板圖集仿真?？梢钥闯?，非相干陰影圖像準(zhǔn)確重現(xiàn)了給定角度下目標(biāo)在環(huán)境上的穩(wěn)定和完整陰影特性。

(a) 非均勻網(wǎng)格模型

(b) 非均勻三角網(wǎng)格模型本文方法消隱結(jié)果

(c) 均勻三角網(wǎng)格模型Z-Buffer算法消隱結(jié)果

4 結(jié)論

本文提出的基于射線管分裂方法的SAR場(chǎng)景快速消隱技術(shù)有效融合了區(qū)域細(xì)分算法和射線投射算法思想，能夠解決采用非均勻三角網(wǎng)格描述的SAR場(chǎng)景模型的精確快速消隱問(wèn)題。消隱重構(gòu)的可見(jiàn)三角網(wǎng)格模型能夠直接用于SAR場(chǎng)景非相干陰影模板圖像仿真，射線管分裂結(jié)果亦可直接用于SAR場(chǎng)景電磁散射特性計(jì)算，從而顯著提高復(fù)雜目標(biāo)電磁特性預(yù)估以及SAR模板圖像的仿真效率。

圖7 草地上T-72坦克在73°入射角、0.2 m分辨率、128像素×128像素非相干陰影圖像

[1] Oliver C J, Quegan S, Ward, I A等著, 丁赤飚等譯. 合成孔徑雷達(dá)圖像理解[M]. 電子工業(yè)出版社, 2009.

Oliver C J, Quegan S, Ward, I A,, translated by Ding Chi-biao,Synthetic Aperture Radar Image Inter- pretation[M]. Publishing House of Electronics Industry, 2009.

[2] Ross T D, Bradley J J, Hudson L J,SAR ATR: so what's the problem? An MSTAR perspective[C]. SPIE Conference on Algorithms for Synthetic Aperture Radar Imagery, Orlando, Florida, April 1999, 3721: 662–672.

[3] 和青芳. 計(jì)算機(jī)圖形學(xué)原理及算法教程(Visual C++版)[M]. 清華大學(xué)出版社, 2010.

He Qing-fang. Principle and Algorithm on Computer Graphics(Visual C++ Edition)[M]. Publishing House of Tsinghua, 2010.

[4] Schneider P J and Eberly D H著, 周長(zhǎng)發(fā)譯. 計(jì)算機(jī)圖形學(xué)幾何工具算法詳解[M]. 電子工業(yè)出版社, 2005.

Schneider P J and Eberly D H, translated by Zhou Chang-fa. Geometric Tools for Computer Graphics[M]. Publishing House of Electronics Industry, 2005.

[5] Parker S G, Bigler J, Dietrich, AOptiX: a general purpose ray tracing engine[C]. ACM Transactions on Graphics, New York, July 2010, 29(4): 1–13.

[6] Wang Pan, Liu Hua-hai, and Li Si-kun. Multi-GPU Compositeless parallel rendering algorithm[C]. 12th Inter- national Conference on Computer-Aided Design and Computer Graphics, Shenzhen university, December 2011, 66: 103–107.

[7] Zhang Chang-gong, Xi Ping, and Zhang Chao-xin. CUDA- based volume ray-casting using cubic b-spline[C]. Inter- national Conference on Virtual Reality and Visualization, Renmin University, October 2011, 10: 84–88.

[8] Shih Min, Chiu Yung-Feng, Chen Ying-Chieh.. Real-time ray tracing with CUDA[C]. Lecture Notes in Computer Science, Berlin Heidelberg, 2009, 5574: 327–337.

[9] Balciunas D A, Dulley L P, and Zuffo M K. GPU-assisted ray casting of large scenes[J]., 2006, 18(20): 95–103.

[10] Dwyer R A. A faster divide-and-conquer algorithm for constructing delaunay triangulations[J]., 1987, 2(2): 137–151.

[11] Shewchuk J R. Triangle: Engineering a 2D quality mesh generator and delaunay triangulator[J].:, 1996, 1148: 203–222.

[12] Shewchuk J R. Delaunay Refinement algorithms for triangular mesh generation[J]., 2002, 22(1–3): 21–74.

A Fast Hidden Surface Removal Approach for Complex SAR Scene Based on Adaptive Ray-tube Splitting Method

Dong Chun-zhuYin Hong-chengWang Chao

(Information Engineering School, Communication University of China, Beijing 100024, China)(National Electromagnetic Scattering Laboratory, Beijing 100854, China)

Traditional hidden surface removal algorithm based on hardware Z-Buffer technique cannot give attention to precision or efficiency at the same time when dealing with the non-uniform triangulated SAR (Synthetic Aperture Radar) scene model. A novel high-precision hidden surface removal approach using fast ray-tube splitting algorithm is proposed, where the SAR scene hidden surface removal problem is decomposed into two simple procedures,.. a Delaunay triangulator is used to generate the initial ray tubes from the projected point clouds of all incident visible vertices, then an adaptive ray-tube splitting method is adopted to carry out the complex scene shading situations and resultant visible model reconstruction. Simulation results of typical aircraft and T-72 tank show that, the new approach is feasible and effective.

Hidden surface removal algorithm; Ray-tube splitting method; Delaunay triangulation; Z-Buffer algorithm; SAR (Synthetic Aperture Radar) scene

TN957

A

2095-283X(2012)04-0436-05

10.3724/SP.J.1300.2012.20064

董純柱(1981－)，男，河南信陽(yáng)人，工程師，現(xiàn)為中國(guó)傳媒大學(xué)電磁場(chǎng)與微波技術(shù)專業(yè)在職博士生，主要研究興趣為SAR圖像解譯和電磁散射理論計(jì)算。

殷紅成(1967－)，男，江西余江人，研究員，專業(yè)總師，博士生導(dǎo)師，主要研究興趣為電磁散射、雷達(dá)目標(biāo)特性、目標(biāo)識(shí)別等。

王 超(1979－)，男，陜西西安人，高工，博士，主要研究興趣為電磁散射、雷達(dá)目標(biāo)特性和數(shù)值計(jì)算等。

2012-09-11收到，2012-11-14改回；2012-12-10網(wǎng)絡(luò)優(yōu)先出版

國(guó)家部委基金資助課題

董純柱 dongcz207@gmail.com