9.1 A class of fast algorithms for total variation image restoration  (Page 5/6)

for all $k$ sufficiently large, where $T_{EE}={\left[T_{i,j}\right]}_{i,j\in E\cup (n^2+E)}$ is a minor of $T$ , ${\parallel v\parallel }_M^2=v^{\top }Mv$ and $\rho (·)$ is the spectral radius of its argument.

Extensions to multichannel images and tv/l

The alternating minimization algorithm given in "A New Alternating Minimization Algorithm" can be extended to solve multichannel extension of ( ) when the underlying image has more than one channels and TV/L ${}^1$ when the additive noise is impulsive.

Multichannel image deconvolution

Let $\overline{u}=[{\overline{u}}^{\left(1\right)};...;{\overline{u}}^{\left(m\right)}]\in {\mathbb{R}}^{m{n}^2}$ be an $m$ -channel image, where, for each $j$ , ${\overline{u}}^{\left(j\right)}\in {\mathbb{R}}^{n^2}$ represents the $j$ th channel. An observation of $\overline{u}$ is modeled by ( ), in which case $f=[f^{\left(1\right)};...;f^{\left(m\right)}]$ and $\omega =[{\omega }^{\left(1\right)};...;{\omega }^{\left(m\right)}]$ have the same size and the number of channels as $\overline{u}$ , and $K$ is a multichannel blurring operator of the form

where $K_{ij}\in {\mathbb{R}}^{n^2\times n^2}$ , each diagonal submatrix $K_{ii}$ defines the blurring operator within the $i$ th channel, and each off-diagonal matrix $K_{ij}$ , $i\ne j$ , defines how the $j$ th channel affects the $i$ th channel.

The multichannel extension of ( ) is

where $I_m$ is the identity matrix of order $m$ , and“ $\otimes$ " is the Kronecker product. By introducing auxiliary variables ${\mathbf{w}}_i\in {\mathbb{R}}^{2m}$ , $i=1,...,n^2$ , ( ) is approximated by

For fixed $u$ , the minimizer function for $\mathbf{w}$ is given by ( ) in which $D_{i}u$ should be replaced by $(I_m\otimes D_i)u$ . On the other hand, for fixed $\mathbf{w}$ , the minimization for $u$ is a least squares problem which is equivalent to the normal equations

where $w$ is a reordering of variables in a similar way as given in ( ). Under the periodic boundary condition, ( ) can be block diagonalized by FFTs and then solved by a low complexity Gaussian elimination method.

Deconvolution with impulsive noise

When the blurred image is corrupted by impulsive noise rather than Gaussian, we recover $\overline{u}$ as the minimizer of a TV/L ${}^1$ problem. For simplicity, we again assume $\overline{u}\in {\mathbb{R}}^{n^2}$ is a single channel image and the extension to multichannel case can besimilarly done as in "Multichannel image deconvolution" . The TV/L ${}^1$ problem is

Since the data-fidelity term is also not differentiable, in addition to $\mathbf{w}$ , we introduce $z\in {\mathbb{R}}^{n^2}$ and add a quadratic penalty term. The approximation problem to ( ) is

where $\beta ,\gamma \gg 0$ are penalty parameters. For fixed $u$ , the minimization for $\mathbf{w}$ is the same as before, while the minimizer function for $z$ is given by the famous one-dimensional shrinkage:

On the other hand, for fixed $\mathbf{w}$ and $z$ , the minimization for $u$ is a least squares problem which is equivalent to the normal equations

Similar to previous arguments, ( ) can be easily solved by FFTs.

Experiments

In this section, we present the practical implementation and numerical results of the proposed algorithms. We used two images,Man (grayscale) and Lena (color) in our experiments, see . The two images are widely used in the field of image processing because they contain nice mixture of detail, flatregions, shading area and texture.