当前位置:首页 >> 能源/化工 >>

计算智能大作业


题 课 姓 学 专

目:遗传算法在图像处理中的应用研究 程: 计算智能 名: 号: 业:模式识别与智能系统

遗传算法在图像处理中的应用
摘要
遗传算法是一种基于生物自然选择与遗传机理的随机搜索与优化方法。 近年来, 由于遗 传算法求解复杂优化问题的巨大潜力,广泛应用在生物信息学、系统发生学、计算科学、工 程学、经济

学、化学、制造、数学、物理、药物测量学和其他领域之中,这种算法受到了国 内外学者的广泛关注, 尤其是在计算机科学人工智能领域中。 本文介绍了遗传算法基本理论, 描述了它的主要特点和基本性质; 重点综述遗传算法在图像处理中的主要应用, 特别是在图 像分割、图像压缩、图像增强等方面的作用;深入研究目前遗传算法在图像处理领域中存在 的问题,并结合自己的研究方向,对这些问题提出了一些深刻的见解,展望了今后遗传算法 在图像处理应用的发展方向。 关键词 :遗传算法,数字图像处理

1

1.背景介绍
遗传算法(Genetic Algorithm, GA)是一种自适应启发式群体型概率性迭代式的全局 收敛搜索算法,其基本思想来源于生物进化论和群体遗传学,体现了适者生存、 优胜劣汰的进 化原则。 使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基 本思想早在 20 世纪 60 年代初期就由美国 Michigan 大学的 Holland 教授提出,其数学框架也 于 20 世纪 60 年代中期形成。 由于 GA 的整体搜索策略和优化计算不依赖于梯度信息,所以它 的应用范围非常广泛,尤其适合于处理传统方法难以解决的高度复杂的非线性问题。它在自 适应控制、组合优化、模式识别、机器学习、规划策略、信息处理和人工生命等领域的应用 中越来越展示出优越性。 图像处理(image processing),用计算机对图像进行分析,以达到所需结果的技术。又 称影像处理。图像处理一般指数字图像处理。数字图像是指用数字摄像机、扫描仪等设备经 过采样和数字化得到的一个大的二维数组,该数组的元素称为像素,其值为一整数,称为灰 度值。图像处理技术的主要内容包括图像压缩,增强和复原,匹配、描述和识别 3 个部分。 常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。图像 处理一般指数字图像处理。图像处理是计算机视觉中德一个重要研究领域,然而,在图像处 理过程中,如扫描、特征提取、图像分割等不可避免地会存在一些误差,从而影响图像的效 果。 于是, 研究者就开始探索怎么样才能使这些误差最小从而使计算机视觉达到实用化的重 要要求, 最终, 遗传算法凭借其在这些图像处理中的优化计算方面独特的优势成为各种算法 的佼佼者,得到了广泛的应用。

2.遗传算法的原理和基本步骤
遗传算法是一个不断迭代过程的搜索算法,它的基本处理流程如下图所示。

2

由上图可知,遗传算法模拟了自然选择和遗传进化中发生的繁殖、交配和突变现象, 从任意一个初始种群出发,通过随机选择、交叉和变异操作,产生新的更适应环境的个体, 使群体进化到搜索空间中越来越好的区域。这样一代一代不断繁殖、进化,最后收敛到一群 最适应环境的个体上, 求得问题的最优解。 遗传算法对于复杂的优化问题无需建模和复杂运 算,只要利用遗传算法的三种算子就能得到最优解。 GA 结构较为简单,算法也不复杂,但是又具有良好的选择效果,具有自适应性、子 组织性和自学习性等特点,具有许多其它算法没有的优点,主要有: (1)GA 是对参数编码进行操作, 而非对参数本身, 减少约束条件的限制, 如连续性、 可导性、单峰性等。 (2)GA 是多点搜索, 减少了陷于局部优解的风险。 (3)GA 仅用适应度函数来指导搜索, 不需要其他推导和附加信息, 对问题依赖性小。 (4) GA 的寻优规则是概率性的而非确定性的。 研究者们在应用 GA 过程中也不断研究改进 GA 的性能,使 GA 更能满足时代的需要,比 如在选择策略中提出了精英选择、稳态选择和竞争选择等新的机制 ; 在变异环节提出了两 点、 多点和一致变异作为传统一点变异的改进和补充; 在编码环节中应用格雷码和动态编码 等克服传统二进制编码和定点十进制整数编码所就带来的问题 ; 此外, 还提出自适应技术 动态改变 GA 控制参数, 克服采取传统的静态控制参数策略引起的多样性和收敛性不均衡 问题, 以及用梯度方法、单纯型法或模拟退火方法精细调整的混合 GA, 以提高算法的收敛 速度; 用均匀分布的初始群体代替随机产生的初始种群; 研究了分布式 GA、 迁徙 GA 和并行 GA 等, 进一步推动了 GA 的发展。

3.遗传算法在图像处理中的应用
3.1 基于遗传算法的图像增强
图像增强技术是将不清晰的图像经过优化处理变成一张比之前更加清楚, 或者变成一张 使得特点更加鲜明的照片, 以便于对图像再进行后期的加工。 目前图像增强方法主要包括将 图像进行某种变换的频域法和对直接对原始图像进行处理的空域法两种。 而基于遗传算法的 图像增强技术的实现则是利用遗传的选择方法找到一个最优或者局部最优的方法。 具体的操 作方法是,首先将每一个目标值设置一个基位,用实数进行编码,这样问题就转化成求解这 个目标基位组合的题目。然后,对适应度进行设计,适应度设计为个体进化提供动力,在设 置适应度的时候既要考虑图像的整体和局部的质量问题, 也要将结构和细节考虑进去。 再后, 对遗传算子进行设计, 先根据前面设置的适应度值将个体从大到小进行排列, 从中选择优秀 的个体进入下一个程序当中; 为了防止遗传算法在计算的过程中过早收敛, 对种群的多样性 进行保护,在计算过程中采用交叉操作的方法产生新的个体;对进化方向进行微调,采用变 异操作的方法,对一个被选中的变异操作来说,就是采用“1”→“0”和“1”→“0”的方 式进行变异。最后,设置算法的结束条件,一般算法的结束条件就是迭代次数达到了最大进 化代数或者最大适应度的值变化不明显。 例如,对于一幅数字图像 f(.),f(x,y)是图像在 x 行 y 列的像素值。f’(x,y)为增强后 的图像在对应点的像素值。则有:

f' (x ,y ) ? g ? m ? x,y ? ? ? k ? f ? x,y ? ? m ? x,y ? ?
3

其中 g(.)是一个对比度扩展函数。m(x,y)为 x 行 y 列处像素值占在它的某个邻域内的

局部均值。K>0 是一个控制参数,其大小直接影响到图像的处理质量。 因此,数字图像的增强过程可以转化为寻找求最优参数 k 的过程。进而,可用遗传算法 按照上述过程进行寻优。

3.2 基于遗传算法的图像恢复
图像恢复就是把一个退化(或劣化)图像尽量恢复到它的原始面目, 是数字图像处理中 的一个重要分支。目前已提出许多有效的图像恢复方法, 如逆滤波法、维纳滤波法、奇异值 分解伪逆法、最大熵恢复法等 。由于引起图像退化的原因未知或不能用函数表达, 使得上 述方法面临较多的约束问题或是计算量过大问题, 由于难以确定退化函数 h, 限制了其实 际应用的效果。 GA 用于灰度图像的恢复, 一般将染色体编码成以各像素的灰度值为元素的 2 维矩阵, 即一个染色体就代表一幅图像, 每个基因对应一个像素, 采用自然数编码。 每个个体的适应 度函数中 f i 为个体 i 代表的推测恢复图像, g 为观测到的退化图像, h 为退化过程, 函 数值越大表示个体越好。 在交叉操作时一般采用窗口交叉, 即在父代染色体矩阵中选择相同 大小的窗口, 进行交换。变异操作采用临近小范围内的平均值替换需要变异的某一基因值。 此外,GA 也用于彩色图像的恢复,并且取得了很好的效果。 基于 GA 的图像恢复方式, 突破了原有的理论,而且其开放的结构易于与其他方式融合, 如与模糊逻辑相结合的模糊 GA 等。利用 GA 恢复图像不仅较好的克服了噪声的影响, 而且 使图像更平滑, 边缘没有条纹效应, 视觉效果好。 强大的全局搜索能力是遗传算法图像恢复 方法行之有效的主要原因。

3.3 基于遗传算法的图像分割
图像分割是自动目标识别的关键和首要步骤, 其目的是将目标和背景分离, 为计算机视 觉的后续处理提供依据。目前图像分割的方法很多,常用的包括阈值法、边缘检测法和区域 跟踪法。其中域值法是图像分割的最常用方法。 当前常用的域值分割方法如最小误差阈值法、最大类别方差法(Otsu 法)以及最佳直 方图熵法。下面我们以 Kapur 等人提出的最佳熵法(KSW 熵法)为例讨论遗传算法在图像 分割中的应用。KSW 熵法是一种不需要先验知识,而且对于非理想双峰直方图的图像也可以 较好分割的方法。其缺点是在确定阈值时,尤其是确定多阈值时,计算量很大。将信息论中 Shannon 熵概念用于图像分割时,测量图像灰度直方图的熵,由此找出最佳阈值,其出发点 是使图像中目标与背景的信息量最大。 根据 shannon 熵的概念,对于灰度范围{0,1,?,255}的直方图,其熵测量为

H T =-? pi Lnpi
i? 0

l ?1

其中 pi 为第 i 个灰度出现的概率。设阈值 t 将图像划分为目标与背景两类,则令

pt ?

?i
t

?0

pi

H t ? ??i ? 0 pi ln pi
t

由 阈 值 t 分 为 A,B 两 类 后 , 两 类 的 概 率 分 布 分 别 为 p0/pt, pt, ? ,pl/pl; pt+1/(1-pt),pt-2/(1-pt), ?, pt-1/(1-pt), 与每个分布有关的熵分别为 HA(t)和 HB(t)

4

H A( t ) ? ??
i ?0

t

pi p ? 1 Ht ln t ? ln pt ? pt pt pt

y '(x ,y ) ? b0 ? b1x ? b2y ? b3xy
H B( t) ? ?

? i t

l ?1

pi
1 ? pt

ln

pi
1 ? pt

? ?1

? ln(1 ? pt ) ?

HT ? Ht 1 ? pt

图像的总熵 H(t)为 HA(t)和 HB(t)之和,即:

H( t ) ? ln pt(1 ? pt ) ?

Ht HT ? Ht ? pt 1 ? pt

当该函数取最大值时即为图像的最佳分割,因此将其作为遗传算法中的适应度函数。 (1) 编码。我们选取有 255 个灰度级的灰度图,由于图像灰度值在 0-255 之间,故将 各个染色体编码为 8 位二进制编码,代表某个分割阈值。初始代个体的值为随即产生,其 对应的适应度值也各有高低。 (2) 群体体模型。若个体数过多,则每一代适应度值的计算机过大,因此个体数应设置 合理。我们在此将个体数设为 10, 最大繁殖代数为 50. (3) 解码。对二进制染色体数组解密为 0-255 之间的值,以求其适应度值。 (4) 适应度函数。采用 H(t)式作为适应度函数。 (5) 算法的基本操作:选择:遗传算法的收敛定义指出保留最优个体(精英策略的遗传 算法全局收敛。因此本文在进行选择操作时,先进行轮盘赌选择法(蒙特卡罗法),再采用 精英策略。交叉:交叉互换的目的是产生不同于父体的子体。交叉率越大,交叉操作的可能 性也越大;如果交叉率太低,收敛速度可能降低。单阈值分割由于只有一个参数,所以采用 单点交叉,在此设交叉率为 0.6。变异:变异是子代基因按小概率扰动产生的变化。本文选 取变异概率为 0.1。终止准则:规定算法执行到最大代数(50 代)或经过某些代进化,群 体的最高适应度不再发生变化(稳定条件),算法停止,具有最高适应度值的个体即为分割 阈值。

3.4 基于遗传算法的图像压缩
图像压缩技术最主要的原理就是将拥有自相似性的对象用这一组简单的代数关系式进 行表达的过程。将互相不重叠的小块定义为值域块,然后进行编码,并使经过映射后的定义 域块与值域块的距离在某种度量值下最小, 在分解和处理过程中, 由于值域块的数量过于庞 大,压缩搜索过程任务繁重,遗传算法的强大全局搜索能力就能很好的派上用场,发挥良好 的效果。 有研究者用区域块左上角的坐标 x, y 和区域块的旋转变换 z (共有 8 种旋转)进行染 色体编码, 在搜索最优定义域块时使用的两个参数是定义域块相对于值域块位移的水平和垂 直分量( xi, yi ), 用 10 位二进制串对其进行编码, 每个参数用 5 位编码;有一种带分类的 编码法, 这样的编码具有特征集中, 搜索速度快的特点,能够改进遗传算法的速度, 克服压 缩中分类匹配算法的局部最优和随机搜索问题。

3.5 基于遗传算法的图像匹配
5

图像匹配是图像处理中一个重要的课题,在计算机视觉、运动目标跟踪与识别、序列图 像压缩中运动补偿、 医学图像处理等领域有广阔的应用前景.在对图像的理解中,匹配技术起 着重要的作用,是实现图像理解的基础。下面介绍一种基于遗传算法的图像校准函数辨识方 法。 假设灰度图像 A 上一点(x,y)的灰度为 A(x,y)。定义下面的非线性变换:

x '(x ,y ) ? a0 ? a1x ? a2y ? a3xy

y '(x ,y ) ? b0 ? b1x ? b2y ? b3xy

经过以上变换,得到图像 A’。现在要考虑的是确定系数 a0,a1,a2,a3,和 b0,b1,b2, b3,使图像 A’与歪斜图像 B 之间的误差最小,则我们根据获得的变换图像推断歪斜图像 B 中发生了变化的部分。将遗传算法应用于变换函数的辨识, 考虑对系数 (a0,a1,a2,a3,b0,b1,b2,b3)进行个体染色体编码,个体的适应度可根据其系数计算变换后 图像 A’与歪斜图像 B 之间的误差进行评价,误差值可按下式计算。个体的误差值越小,则 其适应度越大。

(A '(x ',y ') ? B(x ',y ')) ? ? y
x' '

2

由于未考虑歪斜图像灰度的变化(除局部的变化外),在对于歪斜之外的变化很大的场 合,用这种方法进行图像校准是不合适的。

4.遗传算法在图像处理中的缺陷及改进
(1)遗传算法用于图像增强技术能够很好的达到预期效果,但是在时间上 进行考量, 目前的方法在寻找最优解方面速度好比较慢,可以考虑在运算过程中 使用并行遗传算法,是未来遗传算法在这个领域的发展方向。 (2)在图像恢复技术中,遗传算法的计算量相对较大,而且解不止一个, 未来要在编码技术上多投入精力,解决遗传算法早熟的问题。 (3)遗传算法在图像重建过程中还没能形成一个成熟的算法,目前拥有的 算法都具有一些问题,如速度较慢,处理出的图像边缘不清晰等,需要进行更多 有效的探索。 (4)在图形压缩技术方面,由于遗传算法在寻找最优解和分形计算时间上 具有一定的优势, 但是控制参数一般都是经验获得的,如何自适应的控制这些参 数是未来发展的趋势, 也是增强压缩和解码质量的一个重要手段,遗传算法与分 形结构的结合具有良好的发展前景。
6

随着理论研究的深入,可以肯定,GA 以其特有的算法特点使其在图像处理问题中的应用 会越来越广;同时,广泛的数学方法和强大的计算机模拟工具的出现,必将使 GA 研究取得 长足的进展,使 GA 在图像处理中的作用更趋完善。

7


相关文章:
智能计算大作业
智能计算大作业_机械/仪表_工程科技_专业资料。1.1 问题描述求解 Rastrigin ...由初始解 i 和控制参数初值 t 开始,对当前解重复“产生新解→计算目标函 数...
智能计算结课大作业
智能计算结课大作业_理学_高等教育_教育专区。用Hopfield网络实现联想记忆、用SOFM...由于神经网络是并行计算的,其计算量不随维数的增加 而发生指数性“爆炸”,因而...
计算智能大作业
计算智能大作业_信息与通信_工程科技_专业资料。1.BP 神经网络基本原理 1.1 人工神经元模式 神经网络是由大量简单处理单元组成, 通过可变权值连接而成的并行分布式...
计算智能大作业
计算智能大作业_能源/化工_工程科技_专业资料。遗传算法在图像处理中的应用研究。题课姓学专 目:遗传算法在图像处理中的应用研究 程: 计算智能 名: 号: 业:...
计算智能理论作业
智能计算结课大作业 29页 2下载券 计算智能的作业说明 30页 1下载券 智能计算...几种智能计算方法的研究及应用进展本文对几种常用的智能计算方法(遗传算法、粒子...
人工智能大作业
人工智能大作业_计算机软件及应用_IT/计算机_专业资料。西电人工智能大作业。...(5)SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量...
智能计算期末作业
大连理工大学智能计算期末大作业,包括神经网络,蚂蚁算法,模糊聚类,小生境PSO算法等等。大连理工大学智能计算期末大作业,包括神经网络,蚂蚁算法,模糊聚类,小生境PSO算法...
计算智能作业三
计算智能作业三_工学_高等教育_教育专区。SY14035 班 刘利芬 要程序及仿真结果。 clear; clc; SY1403505 采用了遗传算法进行最短距离的求解,作业中设置的城市个...
智能控制大作业
智能控制》大作业姓名: 1、简答题: 1.1.根据目前智能控制系统的研究和发展...3) 在传统控制系统中起优化计算作用; 4)在与其它智能控制方法和优化算法相融合...
智能计算第一次作业
智能计算第一次作业_计算机软件及应用_IT/计算机_专业资料。智能计算,证据理论 ...小结以上所有提出的方法各有优缺点, 大部分问题的解决都是针对于具体情况提出的...
更多相关标签:
作业帮智能计算器 | 作业帮智能计算器在线 | 作业帮智能计算器网址 | 智能计数器 | 计算器智能 | 人工智能计算 | 智能控制大作业 | 人工智能大作业 |