吳珍麗

(中鐵大橋勘測設(shè)計(jì)院集團(tuán)有限公司，湖北 武漢 430050)

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

吳珍麗*

(中鐵大橋勘測設(shè)計(jì)院集團(tuán)有限公司，湖北 武漢 430050)

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

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

1 引 言

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

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

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

2 獲取外輪廓點(diǎn)集

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

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

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

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

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

3 簡化外輪廓點(diǎn)集

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

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

(1)確定距離閥值D；

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

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

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

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

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

4 實(shí) 驗(yàn)

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

圖3 無人機(jī)正射影像有效范圍確定

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

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

5 結(jié) 論

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

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

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

[4] 楊得志，王杰臣，閭國年. 矢量數(shù)據(jù)壓縮的Douglas-Peuker算法的實(shí)現(xiàn)與改進(jìn)[J]. 測繪通報(bào)，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—)，女，博士，工程師，主要從事工程測量及攝影測量技術(shù)工作。 基金項(xiàng)目：中國中鐵股份有限公司科技開發(fā)計(jì)劃(2013-重點(diǎn)-7)