Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
1~66805
La présente invention concerne les nnachines à recon-
naissance des formes qui sont utilisées notamment pour la lecture
automatigue de textes imprimés ou dactylographiés~
Plus précisément, elle concerne les machines à recon-
naissance des formes dans lesguelles la lecture des ~ormes est
effectuée de telle manière ~ue l'on dispose pour cha~ue ~orme
d'un ensemble de nombres binaires dont chacun correspond à la
. présence ou l'absence d'un élément de la forme dans une surface
élémentaire ou zone déterminéeO
Dans ces machines, le disposit-i~ d'ac~uisition ou
lecture fournit pour chague caractère ou graphisme traité un
certain nombre de données binaires dont l'ensemble correspond
au graphisme considéré. Ce nombre, ~ui dépend de la finesse de
définition du graphisme, est relativement élevé, 256 par exempleO
Que l'acquisition du graphisme sous forme de P nombres
binaires ait été effectuée en vue de la restitution ultérieure du
. caractère, ou en vue de sa reconnaissance pour son exploitation
dans un ordinateur (cas d'un nombre '11u" automati~uemcnt à l'en-
trée d'un circuit de calcul), dans les machines connues, toutes
ces informations doivent être conservées, le graphisme n'y étant
identifiable gue par la totalité de celles-ci.
La présente in~ention a pour objet un procédé de trai-
tement de ces P informations, en vue de la reconnaissance des
caractères ac~uis, procédé gui permet notamment de réduire nota-
blement le nombre des informations utiles caractérisant un gra-
~ phisme donnéO La présente invention a également pour objet les
dispositifs de mise en oeuvre de ce procédéO
Pour alléger le langage, on utilisera, dans ce guisuit, indifféremment les termes "caractère" et'~raphisme" aussi
bien pour désigner une forme à reconnaître proprement di~ gue
pour désigner les P nombres binaires gui lui correspondent dans
~066805
les procédés d~acguisition susvisés, et ce, bien entendu, cha~ue
~ois gu~il n'y aura pas de confusion possible~
On utilisera également le terme ~'point~' pour désigner
. un point géométrigue du graphisme et pour désigner un point
mémoire, c~est-à-dire le nombre binaire correspondant à une zone
~ élémentaire précitée.
: Pour la clarté du texte et pour fixer les idées 7 on
~ suppose, dans ce ~ui suit, ~ue les zones du caractère auxguelles
correspondent les P nombres binaires ont été définies par des
axes de coordonnées respectivement horizontal et vertical~
- Le procédé de traitement suivant l'inve~tion comporte
trois étapes successives essentielles :
un pré-traitement du graphisme aboutissant à la sépara-
.~ tion des segments verticaux, horizontaux, obligues à
pente positive et obli~ues à pente négative, gui le cons-
tituent, les lignes courbes étant considérées comme for-
mées par une succession de segments de pentes différentes;
(ii) - la localisation des divers segments constitutifs du gra-
phisme;
(iii) - la reconnaissance des formes proprement dites.
La première étape revient à effectuer une transforma-
tion point segment, les informations définissant le caractère en
fin de cette étape étant séparées suivant l'orientation du carac-
t.ère au point considéréO
La seconde étape aboutit à la réduction de l'infor-
mation, le nombre total des informations retenues étant la somme
des nombres de zones de localisation pour chague direction de
segmentO Pour la reconnaissance des caractères alphanumérigues
~ ~64 caractères : 27 minuscules, 27 majuscules et 10 chiffres)
il s'est avéré utile de définir 2i zones : six zones pour la lo-
calisation des obligues à droite et six zones pour celle des
.~ .
- 2 _
~L066805
obligues a gauche, six zones pour la localisation d~s verticales,
et trois zones pour la localisation des horizontales.
A la fin de cette étape, le graphisme est caractérisé
par T variables binaires, 21 dans le cas des caractères alpha-
numérigues, chacune d'elles indiguant la présence ou l'absence
d'un segment d'orientation donné dans une zone donnéeO
Quant à la troisième étape, elle consiste essentiel-
lement en un transcodage ou un décodage suivant l'utilisation
prévue réalisable par une logique combinatoire simple lorsgue le
nombre de caractères à reconnaître est réduit~ comme c'est le
- cas pour l'ensemble des caractères alphanuméri~ues courants;pour
les caractères plus complexes, ou plus nombreux talphabet cyril-
li~ue, idéographe~.. ), le transcodage pourra être réalisé plus
avantageusement par comparaison des valeurs des variables bi-
naires avec des ensembles de valeurs mises en mémoire égales aux
valeurs de ces variables; lesdits ensembles correspondant respec-
tivement aux différents caractères à reconnaître.
Un appareil de traitement suivant l'invention, pour la
mise en oeuvre de ce procédé, comprend :
- un circuit de calcul de sommes des points mémoire se trouvant
de part et d'autre d'un point donné suivant des directions ho-
rizontales, verticales et obligues à pente positive et à pente
negatlve;
- un circuit d'affectation desdits points à un segment horizontal,
vertical ou obl~ue, par comparaison des diverses sommes obte-
nues et éliminations des fausses indications par contrôle de la
présence d'au moins un point adjacent sur le segment retenu
pour un point donné;
- un circuit de calcul de zones définissant pour cha~ue caractère
un certain nombre de zones par comparaison des coordonnées
de tous les points;
:~0~i680S
- un circuit de localisation des divers segments dans lesdites
zones, fournissant les variables binaires de caractérisation du
graphisme: et
- un ensemble de circuits logigues élémentaires assurant le
décodage de ces variables.
Dans le cas particulier où les caractéres auront été acquis
au moyen de l'appareil d'acquisition décrit dans la demande de
brevet française No. 73.46285 deposée par la Demanderesse le
26 ~écembre 1973 et ~ublie le 21 Novembre 1975 sous le ~o. de
publication 2.269,290 pour "Appareil d'acquisition de texte pour
machine a reconnaissance des formes" dans lequel les données d'un
caractére sont acquises en série par balayage suivant des coordonnées
cartésiennes et stockées dans une memoire à accés et sortie série,
à 256 adresses, un circuit de calcul des intégrales suivant l'invention
comporte deux registres série-parallele a huit sorties, respectivement
pour les coordonnés horizontales et verticales des points; quatre
additionneurs effectuent les calculs des intégrales suivant le
segment horizontal, vertical, obliaue positive et oblique négative
(en prenant pour origine le sommet d'une maille de'finie par quatre
surfaces élementaires d'acquisition).
Le circuit deca]cul des zones ccmporte deux registres
parallele-paralléle definissant le gabarit du graphisme et des
circuits de calcul definissant les coordonnées des limites de
diverses zones de localisation.
Le circuit d'affectation des segments aux diverses zones,
c'est-à-dire de definition des variables caracte~risant le graphisme,
comporte des circuits de coincidence de l'adresse d'un segment avec
une adresse quelconaue camprise dans la zone considérée.
Le circuit de décodage comporte un ensemble de circuits
logiques exprimant la presence simultanée de certaines
_ 4 _
~066805
des variations à l'exclusion de certaines autres.
Une logi~ue de commande assure la transmission automa-
tigue des données de la mémoire d'ac~uisition aux circuits de
reconnaissanceO
Dans le cas particulier précite, les informations rela-
tives à un caractere étant réduites des 256 valeurs d'ac~uisition
à 21 valeurs binaires, on voit ~ue le stockage des informations
est considérablement simplifié. D'autre part, les circuits de
décodage sont réduits à une simple combinaison de circuits
logi~ues élémentaires.
Les particularités et avantages de l'invention précé-
demment cités, ainsi c,ue d'autres, apparaîtront plus clairement .
dans la description ~u~suit, donnée à titre d'exemple nullement
limitati~.
Aux dessins annexés :
- ~ La figure 1 est le schéma explicatif;
La figure 2 est le schéma synoptigue simplifié du
procédé suivant l'inven~ion;
' Les figures 3a-3d sont descchémas explicatifs;
. 20 La figure 4 ëst un schéma synopti~ue détaillé de la
~ mise en oéuvre du proeédé suivant l'invention;
~.~ La figure 5 est le schéma synopti~ue d'une machine
complète de reconnaissance de formes suivant l'invention;
La figure 6 est le schéma synopti~ue d'un exemple de
réalisation d'un des circuits de la figure 5;
: La figure 6a explicite un détail de la figure 6;
: La figure 7 représente l'algorithme ~ui est effectué
par le circuit 60 de la figure 6;
La figure 8 est un schéma explicatif;
Les figures 9, lOa, lQb; lla et llb sont des organi-
grammes des circuits de la figure 6;
: - 5 -
-
~066~305
Les figures 12~ 13 et 14~ sont des schémas explicatifs;
La ~igure 15 est le schéma synoptigue simplifié d'un
des circuits de la figure 6;
La figure 16 est un exemple préféré de schéma synop-
tigue détaillé du circuit de la figure 15;
Les figures 17, 18 et 19 constituent, ensemble, l'or-
ganigramme du circuit de la figure 16;
La figure 20 est le schéma synopti~ue simplifié d'un
des circuits de la figure 6;
La figure 21 est un exemple de réalisation du circuit
de la figure 20;
La figure 22 est l'organigramme du circuit de la
~igure 21;
La figure 23 est un exemple de réalisation d'un des
circuits dè la figurè'16;
Les figures 24a et 24b sont des schémas explicatifs;
La figure 25 est l'organigramme du circuit de la
figure 23;
Les figures 26, 27 et 28 sont des schémas synoptigues
de circuits de la figure 6, et
. Les figures 29, 30, 31, 32 et 33 sont des diagrammes
gui représentent~ en fonction du temps~ divers sisnaux mis en jeu
dans les circuits décrits.
Pour ~ixer les idées, on suppose gue le graphisme à
reconna~tre a été acguis comme indigué dans la demande de brevet
français précitéeO
Dans ce cas, le graphisme à reconnaître est stocké dans
une mémoire organisée en 16 lignes de 16 pointsO
L'information memorisée par chague élément de cette
mémoire est 1 ou 0 selon gue le point correspondant appartient
ou non au graphismeO L'adresse d'un élément de la mémoire est
- ' ' ~ ~
~066~ 5
- définie par le couple (x, y). On définit ainsi une fonction bo-
léenne M (xy) où O ~ x ~ 15, 0 ~ y ~15 gui caractérise le
graphisme 5 lui-même constitué par un ensemble de carrés noirs ou
blancs adjacents comme représenté figure lo Pour simplifier, on
appellera également M (xy) le point~mémoire correspondant.
Le procédé de traitement~suivant l'invention est sché-
matisé à la figure 2.
En 21 est effectuée l'opération de séparation des seg-
ments : les points mémoire M (xy) sont comparés entre eux de
1~ manière à déterminer si un point m (X, Y) sommet d~une maille
X ~ 15; 1 ~ Y ~ 15) définie par les carrés formant le
caractère (voir'figure 1), appartient- à un segment horizontal (H),
vertical (V), obligue positif ou à droite (D) ou obligue négatif
. ou à gauche (G). Pour simplifier on désignera ces segments respec-
tivement par H, V~ D, G, dans ce ~ui suit.
En 22 les divers segments précédemment reconnus sont
localisés, ce gui aboutit à la détermination de 21 variables bi-
naires ~ 1 à ~ 21 correspondant généralement aux zones indiguées
: aux figures 3a, 3b, 3c, 3d respectivement pour les segments D, G,
V, H; la délimitation de ces zones sera expliguée plus loin,
étant entendu ~ue le nombre de zones choisies dépend du nombre de
graphismes possibles à reconnaître et de leur différenciation
graphi~ue. Sur ces figures, le rectangle intérieur représente le
. gabarit du graphisme, le rectangle extérieur le gabarit de la
~. zone d'acguisition représentée figure 1~ Un segment localisé
. dans une zone peut etre situé n'importe où à l'intérieur de celle-
ci. Les pentes des segments obligues peuvent être différentes,
seule leur orientation générale est considérée.
.~ Enfin, en 23, on effectue le transcodage ou le décodage
~~ 30 de ces variables par une logigue combinatoire, chague graphisme
étant caractérisé par la présence simultanée de certaines de ces
.
1{~66805
variables à l'exclusion de certaines autres.
Sui~ant une mise en oeuvre préféree du procédé de
l'invention, illustrée par la ~igure 4 :
- l'opération de séparation des v, H,-G et D comporte une étape
- (21a) d'ac~uisition des points mémoire M (x, y) situés autour
.- d'un point m (X, Y), une étape (21b) de calcul au cours de la-
guelle sont calculées les intégrales de~ points mémoire situés
sur des verticales, des horizontales ou suivant des obli~ues
par rapport au point m (X, Y) et une étape (22c) de comparaison
de ces intégrales résultant en l'af~ectation des points m (X, Y)
à des mémoires ncC différentes (aveo~ = V, ~, G, D) suivant le
segment au~uel ce point appartient, et
- I'opération de localisation des segments comporte une étape
(22a) d'ac~uisition de l'ensemble des points M (xy), une étape
(22b) de calcul des paramètres définissant les diverses zones
~i parmi les~uelles sont répartis les divers segments et une étape
(22c) de comparaison des coordonnées des points m (X, Y) en mé-
~- moire dans les mémoires m~ , avec celles définissant les zones.
Les opérations des étapes 22a et 22b pourront etre
réalisées avant, pendant ou après les étapes 21a, 21b et 21c.
. On voit à la figure 5, le schéma dé principe le plus
général d'une machine à reconnaissance de ~ormes comportant un
appareil de traitement suivant l'invention.
Sur ce schéma~ le s~stème d'ac~uisition, ~ui n'est pas
. un objet de la présente invention, est représenté globalement en
51. L'appareil de traitement comporte essentiellement :
- une mémoire M où sont emmagasinés les signaux binaires repré-
. ~ sentatifs d'un caractère
- un générateur 52 d'adresse de la mémoire M
- un circuit, 53, d'extraction des verticales, horizontales,
obli~ues droite et gauche
'
-- 8 --
~Q66805
- guatre mémoires moC aveccC = H, V, D, G pour les segments ex-
traits en 53; ces mémoires sont adressées par le générateur d'-
adresses m, 54, lui-même contrôlé par le générateur d'adresses
M52, la relation entre les adresses (X, Y) d'un sonmet de maille
et les adresses (x, ~) des points M étant définie conformément
à la figure 1.
L'ensemble du circuit ~3 et des mémoires m~ réalise
les étapes 21a à 21c;
- un circuit 55 de calcul de zones, réalisant les étapes 22a et
22b,
- un circuit de tests, 56~ effectuant la caractérisation du gra-
phisme (étape 22c). Ce circuit détermine dans ~uelles zones,dé-
finies par le circuit 55, se trouvent les segments mis en mé-
moire en m~ , et définit ainsi les 2i variables ~i; et
- un décodeur 57 (étape 23). La sortie de ce décodeur atta~ue des
dispositifs d'exploitation U, par exemple un ensemble d'affi-
- chage tel gue les tubes Nixie.
- Bien entendu, des mémoires et des générateurs d'adresses
-~ distincts peuvent être utilisés si nécessaire pour l'ac~uisition
et la reconnaissance.
L'ensemble des circuits d'acguisition et de reconnais-
sance est avantageusement synchronisé automati~uement par une lo-
gi~ue de commande unigue L ~ui envoie des ordres d'opération aux
divers circuits, ces ordres étant à la fois programmés dans la
logi~ue interne de L, et contrôlés par des signaux en provenance
des divers circuits comme indi~ué par les diverses flèchesO
- Ces ordres définissent des phases opératoires des di-
vers circuits. En résumé, le circuit de traitement suivant l'in-
vention fonctionne en dix phases, ~0 à ~9~ explicitées plus loin.
Pour la clarté de la figure~ on a représenté par
- des traits continus simples les connexions fonctionnelles
1C~6613~X
- réalisant le transfert de données pr~prement dites d'un circuit
à un autre;
- des traits doubles : les connexions réalisant le transfert d'-
.': indications d'adressage des mémoires (ces connexions vehiculent
des signaux multiples, en nombrc égal à celui des bits d'adresse)
- des traits discontinus : les connexions servant aux transferts
-' d'ordresD
Les divers signaux véhiculés par les diverses conne-
xions seront explicités plus en détail ultérieurement, lors de la
description d'exemples pré~érés de mise en oeuvre avec référence
aux figures suivantes~
La figure 6 est le schéma synopti~ue d'un exemple de
réalisation du circuit d'extraction des segments V, H, D et G.
Pour la détermination de l'appartenance d'un point m
~X, Y) à un segment V, H, D ou G, on calcule guatre integrales
: respectivement Iv, IH, ID, IG, ~ui sont les sommes discrètes des
. points mémoire M(x, y) de part et d'autre du point considéré,
.~ suivant des segments verticaux pour Iv, horizontaux pour IH,
: obli~ues vers la droite pour ID et vers la gauche pour IG~
En tenant compte des relations entre les coordonnées
X, Y, des points m sommet de la maille et les coordonnées (~, ~)
des points M(x~y) illustrés figure 1, on voit ~ue pour un point m
d'adresse X, Y intégrales, les adresses x, y des points M néces-
saires sont :
x = X + n ; y = Y + p
x = X * n ; y = Y - (1 ~~ p)
~. x = X - (1 + n) ; y = Y + p
x = X - (1 + n) ; y = Y - (1 + p)
x = X + p ; y = Y + n
x = X + p ; y = Y - (1 + n)
x = X - (1 + p) ; y = Y + n
x = X - (1 + p) ; y = Y - (1 = n)
~ '
- 10
10668()S
.. Compte-tenu des ~aleurs précitées de x et y, ces inté-
grales s~écrivent :
n P
max max
ID = ~ ~ M CX - ln + 1), Y +p~ M ~X + n, Y - (p + 1
n=0 p=n
+ M~X - (p + 1), Y + n~ M~X + p,[Y - (n + 1
n P
max max
IG = ~ ~ M~X - (n-+ 1), Y - (p + 1~ M ~ + n, Y + p)
n=0 p=n
+ M[X - (p + 1), Y - (n + 1~ M~X + p, Y + n~
~ 10 P max
V = ~ ~ -1, Y-(P+1~ M ~ , Y-(p+1 l + M ~ -1, Y+p~ M ~ , Y+p~
' p=O
: P max
; IH = ~ M ~-(p+1), Y- ~M ~X-(p+1), Y~ + M~X+p, Y- ~M ~X+p, Y~
p=O
où nmaX et PmaX sont égaux à la plus petite des valeurs de k
définies par les inégalités x - (1 + kj~ 0, x + k ~15,
y - (1 + k)~ 0, y + k ~15 et où P'max est la plus grande des
valeurs définies par ces inégalitésO
Les points mémoire pris en compte pour le calcul de
IV : correspondent à des points situés sur les verticales adja-
centes au sommet de maille m(X, Y);
IH : correspondent à des points situés sur les horizontales adja-
centes à m(X, Y);
ID : correspondent à des points situés sur des obligues passant
par m(X, ~) inclinées vers la droite;
IG : correspondent à des points situés sur des obligues passant
par m(X, Y) inclinées vers la gaucheO
~' Les segments considérés ont une certaine largeur de l'ordre du
double de celle d'une surface élémentaire d'acguisition.
Ces intégrales sont donc des mesures de l'appartenance du sommet
de maille respectivement à un segment horizontal, vertical,
'~
~ 1066805
obligue droite, obligue gaucheO La décision d'affectation d'un
point à l'un de ces divers types de segmen~s est prise en tenant
compte de la valeur relative de ces intégralesO
Le schéma de principe représenté ~igure 6 comporte es-
sentiellement :
- ces compteurs 6v, 6H~ 6G et 6D~ ef~ectuant lesdites sommes
- une logigue 60 d'affestation des points suivant les valeurs re-
latives des intégrales; cette logigue af~ecte les points sui-
~ vant l'algorithme représenté figure 7 ~ui sera explicité plus
loin, et
- des ensembles de circuits annexes E1 et E2 dont le rôle est
essentiellement :
- circuit E1 : de fournir aux compteurs les valeurs élémen-
taires de calcul,
- circuit E2 : d'assurer l'inscription, dans les mémoires mv,
mH, mG, mD, des valeurs retenues d'une part en cours de cal-
cul, d'autre part après segmentation, c'est-à-dire après éli-
mination des points parasites dont l'existence éventuelle sera
- explicitée plus loin.
Sur la figure, les nombres entre parenthèses sur les
lignes de connexion doubles indi~uent le nombre d'informations
véhiculées simultanément.
Les circuits ~1 ont été conçus de fa~on à ~onctionner
automatiguement ~uelles ~ue soient les valeurs de x et y. Ils
comportent des moyens de validation des calculs suivant ~ue les
valeurs correspondantes des coordonnées sortent ou non de la
. mémoire.
Les circuits E1 comportent :
- un registre série-parallèle 61
- une logigue 62 de validation des points mémoire
- un circuit 63 d'élaboration de sémaphores
- 12 _
66805
- un ensemble de mémoires 64
- une logigue 65 de validation des calculs et
- une logi~ue 66 de commande des e~trées des compteu~s.
Les circuits E2 comportent une logi~ue 67~ d'inscrip-
tion des mémoires m~ et une logi~ue 58 de confirmation des points
. inscrits dans les mémoires mO
Llentrée de signal du registre série parallele 61 est
couplée à la sortie de la mémoire M (voir figure 6)o Ce registre
comporte d'autre part une entrée de contrôle, couplée à la sor-
tie de la ~ogi~ue 52 de validation de points, et une entrée desynchronisation couplée à la logi~ue générale L~ Le registre
comporte huit sorties en parallèle sur les~uelles sont dispo-
nibles les valeurs t0 ou 1) des huit points nécessaires au cal-
cul des intégralesO
Un circuit annexe 62, designé comme étant la "logi~ue
de validation des points mémoire" assigne à ces sorties la va-
leur zéro dès ~ue l'adresse d'un point situe celui-ci à l'exté-
rieur de la mémoire. Cette logi~ue compare les adresses X = n,
X = (1 + n), X + p X - (1 + p) d'une part, Y + p, Y - (1 + p),
Y + n, Y - (1 + n) d'autre part avec les valeurs minimum (0) et
maximum (1~) gue peuvent prendre les adresses des points mémoire
Mo D'autre part, les points n'appartenant pas au segment du point
M ( xy) considéré ne devant pas être pris en compte, le circuit
63 élabore des sémaphores gui sont appli~ués à la logi~ue de com-
mande des compteurs et annulent par celle-ci la contribution de
ces points au calcul des intégrales (cas, par exemple, illustré
à la figure 8 d'un sémaphore posé pour un segment vertical vers
le haut du point m(X, Y) ); ce sémaphore est posé lors~ue les
points mémoire d'adresses X-(l+p), Y-(l+n) et X-(l+n), Y+p sont
1 pour p=0 et ~ue l'un dbux est zéro pour p=1 (croix eO, gO~ e1
sur la figure 8~o Dans ce cas on ne doit pas prendre en compte
13 -
~ ' -
- ~066805
les points ultérieurs (p = 2, 3,..) meme s'ils sont égaux à 1,
pour le calcul de Iv. Pour élaborer ces sémaphores, le circuit
63 doit disposer des valeurs aux sorties du registre correspon-
dant à un couple de valeurs n, p et des valeurs précédentes ~ui
lui sont fournies par la mémoire 64 dont l'accès est synchronisé
également par la logi~ue L (figure 53.
La logi~ue 66 de commande des compteurs autorise l'en-
trée d'un compteur I~ (~ = V, H~ G, D) aux signaux de sortie du
registre 61 si :
- ce signal correspond à un des termes de l'intégrale calculée
par le compteur considéré, et si
- il n'~ a pas un sémaphore pour l'intégrale considérée.
Lors~ue pour un couple de valeurs X~ données, l'ensem-
ble de la memoire a été exploré, les compteurs 6v, 6H, 6G~ 6D
contiennent les valeurs des intégrales.
La figure 7 montre un algorithme préféré réalisé par la
logi~ue 60 pour l'affectation des-points m (X, Y) à l'une des mé-
moires ~V' mH, mG et mD-
Les symboles uti1isés sont les suivants cha~ue hexa-
Z0 gone représente une interrogation posée dans le sens indigué, parexemple l'hexagone supérieur correspond à la ~uestion : "est-ce
~ue I~I est supérieur à 21V ?'lo Si la réponse à l'interrogation
est "oui"~ on procède à l'opération indiguée à la sortie "~" du
losange; dans le cas contraire, on procède à l'opération indi~uée
à la sortie ''-''0
Ainsi si IH est supérieur à 21V, on affecte le point à un seg-
ment horizontal, c'est-à-dire ~u'on entre un "1" dans la mémoire
mH à l'adresse X, Y0
L'algorithme indi~ué a été retenu pour sa simplicité.
Il n'est pas symétri~ue, donnant la préférence au départ aux ho-
zontales. Il est bien évident ~ue l'on pourrait en conservant le
~ ~06680S
.
meme schéma d~opérations intervertir IV et IH d'une part, IG et
ID d'autre part. On pourrait aussi prendre un algorithme symé-
trigue~ mais au prix d'un circuit plus compligué, ~ns intérêt
prati~ue.
Lorsgu'un point m(XY) a été affecté à une des mémoires
m~ , on recommence l'opération par un nouveau point à condition
~ue ce nouveau point appartienne à un segment du caractère. Ceci
est reconnu par le fait gue dans les guatre surfaces élémentaires
dont le point m(X, Y) est le sommet commun, il y a au moins trois
"1ll, ou deux "1" disposés symétriguement par rapport à ce sommet.
Clest le rôle de la liogigue 65 de validation des calculs de dé-
terminer s'il en est bien ainsi. Si oui, la logigue 65 envoie
des signaux de validation à la logigue d'affectation. La logigue
61 envoie aussi un signal d'information à la logigue générale L
pour la suite des opérations du système.
Cette opération d~affectation est effectuée pour tous
les points du graphisme. A la fin de l'opération les points m
(X, Y) se trouvent répartis dans les mémoires mv, mH, mG, mD ~ui
contiennent respectivement les points placés sur des segments
horizontaux, verticaux, obligues gauche et obligues droite. Au
cours de cette opération, il n'y a pas eu de réduction de l~in-
formation à proprement parler, mais seulement transformation des
points M(xy) en m(X, Y).
L~entrée dans les mémoires m~ est effectuée sous le contrôle des
circuits E2 gui comprennent une logigue d'inscription 67 et une
logigue de confirmation 68.
La logigue de confirmation compare les signaux emmaga-
sinés dans les mémoires m~ selon les critères suivants :
- un point situé dans la mémoire mv est confirmé s'il existe au
moins un point adjacent sur la même verticale, c'est-à-dire à
la même adresse X;
- 15 -
iO668(15
- un point situé dans la mémoire mH est confirmé s'il existe au
moins un point adjacent sur la même horizontale, c'est-à-dire
à la même adresse Y;
- un point situé dans une mémoire mD ou mG est confirmé s'il
existe au moins un point adjacent sur l'obligue à 45~ de meme
orientation passant par ce point, c'est-à-dire à l'une des
adresses (X ~ 1, Y - 1) ou (X - 1, Y ~ 1) pour la mémoire mD
et à l'une des adresses (X - 1, Y - 1) ou (X ~ 1, Y ~ 1) pour
la mémoire mG.
La logigue 67 d'inscription des mémoires permet d'ai~
guiller sur l'entrée d'écritures des mémoires m~ la bonne infor-
mation, c'est-à-dire gue selon la phase opératoire où l'on se
- trouve, cette logigue effectue l'opération d'inscription en pro-
venance de la logigue d'affectation 60, ou l'opération d'ins-
cription (point confirmé) ou d'effacement (point non confirmé)
en provenance de la logigue de confirmation 60. Les diverses
phases opératoires sont synchronisées par la logi~ue générale Lo
La circulation des données depuis la mémoire M (figure
5) jusgu'aux compteurs, est illustrée par les organigrammes des
figures 9, lOa, lOb, lla et llb et programmée, conformément à ces
organigrammes, par la logi~ue de commande L.
Conformément à l'organigramme de la figure 10, l'explo-
ration de la mémoire M(x, y) autour du point m (X, Y) représenté
figure 1, pour en extraire les points nécessaires au calcul des
intégrales, est effectuée comme représenté figure 12 : on extrait
d'abord les points de la croix centrale A dU centre m, puis ceux
des zones B, puis ceux des zones C~ etcO0., ce gui correspond à
zone A : n=0 p = 0, 1, 2 ~-- P' a
zone B : n=1 p = 1, 2, 0OO
zone C : n=2 p = 2, 0..
etc.. Sur cette figure, les hachures ont uniguement pour but de
désigner nettement les zones.
- 16 -
1066805
Les phases ~o7 ~l et ~2 sont a~fectées respectivement :
- - - à la génération des adresses x~ y de la mémoire M (sur les fi-
gures~ on représente par Adi l~ensemble des bits d~adresses x,
y);
- à la générAtion des adresses X, Y nécessaires pour la confir-
mation des points dont les mémoires mV et ~ ; et
- à la génération des adresses X, Y nécessaires pour la confir-
mation des points dans les mémoires mG et mDO
.
Xdi et Ydi représentent sur les figures l'ensemble des
bits d'adr~sses X et Y respectivement.
Le programme est le suiYant :
Au départ : X = Y = 1 n = p = O IG = ID = IH = IV
aucun sémaphore n'est posé (Fi = O ~uel gue soit i)
le registre 61 n'est pas chargé, ce gui est exprimé
par Qi = 00
Les circuits sont programmés par n et p guelcongues.
n et p étant ~ixés, les différentes adresses x, x ~ n, x - (l+n),
y~ y + p~ etcO. sont comparées à leurs limites O et 15o
Les condition~ inîtiales sont rappelées en 9.1 en haut
de la figure 90
Pour chague valeur de n le sous programme représenté
a.ux figures lOa et lOb (dont l~ensemble constitue la figure 10)
est effectuéO
Les symboles utilisés pour ces organigrammes sont iden-
tigues à ceux gui sont utilisés figure 70
On rappelle gue les valeurs X + n, X + p, X - (1 + n)
etcO. et Y + n, v + p, etcO. représ0ntent les valeurs d'adresses
x, yO
Les notations sont les suivantes :
Depx+~Depy+ = débordement par excès (x> 15 ou y ~ 15)
Depx+, Depy = débordement par dé~aut (x < O ou y ~ 0)0
. .
- 17 _
1066805
Le signal Dep est "1" si x ou y dépassent les limites
0, 15-
To = 1 pour n = 0
Tl = 1 s'il y a débordement de partout
T2 = 1 s'il y a au moins un débordement sur une adresse x et une
adresse y
T3 = 1 pour p = n
T4 = 1 pour p = 0
Les signaux QA ~ . . ~ QH sont les valeurs disponibles pour les
intégralesO Ils traduisent l'existence ou l'absence d'un point à
l'adresse x, y, considérée, définie figure lOa.
La partie lOa de l'organigramme 10 représente les opé-
rations logigues d'acguisition des valeurs QA ~ . ~ QH.
La génération des adresses x, y, nécessaire à leur mise
en oeuvre est décrite plus loin avec référence à la figure 260
La partie lOb de cet organigramme représente l'opération
de validation des calculs effectués en 65 (figure 6), les signaux
: VG, VD, exprimant, lorsgu'ils sont 1, gu'il y a validation des
calculs pour un point situé sur une obligue à gauche et à droite
respectivement, le signal V = 1 exprimant gu'il y a au moins 3
points M appartenant à un caractère autour du point m précédemment
considéré et le signal VA = 1 exprimant gue l'un au moins de ces
signaux a la valeur llll'.
g ~ = VB, V~I, etcO..) t les séma
phores générés par le circuit 63; lorsgue F~r = 1 les points
situés au-delà du dernier dans la direction indiguée par ~r ne
sont pas pris en compte; la pose des F~r correspond aux cas
similaires à celui gui est illustre figure 8.
Les abréviations~ ~ utilisées signifient :
VB sur la verticale du point et vers le bas, descendante;
VH sur la verticale et vers le haut;
HG sur l'horizontale vers la gauche;
: - 18 -
-
1066805
HD sur l'hori~ontale vers la droite;
GH sur 1'obligue à gauche vers le haut;
GB sur l~obli~ue à gauche vers le bas;
DH sur l~obli~ue à droite vers le haut;
DG sur l'obligue à droite vers le basO
Le sous-programme des figures 10- lOb est mis en oeuvre
autant de ~ois ~ue nécessaire pour explorer la totalité des H, V,
G, D, passant par le point m (1, 1); ce sous-programme, lorsgu'-
il est terminé, recommence automati~uement pour le point suivant
à droite sur la même ligne et, si la ligne est terminée, pour le
~ point d'abscisse 1 sur la ligne suivanteO
Il démarre avec n = p = 0 (condition initiale).
Lors~u'il est terminé, il recon~ence pour n = 0, p = 1,
puis p = 2, etc, jus~u'à débordement (Depy+ = l)o
Puis il recommence à n = 1, p = 1, puis p = 2, etc..0
Ceci est exprimé sur l'organigramme par p ~ 1 = p,
c'est-à-dire gue la nouvelle valeur de p est égale à la précé-
dente incrémentée de 1o
Les notations n + 1 = n et X + 1 = X ont la meme signi-
fication pour n et X respectivementO
La notation Qi . _ ~ Qio indi~ue ~ue Qi devient lavaleur Qio de départ.
Qi représentant QA, QB ..0 et les intégrales Iv, IG,
IH, ID étant exprimées par
P max
. IH = ~ QA QB + QC QD pour n - 0
P max
~ IV ~ QE QG + QF QH pour n = 0
o
-- 19 --
,
~ . . .
1066B05
nmax Pmax
E~QH QA-QD
n=O p=n
nmax Pmax
LD ~ ~ QF QG ~ QB ~ QC
n=O p=n
L'organisme de la figure ~ montre la contribution des
calculs effectués conformément à l'organigramme de la figure 10
au calcul des intégrales, comme indigué en 92 et 93.
Lorsgu~on arrive en 99, tous les points ont été traités
(puis~ue Y = 15 et X = 15). On passe alors aux phases suivantes
~1 puis ~2 en repartant des conditions X = Y = 1, n = p = O
pour la confirmation des points affectés aux mémoires m~ .
- Les opérations de confirmation des points sont effec-
tuées suivant l'organigramme de la figure lla pour les points des
mémoires m~ et mH et de la figure llb pour ceux de mG et mD.
Ces opérations consistent essentiellement à vérifier la
présence d'un point adjacent sur le segment retenu.
En se reportant à la figure 1 pour la signification de
X et Y~ on voit gue les adresses indiguées dans les parties à
gauche des rectangles llal et llbl, llb2, correspondent à des
points situés par rapport aux points d'adresses X, ~ dans les di-
rections désignées par les abréviations H, D (horizontale~ droite,
etc...)~ la notation m~ ~ indiguant : point de la mémoire m~
situé dans la direction ~ par rapport au point m tX, Y) avec
~ = D vers la droite, ~ = H vers le haut, etc..., et pour les
obli~ues ~ = HD vers le bas à droite, ~ = BG vers le bas à
gauche, etc.~.
Dans la mémoire M le graphisme est caractérisé par un
ensemble de points M (x y). Le graphisme est encore caractérisé
par un ensemble sensiblement égal de points m (X, Y) répartis dans
- 20 -
1066805
les mémoires m~ suivant l~o~ie~tation du graphisme au point
considéré.
- On a donc dans une mémoire m~ 1'ensemble des points
du graphisme appartenant à des segments de même orientation. On
peut encore dire gue l~on a dans une mémoire m~ un ensemble
de segments de meme orientation d'adresses différentes m (X, Y),
les segments d'une mémoire m~ étant caractérisés par autant d~-
adresses ~u~il y a de points m(X, Y) en les~uels le graphisme a
la même orientation.
Le nombre de ces informations est ensuite réduit par lo-
calisation d'un segment de t~pe donné, non plus par son adresse
m (X, Y), mais par l'appartenance de son adresse à une zone
donnée, tous les segments de même orientation situés dans la
même zone représentant une information uni~ue, comme cela est
schématisé figures 3a à 3d, un segment représenté sur cette
figure correspondant à un ou plusieurs segments de même orienta-
tion, situé n'importe où dans la même zone, tous les segments
de même orientation situés dans une même zone donnant lieu à
une information binaire ~i uni~ue suivant le principe essentiel
de l'inventionO
La localisation de segments par zone nécessite la com-
paraison des adresses m(X Y) des points de la mémoire m~ avec
les adresses des limites des diverses zones. Le circuit 55 de la
figure 5 a précisément pour objet le calcul de ces adresses ~ui
comporte les étapes suivantes :
(i) définition du gabarit, c'est-à-dire du rectangle dans le~uel
s'inscrit le graphisme. Ceci est obtenu par projection de
l'ensemble des points constituant le graphisme sur les axes
correspondant aux deux adresses~ Ceci peut être fait à par-
tir des points M (x, y), ou m(X, Y)O
= .
_ 21 -
'
1066805
Le CircUit de définition de zone représenté à la ~i-
gure 15 opère sur les points m (X, Y) ~ui so~t dispo~ibles dans
les mémoires m~ .
La projection du gabarit (voir figure 13) détermine :
. - les grandeurs l , L ~ui définissent la position du graphisme
dans la fen8tre d'acguisition, c'est-à-dire encore les adresses
X et Y minimum aux~uelles il y a au moins un point mémoire 1
dans au moins l'une des mémoires m~ , et
- les grandeurs 11 + L1 et lo + LO ~ui sont les adresses X et Y
maximum aux~uelles il y a au moins un point mémoire 1 dans au
moins l'une des mémoires m~ .
(ii) définition des zones à l'intérieur du gabarit.
Pour les horizontales, on considère ~u'elles sont en haut, au
centre, ou en bas, sui~ant ~ue leurs projections sont situées
respectivement dans les intervalles
~Lo LO + 2 f
CLO + 2 Lo + L1 -2
Lo + L1 -2 Lo + L1J
Ces intervalles définissent les trois zones Za~ Zb, Zc,
(représentées figure 14 en a) définissant trois paramètres 17,
; 18, 19 (voir figure 3d) caractérisan* les segments horizontaux
d'ordonnée Y respecti~ement définies par
Lo ~ Y ~ Lo + 2
LO + 2 ~Y ~ o + L1 -2
Lo + L1 -2 ~ Y ~ Lo + lo
Quant aux obli~ues, on les répartit suivant les X en
deux zones égales droite et gauche égales ZD et ZG, sui~ant ~ue
leurs adresses X sont inférieures ou égales à XG ou supérieures
à XD, XG, et XD étant définies par XG = E ~210 ~ /2
XD = E f210 + llJ /2 +1
où "E" signifie "partie entière de".
- 22 -
1066805
Sui~ant les Y on les répartit en trois zones ZII~ ZB~ ZC~
correspondant au~ adresses Y telles gue:
pour ZH : 'l ~ YH; pour ZB : Y~ YB; pour ZC : ZH ~ Y <YB
où YH = E (2 Lo 2 L1 _3)
et YB = E (2 lo 2 Ll +3) + 1
Pour les graphismes de faible hauteur (L1 < 10) on ne
définit gue deux zones égales; on a alors
2 Lo + L1 _ 1 <YH = E ( Lo + L1) + 1
Z Lo + L1 + 1~ YB = E (2 Lo2+ L1) + 1
Les hauteurs des trois' zones définies pour les obli~ues
guand L1~ 10, diffèrent de celles définies pour les horizontales,
la zone centrale des obli~ues étant plus petite.
Dans le cas général (L1> 10), il y a do~c six zones,
caractérisation des obli~ues~ intersection des zones Z~, ZB, ZC
avec les zones ZG, ZD, définissant les 6 paramètres ~ 6 et
12 conformément aux figures 3a et 3bo
~-~ Pour les verticales, on considère ~u'elles se trouvent
à gauche, au centre, ou à droite, suivant ~ue leurs projections
sont situées respectivement dans les intervalles
~1o lo + 2 [
[l + 2 lo ll 2 [
o ~ 2 lo ~
~ui définissent les 3 zones Zg, Zc1, Zd de la ~igure 14 (b).
Pour les verticales gui se trouvent dans la zone Zg,
c~est-à-dire dont l'adresse X est telle ~ue lo~ X ~ lo + 2,
on distingue les zones haute ZgH, intersection de Zg et ZH, basse
ZfB, intersection de ZgB et ZB et centre, c'est-à-dire hors de
ZH et ZB, ou encore intersection de Zg et ZH.ZB. Les paramètres
~15, ~16, et ~21 caractérisent respectivement les verticales
de ces zones.
- 23 -
''
' 1066~05
Les verticales gui se trouvent dans la zone droite Zd
sont réparties seulement en deux groupes, bas et haut, suivant
gu'e].les se trouvent ou non en ZH ou ZB : les verticales gui se
trouveraient à droite entre ZH et ZB ne sont pas retenues dans ce
découpage, le paramètre au~uel elles donneraient lieu n'étant pas
nécessaire pour la détermination des 64 caractères alphanumérigues,
seuls considérés icio
Pour simplifier le langage on se réfèrera par la suite
à ces zones par les abréviations définies ci-après, également
utilisées pour les s-ignaux de sortie du circuit de calcul de
zones gui définissent ces zones, les abréviations utilisées étant
choisies en considération des combinaisons logi~ues retenues pour
l'abréviation des signaux de caractérisation des zonesO
Horizontales : H : zone Zh
C : zone Zc
B : zone Zb
Obli~ues : BG : intersection des zones ZB et ZG
BD : intersection des zones ZB et ZD
HG : intersection des zones ZH et ZG
HD: intersection des zones ZH et ZD
CG: intersection des zones ZC et ZG
CD: intersection des zones ZC et ZD
Verticales :. G: zone Zg
D: zone Zd
__
DG: zone Zc2
GoIIG: zone ZgH
G.BG : zone ZgB
D o HD : zone ZdH
D.BD : zone ZdB
Un circuit de calcul de zones dont l'organigramme est
représenté figures 17, 18 et 19, comporte essentiellement,
comme représenté figure 15 :
.
- 24 -
.
1066805
-- un circuit 15a de pro jection de l'ensemble d'adresses des poi~nts
"1" des mémoires moC sur les axes X et Y respectivement; ce
circuit fournit les signaux S1 et S2;
- un circuit 15b qui, à partir de S1 et S2, élabore les signaux
XG, YG, YB, YH, représentatifs des coordonnées de même réfé~
rence, indi~3uées figure 13 et définissant les zones de carac-
térisation des obligues;
- une logigue 15c ~aui élabore, à partir de XG, YG, YB, YH, les
signaux CG, BG, HG, CD, BD, HD, définissant les zones de mêmes
références respectivement;
- des circuits de calcul 15d et 15e élaborant, à partir des si-
gnaux S1 et S2, respectivement les signaux G, D et ~I, C, B;
- le circuit comporte encore 2 circuits, 15f et 15g, de projec-
tion des horizontales sur OY et des verticales sur OX, gui éla-
bGrent les signaux S4 et S3 respectivement slui seront utilisés
pour la caractérisation des horizontales et verticales~
Suivant un exemple préferé de réalisation de l'inven-
tion, représenté figure 16, le circuit de détermination du gabarit
dont l'organigramme est représenté figure 17 comporte deux re-
gistres 15al et 15a2 respectivement pour X et Y à accès parallèles
sur lesguels les 15 informations correspondant aux 15 valeurs de
X et de Y sont aiguillées par l~intermédiaire d~un démultiplexeur
15a3 adressé par Xi ou Yi seLon $1ue la projection est effectuée
sur OX ou OY au moyen d'un multiplexeur 2 voies, 15a4 et par les
mémoires par l'intermédiaire d'un multiplexeur 4 voies~ 15a5. Ce
circuit comporte encore une logigue 15a6 de remise à zéro en fin
de ligne et de colonne.
Les registres sont synchronisés par la logigue de com-
mande L. Le gabarit est connu et matérialisé dans les registres
après deux lectures des mémoires, effectuées pendant les phases
3~3 et ~4 sous le contrôle de la logislue L.
- 25 -
:~066805
Similairement, les circuits i5f et 15g dont l'organi-
gramme est représenté figure 18 sont constitués par des registres
parallèle-parallèle couplés respectivement aux mémoires mH et
par l'intermédiaire du démultiplexeur 15a3 et synchronisés par
les signaux de validation des phases ~4 et ~5 respecti~ement, de
la logi~ue L.
L'organigramme du circuit 15b est représenté figure 19
avec les mêmes symboles gue précédemmentO C10, Cll, etc.O.~ in-
diguent les valeurs de comptage des compteurs de lo, ll, etcOOO
Ce circuit 15b comporte ~uatre compteurs, 15bl et 15b2 pour 10
et 11 respectivement et 15b3, 15b4 pour Lo et L1 respectivement,
une logi~ue, 15b5, de commande des compteurs, trois additionneur~
15b6, 15b7, 15b8, et trois comparateurs 16b9, 15blO, 15bll. Les
opérations effectuées par les additionneurs sont, en fait, en
plus d'additions, des multiplications par 2 et des divisions par
2. Ces opérations étant réalisées par simple décalage dans les
circuits binaires, les circuits sont constitués de simples addi-
tionneurs binairesO
Le fonctionnement de la logi~ue de commande 15b5 est
déterminé pendant le signal de phase ~7; cette logi~ue,
- d'une part autorise sélectivement l'incrémentation des comp-
t-eurs de lo et ll (15b, 15b2) suivant ~u'il y a ou non un
point mémoire 1 à l'adresse X considérée et celle des comp-
teurs de Lo et L1 (15b3, 15b~) suivant la présence ou l'ab-
sence d'un point 1 à l'adresse Y. A cet ef~et, la logi~ue
15b5 reçoit les signaux S2 et S3.
- d'autre part, contrôle en synchronisme les ~aleurs initiales
du compteur 15b4 et de l'additionneur 15b80
En effet, on peut ecrire YB et YH sous la forme
YH = E 2 [2Lo + L1 -~ 6~
YB = E 1 [2Lo + L1 - ~ 6 + ~ 12 ~ + 1
~ a~ec ~ = o si L1 < 10, et ~ = 1 si L1 ~ 10.
- 26 -
~0668~)5
L'additionneur 17b7 étant couplé aux sorties du comp-
teur de Lo (15b3) et du compteur 15b4, la logi~ue 15b5 affiche
au départ 0 ou -6 dans ce dernier suivant la valeur de ~ .
L'additionneur 15b8 effectue la somme dlune ~aleur
interne d'af~ichage a~ec la sortie de l'additionneur 16b7~
La logi~ue 15b5 affiche zéro en 15b8 lors~ue ~ - 0
et +12 si ~= lo
Les comparateurs 15b9, 15b 10 et 15bll ~ui reçoi~ent
respectivement les signaux ~ 2 ~ L_ . ~-- -- -2~
2Lo + 21 + ~ 6 des calculateurs 15b7~ 15b8 et 15b9, fournis-
sent les parties entières utiles représentées par les signaux
XG, XD, YB, YHo La logi~ue 15c d'élaboration des zones d'affec-
: tation des obli~ues fournit les signaux :
~ CG = XG~YBoYH
CD = XDoYB~YH
HG = XG. YB
BD = XDoYB
- HG = XG~ YH
HD = XD.YH
Les circuits 15d, 15e, d'élaboration des signaux H~ C~
B, G et D, opèrent plus simplement à partir des projections des
gabarits retardées et avancées des deux unités d'horlogeO Ces
circuits 15dl, 15el, comportent chacun une double bascule et un
circuit Non-ET, i5d2, 15e27 afin de fournir directement les si.-
gnaux D~ G, H7 C~ B, plus prati~ues ~ue les signaux directs pour
la réalisation du circuit de caractérisation du graphisme, dont
un exemple préféré suivant l'invention est illustré.
Le principe de la caractérisation de graphisme est
simple : il consiste essentiellement à tester l'existence des
divers segments dans les zones définies précédemntentO
- 27 _
: 1066805
Par exemple
Y YH X = XG
~ ~ ~ mD (X, Y) = 1
Y = 1 X = 1
indigue gu'il existe au moins une obligue à pente positive en
bas et à gauche du graphisme.
On définit ainsi 21 tests dont la réponse positive
- (~ i = 1, où i = 1 à 21) dénote l'existence de segments confor-
mément aux schémas des figures 3a à 3d.
La figure 20 est le schéma de principe d'un circuit
de caractérisation du graphisme le plus géneral utilisable guels
gue soient les nombres des zones définies sur cette figure, 15
représente globalement le circuit de calcul de zones et Zi les
signaux caractérisant les diverses zones, le signal Zij d'une
zone étant simple (une seule adresse ou coordonnée) ou double
suivant gu'il s'agit d'une des zones telles gue ~, B, C ou des
zones telles gue BG, BD, etcO..; pour la zone HG précisément,
Zij comporte les signaux YH et XG.
Sur la figure, pour généraliser, on a désigné par :
Ziv les zones d'affectation des verticales et plus généralement
i ~ nombre de zones d'affectation des verticales;
ZjH les zones d'affectation des horizontales;
Zkd les zones d'affecta~ion des obli~ues à droite;
Zld les zones d~affectation des obligues à gaucheO
Dans le cas des caractères alphanumérigues :
Zkd = Zld avec k = 1 ~ 6; et i = 6 et j = 3.
Les adresses des points 1 des mémoires sont comparées
respectivement en 20A, 20B, 20C, 20D, avec les signaux ZiV,
ZiH, Zkg et Zld, chague comparaison déterminant les variables
correspondantes, soit ~jH pour les horizontales, ~iV pour les
verticales, etc.... avec ~ld = 91 à ~6, ~kg = 07 à ~12,
~jH = ~17 à ~19 et ~iv = ~13 à Bl6 et ~20, ~21, dans
- 28 _
1~66805
l'exemple con~idéré précédemmentO
La figure 21 est un exemple préféré de circuit de
caractérisation suivant l'invention, la figure 22 étant l'orga-
nigramme d'affectation mis en oeuvre dans le circuit de la figure
21; dans ce cas les zones Zkg et Zld sont identi~ues, les hori-
zontales sont caractérisées uniguement par leur adresse Y et
les signaux de caractérisation de zones sont les signaux dis-
ponibles aux sorties du circuit de la figure 16, à savoir, pour
rappel : CG, CD, BG, BD, HG, HD, H, C, B, D et G, et où on dis-
pose en S3 et S4 des projections S3 et S4 des verticales sur 0X
et des horizontales sur OYO
Le circuit de la figure 21 est réalisé en logi~ue né-
gative, la technologie de ces circuits étant plus simple gue
celle des circuits logigues directs. Pour faciliter la compré-
hension de fonctionnement de ces circuits, on rappelle gue, les
paramètres a, b, c~ représentant des variables guelcongues,
a ~ b ~ c = a b c, les sommes et produits étant bien entendu
des sommes et produits logigues.
Dans ces conditions, les divers circuits logigues
traduisent bien l'intersection des adresses des points mémoire
m~ "1" a~ec celles des zones considérées.
Un signal de zone surmonté d'une barre indigue gue 1'~
on considère les points de mémoires m~ dont les adresses sont
extérieures à celles des limites des zones considérées.
Les signaux de sortie des circuits logigues de compa-
raison 20 à 20 ~ chargent 5 registres parallèle-parallèle 31 à
35, servant de mémoire, dont les sorties sont synchronisées par
la logigue de commande L.
Les paramètres ~ 1 à ~ 12 (obligues gauche et droite)
sont directement déterminés par les circuits logi~ues 20a à 201.
- 29 _
~()66805
Les par~mètres ~17, ~18~ ~19 thorizontales)
ainsi gue le paramètre ~ 21 (verticale au centre), sont égale-
ment directement déterminés par les circuits logigues 20t, 20u,
20v et 20~.
Pour la détermination des paramètres ~13 à ~16, si~-
paramètres intermédiaires, ~ 1 à ~ 6 sont respectivement éla-
borés, dans les circuits Non-OU 20s, 20r, 20m, 20n, 20O et 20p
avec les relations suivantes : ~ 1 = S30D
Z 2 = S3~G
t 3 = mv.BG
~ ~4 = mv.BD
~ t5 = mvOHG
Z6 = mvOHD
Quatre portes ET sont couplées aux sorties des regis-
tres 34 et 35 sur lesguelles sont transférés les paramètres ~ 1
~ J à ~ 6 de facon à fournir les paramètres :
~ ~13 = ~ 4O ~ 1 = mv D.BD
~14 = t 6. ~ 1 = mv D.HD
~15 = ~ 3. ~ 2 = mv G.BG
~16 = Z 5. Z 2 = mv GoHG
(dans les relations précédentes, on a éliminé S3 puisgue l'adres~
se X des verticales est comprise dans l~ensemble des adresqes X,
Y de celles-ci)O
A la fin de la phase ~8~ les 21 variables ~i sont
~~ déterminées et la logigue de commande envoie le signal ~9 de
validation des circuits de décodage, dernière étape du procédé
de reconnaissance.
Cette dernière étape, c'est-à-dire la reconnaissance
proprement dite, consituée par le décodage des variables ~i,
sera plus ou moins complexe selon la nature et le nombre de
graphismes susceptibles d'etre reconnus, c'est-à-dire encore
: - 3~ -
~: 1066~305
suivant le nombre de combinaisons des variables ~ i nécessaires
à l'identification d~un caractère, en tenant compte des diverses
variantes possibles de l'e~semble des points M(xy) d'un même
caractère, dues en particulier aux effets de phase au cours de
l'échantillonnage, c'est-à-dire aux effets parasites de la
guanti~ication.
Le circuit de la figure 23 réalise en logi~ue en majo-
rité négative le circuit de décodage des 10 chiffres O à 9.
Le décodeur réçoit sur ses 21 entrées respectivement
les 21 variables binaires 01 à ~21 et ~ournit, sur 10 sorties,
10 variables binaires s'excluant mutuellement, notées 0, 1, 2~o~
90 Ces variables peuvent être appliguées à tout système d'utili-
sation à entrées binaires, par exemple elles peuvent être utili-
sées pour exciter un dispositif d'affichage décimal constitué
par des tubes Nixie.
Le principe de ce décodage est valable pour le déco-
dage de l'ensemble des caractères alphanumérigues~ C'est un
décodage hiérarchisé basé sur la signification ph~sigue des
variables.
ZO Pour les chiffres 5, 6, 8, 9, O, il a été trouvé
avantageux d'élaborer 6 variables intermédiaires al, a2, a3, a4
et ~ 1, ~2, dont la valeur 1 dénote l'existence de courbes de
forme et de situation telles gue représentées aux figures 24a et
24b avec les mêmes références, les courbes al à a4 étant des
courbes relativement fermées et les courbes ~ 1, q 2 des courbes
très ouvertes. Les chiffres 1, 2, 3, 4 et 7 sont décodés essen-
tiellement à partir des variables ~ i, les variables al à a4,
~ 1 à ~2 n'intervenant ~ue pour exclusive.
- 31 -
-
~06~805
Les combinaisons logigues caractérisant les chiffres 0
à 9 et mises en oeuvre dans le circuit de la figure 23~ sont ré-
capitulées au tableau de la figure 25.
En clair, la reconnaissance respecti~e des divers
chiffres est déterminée par la présence ou l'absence des seg-
; ments et courbes indigués ci-après par la référence du paramètre
correspondant.
Chiffre 0 : - présence de ~ 1 et ~ 2
- absence de 0 1, ~ 4, ~ 8~ ~9, ~ 19
- absence de la combinaison déterminant le chiffre 8
- absence de l'un au moins parmi ~5 et ~6
Chiffre i : - présence de ~13 et ~14
- absence de a4~ ~7~ ~15, ~16
- absence des combinaisons correspondant aux chiffres
5, 6, 8 et 9
Chiffre 2 : - Présence de ~18
- Présence de l'un au moins parmi ~4, ~5, ~6
- Absence de ~ 12, ~ 13, ~14
- Absence des combinaisons définissant les chiffres
5, 6, 8 et 9
Chiffre 3 : - présence de a4
- présence de l'un au moins parmi a3, ~4~ ~17 et/
ou de l'ensemble ~9, ~10
- absence de al~ a2, ~15, ~16, 019
Chiffre 4 : - présence de ~ 5
- présence de l'un au moins parmi ~13 et B20
- présence de l'un au moins parmi ~11, ~12, ~19
- absence de ~14, ~15, ~17
- absence des combinaisons correspondant aux chiffres
3~ 5, 6, 8 et 9
32
1066805
Chif~re 5 : - présence de a4
- présence de l'un au moins parmi al et ~16
- absence de a3, ~ 5~ ~8~ ~14, ~15
Chiffre 6 : - presence de a2
- présence de l'un au moins parmi 21 et 15
- absence de ~ 6, ~10, ~ 14, al, a3
Chiffre 7 : - présence de ~ 17
- présence d'au moins l'un parmi ~ 4, ~5, ~6
- absence de a4, B 12, ~13, ~ 18, ~ 19 et
des combinaisons définissant les chiffres 5 7 6
8 et 9
Chiffre 8 : - présence de~ 1, a2, a4
Chiffre 9 : - présence de al et/ou de l'ensemble ~ 16
- présence de a3 et/ou de l'ensemble ~ 6
- absence de a2 et a4
Les arcs al, a2, a3, a4, ~ 1 et ~ 2 étant caracté-
risés respecti~ement par :
al : présence simultanée d'au moins l'un des groupes ~3 et
~ 3, ~16 et ~ 19 ~ 16 et ~17 - ~ 16
~17 et ~ 19
a2 : présence simultanée des paramètres d'au moins l'un des
groupes : ~ 5 et ~ 7 - ~5~ ~ 15~ ~18 - ~7~ ~15 et
~19 - ~ 15~ ~18 et ~ 19
a3 : présence simultanée d'au moins l'un des groupes ~ 4, ~17,
~ 19 - ~ 10, ~14, ~19 - ~ 14, ~17, ~6 et B6, ~lo
a4 : présence simultanée des paramètres d'au moins l'un des
~ groupes ~2, ~12 - ~13, ~18 et ~ 19 - ~2, ~ 13 et ~19-
12, ~13 et ~18
~ 1 : présence simultanée des paramètres d'au moins l'un des
groupes ~ 3, ~ 10 - ~17~ ~3 et ~ 14 - ~ 17, ~14 et ~16 ~
~ 17, ~16 et ~ 10.
2 : présence simultanée des paramètres d'au moins l'un des
:~ .
- 33 -
~066~3~5
groupes ~2, ~7 - ~18, ~?15 et ~2 - ~18, ~15 et ~13_
18, ~ 13 et ~ 7.
Les circuits de séparation et affectation des segments
de caractérisation du graphisme par zones de localisation des
segments et de décodage précédemment décrits constituent les
éléments essentiels de l'in~ention. Leur mise en oeuvre met en
jeu des circuits auxiliaires, représentés en 52, 54 et L,
figure 5, c'est-à-dire des générateurs d'adresses pour les mé-
moires M et m~ , et une logi~ue de commande générale dont le rôle
est d'assurer l'automatisme du fonctionnement du système tout en
synchronisant les di~erses opérations de fac~on telle gu'elles
soient réparties dans le temps avec un décalage à la fois suf-
fisant pour é~iter gue la commutation d'un circuit introduise
des signaux parasites dans un autre circuit, donnant lieu à des
informations fausses, et aussi court ~ue le permettent les ca--
. .
ractéristi~ues des composants utilisésO
Les générateurs d'adresses et la logi~ue de commandesont entièrement définis par leurs fonctions et pourront être
réalisés suivant les techni~ues courantes utilisées en informa-
..,
tigue.
Les figures 26 et 27 sont desschémas synopti~ues d'-
exemples préférés de ces générateurs, particulièrement adaptés
à la mise en oeuvre des organigrammes des figures 9~ 10 d'une
part, et 11 d'autre part; la figure Z8 est le schéma de prin-
~ cipe d'un exemple préféré de logi~ue de commande.
; Le générateur d'adresses M représenté à la figure 26
a pour fonctions :
- d'effectuer l'adressage de la mémoire M pour la mise en oeu~re
des circuits d'extraction des segments,
- de transmettre un adressage extérieur lors du chargement de
cette mémoire.
- .3
1066805
Ce générateur doit donc élaborer les huit couples d'-
adresses x = Y + n ; y = Y + p
x = X + n ; y = Y - (1 + p), etc~..
définies précédemment pour le calcul des intégrales Iv, IH,
IG, ID.
Les grandeurs x, y, n et p sont disponibles respecti-
vement aux sorties des compteurs 201, 210, 206 et 208 dont l'-
incrémentation et la remise à valeur initiale (zéro pour le
compteur de n, 208~ et n pour le compteur de p, 206) sont régies
par la logi~ue L, selon le résultat des tests de dépassement ef-
fectués sur les adresses par une logi~ue 207, d'élaboration de
ces tests ~ui compare les dernières valeurs de x et y obtenues
aux valeurs limite 0 et 16. La logi~ue 207 reçoit les valeurs n
~ et p des compteurs 206 et 20~ et les indications de retenues c4,
c'4 des additionneurs 202, 211. Elle élabore les signaux Depx+,
~: Depy+, Depx , Depy et les signaux T0, Tl, T2, T3 et T4 définis
; sur l'organigramme 9.
:i A la figure 26, EX, EY, Zp, En, désignent les signaux
~............ d'incrémentation respectifs des compteurs et Ra indi~ue le si-
gnal de remise à valeur initiale de la variable indi~uée.
Les nouvelles adresses x et y sont élaborées à cha~ue
instant à partir des valeurs précédentes de X et ~, par addition
ou soustraction en 202 et 211 et multiplexage de n et p en 204
et 211 selon les ordres recus de la logi~ue L conformément à
l'organigramme de la figure 10.
Un multiplexage final, respectivement en 203 et 212,
permet d'adresser la mémoire soit par les grandeurs de sorties
des circuits 202 et 211 soit par les adresses Aiw provenant du
système d'acguisition; Adi représente une adresse x, y guelcon~ue
de la mémoire M.
- 35 -
'~
1066805
Le générateur d'adresse m doit fournir : l'adresse (X,
Y) du point m (X, Y) (figure 1) pour la mise en mémoire du point
et les adresses : X + 1, Y ; X - 1, Y ; X, Y - 1 ; X, Y + 1
pour la confirmation des points dans les mémoires mH et mv,
les adresses : X + 1, Y ~ 1; X - 1, Y - 1; X + 1, Y - 1, X 1,
Y + 1, pour la confirmation des points dans les mémoires mG et mD.
. Ces adresses sont élaborées à partir de X et Y fournies
: par les compteurs 201 et 210 (communs aux générateurs d'adresses
m et M) par addition et soustraction de 1 ou 0 par les circuits
302 et 303. Les opérations sont synchronisées par les logicues
de commande 305 et 306, elles-mêmes régies par un compteur 301 à
5 états, selon l'organigramme de la figure 11. Ce compteur est
au repos à l'état 4 pour leguel les adresses de sorties Xdi et
: Ydi sont égales à X et Y.
. Une logigue de validation de points mémoire, 304, as-
signella valeur 0 aux points dont l'adresse les situe en dehors
des mémoires mO
La logigue de commande L assure le déroulement succes-
sif des opérations précédemment décrites suivant les dix phases
~0 à ~9, pour mémoire :
- trois phases ~0, ~ 2 pour la séparation des segments;
- cing phases ~3 à ~7 pour le calcul des zones;
.' - une phase ~8 pour la caractérisation du graphisme;
- une phase ~9 pour le décodage.
Elle est entièrement définie par ses fonctions gui sont
la génération des divers signaux de commande des divers proces-
seurs décrits, à savoir :
ordres d'incrémentation des adresses pour élaboration des adres-
ses dans le générateur d'adresses M (figure 26) : ordres EX, EY,
: 30 Ep, En;
' ordres de commande am, bm, cm, des circuits du générateur d'a-
dresses M;
- 36 -
~066805
ordres de remise à valeur lnitiale de ces adresses : RaX, RaY,
Ran (l'ordre Rap étant identi~ue à En puisgue p ~ n);
ordres dlécriture des registres mémoires 63, 64 du processeur de
séparation des segments (figure 6) : hr ~ fF~ hV et leurs remi-
ses à zéro RaOH, RaoQi;
ordres d'écriture des mémoires M : WM;
: ordres d'écriture des mémoires m ~;
ordres d'écriture des mémoires de projection du processeur de
calcul de zones (figure 16) : PEl - PE2 - PE3 - PE4 - ;
ordres d'écriture des mémoires de test du processeur de carac-
térisation de graphisme (figure 21) : PETl, PET2;
signaux de validation des diverses phases opératoires. Ces si-
gnaux sont désignés par les memes références ~0 .Ø ~9 gue les
phases gu'ils définissentO
La logigue L comporte également des circuits d'initia-
lisation gui concourent à l'élaboration des ordres d'écriture WM
de la mémoire ~ et à la remise à zéro de l'ensemble des compteurs
et mémoires, en fonction des informations reçues du système d'ac-
guisition.
~ 20 Tous ces ordres sont élaborés conformément aux organi-
grammes des figures 7, 9 à 11, 17 à 19, et 22. Les figures 29
à 33 montrent~ en fonction du temps~ les principaux signaux
élaborés, et la figure 28 est un schéma synoptigue simplifié
d'une logigue de commande Lo
Elle comprend essentiellement :
- une horloge mère H fournissant le signal d'horloge h;
- un compteur ADM à 12 états, un compteur de phase ~ et des cir-
cuits logigues combinatoires LC élaborant les divers ordres de
contrôle hf, fro, hi, am, bm, cm, W, conformément aux divers
organigrammes, ceci à partir de l'état des compteurs d'une
- part, et de la valeur des variables caractérisant les tests
~066805
réalisés par les processeurs (DepX, DepY, T1, T2, T3, T~);
- un dispositi~ R recevant les informations fournies par le sys-
tème d'ac~uisition; signal FE de fin d'écriture coincidant
- avec la retombée de A7W, dernier des 8 bits d'écriture Ao7 à
A7W -
Dès l'apparition de FE~ ce dispositif émet en synchro-
nisme avec h un signal de commande Cde ~ui provo~ue la transmis-
sion des données de la mémoire du s~stème d'ac~uisition avec
celle, M, du système de reconnaissance. La transmission est ter-
minée lorsgue le bit d'adresse d'écriture A7W (2e bit ~7W sur la
figure, le ler correspondant à l'écriture dans le système d'ac-
~uisition) repasse à l'état zéro.
Sur le diagramme on a encore représenté
- les signaux Q2 et Q3, définis à partir de FE et AiW ~ui servent
à élaborer le signal Cde;
- le signal W (figure 26) gui aiguille sur l'entrée de la mémoire
M soit les adresses AiW du système d'ac~uisition soit celles
générées par le processeur d'adresses du système de reconnais-
sance;
- le signal WM d'écriture de la mémoire M ~ui apparaît à la fin
de la première impulsion d'horloge suivant le signal Cde et se
termine avec la fin du dernier bit d'écriture dans M~ A7w; et
- le signal RAZ de remise à zéro générale ~ui colncide avec la
fin de WM et dure une impulsion d'horloge~
Les états du compteur ADM sont représentés sur le dia-
- gramme de la figure 30 où l'on voit les divers signaux de com-
mande du générateur d'adresses M de la ~igure 26, et les valeurs
des adresses correspondantes.
- les signaux am et bm, ou commandes d'opérateurs pour y et x,
~ui déterminent si l'opération est -~n ou +p d'une part, ou
~(n + 1) ou -(p + 1)
- 38 -
~0~;68()5
- le signal cm, o~ commando d'opérande de l'adresse x, Y;
- - le signal hr gui synchronise le chargement des registres.
Sur ce diagramme, on a encore indi~ué en ~ 1' la mise en
place des sémaphores si n ~ 0, ou la mise en mémoire des valida-
tions si n = 0.
en ~ 2 l'incrémentation des compteurs d'intégrales Tv7 6H~ 6G~ 6D;
en a 3 l'incrémentation des compteurs de p, (Ep ~ et la mise
en mémoire des Qi;
en ~ 4 l'incrémentation du compteur de n et la remise à zéro des
Qi, et la remise à zéro des sémaphores Fi;
en ~ 7 la phase d'affectation d'un point à une mémoire m~;
en ~ 8 l'incrémentation de X ou Y et la remise à zéro des comp-
teurs 6v, 6~, 6H~ 6~-
Les états du compteur à 5 états, 3017 du générateur d'-
adresses à 4 états, M, et ses trois bits QA, QB, QC' synchronisés
. par h, sont représentés à la figure 31 où l'on voit les divers
signaux de commande du générateur d'adresses m de la figure 27 et
;~ les valeurs des adresses correspondantes.
. - signaux ~X et ~ X de la logigue de commande de calcul de 1'-
adresse X (figure 27) respectivement commande d'opérande et
commande opérateur de l'adresse X.
- et signaux ~ X et ~'~, respectivement de même rôles~ pour
~ l'adresse Y.
Les signaux de commande du processeur de calcul de
zones sont représentés aux figures 32 et 33~ avec des échelles
. différentes pour la clarté de celles-ci.
La vitesse de fonctionnement du dispositif suivant 1'-
invention est essentiellement limitee par le temps d'accès aux
mémoires, le temps de propagation au niveau de la logi~ue n'in-
tervenant ~u'au second ordre, les circuits utilisés étant réa-
lisés de préférence en technologie de type TTL. Dans un dispositif
- 39 -
-'
1066805
suivant l'invention, réalisé avec les matériels décrits ci-après,
la fré~uence d'horloge est de l'ordre de 5 Mc/s, ce gui permet la
reconnaissance d'un caractère alphanumérigue en 5,3 ms au maximum,
dont 4,5 ms environ sont utilisées pour l'extraction des segments.
Ce temps peut être diminué au prix d'une augmentation du matériel
en substituant à la mémoire M plusieurs sous-mémoires gui se-
raient explorées simultanémentO
Exemple de types de matériels utilisés dans un circuit
réalisé suivant l'invention :
- tous les circuits logigues sont réalisés en technologie TTL
Schottky essentiellement négative;
- mémoires M et md Intersil MM5523 et matériels Texas Instru-
ments;
- registres série-parallèle 8 bits (61, figure 6, 213, figure 26)
SN 74 164 (Texas Instruments);
- guadruples bascules D avec remise à zéro (63 et 64, figure 6):
: SN 74-175;
- compteurs 4 bits entièrement synchrones (6v, 6H~ 6G~ 6
figure 6 - 206, 108, figure 26 - 301, figure 27 et ADM,
figure 28) : SN 74-~63;
- comparateurs 4 bits cascadables (60, figure 6 ; 15b9~ 10, 11,
~igure 6 ; 202, figure 26) : SN 7l~-85 ;
- guadruples multiplexeurs 2 ~oies (15a4, figure 16 et 203, 204,
209, 212, figure 26) : SN 74-157 ;
- démultiplexeurs 1-16 voies (15a3, figure 15) : SN 76-154 ;
- doubles multiplexeurs 2 ~oies (15a6, figure 15) : SN 74-153 ;
- compteurs synchrones 4 bits avec chargement (15bl, 2, 3, 4~
figure 16 - 201 et 210~ figure 26 - 0, figure 28) : SN 74-161 ;
- registres 5 bits entrée et sortie en parallèle (15al~ 15a2,
15f, 15g) : SN 74-96 ;
- addition~eurs 4 bits (15b6, 7, 8, figure 1; 202, 205, 211,
figure 26 - 302, 303, figure 27) : SN 74~83 ;
_ 40 -
106680S
- doubles bascules D (15b5, 15d, 15e, figure 16 et 3 moitiés de
ces bascules en R, figure 28) SN 74-74~
L'in~ention n'est pas limitée aux exemples de réali-
sation et d'utilisation décrits uniguement à titre d'illustration.
Plus généralement, le procédé de reconnaissance de formes sui-
vant l'invention est applicable guel gue soit le procédé d'ac-
guisition de celles-ci pour autant gue l'on dispose, au départ,
d'un ensemble de données binaires correspondant à des surfaces
élémentaires dé~inissant le graphisme. Bien gue, pour fixer les
idées~ ce procédé ait été décrit dans le cadre de son application
- au cas des caractères acguis par balayage suivant des coordon-
nées cartésiennes, il est applicable guel gue soit le système de
coordonnées choisies, les circuits particuliers décrits à titre
d'exemples étant utilisables encore à condition d'y associer
des transformateurs de coordonnées; d'autres circuits, réalisés
pour fonctionner directement à partir des coordonnées utilisées
pour le balayage, pourront aussi être utilisés~
Le procédé de l'invention gui consiste essentiellement
en la caractérisation du graphisme par son orientation en un
nombre limité de zones a été exposé dans le cas où on ne dis-
tingue gue 4 types d'orientation suivant une horizontale~ sui-
vant une verticale, suivant une obligue à pente position dite
"droite~' et suivant une obligue à pente négative dite "gauche",
sans distinction de la pente de ces obligues; en effet, il a été
remargué gue pour reconnaître les 64 caractères alphanuméri~ues
courants, il est inutile de distinguer les unes des autres les
obligues de même orientation généraleO Cependant, le procédé
suivant l'invention peut être mis en oeuvre en distinguant les
pentes des obligues, notamment dans le cas où il serait utilisé
pour la reconnaissance de caractères plus comple~es. Le principe
des circuits décrits reste entièrement applicable~ le nombre des
:
_ 41 -
- :1066805
mémoires intermédiaires m~ étant evidemment égal au nombre de
types de segments distincts.
Enfin~ on remar~uera ~ue les directions horizontale
et verticale ont été retenues uni~uement pour la commodité de
leur détermination, ces directions correspondant à la fois à des
directions préférentielles d'un grand nombre de caracteres cou-
rants et aux directions de balayage usuels, mais on peut choisir
à priori des directions différentes sans sortir du cadre de 1'-
invention.
, 10
- 42 -
