Auflistung nach Autor:in "Fischer, Andreas"

Gerade angezeigt 1 - 20 von 25

A Fast Matching Algorithm for Graph-Based Handwriting Recognition
(2013) Fischer, Andreas; Frinken, Volkmar; Riesen, Kaspar; Bunke, Horst; Suen, Ching Y.; Haxhimusa, Yll; Jiang, Xiaoyi; Artner, Nicole M.; Kropatsch, Walter G.
04B - Beitrag Konferenzschrift
An Experimental Study of Graph Classification using Prototype Selection
(2008) Fischer, Andreas; Riesen, Kaspar; Bunke, Horst
04B - Beitrag Konferenzschrift
Approximation of graph edit distance based on Hausdorff matching
(2015) Fischer, Andreas; Frinken, Volkmar; Riesen, Kaspar; Suen, Ching Y.
01A - Beitrag in wissenschaftlicher Zeitschrift
Approximation of Graph Edit Distance in Quadratic Time
(05/2015) Riesen, Kaspar; Ferrer, Miquel; Fischer, Andreas; Bunke, Horst
The basic idea of a recent graph matching framework is to reduce the problem of graph edit distance (GED) to an instance of a linear sum assignment problem (LSAP). The optimal solution for this simplified GED problem can be computed in cubic time and is eventually used to derive a suboptimal solution for the original GED problem. Yet, for large scale graphs and/or large scale graph sets the cubic time complexity remains a severe handicap of this procedure. Therefore, we propose to use suboptimal algorithms – with quadratic rather than cubic time complexity – for solving the underlying LSAP. In particular, we introduce several greedy assignment algorithms for approximating GED. In an experimental evaluation we show that there is great potential for further speeding up the GED computation. Moreover, we empirically confirm that the distances obtained by this procedure remain sufficiently accurate for graph based pattern classification.
04B - Beitrag Konferenzschrift
Building Classifier Ensembles Using Greedy Graph Edit Distance
(Springer, 2015) Riesen, Kaspar; Ferrer, Miquel; Fischer, Andreas
Classifier ensembles aim at more accurate classifications than single classifiers. In the present paper we introduce a general approach to building structural classifier ensembles, i.e. classifiers that make use of graphs as representation formalism. The proposed methodology is based on a recent graph edit distance approximation. The major observation that motivates the use of this particular approximation is that the resulting distances crucially depend on the order of the nodes of the underlying graphs. Our novel methodology randomly permutes the node order N times such that the procedure leads to N different distance approximations. Next, a distance based classifier is trained for each approximation and the results of the individual classifiers are combined in an appropriate way. In several experimental evaluations we make investigations on the classification accuracy of the resulting classifier ensemble and compare it with two single classifier systems.
04B - Beitrag Konferenzschrift
Combining Bipartite Graph Matching and Beam Search for Graph Edit Distance Approximation
(Springer, 2014) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst; El Gayar, Neamat; Schwenker, Friedhelm; Suen, Cheng
Graph edit distance (GED) is a powerful and flexible graph dissimilarity model. Yet, exact computation of GED is an instance of a quadratic assignment problem and can thus be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, the primary optimization process of this approximation framework is able to consider local edge structures only, and thus, the observed speed up is at the expense of approximative, rather than exact, distance values. In order to improve the overall approximation quality, the present paper combines the original approximation framework with a fast tree search procedure. More precisely, we regard the assignment from the original approximation as a starting point for a subsequent beam search. In an experimental evaluation on three real world data sets a substantial gain of assignment accuracy can be observed while the run time remains remarkable low.
04B - Beitrag Konferenzschrift
Combining graph edit distance and triplet networks for offline signature verification
(Elsevier, 2019) Maergner, Paul; Pondenkandath, Vinaychandran; Alberti, Michele; Liwicki, Marcus; Riesen, Kaspar; Ingold, Rolf; Fischer, Andreas
Offline signature verification is a challenging pattern recognition task where a writer model is inferred using only a small number of genuine signatures. A combination of complementary writer models can make it more difficult for an attacker to deceive the verification system. In this work, we propose to combine a recent structural approach based on graph edit distance with a statistical approach based on deep triplet networks. The combination of the structural and statistical models achieve significant improvements in performance on four publicly available benchmark datasets, highlighting their complementary perspectives.
01A - Beitrag in wissenschaftlicher Zeitschrift
Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time
(Springer, 2014) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst; El Gayar, Neamat; Schwenker, Friedhelm; Suen, Cheng
Exact computation of graph edit distance (GED) can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, since this approach considers local – rather than the global – structural properties of the graphs only, the GED derived from the optimal assignment is suboptimal. The contribution of the present paper is twofold. First, we give a formal proof that this approximation builds an upper bound of the true graph edit distance. Second, we show how the existing approximation framework can be reformulated such that a lower bound of the edit distance can be additionally derived. Both bounds are simultaneously computed in cubic time.
04B - Beitrag Konferenzschrift
Cross-evaluation of graph-based keyword spotting in handwritten historical documents
(Springer, 2019) Stauffer, Michael; Maergner, Paul; Fischer, Andreas; Riesen, Kaspar; Conte, Donatello; Ramel, Jean-Yves; Foggia, Pasquale
In contrast to statistical representations, graphs offer some inherent advantages when it comes to handwriting representation. That is, graphs are able to adapt their size and structure to the individual handwriting and represent binary relationships that might exist within the handwriting. We observe an increasing number of graph-based keyword spotting frameworks in the last years. In general, keyword spotting allows to retrieve instances of an arbitrary query in documents. It is common practice to optimise keyword spotting frameworks for each document individually, and thus, the overall generalisability remains somehow questionable. In this paper, we focus on this question by conducting a cross-evaluation experiment on four handwritten historical documents. We observe a direct relationship between parameter settings and the actual handwriting. We also propose different ensemble strategies that allow to keep up with individually optimised systems without a priori knowledge of a certain manuscript. Such a system can potentially be applied to new documents without prior optimisation.
04B - Beitrag Konferenzschrift
Estimating Graph Edit Distance Using Lower and Upper Bounds of Bipartite Approximations
(World Scientific, 02.03.2015) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst
The concept of graph edit distance (GED) is still one of the most flexible and powerful graph matching approaches available. Yet, exact computation of GED can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, this approach considers local — rather than the global — structural properties of the graphs only, and thus GED derived from the optimal node assignment generally overestimates the true edit distance. Recently, it has been shown how the existing approximation framework can be exploited to additionally derive a lower bound of the exact edit distance without any additional computations. In this paper we make use of regression analysis in order to predict the exact GED using these two bounds. In an experimental evaluation on diverse graph data sets we empirically verify the gain of distance accuracy of the estimated GEDs compared to both bounds.
01A - Beitrag in wissenschaftlicher Zeitschrift
Filters for graph-based keyword spotting in historical handwritten documents
(Elsevier, 2020) Stauffer, Michael; Fischer, Andreas; Riesen, Kaspar
01A - Beitrag in wissenschaftlicher Zeitschrift
Graph embedding for offline handwritten signature verification
(2019) Stauffer, Michael; Maergner, Paul; Fischer, Andreas; Riesen, Kaspar
Due to the high availability and applicability, handwritten signatures are an eminent biometric authentication measure in our life. To mitigate the risk of a potential misuse, automatic signature verification tries to distinguish between genuine and forged signatures. Most of the available signature verification approaches make use of vectorial rather than graph-based representations of the handwriting. This is rather surprising as graphs offer some inherent advantages. Graphs are, for instance, able to directly adapt their size and structure to the size and complexity of the respective handwritten entities. Moreover, several fast graph matching algorithms have been proposed recently that allow to employ graphs also in domains with large amounts of data. The present paper proposes to use different graph embedding approaches in conjunction with a recent graph-based signature verification framework. That is, signature graphs are not directly matched with each other, but first compared with a set of predefined prototype graphs, in order to obtain a dissimilarity representation. In an experimental evaluation, we employ the proposed method on two widely used benchmark datasets. On both datasets, we empirically confirm that the learning-free graph embedding outperforms state-of-the-art methods with respect to both accuracy and runtime.
04B - Beitrag Konferenzschrift
Graph Similarity Features for HMM-Based Handwriting Recognition in Historical Documents
(2010) Fischer, Andreas; Riesen, Kaspar; Bunke, Horst
04B - Beitrag Konferenzschrift
Graph-based keyword spotting in historical documents using context-aware Hausdorff edit distance
(IEEE, 2018) Stauffer, Michael; Fischer, Andreas; Riesen, Kaspar
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.
04B - Beitrag Konferenzschrift
Graph-based keyword spotting in historical manuscripts using Hausdorff edit distance
(Elsevier, 2019) Ameri, Mohammad Reza; Stauffer, Michael; Riesen, Kaspar; Bui, Tien Dai; Fischer, Andreas; Fischer, Andreas
Keyword spotting enables content-based retrieval of scanned historical manuscripts using search terms, which, in turn, facilitates the indexation in digital libraries. Recent approaches include graph-based representations that capture the complex structure of handwriting. However, the high representational power of graphs comes at the cost of high computational complexity for graph matching. In this article, we investigate the potential of Hausdorff edit distance (HED) for keyword spotting. It is an efficient quadratic-time approximation of the graph edit distance. In a comprehensive experimental evaluation with four types of handwriting graphs and four benchmark datasets (George Washington, Parzival, Botany, and Alvermann Konzilsprotokolle), we demonstrate a strong performance of the proposed HED-based method when compared with the state of the art, both, in terms of precision and speed.
01A - Beitrag in wissenschaftlicher Zeitschrift
Improving Approximate Graph Edit Distance Using Genetic Algorithms
(22.08.2014) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst
04B - Beitrag Konferenzschrift
Improving Hausdorff Edit Distance Using Structural Node Context
(Springer, 2015) Fischer, Andreas; Uchida, Seiichi; Frinken, Volkmar; Riesen, Kaspar; Bunke, Horst; Liu, Cheng-Lin; Luo, Bin; Kropatsch, Walter G.; Cheng, Jian
In order to cope with the exponential time complexity of graph edit distance, several polynomial-time approximation algorithms have been proposed in recent years. The Hausdorff edit distance is a quadratic-time matching procedure for labeled graphs which reduces the edit distance to a correspondence problem between local substructures. In its original formulation, nodes and their adjacent edges have been considered as local substructures. In this paper, we integrate a more general structural node context into the matching procedure based on hierarchical subgraphs. In an experimental evaluation on diverse graph data sets, we demonstrate that the proposed generalization of Hausdorff edit distance can significantly improve the accuracy of graph classification while maintaining low computational complexity.
04B - Beitrag Konferenzschrift
Keyword spotting in historical handwritten documents based on graph matching
(Elsevier, 2018) Stauffer, Michael; Fischer, Andreas; Riesen, Kaspar
In the last decades historical handwritten documents have become increasingly available in digital form. Yet, the accessibility to these documents with respect to browsing and searching remained limited as full automatic transcription is often not possible or not sufficiently accurate. This paper proposes a novel reliable approach for template-based keyword spotting in historical handwritten documents. In particular, our framework makes use of different graph representations for segmented word images and a sophisticated matching procedure. Moreover, we extend our method to a spotting ensemble. In an exhaustive experimental evaluation on four widely used benchmark datasets we show that the proposed approach is able to keep up or even outperform several state-of-the-art methods for template- and learning-based keyword spotting.
01A - Beitrag in wissenschaftlicher Zeitschrift
Kontinuität und Neues - Impulse für die Weiterentwicklung eines MAS-Programms mit Hilfe von Evaluation
(Universität Bern Zentrum für universitäre Weiterbildung, 01.07.2015) Hörmann, Martina; Meier, Kathrin; Friedrich, Verena; Fischer, Andreas
04A - Beitrag Sammelband
KWB-Studiengänge begleiten und bewerten. Leitfaden zur Evaluation von Weiterbildungsstudiengängen
(Universität Bern, Koordinationsstelle für Weiterbildung, 2007) Beywl, Wolfgang; Fischer, Andreas; Senn, Peter
02 - Monographie