New Models and Fast Algorithms for Variational PDE Image Processing

变分偏微分方程图像处理的新模型和快速算法

• 批准号: 0610079
• 负责人: Christoph Thiele
• 金额: --
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-07-01 至 2010-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0610079&HistoricalAwards=false
• 关键词: New; Models; Fast; Algorithms; Variational

The investigators will study new variational PDE-based mathematical models and fast computational algorithms for solving them. These models have emerged recently as a powerful addition to the variety of methodologies for image processing and computer vision. They are distinguished by their use of powerful mathematical tools from differential geometry, PDE and functional analysis to handle geometry regularities and sharp feature boundaries. A particularly popular example of this class of models is the total variation based image restoration model, first introduced by Rudin, Osher, and Fatemi (ROF). The ROF model has proven to be extremely successful, both in practice and in theory, and has created a lot of interest and extensions. At this point in time, there is quite a complete understanding of its theoretical properties and both its advantages and limitations. For example, the model has been extended to include deblurring, to vector-valued images, to higher order regularization involving curvatures of the underlying level sets of the image intensity function, to deal with the "stair-casing" effect, Meyer's recent "image decomposition" (as opposed to image denoising), introduction of the dual norm of TV to extract texture information, and the idea of an "inverse scale space". Taken all together, there has truly been an explosion of exciting and novel ideas recently that were inspired by the original ROF model, and the field has been enjoying a revival of interest and activities. Despite all the new developments mentioned above, there remains a major drawback of nonlinear PDE-based models: their computational efficiency. There are many reasons for this difficulty: their nonlinearity (which are designed on purpose to allow the models to recover discontinuous solutions), non-smooth objective functions (making it difficult to construct Newton-type methods to achieve quadratic convergence), and globally spatial coupling (resulting in a spatial stiffness that presents a major challenge to any solution algorithm). In this proposal, the investigators will study systematically the design of robust, scalable and efficient computational algorithms for this class models. They will make use of new paradigms involving the use of a dual formulation to recover sharp discontinuities without the usual edge-smearing numerical regularization of the primal TV formulation, the use of novel Newton-type linearizations (Newton on the primal-dual system, and use of non-smooth Newton) to obtain faster than linear convergence, and the use of novel multigrid methods to deal with the spatial stiffness. The investigators will also study the TVL1 model. This seemingly simple extension of the ROF model (replacing the L2 fidelity term by a L1 term) turns out to produce fundamentally new, and often desirable, properties: contrast invariance, better scale separation, better multiscale image decomposition, and intrinsic geometric properties which allow its use to derive powerful but simple convex optimization algorithms which can find the global optimums of several non-convex shape optimization problems. The final part of the proposal is on the application of these variational PDE-based models to image processing on manifolds. This class of problems has many important applications, especially in medical imaging (e.g. brain mapping) and computer graphics. The particular approach proposed here is a novel one based on some new conformal mapping techniques developed for brain mapping that are particularly simple to use in conjunction with PDE-based image processing models. Imaging sciences has emerged as a powerful paradigm in computational and applied mathematics. It has attracted a lot of interested from mathematicians from other fields, especially among students and young researchers. There are many applications to science, engineering, medicine and even in the entertainment industry. This proposal is on novel new ideas that are at the forefront of this relatively new field and that have aroused much interest in the field. These new developments are mathematically based and make use of powerful and subtle concepts from other parts of computational mathematics, such as duality, non-smooth optimization and multigrid methods. The focus is on key issues, such as computational efficiency, feature extraction, multiscale decomposition, global optimization, which are keys to further advances. It also leverages powerful new techniques from computational biology and combine them with PDE-based image models for new applications to the general class of problems of solving PDEs on manifolds. The ultimate goal is to produce an efficient set of algorithms for a general class of nonlinear PDE-based models that are robust, scalable, accurate, and fast.

研究人员将研究新的变分偏微分方程为基础的数学模型和快速计算算法来解决这些问题。这些模型最近已经成为图像处理和计算机视觉的各种方法的有力补充。他们的区别在于他们使用强大的数学工具，从微分几何，偏微分方程和功能分析来处理几何图形和尖锐的特征边界。这类模型的一个特别流行的例子是基于总变差的图像恢复模型，首先由Rudin，Osher和Fatemi（ROF）介绍。ROF模型已被证明在实践和理论上都非常成功，并引起了很多兴趣和扩展。在这个时间点上，有相当完整的理解其理论属性及其优点和局限性。例如，该模型已经扩展到包括去模糊，矢量值图像，涉及图像强度函数的底层水平集的曲率的高阶正则化，以处理“阶梯”效应，Meyer最近的“图像分解”（与图像去噪相反），引入TV的对偶范数来提取纹理信息，以及“逆尺度空间”的想法。总的来说，最近受到原始ROF模型的启发，出现了令人兴奋和新颖的想法，该领域一直在享受兴趣和活动的复兴。尽管有上述所有新的发展，仍然有一个主要的缺点，非线性偏微分方程为基础的模型：其计算效率。造成这种困难的原因有很多：它们的非线性（设计的目的是让模型恢复不连续的解决方案），非光滑的目标函数（使得难以构建牛顿型方法来实现二次收敛），以及全局空间耦合（导致空间刚度，这对任何解决方案算法都是一个重大挑战）。在这个建议中，研究人员将系统地研究这类模型的鲁棒性，可扩展性和有效的计算算法的设计。他们将利用新的范例，涉及使用一个双重制定，以恢复尖锐的不连续性，没有通常的边缘涂抹数值正则化的原始电视制定，使用新的牛顿型线性化（牛顿的原始对偶系统，并使用非光滑牛顿），以获得比线性收敛更快，并使用新的多重网格方法来处理空间刚度。研究人员还将研究TVL 1模型。ROF模型的这种看似简单的扩展（将L2保真度项替换为L1项）产生了全新的、通常令人满意的特性：对比度不变性、更好的尺度分离、更好的多尺度图像分解和内在几何特性，这些特性允许其用于导出功能强大但简单的凸优化算法，这些算法可以找到几个非凸形状优化问题的全局最优解。该建议的最后一部分是这些变分偏微分方程为基础的模型，流形上的图像处理的应用。这类问题有许多重要的应用，特别是在医学成像（例如大脑映射）和计算机图形学中。这里提出的特定方法是一种新的基于一些新的共形映射技术开发的大脑映射，特别是简单的使用结合基于偏微分方程的图像处理模型。成像科学已经成为计算和应用数学中的一个强大的范例。它吸引了很多来自其他领域的数学家，特别是学生和年轻研究人员的兴趣。有许多应用到科学，工程，医学，甚至在娱乐业。这一建议是关于处于这一相对较新的领域前沿并引起该领域极大兴趣的新颖想法。这些新的发展是基于数学的，并利用强大的和微妙的概念，从其他部分的计算数学，如对偶，非光滑优化和多重网格方法。重点是关键问题，如计算效率，特征提取，多尺度分解，全局优化，这是进一步发展的关键。它还利用了强大的新技术，从计算生物学和联合收割机结合起来，他们与基于偏微分方程的图像模型的新应用程序，解决偏微分方程流形上的一般类问题。最终的目标是产生一组有效的算法的一般类的非线性偏微分方程为基础的模型，是强大的，可扩展的，准确的，快速的。