基于IGA的三维OTSU算法的改进

基于IGA的三维OTSU算法的改进

张玉连，褚巧龙，郭贵冰

（燕山大学信息科学与工程学院，河北秦皇岛，066004）

摘要：在图像分割中三维OTSU阈值分割算法充分考虑了像素之间的灰度相关信息，较一维和二维OTSU阈值法的分割效果好，但其计算复杂性高、实时性差。为此，本文提出了将免疫遗传算法应用到三维OTSU阈值寻优中，并采用递推的方法来减少适应度函数的计算。实验表明，与传统的三维OTSU阈值分割算法相比，图像分割清晰，实时性得到明显改善。

关键词：图像分割；三维OTSU阈值分割法；免疫遗传算法

中图分类号:TP391

Three-dimensional Otsu Threshold Algorithm Based On The Improved of Immunity Genetic Algorithm

Zhang Yu-lian,Chu Qiao-long,Guo Gui-bing

(College of Information Science and Engineering,Yanshan University,Qinhuangdao

Hebei ,066004,China)

Abstract The three-dimensional OTSU thresholding segmentation method utilizes gray level correlation information between each of pixel in image segmentation field,and it have better segmentation result than one-dimensional and two-dimensional thresholding,but it had the high complex computational complexity and poor real-time.So,this paper adopted an immunity genetic algorithm and used in the search of three-dimensional OTSU optimizing threshold,and the repeat computations of the fitness function in iteration are reduced significantly using recursion. The experimental results show that compared with the traditional three-dimensional OTSU thresholding segmentation method,the image segmentation clear,and the real-time had be improved.

Key words:image segmentation;three-dimensional OTSU thresholding segmentation method;

immunity genetic algorithm

0 引言

图像分割是图像处理的一个关键步骤，是计算机视觉和人工智能中基本而关键的技术之一。阈值分割因其计算简单、实时性高，而成为图像分割的应用最广泛的关键技术之一。在众多阈值分割算法中，由Otsu[1]在1979年提出的1维最大类间方差法，因其计算简单、分割效果较好而得到广泛应用，但其仅仅利用像素本身的灰度信息，没有利用像素之间的空间信息，并且信噪比较低，遇到较复杂的图像时，容易产生较严重的分割错误。针对这一点，我国学者刘健庄[2]等人在1993年提出了基于自身灰度和邻域平均灰度的二维Otsu阈值分割法，其抗噪声能力要强于1维Otsu阈值分割法，并且图像处理效果也有明显改善。但是，随着噪声的增加，图像的信噪比不断降低，图像的分割效果也越来越差。为此，景晓军等人[3]引入了邻域中值作为第三个特征，构造了三维直方图，并提出了三维Otsu阈值分割法，使得对于低信噪比的图像有了更好的分割效果，并给出了一个递归算法，是得三维Otsu法的计算复杂度从O(L6)降到了O(L3)。范九伦等人[4]在此基础上指出了景晓军给出的递归公式的错误并加以改正，同时给出了一组新的递推公式，计算复杂度仍为O(L3)，但时间有所减

少，并且证明了加入了混合噪声的图像的处理效果更好。虽然递推算法的引入使得三维Otsu 阈值分割法的计算复杂度降低了，但是计算时间仍较长，也容易受到噪声干扰，基于此点，本文提出了将免疫遗传算法融入到三维Otsu 阈值分割法中，既可利用遗传算法的固有的并行性、不易陷入局部最优和全局搜索的特点，在将免疫因子融入到遗传算法的时候，也缓解了遗传算法的退化现象，克服了遗传算法的早熟收敛和收敛性能差的缺点，大大提高了搜索效率[5]

。总而言之，将免疫遗传算法应用到三维Otsu 阈值分割算法中，提高了该算法的抗噪能力，在搜索最佳阈值过程中节约了时间，提高了算法的实时性，达到了较好的分割效果。

1 三维Otsu 阈值分割法

对于一幅M N ?的数字图像，我们用(),f x y 来表示(),x y 处像素点的灰度值，用

(),g x y 来表示(),x y 处的k k ?邻域的平均灰度值，(),g x y 定义如下：

()()/2/2

2

/2/2

1,,k k m k n k g x y f

x m y n k

=-=-=

++∑∑

(1)

用(),h x y 表示(),x y 处k k ?邻域的灰度中值，(),h x y 定义如下：

()(){},,,/2,,/2;/2,,/2h x y med f x m y n m k k n k k =++=-???=-??? (2)

从(),g x y 和(),h x y 的定义可以看出，如果图像的灰度级为L ，那么相应的邻域平均灰度级和邻域中值的灰度级也为L 。我们将由(),f x y 、(),g x y 和(),h x y 组成的三元组

(),,i j k 定义为三维直方图，该三维直方图定义在一个L L L ??的立方体区域内，其三个坐

标分别表示像素的灰度值、邻域均值和邻域中值，如图1(a)所示。将直方图上任意一点的向量(),,i j k 发生的频率定义为ijk p ，ijk p 由下式确定：

ijk ijk c p M N

=

? (3)

其中ijk c 是(),,i j k 出现的频数，0,,1i j k L ≤≤-，111

000

1L L L ijk i j k p ---====∑∑∑

。

图1 三维直方图区域

Fig.1 D histogram region

根据上面给出的三维直方图定义，若(),,s t q 是选取的阈值点，则三维直方图被分成如图1(b)所示的八个区域，具体的区域划分如图1(c)和(d)所示。由于目标内部和背景内部的像素点之间的相关性较强，像素点的灰度值、邻域均值和邻域中值非常接近；而目标和背景的边界附近的像素点，以上三个值之间的差异会比较明显。基于以上认识，区域0和区域1分别被看成背景和目标，区域2~7被看成边缘和噪声。由于边界和噪声区域的像素点远远小于背景和目标的像素点，所以我们将区域2~7的所有像素点的概率和近似为0。

三维直方图中的区域0和1分别代表图像的背景和目标，为了表示方便，将这两个区域分别表示成0C 和1C ，则背景和目标分别出现的概率为：

()()

00,,,,ijk i j k C s t q P P ∈=

∑

(4) ()()11,,,,

ijk i j k

C s t q P P ∈=

∑

(5)

(a)三维直方图的定义域

(,h x y

(,h x y

(b)三维直方图区域的划

(,h x y (c)区域0、2、3、4的划

分

(),h x y

(d)区域1、5、6、7的划分

背景和目标对应的均值矢量分别为：

()()()

()()

()()

000,,,,,,,,,,,,00000

,,,

,ijk

ijk

ijk i j k C s t q i j k C s t q i j k C s t q i j k

iP jP kP P P P μμμμ∈∈∈'??

?'==

? ??

?

∑

∑

∑

(6)

(

)()()()()(

)

()1

11,,,,,,,

,,

,

,,11111

1

1

,,,

,

i j k

i j k

i j k i j k C

s t q

i j k

C s t q i

j

k

C s t q

i j k

i P j P k P P P P μμμμ∈

∈∈'

??

?'=

= ? ??

?

∑

∑

∑

(7) 三维直方图上总的均值矢量为： ()11111111

1

000

0,,,,

L L L L L L L L L T T i

T j T

k i j k i j k i j k i j k i j k i j k i P j P k P μμ

μμ---------========='

??'

=

= ???

∑∑∑∑

∑∑∑∑∑

(8) 前面我们已经假设区域2~7的概率之和近似为0，则可知：

011P P +≈ (9) 0011T P P μμμ≈+ (10) 定义类间的离差矩阵

()()()(

)00010

B T T T T S P P μμμμμμμμ?

??

?

''=--+--?????

?

?

?

(11) 使用B S 的迹作为类间的离散度测度，有

()()()()()()22222

2

00001111r B i Ti j Tj k Tk i Ti j Tj k Tk

t S P P μμμμμμμμμμμμ????=-+-+-+-+-+-????

???

?

()

()()

()

2

2

2

000001i Ti j Tj k Tk

P P P P P μμμμμμ-+-+-=

- (12)

这里()()

0,,,,i ijk i j k C s t q iP μ∈=

∑

，()()

0,,,,j

ijk i j k C s t q jP μ

∈=

∑

，()()

0,,,,k ijk i j k C s t q kP μ∈=

∑

。

则最佳阈值(),,s t q '''即为离散度测度r B t S 取得最大值时，即

()()010101

,,max ,,r B s L t L q L s t q Arg t S s t q ≤≤-≤≤-≤≤-'''= (13)

2 基于IGA 的三维OTSU 算法的改进

遗传算法是根据生物进化的模型提出的一种进化算法，它模拟生物优胜劣汰的繁衍过程，算法的步骤主要是初始化群体、适应度评估、选择、遗传和变异等。遗传算法具有易编码、操作简单、全局解空间搜索等优点，但也有待改进的地方：易退化、早熟收敛、收敛性能差等。免疫算法是模拟生物体的免疫系统对从外界入侵的细菌、病毒进行防御的一种优化

算法，其特点是操作简单、收敛速度快，算法的核心是疫苗的提取和接种。

目前，免疫遗传算法(Immunity Genetic Algorithm ，简称IGA )存在多种结合模式，本为所采取的是将免疫因子融入到遗传算法当中，可以有效克服遗传算法的早熟收敛和收敛性能

差的缺点，提高收敛速和搜索效率[6,7]

。本文又将传统的免疫遗传算法进行了还进，将三维OTSU 阈值法和改进后的免疫遗传算法结合到一起，可以改善三维OTSU 阈值法的分割效果，提高运算速度。改进算法的主要步骤如下：

(1)编码

由于图像的灰度级别为0~255，将每个染色体的编码长度设置为8bit ，对于使用三维OTSU 阈值法进行分割，这里定义的每条染色体的长度即为24bit ，它表示某个阈值。

(2)初始化

对于初始群体的产生，一般采用的是随机的方法。由于初始群体的规模会影响算法的执行效率和结果。规模太大，则计算复杂性提高，运行时间较长；规模太小，则会导致搜索空间国小，不利于求取最优解。我们在区间0~255以同等概率随机生成30个个体，作为初始群体。

(3)适应度函数的确定 在遗传过程中，每一代都有许多不同的染色体，适应度的大小将决定都有哪些染色体遗传到下一代。本文采用的适应度函数是式(12)，适应度值越大，则越接近最优解。本文在前面已经介绍过，式(12)已经由递推算法对其进行了优化，其计算复杂度由O(L 6)降到了O(L 3)，大大提高了运算速度，本文在计算适应度值时，也是使用递推算法进行计算的。

(4)选择机制

本文采用的选择机制是赌盘法选择机制。将每个个体按照适应度值的大小分布在读盘上，其所占的面积与其适应度的大小成正比。适应度大的个体其遗传到下一代的概率较大、个体数目较多，利于种群的优化；适应度小的个体被遗传到下一代的概率较小、个体数目较少，但可以保证群体的多样性以及适应度小的个体的某些优秀基因片段。

(5)交叉算子

在三维Otsu 算法中，采用的是双点交叉，交叉概率为c P 。在迭代初期交叉概率选的大一些，可以增强搜索能力；在迭代后期可以选的小一些，避免一些优秀的基因遭到破坏，并提高收敛速度。鉴于以上观点，本文采用的自适应交叉概率c P 为：

1c t P T ?=

-??

(14) 式中t 代表了当前遗传代数，T 代表遗传终止代数， m a x

m

a x

m i n

a F F

F F F -=

- (15)

()m a x m

a

x

m i n

c F F x F F F -=

- (16)

式(15)和式(16)中，max F 表示最大适应度值，m in F 表示最小适应度值，F 表示平均适应度值，()F x 表示待交叉的两个个体之间的适应度较大者。

(6)疫苗提取

本文采取的疫苗提取的方法是从当代交叉后的群体中，以适应度最好的个体的全部基因的有效信息作为疫苗进行提取。由于免疫系统产生的抗体具有很强的针对性，所以适应度较高的抗体含有解决问题的特征信息。在改进后的算法中，提取最优个体基因作为疫苗时采用疫苗更新，即在每一代个体进行交叉后，选出当代中适应度最好的个体的全部基因作为疫苗，进行接种，这样可使每一代接种的疫苗最优，还不影响算法的收敛性。

(7)变异算子

为了增强算法的局部搜索能力，本文采用的变异算子为非均匀变异算子，随着进化代数的增加，变异基因位的取值范围越小、与原基因位的值越接近，这样可以保证在进化的后期保住最优个体的基因。本文选取的变异概率m P 为：

m ax m in m ax m ax

1log m P P F F F F P F F

P F F -?

>?

-?

+=?-?

?≤? (17)

其中：m ax P =0.1为最大变异概率，m in P =0.002为最小变异概率，F 为要变异个体的适应度值，

max F 和F 分别表示当代中最大适应度和平均适应度。

(8)疫苗接种

本文选取的疫苗接种方法是动态疫苗接种，即对当代群体中的所有个体上的所有基因，一位一位的使用疫苗上相对应的基因位对其进行改变，并计算改变后的个体的适应度值；若某些个体上的基因与疫苗上相对应的基因相同，则该个体已经是最优个体，不再进行接种，直接遗传到下一代。在三维OTSU 算法中，每个个体表示一个像素点，该像素点的灰度值、邻域均值、邻域中值为该个体上的基因，疫苗接种则是用适应度值最高的个体上的这三个值来依次改变每个个体上的每一位基因，将对其适应度值改变最大并有所提高的那一位基因用免疫疫苗所对应的基因将其覆盖，其它基因位保持不变。

(9)免疫检测

对已经进行疫苗接种的个体进行检测，即计算其接种后的适应度值。若接种后的个体适应度值优于父代的适应度值，则它的子孙代替父代进入下一代种群；若接种后其适应度仍不如父代，则该个体将被父代中所对应的个体取代。

(10)终止准则的确定

最大遗传代数为40代；当相邻两代的平均适应度值的差在范围[0.000，0.005]之内时，则停止迭代。

若不满足终止准则，则以新的群体为初始群体，转到步骤(3)继续进行计算；若满足，则输出结果，结果为适应度值最大的个体。

该算法的流程图如图2所示。

图2 基于IGA的三维Otsu改进算法流程图

Fig.2 Flow chart of three- dimensional Otsu improved arithmetic based on IGA

3 实验结果与分析

仿真实验是在处理器为AMD2800+，1.6GHz，内存为1G的机器上进行的，仿真环境为MATLAB7.0。本次实验采用的是国际标准图像Lean图像，初始群体设置为30个个体，最大迭代次数为40代，实验结果如图3所示。

(a)原始图像(b)三维Otsu算法处理后的图像(c)本文算法处理后的图像

图3 Lean图分割结果图

Fig.3 The result of Lean segmentation chart

对比Lean图的分割结果可以看出，图3(c)较图3(b)的分割效果较好，传统三维Otsu阈值法求得的最佳阈值为(138,125,126)，应用本文的算法求得的阈值为(138,125,127)；而且，在使用本文中的算法对Lean图像进行处理时，在迭代到23代时便得到了最佳阈值，时间为42.37S，相对于使用传统的三维Otsu算法处理Lean图像的140.39S，时间还不到其三分之一，在运算速度上有了大幅度的提高。实时性得到明显提高，分割效果也得到了改善。

4 结束语

三维Otsu阈值分割算法的抗噪能力、分割的稳定性以及分割的效果相对于一维和二维Otsu算法，已经有了很大的提高，但三维Otsu算法的时间复杂度较高，实时性很差。虽然运用递推法已经将三维Otsu算法的时间复杂度从O(L6)降到了O(L3)，但对每一个候选阈值都计算一次的话，计算量非常大，仍然非常耗时。而基于免疫遗传算法改进的三维Otsu阈值分割算法，随机生成初始群体的个数为30，最大迭代次数是40，而且实验证明，往往不需要遗传到40代便可求出最佳结果，与传统的三维Otsu算法相比，运算时间有了明显提高。可见，在图像分割领域，免疫遗传算法可以大大减少寻找最佳阈值的时间，具有很好的应用前景。

参考文献

[1]OTSU N. A threshold selection method from gray2level histogram [J].IEEE Trans on Systems

Man and Cybernetic, 1979, 9 (1): 62-66.

[2]刘健庄,栗文清. 灰度图像的二维Otsu自动阈值分割法[J].自动化学报, 1993, 19 (1) : 101 –

105.

[3]景晓军,李剑锋,刘郁林. 一种基于三维最大类间方差的图像分割算法[J].电子学报, 2003,

31(9):1281-1285.

[4]范九伦,赵凤,张雪峰. 三维Otsu阈值分割方法的递推算法[J].电子学报, 2007, 35(7): 1398

-1402.

[5]Wang Lei. The Immune Genetic Algorithm and Its Converge[A]. ICSP’98[C],1998,3(1)：1347-

1350.

[6]高岩,位耀光,付冬梅等. 免疫遗传算法的研究及其在函数优化中的应用[J].软件时空, 2007,

2(3):183—185.

[7]米焕霞. 关于免疫遗传算法的研究[D],西北大学,2009.

第一作者简介：张玉连(1957- ),女，黑龙江，本科，副教授，主要研究方向为信息检索、

图像处理等。

通讯作者简介：褚巧龙(1983- )，男，河北石家庄，硕士，主要研究方向为图像处理。Email：chuqiaolong123@https://www.wendangku.net/doc/836172773.html,

otsu自适应阈值分割的算法描述和opencv实现,及其在肤色检测中的应用

otsu算法选择使类间方差最大的灰度值为阈值，具有很好的效果 算法具体描述见otsu论文，或冈萨雷斯著名的数字图像处理那本书 这里给出程序流程： 1、计算直方图并归一化histogram 2、计算图像灰度均值avgValue. 3、计算直方图的零阶w[i]和一级矩u[i] 4、计算并找到最大的类间方差（between-class variance） variance[i]=(avgValue*w[i]-u[i])*(avgValue*w[i]-u[i])/(w[i]*(1-w[i])) 对应此最大方差的灰度值即为要找的阈值 5、用找到的阈值二值化图像 我在代码中做了一些优化，所以算法描述的某些地方跟程序并不一致 otsu代码，先找阈值，继而二值化 // implementation of otsu algorithm // author: onezeros(@https://www.wendangku.net/doc/836172773.html,) // reference: Rafael C. Gonzalez. Digital Image Processing Using MATLAB void cvThresholdOtsu(IplImage* src, IplImage* dst) { int height=src->height; int width=src->width; //histogram float histogram[256]= {0}; for(int i=0; iimageData+src->widthStep*i; for(int j=0; j

拓扑-网络连通性算法

网络连通性算法 网络定义 节点与支路的集合，该集合中的节点与支路的连接关系可通过一节点-节点关联矩阵A 充分表达： A =[a ij ]n ×n i,j=1,2,…,n 式中：a ij =???间有支路直接相连。 与节点，当节点间无支路直接相连，与节点，当节点j i 1j i 0 n —网络节点数 连通性算法 理论算法： 称矩阵A 为网络一级连通矩阵，A 2为二级连通矩阵，…，A n-1为n-1级连通矩阵。 A 2=AA =[a 2ij ]n ×n i,j=1,2,…,n 式中：a 2ij =???相连。节点间有支路直接或经第 与节点，当节点相连，节点间无支路直接且经第与节点，当节点k 3j i 1 3j i 0k k=1,2,…,n ，k ≠i,j …… A n-1= 个1-?n A AA =[a n-1ij ]n ×n i,j =1,2,…,n 式中： a n-1ij =???-?-?个节点相连。，，，间有支路直接或经其它 与节点，当节点个节点相连，，，，间无支路直接且经其它与节点，当节点221j i 1 221j i 0n n 矩阵A n-1的每一线性无关的行或列中“1”元素对应的节点均处于同一连通子集中。 实际算法： 若矩阵A 第i （i=1,2,…,n ）行元素与第j （j=i+1,i+2,…,n ）行元素中第k 列元素a ik 和a jk 同为“1”，则第j 行中的其它“1”元素均填入第i 行的相应列中。结果矩阵A 第i 行中所有“1”元素对应的节点处于同一连通子集中。 数据定义 Nc —元件数 Nd —节点数 NOD （Nc,3）—每个元件的节点编号i 、j 、k KND （Nc ）—每个元件的种类（断路器、隔离开关、母线、线路、变压器……） CNT （Nc ）—每个开关元件的分、合状态（逻辑型，例如：合为“真”，分为“假”） NDS0（Nd ）—每个节点初始所在连通子集编号 NDS （Nd ）—每个节点所在连通子集编号 NCT0（Nc ）—每个元件初始所在连通子集编号

差分进化算法及应用研究

湖南大学 硕士学位论文 差分进化算法及应用研究 姓名：吴亮红 申请学位级别：硕士 专业：控制理论与控制工程指导教师：王耀南 20070310

硕士学位论文 摘要 论文首先介绍了智能优化算法的产生对现代优化技术的重要影响，阐述了智能优化算法的研究和发展对现代优化技术和工程实践应用的必要性，归纳总结了智能优化算法的主要特点，简要介绍了智能优化算法的主要研究内容及应用领域。 对差分进化算法的原理进行了详细的介绍，给出了差分进化算法的伪代码。针对混合整数非线性规划问题的特点，在差分进化算法的变异操作中加入取整运算，提出了一种适合于求解各种混合整数非线性规划问题的改进差分进化算法。同时，采用时变交叉概率因子的方法以提高算法的全局搜索能力和收敛速率。用四个典型测试函数进行了实验研究，实验结果表明，改进的差分进化算法用于求解混合整数非线性规划问题时收敛速度快，精度高，鲁棒性强。 采用非固定多段映射罚函数法处理问题的约束条件，提出了一种用改进差分进化算法求解非线性约束优化问题的新方法。结合差分进化算法两种不同变异方式的特点，引入模拟退火策略，使算法在搜索的初始阶段有较强的全局搜索能力，而在后阶段有较强的局部搜索能力，以提高算法的全局收敛性和收敛速率。用几个典型Benchmarks函数进行了测试，实验结果表明，该方法全局搜索能力强，鲁棒性好，精度高，收敛速度快，是一种求解非线性约束优化问题的有效方法。 为保持所求得的多目标优化问题Pareto最优解的多样性，提出了一种精英保留和根据目标函数值进行排序的多目标优化差分进化算法。对排序策略中目标函数的选择方式进行了分析和比较，并提出了一种确定进化过程中求得的精英解是否进入Pareto最优解集的阈值确定方法。用多个经典测试函数进行了实验分析，并与NSGA-Ⅱ算法进行了比较。实验结果表明，本文方法收敛到问题的Pareto前沿效果良好，获得解的散布范围广，能有效保持所求得的Pareto最优解的多样性。 提出了一种新的基于群体适应度方差自适应二次变异的差分进化算法。该算法在运行过程中根据群体适应度方差的大小，增加一种新的变异算子对最优个体和部分其它个体同时进行变异操作，以提高种群多样性，增强差分进化算法跳出局部最优解的能力。对几种典型Benchmarks函数进行了测试，实验结果表明，该方法能有效避免早熟收敛，显著提高算法的全局搜索能力。提出了将该改进算法用来整定不完全微分PID控制器最优或近似最优参数的新方法。为克服频域中常用的积分性能指标如IAE，ISE和ITSE的不足，提出了一种新的时域性能指标对控制器性能进行测试和评价。用三个典型的控制系统对提出的ASMDE-PID控制器进行了测试。实验结果表明，该方法实现容易，收敛性能稳定，计算效率高。与ZN，GA和ASA方法相比，DE在提高系统单位阶跃响应性能方面效率更高，鲁棒性更强。 为了提高差分进化算法的全局搜索能力和收敛速率，提出了一种双群体伪并行差分

基于定向天线的无线自组网拓扑控制算法研究

基于定向天线的无线自组网拓扑控制算法 研究 作者姓名：孙茜 指导教师：刘军副教授 单位名称：信息科学与工程学院 专业名称：通信工程 东北大学 2011 年6月

Research on Topology Control Algorithm in Ad Hoc Networks Based Directional Antenna By Sun Qian Supervisor：Associate Professor Liu Jun Northeastern University June 2011

东北大学毕业设计（论文）毕业设计（论文）任务书 毕业设计（论文）任务书毕业设计（论文）题目： 基于定向天线的无线自组网拓扑控制算法研究 设计（论文）的基本内容： 论文主要提出了一种无线自组网的异构拓扑控制算法。算法借鉴了现存的网络拓扑控制算法DRNG，在其基础上提出一种基于定向天线的K-DRNG拓扑控制算法，采用定向天线能够降低网络中的节点平均能耗，提高无线资源空间复用性，改善网络性能。 毕业设计课题研究的内容主要包括以下几个方面： 1.深入了解无线自组网的拓扑控制算法； 2.学习了定向天线的基本知识及基于定向天线的拓扑控制算法； 3.提出一种适于异构网络基于定向天线的无线自组网拓扑控制算法； 4.利用NS2网络模拟软件对算法进行了测试，进行性能分析； 5.撰写毕业论文。 毕业设计（论文）专题部分： 题目： 设计或论文专题的基本内容： 学生接受毕业设计（论文）题目日期 第周指导教师签字 年月日

基于定向天线的无线自组网拓扑控制算法研究 摘要 拓扑控制技术是改善无线自组织网络性能的重要手段之一，然而随着网络大规模、多应用和泛在化的发展，定向天线的高增益，节省功率和抗干扰等特点日益引起关注，对采用定向天线的异构自组织网络进行拓扑控制成为研究热点。 提出一种基于定向天线的异构无线自组网拓扑控制算法K-DRNG。算法主要包括三个阶段：信息收集阶段，节点控制发射功率，通过扇区转换机制收集邻域拓扑信息；拓扑构建阶段，节点在邻域内构建定向邻近图，初步确定在所生成拓扑内的邻居节点；拓扑优化阶段，节点间通过删除和添加方向性链路，确保生成拓扑的双向连通性。 使用NS2网络模拟软件对所提出的拓扑控制算法进行测试，结果证明，K-DRNG算法相比基于UDG和DRNG图的拓扑控制算法，能够降低网络中的节点平均能耗，提高无线资源空间复用性，改善网络性能。 关键词：无线自组织网络；拓扑控制；定向天线；异构；NS2

Otsu算法(大律法或最大类间方差法)

Otsu算法(大律法或最大类间方差法) 一、Otsu最大类间方差法原理 利用阈值将原图像分成前景，背景两个图象。 前景：用n1,csum,m1来表示在当前阈值下的前景的点数，质量矩，平均灰度 后景：用n2, sum-csum,m2来表示在当前阈值下的背景的点数，质量矩，平均灰度 当取最佳阈值时，背景应该与前景差别最大，关键在于如何选择衡量差别的标准，而在otsu算法中这个衡量差别的标准就是最大类间方差（英文简称otsu，这也就是这个算法名字的来源），在本程序中类间方差用sb表示，最大类间方差用fmax 关于最大类间方差法（otsu）的性能: 类间方差法对噪音和目标大小十分敏感，它仅对类间方差为单峰的图像产生较好的分割效果。 当目标与背景的大小比例悬殊时，类间方差准则函数可能呈现双峰或多峰，此时效果不好，但是类间方差法是用时最少的。 最大类间方差法（otsu）的公式推导： 记t为前景与背景的分割阈值，前景点数占图像比例为w0，平均灰度为u0；背景点数占图像比例为w1，平均灰度为u1。 则图像的总平均灰度为：u=w0*u0+w1*u1。 前景和背景图象的方差：g=w0*(u0-u)*(u0-u)+w1*(u1-u)*(u1-u)=w0*w1*(u0-u1)*(u0-u1),此公式为方差公式。 可参照概率论课本上面的g的公式也就是下面程序中的sb的表达式。当方差g最大时，可以认为此时前景和背景差异最大，此时的灰度t是最佳阈值sb = w1*w2*(u1-u0)*(u0-u1) 算法实现1： unsafe public int GetThreshValue(Bitmap image) { BitmapData bd = image.LockBits(new Rectangle(0, 0, image.Width, image.Height), ImageLockMode.WriteOnly, image.PixelFormat); byte* pt = (byte*)bd.Scan0; int[] pixelNum = new int[256]; //图象直方图，共256个点 byte color; byte* pline; int n, n1, n2; int total; //total为总和，累计值 double m1, m2, sum, csum, fmax, sb; //sb为类间方差，fmax存储最大方差值 int k, t, q; int threshValue = 1; // 阈值 int step = 1; switch (image.PixelFormat) { case PixelFormat.Format24bppRgb: step = 3; break; case PixelFormat.Format32bppArgb: step = 4; break; case PixelFormat.Format8bppIndexed: step = 1; break; } //生成直方图 for (int i = 0; i < image.Height; i++) { pline = pt + i * bd.Stride; for (int j = 0; j < image.Width; j++) { color = *(pline + j * step); //返回各个点的颜色，以RGB表示 pixelNum[color]++; //相应的直方图加1 } } //直方图平滑化

图论在网络拓扑发现算法中的应用

小 型 微 型 计 算 机 系 统 Journal of Chinese Computer Systems
2008 年 月 第 期 Vol.28 No. 2008
?
图论在网络拓扑发现算法中的应用
路连兵 1+，胡吉明 2，姜 岩 1
1，2
，2
(河海大学 计算机及信息工程学院,江苏 南京
210098)
E-mail ：famioo@https://www.wendangku.net/doc/836172773.html,
摘
要：网络拓扑发现技术已经广泛地应用在各种项目软件中。然而，随着网络结构复杂度升级，这给拓扑发现带来了
挑战。所以我们越来越需要一种高效，准确的网络拓扑算法自动发现网络拓扑结构。目前的拓扑算法主要集中在：(1)路 由层的发现。这个层面的发现算法在技术上比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系， 利用路由器的自身特性，很容易实现。(2)链路层的发现。直到目前为止，已有的厂商工具很难准确发现网络拓扑，已发 表的理论文献知识也只是理论上阐述，实际应用难度比较大。本论文，提出一种基于图论的骨架树数据存储结构算法，可 以高效推断网络的拓扑关系。 关键词：骨架树;子网;地址转发表;图论；信任节点
Topology Discovery in Networks Based on Graph Theory*
LU Lian-Bing1+, HU Ji-Ming2，Jiang Yan1,2
1,2
(School of Computer Science and Information, Hohai University, Nanjing Jiangsu 210098, China)
Abstract: Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, Today's IP network is complex and dynamic. Keeping track of topology information efficiently is a difficult task. So, we need effective algorithms for automatically discovering physical network topology. Earlier work has typically focused on: (1) Layer-3 (network layer) topology, which can only router-to-router interconnections and router interface-to-subnet relationships. This work is relatively easy and has lots of systems can do it. (2)Layer-2(link layer), till now, no tools can discovery the network topology exactly because of bad algorithm. In this paper, Skeleton-tree based on Graph theory is proposed to infer the connections between network nodes. Key words: Skeleton-tree; subnets; Address Forwarding Table; Graph Theory；Trust Node
作者简介: 路连兵(1979－),男,江苏泗洪人,硕士。 主要研究网络自拓扑,软件项目管理,Perl 研究;胡吉明(1967－),男,硕导,副教授,主要研究 领域为计算机应用技术,网络安全,数据挖掘，Z 语言; 姜岩(1979-),男,硕士研究生,主要研究方向,网络应用,中间件

IP网络拓扑自动发现------------------------------------------------------算法比较经典---已读

IP网络拓扑自动发现 自从20世纪90年代以来，越来越多的企业及个人在加入Internet网，使网络规模持续扩大。为了适应越来越多的流量，新节点、新链路不断的被引进到网络上，从而使手工维护很难跟上网络的变化，给网络管理带来困难。 网络由一起工作的大量实体构成，向用户提供某种服务。这些实体功能由硬件和软件执行，一些出现在真实网络中实体的例子有路由器、服务器、普通主机、链路等，所有这些都影响着网络运行的方式及提供给最终用户的服务质量。例如，如果一个应用服务器（Web Server）出现宕机而从网络上剥离下来，那么用户将得不到他们所期望的服务（浏览网页）。提到拓扑发现，一般是指发现完成最终用户服务所涉及到的所有实体，不仅要发现实体，而且要发现实体在网络中所起的作用及实体间互相连接的方式。 网络拓扑对网络管理、网络规划非常有用。例如，网络故障、流量瓶颈等重要信息能直接显示在网络拓扑上，这样网络管理员对当前的网络状况就有一个清楚的认识，对哪里发生了故障一目了然。如果网络拓扑上显示一条链路总处于满负荷传输状态，那么扩大该条链路的容量对提高网络性能将有很大帮助。此外，网络拓扑对网络仿真也十分重要，要仿真能否在现有网络上新开放一种应用，必须首先有正确的网络拓扑。 获得网络拓扑的最简单的方法莫过于让管理员根据实际网络手工绘出其拓扑，但现在网络越来越复杂，越来越庞大，并一直在膨胀，而且实体在网络中担负的功能也越来越复杂，要跟踪这样一个网络需要花费很多时间或精力，而且网络一旦有所改变所有工作必须重做。网络拓扑自动发现正是基于这个原因发展起来的，本文对能用于拓扑发现的一些常用的工具和技术作了简要的介绍，并基于笔者的实践提供了一个简单的算法实现，该算法主要针对同一个管理机构下的IP网络的拓扑自动发现，更复杂的拓扑发现算法可在此基础上进一步扩展。 一、用于拓扑发现的工具 1. Ping

基于TSP的改进差分进化算法

龙源期刊网 https://www.wendangku.net/doc/836172773.html, 基于TSP的改进差分进化算法 作者：朱宇航伏楠 来源：《硅谷》2012年第17期 摘要: 针对TSP问题,提出一种改进的差分进化算法:利用贪心算法产生初始种群,定义特有的编码匹配函数进行变异操作,排序法修复变异个体,并采用顺序交叉,在变异操作之后,加入新的选择机制,防止交叉操作破坏变异出的优良个体,实验结果表明改进后的差分进化算法能够高效地解决TSP问题,体现良好的优化性能。 关键词: 差分进化算法;TSP;进化算法 0 引言 差分进化算法(DE:Differential Evolution)是一种模拟自然进化法则的仿生智能计算方法,在解决复杂的全局优化问题方面,DE的性能更加优秀,过程也更为简单,受控参数少[1],但由于DE 特有的差分操作的限制,DE被成功应用的领域多集中在连续优化领域,在离散优化领域的应用还相对较少[2]。 TSP(旅行商问题)作为典型的离散优化问题,是解决很多实际问题的最终转化形式,同时也是著名的NP难题,在短时间内求出其最优解非常困难,现有解法[3-4]在求解中都各有缺点.因此,研究将DE经过必要的改进后应用于TSP的求解具有重要意义。 1 改进DE算法 1.1 编码及匹配函数 适应度定义为:负的路径长度,使得路径长度越短,适应度值越大。 1.2 贪婪初始化 为提高初始种群的质量,采用贪婪的初始化方法.对于初始种群的每个个体,产生方法如下: step1:初始化待走城市列表List为包含所有城市的列表; step2:随机选择一个城市A作为起点,并将此点作为当前城市T,从List中移除; step3:从List中选择距离城市T最近的城市作为新的当前城市T,并将T从List中移除; step4:判断List是否为空,若是,则结束;若否,则转step3。

最大类间方差法(otsu)的原理

在网上很多地方都可以找到，但是我发觉似乎都是一样，而且一点注释都没有，如果光拿来用当然可以了，可是用一个算法不搞清楚里面的数学是件很遗憾的事情，我把OTSU的代码加上详细的注释，也算是对自己以后继续努力的一个鞭笞吧！ 最大类间方差法（otsu）的原理： 阈值将原图象分成前景，背景两个图象。 前景：用n1, csum, m1来表示在当前阈值下的前景的点数，质量矩，平均灰度后景：用n2, sum-csum, m2来表示在当前阈值下的背景的点数，质量矩，平均灰度 当取最佳阈值时，背景应该与前景差别最大，关键在于如何选择衡量差别的标准而在otsu算法中这个衡量差别的标准就是最大类间方差（英文简称otsu，这也就是这个算法名字的来源） 在本程序中类间方差用sb表示，最大类间方差用fmax 关于最大类间方差法（otsu）的性能: 类间方差法对噪音和目标大小十分敏感，它仅对类间方差为单峰的图像产生较好的分割效果。 当目标与背景的大小比例悬殊时，类间方差准则函数可能呈现双峰或多峰，此时效果不好，但是类间方差法是用时最少的。 最大最大类间方差法（otsu）的公式推导： 记t为前景与背景的分割阈值，前景点数占图像比例为w0，平均灰度为u0；背景点数占图像比例为w1，平均灰度为u1。 则图像的总平均灰度为：u=w0*u0+w1*u1。 前景和背景图象的方差： g=w0*(u0-u)*(u0-u)+w1*(u1-u)*(u1-u)=w0*w1*(u0-u1)*(u0-u1),此公式为方差公式，可参照概率论课本 上面的g的公式也就是下面程序中的sb的表达式 当方差g最大时，可以认为此时前景和背景差异最大，也就是此时的灰度是最佳阈值 unsafe public int GetThreshValue(Bitmap image) { BitmapData bd = (new Rectangle(0, 0, , , , ; byte* pt = (byte*); int[] pixelNum = new int[256]; //图象直方图，共256个点 byte color; byte* pline; int n, n1, n2; int total; //total为总和，累计值 double m1, m2, sum, csum, fmax, sb; //sb为类间方差，fmax存储最大方差值 int k, t, q; int threshValue = 1; // 阈值 int step = 1; switch { case :

OTSU算法进行图像二值化的实现

实习名称：OTSU算法的实现实习日期：2012年05月25日 得分：指导老师：夏志华 系：计算机专业：网络工程年级：大二 班次： 1 班姓名：学号： 实验名称：OTSU算法进行图像二值化的实现 (一)实验目的 1.熟悉otsu算法的原理 2.掌握otsu算法的应用 (二)基本原理 记t为前景与背景的分割阈值,前景点数占图像比例为W0, 平均值U0； 背景点数占图像比例为W1, 平均值为U1. 图像的内积平均值为：u=W0*U0 + W1*U1.从最小灰度值到最大灰度值遍历t,当t使得值g=W0*(U0-u)2+W1*(U1-u)2最大时t即为分割的最佳阈值。 (三)实验步骤 clear; %清屏 clc; G=imread('Tom.jpg'); %打开图像 subplot(2,2,1); %显示图像位置布局 imshow(G); %显示图像 %axis(‘square’); title('原始图像'); I=rgb2gray(G); %将真彩色G转化为灰度图像 subplot(2,2,2); %显示图像位置布局 imshow(I); %显示原始图像 %axis(‘square’); title('灰度化后图像'); I1=I; [p,q]=size(11); thresh=150; for i=1:p %i取从1到p的值 for j=1:q %j取1到q的值 if I1(i,j)>thresh I1(i,j)=255; else I1(i,j)=0; end end end subplot(2,2,3); imshow(I1); %显示灰度化后的图像

%axis(‘square’); title('固定阀值150二值化后图像'); %%%利用OTSU二值化后图像 Hist =zeros(256); %直方图 dHist = zeros(256); variance = zeros(256); %方差 [m,n]=size(1); PXD=0; %用来遍历阀值%%%%%%%%%%%%%%%%%%%%%求出直方图 for i=1:m for j=1:n Hist(I(i,j)+1)=Hist(I(i,j)+1)+1; end end for i=1:256 %i取从1到256的值 dHist(i)=Hist(i)/(m*n); end for PXD=1:256 %PXD取从1到256的值 w0=0; w1=0, u0=0, u1=0, u=0; %大津阈值 for i=1:PXD u0=u0+(i-1)*dHist(i); w0=w0+dHist(i); %m1=g0/w0; end for i=PXD+1:256 %定义函数i u1=u1+(i-1)*dHist(i); w1=w1+dHist(i); %m2=g1/w1; end u=u0*w0+u1*w1; %图像的总平均灰度 variance(PXD)=w0*(u0-u)^2+w1*(u1-u)^2; %分割的最佳阈值end %%%%%%%%%%%%%%%%%%%% for i=1:m for j=1:n if I(i,j)> PXD-1 I(i,j)=255; else I(i,j)=0; end end end imagBW=I; subplot(2,2,4)

拓扑控制

拓扑控制 1 拓扑控制的意义 无线网络一般具有环境复杂、节点资源受限、网络拓扑不稳定的特点. 不同于有线网络,无线网络可以通过改变各个网络节点传输功率以改变网络的拓扑结构，这就是拓扑控制的实现技术基础。由节点的位置和其无线传输范围所确定的网络拓扑结构对网络的性能有着重大的影响. 如果拓扑结构过于松散,就容易产生网络分区以及增大端到端的时延;相反的,非常密集的拓扑不利于空间重利用,从而减小网络的容量[2]。拓扑管理和控制主要研究如何为节点分配功率以获得具有某种性质的拓扑结构和优化一些网络目标函数,其目的就是提高网络的性能, 降低通信干扰和延长网络的生存时间。 拓扑控制技术是无线网络中最重要的技术之一。在由无线传感器网络生成的网络拓扑中，可以直接通信的两个结点之间存在一条拓扑边。如果没有拓扑控制，所有结点都会以最大无线传输功率工作。在这种情况下，一方面，结点有限的能量将被通信部件快速消耗，降低了网络的生命周期。同时，网络中每个结点的无线信号将覆盖大量其他结点，造成无线信号冲突频繁，影响结点的无线通信质量，降低网络的吞吐率。另一方面，在生成的网络拓扑中将存在大量的边，从而导致网络拓扑信息量大，路由计算复杂，浪费了宝贵的计算资源。因此，需要研究无线传感器网络中的拓扑控制问题，在维持拓扑的某些全局性质的前提下，通过调整结点的发送功率来延长网络生命周期，提高网络吞吐量，降低网络干扰，节约结点资源。 拓扑控制主要研究如何在保证网络连通性的前提下，设计高效的算法为节点分配功率以获得具有某种性质的拓扑结构和优化一些网络目标函数，其目的就是节约节点的发射功率，延长网络的生存时间，提高网络的性能。拓扑控制是无线网络设计和规划的重要组成部分。 拓扑控制技术保证覆盖质量和连通质量，能够降低通信干扰、节省能量，提高MAC(media access control)协议和路由协议的效率。进一步，也可为网络融合提供拓扑基础；此外,拓扑控制还能够提高网络的可靠性、可扩展性等其他性能.总之，拓扑控制对网络性能具有重大的影响，因而对它的研究具有十分重要的意义。 无线网络的特点使拓扑控制成为挑战性研究课题,同时,这些特点也决定了拓扑控制在无线网络研究中的重要性。

差分进化算法的算法设计研究

差分进化算法的算法设计研究 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。而作为一种优化算法，差分进化算法因其有效性，在现代优化技术和工程实践应用中的作用越来越凸显。阐述了差分进化算法的基本概念，对差分简化算法的原理进行了介绍，对算法步骤进行了论述，并结合一物流配送路径优化例子，重点围绕该算法的设计进行分析，为差分进化算法的应用提供了思路。 标签：差分进化算法；算法设计；应用 0 引言 差分进化算法（Differential Evolution ，DE）是一种新兴的进化计算技术。它是由R.Storn 和K.Price于1995 年提出的，最初的设想是用于解决切比雪夫多项式问题，后来发现DE 也是解决复杂优化问题的有效技术。DE 特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。近年来，DE 已经在许多领域得到了应用，譬如人工神经元网络、化工、电力、机械设计、信号处理、路径优化等。 1 差分进化算法概述 1.1 概念 差分进化算法是一种强调在全局中寻找最优解的技术，即通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法，是一种以“适者生存”的理念来进行“优胜劣汰”的智能型算法，同时，差分进化算法在对问题的求解过程中采用了并行搜索的实现方式，通过该方式，大大减少了对问题求解过程中所需要的时间。差分进化算法通过非常简单的算法结构，趋于智能化的适应条件判断来进行新一代种群的生成，并最终通过适应条件判断来选出全局的最优方案。 1.2 优点 差分进化计算是一种具有鲁棒性的方法，能适应不同的环境不同的问题，而且在大多数情况下都能得到比较满意的有效解。它对问题的整个参数空间给出一种编码方案，而不是直接对问题的具体参数进行处理，不是从某个单一的初始点开始搜索，而是从一组初始点搜索。搜索中用到的是目标函数值的信息，可以不必用到目标函数的导数信息或与具体问题有关的特殊知识。因而进化算法具有广泛的应用性，高度的非线性，易修改性和可并行性。 2 差分进化算法的原理

基于改进的差分进化算法的非均匀阵列综合

基于改进的差分进化算法的非均匀阵列综合 宋晓侠郭陈江丁君 西北工业大学电子信息学院，陕西西安７１０１２９ 摘 要：针对标准差分进化算法早熟收敛和局部搜索能力差的缺陷，采用一种改进的差分进化算法综合非均 匀线阵。该算法在计算过程中自适应调整缩放因子和交叉概率因子，以非均匀阵列天线的阵元间距为优化变 量，实现了阵列的最大峰值旁瓣电平的有效控制。仿真结果表明：该改进算法可应用非均匀天线阵列的综合， 并取得良好的优化结果，简单实用，快速方便，鲁棒性和稳定性好。 天线；非均匀阵列；综合；改进的差分进化算法；峰值旁瓣电平 ＴＮ８２０Ａ１００８－１１９４（２０１２）０４－００７１－０４ Ｓｙｎｔｈｅｓｉｓ　ｏｆ　Ｎｏｎ－ｕｎｉｆｏｒｍ　Ａｒｒａｙｓ　Ｕｓｉｎｇ　Ｍｏｄｉｆｉｅｄ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ ＳＯＮＧ　Ｘｉａｏｘｉａ　ＧＵＯ　Ｃｈｅｎｊｉａｎｇ　ＤＩＮＧ　Ｊｕｎ ２０１２－０２－０６ 西北工业大学研究生创业种子基金项目资助（Ｚ２０１２０７２） 作者简介：宋晓侠（１９８９－），女，安徽人，硕士研究生，研究方向：阵列天线综合。Ｅ－ｍａｉｌ：　ｓｏｎｇｘｘ２０１０２０１１３５＠　ｍａｉｌ．　ｎｗ ｐｕ．　ｅｄｕ．　ｃｎ。 万方数据

将该改进的差分进化算法用来综合非均皇 线阵，在讲化讨程中增加了甜讲ＤＥ算渎而孙理和后万方数据

１４ ７．　３３４　４４ １５ ８．　０５６　９１万方数据

＠＠［１］汪茂光，吕善伟，刘瑞祥．阵列天线分析与综合［Ｍ］．成 都：电子科技大学出版社，１９８９． ＠＠［２］Ｋｕｍａｒ　Ｂ　Ｐ，　Ｂｒａｎｎｅｒ　Ｇ　Ｒ．　Ｇｅｎｅｒａｌｉｚｅｄ　ａｎａｌｙｔｉｃａｌ　ｔｅｃｈｎｉｑｕｅ　 ｆｏｒ　ｔｈｅ　ｓｙｎｔｈｅｓｉｓ　ｏｆ　ｕｎｅｑｕａｌｌｙ　ｓｐａｃｅｄ　ａｒｒａｙｓ　ｗｉｔｈ　ｌｉｎｅａｒ， ｐｌａｎａｒ，　ｃｙｌｉｎｄｒｉｃａｌ　ｏｒ　ｓｐｈｅｒｉｃａｌ　ｇｅｏｍｅｔｒｙ［Ｊ］．　ＩＥＥＥ　Ｔｒａｎｓ． Ｔｒａｎｓ　ｏｎ　Ａｎｔｅｎｎａ　ａｎｄ　Ｐｒｏｐａｇａｔｉｏｎ，　２００５，　５３　（２）：６２１－ ６３４． ＠＠［３］Ｓｔｏｒｎ　Ｒ　Ｐｒｉｃｅ　Ｋ．　Ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ－ａ　ｓｉｍｐｌｅ　ａｎｄ　ｅｆｆｉ ｃｉｅｎｔ　ａｄａｐｔｉｖｅ　ｓｃｈｅｍｅ　ｆｏｒ　ｇｌｏｂａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｖｅｒ　ｃｏｎｔｉｎ ｕｏｕｓ　ｓｐａｃｅｓ［Ｒ］．　ＵＳ：　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　Ｉｎ ｓｔｉｔｕｔｅ，　１９９５． 万方数据

Otsu传统算法和快速算法的matlab实现

说明：每个%%都表示一个模块，每个模块可以单独执行，也可以将%%去掉整体执行。将读入图像修改成自己机子上的，Otsu传统算法执行顺序如下：cell1-cell2-cell3, Otsu快速迭代算法执行顺序如下：cell1-cell2-cell4。%%%%%%%%%%%%%%%%%%%%%%%%%% %% cell1 读入图像1 I=imread('e:/photo/m/rice.png'); %% cell2 显示原图及其直方图 subplot(2,2,1);imshow(I);xlabel('a,原图'); subplot(2,2,2);imhist(I); %% cell3 Otsu法传统算法的参数说明及步骤 %参数说明： %M,N---图像大小 %TT,T-----阈值,使得方差为最大的阈值 %Ib,Ibav,Ibavm----背景图像,背景图像的灰度平均值,合适阈值时对应的背景图像的灰度平均值 %If,Ifav,Ifavm----前景图像,前景图像的灰度平均值,合适阈值时对应的前景图像的灰度平均值 %Iav----图像的平均灰度值（数学期望） %Ivar,Ivarm----方差,值最大的方差 %%%%%%%%%% %步骤： %1.阈值T从图像的最小灰度值开始遍历，直到最大灰度值。 %2.划分前景和后景：所有I>=T的为背景Ib,得出背景所占比例pb与背景的平均灰度值Ibav; %2.划分前景和后景：所有I

OTSU阈值分割的实现

目录 摘要 1原理与实现 (1) 1.1图像分割 (1) 1.2阈值分割 (1) 1.3 OTSU算法 (2) 2 设计实现程序 (4) 3 程序运行结果与分析 (7) 3.1程序运行结果 (7) 3.2 结果分析 (9) 4 心得体会 (11) 参考文献 (12)

摘要 图像分割是图像识别和图像理解的基本前提步骤。图像分割算法一般是基于灰度的两个性质之一：不连续性和相似性。图像的阈值分割是基于图像的相似性根据事先制定的准则将图像分割为相似的区域。图像分割的作用是把反映物体真实情况的、占据不同区域的、具有不同特性的目标区分开来，以便计算各个目标的数字特征。图像分割质量的好坏直接影响后续图像处理的效果，甚至决定其成败，因此，图像分割的作用至关重要。本设计主要是使用阈值分割法中的最大类间方差法（OTSU）的原理来将图像进行不使用库函数和使用库函数的阈值分割，并将两种方法的阈值显示出来进行比较，同时显示不同阈值情况下的图像结果。 关键词：图像分割阈值分割最大类间方差法

1原理与实现 1.1图像分割 数字图像处理的目的之一是图像识别, 而图像分割是图像识别工作的基础。图像分割是将一幅图像分解成若干互不交叠的、有意义的、具有相同性质的区域。这些区域互不交叠, 每一个区域内部的某种特性或特征相同或接近, 而不同区域间的图像特征则有明显差别, 即同一区域内部特性变化平缓, 相对一致, 而区域边界处则特性变化比较剧烈。区域内是一个所有像素都有相邻或相接触像素的集合, 是像素的连通集。在一个连通集中任意两个像素之间, 都存在一条完全由这个集合的元素构成的连通路径。图像分割的基础是像素间的相似性和不连续性。所谓“相似性”是指在某个区域内像素具有某种相似的特性, 如灰度一样, 纹理相同;所谓“不连续性”是指特性不连续, 如灰度值突变等。 图像分割的方法有多种, 依据工作对象来分, 可分为点相关分割和区域相关分割; 按算法分类, 可分为阈值法、界限检测法、匹配法、跟踪法等。然而大多数分割方法都不能将图像完美的分割，具体处理时总是在各种约束条件之间找一种合理的平衡。 1.2阈值分割 阈值处理是一种区域分割技术, 它适用于物体与背景有较强对比的景物分割。它主要是利用图像中要提取的目标物体和背景在灰度上的差异, 选择一个合适的阈值, 通过判断图像中的每一个像素点的特征属性是否满足阈值的要求来确定图像中该像素点应该属于目标区还是应该属于背景区域, 从而产生二值图像。它计算简单, 而且总能用封闭而且连通的边界定义不交叠的区域。 在使用阈值法进行分割技术时, 阈值的选取成为能否正确分割的关键, 若将所有灰度值大于或等于某阈值的像素都被判属于物体, 则将所有灰度值小

otsu

Otsu法灰度图像二值化原理(2012-10-16 15:22:01)转载▼ 标签：otsu 二值化图像分割杂谈分类：学术 Otsu方法是一种全局化的动态二值化方法，又叫大津法，是一种灰度图像二值化的常用算法。该算法的基本思想是：设使用某一个阈值将灰度图像根据灰度大小，分成目标部分和背景部分两类，在这两类的类内方差最小和类间方差最大的时候，得到的阈值是最优的二值化阈值。 我个人对这个算法实践后的结果是：这个算法在光照均匀的时候，可以得到很好的效果，大多数情况下，都可以的到相当不错的效果。而且其本质是很好理解的。说通俗一点的比方，用一个分数线将班上所有学生的成绩分为好学生和差学生两类，要使两类学生的区分看起来最明显，很显然要达到的效果是：好学生和差学生之间要区别最大，同时好学生和好学生之间分数不能拉太大，同时差学生和差学生之间也差距不大。 回到图像的问题上来，对一幅N×M个像素的图像来说。 1°.首先计算图像的平均灰度u，计算如下： 对于一张大小M×N的图像，统计得到全部图像中灰度为i对应的像素个数n(i),于是该图像的平均灰度值 u=∑i*n(i)/(M*N); 2°.列出求解最佳阀值t的相关变量 记t为目标与背景的分割阈值，记目标像素（灰度大于t）占图像的比例为w1，记目标像素的平均灰度为u1： w1= W1/(M*N）,其中的W1是灰度值大于t的统计数 u1= ∑i*n(i)/W1, i>t. 同理，得到背景像素占图像的比例w2，背景像素的平均灰度u2。 3°.求解最佳阀值t是类差别最大 遍历2°中的t，使得G=w1*(u1-u)*(u1-u)+w2*(u2-u)*(u2-u)最大. G最大时，即得到了最佳阈值，与上式子等价的还有：G=(u1-u)*(u1-u)*(u2-u)*(u2-u)；最大 两者的等价关系很容易证明。