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
%d bloggers like this: