基于轮廓跟踪及Douglas-Peucker算法的正射影像有效范围确定

吴珍丽

(中铁大桥勘测设计院集团有限公司，湖北 武汉 430050)

基于轮廓跟踪及Douglas-Peucker算法的正射影像有效范围确定

吴珍丽*

(中铁大桥勘测设计院集团有限公司，湖北 武汉 430050)

由于影像数据文件在计算机存储的限制，正射纠正后影像四周会存在一些无效像素区域，通常采用最小的灰度级或最大灰度级填充，这些无效像素区域包含在正射影像的范围内，会对后续镶嵌处理造成影响。为了排除这种无效像素区域的影响，本文首先采用轮廓跟踪算法获得正射影像有效范围的外轮廓点集，然后采用道格拉斯-普克(Douglas-Peucker)算法对获得的外轮廓点集进行简化，剔除外轮廓点集中大量冗余点，从而获得简化后的正射影像有效范围。

正射影像；有效范围；轮廓跟踪；道格拉斯-普克算法

1 引 言

正射影像作为摄影测量与遥感最重要的基础数据产品，是制作地形图、建立基础信息数据库的基础，由于能直观反映地表状况，被广泛应用于城市规划、国土资源调查、地表覆盖变化监测、应急救灾等领域。

正射影像一般是由航空或航天遥感平台获取的遥感影像数据经过正射纠正处理得到的。在进行正射纠正的过程中通常会进行一定的旋转处理或者存在一定程度的DEM数据缺失。由于影像数据文件必须按矩形存储，因此正射纠正后的影像(即正射影像)中通常存在一些无效像素区域，一般用最小的灰度级或最大灰度级填充(对于8位影像，即用0或者255来进行填充)。这样得到的正射影像四周会存在一些无效像素区域，即没有被影像内容所覆盖的区域。这些无效像素区域包含在正射影像的范围内，会对后续镶嵌处理造成影响。如果镶嵌处理过程中生成的接缝线落入正射影像的无效像素区域，则最终得到的镶嵌结果中也存在一些不被影像内容所覆盖的无效像素区域，使镶嵌结果不能反映地物的真实情况。因此在进行正射影像的镶嵌处理时，有必要确定正射影像的有效范围，即将正射纠正引入的无效像素区域排除，获得正射影像的有效像素区域。

本文首先采用轮廓跟踪算法获得正射影像有效范围的外轮廓点集，然后采用道格拉斯-普克算法对获得的外轮廓点集进行简化，剔除外轮廓点集中大量冗余点，从而获得简化后的正射影像有效范围。

2 获取外轮廓点集

正射影像有效范围的外轮廓点集是采用轮廓跟踪方法实现的，其基本思想是，先根据一定的探测准则找出第一个正射影像有效范围外轮廓上的像素点，再根据外轮廓像素的特征用一定的跟踪准则找出外轮廓上的其他像素。

(1)首先找到第一个外轮廓上的像素点，即第一个边界点。对每幅影像按照从左到右，从下到上的顺序搜索，找到第一个有效的像素点，该点为最左下方的边界点(探测准则)；

(2)从最左下方的边界点开始，定义初始的搜索方向为左上方；搜索在像素的8邻域进行，即一个像素点的左、左上、上、右上、右、右下、下、左下共8个方向进行搜索，相邻的搜索方向夹角为45°。如果左上方的点为有效像素点，则该点为边界点，否则搜索方向顺时针旋转45°，这样在该点的8邻域内一直找到第一个有效的像素点为止；然后把这个有效像素点作为新的边界点，在当前搜索方向的基础上逆时针旋转90°，继续用同样的方法继续搜索下一个边界点，直到返回最初的边界点为止。这些搜索得到的边界点就是该正射影像有效范围的外轮廓点集(跟踪准则)[1，2]。

轮廓跟踪算法的示意图如图1所示，图中黑色圆点(包括实心圆点、空心圆点)表示有效像素点，其中黑色实心圆点表示搜索得到的边界点。左下方的黑色实心圆点为搜索得到的第一个边界点，然后从此位置开始继续搜索，图1中的黑色实心圆点周围的箭头表示当前像素的搜索方向，根据步骤(2)依次搜索得到了多个边界点如图1中黑色实心圆点所示。为提高采集外轮廓点集的效率，可以在正射影像的缩略图上进行，当然得到外轮廓点集的精度取决于缩略图的缩小比例。对于多个波段的遥感数据，可以选取其中一个波段进行处理，也可以将多个波段合成一个波段后再进行处理。

图1 轮廓跟踪算法示意图[1]

3 简化外轮廓点集

基于轮廓跟踪算法获取的外轮廓点集可以准确表达正射影像的有效范围，但点数过多，且有大量冗余的外轮廓点。虽然在正射影像的缩略图上进行轮廓跟踪可以提高效率，但即便这样，外轮廓点集的点数也较多，仍然有大量冗余，实际上多数的正射影像有效范围是一个四边形，因此需要在保持轮廓形状的同时尽量减少轮廓上的点数。本文采用道格拉斯-普克(Douglas-Peuker)算法对获得的外轮廓点集进行简化，剔除外轮廓点集中大量冗余点，从而获得简化后的正射影像有效范围。

道格拉斯-普克算法是一个从整体到局部，即由粗到细的方法来确定曲线压缩后保留点的过程。其优点是具有平移、旋转的不变性。加之距离计算在执行效率方面的优势，使得该算法的应用比较普遍。该算法也是地理信息系统中经典的矢量压缩算法，因此本文选取该算法对采用轮廓跟踪算法得到的外轮廓点集数据进行简化。道格拉斯-普克算法的具体过程如下[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个角点，这也最大程度的将获得的外轮廓点集进行了简化。获得正射影像有效范围之后，就可以进行后续镶嵌处理了。

5 结 论

为了排除正射影像由于正射纠正过程引入的无效像素区域对后续镶嵌处理的影响，本文首先采用轮廓跟踪算法获得正射影像有效范围的外轮廓点集，然后采用道格拉斯-普克算法对获得的外轮廓点集进行简化，剔除外轮廓点集中大量冗余点，从而获得简化后的正射影像有效范围。通过实验表明，本文所采用的方法能有效、准确地获得正射影像的有效范围，为后续镶嵌处理奠定了基础。

[1] 何斌，马天予，王运坚等. Visaul C++数字图像处理[M]. 北京：人民邮电出版社，2001.

[2] 马瑾，陈立潮，张永梅. 轮廓跟踪与边沿检测的图像自动识别[J]. 中北大学学报·自然科学版，2006，27(5)：431～435.[3] 龚健雅. 地理信息系统基础[M]. 北京：科学出版社，2001.

[4] 杨得志，王杰臣，闾国年. 矢量数据压缩的Douglas-Peuker算法的实现与改进[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—)，女，博士，工程师，主要从事工程测量及摄影测量技术工作。 基金项目：中国中铁股份有限公司科技开发计划(2013-重点-7)