楊豪斌, 周 虹
(深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院,廣東 深圳 518060)
一種基于空間距離的邊綁定方法
楊豪斌, 周 虹
(深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院,廣東 深圳 518060)
邊綁定方法是近年來信息可視化領(lǐng)域的一個(gè)研究熱點(diǎn),解決圖可視化中由于邊的過多交叉而引起的視覺混亂問題。在現(xiàn)有的邊綁定方法中,基于路徑構(gòu)建的算法通常能夠在時(shí)間和綁定效果上獲得較好的結(jié)果,其中基于邊聚類和骨架構(gòu)建路徑的方法具有良好的數(shù)據(jù)表達(dá)能力。在此基礎(chǔ)上,提出一種基于空間距離的邊綁定的方法,結(jié)合邊的空間距離和骨架生成的特點(diǎn),在實(shí)現(xiàn)邊綁定功能的同時(shí)針對(duì)以往基于骨架路徑的方法做了進(jìn)一步的改進(jìn)。實(shí)驗(yàn)結(jié)果表明,該方法相比原方法有著更高的時(shí)間效率,對(duì)數(shù)據(jù)的細(xì)節(jié)保留更為合理,消除了原方法存在的綁定過度的問題,簡化原方法的計(jì)算過程,并避免奇異性問題,更為實(shí)用。
邊綁定;邊聚類;圖像骨架算法;圖簡化;信息可視化
圖是信息可視化中一種重要的表現(xiàn)手段,通常以點(diǎn)線圖的形式表示。在應(yīng)對(duì)小規(guī)模數(shù)據(jù)的情況下,點(diǎn)線圖能夠很好地表示數(shù)據(jù)的結(jié)構(gòu)以及彼此之間的關(guān)聯(lián)。但是隨著大數(shù)據(jù)的發(fā)展,可視化所面對(duì)的數(shù)據(jù)規(guī)模也在不斷膨脹,點(diǎn)線圖對(duì)于數(shù)據(jù)的表現(xiàn)能力急劇下降,在眾多邊交叉的情形下,用戶無法辨識(shí)圖中數(shù)據(jù)的關(guān)聯(lián)。為了解決這一問題,邊綁定便應(yīng)運(yùn)而生。邊綁定方法在不減少頂點(diǎn)和邊的前提下,將圖中相似的邊捆綁成束,從而減少邊的交叉與重疊,達(dá)到消除視覺混亂的目的。Telea等[1]所做的用戶研究表明邊綁定是一種有效的方法,其能夠幫助用戶更好地分析數(shù)據(jù)。第一種實(shí)用的邊綁定方法是Holten[2]提出的,但是只針對(duì)具有層次結(jié)構(gòu)的數(shù)據(jù)。適用于普通圖類型數(shù)據(jù)的邊綁定方法是由Cui等[3]首先提出的基于幾何的邊綁定(geometry-based edge bundling, GBEB),其使用稱為控制網(wǎng)格的方法將邊綁定到網(wǎng)格路徑上。與GBEB類似的基于網(wǎng)格模型的邊綁定方法(w inding roads, WR)是Lambert等[4]提出的,WR方法與GBEB的不同之處在于其使用維諾圖及四分樹來生成網(wǎng)格,而 GBEB則通過手動(dòng)或自動(dòng)生成的控制點(diǎn)來產(chǎn)生網(wǎng)格。GBEB和WR模型能夠得出較好的綁定結(jié)果,但在數(shù)據(jù)的表現(xiàn)層級(jí)上較差,無法呈現(xiàn)復(fù)雜程度不同的結(jié)果,缺乏數(shù)據(jù)表現(xiàn)的伸縮性。Holten和Wijk[5]提出的力導(dǎo)向邊綁定方法(force-directed edge bundling, FDEB),基于簡單的力學(xué)模型,有易于實(shí)現(xiàn)的優(yōu)點(diǎn)。姚中華等[6]在力導(dǎo)向模型基礎(chǔ)上,從邊和群組兩個(gè)層次對(duì)網(wǎng)絡(luò)圖的可視化進(jìn)行了優(yōu)化,但總體上基于力導(dǎo)向的算法具有 O(n2)的時(shí)間復(fù)雜度,在時(shí)間效率上表現(xiàn)較差,并且也存在著伸縮性較差的缺點(diǎn)。由Gansner等[7]提出的多層級(jí)聚合邊綁 定 (multilevel agglomerative edge bundling, MAEB)是一種具有良好伸縮性的方法,其可通過不同的遞歸次數(shù)表現(xiàn)不同的數(shù)據(jù)層級(jí),但其對(duì)圖的簡化效果較差,在多次遞歸的情況下依然存在較多的邊交叉。Ersoy等[8]提出的基于骨架的邊綁定方法(skeleton-based edge bundling, SBEB),其通過生成骨架來構(gòu)建邊的綁定路徑。SBEB的計(jì)算模型較為復(fù)雜,并且在較高迭代次數(shù)的情形下存在著綁定過度的問題,但SBEB同時(shí)具備了良好的數(shù)據(jù)表現(xiàn)伸縮性以及對(duì)圖的簡化效果?;赟BEB方法的這些優(yōu)點(diǎn),本文主要針對(duì)SBEB方法存在的問題加以改進(jìn),以期在保留良好的數(shù)據(jù)表現(xiàn)能力的同時(shí),進(jìn)一步簡化模型的計(jì)算流程,提高時(shí)間效率。
給定一個(gè)點(diǎn)線圖 G=(V,E)(本文假設(shè)圖G為二維無向圖,并且頂點(diǎn)集V和邊集E的數(shù)據(jù)是給定的),SBEB方法的計(jì)算流程如圖1所示,詳細(xì)的實(shí)現(xiàn)過程參閱文獻(xiàn)[7]。
SBEB方法的主要步驟為邊聚類、形狀構(gòu)造和邊綁定,以及這3個(gè)部分的迭代過程。
圖1 基于骨架的邊綁定計(jì)算流程
其中邊聚類主要是將方向相似,空間距離接近的邊分為一類。文獻(xiàn)[7]中所提出的聚類算法,在針對(duì)直線邊的時(shí)候能夠較有效地對(duì)邊進(jìn)行聚類,然而隨著迭代次數(shù)的增加,聚類個(gè)數(shù)減少,邊變?yōu)榍€,其聚類方法的效果變得較差,通常會(huì)將本來方向和空間距離差異較大的邊分在一類,從而導(dǎo)致數(shù)據(jù)分析的歧義。形狀構(gòu)造部分將圖的布局結(jié)果像素化,然后通過圖像骨架提取算法[9-11]提取出作為邊綁定部分使用的路徑。在邊綁定上,由于骨架算法本身的特點(diǎn),在將邊上的采樣點(diǎn)對(duì)應(yīng)到骨架路徑上的時(shí)候,可能存在兩個(gè)對(duì)應(yīng)的骨架路徑點(diǎn),也即邊的采樣點(diǎn)剛好落到維諾圖的路徑上(奇異性問題)。SBEB方法通過對(duì)角度判斷來消除奇異性問題,然而在實(shí)現(xiàn)過程,對(duì)于角度大小的指定會(huì)影響奇異性的判斷,出現(xiàn)誤判的可能性較大。后期處理部分主要是對(duì)綁定結(jié)果進(jìn)行諸如邊的平滑等操作,以增強(qiáng)結(jié)果的可讀性和美觀度。迭代次數(shù)是影響算法時(shí)間效率的關(guān)鍵點(diǎn),在保證綁定效果的前提下盡可能地減少迭代次數(shù)能夠使整個(gè)算法的時(shí)間效率成倍地提高,從而使得算法具有更好的實(shí)時(shí)性。
針對(duì)SBEB存在的邊綁定歧義、時(shí)間效率和奇異性問題,本文提出了一種基于邊的空間距離的新方法。新方法不依賴于通過聚類算法對(duì)邊進(jìn)行相似性判斷并將其綁定在一起,而是通過判斷邊的采樣點(diǎn)到骨架的距離是否小于一定的閾值作為綁定的依據(jù)。在迭代過程中不斷將邊和骨架的空間位置進(jìn)行擬合,以使最終的綁定結(jié)果最大程度地符合原圖中邊的分布模式。
SBEB方法依靠聚類實(shí)現(xiàn)對(duì)相似邊的綁定,基于空間距離的方法則在綁定的過程中進(jìn)行判斷,當(dāng)邊的采樣點(diǎn)與骨架路徑的距離小于閾值θ時(shí),才將采樣點(diǎn)綁定到骨架路徑上,其過程如圖2所示。隨著迭代過程,邊的綁定從外圍逐漸深入到內(nèi)部,直到所有邊的采樣點(diǎn)與骨架路徑的距離 S都小于θ時(shí),完成對(duì)邊的綁定過程。此過程中,邊的分布模式和綁定結(jié)果不斷地引導(dǎo)骨架路徑的生成,最終使得生成的骨架路徑很好地?cái)M合了邊的空間分布模式,而綁定到骨架上的邊便能夠很好地表現(xiàn)出原圖的分布模式。依據(jù)此思想,下面具體說明本文方法主要步驟的實(shí)現(xiàn)過程,其計(jì)算流程如圖2所示。
圖2 基于空間距離的邊綁定算法流程
2.1 邊聚類
SBEB方法通過在迭代過程中線性減少層次聚類的劃分因子δ來減少聚類個(gè)數(shù),以達(dá)到最終用戶指定的聚類個(gè)數(shù),本文方法并不以聚類來判斷邊的相似性,因此無需在迭代過程中進(jìn)行聚類,但是為了保證綁定的效果,依然需要對(duì)邊進(jìn)行聚類(聚類劃分的區(qū)域越多,生成的骨架路徑也越大,綁定結(jié)果中邊的扭曲度越小,綁定結(jié)果將更符合原圖的分布)。在迭代之前進(jìn)行一次聚類,直接將邊劃分為用戶指定的聚類個(gè)數(shù),并且對(duì)于聚類的效果不敏感,因此可以充分簡化聚類模型。本文方法使用開源的聚類框架[12],并且使用時(shí)間復(fù)雜度較低的K-means聚類而非原文使用的層次聚類。每條邊的特征向量定義為 v=(xs,ys,xe,ye),其中xs、ys為邊的始點(diǎn)坐標(biāo), xe、 ye為邊的終點(diǎn)坐標(biāo),同時(shí)相似性度量函數(shù)定義為歐拉距離函數(shù):
其中,v、w表示邊的特征向量,N表示特征向量的維度,即邊的采樣點(diǎn)數(shù)目。對(duì)于 K-means的聚類個(gè)數(shù) K值,可根據(jù)圖的復(fù)雜程度和用戶所需的綁定層級(jí)設(shè)定。
2.2 邊綁定
SBEB方法的邊綁定計(jì)算公式見式(2),具體可參閱文獻(xiàn)[7]中的式(7)。
其中,x表示當(dāng)前的坐標(biāo)位置, xnew表示新的坐標(biāo)位置,α用于控制綁定的松緊程度,λ(x)表示從曲線起點(diǎn)到當(dāng)前坐標(biāo)位置x的弧長。φ(t)=[2m in(t,1-t)]K(K∈[3,6])控制曲線起始點(diǎn)的位置不變,并且使得越靠近曲線中間部分的采樣點(diǎn)移動(dòng)的越多。 FTS(x)為x的特征變換(feature transform)距離。
SBEB方法主要通過邊的平流因子(advection factor)α來控制綁定的聚合速度,α隨著迭代次數(shù)線性減少,較小的α值使得綁定過程邊更好地?cái)M合聚類模式,但需要更多的迭代次數(shù),較大的α值能夠加快綁定過程并使得邊的綁定更靠緊骨架,但是在簡化較為復(fù)雜的圖時(shí)自由度受到限制。
在 SBEB方法中,邊的綁定效果與α值有較大關(guān)聯(lián),原文中將α值根據(jù)迭代次數(shù)從0.9線性減少到0.2,但實(shí)踐中發(fā)現(xiàn)α值與具體的圖布局有很大關(guān)系,不同的圖布局在采用相同α設(shè)置的時(shí)候,綁定效果有較大差別,因此實(shí)際過程中α需要根據(jù)不同的圖布局進(jìn)行設(shè)置。為了避免α的設(shè)置,基于空間距離的方法不使用α來控制綁定的聚合速度,而是通過邊的采樣點(diǎn)與骨架路徑的距離θ來控制聚合速度。采樣點(diǎn)與骨架的距離不會(huì)因?yàn)椴煌膱D布局而有所變化,其具有統(tǒng)一性,從而防止了SBEB方法中針對(duì)α的復(fù)雜設(shè)定。θ的初始值定義為圖布局包圍盒的長寬和均值的 0.01,并且隨著迭代次數(shù)線性增長。θ根據(jù)迭代次數(shù)線性增長是因?yàn)殡S著迭代次數(shù)的增加,邊與骨架的擬合程度也越來越高,因此在每次迭代之后適當(dāng)增加θ值可以有效減少迭代次數(shù),提高整體效率。θ同時(shí)也作為采樣點(diǎn)是否綁定到骨架路徑的依據(jù),如圖3(a)所示,只有當(dāng)前的采樣點(diǎn)和對(duì)應(yīng)的骨架點(diǎn)距離 S小于θ時(shí),才進(jìn)行綁定。θ計(jì)算公式見式(3)。
其中,i表示當(dāng)前迭代次數(shù),0θ表示θ的初始值,h為圖布局包圍盒的高,w為圖布局包圍盒的寬。φ為控制聚合速度的因子,φ值越大,迭代過程中iθ越小,邊與骨架的擬合度也越高,但是相應(yīng)增加了迭代次數(shù)。經(jīng)過多次的試驗(yàn),φ在[4,10]的區(qū)間內(nèi)能得到較好的結(jié)果。由于本文方法不使用α值來控制聚合速度,因此可將α設(shè)為定值0.9。
2.3 迭代過程
從圖1和圖2可以看到,迭代過程包含了幾個(gè)關(guān)鍵的計(jì)算步驟,減少迭代次數(shù)I能夠有效地提高算法的時(shí)間效率,在文獻(xiàn)[7]中,迭代次數(shù)I通常設(shè)定在[10,15]之間,以使綁定達(dá)到好的結(jié)果。本文方法通過θ控制邊綁定的聚合速度,同樣也影響到迭代次數(shù)I上,θ值越大,所需的迭代次數(shù)I越少,但是過大的θ值將使邊與骨架路徑的擬合程度變差。假使θ如式(3)所示的設(shè)定,在實(shí)際實(shí)現(xiàn)過程中迭代次數(shù)I在[5,8]之間便能夠得到很好的綁定效果,也即本文方法所需的迭代次數(shù)能夠比SBEB方法減少一半左右,并且對(duì)于邊的聚類只需進(jìn)行一次,極大地提高了整體時(shí)間效率。圖3(b)展示了新方法一次迭代之后的結(jié)果。
圖3 一次迭代之后的綁定結(jié)果(紅色部分為骨架路徑)
奇異性問題來源于骨架算法的特點(diǎn),骨架路徑上可能存在 2個(gè)不同的坐標(biāo)點(diǎn)對(duì)應(yīng)于一個(gè)非骨架路徑上的點(diǎn),而在邊綁定過程中,某個(gè)邊的采樣點(diǎn)可能就對(duì)應(yīng)兩個(gè)骨架路徑點(diǎn),從而導(dǎo)致在綁定過程中曲線邊上出現(xiàn)急劇的直線跳躍,使得曲線邊不夠光滑,如圖4(a)中的紅色部分所示。
解決奇異性問題可從2個(gè)方面進(jìn)行:①保證在綁定過程中一條邊只對(duì)應(yīng)于一條路徑,而不以所有路徑中與邊采樣點(diǎn)距離最近的點(diǎn)為基準(zhǔn),此方面確使一條邊對(duì)應(yīng)一條路徑,不出現(xiàn)一條邊在多條路徑上跳躍的情況;②即使保證了一條邊只對(duì)應(yīng)于一條路徑,也可能出現(xiàn)奇異性問題,如圖4(a)中的P點(diǎn)。為了解決這個(gè)問題,文獻(xiàn)[7]提供了一種角度判斷的方法,如圖4(a)所示,如果角度大于某個(gè)設(shè)定的閾值β,即判斷此處出現(xiàn)奇異性問題,此種解法需要用戶指定β的大小,然而在實(shí)現(xiàn)過程中固定的β值并不能很好地判斷所有的奇異性問題。為了更好地解決此問題,本文改變了邊綁定的流程,如圖4(b),通過在骨架路徑上進(jìn)行采樣,并計(jì)算出路徑采樣點(diǎn)所對(duì)應(yīng)的邊的采樣點(diǎn),從而在根本上避免了奇異性問題的產(chǎn)生。新流程的計(jì)算過程分為2個(gè)步驟:①根據(jù)邊的端點(diǎn)計(jì)算出對(duì)應(yīng)的骨架路徑,此路徑所對(duì)應(yīng)的是完整路徑的一部分,也即子路徑;②通過對(duì)子路徑進(jìn)行均勻采樣,再計(jì)算出子路徑采樣點(diǎn)所對(duì)應(yīng)的邊的采樣點(diǎn),從而計(jì)算出新的邊采樣點(diǎn)的坐標(biāo)。通過對(duì)于流程的調(diào)整,既解決了奇異性問題,又簡化了算法的實(shí)現(xiàn)復(fù)雜度,增強(qiáng)了穩(wěn)定性。
圖4 奇異性問題
實(shí)驗(yàn)的硬件設(shè)備和軟件配置主要為:Intel(R) Core(TM) i3-3110M CPU 2.40 GHz,內(nèi)存為8 GB,顯卡為 NVIDIA GeForce GT 630 M,64-bit Windows 7 Professional 操作系統(tǒng),Visual Studio 2010開發(fā)平臺(tái),C++與OpenGL。
本文的數(shù)據(jù)來源于文獻(xiàn)[3-5]和文獻(xiàn)[7-8],分別為美國西北航空線路圖、美國遷移數(shù)據(jù)圖和撲克玩家關(guān)系圖。實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)如表 1所示。從表 1的實(shí)驗(yàn)結(jié)果可以看出,由于有效地簡化了計(jì)算模型和減少了迭代次數(shù),本文方法在時(shí)間效率上有了較大的提升。
從圖 5的結(jié)果對(duì)比來看,本文方法在實(shí)現(xiàn)了圖簡化的同時(shí)保留了更多的數(shù)據(jù)細(xì)節(jié)。以西北航空?qǐng)D為例,對(duì)比圖5(d)、(f)、(h),明顯看出圖5(h)較好地保留了原圖的局部走向,圖5(f)在中間部分和右半部分明顯出現(xiàn)了過度綁定,導(dǎo)致數(shù)據(jù)出現(xiàn)了較大的“失真”。從遷移圖的比較來看,兩種方法效果差別不是很大,但是依然能夠看出圖5(g)在最右部分出現(xiàn)了較明顯的過度綁定,而本文方法則較好地保留了原圖的基本走向。本文方法相比較于 SBEB方法更好地解決了由于數(shù)據(jù)規(guī)模引起的視覺混亂和數(shù)據(jù)表達(dá)之間的矛盾。
表1 數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果
圖5 SBEB方法與本文方法結(jié)果對(duì)比
本文主要基于SBEB方法中骨架路徑的思想,并從圖布局的空間距離考慮,提出了一種新的邊綁定方法。同時(shí)針對(duì) SBEB方法出現(xiàn)的奇異性問題,對(duì)邊的綁定流程進(jìn)行了調(diào)整,避免了對(duì)參數(shù)的設(shè)定,有效地簡化算法的實(shí)現(xiàn)復(fù)雜度。本文方法也存在一些不足,為了減少迭代次數(shù),隨著迭代次數(shù)的增加,θ呈線性增長,會(huì)在一定程度上影響邊與骨架的擬合程度。從綁定結(jié)果上,在相同的聚類數(shù)目下,本文方法能夠有效地對(duì)邊進(jìn)行綁定,并且保留更多的細(xì)節(jié),在減輕圖的視覺混亂和數(shù)據(jù)的呈現(xiàn)上做到了較好的平衡,但是從美學(xué)上,本文方法的表現(xiàn)結(jié)果要比SBEB稍差??傮w上來說,基于空間距離的方法有著更高的時(shí)間效率和更低的實(shí)現(xiàn)難度,是一種有效的方法。
[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] 姚中華, 吳玲達(dá), 宋漢辰. 網(wǎng)絡(luò)圖中邊集束優(yōu)化問題[J]. 北京航空航天大學(xué)學(xué)報(bào), 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]. 計(jì)算機(jī)應(yīng)用, 2005, 6(6): 1305-1306.
[11] 楊志平, 齊清文, 黃仁濤. 數(shù)學(xué)形態(tài)學(xué)在空間格局圖像骨架提取中的應(yīng)用[J]. 地球信息科學(xué), 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
國家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61103055)
楊豪斌(1988–),男,廣東普寧人,碩士研究生。主要研究方向?yàn)樾畔⒖梢暬?。E-mail:haobinyang1988@163.com
周 虹(1982–),女,湖南長沙人,講師,博士。主要研究方向?yàn)樾畔⒖梢暬涂梢暦治觥-mail:hzhou@szu.edu.cn