結合GMM和Graph?Cuts的直觀傳輸函數設計方法

摘 要： 提出一種新的基于筆畫的傳輸函數設計方法。與其他基于筆畫的方法相比，該方法只要求用戶對感興趣數據做少量標記，操作更簡便；另外該方法更好地考慮了體數據的空間信息，分類結果更合理。首先使用貪心極大似然估計算法構建用戶感興趣數據和背景數據的高斯混合模型（GMM）模型；然后基于GMM模型使用Graph?Cuts實現對體數據的分類，并通過仔細設計Graph?Cuts能量函數的平滑項將空間信息引入分類過程。針對體數據的規模大，難以直接應用Graph?Cuts算法的難題，在此通過使用層次模型減小Graph?Cuts算法所處理問題的規模，從而獲得了實時交互的效果。該方法使用多個體數據進行測試，獲得令人滿意的效果。

關鍵詞： 直接體繪制； 傳輸函數； Graph?Cuts算法； 高斯混合模型； 空間信息

中圖分類號： TN919?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2013）14?0004?06

Design method of intuitive transfer function combining GMM and Graph?Cuts

TAN Wen?min， LUO Yue?tong， ZHU Hui?guo， HAN Juan

（VCC Division， School of Computer and Information， Hefei University of Technology， Hefei 230009， China）

Abstract： A new design method of paint?based transfer function is presented in this paper. In comparison with other paint?based methods， the proposed method only asks the user to mark the interesting data. It is more convenient anyway. In addition， the method more appropriately considers volume data’s spatial information， and results in more reasonable classification. Firstly， the Gaussian mixed models （GMMs） for both user’s interesting data and background data are established by greedy maximum likelihood estimation algorithm， then classification is achieved by Graph?Cuts optimizations based on the established GMMs， and spatial information is involved in the classification through careful design of smoothing term of the Graph?Cuts energy function. In general， volume data is too large to apply Graph?Cuts algorithm directly for interactive rate， which is resolved by using volume data’s hierarchical model. Testing on several volume data has demonstrated the effectiveness and advantage of the method.

Keywords： direct volume rendering； transfer function； Graph?Cuts algorithm； GMM； spatial information

0 引 言

直接體繪制能將三維體數據直接轉化為二維圖像，能有效揭示體數據內部特征，是最重要科學計算可視化技術之一。傳輸函數是直接體繪制方法的關鍵步驟，它將體數據映射到顏色、透明度等光學屬性，是實現體數據內部特征有效展示的關鍵，因此傳輸函數設計一直是體數據可視化領域的研究熱點[1]。

關于傳輸函數的研究一直圍繞兩個問題：一是如何提高傳輸函數的分類能力，二是如何增強傳輸函數設計過程的直觀性。基于標量值的一維傳輸函數最早出現，應用也最廣泛，但一維傳輸函數分類能力不強，如難以有效區分CT值范圍有重疊的器官組織[2]，為此人們在傳輸函數中引入其他信息，如梯度模、曲率[3]、特征大小[4]、紋理[5]和形狀[6]等信息，發展具有更強分類能力的高維傳輸函數。G. Kindlmann在 IEEE Visualization 2001上指出空間信息對體數據分類至關重要[7]。將體素的空間坐標x， y和z直接作為傳輸函數的輸入變量是引入空間信息的最簡單方法但實踐證明這種方法的效果不理想，因為空間信息不僅指體素的空間位置，還包括體素之間的連接關系，而且有時連接關系對分類更重要。Roettger S等人和Claes Lundstr?m等人都在基于空間信息的傳輸函數設計方面進行了有效嘗試，他們基于空間屬性對直方圖進行劃分，進而設計出包含空間信息的傳輸函數[8?9]。本文的出發點正是研究如何有效利用空間信息，尤其是相鄰關系的空間信息增強傳輸函數的分類能力的方法。

高維傳輸函數雖然具有更強的分類能力，但其參數空間更大，設計過程更復雜，為此人們研究各種直觀傳輸函數設計方法。基于各種數據分析及技術的自動、半自動傳輸函數設計方法最受關注，如Chen Wei等使用核密度估計（KDE）方法[10]、Yunhai Wang等使用高斯混合模型（GMM）分析體數據的直方圖[11]，然后用戶基于分析結果半自動設計傳輸函數；Fan?Yin Tzeng 和Kwan?Liu Ma使用ISODATA聚類法首先進行體數據聚類，然后用戶根據少量聚類結果完成傳輸函數設計；此外，人們還提出傳輸函數設計倉庫（Design Gallery）[13]、傳輸函數電子表格（SpreedSheet） [14]等交互函數設計方法。和上述方法均要求用戶在傳輸函數參數空間進行操作不同，基于筆畫的方法允許用戶直接在體數據空間（切片圖像或直接體繪制結果圖像）設計傳輸函數，因此操作更方便直觀。

基于筆畫的傳輸函數設計由三個基本步驟組成：用戶使用畫筆標記感興趣（或不感興趣數據），生成樣本數據；然后使用某種數據分析方法基于樣本數據自動生成高維傳輸函數；最后完成體數據的分類。F.Y. Tzeng 等讓用戶在切片圖像上標記樣本點，然后使用樣本點訓練神經網絡或支持向量機，用完成訓練的神經網絡或支持向量機作為二十四維傳輸函數[15]；Y. T. Luo等人實現類似于[15]的傳輸函數設計方法，但Y. T. Luo 等將生成傳輸函數過程看作高維空間的插值問題[16]，使用徑向高斯函數逼近方法自動生成高維傳輸函數；Hanqi G 等允許用戶直接操作直接體繪制的結果圖像，實現所見即所得的傳輸函數設計方法[17]。上述基于筆畫的方法均能考慮體數據的空間信息，但都僅直接簡單地使用x，y，z坐標，沒有做深入分析。本文的整體流程與文獻[15?16]類似，但分類過程通過Graph?Cuts算法實現。因為Graph?Cuts算法能考慮體素之間的鄰接關系，因此能很好地將空間信息，尤其是空間鄰接信息引入體數據分類過程，進而能改進體數據的分類效果。

1 方法概述

本文方法的整體流程如圖1所示。首先在預處理階段為體數據建立層次模型，該層次模型將用于減小Graph?Cuts算法的問題規模，從而保證能獲取實時交互的效果；在完成預處理工作后，由用戶手動在少量切片圖上標記前景數據（即感興趣數據），之后系統自動地分別構建前景數據和背景數據的GMM模型，圖中步驟③；之后根據①，③的結果構建圖，并應用Graph?Cuts算法完成體數據分類；最后根據分類結果實時生成渲染結果圖像。如果渲染結果不能滿足用戶要求，用戶可通過標記新數據來優化結果，整個過程具有實時交互性。

圖1 算法整體流程

體數據的層次模型、前景數據和背景數據的GMM模型、基于Graph?Cuts 的分類過程是整個算法的三個關鍵步驟。

2 預處理：構建體數據層次模型

體數據的規模一般都較大，如果直接將體素作為圖的頂點，那么Graph?Cuts算法的效率將較低，難以實現實時交互效果。為此本文在在預處理階段構建體數據的層次模型，之后基于層次模型構建小規模圖用于Graph?Cuts算法，以獲得實時交互效果。

體數據的層次模型如圖2所示，采用八叉樹結構存儲，八叉樹的根結點表示整個體數據，葉子結點對應于體素，且每個結點保存所對應體數據的分布特征和結構特征。

圖2 體數據的層次模型

分布特性：指數據的分布情況。首先采用k?Means算法進行聚類分析，然后使用每個類的中心位置、類方差、樣本點數表示八叉樹結點的數據分布特征，即。如果直接用均值和方差描述數據的分布特征，對于如圖3所示包含多種數據的情況不能準確刻畫，但采用本文方法能有效解決這個問題。用戶可指定類別數目，但試驗表明時效果較好，因此本文的所有試驗中均為4。如果某八叉樹結點中體素的個數少于，則使用相應數據的均值和方差表示分布特性，即。

圖3 包含多種數據的數據塊

結構特征：不同物質之間的邊界是體數據的最重要結構特征之一，梯度模能有效刻畫體數據的邊界特性，因此本文使用八叉樹結點所對應的所有體素的梯度模的平均值表示其結構特征，即，其中表示梯度。

3 前景數據與背景數據的高斯混合模型

高斯混合模型非常適合描述離散采樣點，在模式識別、醫學圖像分割等領域得到了廣泛應用，近年可視化領域也應用GMM解決不確定數據可視化和傳輸函數設計問題。和文獻[15?16]直接把用戶標記數據作為樣本點作為神經網絡、支持向量機、高維函數逼近的輸入不同，本文首先構建前景和背景的混合高斯模型和，然后再將和作為Graph?Cuts算法的輸入。因為GMM是一種統計模型，具有良好的抗噪性能，且用戶只需少量輸入即可獲得滿意效果。

和分別表示整個體數據和用戶手工標記的體素。本文采用類似于文獻[11]改進的貪心極大似然算法估算高斯混合模型和。前景高斯混合模型（個高斯模型）直接基于用戶標記體素進行估算。本文方法中用戶只需標記前景數據，因此本文將整個體數據當作背景數據進行背景高斯混合模型（個高斯模型）估算。雖然和可以任意取值，但實驗表明和分別取2和4時效果較好。這是因為前景數據比較一致，而背景數據組成更加復雜，因此的取值要比小。圖4展示了用戶在腳數據切片上的勾畫情況，及對應的前景數據和背景數據的GMM模型。

圖4 肢數據的前景與背景的GMM

4 基于Graph?Cuts的體數據分類

Graph?Cuts算法是一種基于能量方程最小化求解的圖分割方法，在圖像分割、數據分類等領域都有廣泛應用。本文將體數據分類看作圖分割過程，應用Graph?Cuts算法實現體數據分類，具體實現時借鑒文獻[12]最小圖割優化算法。數據分類過程包含兩個關鍵步驟：基于體數據的層次模型構建圖，要既能表示體數據的特性，又盡量減少圖的規模；構造合適的能量函數，進而保證Graph?Cuts的結果能很好地體現用戶意圖。

4.1 構建圖

最直接的構建圖方法是將每個體素作為一個頂點，在相鄰體素對應的頂點之間添加一條邊，但這種圖因過大而難以應用Graph?Cuts算法進行快速處理，難以滿足本文的實時交互性要求。因此本文通過從體數據的層次模型中選取合適結點作為圖頂點來減小圖規模，進而提高Graph?Cuts算法的運行效率。本文采用圖5所示遞歸算法選取層次模型結點，其中IsForgroundNode（Node）用于判斷結點Node對應體素是否全部屬于前景，而IsBackgroundNode（Node）則用于是否全部屬于背景。

如果頂點滿足下列全部條件，那么認為所包含的全部體素都屬于前景，即屬于前景：

（1）：滿足此條件表示結點所包含數據的每個類的聚合度都很高，使用類中心表示整個類合理；

（2）：滿足此條件表示屬于前景的概率很大。因為體數據的結構特征對分類結果有重要影響，因此通過為結構特征強的結點設置更苛刻的閾值條件，以防止結構特征過早被過濾掉。

圖5 選擇層次模型結點的偽代碼算法

（3）：此條件表示屬于背景的可能性很小，的作用與第（2）條類似。采用類似的過程判斷是否屬于背景，但判斷條件（2）和（3）分別是：

對于體素數少于的結點處理過程與上述過程完全一致，相當于的特例。

將選出層次模型結點作為圖的頂點，如果兩個結點所對應的體數據相鄰，那么在對應的圖頂點之間添加一條邊。如在圖6中，有色彩標記的結點表示是被選中的結點，對應的圖如（b）所示。

4.2 能量函數計算

基于前景模型和背景模型，應用Graph?Cuts算法實現體數據分類，也就是將體數據分類轉換為對圖頂點標記問題，即通過最小化以下能量函數求得每個體素的二值標簽 ：

式中：數據項表示頂點被標記為的懲罰量；平滑項表示給相鄰頂點和賦予不同標簽時的懲罰量；是調節和的權重系數。

圖6 構圖示意圖

為了更清楚地描述和的定義，本文首先討論圖的每個頂點對應一個體素，然后再討論圖頂點表示層次模型結點的情況。

（1）圖頂點表示體素

在此情況下的和的定義分別為：

數據項根據前景模型和背景模型進行定義，其中是一很大常數，和分別為和，其中ε取一個很小的正常數（本文中），以防止取無窮大值，表示體素對應的標量值。因為梯度模能有效刻畫體素之間的光滑度，因此本文根據梯度模定義平滑項，其中和分別表示體素和對應的梯度模，為一常數。

（2）圖頂點表示層次模型結點

此時圖的一個頂點可能對應一組體素，不能直接應用上述能量函數。

數據項的定義與第1節描述基本一致，但因為層次模型結點包含多個類中心，而不是一個標量值，所以將和的定義進行如下改進：

因為兩個相鄰圖頂點實際對應一個或多個相鄰體素，所以本文根據相鄰體素梯度模的平均值計算平滑項。圖7（a）中，小圓圈表示體素，虛線框方框對應層次模型結點，相應圖如圖7（b）所示，邊上標記了用于計算平滑項的平均梯度模，因此平滑項計算公式如下：

式中：與是與空間相鄰的體素；是相鄰體素個數。

圖7 構建圖示意圖

5 實驗結果

本文對結合GMM和Graph?Cuts的直觀傳輸函數設計進行了實現，并使用多個體數據進行實驗。實驗的基本配置如下：Intel I3 2.93 GHz CPU，2.0 GB RAM，NVIDIA GeForce GTS450 GPU。運行環境為Microsoft WIN7 32 b，程序設計中使用了Qt 4.7.2與OpenGL 3.1等庫，其中主要部分使用C++語言編寫，用于體繪制的光線投射算法以及光照部分采用的是可編程著色器語言GLSL。首先選用128×128×128的腳數據檢驗本文方法的效果，如圖8所示。

圖8 腳部數據分類結果

圖8（c）是腳數據的整體情況，其中骨骼數據被外圍的肌肉、皮膚等包圍，實驗的目標是將骨骼清晰展現出來。用戶只需使用畫筆在切片上標記骨骼區域，之后系統就自動對整個體數據進行分類，將骨骼清晰展現，如圖8所示。由圖可觀察到，分類結果比較理想，其他背景數據如肌肉、皮膚等被較干凈地去除，僅保留了骨骼。

高斯混合模型是本文方法的重要組成部分，高斯模型的參數和 對結果有重要影響，太小難以準確刻畫數據特性，太大則容易計算量過大。這里選用128×128×128的頭顱數據測試kf和kb對算法性能的影響。圖9（c）中用戶用畫筆選擇了骨骼和牙齒部分，當和時，分類結果如圖9（a）所示，結果不很理想，這是因為骨骼和牙齒的CT值相差較大，只有1個高斯模型的GMM不能準確表達前景數據。圖9（b）表示與分別取2和4時的效果比較理想。這也說明了高斯混合模型參數和 對本文方法性能有重要影響。

圖9 不同前景聚類中心個數對繪制結果的影響

6 結 語

本文提出一種新的基于筆畫的傳輸函數設計方法，通過結合使用GMM和Graph?Cuts，能在用戶進行少量交互的情況下獲得滿意的結果，尤其在能較好地將體數據的空間特征反應到分類結果中。為獲得實時交互效果，本文結合體數據層次模型降低圖的規模，從而減少Graph?Cuts的計算量，相關實驗證明了本文方法具有良好的實時交互效果。GMM是本文方法的重要組成部分，高斯模型的個數對GMM的性能也有重要影響，但本文不能做到自動確定合適參數，還要依賴經驗進行設置，希望下一步能自動選擇GMM的參數。在設計Graph?Cuts的能量函數時，本文只使用了梯度模刻畫體數據的空間特性，未來將進一步探索更合理的描述方法。

參考文獻

[1] PFISTER Hanspeter， BAJAJ Chandrajit， SCHROEDER Will， et al. The transfer function bake?off [C]// Proceedings of 2000 IEEE Visualization. [S.l.]： IEEE， 2000： 523?526.

[2] KNISS J， KINDLMANN G， HANSEN C. Interactive volume rendering using multi?dimensional transfer functions and direct manipulation widgets [C]// Proceedings of 2001 IEEE Visualization. [S.l.]： IEEE， 2001： 255?262.

[3] KINDLMANN G， WHITAKER R， TASDIZEN T， et al. Curvature?based transfer functions for direct volume rendering： methods and applications [C]// Proceedings of the 14th IEEE Visualization. Washington， DC， USA ： IEEE Computer Society， 2003： 67?73.

[4] CORREA C， KWAN?LIU M. Size?based transfer functions： a new volume exploration technique [J]. IEEE Transactions on Visualization and Computer Graphics， 2008， 14（6）： 1380?1387.

[5] CABAN J J， RHEINGANS P. Texture?based transfer functions for direct volume rendering [J]. IEEE Transactions on Visualization and Computer Graphics， 2008， 14（6）： 1364?1371.

[6] PRASSNI J S， ROPINSKI T， MENSMANN J， et al. Shape?based transfer functions for volume visualization [C]// 2010 Pacific Visualization Symposium. [S.l.]： IEEE， 2010： 9?16.

[7] KINDLMANN G. Transfer functions for direct volume rendering [C]// Proceedings of 2001 IEEE Visualization. [S.l.]： IEEE， 2001： 111?121.

[8] ROETTGER S， BAUER M， STAMMINGER M. Spatialized transfer functions [C]// EUROGRAPHICS IEEE VGTC Symposium on Visualization. [S.l.]： IEEE， 2005： 271?278.

[9] LUNDSTR?M Claes， YNNERMAN Anders， LJUNG Patric， et al. The alpha ?histogram： using spatial coherence to enhance histograms and transfer function design [C]// Proceedings of IEEE Visualization Symposium. [S.l.]： IEEE， 2001： 227?234.

[10 ]MACIEJEWSKI R， INSOO W， WEI C， et al. Structuring feature space： a non?parametric method for volumetric transfer function generation [J]. IEEE Transactions on Visualization and Computer Graphics， 2009， 15（6）： 1473?1480.

[11] YUNHAI W， WEI C， JIAN Z， et al. Efficient volume exploration using the gaussian mixture model [J]. IEEE Transactions on Visualization and Computer Graphics， 2011， 17（11）： 1560?1573.

[12] BOYKOV Y Y， JOLLY M P. Interactive graph cuts for optimal boundary region segmentation of objects in n?d images [C]// Proc. Internation Conference on Computer Vision. [S.l.]： ICCV， 2001： 105?112.

[13] GIBSON S， BEARDSLEY P， RUML W， et al. Design galleries： a general approach to setting parameters for computer graphics and animation [C]//Proceedings of 1997 SIGGRAPH. [S.l.]： SIGGRAPH， 1997： 389?400.

[14] JANKUN?KELLY T J， KWAN?LIU M. A spreadsheet interface for visualization exploration [C]// Proceedings of 2000 Visualization. [S.l.]： [s.n.]， 2000： 69?76.

[15] TZENG F Y， LUM E， MA K L. An intelligent system approach to higher?dimensional classification of volume data [J]. IEEE Trans. on Visualization and Computer Graphics， 2005， 11（3）： 273?284.

[16] LUO Yue?tong， CHEN Jin?sheng， WANG Han?bin， et al. Flexible painting?based volume classification using ellipsoid Gaussian transfer function [C]// Proceedings of 2011 International Conference on Virtual Reality and Visualization. [S.l.]： ICVRV， 2011： 234?243.

[17] HANQI G， NINGYU M， XIAORU Y. Volume visualization [J]. IEEE Transactions on Visualization and Computer Graphics， 2011， 17（12）： 2106?2114.