一個(gè)基于超像素的圖像分割算法

劉乘風(fēng)+徐剛

摘要：圖像分割技術(shù)是計(jì)算機(jī)視覺領(lǐng)域的基礎(chǔ)工作，目前的圖像分割技術(shù)大多以像素為單位進(jìn)行。隨著圖像分辨率的提升，圖像分割的成本越來越高，于是尋找降低圖像分割成本的需求越來越迫切?；诔袼氐膱D像分割算法就是這樣一種方法。超像素其實(shí)就是將具有相似紋理、顏色、亮度等特征的相鄰像素進(jìn)行合并后的圖像塊。采用超像素的圖像分割算法后，可以消除像素間的冗余，大大降低后續(xù)圖像處理任務(wù)的成本，加快圖像識(shí)別的速度。

關(guān)鍵詞：計(jì)算機(jī)視覺； 圖像分割； 超像素； K-means聚類； 歸一化分割

中圖分類號(hào)：TP317 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）25-0165-02

Abstract：Image segmenting is the basic technology in computer vision， and most image segmenting technology is Based on pixels in nowadays. With the promoting of image resolution， the cost of image segmenting is higher and higher， so the requirement of lower image segmenting method is more and more urgent. Image segmenting Based on superpixel is such method. In fact superpixel is an image block consisting of neighbor pixels， which has the similar texture，color，and brightness. By taking superpixel method， it will eliminate redundancy of pixels，and decrease the cost of following image processing， and accelerate image recognizing.

Key words：computer vision； image segmenting； superpixel； K-means clustering； normalized cut

1 概述

圖像特征反映了圖像的基本特性，一般可分為全局特征、局部特征和空間關(guān)系特征。

全局特征主要有顏色特征和紋理特征。顏色特征和紋理特征描述了圖像所對(duì)應(yīng)的對(duì)象的表面性質(zhì)。

局部特征主要是輪廓特征和區(qū)域特征。輪廓特征主要描述了物體的外邊界，區(qū)域特征則描述整個(gè)形狀區(qū)域。

空間關(guān)系特征是指圖像中分割出來的多個(gè)目標(biāo)之間的相互的空間位置或相對(duì)方向關(guān)系?？臻g關(guān)系又分為兩類：相對(duì)空間位置信息和絕對(duì)空間位置信息。相對(duì)空間位置關(guān)系強(qiáng)調(diào)的是目標(biāo)之間的相對(duì)情況，如上下左右等，絕對(duì)空間位置信息關(guān)系強(qiáng)調(diào)的是目標(biāo)之間的距離大小以及方位，如鄰接、重疊、和包容等。

圖像分割技術(shù)是一種根據(jù)圖像特征進(jìn)行圖像劃分的技術(shù)。圖像分割技術(shù)要求將圖像分割成互不重疊的區(qū)域，并且每個(gè)區(qū)域具有各自特征，區(qū)域間的特征值差別明顯。圖像分割應(yīng)滿足以下條件：1）分割后所得到的各個(gè)區(qū)域的總和應(yīng)能夠覆蓋整個(gè)圖像，即各個(gè)區(qū)域的并集等于圖像全集；2）各區(qū)域之間不能有重疊，即各個(gè)區(qū)域的交集是空集；3）同一區(qū)域的像素特征值相似或相近，例如具有相近的顏色、紋理值；4）同一個(gè)對(duì)象可以分割在一個(gè)區(qū)域內(nèi)，也可以分割到多個(gè)區(qū)域中[1]。

圖像分割技術(shù)發(fā)展到今天，已經(jīng)有出現(xiàn)了許多方法，歸納起來主要有三類：1）邊緣檢測(cè)方法；2）區(qū)域提取方法；3）閾值分割方法[2]。

2 基于超像素的圖像分割算法

目前對(duì)圖像的分割處理大都以像素為單位進(jìn)行。核心思想就是利用二維矩陣來表示一張圖像，直接在二維矩陣的基礎(chǔ)上進(jìn)行分割處理。這種做法并未考慮像素之間的空間組織關(guān)系，這使得效率過低，于是Ren[3]提出了超像素（Superpixel）這一概念。超像素其實(shí)就是將具有相似紋理、顏色、亮度等特征的相鄰像素進(jìn)行合并后的圖像塊。利用超像素進(jìn)行圖像分割，可以消除冗余，降低后續(xù)圖像處理任務(wù)的成本。超像素分割算法是一種基于區(qū)域提取的圖像分割方法。

2.1 K-means聚類算法及其應(yīng)用

在使用超像素技術(shù)時(shí)，將用到其核心算法K-means算法[4]。

K-means聚類算法的主要步驟如下：首先隨機(jī)給定K個(gè)聚類中心，按照最鄰近原則把待分類樣本點(diǎn)分到各個(gè)簇中；然后按平均法重新計(jì)算各個(gè)簇的質(zhì)心，從而確定新的聚類中心；一直迭代下去，直到聚類中心移動(dòng)的距離小于某個(gè)給定的值， 或聚類次數(shù)達(dá)到要求為止。

由K-means算法得到的K個(gè)點(diǎn)集能保證聚類的性能最佳。我們把這種方法用于聚類圖像中的像素點(diǎn)，這是超像素算法中重要的一步。

2.2 超像素特征提取技術(shù)研究

超像素技術(shù)基于一個(gè)測(cè)度謂詞——超像素，其利用圖像的基于圖論的表示法來判定兩區(qū)域的邊界。我們將原始圖像預(yù)分割為多個(gè)區(qū)域一致性和邊緣描述性較好的區(qū)域，這些區(qū)域在本文中被稱為超像素[5，6]。

基于超像素技術(shù)，本文使用一種叫做Ncut（Normalized cut）的技術(shù)進(jìn)行圖像分割[7，8]。Ncut技術(shù)又稱歸一化分割，它遵循歸一化準(zhǔn)則‘Ncut，使得分割出的超像素類間距離盡可能大，并且類內(nèi)距離盡可能小。

第二步：求解特征系統(tǒng)[（D-W）y=λDy]方程。當(dāng)我們把y的取值范圍放寬到實(shí)數(shù)時(shí)，則求最小化Ncut，就相當(dāng)于是求解特征系統(tǒng)[（D-W）y=λDy]方程。在Ncut方法中，我們采用的是其特征方程的第二個(gè)最小特征值所對(duì)應(yīng)的特征向量作為該問題的解。endprint

第三步：利用K-means算法對(duì)上一步驟中的特征向量y進(jìn)行聚類。得到超像素集SP。

第四步：對(duì)SP集合中的區(qū)域塊邊界進(jìn)行畫線，保留畫線。

3 實(shí)現(xiàn)方案

本文用Noramlized Cut和K-means方法提取超像素集合，并對(duì)超像素的邊界進(jìn)行分割。我們?cè)贗ntel酷睿i5，主頻3.4GHz、內(nèi)存4GB的計(jì)算機(jī)上，利用在Matlab2014a實(shí)現(xiàn)了圖像分割。我們分別對(duì)風(fēng)景、人物圖片做了分割實(shí)驗(yàn)，取得了不錯(cuò)的效果。圖1為使用超像素算法處理圖片的一個(gè)實(shí)驗(yàn)結(jié)果。

圖1（a）為原圖I，圖1（b）為N_SP=20時(shí)超像素塊的邊界I_SP，圖1（c）為N_SP2=200時(shí)的邊界I_SP2 ?；趯?duì)運(yùn)行效率以及特征信息的高敏感性的考慮，我們采用N_SP=20作為實(shí)驗(yàn)參數(shù)。

參考文獻(xiàn)：

[1] 章毓晉. 圖像分割[M]. 北京： 科學(xué)出版社， 2001.

[2] 周強(qiáng).圖像分割算法研究[J].世界科技研究與發(fā)展， 2012，32（3）：157- 158.

[3] X. Ren ， J. Malik. Learning a classification model for segmentation[C]. In Proc. 9th Int. Conf. Computer Vision， 2003 （1）：10-17.

[4] 劉雄. 基于K-means的改進(jìn)聚類融合算法的研究與應(yīng)用[D].中南大學(xué). 2011.

[5] O. Veksler， Y. Boykov， P. Mehrani. Superpixels and Supervoxels in an Energy Optimization Framework[C]. In European Conference on Computer Vision， 2010：211-224.

[6] 趙淵，彭濟(jì)根，高義. 基于SLIC超像素分割的圖分割算法[J].工程數(shù)學(xué)學(xué)報(bào)， 2016，33（5）：441-449.

[7] 姜長龍. 基于Graph Cuts圖像分割的Mean Shift目標(biāo)跟蹤算法研究[D].西安電子科技大學(xué)，2010.

[8] 席秋波. 基于Ncut的圖像分割算法研究[D].電子科技大學(xué)，2010.endprint