杨阿华,张 强,常 鑫,赵 斐
(北京跟踪与通信技术研究所,北京 100094)
近年来,随着航天和传感器技术的飞速发展,对地观测卫星的空间分辨率、光谱分辨率、时空覆盖率等不断提高,形成了多层次、多维度、多手段对地观测体系[1],卫星遥感数据井喷式增长,对遥感数据地面处理系统提出了极高要求和极大挑战。
在遥感数据存储、处理和产品生产过程中,一是由于遥感影像数据量极大,导致处理时资源开销大、时间长,影响了遥感影像处理效率,制约了产品时效;二是由于重复下传、重复观测、传输误码、气象因素等原因,卫星地面站接收回传的原始遥感影像数据存在重复、损坏、成像质量差等问题,导致数据的无效存储和处理;三是遥感数据来源广,不同服务商生产的数据,其存储形式、编目数据格式等不尽相同,导致检测相似重复数据存在难度,同时,数据源的多样性进一步增加了数据相似重复的概率。因此,有必要针对原始遥感影像数据进行清洗,删除重复、低质量数据等脏数据,进而降低数据存储开销,减小遥感数据后处理工作量,最终提高遥感数据处理效率和存储利用率。
国内外学者针对航天遥感影像数据相似重复清洗做了大量研究。主要分为:1)通过对遥感影像编目数据进行分析,进而确定相似重复影像的检测算法,例如采用基于密度的空间聚类算法(density-based spatial clustering of applications with noise,DBSCAN)[2-4],实现对数据的相似重复检测。该方法简单、高效,但存在影像编目数据相似而编目数据对应的实体影像并不一定相似重复的问题,不具备直接删除的条件。例如,由于数据源不同或生产处理的原因,相似重复影像中含有不同的感兴趣区域,或影像缺块现象不同等,若直接删除相似重复数据,会造成有用数据丢失。2)通过图像匹配算法进行相似重复检测[5],但是航天遥感影像数据量庞大,直接基于图像匹配对库中的实体影像数据进行相似重复检测,处理开销大、效率低。
本文方法将改进的DBSCAN 相似重复记录检测与图像匹配相结合,首先基于航天遥感影像编目数据进行相似重复检测,缩小数据清洗的范围,确定可能的相似重复影像;然后对潜在的相似重复影像做图像匹配,实现相似重复影像的确判;最后,通过质量评价对影像进行分级,根据清洗策略确定影像的去留,从而实现高效准确清洗。本文的创新之处在于改进了DBSCAN 算法及基于特征的影像匹配方法,并基于遥感编目数据和原始影像数据,将数据聚类、影像匹配、影像质量评价3 种方法组合、顺序运用,解决了原始遥感数据高效、准确清洗的问题。
航天遥感影像数据清洗处理流程如图1 所示,具体流程如下。
Step 1 利用改进的DBSCAN 算法,对编目数据集进行相似重复检测,即:对同一类型传感器获取的数据,将观测时间或影像地理位置相似的数据记录检测出来,作为潜在相似重复记录集。
Step 2 对Step 1 检测出的记录所对应的实体遥感影像,采用Harris 角点与SIFT 特征相结合的方式进行图像匹配,进而得到相似重复影像的匹配率。
Step 3 若匹配率大于90%,则确定两幅影像为相似重复,需通过Step 4 进一步处理;否则保留两幅影像,并进行标注。
Step 4 对相似重复影像进行质量评价,根据评价结果,依据清洗规则,对相似重复影像进行去重或标注,同时更新编目数据。
1.2.1 改进的DBSCAN 相似重复记录检测
由于航天遥感数据源的多样性,不同来源的数据,其编目数据的格式不尽相同,若直接通过属性比较来检测相似重复记录,一是需要将数据进行规范化处理,二是两两比较代价较大,效率较低。因此,本文采用聚类的思想,基于DBSCAN 算法将编目数据划分为多个类,再检测其中的相似重复记录。
ESTER M 等提出的DBSCAN (density-based spatial clustering of applications with noise)是一个基于密度的空间聚类算法[6-7],该算法将具有足够高密度的区域划分为簇,并可在带有“噪声”的数据中发现任意形状的聚类。研究人员使用该方法对数据集进行聚类,以发现数据集中的相似重复记录。
针对传统的DBSCAN 算法对密集度不均匀的多密度数据集聚类质量较差的问题,本文采用一种改进的DBSCAN 算法,进行相似重复检测。算法相关定义如下:
1)ε 邻域
ε 邻域是指在对象a 的半径ε 范围内的点的集合,表示为Nε(a)。
2)核心对象
如果数据对象a 满足|Nε(a)|≥MinPts,则a 为核心对象。
3)密度直达
在数据集D 内,若数据对象u 在核心对象a 的邻域内,那么数据对象u 直接密度可达核心对象a。
4)密度可达
如果存在核心对象p1、p2、…、pn,且p1到p2密度直达,p2到p3密度直达,…,p(n-1)到pn密度直达,pn到q 密度直达,则p1到q 密度可达。
5)密度相连
如果存在核心对象a,使得a 到p 和q 都密度可达,则p 和q 密度相连。密度相连的两个点属于同一个聚类簇。
改进的DBSCAN 算法步骤:
输入:数据集D(航天遥感编目数据集),参数ε和MinPts。
输出:相似重复数据集C'。
Step 1:从D 中找出一个核心对象a,然后查找a 的ε 邻域,标记为C1聚类集合,并加入W 队列中。
Step 2:遍历D 中的所有数据对象,若与W 中的对象密度相连,则将该数据对象加入W 队列中,并标记为C1。
Step 3:重复Step 2,直至没有新的对象加入W 中。
Step 4:从D 中未标记的数据对象中查找核心对象,若存在,则重新执行Step 1、Step 2、Step 3;否则增加ε,继续Step 4。
Step 5:将没有被标记的点标注为奇异点。
通过上述过程,得到该数据集的聚类集合列表,即将数据集中相似重复数据进行了聚类归堆。
传统的DBSCAN 算法,用户需要输入邻域半径,如果半径过大,类中会含有噪声;半径过小,数据距离过大的类将无法识别,影响识别质量。改进的算法借助密度相连,可获得数据集中每个类的聚类集合;同时,可基于数据自身情况灵活调整ε 的大小,提高聚类准确度。
在聚类过程中需要对记录之间的相似度进行计算。针对计算记录相似度耗时较长的问题,采用欧几里得距离公式计算记录间的相似度[6]。
其中,d 是记录a 与b 之间的距离,ai、bi分别是a 与b 的第i 个属性值,D 是两个记录中的属性集合。
基于上述改进的DBSCAN 算法进行相似重复记录检测,处理流程如图2 所示。
图2 相似重复记录检测流程图Fig.2 Flowchart of detecting similar duplication records
相似重复记录检测步骤如下:
输入:数据集Y(编目数据集),参数ε 和MinPts。
输出:相似重复数据记录T'。
Step 1:对编目数据记录中的字段进行筛选,获取相关字段。
Step 2:基于改进的DBSCAN 算法对数据集进行聚类,得到多个数据类。
Step 3:利用pair-wise 算法分别对各类中的记录进行相似度计算[8],根据相似度确定最终的相似重复记录,作为下一步影像匹配的输入。
需要说明的是,在上述过程中,利用改进的DBSCAN 算法将潜在的相似重复记录聚在一个类后,再通过pair-wise 算法对各类进行再聚类,可以很好地解决由于字段位置不一致而造成的错误聚类,提高了检测的准确性。
1.2.2 基于Harris 角点与SIFT 特征的影像相似重复检测
基于前面检测出的潜在相似重复编目数据对应的两幅实体影像,采用Harris 角点检测算法提取影像角点[9-10],在角点邻域范围内提取出SIFT 特征点[11],并利用高斯尺度空间函数对特征点进行筛选,以此为基础进行特征匹配。基于匹配结果进行匹配率检测,当匹配率大于90%时,确认为相似重复影像。上述过程包括:特征点检测、特征点筛选、特征点匹配、匹配率计算4 个步骤,分别介绍如下。
1)特征点检测
Harris 角点提取过程如下。
图像窗口平移产生的灰度变化为E(u,v):
其中,w(x,y)是用来滤波的高斯函数。对于局部的微小移动量[u,v],近似表达式为:
M 可由图像的导数求得:
像素点的响应函数F 的计算方法为:
当F 大于一定阈值时,则认为此像素为角点。
以Harris 角点为中心,r 为半径,筛选图像的SIFT 特征点。通常情况下半径r 的计算公式为:
其中,δoct为Harris 角点所在的尺度,将不在Harris角点一定范围内的点删除,从而使留下的点具备较高的稳定性和旋转不变性。同时利用128 维特征描述子,提高匹配的准确率。
2)特征点筛选
采用上述特征点检测方法会不可避免出现特征信息少的特征点,从而导致后续特征匹配时的误匹配。因此,需要对提取到的特征点进行筛选,删除特征信息少、纹理单一的特征点,保留纹理信息丰富的特征点。将图像的高斯尺度空间函数L(x,y,δ)在特征点(x0,y0,δ)处进行泰勒展开,如式(7)所示:
对式(7)进行求导,并令L(x,y,δ)为0,得到特征点的精确位置:
3)特征点匹配
利用最近绝对值距离与次近绝对值距离的比值作为匹配依据。通过欧式距离计算出待匹配图像中每个特征点描述子与参考图像中所有特征点的欧式距离。当欧式距离小于设定阈值时,被定义为潜在匹配点对。本文阈值设置为0.8。若某一待匹配点的欧式距离小于阈值,且该点的最近绝对值距离与次近绝对值距离的比值满足要求,则认为对应的最近绝对距离点为该点的匹配点。
4)匹配率计算
特征点匹配完后进行匹配率计算,匹配率计算公式如式(10)所示:
其中,n1和n2分别是参考图像与待匹配图像中检测到的特征点数量,n3是检测到的正确匹配点对。
当匹配率大于等于90%时,则认为两幅影像相似重复,需要进行影像质量评价,以进一步确定清洗策略;若小于90%,则认为非相似重复,保留两幅影像,并分别标注为非相似重复影像。
完成数据的相似重复检测后,还需对检测出的相似重复影像进行质量评价,以确定最终的清洗策略。国内外学者针对遥感影像质量评价进行了深入研究,文献[12]利用Contourlet-SSIM 视觉模型对遥感图像质量进行评价,结果表明Contourlet-SSIM 模型可较为可靠地评价IKONOS 图像质量。文献[13]提出了一种将图像的梯度幅值、相位及结构相似度相结合的图像质量评价模型,解决了传统模型对严重失真图像的客观评价与主观感受不符的问题。美国通过建立图像质量的间接评价标准-国家图像解译度分级标准,进而实现遥感影像的自动评价[14-15]。
本文综合运用上述文献中的方法,基于位置精度、噪音、信息丢失、色彩特征、色彩模式等指标,对影像进行评分。下页表1 和表2 分别为影像质量评分规则和等级评定标准。
表1 影像质量评分规则Table 1 Rules for image quality scoring
表2 影像质量等级评定标准Table 2 Evaluation standards of image quality grades
本文方法采用的相似重复影像清洗规则包括以下3 条:1)各相似重复影像质量合格且评分等级相同,则仅保留其中一幅影像,删除其余影像及编目数据;2)各相似重复影像质量合格且评分等级不同,则对各相似重复影像进行质量等级标注,同时合并,更新对应的编目数据;3)相似重复影像质量不合格,可将不合格影像及编目数据进行剔除。得到影像评分和质量等级后,根据上述3 条规则,确定最终的清洗策略。
采用航天对地观测大数据集进行试验。实体影像数据集包括:SAR 数据、红外数据、可见光数据等,数据量约为2 TB。编目数据共12 000 条记录,每条记录对应一幅影像,包括8 个字段,分别是:图像号、卫星号、载荷类型、轨道号、图像拍摄开始时间、图像拍摄结束时间、中心点纬度、中心点经度。
基于上述编目数据,进行基于DBSCAN 算法的相似重复记录检测实验,DBSCAN 算法的参数和阈值根据以往经验设置为:e=5,MinPts=11。分别提取上述数据集中3 000、6 000、9 000、12 000 条数据记录,检测结果如表3~表4、下页图3~图5 所示。
表3 DBSCAN 算法相似重复记录检测结果Table 3 Similar duplication record detection results of DBSCAN algorithm
表4 改进的DBSCAN 算法相似重复记录检测结果Table 4 Similar duplicate record detection results of improved DBSCAN algorithm
图3 传统和改进算法准确率比较Fig.3 Comparison of accuracy between traditional and improved algorithms
从表4 中可以看出,改进的DBSCAN 算法下相似重复记录检测的平均准确率为89.46%,说明仅依靠基于编目数据的检测过程无法确判影像为相似重复,必须在此基础上进行影像匹配来确判;平均查全率为75.31%,说明还有一部分相似重复记录没有检测出来,这是下一步需要优化的重点。从表3、表4 和图3、图4 可以看出,改进算法提高了准确率和查全率,从而增加了正确检测的相似记录数。但从图5 可以看出,采用改进算法的检测中因为增加了pair-wise 比较过程,所以用时比未改进算法多。
图4 传统和改进算法查全率比较Fig.4 Comparison of recall rates between traditional and improved algorithms
图5 传统和改进算法的处理时间比较Fig.5 Comparison of processing time between traditional and improved algorithms
综上,使用改进DBSCAN 算法检测相似重复记录比传统算法的精度有所提高,但是计算复杂度较传统方法增大,牺牲了一部分时间效率。
从基于DBSCAN 算法检测出的相似重复记录集中,选择一对编目数据对应的两幅实体影像,进行基于Harris 角点和SIFT 特征的影像匹配。图6 为两幅影像特征提取和匹配的情况,左图和右图分别提取了151 个和155 个特征点,共匹配了143 对同名点。两幅影像间的匹配率为93.4%,大于90%,说明两幅影像相似重复,需要通过质量评价确定最终的清洗策略。
图6 相似重复影像匹配结果Fig.6 Matching results of similar duplication images
针对图6 的两幅影像,采用遥感影像处理算法计算表1 中各质量指标值,进而得到各指标的评分;根据表2 的质量评定标准,左图和右图各项得分如表5 所示。
表5 影像质量评定结果Table 5 Results of image quality evaluation
最终得分左图为92.3 分,属于优,右图为55.3分,属于不合格。根据相似重复影像清洗策略,可直接删除右图,保留左图,减小后续图像处理工作量,节约存储空间。进一步观察发现,图6 右影像确实存在数据缺失的情况。
针对原始航天遥感影像中存在的相似重复和数据质量低(损坏、模糊、噪点等)的问题,本文从航天遥感数据预处理业务出发,根据航天遥感数据特点,将改进的DBSCAN 算法与基于特征的图像匹配相结合,对编目数据和实体影像进行处理,检测出相似重复数据。以此为基础,采用一系列指标对相似重复影像进行质量评价,实现对航天遥感影像数据的准确、高效清洗。
本方法利用编目数据信息对潜在相似重复影像进行初步筛选,在初筛基础上有针对性地进行影像匹配,避免了基于影像匹配的遍历搜索,极大降低了相似重复影像检测工作量。同时充分运用编目和影像信息,提高了相似重复影像检测准确率。本方法是航天遥感数据预处理的第1 步,通过综合运用编目数据聚类、图像匹配、影像质量评价3 个处理步骤,可从海量遥感影像中有效清洗掉重复、低质量影像,提高遥感数据质量,减小后续处理工作量,降低存储开销。