層次信息可視化集成技術的應用

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

2.武漢基華電腦系統有限公司，湖北 武漢 430074）

層次信息可視化集成技術的應用

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

2.武漢基華電腦系統有限公司，湖北 武漢 430074）

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

可視化；目錄樹；雙曲樹；氣泡樹；集成技術

0 引 言

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

1 集成可視化方法

1.1 雙曲樹模型

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

設節點M 的扇形區域為（pk，qk），那么第k個子節點的扇形區域為

式中：p表示節點扇形區域的起始角度，q表示扇形區域的大小，n為子節點總數.

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

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

1.2 氣泡樹模型

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

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

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

1.3 層次信息結構及可視化集成

信息可視化集成過程是，先將應用領域的層次信息抽象，建立目錄樹信息結構，通過布局形成可視化目錄樹視圖；同時提取普通目錄樹數據轉換成雙曲樹層次信息結構，然后通過布局映射成雙曲樹視圖，實現層次信息的可視化集成表示如圖2所示.

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

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

1.3.2 目錄樹的層次結構 以樹形結構表示領域層次信息和項目庫中所有項目，按預設的行政區塊（市、區、鎮、三區三園等）逐級表示（見圖3）.

圖3 目錄樹結構Fig.3 Structure of directory tree

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

表1 目錄樹對象結構Table 1 Object structure of directory tree

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

相關類的成員變量和成員函數如表2所示.

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

表2 雙曲樹的對象結構Table 2 Object structure of hyperbolic tree

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

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

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

圖6 用戶點擊某區域層后的布局Fig.6 Layout after clicking

表3 氣泡樹的對象結構Table 3 Object structure of bubble tree

2 視圖變換和可視化控制

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

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

3 應用及其改進

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

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

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

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

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

4 結 語

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

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

［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的三維景觀動態仿真［J］.武漢工程大學學報，2011，33（7）：108-110.

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

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

［8］竇長威.層次信息可視化技術的一種實現方法［J］.工程地質計算機應用，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

湖北省教育廳高校產學研合作重點資助項目（C2010033）.

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

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