摘要：在图像识别中，矩形作为最常见的人工图形之一，对它的检测有着广泛应用。提出了一种基于边缘直线检测的矩形提取方法。该方法首先对图像进行边缘检测，得到边缘图像；然后对边缘图像进行直线检测，得到图像中所有的直线段；最后对满足矩形特征的直线段进行组合，提取图像中可能的矩形。实验结果表明，该方法具有较好的抗干扰能力，且运算速度快，是一种有效的矩形提取方法。

关键词：矩形提取；图像识别；边缘检测；直线检测

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）31-0182-03

An Approach to Rectangle Extraction Based on Edge Line Detection

BU Fei-yu

（Institute of Information and Electronic Engineering， Hunan City University， Yiyang 413000， China）

Abstract： In the image recognition， rectangle as one of the most common man-made shapes， detection of it has a wide application. An approach Based on edge line detection to extract rectangles in images is presented in this paper. The method firstly applies edge detection on the input image and obtains the edge map； secondly， it performs line detection to the edge map and obtains all straight line segments； thirdly， the line segments that satisfy the rectangular feature are combined to extract possible rectangles in the image. Experimental results show that the method has better anti-jamming ability， and it is fast and effective.

Keywords： rectangle extraction； image recognition； edge detection； line detection

1 概述

目標检测是图像识别中一个非常关键的任务。矩形是最常见的人工图形之一，对它的检测在图像识别系统中不可缺少。如车牌识别、广告牌检测等计算机视觉应用；从卫星遥感图像或飞机航拍图像中提取建筑物、车辆目标等。另外，矩形标识可用作无人机、智能机器人的定位地标，因此矩形检测可以用于机器人导航。

矩形检测的深入系统研究是最近若干年才开始的。一种矩形检测方法[1]是用Canny边缘检测算法得到线段，然后从这些线段中检测出T型和L型连接，将它们分解成更小的片段，再将小的片段进行联合线性化组成更长的线段。Tao等人[2]则将轮廓跟踪和直线分割技术应用到边缘图像中，由此获得图像中的直线段，然后通过分析和合并直线段来构造矩形。Jung和Schram提出了一种窗口化的霍夫变换[3]，先运用霍夫变换获得候选直线，然后通过检测候选直线的组合能否满足矩形性质来检测矩形，但该方法中的一些参数需要调试。

Y.Liu 等人[4]提出了一种结合全局轮廓线段检测和马尔可夫随机域模型的矩形检测算法，从彩色图像中提取矩形目标。算法先经边缘检测获得边缘图像及边缘像素的梯度信息，然后从边缘图像中抽取线段，并将平行且相邻的线段合并；最后，集结在未知矩形边缘的线段会被马尔可夫随机域模型标记。该算法的弱点是过度依赖于边缘检测算法。

国内，王红军等人[5]提出了一种实用的基于Hough变换和最小二乘法相结合的矩形几何提取和校正算法。该算法通过Hough算法检测出直线，在检测到的直线邻域内，通过最小二乘法拟合得到更精确的直线，由4条直线确定矩形。任玲辉等人[6]提出了一种灰度投影积分极值法的矩形检测方法：把待测图像沿0～π方向进行投影得到灰度投影积分（GPI）矩阵，求得矩阵中极值点的位置，将其保存为新的矩阵GPIEV，并在GPIEV矩阵中搜索平行线重构矩形，从而完成矩形检测。

本文提出一种基于边缘直线检测的矩形提取方法。该方法首先通过改进的Robert边缘检测算子得到输入图像的灰度边缘图像，并将其二值化；然后采用一种基于“有向单连通链”的直线检测算法，在二值图像中提取所有的直线段；最后对满足矩形特征的直线段进行组合，获得可能的矩形。实验结果表明，该方法具有较好的抗干扰能力，且运算速度快，是一种可行的方法。

2 基于边缘直线检测的矩形提取

2.1 边缘检测

物体的边缘是由灰度不连续性所形成的。经典的边缘提取方法是考察图像的每个像素在某个邻域内灰度的变化，利用边缘邻近一阶或二阶方向导数变化规律，用简单的方法检测边缘。这种方法称为边缘检测局部算子法。常用的检测算子有Robert算子、Sobel算子、Prewitt算子以及Krisch算子等[7]。在这里选用Robert算子进行边缘检测。Robert边缘检测算子是一种利用局部差分寻找边缘的算子，由下面的公式（1）给出。其中f（x，y）为输入的灰度图像，g（x，y）为输出的边缘图像。

[g（x，y）=（f（x+1，y+1）-f（x，y））2+（f（x+1，y）-f（x，y+1））2] （1）

为了加快运算速度和突出边缘，我们对Robert算子稍加改进，改进后的算子由下面的公式（2）给出：

[g（x，y）=|f（x+1，y+1）-f（x-1，y-1）|+|f（x+1，y-1）-f（x-1，y+1）|] （2）

利用公式（2）进行检测边缘具有边缘定位较准确、边缘较连贯、运算速度较快的优点。为了与人的视觉相对应，对检测到边缘图像进行反色变换。（图2）

2.2 边缘图像二值化

由于我们只需要得到每个矩形目标的边缘，仅需要那些灰度变化比较陡的部分，而灰度变化平滑的区域可以省略，同时考虑到下一步直线提取的需要，在这里要把边缘图像二值化。为更好地适应质量不佳的图像，以及考虑到运算速度的因素，在这里采用了一种改进的基于最大类间方差的二值化方法[8]来对边缘图像进行二值化。（图3）

2.3 直线检测

直线检测，采用的是一种基于“有向单连通链”的直线检测算法[9]。在该算法中，有向单连通链是一种黑像素游程序列。在引入一定约束信息的条件下，对有向单连通链进行拆分和合并，通过直线质量的比较，有效地去除伪直线，补全断裂的直线，可以准确而快速地提取直线。由于上述图像边缘检测中会存在较多的噪声，我们必须将质量不佳且长度较短的直线当噪声处理，予以排除。对于检测到的质量较好且长度较长的直线，将其分成两组：与水平轴的夹角小于等于45度的直线属于横线组，与垂直轴的夹角小于45度的直线属于竖线组，将横线从上到下排序，将竖线从左到右排序。

2.4 矩形提取

设在2.3中直线检测找到的横线有m条，记为HorLine[i]，i=0，1，……，m-1；竖线有n条，记为VerLine[j]，j=0，1，……，n-1；又设到目前为止已经找到的矩形有p个，记为Rect[k]，k=0，1，……p-1，每个Rect[k]记录了该对应矩形的上、下、左、右四条边缘直线。则寻找下一个矩形的四条边缘直线的算法的步骤如下：

step1：按顺序从横线组HorLine[ ]中找出一条不属于任何一个已找到的矩形Rect[k]的边的横线HorLine[i]，若i=m-1，则转step5；否则转step2。

step2：从HorLine[ ]中找出所有位于HorLine[i]下方且与HorLine[i]平行的直线，这里平行可看作兩条直线的夹角小于2度。若找不到与HorLine[i]平行的直线，令i=i+1后转step1；否则，设找到了m1条与横线HorLine[i] 平行的直线，将HorLine[i]及其对应的平行线记录为HorEdgeLine[i1]，i1=0，1，……，m1；转step3。

step3：假设HorEdgeLine[0]为当前要找矩形目标的上边缘直线，HorEdgeLine[i1]（i1=1，……，m1）为该矩形目标的下边缘直线，看能否从竖线组VerLine[ ]中，找到两条彼此平行且垂直于HorEdgeLine[0]的竖线VerLine[j1]和VerLine[j2]（VerLine[j2]位于VerLine[j1]右边），使得HorEdgeLine[0]、HorEdgeLine[i1]、 VerLine[j1]、VerLine[j2]正好构成一个矩形。构成矩形的条件由下面的不等式（3）和（4）限定。若构成一个矩形，则说明找到了当前要找的矩形目标的四条边缘直线，将其记录于Rect[p]中，令p=p+1，转step1；否则转step4。

step4：令i1 = i1+1，转step3。

step5：寻找结束。

设横线HorEdgeLine[0]左端点到竖线VerLine[j1]上端点的距离为DistTL，其右端点到竖线VerLine[j2]上端点的距离为DistTR；横线HorEdgeLine[i1]左端点到竖线VerLine[j1]下端点的距离为DistBL，其右端点到竖线VerLine[j2]的下端点的距离为DistBR。

又设VerLine[j1]、VerLine[j2]、HorEdgeLine[0]、HorEdgeLine[i1]四条线的长度分别为LenL、LenR、LenT、LenB，记d = max（20，（LenT+LenB+LenL+LenR）/100），则在step3中，判断这四条直线是否正好构成一个矩形须同时满足下述两个条件：

条件1：DistTL+DistTR+DistBL+DistBR<6d （3）

条件2：max（DistTL，DistTR，DistBL，DistBR）<2d （4）

3 实验结果

本文方法用VC++6.0实现，输入为灰度图像，尺寸1200×900像素。测试环境：CPU： AMD Athlon II X2 3.0GHz；内存2GB；系统WINDOWS XP。形

1） 速度：从边缘检测，边缘图像二值化、直线检测到完成矩形提取共耗时0.169秒.

2） 准确率：图4中三个矩形目标：书本、放在书本上的遥控器，书本上印刷的条形码，均被准确地提取出来。

4 结论

本文提出了一种基于边缘直线检测的矩形目标提取方法。先检测图像中的边缘点，再检测出由边缘点构成的直线，最后寻找出图像中每个矩形目标的四条边缘直线所构成的矩形，从而可将图像中每个矩形目标提取出来。实验证明，该算法速度较快，准确度也较高。另外，本方法改进后也可应用于多矩形目标的彩色图像分割。

参考文献：

[1] Lin C， Nevatia R. Building detection and description from a single intensity image. Computer Vision and Image Understanding. 1998， 72（2）：101-121.

[2] Tao W， Tian J， Liu J. A new approach to extract rectangular building from aerial urban images. In： 6th International Conference on Signal Processing. IEEE， 2002， 1：143-146.

[3] Jung CR. Schramm R. Rectangle detection Based on a windowed Hough transform. In： Proceedings of the 17th Brazilian Symposium on Computer Graphics and Image Processing. IEEE， 2004， 113-120.

[4] Liu Y. Ikenaga T. Goto S. An MRF model-based approach to the detection of rectangular shape objects in color images. In： 5th IEEE International Conference on Cognitive Informatics. IEEE， 2006， 1：386-393.

[5] 王红军， 陈临强， 王磊.机器视觉中矩形几何提取和校正[J].机电工程，2010，27（4）：95-111.

[6] 任玲辉， 刘凯， 张海燕， 等.灰度投影积分极值法的矩形检测[J].计算机工程，2012，38（8）：159-163.

[7] 谭艳， 王宇俊，李飞龙， 等.几种典型的图像边缘检测算法的分析比较[J].电脑知识与技术，2012 ， 8 （3）：1604-1608.

[8] 卜飞宇， 祝青， 王涛.一种改进的基于最大类间方差的二值化方法[J].电脑知识与技术，2015（5）：188-189.

[9] 郑冶枫， 刘长松， 丁晓青， 等.基于有向单连通链的表格框线检测算法[J].软件学报，2002，13（4）：790-796.