地図への高速ラベル貼りアルゴリズムの実装と評価

地図への高速ラベル貼りアルゴリズムの
実装と評価
東北大学大学院情報科学研究科
◎小池敦
徳山豪
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
1
地図へのラベル配置問題とは?
地図上の点,辺,領域に対し
ラベル(文字情報)を付加する
広瀬川
仙台駅
東北大学
青葉城址
地理情報処理の
重要問題
⇒ユーザの要求毎に
迅速にラベリングする必要性
今回は点へのラベリングを扱う
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
2
ラベリングに対する要求
1. ラベルは標的点の近くに貼りたい
⇒予め各標的点に対しラベル候補集合を定める
2. ラベル同士が重なって欲しくない
3. 障害物と重なって欲しくない
ラベル配置問題 =
2,3 を満たすようにラベル候補集合からラベルを選ぶ
文字が重なると
読めない
バス停
東北大学
青葉城址
東北大学情報科学研究科
システム情報科学専攻
ここにはラベルを
TOKUYAMA
貼って欲しくないLab.
(道が判らない) 3
ラベル候補集合
各標的点にとうほくとうほく
どちらかのラベルを配置
とうほく
とうほく
とうほく
とうほく
とうほく
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
4
背景
ラベル配置問題は
多くの場合 NP-hard である [Formann et al. ’91]
⇒ラベル候補集合に
強い制限が必要
東北大学
東
本論文では
北
ラベルの形状に
東北
大
大学
学
自由度を持たせたモデル
(LOFL;Left-part Ordered Flexible Labeling)を扱う
[Koike, Nakano, Nishizeki, Tokuyama and Watanabe ’01]
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
5
本論文の成果
1. LOFL のアルゴリズムに対する
Red-black tree を用いた高速実装
2. LOFL のバリエーションを考え，評価
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
6
発表の流れ
LOFLについて
⇒ラベル候補集合が left-part ordered set
である時のラベル配置問題
 定式化
 アルゴリズムと計算時間の解析
LOFL になるラベル候補集合の紹介
two-position LOFL モデルに対する
ヒューリスティクス
実験
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
7
ラベル間の半順序(LOFL の定式化)

ラベル l の left-part l
 l の標的点の左側の部分
ラベル間の半順序
l2
l2
l2
l1
l
l1
l1

1

l  l2 のとき l1 ≤ l 2 と定義する
東北大学情報科学研究科システム情報科学専攻
順序付け不可
TOKUYAMA Lab.
8
left-part ordered set
(LOFL の定式化)
ラベル候補集合Lが
left-part
ordered
set




 l1, l2  L l1  l2 or l2  l1
つまりどの2つのラベルのleft-partも包含関係にある
left-part ordered set
left-part ordered set ではない
TOKUYAMA Lab.
すべての標的点のラベル候補集合が
left-part ordered set ⇒LOFL
東北大学情報科学研究科システム情報科学専攻
9
LOFL(Left-part Ordered Flexible Labeling)
の定式化(判定問題)
left-part ordered set
入力
•n個の標的点集合
とうほく
•各標的点に対するラベル候補集合
•スケール係数(フォントサイズ) σ
•合計m辺からなる多角形障害物集合
とう
ほく
とうほく
とうほく
とうほく
とうほく
とうほく
障害物
とうほく
とうほく
Yes
東北大学情報科学研究科システム情報科学専攻
出力
•ラベル配置可能ならYes
TOKUYAMA Lab.
•
不可能ならNo
10
LOFL(Left-part Ordered Flexible Labeling)
の定式化(判定問題)
入力
left-part ordered set
•n個の標的点集合
とうほく
•各標的点に対するラベル候補集合
•スケール係数(フォントサイズ) σ
•合計m辺からなる多角形障害物集合
とうほくとう
とうほくとうほく
とうほくとう
ほく
ほく
とう
No
東北大学情報科学研究科
システム情報科学専攻
ほく
とう
ほく
障害物
出力
•ラベル配置可能ならYes
TOKUYAMA Lab.
•
不可能ならNo
11
LOFL(Left-part Ordered Flexible Labeling)
の定式化(最適化問題)
left-part ordered set
入力
とうほく
•n個の標的点集合
•各標的点に対するラベル候補集合
•合計m辺からなる多角形障害物集合
とうほく
とう
とうほく
ほく
とう
ほく
とう
ほく
とうほく
とうほく
とうほく
東北大学情報科学研究科システム情報科学専攻
出力
•ラベル配置可能な
TOKUYAMA Lab.
スケール係数の最大値
12
判定問題に対するアルゴリズム
平面走査法を用いる
larger
smaller
例 2種類のラベル候補で考える
できるだけ
left small なラベルを
配置する
left small = 左の標的点に与える影響が少ない
TOKUYAMA Lab.
⇒これによりアルゴリズムの正当性を証明できる
東北大学情報科学研究科システム情報科学専攻
13
実装
各標的点での交差判定 (障害物無しの時)
⇒frontier を定義する
frontier:
左端から見ることの
できる領域の集合
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
14
frontier のデータ構造
y座標を key として
各線分を red-black tree に格納
•交差判定 O(log n)
•更新 O(log n)
更新回数 O(n) 回
⇒全体で O(n log n)時間
TOKUYAMA Lab.
同様に障害物があるときは O((n+m)log(n+m))
東北大学情報科学研究科システム情報科学専攻
15
最適化問題に対するアルゴリズム
判定問題を用いて
σ に対する二分探索を行う
⇒標的点の座標が log Γ bit で表されている時
計算時間 O((n+m)log(n+m)log Γ)
⇒必ず最適なスケール係数が求まる
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
16
いろいろな LOFL
どのようなラベル候補集合が
left-part ordered set になるのか
1. 90度回転によるleft-part ordered set
90度回転
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
17
いろいろな LOFL
2. two-position set
two-position model [Formann et al. ’91]
でのラベル候補集合
→90度回転による
left-part ordered set になっている
90度回転
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
18
いろいろな LOFL
3. slider set
slider model [M. van Kreveld et al. ‘99]
でのラベル候補集合
→90度回転による
left-part ordered setになっている
自由に動ける
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
19
いろいろな LOFL
4. degenerate set
⇒属するラベルの
left-part がすべて線分
5. revival set
⇒degenerate set に
reliever を追加
reliever
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
20
two-position LOFL モデル
left-part ordered set ではない
two-position set
これらは
left-part ordered set
⇒これを用いてヒューリスティクスを設計する
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
21
LOFL を用いたヒューリスティクス
[Koike et al. ’01]
1. 各標的点のラベル候補を6枚に限定しLOFL を解き,
σの最大値を求める
2. 各標的点で得られたラベルに対し
two-position set を作る
3. LOFLを解き, σの最大値を求める
4. 3.で得られたラベルに対し
新たにラベル候補集合
を作る
5. 1.から4.を繰り返す
東北大学情報科学研究科システム情報科学専攻
TOKUYAMA Lab.
22
実験
(いろいろなラベル候補集合でスケール係数を比べ
る)
50000×50000の領域上のランダムな
n個の標的点のすべてに
同じラベル候補集合を与え
最適化問題を解き，
スケール係数を比べる．
(障害物は無し)
スケール係数は1000回の平均値
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
23
実験
(いろいろなラベル候補集合でスケール係数を比べ
る)
L
O
F
L
ラベル候補集合
1. fixed : 3 σ ×4 σ
2. two-position set (2-POS)
3. slider set
4. degenerate set:
1×12, 2×6, 3×4,
4×3, 6×2, 12×1
5. revival set
6. two-position LOFL (2-LOFL)
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
24
実験
(いろいろなラベル候補集合でスケール係数を比べる)
スケール係数の大小を
two-position set を基準として比較する
計算機環境



CPU : Intel Pentium4 1.6GHz
Memory : 256MB
プログラミングには
C++ のライブラリである LEDA を使用
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
25
実験結果(Fixed)
スケール係数の理論値は 9000n-1 [Koike et al. ’01]
(正確には 9000n 1 から 9000n-1 の間)

実験値/理論値(9000n-1)

1.2
1
0.8
0.6
0.4
n≥200では
|実験値-理論値|<1
となっている
実験値
理論値
0.2
0
0
5000
10000
15000
東北大学情報科学研究科
標的点数システム情報科学専攻
TOKUYAMA Lab.
26
Fixed と 2-POS の比較
fixed/2-position
1.2
1
fixed
2-position
0.8
0.6
2-position の方が
20倍以上(n=12800)
大きいラベルが貼れる
0.4
0.2
0
0
5000
10000
標的点数
15000
東北大学情報科学研究科システム情報科学専攻
TOKUYAMA Lab.
27
2-POS と slider の比較
slider/2-position
1.2
1
0.8
nに関わらず
slider の方が17%くらい大きい
slider
2-position
0.6
0.4
0.2
0
0
5000
10000
15000
標的点数
東北大学情報科学研究科システム情報科学専攻
TOKUYAMA Lab.
28
2-POS と degenerate の比較
degenerate/2-position
1.2
1
degenerate
2-position
0.8
0.6
•n≥60 では2-position の方が
大きい
•n=12800 では2-position の方が
3倍大きい
0.4
0.2
なぜ degenerate は小さいのか?
0
0
5000
10000
15000
標的点数
東北大学情報科学研究科システム情報科学専攻
TOKUYAMA Lab.
29
degenerate の上限の理論値
σ
σ
σ
σ
少なくともこのラベル1枚が
ラベル候補の時よりは小さい
⇒期待値は 31333n-1
これがdegenerateの上限になる
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
30
degenerate の上限値との比較
vs.
degenerate/上限値
σ
1.2
σ
1
0.8
upper bound
degenerate
0.6
0.4
と同じスケール係数の
ラベルが貼れている．
0.2
0
0
5000
10000
標的点数
15000
東北大学情報科学研究科システム情報科学専攻
TOKUYAMA Lab.
31
degenerate と revival の比較
2-positionで規格化されたスケール係数
2.5
2
degenerate
revival
2-position
1.5
1
revival は
degenerateより
6倍以上大きくなった
→reliever が効果的である
0.5
0
0
5000
10000
15000
標的点数
東北大学情報科学研究科システム情報科学専攻
TOKUYAMA Lab.
32
revival と 2-LOFL の比較
2-positionで規格化されたスケール係数
2.5
•n=20 では同じ
•n=12800 ではrevival の方が
95% 大きい
⇒2-LOFLは
最適なスケール係数を
求めていないため
2
1.5
1
2-LOFL
revival
2-position
0.5
0
0
5000
10000
標的点数
15000
東北大学情報科学研究科システム情報科学専攻
→LOFLは
最適解が求まるので強力
TOKUYAMA Lab.
33
実験結果(計算時間)
1000回の平均値
[ミリ秒]
12000
理論値O(n log n log Γ)の
曲線になっている
fixed
2-position
slider
degenerate
2-LOFL
revival
10000
8000
6000
データ構造に
red-black tree を用いず
単純な list を用いた場合との比較
n=1600 の時 (ミリ秒)
4000
2000
degenerate
2-LOFL
0
0
5000
10000
[標的点の数]
15000
list
red-black
2999
67.6
20936
883.5
⇒大幅に計算時間が短縮された
東北大学情報科学研究科システム情報科学専攻
TOKUYAMA Lab.
34
結論
LOFL のアルゴリズムを
red-black tree を用いて高速実装することにより
計算時間の大幅な改善を行った
LOFL の様々なバリエーションについて
実験を行うことにより
解の品質(スケール係数)を比較した．
⇒バリエーションにより品質は大きく異なる
n≤40 : fixed < 2-POS < degenerate < slider < (2-LOFL) < revival
40<n≤6400 : fixed < degenerate < 2-POS < slider < (2-LOFL) < revival
TOKUYAMA Lab.
東北大学
システム情報科学専攻
6400<n情報科学研究科
: fixed < degenerate
< 2-POS < (2-LOFL) < slider < revival
35
今後の課題
LOFLのバリエーションをさらに増やす
スケール係数についての理論的解析
別の方法でLOFLの品質を評価する

あるスケール係数で何枚貼れるか?
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
36
交差判定詳細
標的点からラベルの右辺までの距離が w 以下である
left smallest なラベルをO(log n)time で
見つけることができるとする
w
•総ラベル候補数がO(n)の時
•slider set
の時などに成立
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
37
交差判定詳細
1. 標的点の右にある線分を見つける
⇒O(log n) time
2. その線分と交差しないラベルを
見つける ⇒O(log n) time
3. その線分の上下の線分を見つける
⇒O(log n) time
4. 上の線分と交差判定→OK
⇒O(1) time
5. 下の線分と交差判定→交差
→下の線分と交差しないラベルを
見つける ⇒O(log n) time
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
38
交差判定詳細
6. さらに上下の線分を見つける
⇒O(log n) time
挿
入
さ
れ
る
線
分
7. 上下の線分と交差判定→OK
⇒O(1) time
消去される線分
長さを更新する線分
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
39
交差判定詳細
まとめると
各標的点について
計算時間 = (消去or更新される線分数)×O(log n)
•線分を見つける O(log n)
•ラベルと交差判定 O(1)
•線分と交わらないラベルを
見つける
O(log n)
•線分の消去 or 更新
O(log n)
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
40
交差判定詳細
総計算時間 = (消去or更新される総線分数)×O(log n)
挿入される線分よりは少ない
多くても 2n
よって
各標的点で多くても2つ
→全部で多くても 2n
総計算時間 = O(n log n)
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
41
LOFLのアルゴリズムの正当性
性質
ラベルl が
自分の標的点より左の標的点のラベルと
交差しないならば，
l1 ≤ l を満たすラベル l1 も
自分より左の標的点のラベルと交差しない
l
l1
l1 ≤ l
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
42
LOFLのアルゴリズムの正当性
示すべきこと
条件を満たすラベル配置が存在するならば
このアルゴリズムで必ず見つけることができる
ラベル配置に辞書式順序を定義
より右側の標的点にleft-smallなラベルを割り当てている配置
⇒小さい配置とする
配置赤と配置緑では
配置緑が小さい
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
43
LOFLのアルゴリズムの正当性
アルゴリズムにより辞書式順序が最も小さい配置 L
(left-minimum solution)が求まることを示す
アルゴリズムで求めた配置が L と異なると仮定する．
アルゴリズムが初めて L と異なるラベルを選んだ
(Lでは l を選択したのにアルゴリズムでは l1を選択した)
とき
•アルゴリズムはleft smallest なラベルを選択する
l
ので l1 < l
よってLにおいて l を l1に入れ替えた配置L´は
Lよりも辞書式順序が小さくなってしまい矛盾
⇒アルゴリズムはいつでも
Lと同じラベルを選択する
東北大学情報科学研究科システム情報科学専攻
∊L
l1
TOKUYAMA Lab.
<
l144 l
Fixed のスケール係数の期待値に
ついて [Koike et al. ’01]
まずスケール係数が
σ以上になる確率を計算
これよりスケール係数がσである
確率密度が求まる
最後にσの期待値を求める
期待値 =


0
  f  d
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
45
Fixedの
スケール係数の期待値計算
標的点集合をP={p1,p2,…,pn}とし
p1から順に3 σ ×4 σのラベルを付けていくとする．
スケール係数が σ 以上になる確率
= p1へのラベルが他のラベルと重ならない確率 Pr1
×p2へのラベルが他のラベルと重ならない確率
×p3へのラベルが他のラベルと重ならない確率 Pr3
:
×pnへのラベルが他のラベルと重ならない確率
Pr2
Prn
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
46
Fixedの
スケール係数の期待値計算
•p1へのラベルが他のラベルと重ならない確率 Pr1=1
•Pr2=50000×50000 – 4×12σ2
50000
p2がこの領域にいなければ良い
p1
50000
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
47
Fixedの
スケール係数の期待値計算
•Pr3=50000×50000 – 2×4×12σ2
50000
p3が点線の領域にいなければ
良い
p1
p２
50000
p1とp2の点線の重なった部分≒0
とみなせる
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
48
Fixedの
スケール係数の期待値計算
スケール係数が σ 以上になる確率
= Pr1× Pr2× Pr3×…× Prn
= 1
×(50000×50000 –
4×12σ2)
×(50000×50000 –
2×4×12σ2)
:
×(50000×50000 – (n-1)×4×12σ2)
Pr1
Pr3
Pr2
Prn
TOKUYAMA Lab.
東北大学情報科学研究科システム情報科学専攻
49
実験結果(Fixed)
スケール係数の理論値は 9000n-1 [Koike et al. ’01]
(正確には 9000n 1 から 9000n-1 の間)

実験値/理論値(9000n-1)

1.2
1
0.8
n≥200では
|実験値-理論値|<1
となっている
0.6
実験値
理論値
Floor
0.4
0.2
0
0
5000
10000
15000
東北大学情報科学研究科
標的点数システム情報科学専攻
TOKUYAMA Lab.
50

Download Report