基于果蝇优化算法的零件图像边缘检测算法研究及应用

谢 昕， 王伟如， 万天成， 江勋绎， 胡锋平

(1.华东交通大学信息工程学院， 南昌 330013; 2.华东交通大学土木建筑学院， 南昌 330013)

图像边缘是图像分割技术依赖的重要依据，也是图像模式识别和机器视觉的基础。常见的边缘检测算法有Roberts[1]、Sobel[2]、Prewitt[3]、Laplacan[4]、Kirsh[5]、LOG[6]、Canny[7]等，其中Canny算法相较于其他算法具有较好的去噪能力和较高的检测精度，应用范围广泛。

果蝇优化算法(fruit fly optimization algorithm，FOA)[8]是模拟果蝇种群的觅食行为而推导的一种群智能演化算法，与其他群智能算法相比，该算法具有操作简单、可塑性强、寻优速度快等优点。彭启伟等[9]提出基于叉分二维直方图的改进二维Otsu法结合果蝇算法对图像进行分割，在二维直方图区域叉分的基础上，利用灰度级大小改善联合概率，综合考虑类间方差和类内方差，同时根据目标和背景在图像中所占比例对阈值求取公式加权，然后通过果蝇优化算法对最优二维阈值向量进行查寻，从而提高算法的检测精度、减少搜索时间；孙立新等[10]提出一种自适应果蝇算法优化模糊均值聚类算法对图像进行分割，提高了算法的准确性和健壮性，但在一定程度上增加了时间复杂性，是否满足实时应用，有待进一步检验。

基于此，现提出一种基于FOA的零件图像边缘检测算法和模型，先通过Canny算子得到待测图像边缘点的信息，再通过希尔伯特变换提取角点信息，以边缘点和角点信息作为启发信息，从而达到对机械零件图像边缘进行快速准确的检测。

1 传统Canny算子边缘检测分析

1.1 高斯平滑滤波

由于图像中的边缘和噪声信息多集中在高频部分，使得图像中的噪声信息容易被当作伪边缘检测出来；为消除噪声干扰，传统Canny算子通过二维高斯滤波器G(x,y)对图像进行卷积操作，实现了对图像边缘的平滑处理[11]。设原图像为I(x,y)，则平滑后的图像H(x,y)表示为

H(x,y)=G(x,y)*I(x,y)

(1)

式(1)中:*表示卷积运算，高斯滤波函数G(x,y)如式(2)所示：

(2)

二维高斯滤波器G(x,y)由高斯函数的标准差σ和选用模板的大小共同确定，其中高斯函数的取值服从正态分布，使得随机变量的数值分布在区间(μ-3σ,μ+3σ)中的概率为0.997 4，也就是说几乎全部集中在这个区间内，所以，模板的大小可以设置为6σ，为保证模板窗口有核心，则6σ必须为奇数，而模板窗口的大小通过1+2ceil(3nσ)得到，ceil为向上取整函数，令ceil(3nσ)=1，则窗口大小设置为3×3。

1.2 计算梯度幅值和方向

梯度幅值A(x,y)和方向θ(x,y)[12]的计算公式为

(3)

(4)

1.3 对梯度值进行非极大值抑制

遍历图像中每个像素点的梯度幅值，然后比较梯度方向上相邻2个像素点的梯度值，若该点的梯度幅值小于相邻方向上的梯度幅值，则该点肯定不是边缘点；否则，该点可能是边缘点，并保留该值。通常在跨越梯度方向的两个相邻像素间采用线性插值来获得要比较的像素梯度，以便提高计算精度。

图1 梯度方向分割Fig.1 Gradient direction segmentation

如图1所示，将梯度分为8个方向，分别为E、NE、N、NW、W、SW、S、SE，其中0代表0°～45°，1代表45°～90°，2代表-90°～-45°，3代表-45°～0°。若像素点p的梯度方向为θ，则像素点p1和p2的线性梯度插值为

tanθ=Hy/Hx

(5)

Hp1=(1-tanθ)E+tanθNE

(6)

Hp2=(1-tanθ)W+tanθSW

(7)

1.4 用双阈值算法检测和连接边缘

具体方法是通过选取高、低阈值两个系数来区分图像边缘，根据先验知识，高阈值(TH)和低阈值(TL)的比率为2/1或3/1时边缘处理的效果最好，在文中取TH=0.3，TL=0.1。遍历图像，如果该像素点的像素梯度幅值大于设置的高阈值，则该点肯定是边缘点；如果该像素点的梯度幅值在设置的高、低阈值之间，则该点被标记为弱边缘点，并通过8邻域像素来判断，即：如果存在一条连接弱边缘和任意强边缘的联通线，则该点被确认为是边缘点，否则，不是；如果该像素点的梯度幅值小于设置的低阈值，则该点肯定不是边缘点[13]。

在实际应用中，采集到的图像总受到随机噪声的干扰，使得Canny边缘检测算法中高斯函数的方差参数σ的选择尤为关键。对于式(2)，当σ取值越大，则G(x,y)的值越小、通频带越窄。由于噪声多集中在高频信息中，因此对噪声的去噪效果较好，同时避免了虚假边缘的检出，但也对图像的边缘进行了平滑处理，使得某些边缘信息丢失。相反，σ取值越小，则G(x,y)的值越大，通频带越宽，对图像边缘的细节信息检测得越完整，但是滤除图像中噪声信息的能力相对较弱，容易检测出虚假边缘；如何对图像边缘进行精确定位并滤除噪声是两个互相矛盾的问题，无法同时得到很好的解决。针对传统边缘检测算法中角点的漏检问题，现拟采用Hilbert变换来提取图像角点信息。

2 基于Hilbert变换提取角点信息

计算机只能分析和处理离散数据，如果信号是连续信号，就需将连续信号通过离散采样变换成离散信号。令s[k]为离散信号，其傅里叶变换[14]为

(8)

式(8)中：j为虚数单位；Ω为非连续周期。

为了分析离散信号s[k]的Hilbert变换，则将s[k]作为离散线性时移不变系统的输入，那么该离散线性时移不变系统的频率响应为

(9)

(10)

(11)

其中{s[k]}的离散傅里叶变换(discrete fourier transform, DFT)[16]为{S[n]}，那么{H[n]}是对式(9)中H(ejΩ)的周期离散性表述，即

(12)

(13)

由式(11)，s[k]和式(14)循环卷积得

(14)

式(14)中:h[k]为s[k]进行卷积计算的模板。

(15)

图像信号作为二维信号，一维信号的Hilbert 变换无法应用，需将其推广至二维空间：首先通过式(11)将二维离散信号s[k1,k2]的各列和h[k]进行卷积运算，得到二维信号列方向上的Hilbert变换，然后再将变换后结果中的各行与h[k]进行卷积运算，从而得到二维信号的离散Hilbert变换为

(16)

式(16)中：N1、N2为一个二维图像信号矩阵的大小；r1、r2为在N1×N2矩阵中横坐标和纵坐标的变化，k1、k2为图像中该像素点位置。

通过二维Hilbert变换将空间域中的角点信息转化为二维平面中的极值点的检测；数字图像中各个像素点(x,y)都存在与之相邻的8个邻域点，这8个邻域点存在4种相邻的情况，则点(x,y)可能是x轴、y轴和对角线(45°和135°)方向中某一个方向所对应的3个相邻像素点中模的局部极大值点。因此，对于任意点(x,y)的梯度方向，就只需判断在x轴、y轴和对角线方向上点(x,y)是否为该梯度方向上模的局部极值点；若是，则点(x,y)为候选点，反之不是候选点。据此，模的局部极值点可以通过以下方法进行寻找，对于任意的点(x,y)，则有

沿着点(x,y)的梯度方向，在限定的范围内对模值进行检测，如果点(x,y)的模值为极大值，则将点(x,y)保留，否则删除。

3 果蝇优化算法分析

果蝇种群在觅食时，果蝇个体通过依靠自身嗅觉器官搜寻空气中的食物气味，并向附近的果蝇发送食物信息，或从附近果蝇那里接收食物信息，然后通过比较当前种群中收集到的气味信息判断食物源的最优位置，飞往该位置继续展开搜索[9]。果蝇觅食过程如图2所示，根据果蝇群体觅食行为的特点，可以将标准果蝇优化算法分为以下几个步骤。

图2 果蝇觅食过程Fig.2 Feeding process of fruit flies

3.1 步骤1：初始化

设置果蝇优化算法的初始参数，其中LR为果蝇种群的位置范围、FR为果蝇单次飞行的距离，则果蝇个体位置与二维坐标(X,Y)相对应。随机初始果蝇种群位置为

(17)

3.2 步骤2：嗅觉搜索过程

步骤2.1：在利用嗅觉器官搜索食物时，随机赋予果蝇飞行方向和搜寻距离。则果蝇个体i的新位置通过式(18)得

(18)

步骤2.2：由于无法得知食物源的具体位置，因此，先计算该点到原点的距离Disti，再计算味道浓度判定值Si，其中Si和Disti互为倒数，即

(19)

Si=1/Disti

(20)

步骤2.3：将味道浓度判定值Si带入味道浓度判定函数Fitness中，以求出果蝇种群中果蝇个体的味道浓度Smelli。

Smelli=Fitness(Si)

(21)

FOA在求解最优化问题时，Fitness就是目标函数或者适应度函数。

步骤2.4：搜索得到当前果蝇种群中味道浓度值最大的果蝇信息，并将其味道浓度值和位置信息进行记录：

[bestSmell,bestSmell]=max(Smell)

(22)

3.3 步骤3：视觉搜索过程

保留最佳味道浓度值和位置信息，并且果蝇群体中的其他个体通过视觉器官均飞往该位置，即

Smellbest=bestSmell

(23)

(24)

3.4 步骤4：重复步骤2和步骤3，直到果蝇的迭代次数达到最大迭代值(Max-gen)时终止搜索

为得到FOA的最优值，在实验中独立进行30次最优值搜索，并记录每次的寻优结果，然后将30次寻优结果的均值、最小值和均方差进行统计。在实验中，最大迭代次数初始设置为100，群体规模数为50，果蝇个体的初始迭代步长设置为1，其测试结果如图3所示。

图3 果蝇算法运行结果图Fig.3 Fruit fly optimization algorithm results

设置独立循环次数，寻求最优解，在独立循环次数设置时，最大迭代次数设定为100，群体规模数设定为50，循环次数设置为10、30、50、100、300、500来寻求最优解，图4所示为在不同循环次数中函数都趋向于0。在不同循环次数时的收敛值和时间对比如表1所示。可以看出，运行时间随着单次循环次数的增加而增加，但是相应的收敛值出现了一定的波动但变化不大。选取单次循环次数为30，收敛值相对较小，时间运行少。

选定单次循环次数为30，将群体规模数进行一定的改变，设置群体规模数为50、100、200、300、400、500，进行收敛实验如图5所示。表2为不同群体规模下的运行时间和最终收敛值的对比，可看出不同群体规模只有对算法的运行时间有一定的影响，对于最终的收敛值影响不大。

图4 不同单次循环次数迭代收敛图Fig.4 Iterative convergence diagram for different single cycles

图5 不同群体规模迭代收敛图Fig.5 Iterative convergence of different population size

4 基于FOA的图像边缘检测算法改进

果蝇优化算法在搜寻最优解时，通过视觉操作指引果蝇种群搜索当前位置的最优解，并结合嗅觉操作对全局进行随机搜索，以便跳出局部最优解，快速搜索到更好的解。由于味道浓度判定值Si取决于果蝇种群的初始位置范围(LR)和单次飞行距离(FR)的初始值设置，若LR参数设置很大而FR参数设置很小，即使FR取值发生变化也无法对解Si产生较大的影响，因此在求解复杂问题的最优解时，标准的果蝇优化算法过于早熟，易陷入局部最优。为解决上述问题，在果蝇的搜索半径机制中引入自适应参数，使得果蝇种群的搜索半径在搜索过程中根据迭代次数平滑地变化。则搜索半径λ和果蝇个体i的位置计算如下：

(25)

(26)

式中：d为区间[1,n]中的整数，n为问题维度，由于j=d，则j的取值范围也为[1,n]，且只能取整数；Iter为迭代次数，Itermax表示最大迭代次数。

为进一步增强索搜强度，在不改变群体位置的情况下通过一个具有均匀分布的决策变量，令d∈{1,2,…,n}为随机选择索引，生成新的解Xi=(xi,1,xi,2,…,xi,n)为

(27)

在候选解选择时，将果蝇的搜索范围从二维空间扩展到三维空间，并将果蝇与原点距离值的线性函数设置成逃逸参数Δ，并将Δ添加到味道浓度判定值Si中。该候选解生成机制为

(28)

表1 不同单次循环次数数据对比

表2 不同群体规模数据对比

(29)

Δ=Disti(0.5-δ)

(30)

式中：δ为区间[0,1]中的随机数，则Δ就可以为负数，因此Si就能为负数。

在图像边缘检测时，果蝇的搜索路线采用数据结构控制思想[17]，在提取边缘点和角点后的图像中选择任意路线，将果蝇群体按照启发信息分布在M×N的二维网格点阵上，其中每一个网格点就表示M×N像素的8 bit(1Byte)的灰度值(0～255)的图像上相应的像素，并且果蝇将会在此二维网格点阵上在候选解机制和搜索半径机制的相互协调下进行迭代移动，进行边缘点的搜索。在搜索过程中将已经搜索过的位置添加到位移矩阵中，记录下果蝇当前的位置，以便在下次查询时有效地避免再次查询，提高搜索效率；为最大限度地提高检测图像边缘的效率，并设定果蝇检测边缘的终止条件和迭代次数，即使查询结果不是最优，依据终止条件，也需停止搜索，在这里迭代次数设置为100[18]。则基于FOA的零件图像边缘检测具体流程如图6所示。

图6 边缘检测流程图Fig.6 Flow chart of the edge detection algorithm

步骤1：通过Canny算子和Hilbert变换提取边缘信息和角点信息。

步骤2：初始化算法参数，设置位移矩阵将果蝇移动过的位置记录在其中，以便减少相应的查询时间，初始化味道浓度矩阵。

步骤3：计算果蝇飞行方向的概率，并将当前位置写入到位移矩阵中。

步骤4：根据当前最佳味道浓度信息选择果蝇个体的位置信息，然后果蝇种群中的其他个体飞往该像素点，并更新味道浓度信息。

步骤5：重复上述步骤，当迭代次数达到最大或得到最优解时终止搜索，并将该像素点进行标记。

步骤6：在果蝇优化算法查寻结束后，将原图像中被标记的像素点设置为白色，其他未被标记的像素点设置为黑色，然后平滑连接已经被标记的点，完成对零件图像的边缘检测。

初始化果蝇算法时，将较高概率成为边缘的像素点作为初始点，在检测高概率区域的过程中对算法进行迭代以寻找局部边缘，从而提高算法的运行效率；位移矩阵的加入有助于加强果蝇寻找最优解的能力，位移矩阵将果蝇已经选择过的点的位置信息记录在该表中，当算法在执行时，对该像素点8个邻接位置进行选择，对存在于位移矩阵中的点选择跳过，从而选择那些从来没有被搜索到的点，就可以达成更大区域的搜索目标，避免了果蝇在局部搜索范围内进行无意义的往返运动；通过味道浓度和启发信息共同指导果蝇算法进行边缘追踪，对果蝇的飞行路线进行了限制与修剪。

5 实验与结果分析

为检验本文算法的可行性，实验平台是处理器主频2.53 GHz，内存4 GB，显存1 GB的个人计算机，MATLAB R2016a软件。

5.1 实验一：标准圆的边缘检测效果对比

先通过MATLAB软件在大小为500×500像素的图像中绘制一个直径为377.0像素的标准圆(图7)，并在圆上选取A、B、C和D共4个端点作为检漏点，利用本文算法对这4个点进行亚像素级的坐标检测，标准圆的边缘检测效。如图8所示，本文算法可以将标准圆的边缘检测出来，并且完整地输出；将标准圆边缘的检测结果与标准值进行比较，对比结果如表3所示。

图8 标准圆边缘检测Fig.8 Standard circle-edge detection

表3 标准圆边缘检测各项结果

如表3所示，算法的检测精度可以精确到1个像素级别，并且相对误差较小，测量精度高。

5.2 实验二：与标准Canny算子与 ACO算法对比

将本文算法、Canny算法、蚁群算法[19](ant colony optimization, ACO)分别对Lena(128×128)、Cameraman(256×256)、Baboon(512×512)、Deer(900×563)、Girl(480×320)5幅图像进行边缘检测，实验结果如图9所示。对于无噪声图像，Canny算子保留细节边缘和高频分量的能力弱于本文算法[20]，而ACO与本文算法差距不大。扫描边缘检测后图像中的每一个像素点，并统计其中为白色区域的像素点的个数；如果这个边缘点是Canny算子在检测图像边缘时对应位置上的边缘点，则该点被标记为准确边缘点。则漏检的边缘点个数就是被检测图像总的边缘点与准确边缘点的差值；漏检率就是边缘像素点中的漏检个数和被测图像中总像素的比值；误检率就是边缘像素点中的误检个数与被测图像中总像素的比值；那么定义定位误差就是漏检率与误检率的和，检测结果如表4所示。

表4 边缘检测评价指标

从表4中可以看出，这3种算法在检测不同分辨率的图像边缘时漏检率各不相同。由于本文算法和ACO都将Canny算子检测到的边缘作为标准边缘点，而传统的Canny算子检测到的边缘点往往比较完整，但可能会包含虚假边缘点，所以本文算法与Canny算子检测到的边缘点全部都是真实边缘，因此算法误检的可能性为0，但边缘漏检的可能性则相对较高，因而本文算法的定位误差就只能通过漏检率表示。如表4所示，与其他两种算法相比，本文算法在漏检率上的数值最小，说明本文算法在检测边缘时要优于其他两种算法。

Hu等[21]提出了一种评价边缘连结程度的方法：在已完成检测的图像中统计被检测到的边缘点个数并记为NP，边缘图像中4联通数用NL表示，那么边缘的线性连接程度就可以用NL/NP值来表示。由于边缘的错检和漏检直接影响着边缘的线性连接程度对总体边缘的评价，所以当边缘点的错检和漏检次数较大时，则表明边缘的线性连接程度差；如果边缘点的错检和漏检次数越少，则表明边缘的线性连接程度就越高，边缘的检测效果就越好。算法性能对比如表5所示，耗时对比如表6所示。

表5 算法性能对比表

表6 本组实验所耗时间对比

由于前文中FOA在寻优迭代次数为100时达到最优值，则零件图像边缘检测模型的单次迭代次数也设置为100；蚁群算法边缘检测的速度与图像的大小、蚁群的初始位置、种群的数量以及图像的复杂程度有关；为突出FOA的速度优点，在不同分辨率的图像中将迭代次数统一设置为100。从表6可以看出，本文算法在时间复杂度上要优于ACO算法，而略逊于Canny 算子，本文算法在实际应用中具有一定的实用性。

5.3 实验三 不同零件边缘检测对比

为了比较本文算法的检测效果，选用工业领域常见机械零件灰度图像作为研究对象，如图10所示，图像边缘完整且精度较高。

为了比较实际图像的检测效果，通过对机器视觉系统工业相机采集到的实际零件图样进行边缘检测，实验中通过将检测软件Cognex(Connolly 2009)作为比较对象对图11进行验证，在零件上随机提取点，然后对比该点的坐标关系来验证本算法在实际零件检测过程中的精确程度。实验结果如表7所示。

由表7可知,本文算法在实际零件检测中坐标偏移量相差小，能够对实际零件进行有效的边缘检测。

图10 机械零件灰度图像边缘检测图Fig.10 Gray-scale image edge detection of mechanical parts

图11 实际零件边缘检测图Fig.11 Edge inspection of actual mechanical parts

表7 零件的像素坐标对比

6 结论

零件表面包含有大量的信息，边缘检测一直是工业检测中的重点和难点，随着科学技术的发展，边缘检测技术在工业中得到了广泛的应用。将Canny算法得到的边缘点信息和希尔伯特变换提取的角点信息作为启发信息，然后建立基于FOA的边缘追踪模型，采用随机平均移动机制和循环终止条件得到图像的单像素边缘，可以避免果蝇在非边缘区域的分布和查找。实验结果表明，本文算法相比Canny边缘算法在图像边缘检测性能上有大幅度的提升，边缘检测精确度高。但是本文算法相对于传统基于微分的边缘检测算法速度还是较慢，果蝇的步长设置还需进一步改进以便减少边缘信息的查找时间。