非线性多重网格反演的一般框2重点

1、非线性多重网格反演的一般框架主要分为五个部分 1.介绍 2多重网格反演框架 反问题 、多重网格的反演算法、固定网格反演、多重网格收敛的反演。稳定泛函。 3. 光扩散层析成像中的应用4数值结果。提出了评价模型所需的分辨率 、多重网格性能评价。摘要A variety of new imaging modalities, such as optical diffusion tomography, require the inversion of a forward problem that is modeled by the solution to a 3-D partial differentia

2、l equation. For these applications,多种新的成像方式，如光扩散层析成像，要求正问题，采用求解三维偏微分方程反演。这些应用程序，图像重建是特别困难的。image reconstruction is particularly difficult because the forward problem is both nonlinear and computationally expensive to evaluate.因为提出的问题是非线性和评价计算昂贵的。在本文中，我们提出了非线性多重网格反演是适用于各种各样的反问题的一般性框架。多重网格反演算法结果的递归多重网

3、格技术的优化问题的求解逆问题中的应用。该方法通过动态调整目标泛函在不同的尺度，that they are consistent with, and ultimately reduce, the finest scale cost functional. 他们是一致的，并最终减少，细尺度函数值。 在这种方式中，多重网格反演算法有效地计算解决所需的精细尺度反演问题。重要的是，新的算法可以大大减少计算，因为在正向和反问题更粗的离散化在较低的分解。 这个方法被广泛应用，贝叶斯光扩散层析，广义高斯马尔科夫随机场图像先验模型。展示了非常大的计算节省潜力。数值数据也表明了鲁棒收敛一系列的初始条件为非凸优化问

4、题。随机场图像的先验模型显示了非常大的计算节省的潜力。数值数据也表明了一系列的非凸优化的初始条件的鲁棒收敛problem.问题。关键词：多重网格算法、反问题、光扩散层析成像、多尺度 一介绍 一大类图像处理的问题，如模糊，高分辨率的渲染，图像恢复，图像分割，与断层运动分析，逆问题的解决，通常，这些反问题的数值解法是计算能力的要求，特别是当问题必须制定在三维上。最近，一些新的成像方式，如光扩散层析成像（ODT） 和电阻抗断层成像（EIT），备受关注，例如光扩散层析成像在安全上有很大的潜力，非侵入性的医疗诊断方法与化学特异。然而，这些反问题有关联的新模式，目前有大量的困难挑战，首先，正演模型取决偏微

5、分方程（PDE）描述的解决，(PDE) which is computationally demanding to solve. Second, the unknown image is formed by the这是计算能力的要求。第二，未知的图像决定于偏微分方程的系数，从而正演模型是高度非线性的，即使本身是线性偏微分方程。最后，这些问题通常是由于固有的三维向三维的能量传播散射介质模型。因为自然界中的许多现象的数学描述偏微分方程反问题，也有许多其他有类似的计算上的困难，包括微波tomography 7, thermal wave tomography 8, and inverse scatt

6、ering 9.断层，热波成像和逆散射。要解决的逆问题，大部分的算法，如共轭梯度（CG），最速下降（SD），和迭代坐标下降（ICD） 10 使用固定网格执行所有计算。尽管巨大的进步已经减少了计算的复杂性，这些固定网格的方法，计算成本仍然十分关注。也许更重要的是，fixed grid optimization methods are essentially performing a local search of the cost function固定的网格优化方法本质上是执行的成本函数的局部搜索，and are therefore more susceptible to being trapp

7、ed in local minima that can result in poorer quality因此更容易陷入局部极小值，会导致质量较差reconstructions.重建。多尺度技术已经减少反问题的计算得到了广泛的研究。即使是简单的多尺度的方法，如初始化的精细分辨率迭代粗的解决方案，已被证明是在许多成像问题的有效。小波已被研究了贝叶斯断层，和wavelet and multiresolution models have been applied in Bayesian formulations of emission tomography小波变换和多尺度模型已应用于发射断层扫描的贝叶

8、斯公式21, 22, 23, 24 and thermal wave tomography 25. For ODT, a two resolution wavelet，和热波成像。光扩散层析成像ODT，一个二维分辨率小波decomposition was used to speed inversion of a problem linearized with a Born approximation 26.分解是用来加速问题线性化近似反演一出世。多重网格方法是一类特殊的多尺度算法，通过递归的方法操作上的数据在不同的分辨率，使用嵌套的迭代和粗网格校正的思。多重网格算法最初引起兴趣的一种方法为有效

9、地消除光误差分量求解偏微分方程，这并不总是阻尼fixed-grid relaxation schemes. In particular, the full approximation scheme (FAS) of Brandt 27 can固定网格松弛方案。特别是，全近似格式（FAS）勃兰特 27 能be used to solve nonlinear PDEs. Multigrid methods have been used to expedite convergence in various是用来解决非线性偏微分方程。多重网格方法已被用来加速收敛的各种image processing

10、problems, for example, lightness computation 33, shape-from-X 33, 34,图像处理的问题，例如，亮度计算 ，形状从-X ，optical flow estimation 33, 35, 36, 37, 38, signal/image smoothing 39, 40, image segmentation光流估计，信号/图像平滑，图像分割40, 41, image matching 42, image restoration 43, anisotropic diffusion 44, sparse-data图像匹配，图像复原，各

11、向异性扩散，稀疏的数据surface representation 45, interpolation of missing image data 40, 46, and image binarization表面表征，丢失的图像数据的插值，和图像二值化。最近，多重网格算法已经被用来解决图像重建问题。博曼和绍尔表明非线性多重网格算法可以应用于贝叶斯反演问题。本文采用非线性多重网格技术计算最大后验概率（MAP）非高斯先验分布和非负约束重建。麦考密克和韦德应用多重网格方法的线性化的企业所得税问题，与博尔恰used a nonlinear multigrid approach to EIT based

12、 on a direct nonlinear formulation analogous to FAS用非线性多重网格方法的基础上制定的非线性EIT直接类似于Fasin nonlinear multigrid PDE solvers. Brandt et al. developed multigrid methods for EIT 50 and在非线性多重网格求解偏微分方程的求解器。勃兰特等人。用于电阻抗断层成像EIT的多重网格方法atmospheric data assimilation 51, and applied multigrid or multiscale methods to

13、various numerical大气数据同化，并应用多重网格或多尺度方法的各种数值computation problems including inverse problems 52, 53. Johnson et al. 54 applied an algebraic计算问题，包括反问题。约翰逊等人。应用代数multigrid algorithm to inverse bioelectric field problems formulated with the finite-element method.多重网格算法的逆生物电场问题的有限元法的制定In 55, 56, Ye, et al.

14、 formulated the multigrid approach directly in an optimization framewo等。制定了多重网格方法直接在一个优化框架，and used the method to solve ODT problems. In related work, Nash and Lewis formulated multigrid使用的方法来解决口腔问题。在相关的工作，纳什和刘易斯制定了多重网格algorithms for the solution of a broad class of optimization problems 57, 58. Imp

15、ortantly, both对于广泛的一类优化问题的求解算法，重要的是，无论是the approaches of Ye and Nash are based on the matching of cost functional derivatives at different你们和纳什方法的基础上在不同的成本函数导数的匹配scales.尺度。在本文中，我们提出了一个方法，我们称之为多重网格反演，多重网格反演是应用非线性多重网格优化的逆解的一般方法问题。在我们的方法中一个关键的创新就是正向和逆解决模型是不同的。这使得我们的方法特别适合于反问题的解决方案with PDE forward model

16、s for a number of reasons:在偏微分方程模型有很多原因：1.通过粗网格解决提出的偏微分方程模型，计算量大大减少，在以前的方法，建立了偏微分方程在最好的网格只解决了。这意味着粗网格更新是计算复杂性，或一种线性逼近was made for the coarse grid forward model 48, 55, 56.粗网格正演模型。2.粗网格模型可以通过正确离散偏微分方程模型，保留正向模型的非线性特性。3. 各种各样的优化方法可用于在每个网格求解反问题。因此，常用的方法，如预条件共轭梯度和/或伴随分化63, 64 can be employed at each grid

17、 resolution.可以在每个网格分辨率。多重网格反演方法目的是解决反问题例如光扩散层析成像（odt）和电阻抗断层成像（eit），它普遍适用于任何反问题，该模型可以自然地represented at differing grid resolutions.表示在不同的网格决议。多重网格反演方法是制定一个优化框架定义一个序列在降低分辨率优化泛函。要有良好的表现方法为了正确的细网格的收敛性，它是必不可少的，在不同尺度下的目标泛函be consistent.是一致的。为了实现这一目标，我们提出了一个适应的粗网格递归泛函方法，这保证了多重网格的更新将不会改变一个确切的解决方案的细网格的问题，即准确的

18、细网格的解决方案，始终是一个固定点的多重网格算法。此外，我们证明了在一定条件下，非线性多重网格反演方法是保证产生monotone convergence of the fine grid cost functional. We present experimental results for the ODT细网格目标泛函的单调收敛性。我们目前的实验结果的ODTapplication which show that the multigrid inversion algorithm can provide dramatic reductions in应用表明，多重网格反演算法提供了急剧减少com

19、putation when the inversion problem is solved at the resolution necessary to achieve a high quality计算，当反演问题的解决在分辨率要达到高质量reconstruction.重建。 本文的结构如下。第二部分介绍了多重网格的一般概念反演算法，并讨论了其收敛性1-4节。在第三节中，我们说明了的多重网格反演方法在ODT问题中的应用，及其数值结果在第四节的最后，第五是结语。二、多重网格反演框架 在本节中，我们概述的正则化反演方法，然后制定一般多重网格反演方法。A反问题 设y是一个随机向量（实数或复数）测量，

20、让x是一个有限维向量表示未知量，在我们的例子中的图像，以重建。任何逆问题，有一个正演模型给出了 (1) 等价于 which represents the computed means of the measurements given the image x. 它代表了计算机测量的装置，给出了图像X。 逆问题很多，如ODT，正演模型是由偏微分方程确定离散偏微分方程的系数给出的解决方案。我们假设测量是有条件的高斯给定，所以 (2) 定义是正定加权矩阵，P是测量维度，参数成比例的噪音方差，请注意，测量噪声covariance matrix is equal to d协方差矩阵相等，当数据值是实数，

21、P等于向量Y的长度，但当测量是复数时，则P等于Y维数的两倍。Our objective is to invert the forward model of (1) and thereby estimate x from a particular measurement vector y. 我们的目标是将正向模型（1），从而根据特定的测试向量估计，这有很多方法执行估计，包括最大后验概率（MAP）的各种方法的估计，估计最大似然，和正则化反演。所有这些方法通过最有目标泛函去计算的值。 （3）其中是稳定函数规范的逆，注意在最大后验方法中，where p(x) is the prior distribu

22、tion assumed for x. 其中p（x）是经验分布假设为x.我们将估计的噪声方差参数和x的共同最大化（3）式对求导，另得到 在把代入（3）中下降常数产生目标泛函优 （4）我们一般认为是一个连续可为的函数。我们发现，在和的联合优化具有许多重要的优点，首先，在许多应用中解决多重网格，测量噪音是事先不知道的，相对噪声的大小可能是已知的。在这样的场景中，它可以同时估计。值随着x值。更重要的是，我们发现，有一个the logarithm in the expression of (4) makes optimization less susceptible to being trapped

23、in local对数在表达（4）中，优化而使人陷在局部最小值minima 67. In any case, the multigrid methods we describe are equally applicable to the case wh。多重网格方法在任何的情况下，我们描述的情况是同样适用于固定的。在这样的情况下，目标泛函是由代替方程（4）。B.固定网格反问题 当目标泛函（4）制定，反是通过解决相关的优化问题的计算,反问题计算用来解决合并优化问题 （5）大多数优化算法，例如共轭梯度（CG），最速下降（SD），和迭代坐标下降（ICD），通过迭代最小目标泛函，我们解释一个简单的迭代，

24、例如固定网格优化： 其中成是目标泛函最小值，是初始值，是更新值，我们通常假定固定网格算法降使目标泛函在每次迭代值下降，除非的初始值是目标泛函的局部最小值。因此我们说这个更新的算法单调，当严格不等式 rc(xinit) 6= 0 or xupdate 6= xinit. 循环应用一个固定网格优化，产生一序列单调递减的估计值，因此，通过迭代公式（6）可以近似解决（5）。 在许多反问题中，例如，光扩散层析成像（odt）正演模型计算需要解决三维偏微分方程，我们必须用计算机来描述数值解，虽然精细离散网格是可取的因为它降低了建模误差和增加最终图像的分辨率，these improvements are ob

25、tained at the expense of a dramatic increase in computational cost.在计算成本大幅增加费用得到了这些改进。the computational cost typically increases by a factor of 8 each time the resolution is计算成本通常会增加8的每个时间分辨率是一个因素增加了一倍。在精细的分辨率问题的解决也趋于收敛速度慢。例如，许多固定网格算法如ICD2有效地消除误差在高空间频率，但低频率errors are damped slowly 29, 10.误差衰减缓慢。C.多重

26、网格反问题的算法在本节中，我们得到了多重网格反演的基本算法的优化求解(5).设表示的细网格的图像，让是的粗分辨率用表示，随着最佳网格采样周期网格采样周期。根据细分变率得到粗分辨率，关系式： 是线性抽取矩阵（限制算子），定义为类似线性插值矩阵，我们首先定义粗网格目标泛函，形式类似于式子（4），由尺度指数量为， （7）注意正演模型，和稳定泛函都用来评价尺度q的，很重要，因为评价提出的模型在低分辨率的基本.减少了计算，因变量的数量也减少。一般D的具体形式从物理问题解决的结果用适当的网格间距在第三节中，我们将给出一个典型的例子是光扩散层析成像(ODT)where D is computed by di

27、scretizing the 3-D PDE using agrid spacing proportional to 2q.其中是通过离散的三维偏微分方程（PDE）使用间距成正比，计算模型. 量在（7）表示一个调整测量向量scale q.尺度q，请注意，在这项工作中，我们假设和是相同的长度在每一个尺度，.因此，数据分辨率对不起作用，稳定泛函在固定尺度上选择的最佳近似的细尺度的泛函。我们给这样一个稳定的一个例子，在第二部分e中， 在本节余下的部分，我们解决了目标泛函的每个尺度能够吻合的连续解，像这样，我们定义调整目标泛函， （8） 其中是一个行向量，引入他是为了校正目标泛函的梯度.所有的量tak

28、e on their fine scale values and A在细尺度值呈现因此我们的目标是导出关于和符合目标泛函的粗细尺度的递推表达式。 设是网格q的局部解，我们想要用这个解循环固定网格优化粗网格，利用这个结果矫正细网格结果，粗网格更新为 （9）其中是由减少形成的初始条件，是更新后的值。现在我们可以利用这个结果来更新更细的网格解决方案。我们通过插值来改变粗尺度解通过 （10）理想情况下，新解和旧解一样好，具体来说，当固定网格算法单调时，我们希望，然而，这不一定，如果目标泛函不一致，粗尺度纠正很容易的就远离了最优解。这种不一致性问题，如果粗、细规模目标泛函等价于are equal wit

29、hin an additive constant.This means we would like等价于内加常数。这意味着我们要 （11）持有的所有值然后，我们的目标是选择一个粗尺度目标泛函符合精细化目标泛函描述（11）。我们通过的合理选择。第一，我们加强了模型和测量之间的初始误差是相同的在粗和细尺度的条件下，给予 （12）产生更新值 （13）直观的说，括号里这项是正演模型与分辨率不吻合的惩罚项。 接下来，我们分情况介绍执行条件，粗细尺度目标泛函等同于当前值，确切的执行情况为在粗网格与细网格目标泛函梯度在和上相同，更确切地说 （14） 图一是校正项的作用，(a) 当粗细网格目标泛函的梯度在初始

30、值不相等时，那么由粗网格迭代得到的很能会增加细网格的值。（b）当粗细网格目标泛函的值吻合时，那么一个经由适当选择的粗网格目标泛函就可以确保粗网格迭代减少细网格目标泛函的函数值。是指由泛函的梯度所构成的行向量，这个条件是最优解是多重网格反演方法的固定点的必要条件，在第二部分第四小节具体给出如何使用这个条件及其他假设来证明多重网格的收敛性。式子（14）需要注意的是插值矩阵乘在梯度向量的右边，它实际上起到的是限制算子的作用，无论限制算子还是延拓算子式子（14）都成立。由式子（14）得到 （15）是未调整的目标泛函在式子（7）中，通过估计梯度值通过式子（15）得到 （16）与是在粗细网格上未调整目标泛

31、函的梯度，分别给出 （17） 更新二重网格 重复次 固定网格更新细网格更新 抽取 用（13）计算 用（16）计算 重复次 固定网格更新粗网格更新 粗网格校正返回次 固定网格更新细网格更新 返回/回送结果图2，二重网格反问题算法的规范代码，符号是用来使目标泛函明确的依赖与 （18）H是共轭转置算子，表示正演模型的梯度或者？ （19） （20)作为本部分的总结，图2展示了伪代码实施二重网格算法，在这个图像中，我们使用符号符号是用来使目标泛函明确的依赖与，注意,和固定网格迭代之前完成粗网格修正,可以通过和调整算法的收敛速度。多重网格V型算法是通过简单地取代了固定网格更新解决二重网格算法的递归子程序调

32、用,在图像3（b）展示了伪代码，通过多重网格迭代算法我们可以解出式子（5），正如图像3（a）所示，多重网格-V型算法算法的然后从细到粗与细的决议迭代，主要的（） 初始值由背景经验值 选择一些固定网格迭代和重复直到收敛 多重网格v型 （a）多重网格V型重复次 固定网格更新细网格更新若，返回/如果是粗网格尺度，返回结果 抽取 用（13）计算 用（15）计算 多重网格v型粗网格更新 粗网格校正返回次 固定网格更新细网格更新 返回/回送结果 （b) 规范伪代码（a）是解决多重网格反问题的重要路线，（b）是多重网格-V算法的子程序，多重网格-V算法相似于二重网格算法，但是递归调用自身进行粗网格迭代。D.

33、多重网格繁衍的收敛性多重网格反演方法可以看做是这样一种方法：即通过暂时性的将原始代价泛函替换成较低分辨率下的代价泛函，以达到降低浅在高额计算量的目的，实际上，为了加快或简化运算过程，学者们已经设计出一大类依赖于所谓替代范围进行利用的最优化方法，或将他们称之泛函替代法，在EM算法中采用的Q函数，就是作为一种典型的替代泛函而为人周知，最近，De Pierro发现同样的基本方法可以应用于断层问题的方式,允许并行更新计算像素的处罚ML重建70,71。De Pierro的方法已经被用来证明收敛和在断层允许并行更新ICD方法72,73。然而，应用在多重网格反演方法中的替代泛函有一个不同于其他独特泛函的独特优势：