Seite - 81 - in Document Image Processing

J. Imaging 2018,4, 37 Foragivenquery, itneedsenoughsamples fromthequeryclass forgettingnovelglobalprincipal alignments. However, in anydatabase, the number of samples for frequent classes dominate the numberofsamples for rareclasses. Theglobalprincipalalignments for frequentqueriesare likely to dominatetherarequeries. Therefore, theprecomputedglobalprincipalalignmentsinFastapproximate DTWmaynotcaptureall thecorrelations for rarequeryclasses. In theproposedQSDTWdistance, theglobalprincipalalignmentsare learnedfromthengrams (cut-portions)of frequentclasses. These n-gramsare inabundanceandalsosharedwithrarequeries, thus thereareenoughn-gram samples for learningthecut-specificalignments. Thecomputedqueryspecificalignments for thecut-portions outperformthealignmentsobtainedfromFastapproximateDTW. Table4.Retrievalperformanceofvariousmethods for rarequeries. Dataset RetrievalResults (mAP)forRareQueries UsingNearestNeighbourClassifier UsingDQC(ExemplarSVM) DTW FastApprxDTW [20] QSDTW Euclidean FastDTW [30] sDTW aNN FastDTW QSDTW QE D1 0.82 0.77 0.83 0.69 0.75 0.91 0.90 0.91 0.95 0.98 D2 0.81 0.74 0.80 0.65 0.74 0.89 0.90 0.90 0.94 0.95 D3 0.73 0.66 0.71 0.59 0.62 0.80 0.78 0.80 0.91 0.96 It is worthmentioning that FastDTW [30], which is an approximationmethod, attempts to compute theDTWdistance inanefficientway. Itdoesnotconsidercutportionsimilarities,whichmay be influencedbyvariousprintingstyles. Hence, theseapproachesarenotapplicable inoursetting where thedatasetcanhavewordsprinted invariedprintingstyles,andthuscanresult inamarked degradationofperformanceforrarequeries. SincequeryspecificDTWfindstheapproximateDTW distanceusingcut specificprincipal alignments, it canexploitpropertieswhichcannotbeusedby otherDTWapproximationmethods. Tosummarize, theexperimentsdemonstrate that theproposedqueryspecificDTWperformswell forbothfrequentandrarequeries. Sinceit is learningthealignmentsfromngrams, itperformscomparable tosDTWdistanceforrarequeries. Forsomequeries, itperformedbetter thantheDTWdistance. 5.5. Results forRareQueryExpansion Theresults forQSDTWenhancedwithqueryexpansion (QE)usingfivebestmatchingsamples arealsogiven inTable4. It isobservedthatQEfurther improves theperformanceofourproposed method. Toshowtheeffectivenessofqueryexpansion,wehavecomputed theaverageof theDTW distancebetweenthegivenqueryandalldatabasesamples thatbelongedto thequeryclass. Likewise, wecomputedtheaverageof theDTWdistancefor thereformulatedquery. Table5showsacomparison of theaveragedDTWdistancefor thegivenqueryandthereformulatedqueryusing2,5,7,and10most similar (to thequery)samples fromthedatabase. Fromtheresults,wecanobserve thatcomparedto thegivenquery, thereformulatedqueryusingfivebestmatchingsamplesgives the lowestaveraged DTWdistance to the samples from the query class. Thismeans the reformulatedquery is a good representative for thegivenquery.However,usingninebestmatchingsamples for reformulatingthe query leads toahigheraverageofDTWdistances. Thismeanssomeirrelevantsamples to thequery arecomingin the topsimilarsamples. Table5.Thetablegives theaveragesumofDTWdistance for thegivenqueryandthereformulated querywithvaryingnumberofsamplesn fromthequeryclass. AverageofDTWDistance Forgivenquery ForReformulatedQuery n=2 n=5 n=7 n=10 2.67±0.19 2.69±0.23 2.52±0.13 2.58±0.21 2.94±0.29 81