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

谷 莉

同濟大學軟件學院，上海 201804

1 概述

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

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

2 譜聚類與圖像分割

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

2.1 圖像分割的度量標準

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

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

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

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

3 基于塊矩陣的圖像分割

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

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

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

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

3.1 算法步驟

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

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

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

4 實驗結(jié)果分析

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

圖1

圖1一幅160X160的嬰兒圖像。a∶Ncut方法的分割結(jié)果，整個過程花費了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.