WEIGHTED UNIVERSAL TRANSFORM CODING: UNIVERSAL IMAGE COMPIRESSION WITH THE KARHUNEN-LOEVE TRANSFORM


We introduce a two-:-;tage iiiiiversxl traiisforiii codc for iiiiagc coiii1)ressioii. Tlic cock> coiiiliiics Kar1iuiic.n-Loive traiisforni c:otfiiig with wciglited uiiivcrsal bit alocation (WUBA) [ I] iii il two-stage algoritlini analogoiis to the algorithm for weighted universal vect;or yuaiitixatioii (WUVQ) [2. 31. The, ciicodcr u s c ~ a col- 

lectioii of i,raiisforiii / bit allocatioii pairs ratlicr tliaii a siiiglc trwisforiii / l i t allocatioii pair ( a s iii JPEG) or a single traiisforiii with a variety of hit allocations (as in WUBA). We dc ihe h t l i an eiicodiiig algoritliiii for idiicviiig optiiiial coiii1)rcssioii usiiig ii col1tx:tioii o f traiisforiii / bit dlocation pairs aiid a tcdiniqiic: for dcsigiiiiig 1oc:ally optiiiial cdlcctioiis of traiisforiii / bit allocation pairs. We dcnioiistrate perforiiiaiice risiiig the i i i e ~i i sqiiart:d t x o r tlist,ortioii iiieasiirc. On a seyimice of coiiiliiicd tvxt aiitl gray scalc iiiiages. tlic a l g o r i t h i acliicvcs iip to 2 tlB iiiiprovciiicmt over a JPEG stylc~ coder iisiiig tlie discrete msiiie traiisforiii (DCT) aiid an o1)tiiiiiLI collectioii of bit allocatioiis. 111) to 3 tlB iiiiproveninlit over a JPEG style coder iisiiig tlie DCT and a siiiglc (optiiiial) bit alloctitioii. up to G tlB o v c ~ aii ciitropy c.oiistraiiic:d WUVQ with firsta i d sccoiid-stage vect,or dinieiisioiis eqiial to 1 G aiid 4 respectively. iiiid iip to 10 dB iiiiproveiiicnt over an eiitropy c:oiistlaiiied vector qiiaiitizcr (ECVO ) with vcctor diiiiensioii 4. 

IN-TRODUCTION

Uiiivcrswl :iolircC cotlliig is the I~raiicli of soiir(:c c:otliiig theory that descril,es tlit: existence aiitl 1)crforiiiaiice of (lata coiiipressioii algorithnis that arc eff'ectivr iiot jiist oii a siiiglc sourcc. h i t on a class of soiirccs. Tlie l i t w aturt, of miivcrsal soiirc(: coding lias rccc:iitly yielded a varicty of tcc:liiiiquc.s for asyiiiptotically optiiiial lossy coiiiI>rrssion, or qiiaiitiantioii. of noiirces with iiiikiiowii or varying statistics. T h e schrnies yield optiiiial perforiii;iiicx: its tlie (lata sccpeiicc h g t h aiid quaiitixcr vector diiiiciisioii grow witliout I)oiuitl. Uiifortriiiately. the coiiipiitation associated with iisiiig a vector qiiaiir grows expoiieiitixlly with t h vector diiiiension. ant1 tlms iii practiccx. ..uiiiversal" vector quantizers itre typically iiiiplcnient ed at very siiiall vector diiiicmsions. 
Transform codiiig provides one iiietliod of acliieviiig reasonahle coniplexity codes a t high effective vector diiiiciisions. hi traiisforiii coding. tlie data is traiisforiiicd prior to coding. Tlie transforiiiatiou used is tlcsigricd to decorrelate tlic sigiial ant1 t,o c:onipact iiiost of its riiergy into n siiiall iiiuii1)rr of traiisforiii c.oiiipoiieiit,s. 
By clecorrelatiiig the sigiial. we rciiiove iiiiicli of the Iiciicfit of coding vectors ratlicr than coding Thus most traiisforiii codcs follow tlie traiisforiri step 11y scalar rather tliaii vector qiiaiitization. Siiicr tlic traiisforiii conipoiieiits are typically of varying magiiitudes aiid iiiiportaiices. it '.bit allocatioii algoritliiii" is uscd t o specify tlic ratc: at wliicli each coiii1)oiieiit of tlic, traiisfornicd d a t a Mock will Ix: codcd. This rat<> ciescriptioii is typically enihodic:d iii a yuantizatioii iliatrix. wliitili descrihes the coarseliess with wliidi each c:oliil)oiiciit of the tritlisforliid d a t a block will I ~c CYIc.odcd. Tlic optiiiial l i t allocatioii stratcgy is data dvl)(wclciit. Giveii a traiisforiii that is efkctivc: at dccorrelating a i d c:oiiipactiiig tlic sigiial and a hit a1loc:atioii strategy that is well iiiatclied to tlir: statistics of tlit' ti.iilisforliicd data, it trilllsforai codc call achieve i i ~i cff'ectivc vt,c:tor cliiiieiisioii ;qq)roximately equal to the tmiisforiii block size. Fiirther. if the traiisforiiiatioii is not coiiipiitationally coiiiplex. the resiiltiiig transforiii cod(: will liave a iiiiich lower coiiiplexity than a vector qimitizer with a coiiipar~tl~le v w h r tliiiieiisioii. 
Tlie Karliiiiieii-Lokve Traiisforiii (KLT) is a datadcpeiideiit traiisforiii that achieves optimal decorrelatioii (all off'-(liagoiial teriiis of tlic traiisforiiitd data's covtwimw iiiatrix are idciitically eqiial t o zcro) aiid optiiiial m ~g y coiiipactioii [4]. To date. tlic KLT h a s not 1,ccii po1)iiIar iii data coiiiprension algorithiiin diir to its data-drI)eiideiicc. Relying solely on traditional tcc:liiiiqiic>s. tlit traiisforiii would liitve to citlicr I)c dies m iii xlvaiicc (wliicli i i i ~a i i s t,liat tlic statistics of tlic data liavc to 1)e kiiowii iii advaiicc,) or coiii1)utcd diuiiig the eiicodiiig process aiid coniiiiiiuicatetl to tjlie decoder. which is expensive hot,li in teriiis of couipiitatioiial coiiiplcxity aiid iii tclriiis of ratc. Givcii t,lic:scx tlifficiiltics with usiiig tlic optiiiial traiisforiii. soiircc codc dcsigiicrs t o tlatcx liavc> rc,licd priiiiarily oil iioii-optiiii;d. tlat a-iiidep eiideiit traiisforiii CO des. For exaiiiple. t lie JPEG iiiiage codiiig staiidartl uses tlie Diswete Cosiiie Traiisforiii (DCT). wliicli does a good job of a1)proxiiiiatiiig tlie KLT for iiiaiiy iiatural or siiiootli iiiiages wit,li high correlation [C;] hiit achieves less siiccess witli low correlation. liigli contrast iiiiages siicli as iiiiages of text. 
We liere iise iiiiiversal soiirce codiiig t,ec:hiiiqiies to design a iiiiiversal traiisforni code. a traiisforiii code whose perforiiiaiice oii every soiirce iii soiiie broad class achieved if' tlic optiiiial traiisforiii aiid tlic optiiiial l i t allocatioii were iisecl for every soiivce eiicoiiiit,ered. The algorit,lini eiiiploys a collection of traiisforiii / hit a1locatioii pairs. 111 Scxctioii 2 we dcscribc tlic wciglited uiiivcrsal traiisforiii codiiig algoritliiii. Sectioii 3 coiit aiiis cxpcriiiieiital rcsults. of sources appro"c1lcs tl1c perforlllallcc! tl1at would b C ? 

THE WEIGHTED UNIVERSAL TRANSFORM CODING ALGORITHM (WUTC)

Let :r' = ( ~1 . . wliicli iiicaiis that we dcscrilx a iiew traiisforiii / 1)itallocatioii pair for each data block. 
Tlie t,otal distortioii associated wit,li eiicodiiig data Mock x N with traiisforiii / lit, allocation pair / j ( i i ( : Tlieii the transform T,* has. in t h e first row. the cigeiivector corresponding t o the largest eigenvalue of V,. in t h e second row, the eigenvector corresponding to the second largest eigenvalue, and so on. Given a transform. the optimal bit allocation inay be accoiiiplished by a n optimal lit-allocation design algorithiii. For exaniple, if tlie individual coinponeiits of the transform d a t a block are scalar quantized aiid theii described using independent entropy codes, as in the example of [l], then each term in tlie quantization matrix inay be chosen independently to iiiiiiiiiiize the Lagrangian perforiiiaiice associated with that component. 
~: ~) ) is N/' d( P. j (,q 2 ) ) ) = d( 2::. j ( &( Z N ) ) ).
The WUTC design algoritliin employs an iterative descent tcclinique t o niiiiiniize the expected Lagrangian pcxrforinaiice. We initialize the algorithm with an arbitrary prefix code s and collection { p ( S ) : j. E s} of transform / bit allocation pairs. Each iteration proceeds t h o u g h three steps which we enumerate below. 
I O - 

5-

1 Newest Neighbor Encodinq Optimize tlie firststage encoder 6 for the given first-stage decoder @ and prefix code '<. 
2 Decoding to th,e Cen,troid. 

EXPERIMENTAL RESULTS

In Figure 

.

  . . :cl) E X' represent, an I-diiiieiisional data vector.we iiiultiply 2' 1)y itii r! x H iiivertiblc iiiatrix T. tlicm T reprcseiits a liiiear traiisforiii of tlic: data. If wc: tlieii scalar yuaiitize thc %th coiiipoiiciit of the resiiltiiig tmiisforiii vector at rate hi. ,i = 1.. tlieii O' represents a hit, allocatioii strategy. Siippose that we are givcii soiiie gciieric sdiciiie for ciicodiiig a traiisforiiicd vc:ctor Tx:' witli bit allocatioii b'. Tlicii itssociatetl witli aiiy traiisforiii / I i t allocation pair (T. (+) is a yitaiitizer C = p o cy with encoder CY : X' + S aiid t\eco(~er /j : s + that t,oget~lier iiiap t,lie iiiput spacc X' of possil,lc data vectors to tlic output s1):icc: 2' of possiMc rcproductioiis 11y way of a iiiiary prefix code s. Let f l ( & (T. 0 ' ) ) = ~~( : , ~' . / ~( f ~( T ~: ' ) ) ) he tlie total distortion achieved by traiisforiiiiiig :I;' with transforin iiiatrix T aiid tlieii qiiaiitiziiig the rcsiiltiiig traiisforiii doiiiaiii vector wit11 Iiit allocatioii b'. Siiiiilarly. let ,T(xL:'. ( T . b ' ) ) = Icx(Tz:' )\ dciiotc tlie associated rate. (While ,T(z:', (T. h ' ) ) equals E.; tii oii average. ,i,(:r', (T, t+)) will vary witli x' in a varia1)le-rate syst c:111. ) we iiext colisider a collection (T~. ti: 1. ( ~2 . ti; 1. . . . . (TM. tik) of traiisforni / hit allocation pairs. Usiiig tlit yuaiitizatioii iiitcrprctatioii of a two-stagc: wciglitcd uiiiversal code [3], wc colisider this collectioii to lie a codebook of traiisforiii / bit allocatioii pairs. T h i s wc defiiie a -first,-st,age cpiaiitizer" [j o fi wit,li eiicoder ii : zN + S ancl decoc~er 6 : S + c tliat iiiaps tlie iiipiit space of possililc data blocks .cN to tlic outpiit spxt: C of possi1,lc traiisforiii / bit allocation pairs (T. b'). Wv licrc assuiiic that. N is a iiiultiple of I . Tlic, first-stag: encoder chooses for each N-block a siiigle traiisforiii / bit, allocation pair. We theii iise the clioseii pair to ciicodc eac.li of tlie I-vcctors in :I?. In traiisforiii codes like JPEG. N c q i a l s the size of a siiigle iiiiagc. For many applications. we may want, siiialler N to allow the traiisforiii / hit allocation pair to cliaiige witliiii a siiigle iiiiage. The exaiiiple of Section 3 iises N = 1. 


i=l

  The t o t d rate associated with eiicodiiig z N iiicliides hotli tlic ratc associated with dc3scril)iiig tlic traiisforiii/ ])it allocatioii pair f i ( & ( x N ) )aiid tl-ie rate associated witli usiiig tlic clioseii pair to describe tlic data. Tlius N/' ? . ( . . N . f i ( ; r ( P ) ) ) = IG(z:N)I + Cr.(.f./?(;t(.:"))). i=l Tlicii. usiiig a Lagraiigiaii iii order to iiiiiiiiiiize thc; distmtioii siihject to a coiistraiiit oil tlie r a t e tlie optimal first-stage encoder fi* for a giveii collection of traiisforiii / 1,it allocation pairs fi is i y * ( : I : = arg iiiii>[ N . j ( s ) ) + xr (:I?. fi( s) )] S E S for every x N . We call the optiiiial fir rcca~est sr,e%,yltd~or ciicoder. giveii first-stage encoder ti satisfies Likcwise. tlie optiinal first-stage dccoder y* for a P * ( s ) = arg iiiin E [d(xN. ( ~. b ' ) ) (T.b' ) E C +Xr(XN, (T,b'))J f i ( X N ) = 4 for cvery s E S. We call the procem of dcxigiiiiig t,lic: optiiiial first-stage (lecoder decodirry to Giveii that, tlie KLT iiiaxiiiiixes the codiiig gain over all ortliogiial traiisforiii codes (e.g.. [G. Appcwdix C]). 




  wc 1ic:re set tlic traiisforiii iii tlic optiiiial traiisforiii / bit allocation pair to tlic KLT iriatclicd t o tlic statistics of the data to lie coded. Usiiig this choice we accoiiiplisli tlie optiiiial decorrelatioil and eiiergy coiiipictioil for tlic sourc:c iii opcxatioii. Tlie KLT is cal-cu1atc:d a s follows. For a giveii iiidex s. 1c:t ,i/t.L l~ tlic mean of tlie 1 vectors that mapped to s. i.e.. ,HI, = ( I / N ) CZzl N/IEIXflii(XN) = s]. Likewise, let V, be tlie correlation matrix associated with these vectors, i.e.. V, = ( I / N ) ~/ 1 ~[ ( ~, 1 ) ( X , l ) ' l & ( x N ) = SI. 




  / bit allocatioii pairs and bit allocatioiis respectively.andN = i != 64 for all experiiiieiits.Each systeiii was trained on a siiigle 2048 pixel by 2048 pixel iiiiagc sc,aiiiicd froni a page of IEEE S p e c t ~i t m Mayu-Z%rw aiid tcsted oil aiiother page from the saiiie issue.Each pagc liad rouglily equal amouiits of text a i d gray scale iiiaterial.All rates are reported in teriiis of eiitropy.WUTC achieves up to 2 dB iiiiproveiiieiit over WUBA. up to 3 dB iiiiproveiiieiit over a siiigle bit allocation systeiii, u p t o G dB improvement over WUVQ.aiid 1113 to 10 dB iiiiproveiiieiit over ECVQ.T h e perforiiiaiice ciirves for all traiisforiii codiiig systeiiis can be expected to shift slightly t,o the left if they iise a lossless code iiiore efficient than iiidepeiidelit entropy codiiig.sucli a s the JPEG code (run-leiigth followcd by Huffiiiaii codiiig) or a zerotree code.In Figure2. we coiiipare the perforiiiaiice of tlie WUTC tLo the perforiiiaiice of an optiiiial traiisforiii code with a siiigle traiisforii-i / bit allocatioii pair. The iinage used is iiitlcpciideiit of tlie test set. 


	1. we conipare tlie performance of tlie W U T C
	and WUBA algorithiiis to the performance of single KLT / bit allocation pair and tlie perforinaiice of a
	DCT-based cock analogous t o t h v JPEG algorithm.
	All transforin code inipleiiieiitations discussed here use
	iiidepeiident entropy codes t o losslessly encode each
	quantized coefficient. W U T C aiid WUBA contain G4

traiisforiii 
0-8186-7310-9/95 $4.00 0 1995 IEEE
Le Eflro, Philip A Ch
WEIGHTED UNIVERSAL TRANSFORM CODING: UNIVERSAL IMAGE COMPIRESSION WITH THE KARHUNEN-LOEVE TRANSFORM