Transcription

MIN-FakultätFachbereich InformatikArbeitsbereich SAV/BV aminSeppkeProf.SiegfriedSIehl

importantfor: Imagearchivese.glargesatelliteimages Imagetransmissione.g.overtheinternet .14University of Hamburg, Dept. InformaticsTransmission,storage,archiving2

ompressionLosslesscompression: sseddata. Examples:– Filecompression,e.g.ZIP,GZetc.– Imageformats:TIFFandPNGLossycompression: ecompresseddata. Examples:– JPEGimagefiles– DVDsandBlu- ‐Rays– MP3audiofiles06.11.14University of Hamburg, Dept. Informatics3

format:greyvalue1repe88on1greyvalue2repe88on2 d:row#column#column#column#column# run1beginrun1endrun2beginrun2end0123456789 10 11 12 13 14 15012306.11.14University of Hamburg, Dept. 01214)4

encodingofindividualpixelswithGgreylevelseach:r b - Hb !"log 2 G # numberofbitsusedforeachpixelG 11H entropyofpixelsourceH P(g) log 2g 0P(g) 6.11.14University of Hamburg, Dept. Informatics5

Huffmancodingschemeprovidesavariable- ‐lengthcodewithminimalaveragecode- University of Hamburg, Dept. Informatics6

ty of Hamburg, Dept. InformaticsEntropy:H 2.185Meancodewordlength:2.27

andomvariableswitha mulIvariatedistribuIonp ( x ) p ( x1 , x2 , , x N iables:E !" xi x j # cij!%% E !" x x T # %%%"Covarianceoftwovariables:E "#(xi µi )(x j µ j ) % vijc11c12c21 c22c31 c32 c13 #&c23 &&c33 && "&!!!!&E "#( x µ )( x µ )T % &&&#Correla'onmatrixwith µ k mean of xkv11v12v21 v22v31v32""v13 ! 'v23 ! ''v33 ! '" # dnotbestaIsIcallyindependent:E !" xi x j # 0 ( ) ( ) ( )p xi x j p xi p x pliesstaIsIcalindependence.06.11.14University of Hamburg, Dept. Informatics8

IP1–Lecture8:Imagecompression1Karhunen- PrincipalComponentsAnalysis) blesxbyalineartransformaIon. y A( x µ ) ! T E !" y y T # A E #( x µ ) ( x µ ) & AT AVAT D"% .AisthematrixofeigenvectorsofV, D isthematrixofcorrespondingeigenvalues. !! !ReconstrucIonofxfromyusing:x AT y µ xNote:Ifisviewedasapointinn- coordinate.06.11.14University of Hamburg, Dept. Informatics9

nstruk8onmitderKarhunen- derReihenfolgesorIertsind:λ1 λ2 λ N ! λ 0 0 EigenvektorenaundEigenwerteλsinddefiniertdurch # 1&Va λaundkönnenbes8mmtwerden,indemman# 0 λ0 &2D det (V λI) 0löst.#&# 0 0 λ3 &ZumBes8mmenderEigenwertevonreellen#& %symmetrischenMatrizengibtesspezielleVerfahren." xkannineinenK- ‐dimensionalenVektoryK, K N ondierendzudenKgrößtenEigenwerten: y K AK x µ äsentaIonmitKDimensionen: Tx! AK y K µ ngverwendetwerden.(06.11.14)University of Hamburg, Dept. Informatics10

nstruc8onusingtheKarhunen- ing:λ1 λ2 λ N ! λ 0 0 EigenvectorsaandEigenvaluesλaredefinedby 1#&Va λaandmybees8matedbysolving:# 0 λ&0 2det (V λI) 0.&D ## 0 0 λ3 &Thereexistfastsolu8onmethodsfortheEigevaluesof#& %realsymmetricmatrices." xmaybetransformaInintoaK- ‐dimensionalvectoryK, withK N Eigenvalues: y K AK x µ uareerror(MSE)ofarepresentaIonwitKdimensions: Tx! AK y K µ 4)University of Hamburg, Dept. Informatics11

um- ‐lossDimensionReduc8onUsingtheKarhunen- ‐Loèvetransform,datacompressionisachievedby changing(rotaIng)thecoordinatesystem atesystemExample:x2y2 y1x2x1x1y2y106.11.14University of Hamburg, Dept. Informatics y112

rKarhunen- ‐LoèveCompression"Given:N 32 0.866 0.5 % '!TV 0.86620 'x ( x1 x2 x3 )! 0.502 '&m 0#Eigenvaluesandeigenvectors" 0.70700.707 %'det(V λ I ) 0 λ 3, λ 2, λ 1 V 0.6120.50.621 ' 123 0.354 0.866 0.354 '#&CompressionintoK 2dimensions!! " 0.707 0.612 0.354 % !Notethediscrepanciesbetweenthey2 A2 x 'x0.5 0.866 &originalandtheapproximated# 0values:ReconstrucIonfromcompressedvalues# 0.707&0%(!!T !x! A 2 y % 0.6120.5 ( y% 0.354 0.866 ( '06.11.14x1 0,5 x1 - 0,43 x2 - 0,25 x3x2 -0,085 x1 - 0,625 x2 0,39 x3x3 0,273 x1 0,39 x2 0,25 x3University of Hamburg, Dept. Informatics13

&durch& &&&&&und&können&bes8mmt&werden,&indem&man&& &löst. Zum&Bes8mmen&der&Eigenwerte&von&reellen& symmetrischen&Matrizen&gibt&es&spezielle&