(57)【特許請求の範囲】
【請求項１】
位置測定装置で測定された人物の動線を編集する動線編集装置であって、
同一人物と推定される断片化した動線情報を結合する動線結合情報作成部を備え、
前記動線結合情報作成部は、
２つの異なる断片化した動線に対する距離に基づく結合スコアを算出する第１の手段と、
第１の動線に対して、結合スコアが最小となる第２の動線を対応付ける第２の手段と、  前記第２の手段による対応付けによって結合された前記第１及び第２の動線から新たな動線を作成する第３の手段と、
を備え、
前記第１の手段は、前記結合スコアを以下の式に基づいて求めることを特徴とする動線編集装置。
結合スコア  Score(ｊ, ｋ) ＝ α×時間的距離(ｊ, ｋ)  ＋  β×空間的距離(ｊ, ｋ)    （１）
ここで、αとβは重みづけ係数である。また、時間的距離(ｊ, ｋ)と空間的距離(ｊ, ｋ)とは以下のように定義される。
時間的距離(ｊ, ｋ) ＝ ｜動線(ｊ)の終点の時刻 − 動線(ｋ)の始点の時刻｜
空間的距離(ｊ, ｋ) ＝  動線(ｊ)の終点と動線(ｋ)の始点との間の距離
【請求項２】
前記第１の手段による処理の前に、断片化した動線内の変化点を検出し、前記変化点から前記断片化した動線の終点までの部分を削除する、第４の手段を備えることを特徴とする請求項１に記載の動線編集装置。
【請求項３】
１つの動線に対して異なる２つの動線が対応付け可能な場合には、前記対応付けを行わないことを特徴とする請求項１又は２に記載の動線編集装置。
【請求項４】
前記αとβとを、位置又は属性に依存させて変化させることを特徴とする請求項１から３までのいずれか１項に記載の動線編集装置。
【請求項５】
位置測定装置で測定された人物の動線をコンピュータに編集させる動線編集方法であって、
同一人物と推定される断片化した動線情報を結合する動線結合情報作成ステップを備え、
前記動線結合情報作成ステップは、
２つの異なる断片化した動線に対する距離に基づく結合スコアを算出する第１のステップと、
第１の動線に対して、結合スコアが最小となる第２の動線を対応付ける第２のステップと、
前記第２のステップによる対応付けによって結合された前記第１及び第２の動線から新たな動線を作成する第３のステップと、
を有し、
前記第１のステップは、前記結合スコアを以下の式に基づいて求めることを特徴とする動線編集方法。
結合スコア  Score(ｊ, ｋ) ＝ α×時間的距離(ｊ, ｋ)  ＋  β×空間的距離(ｊ, ｋ)    （１）
ここで、αとβは重みづけ係数である。また、時間的距離(ｊ, ｋ)と空間的距離(ｊ, ｋ)とは以下のように定義される。
時間的距離(ｊ, ｋ) ＝ ｜動線(ｊ)の終点の時刻 − 動線(ｋ)の始点の時刻｜
空間的距離(ｊ, ｋ) ＝  動線(ｊ)の終点と動線(ｋ)の始点との間の距離
【請求項６】
前記第１のステップによる処理の前に、断片化した動線内の変化点を検出し、前記変化点から前記断片化した動線の終点までの部分を削除する、第４のステップを備えることを特徴とする請求項５に記載の動線編集方法。
【請求項７】
１つの動線に対して異なる２つの動線が対応付け可能な場合には、前記対応付けを行わないことを特徴とする請求項５又は６に記載の動線編集方法。
【請求項８】
前記αとβとを、位置又は属性に依存させて変化させることを特徴とする請求項５に記載の動線編集方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動線を編集する動線編集技術に関する。
【背景技術】
【０００２】
近年、様々なセンサの低価格化やネットワークの進化に伴い、例えば店舗内にカメラや位置測定装置等を設置することで、店舗内を顧客がどのように回遊したかに関する情報を分析し、店舗の売上向上やコスト削減の施策を講じるための助けとすることが行われている。
【０００３】
従来より、測域センサを店舗内に設置し、測域センサから照射されるレーザを用いて人の動きを追跡する方法が知られている（例えば、非特許文献１参照）。
【０００４】
非特許文献１では、駅構内の異なる位置にレーザスキャナを配置し、歩行者のトラッキングを行う。トラッキングアルゴリズムは、レンジデータのクラスタリングによる足候補の検出、足候補のグルーピングによる歩行者候補の検出、歩行者候補の動きベクトルの検出、歩行モデルに基づく拡張カルマンフィルタによる既存軌跡の延長処理、である。これを、東京都内の駅の駅構内のコンコースに適用すると、１５０人を同時にトラッキングすることができる。これにより、レーザが人に当たっている間の人の動き（動線）を個人別に得ることができる（図２Ａを参照して後述する）。
【０００５】
しかし、複数人が行き交う状況が発生すると、レーザが遮蔽されてしまうことにより、動線が途切れて断片化してしまう状況が発生する。動線が途切れると、本来は同一人物の動線であったとしても、別の人物の動線と認識されてしまう問題がある。
【０００６】
このような問題に対処するため、特許文献１には、カメラによって撮影された動画から得られた動線を結合する方法が開示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００９−９３９４号公報
【非特許文献】
【０００８】
【非特許文献１】中村克行  他、電子情報通信学会論文誌  Ｄ−ＩＩ  ＶＯＬ.Ｊ８８−Ｄ−ＩＩ  ｐｐ1143-1152（2005）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１に記載の技術では、オペレータが目視で結合すべき動線を選択する必要があり、動線の数が膨大になった場合に現実的に対応することが難しくなるという問題がある。
【００１０】
本発明は、このような状況に鑑みてなされたものであり、断片化された動線を自動的に結合可能な技術を提供することを目的とするものである。
【課題を解決するための手段】
【００１１】
本発明は、断片化された顧客の移動情報（動線情報）を結合し、分析する上で実用に足る動線情報を生成する。
【００１２】
本発明の一観点によれば、位置測定装置で測定された人物の動線を編集する動線編集装置であって、同一人物と推定される断片化した動線情報を結合する動線結合情報作成部を備え、前記動線結合情報作成部は、２つの異なる断片化した動線に対する距離に基づく結合スコアを算出する第１の手段（ステップS704）と、第１の動線に対して、結合スコアが最小となる第２の動線を対応付ける第２の手段（ステップS709）と、前記第２の手段による対応付けによって結合された前記第１及び第２の動線から新たな動線を作成する第３の手段（ステップS710）と、を備えることを特徴とする動線編集装置が提供される。
【００１３】
前記第１の手段による処理の前に、断片化した動線内の変化点を検出し、前記変化点から前記断片化した動線の終点までの部分を削除する、第４の手段（動線終端処理部）を備えることを特徴とする。
【００１４】
１つの動線に対して異なる２つの動線が対応付け可能な場合には、前記対応付けを行わないことを特徴とする。
前記第１の手段は、前記結合スコアを以下の式に基づいて求めることを特徴とする。
【００１５】
結合スコア  Score(ｊ, ｋ) ＝ α×時間的距離(ｊ, ｋ)  ＋  β×空間的距離(ｊ, ｋ)    （１）
【００１６】
ここで、αとβは重みづけ係数である。また、時間的距離(ｊ, ｋ)と空間的距離(ｊ, ｋ)とは以下のように定義される。
時間的距離(ｊ, ｋ) ＝ ｜動線(ｊ)の終点の時刻 − 動線(ｋ)の始点の時刻｜
空間的距離(ｊ, ｋ) ＝  動線(ｊ)の終点と動線(ｋ)の始点との間の距離
【００１７】
前記αとβとを、位置又は属性に依存させて変化させることを特徴とする。
【００１８】
また、本発明の他の観点によれば、位置測定装置で測定された人物の動線をコンピュータに編集させる動線編集方法であって、同一人物と推定される断片化した動線情報を結合する動線結合情報作成ステップを備え、前記動線結合情報作成ステップは、２つの異なる断片化した動線に対する距離に基づく結合スコアを算出する第１のステップと、第１の動線に対して、結合スコアが最小となる第２の動線を対応付ける第２のステップと、前記第２のステップによる対応付けによって結合された前記第１及び第２の動線から新たな動線を作成する第３のステップと、を有することを特徴とする動線編集方法が提供される。
【発明の効果】
【００１９】
本発明によれば、動線情報の自動編集を精度良く行うことができるという利点がある。
【図面の簡単な説明】
【００２０】
【図１Ａ】本発明の実施の形態による動線編集システムの一構成例を示す概略図である。
【図１Ｂ】本実施の形態による動線編集装置の一構成例を示す機能ブロック図である。
【図２Ａ】動線編集処理前の動線情報のデータ構成例を示す図である。
【図２Ｂ】異常な終端を持つ動線情報のデータ構成例を示す図である。
【図２Ｃ】結合される動線情報のデータ構成例を示す図である。
【図３】異常な終端を持つ動線の一例を示す図である。
【図４】異常な終端を削除した後の動線の一例を示す図である。
【図５】動線の終端処理の流れを示すフローチャート図である。
【図６Ａ】動線の結合スコアを求める様子を示す図である。
【図６Ｂ】動線の結合スコアを求める様子の第１具体例を示す図である。
【図６Ｃ】動線の結合スコアを求める様子の第２具体例を示す図である。
【図７】動線の結合候補を算出する処理の流れを示すフローチャート図である。
【図８】動線の結合候補例を視覚的に示す図である。
【図９】動線の結合処理の様子を視覚的に示す図である。
【図１０】正常な動線の結合の様子を視覚的に示す図である。
【図１１】結合済動線情報を作成する処理の流れを示すフローチャート図である。
【図１２】本発明の第２の実施の形態における動線編集技術の応用例を示す概略図であり、図１Ａに対応する図である。
【発明を実施するための形態】
【００２１】
以下、図面に参照しながら、本発明の実施の形態による動線編集技術について詳細に説明する。尚、本発明の実施の形態は、後述する例に限定されるものではなく、その技術思想の範囲において、種々の変形が可能である。また、実施の形態を説明するための全図において、同一の機能を有する部材には同一または関連する符号を付し、繰り返しの説明は省略する。
【００２２】
＜システム構成＞
図１Ａは、本発明の第１の実施形態による動線編集システムの一構成例を示す機能概略図である。本実施の形態による動線編集システムは、構内や施設、イベント会場など、例えば、店舗１２０１の異なる位置にそれぞれ設置された位置測定装置１２０３Ａから１２０３Ｄまでと、動線編集装置１００と、を有している。
【００２３】
例えば、上記非特許文献１に開示されている公知技術により、店舗内の異なる位置にレーザスキャナを配置し、歩行者（買い物客）のトラッキングを行っている。
【００２４】
位置測定装置１２０３Ａから１２０３Ｄまでは、店舗内を顧客が時々刻々とどのように移動したかを示す動線の情報を取得し記録する装置である。位置測定装置１２０３Ａから１２０３Ｄまでとしては、測域センサ、屋内GPS(Global Positioning System)、Wi-Fi（登録商標）電波強度やBluetoothによる位置測定装置などを利用することができる。
【００２５】
例えば、位置測定装置１２０３Ａから１２０３Ｄまでが測域センサである場合、ある時刻における測域センサと店舗内の対象物との距離を測定し、対象物が人物の部分を分析してその位置を順次抽出することで、出入口１２０５から入って出ていくまでの店舗内の顧客の動線１２０６を得ることができる。なお、図１Ａには位置測定装置１２０３を４台設けた例を示したが、台数は限定されない。
【００２６】
ネットワーク１２０２は、位置測定装置１２０３Ａから１２０３Ｄまでと動線編集装置１００とが互いに通信できるようにするためのものであり、例えばイーサネット（登録商標）、Wi-Fi（登録商標）、USB(Universal Serial Bus)等が挙げられるが、これらに限定されない。
【００２７】
＜動線編集装置の構成例＞
図１Ｂは、動線編集装置１００の一構成例を示す機能ブロック図である。
図１Ｂに示すように、動線編集装置１００は、動線編集処理部１０１と、記憶部１０７とを有している。
【００２８】
動線編集処理部１０１は、位置測定装置１２０３Ａから１２０３Ｄまでから測定情報を取得して断片化した断片動線情報１０８を作成する断片動線作成部１０２と、断片化した動線の終端部に発生する可能性がある異常部分を削除する終端処理後の終端処理済動線情報１０９を作成する動線終端処理部１０３と、断片化した動線に対して結合できる可能性がある結合候補となる別の断片化した動線を探索し、結合に必要な情報を作成する動線結合情報作成部１０４と、前記結合に必要な情報に基づき、断片化した動線同士を結合し、結合済の動線情報である結合済動線情報１１０を作成する結合済動線作成部１０５と、図１Ａにおけるネットワーク１２０２接続のためのインタフェイスを形成するネットワーク接続部１０６と、を有している。
【００２９】
記憶部１０７には、断片動線情報１０８、終端処理済動線情報１０９、結合済動線情報１１０などが保存されている。記憶部１０７としては、ＲＡＭ、ＲＯＭ、ＨＤＤなどを用いることができる。
【００３０】
本実施の形態においては、動線編集装置１００は、例えば、サーバ、PC(Personal Computer)、仮想マシンなどで構成することができる。なお、動線編集装置１００は、コンピュータなどに含まれるCPU(Central Processing Unit)、メモリ、入力指示装置（キーボード・マウス）などが必要に応じて搭載されているものとする。
【００３１】
また、動線編集装置１００が設置されている場所については限定されない。例えば、店舗内に設置されていてもよいし、クラウド上に設けられていてもよい。図１Ｂには、動線編集装置１００の構成例が示されているが、個々の構成要素は別々の動線編集装置１００に設けられていてもよい。
【００３２】
＜動線情報の構成例＞
次に、動線情報のデータ構成例について説明する。
図２Ａは、動線編集処理前の動線情報である断片動線情報１０８のデータ構成例を示す図である。
【００３３】
図２Ａの断片動線情報１０８は、例えば非特許文献１に開示されている技術を用いて得ることができる。図２Ａに示す例では、顧客を一意に識別するｉｄ２０１と、測定された時刻２０２と、その時刻におけるｉｄ２０１で識別される顧客の店舗内における２次元的な位置（ｘ２０３，ｙ２０４）と、が例えば時系列で記憶されている。
【００３４】
断片動線情報について、図２Ａの上から二行目の項目を例にして具体的に説明する。断片動線作成部１０２が、位置測定装置１２０３が測定した情報を解析して店舗内の顧客の位置を検出する。検出した顧客毎に固有の識別子「１」をid２０１として割り当て、検出した時刻「2014-05-01T10:00:00.000+09:00 」をtime２０２とし、店舗内の顧客の座標の横成分「１００」をx２０３、縦成分「２００」をy２０４とする。ここで、座標の原点や座標値の単位は任意で良い。以下では、ｘ１、ｙ１などの記号で説明する。
【００３５】
断片動線作成部１０２は、定期的若しくは非定期的に店舗内の顧客の位置情報を断片動線情報１０８として記録する。但し、id２０１については、例えば非特許文献１に記載されているような方法により以前に検出した顧客と同一人物と推定される場合には、その際に採番したものと同じ識別子（ｉｄ１など）を用いる。
【００３６】
従って、例えば図２Ａに示す断片動線情報１０８からid２０１が「１」であるデータのみを取り出すと、id２０１として「１」が割り当てられた顧客が、どの時刻に店舗内のどの位置に存在したかに関する一連の情報が得られ、これが動線情報となる。
【００３７】
＜断片化した動線の終端部分の処理例＞
測域センサなどを用いて動線を求めた場合には、複数人がすれ違う時（同じタイミングで、測域センサにより同じ位置と判定されてしまう場合）など、測域センサが発するレーザが遮蔽される状況が発生しうる。この状況が発生すると、人物を正確に追跡することができなくなり動線が途切れて断片化してしまう場合がある。特に、混雑している店内などでは頻繁に生じうる。さらに、動線が途切れた場合、動線の終端部分が異常な振る舞いをすることがある。この状況を図３を参照して説明する。
【００３８】
符号３０１は動線を示しており、符号３０２が動線の始点を、符号３０５が動線の終点を示す。つまり、人は始点３０２（時刻ｔ１、位置（ｘ１，ｙ１））から終点３０５（時刻ｔ１３、位置（ｘ１３，ｙ１３））まで移動したことになる。ここで、始点３０２と終点３０５との間の中間点３０３（時刻ｔ４、位置（ｘ４，ｙ４））の位置でレーザが遮蔽された場合を考える。実際の人は動線の移動方向に沿って、例えば破線で示した動線３０６の様に移動していても、装置の仕組みに依存して、正確に人を追跡することができずに、例えば、人がすれ違ったために人の追跡アルゴリズムが上手く機能せずに、本来は人がいない場所に人がいると誤って推定してしまった結果、異常な動線３０４が生成される場合も多い。
【００３９】
このような場合には、後述する動線の結合処理の前に、動線の進行方向や速度などが大きく変化する変化点３０３を検出して（変化点検出部、図示せず。）、前記変化点３０３から終点３０５までを異常な情報とみなして削除する前処理を行うことが好ましい。
【００４０】
図４に、図３の変化点３０３から終点３０５までの異常部分を削除した後の動線終端処理後の動線の一例を示す図である。図３と図４とを比べると、動線の始点３０２の位置は同じであるが、終点の位置は、図４では符号４０３（図３の符号３０３に対応する点）になっている。
【００４１】
＜終端処理済動線情報の作成方法例＞
上記のような動線終端処理部１０３が行う上記のコンピュータによる処理例を、図５のフローチャートを用いて説明する。簡単のため、断片動線情報１０８に含まれるid２０１は１〜Ｎの範囲でありＮ種類とする。また、図２Ｂは、異常な終端を持つ動線情報のデータ構成例を示す図である。適宜、図３、４も参照して説明する。
【００４２】
図５に示すように、動線終端処理部１０３による処理が開始され、変数ｋを１に初期化する（ステップＳ５０１）。
【００４３】
次いで、断片動線情報１０８の中からid２０１がｋ（最初は１）の動線を取り出す（ステップＳ５０２）。図２Ｂに示す顧客ｉｄ２０１＝１の一連のデータを例えば時系列的に得ることができる。
【００４４】
変化点検出部が、ｉｄ２０１がｋ（ここでは“１”）の動線の中から変化点を探索する（ステップＳ５０３）。
【００４５】
変化点検出部による変化点の探索の方法の例としては、例えば、動線の進行方向や速度が予め定めたしきい値を超えた場合や、自己回帰モデル、多項式回帰モデルなどの時系列モデルを用いる方法等がある。具体的な変化点の探索方式は任意で良く、探索方法を限定するものではない。尚、変化点が複数検出された場合は、例えば、最も時刻の遅いものを変化点とみなすか、しきい値を超える度合いが最大の点など何らかの基準により変化点を一つ選びだすこととする。ｉｄ２０１がｋの動線の中で、前記変化点（例えば３０３）から終点（例えば３０５）までの情報を削除する（ステップＳ５０４）。例えば、図２Ｂで、時間ｔ１からｔ４までに比べて、時間ｔ１１以降のデータは位置が大きく変化していれば、変化点以降のデータとして削除する。
【００４６】
ステップＳ５０４で作成した動線情報を終端処理済動線情報１０９として記憶部１０７に書き込む（ステップＳ５０５）。
【００４７】
そして、ｋがＮ（識別可能な顧客の数）に等しいか否かを判定し（ステップＳ５０６）、等しい場合は処理を終了し、等しくない場合はｋに１を加えて（ステップＳ５０７）、ステップＳ５０２以降の処理を繰り返す。
これにより、すべての顧客の動線の終端処理を行うことができる。
【００４８】
＜結合スコア＞
以下に、上記のような方法により断片化した動線を結合する際に必要となる結合スコアを導入する。結合スコアとは、ある動線に対してどの動線を結合させるのが妥当であるかを定量的に示す指標である。例えば、ある動線に対する結合スコアが最小となる動線が結合候補となる。結合スコアが最小となる動線が複数存在する場合は、事前に定めた基準によりいずれかの動線を選択するようにすればよい。
【００４９】
ｉｄ２０１がｊの動線（以降、動線(ｊ)と呼ぶ。）に対するｉｄ２０１がｋの動線（以降、動線(ｋ)と呼ぶ。）の結合スコアをScore(ｊ,ｋ)で表し、以下の計算式（１）で定義する。
【００５０】
Score(ｊ, ｋ) ＝ α×時間的距離(ｊ, ｋ)  ＋  β×空間的距離(ｊ, ｋ)    （１）
【００５１】
ここで、αとβは定数である。また、時間的距離(ｊ, ｋ)と空間的距離(ｊ, ｋ)とは以下のように定義する。
時間的距離(ｊ, ｋ) ＝ ｜動線(ｊ)の終点の時刻 − 動線(ｋ)の始点の時刻｜
空間的距離(ｊ, ｋ) ＝  動線(ｊ)の終点と動線(ｋ)の始点との間の距離
【００５２】
但し、上述の時間的距離(ｊ, ｋ)と空間的距離(ｊ, ｋ)の定義は一例であり、必要に応じて別の定義にしてもよい。
【００５３】
更に、始点や終点の位置や時刻の値が予め定めた値や範囲から外れたり、時間的距離(ｊ, ｋ)、空間的距離(ｊ, ｋ)が予め定めた閾値を超えた場合は、結合スコアは無限大とする。無限大にする理由は、結合スコアを無限大にしておけば結合候補にならないためである。また、結合スコアに閾値を設け、ある動線に対する結合スコアが前記閾値より小さくなるような動線が全くない場合は、前記動線に結合すべき動線はないとすることもできる。
【００５４】
＜断片動線の結合方法＞
図６Ａに、断片化した３つの動線６０１・６０４・６０７を例示的に示す。図２Ｃは、断片化した３つの動線Ｌ１’（６０１）、Ｌ２’（６０４）、Ｌ３’（６０７）のデータ構成例を示す。ここでは、顧客ｉｄが異なると判定されているｉｄ＝１、ｉｄ＝２、ｉｄ＝３のそれぞれにおける、時間と位置との関係が示されている。各動線の始点は、６０２・６０５・６０８であり、終点は６０３・６０６・６０９である。それぞれに対応する時間及び位置は図２Ｃ及び図６Ａに示されている。
【００５５】
図６Ａに示すように終点６０３で途切れた動線６０１と、時間的・空間的に距離が短い（最も近い位置で）別の（新たな）動線が存在する場合は、この２つの動線が同一人物によるものだとして結合するのが自然である。つまり図６Ａでは、顧客ｉｄ＝１の動線６０１の終点６０３と顧客ｉｄ＝２の動線６０４の始点６０５とを結合することができる。
【００５６】
図６Ｂは、動線の結合スコアを求める様子の第１具体例を示す図である。図６Ｂでは、動線６０１の終点６０３に対して、動線６０４の始点６０５と動線６０７の始点６０８のうち、位置的距離又は時間的距離が近い方（Ｌ２１＜Ｌ２２）の動線の始点６０５を結合候補とする例である。
【００５７】
図６Ｃは、動線の結合スコアを求める様子の第２具体例を示す図である。動線６０１の延長線Ｌ３１と、動線６０４を近似的に表した直線Ｌ３２との成す角度θ１と、Ｌ３１と、動線６０７を近似的に表した直線Ｌ３３との成す角度θ２とを比較して、角度が小さい方の動線６０４の結合スコアを小さくすることで、結合した場合に、よりスムーズで自然な動線を結合対象とすることができる。
【００５８】
＜結合候補情報の作成例＞
図７のフローチャートを参照して、動線結合情報作成部１０４が断片化した動線同士をどのように結合するかの結合候補情報を作成する処理例を示す。簡単のため、終端処理済動線情報１０９に含まれるｉｄ２０１は１〜Ｎの範囲でありＮ種類とする。
【００５９】
まず、変数ｋを１、変数ｊを１に初期化する（ステップＳ７０１）。ｋとｊとが等しい場合はステップＳ７０５へ進み、等しくない場合はステップＳ７０３へ進む（ステップＳ７０２）。
【００６０】
終端処理済動線情報１０９からｉｄ２０１がｋの動線と、ｉｄ２０１がｊの動線を取り出す（ステップＳ７０３）。
【００６１】
ステップＳ７０３で取り出した動線に対する結合スコアScore(ｋ, ｊ)を前述の方法を用いて計算する（ステップＳ７０４）。
【００６２】
ｊがＮに等しいか否かを判定し（ステップＳ７０５）、等しい場合はステップＳ７０６へ進み、等しくない場合はｊに１を加えて（ステップＳ７０７）、ステップＳ７０２以降の処理を繰り返す。
【００６３】
ｋがＮに等しいか否かを判定し（ステップＳ７０６）、等しい場合はステップＳ７０９へ進み、等しくない場合はｋに１を加えてｊを１にして（ステップＳ７０８）、ステップＳ７０２以降の処理を繰り返す。
【００６４】
結合候補Pair(x)をｚで定義する。ここでｚはｘを固定した時、Score(ｘ，ｙ)を最小にするｙである。１〜Ｎのｘに対する結合候補Pair(ｘ)を算出する（ステップ７０９）。
【００６５】
ステップＳ７１０において、算出された結合候補を記憶部１０７に格納する。図２Ｃでは、動線Ｌ１’に対して動線Ｌ２’が結合候補となる。
【００６６】
＜仮結合グラフ＞
結合候補Pair(x)を視覚的に表現したグラフを図８に示す。Pair(１)＝２の場合、ｉｄ２０１が１の動線Ｌ１’がｉｄ２０１が２の動線Ｌ２’に結合されることを意味し、符号８０２で示した様に可視化する。更に、図８で同じ数字同士を連結させると、図９に示す様に、複数の動線のｉｄ２０１が結合したグラフ（以降、「仮結合グラフ」と呼ぶ。）を作成することができる。図９では、符号９０２と符号９０３との２つの仮結合グラフが示されている。一般に、結合候補Pair(ｘ)の情報を元にして仮結合グラフを作成すると、Ｍ個の仮結合グラフができる。
【００６７】
ここで符号９０１の部分に着目すると、ｉｄ２０１が「５」の動線は、ｉｄ２０１が「４」と「９」との２つの異なる動線から結合されている状況になっている。このような状況は、測域センサの遮蔽が激しく人物の追跡が十分に行えなかった場合等に発生し、上述の結合スコアを用いた方法でも正しく結合できない場合に相当する。この場合は、ｉｄ２０１が「４」と「５」、「９」と「５」は結合させないようにする。
【００６８】
尚、１つの動線に対して 異なる２つの動線が対応付け可能な場合には、前記対応付けを行わないようにするために、図９の段階で上記の結合を解除する処理に代えて、図８の段階で、あらかじめ、「４」と「５」、「９」と「５」は結合させないようにしても良い。
【００６９】
図１０に、「４」と「５」、「９」と「５」を結合させなかった場合のグラフ（以降、「結合グラフ」と呼ぶ。）を示す。図１０では、異なる２つのｉｄ２０１から結合されている状態は回避されていることが分かる。なお、図９の符号９０３は全てのｉｄ２０１に対して２つ以上のｉｄ２０１から結合される状況が発生していないため、符号９０２の様に結合を解除する必要はない。
【００７０】
＜結合済動線の作成例＞
図１１のフローチャートを参照して、結合済動線作成部１０５が、仮結合グラフから結合済動線情報１１０を作成する手順例を示す。
【００７１】
終端処理済動線情報１０９に対して図７で説明した処理方法を用いて結合候補Pair(ｘ)を算出し、仮結合グラフを生成する（ステップＳ１１０１）。ここで、仮結合グラフがＭ個生成されたとする。また、それぞれの仮結合グラフを、Ｆｊ（１≦ｊ≦Ｍ）と表記する。更に、Ｆｊにはｉｄ２０１がＬｊ個含まれていたとする。また、Ｌｊ個のｉｄ２０１をｉｄｋ（１≦ｋ≦Ｌｊ）と表記する。
【００７２】
次いで、変数ｋを１、変数ｊを１に初期化する（ステップＳ１１０２）。
仮結合グラフＦｊのｉｄｋが２つ以上のｉｄ２０１から結合されているか否かを判定し、ＹＥＳの場合はステップＳ１１０４へ進み、ＮＯの場合はステップ１１０５へ進む（ステップＳ１１０３）。
【００７３】
仮結合グラフＦｊのｉｄｋが２つ以上のｉｄ２０１から結合されている場合は、ｉｄｋへの結合を解除する（ステップＳ１１０４）。
【００７４】
ｋがＬｊに等しいか否かを判定し（ステップＳ１１０５）、等しい場合は（ＹＥＳ）、ステップＳ１１０６へ進み、等しくない場合は（ＮＯ）、ｋに１を加えて（ステップＳ１１０８）、ステップＳ１１０３以降を繰り返す。
【００７５】
ステップＳ１１０４で結合を解除した結果、一般に仮結合グラフＦｊからＮｊ個の結合グラフが得られる（ステップＳ１１０６）。ここで得られた結合グラフをＧｊｉ（１≦ｊ≦Ｍ、１≦ｉ≦Ｎｊ）と表記する。
【００７６】
ｊがＭに等しいか判定し（ステップＳ１１０７）、等しい場合は（ＹＥＳ）、ステップＳ１１１０に進み、等しくない場合は（ＮＯ）、ｊに１を加えてｋを１にして（ステップＳ１１０９）、ステップＳ１１０３以降の処理を繰り返す。
変数ｉを１、変数ｊを１に初期化する（ステップＳ１１１０）。
【００７７】
ステップＳ１１０６で作成した結合グラフＧｊｉに含まれる複数ｉｄ２０１を取り出し、終端処理済動線情報１０９内で前記複数ｉｄ２０１に該当するｉｄ２０１を、新たに採番したｉｄ２０１で置換し、結合済動線情報１１０を作成する（ステップＳ１１１１）。例えば、図１０では、「１→２→３→４」という結合グラフがあるが、終端処理済動線情報１０９内に含まれるｉｄ２０１が「１」、「２」、「３」、「４」の部分を、新たに採番した例えば「１００」で置換する。これにより、ｉｄ２０１が「１」、「２」、「３」、「４」の動線は全てｉｄ２０１が「１００」となる連結した動線となる。
【００７８】
ｉがＮｊに等しいか判定し、等しい場合はステップＳ１１１３に進み、等しくない場合はｉに１を加えて（ステップＳ１１１４）、ステップＳ１１１１以降の処理を繰り返す。
【００７９】
ｊがＭに等しいか判定し（ステップＳ１１１３）、等しい場合は処理を終了し、等しくない場合はｊに１を加え、ｉを１にして（ステップＳ１１１５）、ステップＳ１１１１以降の処理を繰り返す。
【００８０】
以上により、仮結合グラフから結合済動線情報１１０を作成することができる。
本実施の形態によれば、測域センサで取得した断片化している動線情報を自動で適切に結合することが可能となる。
【００８１】
尚、結合スコアを求める際の重み付け係数について以下のように設定してもよい。
図１２は、図１Ａに対応する図であり、得られた動線１２０６と店舗内のエリアとの関係を示す図である。上記の（１）式の係数α、βは、エリア内の位置、すなわち、例えば店舗であれば、その棚の商品属性等に依存させて変更するようにしてもよい。図１２で、動線１２０６を得る場合に、エリア１２１１においては、α＝α１、β＝β１とし、エリア１２１２においては、α＝α２、β＝β２として異なる値を設定することができる。例えばエリア１２１１が飲料の配置エリアであり、エリア１２１２が本の配置エリアであるとする。一般的に、飲料を買う顧客はその位置に長く滞在する確率が低く、本を買う顧客はその位置に長く滞在する確率が高い。そこで、時間的距離の重み付け係数β１、β２を、エリアにより異なるようにすると良い。例えば、本の配置エリアであるエリア１２１２の時間的距離の重み付け係数β２は、飲料の配置エリアであるエリア１２１１の時間的距離の重み付け係数β１よりも、小さくする必要がある。
【００８２】
このように、エリアの属性に依存して、重みづけ係数を変更するようにすることで、精度の高い結合スコアを求めることができる。
【００８３】
尚、あるエリアにおける重みづけ係数は、動線に関する統計的なデータに基づいて決めるようにしてもよい。
【００８４】
（利用例）
以下に、上記の手法により得られた動線情報の利用例を説明する。
例えば、店舗に入店した顧客の動線が店舗内で断片化したとしても、本実施の形態の手法を用いることで動線を結合し、顧客が退店するまでの動線を作成することが可能になる。
【００８５】
入店から退店までの動線を用いることで以下のような顧客の特徴を捉えることが可能となる。
(１)  入店したが何も購買することなく退店した非購買客の動きを取得することで、例えば、そのような客であっても興味を示したエリア（商品等）を知ることで、商品の変更などの際の参考にすることができる。
(２)  大量の動線の中から主要な動線をパターン分類することで、大まかな顧客の動向を知ることができる。
(３)  家族連れなど共連れを検知することで、家族の場合の購入傾向などを知ることができる。
(４)リピート顧客を検知することで、例えば商品の売り上げ予測を立てやすいなどの利点がある。
(５)  店舗内でスムーズに進行せずに、うろついている、Ｕターンする、異常な行動を取る、レジ待ちをしている顧客を発見することで、危険防止等に活用できる。
【００８６】
更に、上記の特徴を分析することで以下のようなビジネス価値が生まれる。
(６)  スタッフの数の最適化による人員コスト削減、
(７)  発注の最適化による廃棄コスト削減、
(８)  店舗内で顧客が寄り付かない場所へ顧客を誘導することによる売上向上、
(９)  死に筋商品の入替えによる売上向上、
(１０)  欠品状態を回避することによる機会損失の減少、
(１１)  顧客の店舗内の回遊量を最適化することによる売上向上、
(１２)  棚の前の人の寄り付き具合と、棚の商品の売行きとを可視化して比較することによる商品の魅力の定量化や、レイアウト変更等による売上向上。
【００８７】
上記の実施の形態において、添付図面に図示されている構成等については、これらに限定されるものではなく、本発明の効果を発揮する範囲内で適宜変更することが可能である。その他、本発明の目的の範囲を逸脱しない限りにおいて適宜変更して実施することが可能である。
【００８８】
また、本発明の各構成要素は、任意に取捨選択することができ、取捨選択した構成を具備する発明も本発明に含まれるものである。
【００８９】
また、本実施の形態で説明した機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各部の処理を行ってもよい。尚、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
【産業上の利用可能性】
【００９０】
本発明は、動線編集装置として利用可能である。
【符号の説明】
【００９１】
１００…動線編集装置
１０２…断片動線作成部
１０３…動線終端処理部
１０４…動線結合情報作成部
１０５…結合済動線作成部
１０８…断片動線情報
１０９…終端処理済動線情報
１１０…結合済動線情報
３０１…動線
【図１Ａ】
0006397706.tif 000002
【図１Ｂ】
0006397706.tif 000003
【図２Ａ】
0006397706.tif 000004
【図２Ｂ】
0006397706.tif 000005
【図２Ｃ】
0006397706.tif 000006
【図３】
0006397706.tif 000007
【図４】
0006397706.tif 000008
【図５】
0006397706.tif 000009
【図６Ａ】
0006397706.tif 000010
【図６Ｂ】
0006397706.tif 000011
【図６Ｃ】
0006397706.tif 000012
【図７】
0006397706.tif 000013
【図８】
0006397706.tif 000014
【図９】
0006397706.tif 000015
【図１０】
0006397706.tif 000016
【図１１】
0006397706.tif 000017
【図１２】
0006397706.tif 000018