; TeX output 2007.07.24:1736⟷O! /DvipsToPDF { 72.27 mul Resolution div } def /PDFToDvips { 72.27 div Resolution mul } def /HyperBorder { 1 PDFToDvips } def /H.V {pdf@hoff pdf@voff null} def /H.B {/Rect[pdf@llx pdf@lly pdf@urx pdf@ury]} def /H.S { currentpoint HyperBorder add /pdf@lly exch def dup DvipsToPDF /pdf@hoff exch def HyperBorder sub /pdf@llx exch def } def /H.L { 2 sub dup /HyperBasePt exch def PDFToDvips /HyperBaseDvips exch def currentpoint HyperBaseDvips sub /pdf@ury exch def /pdf@urx exch def } def /H.A { H.L currentpoint exch pop vsize 72 sub exch DvipsToPDF HyperBasePt sub sub /pdf@voff exch def } def /H.R { currentpoint HyperBorder sub /pdf@ury exch def HyperBorder add /pdf@urx exch def currentpoint exch pop vsize 72 sub exch DvipsToPDF sub /pdf@voff exch def } def systemdict /pdfmark known not {userdict /pdfmark systemdict /cleartomark get put} if ps:SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if endps:SDict begin [ /Title () /Subject () /Creator (LaTeX with hyperref package) /Author () /Producer (dvips + Distiller) /Keywords () /DOCINFO pdfmark end򽍠e̍Ncolor push Blackcolor push gray 0ps:SDict begin H.S endcolor push gray 0 color popps:SDict begin H.R endJps:SDict begin [ /View [/XYZ H.V] /Dest (page.1) cvn H.B /DEST pdfmark end color popG4 color pop,4NeJps:SDict begin [ /Count 6 /Dest (chapter.1) cvn /Title () /OUT pdfmark endYps:SDict begin [ /Count -0 /Dest (section.1.1) cvn /Title (Introduction) /OUT pdfmark endZps:SDict begin [ /Count -0 /Dest (section.1.2) cvn /Title (Related works) /OUT pdfmark enddps:SDict begin [ /Count -2 /Dest (section.1.3) cvn /Title (Optimum path classifier) /OUT pdfmark endZps:SDict begin [ /Count -0 /Dest (subsection.1.3.1) cvn /Title (Training) /OUT pdfmark end`ps:SDict begin [ /Count -0 /Dest (subsection.1.3.2) cvn /Title (Classification) /OUT pdfmark end_ps:SDict begin [ /Count -0 /Dest (section.1.4) cvn /Title (Learning Algorithm) /OUT pdfmark endTps:SDict begin [ /Count -0 /Dest (section.1.5) cvn /Title (Results) /OUT pdfmark endhps:SDict begin [ /Count -0 /Dest (section.1.6) cvn /Title (Conclusions and future work) /OUT pdfmark endUps:SDict begin [ /Page 1 /View [ /FitV ] /PageMode /UseOutlines /DOCVIEW pdfmark end1ps:SDict begin [ {Catalog} << >> /PUT pdfmark endps:SDict begin H.S endps:SDict begin 12 H.A endMps:SDict begin [ /View [/XYZ H.V] /Dest (Doc-Start) cvn H.B /DEST pdfmark endpapersize=614.295pt,794.96999ptps:SDict begin H.S endps:SDict begin 12 H.A endMps:SDict begin [ /View [/XYZ H.V] /Dest (chapter.1) cvn H.B /DEST pdfmark end color push Black color pop`GGecrb1728DesignJofrobustJpatternclassiersbasedonoptimfum-pathk+forests`V eccc1000JoZoP.P apaA^T2ecrm07001F 1 ecrm1000,U AlexandreX.Fhalc㐵Zop\^1u,U P aZuloA.V.Mirandan^1sH, CelsoT.N.Suzuki_l^1g̾andU NelsonD.A.Mascarenhas6^2F񍍟-:(kTecsl06001Iecsl0800State(UnivÒersityofCampinas,InstituteofComputing,Campinas,Brazil )&ecst0800jpaulo,afalcao@ic.unicamp.br,paÒvmbr@yahoset.ThemethoAdisrobusttooutliers,lhandlesnon-separable;mclasses,$andcanoutpAerformsupportvclassierisbasedonlabGeledsamplesfromtrainingandevqaluationsets.4AtestsetwithunseensamplesU isusedtoassessthepGerformanceoftheclassier. ThehAtraininghBsamplesarenoGdesofacompletegraphinthesamplefeaturespace(allpairsofnoGdesareconnectedbyonearc).KSeeFigurecolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 01 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (figure.1.1) cvn H.B /ANN pdfmark end color popa.KThearcsareyvweightedbythedistancebGetweenyuthefeaturevectorsoftheirnoGdes.AGIsetGofprototypGesG(keyGsamples)isobtainedfromthetrainingset.HW*edene.ap}/ath-costpzfunction/based.on.arcweights,6whichassigns.toanypathinDtheEgraphthecostofconsideringallsamplesalongthepathasbGelongingto0a0sameclass(e.g.,86function b> cmmi10f 0ercmmi7maxwhichassignsthemaximum0arcweightNcolor push BlackG4 color pop*⟷ps:SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end򽍠e̍Ncolor push Blackcolor push gray 0ps:SDict begin H.S endcolor push gray 0 color popps:SDict begin H.R endJps:SDict begin [ /View [/XYZ H.V] /Dest (page.2) cvn H.B /DEST pdfmark end color popG4 color pop,4e̍Nalong+thepath).4W*ethenapplytheIFTalgorithm[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 03 color popps:SDict begin H.R endtps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Falcao:04) cvn H.B /ANN pdfmark end color pop],topartitionthegraph NintoanoptimumpathforestroGotedattheprototypGes(Figurecolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 01 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (figure.1.1) cvn H.B /ANN pdfmark end color popb).^Thatis,NthepprototypGescompeteamongthemselvesqandeachprototypGedenesanNoptimum*pathtree,Fmwhose+noGdesaresamplesmorestronglyconnectedtoNthatLprototypGethantoanyotherMroGot,accordingtothatpath-costfunction.NThetrainingessentiallyconsistsofbuildingthisoptimumpathforest,whereNthesamplesinagivenoptimumpathtreeareassumedtohavethesameNlabGelU oftheirrootprototype.8Nf!color push Black(ߍps:SDict begin H.S endps:SDict begin 12 H.A endQps:SDict begin [ /View [/XYZ H.V] /Dest (subfigure.1.1) cvn H.B /DEST pdfmark endZ&APSfile="./images/figure1a.pdf" llx=0 lly=0 urx=72 ury=72 rwi=847 @"-0"ecrm0800(a)y@ps:SDict begin H.S endps:SDict begin 12 H.A endQps:SDict begin [ /View [/XYZ H.V] /Dest (subfigure.1.2) cvn H.B /DEST pdfmark endy@APSfile="./images/figure1b.pdf" llx=0 lly=0 urx=72 ury=72 rwi=847 I(b)uZps:SDict begin H.S endps:SDict begin 12 H.A endQps:SDict begin [ /View [/XYZ H.V] /Dest (subfigure.1.3) cvn H.B /DEST pdfmark enduZAPSfile="./images/figure1c.pdf" llx=0 lly=0 urx=72 ury=72 rwi=847 &(c)ney@ps:SDict begin H.S endps:SDict begin 12 H.A endQps:SDict begin [ /View [/XYZ H.V] /Dest (subfigure.1.4) cvn H.B /DEST pdfmark endy@APSfile="./images/figure1d.pdf" llx=0 lly=0 urx=72 ury=72 rwi=847 I(d)RFigur$e1.`color push gray 0ps:SDict begin H.S endcolor push gray 0 color popps:SDict begin H.R endNps:SDict begin [ /View [/XYZ H.V] /Dest (figure.1.1) cvn H.B /DEST pdfmark end color pop`(a)UCompleteVwproblemconsists=ofusingS,Ҳ(v[;d),ѵZ1`andZ2to=pro0jectanoptimalNcolor push BlackG4 color popOt⟷ps:SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end򽍠e̍Ncolor push Blackcolor push gray 0ps:SDict begin H.S endcolor push gray 0 color popps:SDict begin H.R endJps:SDict begin [ /View [/XYZ H.V] /Dest (page.5) cvn H.B /DEST pdfmark end color popG4 color pop,4e̍NclassierdwhichcanpredictthecorrectlabGel(s)ofanysamples}2~Z3|s. NW*epropGoseaclassierwhichcreatesadiscreteoptimalpartitionoftheNfeaturespacesuchthatanysamples/2Z3canbGeclassiedaccordingtoNthis{partition.ŐThispartitionisanoptimumpathforestz(OPF)^computedNinU <^nƞbytheimageforestingtransform(IFT)algorithm[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 03 color popps:SDict begin H.R endtps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Falcao:04) cvn H.B /ANN pdfmark end color pop].NLet5(Z1|s;A)5bGeacompletegraphwhosethenoGdesarethesamplesinZ1NandanypairofsamplesdenesanarcinA=Z1"Z1Fq(Figurecolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 01 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (figure.1.1) cvn H.B /ANN pdfmark end color popa).CThearcsNdoQnotneedtoRbGestoredandsothegraphdoesnotRneedtobeexplicitlyNrepresented.@A͖path͵isͶasequenceofdistinctsamples=hs1|s;s2;:::;sk됸i,NwhereҸ(siTL;si+1 tO)w2Aҹfor1ik61.IAҘpathissaidtrivial0ifP=hs1|si.NW*eassigntoeachpath5޹acostf([ٲ)givenbyapath-costfunctionf.0ANpathUʹissaidoptimumUiff([ٲ)sf([ٟ^ O!cmsy70*)UforUanyotherpath[ٟ^0*,V$whereɹandN[ٟ^0fenduSatuTasamesamplesk됹.W*ealsodenoteby3NYhs;titheconcatenationNofU apathwithterminusatsandanarc(s;t).NThe}OPFKalgorithm~maybGeusedwithanysmo}/othӹpath-costfunctionNwhichcangroupsampleswithsimilarpropGerties[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 03 color popps:SDict begin H.R endtps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Falcao:04) cvn H.B /ANN pdfmark end color pop].;gAfunctionfdissmoothNinP(Z1|s;A)whenforanysampletj92Z1,gtherePexistsanoptimumpathNendingU attwhicheitheristrivial,orhastheformZ8hs;tiwherePcolor push Black color popPf(!Dz)f([ٲ),NPcolor push Black color popPvisU optimum,MPcolor push Black color popPforU anyoptimumpath!ǟ^0E endingats,f(!ǟ^0(8hs;ti)=f([ٲ).NW*ewilladdressthepath-costfunctionfmaxw,bGecauseofitstheoretical NpropGertiesU forestimatingoptimumprototypGes.U!ps:SDict begin H.S endps:SDict begin 12 H.A endNps:SDict begin [ /View [/XYZ H.V] /Dest (equation.1) cvn H.B /DEST pdfmark endfmaxw(hsi)K=1i^u cmex10:>k0YˋifU s2S, 37>k+1Yˋotherwise37˗fmaxw(8hs;ti)K=1imaxD ߸ffmaxw([ٲ);d(s;t)gcolor push Black(1) P color popNsuchFthatfmaxw([ٲ)computestheGmaximumdistancebGetweenadjacentsam-NplesU in[ٹ,whenisnotatrivialpath.NThe'OPFalgorithm&assignsoneoptimumpathPc^s(s)fromStoeveryNsampleеs2Z1|s,forminganoptimumpathforestP ^(afunctionwithnoNcycles whichassignstoeachs2Z1|snSWitspredecessorPc(s)inP^s(s)oraNmarkernilnwhen s$U2$TS, asshowninFigurecolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 01 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (figure.1.1) cvn H.B /ANN pdfmark end color popb).ILetRDz(s)$T2$US bGetherootNof-Pc^s(s),whichcanbGereachedfromPc(s).?TheOPFalgorithmcomputesNforeachs a2Z1|s,thecostC(s)ofPc^s(s),thelabGelL(s) a=(RDz(s)),andtheNpredecessorU Pc(s),asfollows.Nps:SDict begin H.S endps:SDict begin 12 H.A endOps:SDict begin [ /View [/XYZ H.V] /Dest (algorithm.1) cvn H.B /DEST pdfmark end `Mcolor push Black7]f ecbx1000Algorithm1. color popU OPFalgorithm#捍8C) eccc0900Input:A`A'-lab$eled4trainingsetZAacmr61*,&prototypesS3 cmsy9Z1Gandthe3pair(vR;d) A`forNfe$aturevectoranddistancecomputations.Output:A`OptimumNp$athforestPH,costmapCandlabelmapL. Auxiliar0 y:A`PriorityNqueueQandc$ostvariablecst.Ncolor push BlackG4 color poplM⟷ps:SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end򽍠e̍Ncolor push Blackcolor push gray 0ps:SDict begin H.S endcolor push gray 0 color popps:SDict begin H.R endJps:SDict begin [ /View [/XYZ H.V] /Dest (page.6) cvn H.B /DEST pdfmark end color popG4 color pop,4e̍Ncolor push Black color popN1. ;F:or$eacC(s),$doN7.Lτ 0, ␟1Compute$cst maxfC(s);d(s;t)g.N8.Lτ 0, ␟1If$cst{QC(s)(t)Q2S-=^totpassingthrough$s-=UT. color pop㍒NThepdoptimumpeprototypGesarethepeclosestelementspeintheMSTp^withdif-NferentQlabGelsinPZ1|s.ByremovingtheParcsbGetweendierentclasses,PtheirNadjacentsamplesbGecomeprototypGesinS^ *6andAlgorithmcolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 01 color popps:SDict begin H.R endqps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (algorithm.1) cvn H.B /ANN pdfmark end color popcancomputeNanoptimumpathforestwithnoneclassicationerrorsinZ1~(Figurecolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 01 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (figure.1.1) cvn H.B /ANN pdfmark end color popb),Nwhich"*can")bGeexplainedby")thetheoreticalrelationbGetween")minimumspan-NningptreespandtheoptimumpathtreeobtainedbyOPFpwithfmax߹[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 019 color pop `ps:SDict begin H.R end `tps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Cousty:07) cvn H.B /ANN pdfmark end color pop].NNote9uthat,ragiven9vclassmaybGerepresentedbymultipleprototypGes(i.e.,NoptimumRpathRtrees)andtheremustexistatleastoneprototypGeperRclass.NÜps:SDict begin H.S endps:SDict begin 12 H.A endTps:SDict begin [ /View [/XYZ H.V] /Dest (subsection.1.3.2) cvn H.B /DEST pdfmark end color push Black3.2 ( color popClassication F*orFWanyFVsamplet2Z3|s,|weFWconsiderallFVarcsconnectingtwithsampless2Z1|s,asEthoughtwerepartoftheEgraph(Figurecolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 01 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (figure.1.1) cvn H.B /ANN pdfmark end color popc).D ConsideringallpGossiblepaths&fromS^ܗto't,wewish&tondtheoptimumpath'Pc^s(t)fromS^ܗandlabGelCtCwiththeclass(RDz(t))ofitsmoststronglyconnectedprototypGeRDz(t)2S^䑹(Figurecolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 02 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (figure.1.2) cvn H.B /ANN pdfmark end color popb).=+This pathcanbGeidentiedincrementally*,׆byevqaluatingtheoptimumU costC(t)asHAğps:SDict begin H.S endps:SDict begin 12 H.A endNps:SDict begin [ /View [/XYZ H.V] /Dest (equation.2) cvn H.B /DEST pdfmark endHAĵC(t)=minqƸfmaxvfC(s);d(s;t)gg;ȸ8s2Z1|s::n(2)Let?thenoGdes^_2Z1betheonethatsatisestheabove?equation?(i.e.,vthepredecessor2Pc(t)2intheoptimumpathPc^s(t)).f GiventhatL(s^)=(RDz(t)),thekclassicationsimplyassignsL(s^)asthekclassoft.AnerroroGccurswhenU L(s^)6=(t). KՍSimilar˥proGcedureˤisappliedforsamplesintheevqaluationsetZ2|s.CInthiscase,wUhowever,wVwep}wouldp~liketousesamplesofZ2tolearnthedistributionNcolor push BlackG4 color popّ⟷ps:SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end򽍠e̍Ncolor push Blackcolor push gray 0ps:SDict begin H.S endcolor push gray 0 color popps:SDict begin H.R endJps:SDict begin [ /View [/XYZ H.V] /Dest (page.8) cvn H.B /DEST pdfmark end color popG4 color pop,4e̍NofDtheEclassesinthefeaturespaceandimproveDthepGerformanceoftheOPF Nclassier.Neps:SDict begin H.S endps:SDict begin 12 H.A endOps:SDict begin [ /View [/XYZ H.V] /Dest (section.1.4) cvn H.B /DEST pdfmark endO5color push Black4. ? color popLearningAlgorithmy⍹The-pGerformanceoftheOPF classierimproves-whentheclosestsamplesfromdierentclassesareincludedinZ1|s,bGecausethemethoGdndsproto-typGesthatwillworkassentinelsinthefrontierbGetweenclasses.?W*epropGoseaxlearningalgorithmtoidentifybGetterprototypGesfromsamplesofZ2tthathaveoneverobGeeninZ1(Algorithmcolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 02 color popps:SDict begin H.R endqps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (algorithm.2) cvn H.B /ANN pdfmark end color pop).Firstlywegivepreferenceotoreplaceirr}/elevantW۹sampleseofZ1ᅹbyerrorsinZ2|s,iandsecondlyothersamplesofZ2arereplacedbyirr}/elevantsamplesofZ1|s.T*InbGothcases,weneverletasam-ple*of+Z2returntoZ1|s.IftheapplicationdidnotimpGoseanylimitationinjZ1|sj,4theprototypGescouldbefoundfromZ1R[ߵZ2` withnoneclassicationerrorsinbGothsets.D*ThelearningalgorithmessentiallytriestoidentifytheseprototypGesU fromafewiterationsofclassicationoverZ2|s. O5TheBalgorithmCoutputsale}/arningcurveZoverTѹiterations(LinesB229),which5repGortstheaccuracyvqaluesof4eachinstanceofclassierduringlearning,andthenalOPFVclassier.<Lines47executetrainingandinitialize:theauxiliaryarraysandlists.!Theclassicationofeachsamplet2Z2yisqpGerformedinLinesq8pp18,updatingauxiliaryarrays.%xTheconditioninU Line10indicatesthattismisclassied.In8orderto8deneirrelevqantsamples,pweconsiderall8rightandwrongclassicationssinZ2|s.yWhentti2jZ2 iscorrectly/incorrectlyclassied,шweaddJEonetoJDthenumbGerJEofright/wrongclassications,LqNRDz(rG)orNWc(rG),Lqofevery(sampler52Z15intheoptimumpath)Pc^s(t)fromRDz(t)2S^噹tos^R (Lines1418).7aAdditionally*,ɣLinesò1113ùupGdatethenumberoffalsepositiveandfalsenegativearrays,gFcPandFN,fforaccuracycomputation,gandinserttinU thelistLE((t))oferrorsifthasneverbGeeninZ1ѓ(t62TcRǹ).ps:SDict begin H.S endps:SDict begin 12 H.A endOps:SDict begin [ /View [/XYZ H.V] /Dest (algorithm.2) cvn H.B /DEST pdfmark end icolor push BlackAlgorithm2. color popU LearningalgorithmD͑捍Input:A`TJr$aining9andevaluationsetslabeledby,Z1andZ2*,numberT A`ofiter$ations,2tandthepair(vR;d)forfeaturevectoranddistanceA`c$omputations."Output:A`L$earningw0curvew/LandthelastOPFw%classier,{r$epresentedbyw0the A`pr$edecessorNmapPH,c$ostmapC,andlabelmapL.Auxiliar0 y:A`FJalseqp$ositiveandfalsenegativearrays,zlFHPmandFN,zlofsizesc, A`lists,uLIIandLE2,ofirr$elevantsamplesanderrorsamplesforeachA`class,Jarr$aysMpfortheMonumberofrightandMowrongclassications,A`NR7andNWH,ofsizesjZ1*j,variablesrforsample,andsetTHRA`toNavoidsamplesofZ2xr$eturntoZ1*.GVocolor push Black color pop1. ;THR ;. 2. +F:or$eac(s) 0$andNWH(s) 0. N6.Lτ ␟1F:or$eac,thenLE2((t)) LE((t))8[ftg.N14.Lτ 0, ␟1While$rӍ6=nil&9,doN15.Lτ 0, Ä0, ␟nNWH(rA) NWH(rA)8+1$andrӍ P(rA).N16.Lτ 0, ␟1ElseN17.Lτ 0, ␟1While$rӍ6=nil&9,doN18.Lτ 0,Ä0, ␟nNR>(rA) NR>(rA)8+1$andrӍ PH(r).N19.Lτ ␟1Compute$L(I[)bNR>(s),$thenN22.Lτ 0,Ä0, ␟nLI[((s)) LI((s))8[fsg.N23.Lτ ␟1F:or$eac0andjLE2(i)j>0,doN25.Lτ 0, ␟1LI[(i) LI(i)nfsg$andLE2(i) LE(i)nftg.N26.Lτ 0, Ä ␟nReplace$s2Z1?b0,doN28.Lτ 0, ␟1LI[(i) LI(i)nfsg.N29.0, ␟nFind$t2Z2*nTHR>,with(t)=i,andreplaceitb&ps:SDict begin H.S endps:SDict begin 12 H.A endNps:SDict begin [ /View [/XYZ H.V] /Dest (equation.5) cvn H.B /DEST pdfmark end>&L(I)=K2c8Pލ c% i=1E(i)KfeBhR (֍;2cJ\=18lPލ Nc% Ni=1EE(i)lfe,ۘ (֍2c(5)Ncolor push BlackG4 color pop Ή⟷ps:SDict begin /product where{pop product(Distiller)search{pop pop pop version(.)search{exch pop exch pop(3011)eq{gsave newpath 0 0 moveto closepath clip/Courier findfont 10 scalefont setfont 72 72 moveto(.)show grestore}if}{pop}ifelse}{pop}ifelse}if end򽍠e̍Ncolor push Blackcolor push gray 0ps:SDict begin H.S endcolor push gray 0 color popps:SDict begin H.R endKps:SDict begin [ /View [/XYZ H.V] /Dest (page.10) cvn H.B /DEST pdfmark end color popG4 color pop,4e̍NLinesZl2022identifyZkasirrelevqantsamplesZkinZ1߹thosewithnumbGer NofqincorrectclassicationshigherthanthenumbGerqofcorrectclassications.NLines22329removeelementsfromthelists1ofirrelevqantsamplesanderrors,NLIR]and|LE,6for{eachclass,and|rstreplaceerrorsbyirrelevqant|samplesthenNreplacetheremainingirrelevqantsamples(ifany)byothersamplesofZ2uthatNhaveU neverbGeeninZ1|s. NOutliersdegradethepro0jectofanyclassier.VTheywillbGeusuallyiden-NtiedasirrelevqantprototypGes,AbeingmovedfromZ1toZ2|s.Finally*,ALineN30pGerformsthetrainingoverthelastsetZ1;tooutputthedesignedOPFNclassier.NAfter5learning,<7theclassicationofanysamplet2Z3pis5donebysimplyNndings^Jܸ2Z1^wthatsatisesEquationcolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 02 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (equation.2) cvn H.B /ANN pdfmark end color popandassigninglabGelL(s^)astheNclassU oft.Nkps:SDict begin H.S endps:SDict begin 12 H.A endOps:SDict begin [ /View [/XYZ H.V] /Dest (section.1.5) cvn H.B /DEST pdfmark end color push Black5. ? color popResultsW*excomparethexOPFxclassierwithsuppGortvectormachinesx(SVM[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 04 color popps:SDict begin H.R endtps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Vapnik:92) cvn H.B /ANN pdfmark end color pop])usingifourdatabaseswithoutliersiandnon-separableclasses:Cone-torusfrom[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 09 color popps:SDict begin H.R endvps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Kuncheva:04) cvn H.B /ANN pdfmark end color pop],Painteddatabase(Figurecolor push rgb 1 0 0ps:SDict begin H.S endcolor push rgb 1 0 03 color popps:SDict begin H.R endpps:SDict begin [ /Color [1 0 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (figure.1.3) cvn H.B /ANN pdfmark end color popa),MPEG-7shapGedatabase[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 015 color pop `ps:SDict begin H.R end `tps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.MPEG-7:02) cvn H.B /ANN pdfmark end color pop],andWM/GM8x(white8matter/graymatter)database[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 01 color popps:SDict begin H.R endwps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Collins:1998) cvn H.B /ANN pdfmark end color pop].Thecone-torusdatabasecontains400samplesand3non-separableclasseswhilethepainteddatabasecontainsC5,867Dsampleswithoutliersand4classes.-InbGothcases,thefeaturevectorsMarethesample(x;y[ٲ)coGordinates.TheMPEG-7databasecontains1,400a2DaqshapGesand70classes.ET*oaincreaseoverlapa(diculty)bGetweenclasses,vwe1simply2adoptthe126mostsignicantcoGecients2intheF*ouriertransformoftheshapGesasfeaturevector.^)TheWM/GM databasecontains1.5MvoxelsofWMandGM(2classes)fromMR-T1imagesofphantomswith~!vqariouslevelsofnoiseand~"inhomogeneitytoproGduceoutliers.Theimages!andground!truthareavqailablefrom[color push rgb 0 1 0ps:SDict begin H.S endcolor push rgb 0 1 01 color popps:SDict begin H.R endwps:SDict begin [ /Color [0 1 0] /H /I /Border [0 0 0] /Subtype /Link /Dest (cite.Collins:1998) cvn H.B /ANN pdfmark end color pop],Tandthefeaturevectoristhelowestandhighestvqaluesaroundthevoxel,anditsintensityvqalue.6 InallU cases,functiondistheEuclideanmetric.Kljucolor push Blackps:SDict begin H.S endps:SDict begin 12 H.A endQps:SDict begin [ /View [/XYZ H.V] /Dest (subfigure.3.1) cvn H.B /DEST pdfmark endhEu7PSfile="painted.pdf" llx=0 lly=0 urx=72 ury=72 rhi=850 i?(a)(ps:SDict begin H.S endps:SDict begin 12 H.A endQps:SDict begin [ /View [/XYZ H.V] /Dest (subfigure.3.2) cvn H.B /DEST pdfmark end(GPSfile="report_opf/accuracy_opf.pdf" llx=0 lly=0 urx=72 ury=72 rhi=992 Ȣ(b)Figur$eN3.?color push gray 0ps:SDict begin H.S endcolor push gray 0 color popps:SDict begin H.R endNps:SDict begin [ /View [/XYZ H.V] /Dest (figure.1.3) cvn H.B /DEST pdfmark end color pop?(a)$P> /Subtype /Link H.B /ANN pdfmark end color pop>.ps:SDict begin H.S endps:SDict begin 9.5 H.A endJps:SDict begin [ /View [/XYZ H.V] /Dest (Item.2) cvn H.B /DEST pdfmark end color push Black[ps:SDict begin H.S end2ps:SDict begin 9.5 H.A endPps:SDict begin [ /View [/XYZ H.V] /Dest (cite.Duda:00) cvn H.B /DEST pdfmark end]? color popwR.O.h4Duda,f3PJ.E.Hart,f4andeD.G.h5Stork,PatternClassication,2ndeed.,Wiley-wInÒterscience,(2000. ps:SDict begin H.S endps:SDict begin 9.5 H.A endJps:SDict begin [ /View [/XYZ H.V] /Dest (Item.3) cvn H.B /DEST pdfmark end color push Black[ps:SDict begin H.S end3ps:SDict begin 9.5 H.A endRps:SDict begin [ /View [/XYZ H.V] /Dest (cite.Falcao:04) cvn H.B /DEST pdfmark end]? color popwA.X.:FJalco,8HJ.: Stol,and7R.A.Lotufo,8GThe\imageforestingtransform:]theory,walgorithms,Landapplications,(IEEETJrans.onPAMI26(2004),no.1,1929.ps:SDict begin H.S endps:SDict begin 9.5 H.A endJps:SDict begin [ /View [/XYZ H.V] /Dest (Item.4) cvn H.B /DEST pdfmark end color push Black[ps:SDict begin H.S end4ps:SDict begin 9.5 H.A endRps:SDict begin [ /View [/XYZ H.V] /Dest (cite.Vapnik:92) cvn H.B /DEST pdfmark end]? color popwB.E.Boser,I.M.GuyÒon,and}V.N.VJapnik,A trainingalgorithmforoptimalmarginwclassiers,&Proofthe23rdinÒternationalconferenceonMachinelearning,2006,wpp.(921928.ps:SDict begin H.S endps:SDict begin 9.5 H.A endKps:SDict begin [ /View [/XYZ H.V] /Dest (Item.14) cvn H.B /DEST pdfmark end color push Black[ps:SDict begin H.S end14ps:SDict begin 9.5 H.A endQps:SDict begin [ /View [/XYZ H.V] /Dest (cite.Panda:06) cvn H.B /DEST pdfmark end] color popwN.\PÒanda,xE.Y.Chang,andKG.WJu,yConceptboundarydetectionforspeedingupwSVMs,ICML'06:WProaLibraryforSupportVWectorMachines,)2001.Soft-wwÒare(av$ailableatcolor push rgb 0 0 1ps:SDict begin H.S endcolor push rgb 0 0 1http://www.csie.ntu.edu.tw/~cjlin/libsvm color pop`r ps:SDict begin H.R end`ps:SDict begin [ /H /I /Border [0 0 0] /Color [0 1 1] /Action << /Subtype /URI /URI (http://www.csie.ntu.edu.tw/~cjlin/libsvm) >> /Subtype /Link H.B /ANN pdfmark end color pop.ps:SDict begin H.S endps:SDict begin 9.5 H.A endKps:SDict begin [ /View [/XYZ H.V] /Dest (Item.18) cvn H.B /DEST pdfmark end color push Black[ps:SDict begin H.S end18ps:SDict begin 9.5 H.A endUps:SDict begin [ /View [/XYZ H.V] /Dest (cite.Arica:BAS:03) cvn H.B /DEST pdfmark end] color popwN.†AricaandF.…T.Y.VJural,WBAS:@APerceptualShapeDescriptorbasedonthewBeamAngleStatistics,VPÒatternLRecognitionMLetters24(2003),Wno.9-10,16271639.ps:SDict begin H.S endps:SDict begin 9.5 H.A endKps:SDict begin [ /View [/XYZ H.V] /Dest (Item.19) cvn H.B /DEST pdfmark end color push Black[ps:SDict begin H.S end19ps:SDict begin 9.5 H.A endRps:SDict begin [ /View [/XYZ H.V] /Dest (cite.Cousty:07) cvn H.B /DEST pdfmark end] color popwJ.CoustÒy,YG.Bertrand,L.Naxjman,andHM.Couprie,XWWatersheds,OminimumOspan-wningLforests,andthedropofwaterprinciplen(2007),(no.IGM2007-01.Ncolor push BlackG4 color pop5;[{ <&ectt0800;Yecbx0800: {}ecti08008C) eccc09007]f ecbx10003 cmsy925" cmmi91o cmr90"ecrm0800/HЃ ecti1000.!N ecbx1200,, ecti0900+u ecbx0900*. ecrm0900)&ecst0800(kTecsl0600!q% cmsy6;cmmi6Aacmr6Iecsl0800T2ecrm0700V eccc1000`GGecrb1728 1 ecrm1000 !", cmsy10 O!cmsy7 b> cmmi10 0ercmmi7K`y cmr10ٓRcmr7u cmex10El