for 2D and 3D images
F. Lazzaroni, A. Signoroniand R.Leonardi
Signals and Communications Lab. - DEA- University of Brescia, Italy
via Branze, 38- I25123 Brescia, Italy Tel.+39030 3715434 Fax.+39030380014
ABSTRACT
Current wavelet-based image coders obtain high performance thanks to the identi cation and the
exploita-tion of the statistical properties of natural images in the transformed domain. Zerotree-based algorithms,
as \Embedded Zerotree Wavelets" (EZW) and \Set Partitioning In Hierarchical Trees" (SPIHT), o er high
Rate-Distortion (RD) coding performanceand lowcomputational complexity by exploiting statistical
depen-denciesamonginsigni cantcoeÆcientsonhierarchicalsubbandstructures. Anotherpossibleapproachtries to
predict the clusters of signi cant coeÆcientsby means of someform of morphologicaldilation. An example
of amorphology-basedcoderis the\Signi cance-Linked ConnectedComponentAnalysis"(SLCCA) that has
shownperformancewhicharecomparabletothezerotree-basedcodersbutisnotembedded. Anewembedded
bit-plane coderis proposed herebasedon morphologicaldilation of signi cant coeÆcientsand context based
arithmetic coding. The algorithm is able to exploit both intra-band and inter-band statistical dependencies
amongwaveletsigni cantcoeÆcients. Moreover,thesameapproachisusedbothfortwoandthree-dimensional
wavelet-based image compression. Finally the algorithms are tested on some 2D images and on a medical
volume,bycomparing theRD resultsto thoseobtainedwiththestate-of-the-artwavelet-basedcoders.
Keywords: 2Dand3Dimagecoding, wavelettransform,embedding,arithmetic coding,morphology.
1.INTRODUCTION
In the last years the needto store and communicate largeamounts of visual data has required thestudy of
newcompression techniques. Nowadays,there exists arich literatureandstandardizationactivitiesregarding
imagecoding. Amongthebesttwo-dimensional(2D)compressionschemes,waveletbasedzerotreecodingo ers
highRate-Distortion (RD)performancewithlowcomputationalcomplexity. Thissystemiscomposed ofthree
stages: wavelet transform,zerotree-basedquantization andentropycoding. The successof thezerotree-based
approach is due to the statistical exploitation of the inter-subband dependency among insigni cant wavelet
coeÆcients, which is pointed out by the reorganization of coeÆcients in subband tree structures. Examples
of coding techniques that use the zerotree idea are \Embedded Zerotree Wavelet" coding (EZW) 1
and \Set
PartitioningInHierarchicalTrees"(SPIHT). 2
MoreoverEZW andSPIHT codershavebeenextended to the
third dimension 3{5
obtaining satisfactory results in termsof RD and complexity performance for volumetric
data.
In addition to the zerotree idea other statistical dependencies in the wavelet domain canbe highlighted.
Forexampletherecent\EmbeddedBlockCodingwithOptimizedTruncation"(EBCOT) 6
algorithm,adopted
in the JPEG2000 standard,combines RD optimization, block coding and context-based arithmetic coding in
an original way, which has demonstrated a good correspondence to the statistical nature of wavelet data.
Such statistically matchedbehavioris thebasiswhichallowsto reachalow-complexityand progressive
high-performance coder. The zerotree idea can also be reformulated in a dual approach in order to de ne the
possibilityto ndstructuresofsigni cantcoeÆcientsinthewaveletdomain. Thus,analternativeway,inorder
toexplorethestatisticaldependenciesamongwaveletcoeÆcients,canbethepredictionofthesigni canceand
the coding of asigni cance-map bya morphologicaldilationapproach. Thebasicreason that justify theuse
Furtherauthor'sinformations:
ofamorphology-basedapproachis thehypothesisof thepresenceofenergyclustersin waveletsubbands. A
recently proposed algorithm based on morphologicalrepresentation of wavelet data, the \Signi cance-Linked
ConnectedComponentAnalysis"(SLCCA), 8
hasshowncompressionperformancesimilartothebest
zerotree-basedalgorithms. HoweverSLCCAdoesnotprovideanembeddedbit-stream.
Weproposehereanewembeddedbit-planecoderbasedonmorphologicaldilationofsigni cantcoeÆcients
which is able to exploit both intra-band and inter-band statistical dependencies among wavelet signi cant
coeÆcients. Moreoverweextendouralgorithmtothree-dimensionalimagecompression. Thecodingresultsof
theLena, Barbaraand Goldhillimages for2D applicationsand ofthetest medicalvolumeCTSKULL 3{5
for
3Dapplicationsareoftensensiblysuperiortothestate-of-the-artcompressionperformance.
Therest ofthepaperisorganizedasfollow. InSection II thestatistical properties ofwavelet-transformed
natural images and their exploitation in zerotree-basedand morphologicalalgorithms are rst discussed. In
Section III our Embedded Morphological Dilation Coder EMDC is presented in detail. In Section IV the
entropycoderisdescribed. InSectionVanexperimentalperformanceevaluationrespecttothestate-of-the-art
wavelet-basedcodersispresented. Finally, theconclusionsof thepaperarein SectionVI.
2.ZEROTREE AND MORPHOLOGICALCLUSTERING APPROACHES
2.1. Statistical properties of wavelet coeÆcients
Recognizing the statistical properties of wavelet-transformed naturalimages and building astatistical model
ofthese datais afundamental taskin thedesignofahigh-performancewavelet-basedcoder. Weresumehere
someimportantfeaturesofwavelet-transformedcoeÆcientsofnaturalimages:
1. spatial-frequencylocalization;
2. decayofmagnitudeofwaveletcoeÆcientsacrosssubbands;
3. magnitudecorrelationofcoeÆcientsatsamespatial locationinconsecutivedecompositionlevels 1
;
4. magnitudecorrelationofneighboring coeÆcientswithin asubband 9
;
5. clustering ofsigni cantcoeÆcients(biggerthanacertainthreshold)withinthesubbands. 7,8
The rst property is a feature of the wavelet transform and means that each wavelet coeÆcient refers to a
speci careaoftheoriginaldata(i.e. itisspatiallylocalized)andrepresentsinformationinacertainfrequency
range(i.e. it isfrequencylocalized). Theotherpropertiesare dueto thehigh-orderstatistical characteristics
of natural images. In fact, the non-stationary nature of an highly correlated image source (natural image)
re ectson thenon-stationarynature oftheweaklycorrelated transformedcoeÆcients. This situation hasled
to thesigni cant-nonsigni cantdichotomyand totheexploitationofhigh-orderstatisticalpropertiesofthe
wavelet coeÆcientsbothin thequantizationand entropycoding steps. The various wavelet-basedcoderstry
to exploit someof thementionedstatistical characteristicsin order to obtaingood RD performancewith low
computationalcomplexity.
2.2. The zerotree approach
Zerotree-basedcoders,asEZW 1
andSPIHT, 2
basicallyexploitthemagnitudedecayofthewaveletcoeÆcients
across the subbands by the use of subband trees collection structure, where the children of a node are the
coeÆcients at the same spatial location in the ner scale of a subband decomposition. In fact, although in
this kindof structurethelinear correlationbetweenaparent andits childrenis irrelevant,there isarelevant
dependencyamongtheirmagnitudes. Experimentsonnaturalimagesshowedacorrelationbetweenthesquare
magnitude ofachildand its parentbetween 0.2and 0.6 with astrongconcentrationaround 0.35. 1
Besides,
themagnitudeofwaveletcoeÆcientstypicallydecaysalongtheparent-childrenhierarchy. 10
Solargecollection
ofcoeÆcients,whichcanbeorganizedin multiresolutiontrees,arecomposed ofcoeÆcientssmallerthantheir
progenitors. This behaviorcanbedescribed bycoding thesub-trees composed ofall insigni cantcoeÆcients
withasinglesymbol(zerotree) orbyusing similarset-partitioningtechniques. Othertheoreticaljusti cations
oftheperformanceofzerotree-basedcoderscanbefoundforexamplein. 11
inter-bandclusters.
2.3. The clustering of signi cant coeÆcients
Evenifthezerotree-basedalgorithmsareveryeÆcient,theydon'texploit animportantstatistical propertyof
wavelet-transformednaturalimages: theclustering ofsigni cantcoeÆcients. Thispropertycanbeveryuseful
forcompressionpurposesbecauseitallows,givenasmallnumberofsigni cantcoeÆcients,toidentifytheareas
wherethegreatestpartofsigni cantcoeÆcientsmaybefound. Theclustering tendencyofsigni cantwavelet
coeÆcients is due, as stated above, to the characteristics of naturalimages. In fact these kind of data are
typically composedof largehomogeneousortextured regionsdelimited byedgediscontinuities. Homogeneous
regionsmostly consist oflowfrequency components andso thecoeÆcientsassociatedwith these areasin the
medium-highfrequencysubbands typicallyhavelow magnitude. Textured regions consistof amixtureof low
andhighfrequencycoeÆcients. Edgesaremostlycomposedofhighfrequencycomponentsandsotheygenerate
arelativelysmallnumberofcoeÆcientswith highmagnitude in themedium-high frequencysubbands. These
coeÆcients have a spatial distribution which depends on the local direction of the object boundaries in the
originalimagewithrespecttothespatialorientationofthehighandlow-passsubband lters. Theclusteringof
signi cantcoeÆcientscanbeempiricallyobservedinFig.1{awheretheclusterswithinawaveletsubbandmainly
correspondtotheedgesandsecondlytothetexturedareasintheoriginalimage. Wecanalsoobservethatthese
clusterstendtobelocalizedatsamespatialpositionsand lteringorientationsateachdecompositionlevel. 7
In
fact,sincetheclustersareduetospatialedgesandtexturedareas,weexpectsomeenergyconcentrationinthese
zonesatallscales. Forexampleinthepresenceofaverticaledgeweexpectto ndclustersinallsubbandswith
horizontal high-pass lteringand verticallow-pass ltering. We callinter-band clustersthese sets of clusters
which canbelinkedtogetherthroughsomeform ofhierarchicalcollectionstructures(seeFig.1{b).
2.4. The morphological approach
A method for exploiting the clustering of signi cant coeÆcients is the morphological dilation. 7,8
Before
describing this technique we give a brief review of some aspects of mathematical morphology. A survey of
theapplicationofmorphologytomulti-dimensionalsignalprocessingmaybefoundin. 12
Weconsider aset S
ofpointsinaN-dimensionalstructureand astructuringelementB that de nesamorphology-baseddistance.
The morphological dilation of set S by B is the union of all points falling under the structuring element B
when it is centered at each point of S. Inour context the set B consists of the already identi ed signi cant
and8.
morphologicaldilationwerefertoasequenceofmorphologicaldilations,appliedtonewsigni cantcoeÆcients.
The iteration nishes when a dilation does not nd new signi cant coeÆcients. Moreover, we use the term
inter-bandexpansiontoindicateasortofmorphologicaldilationperformedfromparentstowardstheirchildren
inthetreecollectionstructures. Nowwecanseehowthisconceptscanbeusedinsigni cance-mapcoding.
Weconsiderthewaveletsigni cantcoeÆcientswithrespecttoacertainthreshold. AsseenthesecoeÆcients
tend to form clusters within the various subbands, linked in inter-band clusters. If we know the position of
a very small number of signi cant coeÆcients, one for each inter-band cluster, we can identify many other
signi cantcoeÆcientsbyapplyinganiterativemorphologicaldilationandan inter-bandexpansion. This way,
wecanmapagreatnumberofsigni cantcoeÆcientswhich resultto becollectedin inter-bandclusters. Todo
this wehaveto analyzearelativesmall numberofcoeÆcientsand explicitlycodeasingle coeÆcientposition
foreachinter-bandcluster.
2.5. Our embeddedmorphological approach
Ourprimaryobjectiveisto introduceamorphologicalapproachwithin anembeddedframework. Considering
asetofdecreasingthresholds(typicallythedecreasingpowersoftwo),thegrowingoftheclustersofsigni cant
coeÆcientscanbeobservedatthesametime(Fig.2). Ifateachstep(i.e. foreachthreshold)amorphological
dilationandaninter-bandexpansionisapplied tothealreadysigni cant-markedcoeÆcients,thelargepartof
signi cant coeÆcients can be predicted, with a high probability, by analyzing arelative little number of the
total of the wavelet coeÆcients. In fact, at each threshold level, it is reasonable to look for new signi cant
coeÆcientsinsidethealreadydetectedclusters. Whenthese clustershavebeenprocessedtheattentioncanbe
moved in other regionsin order to nd new clusters ortoidentify isolatedsigni cantcoeÆcients. Using this
approachtwoimportante ects canbeobtained:
1. Theregionswithahigherexpectedpercentageofsigni cantcoeÆcientareanalyzed rst. Thismeansthat
thesigni cance-map coding bit-streamis statisticallyordered by distortionreduction. Asort ofimplicit
rate-distortionoptimizationisobtained,withoutanycomputationalcomplexityincrementortheneedto
transmitauxiliaryinformation.
2. ThewaveletcoeÆcientscanbepartitionedintwosubsetscorrespondingtoregionswherethereareclusters
ofsigni cantcoeÆcientsandregionswhereweexpectto ndonlyafewisolatedsigni cantcoeÆcients. As
shownintwoexperimentsexposedin 7
theentropyofthecompositemodelobtainedthroughthispartition
is widelyinferior totheglobal entropyofthewaveletcoeÆcients. Thisfact canbe exploitedduring the
ingrayinsigni cant oneswithin thearea consideredforinspection. (a)Initialsigni cance-mapfor athresholdequalto
16. (b)Signi cance-mapafterintra-band morphological dilationand inter-bandexpansion. (c)Signi cance-mapafter
additional-morphologicaldilation. (d)Finalsigni cance-mapafterexplicitpositioncoding.
3. EMDC:EMBEDDED MORPHOLOGICAL DILATION CODING
Like in EZW and SPIHT, the proposed progressive algorithm EMDC is a bit-plane coder composed of two
iterativesteps: asortingpass(orsigni cance-mapcoding)thatidenti essigni cantcoeÆcients(i.e. largerthan
agiventhreshold)andcodestheirposition,andare nementpassthataddstotheprecisionofthe
signi cantly-marked coeÆcients. Initially thethresholdis setto thelargestpoweroftwowhich issmallerthan thelargest
magnitudeofthewaveletcoeÆcients. Onceascanningstrategyisde ned,thepositionsofsigni cantcoeÆcients
arecodedinthesortingpass,thenare nementpassfollowstocompletethebit-planecoding. Atthispointthe
thresholdishalvedandthescanningrestarts. Thiswayanembeddedbit-streamisobtained. Thecodingofthe
signi cance mapis acrucial taskin this kindof scheme. The main ideawepropose forobtainingan eÆcient
coding ofthe signi cance-map is to look for newsigni cantcoeÆcients near thealready signi cantly-marked
oneswithinthesamesubband(intra-bandmorphologicaldilation),andamongtheirsons(inter-bandexpansion)
inthecorrespondingtreestructure. Moreprecisely,thesigni cance-mapcodingofeachsubbandissubdivided
infour phases: intra-bandmorphologicaldilation,inter-bandexpansion,additionalmorphologicaldilationand
explicitposition coding.
1. Intra-band morphologicaldilation: thecoeÆcients near thesigni cantly-markedones are analyzed
through an iterative morphological dilation; this operation is repeated each time a new signi cant
co-eÆcient is found also during the other three phases. We tested di erent structuring elements for this
morphologicaldilationand weobtainedbestresultsusing a3x3square forimages anda3x3x3cubefor
volumes.
2. Inter-band expansion: thesonsofthesigni cantly-markedcoeÆcientsareanalyzed.
3. Additional morphologicaldilation: amorphologicaldilationisfurtherperformedaroundcoeÆcients
analyzedinpreviousphasesandresultedinsigni cant;thisoperationisrepeateduntiltwosuccessivescans
donotleadto thedetectionofanynewsigni cantcoeÆcient. Eveninthis casethestructuringelement
used isa3x3squarein2Danda3x3x3cubein 3D.
4. Explicit positioncoding : thepositionofremainingsigni cantcoeÆcientsisexplicitlysent.
Intra-bandmorphologicaldilationandinter-bandexpansionallowtoexplorethealready-identi edclusters,
theadditionalmorphologicaldilatationanalyzethecoeÆcientsontheborderofclustersand nallytheexplicit
positioncodingallowto ndnewclusters(especiallyatthestartofthecoding)andcodethepositionofisolate
signi cant coeÆcients. Thefour stepsareordered in termof theireÆciency considering astatistical measure
expansion is performed and so on. With this method the compression ratio at the end of a sorting pass is
substantiallyunalteredbuttheperformanceat intermediatepointsissuperior. *
Fig.3shows,withanexample,howtheEMDCalgorithm worksduringthevariousphaseswithinasubband.
3.1. EMDC data structures
Forimplementationpurposesthesigni cance/insigni canceinformationofeachwaveletsubband(l;i)(wherel
isthedecompositionlevelandi thesubbandnumber)arestoredinto twosetsoflists:
thelistsofsigni cantcoeÆcients(LSC
l;i
),containingallsigni cantly-markedcoeÆcients;
the lists of insigni cant coeÆcients (LIC
l;i
), containing the coeÆcients analyzed in the present sorting
passwhichresultedinsigni cant. Theselistsareusedfortheadditionalmorphologicaldilation.
Besides, the same information is also stored in a wavelet coeÆcients matrix (WCM) in order to allow an
immediate knowledgeof thestatus ofthecoeÆcients: signi cantly-marked("S"), insigni cantly-marked("I")
ornotyetanalyzed("NA")inthecurrentsortingpass. Finallywede neadatastructuretostoreeachsubband
status SS(l;i), i.e. the next step that has to be executed in the signi cance-map coding. Possible valuesin
thisdata structureare: morphologicaldilation("MD"),inter-bandexpansion("IE"), additionalmorphological
dilation("AMD"), explicitposition coding ("EPC"),sorting passterminated ("SPT")andall coeÆcientsare
signi cant("ACS").
3.2. EMDC algorithm
The coding algorithm is virtuallythe samefor 2D and 3Dimage coding. Toknowif in asubband there are
new(not alreadymarked)signi cantcoeÆcients(withrespecttothecurrent2 n
threshold)weusethefunction
S
n
(l;i). This function is equalto 0ifall signi cantcoeÆcients in the(l;i)subband are already been found,
whileitisequalto1iftherearesigni cantcoeÆcientsto nd. ThescanningofthewaveletcoeÆcients,ifnot
re-routedbythemorphologicaloperations,is performedbyrowandthesubbandscanningis fromlowto high
resolution.
1. Initialization: MAX =maximummagnitude of wavelet coeÆcients; output n=blog
2
(MAX)c,set the
threshold to 2 n
, set all the LSC
l;i
and LIC
l;i
to emptylists, set all elementsof WCM to "NA" and all
subbandstatusto "MD"
.
2. SortingPass:
foreachsubband(l;i)withstatusnotequalto"ACS"do:
{ ifS
n
(l;i)=0output0andsetSS(l;i)to"SPT";
{ else output1andifLSC
l;i
innotemptysetSS(l;i)to "MD",otherwiseifl1andLSC
l 1;i is
notemptyset SS(l;i)to"IE"andotherwisesetSS(l;i)to"EPC".
(a) Intra-bandmorphologicaldilation: foreachsubband(l;i)withSS(l;i)equalto"MD":
for each entry in the LSC
l;i
analyze the adjacent coeÆcients in the same subband: for each
coeÆcientofcoordinatesx do:
{ ifWCM(x )isnotequalto"NA" passtothenextcoeÆcient;
{ elseifthecoeÆcientissigni cant(biggerthan2 n
): output 1,output itssign,addit tothe
endofLSC
l;i
andsetWCM(x )to"S";
{ ifitisnotsigni cant: output0,additto theendof LIC
l;i
and setWCM(x )to "I";
ifS
n
(l;i)=0thensetSS(l;i)to"SPT"andoutput0;
l 1;i
to"AMD".
(b) Inter-band expansion:foreachsubband(l;i)withSS(l;i)equalto"IE":
Foreachentryinthefather-subbandLSC
l 1;i
thefour(eightin3D)sonsareanalyzed: foreach
coeÆcientofcoordinatesx do:
{ ifWCM(x )isnotequalto"NA" passtothenextcoeÆcient;
{ elseifthecoeÆcientissigni cant: output1,outputitssign,addittotheendofLSC
l;i ,set
WCM(x )to "S"and immediatelyperformanintra-banddilation(a)onthenewcoeÆcient
addedtoLSC;
{ ifitisnotsigni cant: output0,additto theendof LIC
l;i
and setWCM(x )to "I";
ifS
n
(l;i)=0thensetSS(l;i)to"SPT"andoutput0;
elseoutput1setSS(l;i)to"AMD".
(c) Additional morphologicaldilation:foreachsubband(l;i)withSS(l;i)equalto "AMD":
For each entryin LIC
l;i
ofthe subbandexcept thoseincluded in thisadditional morphological
dilationanalyzetheadjacentcoeÆcientsinthesamesubband: foreachcoeÆcientofcoordinates
x do:
{ ifWCM(x )isnotequalto"NA" passtothenextcoeÆcient;
{ if the coeÆcient is signi cant: output 1, output its sign, add it to the end of LSC
l;i , set
WCM(x )to "S"andimmediatelyperformanintra-banddilation(a)onthenewsigni cant
coeÆcient;
{ ifitisnotsigni cant: output0,additto theendof LIC
l;i
and setWCM(x )to "S";
Repeat the additional morphological dilation on the new entry of LIC
l;i
until two successive
scansdonotleadto newsigni cantcoeÆcients;
ifS
n
(l;i)=0thensetSS(l;i)to"SPT"andoutput0;
elseoutput1andsetSS(l;i)to"EPC".
(d) Explicit positioncoding :foreachsubband(l;i)withSS(l;i)equalto "EPC":
The position of remaining signi cant coeÆcientsis explicitly sentas a binary numberusing a
suÆcient number ofdigits consideringthe numberof notanalyzedcoeÆcientsin thesubband;
alsoin thiscasethesigni cantcoeÆcientsareaddedtoLSC
l;i
andanintra-banddilation(a)is
performedaftereach position coding;
A special symbol (for examplethe position 1) is sent when all signi cant coeÆcientsin the
subband(l;i)havebeenidenti ed.
3. Re nement Pass: foreach entryin all LSC's,except those includedin thelast sorting pass,output the
n-th mostsigni cantbit;
4. Setthedatastructuresfornextsortingpass:
EmptyallLIC
l;i ;
allelementsin WCM equalto "I"aresetto "NA";
ifasubband(l;i)hasallcoeÆcientssigni cantly-markedthenSS(l;i)issetto"ACS".
5. Quantization-StepUpdate: decrementn by1(thethresholdishalved)andrepeatfrom step2.
Note thatthe rstsigni cantcoeÆcientis alwayscodedbyanexplicitpositioncoding. Thealgorithm can
In orderto increase the coding eÆciency, the bit-stream produced by theprogressivequantization is entropy
codedusing acontext-basedadaptivearithmetic coder,basedon. 13
Forthispurpose weconsider theEMDC
algorithm as a binary non-stationary symbol source with memory. First we identify seven main contexts in
the structure of EMDC (structural contexts): sign bits, re nement bits, four contexts for the four phases of
signi cance-mapcodingandacontextfortheoutputoftheS
n
(l;i)function. Moreover,insidesome
structural-context we locate some sub-contexts (proper contexts) in order to better exploit the statistical relationships
betweenthewaveletcoeÆcients. Weusethesamesetofcontextsfor2Dand3Dapplications.
4.1. Signi cance-map coding contexts
As seen in Section II there is a correlation between magnitude of the wavelet coeÆcients at same spatial
and frequency location in consecutive resolution levels and between neighboring coeÆcients within a same
subband. Thismeansthat there isalso acorrelation betweenthesigni cancevalueof thesecoeÆcients. This
correlationcanbeexploitedbythearithmeticcodingthroughtheidenti cationofcontextstobeassociatedto
thesigni cance-mapstructure. Inordertoconsiderandexploitthecausaldependenciesbetweentwoconsecutive
bit-planerelatedsigni cance-maps,wepropose(seealso 5
)tomakeuseofthreesigni cancevalues,distinguishing
not onlybetween signi cantand insigni cant coeÆcients, but also between previously-signi cant (marked as
signi cantinaprevioussortingpass)andnewly-signi cantones(markedsigni cantinthecurrentsortingpass).
Forthesigni cance-mapcodingweidentify12di erentcontexts:
7contextsforintra-bandmorphologicaldilation:
{ 1contextforthe rstlevel(lowerresolution)subband;
{ 6 (3x2) contexts for the other subbands depending on the signi cance value of the father (three
possible values: previously-signi cant, newly-signi cant and insigni cant) and the presence of at
least one signi cantly-marked coeÆcient among the adjacent ones towards the low-pass ltering
direction (twopossiblevalues,exceptfortheHHsubband'scoeÆcientswhich haveauniquevalue);
2contextsforinter-bandexpansion,dependingonthesigni cancevalueofthefather(previously-signi cant
ornewly-signi cant);
1contextforadditionalmorphologicaldilation;
1contextforexplicitpositioncodingand1contextfortheoutputoftheS
n
(l;i)function: these bitsare
notcompressed,sothesecontextsarenotadaptiveandaresetasbinaryandequiprobable.
4.2. Re nement bits compression
Re nementbitsmaybecompressedbecausethetypicalsubbandcoeÆcienthistogramofeachbit-planeinterval
isunbalanced towardslowervaluesandsoitismoreprobablethatacoeÆcientliesin theinferiorhalf-interval
ratherthaninthesuperiorone. 5
Thisunbalanceismorepronouncedforthe rstre nementbitsanddecreases
as the re nement proceeds. For this reason we create two sub-contexts for re nement bits compression: a
context for the rst re nementbit ofeach coeÆcientsand another onefor theother re nement bits. In this
waythere nementbitsareentropycompressedbyabout8%,inabit-raterangefrom 0.25to 1.0bpp.
4.3. Sign bits compression
Asstatedin 6
signbitsmaybecompressedaswell,becauseadjacentwaveletcoeÆcientsinmixedlowpass/highpass
subbands(e.g. LHandHLin2D)exhibitsubstantialstatisticaldependencies. Infact,alongthelow-pass
lter-ingdirection,neighboringcoeÆcientsexhibit,withahighprobability,thesamesign;whilealongthehigh-pass
lteringdirectiontheyoftenhaveoppositesigns. Forexploitingthisstatisticalevidencewemakeuseofthetwo
functions l(x) and h(x), that summarize the information aboutthe signi cantly-markedadjacentcoeÆcients
of the coeÆcientx , respectivelytowards the high-pass and the low-pass directions. These functions assume
note that only the signof coeÆcients in mixed lowpass/highpass subbandsare entropycoded. Forthe other
signbitsweuseanadditionalnon-adaptiveandequiprobablecontext. Weexperimentedthatsignbitsmaybe
compressedofabout10%for2Dimageswhilein the3Dcasethecodinggainmayevenreach40%.
4.4. Adaptivity of the model
Because of thenon-stationarity ofthe EMDC sourceweusean adaptivemodelto obtain better compression
performance. Byreducing the numberof bits used to storesymbolfrequencies (that we callfrequency-bits),
we can emphasize the adaptivity of the model making the arithmetic coding more reactive with respect to
uctuationsinthewaveletcoeÆcientsstatistics. However,wemustuseasuÆcientnumberoffrequency-bitsin
ordertoobtainanenoughaccurateapproximationoftheactualfrequenciesofthesymbols. 13
Thisisespecially
truefor contexts wherethe probabilitiesof thetwosymbolsareverydi erent (in ourcasethe morphological
dilation contextpresentsthis feature). Sowehad to slightly modify thearithmetic coder 13
in order to make
possibletheuseofadi erentnumberoffrequency-bitsfordi erentcontexts. Todothis,itissuÆcienttoinsert
afrequency-bits eld in the context record,and thenuse, in each context, theproperfrequency-bitsnumber.
Wetested various combinationof frequency-bitsobtainingbest resultsusing 10 bits in 2Dand 15 bits in 3D
fortheadditionalmorphologicaldilationcontext, and6bitsforalltheothercontextsbothin2Dandin 3D.
5. EXPERIMENTAL RESULTS
5.1. 2D Performance
Inthecaseof2DcodingwetestedtheEMDCalgorithmontheLena,BarbaraandGoldhill images. Weuseda
ve-levelwaveletdecompositionwith9/7-tap lters. 14
WecomparedourcoderwithrespecttotheSPIHT 2 and EBCOT 6 embedded coders y
andthemorphologicalcoderSLCAA. 8
As shown inTab.1theEMDC algorithm
obtainsthebest performance in almostallcases. InFig.4 theRD performanceofouralgorithm compared to
SPIHTand EBCOTonthe Goldhillimage isshown. InFig.5somepictorial coding resultsareshown forthe
Lenaimageatvariousbit-rates.
5.2. 3D Performance
For3Dapplicationswetested theEMDCalgorithmonthe256x256x128medicaltestvolumeCTSKULLand
compared thecodingresultswith respect toothers state-of-artcoders. 3{5
Weused a3Dseparable four-level
decompositionwavelettransformwithdi erentcombinationofbiorthogonal lterswhichhavebeenselectedin
eachspatialdirectionbetweenthe9/7-tapandthe10/18-tap 15
ones. Ourresultsaresensiblysuperiortothose
shown byother coders both in termsofmean PSNRonthe wholevolume, worst slicePSNRand in termsof
mean slicebased PSNR uctuations 16
among near slices. The resultsare summarized in Tab.2. With mean
PSNR uctuation we refer to the mean value of the maximum slice based PSNR di erence calculated for a
sliding windowof10slices. InFig.6thePSNRcalculatedoneachslicealongthe zdirectionis shownfor two
di erent target rates: 0.1 and 0.5 bpp. In Fig.7 some pictorial coding results are shown for the worst slice
(nr.72)oftheCTSKULLvolumetricdata-set,atvariousbit-rates.
6.CONCLUSIONS
Inthis paperanewembeddedbit-plane coder,called Embedded MorphologicalDilationCoder(EMDC),has
beenproposed. Thisalgorithmisbasedonamorphologicaldilationofsigni cantcoeÆcientswhichexploits
inter-bandandintra-bandstatisticaldependenciesamongsigni cantcoeÆcientsandtheirtendencytoformclusters.
Somefeaturesoftheproposedmorphologicalapproach,whichallowtoimprovethecodingperformance,canbe
highlighted: thesortingpassbit-streamof each bit-plane hasbeen structured in orderto obtainagood
rate-distortioncharacteristicandanembeddedbit-stream;moreover,thewaveletcoeÆcientshavebeensubdividedin
tworegions withverydi erentsigni cantcoeÆcientsfrequencies,in orderto obtainahighlyeÆcient
context-based arithmetic coding. The EMDC algorithm has been tested both for 2D and 3D applications showing
performancethatareoftensensiblysuperiorwithrespecttothestate-of-the-artembeddedcoders.
y
Image Rate(b/p) SPIHT 2 SLCCA 8 EBCOT 6 2D-EMDC 0.25 34.11 34.28 34.16 34.50 Lena 0.50 37.21 37.35 37.29 37.57 1.00 40.41 40.47 40.48 40.50 0.25 27.58 28.18 28.40 28.42 Barbara 0.50 31.39 31.89 32.29 32.16 1.00 36.41 36.69 37.11 37.35 0.25 30.56 30.60 30.59 30.75 Goldhill 0.50 33.13 33.26 33.25 33.45 1.00 36.55 36.66 36.59 36.97
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
30
31
32
33
34
35
36
37
Bit rate (bpp)
PSNR (dB)
SPIHT
EBCOT
EMDC
Figure4: 2DcodingresultsontheGoldhillimage.
Figure 5. Coding resultsfor Lena. (a)Originalimage. (b)Compressedimage at 0.5 bpp. (c)Compressed image at
Rate EZW 3 3DSPIHT 4 I3DSPIHT 5 3D-EMDC 3D-EMDC (b/p) (9/7+10/18) (10/18taps) '32:5 33.99 34.07 35.38 35.38 0.1 29.8 29.2 30.98 32.31 32.62 '2:5 '6:0 2.28 2.25 2.04 '42 42.89 43.67 44.77 44.56 0.5 39.5 37.5 41.64 42.88 42.87 '2:5 '4:0 2.39 2.09 1.99
0
20
40
60
80
100
120
32
34
36
38
40
42
44
46
48
50
Slice number
PSNR (dB)
0.5 bpp
0.1 bpp
Slice 72
Slice 72
Figure6.CodingresultsforCTSKULLwith10/18 lters: slicebasedPSNRfor0.5and0.1bppalongthezdirection.
Figure 7. Codingresultsfor theCTSKULLvolume. (a)Originalslice n.72. (b)Slicen.72ofthecompressedvolume
1. J.M.Shapiro,\EmbeddedimagecodingusingzerotreesofwaveletcoeÆcients,"IEEETrans.onAcoustics,
Speech andSignalProcessing41,pp.3445{3462,Dec.1993.
2. A.SaidandW.Pearlman,\Anew,fast,andeÆcientimagecodecbasedonsetpartitioninginhierarchical
trees,"IEEE Trans.CircuitsandSystemsfor VideoTechnology6,pp.243{250,June1996.
3. A. Bilgin, G. Zweig, and M. W. Marcellin, \Three-dimensional image compression using integer wavelet
transforms," Applied Optics: Information Processing, Special Issue on Information Theory in
Optoelec-tronic Systems39,pp.1799{1814,Apr.2000.
4. Z.Xiong,X. Wu,D. Yun,andW. Pearlman,\Progressivecodingofmedicalvolumetricdatausing
three-dimensionalintegerwaveletpacket transform,"inSPIE,3653,pp.327{335,1999.
5. A.Signoroni,M.Arrigoni,F.Lazzaroni,andR.Leonardi,\ImprovingSPIHT-basedcompressionof
volu-metricmedicaldata,"inPCS 2001,pp.187{190,Apr.2001.
6. D. Taubman,\Highperformance scalableimage compressionwithEBCOT,"Trans.onImage Processing
9,pp.1158{1170,July2000.
7. S.Servetto,K.Ramchandran,andM.Orchard,\Imagecodingbasedonamorphologicalrepresentationof
waveletdata,"IEEETrans.on SignalProcessing8,pp.1161{1174,Sept.1999.
8. B. Chai, J. Vass, and X. Zhuang, \Signi cance-linked connected component analysis for wavelet image
coding,"IEEE Trans.onImage Processing8,pp.774{784,June1999.
9. K. Ramchandran and M. Orchard, \An investigation of wavelet-based image-coding using an
entropy-constrainedquantizationframework,"IEEE Trans.onSignalProcessing46,pp.342{353,Febr.1998.
10. X.Liand X.Zhuang,\The decayand correlationpropertiesin wavelet transform,"tech.rep., University
ofMissouri-Columbia,March 1997.
11. F.Henryand P.Duhamel,\Rate-distorsioneÆciency ofzerotreecoders,"inICIP99, p. 25PP5,1999.
12. P.Maragosand R.Schafer, \Morphologicalsystemsformultidimensionalsignalprocessing,"Proc. IEEE
78,pp.690{710,1990.
13. A. Mo at, R. M. Neal, and I. H. Witten, \Arithmetic coding revisited," ACM Trans. on Information
Systems16,pp.256{294,July1998.
14. M.Antonini,M.Barlaud,P.Mathieu,andI.Daubechies, \Imagecoding usingwavelettransform,"IEEE
Trans.onImage Processing1,pp.205{220,Apr.1992.
15. M.Tsai,J.Villasenor,andF.Chen,\Stack-runimage-coding,"IEEE Trans.onCircuitsandSystemsfor
VideoTech.6,pp.519{521,Oct.1996.
16. A.SignoroniandR.Leonardi,\ModelingandreductionoffPSNRg uctuationsinf3Dgwaveletcoding,"
