VISUALDATAREPRESENTATIONANDCODINGBASEDONTENSORDECOMPOSITIONANDSUPER-RESOLUTIONByAboTalibMahfoodhADISSERTATIONSubmittedtoMichiganStateUniversityinpartialentoftherequirementsforthedegreeofElectricalEngineering|DoctorofPhilosophy2016ABSTRACTVISUALDATAREPRESENTATIONANDCODINGBASEDONTENSORDECOMPOSITIONANDSUPER-RESOLUTIONByAboTalibMahfoodhTensorbasedmethodshavebeenusedinawiderangeofsignalprocessingapplications.Aparticularareaofinterestistensordecomposition,whichcanbeusedtoreducethedi-mensionalityofthemassivemultidimensionaldata.Hence,tensordecompositioncanbeconsideredasahighdimensionextensionofpopularSingularValueDecomposition(SVD)methodsusedformatrixanalysis.Thelowerdimensionrepresentationoftensorsresultingfromtensordecompositioncanbeusedforpatternrecognition,andreconstruc-tion.Ourobjectiveinthepartofthisthesis,istodevelopatensorcodingframeworkbasedonatensordecompositionmethodforvisualdataentrepresentationandcom-pression.Aspartoftheproposedtensorcodingframework,wedevelopedatensordecompositionalgorithmthatdecomposedtheinputtensorintoasetofrank-onetensors.Theproposeddecompositionisdesignedtobetspforvisualdata.Theproposedtensordecompositionalgorithmisappliedinablock-wiseapproach.Twopartitioningmethodsareproposedfortensorcodingframeworkwhichareuniformandadaptivetreepartitioning.Theformersubdividearegionintoasetofequalsizeblockswhilethelatersubdividearegionintoasetofvariablesizeblocks.Thedecisionwhethertosubdividetheregionornotismadebasedontheexistingamountoftheinformationandtheoverallavailablebitrate.Atreedatastructurestoresthepartitioningstructureinformationwhichisrequiredforthetensorreconstructionprocess.Furthermore,anencoder/decoderframeworkisproposedforcompressingandstoringthedecomposeddata.Theproposedframeworkprovidesanumberofdesirablepropertiesespeciallyatthedecodersidewhichcanbecriticalforsomeapplications.Lowcomplexityreconstruction,randomaccess,andscalabilityarethemainpropertiesthatwehavetargeted.Wedemonstratetheviabilityoftheproposedtensorcodingframeworkbyemployingitfortherepresentationandcodingofthreetypesofdatasets:hyperspectral/multispectralimages,bio-metricfaceimageensembles,andlowmotionvideos.Thesedatasetscanbearrangedaseitherthreeorfourdimensionaltensors.Foreachapplication,weshowthatthecompressionalongwiththeinheritedpropertiesoftheproposedtensorcodingframework,provideacompetitiveapproachtothecurrentstandardmethods.Inthesecondpartofthethesis,weproposeanexample-basedsuper-resolutionalgorithmforanewframeworkofscalablevideostreaming.Theproposedmethodisapplicabletoscal-ablevideoswheretheenhancementlayerofsomeframesmightbedroppedduetochangingnetworkconditions.ThisleadstoastreamingscenariothatwecallInconsistentScalableVideo(ISV)streaming.Atthedecoder,theframeswiththeenhancementlayerareusedasadictionaryforsuper-resolvingothervideoframeswhoseenhancementlayersweredropped.Theproposedsuper-resolutionframeworkisintegratedwithGoogleVP9videocodec.ThenitisappliedtovariousHigh(HD)videostoestimatethedroppedenhancementlayer.OursimulationresultsshowanimprovementvisuallyandintermsofPSNRovertraditionalinterpolationup-samplingTomyfamily...ivACKNOWLEDGMENTSIwouldliketothankprofessorHayderRadhawhohasbeenmyadviserduringthePhDprogram.Itwasagreatlearningopportunityformetoworkwithhim.Hissupportiveandconstructiveguidancewasamajorcontributortomysuccessincompletingthisthesis.IalsowouldliketothankmyguidancecommitteemembersprofessorSelinAviyente,professorYiyingTong,andprofessorLalitaUdpafortheirsupport,andforwhatIhavelearnedfromthem.MyspecialgratitudetoprofessorYiyingTongforhisgracioussupportthatleftagreatimpactonme.vTABLEOFCONTENTSLISTOFTABLES....................................viiiLISTOFFIGURES...................................ixChapter1Introduction...............................11.1TensorCoding...................................11.2Tensorcodingmotivations............................41.3Tensorcodingrelatedwork............................51.4Inconsistentscalablevideostreaming......................91.5ISVrelatedwork.................................111.6Summaryofcontributions............................121.7Thesisorganization................................13Chapter2Tensordecompositionforvisualdata................152.1CPdecomposition.................................152.2CPdecompositionforvisualdata........................182.3ProgressiveCPdecomposition..........................192.4TheRank-Distortionoptimizationproblem...................232.5Rank-Distortionoptimizationproblemsolution.................26Chapter3Tensorcodingframework.......................303.1Tensorpartitioning................................303.1.1Uniformpartitioning...........................313.1.2Adaptivetreepartitioning........................343.2ersarrangementandcoding.......................393.3Residualcoding..................................443.4Tensorcodingproperties.............................453.4.1Randomaccess..............................453.4.2Progressivereconstructionanddecoding................473.4.3PCPtimecomplexity...........................47Chapter4Tensorcodingapplications......................504.1Hyperspectralimagecoding...........................504.1.1Experimentalresults...........................514.2Imageensemblescoding.............................614.2.1Experimentalresults...........................614.3Lowcomplexityvideocoding...........................654.3.1Experimentalresults...........................66viChapter5Super-resolutionforreconstructinghighfrequencydata....785.1SpatialISVwithHybridSuperandBaseFrames................785.2Super-resolutionframeworkforISV.......................805.3Experimentalresults...............................82Chapter6Conclusion................................88BIBLIOGRAPHY....................................91viiLISTOFTABLESTable4.1:bitratecomparisonbetweentensorcodingandJPEG2000forvarioushyperspectralimagesfromAVIRISdataset..............54Table4.2:Theencoding/decodingtime,PSNRandbitrateoftenCIFvideoswith180framesusingfourcodingmethods.Relatively-lowand(al-most)thesamePSNRvaluesweretargetedforthisexperimenttocomparethebitrateandtimecomplexity................74Table4.2:(cont'd)..................................75Table4.3:Theencoding/decodingtime,PSNRandbitrateoftenCIFvideoswith180framesusingfourcodingmethods.Relatively-highand(al-most)thesamePSNRvaluesweretargetedforthisexperimenttocomparethebitrateandtimecomplexity................76Table4.3:(cont'd)..................................77Table5.1:PSNRcomparisonbetweenbicubicup-samplingandtheproposedsuper-resolutionframework........................87viiiLISTOFFIGURESFigure2.1:AthreedimensionaltensorreconstructionfromasetofRrank-onetensors.Each3Drankonetensorisanouterproductofthreevectors.Thereconstructedtensorisalinearcombinationoftheserankonetensors...................................16Figure2.2:PCPdecompositionprogressivereconstructionof˜.Attheiter-ationtheinputtensorisapproximatedwithonlyonerankonetensor.Thenateachiterationarankonetensorisaddedtoapproximatetheresidual..................................21Figure2.3:Anexampleofuniformpartitioningofan3DtensorandthePCPdecompositiononeachblock.PCPallocatestvalueofRjforeachblockbasedontheamountoftheinformationinthatparticularblock...................................21Figure3.1:Tensorcodingframeworkforvisualdatacodingandrepresentation.Theframeworkconsistofvariousmodulesthatoperateatntstages.Amongthesemodulesaretensorpartitioning,decomposition,anderscoding.Italsoshowstheresidualcodingprocess...31Figure3.2:PSNRvsbitrateplotsof(a)Silentand(b)ContainerCIFvideosemployingthreetblocksizes.LargerblocksizesresultinhigherPSNRatlowerbitrateshoweveratsomebitratepointtheycrossover.................................32Figure3.3:PSNRplotsof(a)Silentand(b)ContainerCIFvideosemployingblocksofenttimedimensionsize.Theplotsshowthatifthevideohashighredundancyacrosstime,thenlargerblocksizeswillresultinhigherPSNR..........................33Figure3.4:(a)Anexampleof3Dblockrecursivesubdivision,and(b)itscorre-spondingoctreerepresentation.Theleafnodeindicatenosubdivisionwhilethebranchingnodesubdividedandithaseightchildren.Aleafisrepresentedby0andabranchingnodeisrepresentedby1.Theoctreerepresentationcodeisalsoshown................35Figure3.5:Anexamplethreelevelshextreestructurewithitscorrespondingcode.Eachbranchingnodehas16childrennodeswhichcanbeeitheraleaforabranchingnodeaswell....................37ixFigure3.6:Anexamplethreelevels2n-arytreestructurewithitscorrespondingcode.Eachbranchingnodehas2nchildrennodeswhichcanbeeitheraleaforabranchingnodeaswell...................37Figure3.7:ersofthePCPtensordecompositionandtherankvaluesRfor50blocksoftheContainerCIFvideowith180frames.Theshowsapossibleersarrangementforcodingandstorage...40Figure3.8:Thecorrelationamong(a)matrixAcolumns(i.e.CPvectors);(b)matrixBcolumns(i.e.PCPers);Thecorrelationamong(c)matrixArows;(d)matrixBrows;(e)after(r;j)absorptionontoa(3)(r;j)vectors;and(f)after(r;j)absorptionontob(3)r.ThevideoisContainerCIF...............................42Figure3.9:"RedFlower"CIFvideoencodedbytensorcodingwithatotalof4000rank-onetensors.Uniformpartitioningwasusedwithblocksizeof1616180.Thevideodecodedwith(a)1000(93Kbps30.43dB),(b)2000(205Kbps35.76dB),(c)3000(320Kbps38.49dB),(d)4000(433Kbps40dB),rank-onetensors...................48Figure4.1:IndianpinePSNRvsbpppbcomparisonamongTCwithtblocksizes,TCwithoctreeandJPEG2000...............52Figure4.2:Thespectralover200bandsofaparticularspatiallocationfromtheIndianpinedatashowninFigure4.3.Threereconstructedspectralbasedontheproposedframeworkattbitratesareshown.................................53Figure4.3:Ahyperspectral3Dimagingdataanditsreconstructedrepresentationusingaprogressivenumberof3Dersets.Compressionratiosragingfromoneorderofmagnitude(nearlossless)tomorethantwoordersofmagnitude.(b)OriginalIndianpine,(b)100ers,compressionratio213,(c)1000ers,compressionratio37,(d)1000ersplusresidualcoding,compressionratio10......55Figure4.4:LakemultispectralimagePSNRvsbpppbcomparison.Thecom-pressionresultof4Dtensorcodingwithhextreepartitioningiscom-paredwith3Dtensorcodingwithoctreepartitioning.4Dtensorcod-ingachieveshighercompressionbyexploitingtheexistingcorrelationalongallthedimensionofthelakemultispectralimage........57xFigure4.5:Lakemultispectralimagedecodingtimecomparison.Thedecodetimepersliceisshowninmillisecondsfor4Dand3Dtensorcoding.Atlowerbitratesthedecodingtimeisclosewhileinthehigherbitratesthe4Dtensorcodingresultsinhigherdecodingtime.........57Figure4.6:3Dtensorcodingofhigh-resolution2K2Kpixelsacross20timeinstancesofLandsatdata.(a)originalimage,(b)compressionratio=1142andPSNR=29,(c)compressionratio=727andPSNR=30.83,(d)compressionratio=534andPSNR=31.73,(e)compressionratio=421andPSNR=32.37,(f)compressionratio=340andPSNR=32.88....................................59Figure4.7:4Dtensorcodingofhighresolution2K2Kpixelsacross20timeinstancesofLandsatdata.(a)originalimage,(b)compressionratio=6154andPSNR=27.29,(c)compressionratio=4210andPSNR=29.43,(d)compressionratio=3077andPSNR=30.43,(e)com-pressionratio=1429andPSNR=31.02,(f)compressionratio=769andPSNR=32.22..........................60Figure4.8:AveragePSNRplotof38personsfaceimagesfromYaleFaceDatabaseBversustheaveragestoragesizerequiredperimage..........62Figure4.9:PCPRvaluesfortheblocksofanimageencodedata)288Bytesb)979Bytes.Astheallocatednumberofrankonetensorsisincreased,thetensorcodingframeworkallocateahighernumberofrankonetensorstotheblockswithmoreinformation.Forexampletheblocksthatcontainstheeyesandthemouth.................63Figure4.10:(a)Originalimage;(b)tensorcodingwithPCP(288Bytes,30.1dB);(c)tensorcodingwithCP(286Bytes,28.98dB);(d)JPEG2000(291Bytes,25.68dB);(e)motionJPEG2000(292Bytes,24.63dB);(f)JPEG(790Bytes,25.19dB).....................64Figure4.11:(a)Originalimage;(b)tensorcodingwithPCP(979Bytes,PSNR:34.5);(c)tensorcodingwithCP(986Bytes,PSNR:32.6);(d)JPEG2000(975Bytes,PSNR:35.27);(e)motionJPEG2000(990Bytes,PSNR:35.1);(f)JPEG(999Bytes,PSNR:29.1)................64Figure4.12:Averagea)decodingb)encodingtimeof38personsfaceimagesfromYaleFaceDatabaseBversustheaveragestoragesizerequiredperimage...................................65Figure4.13:HEVCIntraandH.264Intratimecomplexitycomparisonforcon-tainervideo.(a)Encodingtime,(b)Decodingtime..........67xiFigure4.14:PSNRvs.bitrateplotsof(a)Container,(b)Silent,(c)BridgeClosevideo....................................68Figure4.15:PSNRvs.framesplotsof(a)Container(500Kbps),(b)Silent(699Kbps),(c)BridgeClose(380Kbps)videosencodedwithTCandSPIHT.TensorcodingmaintainsamoreuniformPSNRacrosstheframeswhiletheSPIHTqualitytendstodegradeasitgetclosertotheendoftheGOP............................69Figure4.16:Frame14oftheContainerCIFvideo.(a)originalvideo,(b)tensorcoding(731.07Kbps;37.39dB),(c)H.264/AVC-no-motion(732.09Kbps;35.26dB),(d)DISCOVERDVC(735.53Kbps;34.06dB),(e)H.264/AVC-Intra(753.96Kbps;30.02dB),(f)SPIHT(732.94Kbps;38.22dB).................................70Figure4.17:TherstframeoftheBridgeCloseCIFvideo.(a)originalframe,(b)tensorcoding(202.74Kbps;33.48dB),(c)H.264/AVC-no-motion(209.29Kbps;32.21dB),(d)DISCOVERDVC(274.77Kbps;28.32dB),(e)H.264/AVC-Intra(218.41Kbps;26.71dB),(f)SPIHT(203.77Kbps;31.81dB)..............................71Figure5.1:EncoderdiagramoftheproposedspatialISVwithhybridtwo-layerspatialvideocodingthatconsistofthesuper-framesandthebase-frames.Theprocessofgeneratingthebaseandtheenhancementlayerisshown...............................79Figure5.2:Theproposeddecoderstructurewithsuper-resolutionframeworkforatwo-layerISVencodedvideo.Thereconstructeddisplayvideoconsistsofsuper-framesandbase-frames.Thesuper-framesareaddeddirectlywhilethebase-framesaresuperresolvedtoimprovetheirquality...................................80Figure5.3:Thequadtreeblockstructurewhichwasusedfortheproposedsuper-resolutionframework.Theframeisthe25thframeoftheintotree.83Figure5.4:PSNRcomparisonoftheproposedsuper-resolutionframeworkwhenappliedtoquadtreeandvarioussizeblocks...........84Figure5.5:PSNRresultsofthesuper-resolutionwithbilinearup-sampling,super-resolutionwithBicubicup-sampling,bilinearup-sampling,andBicu-bicup-samplingof(a)Intotree,(b)shields,and(c)oldtown....85xiiFigure5.6:Frame27ofthe(a)original,(b)bilinearup-samplingandthepro-posedsuper-resolutionframework,(c)bilinearup-sampling,(d)bicu-bicup-sampling,oftheoldtownvideo.For(b),(c),and(d),thevideoisencodedat2.7Mbps......................86xiiiChapter1Introduction1.1TensorCodingTensordecomposition,whichisageneralizationofmatrixSVDdecomposition,hasbeenreceivinggrowingattentionrecently[1{5].Tensorsaremulti-dimensionalsetofdataandgeneralizationsofvectorsandmatrices,whichare1Dand2Dtensors,respectively.Therearetwomaintensordecompositionmethods.TheoneisknownasHigherOrderSVD(HOSVD)orTuckerdecomposition[1,6].TheseconddecompositionapproachisknownasCanonical-decompositionParallel-factor(CP)[7,8].TheCPdecompositionfactorizesatensorontoanumberofrank-onetensors[1].Arank-onetensorcanbethoughtofasa"basis-tensor"thatcanberepresentedtlyandreconstructedperfectlyusing1Dvectors.Inparticular,anndimensionalrank-onetensorcanberepresentedbyn1Dvectorsonly.LikematrixSVD,tensordecompositionmethodsareusedinawiderangeofapplications.Tensordecompositionhasbeenusedfordataanalysis,fusion,representationand[9].Inthisthesis,weproposeaframeworkbasedontensordecompositionforrepresentationandcodingofndimensionalvisualdata.Therearevarioustypesofdatathatcaninthiscategoryof"ndimensionalvisualdata".Forexample,asetof2Dvideoframesovertimeisinherentlya3Ddataset.Also,asetofimagesstoredwithinacommonimagedatabase(e.g.,forstoringimagesofhumanfaces;orimagesofcertainclassofvisualobjects)canbecategorizedasahighdimensiondataset.Ingeneral,forasetoflargenumberofimagesor12Dvideoframesstoredinacommonimagedatabase,wecallthesetypesofimaging/videodataasa"visualdataensemble".Hence,inthisthesis,anensembleisa3Dorhigherdimensionalsetoftensordata.Wecallthe2Dmatricesalongaparticulardimension,slice.Forexamplea3Dvisualdataensembleconsistsof2Dmatricesalongthethirddimension,whicharestackedontopofeachother.Inourexperiments,weused3Dand4Dvisualdataensemblestoillustratetheconceptandshowtheexperimentalresults.Ourgoalistodevelopacompressionapproachforvisualdataensembleswhileachievingdesirablepropertiesforapplicationslikewebbrowsingandimageretrieval.Atensorbasedcodingframeworkcanachieve:Randomaccess:Itistheabilitytoreconstructanyslicewithinanensemblewithouttheneedtoreconstructoraccessanyotherslicefromthesameensemble.Randomaccessiscrucialforsomeapplications,notonlyforstoragecy,butalsotoreducebandwidthacrossnetworksforscalablesearchandretrievalengines.Codingachievinghighercompressionratiobyexploitinganypotentialcorrelationthatmayexistamongthesliceswithinthesamedataset.Lowcomplexity:Theabilitytoreconstructtheoriginaltensordatawithlowcom-plexitycanprovidefastaccessandenablelowenddevicestobfromtheproposedapproach.Aspartoftheproposedtensorcodingframework,wedevelopedaProgressiveCanoni-cal/Parallel(PCP)tensordecomposition,whichisbasedonthepopularCPtensorfactor-ization[1],fordecomposinganyarbitrarygivenvisualdataensemble.SimilartoCP,PCPfactorsann-dimensionaltensorintoasetofRrank-onetensors,eachofwhichisrepresentedbynonedimensionalvectors.WeapplyPCPinablock-wisebasis,andeachtensor-block2isdecomposedintoatnumberofrank-onetensors.Dependingonthenatureofthedata,auniformpartitioningoranadaptivetreepartitioningcanbeemployedtopartitionthetensorintoasetofequalsizeblocksorvariablesizeblocksrespectively.Theblock-wisetensordecompositionstrategyleadstotheneedforderivingtheoptimaldistributionofrank-onetensorsamongthetvisualdataensembletensorblocks.Thus,wefor-mulatedtherankdistributionasanoptimizationproblem.Agreedyalgorithmisdevelopedforidentifyingtheoptimalnumberofrank-onetensorsthatshouldbeusedfordecomposingtheensembleblocks.Tensordecompositioniswellsuitedforapproximatinglowrankdata.Ifthesignalcon-tainsalargeamountofhighfrequencydata,thentherankofthecorrespondingtensorishigh.Forthehighranktensors,atsomepointwewouldnotbeabletocapturethehighfrequencyinformation,nomatterhowmanyrank-onetensorsareused.Meanwhile,therearecasesandapplicationsthatwouldnotrequirethepresenceofhighfrequencydata,enablingthepossibilityofnearlosslessandlosslesscompressionisdesirable.Theyofthereconstructionqualitythatcanrangefromlowqualitytohighqualitycanservedttypesofapplications.Aresidualcodingmoduleispresentedaspartoftheproposedtensorcodingframeworktoenablenear-losslesscoding.Dataencodingbasedontensordecompositionhastapplicationsfor3Dandhigherdimensionalvisualdataensembles.Forexample,alowmotionvideoholdsahighcorrelationamongtheframeswhichcanbeexploitedforlowcomplexitycoding[10].Similarly,animageensembleoffaceimages,canbecodedwithtensor-factorizationbasedmethod[11]toexploittheexistingcorrelationamongalargenumberofimages.Thepotentialapplicationsoftheproposedtensorcodingframeworkareillustratedusingthreetypesofdatasets:1.Hyperspectral/multispectralimagesdataset:Thesetypesofdatasethavea3highcorrelationinthespectrumspectralandtimetemporaldimension.Theproposedtensorcodingframeworkexploitsthiscorrelationtocreateantrepresentationandcodingthatholdsthedesirablerandomaccessproperty.2.Bio-metricfaceimagedataset:Asetoffaceimagestakenundertcondi-tions,whichcanbeusedforrecognitionandanalysis,forma3Dtensor.Theseimagescontainahighamountofsimilarities,espciallyforfaceimagesofthesameperson.3.Lowcomplexityvideocompression:Theproposedtensorcodingframeworkcanbeusedinvideocodingscenarioswherelowcomplexitydecodingandrandomaccessareimportant.1.2TensorcodingmotivationsVisualdataisacorecomponentofmanyapplicationsandservices.Forexampleim-agedatabasesoffacesandtsareusedforsecurityapplications,andhyperspec-tral/multispectralimagesareusedforscienanalysis.Suchdatabasesstorealargenum-berofimagesofthesametype.Inmanysuchapplications,thetraditionalcompressionstandardsareusedtostoretheseimageswithoutexploitingthecorrelation.Thegoaloftheproposedtensorcodingframeworkistodevelopacompressionmethodtoprovide:Randomaccesstoanyslicewithoutdecodingotherslices.Codingbyexploitinganypotentialcorrelationthatmayexistamongthesliceswithinthesamedataset.Lowcomplexityandfastdecoding.4Scalablereconstructioninwhichalowerqualitycanbereconstructedwithpartoftheencodeddata.Enablefastaccessandbrowsing.1.3TensorcodingrelatedworkTensorbasedalgorithmshavebeenusedwidelyinimageprocessingandcomputervisionapplications[3,12].Ourproposedframeworkbelongstotheareaofmultidimensionalsignaldecomposition.In[13]avideoencoderbasedon2DSVDdecompositionwasproposed.2DSVD[14]decomposesaGOPontotwoeigenvectormatricesandgroupofcotmatrices.Theirframeworkwasbasedoncodingthefactoredmatrices.Ourmethodhastwoadvantagesover2DSVDencoder.(a)Itisfasterthan2DSVD.(b)Itcanbeextendedtohigherdimensions.FurthermoretheproposedtensorcodingframeworkprovideshigherPSNR.ArankRdecompositionmethodwasproposedin[15]forvideodimensionreduction.Basedonthepresentedexperimentalresults,themethodworkswellfortexturevideos,whichareknowntobelowrank.ThevalueofRintheproposedmethodisThesamemethodwasusedin[16]forcompactrepresentationofvideotextures.AntrankRdecompositionwasproposedin[17]forcompactrepresentationofimageensembles.Themethodwasusedforcompactrepresentationoffacedatasetsandtoyvideosequence.HOSVDanalysis(Tuckerdecomposition)wasproposedin[17]formodelingdynamictextures.Similarly,HOSVDdecompositionwasusedin[18]forrepresentingfacialimagesincomputervisionproblems.5AD-1factorizationwasusedin[19]forvideocompressionandHowever,themethodwasusedforvideoclasscationnotcoding.Arank-onedecompositionwasusedforcompactrepresentationofmultidimensionaldatain[20].Theirmethodisbasedonstandardrank-onedecomposition,whichisnotastasourproposedPCP.Theyappliedtheirapproachfordecomposingvideotextures.Acompressionmethodbasedontuckerdecompositionwasproposedin[21]forhyper-spectralimages.Thetuckerdecompositionwasappliedonthewavelettransformcotsofthehyperspectralimagestocompacttheenergyofthesubimages.Thiswillresultinlossofrandomaccessproperty.Furthermore,[22,23]proposedtensorbasedmethodsforhyperspectralimagecompres-sion.Bothworkswerebasedonproposingadecompositionalgorithmwithoutpresentingacompletecodingframework.Itisimportanttomeasurethecompressionbasedonastoragerequirementnotjustthenumberofcocients.Thisisbecauseofthefactthatthedecomposedvaluesarenumbersasopposedtothevisualdatavalueswhichareusually8bitsintegers.LeiWangetal.presentedahyperspectralimagecompressionsystembasedonthelappedtransformandTuckerdecomposition[24].Thelappedtransformdecorrelatethehyperspec-tralimagebands.Thentheyarrangedthetransformedcotsoftfrequenciesintoa3Dwaveletsub-bandtensor.FinallyTuckerdecompositionwasusedtodecomposethetensorintoacoretensorandthreefactormatrices.Thebit-planecodingalgorithmwasusedtoencodethecoretensor.Vasilescu,M.AlexO.,andDemetriTerzopoulosproposedamultilinearmodelingtech-niquethatemploysanN-modeSVD[18].Theypresentedthemultilinearanalysisoffacialimagesensembleswhichcontainttypes,liketfacialgeometries,expressions,6headposes,andlightingconditions.TheycalltherepresentationTensorFacesandarguethatmultilinearanalysiscanbeaneframeworkforcomputervisionproblems.HazanTamiretal.presentedanalgorithmforanon-negative3Dtensordecompositionwhichextractsalocalpartsfeaturedecompositionfromasetofobjectimages[25].TheyshowedthatthisfeaturecanbeusedforfacedetectionusingSVMandAdaboostTheyarguethattheirtensorfactorizationhasauniquefactorizationanditpreservesthe2Drepresentationsofimages.Theyarguethattheproposedalgorithmimprovethesparsitylevel,ghostresidue,andcompressionaroundcomparingtoNMF.Wang,Hongcheng,etal.presentedanout-of-corealgorithmtoapproximatehighdimen-sionaltensors[26].Thealgorithmpreservetheoriginaldimensionalityofthedataitemsandhenceexploitexistingspatialredundancymoreelytoreducethecomputationcomplexity.Theypartitionatensorintoasetofblocksandcompletethetensoroperationsinablock-wiseapproach.Theirexperimentalresultsshowedtheadvantageoftheproposedmethodforthreegraphicsmodelswhichare6Dbidirectionaltexturefunctions,7DdynamicBTFsand4Dvolumesimulationsequences.Theproposedmethodcanprocessout-of-coredataandachievehighercompressionratioscomparingtothepreviousmethods.Inoue,Kohei,andKiichiUrahamaproposedadyadicsingularvaluedecomposition(DSVD)thatreducesthedimensionalityofasetofmatrixdata[27].Theirexperimen-talresultsshowedthemethodapplicationinimagecompressionandfacerecognition.TheDSVDalgorithmisderivedfromthehigherOrderSVD(HOSVD)ofathreedimensionaltensor.Itprovidesalowrankapproximationfordatamatrices.TheyshowedthattheDSVDcanprovidesbetterresultsintermsofthecomputationalcomplexityandaccuracyinimagecompressioncomparingtotheotherdimensionalityreductionmethods.Theyarguethattheirresultsarebetterthantheresultderivedfromtheeigenfacemethod.7HouJunhui,etal.proposedacompactandprogressiverepresentationofthemotioncap-turedatainvideocodingbyemployingatensordecompositionmethod[28].Theyarrangedthemotioncapturesequenceinathreedimensionaltensor.Theyarguethatthistypeofdatahasstrongcorrelationwithinandacrossslicesofthetensor.Then,theyperformedtensordecompositioniterativelytotakeadvantageoftheexistingcorrelation.Theirexperimentalresultsshowedthattheirproposedmethodprovidesbetterresultsintermsofscalabilityandstoragerequirementcomparingtotheexistingalgorithms.[29]SuterSusanneK.,etal.proposedamulti-scalevolumerepresentationinaGPU-acceleratedout-of-coremulti-resolutionrenderingframework.Theproposedmethodisbasedonthetensorapproximation.Theyarguethattheproposedhierarchicaltensordecomposi-tioncanachievelargevolumedatapre-processing,GPUacceleratedtensorreconstruction,andetensorquantizationfordatatransferbandwidthreduction.Theyshowedthattheproposedmulti-scalerepresentationcanperformtheextraction,analysisanddisplayofstructuralfeatures.Theirexperimentalresultsshowedtheapplicationoftheproposedmethosonagigabyte-sizedmicro-tomographicvolumesdataset.WuQing,etal.developedahierarchicaltensortransformationforcompactdatarepre-sentation[30].Inordertoshowtheexistingmultiscalestructures,amultidimensionaldatasetistransformedintoasetofhierarchicalsignals.Ateachlevel,thesignalisfurtherdividedintoasetofsmallertensors.Furthermoreatensorapproximationmethodisusedtotrans-formthesesmallertensors.Theirmethodhastheadvantageofprogressivereconstruction.Theirexperimentalresultsshowedthattheproposedmethodcanprovidehighercompres-sionratiosandqualitywhencomparedtowavelettransforms,waveletpackettransforms,andsingle-leveltensorapproximation.[31]Sivalingam,Ravishankar,etal.proposedasparserepresentationofpositive8nitematricesthatpreservestheinherentstructureofthedataunlikevectorization.Theyformulatedthesparsedecompositionofapositivematrixasaconvexoptimizationproblem.Antinteriorpointalgorithmscansolvetheformulatedproblem.Theirex-perimentalresultsshowedtheadvantageofthenewmodelforextendingthesparsity-basedalgorithmsforpositivematrices.1.4InconsistentscalablevideostreamingVideohasbeengrowingcontinuouslyespeciallyduringthelastfewyears.AccordingtoCISCO'sVisualNetworkingIndex[32],by2018thesumofallformsofvideowillbeinarangeof80to90percent.AnotherimportantfactorinCISCO'sindexisthefactthatby2018overhalfofallwilloriginatefromnon-PCdevices.Furthermore,themobiledatawillincrease11-foldandthefromwirelessdeviceswillexceedthefromwireddevices.Thereportedvideoincreaseaccountsforbothconsumergrowth,theemergingofhighqualityvideostreaming,andthedevelopmentofdevicesthatcancapture360degreevideosasvirtualrealitycontents.Therearealreadymany4k,8kvideos,andvirtualrealitycontentsavailableonmajorInternetportalssuchasYouTube,Amazon,andThesestatisticssupportthefactthatconsumersarerequestingvideocontentsfromvar-iousdevicesrangingfromsmallcell-phonestolargesmartTVs.Furthermorethenetworkconnectionqualityofthesedevicesmayvarytremendouslybasedontheregionandconsumerpreferences.Consequently,avideostreamingserverhastoensuresendingthebestqualityvideobasedontheuserdeviceandnetworkquality.ScalableVideoCoding(SVC)[33{35]isincreasinglyemergingasaviablesolutionto9addresstheaforementionedvariabilityinnetworkconditionsanddevicecapabilities.SomeexamplesamongthevarioustypesofSVCaretemporal,spatial,andSNRmethods.Inthisthesis,weaddresstheimportantcasewhensomeenhancementlayers(e.g.,withinaGOP)aredroppedwhileotherenhancementlayerscanreachthereceiver.ThisleadstoanIn-consistentScalableVideo(ISV)streaming.Insuchscenario,thedecodercanexploitthehigherquality/resolutionSVCdecodedpicturestoassistinasuper-resolutiondrivenrecon-structionofthelowerquality/resolutionpictures.TheproposedframeworkwasdevelopedforspatialSVC.However,itcanbeextendedandusedwithinotherformsofscalability,andinparticularSNRSVC.Theproposedframe-workisapplicablewhennetworkconditionschange,andconse-quently,astreamingservercanperformISVstreamingbychoosingtodropsomeoftheenhancement-layerframes.Underthesecircumstances,theframeswithdroppedlayersneedtobescaleduptothedisplaysize.AsimpleinterpolationmethodcanbeusedforISV.Howevertheframewouldbeblurryandmissingthehighfrequencydata.Thepro-posedframework,whichwasappliedinblock-wiseapproch,employesanexamplebasedsuper-resolutionmethodtoscaleupthoseframeswithabetterquality.Theblockpartitionstructurewasdrivedfromthequadtreeblockstructureoftheencoder.Ourexperimentalresultsshowthatthispartitioningstrategycanimprovesthereconstructionqualitywhencomparedtousinguniformsizeblocks.TheproposedframeworkwasimplementedwithinVP9spatialSVC[36].VP9isanopensourcevideocodecwhichhasbeendevelopedandsupportedbyGoogle.ThesourcecodeisavailableaspartofGooglesWebMprojectandcanbeobtainedfrom[37].101.5ISVrelatedworkManypriorortshavebeenproposedforsingleimagesuper-resolutionwithhighqualityreconstructionresults[38].Thebetterqualitycomesattheexpenseofhighercomputationcomplexity.Thiscomplexitymakesittoemploythesemethodsforvideos.In[39],theauthorsproposedafastsuper-resolutionmethodbasedonmulti-framesthatcanbeusedforvideo.However,thecomplexityforevenalowresolutionvideowashigh.Withtheemergenceofhighresolutionvideos(HDandabove),usingthistypeofsuper-resolutionisnotapplicable.Ontheotherhand,manyoftheclassicalimagesuper-resolutionmethodsdonotperformwellonthehigh-frequencycomponent[40].Thisisanimportantdrawbackespeciallyforhighresolutionvideossincethistypeofvideostendtohavemorehighfrequencycomponents.Avideosuper-resolutionframeworkhasbeenproposedin[41{43]basedoncodingsomeoftheframesatahighresolution(key-frames)tobeusedasthedictionary.Thenon-key-framesaresuperresolvedwiththehighfrequencydatafoundinthedictionary.Inourwork,wearefocusingonestimatingthehighfrequencycomponentasameanofsuperresolvingthevideo.Weuseasimilarexamplebasedsuper-resolutionasin[41]toscaleuptheframeswhoseenhancementlayerisdropped.FreemanWilliamT.,etal.proposedafastalgorithmforone-passsuper-resolutionthatisbasedonatraining-basedsuper-resolutionalgorithm[44].Thealgorithmperformanearest-neighborsearchinthetrainingsettoafeaturevectorthatisobtainedfromeachpatchoflocalimagedata.Theirexperimentalresultsshowedtheapplicationoftheproposedmethodinnaturalimagequalityenhancement.Xiong,Zhiwei,etal.proposedarobustsingleimagesuper-resolutionmethodtoincrease11thequalityoflowqualitywebimagesandvideos[45].Theirmethodcombinesadaptiveregularizationandlearning-basedsuper-resolution.Duringtheiterativeregularizationpro-cess,theimageenergychangecharacteristicsisanalyzed.Thisanalysisprovidetheconver-gencepropertyoftheenergychangeratio.Itleadstotheregularizationparameterwhichbalancequalityenhancementandprimitivecomponentspreservation.Also,theadaptiveregularizationimprovethepairmatchingaccuracyinlearning-basedsuper-resolution.Theirexperimentalresultsshowedthattheproposedmethodcanenhancethevisualqualityofthedegradedwebimagesandvideos.Shan,Qi,etal.proposedanupsamplingmethodforimageandvideoresolutionenhance-mentthatpreservetheessentialstructuralinformation[46].Theirproposedfeedback-controlframeworkrecoversthehighfrequencydetailswithoutadditionallocalstructureconstraints.Theyarguethattheproposedmethodisindependentofthequalityandnumberofthese-lectedexamples.Theirexperimentalresultsshowedthattheproposedmethodcanachievehighqualityimagesenhancementwithoutobservableartifacts.Alsotheyarguethatthemethodcanextendstovideoupsamplingwhilemaintainingthetemporalcoherence.1.6SummaryofcontributionsThecontributionsmadeinthisthesisaresummarizedasfollows:1.DevelopingaProgressiveCanonical-decompositionParallel-factor(PCP)tensor-decompositionforrepresentingandcodingvisualdataensemblestly.2.Developinganadaptivetreepartitioningalgorithmforsubdividinganinputtensorintoasetofsmallersizeblocks.Forthreeandfourdimensionaltensors,ittranslatestooctreeandhextreerespectively.Forndimensionaltensorsittranslatesto2n-ary12tree.3.FormulatingtheproblemoftheglobaloptimalnumberofPCPersfortheblocksofavisualdatatensorasanoptimizationproblem.4.Developingagreedysolutiontosolvetheaboveoptimizationproblem.5.Developingacompletecodingframework,basedontheproposedPCPtensordecom-position.6.Applyingtheproposedtensorcodingframeworkonthreetypesofdatasetswhichare:hyperspectral/multispectralimages,bio-metricimages,andlowmotionvideos.7.Developinganexamplebasedsuper-resolutionframeworktoapproximatethemissinghighfrequencydata.8.Employingtheproposedsuper-resolutionframework,whichwasdevelopedwithinGoogle'sVP9scalablevideocodingsoftware,inaninconsistentscalablevideostreamingsce-nario.1.7ThesisorganizationThethesisisorganizedintwomainparts.Inthepart,weproposeatensorcodingframeworkforrepresentationandcodingofvisualdataensembles.Inthesecondpartofthethesis,anexamplebasedsuper-resolutionalgorithmisproposedforenhancingthequalityofscalablevideostreamingwhensomeoftheenhancementlayersaredropped.Theremainingofthethesisisorganizedasfollows:13Inchapter2,asummeryofCPtensordecompositionispresented.Nextwetheproblemandproposeaprogressivetensordecomposition.Laterinthechapterwetheproblemoftheoptimalnumberofrank-onetensorsforallthesubblocksasanoptimizationproblemandproposeagreedysolutionforit.Thetheoriesarepresentedforthreedimensionaltensorsforillustratingpurpose.Theresultareextendedforthegeneralndimensionaltensorsafterward.Inchapter3,thetmodulesofthetensorcodingframeworkarepresented.Auniformandadaptivetreepartitioningmethodsarediscussed.Furthermoredecom-posedvectorsarrangementandcodingareexplainedindetailsalongwithresidualcodingmodule.Wealsopresentthemainpropertiesofthetensorcodingframework.Inchapter4threentapplicationsoftheproposedtensorcodingframeworkarepresented.Foreachapplication,wecompareourexperimentalresultswithsomeofthestandardcodingmethodsusedwithintheapplication.Chapter5consistofthesecondpartofthisthesis.TheISVstreamingproblemisunderwhichsomeoftheenhancementlayersofascalablevideoaredroppedduetopoornetworkquality.Laterinthechapter,anexamplebasedsuper-resolutionalgorithmisproposedtoreconstructthemissinghighfrequencydataofthevideo.Finally,theexperimentalresultsareshownandcomparedwithsimpleinterpolationmethods.Inchapter6wediscusstheconclusionsofthetwomainproposedframeworksinthisthesis.14Chapter2TensordecompositionforvisualdataInthischapterabriefintroductiononCPtensordecompositionispresentedbeforewediscussthedetailsoftheproposedtensordecomposition.Ateachsection,wedevelopandillustratethetheoriesandtheresultsforthethreedimensionaltensors.Then,weextendtheresultsforageneralcaseofthendimensionaltensors.2.1CPdecompositionCPdecomposesa3Dtensor˜2Rv1v2v3ontoanumberofrank-onetensors,eachofwhichcanbewrittenasanouterproductofthreevectors[1].Theoriginaltensorisapproximatedbysummationoftheserank-onetensorsasshownineq.(2.1).^˜=RXr=1ra(1)ra(2)ra(3)r(2.1)Whereisanouterproduct,andrisanormalizationfactorsuchthattomaintainan`2unitnormforthevectorsa(d)r,d2f1;2;3g[1].Hence,thetensor˜isapproximatedusingalinearcombinationofrank-onetensorsa(1)ra(2)ra(3)r;andtherankparameterRisthenumberofrank-onetensorsusedtoapproximate˜.Figure2.1showsthereconstructionofathreedimensionaltensorfromasetofrank-onetensors.Thevectorsa(d)rcanbearrangedascolumnvectorsofacorrespondingsetofmatrices15^˜=1A(1)1A(3)1A(2)1+:::+A(1)RA(3)RA(2)RFigure2.1:AthreedimensionaltensorreconstructionfromasetofRrank-onetensors.Each3Drankonetensorisanouterproductofthreevectors.Thereconstructedtensorisalinearcombinationoftheserankonetensors.(i.e.A(d)whered=1;2;3).Forexample,A(1)=[a(1)1a(1)2:::a(1)R]isav1Rmatrix.Ingeneral,A(d)2RvdR.Thesematricescanbefoundusingeq.(2.2).A(d)=argminA(d)X(d)A(d)A(d1)A(d2)TF(2.2)Where,isKhatri-Raoproduct,d2f1;2;3g,d12f1;2;3gfdg,andd22f1;2;3gfd;d1g.X(d)isamatrixthatresultsfromunfoldingthetensor˜withrespecttothedthdimension.Forexample,X(1)2Rv1(v2v3)isamatrixthatresultsfromunfoldingtheoriginaltensor˜withrespecttothedimension(i.e.v1).Similarly,X(2)andX(3)aretheunfoldedoriginaltensorswithrespecttothesecond(v2)andthird(v3)dimensions[1],respectively.ForagivenrankparameterR,theAlternativeLeastSquare(ALS)[7]approachcanbeusedtosolveforthesetofmatricesineq.(2.2).ItsolvesforA(1)byA(2)andA(3)andsimilarlyforA(2)andA(3)asshownin(2.3).A(d)=X(d)Z(d)TZ(d)TZ(d)1(2.3)WhereZ(d)=A(d1)A(d2)and,asbefore,d2f1;2;3g,d12f1;2;3gfdg,andd2216f1;2;3gfd;d1g.Ann-dimensionaltensor˜2Rv1:::vnisdecomposedbyCPontoasetofofrank-onetensors.Anndimensionalrank-onetensorisequaltoouterproductofnvectors[1].Theoriginaltensorisapproximatedbysummationoftheserank-onetensorsasshownineq.(2.4).^˜=RXr=1ra(1)r:::a(n)r(2.4)Thevectorsa(d)rcanbearrangedascolumnvectorsofacorrespondingsetofmatricesA(d)2RvdRwhered=1;2;:::;nandA(d)=[a(d)1a(d)2:::a(d)R].Findingthesematricescanbeformulatedinanoptimizationproblemasshownineq.(2.5).A(d)=argminA(d)X(d)A(d)A(1):::A(d1)A(d+1):::A(N)TF(2.5)Where,isKhatri-Raoproduct,d=1;2;:::;n.X(1)2Rvd(v1v3:::vd1vd+1:::vn)istheunfoldedtensor˜withrespecttothedthdimension.ForagivenrankparameterR,theALSapproachcansolveforthesetofmatricesineq.(2.5).ItsolvesforA(1)byA(2),A(3),:::,andA(n)andsimilarlyforA(2);:::;A(n)andsoonasshownineq.(2.6).A(d)=X(d)Z(d)TZ(d)TZ(d)1(2.6)WhereZ(d)=A(d1):::A(d1)A(d+1):::A(n);d=1;2;:::;n.172.2CPdecompositionforvisualdataAstraightforwardapproachfortensor-basedrepresentationofvisualdataistodirectlyem-ploytheCPdecompositionontoanoriginaldataset.However,suchstraightforwardap-proachdoesnotresultinantcodingmethod.TherearethreemaindisadvantagesinusingCPdecompositionforvisualdatacodingwhichare:1.Independentoftheformoftensordecompositionused,therankparameterRshouldnotbethroughoutthetensordecompositionoftheentirevisualdatatensor.Inparticular,thevalueofRdirectlytherateandoftheoriginaltensorrepresentationsinceitdeterminesthenumberofrank-onetensorsusedforthisrepresentation.Meanwhile,entpartsofthemultimediatensorhavetlevelsofspatialandtemporaldetails.Ontheotherhand,itisknownthatthetenorrankisanNP-completeproblem[47].Aprimitivewayoftherankistostartatoneandgraduallyincreasetherank,untiltheoptimalrankisfound.However,inthecaseofCPdecompositionthiswillresultinahightimecomplexity.2.CPdecompositionrequiresallthecomposingrank-onetensorsinordertoapproximatetheoriginalvisualdatatensor˜.Thisistrueeveniftheactualrankofthetensorissmallerthanthenumberofthecomposingrank-onetensors.Inotherwords,ifpartofthedecomposeddataaremissing,thereconstructedresultwillbedegradedcantly.Thiswillresultinanon-progressivereconstructioninwhichalltheersarerequiredpriortothereconstruction.3.CPdecompositionresultinasetofdecomposedvectorswithrealnumbervalues.Thereconstructionqualityishighlysensitivetosmallapproximationinthedecomposed18values.Astheresult,thereshouldbeenoughnumberofbytesallocatedforstoringthedecomposedvalues.Thiswilldecreasethestorageespeciallyconsideringthefactthatmostofthevisualdataare8-bitandrequiresonlyonebytetostoreeachpoint.Furthermore,becauseoftheprecisionsensibility,theCPdecomposedvaluesarenotnoiserobust.Thenoisydecomposedvalueswillresultinpoorqualityreconstruction.WeproposeaCP-baseddecompositionforvisualdatathatcanaddressthebeforemen-tionedshortcomingsoftheCPdecomposition.Thedetailsoftheproposeddecompositionispresentedinthenextsection.2.3ProgressiveCPdecompositionSimilartoCP,theapproximatedtensor(^˜)underPCPisasumofrank-onetensors.How-ever,thePCPdecompositionresultsintrank-onetensorsandcorrespondingvectorsfromwhatisgeneratedbyCP.Wealsouseatnormalizationasexplainedfurtherbelow.Toemphasizetheerencebetweenthetwoschemes,weexpressthePCPde-compositionusingtnotationsforrank-onetensorsandnormalizationparametersasexpressedineq.(2.7).^˜=RXr=1r(b(1)rb(2)rb(3)r)(2.7)UnderPCP,R2f1;2;:::;Rmaxg,whereRmaxisthemaximumpossiblenumberofrankonetensorsthatareavailableforapproximatingtheoriginaltensor.Itlimitsthetotalbitratebylimitingthenumberoferstobecoded.SimilartoCP,b(d)rcanbearrangedascolumnvectorsofacorrespondingsetofmatricesB(d)whered=1;2;3.UnderPCPthough,therearetwokeyces.19Theceisthattheersb(d)rarecomputedindividuallyasshownineq.(2.8).b(d)r=argminb(d)r X(d)r1Xk=0X0(d);k!b(d)rz(d)rTF(2.8)Wherez(d)r=b(d1)rb(d2)r;d2f1;2;3g,d12f1;2;3gfdg,andd22f1;2;3gfd;d1g.X0(d);kisthekthrank-oneunfolded-tensoroverdimensiond,andk2f0;1;2;:::;Rg.X0(d);0=0;X0(d);k=kb(d)kz(d)kT.Notethatthevectorproductb(d)rz(d)rTineq.(2.8)resultsinamatrixofsizevdvd1vd2,whichisthesizeoftheunfolded-tensormatrixX(d).ForagivenrankparameterRmax,wemodifytheALSapproachtosolvetheminimizationproblemineq.(2.8).SimilartoCP,web(2)randb(3)randsolveforb(1)r;andsimilarlyforb(2)randb(3)rasineq.(2.9).b(d)r= X(d)r1Xk=0X0(d);k!z(d)rTz(d)rTz(d)r1(2.9)Ateachiterationrwecalculatetheerrorr=MSE(˜^˜r),where^˜risobtainedfromeq.(2.7).ThePCPdecompositionisappliedinblock-wiseapproach.Theerrorsofall3D-blocksareusedinaprocedureoftheoptimalglobalsolutionaswillbediscussedlater.Thesolutionmayaddanotherrank-onetensortoapproximatetheresidual˜^˜rinthenextiteration.Thisapproximationresultsinaprogressivedecompositionof˜asshownin2.2.Figure2.3showsanexampleofuniformpartitioningofthetensorandthePCPdecom-positiononeachblock.Asmentionedbefore,thevalueofRforeachblockcouldbet20Figure2.2:PCPdecompositionprogressivereconstructionof˜.Attheiterationtheinputtensorisapproximatedwithonlyonerankonetensor.Thenateachiterationarankonetensorisaddedtoapproximatetheresidual.Figure2.3:Anexampleofuniformpartitioningofan3DtensorandthePCPdecompositiononeachblock.PCPallocatestvalueofRjforeachblockbasedontheamountoftheinformationinthatparticularblock.21basedonitsrank.Theproblemoftheoptimalnumberofrank-onetensorsforeach3D-blockisaddressedinthenextsection.ThesecondbetweenCPandtheproposedPCPisthefollowing.Asmentionedabove,underCP,therank-onetensorsarenormalizedbymaintainingan`2unit-normvec-tors.Thisiscapturedthroughrineq.(2.1).UnderPCP,weemployan`1norminstead.Thisleadstothefollowing:Thenormalizingparameterrcapturesthemaximummagnitudesoftheentriesofthecorrespondingvectorsb(d)r,d=1;2;3.Thevectorsb(d)rhavenormalizedvaluesbetween1and+1.Asweshowlater,theproposedPCPlendsitselftomoretcodingwhencomparedtotraditionalCP.PCPapproximatesanndimensionaltensor˜asalinearcombinationofasetofrankonetensorsasshownineq.(2.10).^˜=RXr=1r(b(1)r:::b(n)r)(2.10)WhereR2f1;2;:::;Rmaxg,whereRmaxisthemaximumpossiblenumberofrank-onetensorsthatcanbeused.b(d)rarecolumnvectorsofacorrespondingsetofmatricesB(d)whered=1;2;:::;n.ThePCPersb(d)rcanbecomputedasfollows:b(d)r=argminb(d)r X(d)r1Xk=0X0(d);k!b(d)rz(d)rTF(2.11)Wherez(d)r=b(1)r:::b(d1)rb(d+1)r:::b(n)r;d2f1;2;:::;ng.X0(d);kisthekthrank-oneunfolded-tensoroverdimensiond.X0(d);0=0;X0(d);k=kb(d)kz(d)kT.The22vectorproductb(d)rz(d)rTineq.(2.11)resultsinamatrixofsizevdv1v2:::vd1vd+1:::vN,whichisthesizeoftheunfolded-tensormatrixX(d).ForagivenrankparameterRmax,ALSapproachcansolvetheminimizationproblemineq.(2.11).Web(2)r;b(3)r;:::;b(n)randsolveforb(1)r;andsimilarlyfortheotherersasshownineq.(2.12).b(d)r= X(d)r1Xk=0X0(d);k!z(d)rTz(d)rTz(d)r1(2.12)2.4TheRank-DistortionoptimizationproblemIntheproposedtensorcodingframework,a3Dvisualdatatensorispartitionedintoasetof3Dsub-tensorblocks.Blockjhassjelementswheresj=v1jv2jv3j.PCPdecomposesagiven3Dblock,whichisindexedbyj,ontoRjrank-onetensors,eachofwhichhasthreeers.ThetotalnumberofelementsinthePCPrank-onedecompositionfor3Dblockjiss0jwheres0j=Rj(v1j+v2j+v3j).AssumingthatweusethesameprecisionfortheoriginalvisualdatapixelsandfortheelementsofthePCPdecomposition(e.g.,eightbits/pixelandeightbits/elementinaner),thenusingtheeiersinsteadoftheoriginalblockwillresultinthecompactionratioshownineq.(??).sjs0j=v1jv2jv3jRjv1j+v2j+v3j(2.13)WewouldliketoincreasetheblocksizeandminimizethevalueofRjtohavelargercompactionratio.However,alargerblockpotentiallyhashigherrankandrequiresalargervalueofRjtobecodedwithacceptablequality.Thiswilldecreasethecompactionratio.23Oneoptionistohavethecompactionratiolargerthansomeregularizationparameter>1.ThisleadstoanupperboundforRjthatkeepsthecompactionratiolargerthanasshownineq.(2.14).Rj<1v1v2v3v1+v2+v3(2.14)Weemploytheinequalityineq.(2.14)asaconstraintforouroptimizationproblem.Anotherconstraintisrelatedtothereconstructionerror.Weusetheaverageerrorconstraintshownineq.(2.15)forreconstructingtheoriginaltensor.1NNXj=1˜jRjXi=1b(1)i;jb(2)i;jb(3)i;jFmax(2.15)ForagivendatasetwithN3Dtensorblocks,thegoalistotheglobaloptimumR,whereRisavectorofdimensionN.EachentryofR=(R1;R2;:::;RN)correspondstothenumberofrank-onetensorswhichareusedtoreconstructa3D-blockofthedataset.Weformulatetherank-distortionoptimizationproblemtotheglobaloptimumRasineq.(2.16).min0@NXj=1Rj1As:t:1NNXj=1˜jRjXi=1b(1)i;jb(2)i;jb(3)i;jFmaxNXj=1Rj<0@1NXj=1v1jv2jv3jv1j+v2j+v3j1A,Rmax(2.16)Wheremaxistheaverage,overallacceptableerror.Thesecondinequalityineq.(2.16)capturesanupperboundforthetotalnumberofersthatcanbeused.NotethatIf24alltheblockshavethesamesize,Rmaxcanbeto((v1v2v3)N)=((v1+v2+v3)).Anndimensionalblockjhassjelementswheresj=v1jv2j:::vnj.PCPdecomposesthisblockontoRjrank-onetensors,eachofwhichhasners.ThetotalnumberofelementsinthePCPrank-onedecompositionforblock(j)iss0jwheres0j=Rj(v1j+v2j+:::+vnj).Usingtheeigenersinsteadoftheoriginalblockwillresultinthefollowingcompactionratiosj=s0j=v1jv2j:::vnj=Rjv1j+v2j+:::+vnj).TheupperboundforRjthatkeepsthecompactionratiolargerthanisRj<1v1jv2j:::vnj=v1j+v2j+:::+vnj.Foranndimensionaltensor,weusetheaverageerrorconstraintshownineq.(2.17)forreconstructingtheoriginaltensor.1NNXj=1˜jRjXi=1b(1)i;jb(2)i;j:::b(n)i;jFmax(2.17)ForagivenndimensionaltensorwithNndimensionalsub-tensorblocks,thegoalistotheglobaloptimumvectorR,whereRisavectorofdimensionN.EachentryofR=(R1;R2;:::;RN)correspondstothenumberofrank-onetensorswhichareusedtoreconstructanndimensionalblockofthedataset.Therank-distortionoptimizationproblemtotheglobaloptimumRisasshownineq.(2.18).min0@NXj=1Rj1As:t:1NNXj=1˜jRjXi=1b(1)i;jb(2)i;j:::b(n)i;jFmaxNXj=1Rj<0@1NXj=1v1jv2j:::vnjv1j+v2j+:::+vnj1A,Rmax(2.18)Asmentionedearlierinthecaseofa3Dtensor,maxrepresentstheaverageoverall25acceptableerror.Thesecondinequalityistheupperboundforthetotalnumberofersthatcanbeused.Ifthetensorispartitioneduniformlytoasetofequalsizeblocks,Rmaxcanbeto((v1v2:::vn)N)=((v1+v2+:::+vn)).AsolutiontothisoptimizationproblemcanbefoundbysearchingfortheoptimumRjwhichtheconstraints.ThesearchisdonebystartingfromRj=1;j=1;:::;NandincreasingRjofblockjthatmeetsacertaincriteriongraduallyuntiltheconstraintsareThedetailsarepresentedinthenextsection.2.5Rank-DistortionoptimizationproblemsolutionAgreedyalgorithmisdevelopedinthissectiontosolveeq.(2.16).Foran3DinputtensorthathasbeenpartitionedtoN3Dtensorblocks,thealgorithmstartsinitiallybyR=!1.Thisinitializationisalongwiththefactthateach3Dtensorblockshouldberepresentedatleastwithonerank-onetensor.Furthermore,EjisasblockjerrordecrementifRjincreasedbyoneasshownineq.(2.19).Ej=j;Rjj;Rj+1(2.19)Wherej;RjisthereconstructionerrorwhenRjrankonetensorsareusedinblockjreconstruction.InitiallyEj=j;1j;2forj=1;2;:::;N.IterativelyweblockjthathasthemaximumEjandincreaseitscorrespondingRjbyone.Thisgreedychoiceprovidesthelargestpossibleerrorreductionateachiteration.AfterRjisincrementedforblockj,theinequalitiesarechecked.Iftheinequalityisorthesecondinequalityisnotthealgorithmwillbeterminated.ThePCPtensordecompositionalgorithmfor3Dtensorsisshowninalgorithm1.26Algorithm13DtensordecompositionwithRank-DistortionOptimizationInput:Asetof3Dtensorblocks(i.e.˜j;j=1;:::;N.),andOutput:Asetoferstorepresenttheinputtensor.R=!1Findb(1)r;j;b(2)r;j;andb(3)r;jforr=1;2andj=1:::Nfromeq.(2.9).j;r=˜jPri=1b(1)i;jb(2)i;jb(3)i;jFforr=1;2andj=1:::NdoEj=j;1j;2:forj=1:::Nendforwhileinequalityineq.(2.16)isnotandthesecondinequalityineq.(2.16)isdoj=argmaxjEjr=Rj+1Findb(1)r;j;b(2)r;j;b(3)r;jfromeq.(2.9)j;r=˜jPri=1b(1)i;jb(2)i;jb(3)i;jFj;r+1=˜jPr+1i=1b(1)i;jb(2)i;jb(3)i;jFEj=j;r+1j;rRj=rendwhile27Foranndimensionaltensor,theoptimizationproblemshownineq.(2.18)canbesolvedwiththegreedyalgorithmshowninalgorithm2.Similartothealgorithmfora3Dtensor,thealgorithmstartsinitiallybyR=!1.ItiterativelyblockjthathasthemaximumEjandincreaseitscorrespondingRjbyone.Thetimecomplexityofcalculatingtheerrordecrementsateachiterationcanbereducedbystoringtheminavector.ThevectorEstoresthevaluesEjforj=1;2;:::;N.Ateachiteration,onlythevalueoftheentrypointjneedstobeupdated.28Algorithm2ndimensionaltensordecompositionwithRank-DistortionOptimizationInput:Asetofndimensionaltensorblocks(i.e.˜j;j=1;:::;N.),andOutput:Asetoferstorepresenttheinputtensor.R=!1Findb(1)r;j;b(2)r;j;:::;b(n)r;jforr=1;2andj=1:::Nfromeq.(2.12).j;r=˜jPri=1b(1)i;jb(2)i;j:::b(n)i;jFforr=1;2andj=1:::NdoEj=j;1j;2:forj=1:::Nendforwhileinequalityineq.(2.18)isnotandthesecondinequalityineq.(2.18)isdoj=argmaxjEjr=Rj+1Findb(1)r;j;b(2)r;j;:::;b(n)r;jfromeq.(2.12)j;r=˜jPri=1b(1)i;jb(2)i;j:::b(n)i;jFj;r+1=˜jPr+1i=1b(1)i;jb(2)i;j:::b(n)i;jFEj=j;r+1j;rRj=rendwhile29Chapter3TensorcodingframeworkPCPisthecoretransformusedinthetensorcodingframework.Othertasksoftheframe-workarehandledinvariousmodules.Amongthistasksaretensorpartitioning,ersarrangementsandcoding,headerdatamanagement,etc.Figure3.1showsthediagramofthetensorcodingframeworkwithitsvariousmodules.Thedetailsofthesemodulesarepresentedinthischapter.3.1TensorpartitioningThestepofthetensorcodingframeworkistheinputtensorpartitioning.Ithelpstobalancetherateintheoptimizationproblemineq.(2.2)andeq.(2.5).Italsobalancethecomplexitybasedontheblocksize.Weemployedtwotypesofpartitioning:Uniformpartitioning:theinputtensorisdividedintoasetofequalsizeblocks.Theblockshavethesamedimensionastheinputtensor.Adaptivetreepartitioning:initiallytheinputtensorispartitionedintoasetofequalsizeblocks,thenforeachblockarecursivealgorithmisemployedtosubdivideitifrequired.Thedecisionofwhethertosubdivideablockornotismadebasedonacriteria.Atreestructurerepresentsthepartitioningstructure.For3Dand4Dinputtensors,thepartitioningcanberepresentedbyoctreeandhextreecorrespondingly.Ahigherdimensiontensorpartitioningcanberepresentedbyan2n-arytreewherenis30Inputtensor˜TensrpartitioningBlock-wisePCPB(1)B(2)B(3)HeaderdataEntropycodingInitialquantization2DimagecompressionCompressedoutputReconstruct^˜,˜r=˜^˜Compress˜rResidualcodingFigure3.1:Tensorcodingframeworkforvisualdatacodingandrepresentation.Theframe-workconsistofvariousmodulesthatoperateaterentstages.Amongthesemodulesaretensorpartitioning,decomposition,anderscoding.Italsoshowstheresidualcodingprocess.thetensordimension.Similartotheuniformpartitioning,eachblockhasthesamedimensionastheinputtensor.Thedetailsofthealgorithmwillbediscussedlater.3.1.1UniformpartitioningUniformpartitioningdividestheinputtensorintoasetofequalsizeblocks.Intuitively,wewouldliketoincreasetheblocksizetohavealargercompactionratio.However,increasingtheblocksizemayincreasetherequirednumberofrank-onetensorstocodeit.Supposea3Dregioncoveredbyablockofsizev1v2v3requiresRrank-onetensorstobecoded.Also,ifthesameregioncoveredbyeightblocksofsizev12v22v32requiresR0rank-onetensorstobecoded.HereR0isthetotalnumberofrank-onetensorsforalltheeight3Dblocks.Thecompactionratioforbothscenariosisasfollows,respectively:C=v1v2v3R(v1+v2+v3)andC0=14v1v2v3R0(v1+v2+v3).ThelargerblockresultsinbettercompressionwhenC>C0andconsequentlyR<4R0.ThisimpliesthatifitispossibletocodearegionusingthelargeblocksizewhiletheerrorisnotlargerthanwhenitiscodedwiththesmallblocksizeandifR<4R0,thelargeblocksizewouldresultinhighercompressionthanthe31(a)(b)Figure3.2:PSNRvsbitrateplotsof(a)Silentand(b)ContainerCIFvideosemployingthreetblocksizes.LargerblocksizesresultinhigherPSNRatlowerbitrateshoweveratsomebitratepointtheycrossover.smallone.Moregenerally,forablocksizeratiod(i.e.d=v1=v01=v2=v02=v3=v03),ifR<d2R0andthereconstructionerrorisrelativelyclose;then,thelargerblockwouldbeabetterchoiceintermsofcoding.Figure3.2showsPSNRplotsofSilentandContainerCIFvideos,encodedwiththreeblocksizeswhichare88180,1616180,and3232180.TheplotshowsthatlargerblocksizesresultinhigherPSNRatlowbitrates,howevertheycrossoveratsomebitratepoint.32(a)(b)Figure3.3:PSNRplotsof(a)Silentand(b)ContainerCIFvideosemployingblocksofttimedimensionsize.Theplotsshowthatifthevideohashighredundancyacrosstime,thenlargerblocksizeswillresultinhigherPSNR.Inanotherexperimentthesizeofthethirddimensionisvariedwhilethespatialsizeis1616.Theblocksizeoverthethirddimensionofsize180,90,60,45,and36wereevaluated.Figure3.3showsthePSNRresultsforContainerandSilentvideo.Theresultsshowwhenthevideohaslargenumberofblocksthatdonotchangewithtime,expandingtheblockintimedimensionwillresultintakingadvantageoftheredundancyandincreasesthePSNR.InthecaseofContainervideothathaslinearandtexturemovement;atlowbitrates,thelarger33blocksizesresultsinhigherPSNRthansmallerblocksizes.Howeveratsomebitratepoints,theycrossover.UsingvariableblocksizefortregionsofavideohastheadvantageofobtainingthehighestpossiblePSNR.Similarblocksizeanalysiscanbedoneforanndimensionaltensor.Assumingthatanndimensionalregioncoveredbyablockofsizev1v2:::vnrequiresRrank-onetensorstobecoded,ifthesameregioncoveredbydnblocksofsizev1dv2d:::vndrequiresR0rank-onetensorstobecodedwhereR0isthetotalnumberofrank-onetensorsforallthednndimensionalblocks.Thecompactionratioforbothscenariosisasfollows,respectively:C=v1v2:::vnR(v1+v2+:::+vn)andC0=1d(n1)v1v2:::vnR0(v1+v2+:::+vn).ThelargerblockresultsinbettercompressionwhenC>C0andconsequentlyR<d(n1)R0.3.1.2AdaptivetreepartitioningAdaptivetreesubdividetheinputtensorintoasetofvariablesizesub-blocks.Inthecaseofa3Dtensor,ittranslatetooctree,for4Dtensorittranslatetohextreeandingeneralforanndimensionaltensorittranslateto2n-arytree.Fortheillustrationpurposethepartitioningalgorithmisdevelopedforoctreeandtheresultisextendedafterward.Octreeisthe3Danalogousofquadtreeinwhicha3Dblockisrecursivelysubdividedintoeightadjacentdisjoint3Dsub-blocks[48].Figure3.4illustratesanexample3Dblocksubdivisionanditscorrespondingoctreerepresentation.Theoctreedividesa2v12v22v3blockintoav1v(l0)1+1levelstree.Where2v(l0)12v(l0)22v(l0)3isthesmallestpossibleblock.Dependingontheapplication,itisdesirabletohavetheyofallocatingtsizealongeachdimensions.Forexample,forahyperspectralimagestensor,sincethenatureofthethirddimensionistthanthespatialdimensions,wewouldliketoallocatetsizealongthethirddimension.34(a)Levell=l0+3Levell=l0+2Levell=l0+1Levell=l0Code:1j10000000j01000000j00000000(b)Figure3.4:(a)Anexampleof3Dblockrecursivesubdivision,and(b)itscorrespondingoctreerepresentation.Theleafnodeindicatenosubdivisionwhilethebranchingnodesubdividedandithaseightchildren.Aleafisrepresentedby0andabranchingnodeisrepresentedby1.Theoctreerepresentationcodeisalsoshown.Howeverthetreelevelissimilarinalldirections,v1v(l0)1+1=v2v(l0)2+1=v3v(l0)3+1.Theblocksatlevellhavethesize2v(l)12v(l)22v(l)3where06v(l0)d6v(l)d6vd;d=1;2;3.Eachnodecanbealeaforitcanbedividedtoeight2(v(l)11)2(v(l)21)2(v(l)31)sub-blocks.Similartoquadtree,theoctreecanberepresentedwithaseriesofbitsinwhich0indicatesleafand1indicatesbranchingnode.Thetopdownapproachisusedforsubdividingtheblocks.Itstartswithamaximumsizeblockanddivideitifacriteriaismet.Theprocedureisappliedtotheeightsub-blocksrecursivelyuntilthesub-blocksdonotrequirefurtherdivisionortheyreachthemaximumtreelevell0.Sincewearetryingtoapproximateatensorblockbyalinearcombinationofrank-onetensors,anaturalchoicefordivisioncriteriaistherank.However,asmentionederalier,ingtensorrankisanNP-completeproblem.Asanalternative,weighteddirectionalvarianceisusedasthecoreofthedecisioncriteria.Foragiventensorblock˜2R(2v12v22v3),theaveragevariancealongeachdimensionisasineq.(3.1).sd=KXk=0VAR(Xjk(d));d=1;2;3(3.1)35WhereX(d)isamatrixthatresultsfromunfoldingthetensor˜withrespecttothedthdimensionandKisthenumberofthecolumns.Theweighteddirectionalvarianceisasineq.(3.2).=3Xd=1wdsd(3.2)WherewdisthedimensionweightandP3d=1wd=1.wdregulatesthecontributionofeachdirectioninthedecision.Foreachblockwecalculatetheaveragevarianceatlevell(i.e.l),thenwesubdivideitintoeightsub-blocksandcalculatetheaveragevarianceforeachofthem(i.e.(l1)j;j=1;:::;8).Ifsumoftheaveragevarianceofthesub-blocksissmallerthantheaveragevarianceoftheblock,thentheblockwillbedividedintoeightsub-blocks.Ingeneralarelaxedcriteriaisusedasineq.(3.3).n8Xj=1n1j<˝ˆ(3.3)Where˝isathresholdandˆ=4Rmax=N.Thevalueoftheˆisderivedfromtheblockanalysisinsection3.1.1.NotethattheratioRmax=Nistheaverageavailablerank-onetensorsperblock.Asmentionedearlier,whentheavailablerank-onetensorsperblockissmall,largerblockswillprovidebetterapproximationoftheinputdata.Theparameterˆwillenforcelessaggressiveblocksubdivisionatlowerratesandmoreaggressiveblocksubdivisionathigherrate.Iftheabsolutevalueofthetialaverageissmallerthan˝=ˆ,thensubdivisionisnotrequired.Otherwise,theblockisdividedintoeightsub-blocksandtheprocedureisrepeatedrecursivelyforeachofthem.Figure3.5showsanexampleofthehextreeanditscorrespondingcode.Figure3.6showsanexmpleofthegeneral2n-arytreeanditscorrespondingcode.Asmentionedbefore,36Levell=l0+3Levell=l0+2Levell=l0+1Levell=l0Code:1j0000100000000000j0000010000000000j0000000000000000Figure3.5:Anexamplethreelevelshextreestructurewithitscorrespondingcode.Eachbranchingnodehas16childrennodeswhichcanbeeitheraleaforabranchingnodeaswell.Levell=l0+3Levell=l0+2Levell=l0+1Levell=l0Code:1j0000100000:::000j0000010000:::000j0000000000:::000:::::::::Figure3.6:Anexamplethreelevels2n-arytreestructurewithitscorrespondingcode.Eachbranchingnodehas2nchildrennodeswhichcanbeeitheraleaforabranchingnodeaswellDependingontheapplicationanditsassociateddata,anndimensionalinputtensorcanhavetnaturealongeachdirection.Therefore,theadaptivetreepartitioningshouldbeabletohandleablockwithtsizealongeachdirection.Weusea2n-arytreeforpartitioninganndimensionaltensor.Itdividesa2v12v2:::2vnblockintoav1v(l0)1+1levelstree.Althoughtheblocksizemaynotbeequalalongthedimensions,weassumethatthetreelevelsareequalinalldirections,v1v(l0)1+1=v2v(l0)2+1=:::=vnv(l0)n+1.Where2v(l0)12v(l0)2:::2v(l0)nisthesmallestpossibleblock.Theblocksatlevellhavethesize2v(l)12v(l)2:::2v(l)n.Fordimensiond,06v(l0)d6v(l)d6vd;d=1;2;:::;n.Eachnodecanbealeaforitcanbedividedto2nchildsub-blockswithasizeof2(v(l)11)2(v(l)21):::2(v(l)n1).Thedividingprocedureisappliedtothe2nsub-blocksrecursivelyuntilthesub-blocks37donotrequirefurtherdivisionortheyreachthemaximumtreelevell0.Foragiventensorblock˜2R(2v12v2:::2vn),theaveragevariancealongeachdimensionisasineq.(3.4).sd=KXk=0VAR(Xk(d));d=1;2;:::;n(3.4)WhereX(d)isamatrixthatresultsfromunfoldingthetensor˜withrespecttothedthdimensionandKisthenumberofthecolumns.Theweighteddirectionalvarianceisasineq.(3.5).=nXd=1wdsd(3.5)WherePnd=1wd=1.Foreachblockwecalculatetheaveragevarianceatlevell(i.e.l),thenwesubdivideitinto2nsub-blocksandcalculatetheaveragevarianceforeachofthem(i.e.(l1)j;j=1;2;:::;2n).Ifsumoftheaveragevarianceofthesub-blocksissmallerthantheaveragevarianceoftheblock,thentheblockswillbedividedinto2nsub-blocks.Ingeneralarelaxedcriteriaisusedasshownineq.(3.5).l2nXj=1l1j<˝ˆ(3.6)Whereˆ=d(n1)Rmax=Nand˝isathreshold.Iftheabsolutevalueoftheerentialaverageissmallerthan˝=ˆ,thensubdivisionisnotrequired.Otherwise,theblockisdividedinto2nsub-blocksandtheprocedureisrepeatedrecursivelyforeachofthem.Similartooctree,the2n-arytreecanberepresentedwithaseriesofbits.However,asthedimensiongrowsnumberofthebitsgrowsexponentially.Arithmeticcodingandzero38trailterminationcodecanbeusedtoreducethesizeoftheencodedtree.3.2ersarrangementandcodingOncetheersareevaluatedforalltheblocksofatensor,wecanarrangethemontothecolumnsofa2DmatrixB.Thus,wecanapplya2DcompressionschemetothismatrixB,treatingitasanimage.Subsequently,wecandecodeitscolumns,whichrepresenttheersb(d)r,toreconstructtheoriginaltensor.Twoimportantquestionsneedtobeanswered:1.Howshouldtheersb(d)rbearrangedwithinthematrixB?2.Howmuchcorrelationdoesexistamongtheseers?RecallthatunderPCPeachblockhasitsownrank,andhencewedenoteRjtorepresentthenumberofrank-onetensorsusedforapproximatingblockj.Consequently,thetotalnumberofrank-onetensorsusedforapproximatingthewholetenoris:PNj=1Rj,whereNisthetotalnumberofblocks.Each3Drank-onetensorrequiresthreeers:(b(1)r;jb(2)r;jb(3)r;j),forr=1;:::Rjandj=1;:::N;thenwehaveatotalof3PNj=1Rjerstocode.Therearemanyoptionsforarrangingtheseersb(d)r;jontothematrixBthatweplantocompressasa2Dimage.Here,weemploythearrangementshownintheexampleofFigure3.7.Inthisexample,wegeneratedtheersof180framesoftheContainerCIFvideo.Wedividedthevideointo16161803Dblocks,whichresultsinto396tensorblocks.Forclarityandease-of-illustrationpurposes,weareonlyshowingtheersforthe39b(1)r:b(2)r:rb(3)r:306001020304050Rj:jr=1r=2;:::;RmaxFigure3.7:ersofthePCPtensordecompositionandtherankvaluesRfor50blocksoftheContainerCIFvideowith180frames.Theshowsapossibleersarrangementforcodingandstorage.50blockschoseninaraster-scanorder.Allervaluesaremappedfromtheirnormalized[1;+1]rangeontothetraditional[0;255]pixelvalues.Asshowninthe,weemploythefollowingarrangement:Verticalarrangement:Theeigenersb(1)r;jareputatthetopofthe2Dimage;eacherisofheight16.Next,thesecondersb(2)r;j,alsowithheight16,areplacedbelowb(1)r;j.Thesetwogroupsoferscapturethe1616spatialinformationofthevideo-blocks.Meanwhile,thethirdbersb(3)r;jwithheight180areplacedbelow;andtheselatererscapturethetemporalinformationofthe3Dvideo-blocks.Horizontalarrangement:Moreimportantly,weseparatetheersassociatedwiththerank-onetensors(i.e.,forr=1)fromtherestofallothereigeerswithhigherrankindex(i.e.forr>1).Thisseparationisanalogoustotiating40between"DC"and"AC"cotsintraditionalimageandvideocoding.Theleftbrightareaintheimagesof3.7correspondstotheseers.Forhigherrankindices,r>1,wesimplyplacetheersaccordingtotheblockstheybelongtoinaraster-scanorder.Wehavealsoexperimentedwithotherhorizontalarrangementsforerswithr>1.Forexample,onecangroupeigenerswithr=2,followedbyoneswithr=3,andsoon.Weobservedlittleimprovementincodingwhileusingsucharrangement;meanwhileitincreasesthecomplexityduetotheneedofperformingmatrixpermutationsatboththeencodinganddecodingsides.Notethat,inadditiontotheers,wealsohavethenormalizationparameterr.Undertheproposedtensorcodingframework,weabsorbtheparametersr;jontothethirddirectionersb(3)r;j,asshownin3.7.Therearetwobforabsorbingtheseparametersontothebers.First,weeliminatetheneedforcodingtheseparametersseparately.Second,thismultiplicationprocessimprovesthecorrelationamongtheerswithinthe2Dimageaswediscussbelow.Itisimportanttonotethatforagiven3Dblock,thethreeers(b(1)r;b(2)r;b(3)r)areexpectedtobeuncorrelated.However,ifweconsidert3Dblocksofsimilarspatialandtemporalcharacteristics,thenweanticipatethattheersacrosssuchblockstobecorrelated.Figure3.8ashowsthecorrelationamongthecolumnsofmatrixAthatcorrespondtotraditionalCPfactoredvectors(a(1)r;j;a(2)r;j;a(3)r;j).Figure3.8bisthecorrelationamongthecolumnsofmatrixB,whicharethePCPers(b(1)r;j;b(2)r;j;b(3)r;j).Thebrightupper-leftregioncorrespondstothecorrelationamongtheersofeachblock.Theseparticularers,whichrepresenttheprincipleers,arehighlycorrelated.However,theyhavelowcorrelationwithmostoftheotherers41(a)(b)(c)(d)(e)(f)Figure3.8:Thecorrelationamong(a)matrixAcolumns(i.e.CPvectors);(b)matrixBcolumns(i.e.PCPers);Thecorrelationamong(c)matrixArows;(d)matrixBrows;(e)after(r;j)absorptionontoa(3)(r;j)vectors;and(f)after(r;j)absorptionontob(3)r.ThevideoisContainerCIF.42(darkerupperpanel).Asexpected,andsimilartotheoriginalCPdecomposition,PCPprovidesuncorrelatedvectorswithineachblock.Meanwhile,theentrieswithintheerscanbecorrelated.Inotherwords,ifweconsidertherowofmatrixBthenitwillbedesiredtohavethisrowcorrelatedwithotherrowswithinthesamematrix.Suchinercorrelationiscapturedbythecorrelationamongtherowsoftheermatrixshownin3.8c-3.8f.TheproposedPCPdecompositionprovideshigherinerscorrelationthanwhatcanbeachievedunderCP.AssumingRisknown,wedecomposedthevideousingbothCPandPCPwiththesameRtoobtainacomparablenumberoffactoredvectorsandeigeersinthisexperiment.Figure3.8cisthecorrelationamongtherowsofmatrixAand3.8disthecorrelationamongtherowsofmatrixB.From3.8cand3.8d,PCPprovideserswithhigherrowcorrelationthanthestandardCP.ThethreesquareregionsonthediagonalaretheintrercorrelationofB(1);B(2),andB(3)respectively.TheotherthreeregionsabovethediagonalistheinercorrelationofB(1)withB(2),B(1)withB(3),andB(2)withB(3).Figures3.8eand3.8fshowtheimpactofabsorbingthenormalizationparametersr;j(forCP)andr;j(forPCP)withinthecorrespondingeigeers.ThenextstepistocodetherankparametersRjforallblocks.Wesimplyarrangethesevaluesontoavectorandentropycodetheminalosslessmanner.Forahigherdimensioninputtensorwesimplyaddtheersatthebottomofthe2Dmatrix.Forexample,decomposinganndimensionalinputtensorwillresultinners.Basedonthepartitioningmethodwehavetwotsettings:1.Uniformpartitioning:assumingeachblockisofsizev1v2:::vn,thevectorthatstackalltheersofarank-onetensorwillbeofsizev1+v2+:::+vn.Sincealltheblocksareofthesamesizewecanarrangethisvectorsascolumnsofthe2Dmatrix.432.Adaptivetreepartitioning:inthissettings,eachblockcanhaveatsize.How-everbasedonthetreestructureweknowthemaximumblocksizeandthetreelevel.Consequentlywecanobtaintheminimumblocksize.Foraminimumsizeblockwesimplyfollowthearrangementstepsofuniformpartitioning.Forlargerblocks,inordertomaintainconsistentcolumnsize,wesimplystorethecorrespondingeigen-ersasmultiplecolumns.Eachcolumnhasthesamesizeasthevectorofersoftheminimumsizeblock.Forexample,assumethesizeoftheminimumblockisv1v2:::vnandaparticularblockjhasasizeof2v12v2:::2vn.Theersvectoroftheblockjwillbeofsize2v1+2v2+:::+2vn,thereforwestorethisvectorastwovectorsofsizev1+v2+:::+vneachtobeconsistentwiththeminimumsizeblock.3.3ResidualcodingTheproposedframeworkisbasedonapproximatingatensorwithasetofrank-onetensors.Iftheoriginaltensorisoflow-rankwewouldbeabletoreconstructitexactly.However,ifthetensorisclosetofullrank,atsomepointnomatterhowmanyrank-onetensorsweadd,theapproximationwillnotconvergetotheoriginalone.Theexactornearlosslessreconstructionisimportantforsomeapplications.Inordertopresentacompletecodingframeworkthatwouldbeabletocodethevisualdatatensorswithhighquality(nearlossless),weemployaresidualcodingprocessasshownin3.1.Afterapproximatingavisualdatatensor˜withtheproposedtensorcodingframework,weobtaintheresidual˜r=˜^˜where^˜istheapproximationtensor.SincePCPcapturedtheexistingcorrelationintheinputtensor,wecodeeachresidual44sliceseparately.Thiswouldalsomaintaintherandomaccessproperty.Notethat,theseslicescanbealonganydimensionaldirectiondependingonthetypeoftherandomaccessrequiredinaparticularapplication.Forexample,imageensembledecodingrequiresrandomaccessalongthethirddimension.Consequently,theresidualslicesarecodedseparatelyalongthethirddimension.Whiletherateofcodingtheresidualsliceswouldnotbeashighascodingtheoriginalimages,thescalabilityoftheproposedmethodprovidesyfortapplicationstoreconstructthedatabasedontheirrequirement.InthisthesisweusedtheAmplitudeandGroupPartitioning(AGP)imagecodingmethod[49]tocodetheresidual.3.4TensorcodingpropertiesTheproposedtensorcodingframeworkhassomedesirableproperties.Theseproperties,individuallyorcombined,resultinadvantagesoverstandardcompressionmethodsinsomeapplications.InthissectionRandomaccess,progressivereconstruction,andtimecomplexitywillbediscussed.3.4.1RandomaccessTensorcodinghastheadvantageofrandomaccess,whichisnotthecaseforthemotionbasedcodingmethodsandmany3Dtransformbasedcodingapproaches.ThemotionbasedcodingmethodscodesaGOPusingasinglekeyframeandtherestarepredictedframes.Inordertodecodeanypredictedframe,thedecoderneedtohaveallofthepreviousframesinthesameGOP.The3Dtransformbasedcodingmethods,takeadvantageoftheexistingcorrelationalongallthedimensions.Howevertheyrequireallthetransformdomaincotsto45reconstructtheoriginaltensor.Inthecaseoftensorcoding,toreconstructaslicefroma3Dtensor,thedecoderrequiresthetwoersandavalueofthethirdertodecodeasliceindependently.Ingeneral,anyslicecanbedecodedasshownineq.(3.7).Slicei;j=RjXr=1(B(1)j;rB(2)j;rB(3)i;j;r);j=1;:::;N(3.7)Wherejistheblockindex,B(1)j;randB(2)j;rarevectors,B(3)j;r;iisasinglevaluefromrowiofB(3).Thecolumnindicesareeitherobtainedfromtheoctreestructureinthecaseofadaptivetreepartitioning,orfromtheblocknumberinthecaseoftheuniformpartitioning.Thetwoerscanbethoughtofasbasis,whilethevaluesfromthethirderarethecots.Forthemoregeneralcaseofanndimensionaltensor,aparticularslicecanbedecodedasshownineq.(3.8).Slicei;i3;:::;i4=RjXr=1(B(1)j;rB(2)j;rB(3)i3;j;r:::B(n)in;j;r);j=1;:::;N(3.8)Therandomaccesspropertyisnotlimitedtoasliceoftheandseconddimensionandbasedontheapplicationasubsetoferscanbeselectedtoreconstructasliceinaparticulardimension.Forexample,inhyperspectralimages,avectorofvaluesacrossallbandsforaparticularpixelcalledpixelsignature.Itprovideavaluableinformationaboutthetypeoftheearthmaterialsorthevegetation.Whenahyperspectralimagesiscodedwithtensorcodingframework,apixelsignaturecanbereconstructedfromasetofbersasshownineq.(3.9).46Signaturei1;i2;j=RjXr=1(B(1)i1;j;rB(2)i2;j;rB(3)j;r);j=1;:::;N(3.9)Notethatthereconstructedsignatureisaonedimensionalvectorandjistheblockindex,B(1)i1;j;randB(2)i2;j;raresinglevaluesfrommatricesB(1)andB(2)correspondingly,andB(3)j;risavector.3.4.2ProgressivereconstructionanddecodingUnlikeCPdecompositionPCPfactorizesthetensorinaprogressivescheme.Inotherwords,ifonederivestheCPdecompositionusingagivenrankparametersR,thenalloftheRrank-onetensorsmustbeusedforreconstructingtheapproximatedtensor^˜;otherwise,thequalityofthereconstructedtensoriscantlydegraded.Thisistrueevenifthe3Dblockhasalowrank;allofthefactoredvectorsshouldbeusedinthereconstructiontogivereasonableresults.Ontheotherhand,PCPsimplyimprovesthequalityofthereconstructedtensor,whenincreasingthenumberofrank-onetensorsusedforreconstruction.Therefore,asubsetoftheerscanbeusedtoreconstructalowerqualityresult.Figure3.9showsaframefromthe"RedFlower"CIFvideoencodedbytheproposedtensorcodingframeworkwithatotalnumberofrank-onetensorsequalto6000andthendecodedusing(a)1000,(b)2000,(c)3000,and(d)4000rank-onetensors.Increasingnumberofrank-onetensors,resultingradualincrementofthevideodetails.3.4.3PCPtimecomplexityThemosttime-consumingoperationofthePCPdecompositionistheKhatri-Raoproductineq.(2.9).Forexampletob(1)rweneedtocalculatez(1)randX0(1);k.Theterm47(a)(b)(c)(d)Figure3.9:"RedFlower"CIFvideoencodedbytensorcodingwithatotalof4000rank-onetensors.Uniformpartitioningwasusedwithblocksizeof1616180.Thevideodecodedwith(a)1000(93Kbps30.43dB),(b)2000(205Kbps35.76dB),(c)3000(320Kbps38.49dB),(d)4000(433Kbps40dB),rank-onetensors.isoforderO(v2v3)whilethesecondoneisoforderO(v1v2v3).Recallthatv1v2v3isthesizeofthe3Dtensorblock.Thetimecomplexityofallthreedecomposedersandallotherextraoperationscanbecapturedbyaconstantterm(ˆ).ThetotalcomplexityofcodingavisualdataensemblewithtensorcodingframeworkisOˆv1v2v3PNj=1RjwhereNisthenumberofblocks,andRjisthenumberofrank-onetensorsusedtoreconstruct48blockj.Notethattosolveforb(1)rweareusingALS,whichisaniterativeapproach.Thecomplexityofalltheiterationsiscapturedbyˆ.PCPreconstructsa3Dtensorasineq.((2.7)).Itconsistsofouterproductofdecom-posedersandthenadditionofrank-onetensors.Overalltherearev1v2v3PNj=1Rjmultiplicationsandv1v2v3PNj=1Rjadditions;whereNisthenumberofblocks.Hence,thecomplexityofthedecodingalgorithmisoforderO(2v1v2v3PNj=1Rj).Foranndimensionaltensor,thePCPreconstructionshownineq.(2.10)hasatimecomplexityofOˆv1v2:::vnPNj=1Rj.WhereNisthenumberoftheblocks.NotethatthistimecomplexityaccountsforthePCPdecompositiononlyanddespitetheusedtensorpartitioningapproach.Theadaptivetreepartitioningtimecomplexityshouldbeconsideredaspartoftheoveralltensorcodingcomplexity.49Chapter4TensorcodingapplicationsTheproposedtensorcodingframeworkisoptimizedforvisualdata,howeveritcanbeappliedtoanytypeofdata.Itisdesignedtobeabletorepresentandcodeinputtenorwithanydimensiontlyspecially3Dandabove.Inthisthesis,theframeworkisappliedtothreeapplicationswhichare1.Hyperspectralandmultispectralimages.Multipleexperimentshavebeendoneforboth3Dand4Dinputdatatensors.2.Biometricfaceimageensembleswhichare3Dtensors.3.Lowcomplexityvideocodinginwhichavideoistreatedasa3Dtensor.4.1HyperspectralimagecodingUnliketheconventionalimagingsystemsthatmeasuretheenergiesinthevisiblelightspectralbands,thehyperspectralimagingsystemmeasurestheenergiesinabroadrangeofspectralbands.Thenumberofspectralbandscanrangefrom8inLandsatdatasetsupto200inthemultispectraldatasets.Whilemostofthebandsdonotprovidevisualinformation,theycontainavitalscieninformationabouttheearthandatmosphere.Antsystemforrepresentationandcodingofhyperspectralimagesisessentialespeciallyconsideringthefactthattheamountofthistypeofimagesaregrowingrapidly.50Whileeachbandhasitscharacteristics,thereisahighamountofcorrelationamongthemthatcanbeexploitedforcompression.Various3D-waveletbasedcompressionmeth-odsareproposedtoexploitthiscorrelation[50{53].However,therandomaccesspropertyisnotpreservedinthesemethods.Fastrandomaccesspropertyisplayingakeyroleinprovidingtbrowsingexperience.Supposethatwewanttodownloadaspbandofahyperspectralimagesavailableonaserver.Underthe3D-waveletmethods,thewholecompresseddatashouldbeavailabletoreconstructtheoriginaldataandthenaccessthatparticularband.Dependingonthesizeoftheimage,networkquality,andtheserverband-obtainingthecompletecompresseddatacanbeinconvenient.Theproposedtensorrepresentationandcodingcanprovidearandomaccesswhiledeliv-eringabettercompressionthanthesingleimagecompressionmethods[54].Furthermore,theinheritedscalablecodingpropertyoftheproposedmethodcanprovidereconstructionwithvariablequality.Thescalabilitypropertycontributeintfunctionality.Forex-amplewecanusealowerqualityreconstructionforAlso,theproposedmethodcapableoffastdecodingwhichisakeycomponentofthetbrowsing.Theinheritedscalablecodingpropertyoftheproposedmethodcanprovidereconstructionwithvariablequality.Furthermore,withtheresidualcodingcapabilitythehighfrequencydatacanbereservedanddeliveredwheneverdesired.4.1.1ExperimentalresultsTheproposedtensorcodingframeworkwasemployedtocodeasetof3DhyperspectralimagesfromAVIRISdataset[55]andmultispectralimagesfromLandsatdataset[56].Alltheexperimentswereevaluatedatadesktopcomputerwith12GBofmemoryandanIntelCorei72600CPU(8MBCache,3.4GHz).51Figure4.1:IndianpinePSNRvsbpppbcomparisonamongTCwithentblocksizes,TCwithoctreeandJPEG2000.IntheexperimentwedecomposedtheIndianpinehyperspectralimagedatawithtnumberoferstolimittherateandconsequentlythestoragesize.TheIndianpinedatasetconsistsof200spectralbandsandthespatialresolutionis144144.Figure4.1showsthePSNRvsbitperpixelperband(bpppb)plot.TensorcodingresultswithtblocksizesandoctreeblockstructurearecomparedtotheJPEG2000.Weusedanoctreewiththreelevelsandthelargestblocksizeof4848200.Theweightsineq.(3.2)areequallydistributedandthethresholdineq.(3.3)issetas1%oftheparentblockvariance.Similartothediscussioninthesection3.1.1,Figure4.1showsthatforsmallerrate,thelargerblocksizesprovidebettercompressionatlowerbitrates.Howevertheycrossoveratsomepointandathigherbitratessmallerblocksizesprovidebettercompression.Ontheotherhand,octreedeliversaconsistentbettercompressionbychoosingavariableblocksizebasedontheregionandtheavailablebitrate.Acriticalillustrationforhowesuchdecompositioncanbeishowdoesitimpactthespectralofindividualphysicallocationsacrossbands.Thespectralisa52Figure4.2:Thespectralover200bandsofaparticularspatiallocationfromtheIndianpinedatashowninFigure4.3.Threereconstructedspectralbasedontheproposedframeworkattbitratesareshown.keypieceofinformationthatscientistsrelyontoanalyzethedata.ThespectraloftheIndianpineisshowninFigure4.2.Oursimulationresultsshowthatreconstructionwithtwoorderofmagnitudesofcompressionratioprovidesspectralthattracktheoriginaloneverycloselythereforeitcanbeusedinapplicationslikeandpatternrecognition.Thescalabilityoftheproposedtensorcodingmethodprovideayonthereconstructedsignaturequality.Howeverthereisatradebetweenthethereconstructedsignatureprecisionandthecompressionratio.AsimilarexperimentsweredoneforthyperspectralimagesfromAVIRISimagedatasets.Table4.1showsthebitratecomparisonbetweentensorcodingandJPEG2000ataparticularPSNRforthesehyperspectralimages.Theresultsshowtheadvantageoftensorcodinginexploitingthecorrelationoverastandard2Dcompressionmethod.Intencodingscenario,wesettheRmaxvalueto100and1000whichresultinaverageof1.39and6.95ersperblockrespectively.Furthermoretoachievenearloss-lesscompression,whencodedwithRmax=1000,weencodedeachresidualslice53Table4.1:bitratecomparisonbetweentensorcodingandJPEG2000forvarioushyperspec-tralimagesfromAVIRISdataset.ImageTensorcodingJPEG2000bitrate(bpppb)PSNR(dB)bitrate(bpppb)PSNR(dB)Cuprite0.2042.820.4142.83PaviaUniversity0.2051.900.5351.94Botswana0.2052.950.4252.94Salinas0.2066.170.9066.17Indianpines0.2055.290.6655.32betweenoriginalandreconstructedslices)usingAGPimagecoding[49].Figure4.3showsthereconstructionresults.NotethatforillustrationpurposeonlyRGBbandsareshown.Inadditiontothetandscalablerepresentationrangingfrommorethantwoordersofmagnitudetooneorderofmagnitudeincompressionratios(fornearlossless),thetimeforreconstructionrangesfrom0.6to1.35perone2Dslice(usingMatLab).Thisenablesreconstructionof100low-resolutionslicestomorethan40high-resolutionslicespersecond.ThedecodingprocesstimecomplexitycanbefurtherreducedthroughusingC/C++im-plementationwithparallelcomputingcapability.Inthisexperiment,forRmax=100,weobtainedacompressionratioequalto228andtheaveragedecodingtimeof0.6msec/slice.ForRmax=1000,thecompressionratiowas61.5andtheaveragedecodingtimewas1.35msec/slice.Finally,thenearlosslesscodingcompressionratiowas10.Notethatherethecompressionratioistheratiobetweentheactualbitsneededtostorethecompresseddataandtheoriginalimagebits.Inanotherexperiment,weconducted3Drepresentationofhigh-resolution2K2Kpixels54(a)(b)(c)(d)Figure4.3:Ahyperspectral3Dimagingdataanditsreconstructedrepresentationusingaprogressivenumberof3Dersets.Compressionratiosragingfromoneorderofmagnitude(nearlossless)tomorethantwoordersofmagnitude.(b)OriginalIndianpine,(b)100ers,compressionratio213,(c)1000ers,compressionratio37,(d)1000ersplusresidualcoding,compressionratio10.55ofLandsatdataacross20timeinstances.TheLandsatimagesaremultispectralthathavefewerspectralbandscomparingtohyperspectral.However,Landsattakesperiodicimagesofthesameregion.Whilethespectraldirectionofthedatasethavesomecorrelation,thereisalargeamountofcorrelationinthetimedirection.Forthisexperimentweusedthebelowcodingscenariotoevaluateandcomparethehigherdimensiontensorcoding.1.TheLandsatmultispectralimageshavesixspectrum.Wealignedthe20timeinstancesofeachspectrumina3Dtensor.Asaresult,six3Dtensorswereencodedwiththeproposedframework.2.TheLandsatmultispectralimageswerealignedina4Dtensor.Thedimensionsaretwospatial,time,andspectrum.Thenahextreewasusedtorepresentthetensorpartitioninganda4Dtensorcodingframeworkwasappliedtocodethedata.Wecomparedthecompressionratioofthesetwoscenariosattbitrates.Figure4.4showsthebitratevs.PSNRplotfortheLakemultispectralimage.Thelowestbitratepointachievedbythe4Dtensorcodingframeworkwas0.0072bpppb.Ittranslatetoacompressionratioof1111.ThecorrespondingPSNRwas31.5.Theencodingtimeatthisparticularbitratepointwas13.2secondspersliceandthedecodingtimewas114millisecondsperslice.Inotherwords,the4Dtensorcodingframeworkcandecodeabout9slicespersecondatthebitrateof0.0072bpppb.Figure4.5showsthedecodingtimecomparisonalongtbitratesbetweenthe3Dand4DtensorcodingfortheLakemultispectralimage.Thedecodingtimesof4Dand3Dtensorcodingatlowerbitrateswereclose.Howeverthegapwasgraduallyincreasedasthebitratewasincreased.Figure4.6showstheoriginalimagealongwiththe3Dtensorcodingreconstructionresultsattcompressionratios.Thecompressionratioswererangingfrom1142to340which56Figure4.4:LakemultispectralimagePSNRvsbpppbcomparison.Thecompressionresultof4Dtensorcodingwithhextreepartitioningiscomparedwith3Dtensorcodingwithoctreepartitioning.4Dtensorcodingachieveshighercompressionbyexploitingtheexistingcorrelationalongallthedimensionofthelakemultispectralimage.Figure4.5:Lakemultispectralimagedecodingtimecomparison.Thedecodetimepersliceisshowninmillisecondsfor4Dand3Dtensorcoding.Atlowerbitratesthedecodingtimeisclosewhileinthehigherbitratesthe4Dtensorcodingresultsinhigherdecodingtime.57arequitet.Notethatatcompressionratio1142,eachblockisrepresentedbyonlyonerankonetensor.Sinceeachblockneedstoberepresentedatleastwithonerankonetensor,thiscompressionratiorepresentalowerboundaryonhowmuchcompressionthe3Dtensorcodingcanachieve.Figure4.7showstheoriginalimagealongwiththe4Dtensorcodingreconstructionresultsattcompressionratios.Thecompressionratioswererangingfrom6154to769.The4Dtensorcodingcanachievebetterqualityreconstructionatthesamecompressionratiocomparedtothe3Dtensorcoding.Thisisduetothefactthatthe4Dtensorcodingtakesadvantageofthecorrelationalongthefourthdimension.Also,notethat4Dtensorcodingcanencodeatlowerbitratescomparedto3Dtensorcodinglowerboundary.58(a)(b)(c)(d)(e)(f)Figure4.6:3Dtensorcodingofhigh-resolution2K2Kpixelsacross20timeinstancesofLandsatdata.(a)originalimage,(b)compressionratio=1142andPSNR=29,(c)compressionratio=727andPSNR=30.83,(d)compressionratio=534andPSNR=31.73,(e)compressionratio=421andPSNR=32.37,(f)compressionratio=340andPSNR=32.88.59(a)(b)(c)(d)(e)(f)Figure4.7:4Dtensorcodingofhighresolution2K2Kpixelsacross20timeinstancesofLandsatdata.(a)originalimage,(b)compressionratio=6154andPSNR=27.29,(c)compressionratio=4210andPSNR=29.43,(d)compressionratio=3077andPSNR=30.43,(e)compressionratio=1429andPSNR=31.02,(f)compressionratio=769andPSNR=32.22.604.2ImageensemblescodingImagedatabasesrepresentacorecomponentofmanywell-establishedandemergingapplica-tionsandservicesincludingecommerceandsecurity.Forexample,imagedatabasesoffaces,ts,andeyeretinasareusedextensivelyforbiometricandothersecurity-relatedapplications.Suchdatabasesstoreavastnumberofimagesofthesametype,andyet,tradi-tionalcompressionstandardsareusedtocompressandstoretheseimageswithoutexploitingthecorrelationthatpotentiallyexistsamongtheimageswithinthesamedatabase.Forexample,theISO/IEC19794standardonbiometricdatainterchangeformatJPEGandJPEG2000asadmissiblelossycompressionmethods.Akeydriverforencodingeachimageinisolationofotherimageswithinthesamedatabaseistheabilitytoaccessanddecodeanyimagewithouttheneedtoaccess/decodeotherimages.Suchrequirementelim-inatespopularvideocodingstandardsasviablecandidatesforcodingstill-imagedatabases.Employingtheproposedtensorcodingframeworkcanachieveboth:(a)randomaccesstoanyimagewithinacollectionofimagescodedjointlyand(b)codingbyexploitinganypotentialcorrelationthatmayexistamongtheimageswithinthesamedatabase.4.2.1ExperimentalresultsTheproposedmethodwasappliedtotheYaleFaceDatabaseB[57].Thedatabasehasimagesof38persons.Eachofthemhas64imagesofsize192168.Theseimagesvaryinexpressionandilluminationcondition.Afterstackingtheimagesontopofeachother,wehavea3Dtensorofsize1921682432.TheresultingtensorisdecomposedusingPCPandtheersarearrangedin2Dmatrices.ThentheresultiscompressedbyJPEG2000.Withinthecontextofourproposedimage-ensembletensorbasedcompression,wecomparethe61Figure4.8:AveragePSNRplotof38personsfaceimagesfromYaleFaceDatabaseBversustheaveragestoragesizerequiredperimage.followingtensordecompositionapproachesandexistingstill-imagecompressionstandardsusedinimagedatabases:1.Block-wisePCP-decomposition.Theblocksizeis162164andthevalueofischangedtocontrolthestoragesize.2.Block-wiseCP-decomposition.Theblocksizeisthesameasinmethod(1)andthevalueofischangedtocomparetheresultsfordtcompactionratios.Here,weusedthesamestructureasin3.1exceptthedecompositionmethodisreplacedwithCPandJPEG2000losslessmodeisusedsincesmallchangesintheCPdecomposedvectorscanleadtolargeerrorinreconstruction.3.StoringeachimageseparatelyusingJPEG2000standard.TheMATLABimplementa-tionisused.Figure4.8showsthereconstructionPSNRaveragedover38personsversustherequiredspace(inKbytes)forallthe64imagesofapersonaveragedover38persons.Overawide-rangeofbitrates,PCPoutperformsothermethods.Figure4.9showsthePCPRvaluesfortheblocksofanimageencodedattwotbitrates.Noticethatwhenweincrease62(a)(b)Figure4.9:PCPRvaluesfortheblocksofanimageencodedata)288Bytesb)979Bytes.Astheallocatednumberofrankonetensorsisincreased,thetensorcodingframeworkallocateahighernumberofrankonetensorstotheblockswithmoreinformation.ForexampletheblocksthatcontainstheeyesandthemouththeRmaxvalue,ouralgorithmallocatelargerRvaluesfortheblocksthatcontainmoreinformation.InthecaseoftheYaleFaceDatabase,thoseregionsarearoundtheeyes,noseandthemouth.Figure4.10showsoneofthereconstructedimagesusingabovemethodsandstandardJPEGalongwithMATLABimplementationofMotionJPEG2000.Figure4.11showsthereconstructionresultsathigherbitrates.Athigherbitrates,exceptforJPEG,allofthemethodshaveclosePSNRandthevisualqualityissimilar.BasedontheprogressivenatureofPCP,itstimecomplexityislinearasafunctionofthenumberofrank-onetensors.CPfactorization(i.e.,theencodingside)hasaquadraticcomplexityasafunctionofR.Eithercase(PCPorCP),thedecodingcomplexityisonthesameorderasatraditionalJPEG2000decoding.Figure4.12showsthetimecomplexity,wherethedecompositionmethodsareevaluatedatadesktopcomputerwith12GBofmemoryandanIntelCorei72600CPU(8MBCache,3.4GHz).63(a)(b)(c)(d)(e)(f)Figure4.10:(a)Originalimage;(b)tensorcodingwithPCP(288Bytes,30.1dB);(c)tensorcodingwithCP(286Bytes,28.98dB);(d)JPEG2000(291Bytes,25.68dB);(e)motionJPEG2000(292Bytes,24.63dB);(f)JPEG(790Bytes,25.19dB).(a)(b)(c)(d)(e)(f)Figure4.11:(a)Originalimage;(b)tensorcodingwithPCP(979Bytes,PSNR:34.5);(c)tensorcodingwithCP(986Bytes,PSNR:32.6);(d)JPEG2000(975Bytes,PSNR:35.27);(e)motionJPEG2000(990Bytes,PSNR:35.1);(f)JPEG(999Bytes,PSNR:29.1).64(a)(b)Figure4.12:Averagea)decodingb)encodingtimeof38personsfaceimagesfromYaleFaceDatabaseBversustheaveragestoragesizerequiredperimage.Thesesimulationstheconjecturethatonecanachievetprogressivecodingofimageensembleswhilemaintaininglow-complexityrandomaccesstoanydesiredimagewhenemployingtensor-baseddecomposition.4.3LowcomplexityvideocodingTheproposedframeworkdoesnotrelyonanyformofMotionEstimation(ME)orMotionCompensation(MC).Itcanbetargetedforapplicationsanddevicesthattoleratedelaybutrequirelow-complexityatboththeencoderanddecoder.Weshowthatforlowrankvideos,TCoutperformsthevideocodingschemesthatdonotemployME.Amongsuchvideocod-ingschemes,H.264/AVC-Intra[58,59]arebasedoncodingeachframewithoutexploitingtemporalredundancy.DistributedCodingforVideoServices(DISCOVER)codec[60]isbasedonWyner-Zivcodingwithsideinformation[61,62].H.264/AVC-nomotion[58]codesaGroupOfPictures(GOP)suchthattheframeiscodedasareference(i.e.Iframe)andtheotherframesinthesameGOParecodedaspredictedpictures.ThislattercodingschemeexploitsthetemporalredundancywithoutemployinganyME.Anothersetoflow65complexityvideocodingschemesarebasedondimensionalityreductionbymeansofmultidi-mensionaldecomposition.Two-dimensionalSingularValueDecomposition(2DSVD)[14,63]videocodingisoneoftherecentdevelopedframeworksinthisfamily[13].4.3.1ExperimentalresultsInoursimulations,wesimplyemployedJPEG2000tocompresstheers'matrix.andrun-lengthcodingwasappliedtocompresstherank-valuesRj.Theproposedtensorcodingwasevaluatedbycomparingitwithfourencoders.Theyhaveincommonthepropertyoflowcomplexityencoding.WedidnotshowcomparisonresultswiththeHighVideoCoding(HEVC)standardbecauseofitsencodingcomplexity.EvenIntracodingofHEVChashighercomplexityincomparisonwithH.264.Figure4.13shows(a)encoding,(b)decodingtimecomparisonbetweenHEVCIntraandH.264IntraforContainervideo.WhileHEVCIntraistlymorecomplexthanH.264Intra,itachieves1.24dBaveragePSNRincrease.InthisexperimentHHIHEVCsoftwarerevision3604[64]wasusedatadesktopcomputerwith12GBofmemoryandanIntelCorei72600CPU(8MBCache,3.4GHz).Thefollowingevideocodecswereusedinoursimulations:1.H.264/AVC-nomotionwithhighle,GOPofsize24andnumberofreferenceframesequalstoone.TheJM18.4versionimplementedinC/C++availableat[65]wasused.2.H.264/AVC-Intrawithhigh(JM18.4version).3.Scalablevideocodingwith3Dsetpartitioninginhierarchicaltrees(3DSPIHT)[66{68].TheC/C++implementationisavailableat[69].InthisimplementationtheGOPsize66(a)(b)Figure4.13:HEVCIntraandH.264Intratimecomplexitycomparisonforcontainervideo.(a)Encodingtime,(b)Decodingtime.is16.Thevalueofbitperpixel(bpp)waschangedaccordinglytoachievetbitrates.4.DISCOVERDVCintracodec[60]withGOPsizeoftwo.TheC/C++implementationavailableat[70]wasused.5.TheproposedtensorcodingframeworkimplementedinMATLAB.First,wepresentthePSNRresultsandcorrespondingplotsfor180framesoffourCIFvideosavailableat[71{73].NotethattheDISCOVERcodecrequiresoddnumberofframestocodethem.Weused179framesofthetestvideosequenceswhencodingwithDISCOVERcodec.Also,theparameterswereassignedinawaytokeepthePSNRvaluesofbothkeyandWyner/Zivframesclosetogether.Fortensorcoding,wechangedtheblocksizetoobtainthehighestpossiblePSNRattbitrates.67(a)(b)(c)Figure4.14:PSNRvs.bitrateplotsof(a)Container,(b)Silent,(c)BridgeClosevideo.68(a)(b)(c)Figure4.15:PSNRvs.framesplotsof(a)Container(500Kbps),(b)Silent(699Kbps),(c)BridgeClose(380Kbps)videosencodedwithTCandSPIHT.TensorcodingmaintainsamoreuniformPSNRacrosstheframeswhiletheSPIHTqualitytendstodegradeasitgetclosertotheendoftheGOP.ThePSNRplotsareshowninFigure4.14.OurproposedmethodoutperformedallotherencodersexceptforhigherbitratesoftheContainervideowhere3DSPIHTprovidedhigheraveragePSNR.Eventhough3DSPIHTonaverageperformedbetterthanourmethod,itfromwidePSNRvariationwithineachGOP,andwithveryvisibledegradationthatisquitettowardtheendoftheGOP.Inparticular,3DSPIHTresultsinhighPSNRamongtheframesatthebeginningoftheGOPincomparisonwithframesattheendoftheGOP,especiallyforvideosthathaveframesthattendtochangewithinaGOP.Figure4.15showsthePSNRversusframesequenceofContainerandBridgeClose69(a)(b)(c)(d)(e)(f)Figure4.16:Frame14oftheContainerCIFvideo.(a)originalvideo,(b)tensorcoding(731.07Kbps;37.39dB),(c)H.264/AVC-no-motion(732.09Kbps;35.26dB),(d)DISCOVERDVC(735.53Kbps;34.06dB),(e)H.264/AVC-Intra(753.96Kbps;30.02dB),(f)SPIHT(732.94Kbps;38.22dB).70(a)(b)(c)(d)(e)(f)Figure4.17:TheframeoftheBridgeCloseCIFvideo.(a)originalframe,(b)tensorcoding(202.74Kbps;33.48dB),(c)H.264/AVC-no-motion(209.29Kbps;32.21dB),(d)DISCOVERDVC(274.77Kbps;28.32dB),(e)H.264/AVC-Intra(218.41Kbps;26.71dB),(f)SPIHT(203.77Kbps;31.81dB).71videosencodedusingtensorcodingand3DSPIHT.Atlowbitrates,thePSNRvariationof3DSPIHTwasnoticeable.Hence,suchwidevariationinvisualqualityisarguablyunacceptableformanyapplications.Figure4.16showsframenumber14ofcontainervideo.Theoriginalframewascom-paredwiththedecodedframeofetcodecsinthiscase.Thevideowascodedatapproximately730Kbps.Forthisparticularframe,tensorcodinghadlowerPSNRatthisbitratethanthe3DSPIHT.Meanwhile,tensorcodingdecodedtheframewithmoredetails(especiallythewaterregion)incomparisonwiththeotherdecoders.Figure4.17showsthestframeof"BridgeClose"video.Theoriginalframewascom-paredwiththedecodedframeoftheeencodersasinthepreviousexperiment.Thevideowascodedatapproximately210Kbps.Inthisexample,tensorcodingoutperformedallotherecodecsbothintermsofPSNRandvisualquality.Thedetailsofthebridgearemorevisibleintheframedecodedwithtensorcodingincomparisontotheothermethods.Duetotheaforementionedissueswith3DSPIHT,andinparticularthetvariationinvisualqualitywithineachGOP,wefocustheremainderofthissectiononcomparingtensorcodingwiththeotherthreeleadingcodingsystems.Inanotherexperiment,weencodedtenCIFvideosattwolevelsofPSNRtocomparethebitrateandthetimecomplexity.TheresultsfortherelativelylowPSNRareshowninTable4.2.Table4.3showstheresultscorrespondingtoencodingthesamevideosbutatrelativelyhigherPSNRvalues.Theencoderswereevaluatedatadesktopcomputerwith12GBofmemoryandanIntelCorei72600CPU(8MBCache,3.4GHz).Tensorcodingprovidesthebestbitrateresultsandverycompetitiveencoder/decodertimesatlowbitrates.Asexpected,DISCOVERDVCprovidedthebestencodingtimesbutatatpenaltyatthedecoderside.Forvideoswithlowmotion,tensorcodingencodingtimewaseven72smallerthanDISCOVERDVC.Howeverathigherbitratestheencodingtimewashigherthanothermethods.ThetensorcodingdecodingtimewasconsistentlythelowestatboththelowandhighPSNRlevels.Overall,tensorcodingprovidedagoodbalanceofcodingandlow-complexitydespiteitsMATLABimplementation.73Table4.2:Theencoding/decodingtime,PSNRandbitrateoftenCIFvideoswith180framesusingfourcodingmethods.Relatively-lowand(almost)thesamePSNRvaluesweretargetedforthisexperimenttocomparethebitrateandtimecomplexity.VideoMethodPSNR(dB)bitrate(Kbps)Encodetime(s)Decodetime(s)ContainerH.264/AVC-nomotion30.35276772.9H.264/AVC-Intra30.02754967.7DISCOVER30.2942458803TC30.18114811.4SilentH.264/AVC-nomotion30.96192884.2H.264/AVC-Intra30.376721119.6DISCOVER30.45456541367TC30.97116681.3MotherandDaughterH.264/AVC-nomotion32.55120723.62H.264/AVC-Intra32.38284897.7DISCOVER32.94227541059TC32.6498651.2BridgeCloseH.264/AVC-nomotion32.12209752.5H.264/AVC-Intra32.612641048.3DISCOVER32.64788641173TC32.29100641.3BridgefarH.264/AVC-nomotion37.0251762.7H.264/AVC-Intra37.03638977.9DISCOVER36.8449358151774Table4.2:(cont'd)TC37.0333250.7WaterfallH.264/AVC-nomotion26.53219813.6H.264/AVC-Intra26.43433938.7DISCOVER26.3727653971TC26.68148801.7VassarView0H.264/AVC-nomotion32.56109893.23H.264/AVC-Intra32.015881149.1DISCOVER32.2938268995TC32.4383451.1NewsH.264/AVC-nomotion32.44231763.4H.264/AVC-Intra32785977.9DISCOVER32.04486591044TC32.492301132.5RedFlowerH.264/AVC-nomotion32.52124842.4H.264/AVC-Intra32.0616451099DISCOVER32.1877673791TC32.48100381.2HallH.264/AVC-nomotion32.68117863.1H.264/AVC-Intra32.11672957.8DISCOVER32.3843458922TC32.6798361.275Table4.3:Theencoding/decodingtime,PSNRandbitrateoftenCIFvideoswith180framesusingfourcodingmethods.Relatively-highand(almost)thesamePSNRvaluesweretargetedforthisexperimenttocomparethebitrateandtimecomplexity.VideoMethodPSNR(dB)bitrate(Kbps)Encodetime(s)Decodetime(s)ContainerH.264/AVC-nomotion39.8819021256.5H.264/AVC-Intra38.9131841259.6DISCOVER39.4718001001020TC39.3612144483.1SilentH.264/AVC-nomotion39.7412161185.5H.264/AVC-Intra39.16374915111.5DISCOVER38.7420741011843TC39.7311123202.4MotherandDaughterH.264/AVC-nomotion39.28776885.3H.264/AVC-Intra39.7012031169.6DISCOVER39.62740721143TC39.977361541.9BridgeCloseH.264/AVC-nomotion39.9420381255.9H.264/AVC-Intra39.28396413710.4DISCOVER39.2826651192069TC39.9619753293.73BridgefarH.264/AVC-nomotion39.08446954.6H.264/AVC-Intra39.23137012210.1DISCOVER39.31104570209276Table4.3:(cont'd)TC39.203322083.6WaterfallH.264/AVC-nomotion32.4419841128.6H.264/AVC-Intra32.66238912910.9DISCOVER32.381093721219TC32.5012913733.4VassarView0H.264/AVC-nomotion39.326951164.3H.264/AVC-Intra39.17273314110.2DISCOVER39.011799921719TC39.226361831.9NewsH.264/AVC-nomotion39.52879974.6H.264/AVC-Intra39.3820851129.4DISCOVER39.141308871749TC39.918501882.2RedFlowerH.264/AVC-nomotion39.185981103.3H.264/AVC-Intra39.06415913710.9DISCOVER39.422169991465TC39.86494871.6HallH.264/AVC-nomotion39.897361045.1H.264/AVC-Intra39.4319901169.4DISCOVER39.261467752703TC39.846341222.277Chapter5Super-resolutionforreconstructinghighfrequencydataWepresentabriefintroductiontospatialISVinthecontextoftheproposedframework.Subsequently,theoverallarchitectureoftheproposedsuper-resolutionbasedspatialISVsystemisexplainedindetails.5.1SpatialISVwithHybridSuperandBaseFramesFigure5.1showstheproposedhybridtwo-layerspatialISVwithsuperandbaseframes.Thebaselayer(B(Fi))isthesequenceofthedown-sampledvideowheretheFiistheframei.Thedown-sampleratiocanbeanyreasonablevalue.Theenhancementlayer(E(Fi))isthebetweentheup-sampledbaselayerandtheoriginalvideo.Inotherwords,theenhancementlayercarriesthehighfrequencycomponents.Droppingtheenhancementlayercanreducetherequiredbandwidthtostreamthevideo.Howeverthemereup-sampledbaselayerwouldresultinblurryframeandnoticeablequalitydrop.Intheproposedframework,afewframesareencodedand/ortransmitted/receivedwiththeenhancementlayer.Werefertosuchframesassuper-frames.Theremainingframesareencodedand/ortransmitted/receivedusingthebaselayeronly.Wecalltheseframesbase-frames.Hence,thedecoderreceivesahybridofsuper-framesandbase-frames.This78Figure5.1:EncoderdiagramoftheproposedspatialISVwithhybridtwo-layerspatialvideocodingthatconsistofthesuper-framesandthebase-frames.Theprocessofgeneratingthebaseandtheenhancementlayerisshown.encodingframeworkwouldenabletheuseofhighfrequencydatainsuper-framestoenhancethebase-frames.Inotherwords,thesuper-framescanbeusedtobuildadictionaryforthesuper-resolutionmethod.Encodingafewframeswithenhancementlayerenablessavingbandwidthand/orreactingtochangingnetworkconditions.Undertheproposedframework,aGroupOfPictures(GOP)isasasetofonesuper-frameandallremainderframesarebase-frames.Ingeneral,thesuper-framecouldbeplacedwithinanywherewithaGOP.However,forsimplicityofimplementationandsimulation,weplacethesuper-frameastheframewithinaGOP.ItisimportanttonotethatalargerGOPsizewouldresultinasmallerrequiredbandwidth.Atthereceiverside,thedecodedvideoconsistsofframeswithtwotspatialsizes.Thesuper-framesareaddedtothedisplaysequencedirectlysincetheyhavethesameresolutionasofthedisplaysequence.Theyarealsousedtoextractthehighfrequencydata.Thebase-framesareup-sampledandthensuperresolvedusingtheproposedframework.Finally,theyare79Figure5.2:Theproposeddecoderstructurewithsuper-resolutionframeworkforatwo-layerISVencodedvideo.Thereconstructeddisplayvideoconsistsofsuper-framesandbase-frames.Thesuper-framesareaddeddirectlywhilethebase-framesaresuperresolvedtoimprovetheirquality.addedtothedisplaysequence.Figure5.2showstheproposeddecoderstructureandtheprocessofreconstructingthedisplayvideo.5.2Super-resolutionframeworkforISVTheproposedframeworkissimilartoanunsharpmaskingwheretheblurredcopyoftheframeisobtainedbyadown-samplingfollowedbyanup-samplingAbilinearorbicubiccanbeused.TheunsharpmaskSFRisobtainedusingthebetweenthedecodedsuper-frameandanup-sampledversionofitslow-resolutionpictureasineq.(5.1).SFR=SFSFH(5.1)Here,SFRistheresidual(unsharpmask),SFisthedecodedsuper-frame,andSFH=UP(DOWN(SF)).BothSFRandSFHarestoredintobeusedforsuperresolvingbase-frames.Onceanewsuper-frameisdecoded,theprocessofextractinghighfrequencydatawillberepeatedandthewillbeupdatedwiththenewdata.80Eachbase-framewasup-sampledandthensuperresolved.Thesuper-resolutionwasappliedinablock-wiseapproach.Weusedtheblocksthatarebythequadtreestructureoftheencoder.Theblocksareoftsizesrangingfrom44upto6464.Sincethequadtreestructureisonthebase-framewithsmallersize,up-samplingresultsinlargerblocksizes.Forexampleifthebase-frameisscaledupby2ateachdirection,thentheblocksizeswouldbefrom88upto128128.Basedonexperiment,weoutthatinthiscase,dividingtheblocksizebytwoateachdirectionandmaintainingthe168and816astheminimumblocksizegivesthebestresult.ForeachblockofBFH,ablock-wisesearchwasappliedtoamatchinSFH.Here,BFHistheup-sampledbase-frame.Thewindowofthesearchcanberestrictedtodecreasethecomplexity.Inourexperiments,thewindowwas64pixelsfromeachdirectionofthecurrentblock.Sumoftheabsolutevaluewasusedastheerrormeasure.Eq.(5.2)showstheblock-matchingminimization.k=argminkSUMSFkHBFjH(5.2)Wherejistheindexoftheblocktobesuperresolved,kistheindexofamatchingblockinSFH,SUM()isthesumofalltheelementsinablock.Afterk,wesuperresolveblockjbyaddingthecorrespondinghighfrequencydatafromSFR:^Fj=BFj+SFkR(5.3)Theoverallproposedalgorithmisasfollow:81Algorithm3super-resolutionforISVInput:HybridspatialSVCencodedvideo.Output:Superresolveddecodedvideoifsuper-framethenDecodetheframeandsendtotheoutputstreamComputeandstoreSFHinaComputeSFRasinEq.(5.1)andstoretheresultinaelseDecodeandup-sampletheframeforblockkinthequadtreestructuredoSearchforamatchinSFHasinEq.(5.2)FindthecorrespondinghighfrequencydatafromSFR.SuperresolvethecurrentblockasinEq.(5.3).endforSendthesuperresolvedbase-frametotheoutputstream.endif5.3ExperimentalresultsTheproposedframeworkwasimplementedwithinspatialSVCofVP9version1.3.0.Avideowasencodedintwospatiallayers.Thebaselayerwashalfofthedisplayvideoateachdirection.Theenhancementlayerwasthesamesizeasthedisplayvideo.Theenhancementlayerofthebase-frameswasdroppedbasedontheGOPsize.GOPsizes2,5,10,15,20,25,and30wereusedforcomparison.Theresultofusingquadtreeblockswascomparedwithvarioused-sizeblocks.The82Figure5.3:Thequadtreeblockstructurewhichwasusedfortheproposedsuper-resolutionframework.Theframeisthe25thframeoftheintotree.blocksizeswere88,1616,3232,and6464.Thequadtreeblockwasdividedintofoursub-blockstocompensateforup-sampling.Figure5.3showsthestructureofthequadtreeonthe25thframeoftheintotreevideo.Inthisexperiment150framesofintotree720pvideowereencodedat4Mbps.Thesearchboxforblockmatchingwas64pixelsfromeachdirection.FordownandupsamplingweusedbilinearinterpolationFigure5.4showsthePSNRresultversusGOPsize.NotethatforthesmallerGOP,largerblocksizehashigherPSNRresultwhileforlargerGOPthelargerblocksresultinlowerPSNR.Thisismainlybecauseofthefactthatatalongerdistancefromthesuper-frame,agoodmatchforlargerblocksizesbecomesharder.UsingthequadtreekeepsagoodbalancebetweenthesmallerandlargerGOP.Inanotherexperiment,150framesofintotree,shields,andoldtownvideoswereen-codedwithVP9SVCatvariousbitrates.Allthevideoswere720p.Theywereencodedwithtwolayers.Thebaselayerwashalfoftheenhancementlayerateachdirection.Theenhancementlayerofthebase-frameswasdropped.Thenatthedecoder,thefollowingmethodswereusedtoup-samplethebase-frames:83Figure5.4:PSNRcomparisonoftheproposedsuper-resolutionframeworkwhenappliedtoquadtreeandvarioussizeblocks.BilinearinterpolationBicubicinterpolationBilinearinterpolationandtheproposedsuper-resolutionBicubicinterpolationandtheproposedsuper-resolutionFigure5.5showsthePSNRvs.bitrateplotsthatcomparestheaboveup-samplingmethods.InthisexperimenttheGOPsizewas15.Notethatusingbilinearorbicubicup-samplingwiththeproposedsuper-resolutionframework,changesthePSNRresultslightly.Thisisbecauseofthefactthatusingbicubicup-samplingwouldresultinmorehighfrequencycomponentsinSFHandconsequentlylesshighfrequencycomponentsinSFR.Also,BFHineq.(5.3)wouldhavemorehighfrequencycomponentsduetobicubicup-sampling.However,theSFRhighfrequencycomponentsdecreasealmostcancelouttheTable5.1showsthePSNRcomparisonbetweenbicubicup-samplingandtheproposedsuper-resolutionframeworkforvariousvideoswithGOPofsize5.84(a)(b)(c)Figure5.5:PSNRresultsofthesuper-resolutionwithbilinearup-sampling,super-resolutionwithBicubicup-sampling,bilinearup-sampling,andBicubicup-samplingof(a)Intotree,(b)shields,and(c)oldtown.85(a)(b)(c)(d)Figure5.6:Frame27ofthe(a)original,(b)bilinearup-samplingandtheproposedsuper-resolutionframework,(c)bilinearup-sampling,(d)bicubicup-sampling,oftheoldtownvideo.For(b),(c),and(d),thevideoisencodedat2.7Mbps.86Table5.1:PSNRcomparisonbetweenbicubicup-samplingandtheproposedsuper-resolutionframework.VideosSRBicubicGainoldtown720p34.3332.711.62shields720p32.8231.311.51Stockholm720p32.7131.271.44intotree720p34.2833.241.04station1080p37.5036.750.75parkrun720p25.5925.240.35Pedestrianarea1080p36.5136.160.35crowdrun1080p26.926.60.3tractor1080p33.2132.960.25Figure5.6showsframe27oftheoldtownvideo.Theresultofbilinearup-sampling,bicubicup-sampling,bilinearup-samplingandtheproposedframeworkwerecomparedwiththeoriginalframe.Thevideowasencodedat2.7Mbps.Inthehighlightedpart,itisobviousthattheproposedframeworkreconstructedtheframewithmorehighfrequencycomponents.87Chapter6ConclusionWepresentedtensorcodingasalowcomplexityframeworkforcodinghighdimensionalvisualdata.TensorcodingisbasedonaproposedProgressiveCanonical-decompositionParallel-factor(PCP)decompositionthatreducesanndimensionaltensorontoa2Ddataset.TheproposedPCPwasappliedinblock-wiseapproach.Twotensorpartitioningmethodswhichareuniformandadaptivetreewereemployedtodividetheinputtensorintoasetofsub-tensorblocks.Theuniformpartitioningdivideatensorintoasetofequalsizeblocks.Theadaptivetreepartitioningemploysatopdownapproachtodividethetensor.Ateachlevelitdecidewhetherablockneedtobesub-dividedintoasetofsmallerblocksornot.Thedecisionismadebasedonadevelopedweighteddirectionalvarianceandtheallocatednumberofrank-onetensors.A2n-arytreestructurewasusedtostorethepartitioninginformation.Thepartitionedsub-tensorshavetamountofinformationandrank.Thereforetheymayrequiretnumberofrank-onetensors.Theproposedframeworkutilizesagreedyalgorithmtosearchfortheglobaloptimalnumberofrank-onetensorsthatrepresentalloftheblocksofatensor.AfterapplyingthePCPtoalltheblocks,thedecomposedersarearrangedandthenfurthercompressedbya2Dcompressionmethod.Therequiredsideinformationfordecodingwerestoredinaheaderandthenentropycoded.Theproposedtensorcodingframeworkwassupplementedwitharesidualcodingmoduletoenablenearlosslesscompression.Thisadditioncanbtheapplicationsthatrequirea88levelofdetails.Theresidualcodingmoduleencodedthetensor'sslicesseparatelysincethePCPhasalreadycapturedthepresentcorrelationamongtheslices.Animportantaspectoftheproposedtensorcodingframeworkisitsdesirableproperties.Weshowedthattheframeworkcanachieverandomaccess,progressivereconstructionorscalability,andlowcomplexityreconstruction.Thesepropertiesplayanimportantroleinapplicationslikeonlinebrowsing,streamingandscienanalysis.Weappliedtheproposedtensorcodingframeworktorepresentandcodethreetypeofdatasetswhichwerehyperspectral/multispectralimages,bio-metricfaceimages,andlowmotionvideos.Foreachapplicationweshowedthattheproposedtensorcodingframeworkcanachievehigherqualityreconstruction,speciallyatthelowbitrates,incomparisonwiththestandardcompressionmethods.Ourexperimentalresultsforthe4Dmultispectralimagesshowedapossibilityofthreeorderofmagnitudecompression.Thistcompressionratioispossiblebytakingadvantageoftheexistingcorrelationalongallthedimensions.Thelowerdimensionscom-pressionmethodscannotachievethislevelofcompression.Althoughthequalityofthereconstructedimageatthiscompressionlevelwasdegraded,itcanbeacceptableforsomeapplicationslikecourselevelbrowsingandOnthesecondpartofthisthesis,weproposedasuper-resolutionmethodforspatialinconsistentscalablevideostreaming.Inthisstreamingscenariosomeoftheframescanlosetheirenhancementlayerduetonetworkconnectionquality.Thisleadstoanundesirableexperiencewheresomeoftheframesareathighqualitywhiletheothersarenot.Intheworstcasethestreamingcankeepswitchingbetweenthetwoqualitiesinantomitigatethenetworkcongestion.Theproposedmethodwasusedtoreconstructtheframeswithdroppedenhancement89layer.Thiswasdonebyusingthehighfrequencydataoftheframeswithenhancementlayer(super-frames)asdictionary.Theframeswithoutenhancementlayer(base-frame)wereup-sampledandthensuperresolved.Thesuperresolutionmethodwasbasedonsearchingthedictionaryforamatchandthenaddingthecorrespondinghighfrequencydata.Thequadtreestructureofthecurrentframewasusedforblock-matchingsearchwithsuper-frame.TheproposedsuperresolutionframeworkwasintegratedwithGoogleVP9videocodec.ThenweappliedtheframeworktovariousHigh(HD)videostoestimatethedroppedenhancementlayer.OursimulationresultsshowanimprovementvisuallyandintermsofPSNRovertraditionalinterpolationup-sampling90BIBLIOGRAPHY91BIBLIOGRAPHY[1]T.G.KoldaandB.W.Bader,\Tensordecompositionsandapplications,"SIAMreview,vol.51,no.3,pp.455{500,2009.[2]R.M.BowenandC.-C.Wang,Introductiontovectorsandtensors.CourierCorpora-tion,2008,vol.2.[3]A.Cichocki,D.Mandic,L.DeLathauwer,G.Zhou,Q.Zhao,C.Caiafa,andH.A.Phan,\Tensordecompositionsforsignalprocessingapplications:Fromtwo-waytomultiwaycomponentanalysis,"SignalProcessingMagazine,IEEE,vol.32,no.2,pp.145{163,2015.[4]O.Scherzer,HandbookofMathematicalMethodsinImaging:Vol.1.SpringerScience&BusinessMedia,2011.[5]J.Liu,P.Musialski,P.Wonka,andJ.Ye,\Tensorcompletionforestimatingmissingvaluesinvisualdata,"PatternAnalysisandMachineIntelligence,IEEETransactionson,vol.35,no.1,pp.208{220,2013.[6]L.R.Tucker,\Somemathematicalnotesonthree-modefactoranalysis,"Psychometrika,vol.31,no.3,pp.279{311,1966.[7]J.D.CarrollandJ.-J.Chang,\Analysisofindividualinmultidimensionalscalingviaann-waygeneralizationofeckart-youngdecomposition,"Psychometrika,vol.35,no.3,pp.283{319,1970.[8]R.A.Harshman,\Foundationsoftheparafacprocedure:Modelsandconditionsforan"explanatory"multi-modalfactoranalysis,"1970.[9]A.Cichocki,D.Mandic,L.DeLathauwer,G.Zhou,Q.Zhao,C.Caiafa,andH.A.Phan,\Tensordecompositionsforsignalprocessingapplications:Fromtwo-waytomultiwaycomponentanalysis,"SignalProcessingMagazine,IEEE,vol.32,no.2,pp.145{163,2015.[10]A.T.MahfoodhandH.Radha,\Tensorvideocoding,"inAcoustics,SpeechandSignalProcessing(ICASSP),2013IEEEInternationalConferenceon.IEEE,2013,pp.1724{1728.92[11]||,\Compressionofimageensemblesusingtensordecomposition,"inPictureCodingSymposium(PCS),2013.IEEE,2013,pp.21{24.[12]S.Aja-Fandez,R.deLuisGarcia,D.Tao,andX.Li,Tensorsinimageprocessingandcomputervision.SpringerScience&BusinessMedia,2009.[13]Z.Gu,W.Lin,B.-S.Lee,andC.Lau,\Low-complexityvideocodingbasedontwo-dimensionalsingularvaluedecomposition,"ImageProcessing,IEEETransactionson,vol.21,no.2,pp.674{687,2012.[14]C.H.DingandJ.Ye,\2-dimensionalsingularvaluedecompositionfor2dmapsandimages."inSDM.SIAM,2005,pp.32{43.[15]B.Zhou,F.Zhang,andL.Peng,\Videodimensionreductionandcodingusingmul-tipletensorrank-rdecomposition,"inImageandSignalProcessing(CISP),20114thInternationalCongresson,vol.1.IEEE,2011,pp.330{334.[16]||,\Compactrepresentationfordynamictexturevideocodingusingtensormethod,"CircuitsandSystemsforVideoTechnology,IEEETransactionson,vol.23,no.2,pp.280{288,2013.[17]H.WangandN.Ahuja,\Rank-rapproximationoftensorsusingimage-as-matrixrep-resentation,"inComputerVisionandPatternRecognition,2005.CVPR2005.IEEEComputerSocietyConferenceon,vol.2.IEEE,2005,pp.346{353.[18]M.A.O.VasilescuandD.Terzopoulos,\Multilinearanalysisofimageensembles:Ten-sorfaces,"inComputerVisionECCV2002.Springer,2002,pp.447{460.[19]C.Ding,H.Huang,andD.Luo,\Tensorreductionerroranalysisapplicationstovideocompressionand,"inComputerVisionandPatternRecognition,2008.CVPR2008.IEEEConferenceon.IEEE,2008,pp.1{8.[20]H.WangandN.Ahuja,\Compactrepresentationofmultidimensionaldatausingtensorrank-onedecomposition,"vectors,vol.1,p.5,2004.[21]A.Karami,M.Yazdi,andG.Mercier,\Compressionofhyperspectralimagesusingdisceretewavelettransformandtuckerdecomposition,"SelectedTopicsinAppliedEarthObservationsandRemoteSensing,IEEEJournalof,vol.5,no.2,pp.444{450,2012.[22]L.Zhang,L.Zhang,D.Tao,X.Huang,andB.Du,\Compressionofhyperspectralremotesensingimagesbytensorapproach,"Neurocomputing,vol.147,pp.358{363,2015.93[23]H.Chen,W.Lei,S.Zhou,andY.Zhang,\Anoptimal-truncation-basedtuckerde-compositionmethodforhyperspectralimagecompression,"inGeoscienceandRemoteSensingSymposium(IGARSS),2012IEEEInternational.IEEE,2012,pp.4090{4093.[24]L.Wang,J.Bai,J.Wu,andG.Jeon,\Hyperspectralimagecompressionbasedonlappedtransformandtuckerdecomposition,"SignalProcessing:ImageCommunication,vol.36,pp.63{69,2015.[25]T.Hazan,S.Polak,andA.Shashua,\Sparseimagecodingusinga3dnon-negativetensorfactorization,"inComputerVision,2005.ICCV2005.TenthIEEEInternationalConferenceon,vol.1.IEEE,2005,pp.50{57.[26]H.Wang,Q.Wu,L.Shi,Y.Yu,andN.Ahuja,\Out-of-coretensorapproximationofmulti-dimensionalmatricesofvisualdata,"inACMTransactionsonGraphics(TOG),vol.24,no.3.ACM,2005,pp.527{535.[27]K.InoueandK.Urahama,\Dsvd:Atensor-basedimagecompressionandrecognitionmethod,"inCircuitsandSystems,2005.ISCAS2005.IEEEInternationalSymposiumon.IEEE,2005,pp.6308{6311.[28]J.Hou,L.-P.Chau,N.Magnenat-Thalmann,andY.He,\Scalableandcompactrep-resentationformotioncapturedatausingtensordecomposition,"SignalProcessingLetters,IEEE,vol.21,no.3,pp.255{259,2014.[29]S.K.Suter,J.A.I.an,F.Marton,M.Agus,A.Elsener,C.P.Zollikofer,M.Gopi,E.Gobbetti,andR.Pajarola,\Interactivemultiscaletensorreconstructionformul-tiresolutionvolumevisualization,"VisualizationandComputerGraphics,IEEETrans-actionson,vol.17,no.12,pp.2135{2143,2011.[30]Q.Wu,T.Xia,C.Chen,H.-Y.S.Lin,H.Wang,andY.Yu,\Hierarchicaltensorapproximationofmulti-dimensionalvisualdata,"VisualizationandComputerGraphics,IEEETransactionson,vol.14,no.1,pp.186{199,2008.[31]R.Sivalingam,D.Boley,V.Morellas,andN.Papanikolopoulos,\Tensorsparsecodingforregioncovariances,"inComputerVision{ECCV2010.Springer,2010,pp.722{735.[32]V.Cisco,\Forecastandmethodology,2013{2018.(2014)."[33]H.M.Radha,M.VanderSchaar,andY.Chen,\Thempeg-4scalablevideocodingmethodformultimediastreamingoverip,"Multimedia,IEEETransactionson,vol.3,no.1,pp.53{68,2001.94[34]J.-R.OhmandM.vanderSchaar,\Scalablevideocoding,"inTutorialmaterial,Int.Conf.ImageProcessingICIP,vol.2001,2001.[35]H.Schwarz,D.Marpe,andT.Wiegand,\Overviewofthescalablevideocodingex-tensionoftheh.264/avcstandard,"CircuitsandSystemsforVideoTechnology,IEEETransactionson,vol.17,no.9,pp.1103{1120,2007.[36]D.Mukherjee,J.Bankoski,A.Grange,J.Han,J.Koleszar,P.Wilkins,Y.Xu,andR.Bultje,\Thelatestopen-sourcevideocodecvp9-anoverviewandpreliminaryre-sults,"inPictureCodingSymposium(PCS),2013.IEEE,2013,pp.390{393.[37]\webm/libvpx,"https://chromium.googlesource.com/webm/libvpx/,accessed:2015-01-04.[38]S.C.Park,M.K.Park,andM.G.Kang,\Super-resolutionimagereconstruction:atechnicaloverview,"SignalProcessingMagazine,IEEE,vol.20,no.3,pp.21{36,2003.[39]S.Farsiu,M.D.Robinson,M.Elad,andP.Milanfar,\Fastandrobustmultiframesuperresolution,"Imageprocessing,IEEETransactionson,vol.13,no.10,pp.1327{1344,2004.[40]S.BakerandT.Kanade,\Limitsonsuper-resolutionandhowtobreakthem,"PatternAnalysisandMachineIntelligence,IEEETransactionson,vol.24,no.9,pp.1167{1183,2002.[41]E.M.Hung,R.L.DeQueiroz,F.Brandi,K.F.DeOliveira,andD.Mukherjee,\Videosuper-resolutionusingcodebooksderivedfromkey-frames,"CircuitsandSystemsforVideoTechnology,IEEETransactionson,vol.22,no.9,pp.1321{1331,2012.[42]K.F.DeOliveira,F.Brandi,E.M.Hung,R.L.deQueiroz,andD.Mukherjee,\Bipredictivevideosuper-resolutionusingkey-frames,"inProc.SPIESymposiumonElectronicImaging,VisualInformationProcessingandCommunication,2010.[43]F.Brandi,R.deQueiroz,andD.Mukherjee,\Super-resolutionofvideousingkeyframesandmotionestimation,"inImageProcessing,2008.ICIP2008.15thIEEEInternationalConferenceon.IEEE,2008,pp.321{324.[44]W.T.Freeman,T.R.Jones,andE.C.Pasztor,\Example-basedsuper-resolution,"ComputerGraphicsandApplications,IEEE,vol.22,no.2,pp.56{65,2002.[45]Z.Xiong,X.Sun,andF.Wu,\Robustwebimage/videosuper-resolution,"ImagePro-cessing,IEEETransactionson,vol.19,no.8,pp.2017{2028,2010.95[46]Q.Shan,Z.Li,J.Jia,andC.-K.Tang,\Fastimage/videoupsampling,"inACMTrans-actionsonGraphics(TOG),vol.27,no.5.ACM,2008,p.153.[47]J.Hastad,\Tensorrankisnp-complete,"JournalofAlgorithms,vol.11,no.4,pp.644{654,1990.[48]M.J.AtallahandM.Blanton,AlgorithmsandTheoryofComputationHandbook,Vol-ume2:SpecialTopicsandTechniques.CRCpress,2009.[49]A.SaidandW.A.Pearlman,\Low-complexitywaveformcodingviaalphabetandsample-setpartitioning,"inElectronicImaging'97.InternationalSocietyforOpticsandPhotonics,1997,pp.25{37.[50]X.Tang,W.A.Pearlman,andJ.W.Modestino,\Hyperspectralimagecompressionusingthree-dimensionalwaveletcoding,"inElectronicImaging2003.InternationalSocietyforOpticsandPhotonics,2003,pp.1037{1047.[51]E.Christophe,C.Mailhes,andP.Duhamel,\Hyperspectralimagecompression:adapt-ingspihtandezwtoanisotropic3-dwaveletcoding,"ImageProcessing,IEEETrans-actionson,vol.17,no.12,pp.2334{2346,2008.[52]X.Tang,S.Cho,andW.A.Pearlman,\3dsetpartitioningcodingmethodsinhyper-spectralimagecompression,"inImageProcessing,2003.ICIP2003.Proceedings.2003InternationalConferenceon,vol.2.IEEE,2003,pp.II{239.[53]X.TangandW.A.Pearlman,\Three-dimensionalwavelet-basedcompressionofhyper-spectralimages,"inHyperspectralDataCompression.Springer,2006,pp.273{308.[54]Q.DuandJ.E.Fowler,\Hyperspectralimagecompressionusingjpeg2000andprincipalcomponentanalysis,"GeoscienceandRemoteSensingLetters,IEEE,vol.4,no.2,pp.201{205,2007.[55]Aviris-airbornevisible/infraredimagingspectrometer-data.[Online].Available:http://aviris.jpl.nasa.gov/data/index.html[56]Landsatglobalarchiveconsolidation.[Online].Available:http://landsat.usgs.gov//LandsatGlobalArchiveConsolidation.php[57]A.S.Georghiades,P.N.Belhumeur,andD.J.Kriegman,\Fromfewtomany:Illu-minationconemodelsforfacerecognitionundervariablelightingandpose,"Pattern96AnalysisandMachineIntelligence,IEEETransactionson,vol.23,no.6,pp.643{660,2001.[58]D.Marpe,T.Wiegand,andG.J.Sullivan,\Theh.264/mpeg4advancedvideocodingstandardanditsapplications,"CommunicationsMagazine,IEEE,vol.44,no.8,pp.134{143,2006.[59]T.Wiegand,G.J.Sullivan,G.Bj˝ntegaard,andA.Luthra,\Overviewoftheh.264/avcvideocodingstandard,"CircuitsandSystemsforVideoTechnology,IEEETransactionson,vol.13,no.7,pp.560{576,2003.[60]X.Artigas,J.Ascenso,M.Dalai,S.Klomp,D.Kubasov,andM.Ouaret,\Thediscovercodec:architecture,techniquesandevaluation,"inPictureCodingSymposium(PCS"07),no.MMSPL-CONF-2009-014,2007.[61]L.Liu,Z.Li,andE.J.Delp,tandlow-complexitysurveillancevideocompres-sionusingbackward-channelawarewyner-zivvideocoding,"CircuitsandSystemsforVideoTechnology,IEEETransactionson,vol.19,no.4,pp.453{465,2009.[62]M.Tagliasacchi,A.Trapanese,S.Tubaro,J.Ascenso,C.Brites,andF.Pereira,\Intramodedecisionbasedonspatio-temporalcuesinpixeldomainwyner-zivvideocoding,"inAcoustics,SpeechandSignalProcessing,2006.ICASSP2006Proceedings.2006IEEEInternationalConferenceon,vol.2.IEEE,2006,pp.II{II.[63]J.Ye,\Generalizedlowrankapproximationsofmatrices,"MachineLearning,vol.61,no.1-3,pp.167{191,2005.[64]\HEVC,"http://hevc.hhi.fraunhofer.de,accessed:2013-08-09.[65]\H.264/AVCJMReferenceSoftware,"http://iphome.hhi.de/suehring/tml/,accessed:2013-01-18.[66]A.Said,W.Pearlmanetal.,\Animagemultiresolutionrepresentationforlosslessandlossycompression,"ImageProcessing,IEEETransactionson,vol.5,no.9,pp.1303{1310,1996.[67]B.-J.Kim,W.Pearlmanetal.,\Anembeddedwaveletvideocoderusingthree-dimensionalsetpartitioninginhierarchicaltrees(spiht),"inDataCompressionCon-ference,1997.DCC'97.Proceedings.IEEE,1997,pp.251{260.97[68]Y.ChenandW.A.Pearlman,\Three-dimensionalsubbandcodingofvideousingthezero-treemethod,"inVisualCommunicationsandImageProcessing'96.InternationalSocietyforOpticsandPhotonics,1996,pp.1302{1312.[69]\Imagecompressionprograms,"http://www.cipr.rpi.edu/research/SPIHT/spiht3.html,accessed:2013-09-02.[70]\Discover,"http://www.discoverdvc.org/,accessed:2012-11-20.[71]\Xiph.orgvideotestmedia,"http://media.xiph.org/video/derf/,accessed:2012-11-20.[72]\Yuvvideosequences,"http://www.discoverdvc.org/,accessed:2012-11-20.[73]\Videoqualityexpertsgroup(vqeg)-its,"ftp://vqeg.its.bldrdoc.gov/MM/cif/,ac-cessed:2012-11-20.98