基于图论最大匹配的非Manhattan版面阅读顺序  

Reading Order Based on Maximal Matching in Graph Theory for Non-manhattan Layout

作　　者：贾娟[1] 陈堃銶[1] 周东浩 

机构地区：[1]北京大学计算机科学技术研究所文字信息处理技术国家重点实验室,北京100871 [2]IBM中国有限公司,北京100027

出　　处：《计算机工程》2006年第2期32-33,47,共3页Computer Engineering

摘　　要：非Manhattan版面中,区域形状不规则及空间关系复杂使得确定合乎视觉脉络的无歧义的文字阅读顺序成为排版及版面理解过程中的一个难点。针对此问题,建立了新的版面布局模型,提出了基于图论最大匹配理论的阅读顺序确定算法。已成功运用于专业中日文排版系统,取得了满意的效果,并对更深入研究文档图像理解具有十分重要的理论和实践意义。Detecting residing 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 thcoty, an algorithm for reading order detection is presented. It is proven be effective by a special typcsctting system and also helpful to go deep into DIU.

关 键 词：最大匹配 非Manhattan版面 阅读顺序 空间关系 

分 类 号：TP391.12[自动化与计算机技术—计算机应用技术]