Seite - 80 - in Document Image Processing

J. Imaging 2018,4, 37 performscomparablywithDTWforall thedatasets. ItperformssuperiorcomparedtotheFastDTW, FastapproximateDTWdistance [20]andperformssignificantlybettercomparedtoEuclideandistance. ForDQC,we experimentedwith four options for indexing the frequent classmean vectors: subsequenceDTW[18] (sDTW),approximatenearestneighborNNDQC[18] (aNN),FastDTW,andQS DTW.Weuse thecut-portionsobtainedfromthemeanvectorsof themost frequent1000wordclasses for (i) computingthecut-specificprincipalalignments incaseofQSDTW, (ii) computingtheclosest matching cut-portion (i.e., onewith the smallest distance, which can be Euclidean or DTW)with acut-portionfromthequeryvector, incaseofaNNorFastDTW. However, sincesDTWhascomputationalcomplexityO(n2),werestrict thenumberof frequent wordsusedfor indexingto100. TheQSDTWdistance improves theperformanceof theDQCclassifier. This ismainlydueto the improvedalignments involvedin theQSDTWdistance. Thequeryspecific alignmentsbettercapture thevariations in thequeryclass.Moreover,unlike thecaseofsDTWdistance, theQSDTWdistancehas linearcomplexityandthereforeweareable to indexall the frequentmean vectors in theDQCclassifier. Thus, theproposedmethodofQSDTWenhances theperformanceof the DQCclassifier [18]. For frequent queries, the experiments revealed that the QS DTW gets the global principal alignments fromthemeanvectorof thesame(query)class. Since thealignmentsarecomingfromthe queryclass, itgivesminimumdistanceonly for thesampleswhichbelongto itsownclass. Therefore, the retrieved samples largely belong to the query class. The performance is therefore improved comparedtosDTWdistance. Incontrast, theFastapproximateDTWdistance [20]computes theglobal principalalignmentsusingall samples in thedatabase,withoutexploitinganyclass information. The computedglobalprincipalalignments, therefore, includealignments fromclasses thatmaybedifferent fromthequeryclass. For this reason, itperforms inferior to theproposedDTWdistance. Table3.Retrievalperformanceofvariousmethods for frequentqueries. Dataset RetrievalResults (mAP)forFrequentQueries UsingNearestNeighbourClassifier UsingDQC(ExemplarSVM) DTW FastApprxDTW [20] QSDTW Euclidean FastDTW [30] sDTW aNN FastDTW QSDTW D1 0.94 0.92 0.92 0.81 0.91 0.98 0.98 1 1 D2 0.91 0.89 0.9 0.75 0.87 0.96 0.95 0.97 0.99 D3 0.83 0.79 0.81 0.67 0.76 0.91 0.92 0.93 0.96 5.4. Results forRareQueries Thefaster indexingofferedbytheuseofQSDTWwithDQCallowsus tomakeuseof themean vectors of all the 1000 frequent classes. This givesus amuch improvedperformance of theDQC onrarequeries, comparedtosDTW[18]whichusesmeanvectors from100frequentclasses. Table4 showstheretrievalperformanceofDQCwithanearestneighbourclassifierusingdifferentoptions fordistancemeasures. Theperformance is showedintermsofmeanaverageprecision(mAP)values onrarequeries fromthreedatasets. For thenearestneighbor classifier,weexperimentedwithfive distancemeasures: naiveDTWdistance, Fast approximateDTWdistance [20], query specificDTW (QSDTW)distance,FastDTW[30]andEuclideandistance.Wesee thatQSDTWperformscomparably withDTWdistance forall thedatasets. Itperformssuperiorcomparedto theFastapproximateDTW distance [20],FastDTWandsignificantlybettercomparedtoEuclideandistance. For DQC, we observe that QS DTW improves the performance compared to sDTW. This improvementofQSDTWoversDTWismoreforrarequeriescomparedtothat for frequentqueries. This showsthatQSDTWcanbeusedfor faster indexingforbothfrequentandrarequeries. Forrarequeries, thequeryspecificDTWdistanceoutperformsFastapproximateDTW[20]distance. Thishappensbecause theFastapproximateDTWcomputes theglobalprincipalalignments fromthe databaseanditsperformancedependsonthenumberofsamples.Also, thesealignmentsarequery independent, i.e., theydonotuseanyqueryinformationforcomputingtheglobalprincipalalignments. 80