Image Inpainting Considering
Brightness Change and Spatial Locality of
Textures and Its Evaluation
Norihiko Kawai, Tomokazu Sato, and Naokazu Yokoya
Graduate School of Information Science, Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-0192, Japan{norihi-k,tomoka-s,yokoya}@is.naist.jp
http://yokoya.naist.jp/
Abstract. Image inpainting techniques have been widely investigated toremove undesired objects in an image. Conventionally, missing parts in animage are completed by optimizing the objective function using patternsimilarity. However, unnatural textures are easily generated due to two factors: (1) available samples in the image are quite limited, and (2) patternsimilarity is one of the required conditions but is not suﬃcient for reproducing natural textures. In this paper, we propose a new energy function basedon the pattern similarity considering brightness changes of sample textures(for (1)) and introducing spatial locality as an additional constraint (for(2)). The eﬀectiveness of the proposed method is successfully demonstrated
by qualitative and quantitative evaluation. Furthermore, the evaluation
methods used in much inpainting research are discussed.
Keywords: Image Inpainting, Energy Minimization, Evaluation Method.

1

Introduction

Image inpainting methods have been widely investigated to remove undesired visual objects in an image. These methods can be classiﬁed into two categories. One
is a non-exemplar-based method and the other is an exemplar-based method. The
non-exemplar-based methods [1,2,3,4,5,6,7,8,9,10,11] are based on pixel interpolation considering the continuity of pixel intensity. These methods are eﬀective
for small image gaps like scratches in a photograph. However, the resultant image easily becomes unclear when the missing region is large. Therefore, recently
many exemplar-based inpainting methods have been intensively developed because they can synthesize complex textures in the missing region.
Exemplar-based methods basically synthesize textures for the missing region
based on pattern similarity that is deﬁned between the missing region and therest of the image (data region). Some of the exemplar-based methods use thedistance in the feature space as a similarity measure. As the feature space,
Fourier space, wavelet domain and eigenspace have been used [12,13,14]. Mostof the other exemplar-based methods simply employ SSD (Sum of Squared
Diﬀerences)-based pattern similarity measures [15,16,17,18,19,20,21,22,23,24].
Efros et al. [15] have proposed a method that successively copies the most similar
T. Wada, F. Huang, and S. Lin (Eds.): PSIVT 2009, LNCS 5414, pp. 271–282, 2009.
c Springer-Verlag Berlin Heidelberg 2009
272

N. Kawai, T. Sato, and N. Yokoya

pattern from the data region to the missing region. Although this method cangenerate complex textures, the quality of resultant images is severely aﬀectedby the order of texture copy. To obtain good results with successive texture
copy, conﬁdence maps such as the number of ﬁxed pixels in a window, strengthof isophotes around the missing regions and pattern similarity have been used
to determine the order of texture copy [16,17,18]. Although the duplication ofsimilar textures preserves the local texture continuity in these methods, discontinuous textures are easily synthesized in the completed image. To avoid theordering problem, recent inpainting methods employ the iterative global optimization approach [19,20,21]. In these methods, the objective functions that
evaluate the pattern similarity are deﬁned and optimized by using EM algorithm,
Belief Propagation approach and graph cut approach.
Although the global optimization methods have obtained good results formany images, unnatural images are still generated due to two factors: (1) available samples in the data region are quite limited, and (2) pattern similarity is
one of the required conditions but is not suﬃcient for reproducing natural textures. Thus, in order to improve the image quality, these two factors should beconsidered. There have already been some attempts at this. For (1), the scale andorientation of textures have been considered to obtain eﬀective samples [22]. For(2), Sun et al. [23] and Jia et al. [24] have proposed techniques that use explicit
constraints for texture boundaries. These methods synthesize textures preserving the edges or boundaries of the texture. However, automatic and eﬀective
determination of these explicit constraints is still diﬃcult.
In this paper, we propose a new approach that is diﬀerent from conventional
ones. For (1), brightness change of sample textures that has not been consideredin the literature is allowed to obtain eﬀective samples. For (2), the spatial localityof texture pattern is considered as an implicit constraint that is usually satisﬁed
in a lot of real scenes. In this study, these ideas are implemented with the framework of energy minimization. The eﬀectiveness of our method is demonstrated
with subjective and objective evaluation. In addition, in this paper, the validityof evaluation methods for image inpainting which has not been well discussed isanalyzed. Furthermore, the problems of qualitative and quantitative evaluation
methods that have been used in the literature are clearly demonstrated.

2

Image Inpainting Based on Energy Minimization

In the proposed method, after initial values are given to missing regions, thetarget regions are completed by minimizing an energy function. In the following
sections, the deﬁnition of an energy function and the minimization method of
the energy function are described.
2.1

Energy Function Considering Brightness Change and Spatial
Locality

As illustrated in Figure 1, an image is divided into region Ω  including the missing
region Ω and the data region Φ, which is the rest of the image. The plausibilityImage Inpainting Considering Brightness Change and Spatial LocalityΦdata region
window W

window W

xi

Ω′

x̂i

273

Ω

missing
regionFig. 1. Data and missing regions in an image

in the missing region Ω is deﬁned by using image patterns in the data region Φ.
Here, Ω  is the expanded area of the missing region Ω. Ω  has a central pixel xi
of a square window W overlapping the region Ω. The energy function is deﬁned
as the weighed sum of SSD representing the pattern similarity considering
brightness change and SD representing the spatial locality as follows:
wxi {SSD (xi , x̂i ) + wdis SD(xi , x̂i )} ,(1)E=
xi ∈Ω where xi is the pixel in the region Ω  , x̂i is the corresponding pixel in the dataregion Φ and wdis is the weight for the spatial locality. Here, wxi is the weightfor pixel xi and is set as 1 if xi is inside of the region Ω  ∩ Ω because pixel values
in this region are ﬁxed: otherwise wxi is set as c−d (d is the distance from theboundary of Ω and c is a constant) because pixel values around the boundary
have higher conﬁdence than those in the center of the missing region. In thefollowing, deﬁnitions of SSD (xi , x̂i ) and SD(xi , x̂i ) are described.
Similarity considering brightness change
The similarity measure SSD is deﬁned as:2SSD (xi , x̂i ) ={I(xi + p) − αxi x̂i I(x̂i + p)} ,

(2)

p∈W

where I(x) represents the intensity of pixel x. αxi x̂i is the intensity modiﬁcation coeﬃcient. By using this coeﬃcient, the brightness of the texture in thedata region is adjusted to that in the missing region so as to prevent unnatural
brightness changes. In this paper, we employ the ratio of average pixel values
around the pixels xi and x̂i as the coeﬃcient αxi x̂i .
2q∈W I(xi + q)
αxi x̂i = .
(3)2q∈W I(x̂i + q)

274

N. Kawai, T. Sato, and N. Yokoya

Cost of spatial locality

SD ( x, xˆ )Distancex − xˆ
between pixels
Inside an object

Outside an object

Fig. 2. Sigmoid function for cost of spatial locality

However, an unnatural image is easily generated if large brightness change isapproximated by linear transformation. Therefore, we limit the range of thevalue αxi x̂i .
Spatial locality of texture
Cost term SD for spatial locality of a texture pattern is deﬁned by using asigmoid function:
SD(xi , x̂i ) =W 
1 + e{−K(xi −x̂i −X0 )},(4)

where K and X0 are constant and  W  is the number of pixels in a window.
As illustrated in Fiture 2, this cost term is based on the assumption that theprobability of similar texture existence for a certain pixel is uniformly high (costis uniformly low) in the object region which the pixel belongs to. On the other
hand, outside the object region, the probability can be assumed to be uniformly
low (cost is uniformly high). By adding the constraint of spatial locality, evenwhen the deformation of texture pattern exists around the missing region, appropriate textures that exist near the missing region are preferentially selected.
2.2

Energy Minimization

The energy function E in Eq. (1) is minimized by using a framework of greedy
algorithm. In our deﬁnition of the energy E, the energy for each pixel can betreated independently if pattern pairs (xi ,x̂i ) can be ﬁxed and the change ofthe coeﬃcient αxi x̂i in iteration is very small. Thus, we repeat the following
two processes until the energy converges: (i) update of pairs of windows keeping
pixel values ﬁxed, and (ii) parallel update of all the pixel values keeping pairs of
windows ﬁxed.

Image Inpainting Considering Brightness Change and Spatial Locality

275

In process (i), the update of the pair of windows is performed by calculatingx̂i keeping the pixel values I(xi ) ﬁxed. x̂i is determined as follows:x̂i = f (xi ) = argmin(SSD (xi , x) + wdis SD(xi , x)).

(5)

x∈Φ

In process (ii), all the pixel values I(xi ) are updated in parallel so as tominimize the energy keeping the similar pairs of windows ﬁxed. In the following,
the method for calculating the pixel values I(xi ) is described. First, the energy
E is resolved into the element energy E(xi ) for each pixel in the missing region.
As shown in Figure 3, the target pixel to be updated is xi , and the pixel
position inside a window can be expressed as xi +p (p ∈ W ) and is corresponded
to f (xi +p) by Eq. (5). Thus, the position of the pixel corresponding to the pixel
xi is f (xi + p) − p. Now, the element energy E(xi ) can be expressed in terms of
the pixel values of xi and f (xi + p) − p, the coeﬃcient α and the Euclid distance
between xi and f (xi ) as follows:E(xi ) =w(xi +p) {I(xi ) − α(xi +p)f (xi +p) I(f (xi + p) − p)}2

p∈W

+ wdisW 
1 + e{−K(xi −f (xi )−X0 )}. (6)The relationship between the energy E for all of the missing region and theelement energy E(xi ) for each pixel can be written as follows:E(xi ) + C.
(7)
E=
xi ∈Ω

C is the energy of pixels in the region Ω ∩Ω  , and is treated as a constant because
pixel intensities in the region and all pairs of windows are ﬁxed here. Therefore,by minimizing the element energy E(x) respectively, the total energy E can be
minimized. Here, if it is assumed that the change of αxi f (xi ) is smaller than thatof the pixel intensity I(xi ), by diﬀerentiating E(xi ) with respect to I(xi ), eachpixel value I(xi ) in the missing region can be calculated in parallel as follows:p∈W w(xi +p) α(xi +p)f (xi +p) I(f (xi + p) − p)I(xi ) =.
(8)p∈W w(xi +p)
Additionally, in order to avoid local minima eﬃciently, a coarse-to-ﬁne approach is also employed for energy minimization. Speciﬁcally, an image pyramid
is generated and the energy minimization processes (i) and (ii) are repeatedfrom higher-level to lower-level layers successively using a certain size of window. Good initial values are given to the lower layer by projecting results fromthe higher layer. This makes it possible to decrease computational cost and avoid
local minima. In the lowest layer (original size), the energy minimization process
is repeated while reducing the size of the window, and it enables reproductionof more detailed textures.

276

N. Kawai, T. Sato, and N. Yokoya

f (xi + p) − p Φxifmost similar
windowsf ( x i + p)

Ω xi + p

Fig. 3. Relationship between pixels in energy calculation

3

Experiments

In experiments, we have compared the proposed method with conventional
ones using 100 images. The methods are our implemented Criminisi’s method(Method A) [17], our implemented Wexler’s method (Method B) [20] and the
proposed method (Method E). To conﬁrm the eﬀectiveness of considering thebrightness change and spatial locality, respectively, the proposed method allowing only brightness change (Method C) and the proposed method considering
only spatial locality (Method D) were also evaluated. In these experiments, eachparameter in the energy function was set as shown in Table 1 for all the images.
Here, the missing region was manually speciﬁed, and the average pixel value ofthe boundary of the missing region was given as an initial value in the missing
region.
3.1

Qualitative Evaluation

All the completed images by 5 methods were subjectively evaluated by 37 subjects. The subjects were requested to access the web page for questionnaire evaluation and evaluate the resultant images arranged in random order by giving ascore of 1(bad) to 5 (good).
Table 1. Parameters in experiments
Window size

Nw max 9×9
min 3×3
Weight for distancewdis
120
Parameter in sigmoid function K
0.4
X0
20
Range of coeﬃcient αD
0.1

Image Inpainting Considering Brightness Change and Spatial Locality

277

The average scores of the 100 resultant images are shown in Table 2 for eachmethod.1 Table 2 shows that the average score by the proposed method (method
E) is higher than the scores by the conventional methods (methods A and B).
In this experiment, scores of the proposed method (method E) and the conventional methods (methods A and B) were compared by using the t-test with a 5%
signiﬁcant level. Resultingly, signiﬁcant diﬀerence was observed between thesescores. In addition, both methods C and D obtained higher scores than methods A and B and signiﬁcant diﬀerences were also observed by using the t-test
with a 5% signiﬁcant level. Therefore, the proposed method can be statisticallyveriﬁed to be better than the conventional methods A and B, and considering
brightness change and spatial locality is respectively eﬀective. Figure 4 shows
example images for which the proposed method had better scores. The proposed
method has generated better results for the images in which brightness change
and deformation of texture patterns exist around the missing regions due to theillumination change and the perspective projection eﬀect.
3.2

Quantitative Evaluation

In this experiment, RMSE was computed for 29 images whose missing regions
were speciﬁed regardless of the object regions, and we did not use the remaining
71 images because the missing regions of the 71 images are speciﬁed so as toremove certain objects. Table 3 shows the average RMSE. From the results, theproposed method is the best of all 5 the methods and signiﬁcant diﬀerences
between the proposed (E) and conventional methods (A and B) were observedby using the t-test with a 5% signiﬁcant level.
3.3

Discussion of Evaluation Methods

Although some evaluation have been done in the literature of image inpainting,the validity of evaluation methods has not been well discussed. In this section,
qualitative and quantitative evaluation methods are analyzed using our results
and their problems are clariﬁed.
Table 2. Average score from 100 images
MethodA B C D E
Average score 2.21 3.24 3.39 3.42 3.60

Table 3. Average RMSE from 29 images
Method A
BCD
E
RMSE 42.95 28.40 27.83 28.36 27.44

1

One hundred input and resultant images are shown on the web page[http://yokoya.naist.jp/research/inpainting/].

278

N. Kawai, T. Sato, and N. Yokoya(a) Input images with a missing region.

(b) Results by Wexler’s method [20].

(c) Results by the proposed method.
Fig. 4. Example images providing the proposed method with better scores

Reliability of qualitative evaluation
The evaluation using a few images and a few subjects may not be able to validate
the eﬀectiveness of inpainting methods due to the bias of images and subjects.
In this section, the reliability of the result when the images and subjects areAverage Ranking Error:
ARE 0.1 0.05
ARE=0
37
9
5

(h=2,n=4)

1

1
5
100
Number of images: n(a) For A and E.

Average Ranking Error: ARE
Number of Subjects: hNumber of Subjects: hImage Inpainting Considering Brightness Change and Spatial Locality

0.1 0.05

37

279

ARE=0

(h=37,n=18)

29
22
15
(h=2,n=49)

8
1

1

20
40
Number of images: n100(b) For D and E.

Fig. 5. Relationships among ARE and the number of images and subjects

decreased in a questionnaire is analyzed in simulation. Here, the ranking of themethods decided by the average of scores given by 37 subjects in the questionnaire using 100 images were used as the ground truth.
In this paper, as the reliability measure of evaluation results, RE (Ranking
Error) is deﬁned as:RE(n, h) =0 (∀i, g(i, 100, 37) − g(i, n, h) = 0)
1 (otherwise),(9)

where g(i, n, h) represents the rank order of the method i determined by n images
and h subjects. In this study, we compute RE(n, h) with respect to random
selection of n images and h subjects from 100 images and 37 subjects. ARE(n, h)
is the average score of RE(n, h) by 10,000 times selection.
Figure 5 shows the relationship among ARE and the number of images andsubjects. In this ﬁgure, (a) and (b) illustrate isolines of ARE for the methods A
and E, and D and E, respectively. In this ﬁgure, isolines are drawn every 0.05.
The scores of the methods A and E are signiﬁcantly and largely diﬀerent.
From Figure 5(a), when h=2, the ranking corresponds to the ground truth morethan 95% of the time (ARE=0.05) if n>3. Therefore, for methods that generatesigniﬁcantly diﬀerent results, the ranking is usually equivalent to the groundtruth even if the numbers of subjects and images are small. On the other hand,the scores of the methods D and E are signiﬁcantly but a little diﬀerent. From
Figure 5(b), in order for the ranking to correspond to the ground truth morethan 95% of the time, more than 49 images are needed if h=2. Even if h=37,
at least 18 images are needed. Therefore, if the numbers of subjects and images
are small, the ranking may not correspond to the ground truth and the resultof subjective evaluation is not reliable. Therefore, to evaluate image inpainting
methods persuasively, many images and subjects (for example, 40 images and 5
subjects) are needed.

0.8~ 1.0
0.6~ 0.8
0.4~ 0.6
0.2~ 0.4
0 ~ 0.2-0.2~ 0-0.4~ -0.2
-0.6~ -0.4
-0.8~ -0.6
-1.0~ -0.8
05

10 15 20

Number of images(a) From A to E.

Correlation coefficientN. Kawai, T. Sato, and N. Yokoya

Correlation coefficient

280

0.8~ 1.0
0.6~ 0.8
0.4~ 0.6
0.2~ 0.4
0 ~ 0.2-0.2~ 0-0.4~ -0.2
-0.6~ -0.4
-0.8~ -0.6
-1.0~ -0.8
05

10 15 20

Number of images(b) From B to E.

Fig. 6. Correlation coeﬃcient between RMSE and subjective score

Fig. 7. Images with inverse correlation between RMSE and subjective evaluations

Relationship between quantitative and qualitative evaluation
In the literature on image inpainting, as the quantitative evaluation, MSE(Mean Squared Error), RMSE (Root Mean Squared Error) and PSNR (Peak
Signal-to-Noise Ratio), which are based on computing pixel-wise diﬀerences between original and inpainted images, have been often used. In this evaluation,
RMSE is computed for each image, and the relationship between RMSE andscores given by subjects is discussed.
Figure 6 illustrates the distribution of the correlation coeﬃcient between
RMSE and the subjective score for 29 images: (a) is by 5 methods, (b) is by
4 methods except for method A [17]. Correlation coeﬃcient Cc is computed asfollows:
Cc=

Nm ΣiNm Ri Si − ΣiNm Ri ΣiNm Si, (10)
Nm ΣiNm Ri 2 − (ΣiNm Ri )2 Nm ΣiNm Si 2 − (ΣiNm Si )2

where Nm is the number of methods, Ri is RMSE and Si is the average scoreby subjects. From Table 3 and Figure 6(a), there is a clear negative correlation
between RMSE and subjective score. From this, although the evaluation result
by RMSE may correspond to the ground truth, there also exist three images(Figure 7) where positive correlation exists. As shown in Figure 7, these images

Image Inpainting Considering Brightness Change and Spatial Locality

281

have very high-frequency components. It is well known that pixel correlationbased similarity measures including RMSE are sensitive to pixel phase shift
for a high frequency component. However, such a pixel phase shift does notalways aﬀect the naturality of images. Thus, RMSE cannot appropriately evaluate the images with a high frequency component. Figure 6(b) illustrates the
distribution of the correlation coeﬃcient by the 4 methods except for method
A, whose score is extremely low. In Figure 6(b), one third of the coeﬃcients
indicate positive correlation. This means that the small diﬀerence in RMSE
does not always represent that of image naturality. Therefore, RMSE cannot be
used as an absolute criterion of image naturality but can be used for a roughevaluation.

4

Conclusion

In this paper, the new energy function for image inpainting has been proposed.
To obtain good results for many images, two factors were considered: (1) brightness change of sample textures was allowed, (2) spatial locality was introduced
as a new constraint. By considering these two factors, the missing region wascompleted successfully for many images. In experiments, we have demonstrated
the eﬀectiveness of our method by qualitative and quantitative evaluation. wehave also discussed the validity of evaluation methods for image inpainting. In
future work, we should establish a method to decide optimum parameters automatically by analyzing an image.
Acknowledgments. This research was partially supported by the Ministry of
Education, Culture, Sports, Science and Technology, Grant-in-Aid for ScientiﬁcResearch (A), 19200016.

References
1. Levin, A., Zomet, A., Weiss, Y.: Learning How to Inpaint from Global Image
Statistics. In: Proc. ICCV, vol. 1, pp. 305–312 (2003)
2. Ballester, C., Bertalmio, M., Sapiro, V., Verdera, J.: Filling-In by Joint Interpolation of Vector Fields and Gray Levels. Trans. on Image Processing 10(8), 1200–1211(2001)
3. Ballester, C., Caselles, V., Verdera, J., Bertalmio, M., Sapiro, G.: A Variational
Model for Filling-In Gray Level and Color Images. In: Proc. ICCV, pp. 10–16(2001)
4. Tschumperlé, D.: Curvature-preserving regularization of multi-valued images using
pDE’s. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3952,
pp. 295–307. Springer, Heidelberg (2006)
5. Villéger, E., Aubert, G., Blanc-Féraud, L.: Image Disocclusion Using a Probabilistic Gradient Orientation. In: Proc. ICPR, vol. 2, pp. 52–55 (2004)
6. Bertalmio, M., Bertozzi, A.L., Sapiro, G.: Navier-Stokes, Fluid Dynamics, andImage and Video Inpainting. In: Proc. CVPR, pp. 355–362 (2001)

282

N. Kawai, T. Sato, and N. Yokoya

7. Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image Inpainting. In: Proc.
SIGGRAPH 2000, pp. 417–424 (2000)
8. Esedoglu, S., Shen, J.: Digital Inpainting Based on the Mumford-shah-euler Image
Model. European J. of Applied Mathematics 13, 353–370 (2003)
9. Masnou, S., Morel, J.M.: Level Lines Based Disocclusion. In: Proc. ICIP, vol. 3,
pp. 259–263 (1998)
10. Chan, T., Shen, J.: Non-texture Inpainting by Curvature-Driven Diﬀusions (CDD).
J. of Visual Communication and Image Representation 12(4), 436–449 (2001)
11. Chan, T., Kang, S., Shen, J., Osher, S.: Euler’s Elastica and Curvature Based
Inpaintings. SIAM J. of Applied Mathematics 63(2), 564–592 (2002)
12. Hirani, A.N., Totsuka, T.: Combining Frequency and Spatial Domain Information
for Fast Interactive Image Noise Removal. In: Proc. SIGGRAPH 1996, pp. 269–276(1996)
13. Rane, S.D., Remus, J., Sapiro, G.: Wavelet-Domain Reconstruction of Lost Blocks
in Wireless Image Transmission and Packet-Switched. In: Proc. ICIP, vol. 1, pp.
309–312 (2002)
14. Amano, T.: Image Interpolation by High Dimensional Projection Based on Subspace Method. In: Proc. ICPR, vol. 4, pp. 665–668 (2004)
15. Efros, A.A., Leung, T.K.: Texture Synthesis by Non-parametric Sampling. In: Proc.
ICCV, pp. 1033–1038 (1999)
16. Bornard, R., Lecan, E., Laborelli, L., Chenot, J.: Missing Data Correction in Still
Images and Image Sequences. In: Proc. ACM Int. Conf. on Multimedia, pp. 355–361(2002)
17. Criminisi, A., Pérez, P., Toyama, K.: Region Filling and Object Removal by
Exemplar-Based Image Inpainting. Trans. on Image Processing 13(9), 1200–1212(2004)
18. Li, B., Qi, Y., Shen, X.: An Image Inpainting Method. In: Proc. IEEE Int. Conf.
on Computer Aided Design and Computer Graphics, pp. 531–536 (2005)
19. Allène, C., Paragios, N.: Image Renaissance Using Discrete Optimization. In: Proc.
ICPR, pp. 631–634 (2006)
20. Wexler, Y., Shechtman, E., Irani, M.: Space-Time Completion of Video. Trans. on
PAMI 29(3), 463–476 (2007)
21. Komodakis, N., Tziritas, G.: Image Completion Using Global Optimization. In:
Proc. CVPR, pp. 442–452 (2006)
22. Drori, I., Cohen-Or, D., Yeshurun, H.: Fragment-Based Image Completion. In:
Proc. SIGGRAPH 2003, pp. 303–312 (2003)
23. Sun, J., Yuan, L., Jia, J., Shum, H.: Image Completion with Structure Propagation.
In: Proc. SIGGRAPH 2005, pp. 861–868 (2005)
24. Jia, J., Tang, C.: Image Repairing: Robust Image Synthesis by Adaptive ND Tensor
Voting. In: Proc. CVPR, pp. 643–650 (2003)