2. 国防科学技术大学 信息系统工程重点实验室, 湖南 长沙410073
2. Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
直线是数字图像处理领域中的中层描述符号，利用它可以描述许多对象，即使是复杂的曲线在GIS和CAD中仍能用分段线段来表达。因此线特征自动提取在图像处理[1]、计算机视觉[2, 3]、机器视觉[4, 5]和数字摄影测量与遥感[6, 7, 8]中有广泛的研究。
近年来在特征点与特征区域检测方面取得了较大进展[9, 10, 11]，然而，由于图像特征点的离散误差和特征点提取过程中的位移现象，使得由二图像点所确定的直线参数随之产生某种不确定性[12]。此不确定性造成直线提取的不完整和过提取，也是导致直线特征立体匹配结果具有不确定性的关键因素[13]，因此线提取还是影响视觉理解的关键因素。文献[14, 15]总结了具有代表性的线提取算法：霍夫变换法、启发式连接算法、层次记号编组法和Burns设计的相位编组法等。理想的直线提取算法应具有如下特征: ① 能提取低对比度线段；② 保证线段提取完整性，尽量避免提取的破碎性；③ 防止线段被误连，降低取伪概率；④ 提取线段精度高；⑤ 对噪声不太敏感；⑥ 具有良好的局部特性。但现有算法都不能完全解决上述问题，尤其是如何在保证线段提取完整性的条件下尽可能避免“误连”现象，似乎是一对不可调和的矛盾，这将是本文重点研究的问题之一。此外，如何把线提取精度提高至亚像素级(子像素)是进行高精度视觉测量和三维重建的关键，本文也将探讨。
2 基于模糊融合和假设检验的线特征初值提取2.1 边缘检测
传统的边缘检测算子大多是利用边缘的梯度极值特性，检测局部一阶导数最大或二阶导数过零点来作为边缘点。这类算子由于直接对影像进行微分运算，一般对噪声较为敏感，抗干扰性能差。文献[3]指出边缘检测实际上是一个病态问题。为了减少噪声对边缘提取的干扰，在采用正则化方法的基础上又发展起来许多边缘检测算子：如文献[6]中的LOG (Laplacian of Gaussian)算子，它在直线提取中也有应用，但LOG算子也有一定的局限性，在抗干扰和检测出复杂形状的边缘之间存在尖锐的矛盾，而且平滑窗口大小的选择也是一个很难解决的问题。Canny是一种经典的边缘检测算子，它给出了评价边缘检测性能优劣的3个指标：① 好的信噪比；② 好的定位性能；③ 对单一边缘仅有唯一的响应。因此本文选用此算法进行边缘检测。该算法分为3步：① 图像与最优滤波器卷积；② 对卷积图像进行求导；③ 检测图像梯度的局部极大值点作为边缘点。本文采用Canny算子进行边缘检测。
2.2 感知编组与线段拟合特征编组指的是在不需先验知识的前提下，人类视觉系统从影像中获取相关组织及结构的基本能力,该观点来自于术语感知编组(perceptual organization)。感知编组初期分为两个过程：① 对提取的线特征计算简单的几何关系；② 将这些提取的特征在几何关系的基础上建立更大的几何结构。
在线状特征自动提取中，感知编组就是将边缘检测后形成破碎的线段“分组合并”生成完整线段。感知编组通常有两类错误： “弃真”，破碎线段没能真正完全的合并从而破坏了线段的完整性； “取伪”，把不是同一条线段的破碎线段进行了错误的合并。当前算法不同程度地存在上述错误：
(1) 霍夫变换计算量大而且会出现“误连”，即不能区分共线(具有近似的直线方程)但实际上不相连的直线，导致“取伪”；
(2) 跟踪边缘点是启发式连接算法的关键，但通常只能考虑局部邻域的候选连接点信息，因此忽略了全局的线段信息，所以当影像噪声大时，会发生“弃真”，故不能保证线段的完整性；
(3) 相位编组法根据相位信息对图像进行分割，而相位信息的不一致性可能导致一条直线被分解为多条小线段，以致“弃真”。
因此本算法将综合全局尺度(避免“弃真”)和局部尺度(避免“取伪”)信息尽可能保证线段提取的完整性和正确性。而且通常线段拟合都是在感知编组或者边缘跟踪之后完成，而本算法将其统一到感知编组中。与目前一些算法将几何和物理(光谱)信息同时定量化进行编组决策不同，由于二者之间的权重不好确定，因此本算法将其分开，即在满足几何假设的条件下才对物理特征进行单独检验，这样的好处在于进行决策编组时避免了权重分配不当导致的混淆和错误。本文在文献[15]算法的基础上进行改进和优化。
2.2.1 几何假设与检验首先，通过几何关系进行模糊融合决策，为了降低“弃真”的概率，将阈值放宽尽可能纳入更多的具有“全局尺度”的共线线段。从断裂线段间的几何拓扑关系来判断合并连通的可能性，如图 1共4个指标。
|
| 图 1 线段编组中的几何拓扑关系 Fig. 1 Geometric topology relationship of line segments perceptual organization |
(1) 端点距离：线段间的端点必须落在直线的连接感知圆形区域内。考虑到某一条线段越长，即使与另一条线段相距较远也有可能被连接，所以应该综合线段的长短考虑邻近性，而文献[15]没有考虑此因素，由此新定义具有对长度自适应性的隶属度函数为
式中，k为阈值(本文取0.5)，lengthi为线段Li的长度(i=1,2)，x为两条线段间最短距离。
(2) 侧向距离：定义为一条线段中点到另一条线段的距离disi (i=1,2)，隶属度函数为
式中，width1、 width2分别为两条直线对应支持域宽度的阈值(本文取3个像素)，与文献[15]中表示某一个距离不同，x为dis1和dis2的最小值。
(3) 共线方向差：若两线段共线，那么它们之间的夹角应较小，与文献[15]定义30°(π/6)不同，本文认为夹角大于10°时，隶属度为0，修改参数后定义隶属度函数为
式中，x为线段间夹角。
(4) 交叠度：反映两线段重叠的度量，重叠度越高，置信度越低。如图 1(d)，线段L2的端点Q1在L1上的投影到线段L1端点P2的距离dis1必须小于Q2到线段L1投影与L1端点P2的距离dis2，隶属度函数为
式中，x = dis2－dis1。首先将L1和L2往x、y轴投影，至少在一个投影方向上线段坐标有相交则采用本隶属度函数，否则说明两直线完全不重叠，隶属度值直接赋1。综合上述4个几何拓扑关系进行模糊融合决策如下 当S=1时，进行合并连接；S=0时，不予连接。
然后根据直线的角度选择不同的残差方向对可合并的线段进行拟合
式中，θ表示直线与x轴的夹角。实际上，即使满足模糊融合的条件拟合出的直线也未必具有可信度，本文采用对直线方程的斜率参数a进行假设检验来提高拟合直线的信度。检验统计量为 式中，即应服从自由度为(1,n-2)的F分布；Sregression是回归平方和；Sresidual是残差平方和；
表示拟合的估值；为观测值yi的均值。在显著性水平α下，若F > Fα (1,n-2) 则拒绝原假设a=0，接受备择假设认为线性回归显著，否则认为不满足线性关系，线段不予合并。
2.2.2 物理光谱检验上述基于全局尺度的几何假设与检验在降低“弃真”概率的同时会增加“取伪”概率。为了减少“取伪”概率，本文建议采用物理检验的方法：即需在线段连接区域内的“微观尺度”进行灰度和纹理信息的审核避免“误连”。如图 2(a) 中l1和l2满足几何连接关系，但连接后图 2(b)、(c)中框选区域提取的红色线段显然是错误的。通过上述式(1)～式(7)在几何上确定线段l1和l2可以连接后，再对3条线段P1P2、P2Q1和Q1Q2进行物理相似性测度，显然若3线段物理特征相似性高可以进行合并，反之则不予合并。采用文献[16, 17]提出的稳健线段描述子中的MMSD(梯度幅值均值-标准差描述子)进行连通性检验，该算子最大的优点在于与线段长度无关，且具有平移、旋转和线性光照不变性。归一化后的MMSD为
式中，L就是描述线段的4r+2维向量；r为支持域的宽度，本文取7个像素，此描述子与线段长度无关，具体计算参见文献[16]，通过公式(8)分别计算出线段P1P2、P2Q1和Q1Q2的MMSD描述子，然后利用欧式距离来测度相似性(阈值0.2)。若不相似则否定原假设，最终不能连接，反之则相连。以图 2(a)、(b)为例，l1与l2通过式(1)～(5)模糊决策后S=1，再经过式(7)进行统计检验，在显著性水平α=0.01下拒绝原假设，认为线性回归显著，故在几何上可以连接。但计算P1P2和P2Q1的MMSD描述子之间的欧式距离发现‖MMSD(P1P2)－MMSD(P2Q1)‖>0.2，所以光谱信息不相似，最终拒绝连接。
|
| 图 2 连接区域的假设检验 Fig. 2 The hypothesis testing of connected region |
目前有很多文献都对高精度线特征提取进行了研究，文献[18]提出了一种基于离散直线段的合并方法，该方法可以较好地保证局部边缘特性[18]。还有一种结合精确单点定位方法和基于分裂的最小距离误差线段逼近法的高精度轮廓直线特征提取算法[19]。由于已有线段较好的定位初值，故可采用最小二乘影像匹配(LSM)实现线段的子像素提取，该算法文献[20]中提出，由于该方法充分利用了影像窗口内的信息进行平差计算，使影像匹配可以达到子像素级(1/10~1/100 像素)精度。此后，文献[21]对LSM进行了扩展，以给定的特征模式作为参考模板与实际影像做最小二乘影像匹配(LSTM)，从而高精度提取目标。
由于经过上述严格的几何和物理检验已经提取出比较精确的线段可作为真实影像线段的近似边缘，故可利用最小二乘模板匹配的方法将线段提取的精度进一步提高至亚像素。以阶跃边缘为例，由理论边缘模式生成阶跃边缘模板，用此模板与实际的待检测影像线段进行匹配，通过调整定位线段的坐标参数使得相关系数最大，从而可精确定位边缘。假设给定模板为gm(x,y)、gt(x,y)是实际影像块，建立两者的匹配意味着gm(x,y) = gt(x+Δx,y+Δy)[22, 23, 24]。由于噪声，它们之间不可能完全相等，但可写出误差方程进行平差解算
为计算方便在匹配前可将影像块旋转成水平影像，使二维匹配转化为一维匹配。
4 试验与分析通过VC++6.0结合OpenCV 1.0编制了程序进行算法验证，选择航空(1080像素×1920像素)和地面(1000像素×1500像素)近景真彩色影像进行试验。为了便于给出提取线段的边缘定位效果，在原始影像上用红色线段进行显示。如图 3(a)和(f)为使用OpenCV中提供的霍夫变换对上述航空和地面影像提取线段的结果，它们的局部影像放大后对应图 3(b)和(g)，可发现，放大区域存在大量的错误提取直线，可能是共线的线段被误连而导致的。图 3(c)和(h)是经过边缘检测、感知编组但未进行假设检验提取的线段，也存在明显的误连(例如图中虚框所示区域)，图 3(d)和(i)是本文提出的算法，可以看出本算法可以较好地克服“两类错误”。可见传统的算法提取的近景建筑物影像线段虽然很长，但是存在错误的分组合并，而经过本算法的假设检验后可以在一定层度上克服线段的“误连”并同时尽可能保证线段的完整性。经过LSTM后线段的定位精度得到了进一步的提高，如图 3(j)可以看出匹配结果与实际边缘完全吻合。表 1给出了提取线状特征的信息，不经过假设检验提取的线段合并得多所以数量少，而假设检验后排除了大量误连线段所以数量多。定位精度没有达到理论上1/10~1/100像素，可能与线段合并拟合后降低了边缘定位初始精度有关，因为有试验表明LSTM算法对初值的要求比较高。尽管如此，本试验定位线段的精度都达到了子像素，航空和地面影像的平均精度分别为0.13像素和0.12像素，其均方差分别为0.04和0.03，可用于高精度视觉测量和三维重构。
|
| 图 3 航空和地面影像线特征提取结果 Fig. 3 Results of line extraction for aerial and ground images |
| 航空影像提取数量 | 地面影像提取数量 | 航空影像提取精度/像素 | 地面影像提取精度/像素 | |
| 经典霍夫算法 | 1768 | 703 | - | - |
| 不经过假设检验 | 962 | 738 | - | - |
| 本文算法 | 1383 | 1031 | 0.13±0.04 | 0.12±0.03 |
笔者提出了一个基于几何假设和物理检验的线段“感知编组”算法，可提高线段提取的可靠性，通过模糊融合和回归显著性检验在几何上严格测试破碎线段的几何连通性，从而保障线段的完整性，但在降低“弃真”概率的同时增大了“取伪”概率。所以，需考核可编组线段之间的物理光谱相似性来判断最终是否能够连接，从而避免误连，这种从全局到局部尺度、几何假设加物理检验的感知编组方法可以克服霍夫变换和传统边缘跟踪等算法的不足。最后利用LSTM可将线段的定位精度提升到亚像素。本算法可以同时减少“弃真”和“取伪”的概率，在一定程度上解决两者之间的矛盾。
虽然，利用连通区域光谱检验可以很好地防止线段误连，但由于阴影、背景和遮挡等“噪声”会导致光谱差异变大从而破坏线段提取的完整性。因此，影像滤波和多波段信息的引入，以及“噪声”的检测是否能进一步提高线特征抽取的鲁棒性是将来研究的重点。
| [1] | HUERLAS A N,EVATIA R. Detecting Buildings in Aerial Images[J]. Computer Vision Graphics and Image Processing, 1988, 41(2) : 131-152. |
| [2] | HUERLAS A, COLE W, EVATIA R. Detecting Runways in Complex Airport Scenes[J]. Computer Vision Graphics and Image Processing, 1990, 51 (2): 107-145. |
| [3] | MA Songde, ZHANG Zhengyou. Computer Vision-Theory of Computation and Algorithm[M]. Beijing: Science Press, 2003.(马颂德, 张正友. 计算机视觉[M]. 北京:科学出版社,2003.) |
| [4] | MERLET N, ZERUBIA J. New Prospects in Line Detection by Dynamic Programming [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18 (4) : 426-431. |
| [5] | ZHANG Guangjun. Machine Vision[M]. Beijing: Science Press, 2005. (张广军. 机器视觉[M]. 北京:科学出版社, 2005.) |
| [6] | ZHANG Zuxun, WU Jun, ZHANG Jianqing. A Method for Straight-Line Extraction Based on Line Space[J]. Geomatics and Information Science of Wuhan University, 2004, 29(3): 89-194. (张祖勋, 吴军, 张剑清. 一种基于线空间的直线抽取算法研究[J]. 武汉大学学报:信息科学版,2004. 29(3):189-194.) |
| [7] | SHE Eryong, WANG Runsheng. Line Extraction in Multiple Images Based on Fusion Edges[J]. Chinese Journal of Computers, 2005, 28(1): 142-145. (佘二永, 王润生. 基于边缘融合的多图像直线提取算法[J]. 计算机学报, 2005, 28(1): 142-145.) |
| [8] | BAILLARD C, SCHMID C, ZISSERMAN A, et al. Automatic Line Matching and 3D Reconstruction of Buildings from Multiple Views[C]// Proceedings of ISPRS Conference on Automatic Extraction of GIS Objects from Digital Imagery. München: ISPRS,1999: 69-80. |
| [9] | LOWE D G. Distinctive Image Features from Scale-invariant Keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110. |
| [10] | MIKOLAJCZYK K, SCHMID C. A Performance Evaluation of Local Descriptors[J]. IEEE Transactions on Pattern Analysis Machine Intelligence, 2005, 27(10): 1615-1630. |
| [11] | MIKOLAJCZYK K, TUYTELAARS T, SCHMID C, et al. A Comparison of Affine Region Detectors[J]. International Journal of Computer Vision, 2005, 65(1-2): 43-72. |
| [12] | SUN Fengmei, HU Yu, HU Zhanyi. A Study on the Uncertainties in Line Extraction from Images[J]. Acta Automatica Sinica, 2003, 29(4): 589-598. (孙凤梅, 胡宇, 胡占义. 直线提取中的不确定性研究[J]. 自动化学报, 2003, 29(4): 589-598.) |
| [13] | Wang Jiyang, Wen Gongjian, Li Deren. Uncertainty in Matching Straight Line Segments[J]. Signal Processing, 2010, 26(5): 641-647. (王继阳, 文贡坚, 李德仁. 直线特征立体匹配中的不确定性问题[J]. 信号处理, 2010, 26(5): 641-647.) |
| [14] | Wen Gongjian,Wang Runsheng. A Robust Approach to Extracting Straight Lines [J]. Journal of Software,2001, 12(11): 1660-1666. (文贡坚, 王润生. 一种稳健的直线提取算法[J]. 软件学报, 2001, 12(11): 1660-1666.) |
| [15] | MAO Xia, ZHAO Xingyuan, LI Lei. Algorithm of Extracting Straight Lines Based on Fuzzy Fusion[J]. Infrared and Lase, 2006, 35(sup4): 13-18. (毛峡, 赵兴国, 李磊. 一种基于模糊融合的直线提取算法[J]. 红外与激光工程, 2006,35(sup4): 13-18.) |
| [16] | WANG Zhiheng, WU Fuchao. Mean Standard Deviation Descriptor and Line Matching[J]. Pattern Recognition and Artificial Intelligence, 2009, 22(1): 32-39 .(王志衡, 吴福朝. 均值—标准差描述子与直线匹配[J]. 模式识别与人工智能, 2009, 22(1): 32-39.) |
| [17] | WANG Zhiheng, WU Fuchao, HU Zhanyi. MSLD: A Robust Descriptor for Line Matching[J]. Pattern Recognition,2009, 42(5): 941-953. |
| [18] | SCHMID C, ZISSERMAN A. Automatic Line Matching Across Views[C]// Proceedings of the Conference on Computer Vision and Pattern Recognition. Puerto Rico:[s.n.], 1997: 666-671. |
| [19] | LI Cailin, GUO Baoyun, LI Chang. The High-accurate Extraction of Line Features of Object Contour[J].Acta Geodaetica et Cartographica Sinica, 2011, 40(1): 66-70. (李彩林,郭宝云,李畅. 目标轮廓直线特征的高精度提取[J]. 测绘学报, 2011, 40(1): 66-70.) |
| [20] | ACKERMANN F. High Precision Digital Image Correlation[D]. Stuttgart:University of Stuttgart, 1983:231-243. |
| [21] | GRUEN A. A Daptive Least Square Correlation: A Powerful Image Matching Technique [J]. South African Journal of Photogrammetry and Remote Sensing, 1985, 14 (3): 175-187. |
| [22] | Subject Group of Survey Adjustment School of Geodesy and Geomatics Wuhan University. Error Theory and Surveying Adjustment Foundation[M].Wuhan:Wuhan University Press, 2003.(武汉大学测绘学院测量平差学科组. 误差理论与测量平差基础[M].武汉:武汉大学出版社,2003.) |
| [23] | XIE Wenhan.Camera Calibration Based on Vanishing Points of Multi-image[D].Wuhan: Wuhan University,2004.(谢文寒.基于多像灭点进行相机标定的方法研究[D].武汉:武汉大学,2004.) |
| [24] | ZHANG Yongjun,WANG Cheng, ZHANG Zuxun,et al. Object Space-Based Matching and Reconstruction of Circles[J]. Chinese Journal of Mechanical Engineering, 2004,40(2):92-95. (张永军,王乘,张祖勋,等.基于物方直接解的圆匹配与重建[J]. 机械工程学报,2004,40(2):92-95.) |