Abstract An Adaptive Block Truncation Coding Schem

AnAdaptiveBlockTruncationCodingSchemeandItsData-DrivenParallelImplementationXiaoyanYuAdissertationsubmittedtoKochiUniversityofTechnologyinpartialfulfillmentoftherequirementsforthedegreeofDoctorofPhilosophy(SpecialCourseforInternationalStudents)DepartmentofEngineeringGraduateSchoolofEngineeringKochiUniversityofTechnologyKochi,JapanMarch,2006AbstractAnAdaptiveBlockTruncationCodingSchemeandItsData-DrivenParallelImplementationXiaoyanYuInthisdissertation,anadaptiveblocktruncationcoding(ABTC)schemesuit-ableforhighly-parallelsoftwareimplementationisproposed.ABTCisoneofextendedschemesoftheoriginalblocktruncationcoding(BTC),butitintroducesanewclassifi-cationapproachforadaptivecodinganddifferentialpulsecodingmodulation(DPCM).Furthermore,itshighly-paralleldata-drivensoftwareimplementationisdiscussedtorealizereal-timevideoapplicationsonsmallandlow-powerubiquitousdevices.IntheproposedABTCscheme,twooptimalthresholdvaluesareintroducedtoidentifyaluminanceblockimageasuniformblock,normalblock,orpatternblock.Oneisthesamplefirstabsolutecentralmoment(AM),whichdenotesthedispersionfromthemeanvalueina4x4pixelblock;anotheristhemeanofabsoluteerrors(MAE)betweentheoriginalpixelvaluesandtheirdecodeddataineveryblockimage,whichiscomputedwiththesimplifiedabsolutemomentblocktruncationcoding(SAMBTC).Inordertoachieveabettertrade-offbetweentheimagequalityandcomputationalcomplexity,differentcodingapproachesareemployedtocompress/decompressthreesortsofblockimages.Moreover,toimprovethecompressionefficiency,DPCMisutilizedtoremovetheredundanciesexistingintheintra-andinter-framebyvariantpredictionmethodswiththenegligibleimagedistortion.Inthedata-drivenparallelimplementation,thefollowingtechniquesareutilizedto–i–achieveahigh-throughputperformance.First,hierarchicalparallelisminherentintheABTCschemeisexploitedtoutilizethehardwareresourcesatmaximum.Second,thecomputationalcomplexityisdecreasedbytakingfulladvantageofthecompoundoper-atorsinvolvedinthecurrentinstructionsets.Also,associativetemporalmemoriesareusedtorealizethedistributedcomputation.Third,theSIMD-type(single-instruction-multiple-data)packetisemployedtoaccomplishthedata-levelparallelism(DLP)andtodecreasethepipelineprocessingload.Finally,staticloadbalanceisdiscussedforthescalableimplementationontheavailableprocessingresourcessuchasprocessorsandmemories.Experimentalevaluationsoftheproposedschemewereperformedusingstandardvideosequencesdepictingvariantamountsofmotionandbackgroundactivity.Theresultsillustratethattheproposedschemecanachievereconstructedimagesequencesuptoaround37dBwith60compressionratio.Comparedwithpreviousscheme,over1dBimagequalitygainscanbeobtainedwiththeidenticalcompressionratio.Furthermore,evaluationresultofDDMPimplementationshowsover60VGAframespersecondonaverage,whichisaroundtwofoldasmanyasthatofpreviousscheme.keywordsdata-driven,adaptiveBTC,DPCM,parallelimplementationiiAcknowledgementFirstofall,IwouldliketoappreciateKochiUniversityofTechnologyandPresidentofKUT,Prof.HajimeOKAMURA,forgivingmethischancetostudyhereandofferingthreeyearsofexpensesupport.Withoutthespecialscholarshipprogram(SSP)forinternationalstudents,Icannotcompletemydoctoralresearchsuccessfully.Next,Iamverythankfulofmysupervisor,Prof.MakotoIWATA,forthreeyearsofencouragement,guidanceandsupport.Prof.MakotoIWATAhasguidedmeintotheexcitingareaofimageprocessingandcomputervisionanddata-drivenparallelcomputingofhighperformance.Ihadneverforgottenhissayingthat“Nevergiveup”whenyoumeetthedifficultyinyourresearch.Moreover,hisresearchenthusiasmandinsightintodata-drivenarchitecturesandsoftwaresystemmakemedeepimpression.Especially,hispatienceandseriousspiritforstudyandinstructingstudentswillaffectmycareerforever.Theworkpresentedherewouldnothavebeenpossiblewithouthisconstantguidanceandhelpfulrecommendation.Iamespeciallygratefulforhisuntiringefforttoteachmehowtothinktotackletheproblemsinmyresearchworld.Ibelievehisgoodthinkingwayandresearchskillswillbebeneficialtomystudyinthefuture.Iwouldalsoliketothankothermembersofmycommittee,Prof.TakaoNISHITANI,Prof.KazunoriSHIMAMURA,Prof.MamoruOKADA,andAssociateProf.MasahiroFUKUMOTO,forhelpfulcommentsonmythesiswork.Besides,Iwouldliketoappreciatetheotherprofessorsandsecretariesofthede-partmentofInformationSystemsEngineeringfortheirhelp.Moreover,Iacknowledgethestaffsoftheinternationalrelationscenter,Prof.MikikoBAN,Ms.MarikoKUBO,Ms.YurikoHAMADA,Ms.KimiKIYOOKA,fortheirkindnessandwarmness.–iii–Third,IamgratefulofthefellowstudentsinIwataLab.Itwouldhavebeenfarmoredifficulttocompletethisworkwithouttheirhelp.SpecialthanksgotoDaichiMorikawa,RuhuiZhang,ShujiSannomiya,HiroshiShima,ShinjiOgasawara,ShiraneYuta,ShoujiTsuneishifortheirhelpfuldiscussionandadvice.IwouldhaveneverforgottentheirhelpandwarmnesswhichmademyacademicexperienceatKUTmostenjoyable.Again,IwouldliketothanktheotherSSPstudentsofKUTfortheirhelp.Lastbutnotleast,mydeepestgratitudegoestomydearhusbandforhisdeeploveandpersistentsupport.Hehasbeenmyadvisor,critic,teacher,co-investigator,closefriend,andpartnerfrombeforethebeginningofthisPh.Dworkandthroughitsevolution.Iappr