SAR圖像并行拼接方法研究與實(shí)現(xiàn)*——基于改進(jìn)完全二叉樹(shù)模型

孫 權(quán)，張 華，荊于勤

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

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

在此所用SAR圖像尺寸均為4 096×4 096，數(shù)據(jù)大小為16 M.機(jī)載成像平臺(tái)以近似勻速直線(xiàn)運(yùn)動(dòng)方式對(duì)某地面區(qū)域連續(xù)成像生成源SAR圖像數(shù)據(jù)序列，選取其中5張圖像(圖1)進(jìn)行實(shí)驗(yàn)研究，圖像編號(hào)從img1至img5.序列中相鄰圖像間均存在局部區(qū)域重疊現(xiàn)象.

圖1 源SAR圖像序列示意圖

1 傳統(tǒng)完全二叉樹(shù)模型

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

圖2 完全二叉樹(shù)模型

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

2 基于分割的完全二叉樹(shù)模型

將SAR圖像序列進(jìn)行手動(dòng)編號(hào)，從前到后依次編號(hào)為img1到img6.經(jīng)對(duì)所有圖像數(shù)據(jù)分析研究后發(fā)現(xiàn)，圖像序列中處于中間位置的圖像(即img2到img5)，與前后相鄰幀圖像有著重疊部分，稱(chēng)之為重疊區(qū)域.這些重疊區(qū)域大小不一，部分帶有輕微角度變化.而同一圖像(如img3)存在的部分獨(dú)立區(qū)域，與前相鄰的一幀圖像(img2)和后相鄰的一幀圖像(img4)所重疊的兩個(gè)區(qū)域是不重合的(如圖3虛線(xiàn)部分所示).

圖3 圖像img3獨(dú)立區(qū)域示意圖

由圖像拼接原理可知，參與一次拼接處理的兩張圖像分為參考圖像與待拼接圖像，通過(guò)將待處理圖像映射到參考圖像上來(lái)實(shí)現(xiàn)兩張圖像的拼接.理論上，參考圖像在拼接過(guò)程中是不需要進(jìn)行圖像變換等操作的.參考標(biāo)準(zhǔn)拼接過(guò)程的特點(diǎn)，再結(jié)合本課題中SAR圖像序列的特征，設(shè)計(jì)出基于分割的完全二叉樹(shù)模型.

由圖2可知，SAR圖像序列的中間圖像幀是存在獨(dú)立區(qū)域的，沿獨(dú)立區(qū)域的中間部分將SAR圖像進(jìn)行分割，然后將分割產(chǎn)生的兩張圖像分別與有重疊區(qū)域的前相鄰和后相鄰兩張圖像進(jìn)行組合，作為完全二叉樹(shù)的葉子節(jié)點(diǎn)，最后每對(duì)葉子節(jié)點(diǎn)占用一臺(tái)節(jié)點(diǎn)機(jī)進(jìn)行拼接.原理如圖4所示:

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

圖4 中，葉子結(jié)點(diǎn)img2f和img2l為3幅圖像中間幀img2經(jīng)過(guò)分割產(chǎn)生的兩幅子圖像，它們分別與存在重疊區(qū)域的img1和img3進(jìn)行組合，經(jīng)過(guò)步驟，拼接生成相應(yīng)的拼接圖片img1_2f和img3_2l.然后經(jīng)過(guò)步驟2，直接連接兩幅圖像生成最終拼接結(jié)果.

2.1 累積誤差分析

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

3 基于分割的完全二叉樹(shù)模型的SAR圖像并行拼接方法實(shí)現(xiàn)

傳統(tǒng)并行圖像拼接處理中，圖像數(shù)據(jù)的劃分方式是兩兩分組，按照完全二叉樹(shù)模型，將各圖像作為葉子結(jié)點(diǎn)按順序生成完全二叉樹(shù)，然后按每對(duì)葉子結(jié)點(diǎn)一臺(tái)處理機(jī)的分配方式進(jìn)行并行系統(tǒng)資源分配.這種分組方式簡(jiǎn)單易實(shí)現(xiàn)，但隨著拼接數(shù)量的增長(zhǎng)，通信開(kāi)銷(xiāo)也不斷增大，從而影響并行拼接的效率［5］.

此處提出的改進(jìn)方法對(duì)圖像序列按3副一組進(jìn)行處理，如每組按前后順序編號(hào)分組結(jié)果為(img1，img2，img3)、(img4，img5，img6).由于相鄰S(chǎng)AR圖像間存在重疊區(qū)域，而單張圖像存在獨(dú)立區(qū)域，因此本方法將每組第2張圖像按獨(dú)立區(qū)域中線(xiàn)進(jìn)行分割，由此產(chǎn)生兩幅分割后的新圖像，例如對(duì)img2進(jìn)行分割后產(chǎn)生兩幅圖像 img2f與 img2l.

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

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

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

余數(shù)為1的圖像序列，采用增加一次拼接處理來(lái)實(shí)現(xiàn).以4幅圖像為例，首先將圖像前3張分為一組，剩余的1張為單獨(dú)一組.使用兩臺(tái)處理機(jī)并行處理，前3張圖像并行拼接完成后，再增加一次拼接工作，將前3張拼接后圖像作為參考圖像與剩余的一張圖像進(jìn)行拼接.雖然需要兩個(gè)拼接時(shí)間來(lái)完成全部拼接任務(wù)，但與傳統(tǒng)分組方式相比，后一次拼接中的圖像投影變換由于數(shù)據(jù)量減少，變換的時(shí)間花費(fèi)較少，更有優(yōu)勢(shì).

余數(shù)為2的圖像序列，采用增加一臺(tái)處理機(jī)的方式來(lái)實(shí)現(xiàn).以5副圖為例，首先將前3張圖像分為一組，剩余的兩張分為一組，使用3臺(tái)處理機(jī)并行處理.一次拼接時(shí)間后，前3張圖像與后兩張圖像的拼接分別完成.再對(duì)這兩張進(jìn)行一次拼接工作完成全部圖像的拼接.總共花費(fèi)兩次拼接時(shí)間，而傳統(tǒng)方式則需3次拼接時(shí)間才能完成.

此種方法極大減少了拼接的時(shí)間消耗.沿獨(dú)立區(qū)域分割后主節(jié)點(diǎn)機(jī)發(fā)送的數(shù)據(jù)量減少，有效減少了并行處理時(shí)的數(shù)據(jù)傳輸時(shí)間.兩臺(tái)節(jié)點(diǎn)機(jī)并行處理使得原來(lái)串行方法需兩次拼接時(shí)間才能完成的工作縮減到一次拼接時(shí)間外加兩幅圖像連接的時(shí)間，而兩幅圖像連接的時(shí)間非常短，因此可以看作一次拼接時(shí)間就完成3幅圖的拼接工作量，極大提高了SAR圖像的拼接效率.

3.1 生成拼接圖

拼接工作中，投影后坐標(biāo)出現(xiàn)非整數(shù)值時(shí)，采用相鄰四像素雙線(xiàn)性插值法進(jìn)行處理，生成SAR拼接圖像.并采用Szeliski算法［6］對(duì)因相鄰兩圖像間灰度差異而導(dǎo)致的拼接縫進(jìn)行消除.

3.2 負(fù)載均衡

實(shí)驗(yàn)中使用MPI［7，8］點(diǎn)對(duì)點(diǎn)通信方式實(shí)現(xiàn)機(jī)群間的通信.由負(fù)載均衡原理可知，其主要是針對(duì)節(jié)點(diǎn)機(jī)性能不一致的并行系統(tǒng).本實(shí)驗(yàn)中由于所使用計(jì)算機(jī)配置統(tǒng)一，各節(jié)點(diǎn)機(jī)性能一致，如果采用負(fù)載均衡策略先分析節(jié)點(diǎn)性能，再對(duì)SAR圖像矩陣數(shù)據(jù)進(jìn)行分配會(huì)增加系統(tǒng)額外開(kāi)銷(xiāo)，影響并行效率，因此在負(fù)載均衡中去除了節(jié)點(diǎn)性能分析步驟.

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)使用編號(hào)為1到4的4臺(tái)節(jié)點(diǎn)機(jī)(即nd0，nd1，nd2，nd3)，所使圖像大小均為1 M，3副SAR圖像序列選取img1-img3，4副SAR圖像序列選取img1-img4，5副SAR圖像序列選取img1-img5.在機(jī)群并行平臺(tái)上，實(shí)驗(yàn)分別對(duì)圖像數(shù)為3，4，5的3個(gè)圖像序列采用基于傳統(tǒng)的兩兩分組構(gòu)建完全二叉樹(shù)方法(以下簡(jiǎn)稱(chēng)傳統(tǒng)方法)與本文所提出的基于分割的完全二叉樹(shù)模型的方法(以下簡(jiǎn)稱(chēng)新方法)進(jìn)行并行拼接實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比分析.

SAR圖像3副序列選取img1-img3進(jìn)行并行拼接實(shí)驗(yàn)，選用1號(hào)和2號(hào)節(jié)點(diǎn)機(jī)(nd0，nd1).由于傳統(tǒng)并行拼接方法對(duì)于3副圖像無(wú)法進(jìn)行兩組以下的配對(duì)，其拼接過(guò)程與串行拼接方法相同，拼接時(shí)間消耗也與串行拼接相當(dāng).因此對(duì)于3副SAR圖像序列的拼接只進(jìn)行文中拼接方法的實(shí)驗(yàn)，首先將img2分割為img2f和img1，img2l和img3兩組，分別交由nd0和nd1并行拼接.并行拼接后，nd1發(fā)送結(jié)果img2l_3到nd0，由nd0連接img2f_1與img2l_3兩幅圖像，生成完整拼接圖像img1_2_3.實(shí)驗(yàn)結(jié)果如表1所示.

表1 3副SAR圖像并行拼接實(shí)驗(yàn)結(jié)果對(duì)比表

SAR圖像4副序列選取img1-img4進(jìn)行并行拼接實(shí)驗(yàn)，同樣選用1號(hào)和2號(hào)節(jié)點(diǎn)機(jī)(nd0，nd1).使用傳統(tǒng)方法對(duì)4副圖像序列進(jìn)行并行拼接，首先將4幅圖像分為img1和img2，img3和img4兩組，然后分別交由nd0和nd1并行拼接.并行拼接拼接后nd1發(fā)送結(jié)果圖像到nd0，由nd0繼續(xù)完成img1_2和img3_4的拼接后，生成完整拼接圖像img1_2_3_4.使用文中方法對(duì)4副SAR圖像序列進(jìn)行并行拼接，首先將img1，img2和img3分為一組，img4單獨(dú)一組;然后將img2分割為img2f和img1，img2l和img3兩組后分別交由nd0和nd1并行拼接，并行拼接后nd1發(fā)送結(jié)果img2l_3到nd0，由nd0連接img2f_1與img2l_3，最后再由nd0對(duì)img1_2_3和img4進(jìn)行拼接，生成完整拼接圖像img1_2_3_4.實(shí)驗(yàn)結(jié)果如表2所示.

表2 4副SAR圖像并行拼接實(shí)驗(yàn)結(jié)果對(duì)比表

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

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

表3 5副SAR圖像并行拼接實(shí)驗(yàn)結(jié)果對(duì)比表

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

［2］鄭世友，周曄.無(wú)有效重疊區(qū)域的SAR圖像拼接方法［J］.中國(guó)圖象圖形學(xué)報(bào)，2009，14(10):2055

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

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

［5］雷英杰，霍紅衛(wèi).典型并行算法的實(shí)現(xiàn)性能分析［J］.空軍工程大學(xué)學(xué)報(bào)，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］張建文，徐瓊，王強(qiáng).基于 MPI環(huán)境的并行程序設(shè)計(jì)［J］.東華理工學(xué)院學(xué)報(bào)，2007，30(1):81-84

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