Newspaper article reconstruction using ant colony optimization and   bipartite graph

doi:10.1016/j.asoc.2012.07.012

CORC > 北京大学 > 信息科学技术学院

	Newspaper article reconstruction using ant colony optimization and bipartite graph
	Gao, Liangcai ; Wang, Yongtao ; Tang, Zhi ; Lin, Xiaofan
刊名	applied soft computing
	2013
关键词	Document digitalization Document analysis and recognition Pattern recognition Swarm intelligence Electronic newspaper Article reconstruction Digital library
DOI	10.1016/j.asoc.2012.07.012
英文摘要	The primary information units in a newspaper are the articles. How to segment a newspaper page into individual articles and to recover the reading order of each article, namely newspaper article reconstruction, is known to be challenging due to the complexity of the multi-article page layout. In this paper, we propose a novel article reconstruction approach by solving a series of subtasks: grouping the article bodies, detecting the reading order, associating the title-body pairs and linking article parts scattered in multiple pages. We formulate reading order detection as a traveling salesman problem (TSP), and employ the Max-Min Ant System (MMAS) to solve it. Furthermore, a level-based pheromone mechanism is introduced to improve the efficiency of standard MMAS. Moreover, in sharp contrast to the existing methods, we perform the first two subtasks of article reconstruction in reverse order, that is, we detect the reading order of the text blocks first and then use the content continuity implicitly specified in the reading order to aggregate text blocks of the same article. In this way, we can effectively overcome the limitation of content similarity on article body aggregation. The other two subtasks (associating the title-body pairs, linking article parts scattered in multiple pages), are solved under a unified bipartite graph framework, which models the complex relationships between page objects as one-to-one correspondences, and accomplishes the two subtasks by finding the optimal matching on this graph. During the optimization process, various information sources, including geometric layout, linguistic and semantic content, are deeply mined in MMAS and bipartite graph model to deal with the wide range of complex newspaper layouts. Experimental results on real-world data have demonstrated the effectiveness of our proposed method. It has also been adopted in several large-scale newspaper digitalization projects. (C) 2012 Elsevier B. V. All rights reserved.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000319205600004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Artificial Intelligence; Computer Science, Interdisciplinary Applications; SCI(E); EI; 3; ARTICLE; 6; 3033-3046; 13
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/161785]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Gao, Liangcai,Wang, Yongtao,Tang, Zhi,et al. Newspaper article reconstruction using ant colony optimization and bipartite graph[J]. applied soft computing,2013.
APA	Gao, Liangcai,Wang, Yongtao,Tang, Zhi,&Lin, Xiaofan.(2013).Newspaper article reconstruction using ant colony optimization and bipartite graph.applied soft computing.
MLA	Gao, Liangcai,et al."Newspaper article reconstruction using ant colony optimization and bipartite graph".applied soft computing (2013).