key: cord-0044874-0o90qaf7
authors: Zámečníková, Hana; Perfilieva, Irina
title: Nonlocal Laplace Operator in a Space with the Fuzzy Partition
date: 2020-05-16
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50153-2_22
sha: a7f36ff850ae2f30487fb8bc43e772ed535cd769
doc_id: 44874
cord_uid: 0o90qaf7

Differential operators play an important role in the mathematical modeling of dynamic processes and the analysis of various structures. However, there are certain limitations in their use. To remove them, nonlocal differential operators have been proposed. In this work, we focus on nonlocal Laplace operator, which has become increasingly useful in image processing. We introduce the representation of F-transform based Laplace operator in a space with a fuzzy partition. Many useful properties of this operator are proposed and their proofs are also included.

Image processing requires quick and efficient processing of large amounts of data. The most important factor here is the speed of processing, which can be generally in conflict with quality. For this reason, the classical metric spaces are gradually being replaced by more general spaces based on the notion of proximity. The direction of research is moving towards nonlocal differential operators defined on these spaces.

Methods based on nonlocal Laplace operator have become widely used in many application fields. Dimensionality reduction (extracting low dimensional structure from high dimensional data) [1] or clustering (automatic identification of groups of similar objects) [2] can be mentioned. This approach also turned out to be successful for image colorization [3] , image denoising or segmentation [4] .

In our approach we try to extend the theory of fuzzy transforms, that was proved to be useful in image processing. The purpose is to focus on similarities between approach based on the theory of fuzzy transform and framework based on nonlocal Laplace operator, mentioned above. We assume, that the use of nonlocal operators-based methods in spaces determined by fuzzy partition can somehow enhance the research in this direction.

Let f be a real function, f : Ω → R, Ω ⊂ R n . Laplace operator is a second order differential operator in the n-dimensional Euclidean space, given by the divergence of the gradient of a function f . Equivalently it can be defined by the sum of all the unmixed second partial derivatives of function f in the Cartesian coordinates

. This formula incorporates the partial derivatives, that should fulfill certain well-known conditions. However, this puts limitations on sets of functions, that can be differentiated as required.

For this reason, the notion of derivative was extended to a nonlocal version by defining [5] :

whered, 0 <d(x, y) ≤ ∞, defines a positive distance measure between x and y.

and symmetrical (w(x, y) = w(y, x)), then w is called a measure of proximity. A pair (Ω, w) defines a proximity space.

A proximity space (Ω, w) can be also introduced with the reference to a distance measure, e.g. defining

In (Ω, w), a nonlocal derivative can be defined as follows [5] :

This notion can be extended for functions of several real variables. In a similar way, other operators of vector field can be defined in a nonlocal form. The nonlocal gradient ∇ w f (x) : Ω → Ω × Ω, which is defined as a vector of all partial derivatives, has a form [5] :

: Ω × Ω → Ω can be written as follows [5] :

It is well known that the Laplace operator can be defined by the divergence of the gradient up to a constant multiplication, therefore with the notions mentioned above we can define nonlocal Laplace operator in this case by:

for each function f : Ω → R and [a, b] ⊂ Ω.

The choice of proper proximity function is extremely important. In this article we proposed one, where proximity is determined by fuzzy partition A 1 , . . . , A n .

. . , n holds [6] :

The membership functions A 1 , . . . , A n are called basic functions.

) and the following additional properties are fulfilled: 

A 0 is called a generating function of uniform fuzzy partition.

Generating function A 0 produces infinitely many rescaled functions [8] A H : R → [0, 1] with the scale factor H > 0, so that:

{A H (x − k · h), k ∈ Z}.

Direct Fuzzy transform or F-transform is a result of weighted linear integral transformation of a continuous function with weights determined by basic functions. 

is the direct integral F-transform of f with respect to A 1 , . . . , A n .

F-transform establishes a correspondence between a set of continuous functions on [a, b] and the set of n-dimensional vectors. Inverse F-transform then converts an n-dimensional vector of components (F 1 , . . . , F n ) into another continuous function:f

which approximates the original one.

, h > 0 and A h be a h-rescaled generating function.

Assume the measure of proximity as follows: 

defines nonlocal Laplace operator. F x denotes the particular

In this section we propose several properties of the operator Δ F T w . Proposition 2 . For all x, y ∈ [a, b] , the operator Δ F T w admits following properties:

where ·, · denotes inner product on L 2 , defined as f, g = b a f (x)g(x) dx.

Proof. Property 1:

Property 2:

Property 3:

Property 4:

Property 5:

Image regularization that uses the nonlocal Laplace operator is proved to be very efficient [9] . The regularization of an image function f 0 corresponds to an optimization problem, which can be formalized by the minimization of a weighted sum of two energy terms [9] :

where R p w (f ) = 1 p u∈V |∇ w f (u)| p (details can be found in [9] ). When assuming p = 2, this problem has a unique solution.

In [9] , linearized Gauss-Jacobi iterative method was used to solve this problem. Let t be an iteration step, and let f (t) be the solution at the step t. The method is given by the following algorithm:

It describes a family of discrete diffusion processes, which is parametrized by the structure of the graph, the edge weights, the parameter λ and the parameter p.

In our case, p = 2, the equation of the (t + 1)th step is simplified to:

The minimization problem and the discrete diffusion processes can be used to regularize any function defined on a finite set of discrete data. This is realized by constructing a weighted graph G = (V, E, w), and by selecting the function to be regularized as a function f 0 , defined on the vertices of the graph.

Graph is produced as follows. Each pixel is identified with one vertex and semantically related pixels are connected by edges. The edges weights are computed according to a symmetric similarity function m : V × V → R. If between vertices u and v does not exist an edge, then w(u, v) = 0, otherwise w(u, v) = m (u, v) .

Every data u ∈ V is assigned with a feature vector F (f 0 , u) ∈ R q . In the simplest case, one can consider F (f 0 , u) = f 0 (u).

Also the choice of graph topology plays an important role, because different types of graphs are suitable to use for different types of problems.

Consider an image damaged by additional noise and the goal of this method is to restore the initial uncorrupted image. In our case RGB noise was added. We analyzed the case of weight function depending on the fuzzy partition for a fixed value of parameter p. The scalar feature vector was used, F (f 0 , u) = f (u). And for this configuration, we considered a standard 4-adjacency grid graph.

Various values of parameter λ were tested. For illustration we selected the one best output after 15 iterations of regularization process. Figure 1 shows, that the noise was partly removed and this process caused minimal damage to geometric features. 

A new representation of nonlocal Laplace operator in a space with a fuzzy partition is proposed and analysed. It stems from the theory of fuzzy transform, where the weight assignment is based on a generating function of a fuzzy partition and represents proximity between points. We proved validity of all important properties of this operator and illustrated its usefulness in image denoising.

In the future work, we would like to continue in this direction, we are now focusing on how a new expression of nonlocal Laplace operator can be applied to image processing tasks, specifically we would like to turn the attention to image segmentation and filtering, that are connected to the regularization. This nonlocal approach is significantly computationally simpler, so we expect that compared to classical methods it will be a significantly lower time consuming, which is one of the main priorities in this field.

Laplacian eigenmaps for dimensionality reduction and data representation

A tutorial on spectral clustering

Nonlocal graph regularization for image colorization

Nonlocal linear image regularization and supervised segmentation

Nonlocal operators with applications to image processing

Fuzzy transforms: theory and applications. Fuzzy Sets Syst

Towards a higher degree F-transform

Total variation with nonlocal FT-Laplacian for patchbased inpainting

Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing

Acknowledgements. The authors thank the reviewers for their valuable comments and suggestions to improve the quality of the paper. The support of the grant SGS01/UVAFM/2020 is kindly announced.