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

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

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

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

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

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

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

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

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

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

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

11、Â Ç È É Â Ã Â Ä Å Æ Ç Ã È É Â Â Ä Á ÂÂ ÂÂ Â 測(cè)繪科技情報(bào) 總第 期 表 正交試驗(yàn)方案表 Á S i1 1 S16 S i2 2 S16 Á Â Ã Ä Å Æ Ç È É Â Á Ã Ä

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

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

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

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

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

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

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

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