曲線の最小Fréchet距離近似に関するアルゴリズムの実装
8
0
0
全文
(2) り、単純化された頂点数を保証する。アルゴリズ ムを実装し，文献［APMW 02］の手法の実効性 を確認した。. 2. FD (f, g) =. Fr´ echet 誤差測定法による曲線 単純化 Fr´echet 誤差測定法による曲線単純化の最適解を. 求めるためにかかる計算時間は、O(n3 ) であるこ とが知られている ([II88])。ここでは、O(n log n) で計算する近似アルゴリズムを紹介する。. max {d(f (α(t)), g(β(t)))} inf α : [0, 1] → [a, a ] t∈[0,1] β : [0, 1] → [b, b ]. 人間が犬を散歩に連れて行く光景を思い出して ほしい。いま、犬を鎖につけて散歩すると考える。 人間は f 上の道を a から a まで戻らずに歩き、犬 は g 上の道を b から b まで戻らずに歩くとし、道 をはみ出すことはないとする。また、人間は鎖か ら手を離さないとする。そのときに、鎖が伸びきら ないように最後まで歩くことができるような、最 小の鎖の長さが、f と g の間の Fr´echet distance に. 2.1. 相当する。. Fr´ echet Distance. p2 p4 f b’. p6. p1 a. p3. a’. p5. 図 2: x-単調な折れ線と水平線分の間の Fr´echet b. distance. g. 線分と線分方向に単調な折れ線 P の場合を考え てみる。図 2 のように f を P 、g を線分 p1 p6 とする. 図 1: f ,g 上を動く２点間の距離. と、Fr´echet distance は、P の各頂点から線分 p1 p6 . . ２つの曲線 f : [a, a ] と g : [b, b ] を考える。α, β. への最短距離の中で、最大のものとなる。ここで. を連続かつ増加関数とし、パラメータを t ∈ [0, 1]. は、p2 から線分 p1 p6 へ下ろした垂線が、Fr´echet. とすると、α(t), β(t) はそれぞれ、f, g 上を動く。. distance となる。. ただし、α(0) = a, α(1) = a , β(0) = b, β(1) = b. 従って、片方が線分で他方が単調である場合は、 通常の Hausdorf f 距離と同一である。. とする。これらを表したのが、図 1 である。. f と g の間の Fr´echet distance である FD (f, g) は以下の式で定義される。. 2.2. Fr´ echet 誤差測定法. ２つの頂点 pi , pj ∈ P, i < j に関して、線分 pi pj と P の Fr´echet 誤差は以下の式で定義される。. δF (pi pj , P ) = FD (π(pi , pj ), pi pj ) π(pi , pj ) は、pi から pj までの P の部分曲線で ある。図 3 のような破線と実線からなる P を考え ると、π(pi , pj ) は、実線部分がそれに相当する。. 2 −10−.
(3) 2.3. pj. FrechetSimp 法. Fr´echet 誤差測定法のもとで P の ε-simplification である P を計算する近似アルゴリズムである FrechetSimp 法は、以下の手順で行われる。 アルゴリズム. • 入力：P = p1 , p2 , . . . , pn
(4) と誤差 ε(> 0). pi. • 出力：頂点系列 P 1. P = pi1 = p1
(5) とし、k = 2 とする。 2. P に 含 ま れ る 点 の な か で 、添 え 字 が 最 大. 図 3: π(pi , pj ) v. A(t). x. u C(t) x. B(t). B(t). ≤ ε, δF (pij pk+1 , P ) > ε となる k を見つけ、pk. v. の も の を pij と す る と 、δF (pij pk , P ). C(t) y. u. を P に含める。. A(t) y. 3. k > n となるまで手順２を繰り返し、最後に pn を P に含める。. 図 4: 有向辺 uv,xy. 2.4. FrechetSimp 法の計算時間. ここで、以下の補題が成立する。. FrechetSimp 法の計算時間が、O(n log n) である 補題 2.1 ２つの有向辺である uv と xy に関し. ことを示す。それを示すために、距離判定問題と 二分探索法の２つについて述べる。. て、以下の補題が成立する。. 2.4.1. FD (uv, xy) = max{d(u, x), d(v, y)}. 距離判定問題. 証明 δ = max{d(u, x), d(v, y)} とおく。まず、FD. p2. は定義式より、u と x、v と y が対応する。d(u, x) と. d(v, y) は FD の値の候補となるため、FD (uv, xy) ≥ δ が成立する。. p4. p1. p6. 一方、t ∈ [0, 1] において、A(t) = u + t(v −. p3. u), B(t) = x + t(y − x) とし、C(t) = A(t) − B(t) とすると、C(t) = (1 − t)(u − x) + t(v − y) とな. p5. る。ここで、. ||C(t)||. =. ||(1 − t)(u − x) + t(v − y)||. ≤. (1 − t)||u − x|| + t||v − y||. ≤. (1 − t) · δ + t · δ = δ. p1. したがって、FD (uv, xy) ≤ ||C(t)|| ≤ δ となる。 以上より、FD (uv, xy) = δ. ✷ 3 −11−. p6. 図 5: 各頂点から ε 以内にある区間の作成.
(6) a. b. a p. q. p. 㬍. a. ㈩⟎ਇน⢻䈭႐ว. (b). p. q. q. p. 㗔ၞ䈏ᦝᣂ䈘䉏䉎႐ว. (c). 補題 2.2 δF (pij pk , P ) が ε より大きいかどうか. b. q. a. 䇭. (a). b. 判定するのにかかる時間は、O(k − ij ) である。. q. 㗔ၞ䈏ᦝᣂ䈘䉏䈭䈇႐ว. 2.4.2. 二分探索法 b 0 b 1b 2. b4. b2. b8. j. 䇭䇭䇭䇭䋰䋰䋰 䊶䍃䍃 䋰 䊶䍃䍃 䊶䍃䍃 䋰 䊶䍃䍃 䊶䍃䍃 䂔 䊶䍃䍃 䊶䍃䍃 䋱 䊶䍃䍃. 図 6: 現在の区間と考慮する区間との関係. pim. pim+1. 手 順 ２ で δF (pij pk , P ) が ε よ り 大 き い か ど う か の 判 定 に 関 し て 、以 下 の よ う に 行 う。 . 図 7: 最初に bρ が１になる j. pij pij +1 ,. . . ,pk−1 pk で あ る よ う に 、π(pij , pk ) を 線 分 に 分 割 し て 考 え る 。線 分 pij pk に 関 し て 、π(pij , pk ) 上 の pij , pij +1 ,. . . ,pk 応する点. pij , pij +1 ,. . . ,pk. 頂点 pim ∈ P の次に、P に含まれる pim +k を 計算する方法を考える。これには、二分探索法を. と対. 用いる。. を 、そ れ ぞ れ 決 め. る 。補 題 2.1 よ り、FD (pij pk , π(pij , pk )) は 、. まず、bρ を１ビットの値とし、δ(pim pim+ρ ) > ε. d(pij , pij ),. . . ,d(pk , pk ) の 最 大 値 と な る か ら 、 d(pij , pij ),. . . ,d(pk , pk ) の最大値がすべて ε 以下 で、かつ、点 pij , pij +1 , . . . , pk が後戻りしないよう. るのにかかる時間は、補題 2.2 より、O(ρ) となる。. に配置することができれば、FD (pij pk , π(pij , pk )). ならば 1、そうでなければ 0 とする。bρ を計算す. bk = 0, bk+1 = 1 となる、連続した２ビットの 値を探すのだが、最初に探索する範囲を決定する。 b0 = 0 とし、b1 , b2 , b4 , . . . , b2j と飛び飛びに計算 し、最初に値が１となる j の値を求め、b2j−1 か. の値は ε 以下となり、そうでなければ、ε よりも 大きくなる。 これらを計算するために、図 5 のように、点. ら b2j を探索の区間に定める。なお、2j > n と. pij , pij +1 , . . . , pk を中心とする半径 ε の円が含む、. なった場合は、探索の終点を頂点が pn に相当する. 間でできる。この得られた区間内に関して、点 pij. bρ とする。この作業にかかる時間は、O((im+k − im ) log(im+k − im )) となる。図 7 はこの作業をイ. から順番に点を配置できるかどうか判定する。. メージしたものだが、数字が書いていない場所は、. 線分 pij pk の各区間を求める。この作業は定数時. まだ判定が行われていないことを表している。図. まず、初期区間を線分 pij pk の両端点とする。次 に、点 pij +1 がつくる区間に点. pij +1. を配置する。. 7 では、b16 が b2j に対応している。. この際、図 6 のような関係が考えられる。現在の. 䌢8. 䋰. 区間を [p, q]、考慮する区間を [a, b] とする。(a) の 場合は、順番に点を配置することができない。(b). 䌢8. 䋰. の場合は、区間を [a, q] に更新する。(c) の場合は、 区間は変更されず、そのままである。 䌢8. この処理を pk まで繰り返していき、すべての点. 䋱. 䋰 䋿 䋱. になると分かる。そうでなければ、ε より大きくな. 䋱 䌢8. 䌢12. 䋿. を順番に配置することができれば、ε より小さい値 る。したがって、この配置を行うのに、O(k − ij ). 䋱. 䌢10. 䋰 䌢9. 䌢16. 䋿 䌢12. 䋱. 䋰. 䌢10. 䌢12. 䌢12. 䋰. 䋱. 䌢10. 䌢11. 䋱. 䋱. 䌢16. 䋿. 䋰. 䋰 䋿 䋱 䋱. 䋰. 䌢14. 䌢14. 䋰. 䋱. 䋰 䋿 䋱 䌢12. 䋱. 䌢13. 䋰. 䌢16. 䋰 䋿 䋱 䌢14. 䋰 䌢15. の時間がかかる。 関数 d は定数時間で計算できるので、. 図 8: 二分探索の例. δF (pij pk , P ) を 計 算 す る の に 要 す る 時 間 は 、 O(k − ij ) となる。従って、次の補題を得る。. この区間内には、01 の連続した２ビットが存在 する。これを探すのに二分探索を行う。最初は、. 4 −12−.
(7) b(2j +2j−1 )/2 を計算し、その値が 0 ならば、左半分. 補題 2.5 P = p1 , p2 , . . . , pn
(8) とする。l ≤ i ≤. の区間で、1 ならば右半分の区間で同様の処理を. j ≤ m なる、i, j, l, m について、以下の式が成立 する。. 行う。この処理を繰り返して、区間の幅が１になっ たら、そのときの位置、または１つ後ろの位置が. δF (pi pj , P ) ≤ 2 · δF (pl pm , P ). 求める k の値となる。図 8 は、図 7 のときに二分 探索を行った場合を示している。このときにかか る時間は、二分探索に O(j − 1) = O(log(im+1 −. im ))、bρ の値の判定に O(im+1 − im ) かかるので、 O((im+1 − im ) log(im+1 − im )) となる。 したがって、FrechetSimp 法に要する計算時間 は、O(n log n) となる。. 証明 δ =δF (pl pm , P ) とする。Fr´ echet distance の定義より、δF (pl pm , P )=FD (pl pm , π(pl , pm )) で あ り、π(pl , pm ) 上 の pi , pj と 対 応 す る 点 を そ れ ぞれ 、pi , pj. ∈ pl pm と する 。そ うす る と 、. FD (pi pj , π(pi , pj )) ≤ δ が成立する。これに関 連して、d(pi , pi ) ≤ δ , d(pj , pj ) ≤ δ が成立. する。ここで、補題 2.1 より、FD (pi pj , pi pj ) =. 2.5. FrechetSimp 法による頂点数の上 限. FrechetSimp 法によってできる P について、以. max{d(pi , pi ), d(pj , pj )} ≤ δ となる。よって、補. 題 2.4 より、. δF (pi pj , P ) =. 下の補題が成立する。 . 補題 2.3 FrechetSimp 法は、δF (P , P ) ≤ ε と . なる P を計算する。. FD (pi pj , π(pi , pj )). ≤. FD (pi pj , π(pi , pj )) + FD (pi pj , pi pj ). ≤. FD (pi pj , π(pi , pj )) + δ . ≤. δ + δ = 2δ . したがって、δF (pi pj , P ) ≤ 2 · δF (pl pm , P ) とな. . 証明 P = p1 = pi1 , pi2 , . . . , pim = pn
(9) ∈ P とす. ✷. る。. る。FrechetSimp 法より、δF (pi1 pi2 , π(pi1 , pi2 )) ≤. ε, . . . , δF (pim −1 pim , π(pim −1 , pim )) ≤ ε となる。. pi. pj. . よって、補題 2.1 より、δF (P , P ) ≤ ε となる。. ✷. pl. 次に、FrechetSimp 法によってできる P の頂点. pm. 数の上限について考えるが、その前にそれを考え るために必要な補題を示す。 補題 2.4 P と２つの線分 uv, xy に関して、以 下の式が成立する。. FD (xy, P ) ≤ FD (uv, P ) + FD (xy, uv). 図 9: δF (pl pm , P ) と δF (pi pj , P ). 証明 t ∈ [0, 1] において、A(t) = u + t(v −. FrechetSimp 法によってできる P の頂点数の上 限について、以下の補題が成り立つ。. u), B(t) = x + t(y − x) とする。すべての t ∈ [0, 1] について、三角不等式より、. ✷. 補題 2.6 FrechetSimp 法は、|P | ≤ κF (ε/2, P ) を. d(B(t), P (t)) ≤ d(A(t), P (t)) + d(B(t), A(t)). 満たす P を作成する。. が成立する。. 証明 P = p1 = pi1 , . . . , pik = pn
(10) とし、. よって、FD (xy, P ) ≤ FD (uv, P ) + FD (xy, uv). Q = p1 = pj1 , . . . , pjl = pn
(11) を、P の ε/2simplification とする。ただし、1 ≤ m ≤ k に. 5 −13−.
(12) 䌐. p1 䍃 䍃 䍃 䍃. Q. pj1 䍃 䍃 䍃 䍃 pjm−1. 䍃 䍃 䍃 䍃 pn pjm 䍃 䍃 䍃 䍃. 頂点数 n. 実行後の頂点数. 時間 (sec). 䍃䍃䍃䍃. 1000. 19. 0.02. 2000. 35. 0.03. 3000. 51. 0.04. 4000. 66. 0.05. 5000. 82. 0.07. おいて、1 ≤ im ≤ n とし、1 ≤ m ≤ l におい. 6000. 98. 0.08. て、1 ≤ jm ≤ n とする。すべての m において、. 7000. 114. 0.09. im ≥ jm であることを示す。. 8000. 130. 0.11. 9000. 146. 0.12. 10000. 162. 0.13. 䌐㫪 pi 䍃 䍃 䍃 䍃 1. pim pim+1. pim−1. 図 10: P と Q の関係. 図 10 の よ う に 、pjm−1 , . . . , pjm. の中に. pim−1 ,. . . ,pim , pim +1 が 含 ま れ て い る と 仮 定 す る 。P に つ い て 、FrechetSimp 法 よ り、 δF (pim−1 pim , P ) ≤ ε, δF (pim−1 pim +1 , P ) > ε と な る 。Q は P の ε/2-simplification で あ る か ら 、補 題 2.5 よ り、δF (pim−1 pim +1 , P ). ≤. 2 · δF (pjm−1 pjm , P ) ≤ 2 · ε/2 = ε となり、矛 盾する。よって、i1 = j1 = 1 であることから、 im ≥ jm となることが分かる。. 㪇㪅㪈㪋 㪇㪅㪈㪉. したがって、jk ≤ ik = n となるから、k ≤ l が . 成立する。以上より、|P | ≤ κF (ε/2, P ) が成立す. ✷. る。. 表 1: 単純化したときの頂点数と実行時間. 㪀㪺 㪇㪅㪈 㪼㫊 㪇㪅㪇㪏 㩿㪼 㪇㪅㪇㪍 㫀㫄 㪫 㪇㪅㪇㪋 㪇㪅㪇㪉. 3. 㪇. 実験. 㪇. 㪉㪇㪇㪇. 㪋㪇㪇㪇. 㪍㪇㪇㪇. 㪏㪇㪇㪇. 㪈㪇㪇㪇㪇. 㫅. Fr´echet 誤差測定法による曲線単純化の近似ア ルゴリズムである FrechetSimp 法を実装した。こ のアルゴリズムを用いて、様々な P に関して実験. 図 11: n と計算時間の関係. を行った。 まず、P を正弦波曲線を 0.05[rad] 刻みに取った 頂点集合とする。誤差 ε=0.5 と固定し、頂点数を 変えて計算時間に関する実験を行った。. 㪊. 図 11 を見ると、O(n log n) に近いグラフが得る. 㪉. ことができた。このことより、計算時間に関して. 㪈. は O(n log n) であることが確かめられる。. 㪄㪊. 次に、P を図 12 のようなリサージュ曲線とし、 誤差 + の値を変えて実行した。頂点数は 628 個で. 㪄㪉. 㪄㪈. 㪇 㪄㪈 㪇. 㪈. 㪉. 㪄㪉 㪄㪊. ある。また、P を Hilbert 曲線とし、一辺の長さが ２の正方形に囲まれた、図 15 の場合で、誤差 + の 図 12: リサージュ曲線. 値を変えて実行した。 図 13、図 14 を見ると、+=0.1、+=0.01 の場合. 6 −14−. 㪊.
(13) 㪊 㪉 㪈 㪄㪊. 㪄㪉. 㪄㪈. 㪇 㪄㪈 㪇. 㪈. 㪉. 㪊. 㪄㪉 㪄㪊. 図 13: + = 0.1 の近似曲線. 㪊 㪉 㪈 㪄㪊. 㪄㪉. 㪄㪈. 㪇 㪄㪈 㪇. 㪈. 㪉. 㪊. 㪄㪉 㪄㪊. 図 16: Hilbert 曲線 H5 と H6 の + = 0.05 での近似 曲線. 図 14: + = 0.01 の近似曲線. 図 15: Hilbert 曲線 H6. 図 17: Hilbert 曲線 H4 と H6 の + = 0.1 での近似 曲線. 7 −15−.
(14) 参考文献 [APMW 02] Pankaj Agarwal, Sariel Har-Peled, Nabil H.Mustafa, Yusu Wang. NearLinear Time Approximation Algorithms for Curve Simplification in Two and Three dimensions. Proc. of the 10th European Symposium on Algorithms (ESA’02),2002.. 図 18: Hilbert 曲線 H3 と + = 0.25 の近似曲線. [II 88]. H.Imai and M.Iri. Polygonal approximations of a curve-formulations and algorithms. In G.T.Toussaint, editor, Computational Morphology, pages 71-86. North-Holland, Amsterdam, Netherlands, 1988.. [God 91]. M.Godau. A natural metric for curves: Computing the distance for polygonal chains and approximation algorithms. In proc. of the 8th Annual Symposium on Theoretical Aspects of Computer Science, pages 127-136, 1991.. [HS 94]. J.Hershberger and J.Snoeyink. An O(n log n) implementation of the Douglas-Peucker algorithm for line simplification. In Proc. 10th Annual ACM Symposium on Computational Geometry, pages 383-384, 1994.. の頂点数は、それぞれ 14 個、42 個であり、いずれ も、頂点数を減らして、オリジナルに近い曲線を 得ることができている。 また、図 16、図 17、図 18 を見ると、H6 の近 似曲線として、H5 、H4 、H3 に近い図形が得られ ていることが分かる。Hilbert 曲線 Hn は、Hn−1 を利用して再帰的に作られているので、誤差 + で 近似すると、Hk (k ≤ n) の曲線が得られることが 推測される。これらの結果より、複雑な曲線でも、. FrechetSimp 法の実効性を確認することができる。. 4. まとめ. Fr´echet 誤差測定法に二分探索法を導入したこと で、計算時間を O(n log n) に改善し、複雑な曲線 に関しても、その実効性を確かめることに成功し た。今後の課題としては、データ構造を活用する ことで、より高速なアルゴリズムを構築すること、 より良い誤差測定法を提案することが挙げられる。. 8 −16−.
(15)
関連したドキュメント
A nearly best-Possible approximation algorithm for node-weighted Steiner trees. Spider covering algorithms for network
As a consequence of the transport-entropy inequalities obtained for the laws at a given time step of Euler like schemes and stochastic approximation algorithm, we will
Recently Verma [21] introduced an iterative scheme characterized as an auxiliary variational inequality type of algorithm and applied to the approximation-solvability of a class
O’Regan, “A Lefschetz fixed point theorem for admissible maps in Fr´echet spaces,” Dynamic Systems and Applications, vol.. G ´orniewicz, Topological Fixed Point Theory of
In the second computation, we use a fine equidistant grid within the isotropic borehole region and an optimal grid coarsening in the x direction in the outer, anisotropic,
In order to demonstrate that the CAB algorithm provides a better performance, it has been compared to other optimization approaches such as metaheuristic algorithms Section 4.2
1 Miko laj Marciniak was supported by Narodowe Centrum Nauki, grant number 2017/26/A/ST1/00189 and.. Narodowe Centrum Bada´ n i Rozwoju, grant
Having this product and a product integral in a Fr´ echet space (see [6]), we obtain the exact formula (11) for the solution of problem (1), being an extension of a similar formula
