一种新型的地形等高线矢量化方法.pdf

2004.3计算机工程与应用1引言等高线的识别和矢量化工作一直是GIS中一个非常重要而又远未解决的工作1。对于这项工作，人们提出了不少方法，比较传统和经典的矢量化地形等高线的方法大体可分为以下几个步骤：!对等高线地图进行预处理，比如消除噪声，二值化等；细化；#用链码表示等高线；$进行其它处理，比如用曲线表示等高线。在传统方法中，等高线的细化环节非常重要，主要是提取图像的拓扑结构。细化又叫中轴变换（mediaI axistransformation）或骨架化（skeIetonisation）2。对于不同的图像，人们提出了很多细化算法24。但每种细化算法都不同程度地存在着局限性。该文根据等高线的特点，提出了一种基于圆跟踪的自动适应的矢量化方法，并在此基础上使用三次B-样条对矢量化结果进形曲线拟合。该文的矢量化方法实际上使用半径不等的圆沿等高线的走向测量等高线，并记录测量的结果的方法。使用该方法，可以不需要对地形等高线进行细化处理，文献1中的方法虽说也不需要细化，但该方法需要从等高线的左端点开始，具有局限性。该文提出的方法可以从等高线的任意一个端点开始。该文的以下部分是这样组织的：在第二部分中介绍矢量化方法跟踪等高线方法；在第三部分中介绍使用三次B-样条对矢量化结果进形曲线拟合；第四部分是实验结果；第五部分给出了结论。2矢量化算法描述等高线有一些很重要的性质，如：一般地形的等高线彼此不应该相交；每一条等高线都是封闭的曲线。在一个小地区范围内，人们所看到的等高线不一定是完整的封闭曲线，但就整体而言它们都是封闭的。该文正是利用了这种特点，对地形等高线的关键数据点进行搜索。具体方法如下：首先查找等高线的起始点A，并记录该点，然后以A点为圆心，以指定的长度为半径画圆，并记录该圆与等高线的交点B，以此类推，每一次画一个圆都记录一个交点，直至所画的圆和等高线没有交点为止，把这个过程叫作跟踪等高线，这一系列的圆叫跟踪圆（图1所示）。以下是在实现跟踪等高线算法过程中应注意的几个问题：（1）从画第二个跟踪圆开始，每个跟踪圆和等高线都有两个交点，如图1中跟踪圆B和等高线有两个交点（封闭等高线第一个跟踪圆和等高线有两个交点，取任意一个交点作为下一个跟踪圆的圆心），第一个近似在A点，另外一个在C点，而C点是应该记录下来的点，此时可做如下处理：当交点落在前一个圆的内部时应该忽略该点。（2）在记录跟踪圆和等高线交点的过程中，实际上记录的是跟踪圆和等高线有几个像素点重合。一般说来，如果等高线较宽，则跟踪圆和等高线重合的像素就较多，此时可以通过求这些像素坐标的平均值作为跟踪圆和等高线的交点。即：x!=1IIi=1xi!=1IIi=1i（1）一种新型的地形等高线矢量化方法陈争光1，2吴裕树1王玉芳21（北京理工大学计算机科学与工程系，北京100086）2（大庆油田技术培训中心，大庆163254）E-maiI：摘要该文提出了一种新型的地形等高线的矢量化方法，使用该方法，不需要对等高线进行细化处理而直接进行矢量化，并在此基础之上对矢量化结果使用三次B-样条拟合。实验证明该方法是有效的，并且试验结果和实际等高线基本吻合。关键词等高线矢量化拟合三次B-样条曲线文章编号1002-8331-（2004）03-0084-03文献标识码A中图分类号TP39A New Schema of Vectorization of ContourChen Zhengguang1，2Wu Yushu1Wang Yufang21（Department of Computer Science Engineering，Beijing Institute of TechnoIogy，Beijing 100086）2（Department of Computer Engineering，TechnoIogy Training Center ofDaging OiI FieId，Daging 163254）Abstract：This paper presents a new method of vectorization of contour.By this method，peopIe can guantize thecontour without thinning it beforehand.The cubic B-spIine approximation is figured based on the vectorization resuIts.The experimentaI resuIts obtained with the proposed schema are encouraging which demonstrates the effectiveness of theapproach.Keywords：Contour，Vector guantization，Fitting，Cubic B-spIine84计算机工程与应用2004.3式中：I为跟踪圆和等高线重合的像素点的个数；xi，yi为跟踪圆和等高线重合像素的坐标；x，y为跟踪圆和等高线的交点。图l（3）在等高线较稠密或者是等高线存在急拐弯的情况下，等高线和跟踪圆之间的关系如图2所示（图中每一个方格代表一个像素）。粗折线代表等高线，箭头指示方向为跟踪圆行进的方向，图中上面的圆指示的是跟踪圆和等高线的交点处于上一个跟踪圆的范围之内，应该忽略。而图中下面的圆和左面的椭圆所指示的跟踪圆和等高线的交点则不处于上个跟踪圆的范围之内，此时如果以这两部分的重合的像素点的平均值作为跟踪圆与等高线的交点记录下来，则结果误差太大，甚至会出现问题。此时应做如下处理：首先按一定的步长缩小跟踪圆的半径重新跟踪（如图2中内跟踪圆所示），如果此时跟踪圆和等高线重合的像素还很多，则继续缩小跟踪圆的半径，直到跟踪圆和等高线重合的像素点在一个指定的阈值范围之内为止。阈值的选择和图像中等高线的宽度有关，如果等高线宽度较宽，则阈值选得大些，反之则阈值选得小些。一般根据经验值，阈值的选择不要超过等高线像素宽度的l.5倍。图2如果跟踪圆和等高线重合的像素数量在允许的阈值范围之内，而这些重合的像素不处于一个连通域内（关于连通域的概念，请参阅文献5），如图3所示，某跟踪圆和等高线有5个像素点（在阈值范围内）重合，但这5个像素点分别位于两个连通域内，则说明是跟踪圆和等高线的两个部分相交（重合），或者是跟踪圆和两条等高线相交，这种跟踪圆和等高线有多个像素点重合并且重合的像素点的个数在规定的阈值范围内的情况不是很多，可以通过人为干预完成。图3（4）跟踪圆的画法使用中点画圆法一个像素一个像素绘制（具体算法请参考文献6中的说明）。并且在绘制过程中判断各个像素是否为圆和等高线的重合点。3利用B样条曲线还原等高线6，7利用上述方法得到的是等高线上一些距离间隔不等的离散的坐标点，为了还原等高线或者是作为后续的插值求其它点的高程或者其它属性，必须对这些离散的数据点进行曲线拟合。在此，采用三次B-样条进行拟合。三次B-样条拟合的过程其实就是反求B样条的过程，拟合的结果就是对每一条等高线上的I个型值点求得I+2个控制点。假设利用上述方法得到某条等高线的一组型值点0i（xi，yi）（i=l，2，I），要找到一条三次B样条曲线C经过这一组点0i（xi，yi），即找到一组与0i（xi，yi）对应的三次B样条曲线特征多边形顶点PJ（xJ，yJ）（J=0，l，2，I，I+l），对于三次B样条曲线，其上的型值点和控制点的关系为：PJ（0）=l6（PJ-l+4PJ+PJ+l）=0J（J=l，2，I-l，I）（2）式（2）有I个方程，但有I+2个未知数，需要两个边界条件。（l）若曲线是通过0l、0I两个端点的三次B-样条曲线。此时有Pl=0l，PI=0I，于是求解PJ的线性方程组为式（3）。该式的系数矩阵是对角线严格占优的，因此系数矩阵是非奇异的，可以使用文献8追赶法求解出PJ（xJ，yJ）（J=l，2，I）。P0和PI+l的求法为P0=2Pl-P2，PI+l=2PI-PI-l。此时生成的三次B-样条曲线在两端点处的曲率为零。（2）若等高线是封闭曲线，为了保证曲线能首尾相连，此时设P0=PI，PI+l=Pl，此时可得如式（4）所示的线性方程组。求得各条等高线的控制点之后，再利用文献7提供的三次B样条曲线的画法画出对应的等高线。6 0l 4 l0l 4 l.0l 4 l0TLTJ6PlP2P3!PI-lPITLTJ=60l0203!0I-l0ITLTJ（3）852004.3计算机工程与应用（上接64页）致的。如果已知A是向上继承的，并且检测到Pl和P2在A上的属性值是不一致的，则描述框架中可能存在下面的问题：一是Pl（A）和P2（A）中至少有一个是不正确的或不精确的；二是Pl（A）和P2（A）中至少有一个是无值的，即不完备的；三是可能Pl不是P2的超部分。上面，讨论了语义一致性和完备性分析的情况。主要是利用属性分析帮助检查知识库的语义一致性和完备性，以便创建正确、健壮和较完备的知识库。4总结和进一步探讨的问题第2部分主要以人造物为背景讨论了基于Part-whoie关系的属性分析，包括整体和部分之间的属性相互继承关系；分析多个属性之间的内在约束关系；分析属性的单调性。另外，给出了命题l和命题2。第3部分主要讨论了三种重要的语义不一致性。实践证明，知识分析是建立知识库系统过程中的关键一环，属性分析是知识分析中的重要一部分。该文为说明属性分析的思路和意义，仅仅讨论了整体和部分的相同属性的属性分析。对于整体和部分的不同属性之间的内在约束关系没有分析，也没有讨论部分之间的属性值之间的依赖关系。笔者将对上述问题做进一步讨论。致谢：中科院计算所大规模知识课题组的博士生张春霞同学给予过不少的建议，在此表示感谢。（收稿日期：2003年2月）参考文献l.曹存根.知识分析中的若干概念和方法R.中科院计算所学术报告，200l-062.雷玉霞，眭跃飞.基于Concept-Reiation模型的知识联通J.计算机科学，2002；29（ll）：53583.雷玉霞.基于本体的军事知识联通.北京：中科院软件所资料室，2002-064.雷玉霞等.基于本体的军事知识获取以及知识分析J.计算机科学（专刊），2002；29（ll）：l44l485.A Artaie，E franconi et ai.Part-whoie Reiations in Object-CenteredSystems：An OverviewJ.data&Knowiedge Engineering，l996；20：3473836.E winston，R Chaffin，d Herrmann.A Taxonomy of Part-whoieReiationJ.Cognitive Science，l987；ll：4l74444 lll 4 l0l 4 l.0l 4 lllTIIIIIILTIIIIIIJ4PlP2P3!PI-lPITIIIIIILTIIIIIIJI6OlO2O3!OI-lOITIIIIIILTIIIIIIJ（4）4实验很显然，如果使用的跟踪圆的半径较小，那么记录下来的交点的数量就较多，根据这些点还原出来的等高线就越和实际的等高线相吻合。所以在实际工作过程中，可以根据等高线的实际情况和精度要求选择不同半径的圆来跟踪等高线。图4图5图4是使用上述方法在计算机上使用Visuai C+6.0编程运行的结果，图4（a）是一条宽度为3个像素的等高线，其中在A点处曲线的曲率较大。图4（b）（c）（d）分别是在跟踪圆半径为30像素，20像素和l5像素的跟踪结果基础之上通过三次样条函数还原的等高线。笔者主要关注曲率最大点处的结果，图5是把图4（a）、（b）、（c）、（d）叠加在一起的情形，从图5可以看出，随着跟踪圆半径的减小，最后结果就越接近实际的等高线（图5中A点处所示）。在实际工作中，如果曲线的曲率不大，则跟踪圆的半径可选得较大些，这样，既能满足实际要求，也减少了运算量，提高了效率。5结束语（l）实验证明，使用该文提出的跟踪等高线的方法进行等高线的矢量化减少了常规地形等高线矢量化方法中细化等高线的步骤，大幅度提高了效率。（2）使用该文提出的方法，矢量化可以从等高线的任意端点开始，没有方向限制，如果等高线是封闭曲线，则从任意一个点开始跟踪等高线。（3）该文提出的方法能够根据地图中等高线的疏密程度和曲线的曲率大小自动调整跟踪圆的半径大小，从而使结果更加接近真实的等高线。（4）该方法不仅能跟踪地形等高线，而且对于图像中物体的边界跟踪效果也不错，所以在模式识别和机器视觉方面也有所应用。（收稿日期：2003年3月）参考文献l.李岩影，过静君.等高线扫描图象的高效自适应识别方法J.北京测绘，2000；（2）2.Vincent Ranwez，Pierre Soiiie.Order independent homotopic thinningfor binary and grey tone anchored skeietonsJ.Pattern RecognitionLetters，2002；23：6877023.Ju Jia Zou，Hung-Hsin Chang，Hong Yan.Shape Skeietonzation byidentifying discrete iocai symmetriesJ.Pattern Recognition，200l；34：l895l9054.陈国军，叶飞跃.大幅图象的分块细化加速算法J.计算机工程与应用，200l；37（23）：l0ll025.章毓晋.图象工程（上册）.北京：清华大学出版社，l999-036.孙家广.计算机图形学.第三版，北京：清华大学出版社，2002-0l7.纪玉波.计算机图形学.北京：煤炭工业出版社，2000-068.徐士良.C语言常用算法.第二版，北京：清华大学出版社，200l86一种新型的地形等高线矢量化方法一种新型的地形等高线矢量化方法作者：陈争光，吴裕树，王玉芳作者单位：陈争光(北京理工大学计算机科学与工程系,北京,100086;大庆油田技术培训中心,大庆,163254)，吴裕树(北京理工大学计算机科学与工程系,北京,100086)，王玉芳(大庆油田技术培训中心,大庆,163254)刊名：计算机工程与应用英文刊名：COMPUTER ENGINEERING AND APPLICATIONS年，卷(期)：2004,40(3)被引用次数：9次 参考文献(8条)参考文献(8条)1.李岩影;过静君 高线扫描图象的高效自适应识别方法期刊论文-北京测绘 2000(02)2.Vincent Ranwez;Pierre Soille Order independent homotopic thinning for binary and grey tone anchoredskeletons外文期刊 2002(6)3.Ju Jia Zou;Hung-Hsin Chang;Hong Yah Shape Skeletonzation by identifying discrete local symmetries外文期刊 2001(10)4.陈国军;叶飞跃 大幅图像的分块细化加速算法期刊论文-计算机工程与应用 2001(23)5.章毓晋 图象工程 19996.孙家广 计算机图形学 20027.纪玉波 计算机图形学 20008.徐士良 C语言常用算法 2001 本文读者也读过(8条)本文读者也读过(8条)1.叶海建.李四明 工程图纸向CAD系统自动输入处理期刊论文-计算机工程与应用2003,39(33)2.孙景荣.许录平 一种改进的图形矢量化方法期刊论文-计算机工程与应用2004,40(1)3.宋晓宇.王永会.栾方军 基于动态跟踪步长的直线快速矢量化算法期刊论文-计算机工程与应用2002,38(2)4.胡青泥.王晓丽 一种包括隐含图形信息提取的工程图识别算法期刊论文-计算机辅助设计与图形学学报2002,14(1)5.沈萌红.崔云峰 基于节点的曲线图表矢量化算法研究期刊论文-计算机工程与应用2004,40(1)6.宋晓宇.王永会.Song Xiaoyu.Wang Yonghui 工程图自动矢量化算法的研究期刊论文-计算机工程与应用2000,36(3)7.康兰.赵文.KANG Lan.ZHAO Wen 基于散乱数据点的B样条曲线反求方法期刊论文-机械设计与制造2009(9)8.宋晓宇.何斌.王永会 拓扑关系在图形对象表示与识别中的应用期刊论文-计算机工程与应用2010,46(10)引证文献(9条)引证文献(9条)1.王勇.李朝奎 线性要素栅格数据矢量化快速简便算法设计与实现期刊论文-测绘工程 2009(5)2.张欣.陈国雄.钟耳顺 优化栅格细化算法的线状地物提取期刊论文-地球信息科学 2007(3)3.邢科礼.纪铭.金侠杰.张国贤 一种液压泵/液压马达特性曲线的绘制方法期刊论文-机床与液压 2006(1)4.赵国成.孙群.安晓亚.陈焕新 一种从彩色扫描图像上提取等高线的方法期刊论文-测绘通报 2011(4)5.史桂娴.张平 栅格图像矢量化方法及其研究进展期刊论文-电脑知识与技术 2008(33)6.安如.张琴.丁贤荣.王船海 长江河道AutoCAD数据转换为GIS数据的方法期刊论文-河海大学学报（自然科学版）2009(5)7.刘人午.李燕 扫描细化算法的地图自动矢量化研究期刊论文-测绘学报 2012(2)8.刘春梅 彩色军事地图等高线的识别与矢量化问题研究学位论文硕士 20059.李海燕 军用地图扫描图像数字处理算法的研究学位论文硕士 2005 本文链接：http:/