erebralarteriography,singlephoton emission tomography),its relativelylow ost and itslarge availabilityhave gained to this pro edure the onditionof "golden standard&#34

Wavelet Pa ket De omposition

Federi oSantoni 1

and Fran es oMarrosu 2

1

CRS4CenterforAdvan edStudies,Resear handDevelopmentinSardinia

2

CagliariUniversityHospital

Abstra t. Thispaperproposesamethodologyfor extra tingfeaturesfromEEG

in suspe ted brain death onditions. Those signals are usually ara terized by a

low SNR and in su h situations distortions introdu ed by skull/ele trode/ able

interfa ebe omeveryrelevant.Aftera alibrationpro edure,theanalysisofEEG

signalswasperformedwithaWaveletPa ketDe ompositionlter,wherethemain

omponent of noise are removedwith soft thresholding strategy. We propose an

estimateof error probability leading to the hoi eof wavelet basis andthreshold

parameters.Asresult,inabsen eofbraina tivity,theoutputofthislterprodu es

really atsignals.Howeverthepresen eofsomea tivity anbeexaminatedinWP

time-frequen y domainrevealing distin tions between real brain a tivity, narrow

bandnoiseandartifa ts.

1 Introdu tion

Theele troen ephalographi (EEG)re ordingisextensivelyusedinIntensive

CareUnits(ICU)asareliablemeasureofele tri albraina tivity.Moreover,

the interpretation of EEG re ords aimed at diagnosis of the ondition of

"brain death", better expressed as ele tro lini al silen e (ES), is a ru ial

stepinmodernmedi ineandrepresentsthefundamentalpre-requisitein lin-

i alsettingsorientedfortransplants[1℄.AlthoughEEGanalysisrepresentsa

diagnosti toolamongmanyothers(e.g. erebralarteriography,singlephoton

emission tomography),its relativelylow ost and itslarge availabilityhave

gained to this pro edure the onditionof "golden standard" in monitoring

omatose patients. However,digital EEG monitoringin ICU is, nowadays,

neither popular nor widespread. Among the reasons for this resistan e in

penetratingthe ommonICUpra ti e,themostimportantisthatEEGmon-

itoring hasyet to be provedas aneasy andreliabletool.Theoreti ally, the

analysis ofadigitalsignalseems"primafa ie"arelevantvantageoverana-

logue re ordings.However,in aseofES,sin epreviouspaperEEG yielded

resultsthatvisually orrelatefaithfullywith lini alsigns(thefatal atline),

youshould expe tthatthe omputerizedEEG(CEEG)performsasuperior

task in this spe i diagnosis pro edure. Unfortunately, the noising ba k-

groundofanICUgeneratesinsidiousartifa tsandtherequiredampli ation

Thedensitydistributionofa alibratedESsignalisalmostgaussian[2℄.From

this premise, we an state the problem as one of estimating an unknown

deterministi signal after observing a pro ess sampled over an interval of

lengthN. Wehen eforthassumethat theobservedsamplesare thoseof an

underlyingunknownsignalandofwhitenoise,where

x[m℄=s[m℄+n[m℄; (1)

form=1;2;:::;N andnN(0; 2

).

Implementinganestimatorinanorthogonalbasisisintuitivelyappealing

on a ountof the distribution of the noiseenergy in su h a basis. Wavelet

bases are known to on entratethe energy of pie ewisesmooth signalsinto

a few high-energy oeÆ ients [3℄. If the energy is on entrated into a few

high-amplitude oeÆ ients, su h a representation an provide an a urate

estimateofs[m℄.Theadvantageofexpressinginanorthogonalwaveletbasis

istwo-fold:

a) if the ontaminating noise samples are independent and identi ally

distributed (i.i.d.) Gaussian,so are the oeÆ ients, and theirstatisti al in-

dependen eispreserved.

b)intrinsi propertiesofthesignalarepreservedin awaveletbasis.

We rst dis uss a method for estimating the mean-square error asso i-

ated with thresholding wavelet oeÆ ients at a given level. Given a signal

in somebasisrepresentation, wewillthreshold the oeÆ ientsand estimate

theresultingerror,andthiserrorwillthenbeusedin thesear hforthebest

basisfamily.Su intlywereporttheproblemasanalysedin[4℄.Moreoverwe

presenta new derivation used to set the error probability of our dete tion

system.

2.1 Risk ofa Wavelet-based estimator

In thisse tion, wepresent amean-square errorestimatorexstensivelyused

inliteratureexpe iallyforwaveletde-noising[6℄.Themean-squareerror,or

moreformallytheriskrelatedtore onstru tionofave torswithathreshold

T,isgivenby

R (s;T)=Efks

^

sk 2

g (2)

where^sistherepresentationofthere onstru tedve tor.Asignalre onstru -

tionisobtainedbyapplyingsomefun tion ofas alarT ("thresholding")to

asetof oeÆ ientsofsinagivenWaveletbasisandthenapplyinganinverse

transformation.Thisisthegeneralpro edureweusethroughoutthepaper.

Thoughmanythresholdingfun tionsareappliable,forthesakeofsimpli -

ity,inthisse tionweanalysestri tlytherisklimitedtothehardthresholding

rule.Softthresholdingrulewillbepresentedinse tion3.2andforotherrules

outthefollowingse tions)wedes ribethehardthresholdingruleas

T (y

x )=

8

<

: y

x;

ifjy

x j>T

0; ifjy

x jT:

(3)

foranys alary

x

whereT isthethreshold.Usuallythemeasureofloss aused

byre overingsignal oeÆ ients,derivesfromaquadrati distan ewhi hde-

pendsonT andonsignal oeÆ ientsy

s :

Lf

T (y

x );y

s

;Tg=(y

s

T (y

x ))

2

: (4)

Consideringthere onstru tedsignal^sasobtainedfrom therule(4)applied

to thewavelet oeÆ ients in aparti ular orthogonalbasisB =fW

x

i g and

with W

x

expressing theve torof proje tion (innerprodu t)of xonto the

wavelet basisW

x

i

=hx;W

x

i

i, themean valueofthe lossis theestimation

error(2)

EfL(

T (W

x

);s;T)g=Efks W

x

T (W

x )k

2

g=R (s;T); (5)

where for ompa tnessW

x

representsthematrixofbasisfun tions.Repre-

sentingthesignals=W

x W

s

withthewaveletbasis(W

s

istheve torwith

omponentshs ;W

x

i

i),risk anbeexpressedintermsofthebasis oeÆ ients

too,or

R (s;T)=EfkW

x W

s W

x

T (W

x )k

2

g= N

X

i=1 E



jW

si

T (W

xi )j

2

:

(6)

Tobetterunderstandthestru tureofR ,werewritethefun tion

T (W

xi )=

W

xi I

jW

x

i j>T

where I istheindi atorfun tion.Asbrie yalludedto earlier,

rememberthatW

xi

=W

si +W

ni andW

ni

N(0; 2

).

Afterfew al ulationsand onsideringW 2

s

i I

jW

x

i j<T

+W 2

s

i I

jW

x

i jT

=W 2

s

i

weobtainfrom(6)

R (s;T)= N

X

i=1 E

n

W 2

si I

jW

x

i j<T

+W 2

ni I

jW

x

i jT

o

: (7)

This equation express an intuitive on ept: the ontributeto thetotal risk

isdued tothesignal oeÆ ientswhenthenoisy oeÆ ientW

xi

isunder the

thresholdandtothepurenoiseW 2

n

i

whenW

xi

isoverthethreshold.

Wavelet Pa ket De omposition and Re tangular approximation.

TheWaveletPa kedDe omposition(WPD)diersfromWaveletDe omposi-

tion(WD)sin eitde omposesapproximationanddetail oeÆ ients,building

frequen y(s ale) plan in amore omplete way than WDand to monitorize

with thesamedetaillevelallfrequen ybands. Thisfeature is reallyimpor-

tant forbothdete tion and analysispurposes,as dis ussed in next se tion.

Consideralevelj ofWPDde ompositionofthesignals.Thislevel ontains

N oeÆ ients distributed into 2 j

basis and, as previouslyaÆrmed for WD,

onlyfew oeÆ ientsaresigni antlygreaterthanzero.Obviouslythesignal

energyis onservedin theWPdomainso,E

s

= P

N

i=0 js

i j

2

= P

N

i=0 jW

s

i j

2

.

Now we introdu e an approximation assuming that the distribution of

oeÆ ientsW

s

i

is onstantfor asubsetof indexesN

fi:W

s

i

6=0g and

n

= ard(N

)N

W

si

= 8

>

<

>

:

 q

Es

n

;

ifi2N

0; ifi62N

:

(8)

Inotherwords,weapproximatewithare tangularfun tion thedistribution

of WP oeÆ ients in a way to maintain the signal energy. Obviously this

fun tionworkswellwhentherearefew oeÆ ientstoapproximateintheWP

domain.Infollowingse tionsweassumealmostoneWP oeÆ ientofsignal

>Tandwein ludetheenergylossafterthresholdingwithaneÆ ien yfa tor

k= Es

E

s true

<1.Thisfa toris stri tlyrelatedwith n

and thoseparameters

denethe ompressioneÆ en yofaWPDwithagivenbasis.

3 Dete tion and analysis

Theaimofthispaperistodemonstratetheee tivereliabilityofadete tion

andanalysissystemofEEGsignalsofpatientsin riti al onditionbasedon

WPD. Inthis opti s wedes ribethequalitativebehaviorofthe risk.Inthe

nextparagraphweshowtherelationbetweenerrorprobabilityand ompres-

sionandthereforesuggestwhi hkindofwaveletbasisuseforde omposition.

Ifdete tionshowssomeeviden eoflife,it'simportanttodenesomeanalysis

pro edure to re overand re onstru t this embedded and unknowna tivity.

We used the algorithm implemented by Donoho and Johnstone based on

theneedingofsomevisualfeature (smoothness)ofthere onstru tedsignal.

Theirworksdemonstratedtheoptimality,under ertain ondition,oftheuse

ofsoft-thresholdingrulewhenminimizingtheriskR (s;T)inaminimaxsense

[6℄.Inthispaper,sin ethenoise onsiderediszero-mean,wedene

SNR=10log



var(s )

 2



(9)

Toevaluate theerror probability of asystembasedon hardor soft thresh-

olding,we onsidertwosituations.Intherst ase,thepatientisalivesohis

EEGsignal an bemodeled withtheadditivemodel (1).Theprobabilityof

anulldete tion(i.e.toobtainave torofzeroes0) is

P(e) +

=P(^s=0)=P(W

x

T (W

x

)=0)= N

Y

i=0 P(jW

xi

j<T); (10)

sin eweare onsidering orthogonalbasesandun orrelatednoise.Usingthe

sameapproximationdes ribedin (8),theequation(10) an berewrittenas

P(e) +

= Y

i2N P jW

ni +

r

E

s

n

j<T

!

Y

i62N P(jW

ni j<T)

=P jW

n +

r

E

s

n

j<T

!

n

P(jW

n j<T)

N n

=p n

Es :p

N n

n

(11)

Inthese ond ase,we onsideranESsignal(s=0)so it anbe onsidered

as pure noise (W

xi

= W

ni

). The probability of dete t something dierent

fromnoiseis

P(e) =P(^s6=0)=1 N

Y

i=0 P(jW

n

i

j<T) (12)

=1 P(jW

n j<T)

N

=1 p N

n

Thewholeerrorprobabilityofoursystem an bewritten as

P(e)=P(ejs6=0)+P(ejs=0)=P(e) +

+P(e) (13)

=1 p N

n



1



p

Es

p

n



n



where P(e) +

represents thein iden e of false negativesand P(e) thein i-

den eoffalsepositives.

Straightforward onsiderations on (13) demonstrate the need of a high

ompression(n

N)tokeeplowtheerrorprobability.Butthisisthe ase

ourapproximationworks better. Ourpurpose is to obtainsomereasonable

values of loss(k) and ompression (n

) for a lini al a eptable error. We

plot theequation (13)in fun tion of n

N

%, onsidering k= 1

2

andfor some

SNR values(g.1). Forlowvaluesof ompressionthe in iden eof P(e) is

predominantwhile, forveryhighvalueof ompression( 97%), the ontri-

bution of false negativesis the mostsigni ant and limitsthe lower bound

oftheerror.

For example,to obtainaP(e)<10 4

with SNR=0,weneed ofabasis

with a ompression of n

N

 97% with a loss of 50%. We made a lot of

testswithEEGsignalsandwefoundthat Coi et4family[10℄satisesthese

3.2 Analysis

The SURE algorithm is a method presentedby Donoho and Johnstone [5℄

forthesoft-thresholdingpro edure denedby

(y

x

)=sign(y

x )

8

<

: jy

x j T

; ifjy

x

j T >0

0; ifjy

x

j T 0

(14)

Besides the benets of this strategy, largely des ribed in [6℄, the weak

dierentiabilityofthisthresholdingfun tion makesstraightforwardappli a-

bletheSteinmethod[9℄toestimatetheriskR (s;T)inanunbiasedfashion.

Theoptimal thresholdT will be hosento minimizethis approximationfor

ea hde omposition level.This "adaptative" method isreally quasi-optimal

in the"dense" situation, i.e. when theenergy is distributed overmany o-

eÆ ients, but it has a serious drawba k in situations of extreme sparsity

or, in other words, when the signal ompression is high. Donoho proposed

a pre-testing pro edure to In this ase, exploiting that, in probability, if

Wn  N(0; 2

);kWnk

l 1

n

 T

f

=  p

2log(n) [7℄, the threshold is set to

T

f

.Asusual,noisevarian eisapproximatedwith^ 2

=



MAD(Wx)

0:6745



2

.

InFig.2weapply WPsoftthresholdingonaEEGsignalmeasuredfrom

apatientin BrainSilen e ondition (Fig.2 ,2d) ompared to theanalogue

appli ationonasignalderivingfromanormalpatient(Fig.2a,2b).

4 Future work

Inthis paperaprepro essingsystemfor de-noisingand omputerizedanal-

ysis of EEGsignals in riti al onditionshasbeenpresented.The basi al-

beendedi ated to theorthogonalbasis. Thiskind ofapproa hwas rst de-

veloped by Donohoand Johnstone with their SURE algorithm based on a

soft-thresholding strategy[5℄. Starting from this miliary stone, we derivea

really simplemethods to relatetherisk, and onsequenltythe errorproba-

bility of adete tion systembasedupon these on epts, to the ompression

propertiesoftheunderlying setofbases hosenfordenoising.Weproje tto

apply thisalgorithmto longEEGa quistion(setting asample frequen yof

128Hzandana quisition of12h,wehaveaset of5:5millionofsamples

forea hEEGderivation). Theaimisto buildanautomati pre-analyzerto

help theexpert toonlyexaminethereallyinterestingparts.

Referen es

1. J.Doyle(1995)Thediagnosisofbraindeath:a he klistapproa h.TheOnline

JournalofAnesthesiology,vol.2,(http://www.gasnet.org/esia /19 95 /mar h/).

2. F.Santoni(2001) Calibrationalgorithm for EEGA quisition Systems.CRS4

InternalReport02/26

3. I. Daube hies (1988) Orthonormal bases of ompa tly supported wavelets.

Com.PureandAppl.Math.,vol.XLI,pp.909-996.

4. H.Krim, D.Tu ker, S. Mallat and D. Donoho (1999) On denoising and best

signalrepresentation.IEEETrans.Inform.Theory,vol.45,no.7,pp.2225-2238

5. D.Donoho, I.Johnstone(1995) Adaptingto unknownsmoothnessvia wavelet

shrinkage. Journal of the Ameri an Statisti al Asso iation, vol. 90, pp.1200-

1224.

6. D.Donoho(1995)De-noisingbysoft-thresholding.IEEETrans.Inform.Theory,

vol.41, pp.613-627.

7. S. I. Resni k (1987) Extreme values, regular variation and point pro esses.

Appl.Probab.Series,NewYork:Springer-Verlag.

8. H.Y.Gao(1998)WaveletShrinkagedenoisingUsingtheNon-NegativeGarrote.

JournalofComputationalandGraphi alStatisti s,vol.7,no.4,pp.469-488.

9. C.M.Stein(1981)Estimation ofthemeanofamultivariatenormaldistribu-

tion.Ann.Statist.,vol. 9,no.6,pp.1135-1151.

10. Coifman, R.R., Y. Meyer, M.V. Wi kerhauser (1992) Wavelet analysis and

signal pro essing. Waveletsand their appli ations,M.B. Ruskaietal. (Eds.),