Vasile Patrascu
email: patrascu.v@gmail.com

Applying Onicescu information energy for gray level image segmentation

Keywords: neutrosophic information, Onicescu information energy, image segmentation, gray level image threshold. ACM/AMS Classification: 68U10, 62H35 1 Introduction

diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

the gray levels. These thresholds will be defined by the local maximum points of the Onicescu information energy. The segmentation of a gray level image actually means the determination of some clusters and we start from the premise that within each cluster, the Onicescu information energy is maximum. Next, the article has the following structure: section 2 does a brief presentation of the neutrosophic representation of the information; section 3 presents Onicescu's information energy and its extension to neutrosophic information [7]; section 4 presents the method of constructing neutrosophic information associated with gray levels and at the same time correlated with a certain separation threshold; section 5 presents the segmentation method; section 6 presents the experimental results; section 7 presents some conclusions while the last section is that of references.

2 The Neutrosophic Representation of Information.

Neutrosophic information is described by a triplet q = (µ, ω, ν) ∈ [0, 1] 3 , where µ represents the degree of truth, ω degree of neutrality and ν degree of falsity [8], [9], [START_REF] Smarandache | An Introduction to the Neutrosophic Probability Applied in Quantum Physics[END_REF], [START_REF] Smarandache | Neutrosophic Set -A Generalization of the Intuitionistic Fuzzy Set[END_REF]. The neutrosophic representation is a generalization of the fuzzy representation [START_REF] Zadeh | Fuzy sets[END_REF] and at the same time a generalization of the intuitionistic fuzzy representation [START_REF] Atanassov | Intuitionistic Fuzzy Sets[END_REF]. For neutrosophic information the operations of union, intersection and negation can be defined. For two neutrosophic information a = (µ a , ω a , ν a ) and b = (µ b , ω b , ν b ) we define in this article the union ∪ and the intersection ∩ with the following formulas:

• The union a ∪ b µ a∪b = µ a ∨ µ b (1)
ω a∪b = (µ a -ν a ) ∨ (µ b -ν b ) -(µ a -ω a -ν a ) ∨ (µ b -ω b -ν b ) (2)
ν a∪b = µ a ∨ µ b -(µ a -ν a ) ∨ (µ b -ν b ) (3)
• The intersection a ∩ b

µ a∩b = µ a ∧ µ b (4)
ω a∩b = (µ a -ν a ) ∧ (µ b -ν b ) -(µ a -ω a -ν a ) ∧ (µ b -ω b -ν b ) (5)
ν a∩b = µ a ∧ µ b -(µ a -ν a ) ∧ (µ b -ν b ) (6)
where the symbol ∨ represents the maximum while the symbol ∧ represents the minimum, namely:

∀x, y ∈ ∞, ∞), x ∨ y = max(x, y) (7)
x ∧ y = min(x, y)

The negation operator for the neutrosophic information a = (µ, ω, ν) is obtained by the negation of each component, i.e. it is defined with the following formula:

• The negation ā ā = (1 -µ, 1 -ω, 1 -ν) (9)
We must mention that the three operators defined above, construct a De Morgan algebra for neutrosophic information. At the end of the short presentation of neutrosophic information representation, we must note the following classification: Neutrosophic information is complete if

µ + ω + ν = 1 (10) is incomplete if µ + ω + ν < 1 (11)
and is inconsistent if

µ + ω + ν > 1 ( 12
)
3 Onicescu Information Energy.

Onicescu information energy was defined for probability distributions [START_REF] Onicescu | Energie informationelle[END_REF], [START_REF] Onicescu | Elemente de statistica informationala cu aplicatii (Elements of information statistics with applications[END_REF], [START_REF] Onicescu | Energia informationa (Information energy)[END_REF]. For a discrete probability distribution P = (p 1 , p 2 , . . . , p n ), which obviously verifies the partition condition of unity,

p 1 + p 2 + . . . + p n = 1 (13)
Onicescu's information energy was defined with the following formula:

E o (P ) = n i=1 p 2 i ( 14
)
The Onicescu information energy formula was extended to an n-dimensional fuzzy representations but which verifies the partition condition of unity. Thus, for an n-dimensional fuzzy information M = (µ 1 , µ 2 , . . . , µ n ∈ [0, 1] n and which verifies the partition condition of unity,

µ 1 + µ 2 + . . . + µ n = 1 (15)
using formula (14) we obtain:

E o (M ) = n i=1 µ 2 i ( 16
)
But there are cases when the fuzzy information M = (µ 1 , µ 2 , . . . , µ n ) does not check the partition condition of unity (15) such as intuitionistic fuzzy information [START_REF] Atanassov | Intuitionistic Fuzzy Sets[END_REF], paraconsistent fuzzy information and neutrosophic fuzzy information [8], [9], [START_REF] Smarandache | An Introduction to the Neutrosophic Probability Applied in Quantum Physics[END_REF], [START_REF] Smarandache | Neutrosophic Set -A Generalization of the Intuitionistic Fuzzy Set[END_REF]. This may be incomplete if:

µ 1 + µ 2 + . . . + µ n < 1 ( 17
)
or it may be inconsistent, if:

µ 1 + µ 2 + . . . + µ n > 1 (18)
This happens in the case of neutrosophic fuzzy information because it is possible that the sum µ + ω + ν is different from 1. If the fuzzy information M = (µ 1 , µ 2 , . . . , µ n ) is incomplete or inconsistent, a complete information M is constructed associated with the primary information [7]. Thus, we define the following parameters:

δ = µ 1 + µ 2 + . . . + µ n -1 (19) π = max(-δ, 0) (20)
We define the components of information M with the following formula [7]:

μi = µ i + 2π n 1 + |δ| (21)
In the next, we will prove that the information M whose components are defined by formula ( 21) is a complete information and that it verifies the partition condition of unity:

n i=1 μi = 1 (22)
From (21) it results:

n i=1 μi = n i=1 µ i + 2π n 1 + |δ| = 1 1 + |δ| ( n i=1 µ i + 2π) (23)
The following two formulas result from ( 19) and (20):

n i=1 µ i = 1 + δ (24) π = -δ + |δ| 2 (25)
Replacing ( 24) and ( 25) in ( 23), it results the following two equalities:

n i=1 μi = 1 1 + |δ| 1 + δ + 2 -δ + |δ| 2 = 1 (26)
Thus, we proved that the information M = (μ 1 , μ2 , . . . , μn ) defined by ( 21) is a complete one and we can calculate the Onicescu information energy with the formula ( 16):

E o ( M ) = n i=1 μ2 i (27)
The Onicescu energy of the complete information M will also define the Onicescu energy for the information M [7], namely:

E o (M ) = E o ( M ) (28)
The following equivalent formula results from formulas (27), ( 28) and ( 21):

E o (M ) = n i=1    µ i + 2π n 1 + |δ|    2 (29)
In the particular case of the neutrosophic information q = (µ, ω, ν), the formulas ( 19) and (20) become:

δ = µ + ω + ν -1) (30) π = max(-δ, 0) (31)
From (21), it results the complete neutrosophic information q = (μ, ω, ν):

μ = µ + 2π 3 1 + |δ| (32) ω = ω + 2π 3 1 + |δ| (33) ν = ν + 2π 3 1 + |δ| (34)
From ( 27) and (29), we obtain for the neutrosophic information, the following formulas for the Onicescu information energy:

E o (q) = μ2 + ω2 + ν2 (35)
and

E o (q) =    µ + 2π 3 1 + |δ|    2 +    ω + 2π 3 1 + |δ|    2 +    ν + 2π 3 1 + |δ|    2 (36)
4 The Neutrosophic Information Construction.

Any image with gray levels is defined by the triplet (D, V, f ), where D = {1, 2, . . . , k -1, k} × {1, 2, . . . , l -1, l} is the domain image, V = [0, 1] is the range of values of the gray levels, while f : D → V is the function that defines the image. The two parameters k and l are natural numbers. We will denote by C f the codomain of the function f , that is C f = f (D) and then we define the range of values that includes the codomain C f , that is:

c m = min(C f ) (37) c M = max(C f ) (38)
Now, we consider a certain threshold defined by the point t ∈ (c m , c M ). The point t defines two subdomains C l and C h , namely:

C l = {c ∈ C f |c ≤ t} (39)
C h = {c ∈ C f |c ≥ t} (40)
Next, we will present the necessary steps to construct the neutrosophic information associated with the separation threshold t. We will calculate the averages m l and m h for C l and C h with the following two formulas:

m l (t) = 1 card(C l ) c∈C l c (41) m h (t) = 1 card(C h ) c∈C h c (42)
To calculate the components of neutrosophic information, we will use the similarity function for the gray levels from [START_REF] Patrascu | Gray Level Image Threshold Using Neutrosophic Certainty[END_REF], [6]. This similarity function is defined by the following formula:

s : [0, 1] × [0, 1] → [0, 1], s(x, y) = 1 - 2|x -y| 1 + |x -0.5| + |y -0.5| (43)
First, we calculate the similarity between each gray level c ∈ C f and the averages m l , m h and the threshold t. The following three similarity values result: s(c, m l ), s(c, m h ) and s(c, t).

s(c, m l ) = 1 - 2|c -m l (t)| 1 + |c -0.5| + |m l (t) -0.5| (44) s(c, m h ) = 1 - 2|c -m h (t)| 1 + |c -0.5| + |m h (t) -0.5| (45) s(c, t) = 1 - 2|c -t| 1 + |c -0.5| + |t -0.5| (46)
We also define the similarity between a gray level c ∈ C f and the pair (m l , m h ) with the following aggregation formula:

s a (c, m l , m h ) = max(s(c, m l ), s(c, m h )) (47)
With the similarities defined by (44), (45), ( 46), (47), we will construct the neutrosophic information for each gray level c and for each threshold t with the formulas used in [6], [7]. This results in the following calculation formulas:

• The degree of truth:

µ(c, t) = s(c, m l ) • (1 -s(c, m h )) 1 -s(c, m l ) • s(c, m h ) (48)
• The degree of neutrality:

ω(c, t) = s(c, t) • (1 -s a (c, m l , m f )) 1 -s(c, t) • s a (c, m l , m f ) (49)
• The degree of falsity:

ν(c, t) = s(c, m h ) • (1 -s(c, m l )) 1 -s(c, m l ) • s(c, m h ) (50)
With formulas (48), ( 49) and (50) we constructed the neutrosophic information (µ, ω, ν) for the gray level c and the threshold t.

5 The Segmentation Method.

To begin with, we construct the possible set for the threshold values according to the values of the gray levels contained in image f . For this, we will use as a parameter, a natural number Q ≥ 100. Thus the possible set for the threshold values will be defined by the formula:

V Qf = (c m , c M ) ∩ 1 Q , 2 Q , . . . , Q -1 Q (51)
where the pair (c m , c M ) is defined by ( 37) and (38). For each threshold t ∈ V Qf , we will calculate the average energy for fuzzy sets associated with the neutrosophic components µ, ω and ν defined by formulas ( 48), ( 49) and ( 50). Thus, we obtain the partial energies E µ (t), E ω (t) and E ν (t).

E µ (t) = c∈C f µ(c, t)E o (c, t) c∈C f µ(c, t) (52) E ω (t) = c∈C f ω(c, t)E o (c, t) c∈C f ω(c, t) (53)
E ν (t) = c∈C f ν(c, t)E o (c, t) c∈C f ν(c, t) (54)
where E o (c, t) is calculated by the formula (36) for the triplet (µ(c, t), ω(c, t), ν(c, t)).

The total energy E(t) is calculated with the average of the three partial energies, i.e.:

E(t) = E µ (t) + E ω (t) + E ν (t) 3 ( 55
)
We assume that at the end of the Onicescu energy calculation stage, we obtain the following n points of local maximums (t 1 , t 2 , . . . , t n ). These local maximum points define the following n + 1 subsets:

w 1 = (c m , t 1 ) ∩ C f ,...,w i = (t i-1 , t i ) ∩ C f ,...,w n+1 = (t n , c M ) ∩ C f .
Then for each subset w i , we calculate its mean ϑ i , using the following formulas: ∀i = 1, 2, . . . , n + 1,

ϑ i = 1 card(w i ) c∈w i c (56)
The segmented image is obtained by replacing each gray level that belongs to the subset w i with the mean ϑ i . In formulas (52), ( 53) and (54) for a greater refinement of the segmentation, we can replace the set C f with a local neighborhood of the threshold t of the form

C ∆f = C f ∩ [t -∆, t + ∆]
where ∆ ∈ (0, 1). In this case the formulas (52), ( 53) and (54) become:

E µ (t) = c∈C ∆f µ(c, t)E o (c, t) c∈C ∆f µ(c, t) (57)
E ω (t) = c∈C ∆f ω(c, t)E o (c, t) c∈C ∆f ω(c, t) (58)
E ν (t) = c∈C ∆f ν(c, t)E o (c, t) c∈C ∆f ν(c, t) (59)
6 Experimental Results.

To test the properties of the method proposed in this article, we used it to segment the following images with gray levels: " baboon", " Mary", "peppers", "spider", "parrots" and "Bobby". These images can be seen in Figures

. The graphic of the functions obtained for the Onicescu information energy can be seen in Figures

. The segmented images can be seen in Figures 7 Conclusions.

This article presents a method of segmenting images with gray levels using elements of neutrosophic theory. In fact, each pixel is associated with neutrosophic information to which the Onicescu information energy is calculated. The segmentation method uses the determination of optimal thresholds, for separating the gray levels in intervals, after which, the averages of these intervals describe the basis for the representation of the segmented image. The separation thresholds are defined by the local maximum points of the Onicescu information energy. The experimental results show us that the local maximums of the Onicescu information energy can be used as thresholds for separating the gray levels in the segmentation process. It is also observed that the presented method can provide multiple separation thresholds. On the other hand, this article is an example of using the neutrosophic representation of information in the field of image processing with gray levels and at the same time the use of Onicescu information energy.

Figure 1 :Figure 2 :

 12 Figure 1: The image "baboon" (a). The graphic of the Onicescu energy and its local maximums (b). The segmented image with three gray levels (c).

Figure 3 :Figure 4 :Figure 5 :Figure 6 :

 3456 Figure 3: The image "peppers" (a). The graphic of the Onicescu energy and its local maximums (b). The segmented image with four gray levels (c).


Mohamed-Amine Baazizi
email: baazizi@ia.lip6.fr

Dario Colazzo
email: dario.colazzo@dauphine.fr

Giorgio Ghelli
email: ghelli@di.unipi.it

Carlo Sartiani
email: carlo.sartiani@unibas.it

Stefanie Scherzinger
email: stefanie.scherzinger@uni-passau.de

Not Elimination and Witness Generation for JSON Schema (short version)

Keywords: JSON Schema, negation, witness generation

JSON Schema is an evolving standard for the description of families of JSON documents. JSON Schema is a logical language, based on a set of assertions that describe features of the JSON value under analysis and on logical or structural combinators for these assertions. As for any logical language, problems like satisfaction, not-elimination, schema satisfiability, schema inclusion and equivalence, as well as witness generation, have both theoretical and practical interest. While satisfaction is trivial, all other problems are quite difficult, due to the combined presence of negation, recursion, and complex assertions in JSON Schema. To make things even more complex and interesting, JSON Schema is not algebraic, since we have both syntactic and semantic interactions between different keywords in the same schema object.

With such motivations, we present in this paper an algebraic characterization of JSON Schema, obtained by adding opportune operators, and by mirroring existing ones. We present then algebrabased approaches for dealing with not-elimination and witness generation problems, which play a central role as they lead to solutions for the other mentioned complex problems.

INTRODUCTION

JSON Schema [2] is an evolving standard for the description of families of JSON documents. It is maintained by the Internet Engineering Task Force IETF [1]. Its latest version has been produced on 2019-09 [START_REF] Wright | JSON Schema validation: A vocabulary for structural validation of json -draft-handrews-json-schema-validation-02[END_REF] but is not widely used compared to the intermediate Draft-06.

JSON Schema uses the JSON syntax. Each construct is defined using a JSON object with a set of fields describing assertions relevant for the values being described. Some assertions can be applied to any JSON value type (e.g., type), while others are more specific (e.g., multipleOf that applies to numeric values only). The syntax and semantics of JSON Schema have been formalized in [START_REF] Pezoa | Foundations of json schema[END_REF] following the specification of Draft-04. We limit ourself to an informal discussion revealing the possible constraints associated to each kind of type:

• when defining a string, it is possible to restrict its length by specifying the minLength and maxLength constraints and to define the pattern that the string should match; • when defining a number, it is possible to define its range of values by specifying any combination of minimum / ex-clusiveMinimum and maximum / exclusiveMaximum, and to define whether it should be multipleOf a given number; • when defining an object, it is possible to define its properties, the type of its additionalProperties and the type of the properties matching a given pattern (i.e. patternProperties). It is also possible to restrict the minimum and maximum number of properties using minProperties and maxProperties, and to indicate which properties are required; • when defining an array, it is possible to define the type of its items and the type of the additionalItems which were not already defined by items, and to restrict the minimum and maximum size of the array; moreover, it is also possible to enforce unicity of the items using uniqueItems.

JSON Schema is a logical language allowing for combining assertions using standard boolean connectives: not for negation, allOf for conjunction, anyOf for disjunction, and oneOf for exclusive disjunction. As for any logical language, the following problems have a theoretical and practical interest:

• satisfaction 𝐽 ⊨ 𝑆: does a JSON document 𝐽 satisfy schema 𝑆?

• not-elimination: is it possible to rewrite a schema to an equivalent form without negation? • satisfiability of a schema: does a document 𝐽 exist such that 𝐽 ⊨ 𝑆?

• schema inclusion 𝑆 ⊆ 𝑆 ′ : does, for each document 𝐽 , 𝐽 ⊨ 𝑆 ⇒ 𝐽 ⊨ 𝑆 ′ ? • schema equivalence 𝑆 ≡ 𝑆 ′ : does, for each document 𝐽 , 𝐽 ⊨ 𝑆 ⇔ 𝐽 ⊨ 𝑆 ′ ?
• witness generation: is there an algorithm to generate one element 𝐽 for any non-empty schema 𝑆? While satisfaction is trivial, all other problems are quite difficult, due to the combined presence of negation, recursion, and complex assertions.

A second aspect that makes the task difficult is the non-algebraic nature of JSON Schema. A language is "algebraic" when the applicability and the semantics of its operators only depends on the semantics of their operands. In this sense, JSON Schema is not algebraic, since we have both syntactic and semantic interactions between different keywords in the same schema object, such as the prohibition to repeat a keyword inside a schema object, or the interactions between the "properties" and "additionalProperties" keywords. For instance, the following schema 1 demands that any properties other than foo and bar must have boolean values.

{ "properties": {"foo": {}, "bar": {}}, "additionalProperties": {"type": "boolean"} } Such features complicate the tasks of reasoning about the language and of writing code for its manipulation.

SUMMARY OF CONTRIBUTIONS

JSON Algebra. We define a core algebra, which features a subset of JSON Schema assertions. This algebra is minimal, that is, no operator can be defined starting from the others.

Not elimination. We show that negation cannot be eliminated from JSON Schema, since there are some assertions whose complement cannot be expressed without negation such as or multipleOf. We enrich the core algebra with primitive operators to express those missing complementary operators, and we present a not elimination algorithm for the enriched algebra. To our knowledge, this is the first paper where not elimination is completely defined, with particular regard to the treatment of negation and recursion.

Witness generation. We define an approach for witness generation for the complete JSON Schema language, with the only exception of the uniqueItems operator, hence solving the satisfiability and inclusion problems for this sublanguage.

For space reasons, many details and formal aspects presented in the complete report [START_REF] Baazizi | Not elimination and witness generation for json schema[END_REF] are not reported here, including the extension to uniqueItems for witness generations. The presentation of several steps (especially for witness generation) is driven/based by/on examples.

Also, we would like to stress that results presented in this paper takes part of research activities [START_REF] Baazizi | Not elimination and witness generation for json schema[END_REF] that are still in progress. So our main aim here is to present existing results, mainly at the definition and formalisation level of algorithms.

RELATED WORK

The first effort to formalize the semantics of JSON Schema as by Pezoa et al. in [START_REF] Pezoa | Foundations of json schema[END_REF] whose goal was to lay the foundations of the JSON schema proposal by studying its expressive power and the complexity of the validation problem. Along the lines of this work, Bouhris et al. [START_REF] Bourhis | JSON: data model, query languages and schema specification[END_REF] characterized the expressivity of the JSON Schema language and investigated the complexity of the satisfiability problem which turns out to be 2EXPTIME in the general case and EXPSPACE when disallowing uniqueItems. None of the above works study the problem of generating an instance of a JSON Schema. The only attempt to solve this problem was investigated by Earle et. al [START_REF] Benac | Jsongen: a quickcheck based library for testing json web services[END_REF] in the context of testing REST API calls but the presented solution, which is based on translating JSON Schema definitions into an Erlang expression, is not formally defined and restricted to atomic values, objects and to some form of boolean expressions.

1 Example available at [START_REF]Json schema test suite[END_REF].

From the point of view of schema normalization, the closest work to ours is the one in [START_REF] Habib | Type safety with json subschema[END_REF] which studies schema inclusion for JSON Schema. To cope with the high expressivity of the JSON Schema language, a pre-requisite step is needed to rewrite the schemas into a Disjunctive Normal Form which has some similarities with the preparation phase of our work. However, compared to our work, the schema normalization in [START_REF] Habib | Type safety with json subschema[END_REF] lacks the ability of eliminating negation for all kinds constraints, does not deal with recursive definitions and is not able to decide schema satisfiability which is captured by the inhabited( ) predicate whose specification is only informally discussed. This has been confirmed in practice by experimenting the tool developed in [START_REF] Habib | Type safety with json subschema[END_REF] for parsing real world schemas described in [START_REF] Baazizi | Not elimination and witness generation for json schema[END_REF]: the tool raised an issue for 21,859 out of 23,480 input schemas. The dominating error is related to constructs not being supported, but many other errors due to the inability to parse recursive schemas or to navigate references are present.

CONCLUSION

JSON Schema is an evolving standard for the description of families of JSON documents, and is widely used in data-centric applications. Despite the recent interest in the research community related to this schema language, crucial problems like schema equivalence/inclusion and consistency have either been partially dealt with or not explored at all. In this work we present our approach in order to solve these problems, based on our algebraic specification of JSON Schema. We are currently finalizing a Java implementation of the presented algorithm, and studying optimisation techniques, by analysing a large repository of JSON Schemas allowing us for determining how often mechanisms that are critical for execution times are used. We are also investigating witness generation techniques able to generate several instances meant be used for testing queries and programs manipulating valid JSON data.

© 2020, Copyright is with the authors. Published in the Proceedings of the BDA 2020 Conference (October 27-29, 2020, En ligne, France). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. © 2020, Droits restant aux auteurs. Publié dans les actes de la conférence BDA 2020 (27-29 octobre 2020, En ligne, France). Redistribution de cet article autorisée selon les termes de la licence Creative Commons CC-by-nc-nd 4.0.

ACKNOWLEDGEMENTS

The research has been partially supported by the MIUR project PRIN 2017FTXR7S "IT-MaTTerS" (Methods and Tools for Trustworthy Smart Systems).