Metro maps are common media for providing information about public transportation means, and usually available in every major city to help travelers make full use of the corresponding transportation systems. Generating aesthetic layout of such metro maps will significantly improve their readability, and thus is important also from a practical viewpoint. Indeed, Harry Beck invented schematic representation of London Underground map by introducing several aesthetic criteria for rearranging the layout of the metro network. His criteria have been commonly employed by contemporary map illustrators when they draw schematic representations of metro maps, for example, in travel guidebooks.

On the other hand, annotating metro maps with text and image labels can provide supplemental information, and thus can facilitates travelers to effectively find sites of interest and their associated routes over the metro network. Actually, map illustrators often seek aesthetic layouts of both the metro network and large annotation labels, and successfully arranged their positions to increase the space coverage over the map domain. However, as a computational problem, optimal placement of such large annotation labels has been explored independently of the layout of metro networks. Automatically tailoring the aesthetic layout of a metro network and its associated annotation labels together is still a challenging task, due to not only the computational complexity of each individual layout problem but also that for finding a plausible compromise between these two problems.

This thesis presents a novel approach to customizing annotated metro maps by solving this hybrid problem of metro map layout and annotation. The contribution of this thesis is three-fold (see Figure 1). We first tackle the metro map annotation problem by developing a zone-based approach for placing annotation labels while keeping the original layout of a metro network unchanged. This is accomplished by tightly enclosing the metro network to maximally utilizing available labeling space around it. For placing annotation labels while minimizing the total leader lengths, we incorporated evolutions algorithms so that we can embed labeling boxes into specific zones according to their types. We then pursue the metro map layout problem by introducing travel-route-centered design of metro maps. This allows us to aesthetically deform the map layout by elongating a specific route over the metro network to be straight along the centerline of the map domain. Annotation labels are constrained to be placed at the top and bottom of the map domain in this approach for annotating all the stations along the specified route. Finally, we compose a hybrid approach for solving both the metro map layout and annotation problems by seeking maximum space efficiency of the map contents. Indeed, with this approach we try to place annotation labels as compactly as possible while keeping the aesthetic layout of the metro network. The associated computational complexity has been significantly reduced by a newly developed three-step algorithm, where we can also select the stations to be annotated while adjusting the size of the corresponding annotation labels.

The idea behind our approach is to formulate the aesthetic criteria for designing metro map layout and annotation as constraints imposed on the metro network, and solve the associated map composition problem as a constrained optimization problem. Our computational tools for solving such constrained optimization problems are genetic-based formulation, minimum-cost maximum-flow problem formulation, and mixed-integer programming formulation. The genetic-based formulation allows us to embed annotation labels within the available labeling space around the metro network while avoiding mutual intersections between labeling boxes and leaders (Figure 2). The minimum-cost maximum-flow problem formulation makes it possible to explore the curved leader shapes between stations on the straight centerline route and boundary labels while maximally reducing the number of intersections between the label leaders and the underlying metro line segments (Figure 3). The mixed-integer programming formulation searches for octilinear layouts of the metro network together with well-balanced distribution of annotation labels around it (Figure 4). Our contribution lies in the new formulation of such constrained optimization problems for aesthetic design of annotated metro maps together with implementation of computational algorithms for solving them. Several design examples are also presented to demonstrate the feasibility of this approach, which is followed by user studies and discussion on the limitations of the present formulation.

Figure 1: Organization of this thesis. In Chapter 3, we tackled the label placement problem. In Chapter 4, we tackled the label rearrangement problem. In Chapter 5, we tackled the hybrid problem of the above two.

Figure 2: The result of our zone-based approach to annotating image annotation on geographic metro layout.

Figure 3: The result of our approach to designing annotated travel-route-centered metro map.

Figure 4: The result of our approach for spatially efficient design of annotated metro maps.

地下鉄路線図の可視化は,情報可視化において,グラフ描画問題の古典的かつ有名な事例と認識されている.加えて,最近我々が目にする旅行ガイドブックでは,路線図上に比較的サイズの大きな注釈が,スペース効率を考慮に入れて最適に配置されている.しかしながら,このような路線図や注釈ラベルの最適配置は,従来人の手により行われてきており,その自動計算は計算量の観点から非常に難しい問題となるため,近年やっと基礎研究が行われ始めた状況にあった.本論文の貢献は,このように地下鉄路線図と注釈ラベルの最適配置を,制約付き最適化問題として新たに定式化し,その解法アルゴリズムを計算機上に実装し,さらに実用性を評価した点にある.

本論文は7章で構成され,各章の内容は以下のようにまとめることができる.

第1章では,地下鉄路線図設計と注釈ラベル配置の2つの問題のとらえ方を紹介し,可視化研究の分野における注釈付き地下鉄路線図問題の位置づけについて概観し,本論文の提案する制約付き最適化手法を導入する動機付けと,本論文の技術的な貢献や論文自体の構成についてまとめている.

第2章では,本論文で取り組む地下鉄路線図と注釈ラベル配置の問題に関連の深い,グラフ描画問題,注釈ラベル配置問題,地下鉄路線図設計問題の既存の手法について関連研究を紹介し,地下鉄路線図と注釈ラベルの最適配置問題の両方を考慮にいれて解く手法の必要性について論じている.

本論文の主たる貢献は,第3,4,5章の3つの章において記述されている.

第3章は,地下鉄路線図配置が固定の場合に,テキストなどの比較的サイズの小さい注釈ラベルと,画像などのサイズの大きい注釈ラベルの2種類の注釈ラベルを対象とし,地図上の区域分割に応じてそれらを配置するアルゴリズムを示す.具体的には,路線図に近い方から,路線図だけを内包する領域,小さいテキスト注釈ラベルだけ配置する領域,すべてのラベルが配置できる領域の3つの領域を,地下鉄路線図網の画像にモルフォロジーの操作である膨張操作を繰り返し適用して得る.さらに,地図領域を正方形セルのグリッドの集合と見なして,注釈ラベルをグリッドに沿うように配置することで,その可動位置の自由度を適切に限定し探索空間を小さくしている.その後,注釈ラベルの最適配置問題に対し,遺伝的アルゴリズムを導入して,比較的短時間に最適解に近い解を求めることに成功している.

第4章は,注釈ラベルの配置が地図領域の上下境界領域に限定された場合に,ある特定の旅行経路を中心として地下鉄路線図を配置するアルゴリズムを示している.具体的には,まず従来手法である混合整数計画法の定式化を用いて,地下鉄の各路線を縦,横,斜めの8方向に配置するとともに,路線図を構成する辺の向きを系統的に制御することで,ある特定の路線を地図上の中心線としてまっすぐ伸ばす変換を施す.注釈ラベルの最適配置問題については,路線図に含まれている重要な駅などのランドマークと注釈ラベルと駅を結ぶリーダ線の重なりを明示的に回避するために,2部グラフのマッチングの組み合わせとして定式化し,これをネットワーク流の問題としてとらえ,反復最短経路アルゴリズムを利用しその最小コスト最大流を計算することで解決を図っている.

第5章は,地下鉄路線図と注釈ラベル配置の両方を考慮した,スペース利用効率の高い注釈付き地下鉄路線図生成手法を示している.具体的には,前述の混合整数計画問題を用いた地下鉄路線図配置のための従来手法に加えて,注釈ラベルとリーダ線の配置も混合整数計画問題として記述することで,地下鉄路線図と注釈ラベルの両方の配置を最適化するハイブリッド手法を実現している.さらに,路線図初期配置,注釈ラベル配置,スペース効率の効率化の3つの最適化計算のステップを経ることで,最適化のための探索空間を劇的に最小化するアルゴリズムも考案もおこなっている.

最後に第6章で,各提案手法に対する評価を行ったのち,第7章で論文を総括し,今後の課題について言及している.

以上のように,本論文は地下鉄路線図と注釈ラベルの最適配置を,制約付き最適化手法として解く新たな数理的枠組みを提案するとともに,その有効性をシステム実装に示すことに成功している点において,非常に独創的かつ重要な研究となっている.審査委員会は,情報可視化分野における本論文の特筆すべき貢献を評価し,博士号に十分値するものと判断した.

なお,本論文の第3章と第4章は,高橋成雄,林春成, 顏嗣鈞,第5章は前述の共同研究者に加え廣野大地,有川正俊との共同研究であるが,論文提出者が主体となって手法の考案と実装を行ったもので,論文提出者の寄与が十分であると判断する.

したがって,博士(科学)の学位を授与できると認める.