SUBMITTED TO IEEE TRANSACTIONS ON IMAGE PROCESSING

TREE-STRUCTUREDMETHODFORLUTINVERSEHALFTONINGANDFORIMAGE

HALFTONING

MuratMe¸seandP.P.VaidyanathanDepartmentofElectricalEngineering136-93,

CaliforniaInstituteofTechnology,Pasadena,CA91125USA,

Phone(626)395-4681Fax:(626)795-

E-mail:mese@systems.caltech.edu,ppvnath@sys.caltech.edu

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING

EDICS:4-DISPor4-OTHD

ABSTRACT1

RecentlytheauthorsproposedaLookUpTable(LUT)basedmethodforinversehalftoningofimages.TheLUTforinversehalftoningisobtainedfromthehistogramgatheredfromafewsamplehalftoneimagesandcorrespondingoriginalimages.ManyoftheentriesintheLUTareunusedbecausethecorrespondingbinarypatternshardlyoccurincommonlyencounteredhalftones.Thesearecallednonexistentpatterns.Inthispaper,weproposeatreestructurewhichwillreducethestoragerequirementsofanLUTbyavoidingnonexistentpatterns.Wewilldemonstratetheperformanceonerrordiffusedimagesandorderedditherimages.Then,weintroduceLUTbasedhalftoningandtree-structuredLUT(TLUT)halftoning.EventhoughTLUTmethodismorecomplexthanLUThalftoning,itproducesbetterhalftonesandrequiresmuchlessstoragethanLUThalftoning.Wewilldemonstratehowerrordiffusioncharacteristicscanbeachievedwiththismethod.Afterwards,ouralgorithmwillbetrainedonhalftonesobtainedbyDirectBinarySearch(DBS).ThecomplexityofTLUThalftoningishigherthanerrordiffusionalgorithmbutmuchlowerthanDBSalgorithm.Also,thehalftonequalityofTLUThalftoningincreasesifthesizeofTLUTgetsbigger.Thus,halftoneimagequalitybetweenerrordiffusionandDBSwillbeachieveddependingonthesizeoftree-structureinTLUTalgorithm.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING2

I.Introduction

Inversehalftoningreferstoreconstructingacontinuoustoneimagefromitshalftonedversion.Thereisnouniqueinversehalftoneforagivenhalftonedimage.Hence,extrapropertiesofimagesareusedininversehalftoning.Thebasicassumptioninallinversehalftoningalgorithmsisthe“lowpass”assumption:“Natural”imageshave“mostlylowpass”characteristics.Thus,thesimplestinversehalftoningislowpassfilteringbutthismethodalsoremovestheedgeinformation.Besideslowpassfiltering,therearemoresophisticatedapproachesforinversehalftoning[1],[3],[2],[18],[20]and[4].Theseapproachesaresummarizedin[9].

Inrecentpapers[7],[8],[9]weintroducedLookUpTable(LUT)methodsforinversehalftoningofimages.TheLUTmethodwasfirstusedbyNetravalietal.todisplayorderedditheredimages[13].However,inthatworktheauthorsassumedthatthedithermatrixandtheregistrationofhalftonedimagewiththedithermatrixareknown.Noticethat,thisinformationmaynotbeknownforaparticularhalftoneimage.Inanotherpaper,TingandRiskinusedLUTmethodinhalftonecompressiontogetatemporarycontoneimage[15]butahighqualitycontoneimagewasnotaimedinthatwork.

Inthispaper,wereviewtheLUTinversehalftoningmethodinSec.II.Thenwewillintroducetree-structuredLUT(TLUT)inversehalftoningandshowhowtodesignTLUTinSectionIII.TheexperimentalresultsofTLUTinversehalftoningwillbeshowninSectionIV.Inthesecondpartofthepaper,wewillapplyLUTandTLUTideastoimagehalftoning.TheaimofTLUTwillbetoimitatethecomputation-intensivegoodqualityhalftones.ThesewillbediscussedinSectionsV-VII.Preliminaryversionsofthispaperwerepresentedin[10]and[11].

II.ReviewofLUTinversehalftoning

LUTinversehalftoningmethoddoesnotinvolveanylinearfilteringatallanditdoesnotassumeanyimagemodel.Letusdefineacollectionofpixelsintheneighborhoodofaspecificpixelasatemplateofthepixel.Todeterminetheinversehalftonevalueataspecificpixel,thealgorithmlooksatthepixel’sneighborhoodanddependinguponthedistributionofpixelsinthetemplateofthepixel,itassignsacontonevaluefromaprecomputedLUT.InTableIweshowanexampleofatemplateusedinLUTinversehalftoning.Inthistable“O”denotestheestimatedpixelandallofthepixelswithinthetemplateareusedintheprediction.Thenumberofpixelsusedinthetemplateisrelativelysmall,typicallysixteen.Forasixteenpixeltemplateweneed216=KbytesofLUT,andforanineteenpixeltemplateweneed219=512KbytesofLUT.ThemethodiscompletelyparallelanditdoesnotrequireanycomputationbecauseitisanLUTbasedalgorithm.Thismakesitfasterthanthepreviouslyknownmethods.Moreover,themethodprovidesverygoodimagequality,oftenevenbetterthanthemethodin[4]aswehavedemonstratedin[7].Fig.1showstheinversehalftonedmandrillimageusingthemethodof[4],andFig.2showsthesameusingtheLUTmethodof[7]2.Inbothcasesthestartingpointwasanerrordiffusedhalftoneimage.NoticethattheLUTmethodpreserveshighfrequencyinformationverywell(haironthecheeks).

Sinceinversehalftoningcannotbedonewithoutusingextrapropertiesofimages,weusesampletrainingimagesfor

2Note

thatthetrainingandtestimagesdescribedinSec.IVareusedthroughputthepaper.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING3

Fig.1.Inversehalftoningbyfastiht2(Kiteet.al.)

(PSNR=22.59dB).Thehalftonewasobtainedbyerrordif-fusion.Fig.2.LUTinversehalftoningwith“Rect”template

(PSNR=24.42dB).Thehalftonewasobtainedbyerrordif-fusion.

generatingtheLUT.Inthetrainingphase,sampleimagesandcorrespondinghalftoneversionsareusedtoobtaintheLUT.Thetrainingphaseissimple,andhastobedoneonlyonceforaspecifichalftonemethod.

NonexistentPatterns:TheLUTsizescanbecomebiggerifahighqualityinversehalftoneisrequired.EachbinarycombinationofpixelsinthetemplatecorrespondstooneentryintheLUT.Butmanyofthesecombinationshardlyariseinpractice,andarereferredtoasnonexistentpatterns.Forexample,inerrordiffusionwithaeighteenpixelneighborhood,wefoundthat22.75%ofthepatternsarenonexistent.Forclustereddotordereddither78.22%arenonexistent,andforBayer’sdisperseddotordereddithering86.22%.Inthenextsectionweshowhowtotakeadvantageofnonexistentpatternsandreducestorage.

III.TreestructuredLUT(TLUT)inversehalftoning

Inthissection,weshowhowtotakeadvantageofnonexistentpatternsandreducestorage.Byusingatreestructure,thestoragerequirementscanbeafractionofitsLUTequivalent.Inthissense,thetreestructurecanberegardedasa‘compressed’versionoftheLUT.FirstasmalltemplateLUTwillbeusedtogetacrudeinversehalftoneforeachpixel.Thenthisvaluewillberefinedbyadaptivelyaddingpixelstothetemplatedependingonthecontext.Theseadaptivepixelswillbeplacedinatreestructure.LiketheLUTmethod,treestructureinversehalftoningdoesnotinvolveanyfiltering,buttherewillbemorestepsininversehalftoningasoutlinedinSec.III-B.

InSec.III-Aweshowthetypeoftreestructureweareusingininversehalftoning.ThenwewilldescribeourinversehalftoningwithtreestructureinSec.III-B.DesignoftreestructureisdiscussedinSec.III-CwhereasassigningthecontonevaluestotreeleavesisoutlinedinSec.III-D.Thentheexperimentalresultsonerrordiffusedhalftoneimages

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING4

xxxxxxxxxxOxxxxxTABLEI

Anexampleoftemplateusedininverse

halftoning

(-3,0)(2,1)(4,-1)(3,1)(2,-1)......(2,-1)(2,0)(3,-1)(2,-1)Pixel coordinates.Contone value for inverse halftoning;halftone value for halftoning.Fig.3.Generictreestructuresusedininversehalftoningandhalftoning.

A.TreeStructure

Letusdenotethesizeoftheinitialtemplateusedasa(thisistypicallysmall,e.g.,a=9).Wewilldefine2abinarytreescorrespondingtothedifferentpatternsinthetemplate.Eachtreenodeiseithersplitfurtheroritisaleaf.TreenodesaresplitsothatthecontonevaluesofLUTobtainedwithinitialtemplatecanberefined.Ifanodeissplit,thenthelocationofadditionalpixel,(i,j),isstoredinthenodeandtwomorenodesattachedtothisnodeasitschildren.Ifatreenodeisatreeleaf,thenacontonevalueisstoredinthenode.

InFig3wehaveillustratedagenerictreestructure.Theuppertreenodesarethetreeroots.Theblackshadednodesarethetreeleavesandtheystoreacontonevaluein[0,255].Unshadedtreenodeshavetwochildrenandtheystorethelocationoftheadditionalpixelasshown.

Inordertostorethetree,weneedtorecordthetreestructure,additionalpixellocations,andcontonevaluesstoredinthetreeleaves.Letusassumethatwehave2atreesandbtreeleaves.Thenitcanbeshownthatweneedbbytestostorethecontonevaluesinthetreeleaves,(2b−2a)/8bytestostorethetreestructureand(b−2a)memoryunitstostorethelocationsofadditionalpixels(SeeAppendixIfordetails).Memoryunitusuallycorrespondsto1or2bytes.Thestoragerequirementofmemoryunitwilldependonthenumberofpossiblelocationsforadditionalpixels.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING5

B.InverseHalftoningwithTreeStructure

Intree-structuredinversehalftoning,wetrytofindatreeleafforeachpixelinthehalftoneimage.Afterfindingthetreeleaf,thecontonevaluestoredinthetreeleafwillbeassignedastheinversehalftonevalueofthepixel.Tofindthecorrespondingtreeleafforeachhalftonepixellocationwewilldothefollowing:

1.FirstlookatthepatterninsidetheinitialtemplateBofsizea.Eachpatternwillcorrespondtooneofthebinarytrees.Therootofthecorrespondingtreeisdeclaredasthecurrentnode.

2.Eachnodeiseithersplitintotwonodesoritisaleaf.Ifanodeisaleaf,thentheaveragecontonevalueisstoredinthenode.Thisvalueisassignedastheinversehalftonevalueatthepixel.

3.Ifanodeissplitintotwo,thenthelocation(i,j)oftheadditionalpixelisstoredinthenode.Getthehalftonevalueofthepixelwhichis(i,j)awayfromthecurrentpixel.Ifthisvalueis0(1),thentheleft(right)nodeisassignedasthecurrentnode.Thengotostep2.C.Designingthetreestructure

First,theinitialtemplateBofsizeashouldbechosen.ThepixelsinBarechosenfromaneighborhoodNLofthecurrentpixel.HereNLdenotesaneighborhoodofsizeL:

NL={(i,j)|i∈{−L,...,L}andj∈{−L,...,L}}.

Thus,B={(i0,j0),(i1,j1),...,(ia−1,ja−1)}.Thistemplatecanbefoundusingthealgorithmoutlinedin[8]andasummaryofthisalgorithmisgiveninAppendixII.Then,eachpatterninthistemplatewillcorrespondtooneofthebinarytrees.Thesewillalsocorrespondtotheinitial2atreeleaves.Startingfromthistreestructure,wewilladdnewtreeleavesincrementally.Thisisdoneuntilwegetsufficientnumberoftreeleavesorwearesatisfiedwiththeinversehalftonequality.InthisprocessthecostfunctionwillbetheMSEofaspecifictreestructure.Bythis,wemeanthemeansquarederrorbetweentheinversehalftonedimageswiththespecifictreestructureandtheoriginalimagesinthetrainingset.FindingtheMSEofatreerequiresthecontonevaluesinthetreeleaves.Givenanytree,thereisanoptimalwayinMSEsensetoassigncontonevaluestoitsleaves.InSec.3-Dweexplainhowthesearecalculated.Herewegiveanalgorithmtoaddthe‘best’treeleafinMSEsensetoatreestructure.

1.ForeachleaftandforeachpixelpinNLdothefollowing:Assumethattheleaftissplitintotwonodeswiththeadditionalpixelp.CalculatetheMSEofthistreestructure(MSEt,p).2.FindtheleaftoandadditionalpixelposuchthatMSEto,poisminimum.

3.Updatethetreestructurebysplittingthetreeleaftowiththeadditionalpixelpo.

Herethealgorithmiswrittenasaboveforsimplicity.Howeverthealgorithmcanbeimprovedforcomputationalefficiency.AnothersimplificationwouldbetosplitKleavesratherthanoneleafaftercalculatingtheMSEforeachtreeleafinthetreestructure.Then,thesecondandthirdstepsoftheabovealgorithmshouldbemodifiedasfollows:2’.FindKleavesto,1,...,to,Kandpo,1,...,po,KsuchthatMSEto,1,po,1,...MSEto,K,po,KarethesmallestKnumbers

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING6

xxxxxxx0xxxxxTABLEII

InitialtemplateTFS13usedintreestructureLUTinversehalftoningofFloyd-SteinbergErrorDiffused

Images.

3’.Updatethetreestructurebysplittingthetreeleavesto,1,...,to,Kwiththeadditionalpixelspo,1,...,po,Kcorre-spondingly.

D.Assigningcontonevaluestotreeleaves

Wehavetofindthecontonevaluesforeachtreeleafgivenatreestructureandadditionalpixellocations.Afterwards,thesecontonevalueswillbeassignedasinversehalftonevaluesinthetreestructureinversehalftoningalgorithm(Sec.3-B).Wewillusetrainingimagesinthisprocess,i.e.,halftoneimagesandcorrespondingcontoneimages.FirstwefindthetreeleavesforeachpixelinthetrainingsetusingtheinversehalftoningalgorithminSec.3-B.LetusdenotethesetofcontonevaluesofpixelswhichhavethesametreeleaftasStwhereatisthesizeofSt.ThusSt={x1,x2,...,xat}.Then

󰀁at

xi/at).theclosestintegertothemeanvalueofStwillbeassignedasthecontonevalueoftheleaf(ct):ct=int(i=1

IV.ExperimentalResultsforTLUTinversehalftoning

WewillfirstapplytheTLUTinversehalftoningalgorithmonerrordiffusedhalftonestodemonstratetheperformanceofouralgorithm.Then,TLUTwillbeappliedonclustereddotorderedditheranddisperseddotorderedditherhalftones.Notethat,ourinversehalftoningalgorithmcanbeappliedtoanytypeofhalftoningalgorithm.A.TLUTinversehalftoningoferrordiffusedimages

Firstwechoosetheinitialtemplateusingthealgorithmgivenin[9].Wehaveincluded30imagesinourtrainingsetandanother30imagesinourtestset.Inthesesets,wehavebothincludedsmoothandnon-smoothimagesandtheseimagescanbefoundat[21].Thetemplate,calledTFS13,forFloydSteinbergerrordiffusedimagesisshowninTableII.Inthetable‘0’denotesthecurrentpixel,andthe‘x’denotestheotherpixelsinthetemplate.Wehavechosenthebiggesttemplatesuchthattherearenononexistentpatternsinthehalftonetrainingimages.ThenthenodesareaddedincrementallyusingthealgorithmsummarizedinSec.3-C.Forthetreedesignalgorithm,wehavechosenN3asourneighborhood3.NotethatthroughoutthepaperweusedtheimprovedtreedesignalgorithmforcomputationalefficiencywithK=256(KisdefinedinSec.III-C).

InTableIV,wehavesummarizedtheperformanceoftreestructureinversehalftoning.Thetreesuseddifferonlyinthenumberoftreeleaves.TheinitialtemplateforallofthesetreestructuresisTFS13andithasninepixelsin

3A

listofacronymsusedinthispaperissummarizedinTableIII.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING7

NL

TFS13

FS1,FS2,FS3,FS4,FS5TCD9

CD1,CD2,CD3,CD4,CD5TOD8

OD1,OD2,OD3NeighborhoodaroundthecurrentpixelInitialtemplateusedforFSerrordiffusedimages

DifferenttreesusedinTLUTinversehalftoningofFSerrordiffusedimagesInitialtemplateusedforclustereddotorderedditheredimages

DifferenttreesusedinTLUTinversehalftoningofclustereddotorderedditheredimagesInitialtemplateusedfordisperseddotorderedditheredimages

DifferenttreesusedinTLUTinversehalftoningofdisperseddotorderedditheredimages

TABLEIII

Acronymsusedinthepaper.

Tree#add.leavesStorage(tree)Storage(contone)Storage(location)Storage(total)AveragePSNRLenaFS120481536B10240B2048B13824B26.dB30.33dBFS240962048B12288B4096B18432B26.93dB30.73dBFS361442560B14336B6144B23040B27.01dB30.84dBFS481923072B16384B8192B278B27.05dB30.91dBFS5102403584B18432B10240B32256B27.08dB30.95dBTABLEIV

ComparisonofDifferentTreeStructuresusedin

TLUTinversehalftoning.

thetemplate.Thusalltreestructureshave213=8096initialtreeleaves.Thenumberofadditionaltreeleavescanbeseeninthesecondrow.Storagerequirementsforstoringthetreestructure,thecontonevaluesandtheadditionalpixellocationsarealsoshowninthird,fourthandfifthrowrespectivelyintermsofbytes.Thetotalstoragerequirementofatreeisthenreportedinthesixthrow.Intheseventhrow,theaveragePSNRvalueoftheinversehalftoneimagesinthetestset(withrespecttotheoriginalcontoneimages)areshown.WealsoaddedthePSNRvaluesofTLUTinversehalftonedLenaimages.NotethatLenaimageisnotinthetrainingset.

SimilarlyinTableVwehavesummarizedtheinversehalftoneimagequality,andstoragerequirementsof16and19sizeLUTinversehalftoning[8],andtheinversehalftoningalgorithm‘fastiht2’reportedin[4].Inthelastrow,theaveragePSNRvalueoftheinversehalftoneimagesinthetestsetarereported.Inthetable‘Rect’denotesaspecific16pixeltemplateand‘19pels’denotesaspecific19pixeltemplateasdefinedin[8].

FromthesetablesitcanbeseenthattheimagequalityachievedwithtreestructureFS1isbetterthantheimagequalityachievedwithLUThalftoningusingthe‘19pels’template.Notethatthelatterneeds512KBforstoragewhereasFS1needslessthan13.5KB.Also,theinversehalftoneimagequalityachievedwithFS1isbetterthanfastiht2method.Besides,theinversehalftonequalityissuperiorformandrillimagewhichhasalothighfrequencycontent.ImagequalityMethodTemplateStorageAveragePSNRLUTMethodRect19pelsKB512KB26.50dB26.60dBfastiht2(Kite[4])-25.94dBTABLEV

ComparisonofDifferentTemplatesusedinLUT

inversehalftoning.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING8

Fig.4.ResultofLUTinversehalftoningwith“Rect”tem-plate.

Fig.5.ResultofTreestructureinversehalftoningwithFS2.

forFS1canbeincreasedbyaddingmoretreeleavestoFS1.Biggertreeswithstoragerequirementsarereportedinsecond,thirdandfourthcolumnsoftableIV.Eventhough,theaveragePSNRoftheTLUTinversehalftonedimagesinthetestsetincreases,visually,theimagequalityremainsalmostthesame.ForvisualcomparisonwenowshowtheinversehalftoneimagesforLenaimagesinFig.4andFig.5.Thesefigurescanbeseenbetteratthewebsite[21].InFig.4theinversehalftoneisobtainedwithLUTinversehalftoningusing‘Rect’template.InFig.5,thetreestructuredinversehalftoningwithtreeFS2isshown.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING9

B.TLUTinversehalftoningofclustereddotorderedditheredimages

WehavedesignedandtrainedTLUTtreeson3×6clustereddotorderedditherhalftones[5].Theinitialtemplateisfoundusingthetemplateselectionalgorithmgivenin[8]andthistemplateisshowninTableVI(TCD9).InTableVIIwehavelistedTLUTtreeswiththesameTCD9initialtemplatebutwithdifferentnumberoftreeleaves4.Thus,allthesetreestructureshave29=512initialtreeleaves.Forthetreedesignalgorithm,wehavechosenN3asourneighborhood.Inthetable,thenumberoftreeleavesincreasesfromlefttorightandaveragePSNRdenotestheaveragePSNRoftheinversehalftonedimagesinthetestset.TheinversehalftoneimagesobtainedusingCD1treestructurehaveapparentperiodicstructuresbecausewedidnothaveenoughadaptivepixels.IftreestructureCD3isusedinTLUT,mostoftheperiodicstructuresaresuppressedandtheinversehalftonesarefreefromblockiness.IfweaddmoretreeleavestotreestructureCD3theaveragePSNRoftheinversehalftonedimagesinthetestsetincreases.However,theinversehalftonequalitydoesnotchangemuchvisuallywhenweaddmoretreeleavestotreestructureCD3.InFig.6weshowtheTLUTinversehalftonedBoat400imagewithCD3tree.ForcomparisonweshowtwostepLUTinversehalftonedBoat400imagewith19pixeltemplateinFig.7[9].TwostepLUTinversehalftoningalgorithmisLUTinversehalftoningalgorithmfollowedby3×3medianfilteringtosupresstheperiodicstructures.Visually,theTLUTresultisbetter:NoticethatthereisanaturaltextureinthewaterinTLUTresultwhereasthewaterdoesnotlooknaturalinsomepartsintheLUTexample.)Also,TLUTneedsonly14KBwhereasLUTneeds512KB.ForcomparisoninFig.8(PSNR=25.86dB)weshowtheinversehalftonedimageswithalgorithmIIin[5].IfthisiscomparedwiththeimageinFig.6,weseethattheTLUTinversehalftonequalityisbetterthantheimagequalityoftheresultofalgoritmIIin[5].

TheimpulsivenoisewhichoccurswhenasmallertreeisusedcanberemovedbymedianfilteringifwewanttoreducethestoragerequirementofTLUTinversehalftoning.Weused3×3medianfilteringtosuppressit.LetuscallthefollowingalgorithmastwostepTLUTinversehalftoning:Givenahalftoneimage,firstTLUTinversehalftonetheimageandthenapplymedianfilteringtotheresult.TheresultsoftwostepTLUTinversehalftoningaregiveninTableVIII.WefoundoutthatvisualqualityoftwostepTLUTinversehalftoningwithtreestructureCD2isthesameasthevisualqualityoftwostepTLUTinversehalftoningwithtreestructureCD3.Thusthestoragerequirementcanbedecreasedto9.56KB.

C.TLUTinversehalftoningofdisperseddotorderedditheredimages

Here,wetrainedourTLUTtreesondisperseddotorderedditheredwith8×8Bayer’smatrix.Againtheinitialtemplateisfoundusingthetemplateselectionalgorithmgivenin[8]andthistemplateisshowninTableIX(TOD8).WehavelistedTLUTtreeswiththesameTOD8initialtemplatebutwithdifferentnumberoftreeleavesinTableX.Inthistable,thenumberoftreeleavesincreasesfromlefttoright.N5neighborhoodisusedindesigningthetrees.WehaveobservedperiodicstructuresintheTLUTinversehalftoneswhenatreestructuresmallerthanOD3isused.WehavesuppressedtheperiodicstructureswithtreestructureOD3.WehaveshowntheTLUTinversehalftonedBoat400

4Note

thatthePSNRvaluesofinversehalftonedclustereddotorderedditherimagesaresmallerthanthePSNRvaluesofinversehalftoned

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING10

xxxxxTABLEVI

InitialtemplateTCD9usedintreestructureLUTinversehalftoningofclustereddotordereddithered

images.

x

0xxTreeadditional#ofleavesStorage(tree)Storage(contone)Storage(location)Storage(total)AveragePSNRBoat400CD12048576B2560B2048B5184B25.26dB26.72dBCD240961088B46084096B9792B25.54dB26.99dBCD361441600B6656B6144B14400B25.67dBdB27.19dBCD481922112B8704B8192B19008B25.76dB27.26dBCD5102402624B10752B10240B23616B25.82dB27.33dB

TABLEVII

ComparisonofDifferentTreeStructuresforTLUTinversehalftoningofclustereddot

orderedditheredimages.

TreeAveragePSNRBoat400CD123.82dB27.22dBCD224.06dB27.41dBCD324.17dB27.54dBCD424.22dB27.58dBCD524.26dB27.dB

TABLEVIII

ComparisonofDifferentTreeStructuresfortwo-stepTLUTinversehalftoningofclustered

dotorderedditheredimages.

Fig.6.ResultofTLUTinversehalftoneofclustereddot

orderedditheredBoat400imagewithCD3.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING11

Fig.7.TwostepLUTinversehalftoning

with“19opt”template.ThehalftonewasaClusteredDotOrderedDitherImage(PSNR=26.73dB).

Fig.8.InversehalftonedboatimagewithAl-gorithmIIin[5].

imagewithOD3treeinFig.9.NoticethatLUTinversehalftoningcouldnotsuppresstheeseperiodicstructures[9].

V.LUTandTLUTImageHalftoning

Theaimofhalftoningistherenditionofgray-scaleimagesonbileveldevices.Themostcommonalgorithmsforhalftoningaredisperseddotorderedditheranderrordiffusion.Indisperseddotorderedditheracontinuous-toneimageisthresholdedwithaspatiallyperiodicscreenwhereasinerrordiffusionhalftoning,theerroris‘diffused’totheunprocessedneighborpoints[16].

Thecomplexitiesofthealgorithmsandtheresultingimagequalityaredifferent.Disperseddotorderedditherrequiresonlypointwisecomparisons,anditisaparallelmethod.Buttheresultinghalftonessufferfromperiodicpatterns.Error

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING12

xxxx0xxxTABLEIX

InitialtemplateTOD8usedintreestructureLUTinversehalftoningofdisperseddotordereddithered

images.

Treeadditional#ofleavesStorage(tree)Storage(contone)Storage(location)Storage(total)AveragePSNRBoat400OD12048544B2304B2304B5152B24.48dB27.49dBOD241961056B4352B4608B10016B24.62dB27.62dBOD361441568B00B6912B14880B24.66dB27.65dBTABLEX

ComparisonofDifferentTreeStructuresforTLUTinversehalftoningof8×8disperseddot

orderedditheredimages.

diffusedhalftonesdonotsufferfromperiodicityandofferbluenoisecharacteristic[16]whichisfoundtobedesirable.Themaindrawbackisthaterrordiffusionisinherentlyserial,anditrequiressomecomputationinthediffusionprocess.Thebluenoisemaskisanotherwaytogethalftonequalitysimilartoerrordiffusion[12].Thedisadvantageofbluenoisemasksisthattheresultinghalftonesdonothaveenhancementliketheerrordiffusioninherentlyhas.

Here,weintroduceLUTbasedhalftoningandTLUTbasedhalftoningmethods.PixelsfromacausalneighborhoodandthecontonevalueofthecurrentpixelwillbeincludedintheLUT.TheLUThalftoningwillrequirenoarithmeticoperationsotherthanmemoryaccess.Foranyhalftoningmethod,asamplesetofimagesandhalftonesoftheseimageswillbeusedtoconstructtheLUT.Eventhoughtree-structureLUT(TLUT)halftoningismorecomplexthanLUThalftoningitproducesbetterhalftonesanditrequiresmuchlessstoragethanLUThalftoning.Wewilldemonstratehowerrordiffusioncharacteristicscanbeachievedwiththismethod.

Therearemorecomputation-intensivehalftoningmethodslikeDirectBinarySearch(DBS)[14]whichgivethebesthalftonequality.Thesealgorithmsserveasexcellentbenchmarks,butarenotcommonlyused.WhenTLUTistrainedonDBS-likeimages,thehalftonequalitywillbeinbetweentheerrordiffusionqualityandDBSquality.Moreover,theTLUThalftonequalitywillgetbetterwhenthesizeofTLUTincreases.

VI.LUTHalftoning

Wewillprocesspixelsonebyoneinraster-scanorder.Inordertodecidethehalftonevalueatachosencell(orpixellocation),wewillusethehalftonevaluesalreadydecidedinacarefullyselectedtemplateorneighborhoodofthechosencellandthecontonevalueofthechosenpixel.Thetemplatedesignphaseismerelyaprocessofdecidingwhichneighboringcellsshouldbeinvolvedintheprediction.WeshowasampletemplateinTableXI.Theletter“0”denotes

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING13

Fig.9.ResultofTLUTinversehalftoneofdisperseddot

orderedditheredBoat400imagewithOD3.

TABLEXI

LUTtemplateusedinhalftoning.

131015117593162O148412thecellwhosehalftonevalueisbeingdecidedandothernumbersdenotethecellsinthetemplate.Thetemplateselectionalgorithmwillbedescribedlaterinthissection.

LetusassumethatthereareNpixels(excludingthepixelbeingpredicted)intheneighborhoodandtheyareorderedinaspecificway.Letusalsocallthehalftonevaluesofpixelsasp0,p1,...,pN−1andthecontonevalueofthepixelbeingpredictedasc.Notethatthereare2N28differentpatternssincepi∈{0,1}fori=0,1,...,N−1andc∈{0,28−1}.Sincethehalftoneimageisabilevelimage,ourLUTshouldreturnabinaryvalueforeachpattern(p0p1...pN−1c):T(p0p1...pN−1c).A.DesignofLUT

InthedesignofLUT,weneedtrainingimagesandcorrespondinghalftoneimages.Thus,weselectasetofimagesandhalftonetheseimageswithanyhalftoningalgorithmofourchoice.Wewillfirstobtaintheexpectedhalftonevalueforeachpattern.ThenthishalftonevaluewillbeassignedtothecorrespondingLUTpositionforthatpattern.Letusdenotethenumberofoccurrencesofpattern(p0p1...pN−1c)inthesamplehalftoneimagesasKp0p1...pN−1candcorrespondinghalftonevaluesas

hp0p1...pN−1c,i

IfKp

p...p

c

fori=0,1,...,Kp0p1...pN−1c−1.

>0,theLUThalftonevalueforthepattern(p0p1...pN−1c)willbetheclosestquantizationpointtothe

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING14

meanofthecorrespondinghalftonevaluesis,i.e.,

󰀉

T(p0p1...pN−1c)=

where

mp0p1...pN−1c=

B.Nonexistentpatternestimation

IfKp0p1...pN−1c=0,thenthepattern(p0p1...pN−1c)doesnotexist.Inthiscasethehalftonevalueshouldbeestimatedinadifferentway.AsimilarproblemarisesinLUTinversehalftoningaswell,andthreemethodsareproposedin[7]forthis.Oneofthesecalledthebestlinearestimator,modifiedforLUThalftoning,worksasfollows:Letusnumberallthepatternswhichexistinthesamplehalftoneimagesas(pi,0pi,1...pi,N−1ci)fori=0,1,...,M−1whereMisthenumberofexistingpatterns.LetA(i,j)=pi,jandb(i)=T(pi,0pi,1...pi,N−1ci)fori=0,1,...,M−1,j=0,1,...,N−1.AlsoletA(i,N)=cifori=0,1,...,M−1.Wearelookingforanestimateofthehalftonevalueofthenonexistentpatternof(p0p1...pN−1c)inthefollowingform

y=[p0p1...pN−1c][x0x1...xN−1xN].

󰀇󰀆󰀅󰀈x

T

1ifmp0p1...pN−1c≥0.50ifmp0p1...pN−1c<0.5

hp0p1...pN−1c,i

󰀁Kp0p1...pN−1c−1

i=0

Kp0p1...pN−1c

.

ThebestlinearestimatorwillbetheleastsquaressolutiontotheoverdeterminedsystemofequationsAx=b.Thesolutionis

x=(ATA)

−1

ATb.

Thenforeachnonexistentpattern(p0p1...pN−1c),weobtainthehalftonevalueasfollows:

󰀉

0,ify<0.5

T(p0p1...pN−1c)=

1,ify≥0.5C.TemplateSelection

WehaveshownhowtodesigntheLUTforagiventemplate.ThenextquestionishowwecanchoosethebesttemplateforLUThalftoning.WehaveproposedamethodfortemplateselectioninLUTinversehalftoningin[8].HerewewillmodifythatalgorithmforLUThalftoning.

Assumethatthenumberofpixelstobeusedinthetemplateisfixed.OuraimwillbetochoosethebesttemplateofsizeN.Wewillsimplifythetemplateselectionproblembyrestrictingthepixelstobeinafixedcausalneighborhood.WewilldefineourneighborhoodasNL={(i,j)|i∈{−L,...,0},j∈{−L,...,L}}∪{(0,j)|j∈{−L,...,−1}}.Letuscallthepixelwhosehalf–tonevalueisbeingestimatedasthecurrentpixel.

Herewegivearecursivealgorithmtochoosethetemplate.LetusdenoteatemplatehavingapixelsasTa.AssumethatwehavePimageswhichhavesizesx1×y1,x2×y2,...,xP×yPinourtrainingset.WewillhavebothcontinuoustoneimagesDl(n1,n2)andcorrespondinghalftoneimagesHl(n1,n2)forl=1,2,...,Pinourtrainingsetwhere(n1,n2)denotesthepixellocationintheimages.

NowletusdefinetheerrorintheLUThalftoneimagescomparedtoLUTimagesforagiventemplateTasfollows5:

5Note

󰀁

that,abettererrormeasurewouldbetheMSEoftheHVSfilterederrorbetweenthehalftones.Howeverthistopicisleftforfurther

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING15

Fig.10.GoldhillhalftonedwithFSerrordiffusion.

ET(H,H)=

󰀃T

ylxl󰀂P󰀂󰀂l=1i=1j=1

󰀃lT(i,j))(Hl(i,j)−H

2

󰀃TisobtainedusingLUThalftoningwithtemplateT.Wecansummarizeoursize-MtemplateselectionwhereH

algorithmintwosteps:Step0.a=0.Ta=∅.Step1.Define(p,r)asfollows:

(p,r)=

argmin󰀃T,H).󰀁ET(H

(i,j)∈NL

Includethepixel(p,r)inthetemplate:Ta=Ta−1+{(p,r)}.

Step2.IfTeadoesnothaveMelementsgotostep1.Otherwisestop.D.LUTexample

WehavechosenN=15andconstructedourtemplateusingalgorithmgivenintheprevioussection.Thetrainingsetincludedseveralerrordiffusedhalftoneimages(seebelow).ThistemplatewasshowninTableXI.Inthetable,“k”thcell(k>0)denotesthatthecellisaddedtothetemplateinkthstep.

Notethatweneed2N28=223Bits(1MBytes)tostoretheLUT.WehavetrainedourLUTwithimagesusingthefollowingimages:Lena,peppers,greyramp,boat,airplane,Zelda,greyscalerampandtwomoresmoothimages.Thehalftonesoftheseimagesfortrainingareobtainedwitherrordiffusion.Afterwardswehalftonedgoldhillwiththe

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING16

Fig.11.GoldhillhalftonedwithLUThalftoning.

designedLUT.Noticethatgoldhillwasnotinthetrainingset.TheresultisshowninFig.11.ForcomparisonweshowGoldhillhalftonedwitherrordiffusioninFig.10.ExceptinregionsofverylowandveryhighgreylevelstheLUThalftoningmethodgivesthesameimagequalityaserrordiffusion.6Noticethat,thestoragerequirementofLUThalftoningisalsohigh.InthenextsectionwewillintroduceTLUThalftoninginordertoovercometheseproblems.

VII.Tree-structureLUThalftoning

Asillustratedabove,LUThalftoninghassomedefectsinregionsofverylowandveryhighgreylevels.Itcanbeseenthatthehalftonepatternforg=

1256hasapproximately16×16periodicity,andLUThalftoningwithatemplateshown

inTableXIcannotcapturethisperiodicity.Becausethistemplatedoesnothaveapixelwhichis16×16pixelsawayfromthehalftonepixelbeingpredicted.Differentcellsshouldbeaddedtocapturedifferenthalftonepatterns.However,thetemplatesizecannotbeincreasedarbitrarilybecauseofstorageproblems.Thisproblemcanbesolvedbyaddingcellsadaptivelytothetemplate.Wewillshowthat“adaptivecells”canbestoredefficientlyinatreestructure.A.Treestructure

Letusdenotethesizeoftheinitialtemplateusedasa(thisistypicallysmall,e.g.,a=11).Wewilldefine2a+8binarytreescorrespondingtothedifferentpatternsinthetemplate.Eachtreenodeiseithersplitfurtheroritisaleaf.TreenodesaresplitsothatthehalftonevaluesofLUTobtainedwithinitialtemplatecanberefined.Ifanodeissplit,thenthelocationofadditionalpixel,(i,j),isstoredinthenodeandtwomorenodesareattachedtothisnodeasitschildren.Ifatreenodeisatreeleaf,thenahalftonevalueisstoredinthenode.

InFig3wehaveillustratedagenerictreestructure.Theuppertreenodesarethetreeroots.Theblackshaded

6The

imagescanbefoundatthewebsite[21]forbetterviewing.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING17

nodesarethetreeleavesandtheystoreahalftonevalue.Unshadedtreenodeshavetwochildrenandalsotheystorethelocationoftheadditionalpixelasshown.

Inordertostorethetree,weneedtorecordthetreestructure,additionalpixellocations,andhalftonevaluesstoredinthetreeleaves.Letusassumethatwehave2a+8treesandbtreeleaves.Thenitcanbeshownthatweneedbbitstostorethehalftonevaluesinthetreeleaves,(2b−2a+8)bitstostorethetreestructureand(b−2a+8)memoryunitstostorethelocationsofadditionalpixels7.Onememoryunitusuallycorrespondsto1or2bytesandthisdependsonthesizeofNLusedinthetreedesignstep.IngeneralonememoryunitiskbitswherekInTLUThalftoning,wetrytofindatreeleafforeachpixelinthehalftoneimage.Afterfindingthetreeleaf,thehalftonevaluestoredinthetreeleafwillbeassignedasthehalftonevalueofthepixel.Tofindthecorrespondingtreeleafforeachhalftonepixellocationwewilldothefollowing:

1.FirstlookatthepatterninsidetheinitialtemplateTofsizea.Eachdifferentpatternwillcorrespondtooneofthebinarytrees.Therootofthecorrespondingtreeisdeclaredasthecurrentnode.

2.Eachnodeiseithersplitintotwonodesoritisaleaf.Ifanodeisaleaf,thenthehalftonevalueisstoredinthenode.Thisvalueisassignedasthehalftonevalueatthepixel.

3.Ifanodeissplitintotwo,thenthelocation(i,j)oftheadditionalpixelisstoredinthenode.Getthehalftonevalueofthepixelwhichis(i,j)awayfromthecurrentpixel.Ifthisvalueis0(1),thenleft(right)nodeisassignedasthecurrentnode.Thengotostep2.C.Designingthetreestructure

First,theinitialtemplateTofsizeashouldbefound.ThepixelsinTarechosenfromaneighborhoodNLofthecurrentpixel.ThistemplatecanbefoundusingthealgorithmoutlinedinSec.VI-C.Then,eachpatterninthistemplatewillcorrespondtooneofthebinarytrees.Thesewillalsocorrespondtotheinitial2a+8treeleaves.Startingfromthistreestructure,wewilladdnewtreeleavesincrementally.Thisisdoneuntilwegetsufficientnumberoftreeleavesorwearesatisfiedwiththehalftonequality.InthisprocessthecostfunctionwillbetheMSEofaspecifictreestructure.Bythis,wemeanthemeansquarederrorbetweentheTLUThalftonedimageswiththespecifictreestructureandthehalftoneimagesinthetrainingset.FindingtheMSEofatreerequiresthehalftonevaluesinthetreeleaves.Givenanytree,thereisanoptimalwaytoassignhalftonevaluestoitsleavesusingthemajorityrule.Herewegiveanalgorithmtoaddthe‘best’treeleaftoatreestructure.

1.ForeachleaftandforeachpixelpinNLdothefollowing:Assumethattheleaftissplitintotwonodeswiththeadditionalpixelp.CalculatetheMSEofthistreestructure(MSEt,p).2.FindtheleaftoandadditionalpixelposuchthatMSEto,poisminimum.

3.Updatethetreestructurebysplittingthetreeleaftowiththeadditionalpixelpo.

7Similar

󰀁

󰀁

󰀁

calculationsforstoringthetreeusedininversehalftoningaredoneinAppendixI.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING18

Fig.12.GoldhillhalftonedwithTLUThalftoningtrainedonerror

diffusedimages.

D.Assigninghalftonevaluestotreeleaves

Wehavetofindthehalftonevaluesforeachtreeleafgivenatreestructureandadditionalpixellocations.Afterwards,thesehalftonevalueswillbeassignedashalftonevaluesintheTLUThalftoningalgorithm.Wewillusetrainingimagesinthisprocess,i.e.,halftoneimagesandcorrespondingcontoneimages.FirstwefindthetreeleavesforeachpixelinthetrainingsetusingtheTLUThalftoningalgorithminSec.VII-B.LetusdenotethesetofhalftonevaluesofpixelswhichhavethesametreeleaftasStwhereatisthesizeofSt.ThusSt={h1,h2,...,hat}.IftherearemoreonesthanzerosinSt,thenthehalftonevalueoftheleaf(ct)willbeone.Otherwiseitwillbezero.

E.TLUTexample

WehavechosenourinitialtemplatetoconsistofthefirstelevenelementsofthetemplateshowninTableXI.ThenwehaverefinedthetreeswiththetrainingsetasinSec.VIforLUThalftoningwithN17.Intheresultingtree,wehavea=11,b=2a+8+27310=524288.TheTLUThalftoneimageisshowninFig.12.Asitcanbeseenfromthefigure,theproblemswithveryhighandverylowgreylevelsinLUThalftonedimagesdonotoccurforTLUThalftoningalgorithm(seetheskyintheimage).Thetotalstoragecostisapproximately158KB.NotethatthisismuchlessthanstoragerequirementsofLUThalftoningwhich1MB.

WehavealsotrainedTLUTonDBShalftones.ThehalftonesareobtainedbyapplyingfiftystepsofDBSiterationsonFSerrordiffusedhalftones[14].OurinitialtemplateconsistsofthefirstelevenelementsofthetemplateshowninTableXI.TheparametersoftheTLUTwithN17areasfollows:a=11,b=2a+8+32768=557056.TheTLUThalftonedimageforGoldhillisshowninFig.13.Noticethatthequalityofthehalftoneimageisbetterthanerror

󰀁

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING19

Fig.13.GoldhillhalftonedwithTLUThalftoningtrainedonDBS

Images.

diffusedhalftoneimage(especiallyinthesky).ThedotsaremoreuniformlydistributedintheskyinTLUThalftonedimagewhereasartificialwormartifactsintheskycanbenoticedeasilyinerrordiffusedimages.8

VIII.Conclusion

Inthefirstpartofthepaper,wediscussedtreestructuredinversehalftoning.Thismethodgivesgoodresults,andthestoragerequirementsaremuchsmallercomparedtoLUTinversehalftoning.Herewehaveappliedouralgorithmtoerrordiffusedhalftones,disperseddotorderedditherhalftonesandclustereddotorderedditherhalftones.Othertypeofhalftones(e.g.,dotdiffusedimages[6])canalsobeinversehalftonedeasily.Inthesecondpartofthepaper,anewLUTbasedhalftoningmethodisdiscussed.Thealgorithmiscapableofproducinggoodqualityhalftones.Torefinethehalftones,wethenproposedtree-structuredLUThalftoning.WehavedemonstratedtheperformanceofouralgorithmbytrainingonerrordiffusedandDBSimages.ThecomplexityofTLUThalftoningishigherthantheerrordiffusionalgorithmbutmuchlowerthantheDBSalgorithm.Correspondingly,thehalftoneimagequalitywilllieinbetweenerrordiffusionandDBS.

Appendices

I.CalculationofstoragerequirementfortreestructuresusedinTLUTinversehalftoningAssumethatwehave2atreesandbtreeleavesinthetreestructure.Sincethecontonevaluesarestoredinthetreeleavesweneedbbytestostorethecontonevalues.Noticethat,everyadditionofanewpixeltothetreestructure

8The

imagescanbefoundatthewebsite[21]forbetterviewing.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING20

increasesthenumberoftreeleavesbyone.Sincethetreestructurewithbtreeleavesisobtainedbyaddingadditionalpixelstoaninitialtreewhichcontainsonly2atreeleaves,treestructurecontainsb−2aadditionalpixelsandweneedb−2amemoryunitstostorethelocationsoftheseadditionalpixels.

Inordertoexplainhowtostorethetreestructure,letusdefineatreenodestorageroutineasfollows:Inthisroutine,a“1”willbestoredifthetreenodeisaleaf.Ifthetreenodeissplit,thena“0”willbestoredandthiswillbefollowedbyapplyingthetreenodestorageroutinetotherightchildandthentotheleftchild.Thus,ifweapplythetreenodestorageroutinetotherootsof2abinarytreesinaspecificorder,wecanstorethetreestructure.Noticethat,weneedbbitstostorethetreestructurewhenb=2aandeachadditionofanadaptivepixeltothetreestructureincreasesthestoragerequirementby2bits.Thusweneed2b−2abitstostorethetreestructure.

II.SummaryofTemplateSelectionAlgorithminLUTinversehalftoning

Assumethatthenumberofcellstobeusedinthetemplateisfixed.OuraimwillbetochoosethebesttemplateofsizeM.Wewillsimplifythetemplateselectionproblembyrestrictingthecellsinafixedneighborhood,i.e.,NL.LetuscallthecellwhosecontonevalueispredictedasthecurrentandatemplatehavingaelementsasTea.AssumethatwehavePimageswhichhavesizesx1×y1,x2×y2,...,xP×yPinourtrainingset.WewillhavebothcontinuoustoneimagesDi(n1,n2)andhalftoneimagesHi(n1,n2)fori=1,2,...,Pinourtrainingsetwhere(n1,n2)denotesthecelllocationintheimages.Nowletusdefinethecorrelationbetweentwoimagesets{Dl}and{Fl}asfollows:

Cor(D,F)=

ylxl󰀂P󰀂󰀂l=1i=1j=1

󰀁P󰀁xl󰀁yl

(Dl(i,j)−mD)(Fl(i,j)−mF)

where

mD=

l=1

i=1j=1

󰀁Pl=1xlyl

Dl(i,j)

andsimilarlyformF.Herewegivetemplateselectionalgorithmisfivesteps:Step0.a=0.Tea=∅.

Step1.Letusdefine{Hl,(i,j)}tobetheshiftedversionsofhalftoneimages{Hl}:Hl,(i,j)(m,n)=Hl(m−p,n−r).ThencalculateCor(D,H(i,j))for(i,j)∈NL.Let(p,r)=argmax(i,j)∈NL|Cor(D,H(i,j))|.Includethecellinthetemplate:Tea=Tea−1+{(p,r)}.

Step2.Incrementaby1.DesignanLUTtableusingthetemplateTea−1toestimatecontonevalueofacellusingthecellsinthetemplateTea−1.UsethisLUTtabletoestimatethecontoneimages{Di}fromhalftoneimages{Hi}.Let󰀄uscalltheestimateimagesas{Dl}.

Step3.DesignanLUTtableusingthetemplateTea−1toestimatehalftonevalueofacell(i,j)cellsawayfromthecurrentcell.Inthedesign,majorityvoterulewillbeusedforeachpattern:If1’soccurmorethan0’sinaparticularpatternthen1willbeassignedforthatpattern;otherwise0willbeassigned.Letuscalltheestimatehalftonesas󰀄i,(p,r)}.Calculate{He󰀄i,(p,r)}forallthecellswhichareinthefixedneighborhoodbutnotinthetemplate.{He

ˆH−He󰀄(i,j))|.IncludetheStep4.CalculateCor(D,He(i,j))for(i,j)∈NL.Let(p,r)=argmax(i,j)∈NL|Cor(D−D,cellinthetemplate:Tea=Tea−1+{(p,r)}.

Step5.IfTeadoesnothaveMelementsgotostep1.

SUBMITTEDTOIEEETRANSACTIONSONIMAGEPROCESSING21

References

[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21]

M.AnalouiandJ.P.Allebach,“Newresultsonreconstructionofcontinuous-tonefromhalftone,”ICASSP,Vol.3,pp313-316,1992.Z.Fan,“Retrievalofimagesfromdigitalhalftones,”ISCAS,pp313-316,May1992.

S.HeinandA.Zakhor,“Halftonetocontinuous-toneconversionoferror-diffusioncodedimages,”IEEETrans.ImageProcessing,vol.4,2,pp208-216,February1995.

T.D.Kite,N.Damera-Venkata,B.L.Evans,andA.C.Bovik,“AFast,High-QualityInverseHalftoningAlgorithmforErrorDiffusedHalftones”,IEEETransactionsonImageProcessing,vol.9,no.9,pp.1583-1592,Sep.2000.

J.Luo,RicardodeQueiroz,andZhigangFan,“Arobusttechniqueforimagedescreeningbasedonthewavelettransform,”IEEETrands.SignalProcessing,vol.46,pp1179-1184,April1998.M.Me¸seandP.P.Vaidyanathan,“OptimizedHalftoningUsingDotDiffusionandMethodsforInverseHalftoning,”IEEETransactionsonImageProcessing,vol.9,no.4,pp.691-709,April2000.

—,“LookUpTable(LUT)InverseHalftoning,”ProceedingsofISCAS,2000.

—,“TemplateSelectionforLUTInverseHalftoningandApplicationtoColorHalftones,”ProceedingsofICASSP,2000.

—,“Lookuptable(LUT)Methodforinversehalftoning,”,IEEETransactionsonImageProcessing,vol.10,no.10,pp.1566-1578,April2000.

—,“Tree-structuredmethodforimprovedLUTinversehalftoning,”,ProceedingsofEUSIPCO,2000.—,“LookUpTableMethodforImageHalftoning,”,ProceedingsofICIP,2000.

T.MitsaandK.J.Parker,“DigitalHalftoningTechniqueUsingaBlueNoiseMask,“J.Opt.Soc.Am.A,Vol.9,No.11,pp.1920-1929,November1992.

A.N.NetravaliandE.G.Bowen,“Displayofditheredimages,”Proc.SID,vol.22,no.3,pp185-190,1981.

M.A.Seldowitz,J.P.Allebach,andD.E.Sweeney,“Synthesisofdigitalhologramsbydirectbinarysearch,”Appl.OptVol.26,pp.2788-2798,1987.

M.Y.TingandE.A.Riskin,“Error-diffusedimagecompressionusingabinary-to-gray-scaledecoderandpredictiveprunedtree-structuredvectorquantization,”IEEETrans.ImageProc.,vol.3,pp854-858,1994.

R.A.Ulichney,“DitheringwithBlueNoise,“ProceedingsofIEEE,vol.76,no.1,pp.56-79,Jan.1988.

R.A.VanderKam,P.A.Chou,andR.M.Gray,“Combinedhalftoningandentropyconstrainedvectorquantization,”inSIDDigestofTechnicalPapers,(Seattle,WA),pp223-226,May1993.

P.W.Wong,“Inversehalftoningandkernelestimationforerrordiffusion,”IEEETrans.ImageProcessing,vol.4,4,pp486-498,April1995.

P.W.Wong,“Entropyconstrainedhalftoningusingmultipathtreecoding,”IEEETrans.ImageProcessing,vol.6,4,November1997.Z.Xiong,K.RamchandranandM.Orchard,“Inversehalftoningusingwavelets,”ICIP,vol.I,pp569-572,1996.[Online].Available:http://www.systems.caltech.edu/mese/halftone/