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

HAL
open science

# An experiment in characters separation

Marc Berthod

► To cite this version:

Marc Berthod. An experiment in characters separation. [Research Report] IRIA-RR-179, IRIA. 1976, pp.22. hal-04716361

HAL Id: hal-04716361

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

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
IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

ARCHIVES
laboratoire de recherche
en informatique
et automatique

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

AN EXPERIMENT
IN CHARACTERS SEPARATION

Marc BERTHOD

Rapport de Recherche N° 179

Juillet 1976
AS EXPERIMENT IN CHARACTERS SEPARATION

Marc Berthod

IRIA/LABORIA

Résumé :

La recherche de critères qui permettent de distinguer deux caractères manuscrits est esquissée ici
dans un cas particulier.

Ces critères ou « attributs morphologiques », doivent servir de base à un système de reconnaissance
des caractères manuscrits, approchant les performances de l'œil humain.

Abstract :

The research of criterions to distinguish two manuscript characters is faced here, for a particu-
lar couple.

These criterions, so-called «morphological attributes», will be the base of a handwritten charac-
ters recognizer, the capabilities of which should approach these of human eye.
AS EXPERIMENT IN CHARACTERS SEPARATION

∴
∴
∴

INTRODUCTION

Automatic character recognition used to be and is still a very
important research field. Most of the teams working in pattern recognition
happened to get involved in that problem.

One can find two reasons to that infatuation.

First, practical applications of a good character-reader are
numerous. Written text, manuscript as well as printed, is the most widely
used support, for communication and storage of information. For practically
all of its form : zipcodes, books, punching sheet, there could be an interes-
ting application of automatic character recognition.

Second, it is a fascinating problem : as much for its difficulty,
that for the diversity of the methods that can be used to solve it. All
classical methods and techniques of pattern recognition were tested on character
recognition : masks, statistical techniques, so-called syntactic methods,
and so on.

As a matter of fact, there are many subproblems, according as
characters are printed or manuscript, single or multi-font, centered or not,
and, if they are manuscript, according as they are centered or not, normalized
or not.
Satisfying solutions were found in a few cases : some optical readers recognize very well single-font and even multi-font characters ; others recognize normalized hand-printed numerals, and even normalized hand-printed letters.

Another subproblem is the on-line recognition of hand-printed characters (1,2): time information is then very useful, and very distorted characters may be recognized. Other works try to recognize hand-printed characters from their image (3,4), but one can say that the general problem of automatic recognition of all separate characters that the eye can recognize is not solved. With regard to cursive writing, its recognition is hardly foreseen, and it seems to rely on the development of natural language understanding, and the use of context.

So the actual problem can be stated as follows : recognize hand-printed characters or multi-font characters, with the same accuracy as human eye.

B. Blesser, T. Kuhlinski, R. Shillman et al, working in the Cognitive Information Process Group (C.I.P.G.) of Professor Murray Eden are trying to solve this problem (5).

## I. - C.I.P.G approach : phenomenological attributes

The purpose of the team is the long-dated recognition of unsconstrained hand-printed characters, the error-rate being approximately that of a human being reading in the same conditions.

The analysis of already existing systems leads to the hypothesis that the main reason of their important error rates is the lack of a precise definition of the objects to be recognized. Besides, here is the great difference with the recognition of single-font characters.

Thus, the first stage of the project is to precisely define handprinted characters, i.e. to find the exact criterion that man use to recognize such characters.
That is not different from usual syntactic, or feature
extraction methods. What is original in this approach is the way these
criterions are extracted.

As many distortions may happen in a handprinted character,
the really important features of a character are those that allow it to be
distinguished from the others. To put it another way : classical syntactic
approach leads to find an "ideal" definition of an "ideal" character, and
then tolerate variations about this definition.

Here, on the contrary, the exact definition is not considered
important, only "phenomenological attributes", i.e. : parts of that definition
that are necessary to separate the character from any other, are essential.

Before building an efficient character recognizer, one must
find, for any pair of characters, the criterion which is different between
them. That leads to 26 x 26 = 676 possible criterions. Fortunately, most of
these criterions seem to be similar, as it has been shown on already studied
pairs ( 6 ) : one can hope that a new definition of characters in terms of
phenomenological attributes can be found.

It could be used in the same way as "classical" ones, but it is
someway minimal.
Let us take an example (Fig. 1).

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

The threshold, with regard to 1/L, which allows separation between
F et C is the same that the threshold between V and Y. So there is a "tail"
attribute, present in F and Y, absent in C and V.
Moreover, the way to find if this attribute is present is shown too. One knows now :

- the functional attribute "tail"

- the rule to go from the physical attribute "tail", to the functional attribute "tail".

In many cases, functional attributes are already known by intuition : what is important to found is the rule leading from physical to functional attribute.

## II. - CONNECTION WITH THE LABORIA CHARACTER RECOGNITION PROGRAM

Analogies can be found with the program written at IRIA in 1974-1975 to recognize handprinted characters from a graphic tablet (1).

As a matter of fact, this program extracts, from the written character, a few features called "primitives", and topological relations between these primitives. For instance, a "V" is described as two successive bars, making between them a positive angle. In this description, only one primitive: the bar, and one relation : the angle, are used.

A very limited number of such primitives and relations are needed to describe the set of commonly handprinted characters, and even, more generally, frequently used symbols, like Σ + - x .

The primitives are :

- bar

- curves (clockwise and counterclockwise)

- cusp

- penlift.

The topological relations between these primitives are :

- angle

- position of a characteristic point, according to another primitive.
In a "T", for instance, the beginning (first point) of the first bar is approximately in the middle of the second bar.

Thus, a character is represented by, at least, the sequence of its primitives. Moreover, this representation includes the minimal set of topological relations between these primitives, needed to separate it from any other character or symbol.

Let us take another example : "B" and "R" may be represented by the sequence B L N C N, where B stands for "bar", L for "penlift", N for "clockwise" (negative) curve, C for "cusp".

But the distance from the last point of the curve to the stroke is different whether it is a "B" or an "R". Practically this distance is quantified on very few levels, and the answer "B" or "R" may be taken as the output of a logical predicate.

The learning mechanism itself insures that the number of relations between the primitive will be minimal : at the beginning, a character is represented by the sequence of the primitives that compose it. If this character happened to be recognized in place of another, then a learning stage is initiated, which provides a unique measure, the value of which is different between the sample-sets of the two characters. Each of these two characters is now represented by the sequence of its primitives, and by this measure and its value. The next time the sequence of primitives will be encountered, this measure will be applied, and the value found will precisely determine the character. The same algorithm may be applied to this character if a new ambiguity appears.

We can see now where are the links with the MIT project. First, the primitives and relations used were found after careful examination, by two persons, of the way they wrote characters. It would be worthwhile to replace them by those found at M.I.T; that should be possible, for the two descriptions try to be minimal.
One could view that adaptation in two ways :

1°/ Improving the primitive extraction algorithm :

For example, the U and V (supposed to be symmetric) can be separated by a relation linking the slope at the beginning of the stroke to the curvature in the down part of the stroke. Such a criterion could be precious to refine the definition of a cusp.

2°/ Getting rid of learning

Automatic learning was first introduced because one could hardly foresee all the possible shapes of a handprinted character, particularly with several scriptors, which would be necessary in order to choose the relations that distinguish them.

M.I.T. project is aiming at finding such relations : if it succeeds, provided relations should even be better than those provided by learning.

III. - AN EXAMPLE : THE O-Q SEPARATION

The separation between O and Q which I studied during my visit at MIT shows that this problem is different from other pairs separations like U and V and that most of the pairs induce specific separation criterions.
### 3.1. Methodology of the experiment

Each experiment copes with the separation of two characters,
i.e : the way people recognize one of these two characters from the other.

A few tens of "stimuli", i.e samples of the two characters, are
presented to "subjects". We describe here the procedures used, upon psycho-
logists suggestion.

#### 3.1.1. Labelling : the subjects label the stimuli.

There are two variants :

- two ways labelling: the subjects label the stimuli as one of
  the two possible characters (here = 0,Q)

- three ways labelling: they may also not label it (here 0, Q, nothing)
  if the stimulus does not look like any of the two characters.

#### 3.1.2. Goodness : the subjects rate the stimuli, from 0 through 5, as representing one of the two characters.

A 0 means that the stimulus does not represent the corresponding character.

A 5 means that it perfectly represents this character. There are thus two
possible rates for a given stimulus : its goodness as the first character (0)
its goodness as the second (Q).

These procedures may be, and in fact were, used simultaneously in
the same experiment.

Let us quote that only subjects whose English was the first
language were admitted ; for the drawing of some characters can vary with
languages and countries.
### 3.2. Characteristics of the stimuli

Precise measures of the geometric properties of the proposed stimuli must be possible; for that reason, they are not hand drawn but analytically designed. They are made of portions of known curves (lines, circles...), the parameters of which define the character. They are sort of "ideal" or "perfect" characters.

In the O,Q case, the character is a perfect circle drawn with compasses, with a line drawn with a rule for the Q.

The thickness of the stroke is constant (about 1 mm). Each stimulus is presented on a card (about 3 x 5 inches) without any spot.

### 3.3. Choice of the stimuli

With the above definition of O and Q, the only interesting variations regard Q: more precisely, the radius of the circle is constant (half an inch), and the Q is defined by the four parameters which define the line segment of the Q.

A Q is thus a point in a four-dimensional space, and there is no way to clearly represent it. Moreover if we want to study, with some precision, the different combinations of these parameters, we are led to a rather big number of stimuli: for 10 possible values of each parameter, there should be $4^{10}$ stimuli.

To cope with this constraint, we fix parameters in turn.

The line segment of the Q is defined by the following parameters:

$\alpha$: angle with the horizontal

$\theta$: curvilinear abscissa of the intersection point with the circle

$l_i$: length inside the circle (percentage of the radius)

$l_o$: length outside the circle (percentage of the radius)
What is probably most important for the distinction between
O and Q is the presence of a line segment, more than its orientation.

So we begin in setting α and θ to π/4, corresponding to an
ideal Q, and we let lᵢ and l₀ vary, trying to find some simple relation
R (lᵢ, l₀), which would easily generalize when α and θ vary.

This was the standard method successfully used for other couples
of characters (X, Y, ...)

D/ First experiment

69 stimuli were presented to 18 subjects, who had to :

- label each stimuli as C, Q or nothing

- rate it first as an O then as a Q.

The 69 stimuli covered a large variety of Q (or O), with 0 < lᵢ < 200
0 < l₀ < 30

( α = θ = π/4, and lᵢ and l₀ are expressed in percentage of the radius of the circle).

Fig. 2 shows the"labelling" result of the experiment. Each stimulus is a pair of coordinates (lᵢ, l₀) ; in the corresponding square are given the percentage of subjects who label it as an O (Lo) (lower number) and as a Q (Lq) (upper number).

Fig. 3 shows the goodness result : in each square of coordinates (lᵢ, l₀), the means of the ratings as an O(G) (lower number) and ratings as a Q(G) (upper number) are given.

This first experiment gives us useful information about the region
where O et Q get confused. We are now able to chose the values of the parameters
for the stimuli in the second experiment.
Fig. 2 and 3 show that :

- if $1_i > 50$, $G_o < 0,6$

$L_o < 44\%$

- if $1_o > 40$, $G_o < 1,3$

$L_o < 17\%$

That is: in these regions, $O$ is "badly" recognized and the ambiguity with a $Q$ is not very apparent. For that reason, we focus on $O$ and $Q$, with $0 < 1_i < 30$ and $0 < 1_o < 30$.

## E/ Second experiment

The second experiment was run with 18 subjects. To every subject 49 stimuli were shown ($0 \le 1_i \le 30$, $0 \le 1_o \le 30$, with a step of 5), to be

- labelled as $O$ or $Q$

- rated as an $O$ and as a $Q$.

The three possibilities : $O$, $Q$, nothing, were offered, in the first experiment, in order to eliminate those regions where labelling was neither $O$ nor $Q$. There is no such reason in the second experiment.

The results of this experiment are displayed on Fig. 5 - 9. Fig 4, gives the correspondance between the number of a stimulus and the values of its parameters.

The results of the labelling are shown on Fig. 5, but a clearer representation is given in Fig. 8, using the labelling curves. The most interesting of these curves is the 50-one, which gives the border between
0 and Q, i.e. the stimuli along this line are the most ambiguous ones.

The aim of the study is to determine that border ; further
studies are necessary to precisely found which simple relation,
if any, between lᵢ and l₀ this curve approximates : may be some hyperbola.

The other part of the experiment : goodness (as an O and as a Q)
is displayed in Fig. 6 - 7. But a better representation is given in
Fig. 9 and 9 bis, using both labelling and goodness results.

In each figure, the percentage of labelling as an O along the
chosen trajectory is referred on the x-axis, which the mean ratings as
an O, and as a Q, are referred on the y-axis.

A trajectory is a straight line in the(lᵢ, l₀) plane, and is
referred by the name of its initial and its terminal stimuli.

The different trajectories that are displayed show the coherence
between goodness and labelling at least in the range of 50% < P (0) < 100 ;
i.e. in the "0" region.

IV. - INTERPRETATION AND CONCLUSION

Thus the above experiments give an idea of a possible rule
for separating O's from Q's. But the apparent simplicity of the curve
obtained, as well as the coherence between the two parts of the experiment
must not make illusion.
The transitions between O and Q are caused by very slight
changes in the values of the parameters, i.e. a very little bar is
enough to distinguish an O from a Q.

An explanation of this fact is that, as this bar, in a "perfect"
character cannot be an accident, so it proves that the character is a Q,
as small as it may be.

The problem is that real characters are noisy, and spots
or other kind of noise of the same magnitude of the "border" bar are
likely.

Another very curious phenomenon is the following :

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

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

If the Q has a very big bar, then it is hardly recognized
as a Q, as long as it is perfectly drawn. But it is very well recognized
as long as it is hand-drawn, even carefully.

So it is likely that the border between O and Q is shifted
towards greater $1_i$ and $1_o$ for manuscript characters, and maybe for real
typed characters.

For these reasons, I think that further experiment partly
dealing with real, noisy or hand-written characters is necessary.
<caption>Figure 2</caption>

The upper number is the percentage of Q labelling.
The lower number is the percentage of O labelling.

<table><thead><tr><th></th><th>44</th><th>94</th><th>94</th><th>94</th><th>100</th><th>100</th><th>61</th><th>33</th><th>17</th></tr></thead><tbody><tr><th>6</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>33</th><td>89</td><td>94</td><td>100</td><td>100</td><td>100</td><td>100</td><td>61</td><td>33</td><td>17</td></tr><tr><th>22</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>56</th><td>94</td><td>100</td><td>100</td><td>100</td><td>100</td><td>100</td><td>61</td><td>17</td><td>11</td></tr><tr><th>17</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>6</td><td>0</td></tr><tr><th>61</th><td>89</td><td>94</td><td>100</td><td>100</td><td>94</td><td>94</td><td>67</td><td>28</td><td>11</td></tr><tr><th>28</th><td>11</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>22</th><td>89</td><td>89</td><td>94</td><td>94</td><td>94</td><td>94</td><td>67</td><td>28</td><td>6</td></tr><tr><th>50</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>0</th><td>28</td><td>61</td><td>56</td><td>72</td><td>67</td><td>67</td><td>22</td><td>6</td><td>6</td></tr><tr><th>78</th><td>50</td><td>22</td><td>17</td><td>0</td><td>6</td><td>6</td><td>6</td><td>6</td><td>0</td></tr><tr><th>0</th><td>0</td><td>0</td><td>0</td><td>6</td><td>6</td><td>6</td><td>6</td><td>0</td><td>0</td></tr><tr><th>100</th><td>72</td><td>72</td><td>64</td><td>44</td><td>11</td><td>11</td><td>11</td><td>6</td><td>17</td></tr></tbody></table>
<caption>Figure 3</caption>

The upper number is the mean goodness as a Q.
The lower number is the mean goodness as an O.

<table><thead><tr><th></th><th>2</th><th>2,9</th><th>3,5</th><th>3,7</th><th>4,5</th><th>4,4</th><th>3,1</th></tr></thead><tbody><tr><td></td><td>0,8</td><td>0,5</td><td>0,4</td><td>0,4</td><td>0,1</td><td>0,2</td><td>0,2</td></tr><tr><td></td><td>2,2</td><td>3,4</td><td>3,9</td><td>4,1</td><td>4,4</td><td>4,5</td><td>3,0</td></tr><tr><td></td><td>1</td><td>0,6</td><td>0,7</td><td>0,4</td><td>0,3</td><td>0,2</td><td>0,9</td></tr><tr><td></td><td>2,2</td><td>3,2</td><td>3,9</td><td>4,3</td><td>4,5</td><td>4,5</td><td>3,2</td></tr><tr><td></td><td>1,3</td><td>0,5</td><td>0,6</td><td>0,3</td><td>0,1</td><td>0,2</td><td>0,3</td></tr><tr><td></td><td>2,2</td><td>2,7</td><td>3,6</td><td>4,3</td><td>4,2</td><td>3,9</td><td>3,5</td></tr><tr><td></td><td>1,6</td><td>1,1</td><td>0,7</td><td>0,6</td><td>0,3</td><td>0,3</td><td>0,1</td></tr><tr><td></td><td>1,6</td><td>3</td><td>3,7</td><td>4,0</td><td>3,8</td><td>3,2</td><td>3,4</td></tr><tr><td></td><td>2,5</td><td>1,5</td><td>0,8</td><td>0,8</td><td>0,6</td><td>0,6</td><td>0,4</td></tr><tr><td></td><td>0</td><td>2,2</td><td>2,8</td><td>2,4</td><td>2,5</td><td>2,3</td><td>1,2</td></tr><tr><td></td><td>3,5</td><td>2,1</td><td>1,4</td><td>1,4</td><td>0,8</td><td>0,5</td><td>0,5</td></tr><tr><td></td><td>0</td><td>0,4</td><td>0,9</td><td>1,0</td><td>1,1</td><td>1,2</td><td>0,6</td></tr><tr><td></td><td>5</td><td>3,5</td><td>2,1</td><td>1,9</td><td>1,6</td><td>0,6</td><td>0,6</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,6</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,5</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>0,2</td></tr></tbody></table>
<figure><img src="image_7.png" /><figcaption>Figure 4</figcaption></figure>

Stimuli identification.

<figure><img src="image_8.png" /><figcaption>Figure 5</figcaption></figure>

Percentage of labelling as an 0.
<table><caption>Figure 6</caption><thead><tr><th>1<sub>o</sub></th><th>0,5</th><th>0,5</th><th>0,2</th><th>0,0</th><th>0,0</th><th>0,0</th><th>0,0</th></tr></thead><tbody><tr><th>30</th><td>0,6</td><td>0,2</td><td>0,2</td><td>0,0</td><td>0,0</td><td>0,0</td><td>0,1</td></tr><tr><th>25</th><td>0,7</td><td>0,8</td><td>0,1</td><td>0,2</td><td>0,0</td><td>0,1</td><td>0,1</td></tr><tr><th>20</th><td>1,5</td><td>1,0</td><td>0,6</td><td>0,6</td><td>0,3</td><td>0,2</td><td>0,2</td></tr><tr><th>15</th><td>2,6</td><td>1,6</td><td>1,2</td><td>1,0</td><td>0,8</td><td>0,5</td><td>0,4</td></tr><tr><th>10</th><td>3,7</td><td>2,2</td><td>1,9</td><td>1,7</td><td>1,2</td><td>1,2</td><td>1,0</td></tr><tr><th>5</th><td>4,8</td><td>4,0</td><td>2,7</td><td>2,4</td><td>2,2</td><td>1,7</td><td>1,3</td></tr><tr><th>0</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

Goodness as an O.

<table><caption>Figure 7</caption><thead><tr><th>1<sub>o</sub></th><th>3,1</th><th>4,0</th><th>4,0</th><th>4,4</th><th>4,4</th><th>4,5</th><th>4,6</th></tr></thead><tbody><tr><th>30</th><td>2,8</td><td>3,2</td><td>3,8</td><td>4,3</td><td>4,3</td><td>4,6</td><td>4,5</td></tr><tr><th>25</th><td>2,6</td><td>2,7</td><td>3,6</td><td>4,1</td><td>4,0</td><td>4,4</td><td>4,3</td></tr><tr><th>20</th><td>1,7</td><td>2,7</td><td>3,1</td><td>3,4</td><td>3,6</td><td>3,6</td><td>3,7</td></tr><tr><th>15</th><td>1,1</td><td>2,0</td><td>2,2</td><td>2,7</td><td>2,7</td><td>2,6</td><td>2,3</td></tr><tr><th>10</th><td>0,3</td><td>1,4</td><td>1,7</td><td>1,6</td><td>1,8</td><td>2,0</td><td>2,0</td></tr><tr><th>5</th><td>0,0</td><td>0,5</td><td>0,7</td><td>0,8</td><td>1,1</td><td>1,5</td><td>1,4</td></tr><tr><th>0</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

Goodness as a Q.
<figure><img src="image_9.png" /><figcaption>Figure 8</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 9
Goodness</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Figure 9 bis</figcaption></figure>
BIBLIOGRAPHY

[1] BERTHOD M. - Une méthode syntaxique de reconnaissance des caractères manuscrits en temps réel avec un apprentissage continu. Thèse de 3ème cycle - Université de Paris VI - Mai 1975.

[2] GAILLAT C. - Une procédure statistique de décision aux apprentissage et son application à la reconnaissance des caractères manuscrits. Thèse de 3ème cycle - Université de Paris VI - Mai 1975.

[3] TOU J.T., GONZALEZ R.C. - Recognition of handwritten characters by topological feature extraction and multilevel categorization. IEEE Trans. on Comp. - July 1972.

[4] CASKEY D.L., COATES C.L. - Machine recognition of handprinted characters. IJCPRI, Nov. 1973, pp 41-49.

[5] BLESSER B., SHILLMAN R., KUBLINSKI T., CHEN C., EDEN M., VENTURA J., A theoretical approach for character recognition based on phenomenological attributes. IJCPRI, Nov. 1973, pp 33-40.

[6] SHILLMAN R. - Character recognition based on phenomenological attributes: Theory and Methods. Aug. 1974, PHD Thesis, MIT Cambridge (Mass).