1A1-H-46

時分割式超音波３次元位置計測のための同時サンプリング手法
相 澤 洋 志 †1西 田 佳 史 †2 †3堀 俊 夫 †2 †3柿 倉 正 義 †1

†1 東京電機大学 †2 産業技術総合研究所 デジタルヒューマン研究センター †3 CREST, JST

Simultaneously sampling algorithm
for time-sharing type of ultrasonic location sensor
Hiroshi Aizawa †1 , Yoshifumi Nishida†2 †3 , Toshio Hori †2 †3 , Masayoshi Kakikura †1†1 Tokyo Denki University†2 Digital Human Research Center,
National Institute of Advanced Industrial Science and Technology (AIST)†3 CREST, JSTAbstract The time-sharing type of ultrasonic location sensor has a problem that the sampling frequency intracking ultrasonic transmitter decreases as the number of transmitters to be tracked increases. To solve theproblem, this paper proposes a new algorithm for simultaneously sampling an ultrasonic transmitter of thetime-sharing type of ultrasonic location sensing system. The algorithm makes it possible to track transmitters’
positions with a high sampling frequency considering the density of transmitters. The eﬀectiveness of theproposed algorithm is conﬁrmed by simulation and experiments.
Key Words: Human Activity Obervation, Ultrasonic Location Sensor, Location Algorithm

1.

緒論

日常空間で行われる人間の行動を観察するためのシステムとして，本研究では，これまでに超音波 3 次元タグシステムを構築してきた 2, 3) ．超音波 3 次元タグシステムは，対象物の性質を維持しつつ対象物に超音波 3 次元タグ (超音波送信器) を取り付けることで，対象物をセンサ化することによって人の日常行動を観察することを可能とするシステムである．このシステム
では，超音波発信を時分割で行っているために追跡すべき超音波タグ（送信器）の数が増えると，タグ 1 個あたりのサンプリング周波数が低下する問題点がある．
現在のシステムにおけるタグ 1 個あたりのサンプリン
グ周波数は，約 50 Hz であるため、送信器の数が n 個の場合は，50/n Hz になる．
サンプリング周波数の低下を防ぐための方法として，
1) 複数の超音波周波数を利用する方法や，2) 発信する超音波パルスをコード化する方法が考えられる．しかし、これらの方法は，回路構成の複雑化に伴う高コスト化を招くといった問題がある．その他にも、特に1) では、多数の周波数バンドを確保するためには、周波数のレンジが広くなり、周波数の特性が変化してしまう、2) では、エンコードする際のエラーが多発するといった問題があり、実用上有用な解決とはなりにくい．そこで、本研究では，複数の送信器から同一の周波数の超音波を同時に発信させることによって，送信器の 3 次元位置を推定する手法を提案してきた 4, 5) ．
この手法による 3 次元位置の導出の手順の概要は以下である．A) 複数の対象物に取り付けられた送信器から超音波を同時に発信し、各受信器で複数の距離情報を取得する, B) ある受信器に着目した時、どの距離情報がどのタグから到達したものであるのか不明であるので、全組み合わせを試し 3 次元位置を計算する、C) 冗長な受信器 (3 個以上) の距離情報によって最適な3 次元位置の推定値を選択する．この提案手法によって，お互いの送信器が少なくとも 50 cm 離れている
複数の送信器から，超音波を同時に発信した場合の送信器の位置を推定することが可能であることを検証してきた．しかしながら，組み合わせの爆発の問題のため，50Hz のサンプリングが可能な最大発信器数は 3個であり，同時サンプリング可能な数の増大が課題であった．
本稿の目的は，従来の問題点を改善するために，発信器相互の存在密度を評価し，同時発信と時分割発信とのハイブリッド発信を行うことで，各発信器のサンプリング周期を高く維持することが可能なアルゴリズ
ムを提案し，検証することにある．

日本機械学会 [No.04-4] ロボティクス・メカトロニクス講演会’04 講演論文集

1A1-H-46(1)2004.6.18〜20 名古屋市

2.

送信器の存在密度を考慮した高サンプリングアルゴリズムの提案

提案手法を示す．現在の発信器の位置は既知であることを仮定する．

• 発信器の存在密度を考慮し、図 1 に示すようにグループ分けする．図 1 の (C) の場合、赤色の領域が低密度領域、青色の領域が低密度領域で、全部で 4 グループ存在している．
• 青色のグループにある発信器を同時発信させる．
さらに、赤色のグループにある発信器は、各グループ内で時分割発信させる．例えば、図 1 の(C) の場合、ある瞬間には、青色グループ内の 4個の発信器と 3 個の赤色グループ内の 1 個づつの合計 7 個が同時発信されることになる．
• 受信器で得られた距離情報を用いて各発信器の位置を計算する．各発信器の位置の計算は、前回の発信器の位置情報をもとにして、超音波が到達されるはずの受信器を選択し、選択された受信器の距離情報のみを使用することで計算する．

本節では，日常空間に存在する送信器相互の存在密度を考慮して，同時発信と時分割発信のハイブリッド発信を行う手法を提案する．

2·1

広範囲に分散した発信器の存在密度

通常、日常空間に分散した送信器の存在密度は，一様ではなく、図 1 に示すように、高い領域と低い領域が混在していると考えられる．以下、超音波到達範囲が重なっている領域が密度が高い領域、それ以外を密度が低い領域と呼ぶことにする．より一般的には、図2 に示すように、(A) 全てが高密度の場合，(B) 全てが低密度の場合, (C) （複数の）高密度領域と低密度領域が混在する場合，に分類可能である．
⿥㖸ᵄ೔㆐▸࿐⿥㖸ᵄ࠲ࠣ㧔⊒ାེ㧕

提案手法を用いると，全ての領域が密度が低い場合，全ての発信器 (n 個) を同時発信させ，それらの位置を計算することが可能であり、サンプリング周波数はシステムの最高サンプリング周波数 (我々のシステムでは 50 Hz) である．全ての領域が密度が高い場合には、全ての発信器 (n 個) が時分割発信となり、50/n Hz となる．多くの場合は、（複数の）高密度領域と低密度領域が混在する場合であると考えられるので、50/n〜50 Hz の位置情報更新が可能となる．

Fig.1 Diversified density of transmitters distributed
in environment

2·3

ハイブリッド発信アルゴリズムの手順を述べる．図3 にフローチャートを示す．各発信器は優先度をあらわす属性を持つ．

⊒ାེ# ోߡኒᐲ߇ૐ޿႐ว$ ోߡኒᐲ߇㜞޿႐ว% ኒᐲ߇㜞޿㗔ၞߣૐ޿㗔ၞ߇ᷙ࿷ߔࠆ႐ว

Fig.2 Density of transmitters distributed in environment

2·2

発信器の存在密度を考慮した超音波のハイブリッ
ド発信アルゴリズム

発信器の存在密度を考慮した超音波のハイブリッ
ド発信の原理発信器の存在密度を考慮することで、各発信器の位置情報の更新レートを高く維持することを可能とする

1. 超音波発信を優先度 (Priority) 順にソートし，最も高い優先度の発信器から順に以下の 2〜4 のステップを実行する．
2. i 番目に高い優先度を持つ発信器を発信させた場
合，同時発信リストに含まれている優先度が高い発信器と干渉するかを計算する．干渉しない場合
は，ステップ 3 に進み，干渉する場合は，Priorityを上げる（発信させない)．
3. i 番目に高い優先度を持つ発信器を発信させた場
合に，超音波が受信可能である受信器を調べ，その数が発信器の位置を計算するのに十分かを計算する．十分な場合，ステップ 4 に進み，十分でない場合，Priority を上げる（発信させない)．
4. i 番目に高い優先度を持つ発信器を同時発信リストに加える．
5. 同時発信リストにある発信器を全て同時に発信させ，以下のステップ 6〜8 を各発信器に対して実行する．
6. ID=k 番の発信器の位置を計算する．
7. ID=k 番の発信器の位置が計算可能であった場合，ステップ 8 に進み，計算不能であった場合には，Priority を上げる．
8. ID=k 番の発信機の優先度を下げる (Priority=0)．

1A1-H-46(2)きのサンプリング周波数は，送信器 1 個当たり平均約30 Hz である．いずれの場合も，時分割発信を行った
場合 (n 個の発信器の場合, 50/n Hz) よりも高いサンプリングが可能であることを示している．

STARTԘఝవᐲ㗅ߦ⊒ାེ+&ࠍ࠰࡯࠻ߔࠆఝవᐲK㨪P⇟⋡ԙ⊒ାེ K⇟⋡ߩఝవᐲ ߪ㧘หᤨ⊒ା࡝ࠬ࠻ߦ޽ࠆ㧔ఝవᐲߩ㜞޿㧕⊒ାེߣᐓᷤߒߥ޿߆㧫〒㔌ᖱႎࠍ฽߹ߥ޿ฃାེ୘ߩ〒㔌ᖱႎࠍ฽߻ฃାེ୘એ਄ߩ〒㔌ᖱႎࠍ฽߻ฃାེᐓᷤߔࠆ૏⟎⸘᷹น⢻ߥㅍାེ૏⟎⸘᷹ਇน⢻ߥㅍାེᐓᷤߒߥ޿Ԛ⊒ାེ KVJ ߩ૏⟎ࠍ⸘▚ߔࠆߩߦචಽߥฃାེ߇ሽ࿷ߔࠆ߆㧫ሽ࿷ߒߥ޿ሽ࿷ߔࠆԛหᤨ⊒ା࡝ࠬ࠻ߦട߃ࠆԜหᤨ⊒ା࡝ࠬ࠻ߦ޽ࠆ⊒ାེࠍหᤨ⊒ାߐߖࠆ⊒ାེM㨪P⇟⋡ԝ⊒ାེߩ૏⟎ࠍ⸘▚ߔࠆԞ⸃ߌߥ߆ߞߚ⊒ାེߩ૏⟎߇⸘▚น⢻ߢ޽ߞߚ߆㧫⸃ߌߚԟఝవᐲࠍਅߍࠆ 2TKQTKV[ఝవᐲࠍ਄ߍࠆ 2TKQTKV[Fig.4 Results of simulation based on proposed algorithm (Top is in case of 10 transmitters，bottom
is in case of 20 transmitters)

3·2

Fig.3 Flow chart of hybrid emission algorithm

シミュレーションにおける時分割・同時ハイブ
リッド発信アルゴリズムと時分割発信の比較

3.

シミュレーションと実環境を用いた検証

3·1

MATLAB を用いたシミュレーションの結果

広範囲 (10 m×10 m) に分散した 10 個，20 個の送信器に対して，提案した時分割・同時ハイブリッド発信アルゴリズムによって，超音波タグ（発信器）の位置を計算するシミュレーションの様子を図 4 に示す．
受信器は，10 x 10 m の範囲に，1 m おきに 100 個配置している．上図は，送信器 10 個の場合，下図は，送信器 20 個の場合のシミュレーション結果である．発信器の位置はランダムに与えた．
図中における各々のマークは，黒丸 : 距離情報を含まない受信器，青丸 : 1 個の距離情報を含む受信器，赤丸 : 2 個以上の距離情報を含む受信器である．また，
紫色 ⊕ 記号 : 位置計測可能な送信器，黒色 ⊕ 記号 :位置計測不可能な送信器である．
送信器が 10 個の場合，全ての送信器の 3 次元位置推定が可能であるを示している (図中が紫丸 ⊕ 記号は，位置計測可能な送信器を示す．)．このときのサンプ
リング周波数は，送信器 1 個当たり平均約 50 Hz であった．また，送信器が 20 個の場合，紫丸と黒丸が存在していることがわかる．これは，全ての送信器の位置推定が同時に行えないことを示している．このと時分割・同時ハイブリッド発信アルゴリズムと，時分割発信を行った場合のサンプリング周波数の比較を
図 5 に示す．横軸は，送信器の数，縦軸は，サンプリング周波数を示している．青線は，時分割・同時ハイブリッド発信アルゴリズムによる計算結果を示し，赤線は，時分割発信による計算結果を示している．
時分割・同時ハイブリッド発信アルゴリズムの場合，送信器が 1 個 ∼10 個がランダムに存在している場合，ほぼ全領域が低密度な状態に近くなるため，サンプリング周波数を 50 Hz で維持可能であることがわかる．
時分割発信の場合，対象物の数に比例してサンプリング周波数の急激な低下が見られるが，時分割・同時ハイブリッド発信アルゴリズムの場合は，送信器の増加に伴って，やはりサンプリング周波数の低下が見られるものの，急激な低下は見られなかった．以上のことから，時分割・同時ハイブリッド発信アルゴリズムと時分割発信を比較すると，送信器が多い場合，時分割・同時ハイブリッド発信アルゴリズムを使用した方がサンプリング周波数の低下を抑えられることが確認された．

3·3 検証実験のための環境の構築
時分割・同時ハイブリッド発信アルゴリズムの検証を行うために構築した検証システムを図 6 に示す．こ1A1-H-46(3)50-2000040〒㔌࠺࡯࠲ࠍ฽߹ߥ޿ฃାེ୘ߩ〒㔌࠺࡯࠲ࠍ฽߻ฃାེ304000

୘એ਄ߩ〒㔌࠺࡯࠲ࠍ฽߻ฃାེ20Time division (conventional method)2000

૏⟎ផቯ߇น⢻ߥㅍାེ8000

૏⟎ផቯ߇ਇน⢻ߥㅍାེ

10000

6000

10000

10Frequency [Hz]Simultaneous sampling

5000[mm]0ታ਎⇇ߦࠃࠆ⚿ᨐ ㅍାེ୘-2000

00

20

40

60

80

0100

The number of Transmitters

2000

3000
2000
1000
04000
6000

Fig.5 Comparison between sampling frequency of
hybrid emission algorithm and that of timesharing emission

10000

10000

5000
0100005000

00 [mm]ࠪࡒࡘ࡟࡯࡚ࠪࡦ⚿ᨐの空間は，高さ 3.0 m，横 8.0 m，縦 11.0 m である．
天井には，1.0 m 間隔で 88 個の受信器が取り付けられている．
．

10000

5000

8000

ታ਎⇇ߦࠃࠆ⚿ᨐ ㅍାེ୘

Fig.7 Result of simultaneously sampling algorithm in real space (left below:simulation，rightabove:2D display based on measured values inreal space，right below:3D display based on
measured values in real space)

Receiver1mト）が低下するという問題を解決するための手法として，時分割・同時ハイブリッド発信アルゴリズムを提案した．
MATLAB を用いたシミュレーション結果により，10x 10 m の範囲に，1 個 ∼100 個の発信器を分散配置させた場合，各発信器の位置情報更新を 50/n Hz 以上で可能であることを確認した．さらに，受信器 88 個からなる検証システム（計測範囲 8 x 11 m) を用いた検証実験により，提案した手法が実現可能であり，提案した手法によって，高いサンプリング周波数を維持可能であることを確認した．

1m12m
8mTransmitter

参考文献

Fig.6 Experimental system consisting of 88 receivers embedded on ceiling

3·4

実環境下における時分割・同時ハイブリッド発信アルゴリズムの検証実験構築した検証システムに，時分割・同時ハイブリッド発信アルゴリズムを適用し，発信器の位置を計算させた様子を図 7 に示す．
左下図は，送信器から発信した超音波をどの受信器で受信可能であるかを予測した結果を示している．ただし，超音波の発信条件として，送信器の指向性を 100度と仮定している．青丸は，1 個の距離データを含む受信器，赤丸は，2 個以上の距離データを含む受信器，緑丸は，距離データを含まない受信器を示している．
右上図は，5 個の送信器から発信した超音波の実際の距離データをもとに，どの受信器で超音波が受信可能であるかを求めた結果である．右下図は，実際に求まった発信器の位置を表示している．

4.

結論

本稿では，時分割発信式の超音波位置計測装置を用いた場合の問題として，追跡すべき超音波発信器の数の増加に伴って，サンプリング周波数（位置更新レー

1) 独立行政法人 産業技術総合研究所編, “デジタル· サイバー · リアル —人間中心の情報技術 —,”丸善, 2002
2) 西田, 相澤, 堀, 正義, ”超音波センサを用いた対象物のセンサ化に基づく人の日常活動の認識,” 日本機械学会 ロボティクス・メカトロニクス講演会’02 講演論文集, 1A1-J07, June 2002
3) Y. Nishida, H. Aizawa, T. Hori, N.H. Hoﬀman,T. Kanade, M. Kakikura, ”3D Ultrasonic Tagging System for Observing Human Activity, ” inProceedings of IEEE International Conferenceon Intelligent Robots and Systems (IROS2003),
pp.785-791, October 2003
4) 西田, 秋山, 堀, 柿倉, ”超音波 3 次元位置計測のための冗長なセンサデータを用いた高速位置推定ア
ルゴリズム,” 日本機械学会 ロボティクス・メカ
トロニクス講演会’03 講演論文集, 1P1-3F-E6(1)(2), May 2003
5) T. Hori, Y. Nishida, T. Kanade, K. Akiyama,”Multi-lateration for Multiplexed UltrasonicSensors,” in Proceedings of 2003 IEEE International Conference on Sensors (Sensors 2003),
Vol. 2, pp. 1219-1224, October 2003

1A1-H-46(4)