WISS2007

クラッタリングを回避する 3 次元情報可視化手法を用いたコンテンツブラウザ
3D Contents browser using a cluttering-avoided visualization technique

宮崎 麗子

伊藤 貴之∗

Summary.
We propose a three-dimensional visualization technique which realizes browsing of hierarchical or metadata-based link structures intelligibly while avoiding three-dimensional cluttering. The
paper describes the algorithm which relocates the metaphor of contents mapped onto three-dimensional
space so that cluttering is avoided on a two-dimensional projection space. We apply the visualization
technique ”HeiankyoView” which represents hierarchical structure as nested rectangular regions, and enables to directly access to the contents which place at the lowest level of hierarchy. Furthermore, whena user chooses arbitrary content, the technique efficiently represents the classification result based onanother metadata simultaneously.

1

従来の音楽，写真，動画などのコンテンツブラウザ
は，ひとつのデータを複数のメタ情報により分類し，動的に階層構造を生成するものが多い．例えば音楽の場合，ジャンル→アーティスト→アルバム→トラッ
クという順序で，一階層ずつひとつのフォルダの内容を表示するため，必要なコンテンツにたどり着くまでに多くのステップを必要とする．また，メタ情報をキーとするブラウジングを続けていくことで，前後のリンク関係がわからなくなり，過去の表示状態に戻れなくなることがある．
そこで我々は，入れ子状に階層構造を構築する視覚化手法「平安京ビュー」[2] を活用してコンテンツを階層的に画面配置し，さらにこれを 3 次元化してコンテンツを重ねて表示することを考える．これによりコンテンツの同時表示数を増やし，また個々のコンテンツに直接アクセスさせることで，階層をたどる操作を不要にできる．
しかし，特に 3 次元可視化システムにおいては，2 次元に比べて表示できる情報量は多いものの，クラッタリングの起こりやすさや複雑な操作性に起因して，現実的に使用するには問題が多い．このような問題を解決するために，力学モデルによってクラッタリングを回避する手法が提案されている [3]．
本報告では，音楽コンテンツを主たる対象とし，3 次元のクラッタリングを回避しながら，メタ情報によって動的に変化する階層構造をわかりやすくブラウジングできる手法を提案する．

2

提案手法

提案手法の特徴は以下の 3 点である．
∗• クラッタリングの回避• 分類メタ情報の切り替え• 表示履歴背景と目的

Copyright is held by the author(s).
Reiko Miyazaki and Takayuki Ito, お茶の水女子大学大学院

2.1

クラッタリングの回避提案手法では次の 3 ステップにより，できるだけクラッタリングが少なくなるような 3 次元配置を実装する．本手法を適用した例を図 1 に示す．

図 1. クラッタリング回避手法の適用例

2.1.1

認識矩形の取得

平安京ビューにおいて，ノードを枠で囲んで定義されたグループという概念は，ユーザが階層構造を認識する上で重要な単位である．しかし平安京ビューを 3 次元化して，最下層のトラックを示すアイコンを組積状に定義した場合，高い組積の周囲の組積は遮蔽されてしまう．提案手法では組積を囲む矩形領域を「認識矩形」と呼ぶことにする．この認識矩形の位置と大きさを 3 次元空間のノードの座標から求める. これにより，3 次元クラッタリングの問題は，2 次元矩形の重複の問題として捉えられる．

2.1.2 重複しない認識矩形位置の算出
2.1.1 節で得られた複数の認識矩形について，2 次元投影面の座標系で以下の処理を行うことによって，認識矩形間の重複を抑えた配置を算出する．この手法はアイコンの重複を解消する Watanabe らの手法
[1] に類似するものである．

WISS 2007

図 2. 分類メタ情報の切り替え

1. 認識矩形の中心を入力点群としたドロネー三角形分割を行う．
2. ドロネー辺で結ばれた認識矩形の対において，重なりがなくなるような理想的な相対位置を求める．具体的には，各認識矩形の対について，重なりがない場合には現在の位置を，重なりがある場合には重ならなくなるように両者を結ぶ直線上に平行移動した位置を，理想的な相対位置とする．このとき，各認識矩形を重複しない位置に最短距離でずらせるよう，重複部の xy 方向の長短も考慮する．
3. 2 で得られた認識矩形の座標を自由変数として，認識矩形間の現在の相対位置と理想的な相対位置との差を最小二乗法で最小化する．また，視点移動前後の表示で大きな差が生じて位置関係が崩れないように，直前に表示した相対位置との差も最小化の入力情報とする．
以上を認識矩形の重複がなくなるまで数回繰り返す．

2.1.3 3 次元空間配置へのフィードバック2.1.2 節で得られた理想の認識矩形の投影面座標を，以下の処理を行うことにより，グループ位置の 3 次元空間座標に変換する．

1. 投影面座標における理想の認識矩形の中心位置を (x’,y’,z’) とする．
（x’,y’ は 2.1.2 節で求めた座標）

2. y=(各グループで最も高い組積と最も低い組積の高さの平均) という方程式の平面を 3 次元空間に描画し，(x’,y’) における z’ の値をデプスバッファから取得する．
（この平面は表示しない）
3. (x’,y’,z’) に対応する 3 次元空間座標値 (x,y,z)を OpenGL の関数で算出する．

2.2

分類メタ情報の切り替え

音楽コンテンツファイルは一般的に，ジャンル，アーティスト，アルバム，作曲者，ムードなどの複数種のメタ情報を保持できる．よって最初は特定のアーティストの楽曲を聴いていても，再生中の楽曲と同じ作曲者の他の曲や，あるいは同じムードで違うジャンルの曲など，メタ情報により聴きたい曲が派生していくケースは多い．

提案手法では，このように分類に用いられるメタ情報が切り替えられた場合も，現在の分類結果と，フォーカス中のコンテンツにおける他のメタ情報を元にした分類結果を同時に表示することにより，効率のいいブラウジングを支援する（図 2（b））．

2.3

表示履歴

提案手法では，2.2 節で展開された複数の分類メタ情報から任意の分類を選択すると，新しい分類結果の全容を表示する（図 2（c））．このとき，直前に選択したコンテンツの位置は動かさず，2.1 節で述べたように，クラッタリングを回避した状態で周囲のコンテンツを配置する．また，組積を折りたたみスタックした状態で，過去の分類結果を常時表示させておく．これにより，ユーザはいつでも任意の過去の分類結果へ 1 ステップで戻ることができる．

3

今後の拡張

提案手法では特に，認識矩形の定義は平安京ビューのグループ定義に依存していたが，ユーザ自身がこの認識矩形を定義できるようなインタラクションを設けたい．また，検索機能やレコメンド機能の結果として特定のデータを強調させるために，特定のデータを見やすい位置へ自動的に視点を移動させたり，注目すべきデータとそうでないデータの重複度を動的に変化させて，より空間利用効率のいいレイアウ
トを生成する機構を実装したい．

参考文献[1] N. Watanabe, M. Washida, and T. Igarashi. Bubble Clusters: An Interface for Manipulating Spatial Aggregation of Graphical Objects. In ACM
User Interface Software and Technology, pp. 173–182, 2007.
[2] 伊藤 貴之, 山口 裕美, 小山田 耕二. 長方形の入れ子構造による階層型データ視覚化手法の計算時間および画面占有面積の改善. 可視化情報学会論文集, 第 26 巻, pp. 51–61, 2006.
[3] 吉田 謙一, 高橋 成雄, 西田 友是, 嶋田 憲司. 運転
経路が遮蔽されないカーナビゲーションシステム.
Visual Computing / グラフィクスと CAD 合同シンポジウム 2005, pp. 87–92, June 2005.