细胞膜优化算法

细胞膜优化算法（精选7篇）

细胞膜优化算法 篇1

细胞分割的传统方法有两类:阈值法[1,2]和先验模型法[3]。阈值法计算量小, 算法容易实现, 但阈值很难确定。如果阈值选择过大容易造成过分割, 如果选择过小则会产生分割不够的问题。先验模型法对呈规则椭圆型细胞的简单粘连有较好的分割效果, 但对弱边缘、边缘不连续、带噪等情况下的非规则椭圆型细胞图像不能有效分割。

参考文献[4]提出的无需重初始化水平集模型属于基于梯度的边缘模型, 解决了C-V水平集模型的忽略图像局部特征的问题。另外由于无需重初始化, 极大提升了水平集的进化速度, 具有较高的实用价值。但该模型存在基于梯度的边缘模型固有的问题:对带噪、弱边缘、边缘不连续的图像难以精确分割[5]。目前, 一些文献针对该模型的边缘终止函数进行了优化。参考文献[6]将边缘终止函数中的高斯滤波用Kalman滤波代替, 促使水平集曲线进一步收敛, 同时加快了模型的进化速度;参考文献[7]提出一个无需高斯平滑的边缘终止函数, 不但使模型的边缘定位更精确, 同时减少了约45%的分割时间和迭代次数。然而, 上述改进还是基于梯度的边缘终止函数, 难以从根本上克服基于梯度的边缘模型的缺点。鉴于此, 本文结合局部熵和灰度变换函数构造新的边缘终止函数。实验证明了新的终止函数能够有效克服基于梯度的终止函数固有的缺点, 缩短了进化时间。

本文首次将优化水平集和改进的OTSU阈值法相结合对神经元干细胞NSC (Neural Stem Cells) 图像进行分割, 分别解决了细胞分割中选取细胞团轮廓和分割粘连细胞的难题, 具有很好的分割效果。

1 水平集算法

本文采用无需重初始化的变分水平集模型, 并结合局部熵和灰度变换作为该模型的边缘终止函数, 以实现对细胞团轮廓的提取。

1.1 无需重初始化的水平集模型

无需重初始化的水平集模型属于基于梯度的边缘模型, 如图1所示。它存在基于梯度的边缘模型固有的一些缺点: (1) 对于噪声图像, 梯度值在远离边缘的噪声点处也较大, 导致进化曲线停滞在噪声区域且进化速度慢, 如图1 (d) ; (2) 边缘泄漏。由于梯度值在弱边缘处较小, 导致弱边缘处停止力较弱, 进化曲线易忽略边界继续进化, 如图1 (e) ; (3) 模型对不连续边缘的识别困难, 造成不连续边缘的漏分割, 如图1 (f) 。

1.2 图像局部熵与灰度变换

设M×N为图像的局部窗口大小, I (x, y) 是窗口中坐标为 (x, y) 的像素点灰度值, 则图像局部熵定义为:

其中, 时, 定义E (I) =log (MN) , 当pij=0时, 规定-pijlog pij=0。

采用所属窗口的局部熵值来代表每个像素点, 以获得图像的局部熵描述。通过测试大量体视显微镜下未经染色的NSC图发现, 细胞图局部熵值的变化区间一般较小。如图2 (a) 所示细胞图的局部熵区间为[0.902 5, 0.9997] (M×N=3×3) , 由于动态区间太小, 局部熵图像很难清楚显示。

(1) 线性变换

熵图像E (I) 的灰度范围为[a, b], T1定义了一种作用于E (I) 的操作, 图2 (a) 的熵图像E (I) 经T1变换后的图像如图2 (b) 所示。灰度范围从[0.902 5, 0.999 7]扩展为[0, 1], 但仍存在边缘较弱的问题, 需对其再进行指数变换以突出边缘, 如图2 (c) 所示。

(2) 指数拉伸变换

其中, T2定义了一种作用于原始图像亮度r的操作, s为变换后的亮度, m为阈值, k为拉伸参数。通过函数T2来增强图像对比度, 以突出边缘。

1.3 新的边缘停止函数

本文提出的基于局部熵和灰度变换的新边缘终止函数定义如下:

其中, T1、T2分别定义了作用于E (I) 的线性变换和指数拉伸变换, E (I) 为输入图像I的局部熵图像。K∈[50, 100], m=min{E (I) }+d (max{E (I) }-min{E (I) }) , d∈[0, 1]。实验中对于弱边缘, d值可适当取大, 而K值越大, 边缘和背景的对比度越强。

2 改进的OTSU阈值法

经典OTSU算法和局部递归OTSU算法都是基于灰度统计的分割算法, 它们是基于目标和背景的灰度均值相差较大这一理想情况, 而并未考虑目标与背景的类内平均距离。但实际上, 加大的类内平均距离会造成直方图的叠加, 不利于图像分割。这也是上述两种算法对对比度较低和含噪图像的分割效果往往较差的原因。鉴于此, 本文提出一种改进的OTSU阈值法, 如图3所示。它将类内平均距离引入到阈值选择函数, 新的阈值选择函数为:

对水平集分割后的细胞轮廓, 用阈值T继续分割, 见图3 (b) , 得到的结果如图3 (c) 所示。最后通过膨胀、腐蚀, 得到最终分割结果如图3 (d) 所示。

3 仿真结果与分析

为验证本文算法, 采用大量图像进行实验, 取其中1个NSC图像序列 (160帧, 每帧细胞数为33个, 大小为250×250像素) 作为例证, 此序列具有细胞数目众多, 出现复杂粘连和带噪、弱边缘等特点。由于篇幅限制, 图片不宜过大, 故采用25X的物镜观察细胞。实验中, 局部熵窗口尺寸M×M=3×3。灰度变换参数d=0.9, K=80。水平集参数主要参考参考文献[5]:λ=5.0, u=0.04, v=3.0, τ=5.0。实验是在Intel P4 3.0 GHz, Windows XP 2 048 MB内存的PC上实现, 程序由Matlab 7编写。

分别采用阈值法、先验模型法和本文算法对序列中随机抽取的第102帧图像进行分割, 结果如图4所示。

图4 (b) 显示了阈值法的分割结果, 可见, 不仅将相邻细胞误判为一个整体 (这是由于出现了3个以上的细胞粘连) , 而且还漏标了多个细胞 (这是由于该细胞形状为非规则圆形) 。参考文献[3]先验模型算法在求出细胞的等效半径r、圆形度c和质心o后, 以质心o为圆心, 以r为半径, 划定一个圆形区域来检测细胞的粘连部分。算法对呈规则圆型细胞的复杂粘连有较好效果, 但对特殊形状的复杂粘连分割不够, 见如图4 (c) 。图4 (d) 是本文算法的分割结果, 除了极少数细胞的丢失外, 在细胞的形态信息和位置信息上都有更好的保留, 体现了算法的优越性, 利用人眼观察可以看出分割正确率要比另两种算法高得多。

本文给出了结合优化水平集和改进OTSU阈值的NSC图像分割算法, 分别解决了细胞分割中选取细胞团轮廓和分割粘连细胞的难题。实验结果表明, 相较于其他分割算法, 本文算法对复杂粘连和带噪、弱边缘的细胞图像分割速度更快速、更准确。

参考文献

[1]钱翔, 叶大田.分割神经干细胞图像的两种聚类多阈值分割方法[J].清华大学学报:自然科学版, 2010, 50 (3) :462-465.

[2]鲁劲松, 段侪杰, 俞燕明, 等.细胞DNA指数全自动分析仪及其关键技术[J].仪器仪表学报, 2009, 30 (2) :293-297.

[3]顾广华, 崔冬.白细胞图像的自动分割算法[J].仪器仪表学报, 2009, 30 (9) :1874-1879.

[4]张霞, 王超.医学图像处理技术及发展趋势[J].中外医学研究, 2010, 8 (7) :22-25.

[5]JIANG T Z, YANG F G, FAN Y.An adaptive particle level set method[J].Electronic Notes in Theoretical Computer Science (S1571-0661) , 2001, 46 (12) :214-224.

[6]Ru Zhongliang, Zhu Chuanrui, Zhao Hongbo.Study on the extend finite element method based on level set algorithm[J].Engineering Mechanics, 2011, 28 (7) :20-25.

[7]Lu Ke, He Ning, Xue Jian.A new geometric deformable model for medical image segmentation[J].Chinese of Journal Electronics, 2009, 45 (36) :232-234.

细胞增殖改进型单亲遗传算法分析 篇2

在一般的工程设计中, 单亲遗传算法 (PGA) 不采用交叉算子, 以基因重组算子[1] (基因换位、基因移位、基因倒位) 代替交叉算子进行种群操作, 具有简化遗传操作, 提高运算速度, 不存在“早熟收敛”等优点, 在以下两个方面具有较强的优势:组合优化问题和有约束的复杂工程问题。本文通过模拟生物细胞增殖过程中的分裂过程和坏死过程, 对单亲遗传算法进行优化和改进, 提出了细胞增值改进型单亲遗传算法 (CPGA) 。

一、细胞增值改进型单亲遗传算法 (CPGA) 的基本思想

细胞增殖型单亲遗传算法 (CPGA) 与单亲遗传算法 (PGA) [2]相似, 是将问题的所求解以一定的编码方式表示成“染色体”, 每个染色体中的“基因”都代表着所求解的重要要素, 不同的“基因组合”组成了不同的所求解, 细胞增殖型单亲遗传算法 (CPGA) 将一个“染色体”看为一个细胞, 在此基础上加入了增殖算子和坏死操作, 模拟细胞增殖过程中的细胞有丝分裂和细胞坏死, 进行遗传操作。

二、细胞增值改进型单亲遗传算法 (CPGA) 分析

2.1新增基本概念。细胞增殖:将染色体作为细胞进行有死分裂。细胞坏死:将染色体中不满足指定适应度范围而淘。

2.2编码方法。细胞增值改进型单亲遗传算法 (CPGA) 编码方法主要包括:序号编码方式和实数编码方式。

2.3适应度函数设计。细胞增值改进型单亲遗传算法 (CPGA) 在计算求解过程中不会用到其他指标, 仅以适应度函数为依据, 将问题筛选转化问对适应度函数取值的筛选, 适应度函数的设计主要根据目标函数而定, 通常可有三种设计方式, 适应度函数尺度变换主要有:线性变换、幂函数变换、指数变换。

2.4遗传算子。细胞增值改进型单亲遗传算法 (CPGA) 根据主要编码方式而产生的遗传算子分为四类:选择算子、基因重组算子、基因突变算子、增殖算子。选择算子、基因重组算子和基因突变算子概率范围与单亲遗传算法 (PGA) 相同。

这里我们主要介绍一下增殖算子的原理:在此定义增殖算子为将一个染色体中的基因串长度近似平均分为两份 (若长度为偶数, 则可平均分为两份, 若长度为奇数, 则以后面长度比前面长度多1的准则来分, 如某染色体编码为[348691]或[6897523], 则近似分配后为[348┆691]或[689┆7523]) 。保持右半部分基因不变, 将左半部分基因随机进行突变、换位或倒位操作, 然后以新形成染色体编码为对象进行整体的随机移位操作, 形成第一条染色体;同时保持左半部分基因不变, 将右半部分基因随机进行突变、换位或倒位操作, 然后以新形成编码为对象进行整体的随机移位操作, 形成第二条染色体。

2.5停机条件。细胞增值改进型单亲遗传算法 (CPGA) 与单亲遗传算法 (PGA) 的收敛准则相似, 一般可表示为以下几种情况: (1) 如果问题的最优解可以识别, 则在得到最优解时停机。 (2) 先设置遗传迭代的次数tm, 则当算法运行迭代次数大于等于tm时停机。

2.6基本流程。Step1:编码, 根据所求具体问题确定所采取的编码方式, 对于组合优化问题一般采用序号编码方式, 对于复杂工程优化问题一般采用实数编码方式。

Step2:根据目标函数设计适应度函数, 并确定遗传算子 (包括方式选择和概率参数选择) 。

Step3:根据编码方法产生初始种群, 以适应度函数评价初始种群中的染色体的适应度值大小。

Step4:判断适应度值, 若存在最优个体, 则输出最优个体后停机;否则转下一步。

Step5:增殖操作, 以增殖算子对初始种群进行增殖操作, 若初始种群数为N, 则在增殖操作以后产生新的种群数为3N。 (初始种群N+增殖种群2N)

Step6:坏死操作, 评价新生种群的适应度值大小, 若存在最优个体, 则输出最优个体后停机, 否则以竞标赛选择方法, 取适应度值前面的N个个体组成的新群体进化到下一步, 将剩下的群体坏死后转Step5。

三、结论

细胞增值改进型单亲遗传算法 (CPGA) 在组合优化问题和复杂工程优化问题中相较单亲遗传算法 (PGA) 具有更快的运算速度和更强的全局搜索能力。

参考文献

[1]李茂军.单亲遗传算法理论及应用[D].湖南大学, 2002.

细胞膜优化算法 篇3

关键词：细胞分割,瓶颈检测,Dijkstra算法

0 引言

重叠细胞是由于在一定空间内细胞分布密集导致的。高密度使得细胞与细胞之间容易发生接触, 从而导致在显微成像过程中出现重叠的细胞团或簇。常用的重叠细胞分割方法主要分为分水岭算法[1]、形态学方法[2]、活动轮廓模型法[3]、凹点检测法[4]、椭圆建模法[5]、机器学习法[6]等。例如, Kharma等人[7]提出一种运用椭圆检测自动分割显微细胞图像的方法, 该方法包括两个步骤:首先应用迭代阈值识别和标记细胞前景区域;然后采用基于遗传算法的椭圆检测快速分割重叠细胞。文献[8]提出了一种运用形状分类来分割重叠细胞的方法, 首先运用训练好的形状分类器, 判断当前区域是否属于重叠细胞区域, 如果是, 则根据轮廓特征提取分离点对, 并利用原始图像梯度寻找最优分割路径, 对当前重叠细胞区域进行分割。该方法对于过度重叠的细胞易产生过分割, 并且在寻找分离点对和最优分割路径的过程中, 算法复杂度高, 耗时长。本文针对显微图像中细胞的形状特征, 提出一种基于瓶颈检测和Dijkstra算法的重叠细胞分割方法。该方法主要包括分离点判定和最优路径搜索两个步骤。

1 算法描述

1.1 分离点判定

对原始显微图像进行二值化提取细胞区域。对于重叠细胞的分离, 需要寻找分离点对。基于细胞的轮廓特性, 首先运用瓶颈检测, 初步判定候选分离点对, 然后再进一步通过椭圆拟合判断, 排除掉一些误检的分离点对, 筛选出正确的分离点对。

对于给定的细胞边缘上的任意两点pa和pb, 首先定义它们之间的瓶颈率e:

其中, dist (pa, pb) 表示点pa和pb之间的欧式距离, length (pa, pb) 表示沿着细胞轮廓从pa顺时针行进至pb的路径长度, min{}则表示两个长度中较小的那个值。为了获取候选分离点对, 引入阈值Te, 如果边缘像素点pa和pb的瓶颈率小于阈值Te, 它们则被判定为候选分离点对。本文Te设置为0.5, 如果未检测到候选分离点对, 表明当前区域为单个细胞。

在得到候选分离点对后, 需要对其进行进一步判断。本文采用的是椭圆拟合判断。将所有候选分离点对按瓶颈率大小进行升序排列。首先, 将细胞轮廓由第一对候选分离点对处断开, 得到两段分离边缘L1和L2, 然后, 对这两个分离边缘分别进行椭圆拟合。通常一幅图像中, 同种细胞的大小不会有很大差别。因此, 如果得到的两个拟合椭圆的面积差异较大, 那么相应的分离点对很可能是错误的。令S1和S2分别表示由L1和L2拟合得到的椭圆的面积, r为由这两个面积计算得到的最大面积比, 且r=max (S1/S2, S2/S1) , 若r满足条件r>Tr, 表示得到两个椭圆的面积相差较大, 从而认为相应的候选分离点对是不正确的, 其中Tr为预先设置的一个阈值, 本文取Tr=10。否则, 进一步采用平均代数距离 (mean algebraic distance, MAD) 作为另一个判断标准对该候选分离点对进行判断。令xi表示分离边缘L, L上像素点与拟合的椭圆之间的平均代数距离MAD计算如下:

其中s表示L上像素点的数目, a=[a, b, c, d, e, f]T, xi=[xi2, xiyi, yi2, xi, yi]T, F (a;xi) 表示点xi= (xi, yi) 到椭圆ax2+bxy+cy2+dx+ey+f=0的代数距离, 由F (a;xi) =a·xi=axi2+bxiyi+cyi2+dxi+eyi+f计算得到。MAD可以作为分离边缘拟合误差的度量标准。

分别计算分离边缘L1和L2与由它们拟合得到的椭圆之间的平均代数距离MAD1和MAD2, 并将它们之间的最小值MADmin与一个预先设置的阈值Tmad进行比较。若MADmin满足:

则表示两段分离边缘L1和L2中至少有一段的拟合误差较低, 且相应的候选分离点对被认为是正确的。对于离心率较大的单个细胞, 瓶颈检测会误检测一些候选分离点对。这种情况下, 由两段分离边缘计算得到的拟合误差都将较小, 因此, 这些误检测候选分离点对不能被公式 (3) 排除。为了解决该问题, 引入了另一个判断条件:

其中MADc表示由整个封闭细胞轮廓计算得到的平均代数距离。由于单个细胞近似于椭圆结构, 因此由它们计算得到MADc值通常较小。对于单个细胞误检测的候选分离点对, 可以通过比较拟合误差MADc与先前定义的阈值Tmad进行排除。仅当拟合误差MADmin和MADc分别满足条件 (3) 和 (4) 时, 该区域才被认为是重叠细胞区域, 且相应的候选分离点对才被最终判定为正确的分离点对。阈值Tmad设置为0.01。

1.2 基于Dijkstra算法的最优分割路径搜索

在确定分离点对后, 需要搜索一条最优分割路径将重叠细胞分离开来, 利用图像灰度信息, 提出一种基于最短路径的分离点对连接方法。首先, 根据分离点对获取正方形的局部图像块作为感兴趣区域 (region of interest, ROI) , 局部图像块的边长设定为分离点对之间欧氏距离, 如图1所示, 其中空心点A*和B*为分离点对, 红色正方形区域为感兴趣区域ROI。

直观上, 我们的目标就是在ROI区域内找到一条最强的边界连接分离点对A*和B*。为了达到该目标, 首先定义一个基于图像梯度的能量函数:

其中S表示感兴趣区域。通常来说, 对于该能量函数, 找到一条连接点A*和B*, 同时能使该能量函数最小化的路径就相当于找到了一条用于分离重叠细胞的最优分割路径。我们定义一条连接分离点对A*和B*的4-或者8-连接的路径c, 然后定义路径c的花费 (cost) E (c) :

其中, ci表示路径c上的第i个像素, N表示路径c包含的像素总数目。因此, 可以通过最小化E (c) 获得最优分割路径c*:

在实验过程中, 运用Dijkstra算法[9], 对花费函数 (cost function) E (c) 进行最小化。

2 实验结果与分析

图2为重叠细胞分割结果, 其中第一行为原始图像, 均来自于美国社会血液学数据库, 第二行为细胞分割结果。从图中可以看出, 重叠细胞均被有效分离, 且分离路径能较好地贴合重叠的真实边缘, 即使是重叠细胞之间的弱边界, 该方法也能有效检测。值得注意的是, 利用图像梯度进行最优分割路径搜素, 当重叠细胞之间不存在明显梯度信息时, 该方法将以分离点对之间的欧式距离作为分割路径搜索结果, 这也是目前大部分现有细胞分割方法所采用的方式。

3 结语

本文提出了一种基于瓶颈检测和Dijkstra算法的重叠细胞分割方法。首先通过计算细胞轮廓边缘点之间的瓶颈率得到候选分离点对, 然后进一步运用椭圆拟合法进行判断获取正确的分离点对。针对重叠细胞的分离问题, 提出了一种基于Dijkstra算法的最优分割路径搜索方法。该方法通过充分利用图像的灰度信息, 可自动搜索一条连接分离点对, 且贴合真实细胞边缘的路径, 将重叠细胞分离开来。

参考文献

[1]Lim H N.White blood cell segmentation for acute leukemia bone marrow images[C]In:2012 International Conference on Biomedical Engineering, 2012, 357-361.

[2]Huang J D.An improved algorithm of overlapping cell division[C]In:2010 International Conference on Intelligent Computing and Integrated Systems, 2010, 687-691.

[3]Bergeest J P, Rohr K.Efficient globally optimal segmentation of cells in fluorescence microscopy images using level sets and convex energy functional[J].Medical Image Analysis, 2012, 16 (7) :1436-1444.

[4]Latorre A, Alonso-Nanclares L, Muelas S, et al.Segmentation of neuronal nuclei based on clump splitting and a two-step binarization of images[J].Expert System with Applications, 2013, 40 (16) :6521-6530.

[5]Bai X, Sun C, Zhou F.Splitting touching cells based on concave points and ellipse fitting[J].Pattern Recognition, 2009, 42 (11) :2434-2446.

[6]Wang W.Binary image segmentation of aggregates based on polygonal approximation and classification of concavities[J].Pattern Recognition, 1998, 31 (10) :1503-1524.

[7]Talbot H, Appleton B.Elliptical distance transforms and the object splitting problem[C].In sixth international symposium mathematical morphology, 2002, 229-241.

[8]Wang H, Zhang H, Ray N.Clump splitting via bottleneck detection and shape classification[J].Pattern Recognition, 2012, 45 (7) :2780-2787

细胞膜优化算法 篇4

图像分割就是指把感兴趣的目标与背景分离出来, 并按照不同的含义把目标分割开来, 也就是提取目标。图像分割在图像处理中占了非常重要的位置, 是图像处理中从图像预处理到图像分析处理最为关键的一步骤。一方面它对特征测量、特征提取及度量有重要的影响作用, 是目标表达的基础;另一方面, 对图像分析和理解在图像分割后更加容易[1]。

图像分割是图像中阳性细胞的提取、定量分析的重点。好的图像分割法能对阳性细胞进行计量分析, 并且能进行形态分析等, 图像分割问题的解决对临床病理医生的定量分析、百分比计量具有重要的作用。在临床诊断研究、医学科研研究、病理诊断分析、医学影像信息处理、计算机辅助疾病诊断等方面, 图像分割的应用范围十分广泛。在这些图像处理应用中, 图像分割是不可缺少的一步, 且也是最关键一步。

2 C-均值聚类算法

目前, 图像分割有很多方法, 归根到底, 主要有三种不同的途径。图像分割没有通用的、标准的、唯一的方法。分割方法主要包括:灰度阈值分割法、边缘检测法、区域分割法和聚类法等[2]。

C-均值聚类分割算法最早是由J.Mac Queen提出的, 是在误差平方和准则上把图像分成C类区域[3]。在C-均值聚类分割算法中先要一个准则函数, 依据样本和聚类中心之间的距离, 选择初始聚类中心C个, 划分类别, 然后每一个类的聚类的中心再重新计算。反复不断地对这个过程进行操作, 算出准则函数的值是最小为止, 一般来说都应该选择样本以及其聚类中心的平方误差的总和为准则函数[4]。C-均值聚类算法可以做动态聚类是其最为突出的优点且也是一种不许需要任何方法监督的学习算法。显微细胞彩色图像含有三基色数据, C-均值聚类算法直接运用在显微细胞彩色图像的分割中将难以进行。因此在运用C-均值聚类算法分割前必须要对显微细胞彩色图像进行处理, 将分割样本的数据量减少, 使C-均值聚类算法运行时间缩短。C-均值聚类算法运行如下[5]:

2.1从初始化聚类中心的所有数据点中任取c个初始类均值。

2.2进行迭代, 在第K次时就将数据x归为类Cj (其中j=mini{ (x-mi) }) ;那么均值离Cj最近的类即为数据x。

2.3将类均值更新

2.4假如i符合mik+1=mik, 则算法结束;否则返回 (2) 重新运行。

C-均值聚类算法最主要是要依赖于聚类中心的初始的位置来进行迭代, 在进行运算的过程中并不能保证其结果都是收敛于最优解。所以, 为了使运算结果能够更加的接近正确值, C-均值聚类算法在选择初始聚类中心的方法上要进行比较。C-均值聚类算法在选择初始聚类中心的方法有很多种, 有的在开始就应用已经确定好的n个初始聚类中心, 然后再反复地运算;还有的是先确定一个任意隶属矩阵, 然后再来运算;C-均值聚类算法也可以通过时间平均, 以在线的方式运行, 导出聚类中心。

在上述的算法中确定好n个初始聚类中心的这种C-均值聚类算法最具有代表性。

3 Ki-67彩色图像分割方法

在本文中以Ki-67彩色图像在HSI空间的特点为例, 提出Ki-67彩色图像分割方法:基于色度学准则先建立一个Ki-67彩色图像的色度学准则, 将Ki-67彩色图像粗分割成只有阳性图像;然后在此基础上用C-均值聚类算法对粗分割后的图像分割, 提取阳性细胞;最后对分割后的阳性细胞图像进行修正, 从而计算出阳性细胞的个数和面积。

3.1进行图像增强处理, 将图像中绿色区域背景颜色值加强,

3.2利用Matlab工具箱对图像进行预处理。

3.3运用色度学准则分割增强后的图像, 分割出包含有阳性细胞图及其它颜色的色彩区的图。

3.4根据此图的特征确定初始聚类中心, 按以下方式确定初始聚类中心:m1=min (X) , m2= (m1+m2) /2, m3=max (X) , X是分割出具有阳性细胞图中的每个像素的R分量值, 将已经确定的聚类数3平分为3类, 使其类间距最大化。

3.5运用C-均值聚类分割法分割该图像, 图像中的每个像素与聚类中心的距离计算出并归集到距离最近的类别中, 每个类别像素值的平均值又再一次计算, 并且其作为下一次迭代的聚类中心, 重复几次, 直到聚类中心值前后两次相等, 那么算法完成。

3.6分割出阳性细胞并提取出来, 对彩色图像进行二值化处理, 然后运用定量分析法对阳性细胞进行定量分析[5]。计算出阳性细胞数量并算出所占百分比数, 可以用于对Ki-67图像定量分析, 对肿瘤进展及预后有较强的数据依据。

4结语

因此, C-均值聚类是最基本的聚类分割方法在显微彩色图像分割中是简单直观、且较易操作, 在图像的彩色数据中聚类方法可以将其看作完整的个体来进行处理并且分割, 可以得到较好的效果。C-均值聚类是最基本的聚类分割方法, 也是最常用的方法。

参考文献

[1]张伟, 王军锋, 王涛, 等.一种基于改进算子的形态学边缘检测算法[J].计算机技术与发展, 2013, 23 (6) :23-26.

[2]侯青, 李伟, 任娜娜, 等.一种改进的中草药显微图像边缘提取算法[J].计算机技术与发展, 2014, 24 (8) :243-245.

[3]刘志文, 安兴, 李衡, 等.显微细胞图像分析方法的研究进展[J].北京理工大学学报, 2014, 34 (5) :441-453.

算法分析与优化 篇5

在进行程序设计时, 同一问题可以用不同的算法解决, 而一个算法的质量优劣将影响到程序运行的效率。在存储空间和程序运行时间要求苛刻的情况下, 就必须对各种算法进行分析, 其目的在于选择合适算法和改进算法。算法分析主要是指分析算法的效率, 它主要包含两方面的内容:算法的运行时间和运行使用空间。我们可以通过对同一问题的不同算法分析来评价这些算法的优劣。

2 算法的运行时间

一个算法执行所耗费的时间, 从理论上是不能算出来的, 必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试, 我们可以通过算法花费的时间与算法中语句的执行次数成正比这种关系来判断不同算法执行所耗费的时间的不同。下面我们通过分析一个具体问题的不同算法来说明各种算法的执行时间效率。

问题描述:求范围[2, n]内的所有素数 (质数) 。

算法一:判断一个整数n是否是素数, 可依次进行n/2, n/3, ..., n/ (n-1) 试除, 如果都没有除尽, 则n是素数, 否则n不是素数。简单说:就是试除到n的前一个数。

算法二:判断一个整数n是否是素数, 可依次进行n/2, n/3, ..., n/ (n/2) 试除, 如果都没有除尽, 则n是素数。否则n不是素数。简单说:就是试除到n的二分之一处。

算法三:判断一个整数n是否是素数, 可依次进行n/2, n/3, ..., n/sqrt (n) 试除, 如果都没有除尽, 则n是素数;否则n不是素数。简单说:就是试除到n的开平方根处。

上述三种算法都涉及到如下双循环语句结构:

其中, “□”处可依次用n-1、n/2、sqrt (n) 分别代替形成前面对应算法。

上述三种算法采用的都是双循环结构, 无论是判断单个数还是判断完所有数, 三种算法的运行次数显然是不同的, 算法一执行次数最多, 算法二位列其次, 算法三执行次数最少。然而, 如果我们逆向思维, 结合第三种算法思想, 以范围内所有整数的可能最简因子作为外循环, 内循环采用排除法, 排除那些因子倍数的非素数, 最后剩下的便是我们所要的范围内的所有素数, 具体算法如图2所示算法四函数模块。

算法四同算法三比较, 算法执行的时间进一步缩短了, 但带来了新的问题:算法在运行过程中增加了内存空间的开销。如何压缩使用内存成为我们接下来需要改进算法的目的所在。

3 算法运行使用空间

针对前面提出的新问题, 我们可以基于如下思想:对于处理一段在连续区间分布的整数, 我们可以利用二进制位和位运算, 通过公式运算将每个整数转换到连续区间分布的某位二进制位上, 从而实现存储空间的压缩使用。如果系统存储一个整数需要2个字节, 则新算法可以实现用1位代替2个字节;如果系统存储一个整数需要4个字节, 则新算法可以实现用1位代替4个字节, 具体算法如图3所示算法五函数模块。

4 结束语

算法设计是软件开发的灵魂, 不同的人可能设计出不同的算法, 每种算法在执行时间和使用空间上可能存在差异。在存储空间和程序运行时间要求苛刻的情况下, 就必须对各种算法进行分析, 以期追求最优的算法。编写好的算法也是一个优秀程序设计人员所追求的目标, 笔者也想借此抛砖引玉, 希望广大程序设计人员设计出最优的算法。

参考文献

[1]严蔚敏.数据结构.北京:清华大学出版社, 2008

[2]黄维通.Visual C++面向对象与可视化程序设计.北京:清华大学出版社, 2001

细胞膜优化算法 篇6

随着课改的不断深入, 部分教师在运用此理念的过程中走入了一些误区.

误区一:把“提倡算法多样化”理解为“一定要算法多样化”

案例两位数减一位数的退位减法.

首先教师通过问题情境出示例题“33-8”.然后在学生独立思考后, 教师组织交流算法的过程中, 在教师精心“引导”、一再追问下, 出现了多种算法:

算法一:33-3=30, 30-5=25.

算法二:33-10=23, 23+2=25.

算法三:13-8=5, 20+5=25.

……

老师:小朋友, 真了不起, 想出了这么多种计算的方法, 以后在计算时, 你喜欢用哪种方法就用哪种方法.

反思上述案例反映了在计算教学中老师对算法多样的认识模糊.算法多样化应是一种态度, 是一个过程, 算法多样化不是教学的最终目的, 不能片面追求形式化.老师不必煞费苦心“索要”多样化的算法, 也不必为了体现多样化, 刻意引导学生寻求“低思维层次算法”.即使有时是教材编排的算法, 但在实际教学中学生中没有出现, 即学生已经超越了“低思维层次算法”, 教师可以不再出示, 没有必要走回头路.片面地追求算法的数量, 而忽视算法背后所代表的学生真实的思维状态, 就很容易把学生引入钻牛角尖和生拼硬凑的误区, 对学生的发展是非常不利的.

误区二:把“算法多样化”理解为“一题多解”

案例苏教版第十一册“根据比例尺求图上距离或实际距离”.

教师出示例7:在一幅比例尺为1∶8000的地图上, 明华小学到少年宫的图上距离是5厘米, 实际距离是多少厘米?学生试做.交流汇报的过程中, 学生出现多种算法, 并都说出了自己的解题思路.

方法三:

解:设明华小学到少年宫的实际距离是x厘米.

方法四:

解:设明华小学到少年宫的实际距离是x米.

师:同学们, 对于以上的几种方法你们都理解吗?下面请同学们用刚才所介绍的几种方法来完成下面练习.

反思上述案例中老师显然误把“算法多样化”理解为“一题多解”.“一题多解”追求的是学生个体方法的多样化, 要求学生个体用多种方法解决同一问题;“算法多样化”追求的是学生群体方法的多样化, 是每一名学生经过自己独立的思考和探索, 提出各自的方法, 对某一个体学生而言, 方法可能只有一种, 但对众多学生而言, 方法就呈现出多样化.笔者认为我们不能简单地将“算法多样化”与“一题多解”混为一谈, 提倡算法多样化并非让学生掌握每一种算法, 而是要通过反馈交流、评价沟通, 让学生体验、学习别人的思维活动的成果, 掌握适合自己的一种或几种算法.这样才能呵护学生主体意识、创新意识, 实现“不同的人在数学上得到不同的发展”.

误区三:把“算法的优化”理解为“方法的固定化”

【案例】解决实际问题中, 学生尝试计算“25×12”的积在交流计算方法的过程中, 学生中出现了多种计算方法:

师:同学们真厉害, 一下子就想出了这么多的方法, 在这些方法中, 你最喜欢哪种方法?

生1:我觉得第一种方法简单, 25×2=50, 比较简单.

生2:我喜欢用第二种方法.

生3:第三种方法使用了乘法分配率, 使计算简便.……

师:其实前面四种方法都使用了运算定律, 使计算简便, 但是, 我们在用简便方法计算时, 凑成整百数最简便, 所以运用第二种方法比较好.下面请同学们运用第二种方法来练一练24×25.

细胞膜优化算法 篇7

无线传感器网络WSN由一组传感器节点以自组织方式构成。每个节点兼备路由器和主机两种功能,不仅要执行感知、传输数据等应用任务,还要参与路由发现、维护以及网络构建等任务。WSN中节点一般采用电池供电,节点大部分情况下被布置在无人看守的环境中,电池不能补充和更换,节点能量受限。在这种情况下要延长网络生存时间就必须降低节点工作时能量消耗,试验表明节点能量主要消耗在通信模块上。无线通信中的传输数据的能量消耗与有效半径的2-4次方相关,减小节点的有效传输半径可以降低节点能量消耗。

另外WSN还有着不同于传统无线网络的其他特征:首先WSN中节点数量庞大,传统的以IP地址为基础的路由协议不适合WSN;其次WSN的应用背景主要是多个源节点感知数据,然后将感知数据传给目的节点Sink,不要求建立网络中任意两点之间的路由路径,这给设计高效的路由协议带来了可能性。因此采用合适的、高效的路由协议是降低无线传感器网络整体能耗的关键。这就需要我们设计一个满足需要的高效的路由协议。

1 相关工作

研究工作者们提出了许多的路由算法,比如SPIN[1](基于协商的路由算法)、DD[2](定向扩散协议)、LEACH[3]、TTDD[4](基于虚拟网格的路由协议)、LAR[5](位置辅助路由协议)等路由协议。他们都很好地解决了无线传感器网络的某方面的问题,但也都存在各自的问题。比如SPIN协议中出现了多个节点向同一个节点同时发送REQ的情况,有关的退避机制需要考虑。DD算法不能用于大规模的网络,主要用于具有大量查询而只有少量事件的应用场景,如果网络拓扑结构频繁变动,它的性能将大幅下降。

在WSN中,从源节点到基站或是到基站的某条传输路径一旦确定,就不会频繁改动,这样就会出现由于路径上的传输节点的失效或暂时不可用导致数据包传输失败,为此需要重新更新路由,增大了能耗和传输延迟。为了解决这个问题,研究工作者们提出了多路径路由[6,7]的概念。多路径路由协议通过将数据流分散到多个不同的路径上传送以实现负载的均衡性,在WSN中体现为能量的均衡性,并且可以通过增加冗余路径来提高网络的可靠性。优化增加了网络的可靠性,但同时也增加了网络能耗。

混合蛙跳算法[8]可以实现路由优化的目的,但是传统的混合蛙跳算法不能将可行解中的优良性能很好地保留在青蛙群体中,它的收敛速度也比较慢,这就表明了传统的混合蛙跳算法不适用于能量有限的无线传感器网络中。

针对以上问题,我们提出了一种改进的混合蛙跳算法来全局优化多路径路由。考虑到混合蛙跳算法的计算量大,所需要的资源信息较多,我们将混合蛙跳算法的执行在基站完成。这样就解决了由于建立多路径导致的网络能量浪费,又实现了多路径路由的优点,实现了WSN多路径路由的全局优化。

2 WSN路由优化算法

混合蛙跳算法是一种基于群体智能的生物进化算法。在WSN中,青蛙群体由一群具有相同结构的青蛙组成。整个群体被分为多个族群,每个族群有自己的思想,执行局部优化策略。在局部优化迭代结束后,各个族群之间进行思想交流,实现族群间的混合运算。达到了路由优化的目的。

2.1 网络模型

WSN网络模型假设如下:

1) 所有节点随机均匀地分布在一矩形区域内。且位置已知。

2) 所有节点与基站均保持静止,节点初始能量相同,并无法补充能量。基站的能量无限大。

3) 所有节点均同构,且唯一ID,并具有数据融合功能。

4) 每个节点的传输功率相同,有效通信距离均一样。

将无线传感器网络模型表示为一个有向图G=(V,E),其中V表示所有节点的集合,E表示所有边的集合。令r为节点v∈V的发射范围,L表示相邻节点间的距离。随机生成F只青蛙组成初始群体,每个青蛙个体表示一条源节点到基点的可行路径为U = (U1,U2 ,…,Ud),其中d表示解空间的维数。例如5个传感器节点组成的网络链路如图1所示。

随机生成的初始群体:

U1={S,1,2,BS} U2={S,1,3,2,BS}

U3={S,1,2,4,BS} U4={S,3,2,BS}

U5={S,1,2,3,4,BS} U6={S,4,BS}

U7={S,3,2,4,BS} U8={S,3,1,2,BS}

U9={S,3,4,BS} U10={S,4,3,2,BS}

2.2 算法描述

路由协议的好坏极大地影响整个网络的性能。好的路由协议不仅能够降低整个网络的能量消耗,延长网络生存周期,还能提高网络的稳定性。基于混合蛙跳算法的多路径路由的优化主要考虑了传输数据的能耗和可靠性两方面来全局优化多路径路由。以下为优化算法的具体步骤:

1) 初始化参数

在无线传感器网络中,按一定规则随机生成F只青蛙组成初始群体,计算青蛙个体的适应度f(i)。青蛙个体的适应度函数定义为:

$F(u)=\frac{1}{{\displaystyle \sum _{x\in v}(}D(u,x)\times g(u))+{\displaystyle \sum _{x\in v}(}R(u,x)\times t(u))+W(u)\times t(u)}$

其中D(u,x)表示源节点u在链路(u,x)上分配的数据流量,g(x,u)表示节点u在链路(x,u)上接收单位数据所消耗的能量,R(x,u)表示节点u在链路(x,u)上接收到的数据流量,t(u,x)表示节点u在链路(u,x)上发送单位数据所消耗的能量,W(u)表示感知的数据量。

2) 构造子族群

将生成的青蛙按适应度降序排列划分成m个族群,构造子族群。在随机生成初始群体之后,将青蛙个体按适应度f(i)降序排列存储于X={Ui},i=1,2,…,F,然后按照以下划分原则将整个青蛙群体分成m个族群Y1,Y2,…,Ym,每个族群中包含n只青蛙,满足下列关系:

Yij=X[j+(i-1)×n] i=1,2,…,m j=1,2,…,n

假设m=3,F只青蛙按适应度由高到低排列,位置位于第1 的青蛙分入第1 族群,第2 的青蛙分入第2 族群,第3 的青蛙分入第3 族群,第4的青蛙分入第1 族群,依次类推,将所有青蛙个体划分到3 个族群中。

3) 局部优化

将青蛙种群划分的多个族群进行局部优化。在每一个子族群中,具有最好适应度的可行路径表示为Ub,最差适应度的可行路径表示为Uw 。对每个子族群的局部优化,主要是对Ub和Uw进行交叉替换操作。具体的操作可如下进行:

(1) 在Ub和Uw中查找它们的公共基因,即查看两条路径是否同时经过某个节点,如果存在公共基因表明可以进行交叉。如果没有,则表明这两个个体不能交叉。

(2) 从选中的这个公共基因开始,直到下一个公共基因 (如果两条路径仅有一个相同节点,则取目的节点为下一个公共节点) ,对Uw进行链路交换。

例如: Ub={S,1,3,4, BS}

Uw={S,1,2,4,BS}

节点1、节点4为公共节点,经过交叉后,Ub不变。Uw变为:

Uw={S,1,3,4,BS}

计算交叉后的最差青蛙的适应度f′(w),如果f′(w)大于交叉前最差青蛙的适应度f(w),则交叉成功,否则交叉失败。如果交叉失败,再选用全局最优青蛙与最差青蛙进行交叉替换。交叉后判断交叉前后的最差青蛙的适应度,如果f′(w)大于f(w),则交叉完成,否则随机产生一个新的青蛙代替原来的最差的青蛙,交叉结束。

(3) 交叉后再对子族群中的所有的青蛙进行变异。每一个青蛙都以固定的概率p进行变异,大量实验表明p的值取0.02比较理想。子族群中的最优青蛙Ub也可能变异,为了防止变异后的Ub变得比原来的适应度差,如果变异后的Ub的适应度f′(b)大于变异前的适应度f(b),则发生变异,否则不进行变异。

4) 全局优化

所有子族群经过一定次数的局部优化后,将所有族群的青蛙混合在一起,重新计算适应度f(i),按适应度f(i)降序排列,重新划分族群,再进行局部优化,如此循环直到满足收敛条件为止。

2.3 算法分析

随机生成青蛙种群的时候,在可行路径中的节点的选择时,加入了节点的剩余能量的考虑。剩余能量越大的节点被选中的概率越大。概率q=E1/E2,E1表示节点的剩余能量,E2表示节点的初始能量。剩余能量的考虑缓解了部分节点因大量使用而死亡的问题。

改进的混合蛙跳算法改进了子族群青蛙局部优化方法,主要是对子族群中青蛙进行交叉变异操作,对子族群中最优青蛙和最差青蛙的交叉操作,考虑了多种情况,避免了局部早熟。随后进行概率变异操作,变异中如果最优的青蛙如果发生变异,要进行比对。这样不仅保证了青蛙个体的多样性,而且保留了青蛙的优良性,缩短了找到全局最优解的时间。

在每次的优化后保存最优的青蛙和次优的青蛙。采用这样的多路径路由可获得比单路路由更好的网络吞吐率和可伸缩性。如果最优路径中的某一个或几个节点的剩余能量很低,并且下一轮的路由更新还没开始,最优路径就不能传输数据。多路径路由就可以只使用次优的路径进行传输,保证了网络的流通,增加了网络的可靠性。

3 算法实现和实验仿真

3.1 算法流程

1) 基站收集网络初始信息。得到网络各个节点的邻居矩阵N和感知数据集合{W(u)|u∈V}。

2) 对网络节点ID编码并初始化青蛙群体。

3) 依据青蛙适应度划分生成青蛙种群。

4) 针对子族群中最优青蛙和最差青蛙进行选择替换操作,然后子群青蛙按概率0.02进行变异。

5) 混合子族群,再重复3)、4)操作;直到满足收敛条件为止。

6) 输出青蛙种群中适应度最优和次优的青蛙作为问题的满意解。

3.2 实验仿真

在下面的实验中,通过仿真网络中节点的通信和节点的能量消耗,主要从网络能量消耗方面进行了实验分析。

基本参数设定

网络的负荷根据控制系统的一般要求设置为:周期性发送和感知数据,各节点的发送数据周期为0.01 s～0.10 s,感知数据周期为0.1 s～0.5 s。青蛙更新迭代次数IT=10。定义网络生存周期为网络从运行开始到网络中死亡节点的百分数低于原来总节点数的50%时所持续的时间。

选择经典的传感网络路由算法定向扩散(DD) 算法作为比较对象。在同一环境下分别对混合蛙跳算法和DD算法的网络生存周期进行仿真测试。仿真结果如图2所示。

从图2中可以看出,采用改进的混合蛙跳算法的WSN路由优化算法具有更长的网络生存周期,并且随着感知数据量的增大,网络生存周期延长的效果越明显。说明混合蛙跳算法对于大数据量的全局优化更加突出。

4 结 语

本文在分析了现有的混合蛙跳算法的基础上,结合无线传感器网络的特点,提出了一种适合于无线传感器网络的路由优化算法。改进的混合蛙跳路由优化算法考虑到了节点的剩余能量,并且复杂的优化计算问题由能源充足、计算和存储能力强大的基站解决,平衡了节点能量负载,节省了能量消耗。仿真实验表明,相比DD算法,新算法均衡了网络能量消耗,有效地提高了网络生存周期,改善了网络性能。

参考文献

[1]WHeinzelman,J Kulik,HBalakrishnan.Adaptive Protocols for Infor-mation Dissemination in Wireless Sensor Networks[C]//Proc.5thACM/IEEE Mobicom,Seattle,WA,Aug 1999:174-85.

[2]C Intanagonwiwat,R Govindan,D Estrin.Directed Diffusion:a Scala-ble and Robust Communication Paradigm for Sensor Networks[C]//Proc.ACMMobi-Com2000,Boston,MA,2000:56-57.

[3]Heinzelman W,Chandrakasan A,Balakrishman H.Energy efficientcommunication protocol for wireless microsensor networks[C]//Proc ofthe 33rd Hawaii International Conference on Systern Sciences.Maui:IEEE Computer.

[4]HLuo,Fan YE,J Cheng,et al.TTDD:A Two-tier Data DisseminationModel for Largescale Wireless Sensor Networks[J].Wireless Net-works,2005,11(2):161-175.

[5]Young-Bae Ko,Nitin H Vaidya.Location-Aided Routing(LAR)inmobile ad hoc networks[J].ACM/Baltzer Wireless Networks(WI-NET)Journal,2000,6(4):307-321.

[6]Lees J,Gerlam.Sp litmultipath routing with maximally disjoint paths inAd Hoc networks[EB/OL].[2008-06-18].http://www.hp l.hp.com/personal/Sung-Ju_Lee/abstracts/papers/icc2001b.pdf.

[7]周集良,李彩霞,曹奇英.基于遗传算法的WSNs多路径路由优化[J].计算机应用,2009(2):521-524.