Signal Processing: Image Communication 28 (2013) 753–762

Contents lists available at SciVerse ScienceDirect

Signal Processing: Image Communication
journal homepage: www.elsevier.com/locate/image

An efficient framework for image/video inpainting
Miaohui Wang a,n, Bo Yan b, King Ngi Ngan aab

Department of Electronic Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong
School of Computer Science, Fudan University, Shanghai, Chinaa r t i c l e i n f oabstract

Article history:
Received 11 September 2012
Received in revised form
29 January 2013
Accepted 11 March 2013
Available online 8 April 2013

Image inpainting has been widely applied to many applications, such as restoringcorrupted old photos, erasing video logos, concealing errors in a digital video processing
system, and so on. However, traditional geometric inpainting methods suffer low
efficiency. To tackle this problem, this paper addresses an efficient transform based
framework for geometric methods. Given an image, we firstly decompose it, thenseparately perform restoration process and finally employ Laplacian diffusion function
to hold local texture coherence. Experimental results show that the proposed method not
only speeds up and enhances the performances of geometric methods, but also obtains abetter restoration results compared with the traditional texture and hybrid methods.
& 2013 Elsevier B.V. All rights reserved.

Keywords:
Image inpainting
Image interpolation
Image restoration
PDE
Diffusion function

1. Introduction
Digital image inpainting, also called image interpolation[1–3], image completion [4–6] or image restoration [7,8],
aims at removing corrupted areas but avoiding being
noticed obviously by observers, which is proposed by
Bertalmio et al. [9–11]. Image inpainting is commonlyused to remove video logos [12,13], restore occlusion invideo sequences [14–16], edit digital photos [17–19] andcompress images [20–22]. In the past decade, many
inpainting methods have been widely developed by mathematicians or computer scientists. Generally speaking,inpainting methods fall into two categories: geometricmethods (non-texture) and texture based methods.
Geometric methods restore the damaged image bydiffusing boundary information to the missing area along
the isophote lines (level lines). In [23,24], Masnou et al.
restored the occlusion area along level lines. Chan et al.
[25–27] developed a total variational (TV) model to restorenCorresponding author. Tel.: +852 5495 7535.
E-mail addresses: mhwang@ee.cuhk.edu.hk (M. Wang),
byan@fudan.edu.cn (B. Yan), knngan@ee.cuhk.edu.hk (K. Ngi Ngan).
0923-5965/$ - see front matter & 2013 Elsevier B.V. All rights reserved.
http://dx.doi.org/10.1016/j.image.2013.03.002

the missing parts and later proposed a curvature driven
diffusion scheme [28] by considering Euler's Elastica. By
contrast, some methods [9,29–31] directly employed partial
differential equations (PDE) to restore natural image geometric structures. For instance, Bertalmio et al. [9] adopted
Laplace formula, and [29] adopted Navier–Stokes formula.
Geometric methods restore the damaged areas from theboundary to center which indicate that only boundary pixels
can be used. The constraints of geometric methods are:(1) smooth restoration results, (2) poor performance at the
thick area, and (3) extensive computational time.
Texture based methods begin with exploring the selfcoherence features and then copy the best texture patch
from restoration dictionary to the missing area. Criminisi
et al. [32] proposed exemplar based method to restore themissing parts by the best patch. Exemplar based methods
employed texture synthesis [33] to integrate the patchwith the boundaries. In order to obtain the best patch,sparse representation methods [34–38] were proposed
to utilize linear combination of blocks from an image
dictionary to produce the patch. Under the assumptionof containing repetitive textures, exemplar based methods
may create abnormal structures that are hard to understand, because one order greedy approach is used in754

M. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762

restoration and the filling orders greatly bear the restoring
results when the missing area is thick. Based on spatialtemporal consistency, Wexler et al. [16] combined geometric and exemplar method to find the best patch.
Bugeau [39] proposed a complex energy function tocombine PDE and exemplar based texture synthesis
together, where they stated that the hybrid energy function works poor when missing area is thick or on a
singular location.
Besides the above two main categories, there are someother ponderable methods. For example, in [40], Teleaet al. proposed a fast marching method to restore thedamaged image; In [41], Sun et al. proposed an interesting
method combining user and synthesis technique together
to restore isolated parts. In [42], Bornemann et al. proposed a fast hybrid variational based model. Some methods [8,43] restored the given image in wavelet domain.
However there are many constraints on restoration inwavelet domain: (1) boundary pixels of corrupted area
bring new errors due to subtraction operations in producing subbands; (2) the correlations among pixels havebeen greatly changed.
In this paper, we propose an efficient hybrid inpainting
method for geometric methods. To avoid constraints ofgeometric methods, the proposed transform based framework restores the given image in the new domain. The
proposed framework, to the best of our knowledge, isnovel and the performance is impressive. Experimental
results show that it not only greatly speeds up traditional
geometric methods, but also improves the PSNR by up to
5.10 dB. It should be noted that the proposed framework
is not limited to the geometric methods but can also be
applied to the texture and hybrid methods. Experimental
results show that the proposed framework is able toproduce more reasonable results than texture and hybrid
methods.
The rest of this paper is organized as follows. The
theory foundation of the proposed framework is given in
Section 2. Implementation and optimization details are
discussed in Section 3. The effectiveness of our proposedmodel is evaluated in Section 4. Concluding remarks are
given in Section 5.
2. Theory foundation of the proposed framework
Restoration procedure can be well demonstrated by
the Bayesian model [44]. In image inpainting, we aim at
restoring the original image M by maximizing the following posterior probability formula:PðMjM 0 ; ΩÞ ¼

PðM 0 jM; ΩÞPðMjΩÞ;
PðM 0 jΩÞ

ð1Þwhere M0 and Ω are the given image and the missing data
areas, respectively.
When implementing logarithmic likelihood function on
both side of Eq. (1), the target becomesEðMjM 0 ; ΩÞ ¼ EðM0 jM; ΩÞ þ EðMjΩÞ−EðM 0 jΩÞð2Þ

where E(x) is a minus logarithmic likelihood function.
In a communication channel, since the quality degradation is independent of image content itself, it indicatesPðMjΩÞ ¼ PðMÞ. Once M0 and Ω are given, EðM 0 jΩÞ is aconstant and the minimization problem of Eq. (2) can be
rewritten asarg min : EðMjM 0 ; ΩÞ∝EðM 0 jM; ΩÞ þ EðMÞ;ð3Þ

where the specific notations of E(M) and EðM 0 jM; ΩÞ for
PDE based methods can be calculated by solving Eq. (4).

Fig. 1. Error analysis for image inpainting. (c) represents the restoration result T(M) which is restored firstly by the TV method and then transformed in the
T domain for comparison. (d) shows the restoration result of TðM 0 Þ which is firstly transformed in the T domain and then restored by the TV method.
Both of them consume about 24 s (the same 5000 iterations) [25]: (a) ground truth; (b) scratched M0; (c) T(M) 32.01 dB; and (d) TðM 0 Þ 41.59 dB.

M. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762

In practice, geometric method [45] is trying to minimize the following equation:
Z qﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
arg min :M 2x þ M 2y dx dy þΩ12s2 jΩc \Ωj

Z
2

Ωc \Ω

ðM−M 0 Þ dx dy;

ð4Þ
where ∂Ω is the boundary of the Ω which is assumed to besmooth. Since the above formula is a classical total variational model [46], a PDE is solved to find the result of
Eq. (4).
Our goal is to construct a framework to change theinitial condition of EðMjM0 ; ΩÞ so as to improve traditional
methods efficiently to solve the above minimization problem. In order to efficiently solve Eq. (4), we restore M in
the T domain and numerous experimental results verify
our strategy. Formula (5) is the foundation of the proposedtransform based framework:~ M~ 0 ; ΩÞ
~ ¼ TðEðMjM 0 ; ΩÞÞ:
EðMj

ð5Þ

The various resolutions of video sequences greatly
motive us, where different devices require various resolutions of the same video sequence for displaying, such as
CIF and QCIF formats. The original M0 is decomposed into
four resembling parts as shown in Fig. 1(c). Here the Ttransform is defined by the following Eq. (6) and thedetails are illustrated in Table 1:2~ 0 ¼4
T : M 0 -M

~1
M
0

~2
M
0

~3
M
0

~4
M
0

3
5;

ð6Þ

~ 0 and M~ k ðk ¼ 1; 2; 3; 4Þ, are the new components
where M0in T domain.
After incorporating T transform, Eq. (3) can be rewritten as~ M~ 0 ; ΩÞ∝Eð
~ 0 jM;~ ΩÞ~~~ þ EðMÞ:arg min : EðMjM

755

2.1. Holding local coherence
Fig. 1(c) shows how T transform keeps local texture~ 0 havecoherence. Pixels on ∂Ω of M0 and on Tð∂ΩÞ of M
similar neighboring circumstance. This property guarantees that the restoration results in the T domain are similaras that in the given domain, which keeps the traditional
inpainting methods performing well in the T domain.
2.2. Shrinking thick area
Inscribed Circle of the Hole (ICH) is the biggest inscribedcircle in the Ω areas, and employed in [47]. Generally
speaking, the restoration performances are determined by
the radius of the Inscribed Circle of the Hole (RICH) as shownin Fig. 2.
RICH ¼ MaxfR∂Ω1 ; R∂Ω2 ; …; R∂ΩN g:

ð8Þ

~ i ði ¼ 1; 2; 3; 4Þ is a quarter of the RICH in
The RICH in M0
M 0 which is crucial for inpainting methods. Bugeau et al.
[39] stated that one of constraints in their method is therestoration of thick area, although they have constructed a
hybrid framework for digital image inpainting. Therefore,
restoration of thick area is still a challenge task for stateof-the-art inpainting methods. If RICH decreases, the accumulated error to center pixels also decreases. In thatsituation, texture methods produce less abnormal repetitive results, and geometric methods obtain more information from boundary pixels for one iteration.
Let BΩ ¼ fΘðiÞji ¼ 1; 2; 3; …; Ng be a set containing theboundary pixels of all holes in M0, and ΘðiÞ ¼ fðx; yÞjðx; yÞ∈M∂Ωi g be the boundary pixels in the ith hole of Ω. Letξj be the correct propagation rate of the jth step along thenormal orientation of level line at pixel P0 as shown in Fig. 3,and εi ¼ fε1i ; ε2i ; …; εki ; …g be the error information of the ithhole, where εki is the error information in the kth step along

ð7Þ

In the following parts, we will demonstrate the advan~ M~ 0 ; ΩÞ~ for restoration. In general, the protages of EðMjposed T transform maintains three merits: holding local
coherence, shrinking the thick area and increasing the~ It is these three properties together that
length of ∂Ω.
constitute the main theory foundations of the proposed
framework.

Table 1The CST algorithm.
Chain rule based T Transform algorithm
STransformðM ðiÞ Þ
BEGIN
~
~1
M
ðiþ1Þ ¼ fðx; yÞjðx; yÞ ¼ ð2x; 2yÞ∈M ðiÞ g~~2
Mðiþ1Þ ¼ fðx; yÞjðx; yÞ ¼ ð2x; 2y−1Þ∈M ðiÞ g~~3
Mðiþ1Þ ¼ fðx; yÞjðx; yÞ ¼ ð2x−1; 2yÞ∈M ðiÞ g~~4
Mðiþ1Þ ¼ fðx; yÞjðx; yÞ ¼ ð2x−1; 2y−1Þ∈M ðiÞ g
END

Fig. 2. The definition of the biggest inscribed circle of Ω area. There are
two holes with different biggest inscribed circles in the picture withwidth M and height N.

756

M. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762

of in the given domain. For texture methods, moreboundary pixels provide more restoring orders and it
indicates that texture methods may produce a better
result.
Fig. 1 illustrates that when boundary pixels increase as
shown in Fig. 1(d), TV based methods can restore thecenter pixels better than that of in Fig. 1(c). As theperimeters increase in the T domain, more pixels in Fig. 1(d) can get their values directly from the boundary pixels.
~ to approach the ground truth
This advantage guarantees M
and this is why Fig. 1(d) exhibits better visual quality thanFig. 1(c).

! !
!
Fig. 3. Error propagation ratio and level lines. N 0 , N 1 and N 2 are thenormals of the level line at the pixels P0, P1 and P2, respectively. Pixel O is
the pixel which needs to be restored, and ξj is the correct propagation
rate of the jth step along the normal direction of level line.

the normal direction of level line:kjεki ¼ ΘðiÞ ∑ ∏ ð1−ξ1 Þð1−ξ2 Þ    ð1−ξm Þ:

ð9Þ

j¼1m¼1Let θerror be the total error information that one
restored pixel gets errors from pixels along its level line,
and wi ði ¼ 1; 2; …Þ be the weight of boundary pixels in theith hole. The total error information which is propagated to
the restored pixel can be expressed by the following
equation:kjθerror ¼ ∑ wk εki ¼ ΘðiÞ ∑ wk ∑ ∏ ð1−ξ1 Þð1−ξ2 Þ
k¼1

k¼1

j¼1m¼1  ð1−ξm Þ:

ð10Þ

In the T domain, εki ði ¼ 1; 2; …; NÞ and θerror decrease as
RICH decreases. Experimental results in Section 4 clearlysupport the inference and show advantages of the pro~ M~ 0 ; ΩÞ.
~
posed framework in solving EðMjFurthermore, error bound, for geometric methods, ispresented by Chan et al. [48]errðΩÞ ¼ ∑∂Li jLiΩ j;

ð11Þ

i

where ∂L ¼ Lmax ∂Li −Lmin ∂Li is the biggest intensity difference in the ith level line Li, and LiΩ is the restoration regionof the ith level line.
~ i is smaller
As proved above, the error bound of M
0than that of M0. In other words, the inequality of
1234~ Þ; errðΩ~ Þ, errðΩ~ Þ; errðΩ~ Þg indicateserrðΩÞ 4 maxferrðΩ~ M~ 0 ; ΩÞ~ can obtain a better result.
that EðMj
~2.3. Increasing ∂Ω~ ði ¼ 1; 2; 3; 4Þ, andIn the T domain, ∂Ω is mapped to ∂Ωit can also be proved that the following formula is true.
i4~ i 4∂Ω:
∑ ∂Ω

ð12Þ

i¼1

The above inequality is important for geometric methods. Since more boundary pixels can be used to restore themissing parts, Eq. (4) can be solved more quickly than that

3. Implementation and optimization
3.1. Implementation details
The definition of forward T transform is given by
Eq. (6), and it can be easily checked that T transform isrevertible. In other words, the original image M0 is able tobe completely reconstructed by the inverse transform T −1
as defined in Eq. (13):
2
T

−1

:4

~1
M
0

~2
M
0

~3
M
0

~4
M
0

3
~ 0 -M 0
5¼M

ð13Þ

In the proposed method, chain rule T○TðM 0 Þ can beapplied to the M0 if the Mi0 holds the following error
bounds as shown in Eq. (14). Finally, the chain rule based T
transform is given in Table 1,
8









~ 0 ðx0 ; y Þ−>
M 0 ðx; yÞ−
M
>



0
>  ∑ ∑ 
>
∑  ~
− ∑
 ¼ δ0 ðx; yÞ>< ðx;yÞ∈Pðx;yÞ M 0 ðx þ n; y þ mÞ  ðx0 ;y0 Þ∈Pðx0 ;y Þ M
0 ðx0 þ n; y0 þ mÞ 
0



>
~ 0 ðx0 ; y Þ ¼ δ1 ðx; yÞ>∑ ∑ M 0 ðx; yÞ−M>0>>∈Pðx;yÞ
: ðxðx;yÞ
0 ;y0 Þ∈Pðx0 ;y0 Þð14Þ
In Eq. (14), where n; m ¼ f−1; 0; 1g and δ0 ðx; yÞ is theerror estimator of patch Pðx; yÞ (3  3 pixels) centered at
pixel (x,y). δ0 ðx; yÞ; δ1 ðx; yÞ∈ð0; εÞ, ε is the global error bound,and δ ¼ ð∑∑ðx;yÞ∈∂Ω δðx; yÞÞ=j∂Ωj is the term used to measure
the feasibility of the T transform.

3.2. Optimization
3.2.1. Pre-processing
Although T transform holds the shape of original object~ as shownin M0, it may cause interlacing problem on ∂Ω
in Fig. 10(d), when the T −1 transform is performed on
different layers. One way to avoid this problem is to extend
the boundary of the original ∂Ω before the T transform.
Considering this kind of preprocessing step, the interlaced
problem is greatly removed as shown in Fig. 10(h).
Before introducing the proposed de-interlacing method,some notations are first employed. Let M imask ¼ fEðjÞjj ¼~ 0 in the ith layer of the1; 2; …g represent the mask of M
jth hole. Let Ei∂Ω1 ðjÞ and Ei∂Ω2 ðjÞ represent the first and second

M. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762

757

Table 2The workflow of the proposed framework.
DTF based algorithm
Step 1. BEGIN
Step 2. set initial value: i¼ 0;
iStep 3. construct a pre-processing picture Mp ¼Mi and calculate δ, ε;Step 4. M ip ðx; yÞ ¼ M ip ðx 7 1; y7 1Þ, if M ip ðx; yÞ∈Ei∂Ω1 ðjÞ and M ip ðx 7 1; y7 1Þ∈Ei∂Ω2 ðjÞ belong to different objects, Formula (15);
Step 5.
8
if δ o ε
>
>
>
>
>
>
< STtransformðM i Þ; i ¼ i þ 1; Stepð3Þ
if δ 4 ¼ ε;>>>
maxChain ¼ i; Stepð6Þ
>>>:

Step 6: restore the damaged picture M ip ðx; yÞ ¼
8
> if i ¼ ¼ maxChain>>>< Candidate Inpainting AlgorithmsðxÞ
;if i o maxChain>>>>: Formula ð17Þ Iteration ¼ 10

Step 7. Mi ðx; yÞ ¼

8
< M ip ðx; yÞM imask ¼ 1: M i ðx; yÞM imask ¼ 0;

Step 8. reconstruct the picture M i−1
p ðx; yÞ;Step 9.
8update the argument i ¼ i−1 and perform:> if i 4 ¼ 1>>>< Return to Stepð7Þ:;if i ¼ ¼ 0>>>>: Perform Stepð7Þ: Endof DTF:

Step 10:END

undamaged boundary pixels in the jth hole, respectively,
8 i>< E∂Ω1 ðjÞ ¼ fðx þ ℏ; y þ ℓÞjℏ; ℓ ¼ 0; 7 1: ð15Þ
and ðx; yÞ∈θðjÞ
>: iE∂Ω2 ðjÞ ¼ fðx þ ℏ; y þ ℓÞjℏ; ℓ ¼ 0; 7 2 and ðx; yÞ∈θðjÞ
If M i∂Ω1 ðx; yÞ and M i∂Ω2 ðm; nÞ are neighboring pixels,iM ∂Ω2 ðm; nÞ is reset as M i∂Ω1 ðx; yÞ when this pair of pixels

satisfy the following conditions:
8
i
i
>
>
> M∂Ω1 ðx 7 ℏ; y 7 ℓÞ≠M∂Ω1 ðm; nÞ>>< Mi 1 ðx 7 ℏ; y 7 ℓÞ∉θðjÞ∂Ω>> Mi∂Ω1 ðx; yÞ∈Ei∂Ω1 ðjÞ; M i∂Ω2 ðm; nÞ∈Ei∂Ω2 ðjÞ>>>: ðm; nÞ ¼ ðx þ ℏ; y þ ℓÞ; ℏ; ℓ ¼ 0; 71:

ð16Þ

3.2.2. Post-processing
To guarantee the coherence of boundary pixels at eachlayer of the T −1 transform, Laplacian formula is used torevise the inconsistencies among pixels at each layer
during the reverse process as show in Fig. 10(d) and (h):∂2 M i0 ∂2 Mi0
þ
¼ 0:
∂x2
∂y2

ð17Þ

Laplacian diffusion function Eq. (17) is employed tomaintain neighboring pixels coherence and parameters is
chose to avoid resulting in smooth problem. Details, like
controlling iterations, have been given in Table 2. In theend of this subsection, the details of the proposed diffusion based T transform framework (DTF) is shown in
Table 2.

4. Simulation results
In this section, the effectiveness of the DTF method is
evaluated by extensive experimental results, and theobjective performance is measured by peak signal to noise
ratio (PSNR). The proposed DTF method and other inpainting methods [9,16,25,32,40,42] are tested on a dual-core
PC(RAM 3072 M and CPU 2.53 GHz). For simplicity, theitem maxChain is manually set to two except for Fig. 4 dueto the low image resolutions. The restoration process of
DTF takes four steps as shown in Table 2: (1) forward T
transform; (2) performing traditional restoration; (3)inverse T transform, and (4) diffusion process. Candidates(x) can be geometric [9,25,40], texture [32], or hybrid
methods [16,42].

758

M. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762

Fig. 4. Results of Bertalmio et al. [9] and DTF based method for Tarja. 4(a) represents the results of Bertalmio et al. [9] with iterations ¼100, 1000, 1500,
3000 from left to right. The restoration result of DTF method with 30 iterations is shown in (b) (maxChain ¼3). (c) illustrates the comparison result of
Bertalmio and DTF model: left is the result of Bertalmio et al. [9] with iteration ¼ 3000 (3279 s). Right is the DTF method with iteration ¼ 30 (33 s). Note that
there still exist clearly scratches on the Tarja's hand: (a) Bertalmio et al. [9], Iteration ¼ 100, PSNR ¼ 21.78 dB (left), 1000, 30.18 dB, 1500, 32.06 dB, 3000,
35.72 dB (right); (b) DTF Iteration ¼ 30, 37.84 dB and (c) Tarja mirror-effect.

Fig. 5. Results of geometric inpainting methods and DTF method for Foreman video. (b)–(d) show the results of geometric methods [9,25,40], respectively.
The DTF based results are shown correspondingly for comparison: (a) original; (b) [9] 41.10 dB; (c) [25] 41.56 dB; (d) [40] 40.86 dB; (e) scratch; (f) DTF
41.47 dB; (g) DTF 42.36 dB; and (h) DTF 41.59 dB.

4.1. DTF for geometric methods
In Fig. 4, it is observed that DTF method remarkably
enhances the speed of the classical inpainting method [9],and it also indicates that DTF method works efficiently
under the thick area as shown in Fig. 10(b). Under thesame parameters, our DTF method outperforms Bertalmio
et al. [9]. It should be noted that, as shown in Fig. 10(c), theM. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762

759

Fig. 6. Results of geometric inpainting methods and DTF method for Peony: (a) original; (b) [9] 30.17 dB; (c) [25] 31.14 dB; (d) [40] 31.20 dB; (e) scratch;(f) DTF 30.85 dB; (g) DTF 31.14 dB; and (h) DTF 31.22 dB.

Table 3
Performances of proposed DTF framework for geometric methods.
Name

Tarja

Eye

PepperPeony

ForemanAverage

Methods

[9]
[25]
[40]
[9]
[25]
[40]
[9]
[25]
[40]
[9]
[25]
[40]
[9]
[25]
[40]
Δ Time saving (%)Δ PSNR (dB)Size

584  864
584  864
584  864
200  200
200  200
200  200512  384
512  384
512  384
768  512768  512768  512640  560
640  560
640  560

Time saving (s)PSNR (dB)

Ori.

DTF

Δ Gain (%)

Ori.

DTF

Δ Gain

3279
1980
160
440
433
20
631
810
52
1580
1220
105
185
1170
120

33
61
29
11
16
5
15
33
5
12
25
5
8
33
21

98.99
96.92
81.87
97.50
96.30
75.00
97.62
95.93
90.38
99.24
97.95
95.24
95.68
97.18
82.50

35.72
37.30
37.90
19.18
25.36
27.73
31.41
33.04
33.52
30.17
31.14
31.20
41.10
41.56
40.86

37.84
38.18
38.10
24.28
27.46
29.37
33.45
33.75
33.73
30.85
31.14
31.22
41.47
42.36
41.59

+2.12
+0.79
+0.20
+5.10
+2.10
+1.64
+2.04
+0.71
+0.21
+0.68
+0.00
+0.02
+0.37
+0.80
+0.73

93.20%+1.17

DTF method is able to save more time than method [9]and maintain the similar visual quality. For example, theproposed DTF method takes about 33 s, while Bertalmio[9] takes 3279 s nearly 100 times of the DTF method.
Fig. 5 depicts the performance of geometric methods
and DTF method to restore the Foreman video sequence. Itshows that both the DTF and geometric methods obtainthe similar visual quality. However, the DTF method saves
nearly 90% of time compared with geometric methods[9,25,40].
Fig. 6 depicts the performance of geometric methods
and DTF method to restore the Peony picture. Experimental results show that both the geometric and DTF based
method efficiently restore the yellow scratches. Obviously,
it is a great advantage that our proposed method saves
more time than the traditional geometric methods[9,25,40].
In Table 3, we give the overall performance of the DTF
method versus the geometric methods. It is observed that

our DTF method improves the PSNR 1.17 dB in average, andmeanwhile it saves time by 93.2%.
4.2. DTF for texture methods
In this subsection, we illustrate the results of the DTF
method versus texture methods. Fig. 7 shows that the
proposed framework improves texture method to restore
the missing parts. Fig. 7(b) shows that Criminisi et al. [32]produces irrational white patches on the surface of somesteps, while Fig. 7(d) shows that the DTF method restores the
texture perfectly.
Fig. 8 shows a girl running on the beach. The exemplar
based method [32] is used to remove the girl but it causes
explicit ink marks on the missing area as shown in Fig. 8(b). In Fig. 8(d), the DTF method restores the missing areawith the same texture from the background as expected.
In Fig. 9, we show the ability of the DTF method for edgereconstruction and very large object restoration. Fig. 9(b) and760

M. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762

Fig. 9. Results of edge reconstruction and very large object removal.
(b) and (d) are the results of [32] and the proposed DTF method,respectively: (a) original; (b) [32]; (c) scratch and (d) DTF.

(b) 41 s and Fig. 8(d) 48 s; (3) Fig. 9(b) 34 s andFig. 9(d) 59 s. Note that DTF consumes much time because
the DTF provides more restoring orders than texture methods.
4.3. DTF for hybrid methods
Fig. 7. Results of texture and DTF methods for Stairs picture. Criminisi
et al. [32] is shown in (b) and the DTF method is shown in (d):(a) original; (b) [32]; (c) scratch and (d) DTF.

Fig. 8. Results of texture and DTF method for Beach picture. The
restoration result of Criminisi et al. [32] is shown in (b) and thecomparison result of the DTF method is shown in (d): (a) original;(b) [32]; (c) scratch and (d) DTF.

(d) shows results of the exemplar based method [32] and theDTF, respectively. It is obvious that the proposed DTF method
achieves better performances than Criminisi et al. [32].
The runtime of texture methods versus DTF method aresummarized as: (1) Fig. 7(b) 31 s and Fig. 7(d) 38 s; (2) Fig. 8

The performances of DTF method versus hybrid
inpainting methods are shown in Fig. 10. Fig. 10(b) shows
Wexler et al. [16] with iteration rounds ¼5, neighborhood
radius¼ 3 and levels ¼3, whereas Fig. 10(f) shows theresult of our DTF method with the same parameters. It is
obvious that our DTF based method obtains better visualquality with PSNR gain by 3.51 dB than method [16].
As shown in Fig. 10(c), Bornemann et al. [42] performs
well, although the pupil has sharp corner.
Fig. 11 shows other results of hybrid inpainting methods versus the DTF method. In Fig. 11(b) and (e), our DTF
based method does achieve a better performance with
PSNR gain by 2.95 dB than that of Wexler et al. [16]. In
Fig. 11(c), Bornemann et al. [42] restores the green pepper
in the top-right corner with sickle texture. Comparing withabove results, it is not difficult to find that DTF method
performs better as shown in Fig. 11(f).
The runtime of hybrid methods versus DTF method aresummarized as: (1) Fig. 10(b) 121 s and Fig. 10(f) 140 s; (2)Fig. 10(c) 1 s and Fig. 10(g) 1 s; (3) Fig. 11(b) 1350 s andFig. 11(e) 1564 s; (4) Fig. 11(c) 2 s and Fig. 11(f) 1 s. Note thatDTF may consume more time than hybrid methods because
more restoring orders are tested in the DTF method.
5. Conclusion and discussion
In this paper, we proposed a hybrid transform based
DTF method for image inpainting. The DTF method consists of three components: chain transform part, restoration and diffusion part. Given a image, the DTF method isable to efficiently restore them on the proposed framework. In addition, we gave the theory foundation analysis
of DTF method. In order to tackle interlacing problem,
we designed boundary strategy and employed diffusion

M. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762

761

Fig. 10. Results of hybrid inpainting and DTF methods for eye. (b) and (f) illustrate results of Wexler et al. [16] and DTF method for comparison. Bornemannet al. [42] is presented in (c) and the DTF method is shown in (g). (d) and (h) are the results of DTF without/with pre- and post-processing, respectively:(a) original; (b) [16] 25.74 dB; (c) [42] 30.86 dB; (d) 28.36 dB; (e) scratch; (f) DTF 29.25 dB; (g) DTF 31.10 dB; (h) 31.10 dB.

Fig. 11. Results of hybrid inpainting and DTF based method for Pepper. The restoration result of Wexler et al. [16] is shown in (b) and comparison result of
our DTF method is shown in (e). Bornemann et al. [42] is shown in 11(f) and our DTF method is shown in (f): (a) original; (b) [16] 30.39 dB; (c) [42]33.62 dB; (d) scratch; (e) DTF 33.64 dB; and (f) DTF 33.74 dB.

method to refine the results. Finally, we constructed the
hybrid framework in a hierarchical way. Experimental
results show that the DTF method greatly improves boththe efficiency and performance of conventional methods.

Acknowledgments
The authors would like to thank A.C. Telea, A. Criminisi
and Folkmar Bornemann for publishing their codes which
provide great convenience for our experimental results.
This work is partially supported by NSFC (Grant no.
61073067) and by Hong Kong PGS.

References[1] W. Carey, D. Chuang, S. Hemami, Regularity-preserving image interpolation, IEEE Transactions on Image Processing 8 (1999) 1293–1297.
[2] C. Ballester, M. Bertalmio, V. Caselles, G. Sapiro, J. Verdera, Filling-inby joint interpolation of vector fields and gray levels, IEEE Transactions on Image Processing 10 (2001) 1200–1211.
[3] J. Hwang, H. Lee, Adaptive image interpolation based on local
gradient features, IEEE Transactions on Signal Processing Letters 11(2004) 359–362.
[4] N. Komodakis, Image completion using global optimization, in: IEEE
Computer Society Conference on Computer Vision and Pattern
Recognition, vol. 1, pp. 442–452.
[5] H. Ting, S. Chen, J. Liu, X. Tang, Image inpainting by global structure
and texture propagation, in: Proceedings of the 15th International
Conference on Multimedia, pp. 517–520.

762

M. Wang et al. / Signal Processing: Image Communication 28 (2013) 753–762[6] N. Komodakis, G. Tziritas, Image completion using efficient belief
propagation via priority scheduling and dynamic pruning, IEEE
Transactions on Image Processing 16 (2007) 2649–2661.
[7] J. Mairal, M. Elad, G. Sapiro, Sparse representation for color image
restoration, IEEE Transactions on Image Processing 17 (2008) 53–69.
[8] C. Hsieh, Y. Chen, C. Hsu, Fast image restoration method based on themulti-resolution layer, Tamkang Journal of Science and Engineering
12 (2009) 439–448.
[9] M. Bertalmio, G. Sapiro, V. Caselles, C. Ballester, Image inpainting,in: Proceedings of Computer Graphics and Interactive Techniques,
SIGGRAPH 2000, pp. 417–424.
[10] M. Bertalmio, L. Vese, G. Sapiro, S. Osher, Simultaneous structure
and texture image inpainting, IEEE Transactions on Image Processing
12 (2003) 882–889.
[11] S. Rane, G. Sapiro, M. Bertalmio, Structure and texture filling-in of
missing image blocks in wireless transmission and compression
applications, IEEE Transactions on Image Processing 12 (2003)
296–303.
[12] W. Yan, M. Kankanhalli, Erasing video logos based on image
inpainting, in: IEEE International Conference on Multimedia andExpo (ICME 2002), vol. 2, pp. 521–524.
[13] W. Yan, J. Wang, M. Kankanhalli, Automatic video logo detection andremoval, Multimedia Systems 10 (2005) 379–391.
[14] K. Patwardhan, G. Sapiro, M. Bertalmio, Video inpainting of occluding and occluded objects, in: IEEE International Conference on Image
Processing (ICIP 2005), vol. 2, pp. II–69–72.
[15] K. Patwardhan, G. Sapiro, M. Bertalmío, Video inpainting underconstrained camera motion, IEEE Transactions on Image Processing
16 (2007) 545.
[16] Y. Wexler, E. Shechtman, M. Irani, Space-time completion of video,
IEEE Transactions on Pattern Analysis and Machine Intelligence 29(2007) 463–476.
[17] P. Pérez, M. Gangnet, A. Blake, Patchworks: Example-Based Region
Tiling for Image Editing, Technical Report MSR-TR-2004-04, Microsoft Research, Redmond, WA, 2004.
[18] Y. Pritch, E. Kav-Venaki, S. Peleg, Shift-map image editing, in: IEEE
12th International Conference on Computer Vision, pp. 151–158.
[19] C. Barnes, E. Shechtman, A. Finkelstein, D. Goldman, Patchmatch: arandomized correspondence algorithm for structural image editing,in: ACM Transactions on Graphics (TOG), vol. 28, p. 24.
[20] C. Wang, X. Sun, F. Wu, H. Xiong, Image compression with structureaware inpainting, in: 2006 IEEE International Symposium on
Circuits and Systems (ISCAS 2006), IEEE, p. 4.
[21] D. Liu, X. Sun, F. Wu, S. Li, Y. Zhang, Image compression with edgebased inpainting, IEEE Transactions on Circuits and Systems forVideo Technology 17 (2007) 1273–1287.
[22] Z. Xiong, X. Sun, F. Wu, Block-based image compression withparameter-assistant inpainting, IEEE Transactions on Image Processing 19 (2010) 1651–1657.
[23] S. Masnou, J. Morel, Level lines based disocclusion, in: IEEE International Conference on Image Processing (ICIP 2005), pp. 259–263.
[24] S. Masnou, Disocclusion: a variational approach using level lines,
IEEE Transactions on Image Processing 11 (2002) 68–76.
[25] T. Chan, J. Shen, Mathematical models for local nontexture inpaintings, SIAM Journal on Applied Mathematics 62 (2001) 1019–1043.
[26] T. Chan, J. Shen, L. Vese, Variational PDE models in image processing,
Notices of the American Mathematical Society 50 (2003) 14–26.
[27] T. Chan, J. Shen, Image Processing and Analysis: Variational, PDE,
Wavelet, and Stochastic Methods, Society for Industrial Mathematics, 2005.

[28] T. Chan, J. Shen, Nontexture inpainting by curvature-driven diffusions, Journal of Visual Communication and Image Representation
12 (2001) 436–449.
[29] M. Bertalmio, A. Bertozzi, G. Sapiro, et al., Navier–Stokes, fluid
dynamics, and image and video inpainting, in: IEEE Computer
Society Conference on Computer Vision and Pattern Recognition(CVPR 2001), vol. 1.
[30] M. Bertalmio, Strong-continuation, contrast-invariant inpainting
with a third-order optimal PDE, IEEE Transactions on Image Processing 15 (2006) 1934–1938.
[31] A. Bertozzi, S. Esedoglu, A. Gillette, Inpainting of binary images using
the Cahn–Hilliard equation, IEEE Transactions on Image Processing
16 (2007) 285–291.
[32] A. Criminisi, P. Pérez, K. Toyama, Region filling and object removal by
exemplar-based image inpainting, IEEE Transactions on Image
Processing 13 (2004) 1200–1212.
[33] A. Efros, T. Leung, Texture synthesis by non-parametric sampling, in:Proceedings of the 7th IEEE International Conference on Computer
Vision (ICCV 1999), vol. 2, pp. 1033–1038.
[34] M. Fadili, J. Starck, Em algorithm for sparse representation-based
image inpainting, in: IEEE International Conference on Image
Processing, vol. 2, pp. II–61.
[35] M. Elad, M. Aharon, Image denoising via sparse and redundant
representations over learned dictionaries, IEEE Transactions on
Image Processing 15 (2006) 3736–3745.
[36] O.G. Guleryuz, Nonlinear approximation based image recovery using
adaptive sparse reconstructions and iterated denoising. Part II.:
Adaptive algorithms, IEEE Transactions on Image Processing 15(2006) 555–571.
[37] X. Li, Image recovery via hybrid sparse representations: a deterministic annealing approach, IEEE Journal of Selected Topics in Signal
Processing 5 (2011) 953–962.
[38] Z. Xu, J. Sun, Image inpainting by patch propagation using patch
sparsity, IEEE Transactions on Image Processing 19 (2010)
1153–1165.
[39] A. Bugeau, M. Bertalmío, V. Caselles, G. Sapiro, A comprehensive
framework for image inpainting, IEEE Transactions on Image
Processing 19 (2010) 2634–2645.
[40] A. Telea, An image inpainting technique based on the fast marching
method, Journal of Graphics Tools 9 (2004) 23–34.
[41] J. Sun, L. Yuan, J. Jia, H. yeung Shum, Image completion withstructure propagation, ACM Transactions on Graphics 24 (2005)
861–868.
[42] F. Bornemann, T. März, Fast image inpainting based on coherencetransport, Journal of Mathematical Imaging and Vision 28 (2007)
259–278.
[43] D. Cho, T. Bui, Image inpainting using wavelet-based inter-and intrascale dependency, in: 19th International Conference on Pattern
Recognition (ICPR 2008), pp. 1–4.
[44] J. Shen, Inpainting and the fundamental problem of image processing, SIAM News 36 (2003) 1–4.
[45] T. Chan, J. Shen, Variational image inpainting, Communications on
Pure and Applied Mathematics 58 (2005) 579–619.
[46] L. Rudin, S. Osher, E. Fatemi, Nonlinear total variation based noise
removal algorithms, Physica D 60 (1992) 259–268.
[47] M. Wang, B. Yan, H. Gharavi, Pyramid model based down-samplingfor image inpainting, in: IEEE International Conference on Image
Processing (ICIP 2010), pp. 429–432.
[48] T. Chan, S. Kang, Error analysis for image inpainting, Journal of
Mathematical Imaging and Vision 26 (2006) 85–103.