图割算法在相位解缠中的应用
摘要： 相位解缠一直以来是干涉测量领域中的一个重要研究方向。传统的相位解缠算法的解缠结果易受到噪声或者截断相位的影响。为了解决上述问题，提高解缠精度，在模拟的存在截断相位缺陷的数据上，建立马尔科夫能量模型，推导出能量函数，使得相位解缠变成一个求解全局最优化的问题，利用图割理论求解。实验结果表明，图割理论能够很好的完成能量函数的优化，解缠结果在抗噪性以及精度上，比起传统的解缠算法都有着一定优势。那么就意味着，该方法在相位解缠方面有着重要的研究价值和宽阔的应用前景。
Abstract： Phase unwrapping is an important field in
interference measurement. The traditional phase unwrapping
algorithms are easily affected by noise or discontinuous phase.
In order to solve the problems and improve solution accuracy，
establishing markov energy model， getting the energy
function， making the phase unwrapping into a global
optimization problem on the datas of simulation of
discontinuous phase， using the graph cuts solve the problem.
The experimental results show that the optimization of energy function has a good global solution by the theroy， compared
with the traditional algorithms， the results has an advantages in
noise resistance and precision. That is to say， this method has
important research value and application prospect in phase
unwrapping.
关键词： 相位解缠；马尔科夫随机场；图割；截断相位
Key words： phase unwrapping；Markov random field；graph cuts；discontinuous phase
中图分类号：TN958 文献标识码：A 文章编号：1006-4311（2015）11-0202-04
0 引言
在干涉合成孔径雷达（InSAR）和核磁共振（MR）成像中，由于系统的原因，所得到的与需要的物理量相联系的干涉测量相位值均被缠绕在（-π，π]之间，与真实相位之间存在相位周期模糊，恢复失去的相位周期的过程称为相位解缠或者相位解包裹（Phase Unwrapping）[1]。
目前常用的相位解缠方法可以分为四类：①路径积分法[2]；②最小范数法[3]；③网络规划法[4]；④贝叶斯法[5]。
最小范数法[3]的思想是求一个解缠结果使得该结果与缠绕相位之间的差的p范数最小。该方法对解缠结果进行了平滑，且当存在截断相位的时候得不到有效的解。 一般路径积分法解缠能否成功依赖于Itoh条件是否成立[2]，Itoh条件即是假设相邻像素点的相位差不超过π。如果不满足上述的假设，根据不同路径的积分解缠结果就可能不同，因此发展出了Goldstein枝切线的方法和基于质量图指导的方法。但是由于Goldstein枝切法也存在对图像的间断适用范围[6]以及基于质量图的方法过于的依赖质量图的质量等问题而限制了上述两种方法的应用。
本文方法是结合贝叶斯决策的网络规划方法。就目前来看，国内利用马尔科夫随机场和贝叶斯决策论结合图割理论进行相位解缠的文献并不是很多，对此，本文作了深入研究，结果表明了，利用该方法进行相位解缠较传统的相位解缠有着很大优势。
1 MAP-MRF能量函数的建立
2 最大流/最小割算法对能量函数的优化
2.1 图的构造
由于利用图割方法进行优化，所以在使用该方法之前，应该先将能量函数对应到相应的网络图中。
关于构图的方式，我们将图的节点和图像的像素一一对应，另外构造两个特殊的点：源点s和汇点t。每个节点分别与源点和汇点均由一个有向边连接，称为t-links，其边上权值代表与源点和汇点的相似程度。相邻节点之间由一个有向边连接，称为n-links，其反应的是平滑性，边上权值代表了节点之间的不相似程度，即不连续性。若用G =（V，E）表示。其中E代表边集，V代表节点集，V={s，t，v1，v2，…，vn }。
2.2 最大流/最小割算法
根据能量函数到网络图的构造过程可以知道，对能量函数最小值的求解就是在网络图中求解最小割，其计算方法主要分为两大类[11]：推进重标记（Push relabel）和增广路径（Augmenting paths）法。本文主要对路径增广法进行了研究实验。
2.2.1 最短增广路法
最短增广路算法[11]是对一般增广路方法也称Ford-Fulkerson方法（2F）的改进，该方法是图论中网络流的计算方法，广泛的应用于金融，通讯，社会管理，交通管理等领域[12]。
该算法的思路是：每次在层次网络中找一条含弧数量最少的增广路进行增广。具体步骤如下：
①初始化容量网络和网络流。 ②构造残留网络和层次网络，若汇点不在层次网络中，则算法结束。
③在层次网络中不断的应用广度优先搜索（BFS）增广，知道层次网络中没有增广路为止，每次增广完毕，在层次网络中要去掉因改进流量而导致饱和的弧。
④转到步骤②。 上述步骤②③执行一次称为一个阶段，每个阶段中首先根据残留网络建立层次网络，然后用BFS在层次网络中进行增广，直到流量出现阻塞。该阶段增广完毕后，进入下一个阶段，不断重复，直到汇点不在层次网络中为止。
直到此处，已经完成了结合马尔科夫随机场理论和图论中最大流最小割算法进行相位解缠的完整说明，同时由后面的实验证明，该方法有着很高的解缠精度。
2.2.2 改进的增广路算法
虽然最短增广路径法可以得到精度很高的解缠结果，但是由于该算法的时间复杂度过大，在相位解缠中实际应用价值并不是很高，因此对最短增广路径算法进行改进，以两棵搜索树S和T为搜索起点，终端S和T分别以源点Vs和汇点Vt为根。搜索树中的所有连接父节点和子节点的边都是可增广的不饱和边。搜索树中的节点还可以继续细分为主动（active）和被动（passive）节点。而主动节点是搜索树最外部的活跃节点，被动节点是搜索树内部的节点。主动节点可以吸收、抚养新的子节点来使得搜索树“生长（grow）”。因此主动节点变为了被动节点，而新吸收的子节点变为主动节点。被动节点不能再生长。图2为一个基本的搜索单元图。
设S树最外围的当前活跃节点是图中的灰色点，此时其权值一定是大于0的。下面开始寻找增广路径。这里可以假定事先给定一种优先的搜索顺序，本文以竖直方向搜索优先，且综合考虑A（V）和B（H）的取值情况，在V>0的情况下，若A0，同样地，若为最后一列，则开始下一个正节点的搜索；若不是最后一列，且B不大如0时，S向右操作一位，B>0时，开始下一个正节点的搜索。在V=0的情况下，若H=0，开始下一个正节点的搜索，若H>0，且B不大于0，S向右操作一位，反之，S向下操作。
.1 传统方法的解缠结果
3.2 图割方法的解缠结果
从目视上就可以看出，在带有噪声的间断相位解缠中，Goldstein枝切法已经无法正确的进行解缠了，这是由于噪声的存在导致残差点的密集分布已使得这类方法无法进行解缠了。
而在FFT无加权方法的相位解缠中，由于算法本身的问题，使其在间断相位处无法得到有效值。
对基于相位导数方差图指导的路径积分法来说，虽然比起前两种传统解缠算法在噪声抑制上面表现得比较好，但是仍然逊于图割的解缠算法，同时，通过下表可知，在解缠精度方面，图割方法也远好于基于相位导数方差图指导的路径积分方法。
由于Goldstein枝切法和最小二乘法已经不能有效解缠，因此这两种方法在精度比较方面已经失去了意义，所以上表只列出了质量图指导法和图割方法在精度上的比较。 4 结论
通过模拟带噪声截断相位数据的解缠对比实验发现，图割理论中增广路算法在相位解缠中比起传统的算法在精度方面有了巨大的提升之外，改进的增广路算法运算时间也具有优势，结合以上两点表明，图割理论在相位解缠应用中具有很大的潜力。同时由于图割理论可以很好的对能量函数进行优化，那就表明，在计算机视觉的其他方面该方法也有具有研究价值。
参考文献：
[1]李笑郁，毛士艺.干涉SAR与MRI中的相位展开算法研究[J].中国体视学与图像分析，2001，6（4）：193-197.
[2]Itoh K. Analysis of the phase unwrapping algorithm[J].
Applied Optics，1982，21（14）： 2470-2470.
[3]BONE D J.Fourier fringe analysis： the
two-dimensional phase unwrapping problem [J]. Applied
Optics， 1991，30（25）：3627-3632.
[4]Costantini M. A novel phase unwrappi-ng method based
on network progra-mming[J]. Geoscience and Remote Sensing，
IEEE Transactionson， 1998， 36（3）： 813-821.
[5]J. Dias and J. Leitao， “The ZπM algorithm for
interferometric image reconstruction in sar/sas，” IEEE
Transactions on Image Processing， 2001， Submitted. [6]曾凡光，吴光敏，陈剑鸣.Goldstein 枝切法对存在间断相位缺陷的解缠研究[J].激光技术，2014，38（3）：335-341.
[7]Ying L， Liang Z P， Munson Jr D C，etal. Unwrapping
of MR phaseimages using a Markov random field model[J].
Medical Imaging， IEEE Transactions on， 2006， 25（1）：128-136.
[8]Li S Z. Markov random field modeling in image
analysis[M]. Third ed.London：Springer， 2009：21-29.
[9]V. Kolmogorov， R. Zabih. What energy functions can
be minimized via graph cuts [J]. IEEE Transactions on， Pattern
Analysis and Machine Intelligence， 2004， 26（2）： 147-159.
[10]Bioucas-Dias J M， Valad o G. Phase unwrapping via
graph cuts[J]. Image Processing， IEEE Transactions on，
2007， 16（3）： 698-709.
[11]王桂平，王衍，任嘉辰.图论算法理论、实现以及应用[M]. 北京：北京大学出版社，2011：246-260.
[12]白睿.最大流及最小费用的研究[D].南京：南京邮电大学，2012：1-5.