L'invention est relative à un procédé ou à un dispositif de codage numérique d'une image, notamment une image de télévision, composée de points élémentaires (pels ou pixels) régulièrement répartis dans le plan de l'image, auxquels sont attribuées une ou plusieurs qua¬ lités radio étriques dénommées composantes C..

Ces composantes C. peuvent être, par exemple. les mesures des radiometries de chaque pixel dans N canaux spectraux fournies par des capteurs appropriés étages dans le spectre de fréquences radio-électriques : visible, infrarouge, rayonnement X etc...Ce peuvent être également, des quantités déduites des radiom tries mesu- rées , dans un seul domaine spectral d'un arrangement spatial déterminé de pixels , par une transformation linéaire définissant N canaux indépendants.

La digitilisation d'une image pour son trai¬ tement ou sa transmission fait apparaître un volume d'informations très élevé dont la manipulation, si l'on veut conserver une fidélité acceptable, pose toujours un problème.

Dans l'exemple de la télévision en couleurs, on considère que la densité et la précision d ' échantillon- nage pour la reproduction pratiquement sans distorsion d'une image couleurs, nécessitent 6 millions de bits envi¬ ron à raison de 16 bits par pixel. Le débit numérique d'une transmission télévisuelle sur cette base implique un canal de 170 M bits/seconde, soit l'équivalent de 2500 communi- cations téléphoniques. C'est un rapport qui est prohibi¬ tif au niveau des coûts actuels et qui pénaliserait lour¬ dement l'économie d un tel système de transmission.

On a donc été amené à évaluer des traitements numériques destinés à réduire ce débit et, pour ce faire. à éliminer dans la mesure du possible la redondance du message. Il s'agit pratiquement, d'éviter la répétition

des informations déjà transmises tant que les variations constatées, dans l'espace ou dans le temps entre échantillons voisins, sont inférieures à certaines valeurs définies en relation avec le niveau de qualité souhaitée (rapport signal à bruit, structures et fluctuations indésirables, sensibilité aux erreurs , etc . ) .

De nombreuses propositions, faisant appel aux techni¬ ques de codage différentiel, aux transformations orthogonales, aux codages statistiques et à leur combinaison, ont été expé- rimentées avec des succès divers, sans qu'aucune cependant se révèle totalement satisfaisante. On a également proposé (G. LO ITZ, "Reconnaissance des formes et traitement des images", Congrès AFCET-IRIA, 21-23 février 1978, pp. 699-714) un procédé mettant en oeuvre une technique fréquemment dési- gnée par le terme anglo-saxon "clustering" . Suivant ce procédé de codage numérique d'une image, notamment une image de télé¬ vision, on détermine, dans l 'image, des fenêtres ayant une forme géométrique prédéterminée et comprenant un certain nombre de points élémentaires ; on effectue, pour chaque fenêtre, des regroupements en classes de radiometries (spec¬ trales ou spatiales) des extrémités des vecteurs représenta¬ tifs des pixels ou des combinaisons de pixels de l'image, dans l'espace à N dimensions selon un critère de proximité ; on définit pour chaque classe, à partir des valeurs indivi- duelles des pixels qui la constituent, N radiometries typiques qui seront stockées ou transmises pour être utilisées à la reconstruction de l'image ; on stocke ou transmet également, pour définir chaque pixel , un code caractéristique de la classe à laquelle il appartient, permettant de lui affecter les radiometries typiques correspondantes pour la reconstruc¬ tion de 1 ' image .

L'invention a pour but, surtout, de fournir un procédé et un dispositif de codage numérique des images qui ne pré¬ sentent plus, ou à un degré moindre, les inconvénients rappe- lés ci-dessus et qui permettent notamment d'obtenir un taux de compression élevé.

OMPI

^

Dans ce but, l 'invention propose un procédé caracté¬ risé en ce que l 'on effectue un traitement de hautes fré¬ quences spatiales, par une transformation unitaire dont l 'un des coefficients, celui de la valeur moyenne correspondant à des fréquences spatiales plus basses, est associé aux compo¬ santes de canaux spectraux différents pour traitement par une classification complémentaire.

La notion de proximité dont on utilise une mesure comme critère de regroupement des pixels en classe doit être prise dans un sens très large qui sera précisé selon une application du procédé, comme on le verra par la suite. La métrique qui lui est associée doit en effet prendre en consi¬ dération le ou les critères de qualité essentiels à une reconstruction "satisfaisante de l 'image, qui peuvent être sensiblement différents selon le but recherché (par exemple, fidélité des contours, rendu des demi -teintes , forte diffé- rentiation des textures ou des couleurs, etc.) dans l'appli¬ cation envisagée.

Le critère de proximité peut être, par exemple, la distance, selon la métrique classique, dans l 'espace à N dimensions entre l 'extrémité du vecteur représentatif d'un pixel et l 'extrémité d'un vecteur représentant une classe ; dans ce cas, on peut établir, pour chaque fenêtre, plusieurs classes identifiées par un vecteur dont les N composantes correspondent à des valeurs prédéterminées des radiometries pour chaque canal de l 'image ; on calcule, pour chaque pixel , la distance dans l 'espace à N dimensions entre l 'extré¬ mité du vecteur représentatif de ce pixel et l 'extrémité de chaque vecteur représentant une classe ; on compare les dis- tances ainsi obtenues pour chaque pixel et on range ce pixel dans la classe correspondant à la distance obtenue la plus faible ; on stocke ou on transmet, d'une part, pour chaque pixel, un code permettant d'identifier la classe où il a été rangé et, d'autre part, un dictionnaire donnant, pour chaque classe, les composantes des vecteurs représentant cette classe,

O PI

obtenues par calcul à partir des différents pixels lui appar¬ tenant .

Ce procédé trouve son fondement dans les caractéristi¬ ques des images naturelles qui montrent la possibilité de grouper les pixels (points élémentaires) d'une sous-image (ou fenêtre) arbitrairement délimitée en un nombre restreint de classes judicieusement choisies. Chaque pixel p.eut dès lors être qualifié par un code à faible nombre de bits dont la signification est donnée par la table de conversion spécifique (dictionnaire) de la sous-image traitée.

Il s'agit donc de trouver, dans l'histogramme des radiometries d'une fenêtre (ou sous-image) , des groupes de points, rangés dans une classe déterminée, dont les valeurs radiométriques initiales peuvent valablement être remplacées par un groupe de valeurs radiométriques correspondant à celle de la classe.

Au lieu de transmettre ou de stocker pour chaque pixel, ou combinaison de pixels, les valeurs radiométriques trouvées, on lui fait correspondre un code (le numéro de la classe dans laquelle il a été rangé) dont le nombre est beaucoup plus restreint que l 'ensemble des radiometries possibles. Il suffit, pour rendre le message intelligible, d'ajouter à chaque fenêtre (ensemble de classes) un dictionnaire où chaque code de classe est explicité par ses radiometries correspondantes. Pour permettre une compression notable, il convient de traiter des sous-images (fenêtres) de volume suffisant pour que la transmission du dictionnaire de la table de conversion puisse être considérée comme marginale dans le volume global du message. De préférence, pour une fenêtre déterminée, après avoir effectué une première classification des points élémentaires dans des classes prédéterminées, et calculé, pour chaque classe, à partir des points qui ont été rangés dans cette classe, des radiometries typiques des points, on effectue une nouvelle classification de chaque point élémentaire, dans

OMH WTPO

de nouvelles classes basées sur les radiometries calculées, cette opération d'itération étant répétée autant de fois que nécessaire pour obtenir une précision prédéterminée.

On recherche ainsi, par une méthode adaptative, la meilleure radio- métrie représentative de chaque groupe de pixels rangés dans une classe de manière à n'introduire qu'une erreur négligeable dans le bilan énergétique de la transformation.

Il est clair que l'efficacité d'une telle classification est inti¬ mement liée aux propriétés statistiques de l'image aussi bien dans la distribution énergétique spectrale que spatiale. Il convient, pour tirer le meilleur bénéfice de ces statistiques, d'appliquer le procédé à des données homogènes, c'est-à-dire caractérisant l'un ou l'autre de ces domaines indé¬ pendamment. On pourra, par exemple, s'intéresser aux diverses composantes C. d'un même pixel dans des canaux spectraux différents et former les classes selon un critère de similarité spectrale. On peut aussi, en mono¬ chrome, définir les N canaux se référant à une distribution spatiale des pixels ou combinaison de pixels dans un groupe de forme convenable. Ce pro¬ cédé peut en effet s'avérer moins efficace si les deux types de données spectrales et spatiales sont classés simultanément en faisant ainsi inter- venir deux natures de statistiques différentes.

Le traitement de hautes fréquences spatiales généralement panchro¬ matiques, par une transformation unitaire dont l'un des coefficients, celui de la valeur moyenne correspondant à des fréquences spatiales plus basses, est associé aux composantes de canaux spectraux différents pour traitement par une classification complémentaire telle que décrite précédemment, apporte une solution à ce problème.

Pratiquement, dans le cas de la télévision en couleurs, et pour tirer le meilleur parti de l'image, on procède comme suit : on réunit plusieurs points élémentaires et on détermine, pour chaque réunion, une valeur moyenne des composantes de luminance et de chrominance C(Y)u (R—Y) _M , (B-Y)M] à partir de chaque composante de chaque point élémentaire de la réunion ; on effectue les opérations de classification évoquées précédem¬ ment ; et, pour une reconstruction de tous les points élémentaires à la réception, on applique aux signaux de luminance (Y), de chacun des points élémentaires d'une réunion, une transformation linéaire permettant de rédui¬ re le volume d'informations à transmettre, et l'on transmet les valeurs des

OMPI « ιθ

coefficients complémentaires résultant de cette transforma¬ tion et, à la réception, on effectue une expansion d'Infor- - mation en déduisant à partir des valeurs moyennes transmises [Y (R-Y) _M (B-Y) _M J et des valeurs transformées également transmises, les valeurs de luminance et de chrominance pour chaque point élémentaire d'un groupe.

La réunion des points peut porter sur quatre ou seize pixels contigus, qui sont groupés selon le type de sondage : orthogonal, quinconce ou trame, qui peut avoir été choisi. On définit ainsi deux domaines conjoints complémentaires en choisissant pour chacun d'eux le mode de codage le mieux adapté à leur nature.

Le premier domaine constitue un sous-ensemble poly¬ chrome dont chaque point correspond au point moyen d'une réunion et comporte des composantes obtenues avec une densité de sondage plus faible.

Le second domaine, nécessaire pour une reconstruction à pleine résolution, est constitué à partir des hautes fré¬ quences du signal de luminance Y seul sans aucune information de chromaticité.

Avantageusement, la transformation unitaire utilisée est une transformation de Walsh-Hadamard .

La fenêtre est constituée avantageusement par au moins une ligne horizontale ; dans le cas d'-une image de télévision, il est intéressant de former la fenêtre à l'aide de deux lignes contiguës. Avantageusement, le nombre de classes est égal à trente-deux.

L'invention est ég ^' alement relative à un dispositif pour la mise en oeuvre du procédé défini précédemment ; un tel dispositif est caractérisé par le fait qu'il comprend :

- des moyens pour déterminer une fenêtre dans l 'image en couleurs et pour balayer toute l'image par cette fenêtre ;

- des moyens d'acquisition des valeurs relatives à chaque point élémentaire d'une fenêtre ;

- des moyens de calcul des distances de l 'extrémité du vecteur correspondant à un point élémentaire ou à un point moyen de la réunion de plusieurs points élémentaires, aux extrémités des vecteurs identifiant chaque classe ; - des moyens comparateurs permettant de ranger chaque point élémentaire ou chaque point moyen dans la classe corres¬ pondant, à la plus faible distance calculée ;

- et des moyens de calcul des composantes du vecteur identifiant une classe à partir des différents points lui ap- partenant, la sortie de ce dispositif étant reliée aux moyens de transmission des données de sortie.

L'invention consiste, mises à part les dispositions exposées ci-dessus, en certaines autres dispositions dont il sera plus explicitement question ci-après à propos de modes de réalisation particuliers décrits en détail avec référence aux dessins ci-annexés.

DESCRIPTION SOMMAIRE DES DESSINS La Figure 1 est un schéma illustrant le procédé de 1 ' invention ; la Figure 2 est un schéma synoptique d'un dispositif pour la mise en oeuvre de ce procédé ; la Figure 3 est un schéma illustrant la réunion de plu¬ sieurs points élémentaires suivant un sondage orthogonal ; les Figures 4 à 6 sont des schémas de traitement d'images successives ; la Figure 7 est un organigramme du dispositif pour la mise en oeuvre du procédé ; les Figures 8 à 12 sont des schémas synoptiques plus détaillés de blocs du schéma de la Figure 7 ; la Figure 13 est un schéma synoptique des moyens utili¬ sés pour le décodage des données fournies après classifica¬ tion ; la Figure 14, enfin, est un schéma synoptique d'un opérateur pour la transformation linéaire.

OMPI

DESCRIPTION DETAILLEE DE MODES DE REALISATION

La description qui suit va être donnée, essentiellement avec référence à des images de télévision en couleurs, basée sur une analyse de l 'image en trichromie dans trois primaires "rouge" "verte" "bleue" alimentant trois canaux indépendants, pour des raisons de simplification ; la combinaison de ces trois primaires R, V, B fournit la luminance Y.

Dans cet exemple, le nombre N de canaux est donc égal à trois . Toutefois, le procédé et le dispositif de l'invention conviennent pour le traitement d'images avec un nombre de ca¬ naux inférieur ou supérieur à trois.

L'image de télévision en couleurs peut être considérée comme la combinaison de trois images primaires 11, 12, 13, représentées schematiquement sur la gauche de la Figure 1 correspondant aux trois canaux. Chaque image se compose de pixels répartis suivant des lignes ; les pixels de l'image 11 sont affectés des valeurs de radiométrie pour le premier canal , ceux de l'image 12 sont affectés des valeurs de radio- métrie pour le second canal, et ceux de l 'image 13 sont affectés des valeurs de radiométrie pour le troisième canal. Compression par classification

On détermine, dans l'image, des fenêtres f_ ayant une forme géométrique prédéterminée et comprenant un certain nombre n_ de pixels £. On établit, pour chaque fenêtre f_, plusieurs classes R1, R2 , ... schematiquement représentées, sur la droite de la Figure 1, par-des rangées. Chaque classe est identifiée par un vecteur d'un espace à trois dimensions (N = 3) dont les composantes correspondent à des valeurs prédéterminées des radiometries CI, C2, C3 pour chaque canal de 1 ' image .

On calcule, pour chaque pixel de la fenêtre f_, la distance D, dans l 'espace à trois dimensions, entre l'extrémité du vecteur représentatif de ce pixel et dont les composantes sont constituées par les radiometries

OMPI hs. ∞ -

affectées à ce pixel dans les trois canaux considérés, et l'extrémité de chaque vecteur identifiant une classe.

En fait, ce calcul devra être effectué en tenant compte de la nature de 1'application, ici la Télévision en couleurs où la qualité de l'image reproduite estjugée par un observateur humain dont 1'oeil présente des caractéristiques très particulières quant à la "fidélité subjective" de la reproduction. On pourra, en particulier, adopter dans l'espace à trois dimensions Y, R-Y,B-Y, des métriques non linéaires différentes adaptées à la sensibilité différentielle de l'oeil humain selon chacun de ces axes. Par exemple, la loi de Weber Fechner précise cette sensibilité dif¬ férentielle selon l'axe des luminances pour lequel une échelle logarithmique sera mieux adaptée qu'une échelle linéaire et per¬ mettra de calculer des "distances subjectives" plus satisfaisantes. ^" ; On pourra donc effectuer sur les radiom tries de chacun des ca¬ naux de telles conversions, à 1'aide de tables si 1'on ne dispose pas d'une loi mathématique simple de transformation. , avant de cal¬ culer la distance euclidienne dans l'espace transformé.

Par exemple, pour la classe RI, si 1'on désigne par Cil, C21 ,C31, les composantes du vecteur identifiant cette classe et par γli, γ2i, γ3i, les radiometries du ième pixel, la distance du vecteur représentant ce ième pixel au vecteur identifiant la

2 2 2 classe RI sera définie par : (Dli)= (Cll-γli) +(C21-γ2i) 2

(C31-γ3i)' Pour ce ième pixel, on calcule les distances relatives à toutes les classes, avantageusement au nombre de 32. On obtiendra donc 32 distances calculées Dli D32i.

On compare ensuite ces 32 distances de manière à détermi¬ ner la distance la plus faible et on range ce ième pixel dansla classe correspondant à cette plus faible distance, par exemple la classe R4.

Par la suite, on transmettra, pour ce ième pixel, unique¬ ment un code permettant d'identifier la classe R4 où il a été rangé. Ce code n'exige qu'un nombre de bits réduit par rapport à celui qui aurait été nécessaire pour transmettre les trois radio¬ metries correspondant à ce ième pixel.

OMPI

^

On transmet, en outre, un dictionnaire donnant, pour chaque classe R1, R32, les composantes C'1, C'2, C'3, du vecteur identifiant cette classe. Ces composantes transmises C' 1, C'2, C'3, sont obtenues par calcul , notamment calcul du barycentre, à partir des différents points appartenant à la classe.

Le procédé permet donc de faire correspondre aux trois fenêtres f_ (correspondant à chaque radiométrie primaire) de chacune n_ pixels, une carte unique de codes, associés à un dictionnaire où chaque code est explicité par les trois com¬ posantes (N composantes d'une manière plus générale) du vec¬ teur identifiant la classe correspondant au code. De préfé¬ rence, ces composantes correspondent à celles du barycentre des points rangés dans la classe considérée. Ces composantes pourraient cependant être déterminées par un autre mode de calcul (différent de celui du barycentre) , à partir des points rangés dans la classe.

Le schéma de la Figure 1 résume ces opérations. La classification, c'est-à-dire le rangement des pixels dans des classes déterminées, utilise une procédure par la¬ quelle on regroupe, dans un nombre limité de "classes", des pixels dont l'ensemble des composantes rouge, verte et bleue sont voisines et peuvent être confondues.

Ces classes ne sont pas définies arbitrairement mais adaptées à l 'histogramme à trois dimensions des radiometries d'une fenêtre f_ (ou sous-image) découpée dans l'image d'ori¬ gine. Si le nombre de pixels de la fenêtre f_ n'est pas trop élevé et si le nombre de classes n'est pas trop faible, on peut, en affectant à chaque pixel la valeur moyenne des radio- métries de la classe dans laquelle il est rangé, reconstituer une sous-image très voisine de l'original.

En procédant ainsi de proche en proche, par déplacement régul ^' ier de la fenêtre f_ pour balayer l 'ensemble de l'image, on peut assurer la transmission du message avec une dégrada- tion d'information très réduite.

O PI

Ce procédé permet une réduction notable du volume binaire du message par rapport à celui résultant de la numérisation des trois composantes rouge, verte et bleue.

En supposant qu'on réalise des fenêtres f_ comportant chacune 1024 pixels, caractérisés chacun par trois radiometries codées à huit bits, le volume initial est :

3 x 8 x 1024 = 24 Kbits. Avec le procédé de l'invention, on classe ces mêmes pixels dans trente-deux classes radiométriques différentes R1,... R32 et on désigne chaque pixel par le code (numéro)- de la classe où il est rangé ; il suffi¬ ra de cinq bits pour coder les trente-deux classes en question. On déli¬ vrera donc un premier message de 5 x 1024 bits.

Ce premier message est complété par le dictionnaire donnant la signification radiométrique de chacun des codes ; pour chaque code, il faudra transmettre trois radiometries mesurées chacune par huit bits, c'est-à-dire :

32 x 3 x 8 = 768 bits supplémentaires.

Finalement, avec le procédé qui vient d'être décrit, on trans¬ mettra : (5 x 1024) + 768 = 5888 bits.

Par rapport à la transmission du message initial, le procédé donne un taux de compression de :

(24 x 1024)/5888 = 4,17 environ. Cette valeur suffisamment élevée justifie le codage à l'émission et le décodage à la réception.

Le nombre de classes est un facteur important de la finesse de la classification et, par conséquent, de l'aptitude à approximer au mieux les valeurs radiométriques de l'original. Un nombre trop élevé de classes cependant diminue le taux de compression en raison du nombre de bits du code nécessaire pour numéroter chacune des classes. Il peut être avanta¬ geux de disposer d'un nombre de classes variable adapté à l'histogramme des radiometries de la fenêtre avec, en contrepartie, l'inconvénient d'un code à nombre de bits variables selon les fenêtres f_, ce qui implique un mode de transmission à régulation de débit peu souhaitable. On prendra généralement un nombre de classes fixe et correspon- dans à une puissance de 2 ; dans l'exemple envisagé, on a choisi

OMPI S>0

c

32 = 2 pour fixer la longueur du code à cinq bits. Cette valeur s'est révélée acceptable pour un grand nombre d'images de natures très différentes. Elle est cependant fonction d'un deuxième paramètre, à savoir le nombre de pixels constituant la fenêtre f_ de traitement ; ce nombre, sans être critique, influe sur la qualité de reproduction si le nombre de classes est limité. Il est clair que la variance d'une classe croît généralement avec le nombre de pixels lui appartenant, ce qui traduit une classification de plus en plus abusive. Il faut, cependant, un nombre de pixels suffisant pour permettre une bonne adaptation à la statistique de l'image. On a trouve expérimentalement que des fenêtres f_ de quelques centaines de pixels correspondent à un bon compromis.

La forme de la fenêtre découpée dans l 'image peut être variable pour autant qu'elle intéresse des zones contiguës où la redondance spatiale est maximale. Pour des images de télévision, dont la distribution spatiale est convertie en distribution sérielle dans le temps, il est intéressant de constituer les fenêtres à partir des lignes de balayage de l'image ; c'est pourquoi dans l 'exemple évoqué précédemment, on a indiqué que la fenêtre f_ est formée par deux lignes continguës. On peut alors traiter successivement l'ensemble des pixels d'une ou plusieurs lignes dans un format récurrent et continu qui facilite la mise en oeuvre du procédé. Le nombre de pixels de la fenêtre peut ainsi varier entre 300 et 1500, selon la finesse de sondage nécessaire, dans les limites convenables pour une bonne statistique des radiometries.

Pour une fenêtre déterminée f_, après avoir effectué une première classification des n_ pixels dans les 32 classes R1 , ... R32, on calcule, pour chaque classe R1,... à partir des pixels qui ont été rangés dans cette classe, le barycentre de ces pixels. On. peut effectuer une nouvelle classification de chaque pixel de la fenêtre dans les 32 nouvelles classes basées sur les barycentres ainsi calculés. Cette opération d'itération est répétée

O PI

autant de fois que nécessaire pour obtenir une préci¬ sion déterminée.

Par exemple, si g_ est le nombre de pixels rangés dans la classe R4 qui, lors du premier passage était identifiéepar un vecteur dont les composantes étaient C14, C24, C34, le calcul du bary¬ centre, après le premier passage va conduire à identifier la classe R4 par un nouveau .vecteur dont les composantes seront : i = q

C 14 = Σ - γii q i = q

C'24 = Σ γ2i q i = q

^" 1• = 1• Y3i

C'34 q

Les valeurs γli,γ2i, γ3i correspondent aux trois composantes <^ chacun des q pixels contenus dans la classe R..

On engage ainsi une phase d' adaptitivité en recalculant les barycentres de chacune des classes qui serviront pour le passage suivant d'itération en vue d'améliorer le classement des pixels de la fenêtre par rapport à ces nouveaux barycentres. On peut affiner le résultat par des itérations successives dont la conver¬ gence est rapide.

Lorsque le classement des pixels de la fenêtre est terminé, on effectue la transmission des codes, pixel par pixel, dans l'ordre prédéterminé par le ba¬ layage, puis le dictionnaire relatif à ces codes est transmis ; selon une variante, on peut transmettre le dictionnaire relatif aux code= en premier, puis les codes pixel par pixel.

ζ îR Λi

OMPI

L'opération est renouvelée pour la fenêtre sui¬ vante et ainsi de suite jusqu'à la fin de l'image. On voit que l'algorithme de classement utilisé exige une initialisation des classes RI R32 qui peut être obtenuepar exemple par une distribution régulière dans 1' espace.

Il est avantageux d'utiliser des résultats de calcul antérieurs comme base d'initialisation de la clas¬ sification suivante pour bénéficier de la forte cor- relation spatiale d'une ligne à la suivante, ou de la corrélation temporelle d'une image à la suivante. En particulier, on pourra traiter plus efficacement la pre¬ mière ligne de l'image en utilisant les barycentres obtenus lors de la classification de la même ligne de 1' image précédente dans le temps.

Les systèmes de télévision analogique consti¬ tuent des cadres bien définis par leur norme de balayage (cadence, nombre de lignes) , le codage couleurs (NTSC, SECA , PAL) et de radiodiffusion qu'il est souhaitable de conserver au moins à un certain niveau sous peine de devoir introduire des appareillages compliqués pour l'interface compatible. La télévision numérique s'adapte mieux aux besoins des utilisateurs en conservant le découpage sériel en lignes successives d'analyse et, pour la couleur, en traitant en parallèle trois compo¬ santes caractéristiques Y, R - Y, B - Y, pour chaque pixel, définies à partir des composantes primaires rouge (R) verte (V) et bleue (B) par les relations suivantes Y = 0,59 V + 0,30 R + 0,11 B R - Y = 0,70 R - 0,59 V - 0,11 B

B - Y = 0,89 B - 0,59 V - 0,30 R. Le signal Y, ou signal de luminance, peut être considéré comme la version panchromatique de l'image ; les deux autres signaux R - Y et B - Y sont spécifiques de la chromaticité.

Cette répartition de l 'information permet une discré¬ tisation du message en effectuant un sondage périodique de ces trois signaux à des cadences régulières ( 13,5 MHz pour Y; 6,75 MHz pour R-Y et B-Y) de manière à numériser à 256 niveaux (8 bits) leurs valeurs sans dégradation sensible de qualité. Ceci correspond à 720 pixels de luminance Y pour la partie active de la ligne de balayage.

On voit que le sondage de la chromaticité est effectué avec une densité moitié de celle de la luminance Y, soit 360 échantillons R-Y et 360 échantillons B-Y, mais reste largement suffisant cependant pour le niveau de qualité recher^ ché .

On peut considérer que ce format conduit à étendre la chromaticité d'un pixel _i_ au pixel i+1 suivant dans la ligne ou, si l'on préfère, à assimiler le pixel de chromaticité à un rectangle recouvrant deux pixels de luminance ^" adjacents. La même assimilation dans le sens vertical peut être faite, ce qui conduit à un sondage de chromaticité quatre fois moins dense que celui de la luminance Y, mais encore très suf- fisant pour des images naturelles. On sait d'ailleurs que la reproduction n'exige pas une définition aussi élevée pour la chrominance que pour la luminance.

Différence de traitement entre luminance et chrominance Pour tirer le meilleur parti de la redondance de l 'image, on définit deux domaines conjoints et complémentaires en choisissant pour chacun d'eux le mode de codage le mieux adapté .

1. Le premier domaine constitue un sous-ensemble tri- chrome dont chaque pixel comporte les trois composantes Y, R-T, B-Y obtenues avec une densité de sondage quatre fois plus faible que celle de Y. Ce premier domaine décrit une image précise des basses fréquences spatiales des trois images R, V, B de l 'analyse trichrome.

Les quantités transmises Y _M , (R-Y) _M et (B-Y) _M sont les composantes du vecteur dont on va effectuer la classification selon le procédé expli¬ qué précédemment, pour ce premier domaine.

Pour chaque fenêtre, on transmettra deux messa¬ ges :

- la suite des codes des pixels successifs, ces codes permettant d'identifier la classe dans laquelle chaque pixel a été rangé r

- le dictionnaire donnant la correspondance entre le code de chaque classe et les valeurs de Y M,,, (R - Y) M„ et

(B - Y) du modèle, pour permettre la reconstruction de l'image basse fréquence. 2. Le second domaine nécessaire pour une recons¬ truction de l'image à pleine résolution va être constitué à partir des hautes fréquences du signal de luminance Y seul, sans aucune information de chromaticité.

Une bonne approximation du signal Y est ob- tenue en faisant la moyenne des luminances d'une réunion de plusieurs pixels contigus du sondage Y initial. Avantageusement, on réunit4 pixels selon le type de sondage orthogonal comme représenté sur la figure 3 ; les pixels numérotés 0 et 1 sont situés respectivement aux lignes n+2 et n+1 sur une même verticale,- les pi¬ xels 3 et 2 sont situés sur les lignes n+2 et n+1 immédiatement à droite du pixel 0 et 1.

La réunion des pixels pourrait se faire selon un autre type de sondage par exemple quinconce ligne ou quinconce trame.

Si l'on désigne par Y. , Y , Y , Y les luminances des pixels 0, 1, 2 et 3, la valeur moyenne Y., sera :

_Y = 0 1 2 3

" ₄ Les autres quantités (R - Y) et (B - Y) sont obtenues à partir des valeurs moyennes e chrominance des pixels de la réunion effectuée' avec :

OMPI

1

( R-Y) _M = (R-Y) (R-Y) 2

(B-Y) _M - (B-Y) ₁ + (B-Y) 0

2

En effet, le sondage pour les composantes caractéris¬ tiques R-Y et B-Y est effectué à une cadence (6,75MHz) moitié de celle du sondage Y ( 13,5 MHz) et l 'on considère que les pixels 2 et 3 de la réunion de quatre pixels représentée' sur la Figure 3 ont les mêmes caractéristiques de chrominance que les pixels immédiatement voisins 1 et 0 du sondage. Transformation unitaire préalable sur les signaux de luminance En vue d'une reconstruction de tous les pixels à la réception, on applique aux signaux de luminance Y de chacun des pixels d'une réunion effectuée comme représenté sur la Figure 3, une transformation unitaire permettant de réduire le volume d'information à transmettre, tandis qu'à la récep- tion, on effectue une expansion d'information pour reconsti¬ tuer chaque point élémentaire.

La transformation linéaire utilisée est avantageusement une transformation de Walsh-Hadamard . Elle sera envisagée appliquée à la réunion des quatre pixels 0, 1 , 2 et 3 de la Figure 3, mais elle peut aussi bien être appliquée à la réu¬ nion de seize pixels répartis dans une matrice carrée par exemple .

La luminance moyenne Y est égale à la moitié de la pre¬ mière composante WH _Q de cette transformation puisque :

On code les quatre valeurs Y _n , Y. Y ₂ et Y en leur appliquant la transformation évoquée, c'est-à-dire que l 'on complète la description de Y par les trois composantes complé¬ mentaires représentatives des hautes fréquences :

WH 1/2 (Y. WH V

= 1/2 (Y, ^Y 3 ^{" Y} 0 ⁺ V

WH, = 1/2 (Y - Y„ + Y

On peut remarquer que les valeurs moyennes de chrominance corres¬ pondent à la première composante de la transformatée de Walsh-Hadamard,

OMPI

c'est-à-dire au terme de basse fréquence qui est donc seul utilisé.

L'avantage de ce type de codage réside dans la décorréla¬ tion des coefficients qui en résulte, ce qui assure une réduction de la redondance spatiale sur le groupe de quatre pixels 0, 1, 2, 3. On peut ainsi réduire le volume d'informations à transmettre en introduisant une codification adaptée à chacun de ces coefficients WH., H , ^WH 3 _> grâce à une attribution de bits optimisés pour chacun.

L'expérience montre, en effet, que l'histogramme des valeurs de ces coefficients dans une image présente une décroissance rapide, d'allure exponentielle, en fonc¬ tion de leur amplitude si bien qu'il est avantageux d'é¬ tablir une loi de quantification à échelons non linéaires permettant d'affecter les codes aux valeurs les plus probables. La reconstruction postérieure fait apparaître des erreurs mais 1 ' écart quadratique moyen peut être maintenu dans des limites acceptables si l'on choisitune loi bien adaptée à l'échantillon des valeurs de la fenêtre à considérer. L'objectif d'un taux de compression élevé conduit à des dispositions particulières pour obtenir une bonne adaptation à la statistique de la distribution des valeurs dans chaque fenêtre.

Une possibilité consiste à définir des tables de quantification non linéairestypiques mais judicieuse¬ ment sélectionnées, éventuellement à nombre de niveaux et nombre de bits variables , et à choisir parmi elles celle qui permet d'obtenir le meilleur résultat c'est-à- dire la reconstruction la plus fidèle de la fenêtre. Il faut alors disposer de l'ensemble des tables de re¬ construction et indiquer, par un code spécial, affecté à chaque fenêtre, celle dont la loi a été choisie au codage pour quantifier les coefficients des groupes de pixels de la fenêtre.

Une autre solution, un peu plus coûteuse en volume binaire, mais permettant une adaptation plus fine à la distribution réelle des coefficient H. , WH ,

WH, de la fenêtre consiste à effectuer, sur chacun d'eux, une classification analogue à celle des basses fréquences trichromes. Il s'agit seulement ici de regrouper en classes des grandeurs à une dimension et non des vecteurs à plusieurs dimensions ce qui simplifie les calculs mais la procédure reste la même : - initialisation des classes ,

- regroupement par classe des valeurs de la fenêtre,

- calcul de la moyenne de chaque classe,

- itération.

On devra donc transmettre, pour chaque groupe de pixels de la fenêtre, trois codes correspondant à WH , WH et WH_, ainsi qu'un dictionnaire spécifique de chaque fenêtre fournissant les valeurs moyennes de reconstruction de chaque classe, à utiliser selon le code. Une distribution de bits ayant donné de bons résultats consiste à affecter 8 classes et donc un code

3 a 3 bits (8 = 2 ) à chacun des coefficients WH. et WH .

2 classes seulement, nécessitant un code à un seul bit, suffisent pour le coefficient WH- dont la dynamique est sensiblement plus faible.

Au total (2 x 3) + 1 = 7 bits sont nécessaires par réunion de 4 pixels, ces 7 bits devant être complé¬ tés par le dictionnaire des (2 x 8) = 16 classes

( environ 64 bits) ^• - de WH et WH et de la valeur moyenne du module de WH,. En effet, le bit unique transmis pour WH_ est un bit de signe.

Or. peut noter, à ce stade de la description, donnéeà titre d'exemple, que la combinaison des codages du domaine trichrome et du domaine des hautes fréquences de luminance peut être paramétrée différemment selon le type d'application, les débits numériques acceptables ou

OMPI

modalités de réalisation, sans toutefois sortir du cadre de 1 ' invention.

Il peut s'avérer souhaitable, par exemple, en vue de préserver la qualité de manipulations ultérieures, de pouvoir disposer, après codage, et décodage de la pleine résolution chromatique de l'image, c'est-à-dire celle correspondant à un échantillonnage de toutes les compo¬ santes à 13,5 MHz. On devra alors traiter tous les pixels comme faisant partie de l'espace trichrome sans aucune transformation complémentaire de l'espace luminance.

La classification portera sur- les valeurs Y,R - Y, B - Y de chaque pixel (ou R, V, B) fournissant 720 codes par ligne d'analyse et un dictionnaire des valeurs représentatives de chaque classe par fenêtre. Il sera alors avantageux de définir la fenêtre en question comme une ligne d'analyse unique au lieu d'un couple de deux lignes, comme précédemment, pour éviter la mémori¬ sation d'une trame de balayage.

Du fait de l'analyse par balayage entrelacé de l'image télévisuelle, en effet, on doit disposer, pour les 2 modes de traitement, classification et trans¬ formation, d'une fenêtre formée par 2 lignes contiguës, des valeurs relatives à deux trames successives auxquelles appartiennent respectivement les lignes n+1 et n+2 de la figure 3. On prévoit donc le chargement et la lec¬ ture d'une mémoire d'image pour chacune des composantes Y, R - Y et B - Y d'une trame chargée et lue en temps réel en même temps que le canal délivre le flux corres¬ pondant de la trame suivante. Il en résulte un délai global d'une trame soit 20 m sec . entre l'entrée et la sortie d'une image dans le système de codage. Diver¬ ses stratégies peuvent être envisagées selon le débit du canal de transmission, l'architecture des moyens de codage et de décodage et leur niveau de complexité.

O PÏ

A titre- d'exemple, on peut concevoir un système où l'image est rafraîchie à la cadence trame du signal télévision, soit 50 par seconde, c'est-à-dire en trans¬ mettant de façon continue, au rythme d'entrée des pixels, les diverses composantes de classification trichrome basse fréquence et la transformation WH (Walsh-Hadamard) de haute fréquence.

Dans ces conditions , on dispose également en permanence à la réception de tous les signaux nécessaires à la reconstruction sans avoir besoin de moyens de stoc¬ kage important. Il en résulte, en contrepartie, un débit numérique relativement élevé parce que redondant dans le domaine temporel.

Variante : On peut aussi envisager, si la finesse de réso- lution chromatique peut être notablement inférieure à celle de la luminance, d'appliquer une transformation unitaire d'ordre supérieur à 2 au domaine des hautes fréquences de luminance en réunissant par exemple 16 pixels de luminance dans un ensemble 4 ^' x 4 dont la valeur moyenne sera codée avec les composantes chromatiques correspondantes par classification. Une autre solution peut aussi consister à conserver la transformation d'ordre 2 et la classification d'une réunion de 4 pixels mais choisis sur la même trame d'analyse entrelacée ce qui évite également la mémorisation.

Dans une autre conception préférée, on pourra, au contraire* découper le message entre les deux modes décrits et, par exemple, pendant une trame fournir les composantes de classification, la trame suivante étant affectée à la transmission de 1 ' autre sous-ensemble de composantes HF. Si l'on s'arrange pour avoir deux sous- messages de volume équivalent, le débit de transmission est divisé par 2, mais la reconstruction implique l'uti¬ lisation pendant deux trames de chacun des sous-ensembles qui devront être stockés temporairement. Le rafraîchis-

sèment de l'image est alors celui de la cadence de 'ïeux trames soit 25 par seconde.

La fenêtre de description f, donnée en exemple et constituée de deux lignes contiguëssur l'image (l'une appartenant à la trame paire, l'autre à la trame impaire) permet de respecter, autant que possible, la segmentation déjà imposée par le balayage d'analyse du standard de télévision, aussi bien dans le temps que dans l'espace, et constitue une version préférée du système de trans- mission. On traite ainsi continûment les données au fur et à mesure de leur disponibilité, en parallèle» oar deux opérateurs indépendants appliqués aux deux domaines basse fréquence trichrome et haute fréquence luminance. Ceci permet la plus grande souplesse dans l'organisation du format de transmission et, en particulier, permet, sans difficulté, l'attribution du canal de transmission à l'un ou l'autre sous-message alternativement comme indiqué ci-dessus.

En outre, lorsque le débit du canal de transmis¬ sion est suffisant, on peut aussi multiplexer les deux messages pour éviter les mémoires côté réception.

Dans la même optique, on peut définir, pour une fréquence de sondage donnée et pour chacun des sous- messages, un paquet de données de structure bien définie et de longueur fixe fournissant dans l'ordre naturel de succession des pixels, les codes de classification ou les composantes de WH de la ligne d'analyse correspon¬ dante au numéro du paquet dans la suite Ges données relatives à une trame complète. Cette possibilité garantit une grande sécurité de fonctionnement et pré- sente l'avantage de ne nécessiter aucune régulation de débit en fonction du contenu de l'image.

Si la capacité de transmission est suffisante, il peut également s'avérer intéressant de respecter pour chaque paquet le cadencement de 1'analyse à fréquence

ligne du signal télévision. Le volume des blocs mémoire de stockage intermédiaire est ainsi minimisé et l'in¬ tervalle de suppression de trame est conservé disponible pour d'autres messages tels ceux déjà existants dans le signal analogique.

On va considérer, maintenant, les dispositifs pour la mise en oeuvre du procédé de l'invention.

Les opérations nécessaires au codage et au décodage d'une image peuvent être effectuées à l'aide de différents moyens selon les contraintes imposées par divers paramètres dont les plus importants sont la ca¬ dence de fourniture des pixels par le dispositif amont, le volume de composants électroniquesacceptable, le ni¬ veau d' adaptabilité de l'équipement à des variations de paramètres fonction des conditions opérationnelles. On peut, par exemple, si l'on accepte un temps de codage important, envisager un traitement entièrement effectué par un opérateur unique microprogrammable ou, au contraire, si l'on recherche la rapidité maximale, une combinaison d Opérateurs câblés montés en série- parallèle pour n'introduire aucune attente dans le flux de données entre chaque opération élémentaire. Entre ces deux possibilités extrêmes, toute une gamme de combinai¬ sonsmixtes peut être envisagée. Comme représenté sur la figure 2, les diverses variantes entrant dans le cadre du procédé peuvent être réalisées à partir de deux sous-ensembles électroniques 10, 11 affectés, l'un 10 à la classification, l'autre 11, à la transformation, et fonctionnant dans deux voies parallèles.

Un dispositif 12 d'acquisition et de démultiple¬ xage, situé en amont, sépare et aiguille, en fonction du temps selon la loi de codage définie, les divers données vers la ou les voies convenables pour leur traitement. Ces données sont fournies par des moyens 13 pour

déterminer la fenêtre et pour balayer l'image ; ces moyens 13 peuvent comprendre par exemple, une caméra video combinée avec un convertisseur analogique/digital et des moyens de mémoire fournissant des mots de huit bits correspondant aux caractéristiques Y, R-Y, B-Y. On peut supposer que les données arrivent aux moyens d'acquisition 12 par un bus à vingt-quatre bits fournissant, à la cadence pour chaque pixel, les caractéristiques Y, R-Y et B-Y. Ces trois caractéristiques sont nécessaires pour le traitement de classification par 10 de l'espace trichrome alors que seule la première donnée Y intervient dans le traitement des hautes fréquences par 11. Dans le cas où seule une classification serait effectuée (sans transformation), le sous-ensemble 10 serait seul à intervenir.

En sortie des sous-ensembles 10 et 11, un organe de mutliplexage 14 des produits de codage permet de construire le message de transmission. En ce qui concerne le traitement de classification trichrome, l'ana- lyse des diverses opérations impliquées dans le codage d'une fenêtre fait apparaître deux types de procédures A,B.

D'une part, des opérations de type A (transformation unitaire) sont effectuées au niveau d'un pixel ou d'une réunion (telle que celle représentée sur la Figure 3) de pixels. D'autre part, des opérations dites de type B ("clustering") sont appliquées à la fenêtre dans sa totalité.

En outre, ces deux types de procédure doivent être nécessairement effectués successivement car les résultats obtenus dans le premier type A doivent être complètement disponibles avant d'entamer le deuxième de type B. Enfin, comme il s'agit de préférence d'un dispositit itératif au niveau de la fenêtre, il faudra avoir aussi totalement terminé le premier passage avant de pouvoir entamer le deuxième passage marqué par une nou¬ velle initialisation des composantes des vecteurs identifiant chaque classe de la fenêtre. Au niveau des moyens pour réaliser ces opérations, on prévoit une cascade d'opérateurs formant une chaîne fonctionnelle continue, en prenant soin de limiter les temps morts entre chacun pour réduire le temps de traitement. Corrélativement, si certains opérateurs sont susceptibles d'introduire un ralentissement du débit, on crée avantageusement des chaînes parallèles à ce niveau

pour maintenir un débit de traitement constant.

L'utilisation optimale des organes matériels devant être assurée, on recherchera un fonctionnement permanent de tous les opérateurs sans phase inactive. Cela est possible à condition d'effectuer un brassage du flux de données relatives à une fenêtre entre des opérateurs du type A et des opérateurs du type B en nombres convenables pour tenir compte de leur vitesse de traitement relative. Cette organisation conduit à une gestion des moyens telle qu _e ι _a chaîne fonctionnelle ne coïncide plus nécessairement avec une chaîne matérielle déterminée. En particulier, une itération pourra utiliser des opérateurs différents de ceux du premier passage dans la mesure où ceux-ci ont pu être affectés au trai¬ tement d' une nouvelle fenêtre.

Les figures 4 et 5 donnent deux exemples d'utili¬ sation optimale des opérateurs de type A et de type B. Dans les deux cas, ces opérateurs ont été pré- vus de manière à ce que chacun soit capable de traiter une fenêtre en un temps τ correspondant à la cadence vidéo.

Dans la figure 4 , les coefficients servant à initialiser la fenêtre b de l'image i. sont les résultats obtenus à l'issue du traitement de la fenêtre précédente (b - 1) de la même image i. Les opérateurs A fonctionnent donc pour (i,b) pendant un premier intervalle de temps

0,τ puis les opérateurs B pendant j ,2τ J puis les opé¬ rateurs A sur (i, b + 1) pendant τ, 3τj , et ainsi de suite. Chacun des opérateurs est donc occupé à 50 % du temps, pour l'image i, et le traitement complet de l'i¬ mage se fait à moitié de la cadence temps réel. Les 50 % de temps restant peuvent être utilisés pour traiter une autre image, i + 1 par exemple. La seule précaution con¬ siste à décaler les traitements de i et de i + 1 de a-

nière à ce que l ' initialisation des coefficients pour la première fenêtre de chaque image puisse utiliser les résultats ^• de la première fenêtre de l ' image précédente. On traite donc deux images simultanément à demi cadence temps réel ce qui équivaut au traitement d ' une image en temps réel .

Une mémoire tampon est nécessaire dans ce mode .

Dans la figure 5, les coefficients servant à initialiser la fenêtre de l ' image i+1 sont les résultats obtenus à l ' issue du traitement de la même fenêtre b sur 1 ' image i .

La fenêtre (i, b) est traitée successivement par A puis par B et les résultats sont mémorisés jusqu'à 1' arrivée de la fenêtre (i + 1, b) .

Il convient de noter que ce deuxième mode se prête à un traitement parallèle, bien adapté à l'emploi de processeurs microprogrammables. En effet, la seule con¬ trainte de temps tient au fait que le résultat des étapes A et B sur (i, b) doit être disponible avant l'arrivée de (i + 1, b) . A la limite, il peut donc y avoir autant de chaînes de traitement A + B indépendantes qu'il y a de fenêtres dans une image, chacune traitant une fenêtre pendant le temps d'une image. Plus généralement, s 'il y a 2 fenêtres dans une image, on peut concevoir q chaînes k indépendants de type A, 5_ chaînes indépendantes de type k'

B, sans que k et k' soient nécessairement identiques

(voir figure 6 ) .

En se reportant à la figure 7, on peut voir le schéma synoptique de fonctionnement du sous-ensemble de classification désigné par 10 sur la figure 2. La pro¬ gression s'effectue du haut en bas de la fig. 7, entre un bus d'entrée 15 et un bus de sortie 16. Après acqui¬ sition des données relatives à une réunion de pixels (selon la Fig. 3 par exemple) , les moyennes des luminances et chrominances sont calculées. Il y a ensuite calcul des distances de l'extrémité du vecteur, ayant pour compo-

OMPΓ

santés ces valeurs moyennes, aux extrémités des vecteurs identifiant les classes qui ont été initialisees. Chaque point est rangé dans la classe correspondant à la plus faible distance (regroupement) . Les points de chaque classe sont comptés (histogrammes ) .On passe ensuite à l'opération B concernant toute la fenêtre.

Les barycentres de chaque classe sont calculés (barycentres) puis les variances de chaque classe (va- riances) . II y a ensuite un test de classe vide. On pro¬ cède à la détection de la ou des classes dans lesquelles aucun point n 'a été rangé.

Si au moins une telle classe existe, on effec¬ tue une "séparation", consistant en une création de nou- velles classes par dédoublement de la classe ayant la plus grande variance.

Ceci est obtenu automatiquement en définissant, à partir du barycentre de cette classe ayant la plus grande variance, deux valeurs d'initialisation diffé- rentes symétriques βt distantes d'au moins un pas de quantifica¬ tion en plus ou en moins dans toutes les directions. On a ainsi deux valeurs nouvelles qui définissent nécessairement deux classes indépendantes au cours de l'itération postérieure. L'opération est renouvelée s'il existe encore une classe vide après le premier dédoublement.

On est ainsi assuré d'utiliser, pour chaque fe¬ nêtre, la totalité des classes disponibles et cette pré¬ caution est une source d'amélioration sensible des performances du système.

Les nouvelles composantes des vecteurs identi¬ fiant les classes sont utilisées pour une nouvelle initialisation en vue d'une itération.

Si aucune classe n'est vide, on procède à un test de seuil So pour décider s'il y aura, ou non, une itération. Par exemple, ce test de seuil peut con-

OMPI

sister à effectuer la somme des variances de chaque classe et à comparer cette somme à une valeur prédéter¬ minée So.

Si la somme des variances est supérieure à S , une opération d'itération est commandée.

Si la somme des variances est inférieure ou égale à S , la classification est considérée comme satisfaisante et il y a transfert des codes, dans l'ordre des pixels, et transfert du dictionnaire des classes, par le bus de sortie 16 vers un système d'utilisation par exemple un système de transmission ou un système de stockage.

On a étudié, sur divers matériaux la convergen¬ ce de la classification en fonction des divers para- mètres qui interviennent dans les performances du servo¬ mécanisme que constitue l'algorithme décrit (gain de boucle, constante d'intégration, erreur résiduelle). Il apparaît qu'à partir d'une initialisation uniforme ar¬ bitraire, et sans aucune itération sur chaque fenêtre, il faut traiter une dizaine de fenêtres successives, chaque fenêtre fournissant le sous-ensemble d'initiali¬ sation de la suivante, pour obtenir un "régime permanent" caractérisé par une erreur quadratique moyenne de re¬ construction relativement stable. Si cette manière de procéder peut être envisa¬ gée lorsqu'on traite un message continu d'un grand nombre de fenêtres successives dont les premières peuvent sup¬ porter des erreurs importantes, elle semble exclue dans le cas d'images répétitives du genre télévision où l'on recherche une qualité identique sur la totalité de 1'image.

On prévoit donc, comme déjà signalé, d'une part l'initialisation à partir de la ligne ou de l'image pré¬ cédente mais aussi, pour chaque fenêtre, une phase d'a- daptivité consistant à calculer, après le premier pas¬ sage, les barycentres des points de chaque classe de

la fenêtre pour itérer le processus et affiner encore la classification. On a constaté que l'erreur quadra¬ tique de reconstruction diminue après la première itéra¬ tion et se stabilise après 2 ou 3 itérations, selon la variabilité de l'image.

La contrepartie de ces opérations d'itération est 1 'augmentation par un facteur 2, 3 ou 4 du temps de traitement puisqu'il faut traiter chaque fois la fenêtre complète avant de pouvoir entamer une nouvelle itération. On recherchera un compromis acceptable entre la précision et le temps nécessaire pour l'obtenir.

Les systèmes de transmission utilisés, à partir du bus 16, doivent respecter un format permettant de retrouver, dans le flux de données, les codes de chaque réunions particulières de pixels d'une fenêtre et le dic¬ tionnaire correspondant. La solution la plus simple consiste à fournir, d'une part, la suite des codes dans l'ordre de succession des pixels dans la fenêtre, c'est-à-dire le long de la ligne d'analyse TV et, d'autre part, les valeurs des composantes de chaque classe par exemple dans l'ordre des codes croissants.

On obtient ainsi des paquets de longueur fixe qui pourront être facilement reconnus et traités dans l'opérateur de décodage. un autre avantage de cette organisation du mes¬ sage réside dans l'indépendance totale des fenêtres entre elles, en particulier au niveau des codes et du dictionnaire. Toute erreur n 'affecte donc au'un seul pixel si elle porte sur les codes et n'affecte qu'une seule fenêtre si elle porte sur le dictionnaire. On peut donc présager une bonne protection contre la propagation des erreurs. En outre, une procédure de protection simple du dictionnaire, sans correction des erreurs, est suf-

^« £JREΛ

OMPI

fisante si l'on accepte, en cas de détection d'erreur, d'utiliser le dictionnaire de la fenêtre précédente qui présente de grandes analogies du fait de la méthode d'initialisation et de la corrélation spatiale entre fenêtre. En se reportant aux figures 8 à 12, on peut voir des exemples de circuits pouvant constituer les opérateurs élémentaires désignés sur la figure 7.

La figure 8 montre un opérateur pour effectuer l'acquisition des données et le calcul des moyennes. Les données d'entrée étant supposées fournies avec un échan¬ tillonnage de 8 bits, le bus d'entrée 15 ou bus de données comporte 9 fils (8 fils pour les bits de données et 1 fil pour 1 bit de validation) par canal. Dans le cas de trois canaux, le bus 15 comporte donc 27 fils. Les fils du bus alimentent un accumulateur 17 que l'on charge à la demande lorsqu'apparaissent les va¬ leurs relatives au pixel courant, ces valeurs venant d'un convertisseur analogique digital ou d'une mé¬ moire de trame précédemment chargée.Il y a autant d'ac- cumul teurs 17 que de canaux ; dans l'exemple considéré, de la télévision en couleurs à trois canaux, il y a donc 3 accumulateurs 17 correspondant auxcomposantes Y, B - Y et R - Y. Chaque accumulateur 17 fait la sommation des radiometries qui le concernent, pour 4 pixels de types 0, 1, 2 et 3 tels que représentés sur la figure 3.

Dans le cas représenté sur la figure 8, l'accu¬ mulateur 17, situé le plus à gauche, destiné à la compo¬ sante Y est à 10 bits en sortie, tandis que les deux autres accumulateurs affectés aux deux autres compo- santés B - Y et R - Y sont à 9 bits en sortie.

Un décalage (shift) de bits permet de délivrer les valeurs moyennes du pixel courant i dans des registres

18 où s'inscrivent donc les valeurs Y M.,i., (B - Y).M.i., (R -

La figure 9 montre un opérateur "distances"/ des- tiné à calculer, pour chaque pixel i les valeurs :

et à faire leur somme qui est égale au carré de la distance de l'extrémité du vecteur représentant le pixel i au barycentre de la classe k.

Les valeurs des quantités Y , (R - Y). / (B - Y). sont fournies à partir de la mémoire d'initialisation 19 (Fig.7)sous- fornecomplémentée à 3 accumulateurs distincts 20, affectés à chacun des 3 canaux, accumulateurs qui reçoivent également les valeurs Y„. (R - Yl.. et (B - Y)„. Une table de conversion "carré" , notamment formée par une mémoire PROM, est alors lue à l'adresse fournie par la différence donnée à la sortie de chaque accumu¬ lateur 20 ; la table de conversion 21 fournit sur sa sortie la valeur du carré correspondant, c'est-à-dire

2 2 2 les valeurs respectives Dy , DR_ , D„B . On effectue alors dans un dernier accumulateur 22, la somme des carrés re¬ latif aux 3 canaux ; cette somme est chargée dans un registre 23.

Selon la cadence de fourniture des données et la rapidité des circuits utilisés on pourra effectuer ces calculs pour chacune des 32 classes en série ou en pa¬ rallèle ou toute combinaison série-parallèle envisageable, l'objectif étant de disposer pour l'opérateur suivant de 32 registres tels que le registre 23, chargés par les distances relatives aux 32 classes initialisees.

La figure 10 donne un schéma d'un opérateur pour effectuer le regroupement des points. Cet opérateur est destiné à déterminer, à partir des 32 distances calculées par l'opérateur de la figure 9, laquelle est la plus faible ; cet opérateur doit également désigner cette distance par le code de la classe correspondante.

Avantageusement, on associe à la valeur de chaque registre distance (tel que le registre 23 de la fig. 9) ,

5 bits supplémentaires de poids faible, caractéristiques de la classe concernée par la distance ; sur la figure 10 on a représenté, schematiquement,par un grand rectangle s les valeurs des distances Dl, D2 et par un petit le code de la classe, rectangle contigu numéroté 1, 2...... et situé immédiate¬ ment à droite des grands rectangles. Un premier étage de comparateurs 24 est prévu pour effectuer la comparai¬ son 2 à 2 de toutes les distances, ce qui donne 16 ré¬

10 sultats sur les sorties des comparateurs 24, correspon¬ dant atxplus faibles valeurs des deux termes comparés. Un deuxième étage de comparateurs 25 permettra de réduire à 8 distances le résultat de la comparaison et de proche - - en proche, avec le troisième étage de comparateur 26 et le quatrième étage de comparateur 27, on aboutit à un cinquième étage formé par le seul comparateur 28 qui délivre, sur sa sortie, la plus courte des 32 dis¬ tances, et le code J de la classe correspondante

20 D' utres montages permettant de réduire soit le temps de traitement , soit le volume de matériel nécessaire, seraient également possiblespour aboutir au même résultat.

La figure 11 est un schéma d'un circuit pour réaliser les histogrammes. Cette étape qui fait encore

25 partie des opérations de type A, parce qu'actionnée

. . -, . , _{' .} _3es opérations a chaque nouveau pixel, est la préparation _/ de type B.

Elle permet d'effectuer, pour chaque canal (pratique¬ ment dans 3 opérateurs parallèles) la sommation des ra-

30 diométries des pixels de chaque classe, et dans un qua¬ trième opérateur parallèle, la sommation des carrés des distances minimum correspondantes; il y a en outre incré¬ mentation d'un compteur de pixels par classe.

Chaque opérateur comporte un sélecteur 29 à

35 une entrée et 32 sorties qui aiguille le contenu d'un registre 30 chargé par la donnée radiométrie ou distance

du pixel courant vers l'un des accumulateurs 31 d'un banc de trente deux accumulateurs, ledit accumulateur étant sélectionné par le mot de code affecté aux pixels. Simultanément l'un des trente deux compteurs C de pixels est incrémenté d'une unité. En ^' fin de fenêtre, chacun des 4 accumulateurs de classe (3 accumulateurs pour les ca¬ ractéristiques Y, R - Y et B - Y, et un accumulateur pour la distance) , et chaque compteur corres¬ pondant , e--.t interrogé pour charger 5 registres "somme" effectivement affectés aux radiometries Y, R - Y, B - Y, aux distances et au nombre de pixels de la classe.

Le figure 12 montre le schéma d'un opérateur pour le calcul des barycentres et des variances. Il s'agit d'effectuer un calcul systématique, en fin de fenêtre, des coordonnées du nouveau barycentre de chaque classe à partir des radiometries des pixels qui la composent.

Suivant le temps dont on dispose, on pourra envisager diverses solutions allant de l'opérateur unique traitant successivement toutes les classes, à n. opérateurs tra- vaillant en parallèles pour _3_2 classes avec n = 2 , 4 , 8 , n 16 ou 32 .

Le calcul des coordonnées du barycentre consiste à diviser les sommations des radiometries par le nombre des pixels de la classe.

Pour cela, on prévoit une table 32 de conver¬ sion des inverses, cette table 32 est adressée à l'aide du nombre de pixels de la classe, et la table 32 fournit sur sa sortie l'inverse du nombre qui est appliqué à un multiplieur 33 recevant sur son autre entrée le contenu de l'un des registres de radiométrie. Le résultat fourni à la sortie du multiplieur 33 est la coordonnée du barycentre correspondant.

Le calcul de la variance de chaque classe est effectué similairement par un opérateur de structure

OMPI

identique à celui qu'on vient de décrire, à partir du registre "somme des carrés des distances" dont on divise le contenu par le nombre de pixels de la classe. Ce ré¬ sultat est obtenu à l'aide d'un multiplieur 34 dont l'une des entrées reçoit la somme des carrés des distances et l'autre entrée l'inverse du nombre de pixels.

Si l'on détecte une classe vide, par exemple par l'identité des bits du nombre à zéro, on effectuera, en outre, une comparaison des variantes de toutes les classes pour rechercher celle de variance maximale qui sera dédoublée. Cette recherche est effectuée de la même façon que l'on a, au regroupement, trouvé la plus courte distance. L'opérateur aura une structure semblable à celle représentée de la figure 10, de comparateursétages ,* toutefois, dans le cas de la recherche de la variance maximale, on sélectionnera le résultat le plus grand au lieu de sélectionner le résultat le plus faible dans le cas du regroupement décrit avec référence à la figure 10. Le code de la classe correspondant à la plus forte va- riance est utilisé pour sélectionner les valeurs des coordonnées du barycentre que l'on modifie par addition et soustraction d'un pas ou plus pour générer deux nouveaux barycentres séparés.

L'opération d'initialisation consiste à trans- férer les valeurs des radiometries de barycentre Y, ,

(R - Y), (B - Y), dans une mémoire d'initialisation 19 (figure 7) constituée de trois bancs de 32 cellules à 8 bits qui serviront à l'opérateur "calcul de distances" aussitôt qu'une nouvelle classification (ou itération) sera nécessaire.

Il est à noter, toutefois, que l'initialisation de la première fenêtre d'une nouvelle image (partie haute) proviendra d'une autre mémoire d'initialisation identique à la précédente. Il suffit qu'elle ait été chargée

O PΓ

lors de la classification de l'image précédente par les résultats de la première fenêtre de cette image ; la corrélation temporelle entre imagespermettra générale¬ ment d'obtenir un bon résultat, i Naturellement, cette procédure peut aussi être appliquéeà tous les blocs de l'image si l'on dispose d'une mémoire d'initialisation de capacité suffisante pour stocker l'ensemble des dictionnaires obtenus lors de la classification de l'image précédente.

10 En se reportant à la figure 13, on peut voir une représentation schématique des moyens qui assurent, à la réception, le décodage des informations issues des opérations A et B de classification. Ces moyens de décodage peuvent être réalisés très simplement à partir 5 de trois mémoires 35,36, 37,respectivement chargées, à des adresses progressivement croissantes, par les compo¬ santes Y (R - Y) et (B - Y) de chaque classe fournie _. par le dictionnaire supposé transnis suivant l'ordre croissant ces classes.Chaque code de pixel reçu est appliqué aubus d'adresse 38 et provoque la lecture des valeurs des

20 empesantes correspondantes de chacune des mémoires 35 , 36 , 37. On obtient ainsi, les radiometries de chaque groupe de pixels qui seront utilisées pour constituer chaque pixel du groupe après combinaison avec le résultat du décodage des composantes hautesfréquences de Y. 5 Le codage de 4 échantillons de luminance par transformation de Walsh-Hadamard peut être effectué par un opérateur simple représenté sur la figure 14 et consti¬ tué d ' accumulateurs et d'un complémenteur.

Il convient de calculer les quantités WH. , WH_ 0 et WH., déjà indiquées : WH _χ = 1/2 (Y ₂ + Y ₃ - Y _Q - Y _χ ) H ₂ = 1/2 (Y ₂ - Y ₃ - Y _Q + _Yl ) H ₃ = 1/2 (Y ₂ - Y ₃ 4- Y _Q - Y _± ) .

O PI Λ, ^" 1PO -

- 35 - Ces quantités peuvent s'exprimer à partir de la quantité Y = WH _Q = 1/2 (Y _Q + Y + Y ₂ + Y ) par ^ = Y ₂ + Y^ - WH _Q H ₂ = Y ₂ + Y _χ - WH _Q H ₃ = Y ₂ + Y ₀ - H ₀

Le bus d'entrée 39 délivrant successivement les valeurs de radiométrie Y à cadence régulière, les calculs peuvent être effectués à _. 1'aide de l'opérateur dont le schéma est donné sur la figure 14. A partir du bus de donnée 39, un registre à verrouillage 40 est chargé successivement par les valeurs à 8 bits de luminance Y _n , Y.., Y_, Y_ des 4 pixels du groupe.

Ces valeurs sont transférées à des accumulateurs 41, 42, 43, 44, en parallèle mais sélectivement sous l'effet des commandes d'activation Al, A2, A3, A4. La commande Al permet l'accumulation des 4 radiometries dans l'accumulateur 41 alors que les accumulateurs 42, 43 et 44 ne sont activés que pour Y_ et Y.,, Y_ et Y et Y- et Y_ respectivement. Dans une dernière phase, le résultat de l'accumulateur 41 est transféré, à travers le complémenteur C , vers les entrées des 3 autres accumu¬ lateurs pour effectuer les soustractions de WH- . On dis¬ pose alors sur les sorties des accumulateurs des coeffi- cients recherchés qui sont alors appliqués à un dispo¬ sitif de classification analogue à celui déjà décrit pour les composantes trichromes basse fréquence. On obtient, en définitive, 3 codes de classes WEI. , WH ₂ et WH et un dictionnaire relatif aux valeurs moyennes de chaque code d'une fenêtre de traitement.

A la réception, deux opérations sont nécessaires pour retrouver les valeurs des radiometries. En premier lieu, on doit effectuer l'opération de déclassification c'est-à-dire retrouver pour chaque groupe de pixels la

valeur des coefficients de WH qui lui sont affectés par les trois codes reçus. Ceci est effectué par un opérateur identique à celui de la figure 13, les trois mémoires étant ici affectées à WH , WH et WH chargées à partir du dictionnaire, mais avec la différence que chaque code étant spécifique n'adresse plus qu'une seule mémoire parmi les trois pour effectuer la lecture des coefficients correspondants.

On doit ensuite combiner ces coefficients avec

Y obtenu lors du décodage de l'espace trichrome qui joue le rôle de WH ₀ selon les combinaisons bien connues de la transformation de Walsh-Hâdamard :

Y = 1/2 (WH _ WH - WH + WH ) = 1/2 ( H ₀ - WH + WH + WH.) Y ₂ = 1/2 (WH ₀ + WH. + WH + WH )

Y = 1/2 (WH _Q + WH - WH - WH )

Comme précédemment, on remarque que ces quan¬ tités s'obtiennent à partir de Y„ par :

^γ o = WH + WH

~ ^Y 2

= WH + WH

^Y l ~ ^Y 2

= WH _Q + WH

^Y 3 ~ ^Y 2

Ceci permet d ' utiliser pour ce calcul un opéra¬ teur identique à celui de la figure 14 et fonctionnant de la même manière à la différence près que Y_ est aussi transféré sur le bus de sortie pour définir la radio¬ métrie du 4ème pixel .

On a ainsi reconstitué le message initial de chaque fenêtre par les composantes de la réunion de pixels Y _Q , Y Y ₂ , Y ₃ (R - Y) _M et (B - Y) _M . L ' exemple d ' appl ication décrit concernait la télévi sion en couleurs ; toutefois , l ' invention s ' applique également à la télévision noir et blanc en définissant comme on l ' a indiqué précédemment des canaux indépendants à partir d 'un

arrangement spatial des pixels au lieu d'une sélection spectrale.

L'invention peut s'appliquer à de nombreux autres domaines par exemple pour le traitement d'images couleurs dans le domaine aérospatial (image multispectrale dont le nombre de canaux peut atteindre 11) , en photo¬ graphie, en imprimerie, en télécopie. L'invention ne concerne pas seulement la transmission des images mais également le stockage des images codées numériquement et notamment leur enregistrement sur vidéo disques, cassettes ou analogues.

La transformation unitaire utilisée pour coder les pixels d'une réunion, du type de celle de la figure 3, aura un ordre convenable au nombre de pixels de la réu¬ nion et pourra être choisie parmi toutes celles décrites dans la littérature (Walsh-Hadamard, Slant, cosinus, Fourier , Haar, Karhunen-Loeve...) selon les critères considérés comme les plus importants (facilité de calcul, rapidité, aptitude à la compression ....).

La transformation de Walsh-Hadamard est généra¬ lement la plus intéressante, avec la transformation cosi¬ nus, qui a toutefois l'inconvénient d'être plus compliquée à mettre en oeuvre.