論文
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――

ムービングオブジェクトの速度変化パターンを識別できる類似検索機能の導入
Introduction of a Similarity Search
Function of Moving Objects
Objects to Capture
their SpeedSpeed-Change Patterns

河内 聡惠♥

増永 良文♠

Satoe KAWACHI

Yoshifumi MASUNAGA

我々は，3
我々は，3 次元空間内の物体の動きに関するデータを格納し，様々な問合せを実現するムービングオブジェクトデータベースシステムの構築を進めている．既に，動きに関する問ベースシステムの構築を進めている．既に，動きに関する問合せ手段として有効な類似検索機能の実現に向けて，ムービングオブジェクトデータに対する類似性が体系的に定義している．これにより，同じ軌跡を描く動きであっても，その時間的な変化まで類似した動きを検索することができるようになった．しかしながら，人が類似していると判断する一つの大きな要因として考えられる速度変化のパターンを認識することはできなかった．そこで本稿では加速度を考慮することにより類似性の定義を拡張して速度変化のパターンを認識することができるような類似検索機能が提供できることを明らかにする．
ことを明らかにする．
Our aim is to construct a moving object databasesystem that enables us to store data about moving
objects in the threethree-dimensional real world and allows us
to issue queries for various types of object moves.
Several identity and similarity defi
definitions
nitions of object
moves have been proposed, and by using one of them it
became possible to distinguish two object moves thatdraw the same trajectory but move differently in time.
However, it became also clear that the current
definitions
definitions cannot recognize the differences among
speedspeed-change patternpatterns that seem to be a very importantfactor for human to judge the object move similarity. In
this paper, we propose a new similarity measure that
captures the difference of speedspeed-change patternpatterns bytaking into acc
account
ount the acceleration measure of moving
movingobjects.
objects .

1. はじめに
近年，人間の動きなどを計測するためのモーションキャプ
チャリングシステムや，カーナビゲーションシステムなどで用いられるGPS(Global Positioning System)のように，動く物体の位置を計測するためのセンシング技術が発達してきている．そこで，このような計測データをデータベースに蓄♥学生会員 お茶の水女子大学大学院人間文化研究科博士前期課程 satoe@dblab.is.ocha.ac.jp♠正会員 お茶の水女子大学理学部情報科学科
masunaga@is.ocha.ac.jp

1

え，動きに関する様々な問合せやシミュレーション分析を行いたいという要求が高まってきた．このような要求に応えるためには，空間データと時間データの双方を統合的にデータベース上で扱えるようにするための時空間データモデルが必要となる．
これまでに，我々は動きに関する基本的要素としてオブジェクトの位置情報だけではなく，向き・傾き・形状情報を考慮に入れたムービングオブジェクトデータモデルを提案してきた．そこではドメインリレーショナル論理に基づいた問合せ言語であるMOQL(Moving Object Query Language)を提案し，これによって動きに関する様々な問合せが記述可能となった[1]．さらに，我々がオブジェクトの動きを表現しようとする際，「回転する」「揺れる」のように定義が明確でない言葉を用いることが多い．また，思い描いた動きを言語によって表現するのが困難な場合も往々にしてある．こうした問題に対処するために，動きに関する問合せ手段には言語に依らない検索機能が有効なのではないかと考え，検索したい動きを実際にモーションキャプチャリングシステムを利用して計測し，それをサンプルとして与えることで類似したデータを検索をすることのできる類似検索機能をデータベースシステムに導入することとし，ムービングオブジェクト
データに対する類似性を動きの同一性，基本類似性，部分列類似性，幾何変換類似性，時間変換類似性，時空間変換類似性の6つに分類し定義した．これにより，同じ軌跡を描く動きであっても，その時間的な変化まで類似した動きを検索することができるようになった[2]．
しかし，人が類似していると判断する要因は様々である．
上記の類似性に基づいて類似検索を行った結果，人が類似していると判断する一つの大きな要因として考えられる速度の変化パターンを認識することはできなかった．そこで本論
文では，速度の変化量を表す加速度を考慮することにより類似性の定義を拡張して，速度変化のパターンを認識することが出来る類似検索機能を提案しそれを検証する．

2. 動きの基本類似性
2.1 動きとは
オブジェクトの動きは，オブジェクトの中心座標・速度・加速度，及びそれに付与された時刻印の4要素で構成される．
正式には，周波数 f で時刻 ts から te まで計測されたオブジェ
rrr
クトの動きを M = (m0 ,..., mn ) で表す．ここに，
rr r r r
mi = ( pi , vi , ai , ti ) で，要素はそれぞれオブジェクトの位置ベク
rr r rrr r r
トル pi = ( xi , yi , zi ) ，速度ベクトル vi = ( xi , yi , zi ) ，加速度ベク
rr r rトル ai = ( xi , yi , zi ) を表す．また， ts = t0 ，te = tn ( n = (te − ts ) × f ) である．

2.2 動きの同一性
動きの類似性を求める前に，まずはその基本として動きの同一性の定義を行う．
定義2.1
定義2.1：
2.1 ：(動きの同一性)
r r
動き M , M ' が次の条件を満たすとき，2つの動きは同一である．
1. f = f '2. ts = ts '∧te = te 'rr
3. (∀i) pi = pi '2.3 動きの要素の基本類似性
動きのデータには，位置・速度・加速度という3つの基本

日本データベース学会 Letters Vol.2, No.1

論文
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――
要素がある．そこで，まずはそれぞれの要素についての類似性を定義した．相違度の距離関数には，一般的によく知られているユークリッド距離を用いる．
定義2.2
定義2.2：
2.2 ：(位置の基本類似性)
rr
動き M が M ' に対して以下の条件を満たすとき，位置についてε‑類似している．
1. f = f '2. ts = ts '∧te = te 'nr r
d p (mi , mi ' )r r
i=0
3. D posi ( M , M ' ) =≤εnr rr r
但し d p (mi , mi ' ) =| pi − pi '|2パターンを捉えるという観点からは望ましい結果を与えている．しかしながら，本章で与えた基本類似性の定義ではムービングオブジェクトの速度変化パターンの違いを的確に意識することはできないことが判明した．
そこで，次章で速度変化のパターンを捉えることのできる類似性の尺度の導入を検討する．

定義2.3
定義2.3：
2.3 ：(速度の基本類似性)
rr
動き M が M ' に対して以下の条件を満たすとき，速度についてε‑類似している．
1. f = f '2. ts = ts '∧te = te 'nr r
d v (mi , mi ' )r ri =0≤ε
3. Dvelo ( M , M ' ) =nr rr r
但し d v (mi , mi ' ) =| vi − vi '|2αを超えた時区間で最大値をとる時刻 ti (但し 0 ≤ i ≤ k )で動rr
きを k + 1 個に分割する(図 1)．分割された動きを M 0 ,..., M k と∑

∑

定義2.4
定義2.4：
2.4 ：(加速度の基本類似性)
rr
動き M が M ' に対して以下の条件を満たすとき，加速度についてε‑類似している．
1. f = f '2. ts = ts '∧te = te 'nr r
d a (mi , mi ' )r ri =0≤ε
3. Dacce ( M , M ' ) =nr rr r
但し d a (mi , mi ' ) =| ai − ai '|2∑2.4 類似検索の実験と検証(類似検索の実験と検証(実験1)
実験1)
この実験１では模型列車の動きを計測し，基本類似性について検証を行った．具体的には，直径70cmの環状の線路上を列車が次に示すA〜Cの3つの走行パターンで10秒間で一周する様子を計測してデータベースへ格納した．
Type A: 等速で進む列車の動き(等速パターン)
Type B: 前半に比べて後半が遅く動く列車の動き(速−遅パターン)
Type C: Type B のパターンを2度繰り返す列車の動き(速−遅−速−遅パターン)
データベースに対して，いずれかのTypeに属する動きを一つサンプルとして指定して基本類似性に基づいて検索を行った．その結果，サンプルが属するTypeのデータが必ず上位に検索され，それ以外のものと区別することができた．また，検索結果は各タイプがグループとしてまとまってランキングされた．例えばサンプルがType A の時は，位置と速度に関しては， A，C，B の順で，加速度に関してはA，B，C の順でグルーピングされた．しかしながら，位置と速度に関してA，C，B の順であったことは，計測されたデータを分析したところ，実験データにばらつきがなかったため偶然成立したものであることが判明した．(つまりこの並び順には意味がない.)これに対し，加速度は速度の変化量であり，速度が変わる際に著しく変化するため，加速度の相違度に基づく類似検索結果は，速度が変化する回数の少ないType B がType
C より常に上位にランキングされると考えられ，速度変化の23. 速度変化を捉えれる類似性
3.1 加速度の変化回数による動きの分割
2.4 節で行った実験１より，加速度は速度が変化するたびに著しく変化するため，速度変化回数を捉えることができる
rr
ことが分かった．そこで，動き M において | ai | がある閾値する．
定義 3.1：
3.1：(分割された動きの基本類似性)
r rrrrr
動き M , M ' が各々 M 0 ,..., M p ，M 0 ,..., M q に分割されたとき，r r
r rr rD posi ( M , M ' ) = D posi ( M 0 , M 0 ' ) + ... + D posi ( M i , M i ' )r r+ ... + D posi ( M q , M q ' )r rr rr r
Dvelo ( M , M ' ) = Dvelo ( M 0 , M 0 ' ) + ... + Dvelo ( M i , M i ' )r r+ ... + Dvelo ( M q , M q ' )r rr rとする．但し p ≤ q ， D posi ( M i , M i ' ), Dvelo ( M i , M i ' ) はそれぞれ位置の相違度，速度の相違度を表す．
r rr rD posi ( M i , M i ' ), Dvelo ( M i , M i ' ) は，一般に計測開始時刻，終了時刻が等しくないため，2.3 節で定義された基本類似性でr rr rは計算できない．そこで， D posi ( M i , M i ' ), Dvelo ( M i , M i ' ) を以下のように定義しなおす．ここで，Li (t ), Li ' (t ) は横軸に時刻 t ，縦軸に移動距離 L をとった L − t グラフの表す式， vi (t ), vi ' (t )は横軸に時刻 t ，縦軸に速度 v をとった v − t グラフの表す式，r r
積分範囲は M , M ' それぞれの開始時刻 ts (ts ' ) から終了時刻
te (te ' ) までとする．
定義 3.2：
3.2 ：(分割された動きにおける位置の類似性)
rr
動き M が M ' に対して以下の条件を満たすとき，位置についてε‑類似している．
tete 'r r
D posi ( M i , M i ' ) =Li (t )dt −Li ' (t )dt ≤ ε

∫ts

∫

ts '

定義 3.3：3.3 ：(分割された動きにおける速度の類似性)
rr
動き M が M ' に対して以下の条件を満たすとき，速度についてε‑類似している．
tete 'r r
Dvelo ( M i , M i ' ) =vi (t )dt −vi ' (t )dt ≤ ε∫ts∫ts 'r
ここで， p ≤ q であるから，動き M p +1 以降は存在しない．そこで，次に示すコスト関数を定義する．
定義 3.4：3.4 ：(分割数が異なる場合の類似性)
p < i ≤ q に対して，r rr r
D posi ( M i , M i ' ) = Dvelo ( M i , M i ' ) = ∞
したがって，定義 3.4 より速度の変化回数が異なる 2 つの動きは類似していないと判定することができる．

日本データベース学会 Letters Vol.2, No.1

論文
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――
3.2 位置の相違度と速度の相違度の対応関係
前節で，加速度によって動きを分割し，位置と速度の相違度によって類似性を定義した．ここで，もし位置の相違度と速度の相違度が対応していれば，どちらかの要素のみの相違度で動きの類似性を表すことができる．つまり，次の命題を考える．今後，加速度によって分割された各動きは，ほぼ速度一定であると仮定する．この仮定は，実験１により裏付けられている．このとき，次の命題が成り立つ．
命題 3.1：
3.1 ：(位置の相違度と速度の相違度の対応)
rrr
サンプルとなる動き M s ，比較される動き M d 1, M d 2 を与えた
とき，次の関係が成り立つ．
r r
r r
D posi ( M s , M d 1 ) ≤ D posi ( M s , M d 2 )r rr r
iff Dvelo ( M s , M d1 ) ≤ Dvelo ( M s , M d 2 )r
ここで，この命題を証明する．サンプルとなる動き M s とr比較される動き M d の移動距離を L とする．ここで，2 つの場合を考える．
r r(1)
M s , M d 共に時刻 τ c で 1 回速度変化をする場合
r r(2)
M s , M d がそれぞれ時刻 τ cs ,τ cd で 1 回速度変化をする場合

3.2.1 (1)の場合(1)の場合

r
M s が速度 vs1 で時刻 τ s (= 0) から τ c まで距離 Ls1 移動し，速度 vs 2 で時刻 τ c から τ e まで距離 Ls 2 移動したとする．同様
rに、 M d が速度 vd 1 で時刻 τ s (= 0) から τ c まで距離 Ld1 移動し，
速度 vd 2 で時刻 τ c から τ e まで距離 Ld 2 移動したとする．但し，

図2

Fig.2 Relations between Velocity and Dissimilarity

3.2.2 (2)の場合(2)の場合r
M s が速度 vs1 で時刻 τ s (= 0) から τ sc まで距離 Ls1 移動し，速度 vs 2 で時刻 τ sc から τ e まで距離 Ls 2 移動したとする．同様
rに、M d が速度 vd 1 で時刻 τ s (= 0) から τ dc まで距離 Ld1 移動し，速度 vd 2 で時刻 τ dc から τ e まで距離 Ld 2 移動したとする．但し， Ls1 + Ls 2 = Ld1 + Ld 2 = L とする(図3)． Ls1 = vs1 × τ sc ，
Ls 2 = vs 2 × (τ e − τ sc ) ，Ld1 = vd1 × τ dc ，Ld 2 = vd 2 × (τ e − τ dc ) であるから，
r r
1
D posi ( M s , M d ) = (τ sc × Ls1 − τ dc × Ld1 )2+るから，r r
1
1
D posi ( M s , M d ) = τ e × ( Ls1 − Ld 1 ) = τ e × τ c × (vs1 − vd1 )22r r
Dvelo ( M s , M d ) = τ c × (vs1 − vd1 ) + (τ e − τ c ) × (vs 2 − vd 2 )r rとなる． x 軸に速度， y 軸にそれぞれ D posi ( M s , M d ) ，r r
Dvelo ( M s , M d ) をとると，両者とも速度 vs1 のときに0となるv

1((τ e − τ sc ) × ( Ls1 + L) + (τ e − τ dc ) × ( Ld1 + L ))2r r
Dvelo ( M s , M d ) = τ sc × vs1 − τ dc × vd1 )+ (τ e − τ sc ) × vs 2 − (τ e − τ dc ) × vd 1

Ls1 + Ls 2 = Ld1 + Ld 2 = L とする(図1)． Ls1 = vs1 × τ c ，Ls 2 = vs 2 × (τ e − τ c ) ， Ld1 = vd1 × τ c ， Ld 2 = vd 2 × (τ e − τ c ) であ

速度と相異度の関係
速度と相異度の関係となる． x 軸に時刻， y 軸に速度， z 軸にそれぞれr rr r
D posi ( M s , M d ), Dvelo ( M s , M d ) をとると，両者とも時刻 τ sc ，
速度 vs1 のときに0となる z = c − xy ( c は定数)型のグラフを描く(図4)．したがって，命題3.1が成り立つ．

字型( vs1 まで単調減少，その後単調増加)のグラフを描く(図2)．したがって，命題が成り立つ．

図1(1)の場合(1) の場合

Fig.1

Case(1)

図4
Fig.4

3

図3(2)の場合(2) の場合

Fig.3

Case(2)

時刻，速度，相異度の関係
時刻，速度，相異度の関係

Relations among Time, Velocity andDissimilarity

日本データベース学会 Letters Vol.2, No.1

論文
DBSJ Letters Vol.2, No.1――――――――――――――――――――――――――――――――――――
命題3.1より，位置の相違度か速度の相違度どちらかの要素のみで動きの類似性を表すことができる．ここでは，位置の相違度を用いることにする．
定義3.5
定義3.5：
3.5 ：(速度変化パターンを捉える動きの基本類似性)
rr
動き M が M ' に対して以下の条件を満たすとき，動きについてε‑類似している．
r r
r r
Dmove ( M i , M i ' ) = D posi ( M i , M i ' ) ≤ ε

3.3 類似検索の実行と検証(類似検索の実行と検証(実験 2 と実験 3)
本節では，前節で定義した動きの基本類似性に基づいて行った実験 2 の結果を検証する．

3.3.1 実験 2
まず，2.4節で用いた3つのTypeのデータを用いて，新たに定義した定義3.5の類似性に基づいて検索を行った．いずれのTypeをサンプルとして与えた場合でも，他のTypeとは速度変化回数が異なるため，定義3.4により他のTypeの動きはランキング外になり,速度変化パターンが同一のムービングオブジェクト同士のみが類似していると判定された．
しからば，同一の速度変化パターンを有するムービングオブジェクト同士の間でどのような動きの類似性を識別できるのかさらに実験3を行った．

3.3.2 実験 3
次に，Type B に属するデータのみを対象に実験を行った．
2.4節の実験と同様，直径70cmの環状の線路上を列車がB1〜B3の3つの走行パターンで10秒間で一周する様子を計測，データベースへ格納した．
Subtype B1: 計測開始から1秒後に高速から低速に変化する列車の動き．
Subtype B2: 計測開始から2.5秒後に高速から低速に変化する列車の動き．
Subtype B3: 計測開始から5秒後に高速から低速に変化する
列車の動き．
データベースに対して，いずれかのSubtypeに属する動きを一つ取り上げ，それをサンプルとして指定して基本類似性に基づいて検索を行った．
検索の結果，サンプルに属するSubtypeのデータが必ず上位に検索され，それ以外のものと区別することができた．また，Subtype B1をサンプルとして与えた場合は，位置の相違度，速度の相違度どちらを用いてもランキングはB1，B2，B3 の順になり，人が類似していると判断する要因の一つである速度変化パターンを認識することができていることが確認できた．

4. まとめと今後の課題
本論文では，動きに対する問合せ手段として，実際にモーションキャプチャリングシステムを利用して検索したい動きを計測し，それをサンプルと指定することで類似した動きのデータを検索する類似検索機能を論じた．｢動きが類似している｣と一口に言っても，その意味するところは多様であり，速度変化のパターンが似ているというのも｢動きが類似している｣と判断する一つの要因である．しかしながら，これまでに定義された動きの類似性は，各計測時刻における位置の相違度が基準になっていたが，それでは速度変化のパターンを認識することはできなかった．そこで，速度変化のパターンを判断することができる類似検索機能を提供するために，新たな動きの類似性を定義・導入した．
まず，速度や速度の変化量である加速度を動きの要素に追4加し，各要素の類似性を新たに定義した．実際に，模型列車の動きを計測してデータを格納し，検索を行った結果を検証したところ，位置と速度の類似性は偶然性を排除できない結果になるが，加速度は速度の変化回数を捉えることができることがわかった．そこで，加速度の著しく変化する時刻で動きを分割し，位置と速度の相違度によって類似性を判断する
新たな動きの類似性を定義した．このとき，位置の相違度と速度の相違度には対応関係があり，どちらか一方の相違度のみを用いて動きの類似性を表すことができることを示した．
実際に検索を行ったところ，速度の変化回数の異なる動きは全く別の動きとして判断された．また，同じ速度の変化回数でも，速度の変化する時刻が異なる動きの方が違う動きとして判断された．つまり，速度変化のパターンを認識することができた．
今後の課題としては，大きく 2 つの項目が挙げられる．1点目は，動きの類似性の拡張である．類似性とは，アプリケーションによって様々に定義されるものである．ある動きに対して，その鏡像にあたる動きも似ていると判断する基準の一つと考えられる．また，オブジェクト間の関係についての類似性も考えられる．例えば，｢オブジェクト間の距離関係がおよそ似ているシーンを検索する｣といった問合せである．
これらを考慮に入れて，新たな類似性を定義していく必要がある．2 点目は，索引付けである．時系列データは一般にそのデータサイズが大きくなり，これに対して圧縮及び索引付けを行う研究は既に多くなされている．しかし，データの圧縮とその圧縮したデータを利用した検索では，検索の精度が劣化することがあるため，ムービングオブジェクトデータに対する類似検索としてある一定の精度を保ったまま効率的に検索する方法を検討していく必要がある．

[文献]
文献]
[1] Y. Masunaga, N. Ukai: “Toward a 3D Moving Object
Data Model - A Preliminary Consideration -”, inProceedings of the 1999 International Symposium on
DatabaseApplications
in
Non-TraditionalEnvironments, Kyoto, pp.306-316 (1999).
[2] 水崎 聡子，増永 良文: “ムービングオブジェクトデータベースシステムのための類似検索機能の実現に向けて, ”
情報処理学会第 125 回データベースシステム研究会報告,Vol.2001, No.70, pp. 217-223, (2001).

河内 聡惠

Satoe KAWACHI

2003 お茶の水女子大学大学院人間文化研究科博士前期課程修了(2003 年 4 月(株)野村総合研究所入社)．2001 お茶の水
女子大学理学部情報科学科卒業．ムービングオブジェクトデータベースシステムの研究・開発に従事．日本データベース学会学生会員．

増永 良文

Yoshifumi MASUNAGA

お茶の水女子大学理学部情報科学科教授．1970 東北大学大学院工学研究科博士課程修了，工学博士．データベースシス
テムの研究・開発に従事．情報処理学会データベースシステ
ム研究会主査，ACM SIGMOD 日本支部長，情報処理学会監事などを歴任．情報処理学会フェロー．電子情報通信学会フェロー．日本データベース学会副会長．著書に「リレーショナルデータベース入門 [新訂版]」(サイエンス社)，監訳書に｢オブジェクト指向データベース入門｣（Won Kim 著，共立出版）など．

日本データベース学会 Letters Vol.2, No.1