scraperwiki/pdftables — pull request #91 by pwaller (2013-09-22 11:52:54+00:00)
Title: New centerline detection algorithm

Will paste a screenshot into this issue in place of this text.

This introduces the new centerline estimation, with input from @zarino and @drj11.

The main idea is to figure out where the true centerlines of text might be,
given that the input data may be messy, featuring superscripts/subscripts, large
and small text and all sorts.

It seems to work fairly well, effectively ignoring small variations in vertical
position without resorting to arbitrary quantization using some variation of
`round()`, which might result in incorrectly assigning characters to the
wrong baseline.

At the moment this PR just computes candidate text baselines. It doesn't assign
text to those baselines or anything like that.

This information will be useful for determining the text ordering within a cell,
as well as potentially for determining where cells are and where colspans are.

It works by computing the `hat` function (see the green line on the left) at
only the points where it changes (using the `segments_generator`), the so-called
"hat points".
The hat function is at 0 on the edges of a line segment and goes to 1 at the
centre. The sum over all hats can then be
[scanned for peaks](https://github.com/scraperwiki/pdftables/compare/new-linesegments-functions?expand=1#L2R326)
to search for possible text baselines.

The "hat function" (left green thing) is very similar to the existing
"glyph count histogram" (left red thing), except that it naturally does an "erode"
and has useful peaks in it, regardless of overlapping glyphs.

This algorithm is also used to compute the maximum height of any glyph at every
hat-point. I envisage another use of the `segments_generator` to then visit every
glyph whilst simultaneously "seeing" all candidate centerlines to perform
assignment.

The `segments_generator` function became quite a bit more general, it's now
capable of optionally visiting the midpoints of all input segments as well as
the start and end points and additionally it can cope with multiple inputs of
different kinds, and visit them in different ways. For example, it could visit
baseline candidates exactly once (since they're just a point).