一種基于空間距離的邊綁定方法

楊豪斌， 周 虹

(深圳大學計算機與軟件學院，廣東 深圳 518060)

一種基于空間距離的邊綁定方法

楊豪斌， 周 虹

(深圳大學計算機與軟件學院，廣東 深圳 518060)

邊綁定方法是近年來信息可視化領域的一個研究熱點，解決圖可視化中由于邊的過多交叉而引起的視覺混亂問題。在現有的邊綁定方法中，基于路徑構建的算法通常能夠在時間和綁定效果上獲得較好的結果，其中基于邊聚類和骨架構建路徑的方法具有良好的數據表達能力。在此基礎上，提出一種基于空間距離的邊綁定的方法，結合邊的空間距離和骨架生成的特點，在實現邊綁定功能的同時針對以往基于骨架路徑的方法做了進一步的改進。實驗結果表明，該方法相比原方法有著更高的時間效率，對數據的細節保留更為合理，消除了原方法存在的綁定過度的問題，簡化原方法的計算過程，并避免奇異性問題，更為實用。

邊綁定；邊聚類；圖像骨架算法；圖簡化；信息可視化

圖是信息可視化中一種重要的表現手段，通常以點線圖的形式表示。在應對小規模數據的情況下，點線圖能夠很好地表示數據的結構以及彼此之間的關聯。但是隨著大數據的發展，可視化所面對的數據規模也在不斷膨脹，點線圖對于數據的表現能力急劇下降，在眾多邊交叉的情形下，用戶無法辨識圖中數據的關聯。為了解決這一問題，邊綁定便應運而生。邊綁定方法在不減少頂點和邊的前提下，將圖中相似的邊捆綁成束，從而減少邊的交叉與重疊，達到消除視覺混亂的目的。Telea等[1]所做的用戶研究表明邊綁定是一種有效的方法，其能夠幫助用戶更好地分析數據。第一種實用的邊綁定方法是Holten[2]提出的，但是只針對具有層次結構的數據。適用于普通圖類型數據的邊綁定方法是由Cui等[3]首先提出的基于幾何的邊綁定(geometry-based edge bundling, GBEB)，其使用稱為控制網格的方法將邊綁定到網格路徑上。與GBEB類似的基于網格模型的邊綁定方法(w inding roads, WR)是Lambert等[4]提出的，WR方法與GBEB的不同之處在于其使用維諾圖及四分樹來生成網格，而 GBEB則通過手動或自動生成的控制點來產生網格。GBEB和WR模型能夠得出較好的綁定結果，但在數據的表現層級上較差，無法呈現復雜程度不同的結果，缺乏數據表現的伸縮性。Holten和Wijk[5]提出的力導向邊綁定方法(force-directed edge bundling, FDEB)，基于簡單的力學模型，有易于實現的優點。姚中華等[6]在力導向模型基礎上，從邊和群組兩個層次對網絡圖的可視化進行了優化，但總體上基于力導向的算法具有 O(n2)的時間復雜度，在時間效率上表現較差，并且也存在著伸縮性較差的缺點。由Gansner等[7]提出的多層級聚合邊綁 定 (multilevel agglomerative edge bundling, MAEB)是一種具有良好伸縮性的方法，其可通過不同的遞歸次數表現不同的數據層級，但其對圖的簡化效果較差，在多次遞歸的情況下依然存在較多的邊交叉。Ersoy等[8]提出的基于骨架的邊綁定方法(skeleton-based edge bundling, SBEB)，其通過生成骨架來構建邊的綁定路徑。SBEB的計算模型較為復雜，并且在較高迭代次數的情形下存在著綁定過度的問題，但SBEB同時具備了良好的數據表現伸縮性以及對圖的簡化效果。基于SBEB方法的這些優點，本文主要針對SBEB方法存在的問題加以改進，以期在保留良好的數據表現能力的同時，進一步簡化模型的計算流程，提高時間效率。

1 基于骨架的邊綁定

給定一個點線圖 G=(V,E)(本文假設圖G為二維無向圖，并且頂點集V和邊集E的數據是給定的)，SBEB方法的計算流程如圖1所示，詳細的實現過程參閱文獻[7]。

SBEB方法的主要步驟為邊聚類、形狀構造和邊綁定，以及這3個部分的迭代過程。

圖1 基于骨架的邊綁定計算流程

其中邊聚類主要是將方向相似，空間距離接近的邊分為一類。文獻[7]中所提出的聚類算法，在針對直線邊的時候能夠較有效地對邊進行聚類，然而隨著迭代次數的增加，聚類個數減少，邊變為曲線，其聚類方法的效果變得較差，通常會將本來方向和空間距離差異較大的邊分在一類，從而導致數據分析的歧義。形狀構造部分將圖的布局結果像素化，然后通過圖像骨架提取算法[9-11]提取出作為邊綁定部分使用的路徑。在邊綁定上，由于骨架算法本身的特點，在將邊上的采樣點對應到骨架路徑上的時候，可能存在兩個對應的骨架路徑點，也即邊的采樣點剛好落到維諾圖的路徑上(奇異性問題)。SBEB方法通過對角度判斷來消除奇異性問題，然而在實現過程，對于角度大小的指定會影響奇異性的判斷，出現誤判的可能性較大。后期處理部分主要是對綁定結果進行諸如邊的平滑等操作，以增強結果的可讀性和美觀度。迭代次數是影響算法時間效率的關鍵點，在保證綁定效果的前提下盡可能地減少迭代次數能夠使整個算法的時間效率成倍地提高，從而使得算法具有更好的實時性。

針對SBEB存在的邊綁定歧義、時間效率和奇異性問題，本文提出了一種基于邊的空間距離的新方法。新方法不依賴于通過聚類算法對邊進行相似性判斷并將其綁定在一起，而是通過判斷邊的采樣點到骨架的距離是否小于一定的閾值作為綁定的依據。在迭代過程中不斷將邊和骨架的空間位置進行擬合，以使最終的綁定結果最大程度地符合原圖中邊的分布模式。

2 基于空間距離的邊綁定

SBEB方法依靠聚類實現對相似邊的綁定，基于空間距離的方法則在綁定的過程中進行判斷，當邊的采樣點與骨架路徑的距離小于閾值θ時，才將采樣點綁定到骨架路徑上，其過程如圖2所示。隨著迭代過程，邊的綁定從外圍逐漸深入到內部，直到所有邊的采樣點與骨架路徑的距離 S都小于θ時，完成對邊的綁定過程。此過程中，邊的分布模式和綁定結果不斷地引導骨架路徑的生成，最終使得生成的骨架路徑很好地擬合了邊的空間分布模式，而綁定到骨架上的邊便能夠很好地表現出原圖的分布模式。依據此思想，下面具體說明本文方法主要步驟的實現過程，其計算流程如圖2所示。

圖2 基于空間距離的邊綁定算法流程

2.1 邊聚類

SBEB方法通過在迭代過程中線性減少層次聚類的劃分因子δ來減少聚類個數，以達到最終用戶指定的聚類個數，本文方法并不以聚類來判斷邊的相似性，因此無需在迭代過程中進行聚類，但是為了保證綁定的效果，依然需要對邊進行聚類(聚類劃分的區域越多，生成的骨架路徑也越大，綁定結果中邊的扭曲度越小，綁定結果將更符合原圖的分布)。在迭代之前進行一次聚類，直接將邊劃分為用戶指定的聚類個數，并且對于聚類的效果不敏感，因此可以充分簡化聚類模型。本文方法使用開源的聚類框架[12]，并且使用時間復雜度較低的K-means聚類而非原文使用的層次聚類。每條邊的特征向量定義為 v=(xs,ys,xe,ye)，其中xs、ys為邊的始點坐標， xe、 ye為邊的終點坐標，同時相似性度量函數定義為歐拉距離函數：

其中，v、w表示邊的特征向量，N表示特征向量的維度，即邊的采樣點數目。對于 K-means的聚類個數 K值，可根據圖的復雜程度和用戶所需的綁定層級設定。

2.2 邊綁定

SBEB方法的邊綁定計算公式見式(2)，具體可參閱文獻[7]中的式(7)。

其中，x表示當前的坐標位置， xnew表示新的坐標位置，α用于控制綁定的松緊程度，λ（x）表示從曲線起點到當前坐標位置x的弧長。φ（t）=［2m in(t,1-t)］K(K∈[3,6])控制曲線起始點的位置不變，并且使得越靠近曲線中間部分的采樣點移動的越多。 FTS（x）為x的特征變換(feature transform)距離。

SBEB方法主要通過邊的平流因子(advection factor)α來控制綁定的聚合速度，α隨著迭代次數線性減少，較小的α值使得綁定過程邊更好地擬合聚類模式，但需要更多的迭代次數，較大的α值能夠加快綁定過程并使得邊的綁定更靠緊骨架，但是在簡化較為復雜的圖時自由度受到限制。

在 SBEB方法中，邊的綁定效果與α值有較大關聯，原文中將α值根據迭代次數從0.9線性減少到0.2，但實踐中發現α值與具體的圖布局有很大關系，不同的圖布局在采用相同α設置的時候，綁定效果有較大差別，因此實際過程中α需要根據不同的圖布局進行設置。為了避免α的設置，基于空間距離的方法不使用α來控制綁定的聚合速度，而是通過邊的采樣點與骨架路徑的距離θ來控制聚合速度。采樣點與骨架的距離不會因為不同的圖布局而有所變化，其具有統一性，從而防止了SBEB方法中針對α的復雜設定。θ的初始值定義為圖布局包圍盒的長寬和均值的 0.01，并且隨著迭代次數線性增長。θ根據迭代次數線性增長是因為隨著迭代次數的增加，邊與骨架的擬合程度也越來越高，因此在每次迭代之后適當增加θ值可以有效減少迭代次數，提高整體效率。θ同時也作為采樣點是否綁定到骨架路徑的依據，如圖3(a)所示，只有當前的采樣點和對應的骨架點距離 S小于θ時，才進行綁定。θ計算公式見式(3)。

其中，i表示當前迭代次數，0θ表示θ的初始值，h為圖布局包圍盒的高，w為圖布局包圍盒的寬。φ為控制聚合速度的因子，φ值越大，迭代過程中iθ越小，邊與骨架的擬合度也越高，但是相應增加了迭代次數。經過多次的試驗，φ在[4,10]的區間內能得到較好的結果。由于本文方法不使用α值來控制聚合速度，因此可將α設為定值0.9。

2.3 迭代過程

從圖1和圖2可以看到，迭代過程包含了幾個關鍵的計算步驟，減少迭代次數I能夠有效地提高算法的時間效率，在文獻[7]中，迭代次數I通常設定在[10,15]之間，以使綁定達到好的結果。本文方法通過θ控制邊綁定的聚合速度，同樣也影響到迭代次數I上，θ值越大，所需的迭代次數I越少，但是過大的θ值將使邊與骨架路徑的擬合程度變差。假使θ如式(3)所示的設定，在實際實現過程中迭代次數I在[5,8]之間便能夠得到很好的綁定效果，也即本文方法所需的迭代次數能夠比SBEB方法減少一半左右，并且對于邊的聚類只需進行一次，極大地提高了整體時間效率。圖3(b)展示了新方法一次迭代之后的結果。

圖3 一次迭代之后的綁定結果(紅色部分為骨架路徑)

3 奇異性問題

奇異性問題來源于骨架算法的特點，骨架路徑上可能存在 2個不同的坐標點對應于一個非骨架路徑上的點，而在邊綁定過程中，某個邊的采樣點可能就對應兩個骨架路徑點，從而導致在綁定過程中曲線邊上出現急劇的直線跳躍，使得曲線邊不夠光滑，如圖4(a)中的紅色部分所示。

解決奇異性問題可從2個方面進行：①保證在綁定過程中一條邊只對應于一條路徑，而不以所有路徑中與邊采樣點距離最近的點為基準，此方面確使一條邊對應一條路徑，不出現一條邊在多條路徑上跳躍的情況；②即使保證了一條邊只對應于一條路徑，也可能出現奇異性問題，如圖4(a)中的P點。為了解決這個問題，文獻[7]提供了一種角度判斷的方法，如圖4(a)所示，如果角度大于某個設定的閾值β，即判斷此處出現奇異性問題，此種解法需要用戶指定β的大小，然而在實現過程中固定的β值并不能很好地判斷所有的奇異性問題。為了更好地解決此問題，本文改變了邊綁定的流程，如圖4(b)，通過在骨架路徑上進行采樣，并計算出路徑采樣點所對應的邊的采樣點，從而在根本上避免了奇異性問題的產生。新流程的計算過程分為2個步驟：①根據邊的端點計算出對應的骨架路徑，此路徑所對應的是完整路徑的一部分，也即子路徑；②通過對子路徑進行均勻采樣，再計算出子路徑采樣點所對應的邊的采樣點，從而計算出新的邊采樣點的坐標。通過對于流程的調整，既解決了奇異性問題，又簡化了算法的實現復雜度，增強了穩定性。

圖4 奇異性問題

4 實驗結果和分析

實驗的硬件設備和軟件配置主要為：Intel(R) Core(TM) i3-3110M CPU 2.40 GHz，內存為8 GB，顯卡為 NVIDIA GeForce GT 630 M，64-bit Windows 7 Professional 操作系統，Visual Studio 2010開發平臺，C++與OpenGL。

本文的數據來源于文獻[3-5]和文獻[7-8]，分別為美國西北航空線路圖、美國遷移數據圖和撲克玩家關系圖。實驗的統計數據如表 1所示。從表 1的實驗結果可以看出，由于有效地簡化了計算模型和減少了迭代次數，本文方法在時間效率上有了較大的提升。

從圖 5的結果對比來看，本文方法在實現了圖簡化的同時保留了更多的數據細節。以西北航空圖為例，對比圖5(d)、(f)、(h)，明顯看出圖5(h)較好地保留了原圖的局部走向，圖5(f)在中間部分和右半部分明顯出現了過度綁定，導致數據出現了較大的“失真”。從遷移圖的比較來看，兩種方法效果差別不是很大，但是依然能夠看出圖5(g)在最右部分出現了較明顯的過度綁定，而本文方法則較好地保留了原圖的基本走向。本文方法相比較于 SBEB方法更好地解決了由于數據規模引起的視覺混亂和數據表達之間的矛盾。

表1 數據集的實驗結果

圖5 SBEB方法與本文方法結果對比

5 結 束 語

本文主要基于SBEB方法中骨架路徑的思想，并從圖布局的空間距離考慮，提出了一種新的邊綁定方法。同時針對 SBEB方法出現的奇異性問題，對邊的綁定流程進行了調整，避免了對參數的設定，有效地簡化算法的實現復雜度。本文方法也存在一些不足，為了減少迭代次數，隨著迭代次數的增加，θ呈線性增長，會在一定程度上影響邊與骨架的擬合程度。從綁定結果上，在相同的聚類數目下，本文方法能夠有效地對邊進行綁定，并且保留更多的細節，在減輕圖的視覺混亂和數據的呈現上做到了較好的平衡，但是從美學上，本文方法的表現結果要比SBEB稍差。總體上來說，基于空間距離的方法有著更高的時間效率和更低的實現難度，是一種有效的方法。

[1] Telea A, Ersoy O, Hoogendorp H, et al. Comparison of nodelLink and hierarchical edge bundling layouts: a user study [C/OL]//Dagstuhl Seminar Proceedings 09211: Visualization and Monitoring of Network Traffic. [2015-04-15]. http://drops.dagstuhl.de/protals/index.php? semnr=09211.

[2] Holten D. Hierarchical edge bundles: visualization of adjacency relations in hierarchical data [J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(5): 741-748.

[3] Cui W W, Zhou H, Qu H M, et al. Geometry-based edge clustering for graph visualization [J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(6): 1277-1284.

[4] Lambert A, Bourqui R, Auber D. Winding roads: routing edges into bundles [J]. Computer Graphics Forum, 2010, 29(3): 853-862.

[5] Holten D, Wijk J J V. Force-directed edge bundling for graph visualization [J]. Computer Graphics Forum, 2009, 28(3): 983-990.

[6] 姚中華, 吳玲達, 宋漢辰. 網絡圖中邊集束優化問題[J]. 北京航空航天大學學報, 2015, 41(5): 871-878.

[7] Gansner E R, Hu Y, North S, et al. Multilevel agglomerative edge bundling for visualizing large graphs [C]//In Proceedings of IEEE Pacific Visualization Symposium. Washington: IEEE Computer Society, 2011: 187-194.

[8] Ersoy O, Hurter C, Paulovich F V, et al. Skeleton-based edge bundling for graph visualization [J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(12): 2364-2373.

[9] Telea A, Van Wijk J J. An augmented fast marching method for computing skeletons and centerlines [C]//In Proceedings of the symposium on Data Visualisation 2002. Aire?La?Ville: Eurographics Association, 2002: 251-259.

[10] 趙春江, 施文康, 鄧 勇. 具有魯棒性的圖像骨架提取方法[J]. 計算機應用, 2005, 6(6): 1305-1306.

[11] 楊志平, 齊清文, 黃仁濤. 數學形態學在空間格局圖像骨架提取中的應用[J]. 地球信息科學, 2003, 2(2): 79-83.

[12] Hoon M D, Imoto S, Nolan J, et al. Open source clustering software [J]. Bioinformatics, 2004, 20(9): 1453-1454.

A Distance-Based Edge-Bundling Method

Yang Haobin, Zhou Hong

(College of Computer Science & Software Engineering, Shenzhen University, Shenzhen Guangdong 518060, China)

Edge bundling has become a research hotspot in the field of information visualization. The edge-bundling methods address the visual clutter problem caused by extensive edge crossings in graphs. Among the recent edge-bundling methods, the algorithms which are based on the path construction are generally efficient and have good bundling results, the algorithms which are based on edge clustering and the skeleton construction can effectively reveal underlying patterns. Based on these works, a distance-based edge-bundling method is presented, with the features of space distances and skeletons, which can improve the edge-bundling results generated by the skeleton-based edge-bundling method. The experiment results demonstrate that the distance-based method is efficient and effective in pattern revealing, so that this method can avoid the over bundling problem of the previous one. In summary, this method is a practical one that can simplify the computing process and avoid the singularity problem.

edge bundling; edge clustering; skeleton-based algorithm; graph visualization; information visualization

TP 301.6

10.11996/JG.j.2095-302X.2016030296

A

2095-302X(2016)03-0296-06

2015-09-28；定稿日期：2015-12-01

國家自然科學基金青年科學基金項目(61103055)

楊豪斌(1988–)，男，廣東普寧人，碩士研究生。主要研究方向為信息可視化。E-mail：haobinyang1988@163.com

周 虹(1982–)，女，湖南長沙人，講師，博士。主要研究方向為信息可視化和可視分析。E-mail：hzhou@szu.edu.cn