SAR圖像并行拼接方法研究與實現*——基于改進完全二叉樹模型

孫 權，張 華，荊于勤

(重慶郵電大學移通學院，重慶401520)

由于合成孔徑雷達(Synthetic Aperture Radar，SAR)［1］圖像數據序列中相鄰圖像間存在重疊區域，因此已有SAR圖像并行拼接方法大都采用基于完全二叉樹模型的方法，即將SAR圖像序列中圖像按成像時的先后順序從前到后或從后向前兩兩分組，從而由下至上地構建出一顆完全二叉樹.根據對SAR圖像序列特征［2］的詳細分析，對傳統的基于完全二叉樹模型的方法進行改進，提出一種基于分割的完全二叉樹模型來對SAR圖像進行并行［3］拼接.

在此所用SAR圖像尺寸均為4 096×4 096，數據大小為16 M.機載成像平臺以近似勻速直線運動方式對某地面區域連續成像生成源SAR圖像數據序列，選取其中5張圖像(圖1)進行實驗研究，圖像編號從img1至img5.序列中相鄰圖像間均存在局部區域重疊現象.

圖1 源SAR圖像序列示意圖

1 傳統完全二叉樹模型

以圖像序列中的5幅SAR圖像從img1到img5為例，按照“從下至上，從左至右”的規則建立完全二叉樹模型:

圖2 完全二叉樹模型

圖2 中，img1至img5為SAR圖像序列中的連續圖像，各圖像與相鄰圖像間有重疊區域.非葉子結點(如img1_2，img1_2_3)等是由其子結點拼接后產生的圖像.模型中以參考圖像作為其左孩子結點，待拼接圖像為右孩子結點.

2 基于分割的完全二叉樹模型

將SAR圖像序列進行手動編號，從前到后依次編號為img1到img6.經對所有圖像數據分析研究后發現，圖像序列中處于中間位置的圖像(即img2到img5)，與前后相鄰幀圖像有著重疊部分，稱之為重疊區域.這些重疊區域大小不一，部分帶有輕微角度變化.而同一圖像(如img3)存在的部分獨立區域，與前相鄰的一幀圖像(img2)和后相鄰的一幀圖像(img4)所重疊的兩個區域是不重合的(如圖3虛線部分所示).

圖3 圖像img3獨立區域示意圖

由圖像拼接原理可知，參與一次拼接處理的兩張圖像分為參考圖像與待拼接圖像，通過將待處理圖像映射到參考圖像上來實現兩張圖像的拼接.理論上，參考圖像在拼接過程中是不需要進行圖像變換等操作的.參考標準拼接過程的特點，再結合本課題中SAR圖像序列的特征，設計出基于分割的完全二叉樹模型.

由圖2可知，SAR圖像序列的中間圖像幀是存在獨立區域的，沿獨立區域的中間部分將SAR圖像進行分割，然后將分割產生的兩張圖像分別與有重疊區域的前相鄰和后相鄰兩張圖像進行組合，作為完全二叉樹的葉子節點，最后每對葉子節點占用一臺節點機進行拼接.原理如圖4所示:

圖4 基于分割的完全二叉樹拼接模型

圖4 中，葉子結點img2f和img2l為3幅圖像中間幀img2經過分割產生的兩幅子圖像，它們分別與存在重疊區域的img1和img3進行組合，經過步驟，拼接生成相應的拼接圖片img1_2f和img3_2l.然后經過步驟2，直接連接兩幅圖像生成最終拼接結果.

2.1 累積誤差分析

在SAR圖像序列進行并行拼接時，隨著拼接的深入，其變換矩陣會逐次累積［4］.因此隨著連續拼接次數的增加，相鄰幀之間的拼接誤差會因不斷累積最終形成累積誤差.以參考圖像作為左孩子結點，待拼接圖像作為右孩子結點，在基于分割的完全二叉樹模型中，采用右孩子結點經變換后投影到左孩子結點的拼接模式.隨著拼接層次的變化，參考圖像會不斷調整.由累積誤差產生原因可知，此種方法能一定程度上減小拼接過程中的誤差累計，有助于幫助SAR圖像拼接精度的提升.

3 基于分割的完全二叉樹模型的SAR圖像并行拼接方法實現

傳統并行圖像拼接處理中，圖像數據的劃分方式是兩兩分組，按照完全二叉樹模型，將各圖像作為葉子結點按順序生成完全二叉樹，然后按每對葉子結點一臺處理機的分配方式進行并行系統資源分配.這種分組方式簡單易實現，但隨著拼接數量的增長，通信開銷也不斷增大，從而影響并行拼接的效率［5］.

此處提出的改進方法對圖像序列按3副一組進行處理，如每組按前后順序編號分組結果為(img1，img2，img3)、(img4，img5，img6).由于相鄰SAR圖像間存在重疊區域，而單張圖像存在獨立區域，因此本方法將每組第2張圖像按獨立區域中線進行分割，由此產生兩幅分割后的新圖像，例如對img2進行分割后產生兩幅圖像 img2f與 img2l.

由SAR圖像拼接的原理可知，一般情況下，拼接過程中無需對參考圖形作圖像變換處理.鑒于此特點，本方法將分割產生的兩幅新圖像作為左孩子葉子結點分別與對應的與之共有重疊區域的相鄰圖像進行組合，以左孩子節點為參考圖像作拼接處理.以分組(img1，img2，img3)為例，將分割后產生的圖像img2f與img2l作為左孩子葉子結點，其中img2f與img1組合，img2l與img3組合.在此方式下，兩組拼接圖像中，都以左孩子節點作為參考圖像，對右孩子節點的圖像作投影變換后投影到左孩子結點，即分別對img1和img3做投影變換，而img2f與img2l不作處理.

并行處理時，為每對組合好的拼接圖像分配一臺處理機.對于分組(img1，img2，img3)，并行處理時分別分配兩臺處理機給組合img2f與img1，img2l與img3.這樣，一次拼接時間后即完成img2f與 img1，img2l與img3兩個組合的拼接工作.而又由于img2f和img2l并沒有進行任何變換處理，因此可以直接將拼接后的兩部分按img2f與img2l的連接部分連接起來，最后生成3幅圖像完整的拼接圖像.

而對于SAR圖像數不能被3整除的拼接序列，分為圖像數除以3的余數為1和2兩種情況.

余數為1的圖像序列，采用增加一次拼接處理來實現.以4幅圖像為例，首先將圖像前3張分為一組，剩余的1張為單獨一組.使用兩臺處理機并行處理，前3張圖像并行拼接完成后，再增加一次拼接工作，將前3張拼接后圖像作為參考圖像與剩余的一張圖像進行拼接.雖然需要兩個拼接時間來完成全部拼接任務，但與傳統分組方式相比，后一次拼接中的圖像投影變換由于數據量減少，變換的時間花費較少，更有優勢.

余數為2的圖像序列，采用增加一臺處理機的方式來實現.以5副圖為例，首先將前3張圖像分為一組，剩余的兩張分為一組，使用3臺處理機并行處理.一次拼接時間后，前3張圖像與后兩張圖像的拼接分別完成.再對這兩張進行一次拼接工作完成全部圖像的拼接.總共花費兩次拼接時間，而傳統方式則需3次拼接時間才能完成.

此種方法極大減少了拼接的時間消耗.沿獨立區域分割后主節點機發送的數據量減少，有效減少了并行處理時的數據傳輸時間.兩臺節點機并行處理使得原來串行方法需兩次拼接時間才能完成的工作縮減到一次拼接時間外加兩幅圖像連接的時間，而兩幅圖像連接的時間非常短，因此可以看作一次拼接時間就完成3幅圖的拼接工作量，極大提高了SAR圖像的拼接效率.

3.1 生成拼接圖

拼接工作中，投影后坐標出現非整數值時，采用相鄰四像素雙線性插值法進行處理，生成SAR拼接圖像.并采用Szeliski算法［6］對因相鄰兩圖像間灰度差異而導致的拼接縫進行消除.

3.2 負載均衡

實驗中使用MPI［7，8］點對點通信方式實現機群間的通信.由負載均衡原理可知，其主要是針對節點機性能不一致的并行系統.本實驗中由于所使用計算機配置統一，各節點機性能一致，如果采用負載均衡策略先分析節點性能，再對SAR圖像矩陣數據進行分配會增加系統額外開銷，影響并行效率，因此在負載均衡中去除了節點性能分析步驟.

4 實驗結果與分析

實驗使用編號為1到4的4臺節點機(即nd0，nd1，nd2，nd3)，所使圖像大小均為1 M，3副SAR圖像序列選取img1-img3，4副SAR圖像序列選取img1-img4，5副SAR圖像序列選取img1-img5.在機群并行平臺上，實驗分別對圖像數為3，4，5的3個圖像序列采用基于傳統的兩兩分組構建完全二叉樹方法(以下簡稱傳統方法)與本文所提出的基于分割的完全二叉樹模型的方法(以下簡稱新方法)進行并行拼接實驗，并對實驗結果進行了對比分析.

SAR圖像3副序列選取img1-img3進行并行拼接實驗，選用1號和2號節點機(nd0，nd1).由于傳統并行拼接方法對于3副圖像無法進行兩組以下的配對，其拼接過程與串行拼接方法相同，拼接時間消耗也與串行拼接相當.因此對于3副SAR圖像序列的拼接只進行文中拼接方法的實驗，首先將img2分割為img2f和img1，img2l和img3兩組，分別交由nd0和nd1并行拼接.并行拼接后，nd1發送結果img2l_3到nd0，由nd0連接img2f_1與img2l_3兩幅圖像，生成完整拼接圖像img1_2_3.實驗結果如表1所示.

表1 3副SAR圖像并行拼接實驗結果對比表

SAR圖像4副序列選取img1-img4進行并行拼接實驗，同樣選用1號和2號節點機(nd0，nd1).使用傳統方法對4副圖像序列進行并行拼接，首先將4幅圖像分為img1和img2，img3和img4兩組，然后分別交由nd0和nd1并行拼接.并行拼接拼接后nd1發送結果圖像到nd0，由nd0繼續完成img1_2和img3_4的拼接后，生成完整拼接圖像img1_2_3_4.使用文中方法對4副SAR圖像序列進行并行拼接，首先將img1，img2和img3分為一組，img4單獨一組;然后將img2分割為img2f和img1，img2l和img3兩組后分別交由nd0和nd1并行拼接，并行拼接后nd1發送結果img2l_3到nd0，由nd0連接img2f_1與img2l_3，最后再由nd0對img1_2_3和img4進行拼接，生成完整拼接圖像img1_2_3_4.實驗結果如表2所示.

表2 4副SAR圖像并行拼接實驗結果對比表

SAR圖像5副序列選取img1-img5進行并行拼接實驗，選用1號和3號節點機(nd0，nd1，nd2).使用傳統方法對5副圖像序列進行并行拼接，首先將5幅圖像分為img1和img2，img3和img4，img5 3組，然后分別將前兩組交由nd0和nd1并行拼接，并行拼接拼接后，nd1發送結果圖像到nd0，由nd0將img1_2和img3_4拼接產生img1_2_3_4，最后再由nd0完成img1_2_3_4與img5的拼接，生成完整拼接圖像img1_2_3_4_5.使用文中方法對4副SAR圖像序列進行并行拼接，首先將img1，img2和img3分為一組，img4和img5分為第2組;然后將img2進行分割后分為img2f和img1，img2l和img3兩組后分別交由nd0和nd1，將img4和img5交由nd3進行并行拼接，并行拼接后，nd1發送結果img2l_3，nd3發送結果img4_5到nd0，由nd0完成對img2f_1與img2l_3的連接，生成img1_2_3后，再將img1_2_3與img4_5進行拼接，生成完整拼接圖像img1_2_3_4_5.實驗結果如表3所示.

分析以上實驗結果可知，在SAR圖像序列為3幅時，傳統方法無法有效對之進行并行拼接，而文中方法能很好解決3幅圖像并行拼接問題，并達到了較理想的并行效率.對于序列中SAR圖像數為4幅的拼接處理，相較于傳統方法，文中方法在并行拼接效率上同樣有所提升.在5幅圖像的SAR圖像序列的拼接工作中，文中方法效率提升優勢尤為明顯.由此可以看出，所設計的基于分割的完全二叉樹模型能大大縮減多幅SAR圖像序列的拼接時間，極大提高了拼接效率.

表3 5副SAR圖像并行拼接實驗結果對比表

［1］宋建社，鄭永安，袁禮海.合成孔徑雷達圖像理解與應用［M］.北京:科學出版社，2008

［2］鄭世友，周曄.無有效重疊區域的SAR圖像拼接方法［J］.中國圖象圖形學報，2009，14(10):2055

［3］HOSSFELD F.Teraflops Computing:A Challenge to Parallel Numeries［C］∥ACPC’99，1999:1-12

［4］張紅斌.遙感圖像拼接算法研究［D］.西安:西安電子科技大學，2006

［5］雷英杰，霍紅衛.典型并行算法的實現性能分析［J］.空軍工程大學學報，2003，4(5):68-73

［6］FATTAL R，LISCHINSKI D，WERMAN M.Gradient Domain High Dynamic Range Compression［C］∥Proc of the 29thAnnual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press，2002

［7］張建文，徐瓊，王強.基于 MPI環境的并行程序設計［J］.東華理工學院學報，2007，30(1):81-84

［8］陳國良，安虹.并行算法實踐［M］.北京:高等教育出版社，2004