Keywords

1 Introduction

Image decomposition into structure and texture is an important procedure for image understanding and analysis. Structure contains edges and hues of objects and texture is characterized as oscillations in the image. These individual components can be used, for example, for similarity analysis, texture synthesis, texture image segmentation [1], and structure or texture image inpainting [2, 3].

A common way to decompose an image into structure and texture is to use the variational approach. Vese and Osher proposed the first order Vese-Osher (FOVO) variational model [4] that combines Meyer’s oscillating function [5] for texture images with the total variation (TV) model [6]. However, the FOVO model suffers from the undesirable staircase effect - the decomposed structure image has a uneven appearance. This is because energy minimization in the bounded variation (BV) space [6] results in a piecewise constant objective function, leading to the staircase effect. High order variational models can be used to remedy this side effect. However, the high order models usually contain second order derivatives which lead to nonlinear fourth-order partial differential equations (PDEs) that are very difficult to discretize to solve computationally.

In this paper, we propose a second order Vese-Osher (SOVO) model for image decomposition to overcome these problems with existing models mentioned above. The proposed model replaces the first order regularizer in original FOVO model with the second order regularizer used in Lysaker-Lundervold-Tai (LLT) model [7], which enables it to decompose an image into an oscillating texture component and a structure part without the staircase effect. Instead of solving high order nonlinear PDEs, the split Bregman algorithm [8], which has been successfully applied to optimise L1-based variational models, is adapted to transform the energy minimization problem of the proposed SOVO decomposition model into four subproblems. These subproblems are then efficiently solved by fast Fourier transform (FFT) and analytical soft thresholding equations without any iteration. We validate the new model through extensive experiments.

2 The Proposed SOVO Model

In order to extract the structure and texture components, Meyer defined the Banach space G as follows

$$\begin{aligned} G = \left\{ {v\left| {v = div\left( g \right) ,\;g = \left( {{g_1},{g_2}} \right) \in {L^\infty }} \right. } \right\} \ \end{aligned}$$

where \(div\left( \cdot \right) \) is divergence operator and \(div\left( g \right) = {\partial _x}{g_1} + {\partial _y}{g_2}\). The space G is equipped with the following norm

$$\begin{aligned} {\left\| v \right\| _G} = \mathop {\inf }\limits _{g = \left( {{g_1},{g_2}} \right) } \left\{ {{{\left\| {\sqrt{g_1^2 + g_2^2} } \right\| }_{{L^\infty }}}\left| {v = div\left( g \right) ,\;g \in {L^\infty },\; \left| g \right| \mathrm{{ = }}\sqrt{g_1^2\mathrm{{ + }}g_2^2} } \right. } \right\} \ \end{aligned}$$

A function belonging to space G may have large oscillation and a small norm. Thus the G norm can be adapted to capture the oscillations of a function in energy minimization. As such, Meyer proposed the following image decomposition model (2.1)

$$\begin{aligned} \mathop {\min }\limits _{u \in BV\left( \varOmega \right) } \left\{ {E\left( u \right) = \int _\varOmega {\left| {\nabla u} \right| } + \lambda {{\left\| v \right\| }_G},\;f = u + v} \right\} \ \end{aligned}$$
(2.1)

where \(\varOmega \) is an open and bounded domain and an input image function f is defined on \(\varOmega \). Function u is defined in BV space and represents the non-oscillating structure part. The first term in this model is total variation of u, which helps to preserve sharp edges or contours of objects. Function v in the second term belonging to space G denotes the oscillating part (texture or noise) of an image. The model only replaces the \({L^2}\) norm in the data fitting term of the TV/ROF model by the G norm. However, it is not possible to derive the Euler-Lagrange equation for the G norm to use a straightforward PDE method to solve it.

To implement the model numerically, Vese and Osher [4] first propose the FOVO model based on div \(\left( {{L^p}} \right) \) norm

$$\begin{aligned} \mathop {\min }\limits _{u,g} \left\{ {E\left( {u,g} \right) = \frac{1}{2}\int _\varOmega {{{\left( {f - u - div\left( g \right) } \right) }^2}} + \lambda \int _\varOmega {\left| {\nabla u} \right| } + \gamma {{\left[ {\int _\varOmega {\;{{\left| g \right| }^p}} } \right] }^{{1/p}} }}\right\} \end{aligned}$$
(2.2)

where \(p \ge 1\). \(\lambda \) and \(\gamma \) are two positive tuning parameters balancing the three energy terms. Vese and Osher also confirmed that there are no obvious numerical differences using different values of p, with \(1 \le p \le 10\). However, the case \(p=1\) yields faster calculation. However, as the term \(\int _\varOmega {\left| {\nabla u} \right| }\) in (2.2) is defined in BV space, leading to piecewise constant result (i.e. staircase effect) in the decomposed structure.

To avoid this side effect without blurring edges of objects, we directly incorporate the second order derivative information into the original FOVO model, that is, we replace the first order TV term with the second order one. Our proposed SOVO model then becomes

$$\begin{aligned} \mathop {\min }\limits _{u,g} \left\{ {E\left( {u,g} \right) = \frac{1}{2}\int _\varOmega {{{\left( {f - u - div\left( g \right) } \right) }^2}} + \lambda \int _\varOmega {e\left( {\left| {\nabla u} \right| } \right) \left| {{\nabla ^2}u} \right| } + \gamma \int _\varOmega {\left| g \right| } } \right\} \end{aligned}$$
(2.3)

where \({\nabla ^2}u\) denotes the Hessian matrix of u over image domain \(\varOmega \). And the diffusivity e is defined as follows

$$\begin{aligned} e\left( s \right) = 1 - \exp \left( {\frac{{ - {C_h}}}{{{{\left( {{s {\big /} \lambda }} \right) }^h}}}} \right) \end{aligned}$$

The constant \(C_h\) is automatically calculated in such way that \({\left. {\left( {{{\partial \varPhi \left( s \right) } \big / {\partial s}}} \right) } \right| _{s = \lambda }} = 0\), where \(\varPhi \left( s \right) = se\left( s \right) \). Parameter h determines how fast the diffusivity e changes, and \(\lambda \) controls smoothness of function u.

The new regularizer \(\int _\varOmega {\left| {{\nabla ^2}u} \right| }\) with diffusivity e in (2.3) has shown good performance in image decomposition producing smooth structures while preserving the edge features. Traditionally, the optimisation problem is solved directly by gradient decent flow leading to a fourth order nonlinear PDE which is very complicated to discretize. Even though the semi-implicit finite difference can be imposed, it is still computationally expensive. In addition, if directly deriving the Euler-Lagrange equations of the vector function g used to represent oscillating part of an image in the proposed model, we obtain another two PDEs with respect to \(g_1\) and \(g_2\), which are not analytical. To solve the equations, we need to use semi-implicit fixed-point iteration method to iterate \(g_1\) and \(g_2\) until convergence. Inevitably, this iterative process needs additional computing time. We will address the challenge of computational efficiency in next section.

3 The Split Bregman Algorithm

In Goldstein-Osher [8], fast iterative schemes were proposed and tested for the TV model. It is one of most efficient numerical schemes for solving the L1-based variational models [11, 12]. There exist some other fast algorithms. For example, the fast dual projection algorithm was adopted [9, 10, 13] to efficiently solve the second order texture-extraction models. Moreover, the more recent augment Lagrangian method [14, 15] also attracts attention due to its extensive applications to the variational models such as LLT model [7], Euler-elastic model [16, 17], mean-curvature model [18], and TV-Stokes model [19]. In this section, we apply split Bregman algorithm to solve the proposed SOVO model. The idea is to first split the original minimization problem into several subproblems by introducing some auxiliary variables, and then solve each subproblem. We first transform the unconstrained minimization problem (2.3) into minimising the following constrained functional

$$\begin{aligned} {E\left( {u,g,w,m} \right) = \frac{1}{2}\int _\varOmega {{{\left( {f - u - div\left( g \right) } \right) }^2}} + \lambda \int _\varOmega {e\left| w \right| } + \gamma \int _\varOmega {\left| m \right| } } \end{aligned}$$
(3.1)

with constraints \(w = {\nabla ^2}u\) and \(m=g\). In (3.1), vector function \(m = \left( {{m_1},{m_2}} \right) \in {\left( {{R^{M \times N}}} \right) ^2}\) is related to function g, and \(w = \left( \begin{array}{l} {w_1},{w_2}\\ {w_3},{w_4} \end{array} \right) \in {\left( {{R^{M \times N}}} \right) ^4}\) is a matrix valued function related to the Hessian of the function u. \(\left| w \right| = \sqrt{\sum \nolimits _{1 \le n \le 4} {{{\left( {{w_n}} \right) }^2}} }\) stands for the Frobenius norm of the matrix w. The two constraints above can be enforced effectively via the Bregman distance technique. Two Bregman iteration parameters \({b_1} = \left( \begin{array}{l} {b_{11}},{b_{12}}\\ {b_{13}},{b_{14}} \end{array} \right) \in {\left( {{R^{M \times N}}} \right) ^4}\) and \({b_2} = \left( {{b_{21}},{b_{22}}} \right) \in {\left( {{R^{M \times N}}} \right) ^2}\) are introduced to transform the constrained functional (3.1) into following

$$\begin{aligned} E\left( {u,g,w,m;{b_1},{b_2}} \right)&= \frac{1}{2}\int _\varOmega {{{\left( {f - u - div(g)} \right) }^2}}\nonumber \\&\quad +\, \lambda \int _\varOmega {e\left| w \right| } + \frac{{{\theta _1}}}{2}\int _\varOmega {{{\left| {w - {\nabla ^2}u - {b_1}} \right| }^2}} \\&\quad +\, \gamma \int _\varOmega {\left| m \right| } \; + \frac{{{\theta _2}}}{2}\int _\varOmega {{{\left| {m - g - {b_2}} \right| }^2}} \nonumber \end{aligned}$$
(3.2)

where \(\theta _1\) and \(\theta _2\) are two positive penalty parameters. It is known that one of saddle points for functional (3.2) will give a minimizer for the constrained minimization problem (3.1). In practice, it is very difficult to directly solve the minimization problem (3.2), so we have developed an alternative optimization method. Specifically, we split (3.2) into four subproblems for u, g, w and m each of which can be solved quickly. The following section will introduce how to solve the four subproblems.

4 Solving the Subproblems

4.1 Minimization of Subproblem with Respect to u

$$\begin{aligned} u = \mathop {\mathrm{{argmin}}}\limits _{u \in {R^{M \times N}}} \left\{ {E\left( u \right) = \frac{1}{2}\int _\varOmega {{{\left( {f - u - div\left( g \right) } \right) }^2}} + \frac{{{\theta _1}}}{2}\int _\varOmega {{{\left| {w - {\nabla ^2}u - {b_1}} \right| }^2}} } \right\} \end{aligned}$$

Deriving its Euler-Lagrange equation leads to following fourth order linear PDE

$$\begin{aligned} u + {\theta _1}di{v^2}\left( {{\nabla ^2}u} \right) = f - div\left( g \right) - {\theta _1}di{v^2}\left( {{b_1} - w} \right) \end{aligned}$$
(4.1)

\(div^2\) denotes second order divergence operator. By applying discrete Fourier transform to the both sides of equation (4.1), one can obtain

$$\begin{aligned} \underbrace{\left[ {1 + 4{\theta _1}{{\left( {\cos \frac{{2\pi s}}{N} + \cos \frac{{2\pi r}}{M} - 2} \right) }^2}} \right] }_\xi {\mathcal{F}}\left( {{u}} \right) = {\mathcal{F}}\left( {{G}} \right) \end{aligned}$$
(4.2)

where \(G=f - div\left( g \right) - {\theta _1}di{v^2}\left( {{b_1} - w} \right) \). \(i \in \left[ {1,M} \right] \) and \(j \in \left[ {1,N} \right] \) are the indexes in discrete time domain. \(r \in \left( {1,M} \right) \) and \( s \in \left( {1,N} \right) \) are the frequencies in the discrete frequency domain. (4.2) provides us with a closed-form solution of u as

$$\begin{aligned} u = \mathfrak {R}\left( {\mathcal{F}{^{ - 1}}\left( {\frac{{\mathcal{F}\left( {{G}} \right) }}{\xi }} \right) } \right) \end{aligned}$$

\(\mathcal F\) and \( \mathcal{F}^{-1}\) denote the discrete Fourier transform and inverse Fourier transform respectively. \(\mathfrak {R}\) is the real part of a complex number. “—” stands for pointwise division of matrices.

4.2 Minimization of Subproblem with Respect to g

$$\begin{aligned} g = \mathop {\mathrm{{argmin}}}\limits _{g \in {{\left( {{R^{M \times N}}} \right) }^2}} \left\{ {E\left( g \right) = \frac{1}{2}\int _\varOmega {{{\left( {f - u - div\left( g \right) } \right) }^2} + \frac{{{\theta _2}}}{2}\int _\varOmega {{{\left| {m - g - {b_2}} \right| }^2}} } } \right\} \ \end{aligned}$$

Its Euler-Lagrange equation is given by

$$\begin{aligned} -div\left( g \right) + {\theta _2}g = \nabla \left( {u - f} \right) - {\theta _2}\left( {b - m} \right) \end{aligned}$$

By applying discrete Fourier transform to the both sides of equation, we have

$$\begin{aligned} \left( \begin{array}{l} {a_{11}}\quad {a_{12}}\\ {a_{21}}\quad {a_{22}} \end{array} \right) \left( \begin{array}{l} \mathcal{F} {{{\left( {{g_1}} \right) }}} \\ \mathcal{F} {{{\left( {{g_2}} \right) }}} \end{array} \right) = \left( \begin{array}{l} \mathcal{F} {{{\left( {{h_1}} \right) }}} \\ \mathcal{F} {{{\left( {{h_2}} \right) }}} \end{array} \right) \ \end{aligned}$$

where the coefficients are

$$\begin{aligned} \begin{array}{l} {a_{11}} = {\theta _2} - 2\left( {\cos \frac{{2\pi s}}{N} - 1} \right) \\ {a_{12}} = - \left( { - 1 + \cos \frac{{2\pi s}}{N} + \sqrt{ - 1} \sin \frac{{2\pi s}}{N}} \right) \left( {1 - \cos \frac{{2\pi r}}{M} + \sqrt{ - 1} \sin \frac{{2\pi r}}{M}} \right) \\ {a_{21}} = - \left( { - 1 + \cos \frac{{2\pi r}}{M} + \sqrt{ - 1} \sin \frac{{2\pi r}}{M}} \right) \left( {1 - \cos \frac{{2\pi s}}{N} + \sqrt{ - 1} \sin \frac{{2\pi s}}{N}} \right) \\ {a_{22}} = {\theta _2} - 2\left( {\cos \frac{{2\pi r}}{M} - 1} \right) \end{array} \end{aligned}$$

with

$$\begin{aligned} {h_1} = {\nabla _x}\left( {u - f} \right) - {\theta _2}\left( {{b_{21}} - {m_1}} \right) \end{aligned}$$
$$\begin{aligned} {h_2} = {\nabla _y}\left( {u - f} \right) - {\theta _2}\left( {{b_{22}} - {m_2}} \right) \end{aligned}$$

We have \(M \times N\) numbers of \(2 \times 2\) systems. The determinant of the coefficient matrix \( \left( \begin{array}{l} {a_{11}}\;{a_{12}}\\ {a_{21}}\;{a_{22}} \end{array} \right) \) is

$$\begin{aligned} D = \theta _2^2 - 2{\theta _2}\left( {\cos \frac{{2\pi s}}{N} + \cos \frac{{2\pi r}}{M} - 2} \right) \end{aligned}$$

which is always positive for all discrete frequencies if \({\theta _2} > 0\). After the systems of linear equations are solved for each frequency r and s over the discrete frequency domain, we use the discrete inverse Fourier transform to obtain

$$\begin{aligned} {{g_1} = \mathfrak {R}\left( {{{\mathcal{F}}^{ - 1}}\left( {\frac{{{a_{22}}\mathcal{F}\left( {{h_1}} \right) - {a_{12}}\mathcal{F}\left( {{h_2}} \right) }}{D}} \right) } \right) } \end{aligned}$$
$$\begin{aligned} {{g_2} = \mathfrak {R}\left( {{\mathcal{F}^{ - 1}}\left( {\frac{{{a_{11}}\mathcal{F}\left( {{h_2}} \right) - {a_{21}}\mathcal{F}\left( {{h_1}} \right) }}{D}} \right) } \right) } \end{aligned}$$

4.3 Minimization of Subproblem with Respect to w and m

The minimisation problems of w and m works in a same manner. Both of their solutions are form of analytical generalised soft thresholding equation. Specifically, we solve the following two problems

$$\begin{aligned} w = \mathop {\mathrm{{argmin}}}\limits _{w \in {{\left( {{R^{M \times N}}} \right) }^4}} \left\{ {E\left( w \right) = \lambda \int _\varOmega {e \left| w \right| } + \frac{{{\theta _1}}}{2}\int _\varOmega {{{\left| {w - {\nabla ^2}u - {b_1}} \right| }^2}} } \right\} \end{aligned}$$
$$\begin{aligned} m = \mathop {\mathrm{{argmin}}}\limits _{m \in {{\left( {{R^{M \times N}}} \right) }^2}} \left\{ {E\left( m \right) = \gamma \int _\varOmega {\left| m \right| dx + \frac{{{\theta _2}}}{2}\int _\varOmega {{{\left| {m - g - {b_2}} \right| }^2}} } } \right\} \end{aligned}$$

Their solutions respectively read

$$\begin{aligned} w = \max \left( {\left| {{\nabla ^2}u + {b_1}} \right| - \frac{{\lambda e}}{{{\theta _1}}},0} \right) \frac{{{\nabla ^2}u + {b_1}}}{{\left| {{\nabla ^2}u + {b_1}} \right| }} \end{aligned}$$
$$\begin{aligned} m = \max \left( {\left| {g + {b_2}} \right| - \frac{\gamma }{{{\theta _2}}},0} \right) \frac{{g + {b_2}}}{{\left| {g + {b_2}} \right| }}\ \end{aligned}$$

with the convention that \(0\big /0 = 0\). The above equation is known as the analytical soft thresholding equation or shrinkage.

After the minimizers of the four subproblems are found, we can update Bregman iterative parameters in (3.2) as follows

$$\begin{aligned} {b_1} = {b_1} + {\nabla ^2}u - w \end{aligned}$$
$$\begin{aligned} {b_2} = {b_2} + g - m\ \end{aligned}$$
Fig. 1.
figure 1

Main test images (resolution \(510 \times 520\)).

Full size image

5 Experimental Results

In this section, we use an example to illustrate the effectiveness of our proposed SOVO model. More experimental results will be performed in the forthcoming paper. Decomposition results on Fig. 1 (b) by the proposed SOVO model, TV (ROF) model [6], FOVO model [4], Chambolle’s Inf-convolution model [21] and TGV model proposed by Bredies et al. [20] are shown from Figs. 2 to 5. The quality of the decomposed images is validated quantitatively by the SSIM index [22].

In Fig. 2, the decomposed structures and their corresponding SSIM calculated from the reference image Fig. 1 (a) are given. It is clear to see that some texture still remains in the result by TV model, leading to the lowest SSIM. FOVO model outperforms TV model as there is no texture left in its decomposed result. However, the staircase effect appears, which makes the result less appealing. From Fig. 2 (c) and (d). The high order Inf-convolution and TGV models give good and smooth output whilst preserving the edge features. As Inf-convolution slightly blur edges of the decomposed structure, and it does not outperform TGV model. The proposed SOVO model achieves the best visual and quantitative evaluation result. It decomposes all texture while removes the staircase effect and preserves the sharp edges.

Fig. 2.
figure 2

Decomposed structural components of Fig. 1 (b) by different methods. The resulting SSIMs from left to right are 0.3958, 0.6934, 0.7725, 0.8225, and 0.8551, respectively.

Full size image
Fig. 3.
figure 3

A middle slice for detailed comparisons.

Full size image
Fig. 4.
figure 4

Decomposed textural components of image Fig. 1 (c) by different methods.

Full size image

In Fig. 4, the rescaled decomposed textural components by different models are presented. Figure 4 (a) is the pure texture image computed by rescaling the result of Fig. 3 (a) minus Fig. 3 (b). We do not list the SSIM index in the Figure as it is not accurate after rescaling. However, one can observe Fig. 4 (b), (d) and (e) contain more structure of original image Fig. 1 (a) than these by FOVO and SOVO models. Thus, Fig. 4 (e) and (f) are more similar to the Fig. 4 (a). Note that TV, Inf-convolution and TGV models simply use the \(L^2\) norm to capture the oscillations while the FOVO and SOVO models apply \(L^1\) norm of \(\left| g\right| \). The latter is more capable of extracting oscillatory pattern from the textural signal.

In Fig. 3, the middle slices of the image Fig. 1 (b) are shown and its corresponding decomposition results are shown in Fig. 2. The conclusions are consistent with Fig. 2. It is more obvious that the proposed model outperforms the other fours in terms of capability of textural removal and smoothness and sharp edges/corners preservation.

To examine the quality of the decomposed structural parts in Fig. 2 as the number of iteration increases, we have plotted the evolution of SSIM values in Fig. 5. In the horizontal axis, instead of the number of iterations we put the absolute CPU time calculated by multiplying the number of iterations and CPU time per iteration. We also designed fast split Bregman algorithm for TV, Inf-convolution, and TGV models for comparison with our algorithm. The fixed point iteration method is applied to the FOVO model. For TV and FOVO models, their corresponding SSIM value increases at the beginning of iterations and then drops when the staircase effect appears. The SSIM values of Inf-convolution, TGV and SOVO models increase dramatically before 5 seconds and then remain stable. The split Bregman is also used for TV, Inf-convolution, TGV and SOVO models, and performed faster than the FOVO model.

Fig. 5.
figure 5

Evolution of the SSIM index with absolute CPU time for the examples in Fig. 2.

Full size image

6 Conclusion

In this paper, we proposed the SOVO model for image decomposition, which can decompose an image into texture and structure without introducing the staircase effect. The advantages of our model also include computational efficiency by using the split Bregman algorithm to avoid numerically solving high order PDEs. We provided the implementation details of the split Bregman algorithm for solving the proposed model efficiently. Extensive experiments demonstrate that the proposed second order model performs better than the existing image decomposition models. Our future work will extend the proposed SOVO model to image denoising and decomposition [23] for real world applications such as medical imaging [24].