Seite - 84 - in Document Image Processing

J. Imaging 2018,4, 37 For thegiventwosamplesxandyof lengthN, FastDTW[30] iscomputedin the followingway. First, these two samples are reduced to smaller length (1/8 times) and thenaiveDTWdistance is appliedover thereducedlengthsamples tofindtheoptimalwarppath.Next,both theoptimalpath andthereducedlengthsamples fromthepreviousstepareprojectedtohigher (twotimes) resolution. Insteadoffillingall the entries in the costmatrix in thehigher resolution, only the entries around aneighborhoodof theprojectedwarppath,governedbya parametercalledradius r, arefilledup. Thisprojectionstep iscontinueduntil theoriginal resolutionwasobtained. Thetimecomplexityof FastDTWisN(8r+14),where r is theradius. TheperformanceofFastDTWdependsontheradius r. Thehigher thevalueof r, thebetter theperformance is. The timecomplexityofQSDTW/FastApprx DTWisN∗p,where p is thenumberofprincipalalignments. Ingeneral, p<<8r+14, forgettingthe similarperformance inboth themethods. 6.Conclusions WehaveproposedqueryspecificDTWdistance for faster indexing inthedirectqueryclassifier DQC[18]. ThebenefitofdeployingQSDTWwithDQCis that it results in linear timecomplexity. Therefore,we are able to index all the frequentmeanvectors of thedatabase for constructing the meanvector for thequeryclass in theDQCclassifier. SinceQSDTWdistanceperformsequallywell asDTWdistanceandbecauseweconsiderall the frequentmeanvectors for indexing, theproposed methodenhances theperformanceof theDQC.Unlikepreviousapproaches, theproposedQSDTW distanceusesboththeclassmeanvectorsandthequeryinformationforcomputingtheglobalprincipal alignments for thequery. Theuseofngrams for computing theglobalprincipal alignmentsmakes themethodperformwell for rarequeries,whicharequerywordimages thatbelongtonon-frequent wordclasses forwhichmeanvectorsarenotcomputedfor thedatabase. Thequeryexpansion(QE) further improves theperformanceofQSDTW.Wehavedemonstrated theutility of theproposed techniqueover threedifferentdatasets. TheproposedqueryspecificDTWperformswell comparedto thepreviousDTWapproximations. Acknowledgments:ThisworkwassupportedfromthegrantreceivedfortheIMPRINTproject titled"Information access fromdocument imagesof Indian languages," fromMHRD,Governmentof India. AuthorContributions:GattigorlaNagendarandVireshRanjanperformedtheexperiments.GauravHaritand C.VJawaharwrote thepaper. Conflictsof Interest:Theauthorsdeclarenoconflictof interest. References 1. Nagy,G.TwentyYearsofDocument ImageAnalysis inPAMI.PAMI2008,22, 38–62,doi:10.1109/34.824820. 2. Sivic, J.; Zisserman, A. Video Google: A Text Retrieval Approach to Object Matching in Videos. In Proceedings of the Ninth IEEE International Conference on Computer Vision, Nice, France, 13–16October2003;pp. 1470–1477. 3. Rath, T.M.; Manmatha, R. Word spotting for historical documents. IJDAR 2007, 9, 139–152, doi:10.1109/SIU.2008.4632567. 4. Zeki, Y.I.; Manmatha, R. An Efficient Framework for Searching Text in Noisy Document Images. In Proceedings of the 2012 10th IAPR InternationalWorkshop onDocumentAnalysis Systems (DAS), GoldCost,QLD,Australia, 27–29March2012;pp. 48–52. 5. Konidaris,T.;Gatos,B.;Ntzios,K.;Pratikakis, I.; Theodoridis, S.; Perantonis, S.J.Keyword-guidedword spotting inhistoricalprinteddocumentsusingsyntheticdataanduser feedback. IJDAR2007,9, 167–177, doi:10.1007/s10032-008-0067-3. 6. Basilios,G.;Nikolaos,S.;Georgios,L. ICDAR2009HandwritingSegmentationContest. InProceedingsof the10thInternationalConferenceonDocumentAnalysisandRecognition,Barcelona,Spain,26–29 July2009; pp. 1393–1397. 84