Presentation of Lossy compression

Explain lossy image compression technique

2. Produced by
Omar Ghazi Abbood Khukre
Master Student in Department of Information
Technology, Institute of Graduate Studies and Research,
Alexandria University, Egypt
.

3. Contents
Introduction
Image Compression Definition
Image Compression Types
Wavelet Transforms
Problem Statement
Objective
Methodology
Experiments and Results Analysis
Conclusion
Future work

4. INTRODUCTION
ImageCompression:ItistheArt&Scienceofreducingtheamountof
datarequiredtorepresentanimage.
Itisthemostusefulandcommerciallysuccessfultechnologiesinthe
fieldofDigitalImageProcessing.
Thenumberofimagescompressedanddecompresseddailyis
innumerable.
Webpageimages&High-resolutiondigitalcameraphotosalsoarealso
compressedtosavestoragespace&reducetransmissiontime.
TheresearchershavefacedinthefieldofImagecompressionsome
difficultiesespeciallyingetthebestaccuracyoftheimagewithahigh
compressionratio.
Thisresearchaimsanimprovingtheimagecompressionprocesstothe
maximumextent.

5. Image Compression Definition
Imagecompressionisminimizingthesizeinbytes
ofagraphicsfilewithoutdegradingthequalityof
theimagetoanunacceptablelevel.
Thereductioninfilesizeallowsmoreimages
tobestoredinagivenamountofdiskormemory
space.Italsoreducesthetimerequiredfor
imagestobesentovertheInternetordownloaded
fromWebpages.

6. LossyCompressionTechniques
Ininformationtechnology,lossycompressionorirreversible
compressionistheclassofdataencodingmethodsthatuses
inexactapproximationsandpartialdatadiscardingtorepresent
thecontent.Thesetechniquesareusedtoreducedatasizefor
storage,handling,andtransmittingcontent.Theamountofdata
reductionpossibleusinglossycompressionisoftenmuchhigher
thanthroughlosslesstechniques.
LosslessCompressionTechniques
Losslesscompressionisaclassofdatacompression
algorithmsthatallowstheoriginaldatatobeperfectly
reconstructedfromthecompresseddata.Bycontrast,lossy
compressionpermitsreconstructiononlyofanapproximationof
theoriginaldata,thoughthisusuallyimprovescompressionrates
(andthereforereducesfilesizes)
Image Compression Types

7. Lossy Compression Techniques
LossyCompressionVectorquantizationbyLinde-Buzo-Gray
Lossycompressiontechniqueprovideshighercompressionratio
thanlosslesscompression.
Alossycompressionscheme,showninFigure,mayexaminethe
colordataforarangeofpixels,andidentifysubtlevariationsin
pixelcolorvaluesthataresominutethatthehumaneye/brainis
unabletodistinguishthedifferencebetweenthem.
Vectorquantization(VQ)isaclassicalquantizationtechnique
fromsignalprocessingthatallowsthemodelingofprobability
densityfunctionsbythedistributionofprototypevectors.Itwas
originallyusedfordatacompression.Itworksbydividingalarge
setofpoints(vectors)intogroupshavingapproximatelythesame
numberofpointsclosesttothem.

8. Linde,Buzo,andGray(LBG)proposedaVQdesign
algorithmbasedonatrainingsequence.Theuseofatraining
sequencebypassestheneedformulti-dimensionalintegration.
TheLBGalgorithmAlgorithmTheyusedamappingfunction
topartitiontrainingvectorsintoclustersandbeisofiterative
typeandineachiterationalargesetofvectors,generally
referredtoastrainingset,isneededtobeprocessed.
Lossy Compression Techniques (cont.)

9. Wavelet Transforms
Representanimageasasumofwaveletfunctions(wavelets)
withdifferentlocationsandscales.Anydecompositionofan
imageintowaveletsinvolvesapairofwaveforms:oneto
representthehighfrequenciescorrespondingtothedetailed
partsofanimageandoneforthelowfrequenciesorsmooth
partsofanimage.

10. Discrete Wavelet Transform
TheDiscreteWaveletTransform(DWT)ofimagesignalsproduces
anonredundantimagerepresentation,whichprovidesbetter
spatialandspectrallocalizationofimageformation,compared
withothermultiscalerepresentationssuchasGaussianand
Laplacianpyramid.Recently,DiscreteWaveletTransformhas
attractedmoreandmoreinterestinimagefusion.Animagecan
bedecomposedintoasequenceofdifferentspatialresolution
imagesusingDWT.Incaseofa2Dimage,anNleveldecomposition
canbeperformedresultingin3N+1differentfrequencybandsand
itisshowninfigure.
Wavelet Transforms (cont.)

11. Wavelet Transforms (cont.)
2D -Discrete wavelet transform

12. Lifting Wavelet Transform
Theliftingschemeisatechniqueforbothdesigningwaveletsan
dperformingthediscretewavelettransform.Actuallyitisworth
whiletomergethesestepsanddesignthewaveletfilterswhilepe
rformingthewavelettransform.Thisisthencalledthesecondg
enerationwavelettransform.
Wavelet Transforms (cont.)
Diagram lifting wavelet scheme transform

13. Stationary Wavelet Transform
Thestationarywavelettransform(SWT)isawavelettransform
algorithmdesignedtoovercomethelackoftranslationinvariance
oftheDiscreteWaveletTransform(DWT).Translationinvariance
isachievedbyremovingthedownsamplersandupsamplersin
theDiscreteWaveletTransform(DWT)andupsamplingthefilter
coefficientsbyafactorofinthelevelofthealgorithm.TheSWT
isaninherentlyredundantschemeastheoutputofeachlevelof
SWTcontainsthesamenumberofsamplesastheinput.
Wavelet Transforms (cont.)

14. TheStationaryWaveletTransform(SWT)issimilartotheDWT
exceptthesignalisneversub-sampledandinsteadthefiltersare
upsampledateachlevelofdecomposition.Thefollowingblock
diagramdepictsthedigitalimplementationofSWTasshownin
figure.
Wavelet Transforms (cont.)

15. Problem Statement
•Thelargeincreaseinthedataleadtodelaysinaccesstothe
informationrequiredandthisleadstoadelayinthetime.Large
dataleadtodataunitsandstorageisfullthisleadstotheneed
tobuyabiggerspaceforstorageandlosingmoney.Largedata
leadtogiveinaccurateresultsforthesimilarityofdataandthis
leadstogettinginaccurateinformation.
•Alsotoshowthedifferencebetweenthetypesoftransforms
StationaryWaveletTransform,DiscreteWaveletTransform,
andLiftingWaveletTransformbecausetheyareverysimilar
atonelevelsoweusedthreelevels.

16. Research Objective
Inlossycompression,thecompressionratiois
unaccepted.Theproposedsystemsuggestsanimage
compressionmethodoflossyimagecompression
throughthethreetypesoftransformationssuchas
stationarywavelettransform,discretewavelet
transform,andliftingwavelettransformandthe
comparisonbetweenthethreetypesandtheuseof
vectorquantization(VQ)toimprovetheimage
compressionprocess.

17. Methodology
TheproposedlossycompressionapproachappliedSWT
andVQtechniquesinordertocompressedinputimages
infourphases;namelypreprocessing,image
transformation,zigzagscan,andlossy/lossless
compression.Infigureshowsthemainstepsofthe
systemthatfollowstheschemaindependentandimage
compressiontechniques.Wediscusshowamatrix
arrangementgivesusthebestcompressionratioand
lesslossofthecharacteristicsoftheimagethrough
awavelettransformwithlossycompressiontechniques.

18. Methodology (cont.)
In Block Diagram in the following shows the work in sequence.

19. Methodology (cont.)
Step 1
Pre Processing
Firststepoftheproposed
systemWhenenterfiveimagesto
thesystem,pre-processingwillbe
appliedonimageswhichare
resizeoftheimageinaccordance
withthemeasuredrateof
differentsizesto(8×8)Andthen
convertedfrom(RGB)to(gray
scale).

20. Methodology(cont.)
Step 2
Wavelet transforms
Imagetransformationphase
receivedtheresizablegray
scaleimagesandproduced
transformedimages.This
phaseusedthethreetypesof
wavelettransformssuchas
DWT,LWT,andSWT.

21. Methodology(cont.)
Step 3
Zigzag Scan
In this step we convert the matrix
from 2-D to 1-D by zigzag scan.
Zigzagscansorderingconvertinga
2-Dmatrixintoa1-Darray,sothat
thefrequency(horizontal+vertical)
increaseinthisorderandthe
coefficientvariancedecreasesinthis
orderasfigure.

22. Step 4
Lossy compression
Inthisstepwedomorethan
trytogetthehighestpossible
compressionratio.Weenterthe
matrixtolossycompression
using(VQ).Andagainweenter
thematrixtolossless
compression(HuffmanCoding
andArithmeticCoding)and
makeacomparisonofthe
resultsBetweenthetwo
experiments.Andagainwe
enterthematrixtolossy
compressionusing(VQ),output
ofthisprocess,introduceitto
losslesscompression(Huffman
CodingandArithmeticCoding)
togetthehighestpossible
compressionratioandcompare
theresultsandfindthebest
Methodology(cont.)

23. Methodology(cont.)
Compression Ratio
Compression Ratio: is the ratio of size of the compressed database
system with the original size of the uncompressed database
systems. Also known as compression power is a computer-science
term used to quantify the reduction in data-representation size
produced by a data compression algorithm. Compression ratio is
defined as follows:
Compression Time
•CompressionTime=representstheelapsedtimeduringthe
compressionprocess.

24. Experiments and Results Analysis
Experiments
Inthissectionoftheperformanceofthreetypesofwavelettransform
(SWT,DWT,andLWT)andtheimpactofeachtypeontheimage
lossycompressionperformancealsoitshowsthelossyusingvector
quantization(LBG)andlosslesscompressionusingArithmeticcoding
andHuffmancoding.
The First Experiment
In this experiment, four operations:
1-DWT-Zigzag-Arithmetic
2-DWT-Zigzag-LBG–Arithmetic
3-DWT-Zigzag-Huffman
4-DWT-Zigzag-LBG–Huffman
Table1showingresultsfortheprocesslossyandlosslessimage
compressiontothefiveimagesusingthediscretewavelettransform
witharithmeticcodingandhuffmancodingwithouttheuseofthe
LBG,aswellaswiththeuseoftheLBGandthatusingthree
decompositionlevels.

25. Experiments (cont.)
Discrete wavelet transform, vector quantization (LBG), Arithmetic and Huffman coding
DWT
DWT Zigzag
Arithmetic
DWT Zigzag LBG &
Arithmetic
DWT Zigzag
Huffman
DWT Zigzag LBG &
Huffman
ImageLevelC.Ratio
Running
time(Sec)
C.Ratiopsnr
Running
time(Sec)
C.Ratio
Running
time(Sec)
C.Ratiopsnr
Running
time (Sec)
Lena
1 1.1934 0.49191.254918.2975 0.0157 1.1403 0.07351.187918.29750.057
2 1.261 0.04591.302718.2745 0.012 1.0556 0.07851.140318.27450.0438
3 1.2994 0.0721 1.28 18.2449 0.0164 1.026 0.12371.158318.24490.0465
Camera
man
1 1.2518 0.03511.254918.2588 0.0158 1.177 0.06111.254918.25880.0421
2 1.2549 0.04981.264118.1648 0.0125 1.1557 0.09041.204718.16480.0459
3 1.2896 0.062 1.245718.0733 0.0111 1.1454 0.11481.201818.07330.0609
Tulips
1 1.1851 0.093 1.242717.4091 0.0153 1.1824 0.1483 1.19917.40910.0657
2 1.1934 0.0965 1.28 17.4196 0.0105 1.177 0.1231 1.19917.41960.0458
3 1.0916 0.11311.286417.3919 0.011 1.1479 0.25481.182417.39190.0447
White
flower
1 1.0622 0.04311.254916.7503 0.0128 1.0385 0.07641.187916.75030.0413
2 1.1203 0.05461.254916.7639 0.0106 1.0893 0.075 1.193416.76390.0458
3 1.0916 0.04571.251816.8377 0.0169 1.026 0.07851.187916.83770.047
Fruits
1 1.2047 0.0489 1.28 17.5693 0.013 1.1428 0.08291.210417.56930.0513
2 1.2104 0.09221.242717.6137 0.0139 1.1302 0.09671.216117.61370.044
3 1.2161 0.05081.264117.5718 0.0148 1.1252 0.08311.196217.57180.0455

26. Experiments (cont.)
The SecondExperiment
In this experiment, four operations:
1-LWT-Zigzag-Arithmetic
2-LWT-Zigzag-LBG–Arithmetic
3-LWT-Zigzag-Huffman
4-LWT-Zigzag-LBG–Huffman
Table2showingresultsfortheprocesslossyandlossless
imagecompressiontothefiveimagesusingthelifting
wavelettransformwitharithmeticcodingandhuffman
codingwithouttheuseoftheLBG,aswellaswiththe
useoftheLBGandthatusingthreedecompositionlevels
.

27. Experiments (cont.)
Lifting wavelet transform, vector quantization (LBG), Arithmetic and Huffman coding
LWT
LWT Zigzag
Arithmetic
LWT Zigzag LBG &
Arithmetic
LWT Zigzag
Huffman
LWT Zigzag LBG &
Huffman
Image LevelC.Ratio
Running
time (Sec)
C.Ratiopsnr
Running
time (Sec)
C.Ratio
Running
time (Sec)
C.Ratio psnr
Running
time (Sec)
Lena
1 1.40650.31771.684213.18760.00811.37630.06741.454513.18760.0216
2 1.37630.42311.64111.97840.00971.1130.05271.471211.97840.0162
3 1.16360.04891.684217.43940.00731.0940.07081.454517.43940.0154
Camera
man
1 1.54210.06581.64113.68950.00761.26730.05111.471213.68950.017
2 1.24270.03261.753412.70650.00931.13270.04011.422212.70650.0155
3 1.14280.03761.662316.96490.00741.12280.08361.422216.96490.0204
Tulips
1 1.02750.09471.777716.29790.01221.37630.13571.454517.00320.0196
2 1.43820.13361.64112.26710.01111.0940.10541.471212.26710.0225
3 1.25490.11741.684219.54650.00731.05780.10671.454519.54650.0162
White
flower
1 1.3913 0.04 1.64115.46610.00731.37630.05371.471215.46610.0182
2 1.30610.04731.706614.37030.01181.25490.05281.454514.37030.0186
3 1.16360.08271.64116.12410.00741.25490.05991.471216.12410.0162
Fruits
1 1.23970.04531.777712.33940.00911.12280.05571.406512.33940.016
2 1.3763 0.079 1.64112.22890.00891.1130.09021.471212.22890.0164
3 1.19620.08741.620218.16020.00741.07560.06521.406518.16020.0164

28. Experiments (cont.)
The ThirdExperiment
In this experiment, four operations:
1-SWT-Zigzag-Arithmetic
2-SWT–Zigzag-LBG–Arithmetic
3-SWT-Zigzag-Huffman
4-SWT–Zigzag-LBG–Huffman
Inthetable3,showingresultsfortheprocesslossyandlossless
imagecompressiontofiveimagesusingstationarywavelet
transformwitharithmeticcodingandHuffmancodingwithoutthe
useoftheLBG,aswellaswiththeuseoftheLBGandthatusing
threedecompositionlevels.

29. Experiments (cont.)
Stationary wavelet transform, vector quantization (LBG), Arithmetic and Huffman coding
SWT
SWT Zigzag
Arithmetic
SWT Zigzag LBG &
Arithmetic
SWT Zigzag
Huffman
SWT Zigzag LBG &
Huffman
ImageLevelC.Ratio
Running
time(Sec)
C.Ratio psnr
Running
time(Sec)
C.Ratio
Running
time(Sec)
C.Ratio psnr
Running
time(Sec)
Lena
1 4.36670.11555.007318.01210.0685 2.6256 0.8594.818818.01210.0473
2 4.36670.04145.007318.89820.012 2.6256 0.84394.818818.89820.0455
3 4.36670.19065.007318.89820.0137 2.6256 0.85764.818818.89820.0422
Camera
man
1 4.10420.06515.007316.84830.011 2.6771 0.91574.85316.84830.0419
2 4.10420.05375.007318.10990.011 2.6771 0.83464.85318.10990.0447
3 4.10420.03985.007318.10990.0103 2.6771 0.94814.85318.10990.0462
Tulips
1 3.86410.09345.657418.67870.0099 2.7563 0.89654.602218.67870.0461
2 3.86410.09615.657417.17980.0116 2.7563 0.92894.602217.17980.0456
3 3.86410.09695.657417.17980.0121 2.7563 0.89194.602217.17980.0421
White
flower
1 3.73720.03934.958817.30020.0117 2.7018 0.84834.675717.30020.0459
2 3.73720.03924.958817.21420.0128 2.7018 0.84384.675717.21420.0459
3 3.73720.0414.958817.21420.012 2.7018 0.84114.675717.21420.0412
Fruits
1 3.8280.05845.107218.95030.0132 2.7379 0.84384.320618.95030.0435
2 3.8280.4585.107218.17390.0105 2.7379 0.85854.320618.17390.0567
3 3.8280.11885.107218.17390.012 2.7379 0.84634.320618.17390.043

30. Experiments (cont.)
Average Compression Ratio Level –1
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5.5
Arithmatic LBG Zigzag Arithmatic Huffman LBG Zigzag Huffman
Average Compression Ratio (C.R) in Level -1
SWT
DWT
LWT
Inlevel-1,wefindthatSWT&LBGZigzagarithmeticthebest
thing,andfindthatarithmeticthebestofhuffmanwitheveryone.

31. Experiments (cont.)
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5.5
Arithmatic LBG Zigzag Arithmatic Huffman LBG Zigzag Huffman
Average Compression Ratio (C.R) in Level -2
SWT
DWT
LWT
Average Compression Ratio Level –2
Inlevel-2,WefindthatSWT&LBGZigzagArithmeticthebest
thing,andfindthatArithmeticthebestofHuffmanwitheveryone,
andfirming(SWT)asinlevel1,andthehighrateof(DWT)and
lowrate(LWT).

32. Experiments (cont.)
Average Compression Ratio Level –3
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
5.5
Arithmatic LBG Zigzag Arithmatic Huffman LBG Zigzag Huffman
Average Compression Ratio (C.R) in Level -3
SWT
DWT
LWT
Inlevel-3,wefindthatSWT&LBGZigzagArithmeticthebest
thing,andfindthatArithmeticthebestofHuffmanwitheveryone,
andfirming(SWT)asinlevel1&2,andthelowrateof(DWT)
andlowrate(LWT).

33. 1-CompressionratioinLBGBiggerwithoutLBG.
2-Stationarywavelettransformbesttransform.
3-ArithmeticcodingbestofHuffmancoding.
4-ThatthebestpathforimagecompressionisStationarywavelet
transform-zigzagscan–VectorQuantization(LBG)-Arithmetic
codingwherethecompressionratioachieved5.1476in0.02286
Runningtime(Sec).
Results Analysis

34. Thisthesisintroducedanovelapproachthatisbuilttoworkon
imagecompression.OurapproachusedvectorquantizationLB
G,ArithmeticcodingandHuffmancodingwiththreetypesofwa
velettransformssuchasDiscreteWaveletTransformDWT,Lifti
ngWaveletTransformLWT,andStationaryWaveletTransform
SWTonthreedecompositionlevels.AsinStationaryWaveletTr
ansform(SWT)compressionratioisfixedatahighlevel,andDi
screteWaveletTransform(DWT)compressionratiovariableata
highlevel,eitherLiftingWaveletTransform(LWT)islessthant
hecompressionathighlevel.
WeconcludethatarithmeticcodingisbetterthanHuffmancodi
ngintermsofcompressionratioandtime.Wefoundthatthebes
twaytocompressioninthissystemisthestationarywavelettran
sforms(SWT),LBGvectorquantization,andarithmeticcoding
whereitgivesthebestcompressionratiowithlesstimepossible.
Alsothesizeofcompresseddatabyaddingarithmeticcodingisb
etterthanaddingHuffmancodingtoSWT.
CONCLUSION