A parallel algorithm for “document segmentation”

We present a parallel algorithm for physical segmentation of technical documents. The proposed method follows a “data parallel” approach, based on a divide and conquer implementation. A document page is statically partitioned into n equal-sized rectangular blocks, where n is the number of processors. Each processor independently finds a segmentation of its assigned block, according to the same rules: row/column or-ing and profile xor-ing. Each segmentation is stored in form of xy-tree. The computed trees are combined, in pairs and in parallel, without re-examining the original image. In the paper we prove that the independently computed xy-trees can be efficiently combined, without using the original image to form the global tree, obtained by a sequential application of the algorithm to the image. The method has been implemented on a LAN of workstations communicating through the PVM3 system