特征检测^[1]是计算机视觉和模式识别的经典问题之一，在计算机辅助设计、自动化检测、物体定位等领域有着十分重要的应用。平行性是一种常见的几何特征，在现实场景中广泛存在，比如斑马线、天线、楼梯等多呈现出平行结构；交通标识牌、建筑物、家居装饰等由于观察角度的原因其整体形状往往呈现出变形的效果，但局部的平行特性保持不变，表现为平行四边形或具有平行结构的多边形。

目前，针对图像平行结构检测的研究较少。直线平行性的判断最常用的思路是通过Hough变换得到直线，通过直线斜率相等判断两直线平行；Zheng等^[2]使用马尔可夫模型和维特比解码实现表格与横格稿纸中的平行线检测；Lin等^[3]对检测出的直线进行平移后计算误差，若误差小于某一阈值则认为直线平行。针对矩形和多边形检测的方法较多^[4–15]。广义Hough变换^[4]理论上可用于多边形检测，但由于参数超过2维带来的时间消耗和存储空间的急剧增大使得实际工作中几乎不采用该方法；加窗Hough变换^[5]通过判断Hough变换后的 $\theta $ 参数相等确定一对平行边，文献中的方法只适用于检测矩形，不适用于检测具有平行结构的任意多边形；Barnes等^[6–8]提出的方法首先获取图像边缘，然后依据正多边形的几何特性，利用后验概率定义正多边形的概率密度函数，通过计算正多边形边数和方向偏角来实现道路标识牌中正多边形的检测，仅适用于正多边形检测；Liu等^[9]提出了基于MRF（Markov random field）模型的方法，该方法首先基于全局背景信息从边缘图中提取线段并且合并邻近的平行线段，然后通过这些线段产生的MRF模型标记出矩形的边界线段，可检测出彩色图像中的矩形；Liu等^[10]依据三角形、正多边形和圆具有唯一内切圆这一几何特性，统计像素点到边缘点方向线的距离分布，由此计算每个像素的形状能量，获取内切圆的圆心和半径值，再由获得的形状轮廓点信息实现不同形状的检测。文献[11–13]实现了任意多边形的检测，另外还有一些其他的多边形检测方法^[14–15]。上述方法可实现具有平行结构的多边形的检测（如矩形、正多边形），但是，或利用多边形自身的结构特点^[5–8]，或需要预先给定多边形信息^[11–12]，或仅适用于特定的多边形检测^{[5–6,10,14–15]}，或通过线段组合实现任意多边形的检测^[13]，未利用组成多边形的线段间的平行特性，也不适用于图像中平行线的检测。

作者在充分研究平行结构特性的基础上，基于距离信息提出了平行算子的概念；在此基础上，对于图像中的任一边缘点，计算其平行点组，统计某一方向平行点组的数量，若大于阈值则利用Hough变换实现图像中平行直线的检测；随后，验证非平行直线2个交点间线段的存在性，并根据线段2个端点的位置，实现具有平行结构的多边形的检测。本文所提方法利用图像中平行点的信息，由点获得线，由线组合为多边形。相较于现有方法，本文方法更具有普遍性，适用范围更加广泛。

1 平行算子

对于图像中任一点 ${P_i}({x_i},{y_i})$ ，该点梯度为grad(P_i)= $[{g_{ix}},{g_{iy}}]$ ，其中， ${g_{ix}}$ 和 ${g_{iy}}$ 分别表示该点在x和y方向上的梯度分量。记点P_i的方向线^[16]为通过P_i且垂直于 ${\rm{grad}}({P_i})$ 的直线：

${l_i}{\text{：}}[{g_{ix}},{g_{iy}}, - ({g_{ix}}{x_i} + {g_{iy}}{y_i})]$

(1)

其中， ${g_{ix}}x + {g_{iy}}y - ({g_{ix}}{x_i} + {g_{iy}}{y_i}) = 0$ 。图1为三角形和矩形图像的边缘像素点（其梯度方向均垂直于该像素所在边）A～D与其方向线l_A～l_D，显然，图像轮廓点的方向线同该点所在边的方向一致。

对于任意两点 ${P_1}({x_1},{y_1})$ 和 ${P_2}({x_2},{y_2})$ ，记两点间的距离为：

${d_{{P_1}{P_2}}} = \sqrt {{{({x_1} - {x_2})}^2} + {{({y_1} - {y_2})}^2}} $

(2)

点P₁到点P₂方向线的距离定义为

${d_{{P_1}{l_{{P_2}}}}} = \left| {{a_2}{x_1} + {b_2}{y_1} + {c_2}} \right|/\sqrt {a_2^2 + b_2^2} $

(3)

其中， ${l_{{P_2}}}{\text{:}}[{g_{2x}},{g_{2y}}, - ({g_{2x}}{x_2} + {g_{2y}}{y_2})]$ ，则 ${a_2} = {g_{2x}}$ ， ${b_2} = {g_{2y}}$ ， ${c_2} = - {g_{2x}}{x_2} - {g_{2y}}{y_2}$ 。

同理，点P₂到点P₁方向线的距离为：

${d_{{P_2}{l_{{P_1}}}}} = \left| {{a_1}{x_2} + {b_1}{y_2} + {c_1}} \right|/\sqrt {a_1^2 + b_1^2} $

(4)

其中， ${a_1} = {g_{1x}}$ ， ${b_1} = {g_{1y}}$ ， ${c_1} = - {g_{1x}}{x_1} - {g_{1y}}{y_1}$ 。

通常 ${d_{{P_1}{l_{{P_2}}}}} \ne {d_{{P_2}{l_{{P_1}}}}}$ ，如图2中P₁与P₂点所示；当两点分别位于两条平行线上，如图2中点P₃和P₄所示，则 ${d_{{P_3}{l_{{P_4}}}}} = {d_{{P_4}{l_{{P_3}}}}}$ 但 ${d_{{P_3}{l_{{P_4}}}}} \ne {d_{{P_4}{P_3}}}$ ；对于图2中点P₄与P₅， ${d_{{P_4}{l_{{P_5}}}}} = {d_{{P_5}{l_{{P_4}}}}} = {d_{{P_4}{P_5}}}$ ，则定义点P₄与P₅为一组平行点对。

对于任意两点P_i和P_j，点P_j对P_i的平行算子定义为：

$E = {{\rm{e}}^{ - |{d_{{P_i}{l_{{P_j}}}}} + {d_{{P_j}{l_{{P_i}}}}} - 2 \cdot {d_{{P_i}{P_j}}}|}}$

(5)

当E=1时，表示 ${d_{{P_i}{l_{{P_j}}}}} = $ ${d_{{P_j}{l_{{P_i}}}}} = {d_{{P_i}{P_j}}}$ ，则点P_j与P_i平行；E越小，3个距离之间的差异越大，P_j与P_i的平行性越差。

2 平行结构检测 2.1 平行点组检测

假定点P_i位于直线L_i上，直线L_i为1组平行线 $\varGamma = \left\{ {{L_1},{L_2}, \cdots ,{L_i}, \cdots ,{L_\Lambda }} \right\}$ 中的1条，其中 $\varLambda $ 为平行线的数量，且 $\varLambda \ge 2$ 。对于平行线组 $\varGamma $ 中的任一直线 ${L_j}(i \ne j)$ ，其上均存在一点 $P_i'$ 与点P_i为平行点对。平行线组 $\varGamma $ 中与点P_i为平行点对的点的集合称为点P_i的平行点组，记为 ${G_{{P_i}}} = [{P_i},P_{i1}',P_{i2}', \cdots ,P_{i(\varLambda - 1)}']$ 。图像中平行点组的检测步骤如下：

1）确定有效边缘像素

对于图像I，首先利用Canny算子进行边缘检测，其边缘点集合为V， ${P_i} \in {{V}}$ 。考虑集合V内以P_i为中心、R（实验中R取固定值3）为半径的邻域 $\varOmega $ 中的任意一个边缘点P，若 ${d_{P{l_{{P_i}}}}} < {T_d}$ ，则点P为点P_i邻域 $\varOmega $ 内的支撑像素；反之，则不是。T_d取值越大，则确定的支撑像素越多，后续错误有效边缘像素被确定的概率增大，易引入干扰边缘点；T_d取值越小，则确定的支撑像素越少，真实有效边缘像素被排除的概率增加，导致有效边缘像素不足。文中T_d一般取2，即与P_i方向线距离小于2的点被判断为支撑像素。

计算 $\varOmega $ 内所有支撑像素（包括点P_i）梯度幅值之和 ${M_{\rm spt}}$ ，若 ${M_{\rm spt}} > {T_1}$ ，则点P_i为有效像素；反之，则不是。 ${T_1} = n \cdot T$ 为自适应阈值，主要由图像I的梯度确定，其中 $n = 2 \cdot R - 2$ （实验中R=3，则n=4）， $T = mean(Mag(I)) + {k_1} \cdot std(Mag(I))$ ，其中 $Mag( \cdot )$ 表示梯度幅值， $mean( \cdot )$ 和 $std( \cdot )$ 分别表示计算均值和标准差，k₁为调节系数，一般取 ${k_1} = 1 \text{～} 1.5$ 。T₁越大，真实边缘像素被排除的概率增大，不利于后续直线检测；T₁越小，弱边缘和孤立像素被确定为有效像素的概率增大，导致后续平行点组检测计算量增大。以T₁为阈值可找出位于显著边缘上的像素点，同时剔除孤立的边缘点，有效去除噪声，降低计算量。遍历集合V中的边缘点，获得图像I的有效像素集合 ${V'}$ ，如图4（c）所示。

图3（a）为图像的部分边缘，边缘点处使用不同的灰度表示该点的梯度幅值。对于整幅图像，假定计算后T=M。点P₁和P₂的梯度幅值分别为1.5 M和0.8 M，P₃-P₆的梯度幅值均等于M。指定R=3，则T₁=4M。对于点P₁-P₆，统计其邻域内的支撑像素，获得其梯度幅值之和分别为1.5 M、3.2 M、3 M、4 M、7 M和5 M，则边缘点P₅和P₆为图像的有效像素。图3（b）为对图3（a）所确定的有效像素结果，由图3可以看出，原始边缘中较弱的边缘（如点P₂所在边缘）或孤立的边缘点（如点P₁和P₃）被剔除，显著边缘被保留（如点P₅和P₆所在边缘，点P₄因不满足 ${M_{spt}} > {T_1}$ 故被剔除）。

2）计算有效像素的平行点组

对于 ${V'}$ 中的任意点p_i，根据式（5）计算 ${V'}$ 中所有有效像素对P_i的平行算子，获得与图像I尺寸相同的E_i。其中，

${E_i}(r,c) = \left\{ \!\!\!\!\!{\begin{array}{*{20}{c}}{{{\rm{e}}^{ - |{d_{{P_i}{l_{{P_j}}}}} + {d_{{P_j}{l_{{P_i}}}}} - 2 \cdot {d_{{P_i}{P_j}}}|}},{P_j}{\rm{ = }}\left( {r,c} \right),{P_j} \in V'\text{且}{P_j} \ne {P_i};}\\[3pt]{0,\qquad \text{其他}}\qquad \qquad \quad\end{array}} \right.$

(6)

在E_i中寻找局部极大值 $ Localmax({{E}_i})$ ，当Localmax $({{E}_i}) > {T_2}$ 时，认为极大值对应的点为点P_i的平行点，获得点p_i的平行点组 ${{G}_{{P_i}}} = [{P_i},P_{i1}',P_{i2}', \cdots ,P_{iK}']$ ，K（ $K \ge 1$ ）表示与P_i平行的点的个数。T₂值越大表示两点平行性越好，经过实验计算，T₂取0.95可使得到的平行点与理想平行点之间的误差小于1个像素，因此，实验中T₂=0.95。

3）获取图像中的平行点组集合

将 ${{G}_{{P_i}}}$ 中的点从 ${V'}$ 中删除，并重复步骤2），直至获得图像I中所有的平行点组集合 ${{V}_p} = [{{G}_{{P_1}}}{\rm{ }}{{G}_{{P_2}}}{\rm{ }} \cdots {\rm{ }}{{G}_{{P_{\prod }}}}]$ （ $ \prod $ 表示图像I中寻找到的平行点组个数），如图4（d）。

2.2 平行直线检测

对于图像I，利用获得的平行点组集合 ${{V}_p} = $ $[{{G}_{{P_1}}},{\rm{ }}{{G}_{{P_2}}}{\rm{, }} \cdots {\rm{, }}{{G}_{{P_{\prod}}}}]$ 实现平行线的检测，其步骤如下：

1）对于V_p中的任一点组 ${G_{{P_i}}}(1 \le i \le{\prod})$ ，记该点组梯度向量角为 ${\theta _i}$ （ ${\theta _i}$ 为该组平行点中第一个点的梯度向量角）。统计V_p中各平行点组的梯度向量角，获得其直方图 ${{H}_\theta } = \left[ {{a_{{\theta _1}}},{a_{{\theta _2}}}, \cdots ,{a_{{\theta _{\prod}}}}} \right]$ ，如图4（e）所示，其中， ${a_{{\theta _i}}}$ 表示梯度向量角为 ${\theta _i}$ 的平行点组的个数。

2）若 ${a_{{\theta _i}}} > {T_3}$ ， ${T_3} = mean({{H}_\theta }) + {k_3} \cdot std({{H}_\theta })$ ，其中 $mean({{H}_\theta })$ 和 $std({{H}_\theta })$ 分别表示直方图 ${{H}_\theta }$ 的均值和标准差，k₃为调节系数，则图像中存在梯度向量角为 ${\theta _i}$ 的一组平行线。T₃值太大，会丢失正确的梯度向量角，导致平行线漏检；T₃值太小，会导致冗余平行线组的检测。实验中一般取 ${k_3} = 0$ ～2，以合理控制T₃值。从平行点组 ${{V}_p} = [{{G}_{{P_1}}}{\rm{ }}{{G}_{{P_2}}}{\rm{ }} \cdots {\rm{ }}{{G}_{{P_{\prod}}}}]$ 中提取梯度向量角在 $\left[ {{\theta _i} - 2,{\theta _i} + 2} \right]$ 范围内的点组，记为点集V₁。

3）对于点集V₁，使用Hough变换，得到梯度向量角为 ${\theta _i}$ 的平行线组 ${\varGamma _{_{{\theta _i}}}} = \{ {l_{1{\theta _i}}},{l_2}_{{\theta _i}}, \cdots ,{l_{Q{\theta _i}}}\} $ ，该平行线组共有Q条直线。

4）重复步骤2）和3），检测出图像中具有不同梯度向量角的多组平行线 $\varPhi = \{ {\varGamma _{{\theta _1}}},{\varGamma _{{\theta _2}}}, \cdots ,{\varGamma _{{\theta _N}}}\} $ ，N为获取的平行线组的个数。图4（f）显示了图像I的所有平行线，不同颜色表示不同的平行线组。

2.3 具有平行结构的多边形检测

对于获取的直线集合 $\varPhi = \{ {\varGamma _{{\theta _1}}},{\varGamma _{{\theta _2}}}, \cdots ,{\varGamma _{{\theta _N}}}\} $ ，验证这些直线是否构成闭合的多边形（本算法不考虑一条边同时属于两个多边形的情况）。其步骤如下：

1）计算各直线的交点，并验证各交点确定的线段的存在性。基本思想为：若一条线段存在，则该线段附近应存在足够的边缘点。对于任意2个交点M₁和M₂，考虑以线段M₁M₂为中心轴、宽度为3的矩形区域，记该矩形区域内图像有效像素个数为N₁，线段M₁M₂的长度为 $Length$ ，若N₁满足 ${N_1} \ge {T_4} \cdot Length$ ，则该线段存在。T₄为阈值，经过实验统计，阈值T₄取0.90～0.95可保证存在足够的边缘点。设定矩形区域宽度为3 的原因是考虑到图像点是离散的，线段扫过像素点的理论位置与实际边缘点位置可能存在误差。获取图像中有效线段集合 ${S} = \{ {{S}_1},{{S}_2}, \cdots ,{{S}_i}, \cdots {{S}_W}\} $ ，其中 ${{S}_i} = \left( {{P_{i1}},{P_{i2}}} \right)$ 表示S中的第i条线段， ${P_{i1}}$ 和 ${P_{i2}}$ 分别表示线段S_i的起点和终点。

2）在集合S中检测一个封闭多边形 $Polygon$ 。其步骤如下：

① $Polygon = \left\{ {{\mathit{\boldsymbol{S}}_{P1}}} \right\}$ ，其中， ${\mathit{\boldsymbol{S}}_{P1}}$ 是多边形 $Polygon$ 的第一条线段。

②对于集合S中的 ${\mathit{\boldsymbol{S}}_i}(i \ge 1)$ ，若 ${P_{i1}} = {P_{(i - 1)2}}$ 或者 ${P_{i2}} = {P_{(i - 1)2}}$ ，则 ${\mathit{\boldsymbol{S}}_{Pi}} = {\mathit{\boldsymbol{S}}_i}$ 。 ${\mathit{\boldsymbol{S}}_{Pi}}$ 表示 $Polygon$ 的第i条线段， ${P_{(i - 1)2}}$ 表示第 $i - 1$ 条线段 ${\mathit{\boldsymbol{S}}_{P(i - 1)}}$ 没有与之前线段相连的端点。

③判断 $Polygon$ 中的线段是否构成多边形。 $Polygon = \left\{ {{\mathit{\boldsymbol{S}}_{P1}}, \cdots ,{\mathit{\boldsymbol{S}}_{Pi}}} \right\}$ ，当 $i \ge 3$ 时，判断 $Polygon$ 是否闭合。若 ${P_{i2}}$ （ ${P_{i2}}$ 表示第i条线段 ${\mathit{\boldsymbol{S}}_{Pi}}$ 没有与之前线段相连的端点）与P₁₁（P₁₁表示第一条线段 ${\mathit{\boldsymbol{S}}_{P1}}$ 的起点）相等，则 $Polygon$ 是一个封闭图形，检测结束，从S中删除组成 $Polygon$ 的线段；若不相等，则在剩余的线段中重复步骤②和③，继续寻找 $Polygon$ 的其他组成线段。

④若在 $Polygon$ 中，所有的线段经过验证之后无法闭合，则这些线段不构成封闭多边形，从S中删除这些线段。

3）重复步骤2），在集合S中确定所有封闭多边形 $\{ {Polygon_1}, {Polygon_2}, \cdots,{Polygon_O}\} $ ，如图4（g） 所示。

本文提出的图像中平行结构的检测算法流程如图4所示。首先获取边缘图中的有效像素，然后利用平行算子得到平行点组；接着统计平行点组的梯度方向，利用Hough变换得到平行直线；最后验证直线交点之间线段的存在性，将存在的线段组合为封闭多边形。

3 实验结果 3.1 模拟图像实验

图5以模拟图形为例研究了噪声影响下本文算法对图像平行结构的检测结果。第1行为添加高斯噪声结果，第2行为添加椒盐噪声结果， $\sigma $ 均为0.1。由实验结果可知，本文所提算法可以抵抗一定强度的噪声，这是由于计算过程中噪声边缘与真实图像边缘相比不易形成有效像素所致。如图5（c）所示，提取有效像素后，由噪声产生的边缘点被很好地滤除，图像本身的边缘信息被完整保留。

3.2 真实图像实验

图6为图像的平行点组检测结果。图6（d）中，菱形表示指定像素点，星号表示与指定像素点平行的点，不同的颜色代表不同的平行点组。图6（d）中白玉环的边缘非常理想，因此在平行精度为0.95的条件下检测结果非常好；斑马线图片中噪声比较大，影响梯度值的计算，在平行精度为0.95时由于两点之间的平行算子结果不满足要求而出现漏检。图6中显示了平行精度为0.94时的检测结果。可以看出，本文定义的平行算子能够很好地检测到实际图像中的平行点组，并且在平行精度要求不高的条件下可以抵抗较大的噪声。

图7为本文算法对平行直线的检测结果。由图7可以看出，存在的水平、竖直和任意角度的平行线均被正确检出。

图8为本文算法对具有平行结构的多边形检测结果。图8（g）所示的银盘中的正八边形检测结果不够精确，这是由于图像本身光照原因使得右侧上下两条边产生两个边缘，经过平行算子提取平行点组，对每个方向只提取Hough变换峰值最大的两条直线导致。图8（i）中2个平行嵌套的三角形被正确检测。由可以看出，单个或多个具有平行结构的多边形（包括三角形）均被成功检测出来，因此本文算法具有很好的通用性。

综合上述实验结果，本文提出的基于平行算子图像平行结构检测算法可以准确检测出图像中的平行直线及具有平行结构的多边形。

4 时间复杂度分析

对算法的时间复杂度进行分析。记图像边缘点个数为N。对于平行直线检测，假设图像中存在一组平行直线。确定有效像素的时间复杂度为 $O(N)$ ；记得到的有效像素个数为n₁，对每个有效像素使用平行算子计算其平行点组，其时间复杂度为 $O({n_1})$ 。假设所有有效像素均存在平行点，则所有有效像素参与Hough变换，时间复杂度为 $O(\lambda {n_1})$ ，其中， $\lambda $ 表示[0，180°]上角度的量化数目，因此算法的时间复杂度为 $O(N + {n_1} + \lambda {n_1})$ ，其中， ${n_1} < N$ 。使用Hough变换对边缘点个数为N的图像进行直线检测，其时间复杂度为 $O(\lambda N)$ ，所提算法检测直线的时间复杂度较Hough变换有所降低。同时，可知，当 ${n_1} \ll N$ 时，算法的时间消耗主要用于确定图像中的有效像素，有效像素的提取消除了大量随机边缘点对直线检测的干扰，避免了Hough变换产生的直线断裂、直线拟合不够准确的问题，为后续准确的直线检测提供了保障。

对于具有平行结构的多边形检测，假设图像中存在一个m边形（m为2的倍数）。确定有效像素及平行点组的时间复杂度分别为 $O(N)$ 和 $O({n_1})$ 。若所有的有效像素均存在平行点，平行点组的梯度向量角集中在m/2个峰值，每个峰值对应的像素点分别参与Hough变换，则该步骤的时间复杂度仍为 $O(\lambda {n_1})$ ；对于获取的m条直线，可产生 $m(m - 2)/2$ 个交点（考虑到每条边与其平行的边没有交点），两个交点确定一条线段，则判断线段有效性的时间复杂度为 $O({m^4})$ 。因此多边形检测的时间复杂度为 $O(N + {n_1} + \lambda {n_1} + {m^4})$ 。与平行直线检测相比，多边形检测时增加了线段有效性验证的时间消耗，但需注意到，实际应用中m取值一般小于10，因此本文所提算法效率较高。

5 结　论

利用平行点对间的距离特性，提出了平行算子概念，并将其用于图像中平行线及具有平行结构的多边形的检测。实验结果表明，本文算法能准确检测出图像中的平行结构，算法准确度高，具有较好的抗干扰能力。本文主要结论：

1）根据平行线上点对之间的距离关系，提出了平行算子的概念。

2）将平行算子应用于平行线和具有平行结构的多边形检测，为相关研究提供一种新思路。

3）提出一种有效像素提取方法，使算法具有较强的抗噪声能力，同时降低算法的计算量。