A new algorithm for layout-independent document page segmentation is suggested. Text, image and graphics regions in a document image are treated as three different exture" classes. Soft local decisions on small blocks are made using wavelet packet based feature vectors. Segmentation is performed by propagating and integrating soft local decisions over neighboring blocks, within and across scales.The uncertainties" associated with local decisions are reduced as more contextual evidence is incorporated in the process of decision integration. The majority, taken over weighted combined votes, determines the final decision. The suggested algorithm is based on parallel independent computations which have low complexity. It can also be applied to other signal and image segmentation tasks.