Loading [a11y]/accessibility-menu.js
N-tuple features for OCR revisited | IEEE Journals & Magazine | IEEE Xplore

N-tuple features for OCR revisited


Abstract:

N-tuple features for optical character recognition have received only scattered attention since the 1960s. Our main purpose is to show that advances in computer technolog...Show More

Abstract:

N-tuple features for optical character recognition have received only scattered attention since the 1960s. Our main purpose is to show that advances in computer technology and computer science compel renewed interest. N-tuple features are useful for printed character classification because they indicate the presence or absence of a given rigid configuration of n black and white pixels in a pattern. Desirable n-tuples fit each pattern of a specified (positive) training set of characters in at least p different shift positions, and fail to fit each pattern of a specified (negative) training set by at least n-q pixels in each shift position. We prove that the problem of finding a distinguishing n-tuple is NP-complete, by examining a natural subproblem with binary strings called the missing configuration problem. The NP-completeness result notwithstanding, distinguishing n-tuples are found automatically in a few seconds on contemporary workstations. We exhibit a practical search algorithm for generating, from a small training set, a collection of n-tuples with low class-conditional correlation and with specified design parameters n, p, and q. The generator, which is available on the Internet, is empirically shown to be effective through a comparison with a benchmark generator. We show experimentally that the design parameters provide a useful tradeoff between distinguishing power and generation time, and also between the conditional probabilities for the positive and negative classes. We explore the feature probabilities obtainable for various dichotomies, and show that the design parameters control the feature probabilities.
Page(s): 734 - 745
Date of Publication: 31 July 1996

ISSN Information:


References

References is not available for this document.