Download pdf - Utilisation de la transformation de Hadamard pour le codage et la compression de signaux d’images

UTILISATION DE LA TRANSFORMATION

POUR LE CODAGE ET LA COMPRESSION DE par

Jacques P O N C I N Ing6nieur des t616communications *

DE HADAMARD

SIGNAUX D'IMAGES

R~SUM~. - - Apr~s un rappel sur l'applicalion des mdthodes de translormation globale dans le domaine du codage des images, l' auteur expose les propridtds particuli~res de la transformation de Hadamard. II dtudie spdcialement le probl~me de la rdparlition statistique de l'dnergie dans l'espace de la transformde et il en ddduit les principes de procddds de compression el de codage permettant de rdduire dans un rapport 5 ~z 10 la quantitg d'infor-

mation /I transmettre pour une image.

PLAN. - - �9 I : Introduct ion 1.1. Gdndralitds sur le codage des images ; 1.2. Codage d'une image par transformation globale. �9 I I : L a t r a n s f o r m a t i o n de Hadamard II.1. Ddfinition; II.2. Propridtds; II .3. Formulation math~matique et algorithmes. �9 I I I : Compress ion d ' in format ion sur la transform~e de Hadamard d'une image I I I .1 . Rdpariition de l'dnergie dans le plan de la trans/ormde ; I I I .2 . Compression par suppression de points en amplitude; I I I .3 . Compression par suppression de points par zones. �9 IV : Codage de la tran[ormde IV.1. Principe du codage; IV.2. Loi de eodage ~z hombre variable d'dldmenls binaires.

�9 V : Conclusion. �9 2 Annexes. �9 Bibliographie (14 r6f.).

I . I N T R O D U C T I O N

1.1. G6n6ralit6s sur le codage des images.

Dans le cadre des syst~mes de communica t ion , la t ransmiss ion d ' i n fo rma t ions de na tu re visuelle appa- raf t au jou rd ' hu i comme un domaine en pleine expan- sion. De cer ta ines 6valuat ions fai tes aux E ta t s -Un i s sur les perspect ives d '6volu t ion de diff6rents services (t616phone, t ransmiss ions de donn6es, d ' images , de documents 6crits), dans les v ing t prochaines ann6es, il ressor t en pa r t i cu l i e r [1] que les t ransmiss ions d ' images au ron t d u r a n t cet te p6riode le plus for t t a u x de croissauce annuel et qu'el les pa rv i e nd ron t vers les ann6es 1990 en seconde pos i t ion jus te apr~s le t616phone, du po in t de vue des besoins en canaux de t ransmiss ion.

Si ce bi ian me t en 6vidence le d6ve loppement pr6visible des diff6rents r6seaux de t ransmiss ion d ' in fo rmat ions visuelles (vis iophone ; d i s t r ibu t ion par e~ble de p rog rammes de t616vision; t ransmiss ion rap ide de documents) il mon t re aussi t ou t l ' i n t6 r f t qui s ' a t t ache h la recherche de proc6d6s de compression de ces informat ions afin d 'u t i l i se r au mieux pour ces nouveaux services les voies de t ransmiss ion disponibles.

De nombreuses 6tudes on t d6jfi 6t6 men6es sur ce sujet , en par t i cu l ie r au Centre Na t iona l d ' E t u d e s des T616communications [2, 3, 4, 5] et plusieurs proc6d6s d '61imination de la redondance p a r exp lo i t a t ion des corr61ations ent re points voisins d 'une image ont 6t6

mis au point .

Pour po r t e r uu j ugemen t sur ces diff6rents proc6d6s, on doi t consid6rer comme crit6res p r inc ipaux l 'efflca- cit6 expr imde eu t a u x de compression pour une d6gra- da t ion donn6e de la qual i t6 subjec t ive de l ' image d 'une pa r t , la sensibil i t6 du eodage re tenu aux erreurs de t ransmiss ion d ' a u t r e pa r t , enfln la complexi t6 de mise en oeuvre.

Certains proc6d6s d6sormais classiques comme le codage diff6rentiel ou le codage pa r pr6dic t ion d 'o rd re z6ro pr6senten t des avan tages sur ce dernier po in t mais ne p e r m e t t e n t gu~re de d6passer des t a u x de compression de 3 ou 4. Pour ob ten i r une efficacit6 plus grande, en par t i cu l i e r en t e n a n t compte de la corr61ation b id imensionnel le qui se manifes te pa r l ' ex is teuce de zones sur la surface d ' une image, d ' au t res proc6d6s ont 6t6 propos6e [2, pp. 336 h 346], mais ils semblen t pa r t i cu l i6 rement diffieiles h exploi- te r dans la pra t ique . Les m6thodes de t r ans fo rma t ions globales enfin conduisen t h des compressions impor- t an tes avec une bonne immuni t6 a u x erreurs de t ransmiss ion , au p r ix d 'une assez grande complexi t6 de mise en oeuvre qui est toutefois va r iab le su ivan t la t r ans fo rma t ion choisie ; la t r ans fo rma t ion de H a d a - m a r d semble de ce po in t de r u e la plus favorable .

Dans les pa rag raphes qui suiveut , apr6s un r appe l des pr incipes g6n6raux de codage des images p a r les m6thodes de t r ans fo rma t ion globale, on exposera les propri6t6s par t icul ibres de la t r ans fo rma t ion de H a d a m a r d puis on d6crira les exp6riences r6alis6es en r u e d '6va luer de mani~re pr6cise l 'effieacit6 de divers proc6dds de codage de la t ransform6e d 'une image. On compare ra n o t a m m e n t les r6sul ta ts ob tenus a v e c l a t r ans fo rma t ion de H a d a m a r d h ceux d ' une 6tude aut6r ieure [5] sur la t ransform6e de Four i e r

* A u CNET-Issy groupement INFOHMATIQUE ET TRANSMISSIONS DES DONNI~ES, d6partement TRANSMISSION ET TR~,ITEMENT

DES IMAGES.

- - 2 3 5 -

2/18

et l 'on d6gagera en conclusion les principaux ensei- gnements de cette comparaison.

1.2. Codage d ' u n e i m a g e pa r t r a n s f o r m a t i o n g loba le .

Un expos6 d6taill6 sur les m6thodes de transformat ion pouvan t etre t rouv6 en [6, chap. 6] on se contentera d 'en rappeler ici bri6vement les principes.

La figure 1 donne le sch6ma synoptique d 'un syst6me de compression de ce type.

Image d'erigine

Image restitute

Fro. 1.

Transformation Image , I directe transformfie J Transmission

" ~ o~c~ I 1 , : Transformation

inverse

J. PONCIN [ANNALES DES TI~2LI::GOMMUNICATIONS

~--I N--1 O) F(u, v) = E E f(x, g) a(z, g, u, v) ,

x=0 y - 0

et la t ransformat ion inverse par :

N--1 N--1 (2) f(x, y) = E E F(u, v) b(x, U, u, v) ,

off la fonction F(u, v) est appel6e transform6e de l ' image et les fonctions a e t b noyaux des transfor- mations directe et inverse.

On dit qu 'un noyau est s6parable et sym6trique si l 'on peut d6composer a par exemple sous la forme :

a ( x , y , u , v ) = a l (x ,u) al(g , v ) ,

ce qui permet d'effectuer le calcul de (1) en deux ] 6tapes :

N--1 ~(u, g) = E fix, g) al(x, u ) ,

X--O

- - Sch6ma synopt ique d 'un syst6me de compression par t r ans fo rmat ion globale.

On voit que le t ra i tement de compression et de codage n 'es t pas r6alis6 sur l ' image elle-m6me mais dans l 'espace transform6. Les principaux avantages d 'une telle m6thode sont les suivants :

- - moyennan t un choix convenable de la fonction de t ransformat ion, les propri6t6s de corr61ation entre points de l ' image d'origine se manifestent par des propri6t6s stationnaires de concentrat ion de l'6nergie en un peti t nombre de points de l 'espace transform6, ce qui conduit ~ des proc6d6s de compression particuli~rement simples dans cet espace ;

- - la t ransformat ion inverse qui permet de restituer l ' image r~alise une op6ration d'dclatement des points, de l 'espace transform6, chaque point de l ' image 6tant fabriqu6 comme moyenne pond6r6e de t ous l e s points de la transform6e. En particulier d'6ventuelles erreurs dans la transmission ne produisent pas de d6fauts localis6s mais se t rouven t ainsi diludes sur toute la surface de l ' image ce qui est subject ivement tr6s favorable.

En consid6rant l 'espace d'origine comme un ensemble de points obtenus par un 6chantillonnage h deux dimensions, et en repr6sentant l ' image par la fonction, fix, y) = luminosit6 au point de coordonn6es (x, y),

/ 0 ~ x ~< N - 1 \ (

\o ~< g ~< N - - 1 ) ' (*)

la t ransformat ion directc est d6finie par l 'expression lin6aire :

(3)

puis

(4)

(*) On verra par la suite que des consid6rations de sym6trie entre les rbles jouds pa r les deux dimensions de l ' image, conduisent h d6finir comme image utile une zone carr6e de N points sur N lignes. II est clair d 'aut re pa r t que l 'on peu t t rai ter par t ransformat ion , soit l ' image compl6te, soit succes- s ivement des sous-images de plus peti te dimension, la valeur optimale de N d6pendant du degr6 de corr61ation spatiale que l 'on veut exploiter ainsi que des probl6mes pra t iques de raise en oeuvre li6s, prir lcipalement au volume de m6moire et h la quant i t6 de calculs. On reviendra sur ce point aux pa ragraphes II.1 et V.

N--1 F(u, v) = E y) al(u, v).

y - o

La transform6e plane F(u, v) est ainsi obtenue par deux applications successives d 'une transformat ion h une dimension (lin6aire) sur les lignes de l ' image d'origine puis sur les colonnes de l'image interm~diaire ~(u, g).

La s6parabilit6 de la t ransformat ion facilite la mise en oeuvre du calcul, tandis que sa sym6trie garant i t que les relations de corr61ation entre les points de l ' image dans les directions horizontale et vertica]e interviennent de la m6me mani6re dans le calcul de la transform6e plane.

Si l 'on repr6sente f@, g), al(x, u) et F(u, v) respee- t ivement sons forme de matrices [/], [A] et [F] la relation (1) peut alors s'6crire :

(5) [FI = [A_] [11 [A],

et l 'on peut montrer que les matrices de transformat ion [A] orthogonales et sym6triques (c'est-h-dire telles que [A] -1 = [A] r = [A]) sont part iculi6rement int6ressantes.

En effet, dans ce cas, en prenant [B] = [A] -1 (2) devient :

(6) [71 = [A] [F] [A] = [ l l ,

et l 'on voit que le m6me algorithme, ou le meme syst6me cabl6 est utilisable pour le calcul des trans- formations directe et inverse.

On peut ainsi g6n6raliser la correspondance bi- univoque entre signaux et spectres classique dans le cas d 'une analyse en fr6quence par d6composition en s6rie de Fourier.

Outre la t ransformat ion de Fourier, la classe des t ransformations lin6aires inversibles ainsi d6finie, comprend les t ransformations de Hadamard , de Haa r et de Karhunen-Lo~ve qui r6alisent des d6compositions de l ' image par des fonctions d 'onde orthogonales autres qne les sinusoides.

L 'une des propri6t6s communes ~ ces transfor- mations est la conservation de l '6nergie entre le plan

- - 236 - -

t. 26, n ~ 7-S, 1971]

de l ' image et le plan de la t ransform6e su ivant la formule :

N--1 N--I N--1 N--1

(7) Z Z If( ~, ~)l~ = Z Z [v(,,, o)[~, x = 0 y = 0 u = 0 v : 0

qui g6n6ralise la relat ion de Parseval bien conuue dans le cas d 'une analyse de Fourier.

TRANSFORMATION DE HADAMARD POUR CODAGE ET COMPRESSION 3/18

t ive citde pr6c6demmcnt est dite forme naturelle. L 'au t re correspondant au r angemen t des lignes dans l 'ordre des s6quenccs croissantes est dite ordonn6e. La figure 2 (off le signe + est mis pour le coefficient § 1

II. LA TBANSFOI:tNIATION DE HADAMAI:tD

II. l D6finition.

In t rodui te pour la preini~re fois par le math6ma-

ticien fran~ais H a d a m a r d [7], cette t ransformat ion , 6galement connue sous le nora de t rans format ion de Walsh, est d6finie h partir d 'une matr ice carr6e H qui ne cont ient comme coefficients que les valeurs + 1

et -- 1. Des m6thodes de construct ion des matr ices d ' H a d a m a r d de dimension N ont 6t6 trouv6es pour

diverses valeurs de N mais les m6thodes les plus simples sont celles concernant les valeurs de N = 2n off n est un entier.

En effet, si H est une matrice d ' H a d a m a r d de dimension N, la matrice,

G = -- t t '

est une matr ice d ' H a d a m a r d de dimension 2 N. On

voit qu 'h par t i r de la matr iee 616mentaire de dimension 2,

H 2 = 1 '

il est possible de construire successivement les matrices de dimension 4, 8, ... 2 n , ce qui donne un assez large 6ventail de dimensions pour les applicat ions prat iques, n o t a m m e n t dans le domaine du t r a i t emen t des images [*].

D'apr6s H a r m u t h [8], il est possible de donner une in terpr6ta t ion fr6quentielle de la matr ice de H a d a m a r d

en appe lan t Mquence (par analogie /t fr6quence) le nombre de changements de signes le long d 'nne ligne de la matrice. La t ransformat ion de H a d a m a r d

appara i t alors comme effectuant la d6composition du signal par un ensemble de s ignaux rcctangulaires analogues aux signaux s inusoidaux utilis6s dans la t ransformat ion de Fourier.

A par t i r de ces eonsid6rations, deux pr6sentat ions sont possibles pour une matr ice de H a d a m a r d de dimension N = 2n donn6e.

L 'une fournie par la m6thode de construct ion it6ra-

(*) Dans les exp6riences ddcrites dans les paragraphes sui- rants, on a g6n6ralement utilis6 la valeur N = 256 en appli- quant la transformation h des images carr6es de 256 points sur 256 lignes. Ce choix a 6t6 fait dans l'optique du traitement global d'images de visiophone, qui ont sensiblement cette d6finition : h titre de r6f6rence, les standards du piclnrephone des laboratoires Bell correspondent "~ 251 lignes utiles de 210 points utiles; tout porte h penser d'autre part que lorsque des dispositifs nouveaux /~ 6tat solide remplaceront les tubes actuels pour la prise de rue e t l a restitution des images, des dimensions de la forme 2 n seront retenues pour des raisons d'adressage.

Num6msdes Rum6rosdes s~quences s~quences

+ + + + + + + + 0 + § 0

+ - + - + - + - 7 + + + + . . . . 1' + + - - + + - - 3 + + . . . . + + 2 + - - + + - - + 4 + + - - + + - - 3 + + + + . . . . ~ + - - + + - - + 4 + - 4 - - + - + 6 + - - + - + + - 5 + + . . . . + + 2 + - + - - + - + 6 + - - + - + + - 5 + - + - + - + - 7

~rmena~r~le ~rmeor~nn~e

F r o . 2. - - M a t r i c e s de H a d a m a r d de d i m e n s i o n 8.

et -- pour -- 1) donne un exemple des matrices de H a d a m a r d de dimension 8 sons forme naturel le et sous forme ordonn6e.

Comme on le verra par la suite, il est pr6f6rable d 'ut i l iser la forme ordonn6e pour toutes les op6rations de codage et de compression, la not ion de s6quence 6 tant tr6s voisine de celle de fr6quence spatiale utilis6e dans la t ransformat ion de Fourier. Cependant , pour le calcul la forme naturel le condui t h des algorithmes plus simples et plus rapides.

II.2 Propri6t6s.

I1 est clair, d'apr~s le mode de construct ion donn6 pour les matrices de Hadamard que eelles-ci poss6dent les propri6t6s de sym6trie et d 'or thogonal i t6 :

si [Hj] est le vecteur ligne correspondant h la /e ligne d 'une matr ice de Hadamard , on a en effet :

[Hi] [H~] T = NS, l , ~ j 6 tant le symbole de Kronecker.

On en d6duit que [H] [H] T = [H] [H] = N[I] .

off [I] est la matr ice uni t6 de dimension N.

La matr ice de t ransformat ion poss6dant les pro- pri6t6s d6finies en 1.2 est donc la matr ice de Hadamard normalis6e [AI = I [H]]~/~-.

En fait, pour la commodit6 des op6rations on calcule p lu t6 t la t ransformat ion directe de l '6quat ion (5) sons la forme

(5') IF] = [H] [/1 [ H ] ,

e t l a t rans format ion inverse (6) sons la forme,

1 (6') [fl = - ~ - [H] [/1 [ H ] ,

les deux op6rations 6 tan t identiques au coefficient N ~ pr~s. Dans ces conditions, l '6quat ion (7) de conser- va t ion de l '6nergie devient :

N--1 N--1 1 N--1 N--1

(7') Z Z If(x, g)V = N2 Z Z W(u, v)V. X--0 y--O U--O V--O

II .3 Formulation math6matique et algorithmes de calcul.

D'apr6s Pra t t , Kane et Andrews [9] on peut donner de la t ransformat ion de Hadamard ~ une dimension

- - 237 - -

4 /18

des formulat ions math~mat iques sous forme de s~ries.

- - Si l 'on utilise la forme naturel le, la composante d 'ordre u d ' une transformge de dimension N = 2 n

s 'exprime par :

N - - 1

(8) F(u) = Z f(x) ( - 1 ) ~ ( ~ , u ) , X - - 0

~ - - 1

avec p(x, u) : Z u~ x~, I f f i0

off les u~, xl sont les valeurs des ~l~ments binaires

de rang i dans les d6compositions binaires de u et d e x :

/ /d6clmal ~ [ U n - 1 U n - 2 " ' " U l L / O ] b i . a l r e "

- - Si l 'on uti l ise ]a forme ordonn~e, la composante

d'ordre u qui correspond alors h la s6quence u s e calcule par :

N - - 1

(9) F(u) = ~, f(x) ( - - 1 ) q(x,u) ,

avec q(x, u) = Z g~(u) x~ ,

U ~ _ 1 ,

= Un_ 2 + l l n - 3 ,

et go(U) g~(u)

g~(u) . . .

gn-l(U) U 1 -~ /2 0 ,

les u~, x~ a y a n t le m~me sens que pr6c6demment. On vol t que l 'u t i l i sa t ion de la forme ordonn6e

condui t h u n algori thme de calcul a priori plus compliqu&

Divers auteurs [9, 10, 11, 12] on t donn6 des sch6mas d 'a lgori thmes pour une Transformat ion Rapide de H a d a m a r d analogue h la Transformat ion Rapide de

Fourier, c 'est-h-dire p e r m e t t a n t d 'obteni r les r6sultats en N log z N op6rations au lieu des N 2 qui seraient n6cessaires si on effectuait d i rectement t o u s l e s calculs. Su ivan t les cas, les r6sultats sont obtenus

sous forme naturel le ou sous forme ordonn6e. Le problbme du choix de l 'a lgor i thme opt imal n ' 6 t a n t pas fondamenta l dans le cadre de cette 6tude, on s 'est born6 h comparer du point de rue du temps de calcul, les performances de trois sous-programmes construi ts su ivant les principes d6finis en [9, 11 et 12]. Les temps obtenus ont 6t6 respect ivement de 220 ms, 88 ms et 125 ms par ligne de 256 points ce qui a condui t ~ retenir le deuxibme algori thme qui est d~crit en annexe I.

I I I . C O M P B E S S I O N D ' I N F O I ~ V I A T I O N S U R L A T R A N S F O R M E E

D E H A D A M A R D D ' U N E I M A G E

I I I . 1 R 6 p a r t i t i o n de l ' 6 n e r g i e d a n s le p l a n de la t r a n s f o r m 6 e .

l l l . l . a . N o t / o n s subjectives sur la rdpartition.

Le premier point intdressant h consid6rer est la

J . P O N C I N [ANNALES DES TI~.LECOMMUNICATIONS

dynamique des diff6rents 61~ments de la transform~e plane de Hadamard . Pour cela il suffit de consid~rer comment chaque point du plan de la transform6e, caract~ris~ par ses coordonn~!es s6quentielles u et v est ob tenu h par t i r des points de l ' image. La figure 3

(0,0) (1;0)

(o,1) (Ll)

i"+l. it (~2) (i,2)

§ + - I J- + - +

(0,3) (1,3)

(2,0) (3,0) + + -

+ §

+ - + +

(2,1) (3,1) + + + +

+ + + - +

+ - + - +

(2,2) (3,2) + - + - + - + -

- + - . + - + . +

+ - + : -

+ - + - - + - +

(2,3) (3,3)

Fie. 3. - - Correspondance entre les dldments de la trans- form6e et les points de l'image.

illustre cette correspondance pour les 16 premiers 616ments (0 ~ u ~ 3, 0 ~ v ~< 3 ) d ' u n e t ransform6e plane ordonn6e de dimension N /> 4 : chaque carr~ r e p r &e n t a n t la surface totale de l ' image, un ~16ment donn~ de la t ransform6e est ob tenu en a d d i t i o n n a n t les valeurs des luminos i t& des points compris dans les zones (+) et en r e t r anchan t la somme des valeurs

des points compris dans les zones (--). Ainsi le point de coordonn~es (1,1) d 'une transform~e de H a d a m a r d repr~sente la somme des points du quar t sup~rieur

gauche et du quar t inf~rieur droit de l ' image moins la somme des points du quar t sup~rieur droit et du quar t inf6rieur gauche.

On vol t qu ' en dehors de l'~16ment (0,0) ob tenu en somma n t t o u s l e s points et qui repr&ente doric la luminosit~ moyenne de l ' image, tous les 61~ments sont obtenus par la somme de N2[2 termes positifs et N212 termes n~gatifs, N & a n t la dimension de l ' image. Si l 'on d6signe par M le niveau maximal de

luminosi t~ on a d o n c :

F(O, O) ~< N~M,

u r et - -N2M]2 <. F(u, v) ~ N2M]2 pour r

Si l 'on prend N = 256 et M---- 127 (codage des luminosit~s fi 7 ~l~ments biuaires par point) on vol t que la dynamique de la t ransform~e est de 22a donc qu ' i l faudra i t th6or iquement 23 ~16ments binaires par point pour coder la transform~e. E n fait, l ' in format ion ~tant conserv~e dans la t ransformat ion , on peut ~valuer fi 7 ~16ments binaires par po in t en moyenne la quan- tit~ d ' in format ion dans l 'espace t ransform6 ce qui

- - 238 - -

t. 26, n ~ 7-8, 1971] T R A N S F O R M A T I O N D E H A D A M A R D

t r a d u i t le fa i t que les 616ments ne sont pas ind6- pendan t s et condui t h 6tudier la r6par t i t ion s ta t i s t ique globale de leurs valeurs.

I1 est in tu i t i f d 'apr6s la f g u r e 3 de penser que les 616ments de la t ransformde ont une 6gale probabi l i t6 d'6tre positives ou n6gatives, ce qui sera v6rifi6 par le calcul en annexe I I dans le cas de la t r ans fo rma t ion lin6aire. On a donc consid6r6 comme param6t re la va leur absolue des 616ments de la t ransform6e, et l 'on a t rac6 sur la figure 4 les probabi l i t6s e t les probabi l i t6s

POUR C O D A G E E T C O M P R E S S I O N 5/18 et l 'on a repr6sent6 sur ta figure 5 les points (u, v) de la transform6e de la photographie 1 tels que IF(u,v)[ > sk pour k = 80 %, 90 % et 95 %. On observe que les 616merits de forte ampli tude sont eoncentr6s au vois inage de l 'o r ig ine du p lan des

s~quences spatiales, ainsi que le long des axes, avee des apparcnees de diseontinuit6s aux voisinages des points

u = 0 ~ u = 2 ~' : et ~ , (0 < k < n ) . .- 2~/ ,0 : o /

10"3.

P(IFI)

o,9

0 , 8

0,7

0,6

0,5 - - -

0 ,4

0,3

0,2

1,0

P(]FI<S)

N - - \ - - ~ / .

\ \ \ /

/ . . ,

..: / : "

- 1 - - / , .:." -

t / / i . " ' " . . . . . . . . .

0,1 q0 "4 . . . . . . . i / ~ " ' i I ~ 1 t " - - - t /.~'...".., i .... \

I0 102 10 3 I0 ~ IFt 105 Sso Sg0 S95 $

Fro. 4. --- Courbes de probabi] i t6s et probabil i t6s cuInul6es des valeurs absolues des 616ments de la transform6e d e H a d a m a r d .

- - - p r o b a b i l i t 4 p h o t o g r a p h i e 1 , - - - - - - p r o b a b i l i t 6 p h o t o g r a p h i e 2 ,

. . . . . . p r o b a b i l i t 6 c u m u l 6 e p h o t o g r a p h i c 1 , - . . . . . p r o b a b i l i t 6 c u m u l 6 e p h o t o g r a p h i e 2 .

cumul6es de ces valeurs pour deux photographies (la pho tograph ie 1 6rant le p o r t r a i t de la figure 12a et la plaotographie 2 un au t re p o r t r a i t plus contrast6) .

On observe, d 'une pa r t , la s t a t ionnar i t4 des dis tr i - but ions des valeurs absolues, qui sont tr6s semblables pour les deux photographies, d 'au t re par t leur allure caract6ris6e par une forte probabilit6 des faibles niveaux. Ce r6sultat est comparable h celui obtenu sur les modules de la t ransform6e de Four i e r [5, w 3.2] e t condui t h envisager des proc6d6s de compression pa r suppression des 616ments (te faible ampl i tude . Ces proc6d6s seront analys6s en III-2.

Il est in t6ressant enfin de savoir off sont localis4s dans l 'espace transform6 les 616ments de forte amplitude. On a pour cela utilis6 la m6me m6thode qu 'en [5] en d6 te rminan t sur l ' h i s t og ramme eumul6 de la figure 4 les seuils Sk tels que P([F(u, v)[ ~< S~) = k,

Ces observat ions soul ignent l ' in t6r6t d ' a pp ro fond i r l '6 tude de la r6par t i t ion s ta t i s t ique des 616ments F(u, v) en fonct ion de leurs coordonn6es sdquentiel les

spat ia les u et v.

IIl.l .b. E~ude th~orique de la r~partition.

Dans le cas de la t r ans fo rma t ion h une d imension, il existe un mod61e math6mat ique simple qui permet de repr6senter avec une bonne approximat ion les propri6t6s statistiques d ' images photographiques assez vari6es. Les 6tudes statistiques [13] ont en effet montr6 que sur une ligne de ba l ayage la probabi l i t6 de t r an - s i t ion entre deux 6chanti l lons cons6cutifs ob6i t ~ une loi normale centr6e sur la va leur du premier 6chan- t i l lon :

1 ( [ Z - - ] x - - l ) 2 (10) P ( / z l / z - 1 ) - - s 2 ~ exp 2s 2

- - 2 3 9 - -

6/18 J . P O N C I N [ANN•LES DES TELL;COMMUNICATIONS

FIG. 5. - - Localisation des points de forte amplitude dans le plan de la transform6e :

a ) k = 8 0 %, b) k = 90 %, c) k = 95%.

En consid6rant une ligne d ' image comme un pro- cessus markovien d~fini par une telle loi de probabil i t~

eonditionnelle, Schwartz [14] a calcul6 les lois de probabil i t6 de fonction F u des f x de la forme :

N - - 1

(11) F u ,~ u ~ - - 0

I1 a ob tenu comme r6sul tat :

/:~ (12) P ( F u = Z ) = P'([o) " 2 s ( # J ~ " •

[Z --/o(a~v-1 + a~v-~ + ". + %)12 exp -- 4 s ~ ~ d r ~

off P'(to) est la probabil i t6 a p r i o r i d 'appar i t ion du

premier ~ehantil lon fo de la ligne,

et

(13) 2 g ~ 2 = a~v21+(aN_ l + aN_S ) + . . . + U U �9

(aN_ 1 + aN_ 2 + ... + a~) ~

En part iculier dans le cas off l 'on a :

(14) u u u 0 aN_ 1 + aN_ 2 + ... -{- a o ~ ,

l '~quat ion (12) se simplifie en :

(15) P ( F . = Z ) - 2 e x p - - 4

- - 2 4 0 - -

t , 2 6 , n ~ 7 - 8 , 1 9 7 1 ] T R A N S F O R M A T I O N D E H A D A M A R D

qui caract~rise une var iable al~atoire gaussienne h

valeur moyenne nulle et d '~cart type au = s e p a l 2 .

L'appl ica t ion de ces r~sultats h la t ransformat ion

de H a d a m a r d : conduits aux calculs ddvelopp~s en

annexe I I : comme dans le cas de la t ransformat ion

de Fourier , l 'dquat ion (14) est v~rifi6e et l 'dquat ion (13)

devient : 2 n

(16) 2 a u* - 6 [1 ~- 2 T M ] pour 2 ~+1 > u >~ 2 k,

ce qui mont re que l '~cart type au de la dis t r ibut ion

est une fonct iou eu escalier de ]a sdquence u avec des

discontinuit6s aux valeurs de u ~gales h des puissances

de 2.

Pour v~rifier ce r~sultat on a calculd sur 256 lignes

d 'une image les variances des 256 ~l~ments de la

t ransformde de H a d a m a r d h une dimension et l 'on

a reportd sur la figure 6 les valeurs exp~rimentales

et les valeurs th~oriques calcul~es ~ par t i r de l '~qua-

fO:

Poun CODAGE I/IT COMPRESSION 7/18

logue h celui ddvelopp6 en [14]. On peu t toutefois

obtenir des r6sultats int6ressants sur la rdpart i t ion

des valeurs dans le plan des sdquences spatiales en

ra isonnant par analogie avec le cas lindaire et en

menau t les calculs eu simulation�9

Tout d 'abord il semble logique de supposer que la

valeur en chaque point du plan de la t ransform6e est,

comme pour la t ransform~e lin6aire, une var iable

al6atoire gaussienne h valeur moyenne nulle, dont la

r6part i t ion est d~fiuie par un 6cart t ype (~u.v.

Si l 'on examine l 'expression (13) on vo l t d ' au t re

pa r t que, dans le cas lin~aire, cet 6cart type est d6fini t ~ h par t i r de sommes de coefficients a x , ces - sommes

s '6 tendant sur 1, puis 2, ... puis n coefficients. On

peut g6n6raliser cet te expression eu supposant qu 'h

un coefficient cons tant pr6s on a :

(17) ~ . . . . . . . ~ /a ..... a ..... ~2 au, v ~ (aN2_ 1) -t- ~ N*-I -1- N * - # + "" -t- 11,o iz v u , v ~

(aNq t - I - . . . + a ~ -}- ...-}- a 1 ) ,

. . " . . _ _

�9 � 9 1 4 9 o

�9 o. �9 ~ � 9 , N " ' J 7 . * ~ r �9 o �9 , , � 9 1 7 6 �9 ~ , , 4 , , , . ~ , �9 ~

�9 o ~ , o �9 , o o o , , " "" .",'"-*..* "~' " " ' . �9 J .- " ~ ~ , - ~ v , . . F - - ; - * ~ . ; - j - * ~ * ' : � 9 ~ r - -

' * *

.o / 0 $

O 8 t8 32 64 128 256

FIG. 6. - - Transform~e de Hadamard h une dimension�9 Valeurs th6oriques et exp6rimentales des variances des r6partitions en fonctions de la sdquence :

valeur th~orique pour s = 5, - - valeur th6orique pour s = 6.

t ion (16) pour diff6rentes valeurs de l '6car t type s de

la probabil i t6 de t ransi t ion condit ionnelle. La figure

mont re une bonne correspondance ent re la th6orie et

l 'exp6rience pour des valeurs de s de l 'o rdre de 5 h 6.

Pour g6n6raliser ces r6sultats au cas de la t rans-

form6e plane, il serait n6cessaire de disposer d 'un

moddle ma th6ma t ique qui rende compte des corre-

lat ions bidimensionnelles entre points de l ' image.

Malheureusement un tel module semble difficile

d6finir, et il est de plus probable que sa complexi t6

emp6cherai t de mener h terme un calcul formel ana-

off l ' iudiee m correspond h u n rangement des N 2 points

de l ' image darts l 'ordre des distances euclidiennes

d~croissantes par rappor t h l 'origine du plan, de la

m~me mani~re que les indices de l 'expression (13)

correspondaient ~ u n r angemen t des points d 'une

ligne par abcisses d6croissantes.

Cette correspondance entre indices et posi t ions est

indiqu6e sur la figure 7a pour une image de dimension

4 • 4 dans le cas oh l 'on suppose une dCifinition

isotrope de l ' image, c 'est-h-dire un m~me pas d 'ana lyse

entre les points e t les ligues.

- - 2 4 1 - -

8 /18

0,0

X X

1,0 0,0 12 2,0 3,0

2,2 3

1,3 2:3 3,

Image

yl 2,0 3,0

I~1 2,1 3~

1~2 242 3:

1,3 2,~3 31

Image

Coordonn~ies Indice Coordonn6es Indice des points m des points m

1,0 1 12 1 0,I 2 0,I 2 1,1 3 1,1 3 2,0 4 2,0 4 0,2 5 2,1 5 2,1 6 3,0 6 1,2 7 0,2 7 2,2 8 1,2 8 3,0 9 3,1 9 0,3 10 2,2 10 3,1 11 3,2 tl 1,3 12 0,3 12 3,2 13 1,3 13 2,3 14 2,3 14 3,3 15 3,3 15

a b

FI~. 7. - - Correspondance entre indices et coordonn~es pour le calcul de la variance des ~16ments (transform~e plane).

a) d6finition isotrope, b) d~finition anisotrope.

P a r t a n t de l ' express ion (17) on a calcul~ les valeurs de a~u,v pour les 256 ~l~ments d 'une t ransform~e plane de H a d a m a r d de dimension 16 • 16. Parall~- l ement on a calcul~ des valeurs exp6r imenta les de ces var iances en d iv i san t la pho tograph ic de la figure 12 de d imension 256 • 256 en 256 (~ sous-images ~> de dimensions 16 • 16 eL en a p p l i q u a n t h c h a q u e , sous- image ,) la t r ans fo rma t ion plane. Les figures 8a et 8b donnen t une rep resen ta t ion en perspec t ive cava-

~ , v

J . P O N C I N [ANNALES DES TI~LECOMMUNICATIONS

on a, d ' a u t r e par t , repris le caleul de (17) dans le cas d 'une d~finit ion anisot rope conform~ment h la figure 7b. On ob t ien t ainsi le r~sul ta t repr~sent~ sur la figure 8c qui pr6sente une analogie encore meineure avec la surface exp~r imenta le b n o t a m m e n t du fa i t de la d ispar i t ion de la crete situ~e sur la diagonale pr inc ipa le en a.

Les r~sui ta ts obtenus , jus t i f len t a posteriori la val idi t~ de l ' hypoth~se fa i te pour le calcul de la var iance par l ' express ion (17) et l 'on peu t ainsi pr~ciser la descr ip t ion de la r~par t ion par r a p p o r t aux observat ions fai tes sur la figure 5 : outre la poin te i~ l 'or igine du p lan des sdquences spat ia les , qui cor respond h une forte p robabi l i t6 d ' a vo i r des ampl i - tudes impor t an te s pour les ~l~ments de la t rans- fortune situ~s au voisinage de l 'or igine, la surface est caract~ris~e pa r une al lure d i scont inue au vois inagc des axes e t p r a t i q u e m e n t cont inue vers l ' ex t r~mi t~ du p lan oppos6e h l 'or igine. En se r~f~rant ~ la figure 3 on vo i t que les po in ts situ6s pros des axes cor responden t ~ un d6coupage de l ' image en bandes don t l ' une des dimensions est tr~s sup~rieure h l ' au t re . Les correla t ions j ouen t alors essent ie l lement dans le sens de la plue pe t i t e d imension, e t la lo iobserv~e pour la var iance est tr~s voisine de celle t rouv~e dans le cas de la t ransform6e lin6aire avec une accen- t ua t i on des discont inui t6s a u x va leurs de s~quences ~gales h des puissances de 2, due h une remont6e de la var iance h l ' ex t r~mi t6 des pal iers . Lo r squ 'on s'61oigne des axes, les zones de d~coupage corres- pondan te s on t des dimensions plus homog~nes et l 'on peu t a d m e t t r e en premiere a p p r o x i m a t i o n que la var iance ne d~pend que de la surface moyenne de ces zones, a u t r e m e n t d i t du p r o d u i t uv des s6quences

spat ia les hor izonta le et ver t ica le . Les sect ions de la surface pa r des plans ~s(u, v) ~ C te sont alors des hyperboles uv = k, Ia var iance ~tant une fonct ion cont inue d~croissante de k.

En raison du caract~re d iscont inu de la surface au voisinage des axes, il semble difficile de d6duire de

~,v ~ ,v

b a r

FiG. 8. - - Repr6sentation de la variance des 616ments d'une transform6e plane 16 X 16 en fonction de leurs coordonn6es s6qnentielles (surfaces th6oriques et exp6rimentales) :

a) surface th6orique (d6flnition isotrope) ; b) surface exp~rimentale ; c) surface th~!orique (d6finition anisotrope).

li~re de la surface ~2(u, v) avec une ~chelle logari- t hmique sur l ' axe des ~s et des dchelles lin~aires en u et v. Pour mieux ten i r compte des caract~r is t iques r6elles d ' ana lyse des images utilis6es (cf. annexe 1.2)

ces r6sul ta ts une expression m a t h 6 m a t i q u e de la forme ~2 = f(u, v) va lab le dans t o u t l ' espace de la t ransform6e. Le vo lume de calcul h m c t t r e en oeuvre empgche d ' a u t r e p a r t d 'u t i l i se r l ' express ion (17) pour

242

t. 26, n ~ 7-8, 1971] T R A N S F O R M A T I O N D E H A D A M A R D

une transform6e de dimension sup6rieure h 16 • 16 et l 'on dolt extrapoler empi r iquement les r6sultats pour les appliquer au eas d 'une transform6e 256 • 256. Malgr6 ees l imitat ions, on verra, en part iculier au paragraphe III-3, que les r6sultats ainsi obtenus sur Failure stat is t ique de la r6part i t ion t rouven t d ' int6-

ressantes applications pour le codage et la compression.

III.2 Compression par supression de points en amplitude.

Dans l 'op6rat ion lin6aire de t ransformat ion inverse d6finie par l 'expression (6') qui permet de rest i tuer une image ~ par t i r de sa transform6e, la cont r ibu t ion d ' un 616merit de la transform6e en chaque point de l ' image est proport ionnelle ~ son ampli tude. Ceci condui t h envisager un proc6d6 de compression bas6 sur la t ransmission des seuls 616ments de la t rans-

form6e dont l ' ampl i tude en valeur absolue d~passe un certain seuil. Ce proc6d6, 6tudi6 en d6tail en [5] pour la t ransformat ion de Fourier ainsi qu 'en [6]

pour diverses t ransformat ions est opt imal si l 'on consid6re comme crit6re l 'erreur quadra t ique sur l ' image restitu6e. En effet si F(u, v) est la transform6e d 'une image f(x, g) et si l 'on cousid~re de mani~re g6ndrale un proc~d6 de compression par suppression

de points off l 'on t r ansmet une part ie des 616ments de la transform6e, les autres 6rant remis h z~ro a v a n t

la t ransformat ion inverse, on peut 6crire :

F(u, v) = FI(u, o) + F2(u , v),

off F~(u, v) repr6sente les 616ments trausmis,

et Fz(u, v) les 616ments supprim6s. Dans la t ransformat ion inverse on a :

[I]=[H][FI[H]=[HI[Fx][H]+ [H][Fz][HI=[/~I+II,] ,

l ' image restitu6e apr~s compression 6 tant [/1], on voit que l 'erreur quadra t ique r6sul tant de la compression est :

N--1 N--1 N--1 N--1

Z Z (f(x,y) -- fl(x,y))2 = Z Z (fu(x,y))2, X=0 y - 0 X--0 y - 0

N--1 N--1 : Z Z

U=0 V--0

d'apr~s la propri6t5 de conservat ion d'6nergie clans la t ransformat ion. Pour une image donn6e et un taux de suppression donn6 on volt que l 'erreur est minimale si l '6nergie des 616ments supprim6s est minimale, c'est-h-dire si l 'on supprime les ~16ments de faible ampli tude.

Cependant , pour comparer diff6rents proc6d6s de compression, il est n6cessaire de consid6rer pour une m~me d6gradation de l ' image (c'est-h-dire une m6me

erreur quadra t ique ou mieux une m~me qualit6

subjective) quels sont les t aux de compression obtenus ou les quant i t6s d ' informat ion transmises. En parti-

eulier dans le eas d 'nne compression par suppression

de points en ampli tude, il faut tenir eompte de l ' in format ion de position des points conserv6s que l 'on dolt t r ansmet t re en plus de l ' in format ion

d 'ampl i tude .

P O U R C O D A G E E T C O M P R E S S I O N 9/18

Pour coder cette informat ion de position, la m6thode la plus classique [5, 6] et la plus 6conomique compte tenu de la concentra t ion des points conserv6s, eonsiste h d6flnir la position d ' un point h par t i r de la longueur de la plage de points remis h z6ros qui le s6pare du pr@6dent point eonserv6 sur une m6me ligne de la

transform6e. Un 616ment binaire de marquage est r6serv6 pour dist inguer une informat ion d ' ampl i tude

d 'une informat ion de longueur de plage. Si l 'on d6signe par :

N la dimension de l ' image carr6e initiale, ni le nombre d'616ments binaires n6cessaires pour

coder un point de l ' image initiale, nt le nombre d'616ments binaires n6cessaires pour

coder l ' ampl i tude d ' un point de la transform6e, Np le nombre total de plages dans l 'espace t ransform6,

pour une longueur de plage limit6e h L,, . . . . p le nombre d'616ments binaires n6cessaires pour

coder la longueur d 'une plage (p = log 2 L ..... ), Vs le t aux de suppression, le t aux de compression est d6fini par :

e QI (18) 'c - - QA + Q P '

ou

QI = N2ni cst la quant i t6 d ' in format ion n@essaire pour t ransmet t re l ' image sons la forme initiale,

QA = N2(nt + 1)['Vs est la quant i t6 d ' in format ion

d 'ampl i tude sur les points con- serv6s,

Qp = Nv( p § 1) est la quant i t6 d ' in format ion de position.

Pour caraet6riser la concentra t ion globale des points conserv6s dans l 'espace transform6, on pen t d6finir un facteur de concentra t ion [c comme le rappor t du nombre de plages au nombre de points eonserv6s :

N p "r: s = �9

Le t aux de coml)ression s 'exprime alors par :

TH __ N 2 nl c [N2(nt § 1)]'rs] § [N 2 lc(P § 1)/'rs]

I l l "~'S

(m § 1) + r e ( p + 1) Si l 'on prend

ni = 6 616ments binaires par point ,

nt -- 6 (on verra au chapitre IV la just i f icat ion de ce choix),

p -- 8 ce qui correspond h une longueur maximale de plage 6gale ~ 256,

et /c = 0,5 ,

on trouve (19) Zc H = 0,52 % .

En fait, le facteur de concentra t ion ainsi que la

longueur maximale de plages d o n n a n t le meilleur

t aux de compression sont variables en fonction du t aux de suppression. On a port6 sur la figure 9 un certain nombre de valeurs du t aux de compression

en fonction du t aux de suppression avec comme param~tre la longueur maximale des plages, ainsi

- - 243 - -

10/18

[

i

FIG. 9 . - Taux de compression en fonction du taux de suppression (suppression en amplitude).

Longueur maximale des plages : �9 Lmax := 16, C) Lraax = 32, [] Lmax = 64, A Lmax := 128, • Lmax ~ 256.

J . P O N C I N [ANNALES DES TI~LIi;COMMUNICATIONS

Ces diff6reuces p e u v e n t 6tre interpr6t6es pa r le fa i t que darts la quan t i t6 d ' i n fo rma t ion to ta le t r a n s m e t t r e @a + QP de l ' express ion (18), r in fo r - ma t ion de pos i t ion Qp est plus impor t an t e pa r r a p p o r t

l ' i n fo rmat ion d ' a m p l i t u d e ou de module Oa darts le cas de H a d a m a r d que dans le cas de Fourier . Aut re - m e n t di t , il semble que la t r ans fo rma t ion de Four ie r r6alise une meil leure concen t ra t ion de l ' i u fo rmat ion pu i squ 'on peu t darts ce cas ut i l iser un crit6re de suppression ne p o r t a n t que sur un des deux pa ra - m6tres, module et phase, qui d6finissent un 616ment dans le demi-espace t ransform6.

L 'effe t subject i f d 'une compress ion pa r suppression de points en amp l i t ude peu t 6tre 6valu6 sur la figure 12b qui cor respond ~ un t a u x de suppression de 10 et un t a u x de compress ion de 5,31.

que la droi te d6finissant le t a u x de compression id6al qui a pour dquat ion

(20) "re H = 0,5 + 0,5 "~s,

ce qui donne des valeurs peu diff6rentes de celles de l ' express ion (19).

II est in t6ressant de compare r du po in t de vue des t a u x de compression la m6thode de suppression en amp l i t ude sur la t ransform6e de H a d a m a r d et la m6thode de suppress ion en module d6crite en [5] pour la t ransform6e de Fourier . On rappel le que la t r ans fo rma t ion de Four ie r est complexe, mais poss6de la propri6t6 de sym6tr ie hermi t ienne pa r r a p p o r t l 'or igine ee qui condui t h compte r les points conserv6s et les plages clans la moit i6 de l 'espace t ransform6. Dans ces condi t ions , avec les m6mes no ta t ions que ci-dessus, on a :

N 2 tl~

= [N2(2 nt + 1)/2 ~s] + [V 2 I~(P + 1)/2 ~s] '

l l i Ts

(nt + 0,5) + / c [ ( p ] 2 + 0,5)]

Soit avee les m~mes va leurs des param~tres :

(21) xc e = 0,69 ~s ,

et pour la droi te exp6r imenta le analogue h celle de la figure 9 l ' 6qua t ion :

(22) ~ = 0,25 + 0,75 Zs.

La compara i son des expressions (19) et (21) ou (20) e t (22) mon t re que pour un m~me t a u x de suppression, on ob t i en t des t a u x de compression moins 61ev6s sur la t ransform6e de H a d a m a r d que sur la t ransform6e de Four ier , cornme le pr6cise le t ab leau I.

Taux de suppression

5 10 20

TA.BLEAU I

Taux de compression

Fourier Hadamard

3 5,5

10,5

4 7,75

15,25

I I I - 3 Compression par suppression de p o i n t s par zones

On a vu que le proc6d6 de suppression en amp l i t ude 6tai t op t imal pour une image donn6e du po in t de r u e de la quan t i t6 d ' i n fo rma t ion conservde en fonct ion du laux de suppression, mats qu ' i l fa l la i t dans ce cas teni r compte de l ' i n fo rmat ion de posi t ion qui en t raIne une d iminu t ion du t a u x de compression. A la suite de l '~ tude de la rdpar t i t ion s ta t i s t ique fai te en I I I -1 , on peu t envisager un au t re proc6d6 de compression qui consiste h ne conserver que les poin ts de la t ransformde h l ' in tdr ieur d 'une zone d6finie a priori.

A la diffdrence du premier proedd6, qui est adap ta t i f , celui-ci ne peu t 6tre opt imal is6 que g loba lement sur une eer taine classe d ' images en chois issant les l imites de zones de telle mani~re que la probabi l i t6 d 'une forte amp l i t ude soit, en t ou t po in t in tdr ieur h la zone, sup6rieure h la probabi l i t6 de la m6me ampl i t ude en tou t po in t extdrieur. En par t icul ier , si l 'on a d m e t l ' hypo thbse de la r6par t i t ion gaussienne eentrde pour chaque 616ment, on voi t que les zones opt imales seront d6finies pa r les poin ts don t la var iance est la plus 61evde. On doi t no te r d ' a u t r e p a r t que, quelle que soit la forme de la zone et la mdthode util isde pour la ba layer , aucune in format ion de posi t ion n ' e s t h t r a n s m e t t r e dans ce cas pour les po in ts eonservds et t ransmis . A u t r e m e n t di t , dans les procdd6s de suppression de points pa r zones, le t a u x de compress ion est 6gal au t a u x de suppression.

Afin de comparer ces divers proc6dds, on a utilis6 comme crit~re le fac teur de b ru i t ddfini en [5] p a r :

(23) Fs = E t l E c ,

off Et = ~ (F(u, v)) 2 est l'6nergie to ta le de la t rans- u,v form6e,

et Er = ~ (F(u, v)) ~ est l '6nergie des po in ts conserv6s, x I 6 tan t l ' ensemble de ces points .

En fai t , la composan te cont inue de l ' image corres- p o n d a n t au po in t (u = 0, v = 0) repr6sente une f rac t ion impor t a n t e de l '6nergie to ta le et , en obse rvan t que ce po in t doi t tou jours etre conserv6 quel que soit le proc6d6 de suppression, on vo l t que des r6sul ta ts

2 4 4 - -

t . 2 6 , n ~ 7 - S , 1 9 7 1 1

plus significatifs peuven t 6tre obtenus en rempla- ~ant (23) par :

/gt - - (F(O,O)) * (23') F~ = Ec--(F(O,O)) 2 '

off F ' est di t facteur de brui t sans eomposante continue. On a trac6 sur la figure 10 les courbcs de F~ en

T R A N S F O R M A T I O N D E I I A D A M A R D P ( ) U R C O D A G E E T C O M P R E S S I O N

0,25 . . . . . . . . . . .

Fs(dB)

0,20. . . . . . . . . =

V 32 64 l~l ' ' (

I r - ~ . . _ ._I i

. . . . . . i ,-J )......~ ?

t i I F'" '*':

. . . . I_...)

11/18

2 ~

k

/

, '

o . . . . . . . . . T ~ . . . . .

o.

' Z

o,oo, L ~ . . . . . . ~

/

Fro. 10. Faeteur de bruit en fonetion du taux de compression pour divers proc6d6s de suppression.

-- . ~ suppression en amplitude. . . . . . A suppression par zones circulaires.

- ~ suppression par zones hyperboliques. . . . . . �9 suppression par zones optimales.

fonction du t aux de compression ~c pour le proc6d6 de suppression eu ampl i tude et divers proc6d6s de suppression par zones :

les zones circulaires sont d6finies par :

(u ,v) ~ I pour u 2 -t- v z <<. R 2,

les zones hyperboliques par :

(u ,v) ~ 1 pour u v ~< k.

Les zones dites optimales ont 6t6 trae~es par extra- polat ion des r~sultats obtenus en III-1 sur la variance des 616ments de la transform6e : la figure 11 repr6- sente pour quelques t aux de suppression les limites de ees zones. On observe en part ieul ier les diseonti- nuit6s pour les valeurs de s6quences 6gales h des puissances de 2 ainsi que la dissym6trie p rovenan t de l 'anisotropie daus l 'analyse des images utilis6es.

La figure 10 montre que la suppression par zones

eirculaires qui correspond h un filtrage passe-bas de l ' image n 'es t pas le proc6d6 le mieux adapt6 pour la

compression. Les zones hyperboliques donne n t une meilleure approximat ion de la r6part i t ion. Enf in les zones optimales conduisent , h taux de compression 6gal, h des facteurs de bru i t 16g6rement inf6rieurs h ceux obtenus par suppression en ampli tude.

Pour compl6ter ces r6sultats par des jugements

Fro. 11. - Limites des zones optimales de suppression : xs = 20, ~r I0,

. . . . "t'S ~ 5 .

subjeetifs de qualit6 on pr6sente sur la figure 12 les images restitu6es apr~s compression par diff6rents proc6d6s darts un rappor t de l 'ordre de 5. La d6gra-

dat ion la plus g6nante appara l t sur la figure 12c (zones circulaires) off la d iminut ion de d6finition

appara i t ne t t e me n t sur toute la surface de l ' image. Les images 12b et 12d out une qualit6 h pen pr6s 6quivalente.

Du point de r ue des r6sultats on pen t doric consi- d6rer que les proc6d6s de suppression en ampl i tude ou par zones optimales pr6sentent le m6me int6r~t. En fair, la suppression par zones est plus int6ressante pour des questions de raise en oeuvre : elle est plus simple h r6aliser puisqu'elle 6rite route la part ie de codage de l ' in format ion de position. D 'au t re part , si l 'on dispose d ' u n canal de t ransmiss ion de d6bit donn6 pour t r ansmet t re une s6rie d ' images, on vol t que pour

le proc6d~ de suppression en ampl i tude on devra soit calculer sur chaque image le scull de suppression par t i r de l 'h is togramme des ampli tudes pour obteni r le t aux de compression correspondant , soit fixer un scull a priori et disposer d 'une m6moire t ampon pour r6gulariser le d6bit d ' in format ion sur plusieurs images.

Enf in , on pen t penser que la suppression par zones est plus favorable du point de vue de la sensibilit6 aux erreurs de t ransmission qui n 'affectent alors que l ' ampl i tude de points isol6s de la transform~e tandis que, dans le cas de la suppression en ampl i tude , une erreur sur la longueur d 'une plage ou sur tou t sur les 616ments binaircs de diff6renciation points-plages se

r6percute sur plusieurs 616merits de la transform6e. Pour terminer , il est int6ressant de comparer les

d6gradations de qualit6 des images fi la suite des t ra i tements de compression sur les transform6es de Fourier et de Hadamard , telles qu'elles apparaissent sur la figure 12 et par exemple sur la figure 12 de [5].

A t a u x de compression 6gal les d6fauts sont subjeeti- vemen t plus g6nants pour la t ransformat ion de H a d a m a r d off les contours obliques sont d@rad6s

- - 245 - -

1 2 / 1 8 J. PONCIN [ANNAL~S D~S TiL~COMMUNICATIONS

FIa. 12. - - Images res t i tudes aprbs compress ion, a) rdfdrenee, b) suppress ion en amp l i t ude (To = 5,31), c) suppression pa r zone eirculaire ('re = 5,36), d) suppress ion pa r zone opt imale ('re = 5,31).

I. 26, n ~ 7-8, 1U71] T R A N S F O R M A T I O N D E I I A D A M A R D

par la d6composition de l ' image en carr6s alors que dans le cas dc Fourier la compression sc t r adu i t par un flou sur l ' image. Dans ces conditions, il semble quc la l imite supgrieure des t aux de compression utilisables se situe entre 5 et 10 pour Hadamard contre 10 h 15 pour Fourier. I1 est cependant probable que l ' in t roduct ion d ' un t r a i t cmen t de lissage h la res t i tu t ion permet t ra i t d 'ob ten i r des performances tr(~s voisines dans les deux cas.

IV. CODAGE DE LA T R A N S F O B M E E

IV.1 Principe du codage.

Dans les calculs effectu~s au chapitre precedent pour estimer les taux de compression, on a suppos6

P O U R CODAG-E E T C O M P R E S S I O N 13/18 de quant i f ica t ion gaussienne telle que, n 6 tant le

nombre d'616ments binaires de codage, les limites L t des intervalles de codage sont dgfinies par :

et les valeurs de codages X~ pour L~ < F ~ Li+ 1 par

j L X i -- F~12z ' ~ Li+ , -- F~12."- e d F = e dl.

,./xi

Une telle loi de codage est illustrge sur la figure 13 pour n -- 4 glgments binaires. Il est clair qu'elle est

mieux adapt~e qu 'une loi lin~aire h la r~part i t ion

s tat is t ique dans le plan de la transform~e et le seul probl~me reside dans le choix de la fonct ion ~ ( u , v) repr6sentant la var iante en un point en fonct ion de ses coordonn5es sgquentielles. On a vu en I I I - l - b qu' i l 6tait difficile de dgfinir th~or iquement une telle

x 0 Xl X 2 X3

Ji

X4 X5 X6 X? X8 X9 XlO Xll x12 X13

\

LI4 1 x14

1 F(u, v) x15

FrG. 13. -- Loi de quantiiication gaussienne h quatre 616ments binaires.

qu' i l ~tait possible de coder les points conserv6s de la transform~e avec le m6me hombre d'~l~ments binaires que les points de l ' image initiale, c'est-h-dire environ six ~l~ments binaires par point en moyenne. I1 est ndcessaire pour cela de d~finir une loi de codage

adaptde h la r6part i t ion s tat is t ique des valeurs des

616ments de la transform~e qui a dt6 6tudi~e ell III-1.

Pra t t , Kane et Andrews [9] out constat~ en part i-

culier qu 'une 6chelle de quant i f ica t ion lin~aire sur la

dynamique de la transform6e donna i t de mauvais

r~sultats, pr inc ipa lement du fait des erreurs de quant i -

fication impor tantes commises snr les ~l~ments de

faible valeur. Ils ont sugg~r~ l 'u t i l isa t ion d 'une loi

fonction sur tou t l 'espace transformS, et l 'on doit donc recourir h des approximat ions exp~rimentales. L 'hypoth~se de l '~galit5 de la variance en tous les points de l 'espace transform~ situ~s sur un m~me cercle centr~ h l 'origine a ~t~ utilis~e en [9] off une loi de la for int

~2(u, v) -- S o-("2+~'~)1 p

a 5t~ choisie. A la suite de l '~tude s ta t is t ique d~crite au paragraphe III-1 il nous a sembl~ preferable de

prendre comme courbes d 'dquivar iance des hyper-

boles u v : K et d 'dtudier exp~r imenta lement la relat ion

a(u2 v) = f(K).

- - 247 - -

14/18

Des courbes de m~me allure ont ~t~ obtenues sur plusieurs photographies repr6sent~es avec unc bonne approximat ion par unc loi de la forme :

(24) (~(u, v) = A / K t~ ,

avec, comme valeurs des param~tres A = 105 et

B = 0,6. L 'ana lysc de photographies restitu6es apr~s appli-

cat ion de ce proc6d6 de codage a mis en 6vidence les points suivants :

- - l e proc~d~ de codage qui suppose une distri- bu t ion gaussicnne h valeur moyenne nulle n ' es t pas applicable h l'~16ment de coordonn6es s6quentielles (u = 0, v -- 0) de la t ransform6e qui correspond h la

composante cont inue de l ' image et dont on a vu que la r~part i t ion s tat is t iquc 6tait particuli~re. Compte tenu de l ' impor tance de cct ~16ment dont d~pend le cadrage de la dynamiquc de l ' image restitu6e, la

solution la plus simple semble ~tre de le t r ansmet t re de mani~re ind~pendantc et avec toute la precision

n~cessaire (codage lin~aire h 23 ~ldments binaires) ; - - l ' e f f e t des erreurs de quant i f ica t ion est g~nd-

ra lement peu visible en raison du ph~nom~nc d'~ta- lement d~jh signal~. Toutefois, les grosses erreurs,

m~me si elles sont peu nombrcuses, p rovoquent des d~fauts g~nants avec l ' appar i t ion de faux contours aux limites des surfaces de d~coupage correspondantes (voir Fig. 3).

Ces errcurs p rov icnncn t g(~n~ralemcnt des ~lSments

de grande valeur absolue qui se t rouven t ramen~s par lc codage fi la valeur maximale du code (par exemplc dans le cas d ' un codage h 4 ~l~ments binaires

h la valeur X o si l '~l~ment cst n~gatif, h X15 s'il est positif).

Pour ~viter ce genre de d~fauts, deux ameliorat ions peuven t ~tre appliquSes. L 'une consiste h util iser comme loi ~(u, v) une loi sur~valude par rappor t h la loi exp~rimentale : on peut par exemple choisir :

1 ~r(u,v) = ~- Max ([ F ( u , v ] ) ,

s u r 1 h y p e r b o l e u/~' = K

qui condui t fi une expression de la meme forme que (24) avec une valeur plus 61ev6e pour le param~tre A.

L 'aut re ameliorat ion est l 'u t i l isat ion d 'une loi de codage ~ nombrc variable d'~lSments binaires.

IV.2 Loi de codage ~ nombre variable d'~16- ments binaires.

La loi de quant i f ica t ion gaussienne d~finie au paragraphe pr~cSdent revient h calculer pour chaque valeur F de la transform~c la valeur r~duite R = F / ~

puis ~ d~terminer l ' in terval le i tel que Li ~ R ~ LI+ 1. Pour d~coder on associe au code t ransmis i la valeur

r~duite X~ puis la valeur cod~e de la transform~.e

F = X ~ . Soit e = R -- Xi l 'erreur commise dans la quant i -

fication sur la variable r~duite, "& laquelle correspond A

une probabili t~ P(e), et E = F -- F ~ ~e l 'e r reur sur

la valeur codde de la transformde. On a :

P(E) = P ( a e ) = P(e) ,

J . P O N C I N [AxN)A,t.:s DES TI::IA~;[:(~MMI:'~ICA'IIO'~S

ct l 'on volt q u ' f une probabil i t6 donn~e correspond une crreur d ' a u t a n t plus grande que la variance est grandc.

Afin d 'uniformiser les erreurs sur l 'enscmblc des valeurs de la transform~e, il semble donc int6ressant de faire varier P(e) en fonction de ~, en ut i l i sant un hombre variablc d'616ments binaires pour coder la variable r6duite.

Si l 'on 6tudie la d is t r ibut ion des erreurs P(E)

en fonction de ~ et du nombre n d'616ments binaires de codage on troupe une loi de probabil i t6 illustr~e sur la figure 14 et scnsiblement d6finie par :

t P(E) = P pour [E[ < Eo ,

e ( E ) = o pour ] ~ ] > ~ o

avec E o = 1/2P ~ A ~ / 2 n , oh A est unc constante. On volt donc qu ' i l suffit d ' a jou te r un 61~ment

binaire chaque fois que ~ est multipli~ par 2 par rappor t h une valeur initiale.

Ainsi avec la loi g(u, v) d~finie en (24) en fonction de K = u v on troupe les zones de codage suivantes :

2 <~ K < 8 8 ~< K ~ 2 5

25 ~< K ~ 77 77 ~< K < 234

234 ~< K ~ 710 710 ~ K ~ 2 153

2153 ~< K ~ 7200

11 61~ments binaires, 10 616ments binawes,

9 61dments binaires, 8 616ments binalres, 7 616ments binaires, 6 616ments binaires, 5 61~ments binaires.

Compte tcnu du fait que les points cod~s sont

d ' a u t a n t plus nombreux que les hyperboles (uP = K )

sont plus dloign~es de l 'origine, on ob t ien t ainsi un nombre moyen d'~l~ments binaires par point cod~

~gal h 6 avec une meilleure r~part i t ion des erreurs commc le prouve le tableau I I calcul6 sur la t rans-

fortune de la photographie de la figure 12 :

TAnLEAU II

Codage h nombre Codage h nombre d'e.b, constant d'e.b, variable

n-=- 6 nmoy = 6

Probab. (tE[~ 200) 77,5 % 79,5 % Probab. ([EI~1000) 98 ,1% 99,96 % Probab. ([E 1~2000) 99,51% 99,99 % Erreur de codage

maximale . . . . . . . 42 000 2 700

I1 est clair en part iculier que la loi de codage h nombre d'dl~ments binaires variable permet d '6viter les erreurs importantes .

La figure 15 montre une image obtenue apr~s suppression par zones optimales, codage h hombre

d'~l~ments binaires variable et d6codage. Par comparaison, avec la figure 12d, on volt quc l 'op~rat ion

de codage-d~codage sur la transform~c n ' i n t rodu i t

aucun d~faut visible sur l ' image restitu6e.

V. CONCLUSION

A va n t de tirer quelques conclusions des r~sultats obtenus il convient de signaler un certain nombre

- - 248 - -

t. 26, n ~ 7-8, 1.q711 T R A N S F O R M A T I O N I)E I I A D A M A R D P O U R ( ' O D A G E ET C O M I ' R E S S I O N

J jii / ,

/ i . ' : • ]

.../ ' / /

...... ..."'~ • o / " .. ........... - : ~ . . ~ , ~ _ ~ ~ ~ , : ~

-I00 -90 -80 -70 -60 -5~ -40 -30 -20 -I0

~P(s [

i i i" i

-10 t i i

I i

\ ....,.. \ ,,, :':....

, ' : _ _ : . 10 20 30 40 50 60 70 80 90 100 E

FIG. 14. ('ourbes de probabilit& d'erreur (loi de quantilication gaussienne). - - - ~ - - 1 0 0 0 , n 5 e . b . ,

( ~ - 1 000, n 6 e.b., : l 000. t l 7 e.h.

FIa. 15. - - Image restitu6e apres suppression par zone optimale, codage fi nombre d'dl~ments binaires variables et

ddcodage.

15/18

dc points qui n6cessiteraient encore une 5tude plus approfondie.

-- Les essais r6alis~s jusqu 'h p r&en t ont port6 sur un pet i t nombre de photographies, et il conviendra i t de les g6n6raliser sur une assez large classe d' images.

Ces nouvelles expSriences ne devraient pas conduirc h une remisc en cause des principes de codage, puisque ceux-ci ont 6t~ d6finis h part ir d 'un module th~orique stat ist ique, mais elles permet t ra ien t un a jus t emen t optimal de certains parambtres (limites des zones de

SUl)pressions ; coefficients de la loi ~(u, v) par exemple).

- - L e probl&ne de la sensibilit6 aux erreurs de t ransmission devrai t Otre ~galement abord6 en obser- van t l'effet d 'erreurs al6atoires de probabil i t6 donn~e introduites entre le eodage et le d6eodage. Des proc6- dures de d6tection et de eorrection d 'erreurs pour- ra ient 6ventuel lement ~tre envisag~es.

- O n a vu au paragraphe I I I -3 que le d~faut subjectif le plus g6nant r~sul tant de la compression ~tait l ' appar i t ion de faux contours en earr&, ee qui justifie l '~tude d ' un proc6d~ de lissage. Une m~thode possible eonsisterait h remplacer a va n t la t rans- formation inverse les points non transmis, non plus par la valeur 0, mais par une valeur al~atoire eonforme

h la r6part i t ion stat is t ique en ces points.

- - Enfin, il scrait int~ressant d '~tudier le probl~me

de la dimension optimale de la t ransformat ion. En effet, clans les experiences r6alis6es jusqu ' ie i on a

sur tout utilis6 la dimension maximale N = 256, alors qu' i l est possible en divisant l ' image en sous-images

de ealculer des transform~es de plus petites dimen-

- - 249 - -

sions. Du point de vue du nombre d 'op6rations (donc

16 /18

du t emps de calcul) et du volume de m6moire n6ces- saire (en par t icu l ie r pour le s tockage de l ' image in term6diai re) une tel le division sera i t int6ressante. En effet, si N est la d imension de l ' image comple te et n la dimension d 'une sous-image, le calcul de la t ransform6e lin6aire sur une ligne de l ' image comple te ndcessite (N]n) (n log~ n) op6rat ions et celui de la t ransform6e p lane sur rou te l ' image.

(N[n) ~ (2 n ~ l o g g K ) = 2N 2 log~ n op6rat ions et l 'on voi t qu 'on a int6r6t h choisir n aussi p e t i t que possible. I1 est clair d ' au t r e p a r t que l ' exp lo i t a t ion des corr6- la t ions spat ia les entre poin ts d 'une image qui cst la base du proc6d6 de compression darts l ' espace t ransform6 n ' a de sens que si 1'on choisi t une sous- image con t enan t un hombre min ima l de points , e t que pour une qual i t6 subjec t ive donn6e le t a u x de compression est d ' a u t a n t plus 61ev6 que n e s t grand. On peu t donc penser qu ' i l existe entre ces deux exi- gences un compromis qu 'une 6tude exp6r imenta le p e r m e t t r a i t de pr6ciser.

Compte tenu des l imites qui v iennen t d ' e t r e signa- 16es, les p r inc ipaux r6sul ta ts de l '6 tude r6alis6e son t les suivants .

- - L a t r ans fo rma t ion de H a d a m a r d appl iqu6e une image permet , comme la t r ans fo rma t ion de Four ier , d ' ob ten i r une concen t ra t ion de l ' i n fo rmat ion

dans l ' espace t ransform&

Cette propri6t6 est u t i l i sable pour r6aliser une compression par suppression de points . Pa rmi les proc6d6s de suppression, la suppression par zones est la plus s imple '~ r6aliser ; m o y e n n a n t un choix correct des zones, elle condui t h des r6sul ta ts sub j ec t i vemen t comparables h ceux d 'une suppression en ampl i tude .

- - A t a u x de compression 6gaJ, les d6fauts r6sul- t a n t de la compression sur la t ransform6e de H a d a m a r d sont 16g~rement p lus g6nants que lo rsqu 'on ut i l ise la t r ans fo rma t ion de Fourier . Cet inconv6nient es t compens6 pa r une plus grande facilit6 de r6al isat ion de l 'organe de calcul de la t ransform6e. Les t a u x de compression envisageables pour une appl ica t ion pra-

t ique sont de l ' o rd re de 5 h 10. - - Six 616ments binaires en moyenne sont suffisants

pour coder les poin ts conserv6s de la t ransform~e avec une loi de quan t i f i ca t ion gaussienne. L 'u t i l i s a t ion d ' un nombre d'616ments binaires var iable en fonct ion de la posi t ion du po in t h coder pe rme t de minimal i ser les erreurs de quant i f ica t ion .

Pour compl6ter ces r6sul ta ts et en t i re r par t i , deux voies peuven t 6tre ddfinies: sur le p lan th6orique, il sera i t in t6ressant de poursu ivre des 6tudes en simu- la t ion sur les poin ts 6num6r6s au d6but de ce pa ra - graphe, para l l~ lement des reeherches plus fondamcn- ta les sur les propri6t6s de corr61ations entre poin ts d 'une image pou r r a i en t pe rme t t r e de d6finir un module m a t h 6 m a t i q u e et de pr6ciser les propri6t6s s ta t i s t iques de la r6par t i t ion de l '6nergie sur la t rans- form6e. I1 sera i t ainsi possible d 'ob ten i r une base de compara i son ent re diverses t r ans fo rmat ions (Four ier , H a d a m a r d , Haar , Karhunen-Lo~ve , etc.).

Enfin, sur te p lan des r6al isat ions, l ' 6 tude d ' une m a q u e t t e de t r a n s f o r m a t e u r lin~aire de H a d a m a r d ,

J . PONCIN [ANNALES I)ES q-'I'LI~COMMUNICA'rIONS

fonc t ionnan t en t emps r~el h la cadence du vis iophone, dev ra i t pe rme t t r e d ' a b o r d e r les probl~mes de (, faisa- bil i t6 ~> et d '6va luer h quel cofit en 6quipements d 'ex t r~mit6s pe uve n t 5tre obtenus les t a u x de compression impor t an t s qui carac t6r isent les m6thodes de codage par les t r ans fo rmat ions lin6aires.

A N N E X E I

C a l c u l d e l a t r a n s f o r m 6 e p l a n e d e H a d a m a r d .

1) Algorithme de calcul de let trans[orm~e lin~aire.

L 'a lgo r i thme est cons t ru i t sur le pr incipe expos6 par Crother et R a d e r dans la r6f6rence [11]. I1 consiste en n : log s N passages ident iques , chaque passage c o m p o r t a n t N]2 add i t ions et N]2 soustract ions .

A t i t re d 'exemple , on donne sur la figure A-1 le schema des opera t ions pour N = 8 (n = 3).

Remise en S~quences Donn~es Ierpassage 2epassage 3epassages~ or~im mdonn6es

fo

f l

f2

f3

f4

f5

f6

f7

~ ~o

sl

$2

$3

$4

S6

S7

A+B A-B Aj Ao 111~ B B~"

FIG. A-1. - - Schema de l 'a lgorithme de calcul de la transformation de Hadamard.

A la fin de n passages, les r6sul ta ts sont obtenus sous forme nature l le e t un dernier passage, d i t de remise en ordre, est n6cessaire pour ob ten i r les s6quences ordonn6es. On uti l ise pour cet te op6ra t ion une tab le de correspondance cons t ru i te au pr6alable su ivan t la r~gle :

S~ : S~ a v e c ]d6cimal = [ / n - 1 i n - 2 ... ]0]binaire ,

id6clmal = [in-1 in-s . . . i0]binalre ,

et i o = in-1 , il = in-1 + in-2 (modulo 2),

Zn-1 = ]1 + ]o (modulo 2).

Cet a lgor i thme n6cessite 2 N cases de m6moire et N (log~ N + 1) op6rat ions 616mentaires.

2) Mise en oeuvre du calcul.

Darts les exp6riences r~alis~es en s imula t ion , l ' aequi - si t ion de l ' image est fa i te au moyen d 'un appare i l d e

250 - -

t. 26, n ~ 7-8, 1971]

t61~photographie suivi d ' un codeur h 7 616ments

binaires par point. L ' image num6ris6e est ensuite r6duite h un tableau de 256 lignes x 256 points qui

correspond h une d6finition de 2 l ignes/mm duns le sens vertical et 3 points / ram duns le sens horizontal.

Dans une premiere phase l 'a lgor i thme de t ransformat ion lin6aire est appliqu6 "h chaque ligne de

l ' image, les valeurs /o, f~ .... / N - 1 6taut les luminosit6s deux points d'abscisse 0, 1, ..., N_ i sur la liguc.

On calcule ainsi l ' image interm6diaire,

[S] = [/] [ H ] .

La transform6e planc 6tant d6finie par l '6quat ion (5') il faut ensuite calculer

[ F ] = [H] [S] ou [ F l t = [Slt [I t]

puisque [H] est sym6trique.

La deuxi6me phase du calcul consiste donc h t ransposer la matrice image interm6diaire, la troisi6mc

6tant ident ique h la premiSre (application de l 'algo- r i thme aux lignes de l ' image interm6diaire transpos6e).

La t ransformat ion inverse se calcule de la m6me mani~re en remplaTant [/] par [F] t, et en divisant

t o u s l e s 616ments du tableau r6sultat par N ~ selon l '6quat iou (6').

Sur le ealculateur utilis6 (*), le temps de calcul n6cessaire pour les 1 re et 3 e phases d 'une transfor-

ma t ion plane 256 • 256 (celui de la 2 e phase d6pend

du volume de m6moire centrale occup6 pour la t ransposi t ion) est de 34 secondes. A t i tre de comparaison le temps correspondant pour la t ransformat ion de Fourier est de 72 secondes, ce qui montre que la

t ransformat ion de Hadamard est environ deux fois plus rapide ~ calculer.

T R A N S F O R M A T I O N D E H A D A M A R D P O U R C O D A G E E T C O M P R E S S I O N 17/18

A N N E X E I I

C a l c u l t h 6 o r i q u e de la d i s t r i b u t i o n des v a l e u r s

de l a t r a n s f o r m 6 e de H a d a m a r d ~t u n e d i m e n s i o n .

La transform6e ordonn6e/k une dimension du vecteur

{f(X)}x=0,. . . ,N-1 est le veeteur { F ( u ) } u = o , . . . , N _ 1

d6fini par :

N--1

F(u) = E f(z) a~,

a'j = ( - - 1 )q (x ,u ) , a v e c

et

(25) q(x, u) = XoU~,._ 1 + ... + x v ( u n _ v + u n - v - 1 ) +

... + x n - l ( u l + u o ) ,

oh ut et xt sont les 616ments de rang i des d6compo- sitions binaires de u et x.

N--1

a) Calcul de S~ = ~ a~. g$:0

La remise en ordre des s6qucnces de la transform6e est une simple op6ration de permuta t ions entre lignes

(*) G.E. 635 du Centre de calcul du CNET.

de la matr ice de H a d a m a r d naturel le dont la construc- t ion a 6t6 donnSe au w II-1. I1 est clair que toutes les

ligues d 'une telle matrice, h l 'except ion de la premiere, compor tent un nombre 6gal de coefficients § 1 et - - 1 donc on a :

zl S O = 0 pour toutes les s6quences u =/= 0.

L '6quat ion (14) est donc v6rifi6e.

N--1 b) Calcul de 2 (a~) 2 = Z (S:'.) 2 = (a,~_,} 2 -}-

x : l

(a~ j -~- a~v_2) 2 -~- ... -~- (a~,_u -J-a~, ~ ~- ... -~- a~) 2.

Soient [xn -1 . . . . . Xo] et [Xn-1 . . . . . xo] les d6compo- sitions binaires des entiers positifs x et x - 1 et soit p le rang de l'616ment binaire tel que :

X p = 1 ,

Xq = 0 , pour q < p .

Xq ~ Xq , pour q > p ,

On a alors x~o = 0 ,

xq = 1 , pour q > p .

L'expression (25) s'6crit donc pour q(x - - 1, u) :

q(X - - 1, U) = q ( x , U) - - (Un_ p § U n _ p _ l ) -t-

u n - 1 + ( u n - 1 + u~_2) + ... + ( u n - v + l + u n - v ) ,

= q(.~:, u) + 2(Un-1 § Un-2 § ... +

u n - v + l ) - - u n - v - 1 . D'ofl

(26) a~_l = ( _ 1)q(x-1 u) = a~(-- 1)u,,-p-,.

Consid6rons m a i n t e n a n t les s6quences u telles que 2~ ~< u < 2k+l pour lesquelles on a donc :

U k + i ~ ~ k + 2 ~ .- . ~ l l n - 1 ~ 0 ,

ll k ~ 1 ,

et divisons l ' in terval le [0 ~< x < 2 n] en 2 k intervalles

tels que

I K = [(K -- 1) 2 n-/~ ~< x < K 2 n - I t ' , K = 1 ... 2 k .

Dans cet intervalle, p, rang du premier 616ment binairc de x non nul est toujours inf6rieur h n - - k - - 1 saul pour le seul mult iple de 2 n -~ - I se t r o u v a n t dans cet intervalle, h savoir (2 K -- 1)2 n-k-1 .

En posant S = S . . . . K2n--k = aN- - i -[- aN--2 ~- ... "4- a K 2 n - - k ,

A = a u K 2 n - k - I ,

et en app l iquan t la loi de r6curence (26) on peu t donc calculer de droite ~ gauche le tableau A-1.

Sur l 'ensemble des intervalles I K on a donc : u

S ( U K - 1 ) 2 n - k = S K 2 n - - k . . . . . S ~ n ~- S ,

et S = 0 d'apr6s la derni6re 6galit6. I1 s 'en suit que :

~, ( S : ) ~ = A z [2(12+22+...+(2n-~-~--l)2)+22n-~-21, XEIK

avec A = + 1 par d6finition, donc A ~ = 1 Vk. E t f inalement

Y--1 2 ( a ~ ) 2 = Z ( S ; ) z = 2k Z ( S ; ) * - - ( S ; ) * ,

X =1 XfflK

- - 251 - -

1 8 / 1 8

X u

{lx

q

(K- -1 )2n-k - - A A

S

J . PONCIN

TABLEAU A I

[ANNALE$ DES T[:,I,P:COMMUNICATION8

(2~s (2 K - - l ) 2 . - k - , ( 2K- - 1) 2~ -~ - , + 1 - - A A A ~ T - .

K 2n-k - - 1 K 2n-k A

(par hypoth~se)

S + A s (par

hypoth~se)

avec Sg = 0, comme oil l ' a vu en a) On en d6dui t a i s6ment :

2 (~ ) 2= 2n[1 + 2Zn-~k-*][6 pour 2 lc ~< u < 2 k+l ,

( k = 0 ... n - - 1)

Pour u ~ 0 le calcul d i rec t est dvident puisque a: = 1, Vx. On t rouve dans ce cas 2 (al~ 2 = 12 + 2 2 + ... + (N - - 1) 2 = [N(N -- 1) (2 N - - 1)][6 mais l ' expression (12) du pa r ag raphe I I I - l - b ne se simplifie plus puisque S o #: 0. Le r6sul ta t est 6v idemment ident ique h celui t rouv6 en [14] pour la fr6quence spat ia le nulle de la t ransform~e de Fourier .

Manuscrit recu le 21 avril 1971.

BIBLIOGRAPHIE

[1] PROFIT (A.). Prospectives des r6seaux de transmission d'informatiou. Onde Electr. Fr. (janv. 1971), 51, n ~ 1, pp. 1-6.

[2] *** Special issue on redundancy reduction (num6ro special sur la r6duction de redondance). I.E.E.E., U. S. A. (mars 1967), 55, n ~ 3, pp. 251-~80.

[3] ESTOURNET (D.). Compression d'information de signaux d'images par les syst~mes diffdrentiels cod6s. Onde Electr., Fr. (sept. 1969), 49, no 8, pp. 858- 868.

[4] CHAaaI~RE (F.). Application de la compression de donndes au codage d'images fixes. Ann. Tdldcom- munie., Fr. (janv.-f6vr. 1970), 25, n ~ 1-2, pp. 29-40.

[5] MAaANO (Ph.), SCaWXRTZ (P. Y.). Compression d'information sur la transformde de Fourier d'une image.

Onde Electr., Fr. (d6c. 1970), 50, n ~ l i , pp. 908- 919.

[6] ANDREWS (H. C.). Computer techniques in image processing (Application des calculateurs au traitement des images). Academic Press. New-York ( i 97o ) , 187 p.

[7] HADAMARD (J.). R6solution d'une question relative aux d6terminants. Bulletin des Sciences MatM- matiques, s6rie 2, 17-1, (1893).

[8] HARMUTIt (H.F.). A generalized concept of frequency and some applications (Une g6n6ralisation du concept de fr6quence et quelques applications). I.E.E.E. Trans., IT. U. S. A. (mai 1968), 14, n ~ 3, pp. 375- 382).

[9] PRATT (W. K.), KANE (J.), ANDREWS (H. C.). Hada- mard transform image coding (Codage d'images par la transformation de Hadamard. Proc. I.E.E.E. U. S. A. (janv. 1969), 57, n ~ l , pp. 58-68.

[10] SUANKS (J. L.). Computation of the fast Walsh- Fourier transform (Calcul de la transform6e rapide de Walsh-Fourier). I.E.E.E. Trans., C, U. S. A. (mai 1969), 18, n ~ 5, pp. 457-&59.

[1]] CROTHER (W. R.), RADER (C. M.). Efficient coding of vocoder channel signals using lineartrans formation (Codage efficace de signaux d 'un vocoder canaux utilisant une transformation lin6aire. Proc. I.E.E.E., U. S. A. (nov. 1966), 54, pp. t594-1595.

[12] ULMAN (L. J.). Computation of the Hadamard transform and the R. transform in ordered form. (Calcul de la transformde de Hadamard et de la transform6e R sous forme ordonn6e). 1.E.E.E. Trans., C, U. S. A. (correspondance) (avril 1970), 19, n o 4, pp. 359-360.

[13] ESTOURNET (D.). Etude statistique d 'un signal d'image. Onde Electr. Fr. (sept. t969), 49, n ~ 8, pp. 8&8-857.

[14] SCHWARTZ (P. Y.). Analyse de la compression d'information sur la transform6e de Fourier d'une image. Ann. Tdldcommunic. Fr., (mars-avril 1971), 26, n ~ 3-4, pp. 334-144.

- - 2 5 2