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

3 次元地図を用いた映像データのリアルタイム索引法
Real-time Indexing of Video Data using aThree-Dimensional Map

佐藤 有紀子♥

増永 良文♠

Yukiko SATO

Yoshifumi MASUNAGA

撮影者は街角で GPS とジャイロを装着されたビデオカメ
ラで家並みを撮影する．時刻データと位置データ，ビデオカ
メラの姿勢データ，カメラの画角データに加えて，データベースに格納されている 3 次元地図を使うことにより，映像のどのフレームからどのフレームまでどのような建物が写っていたかを自動抽出し映像に建物名を索引としてリアルタイムで付与することができるアルゴリズムを開発・検証したので，それを報告する．
This paper presents a real-time automatic indexing
method for digital video contents. The method computes
automatically the building objects in a city captured by adigital video camera with a GPS for time and position
data and a Gyro for posture data of the camera. In
addition, a 3-dimensional city map is used to identify thestart and the end frame for each building object to becaptured in a video unit.

1. はじめにディジタル映像処理の研究には，(a) ショット検出（shotdetection ） の 研 究 ， (b) シ ー ン 検 出 （ scene or storydetection）およびシーンの類似検索の研究，(c) 映像ある
いは映像の部分列にメタデータ，つまり索引（index）ある
いは注釈（annotation）を付与する研究，(d) 映像検索技術の研究などがあり，これまで多くの研究がなされてきた[1,2]．
本研究は上記(c)項に類別されるが，画像理解技術，被写体オブジェクトの抽出と追従技術，音声認識技術，話者認識技術，文字認識技術，あるいはカメラワーク情報など従来の技術を用いて特徴量を抽出して索引付けを行おうとするのではなく，GPS,ジャイロ，ビデオカメラのレンズの画角，撮影地点の 3 次元地図を使って，映像に何が写っているかを直接計算して映像の部分列（これをユニットということにする）に被写体オブジェクトを索引として付与しようとする研究である[3,4,5．関連して 6]．本論文はこの研究をさらに進めて，撮られた映像に“リアルタイム”で索引付けをするアルゴリズムを開発して，その有効性を検証した結果を報告するものである．

2. 被写体建物オブジェクトの自動抽出・索引付けシステム
図 1 は我々が開発しているシステムの概念図である．ビデ
オ撮影者の位置と時刻を取得するために GPS，ビデオカメラの姿勢を知るためにジャイロを使用している．カメラの画角
横 44°，縦 35°で，3 次元地図データ（三菱商事製 DiaMap）を，本論文で提案するアルゴリズムで総合的に処理して，被写体建物オブジェクト ID を計算により同定して，その IDとその建物が写っているユニットを対応付けるインデック
ステーブル XBuildings が作成される． 図中，リアルタイム性補償モジュールを除いたモジュールとテーブルの詳細は，先行研究[4, 5]を参照していただきたい．なお，ユニットに関しては，本研究に固有の概念なので，その概略を次に示す．

図1 3次元地図を用いた被写体建物オブジェクトの自動抽出・索引付けシステムの概念
Fig.1 Concept ofAutomatic Extraction and Indexing System ofBuilding Objects using a Three-Dimensional Map
撮影者は市街地を歩行しながらビデオカメラで家並みを撮影する．uv，o，iは建物オブジェクト（oとする）が，ビデオ（vとする）のあるフレーム（bとする）から始まり，あるフレーム（eとする）まで連続して写しこまれている，第i番目の部分とする（i≧1）．このビデオフレームの連続をuv，o，i =(v，o， i， b， e)で表わし，ユニット（unit）と呼ぶ．図 2 に被写体建物オブジェクトとユニットの関係を示す．例では，建物O1とそれが連続して写っているユニットの対がINDEXデータベースのXBuildingsテーブルに記録されるので，少なくとも(O1， uv，o，1) と(O1， uv，o，2)の２つのタップルが存在する．その結果，建物IDで問い合わせると，その建物が写っているユニット全てを知ることができる．

♥学生会員 お茶の水女子大学大学院人間文化研究科博士前期課程 yukiko@db.is.ocha.ac.jp♠
正会員 お茶の水女子大学理学部情報科学科
masunaga@is.ocha.ac.jp

1

図2 被写体建物オブジェクトとユニットの関係
Fig.2 Relationship between Building Objects and Units

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

論文DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
3. リアルタイム性補償モジュール
本章では図 1 のリアルタイム Index 作成モジュール中に示した”リアルタイム性補償モジュール”の説明を行う．

3.1 基本的考え方
通常，映像は 1/30 秒毎に所得されるので，各フレームに写っているべき建物オブジェクト群の抽出とそれに基づいたビデオの索引付けが常に 1/30 秒以内に行われるなら特段の方策を労することなくリアルタイム性が保証される．しかし，このリアルタイム性は大別すると次の要因で阻害される．
(a)1 フレーム分の被写体オブジェクト群の抽出計算が 1/30 秒以内に終了しない．
(b)(よしんば(a)項のリアルタイム性が保障されたとしても，)次々と抽出されるオブジェクト群をフレームごとに取得し処理して，ユニットを構成しかつユニットを XBuildings テーブルに格納する処理に時間遅れがでる．
そこで，我々は，処理の対象となるフレームを動的に“間引いて”リアルタイム性を補償することを考えた．

3.2 映像フレームの動的間引き
映像の第 i(i≧1)フレームの被写体オブジェクト群の抽出処理に p 秒を要したとする．このとき，次に処理するフレームは，p に依存して，i+ ⎡p × 30⎤ (＝p×30 を下回らない最小の整数)番目のフレームとする．(換言すると，この間のフレームが処理の対象から間引かれたことになる．)
さらに，ユニット構成・格納処理で時間遅れが出たときは(この状況は 4.5 節で詳述)，被写体オブジェクト抽出の対象となるフレーム間隔に 1 を加える．一方，あるフレーム間隔でリアルタイム性が一定時間保障されていれば，間引くフレーム数を 1 減じる．
なお，フレーム取得の最小時間単位である 1/30 秒毎に映像データに索引付けがなされることは理想的かもしれない
が，人が認識できる映像はその長さが 3 秒以上であるという報告[7]もあり，また，我々の予備実験では，時間間隔を 1秒にとるとリアルタイム索引付けが問題なく行われているようなので，上記の考え方に無理はないと考えた．

クトがユニット抽出モジュールで処理されるとすぐに，次のオブジェクトを渡す．
z ユニット構成モジュール：ObjectQueue から渡された 1フレームに相当するオブジェクト群を固定長の配列
ObjectHolder に取り込み，“ユニットとして完全なタップル”ができれば，それを XBuildings テーブルに挿入するための SQL 文を発行する．その処理が終ったら，
ObjectQueue から次のオブジェクト群を取り込み，処理を続ける．ここで“ユニットとして完全なタップル”とはある ObjectID が毎回フレームで被写体オブジェクトとして連続して抽出されているが，あるフレームで抽出されなくなる時に決まるユニットのことである．
ユニットを構成し，SQL 文を発行するかしないかの見分けをするためには，新たに ObjectQueue から渡されたオブジェクトと既に ObjectHolder にユニットを構成するオブジェクトとのマッチングをする必要がある．マッチングは以下の 3 通りに分けられる．
① 新規オブジェクトの場合は新規ユニットを構成する．
② オブジェクトが ObjectHolder にユニットを構成するオブジェクトとして存在する場合，そのユニットのフレームデータを更新する．
③ 存在するユニットの中で更新されなかったユニッ
トは”ユニットとして完全なタップル”とみなされて SQL 文を発行し，このタップルを削除する．
（詳しくは次節のアルゴズム）

3.3 リアルタイム性補償モジュールの概要
図 3 は上記の考え方で映像データをリアルタイムで索引付けするモジュール構成の概要である．”リアルタイム性補償モ
ジュール"は"データ取得決定モジュール"と被写体建物オブジ
ェクトで抽出された建物オブジェクトのストリームを一時的に格納するキュー"ObjectQueue"と"ユニット構成モジュール"から成り，画角データ･姿勢データ・位置データの取得間隔をコントロールすることで索引付けのリアルタイム性を補償す
る．各モジュールの働きを下に示す．
z データ取得間隔決定モジュール: 被写体抽出オブジェ
クトモジュールから抽出処理時間を取得し，次のフレーム処理をするための時間間隔を決定する．また，キューの ObjectQueue，配列 ObjectHolder は固定長となるため，溢れが発生した場合には次の処理間隔を１ずらす．これがフレームの間引きのタイミングにつながる．
z ObjectQueue： キューの働きをする．被写体オブジェク
ト抽出モジュールによって抽出されたオブジェクトがストリームとなってフレーム番号と供に ObjectQueueで一時的に保持される．ObjectQueue の渡したオブジェ

2

図3 リアルタイム性補償モジュール
Fig.3 Real-Time Compensation Module

3.4 リアルタイム索引作成アルゴリズムの実装
図 4 に前節の考え方に基づき実装した XBuildings テーブ
ルのリアルタイム作成のアルゴリズムを示す． "リアルタイ
ム性補償モジュール”がどのように稼動してリアルタイムで映像データの索引付けが出来るのかを具体的に説明する.特に，ユニット構成モジュールの場合分けに注目する．

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

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

図4 XBuildingsテーブルのリアルタイム作成アルゴリズム
Fig.4 RealtimeAlgorithm of Creating XBuildings Table

3.4.1 XBuildings テーブルの属性
図 5 に示すように，XBuildings テーブルの属性は映像番号（VideoID），建物番号(ObjectID)，建物名(ObjectName)，開始フレーム番号（Fs），終了フレーム番号(Fe)，ユニット番号(UnitID)である．

3.4.2 パラメタの説明
配列 ObjectHolder[N]は構造体として以下のパラメタを有する．
z
建物名：ObjectNamez
フレーム開始番号：Fsz
フレーム終了番号：Fez
ユニット番号（一意）：UnitIDz
アップデートされている/いないのフラグ：Update

次に，第 2 フレーム（時刻 t=τ）の処理がなされ，オブジ
ェクト群 B，C，D が被写体オブジェクトとして抽出されObjectQueue に格納されたとする．ユニット構成モジュール
は第 1 フレームの ObjectQueue のオブジェクトの処理が終っていれば，第 2 フレームの ObjectQueue のオブジェクトをObjectHolder に取得し既存のオブジェクトとマッチングをする．このとき B，C オブジェクトは既に ObjectHolder に存在するのでフレーム番号と供にそれらのタップルを更新する（フラグ Update=True)．D オブジェクトは新規なので新たにタップルを作成する（フラグ Update＝Ture)．一方，一番目に抽出されたオブジェクト A は今回は抽出されたかったので（フラグ Update＝False），A のタップルは“ユニットとして完全なタップル”となり，フレーム開始番号，終了番号と供に XBuildings テーブルに格納するべく SQL 文が発行され，ObjectHolder から削除される．
次に，第 3 フレーム（時刻ｔ＝2τ）の処理がなされ，オブジェクト群 C，D，A が被写体オブジェクトとして抽出されObjectQueue に格納されたとする．ユニット構成モジュールが以前のタップルの処理中でなければ第 3 フレームのObjectQueue のオブジェクトを ObjectHolder に取得しマッチングする．このとき C，D オブジェクトは既に ObjectHolderに存在する（フラグ Update＝Ture）のでフレーム番号と供にそれらのタップルを更新する．A オブジェクトは t=0 のObjectHolder にはタップルとして存在していたが，t=τで削除されているため新規タップルとして作成する（フラグUpdate＝Ture）．一方，オブジェクト C，D は今回は抽出されなかったので（フラグ Update＝False）C，D のタップルは“ユニットとして完全なタップル”となる．その結果フレーム開始番号，終了番号と供に XBuildings テーブルに格納するべく SQL 文が発行され，ObjectHolder から削除される．以下，ｔが END になるまで，すなわちデータを取り終わるまで同様に繰り返す．この方法により刻々と抽出された被写体建物オ
ブ ジ ェ ク ト 群 が ObjectHolder に 流 れ 込 む と 同 時 に ，XBuildings を構築していくというリアルタイム性を実現することができる．

3.5 溢れによるリアルタイム性阻害要因の検出

図5 XBuildingsテーブル
Fig.5 XBuildings Table

3.4.3 配列 ObjectHolder への格納と SQL 文発行
データ取得間隔決定モジュールにより決められた間隔（τ）で被写体オブジェクトモジュールによって抽出されたオブジェクト群はストリームとしてフレーム番号と供に次々にキューObjectQueue に挿入される．
たとえば，第 1 フレーム（時刻 t=0)で映っているであろうオブジェクト群 A，B，C が抽出され ObjectQueue に格納されたとする．ユニット構成モジュールはこれらのオブジェクト群を ObjectHolder にフレーム番号と供に格納する．

3

3.1 節で，リアルタイム性を阻害する 2 つの要因を挙げたが，(b)項の要因は，さらに次の 2 つに分かれる．
z ObjectQueue が溢れる(図 3 の①)．ユニット構成モジュールの処理に時間がかかり，被写体オブジェクト抽出モジュールが供給してくるオブジェクト群の処理に追いつけない．
z
ObjectHolder が溢れる(図 3 の②)．ObjectHolder 中のタップルがなかなかユニットとして完全なタップルにならず，かつそのようなタップルが増加していく．
(ObjectHolder のサイズをある程度大きくしておけば回避できよう．)
なお，データベース管理システムの SQL 挿入文処理は，それを発行すると瞬時にコミットしており，リアルタイム性阻害の要因にはなっていないことを確認して，要因とはしなかった．
したがって，図 3 に示すように，オブジェクト抽出の対象となるべきフレーム(間隔)を決める「データ取得間隔決定モジュール」は 3 入力となる．

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

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
4. リアルタイムアルゴリズムの検証

5. まとめと今後の課題

XBuildings テーブルのリアルタイム作成アルゴリズムの一部実装を行った．提案したアルゴリズムの基本的な有効性を検証するために，ObjectHolder は配列 30 として，銀座エリアで収録した 10 分間の映像がリアルタイムで索引付け可能かどうか検証した．
実装環境は以下のようである．
z
OS：Windows XP(CPU: Mobil Intel Pentium4, RAM:256Mbyte)z
描画ソフト：
ゼンリン社製 Zmap-TownⅡ
Autodesk 社製 AutoCad Map 3Dz
開発言語：VB.NETz
データベースシステム：Microsoft Access
その結果，この状況では ObjectQueue と ObjectHolder に溢れが生じることなく時々刻々と図 6 に見られるように被写体建物オブジェクトが抽出された（平均取得間隔 0.5 秒）．
同じ銀座エリアでも建物が密集しているエリアの場合は,被写体建物オブジェクト抽出モジュールの抽出処理時間が 1 秒を超えた．しかしながら，オブジェクトが抽出されると同時に 図 7 に示すようなデータベースがリアルタイムで作成され，リアルタイムで XBuildings テーブルは 1 秒ごとに即時更新される状況が確認できた．また，インタフェースからの
検 索 操 作 は 同 時 実 行 可 能 で あ っ た ． な お ， 10 分 後 のXBuildings テーブルのタップル数は 188 であった．

本論文では，GPS とジャイロセンサデータ，レンズ画角データに加えて，撮影地点の 3 次元地図を使うことで，映像に写し込まれている建物オブジェクトを自動計算するにあたり，計算環境の変化に動的に対応して，映像にリアルタイムで建物オブジェクトを索引付けるアルゴリズムを提案し実装してその有効性を検証した．
今後の課題としては，実際に全てのモジュールを一台のモバイルコンピュータに組み込み，フィールドでの実験を行い，アルゴリズム，リアルタイム性の効率をより具体的に検証することがあげられる．他に，ＧＰＳやジャイロセンサなどの精度の検証と対策，街路樹などの障害物に対する対処法，建物屋上に設置された看板類の扱い，視野長 L の設定法，建物オブジェクトの重要度の考慮や富士山・東京タワーといったランドマークの扱い方などが挙げられる．
末筆ながら，本研究を支援してくださった方々に深謝する．

図6 3次元での被写体建物オブジェクト抽出
Fig.6 Three Dimensional Building Object Extraction[文献］[1] Vaughan， G.， Smeaton， A.， Gurrin， C.， Lee， H.，
and McDonald， K.: “Design， Implementation and Testing ofan Interactive Video Retrieval System，” Proceedings of the 5thACM SIGMM International Workshop on Multimedia
Information Retrieval， pp.23-30，November 2003.
[2] Wang， Y.， Ostermann， J. and Zhang， Y-Q.: “VideoProcessing and Communications，” (book) Prentice Hall，
2002.
[3] 石黒玲，佐藤有紀子，増永良文“3 次元地図を用いたビデオコンテンツの自動索引法−被写体建物オブジェクトの自動抽出−”，情報処理学会研究報告（DBWS2003），
Vol2003，№133-55，2003 年 7 月．
[4] 佐藤有紀子，石黒玲，増永良文“3 次元地図を用いたディジタルビデオコンテンツの自動索引法の提案と検証”，
日本データベース学会（DBSJ Letters），Vol.3，No.1，
pp.149-152，2004 年 6 月．
[5] Yukiko Sato and Yoshifumi Masunaga: ”A Novel Indexing
Method for Digital Video Contents using a 3-Dimentional CityMap ”，Proceedings of the 4th International Workshop on Web
and Wireless Geographical Information Systems (W2GIS)，
pp.333-343， November 2004.
[6] 上田隆正，天笠俊之，吉川正俊，植村俊亮：“位置情報と時刻情報を用いた映像データの索引付け手法，”電子情 報 通 信 学 会 第 12 回 デ ー タ 工 学 ワ ー ク シ ョ ッ プ（DEWS2001），2001 年 3 月．
[7] HonJian Zhang， Chien Yong Low， Stephen W. Smoilar，and JianHua Wu: ”Video Parsing, Retrieval and Browsing”，
Intelligent Multimedia Information Retrieval, ed. Mark T.
Maybury， PP.139-158， MIT Press， Massachusetts， 1997.

佐藤 有紀子Yukiko SATO

2005 お茶の水女子大学大学院人間文化研究科博士前期課程
数理・情報科学専攻修了．映像データベースシステムの研究・開発に従事．日本データベース学会学生会員．

増永 良文

図7 リアルタイム生成されたXBuildingsテーブル
Fig.7 XBuildings Table created in Real-Time

4

Yoshifumi MASUNAGA

お茶の水女子大学理学部情報科学科教授．1970 東北大学大学院工学研究科博士課程修了，工学博士．データベースシス
テムの研究・開発に従事．情報処理学会および電子情報通信学会フェロー．日本データベース学会会長．著書に「リレーショナルデータベース入門[新訂版]」(サイエンス社)など．

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