Seite - 75 - in Document Image Processing

J. Imaging 2018,4, 37 2.2.NNDQC:DesignofDQCUsingApproximateNearestNeighbour Aspeed-upisobtainedbyusingapproximatenearestneighborsearch insteadofusingDTW. • Insteadofconcatenating theclassmeanvectors,noweachclassmeanvector isdivided intosame p number of fixed length portions. An index is built over frequent classmeans cut portions usingFLANN. • EachcutportionofXq is comparedwith frequentclassmeanscutportionsusingnearestneighbor searchwithEuclideandistance. • Thebestmatchingcutportionsof themeanvectorsareusedtosynthesize themeanvector for the queryclass. However,usingnearestneighbor(NNDQC)insteadofsubsequenceDTWbasedscheme(DPDQC) compromises theoptimalityof theclassifiersynthesis. Fewqualitativeexamples for the twoversionsofDQCaregiven inFigure1. Wehaveshown the retrieval results for frequent queries and rare queries. For each case, we have compared the retrieval results forNNDQCandDPDQC.Forrarequery,wehavealsoshowntheresults forQuery expansion(QE). Frequent Rare NN DQC NN DQC DP DQC DP DQC NN DQC QE with Query Method Rank 1 Rank 2 Rank 4Rank 3 Rank 5 Retrieved Results Query Query Figure1.Figureshowsfewquerywordsandtheircorrespondingretrieval results. Thefirstcolumn showsthequery imageandthecorrespondingimages ineachroware its retrieval results. First two rowsshowfrequentqueryresults. Thefirst rowshowstheresults forNNDQCandsecondrowshow the results forDPDQC.Row3 toRow5showthe retrieval results for a rarequery. Row3shows the results forNNDQCandRow4show the results forDPDQCandRow5show the results for queryexpansion. 3.ApproximatingtheDTWDistance In general, DTW distance has quadratic complexity in the length of the sequence. Nagendaretal. [20]proposedFast approximateDTWdistance (FastApprxDTW),which is a linear approximationtotheDTWdistance. Forapairofgivensequences,DTWdistanceiscomputedusingthe optimalalignment fromall thepossiblealignments. Thisoptimalalignmentgivesasimilaritybetween thegivensequencesbyignoringlocalshifts.Computationofoptimalalignment is themostexpensive operationinfindingtheDTWdistance. Foragivensetof sequences, therearesimilaritiesbetweentheoptimalalignmentsofdifferent pairs of sequences. For example, if we take two different classes, the top alignments (optimal alignments/leastcostalignments)betweenthesamplesofclass1andthesamplesofclass2always havesomesimilarity. Forasmalldataset, the topalignmentsbetweenfewclass1samplesandfew class 2 samples areplotted inFigure2. It canbeobserved that the topalignments are inharmony. Basedonthis idea,wecomputeasetofglobalprincipalalignmentsfromthetrainingdatasuchthat the computedglobalprincipalalignmentsshouldbegoodenoughforapproximatingtheDTWdistance betweenanynewpairof sequences. Fornewtest sequences, insteadoffindingtheoptimalalignments, theglobalprincipalalignmentsareusedforcomputingtheDTWdistance. Thisavoidsthecomputation 75