一种快速的图像修复算法

处理图像修复问题的一类主要方法是建立偏微分方程,用迭代的方法来求解,其中最具代表性的算法是BSCB(bertalmio-sapiro-caselles-bellester)算法。针对BSCB模型速度很慢的缺点,提出了结合扩散率函数的选择性自适应插值算法。实验结果表明,该算法简便易行,使运算速度比BSCB模型提高了很多,同时修复的效果也有所改善。     

Fast local image inpainting based on the Allen–Cahn model

In this paper, we propose a fast local image inpainting algorithm based on the Allen–Cahn model. The proposed algorithm is applied only on the inpainting domain and has two features. The first feature is that the pixel values in the inpainting domain are obtained by curvature-driven diffusions and utilizing the image information from the outside of the inpainting region. The second feature is that the pixel values outside of the inpainting region are the same as those in the original input image since we do not compute the outside of the inpainting region. Thus the proposed method is computationally efficient. We split the governing equation into one linear equation and one nonlinear equation by using an operator splitting technique. The linear equation is discretized by using a fully implicit scheme and the nonlinear equation is solved analytically. We prove the unconditional stability of the proposed scheme. To demonstrate the robustness and accuracy of the proposed method, various numerical results on real and synthetic images are presented.     

基于张量扩散的小波域修复模型

在JPEG2000图像压缩标准中,有损传输过程中的小波系数的丢失将严重影响接收端图像的质量.为了修复丢失的或被损坏的小波系数,本文提出了一种基于张量扩散的小波域修复模型(TDWI),该混合模型将结构自适应各向异性正则与小波表示结合起来.同时推导该模型对应的Euler-Lagrange方程,并据此来分析它在像素域的几何正则性能.由于在正则项中采用了矩阵值的结构张量,该模型的扩散核的形状随着图像的局部结构特征(包括尖锐边缘、角点和各向同性区域)自适应地变化.与已有的小波域修复模型相比,本文所提模型能更自适应地、更准确地控制像素域的几何正则性,并对噪声有更强的鲁棒性.另外,本文采用了一个更加有效且适合的数值实现方法来进一步改善所提模型的修复性能.最后,给出了各种丢失情形下的实验结果来表明该模型在小波域修复性能和抗噪性能等方面的优越性.     

Evolutionary algorithms for optimization problems with uncertainties and hybrid indices

Many optimization problems in real-world applications contain both explicit (quantitative) and implicit (qualitative) indices that usually contain uncertain information. How to effectively incorporate uncertain information in evolutionary algorithms is one of the most important topics in information science. In this paper, we study optimization problems with both interval parameters in explicit indices and interval uncertainties in implicit indices. To incorporate uncertainty in evolutionary algorithms, we construct a mathematical uncertain model of the optimization problem considering the uncertainties of interval objectives; and then we transform the model into a precise one by employing the method of interval analysis; finally, we develop an effective and novel evolutionary optimization algorithm to solve the converted problem by combining traditional genetic algorithms and interactive genetic algorithms. The proposed algorithm consists of clustering of a large population according to the distribution of the individuals and estimation of the implicit indices of an individual based on the similarity among individuals. In our experiments, we apply the proposed algorithm to an interior layout problem, a typical optimization problem with both interval parameters in the explicit index and interval uncertainty in the implicit index. Our experimental results confirm the feasibility and efficiency of the proposed algorithm.     

A Hybrid Implicit-Explicit Adaptive Multirate Numerical Scheme for Time-Dependent Equations

We develop a hybrid implicit and explicit adaptive multirate time integration method to solve systems of time-dependent equations that present two significantly different scales. We adopt an iteration scheme to decouple the equations with different time scales. At each iteration, we use an implicit Galerkin method with a fast time-step to solve for the fast scale variables and an explicit method with a slow time-step to solve for the slow variables. We derive an error estimator using a posteriori analysis which controls both the iteration number and the adaptive time-step selection. We present several numerical examples demonstrating the efficiency of our scheme and conclude with a stability analysis for a model problem.     

改进的TV模型图像修复算法

分析了基于整体变分(total variation,TV)模型的图像修复算法,TV模型修复算法只使用各向异性扩散,TV模型各向异性扩散仅向图像边缘方向扩散,容易在平滑区域引入阶梯效应.提出了一种改进的图像修复算法,该算法同时结合了各向同性和各向异性扩散,利用区域频率差异实现了在不同的区域使用不同的迭代方程,有效避免了原始算法引入的阶梯效应,同时在平滑区域提高了迭代效率.Matlab环境下的仿真结果表明,改进算法的修复效果和峰值信噪比的计算结果均明显优于原始算法.     

图像修复TV模型的快速算法研究

关于图像修复的全变分（ TV）模型的求解有很多方法。在图像修复的全变分（ TV）模型中,文中针对含有非光滑项的凸优化问题提出了一种基于交替方向乘子法（ ADMM）的快速求解算法。 ADMM方法对迭代公式中具体的子问题求解过程一般采用Gauss-Seidel方法,文中通过分析TV修复模型的性质,对ADMM算法进行了相应的改进,使得具体的数值求解可以用快速傅里叶变换方法,并证明了该算法的收敛性。实验结果表明,文中所提出的新算法与采用Gauss-Seidel迭代的方法相比较,不但修复效果更好,而且修复速度更快。     

Efficient determination of the k most vital edges for the minimum spanning tree problem

We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit enumeration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.     

Bregmanized Domain Decomposition for Image Restoration

Computational problems of large-scale data are gaining attention recently due to better hardware and hence, higher dimensionality of images and data sets acquired in applications. In the last couple of years non-smooth minimization problems such as total variation minimization became increasingly important for the solution of these tasks. While being favorable due to the improved enhancement of images compared to smooth imaging approaches, non-smooth minimization problems typically scale badly with the dimension of the data. Hence, for large imaging problems solved by total variation minimization domain decomposition algorithms have been proposed, aiming to split one large problem into N>1 smaller problems which can be solved on parallel CPUs. The N subproblems constitute constrained minimization problems, where the constraint enforces the support of the minimizer to be the respective subdomain. In this paper we discuss a fast computational algorithm to solve domain decomposition for total variation minimization. In particular, we accelerate the computation of the subproblems by nested Bregman iterations. We propose a Bregmanized Operator Splitting–Split Bregman (BOS-SB) algorithm, which enforces the restriction onto the respective subdomain by a Bregman iteration that is subsequently solved by a Split Bregman strategy. The computational performance of this new approach is discussed for its application to image inpainting and image deblurring. It turns out that the proposed new solution technique is up to three times faster than the iterative algorithm currently used in domain decomposition methods for total variation minimization.     

An Inexact Alternating Directions Algorithm for Constrained Total Variation Regularized Compressive Sensing Problems

Recently, the efficient solvers for compressive sensing (CS) problems with Total Variation (TV) regularization are needed, mainly because of the reconstruction of an image by a single pixel camera, or the recovery of a medical image from its partial Fourier samples. In this paper, we propose an alternating directions scheme algorithm for solving the TV regularized minimization problems with linear constraints. We minimize the corresponding augmented Lagrangian function alternatively at each step. Both of the resulting subproblems admit explicit solutions by applying a linear-time shrinkage. The algorithm is easily performed, in which, only two matrix-vector multiplications and two fast Fourier transforms are involved at per-iteration. The global convergence of the proposed algorithm follows directly in this literature. Numerical comparisons with the sate-of-the-art method TVLA3 illustrate that the proposed method is effective and promising.     

目标跟踪算法的并行优化

目标跟踪是计算机视觉领域一个重要的研究方向,近年来学者提出了众多优秀的目标跟踪算法,但许多算法的低实时性制约了其在应用场景中的有效性。针对这些算法,提出了一个通用的跟踪模型,并针对此模型提出了一个可行的并行优化方案。之后使用SCM算法验证了所提出的并行优化方案。在四核CPU的环境下,并行后的SCM算法相比于未并行的算法取得了3.48倍的并行加速比,并且比原算法Matlab+C程序的运行速度快了约30倍,这说明了所提出的并行优化方案的有效性。     

基于分组行进算法的图像修补方法

图像修补是图像恢复研究中的一个重要内容,它的目的是根据图像的现有信息来自动恢复丢失的信息。虽然图像修补的基本思想十分简单,但是许多的图像修补算法都十分复杂,而且难于实现。快速行进算法(FMM)与水平集法(Level Set)相结合进行曲线进化是一种高效的曲线进化算法,该算法的时间复杂度是O(NlbN)。Kim提出了另一种水平集的曲线进化算法——分组行进算法(GMM),该算法的时间复杂度是O(N)。受其启发,为了更快地进行图像修补,提出了一种基于GMM算法的图像修补的新算法,并研究了对GMM算法的细节改进。为了验证算法的快速性,还给出了使用Bertalmio提出的算法、Telea提出的算法以及新算法对同一幅图片进行修补的实验结果。通过比较发现,该新算法在大幅度提高修补速度的同时,仍能保持较好的修补效果。     

An efficient split-step quasi-compact finite difference method for the nonlinear fractional Ginzburg–Landau equations

In this paper, we propose a split-step quasi-compact finite difference method to solve the nonlinear fractional Ginzburg–Landau equations both in one and two dimensions. The original equations are split into linear and nonlinear subproblems. The Riesz space fractional derivative is approximated by a fourth-order fractional quasi-compact method. Furthermore, an alternating direction implicit scheme is constructed for the two dimensional linear subproblem. The unconditional stability and convergence of the schemes are proved rigorously in the linear case. Numerical experiments are performed to confirm our theoretical findings and the efficiency of the proposed method.     

结合网函数插值与TV模型的图像修复算法

TV（Total Variation）模型用于图像修复时没有考虑缺损区域的方向信息,并且存在收敛速度缓慢以及修复质量较低等问题.针对图像上方向特征明显的条状缺损区域,提出带方向的TV图像修复算法（ADTV）.该算法分别针对4种方向（0度、45度、90度、135度）对TV算法离散格式进行改进,并引入方向判断,将缺损区域归类到此4种方向进行修复.实验结果表明,该算法充分利用了条状缺损区域的方向信息,有效提高了图像修复质量.为提高修复效率,将网函数插值分别与TV算法、ADTV算法相结合提出Net-TV算法、Net-ADTV算法.实验结果表明,结合算法不但有效减少了迭代次数,降低了时间成本,加快了收敛速度,而且提高了图像修复效果.     

综合自适应阈值与多尺度的TV图像修复方法

基于TV模型的图像修复算法具有较好的修复效果，但其对参数的选取较敏感，且运算量较大。该文提出了一种综合自适应阈值与多尺度的TV图像修复算法，该方法不仅可以提高TV图像修复模型的修复稳定性，还可以进一步压缩运算量，提高修复速度。     

An exact algorithm with learning for the graph coloring problem

Given an undirected graph G=(V,E), the Graph Coloring Problem (GCP) consists in assigning a color to each vertex of the graph G in such a way that any two adjacent vertices are assigned different colors, and the number of different colors used is minimized. State-of-the-art algorithms generally deal with the explicit constraints in GCP: any two adjacent vertices should be assigned different colors, but do not specially deal with the implicit constraints between non-adjacent vertices implied by the explicit constraints. In this paper, we propose an exact algorithm with learning for GCP which exploits the implicit constraints using propositional logic. Our algorithm is compared with several exact algorithms among the best in the literature. The experimental results show that our algorithm outperforms other algorithms on many instances. Specifically, our algorithm allows to close the open DIMACS instance 4-Fullins_5.     

基于P-Laplace算子的小波域图像修补模型

本文研究如何利用不完整的小波系数来恢复原始图像. Chan, Shen 和 Zhou 已经提出了一种基于整体变分 (total variational, TV) 模型的小波域图像修补算法. TV 模型的主要优点是可以保持图像的边缘, 但该模型在平滑区容易产生阶梯效应, 使图像的修补效果不是很理想. 为了克服这个缺陷, 本文首先从局部坐标角度分析了TV模型与p-Laplace算子的物理意义, 从本质上说明了 p-Laplace 算子的扩散性能优于 TV 模型.然后给出了一种基于 p-Laplace 算子的小波域图像修补模型. 该模型不仅有效降低 TV 模型引入的阶梯效应, 而且能保持图像的边缘, 用较少的运算量得到比 TV 模型更好的修补效果. 实验结果表明, 该模型在运算时间和修补效果上都具有更好的综合性能.     

采用顺序修复的样本例图像修复算法

本文提出了一种采用顺序修复的样本例图像修复算法,该方法在原Criminisi经典图像修复算法的基础上对修复顺序进行新的尝试.原Criminisi经典算法的修复顺序通过计算优先级得出,随着修复的深入优先级逐渐趋近于0,导致算法失去作用.为解决该问题,本文采用顺序修复的方法来代替优先级决定顺序,避免出现算法失去作用的情况;同时本文提出的“倒L”型样本模板来增强结构的传播能力、提高匹配的正确率.实验结果证明,本文的修复算法相对Criminisi算法具有优势并取得很好的修复结果.     

New Variational Formulations for Level Set Evolution Without Reinitialization with Applications to Image Segmentation

Interface evolution problems are often solved elegantly by the level set method, which generally requires the time-consuming reinitialization process. In order to avoid reinitialization, we reformulate the variational model as a constrained optimization problem. Then we present an augmented Lagrangian method and a projection Lagrangian method to solve the constrained model and propose two gradient-type algorithms. For the augmented Lagrangian method, we employ the Uzawa scheme to update the Lagrange multiplier. For the projection Lagrangian method, we use the variable splitting technique and get an explicit expression for the Lagrange multiplier. We apply the two approaches to the Chan-Vese model and obtain two efficient alternating iterative algorithms based on the semi-implicit additive operator splitting scheme. Numerical results on various synthetic and real images are provided to compare our methods with two others, which demonstrate effectiveness and efficiency of our algorithms.     

结合纹理结构的分数阶TV模型的图像修复

目的 TV（total variation）模型在图像修复时易导致图像中具有弱导数性质的纹理和边缘细节等信息变得模糊,为了克服该缺陷,分数阶微分被引入到TV模型中,但传统的分数阶TV模型对弱边缘和弱纹理等细节信息的保持仍不够理想,并且没有充分利用图像已知区域的先验信息,修复精度仍有待提高。方法 针对该问题,提出结合纹理结构信息和分数阶TV模型的图像修复算法。改进的模型在分数阶TV模型求解时,在梯度计算过程中增加了一个极小值,克服了正则项和数据项在零点处的不可微,从而增加了模型的稳定性。再则改进的模型根据图像已知区域的先验信息确定待修复区域的纹理方向,从而更好地保持了图像中的纹理细节和弱边缘信息。结果 将本文算法与3种修复效果较好的算法进行对比,采用客观评价指标：均方差（MSE）、峰值信噪比（PSNR）和差值图像进行评价,实验结果表明本文算法在不同的纹理图像修复中均取得较好的效果,如对标准图像库中的Barbara和Lena图像以及岩石图像进行修复后,与原始TV模型相比,它们的峰值信噪比分别提高5.94%、8.07%和3.85%,灰度均方差分别降低48.66%、65.89%和35%;与分数阶TV模型相比,它们的峰值信噪比分别提高4.17%、8.59%和1.81%,灰度均方差分别降低37.90%、68.00%和18.68%。结论 提出的模型相对于原始的TV模型和分数阶TV模型,均能有效地提高图像修复的精度,适合于包含较多弱纹理和弱边缘信息的图像修复,该模型是TV模型的重要延伸和推广。