<figure><img src="image_1.png" /></figure>

HAL
open science

# Classification automatique et reconnaissance des formes

Jean-Claude Simon, Edwin Diday, Jean-Paul Maroy, Marc Berthod

► To cite this version:

Jean-Claude Simon, Edwin Diday, Jean-Paul Maroy, Marc Berthod. Classification automatique et reconnaissance des formes. [Research Report] IRIA-RR-076, IRIA. 1974, pp.30. hal-04715963

HAL Id: hal-04715963

https://inria.hal.science/hal-04715963v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la 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.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
02094 RR76

RIA
laboria

laboratoire de recherche
en informatique
et automatique

ARCHIVES

Classification automatique
et reconnaissance
des formes

J.C Simon, E.Diday
J.P Maroy, M.Berthod

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 76

juillet 1974
CLASSIFICATION AUTOMATIQUE
ET RECONNAISSANCE DES FORMES

J.C. Simon, E. Diday, J.P. Maroy, M. Berthod

Abstract

This report contains the four papers presented by the group at the Second International Joint Conference on Pattern Recognition held in August 1974 in Copenhagen. In a first invited paper J.C. SIMON presents a formal approach of semantics in Pattern Recognition and Scene Analysis. In a second invited paper E. DIDAY makes a survey of distances and similarity measures used in Pattern Recognition and advocates the use of adaptative distances. In a third paper E. DIDAY presents the Sequential Dynamic Clusters Method. In the fourth paper J.P. MAROY and M. BERTHOD describe a new algorithm for on-line recognition of Handprinted Characters based upon Scene Analysis techniques.

Résumé

Ce rapport regroupe les quatre communications présentées par l'équipe à la seconde conférence internationale de reconnaissance des formes qui s'est tenue à Copenhague en Aout 1974. Dans une présentation de synthèse demandée par le comité, J.C. SIMON propose une sémantique formalisée des problèmes de reconnaissance des formes. Dans une autre communication invitée, E. DIDAY analyse les différentes distances et mesures de similarité utilisées en classification automatique et propose l'emploi de distances adaptatives. Dans une troisième communication E. DIDAY présente l'algorithme des nuées dynamiques séquentialisé. Dans la quatrième communication J.P. MAROY et M. BERTHOD décrivent un algorithme de reconnaissance en temps réel de caractères manuscrits fondé sur l'analyse de scènes.
SECOND INTERNATIONAL JOINT CONFERENCE
ON PATTERN RECOGNITION

August 13-15, 1974, Lyngby-Copenhagen, Denmark

SECRETARY: E. Backer, Delft University of Technology, EE-Dept., Mekelweg 4,
Delft, Holland

LOCAL ARR.: Dr. P. W. Becker, Technical University of Denmark, Electr. Lab.,
Bldg 344, 2800 Lyngby, Denmark

CONFERENCE CHAIRMAN
Ir. C. J. D. M. Verhagen, Netherlands

SCIENTIFIC PROGRAM COMMITTEE

Dr. C. K. Chow, USA
Dr. King-Sun Fu, USA
Dr. H. Kazmierczak, West Germany
Dr. V. A. Kovalevsky, USSR
Dr. M. Nagao, Japan
Dr. H. L. Oestreicher, USA
Dr. J. C. Simon, France

STANDING
CONFERENCE COMMITTEE

Prof. K. S. Fu, USA
CHAIRMAN

Dr. C. K. Chow, USA
Prof. Herbert Freeman, USA
VICE CHAIRMEN

Prof. R. S. Ledley, USA
SECRETARY

Dr. M. Alserman, USSR
Dr. Peter W. Becker, Denmark
Dr. E. R. Calanietto, Italy
Prof. Thomas M. Cover, USA
Dr. Sandor Csibi, Hungary
Dr. Richard O. Duda, USA
Prof. Samuel J. Dwyer, III, USA
Prof. Adolfo Guzman, Mexico
Prof. Laveen N. Kanai, USA
Dr. H. Kazmierczak, West Germany
Dr. V. A. Kovalevsky, USSR
Prof. D. G. Lainiotis, USA
Dr. Morton Nadler, France
Prof. Jin-ichi Nagumo, Japan
Prof. R. Narasimhan, India
Dr. Torleiv Orhaug, Sweden
Prof. E. A. Patrick, USA
Dr. K. Preston, USA
Prof. Azriel Rosenfeld, USA
Dr. Denis Rutovitz, Great Britain
Dr. T. Sakai, Japan
Prof. J. C. Simon, France
Dr. T. Vamos, Hungary
Dr. C. J. D. M. Verhagen, Netherlands
Prof. M. S. Watanabe, USA

THE SECOND INTERNATIONAL JOINT CONFERENCE ON PATTERN RECOGNITION
TO BE HELD IN LYNGBY NEAR COPENHAGEN IN DENMARK, AUGUST 13 - 15,
1974.

The Conference is the second in a series of International Joint Conferences which are planned to take place every second year. At this series of Conferences it is intended to pay attention to all aspects of pattern recognition and also to discuss such aspects in relation to each other. In this way the International Joint Conferences on Pattern Recognition will acquire an individual identity.

ON THE CONFERENCE PROGRAM

It is the purpose of the Conference to bring together scientists
in the field of Pattern Recognition from all over the world to
discuss problems of common interest. The program for the Confe-
rence covers all aspects of theoretical and applied Pattern Recog-
nition. A number of speakers are invited to give a survey of some
key problems while including their ideas of trends in future de-
velopment. The program also includes four panel-discussions, ex-
ploring current trends and difficulties in the field of Pattern
Recognition. Conference participants are invited to give brief
talks (5 minutes at the most) about recent research results. A
small exhibition of hardware applied in Pattern Recognition de-
vices is planned. A reading-room will be opened where partici-
pants can inspect the most recent literature in the field.

SPONSORS

The sponsoring societies include: IEEE Computer Society, Control
Systems Society, Information Theory Group, and the Systems, Man,
and Cybernetics Society, The International Federation of Inform-
ation Processing, The Association for Computing Machinery, The
Optical Society of America, The Pattern Recognition Society, The
Society of Photo-Optical Instrumentation Engineers, Dansk Inge-
niørforening and Ingeniør-Sammenslutningen.
# SCIENTIFIC PROGRAM

## Special sessions

Opening session: Tuesday, August 13, 9.30 a.m.

Closing session: Thursday, August 15, 5.15 p.m.

## Panel discussions

* General and dominant problems in pattern recognition.
  Chairman: Kanal; members: Wolferts, Verhagen; other panelists to be invited.

* Structural pattern recognition.
  Chairman: Fu; members: Simon, Rosenfeld, Narashiman.

* Feature extraction.
  Chairman: Nadler; members: Hanakata, Levine, Roche, Watanabe.

* Bridging the gap between pattern recognition theory and practice, with particular emphasis on representative data bases.
  Chairmen: Foley, Oestreicher; other panelists to be invited.

## Invited surveys

* recent progress in statistical methods applied to pattern recognition (Toussaint)

* recent progress in distance and similarity measures (Diday)

* recent progress in linguistic methods applied to pattern recognition (Fu)

* recent progress to a formal approach to pattern recognition and scene analysis (Simon)

* recent progress in adaptive pattern recognition (Pugatshev)

* recent progress in interactive pattern recognition (Kanal)

* recent progress in picture processing and scene analysis (Montanari)

## Session on last minute results

Registrants are invited to report on recent results of their research in pattern recognition for at most 5 minutes. Participants can register for this session during the first day of the conference by completing a form to be obtained at the registration desk.

## Regular sessions

There will be three or four parallel sessions. The time schedule is intended to provide synchronism between the sessions, to give the possibility of changing to another session at the end of a paper. A long paper is limited to 25 minutes at the most, followed by 5 minutes for discussion; a short paper is limited to 10 minutes at the most and 5 minutes for discussion, so two short papers are equivalent in time to a long one. When discussion time is too short, the discussion can be continued after the session. The program is provisional; some changes are to be expected. A few papers are still under consideration. Several more papers from the USSR are announced, but have not arrived yet.

The titles given below are the ones from the submitted drafts. The members of the Scientific Program Committee suggested several changes as to the contents of the drafts of accepted papers and sometimes as to the titles of the papers. A few submitted papers will be combined to form one new paper; the title of one of the original drafts is given hereafter. It is to be expected that some of the French titles and papers will be translated into English. The oral presentation of all papers will be in English.
Short papers are indicated by a *; in a few cases the indication is not yet definitive.

# SUBMITTED PAPERS

## Mathematical methods

* WOLD (Sweden): Pattern cognition and recognition (cluster analysis) based on disjoint principal components models

* LEE (USA): A sub-minimal spanning tree approach for large data clustering

* WATANABE (USA): A dynamical model of clustering

* BECKER (Denmark): What multivariate probability densities are possible with a specified set of marginals?

* BATCHELOR (Great Britain): Artificial data for pattern recognition: generation and uses

* HÖHNE (West Germany): An adaptive algorithm for approximation of sampling distributions, based upon the method of moments

* DIDAY (France): Classification automatique sequentielle pour grands tablaux
  ROCHE (France): Application of multilevel clustering to the automatic generation of recognition operators
  A link between feature extraction and classification
  SABAH (France): La notion d'operateur de commande en reconnaissance des formes

* DUDANI (USA): The distance-weighted k-nearest neighbour decision rule

* VAJTA,FRITZ (Hungary): Some remarks on optimal k-nearest neighbour pattern classification

* GYÖRFI (Hungary): A suboptimal solution of linear classification problem of minimal error probability

* CHANG,DWYER (USA): New approach to measurement selection in pattern recognition

* KITTLER (Great Britain): A method of feature selection for high dimensional pattern recognition problems
  TOMITA,NOGUCHI (Japan): On a self-classification of patterns by the Karhunen-Loève orthogonal system
  UNGER,STANKE (DDR): Properties of a regression function generating classification algorithms of the so-called error correction type
* HAND,BATCHELOR (Great Britain): A preliminary note on pattern classification using incomplete vectors
* YOUNG (USA): The prediction of performance in multi-class pattern classification
  DUIN,HAERSMA BUMA (Netherlands): Some methods for the selection of independent binary features
* GOSE,WU (USA): Feature selection and re-selection de FIGUEIREDO (USA): Optimal linear and non-linear feature extraction based on the minimization of the increased risk of misclassification
  DEVIJVER (Belgium): The generalized Bayesian distance

* TROBORST,BACKER,BOEKEE,BOXMA (Netherlands): New families of probabilistic distance measures
  TOUSSAINT (Canada): On the divergence between two distributions and the probability of misclassification of several decision rules

* ITO (Japan): Approximate bounds of misrecognition and their computational evaluation

* CHANDRASEKARAN,JAIN (USA): Distance functions for independent measurements and finite sample size
  BORIELLO,FUSCO (Italy): Matched filters for signal detection in noisy images

* ROHRER (West Germany): Pattern recognition in a hierarchical structure of learning automata

* PAU (France): Adaptive on-line failure diagnosis and prediction

* YOUSIF (USA): State estimation of power system by pattern recognition

* MICHALSKI (USA): A logistic approach to optimal classification into a large number of classes
  BELL (Great Britain): Decision trees made easy
## Syntactic methods

* BLACKWELL (USA): Combining mathematical and structural pattern recognition

* FUNG, FU (USA): Stochastic syntactic decoding for pattern classification

* SVENSSON (Sweden): On the use of fuzzy concepts in description
  ITO (Japan): An algebraic theory of pattern manipulation

* THOMASON, GONZALEZ (USA): Error detection and classification in syntactic pattern structures
  CHO (USA): The generating properties of context-free picture grammars

LAFFAN, SCOTT (USA): A new tool for automatic pattern recognition; a context-free grammar for plane projective geometry

TSUJI, FUJIWARA (Japan): A linguistic segmentation of scenes into regions

* HANAKATA (West Germany): A descriptive data structure for interactive pattern recognition
  HAYES-ROTH (USA): An optimal network representation and other mechanisms for the recognition of structured events

* ALBUISSON, MONGET, BORDET (France): Pattern recognition of structure functions as an aid for understanding the morphology of two-dimensional field data

* OUABDESEELAM (France): Proving programs by pattern difference

## Line processing and analysis

### BERTHOD, MAROY (France): Une méthode heuristique de suivi de courbes en temps réel

* RAJASEKARAN, DEEKSHATULU (India): A sequential template matching procedure for the recognition of complex line patterns

HOROWITZ (USA): A general peak detection algorithm with applications in the computer analysis of electrocardiograms

STOCKMAN, KANAL (USA): An experimental waveform parsing system

COOPER (USA): Feature selection and super data compression for pictures occurring in remote conferencing and classrooms systems

* DREWES (West Germany): Learning class descriptions of line patterns

## Picture and scene processing and analysis

JAMATI, LAPLACE, VIOVY (France): Simulation de l'extraction des contours par le système visuel

KUNII, TENENBAUM (Japan, USA): Designing large shared data bases for picture processing applications
HOROWITZ, PAVLIDIS (USA): Picture segmentation by a directed split-and-merge procedure

* KASVAND (Canada): Experiments in global picture segmentation for improving a picture language

* GUPTA, WINTZ (USA): Computer processing algorithm for locating boundaries in digital pictures

* TRIENDL (West Germany): Recognition of texture edges by propagation

* ARCELLI, CORDELLA, LEVIALDI (Italy): A grassfire transformation for binary digital pictures

ZAHN (USA): Region boundaries on a triangular grid

PERSOON, FU (USA): Shape discrimination using Fourier descriptors

SKLANSKY (USA): Parallel analysis of concavities in cellular blobs

NADLER (France): Sequentially-local picture operators

BOWKER (USA): Edge vector image analysis

* SMITH, DAVIS (Canada): A new algorithm for edge detection

* FRIEDEN (USA): Restoration of pictures by Monte Carlo allocation of 'grains'

* MARMOLIN, NYBERG (Sweden): Multidimensional scaling of subjective image quality

* WALL, KLINGER (USA): Analysis of image histograms

* AGGARWAL, DUDA (USA): Motion and computer pattern recognition

ABOUTALIB, SILVERMAN (USA): Restoration of images degraded by curvilinear motion

* TENENBAUM, GARVEY, WEYL, WOLF (USA): An interactive facility for scene analysis research

* NAGAO, MASUI, FUKUNAGA (Japan): An interactive picture processing system on a mini-computer

YAKIMOVSKY (USA): Computer software using AI applied to pattern recognition

## Analysis of three-dimensional scenes

BADLER (Canada): Three-dimensional motion from two-dimensional picture sequences

GARVEY, TENENBAUM (USA): On the automatic generation of programs for locating objects in office scenes

KUIPERS (USA): An hypothesis-driven recognition system for the blocks world

CHIEN, CHANG (USA): Recognition of curved objects and object assemblies

* RÖCKER (West Germany): Localization and classification of three-dimensional objects

BAJCSY, LIEBERMAN (USA): Computer description of real outdoor scenes

TASTO (West Germany): A probabilistic object model for computerized transverse axial tomography

## Special applications of picture and scene processing

KAMESWARA, RAO, PRASADA, SARMA (India): An automatic fingerprint classification system

OHTERU, KOBAYASHI, KATO, NODA, KIMURA (Japan): Automated fingerprint classifier

* WOLFERTS (West Germany): Special problems in interactive image processing for traffic analysis

* BAJCSY, TAVAKOLI (USA): Computer recognition of roads from satellite pictures

BORRIELLO, CAPONETTI, FUSCO (Italy): Urban area analysis by multispectral satellite's images

* EKLUNDH (Sweden): Object selection in SEM images

* ABMAYR (West Germany): Non linear preprocessing methods for the evaluation of yeast cell pictures

* HOWARTH (Great Britain): The impact of pattern recognition methodology in geochemistry

## Character recognition

SHILLMAN, KUKLINSKI, BLESSER (USA): Experimental methodologies for character recognition based on phenomenological attributes

* MASUDA (Japan): Assessment of handprinted character quality and its applications to machine recognition
  BOHNER (West Germany): A quantitative method for font assessment

* SHURNA, LASHAS, GVILDYS (USSR): Preprocessing of patterns in optical character recognition systems
  MÜNSTER, PONSAING (Denmark): A low-cost zipcode-reader using optical line detection

* JOYNSON, MUNDY, BANERJI (USA): A line description system based on Hadamard features

* GAILLAT (France): Un programme de reconnaissance de caractères manuscrits, pendant la phase d'écriture

* ICHIKAWA, YOSHIDA (Japan): On-line recognition of handwritten characters with associative read-out of patterns in a memory

* BELL, COWIN, OLDING, PARKS, WATSON (Great Britain): A reader for handwritten numerals
  MORI, MORI, YAMAMOTO, YAMADA, SAITO, NAKATA (Japan): Recognition of handprinted characters

* OTT (West Germany): On feature selection by means of principal axis transformation and non-linear classification
## Character recognition (continued)

* BLEICHRODT, KRAUSE, SCHWERDTMANN, PAUL (West Germany): Reduction of computations for a quadratic classificator without loss of performance

* TUCKER, EVANS (Great Britain): A two-step strategy for character recognition using geometrical moments

* SPANJERSBERG (Netherlands): Combinations of different systems for the recognition of handwritten digits
* COX, BLESSER, EDEN (USA): The application of type font analysis to automatic character recognition

* OZAWA, TANAKA (Japan): Band correlation method for a highly efficient OCR

* STUCKI, SCHMID (Switzerland): A misregistration and orientation independent method to recognize single font typewritten numerals
* AL-KIBASHI, TAYLOR (Great Britain): The UCLM3 programmable pattern recognition machine
* HAGER (West Germany): Experiences with sequential polynomial pattern classifiers

* STRINGA (Italy): MARS, a hand and machine-written address reader, implemented on a multimini based associative processor

## Speech recognition

* KYNNAP (Estonian SSR): Recognition of voiced-speech waveforms

* CHITAVICHIUS, GUDONAVICHIUS, KEMEŠHIS, PATASHIUS (USSR): Word recognition on the basis of structural properties of speech signal

* MICLET (France): Reconnaissance de la parole: pré-diction de mots pas contraintes phonologiques

* DOWLING, HALL (Great Britain): Elastic template matching in speech recognition, using linguistic information

* TOKUNAGA, HIRAKAWA, SUGIHARA (Japan): Speaker and spoken digits simultaneous recognition
* RAMISHVILI (USSR): Experiments on automatic verification of speakers

* BAUDRY, DUPEYRAT (France): Reconnaissance automatique de la parole

## Bio-medical applications

* HENDERSON (USA): Adaptive training of a multi-stage pattern classifier for health testing applications
* REICHERT, KRIEGER (USA): Quantitative certainty in differential diagnosis

* AKATSUKA, ISOBE (Japan): Feature extraction of stomach radiograph

* BALLARD, SKLANSKY (USA): Hierarchical recognition of tumors in chest radiographs

* PATON (Great Britain): Detection of inter-rib spaces in chest radiographs

* STARK, TUTEUR (USA): A proposed optical-digital approach to the problem of classifying pneumoconioses from chest X-rays
* TASTO, BLOCK (West Germany): Locating objects in complex scenes using a spatial distance

* YAMAMOTO, YOKOUCHI, SUZUKI (Japan): Image processing and automatic diagnosis of color fundus photographs

* BACUS (USA): Design and performance of an automated leukocyte classifier
* MANCILLAS, WARD (Great Britain): Machine recognition in pathology
* PIERONI, NARASIMHAN (Italy, India): Cardiac potential map analysis and description

* KRISHNAN, TUTEUR (USA): Pattern recognition of evoked responses

## Industrial and other applications

* PETERSON (Netherlands): Automated visual inspection

* NORTON-WAYNE, HILL (Great Britain): The automatic classification of defects on moving surfaces
* LOGAN, MACLEOD (Great Britain): An application of pattern recognition algorithms to the automatic inspection of steel strip surfaces

* BLIN, WHINSTON (USA): The use of discriminant functions in group decision making

* CHEN (USA): Feature extraction and computational complexity in seismological pattern recognition
* SCHOENDORF, CARAYANNOPOULOS, BURDICK, THERRIEN (USA): The application of feature extraction to radar signature classification

* SAKAI, KANADE, ARIKI (Japan): Multi-feature display of on-line signature by color TV display

## Accepted behind schedule

LOWITZ (France): A linearization method around cardinal points of the geometrical distortions of images

## Final session-schedule

A final session-schedule will be distributed to all preregistrants and authors a few weeks before the conference. Late registrants will get it at the registration desk.
# RECENT PROGRESS TO A FORMAL APPROACH OF PATTERN RECOGNITION
AND SCENE ANALYSIS

J. C. SIMON

Institut de Programmation

Université Paris VI

Place Jussieu, 75230 - PARIS Cédex 05

## O. PRELIMINARY REMARK

Originally a paper had been written for I.J.C.P.R.II on "some formal aspects of Pattern Recognition (P.R.) and Scene Analysis". Some committee members thought that it should be transformed in a survey paper of the above title.

Though it seems important to draw the attention of the P.R. specialists to this aspect of their field, the survey gave a nearly empty harvest... We have to admit that the P.R. domain has been developped mainly under the need to solve some practical applied problems and that little attention has been paid to the formal aspects of a possible theory of P.R.

However it seems to be time to try to introduce some order or rather some unifying points of view. This is in fact the purpose of this paper, which thus presents more of the author's personal opinions than should indeed a survey of the existing published work.

## I. INTRODUCTION

The paper tries to underline the common properties of a recognition procedure.

As the "semantic of programming languages" tries to define precisely *what is a computation*, the P.R. specialist should try to define *what is a recognition*. In other words he should be able to define precisely the semantic of a recognition procedure.

To do this he needs a proper language in which he can express his recognition procedures and the associated semantic. A proposition is made for such a language and the different interpretations in natural or mathematical languages, in programming languages, or in abstract machine languages.

A review is made of the different properties used by the P.R. specialist to build the practical P.R. procedures. Intuition, physical sense have been the guidelines in the past ; it seems worthwhile to make explicit the reasons which guided the experimental search ; in particular, if we wish to automatize the build up of P.R. procedures according to their domains.

The burgeoning P.R. field has stemmed from the computer. The aim was to obtain practical P.R. programs. At present the field seems rather "unwielded". Applied mathematics should be the language able to bring some unity and to define precisely the P.R. properties, though P.R. is not a branch of applied mathematics...

## II. IMPORTANCE OF SEMANTICS IN A RECOGNITION

II.1. A Pattern Recognition or a Scene Analysis may be viewed as *the passage from a structured data to another structured data*.

Such a vague statement would be good also for a definition of the execution of any "task" by a computing system...

Our field is characterized by *two essential differences* :

i) The *starting structured data (s.s.d.)* represents the results of some experimental measurements of a *field or domain*.

ii) The final *structured data (f.s.d.)* represents what a human operator expects to be either a classification or a scene analysis result.

These "differences" could also be phrased as :

i) The *interpretation* of the s.s.d. is the result of some *experimental measurements of a field or domain*.

ii) The interpretation of the f.s.d. is a classification or description relevant to the field or domain.

## Remarks

A structured data is an element of a data base called also data type (in french, *structure de données*).

From now on, a "recognition" will designate the passage from a s.s.d. to a f.s.d. if this passage performs what *may be interpreted* as a Pattern Recognition or a Scene Analysis.

The interpretation of a f.s.d. may be quite different, according to the problem. A human observer may interpret ("understand") a visual display of the f.s.d. or a machine such as a "robot" may interpret the f.s.d. by *actions* ; for example the WINOGRAD robot manipulating cubes and pyramids (3¹).

II.2. Thus in a recognition the interpretations, of if one prefers, the semantics of the s.s.d. and f.s.d. are quite essential. The passage from the s.s.d. to the f.s.d. is concretely executed by some machine, usually a computer.

*The basic problem of a recognition is to define and implement the procedure which will perform the recognition.*

Again detailed interpretations of this procedure are usually quite important and usefull, as we shall see later.

## III. THE DIFFERENT LEVELS OF ABSTRACTION

III.1. The purpose of an "abstraction" is to suppress details that are not essential, and to retain, if possible, the important properties.

Naming a real object, a situation, a procedure or a mathematical object is a *usual result* of an abstraction process.

A language defines an abstraction level. A word or a phrase of the language defines an abstraction at that level.
The computer scientists are quite familiar with the idea that the different languages such as a machine language, an assembler language, a programming language provide different ordered levels of abstraction: the non relevant details are suppressed in the "higher" languages.

The mathematical logicians speak of the "language of logic" as representing relations and properties which may be interpreted in various domains: natural languages, mathematics etc... cf. LYNDON (¹³). Logic is a "metamathematic" language, abstracting what is expressed usually by mathematicians in natural language.

### III.2. A "recognizer" should also specify at what level, i.e. in what language, he wishes to express himself.

Most of the papers on recognition describe various procedures, working on data. It is not always clear at what level is made the description. Is it the machine level, the procedure description or an abstract mathematical level? Our feeling is that some "ad hoc" language L should be defined and used, to deal with a recognition problem. Some similar efforts have been made. For example cf. (¹) (3).

The first purpose of L would be of course naming the objects of a recognition: the datas, and the procedures applied on the datas to obtain the result.

Different properties, for example invariance, continuity, should be expressible in L. Usually they pertain to the recognition procedure.

The essential type of features should exist :

i) An interpretation from L into the natural or mathematical language (the meaning).

ii) An interpretation into a programming language or an "abstract machine" language (the implementations).

## IV. SOME PROPOSALS FOR A LANGUAGE L

### IV.1. If the purpose of L is to speak of a recognition, mostly of a classification, it should be able :

- to name datas at different steps or recognition

- to name functions, implemented as procedures or programs, or a programming language, or as operators of an abstract machine.

- to admit the two types of interpretations as above.

An important point at this step is to ask to what details should L go in describing recognition operations, i.e. what should be primitives of L.

For example : should we admit as primitive (one word of the language) a function, an interpretation of which would be an addition, or rather describe it by some boolean functions. It is clear that the interpretations should be stated at the very beginning of the language definition.

Let $x_i$ be a word of L, a chain of words $e = x_1 \dots x_i \dots x_p$ is a phrase, or expression of L.

Let $\Phi e$ be the interpretation of $e$ into the natural or mathematical language, $\varphi e$ be the interpretation of $e$ into an abstract machine language, $\varphi'e$ be the interpretation of $e$ into a programming language.

### IV.2. Primitive terms and functions

Let T be the set of primitive terms. Their use is essentially to name variable experimental datas, ($\Phi$ interpretations) ; $X \in T_0$ is used to name the variable s.s.d., $\Omega \in T_0$ the variable f.s.d. Their $\varphi$ interpretations could be memory addresses in abstract machines.

Let F be the set of primitive "functions" (*) f. It can be decomposed in a number of subsets, each of

which, $F_n$ for example, contains the functions $f_n$ of order n.

The functions of order zero are the constants. An example of $\Phi$ interpretation is the result of an experiment, and of $\varphi$ interpretation the state of a memory cell.

The $\Phi$ interpretation of f is to be called an operation, or mapping, (passage has also been used in that sense). See fig. 1.

The $\varphi$ interpretation of f will be called a procedure if one thinks of a programming language, an operator if the $\varphi$ interpretation domain is an abstract machine.

### Remarks

- The very concept of function should be carefully appreciated by the P.R. specialists, see IV.6.

- Among the familiar constructive functions, the Mc CARTHY conditional functions allow iteration and recursion. This last property may give functions that are not defined on the whole argument set, a feature which should interest the P.R. specialist more than the concept of fuzziness...

- If conditional functions are to be used, then of course predicates should be introduced in L. Let us recall the usual conditional function f as defined by

$$f = \text{if } p \text{ then } f' \text{ else } f''$$

$f'$, $f''$ being function, p a predicate defined on the set of terms and functions.

### IV.3. An algebra of terms, an algebra of functions

#### IV.3.1. The application of functions on terms generates new terms. Thus the general definition of terms :

i) a primitive term is a term

ii) if $t_1 \dots t_n$ are terms $f_n t_1 \dots t_n$ is a term $t = f_n t_1 \dots t_n$

The set of terms is potentially infinite.

This algebra should be refined if the conditional functions are introduced.

#### IV.3.2. In the same way an algebra of functions may be defined. From a set of primitive functions, (consisted now as the terms of the algebra), functionals may generate new functions (exactly like functions would previously generate new terms). The functionals may be considered as mappings from functions into function. Their $\varphi$ interpretation is the "command operators" of ROCHE (¹⁹) and SABAH (²³).

### IV.4. Convention

It is essential to be able to distinguish between a variable such as $t_i$ and the state of a variable. If the interpretation $\varphi t_i$ in the domain of an abstract machine is a register, the $\varphi$ interpretation of the 'state of $\varphi t_i$' will be represented by the same letter in studies. The name of the current state of a variable $t_i$ is represented by $t_i'$.

We need names for constants in L independently of the variables (the $f_0$ functions), let these be 2, 1, 0, ..., 0, 1, ..., $n$, ...

### IV.5. The recognition functions

Let $\&$ the global recognition "function", i.e. $\&$ is the "good" mapping between the experimental results and the classification or scene analysis, $\varphi \&$ is the good recognition program or the combination of complex automatas, that will implement the classification or scene analysis.

<footnote>(*) To be in agreement with the prevailing customs, we will use also "procedure" or "operator", but to our opinion the word "function" should be preferred at the level of L.</footnote>
Let $X$ and $\Omega$ be the variable s.s.d. and f.s.d. in L.

$$ \Omega = \mathcal{A} \ X \qquad (1) $$

The expression (1) does not teach us much about the process ! We have to give more details.

Let us limit ourselves to classification. Then $X$ should usually be described as a list (not as a point of $\mathbb{R}^n...!$).

$$ X = (x_1, ..., x_m) $$

a state of $X$ is thus

$$ X = (x_1, ..., x_m) $$

$\Phi$ $X$ is called sometimes an "initial description".

The set of states $\mathcal{X}$ is a set of lists. It is in that limited sense that we can speak of a structured data set.

Let $\mathcal{A}$ be a state of $\mathcal{X}$, $\mathcal{A}[i]$ is the proper classification name. Thus the structure needed is only the structure of a set $\mathcal{A}$.

Unless we have very specific reasons, there is no justification to embed $\mathcal{A}$ or $\mathcal{A}$ into a topological space such as $\mathbb{R}^n$. We will comment later on this point.

<figure><img src="image_3.png" /><figcaption>Figure 1 gives a picture of the languages correspondances and of the usual names in each languages</figcaption></figure>

Of course direct correspondances can also be established between abstract machine languages, programming languages and natural or mathematical languages.

## IV.6. Constructive definitions of $\mathcal{A}$

Usually the experimenter can provide a "training" or "learning" set, i.e. a finite set of couples $(X, \omega)$. Thus $\mathcal{A}$ is defined on a number of "samples". But up to now $\mathcal{A}$ is not defined outside.

The real problem of recognition is precisely to obtain $\mathcal{A}$ outside of the training set. Obtaining an extension of $\mathcal{A}$ outside of the training set is the generalization problem.

This of course can be obtained only by guessing the properties of $\mathcal{A}$ . These properties are typical of the semantic of a specific P.R. domain.

Let us take some examples, to show how the semantic of different P.R. problem has been introduced in fact by P.R. specialists :

- discriminant functions and the use of probability distribution

- the use of properties of $\mathcal{A}$ such as invariance, continuity or neighbourhood, metrics.

- the use of a priori operations and of certain heuristics in the build up of a proper $\mathcal{A}$.

## V. EXAMPLES OF DETERMINATIONS OF A RECOGNITION PROCEDURE BY THE MATHEMATICAL OR PHYSICAL PROPERTIES

### V.1. "Classifier", "discriminant functions" and decision surfaces" procedures

Let us refer to the book by R.O. DUDA and P.E.HART (6) Pattern Recognition and Scene Analysis, § 2.4.

It is clear that the abstraction level, i.e. the language, is "mathematical english".

They propose to represent the starting structured datas (s.s.d.) by a vector $x$, more precisely by a point in $\mathbb{R}^n$. The justification is found in the nature of the n different measurements.

Then they define discriminant functions (or operations) $g_i(x)$, $1 \le i \le p$.

The classification conditional function is :

"if $g_i(x) > g_j(x)$ for all $j \ne i$, $x$ is in the class $i$"
Thus $\&$ is a mapping from $\mathbb{R}_n$ into the set $\{\omega_i\}$.

But this mapping is entirely defined by the p discriminant functions $g_i$.

The authors remark that if a set of $g_i$ is satisfactory, one can say the same of the set of $f_i(g_i(x))$, $f$ being a "monotonically increasing function". The freedom of choice is functionally infinite. Then is made the proposition that the $g_i$ be the probability functions:

$$g_i(x) = P(\omega_i | x)$$

$$\text{or} \quad g_i(x) = \log p(x | \omega_i) + \log P(\omega_i)$$

But this is still a "non constructive" level of abstraction. In § 2.7. they give to the $g_i$ the very strict form of "multivariate normal density", which is justified by the interpretation of the domain.

Now $\&$ is entirely and precisely specified as a well known explicit function.

A degenerate form is the "linear discriminant functions". Then

$$g_i(x) = w_i x + w_0$$

There again the functions are determined a priori, in a very detailed way.

Once this decision is taken, various techniques can be applied to adapt the functions $g_i$ to the real problem. J. N. NILSSON (⁷) has given the proofs of convergence for the procedures to adapt the set of linear $g_i$ to a given training set. (The perceptron algorithm). Many other examples are quoted in the book by DUDA and HART (⁶) chap. 5.

We may conclude:

i) The $\&$ mapping is determined by constructive means, inspired by some physical, mathematical or cultural background.

ii) The $\&$ mapping works all right on the training set.

iii) The $\&$ mapping works usually in a quite unsatisfactory way outside of the training set. The generalization properties of $\&$ are poor.

Of course these techniques have been quite usefull in many practical problems. Our purpose here is only to point out their artificiality, as V. A. KOVALEVSKY did clearly in (¹²).

## V.2. The use of invariant properties

Let $x$ and $x'$ be two "initial descriptions" such that

$$x' = T x$$

T is a function or procedure such that

$$\& (x) = \& (T x)$$

Then the classification function $\&$ is invariant under the transformation described by T.

One may predict, under experimental reasons, the existence of T. Thus important properties of $\&$ can be guessed. Let us give examples:

### Preprocessing

An initial description is represented by a list of n samples

$$X = (x_1, \dots, x_i, \dots, x_n)$$

Each of these $x_i$ samples is itself represented by one among q values.

By a filter (the T function) a new description $X = T X$ is obtained with a new $n' < n$ and eventually $q' < q$ such that

$$\& (T X) = \& (X)$$

The recognition procedure can then start from $X'$. In fact, the filtering process maps on $X'$ a large number of $X$, reducing the dimensionality of the problem.

The digital filters, the "Fourier filters" are currently used for voice or image preprocessing, cf. A. ROSENfeld (²⁰).

Such a transform T may be useful to present a complicated s.s.d. as a reduced structured data to a human observer.

### Geometrical transformations

Frequently the recognition is invariant for some transformations in the space of the observed object.

For example the voice signal should be invariant to amplitude to a large extent and to certain variations in frequency (male or female speakers). Also physiology seems to indicate that the pitch and formant frequencies are invariant for a given speaker. Thus are suggested some transformations that will provide an invariant description from the initial signal.

An image description should be invariant for translation and possibly for rotation or plane projection. We have proposed some transformations on the initial description to obtain a new invariant description, thus simplifying the $\&$ procedure, cf. J. C. SIMON et al. (²⁴).

Many other propositions based on invariance properties of the $\&$ function have been made. In fact, invariance may seem one of the main justification for the so called linguistic techniques.

### Linguistic techniques

Syntactic analysis has stemmed from the recognition and translation of strings of words (phrases) belonging to a language $\Lambda$. The language $\Lambda$ is generated by a grammatical procedure, i.e. the deduction from the axiom by rewriting rules (productions).

The essential interest of these grammatical procedures is to generate or to recognize phrases without having to search a large memory. In particular, if a derivation is recursive, some phrases of $\Lambda$ can be as large as one wishes. Thus the economy of memory can be very important.

Practical compiling techniques use only context free (c.f.) grammars: this means basically that the use of a production is invariant with the position in the string of characters.

Productions or rewriting rules are nothing else that functions of a very simple type. A c.f. production, used bottom up, is a function with a p list input and one output.

Again the nature of the recognition function is chosen according to the property of invariance to translation.

### Remarks on the "linguistic techniques"

The above statements do not make justice to the contribution of the linguistic procedures to P.R.

The reader should report to the progress-survey paper by K. S. FU (⁹) given during the same IJCPR II.

However, in the author's opinion, the introduction of linguistic procedures is the recognition that, the use of algebraic functions in $\mathbb{R}^n$ being insufficient, the full power of "general recursive" functions should be called for. In a way, the "linguistic attitude" in P.R. is nothing but a pace in that direction.

For example a rewriting rule or production is nothing but the most simple expression of a list function...
### V.3. Clustering

The clustering techniques are based on the "a priori" existence of distances or similarity measures between objects to be classified.

More precisely if $X = (x_1, ..., x_p, ..., x_n)$ is a s.s.d. corresponding to an object $\zeta$, distance evaluations are proposed by the specialist :

- between two objects of the domain

- between an object and a class of partition $\omega_i$ or a representation of that class $\omega_i$

- between a class of partition and a parametrized representation of that class.

These distances are computed from the $\infty$ of the objects to be classified, cf. E. DIDAY (⁴) (⁵).

The implementation of the $\&$ function is usually a table look up. Then the $\&$ function is defined only on the set of classified objects. DIDAY presents in (⁵) a dynamical clustering method for which $\&$ is different and has generalization properties.

The interesting point is that the building of the $\&$ is made through the use of a "semantic information" implemented by the distance evaluations, specific to a PR field. This idea will be proposed again in a different way.

### V.4. Topological properties

The neighbourhood or continuity properties of the space of $X$ representations is often intuitive. They are of course local and quite difficult to implement properly.

Most often the use of $\mathbb{R}^n$ and of algebraic functions is an overstatement of these topological properties.

The method of potential functions cf. (¹²), p. 13 was popular ten years ago among P.R. specialists. It relies on the idea of continuity in a topological space

An interesting essay by T. THOM (²⁷) formalizes the dynamic of geometrical shapes in biology. The proposed models are inspired from differential topology.

The interpretation theories of a physical signal allow to propose "generalizations" of a function defined on a set of samples. Again the properties of the function are "guessed" : for example the existence and bounds of the derivatives, cf. J. C. SIMON (²⁵).

### V.5. The use of "a priori" operations

Artificial Intelligence techniques can be described, at the mathematical level, as the proper build up of a constructive function which maps the s.s.d. (the initial representation) on the f.s.d. (the wanted situation or goal). For this, given operations are combined, according to a set of axioms. See GPS of G. W. ERNST and A. NEWELL (⁷) or N. J. NILSSON (¹⁵).

Some heuristic evaluation functions may guide the build up of the operation combination. This combination is a mixture of sequential and parallel application of operations on intermediate structured datas (i.s.d.).

At the mathematical level, this can be described as an "algebra of functions". New functions are produced by combining the primitive functions, which we call here "operations".

A similar technique for classification has been tried by J. C. SIMON and C. ROCHE (²⁶). For more details see C. ROCHE thesis (¹⁸).

Let {$\varphi_k$} be a set of given dyadic operations (two arguments, one value). Let $X_p = \{x_1, ..., x_p\}$, $\dots, x_p$) be a structured data, here a list.

If $p = n$, it is a starting s.d.

If $p = 1$, it is a final s.d.

If $1 < p < n$, it is an intermediate s.d.

The obtention of $x_p$ from $X_{p-1}$ results from the replacement of $x_i$ and $x_j$ by $x_i = \varphi_k x_i x_j$.

But we have to specify at that step

- how $\varphi_k$ is chosen in the set

- how $x_i$ and $x_j$ are selected

- how $x_e$ is put in the $X_{p-1}$ list.

The $\&$ procedure specify these choices on the variables once for all.

To build this procedure, different heuristics are described in (¹⁶).

They are based on mutual information as an estimation of the average performance of the $\varphi_k$ operation at a given step.

#### Example 1

The problem is to separate a set of couples of points in a frame, the "distant points" set from the "close points" set.

A s.s.d. is $X = (x, y, u, v)$, the list of cartesian coordinates of the two points. The f.s.d. is the binary variable $u$, the interpretation of which is "distant" or "close". The primitive set of operations is $(+, -, *)$, obviously relevant to the problem. The building up of the proper $\&$ function is made by a "breadth first" tree search, evaluated by the mutual information heuristic.

The euclidian distance function is found after three steps only, for the given training set.

#### Example 2

The problem is to classify phonemes. Again the s.s.d. and i.s.d. are lists. The process used is more ambitious ; the set $\varphi_k$ is not given. The only request is that the $\varphi_k$ be dyadic functions. At each steps the "good" $\varphi_k$ function is build up by maximizing the "mutual information index" comparing the average $\varphi_k$ performance with an "ideal performance", as it is defined by the learning set.

The $\varphi_k$ are implemented as table look-up. Each can be described as a set of productions or rewriting rules.

$$x_i x_j \rightarrow x_e$$

The $\&$ procedure works usually well on the training set, but there is no guarantee outside. The generalization may fail.

The vowel recognition for one speaker attains a level of performance comparable to other "ad hoc" methods. The interest of this method is to be independent of any semantic information except the mutual information estimation.

### V.6. Remark on the concept of features

It is frequent to find in the P.R. litterature the word "feature". The concept comes from :

i) The decompositions of the $\&$ procedure in sub-procedures $\&_i$.

ii) The interpretations of the variable $X_i$ given by $\&_i$.

For example if a printed letter is to be recognized; straight lines, curves, closed loops are to be recognized by proper sub-procedures. Practically these partial recognitions help the global recognition.

The problem is still to build up the "good" sub-procedures, which on an s.s.d. will decide of the existence of the said features. It is then clear that a "feature" is a $\Phi$ interpretation of $X_i$, variable result of $\&$.

In the process of SIMON and ROCHE for example, sub-procedures are built automatically with the use of a mutual information semantic. Then one finds that the interpretations of the intermediate variables $X_i$ are quite hazy, if not impossible.
The idea of feature relies on an interpretation of
a i.s.d., which is not essential as long as the final
& is proper. On the other hand, as it has been said,
an interpretation depends essentially on the final goal
of the specific field. It may be quite different accor-
ding to the given semantic of the field.

# VI. CONCLUDING PROPOSITIONS FOR A RECOGNITION LANGUAGE

VI.1. From what has been said we will attempt now to describe the necessary framework of a language L, in which recognition should be described (cf. IID

i) a primitive set of terms

ii) a primitive set of functions

iii) an algebra of terms

iv) an algebra of functions

v) $\Phi$ interpretations in the domain of natural or mathematical language : the semantic of the domain

vi) some interpretations in the domain of programming languages or abstract machines : the implementations of the P.R. structured datas and procedures.

The point (v) deserves some development. The semantic interpretation plays a leading part :

## 1. Interpretation of datas

- s.s.d. as an initial or starting description of an experiment

- i.s.d. as possible "features"

- f.s.d. as a classification or a scene analysis.

## 2. Interpretation of functions (procedures)

Some examples of function semantics have been given in this paper through their mathematical properties or by corresponding relevant operations, (V.1. ... 5). An evaluation of the average performance of a given function is also a semantic V.5. These semantics allow to simplify or to build appropriate & functions (procedures).

Expressing this type of process should also be done in a formal way, generating then a "calculus of functions" (the functionals).

At the level of the abstract machine, a lattice or recursive procedures are implemented.

At the level of programming language, subroutines are linked sequentially of in parallel, or recursively.

Of course, remains the real problem of how to implement the semantic to generate automatically this calculus.

The feed-back of such a semantical process on the building of & functions is the modern version of a learning process in recognition.

To guide the functional (or procedural) calculus, many other semantical techniques may be proposed, different of the few briefly surveyed in this paper.

Scene analysis requires more refinements in two ways :

- data structures such as trees or more general graphs.

- procedures handling should rely more heavily on a complex semantic universe.

The A.I. Lab. of M.I.T., in particular P.H. WINSTON (³⁰) has suggested learning to describe scene analysis as a way to establish a semantic of concept forming. These lines of research seem quite important and promising.

# VII. PROSPECTIVE CONCLUSIONS

Though predictions should be advanced with the greatest care, it seems that the P.R. community should follow with attention and learn from the following current researches :

- the semantic of programming languages, which tries to automatize or at least give a mathematical interpretation of a computing algorithm, represented by a program schemata.

- Artificial Intelligence, which builds up procedures to solve problems, from a set of permitted operations. The semantic of the domain is implemented by heuristic techniques.

L. SIKLOSSY (²¹) has shown how the build up may be greatly simplified by a semantic more specific to the problem.

- **Computing functions theory and implementation.**
In particular recursive functions could be used as partially defined functions, (a constructive concept of fuzziness...). Complexity theory should also be of interest cf (³).

- **Semiotics (in french semiologie),** which is a current research of linguists trying to give a meaning to the phrase of a language. This field was initiated in 1910, by F. de SAUSSURE (²²), which underlined that a representation (signifiant) could not be separated from its interpretation (signifié).

In fact, are we not just beginning to realize that, like the iceberg, the hidden part is still the biggest and may be the most difficult to see...?

## Acknowledgment

The author wishes to thank E. DIDAY, G. GUIHO, and J. P. MAROY for many fruitful discussions and F. H. RAYMOND for his inspiring ideas on the algebras of computing functions.

## REFERENCES

(¹) R. B. BANERJI
A language for Pattern Recognition. Pattern Recognition Journal vol.1, n°1, pp. 63-74 (July 68).

(²) R. B. BANERJI
Some linguistic and statistical problems in Pattern Recognition. Pattern Recognition Journal vol. 3, n° 4, pp. 409-419 (Jan. 72).

(³) T. M. COVER
Generalization on Patterns using Kolmogoroff complexity. Proceedings of the first IJCPR. Washington Oct. 73, pp. 551-553.

(⁴) E. DIDAY
Optimization in non hierarchical clustering. Pattern Recognition Journal 6, 1, (1974).
(5) E. DIDAY
The dynamic clusters methods in non hierarchical clustering. Proceeding of the first IJCPR, Washington Oct. 73, available at IRIA - 78 - Rocquencourt - France.

(6) R. O. DUDA and P. E. HART
Pattern classification and scene analysis (John WILEY and sons).

(7) G. W. ERNST and A. NEWELL
GPS : a case study in Generality and Problem solving (Acad. Press. 69).

(8) K. S. FU
Sequential methods in Pattern Recognition and machine learning (Academic Press.).

(9) K. S. FU
Recent progress in linguistic methods applied to Pattern Recognition. Proceedings of the second IJCPR - Copenhaguen, Aug. 74.

(10) F. HAYES-ROTH
A structural approach to pattern learning and the acquisition of classificatory power. Proceeding of the first IJCPR, Washington Oct.73 pp. 343-351.

(11) A. K. JOSHI
Remarks on some aspects of language structure and their relevance to Pattern analysis. Pattern Recognition Journal. Vol. 5, n° 4, pp. 365-381 (Dec. 73).

(12) V. A. KOVALEVSKY in J. T. TOU
Advances in information systems sciences, vol. 3 Chap. I (Plenum Press).

(13) R. C. LYNDON
Notes on Logic - (Van Nostrand Math. Studies).

(14) J. MYLOPOULOS
On the application of formal language and automata theory to Pattern Recognition. Pattern Recognition Journal. Vol. 4, n° 1, pp. 37-51 (Jan. 72).

(15) J. N. NILSSON
Problem solving methods in Artificial Intelligence (Mc Graw Hill, 71).

(16) J. N. NILSSON
Learning machines : foundations of trainable pattern classifying systems (Mc Graw Hill).

(17) F. H. RAYMOND
Formalization du concept de calcul, algèbre des fonctions, Conservatoire National des Arts et Métiers, Paris.

(18) C. ROCHE
Thèse d'Etat, Dec. 72, Institut de Programmation Paris VI.

(19) C. ROCHE
Application of multilevel clustering to the automatic generation of recognition operators. Proceedings of the second IJCPR. Copenhaguen, Aug. 74.

(20) A. ROSENFELD
Picture processing by computer (Academic Press).

(21) G. SARAH
The notion of command operator in Pattern Recognition. Proceedings of the second IJCPR. Copenhaguen Aug. 74.

(22) F. de SAUSSURE
Cours de linguistique générale (Payot edit., Paris 1972).

(23) L. SIKLOSSY and J. DREUSSI
An efficient robot planner which generates its own procedures. Proceedings of the Third IJCAI Aug. 73, Stanford, Calif.

(24) J. C. SIMON, A. CHECROUN and C. ROCHE
A method of comparing two patterns independent of possible transformations and small distortions. Pattern Recognition Journal 4, 1. (Jan. 72) p.73.

(25) J. C. SIMON and G. GLIHO
Picture representation and transformations by computer. Pattern Recognition Journal 3, p. 169.

(26) J. C. SIMON and C. ROCHE
On automatic generation of Pattern Recognition operators. Proceeding of the 1972 IEEE, Int. Conf. on Cybernetics and Society, p. 232.

(27) R. THOM
Stabilité structurelle et morphogénèse (W. A. BENJAMIN, advanced book program, Reading Mass. U. S. A., 1972).

(28) L. UHR
Flexible linguistic pattern recognition. Pattern Recognition Journal. Vol. 3, n° 4, pp. 363-383 (Jan. 72).

(29) W. E. UNDERWOOD and L. N. KANAL
Structural descriptions, transformational rules, and Pattern analysis. Proceeding of the first IJCPR, Washington Oct. 73, pp. 434-449.

(30) P. H. WINSTON
Learning structural descriptions from examples. Ph. D. Thesis, A. I. Lab. M.I.T. Sept. 70.

(31) T. WINOGRAD
Ph. D. Thesis, A.I. Lab. M.I.T. (1971).
E. DIDAY

# CONTENTS

I - INTRODUCTION

II - DIFFERENTS TYPES OF RESEMBLANCE MEASURES

2.1. Nature of the data

2.2. Resemblance measures for quantitative data

2.3. Resemblance measures for qualitative data

2.3.1. Coding of ordinal and nominal qualitative data

2.3.2. Resemblance measures used between data units

2.3.3. Binary data

2.3.4. Resemblance measures between nominal variables

2.3.5. Distances between groups of data units.

III - ADAPTATIVE DISTANCES

3.1. A classical example of adaptative distance in classification

3.2. An example of adaptative distance in clustering.

IV - RESEMBLANCE MEASURE AND PERCEPTION

V - CONCLUSION.

# SUMMARY

We first show the link between the notion of similarity coefficient and pattern recognition in its "classification" and "clustering" aspect. Usual resemblance measures are presented according to the nature of the data (quantitative, qualitative ordinal or nominal, etc...).

The prospects of the author concerning further research in this field are presented laying particular stress on the importance of the dynamic aspect of the notion of resemblance measurement; two examples of adaptative distance are given. The link with "gestalt theorie" is suggested.

I - INTRODUCTION

A resemblance measure is a symmetrical function of $EXE \to R^+$. Conventionally we shall call "resemblance measure", either a "distance" or a "similarity coefficient". The distinction between these two notions stems from the fact that a distance is a measure of dissimilarity. In Pattern Recognition, this notion of resemblance measure appears under two aspects :

a) in classification, in order to assign a data unit to its most "similar" class (with respects to a given measure) among a prior set of classes.

b) in clustering, in order to build clusters of similar objects.

Numerous algorithms are based up on the fact that the resemblance measure is defined a priori and once of all. However, when one introduces data units which do not belong to the learning set, difficulties may arise either because the prior classes on the learning set are wrong, or because the variables are unable to express the classes, or even because the used distances are not adequate.

This is the reason why in a first part we will briefly review the principal distances which have been used so far in recent years while in the second part we propose methods using adaptative distances.

It is not the scope of this paper to give an exhaustive

list of the resemblance measures used at the present time. This is why we have restrained ourselves to the description of the non probabilistic resemblance measures.

II - DIFFERENTS TYPES OF RESEMBLANCE MEASURES

2.1. Nature of the data

The data may be roughly classified in two main types : quantitative or qualitative.

Quantitative data sets are those where the data units may take numerical values that are ordered and continuous. Qualitative data sets may be nominal (colour, illness names) or binary (answers yes, no) or ordinal (small, medium, large). For more details see [18].

2.2. Resemblance measures for quantitative data

Let $m$ be the number of data units, and $n$ the number of variables. A data unit will be represented by the vector

$$X_i^T = (x_{i1}, \dots, x_{ij}, \dots, x_{in}),$$

the variables will be noted

$$Y_j^T = (x_{1j}, x_{2j}, \dots, x_{mj}).$$

$$d_1(x_i, x_j) = \left[ \sum_{j=1}^{n} \left| x_{ij} - x_{i,j} \right| \right]^{\frac{1}{\lambda}} \quad (\text{Minkowsky metric})$$

$$d_2(x_i, x_j) = \sum_{j=1}^{n} \left[ \frac{\left| x_{ij} - x_{i,j} \right|}{(x_{ij} + x_{i,j})} \right] \quad (\text{Camberra metric})$$

$$d_3(x_i, x_j) = \max_j \left| x_{ij} - x_{i,j} \right| \quad (\text{Chebychev metric})$$

$$d_4(x_i, x_j) = (x_i - x_j)^T Q (x_i - x_j) \quad (\text{quadratic metric})$$

where $Q$ is a $m \times m_1$ matrix.

$$d_5(x_i, x_j) = [\det W] P^{-1} (x_i - x_j)^T W^{-1} (x_i - x_j) \quad (\text{Mahalanobis metric})$$

where $W$ is the covariance matrix of $(Y_1, \dots, Y_n)$

$$d_6(x_i, x_j) = \frac{\sum_{j=1}^{n} (x_{ij} - \bar{x}_j)(x_{i,j} - \bar{x}_i)}{\left[ \sum_{j=1}^{n} (x_{ij} - \bar{x}_j)^2 \sum_{j=1}^{n} (x_{i,j} - \bar{x}_i)^2 \right]^{1/2}} \quad (\text{correlation})$$

$$d_7(x_i, x_j) = \sum_{j=1}^{n} w_{ij} |x_{ij} - x_{i,j}| \quad (\text{"city block" metric})$$

$$d_8(x_i, x_j) = \sum_{j=1}^{n} \frac{1}{x_{ij}} \left( \frac{x_{ij}}{x_i} - \frac{x_{i,j}}{x_j} \right)^2 \quad (\text{X}^2 \text{ metric, Benzecri})$$

$$\text{where } x_j = \sum_{i=1}^{n} x_{ij} \quad \text{and} \quad x_i = \sum_{j=1}^{n} x_{ij}.$$
This distance, which is in great use in France, verifies a certain number of properties among which the so-called "Equivalence distributionnelle", in other words : two individuals i and i' with the same profile

(i.e. $\frac{x_{ij}}{x_i} = \frac{x_{i'j}}{x_{i'}}$) may be replaced by a third

one i' of same profile and whose weight is the sum of the weights of i and i' ($x_{ij} = x_i + x_{i'j}$)

and this without modification of the distance (according to $d_8$) between the data units or between the variables.

## 2.3. Resemblance measures for qualitative data

### 2.3.1. Coding of ordinal and nominal qualitative data

Let us consider the function Z : $\mathbb{N} \to \{0,1\}^k$ if k is the number of possible qualitative variable of a given variable. In the case of nominal data

$$Z^T(x_{ij}) = (0, \dots, 0, 1, 0, \dots, 0)$$

is a vector which contains only 0 except for the coordinate of rank $x_{ij}$, in other words :

$$(i) \quad y_j = \begin{pmatrix} 1 \\ 3 \\ 2 \\ 2 \\ 1 \end{pmatrix} \to Z^T \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$

In the case of ordinal data $Z^T(x_{ij}) = (1, \dots, 1, 0, \dots, 0)$

is a vector where all the coordinates are equal to 1 up to the rank $x_{ij}$, the following being null. In other words :

$$(ii) \quad y_j = \begin{pmatrix} 1 \\ 3 \\ 2 \\ 2 \\ 1 \end{pmatrix} \to Z^T \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$

A more detailed description of this coding can be found in [18].

### 2.3.2. Resemblance measures between data units

Let $Z_i = (z_{i1}, \dots, z_{it})$ be the vector representing the ith line of the table transformed by $Z^T$. It can be seen that by using this coding, any binary or quantitative distances may be used on the table transformed by $Z$.

This will allow us to show in 2.3.5 that the distance

$$d(Z_i, Z_{i'}) = \sum_{j=1}^{k} \frac{1}{z_j} (z_{ij} - z_{i'j})^2$$

amounts to the computation of a $\chi^2$.

Thus it can be shown that the distance $d_8$ of the $\chi^2$, due to Benzecri, can be written in the following way :

$$d_9(x_i, x_{i'}) = \sum_{j=1}^{n} \left( \frac{1}{P(x_{ij})} + \frac{1}{P(x_{i'j})} \right) \delta_{ii'}^j \quad \text{where}$$

$$\delta_{ii'}^j = \begin{cases} 1 & \text{if } x_{ij} \neq x_{i'j} \\ 0 & \text{if } x_{ij} = x_{i'j} \end{cases} \quad \text{and}$$

$P(x_{ij})$ the number of times that the qualitative variables

ble $x_{ij}$ is achieved for the variable j.

Let us give some classical similarity measures.

* Spearman's ranks coefficient :

$$d_{10}(x_i, x_{i'}) = 1 - \frac{6}{n(n-1)} \sum_{j=1}^{n} (x_{ij} - x_{i'j})^2$$

It can be shown that this measure is equivalent to $d_8$ hence $d_{10}$ measures the correlation between the ranks.

Furthermore, it is possible to get a test of the independence of $X_i$ and $X_{i'}$, from already existing tables.

* Kendall's ranks correlation.

$$\text{Let } \Delta_{jk} = (\text{the sign of } (x_{ij} - x_{ik})) \cdot 1$$

$$\Delta'_{jk} = (\text{the sign of } (x_{i'j} - x_{i,k})) \cdot 1$$

$$\tau = \frac{2}{n(n-1)} \sum_{j<k} \Delta'_{jk} \Delta_{jk} = 2 \frac{a-b}{n(n-1)}$$

where a is the number of times $\Delta_{jk}$ and $\Delta'_{jk}$ are of the same sign and b the number of times they are of opposite sign. Then :

$$d_{11}(x_i, x_{i'}) = 1 - \tau$$

* Distance between finite sequences :

P.H. Sellers (cf. [16]) propose a distance between a = (a_1, a_2, ..., a_p) and b = (b_1, b_2, ..., b_q) : $d(a,b)$ is the smallest number of steps necessary to make the sequences identical where a step is

(i) The deletion of a term from either sequence, or
(ii) The change of a term in either sequence, so as to make it equal to a term in the other sequence.

**Example**

$$a=(x,y,w,x) \quad b=(x,w,y,y,x) \Rightarrow d(a,b) = 2$$

because it takes at least 2 steps to make them alike.
1. change w to y in a,
2. delete w from b.

Sellers gives an algorithm which computes $d(a,b)$. The number of computational steps is $m^2n$ if $m < n$.

### 2.3.3. Binary data

If $X_i$ and $X_{i'}$ are two binary vectors, to define $D(x_i, x_{i'})$ it is necessary to introduce the four following quantities :

a = the number of times where $x_{ij}=1$ and $x_{i'}j=1$.

b = the number of times where $x_{ij}=0$ and $x_{i'}j=1$.

c = the number of times where $x_{ij}=1$ and $x_{i'}j=0$.

d = the number of times where $x_{ij}=0$ and $x_{i'}j=0$.

<table><tr><th>X<sub>i</sub></th><th>1</th><th>0</th></tr><tr><th>X<sub>i'</sub></th><td></td><td></td></tr><tr><th>1</th><td>a</td><td>b</td></tr><tr><th>0</th><td>c</td><td>d</td></tr></table>
The following similarity measures have often been used in biology (for further detail see [18]):

$$D_1(X_i, X_i') = \frac{a}{a+b+c+d} \qquad \text{Russel and Rao}$$

$$D_2(X_i, X_i') = \frac{a}{a+b+c} \qquad \text{Jaccard, Needham}$$

$$D_3(X_i, X_i') = \frac{a}{2a+b+c} \qquad \text{Dice}$$

$$D_4(X_i, X_i') = \frac{a}{a+2(b+c)} \qquad \text{Sokal and Sneath}$$

$$D_5(X_i, X_i') = \frac{a+d}{a+b+c+d} \qquad \text{Sokal and Michener} \\ \text{(simple matching coefficient)}$$

$$D_6(X_i, X_i') = \frac{a}{b+c} \qquad \text{Kulzinsky}$$

$$D_7(X_i, X_i') = \frac{a+d}{a+d+2(b+c)} \qquad \text{Rogers and Tanimoto}$$

$$D_8(X_i, X_i') = \frac{ad-bc}{ad+bc} \qquad \text{Yule}$$

$$D_9(X_i, X_i') = \frac{ad-bc}{[(a+b)(c+d)(a+c)(b+d)]^2} \qquad \text{Correlation.}$$

Let us call $E_i$ (resp. $E_{ij}$) the variables set for which $X_i$ (resp. $X_i'$) takes the value 1. The introduction by Léonard of the hypothesis of absence of link and the definition of two dual random variables of same distribution $S_i=\text{card}(E_i \cap Y)$, $S_i'=\text{card}(E_i' \cap Y)$ when $S$ designates the common random variable, allow him to introduce a new class of resemblance coefficients. The measure of similarity finally taken in consideration is the probability $P_r^{[S \subset \emptyset]}$, and the notion of likelihood is thus introduced in the notion of resemblance (cf. [10][11]).

### 2.3.4. Ressemblance measure between nominal variables

The joint distribution of two nominal variables is given in Table 2 (contingency table) where $n_{ij}$ is the number of data units which fall in both the ith class of variable $Y_i$ and the jth class of variable $Y_e$.

<table><thead><tr><th>Y_e</th><th>1</th><th>2</th><th>3</th><th>j</th><th>r</th><th>Totals</th></tr></thead><tbody><tr><th>Y_k</th><td>n<sub>11</sub></td><td>n<sub>12</sub></td><td></td><td></td><td></td><td>n<sub>1.</sub></td></tr><tr><th>1</th><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>2</th><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>i</th><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>P</th><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>Totals</th><td>n<sub>i.1</sub></td><td></td><td></td><td></td><td></td><td>n<sub>i..</sub></td></tr></tbody></table>

$$d_{11}(Y_e, Y_k) = \sum_{i=1}^{p} n_{i.} \sum_{j=1}^{r} \left| \frac{n_{ij}}{n_{i.}} - \frac{n_{.j}}{n_{.i}} \right| \quad (\text{see}[12], 1)$$

$$d_{12}(Y_e, Y_k) = \frac{1}{n_{.i}} \sum_{j=1}^{p} \max_{j} n_{ij} \quad (\text{see}[12], 1)$$

Chi-Square with $(p-1)(r-1)$ degree of freedom under the hypothesis of bivariate normality and independence

$$d_{13}(Y_e, Y_k) = n_{.i} \sum_{j=1}^{p} \sum_{i=1}^{r} \left( n_{ij} - \frac{n_{i.} n_{.j}}{n_{i.} n_{.i}} \right)^2 \frac{1}{n_{i.} n_{.j}}$$

Similarity measures based on the information

$$d_{14}(Y_e, Y_k) = I(Y_e) + I(Y_k) - I(Y_e \cap Y_k)$$

where

$$I(Y_e) = - \sum_i p_{i.} \log_2 p_{i.} \quad \text{where} \quad p_{i.} = \frac{n_{i.}}{n_{.i}}$$

$$I(Y_k) = - \sum_j p_{.j} \log_2 p_{.j} \quad \text{where} \quad p_{.j} = \frac{n_{.j}}{n_{j.}}$$

$$I(Y_e \cap Y_k) = \sum_{i,j} p_{ij} \log_2 p_{ij}$$

Under the independence hypothesis between $Y_e$ and $Y_k$ one shows that

$$d_{14}(Y_e, Y_k) = \frac{1}{\log 2} \sum_i \sum_j \frac{(n_{ij} - n_{i.} n_{.j})^2}{n_{i.} n_{.j}} = \frac{2}{\log 2}$$

### 2.3.5. Distances between groups of data units

Let $\mu$ be a function of the set of all subsets of $E$ in $\mathbb{R}^+$ such that

$$\mu(A) = \sum_{a \in A} \mu(a) \quad \forall A \subset E$$

Let us give

$$D(x,A) = \frac{1-\mu(A)}{\sum_{a \in A} a} \quad d(x,a)$$

$$G(A) = \frac{1}{\mu(A)} \sum_{a \in A} a$$

$$\text{var } A = \frac{1}{\mu(A)} \sum_{a \in A} d(a, G(A))$$

where $d$ is given by a quadratic metric, the Koenig-Huygens theorem can be used and one deduces the following formulas: $((A_1, \dots, A_k)$ is a partition of $E$).

$$D(x,A) = \mu(A)[d(x,G(A)) + \text{var } A]$$

$$\text{var}(\bigcup_{i=1}^{k} A_i) = \sum_{i=1}^{k} \mu(A_i) \text{var } A_i + \text{D}(A_1, \dots, A_k)$$

where

$$D(A_1, \dots, A_k) = \sum_{i=1}^{k} \mu(A_i) d(G(A_i), G(\bigcup_{j=1}^{k} A_j))$$

In the case of a partition in two classes we have:

$$D(A,B) = \frac{\mu(A)\mu(B)}{\mu(A)+\mu(B)} d(G(A),G(B))$$

If the initial table is supposed transformed by the function $z^i$ as indicated in 2.3.1. and if one takes $\mu(a)=1$ for $a \in E$,

$$G(A) = \frac{1}{\text{card } A} \sum_{a \in A} d(G(A),G(B))$$

$k$ is the number of qualitative variables of a given variable $Y_e$. Let $A_1, \dots, A_k$ be two parts of $E$ one gets the table 2 hence $G_j(A_i) = \frac{n_{ji}}{n_{.i}}$.

<table><caption>Table 2</caption><thead><tr><th>Y_e</th><th>A_1</th><th>A_2</th></tr></thead><tbody><tr><th>1</th><td>n<sub>11</sub></td><td>n<sub>12</sub></td></tr><tr><th>2</th><td></td><td></td></tr><tr><th>3</th><td></td><td></td></tr><tr><th>k</th><td>n<sub>k1</sub></td><td>n<sub>k2</sub></td></tr></tbody></table>
**Example**

Let $A_1 = \{X_2, X_5, X_6\}$;

$$Y_j = \begin{pmatrix} x_{1j} \\ \vdots \\ x_{6j} \end{pmatrix} = \begin{pmatrix} 1 \\ 3 \\ 2 \\ 2 \\ 2 \\ 1 \end{pmatrix} \quad \text{and let us consider} \\ \text{the case of an ordinal variable.}$$

$$\text{Then} \qquad \begin{pmatrix} z_j^T(X_2) \\ z_j^T(X_5) \\ z_j^T(X_6) \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$

$$\text{And } G_1(A_1)=1, \quad G_2(A_1)=\frac{2}{3}, \quad G_3(A_1)=\frac{1}{3}$$

$$\text{Let } d_{15}(z_i, z_j) = \sum_{j=1}^{k} \frac{1}{x_{.j}} (z_{ij} - z_{i,j})^2$$

Then, one has (cf. [19]):

$$\begin{align*} D(A_1, A_2) &= \mu(A_1)d(G(A_1), G(A_1 \cup A_2)) + \mu(A_2)d(G(A_2), G(A_1 \cup A_2)) \\ &= \sum_{i=1}^{2} n_{.i} \sum_{j=1}^{k} \frac{1}{n_{.j}} \left( \frac{n_{ji}}{n_{.i}} - \frac{n_{j.i}}{n_{..}} \right)^2 \\ &= \sum_{i=1}^{2} \sum_{j=1}^{k} \frac{1}{n_{.i} n_{.j}} \left( n_{j.i} - \frac{n_{.i} n_{.j}}{n_{..}} \right)^2 = \frac{x_{..}^2}{n_{..}} \end{align*}$$

### III - ADAPTATIVE DISTANCES

#### 3.1. Example of an adaptive distance in classification.

Sebestyen (cf. [15]) proposes the computation of local measures of similarity corresponding to the maximum aggregation of the points of a given group. Let $(P_1, P_2, \dots, P_K)$ be a partition of E and $N_K = \text{card } P_K$. One notes $X_i^K = (x_{i1}^K, x_{i2}^K, \dots, x_{im}^K)$ where $X_i^K$ is the ith element of the Kth group. Let us note

$$\begin{gathered} \bar{x}_j^K = \frac{1}{N_K} \sum_{i=1}^{N_K} x_{ij}^K \\ (\sigma_j^K)^2 = \frac{1}{K} \sum_{i=1}^{K} (x_{ij}^K - \bar{x}_j^K)^2 \end{gathered}$$

the similarity between an individual and a group is denoted by

$$D(\bar{x}_i^K, P_K) = \frac{1}{N_K - 1} \sum_{j=1}^{N_K} d(\bar{x}_i^K, x_j^K)$$

The measure of the aggregation of a group will be noted

$$D(P_K) = \frac{1}{N_K(N_K - 1)} \sum_{i=1}^{N_K} \sum_{j=1}^{N_K} d(x_i^K, x_j^K).$$

In Sebestyen's view (cf. [15]) the problem may be given as follows:

**Being given a partition** $(P_1, \dots, P_K)$ find $(W_1, \dots, W_K)$ which minimizes $\sum_{i=1}^{K} D(P_i)$ such that $d_i(a,b) = (a-b)^T W_i^{-1} (a-b)$

is quadratic for $i \in \{1, 2, \dots, K\}$. Of course it is necessary to impose constraints on $W_i$. With the following conditions

$$W_i = \begin{pmatrix} w_1^i & & & \\ & \ddots & & \\ & & \ddots & \\ & & & w_n^i \end{pmatrix} \quad \text{and} \quad \sum_{j=1}^{n} W_j^i = 1$$

one finds (cf. [15]).

$$\bar{W}_j^K = \frac{1}{(\sigma_j^K)^2 \sum_{i=1}^{n} \frac{1}{(\sigma_i^K)^2}}$$

In other words, less weight is given to the parameters of large variance.

A second Sebestyen's approach is to take any $w_i^K$, with the constraints $\det W_i^K = 1$; then $W_i = (\det V_i)^{-1} W_i^{-1}$ where $V_i$ is the variance covariance matrix of the group i variables (as in $d_i$)

#### 3.2. Example of an adaptive distance in clustering.

In most of existing clustering algorithms, a similarity measure is used which is the same for the whole space E and remains constant during the achievement of the algorithm. Some authors have already been interested in the adaptive distance in clustering, namely Chernoff [3] Sokal and Sneath [12]. This algorithm enters in the field of ISODATA (cf. [2]) and k-means ([12]). The similarity measure, while remaining quadratic, evolves by locally adapting itself to the structure of the space E until the point of convergence and by making decrease a criterion which expresses this adaptation. A more detailed development of this part can be found in [6].

##### 3.2.1. Formalization of the problem.

The set E to be classified is a finite set of $\mathbb{R}^p$.

• Let $L = \mathbb{R}^p \times \mathcal{B}$ where $\mathcal{B}$ is the set of all Euclidean distances on $\mathbb{R}^p$, the associated matrices of which have their determinants equal to 1.

• A resemblance measure D between an element x of E and an element $\lambda = (a,d)$ of L is defined as :

$$D(x, \lambda) = d(x, a)$$

• A resemblance measure I between any finite subset B of $\mathbb{R}^p$ and an element $\lambda = (a,d)$ of L is defined as :

$$I(B, \lambda) = \sum_{y \in B} d(a, y),$$

I(B, λ) therefore is the moment of inertia of B with respect to the point a for the distance d.

• Let $P_K$ be the set of all partitions of E in k classes and $\mathfrak{I}_K$ the set of all k-tuples $(\lambda_1, \dots, \lambda_k)$ where $\lambda_i \in L = \mathbb{R}^p \times \mathcal{B}$, $k$ is assumed a priori given.

##### 3.2.2. The criterion.

The Criterion which we try to optimize is the application of $V_K = \mathfrak{I}_K \times P_K$ in $\mathbb{R}^+$ defined as :

$$W(v) = W(L, P_K) = \sum_{i=1}^{k} I(P_i, \lambda_i) = \sum_{i=1}^{k} \sum_{y \in P_i} d(a_i, y)$$
where $v = (L,P)$

$$L = (\lambda_1, \dots, \lambda_k) \quad \text{with} \quad \lambda_i = (a_i, d_i)$$

$$\text{and } P = (P_1, \dots, P_k).$$

To minimize $W$ is equivalent to search among all couples $(L,P)$ the one which minimizes the sum of the moments of inertia of the classes $P_i$ with respect to the point $a_i$ for the distance $d_i$.

One can see that the distance is not determined once for all and moreover is different from one class to another.

### 3.2.3. The Method.

The aim of the algorithm is to find an element $v$ of $V_k$ which minimizes $W(v)$. It consists, by starting from an element $v \in V_k$ in building a sequence $(v_n)$ such that the associated value of the criterion $W(v_n)$ is decreasing.

To build this sequence two functions are used :

- $f: \mathcal{L}_k \to P_k$ function which associates a partition of $E$ in $k$ classes with $k$ point-distance couples.

- $g: P_k \to \mathcal{L}_k$ function which associates $k$ point-distance couples with a partition of $E$ in $k$ classes.

The sequence $(v_n)$ is then defined by
$$v_0 = (L^{(0)}, P^{(0)}) \text{ any couple in } V_k, \text{ and}$$

$$v_{n+1} = (g_o(f(L^{(n)}), f(L^{(n)})) \text{ if } v_n = (L^{(n)}, P^{(n)})$$

Let us now define $f$ and $g$ more precisely.

#### The identification function ;

$$f: \mathcal{L}_k \to P_k$$

If $L \in \mathcal{L}_k$ with $L = (\lambda_1, \dots, \lambda_k)$ and $\lambda_i = (a_i, d_i)$, $f(L)$ is the partition $n=(P_1, \dots, P_k)$ where

$$P_i = \{x \in D / D(x, \lambda_i) < D(x, \lambda_j) \quad \forall j \neq i\}$$

since

$$D(x, a_i) = d_i(a, x_i)$$

$$P_i = \{x \in E / d_i(x, a_i) < d_i(x, a_j) \quad \forall j \neq i\}$$

The class $P_i$ therefore is made of the elements of $E$ which are nearer to $a_i$ in terms of $d_i$ than to any $a_j$ in terms of $d_j$ for $j \neq i$.

#### The representation function

$$g: P_k \to L_k$$

If $P_k = (P_1, \dots, P_k)$ is a partition in $k$ classes of $E$, $g(P)$ is the $k$-tuple $L = (\lambda_1, \dots, \lambda_k)$ where $\lambda_i = (a_i, d_i)$ such that :

$$I(P_i, (a_i, d_i)) = \min_{(a,d) \in \mathbb{R}^p \times \mathbb{R}^q} I(P_i, (a,d))$$

If $B$ is a finite subset of $\mathbb{R}^p$, $d$ an Euclidean distance on $\mathbb{R}^p$, and $a^*$ defined as

$$I[B, (a^*, d)] = \min_{a \in \mathbb{R}^p} I[B, (a, d)],$$

one can prove that $a^*$ is the center of gravity of $B$ ($a^*$ does not depend on $d$).

If $B$ is still a finite set of $\mathbb{R}^p$, and if a couple

$(a^*, d^*)$ defined as

$$I[B, (a^*, d^*)] = \min_{(a,d) \in \mathbb{R}^p \times \mathbb{R}^q} I[B, (a, d)]$$

is searched, then one can prove the following proposition by using the above property and the results of [4] and [13] :

#### Proposition

- $a^*$ is the center of gravity of $B$,

- $d^*$ is the distance defined by the matrix $M=|Q|^{1/p} \cdot Q^{-1}$ where $Q$ is the covariance matrix of $B$ (i.e. $d^*$ is the Mahalanobis distance associated with $B$).

Consequently the function $g$ will associate with a partition $(P_1, \dots, P_k)$ the $k$-tuple $(\lambda_1, \dots, \lambda_k)$ where $\lambda_i$ is the couple : center of gravity of $P_i$ - Mahalanobis distance of $P_i$.

### 3.2.4. Convergence Properties

The sequence $(v_n)$ is said to be convergent if and only if : $\exists N, \forall n>N \ v_n = v_N$. Let us note :

$$v_n = (L^{(n)}, P^{(n)})$$

$$L^{(n)} = (\lambda_1^{(n)}, \dots, \lambda_k^{(n)})$$

$$\lambda_i^{(n)} = (a_i^{(n)}, d_i^{(n)})$$

$$Q_i^{(n)} \text{ is the covariance matrix of } P_i^{(n)}$$

By using the results of [4] one can prove the following result :

#### Theorem

The sequence $(v_n)$ converges and makes the following criterion decrease :

$$W(v_n) = \sum_{i=1}^{k} \sum_{x \in P_i} d_i^{(n)}(a_i^{(n)}, x)$$

which can also be written :

$$W(v_n) = p \sum_{i=1}^{k} \mathrm{card}(P_i^{(n)}). |Q_i^{(n)}|^{1/p}$$

#### Remarks

It can be proved that this algorithm tends to give classes such that the product of the variances of each class on all inertia axes of this same class is the least possible.

Moreover the obtained solution is invariant for any change of basis on the vector space $\mathbb{R}^p$ which contains the space $E$ of the individuals to classify.
## IV - RESEMBLANCE MEASURE AND PERCEPTION

It seems that there exists an analogy between the approach presented in III and the Gestalt Theorie (cf. [7], [9]). As a matter of fact, the perception can be considered as the interpretation of some kind of screening (syntactic aspect) of the external world (the universe) through the sensorial organs. The comprehension of the situation (semantic aspect) then occurs and may put back the function on the perception and so on until an equilibrium position is reached.

"... the comprehension is not overadded to the perception. The improvements in the understanding of a situation are formal changes of the perception, aspects modifications where the sensitive characters are altered." (P. Guillaume in [8]). In fact, the methods based on adaptative distances draw their inspiration from the same model. The field to be studied has been defined from the external world with the help of an operator called *h*, this field is characterized by a learning set (coding, a priori types) and is a function of the chosen distance. The comprehension of the situation (the interpretation of the clusters, significations, relations between them, etc...) is achieved after having used a classification operator *f* and it can be put back in question by the operator *g* (*g* sets back *d*, hence the field). The schemes (1) and (2) point out at the analogy in question

<figure><img src="image_4.png" /><figcaption>Scheme 1</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Scheme 2</figcaption></figure>

## CONCLUSION

The notion of similarity measure is closely related to the choosen field : way of coding, learning set, prior classification. Classification of clustering algorithms call out a certain number of operations which, combined with the used resemblance measure, will have an effect upon the obtained result. For further research it will be necessary to take into account the two following ideas :

1. The interaction between the resemblance measure, the field, and the implicit operators of the used algorithms.

2. According to J.C. Simon ideas (cf. [17]), after having sifted out the primitives of scheme 2 for example, the use of the information processing tool should allow the introduction of more "powerfull" operators than those usually used by mathematicians.

données" - I:- La taxinomie. Dunod.

[2] Ball J.M., 1970, "Classification analysis", Tech. note, Stanford Res. Inst., Menlo Park, California.

[3] Chernoff I. 1970, "Metric considerations in cluster analysis", Proc. of the Sixtn Berkeley symposium on Math. Stat. and Prob.

[4] Diday E., 1972, Thèse d'Etat, Université de Paris VI.

[5] Diday E., 1973, "Analyse factorielle typologique". Rapport Laboria n°27, IRIA Rocquencourt (78).

[6] Diday E., Govaert G., 1974, "Adaptative resemblance measure in pattern recognition". Sémin. IRIA, Bonas.

[7] Guillaume P., 1947, " La psychologie de la forme". Gallimard, 1964.

[8] Guillaume P., 1973, Préface à "l'intelligence des singes supérieurs" de Köhler. CEPL PUF.

[9] Köhler W., 1964, "La psychologie de la forme". Gallimard, 1964.

[10] Lerman I.C., 1970, "les Bases de la classification automatique". Dunod.

[11] Lerman I.C., 1973, "Introduction à une méthode de classification automatique illustrée par la recherche d'une typologie des personnages enfants à travers la littérature enfantine". Revue de Statistique appliquée. Vol XXI n°3, Paris 1973.

[12] Mac Queen J., 1967, "Some methods for classification and Analysis of Multivariate observations". The 5th Berkeley Symposium on Mathematics, Statistics and Probability. vol. 1, n°1.

[12] Morgan J.N. and Messenger R.C., 1973, "Thaïd". Thomson-Shore, Ann-Arbor. (Michigan).

[13] Romeder J.M., 1969, "Méthodes de discrimination", Thèse de 3ème Cycle, Statistique Mathématique, Faculté des Sciences de Paris VI.

[14] Scott A.J. and Symons M.J., 1971, "Clustering, methods based on likelihood ratio criterias". Biometrics 27, n°2, 387-398.

[15] Sebestyen C.S., 1962, "Decision Making Processes in Pattern Recognition", The Macmillan Company.

[16] Sellers P. 1974, "An algorithm for the distance between two finite sequences". Journal of Computational Theory (A) 16, 253-258.

[17] Simon J.C., 1974, "A formal aspect of Pattern Recognition and Scene Analysis". I.J.C.P.R. II, Feb. 74.

[18] Sneath P. Sokal R. 1974, "Numerical Taxonomy", W.M. Freeman Ed.

[19] Tenenhaus M., Bouroche J.M. (1970), "Some segmentation methods", Metra vol IX, n°3.

[20] Wishart D. 1971, "Some problems in the theory and Application of the methods of numerical Taxonomy". Ph. D. Thesis, University of St. Andrews.

[21] Wolfe J.M., 1970, "Pattern clustering by Multivariate mixture analysis". Behavioral Res. 5, n°3. 329,350.

[0] Anderberg M.R., 1973, "Cluster Analysis for applications". Acad. Press.

[1] Benzecri J.P. et collaborateurs, 1973 "Analyse des
CLASSIFICATION AUTOMATIQUE SEQUENTIELLE POUR GRANDS TABLEAUX

E. DIDAY

I.R.I.A. - Domaine de Voluceau-Rocquencourt
78150 LE CHESNAY (France)

Abstract

On donne une méthode de classification automatique adaptée au traitement des grands tableaux grâce à l'économie de place en mémoire centrale. On montre que l'espace des solutions obtenues est identique à celui que l'on obtient avec la méthode des nuées dynamiques. On donne quelques variantes et on explicite les critères que ces variantes tendent à optimiser. Dans le cas d'un tableau de modalité, on propose une formulation de la distance du $X^2$ de Benzecri adaptée à la méthode.

I - INTRODUCTION

Dans tous les domaines où l'on peut définir un ensemble E dans lequel les éléments peuvent être reliés par une mesure de ressemblance, il est possible de classifier ; autrement dit, de chercher à détecter des classes d'objets telles que deux objets d'une même classe soient plus proches au sens de cette mesure de ressemblance que deux objets appartenant à des classes différentes. On peut concevoir des classifications plus ou moins bonnes au sens d'un certain critère. Le but de cet article est de donner des méthodes tendant à optimiser de tels critères et qui soient adaptées au traitement de grands tableaux nécessitant plus de 100 K mots mémoire.

La classification hiérarchique a intéressé beaucoup de chercheurs (cf. (2), (3), (6), (12), (13), (15), (18)). C'est une méthode qui permet de fournir des partitions de E emboîtées les unes dans les autres, sous forme d'un arbre. Dans le cas de grands tableaux, ce type de méthodes se heurte à deux difficultés :

a) Le découpage de l'arbre pour obtenir des classes permettant de définir des types.

b) La nécessité de stocker un tableau à $\frac{N(N-1)}{2}$ cases correspondant aux distances deux à deux des éléments de E.

L'arbre de longueur minimum (cf. (11) et (20)) permet une approche séduisante du problème en fournissant un arbre dont les sommets sont les éléments de E et la longueur des arêtes représente le degré de ressemblance entre les éléments reliés. La méthode permet de construire un arbre dont la somme des longueurs des arêtes est minimum. Bien que soumise à l'effet de chaîne, la représentation visuelle d'un tel arbre peut être très enrichissante. Pour définir des types dans le cas d'ensembles de grande taille, il faut utiliser des techniques de découpage dépendant de seuils a priori.

On peut concevoir beaucoup de méthodes permettant de fournir uniquement une partition de E. A notre avis, les plus intéressantes sont celles qui réduisent au maximum le nombre de paramètres arbitraires et qui expriment le critère qu'elles optimisent ; les méthodes qui font l'objet de ce travail nécessitent la connaissance du nombre de classes de la partition cherchée, autrement dit, du degré de finesse désiré par l'utilisateur ; de plus un critère simple permet de saisir la signification de la partition obtenue. Ces méthodes dites des "nuées dynamiques" sont basées sur le choix de trois fonctions :

h est une fonction qui permet de définir l'ensemble E et une méthode de mesure sur cet ensemble (codage, mesure de ressemblance, types a priori, etc.) ;

g une fonction de représentation d'une classe quelconque de E ;

f une fonction permettant de situer un élément quelconque de E à l'aide de cette représentation.

La méthode des nuées dynamiques (notée MND cf. (7) et (9)) consiste à entrer E en mémoire centrale et à utiliser successivement et de manière alternative f et g jusqu'au moment où une position d'équilibre (correspondant à un optimum local du critère) est atteinte. La Méthode des Nuées Dynamiques Séquentialisée (notée MNDS), à laquelle cet article est consacré, est basée sur le même principe que la MND mais ne nécessite pas la mise en mémoire centrale du tableau de données associé à E, tout en n'occasionnant pas une perte de temps importante par rapport à la MND ; ceci est un avantage considérable pour les grands tableaux.

La MND et la MNDS peuvent être considérées comme une généralisation d'un ensemble de procédés appelés "Itération relocation procédure" par certains auteurs (Cormack (1971), Wishart (1971)), k-means par d'autres (Mc Queen (1967), Watanabé (1972)). Ces procédés peuvent grossièrement s'énoncer comme suit : on part de k points estimés ou choisis dans la population ; ces k points jouent le rôle de centres ; tous les points sont affectés au centre le plus proche suivant l'une des deux techniques suivantes :

a) Les k centres peuvent changer quand tous les points sont classés (Forgey (1965), Hall et Ball (1965), Jancey (1966)). La moyenne de chaque groupe est calculée et ce point est pris pour nouveau centre.

b) Les k centres peuvent se déplacer après l'affectation de chaque point (Thorndike (1953), Mc Queen (1967), Beale (1969), Wishart (1971)). Quand un point est ajouté à un groupe, la moyenne de ce groupe est ajustée de manière à prendre le nouveau point en compte. Cette moyenne définit le nouveau centre.

Finalement, toute la population est itérativement classée plusieurs fois avec la technique a) Beale (1969), Wishart (1971) et la technique b). Le procédé est arrêté quand un nombre d'itérations (fixé à l'avance) se produit ou quand il y a oscillation ou stabilisation du processus. Signalons que des programmes anglo-saxons classiques comme ISODATA font intervenir des seuils arbitraires d'union et de découpage des classes pendant le déroulement de l'algorithme (cf. (16)).

La MND admet comme cas particulier a) si la fonction de représentation g fournit des centres de gravité.

La MNDS consiste à utiliser g dès que tous les individus d'un paquet sont affectés. Même si g fournit des centres de gravité, cette méthode reste plus générale que b) et doit permettre un gain de temps appréciable, en réduisant le nombre de centrages.

L'apport nouveau de cet article tient principalement à :

<footnote>§ Cet article est un extrait d'une note plus importante (50 p) qui peut être obtenue à l'I.R.I.A.</footnote>
1°) l'introduction de la MNDS,

2°) les propriétés de convergence pour différentes variantes auxquelles on associe des critères significatives pour l'utilisateur,

3°) la démonstration de l'équivalence du point de vue des solutions obtenues de MND et MNDS (donc de a) et b).

## II - NOTATIONS

• E est l'ensemble des objets à classifier.

• $L_k = \{L^i = (A_1, ..., A_k) / A_i \subset B\}$, B est un espace dépendant des variantes.

• P(E) est l'ensemble des parties de E.

• P<sub>k</sub> est l'ensemble des partitions de E en k classes.

P, Q<sub>P</sub><sub>k</sub> seront notés P = (P<sub>1</sub>, ..., P<sub>k</sub>) et
Q = (Q<sub>1</sub>, ..., Q<sub>k</sub>).

• D : E x P(B) → R<sup>+</sup>

• F : P<sub>k</sub> x P(E) x L<sub>k</sub> → P<sub>k</sub> est donnée par :

F(Q,H,L) = P où P est défini à l'aide d'une suite
{Π<sub>n</sub>} de P<sub>k</sub> comme suit :

On note Π<sub>ℓ</sub> = (Π<sub>ℓ₁</sub>, ..., Π<sub>ℓₖ</sub>) et H = {y₁, ..., yₘ}.

Soit Π<sub>o</sub> = Q, la suite Π<sub>n</sub> se définit par récurrence à partir de Π<sub>o</sub> ; étant donné Π<sub>ℓ-1</sub> on construit Π<sub>ℓ</sub> comme suit : (on suppose y <sup>-1, j</sup><sub>-1, j</sub>)

a) $\forall i : D(y_i, A_i) < D(y_{i-1}, A_{i-1})$ avec j < i en cas d'égalité ; alors $\Pi_{i-1}^i = \Pi_{i-1}$

b) $\exists i : D(y_i, A_i) \le D(y_{i-1}, A_{i-1})$ avec j > i en cas d'égalité ; alors $\Pi_{i-1}^i = \Pi_{i-1}$, $\exists j \in \{y_i, \dots, y_{i-1}\}$ $\Pi_{i-1}^j = \Pi_{i-1, j}^j = \{y_{i-1}\}$ et $\Pi_{i-1, n} = \Pi_{i-1, n}$

On pose finalement P = Π<sub>m</sub>.

• R est une application dite "d'agrégation-écartement" qui est définie sur $B \times \mathcal{J}[k] \times P_k$ et à valeurs dans $R^+$ (ou $\mathcal{J}[k] = \{1, 2, ..., k\}$).

• On se donne k nombres entiers n₁, ..., nₖ.

• g<sup>s</sup>: P<sub>k</sub> → L<sub>k</sub> est telle que g<sup>s</sup>(P) = L = (A<sub>1</sub>, ..., A<sub>k</sub>) où
A<sub>i</sub> = {les n<sub>i</sub> éléments de B qui minimisent R(x, i, P)}

• W: V<sub>k</sub> = L<sub>k</sub> x P<sub>k</sub> → R<sup>+</sup> est le critère à optimiser, il s'écrit W(v) = Σ<sub>i∈J[k]</sub> Σ<sub>x∈A<sub>i</sub></sub> R(x, i, P) où v = (L,P).

S' : S'(L,P) = W(v) ∀v = (L,P)

## III - L'ALGORITHME DE BASE MNDS

On part de P<sup>(o)</sup> et on en déduit L = g<sup>s</sup>(P<sup>(o)</sup>) et
P<sup>(l)</sup> = F(P<sup>(o)</sup>), H<sup>(o)</sup>, L<sup>(l)</sup>).

On note H<sup>(o)</sup>, H<sup>(l)</sup>, ... H<sup>(N)</sup> une partition de E et on définit la suite H<sup>(n)</sup> en posant H<sup>(n)</sup> = H<sup>(r)</sup> si r est le reste de la division de n par N + 1. L'algorithme MNDS est défini par la suite v<sup>(n)</sup> suivante :

on a v<sub>1</sub> = (L<sup>(1)</sup>, P<sup>(1)</sup>) et v<sub>n+1</sub> = (L<sup>(n+1)</sup>, P<sup>(n+1)</sup>) se déduit de v<sup>(n)</sup> = (L<sup>(n)</sup>, P<sup>(n)</sup>) comme suit :

P<sup>(n+1)</sup> = F<sup>(n)</sup>(P<sup>(n)</sup>), H<sup>(n)</sup>, L<sup>(n+1)</sup>) et L<sup>(n+1)</sup> = g<sup>s</sup>(P<sup>(n)</sup>).

On pose u = W(v), z = S'(L<sup>(n+1)</sup>, P<sup>(n)</sup>), H<sup>(n)</sup>
= {y<sub>0</sub>, ..., y<sub>m</sub><sup>n</sup>}, la suite Π<sub>ℓ</sub> associée à H<sup>(n)</sup> sera no-

tée Π<sub>ℓ</sub>. Pour simplifier, on supposera que tous les
blocs H<sup>(n)</sup> sont tels que card (H<sup>(n)</sup>) = m fixé et donc
card E = mN (toutes les démonstrations qui suivent res-
tent valables si m est variable).

## Définition :

On dira que R est carré au sens de MNDS si VP,L,y

S'(L, F(P, y, L)) < S'(L, P).

## Théorème 1

Si R est carrée au sens de la MNDS alors les suites u<sub>n</sub> et z<sub>n</sub> convergent en décroissant et la suite v<sub>n</sub> converge.

## IV - LIENS ENTRE MND ET MNDS

### 4.1.- Rappel concernant la MND

R est définie comme précédemment.

On introduit une application f : L<sub>k</sub> → P<sub>k</sub> telle que
f(L) = P où

P<sub>i</sub> = {x ∈ E / D(x, A<sub>i</sub>) ≤ D(x, A<sub>j</sub>)} en cas d'égalité, on affecte x à la classe de plus petit indice.

L'application g : P<sub>k</sub> → L<sub>k</sub> est donnée par g(P) = L où
L = (A<sub>1</sub>, ..., A<sub>k</sub>) avec A<sub>i</sub> = { les n<sub>i</sub> éléments de B mini-
mis nt R(., i, P)}.

S est une application L<sub>k</sub> x L<sub>k</sub> → R<sup>+</sup> telle que

$$
S(L,M) = \sum_{i=1}^{k} \sum_{x \in A_i} R(x,i,f(M))
$$

Le critère s'écrit alors W(v) = Σ<sub>i=1</sub>Σ<sub>x∈A<sub>i</sub></sub> R(x, i, P) où
v = (L, P).

### 4.2 - Comparaison des solutions obtenues par MND et MNDS

Afin de simplifier l'énoncé du résultat suivant, nous dirons qu'un algorithme MNDS est associé à un algorithme MND si les applications F, f, g<sup>s</sup> et g qui leur correspondent, se définissent à partir des mêmes applications D et R. Rappelons qu'une application R est dite carrée au sens de MND (cf (1), (2)) si ∀ L, M, L<sub>k</sub> S(L,M) < S(M, M) = S(L, L) < S(L, M) (2).

Nous avons démontré (cf (8)) que si R est carrée au sens de MND, l'algorithme de base de la MND fait décroître le critère W.

## Théorème 2

Soit BC E. Etant donné un algorithme de base de la MND et l'algorithme de la MNDS qui lui est associé, si R est carrée au sens de MNDS et au sens de MND alors ces deux algorithmes font décroître le même critère et convergent vers les mêmes solutions.

### 4.3 - Une condition suffisante pour que R soit carrée au sens de MND et de MNDS

#### Proposition 1

Pour que R soit carrée simultanément au sens de MND et au sens de MNDS, il suffit que la condition suivante soit vérifiée<sub>k</sub> :

$$
(1) \quad S'(L,P) = \sum_{i=1}^{k} \sum_{x \in P_i} \mu(z) D(z,A_i) \quad \forall L = (A_1, \dots, A_k) \in L \\
\text{et } P = (P_1, \dots, P_k) \in P.
$$

### 4.4 - Intérêt comparé des deux méthodes

MNDS peut être comçue de manière à ne nécessiter qu'une seule fois l'entrée en mémoire de toute la population
à chaque itération(1), et le calcul des moyennes s'effectue séquentiellement, bloc par bloc, alors que la MND nécessite deux fois cette entrée à chaque itération (une fois pour le calcul de la partition, une seconde fois pour le calcul des noyaux). De plus pour la MND, les centrages s'effectuent classe par classe, ce qui est très lourd si le tableau des données n'est pas en mémoire centrale. L'inconvénient de la MNDS est qu'elle nécessite N-k (N est le nombre de parties $P_i$) centrages supplémentaires et plus coûteux, à chaque itération (le nombre d'itérations avant convergence semble être sensiblement le même pour les deux méthodes).

## V - ÉTUDE DE QUELQUES VARIANTES DANS LE CAS SEQUENTIEL

On introduit une application $d: E \times E \to R^+$ symétrique et une mesure $\mu: P(E) \to R^+$ telle que

$$ \mu(A) = \sum_{x \in A} \mu(x) $$

Pour les variantes 5.1, 5.2 et 5.3 qui suivent, nous donnons simplement D et R ; les algorithmes MND et MNDS associés se définissent comme en (2) et (4.1) à partir des applications F, $g^s$, f et g qui se déduisent de D et R.

### 5.1 - Cas d'une pondération constante

Dans ce cas $\mu(x)$ est constant, on prendra pour simplifier

$$ \mu(x) = 1 \forall x \in E $$

$$ D(x,A) = \frac{1}{\text{card } A} \sum_{a \in A} d(x,a) \text{ et } R(x,i,P) = \frac{\text{card}(P_i)}{n_i} D(x,P_i) \\ (n_i \text{ le nombre d'éléments par noyau est constant } \tilde{V}) $$

### 5.2 - Cas d'une pondération variable

Dans ce cas $\mu(x)$ est quelconque et on choisit D et R comme suit :

$$ D(x,A) = \sum_{y \in A} \mu(y) d(x,y) $$

$$ R(x,i,P) = \mu(x) D(x,P_i) $$

### 5.3 - Méthode des "centres de gravité séquentielisée" (C.G.S.)

$$ \text{Ici on a } E \subset \mathbb{R}^m, B \equiv \mathbb{R}^m, n_i = 1 \text{ si } i \in \{1,2,...,k\} \\ D(x,A) = d(x,G(A)) \text{ où } G(A) = \frac{1}{\mu(A)} \sum_{x \in A} \mu(x) \times \\ R(x,i,P) = \sum_{y \in P_i} \mu(y) d(x,y) $$

Ce type de méthode a été introduite par Thorndike (1953) et approfondie par Mac Queen (1967). Nous allons préciser les applications F et $g^s$ qui se déduisent facilement de D et R.

* F se définit comme en 1) en remplaçant partout D par d

* $g^s: P_k \to L_k$ est telle que $g^s(P) = L = (A_1, A_2, ..., A_k)$ où $A_i$ est l'élément de B qui minimise

$$ R(x,i,P) = \sum_{y \in P_i} \mu(y) d(x,y) $$

Comme d est quadratique, on en déduit facilement que $A_i = \frac{1}{\mu(P_i)} \sum_{x \in P_i} \mu(x) \times (\text{i.e. } A_i \text{ est le centre de gravité de } P_i)$.

Du point de vue informatique on économise du temps calcul en utilisant les centres obtenus à l'itération n :

$$ A_j^{(n+1)} = \frac{A_j^{(n)} \omega_j^{(n)} + \sum_{i=1}^{m} \epsilon_i \mu(y_i^{(n)}) y_i^{(n)}}{\omega_j^{(n+1)}} \quad \text{où} $$

$$ \xi_i = +1 \text{ si } y_i^{(n)} \in P_i^{(n)} \text{ et } y_i^{(n)} \notin P_i^{(n-1)} $$

$$ \xi_i = -1 \text{ si } y_i^{(n)} \in P_i^{(n)} \text{ et } y_i^{(n)} \in P_i^{(n-1)} \quad (\text{pour } j \neq i) $$

$$ \xi_i = 0 \text{ si } y_i^{(n)} \in P_i^{(n)} \text{ et } y_i^{(n)} \in P_i^{(n-1)} $$

$$ \omega_i^{(n+1)} = \omega_i^{(n)} + \xi_i \mu(y_i^{(n)}), \omega_i^{(0)} = \mu(P_i^{(0)}) $$

On vérifie facilement, à l'aide de ces formules, que $A_i^{(n+1)}$ est bien le centre de gravité de $P_i^{(n)}$.

### Proposition 2

R est carrée au sens de MND et de MNDS pour les méthodes 5.1, 5.2 et 5.3.

## VI - EXPRESSION DU CRITÈRE DANS LE CAS OU D EST

### QUADRATIQUE

Dans le cas où d est une distance quadratique et pour les différentes variantes, nous pouvons exprimer les critères à optimiser en fonction de la variance des classes et des noyaux. On dira que d est une distance quadratique si $\forall x,y \in E$ on a :

$$ d(x,y) = (x - y)' Q(x - y) $$

où Q est une matrice définie positive.

On pose de plus dans tout ce qui suit :

$$ \text{var } B = \frac{1}{\mu(B)} \sum_{x \in B} \mu(x) d(x,G(B)) $$

$$ \text{et } G(B) = \frac{1}{\mu(B)} \sum_{x \in B} \mu(x) \times \forall B \subset E. $$

Soit $v = (L,P)$ avec $L = (A_1, ..., A_k)$

$$ \text{et } P = (P_1, ..., P_k) $$

### Théorème 3

a) La méthode 5.1 (pondération constante) fait décroître le critère :

$$ W_1(v) = \sum_{i=1}^{k} \mu(P_i) [\text{var } P_i + \text{var } A_i + d(G(A_i), G(P_i))] $$

b) La méthode 5.2 (pondération variable) fait décroître :

$$ W_2(v) = \sum_{i=1}^{k} \mu(P_i) \mu(A_i) [\text{var } P_i + \text{var } A_i + d(G(A_i), G(P_i))] $$

c) La méthode des centres de gravité séquentielisée fait décroître simultanément les deux critères suivants :

$$ W_3(v) = \sum_{i=1}^{k} [\mu(P_i) \text{var } P_i + d(A_i, G(P_i))] $$

$$ W_4(v) = \sum_{i=1}^{k} \mu(P_i) \text{var } P_i $$

<footnote>(1) On dit qu'une "itération" est effectuée si tous les éléments de E ont été consulté pour la réalisation d'une nouvelle partition et le calcul de nouveaux noyaux.</footnote>
## VII - INTERET COMPARE DES DIFFERENTES VARIANTES

Pour la méthode à masse constante (variante 5.1), on voit que la tendance est de faire décroître la variance des classes et des noyaux et de rapprocher au mieux chaque noyau du centre de la classe qui lui est associée.

On peut faire la même constatation pour la variante 5.2 en remarquant de plus que cette méthode favorise les noyaux de faible masse. Par exemple, dans un tableau de contingence, si le poids d'un individu est sa fréquence ; on aura tendance à former des classes proches de noyaux formés d'individus similaires et caractéristiques (puisque de faible fréquence).

En ce qui concerne la méthode du centre de gravité, (5.3) l'algorithme forme des classes autour de points moyens, sans être influencé par le fait que de tels points se situent en des endroits à forte densité. Ceci peut être gênant notamment dans le cas où le nombre de classes demandées est faible par rapport au nombre d'individus. Obtenir des classes d'intérieur creux peut être intéressant pour l'obtention de certaines formes géométriques ou artificielles.

Cependant, pour des données vivantes (physiques, biologiques, économiques etc...) une forme est un être que la nature tend à reproduire de manière plus ou moins parfaite. Plus cette reproduction est exacte plus la forme a une réalité objective et plus elle correspond à une zone de forte densité de points dans l'espace des paramètres. C'est ce type de forme qui intéresse l'utilisateur et il correspond à des classes d'intérieur plein. Signalons de plus le fait que les classes obtenues par la méthode du centre de gravité seront d'autant meilleures qu'elles sont éloignées du centre de gravité global, (il suffit d'utiliser le théorème de Huygens).

## VIII - EXEMPLE D'INDICE DE RESSEMBLANCE

### 8.1 - Distance du $\chi^2$ de Benzecri

Notons $P(i,j)$ la valeur prise par l'individu $y_i$ pour le paramètre $j$. On pose :

$$P(i,..) = \sum_j P(i,j) \quad P(.,j) = \sum_i P(i,j).$$

$$P(.,..) = \sum_{i,j} P(i,j)$$

La distance du $\chi^2$ entre deux individus $i$ et $i'$ s'écrit :

$$d(i,i') = \sum_j \frac{1}{P(j,j)} \left( \frac{P(i,j)}{P(i,..)} - \frac{P(i',j)}{P(i',..)} \right)^2$$

On considère qu'un individu $y_i$ est caractérisé par le vecteur

$$\vec{y}_i = \frac{P(1,j)}{P(1,..)}; \dots, \frac{Pcard(E),j)}{P('card(E),..)} \text{ et soit Q la}$$

matrice diagonale telle que $Q(j,j) = \frac{1}{P(j,j)}$. Alors d peut s'écrire sous la forme $d(i,i') = \vec{y}_i \cdot \vec{y}_{i'}$.

La mesure $\mu$ de $E \to R^+$ est $\mu(y_i) = P(i,..)$ pour $A \subset E$

$$\text{on note } \mu(A) = \sum_{y_i \in A} \mu(y_i)$$

$$\text{Soit } [A] = \{i | y_i \in A\}$$

Le centre de gravité s'écrit alors :

$$\vec{G}(A) = \frac{1}{\mu(A)} \sum_{i \in [A]} \mu(y_i) \vec{y}_i$$

d'où :

$$C_j(A) = \frac{1}{\sum_{i \in [A]} P(i,..)} \sum_{i \in [A]} P(i,..) \frac{P(i,j)}{P(i,..)} = \frac{1}{\sum_{i \in [A]} P(i,..)} \sum_{i \in [A]} P(i,j)$$

Par définition, on a :

$$\text{var } A = \frac{1}{\mu(A)} \sum_{i \in [A]} \mu(y_i) d(y_i, G(A))$$

Dans le cas de la variante 5.1 où il faut que les noyaux aient la même masse, on pose $\mu(y_i) = 1$ si ; on obtient les mêmes formules en remplaçant $\mu(A)$ par : $\text{card}(A)$.

### 8.2 - Utilisation de la distance du $\chi^2$ dans le cas d'un tableau de modalités

Ce sont des tableaux tels que chaque objet est caractérisé par des paramètres pouvant prendre plusieurs valeurs entières. On peut utiliser de tels tableaux quand on n'a que des paramètres qualitatifs ou un mélangé de paramètres qualitatifs et quantitatifs (on découpe en zones et on code).

Nous noterons :

* $k$ le numéro du paramètre

* $t_{ik}$ la modalité réalisée par le paramètre $k$ pour l'objet $i$.

Exemple : $t_{1,2} = 2$ dans le tableau 1

<table><caption>Tableau 1</caption><tr><td>k</td><td>1</td><td>2</td><td>3</td></tr><tr><td>1</td><td>4</td><td>2</td><td>1</td></tr><tr><td>2</td><td>1</td><td>2</td><td>2</td></tr><tr><td>3</td><td>3</td><td>1</td><td>2</td></tr><tr><td>4</td><td>1</td><td>3</td><td>2</td></tr></table>

<table><caption>Tableau 2</caption><thead><tr><th>k</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><th>1</th><td>0</td><td>0</td><td>0</td></tr><tr><th>2</th><td>1</td><td>0</td><td>0</td></tr><tr><th>3</th><td>0</td><td>0</td><td>0</td></tr><tr><th>4</th><td>1</td><td>0</td><td>0</td></tr></tbody></table>

Nous allons donner des formules permettant le calcul de distances entre deux objets, d'un objet à un groupe et de groupe à groupe. Ces formules permettent d'utiliser la MND ou la MNDS sans avoir besoin de mettre en mémoire un tableau du type 2 ; seul le tableau de type 1 donnant les codages suffit. On voit que le gain est considérable dans les cas où le nombre de modalités est important.

Nous noterons également :
$$ - p^k(i,j) = \begin{cases} 1 & \text{si la modalité j du paramètre k est réalisée pour l'objet i.} \\ 0 & \text{sinon} \end{cases} $$

Autrement dit :

- $p^k(i,j)$ - contenu de la colonne j pour le paramètre k pour l'individu i dans le tableau 2.

Exemple :

$$ p^{(2)}(1,2) = 1 \qquad p^{(3)}(3,1) = 0 \text{ dans le tableau 2} $$

$$ - p^k(j) = \sum_i p^k(i,j) \qquad p^k(i) = \sum_j p^k(i,j) = 1 $$

Autrement dit $p^k(j)$ est le nombre de fois où le paramètre k a pris la modalité j.

(Autrement dit $P(t_i, k)$ est le nombre d'individus égal ou différent de i ayant pris la même modalité que i sur le même paramètre).

Exemple :

$$ P(t_2,1) = 2 \qquad (\text{cf. tableau 1}) $$

$$ - \delta_{i,i'}^k = \begin{cases} 1 & \text{si } t_{i,k} \neq t_{i',k} \\ 0 & \text{si } t_{i,k} = t_{i',k} \end{cases} $$

### Proposition 3

Soit $d(i,i')$ la distance du χ² entre i et i' or a :

$$ d(i,i') = \sum_{i} \left( \frac{1}{P(t_{i,k})} + \frac{1}{P(t_{i',k})} \right) \delta_{i,i'}^{k} $$

$$ D(i, I) = \sum_{i \in I} d(i, i) = \sum_{k} \frac{1}{P(t_{i,k})} \sum_{i' \in I} \delta_{i,i'}^{k} + \sum_{k} \sum_{i \in I} \frac{\delta_{i,i}^{k}}{P(t_{i,k})} $$

## IX - CONCLUSION

La MNDS doit permettre dès maintenant le traitement de grands tableaux. Dans un avenir proche, les directions suivantes devraient être fructueuses : a) l'aspect stochastique, notamment pour le cas de tableaux infinis afin par exemple de définir des tests d'arrêt. b) L'aspect apprentissage en faisant intervenir des individus étiquetés durant le déroulement des algorithmes.

c) L'aspect temps réel (par exemple pour la tenue à jour d'une nomenclature). d) La programmation des différentes variantes permettrait peut-être d'améliorer les solutions obtenues par changement d'arbre rescence.

Classifier permet à l'homme de se donner une représentation concise de l'univers (compatible avec un cerveau limité) et de situer tout élément à l'aide de cette représentation. Il est bien évident que l'homme remet en question cette représentation dans sa confrontation continuelle à la réalité objective avec de nouveaux éléments à situer. Philosophes et psychologues nous disont peut-être un jour si h fonction de champ, g fonction de représentation et f fonction de situation ne permettent pas de refléter en machine cette dialectique et ne constituent pas une approche de trois fonctions implicites de la connaissance.

## BIBLIOGRAPHIE

(1) BEALE, 1969, "Euclidean Cluster Analysis" - Bul. I.S.E., 43 book 2 - pp. 92-94 (London).

(2) BENZECRI J.P., 1973, "L'Analyse des Données" - Dunod.

(3) BENZECRI J.P., 1969, "Construction ascendante d'une Classification hiérarchique" - L.S.M. I.S.U.P.

(4) BENZECRI J.P., 1970, "Algorithmes rapides d'agré-gation" - Sup. Class. - L.S.M. I.S.U.P.

(5) BRIANNE J.P., 1972, "L'algorithme d'échange" - Thèse de 3° cycle - L.S.M. I.S.U.P.

(6) CORMACK R.M., 1971, "A Review of Classification" The Journal of the Royal Statistical Society - Série A, vol. 134, Part 3.

(7) DIDAY E., 1971, "Une Nouvelle Méthode en Classification Automatique et Reconnaissance des Formes : La Méthode des Nuées Dynamiques" - Revue de Statistique Appliquée - Vol. 19 - N° 2.

(8) DIDAY E., 1972, "Optimisation en Classification Automatique et Reconnaissance des Formes" - RAIRO - vol. 3 - p. 61 à 96.

(9) DIDAY E., 1973, "Introduction à l'Analyse Facto-rielle Typologique" - Rapport Laboria n° 27 - IRIA - Rocquencourt 78.

(10) FORGEY E.W., 1965, "Cluster Analysis of Multivariate Data" - ARAS Biometrie Society (WNRR) - Riverside - California USA.

(11) GOWER J.C. and ROSS G.J.S., 1969, "Minimum spanning trees and single-linkage cluster analysis" Appl. Stat. 18, 54-64.

(12) JARDINE N. and SIBSON R., 1971, "Mathematical Taxonomy" - J. Wiley and sons ltd.

(13) JAMBU M., 1972, "Techniques de Classification Automatique" - Thèse de 3° cycle - L.S.M. I.S. U.P.

(14) JANCEY R.C., 1966, "Multidimensional group analysis" - Aust. J. Bot. vol. 14 p. 127.

(15) LERMAN I.C., 1970, "Les bases de la Classification Automatique" - Gauthiers Villars.

(16) HALL et BALL, 1967, "A clustering technique for summarizing multivariate data" - Behavioral Science vol. 12 n° 2.

(16) NORTHOUSE R.A., From F.R. 1973, "Some results of Non-parametric clustering on large Data Problems" - Proc. of the First Int. Joint Conf. on Pattern Recognition.

(17) MC QUEEN J., 1967, "Some methods for classification and analysis of multivariable observations" 5th. Berkeley Symposium on Mathematical statistics and Probability - vol. 1 n° 1 pp. 281-297.

(18) ROUX M., 1968, "Un algorithme pour construire une hiérarchie particulière" - Thèse de 3° cycle (L.S.M. I.S.U.P.).

(19) THORNDIKE R.L., 1953, "Who Belongs in the Family?" Psychometrika - vol. 18 pp. 267-276.

(20) ZAHN C.T., 1971, "Graph theoretical methods for detecting and describing gestalt clusters" - I.E.E.E. Trans. and Comp. vol. C 20 n° 1.
MORPHOLOGICAL FEATURES AND SEQUENTIAL INFORMATION

IN REAL TIME

HANDPRINTING RECOGNITION

BERTHOD M., MAROY J.P.

I.R.I.A. - Domaine de Voluceau-Rocquencourt
78150 LE CHESNAY (France)

---

Abstract

In this paper, we discuss the problem of geometric deformations for real time recognition of handprinted charac-
ters and introduce morphological features that deal with it. Then, we show the influence of sequential informa-
tion on the recognition process.

Our syntactical recognition method allows us a true real time recognition, i.e. recognition during the drawing of the character. A hierarchical decision process leaves provision for a non statistical adaptive behaviour which does not need a large set of characters to modify its properties.

For this system, we had to devise a new algorithm for real time approximation of curves which does not need infor-
mation on the whole curve to begin its processing. This algorithm has wide applications in data collection and
data compression.

# I - INTRODUCTION

Graphic tablets are already in use on interactive gra-
phic systems. For a better communication with the com-
puter, some programs have already been written to
recognize characters written on these tablets.

Handwritten input is also used for more common input
operations (surveys for example). We find two great
advantages in using such devices ; they provide direc-
tly lines to represent the characters, instead of a
dot image to be processed ; they also provide the se-
quence of the drawing.

This paper is about the use of the information given
by graphic tablets for handwriting recognition and the
particular importance of the sequence information.

I.1 - Handwriting recognition

The main problem for common handwriting recognition
programs is to cope with the wide range of deformations
possible in drawing. Their approach can be stated as
geometrical : If they use a reference pattern for mat-
ching, they have to allow deformations by a similarity
measure which can be used for clustering. But the gene-
ralization properties of this measure are difficult to
predict. Another proposition is to include the charac-
ter in a frame (1) and to map it into a square or a
rectangle before matching. This technic allows a wide
range of global deformations, like tilted handwriting,
but is still sensitive to local deformations of the
character.

Another approach, illustrated by the work of Bessler
(2) on ambiguity in handprinted characters, consists
in the definition of characteristic properties of the
drawing : closure, length of different segments, etc...
But these two techniques seem still too precise and
other researchers try to avoid the geometrical cons-
traints

Golshan and Hsu (3), for numerals, look for horizontal
and vertical segments in some regions of the characters.

Tou and Gonzales (4) consider 8 regions in a rectangle
enclosing the character and represent it by a vector
stating the presence or absence of some geometric pro-
perties of the character. Other grids are used by
Toussaint and Davidson (5) and Knoll (6).

All these methods try to disconnect geometrical proper-
ties one from another so as to widen the range of de-
formation allowed. This range is still widened by the
matching process of the vector which represents the
state of the grid if a similarity measure is used.
These methods are in fact derived from printed charac-
ters recognition techniques and are difficult to adapt
to handwriting.

Some syntactic methods, like those of Caskey and Coates
(7) or Sayre (8) were used quite efficiently. The pri-
mitives rely more on meaningful positions of the
drawing and their relations.

I.2 - On-line recognition of handwriting

On-line recognition of handwriting works on a different
kind of data.

First, the representation of the character is diffe-
rent : a string of small vectors instead of a digitized
picture. Then, new information can be used : the time
sequence of the drawing, its speed (9), the contact-
strength of the pen on the tablet (10).

The main difference in on-line recognition programs is
that they use the sequence to order the vectors repre-
senting the characters. These vectors are in some cases
the same as in off-line programs i.e. digitized on a
grid. Brown (11) considers 7 regions on a grid and keeps
the transitions from one region to another. Teitelman
(12) uses overlapping regions. The idea in using an ir-
regular grid like Brown's is to allow deformations of
the characters. But there is no good justification for
the division into regions, besides the fact it seems to
work (Fig. 1).

Another method is to keep the vector representation gi-
ven as an input. But then the number of vectors is to
be reduced. Miller (13) replaces the string of vectors
by 6 vectors by dividing the number of points by 6.
Then, the representation used for matching is the vec-
tor of six components given by the successive angles of
the six vectors. This vectorial representation (14)
frees itself from geometric exactitude but misses local
properties of deformation.

I.3 - Presentation of the *new algorithm*

Two main critical remarks can be made on usual on-line
recognition programs. they are not actually real-time programs because they have to wait for the character to be entirely drawn before working on the recognition and give importance to an information which is not very natural : the end of a letter.

We think that a true real time algorithm should be able to work as soon as the information flows into the computer, process it and discard all unnecessary information. Then it may be possible to have a really small hardware machine to implement the algorithm.

Then the techniques presented here dealt in different ways with what we may call global geometric transformations. But how was defined the fact that a deformation was licit or not ? The only way we have to know if a character is an admissible input to the system is to be able to recognize it ourselves.

So, we made three remarks on handwritten characters :

a) Writing corresponds to a complex motor activity of the hand;

b) A character can be described as a composition of elementary forms linked together and which deformations are not always transitive;

c) The time sequence of these elementary forms is quite constant for the same writer.

We try to link the geometric aspect of the characters to the psychomotor activity of the hand (15) by the decomposition of the characters in curve segments that correspond to elementary movements of the hand (16) and to visual entities.

We could have such a description if we told someone to describe verbally a character seen through a screen while it is being drawn. The question would be then : what vocabulary can be used to describe the drawing and relations ?

If we adopt such a definition of morphologic primitives (cusps, straight lines, curves, etc...), link them for instance with topological relations, our description can still be valid for global deformations as well as local deformations when only one of the primitives is badly drawn. If the relations are non metric, this representation will also be indifferent to position on the screen and size. If it is based upon angular differences, it will be also indifferent to orientation.

In our experience with someone describing a character being drawn on the screen, the sequence of primitives would be natural. They would be named and described one after another. Of course, it does not mean the sequence is important. It just means it is very easy to consider it. It could even be harmful to consider it if it varied from one occurrence of the character to another. But as handwriting is a complex motor activity, we can make the hypothesis that the sequence will not vary significantly for the same writer and that if it varies, it is just in function of the immediate context.

We present in this paper a program which tests the importance of the sequence on a very reduced set of morphological primitive curve, the straight line and the pen lift (which can sometimes be replaced by a straight line like in Fig. 2) and propose a new recognition algorithm.

## II - MAIN SUBDIVISIONS OF THE SYSTEM

We shall now describe the existing versions of the recognition system and its further developments. We

will show how it satisfies the constraints we imposed upon it.

### II.1 - Angular Segmentation Algorithm

Characters are hand-printed on a graphic tablet. The frequency of sampling is of 200 Hz. and the precision is 0.18 mm. i.e. points are taken among vertices of a 2024.2024 grid covering a 35 by 35 cm. area. A microswitch on the stylus gives its position : high or low. Thus a character is represented by a sequence of 50 to 500 points that form a broken line approximating the stroke drawn by the stylus. This kind of representation is of better quality than that often used of a binary digitized grid. However it is not perfect.

First, a complex processing of the points is not possible. It would take too much core and too much time. For this reason a next sampling is necessary to reduce the amount of information to be kept and processed (fig. 3).

A sampled point of the stroke is in fact a vertex of the grid mentioned above. The tangent to the stroke at this point and the vector make an angle that can reach $\pi/2$.

Then, the visible result of the drawing is not actually what the writer wanted : local and global deformations may occur. On figure 3 a K is shown that is a curve whereas the writer meant it to be made of three lines. These deformations are caused by sporadic lack of muscular control and by the inertia of the hand which bends straight lines and smoothes angles.

So we have strong reasons for a second sampling in order to eliminate most of the points and to replace the broken line that first represents the stroke, by another one that would fit better the expectations of the writer.

We have to satisfy two conditions. First, we must be able to recognize visually the character after the sampling. One reason for the choice of our features is, precisely, that they would be naturally perceived by the eye. Thus we can say that this sampling will still allow us to extract them. These features are : the straight line segment (written T) the loop (written M if clockwise oriented and P otherwise). The loop is a part of a stroke which has curvature of constant sign. The nabla (written N) is a part of a stroke which is too small to be assimilated to another feature. A last feature is implicit : the penlift (written L) which is given by the microswitch on the stylus.

It clearly appears that the points that are the most useful in finding these features are in the regions of the stroke where the curvature is maximum or switches sign. Attneave (17) has already pointed out that maximum curvature points characterize best the form of a drawing.

The second constraint is to proceed to the sampling on-line, while drawing the character. The only information that can be used to decide of the sampling of a point consists in already sampled points. We never heard of a program for following curves satisfying this condition. All those described in the literature need the whole stroke before sampling its first point. This constraint compells us to find a fast algorithm.

The Angular Segmentation Algorithm satisfies these constraints.

The points are first filtered. The first vector (joining the first two points) is taken as a reference : oriented angles between it and the successive vectors are measured. As long as these angles have their absolute values inferior to a threshold $\epsilon$, the points are
rejected. As soon as an angle is superior to $\epsilon$, the origin of the vector is sampled and the vector itself is taken as a reference instead of the first one. The algorithm then iterates until penlift. The last point is systematically sampled.

The angles are computed using scalar and vectorial products which are fast to compute. This prevents us from losing following points, for, while computing, eventual arrivals of points are inhibited. Information needed to sample points merely consists in the already sampled points.

Examples given in figure 3 and other experiences show that sampled points belong to the regions where curvature is maximum (in absolute value) or switches sign. Thus they will allow feature extraction. In annex I demonstration is given of a criterion which links the parameters of Angular Segmentation to classical approximation of curves. Let L be the length of the vector joining two successive points, let D be the greatest distance from the stroke between these two points to the vector, let S be the surface between the stroke and the vector (figure 4), then :

$$S < 1/4 L^2 \text{tg } 1$$ $$D < 1/2 L \text{tg}$$

Examples given in figure 3 show that the actual approximation is much better for handprinted characters. This is caused by particular properties of continuity of hand drawn curves. With a threshold 1 equal to about 30°, a character is sampled by 2 to 15 points.

A practical and theoretical study of online following curves algorithms of this kind is under way. It will compare existent approximation algorithms and the Angular Segmentation Algorithm and a Curvature Segmentation Algorithm of the same kind.

## II.2 - Feature Extraction

As soon as a point is sampled, control is given to a procedure of extraction. The angle between the vector arriving at this point and its predecessor is computed (except for the first vector, of course). This angle is quantified almost in the same way as Freeman's (18) as shown in figure 5.

As soon as an angle is computed, control is given to an automata which eventually writes the feature detected. A sequence of zero angles gives a T (straight line segment), a 4 angle necessarily parts two features (cusp), a sequence of quantified angles with constant sign and different from 4 is a loop of the same sign (fig. 6).

A few remarks on the automata are necessary. The angle between two successive vectors may be 0°. So, the automata has to reject 0° angles. In fact, it works as if the algorithm was applied twice: points that were first sampled become entries for the second iteration.

A loop is defined by a sequence of angles of constant sign. It does not fit with the usual concept of a loop. A straight segment can be incorporated within a loop. The loop can also be a spiral. This does not matter as far as we limit ourselves to hand printed characters.

## II.3 - The Recognition Algorithm

Let us now describe the complete algorithm. It consists of several levels. Each time a level is active it operates, eventually gives control to an upper level and then waits till it recovers control. When it has finished, control is given back to the lower level. This is the usual structure of an on line algorithm. This im-

plies that points that would arrive while processing are lost. Our processing is fast enough to be sure that we don't lose any point in actual experiments.

The first level is the Angle Extraction which associates quantified angles to the remaining vectors. The third level is the Feature Extraction. It consists of the automata described in annex 2. The end of a character gives control to the fourth level which is the Recognizer itself.

The entry to this fourth level is the string of characters representing the sequence of primitive features (noted L,M,P,N,T). This string is searched into a dictionary. If it is found the corresponding character is displayed on a graphic display. There may be several characters to display because of possible ambiguities. If there is only one character the writer may accept it or reject it. If there are several of them, he has to choose the one he wants.

If the string is not found in the dictionary, then the writer must name it. Then the string is inserted in the dictionary with its name. The next time the string is found it will be recognized. Table 1 gives a quite complete dictionary for upper case latin letters and arabic numerals.

As we can see, such a simple device already separates most of the characters: each of the 32 codes represents from one to five characters. Table 2 proves the importance of the sequence. If the sequence is not used and if penlifts, which are linked to the sequence, are replaced by straight lines, there are only 18 different codes, each one representing from one to eleven characters.

However this system, as described, does not recognize all characters. We need some more information to cope with ambiguities. This information must concern some visible characteristic of the stroke. We get them from special procedures. Examples of such procedures are given in table 3: starting angle, enclosure, ending angles, mappings and topological relationships between features.

We wrote as an example a recognition program that uses the sequence and starting angles procedures. After each penlift the quantified slope of the tangent to the beginning of the next stroke is inserted into the string of features instead of the L (penlift) primitive.

The dictionary built with the corresponding codes is given in Table 4. There are very few ambiguities left and a few procedures can solve them. For instance, length and orientation of the geometric sum (given by Enclosure procedure) will separate 0 from 6 and from C.

Yet a disadvantage appears. The greater sharpness of the representation creates a redundancy of codes for a few characters. First: because some angles are near a limit of quantification, a very small rotation of the character changes the value of the quantified angle. The character A is a good example for it. Then the tangent at the beginning of the stroke may vary a lot without the eye noticing it, as is shown for the C (figure 7).

We think however that the angle is a morphological feature. It characterizes the linking movement of the hand between strokes and the variations of the strength of the stylus on the paper. The quite random variation of the angle comes from the sudden transition between the only two positions of the pen that our system can record: up and down.

## II.4 - The General Algorithm

In order to cope with ambiguities, without redundancy of code, we build a more general algorithm, the discriminating power of which varies according to the ambi-
guilties to be solved, and we gave it learning abilities.

The first levels are these of the previous algorithm,
but the dictionary is now a tree, like the one proposed
by Longet-Higgins (19). A path is made of the successive
features encoding a character. The last node contains
the name of the character. In case of ambiguities, the
writer may use procedures as those described in tall
3: these procedures and their outputs are stored at
the tall of the path, and will be automatically used
the next time the path is followed.

In fact, it is not necessary to wait until the end of
the character to apply all the procedures needed. At
any instant of the drawing, i.e. at each node N of the
path, one can define a set of procedure $B_n$, that can
be processed at this point of the drawing and could not
before, and two subsets of $B_n$ :

$B_{n1}$: procedures that will be used at least by one terminal issued from N.

$B_{n2}$: procedures that will be used by all the terminals issued from N;

Let us now represent each feature and each output from
a procedure by a node, and let us group the terminals
corresponding to the same character. The algorithm may
be sketched by a folded tree. Then, for each node N,
we can define $B_{na}$, a set of procedures to be applied

$(B_1 \subset B_n \subset B_n)$ and it must be choosen so that the path will be of minimum length. More precisely, the path must contain the minimal number of nodes that contain morphological features. This implies that the procedures used fit best the drawing and mostly that recognition will be performed as soon as possible, because our features are linked to the drawing sequence.

Let us consider now the problem of segmentation bet-
ween characters. We suppose that the writer no longer
signals the end of the character. We can use the fol-
ded tree mentioned above. The nodes containing the end
of character signal are suppressed and the terminals
containing the associated names of characters are fol-
ded upon the previous nodes.

A sequence of nodes of this folded tree may indeed be
considered as the rewriting of the sequence of the cha-
racters drawn by the writer. Thus the algorithm will
behave like an automata parsing a LL(K) language and
choosing, besides, the procedures to be used (K is
about 4 or 5). We see here the use of the tree struc-
ture of the dictionary, even if it is limited to fea-
tures, for they strictly follow the time sequence of
drawing.

We foresee an other promising extension. As each of
these procedures just supposes the knowledge of the
sampled points, they can work simultaneously, even with
feature extraction. One might conceive a decision de-
vice that would accept as entries all the simultaneous
strings of characters given by these procedures. Thus
the problem lays in the determination of a set of pro-
cedures, the longest of which is still fast, then in
the building of a decision device that work in real-
time and chose at any instant the fastest procedures.
Another mean is for the decision device to wait for
every output of procedure, and to parse it as soon as
it arrives.

### III - CONCLUSION

We presented here a few simple programs that achieve
on-line handwritten characters recognition.

Because of their structures we can hope for more gene-
rality and more realistic learning abilities than what

was done until now.

### ACKNOWLEDGEMENTS

We wish to recognize the constant help and advice of
Professor J.C. SIMON. We would like to thank also the
Metavisu team, for introducing us to their new interac-
tive graphic system.

### BIBLIOGRAPHY

1. TUONG N.
   L'emploi des projections coniques dans la reconnaissance des formes
   Dpt Informatique - Université de Montréal - Mars 69

2. BLESSER B., SHILLMAN R., COX C., KURLINSKI T., VENTURA U., EDEN M
   Characters Recognition Based on Phenomenological attributes - Visible Language VII,3 - Summer 1973

3. GOLSHAN N., HSU C.C.
   A recognition algorithm for handprinted arabic numerals - I.E.E.E. Trans. on SSC. - July 1970

4. TOU J.T., GONZALEZ R.C.
   Automatic Recognition of Handwritten Characters
   via Features Extraction and Multi-level Decision
   I J C IS - vol. 1 - 1972

5. TOUSSAINT G.T., DONALDSON R.N.
   Algorithm for Recognizing Countour-traced hand-printed Characters - I.E.E.E. rans. on C. - June 1970

6. KNOLL A.L.
   Experiments with "Characteristic Loci" for Recognition of Handprinted Characters - I.E.E.E. Trans. on C. - April 1969

7. CASREY R.L., COATES C.L.
   Machine Recognition of Handprinted Characters -
   Hawaii Congress - 1973 - p. 150-153

8. SAYRE K.M.
   Machine Recognition of Handwritten Words - A project Report (Pattern Recognition 1973) vol. 5 - p. 213-228

9. MERMELSTEIN P., EDEN M.
   A System for Automatic Recognition of Handwritten Words - AFIPS 1964

10. NEGROPONTE N.
    Recent Advances in Sketch Recognition - Nat. Comp. Conf. - 1973

11. BROWN R.M.
   On-line Computer Recognition of Handprinted Characters - F J C C 1964

12. TEITELMAN W.
   Real-time Recognition of Hand-drawn Characters -
   F J C C 1964

13. MILLER G.M.
   On-line Recognition of Hand-Generated Symbols -
   F J CC 1969

14. POWERS V.M.
   Pen Direction Sequences in Character Recognition
   Pattern Recognition - December 1973

15. VREDENBREGT J., KOSTER W.G.
   Analyse et Synthese de l'Ecriture - Philips Technical Review - vol. 32 - 1971

16. SIMON J.C.
   Compte Rendu de Visite en URSS - Octobre 1973

17. ATTNEAVE, ARNOULD
   Some Informational Aspects of Visual Perception
   Psych. Review - n° 61 - p. 183-193 - 1954

18. FREEMAN H., GLASS J.M.
   On the Quantization of line-drawing data - I.F.E.E
19 - LONGUET-HIGGINS H.C., ORTONY A.
The Adaptive Memorization of Sequences
Machine Intelligence 3 - Edinburgh - University
Press.

20 - GAILLAT
An On-line character recognizer with learning capabilities
Second IJCPR - Copenhagen - August 1974.

<figure><img src="image_6.png" /><figcaption>FIGURE 1 Generalisation properties - Brown's grid</figcaption></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>FIGURE 2 Straight-lines replacing penlines.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>FIGURE 3. On the left, points before sampling are shown
On the right, only sampled points are shown</figcaption></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /><figcaption>FIGURE 4. CURVE APPROXIMATION</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>FIGURE 5. CURVE APPROXIMATION: LOOPS</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>FIGURE 6. CURVE APPROXIMATION: LINES</figcaption></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /><figcaption>FIGURE 7. STARTING ANGLES</figcaption></figure>

- Table 1 -

Discrimination by morphological features and sequence underlined are the confusions which would be solved by considering the starting angles within brackets (see also table 4)

<table><tr><td>1</td><td>M</td><td>J(-2)</td></tr><tr><td>2</td><td>MLT</td><td>J(-2,0)</td></tr><tr><td>3</td><td>MM</td><td>A(-3,0), A(3,1)</td></tr><tr><td>4</td><td>MM</td><td>7(0)</td></tr><tr><td>5</td><td>MP</td><td>2(1)</td></tr><tr><td>6</td><td>NPM</td><td>B(-1), B(0), B(1)</td></tr><tr><td>7</td><td>MT</td><td>2(0), 2(1), 2(2)</td></tr><tr><td>8</td><td>P</td><td>6C(-3), U(-2), C(3), C(4)</td></tr><tr><td>9</td><td>PLM</td><td>9(-3,-2)</td></tr><tr><td>10</td><td>PLT</td><td>Q(-3,-1), Q(-2,-1), Q(-3,-1), B(-4,-1), C(4,0)</td></tr><tr><td>11</td><td>PM</td><td>9(-3), S(3), S(4)</td></tr><tr><td>12</td><td>PN</td><td>C(-3)</td></tr><tr><td>13</td><td>TLH</td><td>DP(-2,-1), DP(-2,0)</td></tr><tr><td>14</td><td>TLMM</td><td>B(-2,-1), B(-2,0)</td></tr><tr><td>15</td><td>TLMT</td><td>R(-2,0)</td></tr><tr><td>16</td><td>TLMTT</td><td>B(-2,0)</td></tr><tr><td>17</td><td>TLT</td><td>T(-2,0), XY(-1,-3), X(0,-2), I(1,-2)</td></tr><tr><td>18</td><td>TLTLT</td><td>A(-3,-2,0), A(-3,-1,0), A(-2,-2,0), A(-2,-1,0), M(-2,0,-2)</td></tr><tr><td>19</td><td>TLTLLT</td><td>F(-2,0,0), F(-2,1,-1)</td></tr><tr><td>20</td><td>TLTT</td><td>N(-2,-1)</td></tr><tr><td>21</td><td>TLTTT</td><td>H(-2,-1)</td></tr><tr><td>22</td><td>TLMT</td><td>S(-2,0), R(-2,-1)</td></tr><tr><td>23</td><td>THM</td><td>RB(-2)</td></tr><tr><td>24</td><td>TPM</td><td>B(-2)</td></tr><tr><td>25</td><td>TPT</td><td>B(0)</td></tr><tr><td>26</td><td>TT</td><td>LV(-2), W(-1), W(0), I(1)</td></tr><tr><td>27</td><td>TTLT</td><td>4(-3,-2), 4(-2,-2), 7(0,0), I(1,0), A(2,0), P(4,0)</td></tr><tr><td>28</td><td>TTLTLT</td><td>E(-2,0,0)</td></tr><tr><td>29</td><td>TTM</td><td>3(0)</td></tr><tr><td>30</td><td>TTN</td><td>7(0), I(1)</td></tr><tr><td>31</td><td>TTT</td><td>2(0), N(2)</td></tr><tr><td>32</td><td>TTTT</td><td>W(-2), W(-1)</td></tr></table>