Graph-Based Keyword Spotting

The following sections are included:

• Dedication
• Preface
• Contents
• List of Figures
• List of Tables

The following sections are included:

• Keyword Spotting (KWS) as a Scientific Discipline
• Limitations
• Research Questions
• Contributions
• Outline and Organisation of the Book

The following sections are included:

• A Taxonomy of KWS Systems
• Image Preprocessing
• Formal Representation
  • Statistical Representation
  • Structural Representation
• Querying
  • Template-based Approaches for KWS
  • Learning-based Approaches for KWS
• Summary

In recent decades a wide set of handwritten historical documents have been made publicly available by digital means. These documents cover a wide range of different languages, alphabets, and time ranges, and thus, build an important pillar of our cultural heritage. To make these documents available for searching and browsing, different keyword spotting (KWS) approaches have been proposed as discussed in the previous chapter…

The following sections are included:

• Introduction and Basic Definitions
• Graph-Based Pattern Recognition
• From Handwriting to Graphs
  • Keypoint-Based Graphs
  • Grid-Based Graphs
  • Projection-Based Graphs
  • Split-Based Graphs
• Preliminary Experimental Evaluation
• Summary

The following sections are included:

• Overview and Broader Perspective
• Graph Matching for KWS
  • Exact Graph Matching
  • Inexact Graph Matching
  • Formal Requirements
• Graph Edit Distance
  • Suboptimal Algorithms
  • Bipartite Graph Edit Distance (BP)
  • Hausdorff Edit Distance (HED)
  • Bipartite Graph Edit Distance 2 (BP2)
• Polar Graph Dissimilarity (PGD)
  • Polar Segmentation of Graphs
  • Histogram-Based Representation
  • Histogram-Based Dissimilarity Measure
• Summary

The following sections are included:

• Overview of our Framework for KWS
• From Graph Edit Distance (GED) to Retrieval Indices
  • Cost Model for Keyword Spotting
  • Retrieval Indices
• Extensions of the Basic Framework
  • Quadtree Segementations
  • Fast Rejection Methods
  • Ensemble Methods
• Evaluation Metric
• Summary

The following sections are included:

• Overview of Experimental Evaluation
• Experimental Setup
  • Validation of Parameters
• The Baseline KWS System Using BP
• Speeding Up the Baseline KWS System
  • KWS System Based on BP with Quadtree Segmentations
  • KWS System Based on BP with Fast Rejection Methods
  • KWS System Based on PGD
• KWS System Based on HED
  • Hausdorff Edit Distance
  • Context-aware Hausdorff Edit Distance
• KWS System Based on BP2
• Graph-Based Ensembles for KWS
  • Ensemble Methods Based on BP
  • Ensemble Methods Based on HED, CED, and BP2
• Cross-Evaluation of Graph-Based Systems
• Quantitative and Qualitative Summary of Graph-Based Systems
  • Quantitative Summary
  • Qualitative Summary
• Comparison of Our Framework with Reference Systems
  • Reference Systems
  • Comparison with Template-Based Reference Systems
  • Comparison with Learning-Based Reference Systems
• Summary

The following sections are included:

• Conclusion
• Future Work

The visualisation of the four different graph representation formalisms (i.e. Keypoint, Grid, Projection, and Split) is based on graphs with different mean numbers of nodes (i.e. small = 25-50 mean number of nodes, medium = 50-75 mean number of nodes, large = 75-100 mean number of nodes). That is, for every manuscript parameters have been chosen to meet the desired mean number of nodes, see Table 9.1 for George Washington (GW), Table 9.2 for Parzival (PAR), Table 9.3 for Alvermann Konzilsprotokolle (AK), and Table 9.4 for Botany (BOT)…

The optimisation of the parameters is conducted in six subsequent steps as described in Subsection 7.2.1. That is, for every manuscript (i.e. George Washington (GW), Parzival (PAR), Alvermann Konzilsprotokolle (AK), and Botany (BOT)) parameters are optimised individually. However, for bipartite graph edit distance (BP) only, all parameters are provided in Subsection 7.2.1, and thus, we provide the complete list of optimised parameters for all remaining graph matching algorithms (i.e. Hausdorff edit distance (HED), context-aware Hausdorff edit distance (CED), bipartite graph edit distance 2 (BP2), and polar graph dissimilarity (PGD)) in the following sections. In Table 10.1, optimised parameters are provided for cost functions of graph edit distance (GED) computation, while the fast rejection threshold D is optimised with respect to the filter rate (FR) and average precision (AP) in Figs. 10.1, 10.2, 10.3, 10.4, 10.5 and 10.6. Finally, the retrieval index r₂ is optimised in Tables 10.2 and 10.3…

Ensemble methods for graph-based keyword spotting (KWS) allow us to combine the graph edit distances (GEDs) of different graph representations of the same manuscript (i.e. George Washington (GW), Parzival (PAR), Alvermann Konzilsprotokolle (AK), and Botany (BOT)) as introduced in Section 6.3.3. In Section 7.7.1, experiments for ensemble methods by means of bipartite graph edit distance (BP) are discussed, while results of ensemble methods for Hausdorff edit distance (HED), context-aware Hausdorff edit distance (CED), and bipartite graph edit distance 2 (BP2) are summarised in Section 7.7.2. The remaining results (i.e. mean average precision (MAP) and average precision (AP) for HED, CED, and BP2) are provided in the following sections. In Section 11.1, results for HED-based ensemble methods are provided, while CED-based ensemble methods are presented in Section 11.2. Finally, ensemble methods based on BP2 are presented in Section 11.3.

The following sections are included:

• Bibliography
• Index