Comments
Description
Transcript
輪郭線に着目したカンターモーフィングに 関する研究
2005 年度修士論文 輪郭線に着目したカンターモーフィングに 関する研究 指導教授 藤吉 弘亘, 岩堀 祐之 中部大学大学院 情報工学専攻 工学研究科 博士前期課程 高畠 綾子 修士論文題目 輪郭線に着目したカンターモーフィングに 関する研究 情報工学専攻 氏名 高畠 綾子 論文要旨 近年，アニメーションを作成する作業工程中最も手間のかか る動画作成を，モーフィング技法を用いて自動生成する研究 が行われている．モーフィングによる中割り (中間) 画像の自 動生成は，動画マンが一枚一枚動画を描く負担の軽減に期待 されている．また，アニメーション以外にメディカルビジュア ライゼーション等の医療分野や CAD アニメーションにおいて， 中間画像生成手法は応用されている．しかし，既存の手法で は，形状の特徴を表すヒントやパラメータを与える必要があ るため，手動による手間や，付ける人による指定誤差が生じ る．そこで，形状のヒントを人が与えなくとも輪郭形状同士 の対応を求め，自動的に中間形状を生成する手法を本論文で 提案する．与えられたソース形状 (“始め” の原画) をターゲッ ト形状 (“終わり” の原画) に対して，本手法ではデータの始点 を固定しない端点固定 DP マッチングを用い，任意パターン長 データのみを 2 周分用意することで始点の対応位置に関する問 題を解決する．さらに，輪郭形状の多解像度化形状を利用する ことで，安定した対応付けを行うことができるように工夫して いる．バックトレースにより最適な対応を求め，得られた対応 点から中間値を生成することで，全自動による輪郭のモーフィ ングが実現可能となることを示す．また，生成した中間形状を 被験者による評価から，提案手法はより望ましい中間形状を 出力できることを確認した． 目次 第 1 章 まえがき 1.1 本論文の流れ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第 2 章 中間 (中割り) 形状生成 2.1 1 1 3 アニメーション作成作業とその問題点 . . . . . . . . . . . . . . . . . . . . 3 作画作業にかかる手間 . . . . . . . . . . . . . . . . . . . . . . . . . アニメーション作成アプリケーションとその問題点 . . . . . . . . . 3 5 中間形状生成手法を含む関連研究とその問題点 . . . . . . . . . . . . . . . . 6 輪郭形状生成に関する研究 . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 2.2.2 Flash アプリケーション . . . . . . . . . . . . . . . . . . . . . . . . 問題点のまとめとその改善策 . . . . . . . . . . . . . . . . . . . . . . . . . 8 8 2.4 本研究の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 2.1.2 2.2 2.2.1 第 3 章 カンターモーフィング 3.1 3.2 11 カンターモーフィング処理手順 . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.1 ベクトルデータからラスタデータヘの離散化 . . . . . . . . . . . . . 11 3.1.2 輪郭の一次元化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.1.3 端点固定 DP マッチング . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.4 中間形状の生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Contour Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.1 Contour Flow の例 . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.2 複雑な形状における Contour Flow . . . . . . . . . . . . . . . . . . 19 第 4 章 今後の改善策 4.1 21 対応付けがとれない場合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 カンターモーフィング . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 ガウス分布を利用した輪郭形状の平滑化と特徴点の算出 . . . . . . . . . . . 23 4.3.1 4.3.2 平滑化された形状同士をその特徴点で一次元化 4.3.3 ガウス分布 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 . . . . . . . . . . . 24 畳み込み演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 v 4.4 分割点の決定方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4.1 分割方法による比較 . . . . . . . . . . . . . . . . . . . . . . . . . . 28 第 5 章 輪郭線上の特徴点抽出 5.1 31 輪郭線上の特徴点検出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1.1 検出画像に対する前処理 . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1.2 輪郭上の特徴点検出 . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.1.3 スター型スケルトンの利点 . . . . . . . . . . . . . . . . . . . . . . 35 第 6 章 評価実験 6.1 39 アンケートによる評価実験 . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2 評価の結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 第 7 章 まとめ 7.1 43 今後の課題と展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 謝 辞 45 参考文献 47 発表業績一覧 51 vi 図目次 2.1 2.2 アニメーション制作工程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 中割り描画例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 2.3 デジタル化されたアニメーション制作工程 . . . . . . . . . . . . . . . . . . 5 2.4 輪郭線形状サンプル 8 3.1 カンターモーフィングの処理手順 . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 ベジェ曲線の離散化 3.3 輪郭線情報の一次元化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 DP パス . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5 バックトレース . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.6 バックトレース適用例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.7 中間形状生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.8 3.9 Contour Flow 表示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 剛体・非剛体移動時のフロー表示例 . . . . . . . . . . . . . . . . . . . . . . 20 4.1 4.2 対応付け失敗例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 カンターモーフィングの処理手順 . . . . . . . . . . . . . . . . . . . . . . . 24 4.4 分散値 σ の変化によるガウス分布の表示 . . . . . . . . . . . . . . . . . . . 25 4.5 4.6 σ を変化させた際のサンプル . . . . . . . . . . . . . . . . . . . . . . . . . . 26 畳み込み演算計算例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.7 畳み込み用カーネルの範囲指定 . . . . . . . . . . . . . . . . . . . . . . . . 28 4.8 生成された中間形状の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.1 画素の探索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 輪郭の追跡 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3 拡散縮小処理によるノイズ削除 . . . . . . . . . . . . . . . . . . . . . . . . 34 5.4 5.5 スター型スケルトンによる特徴点の抽出処理の流れ . . . . . . . . . . . . . 35 5.6 スター型スケルトンの抽出例 座標をもとのデータに還元 . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 遮断周波数の変化に対する特徴点 . . . . . . . . . . . . . . . . . . . . . . . 36 . . . . . . . . . . . . . . . . . . . . . . . . . 37 vii 6.1 被験者へのアンケート例 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.2 被験者へのアンケート例 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.3 中間形状に対する評価結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 viii 表目次 2.1 手法特徴比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 フローの方向分布の分散. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.1 ガウス分散値 σ と形状の複雑度の関係 ix 7 . . . . . . . . . . . . . . . . . . . . 26 第1章 まえがき 近年，アニメーションを作成する作業工程中最も手間のかかる動画作成を，モーフィン グ技法を用いて自動生成する研究が行われている [1]，[2]．モーフィングによる中割り (中 間) 画像の自動生成は，動画マンが一枚一枚動画を描く負担の軽減に期待されている．ま た，アニメーション以外にメディカルビジュアライゼーション等の医療分野や CAD アニ メーションにおいて，中間画像生成手法は応用されている．しかし，既存の手法では，形 状の特徴を表すヒントやパラメータを与える必要があるため，手動による手間や，付ける 人による指定誤差が生じる．そこで，形状のヒントを人が与えなくとも輪郭形状同士の対 応を求め，自動的に中間形状を生成する手法を本論文で提案する．提案手法により得られ た中間形状は，既存の手法により得られた中間形状と比較し，その有効性を確認する． 1.1 本論文の流れ 本論文は第二章に研究の背景であるアニメーション製作現場の問題，ならびに既存の中 間形状生成手法の問題点について述べている．第三章において，二章に挙げた問題点を 解決する手法を提案する．第四章では，三章で説明しきれなかった輪郭線の特徴点抽出方 法について記載する．提案手法は第五章にて，評価実験を行った結果をまとめている．ま た，今後更なる対応付けの改善に向けて行う予定の理論をまとめている．第六章は本論文 のむすびが記載され，それ以降は本研究に携われた方々への謝辞，参考にした文献，学外 発表の資料が続けて掲載されている． 1 第2章 中間 (中割り) 形状生成 2.1 アニメーション作成作業とその問題点 日本アニメーションは世界に誇れるメディアコンテンツとして，近年国内でもようやく 注目されはじめた．ジャパニメーションとも呼ばれる日本制アニメーションの需要は高ま り続ける一方である．しかし，その影響を受けた製作現場では，スタッフが身を削ってア ニメーションを製作し続けているという現実がある． 専門学校だけではなく，今では大学機関もアニメーション制作に携わる者の育成に力を 入れ始めているが，低賃金で待遇が悪いという現状から，かけだしの修行期間ともいえる 動画マンのうちに仕事を辞める者も多い．そのため海外に作業を廻さなければ，製作が追 いつかない人材不足の問題も生じている． 人材不足を補い，作業効率の向上や作業の軽減が期待されるとして，10 年前からアニ メーションの制作工程にもデジタル機器が導入された．制作工程のほとんどがデジタル化 される中，未だアナログ要素の強い作業が残されている．それは，アニメーションの顔で ある原画，動画の作成を担う作画工程である． 2.1.1 作画作業にかかる手間 アニメーションを作成する企画が興され，アニメーションが完成するまでの流れを図 2.1 に示す．企画に基づいてシナリオが作成され，演出家や絵コンテマンがシナリオに沿っ て絵を描き，効果音，撮影方法などが指示される．作画作業が始まるのはここからであ る．原画マンは絵コンテを元に登場人物の動きを考え，そのタイミングや動画の作画枚数 などを指示する．指示を受けた動画マンは，原画と原画との間をつなぐ絵を指示された枚 数分描く．鉛筆で描かれた原画と動画は後にトレスされ，着色される．美術スタッフが作 成する背景とともに撮影し，編集作業にはいる．効果音，BGM，声優によるアフレコ等 の録音作業を経てアニメーションは完成する． アニメーション製作は原画が描かれなければ，ただの企画で終わってしまう．一秒間に テレビ放映レベルで 24 枚 (24fps) のコマを作成するためには，原画，ならびに原画の中 割り (中間) となる動画を作成する必要がある．一枚一枚を手で描くだけではなく，図 2.2 に示す様な “始め” と “終わり” に指定された原画の中割り (中間の絵柄) を想像し，シー 3 図 2.1: アニメーション制作工程 ン全体の流れを次に繋げなければならない作業が含まれる．元となる絵であるからこそ， そしてその枚数が膨大であるからこそ製作現場の作業としての問題が生じる． 図 2.2: 中割り描画例 多くの作画スタッフは，これら原画や動画を一枚一枚所定の用紙に鉛筆で描き込んで いく．絵コンテに従い，己の中でレイアウトを決めて原画を描く作業と，その原画の中間 を描く作業と，共に創造性が極めて高い．それ故に作業の効率化が難しいのである．500 から 1000 枚の動画を一月描ければ，プロの動画マンとして活躍していると言える．動画 一枚につき 24 分の 1 秒が確保出来ると仮定した場合，一人の作業量は 1 分にも満たない． それほど作業量も多い工程なのである． デジタル化に伴い，作画以降の作業は大幅な作業軽減が実現している．特殊効果の適用 4 も加わり，見た目と品質の向上にも繋がった．しかしその土台は，多くの動画マンがそれ ぞれの技術で凌いでいる現状がある．作画作業の軽減に繋がるものは無いのか，デジタル 化された製作現場の流れを見ながら，まとめていく． 2.1.2 アニメーション作成アプリケーションとその問題点 厳しい環境下で仕事をこなすアニメーションの作画スタッフの多くが利用しているアプ リケーションソフトがある．日本国内においては 9 割も業界に浸透している CELSYS 社 の RETAS! Pro シリーズ [3] や，Adobe Systems 社の After Effects[4] が 2D アニメーショ ンの製作現場においては有名である． 図 2.3: デジタル化されたアニメーション制作工程 1993 年に CELSYS 社の RETUS! Pro シリーズが発売されてから時は流れ，現在アニ メーション作成現場は図 2.3 の “現在” に示すように，そのほとんどがデジタル化された． また，2003 年より Macromedia 社 (現 Adobe Systems 社) の協力もあり，従来ラスタ形 式で作成され，Web 掲載用に作り直しや圧縮せざるを得なかったアニメーション配信作業 の負担が改善された．ラスタ形式の線画をベクトル形式に変換する方式が採用され，Flash で利用出来るアニメーションとして出力する機能が RETUS! Pro に追加されたのである． これにより，インターネットを経由した高品質アニメーションの配布も容易になり，更に 5 需要の増えるきっかけにもなった． しかし，この状態においてもデジタル化が難しいとされているのが図中の作画部分であ る．CELSYS 社はこの問題を，描画部分の機能をユーザが満足できるレベルに引き上げ ることで解決しようとしているが，紙媒体に慣れた人間にデジタルでの中割り作業は逆に 難しいのである．紙はめくればすぐに原画が見える．デジタル画面においても上層のレイ ヤーの透明度を変えたり，ハーフトーン化することで同様の効果を得ることは出来るが， 感覚的に異なるために馴染めないことが多く，結局は紙に描いてスキャンし，ゴミの除去 作業などで時間を使うことになる．また，コスト的な削減にも繋がりにくいとして，導入 できるプロダクションも限られてくる． 2002 年に CELSYS 社より，絵コンテの作成から着色までをフルデジタルかつベクター アニメーション製作が可能な RETAS! Pro STYLOS も発売されたが，発売から 3 年を経 過した今でも作画作業は一枚一枚描く者が多い．このように作画作業をフルデジタル化す るには，まだまだ問題が多い．しかし，大変手間のかかる作業をある程度自動化出来ない ものかと，今も手法が模索され続けている． 2.2 中間形状生成手法を含む関連研究とその問題点 その一方で，中間形状や画像を生成する研究が多く成されている．輪郭形状生成や画像 モーフィング，ワーピングと言った手法である．アニメーションの原画に描かれる主線は， 輪郭形状の様に線から成り立つことから，輪郭形状生成に焦点を当て，原画の中間形状描 画作業の軽減に利用出来ないかと考える． 中間形状の自動生成手法は，既に多くの研究報告がなされている．また，身近なアプリ ケーションとして Flash シェイプトゥイーンが Flash アニメーションを制作する際に広く 活用されている． 原画，動画は線分により構成されているため，輪郭線の中間生成が作画作業の軽減に繋 がるのではないかと考えられる．そこで，輪郭線形状に関する研究について調査を行った． 2.2.1 輪郭形状生成に関する研究 形状同士の対応付けや中間画像の生成に関する論文を見ていくと，その目的は大きく 二つに分かれている．一つは，純粋に中間画像を生成するために特徴点の対応を取るモー フィング手法に関する文献 [5], [6]，他方は，クラス分けをするために注目点の対応を取 る手法に関する文献である [7], [8], [9]．1975 年辺りから，形状の頂点同士を DP マッチ ングで対応づけさせることが，対応付けの定石となっている．DP マッチングは，異なる 二つの時系列信号の類似度と最適な対応を求める手法であり，音声の認識 [10] やステレオ マッチング [11]，カンターマッチング [12]- [15] など，様々な分野で利用されている． 6 今回調査した全文献は，対応付けの方法として DP マッチングを取り入れている．しか し，マッチングを取る一次元信号はそれぞれ特色があり，各手法の比較を表 2.1 にまとめ 考察する． 表 2.1: 手法特徴比較. 文献 1 文献 2,3 対応形状 閉曲線 閉曲線 DP 入力 応力とひずみの関係式を変形 曲線の凹凸を変曲点毎に記録 DP マップ NxM 2Nx2M 開始点の指定 要 不要 回転への対応 × ○ 文献 4 文献 5 対応形状 開閉曲線 閉曲線 DP 入力 曲線の凹凸を変曲点毎に記録 フーリエ変換の式を変形 DP マップ MxN or 2NxM MxM 開始点の指定 不要 不要 回転への対応 ○ ○ 非線形な時間正規化を用いたパターンマッチングである DP マッチングを利用すること で，局所的な形状の違いを吸収し，かつ大局的に対応を求めることができるため，先に述 べた様に多くの分野で利用されている． 初期の頃には端点固定の DP マッチングが利用されていたが [5]，端点固定の DP マッ チングでは，一次元化した際の開始位置が同じでない場合，正しい対応を得ることが出来 ない．その後，Ueda ら [7] の提案した 2N × 2M (横 x 縦) の DP マップ上で対応点を計算 する手法が 1993 年に発表されると，Milios ら [6] や Petrakis ら [8] のように応用や改良を 加えられた DP マッチング手法も用いられるようになった． DP マッチングを用いないで中間画像を生成する方法として，最近発表されたものとし ては Cong と Parvin は対象の輪郭と距離の変化からの内挿を提案している [16]．この手法 では，対象に対して滑かな輪郭の内挿を行うことができるが，計算コスト多大であるた め，アプリケーション等に用いるには実用的でない． また，アニメーションに焦点を当てたモーフィングの研究も行われているが，3D メッ シュを作成する時点で手描きを生かした描画では利用出来ず [1]，画像処理を繰り返し行 うことによるノイズや主線のかすれが生じる等 [2]，2D アニメーションの中間画像生成に 関してまだまだ課題は多い． 7 ■ 輪郭形状について 図 2.4: 輪郭線形状サンプル 通常，輪郭を取る場合，対象となる物体を塗りつぶした状態で輪郭形状を取るため，輪 郭線内に空間が発生することは無い．図 2.4(d) の状態である．アニメーションの動画を 自動的に描きたいと考える場合，直線と曲線の対応付け等，閉曲線だけでは中間形状の生 成に対応することは出来ない．閉直線，閉曲線だけではなく，区分された点を決定し，対 応付けを行い中間形状を計算し描画することを考える必要がある． 2.2.2 Flash アプリケーション 一方，インタラクティブな Web ページを作成する際に用いられる Adobe Systems 社 (旧 Macromedia 社)[17] の Flash では，輪郭のモーフィング手法としてシェイプトゥイーンと 呼ばれる手法が用いられている．これは，ベクトルデータの輪郭形状に対してモーフィン グを適用し，中間形状を出力することができる．しかし，シェイプトゥイーンの入力形 状が人等の複雑な形状である場合，輪郭線同士の正確な対応が求められないため，ユー ザが望む中間形状の生成が不可能となる場合が多い．そのため，Flash では補助機能とし て，ユーザが手動でシェイプヒントと呼ばれる輪郭線の特徴的な対応点を与えることで， ユーザの望む中間輪郭形状を生成することを可能としている．しかし，このような手動操 作で特徴点を与えることは手間であり，また，ユーザが与える対応は必ずしも最適な補助 の位置となるとは限らない．これらの問題を解決するには，全自動で正確な輪郭の対応を 求め，中間形状を生成する必要がある． 2.3 問題点のまとめとその改善策 既存の研究や市販のアプリケーションは，アニメーションとしての中間画像を生成する ことに重点を置いているわけでは無いが，その技術は大いに利用出来ると考えられる．特 に Flash は単純な形状同士の中間形状を自動生成する機能を既に実現している．しかし， 8 問題点となるのは単純な形状同士に限られるところである．ある程度複雑な形状同士の対 応は対応点をユーザが逐一設定することで実行できるが，それは手間でしかない． 物体の位置や大きさを数値的に変化させるモーショントゥイーンは 3D アニメーション で用いられているが，2D ではあまり用いられていない．Flash アニメーションではよく 利用される機能であるが，通常のアニメーションにおいてその動きは不自然と感じられる ことが多いためあまり利用されていない．これは技術者がデジタルアニメーション作成に 特化したシステムを提供できていないとともいえる． デジタル上で絵を描くことが出来る者が増えていること，フルデジタル化されたアニ メーションの出現，これらより今後はオリジナリティーのある作画工程として作業工程の 全てがデジタル化かつ，品質向上のためにベクター化されることが想定される． 2.4 本研究の目的 本研究ではそのような現場を想定し，形状の特徴を表しているヒントを与えること無く 輪郭形状の対応を求め，次いで，線分同士の対応を行い，アニメーションの動画の様な中 割り画像を生成することを視野に入れている．現段階ではまず，簡単なオブジェクト全体 の輪郭形状に対する中間形状を生成する手法について考える．与えられたソース形状 (“ 始め” の原画) をターゲット形状 (“終わり” の原画) に対して，本手法ではデータの始点を 固定しない端点固定 DP マッチングを用い，さらに，任意パターン長データのみを 2 周 分用意することで始点の対応位置に関する問題を解決する．輪郭特徴のデータが環状情報 であり，始点と終点が繋がることを利用するのである． バックトレースにより最適な対応を求め，得られた対応点から中間値を生成すること で，全自動による輪郭のモーフィングが実現可能となることを示し，また，生成した中間 形状を被験者による評価から，その有効性を示す． 9 第3章 カンターモーフィング 本章ではオブジェクト全体の形状に対する中間形状を生成する手法についてまとめる． 次節よりに提案するカンターモーフィングの手順とその理論を順次述べる．また，カン ターフロー生成の際に生じる対応点同士を繋ぐ線分の有効活用法についても簡単にまと める． 3.1 カンターモーフィング処理手順 カンターモーフィング手順を図 4.3 に示す． まず初めに，ベジエ曲線で描かれたベクトルデータの輪郭線をラスタ化する．予めラス タデータが入力としてきた場合には，そのままのデータを利用する． 入力されたデータの輪郭線を取得し，形状の重心から各輪郭点までの距離である一次 元信号に変換する．この方法について，詳しくは 5 章にて説明する．その後に端点固定の DP マッチングを用いて対応付けを行い，得られた輪郭線の対応から中間形状を生成する． 最後に，中間形状データをベクトルデータに戻す． 本手法で使用した輪郭線形上のサンプルは，交差しない閉曲線を対象としている．ま た，アニメーションを作成することを考慮しているため，極端にフレーム数を進めた場合 に相当する “変化の激しいモーフィング” は今回対象としていない． 3.1.1 ベクトルデータからラスタデータヘの離散化 ベジエ曲線は多くの描画系アプリケーションに用いられている描画形式である．輪郭線 を基にしたシェイプトゥイーンを行う初めのステップは，このベジエ曲線をラスタ化し， 離散点を求める．ベジエ曲線は次式で表わされる． x = (1 − t)3 x1 + 3(1 − t)2 tx2 + 3(1 − t)t2 x3 + t3 x4 y = (1 − t)3 y1 + 3(1 − t)2 ty2 + 3(1 − t)t2 y3 + t3 y4 (3.1) (0 ≤ t ≤ 1) (x1 , y1 ) は始点，(x2 , y2 ), (x3 , y3 ) は制御点，そして (x4 , y4 ) は終点である．ラスタ化された ベジエ曲線状の点 (x, y) は媒介変数 t により制御される．図 3.2 に示す様に，変数 t を変 11 図 3.1: カンターモーフィングの処理手順 化させた場合，座標のサンプリング間隔が変化する．変数 t が 0.1 である場合，ラスタ化 されたデータは 10 個となる．本研究では，t = 0.001 を用いる． 上述された方法より得られたラスタデータは，Freeman のチェーンコード [23] を利用 し，保持容量を抑えたプログラムにより記録される． 3.1.2 輪郭の一次元化 2 次元である輪郭形状の特徴量を重心からの距離である 1 次元データに変換する [21]． 対象の輪郭形状の重心点を (xc , yc )，I を輪郭点の数，(xi , yi ) を i 番目の輪郭点座標とする． このとき，各輪郭点から重心までのユークリッド距離 d(i) は次式より求められる． q d(i) = (xi − xc )2 + (yi − yc )2 (3.2) 図 3.3 に，1 次元化した二つの輪郭形状例を示す．モーフィングに使用するソースパター 12 図 3.2: ベジェ曲線の離散化 ンの輪郭点を i，ターゲットパターンの輪郭点を j とする． 図 3.3: 輪郭線情報の一次元化 3.1.3 端点固定 DP マッチング DP マッチングは，異なる二つの時系列信号の類似度と最適な対応を求める手法であり， 音声の認識 [10] やステレオマッチング [11]，カンターマッチング [12]-[15] など，様々な分 野で利用されている．これは，非線形な時間正規化を用いたパターンマッチングである 13 DP マッチングを利用することで，局所的な形状の違いを吸収し，かつ大局的に対応を求 めることができるため多くの分野で利用されている． 端点固定の DP マッチングでは，一次元化した際の開始位置が同じでない場合，正しい 対応を得ることが出来ない．また，対応させる各データをつなぎ合わせる手法を用いた場 合，最も類似度が低くなる開始点を決定するための計算プロセスが必要となるため計算コ ストが余分にかかる等の問題がある． そこで，本手法ではデータの始点を片方固定した端点固定 DP マッチングを用い，さら に，任意パターン長データのみを 2 周分用意することで始点の対応位置に関する問題を解 決する．輪郭特徴のデータが環状情報であり，始点 ds (0) と終点 ds (I) で繋がることを利 用するのである． 以下に，端点固定 DP マッチングの適用法について示す． 図 3.4: DP パス ■ 初期設定 i を任意長パターンデータ (ソースデータ)，j を固定長パターンデータ (ターゲットデー タ) としたとき，式 (3.3) に示すような初期値を設定する． g(i, 0) = 0 g(0, j) = ∞ (i = 0, 1, . . . , 2I) (j = 1, 2, . . . , J) (3.3) ただし，I を任意パターン長データの輪郭周囲長，J を固定パターン長データの輪郭周 囲長とする．g(i, 0) は，始端点フリーとするために 0 に初期化する．g(0, j) は，固定パター ン長データである dt の周囲長未満のデータが最適な対応であると判断しないよう，予め 大きな重みを与えて DP パスが選択されないように制限する． 14 ■ DP 値の計算 端点固定 DP マッチングに用いる DP パスを図 3.4 に示す．各格子点 (i, j) における累積 距離 g(i, j) を次式より求める． g(i,j)=min g(i−1,j−2)+2·ld(i,j−1) :(a) g(i−1,j−1)+ld(i,j) :(b) g(i−2,j−1)+2·ld(i−1,j) :(c) +ld(i,j). (3.4) 式 (3.4) は，図 3.4(a) に示す対称的な 3 つのパスから最も輪郭特徴が似ているパスを選 択する．このとき，選択されたパスに対応したラベル (a), (b), (c) をバックトレースの際 に用いるため保存しておく． ローカルディスタンス ld(i, j) は式 (3.5) より求める．輪郭特徴である ds (i), dt (j) の差の 2 乗を算出するため，輪郭特徴が似ていないほど急激に値が大きくなり，パスとして選択 されなくなる． ld(i, j) = (ds (i) − dt (j))2 (3.5) 格子点 (i, j) までに選択された経路の長さを式 (3.6) より求める． c(i − 1, j − 2) + 3 if (a) c(i, j) = c(i − 1, j − 1) + 2 if (b) c(i − 2, j − 1) + 3 (3.6) if (c) 以上の操作を各格子点にて行い，式 (3.7) より累積距離をそれまで辿った経路の長さで正 規化する． G(i, J) = g(i, J) c(i, J) (3.7) ■ バックトレース DP マッチングの後，最適な対応を算出するためバックトレースを行う．式 (3.8) より 求めた正規化距離 G(i, J) の中で最も小さな値となる i0 を開始点として選択する． i0 = argmin(J/2≤i≤2I) G(i, J) (3.8) バックトレースの開始点は図 3.5 のように，傾斜制限を設けているため (J/2 ≤ i ≤ 2I) 間で決定する．開始点が決定した後，最適ルートを式 (3.4) で記憶されたラベル a, b, c に 15 従い各ノードをバックトレースする．このプロセスを終点 (j = 0) になるまで繰り返し 行う． バックトレースにより得られた最適ルートは，各輪郭線上の対応を示すことになる． 図 3.5: バックトレース 図 3.6 に，バックトレースと算出された最適ルートにより対応付けされた輪郭線上の データの一例を示す．図 3.6 より，最適ルートがソースとターゲットの各輪郭点の対応を 表していることが分かる． ただし，形状によっては，たまたま累積距離の値が，小さくなる箇所からバックトレー スが開始され，対応付けが出来ないケースもある．この判断の見定め方は，累積距離をプ ロットした際に，小さくなる値がどこにあるかを見極めることである．開始場所により， 対応付けできない箇所が続き，データ長が間延びする．対象とする本来の周囲長よりも データ長が長い場合は，次に勾配的に累積距離が小さくなる箇所をバックトレース開始位 置として周囲長の判断を行う必要がある． 3.1.4 中間形状の生成 2 章で示した提案手法を用いて，ソース形状とターゲット形状の輪郭線対応が決定され た後，次式により内挿後の座標 (x0 , y 0 ) を求める． x0 = (1 − α)xs + αxt y 0 = (1 − α)ys + αyt (3.9) 0<α<1 (xs ，ys ) はソース形状の輪郭，(xt , yt ) はターゲット形状に対応した各座標である．α は内 16 図 3.6: バックトレース適用例 挿するスケールを決定するパラメータである．内挿点が決定した後に，他アプリケーショ ンでの利用が可能となるよう，ベクトル化 (ベジエ曲線化) を行う [22]． 図 3.7 に α を 0.25, 0.50, 0.75 と変化させた際に，提案手法と Flash シェイプトゥイーン を用いて生成した中間形状の例を示す．Flash シェイプトゥイーンは，複雑な図形の場合 ユーザからの特徴点を指定しなければユーザの望む形状に変化出来ない．このような特 徴点は，適宜ユーザが試行錯誤してポイント数やその位置を決定していく必要がある．図 3.7 より，シェイプヒントが無い場合では足の中間形状がつま先まで正しく生成されてい ないことが見て取れる．また，円で示した足のつま先部分について比較すると，提案手法 は人等の複雑な形状に対して，ソースとターゲット形状に含まれる特徴を残した中間形状 をシェイプヒント無しに生成可能であることが分かる． 17 図 3.7: 中間形状生成 3.2 Contour Flow 輪郭形状同士の対応を求めるために，各輪郭形状を 1 次元データへ変換し，端点固定 DP マッチングを用いて輪郭点の対応を求める．このとき，各輪郭線上にある点同士の対 応を Contour Flow と呼び，中間形状生成の際に使用する． この Contour Flow は，物体の移動の様を示す線として移動体の移動前，移動後に向け て生成される．通常，フロート呼ばれるものは画像処理において，移動体検出に利用され る．これと同様の働きをカンターフローも行うことが出来るのではないかと考えられるた め，実際の画像を利用したカンターフローの生成も行った，その結果を次節より示す． 18 3.2.1 Contour Flow の例 プリミティブな形状を平行移動，回転，拡大縮小，変形した際の対応から得られる Con- tour Flow を図 3.8 に示す． 図 3.8: Contour Flow 表示例 図 3.8 より，各頂点が変形後の頂点と正しい対応を得られていることがわかる．このよ うな，輪郭線のみからフローを求められる利点として，画像のテクスチャが必要でないこ と，フローの計算に SAD 等の計算が必要でないため高速化が期待できる． 3.2.2 複雑な形状における Contour Flow 複雑な形状パターンとして，端点固定カメラに対して横方向に移動する歩行者と走行 車のシーケンスを利用する．歩行者と走行車のビデオより選択された 20 シーケンスに対 し，背景差分により移動体領域を検出し，その後得られた輪郭線より，Contour Flow を 計算した．図 3.9 にその結果を示す． 歩行者の場合，腕や足が前後に動くため，図 3.9(a) に示すフローの方向ヒストグラムか ら，フローの方向は一定に定まらないことが分かる．一方の走行車の場合は，剛体である ゆえに一定方向のフローが観測された (図 3.9(b) 参照)．これらより，輪郭線上のフロー は剛体 (自動車) と非剛体 (人間) の判別に用いる一つの特徴量として利用可能であるとい える． 表 3.1: フローの方向分布の分散. クラス 歩行者 走行車 平均 3731.82 19 39.01 図 3.9: 剛体・非剛体移動時のフロー表示例 表 3.1 に，剛体・非剛体の各 10 シーケンスより求めた，フローの方向分布の分散を示 す．これより，提案手法により得られるフローから剛体・非剛体を判別することが容易で あることから，輪郭線上のフローが正確に求められていることがわかる． 20 第4章 今後の改善策 中間形状生成実験を行った際に，対応付けがとれない場合も現在存在する．本章ではそ のように対応付けのとれなかった形状について確認し，その対策を検討する． 4.1 対応付けがとれない場合 本手法を用いて対応付けが出来ない場合について，その原因は DP マッチングを用いて いることにある．異なる長さを持つ輪郭線をカンターマッチングする際，その長さが 2 倍 上，もしくは 1/2 以下であると，DP パスの傾斜制限から正確な対応が取れない．そのた め，対応付けを開始する位置である累積距離の最小値が好ましくない位置を示し, そこか らバックトレースで対応付けされてしまうのである． 図 4.1 に対応付け失敗時の累積距離値の推移，DP マップ上での対応付け，対応付けさ れた周囲長を示す．バックトレース開始位置が，本来あるべき中心部，又は終了部より半 周分ずれていることが見て取れる．本来の周囲長分の対応付けがとれているターゲット形 状に対し，ソース形状は半分しか対応付けされていない．それ故に対応がとれない事態と なる． この主な原因は，元から形状同士の類似度が低いために生じる．故に，周囲長の過不足 を補う形での対応付けを円滑に行う方法について検討する必要がある． 4.2 カンターモーフィング 形状が異なる故に周囲長も異なる．この 2 点が対応付けに失敗する場合の原因となる． 周囲長の過不足を補いながら，大局的に DP マッチングの対応が行き届くように，対応付 けさせる方法を提案する． まずは元の輪郭線形状をガウス分布の畳み込み演算を用いて平滑化する．ガウス分布を 用いて平滑化を行うことで，ノイズの緩和と，周囲長の複雑さを軽減し，周囲長の特徴を 消さない状態でその長さを減らすことが出来る．平滑化の度合いを変化させ，総当たりの 対応付けを行い，類似度が高く，対応付け出来た周囲長が平滑化した形状に近いもの同士 を参考とする平滑化度合いの組み合わせとする． 21 図 4.1: 対応付け失敗例 22 その組み合わせのうち，ソース形状の一次元信号を算出し，特徴点を決定する．対応づ けられたターゲット形状の特徴点記録し，図 4.2 後の分割点とするべく特徴点の座標を元 のデータに還元し，特徴点間の線分同士を DP マッチングで対応付けさせる．その後，得 られた対応から中間形状を生成する．一連の流れを図 4.3 に示す． 図 4.2: 座標をもとのデータに還元 4.3 ガウス分布を利用した輪郭形状の平滑化と特徴点の算出 予め，周囲長のノイズ緩和と，対応付けの目安となる粗い対応点を，ガウス分布を用い た畳み込みで平滑化された形状にて決定する．その後に，一次元化されたデータの変曲点 をもとの形状に移すことで，分割ポイントを決定する．分割された長さ同士を対応づけさ せることで，極端な間延びや短い間隔の対応付けを防止することができる． この算出は，元の形状データにガウス分布の畳み込み演算を行うことで得られる形状 と，その形状における変曲点を求める式から成り立つ．ガウス分布を決定するパラメータ σ を順次プログラム内で自動的に変化させることにより，自動的に形状の平滑化を行う． 23 図 4.3: カンターモーフィングの処理手順 4.3.1 平滑化された形状同士をその特徴点で一次元化 輪郭線上にある全ての点は，式 (4.1) に示す 2 つの周期関数により表すことができると いう仮定に基づき，計算していく． C(t) = (x(t), y(t)). (4.1) 変数 t は特定の点から輪郭形状の周囲を測る様に番号付けされている． 上の仮定のもと， X(t, σ) は x(t) と一次ガウス分布 g(t, σ) の畳み込みとして, Y (t, σ) は y(t) と一次ガウス 分布 g(t, σ) の畳み込みとして，式 (4.2, 4.3 ) により定義する． X(t, σ) = x(t) ⊗ g(t, σ) Z +∞ 1 2 2 = x(u) q e−(t−u) /2σ du, −∞ σ 2π Y (t, σ) = y(t) ⊗ g(t, σ) 24 (4.2) = Z +∞ −∞ 1 2 2 y(u) q e−(t−u) /2σ du. σ 2π (4.3) 与えられた輪郭形状は図 4.5 の様にガウス分布により平滑化され，パラメータ σ が大き くなればなるほど，図 4.4 の様にガウス分布の中心幅は広くなるため滑らかな曲線が描か れる．これの畳み込みにより，輪郭形状は丸みを帯びて行く． 図 4.4: 分散値 σ の変化によるガウス分布の表示 4.3.2 畳み込み演算 畳み込みを行うことで，入力ファイルの全ピクセルに対し，そのピクセルを中心とした ピクセル群 (図の場合 3x3) と，カーネルの係数との掛け合わせを行い出力を得ることが出 来る．これにより重みづけられた値を算出することが出来る．画像処理のフィルタを例に 考えてみると，二次元の畳み込み演算は図 4.6 の様になる．フィルタの基本となるカーネ ルにより画像処理が異なる仕組みである．この丸みを帯びた輪郭点同士で先ずは粗いマッ チングを行う．マッチングには端点固定の DP マッチングを用い，そのデータとしては， 変形後の形状における重心からの距離とする．その後，更にガウス分布のパラメータ σ を 変えた場合のデータを用いて繰り返し以下の処理を行う．(1) 各特徴点間の輪郭線データ 25 の一次元化，(2) 各特徴点間の端点固定の DP マッチング，(3) バックトレースを利用した 輪郭点対応付け． 予め，周囲長のノイズ緩和と，対応付けの目安となる粗い対応点を決定する．パラメー タ σ を変化させ，丸みを帯びた形状を数パターン用意する．一次元化された周囲長の変曲 点を求めることで形状を分割し，分割された元形状の長さ同士を対応づけさせることで， 極端な間延びや短い間隔の対応付けを防止することができる．分割された領域同士で何度 か対応付けを行い，必要であれば更に細かな分割を生じさせる．最終的にはある程度の長 さ (今後実験と検討予定) に分割する必要があると考えられる． 図 4.5 に描かれた橙色の曲線の様に，分散値である σ を大きな値とすれば輪郭形状は丸 みを帯び滑らかになり，逆に小さな値 (0 より大きい値) とすれば細かな形状へと規則的に 変形する．また，形状の複雑度と σ との関係を式 4.1 にまとめる．表より，σ の値が大き くなるほどその複雑度は最小の値に近づく． 複雑度の最小の値は理論上 4π となるが，形状の解像度により計算に必要な周囲長と面 積が異なるため，320x240px 程度のキャンバスに真円の輪郭線を描いても，真値 4π を得 ることは出来ない． 元形状 σ = 1 .0 σ = 5 .0 σ = 3.0 σ = 1 0.0 σ = 2 0.0 図 4.5: σ を変化させた際のサンプル 表 4.1: ガウス分散値 σ と形状の複雑度の関係 元形状 σ=1 σ=3 σ=5 σ=10 σ=20 周囲長 363 複雑度 48.214 357 349 339 310 272 40383 38.182 35.934 32.843 29.953 今回利用しようとしているのは，一次元のデータ長である．従って，ガウス分布を利用 して一次元のカーネルを出力し，そこから各ピクセルごとの出力を得るアルゴリズムを作 成する．次に，ガウス分布の特徴や性質について簡単にまとめる． 26 図 4.6: 畳み込み演算計算例 4.3.3 ガウス分布 ガウス分布は自然界に生じる現象が起こる確率を表す確率群としてよく知られている． 無限に広がるその値をいつまでも計算することは容易ではない．そこで，確率的にガウス 分布の面積を求めることを考え，畳み込みの際に利用する範囲を決定する． f (x) = 1 q e−(t−u) 2 /2σ 2 . (4.4) σ 2π 通常，式 (4.4) において，σ で分布幅が決定されている時に，±3σ あればガウス分布によ り得られる分布面積の内 99.73% は算出することが出来る．また，5σ あれば 99.999427% もの面積を算出することが可能とされている．図 4.7 より，算出出来る面積を見て取るこ とが出来る．数値処理的にシビアな計算は行わないため，計算コスト的に処理の少なくな る 3σ を本研究においては利用する． 4.4 分割点の決定方法 分割点となる特徴点の決定方法が多々あるため，これよりその特徴点の求め方について 考察する． 今回は平滑化された形状の一次元化形状より，ゼロ交差法を用いた変曲点を特徴点とす る方法と，等間隔に特徴点を取る方法とを取り上げ比較する． 27 図 4.7: 畳み込み用カーネルの範囲指定 4.4.1 分割方法による比較 図 4.8 に，対応付けの得られた平滑化形状の一次元化データの分割方法を変え，中間形 状を生成した結果を示す． 図より，変曲点を利用して分割を行った場合，足のつま先等，対応付けを取りたい箇所 の形状が壊れずに中間形状を生成している．等間隔に分割しただけでは，特徴となる点同 士の対応がカンターモーフィングで取られていても，その対応が後からの対応で壊されて しまうために，つま先の形状が変形してしまっているものと考えられる． しかし，変曲点を分割に用いた場合においても，元々のかかとの形が変形していること より，対応付けには細い特徴点を付ける必要があると考えられる． 次に，特徴点をおく個数について考察する．分割点のおおい方が，細かな対応が得られ てよいと考えられるが，実際に生成された形状を見てみると，細かすぎて逆に DP での対 応付けが出来る範囲を超えてしまうことが多々あった．現在データ数を正規化することに より対応づけさせているが，あまりにも多い特徴点の算出も問題になると考えられる． 28 \ [ X ^ [ Q b g u6 “ \ [ X ^ [ Q b g u4 “ \ [ X ^ [ Q b g 図 4.8: 生成された中間形状の比較 29 第5章 輪郭線上の特徴点抽出 5.1 輪郭線上の特徴点検出 異なる長さを持つ輪郭線をカンターマッチングする際，その長さが 2 倍上，もしくは 1/2 以下であると，DP パスの傾斜制限から正確な対応が取れないという問題がある．そ こで，輪郭線を点群として捉え，Curvature Scale Space を用いて輪郭の解像度を上げる ことにより，大局的なマッチングを実現する．以下にその手順を示す． 1. ガウス分布による輪郭線の平滑化 2. カンターマッチングによる対応計算（大局的） 3. 輪郭線の分割 4. カンターマッチングによる対応計算（局所的） 大局的な対応から，輪郭線を部分的に局所探索を行う．その際に，輪郭線を分割するた めに，平滑後の輪郭線上の特徴点を求める必要がある． 5.1.1 検出画像に対する前処理 本研究では，イラストレータが作成する線図形を対象としているが，撮影した画像から 抽出した輪郭線に対しても，カンターモーフィングにの適用が可能でる．しかし，一般に 物体検出の段階で，対象とするピクセル群を全て正確に検出するのは不可能である．ま た，NTSC カメラを使用して撮影した際，デジタル画像への量子化する過程において，イ ンターレースノイズの影響により，誤ったピクセルを誤検出する場合がある．そこで，移 動体検出後の領域に対して，空間的なフィルタリング処理を行い， ノイズ除去を行う． 以下にその手順を示す． まず，検出領域に対して，拡散 (dilation) と縮小 (erosion) 処理を下記のアルゴリズムに より施す． ■拡散縮小処理アルゴリズム 画像中の図形のノイズを除去する目的で行われる処理に，拡散・縮小がある．これは，図 形を外側に 1 画素分広げたり，1 画素分細かくする処理であり，ノイズの影響により図形 31 に 1 画素の穴があいたり，ヒゲのような突起ができたときに，拡散・縮小を組み合わせる ことにより除去することができる． 拡散 背景または穴に接する対象の画素に，画素をひとまわり加える処理を拡散という. この処理を繰り返すと，穴は小さくなりやがて消え去る. また，拡散処理によって近くに ある複数んお連結成分どうしがつながり 1 つの連結成分となることがある. 膨張処理は連 結性を保存しない． 縮小 背景または穴に接する対象の画素をひとまわりはぎとる処理を縮小という．この処 理を繰り返すと，対象の領域は小さくなり，やがて消えさる．縮小処理も連結性を保存し ない処理である. 拡散処理と縮小処理を交互に繰り返すことにより，検出領域内のインターレースノイズ による凹凸を除去することが可能となる．また，検出漏れによる穴等のピクセルは，拡散 処理により物体であるという”1”?が設定され，スパイク状のノイズが軽減される．この処 理の実装には，2 度の拡散処理の後，縮小処理を 1 度施す．これは，例えば腕か脚の領域， 検出領域の幅が小さい検出ピクセルに対して，有効なノイズ除去を実現できる． 検出領域のノイズを削除した後，輪郭線は境界線を探索するアルゴリズムに用いて計算 する． ■輪郭線追跡アルゴリズム 輪郭線追跡とは連結成分の境界を求めることで，ここでは 8 連結の場合の輪郭線追跡につ いて説明する． 1. ラスタスキャンにより，白画素から黒画素に変わる画素を探索する．このとき，ラ スタスキャンで探索した方向を進入方向とする． 2. 図 5.1 に示すように，その進入方向を基点に番号順に右回りに黒画素を探索する． 3. 見つかった黒画素に移動する．黒画素が開始点でかつつぎの移動点が追跡済みの場 合は，処理を終了し，追跡結果を登録する．そうでない場合 2 の処理を繰り返す． 分岐点や端点では図 5.2 に示すように何度も同じ画素を追跡する可能性があるため，つ ぎの移動点が追跡済みの場合だけでなく開始点という条件が必要である．また，どの方向 から追跡されたか覚える必要があり，画素ごとに 8 つの方向から進入方向をチェックして おく必要がある． 画像からの物体検出小異機における前処理の過程を図 5.3. に示す． 32 図 5.1: 画素の探索 図 5.2: 輪郭の追跡 5.1.2 輪郭上の特徴点検出 輪郭線から分割するための特徴点の検出を行う．このような輪郭線の形状の特徴を定量 化する手法として骨格化 (skeltonization) を用いる．このような骨格化には，細線化や距 離計算などの手法が既に提案されている．しかし，それらの処理は計算コストが高く，さ らに対象物の輪郭線上のノイズに非常に影響されやすいという問題がある．そこで，提案 手法では輪郭線上の変曲点等の特徴を検出することにより，高速でかつ強健なに星形のス ケルトンを生成する．スター型スケルトンは，中心点と検出された各特徴点を結ぶグラフ で表現されたモデルとなる．以下に，スター型スケルトンによる特徴点の抽出処理の流れ を示す． 1. 輪郭線上の座標点から，形状の重心 (xc , yc ) を求める． 33 Moving target binarization Border extraction Dilation (twice) Erosion 図 5.3: 拡散縮小処理によるノイズ削除 Nb 1 X xi , Nb i=1 Nb 1 X yi yc = Nb i=1 xc = (5.1) (xc , yc ) は，輪郭線上の座標 (xi , yi ) の平均であり，Nb は輪郭線を構成する座標点の数 である． 2. 形状の重心 (xc , yc ) から，輪郭線上の各座標点 (xi , yi ) までの距離 di を次式により計 算する． di = q (xi − xc )2 + (yi − yc )2 (5.2) これらは，輪郭線上の 2 次元座標群を一次元の距離に変換したものであり，この di を 離散関数 d(i) = di とする． ˆ は，高周波数であるノイズを除去するために，フー 3. 1 次元化された輪郭線を表す d(i) リエ変換にしょる周波数領域にてローパスフィルタリング行う． ˆ から特徴点をゼロ交差法により検出 4. フィルタリング後の平滑された 1 次元信号 d(i) する．そして，検出した各特徴点と輪郭線の重心 (xc , yc ) を接続することにより，ス ター型スケルトンを求めることが可能となる． ˆ − d(i ˆ − 1) δ(i) = d(i) スター型スケルトン処理手順を図 5.4. に示す． 34 (5.3) centroid distance distance d(i) 0,end i border position 0 e DFT end LPF a d ^ distance d(i) Inverse DFT b c "star" skeleton of the shape a b c d e 図 5.4: スター型スケルトンによる特徴点の抽出処理の流れ 5.1.3 スター型スケルトンの利点 スター型スケルトンの処理には以下の 3 つの利点がある． • 繰り返しの処理がないため，計算コストが低く，リアルタイム処理が可能 • 特徴点のは，形状の複雑度によって自動的に抽出され，かつその複雑性を考慮する パラメータ制御が可能 • 形状に依存したモデル（例えば人の形状モデル）を予め定義する必要がない 本手法では，ローパスフィルタの遮断周波数 c を変えることにより，輪郭線の形状の複 雑度に応じて特徴点を検出することが可能である．図 5.5 は，異なる遮断周波数 c: c = 0.01 × Nb と c = 0.025 × Nb を用いた際の，ローパスフィルタ後の輪郭データを示す．c がより高い値では，より複雑輪郭情報が残されることになる．こえにより，本手法では異 なったレベルの複雑に対してパラメータを設定することができる． 本アプリケーションのひとつとして，スムージング後の輪郭データから特徴点を検出 し，その個数から輪郭形状の複雑度を求めることが可能である． 既に，人の形状からそのアクティビティ認識する手法が提案されている [18],[19], [20]． しかし，これらの手法は，予め cardboard モデルと呼ばれるモデル用意しておく必要があ るという問題がある．一方，本手法であるスター型スケルトンは，cardboard モデルを必 要としないため，動物や自動車等剛体，非剛体の影響を受けることなく，様々な形状に適 用することが可能である．図 5.6 にスター型スケルトンの適用例を示す． 35 40 80 35 DFT spectrum 70 Original signal 60 50 40 25 Power [dB] 30 20 20 10 15 0 10 -10 5 0 50 100 150 200 -20 250 0 Nb Border position i 20 c = 0.025 40 60 80 100 120 Nb /2 Channels n c = 0.01 (a) 輪郭データと DFT スペクトル 35 c = 0.01 30 d(i) ^ 25 Distance 20 15 10 5 0 50 100 150 200 250 Extremal points : 3 Nb Border position i (b) 平滑後の輪郭データ 1 (c=0.01) 40 c = 0.0025 35 30 Distance d(i) 25 ^ Distance d(i) 30 20 15 10 5 0 50 100 150 200 250 Extremal points : 5 Nb Border position i (c) 平滑後の輪郭データ 2 (c=0.025) 図 5.5: 遮断周波数の変化に対する特徴点 36 video image motion detection skeleton (a) Human (b) Vehicle (c) Polar bear 図 5.6: スター型スケルトンの抽出例 37 第6章 評価実験 本手法により出力された結果有効性を示すために，すでに多くの Flash アニメーション 作成に利用されている Flash のシェイプトゥイーン機能との比較を行う．比較方法として は，映像 (実際の中間形状を得られるもの) より得られた人形を，本提案手法と Flash シェ イプトゥイーンを用いて得られた方法 (ヒントあり · なし複数通り) を比較対象とし，人の 目によるアンケートを計画している． アニメーションの中間形状を決定するのは何よりも人の目である．それ故数値的な評価 よりもアンケート評価を今回行う． 6.1 アンケートによる評価実験 歩行者の映像から連続する 4 枚のフレームを選択し，これらを用いて生成された中間 形状の評価を行う．第 1 フレームをソースフレーム，第 4 フレームをターゲットフレー ムとして各手法により中間形状を生成する．残る第 2，第 3 フレームは，各手法により生 成された中間形状と比較するための望ましい中間形状として使用する．比較実験として， Flash シェイプトゥイーンでシェイプヒントを用いない場合，用いた場合 (1 個，2 個)，そ して提案手法の計 4 手法より得られた中間形状を対象とする．図 6.2 に実際に評価実験に 用いた中間形状例を示す．これらの形状パターンを被験者に見てもらい，似ている，どち らでもない，似ていないを選択する．Flash シェイプトゥイーンでは，複雑な図形の内挿 を行う際に適切な場所にシェイプヒントをおく必要がある．そこで，評価用データには予 め調べた適切なポイントを用いた場合のみを対象としてデータに加えている． 6.2 評価の結果 被験者 50 人に対して評価実験を行った．被験者は各手法により生成された中間形状に 対して 3 段階に評価 (類似する，どちらともいえない，類似しない) する． アンケートより得られた 3 段階の評価結果を-1 から 1 までの数値 (-1:類似しない，0:ど ちらともいえない，1:類似する) に数値化し，150 パターン (3 パターン ×50 人) の平均と 分散を図 6.3 に示す．図 6.3(a) より，Flash シェイプトゥイーンの “シェイプヒント無し” 39 図 6.1: 被験者へのアンケート例 1 40 図 6.2: 被験者へのアンケート例 2 41 図 6.3: 中間形状に対する評価結果 と “シェイプヒント 1 個” の結果は負の評価であることがわかる．これは明かに似ていな いと被験者が判断した事を意味する．Flash シェイプトゥイーンを複雑な形状に適応させ る場合，数点のキーポイントを与える必要があるため，望ましい中間形状の生成が不可能 であった． 一方，“Flash シェイプヒント 2 個” と “提案手法” では正の評価を得た．これは複数の シェイプヒントを形状の特徴となる正しいポイントに設定したため，Flash においても良 い評価を得た．一方，提案手法も同様の評価を得ている．両者の評価値に対して t 検定を 行った結果，有意水準を 5%としたとき，その有意差は無いと判定された．これより，提 案するモーフィング手法は，既存のシェイプトゥイーンのようにシェイプヒントを与える ことなく，それと同等の中間形状を生成できることがわかる．また，図 6.3(b) に示す評価 結果の分散値を比較すると，Flash を利用した場合よりも提案手法の分散が小さいことが わかる．これは，提案手法が様々な形状に対しても，より滑らかで自然な中間形状を安定 して生成可能であることを示している． 42 第7章 まとめ 本稿では，端点固定 DP マッチングを用いた閉曲線輪郭形状の中間形状を生成するカン ターモーフィングを提案した．輪郭線の対応付けは端点固定 DP マッチングにより自動的 に算出されるため，既存の Flash シェイプトゥイーンでは必要とされたユーザからの入力 情報を，本手法では一切必要としないでユーザの望む中間形状を生成することが可能であ る．被験者による評価の結果，提案手法はより望ましい中間形状を出力できることを確認 した． 7.1 今後の課題と展望 本研究内容は現場において少しでもその軽減に役立レベルに達することが出来るよう， 更なる実験や改良を繰り返す．特に，調査段階で研究期間を終えてしまった形状を分割 し，対応付けを行う方法については，比較対象としても利用出来るため，今後理論を確立 して行く． 放送用アニメーション現場においてより利用されるのは，今回報告した輪郭形状より も，線分や曲線同士の中間が必要になることのほうが多くなる．連なるカットを描かれた 原画二枚を比較し，各線分同士の中割り形状を描く機能についても今後取り組む必要が ある． 2004 年に劇場上映されたイノセンスや，2005 年にテレビ放映された Blood+など，既 にフルデジタルで作成されたアニメも登場している．一枚一枚を描き，塗りこんでいたセ ル画時代と比べ，その作業の殆どは軽減できるところまで来ていると考えられる．作業の 軽減化に伴い，今後はフルデジタルで作成されたアニメーションがさらに増えていくこと は確実であろう． 紙媒体に描くほうが作業の早い者が居り，デジタルでの作業を苦手とする者もいるが， その場合は自分に利用できると感じる部分を利用すればよいのである．有益な機能を増や し，製作側の負担を少し得も減らすことで，本研究が将来的にアニメーション製作に協力 できるのであれば幸いである． 43 謝 辞 本論文の作成にあたり終始適切な助言を賜り, また指導して下さいました中部大学工学 部情報工学科藤吉弘亘助教授に深く感謝致します． 次に，研究時や論文作成時にご助言を頂きました中部大学工学部情報工学科岩堀祐之教 授，ならびに中部大学工学部情報工学科奥居哲助教授に感謝致します. 最後に, プログラム作成にあたり数多くの助言を頂きました中部大学工学部情報工学科 高丸尚教助教授，また，アニメーション作成現場における現状を教えて頂きましたマルチ メディア系専門学校ＣＧ学科講師中本正樹さん，アンケートの回答にご協力頂きました 方々，最高のメンバで構成された藤吉研究室の皆様に深く感謝いたします. 45 参考文献 [1] 白濱洋平 ，大野義夫，“多数決にもとづくアニメーションキャラクターのモーフィン グ手法, ” 情報処理学会研究報告 Vol.2001, No.035, 2001–CG–103, Apr. 2001 [2] 爰島快行, 高橋成雄, 大渕竜太郎,“形状モーフィングにおける位相変化の制御,” 情報 処理学会グラフィクスと CAD 研究会報告 2001-CG-102, pp. 61-66, Feb. 2001. [3] “RETAS! Pro シリーズ”, CELSYS, Inc. http://www.celsys.co.jp/ [4] “After Effects”, Adobe Systems, Inc. http://www.adobe.com/ [5] T. W. Sederberg and E. Greenwood, “A Physically Based Approach to 2-D Shape Blending” Computer Graphics, vol.26, no.2, pp.25-34, 1992. [6] E. Milios and E. G. M. Petrakis, “Shape Retrieval Based on Dynamic Programming” IEEE Transaction on Image Processing, vol.9, no.1, pp.141-147, 2000. [7] N. Ueda and S. Suzuki, “Learning Visual Models from Shape Contours Using Multiscale Convex/Concave Structure Matching” IEEE Trans. Pattern Analysis and Machine Intelligence, vol.15, no.4, pp.337-352, 1993. [8] “Matching and Retrieval of Distorted and Occuluded Space Using Dynamic Programming”, E. G. M. Petrakis , A. Diplaros, and E. Milios(2002) [9] I. Bartolini, P. Ciaccia, and M. Patella, “WARP: Accurate Retrieval of Shapes Using Phase of Fourier Descriptors and Time Warping Distance” IEEE Trans. Pattern Analysis and Machine Intelligence, vol.27, no.1, pp.142–147, 2005. [10] H. Sakoe and S. Chiba, “Dynamic Programming Algorithm Optimization for Spoken Word Redognition” IEE Trans. Acoust., Speech, and Signal Process., Vol.ASSP-26, pp. 43-49, 1978. 47 [11] Y. Ohta and T.Kanade, “Stereo by Two-Level Dynamic Programming” Proc. of the Ninth International Joint Conference on Artificial Intelligence, Vol. 2, pp. 1120-1126, 1985. [12] D. Geiger, A. Gupta, L. A. Costa, and J. Vlontzos, “Dynamic Programming for Detecting, Tracking, and Matching Deformable Contours” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.17, No.3, pp. 294-295, 2004. [13] E. G. M. Petrakis, A. Diplaros, and E. Milios, “Matching and Retrieval of Distorted and Occuluded Shape Using Dynamic Programming” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.24, No.11, pp. 1501-1516, 2002. [14] T. W. Sederberg and E. Greenwood, “A Physically Based Approach to 2-D Shape Blending” Computer Graphics, Vol.26, No.2, pp. 25-34, 1992. [15] E. Milios, and E. G. M. Petrakis, “Shape Retrieval Based on Dynamic Programming” IEEE Transactions on Image Processing, Vol.9, No.1, pp. 141-147, 2000. [16] G. Cong and B. parvin, “A New Regularized Approach for Contour Morphing ” Computer Vision and Pattern Recognition, Vlo.1,pp. 1458-1463, 2000. [17] “Flash Professional”, Adobe Systems, Inc. (Macromedia, inc.) http://www.macromedia.com/ [18] C. Wren, A. Azarbayejani, T. Darrell, A. Pentland, “Pfinder: Real-Time Tracking of the Human Body” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 19, no 7, pp. 780-785, July 1997. [19] S. Ju, M. Black, Y. Yacoob, “Cardboard People: A Parameterized Model of Articulated Image Motion” International Conference on Face and Gesture Analysis, 1996. [20] I. Haritaoglu, D. Harwood, L. S. Davis, “W 4 Who? When? Where? What? A Real Time System for Detecting and Tracking People” FGR98 submitted, 1998. [21] H. Fujiyoshi, A. J. Lipton, and T. Kanade, “Real-Time Human MotionAnalysis by Image Skeletonization” IEICE Trans. Inf. & Syst., Vol.E87-D, No.1,pp. 113-120, 2004. [22] P. Selinger, “potrace: a polygon-based tracing algorithm” [23] Herbert Freeman, “Computer Processing of Line-Drawing Images” ACM Comput., Surv. 6(1), pp. 57-97 ,1974. 48 [24] F. Mokhtarian and A. Mackworth, “Scale -Based Description and Recognition of Planar Curves and Two-Dimensional Shapes” IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI1986) , pp34 –43, 1986. [25] 下田陽久ら編著, “画像処理標準テキストブック”, CG-ARTS 協会,2003. [26] 奥富正敏ら編著, “ディジタル画像処理”, CG-ARTS 協会,2004. [27] F. Mokhtarian and A. Mackworth, “Scale -Based Description and Recognition of Planar Curves and Two-Dimensional Shapes” IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI1986) , pp34 –43, 1986. [28] S. Kopf, T. Haenselmann, and W. Effelsberg, “Enhancing Curvature Scale Space Features for Robust Shape Classification” IEEE International Conference on Multimedia and Expo (ICME2005) ,2005. [29] 森口繁一, 宇田川金圭久, 一松信 共著 “岩波数学公式 1 微分積分, 平面曲線”, 岩波書 店, 1956. [30] H. Asada and M. Brandy, “The curvature primal sketch”, M.I.T. AI Memo 758, 1984. ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-758.pdf [31] 高畑知也, 熊澤逸夫, “画像の多重解像度表現におけるエッジの断層間関連付けと分類 -エッジ情報の有効な利用方法の提案-” , 画像の認識・理解シンポジウム (MIRU2004), 2004. [32] Marr - Hildreth. “ Theory of edge detection”, Proc. Roy. Soc. Lond., B207:187 - 217, 1980. http://users.ntua.gr/karank/topo/PhD notes/Edge%20Detection/marr&hil.htm [33] “Marr/Hildreth and Canny Edge Detection” http://www.cs.ubc.ca/ woodham/cpsc505/examples/edge.html [34] G. Agarwal and S. K. Goel, “Object Recognition through Curvature Scale Space”, http://www.cse.iitk.ac.in/ amit/courses/768/99/gunjan/ [35] C. Anderson, P. Burt, G. van der Wal, “Change detection and tracking using pyramid transformation techniques” SPIE - Intelligent Robots and Computer Vision Vol. 579, pp. 72-78, 1985. [36] J. Barron, D. Fleet, S. Beauchemin, “Performance of Optical Flow Techniques” International Journal of Computer Vision, Vol. 12, no. 1, pp. 42-77, Jan. 1994. 49 [37] J. Davis, A. Bobick, “The representation and recognition of human movement using temporal templates” Proceedings of IEEE CVPR 97, pp. 928 - 934, 1997. [38] E. Grimson, P. Viola, “A Forest of Sensors” DARPA - VSAM workshop, Nov. 1997. [39] T. Kanade, R. Collins, A. Lipton, P. Anandan, P. Burt, “Cooperative Multisensor Video Surveillance” Proceedings of DARPA Image Understanding Workshop 1997, Vol. I, pp. 3-10, 1997. [40] M. Oren, C. Papageorgiou, P. Sinha, E. Osuna, T. Poggio, “Pedestrian detection using wavelet templates” Proceedings of IEEE CVPR 97, pp. 193-199, 1997. [41] P. Tsai, M. Shah, K. Ketter, T. Kasparis, “Cyclic motion detection for motion based recognition” Pattern Recognition, Vol. 27, No. 12, pp. 1591-1603, 1994. 50 発表業績一覧 研究会技術報告 [1] 高畠綾子, 野村太一, 藤吉弘亘, “輪郭形状の対応計算によるシェイプトゥイーン”, 画 像の認識・理解シンポジウム (MIRU2005), 2005. 学会口頭発表 [2] 高畠綾子, 藤吉弘亘, “DP マッチングを用いた輪郭形状のシェイプトゥイーン”, 電気 関係学会東海支部連合大会, 2005. 51