第1期 尹雨山，等：回溯搜索优化算法辅助的多圆值图像分割 .69· 分割方法[0-1]、基于图论的分割方法[34]、基于能 量泛函的分割方法[s16)以及基于机器学习的分割 A2= 分p/e: (4) 方法[-201等。 且满足入=01入1+02入，和101+02=10 基于阈值的分割方法是各类分割算法中简单且 类间方差可表示为 广泛采用的方法，其基本思想是用一个或者多个阈值 d(q)=w1(入1-入)2+e2(入2-A)2 (5) 将待分割的图像的灰度级分为多个部分，灰度值在同 根据类间最大化准则，当方差取得最大值时，便得到 一类中的像素属于同一个目标。因此，阈值的选取 最佳阈值q。 非常关键，并决定分割的结果。常见的计算阈值的方 假设图像P存在a个阈值(91，q2,…,q.),式 法主要有最大类间方差法(Osu算法)[)、最大嫡 (5)容易扩展多阈值类间方差，可表示为 法[4)以及最小误差法)等。上述计算阈值方法基本 d(41,…,9a）=01(入1-入)2+…+w。(A。-A)2 是在满足一定准则下通过解析式求得阈值，例如Otsu (6) 算法以目标和背景的类间方差最大或类内方差最小 根据类间最大化准则，可通过计算式(7)获得 为准则选取阈值。然而，通过解析式求解阈值的计算 最佳阈值： 量和计算复杂度会随着阈值的增加而呈指数增长。 （q1,92,…,9n)=argmax(d(q1,92,…,9a) 因此，一些学者将基于准则函数的阈值求解问题视为 以准则函数为目标函数的优化问题，于是出现了一些 1.2 最大熵法(Kapur法) 基于遗传算法2]、粒子群优化算法[)以及差分算 20世纪80年代以来，Shannon信息嫡的概念被 法[2]等的多阈值方法。得益于经典进化算法能有效 应用于图像阈值化处理中，其思想是利用图像的灰 求解多阈值问题，一些新颖的仿生算法用于该类问 度分布密度函数定义图像的信息嫡，并根据优化准 题，并呈现出较好的分割效果[2427列。 则求得阈值。文献[4]通过使后验的上限最大化准 回溯搜索优化算法(backtracking search optimiza- 则确定阈值，而文献[5]假定目标和背景服从2个 tion algorithm,BSA)是一种新兴的仿生算法，其具有 不同的概率分布，使得信息嫡最大化求得最佳阈值。 简单的结构，并能有效且快速求解各类函数优化问 假设存在m级灰度的图像P,阈值g将图像的 题2】。然而，关于BSA算法的应用研究报道较少，特 灰度值范围[0,1，…，m-1]分为背景与目标2部分。 别是在图像处理及应用领域。因此，借鉴于仿生算法 又设p,表示灰度值为i出现的概率，则目标和背景 求解多阈值问题的有效性，本文将BSA算法应用于 表示为式(1)和式(2)，而它们的信息熵则可表示为 图像分割，提出基于BSA算法的多阈值图像分割。 提出的方法将Osu算法和最大嫡法的准则函数视为 H1=- n() Pi (8) =0101101 目标函数，并采用BSA算法分别获取多阈值，实现图 像分割。实验说明提出的方法具有更好的性能。 H2=- 哈 (9) 1 阈值法 Kapur方法[是在图像P的总信息嫡最大时， 获得最佳阈值，即 1.1最大类间方差法(0tsu法) (10) 最大类间方差法给予判别分析最小二乘法的原 q argmax(H+H) 同样，式(10)很容易扩展为多阈值最大嫡，可 理，其根据图像的灰度特性，将图像分为不同类别」 表示为 各类之间方差要求最大。假设存在m级灰度的图 像P,阈值g将图像的灰度值范围[0,1，…，m-1]分 (q1,92,…,9a)=argmax(H1+H2+…+Hn) 为背景与目标2部分。又设P,表示灰度值为i出现 (11) 的概率，则目标部分和背景的概率分别表示为 式中：a表示阈值数目。 101= (1) 2 回溯搜索优化算法 P i=0 m-1 BSA算法是一种新兴的随机优化搜索技术，其 02= (2) i=g+1 结构简单，并且能够有效求解各类优化问题。另外， 设入、入1、入2分别表示图像、目标和背景的灰 BSA算法也是基于种群的搜索技术，并且使用一个 度值均值，则可表示为 外部文档维护其历史种群信息以引导种群进化。 当BSA算法用于求解优化问题时，首先在解搜 入，= (3) =0 索空间[x..m](=1,2,…,D)内，通过均匀采分割方法咱员园鄄员圆暂 尧基于图论的分割方法咱员猿鄄员源暂 尧基于能 量泛函的分割方法咱员缘鄄员远暂 以及基于机器学习的分割 方法咱员苑鄄圆园暂等遥 基于阈值的分割方法是各类分割算法中简单且 广泛采用的方法袁其基本思想是用一个或者多个阈值 将待分割的图像的灰度级分为多个部分袁灰度值在同 一类中的像素属于同一个目标咱圆暂 遥 因此袁阈值的选取 非常关键袁并决定分割的结果遥 常见的计算阈值的方 法主要有最大类间方差法渊 韵贼泽怎 算法冤咱猿暂 尧最大熵 法咱源鄄缘暂以及最小误差法咱苑暂等遥 上述计算阈值方法基本 是在满足一定准则下通过解析式求得阈值袁例如 韵贼泽怎 算法以目标和背景的类间方差最大或类内方差最小 为准则选取阈值遥 然而袁通过解析式求解阈值的计算 量和计算复杂度会随着阈值的增加而呈指数增长遥 因此袁一些学者将基于准则函数的阈值求解问题视为 以准则函数为目标函数的优化问题袁于是出现了一些 基于遗传算法咱圆员暂 尧粒子群优化算法咱圆圆暂 以及差分算 法咱圆猿暂等的多阈值方法遥 得益于经典进化算法能有效 求解多阈值问题袁一些新颖的仿生算法用于该类问 题袁并呈现出较好的分割效果咱圆源鄄圆苑暂 遥 回溯搜索优化算法渊遭葬糟噪贼则葬糟噪蚤灶早 泽藻葬则糟澡 燥责贼蚤皂蚤扎葬鄄 贼蚤燥灶 葬造早燥则蚤贼澡皂袁 月杂粤冤是一种新兴的仿生算法袁其具有 简单的结构袁并能有效且快速求解各类函数优化问 题咱圆愿暂 遥 然而袁关于 月杂粤 算法的应用研究报道较少袁特 别是在图像处理及应用领域遥 因此袁借鉴于仿生算法 求解多阈值问题的有效性袁本文将 月杂粤 算法应用于 图像分割袁提出基于 月杂粤 算法的多阈值图像分割遥 提出的方法将 韵贼泽怎 算法和最大熵法的准则函数视为 目标函数袁并采用 月杂粤 算法分别获取多阈值袁实现图 像分割遥 实验说明提出的方法具有更好的性能遥 员摇 阈值法 员援员摇 最大类间方差法渊韵贼泽怎 法冤 摇 摇 最大类间方差法给予判别分析最小二乘法的原 理袁其根据图像的灰度特性袁将图像分为不同类别袁 各类之间方差要求最大遥 假设存在 皂 级灰度的图 像 孕袁阈值 择 将图像的灰度值范围咱园袁员袁噎袁皂原员暂分 为背景与目标 圆 部分遥 又设 责蚤表示灰度值为 蚤 出现 的概率袁则目标部分和背景的概率分别表示为 憎员 越 移 择 蚤 越 园 责蚤 渊员冤 憎圆 越 移 皂原员 蚤 越 择垣员 责蚤 渊圆冤 摇 摇 设 姿 尧 姿 员 尧 姿 圆分别表示图像尧目标和背景的灰 度值均值袁则可表示为 姿员 越 移 择 蚤 越 园 蚤责蚤 辕 憎员 渊猿冤 姿圆 越 移 皂原员 蚤 越 择垣员 蚤责蚤 辕 憎圆 渊源冤 且满足 姿 越憎员姿 员垣憎圆姿 圆和 憎员垣憎圆 越 员遥 类间方差可表示为 凿渊择冤 越 憎员 渊姿员 原 姿冤圆 垣 憎圆 渊姿圆 原 姿冤圆 渊缘冤 根据类间最大化准则袁当方差取得最大值时袁便得到 最佳阈值 择遥 假设图像 孕 存在 葬 个阈值渊 择员 袁 择圆 袁噎袁 择葬 冤 袁式 渊缘冤容易扩展多阈值类间方差袁可表示为 凿渊择员 袁噎袁择葬 冤 越 憎员 渊姿员 原 姿冤圆 垣 噎 垣 憎葬 渊姿葬 原 姿冤圆 渊远冤 摇 摇 根据类间最大化准则袁可通过计算式渊苑冤 获得 最佳阈值院 渊择员 袁择圆 袁噎袁择葬 冤 越 葬则早皂葬曾渊凿渊择员 袁择圆 袁噎袁择葬 冤 冤 员援圆 摇 最大熵法渊运葬责怎则 法冤 圆园 世纪 愿园 年代以来袁杂澡葬灶灶燥灶 信息熵的概念被 应用于图像阈值化处理中袁其思想是利用图像的灰 度分布密度函数定义图像的信息熵袁并根据优化准 则求得阈值遥 文献咱源暂通过使后验的上限最大化准 则确定阈值袁而文献咱缘暂假定目标和背景服从 圆 个 不同的概率分布袁使得信息熵最大化求得最佳阈值遥 假设存在 皂 级灰度的图像 孕袁阈值 择 将图像的 灰度值范围咱园袁员袁噎袁皂原员暂分为背景与目标 圆 部分遥 又设 责蚤表示灰度值为 蚤 出现的概率袁则目标和背景 表示为式渊员冤和式渊圆冤袁而它们的信息熵则可表示为 匀员 越 原 移 择 蚤 越 园 责蚤 憎员 造灶渊 责蚤 憎员 冤 渊愿冤 匀圆 越 原 移 皂原员 蚤 越 择垣员 责蚤 憎圆 造灶渊 责蚤 憎圆 冤 渊怨冤 摇 摇 运葬责怎则 方法咱缘暂 是在图像 孕 的总信息熵最大时袁 获得最佳阈值袁即 择 越 葬则早皂葬曾渊匀员 垣 匀圆 冤 渊员园冤 摇 摇 同样袁式渊员园冤很容易扩展为多阈值最大熵袁可 表示为 渊择员 袁择圆 袁噎袁择葬 冤 越 葬则早皂葬曾渊匀员 垣 匀圆 垣 噎 垣 匀葬 冤 渊员员冤 式中院葬 表示阈值数目遥 圆摇 回溯搜索优化算法 月杂粤 算法是一种新兴的随机优化搜索技术袁其 结构简单袁并且能够有效求解各类优化问题遥 另外袁 月杂粤 算法也是基于种群的搜索技术袁并且使用一个 外部文档维护其历史种群信息以引导种群进化遥 当 月杂粤 算法用于求解优化问题时袁首先在解搜 索空间咱曾躁袁 皂蚤灶 袁曾躁袁 皂葬曾暂 渊躁 越 员袁圆袁噎袁阅冤内袁通过均匀采 第 员 期摇摇摇摇摇摇摇摇摇摇摇摇摇摇 尹雨山袁等院回溯搜索优化算法辅助的多阈值图像分割 窑远怨窑