一種改進的基于Douglas-Peucker原理的輪廓采樣算法

摘要:文章首先介紹了Douglas-Peucker算法，它是一種經典的曲線簡化方法，在此基礎上提出了DP算法的一種非遞歸實現方法，該過程主要是利用隊和棧的性質來實現的。結果顯示，用這種方法進行目標物體的輪廓采樣，通過控制距離容差可以得到對輪廓線不同程度的逼近，不僅能夠有效減少物體輪廓的冗余點，提高處理效率，又能夠不失真地表征物體的形狀。

關鍵詞:Douglas-Peucker算法;非遞歸實現;輪廓采樣

中圖分類號:TP391文獻標識碼:A文章編號:1009-3044(2009)25-7214-03

An Improved Contour Sampling Algorithm Based on Douglas-Peucker Theory

ZHANG Zhen

(Department of Biological Science and Medical Engineering， Laboratory of Image Science and Technology， Southeast University， Nanjing 210096， China)

Abstract: This paper， first analyses the theory of Douglas-Peucker algorithm， it is a classical curve simplification method， based on it， then proposes a non-recursive implementation of DP algorithm. This process mainly uses the property of data structure queue and stack. The results show that when using this method for contour sampling， it can obtain different degrees of contour line approaching by controlling the distance tolerance， it can not only reduce the number of redundant points of contour， improve the processing efficiency， also can characterize the shape of object without distortion.

Key words: Douglas-Peucker algorithm; non-recursive implement; contour sampling

在圖像處理和計算機研究領域中，目標物體的定位一直是一個值得探討的問題，目標的準確定位對于目標識別以及圖像理解與分析起著十分重要的作用。在醫學圖像中，人體器官的大小、形狀都有較大差別;在放射治療中，呼吸作用下器官運動造成腫瘤的大小、位置發生變化，這些因素使得空間定位十分困難。主動形狀模型通過建立物體形狀的先驗模型，能夠有效解決物體定位問題，得到了廣泛的研究與應用。主動形狀模型首先要提取目標輪廓點的集合，利用提取的輪廓點，采用統計分析的方法建立點分布模型 [1，3，9]，如果用于建模的點的數目很多，會影響處理的效率。

輪廓采樣是指，在預先給定的誤差準則下，通過對原始輪廓點集合P的采樣得到一組新的輪廓點集合V，使得由V表示的輪廓盡可能逼近原始輪廓，集合V是集合P的子集。輪廓采樣可以減少冗余數據，縮短圖像處理時間，因此，輪廓采樣方法在很多領域得到了研究應用，如地理信息系統[2]，數字圖像處理，計算幾何以及數據壓縮等。

1 輪廓提取

圖像經過閾值處理成為二值圖像之后，需要對目標物體進行輪廓提取，對圖像信息進行分析，得到一個有序的、表征目標外輪廓的邊界點集合，為后面的目標輪廓采樣提供原始的輪廓曲線。

傳統的方法主要是利用經典微分算子中的卷積掩模，對圖像中每個象素進行卷積，從而檢測出目標物體邊緣，經典的微分算子包括Sobel算子、Laplace算子、Roberts算子、Prewittt算子、Robinson算子、Kirsch算子等[6]。這些利用算子進行卷積的方法計算量大，耗時多，而且最終不能得到完整的輪廓點集合。

輪廓提取是由圖像中目標區域的一個邊界點出發，搜索并連接邊界點，進而檢測出組成輪廓的所有點。輪廓提取方法的核心是如何根據當前點的情況判斷下一步的跟蹤方向，文中采用一種基于八鄰域的跟蹤算法[8]。圖像中每個點P都有8個鄰域，如圖1。判斷一個點是不是邊界點即“探測準則”是:判斷這個點的上下左右四個方向的點的象素值是不是0，如果這個點的上下左右四個方向的點的象素值都不是0，那么這個點就可以被確認為邊界點。具體方法如下:

1)首先按照上述“探測準則”，對整幅圖像按照從下到上，從左到右的順序，找到第一個邊界點，將其坐標保存到數組D中，并作為搜索的起始點;

2)在起始點的八鄰域內，從左上方向開始搜索下一個邊界點，如果這個點是邊界點，將其坐標保存到數組D中，如果這個點不是邊界點，則當前搜索方向順時針旋轉45度搜索下一個邊界點。將新搜索到的邊界點作為當前點，然后當前搜索方向逆時針旋轉90度作為新的起始搜索方向，在當前點的八鄰域內按照同樣的方法繼續搜索下一個邊界點;

3)如果新搜索到的邊界點是起始點，停止搜索。

2 輪廓采樣

獲取目標物體的輪廓之后，在一定的誤差準則下，通過對原始輪廓的采樣，去除輪廓的冗余點，以減少構成輪廓的點的數目，減少后續處理的計算量，同時要能夠準確表征物體輪廓的形狀。

常用的輪廓采樣方法有:等角度法、等步長法、曲率采樣方法、Douglas-Peucker方法。

1)等角度法:首先設定一個角度閾值θ，找到輪廓線的形心O，然后遍歷輪廓線上的每個點，找到使P1O，P2O，P3O，P4O兩兩之間連線所成夾角等于θ的點P1，P2，P3，P4，這些點即為符合采樣條件的輪廓點[4]。從圖2所示看，這種采樣方法隨時都有可能丟失輪廓的特征點，而輪廓的特征點是足以代表輪廓基本特征的最重要信息，所以這種采樣方法不能滿足要求。

圖2等角度采樣法圖3等步長采樣法圖4 曲率的定義

2)等步長法:首先設定一個步長值T，遍歷輪廓線上的每個點，使得P1P2=P2P3=P3P4=T [4]，這種采樣方法的唯一判斷標準就是預先設定的采樣步長，隨著步長增大，輪廓線上的特征點丟失的幾率也比較大;如果設定的步長較小，會采樣到一些不必要的點，造成采樣點數目增多，不能達到化簡輪廓線的目的，所以這種采樣方法也存在缺陷。

3)曲率采樣方法:假設s為曲線MN的弧長，φ是過M點的切線與x軸所成的角度，則點M的曲率可以表示為kM=dφ/ds，顯然，M點局部變化越大，則曲率越大，采樣曲率大的點能夠描述輪廓的形狀[7]。

曲率，其中“'”和“\"”分別為弧長參數的一階和二階導數。如果某一點的曲率絕對值大于閾值，或者該點的曲率是它鄰域的極大值或極小值，則采樣此點。這種方法利用曲率來采樣輪廓線，與等角度、等步長采樣法相比，能夠提高采樣效果，但是由于計算曲率比較復雜，所以也較少采用。

基于對上述輪廓采樣方法的分析，本文選用Douglas-Peucker算法，該算法能準確提取輪廓線上表征形狀的特征點，并且能夠通過控制距離容差，獲取對輪廓線不同逼近程度的采樣結果。

3 Douglas-Peucker算法

Douglas-Peucker算法是由D.Douglas和T.Peucker于1973年提出，簡稱DP算法，是公認的線狀要素簡化的經典算法。它的優點是具有平移和旋轉不變性，并且對于給定的曲線和距離容差，采樣結果一定。

DP算法的幾何原理是:曲線上任意一條弧都可用弧上的一條弦來做任意精度的逼近，并且弧上任意點到弧上弦的最大距離能夠描述這種逼近的精確程度[2]。其基本思想是:預先給定距離容差，將曲線首、末兩點連線，依次計算首尾兩點之間的所有中間點到該線段的距離，找出距離最大的點，并判斷該距離是否小于給定的距離容差，若是，則舍去所有中間點;若否，則保留該點，并以該點為界，將曲線分為兩部分，然后對這兩部分重復以上操作。當曲線被新找到的中間點分為兩部分后，將這兩部分分別作為獨立曲線重復以前的步驟[2，5，7]。

設曲線的首、末兩點P1和P2構成直線段P1P2，計算曲線上這兩點之間所有點到此直線段的距離，并找到距離最大值dmax及其對應點P3，將dmax與閾值ε作比較;若dmax>ε，則保留P3，將該段曲線以P3為界分為兩段獨立的曲線，重復上述步驟;若dmax<ε，則將曲線上首末兩點之間的所有點全部舍去，用P1P2取代該段曲線。當ε越小，采樣得到的點數越多，連接采樣點構成的多邊形曲線更加逼近原始曲線。

3.1 Douglas-Peucker 算法的常規實現過程

由以上分析可以看出，DP算法的實現步驟如下:

1)設輪廓曲線由離散點序列(p0，p1，p2，…，pn)組成，用數組D存放采樣得到的點，將起始點p0和末點pn兩點按順序存入D的首位和末位，并令p0->A，pn->B連接AB;

2)在AB之間的所有點中尋找與線段AB具有最大距離的點，若有，轉(3)，否則轉(4);

3)判斷該點到線段AB的距離是否小于給定距離容差，若否，設該點為C，并按順序存入D中，令C->B，返回(2);

4)判斷B是否為pn，若否，令B->A，pn->B，連接AB，返回(2);

5)將A，B存入特征點列D中，結束。

根據上述DP算法的實現步驟，該算法實現過程如圖6所示。

3.2 Douglas-Peucker 算法的非遞歸實現過程

從圖6中看出，DP算法是一個遞歸過程，其實現也一直采用遞歸方式，然而遞歸算法在運行時的空間時間開銷比較大，本文通過利用隊和棧的數據結構，提出該算法的一種非遞歸實現方法。在數據結構中，棧的一個重要應用就是用于在程序中實現遞歸，因此本文采用隊和棧的結構來實現Douglas-Peucker算法，下面給出具體的實現過程:

將在輪廓提取中獲取的輪廓曲線的離散點序列(p0，p1，p2，…，pn)的坐標序列存放在一個數組D中，數據存放形式采用帶索引的數據結構，并用一個隊和棧與之相配合，存放中間點的索引序號，記隊尾元素為a，棧頂元素為b。

1)將原始輪廓曲線的起點D[0]和終點D[n]，分別放入隊和棧中，此時，α=0， b=n;

2)連接D[α]和D[b]，在D[α]，D[b]之間的點尋找到直線D[α]D[b]距離最大的點，若有記為D[c]，否則轉(4);

3)判斷D[c]到D[α] D[b]的距離是否小于預先設定的距離容差T，若否，將c入棧，此時，棧頂元素為c，并將c->b，然后轉(2);

4)判斷b是否等于n，若否，將b放入隊尾，此時，隊尾元素為b，并將b->α，b'->b(b'為棧頂元素的下一個元素)，然后轉(2);

5)將b壓入隊中，隊中元素即為輪廓曲線采樣點的下標，結束。

圖7是DP算法的非遞歸實現方法的流程圖。該過程根據棧的先進后出和隊的先進先出性質來實現的，始終在棧頂點和隊尾點之間尋找采樣點，若找到則將該點壓入棧中;否則將棧頂元素壓入隊尾，直到棧為空，隊中的元素即為提取的采樣點在數組中的下標，也就是在數組中的位置。依次按照隊頭到隊尾的順序從數組中提取點列，即可得到原始輪廓曲線的采樣結果。

4 實驗與討論

本文選用頭部CT圖像的一部分如圖8所示，首先對其進行簡單的閾值分割，采用區域生長方法分割出感興趣區域，再進行輪廓跟蹤，得到組成原始輪廓的點數為234個點，應用本文提出的DP非遞歸實現方法進行輪廓采樣，當距離容差T=0.5時，采樣后輪廓點數為104點，當T=1時，采樣后輪廓點數為25，當T=2時，采樣輪廓點數為16。由圖所示可以看出，當距離容差為2時，采樣輪廓有些失真，但采樣效果依然在接受范圍之內;由表1 DP算法的遞歸實現與本文非遞歸實現的時間對比，可以看出，當距離容差為0.5和1時，該方法不僅能夠減少表示輪廓的點數，減少冗余點，還可以縮短處理時間，同時能夠不失真表達物體的輪廓。

圖8 原始圖像 圖9閾值分割 圖10 區域生長

圖11 原始輪廓(234點)圖12點數=104(T=0.5) 圖13點數=25(T=1) 圖14 點數=16(T=2)

5 總結

本文在經典的曲線簡化算法Douglas-Peucker算法的基礎上，提出了DP算法的一種非遞歸實現方法，主要是采用了隊和棧的數據結構，并根據這兩種數據結構的性質，通過保留距離最大的中間點，減少了計算和判斷操作次數，提高了算法的效率。實驗表明，通過選擇適當的距離容差，該方法能夠有效減少物體輪廓的冗余點，又能夠不失真表征物體的形狀，對于數據量較大的圖像分析與處理，還能夠縮短處理時間，減少后續步驟的計算量，具有一定的實用價值。

參考文獻:

[1] Souza A， Jayaram K. Udupa. Automatic landmark selection for active shape model[J].Medical Imaging 2005: Image Processing. Proc. of SPIE Vol.5747 (SPIE， Bellingham， WA， 2005):1377-1383.

[2] Douglas D H， Peucker T K， Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J].the Canadian Cartographer，2001，10(2):112-122.

[3] Cootes T F， Taylor C J， Cooper D H， et al. Active Shape Model-Their Training and Application[J]. Computer Vision and Image Understanding，1995，61(1):38-59.

[4] 王蔚林，王立功，于甬華，等.一種可調整步長的適應性圖像目標輪廓采樣方法[J].數據采集與處理，2004，19(1):21-27.

[5] 余珊，用于目標分割的主動形狀模型方法研究[D].合肥:中國科學技術大學，2007.

[6] 岡薩雷斯.數字圖像處理[M].2版.北京:電子工業出版社，2006:460-482.

[7] 夏仁波，劉偉軍，王越超.一種改進的基于DP原理的分段輪廓采樣算法[J].計算機工程與應用，2004(21):21-24.

[8] 求是科技.數字圖像處理典型算法及實現[M].北京:人民郵電出版社，2006:406-408.

[9] 蔡宇新，徐濤.基于ASM的圖像中二維物體的定位方法研究[J].計算機應用，2003，6(23):191-194.