We propose to modify image inpainting technique based on F-transform for application dedicated to cartoon images. The images have typical features which are taken into consideration. These features make original algorithm ineffective, because of its isotropic nature. Proposed modification changes it to an anisotropic.
Image restoration, in meaning of object removal or
damage recovery, so called image inpainting, is challenging
task in image processing. Let us consider input image
I which contains unwanted pixels considered as a
damage. In the process of image inpainting, the damaged area
should be erased and replaced by some proper part of I.
The selection of the proper part is crucial. One option is
to choose square shaped patch and replace the damaged
area by its copy. In that case, we are talking about
patchbased image inpainting[
Structure of the paper is as follows. Section 2 gives preliminaries including information about F-transform and details about its two types. Section 3 describes basics of the specific type of images used in this paper and Section 4 gives information about mathematical morphology. Detailed description of proposed technique is in Section 5 and conclusion is given in Section 6. Let us fix the following notation to use throughout the paper. Image I is a 2D vector function such as I : [0, M] × [0, N] → [0, 255]3, where [0, 255]3 stands for pixel intensities in three color channels. We denote [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 and N + 1 is the image height. Image I is assumed to be partially defined: it is defined (known) on the areaΦ and undefined (unknown, damaged) on the area Ω. The border between these areas is denoted by δ Ω and assumed to be unknown. It is assumed that Φ ∩ Ω = 0/ and Φ ∪ Ω ∪ δ Ω = [0, M] × [0, N]. Mask S is a binary image where white pixels denote unknown area Ω + δ Ω. The mask is created by user with respect to areas intended for deletion. The notation is illustrated in Fig. 1. (a) (b)
We are focused on image restoration. By this we mean that pixels from Ω ∪ δ Ω should be replaced by pixels from Φ. The resulting image should make an impression that damage is not present. 2.1
Below, we recall the definition of a fuzzy partition [
4) Ak(x) strictly increase on [xk−1, xk], k = 1, . . . , m; and strictly decrease on [xk, xk+1], k = 1, . . . , m;
m 5) ∑k=0 Ak(x) = 1, x ∈ [0, M].
We say that the fuzzy partition given by A0, . . . , Am, is an h-uniform fuzzy partition if nodes xk = hk, k = 0, . . . , m, are equidistant, h = M/m and two additional properties are met: 6) Ak(xk − x) = Ak(xk + x), x ∈ [0, h], k = 0, . . . , m; 7) Ak(x) = Ak−1(x − h), k = 1, . . . , m, x ∈ [xk−1, xk+1]. Parameter h will be referred to as a radius.
Assume that fuzzy sets A0, . . . , Am establish a fuzzy partition of [0, M]. The following vector of real numbers 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 by
Fk0 =
M ∑x=0 Ak(x)I(x)
M ∑x=0 Ak(x) , k = 0, . . . , m.
(1)
Let us introduce F-transform of a 2D grayscale image I that is considered as a function I : [0, M] × [0, N] → [0, 255].
Let A0, . . . , Am and B0, . . . , Bn be basic functions,
A0, . . . , Am : [0, M] → [
We say that the m × n-matrix of real numbers [Fk0l ]
is called the (discrete) F-transform of I with respect to
{A0, . . . , Am} and {B0, . . . , Bn} if for all k = 0, . . . , m, l =
0, . . . , n,
In this section, we recall the (direct) F1-transform as it has
been presented in [
Pk0(x) = 1, Pk1(x) = x − xk, (Ql0(y) = 1, Ql1(y) = y − yl ), where 1 is a denotation of the respective constant function.
Analogously, let L21(Ak × Bl ) ⊆ L2(Ak × Bl ) be a linear span of the set consisting of three orthogonal polynomials
Sk0l0(x, y) = 1, Sk1l0(x, y) = x − xk, Sk0l1(x, y) = y − yl . Let I ∈ L2([0, M] × [0, N]), and Fk1l be the orthogonal projection of I|[xk−1,xk+1]×[yl−1,yl+1] on subspace L21(Ak × Bl ), k = 0, . . . , m, l = 0, . . . , n.
We say that matrix F1mn[I] = (Fk1l ), k = 0, . . . , m, l = 0, . . . , n, is the F1-transform of I with respect to {Ak × Bl | k = 0, . . . , m, l = 0, . . . , n}, and Fk1l is the corresponding F1transform component.
xk−1 where the weight function is equal to Ak.
1L2(Ak) is a Hilbert space of square-integrable functions f : [xk−1, xk+1] → R with the weighted inner product h f , gik given by
Z xk+1 h f , gik = f (x)g(x)Ak(x)dx, (3)
The F1-transform components of I are linear polynomials in the form
Fk1l (x, y) = ck0l0 + ck1l0(x − xk) + ck0l1(y − yl ), where the coefficients are given by ck0l0 = ck1l0 = ck0l1 = ∑y=0 ∑xM=0 I(x, y)Ak(x)Bl (y)
N
N M , ∑y=0 ∑x=0 Ak(x)Bl (y)
N M ∑y=0 ∑x=0 I(x, y)(x − xk)Ak(x)Bl (y) ∑y=0 ∑xM=0(x − xk)2Ak(x)Bl (y)
N
N M ∑y=0 ∑x=0 I(x, y)(y − yl )Ak(x)Bl (y) ∑y=0 ∑xM=0(y − yl )2Ak(x)Bl (y)
N . 2.3
In [
k=0 l=0
where O is the output (reconstructed) image. In fact, the
algorithm computes the F-transform components of the
input image I and spreads the components afterwards to the
size of I. For details see [
Let us recall basics of the technique and illustrate its update for the cartoon images. The original technique works 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:
This approach works well for photos as was shown
in [
In this paper, we suggest inpainting technique aimed to be applied to images with two specific features: • limited color palette, • strong and thick uni-color edges.
These features are usually included in simple cartoon images as can be seen in Fig. 2.
For testing purposes, we created a set of artificial images with the same features. The set is in Fig. 3. (4) (5) (6) (a) Boy
(b) Goat
(c) Homer
Application of mathematical morphology [
In mathematical morphology, a structuring element is selected and applied to the input image. For our method, a binary image is used. We recall three main operations: erosion, dilation and closing. If image I contains only few colors and thick edges, reconstruction using original algorithm based on (6) is affected by visible artifacts. Illustration is in Fig. 12. A new proposed algorithm is based on the assumption that similar areas should be reconstructed independently. Main idea is 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 during the reconstruction process and it influences the computation of the F0-transform components as it is shown below
We can say that image V and mask S overlaps image I. Mask S coincides with the characteristic function of area Φ. 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 of edges only and similarly, for pixels from the other nonedge areas. This feature changes isotropic nature of the original inpainting algorithm to anisotropic because pixel colors are not necessarily distributed to the all neighbourhood.
Bellow, the proposed algorithm is illustrated on the input from Fig. 4. (a) I (b) S
Comment: At this step, we compute coefficients c00, c10, c01 of I F1-transform components in accordance with (5). The output for the input in Fig. 4 is in Fig. 5. (a) c00
(b) c01 (c) c10
2) Upscale c10 and c01 to the size of image I and convert 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 highest gradient. Because of our assumption about the thick edges in I, we copy and shift c01 to the left and c10 to the up. Doing this, we restrict horizontal and vertical edges.
5) Create new image V as the union of c01, c10 and their shifted copies. Threshold V to obtain the binary image.
Comment: After this step, we obtain binary image V . Its white pixels represent edges whereas black pixels represent areas without significant gradient. Illustration is in Fig. 7.
Comment: The purpose of this step is to fill in all imperfections of V . In step 3, we subtracted the mask and that created holes in the detected edge area. By closing, we fix these holes and prolong (connect) appropriate parts of image edges. Illustration is in Fig. 8. 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. By closing, we fill the holes. Illustration of this step is in Fig. 9.
(a) Vg (b) Vc 9) Find intersections of Vg and the mask S.
The intersections determine places on the edge area which are damaged. Let us name this intersection Sg. Illustration is in Fig. 10. (a) Edge reconstruction (b) detail of a) (c) Reconstruction of the rest 10) Use Sg as a mask and Vg as an valid pixels set for edge reconstruction. Use S − Sg as a mask and Vc as a valid pixels set for reconstruction of the rest.
Because we separated edges from the rest, we can reconstruct these two parts independently. Illustration is in Fig. 11. 5.1
Let us illustrate the proposed inpainting algorithm side by side with original technique based on F-transform. The (g) Shape (h) Shape (i) Shape images from Fig. 3 was damaged and reconstructed afterwards. Results are in Fig. 12.
Let us magnify the details to demonstrate a difference in higher resolution. In Fig. 13, the comparison is given. The original technique blurs the lines, do not follow edges (a) Circle b)
(b) Lines e) (c) Shape h) (d) Circle c)
(e) Lines f) (f) Shape i) and mix colors together. Reason is the isotropic nature of 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
We propose a novel inpainting technique aimed to specific
type of images. Original inpainting technique based on
F-transform was applied on photos and introduced in [
The main idea of the novel algorithm is in division of 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 formulas. The same is applied to the rest of the image. (a) Homer (b) Boy (c) Goat (d) Homer (e) Boy (f) Goat
We illustrated our technique on the two sets of images and compared with original one.
This work was supported by the project LQ1602 IT4Innovations excellence in science.