【摘 要】文章通過分析傳統(tǒng)的8鄰域曲線追蹤算法在處理未完全細(xì)化的細(xì)曲線時存在的幾個方面的問題，對柵格像元的4鄰域和對角鄰域像元的搜索順序區(qū)別對待，提出一種基于m鄰域的曲線追蹤算法，通過實(shí)驗(yàn)驗(yàn)證，該算法在解決基于8鄰接追蹤算法中存在的坐標(biāo)亂序和二義性的問題上具有較好的效果。

【關(guān)鍵詞】m鄰域 8鄰域 細(xì)曲線 追蹤

一、引言

空間數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)一般有柵格數(shù)據(jù)結(jié)構(gòu)和矢量數(shù)據(jù)結(jié)構(gòu)兩種，我們身邊經(jīng)常接觸到的多為柵格形式的數(shù)字化數(shù)據(jù)，如相片，掃描后獲得的圖片等，柵格數(shù)據(jù)具有內(nèi)容豐富，形象逼真，易于加工處理等優(yōu)點(diǎn)，但是它的缺點(diǎn)也是顯著的，例如數(shù)據(jù)量大，表達(dá)精度低，不便于進(jìn)行相關(guān)理論分析等，因此我們常常將柵格形式的數(shù)據(jù)轉(zhuǎn)化為矢量形式的數(shù)據(jù)，如將數(shù)字化后的地形圖再進(jìn)行矢量化。

以地形圖為例，圖上的要素可分為點(diǎn)、線、面三種要素，而線狀要素又是這其中的主要特征要素，因此，如何將線狀要素準(zhǔn)確的、有序的更要無二義的以有序坐標(biāo)形式提取出來，就成為矢量化線狀要素的關(guān)鍵。

傳統(tǒng)的線狀地物矢量化方法是通過對線狀地物先進(jìn)行細(xì)化，利用各種細(xì)化算法將粗線條的線狀地物處理成單像元寬度且像元8鄰域內(nèi)連通像元塊數(shù)大于1的線狀骨架線，然后采用基于8鄰域追蹤算法追蹤骨架線像元并記錄其坐標(biāo)，由于處理后的曲線像元間聚集程度較低，所以該追蹤方法處理此類問題并無較大問題。

本文所處理的線狀對象是單像元寬度且像元8鄰域內(nèi)連通像元塊數(shù)大于等于1的細(xì)曲線，因此在采用傳統(tǒng)的基于8鄰域的追蹤算法追蹤曲線則會出現(xiàn)一系列問題。在此提出一種基于m鄰接的線追蹤算法，該算法很好的解決了基于8鄰域追蹤算法中存在的坐標(biāo)亂序和二義性的問題，并能解決一些圖塊節(jié)點(diǎn)的追蹤問題。

二、幾個基本概念

三、現(xiàn)有算法的缺陷及原因分析

傳統(tǒng)的基于8鄰域追蹤算法是從起始像元開始，按圖3或圖4的搜索順序搜索該像元的8鄰域，將搜索到的第一個像元作為下一次搜索的中心，并將已搜索過的像元置為背景色。實(shí)際中常常遇到未完全細(xì)化或手工繪制的細(xì)曲線，其典型特征是線上一些像元的連通度等于1，因此在使用該算法處理這類曲線時往往會出現(xiàn)如下一些問題。

參考文獻(xiàn)：

[1] 張昊，徐剛.基于四鄰域的二值圖像細(xì)化算法[J].信息技術(shù)與信息化，2004，06：24-27.

[2] 郭繼茹，馮晅，王俊祥，等. 最佳路徑射線追蹤算法研究[J]. 吉林大學(xué)學(xué)報（地球科學(xué)版），2008，38：72-75.

[3] 張釙，劉洪，李幼銘. 射線追蹤方法的發(fā)展現(xiàn)狀[J]. 地球物理學(xué)進(jìn)展，2000，15（1）：36-44.