Model-based comparative measure for vector sequences and word spotting using same

• US 20100191532A1
• Filed: 01/28/2009
• Published: 07/29/2010
• Est. Priority Date: 01/28/2009
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Rodriguez Serrano, Jose A., Perronnin, Florent C.
• Granted Patent: US 8,311,335 B2
• Time in Patent Office: Days
• US Class Current: 704/256.7
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 10/85 Markov-related models; Markov random fields
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models

Abstract

An object comparison method comprises: generating a first ordered vector sequence representation of a first object; generating a second ordered vector sequence representation of a second object; representing the first object by a first ordered sequence of model parameters generated by modeling the first ordered vector sequence representation using a semi-continuous hidden Markov model employing a universal basis; representing the second object by a second ordered sequence of model parameters generated by modeling the second ordered vector sequence representation using a semi-continuous hidden Markov model employing the universal basis; and comparing the first and second ordered sequences of model parameters to generate a quantitative comparison measure.

Claims

1. A storage medium storing instructions executable to compare an input:

vector sequence with a reference semi-continuous hidden Markov model (SC-HMM) having a model basis and an ordered sequence of reference weight parameters using a comparison method including;

modeling the input vector sequence using a SC-HMM having the model basis to generate an ordered sequence of input vector weight parameters, and

comparing the ordered sequence of input vector weight parameters and the ordered sequence of reference weight parameters to generate a quantitative comparison measure.

2. The storage medium as set forth in claim 1, wherein the model basis comprises a Gaussian mixture model (GMM).

3. The storage medium as set forth in claim 1, wherein the stored instructions are further executable to generate the reference SC-HMM by modeling a single reference vector sequence using a SC-HMM having the model basis.

4. The storage medium as set forth in claim 1, wherein the stored instructions are further executable to generate the reference SC-HMM by modeling a training set including a plurality of reference vector sequences using a SC-HMM having the model basis.

5. The storage medium as set forth in claim 1, wherein the stored instructions are further executable to generate the reference SC-HMM by extracting an ordered sequence of feature vectors from an input image and modeling the ordered sequence of feature vectors using a SC-HMM having the model basis.

6. The storage medium as set forth in claim 5, wherein the stored instructions are further executable to generate the reference SC-HMM by (I) extracting one or more ordered sequences of feature vectors from a corresponding one or more reference images to generate a training set and (II) modeling the training set using a SC-HMM having the model basis.

7. The storage medium as set forth in claim 1, further storing instructions executable to define a word spotting application that invokes the instructions executable to compare an input vector sequence with a reference SC-HMM with the input vector sequence derived from an input image of a handwritten word or phrase and the reference SC-HMM representing a handwritten word or phrase of interest.

8. The storage medium as set forth in claim 7, further storing instructions to generate the reference SC-HMM based on images of the handwritten word or phrase of interest printed using a plurality of different computer-generated fonts.

9. The storage medium as set forth in claim 1, wherein the comparing uses a dynamic time warping (DTW) distance to compare the ordered sequence of input vector weight parameters and the ordered sequence of reference weight parameters to generate a quantitative comparison measure.

10. The storage medium as set forth in claim 1, wherein a number of states of the SC-HMM is less than a length of the input vector sequence.

11. An object comparison method comprising:

generating a first ordered vector sequence representation of a first object;

generating a second ordered vector sequence representation of a second object;

representing the first object by a first ordered sequence of model parameters generated by modeling the first ordered vector sequence representation using a semi-continuous hidden Markov model employing a universal basis;

representing the second object by a second ordered sequence of model parameters generated by modeling the second ordered vector sequence representation using a semi-continous hidden Markov model employing the universal basis; and

comparing the first and second ordered sequences of model parameters to generate a quantitative comparison measure.

12. The object comparison method as set forth in claim 11, wherein at least one of the first object and the second object comprises a plurality of objects.

13. The object comparison method as set forth in claim 11, wherein the universal basis comprises a Gaussian mixture model (GMM) and the modeling operations adjust weight parameters of the Gaussian components of the GMM but do not adjust mean or spread parameters of the Gaussian components of the GMM.

14. The object comparison method as set forth in claim 13, wherein the first ordered sequence of model parameters and the second ordered sequence of model parameters comprise weight parameters of the Gaussian components of the GMM but do not comprise transition parameters of the semi-continuous Hidden Markov Model.

15. The object comparison method as set forth in claim 11, wherein:

the first object is an image of a handwritten word or phrase or a plurality of images of a handwritten word or phrase, and

the second object is an image of a reference word or phrase of interest or a training set of images of reference samples of a word or phrase of interest.

16. The object comparison method as set forth in claim 15, further comprising:

optimizing at least static parameters of a basis to generate the universal basis, the first ordered sequence of model parameters and the second ordered sequence of model parameters not including the static parameters.

17. The object comparison method as set forth in claim 16, wherein the basis comprises a Gaussian Mixture Model (GMM) and the static parameters comprise mean and spread parameters of the GMM.

18. The object comparison method as set forth in claim 15, further comprising:

generating the first object by segmentation of an image of a page of a document; and

labeling the document based on the quantitative comparison measure.

19. The object comparison method as set forth in claim 11, wherein the the representing operations employ a number of states of the SC-HMM that is less than a length of first ordered vector sequence representation.

20. The object comparison method as set forth in claim 11, wherein the the representing operations employ a number of states of the SC-HMM that is equal to a length of first ordered vector sequence representation.

21. A document processing system comprising:

segmenting at least one image of a page of a document to generate a plurality of word or phrase images;

generating input ordered vector sequence representations of the plurality of word or phrase images;

modeling the input ordered vector sequence representations to generate corresponding weight parameter sequences using a semi-continuous hidden Markov model employing a Gaussian mixture model (GMM) basis whose constituent Gaussian components have fixed mean and spread parameters; and

labeling the document based on comparison of the weight parameter sequences with one or more word or phrase of interest models.

22. The document processing system as set forth in claim 21, wherein the labeling comprises:

computing distance measures between the weight parameter sequences and the one or more word or phrase of interest models and

labeling the document based on the distance measures.

23. The document processing system as set forth in claim 21, wherein the fixed mean and spread parameters of the GMM basis are trained respective to a training set of images of handwritten text including at least some textual content not corresponding to the one or more word or phrase of interest models.

24. The document processing system as set forth in claim 23, wherein each of the one or more word or phrase of interest models are trained based on one or more images of a word or phrase of interest.

25. The document processing system as set forth in claim 23, wherein each of the one or more word or phrase of interest models are trained based on a plurality of images of a word or phrase of interest in different computer-generated type fonts.