# A Multiresolution Image Completion Algorithm for Compressing Digital Color Images

Authors: R. Gomathi; A. Vincent Antony Kumar
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper introduces a new framework for image coding that uses image inpainting method. In the proposed algorithm, the input image is subjected to image analysis to remove some of the portions purposefully.  At the same time, edges are extracted from the input image and they are passed to the decoder in the compressed manner. The edges which are transmitted to decoder act as assistant information and they help inpainting process fill the missing regions at the decoder. Textural synthesis and a new shearlet inpainting scheme based on the theory ofp-Laplacian operator are proposed for image restoration at the decoder. Shearlets have been mathematically proven to represent distributed discontinuities such as edges better than traditional wavelets and are a suitable tool for edge characterization. This novel shearlet p-Laplacian inpainting model can effectively reduce the staircase effect in Total Variation (TV) inpainting model whereas it can still keep edges as well as TV model. In the proposed scheme, neural network is employed to enhance the value of compression ratio for image coding. Test results are compared with JPEG 2000 and H.264 Intracoding algorithms. The results show that the proposed algorithm works well.


---

## Body

## 1. Introduction

Image inpainting [1–5] is a method for recovering regions in images whose pixels are distorted or removed in some way. Inpainting methods are commonly based on Partial Differential Equations (PDEs) and Total Variation (TV) models. In PDEs technique [6], pixel values around the region to be inpainted are considered to be the boundary condition for a boundary value problem. Then, a proper equation for interpolating in that area will be solved. Image inpainting has a variety of applications such as text and object removal, denoising, superresolution, digital zooming, filling-in, and compression. Galić et al. [7] use an inpainting technique directly for compression whereas, in previous studies, image inpainting is treated only as a preprocessing step to increase other existing image compression standards. Bugeau et al. [8] offered a working algorithm for image inpainting trying to approximate the global minimum of an energy functional that combines the three fundamental concepts of self-similarity, coherence, and propagation. In this method, when the image does not have enough patches to copy from, either because the mask is too spread and the patch size is large or because the mask is placed on a singular location on the image, then the results are poor and although the presence of a geometry term seems to help, it is clearly not enough. The authors did not solve these problems and they did not optimize the search in the patch space.Chan et al. [6] have proposed TV wavelet inpainting models. The main benefit of TV model is that it can keep the edges very well. But, the method has the drawback called staircase effect. To overcome this defect, we analyze the physical characteristics of TV model [9] and p-Laplacian operator [10] in local coordinates. At the same time, the traditional wavelets [11] are not very effective in dealing with multidimensional signals containing distributed discontinuities such as edges. To overcome this limitation, one has to use basis elements with much higher directional sensitivity and of various shapes to be able to capture the intrinsic geometrical features of multidimensional phenomena.In this paper, a new discrete multiscale representation [12] called the Discrete Shearlet Transform (DST) is introduced to perform the inpainting based on p-Laplacian operator in wavelet domain. This approach, which is based on the shearlet transform, combines the power of multiscale methods with a unique ability to capture the geometry of multidimensional data and is optimally efficient in representing images containing edges. In the proposed algorithm, the correlated portions are identified and they are removed at encoder and filled by image inpainting at the decoder. A p-Laplacian based inpainting method which employs a DST is presented which can effectively reduce the staircase effect in TV model and can be used to achieve less computing time. Gradient descent back propagation [13] with adaptive learning rate is proposed for compression.This paper is arranged as follows. First, in Section2, the statement of the problem is described. In Section 3, the framework of proposed coding scheme is discussed. Specifically, Section 3 shows the ANNs based compression in shearlet domain and the shearlet image inpainting based on p-Laplacian operator. In Section 4, the experimental results are presented. Section 5 describes conclusion.


## 2. Statement of the Problem

A standard image model [6] is defined as
(1)z(x)=f(x)+n(x),
where f(x) is original noise free model; n(x) is Gaussian white noise.The standard wavelet transform ofz(x) is given by
(2)z(α,x)=∑j,kαj,kψj,k(x),j∈Z,k∈Z2,
where α=αj,k and is wavelet coefficients; ψ is mother wavelet function.Damages in the wavelet domain cause loss of wavelet coefficients ofz(x) on the index region I, {αj,k}’s with j,k∈I represent those wavelet components missing or damaged. The task of inpainting is to restore the missing coefficients in a proper manner, so that the image will have as much information being restored as possible.For inpainting when we used the traditional wavelets [14–16], they do not deal with multidimensional discontinuities such as edges. Recently, a theory for multidimensional data called Multiscale Geometric Analysis (MGA) has been developed. Many new MGA tools have been proposed such as ridgelet, curvelet, bandlet, and contourlet, which provide higher directional sensitivity than wavelets. Shearlets [17–19], a new approach proposed in this paper, not only possess all the above properties but also are equipped with a rich mathematical structure similar to wavelets, which are associated with a multiresolution analysis. Shearlets form a tight frame at various scales and directions and are optimally sparse in representing image with edges.The discrete shearlet transform ofz(x) is given by
(3)z(α,x)=〈z,ψj,l,k〉j,l∈Z,k∈Z2
and the corresponding image inpainting model in shearlet domain is
(4)min⁡ςj,l,kT(f,z)=∫|∇Xf(ς,x)|dx+∑j,l,kλ2(ςj,l,k-αj,l,k)2,
where,
(5)f(ς,x)=∑j,l,kςj,l,kψj,l,k(x);ςj,l,k(j,l,k)∈I,iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiij,l∈Z,k∈Z2,λ=0ifj,l,k∈I,otherwise it is assigned withpositive constant.When this model is solved, the use of TV norm can retain sharp edges while reducing noise and other oscillations. But the corresponding Euler-Lagrange equation is not trivial to compute since it is highly nonlinear and ill-posed in strong sense. Furthermore, this model has the drawback that is called stair case effect. To overcome these deficiencies, ap-Laplacian operator [20] is introduced in this new shearlet inpainting model and is
(6)min⁡ςj,l,kT(f,z)=1p∫|∇xf(ς,x)|pdxiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii+∑j,l,kλ2(ςj,l,k-αj,l,k)2,1<p<2,
where p can be adaptively selected based on the local gradient features of images. That is, away from edges, p will be approached to 2 to overcome the staircase effect; on the contrary, p will be approached to 1 to preserve edges. So this new model can effectively reduce the staircase effect in TV model whereas it can still retain the sharp edges as TV model.The Euler-Lagrange equation of the above inpainting model is(7)-∇·(|Δxf(ς,x)|p-2·∇xf(ς,x))+λj,l,k(ςj,l,k-αj,l,k)=0.The gradient descent flow of (7) is
(8)(ςj,l,k)t=∇·(|Δxf(ς,x)|p-2·∇xf(ς,x))-λj,l,k(ςj,l,k-αj,l,k).The above equation is solved by the simple explicit finite difference algorithm. To simplify the formulation, we introduce the standard finite difference notations, such asthe forward differences:(9)D1+fk,l=fk+1,l-fk,l,D2+fk,l=fk,l+1-fk,land the backward differences:(10)D1-fk,l=fk,l-fk-1,l,D2-fk,l=fk,l-fk,l-1.We note that it is important to evaluate the nonlinear term, which we denote as(11)SHcurv=∇·(|∇xf∧|p-2∇xf∧(ς,x))in (8). However, the p-Laplace operator is defined in the pixel domain. In this paper, we calculate it straightforwardly by transforming the shearlet domain to the pixel domain to compute the p-Laplace operator and then transform back to the shearlet domain. That is, we calculate the following:
(12)f=∑j,l∈Z,k∈Z2〈ς,ψj,l,k〉ψj,l,k.For all(i,j), we compute the following:
(13)curvi,j=D1-D1+fi,j(|D1+fi,j|2+|D2+fi,j|2+ε)(2-p)/2+D2-D2+fi,j(|D1+fi,j|2+|D2+fi,j|2+ε)(2-p)/2,
where ε is a small positive number which is used to prevent the numerical blow-up when
(14)|D1+fi,j|2+|D2+fi,j|2=0.Then we compute the curvature projection on the wavelet basis by(15)SHcurv(j,l,k)=〈curv,ψj,l,k〉.


## 3. Framework of Proposed Scheme

The method proposed in this section is based on removing redundancy at the encoder and restoring the removed information using an inpainting method at the decoder. In this algorithm, redundancy removal is performed through detecting texture regions with similar statistical characteristics and dividing the image into homogeneous regions. The overall system with encoder and decoder diagrams is depicted in Figures1 and 2. In the following subsections, encoder and decoder blocks are discussed separately.Figure 1
Block diagram of proposed image compression scheme–encoder.Figure 2
Block diagram of proposed image compression scheme–decoder.


### 3.1. Design of Encoder

#### 3.1.1. Image Analysis

The input image is subjected to image analysis by extracting edges from the images in order to identify both the structural and textural regions. An input image is divided into8×8 blocks. Then they are identified as textural or structural blocks based on their distance from edges. The block is identified as a structural one when it contains more numbers of pixels having very small distance from edges. The remaining blocks are called textural blocks.The important blocks from both textural regions and structural regions are selected by using different algorithms [21]. The remaining blocks are easily removed during encoding. In this way, the blocks are identified and removed. After the removal of specified blocks, in the original image, the regions are filled with the corresponding DC value or filled with pure red, or green, or blue component, in the case of color images.


#### 3.1.2. ANN Based Image Compression

Gradient descent back propagation algorithm [13] is the widely used algorithm in Artificial Neural Networks (ANNs). The feed-forward neural network architecture is capable of approximating most problems with high accuracy and generalization ability. This algorithm mainly focuses on the error correction learning rule. Error propagation consists of two passes through the different layer of the network: a forward pass and a backward pass. In the forward pass, the input vector is applied to the sensory nodes of the network and its effect propagates through the network layer by layer.Finally, a set of outputs is produced as the actual response of the network. During the forward pass, the synaptic weights of the networks are all fixed. During the back pass, the synaptic weights are all adjusted in accordance with an error correction rule. The actual response of the network is subtracted from the desired response to produce an error signal. This error signal is then propagated through the network against the direction of synaptic conditions. The synaptic weights are adjusted to make the actual response of the network move closer to the desired response.Procedure for Image Compression. For experiment, feed-forward neural network with three layers is selected. Input layer, hidden layer with 16 neurons, and output layer with 64 neurons are introduced in that network. Back propagation algorithm is used for training process. For training the network, 256 × 256 Lena image is selected (see Algorithm 1).Algorithm 1:Image compression and decompression using ANNs.
(1) Divide the original image in frequency domain into 8 × 8 pixel blocks and reshape each one
into 64 × 1 column vector.
(2) Arrange the column vectors into a matrix of 64 × 1024.
(3) Let the target matrix equal to the matrix in step 2.
(4) Choose a Gradient Descent Back Propagation learning algorithm to start training.
(5) Simulate the network with the input matrix and the target matrix.
(6) Obtain the output matrices of the hidden layer and the output layer.
(7) Post-process them to obtain the compressed image, and the reconstructed image, respectively.


### 3.2. Design of Decoder

After performing the ANN based compression at encoder, the decompression process is carried out at decoder. Final reconstructed image is obtained throughp-Laplacian inpainting based on DST and texture synthesis. The theory of shearlets is discussed in addition to the two most important modules, namely, shearlet domain p-Laplacian inpainting and texture synthesis.


#### 3.2.1. Continuous Shearlet Transform

The continuous shearlet transform [17, 18] is a nonisotropic version of the continuous wavelet transform with a superior directional sensitivity. For n=2,
(16)SHψf(a,s,t)=〈f,ψa,s,t〉.Each analyzing elementψa,s,t is termed shearlet. The frequency tiling of shearlets is shown in Figure 3.Figure 3
(a) The tiling of the frequency plane. The tiling of horizontal cone is illustrated in solid line; the tiling of vertical cone is in dashed line. (b) Frequency support of shearlet satisfies parabolic scaling (j-decomposition level). The Figure shows only the support for ξ1>0; the other half of the support, for ξ1<0, is symmetrical.


#### 3.2.2. Discrete Shearlet Transform

By sampling the continuous shearlet transform, we can get a discrete transform which is shown in Figure4  (see Algorithm 2).Algorithm 2:Construction of discrete shearlet transform.
(1) Decomposefaj-1 into a low pass image faj and a high pass image fdj by
applying Laplacian Pyramid Scheme.
(2) Use pseudo polar grid to computeP·fdj.
(3) Band pass filter the output matrixP·fdj
(4) Re-assemble the Cartesian sampled values
(5) Take the 2D IFFT.Figure 4
Succession of Laplacian pyramid and directional filtering.


#### 3.2.3. Shearlet Domainp-Laplacian Inpainting

From the pure inpainting perspective, the inpainting problem may be stated as follows. LetI be the original image, which is composed by a source area, denoted by ϕ, whose pixel values are known, and a target area, denoted by Ω, representing the damaged region to be repaired or a region to be filled in, and this means being inpainted. As shown in Figure 5, these are nonoverlapping areas, that is, I=ϕ∪Ω and ∂Ω for the boundary between the source and target regions. The simplified architecture for image coding with inpainting is shown in Figure 5 and the pseudocode of proposed work is described as follows: the pseudocode of proposed framework with PDEs inpainting algorithm based onp-Laplacian operator (see Algorithm 3).Algorithm 3:Pseudocode of proposed framework with PDEs inpainting algorithm based on p Laplacian operator.
(1) Obtain a noisy image as input
z(x)=f(x)+n(x)
(2) Smooth the noisy image using
∂z∂x=div⁡(g(∥∇z∥)·∇z)
(3) Analyze the smoothed image by extracting edges through
|∇z(x,y)|=(∂xz(x,y))2+(∂yz(x,y))2
θ=arctan(∂yz(x,y)∂yz(x,y))
(4) Identify the structural and textural regions based on the extracted edges.
(5) Skip the regions that are not selected as necessary information instead fill
the DC value and create a DC filled image
(6) Perform ANN Compression and Decompression using
comp⁡in=∑i=1NVi,jzi,1≤j≤K
zjin=∑i=1NWi,jcomp⁡in,1≤j≤N
whereVij & Wij are weights of compressor and decompressor respectively.
(7) Start the inpainting process with initial guessςj,l,knew=αj,l,kχj,l,k.
Set
ς
j
,
l
,
k
old
=
0 and the initial error E=∥ςnew-ςold∥2
Whereχj,l,k={1(j,l,k)∈I0(j,l,k)∉I} and I is the inpainting region.
(8) Whilei≤N or E≤δ,do
(a) Setςold=ςnew
(b) CalculateSHcurv using (12)–(15)
(c) For allj,l,k update
ςj,l,knew=ςj,l,kold+ΔtΔx(SHcurv-λj,l,k(ςj,l,k-αj,l,k)),
where Δt is the time step size & Δx is the space grid size
(d) Compute errorE=∥ςnew-ςold∥2
(e) End the while loop(a) Illustration of the inpainting problem. (b) The simplified architecture for image coding with inpainting.
(a)
(b)


#### 3.2.4. Texture Synthesis

The missing texture blocks are filled in with the texture from its surrounding [2]. Let the region to be filled be denoted by Ω. The lost block will now be filled, pixel by pixel, in a raster fashion. Let It be a representative template touching the left of a pixel p(i,j)∈Ω. We proceed to find an estimate of It from the available neighborhood, such that a given distance d(It,It.) is minimized. As per [2], d is a normalized Sum of Squared Differences (SSD) metric. Once such an estimate of It is found, we choose the pixel to the immediate right of estimate of It as our candidate for p(i,j)∈Ω. For stochastic textures, the algorithm selects at random one of the pixels neighboring estimate of It. The template It can be a simple seed block of 3 × 3 pixels. Then, of all possible 3 × 3 blocks in the 8 neighbourhoods, the one with the minimum normalized SSD is found and a pixel to its right is copied into the current pixel in the lost block. This algorithm is considerably fast when using the improvements in [21–25].


## 3.1. Design of Encoder

### 3.1.1. Image Analysis

The input image is subjected to image analysis by extracting edges from the images in order to identify both the structural and textural regions. An input image is divided into8×8 blocks. Then they are identified as textural or structural blocks based on their distance from edges. The block is identified as a structural one when it contains more numbers of pixels having very small distance from edges. The remaining blocks are called textural blocks.The important blocks from both textural regions and structural regions are selected by using different algorithms [21]. The remaining blocks are easily removed during encoding. In this way, the blocks are identified and removed. After the removal of specified blocks, in the original image, the regions are filled with the corresponding DC value or filled with pure red, or green, or blue component, in the case of color images.


### 3.1.2. ANN Based Image Compression

Gradient descent back propagation algorithm [13] is the widely used algorithm in Artificial Neural Networks (ANNs). The feed-forward neural network architecture is capable of approximating most problems with high accuracy and generalization ability. This algorithm mainly focuses on the error correction learning rule. Error propagation consists of two passes through the different layer of the network: a forward pass and a backward pass. In the forward pass, the input vector is applied to the sensory nodes of the network and its effect propagates through the network layer by layer.Finally, a set of outputs is produced as the actual response of the network. During the forward pass, the synaptic weights of the networks are all fixed. During the back pass, the synaptic weights are all adjusted in accordance with an error correction rule. The actual response of the network is subtracted from the desired response to produce an error signal. This error signal is then propagated through the network against the direction of synaptic conditions. The synaptic weights are adjusted to make the actual response of the network move closer to the desired response.Procedure for Image Compression. For experiment, feed-forward neural network with three layers is selected. Input layer, hidden layer with 16 neurons, and output layer with 64 neurons are introduced in that network. Back propagation algorithm is used for training process. For training the network, 256 × 256 Lena image is selected (see Algorithm 1).Algorithm 1:Image compression and decompression using ANNs.
(1) Divide the original image in frequency domain into 8 × 8 pixel blocks and reshape each one
into 64 × 1 column vector.
(2) Arrange the column vectors into a matrix of 64 × 1024.
(3) Let the target matrix equal to the matrix in step 2.
(4) Choose a Gradient Descent Back Propagation learning algorithm to start training.
(5) Simulate the network with the input matrix and the target matrix.
(6) Obtain the output matrices of the hidden layer and the output layer.
(7) Post-process them to obtain the compressed image, and the reconstructed image, respectively.


## 3.1.1. Image Analysis

The input image is subjected to image analysis by extracting edges from the images in order to identify both the structural and textural regions. An input image is divided into8×8 blocks. Then they are identified as textural or structural blocks based on their distance from edges. The block is identified as a structural one when it contains more numbers of pixels having very small distance from edges. The remaining blocks are called textural blocks.The important blocks from both textural regions and structural regions are selected by using different algorithms [21]. The remaining blocks are easily removed during encoding. In this way, the blocks are identified and removed. After the removal of specified blocks, in the original image, the regions are filled with the corresponding DC value or filled with pure red, or green, or blue component, in the case of color images.


## 3.1.2. ANN Based Image Compression

Gradient descent back propagation algorithm [13] is the widely used algorithm in Artificial Neural Networks (ANNs). The feed-forward neural network architecture is capable of approximating most problems with high accuracy and generalization ability. This algorithm mainly focuses on the error correction learning rule. Error propagation consists of two passes through the different layer of the network: a forward pass and a backward pass. In the forward pass, the input vector is applied to the sensory nodes of the network and its effect propagates through the network layer by layer.Finally, a set of outputs is produced as the actual response of the network. During the forward pass, the synaptic weights of the networks are all fixed. During the back pass, the synaptic weights are all adjusted in accordance with an error correction rule. The actual response of the network is subtracted from the desired response to produce an error signal. This error signal is then propagated through the network against the direction of synaptic conditions. The synaptic weights are adjusted to make the actual response of the network move closer to the desired response.Procedure for Image Compression. For experiment, feed-forward neural network with three layers is selected. Input layer, hidden layer with 16 neurons, and output layer with 64 neurons are introduced in that network. Back propagation algorithm is used for training process. For training the network, 256 × 256 Lena image is selected (see Algorithm 1).Algorithm 1:Image compression and decompression using ANNs.
(1) Divide the original image in frequency domain into 8 × 8 pixel blocks and reshape each one
into 64 × 1 column vector.
(2) Arrange the column vectors into a matrix of 64 × 1024.
(3) Let the target matrix equal to the matrix in step 2.
(4) Choose a Gradient Descent Back Propagation learning algorithm to start training.
(5) Simulate the network with the input matrix and the target matrix.
(6) Obtain the output matrices of the hidden layer and the output layer.
(7) Post-process them to obtain the compressed image, and the reconstructed image, respectively.


## 3.2. Design of Decoder

After performing the ANN based compression at encoder, the decompression process is carried out at decoder. Final reconstructed image is obtained throughp-Laplacian inpainting based on DST and texture synthesis. The theory of shearlets is discussed in addition to the two most important modules, namely, shearlet domain p-Laplacian inpainting and texture synthesis.


### 3.2.1. Continuous Shearlet Transform

The continuous shearlet transform [17, 18] is a nonisotropic version of the continuous wavelet transform with a superior directional sensitivity. For n=2,
(16)SHψf(a,s,t)=〈f,ψa,s,t〉.Each analyzing elementψa,s,t is termed shearlet. The frequency tiling of shearlets is shown in Figure 3.Figure 3
(a) The tiling of the frequency plane. The tiling of horizontal cone is illustrated in solid line; the tiling of vertical cone is in dashed line. (b) Frequency support of shearlet satisfies parabolic scaling (j-decomposition level). The Figure shows only the support for ξ1>0; the other half of the support, for ξ1<0, is symmetrical.


### 3.2.2. Discrete Shearlet Transform

By sampling the continuous shearlet transform, we can get a discrete transform which is shown in Figure4  (see Algorithm 2).Algorithm 2:Construction of discrete shearlet transform.
(1) Decomposefaj-1 into a low pass image faj and a high pass image fdj by
applying Laplacian Pyramid Scheme.
(2) Use pseudo polar grid to computeP·fdj.
(3) Band pass filter the output matrixP·fdj
(4) Re-assemble the Cartesian sampled values
(5) Take the 2D IFFT.Figure 4
Succession of Laplacian pyramid and directional filtering.


### 3.2.3. Shearlet Domainp-Laplacian Inpainting

From the pure inpainting perspective, the inpainting problem may be stated as follows. LetI be the original image, which is composed by a source area, denoted by ϕ, whose pixel values are known, and a target area, denoted by Ω, representing the damaged region to be repaired or a region to be filled in, and this means being inpainted. As shown in Figure 5, these are nonoverlapping areas, that is, I=ϕ∪Ω and ∂Ω for the boundary between the source and target regions. The simplified architecture for image coding with inpainting is shown in Figure 5 and the pseudocode of proposed work is described as follows: the pseudocode of proposed framework with PDEs inpainting algorithm based onp-Laplacian operator (see Algorithm 3).Algorithm 3:Pseudocode of proposed framework with PDEs inpainting algorithm based on p Laplacian operator.
(1) Obtain a noisy image as input
z(x)=f(x)+n(x)
(2) Smooth the noisy image using
∂z∂x=div⁡(g(∥∇z∥)·∇z)
(3) Analyze the smoothed image by extracting edges through
|∇z(x,y)|=(∂xz(x,y))2+(∂yz(x,y))2
θ=arctan(∂yz(x,y)∂yz(x,y))
(4) Identify the structural and textural regions based on the extracted edges.
(5) Skip the regions that are not selected as necessary information instead fill
the DC value and create a DC filled image
(6) Perform ANN Compression and Decompression using
comp⁡in=∑i=1NVi,jzi,1≤j≤K
zjin=∑i=1NWi,jcomp⁡in,1≤j≤N
whereVij & Wij are weights of compressor and decompressor respectively.
(7) Start the inpainting process with initial guessςj,l,knew=αj,l,kχj,l,k.
Set
ς
j
,
l
,
k
old
=
0 and the initial error E=∥ςnew-ςold∥2
Whereχj,l,k={1(j,l,k)∈I0(j,l,k)∉I} and I is the inpainting region.
(8) Whilei≤N or E≤δ,do
(a) Setςold=ςnew
(b) CalculateSHcurv using (12)–(15)
(c) For allj,l,k update
ςj,l,knew=ςj,l,kold+ΔtΔx(SHcurv-λj,l,k(ςj,l,k-αj,l,k)),
where Δt is the time step size & Δx is the space grid size
(d) Compute errorE=∥ςnew-ςold∥2
(e) End the while loop(a) Illustration of the inpainting problem. (b) The simplified architecture for image coding with inpainting.
(a)
(b)


### 3.2.4. Texture Synthesis

The missing texture blocks are filled in with the texture from its surrounding [2]. Let the region to be filled be denoted by Ω. The lost block will now be filled, pixel by pixel, in a raster fashion. Let It be a representative template touching the left of a pixel p(i,j)∈Ω. We proceed to find an estimate of It from the available neighborhood, such that a given distance d(It,It.) is minimized. As per [2], d is a normalized Sum of Squared Differences (SSD) metric. Once such an estimate of It is found, we choose the pixel to the immediate right of estimate of It as our candidate for p(i,j)∈Ω. For stochastic textures, the algorithm selects at random one of the pixels neighboring estimate of It. The template It can be a simple seed block of 3 × 3 pixels. Then, of all possible 3 × 3 blocks in the 8 neighbourhoods, the one with the minimum normalized SSD is found and a pixel to its right is copied into the current pixel in the lost block. This algorithm is considerably fast when using the improvements in [21–25].


## 3.2.1. Continuous Shearlet Transform

The continuous shearlet transform [17, 18] is a nonisotropic version of the continuous wavelet transform with a superior directional sensitivity. For n=2,
(16)SHψf(a,s,t)=〈f,ψa,s,t〉.Each analyzing elementψa,s,t is termed shearlet. The frequency tiling of shearlets is shown in Figure 3.Figure 3
(a) The tiling of the frequency plane. The tiling of horizontal cone is illustrated in solid line; the tiling of vertical cone is in dashed line. (b) Frequency support of shearlet satisfies parabolic scaling (j-decomposition level). The Figure shows only the support for ξ1>0; the other half of the support, for ξ1<0, is symmetrical.


## 3.2.2. Discrete Shearlet Transform

By sampling the continuous shearlet transform, we can get a discrete transform which is shown in Figure4  (see Algorithm 2).Algorithm 2:Construction of discrete shearlet transform.
(1) Decomposefaj-1 into a low pass image faj and a high pass image fdj by
applying Laplacian Pyramid Scheme.
(2) Use pseudo polar grid to computeP·fdj.
(3) Band pass filter the output matrixP·fdj
(4) Re-assemble the Cartesian sampled values
(5) Take the 2D IFFT.Figure 4
Succession of Laplacian pyramid and directional filtering.


## 3.2.3. Shearlet Domainp-Laplacian Inpainting

From the pure inpainting perspective, the inpainting problem may be stated as follows. LetI be the original image, which is composed by a source area, denoted by ϕ, whose pixel values are known, and a target area, denoted by Ω, representing the damaged region to be repaired or a region to be filled in, and this means being inpainted. As shown in Figure 5, these are nonoverlapping areas, that is, I=ϕ∪Ω and ∂Ω for the boundary between the source and target regions. The simplified architecture for image coding with inpainting is shown in Figure 5 and the pseudocode of proposed work is described as follows: the pseudocode of proposed framework with PDEs inpainting algorithm based onp-Laplacian operator (see Algorithm 3).Algorithm 3:Pseudocode of proposed framework with PDEs inpainting algorithm based on p Laplacian operator.
(1) Obtain a noisy image as input
z(x)=f(x)+n(x)
(2) Smooth the noisy image using
∂z∂x=div⁡(g(∥∇z∥)·∇z)
(3) Analyze the smoothed image by extracting edges through
|∇z(x,y)|=(∂xz(x,y))2+(∂yz(x,y))2
θ=arctan(∂yz(x,y)∂yz(x,y))
(4) Identify the structural and textural regions based on the extracted edges.
(5) Skip the regions that are not selected as necessary information instead fill
the DC value and create a DC filled image
(6) Perform ANN Compression and Decompression using
comp⁡in=∑i=1NVi,jzi,1≤j≤K
zjin=∑i=1NWi,jcomp⁡in,1≤j≤N
whereVij & Wij are weights of compressor and decompressor respectively.
(7) Start the inpainting process with initial guessςj,l,knew=αj,l,kχj,l,k.
Set
ς
j
,
l
,
k
old
=
0 and the initial error E=∥ςnew-ςold∥2
Whereχj,l,k={1(j,l,k)∈I0(j,l,k)∉I} and I is the inpainting region.
(8) Whilei≤N or E≤δ,do
(a) Setςold=ςnew
(b) CalculateSHcurv using (12)–(15)
(c) For allj,l,k update
ςj,l,knew=ςj,l,kold+ΔtΔx(SHcurv-λj,l,k(ςj,l,k-αj,l,k)),
where Δt is the time step size & Δx is the space grid size
(d) Compute errorE=∥ςnew-ςold∥2
(e) End the while loop(a) Illustration of the inpainting problem. (b) The simplified architecture for image coding with inpainting.
(a)
(b)


## 3.2.4. Texture Synthesis

The missing texture blocks are filled in with the texture from its surrounding [2]. Let the region to be filled be denoted by Ω. The lost block will now be filled, pixel by pixel, in a raster fashion. Let It be a representative template touching the left of a pixel p(i,j)∈Ω. We proceed to find an estimate of It from the available neighborhood, such that a given distance d(It,It.) is minimized. As per [2], d is a normalized Sum of Squared Differences (SSD) metric. Once such an estimate of It is found, we choose the pixel to the immediate right of estimate of It as our candidate for p(i,j)∈Ω. For stochastic textures, the algorithm selects at random one of the pixels neighboring estimate of It. The template It can be a simple seed block of 3 × 3 pixels. Then, of all possible 3 × 3 blocks in the 8 neighbourhoods, the one with the minimum normalized SSD is found and a pixel to its right is copied into the current pixel in the lost block. This algorithm is considerably fast when using the improvements in [21–25].


## 4. Performance Evaluation

We illustrate the performance of the proposed algorithm for image compression with image inpainting in shearlet domain using ANNs and compare it with the image inpainting method proposed by Liu et al. [3], The codes are written in MATLAB 2008a.


### 4.1. Test Conditions and Parameters

The proposed algorithm is tested with color images from USC-SIPI and Kodak image database. In all testes, we use shearlet basep-Laplacian inpainting and we set the parameter values p=1.2, λ=0 for noiseless images and λ=0.08 for noisy images.


### 4.2. Overall Performance

Figure6 shows test image Lena and corresponding results of proposed system. In this test, edges are extracted from the input image and shown in Figure 6(b) and the image with removed blocks (25% removal) is shown in Figure 6(c).Comparison with JPEG 2000 with QP = 75. (a) Input image. (b) Edges. (c) Image with 25% of portions removed. (d) Reconstructed image after inpainting and texture synthesis. (e) Reconstructed image by JPEG 2000.
(a)
(b)
(c)
(d)
(e)Based on the preserved blocks, the shearletp-Laplacian inpainting gives results in Figure 6(d). When comparing the restored image in Figure 6(e) with JPEG 2000, proposed scheme saves 36.15% of bits with QP = 75. The comparison of standard images shows up to 50% bits saving which is achieved by the proposed scheme compared to JPEG 2000 and up to 31.61% bit saving compared to edge based image inpainting method proposed by Liu et al. [3]. The bit-saving results are shown in Table 1.Table 1
Bit-rate saving of proposed scheme compared to JPEG 2000 and edge based image inpainting method (QP = 75).
Original image
Block removal (%)
PSNR (dB)
Bit-rate (bpp)
Bit-rate saving (%)
JPEG 2000
Edge based image inpainting
Proposed scheme
Compared with JPEG 2000
Compared with edge based Image inpainting
Jet
25.0
45.67
1.156
0.919
0.780
32.53
15.13
Lena
25.0
37.23
1.112
0.888
0.710
36.15
20.05
Peppers
32.5
39.87
1.217
0.965
0.812
33.28
15.85
Kodim02
51.0
35.78
1.058
0.709
0.529
50.00
25.39
Kodim03
42.8
36.45
0.895
0.608
0.485
45.81
20.23
Kodim07
32.8
39.34
1.079
0.802
0.622
42.35
22.44
Kodim11
35.0
38.00
1.368
1.047
0.716
47.66
31.61
Kodim19
26.7
41.34
1.276
0.915
0.680
46.71
25.68
Kodim20
54.2
33.11
0.897
0.638
0.522
41.81
18.18
Kodim23
53.0
34.12
0.821
0.567
0.492
40.07
13.23Figure7 shows the reconstructed images by the proposed scheme with standard H.264/AVC Intracoding. The bit-rate saving is also noticeable, shown in Table 2, but not as much as the comparison with JPEG 2000. The proposed scheme can acquire 48.07% bit-rate saving compared to the state-of-the-art H.264 Intracoding with QP = 24 for an image Kodim19. Bit-rate saving of 33.01% is achieved for an image Kodim11 by the proposed scheme when compared with edge based image inpainting method.Table 2
Bit rate savings of proposed scheme compared to H.264/AVC intra and edge based image inpainitng method (QP = 24).
Original image
Block removal (%)
PSNR (dB)
Bit-rate (bpp)
Bit-rate saving (%)
H.264
Edge based image inpainting
Proposed scheme
Compared with H.264
Compared with edge based image inpainting
Jet
25.0
42.56
0.985
0.880
0.727
26.16
17.35
Lena
40.0
35.67
0.993
0.869
0.772
22.26
11.16
Peppers
32.5
36.45
1.311
1.080
0.818
37.61
24.27
Mandrill
43.0
36.48
0.880
0.783
0.691
21.47
11.74
Kodim02
51.0
32.11
0.948
0.701
0.510
46.20
27.25
Kodim03
42.8
34.23
0.710
0.562
0.495
30.28
11.92
Kodim07
32.8
35.00
0.876
0.751
0.671
23.38
10.63
Kodim11
35.0
36.78
1.354
1.098
0.736
45.68
33.01
Kodim13
42.0
37.02
0.900
0.872
0.714
20.66
18.12
Kodim19
26.7
39.36
1.246
0.956
0.647
48.07
32.32
Kodim20
54.2
30.00
0.823
0.636
0.473
42.49
25.58Comparison with H.264/AVC with QP = 24. (a) Jet (25% removal); (b) peppers (32.5% removal); (c) kodim05 (23% removal); (d) kodim02 (51% removal). The top row shows the reconstructed images by proposed scheme and the bottom row shows the reconstructed images by H.264/AVC Intracoding.
(a)
(b)
(c)
(d)Figure8 shows the comparison results with JPEG 2000. The first row in Figure 8 shows results of the proposed method and the second row presents JPEG 2000 results. The bits saving of proposed system is indicated in Table 1. The proposed scheme averagely saves 43.54% bits with QP = 75 for the five images shown in Figure 8. Peak Signal-to-Noise Ratio (PSNR) is also used to measure the quality of the restored images. It is defined as follows:
(17)PSNR=10log10(maxI2MSE),
where max⁡I is the maximum possible pixel value of the image.Comparison with JPEG 2000 with QP = 75. (a) Kodim07 (32.8% removal); (b) kodim23 (53% removal); (c) kodim03 (42.8% removal); (d) kodim20 (54.2% removal); (e) kodim11 (35% removal). The first row shows the restored images by proposed algorithm and the second row shows the restored images by JPEG 2000.
(a)
(b)
(c)
(d)
(e)Figure9 gives objective quality comparisons between the proposed scheme, JPEG 2000, and H.264/AVC Intracoding. It can be observed that the objective quality of the proposed scheme outperforms the two standard compression schemes (JPEG 2000 and H.264/AVC Intra) and edge based inpainting algorithm at both low and high bit rates. The proposed algorithm is adapted for subjective quality, and PSNR is not a good measure to evaluate the subjective quality, especially for the resulting images of p-Laplacian inpainting in shearlet domain.Objective quality comparison between proposed scheme, H.264/AVC Intra, and JPEG 2000 on some typical color images.
(a)
(b)
(c)
(d)
(e)
(f)The reconstructed images with same visual quality regardless of large PSNR difference are shown in Figure10. Inpainting with edges produces the results which are difficult to differentiate compared with H.264/AVC Intra. But the inpainting method reduces the bit rate because much less number of bits is required for coding edges. The proposed algorithm averagely saves 21.07% bit rate for images having high percentage of texture regions (mandrill and kodim13) when QP = 24 and it is shown in Table 2.Subjective quality comparison between the proposed scheme and H.264/AVC Intra. QP is 24 for high quality. From top to bottom: mandrill (43% removal) and kodim13 (42% removal). From left to right: incomplete image with black blocks; reconstructed image by the proposed scheme; reconstructed image by H.264/AVC Intra. Please note that the proposed scheme reconstructs both highly textured images with 21.07% bit-rate saving. Please observe that in kodim13 (the first row) the mandrill eye can also be reconstructed on both sides.
(a)
(b)The recent no-reference quality assessment method is adopted in this paper that is proposed in [26] to evaluate the proposed scheme in comparison with JPEG 2000 and H.264/AVC Intra. Note that in [26], blocking artifacts are detected within a compressed image. From Figure 11, it can be observed that the reconstructed images by the proposed scheme contain less blocking than those by JPEG 2000 and H.264/AVC Intra at similar compression ratios. The result shows the better bit-rate reduction when compared with previous methods as far as visual quality is concerned.Quality assessment (by measuring the blocking artifacts by the method in [26]) results that compare the proposed scheme with JPEG 2000 and H.264/AVC Intra on some typical color images.
(a)
(b)
(c)
(d)


### 4.3. Computational Complexity

For the experiment, Intel 2 GHz CPU is used. The shearlet domainp-Laplacian inpainting with the help of assistant information module is realized in MATLAB 2008a. According to our empirical results, the shearlet domain p-Laplacian inpainting process at the decoder needs averagely 3-4 iterations to converge. We found that the proposed scheme needs 1–3 s to decode a 768 × 512 image at 40% removal. The time complexity of inpainting is in general proportional to the size of removed regions.The proposed algorithm is simpler because of the presence of region removal and assistant information generation based on Discrete Shearlet Transform (DST).


## 4.1. Test Conditions and Parameters

The proposed algorithm is tested with color images from USC-SIPI and Kodak image database. In all testes, we use shearlet basep-Laplacian inpainting and we set the parameter values p=1.2, λ=0 for noiseless images and λ=0.08 for noisy images.


## 4.2. Overall Performance

Figure6 shows test image Lena and corresponding results of proposed system. In this test, edges are extracted from the input image and shown in Figure 6(b) and the image with removed blocks (25% removal) is shown in Figure 6(c).Comparison with JPEG 2000 with QP = 75. (a) Input image. (b) Edges. (c) Image with 25% of portions removed. (d) Reconstructed image after inpainting and texture synthesis. (e) Reconstructed image by JPEG 2000.
(a)
(b)
(c)
(d)
(e)Based on the preserved blocks, the shearletp-Laplacian inpainting gives results in Figure 6(d). When comparing the restored image in Figure 6(e) with JPEG 2000, proposed scheme saves 36.15% of bits with QP = 75. The comparison of standard images shows up to 50% bits saving which is achieved by the proposed scheme compared to JPEG 2000 and up to 31.61% bit saving compared to edge based image inpainting method proposed by Liu et al. [3]. The bit-saving results are shown in Table 1.Table 1
Bit-rate saving of proposed scheme compared to JPEG 2000 and edge based image inpainting method (QP = 75).
Original image
Block removal (%)
PSNR (dB)
Bit-rate (bpp)
Bit-rate saving (%)
JPEG 2000
Edge based image inpainting
Proposed scheme
Compared with JPEG 2000
Compared with edge based Image inpainting
Jet
25.0
45.67
1.156
0.919
0.780
32.53
15.13
Lena
25.0
37.23
1.112
0.888
0.710
36.15
20.05
Peppers
32.5
39.87
1.217
0.965
0.812
33.28
15.85
Kodim02
51.0
35.78
1.058
0.709
0.529
50.00
25.39
Kodim03
42.8
36.45
0.895
0.608
0.485
45.81
20.23
Kodim07
32.8
39.34
1.079
0.802
0.622
42.35
22.44
Kodim11
35.0
38.00
1.368
1.047
0.716
47.66
31.61
Kodim19
26.7
41.34
1.276
0.915
0.680
46.71
25.68
Kodim20
54.2
33.11
0.897
0.638
0.522
41.81
18.18
Kodim23
53.0
34.12
0.821
0.567
0.492
40.07
13.23Figure7 shows the reconstructed images by the proposed scheme with standard H.264/AVC Intracoding. The bit-rate saving is also noticeable, shown in Table 2, but not as much as the comparison with JPEG 2000. The proposed scheme can acquire 48.07% bit-rate saving compared to the state-of-the-art H.264 Intracoding with QP = 24 for an image Kodim19. Bit-rate saving of 33.01% is achieved for an image Kodim11 by the proposed scheme when compared with edge based image inpainting method.Table 2
Bit rate savings of proposed scheme compared to H.264/AVC intra and edge based image inpainitng method (QP = 24).
Original image
Block removal (%)
PSNR (dB)
Bit-rate (bpp)
Bit-rate saving (%)
H.264
Edge based image inpainting
Proposed scheme
Compared with H.264
Compared with edge based image inpainting
Jet
25.0
42.56
0.985
0.880
0.727
26.16
17.35
Lena
40.0
35.67
0.993
0.869
0.772
22.26
11.16
Peppers
32.5
36.45
1.311
1.080
0.818
37.61
24.27
Mandrill
43.0
36.48
0.880
0.783
0.691
21.47
11.74
Kodim02
51.0
32.11
0.948
0.701
0.510
46.20
27.25
Kodim03
42.8
34.23
0.710
0.562
0.495
30.28
11.92
Kodim07
32.8
35.00
0.876
0.751
0.671
23.38
10.63
Kodim11
35.0
36.78
1.354
1.098
0.736
45.68
33.01
Kodim13
42.0
37.02
0.900
0.872
0.714
20.66
18.12
Kodim19
26.7
39.36
1.246
0.956
0.647
48.07
32.32
Kodim20
54.2
30.00
0.823
0.636
0.473
42.49
25.58Comparison with H.264/AVC with QP = 24. (a) Jet (25% removal); (b) peppers (32.5% removal); (c) kodim05 (23% removal); (d) kodim02 (51% removal). The top row shows the reconstructed images by proposed scheme and the bottom row shows the reconstructed images by H.264/AVC Intracoding.
(a)
(b)
(c)
(d)Figure8 shows the comparison results with JPEG 2000. The first row in Figure 8 shows results of the proposed method and the second row presents JPEG 2000 results. The bits saving of proposed system is indicated in Table 1. The proposed scheme averagely saves 43.54% bits with QP = 75 for the five images shown in Figure 8. Peak Signal-to-Noise Ratio (PSNR) is also used to measure the quality of the restored images. It is defined as follows:
(17)PSNR=10log10(maxI2MSE),
where max⁡I is the maximum possible pixel value of the image.Comparison with JPEG 2000 with QP = 75. (a) Kodim07 (32.8% removal); (b) kodim23 (53% removal); (c) kodim03 (42.8% removal); (d) kodim20 (54.2% removal); (e) kodim11 (35% removal). The first row shows the restored images by proposed algorithm and the second row shows the restored images by JPEG 2000.
(a)
(b)
(c)
(d)
(e)Figure9 gives objective quality comparisons between the proposed scheme, JPEG 2000, and H.264/AVC Intracoding. It can be observed that the objective quality of the proposed scheme outperforms the two standard compression schemes (JPEG 2000 and H.264/AVC Intra) and edge based inpainting algorithm at both low and high bit rates. The proposed algorithm is adapted for subjective quality, and PSNR is not a good measure to evaluate the subjective quality, especially for the resulting images of p-Laplacian inpainting in shearlet domain.Objective quality comparison between proposed scheme, H.264/AVC Intra, and JPEG 2000 on some typical color images.
(a)
(b)
(c)
(d)
(e)
(f)The reconstructed images with same visual quality regardless of large PSNR difference are shown in Figure10. Inpainting with edges produces the results which are difficult to differentiate compared with H.264/AVC Intra. But the inpainting method reduces the bit rate because much less number of bits is required for coding edges. The proposed algorithm averagely saves 21.07% bit rate for images having high percentage of texture regions (mandrill and kodim13) when QP = 24 and it is shown in Table 2.Subjective quality comparison between the proposed scheme and H.264/AVC Intra. QP is 24 for high quality. From top to bottom: mandrill (43% removal) and kodim13 (42% removal). From left to right: incomplete image with black blocks; reconstructed image by the proposed scheme; reconstructed image by H.264/AVC Intra. Please note that the proposed scheme reconstructs both highly textured images with 21.07% bit-rate saving. Please observe that in kodim13 (the first row) the mandrill eye can also be reconstructed on both sides.
(a)
(b)The recent no-reference quality assessment method is adopted in this paper that is proposed in [26] to evaluate the proposed scheme in comparison with JPEG 2000 and H.264/AVC Intra. Note that in [26], blocking artifacts are detected within a compressed image. From Figure 11, it can be observed that the reconstructed images by the proposed scheme contain less blocking than those by JPEG 2000 and H.264/AVC Intra at similar compression ratios. The result shows the better bit-rate reduction when compared with previous methods as far as visual quality is concerned.Quality assessment (by measuring the blocking artifacts by the method in [26]) results that compare the proposed scheme with JPEG 2000 and H.264/AVC Intra on some typical color images.
(a)
(b)
(c)
(d)


## 4.3. Computational Complexity

For the experiment, Intel 2 GHz CPU is used. The shearlet domainp-Laplacian inpainting with the help of assistant information module is realized in MATLAB 2008a. According to our empirical results, the shearlet domain p-Laplacian inpainting process at the decoder needs averagely 3-4 iterations to converge. We found that the proposed scheme needs 1–3 s to decode a 768 × 512 image at 40% removal. The time complexity of inpainting is in general proportional to the size of removed regions.The proposed algorithm is simpler because of the presence of region removal and assistant information generation based on Discrete Shearlet Transform (DST).


## 5. Conclusion

In this paper, we develop an ANNs based image compression framework that adopts shearlet domain inpainting technique. In this proposed algorithm, the correlated regions are identified and removed automatically at the encoder. Then they are restored at the decoder by using inpainting scheme. The key techniques used for coding are gradient descent back propagation algorithm with adaptive learning rate andp-Laplacian image inpainting in shearlet domain. Experimental results show that the proposed scheme produces good results. The proposed scheme produces up to 50% and 48.07% bits saving when compared with JPEG 2000 and H.264/AVC Intra, respectively.Edge extraction can be flexible and adaptable for compression. Finding the regions that can be eliminated is considered to be an open problem and it seems that solving this problem will lead to increase in compression ratios and output quality.



---

*Source: 757318-2014-03-25.xml*