2011年3月1日火曜日

GPSのログを間引く(折れ線を間引く)

先日,オークションサイトの eBay で TripMate850 という GPS ロガーを買ってみた。昔のネット上の記事だと 79 ドルで買えたそうだが,今回は送料として 20 ドル上積みされて 99 ドルで買った。さて,性能はというと,結構これがいい感じ。やっぱデジカメについているようなものとは質が違う。きっと GPS 用のチップやアンテナも良くなってきてるに違いない。

さて,ここからが本題。TripMate850 は,ログを1秒間隔,5秒間隔,15秒間隔,30秒間隔,5分間隔,10分間隔,と記録できる。他にもスマートログと称して,30km/h以上だと5秒間隔,4km/h以上なら10秒間隔,4km/h未満なら15秒間隔,と記録するモードもある。私の場合はバイクでのツーリングの記録に使いたいと思っている。さすがに1秒間隔のログはいらないのでは?と思っている。スマートログもよいけど,5秒間隔のログがいいような気がしているが,まだ長距離を走ってのログがないので,これからちょこちょこ調べようと思っている。

それでは,5秒間隔でログを取ると,ログはどれぐらいの量になるのだろうか? 5秒間隔なら,1分間で12点1時間なら720点となる。12時間なら8640点24時間だと17280点になる。ログは1点につき,以下のように数行のデータをテキストファイルとして記録している。
$GPGGA,025020.000,35xx.yyyy,N,135yy.zzzz,E,2,8,1.16,99.3,M,34.6,M,0000,0000*62
$GPGSA,A,3,XX,XX,XX,XX,XX,XX,XX,XX,,,,,2.16,1.16,1.82*01
$GPGSV,3,1,10,XX,83,025,42,XX,55,038,31,XX,54,301,47,XX,49,118,26*7A
$GPGSV,3,2,10,XX,49,172,33,XX,32,207,39,XX,26,085,29,XX,22,119,29*73
$GPGSV,3,3,10,XX,19,040,32,XX,17,316,16*79
$GPRMC,025020.000,A,35xx.yyyy,N,135yy.zzzz,E,0.07,0.00,240211,,,D*69
ここでは6行になっているが,あくまでこれで一点を表している。最初の GGA というは,時刻,緯度,経度,高度や,補足できたGPS衛星の個数や,信号の質などの情報を表している。GSA は測位モード,受信衛星数,信号の質などの情報(GGAとダブっている),GSV は各衛星から得られた情報(1行に最大4衛星分),RMC は,時刻 (UTC),緯度経度,速度,日付などの情報を持った行,となっている。違う行に同じ情報がダブっていたりする。この例だと,受信衛星数が10個だったので,GSV行が3行となり,全体で6行で1点を表している。このようなものが測定点の数だけずらっと並んでいるのが GPS のログである。この例では,35xx.yyyy,N が緯度を表している。後ろに N の文字があるので,北緯 35 度 xx.yyyy 分,と読むらしい。なんかピリオドの位置と概念が微妙だけど…。念の為に一部データを伏字にしてみた。135yy.zzzz,E は経度である。ここでは東経 135 度 yy.zzzz 分となっている。また XX で示した部分には GPS 用の衛星の番号(?)が入っている。これがわかるとそれらの情報から位置が特定できると思って念の為に伏字にしてみた。詳しいことは NMEA で検索するといろいろ出てくるので,そちらを見てほしい。

さて,ログの量の話だが,上記の例で400バイト弱になる。つまり1点で 0.4kB 程度必要(衛星の数などによって行数,文字数は変化する)なので,12時間で3.5MB程度必要と見積もれる。24時間なら7MBとなる。1秒間隔なら,12時間で17.5MB程度必要と見積もれる。24時間なら35MBとなる。結構な量になるなぁ。これらをうまく何かに表示したいのだが,いいものとしては Google Map と Yahoo の RouteLab なるものがある。どちらも点情報を与えると,地図上に経路を表示してくれる。Google Map なら場所情報も載せてくれる。ただし,どちらにも点数に限りがあり,
Google Map : 経路の点と場所情報の点の合計が 1000 点以内
Yahoo RouteLab : 経路の点が 8000 点以内
となっている。まぁ,点が多いと何かと処理に時間がかかるので,1000点ぐらいが妥当なのかもしれない。となると,点を減らす(間引く)必要がでてくる。ログデータをコンピュータに取り込んで,何らかの処理を施して点数を減らし,Google Map や Yahoo RouteLab にアップする作戦である。それを今回は Perl でやってみた(しかし,ここで紹介できるようなきれいなものじゃないので,今回は概念だけの記述です)。ちなみに,TripMate850 には,付属で Photo Tagger というソフトがついてくるし,フリーで「轍(Wadachi)」というソフトが「サイクル紀行」というサイトにあるので,普通はそれらを使う方がよっぽどいいと思う。あくまで,これは趣味の一環として行った。

GPSのログの点を間引く方法はいくつかあるみたい。その前にまずは方針を決めないといけない。私の場合はバイクのツーリングでのログ記録を主眼において考える。ツーリングでは,道路自体の写真を撮ったり,風景を撮ったり,田舎の駅に行ってそこの写真を撮ったりする。また,コンビニや道の駅で休憩し,ガソリンを入れる。それらの点を WayPoint(中間地点あるいは停留点)として,残したい。また,経路は道の形が大体わかるようにスムースにつなげたい,と考えた。そこで,まずは
(1) 隣り合うGPSの記録点が近い場合は,一方を省略する。
  停まっていると連続で点が省略される。
(2) 同じ点にしばらく(数分以上?)いる時には,停留点とみなす。
(3) 写真を撮った場所も停留点とする。
という3つの条件を思い浮かべた。処理としては,ログデータを扱いやすいように配列に入れる。配列には,日付,時刻,緯度,経度,高度,速度などの残したいデータを入れる。それを元に,点を間引く。各点にレベルを設定して,レベルがマイナス(負)なら,表示しない,プラス(正)なら表示,ゼロなら処理待ち,としておいて,間引く条件に合えばレベルをマイナスに,逆に残す点として決まれば,プラスになるように設定することにした。間引きの処理中に間引いた点を配列から削除して配列の長さを変えると結構面倒なので,各点に表示レベルを設定して,最後に表示レベルに応じて出力させる,という方式にしてみた。

こうして,まずは上記の3つの条件を充たすようなプロセスを書いた。その際に,どれぐらいの範囲に入れば同じ地点と考えるか?という条件がある。私の場合は,角度で 0.0001 度,距離にして半径約 11 m 程度内にあれば同一点とすることにした。これは GPS の誤差が 3 m とか 10 m とかあるらしいので,今は半径 11 m を一つの基準にしている。また,停留点とみなすための時間は2分としている。これはもう少し長くてもいいかもしれない。また,自転車や山歩きだと値は違った方がいいかもしれない。これらの値をどうするのがよいのかは,今後の課題である。また,写真の情報は別に処理して,一覧を作成しているので,その表と GPS のログを照らし合わせて,写真に GPS 情報を加えたり,GPS の経路に停留点を加えたりしている。

追記)実は,距離についてはもう少し考察が必要だった。何かというと,経度方向の距離は,緯度によって異なる,という点。つまり,高緯度ほど(例えば北極の近くなど)経度で1度進んでも,地球上で進む距離は赤道上に比べるとかなり短くなってしまう。そこで,ヒュベニの公式を参考にして,経度方向だけ緯度による補正を(cos(緯度)みたいなのをかけている)施している。この補正をしなくても,ここで書かれている内容に関してはほぼ問題ない。しかし,計算で経路の距離をだそうと思うと,実際よりもかなり長くなってしまう。ヒュベニの公式の補正を入れると,計算上の経路は少しだけ短めにでた。これは経路を折れ線でつないでいるためだと思っている。いくつか例があるが,だいたい計算で求めた距離は実際の距離(メーター読み)の97.5%ぐらいになっていた。まぁ,ヒュベニの公式を使った計算の誤差が 1% ぐらいはあるから,こんなもんだということにしておこう。
 ちなみに,今回は「日本は山だらけ~ 技術研究本部」の二地点の緯度・経度からその距離を計算するを参考にさせていただいた。感謝,感謝!

さて,上記の条件に合うようにデータを間引くと,5秒間隔のログだとうまくいけば半分程度に点が減る(短い距離のデータからの類推。今後長いログで確認して訂正する予定)。しかし,長いログだとまだまだ地図に載せるには点が多すぎる。そこで,前後の点へのベクトルを考えて,その方向が同じなら間引く,とか,11 m よりも大きな半径の点も間引く,などを考えて実行してみたが,いまいちしっくりこない。そこでネットで調べていると,Douglas-Peuckerのアルゴリズムというのがあるのを知った。それはどんなものかというと,
(1) 経路は,点を結んだ折れ線で出来ていると考え,経路を重みの大きい点(分割点)で分割していく。
  分割点が最終的に表示される点となる。表示点(分割点)の数が必要な数になるまで,分割を繰り返す。
(2) 最初は全経路が一つの区間,と考える。
  始点と終点が同じ場合(距離がとても近い場合)は,始点からの距離が一番遠いものを分割点として,
  区間を2つに分け,それぞれに対して処理を行う。
(3) 区間の始点と終点を結ぶ直線を考え,区間内の各点からのその直線までの距離を求める。
(4) 直線からの距離がある範囲(許容範囲)を超える点が区間内に一点でもあれば,
  直線からの距離が最大の点を「1つ」新たに分割点とする。
  結果として,経路はより細かく分割される。
(5) もし,区間内の全ての点で直線の距離が許容範囲に入っていれば,
  その区間の内部の点は全て省略してもよいと考え,始点と終点だけを経路の分割点として残す。
(6) 必要に応じて,再び経路内にある全ての区間(細分化された区間)に対して,(2)~(4)の処理を行い,分割点を増やす。
  分割点の合計が必要な数に達するまで,何度でも分割点を増やし,経路を細分化する作業を繰り返す。
という感じのもの。手順自体はあまり複雑じゃないけど,2つの分割点の間に引いた線と経路上の一点との距離を求めるのがややこしそう。でもこれは意外と簡単で,分割点の座標をそれぞれ (x0, y0), (x1, y1) とし,経路上の一点の座標を (X, Y) と置くと,
a = sqrt((x1-x0)^2 + (y1-y0)^2)
b = sqrt((X-x0)^2 + (Y-y0)^2)
ab = (X-x0)(x1-x0) + (Y-y0)(y1-y0)
l = sqrt(b^2 - ab^2/a^2) <== これが欲しい結果
と書ける。この式を使うと意外と簡単に Douglas-Peuckerのアルゴリズムを実現できる。Douglas-Peuckerのアルゴリズムを使う際の許容範囲(各点の直線からの距離のずれ幅の許容範囲)として,今は角度で 0.00005 度(距離で約 5 m)を採用している。これもまだ試行錯誤の段階である。

追記)ここでも,距離についての補足が必要。上の方でヒュベニの公式を参考にして,経度方向だけ緯度による補正をしたと書いた。当然,線分からの距離の計算でも緯度による補正が必要になる。ここでは,経度方向の位置を表す x0, x1, X を求める時に,cos(緯度)をかける,という処理をしておいた。あまり正確ではないと思うが,線分からの距離は点を間引く基準にしているだけなので,そんなに精度はいらないということでよしとしておいた。

繰り返しの回数だが,単純に1回ごとに区間数が2倍に増えると考えると,10回分割を行うと,区間数は 1024 になる。ログが長いと一回の処理にかかる時間が長くなるので,ある程度時間がかかるかもしれない。なので,極力,表示しないとした点は処理しないように if 文で条件分けをして処理するのがいいと思う。また,点の数や経路によっては,何回か分割を行うと,分割点の数がほしい数になる前に,それ以上分割できなくなる。その場合は処理を止めれるようにしないといけない。

さて,Perl でスクリプトを作っては見たが,まだバイクでも車でも長距離を走っていない。早く紀伊半島をツーリングして,このスクリプトを実際に応用してみたい,と思っている。

GPSの経路ログ表示にGoogle Maps API V3 を使う (その1:KML ファイルを作る) に続く)

長距離走った時の GPS ログを間引いた結果の報告 に,実際にバイクで走った際の処理の結果について書いておいた。

0 件のコメント: