基于智能遗传算法和Otsu法的多目标图像分割方法

1、第期 测绘科技情报 总第 期 基于智能遗传算法和 法的 多目标图像分割方法 吴世英 郑肇葆 虞欣 （ 武汉大学遥感信息工程学院， 武汉市珞喻路 号， ） 摘 要 为了克服传统遗传算法在优化多目标图像分割参数时易陷入局部收敛和搜索效率低的缺陷， 本文提出一种基于智能遗传算法和 法的多目标图像分割方法， 并将它应用于航空影像的分割。 实验结果表明， 本文提出的算法比传统遗传算法可以更加快速、 更稳定地获取图像分割的最优阈值。 关键词 智能遗传算法 ； 正交设计 ； 法； 图像分割 随着各种搜索算法的不断涌现 ， 它们常 被引入图像分割领域 ， 用来搜索图像分割的 最佳阈值。遗传算法就是其中一种，

2、在优化参 数较少， 遗传编码较短的情况下 ， 它的寻优搜 索效率较高 ， 可以得到较好的分割阈值 ； 然而 对 于 分 割 阈 值 （ 即 参 数 ） 较 多，遗 传 编 码 较 长 的情况下 ， 该算法则极易陷入局部收敛， 出现 过早收敛现象 ， 搜索的效率明显下降， 从而不 能取得令人满意的分割效果。为了克服传统 遗传算法的这一不足， 近年来， 在传统遗传算 法基础上发 展起来一种 新 的 算 法 智 能 遗 传算法 。该算法改变了传统算法基于对染 色体本身选 优和基因随 机交叉的 遗传模 式 ， 将正交设计的思想引入染色体内的基因选优 的操作中， 对交叉操作进行 “正交化” 然后根 ，

3、据基因评价函数， 计算得到染色体内的每个 基因的优劣评价值， 从而依据这个优劣评价 值进行选择操作。 这样， 一方面既把原来对整 个染色体的选优， 转变到染色体内单个基因 的选优， 即将选优具体到染色体内的每一个 基因； 另一方面该算法又克服原有算法中随 机的 “盲目 ” 的搜索， 它将 交叉建立在 优质基 因的强强联合上， 这体现出遗传的智能性， 从 而提高算法的全局搜索能力和稳定性。鉴于 此， 本文提出了一种基于智能遗传算法和 法 的 多 目 标 图 像 分 割 方 法 ， 并 将 它 应 用于航空影像的分割。 实验结果表明， 本文提 出的算法比 传统遗传算 法可以更加 快速 、 稳 定地

4、获得图像分割的最优阈值。 基于智能遗传算法的图像分割 算法的基本原理 本文结合对图像进行两类和三类目标的 分割， 介绍智能遗传算法的基本思想， 但此方 法亦可推广到更多目标的图像分割。 种群个体及编码 基于 法三类目标的图像分割， 就是 要确定基于最大类间方差准则的最优分割阈 值组， 而智能遗传算法可用来在解空间中搜 索这种最优分割阈值组。对于 级（ ） 的 每个阈值进行八位二进制编码 （ 如图 所 示） ， 把它作为种群个体， 也即染色体。 t t 灰度图像， 为便于进行遗传操作， 将阈值组中 适应度函数的设计 在本文实验中， 对 法中最大类间方 差这个准则进行了改进， 采用如下的准则（ 也

5、 Á Â 图 一个个体的二进制编码 第期 测绘科技情报 总第 期 称为适应度函数） 。 （ ） 式中， （，）表示第 类与第 类之间的灰度协方 差， （，）表示第 类的灰度方差， 最后得到的最 优分割阈值组（，）应使适应度值达到最大。 验的基因组合均匀分布在染色体对所有基因 组合的空间内， 所以通过所得到的正交设计 基因组合的试验也就具有代表性， 从而根据 基因评价函数计算得到的每个基因对适应度 的贡献评价就具有可信度。有了每个基因的 优劣评价值， 就可以从染色体对中选出每个 基因位上相对较好的优质基因， 从而实现基 于父体染色体内的优质基因强强联合的智能 交叉。 下面以三

6、类分割为例， 介绍智能交叉的过程 和基因选优的基本原理。 假设遗传优化时的一对 待交叉染色体分别为 ： 和 智能交叉与基因选优 为了从待交叉的一对染色体基因中选出 对适应度贡献较大的优质基因， 虽然可以把 染色体对 中基因的所 有组合都进 行试验， 得 出每次基因组合的适应度值， 然后统计每个 基因对适应度的贡献大小， 能实现对染色体 对中每个基因的优劣评价。 这虽然可行， 但计 算工作量势必太大。为了减少基因组合的试 验次数， 同时又使试验不失代表性， 我们采用 正交设计的思想对染色体对的基因进行 “正 交化” 的组合。 这种正交设计的方法能使得试 ： 。 （ ） 根据待 交 叉 染 色 体

7、 对 、 具 有 的 基 因位数（ ） 和每个基因位上的可能取值个数 （ 两个） ， 生成进行正交设计试验 所需的正交 表 （）（ 如表 所示） 。 表 正交表 第期 吴世英 郑肇葆 虞欣 ：基于智能遗传算法和 法的多目标图像分割方法 总第 期 每个染色体基因位有 个， 在智能交叉 操作中， 每个基因的取值只有两种选择， 要么 来自待交叉的染色体 ， 要么就来自待交叉 的染色体 。我们把每个基因作为一个因素 （ 用 表示， ） 对待 ， 每 个 因 素 有 两 种 选 择， 称为水平数（ 用 表示， ） ， 根据以上原 则生成正交设计所需的正交表 （ ）， 表示 由于是两个染色体交叉， 每个基

8、因位上 的取值有两种情况， 在表中用 表示在该位 表示在该位置上取来自 对应位的基因值。 置上取来自 对应位的基因值， 与此相同， 以 表 中 的 第 三 行 为 例 ， 比 如 ： 在 第 个 基 因 位 上 的 值 为 ， 则 在这个 基因位上 取来自 中第 一位的值， 即 个基因位上取来自 中第 位的值， 即为 ， 基因位上的智能交叉的结果见表 。 表 智能交叉 试验的次数（ 在表 中， ） 。从表 中， 可 以看到正交表的列数等于因素个数 （ 基因的 位 数） ， 因素的水 平数与正 交表 的 水 平 数 一 致。此外， 正交表具有整齐可比性， 即表中任 一列中出现 、 的次数（ 或机

9、 会 ） 相 等 （ 都 是 为 ； 再看第 个 基 因 位 上 的 值 为 ， 则 在 这 次） ； 如果把表中任意两列同一行的两个 数 字 看 成 有 序 数 对 （ ， ） 、 ， ） 、 ， ） 和 （ （ （ ， ） ， 则每 种 数 对 出 现 的 次 数 也 相 同 （ 均 衡 搭配性） 。 所以这种正交设计试验可以使得基 因的取值均匀地分布在所有可能的解空间 内。在本文的实验中， 次试验就可以满足 整齐可比性和均衡搭配性， 从而使得这 次 试验 中基因的取 值均匀地分 布在解空间 中 。 而且， 基因 的组合次 数从原来 的 次 （ 穷 尽 法） 减 少为 次， 这大 大地减少

10、 了 计 算 工 作 量。 f f 如此， 便可以得到智能交叉的结果为 （ 表 中的最后一行） 。这 样将得到的 次交叉结果， 依次组成另一个 示每次试验的适应度值（ 见表 ） 。 表， 称之为正交试验方案表， 表中最后一列表 ÃÂ Â Á Â ÃÁ Â 第期 1 S1 S12 !" Á Â Ã Ä Å Æ Ç È É Â Á Á Ã Ä Å Æ

11、Â Ç È É Â Ã Â Ä Å Æ Ç Ã È É Â Â Ä Á ÂÂ ÂÂ Â 测绘科技情报 总第 期 表 正交试验方案表 Á S i1 1 S16 S i2 2 S16 Á Â Ã Ä Å Æ Ç È É Â Á Ã Ä

12、 Å Æ Â Ç Á È É Ã Â Ä Å Æ Ç Ã È É Â Ä Á Â Â Â 第期 吴世英 郑肇葆 虞欣 ：基于智能遗传算法和 法的多目标图像分割方法 总第 期 （ ） 依据得到的方案表， 将方案表的每一 （ 即得到表 中的倒数第二和第三行） ， 通过 比较同一列中两个数值的大小， 确定它们的 优劣。 所以， 从染色体对中选择每一个对应基 因位上对适应度值贡献较大的

13、基因 （ 见表 中的最 后一行） ， 作为 优质基因 ， 最后可以 得 到所有基因位上优质（ 最好） 基因的一个组合 （ 子 体） （ ） ， 和较差 基 因 的 另一组 合 （ ） 。 至 此 ， 就 实 现了对父体染色体对 、 基因的智能交叉和 优质基因的选择过程。 由于正交设计试验所用的正交表具有统 计意义 上的相互独 立（ 即正交 的涵义） ， 因 此 在不必顾及基因相互干扰的情况下， 每个基 因对适应度的影响可以通过评价函数快速地 估计出来。 正是由于对基因优劣的这种评价， 使得交叉成为一种有目的、有选择的智能行 为， 进而使得整个遗传搜索更加有效和快速。 （ ） 为了保证得到的后代

14、是最好的， 在完 成上述的基础上， 将得到的两个子体与原有 两个父体一起进行比较， 再从中选取两个最 好的个体（ 适应度值高） 作为最终的结果。 由于智能交叉是基于染色体每个基因的 交叉和选优， 这种选优比传统遗传算法中的 基于整个染色体本身的选择来得更加细致和 具体， 因此， 在智能遗传算法中将传统遗传算 法中的选择操作， 融入到智能交叉之中， 从而 提高了算法的效率。 从这个意义上说， 智能遗 传算法可以看作一种压缩型的遗传算法。 行组合作为一次试验的编码， 按前、 后八位分 别作为一个单元， 并解码为 至 的灰度 割后的适应度值 ， 也即为表 中的最后一 列的数值。 （ ） 在对表 中的

15、 次交叉结果进行统 值（ 即分割的阈值） ， 根据式（ ） 计算出图像分 计分析的基础上， 依次对每一位基因的取值 进行优劣判断， 最后得到优质基因的一个组 首先根据下式（ ） ， 即基因评价函数 ， 依 合（ 个体） 和较差基因的另一个组合。 次计算每个基因位分别来自不同染色体 、 和 。 （ ） 对应位基因的评价值 其中， 根据表 可知， ， （ 分别代表染色体 验的次数（ ） 。 表示正交试验方案中第 和 ） ， 表 示 基 因 位 （ ， ， ） ， 表 示 试 次试验的适应度值； 为控制系数 ， 如果第 次试验第 个基因位的值是来自第 个染色 体的第 个基因 （ 由表 可以很容易地判

16、 上式中 表示染色体 对第 个基因的 表示染色体 对第 个 断） ， 则 ， 否则 。 贡献评价值， 同理 基因的贡献评价值， 它同时也反映了第 个基 因位的不同取值对适应度值的贡献大小。如 果 ， 则表示染色体 比染色体 对第 个基因的贡献大， 所以在遗传选择操作时， 就 选 择 染 色 体 上 第 个 基 因 位 上 的 值 ， 作 例如： 对于第 个基因位， 由表 中的数 和 。 为智能选择的结果， 反之亦然。 值 和式（ ） ， 可 以 计 算 得 到 均匀变异 为了增大智能遗传算法在解空间的搜索 范围， 增强种群的多样性， 本文采用了较大的 变异率和均匀变异策略， 但种群中的最优个

17、体不参加变异， 其它的操作与传统的遗传算 法相同。 由于， 说明染色体中的第 个基因比染色体 时， 选择染色体 中的第 个基因值作为选 （ ） 计算出每个基因的优劣评价值后， 再 “优”因此在遗传选择操作 中的第 个基因 ， 择的结果。 基于智能遗传算法的图像分割步骤 在本文的实验中， 首先确定控制参数。 设置种群规模为 个， 变异率为 ， 交叉率 为 ， 最大迭代数为 和遗传收敛条件为 依次比较染色体对 、 对基因的贡献评价值 第期 测绘科技情报 总第 期 连续 代的个体最大适应度不变； （ ） 用本文提出 的 算 法 ， 对 图 像 （ 图 中 的（ ） 和（ ） ） 进行分割， 得到的最

18、优分割阈值 与穷尽法相同， 并且在分割三类时， 所需的分 割时间仅为穷尽法的 （ ） 。 表 本文算法与穷尽法的比较 初始化种群。依据预先设置的种群规 模大小， 随机地产生初始种群； 根据预先设置的交叉率， 从 智能交叉。 种群中选取待交叉的染色体对， 对每一个待 交叉染色体对进行智能交叉和优质基因的选 择， 得到它们的子代； 变异。根据预先设置的变异率对选中 的个体采用均匀变异； 判断是否满足收敛条件， 否则转入步 骤； 表 列出了上述两幅图像， 用本文方法 和穷尽法进行两类和三类分割的最优分割阈 值和所需时间（ 单位： 秒） 的比较。从表 中， 可以看到两种方法得到的最优分割阈值相 同，

19、但在三类分割时， 本文算法耗时仅为穷尽 法的 。 （ ） 智能遗 传 算 法 比 传 统 遗 传 算 法 可 以 更快地获得最优分割阈值， 并且分割的结果 （ 分割质量） 更加稳定。 为了说明智能遗传算法的有效性和稳定 性， 在设置相同遗传控制参数的条件下， 对图 根据得到的最优分割阈值， 对图像进 行分割。 实验结果与分析 为了验证上 述方法的正 确 性 和 有 效 性 ， 在本文的实验中， 选取两幅， 大小为 × 像素的航空影像， 进行分割实验（ 如图 ） 。与 此同时， 与传统遗传算法和穷尽法在同等条 件下进行相应的比较实验。在图 中， （ ） 和 （ ） 表示原始图像， 用本文提出的算法对它们 进行分割， 其中（ ） 为（ ） 的两类分割结果， 而 （ ） 为（ ） 的三类分割结果。 中