A Trainable, Single-Pass Algorithm for Column Segmentation

Column segmentation logically precedes OCR in the document analysis process. The trainable algorithm described here, XYCUT, relies on horizontal and vertical binary profiles to produce an XY- tree representing the column structure of a page of a technical document in a single pass through the bit image. Training against ground truth adjusts a single, resolution independent, parameter using only local information and guided by an edit distance function. The algorithm correctly segments the page image for a (fairly) wide range of parameter values, although small, local and repairable errors may be made, an effect measured by a repair cost function. Keywords: Column segmentation, decolumnization, XY tree, profiles 1 Introduction Column segmentation is an essential part of any document analysis process. The algorithm described here, XYCUT, attempts column segmentation of page images guided by a single parameter based on a nearly universal feature of page layout design, that column gaps a..