F-Transform

Abstract

The theory of the F-transform is presented and discussed from the perspective of the latest developments and applications. Various fuzzy partitions are considered. The definition of the F-transform is given with respect to a generalized fuzzy partition, and the main properties of the F-transform are listed. The applications to image processing, namely image compression, fusion and edge detection, are discussed with sufficient technical details.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Fuzzy Modeling

Fuzzy modeling is still regarded as a modern technique with a nonclassical background. The goal of this chapter is to bridge standard mathematical methods and methods for the construction of fuzzy approximation models. We will present the theory of the fuzzy transform (the F -transform), which was introduced in [1] for the purpose of encompassing both classical (usually, integral) transforms and approximation models based on fuzzy IF–THEN rules (fuzzy approximation models). We start with an informal characterization of integral transforms, and from this discussion, we examine the similarities and differences among integral transforms, the F-transform, and fuzzy approximation models. An integral transform is performed using some kernel. The kernel is represented by a function of two variables and can be understood as a collection of local factors or closeness areas around elements of an original space. Each factor is then assigned an average value of a transforming object (usually, a function). Consequently, the transformed object is a new function defined on a space of local factors. The F-transform can be implicitly characterized by a discrete kernel that is associated with a finite collection of fuzzy subsets (local factors or closeness areas around chosen nodes) of an original space. We say that this collection establishes a fuzzy partition of the space. Then, similar to integral transforms, the F-transform assigns an average value of a transforming object to each fuzzy subset from the fuzzy partition of the space. Consequently, the F-transformed object is a finite vector of average values.

Similar to the F-transform, a fuzzy approximation model can also be implicitly characterized by a discrete kernel that establishes a fuzzy partition of an original space. Each element of the established fuzzy partition is a fuzzy set in the IF part (antecedent) of the respective fuzzy IF–THEN rule. The rule characterizes a correspondence between an antecedent and an average value of a transforming object (singleton model) or a fuzzy subset of a space of object values (fuzzy set model).

To emphasize the differences among integral transforms, the F-transform, and fuzzy approximation models, we note that the last two are actually finite collections of local descriptions of a considered object. Each collection produces a global description of the considered object in the form of the direct F-transform or the system of fuzzy IF–THEN rules.

The idea of producing collections of local descriptions by fuzzy IF–THEN rules originates from the early works of Zadeh [2, 3, 4, 5] and from the Takagi–Sugeno [6] approximation models.

Similar to the conventional integral transforms (the Fourier and Laplace transforms, for example), the F-transform performs a transformation of an original universe of functions into a universe of their skeleton models (vectors of F-transform components) for which further computations are easier (see, e. g., an application to the initial value problem with fuzzy initial conditions [7]). In this respect, the F-transform can be as useful in applications as traditional transforms (see applications to image compression [8, 9] and time series processing [10, 11, 12, 13, 14], for example). Moreover, sometimes the F-transform can be more efficient than its counterparts; see the details below.

The structure of this chapter is as follows. In Sect. 7.2, we consider various fuzzy partitions: uniform and with and without the Ruspini condition, among others; in Sect. 7.3, definitions of the F-transforms (direct and inverse) and their main properties are considered; in Sect. 7.4, the discrete F-transform is defined; in Sect. 7.5, the direct and inverse F-transform of a function of two variables is introduced; in Sect. 7.6, a higher degree F-transform is considered; in Sect. 7.7, applications of the F-transform and F¹-transform to image processing are discussed.

2 Fuzzy Partitions

In this section, we present a short overview of various fuzzy partitions of a universe in which transforming objects (functions) are defined. As we learned from Sect. 7.1, a fuzzy partition is a finite collection of fuzzy subsets of the universe that determines a discrete kernel and thus a respective transform. Therefore, we have as many F-transforms as fuzzy partitions.

2.1 Fuzzy Partition with the Ruspini Condition

The fuzzy partition with the Ruspini condition (7.1) (simply, Ruspini partition) was introduced in [1]. This condition implies normality of the respective fuzzy partition, i. e., the partition-of-unity. It then leads to a simplified version of the inverse F-transform. In later publications [15, 16], the Ruspini condition was weakened to obtain an additional degree of freedom and a better approximation by the inverse F-transform.

Definition 7.1

Let $x_1<\mathrm{\cdots }<x_n$ be fixed nodes within $[a,b]$ such that $x_1=a,x_n=b$ and $n\ge 2$. We say that the fuzzy sets $A_1,\mathrm{\dots },A_n$, identified with their membership functions defined on $[a,b]$, establish a Ruspini partition of $[a,b]$ if they fulfill the following conditions for $k=1,\mathrm{\dots },n$:

• 1. $A_k:[a,b]\to [0,1],A_k\left(x_k\right)=1$

• 2. $A_k\left(x\right)=0$ if $x\notin (x_{k-1},x_{k+1})$, where for uniformity of notation, we set $x_0=a$ and $x_{n+1}=b$

• 3. $A_k\left(x\right)$ is continuous

• 4. $A_k\left(x\right)$, for $k=2,\mathrm{\dots },n$, strictly increases on $[x_{k-1},x_k]$ and $A_k\left(x\right)$ for $k=1,\mathrm{\dots },n-1$, strictly decreases on $[x_k,x_{k+1}]$

• 5. for all $x\in [a,b]$,

  $${\sum _{k=1}}^n{A}_k\left(x\right)=\mathrm{1\hspace{0.33em}.}$$

  (7.1)

The condition (7.1) is known as the Ruspini condition. The membership functions $A_1,\mathrm{\dots },A_n$ are called the basic functions. A point $x\in [a,b]$ is covered by the basic function A _k if $A_k\left(x\right)>0$.

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 Fig. 7.1, two such partitions with triangular and cosine basic functions are shown. The following formulas represent generic fuzzy partitions with the Ruspini condition and triangular functions

$$\begin{array}{rl}{A}_1\left(x\right)& =\mathrm{\{}\begin{array}{rl}1-\frac{(x-x_1)}{h_1},& x\in [x_1,x_2],\\ 0,& \text{otherwise},\end{array}\mathrm{.}\\ A_k\left(x\right)& =\mathrm{\{}\begin{array}{rl}\frac{(x-x_{k-1})}{h_{k-1}},& x\in [x_{k-1},x_k],\\ 1-\frac{(x-x_k)}{h_k},& x\in [x_k,x_{k+1}],\\ 0,& \text{otherwise},\end{array}\mathrm{.}\\ A_n\left(x\right)& =\mathrm{\{}\begin{array}{rl}\frac{(x-x_{n-1})}{h_{n-1}},& x\in [x_{n-1},x_n],\\ 0,& \text{otherwise},\end{array}\mathrm{.}\end{array}$$

where $k=2,\mathrm{\dots }n-1$ and $h_k=x_{k+1}-x_k$.

We say that a Ruspini partition of $[a,b]$ is h-uniform if its nodes $x_1,\mathrm{\dots },x_n$, where $n\ge 3$, are equidistant, i. e., $x_k=a+h(k-1)$, for $k=1,\mathrm{\dots },n$, where $h=(b-a)/(n-1)$, and the two additional properties are met:

• 6. $A_k(x_k-x)=A_k(x_k+x)$, for all $x\in [0,h]$, $k=2,\mathrm{\dots },n-1$,

• 7. $A_k\left(x\right)=A_{k-1}(x-h)$, for all $k=2,\mathrm{\dots },n-1$ and $x\in [x_k,x_{k+1}]$, and $A_{k+1}\left(x\right)=A_k(x-h)$, for all $k=2,\mathrm{\dots },n-1$ and $x\in [x_k,x_{k+1}]$.

2.2 Fuzzy Partitions with the Generalized Ruspini Condition

Fuzzy partitions with the generalized Ruspini condition were introduced in [15]. The generalization consists in replacing partition-of-unity (7.1) by fuzzy r-partition (7.2). This type of partition was investigated in [15, 17], where the focus was on smoothing or filtering data using the inverse F-transform. The following definition is taken from [15].

Definition 7.2

Let $r\ge 1$ and $n\ge 2$ be fixed integers such that $r\le n$. Let $a=x_1<\mathrm{\cdots }<x_n=b$ be nodes within $[a,b]$, and let $x_{1-r}<\mathrm{\cdots }<x_0<a$ and $b<x_{n+1}<\mathrm{\cdots }<x_{n+r}$ be nodes outside of $[a,b]$. A fuzzy r-partition of $[a,b]$ is a family of $n+2r-2$ continuous, normal, convex fuzzy sets

$${A^{\left(r\right)}}_{2-r},\mathrm{\dots },{A^{\left(r\right)}}_1,\mathrm{\dots },{A^{\left(r\right)}}_n,\mathrm{\dots },{A^{\left(r\right)}}_{n+r-1}$$

such that the following conditions are fulfilled:

• 1. For $k=1,\mathrm{\dots },n$, ${A^{\left(r\right)}}_k$ is a continuous function on $[a,b]$ such that ${A^{\left(r\right)}}_k\left(x_k\right)=1$ and ${A^{\left(r\right)}}_k\left(x\right)=0$ for $x\notin [max(x_{k-r},a),min(x_{k+r},b\left)\right]$

• 2. For $k=1,\mathrm{\dots },n$, ${A^{\left(r\right)}}_k$ is increasing on $[max(x_{k-r},a),x_k]$ and decreasing on $[x_k,min(x_{k+r},b\left)\right]$

• 3. For $k=-r+2,\mathrm{\dots },0$, ${A^{\left(r\right)}}_k$ is decreasing on $[max(x_k,a),x_{k+r}]$

• 4. For $k=n+1,\mathrm{\dots },n+r-1$, ${A^{\left(r\right)}}_k$ is increasing on $[x_{k-r},min(x_k,b\left)\right]$

• 5. For all $x\in [a,b]$, the following partition-of-r condition holds

  $${\sum _{k=-r+2}}^{n+r-1}{A^{\left(r\right)}}_k\left(x\right)=r.$$

  (7.2)

If r = 1, then a fuzzy r-partition in the sense of Definition 7.2 becomes the standard fuzzy partition in the sense of Definition 7.1, i. e., the partition-of-unity. In Fig. 7.2, the fuzzy 2-partition with triangular basic functions is shown.

Fig. 7.1 a,b

Two Ruspini partitions with triangular  (a) and cosine basic functions (b)

Fig. 7.2

An example of a fuzzy 2-partition with triangular basic functions

2.3 Generalized Fuzzy Partitions

A generalized fuzzy partition appeared in [16] in connection with the notion of the higher degree F-transform. Its even weaker version was implicitly introduced in [18] with the purpose of meeting the requirements of image compression. We summarize both these notions and propose the following definition.

Definition 7.3

Let $[a,b]$ be an interval on $\mathbb{R}$, $n\ge 2$, and let $x_0,x_1,\mathrm{\dots },x_n,x_{n+1}$ be nodes such that

$$a=x_0\le x_1<\mathrm{\cdots }<x_n\le x_{n+1}=b.$$

We say that the fuzzy sets

$$A_1,\mathrm{\dots },A_n:[a,b]\to [0,1]$$

constitute a generalized fuzzy partition of $[a,b]$ if for every $k=1,\mathrm{\dots },n$ there exist ${h_k}^{\prime },{h_k}^{\prime \prime }\ge 0$ such that

$${h_k}^{\prime }+{h_k}^{\prime \prime }>0,[x_k-{h_k}^{\prime },x_k+{h_k}^{\prime \prime }]\subseteq [a,b]$$

and the following three conditions are fulfilled:

• 1. (locality) – $A_k\left(x\right)>0$ if $x\in (x_k-{h_k}^{\prime },x_k+{h_k}^{\prime \prime })$, and $A_k\left(x\right)=0$ if $x\in [a,b]\setminus [x_k-{h_k}^{\prime },x_k+{h_k}^{\prime \prime }]$

• 2. (continuity) – A _k is continuous on $[x_k-{h_k}^{\prime },x_k+{h_k}^{\prime \prime }]$

• 3. (covering) – for $x\in [a,b]$, ${{\sum }_{k=1}}^n{A}_k\left(x\right)>0$.

It is important to remark that by conditions of locality and continuity,

$${{\int }_a}^b{A}_k\left(x\right)\text{d}x>\mathrm{0\hspace{0.33em}.}$$

An $(h,h^{\prime })$-uniform generalized fuzzy partition of $[a,b]$ is defined for equidistant nodes

$$x_k=a+h(k-1),k=1,\mathrm{\dots },n,$$

where $h=(b-a)/(n-1)$, $h^{\prime }>h/2$ and two additional properties are satisfied:

• 4. $A_k\left(x\right)=A_{k-1}(x-h)$ for all $k=2,\mathrm{\dots },n-1$ and $x\in [x_k,x_{k+1}]$, and $A_{k+1}\left(x\right)=A_k(x-h)$ for all $k=2,\mathrm{\dots },n-1$ and $x\in [x_k,x_{k+1}]$.

• 5. ${h_1}^{\prime }={h_n}^{\prime \prime }=0$, ${h_1}^{\prime \prime }={h_2}^{\prime }=\mathrm{\cdots }={h_{n-1}}^{\prime \prime }={h_n}^{\prime }=h^{\prime }$ and for all $k=2,\mathrm{\dots },n-1$ and all $x\in [0,h^{\prime }]$, $A_k(x_k-x)=A_k(x_k+x)$.

An $(h,h^{\prime })$-uniform generalized fuzzy partition of $[a,b]$ can also be defined using the generating function $A_0:[-1,1]\to [0,1]$, which is assumed to be even, continuous, and positive everywhere except for on boundaries, where it vanishes. (The function $A_0:[-1,1]\to \mathbb{R}$ is even if for all $x\in [0,1]$, $A_0(-x)=A_0\left(x\right)$.) Then, basic functions A _k of an $(h,h^{\prime })$-uniform generalized fuzzy partition are shifted copies of A ₀ in the sense that

$$A_1\left(x\right)=\mathrm{\{}\begin{array}{ll}{A}_0\mathrm{(}\frac{x-x_1}{h^{\prime }}\mathrm{)},& x\in [x_1,x_1+h^{\prime }],\\ 0,& \text{otherwise},\end{array}\mathrm{.}$$

and for $k=2,\mathrm{\dots },n-1$,

$$\begin{array}{rl}& A_k\left(x\right)=\mathrm{\{}\begin{array}{ll}{A}_0\mathrm{(}{\displaystyle \frac{x-x_k}{h^{\prime }}}\mathrm{)},& x\in [x_k-h^{\prime },x_k+h^{\prime }],\\ 0,& \text{otherwise},\end{array}\mathrm{.},\\ & A_n\left(x\right)=\mathrm{\{}\begin{array}{ll}{A}_0\mathrm{(}{\displaystyle \frac{x-x_n}{h^{\prime }}}\mathrm{)},& x\in [x_n-h^{\prime },x_n],\\ 0,& \text{otherwise}.\end{array}\mathrm{.}\end{array}$$

(7.3)

As an example, we note that the function $A_0\left(x\right)=1-\left|x\right|$ is a generating function for all uniform triangular partitions. The difference between them is in parameters h and $h^{\prime }$. An $(h,h)$-uniform generalized fuzzy partition is simply called an h-uniform one (Fig. 7.3 ).

Fig. 7.3

Generating function A₀ of an h-uniform generalized fuzzy partition (after [19])

Remark 7.1

A generalized fuzzy partition can also be considered in connection with radial membership functions; see [20]. In this case, every basic function has a generic representation in terms of a kernel $\phi :{\mathbb{R}}^{+}\to \mathbb{R}$ such that

$$A_k\left(x\right)=\phi (\parallel x-x_k{\parallel }_2),k=1,\mathrm{\dots },n.$$

3 Fuzzy Transform

The F-transform establishes a correspondence between a set of continuous functions on an interval of real numbers and the set of n-dimensional (real) vectors. Each component of the resulting vector is a weighted local mean of a corresponding function over an area covered by a corresponding basic function. The vector of the F-transform components is a simplified representation of an original function that can be used instead of the original function in many applications. Among them, let us mention applications to image compression [8, 9], image fusion, image reduction, time series processing [10, 11, 12, 13, 14], and the initial value problem with fuzzy initial conditions [7].

3.1 Direct F-Transform

In this section, we give the definition of the F-transform according to [1] and recall the main properties of it. We assume that the universe is an interval $[a,b]$ and $x_1<\mathrm{\cdots }<x_n$ are fixed nodes from $[a,b]$ such that $x_1=a$, $x_n=b$ and $n\ge 2$. Let us formally extend the set of nodes by $x_0=a$ and $x_{n+1}=b$. Let $A_1,\mathrm{\dots },A_n$ be the basic functions that form a fuzzy partition of $[a,b]$ according to Definition 7.3. Let $C\left(\right[a,b\left]\right)$ be the set of continuous functions on the interval $[a,b]$. The following definition introduces the fuzzy transform of a function $f\in C\left(\right[a,b\left]\right)$.

Definition 7.4

Let $A_1,\mathrm{\dots },A_n$ be the basic functions that form a generalized fuzzy partition of $[a,b]$ and f be any function from $C\left(\right[a,b\left]\right)$. We say that the n-tuple of real numbers $\mathbf{F}\left[f\right]=(F_1,\mathrm{\dots },F_n)$ given by

$$F_k=\frac{{{\int }_a}^{b}f\left(x\right)A_k\left(x\right)\text{d}x}{{{\int }_a}^b{A}_k\left(x\right)\text{d}x},k=1,\mathrm{\dots },n,$$

(7.4)

is the (integral) F-transform of f with respect to $A_1,\mathrm{\dots },A_n$.

The elements $F_1,\mathrm{\dots },F_n$ are called the components of the F -transform. If $A_1,\mathrm{\dots },A_n$ is an h-uniform Ruspini partition, then (7.4) may be simplified as follows,

$$F_1={\displaystyle \frac{2}{h}}{{{\displaystyle \int }}_{x_1}}^{x_2}f\left(x\right)A_1\left(x\right)\text{d}x,F_n={\displaystyle \frac{2}{h}}{{{\displaystyle \int }}_{x_{n-1}}}^{x_n}f\left(x\right)A_n\left(x\right)\text{d}x,F_k={\displaystyle \frac{1}{h}}{{{\displaystyle \int }}_{x_{k-1}}}^{x_{k+1}}f\left(x\right)A_k\left(x\right)\text{d}x,k=2,\mathrm{\dots },n-\mathrm{1\hspace{0.33em}.}$$

(7.5)

The following is a list of some properties of the F-transform of f with respect to a generalized fuzzy partition of $[a,b]$:

• (a) If for all $x\in [a,b]$, $f\left(x\right)=C$, then $F_k=C,k=1,\mathrm{\dots },n$.

• (b) If $f=\alpha g+\beta h$, then $\mathbf{F}\left[f\right]=\alpha \mathbf{F}\left[g\right]+\beta \mathbf{F}\left[h\right]$.

• (c) If $[c,d]=\left\{f\right(x)\mid x\in [a,b\left]\right\}$, then $F_k={min}_{[c,d]}{{\int }_a}^b\left(f\right(x)-y{)}^2{A}_k(x)\text{d}x$, $k=1,\mathrm{\dots },n$.

• (d) If f is twice continuously differentiable on $[a,b]$, then $F_k=f\left(x_k\right)+O\left(h^2\right),k=1,\mathrm{\dots },n$. (This is true for an h-uniform Ruspini partition of $[a,b]$ only. A similar estimation of the F-transform component F _k as a linear combination of $f(x_k-r+1),\mathrm{\dots },f\left(x_k\right),\mathrm{\dots },f(x_k+r-1)$ can be established for a fuzzy r-partition [15].)

• (e) If a generalized fuzzy partition is $(h,h^{\prime })$-uniform, then for each $k=1,\mathrm{\dots },n-1$,

  $$\left|f\right(t)-F_k|\le 2\omega (\tilde{h},f),\left|f\right(t)-F_{k+1}|\le 2\omega (\tilde{h},f),$$

  where $\tilde{h}=max(h,h^{\prime })$, $t\in [x_k,x_k+\tilde{h}]$, and

  $$\omega (\tilde{h},f)=\underset{\left|\delta \right|\le \tilde{h}}{max}\underset{x\in [a,b-\delta ]}{max}\left|f\right(x+\delta )-f(x\left)\right|.$$

  (7.6)
• (f)
  $${{\int }_a}^{b}f\left(x\right)\text{d}x=h(\frac{F_1}{2}+\frac{F_n}{2}+{\sum _{k=2}}^{n-1}{F}_k).$$

  (This is true for an h-uniform Ruspini partition of $[a,b]$ only.)

3.2 Inverse F-Transform

It is clear that an original nonconstant function f cannot be precisely reconstructed from its F-transform $\mathbf{F}\left[f\right]$ because we lose information when passing from f to $\mathbf{F}\left[f\right]$. However, the inverse F-transform $\widehat{f}$ that can be reconstructed (using the inversion formula (7.7)) approximates f in such a way that universal convergence can be established.

Definition 7.5

Let $A_1,\mathrm{\dots },A_n$ be the basic functions that form a generalized fuzzy partition of $[a,b]$ and f be a function from $C\left(\right[a,b\left]\right)$. Let $\mathbf{F}\left[f\right]=(F_1,\mathrm{\dots },F_n)$ be the F-transform of f with respect to $A_1,\mathrm{\dots },A_n$. Then, the function $\widehat{f}:[a,b]\to \mathbb{R}$ represented by

$$\widehat{f}\left(x\right)=\frac{{{\sum }_{k=1}}^n{F}_k{A}_k\left(x\right)}{{{\sum }_{k=1}}^n{A}_k\left(x\right)},$$

(7.7)

is called the inverse F -transform.

Remark 7.2

If a fuzzy partition of $[a,b]$ fulfills the generalized Ruspini condition (7.2) with $r\ge 1$, then the inversion formula (7.7) can be simplified to

$$\widehat{f}\left(x\right)=\frac{1}{r}{\sum _{k=1}}^n{F}_k{A}_k\left(x\right)$$

or to (in the case of the Ruspini partition for which r = 1)

$$\widehat{f}\left(x\right)={\sum _{k=1}}^n{F}_k{A}_k\left(x\right).$$

The following theorem demonstrates that the inverse F-transform $\widehat{f}$ can approximate a continuous function f with arbitrary precision. Thus, it explains why the F-transform has convincing applications in various fields, including image and time series processing, and data mining [21]. In Fig. 7.4, we illustrate how the inverse F-transform approximates the function $10{\text{e}}^{-(x-\pi {)}^2}$.

Fig. 7.4

The function $f\left(x\right)=10{\text{e}}^{-(x-\pi {)}^2}$ (gray) and its inverse F-transform (brown) with respect to the uniform Ruspini partition of $[0,6]$ by 29 triangular-shaped basic functions. The F-transform components are marked by small circles

Theorem 7.1

Let f be a continuous function on $[a,b]$. Then, for any $\epsilon >0$, there exist $n_{\epsilon }$ and a generalized fuzzy partition $A_1,\mathrm{\dots },A_{n_{\epsilon }}$ of $[a,b]$ such that for all $x\in [a,b]$,

$$eq8\left|f\right(x)-{\widehat{f}}_{\epsilon }(x\left)\right|\le \epsilon ,$$

(7.8)

where ${\widehat{f}}_{\epsilon }$ is the inverse F-transform of f with respect to the fuzzy partition $A_1,\mathrm{\dots },A_{n_{\epsilon }}$.

From Theorem 7.2, which is given below, we learn that for a pointwise approximation (as in Theorem 7.1), it is sufficient to compute the F-transform with respect to the simplest triangular fuzzy partition. Therefore, almost all applications of the F-transform are based on this type of partition.

Theorem 7.2

Let f be any continuous function on $[a,b]$, and let ${A^{\prime }}_1,\mathrm{\dots },{A^{\prime }}_n$ and ${A^{\prime \prime }}_1,\mathrm{\dots },{A^{\prime \prime }}_n$, for $n\ge 3$, be the basic functions that form different $(h,h^{\prime })$-uniform generalized fuzzy partitions of $[a,b]$. Let ${\widehat{f}}^{\prime }$ and ${\widehat{f}}^{\prime \prime }$ be the two inverse F-transforms of f with respect to different sets of basic functions ${A^{\prime }}_1,\mathrm{\dots },{A^{\prime }}_n$ or ${A^{\prime \prime }}_1,\mathrm{\dots },{A^{\prime \prime }}_n$. Then, for arbitrary $x\in [a,b]$,

$$\left|{\widehat{f}}^{\prime }\right(x)-{\widehat{f}}^{\prime \prime }(x\left)\right|\le 4\omega (\tilde{h},f),$$

where $h=\frac{b-a}{n-1}$, $\tilde{h}=max(h,h^{\prime })$ and $\omega (\tilde{h},f)$ is the modulus of continuity (7.6) of f on the interval $[a,b]$.

The proofs of Theorems 7.1 and 7.2 can be obtained from the respective proofs in [22, Theorems 2 and 3] after some necessary changes caused by the usage of the generalized fuzzy partition.

Below, we list some properties of the inverse F-transform $\widehat{f}$ of f that were considered and proved in [1, 15, 23]. If not specially mentioned, it is assumed that the F-transform is computed with respect to a generalized fuzzy partition of $[a,b]$:

• (a) If for all $x\in [a,b]$ ,  $f\left(x\right)=C$, then $\widehat{f}\left(x\right)=C$

• (b) If $f=\alpha g+\beta h$ , then $\widehat{f}=\alpha \widehat{g}+\beta \widehat{h}$

• (c) ${{\int }_a}^{b}f\left(x\right)\text{d}x={{\int }_a}^b\widehat{f}\left(x\right)\text{d}x$ (This is true for the fuzzy r-partition $(r\ge 1)$ of $[a,b]$ only.)

• (d) Let $A_1,\mathrm{\dots },A_n$ be an h-uniform Ruspini partition of $[a,b]$, where $h=(b-a)/(n-1)$ and n > 3. Let $s:[a,b]\to \mathbb{R}$ be a continuous function such that one of the following two conditions are fulfilled:

  • (i) s is $2h$-periodical and for all $x\in [0,h]$, $s(x_k-x)=-s(x_k+x)$, where $k=2,\mathrm{\dots },n-1$

  • (ii) s is h-periodical and ${{\int }_{x_{k-1}}}^{x_k}s\left(x\right)\text{d}x=0$, where $k=2,\mathrm{\dots },n-1$.

  Then, for $x\in [x_2,x_{n-1}]$,

  $$\widehat{f}=\widehat{f+s}.$$

The last property is known as noise removal. This phrase implies that both functions f (non-noisy) and $f+s$ (noisy) have the same inverse F-transform. The noise is represented by s and characterized by conditions (i) or (ii). We illustrate this property in Fig. 7.5.

Fig. 7.5

(a) Function $f\left(x\right)=10{\text{e}}^{-(x-\pi {)}^2}$ (gray) and its inverse F-transform (brown) with respect to the Ruspini partition given by the triangular-shaped basic functions $A_1,\mathrm{\dots },A_5$ (gray). (b) Noisy function $f+s$ (gray), where $s\left(x\right)=\sin \left(2x\right)+0.6\sin \left(8x\right)+0.3\sin \left(16x\right)$, and its inverse F-transform (brown) with respect to the same fuzzy partition . Both inverse F-transforms $\widehat{f}$ and $\widehat{f+s}$ are equal on $[x_2,x_4]$

4 Discrete F-Transform

The discrete case of the F-transform, for which an original function f is defined (may be computed) on a finite set $P=\{p_1,\mathrm{\dots },p_l\}\subseteq [a,b]$, was introduced in [1]. We will adapt the mentioned definition to the case of a generalized fuzzy partition of $[a,b]$.

We assume that the domain P of the function f is sufficiently dense with respect to the fixed partition, i. e.,

$$(\forall k)(\exists j)A_k\left(p_j\right)>\mathrm{0\hspace{0.33em}.}$$

Then, the (discrete) F-transform of f is defined as follows.

Definition 7.6

Let $A_1,\mathrm{\dots },A_n$, for n > 2, be the basic functions that form a generalized fuzzy partition of $[a,b]$, and let function f be defined on the set $P=\{p_1,\mathrm{\dots },p_l\}\subseteq [a,b]$, which is sufficiently dense with respect to the partition. We say that the n-tuple of real numbers $(F_1,\mathrm{\dots },F_n)$ is the discrete F-transform of f with respect to $A_1,\mathrm{\dots },A_n$ if

$$F_k=\frac{{{\sum }_{j=1}}^{l}f\left(p_j\right)A_k\left(p_j\right)}{{{\sum }_{j=1}}^l{A}_k\left(p_j\right)}.$$

(7.9)

It is not difficult to demonstrate that the components of the discrete F-transform have similar properties to those listed in Sect. 7.3.1.

In the discrete case, we define the inverse F-transform on the same set P on which the original function is defined.

Definition 7.7

Let $A_1,\mathrm{\dots },A_n$, for n > 2, be the basic functions that form a generalized fuzzy partition of $[a,b]$, and let function f be defined on the set $P=\{p_1,\mathrm{\dots },p_l\}\subseteq [a,b]$, which is sufficiently dense with respect to the partition. Moreover, let $\mathbf{F}\left[f\right]=(F_1,\mathrm{\dots },F_n)$ be the discrete F-transform of f w.r.t. $A_1,\mathrm{\dots },A_n$. Then, the function $\widehat{f}:P\to \mathbb{R}$ represented by

$$\widehat{f}\left(p_j\right)=\frac{{{\sum }_{k=1}}^n{F}_k{A}_k\left(p_j\right)}{{{\sum }_{k=1}}^n{A}_k\left(p_j\right)}$$

(7.10)

is the inverse discrete F -transform of f.

Remark 7.3

If a fuzzy partition of $[a,b]$ fulfills the generalized Ruspini condition (7.2) with $r\ge 1$, i. e., for all $p_j\in P$, ${{\sum }_{k=1}}^n{A}_k\left(p_j\right)=r$, then the inversion formula (7.10) can be simplified to

$$\widehat{f}\left(p_j\right)=\frac{1}{r}{\sum _{k=1}}^n{F}_k{A}_k\left(p_j\right)$$

or (in the case of Ruspini partition, i. e., r = 1) to

$$\widehat{f}\left(p_j\right)={\sum _{k=1}}^n{F}_k{A}_k\left(p_j\right).$$

Analogous to Theorem 7.1, we can show that the inverse discrete F-transform $\widehat{f}$ can approximate the original discrete function f on P with arbitrary precision [1]. Moreover, the properties (a)–(c) that are listed in Sect. 7.3.2 have valid discrete analogies.

An interesting comparison between the discrete F-transform and the least-square approximation was made in [20]. It was demonstrated that the discrete F-transform is invariant with respect to the interpolating and least-squares approximation of the set $\left\{\right(p_j,f\left(p_j\right))\mid j=1,\mathrm{\dots },l\}$. This means that the best approximation of f on P in the form of ${{\sum }_{i=1}}^n{\alpha }_i{A}_i$, where $n\le l$, has the same direct discrete F-transform as the original f.

5 F-Transforms of Functions of Two Variables

The direct and inverse F-transform of a function of two (and more) variables is a direct generalization of the case of one variable. We introduce it briefly and refer to [1] for more details.

Suppose that the universe is a rectangle $[a,b]\times [c,d]\subseteq \mathbb{R}\times \mathbb{R}$ and that $x_1<\mathrm{\cdots }<x_n$ are the fixed nodes of $[a,b]$ and $y_1<\mathrm{\cdots }<y_m$ are the fixed nodes of $[c,d]$ such that $x_1=a$, $x_n=b$, $y_1=c$, $x_m=d$ and $n,m\ge 2$. Let us formally extend the set of nodes by setting $x_0=a$, $y_0=c$, $x_{n+1}=b$, and $y_{m+1}=d$. Assume that $A_1,\mathrm{\dots },A_n$ are the basic functions that form a generalized fuzzy partition of $[a,b]$ and $B_1,\mathrm{\dots },B_m$ are basic functions that form a generalized fuzzy partition of $[c,d]$. Then, the rectangle $[a,b]\times [c,d]$ is partitioned into fuzzy sets $A_k\times B_l$ with the membership functions $(A_k\times B_l)(x,y)=A_k\left(x\right)B_l\left(y\right)$, $k=1,\mathrm{\dots },n$, $l=1,\mathrm{\dots },m$. Let $C\left(\right[a,b]\times [c,d\left]\right)$ be the set of continuous functions of two variables on the domain and $f\in C\left(\right[a,b]\times [c,d\left]\right)$.

Definition 7.8

Let $A_1,\mathrm{\dots },A_n$ be the basic functions that form a generalized fuzzy partition of $[a,b]$ and $B_1,\mathrm{\dots },B_m$ be the basic functions that form a generalized fuzzy partition of $[c,d]$. Let f be any function from $C\left(\right[a,b]\times [c,d\left]\right)$. We say that the $n\times m$-matrix of real numbers $\mathbf{F}\left[f\right]=(F_{kl}{)}_{n\times m}$ is the (integral) F-transform of f with respect to $A_1,\mathrm{\dots },A_n$ and $B_1,\mathrm{\dots },B_m$ if for each $k=1,\mathrm{\dots },n$, $l=1,\mathrm{\dots },m$,

$$F_{kl}=\frac{{{\int }_c}^d{{\int }_a}^{b}f(x,y)A_k\left(x\right)B_l\left(y\right)\text{d}x\text{d}y}{{{\int }_c}^d{{\int }_a}^b{A}_k\left(x\right)B_l\left(y\right)\text{d}x\text{d}y}.$$

(7.11)

The components F _kl  (7.11) have properties (adapted to the case of two variables) similar to those listed in Sect. 7.3.1. For example, the property (e) has the following form (we assume that $A_1,\mathrm{\dots },A_n$ form an h ₁-uniform Ruspini partition of $[a,b]$ and $B_1,\mathrm{\dots },B_m$ form an h ₂-uniform Ruspini partition of $[c,d]$)

$${{\int }_c}^d{{\int }_a}^{b}f(x,y)\text{d}x\text{d}y=\frac{h_1{h}_2}{4}\mathrm{(}{F}_{11}+F_{1m}+F_{n1}+F_{nm}\mathrm{)}+\frac{h_1{h}_2}{2}\mathrm{(}{\sum _{k=2}}^{n-1}{F}_{k1}+{\sum _{k=2}}^{n-1}{F}_{km}+{\sum _{l=2}}^{m-1}{F}_{1l}+{\sum _{l=2}}^{m-1}{F}_{nl}\mathrm{)}+h_1{h}_2{\sum _{k=2}}^{n-1}{\sum _{l=2}}^{m-1}{F}_{kl}.$$

In the discrete case, when an original function f is known only at points $(p_i,q_j)\in [a,b]\times [c,d]$, where $i=1,\mathrm{\dots },N$ and $j=1,\mathrm{\dots },M$, the (discrete) F-transform of f can be introduced in a manner analogous to the case of a function of one variable. This case is important for applications of the F-transform to image processing [18, 24, 25, 26, 8, 9].

Definition 7.9

Let a function f be given at nodes $(p_i,q_j)\in [a,b]\times [c,d]$, for which $i=1,\mathrm{\dots },N$ and $j=1,\mathrm{\dots },M$, and $A_1,\mathrm{\dots },A_n$ and $B_1,\mathrm{\dots },B_m$, where $n<N$ and $m<M$, be the basic functions that form generalized fuzzy partitions of $[a,b]$ and $[c,d]$, respectively. Suppose that sets P and Q of these nodes are sufficiently dense with respect to the chosen partitions. We say that the $n\times m$-matrix of real numbers $\mathbf{F}\left[f\right]=(F_{kl}{)}_{nm}$ is the discrete F-transform of f with respect to $A_1,\mathrm{\dots },A_n$ and $B_1,\mathrm{\dots },B_m$ if

$$F_{kl}=\frac{{{\sum }_{j=1}}^M{{\sum }_{i=1}}^{N}f(p_i,q_j)A_k\left(p_i\right)B_l\left(q_j\right)}{{{\sum }_{j=1}}^M{{\sum }_{i=1}}^N{A}_k\left(p_i\right)B_l\left(q_j\right)}$$

(7.12)

holds for all $k=1,\mathrm{\dots },n$, $l=1,\mathrm{\dots },m$.

The inverse F-transform of a function of two variables is a simple extension of (7.7). It will be given below for the continuous version of a function.

Definition 7.10

Let $A_1,\mathrm{\dots },A_n$ and $B_1,\mathrm{\dots },B_m$ be the basic functions that form generalized fuzzy partitions of $[a,b]$ and $[c,d]$, respectively. Let f be a function from $C\left(\right[a,b]\times [c,d\left]\right)$ and $\mathbf{F}\left[f\right]$ be the F-transform of f with respect to $A_1,\mathrm{\dots },A_n$ and $B_1,\mathrm{\dots },B_m$. Then, the function $\widehat{f}:[a,b]\times [c,d]\to \mathbb{R}$ represented by

$$\widehat{f}(x,y)=\frac{{{\sum }_{k=1}}^n{{\sum }_{l=1}}^m{F}_{kl}{A}_k\left(x\right)B_l\left(y\right)}{{{\sum }_{k=1}}^n{{\sum }_{l=1}}^m{A}_k\left(x\right)B_l\left(y\right)}$$

(7.13)

is called the the inverse F -transform.

Similar to the case of a function of one variable, we can prove that the inverse F-transform $\widehat{f}$ can approximate the original continuous function f with arbitrary precision, and the (adapted) properties (a)–(c), which are listed in Sect. 7.3.2, are fulfilled.

6 ${\mathit{\text{F}}}^1$-Transform

In [16], a higher degree F-transform was introduced for the purpose for advanced applications in time series and image processing [26, 27]. In this section, we give a description of the F ¹-transform, which has working applications, and refer to [16] for the F ^m-transform for which m > 1.

Throughout this section, we assume that $A_1,\mathrm{\dots },A_n$, n > 2 is an h-uniform generalized fuzzy partition of $[a,b]$ such that there exists a generating function $A_0:[-1,1]\to [0,1]$ such that for all $k=1,\mathrm{\dots },n$, A _k is defined by (7.3) (the illustration is in Fig. 7.3).

Let k be a fixed integer from $\{1,\mathrm{\dots },n\}$, and let $L_2\left(A_k\right)$ be a normed space of square-integrable functions $f:[x_{k-1},x_{k+1}]\to \mathbb{R}$, where the norm $\parallel f{\parallel }_k$ is given by

$$\parallel f{\parallel }_k=\sqrt{\frac{{{\int }_{x_{k-1}}}^{x_{k+1}}{f}^2\left(x\right)A_k\left(x\right)\text{d}x}{{{\int }_{x_{k-1}}}^{x_{k+1}}{A}_k\left(x\right)\text{d}x}}.$$

By $L_2(A_1,\mathrm{\dots },A_n)$ we denote a set of functions $f:[a,b]\to \mathbb{R}$ such that for all $k=1,\mathrm{\dots },n$, $f{|}_{[x_{k-1},x_{k+1}]}\in L_2\left(A_k\right)$, where $f{|}_{[x_{k-1},x_{k+1}]}$ is the restriction of f on $[x_{k-1},x_{k+1}]$.

For any function f from $L_2(A_1,\mathrm{\dots },A_n)$ we define the F ¹-transform of f with respect to $A_1,\mathrm{\dots },A_n$ as the vector of linear functions

$${\mathbf{F}}^1\left[f\right]=(c_{1,0}+c_{1,1}(x-x_1),\mathrm{\dots },c_{n,0}+c_{n,1}(x-x_n\left)\right),$$

(7.14)

where for every $k=1,\mathrm{\dots },n$,

$$c_{k,0}={\displaystyle \frac{{{\int }_{x_{k-1}}}^{x_{k+1}}f\left(x\right)A_k\left(x\right)\text{d}x}{h{s}_0}},c_{k,1}={\displaystyle \frac{{{\int }_{x_{k-1}}}^{x_{k+1}}f\left(x\right)(x-x_k)A_k\left(x\right)\text{d}x}{{{\int }_{x_{k-1}}}^{x_{k+1}}(x-x_k{)}^2{A}_k(x)\text{d}x}},$$

(7.15)

and

$$s_0={{\int }_{-1}}^1{A}_0\left(x\right)\text{d}x.$$

The kth component of the vector ${\mathbf{F}}^1\left[f\right]$ is denoted by ${F^1}_k\left[f\right]$.

The following is a list of properties of the F¹-transform of f with respect to a generalized fuzzy partition of $[a,b]$. They are particular cases of the properties of the F ^m-transform proved in [16]:

• (a) Let F _k and $c_{k,0}+c_{k,1}(x-x_k)$, for $k=1,\mathrm{\dots },n$, be respective kth components of ${\mathbf{F}}^1\left[f\right]$ and $\mathbf{F}\left[f\right]$. Then, $F_k=c_{k,0}$.

• (b) If for all $x\in [a,b]$, $f\left(x\right)=d+cx$, then all the components of F ¹-transform of $d+cx$ are equal to $(d+c{x}_k)+c(x-x_k)$, $k=1,\mathrm{\dots },n$.

• (c) If $f=\alpha g+\beta h$, then ${\mathbf{F}}^1\left[f\right]=\alpha {\mathbf{F}}^1\left[g\right]+\beta {\mathbf{F}}^1\left[h\right]$.

• (d) $c_{k,0}+c_{k,1}(x-x_k)=min\parallel f\left(x\right)-(d+c(x-x_k){\parallel }_k,k=1,\mathrm{\dots },n$, where $min$ is considered over the set of functions of the form $(d+c(x-x_k\left)\right)$.

• (e) If f is four times continuously differentiable on $[a,b]$, then

  $$c_{k,0}=f\left(x_k\right)+O\left(h^2\right),c_{k,1}=f^{\prime }\left(x_k\right)+O\left(h\right),k=1,\mathrm{\dots },n.$$

In Fig. 7.6, we show a schematic representation of the F ¹-transform components of a generic function f.

Fig. 7.6

Function f, its F¹-transform components ${F^1}_1,\mathrm{\dots },{F^1}_k,\mathrm{\dots },{F^1}_n$ (linear segments) and its F ⁰-transform components ${F^0}_1,\mathrm{\dots },{F^0}_k,\mathrm{\dots },{F^0}_n$ (star nodes) (after [16])

Finally, we give simplified expressions of F¹-transform components with respect to an h-uniform triangular fuzzy partition [16]

$$c_{k,0}={\displaystyle \frac{{{\int }_{x_{k-1}}}^{x_{k+1}}f\left(x\right)A_k\left(x\right)\text{d}x}{h}},$$

(7.16)

$$c_{k,1}={\displaystyle \frac{12{{\int }_{x_{k-1}}}^{x_{k+1}}f\left(x\right)(x-x_k)A_k\left(x\right)\text{d}x}{h^3}},$$

(7.17)

where $k=1,\mathrm{\dots },n$.

7 Applications

In this section, we consider applications of the F-transform and F¹-transform to image processing.

7.1 Image Compression and Reconstruction

A method of lossy image compression and reconstruction using fuzzy relations was proposed in [19]. The dominant idea was a choice of suitable granulation (represented by a fuzzy relation) of an image domain. We will refer to this method as FEQ. F-transform image compression (GlossaryTerm

FTR

) is based on the same idea of granulation but connects it with fuzzy partitions [1, 9]. In the cited papers, two approaches were proposed: a uniform fuzzy partition of the entire domain [1] and a two-step partition [9] in which initially the entire domain is partitioned into blocks and second, each block is uniformly partitioned into fuzzy sets. Both approaches were compared with JPEG and other compression techniques (including FEQ) [9], and the conclusion was that the F-transform-based method is slightly worse than JPEG but better than FEQ. Two further improvements of the F-transform-based compression have been proposed in [18, 28], where an advantage over JPEG was achieved in many cases.

In this section, after reiterating the principles of image compression and reconstruction using the F-transform and its inverse, we explain how a proper choice of a fuzzy partition improves the quality of the reconstructed image. A detailed elaboration and comparison with other existing techniques is in [18, 28] and will be presented in subsequent papers.

7.1.1 Principles of Image Compression Using the F-Transform

Let a grayscale image of size $N\times M$ pixels be represented by a function of two variables $u:N\times M\to [0,1]$. The value $u(i,j)$ represents the intensity range of each pixel in the gray scale. The problem of image compression is to reduce the image’s size to save space or transmission time. A desirable size $n\times m$ (where $n<N$ and $m<M$) of a compressed image can be obtained from the compression ratio, $\rho =nm/\left(NM\right)$. If a compression method is lossy (JPEG, FEQ, and the F-transform, for example), then the respective reconstruction $\widehat{u}$ to a full size image is compared with the original image using the two quality indices GlossaryTerm

PSNR

(peak signal-to-noise ratio) and GlossaryTerm

RMSE

(root-mean-square error), where

$$\text{PSNR}=20\ln \frac{255}{\text{RMSE}},$$

and

$$\text{RMSE}=\sqrt{\frac{{{\sum }_{i=1}}^N{{\sum }_{j=1}}^M\left[u\right(i,j)-\widehat{u}(i,j){]}^2}{NM}}.$$

7.1.2 Simple F-Transform Compression

In [1], we proposed representing a compressed image by the $n\times m$ matrix $\mathbf{U}$ of F-transform components

$$\mathbf{U}=\mathrm{(}\begin{array}{rrc}{U}_{11}& \mathrm{\dots }& U_{1m}\\ \mathrm{⋮}& \mathrm{⋮}& \mathrm{⋮}\\ U_{n1}& \mathrm{\dots }& u_{nm}\end{array}\mathrm{)},$$

computed over uniform fuzzy partitions (usually, triangular) $A_1,\mathrm{\dots },A_n$ and $B_1,\mathrm{\dots },B_m$ of the entire domains $[1,N]$ and $[1,M]$, respectively

$$U_{kl}=\frac{{{\sum }_{j=1}}^M{{\sum }_{i=1}}^{N}u(i,j)A_k\left(i\right)B_l\left(j\right)}{{{\sum }_{j=1}}^M{{\sum }_{i=1}}^N{A}_k\left(i\right)B_l\left(j\right)},k=1,\mathrm{\dots },n;l=1,\mathrm{\dots },m.$$

We proposed reconstructing $\mathbf{U}$ to a full-size image using the inverse F-transform of u such that

$$\widehat{u}(i,j)={\sum _{k=1}}^n{\sum _{l=1}}^m{U}_{kl}{A}_k\left(i\right)B_l\left(j\right).$$

This method does not take advantage of any property of the original image and therefore, its quality is not very high. Let us illustrate it on the image Cameraman taken from the Corel Gallery. In Fig. 7.7, we show the original image and its reconstruction using the simple F-transform compression described above. The compression ratio is $\rho =0.25$, and $\text{PSNR}=25.422$ (compare with $\text{PSNR}=38.8$ for JPEG with a similar compression ratio).

Fig. 7.7 a,b

Original image Cameraman (a) and its reconstruction after applying the simple F-transform compression (b) with $\text{PSNR}=25.422$

7.1.3 F-Transform Compression with Block Decomposition

This F-transform-based compression [9] was inspired by the JPEG method in which, at first, the entire domain was decomposed into blocks and then, each block was compressed according to a compression ratio. In [9], the same principle is used. In the first step, a decomposition into blocks of the same size is performed, where the size (chosen experimentally) is such that a certain quality of approximation by the inverse F-transform should be guaranteed (Theorem 7.1 ). Each block is then uniformly partitioned into cosine-shaped fuzzy sets and compressed by the simple F-transform method according to a compression ratio. In comparison with the simple F-transform compression, this method considers the peculiarities of the original images when making the block decomposition. In Fig. 7.8, we show the GlossaryTerm

PSNR

quality measure of the image Cameraman compressed using three methods: FEQ, F-transform with block decomposition and JPEG. It is easily observed that the JPEG method is still better than the F-transform with block decomposition, whereas the latter is better than FEQ. However, for the particular image Cameraman and the compression ratio $\rho =0.25$, the value of GlossaryTerm

PSNR

of the F-transform with block decomposition is similar to that of the simple F-transform compression: $25.0676$ versus $25.422$, respectively. This means that the uniform partition, even when applied to both steps independently, is not effective with respect to the quality estimated by GlossaryTerm

PSNR

. In the next subsection, we propose an F-transform compression method [18] that is almost nonlossy and is based on a nonuniform generalized partition adapted to each particular image.

Fig. 7.8

The PSNR values of the image Cameraman compressed using three methods: FEQ, the F-transform with block decomposition, and JPEG (after [29])

7.1.4 Advanced Image Compression

If we analyze the properties of the F-transform (Sect. 7.3.1), then it is immediate from (a) that the more the function behaves like a constant, the better is the approximation quality of the inverse F-transform. Thus, the following recommendation regarding the choice of a proper generalized fuzzy partition can be made:

• A generalized fuzzy partition of the domain $[1,N]\times [1,M]$ into fuzzy sets $A_k\times B_l$, where $k=1,\mathrm{\dots },n$ and $l=1,\mathrm{\dots },m$, should guarantee that the difference between extremal values of the image over each $A_k\times B_l$ is not greater than $\epsilon >0$ or (if the preceding condition cannot be fulfilled) the area of $A_k\times B_l$ is not greater than $\delta >0$.

There are several algorithms that can produce a generalized fuzzy partition with the mentioned property. In [18], we used the quad tree algorithm for this purpose; see the illustration in Fig. 7.9.

Fig. 7.9

The quad tree algorithm and the generalized fuzzy partition on its base

Let us add that the advanced image compression algorithm [18] uses the following two tricks to increase the quality of the reconstructed image:

• Preserve sharp edges

• Restore the histogram of the original image.

Figure 7.10 shows how the histogram restoration influences the quality of the reconstructed image. In Fig. 7.11, we see that the GlossaryTerm

PSNR

values of the advanced F-transform and the JPEG are almost equal.

Fig. 7.10 a,b

Two reconstructions of the image Cameraman after applying the advanced F-transform compression (the ratio is $0.188$) with the histogram restoring (a) and without it (b) . The PSNR values are $29$ (a) and $30$ (b)

Fig. 7.11

The PSNR values of the image Cameraman compressed using four methods: FEQ, the F-transform with block decomposition, the advanced F-transform, and JPEG

7.2 Image Fusion

Image fusion aims to integrate complementary distorted multisensor, multitemporal, and/or multiview scenes into one new image that contains the best parts of each scene. Thus, the primary problem in image fusion is to find the least distorted scene for every pixel.

A local focus measure is traditionally used for the selection of an undistorted scene. The scene that maximizes the focus measure is selected. Usually, the focus measure is a measure of high-frequency occurrences in the image spectrum. This measure is used when a source of distortion is connected with blurring, which suppresses high frequencies in an image. In this case, it is desirable that a focus measure decreases with an increase in blurring.

There are various fusion methodologies that are currently in use. They can be classified according to the primary technique: aggregation operators [22], fuzzy methods [30], optimization methods (e. g., neural networks and genetic algorithms [29]), and multiscale decomposition methods based on various transforms (e. g., discrete wavelet transforms; [31]).

The F-transform approach to image fusion was proposed in [32, 33]. The primary idea is a combination of (at least) two fusion operators, both of which are based on the F-transform. The first fusion operator is applied to the F-transform components of scenes and is based on a robust partition of the scene domain. The second fusion operator is applied to the residuals of scenes with respect to inverse F-transforms with fused components and is based on a finer partition of the same domain. Although this approach is not explicitly based on focus measures, it uses the fusion operator, which is able to choose an undistorted scene among the available blurred scenes.

7.2.1 Principles of Image Fusion Using the F-Transform

In this subsection, we present a short overview of the two methods of fusion that were proposed in [32, 33] and introduce a new method [34] that is a weighted combination of those two. We will demonstrate that the new method is computationally more effective than the first two.

The F-transform fusion is based on a certain decomposition of an image. We assume that the image u is a discrete real function $u=u(x,y)$ defined on the $N\times M$ array of pixels $P=\left\{\right(i,j)\mid i=1,\mathrm{\dots },N,j=1,\mathrm{\dots },M\}$ such that $u:P\to \mathbb{R}$. Moreover, let fuzzy sets $A_1,\mathrm{\dots },A_n$ and $B_1,\mathrm{\dots },B_m$, where $2\le n\le N,2\le m\le M$, establish uniform Ruspini partitions of $[1,N]$ and $[1,M]$, respectively. We begin with the following representation of u on P,

$$u(x,y)=u_{nm}(x,y)+e(x,y),$$

(7.18)

$$e(x,y)=u(x,y)-u_{nm}(x,y),$$

(7.19)

where u _nm is the inverse F-transform of u and e is the respective first difference. If we replace e in (7.18) by its inverse F-transform e _NM with respect to the finest partition of $[1,N]\times [1,M]$, the above representation can then be rewritten as follows,

$$u(x,y)=u_{nm}(x,y)+e_{NM}(x,y).$$

(7.20)

We call (7.20 ) a one-level decomposition of u on P. If u is smooth, then the function e _NM is small (this claim follows from the property (e) in Sect. 7.3.1), and we can stop at this level. In the opposite case, we continue with the decomposition of the first difference e in (7.18 ). We decompose e into its inverse F-transform $e_{n^{\prime }{m}^{\prime }}$ (with respect to a finer fuzzy partition of $[1,N]\times [1,M]$ with $n^{\prime }:n<n^{\prime }\le N$ and $m^{\prime }:m<m^{\prime }\le M$ basic functions) and the second difference $e^{\prime }$. Thus, we obtain the second-level decomposition of u on P

$$\begin{array}{rl}u(x,y)& =u_{nm}(x,y)+e_{n^{\prime }{m}^{\prime }}(x,y)+e^{\prime }(x,y),\\ e^{\prime }(x,y)& =e(x,y)-e_{n^{\prime }{m}^{\prime }}(x,y).\end{array}$$

In the same manner, we can obtain a higher level decomposition of u on P

$$u(x,y)=u_{n_1{m}_1}(x,y)+{e^{\left(1\right)}}_{n_2{m}_2}(x,y)+\mathrm{\cdots }+{e^{(k-2)}}_{n_{k-1}{m}_{k-1}}(x,y)+e^{(k-1)}(x,y),$$

(7.21)

where

$$0<n_1\le n_2\le \mathrm{\cdots }\le n_{k-1}\le N,0<m_1\le m_2\le \mathrm{\cdots }\le m_{k-1}\le M,e^{\left(1\right)}(x,y)=u(x,y)-u_{n_1{m}_1}(x,y),e^{\left(i\right)}(x,y)=e^{(i-1)}(x,y)-{e^{(i-1)}}_{n_i{m}_i}(x,y),i=2,\mathrm{\dots },k-\mathrm{1\hspace{0.33em}.}$$

(7.22)

7.2.2 Three Algorithms for Image Fusion

In [33], we proposed two algorithms:

• 1. The simple F-transform-based fusion algorithm (GlossaryTerm

  SA

  ) and

• 2. The complete F-transform-based fusion algorithm (GlossaryTerm

  CA

  ).

The principal role in the fusion algorithms GlossaryTerm

CA

and GlossaryTerm

SA

is played by the fusion operator $\kappa :{\mathbb{R}}^K\to \mathbb{R}$, which is defined as follows:

$$\kappa (x_1,\mathrm{\dots },x_K)=x_p,\text{if }\left|x_p\right|=max\left(\right|x_1|,\mathrm{\dots },|x_K\left|\right).$$

(7.23)

7.2.3 The Simple F-Transform-Based Fusion Algorithm

In this subsection, we present a block description of the GlossaryTerm

SA

without technical details, which can be found in [33]. We assume that $K\ge 2$ input (channel) images $c_1,\mathrm{\dots },c_K$ with various types of degradation are given. Our aim is to recognize undistorted parts in the given images and to fuse them into one image. The algorithm is based on the decompositions given in (7.20 ), which are applied to each channel image:

• 1. Choose values n and m such that $2\le n\le N,2\le m\le M$ and create a fuzzy partition of $[1,N]\times [1,M]$ by fuzzy sets $A_k\times B_l$, where $k=1,\mathrm{\dots },n$ and $l=1,\mathrm{\dots },m$.

• 2. Decompose the input images $c_1,\mathrm{\dots },c_K$ into inverse F-transforms and error functions according to the one-level decomposition (7.20).

• 3. Apply the fusion operator (7.23) to the respective F-transform components of $c_1,\mathrm{\dots },c_K$, and obtain the fused F-transform components of a new image.

• 4. Apply the fusion operator to the respective F-transform components of the error functions e _i , $i=1,\mathrm{\dots },K$, and obtain the fused F-transform components of a new error function.

• 5. Reconstruct the fused image from the inverse F-transforms with the fused components of the new image and the fused components of the new error function.

The GlossaryTerm

SA

-based fusion is very efficient if we can guess values n and m that characterize a proper fuzzy partition. Usually, this is performed manually according to the user’s skills. The dependence on fuzzy partition parameters can be considered as a primary shortcoming of this otherwise effective algorithm. Two recommendations follow from our experience:

• For complex images (with many small details), higher values of n and m yield better results.

• If a triangular shape for a basic function is chosen, than the generic choice of n and m is such that the corresponding values of n _p and m _p are equal to 3 (recall that n _p is the number of points that are covered by every full basic function A _k ).

7.2.4 The Complete F-Transform-Based Fusion Algorithm

The GlossaryTerm

CA

-based fusion does not depend on the choice of only one fuzzy partition (as in the case of the GlossaryTerm

SA

) because it runs through a sequence (7.22) of increasing values of n and m. The algorithm is based on the decomposition presented in (7.21), which is applied to each channel image. The description of the GlossaryTerm

CA

is similar to that of the GlossaryTerm

SA

except for step 4, which is repeated in a cycle. Therefore, the quality of fusion is high, but the implementation of the GlossaryTerm

CA

is rather slow and memory consuming, especially for large images. For an illustration, Fig. 7.12, Tables 7.1 and 7.2.

Table 7.1 Basic characteristics of the three algorithms applied to the image Balls

Table 7.2 MSE (mean-square error) and PSNR characteristics of the three fusion methods applied to the image Balls

Fig. 7.12 a–c

The SA (a) , CA (b) and ESA (c) fusions of the image Balls. The ESA fusion has the best quality (Table 7.2)

7.2.5 Enhanced Simple Fusion Algorithm

In [34], we proposed an algorithm that is as fast as the GlossaryTerm

SA

and as efficient as the GlossaryTerm

CA

. We aimed at achieving the following goals:

• Avoid running through a long sequence of possible partitions (as in the case of GlossaryTerm

  CA

  ).

• Automatically adjust the parameters of the fusion algorithm according to the level of blurring and the location of blurred areas in input images.

The algorithm adds another run of the F-transform over the first difference (7.18). The explanation is as follows: the first run of the F-transform is aimed at edge detection in each input image, whereas the second run propagates only sharp edges (and their local areas) to the fused image. We refer to this algorithm as to enhanced simple algorithm (GlossaryTerm

ESA

) and give its informal description:

for all input (channel) images do

 Compute the inverse F-transform

 Compute the first absolute difference between the original image and the inverse F-transform of it

 Compute the second absolute difference between the first one and its inverse F-transform and set them as the pixel weights

end for

for all pixels in an image do

 Compute the value of sow – the sum of the weights over all input images

 for all input images do

  Compute the value of wr – the ratio between the weight of a current pixel and sow

 end for

 Compute the fused value of a pixel in the resulting image as a weighted (by wr) sum of input image values

end for

The primary advantages of the GlossaryTerm

ESA

are:

• Time – the execution time is smaller than for the GlossaryTerm

  CA

  (Table 7.1).

• Quality – the quality of the GlossaryTerm

  ESA

  fusion is better than that of the GlossaryTerm

  SA

  and for particular cases (Table 7.2), it is better than that of the GlossaryTerm

  CA

  .

Because of space limitations, we present only one illustration of the F-transform fusion performed using the three algorithms, GlossaryTerm

SA

, GlossaryTerm

CA

, and GlossaryTerm

ESA

. We chose the image Balls with geometric figures to demonstrate that our fusion methods are able to reconstruct edges. In Fig. 7.13, two (channel) inputs of the image Balls are given, and in Fig. 7.12, three fusions of the same image are demonstrated.

Fig. 7.13 a,b

Two inputs for the image Balls. The central ball is blurred in (a) , and conversely, it is the only sharp ball in  (b)

In Table 7.1, we demonstrate that the complexity (measured by the execution time or by the memory used) of the GlossaryTerm

ESA

is greater than the complexity of the GlossaryTerm

SA

and less than the complexity of the GlossaryTerm

CA

.

In Table 7.2, we demonstrate that for the particular image Balls, the quality of fusion (measured by the values of GlossaryTerm

MSE

and GlossaryTerm

PSNR

) of the GlossaryTerm

ESA

result is better (the GlossaryTerm

MSE

value is smaller) than the quality of the GlossaryTerm

SA

result and even than the quality of the GlossaryTerm

CA

result.

7.3 ${\mathit{\text{F}}}^1$-Transform Edge Detector

Edge detection is inevitable in image processing. In particular, it is a first step in feature extraction and image segmentation. We focused on the Canny edge detector  [35], which is widely used in computer vision. It was developed to ensure three basic criteria: good detection, good localization, and minimal response. In these aspects, the Canny detector can be considered an optimal edge detector. In [26], we proposed using the F ¹-transform with the purpose of simplifying the first two steps of the Canny algorithm. Below, we provide the details of our proposal.

The Canny algorithm is a multistep procedure for detecting edges as the local maxima of the gradient magnitude. The first step, performed using a Gaussian filter , is image smoothing and filtering noise. The second step is computation of a gradient of the image function to find the local maxima of the gradient magnitude and the gradient’s direction at each point. This step is performed using a convolution of the original image with directional masks (edge detection operators , such as those of Roberts, Prewitt, and Sobel, are some examples of these filters). The next step is called nonmaximum suppression [36], and it selects those points whose gradient magnitudes are maximal in the corresponding gradient direction. The final step is tracing edges and hysteresis thresholding, which leads to preserving the continuity of edges.

In our experiment, we removed the first two steps in the Canny algorithm and replaced them by computation of approximate gradient values using the F¹-transform. The reason is that the F¹-transform (similar to the ordinary F-transform) filters out noise when computing approximate values of the first partial derivatives given by (7.15 ). We assume that the image is represented by a discrete function $u:P\to \mathbb{R}$ of two variables, where $P=\left\{\right(i,j)\mid i=1,\mathrm{\dots },N,j=1,\mathrm{\dots },M\}$ is an $N\times M$ array of pixels, and the fuzzy sets $A_1,\mathrm{\dots },A_n$ and $B_1,\mathrm{\dots },B_m$ establish a uniform triangular fuzzy partition of $[1,N]$ and $[1,M]$, respectively.

Let $x_1,\mathrm{\dots },x_n\in [1,N]$ and $y_1,\mathrm{\dots },y_m\in [1,M]$ be the h _x and h _y -equidistant nodes of $[1,N]$ and $[1,M]$, respectively.

According to property (e) in Sect. 7.6, the coefficients $c_{k,1}$ of the linear polynomials of the F ¹-transform components are approximate values of the first partial derivatives of the image function at nodes $(x_k,y_l)$ (for simplicity, we assume $k=2,\mathrm{\dots },n-1$ and $l=2,\mathrm{\dots },m$), where by (7.17) and (7.5) the following hold,

$$c_{k,1}\left(y_l\right)=\frac{12}{{h^3}_x{h}_y}{\sum _{i=1}}^N{\sum _{j=1}}^{M}u(i,j)(i-x_k)A_k\left(i\right)B_l\left(j\right),c_{l,1}\left(x_k\right)=\frac{12}{h_x{h^3}_y}{\sum _{i=1}}^N{\sum _{j=1}}^{M}u(i,j)(j-y_l)A_k\left(i\right)B_l\left(j\right).$$

Then, we can write approximations of the first partial derivatives as the respective inverse F-transforms

$$G_x(i,j)\approx {\sum _{k=1}}^n{\sum _{l=1}}^m{c}_{k,1}\left(y_l\right)A_k\left(i\right)B_l\left(j\right),$$

and

$$G_y(i,j)\approx {\sum _{k=1}}^n{\sum _{l=1}}^m{c}_{l,1}\left(x_k\right)A_k\left(i\right)B_l\left(j\right).$$

All other steps of the Canny algorithm – namely, finding the local maxima of the gradient magnitude and its direction, nonmaximum suppression, tracing edges through the image and hysteresis thresholding – are the same as in the original procedure.

In the two examples in Fig. 7.14, we demonstrate the results of the F¹-transform edge detector on images chosen from the dataset available at ftp://figment.csee.usf.edu/pub/ROC/edge_comparison_dataset.tar.gz.

Fig. 7.14 a–d

Original images (a,c) and their F¹-transform edges (b,d)

We observe that many thin edges/lines are detected as well as their connectedness and smoothness. Moreover, the following properties are retained:

• Smoothness of circular lines

• Concentricness circles

• Smoothness of sharp connections.

8 Conclusions

In this chapter, the theory of the F-transform has been discussed from the perspective of the latest developments and applications. The importance of a proper choice of fuzzy partition has been stressed. Various fuzzy partitions have been considered, including the most general partition (currently known). The definition of the F-transform has been adapted to the generalized fuzzy partition, and the main properties of the F-transform have been re-established. The applications to image processing, namely image compression, fusion and edge detection, have been discussed with sufficient technical details.