基于梯度直方图的交叉点检测方法*

刘进博，郭鹏宇，李 鑫

(1.中国空气动力研究与发展中心 超高速空气动力研究所，四川 绵阳 621000；2.军事科学院 国防科技创新研究院，北京 100071)

相机-投影仪组成的结构光三维重建系统中，相机与投影仪的参数标定最为重要，直接决定了系统形貌测量的精度[1]。目前典型的标定方法是将投影仪视作逆相机，通过虚拟成像，利用张正友平面靶板标定方法确定系统参数，该方法虽然精度较高，但标定过程复杂、耗时较长[2]。通过引入网格结构光，可避免对投影仪进行虚拟成像，从而简化标定过程，提高相机-投影仪标定效率。上述方法的难点在于平面网格结构光的交叉点检测，包括交叉点定位精度和交叉点检测率两方面。

交叉点检测是图像处理中的一项重要内容，可以为图像的特征提取、图像目标识别、图像理解等提供重要的参数和依据[3-6]。目前，交叉点检测仍然是计算机视觉领域尚未完全解决的难题之一，且相关文献较少。已报道的交叉点检测方法主要分为以下两类：①对二值化图像进行膨胀、腐蚀等图像形态学运算，提取交叉线单像素骨架，逐一扫描图像点，根据交叉点8邻域灰度突变次数确定交叉点粗位置，然后根据拟合法或灰度重心法对交叉点进行亚像素定位[7-8]；②分别按行和列对图像进行亮度峰值扫描，细化图像交叉线并提取骨架，通过计算单像素线条交点确定交叉点粗位置，然后根据拟合法或灰度重心法对交叉点进行亚像素定位[8-9]。第一类方法为传统交叉点检测方法，计算速度较快，但错检率、漏检率较高，而且受图像形态学运算精度的限制，传统交叉点检测方法的定位准确性不够。第二类方法要求交叉线夹角(交叉角)近似垂直，且交叉线方向与图像坐标轴近似平行，此种情况下，该方法的图像交叉点检测率和定位精度均较高。但由于未考虑灰度分布的方向性，若图像发生旋转或透视变换，将导致交叉角大小或交叉线方向发生较大变化，从而第二类方法不适用。

在深入研究了尺度不变特征变换(Scale-Invariant Feature Transform,SIFT)算法原理的基础上[10-11]，本文提出了一种基于梯度直方图的交叉点检测方法：以灰度梯度幅值和方向为基础，在角度空间构造8维特征描述子，根据交叉点邻域梯度分布特点对特征描述子进行判定，筛选出候选交叉点，最后通过聚类和灰度加权对交叉点几何中心进行亚像素定位。

1 算法原理

基于梯度直方图的交叉点检测流程如图1所示。对输入图像进行高斯滤波并逐像素扫描，将特征描述子满足交叉点判定准则的像素加入候选交叉点集，最后通过聚类输出图像交叉点检测结果。检测过程主要涉及3个重要环节：特征描述子生成、交叉点判定和候选交叉点聚类，本节内容主要针对上述3个环节进行详细阐述。

图1 基于梯度直方图的交叉点检测方法流程图Fig.1 Flowchart for the detection method based on gradient-histogram

1.1 特征描述子生成

由于相机采集图像存在噪声，为提高算法适应能力，首先对原始图像进行高斯滤波，若原始图像为彩色图像，则需转换为灰度图像再进行高斯滤波。记pi,j为灰度图像的第i行、第j列像素点，g(i,j)为其对应的灰度值，根据中心差分计算各像素点的灰度梯度幅值及方向[12-13]，公式为：

(1)

其中，gx、gy为对应像素点沿图像x、y方向的灰度梯度，m为对应像素点的灰度梯度幅值，θ为对应像素点的灰度梯度方向(范围为0°～360°)。

将角度空间0°～360°划分为8等份，如图2所示。1～8表示划分的角度空间标号，分别代表的梯度方向为0°、45°、90°、135°、180°、225°、270°、315°和360°，其中337.5°～22.5°属于第1角度空间，22.5°～67.5°属于第2角度空间，以此类推。

图2 角度空间8等份划分Fig.2 Slice up angle space into 8 equal parts

统计各像素点16×16邻域的梯度幅值及方向，并按角度空间累积梯度幅值。交叉点如图3(a)所示。由于交叉点中心附近梯度幅值小且方向易受影响，如图3(b)所示，因此利用权重模板，如图3(c)所示，对邻域像素梯度进行加权，进而在角度空间生成梯度直方图，作为各像素点的特征描述子k(pi,j)，如图3(d)所示。

(a)交叉点 (b)交叉点邻域梯度(a)Intersection points (b)Gradients of neighborhood pixel

1.2 交叉点判定

利用1.1节介绍的方法计算出各像素点的特征描述子之后，根据如下的准则对像素点进行逐一判定，筛选出候选交叉点。不失一般性，以图像中任一像素pi,j为例，记k(pi,j) = (h1,h2,h3,h4,h5,h6,h7,h8)为该像素点的特征描述子。

1)总能量判定准则。交叉点由两条直线或近似直线相交而成，在直线边缘处，灰度梯度最大。因此特征描述子的梯度幅值之和，即能量总和必须大于给定的能量阈值Tthresh。

(2)

2)能量占比判定准则。对于任一交叉点，在其邻域范围内必然存在4个梯度主方向。基于此，对特征描述子k(pi,j)中的8个能量分量进行由高到低排序，假设h1≥h2≥h3≥h4≥h5≥h6≥h7≥h8，Rthresh为给定的能量占比阈值，则：

(3)

3)反向判定准则。交叉点由两条直线或近似直线相交而成，直线两侧的灰度梯度方向相反，不失一般性，记hi、hj、hk、hl为特征描述子的4个梯度主方向，ni、nj、nk、nl为其对应的角度空间标号，Si,j表示ni与nj的角度差，Si,k表示ni与nk的角度差，Sk,l表示nk与nl的角度差，Sj,l表示nj与nl的角度差。则ni、nj、nk、nl必然满足式(4)或式(5)。

(4)

(5)

4)能量平均判定准则。交叉点由两条直线或近似直线相交而成，直线两侧的灰度梯度幅值近似相等。不失一般性，记hi、hj、hk、hl为特征描述子的4个梯度主方向，Dthresh为平均能量阈值，hi、hj、hk、hl必然满足：

为什么会沉默时充实，开口时空虚？因为一旦开口，就像战士冲出了战壕，将自己完全暴露于敌人的火力之下。为此，如果没有直接伤害到个人利益，许多人都会选择沉默。过去如此，现在也是如此。至于战阵中伙伴的变化，也是经常发生的事情，高升的不再下顾，退隐的不再出头，所以那些站在前边的改革者和呐喊着，会经常地感觉到苦闷和孤独。

(6)

1.3 候选交叉点聚类

候选交叉点聚类前后如图4所示。由于交叉点的两条交叉线有一定宽度，通常大于1像素，导致交叉点及其相邻像素的特征描述子有一定的相似度。因此在实际的交叉点附近一般存在2个甚至2个以上的候选交叉点，如图4(a)所示。

(a) 透视变换-1 (b) 透视变换-2(a) Transformation-1 (b) Transformation-2

(a) SNR=21.97 dB (b) SNR=10.32 dB

(a) σ =1.0像素 (b) σ=2.0像素

(a) 旋转角为10° (b) 旋转角为30°(a) Rotation angle is 10° (b) Rotation angle is 30°

(a) 交叉角为90° (b) 交叉角为85°(a) Crossing angle is 90° (b) Crossing angle is 85°

(a) 候选交叉点分布(a) Distribution of candidate intersection points

采用基于欧氏距离的候选交叉点聚类方法，即相互距离小于设定的距离阈值dthresh的候选交叉点集聚为一类。

(7)

式中，dist(pi,j,pk,l)为像素点pi,j和像素点pk,l在图像上的欧式距离。

(8)

其中，x，y为像素点p的图像像素坐标。

理论上，交叉点灰度值应大于邻域灰度值，即从候选交叉点中选取灰度值最大的点作为交叉点检测结果输出。但实际应用中发现，图像灰度值大小会受到被观测物体表面粗糙度和反射率影响，导致交叉点灰度值不一定在邻域范围内总是最大，即交叉点能量中心和几何中心存在偏差。因此，采用灰度加权法计算聚类中心[8]。

(9)

选用灰度加权法计算聚类中心虽然使得本文算法更加鲁棒，即对于邻域灰度不完全满足高斯特性的交叉点，本文算法依然可以定位到交叉点几何中心附近，但对于灰度呈高斯分布且能量中心与几何中心重合的交叉点，该灰度加权法会使得交叉点定位精度有所降低，如图4(b)所示。

2 实验

实验目的在于测试算法在不同配置下的检测性能。算法性能通过两个参数表征：图像交叉点提取精度和图像交叉点检测率。

图像分辨率大小为768×1 024，根据不同配置要求仿真交叉点图像，交叉点几何中心真实坐标及交叉点数量视为已知：①对比不同配置条件下交叉点提取坐标和交叉点真实坐标，计算图像交叉点几何中心定位误差；②对比不同配置条件下交叉点检测数量和图像交叉点全部数量，计算图像交叉点检测率。

2.1 交叉角影响

仿真生成37×37的网格交叉点图像，交叉角大小分别设置为90°、85°、80°、75°、65°和60°，交叉线宽为7像素，利用本文算法对图像交叉点进行检测，高斯滤波器卷积模板为：

检测结果如图5所示。表1为不同交叉角配置下算法的检测性能。结果表明：算法适用于交叉角为65°～90°范围内的交叉点检测，几何中心定位精度优于0.6像素，检测率接近100%；当交叉角为60°时，算法对交叉点几何中心的定位精度为5.5像素，检测率仅为12%，算法失效。失效原因在于：随着交叉角的减小，交叉线重叠区域变大，交叉点邻域梯度分布不确定性增大，进而使得特征描述子大概率不能通过交叉点判定准则，最终影响算法定位精度及检测率；算法的几何中心定位精度和检测率与交叉角大小不存在绝对的单调性关系，整体趋势上，算法几何中心定位精度和检测率随交叉角增大而提高，但在某些局部，算法定位精度和检测率可能发生振荡，如交叉角为75°和65°的情况。

表1 不同交叉角配置下算法检测性能Tab.1 Detection functions of intersection points with different crossing angles

2.2 图像旋转角影响

仿真生成37×37的网格交叉点，交叉线宽为7像素，旋转角大小分别设置为10°、30°、50°、60°、70°、80°，利用本文算法对图像交叉点进行检测。高斯滤波器卷积模板与2.1节中相同，检测结果如图6所示，表2为不同旋转角配置下算法的检测性能。结果表明：算法可以很好地抵抗图像旋转，交叉点几何中心定位精度优于0.6像素，检测率接近100%。算法旋转不变的原因在于：图像的整体旋转只会影响交叉点邻域梯度的绝对分布，梯度的相对分布并未发生变化，而本文提出的特征描述子及交叉点判定准则只依赖于梯度的相对分布。

表2 不同旋转角配置下算法检测结果Tab.2 Detection results of intersection points with different image rotation angles

2.3 位置噪声影响

受相机和投影仪元器件加工工艺水平限制，交叉点能量中心和几何中心可能存在位置偏差，影响交叉点检测性能。仿真生成37×37的网格交叉点，交叉角为90°，交叉线宽为7像素，向交叉点能量中心加入不同等级(0均值、标准差σ=0.0～3.0像素)的高斯位置噪声，对交叉点几何中心进行检测，结果如图7所示。表3为不同位置噪声等级下算法的检测性能，结果表明：位置噪声等级由0.0像素提高到3.0像素过程中，交叉点定位精度略有降低，但不明显，检测率均为100%。原因在于：算法采用灰度加权法计算交叉点几何中心位置，对于能量中心和几何中心存在偏差的交叉点，依然可保证较高的交叉点定位精度。

表3 不同位置噪声等级下算法检测性能Tab.3 Detection functions of intersection points with different position noise levels

2.4 灰度噪声影响

电荷耦合器件(Charge Coupled Device,CCD)相机传感器的噪声源主要为暗电流噪声和光子散粒噪声，在数字图像上则表现为椒盐(颗粒)噪声。仿真生成37×37的网格交叉点，交叉角为90°，交叉线宽为7像素，图像灰度等级为0～255，向图像中加入不同等级(σ=0.0～30.0像素)的椒盐噪声，计算不同信噪比条件下算法的检测性能。信噪比定义如下：

(10)

式中：PS表示信号的有效功率；Pn表示噪声的有效功率；信噪比越大，表明图像质量越高。仿真结果如图8所示。表4为不同信噪比条件下算法检测性能。结果表明：交叉点定位误差随信噪比的提高而减小；当信噪比低于8.0 dB时，算法定位误差大于5.0像素、检测率低于50%，算法失效；当信噪比为27.97 dB时，交叉点定位精度优于0.5像素、检测率为100%。目前科学级CCD相机的信噪比一般大于60 dB，可满足算法的工程应用需求。

表4 不同信噪比条件下算法检测性能Tab.4 Detection functions of intersection points with different SNR

2.5 透视变换影响

仿真生成37×37的网格交叉点，交叉线宽为7像素，模拟相机对网格交叉点成像过程。若相机光轴垂直于网格平面，即为正视图。在正视图的基础上，随机改变光轴的空间指向，由于算法主要应用于结构光三维重建，因此设定光轴三自由度变动范围均小于30°，在此约束下，生成透视变换后的网格交叉点图像。对图像交叉点进行检测，高斯滤波器卷积模板与2.1节中相同。检测结果如图9所示。表5为不同透视变换配置下算法的检测性能。结果表明：在上述实验条件下，算法可以很好地抵抗图像透视变换，交叉点几何中心定位精度优于0.6像素，检测率大于90%。

表5 不同透视变换配置下算法检测性能Tab.5 Detection results of intersection points with different perspective transformations

3 结论

本文提出了一种基于梯度直方图的图像交叉点检测方法，具有较高的交叉点定位精度和检测率，可应用于结构光三维重建中的系统标定和形貌测量。其特点可归纳如下：①对图像交叉点中心的提取精度和检测率基本不受图像旋转角大小的影响；②对于交叉角大小具有一定的容忍度，即可用于检测交叉角在65°～90°之间的图像交叉点；③抗噪性能良好，可满足一般透视变换下的图像交叉点检测需求。

但是，本文方法对图像交叉点的检测不具有尺度不变性，图像的放大或缩小会直接影响交叉点的检测率和定位精度。考虑利用图像金字塔[14]，在每一层图像中独立检测、提取交叉点，然后基于欧式距离融合多尺度检测结果。此外，多视图之间的交叉点自动匹配问题也是下一步亟待解决的问题。