地図への高速ラベル貼りアルゴリズムの 実装と評価 東北大学大学院 情報科学研究科 ◎小池 敦 徳山 豪 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 p2 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
© Copyright 2025 ExpyDoc