2008/01/21
経路やエリア情報の圧縮技術を開発、特許出願しました。LocaParam改めLocaPorter。
先のジオメディア２００８新年会で発表していたのですが、昨年9月から、
・経路
・領域
・複数地点
など、緯度経度の複数セット情報を短いテキストに圧縮する圧縮技術を開発し、先週特許出願いたしました。（プレスリリース）
元々は、URL文字数制限の厳しい携帯サイト用のURLに、何点もの緯度経度を入れたい、という話を聞き、ロカポDIYマップで使っているURL圧縮仕様（今は亡きロカポ仕様Ver1.0の圧縮拡張フォーマット）をベースにスタート、ああすればもっと短くなるのでは？、こうすればどうだ？などいろいろ試行錯誤していました。一方、情報圧縮理論もちゃんと勉強してバイナリレベルで究極に圧縮できればどのくらいまで小さくなるだろう？など。結構おもしろかったです。
サイズだけを追求すれば
１．緯度経度を整数にする
２．差分をとってバイナリで表す
３．ワイル符号化、γ符号化、σ符号化などの手法で2進数にする
４．ホフマン符号化、LZ法などで情報圧縮
とやれば小さくなります。
でももっと使い勝手と、携帯やPDAのCPUでも軽～く圧縮・解凍できて、しかも実装も簡単なのが望ましい。ということで、試行錯誤の上にできたのが、今回の圧縮技術です。
これまでは、経路やエリアなどを扱うにはデータベースやKMLファイルを使うことがほとんどだったと思います。この圧縮技術では位置情報をテキスト文字列に圧縮します。
ＱＲコード、ＲＦ－ＩＤ（ＩＣカード）、URL文字列、低速パケット通信回線、赤外線通信など、文字数や容量の制約が厳しい媒体でどんどん使ってください。
ＵＲＬに使っても％ＸＸとＵＲＬエンコードされてしまうと、せっかくの1文字が3文字になるケースがあります。そうならないよう、ＵＲＬエンコード対象外の64文字のみで圧縮データは表現されます。それに６４という数字はあとからバイナリにしてさらに圧縮、、、とかやりたくなったときでも無駄なビットロスがないですし。
位置情報圧縮技術の主な特徴です。
①軽量な圧縮アルゴリズムですが、ホフマン符号等を駆使した場合の約６０％くらいの能力はあります。サンプルの経路データでテストした結果です。
・５箇所の緯度経度 →約２２％に圧縮
・６０箇所の緯度経度 →約１３％に圧縮
・１２００箇所の緯度、経度、高度 →約８％に圧縮
（弊社実験結果より。データの内容により圧縮率は異なる）
②オン・ザ・フライ処理
符号化、復号化とも先頭から順にデータを追加していく方式なので、測位しながら記録し、さらに途中で電源が切れるようなケースでも、すでにあるデータにどんどん追加可能です。
③精度の違うデータの混在が可能
これが目玉です！最後までバイナリレベルのサイズ優先と、バランス優先の二本立てにしようかどうか迷っていたのですが、このメリットが無いことでサイズ優先の選択肢が消えました。
同じ経路でも、精度１ｍで情報を取るのと、精度１０ｍで情報を取るのでは、元の精度を再現するのに必要な情報量は当たり前ですが10倍になります。
仮に海外旅行の旅行記をとるとして、飛行機の飛行経路は一応残したい、立ち寄ったお店の情報はピンポイントの精度が欲しい、となると「広範囲×高精度」でデータ容量はとても多くなってしまいます。元データそのものが大きいので、いくら圧縮しても限界があります。だから通常、このような場合は精度のことなる別々のデータとして、それぞれ圧縮することになります。
この圧縮技術では、一つの経路やエリア情報の中で、精度の異なるデータの混在が可能です。さらに、復号する際に、圧縮時の精度情報も取得できます。
カーナビなどではマップマッチングの技術があり、経路情報はある程度ルートを外れても道路上に戻してくれます。これを利用して、マップマッチングを前提に、ルート情報はかなり情報量を落として容量を節約しつつ、出発地、経由するお店、目的地は１ｍのピンポイント精度で表現する、ということが可能です。
圧縮の効果単独で、たとえばパケット量を減らしてレスポンスを上げるとか、そういう用途にどんどん使って頂きたいのですが、それよりも位置情報サービス同士の連携に使って欲しいと考えています。
そもそも
現在地→周辺情報
が１：Nなのに対して
現在経路→経路沿い情報
では N:Nになるので、通常の
GET/POSTで送信→XML/JSONで受信 のよう単純なデータの流れは難しい。
例えばルート検索後、ルートに沿ったレストランを検索したい場合、ルート情報がデータベースに入っている限り、通常他社サービスからのアクセスはできません。必然的に、こういった複合サービスを提供したい場合は、ワンストップサービスとなり、一つのサイトでルート検索も、路線検索も、ホテル検索も、レストラン検索も、、、ということになりがちです。
でも一般のＩＴの世界では、All in one のポータルサイトより、各ジャンルに特化したサイト同士がマッシュアップする時代です。百貨店より専門店です。位置情報系のサービスだけが百貨店戦略を続けるのは難しい。
そこで、検索した経路や、地図上にマウスで描いたエリアなど、この圧縮技術で一つの文字列にパラメータ化できます。そうして位置情報系サイト同士のマッシュアップが簡単にできるようになれば、どんな斬新なサービスが出てくるのか想像もできません。なぜなら、今の現状ではただ一箇所だけの情報（現在地とか地図の中心とか）でさえ、サービス間連携している例は少ないからです。
だからこのサービスを圧縮ではなく、連携を前面に打ち出して「LocaPorter」という名称にしました。
ジオメディア２００８では「LocaParam」という名前で発表していましたが、パラメータというより、各サービスで使った位置情報を他のサービスへ自由に「持ち運ぶ入れ物」というコンセプトがぴったりで、こちらにしました。それにLocaPointの名付け親のネーミング・コンサルタントからLocaParamは英語的ではちょと、というアドバイスをもらい、LocaPorterはＯＫもらったのと、別の方から「ロカポ」という音が入ってた方がいいという意見も頂いたので。
この位置情報圧縮技術、１月末か2月始めまでにドキュメントなどを整備して、ライセンス販売と導入支援を開始する予定です。
技術の詳細な内容は当面はＮＤＡ前提の公開となりますが、ロカポと同じように、近いうちにオープンにしたいと考えています。
ＬｏｃａＰｏｒｔｅｒをどうぞよろしくお願いいたします。
・経路
・領域
・複数地点
など、緯度経度の複数セット情報を短いテキストに圧縮する圧縮技術を開発し、先週特許出願いたしました。（プレスリリース）
元々は、URL文字数制限の厳しい携帯サイト用のURLに、何点もの緯度経度を入れたい、という話を聞き、ロカポDIYマップで使っているURL圧縮仕様（今は亡きロカポ仕様Ver1.0の圧縮拡張フォーマット）をベースにスタート、ああすればもっと短くなるのでは？、こうすればどうだ？などいろいろ試行錯誤していました。一方、情報圧縮理論もちゃんと勉強してバイナリレベルで究極に圧縮できればどのくらいまで小さくなるだろう？など。結構おもしろかったです。
サイズだけを追求すれば
１．緯度経度を整数にする
２．差分をとってバイナリで表す
３．ワイル符号化、γ符号化、σ符号化などの手法で2進数にする
４．ホフマン符号化、LZ法などで情報圧縮
とやれば小さくなります。
でももっと使い勝手と、携帯やPDAのCPUでも軽～く圧縮・解凍できて、しかも実装も簡単なのが望ましい。ということで、試行錯誤の上にできたのが、今回の圧縮技術です。
これまでは、経路やエリアなどを扱うにはデータベースやKMLファイルを使うことがほとんどだったと思います。この圧縮技術では位置情報をテキスト文字列に圧縮します。
ＱＲコード、ＲＦ－ＩＤ（ＩＣカード）、URL文字列、低速パケット通信回線、赤外線通信など、文字数や容量の制約が厳しい媒体でどんどん使ってください。
ＵＲＬに使っても％ＸＸとＵＲＬエンコードされてしまうと、せっかくの1文字が3文字になるケースがあります。そうならないよう、ＵＲＬエンコード対象外の64文字のみで圧縮データは表現されます。それに６４という数字はあとからバイナリにしてさらに圧縮、、、とかやりたくなったときでも無駄なビットロスがないですし。
位置情報圧縮技術の主な特徴です。
①軽量な圧縮アルゴリズムですが、ホフマン符号等を駆使した場合の約６０％くらいの能力はあります。サンプルの経路データでテストした結果です。
・５箇所の緯度経度 →約２２％に圧縮
・６０箇所の緯度経度 →約１３％に圧縮
・１２００箇所の緯度、経度、高度 →約８％に圧縮
（弊社実験結果より。データの内容により圧縮率は異なる）
②オン・ザ・フライ処理
符号化、復号化とも先頭から順にデータを追加していく方式なので、測位しながら記録し、さらに途中で電源が切れるようなケースでも、すでにあるデータにどんどん追加可能です。
③精度の違うデータの混在が可能
これが目玉です！最後までバイナリレベルのサイズ優先と、バランス優先の二本立てにしようかどうか迷っていたのですが、このメリットが無いことでサイズ優先の選択肢が消えました。
同じ経路でも、精度１ｍで情報を取るのと、精度１０ｍで情報を取るのでは、元の精度を再現するのに必要な情報量は当たり前ですが10倍になります。
仮に海外旅行の旅行記をとるとして、飛行機の飛行経路は一応残したい、立ち寄ったお店の情報はピンポイントの精度が欲しい、となると「広範囲×高精度」でデータ容量はとても多くなってしまいます。元データそのものが大きいので、いくら圧縮しても限界があります。だから通常、このような場合は精度のことなる別々のデータとして、それぞれ圧縮することになります。
この圧縮技術では、一つの経路やエリア情報の中で、精度の異なるデータの混在が可能です。さらに、復号する際に、圧縮時の精度情報も取得できます。
カーナビなどではマップマッチングの技術があり、経路情報はある程度ルートを外れても道路上に戻してくれます。これを利用して、マップマッチングを前提に、ルート情報はかなり情報量を落として容量を節約しつつ、出発地、経由するお店、目的地は１ｍのピンポイント精度で表現する、ということが可能です。
圧縮の効果単独で、たとえばパケット量を減らしてレスポンスを上げるとか、そういう用途にどんどん使って頂きたいのですが、それよりも位置情報サービス同士の連携に使って欲しいと考えています。
そもそも
現在地→周辺情報
が１：Nなのに対して
現在経路→経路沿い情報
では N:Nになるので、通常の
GET/POSTで送信→XML/JSONで受信 のよう単純なデータの流れは難しい。
例えばルート検索後、ルートに沿ったレストランを検索したい場合、ルート情報がデータベースに入っている限り、通常他社サービスからのアクセスはできません。必然的に、こういった複合サービスを提供したい場合は、ワンストップサービスとなり、一つのサイトでルート検索も、路線検索も、ホテル検索も、レストラン検索も、、、ということになりがちです。
でも一般のＩＴの世界では、All in one のポータルサイトより、各ジャンルに特化したサイト同士がマッシュアップする時代です。百貨店より専門店です。位置情報系のサービスだけが百貨店戦略を続けるのは難しい。
そこで、検索した経路や、地図上にマウスで描いたエリアなど、この圧縮技術で一つの文字列にパラメータ化できます。そうして位置情報系サイト同士のマッシュアップが簡単にできるようになれば、どんな斬新なサービスが出てくるのか想像もできません。なぜなら、今の現状ではただ一箇所だけの情報（現在地とか地図の中心とか）でさえ、サービス間連携している例は少ないからです。
だからこのサービスを圧縮ではなく、連携を前面に打ち出して「LocaPorter」という名称にしました。
ジオメディア２００８では「LocaParam」という名前で発表していましたが、パラメータというより、各サービスで使った位置情報を他のサービスへ自由に「持ち運ぶ入れ物」というコンセプトがぴったりで、こちらにしました。それにLocaPointの名付け親のネーミング・コンサルタントからLocaParamは英語的ではちょと、というアドバイスをもらい、LocaPorterはＯＫもらったのと、別の方から「ロカポ」という音が入ってた方がいいという意見も頂いたので。
この位置情報圧縮技術、１月末か2月始めまでにドキュメントなどを整備して、ライセンス販売と導入支援を開始する予定です。
技術の詳細な内容は当面はＮＤＡ前提の公開となりますが、ロカポと同じように、近いうちにオープンにしたいと考えています。
ＬｏｃａＰｏｒｔｅｒをどうぞよろしくお願いいたします。
# posted by Nao : 04:55
