Marinai S., Fujisawa H. (eds.) Machine Learning in Document Analysis and Recognition

Подождите немного. Документ загружается.

Simone Marinai and Hiromichi Fujisawa (Eds.)

Machine Learning in Document Analysis and Recognition

Editor-in-chief

Prof. Janusz Kacprzyk

Systems Research Institute

Polish Academy of Sciences

ul. Newelska 6

01-447 Warsaw

Poland

E-mail:

kacprzyk@ibspan.waw.pl

Further volumes of this series can be found on our

homepage: springer.com

Vol. 66. Lakhmi C. Jain, Vasile Palade and Dipti

Srinivasan (Eds.)

Advances in Evolutionary Computing for System Design,

2007

ISBN 978-3-540-72376-9

Vol. 67. Vassilis G. Kaburlasos and Gerhard X. Ritter (Eds.)

Computational Intelligence Based on Lattice Theory,

2007

ISBN 978-3-540-72686-9

Vol. 68. Cipriano Galindo, Juan-Antonio

Fern

andez-Madrigal and Javier Gonzalez

A Multi-Hierarchical Symbolic Model of the Environment

for Improving Mobile Robot Operation,

2007

ISBN 978-3-540-72688-3

Vol. 69. Falko Dressler and Iacopo Carreras (Eds.)

Advances in Biologically Inspired Information Systems:

Models, Methods, and Tools,

2007

ISBN 978-3-540-72692-0

Vol. 70. Javaan Singh Chahl, Lakhmi C. Jain,

Akiko Mizutani and Mika Sato-Ilic (Eds.)

Innovations in Intelligent Machines-1,

2007

ISBN 978-3-540-72695-1

Vol. 71. Norio Baba, Lakhmi C. Jain and Hisashi Handa

(Eds.)

Advanced Intelligent Paradigms in Computer

Games,

2007

ISBN 978-3-540-72704-0

Vol. 72. Raymond S.T. Lee and Vincenzo Loia (Eds.)

Computation Intelligence for Agent-based Systems,

2007

ISBN 978-3-540-73175-7

Vol. 73. Petra Perner (Ed.)

Case-Based Reasoning on Images and Signals,

2008

ISBN 978-3-540-73178-8

Vol. 74. Robert Schaefer

Foundation of Global Genetic Optimization

, 2007

ISBN 978-3-540-73191-7

Vol. 75. Crina Grosan, Ajith Abraham and Hisao Ishibuchi

(Eds.)

Hybrid Evolutionary Algorithms

, 2007

ISBN 978-3-540-73296-9

Vol. 78. Costin Badica and Marcin Paprzycki (Eds.)

Intelligent and Distributed Computing,

2008

ISBN 978-3-540-74929-5

Vol. 79. Xing Cai and T.-C. Jim Yeh (Eds.)

Quantitative Information Fusion for Hydrological

Sciences,

2008

ISBN 978-3-540-75383-4

Vol. 80. Joachim Diederich

Rule Extraction from Support Vector Machines,

2008

ISBN 978-3-540-75389-6

Vol. 81. K. Sridharan

Robotic Exploration and Landmark Determination,

2008

ISBN 978-3-540-75393-3

Vol. 82. Ajith Abraham, Crina Grosan and Witold

Pedrycz (Eds.)

Engineering Evolutionary Intelligent Systems,

2008

ISBN 978-3-540-75395-7

Vol. 83. Bhanu Prasad and S.R.M. Prasanna (Eds.)

Speech, Audio, Image and Biomedical Signal Processing

using Neural Networks,

2008

ISBN 978-3-540-75397-1

Vol. 84. Marek R. Ogiela and Ryszard Tadeusiewicz

Modern Computational Intelligence Methods for the

Interpretation of Medical Images,

2008

ISBN 978-3-540-75399-5

Vol. 85. Arpad Kelemen, Ajith Abraham and Yulan Liang

(Eds.)

Computational Intelligence in Medical Informatics,

2008

ISBN 978-3-540-75766-5

Vol. 86. Zbigniew Les and Mogdalena Les

Shape Understanding Systems,

2008

Vol. 87. Yuri Avramenko and Andrzej Kraslawski

Case Based Design,

2008

Studies in Computational Intelligence, Volume 90

(Eds.)

ISBN 978-3-540-75770-2

ISBN 978-3-540-76281-2

Vol.

90. Simone Marinai and Hiromichi Fujisawa (Eds.)

ISBN 978-3-540-76279-9

ISBN 978-3-540-75768-9

Vol. 76. Subhas Chandra Mukhopadhyay and Gourab Sen

Gupta (Eds.)

Autonomous Robots and Agents,

2007

ISBN 978-3-540-73423-9

Vol. 77. Barbara Hammer and Pascal Hitzler (Eds.)

Perspectives of Neural-Symbolic Integration,

2007

ISBN 978-3-540-73953-1

Evolutionary Computation in Practice, 2008

Vol. 89. Ito Takayuki, Hattori Hiromitsu, Zhang Minjie

Vol. 88. Tina Yu, David Davis, Cem Baydar and Rajkumar Roy

Machine Learning in Document Analysis and Recognition,

2008

and Matsuo Tokuro (Eds.)

ISBN 978-3-540-75705-4

Rational, Robust, Secure, 2008

Simone Marinai

Hiromichi Fujisawa (Eds.)

Machine Learning in Document

Analysis and Recognition

With 142 Figures and 41 Tables

123

Studies in Computational Intelligence ISSN 1860-949X

 2008 Springer-Verlag Berlin Heidelberg

This work is subject to copyright. All rights are reserved, whether the whole or part of the material

is concerned, speciﬁcally the rights of translation, reprinting, reuse of illustrations, recitation, broad-

casting, reproduction on microﬁlm or in any other way, and storage in data banks. Duplication of

this publication or parts thereof is permitted only under the provisions of the German Copyright Law

of September 9, 1965, in its current version, and permission for use must always be obtained from

Springer-Verlag. Violations are liable to prosecution under the German Copyright Law.

The use of general descriptive names, registered names, trademarks, etc. in this publication does not

imply, even in the absence of a speciﬁc statement, that such names are exempt from the relevant

protective laws and regulations and therefore free for general use.

Cover design: Deblik, Berlin, Germany

Printed on acid-free paper

987654321

springer.com

Simone Marinai

University of Florence

50139 Firenze

Italy

1-280, Higashi-Koigakubo

Kokubunji-shi, Tokyo 185-8601

Japan

ISBN 978-3-540-76279-9 e-ISBN 978-3-540-76280-5

Library of Congress Control Number: 2007939058

Dipartimento di Sistemi e Informatica

Via S. Marta, 3

marinai@dsi.unifi.it

fujisawa@crl.hitachi.co.jp

Hitachi Central Research Laboratory

Hiromichi Fujisawa

Preface

The objective of Document Analysis and Recognition (DAR) is to recognize

the text and graphical components of a document and to extract information.

With ﬁrst papers dating back to the 1960’s, DAR is a mature but still grow-

ing research ﬁeld with consolidated and known techniques. Optical Character

Recognition (OCR) engines are some of the most widely recognized prod-

ucts of the research in this ﬁeld, while broader DAR techniques are nowadays

studied and applied to other industrial and oﬃce automation systems.

In the machine learning community, one of the most widely known re-

search problems addressed in DAR is recognition of unconstrained handwrit-

ten characters which has been frequently used in the past as a benchmark for

evaluating machine learning algorithms, especially supervised classiﬁers.

However, developing a DAR system is a complex engineering task that

involves the integration of multiple techniques into an organic framework. A

reader may feel that the use of machine learning algorithms is not appropri-

ate for other DAR tasks than character recognition. On the contrary, such

algorithms have been massively used for nearly all the tasks in DAR. With

large emphasis being devoted to character recognition and word recognition,

other tasks such as pre-processing, layout analysis, character segmentation,

and signature veriﬁcation have also beneﬁted much from machine learning

algorithms.

This book is a collection of research papers and state-of-the-art reviews

by leading researchers all over the world including pointers to challenges and

opportunities for future research directions. The main goals of the book are

identiﬁcation of good practices for the use of learning strategies in DAR,

identiﬁcation of DAR tasks more appropriate for these techniques, and high-

lighting new learning algorithms that may be successfully applied to DAR.

Depending on reader’s interests, there are several paths that can be fol-

lowed when reading the chapters of the book. We therefore avoided grouping

the chapters into sections; instead we provide a deep introduction to the ﬁeld

and to the book’s contents in the ﬁrst chapter.

VI Preface

It is our hope that this book will help readers identify the current status

of the use of machine learning techniques in DAR. Moreover, we expect that

it can contribute to stimulate new ideas, new collaborations and new research

activities in this research arena.

We wish to express our warmest thanks to the Authors, without whose

interesting work this book would not have materialized.

Simone Marinai, Hiromichi Fujisawa

July 2007

Contents

Introduction to Document Analysis and Recognition

Simone Marinai ................................................. 1

Structure Extraction in Printed Documents Using Neural

Approaches

Abdel Bela¨ıd and Yves Rangoni .................................... 21

Machine Learning for Reading Order Detection in Document

Image Understanding

Donato Malerba, Michelangelo Ceci, and Margherita Berardi .......... 45

Decision-Based Speciﬁcation and Comparison of Table

Recognition Algorithms

Richard Zanibbi, Dorothea Blostein and James R. Cordy .............. 71

Machine Learning for Digital Document Processing: from

Layout Analysis to Metadata Extraction

Floriana Esposito, Stefano Ferilli, Teresa M.A. Basile,

and Nicola Di Mauro .............................................105

Classiﬁcation and Learning Methods for Character

Recognition: Advances and Remaining Problems

Cheng-Lin Liu and Hiromichi Fujisawa .............................139

Combining Classiﬁers with Informational Conﬁdence

Stefan Jaeger, Huanfeng Ma, and David Doermann ..................163

Self-Organizing Maps for Clustering in Document Image

Analysis

Simone Marinai, Emanuele Marino, and Giovanni Soda ..............193

Adaptive and Interactive Approaches to Document Analysis

George Nagy and Sriharsha Veeramachaneni .........................221

VIII Contents

Cursive Character Segmentation Using Neural Network

Techniques

Michael Blumenstein .............................................259

Multiple Hypotheses Document Analysis

Tatsuhiko Kagehiro and Hiromichi Fujisawa .........................277

Learning Matching Score Dependencies

for Classiﬁer Combination

Sergey Tulyakov and Venu Govindaraju .............................305

Perturbation Models for Generating Synthetic Training Data

in Handwriting Recognition

Tam´as Varga and Horst Bunke ....................................333

Review of Classiﬁer Combination Methods

Sergey Tulyakov, Stefan Jaeger, Venu Govindaraju,

and David Doermann .............................................361

Machine Learning for Signature Veriﬁcation

Sargur N. Srihari, Harish Srinivasan, Siyuan Chen,

and Matthew J. Beal .............................................387

Oﬀ-line Writer Identiﬁcation and Veriﬁcation Using Gaussian

Mixture Models

Andreas Schlapbach and Horst Bunke ...............................409

Index ..........................................................429

Contributors

Teresa M.A. Basile

Universit`adiBari

Dipartimento di Informatica

Via Orabona 4

70126 Bari - Italy

basile@di.uniba.it

Matthew J. Beal

Department of Computer Science

and Engineering,

University at Buﬀalo,

The State University of New York,

Buﬀalo NY, USA

mbeal@cse.buffalo.edu

Abdel Belaid

Universit´eNancy2

LORIA UMR 7503

France

Abdel.Belaid@loria.fr

Margherita Berardi

Universit`adiBari

Dipartimento di Informatica

Via Orabona 4

70126 Bari - Italy

berardi@di.uniba.it

Dorothea Blostein

School of Computing

Queen’s University

Kingston, Ontario,

Canada, K7L 3N6

blostein@cs.queensu.ca

Michael Blumenstein

School of Information and Commu-

nication Technology

Gold Coast campus

Griﬃth University QLD 4222

Australia

m.blumenstein@griffith.edu.au

Horst Bunke

University of Bern

Institute of Computer Science and

Applied Mathematics (IAM)

Neubr¨uckstrasse 10

CH-3012 Bern, Switzerland

bunke@iam.unibe.ch

Michelangelo Ceci

Universit`adiBari

Dipartimento di Informatica

Via Orabona 4

70126 Bari - Italy

ceci@di.uniba.it

Siyuan Chen

Center of Excellence for

Document Analysis and Recognition

(CEDAR),

Buﬀalo NY, USA

schen7@cedar.buffalo.edu