# Multiscale Image Representation and Texture Extraction Using Hierarchical Variational Decomposition

Authors: Liming Tang; Chuanjiang He
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

In order to achieve a mutiscale representation and texture extraction for textured image, a hierarchical(BV,Gp,L2) decomposition model is proposed in this paper. We firstly introduce the proposed model which is obtained by replacing the fixed scale parameter of the original (BV,Gp,L2) decomposition with a varying sequence. And then, the existence and convergence of the hierarchical decomposition are proved. Furthermore, we show the nontrivial property of this hierarchical decomposition. Finally, we introduce a simple numerical method for the hierarchical decomposition, which utilizes gradient decent for energy minimization and finite difference for the associated gradient flow equations. Numerical results show that the proposed hierarchical (BV,Gp,L2) decomposition is very appropriate for multiscale representation and texture extraction of textured image.


---

## Body

## 1. Introduction

A grayscale image can be represented by a functionf:(x,y)∈Ω→ℝ with f∈L2(Ω), where Ω is an open, bounded, and connected subset of ℝ2, typically a rectangle or a square [1, 2]. We are interested in the decomposition of f into two components, f=u+v [3–5], or three components, f=u+v+r [6–9], where u represents piecewise-smooth (cartoon or structure) component of f and v represents the oscillatory component of f, that is, texture, and r represents the residual (noise). Image decomposition is an important image processing task, which is widely used in image denoising [4, 10, 11], deblurring [12, 13], image representation [5, 13], texture extraction or discrimination [6, 14], and so on. It has seen much recent progress, much of which has particularly been made through the use of variational framework to model oscillatory component that represents texture; see, for example, [2–6, 8–14]. We give here some classical examples of image decomposition models by variational approaches that are most related to our present work.A celebrated decomposition easier to implement is the total variation (TV) minimization model by Rudin, Osher, and Fatemi (ROF) [3] for image denoising, in which an image f∈L2(Ω) is split into u∈BV(Ω) and v∈L2(Ω):
(1)(u,v)=arg inf{J(f;u,v)=|u|BV(Ω)+μ∥v∥L2(Ω),f=u+v},
which yields so-called (BV,L2) decomposition. This model is convex and easy to solve in practice. The function u∈BV(Ω) allows for discontinuities along curves; therefore, edges and contours are preserved in the restored image u.However, as Meyer pointed out in [15], the function space L2(Ω) is not the most suitable one to model oscillatory components, since the oscillatory functions do not have small L2-norms. He suggested using (BV(Ω))′, the dual space of BV(Ω), instead of L2(Ω) for the oscillatory components. However, there is no known integral representation of continuous linear functional on BV(Ω). To address this problem, Meyer used another slightly larger space to approximate (BV(Ω))′. Using G(Ω) to characterize oscillatory components yields the (BV,G) decomposition by solving the following variational problem:
(2)infu∈BV(Ω),v∈G(Ω){|u|BV(Ω)+μ∥v∥G(Ω),f=u+v}.
The (BV,G) decomposition model can better extract texture; however, it cannot be directly solved in practice due to the nature of the G-norm [4, 6, 14], for which there is no standard calculation of the associated Euler-Lagrange equation. Vese and Osher [6, 14] first overcame this difficulty by replacing the space G(Ω) with Gp(Ω) (p≥1). Then, the (BV,G) decomposition model (2) is approximated by the following minimization problem:
(3)infu∈BV(Ω),v∈Gp(Ω){|u|BV(Ω)+μ∥v∥Gp(Ω),f=u+v}.In [6], Vese and Osher did not solve (3) directly but adapted the model by adding a fidelity term into the energy functional to guarantee f≈u+v. In detail, their variational formulation is defined as
(4)infu∈BV(Ω),v∈Gp(Ω){|u|BV(Ω)+λ∥f-u-v∥L2(Ω)2+μ∥v∥Gp(Ω)}.
In this (BV,Gp,L2) decomposition, the image f is discomposed into three components, f=u+v+r with u∈BV(Ω), v∈Gp(Ω), and r∈L2(Ω).The previous models are examples of a larger class of the fixed scale decompositions (the scale parameters in these models are fixed). It has been argued that a human visualizes a scene in multiple scales [16, 17]. Then, multiscale approaches are appropriate for image representation because a single scale may not be a perfect simulation of the human visual perception. In order to achieve reliable image information in different scales, both the large-scale and small-scale behaviors should be investigated and incorporated appropriately. Thus, a natural way to address this problem is the multiscale analysis.Tadmor et al. [5, 13] presented a hierarchical decomposition based on the ROF model (1) to achieve multiscale image representation, in which the scale parameter is not fixed, but a varying sequence: starting with an initial scale μ0,
(5)f=u0+v0,(u0,v0)=arg inf{|u|BV(Ω)+μ0∥v∥L2(Ω)2,f=u+v},
and then, successive application of the following dyadic refinement step
(6)vi=ui+1+vi+1,(ui+1,vi+1)=arg inf{2i+1∥v∥L2(Ω)2|u|BV(Ω)+μ02i+1∥v∥L2(Ω)2,vi=u+v}
produces, after k such steps, the hierarchical (BV,L2) decomposition of f:
(7)f=∑i=0kui+vk,(k=0,1,…).In this study, we focus on multiscale representation and texture extraction for textured image. As discussed previously, the(BV,L2) decomposition is not the best one for textured image, so using hierarchical (BV,L2) decomposition (7) introduced by Tadmor et al. to implement multiscale representation and texture extraction for textured image is obviously not the best choice. We thus in this paper propose the hierarchical decomposition using the (BV,Gp,L2) model (4), which enables us to capture an intermediate regularity between L2(Ω) and BV(Ω) and oscillation between L2(Ω) and Gp(Ω). We here adopt (BV,Gp,L2) decomposition because Gp(Ω) is a very suitable function space to model oscillatory patterns [6, 14]; in addition, the Gp-norm is easier to solve in practice. In the proposed hierarchical (BV,Gp,L2) decomposition, the scale parameter is not fixed but varies over a sequence of dyadic scales. Consequently, the decomposition of a textured image is not predetermined but is resolved in terms of layers of intermediate scales. So, we can achieve multiscale image representation. Compared to Tadmor et al.’s 2-tuple hierarchical decomposition, the proposed 3-tuple hierarchical decomposition can precisely extract texture in different scales.


## 2. Preliminaries

So far, there have been a lot of efficient variational decomposition models for textured image, much of which follows Meyer’s work. The(BV,Gp,L2) decomposition introduced by Vese and Osher is the first one to practically solve the Meyer’s (BV,G) model presented in (2), in which cartoon component is measured in BV(Ω) and texture component in Gp(Ω), instead of G(Ω). We here recall the definition and some known results of BV(Ω), G(Ω) and Gp(Ω), which are much related to our present study.Definition 1.
LetΩ⊂ℝ2 be an open subset with Lipschitz boundary. Then, BV(Ω) is the subspace of L1(Ω) such that the following quantity
(8)|u|BV(Ω)=∫Ω|Du|=sup{∫Ωudiv(φ)dx∣φ∈Cc1(Ω,R2),∥φ∥L∞≤1∫Ωudiv(φ)dx∣φ∈Cc1(Ω,R2)}
is finite. Further, ∥u∥BV(Ω)=∥u∥L1(Ω)+|u|BV(Ω) is called the BV-norm.Remark 2.
B
V
(
Ω
) with the norm of ∥u∥BV(Ω) is a Banach space, but one does not use this norm since it possesses no good compactness property. Classically, in BV(Ω) one works with the BV-weak* topology, which is defined as un convergence to u in BV-weak* topology if and only if un converges to u strongly in L1(Ω) and ∫ΩφDun converge to ∫ΩφDu for all φ in Cc(Ω,ℝ2).
Theorems3 and 4 show the compactness and lower semicontinuity of BV(Ω).Theorem 3 (see [18]).
Ifun is a uniformly bounded sequence in BV(Ω), then there exist a subsequence unkand u in BV(Ω) such that unk converge to u in the BV-weak* topology.Theorem 4 (see [19, 20]).
Forun∈BV(Ω), if there exists u∈BV(Ω) such that un converge to u in the BV-weak* topology, then |u|BV≤lim_n→+∞|un|BV.Definition 5.
G
(
Ω
) consists of distributions v which can be written as
(9)v=∂1g1+∂2g2=div(g),g∈L∞(Ω;R2),g·n=0on∂Ω,
endowed with the norm
(10)∥v∥G(Ω)=inf{∥g∥L∞(Ω)∣v=div(g),g·n=0on∂Ω}.Definition 6.
G
p
(
Ω
) consists of distributions v which can be written as
(11)v=∂1g1+∂2g2=div(g),g∈Lp(Ω;R2),g·n=0on∂Ω,
endowed with the norm
(12)∥v∥Gp(Ω)=inf{∥g∥Lp(Ω)∣v=div(g),g·n=0on∂Ω}.
For every1≤p<∞, the space Gp(Ω) above can be identified with the space W-1,p(Ω), the dual space to the Sobolev space W01,q(Ω):={u:∇u∈Lq(Ω)2,u≡0on∂Ω}, where 1/p+1/q=1. In fact, the norm ∥v∥Gp(Ω) is a dual norm to the Sobolev norm ∥∇u∥q. And the space G(Ω)=W-1,∞(Ω) which is the dual to the space W01,1(Ω). Moreover, if p→∞, the spaces Gp(Ω) approximate the space G(Ω). By the Sobolev imbedding theorems, we obtain that ∥v∥Gp(Ω)≤CΩ∥v∥G(Ω), where CΩ is a constant which is independent of v but Ω. So, for any 1≤p<∞, these are larger spaces than G(Ω) and allow for different choices of weaker norms for the oscillatory component v.
For instance, consider the sequence of one-dimensional functionsvn(x)=cos(nx) defined on Ω=[0,π/2]. Then, vn(x)=gn′(x), where gn(x)=(1/n)sin(nx)+c. It is easy to check that(1)
∥vn∥L2(Ω)=(∫0π/2cos2(nx)dx)1/2=(π/2)>0;(2)
∥vn∥G(Ω)=(1/n)→0 as n→∞;(3)
∥vn∥Gp(Ω)=(∫0π/2|gn(x)|pdx)1/p=((1/np)∫0π/2|sin(nx)|pdx)1/p≤(π/2)1/p(1/n)→0 as n→∞.
This simple example demonstrates that an oscillatory function has a smallG-norm as well as Gp-norm which both approach to zero as the frequency of oscillations increases, but importantly, not with a so small L2-norm. So, G-norm and Gp-norm are more suitable than L2-norm to measure textures in image decomposition. In addition, Gp-norm is weaker than G-norm. So using Gp-norm to measure oscillatory functions, we also can exactly capture the texture in the energy minimization process.
For the spaceGp(Ω), we have the following results which will be used in what follows.Proposition 7 (see [6]).
Ifv∈Gp(Ω), then there exists g∈Lp(Ω;ℝ2) with v=div(g) and g·n=0 on ∂Ω, such that ∥v∥Gp(Ω)=∥g∥Lp(Ω).Proposition 8.
Ifv∈Gp(Ω), then ∫Ωvdx=0. Indeed, ∫Ωvdx=∫Ωdiv(g)dx=∫∂Ωg·ndS=0.
ReplacingG(Ω) with Gp(Ω) (p≥1), Vese and Osher introduce the following convex minimization problem; that is, (BV,Gp,L2) decomposition:
(13)infu∈BV(Ω),v∈Gp(Ω){|u|BV(Ω)+λ∥f-u-v∥L2(Ω)2+μ∥v∥Gp(Ω)},
where λ,μ>0 are tuning parameters. The first term insures that u∈BV(Ω), the second gives us f≈u+v, while the third term is a penalty on the norm in Gp(Ω) of v. Clearly, if λ→∞ and p→∞, this model is formally an approximation of the (BV,G) model (2) originally proposed by Meyer in [15].In what follows, to simplify the notations, we always writeBV, Gp, and L2 instead of BV(Ω), Gp(Ω), and L2(Ω), respectively.


## 3. The Proposed Hierarchical Decomposition

### 3.1. Description of Hierarchical Decomposition

We firstly modify the original(BV,Gp,L2) decomposition presented in (4) to a single parameter pattern with a constraint condition ∫Ωu=∫Ωf. The new decomposition is defined as
(14)(uλ,vλ)=arg inf{∫Ωu=∫ΩfEλ(f,λ;u,v)=|u|BV+λ∥f-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωf}.
Here, the constraint condition ensures that the sum of texture v and residual (noise) r=f-u-v has zero mean. In this study, the parameter λ in (14) is viewed as a scale factor which can be used to measure the scale of the extracted cartoon, especially texture. If the λ value is too small, then only the small scale feature (coarser texture) is allocated in vλ, while most of the large scale feature (smoother texture) is swept into the residual component rλ=f-(uλ+vλ). If λ is too large, however, all the textures are extracted indiscriminately, regardless of their distinct scales.To achieve multiscale description of a textured image, we here propose a hierarchical decomposition based on (14), which enables us to effectively extract textures in different scales.For a given scaleλ, the minimizer of Eλ(f,λ;u,v) is interpreted as a decomposition, f=uλ+vλ+rλ, such that vλ captures textures in the scale λ, while the textures above λ remain unresolved in rλ. The residual rλ still consists of significant textures when viewed under a larger scale than λ, say 2λ:
(15)rλ=u2λ+v2λ+r2λ,
with
(16)(u2λ,v2λ)=arg inf{∫ΩrλEλ(rλ,2λ;u,v)=|u|BV+2λ∥rλ-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωrλ},
where v2λ captures textures in the scale 2λ, while the textures above 2λ remain unresolved in r2λ. The process of (15) can be continued to capture the missing large scale textures.The proposed hierarchical decomposition can be stated as follows:starting with an initial scaleλ=λ0,
(17)f=u0+v0+r0,
where
(18)(u0,v0)=arg inf{∫Ωu=∫ΩfEλ(f,λ0;u,v)=|u|BV+λ0∥f-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωf}.
Proceeding with successive applications of the dyadic refinement step (15), we have
(19)ri=ui+1+vi+1+ri+1,i=0,1,…,
where
(20)(ui+1,vi+1)=arg inf{∫Ωu=∫ΩriEλ(ri,λ02i+1;u,v)=|u|BV+λ02i+1∥ri-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωri}.
From (19), we obtain, after k such steps, the hierarchical decomposition of f as follows:
(21)f=u0+v0+r0=u0+u1+v0+v1+r1=⋯=u0+u1+⋯+uk+v0+v1+⋯+vk+rk.
The partial sum, ∑i=0k(ui+vi), provides a multiscale representation of f, in which ∑i=0kui lies in the intermediate scale spaces between L2 and BV, and ∑i=0kvi lies in the intermediate scale spaces between Gp and L2. Another application of this hierarchical decomposition is multiscale texture extraction. Indeed, ∑i=0kvi represents the textures in the scales ranging from λ0 to λ02k.


### 3.2. Existence of Hierarchical Decomposition

The existence of our hierarchical decomposition is directly derived from the following result, actually, which can be used for original(BV,Gp,L2) decomposition by replacing ri with f, but Vese and Osher did not give proof for it in their papers.Theorem 9.
Forri∈L2 (i=-1,0,…), the following minimization problem
(22)inf{∫ΩriEλ(ri,λ02i+1;u,v)=|u|BV+λ02i+1∥ri-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωri}
has a solution (u,v) such that u∈BV and v∈Gp.Proof.
SinceEλ(ri,λ02i+1;u,v)≥0 for all u∈BV and v∈Gp, infu∈BV,v∈GpEλ(ri,λ02i+1;u,v)<+∞. We can find a minimizing sequence {(un,vn)}n≥1∈(BV,Gp) such that 0≤Eλ(ri,λ02i+1;un,vn)≤C and ∫Ωun=∫Ωri for all n. Then, we have uniformly
(23)|un|BV≤C,∥ri-un-vn∥L2≤C,∥vn∥Gp≤C.
Here, the constant C may be changed from line to line. By the Sobolev-Poincare inequality, we have
(24)∥un-u-n∥L2≤C|un|BV,u-n=1|Ω|∫Ωun,
where |Ω| is the volume of Ω. We thus obtain ∥un-u-n∥L2≤C by (23), which implies that un is uniformly bounded in L2 since ∫Ωun=∫Ωri for all n≥1. Because Ω is bounded, un is also uniformly bounded in L1. By (23), we thus have
(25)∥un∥BV=∥un∥L1+|un|BV≤C.
By Theorem 3, there exists u∈BV and a subsequence (still denoted by un), such that un converge to u in BV-weak* topology and weakly in L2. In particular, by lower semicontinuity for the BV-weak* topology (Theorem 4), we can obtain
(26)|u|BV≤lim_n→+∞|un|BV.
Sinceun is uniformly bounded in L2, by (23) we have that vn is uniformly bounded in L2. Therefore, there exists v∈L2 such that (up to a subsequence) vn converges to v weakly in L2. By weak lower semicontinuity of L2-norm, we deduce the following property:
(27)∥ri-u-v∥L22≤lim_n→+∞∥ri-un-vn∥L22.
Forvn∈Gp, by Proposition 7, there exists gn=(g1,n,g2,n)∈(Lp)2 such that vn=div(gn)∈𝒟' (𝒟' is the distribution space) and ∥vn∥Gp=∥gn∥Lp, which implies ∥gi,n∥Lp≤C (i=1,2) due to ∥vn∥Gp≤C. Therefore, there exist g=(g1,g2)∈(Lp)2, such that, up to a subsequence, gi,n converges to gi weak* in Lp.
We next prove thatv=div(g)∈Gp. Let φ∈𝒟 (𝒟 is the test function space); then,
(28)∫Ωvnφdx=∫Ωdiv(gn)φdx=-∫Ωgn·∇φdx.
Taking n→∞ (using weak L2 topology and weak*  Lp topology), we obtain
(29)∫Ωvφdx=-∫Ωg·∇φdx=∫Ωdiv(g)φdx.
This implies v=div(g)∈𝒟′. And since v∈L2, v=div(g) a.e. Therefore, v∈Gp∩L2. By weak* lower semicontinuity, it follows that
(30)∥v∥Gp≤∥g12+g22∥Lp≤lim_n→+∞∥g1,n2+g2,n2∥Lp=lim_n→+∞∥vn∥Gp.
By (26)–(30), we have
(31)Eλ(ri,λ02i+1;u,v)≤lim_n→+∞Eλ(ri,λ02i+1;un,vn),
which implies that (u,v) is a solution for (22). The proof is completed.


### 3.3. Nontrivial Property of Hierarchical Decomposition

In this study, if the solution of (22) satisfies u≠0 or v≠0, then the decomposition f=u+v+r is called the nontrivial decomposition. If ri=ui+1+vi+1+ri+1 (r-1=f) is nontrivial for any i∈{-1,0,1,…}, then the hierarchical decomposition (21) is called the nontrivial hierarchical decomposition. Conversely, if the minimization problem (22) has only zero solution, that is, (u,v)=(0,0), then the decomposition ri=ui+1+vi+1+ri+1 of ri is trivial, which makes no sense for image decomposition. In what follows, we discuss the existence of the nontrivial hierarchical decomposition in (21).Firstly, similar to (but slightly different from) Definition 5.3 of [8], we here define a new quantity ∥·∥* to measure the L2-function, which will play a key role in our following study.Definition 10.
Letω∈L2. Then, for any h∈BV and g∈Gp∩L2, one defines
(32)∥ω∥*=suph∈BV,g∈GP∩L2|〈ω,h+g〉||h|BV+∥g∥Gp,|h|BV+∥g∥Gp≠0,
where 〈·,·〉 denote L2 inner product.
By the definition of∥·∥*, we have the following results.Proposition 11.
Letω∈L2. If ∫Ωωdx≠0, then ∥ω∥*=+∞.Proof.
For anyh∈BV, g∈Gp∩L2, and c∈ℝ, replacing h with c+h and noting that |c+h|BV=|h|BV, we have
(33)|〈ω,c+h+g〉||h+c|BV+∥g∥Gp=|c∫Ωωdx+〈ω,h+g〉||h|BV+∥g∥Gp≥|c||∫Ωωdx|-|〈ω,h+g〉||h|BV+∥g∥Gp.
By ∫Ωωdx≠0, we can deduce that
(34)|〈ω,c+h+g〉||h+c|BV+∥g∥Gp⟶+∞as|c|⟶∞.
By the definition of ||·||*, we have
(35)∥ω∥*=sup|〈ω,h+g〉||h|BV+∥g∥Gp=+∞.
By Theorem9, the minimization problem (22) must have solutions. Next, simulating hierarchical (BV,L2) decomposition proposed by Tadmor et al. [5], we show some properties for these solutions, which will be used to demonstrate the nontrivial property for our hierarchical decomposition.Lemma 12.
Letri∈L2. If the minimization problem (22) has a zero solution, then ∥ri∥*≤1/λ02i+2.Proof.
Since (22) has a zero solution, then for any h∈BV and g∈Gp, we have
(36)Eλ(ri,λ02i+1;h,g)≥Eλ(ri,λ02i+1;0,0),
and that is,
(37)|h|BV+λ02i+1∥ri-h-g∥L22+∥g∥Gp≥λ02i+1∥ri∥L22.
This inequality can be rewritten as
(38)|h|BV-λ02i+2〈ri,h+g〉+λ02i+1∥h+g∥L22+∥g∥Gp≥0.
Substituting h by εh and g by εg in (38) and taking ε→0+ and ε→0-, respectively, we obtain
(39)|〈ri,h+g〉|≤1λ02i+2(|h|BV+∥g∥Gp).
By the definition of ∥·∥*, we have ∥ri∥*≤1/λ02i+2.Lemma 13.
Letri∈L2. If ∥ri∥*>1/λ02i+2, then the solution (ui+1,vi+1) of (22) is nonzero; that is, ui+1≠0 or vi+1≠0. Furthermore, ui+1,vi+1 and ri+1=ri-ui+1-vi+1 satisfy
(40)∥ri+1∥*=1λ02i+2,〈ri+1,ui+1+vi+1〉=1λ02i+2(|ui+1|BV+∥vi+1∥Gp).Proof.
The first assertion is proved directly by Lemma12.
Because(ui+1,vi+1) is the solution of (22), for any h∈BV, g∈Gp, and ε∈ℝ, we have
(41)|ui+1+εh|BV+λ02i+1∥ri+1-ε(h+g)∥L22+∥vi+1+εg∥Gp≥|ui+1|BV+λ02i+1∥ri+1∥L22+∥vi+1∥Gp.
By the triangle inequality, we obtain
(42)|ui+1+εh|BV+λ02i+1∥ri+1-ε(h+g)∥L22+∥vi+1+εg∥Gp≤(|ui+1|BV+|ε||h|BV)+λ02i+1∥ri+1-ε(h+g)∥L22+(∥vi+1∥Gp+|ε|∥g∥Gp).
So, the inequality (41) is changed into
(43)|ε||h|BV+λ02i+1∥ri+1-ε(h+g)∥L22+|ε|∥g∥Gp≥λ02i+1∥ri+1∥L22.
Expanding the second term on left side of the last inequality, we can obtain
(44)|ε||h|BV+ε2λ02i+1∥(h+g)∥L22+|ε|∥g∥Gp≥ελ02i+2〈ri+1,h+g〉.
Dividing both sides of the last inequality by ε>0 and taking ε→0+, we obtain
(45)|h|BV+∥g∥Gp≥λ02i+2〈ri+1,h+g〉.
Dividing both sides of (44) by ε<0 and taking ε→0-, we also obtain
(46)|h|BV+∥g∥Gp≥-λ02i+2〈ri+1,h+g〉.
The inequalities (45) and (46) imply that
(47)|h|BV+∥g∥Gp≥λ02i+2|〈ri+1,h+g〉|.
By definition of ∥·∥*, we have
(48)∥ri+1∥*≤1λ02i+2.
Letε∈(-1,1). Replacing (h,g) with (ui+1,vi+1) in the inequality (41), we have
(49)|ui+1+εui+1|BV+λ02i+1∥ri+1-ε(ui+1+vi+1)∥L22+∥vi+1+εvi+1∥Gp=(1+ε)|ui+1|BV+λ02i+1∥ri+1-ε(ui+1+vi+1)∥L22+(1+ε)∥vi+1∥Gp≥|ui+1|BV+λ02i+1∥ri+1∥L22+∥vi+1∥Gp.
So,
(50)ε|ui+1|BV+ε2λ02i+1∥ui+1+vi+1∥L22+ε∥vi+1∥Gp≥ελ02i+2〈ri+1,ui+1+vi+1〉.
Dividing both sides of the last inequality by |ε| and then taking ε→0+ and ε→0-, respectively, we obtain the equality (40):
(51)λ02i+2〈ri+1,ui+1+vi+1〉=|ui+1|BV+∥vi+1∥Gp.
So,
(52)λ02i+2|〈ri+1,ui+1+vi+1〉|=|ui+1|BV+∥vi+1∥Gp,
which, due to ui+1≠0 or vi+1≠0, implies
(53)|〈ri+1,ui+1+vi+1〉||ui+1|BV+∥vi+1∥Gp=1λ02i+2.
By definition of ∥·∥* and (48), we have ∥ri+1∥*=1/λ02i+2.Theorem 14.
Letf∈L2 with ∫Ωfdx≠0, and (ui+1,vi+1) is the solution of (22). Then, for any initial scale λ0>0, the decomposition ri=ui+1+vi+1+ri+1 is nontrivial for any i∈{-1,0,1,…}. In other words, any hierarchical decomposition of f given in (21) is nontrivial.Proof.
Since∫Ωfdx≠0, we have ∥f∥*=+∞ by Proposition 11. By Lemma 13, the decomposition f=r-1=u0+v0+r0 is nontrivial, and ∥r0∥*=1/(2λ0). Because ∥r0∥*=1/(2λ0)>1/(22λ0), again by Lemma 13, the decomposition r0=u1+v1+r1 is nontrivial, and ∥r1∥*=1/(22λ0)>1/(23λ0) which means such nontrivial decomposition can continue.
For theith decomposition, by Lemma 13, we have ∥ri-1∥*=1/(λ02i)>1/(λ02i+1) which means the ith decomposition ri=ui+1+vi+1+ri+1 is nontrivial. In conclusion, any hierarchical decomposition of f given in (21) is nontrivial when ∫Ωfdx≠0.Remark 15.
By Theorems9 and 14, we can deduce that for any L2-function f with ∫Ωfdx≠0, there must be a nontrivial hierarchical decomposition. This result is much significant for image hierarchical decomposition. In general, a digital image f is a nonnegative L2-function with ∫Ωfdx≠0, so any hierarchical (BV,Gp,L2) decomposition of f must be nontrivial.


### 3.4. Convergence of Hierarchical Decomposition

For the hierarchical decomposition given in (21), we have the following convergence result (Theorem 17) in the L2 topology, which is similar to the convergence result of hierarchical (BV,L2) decomposition proposed by Tadmor, Nezzar, and Vese (see Theorem  2.2 in [5] for details). To prove Theorem 17, we need the following lemma.Lemma 16.
Ifri∈L2, then there are u^∈BV, and v^∈L2⊂Gp so that Eλ(ri,λ02i+1;u^,v^)≤C, where C is a constant independent of λ02i+1.Proof.
By [19], there exists a unique solution for ROF model (1), denoted by
(54)(u^,v^)=arg inf{J(ri;u,v)=|u|BV+∥v∥L2,ri=u+v}
such that u^∈BV, v^∈L2⊂Gp. Therefore, we can deduce that
(55)Eλ(ri,λ02i+1;u^,v^)=|u^|BV+2i+1λ0∥ri-u^-v^∥L22+∥v^∥Gp=|u^|BV+∥v^∥Gp≤|u^|BV+C1∥v^∥L2=C,
where C clearly does not depend on λ02i+1.Theorem 17.
Letf∈L2. Then, the hierarchical decomposition given in (21) satisfies
(56)∥f-∑i=-1k(ui+1+vi+1)∥L2=∥rk+1∥L2⟶0,ask⟶∞.
In addition, the following “energy” estimate holds:
(57)∑i=-1∞1λ02i+1(|ui+1|BV+∥vi+1∥Gp)+∑i=-1∞(∥ui+1+vi+1∥L22)=∥f∥L22.Proof.
By Lemma16, there exist u^∈BV and v^∈Gp, such that Eλ(ri,λ02i+1;u^,v^)≤C, where C does not depend on λ02i+1. Since (ui+1,vi+1) is a solution of (22), we have
(58)Eλ(ri,λ02i+1;ui+1,vi+1)≤Eλ(ri,λ02i+1;u^,v^)≤C.
Thus,
(59)λ02i+1∥ri-ui+1-vi+1∥L22≤Eλ(ri,λ02i+1;ui+1,vi+1)≤C,
which, by ri+1=ri-ui+1-vi+1, implies
(60)∥ri+1∥L22≤Cλ02i+1,i=-1,0,1,….
By rk+1=f-∑i=-1k(ui+1+vi+1), we have
(61)∥f-∑i=-1k(ui+1+vi+1)∥L22=∥rk+1∥L22≤Cλ02k+1,k=-1,0,1,….
Therefore, ∥f-∑i=-1k(ui+1+vi+1)∥L2→0 as k→∞. The proof of the first assertion is completed.Next, we prove the second assertion that is, (57). Since ri=ri+1+(ui+1+vi+1), we obtain
(62)∥ri∥L22=∥ri+1∥L22+∥ui+1+vi+1∥L22+2〈ri+1,ui+1+vi+1〉.
By (40), (62) can be rewritten as
(63)∥ri∥L22-∥ri+1∥L22-∥ui+1+vi+1∥L22=2〈ri+1,ui+1+vi+1〉=1λ02i+1(|ui+1|BV+∥vi+1∥Gp).
Since
(64)∑i=-1k(∥ri∥L22-∥ri+1∥L22-∥ui+1+vi+1∥L22)=∑i=-1k(∥ri∥L22-∥ri+1∥L22)-∑i=-1k(∥ui+1+vi+1∥L22)=∥r-1∥L22-∥rk+1∥L22-∑i=-1k(∥ui+1+vi+1∥L22)=∥f∥L22-∥rk+1∥L22-∑i=-1k(∥ui+1+vi+1∥L22),
summing up both sides of (63), we obtain
(65)∑i=-1k1λ02i+1(|ui+1|BV+∥vi+1∥Gp)+∑i=-1k(∥ui+1+vi+1∥L22)=∥f∥L22-∥rk+1∥L22.
By limk→∞∥rk+1∥L2→0, we have
(66)∑i=-1∞1λ02i+1(|ui+1|BV+∥vi+1∥Gp)+∑i=-1∞(∥ui+1+vi+1∥L22)=∥f∥L22.Equation (57) can be seen as the L2-energy decomposition of f in our hierarchical decomposition. In addition, the multiscale nature of our hierarchical extraction can be quantified in terms of this energy decomposition.


## 3.1. Description of Hierarchical Decomposition

We firstly modify the original(BV,Gp,L2) decomposition presented in (4) to a single parameter pattern with a constraint condition ∫Ωu=∫Ωf. The new decomposition is defined as
(14)(uλ,vλ)=arg inf{∫Ωu=∫ΩfEλ(f,λ;u,v)=|u|BV+λ∥f-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωf}.
Here, the constraint condition ensures that the sum of texture v and residual (noise) r=f-u-v has zero mean. In this study, the parameter λ in (14) is viewed as a scale factor which can be used to measure the scale of the extracted cartoon, especially texture. If the λ value is too small, then only the small scale feature (coarser texture) is allocated in vλ, while most of the large scale feature (smoother texture) is swept into the residual component rλ=f-(uλ+vλ). If λ is too large, however, all the textures are extracted indiscriminately, regardless of their distinct scales.To achieve multiscale description of a textured image, we here propose a hierarchical decomposition based on (14), which enables us to effectively extract textures in different scales.For a given scaleλ, the minimizer of Eλ(f,λ;u,v) is interpreted as a decomposition, f=uλ+vλ+rλ, such that vλ captures textures in the scale λ, while the textures above λ remain unresolved in rλ. The residual rλ still consists of significant textures when viewed under a larger scale than λ, say 2λ:
(15)rλ=u2λ+v2λ+r2λ,
with
(16)(u2λ,v2λ)=arg inf{∫ΩrλEλ(rλ,2λ;u,v)=|u|BV+2λ∥rλ-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωrλ},
where v2λ captures textures in the scale 2λ, while the textures above 2λ remain unresolved in r2λ. The process of (15) can be continued to capture the missing large scale textures.The proposed hierarchical decomposition can be stated as follows:starting with an initial scaleλ=λ0,
(17)f=u0+v0+r0,
where
(18)(u0,v0)=arg inf{∫Ωu=∫ΩfEλ(f,λ0;u,v)=|u|BV+λ0∥f-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωf}.
Proceeding with successive applications of the dyadic refinement step (15), we have
(19)ri=ui+1+vi+1+ri+1,i=0,1,…,
where
(20)(ui+1,vi+1)=arg inf{∫Ωu=∫ΩriEλ(ri,λ02i+1;u,v)=|u|BV+λ02i+1∥ri-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωri}.
From (19), we obtain, after k such steps, the hierarchical decomposition of f as follows:
(21)f=u0+v0+r0=u0+u1+v0+v1+r1=⋯=u0+u1+⋯+uk+v0+v1+⋯+vk+rk.
The partial sum, ∑i=0k(ui+vi), provides a multiscale representation of f, in which ∑i=0kui lies in the intermediate scale spaces between L2 and BV, and ∑i=0kvi lies in the intermediate scale spaces between Gp and L2. Another application of this hierarchical decomposition is multiscale texture extraction. Indeed, ∑i=0kvi represents the textures in the scales ranging from λ0 to λ02k.


## 3.2. Existence of Hierarchical Decomposition

The existence of our hierarchical decomposition is directly derived from the following result, actually, which can be used for original(BV,Gp,L2) decomposition by replacing ri with f, but Vese and Osher did not give proof for it in their papers.Theorem 9.
Forri∈L2 (i=-1,0,…), the following minimization problem
(22)inf{∫ΩriEλ(ri,λ02i+1;u,v)=|u|BV+λ02i+1∥ri-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωri}
has a solution (u,v) such that u∈BV and v∈Gp.Proof.
SinceEλ(ri,λ02i+1;u,v)≥0 for all u∈BV and v∈Gp, infu∈BV,v∈GpEλ(ri,λ02i+1;u,v)<+∞. We can find a minimizing sequence {(un,vn)}n≥1∈(BV,Gp) such that 0≤Eλ(ri,λ02i+1;un,vn)≤C and ∫Ωun=∫Ωri for all n. Then, we have uniformly
(23)|un|BV≤C,∥ri-un-vn∥L2≤C,∥vn∥Gp≤C.
Here, the constant C may be changed from line to line. By the Sobolev-Poincare inequality, we have
(24)∥un-u-n∥L2≤C|un|BV,u-n=1|Ω|∫Ωun,
where |Ω| is the volume of Ω. We thus obtain ∥un-u-n∥L2≤C by (23), which implies that un is uniformly bounded in L2 since ∫Ωun=∫Ωri for all n≥1. Because Ω is bounded, un is also uniformly bounded in L1. By (23), we thus have
(25)∥un∥BV=∥un∥L1+|un|BV≤C.
By Theorem 3, there exists u∈BV and a subsequence (still denoted by un), such that un converge to u in BV-weak* topology and weakly in L2. In particular, by lower semicontinuity for the BV-weak* topology (Theorem 4), we can obtain
(26)|u|BV≤lim_n→+∞|un|BV.
Sinceun is uniformly bounded in L2, by (23) we have that vn is uniformly bounded in L2. Therefore, there exists v∈L2 such that (up to a subsequence) vn converges to v weakly in L2. By weak lower semicontinuity of L2-norm, we deduce the following property:
(27)∥ri-u-v∥L22≤lim_n→+∞∥ri-un-vn∥L22.
Forvn∈Gp, by Proposition 7, there exists gn=(g1,n,g2,n)∈(Lp)2 such that vn=div(gn)∈𝒟' (𝒟' is the distribution space) and ∥vn∥Gp=∥gn∥Lp, which implies ∥gi,n∥Lp≤C (i=1,2) due to ∥vn∥Gp≤C. Therefore, there exist g=(g1,g2)∈(Lp)2, such that, up to a subsequence, gi,n converges to gi weak* in Lp.
We next prove thatv=div(g)∈Gp. Let φ∈𝒟 (𝒟 is the test function space); then,
(28)∫Ωvnφdx=∫Ωdiv(gn)φdx=-∫Ωgn·∇φdx.
Taking n→∞ (using weak L2 topology and weak*  Lp topology), we obtain
(29)∫Ωvφdx=-∫Ωg·∇φdx=∫Ωdiv(g)φdx.
This implies v=div(g)∈𝒟′. And since v∈L2, v=div(g) a.e. Therefore, v∈Gp∩L2. By weak* lower semicontinuity, it follows that
(30)∥v∥Gp≤∥g12+g22∥Lp≤lim_n→+∞∥g1,n2+g2,n2∥Lp=lim_n→+∞∥vn∥Gp.
By (26)–(30), we have
(31)Eλ(ri,λ02i+1;u,v)≤lim_n→+∞Eλ(ri,λ02i+1;un,vn),
which implies that (u,v) is a solution for (22). The proof is completed.


## 3.3. Nontrivial Property of Hierarchical Decomposition

In this study, if the solution of (22) satisfies u≠0 or v≠0, then the decomposition f=u+v+r is called the nontrivial decomposition. If ri=ui+1+vi+1+ri+1 (r-1=f) is nontrivial for any i∈{-1,0,1,…}, then the hierarchical decomposition (21) is called the nontrivial hierarchical decomposition. Conversely, if the minimization problem (22) has only zero solution, that is, (u,v)=(0,0), then the decomposition ri=ui+1+vi+1+ri+1 of ri is trivial, which makes no sense for image decomposition. In what follows, we discuss the existence of the nontrivial hierarchical decomposition in (21).Firstly, similar to (but slightly different from) Definition 5.3 of [8], we here define a new quantity ∥·∥* to measure the L2-function, which will play a key role in our following study.Definition 10.
Letω∈L2. Then, for any h∈BV and g∈Gp∩L2, one defines
(32)∥ω∥*=suph∈BV,g∈GP∩L2|〈ω,h+g〉||h|BV+∥g∥Gp,|h|BV+∥g∥Gp≠0,
where 〈·,·〉 denote L2 inner product.
By the definition of∥·∥*, we have the following results.Proposition 11.
Letω∈L2. If ∫Ωωdx≠0, then ∥ω∥*=+∞.Proof.
For anyh∈BV, g∈Gp∩L2, and c∈ℝ, replacing h with c+h and noting that |c+h|BV=|h|BV, we have
(33)|〈ω,c+h+g〉||h+c|BV+∥g∥Gp=|c∫Ωωdx+〈ω,h+g〉||h|BV+∥g∥Gp≥|c||∫Ωωdx|-|〈ω,h+g〉||h|BV+∥g∥Gp.
By ∫Ωωdx≠0, we can deduce that
(34)|〈ω,c+h+g〉||h+c|BV+∥g∥Gp⟶+∞as|c|⟶∞.
By the definition of ||·||*, we have
(35)∥ω∥*=sup|〈ω,h+g〉||h|BV+∥g∥Gp=+∞.
By Theorem9, the minimization problem (22) must have solutions. Next, simulating hierarchical (BV,L2) decomposition proposed by Tadmor et al. [5], we show some properties for these solutions, which will be used to demonstrate the nontrivial property for our hierarchical decomposition.Lemma 12.
Letri∈L2. If the minimization problem (22) has a zero solution, then ∥ri∥*≤1/λ02i+2.Proof.
Since (22) has a zero solution, then for any h∈BV and g∈Gp, we have
(36)Eλ(ri,λ02i+1;h,g)≥Eλ(ri,λ02i+1;0,0),
and that is,
(37)|h|BV+λ02i+1∥ri-h-g∥L22+∥g∥Gp≥λ02i+1∥ri∥L22.
This inequality can be rewritten as
(38)|h|BV-λ02i+2〈ri,h+g〉+λ02i+1∥h+g∥L22+∥g∥Gp≥0.
Substituting h by εh and g by εg in (38) and taking ε→0+ and ε→0-, respectively, we obtain
(39)|〈ri,h+g〉|≤1λ02i+2(|h|BV+∥g∥Gp).
By the definition of ∥·∥*, we have ∥ri∥*≤1/λ02i+2.Lemma 13.
Letri∈L2. If ∥ri∥*>1/λ02i+2, then the solution (ui+1,vi+1) of (22) is nonzero; that is, ui+1≠0 or vi+1≠0. Furthermore, ui+1,vi+1 and ri+1=ri-ui+1-vi+1 satisfy
(40)∥ri+1∥*=1λ02i+2,〈ri+1,ui+1+vi+1〉=1λ02i+2(|ui+1|BV+∥vi+1∥Gp).Proof.
The first assertion is proved directly by Lemma12.
Because(ui+1,vi+1) is the solution of (22), for any h∈BV, g∈Gp, and ε∈ℝ, we have
(41)|ui+1+εh|BV+λ02i+1∥ri+1-ε(h+g)∥L22+∥vi+1+εg∥Gp≥|ui+1|BV+λ02i+1∥ri+1∥L22+∥vi+1∥Gp.
By the triangle inequality, we obtain
(42)|ui+1+εh|BV+λ02i+1∥ri+1-ε(h+g)∥L22+∥vi+1+εg∥Gp≤(|ui+1|BV+|ε||h|BV)+λ02i+1∥ri+1-ε(h+g)∥L22+(∥vi+1∥Gp+|ε|∥g∥Gp).
So, the inequality (41) is changed into
(43)|ε||h|BV+λ02i+1∥ri+1-ε(h+g)∥L22+|ε|∥g∥Gp≥λ02i+1∥ri+1∥L22.
Expanding the second term on left side of the last inequality, we can obtain
(44)|ε||h|BV+ε2λ02i+1∥(h+g)∥L22+|ε|∥g∥Gp≥ελ02i+2〈ri+1,h+g〉.
Dividing both sides of the last inequality by ε>0 and taking ε→0+, we obtain
(45)|h|BV+∥g∥Gp≥λ02i+2〈ri+1,h+g〉.
Dividing both sides of (44) by ε<0 and taking ε→0-, we also obtain
(46)|h|BV+∥g∥Gp≥-λ02i+2〈ri+1,h+g〉.
The inequalities (45) and (46) imply that
(47)|h|BV+∥g∥Gp≥λ02i+2|〈ri+1,h+g〉|.
By definition of ∥·∥*, we have
(48)∥ri+1∥*≤1λ02i+2.
Letε∈(-1,1). Replacing (h,g) with (ui+1,vi+1) in the inequality (41), we have
(49)|ui+1+εui+1|BV+λ02i+1∥ri+1-ε(ui+1+vi+1)∥L22+∥vi+1+εvi+1∥Gp=(1+ε)|ui+1|BV+λ02i+1∥ri+1-ε(ui+1+vi+1)∥L22+(1+ε)∥vi+1∥Gp≥|ui+1|BV+λ02i+1∥ri+1∥L22+∥vi+1∥Gp.
So,
(50)ε|ui+1|BV+ε2λ02i+1∥ui+1+vi+1∥L22+ε∥vi+1∥Gp≥ελ02i+2〈ri+1,ui+1+vi+1〉.
Dividing both sides of the last inequality by |ε| and then taking ε→0+ and ε→0-, respectively, we obtain the equality (40):
(51)λ02i+2〈ri+1,ui+1+vi+1〉=|ui+1|BV+∥vi+1∥Gp.
So,
(52)λ02i+2|〈ri+1,ui+1+vi+1〉|=|ui+1|BV+∥vi+1∥Gp,
which, due to ui+1≠0 or vi+1≠0, implies
(53)|〈ri+1,ui+1+vi+1〉||ui+1|BV+∥vi+1∥Gp=1λ02i+2.
By definition of ∥·∥* and (48), we have ∥ri+1∥*=1/λ02i+2.Theorem 14.
Letf∈L2 with ∫Ωfdx≠0, and (ui+1,vi+1) is the solution of (22). Then, for any initial scale λ0>0, the decomposition ri=ui+1+vi+1+ri+1 is nontrivial for any i∈{-1,0,1,…}. In other words, any hierarchical decomposition of f given in (21) is nontrivial.Proof.
Since∫Ωfdx≠0, we have ∥f∥*=+∞ by Proposition 11. By Lemma 13, the decomposition f=r-1=u0+v0+r0 is nontrivial, and ∥r0∥*=1/(2λ0). Because ∥r0∥*=1/(2λ0)>1/(22λ0), again by Lemma 13, the decomposition r0=u1+v1+r1 is nontrivial, and ∥r1∥*=1/(22λ0)>1/(23λ0) which means such nontrivial decomposition can continue.
For theith decomposition, by Lemma 13, we have ∥ri-1∥*=1/(λ02i)>1/(λ02i+1) which means the ith decomposition ri=ui+1+vi+1+ri+1 is nontrivial. In conclusion, any hierarchical decomposition of f given in (21) is nontrivial when ∫Ωfdx≠0.Remark 15.
By Theorems9 and 14, we can deduce that for any L2-function f with ∫Ωfdx≠0, there must be a nontrivial hierarchical decomposition. This result is much significant for image hierarchical decomposition. In general, a digital image f is a nonnegative L2-function with ∫Ωfdx≠0, so any hierarchical (BV,Gp,L2) decomposition of f must be nontrivial.


## 3.4. Convergence of Hierarchical Decomposition

For the hierarchical decomposition given in (21), we have the following convergence result (Theorem 17) in the L2 topology, which is similar to the convergence result of hierarchical (BV,L2) decomposition proposed by Tadmor, Nezzar, and Vese (see Theorem  2.2 in [5] for details). To prove Theorem 17, we need the following lemma.Lemma 16.
Ifri∈L2, then there are u^∈BV, and v^∈L2⊂Gp so that Eλ(ri,λ02i+1;u^,v^)≤C, where C is a constant independent of λ02i+1.Proof.
By [19], there exists a unique solution for ROF model (1), denoted by
(54)(u^,v^)=arg inf{J(ri;u,v)=|u|BV+∥v∥L2,ri=u+v}
such that u^∈BV, v^∈L2⊂Gp. Therefore, we can deduce that
(55)Eλ(ri,λ02i+1;u^,v^)=|u^|BV+2i+1λ0∥ri-u^-v^∥L22+∥v^∥Gp=|u^|BV+∥v^∥Gp≤|u^|BV+C1∥v^∥L2=C,
where C clearly does not depend on λ02i+1.Theorem 17.
Letf∈L2. Then, the hierarchical decomposition given in (21) satisfies
(56)∥f-∑i=-1k(ui+1+vi+1)∥L2=∥rk+1∥L2⟶0,ask⟶∞.
In addition, the following “energy” estimate holds:
(57)∑i=-1∞1λ02i+1(|ui+1|BV+∥vi+1∥Gp)+∑i=-1∞(∥ui+1+vi+1∥L22)=∥f∥L22.Proof.
By Lemma16, there exist u^∈BV and v^∈Gp, such that Eλ(ri,λ02i+1;u^,v^)≤C, where C does not depend on λ02i+1. Since (ui+1,vi+1) is a solution of (22), we have
(58)Eλ(ri,λ02i+1;ui+1,vi+1)≤Eλ(ri,λ02i+1;u^,v^)≤C.
Thus,
(59)λ02i+1∥ri-ui+1-vi+1∥L22≤Eλ(ri,λ02i+1;ui+1,vi+1)≤C,
which, by ri+1=ri-ui+1-vi+1, implies
(60)∥ri+1∥L22≤Cλ02i+1,i=-1,0,1,….
By rk+1=f-∑i=-1k(ui+1+vi+1), we have
(61)∥f-∑i=-1k(ui+1+vi+1)∥L22=∥rk+1∥L22≤Cλ02k+1,k=-1,0,1,….
Therefore, ∥f-∑i=-1k(ui+1+vi+1)∥L2→0 as k→∞. The proof of the first assertion is completed.Next, we prove the second assertion that is, (57). Since ri=ri+1+(ui+1+vi+1), we obtain
(62)∥ri∥L22=∥ri+1∥L22+∥ui+1+vi+1∥L22+2〈ri+1,ui+1+vi+1〉.
By (40), (62) can be rewritten as
(63)∥ri∥L22-∥ri+1∥L22-∥ui+1+vi+1∥L22=2〈ri+1,ui+1+vi+1〉=1λ02i+1(|ui+1|BV+∥vi+1∥Gp).
Since
(64)∑i=-1k(∥ri∥L22-∥ri+1∥L22-∥ui+1+vi+1∥L22)=∑i=-1k(∥ri∥L22-∥ri+1∥L22)-∑i=-1k(∥ui+1+vi+1∥L22)=∥r-1∥L22-∥rk+1∥L22-∑i=-1k(∥ui+1+vi+1∥L22)=∥f∥L22-∥rk+1∥L22-∑i=-1k(∥ui+1+vi+1∥L22),
summing up both sides of (63), we obtain
(65)∑i=-1k1λ02i+1(|ui+1|BV+∥vi+1∥Gp)+∑i=-1k(∥ui+1+vi+1∥L22)=∥f∥L22-∥rk+1∥L22.
By limk→∞∥rk+1∥L2→0, we have
(66)∑i=-1∞1λ02i+1(|ui+1|BV+∥vi+1∥Gp)+∑i=-1∞(∥ui+1+vi+1∥L22)=∥f∥L22.Equation (57) can be seen as the L2-energy decomposition of f in our hierarchical decomposition. In addition, the multiscale nature of our hierarchical extraction can be quantified in terms of this energy decomposition.


## 4. Numerical Implementation

In this section, we present the details of numerical implementation for our hierarchical(BV,Gp,L2) decomposition:
(67)(uk+1,vk+1)=arg inf{∫Ωrk|u|BV+λ02k+1∥rk-u-v∥L22+∥v∥Gp,∫Ωu=∫Ωrk},k=-1,0,1,….Takingv=div(g)=div(g1,g2), we obtain the following equivalent formulation of (67) in terms of u, g1, and g2:
(68)(uk+1,[g1]k+1,[g2]k+1)=arg inf{∫Ωu|u|BV+λ02k+1∥rk-u-div(g)∥L22+∥g∥Lp,∫Ωu=∫Ωrk},
where gk+1=([g1]k+1,[g2]k+1).Minimizing the energy in (68) with respect to u, g1 and g2 yields the following Euler-Lagrange equations:
(69)-div(∇u|∇u|)-λ02k+2(rk-u-∂∂xg1-∂∂yg2)=0,(70)λ02k+2∂∂x(rk-u-∂∂xg1-∂∂yg2)+(∥g12+g22∥Lp)1-p(g12+g22)p-2g1=0,(71)λ02k+2∂∂y(rk-u-∂∂xg1-∂∂yg2)+(∥g12+g22∥Lp)1-p(g12+g22)p-2g2=0.
If the exterior normal to the boundary ∂Ω is denoted by (nx,ny), then the associated boundary conditions for u, g1, and g2 are
(72)∇u·(nx,ny)=0,(73)(rk-u-∂∂xg1-∂∂yg2)nx=0,(74)(rk-u-∂∂xg1-∂∂yg2)ny=0.Equation (69) with boundary condition (72) implies that ∫Ωu=∫Ωrk holds. Indeed, by taking the integral for each side of (69) and using the Gaussian formula, we obtain
(75)∫Ω(rk-u-div(g))=0.
Since v=div(g)∈Gp, by Proposition 8, we have ∫Ωdiv(g)=0. Therefore, ∫Ωu=∫Ωrk.We solve (69)–(71) by the alternating algorithm. For each equation, we adopt gradient decent method. To simplify the presentation, we introduce the notation
(76)H(g1,g2)=(∥g12+g22∥Lp)1-p(g12+g22)p-2.The details are as follows:(i)
fixed(g1,g2), find the solution u of
(77)∂u∂t=div(∇u|∇u|)+λ02k+2(rk-u-∂∂xg1-∂∂yg2)
with the initial condition u(x,y,0)=rk(x,y),(ii)
fixedu, find the solution g1,g2 of
(78)∂g1∂t=-λ02k+2∂∂x(rk-u-∂∂xg1-∂∂yg2)-H(g1,g2)g1,∂g2∂t=-λ02k+2∂∂y(rk-u-∂∂xg1-∂∂yg2)-H(g1,g2)g2,
with the initial conditions g10=-((1/(λ02k+2))(rk,x/|∇rk|)), g20=-((1/(λ02k+2))(rk,y/|∇rk|)), respectively.We use a simple explicit finite difference scheme to solve (77)-(78). The image domain Ω is discretized by the space steps Δx and Δy. Then, the grid is defined as
(79)(x,y)=(xi,yj)=(iΔx,jΔy),i=0,1,2,…,m,j=0,1,2,…,n.
We denote the time step by Δt, and tn=nΔt (n=0,1,2,…). Let ui,jn be the value of u(x,y,t) at the grid (xi,yj,tn). In order to compute the right hand side of (77)-(78), we denote
(80)Δ+xui,jn=ui+1,jn-ui,jnΔx,Δ-xui,jn=ui,jn-ui-1,jnΔx,Δ+yui,jn=ui,j+1n-ui,jnΔy,Δ-yui,jn=ui,jn-ui,j-1nΔy,Δ0xui,jn=(Δ+x+Δ-x)ui,jn2,Δ0yui,jn=(Δ+y+Δ-y)ui,jn2.
Then, (77)-(78) can be approximated by the following discretizations (to remove the singularity when |∇u|=0 and g12+g22=0, we introduce a regularity parameter ε2):
(81)ui,jn+1=ui,jn+Δt[([rk]i,j-ui,jn-Δ0x[g1]i,jn-Δ0y[g2]i,jn)Ki,jn+λ02k+2×([rk]i,j-ui,jn-Δ0x[g1]i,jn-Δ0y[g2]i,jn)],
with the initial condition
(82)ui,j0=[rk]i,j,
where Ki,jn is the curvature of the level set of u at the grid (xi,yj,nΔt), defined by
(83)Ki,jn=Δ+x(Δ-xui,jn(Δ-xui,jn)2+(Δ-xui,jn)2+ε2)+Δ+y(Δ-yui,jn(Δ-xui,jn)2+(Δ-xui,jn)2+ε2),[g1]i,jn+1=[g1]i,jn-Δt[λ02k+2Δ0x(Δ0y[g2]i,jn[rk]i,j-ui,jn-Δ0x[g1]i,jn-Δ0y[g2]i,jn)+Hi,jn[g1]i,jn],[g2]i,jn+1=[g2]i,jn-Δt[Δ0y[g2]i,jn)λ02k+2Δ0y(Δ0y[g2]i,jn[rk]i,j-ui,jn-Δ0x[g1]i,jn-Δ0y[g2]i,jn)+Hi,jn[g2]i,jn],
with the initial condition
(84)[g1]i,j0=-1λ02k+2Δ0x[rk]i,j(Δ0x[rk]i,j)2+(Δ0x[rk]i,j)2+ε2,[g2]i,j0=-1λ02k+2Δ0y[rk]i,j(Δ0x[rk]i,j)2+(Δ0x[rk]i,j)2+ε2,
where Hi,jn=H([g1]i,jn,[g2]i,jn).


## 5. Numerical Results

We present four numerical examples in this section to demonstrate the efficiency of multiscale texture extraction and image representation using the proposed hierarchical(BV,Gp,L2) decomposition for textured images. Test images, shown in Figure 1, are two synthetic images and two real images. In all experiments, we take the time step Δt=0.05, the space step Δx=Δy=1, the initial scale λ0=0.005, and the regular parameter ε2=10-9.Test images. Left to right: (a) and (b) two synthetic textured images; (c) fingerprint image; (d) a portion of noisy Barbana image which generated by adding Gaussian noise with standard deviation 20 to the clean data.
(a)
(b)
(c)
(d)For the choice ofp, by the theoretical analysis in Section 2, we have that Gp-norms are weaker than G-norm for any 1≤p<∞. So, any choice of p with 1≤p<∞ is suitable. Here, similar to what was done by Vese and Osher in [6, 14], we tested the model (68) with different values of p; our observation is that results are very similar, while the case of p=1 yields faster calculations per iteration. Thus, we set p=1 in the following. We note in passing that some different approaches based on duality principle have been proposed, such as [21, 22], to solve (67) with p=∞. We here adopt the method introduced by Vese and Osher because this study is following their work in [6, 14].(i) Image hierarchical(BV,Gp,L2) decomposition: Figure 2 shows the hierarchical decomposition results for a synthetic textured image for 7 steps. The first column shows the cartoon components of the initial image in different scales. We can see that these cartoon components are very little different visually. This phenomenon is compatible with the theory of causality of scale space. The second column shows the “textures+100” (plus a constant for illustration purposes) of the image in different scales. It is clear that the textures can be gently extracted by increasing the value of scale parameter λ02i+1, because this image involves the textures of different scales: coarser textures correspond to the smaller scales, while smoother textures correspond to the larger scales. The third column shows “residuals+100,” from which we can clearly see that some textures and edges are swept into these residual components when the value of scale parameter λ02i+1 is smaller, and then, they are gradually swept out and absorbed by ui and vi by increasing the value of the scale parameter λ02i+1. Figure 3 shows the plots of the BV-energy of ui, Gp-energy of vi, and L2-energy of ri, respectively.Figure 2
Hierarchical decomposition of a synthetic image for 7 steps.Energy plots of three components. (a) TheBV-energy of ui. (b) The Gp-energy of vi. (c) The L2-energy of ri.
(a)
(b)
(c)(ii) Multiscale texture extraction: Figure4 shows the results of multiscale texture extraction using hierarchical decomposition for another synthetic textured image for 9 steps. The first two images show the initial and final cartoon components which have little visual difference; this phenomenon is identical with the results of the first experiment. The next nine images show the texture components in different scales, which can be used as the results of multiscale texture extraction for this synthetic textured image. We remark that the larger scale textures are gradually resolved from the residual in terms of the increasing scale.Figure 4
Multiscale texture extraction using hierarchical decomposition of a synthetic image for 9 steps.(iii) Multiscale texture extraction and image representation: Figure5 shows the results of multiscale texture extraction and image representation using hierarchical decomposition of a fingerprint for 6 steps. The second column of this figure shows the extracted texture in different scales. The ∑i=0k(ui+vi)s are shown in the last column of this figure, which can be used as a multiscale representation of the original image. We can clearly see that, from top to bottom of this column, an additional amount of blurred texture is resolved in terms of the refined scaling for edges.Figure 5
Multiscale texture extraction and image representation using hierarchical decomposition of a fingerprint for 6 steps.(iv) Multiscale image representation for noisy textured image: Figure6 shows the hierarchical decomposition results of a noisy Barbana for 6 steps. The last column of this figure shows ∑i=0k(ui+vi)s which can be seen as restored images in different scales. Clearly, when the value of k is smaller, such as k=0,1, there are a few textures and noises in the restored images, much of which is swept into residual components. When k=2,3, some textures of the image are recovered on the headscarf of Barbana while removing the smaller scale noises from the entire image. If we continue the decomposition into smaller scales, then noise will reappear in the ∑i=0k(ui+vi) components, since the refined scales reach the same scales of the noise itself. From the last column of this figure, we can obtain restored image from noisy Barbana in different scales according to our requirements.Figure 6
Multiscale image representation using hierarchical decomposition of a noisy Barbana for 6 steps.


## 6. Conclusions

In this paper, in order to achieve multiscale image representation and texture extraction for textured image, we presented a hierarchical(BV,Gp,L2) decomposition model which combines the idea of hierarchical decomposition introduced by Tadmor et al. with the (BV,Gp,L2) decomposition proposed by Vese et al. In addition, we proved the existence and the convergence of the hierarchical decomposition, and the nontrivial property of this decomposition is also discussed. But the uniqueness of this hierarchical decomposition has not been proved in this paper. The authors will be concerned about this problem in the successive research.



---

*Source: 107120-2013-09-05.xml*