Gilles Mauris

Eric Benoit
email: benoit@univ-savoie.fr

Laurent Foulloy
email: foulloy@univ-savoie.fr

Fuzzy symbolic sensors from concept to applications

Keywords: symbolic sensors, fuzzy sensors, measurement theory, fuzzy subset theory, intelligent measurement, range finding sensor, colour matching sensor

come

Introduction

Nowadays, system control by usual techniques of control theory is well-known insofar as one knows a mathematical model of the process. Sometimes, the model is difficult and quite longer to acquire, and then, results in complex calculations for the control law synthesis. In most complicated cases, no viable mathematical models are available, so, alternative methods based on artificial intelligence technics have been developed (expert control [Aström,86], intelligent control [Meystel,87], fuzzy control (among many others) [Pedrycz,89],...). They consist in collecting all the information available on the process and on the way to control it, and then to formalize it with a representational language in order to handle it with a program of adequate structure. This information is generally obtained by the observation of an operator, and provides qualitative explanations upon the behaviour of the process, contrary to numerical information, that provides a fine quanti- Mauris G., Benoit E., Foulloy L., "Fuzzy symbolic sensor : from concept to applications", Measurement, ISSN 0263-2241, N o 12, pp 357-184, 1994 tative representation. Instead of considering the two approaches as competitive, it seems more advantageous to associate the numeric and linguistic representations of a same reality, in order to benefit from the advantages of the two types of models.This assertion is particularly true for integrated automatization of big systems by usual technics, in which, fault detection, supervision and starting problems are difficult to handle, with only a mathematical model of the process. In these cases, it seems interesting to use the information the operators have on their systems. Besides, a linguistic approach facilitates man-machine integration between a system and a user, that will understand the orders applied by control components. An efficient collaboration between numeric and linguistic processing implies a coherence between the two types of information. This aspect concerns first the acquisition of relevant information. This role is attributed to sensors, that have for objective to provide measurements, that allow the decision system to link action and perception.

In our approach, a sensor must be able to perform a linguistic description of acquired signals. It requires the collaboration between two types of information: signal analysis information (essentially analog and numeric), and user's information (essentially qualitative and heuristic). This connection has been realized by means of a new type of sensor, called symbolic sensor [Foulloy,90], [Benoit,91a and 91b]. Such sensors are based on a numeric-linguistic conversion, that can be implemented in many ways. This paper focuses on numeric-linguistic conversion based on a fuzzy subset approach [Zadeh,65 and 83]. Therefore, this kind of sensors are called fuzzy symbolic sensors, or simply fuzzy sensors [Foulloy,88 and 92]. Moreover, one can imagine to implement the numeric-symbolic conversion by means of neural networks, that leads to neural symbolic sensors, or by any other techniques including analog ones.

In a first section, we will reconsider the measurement theory, and describe a general formalism evolved by Finkelstein, that sets theoretical foundations of symbolic (numeric and linguistic) representation. We will develop common and different aspects between numeric and linguistic information. Then, we will propose a mechanism for numeric-linguistic conversion, based on a representation of words by fuzzy subsets of the numerical domain. The structure of linguistic symbolization will be studied as well as adaptation to the global task. Finally, a procedure of management of numeric errors based on a statistical probabilistic description and on associated fuzzy operators will be presented. Then, we will apply the proposed formalism to two concrete examples, an ultrasonic range finding sensor and a colour matching sensor. The first implementation concerns a proximity measurement with numeric acquisition of distance between sensor and obstacle. For this monodimensional measurement, we will be particularly interested in the creation of concepts by semantic relations and in the management of errors. The second one deals with object colour classification. Measurement is a tridimensional one, and a software sensor will be described. It works with the three -red, green and blue -components of a camera. For the colour perception, we will be particularly interested in a learning with teacher procedure based on standard colours, and in the matching of new objects. As a conclusion, the contribution of this research will be pointed out, as well as the new ways opened by symbolic representation of perceived information.

Measurement concept and symbolic representation

Introduction

Before studying in detail the concept of symbolic sensors, it is interesting to discuss the role of the sensor. Its object is to discriminate from the lot of received information a particular physical quantity. Generally, the description of a property or an attribute of an object of the real world is made by the assignment of a numerical value. The relations between numerical values assigned to different elements correspond to empirical relations between the elements to which they are assigned, which allows us to work with a mathematical description of objects. The numerical representation is precise and compact. It provides a way of establishing scientific laws to explain complex phenomena.

Nevertheless, in several cases, using a numerical description is not relevant. For example, the designation of merit of alternatives as judged by an evaluator. Standards of merit may be designated by A, B, C, D, E. Designation by the same letter means equivalent merit, designation by a letter earlier in the alphabetic series means a greater merit. Another example is the representation of colour perception. A number of colours are selected as standard and their given designations are generally referred to with words in a natural language (red, green, blue,...). Any colour which matches a standard colour is then assigned the same designation as the standard. The examples given are not in any way exhaustive, nor have they been rigorously analysed. They show that there are a large number of practical cases in which the attributes and characteristics of objects of the real world are represented not by numbers but by a conventional mark system or by words.

As we will show in the next section, these diverse representations present differences, but share a most essential property, namely, the representing mark refers to the entity represented, relations between the marks correspond to relations between represented entities, and the marks can be used to achieve responses corresponding to the entities they represent. This aspect has been formalized by Finkelstein, who has proposed an extension of the theory of measurement to include such representations [Finkelstein,75]. An outline of his works will now be given in the following paragraph.

Formal presentation

The essence of all measurement and of the non-numerical representations of entities discussed in the preceding paragraph is that they are symbolic representations. A symbol can be defined as the representation of an object or event which has a defined relation to some entity, for the purpose of eliciting a response appropriate to that entity in its absence. The general term for the study of symbols, their uses and relations to the object they represent is known as semiotics. Four aspects of semiotics are generally distinguished.

• Semantics: the study of the meaning of symbols, i.e. their relation to the objects they represent.

• Syntactics: the study of syntax, i.e. the rules of admissible combinations of symbols.

• Pragmatics: the study of the use of the symbols in the whole system in which they are employed from the point of view of the goal of the whole system.

• Sigmatics: the study of the relation between the shape of symbols and the entities they represent as for instance in pictorial symbols.

The present paragraph will be concerned with the first three points. Finkelstein defines a symbolism by considering [Finkelstein,80]:

C= < Q, S, M, R Q , R S , F>
• Q refers to the set of elements of the real world, and R Q refers to the set of relations between them.

• S refers to the set of symbols, and R S refers to the set of relations between them.

• M is a relation from Q to S, and constitutes the representational aspect of the symbolism.

• F is a relation from R Q to R S , and constitutes the relational aspect of the symbolism. Generally F is a one-to-one mapping with domain R Q and range R S . C is a symbolism iff for each k-ry relation R Q ⊂Q k where R Q ∈R Q (k=2,...,n), there is a corresponding relation R S ⊂S k where R S ∈R S (k=2,...,n), such that F: R Q →R S and such that M is a homomorphic mapping under these relations, i.e. iff: for q 1 ,...,q k ∈Q , s 1 ,...,s k ∈S, k=2,...,n R Q (q 1 ,...,q k ) ⇔ R S (s 1 ,....s k ) where R S =F(R Q ) and s 1 =M(q 1 ),...,s k =M(q k ).

(1) Let us consider for example the designation of the merit of students as judged by a professor.Q is the set of students. S is the set of symbols {A,B,C,D,E}. The two important representational and relational facets of the symbolism are described by the properties of M and F. A symbolism is evaluated by the following properties.

• Precision: the correspondence of several elements Q to the same symbol is called ambiguity. The absence of ambiguity is termed precision. It is linked to the injectivity of M.

• Redundancy: the correspondence of more than one symbol to the same element of Q is termed symbolic redundancy. There is no redundancy if M is a mapping.

• Completeness: If all elements of Q have a corresponding symbol in S, i.e. the domain of M is the whole of Q, C is a complete symbolism.

• Relational structure: the value of a symbolism for a relational system increases with the richness of the structure of the relational system and depends on the pragmatic value of the relations in the system.

• Compactness: The ease of processing of a symbol depends upon its compactness, i.e. its small size or duration, so that it requires less time for handling and less space for storage.

• Immunity from error: The form of symbol should be as far as possible immune from error in processing.

e1 e2 e3 M S Q e4 e5 e6 A B C D E R Q R S ~Q > Q = S > S F
It is generally desirable for a symbolism C to be precise, complete and not redundant, i.e. M should be a one-to-one mapping. For the relational structures, some of them are described in the following paragraph.

Fundamental measurement structures

Different authors generally consider three types of scales [Berka,83][Finkelstein,84][Watanabe,91].

• The simplest one performs only an equivalence relation on Q (i.e. ~Q) and S (i.e. = S ). This type of scale is termed a nominal scale.

q 1 ∼ Q q 2 ⇔ M(q 1 ) = S M(q2). ( 2
)
One example is colour matching.

• The second type considers an order relation. It is termed an ordinal scale.

q 1 ≥ Q q 2 ⇔ M(q 1 ) ≥ S M(q 2 ). ( 3
)
One example is the ranking of merit of alternative judged by an evaluator.

• The linear scale is the most popular type in physics. An equivalence relation and a concatenation (or addition) operation are associated to both sets Q and S.

q 1 ∼ Q q 2 ⇔ M(q 1 ) = S M(q 2 ).

(4) q 1 o Q q 2 ∼ Q q 3 ⇔ M(q 1 ) + S M(q 2 ) = S M(q 3 ).

(

) 5
One example is the measurement of the length of an object.

Other classifications are available. Details could be found in [Berka,83].

Moreover, the relation M, that links the empirical domain Q and the symbolic one S is not unique. Any transformation f of M into M' = f(M), that maintains the validity of the representation (i.e. the scale type) is called an admissible transformation. For a nominal measurement, the admissible transformations are any one-to-one mapping. For an ordinal measurement, they are any monotonic increasing mapping. For a linear measurement, the admissible transformations satisfy M' = αM + β with α > 0. These transformations are linked to the meaningfulness of the statements deduced from the measurements. For example, the statement that q 1 is twice as long as q 2 is meaningful, when q 1 and q 2 are measured on a linear scale, even though it is not if q 1 and q 2 are measured on a ordinal scale.

Discussion

Generally, physical quantities are evaluated in a numerical way, i.e. S is the set of real numbers.

The numeric symbolism presents many advantages. It is precise, not redundant, complete, and provides a lot of arithmetic relations. Methods are available to take into account the imprecision of information (error calculus, probability theory). Moreover, numeric measurement are based on an objective operational procedure. Nevertheless, numeric measurement is not always available, because of problems of acquisition or storage of information, because of the multi-dimensional nature of the analysed property, or because it concerns attributes describing human behaviour. In such cases, one is led to make a qualitative description of the observed phenomenon with words of the natural language. Natural language could be seen as a qualitative symbolization. In fact, it is a nominal measurement providing an equivalence relation between the words. At first sight, linguistic symbolization seems less interesting than numerical symbolization. It is less precise, redundant and is subjective in the sense that it can not be experimentally verified in an objective procedure (i.e. independent from the observer). But the linguistic qualitative description is compact (it reduces the problem of the storage of information), easy understandood by human beings (it allows reasoning), and has a richness that the numeric measurement has not, i.e. background knowledge upon the global goal or purpose (i.e. a great pragmatic value).

Foundations of symbolic sensors

Introduction

We have seen in the preceding section that objects of the real world could be described in different manner. Two symbolizations have been considered:

• the numeric measurement (generally obtained by an electronic processing) that provides an objective quantitative description of the objects,

• the linguistic measurement (generally obtained by interrogation of users) that provides a subjective qualitative description of objects.

Therefore, the numeric and linguistic symbolizations are more complementary than competitive, and we will now present a general component, called symbolic sensor, that handles the two representations.The aim of a symbolic sensor is to perform a linguistic symbolization of a phenomenon from a numeric measurement. Therefore, the symbolic sensor acquires a numeric measurement, and then makes the numeric-linguistic conversion itself taking into account the subjectivity of the problem, i.e. the measurement context (global task, interlocutor,...).

• C 1 = < Q, N, M 1 , R Q , R N , F 1 >. It is the usual numerical symbolism,
that links the real world and the numeric world. M 1 depends on the environment through the physical influence variables, e.g. in the measure of distance by time of flight of a wave, the measured distance is linked to the speed of wave propagation, which depends on the temperature.

• C= < N, L, M, R N , R L , F>. It is the linguistic symbolism, that links the numeric world and the linguistic one. M depends on the measurement context through the specified application and the operator. For example, in a temperature measurement problem, the measure 15 o C can be interpreted as cold in a swimming pool context and as very hot for a refrigerator. Moreover, for an eskimo 15 o C is a cool temperature for a bath, while it is quite cold for an african.

• C' = < Q, L', M', R Q , R L' , F'>.
It is the human symbolism, that links directly the real world and the linguistic one. M' takes into account the global environment context. The efficiency of M' is often realized by the simultaneous use of all the senses and of the knowledge of the considered task.

Denote ∆ the composition of two symbolism.

C 2 = C 1 ∆ C iif M 2 = M 1 o M and F 2 = F 1 o F, ( 6
)
where o is the usual composition between two relations.

As shown in figure 2, the symbolic sensor makes the qualitative description in two stages: nu-Real world Numeric world linguistic world

M 1 , F 1 Q, R Q N, R N L, R L M', F' Natural linguistic world L ' , R' L Symbolic Sensor

Human Perception

Pseudo-natural

M,F

meric measurement and numeric-linguistic conversion. It has to provides nearer as possible the same description that performs directly a human. Therefore, in order to implement the symbolic sensor, the symbolism C must be chosen such that C' = C 1 ∆ C. In this sense, the symbolic sensor is an attempt to artificially reproduce the human perception of measurement.

Meaning, description and their fuzzy extensions

The symbolism C 1 is the classical problem of assigning numbers to items of a class of attributes or characteristics of objects of the real world in such a way as to describe them. To express this formally, numeric measurement consists in an operation that establishes a mapping M 1 from a set of entities into a set of numbers. This task is devoted to the sensor in its usual sense and will not be described in further details.

Now, the problem is to define formally the relations M and F that are used in the symbolism C. M is a relation between the set of numeric measurements N and the set of lexical values L (see fig. 3). In the general case, M is a many-to-many relation which is known to be difficult to handle. Therefore, instead of the relation M, we propose to define two mappings called the meaning and the description, detailed in the following paragraphs, which consider P(N) and P(L) [Benoit,91b].

Meaning of a lexical value

The meaning of a lexical value will be defined as an injective mapping from the lexical universe L to the set of the subsets of the numerical domain N.

τ: L → P(N) ∀a ∈ L, τ(a) = {x ∈ N | x M a} ( 7 )
Injectivity ensures that two identical lexical values have the same meaning. The association of a lexical value and its meaning is called a linguistic concept.

b c v w x y z M N L t d a 3.2.

Description of a numeric measurement

The association, for each measurement, of lexical values that characterize it, is called a description.

ι:

N → P(L) ∀x ∈ N, ι(x) = {a ∈ L | x M a} ( 8 )
It will be noted that a measurement may be interpreted by several lexical values.

Links between meaning and description

The relations M, τ and ι are three distinct representations of the same information on the manner the measurements are perceived. Each modification on one of these three relations leads to a modification of the others. Indeed, if a lexical value a belongs to the description of a numeric value

x, it will be equivalent to say that x belongs to the meaning of a.

a ∈ ι(x) ⇔ x M a ⇔ x ∈ τ(a) ( 9 )
With the aim to illustrate our definition, let us consider the following example. Let L be the lexical universe {small, medium, high} with the following meaning:

τ(small) = [0;1.70m] τ(medium) = [1.65m;1.80m] τ(high) = [1.75m;2.50m]
The description of the numeric measurement x=1.78m is ι(1.78m) = {medium, high}.

From crisp concepts to fuzzy concepts

The meaning of a lexical value by a subset of the numerical space, generally an interval, presents two disadvantages. First, the transition from a concept to an other one is abrupt, and leads to a discontinuity in the acquired symbolic information, that may produce brutal variations in the controlled system. Second, the elements that constitute the meaning of a lexical value, do not characterize it in the same way. They describe more or less the considered linguistic concept. It means that one has a graduality in the membership of a lexical value. This phenomenon can be taken into account by extending the crisp relation M into a fuzzy one. The latter is defined by its membership grade µ on the cartesian product L × N. This approach leads to define a fuzzy meaning of a lexical value by a mapping from L to the set of the fuzzy subsets of the numerical domain F(N) [Zadeh,71].

τ: L → F(N) ∀ a ∈ L, ∀x ∈ N, µ τ(a) (x) = µ M (a , x).
(10)

In the same manner, the fuzzy description of a numerical value x is now a mapping from N to the set of the fuzzy subsets of the lexical domain F(L) [Zadeh,71].

ι:

N → F(L) ∀ a ∈ L, ∀x ∈ N, µ ι(x) (a) = µ M (a , x). (11)
The link between the fuzzy description and the fuzzy meaning is formalized by the following relationship:

∀ a ∈ L, ∀x ∈ N, µ ι(x) (a) = µ τ(a) (x). ( 12
)
Figure 4 shows one possible extension of the example given in section 3.2.3. It should be noted that the description provides a set of graduated lexical values. This information is quite complex for some applications. Indeed, in particular cases, it may be reduced to the lexical value whose membership grade is maximum.

Discussion

Generally, the description of a measure is not a singleton of P(L). This aspect may be negative in particular for problems where it is required to transpose operations from the numerical space to the linguistic one. To remedy to this limitation, Luzeaux proposes to define the description by the inverse of the meaning (called the abstraction), that is a mapping from the boolean completion of L (by union, intersection and complementation) to the set of the subsets of the numerical domain.

The completion provides an inclusion order structure and leads to associate to each subset of the numerical space the smallest lexical value that characterizes it [Luzeaux,91]. However, the numerical description of a real object is not always a singleton of N and can also be an interval or a distribution. Therefore, for a measurement problem, we do not require the description to be a singleton.

An other point of interest is the structure of the lexical universe. If one defines only the equivalence (or equality) and inclusion of linguistic concepts, Watanabe shows that two lexical sets (L 1 ,L 2 ), whose completions lead to the same partition of the numerical domain, could be considered equivalent in the sense of nominal measurement [Watanabe,91]. If one chooses a particular lexical set, it is for taking into account an other relation on the linguistic domain, that presents a specific structure. Generally, this relation is an order one.

As mentioned by [Zingales,91], the final objective of any measurement process is to acquire information, that enables to take decision upon a system. Generally, in expert system, the decision is expressed in a sequence of pre-defined classes implying mutual exclusion. But, a feature of most physical systems is the analog nature of the quantities involved, therefore this activity can be seen conceptually as a mapping from a continuum of values into a finite set of intervals. One point of interest of the fuzzy subset approach is that it allows to take into account the continuous nature of the handled variables, inside the symbolic representation that is itself discrete [Dubois,90]. Therefore, choosing the most significant lexical value immediately after the sensor, by taking the concept whose membership grade is maximum, is similar to throwing the baby with the bath water. It is not very interesting, except for the fact that we do not have to define explicitly the threshold between the concepts. This leads to a second point of interest of the fuzzy subset theory, i.e. its capabilities to process and to propagate measurement imprecisions and so to validate the information given back. Then, the latter is defuzzified only when necessary. With regard to the problems of the validation of the fuzzy representation and the meaningfulness of the structure of the lexical set, i.e. the comparison between the empirical relation between fuzzy concepts and the formal relation between membership functions, raised by [Watanabe,91], we can say that the substantiation of the form of the membership functions and the relations between them, is their adequation to the human behaviour by a learning with teacher procedure which will be detailed in the following section.

Creation of linguistic concepts

Introduction

To infer meaningful statement from linguistic information, it is important to define the relations on L and on F(L) too. Similarly to the crisp approach, we will introduce two fundamental measurement structures:

• a nominal fuzzy scale, that performs an equivalence relation,

• an ordinal fuzzy scale, that performs an equivalence and an order relations.

The term fuzzy indicates that the relations associated to the scale concern fuzzy numbers instead of ordinary numbers. On the other hand, the equivalence and order relations are classic ones, and not fuzzy ones.

Nominal and ordinal fuzzy scale

In order to have a nominal scale on the lexical universe, we must define an equivalence relation on it, that corresponds to the one defined on the numerical one. We propose to take:

a,b ∈ L a=b ⇔ µ τ(a) (x)= µ τ(b) (x) ∀x ∈N ⇔ µ ι(x) (a)= µ ι(x) (b) ∀x ∈N . ( 13
)
For the description of numerical measurements, one obtains in the general case a fuzzy subset of L. The equality between two fuzzy subsets of L is then defined by:

ι(x)=ι(y) ⇔ ∀a ∈L µ ι(x) (a)= µ ι(y) (a). ( 14
)
This relationship implies:

x=y ⇒ ι(x) = F(L) ι(y). (15)
The fact that we have not an equivalence between the two parts of the relationship expresses that the nominal numerical scale is more precise than the nominal fuzzy scale.

We must now define an order relation on the lexical universe. We propose to utilize four operators introduced by [Dubois,88]:

µ [τ(a), +∞) (x) = sup{µ τ(a) (y) | y ≤ x }, (16)
µ ]τ(a), +∞) (x) = inf{1 -µ τ(a) (y) | x ≤ y}, (17) µ (-∞, τ(a)[ (x) = 1 -µ [τ(a), +∞) (x), (18) µ (-∞, τ(a)] (x) = 1 -µ ]τ(a), +∞) (x). ( 19
)
Let us illustrate these operators by an example.

So we define a ≤ L b ⇔ µ τ(a) (x) ≤ µ (-∞, τ(b)] (x) ∀x ∈ N. ( 20
)
Having now an order relation on the lexical value and an order relation on the numerical measurement, it seems interesting to compare these two measurements, when only their description is known. We propose to define a distance on F(L) by the following relationship:

(21)

τ(a) ]τ(a), +∞) τ(a) [τ(a), +∞) (-∞, τ(a) [ (-∞, τ(a)] 1 0 1 0 µ µ d ι x ( ) ι y ( ) , (
)

sup a L ∈ µ ι x ( ) a ( ) a L ∈ ∑ µ ι y ( ) a ( ) a L ∈ ∑ - ( ) =

Creating the concepts

As explained earlier, the objective of the symbolic sensors is to provide a linguistic description of the numeric measurements. It leads to define the relations between the numeric measurements and the lexical values. To do this, we propose to define first the meanings of the lexical values. In the crisp approach, it generally leads to making a partition of the numerical domain. Therefore, we propose to extend in the fuzzy case this way of constructing the meaning by defining a fuzzy partition, i.e. satisfying the following conditions [Bezdek,81]:

inf (max a∈ L µ τ(a) (x))> 0 ∀x ∈N (which expresses that L covers N) (22) ∀a,b ∈ L sup x (min(µ τ(a) (x), µ τ(b) (x))) < 1 (which expresses that the linguistic concepts are differentiated), ( 23
) ∀x ∈ N Σ a ∈ L µ τ(a) (x)=1
(that expresses the orthogonality of the concepts).

(24)

A system that satisfies these conditions is called a Fuzzy Information System (F.I.S.) [Tanaka,79].

Obviously, it is a tedious task to specify each meaning of each lexical value. So we are looking for techniques that simplify the creation of concepts. Two methods have been investigated. The first one uses the knowledge of semantic relationships between symbols. The second one needs the knowledge of the meaning of lexical values on particular measurements and then interpolates the meaning for other points.

Generation of the concepts by semantic relationships

The fuzzy symbolic sensor works with several lexical values which are related by means of their semantics. Let us take the example of a temperature measurement. A semantic relationship links the lexical values hot and very_hot due to the order relation on the lexical space corresponding to the order relation on the numerical domain: hot ≤ very_hot. These links between all the concepts should be managed by the sensor itself. We first define, by its meaning, a particular concept, called a generic concept, corresponding to a part of the numerical domain, that is important for the considered task. Defining new concepts leads to giving other lexical values and their meaning. Modifiers, usually called linguistic hedges [Novak,89], can be introduced to perform automatically such an operation. E. Benoit has defined the following operators (more_than, less_than, below, above), within the frame of the pretopology theory [Benoit,91a], to create an ordinal fuzzy scale. The preceding example can be run with other generic functions (e.g. triangle, gaussian) assuming they are known by the sensor (i.e. they belong to the data base). Only the parameters of the generic concept have to changed to reconfigure automatically the fuzzy ordinal scale.

Generation of the concepts by interpolation

This method requires the knowledge of the meaning of lexical values for particular elements of the numerical domain. These particular elements are called characteristic measurements v i , V refers to the set of all the v i 's. For each v i , one creates a fuzzy part F(v i ) having a membership grade equal to 1 for v i , to 0 for the other characteristic measurements

v j ≠ v i . For an element v ∈[v i ,v j ],
we propose to make a linear interpolation in the following manner [Benoit,93]:

µ F(v i ) (v) = d(v j ,v)/d(v i ,v j ) (25) µ F(v j ) (v) = d(v i ,v)/d(v i ,v j ) (26)
These relationships satisfy:

µ F(v i ) (v i )=1, µ F(v i ) (v j )=0, µ F(v j ) (v i )=0, µ F(v j ) (v j )=1. ( 27
)
d refers to a distance relation between two points. In order to create a fuzzy partition, the distance must satisfy: If further information on the shape of the membership function is available, one can use a more general definition:

µ F(v i ) (v) + µ F(v j ) (v) = 1 ⇔ d(v i ,v) + d(v j ,v) = d(v i ,v j ) (28
∀ v ∈ [v i , v j ] µ F(v i ) (v) = f( d( v j , v) / d( v i , v j ) ) (29) µ F(v j ) (v) = f( d( v i , v) / d( v i , v j ) ) (30)
f is an increasing function on [0,1] and satisfies:

f(0) = 0 , f(1) = 1, f(1-a) = 1 -f(a). ( 31
)
Figure 8 : Results with f(x) = 3x 2 -2x 3 .

Note that a new lexical value could be generated by defining the associated characteristic measurements. This principle can be extended to a multi-dimensional measurement. An example is described in section 6.2.

Adaptation to the measurement context

In the previous sections, it has been shown how to build automatically one relationship between the numerical and the lexical domains. It seems obvious that the definition of meanings is the difficult point. A symbolic sensor that is concerned with a temperature measurement problem can interpret the measure "temperature = 15 o C" as a cool temperature. According to the context, the

v 1 v 2 v 3 v 4 v 5 v 6 τ V (a) τ V (b) τ V (c) τ V (d) F(v 1 ) F(v 2 ) F(v 3 ) F(v 4 ) F(v 5 ) F(v 6 ) N τ(a) τ(b) τ(c) τ(d) V µ µ N τ V (a) τ V (b) τ V (c) τ V (d) µ N
description could be false: in a swimming pool context, the temperature is cold; for a refrigerator, it is very hot. Furthermore, the description can differ with the speaker. This last point is very important during the information acquisition time when an expert system is to be implemented.

Therefore, there is a need to configure the sensor according to the context (measurement task, speaker). Formally, taking into account the measurement context is nothing more than adapting the description (and then indirectly the meaning) of the numerical measurement. Two approaches have been developed, a first one based on a functional processing (that makes a global adaptation of the meanings) [Mauris,92], and a second one based on a qualitative learning with a teacher (that makes a local adaptation of the meaning) [Benoit,91c].

Functional approach

Assume the generic concept and the new generated ones are defined on the numerical domain N called the ideal universe. Let N' be the measurement domain and h be a function, called the adaptation function, from N' to N. The description of a measurement for crisp set is now:

L 1 = ι(h(x)) if x ∈τ(L 1 ) (32)
To run this approach, the adaptation function should be sent to the symbolic sensor. However, all adaptation functions should have specific properties that preserve the coherence of configuration informations. Especially, the generic concept definition point should not be changed by the adaptation function, furthermore the description should remain linear around this point. Let m c be the generic concept definition point, the two previous properties lead to:

h(m c ) = m c and h'(m c ) = 1 (33)
Effects of the adaptation function on the measurement domain are called semantic properties (compressing or expanding the definition domain, expanding after a particular measurement...).

The choice of a "good" adaptation function (i.e. having particular semantic properties and the previous mathematical properties) is not so easy. One solution is to choose an adaptation function having the desired semantics, then apply a transformation to get the mathematical properties. Let g be

L N τ L 1 ι • • N' x • h
a function with the desired semantics at point x p , then the adaptation function can be defined as follows (it is assumed that g'(x p ) ≠ 0): h(x) = a.g(x-m c + x p ) + b with a = 1 / g'(x p ) and b = m c -g(x p ) / g'(x p ) (34)

From these considerations, let us give four examples of functions g with interesting semantic

properties:

• expand_before_expand_after g(x) = argsh(k.x)

• compress_before_compress_after g(x) = sh(k.x)

• compress_before_expand_after g(x) = sh(k.x) if x ≥ 0 g(x)=argsh(k.x) else • expand_before_compress_after g(x) =argsh(k.x) if x ≥ 0 g(x) = sh(k.x) else
These functions have been chosen due to their asymptotic properties and their behavior around the origin (here x p = 0). Figure 10 shows resulting adaptation functions h for the generic concept definition point in 5 m, and presents the membership functions for a symbolic sensor dealing with seven concepts defined from a gaussian generic one, distance_is_correct, whose definition point is in 5 m: the adaptation function is obtained from the g compress_before_expand_after function.

Qualitative learning with a teacher

The principle is illustrated in the following figure. It is based on the qualitative comparison be- tween the description of the sensor (sc) and the description of the professor (sp) for the same numerical input x.

Figure 11 : Principle of learning with a teacher.

The qualitative comparison e takes its value in the set of signs S = {-, 0, +} usual in qualitative analysis. In the present instance, we restain ι sp (x) to a singleton, i.e. an element of L , so the result is obtained from the order relation on L.

e = + if ι sp (x) ≥ L ι sc (x) e = -if ι sc (x) ≥ L ι sp (x) e = 0 if ι sp (x) = L ι sc (x)
The qualitative comparison is used to change the meaning of each lexical value, and of course the sensor's descriptions. The idea is to change the meaning in order to obtain a qualitative feedback of the sensor's description according to the professor's description. The qualitative feedback can be easily obtained with the following control strategy. Figure 12 : :Action of increase on the concept sf.

For the temperature T 0 , before the action of the teacher the description is ι(T 0 )={cold(0.6); mild(0.4)}, after the qualitative learning we obtain ι(T 0 )={cold(0.4); mild(0.6)}.

Handling measurement imprecisions

In the previous section, we have considered the conversion of a precise numerical measurement into a lexical value. In reality, the measurement process is not ideal, and the numerical values given back by the sensor are imprecise. The aim of this paragraph is to take into account the metrological performances of the sensor in the numeric-linguistic conversion. To do this, we will first consider a classification of the different errors.

Different types of errors

We consider three types of errors:

• systematic errors, created by erroneous referent values, by the electronic signal processing or by particular conditions of operation.

• regular errors, that produce a measure close to the true value. They come from the noise of circuits and from slight uncontrolled variations of referent parameters.

• aberrant errors, leading to a measured value which has nothing in common with the observed situation. They are due to important faults in electronics, to brutal variations of operation or to a specific configuration of the sensor.

The problem is how to recognize these types of errors. It requires information about the sensor operation, whose performances must be known.

Characterization of the sensor performances

We propose a functional approach that is linked to the usual description of the performances and is coherent with the fuzzy subset theory [Mauris,92]. Therefore, three functions called device functions are defined to characterize the imprecision of the sensor:

• the precision function, that is the probability distribution of the experimental measurements, and reflects the estimation performances of the sensor for regular operating.

• the detection function and the validity function, that describe respectively the detection performances of the sensor and the validity of the measure. They can be interpreted as an a priori and as an a posteriori probability of regular measurements.

These functions could be obtained by theoretical calculus or by experimental analysis. Note that the detection function requires knowledge of the sensor's performances, that depend on the operating configuration. The validity function requires internal or external additional data (i.e. information redundancy), providing information upon the observed situation, in order to do a coherence test of the measured value, that leads to a validity rating of the measurement.

Management of errors

The problem is how to take into account the numerical measurement errors in the numeric-linguistic conversion. Our choice is to associate to a lexical value a membership function that integrates elements of a different nature. The first type of elements are information external to sensor, linked to the designated purpose for linguistic representation. The second type are imprecision measurements, that have to be performed in a way coherent within the frame of fuzzy theory. In the present instance, we propose to process the imprecision measurements in accordance with the type of errors.

Management of systematic errors

We mean to process this type of errors with a function q s , that corrects the numerical value. In the case of correction of systematic errors by a standard, q s may simply be a subtraction by a constant or a multiplication by a scale factor. In the most complex cases, q s may be a parametric function depending on external physical quantities (temperature, pressure,...) or may be given by a correction table.

Management of regular errors

In the crisp approach, the border between two concepts is quite abrupt. Therefore, because of the statistical variations of the numerical value, the lexical value obtained in return varies a lot. The considered procedure may taken into account the precision of the sensor in the construction of the fuzzy partition by smoothing transition between concepts. This operation is similar to a frequential filtering. Therefore, we propose to convolute meanings of concepts by the precision function, which constitutes the impulse response of the symbolic sensor. Let us illustrate this procedure by an example. Let us consider a distance sensor, that has the following precision function:

(35)
The concept far is defined by the crisp interval 40cm-60cm. If we have a precision of 2cm around the 50cm measurement, we obtain for the modified concept a fuzzy one. In the preceding case, the sensor was quite efficient and the change is light. Let us observe now more extreme cases, in order to understand the effect of the convolution by the precision function on the basic concept. In the last case, the fuzzy concept has not a modal value, i.e. the value 1 is not reached. The low membership grade expresses the low credibility of the lexical value, which is in accordance with the precision of the sensor. This information is also an incitement to redefine the basic concept.

p x ( ) 1 σ xp 2π -------------------exp x 2 - 2σ xp 2 ------------     × = 0.

Management of aberrant errors

Aberrant measurements correspond to values, that share nothing with the observed reality. We will distinguish two cases. The a priori aberrant values, determined by the non-membership to a nominal operating area. These measures must lead to a small membership grade of concepts, according to their small confidence value. This result is quite similar to a temporal filtering. Therefore, we mean to multiply the meaning of concepts by the detection function, that constitutes information about the normal operating area of the sensor. Let us illustrate this operation by the following example. The second case is the a posteriori aberrant measurements, that are values belonging to the nominal operating area of the sensor, but that share nothing with the observed reality. To detect these faults, information about the acquired values, that will be characterized by a validity function, is required. The validity is obtained by cross-checking with other internal or external information upon the measurement processing. Finally the meaning of the modified concepts is deduced by multiplication of the basic concepts by the validity function.

Implementation

The following figure presents the different functions of a fuzzy symbolic sensor. The analog part makes the usual sensing. The numeric part acquires a numerical measurement of the considered

µ τ(s) (d) µ τ(s) (d) µ τ(s) (d)
physical quantity with possible correction and compensation of the measures. The association of these two parts leads to sensors usually called smart sensors. The fuzzy symbolic part generates the meanings of the concepts by taking into account the measurement imprecisions and the measurement context. The device functions (precision, detection, validity) depend on the configuration of the sensor and act with specific operators (convolution, multiplication) in the numeric-linguistic conversion. In output, the fuzzy sensor provides numeric measurements and their validity, and a linguistic description of the considered situation. Therefore, it constitutes a general component usable for many types of systems. It will be noted that the proposed mechanism gives back a small membership grade when the partition is too fine or covers an area that is different from the range of the sensor. So the membership grade is shown as a global validity index of the concept fusing linguistic uncertainty and numeric measurement imprecisions.

Applications

This section describes two implementations of fuzzy symbolic sensors. The first one concerns an ultrasonic range finding sensor. After detailing the measurement principle, we focus our attention on the management of numeric errors in the numeric-linguistic conversion by means of the device functions (see section 5.3.). The used method for creating the concepts is based on the definition of the meaning of a modified generic concept (that integrates the accuracy of the sensor)

and the use of linguistic operators described in section 4.3.1. In output, the fuzzy sensor gives back the numeric measurement and its validity, and the linguistic description of the considered distance.The second implementation of a fuzzy symbolic sensor is a colour matching sensor which tries to copy human eyes. In this perspective, the software sensor referred to here works with the three usual components of colour (red, green, blue). So the numeric measurements are three-dimensional, and we extend the interpolation procedure used in the mono-dimensional case (see section 4.3.2.) for creating the meanings of the concepts, whose modal values are given by a learning with teacher procedure described before (see section 4.4.2.). In output, the fuzzy sensor displays the linguistic description of the colour of the considered object.

Ultrasonic range finding sensor

Measurement principle

Two small ultrasonic transducers which have a frequency resonance of about 40kHz have been used. The emitter is linearly modulated in frequency with a frequency sweep rate of α=∆F/T r . As sound travels through air between the receiver at a speed of v=340m/s, the receiving transducer collects a frequency modulated signal delayed by a time t 0 =2d/v (d: distance to the obstacle). The two signals (emission and reception) are made to beat together in a non linear device (i.e. a multiplier)

and the beat note is found to contain two distinct tones f a and f b .

Figure 17 : Principle of a linearly modulated range finding sensor.

t f f 2 f 1 f p t 0 T r t ∆f=|f emitted -f received | f b f a t 0 ∆F T r /2 -T r /2 0 T r 2T r 3T r /2 emissionêêê reception
We have the following relationships:

(36) (37)

Sensor processing

In order to obtain the distance d, the frequency f a must be numerically acquired. We propose a solution based on a complementary use of analog processing and digital processing implemented on a single processor board. The emission consists in generating a triangular signal by integration of a rectangular signal provided by a timer of the board. The received signal is first amplified and then multiplied with the emitted one. Therefore, the multiplier output provides a beat note with two distinct tones: f e +f r and f e -f r . After going through a low-pass filter, a sinusoïdal signal at frequency f a =f e -f r is obtained.

Then a TTL output OS is generated in order to perform a period acquisition. As frequency measurements are not so easy, a microprocessor based period measurement has been implemented. Assuming that T t is the sum of all the measured values (in reference clock ticks), f ref is the reference frequency and N the number of samples, the distance can be computed as:

∆F T r ------- = f a α t 0 × 2 ∆F T r ------- × d v --- × = = with N f a T r t 0 - ( ) × 2 ∆F T r ------- × d v --- × T r 2d v ------ -     × = =
(38)

K is a symbolic constant defined at the assembly level, so that only one multiplication and one division are necessary to compute the distance.

Representation of the sensor performances

The experimental results obtained with the following configuration (∆F=16kHz, T r =15ms, t' 0 =3ms) for an obstacle perpendicular to the ultrasonic beam lead to the following approximated device functions. With regard to the validity function, its formulation requires more attention. We look for a function, that has for domain the numeric space and for range the unit interval [0,1]. A value close to 1 means a good validity for the considered measurement, then a value close to 0 corresponds to a not very reliable measurement. The expression of the validity functions necessarily originates in some sort of redundancy. For the implemented ultrasonic sensor, we have a second value linked to the distance, that is the number of cycles of the tone f a :

(39)

To define the validity, we propose to compute the theoretical number N th corresponding to the calculated distance d obtained by the measurement average f average of f a , and the number N exp corresponding to cycles which frequency is closed from f average (for example, equal to f average with 10% of error).Then, the validity function isobtained by: -------------------------------------------------K N × The distance measurements vary a lot and the validity is low. It is due to the reflection, that is not principally focused on the sensor. In order to perform the actions of configuration, acquisition and processing of the information in a simple manner, E.Benoit has developed a rule based procedural language, called PLICS (prototype of integrated language for symbolic sensors) [Benoit,93]. Therefore, users work in a language close to natural language, as shown in the following example. The method used for creating the concept is based on the definition of a modified generic concept (that integrates the accuracy of the sensor) and the use of the linguistic operators (more_than, less_than, above, below) (see section 4.3.1.). The obtained structure for the symbolic informations is an ordinal fuzzy one (see section 4.2.).

d v sound T r × f ref × N × ∆F T t × -
f v = N exp /N th d(m) N 2 ∆F T r ------- × d v --- × T r 2d v ------ -     × 2 ∆F T r -------d × × ≅ = (t 0 << T r ) f v =N exp /N th . ( 40

Processing linguistic information

The detection function is equal to 1 in the interval [0.05m;1.4m], so that it does not affect the membership grades in this range. The validity can not be displayed because it is obtained a posteriori.

The next figure shows respectively the numeric value, the validity and the lexical value (that corresponds to the higher membership function grade) registered for a robot sweep over a plane sup-

Colour matching sensor

Human and artificial perception of colour

The sensing of colour has been known scientifically, only since Newton's experiment on prisms.

His works and those of his successors have demonstrated that information linked to colour sensing is described by the spectral energy distribution between 400nm and 700nm. This interval is called the visible spectrum. Human beings perceive electromagnetic light beams by four types of photochemical transducers: three cones for day vision and one rod for night vision. The photometric sensors give back information in relation to the received energy:

(41) with λ the wavelength, r the spectral sensitivity of the sensor and s the spectral energy distribution of the received wave. The sensation of colour is generated by the different spectral sensitivities of the cones. The "blue" cones detect short wavelength, whereas the "green" and "red" cones detect respectively medium and long wavelengths. Mathematically, colour information is represented by a three-dimensional vector, and the associated measurement universe is called the colour space. The artificial sensing (for example the video camera) is based on three photometric transducers that recreate the effects of red, green and blue cones. The responses of the detectors are normalized between 0 and 1, and then the colour space is simply a unit cube (R,G,B). Formally, every point of the cube marks a different colour sensation.

In practice, the lexical values of colour (red, blue, green,...) correspond to a partition of the cube in many parts. At this stage of our presentation, it will be noted that the partition of the cube is not an objective procedure, but a subjective one, that depends on users and considered applications. Moreover, other representations, separating characteristics of colour like brightness, saturation and tint can be considered. Nevertheless, associated transformations introduce an important knowledge on the mechanism of the human perception of colour. Therefore, we will use the simple cubic representation (RGB) and a learning procedure for colour concept formation.

Processing linguistic information

The idea is to extend to the three-dimensional case the interpolation method developed for creating a mono-dimensional partition from characteristic measurements (see section 4.3.2.). One begins by partitioning the cube in tetrahedrons using Delaunay's triangulation method. For partitioning the whole measurement universe, the vertices of tetrahedron must be characteristic points. Then, the smallest partition contains eight elements, and the vertices of the cube are characteristic measurements. The lexical set and the associated meanings are defined in the following manner, and lead to a nominal fuzzy scale (section 4.2.).

µ F(v c ) (v)=µ F(v c ) (x,y,z)=ax+by+cz+d, (42)
a,b,c,d are determined by the system of four equations given by the four vertices of the tetrahedron. The fuzzy subset F(v c ), so defined by parts on each tetrahedron, is called a fuzzy point. The meaning of a lexical value is then deduced from the union of fuzzy points associated to the set V a of characteristic measurements describing the considered lexical value:

µ τ(a) (v) = Σ v c ∈V a (µ F(v c ) (v)). ( 43
)
As mentioned before, the proposed method does not take into account all the information on the human perception of colour. Missing information will be introduced by learning with an operator.

He will indicate new colour lexical values and their associated characteristic measurements. For building Delaunay's triangulation, a specific algorithm has been used to create the new partition used by the fuzzy sensor [George,89].

Implementation and experimentations

The implemented sensor is a software one, that assesses the colour of an image using the three components RGB given by a camera. In this case, the software is the instrument. Associated to a shape recognition system, it can give a meaning to objects such a blue pen or a yellow cube.

Principle and description

The sensor use the three-dimensional interpolation method described before. First, the operator defines the lexical set (for example: black, red, green, blue, cyan, magenta, yellow, white) and the associated characteristic points v i (r i , g i , b i ), chosen on the image by the cursor. Then, the software determines the description of the colour of every point.The sensor presents a communication tool, which allows to perform the learning procedure and the management of the results. The acquisition of the three components RGB is provided by a camera, and the analysed point is determined by the position of the cursor on the image. • Fichiers (file): this menu can load a colour image, or the configuration containing the set of characteristic points and their associated descriptions.

• Image: this menu selects the different modes of image vizualisation,i.e. displays in gradations of grey or in pseudo-colours of the original image or of the interpreted image. If one displays the description of a point for a particular lexical value, black means that the lexical value does not belong to the description, white means that the lexical value belongs totally to the description of the considered measurement. If one displays the description for all lexical values, the colour of the pixel is that of the greater membership grade concept.

• RVB (RGB), couleur (colour), Val (%): in this part of the communication box are included numeric values in the range 0-255 of the three components (red, green, blue) and a lexical value (that corresponds to the greater membership grade) and its associated membership grade in percentage.

• Detail: displays all the lexical values and their associated membership grade.

• Modifie (modify): Manages the monitoring procedure. The user selects adapted lexical values for specified points. The software automatically builds the nominal fuzzy scale.

Application

For example, we analyse the following colour image I, represented in gradations of grey for reproduction purposes. It shows a scene composed of four rectangular objects respectively yellow, red, green, blue (down to up): a blue pen (left), a red pen, a grey ring and a white square, in which is written a blue line is drawn and the word "cubes" is written in red. The learning procedure has been performed on six points situated on the background picture, on the ring, and on the four rectangles. The lexical set used here is {black, grey, blue, red, green, yellow, magenta, cyan, white}.

The characteristic colours and their associated lexical values can be seen as follows. Note that the learning points are quite far from the initial characteristic points (i.e. the vertices of the cube RGB), which means that the starting nominal scale is not adequate to the image. Moreover, before monitoring, black is the most meaningful lexical value for the first four points.

Symbols

Blue

Conclusion

The final aim of any measurement process remains the acquisition of evidence that enables to understand and possibly formulate decisions upon some matter. Therefore, numerical data about the measured quantities are ultimately turned into a qualitative response to the requirements that started the measurement process. This decision is generally made by a natural intelligent entity (i.e.

an operator) or by an artificial intelligent entity (i.e. an expert system). It is in general expressed in a binary form (good or bad, equal or not equal,...) or in a sequence of pre-defined lexical values (such as for example: mild, hot, very_hot, cold, very_cold). Our approach is to implement these The fuzzy set theory proposes an interesting frame for the treatment of symbol graduality, measurement imprecisions and validation, and it allows to take into account the measurement context.

This approach leads to a specific structure for the sensors, called then fuzzy symbolic sensors. For instance, both an ultrasonic range finding sensor and a colour matching sensor have been successfully implemented. The former uses a procedure of management of errors and a procedure of creation of the concepts by semantic relationships. The latter uses an interpolation method for creating the concepts by learning with a teacher.

As a conclusion, the proposed structure for the fuzzy symbolic sensors allows conventional sensing, description, adaptation to the measurement context and treatment of errors. Hence, we can consider cases where measurement systems involve a lot of sensors. In such situations, we are faced with new problems: the concept level assessment and organization, the choice of the appropriate constituent devices and the optimal configuration of the sensors, the validation of data from the point of view of the global system. For all these aspects, the new ways opened by symbolic representations seem promising, and they are being developed in our laboratory.

Figure 1 :

 1 Figure 1 : Example of a symbolism. M associates to any student a letter that represents his academic level. Designation by the same letter (= S ) means equivalent merit (~Q), designation by a letter earlier in the alphabetic series (> S ) means a greater merit (> Q ).

Figure 2 :

 2 Figure 2 : Object of symbolic sensor.

Figure 3 :

 3 Figure 3 : Relation between N and L.

Figure 4 :

 4 Figure 4 : Link between meaning and description.

Figure 5 :

 5 Figure 5 : Operators for comparison of fuzzy numbers.

  Figure 6 : Example of an ordinal scale.

)Figure 7 :

 7 Figure 7 : Interpolation method.

Figure 9 :

 9 Figure 9 : Adapting the sensor to the environment.

Figure 10 :

 10 Figure 10 : Example of adaptation.

  if e = + then u = increase if e = -then u = decrease if e = 0 then u = maintainThe semantics of the control actions on u are respectively to increase, decrease or maintain the sensor's description. Now, in order to complete the approach, the function increase, decrease, and maintain have to be defined. The function maintain is obvious since no action is performed. E. Benoit has defined two functions increase and decrease, that modify two neighbouring concepts [Benoit, 91a and 93]. In fact, these operators, based on the pretopology theory, induce a local modification of the partition. An illustration of the action of this sort of operators is shown hereaf-

Figure 13 :

 13 Figure 13 : accuracy of sensor σ=2cm.

Figure 14 :

 14 Figure 14 : accuracy of sensor σ=10cm and σ=30 cm.

  f

Figure 15 :

 15 Figure 15 : Action of the detection function.

Figure 16 :

 16 Figure16: General structure of a fuzzy symbolic sensor.

Figure 18 :

 18 Figure 18 : Sensor processing.

Figure 19 :

 19 Figure 19 : Principle of numeric distance acquisition.

  α

Figure 20 :

 20 Figure 20 : Device functions of the ultrasonic sensor.

)

  When the obstacle-sensor configuration is coherent with the model, i.e. obstacle perpendicular to the ultrasonic beam and sensor configuration parameters (∆F, T r , t' 0 ) adjusted to the distance to the obstacle, then N exp =N th and f v = 1. When the obstacle is inclined or the parameters not adapted to the situation, or,..., then N exp << N th and f v = 0. For instance, the robustness of this function has not been analysed. Examples of measurements obtained by the sensor are shown hereafter.

Figure 21 :

 21 Figure 21 : distance and validity of measurements for a plane obstacle perpendicular to the beam.

Figure 22 :

 22 Figure 22 : distance and validity of measurements for a plane obstacle inclined at 30 o .

Figure 23 :

 23 Figure 23 : Example of creation of concepts.

Figure 26 :

 26 Figure 26 : Triangulations of the cubic colour space.

Figure 27 :

 27 Figure 27 : Monitoring board of the colour sensor.

  figure shows the original image I and the "red" image Ired. Pixels, whose description contains

Figure 28 :

 28 Figure 28 : Images I and I Red

  intelligent capabilities directly in a new type of sensors called symbolic sensors. The latter does not only perform the sensing, i.e. the numerical acquisition of a physical quantity with possible correction and compensation of the measures (usually called smart sensing). It also performs the perception, i.e. the definition of meaning of sensed signals by the assignment of symbols (e.g. predefined lexical values). This paper sets the theoretical foundations of the symbolic sensors, as an extension of the measurement theory, by establishing in a formal way the relationships between the numerical and lexical domains, by means of two mappings called description and meaning. In practice, a symbolic sensor involves two stages: the usual numeric measurement and the numeric linguistic conversion. It entails the definition of the meaning of the lexical values by the user, and the description of the numeric measurements by the formal link between the meaning and the description.The latter consider the set of the subsets of the numerical space and the set of the subsets of the lexical space.


Cyril Labbé
email: cyril.labbe@imag.fr

Dominique Labbé
email: dominique.labbe@iep-grenoble.fr

Are the major bibliographic databases reliable?

Keywords: Bibliographic Databases, Scientific Conferences, Data Quality, Fake Publications, Text-Mining, Inter-Textual Distance, Google Scholar, Scopus, WoK

It is generally assumed that fee paying bibliographic databases guarantee the quality of the data they sell. This technical report shows that this assertion can be challenged. It demonstrates a software method of detecting duplicate and fake publications. The charged-for services (such as IEEE Xplore) accept and index these kinds of publications.

Introduction

Editorial databases such as Scopus (Elsevier) or ISI-Web of Knowledge (WoK Thomson-Reuters) require access fees. They are generally regarded as reliable tools for bibliographic research and for the evaluation of researchers, laboratories, and universities. This is mainly because they store only publications in journals and conferences in which peer selection is supposed to guarantee the quality of the indexed publications. Data quality would also seem to be secured by the publisher of journals and of conference proceedings. Therefore, to our knowledge, the quality of these bibliographic databases has never been questioned.

Text-mining tools are presented and used to detect problematic or questionable papers such as meaningless publications. The method has enabled the identification of dozens of bogus scientific papers.

Corpora and methods

All the texts used are present in bibliographic databases (Scopus and WoK). They are either available from the conferences' web sites, or from the publishers' web sites, like the Institute of Electrical and Electronic Engineers (IEEE) or Association for Computing Machinery (ACM) websites. Three a priori above-reproach corpora: Texts, available online, from three recent conferences were chosen:

• Corpus X: The texts were downloaded from the site ACM Digital Library: http://portal.acm.org/.

Organizers state : 126 "Full papers" (10 pages), 165 "short papers (4 pages), 20" demo papers "(2 pages) or a total of 311 documents. Announced acceptance rates for this edition and the various categories of publications are 13.3%, 17.5% and 52% respectively.

• Corpus Y: The texts were downloaded from the site of the IEEE: http://ieeexplore.ieee.org/. This corpus comprises 150 "regular papers" (4 pages). Official acceptance rate for this edition is 28%.

• Corpus Z: The texts were downloaded from the site of the Conference. Organizers count: 159 documents, which are divided into 3 tracks: one track with 58 documents (acceptance rate 18.4%), 33 documents for the second track (acceptance rate 16.1%), 30 + 6 documents for the last track (acceptance rate unknown), and 32 demonstrations (36% acceptance rate). The used corpus for this conference comprises 153 documents (121 articles and 32 "demos").

Automatically generated, deliberately faked texts: A specific corpus "Antkare" is added.

It contains 100 documents automatically generated using the software SCIgen (http://pdos.csail.mit.edu/scigen/). This software, developed at MIT in 2005, generates random texts without any meaning, but having the appearance of research papers in the field of computer science, and containing summary, keywords, tables, graphs, figures, citations and bibliography.

For the Antkare experiment, SCIgen was modified so that each article had references to the 99 otherscreating a link farm. Thus, all these texts have the same bibliography. Google Scholar retrieved these faked online articles and, as a result, Ike Antkare's H-index reached 99, putting him in the 21st position of the most highly cited scientists [START_REF] Labbé | Ike antkare, one of the great stars in the scientific firmament[END_REF].

Texts Processing: Pdf files are converted to plain text files by the program "pdftotxt" (free software unix and windows version 3.01) that extracts the text from pdf files. During this operation, figures, graphs and formulas disappear, but the titles and captions of these figures and tables remain. To prevent the 100 identical references in the corpus Antkare from disturbing the experiments, the bibliographies have been removed from all texts in all corpora.

The texts are segmented into word-tokens using the Oxford Concordance Program commonly used for English texts [START_REF] Hockey | OCP Users' Manual[END_REF]. In fact, the word-tokens are strings of alphanumeric signs separated by spaces or punctuation.

Text mining tools

Distances between each text and all the others (inter-textual distances) are computed. Then these distances are used to determine which texts, within this large set, were closer to each other and may thus be grouped together (cluster analysis).

Inter-textual distance

The distance between two texts A and B is measured using the following method (for a detailed presentation, see [START_REF] Labbé | Inter-textual distance and authorship attribution corneille and moliere[END_REF][START_REF] Labbé | La distance intertextuelle[END_REF][START_REF] Labbé | Experiments on authorship attribution by intertextual distance in english[END_REF][START_REF] Labbé | La classification des textes. Comment trouver le meilleur classement possible au sein d'une collection de textes ? Images des mathématiques[END_REF]). Given two texts A and B, let us consider:

• N A and N B : the number of word-tokens in A and respectively B, ie the lengths of these texts;

• F iA and F iB : the absolute frequencies of a type i in texts A and respectively B;

• |F iA -F iB | the absolute difference between the frequencies of a type i in A and respectively B;

• D (A,B) : the inter-textual distance between A and B is as follows:

D (A,B) = i∈(A∪B) |F iA -F iB | with N A = N B (1)
The distance index (or relative distance) is as follows:

D rel(A,B) = i∈(A∪B) |F iA -F iB | N A + N B (2)
This index can be interpreted as the proportion of different words in both texts. A distance of 0.5 means that the texts share 50% of their words-types.

If the two texts are not of the same lengths in tokens (N A < N B ), B is "reduced" to the length of A:

• U = N A N B is the proportion used to reduce B in B • E iA(u) = F iB .U is the theoretical frequency of a type i in B
In the Equation (1), the absolute frequency of each word-type in B is replaced by its theoretical frequency in B :

D (A,B ) = i∈(A∪B) |F iA -E iA(u) |
Putting aside rounding-offs, the sum of these theoretical frequencies is equal to the length of A. The Equation (2) becomes:

D rel(A,B) = i∈(A∪B) |F iA -E iA(u)| N A + N B
This index varies evenly between 0 -the same vocabulary is used in both texts (with the same frequencies) -and 1 (both texts share no word-tokens).

In order to make this measure fully interpretable:

• the texts must be long enough (at least more than 1000 word-tokens),

• one must consider that, for short texts (less than 3000 word-tokens), values of the index can be artificially high and sensitive to the length of the texts, and

• the lengths of the compared texts should not be too different. In any case, the ratio of the smallest to the longest must be less than 1:10.

Inter-textual distance depends on four factors. In order of decreasing importance, they are as follows: genre, author, subject and epoch. In the corpora presented above, all texts are in the same genre (scientific papers) and are contemporary. Thus only the authorial and thematic factors remain to explain some anomalies detected by the calculus and the classification. An unusually small inter-textual distance suggests striking similarities and/or texts by the same author.

Automatic clustering

The inter-textual distances allow clustering according to similarities between texts (classifications) and graphical representations of their proximities [START_REF] Sneath | Numerical Taxonomy[END_REF][START_REF] Benzecri | L'analyse des données[END_REF][START_REF] Roux | Algorithmes de classification[END_REF][START_REF] Roux | Classification des données d'enquête[END_REF]].

An automatic cluster analysis is performed on the inter-textual distance matrix, using the following method. The algorithm proceeds by grouping the two texts separated by the smallest distance and by recomputing the average (arithmetic mean) distance between all other texts and this new set, and so on until the establishment of a single set.

These successive groupings are represented by a dendrogram with, in ordinates, the relative distances corresponding to the different levels of aggregation (see Figure 2 and3).

To correctly analyze these figures, it must be also remembered that:

• whatever their position on the horizontal axis, the proximity between two texts or groups of texts is measured by the height at which the vertices uniting them converge, and

• the technique sometimes results in "chain effects": some similarities between texts are indistinguishable because the vertices connecting them are erased by aggregations performed at a lower level.

Detection of forgeries and duplicates in the three corpora

Intra-corpus distances: For each corpus, distances are ranked by ascending values and distributed in equal interval classes. Fig. 1 shows these four distributions. The X, Y and Z corpora have the classic bell curve profile suggesting the existence of relatively homogeneous populations (here a large number of contemporary authors writing in a similar genre and on more or less similar themes). X and Z have a comparable mean/mode and a similar dispersion. In contrast,

• Y has a high average distance and a higher dispersion around this mean, indicating heterogeneity of papers, but also suggesting the presence of anomalies (these two explanations are not mutually exclusive);

• On the left of the graph, the curve with three modes is the distribution of distances between the 100 faked texts by Ike Antkare. This trimodal distribution suggests the existence of two different populations within the texts generated by SCIgen: a small group with very low internal distances are centered on 0.2 -these are short texts (about 1600 word-tokens) -and the other group, with a greater number of texts, containing longer texts (about 3000 word-tokens): Their internal distances are centered on 0.38. The third mode is the distance between these two groups. Therefore it can be inferred that SCIgen uses at least two different ways to generate texts. This is confirmed by the classification (see Figures 2 and3).

Classification of corpora:

The classification and its representation by a dendrogram (Figure 2) show 4 main groups:

• In the center, a large body (C) includes all texts Z and almost all X texts.

• On the right (D) and on the extreme left (A), the texts of the Y Conference meet at the higher levels, confirming the heterogeneity of this conference.

• There is very little intermingling between on one side X, Z and Y on the other side. In other words, most of the papers presented at the Y conference are not of the same nature as those presented at the other two conferences.

• All the chimeras generated by SCIgen for Ike Antkare are grouped in B into two homogeneous groups and connected at a very low level. Thus, SCIgen texts are not "close" to natural language and are distinct from the scientific papers they are supposed to emulate.

Four "genuine-fake" texts: In the dendrogram in Figure 2, the number (1) branches are four Y texts that are clustered within the corpus Antkare. These four texts are "genuine" publications because they have, at least formally, been selected by peer reviewers. They are available (on payment) and referenced by sites of scientific publishers (WoK, Scopus, IEEE). But these texts are fake publications because they have the characteristics of the texts generated using SCIgen: absurd titles and figures, faked bibliographies, mixture of jargon with no logic.

| | | ! ! ! ! ! ! ! ! ! ! ! !! ! !! ! !! ! !! ! ! ! ! ! ! ! l l l l ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! | |

Other SCIgen texts in IEEE

The search engine http://ieeexplore.ieee.org/ offers a functionality ("More Like This") to research texts similar to a chosen paper. We applied it to 3 pseudo papers out of the four found in corpus Y. On the day of the experiment (April 22, 2011), this functionality returned 122 different documents. We call this new corpus More Like This "MLT" and we applied to it the same tools. To make this cluster analysis readable, the dendrogram, reproduced in Figure 3, relates only the comparison of this new corpus with the Antkare texts (to detect some new pseudo texts) and with those of Z (containing only genuine texts).

The corpus MLT includes:

• 82 new pseudo papers grouped with Ike Antkare documents (Group C Figure 3).

C1 contains 17 texts very similar to those of Ike Antkare, but slightly "distorted" to pass the peer selection. Sometimes the titles are appropriate to the subject of the conference, some abstracts are more or less coherent, and few figures have been changed, but most of the writing remains SCIgen.

C2 contains 65 twins from those of Ike Antkare-the texts generated by SCIgen were accepted, without any change, by the conference organizers.

C3 and C4 : twice, identical pseudo publications were presented under a different title, by the same authors to two different conferences!

• 41 genuine papers are classified into two groups (A and B).

After verification, in these 41 texts at list one bibliography in one of these papers comes from SCIgen. The smallest distances: groups A1, A2, A3, B1 and B2. A2 branches are three very similar papers by the same authors in three different conferences. A1, A3 and B2 are pairs of texts by the same authors on very related topics. B1 is a pair of papers by the same authors on the same topic at two different stages: first presented in a conference then enriched and published in a scientific journal.

A "nearest neighbor" classification (knn classification [START_REF] Cover | Nearest neighbor pattern classification[END_REF][START_REF] Meyer | Text mining infrastructure in r[END_REF] with k=1) was tested to verify the feasibility of automatic detection of pseudo papers. For this experiment, the 100 documents of the Ike Antkare corpus and the 121 articles of the corpus Z respectively represent the "fake" and "genuine" papers class. For each text of the corpus "More Like This" the distances to the 221 reference texts are computed and the text is assigned to the group of its nearest neighbor (pseudo or genuine).

Texts examination confirms that, using this method, all pseudo items (SCIgen texts and modified SCIgen texts) are classified with the corpus Antkare.

Conclusion

We selected three international conferences with scientific committees, 614 papers in all. These three conferences show stringent selection rates and two of them (X and Z) are considered among the most rigorous in their fields. In a second step, we added 122 texts selected by the IEEE as "close" to the 4 pseudo texts detected in Y.

This very limited trial gives:

• At least 86 SCIgen papers in IEEExplore.

• More than 20 different conferences have been "infected" between 2008 and 2011. For the two most affected there was respectively more than 20 and more than 10 fake papers published.

Figure 1 :

 1 Figure 1: Distribution of intra-corpus distances.

Duplicated publications: Number ( 2 )

 2 branch is a zero distance (0.006) between two Y papers. Only the titles are different. It reveals that an identical text was presented (and accepted) twice.Smallest distances (without SCIgen texts):The branches of the dendrogram numbered 2 to 8 are the texts with the smallest distances (less or equal to 0.35) all sharing a common subset of authors and very similar topics.

Figure 3 :

 3 Figure 3: Dendrogram for cluster analysis of corpora Antkare (black), Z (blue), MLT (red). Main clusters : C (Antkare and MLT pseudo texts ), B ( Z and MLT genuine), C(MLT genuine). main remarkable points : C3 C4 (SCIgen texts published many times). A1, A2, A3, B1, B2 (smallest distances).

Acknowledgment

We thank the anonymous referees for theirs valuable comments on a previous version of this document but also Tom Merriam, Jacques Savoy, and Edward Arnold for their careful readings of previous versions of this paper, Eric Gaussier, Marie-Christine Rousset for useful discussions about the topic.

 3), ( 4), ( 5), ( 6), ( 7), [START_REF] Labbé | Ike antkare, one of the great stars in the scientific firmament[END_REF] smallest distances (without SCIgen texts).

l l l l l l l l l l l l l l l l l