OCR of unevenly lit documents

Someone gave me some scans in colour that needed converting via OCR into plain text. I thought I would run them through Tesseract, the main open source OCR tool. The results were dreadful, even when I converted them to greyscale as recommended. My images had three faults:

1. they had a large border showing the book's binding and the surrounding environment of the image
2. they were unevenly lit
3. The text was curved - the result of trying to photograph a bound volume of typewritten pages that could not be fully opened without damage

It seemed to me that these problems must be similar to those encountered in practically any digitisation project. But there didn't seem to be any good open-source solutions.

I wanted to fix at least fault 2 to see how Tesseract would fare when the image was, as recommended, in plain black and white. However, after wasting a whole afternoon Googling the problem and trying every conceivable filter in Photoshop and Gimp I couldn't reduce the image to black and white. The problem was the difference in illumination:

Shown on the right is a section of the upper right hand portion of a page, on the left the bottom left hand portion. When these are turned to a global black or white value one is hopelessly too dark and the other too light:

An idea

So I downloaded the FreeImage library and tried to use it to write a simple filter. I first reduced the image to greyscale and manually cropped it to simulate having already solved problem 1 above. Then I passed a small square 64x64 pixels over the image. For each square I computed the average greyscale value. Then I turned all pixels less than this value by at least 8 to black (lesser is darker). All others were turned to white. This very simple approach had the effect of obliterating the lighting differences and producing an evenly illuminated plain black and white text:

Curvature

Unfortunately, Tesseract still doesn't like the strong curvature. It seems to split up lines based on strict horizontals, because it mixed up text from adjacent lines that curved into each other's path. The next stage will be to 'uncurve' the text automatically.

From arbitrary overlap to HTML

If we try to represent original documents not authored in the digital medium, we soon discover that the pen or the printed type used to create them were not constrained, as modern embedded markup languages are, to represent only tree-structures. It would thus be very liberating to encode such documents for digital presentation on the Web, using arbitrary overlapping external properties instead of an embedded hierarchy of tags. This would provide a number of distinct advantages:

1. Properties could represent the source texts more accurately.
2. Different sets of properties could be combined in the same document.
3. With appropriate software, it will be easier to edit separate text and markup files than complex embedded markup.
4. Texts and markup, as separate building blocks, could be exchanged and reused for other applications.

These are winning arguments for at least digital humanists, and maybe for other people who use embedded markup.

How it works

To see how this can be done let's specify some fictitious properties that apply to random ranges of a short text:

0,12,'banana'
3,7,'pear'
12,9,'refrigerator'
13,4,'orange'
18,12,'pineapple'
22,34,'guava'
35,12,'grape'
48,9,'penguin'
52,17,'dog'

What this means is that the text, which is at least 69 bytes long, is 'marked-up' by a series of arbitrary properties. The offsets in the text where these properties start are specified by the first number in each line, their lengths by the second number, and their names by the quoted strings. Of course, in a real-world application the names would more likely be 'p' or 'span' or 'table' etc.

Reduction to intervals

But how can we turn this apparent chaos into syntactically correct HTML? The approach taken here is to break up the properties into a series of 'intervals' where all the properties are the same throughout. For example between offsets 52 and 55 the properties 'dog', 'guava' and 'penguin' are all active.

Intervals defined by overlapping properties

Although dividing the properties into intervals removes the overlap it also creates too many short sequences for efficient HTML. So the next step is to work out where we might be able join them up. To do that we need to know which tags may appear inside which other tags. In other words, we need a kind of basic schema.

On-the-fly deduced schemas

Fortunately we already have the HTML schema. Since we will be using CSS (cascading style sheets) to format the text, we can use CSS rules to tell us which HTML elements will represent our properties, and then work backwards to figure out how they will nest.

The size of the problem can be reduced by reflecting that not all of our overlapping properties will be rendered in HTML. Some have other uses, for example, to provide programming information, are not needed in the current view, or are intended for future use. So it is safe to ignore any properties that aren't mentioned in the CSS file. However, because HTML syntax is fairly loose, this only gives us part of the answer.

The missing information can be deduced from the properties themselves. If we are recording a play, for example, properties like 'line' almost always nest inside 'speech'. In those few cases where they don't, we can split the 'line' property so that it always nests within the dominant tag 'speech'.

Merging this statistical information about property nesting into that derived from the HTML schema allows us to reconstruct almost all of the structure needed to render the document correctly. However, since this relies on statistics, it is not absolutely guaranteed to work in all cases, but even when it doesn't we will still have valid HTML. The worst that can happen is that the formatting won't look right.

Using the deduced hierarchy information

One simple way to express a hierarchy is to record which elements may appear inside which other elements. If you have 10 elements that need rendering this means you must compute a 10x10 matrix. 10 is probably a realistic number in practice, but even with all 107 HTML5 tags a matrix of just 11,449 ints or 45K would suffice.

Properties (left) that may appear within other properties (top)

In my test program I just specified the nesting matrix manually. Following the natural analogy a 'guava' may appear inside a 'penguin', 'dog' or 'refrigerator', but an 'orange' cannot be inside a 'pineapple'. In the finished program, of course, such a matrix would be computed as described above.

From this hierarchy information we can easily work out when to start and stop tags. For each interval visited in order we separate the ranges into three sets:

1. closing: properties that are present in the previous interval but missing in the current one
2. opening: properties that are present in the current interval but were absent in the previous one
3. continuing: properties that are present in both the preceding and current intervals

After this initial classification we use the nesting matrix to correct any anomalies. Any property in the 'continuing' set that is contained by one from the 'closing' or 'opening' sets must be moved to the 'closing' set and also added to the 'opening' set. This is because, in order to preserve well-formedness, the closure or opening of the parent will force the closing and re-opening of a continuing child.

Remaining problems

Even after these measures two problems remain:

1. Since we allowed arbitrary overlap there is nothing to prevent two incompatible properties such as 'guava' and 'grape' being defined for the same interval. Neither may contain the other, so if they occur together one must be dropped.
2. Tags must be written out in the correct order: highest level containers first and the lowest level tags last. This can be achieved by sorting the ranges within each interval by their descending position in the hierarchy. We also use a stack to ensure that closing tags match and come out in the correct order.

The result

Once these adjustments have been made, the intervals can be printed out one at a time, the closing tags followed by the opening ones. Here is the output of the test program, with dots representing the text for clarity:

<banana>............</banana><refrigerator>.<orange>....</orange>.<pineapple>...</pineapple></refrigerator><pineapple>.........</pineapple><guava>..................</guava><penguin><guava>....</guava></penguin><dog><penguin><guava>....</guava>.</penguin>............</dog>

In this crazy random example the conflicting properties 'pear' and 'grape' had to be dropped. There was no way to render them given the containment rules. But the result is still well-formed XML and it would be HTML if we had used a CSS file to transform the properties.

Where to go from here

This test solution needs to be incorporated into the formatter tool and the whole thing converted into a php extension, so it can be used as a direct replacement for XSLT.

From TEI to HRIT and back again

Since we are designing a software suite to more or less replace embedded markup there has to be some way to import legacy texts. At first I thought the problem was insurmountable. Even if the original encoders had stuck to recommended guidelines such as the TEI (Text Encoding Initiative) they would have been forced to customise their encoding in two ways:

1. By adding custom tags and attributes, and
2. By making a selection of tags from the large number of available ones

In the second case it is clear that any general solution that embraced an arbitrary subset of TEI would have to support all of it. Since there are currently 519 tags in the scheme, and (probably) thousands of attributes, that is a daunting prospect for any programmer. And we are talking about meaningful conversion into an entirely different software system, not a simple one-for-one mapping. And in respect to point 1 any customised tags would either have to be left out, or their function would need to be specified by the user.

Solving the problem

When forced to perform the task, however, I soon realised that any customised tags must have already been specified by a user who understood XML. So that same user could supply a customised table of conversion in XML to say what should be done with them. If they didn't follow the Guidelines then they have to do a little extra work, but they're not shut out.

And in the second case only a small subset of TEI is regularly used by digital humanists. For the purposes of defining versions, for example, only a small number of tags come into play, and even customised ones would have to follow one of only a couple of basic patterns, which could be programmed in as general functions. The customisations could be handled by a 'recipe', or set of instructions on how to convert the files. A default recipe would be provided for standard files, which the user could extend or change at will.

Why do this at all?

Because HRIT format is much more powerful than TEI:

1. It allows arbitrary overlap of properties.
2. It does not mandate any standard tag names
3. It supports versions natively including transpositions
4. It allows mixing and matching of markup sets in the one text

That's more than enough reasons to move from TEI to HRIT. Another way of looking at it is to say that rather than replacing TEI it seeks to enhance it, and use it as an interchange format between HRIT and non-HRIT users. It depends on what kind of 'spin' you prefer.

Two-way conversion

Any conversion applied to legacy files (or, if you prefer, current files) would have to be reversible. Those who had imported their files into HRIT and changed their minds later on would feel 'locked in' if they couldn't back out, and those who hadn't made the switch would likewise be frightened off by that very prospect. So the overall process looks like this. Red/green arrows indicate as yet unavailable/available paths:

'TEI' refers to any TEI-encoded file. The two-way process works like this:

• Splitter splits the TEI file into N versions. By default it splits <app><rdg>...</rdg></app> structures as well as nested <del> and <add> and <choice> structures into versions. Unsplitter, not yet written, will take the versions (possibly modified) and try to put them back into one file, although this may be difficult. The recipe file is used by splitter to direct the splitting. It can be customised by the user to control which elements are split and how.
• Stripper removes the remaining markup from each separate version in TEI format. A different recipe file specifies simplifications of elements intended to be rendered as formats in the final HTML. One simplification might be the reduction of <hi rend="italic"> to the property 'italics'. The output of stripper is the HRIT standoff XML format. (But stripper is written in such a way that another format can be added if required). It expresses every TEI element as a potentially overlapping property with possible 'annotations' or attributes. These attributes are ignored by the formatter but are not lost. Elements like the TEI-header, which contain metadata about the text, are entirely hidden but also not lost. This is to enable later reversal of the stripping process. Each version produces a pair of markup and plain text files that are separately merged into a single CorTex and a single CorCode file. It is these files that are edited and read by the HRIT system.
• Formatter takes the properties of the CorCode and combines them with the information from the CSS file into HTML. The CSS is used not only to change the appearance of the text on a web page but also to transform the markup. For example the CSS rule span.italics can be used to change the appearance of italics, but also to convert properties called 'italics' into spans of class 'italics'. In this way we can avoid use of XSLT. But what about the 'annotations' that were originally attributes in the TEI-XML? They are simply ignored (although not lost). If you want to convert an element plus some attribute(s) into a HTML element using formatter, you must first specify a rule to simplify them to a plain property using splitter's recipe file.