Preservation: scanning and OCR tactics for old printouts

[bill75]

@EdS

It seems likely that the best OCR solution might recognise and be specific to the kind of printer used.

Yes that’s right. OCR is hard, take advantage of every constraint you can. By working specifically on the dot matrix problem I was able to far exceed contemporary general-purpose OCR, writing the code from scratch in about ten days (much of which was GUI work). But the dot matrix problem is much simpler than the line printer and N50CH problems posted above.

I was really quite surprised at how poor the Adobe PDF OCR system was on what seemed like a simple font–fixed spacing, single font, uppercase only. Others reported similar poor results with OCR attempts on legacy printouts.

[bill75]

All that’s left to describe is how the dot likelihood vector is used to compute a score for each character in the font. It has three components: base score for dots expected to be present, extra dot penalty for dots expected to be absent, and delta scores for confusing pairs.

The base score is the average of the dot likelihoods over dots expected to be present. This is a very smooth function of the underlying grey scale values. Small changes in shading lead to small changes in score, which makes recognition much less brittle than with hard-threshold methods.

From the base score an extra-dot penalty is subtracted. Extra dots are much less likely to be produced by the printer than missing dots, so the penalty is fairly strong. The total dot likelihood over dots expected to be absent is multiplied by an extra-dot penalty factor, currently set to 0.2, and then subtracted from the base score.

Finally the character’s deltas, if any, are considered. Each delta has a list of the dots that are different between the character pair. Here are the deltas for the Weather Radar font. For each character there is a list of similar ones. For example, the 6 is similar to the 8 and S. The 8 has 2 dots that the 6 doesn’t, and is missing one dot that the 6 has, so it is listed as 8(+2,-1).

3 9(+4,-0)
5 S(+1,-3)
6 8(+2,-1) S(+0,-3)
8 6(+1,-2) 9(+1,-2) S(+0,-4)
9 3(+0,-4) 8(+2,-1) S(+0,-3)
C G(+4,-0)
G C(+0,-4)
O Q(+2,-0)
P R(+4,-0)
Q O(+0,-2)
R P(+0,-4)
S 5(+3,-1) 6(+3,-0) 8(+4,-0) 9(+3,-0)
, ;(+1,-0) .(+0,-4)
; ,(+0,-1)
. ,(+4,-0) :(+2,-1) '(+3,-1)
: .(+1,-2)
| !(+1,-2)
! |(+2,-1)
’ .(+1,-3)

A delta score is computed for every character on the list. It is the square of the average likelihood that the character, and not its delta, is correct. Suppose for example that we’re trying to determine whether a dot likelihood vector is a 6 or an 8. The 2 dots that the 8 has but the 6 doesn’t have likelihoods of 0.1 and 0.2, and the dot that the 6 has but the 8 doesn’t has likelihood of 0.9. The delta score for the 6 is

Likewise for the 8 it is

So if it’s a 6 or an 8, we’re very confident it’s a 6 and not an 8. That doesn’t mean it is a 6, the other components of the score have to be considered.

Squaring the average prevents true ambiguity from yielding too much confidence. If the average is 0.5, both characters get delta scores of 0.25—we can’t tell them apart.

The final score for a character is the minimum of the base score minus the extra dot penalty, and all of the delta scores. Minimum is a generalization of Boolean AND for likelihood values, with maximum a generalization of OR, and 1-x a generalization of NOT. This generalization obeys De Morgan’s theorem.

[mainframetom]

@bill75

During the spiral scan each character in the font records the highest score it found and where in the scan it was found. When the spiral scan ends, the character with the second-highest score is identified from the recorded bests. If the best overall score does not exceed 0.5, and does not exceed the second best by 0.2, it is judged to be of insufficient confidence and will be displayed for human judgement.

Is this sufficient? Maybe there should be at least an option for a warning if the first try is not 95 or 100% detected.

[bill75]

When to warn is a tradeoff between false positives, which must be rare, and false negatives, which require human intervention. The rules I described were sufficient for my specific purpose, which was recovering around 150,000 characters from a listing printed in 1977. There were a half-dozen false positives and a couple of hundred warnings that I had to review, the vast majority of which were correctly identified by the OCR. I could find and fix the false positives by comparing the object code in the 1977 listing with object code generated by assembling the source today. For different purposes, different rules for when to warn would be appropriate.