第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
改进的细菌觅食优化算法用于多阈值图像分割.docx
改进的细菌觅食算法用于多阈值图像分割
田云1，赵青杉，陈惠明，曹建芳
（1.忻州师范学院计算机科学与技术系，山西省忻州市 034000）
摘要：针对细菌觅食算法中细菌翻转方向的随机性以及更新细菌位置没有参照菌群群体最优位置以及个体
历史最优位置信息等问题，提出改进的细菌觅食算法，并将其用于多阈值图像分割。由最大类间方差法函
数作为改进的细菌觅食算法的适应度函数，搜索最优阈值，实现图像的多阈值分割。分割结果分别与传统
最大类间方差法、基于细菌觅食的多阈值图像分割结果对比，实验结果表明，本文算法能够有效提高收敛
速度，缩短图像分割时间，提高图像分割的准确率。
关键词：细菌觅食算法；粒子群算法；多阈值图像分割
中图法分类号: TP391
文献标识码 A
Multilevel Thresholding Methods for Image Segmentation Based on Improved
Bacteria Foraging algorithm
TIAN Yun, ZHAO Qing-shan, CHEN Hui-ming, CAO Jian-fang
(Department of Computer Science and Technology, Xinzhou Teachers University, Xinzhou, Shanxi Province, 034000, China)
Abstract: For bacteria foraging algorithm has the randomness of the bacteria in the tumble direction and updates
bacterial positions without referencing by local and global best positions, improved bacteria foraging algorithm
was presented, and used it to multilevel thresholding image segmentation. The optimization object function using
maximum between-class variance method can be gotten. By the optimization of the object function, the optimal
thresholds can be gotten, and the image by use of the thresholds can be segmented. Compared with the Otsu,
Multilevel thresholding image segmentation based on bacterial foraging algorithm, the experimental results show
that our algorithm can improve the convergence speed, shorten the time required for image segmentation, and
improve the accuracy of image segmentation.
Key words: bacterial foraging algorithm; particle swarm algorithm; multilevel thresholding image segmentation.
I.
Introdution
1 引言
Image segmentation is a key step in image processing and computer vision, is one of the many key technologies in the
field of study. Threshold value method is the most commonly method of image segmentation. Threshold method is divided into
the between-cluster variance method[2], the biggest index entropy method[3] and the minimum error method[4],etc.,especi-
ally suitable for target and background occupy different grayscale images. Because of the need to search for the optimal
threshold in image grayscale range value, the complexity and time-consuming character of the traditional search algorithm, it is
difficult to meet the needs of the image processing.
图像分割[1]是图像处理和计算机视觉中的关键步骤，是许多研究领域的关键技术之一。最常用的图像分割
方法是阈值法，阈值法分为最大类间方差法[2]、最大指数熵法[3]、最小误差法[4]等，特别适合目标和背景占
收稿日期:
基金项目:山西省自然科学基金项目(2014011019-3)；山西省重点实验室开放课题基金项目(2016002)；学院重点学科项目(XK201404)；院级青年基
金项目(QN201409)
This work is supported by the Natural Science Foundation of Shanxi(2014011019-3),the Open Fund Project of Shanxi Provincal
Key laboratory(2016002),the project of college key discipline(XK201404),the fund project of college youth(QN201409).
作者简介:田云(1982 年-)，女，河北保定人，硕士，研究方向为智能计算、图像处理，E-mail:tianyunjw@126.com.
据不同灰度的图像。因需要在图像的灰度范围内寻找最优阈值，传统搜索算法的复杂性和耗时性，很难满足图
像处理的需要。
Swarm intelligence algorithm [5, 6] is a new method of optimization calculation, and many scholars study the use of swarm
intelligence algorithm to search the optimal threshold. Bacterial foraging algorithm [7] is a new type of bionic optimization
algorithm, has a slow convergence speed and precision is not high, easily falling into the most superior.
群体智能算法[5,6]是一门新兴的优化计算方法，许多学者研究使用群体智能算法搜索最优阈值。细菌觅食
(Bacterial Foraging algorithms, BFA) 算法[7]是一种新型仿生类优化算法，具有收敛速度较慢、求解精度不高、
易陷入局部最优等不足。
Scholars at home and abroad came up with various improvement strategies. For example, literature [8] put forward a kind
of based on the Standard bacteria Foraging Optimization algorithm of threshold image segmentation method, literature [9] is
proposed based on bacterial foraging algorithm of SAR image threshold segmentation method, literature [10] proposed for
index more entropy threshold segmentation of bacterial foraging algorithm, The literature [11] was proposed based on the
strategy of particle swarm adaptive foraging algorithm research. Against bacteria foraging optimization algorithm the
randomness of the bacteria in the reverse direction and update bacteria without reference to bacteria group, the optimal
location and the optimal location information, individual history based on these, this paper puts forward the improved bacteria
foraging optimization algorithm.
国内外学者提出了多种改进策略，如文献[8]提出了一种基于标准的细菌觅食优化(Standard Bacterial
Foraging Optimization，SBFO)算法的多阈值图像分割方法，文献[9]提出了基于细菌觅食算法的SAR图像阈值分
割方法，文献[10]提出了用于指数熵多阈值分割的改进细菌觅食算法，文献[11]提出了基于微粒群策略的自适应
觅食算法研究。针对细菌觅食优化算法中细菌翻转方向的随机性和更新细菌位置没有参照细菌群体最优位置以
及个体历史最优位置信息，基于这些不足，本文提出改进的细菌觅食优化算法。
This article mainly has two improvements. Firstly, bacteria group, the optimal location and reverse direction combined with
flora individual history, the optimal location information, avoid bacteria random direction of swimming and delay the problem of
searching the global optimal value. Second, in order to accelerate the bacterial foraging algorithm for global optimization
performance, at the end of every chemotaxis step, by the location of the particle swarm location formula to update all bacteria.
Simulation experiments, in the most between-cluster variance method as optimization objective function, the improved
algorithm is proposed in this paper the optimization, search the optimal threshold, the realization of image threshold
segmentation
本文主要有两个改进，第一，细菌翻转方向结合菌群群体最优位置以及个体历史最优位置信息，避免细
菌随机方向的游动而延误全局最优值搜索的问题；第二，为了加速细菌觅食算法全局寻优性能，在每一次趋化
结束后，由粒子群位置公式来更新所有细菌的位置。仿真实验中，以最大类间方差法作为待优化目标函数，采
用本文提出的改进算法对其优化，搜索最优阈值，实现图像的多阈值分割。
II. Improvement of bacterial foraging optimization algorithm
2 改进的细菌觅食优化算法
BFA 算法包括趋化、复制、迁徙 3 个主要步骤[12]，趋化又包括翻转和游动，趋化操作中细菌更新位置的
公式为：
BFA algorithm includes three main steps as chemotaxis, reproduction, and migration [12], chemotaxis includes tumble and
swimming, the operation of chemotactic bacteria update location formula is:
(i,
j
1, )
k
(i, j,k)
C i D
g
( )
(i, j)
D
(i, j)=
( )
i
T
( )
i
(i)
Among them,
(i, j,k)
says the ith a bacteria position in the j chemotactic operation and in the k copy operation ,
(1)
(2)
( )C i
said bacteria swim step length,
( )i
said bacteria to tumble any direction vector.
其中， (i, j,k)
表示第 i 个细菌在第 j 次趋化操作和第 k 次复制操作中的位置， ( )C i 表示细菌游动的步长； ( )i
表示细菌翻转时任意方向的向量。
The randomness of the bacteria in the reverse direction and update bacteria without reference to bacteria group, the optimal
location and the optimal individual history location information in BFA. Based on these, puts forward the improved bacteria
foraging optimization algorithm, is a kind of new bacteria update location strategy.
BFA 算法中细菌翻转方向的随机性以及更新细菌位置没有参照细菌群体最优位置以及个体历史最优位置
信息，基于这些不足，提出改进的细菌觅食优化算法，是细菌更新位置的一种新策略。
First, Bacterial foraging algorithm, flip behavior are that bacteria remains the current position, randomly choose a new
direction and could delay time of arrival in the optimal solution. In this article, reverse direction will be combined with bacteria
group, the optimal location and the optimal location information, avoid the swimming in random direction of bacteria caused
the delay of search the global optimal value. Bacterial reverse direction vector formula is shown below:
第一，细菌觅食算法中，翻转行为是细菌当前位置不变，随机选择一个新方向，可能延迟到达最优解的时
间。本文将细菌翻转方向结合细菌群体最优位置以及个体历史最优位置信息，避免细菌随机方向的游动而延误
全局最优值的搜索。细菌翻转方向向量的公式如下所示：
D
(i, j 1)
kD(i, j)
R
1 1
||
pbest
(j,k)
(i, j,k) ||
2
R
2
||
global
(i, j,k) ||
(3)
Among them, the k is inertia weight coefficient, the value range is [0.4, 0.95];
pbest
( , )
j k
is the optimal location of the j
chemotaxis, the k copy operation;
global
is the optimal location in the whole search space;
1R and
2R is a random
number between [0, 1];
1 and
2 is learning factor which change with number of chemotactic.
其中，k 是惯性权重系数，取值范围是[0.4,0.95]；
pbest
( , )
j k
是第 j 次趋化、第 k 次复制操作中的最优
位置； global 是在整个搜索空间中的最优位置； 1R 和 2R 是[0,1]之间的随机数； 1和 2 为随趋化次数动态改
变的学习因子。
Second, in order to accelerate global optimization performance of the bacterial foraging algorithm, at the end of every
chemotaxis steps, by particle swarm position formula to update the location of all bacteria, this is called the mutation. To
improve the convergence speed and precision of the optimal solution of bacteria,
(4):
( ,
i
j
1, )
k
is updated by the formula
第二，为了加速细菌觅食算法全局寻优性能，在每一次趋化步骤结束后，由粒子群位置公式来更新所有
细 菌 的 位 置 ， 称 之 为 突 变 。 用 来 改 进 细 菌 的 收 敛 速 度 和 最 优 解 精 度 ， ( ,
i
j
1, )
k
由 公 式 (3) 更 新 ：
(i,
j
1, )
k
1
global
(i, j,k)
(4)
r
1
global
global
(i, j,k)
r
2
pbest
(j,k)
本文改进的细菌觅食优化算法，初始化参数说明：
The improved bacteria foraging optimization algorithm in this paper, initialization parameter:
S = Number of bacteria in the population
Nc = Number of Chemotaxis steps
Ns= Number of Swimming steps
Nre = Number of reproduction steps
J (i, j, k) = Fitness value or cost of i-th bacteria in the j-th chemotaxis and k-th reproduction steps
Jpbest (j, k) = Fitness value or cost of best position in the j-th chemotaxis and k-th reproduction steps
Jglobal= Fitness value or cost of the global best position in the entire search space
Pseudo code of The improved bacteria foraging optimization algorithm in this paper is shown in figure 1:
S：菌群中细菌的数量；Nc：趋化操作的最大次数；NS：游动操作的最大次数；Nre 复制操作的最大次数；
J(i,j,k)：第 i 个细菌在第 j 次趋化操作和第 k 次复制操作中的适应度值；Jpbest(j,k) ：第 j 次趋化操
作和第 k 次复制操作中的最优适应度值；Jglobal：在整个搜索空间中的最优适应度值。本文改进的细菌
觅食优化算法的伪代码如图 1 所示：
Begin:
Initialize the position of the bacteria and the fitness value, and update the following parameters:
初始化细菌的位置和适应度值，并更新下面的参数：Jglobal=Jpbest(j,k);θglobal=θpbest(j,k);
Reproduction:
For k=1 to Nre do{
Chemotaxis:
For j=1 to Nc do{
Tumble:
根据公式（3）产生细菌翻转的方向 The direction of the bacteria to flip is updated by the
Swim: {
m=0;
While(m
Improvement bacterial foraging optimization algorithm is used in multi threshold image segmentation
3.1 最大类间方差法
The between-cluster variance method
The between-cluster variance method is a common image segmentation method. A detailed description as follows:
assumes that the image grey level is L
最大类间方差法[12]是常见的图像分割方法。具体描述如下：假设图像灰度级为 L ，则第 i(i=0,1,…L-1)
级灰度出现的概率为 ip 。假设有 c 个阈值 1
( , t ,
t
2
t ，选择最优阈值 1
(t , t ,
2
)c
,
最大化 ( )
, t )c
t ：
f
(t ,t ,
2
1
K
,t )
c
arg max
( )
f t
0
t
1
K
L
t
c
1
2
0
1
0
( )
)
f t
2
(
K
2
2
)
c
(
(
(
)
1
)
K
2
2
)
c
1
(
1
1
0
0
2
1
1
1
2
c
c
c
2
0
(
c
K
0
c
2
)
c
(5)
(6)
n
1
t
n
i
t
n
1
P
i
,
n 1
i
t
n
tn
1
iPi
/
n 1
1
n c
1
When extended to multi threshold, with the increase of threshold number, image segmentation time will be exponential
growth, this will seriously limits the application of the multi threshold. In order to overcome these problems, improvement
of bacterial foraging algorithm optimize the objective function formula(4) of Otsu, mathematical formula of multi threshold
image segmentation that based on the most between-cluster variance is used as improvement of bacterial foraging
algorithm fitness function, to search the optimal threshold.
当扩展到多阈值，随着阈值数目增加，图像分割时间将指数级增长，这将严重限制多阈值的应用。多阈值
的求解问题可以转换成对目标函数解的优化问题。为了克服以上问题，改进的细菌觅食算法优化 Otsu 的目标
函数公式（4），即将基于最大类间方差的多阈值图像分割的数学公式作为改进的细菌觅食算法的适应度函数，
搜索最优阈值。
3.2 改进的细菌觅食优化算法用于多阈值图像分割，基本步骤如下：
Improvement bacterial foraging optimization algorithm is used in multi threshold image segmentation, basic steps are as
follows:
1. 读入待分割的图像，若是彩色图像，首先将其转化为灰度图像。Read to image segmentation, if they are color
images, converted then to gray images.
2. 设置本文算法的参数大小。Set up the parameters size of the algorithm in this paper.
3. 初始化细菌的位置，细菌位置范围 [0，255]内，位置是灰度的组合。根据公式（6）计算细菌个体的初始适
应度值。初始化θpbest(j,k)和θglobal，Jpbest(j,k)和 Jglobal；θglobal=θpbest(j,k)，Jglobal=Jpbest(j,k)。
Initialize the position of the bacteria, the position of bacteria range [0,255], position is a combination of gray. Calculate the
initial bacteria individual fitness value by the formula (6). Initialize θpbest(j,k) ,θglobal, Jpbest(j,k) and Jglobal.
4. 复制操作循环：k=k+1，当 k
根据公式（1）计算细菌的位置。
计算细菌的适应度值 J(i,j+1,k)。更新θpbest(j+1,k)和 Jpbest(j+1,k)。
Compute fitness function J (i, j+1, k) Update Jbest (j+1, k)
如果 Jpbest(j+1,k)< Jpbest(j,k)时，θpbest(j,k)= θpbest(j+1,k)，Jpbest(j,k)= Jpbest(j+1,k)；θglobal= θpbest(j,k)，
Jglobal=Jpbest(j,k)；
If Jbest (j+1,k)< Jbest (j, k) (if doing better), θpbest(j,k)= θpbest(j+1,k)，Jpbest(j,k)= Jpbest(j+1,k)；θglobal=
θpbest(j,k)，Jglobal=Jpbest(j,k)；
○2 当 m=Ns 或 Jpbest(j+1,k)>Jpbest(j,k)时，则执行下一步突变操作。
While m=Ns or Jpbest(j+1,k)>Jpbest(j,k), execute the next mutation operation.
8. 突变：为使细菌的位置和适应度值更接近于全局最优，使用粒子群算法重新计算细菌在每一次趋化操作结
束后的位置，根据公式（4）计算细菌的位置，提取本次趋化操作中的θpbest(j,k)和 Jglobal。执行结束后返
回第 5 步。Mutation: In order to make the position of the bacteria and the fitness value are closer to the global optimal,
using the particle swarm algorithm to calculate the position of bacteria at the end of every chemotactic, according to the
formula (4) calculate the position of the bacteria, extract θpbest(j,k) and Jglobal of this chemotaxis operation. Return to
step 5 at the end of execution.
9. 复制操作：提取每个细菌的历史最优适应度值 Jpbest(i)，对 Jpbest(i)从小到大进行排序，将 Jpbest(i)中后 1/2
的细菌淘汰掉，被保留下的细菌按照一分为二的分裂方式进行繁殖，且子细菌与母细菌具有相同的生物特
性，即具有和母细菌相同的位置和方向。Reproduction operation: extract the history optimal fitness value of each
bacteria, to order to Jpbest (i) since the childhood, the least healthy bacteria die and others split into two, which are placed
in the same location. Son bacteria and mother bacteria have the same biological features.
10. 输出全局最优解，即输出最优阈值向量 t*。Output the global optimal solution(output the optimal threshold vector t*)
11. 根据阈值向量 t*对原图像进行分割处理，得到分割后的图像。According to the threshold vector t * on the original
image segmentation processing, After segmentation of images
4 实验结果 The experimental results
本文实验环境为 MATLAB2011a，为了验证改进的细菌觅食算法有效性，实验中对多幅图像分别采用 Otsu、
基于 BFA 和基于本文算法进行双阈值、三阈值分割。
In this paper, the experimental environment is MATLAB2011a, in order to verify the improved bacterial foraging algorithm
is effective, experiments of image respectively by Otsu, based on the BFA and double threshold based on the algorithm in this
paper, three threshold segmentation.
仿真实验中，基于 BFA 及基于本文算法的双阈值、三阈值图像分割，其参数值设置如表 1 所示。因篇幅
限制，实验原图如图 2 所示。
In simulation experiment, based on the BFA and based on the double threshold algorithm in this paper, three threshold
image segmentation. The parameter value is set as shown in table 1. Due to the limitation of length, The artwork as shown in
figure 2:
表 1 参数值 Table 1 parameter values
基于 BFA
双阈值
double
threshold
based on
the BFA
2
20
基于 BFA
三阈值
three threshold
based on the bFA
3
20
基于本文算
法的双阈值
the double
threshold
based
on algorithm
in this paper
2
20
基于本文算
法的三阈值
the three threshold based
on algorithm in this paper
3
20
search dimension /p
the number of bacteria /S
chemotaxis number /Nc
number of swimming /Ns
copy number /Nre
every generation reproduction number /Sr
the migration operands /Ned
bacteria transition probability /Ped
30
4
4
S/2
2
30
4
4
S/2
2
0.25
0.25
30
4
4
S/3
--
--
30
4
4
S/3
--
--
(a)长颈鹿原图 The original image of giraffe
(b) 企鹅原图 The original image of penguin
图 2 实验原图 Figure 2
The experimental artwork
下面列出了对一幅长颈鹿、一幅企鹅的分割结果。图 3 和图 4 分别是图 2(a)的双阈值和三阈值图像分割结
果（Otsu、基于 BFA、基于本文算法）。图 5 和图 6 分别是图 2(b)的双阈值和三阈值图像分割结果（Otsu、基
于 BFA、基于本文算法）。
Below is a list of segmentation results for a giraffe picture and a penguin picture. Figures 3 and 4, respectively is the double
threshold figure 2 (a) and three threshold image segmentation results (Otsu , based on the BFA, based on the algorithm in this
paper). Figures 5 and 6, respectively is the double threshold figure 2 (b) and three threshold image segmentation results
(Otsu , based on the BFA, based on the algorithm in this paper).
(a)Otsu 双阈值分割结果 Otsu threshold segmentation results
(b) 基于 BFA 的双阈值分割结果 threshold segmentation
results based on BEA (c)基于本文算法的双阈值分割结果 threshold segmentation results based on the algorithm in this paper
图 3 长颈鹿原图基于 3 种方法的双阈值分割结果 threshold segmentation results of the giraffe artwork based on the three
methods
(a)Otsu 三阈值分割结果
(b) 基于 BFA 的三阈值分割结果 (c) 基于本文算法的三阈值分割结果
图 4 长颈鹿原图基于 3 种方法的三阈值分割结果
(a)Otsu 双阈值分割结果
(b) 基于 BFA 的双阈值分割结果 (c) 基于本文算法的双阈值分割结果
图 5 企鹅原图基于 3 种方法的双阈值分割结果
(a) Otsu 三阈值分割结果 (b) 基于 BFA 的三阈值分割结果 (c) 基于本文算法的三阈值分割结果
图 6 企鹅原图基于 3 种方法的三阈值分割结果
从图 3 至图 6 中，我们可以发现，Otsu 和基于 BFA 的图像分割结果效果差不多，而基于本文算法的双阈
值、三阈值图像分割，分割效果明显优于其他两种方法，图像中的目标轮廓更清晰，目标保持得更完整。
From figure 3 to figure 6, we can find that, image segmentation results of Otsu is the same as image segmentation results
based on the BFA, the double threshold and three threshold image segmentation based on algorithm in this paper, the
segmentation result is superior than other two methods, images of the target contour more clearly, goals keep more complete.
表 2 和表 3 分别是基于三种方法的双阈值和三阈值图像分割，在阈值、适应度值和 CPU 处理时间方面的
比较。从表 3 可以看出，基于 BFA 和基于本文算法的双阈值和三阈值图像分割，CPU 处理时间都相对少的多。
并且在相同的参数条件下，随着阈值数的增加，基于本文算法的收敛速度比 BFA 快，基于本文算法需要更少
的 CPU 处理时间来寻找最优阈值。
Table 2 and table 3 respectively, which is based on three methods of double threshold and three threshold image
segmentation, The threshold, the comparison of fitness value and CPU time. Can be seen from table 3, CPU time is relatively
less, based on the BFA and based on the double threshold algorithm in this paper and three threshold image segmentation. And
under the condition of the same parameters, with the increase of threshold number, based on the convergence speed is faster
than BFA algorithm in this paper, based on this algorithm requires less CPU time to find the optimal threshold.
表 2 阈值、适应度值的比较 Table 2 threshold, fitness value comparison
测试图像
The test image
阈值数
Threshold
number
长颈鹿图像
The giraffe image
企鹅图像
The penguin
image
2
3
2
3
阈值
threshold
(145，209)
(132,179,226)
(133,204)
(114,168,217)
Otsu
基于 BFA
基于本文算法
适应度值 Fitness
value
3.1654e
+003
3.2655e
+003
3.4115e
+003
3.5758e
+003
阈值
(145，209)
(133,180,225)
(133,204)
(110,165,215)
适应度
值
3.1654e
+003
3.2655e
+003
3.4115e
+003
3.5758e
+003
阈值
(125,164)
(105,142,161)
(156,223)
(125,170,173)
适应度
值
2.9187e
+003
2.8926e
+003
3.1647e
+003
3.3090e
+003
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc