Writer Recognition by

Computer Vision
Jeffrey P. Woodard M ITRE CO RP
Christopher P. Saunders M ITRE CO RP & S out h Da k ot a S t a t e Uni ve r s ity

Mark J. Lancaster US G

Measurement Science and Standards in Forensic Handwriting Analysis Conference

June 4-5, 2013, NIST Gaithersburg, MD

Approved by MITRE for Public Release: 10-2431

Approved for Public Release: 12-4194
Distribution Unlimited

© 2013 The MITRE Corporation. All rights reserved.

 |2|

MITRE Computer Vision Approach

 Algorithms used common in science and engineering

 First known application to forensic handwriter

recognition

 Public domain intellectual property

 No linguistic analysis

 No segmentation into units

 Supervision only for classification

© 2013 The MITRE Corporation. All rights reserved.

 |3|

Overview

 Methods
 Features
 Clustering
 Bag of Words
 Latent Approaches

 Experiments
 Arabic
 Dutch

© 2013 The MITRE Corporation. All rights reserved.

 |4|

Local Features: distinctiveness & invariance

S Transform Descriptor 1
{99 52 16 24 …}


Transform Descriptor 2
{98 52 16 23 …}


R Transform Descriptor 3
{41 0 10 129 …}
 |5|

Lowe’s Scale Space

Scale 1 Scale 2 Scale 3 Scale 4 Scale 5

Octave 1

Octave 2

Octave 3
Gaussian Representation

Find
Extrema

Difference of Gaussians Representation

 |6|

Local Features Circle center: feature x-y position

Circle radius: feature scale
Original Image Circle arrow: dominant orientation(s)
DoG-SIFT features
 |7|

Vector Quantization (VQ)

 K-means, Generalized Lloyd clustering
Gersho, A. & Gray, R. (1992) Vector Quantization and Signal Compression, Boston: Kluwer Academic Press.

 Many different local descriptors quantized to

small codebook -- “visual words”
 Represent each image by histogram of visual
words
X   x1 , x2 , x3 , , xB   R B128
Local Features

Iterate 
i:C ( i )  k
xi
mk  , k  1, ,L
Nk
C  arg min xi  mk 2 , i  1,
*
i
2
,B i å  arg min xt  Ciå
1 k  L i

Training Testing
 |8|

VQ “VISUAL WORDS”
100 random image regions from Arabic, DoG detector, SIFT descriptor, 512 codewords

Region sizes vary: all displayed identically

Regions for VQ codeword 1 Regions for VQ codeword 2 Regions for VQ codeword 3

“Visual words” represent fundamental properties associated with early to middle vision
 |9|

Bag of Words Representation

Image Local Features

Images
Histogram
5 VQ encoding
2 3 1
3
Counts

3
2 3 3
2
21 3 3
1
1 2 3 3 33 1
VQ index
1 12
3
 First learning… …Then recognition | 10 |

Images: Class 1 Images: Class N

Class Unknown

…
Local Features
Clustering Codebook
Local Features

image representations

Image or Class Models Class

…
Class 1 Class N
Decision
Adapted from L. Fei-Fei (UIUC, 2007)
 | 11 |

A Hierarchy of Visual Abstraction

more
Visual Meaning ?
Abstraction

Visual Words

Features

Pixels
less
 | 12 |

probabilistic Latent Semantic Analysis

(pLSA):Text Documents documents modeled as combinations of
latent topics

Text Document Latent topic Words

Generative View
 Select a document di with prob P(di)
 Pick latent class zk with prob P(zk|di)
 Generate keyword wj with prob P(wj|zk)

d z w  Boxes replicate

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 50, NO. 3, MARCH 2002 Bag of Words
A Survey of Convergence Results on
Particle
Filtering Methods for Practitioners
Dan Crisan and Arnaud Doucet
Abstract—Optimal filtering problems are ubiquitous in signal
processing and related fields. Except for a restricted class of
models, the optimal filter does not admit a closed-form expression. Word Word Counts
Particle filtering methods are a set of flexible and powerful
sequential Monte Carlo methods designed to solve the optimal
filtering problem numerically. The posterior distribution of
Index
“Particle Filter”
state is approximated by a large set of Dirac-delta masses
samples/particles) that evolve randomly in time according to the
dynamics of the model and the observations. The particles are
interacting; thus, classical limit theorems relying on statistically
1 Filter 5
independent samples do not apply. In this paper, our aim is to
present a survey of recent convergence results on this class of
methods to make them accessible to practitioners.
Index Terms—Bayesian estimation, optimal filtering, particle filtering,
Count Keywords 2 Particle 2
sequential Monte Carlo, state-space models.
I. INTRODUCTION
j Method 12
M ANY models in signal processing can be cast in a statespace
form. In most applications, prior knowledge of the
system is also available. This knowledge allows us to adopt a
Bayesian approach, that is, to combine a prior distribution for
… …
unknown quantities with a likelihood function relating these
quantities to the observations. Within this setting, one performs
inference on the unknown state according to the posterior distribution.
Often, the observations arrive sequentially in time, and
N Result 1
is interested in estimating recursively in time the evolving
say, larger than 4. Moreover, the rate of convergence of the approximation
error decreases as the state dimension increases.
That is, these methods suffer from the so-called curse of dimensionality.
Hofmann, T. (2001) Unsupervised learning by probabilistic latent semantic analysis. Machine Learning Journal, Vol. 42(1), pp. 177-196.
Following the seminal paper by Gordon, Salmond, and
Smith introducing the bootstrap filter/sampling importance resampling
[19], there has been a surge of interest in particle filtering
 | 13 |

pLSA for Images

images modeled as combinations of
latent topics

Image Latent topic Feature index

Generative View
 Select a an image di with prob P(di)
 Pick latent topic zk with prob P(zk|di)
 Generate VQ index w j with prob P(wj|zk)
d z w
Bag of Words

Word Word Counts

Index

1 5
“Writing
Extract Style”
Features
2 2
Quantize
Count Visual Words 3 12

… …

L 1
 | 14 |

pLSA Object “Discovery”

Ranked by max P(d| zk) = argmax P(Image | Objectk )

Topic 1 Style = “tight” Topic 2 Style = “loose”

50

39 29
46 46 46
Writer indexes shown in green

13 5
39
39 48 48

9 48
13 12 5
13
Ranked left-to-right, top to bottom
Woodard, J. Computer Vision for Forensic Applications, February Fourier Talks, Norbert Wiener Center, Department of
Mathematics, University of Maryland, Feb. 17-18, 2011
 | 15 |

Results: Dutch Uppercase Database

250 Subjects
2 documents per subject
500 total documents
Style: Mixed Printed and Cursive
Gray Scale
Text Independent

Strict leave one out (SLOO) Cross-validation

Approach Cross- Features Outside VQ Codebook Rank-1 TIME

Validation Codebook size %Error (hrs)

MITRE3
Spatial SLOO Hessian- IAM1 512 3.8 1.04
Pyramid Affine partial

Two-level SLOO Texture & IAM1 400 14 ?

probabilistic Allographic partial

Univ. Groningen2

1[Link] .
2Brink, A., Smit, J., Bulacu, M. & Schomaker, L. (2012) Writer identification using directional ink-trace width measurements. Pattern Recognition, Vol. 45, pp. 162-171.
3Woodard, J., Saunders, C. & Lancaster, M. Computer Vision and Statistical Learning (on a Budget), Defense Threat Analysis/National
Science Foundation/National Geospatial Intelligence Agency Workshop on Algorithms, San Diego, CA, November 17-22, 2012
 | 16 |

Results: Dutch Lowercase Database

250 Subjects
2 documents per subject
500 total documents
Style: Printed Uppercase
Gray Scale
Text Independent

Strict leave one out (SLOO) Cross-validation

Approach Cross- Features Outside VQ Codebook Rank-1 TIME

Validation Codebook size %Error (hrs)

MITRE3
pLSA 10-fold Hessian- IAM1 512 11.8 15.4
cross Affine partial
Spatial SLOO Hessian- IAM1 512 4.4 1.31
Pyramid Affine partial

Bulacu & SLOO Texture & IAM1 400 16 ?

Univ. Groningen2 Schomaker Allographic partial
(2007)

1[Link]

2Bulacu, M. & Schomaker, L. (2007) Text-independent writer identification and verification using textural and allographic features. IEEE Trans. on Pattern
Analysis and Machine Intelligence, Special Issue - Biometrics: Progress and Directions, vol. 29, no. 4, pp. 701-71, April

3Woodard, J., Saunders, C. & Lancaster, M. Computer Vision and Statistical Learning (on a Budget), Defense Threat Analysis/National
Science Foundation/National Geospatial Intelligence Agency Workshop on Algorithms, San Diego, CA, November 17-22, 2012
 | 17 |

Summary

 Fully automated methods handwriter recognition methods

based on general computer vision methods

 Reasonable performance achieved on Dutch, Arabic, and other

languages with little or no re-engineering

 Little or no human supervision required

 All algorithms are believed to be public domain

 Much more work remains!

© 2013 The MITRE Corporation. All rights reserved.

 | 18 |

Backups
 | 19 |

Querying PLSA: Result

object overlap: probability that chosen objects
in first and second images are similar: “cosine
similarity”

K
sim (d i , d m )   P ( zk | d i ) P ( zk | d m )
k 1

 K
L
 nij nmj
 α    P ( zk | d i , w j ) P ( zk | d m , w j ) 
j 1  k 1   nij  nmj
j j
VQ index sense overlap: do both VQ indexes
refer to the same object? VQ index overlap: do both images contain
common indexes?

retrieved class d *  arg max j{ sim(d i , d j )}

Idea adapted from slide and research by T. Hofmann, Brown Univ. 2001