《基于量子免疫规划的图像分割算法.doc》由会员分享，可在线阅读，更多相关《基于量子免疫规划的图像分割算法.doc（6页珍藏版）》请在三一办公上搜索。
1、精品论文大全基于量子免疫规划的图像分割算法毕晓君，金桂芳哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨（150001）摘要：将量子理论引入到免疫规划中，结合人工免疫系统的克隆选择和免疫机制，提 出了一种新型的进化算法量子免疫规划。并基于阈值分割原理，将量子免疫规划应用到灰度图像分割的阈值选取当中。对测试图像的仿真试验表明，该算法具有快速进化 寻优性能。关键词：免疫规划；量子计算；图像分割-6-0. 前言图像分割是一个古老而具有广阔前景 的问题。基于最大熵准则的图像阈值分割算法可以转化为最优化问题 1 。进化算法是解决优化问题的一种有效方法，但在实际应用中存在着收敛速度慢、收敛过早等问题，大 大
2、影响了其应用效果。针对图像分割的复杂 性和运算量大等问题，本文引入量子计算中 的量子编码以提高进化算法编码的多样性， 并构造具有量子特点的交叉变异算子，从而加快计算速度，保证优化的全局收敛性 2,3 。 为充分利用量子计算的高效并行性，本文在 借用量子理论的同时，继承了人工免疫系统 的克隆选择和免疫机制，与量子计算有机地 结合起来，建立新的进化理论来提高算法的 整体性能，尝试在解决复杂问题时利用局部 特征信息寻找全局最优解的可行性与有效 性。与传统进化算法相比，该算法具有收敛 速度快、寻优能力强的特点。1. 智能计算量子计算机的研究是当前信息领域一 个很活跃的课题，然而关于量子计算更为永 恒和
3、令人激动的理由是它所导致的思考物 理学基本定律的心得，以及它为其他科学技 术所带来的有创见的方法。例如，计算智能 的研究也可以建立在一个物理的基础之上， 量子机理和特性会为计算智能的研究另辟 蹊径，有效利用量子理论的原理和概念，将 会在应用中取得明显优于传统智能计算模 型的结果。因此，量子计算智能(QuantumComputational Intelligence)的出现结合了量子计算和传统智能计算各自的优势，具有很 高的理论价值和发展潜力。1.1 量子计算量子计算(Quantum Computation-QC)首 先由 Benioff P.于 20 世纪 80 年代初提出 4 ， 现已成为各
4、国紧密跟踪的前沿学科之一。量 子计算是相对于经典计算而言的，是量子力 学直接进入算法理论的产物。在量子体系 中，一位的信息位不再是经典的 1 比特，而是由两个本征态的任意叠加态构成，即称之为量子比特位，例如一个 n 位二进制的串在 量子体系中就可同时表示 2 n 个信息，而量 子计算对每个叠加分量(本征态)实现的变换 相当于一种经典计算，所有这些经典计算同 时完成，并按一定的概率振幅叠加起来，给出量子计算的结果5 。量子计算以其独特的 性能引起了广泛关注，并在工程上得到了应 用。1.2 人工免疫系统生命现象和生物的智能行为一直为人 工智能研究者所关注，尤其是近十年人工智 能的成就与生物有着密切
5、关系。免疫系统是 一种高度进化的生物系统，能够识别和消除 病原体，具有学习、记忆和模式识别能力， 因此可以借鉴其信息处理机制用于解决工 程问题。人工免 疫系统 （ Artificial Immune System ,简称 AIS）是模仿自然免疫系统功 能的智能方法。它提供了噪声忍耐、无教师学习、自组织，不需要反面例子，能明晰地表达学习的知识，具有内容记忆和能遗忘很个体所取代；第 2 步是退火选择，即在当前的群体中以概率少使用的信息等进化学习的机理 6 。因而，它结合了分类器、人工神经网络和机器推理等原有一些智能信息处理系统的特点，在解P(xi ) =e f ( xi ) / Tkn0 e f
6、( xi ) / Tki =1(1)决大规模复杂问题方面具有巨大的潜力，并选择个体 x 进入新的群体中，其中 f (x )为ii在人工智能领域掀起了继模糊系统、人工神经网络和进化算法之后的又一个研究热点。 实际上，免疫系统与神经网络、模糊、进化 四种生物现象和体系已经逐步形成了一个 新型的学科生物计算智能系统。1.3 免疫规划我们在对经典进化算法的分析中不难 发现，起到关键作用的两个算子(即交叉和变 异)，都是在一定的概率分布条件下，随机地、 没有指导地对个体进行修正，不可避免地产 生了退化的可能。另一方面，每一个待求的 实际问题都会有自身一些基本的、显而易见 的特征信息或知识，然而经典的进化
7、算法却 忽视了这种特征信息对求解问题的辅助作 用。实践表明，仅仅使用进化规划和以遗传 算法为代表的进化算法，在模仿人类智能寻 优方面还远远不足，必须更加深层次地挖掘 与利用。免疫规划集免疫机制与进化机制于一 体，是人工免疫系统在工程应用中的新思 路。它模拟了人工免疫这一加强人体免疫系 统的手段，利用局部特征信息构造免疫算 子，以一定的强度干预全局并行的搜索进 程，使构造出的算法具有快速全局收敛的良 好性能。免疫算子由接种疫苗和免疫选择两 部分操作构成。前者是为了提高适应度，后 者是为了防止群体的退化。接种疫苗：先在群体中按一定比例随机 抽取部分个体，再按照先验知识修改个体某 些基因位上的基因或
8、其分量，使所得的个体 以较大的概率具有更高的适应度。免疫选择：分两步完成。第 1 步是免疫 检测，即对接种了疫苗的个体进行检测，若 其适应度不如原来个体，则该个体将被原来个体 xi 的适应度，Tk 是趋近于 0 的温度控制序列。免疫规划的流程如图 1 所示：图 1 免疫规划流程图Fig.1 The flow chart of immune programming2. 量子免疫规划量子免疫规划将量子计算的概念引入 到免疫规划中，以量子比特(qubit)和量子叠 加态(superposition of states)为基础，将量子 态的矢量表述引入到抗体编码中，通过量子 门(Q-gate)变换以及
9、其它算子的作用提高抗 体的亲和力，最后多样性消失，量子染色体 收敛于一个状态，所得抗体即为待求问题的 解。2.1 量子染色体编码量子计算中，最小的信息单位为量子比特。一个量子比特的状态可由两个量子态的叠加表示：以上流程中，步骤(1)在初始化时，将染色体中的所有位 ( 0 , 0 ) 都设定为 ii = 0+ 1(2)(1/2 ,1/2 )，表示每一位等概率取 0 或 1。式中， ，0 ，1 为量子比特的状态； ， 为一对复数，代表相应状态出现的概率幅，它们满足：步骤(2)中，由 Q(t ) 生成 P(t ) 是：在第t2i次迭代中，Q(t ) 的第 i 位随机产生一个服从0,1均匀分布的随机数
10、，若该随机数大于 2 + 2 = 122(3)t，则 P(t ) 中的相应位取 1，否则取 0。式中， ， 分别表示量子比特处于状态 0 和状态 1 的概率。对于一个具有 m 个量子比特位的系统， 用量子比特表示的染色体个体为：1 2 L m (4)21 2 L m 这样，就可将 Q(t ) 转化成二进制编码 P(t ) 。步骤(5)中，首先依照交叉概率 Pc 选取若干个个体，将每个染色体次序随机重新排 列，再进行交叉组合，生成新染色体。步骤(6)中，首先依照变异概率 Pm 在选 取某些个体执行变异，采用以下两种变异策2式中， i+ i= 1(i = 1,2,L, m) 。略：一种是将 Q(t
11、 )中某些位随机取值，另一由式(4)定义的染色体可以表示 2 m 个状态， 比传统进化算法具有更好的多样性。随着 2 和 2 趋于 1 或 0，量子比特收敛于一个状态，这时多样性消失，算法收敛。种是将选中个体中量子比特位随机重新排 序。步骤(8)中，常用的量子变换门有：异或 门、受控异或门、Hadamard 变换门和旋转 门。本文使用的量子旋转门为：2.2 量子免疫规划流程量子免疫规划是一种随机搜索算法，设cos( )U = sin sin t+ cos (6)第 t 次迭代生成的所有抗体为：其中， 为旋转角度。这样，每一位量子比Q(t ) = q t , q t ,L, q t (5)特值
12、( tt )12n i , i的更新公式为：式中， q t (i = 1,2,L, n) 由式(4)定义。 t +1 t i量子免疫规划的流程可以描述如下： i it +1 = U ( ) i i (7)(1)初始化 Q(t )，初始化迭代次数 t = 0 。(2)由 Q(t ) 生成 P(t ) ，计算各个抗体的亲和度。(3)提取疫苗。 (4)判断是否满足终止条件，若满足，则停止 计算，输出结果；若不满足，则执行步骤(5)。 (5)执行量子交叉。(6)执行量子变异。(7)执行免疫算子：接种疫苗和免疫更新。(8) t = t + 1 ，用量子变换门U ( ) 更新 Q(t )， 生成 Q(t
13、+ 1) ，转步骤(3)。 可以由多种方法给出，本文 的取值见表1。表 1 量子旋转门中 的取值Tab.1 The value of in the rotation Q-gate其中 ptt= pi ， hti =0t= pi ln pi 。i =0xibesitf (xi ) f (besti ) 0 0 =0 =000true000000false000001true+ 0 01false000010true + 010false000011true+ 011false0000i ii i最佳阈值 t * 使得图像的总熵取得最i i 大值：t * = arg max H (t ) 0t l
14、 -1在多阈值情况下，设 S1，S 2，L，S k是 一 组 分 割 阈 值 ， 且 有S1 S 2 L S k ，则图像的总熵为：H (S1 , S2 ,L, Sk ) S1 S2 l 1= ln pi +ln pi + L +ln pi i =0S1 i=S1 +1 S2 i =Sk +1 l 1表 1 中 xi 为当前抗体的第 i 位；besti 为当前所有抗体中亲和度最高的抗体的第 i位； f (x) 为适应度函数； 为旋转角度的 pi lnpi l =0 S1 pii=0 pi lnpii=S1 +1S2 pii=S1 +1 L pi lnpii=Sk +1l 1 pii=Sk +1
15、大小，表 1 中的 指以相等的概率取 + 或 。(9)最佳阈值12S * , S *,L, S k，使得图像总3. 基于量子免疫规划的图像阈 值分割熵取得最大值：(S * , S * ,L, S * ) = argmaxH (S , S,L, S )12k0S S LS l 1 1 2k3.1基于最大信息熵的图像阈值分割 原理3.2算法设计1 2 k将信息论中 Shannon 熵的概念引入图像 分割当中，使得图像中目标与背景分布的信 息量最大，即通过测量图像灰度直方图的 熵，找出最佳分割阈值。根据 Shannon 熵的概念，对于灰度范围为0,1,L, l 1的图像，其直方图的熵定义为：l 1H
16、 = pi lnpii =0其中 pi 为第 i 个灰度值出现的概率。在单阈值情况下，令 t 为图像的分割阈 值，则图像的总熵为：灰度图像的阈值分割，其难点在于阈值 的选取上。由于图像本身的复杂性，现有的 启发式搜索算法不同程度上均存在运行速 度慢、易形成未成熟收敛等缺点。本文将量 子免疫规划应用到图像分割的阈值选取中， 具体实现步骤如下：步骤 1对原始图像进行直方图均衡来增强 图像。由于图像增强使得噪声的干扰得到加 强，需要增加滤波操作来减少噪声的干扰， 这里采用 55 的均值滤波；步骤 2采用量子免疫规划来完成分割 阈值的寻优过程。在试验中，将图像的总熵H (t )定义为亲和度函数，群体规
17、模 n = 10 ，H (t ) = ln p (1 p ) + ht+ H ht(8)o量 子位数 设为 4 ，循环代 数设为 50 ，ttpt1 ptPm = 0.08 ，Pc = 0.5 ， ij max = 25 ，1 = 2 = 50000 。4. 仿真结果与分析将本文提出的量子免疫规划应用于测 试图像的分割，进行十次独立试验，所得结 果如图 2 所示。通过对运行结果的均值和方 差进行统计比较，并记录 10 次独立运行所 需时间来衡量算法的计算量。从原图可以看 出，图像本身目标区域较多，而且部分区域 对比度较弱。从处理结果来看，量子免疫规 划更多地保留了图像细节，较为精确地分割 出了
18、目标图像，并且较经典遗传算法运行速 度快，搜索时间大大减少，基本运行 20 代 和运行 50 代的结果并无区别，达到预期效 果。图 2 基于量子免疫规划的阈值分割结果Fig.2 Result of image segmentation based on quantum immune programming5. 结论量子免疫规划运行速度快，且具有良好 的全局搜索能力，需要解决的问题越复杂， 它的优越性就 越大。而图像分割本身具有 的特性，使得量子免疫规划的优势得到充分 发挥。尤其是对灰度图像进行多阈值分割 时，随着分割阈值的增加，寻优参数的搜索 空间也急剧增大，然而在以往的进化算法中，群体的多样
19、性和选择性压力不容易同时实现，强的选择性压力必然导致过早收敛， 弱的选择性压力则导致搜索效率过低。本文 引入量子计算理论，采用量子比特染色体编 码，并结合人工免疫系统的克隆选择和免疫 机制，大大改善了优化算法的性能，提高其 收敛速度。理论分析和仿真结果表明，与经 典进化算法、免疫进化算法、量子进化算法 相比，量子免疫规划是一种有效的图像分割 新方法。量子免疫规划的引入虽然不能从根本 上解决图像分割的问题，但作为一种仿生学 算法，它的提出本身就具有开创性，使我们 在图像处理这一难题面前有了更开阔的视 野，不再拘泥于传统的方法之中。随着各种 先进影像设备的发明与改进，既给图像分割 技术带来了挑战，
20、也带来了机遇，量子免疫 规划必将有更广阔的发展空间。如何进一步 增强算法对复杂多峰值图像的分割效果有 待于进一步研究。参考文献1 韩思奇,王蕾.图像分割的阈值法综述J.系统工 程与电子技术,2002(6):91-94.HanSiqi,WangLei. A Survey of Thresholding MethodsforImageSegmentationJ. Systems Engineering and Electronics,2002(6):91-94.2 Han K H, Kim J H. Quantum-inspiredEvolutionaryAlgorithmforaClassofC
21、ombinatorial OptimizationJ. IEEE Trans onEvolutionary Computation, 2002,6(6):580-593.3 Han K H, Kim J H. Genetic Quantum Algorithm and its Application to Combinatorial OptimizationProblemsJ.IEEEConferenceonEvolutionComputation.Piscataway:IEEEPress,2000:1354-1360.4 杨淑媛,刘芳.焦李成.量子进化策略J.电子学报,2001,29(12)
22、:1873-1877.Yang Shuyuan, LiuFang, JiaoLicheng. The QuantumEvolutionary StrategiesJ. Acta Electronica Sinica,2001,29(12):1873-1877.5 Benioff P. The Computer as a Physical System: a MicroscopicQuantum MechanicalHamiltonian Model ofComputers as Represented by Turing MachinesJ. JournalofStatisticalPhysi
23、cs,1980,22(5):563-591.6 焦李成,杜海峰.人工免疫系统进展与展望J.电子学报,2003(10):1540-1548.JiaoLicheng,DuHaifeng.TheEvolutionand Expectation of Artificial Immune SystemJ. Acta Electronica Sinica, 2003(10):1540-1548.7 葛红.免疫算法综述J.华南师范大学学报(自然 科学版),2002(10):120-127.GeHong. Immune Algorithm: A SurveyJ. Journal ofSouth China N
24、ormal University(Natural Science),2002(10):120-127.Image Segmentation Algorithm Based on Quantum ImmuneProgrammingBi Xiaojun, Jin GuifangCollege of Information and Communications Engineering, Harbin Engineering University, Harbin, China (150001)AbstractA quantum immune programming is presented by co
25、mbining quantum theory with the clonal selection and immune mechanism in artificial immune system. Based on the thresholding imagesegmentation principle, the quantum immune programming is applied in the optimization of threshold value of grey image segmentation. The simulation of testing image segmentation proves its superiority.Keywords：immune programming; quantum algorithm; image segmentation
