Seite - 83 - in Document Image Processing

J. Imaging 2018,4, 37 Table8. Retrievalperformanceon the3datasetsD1,D2andD3forvaryingnumberof cut specific principalalignments. NumberofCutSpecific PrincipalAlignments mAPforDifferentDatasets D1 D2 D3 10 0.92 0.89 0.81 20 0.93 0.89 0.81 30 0.91 0.88 0.78 5.8. ComputationTime Table 9 gives the computational time complexity for themethods based on DTW. Themain computation involved in theuseofQSDTWis thatof computing thecutspecificprincipalalignments for the frequentclasses. Figure5showsthe timeforcomputingthecutspecificprincipalalignments for the three datasets. The computation of these cut specific principal alignments can be carried out independently for all the classes. Sincewecancompute theseprincipal alignments inparallel with eachother, theproposedQSDTWscaleswellwith thenumberof samples compared toFast ApprxDTW[20]. Figure5.Computation timeforcomputing thecut specificprincipalalignments forall thedatasets. It includes thecomputationofcutspecificprincipalalignments forall the frequentclassesoverall the cutportions. Table9.ComputationalcomplexitiesofDTW-basedmethodsfordistancecomputation.Heren is the lengthof thecut-portionof the featurevector. Methods sDTW FastApprxDTW [20] FastDTW [30] QSDTW ComputationalComplexity O(n2) O(n) O(n) O(n) Unlike the case ofQSDTW,where the principal alignments are computed for the small cut portions, in Fast Apprx DTW, the principal alignments are computed for the full word image representation. Further, inFastApprxDTW,theprincipalalignmentsarecomputedfromtheentire dataset,unlike thecaseofQSDTWinwhich theprincipalalignmentsarecomputedfor the individual classes. For thesereasons,FastApprxDTWiscomputationallyslowercomparedto theQSDTW. Foragivendataset, computingthecutspecificprincipalalignments for the frequentclasses isan offlineprocess.Whenperformingretrieval foragivenquery,DQCinvolvescomputingthequerymean bycomposing together thenearest cutportions fromthemeanvectorsof frequent classes. Further, thequeryspecificprincipalalignmentsarenotexplicitlycomputedbutratherconstructedusingthe cut-specificprincipalalignmentscorrespondingto thenearestcutportions.Once thequeryspecific principalalignmentsareobtained,computationofQSDTWinvolvescomputingtheEuclideandistance (usingthequeryspecificprincipalalignments)with thedatabase images. 83