一種快速自動多目標圖像分割算法

高華 鄔春學

摘 要：針對進化多目標圖像分割算法運行時間長且依賴人工挑選最優(yōu)解的不足，提出一種快速自動多目標圖像分割算法。首先使用自適應Mean-shift算法對圖像進行預處理，將粗分割結(jié)果進行二次分割以提高運行速度;其次選擇相互排斥的指標作為多目標的目標函數(shù)，并采用RM-MEDA框架對超像素顏色與紋理特征分別進行優(yōu)化，同時對它們使用不同權值作為目標函數(shù)優(yōu)化;最后由模糊模型從眾多Pareto折中解集中自動選擇滿足實際分割要求的PS解。引入Mean-shift進行預分割，相對于標準的RM-MEDA，其運行速度提高近18%，由模糊模型推薦的Pareto解中，97%的情況符合分割要求。

關鍵詞：圖像分割;聚類分析;進化算法;Mean-shift;多目標

DOI：10. 11907/rjdk. 202166????????????????????????????????????????????????????????????????? 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP317.4?? 文獻標識碼：A??????????????? 文章編號：1672-7800（2020）011-0212-05

A Rapid Automatic Multi-objective Image Segmentation Algorithm

GAO Hua1，WU Chun-xue2

（1. Office of Educational Administration， University of Shanghai for Science and Technology;

2. School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology，

Shanghai 200093， China）

Abstract： The multi-objective image segmentation algorithm is confronted with some challenges such as long running speed and manual selection of the optimal solution. In this paper， a rapid automatic multi-objective segmentation algorithm （RAMOSA） is proposed to solve this problem. Firstly， the adaptive mean-shift algorithm is used to pre-segment the image， and the coarse segmentation results are re-segmented to improve the segmentation efficiency. Secondly， mutually exclusive indexes are selected as the multi-objective function， and RM-MEDA framework is used to optimize the color and texture features of super pixels respectively. Finally， the fuzzy model automatically selects the specific optimal solution that conforms to the current situation from many Pareto results. Multiple image materials are selected for image segmentation experiment， the experimental results show that RAMOSA algorithm has higher segmentation efficiency compared with general multi-target image segmentation. Mean-shift is introduced for pre-segmentation. Compared with the standard RM-MEDA， the operating speed is increased by 18%， and the accuracy of the results selected by the fuzzy model reached 70%.

Key Words：image segmentation; cluster analysis; evolutionary algorithms; mean-shift; multi-objective

0 引言

圖像分割是圖像模式識別和場景分析中重要的預處理環(huán)節(jié)。隨著模式識別、計算機視覺、虛擬現(xiàn)實與仿真、衛(wèi)星遙感圖像等技術的發(fā)展，圖像分割技術日益成熟，眾多學者從數(shù)據(jù)處理方法、圖像特征提取等方面，設計了多種代表性圖像分割和處理算法。由于圖像分割具有數(shù)據(jù)量大、圖像信息維度多等特點，分割方法具有強烈的針對性，目前沒有一種適用于所有圖像的通用算法[1-3]。

相對于一般的單目標圖像分割算法，多目標圖像算法將多個特征空間作為算法多個目標函數(shù)，并且多個圖像特征目標函數(shù)之間互斥，同時優(yōu)化多個目標函數(shù)，通過對互斥多目標函數(shù)進行求解，可得到非唯一的最優(yōu)解，稱為Pareto最優(yōu)解集。所以Pareto解集是多個互斥的特征空間最優(yōu)分割結(jié)果集合，最終只需在眾多Pareto集合中挑選滿足實際分割要求的結(jié)果。進化多目標算法（Multi-objective Evolutionary Algorithms）優(yōu)勢獨特，備受關注，目前研究比較成熟的算法主要有：NSGA-II[4]、SPEA2[5]、PEAS[6]、MOEA/D、IBEA[7]、HypE[8]等。根據(jù)不同的可提取進化的目標類型，將多目標圖像分割算法分為3類：①將兩種或者多種分割算法作為兩個或多個目標;②將圖像多個特征空間作為多個目標; ③將不同的距離度量函數(shù)作為多個目標。本文主要針對第二類算法展開研究。

Mean-Shift算法核心內(nèi)容是最優(yōu)化理論中的梯度下降法（亦稱牛頓法，最速下降法等）[9]，即沿著梯度下降方法尋找目標函數(shù)極值。在圖像分割應用中，算法的解是最大相似度值的候選目標位置。Zhang 等[10]提出的 RM-MEDA 框架充分使用連續(xù)多目標優(yōu)化的特性，即對m個目標函數(shù)的連續(xù)多目標優(yōu)化問題。由 Karush-Kuhn-Tucker 條件可知，Pareto最優(yōu)解集合PS（Pareto Set）在決策空間上的分布呈現(xiàn)分段連續(xù)的（m-1）維流形[11]。RM-MEDA 算法本質(zhì)是通過建立多個線性（m-1）-維流形分布的概率模型，分段逼近整個非線性的 PS 流形，再分別對所有線性模型隨機采樣并生成子代種群。

基于文獻[12]，本文針對Mean-shift算法運算量大、需要設定帶寬等缺點，引入改進的Mean-shift算法，對圖像進行降像素及自動帶寬調(diào)節(jié)。通常以手工方法選取最佳Pareto解，本文引入模糊模型從眾多Pareto折中解中找到符合當前情況的具體最佳解，對進化算法相應檢驗指標進行改進，使改進后的指標更加符合本文研究的圖像分割實驗。

1 快速自動多目標圖像分割

1.1 算法框架

RAMOSA算法流程主要包括4個模塊：第1模塊是自適應Mean-shift預處理，后續(xù)再分割基于預分割的過度分割結(jié)果;第2模塊是基于過度分割區(qū)域獲取圖像紋理及顏色兩個特征;第3模塊是使用多目標算法的求解，包括編碼、進化算子、適應度函數(shù)設置和產(chǎn)生Pareto集;第4模塊是自動選取較好的Pareto解，綜合Pareto 解集與具體最優(yōu)方案的求解方法。本文RAMOSA算法流程如圖1 所示。

1.2 Mean-shift算法改進

本文基于MS過度分割的結(jié)果再進行分割。k（x）是核函數(shù)K（x）的剖面函數(shù)，且 k（x）是一個單調(diào)遞減的凸函數(shù)，核函數(shù)K（x）、G（x）分別由K（x）=k（||x||2）、G（x）=g（||x||2）定義且g（x）=-k′（x），則基于核函數(shù)的Mean-shift算法具有收斂性。

本文核函數(shù)K（x）的剖面函數(shù)k（x）為：

k（x）=exp-x2 （1）

在一副n*n大小的彩色圖像中，共有n*n個點x？i（i=1，2，…，n*n），使用RGB色彩空間表示像素點顏色值，可以形成1個五維空間——顏色聯(lián)合特征空間R5（R，G，B，X，Y），圖像中的每個像素點使用1個五維特征向量表示，即由顏色三維和位置二維表示。由于色彩信息與空間信息相互獨立，K（x）可由公式（2）的兩個k（x）的乘積表示。

Khshr（x）=Chs2hrpk（xshs2）k（xrhr2） （2）

其中，C是歸一化常數(shù)，xs表示像素空間位置信息，xr表示像素三維色彩信息，hs為空間窗口區(qū)域半徑，hr為顏色空間窗口半徑。

Mean-shift濾波算法在處理較大圖像時，面臨計算量大且處理速度過慢等問題[13]。在實際運用中，算法運行效率是衡量算法的主要標準，為了提高Mean-shift算法運行效率、減少運行時間，對標準的Mean-shift濾波算法進行如下改進：

（1）從算法運行效率方面考慮，使用高斯金字塔分割算法降低圖像分辨率，算法處理后得到低像素的預處理圖像，使用Mean-shift算法對高斯金字塔分割算法處理的結(jié)果再進行濾波處理，最后對濾波后的圖像恢復到初始分辨率[14]。

（2）使用Mean-shift對圖像進行多次濾波處理，一般直接將x設置為收斂點對應的值，直接計算的數(shù)據(jù)運算量較大，濾波后的圖像顏色不均勻，濾波后圖像效果很難達到分割要求。因此，本文對賦值方法進行改進：在算法實現(xiàn)過程中采用歸類思想對每個像素點設置1個標志位記錄該像素點類別，當算法迭代達到結(jié)束條件時候，將所有梯度方向上沒有設置標記值的像素點設置為同一類別號Ti（i=1，2，3，…，n），如果當前梯度方向已有被標記過的像素點，則將當前梯度方向所有未被標記的像素點類別號設置為已標記像素點的標記值。改進后Mean-shift濾波算法主要步驟為：①讀入原始圖像，降低圖像的像素，保存降低分辨率后的圖像信息;②遍歷降分辨率圖像，根據(jù)式（1）計算mh？（x）;③mh？（x）的值賦給x 即x=mh？（x）;④如果‖mh？（x）-x‖<ε，算法得到概率密度最大值的點即為算法收斂點，算法運算結(jié)束。若‖-x‖>ε，則重復執(zhí)行步驟②和③，直到滿足迭代停止條件，則將該梯度方向未標記的像素點記為同一類;⑤使用同一顏色表示同一標記的像素點;⑥將處理結(jié)束的圖像還原到初始分辨率。

1.3 檢驗指標改進

選擇合適的聚類算法目標函數(shù)是本文算法成功的關鍵，本文選擇的兩個目標函數(shù)具有矩陣關系，因此使用RM-MEDA算法同時優(yōu)化兩個目標函數(shù)[15-16]。

1.3.1 聚類算法設計

本文算法采用聚類的內(nèi)部緊湊函數(shù)Com第一個目標函數(shù)與類的中心點值進行計算，第一個目標函數(shù)類聚類的內(nèi)部緊湊函數(shù)如公式（3）所示。

Com（k）=i=1kxj∈ci||xj-xvi|| （3）

K 為類的數(shù)量，需算法提前設定。類的數(shù)量k 和Com（k）函數(shù)之間是單調(diào)遞減關系，k 數(shù)值增大使Com（k）結(jié)果變小。聚類算法為了得到最佳的聚類數(shù)目，同時需要將類與類之間的差異性考慮在目標函數(shù)之中。本文使用類的中心點值進行計算，類與類之間差異性函數(shù)如公式（4）所示。

Sep（k）=mini≠j？？？||xvi-xvj||？ （4）

本文根據(jù)在聚類內(nèi)部緊湊函數(shù)及類與類差異性之間尋找平衡點的原則[17]，設計基于距離矩陣的有效性指標DXB，如公式（5）所示。聚類內(nèi)部緊湊函數(shù)與類與類之間差的異性函數(shù)的比值為：

DXB=Com（k）/Sep（k） （5）

DXB 有以下優(yōu)點：①Com（k）、Sep（k）與k是單調(diào)遞減的關系，當k值變大，Sep（k）與Com（k）的函數(shù)值變小，一個成功的聚類應該是當Sep（k）的函數(shù)可以取到較大值，Com（k）函數(shù)可以取到較小值，最佳聚類數(shù)指其折中值;②DXB是參照距離矩陣定義的聚類有效性檢驗指標，使用類代表點作為類中心點，同時引入不同的相似性指標到目標函數(shù)中 ;③RAMOSA通過使用實數(shù)值編解碼的方式得到算法類代表點，一般優(yōu)化算法需要遍歷類內(nèi)所有點，本文算法可縮短搜索類代表點的時間。

1.3.2 多目標組合

本文使用Com 與DXB兩個目標函數(shù)，采用RM-MEDA多目標框架同時進行優(yōu)化。具體描述為：

F1=Com（k）F2=DXB（k） （3）

1.4 進化算子

Zhang 等[11]提出的 RM-MEDA 算法框架充分利用了連續(xù)多目標優(yōu)化的特點，處理對于m個目標函數(shù)的連續(xù)多目標問題。由 Karush-Kuhn-Tucker 條件可知，Pareto最優(yōu)解集合PS（Pareto Set）在決策空間上的分布呈分段連續(xù)的（m-1）維流形[18-19]。RM-MEDA 算法本質(zhì)是通過建立多個線性（m-1）維流形分布的概率模型，分段逼近整個非線性的 PS 流形，再分別對所有線性模型隨機采樣并生成子代種群。

算法主要流程為：

算法名稱：RM-MEDA算法

步驟1：初始化參數(shù)。t為算法運行的代數(shù)，pop（t）={x1，x2，…，xn}為t代大小為N的種群，F(xiàn)x1，F(xiàn)x2，…，F(xiàn)xn，令t=0，初始化pop（0），pop（0）的個體隨機得到，計算器函數(shù)適應值。

步驟2：判斷停止條件。達到停止條件，算法計算終止同時返回pop（t）的PS目標函數(shù)向量和種群。

步驟3：模型建立。建立相應的分布概率模型計算pop（t）。

步驟4：繁殖子代。生成新的種群從而得到新的解集Q，使用已經(jīng)建立的模型，同時得到Q目標函數(shù)值。

步驟5：選擇N個來自從Q∪pop（t）中的個體作為下一代pop（t+1）…，…{f（x1），…，f（xi）}。

1.5 基于模糊模型識別的最優(yōu)解確定

多目標圖像分割在算法獲得Pareto 最優(yōu)解集后，通常需經(jīng)人工在眾多PS解集中挑選出分割效果好的結(jié)果[20-21]。本文采用模糊模型識別算法自動推薦最優(yōu)分割結(jié)果，具體實現(xiàn)步驟為：

（1）求出各非劣解的隸屬度向量。各粒子目標隸屬度公式為：

Ai，k=fk，max-fi，kfk，max-fk，min （7）

其中，Ai，k與f i，k分別表示第i 個粒子的第k 個目標隸屬度值與實際結(jié)果;fk，max與fk，min分別為第k 個目標函數(shù)的最大值與最小值。

（2）先根據(jù)實際情況對各目標的重要程度進行排序，再結(jié)合模糊語氣算子，將最重要的目標與其它目標進行二元對比，得到非歸一化的隸屬度指標目標向量[α1，α2 ，α3]。

（3）求各粒子隸屬度向量 [Ai1， Ai2， Ai2]（i=1，2，…，n）與目標權重向量 [α1，α2 ，α3]的貼近度 σ（A i，α），其公式為：

δ（Ai，α）=2（Ai，α）（Ai，Ai）+（α，α）（i=1，2...n）? （8）

其中，

（Ai，α）=Ai，1α1+ Ai，2α2+Ai，3α3 （9）

（4）尋找與 [α1，α2 ，α3]最為貼近的隸屬度向量，其對應分割結(jié)果即為最優(yōu)分割結(jié)果。

2 實驗分析

本文算法實驗參數(shù)設置為：種群個數(shù)為50，最大迭代代數(shù)是100。Mean-shift帶寬為（7，7，50），圖像顏色特征與紋理特征權重初始值分別為0.9、0.1。

本文選取的測試圖像使用標準的RM_MEDA算法與本文RAMOSA算法按照加權的顏色和紋理圖像特征進行分割的結(jié)果如圖2所示。第一列是標準RM_MEDA算法分割結(jié)果，第二列是本文RAMOSA算法分割結(jié)果。

選用標準的RM_MEDA算法與本文算法對圖2（a）-（f）進行圖像分割實驗，試驗時間如表1所示，將表1數(shù)據(jù)以折線圖的方式呈現(xiàn)，如圖3所示。由圖3可以看出：①兩條線趨勢較為一致，說明本文算法與標準RM_MEDA算法在多目標圖像分割上有效;②標準RM_MEDA算法的折線在本文算法的上面，說明本文算法在分割效率上優(yōu)于標本RM_MEDA算法，運行速度提高近18%;③第3張照片算法運行時間比其它圖像時間更長，說明圖像分割時間長短與圖像像素大小具有正相關關系。

本文RAMOSA對圖2（a）-（f）圖像進行分割的Pareto集合結(jié)果如圖4所示，RAMOSA算法并沒有收斂成單一解，而是產(chǎn)生了一組Pareto折中解，但是很多Pareto折中解存在重復，為了方便展示效果，去除重復的解和一些明顯錯誤的解，只突出分割結(jié)果比較好的折中解。由實驗結(jié)果產(chǎn)生大量Pareto解集，說明本文選定的兩個Com和DXB目標函數(shù)是相互排斥的，本文選取的目標函數(shù)是合適的。

圖4中矩形點為各圖像較好的Pareto解，通過觀察可發(fā)現(xiàn)當兩個互斥的目標函數(shù)值較為接近時得到的Pareto解通常符合實際分割要求。實心點為模糊模型推薦的第一個最優(yōu)解，橢圓點是為模糊模型推薦的第二個解。實驗結(jié)果表明， 模糊模型推薦的較好的Pareto解中，97%的情況符合分割要求。

3 結(jié)語

本文基于RM_MEDA框架引入自適應Mean_shift與模糊模型算法， 提出了一種自動快速多目標圖像分割算法RAMOSA。由于進化多目標圖像分割算法存在運行速度緩慢及依賴人工挑選最優(yōu)解等缺點，首先引入自適應Mean-Shift算法，對圖像進行預處理，提取預分割紋理及顏色特征，通過設置不同的權重生成新特征;其次選擇相互排斥的類內(nèi)緊湊度Com與DXB作為目標函數(shù)，RM-MEDA算法對兩個目標函數(shù)同時進行優(yōu)化;最后模糊模型能夠在Pareto折中解集中推薦符合實際分割要求的解。由于引入了Mean-shift進行預分割，運行速度相對于標準RM-MEDA提高近18%，97%由模糊模型推薦的Pareto解符合分割要求。

但同時對于低像素圖像，本文算法效率沒有標準的RM-MEDA算法處理速度快，模糊模型自動挑選的結(jié)果不唯一（有2個）。如何減少模糊模型推薦結(jié)果數(shù)量、提高低像素圖像處理效率是下一步研究內(nèi)容。

參考文獻：

[1] 何志明.? 圖像分割綜述[J].? 山東工業(yè)技術，2016（22）：226.

[2] BALI A，SINGH S N. A review on the strategies and techniques of image segmentation[C]. Fifth International Conference on Advanced Computing & Communication Technologies， 2015：113-120.

[3] 劉叢，陳倩倩，陳應霞. 多距離聚類有效性指標研究[J]. 小型微型計算機系統(tǒng)，2019，40（10）：2209-2214.

[4] LONG J， ZHENG Z， GAO X， et al. A hybrid multi-objective evolutionary algorithm based on NSGA-II for practical scheduling with release times in steel plants[J].? Journal of the Operational Research Society， 2016， 67（9）：1184–1199.

[5] YU F， LI Y，WEI B， et al. Interactive differential evolution for user-oriented image retrieval system[J].? Soft Computing，2016，20（2）：1-15.

[6] EFSA. Reasoned opinion on the modification of the existing maximum residue levels （MRLs） for boscalid in beans and peas with pods[J].? EFSA Journal， 2016， 13（3）：1-19.

[7] BIOLOGíA I D. Quararibea yunckeri sessiliflora Standl. Miranda ex W.S. Alverson - IBUNAM： MEXU： TUXsn01463[D].? Mexico City：Unibio Colecciones Biológicas， 2016.

[8] KAMENOVA K，CAULFIELD T. Stem cell hype： media portrayal of therapy translation.[J].? Science Translational Medicine， 2015， 7（278）：278-281.

[9] 李振宇，胡涵. 基于組合排序的約束多目標優(yōu)化算法[J]. 計算機技術與發(fā)展，2019，29（11）：32-36.

[10] ZHANG Q， ZHOU A， JIN Y. RM-MEDA： a regularity model-based multiobjective estimation of distribution algorithm[J].? IEEE Transactions on Evolutionary Computation， 2008， 12（1）：41-63.

[11] ZHANG H， ZHOU A， SONG S， et al. A Self-organizing multiobjective evolutionary algorithm[J].? IEEE Transactions on Evolutionary Computation， 2016， 20（5）：792？- 806.

[12] 劉叢， 鄔春學.? 進化多目標距離矩陣聚類研究[J].? 小型微型計算機系統(tǒng)， 2016， 37（6）：1298-1302.

[13] 付麗梅.? 使用彩色直方圖均衡法改進的Mean Shift行人跟蹤算法[J].? 軟件工程， 2019， 22（2）：17-19.

[14] 鴻源， 胡改玲， 姜凌奇，等.? Mean Shift算法在目標跟蹤領域的應用研究[J].? 計算機科學與應用， 2020， 10（7）：1391-1399.

[15] 杜冠軍， 佟國香.? 一種新的混合演化多目標優(yōu)化算法[J].? 軟件， 2019， 40（2）：12-16.

[16] 嚴加展，陳華，李陽. 改進的模糊C-均值聚類有效性指標[J].? 計算機工程與應用，2020， 56（9）：156-161.

[17] 劉叢， 萬秀華，彭敦陸. 基于多目標進化算法的多距離聚類研究[J]. 計算機應用研究， 2019， 36（1）：94-98.

[18] 韋占江，梁宇. 快速HAC聚類算法的改進及應用于無監(jiān)督語音分割[J]. 計算機科學與應用， 2020， 10（8）：1464-1470.

[19] 王慧君. 基于規(guī)則模型學習的多目標分布估計算法研究[D].? 西安：西安理工大學，2019.

[20] 宋昊澤， 吳小俊.? 圖像多尺度密集網(wǎng)絡去模糊模型[J].? 激光與光電子學進展， 2019， 56（21）：1-10.

[21] 孫濤， 李東升.? 基于非凸的全變分和低秩混合正則化的圖像去模糊模型和算法[J].? 計算機學報， 2020， 43（4）：643-652.

（責任編輯：江 艷）