The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

1B3-04

多数移動物体の分布変化パターンの統計分析-金魚すくいロボットへの捕獲対象絞込み技能の伝達へ向けてStatistical Analysis of Distribution Patterns for Moving Objects- Skill Acquisition to Focus a Target Region for a Catch-Robot 浮ヶ谷 敦生

河村 竜幸

木戸出 正継Atsuo UKIGAYA

Tatsuyuki KAWAMURA

Masatsugu KIDODE

奈良先端科学技術大学院大学 情報科学研究科
Graduate of Information Science, Nara Institute of Science and Technology

This paper proposes a model to learn distribution patterns of moving objects, by which an intelligent robot isable to catch or scoop given objects among lots of moving ones. Human experts for this kind of catching behavior
show their skill on the basis of moving patterns which dynamically changes. From technical points of view intheir dynamic moving behaviors, we have analyzed their visual moving patterns and built a model of distributions
patterns as a probabilistic state transition mechanism.

1.

はじめにい．すくい易い状態とそうでない状態を明確に区別できる精度で金魚の分布変化パターンを分析し，統計的手法によってモデル化する事により，間接的にこの条件を求める．
生成するモデル
まず，すくい易い金魚を区別できるだけの精度を持った金魚の分布変化パターンのモデルを生成する．次にエキスパートをインタビューして，すくい易い金魚を金魚の動画中で示してもらう．そして示された金魚と分布変化パターンのモデルを対照することで，すくい易い状態に共通する条件を求める．これによりすくい易い状態を見分けることと，その状態に至る予測が可能になる．
エキスパートがすくい易い金魚を絞り込む技能は，次の様なものである．
• 金魚動作を予測できる• すくい易い状態を区別できる
以上のことから，生成するモデルを次の条件を満たす様な確率的状態遷移グラフによって表現する．確率的遷移グラフは状態遷移が確率的に発生する状態遷移グラフである．

現在ロボットなどの機械に，人の持つ様々な技能を伝達したいという要求がある．機械加工技術については，腕の動きを測定しロボットアームの制御に適用する手法が試みられている [1][2]．これは，例えば機械組み立ての様に常に決まった動作を繰り返す技能には有効である．
しかし，金魚すくいですくい易い金魚を絞込む様に，動的に変化する現象に対する 視覚的な情報の取捨選択能力 という技能においては，視線追跡装置などで視線そのものを伝達しても技能を伝達したことにはならない．このような場合の技能伝達とは，対象のどこに注目すれば効果的に対象を分析できるのかという条件を伝達することである．この様なすくい易い金魚を絞り込むためには，対象の変化 (金魚の動き) をモデル化し，技能者 (金魚すくいのエキスパート) が注目している場所の共通点を求めれば，技能が伝達できると考えられる．その為にはまず対象 (背景) の変化パターンをある程度モデル化しておく必要がある．本研究では，動的に変化する対象の視覚的情報を確率的状態遷移モデルでモデル化する．

2.

金魚すくい技能の伝達• 各状態からの状態遷移が 1 本 (100% ) に近い• すくい易い状態とすくい難い状態が区別できる

本研究では，詳細な分析の前に情報そのものの取捨選択が必要な対象として，金魚すくいの金魚に着目した．金魚すくいの技能には多数の金魚からすくい易いものを絞り込む技能が含まれている．この絞込み技能をモデル化することで，金魚すくいのエキスパートの対象絞込み技能を機械へ伝達する．そのためには，金魚の分布変化パターンを定量的に分析できる必要がある．本研究では，まず金魚の分布変化パターンをモデル化する．

2.1

一つ目の条件のみを満たしたモデルは，金魚の動きを予測するだけなら充分な精度を持ったモデルであり，便宜上これを 基礎変化モデルと呼ぶ．また二つ目の条件までも満たしたモデルは，すくい易い金魚の分布を見分けるために充分な精度を持ったモデルであるため，これを 絞込み変化モデル と呼ぶ．
状態
この確率的状態遷移モデルにおける状態とは，画像から得た各種情報をパラメータとする，状態空間の一部である．例を用いて説明する(図 2)．画像から二種類の情報を抽出していたとすると，二次元の状態空間が張られる．この時，状態は二つの領域の和集合として定義されており，二つのパラメータそれぞれについての最小値最大値 (a，b,c, d, e, f, g, h) を用いて，図のように表現される．この領域に含まれる部分的な状態空間そのものがこのモデルの状態である．

金魚すくいの技能人にとっても機械にとっても，金魚をすくう為に 500 匹以上の金魚を全て追いかける事は困難であり，また実際に人は全ての金魚を同時に見ているわけではない．金魚を詳細に追跡する前に，まず追跡する対象を大まかに絞り込むという行為が必要である．(図 1) 従って金魚すくいの技能は次の三つになる．
• すくい易い金魚がいる領域を選択する技能• すくい上げる金魚数匹の動きを詳細に追跡・分析する技能• ポイを破らずに金魚をすくい上げる技能
この内一つ目の技能は，前述の動的に変化する対象の分析が必要な技
能である．

2.2

3.

基礎変化モデルの具体化

基礎変化モデルを生成する手法を以下に解説する．分析前に行う処理，抽出する情報，得られた時系列データからモデルを生成する手法の順に述べる．

対象絞込みの技能とモデル化

3.1

多量の金魚の中からすくい易いものを視覚的に絞り込む技能を伝達するということは，すくい易い状態の金魚と他の状態の金魚を区別する条件を伝達するという事である．しかし金魚すくいのエキスパート
は両者を区別する条件を明確なルールとして自覚しているとは限らな

前処理

情報源はフレームサイズが VGA，15[fps]，24bit color の無圧縮
AVI ファイルである．
• 金魚が泳ぐ様子を観察した結果，物音などに反応した場合でも泳ぐ速度は 15[cm/s] 程度• 金魚一匹の画素面積は 10〜15[pixel] 程度
この動画に対して，フレーム単位に金魚とそれ以外を分離し二値化しておく．

連絡先: 浮ヶ谷 敦生，奈良先端科学技術大学院大学 情報科学研究科，〒 630-0192 奈良県生駒市高山町 8916-5，atsuou@is.naist.jp

1

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

3.2

モデルの初期化

基礎変化モデルの初期化の流れを図 3 にフローチャートで示す．最初に全フレームを 2 値化，状態のパラメータとなる時系列情報を抽出する．その時系列情報を時間に沿って見て行き，パラメータ値がある条件に当てはまるところで状態を生成する．順に状態が生成されるので，時間的に隣り合った状態間で遷移関係を結ぶ．もし同一の状態が既に生成されていたら状態を併合する．
以下，主な処理について詳細を述べる．
(1) 抽出する情報 まず前処理が済んだ二値画像に対し画像処理を行い，

図 2: 状態の例• 白画素数• 白画素領域の重心座標 (二次元)• …
といった情報を得る．フレーム画像は水槽の水面部分を縦 5 分割，横 8 分割した小領域を単位として扱う．こうすることで基礎変化モデルが完成した後，金魚すくいのエキスパートが示すすくい易い金魚の位置 と基礎変化モデル中の状態との対応付けが容易になる．こうして得られた情報がモデルの状態空間を形作るパラメータとなる．
(2) 状態遷移の判定
動画より抽出した時系列データの時刻 t と t-1 を見て，時刻 tと t-1 で状態が変化しているかどうかを判定する．時系列デー
タの種類ごとに，最低値から最高値までの間を数段階に分割する．時刻 t と t-1 を比較して，パラメータの一つでも値が異なる段階に属した時，状態が遷移したと判定する．例えばあるパラメータが全データ中で最低:0〜最大:100 という値で変化し，4段階に分割していたとする (図 4)．そして時刻 t-1 の時の値が20，時刻 t の時の値が 40 を得たとすると，0 ≦ 20 ＜ 25，25≦ 40 ＜ 50 だから，時刻 t で状態が遷移しているとみなす．
(3) 状態生成

図 3: モデルの初期生成
大 1 回) →遷移関係の再構築」を繰り返すことになる．便宜上これを最適化ループと呼ぶ．

(1) オペレーション評価値
オペレーション評価値は各状態が持ち，その状態が結合/分割オペレーションの対象になるべき度合いを示す．値が大きいほど優先的に最適化される．オペレーション評価値は各状態の遷移先数と確率の分散によって式 (1) で計算される．

状態生成時の初期パラメータは，その時点の全種類の時系列データの値によって決定する．具体的にはパラメータ毎に最小値から最大値の値を数段階に分け，状態生成時のパラメータ値を含む段階の上界下界を状態の範囲とする．そうして時系列に沿って状態を生成して行き，生成した順に遷移関係を持たせる．全く同一の状態については併合する．

3.3

E=NV(1)∵ E : オペレーション評価値, N : 遷移先数, V : 遷移確率の分散モデルの最適化(2) 対象選択基準評価値

予測に利用できる基礎変化モデルとするために，前節の初期化されたモデルの各状態の状態遷移確率を 100% へ近づける (図 5)．具体的な最適化の操作は，二つの状態を一つに結合する結合オペレーションや，一つの状態を二つに分割する分割オペレーションをグラフ中の状態に対して繰り返し行うというものである．これにより状態の定義に変更を加え，遷移確率を 100% に近づける．各オペレーションの対象は後述の対象状態選択アルゴリズムで選択される．その対象状態選択アルゴリズムは，各状態の遷移状況を評価するオペレーション評価値と被遷移状態のオペレーション評価値の合計である対象選択基準評価値を利用している．
結合オペレーションで結合された状態の遷移関係は結合前の 2 状態の遷移関係から求まるが，分割オペレーションで分割された状態の遷移関係は時系列データを参照しなおさなければ分からない．従って最適化処理は「結合オペレーション (複数回) →分割オペレーション (最対象選択基準評価値は式 (2) により求まり，これも各状態が持つ．

XS=En

(2)

∵ S:対象選択基準評価値
En :被遷移状態のオペレーション評価値(3) オペレーション対象状態の選択
結合/分割オペレーションは，グラフに含まれる全ての状態について適用できる．少ない計算量で効率的に最適化を進めるため，オペレーション評価値，対象選択基準評価値を用いて，オペレーション対象状態を選択する．オペレーション対象状態選択アルゴリズムは図 6・図 7 の様になる．
オペレーション対象状態の選択方針
結合オペレーションによって遷移先数を減らし遷移確率の分散を高められる可能性があるのは，遷移先が等しい状態間で結合する場合だけである．分割オペレーションは最適化ループ毎に 1回までしかできないので，まず分割オペレーション対象状態を選択し，そこへ遷移している状態の中から結合対象を選択する．
結合/分割対象状態の選択方針は，(a) 結合/分割オペレーションの効果が大きそうなものから分割対象状態を選択し(b) その状態へ遷移している状態で，結合した方が良い状態はすべて結合し(c) 分割対象状態の分割を試みる
但しオペレーション評価値が高くても，結合/分割オペレーションによってオペレーション評価値が大きく減少するとは限らない．従ってオペレーション評価値が最も高い状態を常に選択すると，あまり効果的でないオペレーションを繰り返してしまう

図 1: 金魚の様子

2

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

図 4: 状態遷移の判定
図 6: 結合対象状態選択アルゴリズム

図 5: 最適化の流れ

図 7: 分割対象状態選択アルゴリズム

可能性がある．そこで対象選択基準評価値を重みとしたルーレッ
トアルゴリズムにより，高確率で対象選択基準評価値の高い状態を分割対象に選択しつつ，弱いランダム性も併せ持つ様にした．
結合対象選択アルゴリズム
分割対象状態へ遷移している状態から二つを選択する全ての組み合わせから，結合してオペレーション評価値が減少するものを全て選択する．

図 8: 結合オペレーションの例

分割対象選択アルゴリズム
分割対象状態は結合対象状態を選択するための基準となる状態でもある．結合対象は分割対象状態に遷移している状態の中から選ばれる．従って分割対象状態は，よりオペレーション評価値が高いより多くの状態から遷移されている状態を選択する．被遷移状態数や被遷移状態のオペレーション評価値は状態選択基準評価値に表れるので，状態選択基準評価値が大きい状態から選択する．具体的には状態選択基準評価値を重みとした一般的なルーレットアルゴリズムで選択する．
(4) 結合オペレーション∵ Et :時刻 t における状態毎のオペレーション評価値，Nt :時刻 t における状態数，
Et−n :時刻 t-n における状態毎のオペレーション評価値，Nt−n :時刻 t-n における状態数，
T h:最適化終了の閾値

4.

金魚が泳ぐ様子を天井カメラで捉えた動画から，基礎変化モデルを生成した．

二つの状態を一つにまとめる操作である．対象の二状態に対し，状態空間の範囲を示すパラメータ範囲と被遷移先，遷移先を OR結合する．被遷移先からの遷移確率，遷移先への遷移確率を再計算する．(図 8)(5) 分割オペレーション

4.1

状態遷移確率の分散と状態毎の遷移先数は，各状態からの遷移先の曖昧さを量る指標になる．モデルの状態において，状態遷移確率の分散が大きく遷移先が少ないほど，遷移先の曖昧さが減少する．グラフに存在する状態がそうした変化をしていれば本最適化手法の有効性が示される．
• 全状態のオペレーション評価値の平均状態遷移確率や状態毎の遷移先数を計数し最適化の有効性を検討するとともに，オペレーション評価値の変化を調査し，オペレーション評価値の最適化に対する有効性を検討する．最適化が有効性と相関を持ってオペレーション評価値の平均が変動していれば，オペレーション評価値が最適化処理において有効であると言えよう．
• 最適化終了条件の妥当性

オペレーション評価値のグラフ全体に対する平均値の変動で，最適化を終了するか判断する．過去 n 回最適化ループを行う前との差が閾値未満になる (式 3) か，グラフ中の状態数が 2 つ以下になったら最適化を終了する．

Et

Nt

P−

Et−n

Nt−n

< Th

実験目的

現在の手法で生成される基礎変化モデルの性質を調査した．生成された基礎変化モデルについて以下の点を調査し，本研究の手法の妥当性を確認する．
• 状態遷移確率の分散，状態毎の遷移先数一つの状態を二つに分ける操作である．対象となる状態の状態空間について，パラメータを一つ選択し範囲内のランダムな値で分割する．(図 9) ただし分割オペレーションの効果は，分割後の 2 状態に対する遷移関係が再構築されるまで不明である．従って遷移関係を再構築後，その時の分割が最適化に反していたらその分割を取り消す．その為に，分割前の状態をグラフの外に一時的に保持しておく．
(6) 最適化の終了条件

P

基礎実験と考察(3)

3

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

図 9: 分割オペレーションの例
遷移確率の範囲
100%
90% 以上 40% 以上 60% 未満
最適化前
65(23)
65(23)
47(16)
最適化後
0(0)
3(75)
1(25)

図 10: 全状態の遷移先数の平均

表 1: 最適化前後における遷移確率による状態の分類個数
最適化の終了条件の妥当性を検証するため，最適化前後でのグラフの変化を調査する．
• 生成されたモデルの評価生成されたモデルの状態を遷移確率で分類し，モデルの質を検証する．

4.2

図 11: 全状態のオペレーション評価値の平均

実験環境

以下のような環境で基礎変化モデルを生成した．
• 金魚:体長 3[cm] 程，500[匹]• 水槽:サイズ縦 110[cm] ×横 65[cm]，水深 10[cm]• 動画の長さ:約 33 秒間 (500 フレーム)• 抽出したパラメータ(1) 白画素数(2) 白領域の差分画素数(3) 白領域の重心座標 (2 次元)(4) 白領域の重心座標の速度ベクトル (2 次元)

図 12: 遷移確率の分散の平均抽出したパラメータは任意に選択した．次節で挙げた数値は，この同一条件の下で 10 回の分析・基礎変化モデル生成において毎回調査し，結果の値を平均した．

4.3• 最適化終了条件の妥当性
最適化後の全状態数は最適化前の 2.5% ほどになっている．最
適化中の全状態数はほぼ単調減少なので，最適化ループの回数が増えるほど状態数が減少し，金魚の分布変化パターンの分析モデルとしては精度が低下することになる．従って最適化終了条
件の閾値をどうするかが基礎変化モデルの精度を左右する．しかし絞込み変化モデル生成に際して予測精度を向上させる為に状態定義を変更するので，基礎変化モデルはできるだけシンプルであった方が良いとも考えられる．遷移確率を高く保持できるのであれば，状態数は少なくても充分であると評価する．

実験結果

実験の結果を以下に示す．
• 総結合回数:290• 総分割回数:39.4
次の値の最適化中における変化をそれぞれ示す．
• 状態毎遷移先数:図 (10) 参照• 全状態のオペレーション評価値の平均:図 (11) 参照• 全状態の遷移確率の分散:図 (12) 参照• 全状態数:最適化前 283 →最適化後 6.75
図 (10)〜図 (12) は共に横軸が最適化中のループ回数を表す．最適化が進むに連れて遷移先合計数とオペレーション評価値の平均は減少
し 0 付近に収束している．反対に遷移確率の分散の平均は最適化が進むほど増大している．
生成されたグラフの質を見るため，ある最適化の一例を対象に，状態を状態毎の最大の遷移確率で分類・係数した (表 (1))．表中の数値は条件に当てはまる状態数を，() 内は全状態数に占める割合を示す(単位% )． 90% 以上 は予測可能性が良い状態として， 40% 以上60% 未満 は悪い状態として選択した．1004.4• 生成されたグラフの評価
表 1 を見ると，遷移確率 100% の状態が最適化によって消滅している．しかしこの 100% の状態は，実は動画全体を通して 1回しか遷移しないレアケースで，仮に残しておいても予測に対する影響は小さい．その代わり遷移確率が 90% 以上の状態は最適化後の方がずっと割合が大きく，モデル全体では予測可能性を向上させていると言える．状態数が 1 とはいえ，40% 〜60%の割合が増加してしまっていることが今後の検討課題である．

5.

おわりにすくい易い金魚を絞り込む技能伝達のベースとして，金魚の分布変化パターンのモデル化を試みた．エキスパートにインタビューをする
前段階の成果としてはまだ充分なものにはならなかったが，モデル生
成アルゴリズムの可能性と改善の余地がある事を確認できた．今後の展開としては次の事を計画している．
• 基礎変化モデル生成手法のブラッシュアップ• 絞込み変化モデルの生成• 金魚すくいのエキスパートへのインタビュー

考察• 最適化のプロセスの妥当性
最適化が進むに連れて状態遷移確率の分散の平均は増大し，状態毎の遷移先数は減少している (図 12，図 10)．本研究で主張する手法によって，目的とする基礎変化モデルが得られる可能性を示すものである．また最適化の 30 回目付近が値の変動の境界になっている．
• オペレーション評価値
遷移先数の平均にしても全状態のオペレーション評価値の平均にしても 30 回ほどで収束し，逆に状態遷移確率の分散の平均は30 回を過ぎた辺りから増え始めている．つまり最適化はまず遷移先数を減らし，それが収束すると遷移確率の分散を高めるように作用していることになる．このことからオペレーション評価
値の現在の定義では，遷移確率の分散の高低よりも遷移先数の多少を優先して状態を評価しているのではないかと考えられる．

参考文献[1] 守田 了，石原由紀夫:
熟練ドライバーの視点移動に基づく初心者ドライバーの視点誘導 ，電子情報通信学会 信学技報，
pp43-48，2003[2] 板橋界児，平名計在，鈴木達也，大熊 繁，藤原文治: 時間／事象駆動ハイブリッドシステムに基づく組み立て技能制御器の実現 ，計測自動制御学会論文集（2000）

4