左順序付き柔軟ラベリングの実装 Implementation of Left-part ordered Flexible Labeling 東北大学大学院 情報科学研究科 ◎小池 敦 徳山 豪 TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 1 地図へのラベル配置問題とは? 地図上の点,辺,領域に対し ラベル(文字情報)を付加する 広瀬川 仙台駅 東北大学 青葉城址 地理情報処理の 重要問題 ⇒ユーザの要求毎に 迅速にラベリングする必要性 今回は点へのラベリングを扱う TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 2 ラベリングに対する要求 1. ラベルは標的点の近くに貼りたい ⇒予め各標的点に対しラベル候補集合を定める 2. ラベル同士が重なって欲しくない 3. 障害物と重なって欲しくない ラベル配置問題 = 2,3 を満たすようにラベル候補集合からラベルを選ぶ 文字が重なると 読めない バス停 東北大学 青葉城址 東北大学 情報科学研究科 システム情報科学専攻 ここにはラベルを TOKUYAMA 貼って欲しくないLab. (道が判らない) 3 ラベル候補集合 各標的点に とうほく とうほく どちらかのラベルを配置 とうほく とうほく とうほく とうほく とうほく TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 4 背景 ラベル配置問題は 多くの場合 NP-hard である ⇒ラベル候補集合に 強い制限が必要 東北大学 東 本論文では 北 ラベルの形状に 東北 大 大学 学 自由度を持たせたモデル (LOFL;Left-part Ordered Flexible Labeling)を扱う TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 5 本論文の成果 1. LOFL のアルゴリズムに対する Red-black tree を用いた高速実装 実用的なラベル配置問題では より自由度の高いラベル候補集合に対して ヒューリスティクスを用いて 高速に解く必要性がある ⇒2. LOFL を組み合わせた two-position LOFL モデルに対する高速ヒューリスティクス TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 6 発表の流れ LOFLについて ⇒ラベル候補集合が left-part ordered set である時のラベル配置問題 定式化 アルゴリズムと計算時間の解析 two-position LOFL モデルに対する ヒューリスティクス 実験 TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 7 LOFL の定式化 ラベル l の left-part l l の標的点の左側の部分 l2 l2 l1 1 l l1 l l2 のとき l1 ≤ l2 と定義する 東北大学 情報科学研究科 システム情報科学専攻 TOKUYAMA Lab. 8 LOFL の定式化 ラベル候補集合Lが left-part ordered set l1, l2 L l1 l2 or l2 l1 つまりどの2つのラベルのleft-partも包含関係にある left-part ordered set TOKUYAMA Lab. left-part ordered set ではない 東北大学 情報科学研究科 システム情報科学専攻 9 LOFL(Left-part Ordered Flexible Labeling) の定式化 目的 : できるだけ大きなラベルを配置すること 入力 n 個の標的点集合 各標的点に対し left-part ordered set であるようなラベル候補集合 合計 m 辺からなる多角形障害物の集合 出力 各標的点に配置されるラベル スケール係数σの最大値 (各ラベルはσにより拡大/縮小され配置される) ⇒ σの最大値はσでの配置可能判定問題を用いて TOKUYAMA Lab. 二分探索を行うことで求める 東北大学 情報科学研究科 システム情報科学専攻 10 left-part ordered set 入力 •標的点集合 •各標的点に対するラベル候補集合 •障害物集合 とうほく とう ほく とうほく とうほく とうほく とうほく とうほく とうほく 障害物 とうほく より大きいラベルを配置したい 東北大学 情報科学研究科 システム情報科学専攻 TOKUYAMA Lab. 11 left-part ordered set 入力 •標的点集合 •各標的点に対するラベル候補集合 •障害物集合 とうほく とう とう ほく ほく とう ほく とうほく とう ほく とうほく とうほく とうほく スケール係数σ により拡大 東北大学 情報科学研究科 システム情報科学専攻 出力 •ラベル配置 TOKUYAMA Lab. •スケール係数 12 判定問題に対するアルゴリズム 平面走査法を用いる larger smaller 例 2種類のラベル候補で考える できるだけ left small なラベルを 配置する left small = 左の標的点に与える影響が少ない TOKUYAMA Lab. ⇒これによりアルゴリズムの正当性を証明できる 東北大学 情報科学研究科 システム情報科学専攻 13 計算時間の解析 各標的点での交差判定 (障害物無しの時) ⇒frontier を定義する データ構造に red-black tree を用いる •交差判定 O(log n) •更新 O(log n) 更新回数 O(n) 回 ⇒全体で O(n log n)時間 TOKUYAMA Lab. 同様に 障害物があるときは O((n+m)log(n+m)) 東北大学 情報科学研究科 システム情報科学専攻 14 LOFL を用いたヒューリスティクス left-part ordered set ではない two-position モデル これらは left-part ordered set ⇒これを用いてヒューリスティクスを設計する TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 15 LOFL を用いたヒューリスティクス 1. 各標的点のラベル候補を6枚に限定しLOFL を解き, σの最大値を求める 2. 各標的点で得られたラベルに対し two-position モデルのラベル候補集合 を作る 3. two-positionを解き, σの最大値を求める 4. 3.で得られたラベルに対し 新たにラベル候補集合 を作る 5. 1.から4.を繰り返す 東北大学 情報科学研究科 システム情報科学専攻 TOKUYAMA Lab. 16 実験 (LOFLとtwo-LOFLのスケール係数を比べる) 50000×50000の領域上のランダムな n個の標的点に以下のモデルでラベリング (障害物は無し) 1. fixed model : 3 σ ×4 σ 2. two-position model 3. LOFL : 1×12,2×6 3×4,4×3,6×2,12×1 4. two-position LOFL 東北大学 情報科学研究科 システム情報科学専攻 TOKUYAMA Lab. 17 実験 計算機環境 CPU : Intel Pentium4 1.6GHz Memory : 256MB プログラミングには C++ のライブラリである LEDA を使用 TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 18 実験結果(スケール係数) 100回の平均値 [スケール係数] 2000 n = 800 の時 fixed 1500 •fixed model と比べ •2-positionは6倍 •LOFLは3倍 •2-LOFLは9倍 くらい大きい 2-position LOFL 1000 2-LOFL 500 0 0 200 400 600 800 ヒューリスティクスの方が 2-positionより1.5倍くらい大きい [標的点の数] 東北大学 情報科学研究科 システム情報科学専攻 TOKUYAMA Lab. 19 実験結果(スケール係数) 100回の平均値 [スケール係数] n = 12800 の時 100 fixed 80 2-position 60 LOFL 40 2-LOFL 20 0 800 3800 6800 9800 [標的点の数] 12800 •fixed model と比べ •2-positionは20倍 •LOFLは7倍 •2-LOFLは22倍 くらい大きい ヒューリスティクスの方が 2-positionより11%くらい大きい TOKUYAMA Lab. 東北大学 ヒューリスティクスは 情報科学研究科 システム情報科学専攻 n が小さい時は特に有効である 20 実験結果(計算時間) 100回の合計値 理論値O(n log n)の 曲線になっている [sec] fixed 2-position LOFL 2-LOFL 1000 800 600 データ構造に red-black tree を用いず 単純な list を用いた場合との比較 n=1600 の時 (sec) 400 200 0 0 4000 8000 [標的点の数] 12000 LOFL 2-LOFL list red-black 300 6.7 2094 92 ⇒大幅に計算時間が短縮された 東北大学 情報科学研究科 システム情報科学専攻 TOKUYAMA Lab. 21 結論 LOFL のアルゴリズムを red-black tree を用いて高速実装することにより 計算時間の大幅な改善を行った LOFL でないより一般的な問題に対し LOFL の解法を用いたヒューリスティクスを設計し 解の品質(ラベルサイズ)が向上することを示した 今後の課題 様々なラベル候補集合で実験を行い， より品質の良いものを見つける． TOKUYAMA Lab. 東北大学 情報科学研究科 システム情報科学専攻 22
© Copyright 2024 ExpyDoc
