# Generating Suitable Basic Functions Used in Image Reconstruction by F-Transform

Authors: Pavel Vlašánek
Journal: Advances in Fuzzy Systems
 (2013)

---

## Abstract

Image reconstruction technique based on F-transform uses clearly defined basic functions. These functions have strong impact on the quality of reconstruction. We can use some predefined shape and radius, but also we can create a new one from the scratch. The aim of this paper is to analyze the creating process and based on that find best basic function for input set of damaged testing images.


---

## Body

## 1. Introduction

Image reconstruction aims at recovering damaged parts. In real situation this damage can be caused by various sources on various surfaces. Input information has to be digitalized as a first step and after that divided on damaged and nondamaged parts. Typical situation lays on photography. We can distinguish among many types of damage like stains, scratches, text, or noise. We can say that every kind of damage covers typical way of damaging process. Unwanted time or date stamp is covered bytext. Scratches, cracks, and folds are covered by inpaint. These are shown in Figure 1 which includes also noise.(a) Inpaint damage; (b) text damage; (c) noise damage.
(a)
(b)
(c)Target of reconstruction is removing damaged parts from input image and replacing them by the parts with recomputed values. These values are computed from the neighborhood ones. The technique mentioned in this paper is based on F-transform which brings particular way of valuation neighborhood pixels and their usage in the computation [1, 2]. Other methods [3, 4] differ by the choice at the technique.In this paper, we will focus on the valuation part of the computation. Quality of reconstruction will be measured by RMSE value (RMSE stands for the root mean square error). In Figure2 you can see damaged input images and reconstructed ones with usage of the ideal basic function described later. We will analyse influence of changing parameter on target quality.(a) Original image; (b) damaged image; (c) reconstructed image.
(a)
(b)
(c)


## 2. F-Transform

In image reconstruction, a discrete version of the F-transform is used. Details can be seen in [5, 6]. In this section two-dimensional (2D) variant and also conditions for proper functioning will be briefly introduced.


### 2.1. Fuzzy Partition with Ruspini Condition

Letx1<⋯<xn be fixed nodes within [a,b] such that x1=a, xn=b and n≥2. We say that the fuzzy sets A1,…,An, identified with their membership functions defined on [a,b], establish a fuzzy partition with Ruspini condition of [a,b] if they fulfill the following conditions for k=1,…,n:(1)
Ak:[a,b]→[0,1],  Ak(xk)=1;(2)
Ak(x)=0 if x∉(xk-1,xk+1), where for uniformity of notation, we set x0=a and xn+1=b;(3)
Ak(x) is continuous;(4)
Ak(x), for k=2,…,n, increases on [xk-1,xk], and Ak(x), for k=1,…,n-1, strictly decreases on [xk,xk+1];(5)
for allx∈[a,b],
(1)∑k=1n‍Ak(x)=1.The condition (1) is known as the Ruspini condition. The membership functions A1,…,An are called basic functions. A point x∈[a,b] is covered by basic function Ak if Ak(x)>0.


### 2.2. Shape of the Basic Function

The shape of the basic functions is not predetermined, and therefore, it can be chosen according to additional requirements (e.g., smoothness). Let us give examples of various fuzzy partitions with the Ruspini condition. In Figure3, two such partitions with triangular and cosine basic functions are shown. The formulas given below represent generic fuzzy partitions with the Ruspini condition and triangular functions:
(2)A1(x)={1-(x-x1)h1,x∈[x1,x2],0,otherwise,Ak(x)={(x-xk-1)hk-1,x∈[xk-1,xk],1-(x-xk)hk,x∈[xk,xk+1],0,otherwise,An(x)={(x-xn-1)hn-1,x∈[xn-1,xn],0,otherwise,
where k=2,…,n-1 and hk=xk+1-xk.(a) Ruspini partitions with triangular basic function; (b) Ruspini partitions with cosine basic function.
(a)
(b)We say that a Ruspini partition of[a,b] ish-uniform if its nodes x1,…,xn, where n≥3, are h-equidistant; that is, xk=a+h(k-1), for k=1,…,n, where h=(b-a)/(n-1), and two additional properties are met:(6)
Ak(xk-x)=Ak(xk+x), for all x∈[0,h], k=2,…,n-1;(7)
Ak(x)=Ak-1(x-h), for all k=2,…,n-1 and x∈[xk,xk+1], and Ak+1(x)=Ak(x-h), for all k=2,…,n-1 and x∈[xk,xk+1].Anh-uniform fuzzy partition of [a,b] can be determined by the so called generating functionA0:[-1,1]→[0,1], which is assumed to be even(The function A0:[-1,1]→ℝ is even if for all x∈[0,1],  A0(-x)=A0(x)), continuous, have a bell shape, and fulfill A0(0)=1. Basic functions Ak of an h-uniform fuzzy partition with generating function A0 are shifted copies of A0 in the sense that
(3)A1(x)={A0(x-x1h),x∈[x1,x2],0,otherwise,
and for k=2,…,n-1,
(4)Ak(x)={A0(x-xkh),x∈[xk-1,xk+1],0,otherwise,An(x)={A0(x-xnh),x∈[xn-1,xn],0,otherwise.As an example, we notice that the functionA0(x)=1-|x| is a generating function for any h-uniform triangular partition. In the sequel, we will be using h-uniform fuzzy partitions only and refer to h as to a radius of partition [7].


### 2.3. Discrete 2D F-Transform

We say that then×m-matrix of real numbers [Ukl] is called the (discrete) F-transform ofuwith respect to {A1,…,An} and {B1,…,Bm} if for all k=1,…,n,l=1,…,m,
(5)Ukl=∑j=1M‍∑i=1N‍u(pi,qj)Ak(pi)Bl(qj)∑j=1M‍∑i=1N‍Ak(pi)Bl(qj).The elementsUkl are called components of the F-transform.Theinverse F-transform is defined as follows:
(6)u^(i,j)=∑k=1n‍∑l=1m‍UklAk(i)Bl(j).We use discrete basic functionsAk and Bl. Our results show that sufficient image reconstruction is enough to use maximal radius 4. Discrete basic function with respect to Ruspini condition is building on top of template in Figure 4.Figure 4
Template for basic function definition.You can see white squares in Figure4. These squares can be marked as parts of the basic function. One marked per column. After that is automatically computed mirrored part of the basic function as can be seen in Figure 5. We choose y=4 for the column a. Value in column 10 is the same, and because of Ruspini condition, values in columns 5 and 7 are easily computable as
(7)f(y5)=1-f(ya),f(y7)=1-f(ya)=f(y5).(a) Result after selection of fourth pixel ina column; (b) result after selection of fifth pixel in b column.
(a)
(b)Because of using Ruspini condition, we can use copies of the basic function for covering the whole range. Height of the template determines valuesf(y) on the y axis. For better usability we choose value 0 for first row, 1 for last one, and twice 0.5 on the middle. Two basic functions with marked values can be seen in Figure 6.Figure 6
Template for basic function definition.The overlapping part of basic functions have functional values equal 1 in each column. For better visualization, black vertical lines are also plotted.


## 2.1. Fuzzy Partition with Ruspini Condition

Letx1<⋯<xn be fixed nodes within [a,b] such that x1=a, xn=b and n≥2. We say that the fuzzy sets A1,…,An, identified with their membership functions defined on [a,b], establish a fuzzy partition with Ruspini condition of [a,b] if they fulfill the following conditions for k=1,…,n:(1)
Ak:[a,b]→[0,1],  Ak(xk)=1;(2)
Ak(x)=0 if x∉(xk-1,xk+1), where for uniformity of notation, we set x0=a and xn+1=b;(3)
Ak(x) is continuous;(4)
Ak(x), for k=2,…,n, increases on [xk-1,xk], and Ak(x), for k=1,…,n-1, strictly decreases on [xk,xk+1];(5)
for allx∈[a,b],
(1)∑k=1n‍Ak(x)=1.The condition (1) is known as the Ruspini condition. The membership functions A1,…,An are called basic functions. A point x∈[a,b] is covered by basic function Ak if Ak(x)>0.


## 2.2. Shape of the Basic Function

The shape of the basic functions is not predetermined, and therefore, it can be chosen according to additional requirements (e.g., smoothness). Let us give examples of various fuzzy partitions with the Ruspini condition. In Figure3, two such partitions with triangular and cosine basic functions are shown. The formulas given below represent generic fuzzy partitions with the Ruspini condition and triangular functions:
(2)A1(x)={1-(x-x1)h1,x∈[x1,x2],0,otherwise,Ak(x)={(x-xk-1)hk-1,x∈[xk-1,xk],1-(x-xk)hk,x∈[xk,xk+1],0,otherwise,An(x)={(x-xn-1)hn-1,x∈[xn-1,xn],0,otherwise,
where k=2,…,n-1 and hk=xk+1-xk.(a) Ruspini partitions with triangular basic function; (b) Ruspini partitions with cosine basic function.
(a)
(b)We say that a Ruspini partition of[a,b] ish-uniform if its nodes x1,…,xn, where n≥3, are h-equidistant; that is, xk=a+h(k-1), for k=1,…,n, where h=(b-a)/(n-1), and two additional properties are met:(6)
Ak(xk-x)=Ak(xk+x), for all x∈[0,h], k=2,…,n-1;(7)
Ak(x)=Ak-1(x-h), for all k=2,…,n-1 and x∈[xk,xk+1], and Ak+1(x)=Ak(x-h), for all k=2,…,n-1 and x∈[xk,xk+1].Anh-uniform fuzzy partition of [a,b] can be determined by the so called generating functionA0:[-1,1]→[0,1], which is assumed to be even(The function A0:[-1,1]→ℝ is even if for all x∈[0,1],  A0(-x)=A0(x)), continuous, have a bell shape, and fulfill A0(0)=1. Basic functions Ak of an h-uniform fuzzy partition with generating function A0 are shifted copies of A0 in the sense that
(3)A1(x)={A0(x-x1h),x∈[x1,x2],0,otherwise,
and for k=2,…,n-1,
(4)Ak(x)={A0(x-xkh),x∈[xk-1,xk+1],0,otherwise,An(x)={A0(x-xnh),x∈[xn-1,xn],0,otherwise.As an example, we notice that the functionA0(x)=1-|x| is a generating function for any h-uniform triangular partition. In the sequel, we will be using h-uniform fuzzy partitions only and refer to h as to a radius of partition [7].


## 2.3. Discrete 2D F-Transform

We say that then×m-matrix of real numbers [Ukl] is called the (discrete) F-transform ofuwith respect to {A1,…,An} and {B1,…,Bm} if for all k=1,…,n,l=1,…,m,
(5)Ukl=∑j=1M‍∑i=1N‍u(pi,qj)Ak(pi)Bl(qj)∑j=1M‍∑i=1N‍Ak(pi)Bl(qj).The elementsUkl are called components of the F-transform.Theinverse F-transform is defined as follows:
(6)u^(i,j)=∑k=1n‍∑l=1m‍UklAk(i)Bl(j).We use discrete basic functionsAk and Bl. Our results show that sufficient image reconstruction is enough to use maximal radius 4. Discrete basic function with respect to Ruspini condition is building on top of template in Figure 4.Figure 4
Template for basic function definition.You can see white squares in Figure4. These squares can be marked as parts of the basic function. One marked per column. After that is automatically computed mirrored part of the basic function as can be seen in Figure 5. We choose y=4 for the column a. Value in column 10 is the same, and because of Ruspini condition, values in columns 5 and 7 are easily computable as
(7)f(y5)=1-f(ya),f(y7)=1-f(ya)=f(y5).(a) Result after selection of fourth pixel ina column; (b) result after selection of fifth pixel in b column.
(a)
(b)Because of using Ruspini condition, we can use copies of the basic function for covering the whole range. Height of the template determines valuesf(y) on the y axis. For better usability we choose value 0 for first row, 1 for last one, and twice 0.5 on the middle. Two basic functions with marked values can be seen in Figure 6.Figure 6
Template for basic function definition.The overlapping part of basic functions have functional values equal 1 in each column. For better visualization, black vertical lines are also plotted.


## 3. Influence of Basic Functions

Shapes of the basic functions can benondecreasing, oscillating, or nonincreasing. Differences and influences on computation are described in [8]. We choose basic functions with radius 2 in the first step of reconstruction and radius 4 in the second step because of fully sufficient usage on the input set of testing images. In this paper, we focus on building shape of basic function step by step based on results provided by RMSE. We identified two ways of this process which will be demonstrated on template in Figure 4 where max=6.Column by Column. Find the best value for current column and continue with next column:(1)
choose radiusr=2,(2)
choose active column asc=“a,”(3)
choose current row asy=1,(4)
based on those values create a basic function by mirroring and with respect to Ruspini condition formula (7),(5)
use the basic function for image reconstruction,(6)
compare reconstructed image with original undamaged one by RMSE,(7)
ify=max, then r=4, c=“b” and continue by step 3,(8)
change current row asy=y+1,(9)
continue by step 4.Radius by Radius. Find the best value for current radius and continue with next radius: (1)
choose current radius asr=2,(2)
choose current column asc=“a,”(3)
choose current row asy=1,(4)
based on those values create a basic function,(5)
use the basic function for image reconstruction,(6)
compare reconstructed image with the original undamaged by RMSE,(7)
ify=max and r=4, then c=“b” and continue by step 3,(8)
ify=max, then r=4 and continue by step 3,(9)
choose current row asy=y+1,(10)
continue by step 4.First waycolumn by column is computed in Table 1. You can see that there is for column a best RMSE value for y=6. It means that we choose sixth row for column a. Next column b is the best RMSE value in row y=5 for the Lena and Nature images and y=4 for the Picture image. We choose basic function with values y=6 for column a and y=5 for column b. This function is in Figure 8.Table 1
RMSE values of thecolumn by column basic function creation.
y
a
b
a
b
a
b
Lena
Picture
Nature
1
62.99
5.16
46.72
4.01
71.25
7.55
2
49.99
5.04
36.63
3.89
56.39
7.39
3
49.98
4.97
36.62
3.82
56.37
7.30
4
49.97
4.93
36.62
3.79
56.36
7.27
5
49.97
4.92
36.61
3.80
56.35
7.27
6
49.96
4.95
36.61
3.84
56.35
7.32Second way of basic function creationradius by radius is computed in Table 2. From the table comes that the best value is y=2 for a and y=5 for column b. This basic function is shown in Figure 7.Table 2
RMSE values of theradius by radius basic function creation.
a
/
b
1
2
3
4
5
6
Lena
1
6.12
5.71
5.58
5.51
5.50
5.52
2
5.16
4.97
4.85
4.79
4.78
4.81
3
5.12
4.96
4.86
4.81
4.80
4.83
4
5.11
4.97
4.88
4.83
4.83
4.86
5
5.13
5.00
4.92
4.87
4.87
4.90
6
5.16
5.04
5.97
4.93
4.92
4.95
Picture
1
4.93
4.32
4.21
4.16
4.15
4.19
2
3.93
3.76
3.65
3.61
3.61
3.65
3
3.91
3.76
3.67
3.63
3.64
3.68
4
3.92
3.79
3.71
3.67
3.68
3.72
5
3.96
3.83
3.76
3.73
3.73
3.77
6
4.01
3.89
3.82
3.80
3.80
3.84
Nature
1
8.50
7.68
7.45
7.33
7.30
7.33
2
7.63
7.33
7.16
7.07
7.06
7.10
3
7.53
7.30
7.15
7.09
7.09
7.13
4
7.50
7.30
7.18
7.13
7.14
7.19
5
7.51
7.34
7.23
7.19
7.20
7.25
6
7.55
7.39
7.30
7.27
7.27
7.32(a) Basic function for radius2; (b) basic function for radius 4.
(a)
(b)(a) Basic function for radius2; (b) basic function for radius 4.
(a)
(b)


## 4. Conclusion

As a result we can say that step by step process converges to oscillating or linear shape.Column by column way is the best solution oscillating basic function. Value y=6 for column a and y=5 for column b provides RMSE values 4.92 for Lena, 3.80 for Picture, and 7.27 for Nature. Because of very close results for Picture image between b=4 and b=5, we choose value b=5 for all of them. Radius by radius is the best linear function with y=2 for column a and y=5 for column b. For Lena RMSE is equal to 4.78, for Picture is equal to 3.61, and for Nature is equal to 7.06.



---

*Source: 593694-2013-09-11.xml*