基于非均勻熱擴(kuò)散的交互式圖像分割算法

孫凱月，劉向陽

(河海大學(xué) 理學(xué)院，江蘇 南京 211100)

0 引 言

圖像分割是把圖像分成若干個(gè)特定的、具有獨(dú)特性質(zhì)的區(qū)域并提出感興趣目標(biāo)的技術(shù)和過程。圖像分割在很多領(lǐng)域有著廣泛應(yīng)用，如醫(yī)學(xué)、軍事、氣象等。根據(jù)在分割過程中是否有用戶的參與，可以將圖像分割劃分為自動(dòng)式圖像分割和交互式圖像分割，該文主要研究交互式圖像分割。交互式圖像分割之初，需要用戶的交互操作指定限制條件，指導(dǎo)分割，分割完成后也可添加新的限制條件得到所需前景或背景結(jié)果。

比較經(jīng)典的交互式圖像分割算法有基于Graph Cuts的算法[1-3]、基于透明度的算法[4]、隨機(jī)游走算法[5-6]、深度學(xué)習(xí)算法[7-9]和測(cè)地算法[10-12]等。Graph Cuts的基本思想是通過構(gòu)造圖，使用最大流最小割集定理獲得某種特定形式的能量函數(shù)的全局最優(yōu)解?；谕该鞫鹊姆椒╗4]可以對(duì)單個(gè)像素點(diǎn)包含的色彩進(jìn)行前景和背景的分離，由于算法中加入了透明度，提取的結(jié)果中允許存在羽化的邊緣。隨機(jī)游走算法[4]通過對(duì)像素點(diǎn)貼標(biāo)簽，計(jì)算任一點(diǎn)隨機(jī)到達(dá)背景或前景的概率，從而決定指派區(qū)域。深度學(xué)習(xí)算法的核心思路是通過卷積神經(jīng)網(wǎng)絡(luò)(CNN)自動(dòng)獲取分割。2018年，Wang等人[10]用測(cè)地線距離圖將用戶與CNN的交互結(jié)合起來，并提出了一種能夠給出更好的密集預(yù)測(cè)的分辨率保持網(wǎng)絡(luò)。

除此以外，還有許多其他基于精確測(cè)地距離計(jì)算的圖像分割算法。2008年Criminisi等人[11]將圖像分割問題轉(zhuǎn)化為近似能量最小化問題，提出了一種基于測(cè)地距離的并行濾波算子用于獲取空間光滑、對(duì)比度敏感的分割。2012年Wei等人[12]利用背景的邊界和連通性，提出了新的測(cè)地特征度量。在該類算法中，有效的測(cè)地距離計(jì)算方法始終是保證精確分割的前提。Fast Marching算法是計(jì)算測(cè)地距離的精確算法，2000年由Sethian等人[13]提出，主要思想是通過求Eikonal方程的數(shù)值解，近似測(cè)地距離。2013年Crane等人[14]探尋熱與測(cè)地距離之間的關(guān)系，提出了熱方法(heat method)，核心是由熱方程找到距離增加的方向，再還原測(cè)地距離。

該文基于熱方法，提出了一種非均勻擴(kuò)散的熱方法計(jì)算測(cè)地距離，并將其應(yīng)用于交互式圖像分割。圖像的顏色信息可用于構(gòu)造三角網(wǎng)格，作為熱擴(kuò)散的媒介。此外，通過引入熱擴(kuò)散系數(shù)，熱方程被推廣到了更一般的形式，即非均勻的熱流方程。由于熱的梯度與距離梯度平行，用熱擴(kuò)散計(jì)算得到的單位梯度場(chǎng)，可用于還原真正的測(cè)地距離函數(shù)。最后，設(shè)置測(cè)地距離分割限制條件，即可快速有效地實(shí)現(xiàn)圖像前景分割。

1 熱方法

1.1 程函方程(Eikonal)

過去幾十年中，許多距離的逼近算法[15]都是基于求解Eikonal方程：

(1)

滿足邊界條件φ|γ=0，γ是邊界，可以是一個(gè)點(diǎn)或者一條曲線，φ是距離函數(shù)。Eikonal方程是非線性的雙曲方程，很難直接求解。Fast Marching算法利用一階逆風(fēng)差分格式求得數(shù)值解，近似測(cè)地距離。算法中使用了優(yōu)先隊(duì)列，靠近源點(diǎn)處的測(cè)地距離可以很快計(jì)算出來，但并行化問題無法解決。該方法最大的弊端在于，它們都沒有重用信息，對(duì)于不同的源點(diǎn)，兩點(diǎn)間的距離需要整個(gè)重新計(jì)算。雖然熱方法和Fast Marching都是基于Eikonal方程，但Fast Marching算法屬于波傳播的模型，而熱方法探尋的是熱與距離之間的關(guān)系，魯棒性強(qiáng)，精度高，更易于操作，且預(yù)計(jì)算中的大量信息可以被重用。

1.2 主要思想

由于觀察到熱擴(kuò)散的梯度與真正的距離函數(shù)的梯度平行，方向相反，所以熱方法首先需要找到距離增加的方向，然后利用泊松方程還原測(cè)地距離。熱方法可以應(yīng)用于任何定義了梯度算子、散度算子以及拉普拉斯算子Δ的連續(xù)空間，主要包括以下步驟[14,16]：

(2)計(jì)算單位向量場(chǎng)X=-ut/|ut|；

(3)解泊松方程Δφ=·X。

給定源點(diǎn)集，當(dāng)t→0，函數(shù)φ近似于真正的測(cè)地距離。熱方法還可以應(yīng)用于任何維度，以及定義了梯度和內(nèi)積的任何域，包括正交網(wǎng)格、三角網(wǎng)格和點(diǎn)云，這里著重討論三角網(wǎng)格上的熱擴(kuò)散。

1.3 拉普拉斯和梯度

為了將連續(xù)的過程轉(zhuǎn)變?yōu)殡x散的算法，核心是對(duì)梯度和拉普拉斯算子進(jìn)行空間上的離散化。給定三角網(wǎng)格，V表示頂點(diǎn)，E表示邊，F(xiàn)表示面片，則點(diǎn)i處的拉普拉斯離散化公式為[14,16]：

(2)

其中，Ai是i點(diǎn)附近所有三角形面積之和的三分之一，j是i的鄰近點(diǎn)，αij,βij是對(duì)應(yīng)邊的兩個(gè)對(duì)角。

梯度的離散化公式為：

(3)

其中,Af是三角形面片f的面積，N是向外的單位法向量，ei是i的邊緣向量，ui是其對(duì)角i的u值。

2 基于非均勻熱擴(kuò)散的交互式圖像分割算法

2.1 非均勻熱擴(kuò)散

將熱方法中的熱方程推廣到更一般的形式：

(4)

其中，D是熱擴(kuò)散系數(shù)，γ是源點(diǎn)或一條曲線，δ是指示函數(shù)。在均勻的各向同性介質(zhì)中，D通常表示為一個(gè)常數(shù)標(biāo)量乘以Id，標(biāo)量代表傳導(dǎo)率，Id是單位矩陣。如果各個(gè)區(qū)域上的傳導(dǎo)率不同，則可表示更一般介質(zhì)上的非均勻擴(kuò)散[17]。

假設(shè)p是圖像上的任意像素點(diǎn)，可以定義熱擴(kuò)散系數(shù)D為：

(5)

其中，Q表示人工交互區(qū)域，f是圖像的灰度值或RGB函數(shù)，q>1用于調(diào)節(jié)交互區(qū)域上的擴(kuò)散速度。于是，非均勻熱方程在三角網(wǎng)格上可以離散化為：

(6)

2.2 單位向量場(chǎng)

由于熱擴(kuò)散的方向平行于真正的距離增加的方向，故可用非均勻熱流方程解的梯度近似最終的距離函數(shù)梯度，從而還原測(cè)地距離。熱流梯度的大小可以忽略，這里，由Eikonal方程，假設(shè)距離函數(shù)的梯度是單位長(zhǎng)度的。另外需要注意的是，熱增加的方向與距離增加的方向相反，故還需對(duì)其進(jìn)行負(fù)化得到下面的單位向量場(chǎng)：

(7)

2.3 泊松方程

利用單位向量場(chǎng)，最終的測(cè)地距離函數(shù)φ可通過求解下面的泊松方程還原。

div(Dφ)=·X.

(8)

令b為單位向量場(chǎng)的散度向量，泊松方程可以離散化為三角網(wǎng)格上的稀疏線性方程組：

(9)

2.4 交互式圖像分割算法

原理：非均勻擴(kuò)散的熱方法計(jì)算得到的測(cè)地距離可用于分割圖像的前景或背景區(qū)域。這里，主要討論前景分割。如圖1所示，假設(shè)圖像的前景區(qū)域由三個(gè)灰度值不同的矩形組成，若選定第一個(gè)矩形中某一點(diǎn)為源點(diǎn)，計(jì)算測(cè)地距離并設(shè)置限制，只能將前景中最上方的矩形分割出來，圖1(a)中的黑邊框即為分割的邊界線。而經(jīng)過圖1(b)中的人工干預(yù)，標(biāo)記區(qū)域上的熱擴(kuò)散速度增加，使得灰度值不同的三個(gè)部分之間測(cè)地距離變小，消除了內(nèi)部邊界，從而分割出完整的前景部分。這里，將人工干預(yù)區(qū)域始末兩點(diǎn)設(shè)置為源點(diǎn)。

圖1 人工交互對(duì)分割的影響

如下面的西瓜示例中，圖2中的(b)、(c)分別是人工交互前和人工交互后的測(cè)地距離等值線圖和分割結(jié)果圖。前者以半個(gè)西瓜上某一點(diǎn)為源點(diǎn)，只能分割出前景的一部分。后者將人工標(biāo)記區(qū)域上的熱流擴(kuò)散速度設(shè)置為q=200，則前景中兩個(gè)不同部分之間的測(cè)地距離變小，邊界消除，最終分割出了完整的前景區(qū)域。

圖2 人工交互下的前景分割示例

該算法的核心思路是通過非均勻的熱擴(kuò)散計(jì)算測(cè)地距離，從而實(shí)現(xiàn)交互式圖像分割。圖像的灰度值或RGB值可用于構(gòu)造Delaunay三角網(wǎng)格，作為熱擴(kuò)散的媒介。值得注意的是，梯度更大的邊界會(huì)導(dǎo)致其周圍兩側(cè)點(diǎn)之間的高度相差更多，熱流擴(kuò)散得更慢。非人工區(qū)域上的熱擴(kuò)散系數(shù)中，設(shè)置梯度與擴(kuò)散速度呈反比，同樣減緩了熱在邊界上的擴(kuò)散。經(jīng)過人工交互，更多的測(cè)地距離等值線密集在外部邊界上，形成了完整的前景輪廓。最后，只需設(shè)置相關(guān)的分割限制條件，即可分割出感興趣的前景區(qū)域。該算法步驟簡(jiǎn)單，操作方便，預(yù)計(jì)算中大量信息可以重用，節(jié)省了內(nèi)存和時(shí)間消耗，整體流程如圖3所示。

圖3 基于非均勻熱擴(kuò)散的交互式圖像分割算法流程

3 實(shí)驗(yàn)結(jié)果和分析

3.1 參數(shù)評(píng)估

圖4是一幅灰度值相同的二維圖像，圖中的曲線是人工交互標(biāo)記部分。以“×”為源點(diǎn)，不同擴(kuò)散速度的熱方法下的測(cè)地距離計(jì)算結(jié)果存在明顯差異。

圖4 人工干預(yù)

圖5分別是設(shè)置q=40，q=100，q=200，求解方程(4)得到的熱擴(kuò)散圖。隨著擴(kuò)散系數(shù)q不斷增大，更多的熱擴(kuò)散到了人工標(biāo)記的區(qū)域上。

圖5 不同擴(kuò)散速度下熱方程的解

圖6是由式(7)計(jì)算得到的單位向量場(chǎng)，其中ut是非均勻熱方程(6)的數(shù)值解，熱擴(kuò)散系數(shù)(5)中分別設(shè)置：q=40，q=100，q=200。隨著人工標(biāo)記區(qū)域上的熱擴(kuò)散速度不斷增加，其周圍的向量偏離標(biāo)記曲線指向兩邊外側(cè)的幅度越大。單位向量場(chǎng)指向的是測(cè)地距離增加最快的方向，這可以近似看作源點(diǎn)集由原先的一個(gè)點(diǎn)不斷向一條曲線演變。

圖6 不同擴(kuò)散速度下的單位梯度場(chǎng)

圖7是由泊松方程(9)計(jì)算得到的測(cè)地距離圖，人工標(biāo)記區(qū)域上的熱擴(kuò)散系數(shù)設(shè)置同樣的值。隨著q不斷增加，標(biāo)記曲線上的測(cè)地距離也不斷減小。

圖7 不同擴(kuò)散速度下計(jì)算的測(cè)地距離

3.2 實(shí)驗(yàn)結(jié)果及分析

基于非均勻熱擴(kuò)散的交互式圖像分割算法可以應(yīng)用于各類真實(shí)圖像中復(fù)雜前景的提取，包括人物、動(dòng)物、建筑等等。圖8中的(a)為人工標(biāo)記的圖像，(b)是由非均勻擴(kuò)散的熱方法計(jì)算得到的測(cè)地距離圖，設(shè)置q=200，(c)是最終的分割結(jié)果。(b)中可以看到，更多的距離等值線密集在前景的外部邊界上，形成了明顯的輪廓，這時(shí)，只需要設(shè)置像素點(diǎn)的距離小于輪廓處的距離值就可以將前景完整地分割出來。值得一提的是，盡管圖8中的前景和背景都較為復(fù)雜，但該算法也只需要一筆少量的人工標(biāo)記就可以實(shí)現(xiàn)有效的分割。

圖8 非均勻熱擴(kuò)散的交互式分割算法應(yīng)用于各類圖像

4 結(jié)束語

提出了一種非均勻擴(kuò)散的熱方法計(jì)算測(cè)地距離，并將其應(yīng)用于交互式圖像分割?；跓岱椒?，算法中引入并定義了熱擴(kuò)散系數(shù)，將熱方程推廣到了更一般的形式。非均勻擴(kuò)散的熱方法計(jì)算測(cè)地距離僅需求解兩個(gè)稀疏線性方程組，簡(jiǎn)單快速，更易于操作。實(shí)驗(yàn)結(jié)果表明，該算法可以精確有效地應(yīng)用于各類真實(shí)圖像的交互式分割，且無需過多的人工干預(yù)。在得到測(cè)地距離之后，分割限制條件的設(shè)置還有待進(jìn)一步的調(diào)整，以便適用于更加復(fù)雜的現(xiàn)實(shí)圖像。如何有效且充分地綜合利用好圖像的顏色和紋理信息也是接下來優(yōu)化算法的努力方向。