留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用复合迭代策略进行断裂等高线重建

王峰 刘平芝 杨云

王峰, 刘平芝, 杨云. 利用复合迭代策略进行断裂等高线重建[J]. 武汉大学学报 ● 信息科学版, 2017, 42(5): 683-690. doi: 10.13203/j.whugis20150054
引用本文: 王峰, 刘平芝, 杨云. 利用复合迭代策略进行断裂等高线重建[J]. 武汉大学学报 ● 信息科学版, 2017, 42(5): 683-690. doi: 10.13203/j.whugis20150054
WANG Feng, LIU Pingzhi, YANG Yun. Broken Contour Line' Reconstruction Based on Compound Iterative Strategy[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 683-690. doi: 10.13203/j.whugis20150054
Citation: WANG Feng, LIU Pingzhi, YANG Yun. Broken Contour Line' Reconstruction Based on Compound Iterative Strategy[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 683-690. doi: 10.13203/j.whugis20150054

利用复合迭代策略进行断裂等高线重建

doi: 10.13203/j.whugis20150054
基金项目: 

国家自然科学基金 41271447

详细信息
    作者简介:

    王峰, 博士生, 工程师, 主要研究方向为地图学与地理信息系统、图像处理。bjzxgsb@163.com

  • 中图分类号: P208;P283.1

Broken Contour Line' Reconstruction Based on Compound Iterative Strategy

Funds: 

The National Natural Science Foundation of China 41271447

More Information
    Author Bio:

    WANG Feng, PhD candidate, specializes in digital cartography and GIS, image processing. E-mail:bjzxgsb@163.com

图(6) / 表(1)
计量
  • 文章访问数:  843
  • HTML全文浏览量:  82
  • PDF下载量:  213
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-10-09
  • 刊出日期:  2017-05-05

利用复合迭代策略进行断裂等高线重建

doi: 10.13203/j.whugis20150054
    基金项目:

    国家自然科学基金 41271447

    作者简介:

    王峰, 博士生, 工程师, 主要研究方向为地图学与地理信息系统、图像处理。bjzxgsb@163.com

  • 中图分类号: P208;P283.1

摘要: 多种原因导致彩色栅格地形图分割后得到的等高线图像中存在大量断线,断裂等高线重建是目前的一个研究热点。分析了近5年来4种最新方法的优缺点,在模拟和分解人工智能识别判断过程的基础上,提出了一种利用复合迭代策略的断裂等高线重建方法。该方法首先总结归纳了断裂间隙区间和断裂形态的划分规律,然后制定了多种算法、运行参数、图像数据源相结合的增量式循环迭代断点匹配连接策略,对断点方向角和方向差异算法进一步优化改进,建立了断点方向差异约束规则,最终实现了各种复杂情况下的断点正确匹配连接。实验结果表明,该方法的处理效果和定量指标均优于几种最新方法,具有更好的稳定性和适用性。

English Abstract

王峰, 刘平芝, 杨云. 利用复合迭代策略进行断裂等高线重建[J]. 武汉大学学报 ● 信息科学版, 2017, 42(5): 683-690. doi: 10.13203/j.whugis20150054
引用本文: 王峰, 刘平芝, 杨云. 利用复合迭代策略进行断裂等高线重建[J]. 武汉大学学报 ● 信息科学版, 2017, 42(5): 683-690. doi: 10.13203/j.whugis20150054
WANG Feng, LIU Pingzhi, YANG Yun. Broken Contour Line' Reconstruction Based on Compound Iterative Strategy[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 683-690. doi: 10.13203/j.whugis20150054
Citation: WANG Feng, LIU Pingzhi, YANG Yun. Broken Contour Line' Reconstruction Based on Compound Iterative Strategy[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5): 683-690. doi: 10.13203/j.whugis20150054
  • 等高线数据是地理信息应用中地形分析和数字高程模型 (digital elevation model, DEM) 生成的重要数据源。从彩色栅格地形图中分割、识别、提取等高线图像,进而对等高线图像进行自动矢量化获取矢量等高线数据是目前的一种常见做法。由于受原图质量、扫描仪性能等因素影响,以及彩色地形图本身地理要素复杂,各种地理要素或文字注记与等高线交叉或者重叠[1-3],导致得到的等高线图像中存在大量断裂,不能满足自动数字化的要求。若能快速、准确地实现断裂等高线的连接重建,可大大提高等高线数字化的效率。目前,各种研究断裂等高线重建的方法仍未能较好地解决这一问题,主要是断线重建中断点匹配准确度不高,算法的适应性和实用性不好,对质量较差或者断裂复杂度高的图像无法消除错误和遗漏连接。

    现有针对断裂等高线重建的解决方法主要从数学形态学、几何特征、梯度矢量场、三角网构建[4]等角度开展研究,文献[5-7]提出了各自的解决方法,不同之处主要在于断裂等高线识别提取和匹配重建的策略不同。目前最常用的4种断裂等高线重建方法的优点与不足如下。

    1) 断点延伸相交判断断点匹配方法。文献[5]在判断断点间欧氏距离和方向角的基础上提出了一种断点延伸相交判断匹配方法 (简称为Gul方法)。该方法思路简洁,容易实现,可完成一定数量断点的匹配连接,但对断裂等高线几何图形和空间特性考虑不全,无法连接近似平行的断点,断裂间距过大时错误率较高。

    2) 基于梯度方向场的匹配方法。文献[6]继承了文献[7-11]的研究成果,利用细化后未断裂的等高线信息推断出完整等高线图的梯度方向场,再利用全局梯度流信息找到匹配断点对进行连接 (简称为Ghircoias方法)。该方法可减少等高线断点间的错连率,但算法复杂度高,处理速度慢,不易于实现。

    3) 基于断点分类和方向差异的等高线分级方法。文献[12]提出了基于断点分类和方向差异的等高线分级补断方法和策略。该方法较好地克服了其他常规最小点对法对近似平行等高线断点错连和断裂距离过大无法连接的问题,在时间效率和准确率方面具有一定优势,但对抛物线等形状复杂的断裂等高线完成重建的能力不足。

    4) 基于优化最小点对法的等高线重建方法。文献[13-16]吸收了文献[17-19]中利用欧氏距离最短和方向差异最小条件准则实现断点匹配重建的优点,基于等高线几何形状和空间特性,提出了优化改进后的断裂等高线重建方法[14](简称为Samet方法)。该方法提升了断点匹配的运行效率和正确率,但在处理大幅面和质量较差的等高线图像时性能下降很快,错误率和未完成数量明显增加。

    上述4种方法在运行过程中对运行参数或图像数据源进行了循环迭代,尽管一定程度上减少了断点的错连率,但仍存在突出问题,主要表现在近似平行的密集断裂等高线易出错,形状陡峭、折角过大的等高线无法匹配,断裂处尺寸大的断裂等高线易出错,算法复杂度高、处理速度慢等。

    因此,现有方法仍不能彻底解决复杂形状断裂等高线重建问题。完成各种复杂情况下断点的正确匹配重建,提升方法运行效率,增强其实用性和可靠性是当前研究的重点。

    本文分析了几种主要的断裂等高线重建方法的优点与不足,通过模拟人工智能识别判断断裂等高线匹配连接这一复杂过程,提出了一种基于复合迭代策略的断裂等高线重建方法。

    • 图 1所示,彩色栅格地形图经过分色、滤波去除孔洞、交叉、细化、剪枝等处理后得到的等高线图像中断裂等高线形状复杂多样,既有形态平缓、近似平行的断裂,也有形态陡峭的断裂 (大多位于山脊和山谷区域,如图 1中① 标识),既有密集,断裂也有稀疏断裂 (图 1中② 标识)。同时,断裂间隙也大小不一 (如图 1中③ 标识)。对所有断裂等高线准确无误地完成匹配连接是一个涉及人工智能识别判断的复杂过程,而在计算机人工智能尚未实现的情况下,模拟和分解人工智能识别过程,设计建立一种多阶段、多层级、多模式下渐进式复合迭代处理过程是一种新的解决思路。

      图  1  断裂等高线呈现的多种形态特征

      Figure 1.  Typical Broken Contour Lines with Different Shapes

      在借鉴前述几种方法优点的基础上,通过深入剖析人工智能识别过程和策略,本文提出了一种基于复合迭代策略的断裂等高线重建方法,设计了一种方法库、运行参数和图像数据源三要素复合可循环迭代的策略和机制,从而实现了对断裂等高线重建复杂过程的分解和简化。此外,针对断点方向差异判断在断点匹配中的重要性,本文进一步优化改进了断点方向角和方向差异约束关键算法,建立了断点方向差异约束准则。

    • 断点间空间距离和方向差异是影响断点匹配的关键因素,断点间空间距离越邻近、过渡越平缓,两者匹配连接的可能性越大[19]。因此,本文方法的基本思路是通过模拟分解人工智能识别断点匹配连接这一复杂过程,在断点匹配重建中对所有断点根据断裂间隙和几何形状划分类别和层级,按照先平缓、后陡峭,先断裂间隙小、后断裂间隙大,先稀疏、后密集的步骤和思路调用优化改进的多个重建算法对断裂等高线进行有针对性的渐进迭代处理。

      图 2所示,本文方法基本原理是基于断点间空间距离和方向差异将复杂的断点匹配连接过程拆分为多个阶段、多个层级,并调用多方法支持下的迭代处理过程和模式:(1) 建立统一的断裂间隙区间划分,对所有断点根据断裂尺寸进行分类;(2) 对各区间内复杂多样的断裂形状,根据断点方向、断点间方向差异和平缓程度进行进一步细分类;(3) 按照断点间断裂间隙由小到大、几何形态由平缓到陡峭的顺序,对断点分批次、分层级实施匹配连接;(4) 针对指定断裂区间内不同形态特征的断点,分别调用针对性强的文献[12]方法、Samet方法、Gul方法等算法执行匹配连接;(5) 利用断裂间隙小的区间内完成的重建结果作为迭代数据源替换原始数据,开始相邻大的断裂尺寸区间内的断点重建处理;(6) 不断重复这一迭代循环过程,直至所有断点完成匹配连接为止。

      图  2  基于复合迭代策略的重建方法运行原理

      Figure 2.  Flowchart of the Proposed Method Based on Compound Iterative Strategy

      利用复合迭代策略的重建方法构建了一种将图像数据源、方法 (算法) 与运行参数 (变量) 三要素相结合的动态循环迭代处理过程和机制,可弥补单一重建方法的不足,避免单一重建过程出现的遗漏和错误。

    • 因为等高线断裂形状的多样性和复杂性,以及现有计算断点方向角和断点间方向差异算法存在的局限性和不确定性,本文首先对断点方向角和方向差异计算方法优化改进,建立了断点方向差异约束准则。

    • 图 3(a)所示,有向线段AB的有向角计算公式为:

      $$ {{\alpha }_{AB}}=\text{arctan2}\left( \frac{{{y}_{B}}-{{y}_{A}}}{{{x}_{B}}-{{x}_{A}}} \right) $$ (1)

      式中,αABX轴沿正向绕点A旋转到与有向线段AB重合所需旋转的角度,范围为[-π, π],逆时针旋转为正,顺时针旋转为负; (xA, yA)、(xB, yB) 分别为有向线段AB的端点坐标。文献[5, 14, 16, 18]在计算断点方向角时通常沿指定断点回溯10个像素,利用式 (1) 计算指定断点和回溯终点连线有向角作为断点方向角。等高线图像经过细化、剪枝等预处理后,单像素宽度的断裂线在断点附近会呈现直角、竖直、水平、弯曲等几何形态,若仅以单次回溯固定像素数来计算断点方向角,结果会存在不确定性。为提高断点方向角计算的稳定性,本文提出了多重递增回溯加权算术平均求断点方向角算法,通过设置多重递增回溯终点计算获取多个断点方向角,对多个方向角利用回溯距离加权算术求平均值,作为最终的断点方向角结果,以提升计算结果的准确度和稳定性,计算公式为:

      $$ \left\{ \begin{align} & {{\alpha }_{i}}=\text{arctan2}\left( \frac{{{y}_{i}}-{{y}_{0}}}{{{x}_{i}}-{{x}_{0}}} \right) \\ & {{f}_{i}}=\frac{{{l}_{i}}}{\sum\limits_{i=1}^{n}{{{l}_{i}}}} \\ & \bar{\alpha }=\frac{\sum\limits_{i=1}^{n}{{{\alpha }_{i}}}\times {{f}_{i}}}{\sum\limits_{i=1}^{n}{{{f}_{i}}}} \\ \end{align} \right. $$ (2)

      式中,(x0, y0) 表示起始断点; (xi, yi) 表示第i次回溯终点; fi表示起点至终点距离权; αi表示第i次回溯方向角; α为方向角加权算术平均值。由以上分析可知,该算法兼顾了断点所在断线的局部方向特征和整体走向趋势,避免了单次回溯算法结果的不确定性,有效改善了文献[12]方法、Samet方法、Gul方法计算方向角时的不足。

    • 根据等高线封闭连续和不相交的特性可知,在断裂程度不大的情况下,断裂处等高线走向基本保持一致,断点间连线方向与两端断点方向非常接近,即断点衔接处和断点间构成的方向差异数值非常小。如图 3(b)所示,断裂等高线L上的两断点为AB,断点A方向角为αA、有向线段AB有向角为βAB,断点B方向角反向角为αB、有向线段BA有向角为βBA,则σAβBA构成的偏移量ΔσA=∣αA-βBA ∣反映了断裂等高线在断点A处与有向线段BA衔接时的平缓程度和方向差异,σBβBA构成的偏移量ΔσB=∣αB-βAB ∣反映了断点B与线段AB衔接时的平缓程度和方向差异,断点AB构成的方向角差值ΔφAB=∣αA-αB ∣反映两了断点间的方向差异。

      图  3  断点方向角与断点方向角差异

      Figure 3.  End Point's Directionl Angle and End Points' Orientation Difference

      由以上分析可知,若ΔσA和ΔσB表示的断点与断点连线衔接处方向差异越小,并且ΔφAB表示的断点间方向差异越小,则两断点走向越一致,越符合等高线断裂处走向一致、平滑过渡的要求,两点匹配可能性越大。因此,断点间方向差异的有效约束应同时注意断点处和断点间的方向差异,使其都处在合理的数值范围内。本文建立了断点方向差异约束准则,其运算表达式为:

      $$ \left\{ \begin{align} & \max \left\{ \Delta {{\sigma }_{A}},\Delta {{\sigma }_{B}} \right\} < \varphi \\ & \Delta {{\varphi }_{AB}} < \varphi \\ \end{align} \right. $$ (3)

      式中,φ为断点方向差异最大阈值。

      该约束准则同时兼顾了断点与断点、断点与断点连线走向的一致性,通过最大阈值的灵活取值可直观反映出等管线断裂处的几何形状、走向趋势和过渡时的平缓程度,有效克服了其他方法在处理近似平行密集断裂等高线时易出现的错误连接。

    • 本文采用C#语言对本文方法、文献[12]方法、Samet方法和Gul方法进行了编程实现,选取了多幅基于1:50 000扫描彩色地形图提取得到的单像素等高线图像作为实验样本,从定性对比和定量对比两个方面开展对比实验。

    • 图 4为一幅质量一般的断裂等高线图像样本,图 4中断裂破碎的等高线较多,断裂形态复杂度较高。

      图  4  原始样本

      Figure 4.  Original Sample

      图 5(a)为运用文献[12]方法完成的断裂等高线重建结果,该方法虽然实现了大部分平缓等高线的准确匹配连接,但对位于山脊、山谷区域形状陡峭的断点未能连接,如图 5(a)中虚线圆圈区域所示。该方法也没能避免交叉错误连接,如图 5(a)中虚线矩形区域所示。图 5(b)为Samet方法的处理结果,如图 5(b)中虚线矩形区域所示,该方法在密集且近似平行等高线处会出现大量交叉错位连接,并且当等高线断裂间隙过大时,该方法或者无法连接,或者造成错连;如图 5(b)中虚线圆圈区域所示,该方法对山脊、山谷区域形状过于陡峭的断点依然无法完成匹配连接。图 5(c)为运用Gul方法的重建结果,如图 5(c)中虚线圆圈区域所示,该方法对断裂间距大且近似平行的断点无法完成连接;如图 5(c)中虚线矩形区域所示,该方法还会造成平行断点的错位连接。

      图  5  其他方法处理结果

      Figure 5.  Results Processed by Other Methods

      图 6给出了运用本文方法进行复合迭代匹配连接所取得的中间结果和最终结果。图 6(a)为对断裂间隙在[0,30]像素区间内断点的重建结果,本文方法在该阶段首先提取满足断裂间隙限制的断点备选断点,然后依据断点方向差异约束准则和最大阈值,针对性地采用文献[12]方法处理平缓过渡的断点,采用Samet方法处理方向差异较大、形状略为陡峭的断点。由图 6(a)中虚线大圆圈区域可以看出断裂间隙超限的断点未能重建,图 6(a)中虚线小圆圈区域为山谷山脊区域方向差异增大、超过约束限制的断点,也未能完成匹配连接。图 6(b)为断裂间隙在[30,60]像素区间的重建结果,该阶段以上一阶段处理结果为数据源开始迭代处理,提取该区间断裂尺寸较大的部分断点后,根据断点方向差异约束准则分别采用文献[12]方法、Samet方法完成不同形状类型断点的匹配连接,如图 6(b) 中大小虚线圆圈区域所示,剩余少量未完成的断点呈现了断裂间隙超限和形状过于陡峭的特征。图 6(c)为断裂间隙在[60,90]像素区间的重建结果,该区间的处理过程采用同样的方法和思路迭代处理,经过处理后仅剩一个距图边远且无对应匹配断点的断头线 (如图 6(c)中圆圈标识) 需人工处理。可认为本文方法对该图完成了所有断裂等高线的匹配重建,人工判读后确认该图中不产生错误连接。对于采用断点方向角和方向差异运算改进的文献[12]方法、Samet方法仍不能完成匹配连接的断点,可最后采用Gul方法进行补充处理,最终完成所有断点的处理。

      图  6  本文方法处理结果

      Figure 6.  Results Processed by the Proposed Method

      本文方法将等高线断点的断裂间隙大小和断点间方向差异紧密结合,根据断裂间隙区间由小到大划分大的重建阶段,以方向差异由平缓到陡峭针对性地采用不同方法分批处理,由断裂间隙控制备选断点的选取,断点方向差异约束匹配连接的准确度,充分体现了断点匹配中由近到远、由平滑到突变的人工识别格式塔原则。与图 5相比,本文方法重建效果明显优于文献[12]方法、Samet方法和Gul方法。

    • 本文进一步采用文献[14]提出的指标进行了定量比较实验来评估算法性能。表 1给出了运用本文方法与Samet方法、文献[12]方法、Gul方法对随机选取的4幅实验样本进行处理的定量分析结果。

      表 1  本文方法与其他方法的性能对比

      Table 1.  Performance Comparison Between the Proposed Method and Other Methods

      源图像 图幅尺寸/像素 断裂总数 重建方法 完成连接数 错误连接数 未连断裂数 完成率/% 正确率/% 运行时间/s
      样本1 364×230 55 Samet方法 51 2 1 92.73 96.08 0.031
      文献[12]方法 48 0 7 87.27 100 0.245
      Gul方法 50 1 5 90.91 98 1.265
      本文方法 55 0 0 100 100 1.762
      样本2 544×292 68 Samet方法 65 2 3 95.6 96.9 0.047
      文献[12]方法 43 1 25 63.24 97.67 0.485
      Gul方法 65 0 3 95.59 100 3.516
      本文方法 68 0 0 100 100 1.894
      样本3 704×468 91 Samet方法 89 8 2 97.8 91.01 0.063
      文献[12]方法 83 0 8 91.21 100 0.390
      Gul方法 85 3 6 93.41 96.47 6.265
      本文方法 91 0 0 100 100 1.991
      样本4(图 4) 522×468 144 Samet方法 122 25 22 84.72 79.51 0.140
      文献[12]方法 124 6 20 86.11 95.16 0.766
      Gul方法 138 1 6 95.83 99.27 4.578
      本文方法 144 0 0 100 100 2.421

      表 1中可以看出,随着等高线图像尺寸变化和断点断裂形态复杂度增加,文献[12]方法、Samet方法、Gul方法的正确率、完成率和运行效率等指标均会产生较大起伏,很难保持理想稳定的水平,即不能彻底重建各类图中所有断点。本文方法对几种不同质量和复杂度的样本均取得了100%的正确率和完成率,优于其他三种方法。随着样本尺寸增大和断点复杂度增加,本文方法在处理过程中会将断裂间隙区间范围划分更细,方向差异约束阈值也会灵活变更,使复合迭代的层级和遍历次数增加,并且还可在迭代临时结果不理想的情况下进行数据还原,重新设置断裂区间和方向差异约束阈值,从而使运行时间延长、计算效率下降。从表 1总体来看,即使图像尺寸和断点复杂度逐步增加,本文方法运行时间并未出现无限制延长,而是在中等可接受的范围内。定量对比结果表明,本文方法基本具备完成不同尺寸和复杂度等高线图像中断裂等高线重建的能力,具有良好的适应性和稳定性。

    • 针对复杂断裂等高线的重建过程涉及人工智能识别判断的难题,以及目前最新方法依旧未能完全解决该问题的现状,本文通过借鉴几种最新方法的优点,模拟和分解人工智能识别判断断点匹配连接这一复杂过程,提出了利用复合迭代策略的断裂等高线自动重建方法。该方法建立了一种断裂间隙逐级递增、断裂形态由平缓到陡峭分级分类规律,建立了方向差异约束准则,实施了不同方法、参数和图像数据复合迭代的渐进式处理过程,有效实现了复杂栅格地形图中所有断裂等高线的正确重建。本文利用的复合迭代策略遵循人工智能判别规律,迭代方法过程清晰、简洁、易实现。实验结果表明,该方法的正确率、完成率优于文献[12]方法、Samet方法和Gul方法等其他方法,运行稳定,具有良好的实用性和适应性。

参考文献 (19)

目录

    /

    返回文章
    返回