DISPOSITIF POUR L'ESTIMATION DE CONTOURS D'IMAGES ET APPLICATION AU CODAGE DE SIGNAUX DE TELEVISION.

La présente invention a pour objet un dispo¬ sitif pour l'estimation de contours d'images et une application au codage de signaux de télévision.

Le codage utilisant la modulation d'impul¬ sions codées différentielles (en abrégé MICD, ou en anglais DPCM)- a déjà fait l'objet de nombreuses études publiées notamment dans les articles suivants : - "Prédictive Quantizing Systems (Differential Puise Code Modulation) for the Transmission of Télévision Signais" par J.B. O'Neal, paru dans la revue améri¬ caine "Bell System Technical Journal", vol. 45, pa¬ ges 689 à 721, mai 1966, - "Système de codage numérique de l'image de télévi¬ sion le projet OCCITAN" par J. PONCIN et J. SABATIΞR, paru dans la revue française "L'écho des recherches", janvier 1976, pages 28 à 37,

- "Dégradation des signaux d'images et qualité subjec- tive en codage numérique : visibilité du flottement dé contour" par F. KRETZ et J.L. BOUDEVILLE, paru dans la revue française "Annales des Télécommunica¬ tions", tome 31, n° 9-10, septembre-octobre 1976.

Dans le codage MICD, on code la différence entre la valeur réelle d'un échantillon de signal de télévision et une prédiction (estimation) de cette va¬ leur calculée a partir d'échantillons codés voisins antérieurs. Cette différence est quantifiée et codée. La caractéristique de quantification a fait l'objet de nombreuses études. Classiquement, elle est unique et symétrique par rapport à la valeur O, mais d'autres types de quantification ont été envisagés, qui sont décrits par exemple dans les documents suivants :

- Brevet français PV 77 26773, "Compression et expan- sion (quantification) de signaux numériques de télé¬ vision à codage différentiel", inventeurs MM. F. KRETZ et J.L. BOUDEVILLE,

- "Optimization of DPCM video sche e using subjective quality criterions", par F. KRETZ, J.L. BOUDEVILLE et P. SALLIO, paru dans les comptes-rendus "1ERE Conférence", n° 37, septembre 1977, pages 185-194, - Premier certificat d'addition au brevet PV 77 26773 cité ci-dessus ; PV 78 35485, inventeurs MM. F. KRETZ et J.L. BOUDEVILLE,

- "Ein DPCM. - System mit z eidimensionalen Pradictor und gesteuertem Quantisierer", par T. KUMMΞROW, paru dans les comptes-rendus "TAGUNGSBERICHT J3TG- FACHTAGϋNG : Signal erarbeitung" avril 1973, ERLANGEN, pages 425-439,

- "Adaptive Quantization of Picture Signais using Spa¬ tial Masking", par A. NETRAVALI et B. PRAVADA, paru dans la revue américaine "Proceedings of IEEE", avril 1977, pages 536-548.

En ce qui concerne la transmission numérique d'un signal de télévision, l'Union Européenne de Ra¬ diodiffusion a prévu d'utiliser un système de trans- mission normalisé par le CCITT à un débit de 34 Meb/s. On a pu réaliser un tel système- en codant séparément les composantes ^* et en utilisant l'invention décrite dans le premier additif au brevet mentionné ci-dessus, pour le codage du signal de luminance. On a ainsi ob- tenu une bonne qualité des images restituées.

Pour cette application, il est utile d'es¬ sayer d'améliorer encore la qualité obtenue, par un codage plus complexe. Pour d'autres applications, il peut être utile de diminuer le débit à la valeur mini- maie possible selon les méthodes classiques, en con¬ servant une qualité donnée.

Plusieurs études ont été menées dans ce but, conduisant à une prédiction adaptative. On peut citer par exemple les articles suivants : - "Prédictive Quantizing of Télévision signais" par

R.E. GRAHAM, paru dans les comptes-rendus de "IRE

- ^~ ξ\ ?y ]

OxMPI v W ^* fe, IPO ⁿ

Wescon Convention record", volume 2, partie 4, 1958, pages 147 à 157, - "DPCM Picture Coding ith Adaptive Prédiction" par . ZSCHUNKE, paru dans la revue américaine "IEEE Tr. on Corn.", volume COM 25, n° 11, novembre 1977, pages 1295 à 1302.

Dans ces études, la prédiction est sélec¬ tionnée parmi plusieurs prédictions, chacune corres¬ pondant à la valeur d'un point voisin antérieur du point à coder ou à une combinaison linéaire simple des valeurs de points voisins antérieurs du point à coder. Chaque prédiction est adaptée à une orientation locale donnée de l'image (c'est-à-dire au cas d'un contour de cette orientation passant à proximité du point à co- der) . Un organe de décision estime l'orientation loca¬ le et choisit en conséquence la prédiction appropriée. Les deux dernières études citées ci-dessus utilisent des estimations basées sur des tests simples sur les différences entre points voisins antérieurs au point à coder.

L'invention porte avant tout sur le suivi et l'estimation recursive de l'état local des contours d'une image, que celle-ci soit, ou non, une image de télévision. L'invention porte également sur l'utili- sation du suivi et de l'estimation pour la prédiction adaptative des contours d'une image.

Un des buts visés par la présente invention est donc l'amélioration de l'estimation de l'orienta¬ tion locale pour accroître la qualité des images de télévision restituées après un codage numérique à un débit de 34 Meb/s. Un autre but de la présente inven¬ tion est l'utilisation du même principe pour diminuer le débit de systèmes de transmission numérique d'ima¬ ges, en conservant à ces images une qualité adéquate.

Avant de définir l'invention, quelques dé¬ finitions seront données à propos de notions et de grandeurs relatives aux images traitées.

L'invention s'applique essentiellement aux images formées de lignes de points équidistants dispo¬ sés aux centres de rectangles formés par un double faisceau de lignes orthogonales, répartition qui est classiquement dénommée "structure d'échantillonnage orthogonale". L'invention s'applique également au cas d'une "structure d'échantillonnage en quinconce-tra¬ me" (voir l'article de J. SABATIER et F. KRETZ intitu¬ lé : "L'échantillonnage des composantes du signal de télévision en couleur à 625 lignes" ("Sampling the components of 625-line colour télévision signais") pu- blié dans la revue technique de l'UER n° 171, oct. 1978, p. 212 à 225). La figure la illustre cette structure. Toutes les lignes de points sont supposées contenir N points, qui seront, dans le cas de l'appli¬ cation aux images de télévision, les N points formant une ligne du signal vidéo, le nombre de lignes dépen¬ dant du standard adopté. Chaque point de la ligne est caractérisé par une grandeur optique, soit la luminan¬ ce, soit la chromaticité, soit tout autre signal de ce genre (par exemple le signal de luminance ou les si- gnaux de différence) « Cette grandeur est déterminée par un signal électrique échantillonné noté X avec différents indices ou accents.

Lorsque deux points adjacents présentent une différence d'amplitude qui excède un certain seuil, on observe un "élément de contour d'image", cet élément étant horizontal si les deux points sont l'un au-dessus de l'autre et vertical si les deux points sont l'un à côté de l'autre. Chaque élément de contour sera représenté, comme sur la figure la, par un trait disposé entre les deux points en question et sera noté EH pour les premiers et EV pour les seconds.

OMPI

Deux éléments de contour, horizontaux ou verticaux, sont dits connexes si deux de leurs extré¬ mités sont connectées. On définit alors un contour par un ensemble d'éléments de contour connexes, ou par l'ensemble des points qui leur sont adjacents. La courbe moyenne du contour représente en quelque sorte le lieu des points de même amplitude, par exemple de même intensité lumineuse. Le contour représenté à titre d'exemple sur la figure la comprend 6 éléments de contour verticaux et 4 éléments de contour horizon¬ taux.

Un tel contour présente en tout point une orientation moyenne qui est donnée par la tangente à la courbe moyenne du contour. Cette orientation sera prise par rapport à la verticale et notée θ . Un des objets de l'invention concerne l'estimation de cette orientation à chaque ligne.

Naturellement, tous les éléments de contour d'une image ne sont pas nécessairement connexes et certains peuvent être isolés. Dans le suivi de ligne à ligne des contours et leur observation à chaque ligne, on s'intéressera aux éléments de contour appartenant à une même ligne et qui sont connexes. De tels éléments forment des ensembles dénommés "zones connexes" ou "connexités". La figure la représente une telle con- nexité, considérée comme partie intégrante d'un con¬ tour. Elle commence par un premier élément de contour (dans le cas illustré, il s'agit d'un élément horizon¬ tal) et -se termine par un dernier élément de contour (en l'occurrence, un élément de contour vertical). Ce dernier élément indique la fin d'une zone connexe. Un point de l'image peut appartenir à une connexité. Dans le cas contraire, il est situé dans un "trou".

A la ligne courante, le "passé" du contour observé est résumé par certaines grandeurs nécessaires

au suivi du contour et à l'estimation de l'orientation locale. L'ensemble de ces grandeurs constitue "l'état" du contour et est noté E. Elles sont : H et V : les nombres moyens d'éléments de contour respectivement horizontaux et verticaux, filtrés récursivement au cours du suivi du contour, NM : le nombre de marches précédentes observées au cours du suivi du contour, NP : le nombre d'éléments de contour verticaux connexes, mais non connexes à des éléments de contour horizontaux, observés aux lignes précédant la ligne en cours de traitement, NS : la somme partielle des signes observés, S, au cours du suivi du contour ; on distingue¬ ra sa valeur absolue, JNSJ, et son signe. S, dit signe du contour, Q : qui comptabilise les inversions du signe ob¬ servé (S. S ^ O) en vue d'un test de rupture du suivi du contour.

Dans certains cas, deux (ou plus de deux) contours peuvent se croiser _ρour former une figure que l'on dénommera "fourche". Les deux contours formant une fourche possèdent chacun un état (E ^* et E ) dont on peut extraire au point d'intersection un état qui sera dit "interpolé" et noté E.

L'examen d'une image s'effectue, comme dans le balayage des images de télévision ligne par ligne et point par point. La figure lb montre la répartition géométri¬ que du point courant et des points voisins antérieurs et la figure le la convention angulaire utilisée pour les orientations (θ de -τ_/2 à +π/2, θ ^ O sur la figu¬ re) et leur discrétisation. A la figure lb, on a représenté la position des divers points qui seront utilisés avec les nota-

O FI

tion utilisées : X pour les valeurs à coder, X pour les valeurs décodées.; l'indice prime dans X', désigne les points de la ligne précédente et désignera, en général, les signaux portant des informations corres¬ pondant ^* à la ligne précédente. A la ligne courante, on considère le point courant à l'instant n, (X ) ou à l'instant n+1, (X ,) dans certains cas, pour que le dernier point décodé soit Xn.

A la figure le, on a représenté la conven- tion angulaire (θ est pr.is par rapport à la verticale, positif sur la figure) ainsi que la discrétisation des angles qui, dans l'exemple de réalisation (tableau

Vl-a) , comporte 3eb de module et leb de signe. Sur la figure, le contour ^* suivi au point de rang n-J a une orientation estimée θ, de valeur discrétisée +1. La prédiction est préparée à la ligne courante, pour la ligne suivante en calculant une combinaison linéaire définie par θ, des valeurs de Xn—J, et de X„n-J_+.i, qui concernera un point défini par θ à la ligne suivante. Ces précisions sur la terminologie employée étant données, l'invention prévoit un suivi des con-. tours et une estimation recursive de leur état E qui contient plusieurs paramètres significatifs du con¬ tour et dont on extraira une estimation de l'orienta- tion θ. Au point courant à coder, il est prévu d'ob¬ server les éléments de contour horizontaux EHn et ver- ticaux EV par un test de l'amplitude de gradients locaux associés, d'en suivre la connexité le long de la ligne courante et par rapport à la ligne précéden- te. -L'observation complète d'une zone connexe permet d'une part, d'engendrer un signal de fin de zone con¬ nexe FZCn et un signal d'absence d'éléments de con- tours TROU , et d'autre part de compter le nombre to¬ tal d'éléments de contour horizontaux et verticaux ob- serves, H et V.

OMFI

L'invention prévoit dans les zones con¬ nexes, d'une part, un traitement des "fourches", où un état interpolé E est alors calculé à partir des états des deux derniers contours de la fourche à la ligne précédente et, d'autre part, un calcul du signe obser- ve, S à la ligne courante. L'état E est alors réactua¬ lisé, à partir des observations H, V, S. Si la zone connexe observée à la ligne courante n'est pas connexe d'une zone connexe de la ligne précédente, il est pré- vu une initialisation de l'état ; ces deux opérations, initialisation et réactulisation, constituent le cal¬ cul du nouvel état, E, du contour.

L'invention prévoit de mémoriser les états E correspondant aux diverses zones connexes observées sur la ligne courante (E ¹ ) pour qu'ils puissent être utilisés à la ligne suivante. La mémoire d'état est à accès aléatoire. De même, il est prévu la mémorisation pendant une ligne des signaux EVn et FZCn, (EVn et ZC^) . L'invention .prévoit d'utiliser l'état E ainsi que les signaux EV et FZC pour préparer une prédiction à partir des valeurs de points voisins an¬ térieurs au point à coder. Cette préparation de la prédiction sera mémorisée pendant une ligne pour pou- voir être lue à la ligne suivante. A la ligne couran¬ te, il est ainsi prévu de disposer d'une préparation de la prédiction P , , qui contient les renseignements nécessaires au calcul final, au point courant, de la prédiction P_ ₊₁ « De façon plus précise, l'invention a pour- objet un dispositif pour l'estimation des contours d'une image, qui comprend :

A) une mémoire séquentielle apte à délivrer, lors¬ qu'elle reçoit l'échantillon de rang n+1, respecti- vement : l'échantillon de rang n, soit Xn, l'échan-

OMPI

tillon de rang n-1, soit X ,, appartenant à la même ligne que l'échantillon reçu et l'échantillon de rang n appartenant à la ligne précédente, soit X',

B) un circuit d'examen comprenant : - des moyens pour détecter entre deux échantillons

Xn—1. et Xn successifs d'une même ligne, un élé- ment de contour vertical EV_,

- des moyens pour détecter, entre deux échantillons X' et X de même rang, mais appartenant à deux lignes adjacentes, un élément de contour horizon¬ tal EH _n ,

- un moyen pour détecter l'absence d'éléments de contour, ce moyen délivrant un signal noté TROU ,

- un moyen pour compter le nombre total d'éléments de contour horizontaux et le nombre total d'élé¬ ments de contour verticaux examinés le long d'une ligne, pour chaque zone connexe, ces nombres étant traduits en signaux H et V en fin de zone connexe, - un moyen pour détecter les connexités, ce moyen étant apte à délivrer un signal lorsqu'une con- nexité se termine-au point de rang n, signal noté

C) -une boucle fonctionnant de manière recursive, com- prenant un moyen pour calculer l'état du contour, pour mémoriser l'état E' obtenu pour la ligne pré¬ cédant celle qui est examinée et pour calculer, en fonction de cet état E' et des signaux EH , TROU , FZC , V et H obtenu pour la ligne examinée, le nou- vel état E du contour à cette ligne examinée.

L'invention a également pour objet un dispo¬ sitif de prédiction d'échantillons pour des images de télévision, ce dispositif étant caractérisé en ce qu'il comprend : A) un dispositif pour l'estimation des contours d'une image tel qu'il vient d'être défini et dans le¬ quel :

- la mémoire séquentielle est pourvue de deux sor¬ ties supplémentaires délivrant les échantillons

_ _Λ

^X n-J+1 ^{et X} n-J'

- la boucle recursive possède deux sorties déli- vrant respectivement : i) un signal noté EV indiquant la présence d'un élément de contour vertical pour le point de rang n, - ii) le signal FZC , - la boucle recursive possède une sortie délivrant un signal noté _EJ déterminant l'état du contour au point de rang n-J,

B) un circuit de préparation d'une prédiction et de mémorisation de cette prédiction préparée, ce cir- cuit comprenant des moyens pour calculer une combi-

_«- - naison linéaire des signaux Xn— _τ et Xn„-J_+,l, q - ¹ ui dé- pend de l'état EJ et des signaux EV et FZC , et une mémoire à accès direct qui stocke ladite fonc¬ tion à une adresse qui dépend du rang n-J et de l'état EJ, cette mémoire ayant une sortie qui déli¬ vre un signal P , pour l'échantillon d'entrée de rang n-KL ;

C) un circuit de calcul final de la prédiction compre¬ nant des moyens pour sélectionner ^ _n+ ι ou X selon les informations contenues dans P , et pour adres¬ ser la valeur sélectionnée, soit P ,, , sur une sor¬ tie, ce signal constituant l'échantillon de prédic¬ tion de rang n+1.

De toute façon, les caractéristiques et avantages de l'invention apparaîtront mieux après la description qui suit d'exemples de réalisation donnés à titre explicatif et nullement limitatif. Cette des¬ cription se réfère à des dessins sur lesquels :

- les figures la, lb, le précisent les nota- tions et la terminologie employées,

OMPI

< y IPO

- la figure 2 est un bloc-diagramme d'un co¬ deur MICD connu utilisé pour coder avec compression des signaux d'images de télévision,

- la figure 3 est un bloc-diagramme d'une variante du codeur de la figure 2,

- la figure 4 est un bloc-diagramme d'un dé¬ codeur MICD classique pour reconstruire des signaux d'images de télévision codés MICD,

- la figure 5 est un bloc-diagramme du cir- cuit de prédiction suivant l'invention,

- la figure 6 est un bloc-diagramme du cir¬ cuit des observations et de l'estimation recursive de. l'état,-

- la figure 7 est un bloc-diagramme du cir- cuit d'observation des zones connexes,

- la figure 8 est un bloc-diagramme du cir¬ cuit d'analyse des zones connexes, d'une ligne à la suivante,

- la figure 9 est un bloc-diagramme du cir- cuit de calcul du barycentre des états,

- la figure 10 est un bloc-diagramme du cir¬ cuit de réactualisation des états,

- la figure 11 est un bloc-diagramme du cir¬ cuit de la mémoire de l'état, - la figure 12 est un bloc-diagramme du cir¬ cuit de préparation et de mémorisation de la prédic¬ tion,

- la f gure 13 est un bloc-diagramme du cir¬ cuit de calcul final de la prédiction. Bien que l'invention soit plus générale, la description qui suit se réfère au cas où l'estimation du contour sert à une prédiction utilisée pour le co¬ dage de signaux de télévision.

La compréhension des blocs-diagrammes qui vont être décrits nécessite les conventions classiques

en logique : les valeurs logiques suivent la conven¬ tion positive et les fronts montants des signaux logi¬ ques sont actifs. La synchronisation de l'ensemble des opérations nécessite des circuits de retard et des re- gistres de prise en compte non représentés, sauf s'ils sont explicitement nécessaires à la compréhension de la réalisation. Ainsi, par exemple, l'horloge d'échan¬ tillonnage du signal de télévision, HP, devra être correctement retardée là où cela est nécessaire. Le signal de début de ligne sera noté DL, montant à 1 pendant les suppressions de lignes et redescendant à 0 immédiatement après être monté à 1.

Le signal binaire PL portera l'information de parité de la ligne courante (=1 pour les lignes impaires de la même trame, =0 pour les lignes pai¬ res) ; il changera d'état logique juste avant DL. Se¬ lon la pratique classique, les valeurs des points dé-

_Λ codes X pendant les suppressions-lignes et -trame se- ront imposés à une valeur fixe, 0 par exemple. Les signaux TR0U _n , FZC _n , EH _n , EV _n# E, E' , EV _n _ _j , EV^, FZC^ devront être annulés pendant les mêmes suppressions ; les circuits nécessaires à ces remises à zéro ne sont pas représentés. On conviendra enfin qu'il y a N points par ligne active. Le codeur MICD de la figure 2 comprend un soustracteur algébrique 1 dont la première entrée est l'entrée de signal à coder, noté X , et dont la sortie est reliée à l'entrée d'un circuit quantificateur-co¬ deur 2. La sortie de celui-ci est d'une part reliée à un organe d'émission 3, et d'autre part à un circuit quantificateur décodeur 4 dont la sortie est reliée à la première entrée d'un circuit additionneur algébri¬ que 5. La sortie de celui-ci est reliée à un circuit prédicteur 6 dont la sortie est reliée, d'une part à une seconde entrée du circuit soustracteur 1, et d'au-

tre part, à une seconde entrée du circuit addition¬ neur 5.

Dans l'exemple de réalisation décrit, le si¬ gnal X de télévision à coder est appliqué à l'entrée sous forme numérique, tel que délivré par un codeur classique MIC non montré. Le soustracteur 1 effectue la différence dn entre le signal numérique Xn et un signal numérique de prédiction. P délivré par le cir¬ cuit prédicteur 6. Le circuit quantificateur-codeu peut être constitué par une mémoire morte de codage dans laquelle les valeurs d délivrées par le sous¬ tracteur 1 sont considérées comme des adresses aux¬ quelles correspondent des signaux MICD, C qui sont lus pour être appliqués au circuit 3 qui les transmet. Les signaux numériques sont également appliqués au quantificateur-décodeur 4 qui peut être constitué d'une mémoire morte dans laquelle les valeurs C sont considérées comme des adresses auxquelles correspon¬ dent des signaux numériques d qui constituent les différences reconstruites. L'additionneur 5 effectue l'opération de décodage MICD interne classique et dé-

_-v livre un signal X . Ce signal entre alors dans le cir¬ cuit prédicteur qui contient des mémoires pour stocker

__s. certains points voisins antérieurs X _n . , k > 1 de la même ligne et X' de la ligne précédente. Ce circuit sera décrit plus en détail aux figures suivantes ; il délivre la prédiction P utilisée pour le soustracteur 1 et pour l'additionneur 5.

Le codeur MICD, de la figure 3 est une va- riante de la figure 2. Il comprend un circuit sous¬ tracteur 1 qui reçoit le signal X à coder, sur une première entrée et le signal de prédiction P , sur une seconde entrée. La sortie du circuit 1 est, d'une part, reliée au circuit quantificateur-codeur 2, iden- tique à celui de la figure 2, et d'autre part à un

*^OR£ ^

OMPI

circuit quantificateur 7 dont la sortie est reliée à la première entrée du circuit additionneur 5. Celui-ci est identique à celui de la figure 2 ; il reçoit le signal de prédiction P sur une seconde entrée et sa sortie est reliée à l'entrée du circuit prédicteur 6, identique à celui de la figure 2. La sortie du circuit 2 est reliée à l'entrée du circuit 3, identique à ce¬ lui de la figure 2.

Sur la figure 3, le circuit 7 peut être constitué d'une mémoire dont les adresses sont consti¬ tuées par les signaux numériques d et les signaux d y sont lus : il effectue ainsi directement les opéra¬ tions effectuées par les circuits 2 et 4 de la boucle de prédiction décrite à la figure 2. Le reste des opé¬ rations est identique à celles décrites à la figure 2.

Le décodeur MICD de la figure 4 comprend un circuit d'entrée 8 qui est un organe de réception dont la sortie est reliée à l'entrée d'un circuit quantifi¬ cateur-décodeur 4 dont la sortie est reliée à la pre¬ mière entrée d'un circuit additionneur 5. La sortie de celui-ci est reliée à l'entrée d'un circuit 6 dont la sortie constitue la seconde entrée du circuit 5 ; ce¬ lui-ci délivre le signal reconstitué X qui est appli¬ qué après une conversion numérique-analogique à un ré¬ cepteur de télévision, non représenté.

Les opérations effectuées dans le décodeur sont classiques et elles s'appliquent aux deux varian¬ tes de réalisation du codeur, décrites aux figures 2 et 3. Les codes reçus C sont transformés dans le cir¬ cuit 4, identique à celui de la figure 2, en différen¬ ces reconstruites dn. Dans le circuit 5, dn est addi- tionné à la prédiction P pour délivrer le signal dé-

, rΛ. ⁿ code Xn. Celui-ci entre dans le circuit p*rédicteur comme aux figures 2 ou 3.

Les circuits des figures 2, 3 et 4 sont con¬ nus. L'invention se rapporte plus spécialement au cir-

OMPI

cuit de prédiction 6 qui va maintenant être décrit à l'aide de la figure 5.

Tel que représenté, le circuit prédicteur comprend : A) une mémoire séquentielle à trois circuits 9, 10 et 11 possédant une entrée qui reçoit la suite des échantillons numériques, et cinq sorties déli¬ vrant, lorsque l'échantillon de rang n+1 est reçu à l'entrée, respectivement les échantillons de rang n, soit X , de rang n-1, soit X ,, de rang de n-J+1, soit ^χ _n _ _+ι *3e rang n-J, soit X _n _ , appar¬ tenant tous à la même ligne que l'échantillon reçu et l'échantillon de rang n appartenant à la ligne précédente, soit X', B) un circuit 12 d'examen et d'estimation recursive de l'état, qui possède trois entrées recevant les si¬ gnaux Xn, Xn—i,, et Xn' et trois sorties délivrant respectivement : i) un signal noté EJ déterminant l'état du con- tour au point de rang n-J, ii) un signal noté EV indiquant la présence d'un élément de contour vertical pour le point de rang n, iii) un signal FZC de fin de zone connexe, C) -un circuit 13 de préparation d'une prédiction et de mémorisation de cette prédiction préparée ; ce cir¬ cuit possède cinq entrées principales, deux d'entre elles recevant les échantillons Xn-J_. et Xn-J,+.1, dé- livrés par la mémoire, les trois autres recevant les informations EJ, EV et FZC délivrées par le circuit 12, ce circuit comprend des moyens pour r - calculer une fonction linéaire des signaux X _Λ , et X - _J + _l qui dépend de l'état EJ et des signaux EV et FZC , et une mémoire à accès direct qui stocke ladite fonction à une adresse qui dépend du rang n-J et de l'état EJ, cette mémoire ayant une sortie qui délivre un signal P . pour l'échantillon d'en¬ trée de rang n+1,

D) un circuit 14 de calcul final de la prédiction, ce circuit possédant deux entrées, l'une recevant l'échantillon Xn de la mémoire et l'autre le signal

P ₊ , du circuit 13 de préparation de la prédiction, ce circuit comprenant des moyens pour sélectionner _p_ ^" n+,ι, ou Xn selon les informations contenues dans

P ,, et pour adresser la valeur sélectionnée, soit P ,, sur une sortie, ce signal constituant l'échantillon de prédiction de rang n+1.. Les circuits 9, 10, 11, 12 et 13 sont ac¬ tionnés par les signaux de service HP (horloge) , DL (début de ligne) et PL (parité de ligne) .

Les circuits 12, 13 et 14 sont décrits sur les figures 6 à 13. Le bloc-diagramme de la figure 6 tout d'abord, représente le schéma du circuit 12 d'observa¬ tion et d'estimation recursive de l'état. Ce circuit comprend :

A) un circuit 15 d'examen des connexités comprenant : - des moyens pour détecter entre deux échantillons

* X* ^** * , et X*- successifs d'une mê_.me ligne, la pré¬ sence ou l'absence d'une variation de la valeur de l'échantillon qui excède un certain seuil, et pour engendrer un signal correspondant d'élément de contour vertical noté.EV ,

- des moyens pour détecter, entre deux échantillons X' et de même rang, mais appartenant a deux lignes adjacentes, la présence ou l'absence d'une variation de la valeur de l'échantillon qui excè- de un certain seuil et pour engendrer un signal correspondant d'élément de contour horizontal

- un moyen pour délivrer un signal TROU en cas d'absence de contour au point de rang n, - un moyen pour compter le nombre total d'éléments de contour horizontaux et le nombre total d'élé-

ments de contour verticaux examinés le long d'une ligne dans chaque zone connexe, ces nombres étant traduits en signaux H et V,

- un moyen pour détecter les éléments de contour horizontaux et verticaux connexes sur une ligne, et pour détecter les ensembles de tels éléments connexes, c'est-à-dire les connexités, ce moyen étant ,apte à délivrer un signal lorsqu'une con-*- nexité se termine au point de rang n, signal no- té EZC _n ,

- le circuit 15 d'examen des connexités possédant ainsi trois entrées recevant les échantillons X ,

X„n—i, et Xn' et six sorties délivrant respective- les sig ³ naux EVn. EHn, V, H, FZCn, TROUn, une boucle fonctionnant de manière recursive, com¬ prenant :

- une première mémoire 18, dite mémoire d'état, re¬ cevant les signaux E et FZC relatifs à la ligne en cours d'examen et un signal FZCn* de fin de connexite pour la ligne précédente ; cette mémoi¬ re délivre un signal d'état E* relatif à la ligne précédente ainsi que le signal d'état EJ relatif au point de rang n-J de la ligne en cours d'exa¬ men ; - une seconde mémoire 19, à N registres, recevant le signal FZCn de fin de connexit relatif à la ligne en cours d'examen et délivrant le signal FZC' relatif à la ligne précédente ;

- une troisième mémoire 20 recevant le signal EVn et délivrant un signal EV' relatif à la ligne précédente,

- un circuit 16 d'analyse de connexités d'une ligne à la suivante, ce circuit possédant six entrées recevant resp *-ectivement les sig ³ naux EHn. TROUn et

FZC du circuit d'observation des connexités, et

E', FZCn* et EVn* des trois mémoires, ce circuit possédant des moyens pour extraire, des six si¬ gnaux qu'il reçoit, trois signaux utiles à l'étu- de d'une connexite et relatifs à la partie de la ligne précédente située au contact de ladite con¬ nexite, ces trois signaux étant respectivement : un signal ÏÏ donnant le signe de l'orientation du contour de l'image tel qu'observé à la li- gne courante, un signal TI indiquant, la nécessité d'une ini¬ tialisation de l'état, en début de contour, un signal E relatif à un ancien état équiva¬ lent pour la connexite en cours d'examen dans le cas d'observation d'une fourche ;

- un circuit 17 de réactualisation de l'état, à cinq entrées recevant respectivement les signaux H et V du circuit 15 d'examen des connexités et S, TI et E du circuit 16 d'analyse des connexités d'une ligne à la suivante, et à une sortie déli¬ vrant un signal d'état E obtenu soit à partir de l'ancien état E et des observations plus récentes £3, H, V, soit uniquement à partir des observa¬ tions les plus récentes S, H, V, cas qui est in- diqué par le signal TI.

La figure 7 représente le bloc-diagramme du circuit 15 d'observation des zones connexes. Ce cir¬ cuit comprend :

A) une première voie, de traitement des éléments de contour horizontaux, constituée par :

- un premier circuit différentiateur 21a à deux en¬ trées recevant les signaux xn' et Xn, et une sor- tie délivrant un signal GV de gradient vertical,

- un premier comparateur 22a recevant le signal GV et délivrant le signal logique EH représentant un élément de contour horizontal,

- une sortie délivrant ledit signal EHn,

- un premier accumulateur 23a recevant les signaux EH et les comptabilisant, pour délivrer un si¬ gnal H représentant le nombre d'éléments de con- tour verticaux, cet accumulateur étant remis à zéro par le signal TROU ,

- un premier comparateur 25a, qui reçoit le signal H et le compare à un nombre prédéterminé et dé¬ livre un signal de dépassement DH lorsque H ex- cède ce nombre,

- un premier registre 29a qui charge le signal H , ce registre étant commandé par le signal FZC et délivrant le signal H représentant le nombre d'éléments de contour horizontaux de la connexite examinée,

- un inverseur 26 recevant EHn et délivrant un si- gnal complémentaire EH , une deuxième voie, de traitement des éléments de contour verticaux, constituée par : - un second circuit différentiateur 21b à deux en¬ trées recevant les signaux Xn et n_-l, , et une sortie délivrant un signal GH de gradient hori¬ zontal,

- un second comparateur 22b recevant le signal GH et délivrant le signal logique EV représentant un élément de contour vertical,

- une sortie délivrant ledit signal EV ,

- un second accumulateur 23b recevant les signaux

EV -et les comptabilisant, pour délivrer le si- gnal Vn et représentant le nombre d'éléments de contour horizontaux, cet accumulateur étant ac¬ tionné par le signal d'horloge HP et remis à zéro par le signal TROU ,

- un second comparateur 25b qui reçoit le signal V , le compare à un nombre prédéterminé et déli¬ vre un signal de dépassement DV lorsque V dé¬ passe ce nombre,

USEA7-

CMPI_

- un second registre 29b qui charge le signal V , ce registre étant commandé par le signal FZC , et délivrant le signal V, représentant le nombre d'éléments de contour verticaux de la connexite examinée,

- un comparateur 24 recevant le signal V et compa¬ rant ce signal à 1, et délivrant un signal DZV ,

C) une porte logique de type OU à trois entrées rece¬ vant respectivement les signaux DH , ËH et DV et une sortie délivrant le signal TROU ,

D) une porte logique de type ET à deux entrées rece¬ vvaanntt lleess ssiiggnnaauuxx TTRROUn et DZVn.- _. et une sortie déli- vrant le signal FZCn.

Dans l'exemple d'application traité, les signaux Xn. Xn* et Xn—1, p ^roviennent des mémoires 9, 10,

11 de la figure 5. Les circuits 21a et 21b calculent la valeur absolue de la différence entre leurs deux entrées ; leurs sortie GVn et GHn sont les gradients verticaux et horizontaux codés par huit éléments bi- naires (eb) . Les circuits 22a et 22b sont deux compa¬ rateurs dont les sorties logiques respectives sont à 1 si les gradients GV et GH respectivement sont supé¬ rieurs à deux seuils λ„ et λ„ fixés. Les sorties logi- ques EH et EV de ces comparateurs, lorsqu'elles sont à 1, indiquent donc la présence d'éléments de contours horizontaux et verticaux. Ces éléments de contour sont comptabilisés à chaque front montant de HP dans les accumulateurs 23a et 23b et admettent TR _OUn co_mme si- gnal de remise à zéro ; leurs sorties H et V (3eb suffisent) comptabilisent donc le nombre d'éléments horizontaux et verticaux au cours de l'observation de la connexite traitée ; ils sont chargés dans les re¬ gistres 29a et 29b, en fin de connexite (commande FZC ) qui délivrent les nombres H et V (3eb) d'élé- ments de contours horizontaux ou verticaux dans la

OMPI

connexite qui a été examinée. Le circuit 24 est un comparateur ( >1) dont la sortie est le signal logique DZV qui vaut 1 si V > 1, indiquant le premier élé¬ ment de contour vertical dans la connexite. Il repasse à zéro en fin de connexite à cause de la remise à zéro par TROUn de l'accumulateur 23b.

L'obtention des signaux FZCn et TROUn s'ef- fectue comme -suit. Le signal TROU est destiné à repé¬ rer les intervalles entre connexités, que lesdites connexités comportent ou non des éléments de contour verticaux ; une connexite est interrompue, dans les deux cas suivants .: soit si l'on n'observe plus d'élé¬ ments de contour horizontal, ce qui implique EH = 0 ou ËH = 1 (sortie de l'inverseur 26), soit si l'on observe que le contenu des accumulateurs 23a et 23b dépassent strictement la valeur 6 : les circuits 25a et 25b sont des comparateurs ( > 7) dont les sorties logiq^ues DHn et DVn passent à 1 si Hn ^> 7 et V„n ^ 7 respectivement ; si l'un de ces trois cas se produit, l connexite est alors rompue, et éventuellement par¬ tagée en plusieurs connexités si elle est trop large (DH ou DV actifs) ; la raison d'une telle procédure est d'éviter le risque d'avoir des connexités de lon¬ gueur incontrôlée, ce qui nécessiterait des tamponna- ges complexes, alors que la solution proposée n'offre que peu d'inconvénients, le cas de débordement ne se produisant que très rarement en pratique. Le circuit

27 est un OU à trois entrées dont la sortie TROUn indique donc un trou entre connexités et est une sor- tie du circuit. D'autre part, le signal DZV est, avec

^" TROU , l'une des deux entrées du ET logique 28, qui délivre le signal logique FZC indiquant que le trou détecté par TROUn suit immédiatement une zone connexe admettant au moins un élément de contour vertical : FZC est donc un signal de fin de zone connexe admet-

tant un ou plusieurs éléments de contour verticaux (ce sont exactement les zones connexes pour lesquelles il y aura à effectuer une réactualisation ou une initia¬ lisation de l'état) ; le signal FZC apparaît en sor- tie du circuit.

Bien entendu, chaque utilisation de l'un des deux signaux de commande TROUn ou FZCn requiert un réglage convenable des -retards de l'horloge point HP ; par exemple, dans la figure 7, les signaux FZC de commande d'écriture des registres 29a et 29b doivent agir avant les signaux de commande, de remise à zéro

(TROU ) des accumulateurs 23a et 23b.

Le tableau I décrit, pour une ligne en cours de traitement, l'évolution des divers signaux au cours de l'observation de quatre connexités dont une (la première) n'est pas prise en compte car ne présentant pas d'éléments de contour verticaux et une autre (la troisième) est trop longue et est donc segmentée. Les signaux H et V ne sont indiqués qu'en fin de connexi- té.

Le circuit 16 d'analyse des zones connexes d'une ligne à la suivante est détaillée à la figure 8.

Il comprend :

- un premier circuit retard 30a, à une entrée recevant le signal TROU et à une sortie délivrant un signal retardé TROU ,,

- un registre 31 à une entrée de signal recevant le signal EVn et à une entrée de commande recevant le signa_l TROUn—,1 et à une sortie délivrant le si- gnal S,

- un second circuit retard 30b actionné par le signal d'horloge HP, à une entrée recevant le signal EH et une sortie délivrant un signal EH ,,

- une porte logique 32, de type OU, à deux entrées recevant les signaux EHn—l, et EHn et à une sortie délivrant un signal EHH ,

OMP

- une porte logique 33 de type ET, à deux entrées re¬ cevant les sig ³ naux-EHHn et EVn* et à une sortie déli- vrant un signal EVZ ,

- une première voie de traitement du signal EVZ com- prenant : i) : un premier accumulateur 34a ayant une entrée de remise à zéro recevant le signal TROUn, une entrée de signal recevant EVZn et une sortie délivrant un signal EVC , ii) : un premier comparateur 35a par rapport à 1, à une entrée recevant EVCn et à une sortie délivrant un signal TIn, iii) : un registre 36 possédant une entrée d'écri¬ ture recevant le signal RZC , une entrée de signal recevant TIn et une sortie délivrant un signal TI de nécessité d'une initialisa¬ tion,

- une seconde voie de traitement du signal EVZn com- prenant : i) : un second accumulateur 34b ayant une entrée de remise à zéro recevant le signal FZC', une entrée de signal recevant EVZn ^• et une sortie délivrant un signal AEVZ , ii) : un second comparateur 35b par rapport à 1, à une entrée recevant AEVZn et à une sortie délivrant un signal DEVZ , iii) : un accumulateur 37 possédant une entrée de remise à zéro recevant le signal TROU , une entrée d'autorisation recevant le signal DEVZ , une entrée de signal recevant un si¬ gnal 1 et une sortie délivrant un si¬ gnal FCH , iiii) : un comparateur 38 par rapport à 1, à une entrée recevant le sig ³ nal FCHn et à une sor- tie délivrant un signal de commande PREM,

OMPI

- un circuit retard 39, à une entrée de remise à zéro recevant FZC, à une entrée de signal recevant le signal d'état E' et à une sortie délivrant un signal d'état E*, - un circuit arithmétique et logique 40 à deux en¬ trées, recevant l'une E' et l'autre E', et à une sortie délivrant un signal B* de pondération des si¬ gnaux Ei et Ξ' ,

- enfin, un circuit sélecteur 41 à une entrée de com- mande recevant le signal PREM, à deux entrées rece¬ vant les signaux B' et E*, et à une sortie délivrant le signal E d'état équivalent e présence de four¬ che.

La fonction du circuit 16 d'analyse des zo- nés connexes d'une ligne à la suivante est. d'extraire celles des informations utiles à l'étude d'une con¬ nexite, qui sont relatives à la partie de la ligne précédente située au contact de ladite connexit ; ces informations sont au nombre de trois, correspondant aux trois sorties du circuits : S, TI, E.

Le signal S ^* donne l'information concernant l'orientation du contour (cf. figure le) : S = 1 si θ > 0, S = 0 si θ ^ 0 ; ce signal, disponible sous l'action de TROUn—1,, délivré à partir du signal TROUn par le retard 30a, est fournie en chaque point suivant immédiatement un point non situé dans une connexit , mais n'a la signification requise que lors du début d'une connexite (cf. tableau lia), seul moment où il sera effectivement utilisé par la suite (indiqué par * dans le tableau lia) .

Le signal TI indique la nécessité d'une ini¬ tialisation ; pour la connexite en cours (remise à zé¬ ro par TROU ) , l'accumulateur 34a compte les éléments de contour verticaux EVn' situés immédiatement au-des- sus de la connexite traitée, extrémités comprises

OMPI

(d'où la présence de EH ,) , tandis que le signal TI (inscription de TI -en fin de connexite) indique par sa valeur 1 que ledit accumulateur est vide.

Le signal E constitue l'état équivalent en présence de fourche, c'est-à-dire d'une situation où deux connexités différentes de la ligne précédente se¬ raient reliées toutes deux à la même connexite au cours de son traitement (cf. tableau Ilb) , auquel, cas le circuit 40 effectue un calcul "barycentrique", dont le résultat est B' , à partir des états des deux der¬ nières connexités E' et EJ de la ligne précédente, reliées à la connexite en cours de traitement (ce cir¬ cuit sera précisé à la figure 9) ; en cas de présence d'une fourche à trois branches ou plus, seules lès deux dernières sont retenues pour cette opération. La présence d'une fourche est détectée par le signal de commande PREM du sélecteur 41 (E = E' si PREM = 1, E = B' si PREM = 0) qui est engendré de la manière suivante : le signal AEVZ compte les éléments de con- tour verticaux relatifs à une connexite de la ligne précédente (d'où la remise à zéro par FZC') et reliés à la connexite en cours de traitement ; la sortie du comparateur 35b ( 1) contient l'information néces¬ saire à la détection des premiers instants où AEVZ n'est plus nul : l'état du signal DEVZ donne à l'hor¬ loge Hp l'autorisation d'accumuler l'entrée de valeur

1 dans l'accumulateur 37 ; dont la sortie FCHn compta- bilise (tableau Ilb) le nombre de branches de la four¬ che ; enfin, le comparateur 38 impose PREM = 1 si

Le circuit "barycentre" 40, introduit à la figure 8 est détaillé à la figure 9. Il comprend deux circuits additionneurs 42a et 42b dont les entrées respectives véhiculent des signaux NP' et NM' regrou- pant certains éléments binaires du signal d'état El

W^Ë ϋ^

' OMPI

d'une part, et des signaux NP' et M ¹ extraits du si¬ gnal d'état E' d'autre part. Les sorties des deux cir¬ cuits 42a et 42b sont les entrées d'un circuit trans¬ codeur 43 dont la sortie est une entrée du circuit arithmétique et logique 44 dont la sortie véhicule le signal B', et dont les autres entrées véhiculent les signaux E' et E*.

Les additionneurs 42a et 42b fournissent, les longueurs approchées NL' = NM' + NP' et NLJ = NM' + NP! des deux contours constituant la four¬ che. La sortie du circuit 43 est un coefficient pon¬ dérateur servant à tenir compte de la longueur relati¬ ve des deux contours.

Les tableaux Illa et Illb donnent deux va- riantes de correspondance entre NL-j, NL' et α. Le ta¬ bleau Illa constitue la première variante et le ta¬ bleau Illb complemente le tableau Illa dans le cas de la seconde variante en explicitant le cas NL' 1, NL >, 1 du tableau Illa. Le tableau IV indique la nomenclature des composantes des différents vecteurs d'état utilisés (E, EJ, E*, El , B', E, EE, El) avec leur numérisation.

Le tableau V ci-joint donne la correspondan¬ ce entre les états E' , et El et l'état équivalent par "barycentrage", B'.

Dans ce tableau, les signes S' et SI sont à interprêter sous la forme + 1 (-1 si l'élément binaire est à 0, +1 si l'élément binaire est à 1) cette con¬ vention est valable pour toutes les formules interve- nant dans les divers tableaux.

La figure 10 détaille le circuit "réactuali- sation de l'état local" 17 introduit à la figure 6. Ce circuit comprend : - un premier transcodeur 45a à deux entrées recevant des signaux d'éléments de contour horizontaux et ^"

OMPI

/ ΛJ _f t\t- _N verticaux H et V extraits du signal d'état E, et a une sortie délivrant un signal θ correspondant a la valeur absolue d'un angle ancien d'orientation du contour, - un second transcodeur 45b à deux entrées recevant des signaux d'éléments de contour horizontaux et verticaux H et V issus du circuit 15 et à une sortie délivrant un signal θ correspondant à la valeur ab¬ solue d'un angle à \orientation du contour examiné, - un circuit différentiateur à seuil 46 à deux entrées recevant les signaux θ et θ et à une sortie déli¬ vrant un signal Tθ,

- un circuit comparateur 47 par rapport à 2, à une entrée recevant un signal NM extrait du signal

A/ d'état E et représentant le nombre de marches du contour, et à une sortie délivrant un signal TNM,

- une porte logique 50 de type ET et à deux entrées recevant respectivement les signaux Tθ et TNM et à une sortie délivrant un signal RUPTΘ, - un circuit logique 48, de type OU-exclusif, à deux entrées recevant respectivement le signal S extrait du signal d'état E, et le signal ÏÏ issu du circuit d'analyse ligne par ligne, et à une sortie délivrant un signal SS _r - un circuit combinatoire 49 à deux entrées recevant respectivement un signal Q extrait du signal E et le signal SS, et à deux sorties, l'une délivrant un signal RUPTS et l'autre un signal Q,

- un circuit logique 51, de type OU, à trois entrées recevant respectivement le signal TI, le signal

RUPTΘ et le signal RUPTS et à une sortie délivrant un signal RUPT,

- un circuit arithmétique et logique 52 de réactuali¬ sation de l'état, à neuf entrées recevant respecti- vement le signal Q et les signaux provenant de E

OMPI

soit : NM, NS, H, V, NP, ainsi que les signaux d'ob¬ servation H, V et ^~ S , et à une sortie délivrant un signal EE de réactualisation,

- un transcodeur 53 à trois entrées recevant respecti- vement les signaux H, V et s ^" et à une sortie déli¬ vrant un signal El d'état initialisé,

- un sélecteur 54 à deux entrées, recevant les signaux EE et El, à une entrée de commande recevant le si¬ gnal RUPT, et à une sortie délivrant le signal. E. Les circuits 45a et 45b peuvent être deux mémoires programmables identiques qui à partir de H et V, respectivement H et V, délivrant Θ, respectivement Θ. Ces deux angles mesurent en valeur absolue l'angle ancien et l'angle observé, exprimés avee 3eb dans l'exemple des tableaux Via et VIb qui sont deux va¬ riantes de la transformation donnant Θ à partir de H et V.

Le circuit 46 effectue le test [θ- θj^Δθ, où Δθ est un seuil fixé. Le circuit 47 est un corapara- teur ( > _y 2) dont la sortie est TNM (TNM = 1 si NM 2) . La sortie du ET logique 50 est le signal RUPTΘ qui ne prend en compte la rupture sur la valeur absolue de θ que si la longueur du contour observé est suffisante. Le signal SS, sortie du OU exclusif 48 est traité avec le signal Q par le circuit combinatoire 49 à deux entrées et deux sorties, dont le tableau de correspondance est décrit au tableau Vil.

La sortie RUPTS indique une rupture sur changement de signe persistant au moins deux lignes successives.

Les signaux RUPTS, RUPTΘ et TI sont combinés par le OU logique 51. Le signal RUPT (rupture) résul¬ tant est celui qui effectue le choix E, El (état ini¬ tialisé) dans le sélecteur 54 quand RUPT = 1. Le cir- cuit arithmétique et logique 52 a pour entrées le con-

OMPI

tenu de E, Q ayant néanmoins été remplacé par Q, et les trois observations H, V, S : il effectue la réac¬ tualisation de l'état suivant les formules indiquées aux tableaux VIII et IX, et délivre en sortie le si- gnal ΕE (état réestimé) . Enfin, le signal El est la sortie du circuit transcodeur 53 effectuant, suivant les indications du tableau IX, le chargement de El à partir des observations H, V, Î3. Dans le tableau IX, le signe S est à interpr ter sous la forme ± 1 et non pas 0 ou 1.

Le bloc-diagramme de la figure 11 représente . le schéma de la mémoire d'état 18 mentionnée à la fi¬ gure 6. L'entrée notée FZC est reliée d'une part aux entrées des circuits accumulateurs 56a et 57a et, d'autre part, à l'entrée du circuit mémoire 59 action¬ né par HP ; le circuit 56a, actionné par HP et remis à zéro par le signal DL de début de ligne, a sa sortie reliée à la première entrée des deux circuits mémoire 55a et 55b actionnés par HP. Outre l'entrée notée ^FZC n' ^le ol**-" ⁰¹¹ !*- 57 admet le signal Pi de parité de ligne, et ses sorties sont reliées respectivement à la troisième entrée du circuit 55a et à la troisième en¬ trée du circuit 55b. La sortie du circuit 59 est re¬ liée,à la première entrée des deux circuits logiques OU 58a et accumulateur 56b dont l'autre entrée est le signal DL ; leurs sorties sont respectivement reliées à la première entrée des circuits aiguilleurs 57b et

57c. Le signal d'entrée noté FZCn' est relié à l'entrée des circuits OU logique 58b et accumulateur 56c ac- tionnés par HP et remis à zéro par DL. Les sorties de ces deux circuits sont respectivement reliés aux se¬ condes entrées respectives des circuits 57b et 57c ; les sorties du circuit 57b sont reliées aux quatrièmes entrées des circuits 55a et 55b. Les sorties du cir- cuit 57c sont reliées aux cinquièmes entrées des cir-

cuits 55a et 55b. L'entrée notée E est reliée aux se¬ condes entrées des circuits 55a et 55b. Ces deux cir¬ cuits ont leurs sorties reliées aux entrées du circuit aiguilleur 60 commandé par PL, dont les sorties véhi- culent les signaux E' et EJ.

La mémoire d'état est constituée de deux mé¬ moires à accès direct (RAM) 55a et 55b relatives à la ligne courante et à la ligne précédente, la commuta¬ tion à chaque changement de ligne s*effectuant aux al- guillages 57a, b, c et 60 sous l'effet de la commande PL (0 ou 1) indiquant la parité de la ligne, suivant les indications du tableau X. Le signal AE est une adresse d'écriture sortant de l'accumulateur 56a (re¬ mis à zéro par le signal de commande DL de début de ligne) incrémenté par le signal de commande FZC indi¬ quant la fin d'une zone connexe. De même, les ordres d'écriture OE. et OE ₂ sont obtenus en sortie de l'ai¬ guillage 57a, command par PL, dont les deux entrées sont FZCn et 0 : on écrit seulement dans celle des deux mémoires relatives à la ligne courante (tableau ^χ ) • Les états sont lus d'une part pour la ligne précé¬ dente (état E') et, d'autre part, pour la ligne cou¬ rante (état EJ) pour une connexite qui se trouverait à la ligne courante éventuellement au point n-J (n étant le point courant, J étant un entier fixé qui sera pré- cisé à la fin de la description de la figure 12) . Les commandes de lecture pour la ligne précédente vont donc être obtenues en sortie OL ¹ du circuit OU logique 58b, dont la seconde entrée est DL (signal de commande indiquant un début de ligne) : une première -lecture est à effectuer en début de ligne, puis le signal FZC indique que la connexite relative à l'état E* qui vient d'être lu est terminée et qu'il faut par consé¬ quent donner un nouvel ordre de lecture. L'ordre de lecture de la mémoire d'état relative à la ligne cou-

OMPI

rante, avec un retard J assurant qu'un état éventuel pour une connexit se terminant au point n a été com¬ plètement calculé lorsque le point n-J arrive (les connexités sont de largeur ^ J, cf. figure 7, et ta- bleau I), s'obtient en sortie OLJ du circuit OU logi¬ que 58a à deux entrées admettant FZCn—u- (sortie du circuit 59 retardant FZC de J points) et DL comme entrées . OLJ agit exactement comme OL' . Les ordres de lecture sont aiguillés en 57b sous l'effet de la com- mande PL de parité de ligne (cf. tableau X) . Les adresses de lecture AL' et ALJ, relatives respective¬ ment à la ligne précédente (lecture de E') et à la ligne courante avec retard de J (lecture de EJ) s'ob¬ tiennent, suivant le même principe que précédemment, en sortie des accumulateurs 56b et 56c dont les en¬ trées respectives reç *oivent FZCn' et FZCn—J-., et dont la commande de remise à zéro est DL. L'aiguillage de ces adresses s'effectue en 57c sous l'effet du signal PL (tableau X) . En retour, le même signal PL commande l'aiguilleur 60 (tableau X) qui, ayant pour entrées les sorties el et el des deux mémoires RAM 55a et 55b délivre à sa première sortie E', et à sa seconde sor¬ tie EJ (tableau X) . Le tableau X ci-joint indique les affectations effectuées par les aiguillages 57a, b, c et 60.

Le circuit 13 de préparation et de mémorisa¬ tion de la prédiction est illustré sur la figure 12. Il comprend :

- une première mémoire 61 à une entrée recevant le signal EV et à une sortie délivrant un signal re¬ tardé EVn„—J_,

- un circuit inverseur 63 à une entrée recevant EVn—_. et délivrant un signal complémentaire EV -,

- une seconde mémoire 62 à une entrée recevant le si- gnal FZC et à une sortie délivrant un signal retar- ^{dé FZC} n-J-l'

OMPI

- une porte logique 64 de type ET à deux entrées rece¬ vant respectivement les signaux EV _ et FZC , , et à une sortie délivrant DTn—u _/

- une bascule 65 à deux entrées recevant respective- ment les sig ^J naux EVn—J, et DTn—_ et à une sortie dé- livrant un signal ZC ,,

- une porte logique 66 de type OU à deux entrées, l'une recevant le signal d'horloge HP et l'autre le signal ZCn,—, et à une sortie délivrant un signal OE, - un circuit aiguilleur 67 à deux entrées recevant l'une le signal d'horloge HP, l'autre le signal OE, à une entrée de commande recevant le signal PL, et à deux sorties délivrant respectivement un signal OEPP, et un signal OEPP ₂ - un circuit aiguilleur 68 à deux entrées recevant respectivement le signal d'horloge et un signal 0 de valeur nulle, à une entrée de commande recevant le signal de service PL et à deux sorties délivrant respectivement des signaux OLPP, et OLPP-, - un circuit transcodeur 73 à deux entrées recevant .respectivement les signaux HJ et VJ extraits du si¬ gnal d'état EJ et à deux, sorties,- délivrant respec¬ tivement un signal γJ et un signal NDECAJ,

- un comparateur 75 par rapport à un nombre au plus égal à J, à une entrée recevant le signal NDECAJ et à une sortie délivrant le signal TDECA,

- un compteur 77 à une entrée ede remise à zéro rece¬ vant le signal de service DL et une entrée recevant le signal d'horloge ΗP et à une sortie délivrant un signal n,

- un circuit arithmétique 76 à deux entrées recevant respectivement les signaux NDECAJ et n, et à une sortie délivrant le signal AEP correspondant à n-J + NDECAJ, - un additionneur 78 à deux entrées, l'une recevant le nombre n et l'autre le nombre 1 et à une -sortie

délivrant le signal ALPP correspondant à n+1,

- un premier aiguilleur 69a à deux entrées recevant respectivement le signal PP _ _j ^{et un} signal 0 nul, et à une entrée de commande recevant le signal de service PL et à deux sorties délivrant respective¬ ment des signaux pp, et PP ₂ ,

- un second aiguilleur 69b à deux entrées recevant respectivement les signaux ALPP et AEP, à une entrée de commande recevant le signal de service PL, et à deux sorties délivrant respectivement des signaux AEPP, et AEPP ₂ ,

- une première mémoire 70 à accès direct, à cinq en¬ trées recevant respectivement les signaux OEPP,, OLPP,, AEPP,, ALPP et pp, et à une sortie délivrant un signal p,,

- une seconde mémoire RAM 71 à accès direct, à cinq entrées recevant respectivement les signaux OΞPP ₂ , OLPP ₂ , AEPP ₂ , ALPP et pp ₂ et à une sortie délivrant un signal p_, - un sélecteur 79 à deux entrées recevant respective¬ ment les signaux p, et p ₂ et une sortie délivrant un signal de prédiction préparé P , .

Le sig ^J nal EVn est mémorisé dans le circuit

61 actionné par HP, pendant J périodes de HP ; le si- gnal FZCn est mémorisé dans le circuit 62 actionné par

HP pendant J+l périodes de HP. Le signal EV _ met à 1 la bascule 65 sur ses fronts montants, il est d'autre part inversé par le circuit 63. Le signal DT __ est le résultat d'un ET logique des signaux FZC ,_, et

ËV--, _τ ; par le circuit 64, il met à 0 la bascule 65 sur n—J ses fronts montants. La sortie de la bascule ZCn—o_, indique quand elle vaut 1 que le point n-J est dans une zone connexe, entre le premier élément de contour vertical et la fin de la zone, bornes incluses. Les

- θRÈΛ OMPI

circuits 67, 68, 69a, 69b et 79 permettent de comman¬ der les écritures et les lectures, d'indiquer les adresses d'écriture et de lecture, d'entrer les va¬ leurs à écrire et de sélectionner les sorties des .cir- cuits mémoire RAM 70 et 71, qui mémorisent sur une ligne la valeur PPn—J_. ou la valeur 0 sur une ligne.

Le fonctionnement des circuits 70 et 71 est inversé à chaque ligne, les divers signaux nécessaires à ce fonctionnement sont commutés selon le tableau XI. L'ordre d'écriture OE est obtenu par un ET logique des signaux ZC __ et HP ; il commande l'écri¬ ture de PP.n.—u_ à l'adresse AEP.

Supposons PL = 1, c'est alors la mémoire 70 qui fonctionne selon ce mode (OEPP, = OE, PPx-, = PPn—u,) , l'adresse d'écriture est AEPPJ,. = AEP qui, grâce au circuit arithmétique 76, vaut n-J + NDECAJ, n étant l'indice du point compté dans le circuit 77 qui est remis à zéro en début de ligne, J étant un nombre entier fixe que l'on précisera plus loin et NDECAJ étant un décalage entier directement fonction de l'angle estimé du contour observé au point n-J (voir figure le) . NDECAJ, de même type que γJ, est obtenu par transcodage des signaux HJ, VJ et SJ, issus de l'état EJ, grâce au circuit contenant une mémoire programmable 73 et selon les indications fournies au tableau XII, dans l'exemple considéré. L'angle ΘJ in¬ diqué est obtenu à partir de HJ et VJ de la même façon qu'aux tableaux Via et VIb qui sont deux variantes ; son signe est SJ ; il n'est pas nécessaire d'engendrer ΘJ dans le circuit 73.

Dans l'exemple où PL = 1, la mémoire 71 fonctionne selon un mode de lecture-écriture, de telle sorte qu'à chaque coup d'horloge HP (OLPP ₂ = HP, cir¬ cuit 68), la mémoire 71 est lue à l'adresse ALPP (= n+1, grâce à l'additionneur 78), le sélecteur 79

OMPI

délivre le résultat de cette lecture (P _n+1 = PP2) '• immédiatement après- que la lecture est effectuée, le contenu de la mémoire 71 est remis à zéro, en y ins¬ crivant la valeur 0 (pp, = 0, circuit 69a), à la même adresse (AEPP ₂ = ALPP, circuit 69b). L'horloge d'écriture OEPP ₂ nécessaire" pour cette opération est alors HP, entrée du circuit 67, qui sera retardée suf¬ fisamment pour intervenir après la fin du cycle de- lecture qui délivre P ^* n+.i,. Il faut donc que les mémoi— res RAM 70 et 71 soient conçues pour autoriser un cy¬ cle de lecture puis d'écriture pendant la durée d'une période de l'horloge HP. Quand PL = 0, les deux mémoi¬ res 70 et 71 ont le fonctionnement inverse. Enfin, le circuit mélangeur 72 délivre à partir de ses entrées

selon les indications du tableau XII (circuit 73) . Le signal de décalage NDECAJ entre dans le comparateur 75 (=7) qui délivre un signal TDECA = 1 si NDECAJ = 7, sinon TDECA = 0. Le rôle du circuit 74 est de trans¬ former VPP - en imposant la valeur de _n _ _j à 0,1 ou

VPPn„—J _τ selon les indications du tableau XIII.

Dans l'exemple décrit, les zones connexes ont au plus 7 points et donc J doit être au moins égal à 7. Toutefois, selon la fréquence de HP et la rapidi¬ té des circuits utilisés, J pourra être pris supérieur à 7, mais suffisamment inférieur à la durée de sup¬ pression de ligne pour ne pas perturber le fonctionne- ment de la mémoire d'état (figure 11).

Le circuit de calcul final de la prédiction est représenté à la figure 13. Il comprend : - un circuit décodeur 80 à une entrée recevant le si¬ gnal _n+1 r c circuit détectant la nullité de P_ ₊₁ et possédant une sortie délivrant un signal COM,

OMPI

- un sélecteur 81 à deux entrées recevant respective-

— - ^Λ , _• ment les signaux P . et X , a une entrée de comman¬ de recevant le signal COM et à une sortie délivrant le signal P _n+1# Le rôle du circuit décodeur 80 est de détec¬ ter la nullité de P_ ₊₁ : si P ^" _n+1 = 0, le signal COM de sortie du circuit, passe à 1, il agit alors sur le sélecteur 81 en. imposant P_ ₊₁ ^{= x} _n * ^S ~~ ^P n+1 ^ °' ^ ^e signal COM a la valeur logique 0 et le sélecteur 81 impose alors P-.-. - F ₊ , pour la prédiction.

OMP

T Λ B U E Λ U Ha nn - Kη ncin nKnnBiiaiiaxα

T A a L E A U III.

T A B L E A U ^* Illb

OMP

A B L E A U IV

Notes i (•*-) dons tous leβ cas, ce nombre prend toutes les valeurs rationnelles discrè es du soβment _l ^" " _. ⁰ !] _» autorisées par la nombre d'e.b, disponibles, par exemple, pour 4 a.b,, la pas de discrétisation est _)lprs de 0,5, et le? valeurs permises nont

T A B L E A U V n -s ZΛ -s z- : _t .-- z _f s_ __t z- ___ __:

T A L E A U Via

T A B L E A U VIb

OMPI

T A L E A U vu

T A B L E A U VIII

T Λ B L E Λ U IX oo aa _H _ι a≈≈ -iπ

T A B L E A U X

____,« Sd≤na as wi≈-sq q s»s ≈

T A B L E A U XI

T A B L E U XIT

T A B E A U XIII