-
近年来, WEB2.0、LBS(location-based service)等的快速发展，对地图的连续尺度表达提出了新的需求，人们希望能够实现空间信息可视化表达的多视角和多层次。为满足人们的要求，地图连续综合技术被提出[1]。Morphing又称图形渐变技术，其基本思想是采用某种内插方法使得初始图形光滑连续地渐变到目标图形。这和地图连续综合技术的思想相契合。在GIS领域，利用Morphing实现地图连续尺度变换，其基本思想分为匹配和插值两步[2]。因Morphing变换的精度主要受匹配精度的影响[3]，因此，很多学者在优化匹配方面做了一系列工作，主要有文献[4]通过将小比例尺图形进行点加密，加密到与大比例尺点数一致，然后依据点号进行一一对应，以此建立匹配关系；文献[5]将弧度较大处的顶点视作特征点，然后基于位移的关系建立匹配关系；文献[6]通过约束Delaunay三角网提取小比例尺地图上线状要素的特征点，然后采用模拟退火技术在特征点与大比例尺线状要素顶点之间建立全局最优化匹配；文献[7-9]把弯曲结构作为切入点，提出基于弯曲结构的匹配方法；文献[10]将传统矢量坐标转化为转向角函数，基于转向角函数实现边特征匹配。这些方法或需要寻找特征点建立对应匹配；或不需要特征点，只进行简单内插后匹配，没有顾及要素的上下文信息。对于地图要素而言，小比例尺要素通常是由大比例尺经过综合变换得来的，如弯曲的化简、删除、夸大和典型化的操作[1]。因此，可以从小比例尺上的点入手，寻找各点在大比例尺上的最佳匹配来完成对应点的匹配。大小比例尺具有类似的上下文信息。形状上下文是一种得到广泛运用的目标形状描述子[11]，它通过点集之间的关系，即其上下文信息来描述形状，该方法不需要这些点具有曲率最大、弧度较大等常规方法中认为的特殊点所具备的特征，因此，适应性和鲁棒性较强。
本文提出一种基于形状上下文的Morphing方法，其基本思想是将点的形状上下文作为图形的形状描述，对于大小比例尺下同名实体所对应的点集来说，对应点的匹配可以通过计算每个点的形状上下文及各点之间的匹配度来寻找最佳匹配。匹配完成之后通过常用的线性内插方法就可以得到中间比例尺的地图表达。
-
一个形状表示为N个轮廓点的集合，任意点pi的形状上下文就是pi与点集中其余各点相对于该点的角度θ以及对数距离lgρ的直方图分布，利用直方图来描述图形特征。因此，轮廓上的采样点越多，N越大，对形状的描述就越详细。对任意点pi以其为原点建立对数极坐标系，在对数极坐标系下分别将lgρ和θ进行S等分和T等分(图 1)，因此，整个空间被分成了S×T个区域。通常选择S=5，T=12，即划分出60个子区域[11]。空间区域分割完成之后，记录除pi点外的N-1个点在这60个区域的分布数目，由该数目来作为点的形状上下文。计算公式为:
图 1 形状上下文的计算[11]
Figure 1. Computation of Shape Context
$$ {h_i}\left( k \right) = \# \left\{ {p \ne {p_i}:p \in {\rm{bin}}\left( k \right)} \right\} $$ (1) 其中，k=0, 1, 2, 3, …, 59，#操作表示取p为落入第K个区域(bin)且不同于pi点的轮廓上其余点的数目。以图 1为例，假设从X轴正方向开始由内而外以逆时针起算，则落在箭头所指区域，即第48个bin内有4个点，有hi(48)=4。其他的bin用同样的方法来统计，这样就得到了一个有60个分量的形状直方图。计算点集中每一个点的形状直方图，即可完成图形的形状描述。
考虑到形状上下文描述子是基于直方图分布的特征，因此采用χ2分布统计检验作为形状上下文的相似性匹配代价，定义两个点的匹配代价Cij为：
$$ {C_{ij}} = C\left( {{p_i},{q_j}} \right) = \frac{1}{2}\sum\limits_{k = 1}^K {\frac{{\left[ {{h_i}\left( k \right) - {h_j}\left( h \right)} \right]2}}{{{h_i}\left( k \right) + {h_j}\left( k \right)}}} $$ (2) 式中，hi(k)、hj(k)分别代表第一个图形上点pi和第二个图形上点qj的形状直方图中第K个bin中的值。Cij越大，说明两个点的匹配代价越大，两点之间相似性越小，互为对应点的可能性就越小。得到两个形状所有点之间的匹配代价之后，点模式匹配的目标是寻找一个匹配关系π，使得式(3) 取得最小值。
$$ \mathop {\min }\limits_{\rm{\pi }} H\left( \pi \right) = \sum\limits_i {C\left( {{p_i},{q_{\pi \left( i \right)}}} \right)} $$ (3) 式中，π(i)为与i的对应点号。上面的点集匹配问题就变成了典型的二分图匹配问题，把匹配代价最小的点作为最相似的对应点，而二分图的最大匹配问题可以利用匈牙利算法来解决。
本文从小比例尺出发，利用匈牙利算法建立完美匹配，找到对应大比例尺上的对应点，既可以充分利用小比例尺上的点，又能够很好地顾及到要素的上下文信息。
-
对于一同名实体，它在较大比例尺RA下的表达为A，在较小比例尺RB下的表达为B，任一中间比例尺Rc下的表达为C。通过形状上下文完成点集匹配后，假设A中的一个点的子集Asub(i)对应B中一个点的子集Bsub(j)。则：
$$ A = \sum\limits_i {{A_{{\rm{sub}}\left( i \right)}}} $$ (4) $$ B = \sum\limits_j {{B_{{\rm{sub}}\left( j \right)}}} $$ (5) 令f1和f2分别表示定义域[0, 1]到Asub(i)和Bsub(j)的连续函数, f表示形状内插之后中间状态的连续函数，对应的子集为Csub(k)：
$$ f = \left( {1 - g} \right) \times {f_1} + g \times {f_2},0 \le g \le 1 $$ (6) 式中，g为介于大、小比例尺之间的归一化中间尺度。由此可知，当g=0时, f=f1, 即Csub(k)=Asub(i)；当g=1时，f=f2, 即Csub(k)=Bsub(j)；当0 < g < 1时，f为介于f1和f2之间的中间表达，且g的大小控制内插结果的偏向度。归一化参数g为：
$$ g = \frac{{\left( {\frac{1}{{{R_C}}} - \frac{1}{{{R_A}}}} \right)}}{{\left( {\frac{1}{{{R_B}}} - \frac{1}{{{R_A}}}} \right)}} $$ (7) 通过对每一组对应点集进行相同的处理，最后可以得到Morphing后的中间状态：
$$ C = \sum\limits_i {{C_{{\rm{sub}}\left( k \right)}}} $$ (8) -
为了定量化Morphing的精度，引入文献[5]的评价方法，采用加权的位矢距离来衡量。曲线相似性指标通常有距离、长度、方向、形状等。假设对应的两个点集分别为α(μ)、β(μ)，对应的曲线分别为A′、B′。如果单纯用长度差异clen来衡量，则有：
$$ {c_{{\rm{len}}}}\left( {A',B'} \right) = \left| {\left| {A'} \right| - \left| {B'} \right|} \right| $$ (9) 但是在多尺度环境下，单一指标可能会发生很大的变化，因此，单一指标缺乏鲁棒性。可以通过引入位移矢量来描述曲线方向的变化。对于对应点集来说，其位移矢量就为β(μ)-α(μ)，这些位移矢量又构成一条曲线，定义为γ(μ)，则γ(μ)=β(μ)-α(μ)，μ∈[0, 1]，如图 2(b)所示。
图 2 位矢距离γ(μ)的构造
Figure 2. Construction of the Measuring Distance Parameter γ(μ)
可以用|γ|来表示A′渐变到B′的在方向上的变化大小，很显然，|γ|越大，方向上的偏移就越大。因此可以结合长度和方向这两个指标，用加权位矢δ(A′, B′)来衡量图形变化中的位移大小, 定义如下：
$$ \delta \left( {A',B'} \right) = \frac{{\left| \gamma \right|\left( {\left| {A'} \right| + \left| {B'} \right|} \right)}}{{\left( {\left| {A'} \right| + \left| {B'} \right|} \right)}} $$ (10) 那么对于整体就有：
$$ \delta \left( {A,B} \right) = \sum {\delta \left( {A',B'} \right)} $$ (11) δ(A, B)反映了对应点之间位移矢量的加权变化情况，其值越小说明匹配效果越好，Morphing精度越高。
-
本文采用模拟数据和真实等高线数据进行实验来说明本文方法的可行性和有效性。
模拟实验数据如图 3所示，图 3(a)为一线状要素在大比例尺下的表达，共有205个顶点，即A(p0, p1, p2, …, p203, p204), 表达较为详细。图 3(b)中为同名实体在小比例尺下的表达，共有28个顶点，即B(q0, q1, …, p26, p27)，表达较为概略。实验中，小比例尺图形B上的所有点都将参与匹配。对于该数据，分别采用线性插值算法和本文方法进行点模式的匹配实验。匹配的结果如图 4所示。图 4(a)中Ⅰ区和Ⅱ区出现了明显的误匹配情况，其加权位矢距离δ(A, B)为130.552 8，基于线性的插值算法从纯几何的角度进行点的一一匹配，忽视了点的上下文信息。采用本方法，δ(A, B)为70.747 1，有了很大的改善，在进行匹配的过程中，充分考虑了点的形状上下文信息，提高了匹配的精度，匹配结果见图 4(b)。
图 3 数据在大小比例尺下的表达
Figure 3. Representations of Polylinesin Two Different Scales
图 4 线性方法和本文方法的点匹配结果
Figure 4. Matching Results of Two Different Method
-
基于上面实验的匹配结果，进行形状内插。B被其端点分成了27段，分别为q0q1、q1q2、…、q26q27。A被其端点分成了204段，分别为p0p1、p1p2、p2p3、…、p203p204。点匹配关系可用表 1来表示。
表 1 匹配点对
Table 1. Corresponding Points
qj pi q0 p0 q1 p10 q2 p13 q3 p16 q4 p20 q5 p25 q6 p45 q7 p47 q8 p53 q9 p66 q10 p74 q11 p92 q12 p100 q13 p109 q14 p121 q15 p123 q16 p125 q17 p128 q18 p129 q19 p131 q20 p136 q21 p143 q22 p153 qj23 p179 qj24 p191 qj25 p196 qj26 p199 qj27 p204 线状要素上点将线划分成了线段，因此，由匹配点关系得到匹配线段之间的关系。例如，线段q0q1对应线段p0p10，q1q2对应p10p13。因此, 在基于形状上下文匹配的基础上把对应点之间的连线作为插值路径进行线性插值。
图 5和图 6分别为本文方法和线性插值方法的Morphing结果。其中g=0和g=1分别为线状要素在大比例尺RA下的表达A，在小比例尺RB下的表达B。实验中，分别设置g=0.2、0.4、0.6、0.8等4个不同的尺度进行形状内插。依据式(7)，g与中间比例尺RC的关系为RC=(1-g)×RA+g×RB。可以看出，图 5中的结果更加符合空间数据的渐变特征，弯曲过渡光滑自然。图 6中，由于大小比例尺初始数据采样点密度差异较大，单纯的线性内插并没有考虑要素的上下文信息，使得匹配过程中出现较大偏差，因此渐变过程中出现了不同程度的变形。这主要有以下两个问题：① 出现了不符合原始形态的变化，图 6(d)中方框标注的地方产生了形态变异；② 各部分渐变的尺度不一致，出现了局部的突变，见图 6(c)中的圆框部分。
图 5 基于本文方法的模拟数据Morphing效果
Figure 5. Morphing Effects of Simulation Data Based on the Method in this Paper
图 6 基于线性插值方法的模拟数据Morphing效果
Figure 6. Morphing Effects of Simulation Data Based on the Linear Interpolation Method
图 7和图 8为某区域真实等高线数据采用本方法和线性插值方法的Morphing效果，等高距为25 m，从左到右g值分别为0、0.4、0.6和1，其中，g=0对应1:1万的初始表达，g=1对应1:5万的初始表达，g=0.4、0.6分别对应1:2.6万、1:3.4万的表达。由结果很容易发现图 7的渐变效果更好，曲线弯曲形态由复杂到简单，过渡比较平滑，中间状态不存在自相交；图 8则存在一些明显的形态变异，图中圆框位置发生变形和严重拓扑错误，不符合制图综合的基本要求。
图 7 基于本文方法的真实等高线数据Morphing效果
Figure 7. Morphing Effects of Real Contour Data Based on the Method in this Paper
图 8 基于线性插值方法的真实等高线数据Morphing效果
Figure 8. Morphing Effects of Real Contour Data Based on the Linear Interpolation Method
-
本文提出了一种基于形状上下文匹配的线状要素Morphing变换方法，该方法把点集的形状上下文作为形状描述子，在点模式匹配过程中顾及了要素的上下文信息，同时该方法不需要像常规方法那样寻找特征点，具有很强的鲁棒性，提高了Morphing变换的精度和适用范围。
-
摘要: 提出了一种基于上下文特征的形状匹配方法，并将其用于线状要素的Morphing变换。首先通过计算每个点的形状上下文，建立形状直方图，然后通过直方图匹配找到同名实体在大小比例尺下轮廓点的最佳匹配关系。根据点的匹配关系，得到对应线段。最后通过分段线性内插实现线状要素的连续尺度变换。实验结果表明，基于形状上下文的轮廓点集匹配方法不需要标志点或者关键点，适应性较强，可以有效地实现形状匹配，极大地提高Morphing变换的精度。
-
关键词:
- 形状上下文 /
- Morphing方法 /
- 形状匹配 /
- 线状要素
Abstract: We introduce a shape matching method based on the shape context, and apply it to the morphing of linear features. For the two representations of the same linear feature in two different scales, to get the correspondences of the point, the shape context of every point on the shape is calculated at the very beginning. Then we compute the similarity between different points using shape histogram. The two linear features are divided into two groups of sub-segments by the matching result. Finally, using the linear interpolation method to Morphing every pair of the corresponding sub-segments. The experimental results show that during the process of matching no special landmarks or key-points of the linear features are needed. It has strong adaptability to the shape matching and greatly improve the accuracy of morphing transformation.-
Key words:
- shape context /
- morphing /
- shape matching /
- linear feature
-
图 5 基于本文方法的模拟数据Morphing效果
Figure 5. Morphing Effects of Simulation Data Based on the Method in this Paper
图 6 基于线性插值方法的模拟数据Morphing效果
Figure 6. Morphing Effects of Simulation Data Based on the Linear Interpolation Method
图 7 基于本文方法的真实等高线数据Morphing效果
Figure 7. Morphing Effects of Real Contour Data Based on the Method in this Paper
图 8 基于线性插值方法的真实等高线数据Morphing效果
Figure 8. Morphing Effects of Real Contour Data Based on the Linear Interpolation Method
表 1 匹配点对
Table 1. Corresponding Points
qj pi q0 p0 q1 p10 q2 p13 q3 p16 q4 p20 q5 p25 q6 p45 q7 p47 q8 p53 q9 p66 q10 p74 q11 p92 q12 p100 q13 p109 q14 p121 q15 p123 q16 p125 q17 p128 q18 p129 q19 p131 q20 p136 q21 p143 q22 p153 qj23 p179 qj24 p191 qj25 p196 qj26 p199 qj27 p204 
下载: 导出CSV
-
[1] Sester M, Brenner C.Continuous Generalization for Visualization on Small Mobile Devices[M]. Berlin:Springer, 2005:355-368 [2] 李华, 朱光喜, 朱耀庭, 等.物体渐变技术现状与发展[J].中国图像图形学报(A辑), 2002, 7(8):745-751 http://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB200208000.htm Li Hua, Zhu Guangxi, Zhu Yaoting, et al. A Survey of Object Metamorphosis[J].Journal of Image and Graphics, 2002, 7(8):745-751 http://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB200208000.htm [3] van Kreveld M.Smooth Generalization for Continuous Cooming[C]. The International Cartographic Conference, Beijing, 2008 http://www.researchgate.net/publication/46615515_Smooth_Generalization_for_Continuous_Zooming [4] Cecconi A. Integration of Cartographic Generalization and Multi-scale Databases for Enhanced Web Mapping[D].Zurich:University of Zurich, 2003 https://www.researchgate.net/publication/266339341_Integration_of_Cartographic_Generalization_and_Multi-Scale_Databases_for_Enhanced_Web_Mapping [5] Nllenburg M, Merrick D, Wolff A, et al. Morphing Polylines:A Step Towards Continuous Generalization[J]. Computers, Environment and Urban Systems, 2008, 32(4):248-260 doi: 10.1016/j.compenvurbsys.2008.06.004 [6] 李精忠, 吴晨琛, 杨泽龙, 等.一种利用模拟退火思想的线状要素Morphing方法[J].武汉大学学报·信息科学版, 2014, 39(12):1446-1451 http://ch.whu.edu.cn/CN/abstract/abstract3139.shtml Li Jingzhong, Wu Chenchen, Yang Zelong, et al. A Morphing Method for Linear Features Based on Simulated Annealing[J]. Geomatics and Information Science of Wuhan University, 2014, 39(12):1446-1451 http://ch.whu.edu.cn/CN/abstract/abstract3139.shtml [7] 彭东亮, 邓敏, 刘慧敏.更充分利用独立弯曲结构的线状要素Morphing变换方法[J].测绘学报, 2014, 43(6):637-652 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201406014.htm Peng Dongliang, Deng Min, Liu Huimin. Morphing Transformation of Linear Features by Using Independent Bend Structures More Sufficiently[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(6):637-652 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201406014.htm [8] 彭东亮, 邓敏, 徐枫.顾及BLG树结构特征的线状要素Morphing变换方法[J].武汉大学学报·信息科学版, 2012, 37(9):1120-1125 http://ch.whu.edu.cn/CN/abstract/abstract330.shtml Peng Dongliang, Deng Min, Xu Feng. Morphing Linear Features Considering Their BLG-tree Structures[J]. Geomatics and Information Science of Wuhan University, 2012, 37(9):1120-1125 http://ch.whu.edu.cn/CN/abstract/abstract330.shtml [9] 邓敏, 彭东亮, 徐震, 等.一种基于弯曲结构的线状要素Morphing方法[J].中南大学学报(自然科学版), 2012, 43(7):2674-2682 http://www.cnki.com.cn/Article/CJFDTOTAL-ZNGD201207032.htm Deng Min, Peng Dongliang, Xu Zhen, et al. A Morphing Method Based on Bend Structures for Linear Features[J].Journal of Central South University(Science and Technology), 2012, 43(7):2674-2682 http://www.cnki.com.cn/Article/CJFDTOTAL-ZNGD201207032.htm [10] 谢天, 李精忠.面状居民地Morphing变换的转向角函数法[J].测绘学报, 2015, 44(7):797-804 doi: 10.11947/j.AGCS.2015.20140333 Xie Tian, Li Jingzhong. Steering Angle Function Algorithm of Morphing of Residential Area[J].Acta Geodaetica et Cartographica Sinica, 2015, 44(7):797-804 doi: 10.11947/j.AGCS.2015.20140333 [11] Belongie S, Malik J, Puzicha J. Shape Matching and Object Recognition Using Shape Contexts[J].Pattern Analysis and Machine Intelligence, 2002, 24(4):509-522 doi: 10.1109/34.993558 -
点击查看大图
计量
- 文章访问数: 1289
- HTML全文浏览量: 85
- PDF下载量: 312
- 被引次数: 0
