基于輪廓跟蹤及Douglas-Peucker算法的正射影像有效范圍確定

吳珍麗

(中鐵大橋勘測設計院集團有限公司，湖北 武漢 430050)

基于輪廓跟蹤及Douglas-Peucker算法的正射影像有效范圍確定

吳珍麗*

(中鐵大橋勘測設計院集團有限公司，湖北 武漢 430050)

由于影像數據文件在計算機存儲的限制，正射糾正后影像四周會存在一些無效像素區(qū)域，通常采用最小的灰度級或最大灰度級填充，這些無效像素區(qū)域包含在正射影像的范圍內，會對后續(xù)鑲嵌處理造成影響。為了排除這種無效像素區(qū)域的影響，本文首先采用輪廓跟蹤算法獲得正射影像有效范圍的外輪廓點集，然后采用道格拉斯-普克(Douglas-Peucker)算法對獲得的外輪廓點集進行簡化，剔除外輪廓點集中大量冗余點，從而獲得簡化后的正射影像有效范圍。

正射影像；有效范圍；輪廓跟蹤；道格拉斯-普克算法

1 引 言

正射影像作為攝影測量與遙感最重要的基礎數據產品，是制作地形圖、建立基礎信息數據庫的基礎，由于能直觀反映地表狀況，被廣泛應用于城市規(guī)劃、國土資源調查、地表覆蓋變化監(jiān)測、應急救災等領域。

正射影像一般是由航空或航天遙感平臺獲取的遙感影像數據經過正射糾正處理得到的。在進行正射糾正的過程中通常會進行一定的旋轉處理或者存在一定程度的DEM數據缺失。由于影像數據文件必須按矩形存儲，因此正射糾正后的影像(即正射影像)中通常存在一些無效像素區(qū)域，一般用最小的灰度級或最大灰度級填充(對于8位影像，即用0或者255來進行填充)。這樣得到的正射影像四周會存在一些無效像素區(qū)域，即沒有被影像內容所覆蓋的區(qū)域。這些無效像素區(qū)域包含在正射影像的范圍內，會對后續(xù)鑲嵌處理造成影響。如果鑲嵌處理過程中生成的接縫線落入正射影像的無效像素區(qū)域，則最終得到的鑲嵌結果中也存在一些不被影像內容所覆蓋的無效像素區(qū)域，使鑲嵌結果不能反映地物的真實情況。因此在進行正射影像的鑲嵌處理時，有必要確定正射影像的有效范圍，即將正射糾正引入的無效像素區(qū)域排除，獲得正射影像的有效像素區(qū)域。

本文首先采用輪廓跟蹤算法獲得正射影像有效范圍的外輪廓點集，然后采用道格拉斯-普克算法對獲得的外輪廓點集進行簡化，剔除外輪廓點集中大量冗余點，從而獲得簡化后的正射影像有效范圍。

2 獲取外輪廓點集

正射影像有效范圍的外輪廓點集是采用輪廓跟蹤方法實現(xiàn)的，其基本思想是，先根據一定的探測準則找出第一個正射影像有效范圍外輪廓上的像素點，再根據外輪廓像素的特征用一定的跟蹤準則找出外輪廓上的其他像素。

(1)首先找到第一個外輪廓上的像素點，即第一個邊界點。對每幅影像按照從左到右，從下到上的順序搜索，找到第一個有效的像素點，該點為最左下方的邊界點(探測準則)；

(2)從最左下方的邊界點開始，定義初始的搜索方向為左上方；搜索在像素的8鄰域進行，即一個像素點的左、左上、上、右上、右、右下、下、左下共8個方向進行搜索，相鄰的搜索方向夾角為45°。如果左上方的點為有效像素點，則該點為邊界點，否則搜索方向順時針旋轉45°，這樣在該點的8鄰域內一直找到第一個有效的像素點為止；然后把這個有效像素點作為新的邊界點，在當前搜索方向的基礎上逆時針旋轉90°，繼續(xù)用同樣的方法繼續(xù)搜索下一個邊界點，直到返回最初的邊界點為止。這些搜索得到的邊界點就是該正射影像有效范圍的外輪廓點集(跟蹤準則)[1，2]。

輪廓跟蹤算法的示意圖如圖1所示，圖中黑色圓點(包括實心圓點、空心圓點)表示有效像素點，其中黑色實心圓點表示搜索得到的邊界點。左下方的黑色實心圓點為搜索得到的第一個邊界點，然后從此位置開始繼續(xù)搜索，圖1中的黑色實心圓點周圍的箭頭表示當前像素的搜索方向，根據步驟(2)依次搜索得到了多個邊界點如圖1中黑色實心圓點所示。為提高采集外輪廓點集的效率，可以在正射影像的縮略圖上進行，當然得到外輪廓點集的精度取決于縮略圖的縮小比例。對于多個波段的遙感數據，可以選取其中一個波段進行處理，也可以將多個波段合成一個波段后再進行處理。

圖1 輪廓跟蹤算法示意圖[1]

3 簡化外輪廓點集

基于輪廓跟蹤算法獲取的外輪廓點集可以準確表達正射影像的有效范圍，但點數過多，且有大量冗余的外輪廓點。雖然在正射影像的縮略圖上進行輪廓跟蹤可以提高效率，但即便這樣，外輪廓點集的點數也較多，仍然有大量冗余，實際上多數的正射影像有效范圍是一個四邊形，因此需要在保持輪廓形狀的同時盡量減少輪廓上的點數。本文采用道格拉斯-普克(Douglas-Peuker)算法對獲得的外輪廓點集進行簡化，剔除外輪廓點集中大量冗余點，從而獲得簡化后的正射影像有效范圍。

道格拉斯-普克算法是一個從整體到局部，即由粗到細的方法來確定曲線壓縮后保留點的過程。其優(yōu)點是具有平移、旋轉的不變性。加之距離計算在執(zhí)行效率方面的優(yōu)勢，使得該算法的應用比較普遍。該算法也是地理信息系統(tǒng)中經典的矢量壓縮算法，因此本文選取該算法對采用輪廓跟蹤算法得到的外輪廓點集數據進行簡化。道格拉斯-普克算法的具體過程如下[3～5]；

(1)確定距離閥值D；

(2)連接點集首尾端點構成線段，在點集中搜索離該線段距離最遠的點，并記錄其到連線的距離dmax；

若dmax≤D，則將這條曲線上的中間點全部舍去，該直線段作為曲線的近似，該段曲線處理完畢；

若dmax>D，則保留該最遠點，并以該點為界，把曲線分為兩部分，對這兩部分重復步驟(2)并依此類推。

該算法壓縮簡化精度與距離閥值有關。閥值越大，簡化程度越大，點減少得越多；反之，簡化程度越低，點保留得越多，形狀也越趨于原曲線。其算法示意如圖2所示，在曲線首尾兩點間虛連一條直線，求出其余各點到該直線的距離(如圖2(a))；然后選擇其最大者與閾值相比較，若大于閾值，則離該直線距離最大的點保留，否則將直線兩端點間各點全部舍去，如圖2(b)，第4點保留；依據所保留的點，將已知曲線分成兩部分處理，重復第1、2步操作，迭代操作，即仍選距離最大者與閾值比較，依次取舍，直到無點可舍去，最后得到滿足給定精度限差的曲線點坐標，如圖2(c)、圖2(d)依次保留第6點、第7點，舍去其他點，即完成該曲線的簡化。

圖2 道格拉斯-普克算法示意圖

4 實 驗

為了驗證本文所采用算法在進行正射影像有效范圍確定時的效果，分別用無人機及航空影像為數據源的正射影像進行了實驗。實驗數據均為彩色影像，在獲取外輪廓點集的過程中進行輪廓跟蹤時選擇了其中的一個波段進行的。

圖3 無人機正射影像有效范圍確定

圖4 DMC正射影像有效范圍確定

圖3顯示了一個無人機正射影像有效范圍確定的實驗情況。圖3(a)是正射影像，影像大小為 5 460×6 886，在對該影像進行輪廓跟蹤時獲得了 13 774個輪廓點，然后在采用道格拉斯-普克算法進行簡化的時候，閾值取3，最后輪廓點簡化為4個點，圖3(b)是簡化后的正射影像有效范圍示意圖。圖4顯示了一個DMC正射影像有效范圍確定的實驗情況。圖4(a)是正射影像，影像大小為 15 944×11 332，在對該影像進行輪廓跟蹤時獲得了 22 666個輪廓點，然后在采用道格拉斯-普克算法進行簡化的時候，閾值同樣取3，最后輪廓點簡化為4個點，圖4(b)是簡化后的正射影像有效范圍示意圖。通過實驗表明，本文分別采用輪廓跟蹤算法以及道格拉斯-普克算法來確定正射影像的有效范圍是切實可行、有效的。試驗中均準確的獲得了正射影像的有效范圍，并將其簡化為了4個點，也就是4個角點，這也最大程度的將獲得的外輪廓點集進行了簡化。獲得正射影像有效范圍之后，就可以進行后續(xù)鑲嵌處理了。

5 結 論

為了排除正射影像由于正射糾正過程引入的無效像素區(qū)域對后續(xù)鑲嵌處理的影響，本文首先采用輪廓跟蹤算法獲得正射影像有效范圍的外輪廓點集，然后采用道格拉斯-普克算法對獲得的外輪廓點集進行簡化，剔除外輪廓點集中大量冗余點，從而獲得簡化后的正射影像有效范圍。通過實驗表明，本文所采用的方法能有效、準確地獲得正射影像的有效范圍，為后續(xù)鑲嵌處理奠定了基礎。

[1] 何斌，馬天予，王運堅等. Visaul C++數字圖像處理[M]. 北京：人民郵電出版社，2001.

[2] 馬瑾，陳立潮，張永梅. 輪廓跟蹤與邊沿檢測的圖像自動識別[J]. 中北大學學報·自然科學版，2006，27(5)：431～435.[3] 龔健雅. 地理信息系統(tǒng)基礎[M]. 北京：科學出版社，2001.

[4] 楊得志，王杰臣，閭國年. 矢量數據壓縮的Douglas-Peuker算法的實現(xiàn)與改進[J]. 測繪通報，2002(7)：18～19，22.[5] Douglas D，Peucker T. Algorithms For the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J]，The Canadian Cartographer，1973，10(2)：112～122.

The Determination of Valid Scope for Orthoimage Based on Contour Tracking and Dougla-Peucker Algorithm

Wu Zhenli

(China Railway Major Bridge Reconnaissance & Design Institute Co.，Ltd.，Wuhan 430050，China)

In orthorectification for remote sensed images，there are usually some invalid pixel regions which are filled by minimum or maximum gray levels. The invalid pixel regions in orthoimage are harmful to the following mosaic processing. In order to avoid the influence of invalid pixel regions，this paper first uses contour tracking algorithm to obtain the outer contour point set of orthoimage's valid scope. Then Douglas-Peucker algorithm is adopted to simplify the outer contour point set and obtain the final orthoimage's valid scope.

orthoimage；valid scope；contour tracking；douglas-peucker algorithm

1672-8262(2017)02-102-04

P231，TP751

A

2016—03—11

吳珍麗(1984—)，女，博士，工程師，主要從事工程測量及攝影測量技術工作。 基金項目：中國中鐵股份有限公司科技開發(fā)計劃(2013-重點-7)