超像素SLIC算法源碼閱讀

• 超像素SLIC算法源碼閱讀
• • SLIC簡介
  • 源碼閱讀
  • 實驗結(jié)果
  • 其他超像素算法對比

超像素SLIC算法源碼閱讀

SLIC簡介

SLIC的全稱Simple Linear Iterative Clustering，即簡單線性迭代聚類，論文和代碼鏈接如下：
論文傳送門：SLIC Superpixels Comparedto State-of-the-Art Superpixel Methods
代碼傳送門：superpixels-revisited，這個Github項目是Superpixels: An Evaluation of the State-of-the-Art的作者的開源項目，對比了幾乎所有有開源代碼的超像素算法，本文的代碼就是來自于此。

超像素的目的一般是為了降低后續(xù)圖像處理的復(fù)雜度，SLIC定義的好的超像素算法要求是：(1)超像素的邊界能夠粘附圖像邊界;（2）計算速度應(yīng)該快：（3）用于分割時應(yīng)該能夠提高分割質(zhì)量

SLIC的算法流程如下：
（1）將圖像分割成$S\times S$個格子，每個格子中心生成一個聚類中心
（2）將聚類中心移動到格子中心的八鄰域像素中梯度最低的像素位置（避免將超像素定義在邊緣上，減少噪聲接種的機會）
（3）合并每一個像素和最近的聚類中心（這一步和kmeans不同的是，這里是遍歷每一個聚類中心周圍$2S$區(qū)域的像素點，而kmeans的方法是直接求距離某個像素最近的聚類中心，這種方法可以減少計算量同時使得算法復(fù)雜度與像素數(shù)量無關(guān)（這里我其實不太理解））。這里距離$D$的定義是lab顏色空間和xy坐標(biāo)空間五維空間的加權(quán)距離$$d_e=\sqrt{(l_j?l_i{)}^2+(a_j?a_i{)}^2+(b_j?b_i{)}^2}$$$$d_s=\sqrt{(x_j?x_i{)}^2+(y_j?y_i{)}^2}$$$$D=\sqrt{d_e^2+N{d}_s^2}$$
（4）遍歷所有聚類中心后，重新跟新每個聚類中心的位置（這里和kmeans算法一致了），然后 進行迭代
（5）迭代完成后進行連通域加強并且去除面積過小的超像素

源碼閱讀

函數(shù)DoSuperpixelSegmentation_ForGivenSuperpixelSize是主程序，其步驟大概就是將RGB圖像轉(zhuǎn)到Lab色域——計算Lab色域的梯度——初始化網(wǎng)格中心——將聚類中心初始化到網(wǎng)格中心的八鄰域像素——聚類迭代——對聯(lián)通域加強。

void SLIC::DoSuperpixelSegmentation_ForGivenSuperpixelSize(const unsigned int* ubuff,//原始圖像const int width,//寬度const int height,//高度int*& klabels,//輸出的label，其實記錄的是邊界的位int& numlabels,//輸出的label的數(shù)量const int& superpixelsize,//一個label的像素大小const double& compactness,//緊密度的參數(shù)const bool& perturbseeds,//注意這是個bool變量const int iterations)//迭代次數(shù) {//------------------------------------------------const int STEP = sqrt(double(superpixelsize))+0.5;//步長大小，其實就是畫網(wǎng)格時，網(wǎng)格的間距//------------------------------------------------vector<double> kseedsl(0);vector<double> kseedsa(0);vector<double> kseedsb(0);vector<double> kseedsx(0);vector<double> kseedsy(0);//--------------------------------------------------m_width = width;m_height = height;int sz = m_width*m_height;//整個像素大小//klabels.resize( sz, -1 );//--------------------------------------------------klabels = new int[sz];//一個數(shù)組for( int s = 0; s < sz; s++ ) klabels[s] = -1;//--------------------------------------------------if(1)//LAB, the default option{DoRGBtoLABConversion(ubuff, m_lvec, m_avec, m_bvec);//將顏色空間從RGB轉(zhuǎn)到Lab}else//RGB{m_lvec = new double[sz]; m_avec = new double[sz]; m_bvec = new double[sz];for( int i = 0; i < sz; i++ ){m_lvec[i] = ubuff[i] >> 16 & 0xff;m_avec[i] = ubuff[i] >> 8 & 0xff;m_bvec[i] = ubuff[i] & 0xff;}}//--------------------------------------------------vector<double> edgemag(0);if(perturbseeds) DetectLabEdges(m_lvec, m_avec, m_bvec, m_width, m_height, edgemag);//求顏色的邊界，perturb是干擾的意思，這個是用來求八領(lǐng)域里面最小梯度的梯度的梯度值就是從這里來的//kseedsl這些值放進去之前都是零，運行完這個函數(shù)之后就是有值的了GetLABXYSeeds_ForGivenStepSize(kseedsl, kseedsa, kseedsb, kseedsx, kseedsy, STEP, perturbseeds, edgemag);//這個應(yīng)該是初始化的過程,建立網(wǎng)格，并且在網(wǎng)格中心的八領(lǐng)域里面尋找seedPerformSuperpixelSLIC(kseedsl, kseedsa, kseedsb, kseedsx, kseedsy, klabels, STEP, edgemag, compactness, iterations);//基于Kmeans算法進行迭代numlabels = kseedsl.size();int* nlabels = new int[sz];EnforceLabelConnectivity(klabels, m_width, m_height, nlabels, numlabels, double(sz)/double(STEP*STEP));{for(int i = 0; i < sz; i++ ) klabels[i] = nlabels[i];}if(nlabels) delete [] nlabels; }

函數(shù)GetLABXYSeeds_ForGivenStepSize主要是完成了網(wǎng)格中心的初始化

void SLIC::GetLABXYSeeds_ForGivenStepSize(vector<double>& kseedsl,vector<double>& kseedsa,vector<double>& kseedsb,vector<double>& kseedsx,vector<double>& kseedsy,const int& STEP,//STEP這個值指的是網(wǎng)格間的間距是多少，即一步可以跨多長const bool& perturbseeds,const vector<double>& edgemag) {const bool hexgrid = false;int numseeds(0);int n(0);//int xstrips = m_width/STEP;//int ystrips = m_height/STEP;int xstrips = (0.5+double(m_width)/double(STEP));//這里指的是有多少個步長，+0.5是為了進行四舍五入int ystrips = (0.5+double(m_height)/double(STEP));int xerr = m_width - STEP*xstrips;if(xerr < 0){xstrips--;xerr = m_width - STEP*xstrips;}//劃分網(wǎng)格的時候有可能會多一步，需要保證網(wǎng)格劃分在圖像內(nèi)int yerr = m_height - STEP*ystrips;if(yerr < 0){ystrips--;yerr = m_height- STEP*ystrips;}double xerrperstrip = double(xerr)/double(xstrips);//每一步所包含的誤差是多少double yerrperstrip = double(yerr)/double(ystrips);int xoff = STEP/2;//這個應(yīng)是用來尋找中心點的位置int yoff = STEP/2;//-------------------------numseeds = xstrips*ystrips;//一共會有多少個種子點//-------------------------kseedsl.resize(numseeds);kseedsa.resize(numseeds);kseedsb.resize(numseeds);kseedsx.resize(numseeds);kseedsy.resize(numseeds);for( int y = 0; y < ystrips; y++ ){int ye = y*yerrperstrip;for( int x = 0; x < xstrips; x++ ){int xe = x*xerrperstrip;//到這個格子累計x的誤差int seedx = (x*STEP+xoff+xe);//確定準(zhǔn)確的每個種子點的x的位置if(hexgrid){ seedx = x*STEP+(xoff<<(y&0x1))+xe; seedx = min(m_width-1,seedx); }//for hex grid samplingint seedy = (y*STEP+yoff+ye);int i = seedy*m_width + seedx;//轉(zhuǎn)化成在整個坐標(biāo)中的位置kseedsl[n] = m_lvec[i];kseedsa[n] = m_avec[i];kseedsb[n] = m_bvec[i];kseedsx[n] = seedx;kseedsy[n] = seedy;n++;}}if(perturbseeds){PerturbSeeds(kseedsl, kseedsa, kseedsb, kseedsx, kseedsy, edgemag);} }
函數(shù)PerturbSeeds是將聚類中心調(diào)整到8鄰域像素中梯度最小的像素上， void SLIC::PerturbSeeds(vector<double>& kseedsl,vector<double>& kseedsa,vector<double>& kseedsb,vector<double>& kseedsx,vector<double>& kseedsy,const vector<double>& edges) {const int dx8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};//像素的八領(lǐng)域const int dy8[8] = { 0, -1, -1, -1, 0, 1, 1, 1};int numseeds = kseedsl.size();//點的數(shù)量for( int n = 0; n < numseeds; n++ ){int ox = kseedsx[n];//original xint oy = kseedsy[n];//original yint oind = oy*m_width + ox;//轉(zhuǎn)化成數(shù)組里面的下標(biāo)int storeind = oind;for( int i = 0; i < 8; i++ ){int nx = ox+dx8[i];//new xint ny = oy+dy8[i];//new yif( nx >= 0 && nx < m_width && ny >= 0 && ny < m_height){int nind = ny*m_width + nx;if( edges[nind] < edges[storeind]){storeind = nind;//記錄最小梯度的位置}}}if(storeind != oind){kseedsx[n] = storeind%m_width;kseedsy[n] = storeind/m_width;kseedsl[n] = m_lvec[storeind];kseedsa[n] = m_avec[storeind];kseedsb[n] = m_bvec[storeind];}} }

函數(shù)PerformSuperpixelSLIC是完成整個迭代過程，其實就是一個kmeans算法的實現(xiàn)過程

void SLIC::PerformSuperpixelSLIC(vector<double>& kseedsl,vector<double>& kseedsa,vector<double>& kseedsb,vector<double>& kseedsx,vector<double>& kseedsy,int*& klabels,const int& STEP,const vector<double>& edgemag,const double& M,const int iterations) {int sz = m_width*m_height;const int numk = kseedsl.size();//----------------int offset = STEP;//網(wǎng)絡(luò)線之間的間距//if(STEP < 8) offset = STEP*1.5;//to prevent a crash due to a very small step size//----------------vector<double> clustersize(numk, 0);vector<double> inv(numk, 0);//to store 1/clustersize[k] valuesvector<double> sigmal(numk, 0);vector<double> sigmaa(numk, 0);vector<double> sigmab(numk, 0);vector<double> sigmax(numk, 0);vector<double> sigmay(numk, 0);vector<double> distvec(sz, DBL_MAX);//存儲距離最近的seed的距離double invwt = 1.0/((STEP/M)*(STEP/M));//這個invwet其實是權(quán)衡顏色距離和空間距離的一個權(quán)重，因此參數(shù)M也就是一個權(quán)重int x1, y1, x2, y2;double l, a, b;double dist;double distxy;for( int itr = 0; itr < iterations; itr++ )//限制迭代次數(shù){distvec.assign(sz, DBL_MAX);for( int n = 0; n < numk; n++ )//遍歷所有的種子點{y1 = max(0.0, kseedsy[n]-offset);y2 = min((double)m_height, kseedsy[n]+offset);x1 = max(0.0, kseedsx[n]-offset);x2 = min((double)m_width, kseedsx[n]+offset);//限制鄰域的范圍（seedx + offset， seedy - offsetfor( int y = y1; y < y2; y++ )//在鄰域內(nèi)搜索{for( int x = x1; x < x2; x++ ){int i = y*m_width + x;l = m_lvec[i];a = m_avec[i];b = m_bvec[i];dist = (l - kseedsl[n])*(l - kseedsl[n]) +(a - kseedsa[n])*(a - kseedsa[n]) +(b - kseedsb[n])*(b - kseedsb[n]);//顏色空間距離distxy = (x - kseedsx[n])*(x - kseedsx[n]) +(y - kseedsy[n])*(y - kseedsy[n]);//xy空間距離//------------------------------------------------------------------------dist += distxy*invwt;//dist = sqrt(dist) + sqrt(distxy*invwt);//this is more exact//------------------------------------------------------------------------if( dist < distvec[i] ){distvec[i] = dist;//賦值距離klabels[i] = n;//賦值label}}}}//-----------------------------------------------------------------// Recalculate the centroid and store in the seed values//-----------------------------------------------------------------//instead of reassigning memory on each iteration, just reset.sigmal.assign(numk, 0);sigmaa.assign(numk, 0);sigmab.assign(numk, 0);sigmax.assign(numk, 0);sigmay.assign(numk, 0);clustersize.assign(numk, 0);//------------------------------------//edgesum.assign(numk, 0);//------------------------------------{int ind(0);for( int r = 0; r < m_height; r++ ){for( int c = 0; c < m_width; c++ ){sigmal[klabels[ind]] += m_lvec[ind];//klabel[ind]是這個點屬于那個seed，sigmal[klabel[ind]]是這個seed的l顏色域的累加和，m_lvec[ind]就是這個點l的顏色域的值sigmaa[klabels[ind]] += m_avec[ind];sigmab[klabels[ind]] += m_bvec[ind];sigmax[klabels[ind]] += c;sigmay[klabels[ind]] += r;//------------------------------------//edgesum[klabels[ind]] += edgemag[ind];//------------------------------------clustersize[klabels[ind]] += 1.0;//統(tǒng)計這個seed一共有多少個像素點ind++;}}}{for( int k = 0; k < numk; k++ ){if( clustersize[k] <= 0 ) clustersize[k] = 1;inv[k] = 1.0/clustersize[k];//computing inverse now to multiply, than divide later}}{for( int k = 0; k < numk; k++ ){kseedsl[k] = sigmal[k]*inv[k];//重新分配這個seed的顏色域，然后再循環(huán)到重新開始計算距離什么的kseedsa[k] = sigmaa[k]*inv[k];kseedsb[k] = sigmab[k]*inv[k];kseedsx[k] = sigmax[k]*inv[k];kseedsy[k] = sigmay[k]*inv[k];//------------------------------------//edgesum[k] *= inv[k];//------------------------------------}}} }

函數(shù)EnforceLabelConnectivity實現(xiàn)了連通區(qū)域的重新賦值，之前所有的label值是聚類中心的值，通過這個函數(shù)將其統(tǒng)一超像素的編號，從0開始一直到最后一個超像素，然后會統(tǒng)計每個超像素所占的像素，如果太小的話會進行合并

void SLIC::EnforceLabelConnectivity(const int* labels,//input labels that need to be corrected to remove stray labelsconst int width,const int height,int*& nlabels,//new labelsint& numlabels,//the number of labels changes in the end if segments are removedconst int& K) //the number of superpixels desired by the user { // const int dx8[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // const int dy8[8] = { 0, -1, -1, -1, 0, 1, 1, 1};const int dx4[4] = {-1, 0, 1, 0};const int dy4[4] = { 0, -1, 0, 1};//四鄰域const int sz = width*height;const int SUPSZ = sz/K;//每個小網(wǎng)格像素的大小//nlabels.resize(sz, -1);for( int i = 0; i < sz; i++ ) nlabels[i] = -1;//nlabels為經(jīng)過這個函數(shù)處理輸出的數(shù)組int label(0);int* xvec = new int[sz];int* yvec = new int[sz];//這連個數(shù)組都有整個圖片那么大int oindex(0);int adjlabel(0);//adjacent labelfor( int j = 0; j < height; j++ )//遍歷每一個像素{for( int k = 0; k < width; k++ ){if( 0 > nlabels[oindex] )//nlabels小于零應(yīng)該就是還沒有處理過的像素{nlabels[oindex] = label;//oindex為0時候，label也為0//--------------------// Start a new segment//--------------------xvec[0] = k;//這里存儲的是像素的坐標(biāo)yvec[0] = j;//-------------------------------------------------------// Quickly find an adjacent label for use later if needed//-------------------------------------------------------{for( int n = 0; n < 4; n++ ){int x = xvec[0] + dx4[n];int y = yvec[0] + dy4[n];if( (x >= 0 && x < width) && (y >= 0 && y < height) )//在圖像范圍內(nèi){int nindex = y*width + x;//這個是四鄰域像素if(nlabels[nindex] >= 0) adjlabel = nlabels[nindex];//查看鄰域里面是否有大于等于0的nlabels，如果有的話就是adjlabel}}}int count(1);for( int c = 0; c < count; c++ ){for( int n = 0; n < 4; n++ )//又是一個四鄰域{int x = xvec[c] + dx4[n];int y = yvec[c] + dy4[n];if( (x >= 0 && x < width) && (y >= 0 && y < height) ){int nindex = y*width + x;if( 0 > nlabels[nindex] && labels[oindex] == labels[nindex] ) //這個鄰域像素沒有處理過 && 這個鄰域像素的label和中心像素的label一致{xvec[count] = x;yvec[count] = y;//把坐標(biāo)存進去，就是記錄下有哪些坐標(biāo)nlabels[nindex] = label;//向領(lǐng)域像素擴展count++;//因為這個count會一直增加，因此鄰域也會一直擴展，知道周圍沒有鄰域像素可以再擴izhan了為止}}}}//-------------------------------------------------------// If segment size is less then a limit, assign an// adjacent label found before, and decrement label count.//-------------------------------------------------------if(count <= SUPSZ >> 2)//這個區(qū)域太小{for( int c = 0; c < count; c++ ){int ind = yvec[c]*width+xvec[c];nlabels[ind] = adjlabel;}label--;}label++;}oindex++;}}numlabels = label;if(xvec) delete [] xvec;if(yvec) delete [] yvec; }

實驗結(jié)果

最后的實驗結(jié)果如下：

如果注釋掉EnforceLabelConnectivity函數(shù)里面去除小區(qū)域的代碼塊的結(jié)果是

所以還是加上比較好，SLIC只能整體效果看上去還是不錯哈，單張圖片耗時0.0845s，速度也比較快。

其他超像素算法對比

這里我順便跑了下這個項目里的其他超像素算法，以好有個對比
(1) Felzenswalb & Huttenlocher (P. F. Felzenswalb, D. P. Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision, 59(2), 2004.)
單張圖片耗時：0.0653s

(2) Constant Intensity Superpixels/Compact Superpixels (O. Veksler, Y. Boykov, P. Mehrani. Superpixels and supervoxels in anenergy optimization framework. European Conference on Computer Vision, pages 211–224, 2010.)
單張圖片耗時：0.0468s

(3) Entropy Rate Superpixels (M. Y. Lui, O. Tuzel, S. Ramalingam, R. Chellappa. Entropy rate superpixel segmentation. Conference on Computer Vision and Pattern Recognition, pages 2097–2104, 2011.)
單張圖片耗時：0.786s

(4) Pseudo Boolean Superpixels (Superpixels via pseudo-boolean optimization. Y. Zhang, R. Hartley, J. Mashford, and S. Burn. In International Conference on Computer Vision, 2011.)
單張圖片耗時：0.0255s

(5) Contour Relaxed Superpixels ( C. Conrad, M. Mertz, R. Mester. Contour-relaxed superpixels. Energy Minimization Methods in Computer Vision and Pattern Recognition, volume 8081 of Lecture Notes in Computer Science, pages 280–293, 2013.)
單張圖片耗時：0.430s

(6) Superpixels Extracted via Energy-Driven Sampling (M. van den Bergh, X. Boix, G. Roig, B. de Capitani, L. van Gool. SEEDS: Superpixels extracted via energy-driven sampling. European Conference on Computer Vision, pages 13–26, 2012.)
單張圖片耗時：0.0819s

(7) VLFeat ( A. Vedaldi, B. Fulkerson. VLFeat: An Open and Portable Library of Computer Vision Algorithms.\url{http://www.vlfeat.org/, 2008.)
單張圖片耗時：0.630s(這個結(jié)果應(yīng)該是我參數(shù)沒有設(shè)好)

(8) SNN
2018年好像又出了一個SNN專門用來生成超像素的深度神經(jīng)網(wǎng)絡(luò)框架，是基于SLIC的，但不管是效果還是速度都比SLIC要好。

總結(jié)
通過上面的退比可以發(fā)現(xiàn)同樣的圖片SLIC單張圖片耗時0.0845ms，在所有算法中算比較快的，從結(jié)果來看，效果比較看上去是比較好的，與其有類似效果的有Contour Relaxed Superpixels算法，但是耗時高達400ms，但是超像素的結(jié)果對比不能僅僅從上看去的效果進行比較，本文開始的的簡介中所提到的兩篇文章都有定義超像素效果優(yōu)良的衡量標(biāo)準(zhǔn)，如果需要詳細(xì)對比各個算法間的好壞的話還是需要去細(xì)讀論文和源碼。

總結(jié)

以上是生活随笔為你收集整理的超像素SLIC算法源码阅读的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。