Ramer–Douglas–Peucker Algorithm

RedisLiveのソースコードを読んでいると、時系列データのプロットに Ramer–Douglas–Peucker アルゴリズムというのが使われていた。
大量のデータがあるとき、それらをすべてつなげて曲線をひくのではなく、うまく間引いて元の曲線に近似させるアルゴリズム。“iterative end-point fit algorithm”“split-and-merge algorithm” などとも呼ばれる。

Algorithm

アルゴリズムそのものは以下のようにものすごくシンプル。

  1.  先頭と最後の点をプロット対象にする。
  2.  この2点で線をひく。
  3.  線から近似精度(ε)以上離れた点を探し、その中で最も遠い点をプロット対象にする。
  4.  プロット対象の各点を線でつなげる。
  5.  再帰的に ステップ3とステップ4を繰り返す。

この流れをまとめると下図のようになる。(wikipedia より)

Smoothing a piecewise linear curve with the Douglas–Peucker algorithm.

wikipedia の擬似コードは、クイックソートと同じ要領で再帰的に近似曲線を求めている。

function DouglasPeucker(PointList[], epsilon)
 //Find the point with the maximum distance
 dmax = 0
 index = 0
 for i = 2 to (length(PointList) - 1)
  d = PerpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
  if d > dmax
   index = i
   dmax = d
  end
 end

 //If max distance is greater than epsilon, recursively simplify
 if dmax >= epsilon
  //Recursive call
  recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
  recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

  // Build the result list
  ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
 else
  ResultList[] = {PointList[1], PointList[end]}
 end

 //Return the result
 return ResultList[]
end

Distance from a Point to a Line

少し頭を使うのは、2点x_1, x_2 を通る直線と点 x_0 との距離 d を求めるところ(上の擬似コードでは PerpendicularDistance 関数)。
最短距離 d は ベクトル x_2 – x_1 と 点 x_0 を通るベクトルが直行するときなので、この2つの内積が 0 になり、、、というように高校数学を思い出せばOK。(正射影とか外積とか懐かしい)

Example

程よく歯抜けがあり上下に変動する時系列データとして、数カ月分の基礎代謝のデータ(データ数は100)が手元にあったので、それを利用してプロット対象の点の数を増やしていったのが下のアニメーション。

上のアニメーションではアルゴリズムを少しいじり、近似精度を利用せず最遠点を求め、それを近似曲線対象にしている。点の数が n=2 から100 までの各画像を R で作成し、ImageMagick でアニメーション gif 化した。($ convert -delay 20 -loop 0 *gif rdp.gif)

Advertisements
Tagged with: , ,
Posted in algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 6 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 6 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 6 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 1 year ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago
%d bloggers like this: