英文翻译

An Efficient GEM Model for Image Inpainting Using a New Directional Sparse Representation: Discrete Shearlet Transform

一种新的定向稀疏法表示的GEM模型的高效图像修复方法：离散剪切波变换法

R.Gomsthi, A.Vincent Antony Kumar

Abstract-In this paper, we present a novel Expecation Maximization(EM) algorithm for automatic

color image inpainting using a new discrete multi scale directional sparse representation called the

Discrete Shearlet Transform(DST). It is now acknowledged that the traditional wavelets are not very effective when dealing the multi dimensional signals having distributed discontinuities such as edges. To achieve a more efficient representation one has to use basis elements with much higher directional sensitivity. Using a Shearlet Transform combines the power of multi scale methods with a unique ability to capture the geometry of multidimensional data and is optimally efficient in representing images with edges. The inpainting can be viewed as an interpolation or estimation problem with missing data. Towards this goal, we propose the idea of using Expectation Maximization (EM) algorithm in a Bayesian Framework, which is used to recover the missing samples using a sparse representation-Discrete Shearlet Transform (DST). We first introduce an easy and efficient sparse representation-Discrete Shearlet Transform (DST) based iterative algorithm for image inpainting. And then, we derive its convergence properties. We can demonstrate that this algorithm based on a new sparse representation-

Discrete Shearlet Transform is very competitive in image inpainting applications both in terms of performance and computational efficiency.

Keywords – Sparse representation, Wavelet, Shearlet, image inpainting, Optimization, Expectation Maximization.

摘要：在本文中，我们为了自动彩色图像修复提出了一种新颖的期望最大化算法，利用一种新的离散多尺度定向稀疏表示称为离散剪切波变换法（DST）。众所周知，传统的小波已经不能有效处理如边缘的分步式不连续的多维信号。为了实现更有效的表达，必须使用基础元素

与更高的定向敏感性法。用剪切波变换使多尺度方法的能力与一种能够捕捉多维数据的几何形状的独特的能力，是代表图像边缘优化高效的方法。待修复的部分可被看作是插值或者估计问题与数据缺失。对于这一目标，我们提出这种在叶贝斯框架上利用期望最大化的算法，就是用稀疏表示来恢复丢失的样本的方法—离散剪切波变换法（DST）。首先介绍一个简单而有效的，以图像修复的迭代算法为基础的稀疏表示—离散剪切波变换法（DST）。然后，我们推导出它的收敛性。我们可以证明，这种基于新的稀疏表示—离散剪切波变换的算法在图像修复中的应用，无论是在性能方面还是计算效率上都具有一定竞争力。

关键词：稀疏表示，小波，剪切波，系统修复，优化，期望最大化。

I. INTRODUCTION

1.简介

Image Inpainting refers to filling in missing or damaged regions (like cracks or scars) in images. In fine art museums, inpainting of degraded paintings is traditionally carried out by professional artists and usually very time consuming, not to mention the risk of completely destroying a precious and world-unique ancient painting due to direct retouching.

图像修复是指填补图像缺失或受损区域（如裂缝或疤痕）。在美术博物馆，专业艺术家对图像进行传统的图像修复，通常很费时，更不用说由于直接修复而造成图像完全被破坏的风险。

Mathematically speaking, inpainting is essentially an interpolation problem, and thus directly overlaps with many other important tasks in computer vision and image processing, including image replacement, dis-occlusion, zooming and super resolution, and error concealment. The current work has been motivated and inspired by the error concealment application, which is to automatically recover lost packets information during transmission processes.

从数学角度来说，图像修复本质上是一个插值问题。从而在计算机视觉和图像处理上直接与许多其他重要的任务相重叠，包括图像转换、图像修补、缩放、超分辨率和错误隐藏。当前的工作一直被错误隐藏的应用程序所激励和启发，自动恢复在传输过程中所丢失的数据包信息。

Inpainting in wavelet domain or using a sparse representation is a completely different problem since there are no well defined inpainting regions in the pixel domain. After the release of the new image compression standard JPEG2000, which is largely based on wavelet transforms, many images are formatted and stored in terms of wavelet coefficients. In the wireless communication of these images, it could happen that certain wavelet packets are randomly lost or damaged during the transmission process. Recovering original images from their incomplete wavelet transform is an inpainting problem. But this task remarkably differs from the classical inpainting problems in that the inpainting regions are in the wavelet domain.

在小波域内修复或使用稀疏表示是一个完全不同的问题，因为这种方法没有在像素域定义修复区域的范围。在新的图像压缩标准JPEG2000发布之后，这个新的标准在很大程度上是基于小波变换，许多图像是格式化的并存储在小波系数中。在图像无线传输时，在传输过程中可能会随机丢失或损坏某些小波数据包。 从这些丢失或损坏小波包的图像中用小波变换恢复原始图像是图像修复的难题， 在小波域上，这种方式与传统的修补方法有显著的不同。

In the classical inpainting methods, wavelet employed in the sparse dictionary is the famous Daubechies 7/9 biorthogonal decomposition [1] [2].These traditional wavelets are not effective when dealing multidimen-sional signals containing distributed discontinuities such as edges. This approach, however often leads to the formation of Gibbs-type artifacts [6] around sharp discontinuities, due to the elimination of small wavelet coefficients that should have retained. Although new wavelet extensions such as curvelets and contourlets have a better approximation rate, they may also suffer from the same type of effects. TV model is the powerful tool for inpainting and greatly reduce these Gibbs artifacts. But the TV models suffer from the stair case effect. That is, the smooth regions (ramp) are transformed into piece wise constant regions (stairs).

传统的图像修复方法中，在稀疏字典中运用小波双正交分解的7/9[1][2]。当处理如边缘一样的多维信号中的分散式间断部分时，传统小波的处理是无效的。 这种处理，往往导致Gibbs式假象[6]的形成，其周围锐利，不连续。由于小波系数较小的会被消除，所以系数较小的小波会被保留。虽然新的小波扩展，如曲率波和轮廓波都会有一个更好的逼近速率，但它们也可能受到来自同类型的影响。TV模型是强大的修复工具，因此能大大减少Gibbs式假象的形成。但是，TV模型受到阶梯实例—平滑区域（斜面）转化成片智能的恒定区域的影响。

In this paper, to overcome these deficiencies, a new Generalized Expectation Maximization (GEM) Model is introduced with the new tight frame of shearlets. A key feature is that the discrete shearlet transform has many flexible attributes that lead to better stability and reduced Gibbs type artifacts. The EM algorithm formalizes the idea of replacing the missing data by estimated ones from coefficients of previous iteration, and then reestimates the new expansion coefficients from the complete formed data, and iterates the process until convergence [5,6]. We here restrict ourselves to zero- mean additive white Gaussian noise, even if the theory of the EM can be developed for the regular exponential family. In this proposed model,the Expectation Maximization Algorithm is superi- or to that of TV model. We shall demonstrate that our method based on combining shearlets with Expectation Maximization Algorithm using Bayes-an framework performs better than the traditional wavelet technique. Furthermore, the number of iterations is significantly reduced.

本文克服了这些不足之处，提出了一种新的广义期望最大化（GEM）模型，建立了新的剪切波框架。它的主要特点是离散剪切波变换具有灵活的属性，从而更具稳定性及降低Gibbs式假象的性能。EM算法是根据对先前的迭代系数的估计，用估计数据替换丢失掉的数据。然后用完整的数据对新的膨胀系数重新估计，直到迭代收敛[5][6]。虽然EM理论能够发展成定期指数族，我们在这里仍把它限制为零均值的加性高斯白噪声。在此提出的EM算法模型要优越于TV模型，我们将证明这种基于剪切波同EM算法相结合的新模型在叶贝斯框架演示中，其性能优于传统的小波技术。此外，迭代的次数明显减少。

This paper is arranged as follows. In section II, we give a brief overview of the Discrete Shearlet Transform (DST).In Section III, The brief analysis of Expectation Maximization Algorithm is given. The GEM Algorithm for image inpainting using a sparse representation DST is described in Section IV. The Convergence Properties of inpainting method in shearlet domain is presented in Section V. In section VI, numerical experiments are given to illustrate efficiency of the proposed method. Finally, we have a conclusion section.

本文安排如下：在第二节，我们给出了离散剪切波变换（DST）的简要介绍，在第三节，简要分析了期望最大化算法。第四节，阐述了GEM算法利用稀疏表示DST.第五节提出了在剪切波域内，图像修复方法的收敛性能。第六节，数值试验说明了该方法是有效的。最后，我们得出结论。

II. DISCRETE SHEARLET TRANSFORM (DST)

2.离散剪切波变换法（DST）

It is now widely acknowledged that traditional wavelet methods do not perform as well with multidimensional data. Indeed wavelets are very efficient in dealing with point wise singularities only. In higher dimensions, other types of singularities are usually present or even dominant, and wavelets are unable to handle them very efficiently. Images, for example, typically contain sharp transitions such as edges, and

these interact extensively with the elements of the wavelet basis. As a result, many terms in the wavelet representation are needed to accurately represent these objects. In order to overcome this limitation of traditional wavelets, In this paper, a new wavelet transform is introduced, namely shearlet.

现在人们广泛认为，多维数据部适用于传统的小波模型。事实上，小波是唯一有效处理奇异点的方法。在更高的层面，其他类型的奇异点也会存在，甚至占据主导地位，但小波却不能非常有效的处理这些奇异点，例如像边缘那样的急剧变换的图像和这些波基原理相互作用的图像。因此，在小波表示的许多协议中都需要准确地描述这些对象。为了克服传统小波的局限性，在本文中，引入一个新的小波变换，即剪切波变换。

A. Continuous Shearlet Transform

A.连续剪切波变换

The continuous shearlet transform is a non isotropic version of the continuous wavelet transform with a superior directional sensitivity. In dimension n=2, this is defined as the mapping,

连续剪切波变换是一种具有优越的方向敏感性的非各向同版本的连续小波变换，在维数n=2，定义映射为，

Each analyzing elements _ a,s,t called shearlets has a frequency support on a pair of trapezoids, at various scales, symmetric with respect to the origin and oriented along a line of slope s. The support becomes increasingly thin as a _ 0. As a result, the shearlets form a collection

of well-localized waveforms at various scales, orientations and locations, controlled by a, s, and t, respectively. The frequency supports of some

representative shearlets are illustrated in Fig. 1.

分析每个元素,称为有双梯形支持频率的剪切波。在不同的尺度，要考虑起始点的对称和调整沿线的斜率s。当由a→0时，这种支持会越来越弱。其结果是在不同尺度中，剪切波形成一些明确的波形。a,s,t分别表示波形、方向和位置，典型的剪切波频率如图1所示。

图1.对于不同值的剪切波支持频率

B. Discrete Shearlet Transform

B．离散剪切波

By sampling the continuous shearlet transform on appropriate discret- izations of the scaling, shear, and translation parameters a,s,t,one obtains a discrete transform which is associated to a Parseval (tight) frame for L2(R2). The following procedure describes the construction of Shearlet transform and the procedure is illustrated on Fig. 2.

通过对连续剪切波变换的采样，适当的缩放、剪切和转换参数a,s,t，得到了一个与Parseval结构相关的离散变换（）。下面介绍剪切波变换的构建和步骤，如图2所示。

(1) Apply the laplacian pyramid scheme to decompose into a low pass image and a high pass image .

(2) Compute P on a pseudo polar grid.

(3) Apply a band pass filtering to the matrix P

(4) Directly re-assemble the Cartesian sampled values and apply the inverse two-dimensional FFT

(1) 运用拉普拉斯金字塔计划，把分解成一个低通图像和一个高通图像。

(2) 在伪极地网格中计算P

(3) 用一个带通滤波器对矩阵P进行处理

(4) 重新组装笛卡尔采样值，并用逆二维傅里叶变换计算

图2.阐明了连续的拉普拉斯金字塔和定向滤波

III. GENARALIZED EXPECTATION MAXIMIZATION ALGORITHM

3.广义期望最大化算法

Let’s now turn to the missing data case and let’s write, with is the missing data, and . The incomplete observations do not contain all information to applystandard methods to solve the problem equations. Nevertheless, the EM algorithm can be applied to iteratively reconstruct the missing data and then solve the equation for the new estimate. The estimates are iteratively refined until convergence. Recall that the EM algorithm is a means of obtaining MAP/PMLE estimates (of which maximum likelihood is a particular case) of a parameter in cases where the PMLE is hard to obtain. The (Bayesian) EM algorithm will then produce a sequence of estimates alternating between two steps:

现在，考虑数据丢失的情况。写出，其中是丢失的数据，。不完整的观察值包含部分信息，所以标准的方法不适用于解决这一问题方程。然而，EM算法可以进行迭代，重建丢失的数据，然后解估计方程。估计值是反复精确的，直到迭代收敛。回想一下，EM算法是一种在PMLE很难获得的情况下，获得参量的MAP/PMLE估计值的方法。（贝叶斯）EM算法，将产生一系列的估计量相互转换，有两个步骤：

E-step Computes the conditional expectation of the log likilihood of the complete data, given the observed data and the current estimate,by defining the surrogate function:

E-step 计算可能记录的完整数据的条件期望，通过规定的替代函数得到观测数据和最新的估计值：

M-step Updates the estimates according to:

M-step 根据最新的估计：

The E step

For regular exponential families, it is known that the E-steps involves finding the expected values of the sufficient statistics of the complete data Y given observed data and the estimate of and. Then, as the noise is zero-mean white Gaussian, the E-step reduced to calculate the conditional expected values and the conditional expected squared values of the missing data, that is:

E-step

常规指数族，是已知的E-step包括完整数据Y的充分统计量的期望值，给出参数和和的估计值。然后，因为是高斯白噪声，E-step降低对缺损数据的条件期望值和条件期望平方值的计算，即：

The M step

This step consists in maximizing the penalized surrogate function with the missing observations replaced by their estimates in the E step at iteration t,that is:

M -step

这一步骤是通过在E-step中的迭代参量t,最大限度的处理替代函数和遗漏的观察值，即：

Thus, the M step updates and according to:

因此，根据M-step自己中最新的和值：

Where is the number of observed pixels. D denotes whichever estimation operation, associated to the penalty function , applied to the expansion coefficients in Φ. Note that at convergence, we have:

其中，是观测到的像素数量。D表示以估计操作为准，将相关的补偿函数应用到膨胀系数Φ上。注意，在收敛性上，我们已经有了：

which is the noise variance inside the mask (i.e. with observed pixels). If the noise variance is known in advance, the re-estimation of in the M step can be ignored. A very important feature of the M step is that it involves a denoising operation depending on the choice of the penalty function. For example, under the norm penalization and an orthogonal dictionary , can be simply estimated using the well known soft thresholding scheme. This can also be extended to redundant representations as we will see later. Other prior penalties will lead to different estimation rules in the M-Step.

这是掩码内的噪声方差。如果事先知道噪声方差，在M步骤的再估计可以忽略不计。M-step的一个非常重要的特点是，如何去噪，取决于补偿函数的选择。例如，根据规则补偿和正交字典,可以使用已知的软阈值方案简单的估计。这也可以扩展到冗余表示，稍后我们将会看到。在M-step中，其他先前补偿会导致不同的估计规则。

IV. SPARSE REPRESENTATION: DISCRTE

SHEARLET TRANSFORM BASED GEM

INPAINTING MODEL

4.稀疏表示：基于离散剪切波变换的修复方法

The shearlet domain inpainting GEM Model [2] is described as follows.

剪切波域修复的GME模型[2]如下：

Require: Observed image Yobs and a mask M, convergence threshold δ,

1. Repeat

2. E Step

3. Update the image estimate:

4. M Step

5. for Each transformation k in the dictionary do

6. Calculate the transform coefficients

7. Apply the estimation operator（e.g.soft thresholding) to these coefficients and get，

8. end for

9. Update

10. Update according to(9).

11. until Convergence

要求：观测图像Yobs和掩码M，收敛极限δ，

1：重复

2：E-step

3：更新图像估计值：

4：M-step

5：在字典里做每个转换k

6：计算转换系数

7：把估计操作（如软阈值）应用到系数，并得到

8: 结束

9：更新

10：根据（9）更新。

11：直到收敛

V. CONVERGENCE PROPERTIES OF GEM

INPAINTING MODEL IN SHEARLET DOMAIN

5. GME模型在剪切波域的收敛性

In [5, 7], there is no simple general result for the EM that guarantees convergence to a local or global minimum without further assumptions. For instance, if the penalty function is convex, then the penalized-log-likel -ihood will be strictly convex and the EM algorithm will be guaranteed to converge to the unique maximum penalized likelihood value and a unique optimal image. This follows from results of [7] stated for the EM. But, if the penalty function is not convex then the sequences of the Bayesian EM estimates will only converge to a stationary point. The image at convergence will depend on the initialization of the algorithm. As noted in [5], the convergence rate (at least when the initial position is not too far from the true image) is linear and governed by the fraction of missing information, that can be evaluated from the Fisher Information matrix. Thus, here we decide to use the observed part of the image as an initial estimate.

在[5,7]中，没有进一步的假设能保证EM的结果收敛到一个局部或总体的范围。例如，如果补偿函数是凸状，补偿记录的似然性将会是严格凸状，EM算法将保证收敛到唯一的最大的补偿似然值和一个唯一的最佳图像，这就是[7]中的结果。但是，如果补偿函数不是凸状，那么叶贝斯的EM估计值的次序只能收敛到固定点。图像融合取决于算法的初始化，正如在[5]中，收敛率（至少初始位置不会离准确的图像太远）是线性的，并由一部分缺损信息决定。这部分缺损信息可以在Fisher信息矩阵中得到。因此，我们决定采用观测到的一部分图像作为初始估计。

Many interesting penalties that produce sparse solutions are non-convex or even non-smooth. Unfortunately, their use will be at the price of no guaranty to converge to a global or even to a local minimum. To circumvent this major drawback, we use the same heuristic argument as that of the MCA, for which we give a statistical interpretation. Indeed, one can consider the penalized -log-likelihood functional of the M-step as a Gibbs energy, where the regularization parameter parallels the temperature in the same spirit as for simulated annealing. Then, we start at a high temperature (i.e.λ)and then decreaseλaccording to a perscrib- ed schedule (e.g. Exponential or linear). For each value of λ, we run one iteration of the GEM inpainting Algorithm. This algorithm has flavor of a stochastic version of the EM.

许多令人关注的补偿法所产生的稀疏解法是非凸性的或是不平滑的，可惜的是，他们将以不能保证收敛到局部，甚至局部最小为代价的情况下，使用这种方法。为了解决这个主要的缺点，我们用相同的启发式参数作为MCA，这为我们提供了一个统计学的解释。事实上，在M-step中可以把补偿记录似然函数作为Gibbs能量。这里，正规参量与温度在模拟退火试验的原理相应。然后，我们在高温下（即λ），然后按照规定的计划（如指数或线性）降低λ。对于每个λ值，我们用GEM修复算法的迭代进行计算，这个算法具有EM的随机性。

VI. PERFORMANCE COMPARISON

6. 性能比较

In our previous work, the inpainting algorithm based on PLaplacian Operator with TV Model was applied to several synthetic and real degraded images, from which we present few examples. Fig.1 depicts an example on real old degraded photograph. The dictionary contained the shearlet transform and the convexpenalty was used. The threshold parameter was fixed to the classical value From the resulting pictures, shown in Fig.3, we can see that out shearlet inpainting model based on the plaplacian operator can dramatically improve the image quality better than TV wavelet inpainting model,especially in the large number of damaged coefficients.

在先前研究中，我们提出了少数例子。这些例子都是基于拉普拉斯算子和TV模型的图像修复算法，被应用于合成和图像退化。图1描绘了一张退化了的老照片的例子。字典中包含剪切波变换和被补偿的凸行值，阈值参数是固定的经典值.从而得到图像，如图3所示。我们可以看到，基于p-laplacian算子的剪切波修复模型能够明显地改善图像质量，特别是在大量系数受损的情况下要比TV小波修复模型的效果要。

图3. （a）破损图像 (b)分离待修复部分 (c)图像修复模型（TV+P-Laplacian）

For comparison purpose the PSNR values are also computed and the values are tabulated and shown in Table 1. From the PSNR values, we can easily say that using the sparse representation -DST automatically increases the performance of the inpainting algorithm.

表1表示峰值信噪比的计算和测试值，从峰值信噪比的值中可以说，使用稀疏表示—DST能够增加修复算法的性能。

表1.使用峰值信噪比值的性能比较

In the same way the proposed GEM Model with shearlet will be tested on several synthetic images and real images. Now that work is under in progress. We can assure that the proposed model will give better results when compared with our previous P-Laplacian based inpainting with TV Model.

以同样方式提出的剪切波的GEM模型，对几个合成图像和真实图像作实验。现在，这项实验正在进行中。我们可以确保该模型要比已有的基于P-laolacian的图像修复和TV模型得到的效果更好。

VII. CONCLUSION

7.结论

In this paper, a new sparse representation-Discrete Shearlet Transform domain inpainting model based on Generalized Expectation Maximization (GEM) for restoring arbitrary number of coefficients in arbitrary locations of shearlets coefficients for images with noise is presented. Comparing the proposed model to TV wavelet inpainting model, the better inpainting quality with much less computing time will be achieved, especially with large number of damaged wavelet coefficients.

在本文中，提出了一种新的基于广义期望最大化（GEM）的稀疏表示-离散剪切波变换域的图像修复模型，该模型能够恢复任意位置下的剪切波系数。尤其在小波系数大量受损的情况下，该模型的修复效果要比TV小波模型的更好，并且减少了计算时间。

本文来源：https://www.2haoxitong.net/k/doc/7ec38dfeaef8941ea76e05c9.html