計測自動制御学会東北支部 第 246 回研究集会 (2008.11.19)
資料番号 246-13

視覚センサネットワークにおける視野接続推定の分散化に関する検討
Decentralized topology estimation in a vision sensor network○近藤真, 鏡慎吾, 橋本浩一
○ Shin Kondo, Shingo Kagami, Koichi Hashimoto
東北大学大学院情報科学研究科システム情報科学専攻

Department of System Information Sciences, Graduate School of Information Sciences,Tohoku University
キーワード :

アドホックネットワーク (ad-hoc network)，視野接続 (vision graph，vision topology)，

SIFT(Scale Invariant Feature Transform)，分散ハッシュテーブル (Distributed Hash Table)，

連絡先 :〒 980-8579 仙台市青葉区荒巻字青葉 6-6-01 東北大学 情報科学研究科 橋本・鏡研究室

近藤真, TEL 022-795-7021, FAX 022-795-7019, E-mail: skondo@ic.is.tohoku.ac.jp

1.

緒言

クを想定していることは少ない．しかし，近近年，センサネットワークに関する研究1) が盛んに行われている．特に，観測対象とする空間に無造作に多数のセンサを配置し，そのセンサが自律的に無線によってネットワークを結んでいくことを想定した研究が重要視されている．この場合，ネットワークが静的に設置されているのではなく，近隣にあるセンサ同士が互いと接続しながら動的にネットワークを構築していく．このようなネットワークはアドホックネットワークと呼ばれる．

年集積回路技術の向上によりカメラの小型化，低コスト化，低電力化がますます進んでおり，従来では考えられなかった応用が実現可能になってきている，カプセル型の胃カメラなどの極小の無線カメラの開発が進んでおり，極小カメラを大量にバラまくように配置させるアドホックな視覚センサネットワークの実現も現実味を帯びてきている．人の立ち入りが困難な災害現場でカメラを散布し負傷者を見つけるなど，視覚センサの新たな応用が期待されている．

一方でカメラを用いたセンサネットワークの分野では，複数のカメラをネットワークで結び協調動作させる研究が盛んに行われている．ただし，カメラネットワークは静的に構成されていることが多く，アドホックネットワー

このようなアドホックな視覚センサネットワークを構築するには従来のアドホックネットワークとは別の難しさがある．通常のアドホックセンサネットワークでは，物理的に隣接したセンサ同士が互いに接続されていく．し–1–

あり，画像認識で広く用いられている．SIFTにより得られる特徴量は標準的には128次元のベクトルであり，特徴点の対応づけはその128次元空間中でのユークリッド距離が近い特徴点を探すことで行われる．ただし，SIFT では誤った対応点も検出されるので，本研究では，物理的隣接関係一定数以上の対応点が検出されたら視野が接視野接続関係

Fig. 1

続していると判断する．

視覚センサネットワーク

かし，Fig. 1のように視覚センサの場合は，セ2.2

視野接続推定の分散化

ンサ同士が物理的に隣接していても共通の事
多数のカメラノードの相互間の視野接続を象を見ているとは限らない．視覚センサ同士を協調動作させるには視野接続関係にもとづく論理的ネットワークの構築が重要になる．そこで，本研究では視覚センサネットワークの視野接続関係を効率よく推定する方法を提案

推定する場合は，全カメラノード対全カメラノードについて特徴点の対応づけを行う必要がある．それを行う一つの方法として，すべてのカメラが持つデータを一つのノードに集め，そのノードですべての対応づけを計算すし検討していく．

る方法が考えられる．しかし，そのノードの2.

視野接続の推定2.1

視野接続推定の原理

周囲のリンクに負荷が集中してしまうことや，そのノードが機能しないと対応づけができないことなどの問題があり，一般にセンサネッカメラに画像処理プロセッサを組み込みネットワークには適さない．
また別の方法としては，各カメラノードのトワークに接続できるようにしたものを，本研
究ではカメラノードと呼ぶ．カメラノード間の視野接続推定にはいくつかの先行研究がある．
例えば，Detmoldら2) はカメラに映る動き情報をもとに視野接続を推定している．Chengら3)は画像間での特徴点の対応づけを用いて推定している．本研究ではChengら同様，画像間での特徴点の対応づけを用いる．ここで特徴点とは，物体のコーナーやエッジが交差する所など，複数の画像間で対応づけがとりやすい点のことである．特徴点の対応づけには SIFT
(Scale Invariant Feature Transform)4) を用いる．SIFT は画像中から特徴点を見つけ，その点を表現する特徴量を画像の回転やスケールデータを他のカメラノードすべてに送信 (ブロードキャスト) した上で，各カメラノードにおける視野接続先はそのカメラノード自身に計算させるという方法が考えられる．しかしこの方法では，同じデータをカメラノード数の数だけ重複して送るので無駄が生じ，ネットワーク全体のデータ通信の負荷が大きくなる問題がある．その解決策として Cheng ら 3)
は，データをブロードキャストするが，特徴点数の削減，特徴量次元の圧縮によりデータ通信量を削減することでネットワーク全体の負荷を低減している．しかし，重複による無駄が生じる点には変わりがない．

倍にロバストな形で得ることができるもので–2–2.3

特徴量空間分割法

もう一度整理すると，カメラノード間で視3.

推定精度と通信量の評価

3.1

手順

野接続を推定する際に必要なことは，与えられた特徴量に近いものを観測しているカメラノードをネットワークから探しだすことである．これは Peer-to-Peer (P2P) ネットワーク
5) における共有ファイル発見の問題と似ている．P2Pネットワークの分野では，多数のネットワークノードの中から効率よくファイルを発見するため，分散ハッシュテーブルと呼ばれる技術が開発されている．分散ハッシュテー
ブルでは，ファイルの内容をハッシュ関数により数値に変換し，その数値にノードを対応づけることで，そのファイルの管理情報を持つノードを決定する．

16 台のカメラノードのネットワークを想定して実験を行った．物理的なネットワークに関する情報はすべて既知とし，そのトポロジーは 4 × 4 の 2 次元メッシュとした．カメラは 640× 480 画素で，実際にはカメラ一台で Fig. 2 の4シーンを16枚ずつ撮影した．視野が接続していると判断する基準は対応点が 20 個以上得られた場合とした．128次元の特徴量空間から射影する部分空間は，カメラを2次元上に配置するのと対応させ 2 次元空間とした．射影する 2次元の選択は，今回用いた SIFT の実装 6) における128次元の特徴量ベクトルから18番目と40番目の要素を取り出すことで行った．これら

本研究ではこの技術を援用し，特徴点の対応はすべて経験的に定めた．

づけの分散化を行う．具体的には，まず，128次元の特徴量をある適当な部分空間に射影する．この部分空間の選択は射影後の特徴量がより広く分散するように選ぶことが望ましい．
その部分空間を格子状に分割する．分割した領域のそれぞれをいずれか一つのカメラノードに対応させ，その領域内にある特徴量をそ

データ通信量の評価に関しては，ブロードキャストの場合は，各データはすべてのリンクを一方向に一度だけ通ると仮定する．一方特徴量空間分割法の場合は，経由するリンク数が最小となる経路で特徴量を送信するとする．リンク数が最小の経路は一般に複数ありえるが，毎回ランダムに選ぶものとする．のカメラノードにのみ送信する．特徴量を受け取った各カメラノードは，対応する分割領域内の特徴点について近傍点の探索を行う．

128 次元空間で，ある距離 R だけ離れている
2 つの点は，射影された部分空間上では，その相互間の距離がR 以下となる．よって，対応づけられる特徴点の多くは各分割領域内で見つけることができると期待できる．ただし．すべてが見つかるとは限らないため視野接続関係推定の精度の劣化につながる．そこで以下ではデータ通信量低減効果とともに推定精度

Fig. 2劣化の程度を評価する．

–3–

使用した 4 シーンの画像

3.2.1

実験結果
ブロードキャスト(従来)特徴量空間分割法(提案)

視野接続関係推定精度

正しく視野接続関係を推定した割合(%)

3.2

Fig. 3 と Fig. 4 はシーン 1 について視野接続を推定した結果である．Fig. 3 はブロードキャストによるもので，Fig. 4は特徴量空間分割法によるものである．視野が接続していると推定したものを線で結んでいる．シーン1は部屋の中央で回転しながら画像を撮影したもので100908070605040302010あるため，隣り合わせの画像で正しく視野が0接続していると考えてよい．どちらもほぼ正

Fig. 512scene34

視野接続推定精度 (4 シーン)

しく推定できているといえる．
合で正しく推定できており，特徴量空間分割法でも推定精度は大きく劣化していないといえる．
ブロードキャスト(従来)

データ通信量の比較

3.2.2

視野接続と推定

シーン1におけるカメラノード間の各リンクのデータ通信量をFig. 6に示す．特徴量空間分割法の方がどのリンクでも大きく通信量が減少していることがわかる．ブロードキャストの場合に各リンクの通信量が一定の値なのは，Fig. 3

視野接続関係推定 (ブロードキャスト)

データがすべてのリンクを一度だけ流れると仮定しているためである．
ブロードキャスト(従来)特徴量空間分割法(提案)8

データ通信量(Mbyte)

7

特徴量空間分割法(提案)
視野接続と推定6543210123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

カメラ間のリンクの番号

Fig. 6
Fig. 4

データ通信量の比較 (シーン 1)

4 シーンそれぞれについて全データの通信

視野接続関係推定(特徴量空間分割法)

量を比べた結果を Fig. 7 に示す．ブロードキャ

4シーンそれぞれについて正しく視野接続をストと比較して特徴量空間分割法の方が通信推定できた割合を Fig. 5 に示す．9 割前後の割量は約 10%に抑えられている．Fig. 7 はさらに–4–

ドはクラスタ内の代表ノードにデータを送信

全リンクのデータ通信量(Mbyte)

ブロードキャスト(従来)Chengらの方法(従来)
特徴量空間分割法(提案)し，各代表ノードは他の代表ノードすべてに，クラスタ内から集めた全データを送信すると200180160140120100806040200仮定する．一方特徴量空間分割法の場合は，特徴量空間の分割数は 16 とし，それぞれを代表ノードと対応させる．

4.2123

実験結果

4

ノード数を増加させた時の1リンクあたりのscene

データ通信量を比較した結果を Fig. 8 に示す．

Fig. 7

データ通信量の比較 (4 シーン)

Chengらの論文3) において同手法の代表的な結果として記載されている通信量も示している．
これと比較しても特徴量空間分割法の方が約40%に抑えられている．Chengらの方法は，特徴点を選択し，特徴量の次元数を圧縮することでデータ通信量を低減している．特徴量空グラフより特徴量空間分割法の方がブロードキャストとChengらの方法3) と比較して大きくデータ通信量を低減できていることがわかる．
また特徴量空間分割法のデータ通信量の両手法に対する低減率をみると，ノード数が増加してもそれぞれ約10%，40%であり，同傾向を保っている．

間分割法では特徴点の選択はできないが，特ブロードキャスト(従来)Chengらの方法(従来)
特徴量空間分割法(提案)

徴量の圧縮は適用可能なのでさらなるデータ80通信量の低減が可能だと考えられる．

1リンクのデータ通信量(Mbyte)

4.

70

ノード数増大に対する評価

より多数のノードを持つネットワークに適6050403020用した場合の評価を行った．単純なブロード10キャストと比較した場合の提案手法の優位性

01664は明らかなため，ブロードキャストの場合も，ノードを一定数ごとにクラスタ化するとし，比較を行った．

4.1

144256400

5767841024 1296 1600 1936

カメラノード数(個)Fig. 8 データ通信量の比較 (ノード数を増加させた場合)

手順

クラスタの代表ノードを 16 台とし，各クラ5.

スタ内では簡単のため同じ画像を使用する．
ノード数は 16〜1936 台まで増加させる．

結言

本研究では視覚センサネットワークにおいて効率よく視野接続を推定するための手法をデータ通信量の評価に関しては，ブロード提案した．視野の接続は画像特徴量の対応づ

キャストの場合は，各代表ノード以外のノーけにより行うとし，その特徴量空間を分割す–5–ることで分散化を行う．実画像を用いたシミュ

Intl. Journal. Computer Vision, 60-

レーション実験により，視野接続推定精度を2, 91/110 (2004)大きく損なわずに，データ通信量を大幅に低減できることを示した．

5) 江 崎 浩:

P2P 教 科 書,インプレス

R&D (2007)

今後の課題を述べる．今回の評価は限定された条件下で行ったものであり，今後さらに

6) Rob

Hess:

SIFT

FeatureDetector,多様な条件下で実験を行う必要がある．特徴

http://web.engr.oregonstate.edu/˜hess/,

量空間の次元の選択については，今回は経験(as of October 12, 2007)的に2次元を選択したが，本来は主成分分析等を用いて次元を選択するのが望ましい．また分割法も今回は単純に2次元格子状に分割したが，さらに検討する必要がある．推定精度を上げるためには，分割領域をまたいだ特徴点の対応づけを行う必要があるが，通信量の増大につながるため，詳細な検討が必要となる．

参考文献
1) 徳田英幸: センサーネットワーク総論, 計測と制御, 46-2, 71/76 (2007)

2) Henry Detmold, Anton van den Hengel, Anthony Dick, Alex Cichowski, RhysHill, Elim Kocadag, Katrina Falkner andDavid S. Munro: Topology Estimation
for Thousand-Camera Surveillance Networks, Proc. Intl. Conf. Distributed Smart
Cameras, 195/202 (2007)
3) Zhaolin Cheng, Dhanya Devarajan, andRichard J. Radke: Determining Vision
Graphs for Distributed Camera Networks
Using Feature Digests, EURASIP J. Advances in Signal Processing, 2007-1, 2121 (2007)
4) David G. Lowe: Distinctive Image Features from Scale-Invariant Keypoints,–6–