Filters for graph-based keyword spotting in historical handwritten documents

Show simple item record

dc.contributor.author Stauffer, Michael
dc.contributor.author Fischer, Andreas
dc.contributor.author Riesen, Kaspar
dc.date.accessioned 2018-04-25T09:39:29Z
dc.date.issued 2020-06
dc.description.abstract The accessibility to handwritten historical documents is often constrained by the limited feasibility of automatic full transcriptions. Keyword Spotting (KWS), that allows to retrieve arbitrary query words from documents, has been proposed as alternative. In the present paper, we make use of graphs for representing word images. The actual keyword spotting is thus based on matching a query graph with all documents graphs. However, even with relative fast approximation algorithms the shear amount of matchings might limit the practical application of this approach. For this reason we present two novel filters with linear time complexity that allow to substantially reduce the number of graph matchings actually required. In particular, these filters estimate a graph dissimilarity between a query graph and all document graphs based on their node and edge distribution in a polar coordinate system. Eventually, all graphs from the document with distributions that differ to heavily from the query’s node/edge distribution are eliminated. In an experimental evaluation on four different historical documents, we show that about 90% of the matchings can be omitted, while the KWS accuracy is not negatively affected. en_ZA
dc.description.department Informatics en_ZA
dc.description.embargo 2019-03-30
dc.description.librarian hj2018 en_ZA
dc.description.sponsorship The Hasler Foundation Switzerland. en_ZA
dc.description.uri http://www.elsevier.com/locate/patrec en_ZA
dc.identifier.citation Stauffer, M., Fischer, A. & Riesen, K. 2020, 'Filters for graph-based keyword spotting in historical handwritten documents', Pattern Recognition Letters, vol. 134, pp. 125-134. en_ZA
dc.identifier.issn 0167-8655 (print)
dc.identifier.issn 1872-7344 (online)
dc.identifier.other 10.1016/j.patrec.2018.03.030
dc.identifier.uri http://hdl.handle.net/2263/64717
dc.language.iso en en_ZA
dc.publisher Elsevier en_ZA
dc.rights © 2018 Elsevier B.V. All rights reserved. Notice : this is the author’s version of a work that was accepted for publication in Pattern Recognition Letters. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. A definitive version was subsequently published in Pattern Recognition Letters, vol. 134, pp. 125-134, 2020. doi : 10.1016/j.patrec.2018.03.030. en_ZA
dc.subject Graph theory en_ZA
dc.subject Keyword spotting en_ZA
dc.subject Graph representation en_ZA
dc.subject Filter method en_ZA
dc.subject Fast rejection en_ZA
dc.subject Pattern matching en_ZA
dc.subject History en_ZA
dc.subject Graphic methods en_ZA
dc.subject Bandpass filters en_ZA
dc.subject Approximation algorithms en_ZA
dc.subject Handwritten keyword spotting en_ZA
dc.subject Bipartite graph matching en_ZA
dc.title Filters for graph-based keyword spotting in historical handwritten documents en_ZA
dc.type Postprint Article en_ZA


Files in this item

This item appears in the following Collection(s)

Show simple item record