=Paper=
{{Paper
|id=Vol-1885/167
|storemode=property
|title=Inpainting
Using F-Transform for Cartoon-Like Images
|pdfUrl=https://ceur-ws.org/Vol-1885/167.pdf
|volume=Vol-1885
|authors=Pavel Vlašánek,Irina Perfilieva
|dblpUrl=https://dblp.org/rec/conf/itat/VlasanekP17
}}
==Inpainting
Using F-Transform for Cartoon-Like Images==
https://ceur-ws.org/Vol-1885/167.pdf
J. Hlaváčová (Ed.): ITAT 2017 Proceedings, pp. 167–173
CEUR Workshop Proceedings Vol. 1885, ISSN 1613-0073, c 2017 P. Vlašánek, I. Perfilieva
Inpainting Using F-Transform for Cartoon-Like Images
Pavel Vlašánek, Irina Perfilieva
Institute for Research and Applications of Fuzzy Modeling,
University of Ostrava, 30. dubna 22, Ostrava, Czech Republic
pavel.vlasanek@osu.cz
Abstract: We propose to modify image inpainting tech-
nique based on F-transform for application dedicated to
cartoon images. The images have typical features which
are taken into consideration. These features make origi-
nal algorithm ineffective, because of its isotropic nature.
Proposed modification changes it to an anisotropic.
1 Introduction
(a) (b)
Image restoration, in meaning of object removal or dam-
age recovery, so called image inpainting, is challenging Figure 1: a) Two areas where image I is defined (Φ) and
task in image processing. Let us consider input image undefined (Ω); b) mask S.
I which contains unwanted pixels considered as a dam-
age. In the process of image inpainting, the damaged area
should be erased and replaced by some proper part of I. We are focused on image restoration. By this we mean
The selection of the proper part is crucial. One option is that pixels from Ω ∪ δ Ω should be replaced by pixels from
to choose square shaped patch and replace the damaged Φ. The resulting image should make an impression that
area by its copy. In that case, we are talking about patch- damage is not present.
based image inpainting[1, 6, 7, 8]. In this paper, as well as
in many others, we use principle of the techniques taking
2.1 F0 -Transform
colors of the separated pixels in the close neighborhood of
the damaged area to the consideration [2, 3, 4, 5]. Below, we recall the definition of a fuzzy partition [10].
Structure of the paper is as follows. Section 2 gives Fuzzy sets A0 , . . . , Am identified with their membership
preliminaries including information about F-transform and functions (basic functions) A0 , . . . , Am : [0, M] → [0, 1], es-
details about its two types. Section 3 describes basics of tablish a fuzzy partition of [0, M] with nodes 0 = x0 < x1 <
the specific type of images used in this paper and Section · · · < xm = M if the following conditions are fulfilled:
4 gives information about mathematical morphology. De-
tailed description of proposed technique is in Section 5 and 1) Ak : [0, M] → [0, 1], Ak (xk ) = 1;
conclusion is given in Section 6.
2) Ak (x) = 0 if x ∈
/ (xk−1 , xk+1 ), k = 0, . . . , m;
2 Preliminaries 3) Ak (x) is continuous;
4) Ak (x) strictly increase on [xk−1 , xk ],
Let us fix the following notation to use throughout the
k = 1, . . . , m; and strictly decrease on [xk , xk+1 ], k =
paper. Image I is a 2D vector function such as I :
1, . . . , m;
[0, M] × [0, N] → [0, 255]3 , where [0, 255]3 stands for pixel
intensities in three color channels. We denote [0, M] = 5) ∑m
k=0 Ak (x) = 1, x ∈ [0, M].
{0, 1, 2, . . . , M}, [0, N] = {0, 1, 2, . . . , N} and [0, 255] =
{0, 1, 2, . . . , 255}. Therefore, M + 1 is the image width We say that the fuzzy partition given by A0 , . . . , Am , is
and N + 1 is the image height. Image I is assumed to an h-uniform fuzzy partition if nodes xk = hk, k = 0, . . . , m,
be partially defined: it is defined (known) on the area Φ are equidistant, h = M/m and two additional properties are
and undefined (unknown, damaged) on the area Ω. The met:
border between these areas is denoted by δ Ω and as-
sumed to be unknown. It is assumed that Φ ∩ Ω = 0/ and 6) Ak (xk − x) = Ak (xk + x), x ∈ [0, h], k = 0, . . . , m;
Φ ∪ Ω ∪ δ Ω = [0, M] × [0, N]. Mask S is a binary image 7) Ak (x) = Ak−1 (x − h), k = 1, . . . , m, x ∈ [xk−1 , xk+1 ].
where white pixels denote unknown area Ω + δ Ω. The
mask is created by user with respect to areas intended for Parameter h will be referred to as a radius.
deletion. The notation is illustrated in Fig. 1.
168 P. Vlašánek, I. Perfilieva
Assume that fuzzy sets A0 , . . . , Am establish a fuzzy par- The F1 -transform components of I are linear polynomi-
tition of [0, M]. The following vector of real numbers als in the form
Fm [I] = (F0 , . . . , Fm ) is the (direct) discrete F-transform of
I w.r.t. A0 , . . . , Am where the k−th component Fk is defined Fkl1 (x, y) = c00 10 01
kl + ckl (x − xk ) + ckl (y − yl ), (4)
by
∑M Ak (x)I(x) where the coefficients are given by
Fk0 = x=0M , k = 0, . . . , m. (1)
∑x=0 Ak (x) ∑Ny=0 ∑M
x=0 I(x, y)Ak (x)Bl (y)
c00
kl = ,
Let us introduce F-transform of a 2D grayscale image ∑Ny=0 ∑M
x=0 Ak (x)Bl (y)
I that is considered as a function I : [0, M] × [0, N] →
[0, 255]. ∑Ny=0 ∑M
x=0 I(x, y)(x − xk )Ak (x)Bl (y)
c10
kl = , (5)
Let A0 , . . . , Am and B0 , . . . , Bn be basic functions, ∑Ny=0 ∑M 2
x=0 (x − xk ) Ak (x)Bl (y)
A0 , . . . , Am : [0, M] → [0, 1] be fuzzy partition of [0, M] and
∑Ny=0 ∑M
x=0 I(x, y)(y − yl )Ak (x)Bl (y)
B0 , . . . , Bn : [0, N] → [0, 1] be fuzzy partition of [0, N]. c01
kl = .
We say that the m × n-matrix of real numbers [Fkl0 ] ∑Ny=0 ∑M 2
x=0 (y − yl ) Ak (x)Bl (y)
is called the (discrete) F-transform of I with respect to
{A0 , . . . , Am } and {B0 , . . . , Bn } if for all k = 0, . . . , m, l = 2.3 F-Transform Image Inpainting
0, . . . , n,
In [12], the technique of F-transforms was proposed for
∑Ny=0 ∑M
x=0 I(x, y)Ak (x)Bl (y) the inpainting. It uses two steps: direct and inverse of the
Fkl0 = . (2) 0th-degree F-transform. The direct step is described in the
∑y=0 ∑M
N
x=0 Ak (x)Bl (y)
previous section whereas the inverse is as follows
The coefficients Fkl0 are called components of the F- m n
transform. O(x, y) = ∑ ∑ Fkl0 Ak (x)Bl (y), (6)
k=0 l=0
2.2 F1 -Transform where O is the output (reconstructed) image. In fact, the
algorithm computes the F-transform components of the in-
In this section, we recall the (direct) F1 -transform as it has put image I and spreads the components afterwards to the
been presented in [11]. Let {Ak × Bl | k = 0, . . . , m, l = size of I. For details see [12].
0, . . . , n} be a fuzzy partition of [0, M] × [0, N]. L21 (Ak ) ⊆ Let us recall basics of the technique and illustrate its up-
L2 (Ak ) (L21 (Bl ) ⊆ L2 (Bl ))1 be a linear span of the set con- date for the cartoon images. The original technique works
sisting of two orthogonal polynomials with the assumption that damaged pixels of I should not
be included in a component value. For that purpose, the
binary mask S is used in the computation:
Pk0 (x) = 1, Pk1 (x) = x − xk ,
(Q0l (y) = 1, Q1l (y) = y − yl ), ∑Ny=0 ∑M
x=0 I(x, y)S(x, y)Ak (x)Bl (y)
Fkl0 = .
∑Ny=0 ∑M
x=0 S(x, y)Ak (x)Bl (y)
where 1 is a denotation of the respective constant func-
tion. This approach works well for photos as was shown
Analogously, let L21 (Ak × Bl ) ⊆ L2 (Ak × Bl ) be a linear in [13, 15, 12, 9]. For cartoon images, the quality of recon-
span of the set consisting of three orthogonal polynomials struction is not sufficient because of the isotropic nature of
the algorithm. The problem is that edges are not taken into
00 10 01 consideration during the computation.
Skl (x, y) = 1, Skl (x, y) = x − xk , Skl (x, y) = y − yl .
Let I ∈ L2 ([0, M] × [0, N]), and F1kl be the orthogonal pro- 3 Cartoon Images
jection of I|[xk−1 ,xk+1 ]×[yl−1 ,yl+1 ] on subspace L21 (Ak × Bl ),
k = 0, . . . , m, l = 0, . . . , n. In this paper, we suggest inpainting technique aimed to be
We say that matrix F1mn [I] = (Fkl1 ), k = 0, . . . , m, l = applied to images with two specific features:
0, . . . , n, is the F1 -transform of I with respect to {Ak × Bl |
k = 0, . . . , m, l = 0, . . . , n}, and F1kl is the corresponding F1 - • limited color palette,
transform component.
• strong and thick uni-color edges.
1 L (A ) is a Hilbert space of square-integrable functions f :
2 k
[xk−1 , xk+1 ] → R with the weighted inner product h f , gik given by These features are usually included in simple cartoon
Z x
h f , gik =
k+1
f (x)g(x)Ak (x)dx, (3) images as can be seen in Fig. 2.
xk−1 For testing purposes, we created a set of artificial images
where the weight function is equal to Ak . with the same features. The set is in Fig. 3.
Inpainting Using F-Transform for Cartoon-Like Images 169
4.1 Erosion
The erosion is defined as follows
I T = {z ∈ [0, M] × [0, N]|Tz ⊆ I},
where T is a structuring element and z is a translation vec-
tor. Operator of binary erosion is in fact a test whether
image I contains areas like T .
4.2 Dilation
The dilation is defined as follows
(a) Boy (b) Goat [
I ⊕T = It ,
t∈T
where T is a structuring element and It is the translation of
I by t.
4.3 Closing
Operator of closing is the erosion of dilation defined as
(c) Homer
follows
Figure 2: Test set of cartoon images. I • T = (I ⊕ T ) T.
The effect of binary closing is in filling small holes and
imperfections in the image I.
5 Novel Inpainting Technique
If image I contains only few colors and thick edges, recon-
struction using original algorithm based on (6) is affected
by visible artifacts. Illustration is in Fig. 12. A new pro-
posed algorithm is based on the assumption that similar
areas should be reconstructed independently. Main idea is
(a) Circle (b) Lines to separate these areas and reconstruct each of them with
respect to a particular color. In this paper, we propose to
separate edges (pixels with high gradient) from the rest of
the image, reconstruct their damaged parts and continue
with the other areas afterwards.
For this purpose, another binary image V is taken into
consideration. The image V is created automatically dur-
ing the reconstruction process and it influences the com-
putation of the F0 -transform components as it is shown
below
(c) Shape ∑Ny=0 ∑M
x=0 I(x, y)S(x, y)V (x, y)Ak (x)Bl (y)
Fkl0 = .
Figure 3: Test set of artificial cartoon images. ∑Ny=0 ∑M
x=0 S(x, y)V (x, y)Ak (x)Bl (y)
We can say that image V and mask S overlaps image I.
Mask S coincides with the characteristic function of area
4 Mathematical Morphology Φ. Image V designates by 1 the so called valid pixels. The
latter are used in the reconstruction process. Therefore,
the edges are reconstructed from pixels of the known part
Application of mathematical morphology [14] is an im- of edges only and similarly, for pixels from the other non-
portant step in the proposed method. Let us give a short edge areas. This feature changes isotropic nature of the
description of this technique. original inpainting algorithm to anisotropic because pixel
In mathematical morphology, a structuring element is colors are not necessarily distributed to the all neighbour-
selected and applied to the input image. For our method, hood.
a binary image is used. We recall three main operations: Bellow, the proposed algorithm is illustrated on the in-
erosion, dilation and closing. put from Fig. 4.
170 P. Vlašánek, I. Perfilieva
(a) I (b) S (a) c01 (b) cc10
Figure 4: Input image and mask for algorithm description. Figure 6: Updated coefficients c01 and c10 . Contrast was
enhanced for better visibility.
1) Compute the F1 -transform.
5) Create new image V as the union of c01 , c10 and their
Comment: At this step, we compute coefficients
shifted copies. Threshold V to obtain the binary im-
c00 , c10 , c01 of I F1 -transform components in accordance
age.
with (5). The output for the input in Fig. 4 is in Fig. 5.
Comment: After this step, we obtain binary image V . Its
white pixels represent edges whereas black pixels repre-
sent areas without significant gradient. Illustration is in
Fig. 7.
(a) c00 (b) c01
Figure 7: Image V composed from c01 , c10 and their
shifted copies.
6) Apply morphological closing to V .
(c) c10
Comment: The purpose of this step is to fill in all imper-
Figure 5: Coefficients of F1 -transform. Contrast was en-
fections of V . In step 3, we subtracted the mask and that
hanced for better visibility.
created holes in the detected edge area. By closing, we
fix these holes and prolong (connect) appropriate parts of
2) Upscale c10 and c01 to the size of image I and convert image edges. Illustration is in Fig. 8.
them to gray-scale.
3) Update c01 and c10 by subtracting mask S from them.
Comment: Performing this update we eliminate false
edges. Illustration is in Fig. 6.
4) Make shifted copies of c01 and c10 .
Comment: Edges are detected in the places with the high-
est gradient. Because of our assumption about the thick
edges in I, we copy and shift c01 to the left and c10 to the Figure 8: Morphological closing applied on Fig. 7.
up. Doing this, we restrict horizontal and vertical edges.
Inpainting Using F-Transform for Cartoon-Like Images 171
7) Use white pixels of V to find edge area of I and by
histogram analysis determine a dominant color of it.
Further on, the color is called edge color.
8) Based on the edge color divide I to Vg and Vc and
subtract mask from both. Turn Vg and Vc to binary
images and apply morphological closing.
Image Vg represents edges of the I whereas Vc the rest.
Image Vg contains holes because of the mask subtraction. (a) Edge reconstruction (b) detail of a)
By closing, we fill the holes. Illustration of this step is in
Fig. 9.
(c) Reconstruction of the rest
Figure 11: a) Reconstruction of the edge; b) detail; c) re-
(a) Vg (b) Vc construction of the rest of the image I.
Figure 9: Binary division of image I to the edge area Vg
and the rest Vc followed by a morphological closing.
9) Find intersections of Vg and the mask S.
The intersections determine places on the edge area
(a) Circle (b) Circle (c) Circle
which are damaged. Let us name this intersection Sg . Il-
lustration is in Fig. 10.
(d) Lines (e) Lines (f) Lines
Figure 10: Mask of damaged part of the edges.
(g) Shape (h) Shape (i) Shape
10) Use Sg as a mask and Vg as an valid pixels set for edge Figure 12: Application of our algorithm to damaged im-
reconstruction. Use S − Sg as a mask and Vc as a valid ages from Fig. 3. Images a), d), g) are the damaged ones,
pixels set for reconstruction of the rest. images b), e) and h) were reconstructed using the origi-
nal technique and images c), f) and i) were reconstructed
Because we separated edges from the rest, we can re- using the proposed one.
construct these two parts independently. Illustration is in
Fig. 11.
images from Fig. 3 was damaged and reconstructed after-
5.1 Examples and Comparison wards. Results are in Fig. 12.
Let us magnify the details to demonstrate a difference
Let us illustrate the proposed inpainting algorithm side by in higher resolution. In Fig. 13, the comparison is given.
side with original technique based on F-transform. The The original technique blurs the lines, do not follow edges
172 P. Vlašánek, I. Perfilieva
(a) Circle b) (b) Lines e)
(a) Homer (b) Boy
(c) Shape h)
(c) Goat
(d) Circle c) (e) Lines f)
(f) Shape i)
Figure 13: Details of Fig. 12.
and mix colors together. Reason is the isotropic nature of (d) Homer (e) Boy
the original formula. Thus for cartoon images, we propose
to use different approach described in this paper.
In Fig. 14, the novel inpainting technique is illustrated
on the set of cartoon images.
6 Conclusion
We propose a novel inpainting technique aimed to specific (f) Goat
type of images. Original inpainting technique based on
F-transform was applied on photos and introduced in [12]. Figure 14: The cartoon images from testing set in Fig. 2
The main idea of the novel algorithm is in division of damaged and reconstructed.
input image and independent processing of its parts. In
this introduction paper, we suggest to divide the image to
two parts: edges and rest. The edges are separated using
coefficients of F1 -transform. Its damaged (missing) parts
are connected together using mathematical morphology.
Based on that, missing parts of the edges are identified and
reconstructed using inpainting technique with updated for- We illustrated our technique on the two sets of images
mulas. The same is applied to the rest of the image. and compared with original one.
Inpainting Using F-Transform for Cartoon-Like Images 173
Acknowledgment [15] Vlašánek and I. Perfilieva. Image reconstruction with us-
age of the F-transform. In International Joint Conference
This work was supported by the project LQ1602 CISIS’12-ICEUTE’12-SOCO’12 Special Sessions, pages
IT4Innovations excellence in science. 507 – 514, Berlin, 2013. Springer.
References
[1] M. Ashikhmin. Synthesizing natural textures. In Proceed-
ings of the 2001 symposium on Interactive 3D graphics,
pages 217–226. ACM, 2001.
[2] C. Ballester, V. Caselles, J. Verdera, M. Bertalmio, and
G. Sapiro. A variational model for filling-in gray level and
color images. In Computer Vision, 2001. ICCV 2001. Pro-
ceedings. Eighth IEEE International Conference on, vol-
ume 1, pages 10–16. IEEE, 2001.
[3] M. Bertalmio, A. L. Bertozzi, and G. Sapiro. Navier-stokes,
fluid dynamics, and image and video inpainting. In Com-
puter Vision and Pattern Recognition, 2001. CVPR 2001.
Proceedings of the 2001 IEEE Computer Society Confer-
ence on, volume 1, pages I–355. IEEE, 2001.
[4] M. Bertalmio, G. Sapiro, V. Caselles, and C. Ballester. Im-
age inpainting. In Proceedings of the 27th annual con-
ference on Computer graphics and interactive techniques,
pages 417–424. ACM Press/Addison-Wesley Publishing
Co., 2000.
[5] T. F. Chan and J. Shen. Nontexture inpainting by curvature-
driven diffusions. Journal of Visual Communication and
Image Representation, 12(4):436–449, 2001.
[6] J. S. De Bonet. Multiresolution sampling procedure for
analysis and synthesis of texture images. In Proceedings of
the 24th annual conference on Computer graphics and in-
teractive techniques, pages 361–368. ACM Press/Addison-
Wesley Publishing Co., 1997.
[7] A. A. Efros and W. T. Freeman. Image quilting for tex-
ture synthesis and transfer. In Proceedings of the 28th
annual conference on Computer graphics and interactive
techniques, pages 341–346. ACM, 2001.
[8] A. A. Efros and T. K. Leung. Texture synthesis by non-
parametric sampling. In Computer Vision, 1999. The Pro-
ceedings of the Seventh IEEE International Conference on,
volume 2, pages 1033–1038. IEEE, 1999.
[9] V. Pavel and P. Irina. Interpolation techniques versus F-
transform in application to image reconstruction. In Fuzzy
Systems (FUZZ-IEEE), 2014 IEEE International Confer-
ence on, pages 533–539. IEEE, 2014.
[10] I. Perfilieva. Fuzzy transforms: Theory and applications.
Fuzzy sets and systems, 157(8):993–1023, 2006.
[11] I. Perfilieva, P. Hodáková, and P. Hurtík. Differentiation by
the F-transform and application to edge detection. Fuzzy
Sets and Systems, 2014.
[12] I. Perfilieva and P. Vlašánek. Image reconstruction by
means of F-transform. Knowledge-Based Systems, 70:55–
63, 2014.
[13] I. Perfilieva, P. Vlašánek, and M. Wrublová. Fuzzy trans-
form for image reconstruction. In Uncertainty Modeling in
Knowledge Engineering and Decision Making, Singapore,
2012. World Scientific.
[14] J. Serra. Image analysis and mathematical morphology, v.
1. Academic press, 1982.