（1.武漢工程大學(xué)智能機器人湖北省重點實驗室，湖北 武漢 430074；

2.武漢基華電腦系統(tǒng)有限公司，湖北 武漢 430074）

層次信息可視化集成技術(shù)的應(yīng)用

（1.武漢工程大學(xué)智能機器人湖北省重點實驗室，湖北 武漢 430074；

2.武漢基華電腦系統(tǒng)有限公司，湖北 武漢 430074）

層次信息可視化有多種方法，雙曲樹方法能在有限的空間中顯示結(jié)構(gòu)龐大的層次信息，氣泡樹方法能清晰地顯示用戶關(guān)注的局部信息.在分析了雙曲樹和氣泡樹特點之后，提出將傳統(tǒng)的目錄樹結(jié)構(gòu)轉(zhuǎn)換成雙曲樹結(jié)構(gòu)和氣泡樹結(jié)構(gòu)，經(jīng)過視圖變換和可視化控制，形成目錄樹與雙曲樹、氣泡樹集成的可視化技術(shù)，并將這種集成技術(shù)應(yīng)用到多維、多層數(shù)據(jù)的城市區(qū)域規(guī)劃系統(tǒng)中，發(fā)揮了目錄樹、雙曲樹的強大功能和氣泡樹的輔助作用，提供了便捷、生動的導(dǎo)航界面.

可視化；目錄樹；雙曲樹；氣泡樹；集成技術(shù)

0 引 言

人們對層次信息可視化深入研究，提出了一系列新的可視化技術(shù)方法，其中，典型的有普通目錄樹型；Robertson，Machkinlay和Card等提出的利用三維圖形技術(shù)對層次結(jié)構(gòu)進行可視化的方法三維圓錐樹 Cone Tree［1］；Shneiderman等提出的一種可以充分利用屏幕空間的層次信息表示模型樹圖 Tree-map［2］；Lamping和 Rao等提出的一種基于雙曲空間的可視化和操縱大型層次結(jié)構(gòu)的Focus＋Contxt技術(shù)，稱為雙曲樹Hyperbolic-tree［3］；Richard Boardman提出 了 將 子節(jié)點用一個個氣泡表示，該氣泡通過包含低一級信息來聚集細節(jié)信息，稱為氣泡樹Bubble trees［4］.三維圓錐樹在表現(xiàn)組織結(jié)構(gòu)圖的時候表現(xiàn)出色，它能把大量的節(jié)點顯示在單一的屏幕中.不足之處在于很難同時看到某個層次的所有內(nèi)容，節(jié)點查詢也比一般的層次信息可視化框架困難.Tree-map的優(yōu)點在于它可以有效利用計算機屏幕空間，并且能夠很容易實現(xiàn)，但它的層次結(jié)構(gòu)不清晰，缺乏直觀性.氣泡樹結(jié)合了Focus＋Contxt技術(shù)，在不同時刻根據(jù)用戶的需要分別顯示全局視圖和細節(jié)視圖，采用回溯機制使用戶能夠正確的回到之前所在的視圖位置.在樹的層次較少的情況下有比較好的效果，對于層次較多的樹會造成頻繁的人機交互，給用戶帶來一定的困擾.雙曲樹利用其特有的幾何特性很好地解決了怎樣在用戶屏幕上顯示龐大的層次信息結(jié)構(gòu)的問題.各種方法都有各自的優(yōu)缺點，人們可以研究出更好的新方法，也可以根據(jù)它們的特點進行綜合運用.安徽工程大學(xué)借助Open GL軟件包實現(xiàn)了三維自然導(dǎo)觀的可視化控制系統(tǒng)［5］.靖培棟［6］在圖書館文獻檢索的可視化研究中，根據(jù)中圖法的特點，集成普通樹型及雙曲樹，取得較好的效果.

1 集成可視化方法

1.1 雙曲樹模型

1.1.1 雙曲空間布局模型 在雙曲空間里，節(jié)點的布局是通過Klein模型［7］來實現(xiàn)的.圖1是基于Klein模型的某節(jié)點和其子節(jié)點的布局示意圖.M1、M2、M3是M 的三個子節(jié)點（如果不是葉節(jié)點，這個子節(jié)點是子樹的父節(jié)點），NMR是扇形區(qū)域.過 M1、M2、M3畫 MN、MN′、MN″的平行線，這樣可以保證子樹不重疊.a1、a2、a3就是子樹所分配 到 的 扇 形 區(qū) 域，a1＝ ∠NMN’，d2＝∠N’MN″，d3＝∠N″MR，即子節(jié)點得到的扇形區(qū)域和父節(jié)點一樣大.以此類推，可得到所有子節(jié)點的布局，扇形區(qū)域的計算方法如下.

設(shè)節(jié)點M 的扇形區(qū)域為（pk，qk），那么第k個子節(jié)點的扇形區(qū)域為

式中：p表示節(jié)點扇形區(qū)域的起始角度，q表示扇形區(qū)域的大小，n為子節(jié)點總數(shù).

圖1 雙曲空間Klein模型布局Fig.1 Klein layout model in hyperbolic space

1.1.2 歐氏空間映射模型 雙曲空間是一個抽象的空間，人們很難直觀的理解，在雙曲空間中完成節(jié)點的布局后，用一種方法將雙曲空間里的布局結(jié)構(gòu)映射到歐氏空間的二維平面上，這種方法是龐萊卡投影法.一般把通過龐萊卡投影得到的圓面稱為龐萊卡圓盤（Poincare Disk）模型［8］.龐萊卡投影算法把雙曲空間某節(jié)點映射到扇形區(qū)域的中心，然后運用遞歸算法將所有節(jié)點、結(jié)構(gòu)按照以上的映射方式從雙曲空間映射到歐幾里德空間里.

1.2 氣泡樹模型

氣泡樹是根據(jù)樹的自然屬性遞歸地將當(dāng)前節(jié)點到子節(jié)點進行分類，每個子節(jié)點用一個氣泡表示，該氣泡通過包含低一級信息來聚集細節(jié)信息，兄弟節(jié)點排列在以子樹根節(jié)點為中心的圓周上.氣泡樹技術(shù)是將可視化空間分配給當(dāng)前關(guān)注的的層以及相鄰的幾層，通過氣泡膨脹將用戶感興趣的層次節(jié)點放大顯示，此時上層節(jié)點包括到根節(jié)點的所有層次節(jié)點都消失了，然后通過氣泡回溯回到之前所在的層.所以氣泡膨脹和氣泡回溯是氣泡樹可視化的兩大關(guān)鍵.

1.2.1 氣泡膨脹 氣泡樹地初始布局是以根節(jié)點為中心，第一層（根節(jié)點為第0層）子節(jié)點均勻分布在以根節(jié)點為圓心的圓周上，第二層子節(jié)點以同樣的方式分布在第一層相應(yīng)的父節(jié)點周圍，第三層以及更深層次的節(jié)點則不顯示.用戶可以點擊感興趣層上的某個節(jié)點，該節(jié)點便成為中心，其子節(jié)點按子節(jié)點個數(shù)平均分配一個圓周的角度，即360°，此時上層節(jié)點包括到根節(jié)點的所有層次節(jié)點都消失了，顯示的是當(dāng)前層到下層的節(jié)點信息.就像是在很多氣泡中一個氣泡膨脹導(dǎo)致另一個氣泡縮小消失一樣.

1.2.2 氣泡回溯 失去了父節(jié)點和根節(jié)點的信息，如何回到之前所在的層呢？氣泡樹技術(shù)采用了回溯機制.氣泡膨脹后，可以通過人機交互回到當(dāng)前中心節(jié)點的上一層以及更上一層，回溯的層數(shù)可以根據(jù)用戶的需求和每一層的節(jié)點數(shù)目設(shè)置，一般為兩到三層.

1.3 層次信息結(jié)構(gòu)及可視化集成

信息可視化集成過程是，先將應(yīng)用領(lǐng)域的層次信息抽象，建立目錄樹信息結(jié)構(gòu)，通過布局形成可視化目錄樹視圖；同時提取普通目錄樹數(shù)據(jù)轉(zhuǎn)換成雙曲樹層次信息結(jié)構(gòu)，然后通過布局映射成雙曲樹視圖，實現(xiàn)層次信息的可視化集成表示如圖2所示.

圖2 可視化集成表示Fig.2 Integrated expression of visualization

1.3.1 領(lǐng)域的層次信息 作為應(yīng)用領(lǐng)域的城市區(qū)域發(fā)展規(guī)劃涉及經(jīng)濟、文化、科技、生態(tài)、環(huán)境等各個方面，是一個典型的復(fù)雜系統(tǒng).該系統(tǒng)的評價指標(biāo)體系看作是一個由相互聯(lián)系的不同層次結(jié)構(gòu)與多個組成的有機整體，既有上下的層次關(guān)系，又有指標(biāo)間的平行關(guān)系，不同的指標(biāo)反映城市和諧發(fā)展的不同側(cè)面，分屬于不同的類別.主要由4大評價維度、10多項評價內(nèi)容、數(shù)十個評價指標(biāo)構(gòu)成.并且，城市的和諧發(fā)展與企業(yè)息息相關(guān)，許多指標(biāo)都牽涉的企業(yè)單位，而每個企業(yè)也有不同的層次和區(qū)域劃分和更細的考察評價指標(biāo).所以，這是一個龐大的數(shù)據(jù)系統(tǒng)，用傳統(tǒng)的目錄樹方法進行表示，往往要多次操作，效率很低.

1.3.2 目錄樹的層次結(jié)構(gòu) 以樹形結(jié)構(gòu)表示領(lǐng)域?qū)哟涡畔⒑晚椖繋熘兴许椖?，按預(yù)設(shè)的行政區(qū)塊（市、區(qū)、鎮(zhèn)、三區(qū)三園等）逐級表示（見圖3）.

圖3 目錄樹結(jié)構(gòu)Fig.3 Structure of directory tree

樹形目錄顯示項目的層次化列表，每項有一個標(biāo)題以及一個圖標(biāo)與之關(guān)聯(lián).層次結(jié)構(gòu)的頂端是根項，根項沒有父項，層次結(jié)構(gòu)的根項之下是子項，子項以縮進方式顯示在父項的下面，項目之間用線連接起來.相關(guān)類的成員變量和成員函數(shù)（見表1）.

表1 目錄樹對象結(jié)構(gòu)Table 1 Object structure of directory tree

1.3.3 雙曲樹的層次結(jié)構(gòu) 將目錄樹層次結(jié)構(gòu)轉(zhuǎn)換雙曲樹層次結(jié)構(gòu)的時候，先把根節(jié)點的坐標(biāo)設(shè)為雙曲平面的中心坐標(biāo)（0，0），然后把根節(jié)點周圍的扇形區(qū)域分配給根節(jié)點的子節(jié)點.這樣每個第二層子節(jié)點（設(shè)根節(jié)點為第一層）都有自己的扇面，每個第二層子節(jié)點都把其子節(jié)點放到自己的扇面里，可以使用遞歸的算法來計算每個節(jié)點在雙曲面上的位置（見圖4）.

相關(guān)類的成員變量和成員函數(shù)如表2所示.

圖4 雙曲樹在歐幾里得平面中的布局Fig.4 Layout of hyperbolic tree in the European space

表2 雙曲樹的對象結(jié)構(gòu)Table 2 Object structure of hyperbolic tree

1.3.4 氣泡樹的層次結(jié)構(gòu) 氣泡樹的結(jié)構(gòu)和雙曲樹映射到平面上的結(jié)構(gòu)非常相似，區(qū)別在于父節(jié)點給子節(jié)點分配的扇面總大小是360度.由于氣泡樹在同一時刻顯示給用戶只有三到四層節(jié)點的信息，也就是局部信息，所以顯示非常清晰，用戶可以通過人機交互獲得其他層的節(jié)點信息.

由于氣泡樹和雙曲樹的布局大同小異，所以其算法中用到的部分成員變量就是雙曲樹算法中的成員變量.氣泡樹布局通過對雙曲樹布局稍作修改即可得到.雙曲樹中按照Klein模型給子節(jié)點分配角度，而氣泡樹中子節(jié)點平均分配一個圓周的角度，即360度.雙曲樹中將所有的層都顯示出來，而氣泡樹則將層數(shù)設(shè)置為某一個值，一般為3到4層.氣泡樹結(jié)構(gòu)布局如圖5、圖6所示.相關(guān)類的成員變量和成員函數(shù)如表3所示.

圖5 氣泡樹初始布局Fig.5 Original layout of bubble tree

圖6 用戶點擊某區(qū)域?qū)雍蟮牟季諪ig.6 Layout after clicking

表3 氣泡樹的對象結(jié)構(gòu)Table 3 Object structure of bubble tree

2 視圖變換和可視化控制

層次信息可視化的另一目標(biāo)，根據(jù)用戶的偏好平滑地實現(xiàn)人機交互，提供信息導(dǎo)航功能.當(dāng)層次結(jié)構(gòu)非常大時，在有限的屏幕上很難全面地顯示整個信息，采用焦點十上下文（Focus＋Context）的視圖變換方法，可以在顯示一個小的焦點區(qū)域詳細信息的同時，保持整個內(nèi)容的整體視圖，使用戶很容易訪問上下文信息并能定位到自己所需要的信息.圖7是城市區(qū)域發(fā)展規(guī)劃項目層次結(jié)構(gòu)使用基于雙曲空間可視化方法得到的視圖.最初把根節(jié)點“新溝產(chǎn)業(yè)板塊”當(dāng)作視圖的焦點（見圖7（a）），通過交互操作使“物流產(chǎn)業(yè)板塊”成為視圖的焦點（見圖7（b））.在視圖轉(zhuǎn)化的過程中，視圖中的節(jié)點可能旋轉(zhuǎn).例如在圖中“垃圾、秸稈等重要原料運送物流區(qū)”節(jié)點開始在視圖的上方，經(jīng)過兩次視圖變化最后在視圖的左下方.圖7中所示的旋轉(zhuǎn)對于一般用戶來說是可以接受的，但是當(dāng)在靠近邊緣位置的節(jié)點在轉(zhuǎn)變的過程中，用戶可能會丟失它們的方向感.

圖7 雙曲樹視圖變換Fig.7 Transformation of hyperbolic tree

3 應(yīng)用及其改進

系統(tǒng)提供的界面分成兩個部分，左邊是類似于資源瀏覽器的樹形視圖，右邊是雙曲樹和氣泡樹視圖，這三個不同的視圖中節(jié)點狀態(tài)是同步實現(xiàn)的.例如圖8和圖9的集成表示中，用戶點擊目錄樹視圖中某節(jié)點，那么雙曲樹和氣泡樹視圖中的相應(yīng)節(jié)點將作為雙曲樹和氣泡樹視圖的焦點位于視圖的中心，并將其它信息包括附屬節(jié)點的信息同時突出顯示.這樣，用戶就可以快捷的了解信息結(jié)構(gòu)，掌握項目詳細的信息及區(qū)域的整體情況.通過菜單選項，用戶可以在雙曲樹視圖和氣泡樹視圖之間任意切換，在使用氣泡樹顯示從某一節(jié)點回到上一層節(jié)點的時候這一操作尤為重要.

圖8 目錄樹與雙曲樹集成表示Fig 8 Integrated expression of directory tree and hyperbolic tree

圖9 目錄樹和氣泡樹集成表示Fig.9 Integrated expression of directory tree and bubble tree

為了提高速度和合理布圖，對雙曲樹視圖進行了一些改進.雙曲樹的新視圖生成要經(jīng)過重新布局及映射，如果對所有節(jié)點重新計算，計算量會很大，對于通過映射算法都被映射到圓盤邊緣的大部分的節(jié)點，實際上可以進行簡化處理，計算量就大大減少了.節(jié)點間連線算法改進，增加約束條件和方法，給那些擁有更多子節(jié)點的節(jié)點分配更大的夾角，使布圖更均勻，空間利用率更高.在處理視圖變化的時候通過增加約束的方式保持方向感，即通過在新視圖上加一些約束使新視圖盡可能地和原來的視圖保持一致.改進后的目錄樹與雙曲樹集成表示如圖10所示，“江漢鹽化工業(yè)園”被選中之后，它的子節(jié)點和它的父節(jié)點“潛江”平均分配圓周角，且它與子節(jié)點的連線選用Bezier曲線，達到了不錯的視圖效果.

圖10 改進后目錄樹與雙曲樹的集成表示Fig.10 Integrated expression of hyperbolic tree and directory tree after improvement

4 結(jié) 語

各種可視化方法都有各自的優(yōu)缺點，人們可以研究出更好的新方法，也可以根據(jù)它們的特點進行綜合運用.普通樹型的優(yōu)點是可以清楚地展示局部信息細節(jié)，缺點是不易看出局部信息在整個信息體系中的位置，雙曲樹的優(yōu)缺點與普通樹相反，而氣泡樹則可以輔助雙曲樹清晰的顯示節(jié)點的局部信息.本文分析研究將雙曲樹、氣泡樹可視化技術(shù)和普通目錄樹可視化技術(shù)相結(jié)合，并將其應(yīng)用于實際項目中，取得很好的效果.通過城市區(qū)域發(fā)展規(guī)劃項目實例可以看到，雙曲樹和氣泡樹在大型層次信息的可視化中很好的提供了“Focus＋Context”視圖，有效地為用戶提供了導(dǎo)航功能，與普通目錄樹相結(jié)合為信息的檢索和表示提供了更加便捷、生動的方式.但本系統(tǒng)還存在一些不足的地方，比如當(dāng)子節(jié)點過多時顯示出來會比較密集，動態(tài)拖動的速度比較緩慢等，

這些問題待下一階段進行改進.

［1］George G.Robertson，Jock D.Mackinlay and Stuart K.Card.Cone Trees：Animated 3D Visualizations of Hierarchical Information［C］∥In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems.New York：ACM，1991：189-194.

［2］Brian Johnson，Ben Shneiderman.Treemaps：a spacefilling approach to the visualization of hierarchical information structures［C］∥In Proceedings of the 2nd International Visualization Conference.New York：IEEE，1991：284-291.

［3］John Lamping，Ramana Rao and Peter Pirolli.A Focus＋Context Technique Based on Hyperbolic Geometry for Visualizing Large Hierarchies［C］∥Proceedings of the SIGCHI conference on Human factors in computing systems.New York：ACM，1995：401-408.

［4］Richard Boardman.Bubble trees：The visualization of hierarchical information structures［C］∥CHI＇2000 extended abstracts on Human factors in computing systems.New York：ACM，2000：315-316.

［5］劉琪.基于Open GL的三維景觀動態(tài)仿真［J］.武漢工程大學(xué)學(xué)報，2011，33（7）：108-110.

［6］靖培棟.《中圖法》可視化研究［J］.中國圖書館學(xué)報，2009，35（180）：42-46.

［7］周寧，陳勇躍，金大衛(wèi).大型層次信息可視化方法研究［J］.中國圖書館學(xué)報，2007（4）：64-67.

［8］竇長威.層次信息可視化技術(shù)的一種實現(xiàn)方法［J］.工程地質(zhì)計算機應(yīng)用，2007（2）：11-15.

Application on integration technology of visualized hierarchical information

HE Yang1，LI Wei-bo1，HU Wei-ping2

（1.Hubei Provincial Key Laboratory of Intelligent Robots，Wuhan Institute of Technology，Wuhan 430074，China；

2.JIHUA Computer System Limited Company，Wuhan 430074，China）

There exist several methods of hierarchical information visualization，level of information with huge structure in limited space can be displayed by hyperbolic tree，local information that user focus on can be clearly shown by bubble tree.A method which convert traditional directory tree structure into hyperbolic tree structure and bubble tree structure，then form visualization technology of integrated directory tree with hyperbolic tree and bubble tree through view transformation and visualization controlling was proposed based on analyzing the characteristics of hyperbolic tree and bubble tree.Applied in urban and regional planning system with multi-layer and multidimensional data was playing powerful functions of directory tree and hyperbolic tree and the auxiliary function of bubble tree，convenient and vivid navigation interface was provided.

visualization；directory tree；hyperbolic tree；bubble tree；integration technology

陳小平

TP311

A

10.3969／j.issn.1674-2869.2011.10.021

16742869（2011）10009006

20110727

湖北省教育廳高校產(chǎn)學(xué)研合作重點資助項目（C2010033）.

何 楊（1987），男，湖北嘉魚人，碩士研究生.研究方向：可視化技術(shù).

指導(dǎo)老師：李偉波，男，教授，碩士，碩士研究生導(dǎo)師.研究方向：計算機圖形處理技術(shù).