利用搜索算法原理进行等高线接边

利用搜索算法原理进行等高线接边 第23卷第1期 1g94年2月 测绘 ACTAGEODJETICACARTOGRAPHICA$INICA Vol23,No.1 Feb.199~. 一 77利用搜索算法原理进行等高线接边 李霖 (武汉测绘科技大学,430070) 7 【提要】一般情况下,立体像对测得的等高线数据进行接边处理,距离作为等高 线匹配的标准存在一定的缺陷.本文介绍一种将等高臻本身具有的图形特征作为匹配标 准并利用搜索算法原理寻拽共轭等高线的算法.此算法具有处理等高线数据异常的能 力,较适台一般情况下等高线的接边处理,在此算法中为了减少盲目的搜索提出一种 计算关联值的并此来选择前进的方向,提高搜索效率.此算怯经过了上机实验, 结果令人满意. 【关键蔼】图形特征搜索匹配关联值 1弓 彳;阅茅为残,菇 — , 数字地图的数据来源是多种形式的,除直接在现有地图上采集数据外,航空像对也是重 要的来源之一根据立体像对测得的等高线数据,是地形数据的重要来源.但是,若未进行 接边,就不能直接用作数字地图,因为一幅地形图(比如1:1万比例尺)范围内的等高残数 据由几个像对组成,数据是分块的. 利用立体测图仪测图是一项人机交互的工作,同时也是一个费时,劳动强度较大的过程, 有些数据难免不符台.另外,测图目的不一样,对数据的要求也不同,测图时并没有考虑 到数据将来会用作不同的目的,如果按新要求重测(特别是数据量很大时),显然是不经济 的.因此,设计接边处理算法时,应尽量考虑一般情况下的数据,使其 有较广的适用范围. 在文献报道的等高线接边算法中,为了提高匹配效率,有的算法在重叠区内将矢量数据 转化为栅格数据,处理完后再转化为矢量数据.J有的算法则依赖比较敏感的闽值13.这 类算法对数据采集时产生的”异常情况难以察觉,而且在确定共轭线时,总存在某些不足, 比如确定栅格尺寸或阌值大小,为克服这些不足,适应多种情况,本文将等高线本身的图形 特征作为匹配的标准,并将匹配过程描述为搜索过程,使之能完成一般情况下的等高线接 边. 2图形特征 设计接边算法前,要了解等高线数据所反映出的一般情况,为了使接边算法具有较普遍 的适用范围,由像对测得的等高线数据会呈现如图l所示情况 如图1:高程为1060的等高线由Cj,C组成,图形不连续J高程为1050的等高线由C., *本文1992年3月t2日收到.截稿日期为1993年1月1日. 1期李霹:利用搜索算浩原理进行等高线接边75 C;组成,尽管从图形上看不出不连续的情况,但实际上数据是不连续 的而且有重复数据点, 1040的等高线出现交叉;更有甚者1030的等高线在接边处出现”扭麻花”的现象;此外, 还有少量多余”线头”如1020的等高线,以及”飞线. 如果接边算法有能力处理如图1所示一股情况的等高线数据,那么显然也能处理比较 “理想的数据. 图1 考虑如图1所示的情形,用节点匹配方法或 仅靠距离作为匹配的标准显然难以奏效.鉴于此, 我们采用等高线本身具有的图形特征作为匹配的 标准,用搜索算法原理寻找共轭线段,最大限度 内保证同名等高线各线段间的关系正确. 等高线作为反映地貌形态的符号,本身有其 平面图形特征,这主要现为(间曲线除外): (1)曲线是连续的J (2)曲线本身及曲线间不相交} (3)曲线是封闭的,或曲线两端点位于图 边. 显然,图1所示的等高线数据不具备以上图形特征.据此,在处理过程中,将数据所反 映的图.形特征与等高线本身的图形特征进行匹配,使处理后的数据 具有上述等高线的图形特 征. 3等高线匹配过程 由于所采集的数据中,等高线的高程是给定的(假设不会错误),因而匹配过程就是在同 高程等高线线段中,确定曲线段连接的顺序. 任意两条同高程的等高线都存在连接的可能(即台并成一条等高线).连接的标准是台并 后的线是否与图形特征一致. 如图2(4)有同属某一等高线的5条曲线段,C,C是位于图边的线.若用节点表示 曲线段,弧表示关联关系,贝?处理其连接的方式如图2(6).设C,为起始节点,C只能与C, C.,C?,Ce中之一连接(或有关联关系),若C与Ca有关联关系,则Ca只能与C:,C,C Ca)(6) 测绘23卷 之一有关联关系……. 确定这几段线间蛇关联关系过程可转化一搜索过程.对于上例,其状态可用五元有序组 表示,初始状态为[c,,},,}],皋为待确定的元素,终止状态为[c,Cs,C., ,](即解节点),图3表示搜 索途径., 粗线表示搜索成功(即找至解 节点)的路径.搜索过程是在一棵 树上进行的. 在搜索过程中,我们总希望扩 展后的子节点中只有一个节点满足 要求,可是,实际上可能在子节点 中有一个以上的节点满足要求,这 种二义性在搜索过程中总是难免 的,然而,某些子节点以下的节点 最后会与图形特征矛盾或不满足终图3 ?] \【CC—C} 止条件(根据图形特征,2之(3)是作为终止的判断条件). 若一条开曲皴由几段曲线{C}组成并且不知道哪一段线可作为第一节点,则由这几 个节点组成的序列(或状巷)[:,C:.,……,:s]C?(-},一共有n1个不同的序列, 其解点在这”1个序列之中. 如果这”段线不是构成一条等高线,而是几条并且等高线条数也不能预先确定,那么搜 索过程实际上是在一片森林中进行的,每一条等高线由曲线段组成的序列(状态)是某棵树 上的某一片叶.因此,搜索遍某一棵树的叶节点并不能保证得到所需的状态,如图2之中, 若将2司定为根节点,那么在这一棵树上没有所需要的节点. 根据等高线的图形特点,一棵树上最多只有一个所需的叶节点,而叶节点数与原始曲线段 线成阶乘关系,在这样庞大的空间中进行搜索相当赞时.为此,在搜索过程中增加一定的信 息,启发(或提示)搜索过程沿着最可能”正确”的路径前进,而不盲目地搜索.这个启发 固4 搜索过程的信息,通过过程本身对数据加工得到. 对启发信息,我们基于这样的考虑:一段线与其他段线 关联(连接)的可能性是存在差别的,启发信息应能反映出这 些差别索过程首先考虑可能性大的,其次是可能性小的.反 映这些差别的值称关联值.这样的搜索过程可借用有序状态空 间的算法来完成. 若用节点表示曲线段,弧表示关联关系如图2(6).设当前 段如图4,是第层中的节点C,巳处理过的节点集合为H, 来处理过的节点集合为S. 按扩展S中的每一元素作为C:的子节点(在K+1 屡),计算S申的节点与连接的关联值,选择关联值最大的 子节点作为当前节点,此节点在+1层设为C:+,在S中去掉此节点.若C:与C:连接 后特征能匹配,将c;+{加到H中,对c:,同样在s中扩展子节点j若c与c:连接后特 1期李霖:利用搜索算法原理进行等高线接边77 不匹配,则重新选择S中关联值最大的节点作为当前节点,作上述处理j若c:的S集台 为空,则回逆到K一1层,当前节点为C:一,在/-/q~去掉C.重复此过程,到满足终止条 件. 然而,搜索前,不知哪些线段构成开曲线,哪些构成闭曲线,初始节点很难确定,但可 任取一节点开始,按一段线的关联端点有两个,从中问开始向两边同时扩展. 这种双向扩展的方式只须对上述搜索过程作适当修改,在此过程中要合并多个原始节点 (逐步合并)形成复合节点,而且每次台并时将相应的两个节点与当前节点一起合并成一新 的复合节点. 从这一过程可看出,具有一定等高线知识的搜索过程有剔除数据错误(异常)的能力. 4关联值的计算 根据等高线图形的位置特点(空间关系),两曲线关联的可能性与其距离成反比,距离越 小,连接的可能性越大,因此可以将距离的倒数作为关联值. 求两线的关联值,最简单的方法是节点(或顶点)匹配,但是,这种方法仅考虑曲线端 点而没有顾及曲线本身,不能适应一般情况. 因此,考虑两线问距离的计算应顾及整条曲线的形状.此距离定义为:两曲线上两点问 的最短距离,即 d=MIN{P1.P2,『:P1.?Cl,P2,?C2) C,c分别为两曲线,P;,P分别为曲线Ct,Ct上的点,d为c,C:间的距离. 此外,两条曲线连接时(合并成一条曲线),应注意连接的次序,台理的连接是合并后 曲线的弦长应为最长. . (口) 图5 „ 一. (6) 如图5(a),当C1与C2合并 时,台理的连接是 l—--n22,而 其他如-一i一 t则是不台理的 连接.按这样的原则连接可以除去 一 些不必要的线头.如图5(6),C 与C合并后仍为C,Ct被自动 “合并”掉. 5算法改进 搜索过程的处理速度主要依赖于特征匹配过程和计算反映连接可能性的关联值过程. 为了缩小搜索宽度,减小回逆,预先给定一距离闻值(比如等高线问距的估计值),当两 曲线距离超过闻值时,认为这两曲线不存在连接的可能,因为若这两条线连接后会与其他曲 线相交而与图形特征不匹配.这样可大大地减少不必要的回逆节点. 对矢量数据而言,计算两曲线间距离是相当花时间的,若将计算两直线段的最小距离称 为一次运算,则当两曲线分别由k和:段折线组成时,计算两曲线间的距离共进行?次 运算. 根据实渊数据的状况,可以用曲线两端部分参加计算距离代替整条线参加运算,即曲线 问的距离近似地『目两端部分的曲线间距离来代替. 78测绘23卷 如图6,d=MIN(尸】.P2jJlPEC,PtjEC:} ;MIN(dCiC,dCiC:,dr.,C..,dC;Cg) 曲线两端的多大部分参加运算,显 然是非常实际的问,最理想的情况是 恰好包含重叠部分.按一般情况,我们 作下列假设(经实际验证这个假设是较 合理的) —— 曲线重叠部分与曲线长(或折 线段)成正比} ——重叠部分的长(或段数)不超过总曲线长的平方根.因而,某曲线的一端参加运算 的折线段数n,与总曲线段数的关系为:[~/n],([]为取整) 分别具有A,段两曲线闻的距离计算所需运算次数为? 4?[~/1][~/2]?4-[I?j] 两种方法的运算次数之比为 e=4?[I?t]/(】?2)4l-2 着I=2=19,则日=4/=2/5} 若两曲线直线段增至?I==i00时,则 日=4/*/—100—00=i12s 由此可见,曲线越长,近似计算的效率越高. 采用端部曲线计算最短距离的另一优点是不必以最长弦长作曲线间连接的标准.由于没 有等高线的”标准一位置,为保证等高线连接的位置精度,用两曲线间的最短距离决定如何 连接两共轭线,计算距离时,下两曲线最近的两点,若距离小于某一闻值,连接这两点 形成一条整体曲线.这方法除了对接边处测图时对点较准的情况有效外,对有重叠部分的等 高线数据也同样很有效,因为重叠时,两曲发的距离为.或很小.逸样绝大多数的等高线能 在满足精度的条件下自动连接.若距离大于阈值,剐暂时按上述方式连接,将此线作上标记, 匹配完所有的数据后,在屏幕上显示结果,对有标记的线,用人机交互手段进行检查,核实 以及修改. 根据前述原理和方法,我们用TURBOC语言在PC386机上进行实施,对四幅1:I万 地形图范围(山区)的等高线数据分别进行处理,数据较大的一幅只需26分钟左右,对这 四幅图范围内的所有等高线数据一次处理,共有2500多条曲线,分属160多个高程带,一 条曲线上折线段最多者这几百段,一般为几十段,同一高程带中最多的曲线段为35条(平均 约15条曲线,即平均搜索节点为l51),运行时闻约2小时,速度是较快的,结果相当令人 满意,图上所剩要用人机交互的地方寥寥无几,大大地减少了人工参入的工作量. 这种方法处理后结果的正确程度取决于搜索过程中所具备的等高线特征知识,若描述的 特征越全面,越详细,结果中所剩错误越少但特征越详细,特征匹配的时阐越长应该在 时间和正确洼之间达到适当平衡例如,我们在处理中没有全面考虑”曲线不相交这一特 征,因为若不建立专门的数据结构和索;【,曲线的矢量求交判断设费时间,而现有数据中, 不同高程的曲线相交情况极少 1期李秣:利用搜索算法原理进行等高线接边79 这种方法的速度与搜索路径有关,按关联值大小选择路径,大大减少 无效搜索,使搜索 过程尽可能沿着正确的路径进行. 图7,图8分剐反映处理前后的情况,全幅图是1:2.5万地形图的缩小 图,为避免模 糊,等高距加大为40米,并附局部放大图. 图7处理前 () (丑) 图8处理后 经实践检验,本文提出的接边方法能处理一般情况下等高线数据,算 法中所考虑的因素 比较合理,在速度与正确性之间有较好的平衡. 参考文献 [1)RaymondJHintz.MikeZZhao.DemonstrationofIdealsinFullyAutomaticLine MatchingofOverlappingMapData.Auto-Carto0Proceeding,1990 (2)SchenkT.ARobustSolutiont.theLine-MatchingProblemiaFhotogrammetryand Cartography.FhotogrammetricEngineeringandRemoteSensiag,Vo1.52,No.11,1986 (3)李霖.地图拓扑数据的自动组织.武侧,1987(4)