【摘 要】文章通过分析传统的8邻域曲线追踪算法在处理未完全细化的细曲线时存在的几个方面的问题，对栅格像元的4邻域和对角邻域像元的搜索顺序区别对待，提出一种基于m邻域的曲线追踪算法，通过实验验证，该算法在解决基于8邻接追踪算法中存在的坐标乱序和二义性的问题上具有较好的效果。
　　【关键词】m邻域 8邻域 细曲线 追踪
　　一、引言
　　空间数据的数据结构一般有栅格数据结构和矢量数据结构两种，我们身边经常接触到的多为栅格形式的数字化数据，如相片，扫描后获得的图片等，栅格数据具有内容丰富，形象逼真，易于加工处理等优点，但是它的缺点也是显著的，例如数据量大，表达精度低，不便于进行相关理论分析等，因此我们常常将栅格形式的数据转化为矢量形式的数据，如将数字化后的地形图再进行矢量化。
　　以地形图为例，图上的要素可分为点、线、面三种要素，而线状要素又是这其中的主要特征要素，因此，如何将线状要素准确的、有序的更要无二义的以有序坐标形式提取出来，就成为矢量化线状要素的关键。
　　传统的线状地物矢量化方法是通过对线状地物先进行细化，利用各种细化算法将粗线条的线状地物处理成单像元宽度且像元8邻域内连通像元块数大于1的线状骨架线，然后采用基于8邻域追踪算法追踪骨架线像元并记录其坐标，由于处理后的曲线像元间聚集程度较低，所以该追踪方法处理此类问题并无较大问题。
　　本文所处理的线状对象是单像元宽度且像元8邻域内连通像元块数大于等于1的细曲线，因此在采用传统的基于8邻域的追踪算法追踪曲线则会出现一系列问题。在此提出一种基于m邻接的线追踪算法，该算法很好的解决了基于8邻域追踪算法中存在的坐标乱序和二义性的问题，并能解决一些图块节点的追踪问题。
　　二、几个基本概念
　　三、现有算法的缺陷及原因分析
　　传统的基于8邻域追踪算法是从起始像元开始，按图3或图4的搜索顺序搜索该像元的8邻域，将搜索到的第一个像元作为下一次搜索的中心，并将已搜索过的像元置为背景色。实际中常常遇到未完全细化或手工绘制的细曲线，其典型特征是线上一些像元的连通度等于1，因此在使用该算法处理这类曲线时往往会出现如下一些问题。
　　参考文献：
　　[1] 张昊，徐刚.基于四邻域的二值图像细化算法[J].信息技术与信息化，2004，06：24-27.
　　[2] 郭继茹，冯晅，王俊祥，等. 最佳路径射线追踪算法研究[J]. 吉林大学学报（地球科学版），2008，38：72-75.
　　[3] 張钋，刘洪，李幼铭. 射线追踪方法的发展现状[J]. 地球物理学进展，2000，15（1）：36-44.