Probabilistic Indexing for Information Search and Retrieval in Large Collections of Handwritten Text Images (The Information Retrieval Series, 49)

Preface
Acknowledgements
	Persons
	Projects
	Grants
Contents
Acronyms
	Lists of Abbreviations
	Mathematical Notation
List of Algorithms
List of Figures
List of Tables
Chapter 1 Introduction
	1.1 Motivation and Background
	1.2 Information Retrieval
	1.3 Pattern Recognition
	1.4 Decision Theory
	1.5 Handwritten Text Recognition
	1.6 Assessing Indexing and Search Performance
	1.7 Handwritten Text Recognition and Probabilistic Indexing
	References
Chapter 2 State Of The Art
	2.1 The field of a Hundred Names
	2.2 Taxonomy of KWS approaches
		2.2.1 Segmentation Assumptions
			2.2.1.1 Word Segmentation
			2.2.1.2 Line Segmentation
			2.2.1.3 Segmentation-free
		2.2.2 Retrieved Objects
			2.2.2.1 Word Instances
			2.2.2.2 Lines
			2.2.2.3 Pages
		2.2.3 Query Representation
			2.2.3.1 Query-by-String
			2.2.3.2 Query-by-Example
		2.2.4 Training Requirements
			2.2.4.1 Unsupervised
			2.2.4.2 Supervised
	2.3 Additional Significant Matters for KWS
		2.3.1 Hyphenated Words
		2.3.2 Abbreviations
		2.3.3 Multiple-word Queries
	2.4 State of the Art in HTR Models and Methods
	References
Chapter 3 Probabilistic Indexing (PrIx) Framework
	3.1 Pixel Level Textual Image Representation: 2-D Posteriorgram
	3.2 Image Regions for Keyword Indexing and Search
	3.3 Position-independent PrIx
		3.3.1 NaiveWord Posterior Interpretation of V(X | x, υ)
		3.3.2 Proposed Approximations to  V(X | x, υ)
		3.3.3 Estimating Image-Region RPs from Posteriorgrams
		3.3.4 Line-Region RP and 1-D Posteriorgram
	3.4 Position-independent PrIx and KWS from a HTR Viewpoint
		3.4.1 Comparing the Image Processing and HTR Viewpoints
	3.5 Position-dependent PrIx
		3.5.1 Relevance of an Horizontal Coordinate Position
		3.5.2 Relevance of a Segment of Text-line Image Region
		3.5.3 Relevance of a Transcript Ordinal Position
	3.6 Query-by-Example Paradigm
		3.6.1 Position-independent RPs for Query by Example KWS
		3.6.2 Position-dependent RPs for Query by Example KWS
	3.7 Relations among Position-Dependent and Independent RPs
		3.7.1 Equivalences of Positional RPs and other Posterior Probabilities
		3.7.2 Computing Horizontal Coordinate RP from Segment RP
		3.7.3 Expected Values of Segments and Ordinal Positions
		3.7.4 RP Inequalities Based on Fr´echet Bounds
	3.8 PrIx Implementation Foreword
	References
Chapter 4 Probabilistic Models for Handwritten Text
	4.1 Traditional Image Preprocessing and Feature Extraction
		4.1.1 Image Preprocessing and Text Segmentation
		4.1.2 Text Line Normalization
		4.1.3 Feature Extraction
	4.2 Optical Modeling
	4.3 Hidden Markov Models
		4.3.1 Description
		4.3.2 HMM Training
		4.3.3 HMMs for Optical Modeling in Handwritten Text Recognition
			4.3.3.1 Generative Training
			4.3.3.2 Discriminative Training
	4.4 Artificial Neural Networks
		4.4.1 Description
		4.4.2 Convolutional Layers
		4.4.3 Recurrent Layers
			4.4.3.1 Long Short-Term Memory layers
			4.4.3.2 Estimating character-level posterior probabilities
			4.4.3.3 Connectionist Temporal Classification
		4.4.4 CRNN Training Through Gradient Descent
		4.4.5 Neural Networks for Handwritten Text
	4.5 Key differences between HMMs and CRNNs with CTC
	4.6 N-gram Language Models
		4.6.1 Combining the Output of a CRNN with a N-gram LM
	4.7 Weighted Finite State Transducers (WFST)
		4.7.1 The WFST Composition Operation
		4.7.2 Handling CTC by Means of Elementary WFST Operations
		4.7.3 Lattices Represented as WFST or WFSA
		4.7.4 Normalization of LatticeWeights
			The Backward and Forward Algorithms
			Edge-Posterior Normalization
			Sentence-Posterior Normalization
	References
Chapter 5 Probabilistic Indexing for Fast and Effective Information Retrieval
	5.1 Lexicon-Based and Lexicon-Free PrIx
	5.2 Lexicon-based PrIx from Pixel-level Posteriorgrams
	5.3 Indexing Lexicon-based Lattices
		5.3.1 Position-independent Relevance
			A Lower Cost Alternative
		5.3.2 Lexicon-based Segment Relevance
		5.3.3 Lexicon-based Horizontal Position Relevance
		5.3.4 Lexicon-based Ordinal Position Relevance
			DisambiguatingWG State Positions
			Building Ordinal Position PrIxs
	5.4 The Out-of-vocabulary Problem
	5.5 Indexing Lexicon-free Lattices
		5.5.1 From Character toWord Lattices
	5.6 Alternative Approaches for Lexicon-free PrIx
		5.6.1 Lexicon-free Segment Relevance
			5.6.1.1 Encode Character Alignment
			5.6.1.2 Disambiguating the Input Class Associated to States
			5.6.1.3 From Subpaths to Complete Paths
			5.6.1.4 From Character toWord Alignments
			5.6.1.5 Disambiguating WFST Paths through Automaton Determinization
			5.6.1.6 N-best Paths
			5.6.1.7 Indexing Words with Alignment from Character Lattices
		5.6.2 Lexicon-free Ordinal Position Relevance
			5.6.2.1 Associating OrdinalWord Positions to States
			5.6.2.2 EncodeWord Counts
			5.6.2.3 Indexing Words with Positions from Character Lattices
	5.7 Multi-word and Regular-Expression Queries
	References
Chapter 6 Empirical Validation of Probabilistic Indexing Methods
	6.1 Experimental Setup
		6.1.1 Evaluation Protocol: Image Regions, Query Sets and Metrics
		6.1.2 Datasets and Query Sets
		6.1.3 Statistical Models for Handwritten Text
	6.2 Assessing Posteriorgram Methods for Lexicon-based PrIx
	6.3 Comparing Position-Dependent RP Definitions
	6.4 Evaluating Language Model Impact
		6.4.1 Lexicon-based Models
			N-gram Order
			Lexicon Size
		6.4.2 Lexicon-free Models
			N-gram Order
			Number of Indexed Spots per Line and PrIx Density
		6.4.3 Effect of the Optical and Character-label Prior Scales
	6.5 Impact of Training-set Size and Data Augmentation
	6.6 Correlation between Average Precision and HTR Error Rates
	6.7 Results on Other Academic Benchmark Datasets
		6.7.1 George Washington
		6.7.2 Parzival
		6.7.3 Comparison with Previous State-of-the-art Results
	6.8 Comparing CRNN and HMM-GMM Optical Modeling
		Storage Efficiency
	6.9 Experiments for Real Indexing Projects
		6.9.1 Passau
		6.9.2 Chancery (Himanis)
		6.9.3 Teatro del Siglo de Oro (TSO)
		6.9.4 Large Bentham Dataset (BEN4)
		6.9.5 Carabela
		6.9.6 Finish Court Records (FCR)
	6.10 Segmentation-free Evaluation
		6.10.1 ICDAR2015 Competition on Handwriting KWS
		6.10.2 ICFHR2014 Competition on QbE Handwriting KWS
	6.11 Summary
	References
Chapter 7 Probabilistic Interpretation of Traditional KWS Approaches
	7.1 On the Spotting Versus Recognition Debate
	7.2 Distance-based Methods
		7.2.1 Simplifying QbE RP forWord-segmented Image Regions
		7.2.2 Distance-based Density Estimation
			7.2.2.1 The Multi-variance Problem
			7.2.2.2 The Multi-mode Problem
		7.2.3 Interpretation of Distance-based KWS: Empirical Results
			Results
	7.3 PHOC-based Methods
		7.3.1 Predicting the PHOC of aWord Image Region: PHOCNet
		7.3.2 PHOC-based QbE KWS
		7.3.3 Probabilistic PHOCNet
		7.3.4 PHOCNet Probabilistic Interpretation: Empirical Results
			Results
		7.3.5 Summary of Results of Distance– and PHOC–based Methods
	7.4 HMM-Filler
		7.4.1 HMM-Filler Probabilistic Interpretation: Experiments
			Results and Discussion
		7.4.2 Fast HMM-Filler Computation using Character Lattices
	7.5 BLSTM-CTC KWS
		7.5.1 BLSTM-CTC KWS Interpretation: Experimental Validation
	References
Chapter 8 Probabilistic Indexing Search Extensions
	8.1 Multi-Word Boolean andWord-Sequence Queries
		8.1.1 Experiments
	8.2 Searching for Music Symbol Sequences
		8.2.1 Experiments
	8.3 Structured Queries for Information Retrieval in Table Images
		8.3.1 Experiments
			Discussion
	8.4 Searching for Hyphenated Words
		8.4.1 Experiments
			Discussion
	8.5 Approximate-Spelling andWildcard Queries
		8.5.1 Approximate-Spelling
		8.5.2 Wildcard Spelling
		8.5.3 Experiments
			Discussion
	References
Chapter 9 Beyond Search Applications of Probabilistic Indexing
	9.1 Text Analytics Using PrIx
	9.2 EstimatingWord and Document Frequencies from PrIxs
	9.3 Zipf Curves, RunningWords and Lexicon Size
		9.3.1 Estimating RunningWords and Lexicon Size: Results
	9.4 Statistical Information Extraction from Text Images
		9.4.1 Indexing Semantically TaggedWords and Named Entities
		9.4.2 Statistical Information Extraction from Handwritten Forms
	9.5 Classification of Large Untranscribed Image Documents
		9.5.1 Plaintext Document Classification
			9.5.1.1 Feature Selection
			9.5.1.2 Feature Extraction
		9.5.2 Estimating Text Features from Image PrIxs
		9.5.3 Image Document Classification
		9.5.4 Open Set Classification
		9.5.5 Experiments
			9.5.5.1 Dataset
			9.5.5.2 Empirical settings
			9.5.5.3 Experiments and Results
				Threshold-less Closed and Open Set Classification
				Threshold-based Open Set Classification and Rejection
		9.5.6 Image Document Classification Concluding Remarks
	References
Chapter 10 Large-scale Systems and Applications
	10.1 Conceptual System Organization andWorkflow
		10.1.1 PrIx Components
		10.1.2 Spots Database
		10.1.3 PrIx Search Engine and User Interface
	10.2 Architecture Design
		10.2.1 Web and Data Servers
		10.2.2 PrIx Server and Search Engine
		10.2.3 Web Client
	10.3 Large-Scale Applications
		10.3.1 Tr´esor des Chartes (Chancery)
		10.3.2 Teatro del Siglo de Oro (TSO)
		10.3.3 Bentham Papers (Bentham)
		10.3.4 Parcels from Indias and C´adiz Archives (Carabela)
		10.3.5 Finnish Court Records (FCR)
		10.3.6 General Discussion on Large-Scale Applications
	References
Chapter 11 Conclusion and Outlook
	11.1 Contribution Summary
		Probabilistic Indexing Framework (PrIx)
		Probabilistic Models of Handwritten Text
		Indexing Algorithms based on PrIx
		Probabilistic Interpretation of KWS Methods
		Beyond Traditional and Academic KWS
	11.2 FutureWork
		Stochastic Definitions of Relevance
		Better Statistical Models and Training
		Probabilistic Framework Applied to Other Domains
	References
Appendix A The Probability Ranking Principle
	A.1 Ranking Multiple Relevant Images
	A.2 Evaluation Measures and Optimality
		A.2.1 Precision-at-k
		A.2.2 Recall-at-k
		A.2.3 Average Precision (AP)
		A.2.4 Discounted Cumulative Gain (DCG)
		A.2.5 Normalized Discounted Cumulative Gain (NDCG)
	A.3 Global and Mean Measures
	References
Appendix B Weighted Finite State Transducers (WFST)
	B.1 Introduction
	B.2 Description
	B.3 WFST Operations
		B.3.1 Composition
		B.3.2 Shortest Path and Distance
	B.4 Determinization
	References
Appendix C Text Image Document Collections and Datasets
	General Remarks About How the Dataset Statistics Are Reported
	C.1 IAM
	C.2 The Bentham Papers Collection and Datasets
		C.2.1 ICFHR-2014 Competition on HTR (BEN1)
			C.2.1.1 Line-level PrIx Experiments
			C.2.1.2 Multi-word Page-level PrIx Experiments
		C.2.2 ICFHR-2014 Competition on KWS (BEN2)
		C.2.3 ICDAR-2015 Competition on KWS (BEN3)
		C.2.4 Large Bentham Dataset used in [28] (BEN4)
	C.3 GeorgeWashington (GW)
		Line-level Settings
		Word-level Settings
	C.4 Parzival (PAR)
	C.5 Plantas (PLA)
	C.6 Passau Parish Records (PAS)
	C.7 Tr´esor des Chartes and Chancery (CHA)
	C.8 Spanish Golden Age Theater (TSO)
	C.9 Parcels from Indias and C´adiz Archives: Carabela (CAR)
	C.10 Finnish Court Record (FCR)
		Dataset for Hyphenated-Word Experiments
	C.11 The Vorau-253 Sheet Music Manuscript and Dataset
	C.12 A Dataset for Multi-page Handwritten Deeds Classification
	References