Document Analysis And Recognition With Wavelet And Fractal Theories

by Yuan Yan Tang

Overview

Many phenomena around the research in document analysis and understanding are much better described through the powerful multiscale signal representations than by traditional ways.From this perspective, the recent emergence of powerful multiscale signal representations in general and fractal/wavelet basis representations in particular, has been particularly timely. Indeed, out of these theories arise highly natural and extremely useful representations for a variety of important phenomena in document analysis and understanding.This book presents both the development of these new approaches as well as their application to a number of fundamental problems of interest to scientists and engineers in document analysis and understanding.

Product Details

ISBN-13:	9789814401005
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	03/26/2012
Series:	Series In Machine Perception And Artificial Intelligence , #79
Pages:	372
Product dimensions:	9.10(w) x 6.20(h) x 1.00(d)

Table of Contents

Preface vii

Chapter 1 Basic Concepts of Document Analysis and Understanding 1

1.1 Introduction 1

1.2 Basic Model of Document Processing 4

1.3 Document Structures 8

1.3.1 Strength of Structure 8

1.3.2 Geometric Structure 9

1.3.2.1 Geometric Complexity 10

1.3.3 Logical Structure 12

1.4 Document Analysis 13

1.4.1 Hierarchical Methods 13

1.4.1.1 Top-Down Approach 14

1.4.1.2 Bottom-Up Approach 16

1.4.2 No-Hierarchical Methods 17

1.4.2.1 Modified Fractal Signature 18

1.4.2.2 Order Stochastic Filtering 20

1.4.3 Web Document Analysis 22

1.5 Document Understanding 23

1.5.1 Document Understanding Based on Tree Transformation 24

1.5.2 Document Understanding Based on Formatting Knowledge 25

1.5.3 Document Understanding Based on Description Language 26

1.6 Form Document Processing 27

1.6.1 Characteristics of Form Documents 27

1.6.2 Wavelet Transform Approach 27

1.6.3 Approach Based on Form Description Language 28

1.6.4 Form Document Processing Based on Form Registration 31

1.6.5 Form Document Processing System 31

1.7 Character Recognition and Document Image Processing 32

1.7.1 Handwritten and Printed Character Recognition 32

1.7.1.1 Extracting Multiresolution Features in Recognition of Handwritten Numerals with 2-D Haar Wavelet 33

1.7.1.2 Recognition of Printed Kannada Text in Indian Languages 37

1.7.1.3 Wavelet Descriptors of Handprinted Characters 38

1.7.2 Document Image Analysis Based on Multiresolution Hadamard Representation (MHR) 38

1.8 Major Techniques 43

1.8.1 Hough Transform 44

1.8.2 Techniques for Skew Detection 45

1.8.3 Projection Profile Cuts 46

1.8.4 Run-Length Smoothing Algorithm (RLSA) 47

1.8.5 Neighborhood Line Density (NLD) 48

1.8.6 Connected Components Analysis (CCA) 49

1.8.7 Crossing Counts 50

1.8.8 Form Definition Language (FDL) 50

1.8.9 Texture Analysis - Gabor Filters 51

1.8.10 Wavelet Transform 52

1.8.11 Other Segmentation Techniques 53

Chapter 2 Basic Concepts of Fractal Dimension 55

2.1 Definitions of Fractals 55

2.2 Hausdorff Dimension 57

2.2.1 Hausdorff Measure 57

2.2.2 Hausdorff Dimension 60

2.2.3 Examples of Computing Hausdorff Dimension 64

2.3 Box Computing Dimension 69

2.3.1 Dimensions 69

2.3.2 Box Computing Dimension 70

2.3.3 Minkowski Dimension 75

2.3.4 Properties of Box Counting Dimension 81

2.4 Basic Methods for Calculating Dimensions 83

Chapter 3 Basic Concepts of Wavelet Theory 95

3.1 Continuous Wavelet Transforms 95

3.1.1 General Theory of Continuous Wavelet Transforms 95

3.1.2 The Continuous Wavelet Transform as a Filter 111

3.1.3 Description of Regularity of Signal by Wavelet 114

3.1.4 Some Examples of Basic Wavelets 118

3.2 Multiresolution Analysis (MRA) and Wavelet Bases 124

3.2.1 Multiresolution Analysis 124

3.2.1.1 Basic Concept of MRA 124

3.2.1.2 The Solution of Two-Scale Equation 129

3.2.2 The Construction of MRAs 139

3.2.2.1 The Biorthonormal MRA 146

3.2.2.2 Examples of Constructing MRA 153

3.2.3 The Construction of Biorthonormal Wavelet Bases 163

3.2.4 S. Mallat Algorithms 168

Chapter 4 Document Analysis by Fractal Dimension 173

4.1 Introduction 173

4.2 Document Analysis Based on Modified Fractal Signature (MFS) 179

4.2.1 Basic Idea of Modified Fractal Signature (MFS) 179

4.2.2 δ-Parallel Bodies 180

4.2.3 Blanket Technique to Extract Fractal Feature 183

4.3 Algorithm of Modified Fractal Signature (MFS) 187

4.3.1 Identification of Different Blocks of Document by Fractal Signature 187

4.3.2 Modified Fractal Signature (MFS) 191

4.4 Experiments 194

Chapter 5 Text Extraction by Wavelet Decomposition 203

5.1 Introduction 203

5.2 Wavelet Decomposition of Pseudo-Motion Functions 204

5.2.1 One Variable Case 204

5.2.2 Two Variables Case 208

5.3 Segmentation of Different Areas of Document Image 209

5.3.1 Segmentation of Areas of Different Frequency 209

5.3.2 WDPM Algorithm 212

5.4 Experiments 215

5.4.1 Position of License Plate 215

5.4.1.1 Choose of the Bases 215

5.4.1.2 Experimental Results 219

5.4.2 Localization of Text Areas of Document Images 220

Chapter 6 Rotation Invariant by Fractal Theory with Central Projection Transform (CPT) 231

6.1 Introduction 231

6.1.1 Rotations 232

6.1.2 Rotation Invariants 234

6.1.3 Rotation Invariant of Discrete Images 237

6.1.4 Rotation Invariants in Pattern Recognition 241

6.1.4.1 Boundary Curvature 242

6.1.4.2 Fourier Descriptors 242

6.1.4.3 Zernik Moments 243

6.1.4.4 Neural Networks 243

6.2 Preprocessing and Central Projection Transform (CPT) 244

6.2.1 Preprocessing 244

6.2.2 Central Projection Transform (CPT) 246

6.2.2.1 Basic Definitions of CPT 246

6.2.2.2 Properties of CPT 250

6.2.2.3 Parallel Algorithm for CPT 252

6.2.2.4 Contour Unfolding 253

6.3 Rotation Invariance Based on Box Computing Dimension 256

6.3.1 Estimation of the 1-D Fractal Dimension 256

6.3.2 Rotation Invariant Signature (RIS) 258

6.4 Experiments 267

6.4.1 Rotation Invariant Signature (RIS) Algorithm 267

6.4.1.1 Estimation of the BCD 267

6.4.1.2 Extraction of Feature with Rotation Invariant Property 269

6.4.2 Experimental Procedure and Results 271

Chapter 7 Wavelet-Based and Fractal-Based Methods for Script Identification 279

7.1 Introduction 280

7.2 Wavelet-Based Approach 282

7.2.1 Image Decomposition by Multi-Scale Wavelet Transform 284

7.2.2 Wavelet-Based Features 287

7.2.2.1 Average Energy of Document Image 287

7.2.2.2 Wavelet Energy Distribution Features (F_d) 289

7.2.2.3 Wavelet Energy Distribution Proportion Features (F_dp) 291

7.2.3 Experiments 293

7.2.3.1 Distance Functions 293

7.2.3.2 Experimental Results 295

7.3 Fractal-Based Approach 300

7.3.1 Algorithm 301

7.3.2 Experiments 302

Chapter 8 Writer Identification Using Hidden Markov Model in Wavelet Domain (WD-HMM) 309

8.1 Introduction 309

8.2 Hidden Markov Model and Relative Statistical Knowledge 310

8.2.1 Expectation Maximization (EM) Algorithm 310

8.2.2 Gaussian Mixture Model (GMM) and Expectation Maximization (EM) for Gaussian Mixture Model (GMM) 312

8.2.3 Hidden Markov Model 316

8.2.3.1 Basic Frame of HMM 316

8.2.3.2 Three Basic Problems for HMM 318

8.2.3.3 Important Assumptions for HMM 319

8.3 Hidden Markov Models in Wavelet Domain 320

8.3.1 GMM Model for a Single Wavelet Coefficient 320

8.3.2 Independence Mixture Model 320

8.3.3 WD-HMM and EM for WD-HMM 321

8.4 Writer Identification Using WD-HMM 324

8.4.1 The Whole Procedure 324

8.4.2 Feature Extraction 325

8.4.3 Similarity Measurement 326

8.4.4 Performance Evaluation 329

8.5 Experiments 329

Bibliography 337

Index 353