陳相廷，張偌雅（河南大學(xué)計算機與信息工程學(xué)院，開封　475000）

SLIC超像素分割的并行化實現(xiàn)

陳相廷，張偌雅
（河南大學(xué)計算機與信息工程學(xué)院，開封475000）

數(shù)字圖像處理往往信息量大，算法復(fù)雜度高。SLIC超像素分割算法在圖像預(yù)處理階段，通過相鄰像素的關(guān)聯(lián)特征，將單一像素點聚類為超像素塊，有效過濾高相似度重復(fù)信息。根據(jù)聚類過程相對獨立的特性，并行化實現(xiàn)SLIC超像素分割算法，有效降低算法時間復(fù)雜度。

數(shù)字圖像處理；超像素；并行計算

0　引言

圖像較文字、語言等方式可更加生動地展現(xiàn)所描述對象的空間分布、形態(tài)結(jié)構(gòu)、紋理色澤等特征［1］。數(shù)字圖像因其易存儲、易處理、便于傳輸?shù)榷喾N優(yōu)勢，現(xiàn)已廣泛應(yīng)用于生物醫(yī)療、航空航天、工業(yè)生產(chǎn)、軍事公安、環(huán)境檢測等多個領(lǐng)域。與此同時，為滿足多種需求，數(shù)字圖像處理技術(shù)得到飛速發(fā)展。隨著處理數(shù)據(jù)量的日益增長，如何快速高效地得出結(jié)果已成為當(dāng)代數(shù)字圖像處理技術(shù)的研究重點。

圖像預(yù)處理可最大限度簡化圖像數(shù)據(jù)，增強后期處理所需敏感區(qū)域的特征信息。以單一像素為單位的處理方式，迭代次數(shù)多，數(shù)據(jù)冗余大，重復(fù)信息多，這會大大增加整個處理過程的時間消耗，降低了處理效率。利用冗余信息的關(guān)聯(lián)性將同類單一像素合并為超像素是當(dāng)前研究的熱點，合并后的超像素塊有效突出了關(guān)鍵信息，成為處理算法快速實現(xiàn)的前提［2］。同時，基于每個聚類核心的迭代聚類過程相對獨立，關(guān)聯(lián)性較低，能較好地適用并行計算，從而可并行化地實現(xiàn)超像素分割過程，極大提高處理效率。

1　SLIC超像素分割模型

2003年由Ren等人最早研究并提出了超像素的概念，超像素是將信息敏感度較低的單一像素通過局部紋理形態(tài)特征的關(guān)聯(lián)，將高相似特征值的像素點聚類為像素塊即超像素［3］。紋理邊界作為視覺識別的重要線索，可直接體現(xiàn)圖像中梯度變化較大的感興趣區(qū)域。超像素分割模型弱化梯度差異較小部分，增強圖像邊界部分，可快速定位目標(biāo)處理區(qū)域。

SLIC超像素分割算法是一種基于梯度下降的分割算法，該算法最早由Achanta等人于2010年提出［4］。該算法通過歸類聚合的方式首先將RGB色域空間量映射至LAB色域空間，之后根據(jù)空間相位、色澤差異、亮度明暗等相似特征，把原圖單一像素聚合為以離散分布在原圖中的聚類核心為中心的超像素［5］。該方法較基于圖論的方法可更好地控制分割所得超像素塊的邊緣形狀，平滑度及數(shù)量。SLIC算法通過原圖像素對應(yīng)XY軸坐標(biāo)值及LAB色域空間對應(yīng)特征分量所組成的5階特征矩陣，標(biāo)定聚類核心附近處的聚合閾值［6］。主要步驟如下：

（1）聚類核心初始化。在原圖中離散地生成聚類核心，將原圖中所有K個像素點聚合成形態(tài)規(guī)則，邊界平滑且分布集中的Q個超像素塊，即每個超像素聚合量為K/Q，理想狀態(tài)下聚類核心空間相鄰距離近似為H=

（2）聚類核心校準(zhǔn)。通常情況下，聚類核心分布在梯度變化較大處時聚合過程會產(chǎn)生較大誤差。為避免該情況出現(xiàn)，通常采用的方法是設(shè)定窗口，取聚類核心n×n（n取值通常為3）鄰域內(nèi)梯度最小處坐標(biāo)代替原核心坐標(biāo)。同時為避免后續(xù)步驟重復(fù)該操作，將分配一個單獨標(biāo)號給新的聚類核心。

（3）聚類閾值計算。任取原圖中的兩個像素點e和f，利用像素點對應(yīng)LAB色域空間映射值及對應(yīng)XY軸坐標(biāo)值計算相似度，公式如下：

其中dlab表示像素點e，f的色差值；dxy為像素點e，f的空間相位距離；DH表示像素聚類閾值，H是鄰域聚類核心的距離；m表示調(diào)節(jié)因子，用來平衡色差值和空間相位距離在聚類閾值計算中所占比重，變化區(qū)間為［1，20］，通常為10。計算所得DH值與像素關(guān)聯(lián)度正相關(guān)，即隨著DH值增大，像素關(guān)聯(lián)度也隨之增高。

（4）算法優(yōu)化。為提高聚合過程的效率，SLIC算法搜索以聚類核心為基準(zhǔn)，2H×2H的鄰域范圍，如圖1所示。

圖1　

將聚類核心鄰域范圍內(nèi)相似度大于聚類閾值的像素合并，同時將聚類核心的標(biāo)號分配給超像素內(nèi)的每個像素。重復(fù)聚合過程直至所有超像素收斂，超像素分割算法完成。

2　并行實現(xiàn)

在實際應(yīng)用中，SLIC超像素分割算法往往用于處理多領(lǐng)域海量圖像，處理數(shù)據(jù)量大，運行時間較長。隨著高性能多核計算機的快速發(fā)展，并行計算已廣泛應(yīng)用于大規(guī)模工程與科研運算，并行化實現(xiàn)算法已成為趨勢。MPI（Message Passing Interface，MPI）是并行開發(fā)中的常用模型，該模型基于消息傳遞機制，適用于低關(guān)聯(lián)度執(zhí)行過程的并行實現(xiàn)［7］。

SLIC超像素分割算法在初始化分布聚類核心后，聚核校準(zhǔn)與迭代聚類的過程關(guān)聯(lián)度較小，適用于并行計算，可通過分配獨立的內(nèi)存堆棧并行完成。最后將所生成單一超像素塊整合。并行實現(xiàn)效果如圖2所示。

圖2　

3　實驗結(jié)果及分析

本文對算法的并行實現(xiàn)是基于Windows7（64位）平臺，硬件配置為Intel Core i7處理器，內(nèi)存為8GB。MPI的實現(xiàn)采用的是MPICH2。算法的執(zhí)行環(huán)境為Microsoft Visual Studio 2012。通常并行計算的衡量指標(biāo)為加速比和效率，定義如下：

其中S表示加速比，Ts表示單一進(jìn)程執(zhí)行時間，Tp表示并行計算所用時間，E表示效率，P為并行進(jìn)程數(shù)。將圖2中a，c兩圖設(shè)為實驗樣本一號和二號，程序運行結(jié)果如表1所示。

通過表1可以得出，并行化實現(xiàn)SLIC超像素分割算法可大幅降低算法運行所耗時間。隨著處理數(shù)據(jù)量的提升，算法并行效率提升也越發(fā)顯著。但隨著進(jìn)程數(shù)的增加，并行效率明顯降低，原因是并行計算中用于進(jìn)程間通信和數(shù)據(jù)交互的系統(tǒng)開銷會隨著進(jìn)程數(shù)增大而相應(yīng)增加。所以在工程實踐中應(yīng)根據(jù)硬件配置來設(shè)定進(jìn)程數(shù)，以達(dá)到最佳效率。

表1　SLIC算法并行運算效果

4　結(jié)語

SLIC超像素分割算法根據(jù)圖像相位、紋理、色澤等特征將高相似度像素聚合為邊界平滑，分布均勻的超像素塊，可有效在預(yù)處理階段突出圖像邊緣輪廓信息，降低后續(xù)處理數(shù)據(jù)量。同時，并行化實現(xiàn)SLIC算法可大大降低算法時耗，提高運行效率。未來研究將致力于繼續(xù)降低算法復(fù)雜度，提高并行效率，為大規(guī)模工程與科研運算提供支持。

［1］劉麗，匡綱要.圖像紋理特征提取方法綜述［J］.中國圖象圖形學(xué)報，2009，14（04）：622-635.

［2］陳相廷，張偌雅，渠星星，等.SLIC超像素分割在醫(yī)學(xué)圖像處理中的應(yīng)用［J］.現(xiàn)代計算機：普及版，2015（35）：52-56.

［3］Malik J.Learning a Classification Model for Segmentation［C］.null.IEEE Computer Society，2003：10-17 vol.1.

［4］Achanta R，Shaji A，Smith K，et al.SLIC Superpixels［J］.Epfl，2010.

［5］Bergh M V D，Boix X，Roig G，et al.SEEDS：Superpixels Extracted via Energy-Driven Sampling［J］.International Journal of Computer Vision，2013，111（3）：298-314.

［6］王春瑤，陳俊周，李煒.超像素分割算法研究綜述［J］.計算機應(yīng)用研究，2014，01：6-11.

［7］呂捷，張?zhí)煨?，張必銀.MPI并行計算在圖像處理方面的應(yīng)用［J］.紅外與激光工程，2004，33（05）：496-499.

Digital Image Processing；Superpixels；Parallel Computing

Parallel Implementation of SLIC Superpixels Segmentation

CHEN Xiang-ting，ZHANG Ruo-ya
（College of Computer and Information Engineering，Henan University，Kaifeng 475000）

Digital image processing always has a large amount of information and high algorithm complexity.SLIC superpixels segmentation algorithm uses adjacent pixels correlation feature，clustering single pixel for superpixels.It can filter the high similarity duplicate information effectively in image pre-processing stage.According to the relatively independent characteristics of the clustering process，realizes the SLIC superpixels segmentation algorithm in parallel，which reduces the time complexity of the algorithm effectively.

1007-1423（2016）29-0075-03

10.3969/j.issn.1007-1423.2016.29.018

陳相廷（1991-），男，河南安陽人，碩士研究生，研究方向為數(shù)字圖像處理張偌雅（1993-），女，河南信陽人，碩士研究生，研究方向為數(shù)字圖像處理

2016-08-03

2016-10-10