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