1

Imperial College London Department of Electrical and Electronic Engineering

Digital Image Processing

PART 4 IMAGE COMPRESSIO 1

IMAGE COMPRESSIO !" DAME TALS

Academic responsi#le Dr$ Tania STAT%A&I

Room 811b Ext. 46229 Email: t.stathaki@ic.ac.uk

'ttp())***$commsp$ee$ic$ac$+,)-tania)

COMPRESSIO !" DAME TALS Introd+ction

In recent years, there ha e been si!ni"icant a# ancements in al!orithms an# architectures "or the $rocessin! o" ima!e, i#eo, an# au#io si!nals. %hese a# ancements ha e $rocee#e# alon! se eral #irections. &n the al!orithmic "ront, ne' techni(ues ha e le# to the #e elo$ment o" robust metho#s to re#uce the si)e o" the ima!e, i#eo, or au#io #ata. *uch metho#s are extremely ital in many a$$lications that mani$ulate an# store #i!ital #ata. In"ormally, 'e re"er to the $rocess o" si)e re#uction as a com$ression $rocess. +e 'ill #e"ine this $rocess in a more "ormal 'ay later. &n the architecture "ront, it is no' "easible to $ut so$histicate# com$ression $rocesses on a relati ely lo',cost sin!le chi$this has s$urre# a !reat #eal o" acti ity in #e elo$in! multime#ia systems "or the lar!e consumer market. &ne o" the excitin! $ros$ects o" such a# ancements is that multime#ia in"ormation com$risin! ima!e, i#eo, an# au#io has the $otential to become .ust another #ata ty$e. %his usually im$lies that multime#ia in"ormation 'ill be #i!itally enco#e# so that it can be mani$ulate#, store#, an# transmitte# alon! 'ith other #i!ital #ata ty$es. /or such #ata usa!e to be $er asi e, it is essential that the #ata enco#in! is stan#ar# across #i""erent $lat"orms an# a$$lications. %his 'ill "oster 'i#es$rea# #e elo$ment o" a$$lications an# 'ill also $romote intero$erability amon! systems "rom #i""erent en#ors. /urthermore, stan#ar#isation can lea# to the #e elo$ment o" cost,e""ecti e im$lementations, 'hich in turn 'ill $romote the 'i#es$rea# use o" multime#ia in"ormation. %his is the $rimary moti ation behin# the emer!ence o" ima!e an# i#eo com$ression stan#ar#s.

.ac,gro+nd
0om$ression is a $rocess inten#e# to yiel# a com$act #i!ital re$resentation o" a si!nal. In the literature, the terms source coding, data compression, bandwidth compression, an# signal compression are all use# to re"er to the $rocess o" com$ression. In the cases 'here the si!nal is #e"ine# as an ima!e, a i#eo stream, or an au#io si!nal, the !eneric $roblem o" com$ression is to minimise the bit rate o" their #i!ital re$resentation. %here are many a$$lications that bene"it 'hen ima!e, i#eo, an# au#io si!nals are a ailable in com$resse# "orm. /it'o+t compression0 most of t'ese applications *o+ld not #e feasi#le1 E2ample 1( 1et us consi#er facsimile image transmission. In most "acsimile machines, the #ocument is scanne# an# #i!itise#. %y$ically, an 8.2x11 inches $a!e is scanne# at 233 #$i- thus, resultin! in 4.54 6bits. %ransmittin! this #ata o er a lo',cost 14.4 kbits7s

mo#em 'oul# re(uire 2.62 minutes. +ith com$ression, the transmission time can be re#uce# to 15 secon#s. %his results in substantial sa in!s in transmission costs. E2ample 3( 1et us consi#er a i#eo,base# 08,R&6 a$$lication. !+ll4motion 5ideo, at 43 "$s an# a 523 x 483 resolution, !enerates #ata at 23.546 6bytes7s. 9t this rate, only 41 secon#s o" i#eo can be store# on a 623 6:yte 08,R&6. 0om$ression technolo!y can increase the stora!e ca$acity to 54 minutes, "or ;<*,!ra#e i#eo (uality. Ima!e, i#eo, an# au#io si!nals are amenable to com$ression #ue to the "actors belo'. 6 T'ere is considera#le statistical red+ndanc7 in t'e signal$ 1. +ithin a sin!le ima!e or a sin!le i#eo "rame, there exists si!ni"icant correlation amon! nei!hbour sam$les. %his correlation is re"erre# to as spatial correlation. 2. /or #ata ac(uire# "rom multi$le sensors =such as satellite ima!es>, there exists si!ni"icant correlation amon!st sam$les "rom these sensors. %his correlation is re"erre# to as spectral correlation. 4. /or tem$oral #ata =such as i#eo>, there is si!ni"icant correlation amon!st sam$les in #i""erent se!ments o" time. %his is re"erre# to as temporal correlation. 6 T'ere is considera#le information in t'e signal t'at is irrele5ant from a percept+al point of 5ie*$ 6 Some data tends to 'a5e 'ig'4le5el feat+res t'at are red+ndant across space and time8 t'at is0 t'e data is of a fractal nat+re$ /or a !i en a$$lication, com$ression schemes may ex$loit any one or all o" the abo e "actors to achie e the #esire# com$ression #ata rate. %here are many a$$lications that bene"it "rom #ata com$ression technolo!y. %able 1.1 lists a re$resentati e set o" such a$$lications "or ima!e, i#eo, an# au#io #ata, as 'ell as ty$ical #ata rates o" the corres$on#in! com$resse# bit streams. %y$ical #ata rates "or the uncom$resse# bit streams are also sho'n. Application
;oice 8 ksam$les7s, 8 bits7sam$le *lo' motion i#eo =13"$s> "ramesi)e 156x123, 8bits7$ixel 9u#io con"erence 8 ksam$les7s, 8 bits7sam$le

Data Rate "ncompressed Compressed

64 kb$s 2.35 6b$s 64 kb$s 2,4 kb$s 8,16 kb$s 16,64 kb$s

;i#eo con"erence =12"$s> "ramesi)e 422x243, 8bits7$ixel 8i!ital au#io 44.1 ksam$les7s, 16 bits7sam$le ;i#eo "ile trans"er =12"$s> "ramesi)e 422x243, 8bits7$ixel 8i!ital i#eo on 08,R&6 =43"$s> "ramesi)e 422x243, 8bits7$ixel :roa#cast i#eo =43"$s> "ramesi)e 523x483, 8bits7$ixel <8%; =29.94 "$s> "ramesi)e 1283x523, 8bits7$ixel

43.41 6b$s 1.2 6b$s 43.41 6b$s 63.84 6b$s 248.84 6b$s 1.44 ?b$s

64,568 kb$s 1.28,1.2 6b$s 484 kb$s 1.2,4 6b$s 4,8 6b$s 23 6b$s

Ta#le 1$1( Applications for image0 5ideo0 and a+dio compression$ In the "ollo'in! "i!ure, a systems ie' o" the com$ression $rocess is #e$icte#.
E@0&8ER

8i!ital ima!e, ;i#eo an# 9u#io

*ource 0o#er

0hannel 0o#er

8E0&8ER

8i!ital ima!e, ;i#eo an# 9u#io

*ource 8eco#er

0hannel 8eco#er

!ig+re 1$1 Generic compression s7stem %he core o" the enco#er is the source co#er. %he source co#er $er"orms the com$ression $rocess by re#ucin! the in$ut #ata rate to a le el that can be su$$orte# by the stora!e or transmission me#ium. %he bit rate out$ut o" the enco#er is measure# in bits $er sam$le or bits $er secon#. /or ima!e or i#eo #ata, a $ixel is the basic element- thus, bits $er sam$le is also re"erre# to as bits $er $ixel or bits $er $el. In the literature, the term compression ratio, #enote# as c r , is also use# instea# o" bit rate to characterise the ca$ability o" the com$ression system. 9n intuiti e #e"inition o" c r is
cr = source coder input size source coder output size

%his #e"inition is some'hat ambi!uous an# #e$en#s on the #ata ty$e an# the s$eci"ic com$ression metho# that is em$loye#. /or a still,ima!e, si)e coul# re"er to the bits nee#e# to re$resent the entire

ima!e. /or i#eo, si)e coul# re"er to the bits nee#e# to re$resent one "rame o" i#eo. 6any com$ression metho#s "or i#eo #o not $rocess each "rame o" i#eo, hence, a more commonly use# notion "or si)e is the bits nee#e# to re$resent one secon# o" i#eo. In a $ractical system, the source co#er is usually "ollo'e# by a secon# le el o" co#in!: the channel co#er =/i!ure 1.1>. %he channel co#er translates the com$resse# bit stream into a si!nal suitable "or either stora!e or transmission. In most systems, source co#in! an# channel co#in! are #istinct $rocesses. In recent years, metho#s to $er"orm combine# source an# channel co#in! ha e also been #e elo$e#. @ote that, in or#er to reconstruct the ima!e, i#eo, or au#io si!nal, one nee#s to re erse the $rocesses o" channel co#in! an# source co#in!. %his is usually $er"orme# at the #eco#er. /rom a system #esi!n ie'$oint, one can restate the com$ression $roblem as a bit rate minimisation $roblem, 'here se eral constraints may ha e to be met, inclu#in! the "ollo'in!: Specified le5el of signal 9+alit7. %his constraint is usually a$$lie# at the #eco#er. Implementation comple2it7. %his constraint is o"ten a$$lie# at the #eco#er, an# in some instances at both the enco#er an# the #eco#er. Comm+nication dela7. %his constraint re"ers to the en# to en# #elay, an# is measure# "rom the start o" enco#in! a sam$le to the com$lete #eco#in! o" that sam$le. @ote that, these constraints ha e #i""erent im$ortance in #i""erent a$$lications. /or exam$le, in a t'o, 'ay telecon"erencin! system, the communication #elay mi!ht be the ma.or constraint, 'hereas, in a tele ision broa#castin! system, si!nal (uality an# #eco#er com$lexity mi!ht be the main constraints.

Lossless 5ers+s loss7 compression

Lossless compression
In many a$$lications, the #eco#er has to reconstruct 'ithout any loss the ori!inal #ata. /or a lossless com$ression $rocess, the reconstructe# #ata an# the ori!inal #ata must be i#entical in alue "or each an# e ery #ata sam$le. %his is also re"erre# to as a re ersible $rocess. In lossless com$ression, "or a s$eci"ic a$$lication, the choice o" a com$ression metho# in ol es a tra#e,o"" alon! the three #imensions #e$icte# in /i!ure 1.2- that is, co#in! e""iciency, co#in! com$lexity, an# co#in! #elay. Coding Efficiency %his is usually measure# in bits $er sam$le or bits $er secon# =b$s>. 0o#in! e""iciency is usually limite# by the in"ormation content or entropy o" the source. In intuiti e terms, the entro$y o" a source A $ro i#es a measure "or the Bran#omnessB o" A. /rom a com$ression theory $oint o" ie', sources 'ith lar!e entro$y are more #i""icult to com$ress ="or exam$le, ran#om noise is ery har# to com$ress>. Coding Complexity %he com$lexity o" a com$ression $rocess is analo!ous to the com$utational e""ort nee#e# to im$lement the enco#er an# #eco#er "unctions. %he com$utational e""ort is usually measure# in terms o" memory

re(uirements an# number o" arithmetic o$erations. %he o$erations count is characterise# by the term millions o" o$erations $er secon# an# is o"ten re"erre# to as 6&C*. <ere, by o$eration, 'e im$ly a basic arithmetic o$eration that is su$$orte# by the com$utational en!ine. In the com$ression literature, the term 6IC* =millions o" instructions $er secon#> is sometimes use#. %his is s$eci"ic to a com$utational en!ineDs architecture- thus, in this text 'e re"er to co#in! com$lexity in terms o" 6&C*. In some a$$lications, such as $ortable #e ices, co#in! com$lexity may be characterise# by the $o'er re(uirements o" a har#'are im$lementation. Coding Delay 9 com$lex com$ression $rocess o"ten lea#s to increase# co#in! #elays at the enco#er an# the #eco#er. 0o#in! #elays can be alle iate# by increasin! the $rocessin! $o'er o" the com$utational en!ineho'e er, this may be im$ractical in en ironments 'here there is a $o'er constraint or 'hen the un#erlyin! com$utational en!ine cannot be im$ro e#. /urthermore, in many a$$lications, co#in! #elays ha e to be constraine#- "or exam$le, in interacti e communications. %he nee# to constrain the co#in! #elay o"ten "orces the com$ression system #esi!ner to use a less so$histicate# al!orithm "or the com$ression $rocesses. /rom this #iscussion, it can be conclu#e# that these tra#e,o""s in co#in! com$lexity, #elay, an# e""iciency are usually limite# to a small set o" choices alon! these axes. In a subse(uent section, 'e 'ill brie"ly #escribe the tra#e,o""s 'ithin the context o" s$eci"ic lossless com$ression metho#s.

Coding Efficiency ,0om$ression RatioE Coder Complexity

Coding Delay

,6emory re(uirementsE ,Co'er re(uirementsE ,&$erations $er secon#E !ig+re 1$3 Trade4offs in lossless compression$

Loss7 compression
%he ma.ority o" the a$$lications in ima!e or i#eo #ata $rocessin! #o not re(uire that the reconstructe# #ata an# the ori!inal #ata are i#entical in alue. %hus, some amount o" loss is $ermitte# in the reconstructe# #ata. 9 com$ression $rocess that results in an im$er"ect reconstruction is re"erre# to as a

lossy com$ression $rocess. %his com$ression $rocess is irre ersible. In $ractice, most irre ersible com$ression $rocesses #e!ra#e ra$i#ly the si!nal (uality 'hen they are re$eate#ly a$$lie# on $re iously #ecom$resse# #ata. %he choice o" a s$eci"ic lossy com$ression metho# in ol es tra#e,o""s alon! the "our #imensions sho'n in /i!ure 1.4. 8ue to the a##itional #e!ree o" "ree#om, namely, in the si!nal (uality, a lossy com$ression $rocess can yiel# hi!her com$ression ratios than a lossless com$ression scheme. Signal Quality %his term is o"ten use# to characterise the si!nal at the out$ut o" the #eco#er. , 'hich can be ex$resse# as

%here is no uni ersally acce$te# measure "or si!nal (uality. &ne measure that is o"ten cite# is the si!nal to noise ratio SN
SN = 13 lo!13 encoder input signal energy noise signal energy

%he noise si!nal ener!y is #e"ine# as the ener!y measure# "or a hy$othetical si!nal that is the #i""erence bet'een the enco#er in$ut si!nal an# the #eco#er out$ut si!nal. @ote that, SN !i en in #ecibels =#:>. In the case o" ima!es or i#eo, !SN instea# o" SN . %he calculations are essentially the same as in the case o" SN as #e"ine# here is =$eak si!nal,to,noise ratio> is use# , ho'e er, in the

numerator, instea# o" usin! the enco#er in$ut si!nal one uses a hy$othetical si!nal 'ith a si!nal stren!th o" 222 =the maximum #ecimal alue o" an unsi!ne# 8,bit number, such as in a $ixel>. <i!h SN or !SN alues #o not al'ays corres$on# to si!nals 'ith $erce$tually hi!h (uality. 9nother measure o" si!nal (uality is the mean o$inion score, 'here the $er"ormance o" a com$ression $rocess is characterise# by the sub.ecti e (uality o" the #eco#e# si!nal. /or instance, a "i e $oint scale such as "ery annoying, annoying, slightly annoying, perceptible but not annoying, an# imperceptible mi!ht be use# to characterise the im$airments in the #eco#er out$ut. In either lossless or lossy com$ression schemes, the (uality o" the in$ut #ata a""ects the com$ression ratio. /or instance, ac(uisition noise, #ata sam$lin! timin! errors, an# e en the analo!ue,to,#i!ital con ersion $rocess a""ects the si!nal (uality an# re#uces the s$atial an# tem$oral correlation. *ome com$ression schemes are (uite sensiti e to the loss in correlation an# may yiel# si!ni"icantly 'orse com$ression in the $resence o" noise. Signal Quality ,:it error $robabilityE ,*@RE ,6ean o$inion scoreE

Coding Efficiency ,0om$ression RatioE Coder Complexity

Coding Delay

,6emory re(uirementsE ,Co'er re(uirementsE ,&$erations $er secon#E !ig+re 1$: Trade4offs in loss7 compression$

Iss+es in compression met'od selection

In this cha$ter, 'e ha e intro#uce# some "un#amental conce$ts relate# to ima!e, i#eo, an# au#io com$ression. +hen choosin! a s$eci"ic com$ression metho#, one shoul# consi#er the "ollo'in! issues: 1ossless or lossy. %his is usually #ictate# by the co#in! e""iciency re(uirements. 0o#in! e""iciency. E en in a lossy com$ression $rocess, the #esirable co#in! e""iciency mi!ht not be achie able. %his is es$ecially the case 'hen there are s$eci"ic constraints on out$ut si!nal (uality. ;ariability in co#in! e""iciency. In some a$$lications, lar!e ariations in co#in! e""iciency amon! #i""erent #ata sets may not be acce$table. Resilience to transmission errors. *ome com$ression metho#s are more robust to transmission errors than others. I" retransmissions are not $ermitte#, then this re(uirement may im$act on the o erall enco#er, #eco#er #esi!n. 0om$lexity tra#e,o""s. In most im$lementations, it is im$ortant to kee$ the o erall enco#er,#eco#er com$lexity lo'. <o'e er, certain a$$lications may re(uire only a lo' #eco#in! com$lexity. @ature o" #e!ra#ations in #eco#er out$ut. 1ossy com$ression metho#s intro#uce arti"acts in the #eco#e# si!nal. %he nature o" arti"acts #e$en#s on the com$ression metho# that is em$loye#. %he #e!ree to 'hich these arti"acts are .u#!e# also aries "rom a$$lication to a$$lication. In communication systems, there is o"ten an inter$lay bet'een the transmission errors an# the co#in! arti"acts intro#uce# by the co#er. %hus, it is im$ortant to consi#er all ty$es o" error in a system #esi!n. 8ata re$resentation. In many a$$lications, there is a nee# to su$$ort t'o #eco#in! $hases. In the "irst $hase, #eco#in! is $er"orme# to #eri e an intelli!ible si!nal- this is the case in #ata bro'sin!. In the secon# $hase, #eco#in! is $er"orme# to #eri e a hi!her (uality si!nal. &ne can !eneralise this notion to su!!est that some a$$lications re(uire a hierarchical re$resentation o" the #ata. In the com$ression context, 'e re"er to such com$ression schemes as scalable compression methods. %he

notion o" scalability has been a#o$te# in the com$ression stan#ar#s. 6ulti$le usa!e o" the enco#in!,#eco#in! tan#em. In many a$$lications, such as i#eo e#itin!, there is a nee# to $er"orm multi$le enco#e,#eco#e o$erations usin! results "rom a $re ious enco#e, #eco#e o$eration. %his is not an issue "or lossless com$ression- ho'e er, "or lossy schemes, resilience to multi$le enco#in!,#eco#in! cycles is essential. Inter$lay 'ith other #ata mo#alities, such as au#io an# i#eo. In a system 'here se eral #ata mo#alities ha e to be su$$orte#, the com$ression metho#s "or each mo#ality shoul# ha e some common elements. /or instance, in an interacti e i#eo$hone system, the au#io com$ression metho# shoul# ha e a "rame structure that is consistent 'ith the i#eo "rame structure. &ther'ise, there 'ill be unnecessary re(uirements on bu""ers at the #eco#er an# a re#uce# tolerance to timin! errors. Inter'orkin! 'ith other systems. In a mass,market en ironment, there 'ill be multi$le #ata mo#alities an# multi$le com$ression systems. In such an en ironment, transco#in! "rom one com$ression metho# to another may be nee#e#. /or instance, i#eo e#itin! mi!ht be #one on a "rame by "rame basis- hence, a com$ression metho# that #oes not ex$loit tem$oral re#un#ancies mi!ht be use# here. 9"ter i#eo e#itin!, there mi!ht be a nee# to broa#cast this i#eo. In this case, tem$oral re#un#ancies can be ex$loite# to achie e a hi!her co#in! e""iciency. In such a scenario, it is im$ortant to select com$ression metho#s that su$$ort transco#in! "rom one com$resse# stream "ormat to another. Inter'orkin! is im$ortant in many communications en ironments as 'ell.

T%E SO"RCE CODER

In this course 'e are intereste# in ex$lorin! arious com$ression techni(ues re"errin! to the so+rce coder only, 'here the ima!e com$ression takes $lace. 9 !eneral $roce#ure "or ima!e #ata com$ression is sho'n in the "ollo'in! block #ia!ram =/i!ure 1.4>. T'is is t'e so+rce coder of t'e pre5io+s diagram1 ori!inal ima!e #ata

1 #ecom$osition trans"ormation mo#ellin! etc. "eature selection coul# be: $re#icti e co#in! trans"orm base# co#in! "ractal subban#

3 (uantisation in "inite number o" le els : symbol enco#in! 0oul# be <u""man

Compressed image

ELEME TS O! I !ORMATIO T%EOR;

9ny in"ormation !eneratin! $rocess can be ie'e# as a source that emits a se(uence o" symbols chosen "rom a "inite al$habet ="or exam$le, text: 9*0II symbols

n ,bit ima!es:

2 n symbols>.

*im$lest "orm o" an in"ormation source: discrete memoryless source =86*>. *uccessi e symbols $ro#uce# by such a source are statistically in#e$en#ent. 9 86* is com$letely s$eci"ie# by the source al$habet S = Gs1 , s2 , , s n F an# the associate# $robabilities G p1 , p 2 , , p n F .

Self #nformation$
# = si > = lo! 2 1 = lo! 2 pi pi

, ,

the occurrence o" a less $robable e ent $ro i#es more in"ormation the in"ormation o" in#e$en#ent e ents taken as a sin!le e ent e(uals the sum o" the in"ormation

%"erage #nformation $er *ymbol or Entropy o" a 86*:

& = S > = pi # = si > = pi lo! 2 pi bits7symbol

i =1 i =1

Inter$retation o" Entro$y: , , 9 era!e amount o" in"ormation $er symbol $ro i#e# by the source =#e"inition> 9 era!e amount o" in"ormation $er symbol an obser er nee#s to s$en# to remo e the uncertainty in the source

N th extention o" the 86*: ?i en a 86* o" si)e

n,

!rou$ the source into blocks o" N

symbols. Each block can no' be consi#ere# as a sin!le source symbol !enerate# by a source S N 'ith al$habet si)e n N . In this case
& = S N > = N & = s >

10

Noiseless Source Coding 'heorem 1et S be a source 'ith al$habet si)e

an# entro$y & = S > . 0onsi#er co#in! blocks o" N source

symbols into binary co#e'or#s. /or any > 3 , it is $ossible by choosin! N lar!e enou!h to construct a co#e in such a 'ay that the a era!e number o" bits $er ori!inal source symbol l a"g satis"ies
& = s > l a"g & = s > +

11