JP5534007B2

JP5534007B2 - 特徴点検出システム、特徴点検出方法、及びプログラム

Info

Publication number: JP5534007B2
Application number: JP2012514747A
Authority: JP
Inventors: 伸治加美
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2010-05-12
Filing date: 2011-04-21
Publication date: 2014-06-25
Anticipated expiration: 2031-04-21
Also published as: US20130054602A1; WO2011142225A1; US8938357B2; JPWO2011142225A1

Description

本発明は、ＧＰＳログデータにおける特徴点検出システム、特徴点検出方法、及びプログラムに関する。

近年、スマートフォンやＧＰＳロガーなどの普及により、ユーザが外出の際、容易にＧＰＳ（ＧｌｏｂａｌＰｏｓｉｔｉｏｎｉｎｇＳｙｓｔｅｍ）データを取得することができるようになった。また、取得したＧＰＳデータを地図上にマップするコンピュータプログラムを用いて外出の軌跡を表示し、ブログなどにアップロードして公開するといったことも行われている。このようなプログラムとしては、地図情報がすでに登録されたパッケージソフトウェアや、ＩＳＰ（ＩｎｔｅｒｎｅｔＳｅｒｖｉｃｅＰｒｏｖｉｄｅｒ）や各種提供されているＡＰＩ（ＡｐｐｌｉｃａｔｉｏｎＰｒｏｇｒａｍＩｎｔｅｒｆａｃｅ）などを用いてサーバにログデータをアップロードし、Ｗｅｂブラウザを用いて地図上に軌跡を表示するものなど様々な形態が存在する。これらのソフトウェアはいずれもＧＰＳシステムを用いて取得された測地座標データ及び時刻などのデータ（以後、ＧＰＳログデータと記す。）を地図などの視覚的情報として表示するものである。

しかし、一般にＧＰＳログデータは、一定の時間間隔で取得する等、一定のルールに従って機械的に取得されたデータであり、各データポイント自体は一地点としての意味しか持たないため、それらを地図上に表示しても取得されたデータポイントの軌跡を表示できるにすぎない。そのため、ＧＰＳログデータを利用する場合、ユーザはデータを加工する必要があることが多い。データを加工する典型的な例として、ユーザが旅行したときの情報をブログで公開する場合、訪問した先や、道中で立ち寄ったレストランや、写真を撮ったランドマーク等、他の場所に比べて重要な意味を持つ場所（以後、ウェイポイントと記す。）を、地図上で特に強調したり、そのポイントにリンクを張って関連情報を追加したりする場合がある。

ＧＰＳログデータを再加工するための従来の方法として、ユーザによる手動編集とコンピュータプログラムによる自動処理がある。ユーザによる手動編集は、例えばＧＵＩインターフェースを用いて地図上の該当する場所をマウスポインタなどで選択し、直感的にウェイポイントの追加や編集を行うものである。これにより、ユーザはＧＰＳログデータの軌跡がプロットされた地図を見ながら、自分の記憶をもとに自由にウェイポイントを作成することができる。

また、コンピュータプログラムによる自動処理としては、例えばデータベースとの連携がある。データベースにレストランや観光スポットなどのウェイポイントの候補となるスポットをあらかじめ登録しておき、ＧＰＳログデータの軌跡の中から、登録されているスポットと距離的に近い領域を候補として抽出する。さらに、何らかのポリシーに基づいて、抽出された候補の中からいくつかの候補を表示してユーザに選択させる。例えば、各スポットを人気順で序列化しておいて上位Ｎ個を表示するといった方法が考えられる。

また、コンピュータプログラムによる自動処理の他の例としては、速度や加速度が大きく変化した地点を検出して表示する方法もある（非特許文献１〜３）。この方法によれば、例えば徒歩での移動から車や電車での移動に変わった地点を検出することができるので、交通要所やショッピングセンターなどを表示させることが可能である。

D. Ashbrook and T. Starner, "Using GPS to learn significant locations and predict movement across multiple users", Personal and Ubiquitous Computing, 7(5), 2003 Hariharan, R., Toyama, K., "Project Lachesis: parsing and modeling location histories", M.J. Egenhofer, C.Freksa, and H.J. Miller (Eds.): Geographic Information Science 2004, LNCS 3234, pp106-124 Yu Zheng and Xing Xie, "Learning Transportation Mode from Raw GPS Data for Geographic Application on the Web", Association for Computing Machinery, Inc., 20 April 2008

しかし、従来の方法では、効率的かつ応答性に優れた精度の高いウェイポイントの表示は困難である。ユーザによる手動編集では、ユーザの記憶をもとに該当する場所を地図上の軌跡から抽出する必要があるが、一般にそれは煩雑な作業である。なぜならば、立ち寄った全ての場所を地図上で正確に位置付けることは簡単なことではないからである。

また、データベースとの連携による方法においても、ウェイポイントとなりうる場所はユーザによって異なり、また同じユーザでもその時々で重要な意味を持つ場所は異なるため、予めウェイポイント候補を登録したデータベースを用いてユーザ毎に適切なウェイポイントを選択することは困難である。そのため、ウェイポイントの検出精度は必ずしも高いとは限らない。

さらに、原理的にはＧＰＳログデータの全てのポイントとデータベースに登録されている全てのポイントについて両者の距離を計算しなくてはいけないため非常に計算コストがかかる。ＧＰＳログデータの軌跡の範囲を最初に検出してその範囲に検索範囲を限定する、ユーザの趣向情報などに基づいて検索範囲を絞る、など計算量を削減する方法も考えられるが、データ量の増大に対して計算量が非線形的に増大していくため、規模の大きいデータベースやＧＰＳログデータを対象とする場合には処理時間がかかることが予想される。

また、速度や加速度の変化点を検出する手法では、一般に閾値を用いて変化が大きいか否かを判定するが、様々なＧＰＳログデータに対応した適切な閾値を見つけることは一般に困難であり、ノイズの影響なども受けやすい。より精度を高くするためには、閾値を用いた判定処理の後、さらに候補の絞り込み処理などが必要となり、処理が複雑化する。

本発明の目的は、ＧＰＳログデータから、適切なウェイポイントを精度良く高い応答性で検出することが可能な特徴点検出システム、特徴点検出方法、及びプログラムを提供することである。

本発明に係る特徴点検出システムは、ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいてそのクラスターにおけるユーザの滞留時間を示す指標を決定し、前記指標に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成する滞留エリア検出部であって、前記滞留時間が長いほどそのクラスターが高い確率で抽出される、滞留エリア検出部と、抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を１つずつ抽出すると共に、各々の前記滞留エリア内の前記データポイントの密集度に基づいて、各々の前記代表点のスコアを決定する代表点抽出部と、前記スコアに基づいて、各々の前記代表点を序列化したリストを出力する代表点序列化部と、を備えたものである。

本発明によれば、ＧＰＳログデータから、適切なウェイポイントを精度良く高い応答性で検出することができる。

本発明の実施の形態によるＧＰＳログデータの特徴点検出システムの構成を示すブロック図。本発明の実施の形態による滞留エリア検出部の構成を示すブロック図。本発明の実施の形態による滞留エリア検出部による滞留エリア検出動作を説明する図。２つのデータポイントが衝突する確率を示したグラフ。２つのデータポイントが衝突する確率を示したグラフ。本発明の実施の形態による本発明の多重化ラベルの比較演算を説明する図。本発明の実施の形態による滞留エリア検出手法を説明する図。本発明の実施の形態によるデータポイントの再構成・グループ化処理を説明する図。本発明の実施の形態によるクラスター化部の動作のフローチャート。本発明の実施例の構成を示すブロック図。

次に、本発明を実施するための形態について、図面を参照して詳細に説明する。
図１は、本発明の実施の形態によるＧＰＳログデータの特徴点検出システム１００の構成を示すブロック図である。図１に示すように、特徴点検出システム１００は、入力部１００２、滞留エリア検出部１００３、代表点抽出部１００４、及び出力部１００５を備えている。入力部１００２、滞留エリア検出部１００３、代表点抽出部１００４、及び出力部１００５は、プログラムに従ってコンピュータのプロセッサが行う動作のモジュールを表している。

入力部１００２は、入力されたＧＰＳログデータ１００１から位置情報と時間情報を含む各データポイントの情報（以後、データポイント情報と記す。）を取得し、演算処理が可能な形式に変換する。

ＧＰＳログデータ１００１は、ＧＰＳシステムを介して取得した、ＧＰＧＧＡなどのデータ形式で記述されたデータである。ＧＰＳログデータは、少なくとも位置情報と時間情報を含む。さらに好ましくは、ＧＰＳログデータ１００１は、ＧＰＳシステムによって測定された少なくとも緯度、経度、高度、及び測定時間情報を含むデータの集合である。

滞留エリア検出部１００３は、変換後のデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいてそのクラスターにおけるユーザの滞留時間を示す指標を決定し、指標に基づいて１以上のクラスターを抽出し、抽出したクラスターに基づいてユーザの滞留エリアを形成するものであって、滞留時間が長いほどそのクラスターが高い確率で抽出される。ユーザが一定時間滞留したとみなせるエリア（以後、滞留エリアと記す。）は、データポイントが時間的空間的に密集しているため、データポイントの密度が高いエリアほど高い確率で検出される。

代表点抽出部１００４は、滞留エリア検出部１００３によって検出された滞留エリアの中から、その滞留エリアを代表する点をウェイポイントとして抽出する。代表点は、典型的には、エリア内で一番中心にあるポイントである。例えば、代表点抽出部１００４は、エリア内の全てのデータポイントまでの距離の平方和が最低になる点を選ぶ。このポイントはエリア内の全データポイントの平均値であり、その位置に実際にデータポイントが存在するとは限らない。実際に存在するデータポイントの中から選ぶ場合は、代表点抽出部１００４は平均値から一番近いデータポイントを選べばよい。

また、代表点抽出部１００４は、選択したウェイポイントのスコアを計算する。スコアは、エリア内のデータポイントの密集度合いが高いほど高いスコアとなるように設定する。

スコア算出方法の例について説明する。まず代表点抽出部１００４は、エリア内のデータポイント数が多いウェイポイントほど高いスコアを設定する。さらに、ウェイポイントからエリア内の全てのデータポイントへの平方距離の和（もしくは平均）に基づいて、エリア内のデータポイント数が同じでも、密集度が高い（平方距離の和が小さい）ものほど、より高いスコアを設定する。

出力部（代表点序列化部）１００５は、代表点抽出部１００４によって算出されたスコアに基づいて序列化されたウェイポイントのリスト（ＷＰＴリスト１００６）を出力する。

ＷＰＴリスト１００６は、地図アプリケーション１００７など、ＷＰＴリスト１００６を利用するコンピュータプログラムに合わせて生成されたウェイポイントのリストである。ＷＰＴリスト１００６は、例えばＨＴＭＬやＸＭＬなどのマークアップ言語で記述され、タグによって定義されたフォーマットのデータや、ＣＳＶなどのフォーマットのデータを含んでいる。

地図アプリケーション１００７は、地図上に、ＧＰＳログデータ１００１から得られる軌跡情報とＷＰＴリスト１００６から得られるウェイポイント情報を合わせた画像表示を行うための出力データ１００８を生成するソフトウェアプログラムである。地図アプリケーション１００７は、必要に応じて、インターネットなどを通して提供されているＡＰＩを用いてもよい。

出力データ１００８は、ユーザがウェイポイントを視覚的に認識できるように生成されたグラフィックデータである。出力データ１００８は、例えばＧＰＳログデータ１００１から得られた軌跡データを地図上に表示し、その軌跡上にＷＰＴリスト１００６に含まれるウェイポイントを強調して表示するためのものである。

次に、滞留エリア検出部１００３について詳細に説明する。
なお、ここでは緯度、経度、高度からなる３次元空間を考えるが、次元数はこれに限られない。例えば、時間を加えた４次元空間に拡張するなど、その空間における２点間の距離の近さを点の密集度と対応付けられるならば、次元を増やしてもよい。特に、時間的に近いことは滞留という意味では重要であり、時間の差を空間的な距離の差に変換して時間軸を考慮することが可能である。

図２は、滞留エリア検出部１００３の構成を示すブロック図である。図に示すように、滞留エリア検出部１００３は、確率的ヒストグラム化部２００１、クラスター化部２００２、再構成・グループ化部２００３を備えている。確率的ヒストグラム化部２００１は、連結ヒストグラム作成部２００４、及び多重化ラベル計算部２００５を備えている。多重化ラベル計算部２００５は、複数のラベル計算部２００６を備える。再構成・グループ化部２００３は、サンプリング部３００１とグループ化部３００２を備える。

図３を用いて、滞留エリア検出部１００３による滞留エリア検出動作を詳細に説明する。
確率的ヒストグラム化部２００１は、ＧＰＳログデータ１００１の入力に対して、連結ヒストグラム２００７を計算する。

確率的ヒストグラム化部２００１は、データポイント同士の距離が近いほど高い確率で同じビン（階級）に登録されるようにデータを分類し、ヒストグラム化する。これにより、データポイントが密集するエリアに属するデータポイントがより高い確率で同じビンに登録されるため、データポイントが登録される頻度の高いビンから順にサンプリングしていくことで、データポイントが密集するエリアを効率的に抽出することが可能である。

また、確率的ヒストグラム化部２００１は、各データポイントについてどのビンに登録されるかを計算するだけなので、多くてもデータポイント数程度の計算量で抑えられ、計算時間の大幅な低減が期待できる。

ラベル計算部２００６は、各々１つのデータポイントに対し、多重化ラベル２００８を計算する。各々のラベル計算部２００６は、ラベル２００９の１つのビットに代入する数値を計算する。ラベル２００９のビット数は、ラベル計算部２００６の数と対応する（図３の例では４ビット）。

ここで、入力するデータポイントはＤ次元ベクトル空間の１点であり、ラベル計算部２００６は、式（１）に示すように、ＬＳＨ（ＬｏｃａｌｉｔｙＳｅｎｓｉｔｉｖｅＨａｓｈｉｎｇ）を用いて、Ｄ次元ユークリッド空間から整数値への写像で定義される。

ただし、Ｒは実数、［ｙ］はｙを超えない整数値、ａ∈Ｒ^Ｄは各成分が独立な標準正規分布Ｎ（０，１）に従うランダム数で構成されるＤ次元ベクトルを表し、ｒ〜Ｕ［０，Ｗ）は、Ｕ［０，Ｗ）における一様分布に従うランダム数を表す。また、Ｗ∈Ｒ^Ｄはウィンドウ幅、Ｃは基数（２以上の整数）であり、管理者が設定するパラメータである。この写像により、任意の２点のデータポイントは、その距離が近いほど高い確率で同一の値をもつことになる。

これをＢビット化したものがラベル２００９であり、式（２）で定義される。

任意の２点のデータポイントが与えられた時、それらが同一のラベルを持つ確率（以後、衝突確率と記す。）は式（３）で与えられる。

ただし、Ｚは整数である。図４および５は、２点間の距離ｄの２つのデータポイントが衝突する確率を、Ｗで正規化した距離に対してプロットしたグラフを示す。図に示すように、距離ｄがゼロ付近ではほぼ線形に距離の増加に対して衝突確率が減少していくが、ｄ／Ｗが１を超えたあたりから一定の値Ｃ^−Ｂに収束する。

多重化ラベル２００８は、このラベル演算をＭ回独立に行った結果を多重化した式（４）で定義される。

ここで、図６に示す比較演算を式（５）によって定義し、多重化ラベル２００８同士の衝突を定義する。

これは、多重化ラベル２００８を構成するラベルのうち、１つでも同じラベルが含まれていれば１を返し（多重化ラベル衝突）、そうでなければ０を返す（多重化ラベル非衝突）、という演算である。なお、ここでは１つでも同じラベルが含まれていれば衝突と定義しているが、これはＭ回の試行のうち一度でも同一のラベルを持てばそれは両者の距離が近い可能性が高い、という事実を反映させたものである。管理者のポリシーによって、全てのラベルが衝突しなくては多重化ラベルの衝突とみなさない、といったさらに厳しい条件に変更することも可能である。

式（５）で定義される多重化ラベルの衝突を検証することにより、与えられたデータセットに対してヒストグラムを生成することができる。１つの方法は、あるデータポイントｘに対して、１つ以上のデータポイントが登録されている全てのヒストグラムのビンに対して、既に登録されているデータポイントの多重化ラベルと式（５）の比較演算を行い、その中で１つでも衝突していたらそのビンに新たに追加登録する。該当するビンがなければ新規にビンを作成しそこに登録する。

このような処理により、同じビンに登録されたデータポイントは少なくともどれか１つの他のデータポイントと共通のラベルを有していることが保障される。また、データポイントが登録されるのは１つのビンだけとは限らず、一般に複数のビンに属する可能性がある。

さらに、より厳しい条件として、ビン内の全てのデータポイントと多重化ラベルが衝突した場合にのみ、そのビンに追加することも可能である。この場合は、同じビンに登録されている全てのデータポイントは、少なくとも１つの共通のラベルを共有していることになる。これはＭ回の試行のうち、少なくとも一度は全てのデータポイントが同じラベルを割り当てられたことを意味する。

上記の衝突・ヒストグラム化ポリシーによって、量的な差異はあるものの、同じビンに属するデータは互いに近い距離にある確率が高いことになり、滞留エリアに属するデータポイントは他のエリアのデータポイントに比べて同じビンに属する可能性が高くなる。この性質を利用することで、データポイントが登録される頻度の高いビンのデータポイントから順にサンプリングしていくことで、より密集度の高いエリアから優先的にデータポイントを選択することが可能となる。

なお、サンプリングするビンの数は任意に設定することができる。例えば、抽出する総データポイント数としてもよいし、ビンの数に基づいて指定してもよい。また、平均頻度以上のビンなど頻度の分布からきめることも可能である。

連結ヒストグラム２００７は、上記の処理を独立にＮ回繰り返した結果得られ、複数回の独立試行による結果を連結して考慮することで精度向上を図ったものである。具体的には、Ｎ回の試行のうち、何度も登録頻度の高いビンに登録されるデータポイントは、より密集度の高いエリアに属すると判断でき、偶然衝突したそれほど密集度の高くないエリアに属するデータポイントと区別することが可能となる。

上記の処理によりサンプリングしたデータポイント群を滞留エリアに分類する。１つの方法は、ビンごとに滞留エリアとすることである。しかし、上記の方法では、距離的に近いデータポイントは同じビンでないにしても、周辺のビンに属する可能性が高い。例えば、ラベルのうち１ビットだけ３が２になる、などラベルの差異が小さい場合などが考えられる。その場合、同じ滞留エリアとみなせる領域のデータポイントが異なるビンに属する可能性があるため、ビン単位でのエリア分類は適切でない可能性がある。

そのため、図７に示すように、再構成・グループ化部２００３によって各試行で得られたヒストグラムのうち頻度が多い順に所定の数だけ、それらのビンに属するデータポイントを取り出し、そのうちの一部の特に頻度の多いビンをｈｉｇｈグループ、それ以外をｌｏｗグループに分類する。さらに、クラスター化部２００２によって、ｈｉｇｈグループとｌｏｗグループに分類されたデータから、指定されたサイズや互いの距離関係などを満たすようにクラスターを構成（第２のクラスタリング）していくことで、滞留エリアを指定する。

まず、図８を参照して、サンプリングしたデータポイントの再構成・グループ化処理について詳細に説明する。

再構成・グループ化部２００３のサンプリング部３００１は、Ｎ個の独立したヒストグラム７００１の入力のそれぞれに対して、あらかじめ定められたビンの数Ｋだけ、登録頻度の多いビンを選択する。グループ化部３００２は、所定の閾値に基づいて、各ヒストグラムからサンプリングされたビンをｈｉｇｈとｌｏｗの二種類のグループに分類する。

ここで、閾値は典型的には平均頻度などであるが必ずしもこれに限るものではない。図の例では平均頻度をもとに、平均頻度より頻度が多いビンをｈｉｇｈに、少ないビンをｌｏｗに分類している。またその分類をもとに、グループ化部３００２は、各ビンに登録されているデータポイントをｈｉｇｈグループ７００４およびｌｏｗグループ７００５に登録する。このとき、一般に異なる試行番号のヒストグラムから同じデータが存在するが、重複した場合は削除してもよいし、重複回数はより密集度の高いエリアからのサンプリングを示唆するため、重複を許して登録しても良い。

次に、図９を参照してクラスター化部２００２の動作について説明する。クラスター化部２００２の動作は、大きく前半処理と後半処理に分かれており、前半処理では、ｈｉｇｈグループに属するデータポイントを用いてクラスター分析によるクラスター化を行い、基本コロニーを作成する。後半処理では、ｌｏｗグループに属するデータポイントを基本コロニーに対して新規追加登録していく。

一般に、クラスター分析処理は、データ数の増大に対して計算時間が爆発的に増大しがちである。そのため、クラスター分析処理を全てのデータポイントを用いて行うのではなく、本実施の形態のように２段階に分けることで、より密集度の高いエリアからサンプリングしたデータであるｈｉｇｈグループのみを用いて、効率的に滞留エリアの基幹部分を作成し、比較的密集度の低いエリアからサンプリングされたｌｏｗグループのデータポイントをその基幹部分に追加していくことができる。これにより、計算時間の増大を抑えたまま望ましいクラスターを形成することが可能となる。計算時間に問題がない程度のデータポイント数の場合は、全てのデータポイントをｈｉｇｈグループに登録し、前半処理のみを行うようにしてもよい。

以下、前半処理について詳細に説明する。
前半処理は、クラスター分析処理をｈｉｇｈグループのデータポイントに対して行い、コロニーを形成することを目的としている。ここで、最終的に形成したい滞留エリアの半径を規定するｌ_ｔｈ、滞留エリア間の最小距離を規定するＤ_ｔｈをあらかじめ設定しておく。

（ステップＡ８１０１）クラスター化部２００２は、ｈｉｇｈグループに登録されている全データポイントを用いて初期クラスターセットを作成する。初期クラスターセットは各クラスターに１つのデータポイントのみが含まれるように形成される。

（ステップＡ８１０２）クラスター化部２００２は、初期クラスターセット間の平方距離情報を有する距離行列Ｄを計算する。ここで、初期クラスター間の平方距離はデータポイント間のユークリッド距離の平方とする。

（ステップＡ８１０３）クラスター化部２００２は、クラスター数が１つしかないか、もしくは最小クラスター間距離Ｍｉｎ（Ｄ）とＤ_ｔｈの関係がＭｉｎ（Ｄ）＞Ｄ_ｔｈであればステップＡ８１０６に進む。そうでなければステップＡ８１０４に進む。

（ステップＡ８１０４）クラスター化部２００２は、もっとも距離の近い２つのクラスターを統合して新しいクラスターを作る。この操作に伴い全体のクラスター数は１つ減る。

（ステップＡ８１０５）クラスター化部２００２は、１つ減った新しいクラスターセットに対する距離行列Ｄを計算する。ここで、クラスター間の平方距離の定義は様々な方法があるが、代表的なものとしてはＷａｒｄ法や重心法がある。統合前のクラスターをｐ、ｑ、統合後のクラスターをｔとすると、クラスターｔと、その他のクラスターｒとの距離Ｄ_ｔｒ ^２はクラスター間距離Ｄ_ｐｒ ^２、Ｄ_ｑｒ ^２、Ｄ_ｐｑ ^２を用いて、式（６）（Ｗａｒｄ法）もしくは式（７）（重心法）によって計算される。

ただし、ｎ_Ｘはクラスターｘのデータポイント数である。また距離行列の更新ルールはＷａｒｄ法や重心法に限るものではない。

（ステップＡ８１０６）クラスター化部２００２は、クラスターセットをコロニーセットとして出力する。このコロニーセットは滞留エリアの基幹部分を形成し、互いにもっとも近いクラスター間の距離が少なくともＤ_ｔｈ以上であるか、もしくは１つのクラスターしか含まれない。１つのクラスターしか含まれない場合は、全てのデータポイントは同一の滞留エリアに属するデータポイントとみなされる。

次に後半処理について説明する。
後半処理は、前半処理で形成したクラスターセットに対して、ｌｏｗグループに属する各データポイントが、そのどれか１つのクラスターに属すると判断された場合は該当するクラスターに追加し、どのクラスターにも属しないと判断された場合は新規クラスターを作成し、クラスターセットを更新する処理を行うことで、最終的な滞留エリアを形成する。

（ステップＡ８２０１）クラスター化部２００２は、まず前半処理の出力であるコロニーセットをクラスターセット８００１の初期値に設定する。

（ステップＡ８２０２）クラスター化部２００２は、Ｌｏｗグループのデータポイントのうちまだ未検査のものがあるかチェックする。なければステップＡ８２０９に進み、あればステップＡ８２０３に進む。

（ステップＡ８２０３）クラスター化部２００２は、Ｌｏｗグループからまだ未検査のデータポイントｘを取得する。

（ステップＡ８２０４）クラスター化部２００２は、クラスターセット８００１のクラスターの中で、データポイントｘに一番距離が近いクラスターｃを選択する。ここでは、このデータポイントｘとクラスターｃの距離ｌ（ｘ、ｃ）はクラスターｃの中心的な位置（平均位置もしくは平均位置に一番近いデータポイントの位置）とデータポイントｘのユークリッド距離とする。あるいは、クラスターｃの中で一番データポイントに近いデータポイントとｘの距離や、一番遠いデータポイントとｘの距離、など他の様々な距離としてもよい。

（ステップＡ８２０５）クラスター化部２００２は、ｌ（ｘ、ｃ）とあらかじめ設定したｌ_ｔｈを比較し、ｌ（ｘ、ｃ）＜ｌ_ｔｈならばｘは同一滞留エリアからサンプリングされたデータポイントと判断し、ステップＡ８２０６に進む。そうでなければ、異なる滞留エリアからサンプリングされたデータポイントと判断し、ステップＡ８２０７に進む。

（ステップＡ８２０６）クラスター化部２００２は、データポイントｘをクラスターｃに追加する。

（ステップＡ８２０７）クラスター化部２００２は、新規クラスターｕを作成し、データポイントｘを登録する。

（ステップＡ８２０８）クラスター化部２００２は、クラスターセット８００１を更新する。その後ステップＡ８２０２に戻り、未検査のデータポイントがなくなるまで同じ処理を繰り返す。

（ステップＡ８２０９）クラスター化部２００２は、クラスターセット８００１を出力する。

以上の処理によって、クラスター半径やクラスター間距離が制限されたクラスターの集合が出力され、各クラスターはＧＰＳログデータの滞留エリア候補として考えることができる。

代表点抽出部１００４は、これらのクラスターに対して、前述の方法によって代表点を抽出し、抽出した代表点のスコアを計算し、スコアに基づいて全滞留エリアのウェイポイントを序列化する。

以上のように、本実施形態によれば、ＧＰＳログデータ上で、ユーザが関心を持った場所は他の場所に比べ滞留時間が長くなる傾向があるため、その場所をウェイポイントの候補とし、かつその密集度合いにより序列化することで、ＧＰＳログデータに固有の特徴点を効率的に抽出しユーザへ提示するようにしたので、ユーザにとって、その時点で重要である可能性の高い場所を自動的に抽出し、表示することができる。この結果、ユーザは、ＧＰＳログデータの中から、ランドマーク的なスポット情報のデータベースとの連携やユーザプロファイル情報との連携をせずに、ユーザにとって重要な意味を持つポイントを効率的に抽出することができる。このため、ＧＰＳログデータを加工、編集して利用する際のコストを大幅に削減することができる。

なお、滞留エリアはデータポイントの密度によって決定することができるので、より簡易な方法としては、ＧＰＳログデータの全ての点が収まる最小領域を考え、その領域を固定的な小さいセルに分割し、各セルを１つのビンとしたヒストグラムを作るようにしてもよい。この方法でも一定の効果は得られるが、セルの大きさの結果への影響が大きく、またセルの境界の取り方への依存性がある。このため、ＧＰＳログデータの性質（範囲や密集度合いなど）を考慮しないとよい結果を得られるとは限らない。一方、各セルの幅をランダムに設定すると、滞留エリアの計算に時間がかかる。

また、例えばデータポイントをランダムに抽出しても、滞留エリアのほうがその他のエリア（単なる通過エリア）よりもサンプリング対象となる確率が高いことを利用して滞留エリアを抽出する方法も考えられるが、その場合でも、滞留エリアと通過エリアのデータポイント数の差が大きくないと精度は低くなる。本実施形態では、データポイントの密集度合いを計算するにあたっては、個々のデータポイントの絶対的な座標値は問題ではなく、他のデータポイントとの距離関係のみが重要であることを利用し、互いの距離の近いデータポイント数が多いほど、滞留エリアとして抽出されやすい確率的サンプリング手法を用いているため、適切なウェイポイントを精度良く効率的に抽出することができる。

また、クラスター化部２００２が密集度の高いエリアからより高い確率でサンプリングするようにしたので、データベースなどとのマッチングや、全てのデータポイント間の距離関係などの情報を必要としないことからデータ量の増加に対して計算量を抑えることができる。このため、ウェイポイントの自動検出に際し、データ量が増大しても計算コストを低く抑えることができる。このため、ユーザへのレスポンスが高く、ユーザはストレスなくウェイポイント候補を得ることができる。

本実施形態において、計算時間をきめる主要な処理は、滞留エリア検出部１００３の処理であり、さらに詳しくは、確率的ヒストグラム化部２００１の処理、及びクラスター化部２００２の前半処理である。クラスター化部２００２の計算時間はｈｉｇｈグループのデータポイント数を計算機の能力に合わせて制限することで調整が可能である。確率的ヒストグラム化部２００１の計算時間に関しては、入力データ数が非常に多い時は、まずランダムサンプリングを行い、計算機の能力に合わせた数までデータポイント数を絞り込むことで計算時間を調整可能である。さらに望ましくは、前処理として領域を大きめの固定セルで分割しておき、データポイント数の多いセルからより高い確率でランダムサンプリングするなどの方法を取ることによって、さらに精度を向上させることも可能である。

さらに、滞留エリアと判定されたものの中でも、意味があって滞留した場所と、信号待ちなどあまり意味のない理由で滞留した場所がありうるが、前者を優先的に検出すべきである。そのため、例えば、あらかじめランドマーク的なスポットのラベルを計算しておき、そのデータと衝突したデータポイントのビンはデータポイント１点の重みを上げることにより、同じデータ数でもビンの高さ（重み付き頻度）が高くなるようにすることで、優先的に検出することができる。

また、ユーザプロファイルなどからユーザの趣向情報を取り入れ、ユーザが過去により好ましく判断したスポットと同じビンに登録されたデータポイントに重みをつけることで、ユーザ固有の趣向情報も加味することができる。この方法によれば、従来の方法ではデータベース連携やユーザプロファイル連携に長い計算時間を要したのに対し、同一のオンライン処理時間でデータベースやユーザプロファイル情報と連携しながら滞留エリアを抽出することができる。

次に、図１０を用いて本発明の実施例について説明する。
図１０は本発明による特徴点検出システムをウェイポイント検出部９００７に適用したサーバ９００４を含む、コンピュータシステムの構成を示す図である。図に示すように、ユーザのＧＰＳログデータを記録する記録デバイス９００１と、ＧＰＳログデータをアップロードしたり、加工したデータの結果を表示したりするためのコンピュータ９００２と、サーバ９００４とが、ネットワーク９００３を介して接続されている。

サーバ９００４は、ユーザセッション管理部９００５、ユーザデータ管理部９００６、ウェイポイント検出部９００７、地図アプリケーション９００８、出力部９００９を備え、ユーザのＧＰＳログデータ入力に対し、ｘｍｌやｈｔｍｌに代表されるデータフォーマットで記述された出力データ９０１０を生成する。ユーザはコンピュータ９００２で動作するウェブブラウザ等のソフトウェアプログラムを用いてネットワーク経由で出力データ９０１０を閲覧することができる。

サーバ９００４は、ユーザセッション管理部９００５によって、ユーザ認証や、ユーザとのコネクション管理を行う。ユーザデータ管理部９００６は、ユーザ特有にカスタマイズされたページ情報を管理し、例えば過去にアップロードした情報などを、カレンダーに時系列に整理しユーザが閲覧しやすい形で保存しておく。また、図中には記載されていないが、ユーザデータのデータベースなども必要に応じて備えている。

ユーザデータ管理部９００６は、ユーザによる新規ＧＰＳログデータのアップロードに対してウェイポイント検出部９００７を呼び出し、ウェイポイントリストを作成する。ＧＰＳログデータと計算したウェイポイントリストは、地図アプリケーション９００８に入力され、地図上にＧＰＳログデータの軌跡と、軌跡上のウェイポイントを表示する。

出力データ９０１０は、例えば出力データ表示イメージ９０１１に示すように、ＧＰＳログデータのデータポイントの軌跡上に、ピンで示されたウェイポイントが重ねて表示されたものである。またウェイポイントの詳細情報の一覧などが合わせて表示されてもよい。ユーザはコンピュータ９００２を用いて、出力データ９０１０をネットワーク９００３を介して取得し、閲覧することができる。この一連の処理は、サーバ９００４のウェイポイント検出部９００７の処理により、高い応答性を実現することができる。

この出願は、２０１０年５月１２日に出願された日本出願特願２０１０−１１０３６１を基礎とする優先権を主張し、その開示の全てをここに取り込む。

以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

上記の実施の形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいてそのクラスターにおけるユーザの滞留時間を示す指標を決定し、前記指標に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成する滞留エリア検出部であって、前記滞留時間が長いほどそのクラスターが高い確率で抽出される、滞留エリア検出部と、
抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を１つずつ抽出すると共に、各々の前記滞留エリア内の前記データポイントの密集度に基づいて、各々の前記代表点のスコアを決定する代表点抽出部と、
前記スコアに基づいて、各々の前記代表点を序列化したリストを出力する代表点序列化部と、を備えた特徴点検出システム。

（付記２）前記滞留エリア検出部は、
第１のデータポイントと第２のデータポイントを、２つのデータポイント間の距離が短いほど高い確率で前記第１及び第２のポイントが同一の階級に属するように分類することによりヒストグラムを生成し、前記ヒストグラムの各階級を前記クラスターに対応させて、各階級の頻度を前記滞留時間を示す指標として決定する確率的ヒストグラム化部を備えた付記１に記載の特徴点検出システム。

（付記３）前記滞留エリア検出部は、
前記確率的ヒストグラム化部によって生成された前記ヒストグラムの各階級のうち、前記滞留時間の長いクラスターに対応する階級を抽出し、前記抽出した階級に属するデータポイントに対して第２のクラスタリングを行うことにより前記滞留エリアを形成する、付記２に記載の特徴点検出システム。

（付記４）前記滞留エリア検出部は、
前記確率的ヒストグラム化部によって生成された前記ヒストグラムの各階級のうち、前記滞留時間の長いクラスターに対応する階級を抽出し、前記抽出した階級を前記滞留時間の長短に基づいて２つのグループに分ける、再構成・グループ化部と、
前記２つのグループのうち、前記滞留時間の長い方のグループの階級に属するデータポイントを用いて滞留エリアを形成した後、他方のグループの階級に属するデータポイントを前記滞留エリアに付加し、または新たな滞留エリアを形成して、滞留エリアを形成するクラスター化部と、を備えた付記２に記載の特徴点検出システム。

（付記５）前記確率的ヒストグラム化部は、
各データポイントに対してＬＳＨ（Locality Sensitive Hashing）を用いて付与されるラベルを用いて、各々のデータポイントが属する階級を決定する付記２から４のいずれかに記載の特徴点検出システム。

（付記６）前記滞留エリア検出部は、
ランドマークに対応する地点に対応するデータポイント、及びユーザの嗜好に合った地点に対応するデータポイントの少なくとも一方に対して前記クラスタリングを行い、そのデータポイントが含まれるクラスターが抽出される確率が高くなるように重み付けをする、付記１から５のいずれかに記載の特徴点検出システム。

（付記７）前記滞留エリア検出部は、
前記ＧＰＳログデータをランダムにサンプリングしてデータポイント数を削減してから前記滞留エリアの抽出を行う、付記１から６のいずれかに記載の特徴点検出システム。

（付記８）前記滞留エリア検出部は、
前記ＧＰＳログデータに含まれる全てのデータポイントを含む最小範囲で定義される全体領域を複数の固定領域に分割し、各々の前記固定領域について、前記固定領域に属するデータポイント数が多い固定領域ほど高い確率でデータポイントを抽出し、抽出したデータポイントを用いてクラスタリングを行う請求項１から７のいずれかに記載の特徴点検出システム。

（付記９）ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいてそのクラスターにおけるユーザの滞留時間を示す指標を決定し、前記指標に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成し、前記滞留時間が長いほどそのクラスターが高い確率で抽出される工程と、
抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を１つずつ抽出すると共に、各々の前記滞留エリア内の前記データポイントの密集度に基づいて、各々の前記代表点のスコアを決定する工程と、
前記スコアに基づいて、各々の前記代表点を序列化したリストを出力する工程と、を備えた特徴点検出方法。

（付記１０）コンピュータを、
ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいてそのクラスターにおけるユーザの滞留時間を示す指標を決定し、前記指標に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成する滞留エリア検出部であって、前記滞留時間が長いほどそのクラスターが高い確率で抽出される、滞留エリア検出部と、
抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を１つずつ抽出すると共に、各々の前記滞留エリア内の前記データポイントの密集度に基づいて、各々の前記代表点のスコアを決定する代表点抽出部と、
前記スコアに基づいて、各々の前記代表点を序列化したリストを出力する代表点序列化部と、して機能させるプログラム。

本発明は、ＧＰＳログデータから、適切なウェイポイントを精度良く高い応答性で検出することに適している。

１００特徴点検出システム、１００１入力データ、１００２入力部、１００３滞留エリア検出部、１００４代表点抽出部、１００５出力部、１００６ＷＰＴリスト、１００７地図アプリケーション、１００８出力データ、２００１確率的ヒストグラム化部、２００２クラスター化部、２００３再構成・グループ化部、２００４連結ヒストグラム作成部、２００５多重化ラベル計算部、２００６ラベル計算部、２００７連結ヒストグラム、２００８多重化ラベル、２００９ラベル、３００１サンプリング部、３００２グループ化部、７００１Ｎ個の独立したヒストグラム、７００４ｈｉｇｈグループ、７００５ｌｏｗグループ、９００１記録デバイス、９００２コンピュータ、９００３ネットワーク、９００４サーバ、９００５ユーザセッション管理部、９００６ユーザデータ管理部、９００７ウェイポイント検出部、９００８地図アプリケーション、９００９出力部、９０１０出力データ、９０１１表示イメージ

Claims

ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成する滞留エリア検出部と、
抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を抽出すると共に、各々の前記代表点のスコアを決定する代表点抽出部と、
前記スコアに基づいて前記代表点を出力する出力部と、
を備えた特徴点検出システム。
ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいてそのクラスターにおけるユーザの滞留時間を示す指標を決定し、前記指標に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成する滞留エリア検出部であって、前記滞留時間が長いほどそのクラスターが高い確率で抽出される、滞留エリア検出部と、
抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を１つずつ抽出すると共に、各々の前記滞留エリア内の前記データポイントの密集度に基づいて、各々の前記代表点のスコアを決定する代表点抽出部と、
前記スコアに基づいて、各々の前記代表点を序列化したリストを出力する代表点序列化部と、を備えた特徴点検出システム。
前記滞留エリア検出部は、
第１のデータポイントと第２のデータポイントを、２つのデータポイント間の距離が短いほど高い確率で前記第１及び第２のポイントが同一の階級に属するように分類することによりヒストグラムを生成し、前記ヒストグラムの各階級を前記クラスターに対応させて、各階級の頻度を前記滞留時間を示す指標として決定する確率的ヒストグラム化部を備えた請求項２に記載の特徴点検出システム。
前記滞留エリア検出部は、
前記確率的ヒストグラム化部によって生成された前記ヒストグラムの各階級のうち、前記滞留時間の長いクラスターに対応する階級を抽出し、前記抽出した階級に属するデータポイントに対して第２のクラスタリングを行うことにより前記滞留エリアを形成する、請求項３に記載の特徴点検出システム。
前記滞留エリア検出部は、
前記確率的ヒストグラム化部によって生成された前記ヒストグラムの各階級のうち、前記滞留時間の長いクラスターに対応する階級を抽出し、前記抽出した階級を前記滞留時間の長短に基づいて２つのグループに分ける、再構成・グループ化部と、
前記２つのグループのうち、前記滞留時間の長い方のグループの階級に属するデータポイントを用いて滞留エリアを形成した後、他方のグループの階級に属するデータポイントを前記滞留エリアに付加し、または新たな滞留エリアを形成して、滞留エリアを形成するクラスター化部と、を備えた請求項３に記載の特徴点検出システム。
前記確率的ヒストグラム化部は、
各データポイントに対してＬＳＨ（Locality Sensitive Hashing）を用いて付与されるラベルを用いて、各々のデータポイントが属する階級を決定する請求項３から５のいずれかに記載の特徴点検出システム。
前記滞留エリア検出部は、
ランドマークに対応する地点に対応するデータポイント、及びユーザの嗜好に合った地点に対応するデータポイントの少なくとも一方に対して前記クラスタリングを行い、そのデータポイントが含まれるクラスターが抽出される確率が高くなるように重み付けをする、請求項１から６のいずれかに記載の特徴点検出システム。
前記滞留エリア検出部は、
前記ＧＰＳログデータをランダムにサンプリングしてデータポイント数を削減してから前記滞留エリアの抽出を行う、請求項１から７のいずれかに記載の特徴点検出システム。
前記滞留エリア検出部は、
前記ＧＰＳログデータに含まれる全てのデータポイントを含む最小範囲で定義される全体領域を複数の固定領域に分割し、各々の前記固定領域について、前記固定領域に属するデータポイント数が多い固定領域ほど高い確率でデータポイントを抽出し、抽出したデータポイントを用いてクラスタリングを行う請求項１から８のいずれかに記載の特徴点検出システム。
コンピュータの滞留エリア検出部が、ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成する工程と、
前記コンピュータの代表点抽出部が、抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を抽出すると共に、各々の前記代表点のスコアを決定する工程と、
前記コンピュータの出力部が、前記スコアに基づいて前記代表点を出力する工程と、
を備えた特徴点検出方法。
コンピュータの滞留エリア検出部が、ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいてそのクラスターにおけるユーザの滞留時間を示す指標を決定し、前記指標に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成し、前記滞留時間が長いほどそのクラスターが高い確率で抽出される工程と、
前記コンピュータの代表点抽出部が、抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を１つずつ抽出すると共に、各々の前記滞留エリア内の前記データポイントの密集度に基づいて、各々の前記代表点のスコアを決定する工程と、
前記コンピュータの代表点序列化部が、前記スコアに基づいて、各々の前記代表点を序列化したリストを出力する工程と、を備えた特徴点検出方法。
コンピュータを、
ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成する滞留エリア検出部と、
抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を抽出すると共に、各々の前記代表点のスコアを決定する代表点抽出部と、
前記スコアに基づいて前記代表点を出力する出力部と、して機能させるプログラム。
コンピュータを、
ユーザのＧＰＳログデータに含まれるデータポイントの分布に基づいてクラスタリングを行い、各クラスターに含まれるデータポイント数に基づいてそのクラスターにおけるユーザの滞留時間を示す指標を決定し、前記指標に基づいて１以上のクラスターを抽出し、前記抽出したクラスターに基づいてユーザの滞留エリアを形成する滞留エリア検出部であって、前記滞留時間が長いほどそのクラスターが高い確率で抽出される、滞留エリア検出部と、
抽出された各々の前記滞留エリアから、前記滞留エリアの代表点を１つずつ抽出すると共に、各々の前記滞留エリア内の前記データポイントの密集度に基づいて、各々の前記代表点のスコアを決定する代表点抽出部と、
前記スコアに基づいて、各々の前記代表点を序列化したリストを出力する代表点序列化部と、して機能させるプログラム。