Speeding-up graph-based keyword spotting in historical handwritten documents

Loading...
Thumbnail Image

Authors

Stauffer, Michael
Fischer, Andreas
Riesen, Kaspar

Journal Title

Journal ISSN

Volume Title

Publisher

Springer

Abstract

The present paper is concerned with a graph-based system for Keyword Spotting (KWS) in historical documents. This particular system operates on segmented words that are in turn represented as graphs. The basic KWS process employs the cubic-time bipartite matching algorithm (BP). Yet, even though this graph matching procedure is relatively efficient, the computation time is a limiting factor for processing large volumes of historical manuscripts. In order to speed up our framework, we propose a novel fast rejection heuristic. This heuristic compares the node distribution of the query graph and the document graph in a polar coordinate system. This comparison can be accomplished in linear time. If the node distributions are similar enough, the BP matching is actually carried out (otherwise the document graph is rejected). In an experimental evaluation on two benchmark datasets we show that about 50% or more of the matchings can be omitted with this procedure while the KWS accuracy is not negatively affected.

Description

International Workshop on Graph-Based Representations in Pattern Recognition. GbRPR 2017: Graph-Based Representations in Pattern Recognition pp. 83-93.

Keywords

Handwritten keyword spotting, Bipartite graph matching, Fast rejection, Filtering graph matching

Sustainable Development Goals

Citation

Stauffer M., Fischer A., Riesen K. (2017) Speeding-Up Graph-Based Keyword Spotting in Historical Handwritten Documents. In: Foggia P., Liu CL., Vento M. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2017. Lecture Notes in Computer Science, vol 10310. Springer, Cham.