基于塊矩陣的快速圖像分割

谷 莉

同濟(jì)大學(xué)軟件學(xué)院，上海 201804

1 概述

圖像分割在計算機(jī)視覺領(lǐng)域中的一個經(jīng)典問題，圖像分割的方法也多種多樣。近年來基于圖論的分割方法逐漸成為研究熱點[1]?；趫D論的圖像分割方法的基本原理是首先對輸入的圖像建立一個帶權(quán)的無向圖，其中圖的一個頂點代表圖像中的一個像素，邊上的權(quán)表示邊上兩個頂點之間的相關(guān)性，然后定義一個目標(biāo)函數(shù)并對其優(yōu)化求解，目標(biāo)函數(shù)的最優(yōu)解對應(yīng)一種圖像分割。

對不同的目標(biāo)函數(shù)會有不同的求解方法。譜分析是一種常用的求解方法。這里的譜分析是指用拉普拉斯矩陣的特征向量分析問題。然而，求矩陣特征向量的過程是非常耗時的，也對計算機(jī)內(nèi)存要求很高，這就在很大程度上限制了這類方法的應(yīng)用。本文提出了一種基于塊矩陣的方法能有效地解決這個問題，它不僅可以加速分割過程，同時還可以處理較大的圖像。

2 譜聚類與圖像分割

由于聚類問題和圖像分割本質(zhì)上是相同的，所以許多用作譜聚類的標(biāo)準(zhǔn)和方法也可以用來實現(xiàn)圖像分割。

2.1 圖像分割的度量標(biāo)準(zhǔn)

通常，把圖像中的每個像素看作一個節(jié)點，可以構(gòu)造一個帶權(quán)的無向圖T=（V, E, W）。V是所有節(jié)點的集合；E是圖中所有邊的集合；W是權(quán)矩陣，矩陣元素w（i, j）表示頂點i和j之間的相關(guān)性。將圖像一分為二實際上就是將頂點集合V分成兩個不相交的子集A和B ：且。那么衡量圖像分割結(jié)果好壞的標(biāo)準(zhǔn)可以用下面的等式來定義：

2.2 求解目標(biāo)函數(shù)的譜方法

事實上，這個最小化問題可以轉(zhuǎn)化為廣義特征值問題[1]：

權(quán)矩陣W 中元素w（i,j）表示頂點i和j之間的相關(guān)性；權(quán)w（i,j）越大表示頂點i和j之間的相關(guān)性越強(qiáng)，分在同一個子集中的可能性越大。由于圖像一般只是局部相關(guān)的，可以將頂點距離大于r（r遠(yuǎn)小于像素個數(shù)）的那些頂點之間的權(quán)w（i,j）賦值為0，這樣對計算得到的Fiedler向量的分量排序沒有太大影響，同時由于權(quán)矩陣W變成了稀疏對稱矩陣還可以加快計算速度。

3 基于塊矩陣的圖像分割

然而求解特征值方程（3）的全部特征向量是既耗時又耗費(fèi)內(nèi)存的工作，它的運(yùn)算數(shù)量級是O（n3）。在處理大圖像時,這是很不實際的。但是用Fiedler向量分割圖像具有下列特性：

1）圖像在多數(shù)情況下僅僅是局部相關(guān)的，所以最后得到的權(quán)矩陣W是稀疏矩陣；

2）對Fiedler向量的精確度要求不高，圖像分割中實際使用的是其分量的排列順序。

針對這些特性，我們提出塊矩陣方法來快速求解近似的Fiedler向量?？梢詮膱D像分塊的角度來理解矩陣分塊的思想。首先將一幅圖像m分成4塊（也可以更多）mi，i=1...4。對每個塊圖像分別求其權(quán)矩陣Wi,i=1...4，他們正好對應(yīng)主對角線上的塊矩陣。由于圖像分塊產(chǎn)生的邊界打斷了原圖像m的連續(xù)性，所以需要在局部區(qū)域附加一些約束以保持其原有的連續(xù)性。這里我們是在塊與塊之間的邊界周圍擴(kuò)展了部分區(qū)域形成一些小的塊圖像，n12…n5就是由邊界擴(kuò)展生成的塊圖像。這些擴(kuò)展塊的大小通?？梢砸?guī)定為邊界兩邊各2r個像素的范圍內(nèi)。在擴(kuò)展塊圖像中邊界線兩側(cè)像素之間的相關(guān)性形成的權(quán)矩陣正好對應(yīng)非對角線上的塊矩陣。

3.1 算法步驟

綜上所述，基于塊矩陣的分割方法可以通過如下步驟實現(xiàn)：

1）將圖像分成幾大塊，分別計算其Fiedler向量并形成塊圖像的（局部）分割，然后將這些局部分割綜合起來形成整幅圖像的初始分割；

2）在邊界周圍擴(kuò)展生成塊圖像，分別計算其Fiedler向量并形成局部分割，用這些局部分割結(jié)果來優(yōu)化初始分割中邊界附近的分割。

4 實驗結(jié)果分析

用本文提出的基于塊矩陣的方法分割場景圖像好處是：1）對同樣大小的圖像，我們可以得到與Ncut方法[1]相似的分割結(jié)果（圖1），同時還能大大提高分割速度；2）由于Ncut方法計算過程占用大量的計算機(jī)內(nèi)存,對一些較大的圖像用它根本無法分割，而用本文提出的方法可以很容易地完成分割并得到理想的結(jié)果。

圖1

圖1一幅160X160的嬰兒圖像。a∶Ncut方法的分割結(jié)果，整個過程花費(fèi)了35.16秒；b：用本文提出的方法分割得到的結(jié)果，整個過程只需要20.79秒。

5 結(jié)論

本文提出一種新的快速圖像分割方法，和其它譜聚類方法相比，本文提出的基于塊矩陣的方法在得到很好的分割結(jié)果的同時還能大大提高分割速度。

[1]J.Shi and J.Malik.Normalized cuts and image segmentation [J].IEEE Trans. on Pattern Anal.and Machine Intell.2000，22(8)：888-905.