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

孫凱月，劉向陽

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

0 引 言

圖像分割是把圖像分成若干個特定的、具有獨特性質的區域并提出感興趣目標的技術和過程。圖像分割在很多領域有著廣泛應用，如醫學、軍事、氣象等。根據在分割過程中是否有用戶的參與，可以將圖像分割劃分為自動式圖像分割和交互式圖像分割，該文主要研究交互式圖像分割。交互式圖像分割之初，需要用戶的交互操作指定限制條件，指導分割，分割完成后也可添加新的限制條件得到所需前景或背景結果。

比較經典的交互式圖像分割算法有基于Graph Cuts的算法[1-3]、基于透明度的算法[4]、隨機游走算法[5-6]、深度學習算法[7-9]和測地算法[10-12]等。Graph Cuts的基本思想是通過構造圖，使用最大流最小割集定理獲得某種特定形式的能量函數的全局最優解。基于透明度的方法[4]可以對單個像素點包含的色彩進行前景和背景的分離，由于算法中加入了透明度，提取的結果中允許存在羽化的邊緣。隨機游走算法[4]通過對像素點貼標簽，計算任一點隨機到達背景或前景的概率，從而決定指派區域。深度學習算法的核心思路是通過卷積神經網絡(CNN)自動獲取分割。2018年，Wang等人[10]用測地線距離圖將用戶與CNN的交互結合起來，并提出了一種能夠給出更好的密集預測的分辨率保持網絡。

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

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

1 熱方法

1.1 程函方程(Eikonal)

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

(1)

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

1.2 主要思想

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

(2)計算單位向量場X=-ut/|ut|；

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

給定源點集，當t→0，函數φ近似于真正的測地距離。熱方法還可以應用于任何維度，以及定義了梯度和內積的任何域，包括正交網格、三角網格和點云，這里著重討論三角網格上的熱擴散。

1.3 拉普拉斯和梯度

為了將連續的過程轉變為離散的算法，核心是對梯度和拉普拉斯算子進行空間上的離散化。給定三角網格，V表示頂點，E表示邊，F表示面片，則點i處的拉普拉斯離散化公式為[14,16]：

(2)

其中，Ai是i點附近所有三角形面積之和的三分之一，j是i的鄰近點，αij,βij是對應邊的兩個對角。

梯度的離散化公式為：

(3)

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

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

2.1 非均勻熱擴散

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

(4)

其中，D是熱擴散系數，γ是源點或一條曲線，δ是指示函數。在均勻的各向同性介質中，D通常表示為一個常數標量乘以Id，標量代表傳導率，Id是單位矩陣。如果各個區域上的傳導率不同，則可表示更一般介質上的非均勻擴散[17]。

假設p是圖像上的任意像素點，可以定義熱擴散系數D為：

(5)

其中，Q表示人工交互區域，f是圖像的灰度值或RGB函數，q>1用于調節交互區域上的擴散速度。于是，非均勻熱方程在三角網格上可以離散化為：

(6)

2.2 單位向量場

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

(7)

2.3 泊松方程

利用單位向量場，最終的測地距離函數φ可通過求解下面的泊松方程還原。

div(Dφ)=·X.

(8)

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

(9)

2.4 交互式圖像分割算法

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

圖1 人工交互對分割的影響

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

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

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

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

3 實驗結果和分析

3.1 參數評估

圖4是一幅灰度值相同的二維圖像，圖中的曲線是人工交互標記部分。以“×”為源點，不同擴散速度的熱方法下的測地距離計算結果存在明顯差異。

圖4 人工干預

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

圖5 不同擴散速度下熱方程的解

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

圖6 不同擴散速度下的單位梯度場

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

圖7 不同擴散速度下計算的測地距離

3.2 實驗結果及分析

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

圖8 非均勻熱擴散的交互式分割算法應用于各類圖像

4 結束語

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