3 次元パッキングを用いた
マルチメディアプレゼンテーションのシナリオ生成


ビデオや音声，画像などのマルチメディアデー タを扱ったマルチメディアプレゼンテーションを生成するには，マルチメディアデー タの再生を開始するタイミングを決定するスケジューリングと，画面上のどこに 配置するかを決めるレイアウト問題の 2 つの問題を解決することが不可欠である． プレゼンテーションの作成者が，スケジューリングとレイアウトをすべて考慮し ながら作成するは困難である．したがって，本研究では，作成者にはマルチメディ アデータ間の部分的な時間関係だけを記述させて，スケジューリングとレイアウ トは自動的に行い，マルチメディアデータの時空間の配置を決定したシナリオを 生成することを目的とする．

本研究では，スケジューリングとパッキングを 3 次元パッキングによって行う． 一つのマルチメディアデータを，3 次元の中を移動する一つの直方体として考 えることで，スケジューリングとレイアウトを同時に行える． しかしながら，3 次元パッキング問題は NP 困難な組み合わせ最適化問題で あるため，本研究では，できるだけ多くの制約を満たすような組み合わせを最適 解とする最適化問題として，SA 法を用いて探索した．近似解でも，おおよそ意味 の成り立つシナリオを，実用的な時間内で生成できることを確かめた．