结合因子图的多目的地地图布局优化  

Synthesizing multi-destinations map with factor graph

作　　者：罗振珊 张俊松[1,2] 范接鹏 

机构地区：[1]厦门大学智能科学与技术系艺术认知与计算实验室,厦门361005 [2]福建省仿脑智能系统重点实验室,厦门361005

出　　处：《中国图象图形学报》2015年第3期418-426,共9页Journal of Image and Graphics

基　　金：国家自然科学基金项目(60903129);国家重点基础研究发展规划(973)基金项目(2013CB329502)

摘　　要：目的提出一种结合因子图的多目的地地图生成方法。方法首先,由用户选择多个感兴趣的目的地,系统根据相应规则自动地选择与目的地最相关的路线。然后,通过定义一组衡量布局质量的约束规则,采用因子图方法将定义的每条规则编码成因子,并采用Metropolis Hastings算法对由因子图构建得到的目标分布函数进行采样得到符合约束规则的多目的地地图。结果实验结果表明,使用这种方法得到的多目的地地图,可以在同一显示空间中显示多个目的地之间的道路信息,同时又保留了各目的地区域之间的拓扑和空间关系。结论提出的多目的地地图能有效地为用户提供导航,解决了当前在线地图无法在同一视野中为用户提供空间距离较远的区域道路信息的问题。Objective An increasing number of people usually need to work or take a holiday with their families in another city. Therefore, having an accurate map is necessary when they arrive in an unfamiliar city. Some online maps, such as Baidu or Google, can provide sufficient but redundant information. Users only need some information about their destinations, but excessive details on other places give rise to difficulty in reading maps. Meanwhile, users often need to perform many tedious operations, such as zoom in and zoom out, to obtain useful information. Therefore, we present a factor graphbased method to generate multiple destinations maps. This method can provide users with only useful information so that they can obtain help easily. Method Our method consists of three steps. First, users select multiple destinations of interest. The detail of some areas that are far from the user destinations is unnecessary. Second, the proposed system automatically selects the most relevant subset of roads that are related to the destinations according to certain predefined guidelines. These guidelines ensure that the selected road network maintains conciseness and connectivity so that users can arrive at any destination. Finally, the layout is adjusted to present an accurate map. The map should ensure that the details of the information on the destinations are clear while maintaining the original topology of the map. Moreover, we should maximize screen usage to display more information. Thus, we identify a set of design rules to constrain the map layout. We conduct some preprocessing of the road network to implement layout optimization. We segment the road network into several rectangular areas according to the user destinations. Every rectangle contains only one destination. During optimization, we can choose a rectangular area-based perturbation or point-based perturbation. Furthermore, we use factor graph, a type of graphical model, to improve algorithm efficiency by encoding constraints as factors. We obtain the desired ma

关 键 词：多目的地 地图可视化 因子图 MH算法 

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