In recent years, different approaches for handwriting recognition that are based on graph representations have been proposed (e.g. graph-based keyword spotting or signature verification). This trend is mostly due to the availability of novel fast graph matching algorithms, as well as the inherent flexibility and expressivity of graph data structures when compared to vectorial representations. That is, graphs are able to directly adapt their size and structure to the size and complexity of the respective handwritten entities. However, the vast majority of the proposed approaches match the graphs from a global perspective only. In the present paper, we propose to match the underlying graphs from different local perspectives and combine the resulting assignments by means of Dynamic Time Warping. Moreover, we show that the proposed approach can be readily combined with global matchings. In an experimental evaluation, we employ the novel method in a signature verification scenario on two widely used benchmark datasets. On both datasets, we empirically confirm that the proposed approach outperforms state-of-the-art methods with respect to both accuracy and runtime.

Scanned handwritten historical documents are often not well accessible due to the limited feasibility of automatic full transcriptions. Thus, Keyword Spotting (KWS) has been proposed as an alternative to retrieve arbitrary query words from this kind of documents. In the present paper, word images are represented by means of graphs. That is, a graph is used to represent the inherent topological characteristics of handwriting. The actual keyword spotting is then based on matching a query graph with all document graphs. In particular, we make use of a fast graph matching algorithm that considers the contextual substructure of nodes. The motivation for this inclusion of node context is to increase the overall KWS accuracy. In an experimental evaluation on four historical documents, we show that the proposed procedure clearly outperforms diverse other template-based reference systems. Moreover, our novel framework keeps up or even outperforms many state-of-the-art learning-based KWS approaches.

Graphs provide a powerful representation formalism for handwritten signatures, capturing local properties as well as their relations. Yet, although introduced early for signature verification, only a few current systems rely on graph-based representations. A possible reason is the high computational complexity involved for matching two general graphs. In this paper, we introduce a novel structural approach to offline signature verification using an efficient cubic-time approximation of graph edit distance. We put forward several ways of creating, normalizing, and comparing signature graphs built from keypoints and investigate their performance on three benchmark datasets. The experiments demonstrate a promising performance of the proposed structural approach when compared with the state of the art.

Keyword Spotting (KWS) offers a convenient way to improve the accessibility to historical handwritten documents by retrieving search terms in scanned document images. The approach for KWS proposed in the present paper is based on segmented word images that are represented by means of different types of graphs. The actual keyword spotting is based on matching a query graph with a set of document graphs using the concept of graph edit distance. In particular, we propose to employ ensemble methods for KWS with graphs. That is, a query graph is not matched against one but several different graphs representing the same document word. Eventually, we use different strategies to combine these individual graph dissimilarities. In an experimental evaluation on two benchmark datasets, the proposed ensemble methods outperform the individual ensemble members as well as four state-of-the-art reference systems based on dynamic time warping.

This paper introduces a novel method of reducing the number of prototype patterns necessary for accurate recognition of temporal patterns. The nearest neighbor (NN) method is an effective tool in pattern recognition, but the downside is it can be computationally costly when using large quantities of data. To solve this problem, we propose a method of representing the temporal patterns by embedding dynamic time warping (DTW) distance based dissimilarities in vector space. Adaptive boosting (AdaBoost) is then applied for classifier training and feature selection to reduce the number of prototype patterns required for accurate recognition. With a data set of handwritten digits provided by the International Unipen Foundation (iUF), we successfully show that a large quantity of temporal data can be efficiently classified produce similar results to the established NN method while performing at a much smaller cost.

One of the major tasks in many applications in the field of document analysis is the computation of dissimilarities between two or more objects from a given problem domain. Hence, employing graphs as representation formalism evokes the need for powerful, fast and flexible graph based dissimilarity models. Graph edit distance is powerful and applicable to any kind of graphs but suffers from its high computational complexity. Recently, however, a novel framework for graph edit distance approximation has been introduced. While the run time of this novel procedure is very convincing, the precision of the approximated graph distances is dissatisfying in some cases. The present paper introduces a generalized version of the existing approximation framework using an iterative bipartite procedure. With empirical investigations on three real world data sets we show that our extension substantially improves the accuracy of the approximations while the run time is increased only linearly with the number of additional iterations.