基于总变分图像恢复的半光滑牛顿法研究

The total variation (TV) regularization method has been used in image restoration process since its ability to preserve the edges in the image. However, the TV term in the regularization model is non-differentiable and nonlinear, which causes algorithmic difficulties for its numerical treatment. How to find fast and efficient numerical methods for TV minimization problem is an important research topic. In this project, we will consider the image restoration problem for both Gaussian noise model and non-Gaussian noise model. The aim of this project is to develop fast methods with local super-linear convergence for TV minimization problem by using the new methods and the new theorems in image restoration and numerical analysis. First, by using the primal-dual model and variable splitting method, the TV minimization problem is turn to a minimax problem. We will consider the optimal condition of the minimax problem and then obtain non-linear equations. We will analyze the solution of the non-linear equations and show the Newton differentiable of the correspondence function of the non-linear equations. Next, semi-smooth Newton's method will be applied to find the solution of the non-linear equations and the convergence analysis will be considered. Final, we will do numerical experiences to verify our proposed algorithms and analyze the numerical results and apply our proposed algorithms to solve other TV minimization problems. The successful implementation of our algorithms will be profitable across a broad spectrum in science, engineering where image restoration problems appear frequently. And new techniques and problems in image processing, optimization, convex analysis and numerical analysis will arise through the study of our algorithms and their convergence analysis. A better understanding of these techniques and problems will be beneficial to all fields concerned.

在基于变分模型的图像恢复问题中，因总变分函数能很好地保持图像边缘信息，它在图像恢复中广泛地用作正则项。但总变分函数不可微性造成了数值优化的困难，如何发展行之有效的快速算法来求极值是一项重要的研究课题。本项目以高斯噪声及非高斯噪声污染的图像恢复问题为研究对象，将图像恢复与数值代数的新方法、新理论有机结合，以求发展具有局部超线性收敛速度的算法，并研究相应的收敛理论。首先我们拟采用原－对偶模型以及变量分裂等框架将总变分最小问题转换成极小极大问题。再利用最优条件得一非线性方程组后，深入研究方程组解的性质，阐述方程组所对应函数的牛顿可微性。然后用半光滑牛顿法来构造快速有效的算法，研究算法的收敛性。最后运用数值结果来检验算法，分析数值行为，并推广算法到其他相关的问题。本项目的研究，需用到数值代数、数值优化、图像处理、统计等相关知识，本项目的研究不仅可丰富数值代数自身的理论，也可能推动相关学科的发展。

本项目主要目标是针对变分问题的目标函数不可微性造成了数值优化的困难，发展行之有效的快速算法。项目组采用原对偶模型及以及变量分裂等框架将变分问题转化成求解非线性方程组的问题，阐述了非线性方程组的牛顿可微性，然后应用半光滑牛顿法等算法非线性方程组的解。本项目所发展的算法避免了对变分问题的目标函数直接计算梯度函数，解决不可微性所造成的数值困难。本项目取得了一系列的成果，包括：1) 在高斯噪声污染成像的的图像恢复问题研究上，项目组研究了消除高斯噪声问题的超线性收敛速度算法及带框式约束的图像复原问题中的快速算法。其中关键性的途径是采用投影到可行集的方法来处理约束条件，而投影算子是牛顿可微的，使得应用半光滑牛顿法来求解非线性方程组成为可行。2) 在非高斯噪声污染成像模型研究上，项目组研究了均匀噪声及泊松噪声消除问题并发展了超线性收敛速度的算法。特别是在均匀噪声问题上，项目组所发展的算法比已有算法要快10～20倍。3) 在其他问题研究上，项目组进行了带线性等式约束的非负最小二乘稀疏解等问题的研究，发展了基于投影的快速算法，并将算法应用到概率布尔网络的构造问题中，其数值结果表明所发展的方法比传统的牛顿法要快。项目组成员发表期刊及会议论文13篇，编制了算法软件包，完成了预期研究目标。