Introduction

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 [1,6,7,8]. In this paper, as well as in many others, we use principle of the techniques taking colors of the separated pixels in the close neighborhood of the damaged area to the consideration [2,3,4,5].

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.

Preliminaries

Let us fix the following notation to use throughout the paper. Image I is a 2D vector function such as I : 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, M] × [0, N] → [0, 255]Φ ∩ Ω = / 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. 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.

F 0 -Transform

Below, we recall the definition of a fuzzy partition [10]. Fuzzy sets A 0 , . . . , A m identified with their membership functions (basic functions) A 0 , . . . ,

A m : [0, M] → [0, 1], es- tablish a fuzzy partition of [0, M] with nodes 0 = x 0 < x 1 < • • • < x m = M if the following conditions are fulfilled: 1) A k : [0, M] → [0, 1], A k (x k ) = 1; 2) A k (x) = 0 if x / ∈ (x k−1 , x k+1 ), k = 0, . . . , m; 3) A k (x) is continuous; 4) A k (x) strictly increase on [x k−1 , x k ], k = 1, . . . , m; and strictly decrease on [x k , x k+1 ], k = 1, . . . , m; 5) ∑ m k=0 A k (x) = 1, x ∈ [0, M].

We say that the fuzzy partition given by A 0 , . . . , A m , is an h-uniform fuzzy partition if nodes x k = hk, k = 0, . . . , m, are equidistant, h = M/m and two additional properties are met:

6) A k (x k − x) = A k (x k + x), x ∈ [0, h], k = 0, . . . , m; 7) A k (x) = A k−1 (x − h), k = 1, . . . , m, x ∈ [x k−1 , x k+1 ].

Parameter h will be referred to as a radius.

Assume that fuzzy sets A 0 , . . . , A m establish a fuzzy partition of [0, M]. The following vector of real numbers F m [I] = (F 0 , . . . , F m ) is the (direct) discrete F-transform of I w.r.t. A 0 , . . . , A m where the k−th component F k is defined by

F 0 k = ∑ M x=0 A k (x)I(x) ∑ M x=0 A k (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 A 0 , . . . , A m and B 0 , . . . , B n be basic functions, A 0 , . . . , A m : [0, M] → [0, 1] be fuzzy partition of [0, M] and B 0 , . . . , B n :

[0, N] → [0, 1] be fuzzy partition of [0, N].

We say that the m × n-matrix of real numbers

[F 0 kl ] is called the (discrete) F-transform of I with respect to {A 0 , . . . , A m } and {B 0 , . . . , B n } if for all k = 0, . . . , m, l = 0, . . . , n, F 0 kl = ∑ N y=0 ∑ M x=0 I(x, y)A k (x)B l (y) ∑ N y=0 ∑ M x=0 A k (x)B l (y) .(2)

The coefficients F 0 kl are called components of the Ftransform.

F 1 -Transform

In this section, we recall the (direct) F 1 -transform as it has been presented in [11].

Let {A k × B l | k = 0, . . . , m, l = 0, . . . , n} be a fuzzy partition of [0, M] × [0, N]. L 1 2 (A k ) ⊆ L 2 (A k ) (L 1 2 (B l ) ⊆ L 2 (B l ))

1 be a linear span of the set consisting of two orthogonal polynomials

P 0 k (x) = 1, P 1 k (x) = x − x k , (Q 0 l (y) = 1, Q 1 l (y) = y − y l ),

where 1 is a denotation of the respective constant function.

Analogously, let

L 1 2 (A k × B l ) ⊆ L 2 (A k × B l

) be a linear span of the set consisting of three orthogonal polynomials

S 00 kl (x, y) = 1, S 10 kl (x, y) = x − x k , S 01 kl (x, y) = y − y l . Let I ∈ L 2 ([0, M] × [0, N]), and F 1 kl be the orthogonal pro- jection of I| [x k−1 ,x k+1 ]×[y l−1 ,y l+1 ] on subspace L 1 2 (A k × B l ), k = 0, . . . , m, l = 0, . . . , n.

We say that matrix

F 1 mn [I] = (F 1 kl ), k = 0, . . . , m, l = 0, . . . , n, is the F 1 -transform of I with respect to {A k × B l | k = 0, . . . , m, l = 0, . . . , n}, and F 1 kl is the corresponding F 1 - transform component. 1 L 2 (A k ) is a Hilbert space of square-integrable functions f : [x k−1 , x k+1 ] → R with the weighted inner product f , g k given by f , g k = x k+1 x k−1 f (x)g(x)A k (x)dx,(3)

where the weight function is equal to A k .

The F 1 -transform components of I are linear polynomials in the form

F 1 kl (x, y) = c 00 kl + c 10 kl (x − x k ) + c 01 kl (y − y l ),(4)

where the coefficients are given by

c 00 kl = ∑ N y=0 ∑ M x=0 I(x, y)A k (x)B l (y) ∑ N y=0 ∑ M x=0 A k (x)B l (y) , c 10 kl = ∑ N y=0 ∑ M x=0 I(x, y)(x − x k )A k (x)B l (y) ∑ N y=0 ∑ M x=0 (x − x k ) 2 A k (x)B l (y) , c 01 kl = ∑ N y=0 ∑ M x=0 I(x, y)(y − y l )A k (x)B l (y) ∑ N y=0 ∑ M x=0 (y − y l ) 2 A k (x)B l (y)

.

(5)

F-Transform Image Inpainting

In [12], the technique of F-transforms was proposed for the inpainting. It uses two steps: direct and inverse of the 0th-degree F-transform. The direct step is described in the previous section whereas the inverse is as follows

O(x, y) = m ∑ k=0 n ∑ l=0 F 0 kl A k (x)B l (y),(6)

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 [12].

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:

F 0 kl = ∑ N y=0 ∑ M x=0 I(x, y)S(x, y)A k (x)B l (y) ∑ N y=0 ∑ M x=0 S(x, y)A k (x)B l (y)

.

This approach works well for photos as was shown in [13,15,12,9]. For cartoon images, the quality of reconstruction is not sufficient because of the isotropic nature of the algorithm. The problem is that edges are not taken into consideration during the computation.

Cartoon Images

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.

Mathematical Morphology

Application of mathematical morphology [14] is an important step in the proposed method. Let us give a short description of this technique.

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.

Erosion

The erosion is defined as follows

I T = {z ∈ [0, M] × [0, N]|T z ⊆ I},

where T is a structuring element and z is a translation vector. Operator of binary erosion is in fact a test whether image I contains areas like T .

Dilation

The dilation is defined as follows

I ⊕ T = t∈T I t ,

where T is a structuring element and I t is the translation of I by t.

Closing

Operator of closing is the erosion of dilation defined as follows

I • T = (I ⊕ T ) T.

The effect of binary closing is in filling small holes and imperfections in the image I.

Novel Inpainting Technique

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 F 0 -transform components as it is shown below

F 0 kl = ∑ N y=0 ∑ M x=0 I(x, y)S(x, y)V (x, y)A k (x)B l (y) ∑ N y=0 ∑ M x=0 S(x, y)V (x, y)A k (x)B l (y)

.

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. Comment: At this step, we compute coefficients c 00 , c 10 , c 01 of I F 1 -transform components in accordance with (5). The output for the input in Fig. 4 is in Fig. 5. 2) Upscale c 10 and c 01 to the size of image I and convert them to gray-scale.

3) Update c 01 and c 10 by subtracting mask S from them.

Comment: Performing this update we eliminate false edges. Illustration is in Fig. 6.

4) Make shifted copies of c 01 and c 10 .

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 c 01 to the left and c 10 to the up. Doing this, we restrict horizontal and vertical edges. 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 V g and V c and subtract mask from both. Turn V g and V c to binary images and apply morphological closing.

Image V g represents edges of the I whereas V c the rest. Image V g contains holes because of the mask subtraction. By closing, we fill the holes. Illustration of this step is in Fig. 9. The intersections determine places on the edge area which are damaged. Let us name this intersection S g . Illustration is in Fig. 10. 10) Use S g as a mask and V g as an valid pixels set for edge reconstruction. Use S − S g as a mask and V c 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.

Examples and Comparison

Let us illustrate the proposed inpainting algorithm side by side with original technique based on F-transform. The ), e) and h) were reconstructed using the original technique and images c), f) and i) were reconstructed using the proposed one.

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 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.

Conclusion

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 [12].

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 F 1 -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. We illustrated our technique on the two sets of images and compared with original one.