基于智能遺傳算法和Otsu法的多目標(biāo)圖像分割方法

1、第期 測繪科技情報 總第 期 基于智能遺傳算法和 法的 多目標(biāo)圖像分割方法 吳世英 鄭肇葆 虞欣 （ 武漢大學(xué)遙感信息工程學(xué)院， 武漢市珞喻路 號， ） 摘 要 為了克服傳統(tǒng)遺傳算法在優(yōu)化多目標(biāo)圖像分割參數(shù)時易陷入局部收斂和搜索效率低的缺陷， 本文提出一種基于智能遺傳算法和 法的多目標(biāo)圖像分割方法， 并將它應(yīng)用于航空影像的分割。 實驗結(jié)果表明， 本文提出的算法比傳統(tǒng)遺傳算法可以更加快速、 更穩(wěn)定地獲取圖像分割的最優(yōu)閾值。 關(guān)鍵詞 智能遺傳算法 ； 正交設(shè)計 ； 法； 圖像分割 隨著各種搜索算法的不斷涌現(xiàn) ， 它們常 被引入圖像分割領(lǐng)域 ， 用來搜索圖像分割的 最佳閾值。遺傳算法就是其中一種，

2、在優(yōu)化參 數(shù)較少， 遺傳編碼較短的情況下 ， 它的尋優(yōu)搜 索效率較高 ， 可以得到較好的分割閾值 ； 然而 對 于 分 割 閾 值 （ 即 參 數(shù) ） 較 多，遺 傳 編 碼 較 長 的情況下 ， 該算法則極易陷入局部收斂， 出現(xiàn) 過早收斂現(xiàn)象 ， 搜索的效率明顯下降， 從而不 能取得令人滿意的分割效果。為了克服傳統(tǒng) 遺傳算法的這一不足， 近年來， 在傳統(tǒng)遺傳算 法基礎(chǔ)上發(fā) 展起來一種 新 的 算 法 智 能 遺 傳算法 。該算法改變了傳統(tǒng)算法基于對染 色體本身選 優(yōu)和基因隨 機交叉的 遺傳模 式 ， 將正交設(shè)計的思想引入染色體內(nèi)的基因選優(yōu) 的操作中， 對交叉操作進行 “正交化” 然后根 ，

3、據(jù)基因評價函數(shù)， 計算得到染色體內(nèi)的每個 基因的優(yōu)劣評價值， 從而依據(jù)這個優(yōu)劣評價 值進行選擇操作。 這樣， 一方面既把原來對整 個染色體的選優(yōu)， 轉(zhuǎn)變到染色體內(nèi)單個基因 的選優(yōu)， 即將選優(yōu)具體到染色體內(nèi)的每一個 基因； 另一方面該算法又克服原有算法中隨 機的 “盲目 ” 的搜索， 它將 交叉建立在 優(yōu)質(zhì)基 因的強強聯(lián)合上， 這體現(xiàn)出遺傳的智能性， 從 而提高算法的全局搜索能力和穩(wěn)定性。鑒于 此， 本文提出了一種基于智能遺傳算法和 法 的 多 目 標(biāo) 圖 像 分 割 方 法 ， 并 將 它 應(yīng) 用于航空影像的分割。 實驗結(jié)果表明， 本文提 出的算法比 傳統(tǒng)遺傳算 法可以更加 快速 、 穩(wěn) 定地

4、獲得圖像分割的最優(yōu)閾值。 基于智能遺傳算法的圖像分割 算法的基本原理 本文結(jié)合對圖像進行兩類和三類目標(biāo)的 分割， 介紹智能遺傳算法的基本思想， 但此方 法亦可推廣到更多目標(biāo)的圖像分割。 種群個體及編碼 基于 法三類目標(biāo)的圖像分割， 就是 要確定基于最大類間方差準(zhǔn)則的最優(yōu)分割閾 值組， 而智能遺傳算法可用來在解空間中搜 索這種最優(yōu)分割閾值組。對于 級（ ） 的 每個閾值進行八位二進制編碼 （ 如圖 所 示） ， 把它作為種群個體， 也即染色體。 t t 灰度圖像， 為便于進行遺傳操作， 將閾值組中 適應(yīng)度函數(shù)的設(shè)計 在本文實驗中， 對 法中最大類間方 差這個準(zhǔn)則進行了改進， 采用如下的準(zhǔn)則（ 也

5、 Á Â 圖 一個個體的二進制編碼 第期 測繪科技情報 總第 期 稱為適應(yīng)度函數(shù)） 。 （ ） 式中， （，）表示第 類與第 類之間的灰度協(xié)方 差， （，）表示第 類的灰度方差， 最后得到的最 優(yōu)分割閾值組（，）應(yīng)使適應(yīng)度值達到最大。 驗的基因組合均勻分布在染色體對所有基因 組合的空間內(nèi)， 所以通過所得到的正交設(shè)計 基因組合的試驗也就具有代表性， 從而根據(jù) 基因評價函數(shù)計算得到的每個基因?qū)m應(yīng)度 的貢獻評價就具有可信度。有了每個基因的 優(yōu)劣評價值， 就可以從染色體對中選出每個 基因位上相對較好的優(yōu)質(zhì)基因， 從而實現(xiàn)基 于父體染色體內(nèi)的優(yōu)質(zhì)基因強強聯(lián)合的智能 交叉。 下面以三

6、類分割為例， 介紹智能交叉的過程 和基因選優(yōu)的基本原理。 假設(shè)遺傳優(yōu)化時的一對 待交叉染色體分別為 ： 和 智能交叉與基因選優(yōu) 為了從待交叉的一對染色體基因中選出 對適應(yīng)度貢獻較大的優(yōu)質(zhì)基因， 雖然可以把 染色體對 中基因的所 有組合都進 行試驗， 得 出每次基因組合的適應(yīng)度值， 然后統(tǒng)計每個 基因?qū)m應(yīng)度的貢獻大小， 能實現(xiàn)對染色體 對中每個基因的優(yōu)劣評價。 這雖然可行， 但計 算工作量勢必太大。為了減少基因組合的試 驗次數(shù)， 同時又使試驗不失代表性， 我們采用 正交設(shè)計的思想對染色體對的基因進行 “正 交化” 的組合。 這種正交設(shè)計的方法能使得試 ： 。 （ ） 根據(jù)待 交 叉 染 色 體

7、 對 、 具 有 的 基 因位數(shù)（ ） 和每個基因位上的可能取值個數(shù) （ 兩個） ， 生成進行正交設(shè)計試驗 所需的正交 表 （）（ 如表 所示） 。 表 正交表 第期 吳世英 鄭肇葆 虞欣 ：基于智能遺傳算法和 法的多目標(biāo)圖像分割方法 總第 期 每個染色體基因位有 個， 在智能交叉 操作中， 每個基因的取值只有兩種選擇， 要么 來自待交叉的染色體 ， 要么就來自待交叉 的染色體 。我們把每個基因作為一個因素 （ 用 表示， ） 對待 ， 每 個 因 素 有 兩 種 選 擇， 稱為水平數(shù)（ 用 表示， ） ， 根據(jù)以上原 則生成正交設(shè)計所需的正交表 （ ）， 表示 由于是兩個染色體交叉， 每個基

8、因位上 的取值有兩種情況， 在表中用 表示在該位 表示在該位置上取來自 對應(yīng)位的基因值。 置上取來自 對應(yīng)位的基因值， 與此相同， 以 表 中 的 第 三 行 為 例 ， 比 如 ： 在 第 個 基 因 位 上 的 值 為 ， 則 在這個 基因位上 取來自 中第 一位的值， 即 個基因位上取來自 中第 位的值， 即為 ， 基因位上的智能交叉的結(jié)果見表 。 表 智能交叉 試驗的次數(shù)（ 在表 中， ） 。從表 中， 可 以看到正交表的列數(shù)等于因素個數(shù) （ 基因的 位 數(shù)） ， 因素的水 平數(shù)與正 交表 的 水 平 數(shù) 一 致。此外， 正交表具有整齊可比性， 即表中任 一列中出現(xiàn) 、 的次數(shù)（ 或機

9、 會 ） 相 等 （ 都 是 為 ； 再看第 個 基 因 位 上 的 值 為 ， 則 在 這 次） ； 如果把表中任意兩列同一行的兩個 數(shù) 字 看 成 有 序 數(shù) 對 （ ， ） 、 ， ） 、 ， ） 和 （ （ （ ， ） ， 則每 種 數(shù) 對 出 現(xiàn) 的 次 數(shù) 也 相 同 （ 均 衡 搭配性） 。 所以這種正交設(shè)計試驗可以使得基 因的取值均勻地分布在所有可能的解空間 內(nèi)。在本文的實驗中， 次試驗就可以滿足 整齊可比性和均衡搭配性， 從而使得這 次 試驗 中基因的取 值均勻地分 布在解空間 中 。 而且， 基因 的組合次 數(shù)從原來 的 次 （ 窮 盡 法） 減 少為 次， 這大 大地減少

10、 了 計 算 工 作 量。 f f 如此， 便可以得到智能交叉的結(jié)果為 （ 表 中的最后一行） 。這 樣將得到的 次交叉結(jié)果， 依次組成另一個 示每次試驗的適應(yīng)度值（ 見表 ） 。 表， 稱之為正交試驗方案表， 表中最后一列表 ÃÂ Â Á Â ÃÁ Â 第期 1 S1 S12 !" Á Â Ã Ä Å Æ Ç È É Â Á Á Ã Ä Å Æ

11、Â Ç È É Â Ã Â Ä Å Æ Ç Ã È É Â Â Ä Á ÂÂ ÂÂ Â 測繪科技情報 總第 期 表 正交試驗方案表 Á S i1 1 S16 S i2 2 S16 Á Â Ã Ä Å Æ Ç È É Â Á Ã Ä

12、 Å Æ Â Ç Á È É Ã Â Ä Å Æ Ç Ã È É Â Ä Á Â Â Â 第期 吳世英 鄭肇葆 虞欣 ：基于智能遺傳算法和 法的多目標(biāo)圖像分割方法 總第 期 （ ） 依據(jù)得到的方案表， 將方案表的每一 （ 即得到表 中的倒數(shù)第二和第三行） ， 通過 比較同一列中兩個數(shù)值的大小， 確定它們的 優(yōu)劣。 所以， 從染色體對中選擇每一個對應(yīng)基 因位上對適應(yīng)度值貢獻較大的

13、基因 （ 見表 中的最 后一行） ， 作為 優(yōu)質(zhì)基因 ， 最后可以 得 到所有基因位上優(yōu)質(zhì)（ 最好） 基因的一個組合 （ 子 體） （ ） ， 和較差 基 因 的 另一組 合 （ ） 。 至 此 ， 就 實 現(xiàn)了對父體染色體對 、 基因的智能交叉和 優(yōu)質(zhì)基因的選擇過程。 由于正交設(shè)計試驗所用的正交表具有統(tǒng) 計意義 上的相互獨 立（ 即正交 的涵義） ， 因 此 在不必顧及基因相互干擾的情況下， 每個基 因?qū)m應(yīng)度的影響可以通過評價函數(shù)快速地 估計出來。 正是由于對基因優(yōu)劣的這種評價， 使得交叉成為一種有目的、有選擇的智能行 為， 進而使得整個遺傳搜索更加有效和快速。 （ ） 為了保證得到的后代

14、是最好的， 在完 成上述的基礎(chǔ)上， 將得到的兩個子體與原有 兩個父體一起進行比較， 再從中選取兩個最 好的個體（ 適應(yīng)度值高） 作為最終的結(jié)果。 由于智能交叉是基于染色體每個基因的 交叉和選優(yōu)， 這種選優(yōu)比傳統(tǒng)遺傳算法中的 基于整個染色體本身的選擇來得更加細(xì)致和 具體， 因此， 在智能遺傳算法中將傳統(tǒng)遺傳算 法中的選擇操作， 融入到智能交叉之中， 從而 提高了算法的效率。 從這個意義上說， 智能遺 傳算法可以看作一種壓縮型的遺傳算法。 行組合作為一次試驗的編碼， 按前、 后八位分 別作為一個單元， 并解碼為 至 的灰度 割后的適應(yīng)度值 ， 也即為表 中的最后一 列的數(shù)值。 （ ） 在對表 中的

15、 次交叉結(jié)果進行統(tǒng) 值（ 即分割的閾值） ， 根據(jù)式（ ） 計算出圖像分 計分析的基礎(chǔ)上， 依次對每一位基因的取值 進行優(yōu)劣判斷， 最后得到優(yōu)質(zhì)基因的一個組 首先根據(jù)下式（ ） ， 即基因評價函數(shù) ， 依 合（ 個體） 和較差基因的另一個組合。 次計算每個基因位分別來自不同染色體 、 和 。 （ ） 對應(yīng)位基因的評價值 其中， 根據(jù)表 可知， ， （ 分別代表染色體 驗的次數(shù)（ ） 。 表示正交試驗方案中第 和 ） ， 表 示 基 因 位 （ ， ， ） ， 表 示 試 次試驗的適應(yīng)度值； 為控制系數(shù) ， 如果第 次試驗第 個基因位的值是來自第 個染色 體的第 個基因 （ 由表 可以很容易地判

16、 上式中 表示染色體 對第 個基因的 表示染色體 對第 個 斷） ， 則 ， 否則 。 貢獻評價值， 同理 基因的貢獻評價值， 它同時也反映了第 個基 因位的不同取值對適應(yīng)度值的貢獻大小。如 果 ， 則表示染色體 比染色體 對第 個基因的貢獻大， 所以在遺傳選擇操作時， 就 選 擇 染 色 體 上 第 個 基 因 位 上 的 值 ， 作 例如： 對于第 個基因位， 由表 中的數(shù) 和 。 為智能選擇的結(jié)果， 反之亦然。 值 和式（ ） ， 可 以 計 算 得 到 均勻變異 為了增大智能遺傳算法在解空間的搜索 范圍， 增強種群的多樣性， 本文采用了較大的 變異率和均勻變異策略， 但種群中的最優(yōu)個

17、體不參加變異， 其它的操作與傳統(tǒng)的遺傳算 法相同。 由于， 說明染色體中的第 個基因比染色體 時， 選擇染色體 中的第 個基因值作為選 （ ） 計算出每個基因的優(yōu)劣評價值后， 再 “優(yōu)”因此在遺傳選擇操作 中的第 個基因 ， 擇的結(jié)果。 基于智能遺傳算法的圖像分割步驟 在本文的實驗中， 首先確定控制參數(shù)。 設(shè)置種群規(guī)模為 個， 變異率為 ， 交叉率 為 ， 最大迭代數(shù)為 和遺傳收斂條件為 依次比較染色體對 、 對基因的貢獻評價值 第期 測繪科技情報 總第 期 連續(xù) 代的個體最大適應(yīng)度不變； （ ） 用本文提出 的 算 法 ， 對 圖 像 （ 圖 中 的（ ） 和（ ） ） 進行分割， 得到的最

18、優(yōu)分割閾值 與窮盡法相同， 并且在分割三類時， 所需的分 割時間僅為窮盡法的 （ ） 。 表 本文算法與窮盡法的比較 初始化種群。依據(jù)預(yù)先設(shè)置的種群規(guī) 模大小， 隨機地產(chǎn)生初始種群； 根據(jù)預(yù)先設(shè)置的交叉率， 從 智能交叉。 種群中選取待交叉的染色體對， 對每一個待 交叉染色體對進行智能交叉和優(yōu)質(zhì)基因的選 擇， 得到它們的子代； 變異。根據(jù)預(yù)先設(shè)置的變異率對選中 的個體采用均勻變異； 判斷是否滿足收斂條件， 否則轉(zhuǎn)入步 驟； 表 列出了上述兩幅圖像， 用本文方法 和窮盡法進行兩類和三類分割的最優(yōu)分割閾 值和所需時間（ 單位： 秒） 的比較。從表 中， 可以看到兩種方法得到的最優(yōu)分割閾值相 同，

19、但在三類分割時， 本文算法耗時僅為窮盡 法的 。 （ ） 智能遺 傳 算 法 比 傳 統(tǒng) 遺 傳 算 法 可 以 更快地獲得最優(yōu)分割閾值， 并且分割的結(jié)果 （ 分割質(zhì)量） 更加穩(wěn)定。 為了說明智能遺傳算法的有效性和穩(wěn)定 性， 在設(shè)置相同遺傳控制參數(shù)的條件下， 對圖 根據(jù)得到的最優(yōu)分割閾值， 對圖像進 行分割。 實驗結(jié)果與分析 為了驗證上 述方法的正 確 性 和 有 效 性 ， 在本文的實驗中， 選取兩幅， 大小為 × 像素的航空影像， 進行分割實驗（ 如圖 ） 。與 此同時， 與傳統(tǒng)遺傳算法和窮盡法在同等條 件下進行相應(yīng)的比較實驗。在圖 中， （ ） 和 （ ） 表示原始圖像， 用本文提出的算法對它們 進行分割， 其中（ ） 為（ ） 的兩類分割結(jié)果， 而 （ ） 為（ ） 的三類分割結(jié)果。 中