(57)【要約】【課題】複数の端末において形成される集団を詳細に検知可能であり、且つ簡素に実現可能な、集団検知装置と端末を提供する。【解決手段】集団を形成しうる各端末20,30等は固有の端末IDを変調したパルス状の音波を一定間隔を設けて送信し続け、同時に音波を受信・復調して、受信時刻と対応する端末IDを得て、集団検知装置10へ送信する。距離推定部12は、2端末間における音波送受信時刻の差によって、当該2端末間の距離を推定する。集団検知部13は、各2端末間において推定された距離に基づいて、複数の端末にて形成されている集団を検知する。【選択図】図２
2014190824.tif 000002
【特許請求の範囲】
【請求項１】
端末毎に付与された端末IDを変調することで互いに区別可能なパルス状の音波を、一定間隔で送信し続ける複数の端末の各々より、各端末の送信音波の受信時刻を受信し、当該複数の端末において形成される集団を検知する集団検知装置であって、
第一端末における自身の送信音波の受信時刻及び第二端末の送信音波の受信時刻の差と、第二端末における自身の送信音波の受信時刻及び第一端末の送信音波の受信時刻の差と、の差に基づいて、第一端末と第二端末との距離を推定する距離推定部と、
前記推定された各端末間の距離に基づいて、前記複数の端末において形成される集団を検知する集団検知部と、を備えることを特徴とする集団検知装置。
【請求項２】
前記集団検知部は、同一の集団に属する各端末は、当該集団内における1台以上の他の端末との距離が所定の閾値条件を満たすことに基づいて、前記集団を検知することを特徴とする請求項１に記載の集団検知装置。
【請求項３】
前記複数の端末の各々は、予め所属すべき集団が定められた端末であって当該所属すべき集団に対応するグループIDが付与され、前記送信する音波には当該グループIDが変調され、自身と共通のグループIDが変調された音波のみの受信時刻を求め、
前記集団検知部は、グループIDが共通の端末ごとに、前記集団を検知し、
当該グループIDごとに検知された集団が、単一のグループIDに対して複数存在する場合に、所属端末数が最大の集団以外に属している端末を、本来所属すべき集団から逸脱した端末として検知する集団変化検知部をさらに備えることを特徴とする請求項１または２に記載の集団検知装置。
【請求項４】
前記集団検知部は、前記推定された各端末間の距離に基づいて、前記一定間隔ごとに履歴として集団の候補を検知し、当該履歴において所定期間に渡って連続的に、直前に検知された集団からの所属端末の変化率が所定の閾値条件を満たすものを、本来の集団であるとして判定することを特徴とする請求項１または２に記載の集団検知装置。
【請求項５】
前記集団検知部は、前記本来の集団として判定された集団を、所属端末をノードとし端末間距離をエッジのコストとするグラフとして表現し、当該グラフに基づいて、当該集団が行列を形成しているかをさらに判定することを特徴とする請求項４に記載の集団検知装置。
【請求項６】
前記集団検知部は、前記グラフの全域最小木を求め、当該木における点及び葉の個数に基づいて、前記集団が行列を形成しているかを判定することを特徴とする請求項５に記載の集団検知装置。
【請求項７】
前記集団検知装置が、前記複数の端末のいずれかにおいて実現されていることを特徴とする請求項１ないし６のいずれかに記載の集団検知装置。
【請求項８】
請求項１ないし６のいずれかに記載の集団検知装置によって集団が形成されているかを判定される、個別の端末IDが付与された端末であって、
前記端末IDを変調したパルス状の音波を、一定間隔を設けて送信し続ける音波送信部と、
音波を受信して復調し、自身及び他の端末IDに対応する各音波の受信時刻を求める音波受信部と、
前記受信時刻を前記集団検知装置に送信する通信部と、を備えることを特徴とする端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音波や超音波を利用することにより、端末が形成する集団や行列の有無や変化を検知する集団検知装置及び端末に関する。
【背景技術】
【０００２】
集団や行列の有無や変化を検知する従来技術として、GPS(全地球測位システム)やWi-Fi(登録商標)を使った位置測定の利用がある。スマートフォンやフューチャーフォン等の端末を通して各ユーザの位置を測定し、測定結果から端末密度の高い場所を特定することで、集団を検知できる。
【０００３】
また、集団検知には、カメラを利用することもできる。特許文献1では、定点カメラで道路を通過する自動車を撮影することで、道路の混雑度を推定する。特許文献2では、電車内に設置したカメラの画像から、電車内の混雑度を推定する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2002-342748号公報（待ち行列検出方法及び待ち行列検出装置）
【特許文献２】特開2012-118790号公報（混雑度推定装置）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
集団検知技術には上記のような従来技術が存在するが、ここで、集団や行列の有無や変化を検知できると、様々なサービスが提供可能になる。
【０００６】
例えば、集団登下校において、集団から逸脱する児童を早期検知できれば、迷子や誘拐等を未然に防止できる可能性が高まる。同様に、集団登山や団体ツアーにおいて、逸脱者を検知することで、遭難を未然に防止できる。他にも、ラーメン店やレストラン、トイレ等、店舗や公共施設・設備付近の集団や行列を検知できれば、混み具合や待ち時間の推定・提供が可能となる。
【０００７】
しかしながら、上記のような応用を実現しようとした場合、従来技術におけるGPSやWi-Fi(登録商標)を使った位置測定は10m〜100m程度の誤差を含むため、イベント会場の来場者等の大規模(直径100m以上)な集団は検知できるが、集団登下校等の小規模(直径10m程度)な集団の検知や、集団から逸脱する児童等の検知は困難である。すなわち、精度よく位置測定して集団を詳細に検知することは困難である。
【０００８】
また、上記のような応用を実現しようとした場合に、従来技術として特許文献１，２におけるようなカメラの利用を行うと、小規模な集団なども検知可能とはなるが、定点カメラを設置する必要が生じてしまい、検知手段を簡素に実現できない。さらに、検知可能な範囲も当該定点カメラの撮影範囲内に限定され、集団が移動して撮影範囲内では見えなくなった際に検知し続けることは不可能であり、やはり集団を詳細に検知することは困難である。
【０００９】
本発明は、上記従来技術の課題に鑑み、複数の端末において形成される集団を詳細に検知可能であり、且つ簡素に実現可能な、集団検知装置を提供することを第一の目的とする。
【００１０】
本発明はまた、前記集団検知装置によって集団が検知される端末を提供することを第二の目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明は、端末毎に付与された端末IDを変調することで互いに区別可能なパルス状の音波を、一定間隔で送信し続ける複数の端末の各々より、各端末の送信音波の受信時刻を受信し、当該複数の端末において形成される集団を検知する集団検知装置であって、第一端末における自身の送信音波の受信時刻及び第二端末の送信音波の受信時刻の差と、第二端末における自身の送信音波の受信時刻及び第一端末の送信音波の受信時刻の差と、の差に基づいて、第一端末と第二端末との距離を推定する距離推定部と、前記推定された各端末間の距離に基づいて、前記複数の端末において形成される集団を検知する集団検知部と、を備えることを第一の特徴とする。
【００１２】
また、本発明は、集団検知装置によって集団が形成されているかを判定される、個別の端末IDが付与された端末であって、前記端末IDを変調したパルス状の音波を、一定間隔を設けて送信し続ける音波送信部と、音波を受信して復調し、自身及び他の端末IDに対応する各音波の受信時刻を求める音波受信部と、前記受信時刻を前記集団検知装置に送信する通信部と、を備えることを第二の特徴とする。
【発明の効果】
【００１３】
前記第一の特徴によれば、端末間で送受信される音波の受信時刻に基づいて、集団を詳細に検知可能となる。この際、主に利用するのは音波であるので、定点カメラ等は不要であって、簡素に実現可能である。従って、前記第一の目的が達成される。
【００１４】
前記第二の特徴によれば、前記第一の特徴に係る集団検知装置により集団形成が検知される端末の各々が提供されるので、前記第二の目的が達成される。
【図面の簡単な説明】
【００１５】
【図１】一実施形態に係る集団検知システムの構成を示す図である。
【図２】集団検知システムを構成する集団検知装置及び端末の機能ブロック図である。
【図３】一実施形態に係る集団検知の際の、2端末間での処理フローの概要を示す図である。
【図４】各回の距離推定における第一処理として、各端末から得た受信時刻を集計した情報を説明するための図である。
【図５】各回の距離推定における第二処理として、各端末間の距離が計算され集計されることを説明するための図である。
【図６】第一実施形態に係る集団検知処理のフローチャートである。
【図７】集団変化検知処理のフローチャートである。
【図８】第二実施形態における(条件1)及び(条件2)を満たす集団検知処理のフローチャートである。
【図９】図８のフローで得られる集団履歴を示した図である。
【図１０】行列検知の例を示す図である。
【発明を実施するための形態】
【００１６】
図１は、一実施形態に係る集団検知システムの構成を示す図である。集団検知システム100は、複数(N台)の端末T1, T2, ..., TNと、集団検知装置10と、を備え、これらはネットワーク等を介して相互にデータ通信可能である。各端末は、マイク及びスピーカを利用して、端末同士の間で音波を送信及び受信する。当該音波は、超音波であってもよい。マイク及びスピーカの構成は、端末における内蔵型であっても、外付け型であってもよい。
【００１７】
各端末Ti(i=1,2,…,N)はまた、通信デバイスを利用して他端末Tj(j≠i)の各々及び集団検知装置10と通信する。通信形態としては、Bluetooth(登録商標)やWi-Fi direct(登録商標)、音波通信等の近距離通信を利用して端末間で直接通信する形態であってもよいし、3GやWiMAX(登録商標)、LTE、Wi-Fi(登録商標)等の中遠距離無線通信を利用して、基地局やアクセスポイントを介してネットワーク通信する形態であってもよい。集団検知装置10は、インターネット上のサーバに実装してもよい。
【００１８】
なお、各端末は典型的にはスマートフォンやフューチャーフォン等の携帯型端末であり、端末のユーザが常に携帯していることにより、端末の位置がユーザの位置となることが前提となる。
【００１９】
本発明における、一実施形態に係る検知処理の概要は次の通りである。各端末は、自身及び所属グループのIDを重畳した音波を所定間隔で送信すると共に、同様に送信している他端末からの音波を受信し、そのIDを識別する。各端末は、各音波の受信時刻すなわち、自身の音波送信時刻(自身の音波送信を自身がID識別して受信した時刻)と、ID識別された他端末からの音波受信時刻と、を集団検知装置10へ通知する。
【００２０】
集団検知装置10は、当該通知結果を用いて各端末間の距離を推定し、当該推定距離により、各端末が集団に属しているか、すなわち、各ユーザが集団に属しているかを検知する。また、当該集団の変化も検知する。以下、詳細を説明する。
【００２１】
図2は、集団検知システム100の構成要素としての、集団検知装置10及び端末20,30のそれぞれの機能ブロック図である。ここでは、図1で説明したような複数(N台)の端末T1, T2, ..., TNのうちの2台として、端末20,30を示している。端末20,30は同様の構成であり、同様に機能するが、説明の際は、端末20を「N端末のうちの任意の1台としての自身(あるユーザ)の端末」、端末30を「自身から見た他のN−1台の端末のうちの任意の1台」として説明する。
【００２２】
集団検知装置10は、登録端末管理部11、距離推定部12、集団検知部13、集団変化検知部14及び通信部15を備える。端末20は、端末情報管理部21、音波受信部22、音波送信部23及び通信部25を備える。端末30も、類似の参照番号を付与しているように、端末20と同様の構成を備える。
【００２３】
登録端末管理部11は、端末20,30などの、本発明による集団検知を実施する対象となる端末のID等の登録を予め受け付けて、登録情報として管理して保持する。当該登録情報によって、図1で説明したような各端末Ti(i=1,2,…,N)の識別が可能となり、集団検知が実施される。
【００２４】
距離推定部12は、各端末20,30等から受信した、各端末における音波受信時刻のデータを用いて、端末間の距離を推定する。集団検知部13は、当該推定された距離によって、集団の有無と、各端末がいずれの集団に属しているか(集団所属情報)を検知する。集団変化検知部14は、当該検知された集団及び集団所属情報によって、集団の変化を検知する。
【００２５】
端末情報管理部21,31は、各端末20,30自身に設定されたID等の情報を管理して保持する。
【００２６】
音波送信部23,33は、スピーカを通じて音波を送信する。当該音波は、距離推定部12における距離推定のために利用されるものであり、一定間隔を設けて送信されるパルス状の音波である。
【００２７】
音波受信部22,32は、当該送信されたパルス状の音波を受信して、受信時刻を求める。当該受信対象となる音波は、自身を含むすべての端末からの送信音波である。例えば端末20では、図2で矢印を描いてあるように音波受信部22において、自身が音波送信部23で送信した音波と、他の端末30等が音波送信部33等で送信した音波と、の全てを受信し、いずれの端末から送信された音波であるかを識別したうえで、その受信時刻を記録する。
【００２８】
通信部15,25,35は、上記受信時刻や、予め登録する端末IDなどといった、集団検知を行うに際して必要となる種々の情報を、端末間又は端末−集団検知装置10間で無線通信する。なお、当該情報の伝達が可能であれば、必ずしも無線である必要はなく、音波などを用いてもよい。ただし、距離推定用とは別途に、情報伝達用の音波を設定しておくものとする。
【００２９】
なお、図1、図2その他において、集団検知装置10は端末とは別途のものとして説明し、以下もそのように説明するが、本発明においては、端末上に集団検知装置10が実装されていてもよい。すなわち、1つ以上の端末が集団検知装置10の機能を有していてもよい。この場合、当該端末は、自身が音波の送受信を行って集団検知される対象となると共に、当該集団検知を実施する機能をも担うこととなる。同様に、集団検知装置10の機能のうち任意の一部分(例えば、距離推定部12など)が、1つ以上の端末において実装されていてもよい。
【００３０】
以下、第一実施形態に係る集団検知を説明する。図3に、当該第一実施形態における、全ての2端末間での処理フローの概要を示す。ここでは説明のため、2端末は、図2と同様の端末20,30であり、当該端末20,30は(端末IDの言及のため)、それぞれ端末T1,T2であるものとする。
【００３１】
ステップS20,S30にて、それぞれ端末20,30は、本発明に係る音波送受信並びにデータ収集及び送信を実施するためのアプリを起動する。すなわち、アプリケーションのプログラムを読み込み、本発明の所定ルーチンの実行が開始される。なおここで、当該起動される前の事前準備として、予め以下を行っておく。
【００３２】
（事前準備１）
各端末Ti(i=1,2,…,N)の端末情報管理部(端末20,30であれば、端末情報管理部21,31)に、端末IDとグループIDを、ユーザ又は管理者がマニュアルで登録する。端末IDとグループIDはそれぞれ、端末と集団を一意に特定するためのIDである。
【００３３】
当該端末ID及びグループIDにより、第一実施形態では、集団登下校などの予め誰がいずれのグループに属しているべきかが既知の状況における集団検知を可能とする。すなわち、各グループが本来の所属メンバーによって正しく形成されているか、迷子などが発生していないか、等を検知する。
【００３４】
（事前準備２）
集団検知装置10では、登録端末管理部11に集団情報をマニュアル登録する。集団情報は、上記（事前準備１）における各端末の登録情報を集計して、グループIDに対する端末IDリストとして構成する。端末IDリストは、登録されたグループIDの集団を構成する全端末の端末IDのリストである。
【００３５】
例えば、集団登下校であれば、地域i(i=1,2, ...)にて登下校するグループiに所属する児童リストLi(当該児童の端末リストLi)といった形で、集団情報が与えられる。なお、（事前準備１）が各端末にて実施される毎にその登録情報を集団検知装置10に送信して、自動で逐次的に（事前準備２）の登録情報が構築されるようにしてもよい。逆に、予め（事前準備２）で全体の登録情報を構築しておいてから、各端末に対応する登録情報を送信することによって、（事前準備１）が自動で実施されるようにしてもよい。
【００３６】
以上の事前準備の後に、図３のステップS20,S30にてアプリが起動されると、端末20,30(端末T1,T2)はそれぞれ、以下のような音波送信処理、音波受信処理、受信時刻伝達処理を開始する。当該各処理は互いに同時並行で実施される。
【００３７】
(音波送信処理)
音波送信部23,33にて、一定間隔T毎に音波を送信する。その際、音波を端末毎に互いに区別可能なように、自身に設定されているグループIDと端末IDの情報を音波に変調して送信する。変調方式としては、無線通信や音波通信において広く利用されているFSK (周波数偏移変調；Frequent Shift Keying)、PSK (位相偏移変調；Phase Shift Keying)、ASK (振幅偏移変調；Amplitude Shift Keying)等を利用することができる。
【００３８】
図３では、端末20はステップS21,S23,S25, ...にて、一定間隔Tを設けながら1,2,3,...回目の音波を順に送信している。この際、端末20(端末T1)自身に設定されているグループIDであるGID1と、端末IDであるID1とを変調した音波1が毎回送信される。同じく、端末30はステップS32,S34,S36, ...にて、一定間隔Tを設けながら1,2,3,...回目の音波を順に送信している。この際、端末30(端末T2)自身に設定されているグループIDであるGID1と、端末IDであるID2とを変調した音波2が毎回送信される。
【００３９】
なお、一定間隔Tは、グループIDが同じ端末間で共通のものを、事前準備の段階において設定しておく。また、音波変調方式及び当該方式において利用するパラメータ等も、自身と同じグループIDの全ての端末における設定を、事前準備の段階で各端末において共有し保持しておく。当該設定などは、端末情報管理部21,31や登録端末管理部11に記録しておけばよい。
【００４０】
(音波受信処理)
音波受信部22,32では、逐次的に録音データを取得し、当該録音データより逐次的に音波の検出を試みる。音波が検出された場合さらに、音波を復調してグループIDと端末IDを取り出す。取り出したグループIDが自身に設定されているグループIDと一致した場合、その音波の受信時刻を計算する。
【００４１】
当該検出して復調される音波には、自身が送信した音波と、他の端末が送信した音波と、が含まれる。グループIDが異なる音波については、計算不要であるので受信時刻は計算しない。なお、前述の事前設定で音波変調方式及びパラメータ等が各端末において既知であるので、復調が可能となる。
【００４２】
図３では、端末T1において、端末T2からのステップS32,S34,S36,...の送信音波を受信したステップS22,S24,S26,...が描かれているが、端末T1ではこの他にも、端末T1(端末20)自身の送信音波を受信(音波送信部23の送信を音波受信部22で受信)し、端末T2以外のその他の端末からの送信音波も受信し、それぞれを検出・復調する。
【００４３】
同様に、端末T2において、端末T1からのステップS21,S23,S25,...の送信音波を受信したステップS31,S33,S35,...が描かれているが、端末T2ではこの他にも端末T2(端末30)自身の送信音波を受信(音波送信部33の送信を音波受信部32で受信)し、端末T2以外のその他の端末からの送信音波も受信し、それぞれを検出・復調する。
【００４４】
（受信時刻伝達処理）
各端末にて、逐次的に得られる受信時刻を、無線通信により逐次的に集団検知装置10へと送信する。こうして、集団検知装置10においては、各端末Tiが同グループの端末Tjからの音波をk回目に受信した時刻t[i,j,k]が各k回ごとに、各グループごとに区別して蓄積されていく。なおここで、前述のようにj＝iの場合すなわち、各端末が自身で送信した音波の受信時刻も含まれている。
【００４５】
なお、ステップS20,S30等のアプリ起動の際に、各端末間で時計合わせをしておき、グループ毎に一定間隔Tで音波送信するタイミングが各端末で概ね一致し、回数のカウンタkを共有できるようにしておく。また、一定間隔Tは、音波が端末間を伝達するのに要する時間と比較してある程度は長い間隔として設定しておく。以上のようにして、各端末Tiでは自身のk回目の送信を自身が受信した時刻t[i,i,k]に最も近い受信時刻として、各他端末Tj（ここでは、j≠i）からのk回目の送信音波の受信時刻t[i,j,k]を特定したうえで、集団検知装置10へと送信することが可能となる。
【００４６】
また、上記のように受信時刻t[i,j,k]を特定することによって同様に、k回目においては端末Tiは端末Tjからの送信音波を受信できなかった旨も特定することが可能となる。この場合、受信時刻t[i,j,k]に代えて、当該受信時刻t[i,j,k]として受信されるべきであった音波が受信不可能であった旨の情報を、集団検知装置10へと送信する。
【００４７】
以上の各端末からの（受信時刻伝達処理）に連動して、各グループごとに各k回の受信時刻t[i,j,k]を蓄積する集団検知装置10では、各回kごとに、以下の距離推定処理、集団検知処理、集団変化検知処理を実施する。この際の各回kの間隔は、各グループにて設定されている音波の送信間隔Tと一致させることで、リアルタイムでの検知が可能となる。
【００４８】
(距離推定処理)
逐次的に取得される各k回の受信時刻t[i,j,k]により、距離推定部12は、第一処理として、図4に示すような受信データの集計情報を生成する。当該集計情報を構成しているIIJ(k)は、端末TIの音波の送信時刻(端末TI自身の送信音波の自身での受信時刻)と、端末TJの送信音波の端末TIにおける受信時刻との差の絶対値として、以下のように計算する。
IIJ(k) ＝ |t[I,I,k]−t[I,J,k]|
【００４９】
なお、端末TIと端末TJとの間の距離によっては、前述のように互いの音波を受信できない場合もある。端末TIが端末TJの送信音波を受信できなかった場合、IIJ(k)=∞として、受信不能の旨を表すようにすればよい。
【００５０】
続いて、距離推定部12は第二処理として、当該各k回における各端末間の距離DIJ(k)を計算する。共通のkの表記を省略すると、距離DIJ=|IIJ-IJI|*c/2と計算できる。ここで|IIJ-IJI|/2は音波の伝搬時刻を、cは音速をそれぞれ表す。結果として、図5に示すような各端末間の距離DIJの集計結果が得られる。
【００５１】
なお、上記の式によって端末TI,TJ間の距離DIJが計算可能である旨は、以下の特許文献３，４又は非特許文献1に説明されているため、ここではその説明は省略する。本発明では特に、当該手法を利用することによって、一般的な携帯型端末などで利用可能なスピーカ及びマイクによって、以下説明する集団検知部13等において、小集団の変化であっても検知可能な精度を実現する。
【００５２】
なお、当該手法によれば、各端末は自身のみにおける受信時刻を測定すればよいので、端末間の時計合わせは不要である。しかし、本発明では各k回の管理を行うために、前述のように時計合わせを実施するが、当該k回の区別が可能な精度があればよい。なおまた、当該文献に開示のように、端末のマイク・スピーカ間の距離の値を用いることによって当該距離DIJをさらに精度良く計算するようにしてもよい。
【００５３】
[特許文献3] 特願2012-210109号
[特許文献４] 米国特許7,729,204号公報 ("Acoustic Ranging")
[非特許文献１] BeepBeep: a high accuracy acoustic ranging system using COTS mobile devices; Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia
【００５４】
（集団検知処理）
集団検知部13は、距離推定部12による各端末間の距離DIJ(k)の集計結果から、当該k回目の時点にて共通グループIDに属する端末が形成している集団を検知する。集団である旨を判定する条件として、以下のような（条件１）を用いることができる。ここで、距離DTHは同じ集団に属するか否かを判断するための端末間の距離の閾値である。
【００５５】
（条件１）同じ集団に属する各端末TIは、同集団内の1台以上の他の端末TJと距離DTH以内に位置する
【００５６】
上記の（条件１）を用いた集団の検知処理を説明する。図６は、当該条件を用いた集団の検知処理のフローチャートである。ここで、対象とするグループIDをGID1、グループGID1を構成する端末IDのリストL(GID1)を{ID1, ID2, …, IDN}とする。
【００５７】
ステップS605では、端末IDをリストで格納する変数(端末ID集合)L'に対し初期値として当該リストL(GID1)＝{ID1, ID2, …, IDN}（すなわち、対象としている全ての端末のID）を格納し、カウンタ変数jに初期値1を設定し、リスト変数Sj(当該時点でj=1であるため、Sj＝S1)に初期値φ(空のリスト)を格納(Sj＝φ)して、ステップS610へ進む。
【００５８】
ステップS610では、リスト変数L'内より任意の1つの端末IDを取り出して、そのIDをIDtmpとし、リスト変数L'より当該IDtmpを除外し(L'＝L'−IDtmp)、また、リスト変数Sjに当該IDtmpを追加して格納し(Sj＝Sj+IDtmp)、ステップS615へ進む。
【００５９】
ステップS615では、リスト変数Sjに属する端末IDを有する1台以上の端末との距離が閾値Dth以内となる端末のIDを、リスト変数L'から全て取り出して、リスト変数Ltmpに格納し、ステップS620へ進む。ステップS620では、集合Ltmpが空集合(φ)に等しいかが判定され、等しいならばステップS630へ進み、等しくなければステップS625へと進む。ステップS625では、リスト変数L'よりリスト変数Ltmpを減算し(L'=L'−Ltmp)、また、リスト変数Sjに同リスト変数Ltmpを加算し(Sj＝Sj+Ltmp)、ステップS615へ戻る。
【００６０】
ステップS630では、リスト変数L'が空集合(φ)に等しいかが判定され、等しければ当該フローは終了となる。なお、当該終了した時点で得られている1つ以上の集合Sjの各々が、ある集団に属する端末IDのリストとなっている。得られた結果がS1のみであれば、S1＝L(GID1)であって、当該グループID(GID1)の全ての端末が単一の集合に属していることを意味している。また、S1及びS2の2つの結果が得られれば、当該2つの集団が形成されていることを意味する。
【００６１】
一方、ステップS630で、リスト変数L'が空集合(φ)に等しくないと判定されれば、ステップS635へ進む。ステップS635では、カウンタ変数jを1だけ増分し(j＝j+1)、また、当該増分されたカウンタ変数jによって、リスト変数Sjを設け、初期値として空集合(φ)を設定(Sj＝φ)してから、ステップS610へ戻る。
【００６２】
以上の図６のフローにより、集団条件を満たす集団Sjが抽出される。端末間の距離DIJにより、前述のように全ての端末を含む集団S1が抽出される場合もあれば、2個以上の集団Sjに分割される場合もある。
【００６３】
（集団変化検知処理）
集団変化検知部14は、集団検知部13の検知結果に基づき、本来の集団から逸脱していると判定される端末を検知する。図７は、集団変化検知部14による処理のフローチャートである。
【００６４】
ステップS705では、（図６の場合と同様に、）当該対象としているグループGID1を構成する全ての端末IDのリストL(GID1)を{ID1, ID2, …, IDN}とし、リスト変数L'に当該リストL(GID1)を格納(L'＝L(GID1))して、ステップS710へと進む。ステップS710では、集団検知部13の検知結果Sjを参照して、集合(対応する集団)に属する端末数|Sj|が最大の集合SjをSmaxとし、当該集合Smaxに所属する端末数をCmaxとして、ステップS715へ進む。
【００６５】
ステップS715では、当該端末数Cmaxが、当該対象としているグループGID1を構成する全ての端末の個数Nに等しいかが判定され、等しければステップS720へ進み、等しくなければステップS725へ進む。ステップS720では、逸脱端末の集合Rが空集合(φ)である旨を出力して、フローは終了する。ステップS725では、逸脱端末の集合Rを、全端末の集合L(GID1)より、端末数最大の集合Smaxを減じたもの(R＝L(GID1)−Smax)として出力して、フローは終了する。
【００６６】
以上のように、集合変化検知部14は、各k回目の時点において、同一グループIDを有する端末における集合検知結果を監視し、2つ以上の集合が検知されている場合に、端末数が最大の集合Smaxを検知したうえで、当該最大端末数を有する集合Smaxに属していない端末を、逸脱端末として検知する。
【００６７】
以上、第一実施形態を説明した。第一実施形態では、地域毎、学校毎の集団登下校のように、各端末において本来属するべき集団が予め決まっており、集団IDで当該区別が与えられることを想定していた。次に、当該想定を除外した、第二実施形態を説明する。第二実施形態はすなわち、ラーメン店やレストラン、トイレ等の店舗や公共施設・設備付近の集団(行列)等、集団を構成する端末が事前決定していない場合を対象とする。
【００６８】
従って、第二実施形態は基本的には、予め登録される集団IDが存在しない、という条件のもと、第一実施形態と同様に実施することができる。すなわち、登録されるのは端末IDのみであり、当該登録された全端末を対象として、第一実施形態と同様の処理が行われる。この際、集団検知部13では第二実施形態における追加的な処理が行われる。これにより、集団IDが付与されていない不特定の端末の中から、店舗Aおける集団であると想定されるもの、店舗Bにおける集団であると想定されるもの、等を自動的に区別して特定することが可能となる。また、集団変化検知部14は、第二実施形態では利用されない。
【００６９】
第二実施形態にて、集団検知部13は、距離推定部12(第一実施形態と同様)による各k番目の時点における各端末間の距離DIJ(k)集計結果から集団を検知する。この際、以下の（条件１）〜（条件４）を用いて、集団を検知することができる。
【００７０】
(条件1)集団に属する各端末TIは、同集団内の1台以上の他の端末TJと距離DTH以内に位置する
(条件2)集団を構成する端末数がNTH以上
(条件3)集団の変化率がCTH以下
(条件4)上記3条件を期間PTH以上継続して満たす
【００７１】
ここで、（条件１）は第一実施形態と同様である。当該（条件1）で得られた候補の集団Sjに対してさらに、以下のように（条件2）〜（条件4）を課して、最終的な結果を得る。
【００７２】
(条件2)によりさらに、所属端末数が所定の閾値Nth以上（|Sj|≧Nth）であるもののみが選別される。すなわち、集団を構成するために最低限必要な端末の台数を制限する。
【００７３】
(条件3)によりさらに、集団を構成する端末の変化を制限し、変化率が所定の閾値CTH以下であるもののみが選別される。例えば、スクランブル交差点の信号待ちの人々等、端末の参加や離脱が頻繁な集団と、ラーメン店の行列等、同一の端末で一定時間構成される集団とが考えられるが、(条件3)により後者の集団のみの検知が可能となる。
【００７４】
なお、(条件3)にて、2つの集合(集団)S1、S2の変化率C(S1,S2)は以下のように計算する。ここで|X|は、集合X(＝S1, S2, S1∩S2)に属する端末数である。変化率C(S1, S2)は集合S1、S2の構成要素が異なる程、共通部分の端末数|S1∩S2|が小さくなるため、大きい値となる。
C(S1, S2)= (|S1|+|S2|-|S1∩S2|*2)/(|S1|+|S2|)
【００７５】
さらに、(条件4)により、集団の継続時間を制限し、所定の閾値期間PTH以上に渡って継続しているもののみを選別する。以下、当該(条件1)〜(条件4)に基づく検知処理の詳細を説明する。
【００７６】
まず、図８のフローチャートにより、(条件1)及び(条件2)を満たす集合Sjへの分割を得る。図８のフローは、図６のフローに類似しており、特に、ステップ番号の下2桁が共通のステップ(図8のステップS805と図6のステップS605など)では、共通の処理がなされる。ただし、ステップS805では、第二実施形態に従い、グループIDを設定されず端末IDのみが設定された全端末についてのIDリストとして、リスト変数L'が用意される。
【００７７】
従って、図8のステップS805〜S830は、上記グループIDを利用しない点を除いて、図6のステップS605〜S630と共通であるので、重複した説明は省略する。図8のフローでは特に、(条件2)を課すべく、ステップS840,S845,S850が存在している。そして、ステップS830にて、リスト変数L'が空集合(φ)ではない旨の判定がなされた場合に、ステップS840へと移る。
【００７８】
ステップS840では、集合Sjの所属端末数が閾値Nth以上であるかの判定が行われ、閾値以上であれば、ステップS845へと進む。ステップS845では、カウンタ変数jを1だけ増分して、ステップS850へ進む。一方、ステップS840にて閾値以上ではなかった場合、ステップS850へ進む。
【００７９】
ステップS850では、集合Sjに空集合(φ)を設定して、ステップS810に戻る。従って、ステップS840で閾値以上の判定が下された場合は、当該集合Sjは候補として残り、次の集合Sj+1を対象として処理が継続され、閾値以上の判定が下されなかった場合は、当該集合Sjの結果を空集合(φ)の設定により破棄して、再度当該変数Sjを対象として処理が継続される。
【００８０】
以上、図８のフローによって、図９に示すような各k回目の時点における(条件1)及び(条件2)を満たす集団履歴が得られる。当該集団履歴はすなわち、k=1, 2, 3, ...と一連のkに関して、各端末がどの集団に属しているか、又は集団に属しているとみなせないか、を特定した履歴である。集合(集団)Si(k)(i＝1, 2, ..., Nk)が、k回目(経過時刻k*Tに相当)における履歴を構成している。当該集団の数Nkも、各k回ごとに定まり、一般に一定とは限らない。
【００８１】
次に、当該集合履歴の中から(条件3)及び(条件4)を満たす集合を検出する処理について、説明する。ここで、現在時刻(経過時刻)を時刻k*Tとし、過去k回の集合履歴を取得していると仮定する。図９にも示すように、時刻k*TにNk個の集合Sj(k)を得ているとする。当該処理は、以下に手順を掲げる通りである。
【００８２】
[手順1] 各Sj(k)において、時刻(k-1)*Tにおける集団Si(k-1)との変化率C(Sj(k), Si(k-1))を計算し、(条件3)を満たすSi(k-1)を抽出する。
[手順2] この際、(条件3)を満たすものがない場合、集団なしと判断し、処理を終了する。
[手順3] 一方、(条件3)を満たす集団Si(k-1)が1個以上存在する場合、各集団Si(k-1)において、条件3を満たす集団Si(k-2)を抽出する。
【００８３】
[手順4]上記[手順1]〜[手順3]と同様の処理を、抽出された一連の過去k−1, k−2, k−3, ...,k-mの集団に渡って連鎖的に繰り返し、以下の条件式を満たす集合の組が存在する場合、集団Si(k)が(条件3)及び(条件4)を満たすものと判定し、選別され検知された集団とする。
C(Si(k), Sj1(k-1)) ≦ CTH ,
C(Sj1(k-1), Sj2(k-2)) ≦ CTH, 
…,
C(Sjm-1(k-m+1), Sjm(k-m))<=CTH, 
m*T>PTH
【００８４】
すなわち、集団Si(k)は、継続期間の閾値PTHを超えるだけの所定回数m回の過去履歴を参照して、各時点での変化率が閾値CTH以下であるような経歴によって変化してきたものである、と判定できる場合に、(条件3)及び(条件4)を満たし、検知される集団となる。ここで特に注目すべき点として、図９の集団履歴では、時点kが異なる集団同士の対応付けは与えられていないが、上記のように共通端末数に基づいて定まる変化率によって、擬似的に時点kが異なる集団間の対応付け(一意とは限らない)が与えられていることが挙げられる。
【００８５】
（行列検知）
第二実施形態ではさらに、集団検知部13の追加的な検知処理として、検知された集団が、行列を形成しているかを検知することができる。この際、上記(条件1)〜(条件4)に加えてさらに、以下の(条件5)をも満たしている集団を、行列を形成しているものとして判定する。(条件1)〜(条件4)は満たすが、(条件5)を満たさない集団は、集団ではあるが、行列ではないと判定される。
【００８６】
(条件5) (NL-1)/NP<LTHを満たす。
ここで、NPは行列形成の判定対象となっている集団Sの最小全域木における点の個数、NLは葉の個数である。また、LTHは最小全域木の点の個数に対する葉の個数の割合の所定の閾値である。
【００８７】
(条件5)が満たされているかを判定する具体的な手順の一例を説明する。先ず、検知した集団をグラフとして表現したうえで、当該グラフの全域最小木を求める。集団をグラフとする際には、所属する各端末をノードとし、端末間の距離(距離推定部12で求めた距離)を、対応するノード間のエッジのコストの値とすればよい。また、図８のステップS815で用いた閾値DTHを超えるノード間にはエッジが存在しないものとすればよい。
【００８８】
当該グラフに対する全域最小木は、プリム法等の一般的な方法により求めることができる。続いて、次数が1の端末を全域最小木の根とする。ここで、次数が1の端末は複数存在するが、選び方は(条件5)の判定に影響を与えない。全域最小木の点NPと葉NLの個数をそれぞれ求め、(条件5)により判定する。
【００８９】
図10に行列検知の例(1)及び(2)を示す。(1)は行列と判定される集団の例であり、(2)は行列とは判定されない集団の例である。集団が行列である場合、(NL-1)/NPの値が小さくなり、理想的な行列の場合は0となる。一方、集団が行列ではない場合、(NL-1)/NPの値は大きくなる。
【符号の説明】
【００９０】
100…集団検知システム、10…集団検知装置、20,30…端末、11…登録端末管理部、12…距離推定部、13…集団検知部、14…集団変化検知部、15,25,35…通信部、21,31…端末情報管理部、22,32…音波送信部、23,33…音波受信部
【図１】
2014190824.tif 000003
【図２】
2014190824.tif 000004
【図３】
2014190824.tif 000005
【図４】
2014190824.tif 000006
【図５】
2014190824.tif 000007
【図６】
2014190824.tif 000008
【図７】
2014190824.tif 000009
【図８】
2014190824.tif 000010
【図９】
2014190824.tif 000011
【図１０】
2014190824.tif 000012