Abstract

A cascadic tensor multigrid method and an economic cascadic tensor multigrid method is presented for solving the image restoration models. The methods use quadratic interpolation as prolongation operator to provide more accurate initial values for the next fine grid level, and constructs a preserving-edge-denoising operator to obtain better edges and remove noise. The experimental results show that the new methods not only improves computational efficiency but also achieve better restoration quality.

1. Introduction

As a common information carrier, in the process of formation, transmission, recording, and processing, an image is easy to be affected by the equipment, environment, and other impacts of blurring, distortion, and so on. It is very important to recover effectively the blurred image. In recent years, image retoration problem has received extensive attention from scholars, and many models and algorithms have been proposed, such as super-resolution reconstruction ¹, image denoising ², image restoration ³, and so on.

In addition to the traditional vector-based image restoration model, some scholars use tensor methods to solve the image restoration problem. ⁴ constructs a tensor representation-based degradation model that applies tensor CP decomposition to color image and video recovery. ⁵ proposes a new tensor degeneracy model for color image and video recovery. The tensor degeneracy model can be recovered by solving the tensor equation under the Einstein-product.

Consider the following tensor color image model ⁶,

(1)

where denotes the blurred image, denotes the original image, denotes the 3D convolution operator, denotes the 3D Gaussian function, and denotes the noise function. The corresponding three-dimensional model of image can be ritten as the following tensor equation,

(2)

where denotes a tensor blurred operator, denotes tensor blurred images, denotes the image to be recovered, denotes random noise, denotes the Einstein-product.

The tensor Einstein-product is defined as follows: let , . Its elements are defined as

(3)

In order to solve the tensor equation (3) under the Einstein-product, scholars have proposed a number of effective methods. Brazell et al. ⁸ established a high order dual Conjugate Gradient method (CG) and a high order Jacobi methods. Wang et al. ⁹ proposed CG for solving the tensor equation under the Einstein-product and proved the finite termination of this method. Huang et al. ¹⁰ proposed Conjugate Residual method based on a tensor format (CR-BTF), Conjugate Gradient-Schmidt method based on a tensor format (CGS-BTF), and Bi-Conjugate Gradient method based on a tensor format (BiCG-BTF), etc. The convergence analysis of the methods is given, and the numerical results verify the feasibility of the methods.

Solving the tensor equation under the Einstein-product has some limitations when dealing with high-resolution color images, which require a large amount of memory. The cascadic resolution method ¹⁰ is a good image recovery algorithm.

Cascadic multigrid method is a simple and efficient method, please see ¹² and therein references. Based on the super-convergence and extrapolation methods, ¹³ constructs a better interpolation operator, to get a good initial value for the next iteration to speed up the convergence of the algorithm. ¹¹ proposes a class of nonlinear preserving-edge-denoising operator as the prolongation operator, which can reduce the ringing effect and recover good image edges. ¹⁴ uses a new quadratic interpolation method that can provide better initial values for fine grid levels. ¹⁵ further investigates the selection of blurred operator and smoothing methods and shows that the cascadic multigrid method has good efficiency for image recovery. An economic cascadic multigrid method is proposed in ¹⁶. Compared with the traditional cascadic multigrid method, this method proposes a new formula for the number of iterations, which can obtain the same numerical solution with fewer iterations.

In this paper, we construct the tensor form of the edge-preserving-denoising-operator and the prolongation operator and propose cascadic tensor multigrid method and an economic cascadic tensor multigrid algorithm for the tensor color image model (1). Finally, some experiments show that our algorithm is more efficient.

The structure of this paper is as follows. Section 2, introduces the basic definition of tensor Einstein-product and introduces the basic framework of the economic cascadic tensor multigrid method. Section 3, introduces the prolongation operator. Section 4, introduces edge-preserving-denoising-operator. In Section 5, some numerical results are given to illustrate the effectiveness of the new method. In Section 6, a summary is presented.

2. Preliminaries

The cascadic multigrid method is an efficient one-way multigrid method ¹⁷. Compared with linear interpolation, quadratic interpolation can provide better initial values for the fine grid level. ¹³ presents the following cascadic multigrid method.

Algorithm 1: Cascadic Multigrid Method (CMG) ¹³

Step 1: When , exact solution on the coarsest grid level ;

Step 2: When , iterative calculation:

(1) Prolongation: ;

(2) Smoothing: ;

(3) .

Where denotes the quadratic interpolation operator; denotes the smoothing of times in the th level, which satisfies , where , and can be chosen as a smoothing operator by a method such as conjugate gradient method.

Xu, Shi and Huang present an economical cascadic multigrid method, which requires less work operations on the each level, through control of the iteration numbers on the each level to preserve the accuracy without over iterations.

Algorithm 2: Economic Cascadic Multigrid Method (ECMG) ¹⁶

Step 1: When, exact solution on the coarsest grid level ;

Step 2: When ,iterative calculation:

(1) Prolongation: ;

(2) Smoothing: ;

(3) .

The number of iterations in the algorithm is chosen as follows.

(1) If , then

(2) If , then

Where , , , , ,. Here, denotes the smallest positive integer not less than .

In ¹⁸, a cascadic multigrid method for solving the image recovery problem is proposed. When dealing with color images, it is necessary to extend the method to three dimensions. The use of tensors is more advantageous for the processing of multidimensional data.

In ¹⁹, Chen and Li presented the tensor multigrid method to the Sylvester tensor equations, maintaining accuracy while potentially reducing time consumption. So we combine the ideas of tensor multigrid and cascadic multigrid methods, propose a cascadic tensor multigrid algorithm to solve the tensor equations under the Einstein-product to recover images.

Algorithm 3: Cascadic Tensor Multigrid Method (CTMG)

Step 1: When , the coarsest grid level is solved exactly for :

Step 2: When ,Iterative calculation:

(1) Prolongation:;

(2) Preserving-edge-denoising: ;

(3) Smoothing: ;

Step 3: .

where denotes the maximum number of level of the grid; denotes prolongation operator; denotes preserving-edge-denoising operator. The construction of and are introduced in Section 3 and Section 4. denotes cascadic multigrid method, where denotes smoothing times at the th level and satisfies , where . Conjugate Residual method based on tensor form (CR-BTF), Conjugate Gradient-Schmidt method (CGS-BTF), or Bi-Conjugate Gradient method (BiCG-BTF) etc. can be used as the smoothing operator.

Similarly we can obtain the following economic cascadic tensor multigrid method.

Algorithm 4: Economic cascadic tensor multigrid approach (ECTMG)

Step 1: When , the coarsest grid level is solved exactly for :

Step 2: When ,iterative computation:

(1) Prolongation: ;

(2) Preserving-edge-denoising : ;

(3) Smoothing: .

Step 3: .

The number of iterations in the algorithm is chosen as follows.

(1) If , then

(2) If , then

where, ,, , . Here, denotes the smallest positive integer not less than . CR-BTF , CGS-BTF , BiCG-BTF can be used as the smoothing operator.

3. Prolongation Operator

To improve the convergence speed of the algorithm, it is necessary to construct an effective prolongation operator to obtain a better initial value for the next level.

The image can be regarded as a tensor composed of R, G and B channels. In each channel, the image will be prolonged by the quadratic interpolation operator. The construction of the specific quadratic interpolation operator is introduced in ¹⁸.

In ¹⁸, as shown in (), the hollow circles represent pixels at the grid level, the solid black dots represent pixel values at the grid level, and the rectangular boxes represent pixel values at the grid level. The image values at the other color nodes are computed by quadratic interpolation.

Let denote the pixel values in on the level, denotes R,G,B channels respectly.

4. Tensor Preserving-Edge-Denoising Operator

The color image is a composite image consisting of three "gray matter" maps representing the R, G, and B channels. ¹⁸ describes the preserving-edge-denoising operator in matrix form. The preserving-edge-denoising operator is performed for images under R, G, and B channels respectively. In each channel, the basic principle is the equation ¹⁶ ,

(4)

where denotes the evolving image at time , and is the edge stopping function or a function of the diffusion coefficient that serves to make the image smooth inside the edges and therefore tends to 1. The diffusion coefficients are as follows.

(5)

where denotes the threshold value, which can be pre-set or changed with the result of each iteration of the image, and it is related to the variance of the noise. Let , the image preserving-edge-denoising process can be expressed in matrix form as

(6)

Where and denote the and moment images, respectively. denotes thematrix.

We perform (6) 10 times to achieve the effect of preserving image edges and removing noise.

5. Numerical Results

The image restore model can be expressed as the following tensor, i.e.

(7)

The blurred operator tensor is a sixth-order Toeplitz tensor [20-22] ²⁰ obtained from , that is,

(8)

where denotes a three-dimensional Gaussian function.

(9)

In our numerical experiments, let , we obtain different blurred operators and get different blurred images. And we add random noise to get the blurred and noise image . The correspondly image are shown in ().

Numerical evaluation indexes of image restoration are relative error (denoted by "RE") and the peak signal to noise ratio (denoted by "PSNR"), which are widely used in visual data restoration tasks.

where denotes the original image, denotes the recovered image, and are the dimensions of the tensor . denotes the maximum pixel value of the tensor of the original image. The size of the image is .

(Figure 4) and (Figure 5) show that CTMG methods, ECTMG methods are better than BICG-BTF, CGS-BTF and CR-BTF.

From (Table 1) to (Table 6) and (Figure 6) to (Figure 8), the economic cascadic tensor multigrid, approach achieve higher PSNR and cost less CPUs. ECTMG-CGS performs best with highest PSNR and least CPUs among these methods.

6. Summaries

In this paper, by combining tensor and cascadic multigrid, we present a tensor cascadic multigrid method and an economic tensor cascadic tensor multigrid method. The numerical results show that, compared with the existing methods, methods recover images with higher PSNR and smaller relative error, while reducing the CPU time. For the image restoration problems, CTMG and ECTMG perform better whether PSNR, RE or CPUs.

ACKNOWLEDGMENTS

This work was supported by Natural Science Foundation of China (12161027), Guangxi Natural Science Foundation (2020GXNSFAA159143).

References