We have developed the notion of lexicon density as a metric to measure the expected accuracy of handwritten word recognizers. Thus far, researchers have used the size of the lexicon as a gauge for the difficulty of the handwritten word recognition task. For example, the literature mentions recognizers with accuracies for lexicons of sizes 10, 100, 1000, and so forth, implying that the difficulty of the task increases (and hence recognition accuracy decreases) with increasing lexicon size across recognizers. Lexicon density is an alternate measure which is quite dependent on the recognizer. There are many applications, such as address interpretation, where such a recognizer-dependent measure can be useful. We have conducted experiments with two different types of recognizers. A segmentation-based and a grapheme-based recognizer have been selected to show how the measure of lexicon density can be developed in general for any recognizer. Experimental results show that the lexicon density measure described is more suitable than lexicon size or a simple string edit distance.

Normalization of slant and skew is often used in processing a word image before recognition. In this paper, we prove the theoretical equivalence of different methods for slant and skew corrections. In particular, we show that correcting first for skew by rotation and then for slant by a shear transformation in the horizontal direction is equivalent to first correcting for slant by a shear transformation in the horizontal direction and then for skew by a shear transformation in the vertical direction. Our proof can be easily modified to prove equivalence of other methods for correcting the slant and skew.

We establish significantly improved bounds on the performance of the greedy algorithm for approximating set cover.In particular, we provide the first substantial improvement of the 20 year old classical harmonic upper bound, H(m), of Johnson, Lovssz, and ChvAt al, by showing that the performance ratio of the greedy algorithm is, in fact, exactly in m -in ht m + Q(l), where m is the size of the ground set.The difference between the upper and lower bounds turns out to be less than 1.1.This provides the first tight ansJysis of the greedy algorithm, as well as the first upper bound that lies below H(m) by a function going to infinity with m.We also show that the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on the integralit~gap.Our improvements result from a new approach which might be generally useful for attacking other similar problems.