The Algorithm Design Manual Second Edition

225

Stop and Think: Separate the Text

Problem: “We need a way to separate the lines of text in the optical character-

recognition system that we are building. Although there is some white space be-

tween the lines, problems like noise and the tilt of the page makes it hard to find.

How can we do line segmentation?

Solution: Consider the following graph formulation. Treat each pixel in the im-

age as a vertex in the graph, with an edge between two neighboring pixels. The

weight of this edge should be proportional to how dark the pixels are. A segmen-

tation between two lines is a path in this graph from the left to right side of the

page. We seek a relatively straight path that avoids as much blackness as possible.

This suggests that the shortest path in the pixel graph will likely find a good line

segmentation.

Take-Home Lesson: Designing novel graph algorithms is very hard, so don’t

do it. Instead, try to design graphs that enable you to use classical algorithms

to model your problem.

Chapter Notes

Network flows are an advanced algorithmic technique, and recognizing whether a

particular problem can be solved by network flow requires experience. We point

the reader to books by Cook and Cunningham

[CC97

] and Ahuja, Magnanti, and

Orlin

[AMO93

] for more detailed treatments of the subject.

The augmenting path method for network flows is due to Ford and Fulkerson

[FF62

]. Edmonds and Karp

[EK72

] proved that always selecting a shortest geodesic

augmenting path guarantees that O(n

3

) augmentations suffice for optimization.

The phone code reconstruction system that was the subject of the war story is

described in more technical detail in

[RS96

].