曲线简化中节点重要性度量方法研究

《曲线简化中节点重要性度量方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、cGF规范s暇务-2008高校Gls论坛论文集曲线简化中节点重要性度量方法研究邓敏陈杰徐震南京大学地理信息科学系【摘要】在曲线简化过程中，一个最基础的问题是如何度量曲线上节点的重要性。本文首先简要回顾和评价了现有的节点重要性度量方法，即角度法、面积法、弧比弦法和垂比弦法。然后，提出了一种改进的垂比弦法，并给出了具体的评价方法。通过曲线简化实验发现，相比于弧比弦度量方法，改进后的垂比弦度量方法选取的节点能够较好地保持曲线的形状。【关键词】多尺度表达；曲线简化；节点重要性度量；评价1、引言曲线节点重要性的研究已广泛应用于计算机视觉、图像处理、模式识别、计算机图形学和地球信息科学等领域⋯。

2、例如，在计算机视觉和模式认知领域，用于目标提取、形状识别、点的运动轨迹估计和编码。在地球信息科学领域，用于数据压缩、多尺度表达等[21。Attneave发现曲线上的一部分节点比另一部分节点含有更多的信息，并且富含更多信息的节点比其它节点更能够保持目标的形状【3】。也就是说，这些含有少量信息的节点如果被删除后并不会导致曲线形状发生很大的变化，这也是曲线简化时的一个重要准则。为此，本文探讨曲线节点的重要性度量问题。目前，许多学者已经提出了一些度量节点重要性程度的方法，如角度度量法【4—6】、面积度量法【7】、弧比弦度量法【8】、垂比弦度量法【9】等。这些方法都具有一定的应用范畴，例如，角

3、度度量法和面积度量法在制图综合中应用较早。为此，本文首先简要回顾现有的方法，然后提出一种改进的垂比弦方法，并进行评价分析。2、曲线节点重要性度量的现有方法本文将现有的方法分为两大类：没有顾及支撑域的度量方法和顾及支撑域的度量方法。前者主要有角度度量法和面积度量法。后者主要有弧比弦度量法和垂比弦度量法。30lwww．glserac．I∞2．1没有顾及支撑域的度量方法2．1．1角度度量法对于一条曲线，如果删除其中某个点，将会引起一个角度变化。进而．可以根据这一角度变化的大小来度量这个点的重要性(端点除外)。不妨设曲线上的点依次为户0，尸1，尸2，⋯。P。(其中尸0和尸n为曲线两个端点)，

4、那么删除任一点P1引起的角度变化可以表达为【4—6】：伐(z)=么pfPf—lPi+1，1≤f≤聆一1(1)P1P，fbl图1角度度量计算方法及其局限性如图1Ia)。有5个节点。分别记为Po。P1．尸2。尸3和&。根据式(1)则可依次计算得到，P1。尸2和P3的角度度量值。角度变化越大，点的重要性程度越高。但是，这种重要性度量方法容易受小的凹、凸的影响。如图1(b)，R的角度度量值要比一大。但是删除只对曲线形状的影响不如删除Pi的影响大。2．1．2面积度量法对于一条曲线，如果删除其中某个点，将会产生一个局部变形。这种变形可以利用新曲线与原始曲线围成的面积来度量。如图2(aJ。进而，根

5、据这一围成面积的大小来判断这一点的重要程度。本文称为面积度量法。于是，可以表达删除每个点(端点除外)引起的面积变化为f7】：A(i)=S锄一一。，j+。，1≤i≤刀一1(2)根据式(2)。可以计算得到每个节点的面积变化。面积变化值越大。重要性程度越高。但是，这种方法也容易受变化平缓的长条三角形的影响。如图2(b)。删除尸1引起的面积变化与删除尸4引起的面积变化相同，即重要性程度相同，但是删除P，引起的曲线形状变化要比删除尸4引起的曲线形状变化大得多。PPqnP2(a)(b)图2面积度量计算方法及其局限性t科矾与a圭蜘新2．2顾及支撑域的度量方法2．2．1弧比弦度量法根据文献【8】，支

6、撑域半径H的取值由曲线的总长度(￡o)和曲线的节点数(V。其中端点除外)计算得到。并表达为：R：嘉(3)矿+1、。’进而。对于曲线上任一节点一，它的重要性程度取决于支撑域范围内弧线长度￡i与相应弦长Ci的比值，表达为：LC(i)=Li／Cf。1≤f≤疗一1(4)一种特殊，青况是圆与曲线有一个交点。在这种情况下。把圆心到交点的直线距离作为弦长，即为半径R。PlP2图3弧比弦度量计算方法2．2．2垂比弦度量法对于曲线上的节点只。它的重要性程度可以根据该点到其邻近点只-k、一十k连接弦长的垂直距离Di。k与弦长G．k的比值来度量，该种度量方法亦称之为垂比弦度量法。并且可以表达为【9】：DC

7、(i)=B．t／Cf．I。1≤f≤n一1(5)式中，k的取值从1开始．直到满足如下条件结束。即丝>监e，te舢l(6)如图4，对于点P4，k的取值为2。不难发现，该方法是一种自适应度量方法，没有固定的支撑域。这里。支撑域实质上是一种约束，即式(6)。但是，这¨m越黜I．c‘mPcGF规范s暇务．2008高校GIS论坛论文豢种方法与角度度量法一样，容易受到噪声的影响。PI岛图4垂比弦度量计算方法3、一种改进的垂比弦度量方法为了克服垂弦比度量方法的不足，本文提