Turbo recognition: a statistical approach to layout analysis

Taku A. Tokuyasu and Philip A. Chou


Turbo recognition (TR) is a communication theory approach to the analysis of rectangular layouts, in the spirit

of Document Image Decoding. The TR algorithm, inspired by turbo decoding, is based on a generative model of

image production, in which two grammars are used simultaneously to describe structure in orthogonal (horizontal

and vertical) directions. This enables TR to strictly embody non-local constraints that cannot be taken into

account by local statistical methods. This basis in finite state grammars also allows TR to be quickly retargetable

to new domains. We illustrate some of the capabilities of TR with two examples involving realistic images. While

TR, like turbo decoding, is not guaranteed to recover the statistically optimal solution, we present an experiment

that demonstrates its ability to produce optimal or near-optimal results on a simple yet nontrivial example, the

recovery of a filled rectangle in the midst of noise. Unlike methods such as stochastic context free grammars and

exhaustive search, which are often intractable beyond small images, turbo recognition scales linearly with image

size, suggesting TR as an eƆcient yet near-optimal approach to statistical layout analysis.


Publication typeInproceedings
Published inElectronic Imaging Conf. on Document Recognition and Retrieval
> Publications > Turbo recognition: a statistical approach to layout analysis