曲线简化中节点重要性度量方法及其评价

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

1、曲线简化中节点重要性度量方法及其评价陈杰，邓敏，徐锐（中南大学测绘与国土信息工程系，湖南长沙，410083）摘要:在曲线简化过程中，一个最基础的问题是如何度量曲线上每个节点的重要性程度，它也是选取节点的基本依据。本文首先简要回顾和评价了现有的节点重要性度量方法，即角度法、面积法、弧比弦法和垂比弦法。然后，提出了一种改进的垂比弦法，并给出了具体的评价方法。通过曲线简化实验发现，相比于弧比弦度量方法，改进后的垂比弦度量方法选取的节点能够较好地保持曲线的形状。也就是说，改进后的垂比弦度量能够更好地表达曲线上节点的相对重要性程度。关键词：多尺度表

2、达，曲线简化，节点重要性度量，评价1引言曲线节点重要性的研究已广泛应用于计算机视觉、图像处理、模式识别、计算机图形学[1]和地球信息科学等领域。例如，在计算机视觉和模式认知领域，用于目标提取、形状识别、[2]点的运动轨迹估计和编码。在地球信息科学领域，用于数据压缩、多尺度表达等。Attneave发现曲线上的一部分节点比另一部分节点含有更多的信息，并且富含更多信息的节点比其它[3]节点更能够保持目标的形状，也就是说，这些含有少量信息的节点如果被删除后并不会导致曲线形状发生很大的变化，这也是曲线简化时的一个重要准则。为此，本文探讨曲线节点的重

3、要性度量问题。[4-6]目前，许多学者已经提出了一些度量节点重要性程度的方法，如角度度量法、面积[7][8][9]度量法、弧比弦度量法、垂比弦度量法等。这些方法都具有一定的应用范畴，例如，角度度量法和面积度量法在制图综合中应用较早。为此，本文首先简要回顾现有的方法，然后提出一种改进的垂比弦方法，并进行评价分析。2曲线节点重要性度量的现有方法本文将现有的方法分为两大类：没有顾及支撑域的度量方法和顾及支撑域的度量方法。前者主要有角度度量法和面积度量法，后者主要有弧比弦度量法和垂比弦度量法。2.1没有顾及支撑域的度量方法2.1.1角度度量法对于

4、一条曲线，如果删除其中某个点，将会引起一个角度变化。进而，可以根据这一角度变化的大小来度量这个点的重要性（端点除外）。不妨设曲线上的点依次为p，p，01p2，⋯，pn（其中p0和pn为曲线两个端点），那么删除任一点pi引起的角度变化可以表[4-6]达为：α()ip=∠iip−+11pi,11≤in≤−（1）P3Piα1αPPjα34P20P1P2(a)(b)图1角度度量计算方法及其局限性基金项目：国家自然科学基金项目（No.40501053）和湖南省自然科学基金（No.07JJ6075）391如图1（a），有5个节点，分别记为p，p，p，

5、p和p。根据式（1）则可依次01234计算得到p，p和p的角度度量值。角度变化越大，点的重要性程度越高。但是，这种123重要性度量方法容易受小的凹、凸的影响。如图1（b），Pj的角度度量值要比Pi大，但是删除Pj对曲线形状的影响不如删除Pi的影响大。2.1.2面积度量法对于一条曲线，如果删除其中某个点，将会产生一个局部变形。这种变形可以利用新曲线与原始曲线围成的面积来度量，如图2（a）。进而，根据这一围成面积的大小来判断这一点的重要程度，本文称为面积度量法。于是，可以表达删除每个点（端点除外）引起的面积[7]变化为：Ai()=S,11≤i

6、n≤−（2）∆pppii−+11i根据式（2），可以计算得到每个节点的面积变化。面积变化值越大，重要性程度越高。但是，这种方法也容易受变化平缓的长条三角形的影响。如图2（b），删除P1引起的面积变化与删除P4引起的面积变化相同，即重要性程度相同，但是删除P1引起的曲线形状变化要比删除P4引起的曲线形状变化大得多。P3P1S3SP4SS2P41PSP1340P0P2P1P2P5(a)(b)图2面积度量计算方法及其局限性2.2顾及支撑域的度量方法2.2.1弧比弦度量法根据文献[8]，支撑域半径R的取值由曲线的总长度（L0）和曲线的节点数（V，

7、其中端点除外）计算得到，并表达为：L0R=（3）P3V+1L3进而，对于曲线上任一节点Pi，它的重要性C3P4程度取决于支撑域范围内弧线长度Li与相应弦P0长Ci的比值，表达为：P1P2LCi()=LCii/，11≤≤−in（4）图3弧比弦度量计算方法一种特殊情况是圆与曲线有一个交点。在这种情况下，把圆心到交点的直线距离P4P5作为弦长，即为半径R。P3P6D4,2P72.2.2垂比弦度量法P0对于曲线上的节点Pi，它的重要C4,2P1P2性程度可以根据该点到其邻近点Pi-k、Pi+k连接弦长的垂直距离Di,k与图4垂比弦度量计算方法39

8、2[9]弦长Ci,k的比值来度量，该种度量方法亦称之为垂比弦度量法，并且可以表达为：DCi()=D/C，11≤≤−inik,,ik（5）式中，k的取值从1开始，直到满足如下条件结束，即DDik