基于Linemod-2D与Otsu的多目标工件快速分拣方法研究*

杨俊杰，袁清珂，梁杰超，叶凯冬

(广东工业大学机电工程学院，广州 510006)

0 引言

机器视觉已逐渐应用于工业的各种场景，为了提高系统的柔性，通常机器视觉的应用需要面临着复杂多变的作业要求。在多目标识别中，若干不同的物体以随机的姿态和数量出现在相机视野内，需要识别并定位不同的工件以作不同用途。鲁晟燚等[1]使用Hu不变矩特征匹配到候选零件后，配合SIFT特征匹配进一步分拣，验证了其对螺母等规则零部件分拣的有效性，但Hu不变矩模板匹配比较依赖于稳定的环境和图像预处理的效果，且SIFT特征点的提取过程繁杂；陈洵凛等[2]在基于灰度的归一化积相关匹配法的基础上，采用金字塔分层策略和遗传算法提高大幅面多目标识别的实时性，但是未考虑同一平面中目标姿态不一致的情况，并且智能搜索算法的参数复杂。方祝平等[3]同样使用归一化积相关模板匹配建立了多目标识别与分类系统，实现了多位姿多目标的识别，但没有解决灰度模板匹配存在的实时性不高问题。

而基于边缘梯度的模板匹配的特征点提取和匹配过程简单高效，配合金字塔分层策略能实现高实时性和高准确性，能够作为解决工业需求的较佳选择[5]，其缺点是不具备旋转不变性。HINTERSTOISSER等[6]提出另一种基于边缘梯度的模板匹配Linemod，该算法将梯度离散量化为8个方向，制作所有量化方向的预响应表能使在线计算相似性的过程转换为快速查表的过程，促使速度大幅提升，但精度缺陷明显。张仁政[7]将Linemod用于物流行业分拣。陈全义等[8]为了提高Linemod-2D的精度，将方向量化个数加倍，在金字塔底层采用角度量化精度更高的匹配策略进行精匹配，但不可避免地带来了更多的运算时间消耗。

本文提出一种基于边缘梯度的多目标工件快速分拣方法，采用Linemod-2D的加速方式在金字塔顶层搜寻所有姿态的工件，并且使用双阈值最大类间方差法自动获取梯度幅值筛选阈值以保证分拣质量；而为了结合文献[5]传统匹配准确性高的优点，将其运用在精匹配的过程。

1 传统基于边缘特征的模板匹配

1.1 相似性度量

基于边缘特征模板匹配用轮廓边缘点作为模板特征点，计算所有模板特征点与待搜索图像中对应位置的梯度向量归一化点积的平均值作为相似性，如式(1)所示。

(1)

上式计算模板M在滑窗过程中经过待搜索图像S的位置(x,y)的相似性σ，0≤σ≤1。其中，N为模板特征点总数，md为模板某边缘特征的单位梯度向量，(xi,yi)为第i个特征点相对于模板右侧和上侧的坐标，sd为图像S对应于第i个特征点的单位梯度向量。该相似性度量不受光照的影响，且对噪声具有鲁棒性。为了提高实时性，可采用文献[5]中的停止标准及时停止对非目标的度量。

1.2 金字塔分层策略

在原图尺寸上进行滑窗匹配即对全图所有位置进行式(1)相似性度量会耗费大量时间。为提高实时性，使用金字塔分层搜索策略。首先用2×2高斯或均值滤波器对待搜索图像S进行n次降采样，每次采样后图像宽高减半，保存得到的低分辨率图像并作为金字塔的一层。将最后一次采样图像作为金字塔顶层，其尺寸为S的(1/4)n倍，只需耗费极短的时间就能在顶层进行全局滑窗匹配，即粗匹配。将粗匹配过程中相似性大于设定阈值的位置作为候选点，下一层的精匹配只在候选点邻域内进行。从金字塔顶层到底层，进行了由粗到精的匹配搜寻。

然而，这种基于边缘特征的模板匹配不足之处在于不具备旋转不变性，要预先按照合适的角度步长旋转模板才能定位不同旋转姿态的工件。然后在金字塔顶层用模板的所有旋转姿态依次进行滑窗匹配，这期间需要执行过多的乘法和除法运算。要达到耗费更少时间则需要再降采样若干次，模板层数越多，丢失特征越多，并且逐层精匹配过程中经历的层数增多。

2 Linemod-2D模板匹配

为解决传统边缘特征模板匹配在金字塔顶层运算量大的问题，本文采取Linemod-2D的方式在金字塔顶层进行粗匹配。Linemod-2D被证明用超过3000个模板在640×480分辨率图片中搜寻目标仍能达到实时性[6]，主要得益于预响应表和线性存储配合SSE技术能使在线计算相似性的过程转换为快速查表的过程，消除了大量的乘除运算，模板总数越多带来的效益越明显，适用于多种类型目标搜寻。

2.1 相似性度量

对于模板上的每个特征点，Linemod-2D计算特征点i在图像S的(x+xi,y+yi)位置邻域内的最大得分，如式(2)所示。

(2)

式中，R为图像S中(x+xi,y+yi)位置处的T×T邻域；(tx,ty)∈R。这种相似性度量具备式(1)对光照、噪声的鲁棒性，同时对目标的微小变形更稳健。

2.2 提高算法实时性的措施

接下来阐述Linemod-2D如何进行此种度量。由于采取式(2)的度量方式，Linemod-2D可以T个像素步长进行滑窗搜索，并且为了避免匹配过程中每个特征点都要寻找最相似的梯度方向而带来的时间损耗，Linemod-2D在匹配前针对待搜索图像进行了4个步骤：

步骤1：将图像的梯度方向量化为8个方向，并用二进制来表示，即二进制数中每一位代表一个离散方向，如图1所示。

步骤2：每个量化方向在其T×T邻域中扩散，所以方向扩散后一个像素数值可包含多个方向，如图2所示。

步骤3：预先为每个离散方向计算预响应表，预响应表中每个像素数值保存着对应离散方向在此位置的最大得分，如图3所示两个方向的预响应表。

步骤4：最后对每个预响应表进行线性存储，之便可采用SSE技术并行累加出模板在待搜索图像上所有位置的得分[6]。

图1 梯度方向量化 图2 方向扩散

图3 制作00000001和00001000方向的预响应表

经过上述4个步骤后，式(2)的相似性度量就能由查表来完成，充分发挥计算机的性能。但制作高分辨率图像的预响应表具有耗费大量时间的缺点，并且在逐层精匹配的过程中，待匹配图像中只有少量区域被访问，所以制作下层的预响应表带来的效益不高。而且由于方向扩散，Linemod-2D的精度不高，其总会带来0～T个像素的误差。传统边缘模板匹配采取逐像素遍历滑窗，并没有此精度问题。所以本文采取基于Linemod-2D进行粗匹配后，继续使用传统的边缘模板匹配进行逐层精匹配。

3 金字塔顶层的方向筛选处理

3.1 筛选方式

进行方向扩散前需要作一次筛选，梯度幅值达到某个阈值K的边缘才会保留下来，如图4所示。当该阈值过小，则大部分梯度方向被保留，这会导致很多强度低的非边缘都参与相似性度量，从而顶层得到的候选点数量增多，这会使匹配分拣过程变长；当阈值过大，则过多梯度方向被剔除，参与相似性度量的梯度方向数量不足，可能导致未能搜寻到目标。为避免以上问题，通常需要人工多次调试阈值K。为解决该问题，使用最大类间方差法对梯度幅值直方图进行计算[9-10]，自适应获取分割阈值。

图4 待搜索图像金字塔顶层的方向筛选

3.2 基于Otsu的自适应梯度幅值阈值

图5 待搜索图像在金字塔顶层的梯度幅值直方图

最大类间方差法原本用于灰度阈值分割，计算一幅图像中区分前景和背景的最小错分概率阈值。由于边缘和非边缘区域主要靠梯度强度来判别，在此将其计算对象改为梯度幅值，目的在于将不靠近边缘的低幅值像素和正处边缘或者其周围的高幅值像素区分开。如图5所示，在梯度幅值直方图中，非边缘区域的低幅值数量很大，真正的边缘占极少数，直方图变化逐渐趋于平缓则过渡到边缘附近的梯度幅值[11]。文献[9-10]都用Otsu确定Canny算子的高低阈值，前者将梯度分为两类，计算出满足类间最大方差的阈值作为Canny高阈值，低阈值为高阈值的0.5倍；后者将梯度从小到大分为C0、C1和C2三类，计算出类内最小方差的两个阈值后，Canny低阈值为区分C0和C1阈值，高阈值为区分C1和C2的阈值。为了保证顶层的识别率，不仅要保留边缘的梯度，还要保留边缘附近的梯度，以免丢失目标。而采取文献[10]中分三类的方式能较安全地区分非边缘和边缘附近的区域，通过求出式(3)F函数的最大值则得到低阈值Tl和高阈值Th，然后把K值设置为Tl。

F(tl,th)=w0(u0-u)2+w1(u1-u)2+w2(u2-u)2

(3)

式中，C0类的强度等级为0～Tl-1；C1类的强度等级为Tl～Th-1；C2类的强度等级为Th到最大梯度幅值；w0、w1、w2分别为C0、C1、C2类出现的概率；u0、u1、u2分别为三者的平均强度等级；u为整幅图的平均强度。图5为某张待搜索图像顶层的梯度直方图，87和251分别为双阈值Otsu计算得到的Tl和Th，132为单阈值Otsu的结果。

4 算法流程

算法流程如图6所示，主要包括创建模板、建立待搜索图像金字塔和模板匹配3个部分。

图6 匹配总流程

4.1 创建模板

为保留模板的细节信息，采用2×2高斯滤波器对模板图像进行降采样从而得到图像金字塔。为了匹配旋转的目标，需要金字塔每层的模板进行旋转，旋转步长由模板本身的尺寸决定，模板越大，每次旋转的角度应该越小[12]。使用Sobel算子获取金字塔中各模板图像的X和Y方向的梯度，并计算幅值，然后用Canny提取边缘轮廓。Canny 算子通过非极大值抑制和双阈值法能够得到精度高且较为完整的边缘图像，同时具有一定的噪声抑制能力。考虑到邻近轮廓点之间的梯度特征差异很小，为了兼顾实时性，对轮廓进行均匀离散采样，如图7所示。按照此方式提取的边缘特征点在轮廓曲率变化明显处相对更加密集，进一步精炼了模板的特征[13]。均匀离散采样后，将每个特征点的梯度信息保存下来，至此便完成了某个旋转角度的模板在金字塔某层的特征点提取。最后，对金字塔顶层的各个模板进行角度量化处理。

图7 模板特征点提取

4.2 建立待搜索图像金字塔

使用2×2高斯滤波器建立待搜索图像的金字塔。并且在金字塔每层都采用Sobel滤波器提取图像X、Y方向的梯度信息。在顶层，计算该层图像的梯度方向和幅值，从梯度幅值直方图计算出自适应阈值，然后将梯度方向进行量化处理，并筛选出幅值大于设置阈值的量化方向，而后执行Linemod-2D的方向扩散、计算预响应表和线性存储步骤，便于快速查表。

4.3 模板匹配

在金字塔顶层进行快速粗匹配，用不同旋转角度的模板在线查表，计算模板在金字塔顶层所有位姿的得分，提取得分大于设定阈值且属于极大值的X,Y,Θ作为候选点。然后逐层精匹配的过程中，都会在上一层得到的候选点的坐标邻域、角度邻域内进行匹配，通过式(1)的相似性度量计算得到候选点邻域中的极大值点作为新的候选点。

5 实验结果与分析

5.1 实验平台

实验平台如图8所示，主要由六自由度机器人、工业相机、相机镜头和计算机组成。其中，分拣机器人为广州数控RB08机器人；工业相机型号为MV-CA013-20GM；相机镜头型号为MVL-HF0828M-6MP。工件在相机视野内工作平台上随意摆放。

将图9中的工件1、2和3三种工件各5个摆放在工作台上，用工业相机拍摄50张随机摆放的工件图像用于多目标识别实验，其中待搜索图像的分辨率为1280×1024像素，工件1，2，3模板图像的分辨率分别为340×180，340×180，180×180像素。接下来所有实验中，金字塔层数为4层，相似性阈值为0.8，改进算法中金字塔顶层的扩散大小T=2像素。

图8 实验平台 图9 工件实物图

5.2 实验一

由于工件3形状较为复杂，其识别率容易受到梯度阈值K的影响，所以本实验仅观察K对识别工件3的影响，实验方式为每匹配50张采集图像则用不同K值来进行。图10a记录了顶层匹配候选点结果数量的平均值随着K的增加而减少。图10b表示当K=102时，识别率从100%开始不断下降。图10a和图10b表明当K不断递增时，待搜索图像的顶层中参与相似性度量的梯度向量变少，导致候选点的数量减少进而缩短精匹配过程的时间，但也加大了目标未被识别的危险，所以选择合适的K值是有意义的。50张采集图像中，用双阈值Otsu计算得到的阈值Tl范围为73～91，均小于102，所以K=Tl时能保证工件3全部被识别到；而单阈值Otsu计算结果范围为123～139，必然丢失一些目标。本实验表明使用双阈值Otsu选择K值能保证识别率和匹配效率。

(a) 顶层候选点数量随阈值K变化 (b) 识别率随阈值K变化

5.3 实验二

接下来是对两种匹配算法的对比实验。该实验中，本文算法采用双阈值Otsu计算阈值K，在金字塔顶层用方向量化的模板数据进行匹配，在精匹配过程所用模板数据和传统算法所用的一样。表1记录了两种算法的性能。其中识别率为ρ，所有图像匹配结果中找到的某种工件总数占该工件总数50×5的比例；平均时间为T，用某种工件模板数据在每张图像的金字塔中进行匹配搜寻所占时间的平均值。从实验结果数据来看，两种匹配方式都能正确搜寻到全部工件，但本文算法更为快速，本文算法匹配三类工件的速度都约为传统算法的5倍。

表1 算法性能比较

6 结论

本文提出一种基于边缘特征的模板匹配算法，用于实现多目标工件快速识别分拣。为了保证实时性，在金字塔顶层采用Linemod-2D匹配的加速方式避免了大量的乘除运算，精匹配的过程交由传统边缘梯度模板匹配算法完成，经过实验证明该方法在很大程度上提高了多目标识别的实时性，并保持着传统算法的准确性。再者分析了量化方向的筛选会影响顶层匹配质量，针对该问题运用双阈值最大类间方差法计算梯度幅值直方图，从而达到梯度幅值阈值自适应选择的目的，并且获得良好的效果。整个算法流程较为简洁高效，实用性好。