您好,欢迎访问三七文档
AUTOMATICGENERATIONOFC++/JAVACODEFORBINARYARITHMETICCODINGDannyHongandAlexandrosEleftheriadisColumbiaUniversityNewYork,NY10027,USA{danny,eleft}@ee.columbia.eduABSTRACTBinaryarithmeticcodingis,compression-wise,themostef-fectivestatisticalcodingmethodusedinimageandvideocompression.Itisbeingusedforcompressingbi-levelim-ages/videos(JBIG,JBIG2,MPEG-4shapecoding)andisalsooptionallybeingutilizedforcodingofcontinuous-toneimages/videos(JPEG,H.264).Despiteitswideuse,differ-entarithmeticcodersaregenerallyincompatiblewitheachotherandapplicationdevelopersarefacedwiththedifficulttaskofunderstandingandbuildingeachcoder.Wepresentasetofsimpleparametersthatcanbeusedtodescribeanybinaryarithmeticcoderthatiscurrentlybeingdeployedandwealsointroduceasoftwaretoolforautomaticallygenerat-ingC++/Javacodeforbinaryarithmeticcoding,accordingtothedescription.1.INTRODUCTIONHuffmancoding[1]isarguablythemostwidelyusedstatis-ticalcompressionmechanismformediarepresentation(e.g.,Group3[2]andGroup4[3]fax,MPEG-1[4],MPEG-2[5],andetc.).Itisproventobeoptimalamonginstantaneous(prefix)codesasitcanrepresentanygivenrandomvari-ablewithin1bitofitsentropy(tighterboundsareshownin[6,7,8]).Arithmeticcoding[9,10],derivedfromEliascod-ing[11],isanotherstatisticalcodingmethodproventoyieldbettercompressionthanHuffmancodingwhentheproba-bilitiesofthesymbolsarenotinpowersof0.5;however,ithasnotbeenwidelyusedformediarepresentationduetoitscomplexityandpatentissues.Theveryfirst,practi-calarithmeticcoderwasdevelopedforcompressingbi-levelimages(theSkewcoder[12,13]andtheQ-Coder[14]),asHuffmancodingcannotcompressbinarysymbols,unlessgroupsofsymbolsarecodedatatime.Run-lengthcod-ing(e.g.,Golombcoding[15])isagoodalternativecod-ingmethodforbinarysymbols,whentheprobabilityofoneThismaterialisbaseduponworksupportedinpartbytheNationalScienceFoundationunderGrantACI-0313116.symbolismuchhigherthantheother.Neverthelessitisaanoptimalcodingmethodforsourceswithgeometricdistri-butionandforthebestresultforallpossiblebinarysourcesequences,usinganadaptivebinaryarithmeticcoder(BAC)ispreferred.Eventoday,mostofthepracticalarithmeticcodersdealsolelywithbinaryalphabets:binaryarithmeticcodingiscomputationallysimpleanditmakesusinghigher-ordercon-ditioningmodelsfeasible.Insomecasesitisonlynat-uraltoassumeabinarysource.Forinstance,JBIG[16],JBIG2[17],andMPEG-4shapecoding[18]focusoncod-ingofbi-levelimages/videos(JBIGandJBIG2canalsobeusedforgrayscaleimageswherebit-planebybit-planecod-ingisapplied),andforJPEG2000[19]andMPEG-4tex-turecoding[18],bit-planecodingisultimatelyapplied.Ontheotherhand,arithmeticcodingcanoptionallybeusedinJPEG[20]andH.264[21],andinthesecases,eachsym-bolisfirstbinarizedsothataBACcanbeused.DespitesuchwideuseofBACs,differentBACsaregenerallyin-compatiblewitheachother(e.g.,acodestringgeneratedbyanarithmeticencoderspecifiedinJBIGcannotbecorrectlydecodedbyanarithmeticdecoderspecifiedforMPEG-4shapecoding);asaremedy,wepresentauniquesolutionthatunifiesBACs.WedefineasetofparametersthatcanbeusedtoautomaticallygeneratedifferentvariantsofBACs.Arithmeticcodingcanbeseparatedintotwomainparts:modelingandcoding.Themodelingpartappropriatelyse-lectsoneormorestructuresforconditioningevents,andgatherstherelativefrequenciesoftheconditionedevents[12,22],whichcorrespondtotheeventprobabilities.Model-ing,byitself,isahugetopicandtherearenumerouseffec-tivemodelsthathavebeenintroduced.TheH.264standardalonedefinesmorethan300modelstoaccountfordifferentstructureseachbitofthebinarizedsyntacticelementsmighthave.Consequently,unifyingmodelingisanextremelydif-ficulttask(ifnotimpossible),thoughthereareuniversalcodes(e.g.,[23]),andmodelsoftendependontheseman-ticsofthedata.Here,wefocusonlyonthecodingpart.Foraverygoodintroductiononarithmeticcoding–includingthehistoryofarithmeticcoding–refertothe1984paperbyLangdon[9].Flavor[24,25]isalanguagethathasbeendevelopedtodescribethesyntaxofanycompressedbitstreamsothatthebitstreamparsingandgenerationcodecanbeautomaticallygenerated.Flavoralreadyhasaconstructfordescribingvariable-lengthcodesandwecomplementitbyintroducinganewconstruct(bac,withasetofparameters)fordescrib-ingBACs.UsingFlavorwiththenewconstruct,anyBACcanbeeasilydescribedandthecorrespondingC++/Javacodecanbeautomaticallygenerated.Asaresult,applica-tiondeveloperscansolelyconcentrateonthemodelingpart,whichhasbeenshowntohavehigherimpactonthecom-pressioneffectivenessoftheBACcomparedtothecodingpart.Thenextsectionbrieflydescribesthemainconceptbe-hindbinaryarithmeticcoding,Sections3and4presenttheparametersneededtodescribepracticalBACs,andwecon-cludewithSection5.2.BACKGROUNDAhigh-levelpseudo-codedescribingthebasicconceptofbinaryarithmeticcodingisdepictedinFigure1.Thevari-ableRrepresentsthecurrentintervallength(initially1)anditisdividedintotwosubintervalswithlengthsR0andR1=R-R0,accordingtotheprobabilitiesofthetwopossiblesymbols(P0andP1=1-P0).ThevariableLrepresentsthelowerboundofthecurrentinterval(theintervalisrepre-sentedas[L,L+R))andifthesymbol0isbeingcoded,then,assumingthatthetopintervalcorrespondstothesym-bol0,thenewintervalis[L+R1,L+R1+R0);li
本文标题:AUTOMATIC GENERATION OF C++JAVA CODE FOR BINARY AR
链接地址:https://www.777doc.com/doc-1339 .html