Reading order based on maximal matching in graph theory for non-Manhattan layout

Abstract

Detecting reading order for non Manhattan layout which has anomalous shape and complicated space relationship is a key problem in research of document image understanding (DIU) and text typesetting. To resolve it, a new layout model is defined which uses layout objects, space inclusive and ordinal relationship. Based on maximal matching in graph theory, an algorithm for reading order detection is presented. It is proven be effective by a special typesetting system and also helpful to go deep into DIU.