2. 北京理工大学 深圳研究院, 广东 深圳 518057
2. Shenzhen Research Institute, Beijing Institute of Technology, Shenzhen 518057, Guangdong, P. R. China
在获取的高分辨率遥感影像中,线状目标是一类非常重要的大型人造目标,如机场跑道、高速公路、桥梁等,这类目标于有别于自然背景最重要的特点是呈现出平行的长直线状的几何形态[1]。由于这类目标通常意味着周围出现其它人工目标 (如飞机、车辆) 的可能性很大,因此这类具有长直线状的目标对其它人工目标的检测与识别具有重要意义[2]。
在大多数情况下,目标检测的方法是先找出其边缘,然后根据目标的其他特征 (如形状、纹理、强度等) 来改善检测结果。Hough变换 (Hough Transform) 是一种非常有效的直线或圆目标的检测方法[3, 4],它是一种使用表决原理的参数估计技术,在整个图像范围内将有一定关系的像元进行聚类,并在新定义的参数空间中找寻能与像元用解析表达式相联系的对应点,最后在参数空间进行累加统计,统计值作为图像中目标存在与否的凭据。由于它利用局部特征对所有可能的直线投票,故在噪声图像中提取直线具有较强的鲁棒性[1, 3]。
然而Hough变换的缺点是其计算复杂度会随着图像分辨率及内存呈线性增长,在大画幅、高分辨率的遥感图像中检测速度很慢。过去的20多年中,有一系列改进的算法被提出来减小计算复杂度,如:随机Hough变换 (Random Hough Transform, RHT)[4, 5]、自适应Hough变换 (Adaptive Hough Transform, AHT)[6]、快速Hough变换 (Fast Hough Transform, FHT)[7]、多分辨率Hough变换 (Multi-resolution Hough Transform, MHT)[8]、概率Hough变换 (Probabilistic Hough Transform, PHT)[9]等,其中PHT是多对一映射的变换,它不是对图像空间所有的像素点进行遍历,而是选择性地对点进行Hough变换,因此在一定程度上提高了计算效率[10]。
由于PHT变换是对整幅图像的像素点进行投票,而遥感图像尺度通常很大,地物背景十分复杂,感兴趣目标所占的比例通常很小,因此线状目标在累加矩阵中的比例远远小于背景,很容易淹没在背景之中,难以检测出来[11]。有鉴于此,本文对PHT进行了改进,其基本思想是将原图分割成较小的块,再通过对每个子块图像进行边缘检测后,对边缘部分进行PHT变换以有效地提取出直线。
1 基于改进的PTH变换提取直线目标的方法在Hough变换中,图形边缘M的每个像素点 (xi, yi) 被映射到一个代表正弦曲线投票模式的Nθ×Nρ的累加器矩阵,它描绘了一个标准的 (θ, ρ) 参数平面,代表所有可能通过该像素点的直线,其中,ρ是离原点的距离,θ是直线的方向[3]。
(1) |
对应于同一条直线上的所有像素点的正弦曲线在参数空间中交于理想的一个点,这在累加器矩阵中会达到一个峰值。
由于遥感图像尺度通常较大而且内容复杂,感兴趣的目标很容易淹没在背景之中。在这样的图像中,直接使用Hough变换提取直线是不实际的。如图 1所示,本文提出了基于改进的PHT变换的方法来检测遥感图像中的线性目标。具体步骤如下:首先将输入的原始遥感图像分成许多小块子图像,再对每个子图像进行PHT变换,分割得到许多短直线簇,由于这些短直线簇往往在方向性和位置分布上有一些相近的特性[12],因此可以通过把具有相同方向和位置的线段聚类后,再把每个聚类的集合投影到与其朝向正交的方向上,这样最显著的平行直线就容易被检测出来了,最后再进一步判断这些平行直线的特征是否与感兴趣的目标特征符合。
如果需要在遥感图像中检测直线目标,图像首先要被分割为许多子图像,其宽度应比感兴趣的目标长度小。对小部分进行Hough变换而不是整个图像,可以减小累加器的尺寸,从而减少内存的花费。分块带来的另一个好处是边缘检测的阈值能在不同子图模块范围内变化,因此在局部区域内灰度高而在整个图像中又相对较低的边缘,也能够被检测到,避免了全局阈值的单一性造成部分形态不突出的直线被漏检。
本文对图像分块的长宽尺寸大约为感兴趣目标长度的1/5。此外,如果直线刚好通过子块的四个边角区域,则容易在分块时被切割得过短,因此分块后的相邻子图间要有部分区域重合,本文中约定每一块与相邻块都有1/3的重合区域,以保证直线不会被漏检。由此得到一个Pi, j(i∈[0, s-1], j∈[0, t-1]) 的子图像阵列,s和t分别是子图像阵列的行数和列数。
1.2 PHT图像分割处理PHT变换与标准Hough变换相似,但PHT变换仅仅使用了一个像素点子集m,而不是M所有的点,其中m能代表所在图像区域的噪声和其它特征。由于m < M,投票阶段的复杂度将从o(M, Nθ) 减小到o(m, Nθ)。对M随机选择的子集m可以给它赋一个较低的投票阈值 (但又不至于小到特征不能被检测到),这样可以在确保检测能力的前提下,大大加快运算速度[9]。为此,在对子图进行PHT变换前,我们使用了Canny边缘检测器[10]检测每个子图像的边缘,其中检测阈值设置的规则是:首先计算出子图像pi, j的梯度,再计算出梯度直方图Hi, j(g),假定有P%的像素是边缘,高阈值可设置为gt,满足式 (2):
(2) |
式中的N是子图像pi, j中的总的像素数,一般取P%=0.7%,低阈值为高阈值的0.4倍。最后,对每个子图像进行PHT变换,分割提取到Ci, j条线段Li, j, k(k∈(0, Ci, j))。
1.3 平行线段的提取经过PHT变换后,提取出大量的短线段,其中有的属于真正目标的长直线部分,有的只是背景噪声或者弧线的部分,这类线段的方向位置等都具有随机性,难以在附近找到相似的线段[13]。我们所提出的改进手段是根据所提取线段的方向与位置进行聚类,去除较小的类,并提取连接剩下的线段成为平行直线。具体做法如下:
首先,设置两个阈值。一个是Amax,表示两条直线间最大的夹角,另一个是Dmax,表示两条直线的最大距离。因为Amax很小,所以可以用平行直线距离公式来确定两条直线l1、l2的距离 (D(l1, l2))。
然后,建立一个无向图G(V, E),其顶点是所有检测到的短线段:
(3) |
G的边是满足要求Dmax和Amax的相邻的或同一子图像中的线段对,可以用式 (4) 描述:
(4) |
式 (4) 中的R是最远的相邻子图像间的距离,可由实验决定。G根据其连接性,通过遍历划Ng个子图Gi(i=0, …, Ng),任意两个子图间都没有连接,且任意子图内部都相互连接。这样相邻的平行线就被放在一个子图里了。
对于像机场和高速公路这样的长线状目标拥有两条平行的长边缘,它们的梯度方向是相反的。每个子图Gi(i=0…Ng) 可以根据直线的梯度方向,分为梯度正好相反的两个子图Gi+和Gi-,可以发现目标的两条边缘分别在这两组里。
感兴趣的线性目标的几何尺寸,通常都在一个有限的范围内,可以设定感兴趣的目标的长度和宽度范围 ([Lmin, Lmax]和[Dmin, Dmax]) 以排除不可能的直线。首先,根据每个子图Gi+和Gi-中线段到原点的距离ρ(可以把子图的平均方向θi及各条线段的中点代入方程 (1) 计算得到ρ) 建立两个直方图hi+(ρ) 和hi-(ρ)。
如果在ρpeak+和ρpeak-处存在一对峰值hi+(ρpeak+) 和hi-(ρpeak-),它们分别满足条件 (5)、(6):
(5) |
(6) |
就把所有Gi+中到L+的距离小于一定的阈值的线段连起来。线段AB到直线L+的距离能够被定义为线段上所有点到直线的平均距离:
(7) |
(8) |
(x1, y1)、(x2, y2) 是线段AB的两个端点。然后把Gi-中的直线同样连接起来,就得到线状目标可能的两条边缘。
1.4 平行线对筛选处理通过目标几何尺寸的先验知识约束,可以过滤掉许多短直线的干扰,提取出可能包含目标的平行线对,再进一步利用其他一些特征对平行线对进行筛选,使检测更加精确。
以跑道为例,其相对于背景更亮和更平滑的表面特征,以及高宽比能被用于改善检测。如果在平行线之间的区域能满足以下3条标准,那么该线对可以被认为是跑道的边缘:1) 较周围背景亮;2) 跑道的纹理平滑,直方图较集中;3) 合适的长宽比。
2 实验验证实验使用SPOT-5卫星的遥感影像切片,其地元分辨率2.5 m,画幅为2000×2000,如图 2(a)所示。由于机场建在郊区,背景范围大且较为复杂,机场只占整个图像的一小部分,而且含有大量具有直线特征的农田、河流等容易干扰检测。
图 2(b)和(c)分别给出了按照1.2节分块子图像和整幅图像进行PHT变换后的分割效果。显然,当PHT变换用于整幅图像,仅能提取到跑道的部分边缘并且不连续,大多数短边缘未被检测到,并且还提取了许多无意义的短线段。而对分块子图的PHT变换结果表明,线段和边缘啮合很好且连续,而且大多数短边缘也都能被检测到。图 2(d)给出了对分块PHT变换结果进行聚类之后的效果,显然,大多数无用的短线段都被忽略掉。在实验中,共检测了22280个子图,但大多数分子图只包含一条或两条线段,仅仅124个子图包含超过15条线段。图像中包含跑道的子图有168个线段。这意味着大多数线段在这一步中能够被忽略掉,也使得检测速率大大提高。
根据上面提到的跑道的标准,我们得到了正确的最终结果,见图 3(a),将本文的方法用于其它3幅图像 (分辨率都是2000×2000),也得到了良好的检测效果,没有产生虚警。
Hough变换对线状目标检测有着重要意义。然而,从背景复杂、画幅尺寸巨大的高分辨率遥感影像中有效提取线状目标,传统的Hough变换不仅处理运算复杂,而且很容易造成误检、漏检现象[14]。论文所提出的基于改进的PHT变换,通过将整幅图像分成小块子图,再利用Canny算子提取边缘后执行PHT变换,用分块后子图的局部检测阈值取代了整图的全局阈值,不仅保持Hough变换的鲁棒性,提高了对直线的检出率,而且减小了累加器矩阵规模、降低了内存的消耗和计算复杂度。再经过对PHT变换后的直线簇聚类及平行线对筛选后,更进一步保持了复杂背景下检测长线状目标的可靠性。这种方法也可以推广应用到其他各种有直线边缘的目标检测中。
[1] |
宋晓静.基于Hough变换目标检测问题研究[D].秦皇岛:燕山大学, 2015.
Song X J. The study on target detection based on Hough transform[D].Qinhuangdao:Yanshan University, 2015. |
[2] | Duda R O, Hart P E. Use of the Hough transformation to detect lines and curves in pictures[J]. Communications of the ACM, 1972, 15(1): 11–15. DOI:10.1145/361237.361242 |
[3] | Hough P V C. Method and means for recognizing complex patterns[P]. US Patent, 3069654, 1962-12-18. |
[4] | Li Y, Cao Z R. Improved randomized Hough transform algorithm for circle detection[J]. Journal of Computer Applications, 2010, 6(1): 174–176. |
[5] | Liu Y J, Lai R F, Rong W B, Sun L N. A fast center detecting method based on improved randomized Hough transform[J]. Nanotechnology & Precision Engineering, 2011, 9(4): 298–304. |
[6] | Illingworth J, Kittler J. The adaptive hough transform[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1987(5): 690–698. |
[7] | Li H W, Lavin M A, Master R J L. Fast Hough transform:a hierarchical approach[J]. Computer Vision, Graphics, and Image Processing, 1986, 36(2-3): 139–161. DOI:10.1016/0734-189X(86)90073-3 |
[8] | Atiquzzaman M. Multiresolution Hough transform-an efficient method of detecting patterns in images[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1992, 14(11): 1090. |
[9] | Kiryati N, Eldar Y, Bruckstein A M. A probabilistic Hough transform[J]. Pattern Recognition, 1991, 24(4): 303–316. DOI:10.1016/0031-3203(91)90073-E |
[10] | Barni M, Cappellin V, Paoli A, Mecocci A. Unsupervised detection of straight lines through possibilistic clustering[C]. Image Processing, 1996. Proceedings, International Conference on. IEEE, 1996, 2:963-966. |
[11] | Canny J. A computational approach to edge detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986(6): 679–698. |
[12] | Ommer B, Malik J. Multi-scale object detection by clustering lines[C]. Computer Vision, 2009 IEEE 12th International Conference on. IEEE, 2009, 484-491. |
[13] | Barinova O, Lempitsky V, Kohli P. On detection of multiple object instances using Hough transforms[J]. Computer Vision & Pattern Recognition, 2010, 34(9): 2233–2240. |
[14] | Matas J, Kittler J, Galambos C. Robust detection of lines using the progressive probabilistic Hough transform[J]. Computer Vision & Image Understanding, 2000, 78(1): 119–137. |