Time-Varying Mesh (TVM), which is composed of a sequence of mesh models, captures the realistic and dynamic scene of the real world including a human's shape and appearance from multiple synchronized videos. This thesis is to propose key techniques of TVM processing including motion segmentation, sequence summarization, frame interpolation, and motion composition. There are many challenges in the TVM data. For instance, the raw data in mesh models are in low level without any semantic information, which causes the semantic gap. Because each frame is generated independently in the generating system, the topology and the number of vertices may vary frame by frame, which causes correspondence information is difficult to obtain. There is some noise that comes from the generating system, which requires the proposed algorithms are robust to noise. Because the topology in different frames may change, many existing algorithms cannot be employed directly. Another issue is the efficiency to deal with the huge data that come from TVM.

Management of TVM is essential to use the contents efficiently especially when the contents become very huge. Fundamental techniques are proposed to manage and re-use the TVM data. For example, a similarity measure is necessary in many applications like retrieval, which is useful in TVM management. If a TVM sequence is segmented into single motions, it will become much easier to process further. And summarization of a long sequence is helpful to reduce the viewing time. We also propose an editing system to re-organize the frames for a new purpose. Frame interpolation is an important method to generate new frames from the original frames. By these techniques, it is possible to manage and re-use the TVM data efficiently.

Similarity measure is a powerful tool to reflect the motion degree in a TVM sequence, which is the base of motion segmentation, summarization, and composition. Three types of similarity measures are proposed based on statistical methods such as histogram and mutual information. Those statistical methods are very suitable for huge and noisy data. By analyzing the similarity measures, a TVM sequence is segmented into single motions, which is the pre-requisite of our other algorithms including sequence summarization and motion composition. Two approaches are proposed for two different types of motions in TVM sequences, namely, periodic motions and non-periodic motions. Our experimental results demonstrate high precision and recall are achieved.

Summarization of a TVM sequence is necessary in those applications with limited storage, bandwidth, and other resources. For this purpose, we propose an efficient scheme to extract key frames in each single motion or shot. However, it is conflict to summarize a sequence compactly and completely. Therefore, we consider the trade-off between the rate and distortion in our cost function. Unlike many algorithms in 2D video, it is not required to decide the key frame number in advance in our scheme, which is more friendly to the user.

Currently, one serious problem of TVM is that it is time-consuming and expensive to generate TVM sequences. Therefore, it is necessary to re-use the original data to create new sequences. An editing system is presented for this purpose. A motion graph, which includes all the motions in the database, is defined and constructed considering the smoothness of transitions between motions. The user selects some desired motions from the motion database. Then, an optimized path is searched between every two desired motions by a modified Dijkstra algorithm. The edited sequence is rather smooth.

In this thesis, an approach is presented for frame interpolation in TVM in high level, which is very challenging due to the absence of semantic information in mesh models. A semantic human model is employed to estimate the motion vectors of the object. The mid-frames are interpolated linearly by the estimated motion vectors. Our experimental results demonstrate the effectiveness of the approach. This technique can be applied in many areas such as frame rate up-conversion and motion blending, and can support the motion analysis in high level.

The proposed algorithms in this thesis are key techniques in managing and re-usage of TVM data, which involve not only low level processing but also high level processing in mesh models.

Jianfeng Xu, June 18, 2007

本論文は「Time-Varying Mesh Processing for Segmentation, Summarization, Interpolation and Composition (3次元ビデオ処理:分節化,要約,補間,編集)」と題し,英文で書かれており,7章よりなる.3次元ビデオとは,時間的に変化する3次元メッシュ系列であり,動く実物体を対象に多数カメラで取得した映像から生成する.そのメッシュの頂点数,トポロジーも動的に変化するため,本論文ではTVM (Time Varying Mesh)と称している.TVMは,人物などの動きや形状を3次元で取得し,その再生においては,ユーザの視点を自由に変えることができ,新しい映像メディアとしての期待が高まっている.従来よりTVMの取得法を中心とした研究が進められてきた.これに対して,本論文は,その利活用のための処理手法(分節化,要約,補間,編集)という新しい課題に着目し,それぞれの技術的な提案を論じたものである.

第1章は,「Introduction(序論)」であり,研究の目的,背景,本論文の構成について述べている.

第2章は,「Similarity Measures in Time-Varying Mesh(TVMの類似尺度)」と題し,3次元のメッシュ系列のフレームごとの類似尺度について論じている.この類似尺度は,分節,要約,編集などの処理にて重要な役割を果たす.類似尺度として,距離ヒストグラム,極座標ヒストグラム,相互情報量の提案を行い,その比較評価実験を行っている.計算量と性能のトレードオフを評価し,極座標ヒストグラムを特徴量として以降の章において用いている.

第3章は,「Motion Segmentation(動きの分節化)」と題し,TVMのメッシュ系列をその動きの類似性による分節化について論じている.分節化により人物の舞踊などの一連の動きを適切な単位で切り分けまとめることができる.極座標ヒストグラムに基づく特徴量の時間的な変化に対して,突発的な変化と緩やかな変化の検出を行った.その評価としては,実験データに対して,8人の評価者による主観的な文節位置を求め,ばらつきを考慮して,正解の分節位置を導出し,提案手法の評価を行った.適合率と再現率の調和平均であるF-measureにて,0.85と良好な結果を得ている.さらに,歩行動作など周期的な動きの検出についても検討を行い,繰り返す動きの単位の検出についても論じている.時間方向に階層的な処理を行い,極座標ヒストグラム変化を一定時間でまとめたMotion Atomを定義し,繰り返す動きの単位であるMotion Textonを検出し,そのつながりをMotion Clusterとして検出している.

第4章は,「Key Frame Extraction(キーフレーム抽出)」と題し,TVM系列の要約のためのキーフレーム抽出について論じている.キーフレーム抽出においては,最適なキーフレーム数を求めるとともに最適なキーフレーム位置の決定を行う必要がある.それらは,動きの大小に応じて,異なる値をとらねばならない.本論文では,レート歪のトレードオフ関係を利用し,その最適化を行う手法を提案した.レートは分節区間におけるキーフレーム数,歪がその位置により定まる累積的な誤差とモデル化した.レートと歪によるコスト関数の最小化を行い,最適値を求めている.なお,線形近似を導入することで,解析的に最適値を求めることができることを示した.複数の系列に対する評価を行い,合理的な結果を得ることができた.

第5章は,「Motion Editing(動きの編集)」と題し,動きを考慮したTVMの編集合成手法について論じている.これにより,既存のTVM系列を用いて新しい系列を生成することができる.3章で導いた周期的な動き単位であるMotion TextonをベースとしたMotion Graphを利用する.指定したフレームから探索を始め,十分なめらかに最適な箇所で異なるMotion Textonへ遷移するための手法を導き,実験により評価を行っている.

第6章は,「Motion-Compensated Frame Interpolation(動き補償フレーム補間)」と題し,フレームレートを変化させるためのTVMの補間を論じている.本論文では,頭部,胴体,腕,足に応じて,10区分の接続構造を仮定し,TVMの表現する人の動きを区分ごとに推定する.初期区分はユーザが与え,以降のフレームにおいては,自動的に区分を剛体とみなした動きの推定を行う.さらに,その推定した動きに基づき,メッシュを変形させ,補間を行い,TVM系列のフレームレート向上の実験で評価を行っている.

第7章は,「Summary of Thesis(論文のまとめ)」であり,本論文での成果をまとめるとともに,今後の課題について言及している.

以上これを要するに,本論文では,新しい映像メディアとして期待される3次元ビデオに対し,その利活用につながる処理技術として必要とされる,分節化,要約,補間,編集という新しい課題に対しての提案,検証を行ったものであり,画像工学上貢献するところが少なくない.よって,本論文は博士(工学)の学位論文として合格と認められる.