像素编组和逐级质量控制的线段检测算子范文

《红外与毫米波学报》2016年第6期

摘要:

针对现有线段提取算法存在的不足，提出了一个点元梯度特征引导下的线段检测算子，在编组的前、中和后三大环节进行逐级质量控制．基于梯度最优并结合邻近性、方向性等规则控制“欠提取”错误，采用假设检验方法控制“过提取”错误．多源数据实验表明，提出的算法在编组中不易受到弱梯度像素或噪声的干扰，与经典的线段提取算子相比，在线段提取的效率和稳健性都有一定的优势，有利于实现从场景到结构的重要视觉符号描述．

关键词:

线段检测;像素编组;质量控制;假设检验;欠提取;过提取

引言

线段在数字摄影测量与计算机视觉、遥感信息提取中属于中层视觉符号;是灭点检测［1-2］、直线匹配［3］、基于线特征的影像配准［4-5］、结构识别［6］、遥感地物信息提取［7］和三维重建［8］等场景恢复算法的重要基础，线段提取结果的好坏直接影响后续处理的效率．因此，一个提取完整，抗噪性强，定位精确且运行速度快的线段检测算子对以线段符号为基础的技术应用具有重要意义．线段提取算法可分为如下两类．

(1)基于边缘:该类算法在边缘检测结果上进行提取．霍夫变换［9］，以及Neva-tia等提出的算法［10］最为经典，前者通过参数空间，把寻找满足线性关系的边缘像素组合问题转化为参数空间求极值的问题;后者将边缘跟踪为链码，通过链码的分裂与合并检测线段．虽然两类方法思想不一样，但在提取过程中，梯度模都起着主导作用，即只有边缘像素才能参与线段的拟合．众多线段提取算法在此基础之上从速度和防止误连进行改进，例如Etemadi提出的同时提取线段和曲线的算法［11］，基于EdgeDrawing［12］边缘提取的EDlines［13］，概率霍夫［14-15］、高斯核霍夫［16］等．霍夫检测本身不能克服线段的过连接情况，提取出的是直线不是线段，故往往没有端点．基于链码分裂的提取算法本身依赖于边缘提取的效果，容易带来欠提取的问题，具体表现为:1)若梯度阈值设置过大，则弱边缘提取不完整，造成线段无法提取;2)受噪声影响，边缘链码出现分叉或者局部弯曲时，线段在此出现断裂．欠提取的问题在复杂场景中最为常见．

(2)基于编组:由于线段存在一个区域，区域内的梯度方向具有很大相似性，因此该类算法按照梯度方向的一致性直接将邻近像素编组为线段区域．Burns提出的编组方法［17］最为经典，具有较强的全局性，能有效解决基于边缘的线段提取算法中易受噪声干扰的问题，对于复杂场景以及弱梯度线段的提取均有较好的效果．后续算法从线段定位精度，运行速度［18］，以及伪线段的错误控制［19］进行改进．Grompone等改进了错误控制算法［19］的效率，融合已有算法的优点，提出的LSD［20］在过提取的控制与运行速度上均有出色表现．这类算法与基于边缘的线段提取算法相反，没有使用梯度的模而是梯度的方向作为编组的决定因素，受到线段区域边缘弱梯度像素的影响，编组可能会出现过生长，表现为区域宽度不一致，出现局部突出;若不进行控制，则会产生过提取，使端点定位不准．该类方法通常在编组中对像素设置梯度阈值，并通过逐步缩减线段支持区域的范围，减小编组的方向容忍阈值等方法迭代控制过提取．这可能使过提取又转化为欠提取问题，具体表现为:1)梯度阈值的设置使得处于弱梯度区域的线段有可能完全不能提取，或者含有弱梯度的区域的完整线段被分裂成破碎线段;2)控制过生长的过程有可能造成线段支持区域分裂．基于上述分析，欠提取(弃真，第一类错误)与过提取(取伪，第二类错误)是线段提取需要解决的两类质量问题．对于当前基于像素编组的线段提取算法，弱梯度像素的干扰以及固定的方向容忍阈值是造成过提取的主要因素，而缺乏有效的过提取控制则是造成欠提取的重要原因．由于，只要单一某个环节存在误差就会导致整体的不确定性，故需要在每个环节都进行相应的质量控制．此外，由经典的统计原理可知“当样本容量固定时，若减小犯第一类错误的概率，则犯另一类错误的概率往往增大，若要使犯两类错误的概率都减小，除非增加样本的容量”．由此可见，同时降低两类错误在单一条件下不可能，但是在多条件(例如，增大样本容量)下进行控制则是可以同时减小两类错误的．因此，本文提出一种逐级质量控制的线段检测策略，编组前，通过局部梯度极值生成编组种子点，保证编组初始位置的可靠性;针对经典编组算法抗弱梯度干扰性差的问题，提出利用梯度特征引导编组过程的算法，使得编组过程不易受弱梯度像素的干扰，编组后通过链码分裂可以严格且有效地控制固定方向容忍阈值带来过提取问题;最后采用假设检验的方法剔除伪线段，再利用高精度平差模型提升线段拟合精度，采用多手段力图从各个环节控制两类错误，具体策略和算法如下．

1线段提取算法与策略

算法可分为种子点生成、像素编组与线段拟合、过提取控制三个步骤．种子点生成提高像素编组初始位置的可靠度;在像素编组与线段拟合中，提出一种融合梯度模与梯度方向的编组策略，抑制弱梯度像素的干扰，控制欠提取，使用Partial-EIV［21］模型结合梯度权值提高线段拟合质量;过提取控制包含对两类过提取的控制:固定方向容忍阈值造成的编组过生长;树木，草地等背景噪声中提取出的伪线段．

1．1种子点提取

经典检测算子如LSD，EDLines需要对整体像素设置梯度阈值，导致部分含有弱梯度像元的线段无法完整提取或根本不能提取，因此，仅对初始生长的种子点设置梯度阈值而不对潜在的编组像素设置阈值以解决上述欠提取问题．梯度模越大，则越有可能是边缘像素，将其作为初始生长种子点可以提高编组位置的可靠性。

1．2像素编组与线段拟合

1．2．1像素编组

针对经典像元编组策略易受弱梯度像素干扰的问题，本文提出的算法在编组中除了方向一致性约束外，引入点元梯度方向引导编组过程，并结合梯度模控制像素质量，为后续编组过生长控制奠定基础．具体实现方法如下．编组从种子点开始，编组的走向由点元的预编组角度确定，预编组角度为线段潜在可能增长的方向，由点元梯度角顺时针旋转90°得到．计算公式为θ=arctan(gx(x，y)/－gy(x，y))，(3)式中gx(x，y)，gy(x，y)分别表示点元在x和y方向的偏导数，像方坐标系为右上角为坐标原点的左手坐标系，即横轴为x轴，越往右值越大，竖轴为y轴，越往下值越大．若上一个纳入链码像素的预编组角度为θ，则编组走向(dx，dy)可由式(4)求出:dx=round(cosθ)|θ|≤π/40|θ|＞π/{4dy=round(sinθ)|θ|＞π/40|θ|≤π/{4，(4)式中round为四舍五入函数，式(4)将编组走向简化为带正负号的水平与垂直方向．受Edgedrawing［12］边缘跟踪算法启发，为了控制欠提取，最多可有6个邻近像素参与编组判断:若上一个纳入编组的像素预编组角度为垂直走向，上侧或下侧的三个邻近像素将会作为候选生长点(图1(a))，否则，该像素左侧或右侧的三个邻近像素将会作为候选生长点(图1(b))．按此原则，3个编组候选像素坐标(x1，y1)，(x2，y2)，(x3，y3)可按式(5)计算:x1y1x2y2x3y3=10111－1x+λdxy+λdydy－d[]x，(5)式中(x，y)为上一个纳入编组的像素坐标，λ首先取1，使链码从初始生长点“正”向进行编组，该方向编组结束后回到种子点，取λ为-1，往“负”方向进行编组．三个候选像素都有可能满足编组方向一致性，为了使编组中的像素满足梯度模相对最优，将3个候选像素按梯度模从高到低的顺序进行可编组判断:记编组中已有n个像素，则编组角度可按式(6)计算，angle=arctan∑ni=1sinθi∑ni=1cosθi，(6)式中θi表示编组中第i个像素的预编组角度，若像素的预编组角度与编组角度之差在阈值τ内，则将当前像素加入编组，且不对其它侯选点进行检验．基于梯度方向的线段检测算子［17-20，23］均建议将角度容忍误差设为π/8，我们对不同的阈值进行了实验，也得出π/8相比其它阈值能够取得更好的编组效果，因此参照前人研究，将方向容忍误差设置为π/8．出现以下情况时，停止当前方向的像素编组:(1)3个候选像素均不能满足编组的方向一致性约束;(2)满足约束条件的像素已被使用;(3)到达了整张影像的边界．由编组策略可知，编组走向受梯度方向控制，编组时选择满足方向一致性的梯度模最大的像素，编组后为单像素宽度的链码;因此编组策略既具有方向编组的全局性优势，也避免了LSD等区域编组算法所面对的弱梯度干扰而带来的过生长问题．

1．2．2线段拟合

记链码中有n个像素，h为图像行数，w为图像列数，若n＜－2(log(h)+log(w))log(p)，(7)则链码由于长度太小无法通过后续的错误控制检验．式中p为邻近像素方向一致的概率，因为像素编组的方向容忍误差为π/8，所以p=0．125．若n符合式(7)，则直接剔除该链码，否则，将链码中的点元按EIV(Errorsinvariables)平差模型［24］拟合为线段．

2过提取控制

2．1编组过生长控制

编组过程中使用了固定的方向阈值，可能出现过生长情况，即不属于该编组的像元被加入到编组中，如图2中编组左端的像素被误加入了编组(即，过生长)，因此了降低线段拟合质量．但是，由于编组得到的是单像素宽度的链码，通过计算拟合线段的均方根误差(rootmeansquareoferrors，RMSE)便可检测出编组是否存在过生长若RMSE大于1，则认为线段整体平均偏离了一个像素，存在过生长情况，可以参照边缘分裂算法［25］进行过提取控制:

1)若拟合得到的线段角度|θ|＜π/4，则对链码按x坐标的大小排序，反之，按y坐标的大小进行排序;

2)将距离链码端点组成的线段最远的点作为分裂点，从该点分裂成两条链码．其中较长的链码被保留，短链码中的像素设置为未使用状态，可在后续编组过程中被使用;

3)对长链码进行线段拟合，若通过误差检验，则停止分裂，并将其作为一条线段．否则，返回步骤1)，直至链码中像素个数低于最少像素个数．

2．2伪线段控制

满足均方根误差检验所得到线段仍有可能存在错误提取(FalsePositive)问题，例如树木，草地，云朵等背景将会产生大量伪线段，影响着后续算法的效率与稳定．这些线段可以通过错误控制［19］进行剔除．错误控制方法源自于视觉感知原则:具有视觉显著性的结构，其内部元素，例如梯度方向，呈随机性的概率将会很低，在随机背景模型中表现为异常值．错误控制方法在一种随机背景模型假设下对线段进行假设检验，高斯白噪声在各个方向上具有独立性，可以作为一种图像背景模型．在图像背景模型为高斯白噪声(即非线段)的H0原假设下，Desol-neux等［19］定义了错误响应函数(NumberOfFalseAlarms，NFA)对线段进行假设检验:若图片尺寸为M×N，设n为某一线段链码的像元个数，k为链码中与拟合线段方向一致的像素个数，p为1．2．2节讨论的梯度方向一致的概率，则有:NFA(r)=M(M－1)N(N－1)b(n，k，p)，(8)式中b(n，k，p)为二项概率分布∑ni=k()nipi(1－p)n－i，若NFA(r)＜ε(ε＞0)，则拒绝原假设H0，即背景不是各向同性的随机噪声，从而接受其为线段的备选假设H1;反之接受原假设，将线段作为伪线段剔除．Desolneux建议将ε设为1，表示在一张图片中，会出现一个错误检测．统计编组中n个像素的预编组角度与拟合得到的线段角度一致的像元个数k，并计算出NFA(r)的值，若小于ε，接受为一条线段．需要强调的是，高斯平滑会降低邻近像素的独立性，在错误控制前需对链码中像素的预编组角度在未经过高斯平滑的原图像中重新计算．

3实验与分析

为了检验算法的有效性，通过VS2010结合OpenCV2．4．9开源库编制程序，使用一台处理器为Intel(R)Core(TM)i5-4200UCPU@1．60GHz，内存为4GB，操作系统为Win10的Thinkpadx240笔记本进行实验，所有算法均在Release模式下执行，执行时间均为重复执行10次后得到的平均值．

3．1数据集1(对比实验)

选择了PHT，LSD以及EDlines算法对一张450×400的航空影像进行检测，PHT是经典的线段检测算子，LSD与EDlines则是近年提出而且被广泛采用的线段检测算法．实验结果(图3)可以看出，PHT不能很好的定位出线段的端点，且易受噪声影响造成过提取，产生大量伪线段;EDlines使用了5×5的高斯模板进行平滑，使得线段提取的连续性较好，但平滑造成梯度偏移，且基于梯度极值的链码跟策略可能造成过提取，图4展示了图3原图像线框中的局部提取结果，从框选区域可以看出EDlines出现了明显的错误提取;与LSD相比，在具体细节上各有优势，且均未出现明显的过提取线段，尽管可能存在一些地方LSD提取得更好，但是总体而言，本算法在提取的效果上更优，例如LSD提取图像的框选区域，提出的算法完整的提取出了视觉上呈直线的屋脊，而LSD则出现了断裂，同时，从框选的沙滩椅区域可以看出，对细节特征的提取有较好的改善．为了更加直观表现在细节性与完整性的改善，将不同算法的提取结果进行长度区间计数统计(图5)．总体而言，提出的算法提取的线段数量最多，且在各个长度区间都能较LSD提取更多的线段;ED-Lines采用了大尺寸模板的高斯平滑，提取的长线段区间(大于40个像元)线段数量略多于本算法，但也因此造成误连接与细节丢失，提取的中短线段(长度小于40个像元)数量明显低于本文以及LSD算法．综合来看，算法对细节特征的提取(细节性)以及线段提取的连续性(完整性)均有改善，这正是由如下针对性的改进而造成:(1)算法仅对种子点设置梯度阈值，而不对潜在的编组像素设置阈值，故在编组过程中不会因为梯度过小而断连或造成弱梯度线段不能被提取;(2)使用了一种新的编组策略，不受弱梯度像元干扰且可以对编组结果进行准确的过提取控制．在速度上，PHT算法在OpenCV库中经过了优化，但执行时间仍然最长;EDlines未进行梯度方向计算，因此执行速度最快;由于未对每个像素设置梯度阈值，提出的算法相比LSD需要处理更多的弱梯度像元，计算量更大，但使用分裂算法进行过生长控制，较LSD的迭代方法更为迅速，因此总的执行时间比LSD稍快，只需55ms(毫秒)，可满足实时处理需求．综上，与经典的算法PHT，以及优秀的算法Edlines、LSD相比，在提取的可靠性上最优，而在速度上尽管没获得最优的结果，但也取得了次优(第二)的结果，故总体而言，在质量和速度上做到了较好的兼顾，单位时间内提取线段的质量更高，效率最优．为了进一步说明提出的编组策略对弱梯度像素的抗干扰能力，将LSD的梯度阈值与本算法种子点梯度阈值同时调低，得到不同梯度阈值下线段提取结果(图8)．在原有阈值下，较LSD提取的线段更为连续，且更多线段被提取出来，长度统计结果(图6)也表明提取结果在完整性与细节性上占优．从阈值的变化对线段提取的影响来看，在单一阈值时，LSD随着阈值t=1，2，5．2，逐渐增大时，线段提取得更完整，但细节丢失严重;而反过来，阈值变小时，线段提取更精细，但完整性变差，即不能同时降低两类错误;然而，本文算法由于在像元编组的前、中和后三大环节进行逐级质量控制，采用了非单一的多控制手段，故对阈值的变化并不敏感，仅有少许变化，在保证提取线段的完整性同时，也很好地保留了细节，同时控制了两类错误．随着梯度阈值降低，LSD需尝试多种方法控制弱梯度像素造成的大量过生长，增大了计算量，执行时间从33ms增加到218ms;而本文算法由于受到弱梯度干扰小，只增加了处理的像元数，因此执行时间仅增加了7ms．需要说明的是，当前，LSD被普遍认为是最好的线段提取算法之一，本文提出的算法相比LSD在提取效果和速度上都得到了改善(连续性与弱梯度线段的提取)，总体而言相比于LSD很好地控制了“两类错误”，提取出来的线段更完整且无明显过提取、细节更丰富避免了欠提取．尤其是，相比于LSD本算法对阈值的选择更不敏感，不仅具有一定的稳定性，而且具有较好的自适应性，这是因为本算法所有的阈值并不是凭经验和少许实验而定，而是在参考前人的大量实验和理论推导的基础上得出的，即几乎所有的阈值都是基于概率统计原理在一定显著性水平或置信水平上推导而来，故具有普适性，请见下节的广泛实验．

3．2数据集2(多源数据验证)

为了进一步验证本算法的普适性，选择了多源多平台数据进行测试，包括可见光数据(380～780nm，对传感器获得的R、G、B波段分别赋R、G、B颜色)、彩红外数据(其近红外波长约为780～2526nm，对传感器获得的NIR、R、G波段分别赋R、G、B颜色)、地面室外数据、室内数据和卫星遥感数据等．图8显示了不同场景图像的线段提取结果．当场景比较简单时，如图(a)、(b)，本算法几乎能完整地提取出所有线段．图(c)、(d)较前两张图片场景稍显复杂，但算法在提取线段的完整性以及对局部细节特征的提取能力上均有稳健表现，例如(c)图中的小窗户格子，以及(d)图中的大部分窗体结构都被完整地提取出来．由于算法采用了错误控制，(c)图中的食物以及(d)图中的草坪，植被产生的过提取线段均被剔除．(e)、(f)为两张彩红外的地面与卫星影像，尤其是航天遥感彩红外影像信息的提取，例如:农田、行树与篱笆等提取，可应用于植被覆盖变化监测、林木与农作物估产，以及风侵蚀监测与土壤保护［7］．

4结论

提出一种逐级质量控制的编组策略，对两类线段提取错误进行控制，可为数字摄影测量、计算机视觉、机器视觉、遥感预处理和地学应用奠定基础．实验表明，提出的算法能有效控制欠提取与过提取的矛盾，且可以实现实时线段提取，符合引言中提出的线段提取完整，抗噪性强，运算速度快的特征，即我们提出的算法不仅在控制两类错误上做到了更好的平衡，而且在速度和质量上也取得了较好的平衡．当前还缺少一个客观评价线段提取质量的指标，且非常难以使用groundtruth进行比较，其原因是:一方面线段提取即会发生欠提取，又会发生过提取，所以不能以简单的提取线段的多少进行评价，这两类错误在国际上目前也没有统一公认的可以定量的评价指标;另外一方面，一般场景中的线段太多，少则上百，多则上万，将一一其列举作为groundtruth进行参考并不现实．这也是众多国际期刊没有给出客观评价指标的原因，如何定量评价也是将来研究的重点方向．

参考文献：

李畅，张祖勋，张永军．灭点误差分布的理论精度评定．测绘学报)，2011，40(3):393-396．

李畅．利用灭点进行相机检校与定姿的充要条件及其不确定性分析．测绘学报)，2012，41(6):851-856．

李畅，刘亚文，胡敏，等．面向街景立面三维重建的近景影像直线匹配方法研究．武汉大学学报:信息科学版)，2010，35(12):1461-1465．

高峰，文贡坚，吕金建．基于干线对的红外与可见光最优图像配准算法．计算机学报)，2007，30(6):1014-1021．

朱丹，王斌，张立明．基于直线邻行性和GBVS显著性的遥感图像机场目标检测．红外与毫米波学报)，2015，34(3):375-384．

李畅．城市街道立面自动重建关键技术研究．测绘学报)，2011，40(2):268-268．

陈燕新，戚飞虎．利用梯度方向信息的随机Hough变换．红外与毫米波学报)，1998，17(5):375-380．

刘经南，曾文宪，徐培亮．整体最小二乘估计的研究进展．武汉大学学报:信息科学版)，2013，38(5):505-512．

郑南宁．计算机视觉与模式识别．国防工业出版社)，1998．

作者:李畅 魏东 单位:华中师范大学地理过程分析与模拟湖北省重点实验室 华中师范大学城市与环境科学学院