(57)【要約】【課題】モーショングラフを利用した動き生成において、双方向エッジを連続で遷移しない制約のもと、動きの滑らかさと多様性とを両立した動きを生成する。【解決手段】モーショングラフ生成部4は、動きの滑らかさを確保できる第一のモーショングラフを構築する。モーショングラフ修正部5は、第一のモーショングラフにおける双方向エッジのうち、制約によって局所ループの要因となってしまい動きの多様性に寄与しない局所ループ発生要因ノードを検出して修正する。検出は、複数の双方向エッジが接続されたノードであり且つ所定条件を満たすものを検出し、修正は、双方向エッジの削除や当該ノードの１つ隣のノードに接続する双方向エッジを新たに設けることによって行う。接続動き生成部6は入力時系列データに合った動きデータを第二のモーショングラフを探索して構築する。【選択図】図11
2013218480.tif 000002
【特許請求の範囲】
【請求項１】
予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成装置であって、
複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成部と、
前記第一のモーショングラフにおいて複数のエッジが接続されている各ノードにつき、その遷移特性に基づいて接続されているエッジを修正して前記第二のモーショングラフを生成するモーショングラフ修正部と、
前記第二のモーショングラフに基づいて、各ノードの遷移特性のもとで、前記所定の時系列データに即した動きデータを生成する動き生成部と、を備えることを特徴とする動き生成装置。
【請求項２】
前記モーショングラフ生成部は、
前記複数の動きデータの各々より各動きデータの時間変化に基づいて複数のキーフレームを抽出してノードとなすキーフレーム抽出部と、
同一の動きデータに属して隣接するノード間に単方向エッジを設ける単方向エッジ設定部と、
互いに異なる動きデータに属して第一の所定基準で類似するノード間と、同一の動きデータに属しており且つ隣接しておらず前記第一の所定基準で類似するノード間と、に双方向エッジを設ける双方向エッジ設定部とを含み、
当該ノードと、単方向及び双方向エッジとによって前記第一のモーショングラフを生成し、
前記動き生成部は、前記第二のモーショングラフに基づいて、各ノードの遷移特性に従って、双方向エッジの後は単方向エッジを利用するとの制約のもとで、前記所定の時系列データに即した動きデータを生成することを特徴とする請求項1に記載の動き生成装置。
【請求項３】
前記モーショングラフ修正部は、前記第一のモーショングラフの各強連結成分において複数の双方向エッジが接続されている各ノードにつき、当該複数の双方向エッジが、当該ノードから単方向エッジで辿れる先のノードを一端として有するような少なくとも１つの双方向エッジと、当該ノードから単方向エッジで辿れない先のノードを一端として有するような少なくとも１つの双方向エッジと、からなる場合で、且つ、当該ノードより単方向エッジを辿った先にあるノードに対して接続される双方向エッジが所定条件を満たす場合に、当該ノードを局所ループ発生要因ノードと判定して、当該局所ループ発生要因ノードに接続される双方向エッジを修正することを特徴とする請求項２に記載の動き生成装置。
【請求項４】
前記所定条件が、
当該ノードより単方向エッジを辿った先にあるノードに対して接続される双方向エッジであって、当該ノード以外を一端に有する双方向エッジが存在しないこと、又は、
当該ノードより単方向エッジを辿った先にあるノードに対して接続される双方向エッジであって、当該ノード以外を一端に有する双方向エッジが存在し、当該存在する双方向エッジが全て、当該ノードより単方向エッジを辿った先にあるノードのみをその両端として有すること、であることを特徴とする請求項３に記載の動き生成装置。
【請求項５】
前記モーショングラフ修正部は、前記局所ループ発生要因ノードより単方向エッジを辿った先のノードを一端として有し、前記局所ループ発生要因ノードをもう一端として有する双方向エッジが１つしか存在しない場合に、当該双方向エッジを削除することによって修正を行うことを特徴とする請求項３または４に記載の動き生成装置。
【請求項６】
前記モーショングラフ修正部は、前記局所ループ発生要因ノードより単方向エッジを辿った先のノードを一端として有し、前記局所ループ発生要因ノードをもう一端として有する双方向エッジが２つ以上存在する場合に、当該２つ以上の双方向エッジのうちの１つ若しくは全ての双方向エッジにおける前記局所ループ発生要因ノード以外の一端のノードと、前記局所ループ発生要因ノードに対して１つの単方向エッジで辿り着くノードとを、又は、前記局所ループ発生要因ノードを一端として有する双方向エッジのもう一端のノードであって前記局所ループ発生要因ノードより単方向エッジで辿り着けないノードのうちの１つ若しくは全てとを、両端とする双方向エッジを新たに設けることによって修正を行うことを特徴とする請求項３ないし５のいずれかに記載の動き生成装置。
【請求項７】
前記モーショングラフ修正部は、前記存在する２つ以上の双方向エッジのうち、前記局所ループ発生要因ノード以外の一端のノードにおける、前記局所ループ発生要因ノードから単方向エッジを辿った遷移数が最大又は最小となる双方向エッジを対象として、修正を行うことを特徴とする請求項６に記載の動き生成装置。
【請求項８】
前記モーショングラフ修正部は、前記両端となりうるノードの組み合わせのうちノード間の類似度が最大のものを対象として、修正を行うことを特徴とする請求項６または７に記載の動き生成装置。
【請求項９】
前記モーショングラフ修正部はさらに、
前記第一のモーショングラフを強連結成分分解によって複数の部分グラフへと分割するグラフ分割部と、
前記複数の部分グラフのうちの異なるものに属し且つ第二の所定基準で類似するノード間に双方向エッジを設けることで前記第一のモーショングラフに再接続を施すノード再接続部と、を含み、
当該再接続された第一のモーショングラフを対象として修正を行うことで前記第二のモーショングラフを生成することを特徴とする請求項１ないし８のいずれかに記載の動き生成装置。
【請求項１０】
前記ノード再接続部が、前記複数の部分グラフのうちの異なるものに属するノード間であって、且つ両ノードから１つの単方向エッジで辿った先のノードが当該両ノードのそれぞれの属する強連結成分に属しているノード間のうち、前記第二の所定基準で類似するノード間に双方向エッジを設けることで前記第一のモーショングラフに再接続を施すことを特徴とする請求項９に記載の動き生成装置。
【請求項１１】
前記単方向エッジ設定部は、同一の動きデータに属して隣接するノード間に時間方向の単方向エッジを設けると共に、当該同一の動きデータのうち当該ノード間に存在するデータの時間変化に基づく重みを付与し、
前記双方向エッジ設定部は、互いに異なる動きデータに属して前記第一の所定基準で類似するノード間及び同一の動きデータに属して単方向エッジが設けられておらず前記第一の所定基準で類似するノード間に双方向エッジを設けると共に、当該類似する度合いに基づく重みを付与し、
前記動き生成部は、さらに、
前記第二のモーショングラフ内の各パスの中から、各パスに順次現れるエッジの重みと前記所定の時系列データの各区間に順次現れる特徴量とに所定の関数を適用して得られるコストを最小とするパスを動的計画法により求め、前記所定の時系列データに同期するパスとして決定する同期部と、
前記同期するパスに順次現れるノードに対応する前記複数の動きデータの断片を順次連結し、双方向エッジの両端のノードに対応する断片同士を当該連結する際には平均化を施すことで前記所定の時系列データに即した動きデータを生成する合成部とを含むことを特徴とする請求項１ないし１０のいずれかに記載の動き生成装置。
【請求項１２】
予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成方法であって、
複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成ステップと、
前記第一のモーショングラフにおいて複数のエッジが接続されている各ノードにつき、その遷移特性に基づいて接続されているエッジを修正して前記第二のモーショングラフを生成するモーショングラフ修正ステップと、
前記第二のモーショングラフに基づいて、各ノードの遷移特性のもとで、前記所定の時系列データに即した動きデータを生成する動き生成ステップと、を備えることを特徴とする動き生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き生成に関し、特に、一旦構築したモーショングラフをそのループ構造に基づいて再構築する際に、モーショングラフを利用して動きを生成する際の制約を考慮した上で、より多様な動きを生成する動き生成装置及び方法に関する。
【背景技術】
【０００２】
動きデータの一種として、MoCap(Motion Capture；モーションキャプチャ)データがある。MoCapデータの収録は、画像や映像データの取得に比べてコストがかかる。そのため、新たな動きを生成するために、元のMoCapデータを組み合わせて再利用することが行われる。その際に、短時間の動き要素の間の関係をMotion Graph(モーショングラフ)と呼ばれるグラフ構造で表現する方法がある。
【０００３】
特許文献1や非特許文献1では、音楽と同期した動きを自動生成するために、事前に収録された動きの構造を考慮可能なMotion Graphを利用している。事前に、MoCapデータから動きのビートを抽出し、その動きのビート時刻におけるポーズを表すビートフレームをグラフのノードとする。元のMoCapデータで連続しているビートフレームを表すノード間は、時間軸に沿って単方向エッジで接続する。一方で、連続していないノード間は、ビートフレームの類似度の大きさにより、双方向エッジで接続し，類似度の大きさを双方向エッジの重みとして与える。
【０００４】
さらに、MoCapデータから取得される動きの盛り上がり情報によって単方向エッジに重みを与えることで、Motion Graphが構築される。このMotion Graphを利用することで、入力された音楽から抽出されるビートと動きのビートを合わせた上で、音楽の盛り上がりの傾向と似ている盛り上がりのパタンを持つ動きを、エッジ接続されたノード間のみを遷移することで、音楽と同期しかつ滑らかな動きを生成可能としている。
【０００５】
また，Motion Graphのフレームワークを利用した音楽と同期した動きの自動生成において、音楽の残り時間がMotion Graph上で遷移可能な時間（デッドエンド（遷移するパスがないノード）に到達するまでの時間）が短い場合に動きが生成できなくなる問題を指摘しており、その改善のためにSynchronization Capacity（SC；同期限度；シンクロナイゼーション・キャパシティ）という制約を導入することで、音楽の残り時間に対して最後まで動きを生成可能なノードのみを遷移候補として選択できるようにすることで、デッドエンドへの到達回避の保証をしている。
【０００６】
音楽に同期した動きを生成する場合、音楽より早く動きが終わってしまうことは好ましくない。そのため、音楽と少なくとも同じ長さの動きを生成できることが望まれる。そこでSCを導入する。具体的には、各ノードに対して自身から遷移可能なノードの数の最大値としてSCを定義する。
【０００７】
音楽が入力されて、ある時刻において音楽の残り時間がわかると、その残り時間だけ遷移可能なノードのみが、遷移候補ノードとして選ばれることになる。
【０００８】
従って、音楽が無限時間だけあると考えると、ループ中に含まれる（その先にループを持つ）ノードのみに遷移することになる。この制約により、音楽が終了する前に動きの生成ができなくなる現象を防ぐことはできる。しかしながら、ループを形成しているノード群（部分グラフ）のみに遷移が集中するため、ループに含まれるノード数が少ない（ループサイズが小さい）場合、同じような動きが頻発する。
【０００９】
図12は、SCの例を示す図であり、ここでは丸印「○」で示すノード及び矢印で示すエッジからなるモーショングラフにおいて、各ノードのSCが具体的な数値(無限大「∞」を含む)として示されている。
【００１０】
図12にて例えば、ある現在時刻におけるノードが図12のN1であって、音楽の残り時間が2ノードの長さ未満であれば、遷移候補ノードは同図のN2及びN3の部分のノードとなるが、音楽の残り時間が2ノードの長さ以上であれば、遷移候補ノードはN3の部分のノード（N3のうち、SCが0のデッドエンドノード（一番右端のノードを除く）のみとなる。こうして、SCによって残り時間の長さに応じた遷移候補ノードの絞り込みが可能となる。
【００１１】
また、非特許文献2では、上記の非特許文献1の制約により生成される動きのバリエーションが少なくなる問題に対して、グラフの構造特性を考慮してノード間の双方向エッジの接続判定を適応的に行い、新たなMotion Graphを生成している。これにより、グラフ中のループのサイズが拡大され、従来はエッジが存在しないために遷移できなかったノードに対して、動きの滑らかさをほぼ損なわずに遷移可能としている。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開2011-204113号公報
【非特許文献】
【００１３】
【非特許文献１】J. Xu et al., "MOTION SYNTHESIS FOR SYNCHRONIZING WITH STREAMING MUSIC BY SEGMENT-BASED SEARCH ON METADATA MOTION GRAPHS," IEEE ICME, 2011
【非特許文献２】今野ら，"Motion Graph の強連結成分の統合による自動生成ダンスの多様性向上," 電子情報通信学会総合大会，2012
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、特許文献1では、元の動きファイルで連続していないビートフレーム（ノード）間のエッジ接続判定を、ビートフレーム間の類似度を閾値処理することで、ビートフレーム間での遷移によって生成される動きの滑らかさや音楽のリズムや大きさとの同期といった比較的短時間の動きの質の向上を目的としており、生成される動き全体の多様性を向上させるための検討はされていない。
【００１５】
これに対して、非特許文献2では、同じような動きが繰り返される現象が頻発するという問題に対して、ノードのグラフ上の構造特性に応じて双方向エッジによるノード間の接続判定を適応的に行うことで、解決しようとしている。従来は接続されなかったノード間が接続されるため。多様性が向上すると考えられる。
【００１６】
しかしながら、非特許文献2では、特許文献1や非特許文献1と同様に、実際にMotion Graphに基づき動きを生成する際に、双方向エッジを遷移する際には、その双方向エッジの遷移先に存在する単方向エッジを含めて遷移するという制約がある。
【００１７】
図13は当該制約を説明するための図である。例えばノード2−ノード7間の双方向エッジを2→7の向きに遷移する際の動きの生成する場合、ノード2を途中に含む動きデータ(フレームデータ)F2と、ノード7を途中に含む動きデータF7とをブレンディングという手法で組み合わせることによって生成される。
【００１８】
そして、ブレンディングにおいて双方向エッジで2→7と遷移する際の動きの生成は、当該動きより前の動きがデータF2のノード2より前の部分と滑らかにつながり、当該動きより後の動きがデータF7のノード7より後の部分と滑らかにつながることを前提に生成される。
【００１９】
よって、双方向エッジにおける「2→7」の遷移の際はその前後で必ず単方向エッジによる遷移であるという制約が課され、図中に太字で表しているように「1→2→7→8」という遷移にて動きが生成される。双方向エッジを連続して遷移する「5→2→7」や「2→7→4」は当該制約により、禁止される。
【００２０】
また、当該例ではノード2−ノード7間の双方向エッジにおける「2→7」の遷移について説明したが、逆に「7→2」と遷移する場合も同様に、その前後では必ず「6→7→2→3」という遷移にて動きが生成される。
【００２１】
すなわち、双方向エッジに対応する動き生成のため制約として、双方向エッジとその先に存在する単方向エッジの組み合わせによって遷移することで、1ビート間隔分の動きを生成することができる。当該制約は、双方向エッジを連続して選んで遷移しない、と言い換えてもよい。
【００２２】
そのため、この制約を考慮せずに非特許文献2にある方法でMotion Graphを再構築した場合、(1)SCの制約を満たさないノードへ遷移する可能性があるため、2つのループを統合する新たな双方向エッジを接続しても、そのエッジを遷移するパスが選択されないことや、(2)グラフ構造的には強連結（どのノード間も互いに行き来できるノードから構成される部分グラフ）であっても、ループを形成しているノード群の中に含まれる小さなループ（局所ループ）内での遷移から抜け出せなくなり、多様性が低下するという問題が発生する場合がある。
【００２３】
本発明の目的は、上記の従来技術の課題を解決し、動きの滑らかさを維持しつつ多様な動きデータを生成することのできる動作生成装置及び方法を提供することにある。
【課題を解決するための手段】
【００２４】
上記目的を達成するため、本発明は、予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成装置であって、複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成部と、前記第一のモーショングラフにおいて複数のエッジが接続されている各ノードにつき、その遷移特性に基づいて接続されているエッジを修正して前記第二のモーショングラフを生成するモーショングラフ修正部と、前記第二のモーショングラフに基づいて、各ノードの遷移特性のもとで、前記所定の時系列データに即した動きデータを生成する動き生成部と、を備えることを第一の特徴とする。
【００２５】
また、本発明は、予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成装置であって、複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成部と、前記第一のモーショングラフのエッジを修正して第二のモーショングラフを生成するモーショングラフ修正部と、前記第二のモーショングラフに基づいて、前記所定の時系列データに即した動きデータを生成する動き生成部とを備え、前記モーショングラフ生成部は、前記複数の動きデータの各々より各動きデータの時間変化に基づいて複数のキーフレームを抽出してノードとなすキーフレーム抽出部と、同一の動きデータに属して隣接するノード間に単方向エッジを設ける単方向エッジ設定部と、互いに異なる動きデータに属して第一の所定基準で類似するノード間と、同一の動きデータに属しており且つ隣接しておらず前記第一の所定基準で類似するノード間と、に双方向エッジを設ける双方向エッジ設定部とを含み、当該ノードと、単方向及び双方向エッジとによって前記第一のモーショングラフを生成し、前記モーショングラフ修正部は、前記第一のモーショングラフにおいて複数の双方向エッジが接続されている各ノードにつき、その遷移特性に基づいて接続されている双方向エッジを修正して前記第二のモーショングラフを生成し、前記動き生成部は、前記第二のモーショングラフに基づいて、双方向エッジの後は単方向エッジを利用するとの制約のもとで、前記所定の時系列データに即した動きデータを生成することを第二の特徴とする。
【００２６】
また、本発明は、前記モーショングラフ修正部は、前記第一のモーショングラフの各強連結成分において複数の双方向エッジが接続されている各ノードにつき、当該複数の双方向エッジが、当該ノードから単方向エッジで辿れる先のノードを一端として有するような少なくとも１つの双方向エッジと、当該ノードから単方向エッジで辿れない先のノードを一端として有するような少なくとも１つの双方向エッジと、からなる場合で、且つ、当該ノードより単方向エッジを辿った先にあるノードに対して接続される双方向エッジが所定条件を満たす場合に、当該ノードを局所ループ発生要因ノードと判定して、当該局所ループ発生要因ノードに接続される双方向エッジを修正し、前記所定条件が、当該ノードより単方向エッジを辿った先にあるノードに対して接続される双方向エッジであって、当該ノード以外を一端に有する双方向エッジが存在しないこと、又は、当該ノードより単方向エッジを辿った先にあるノードに対して接続される双方向エッジであって、当該ノード以外を一端に有する双方向エッジが存在し、当該存在する双方向エッジが全て、当該ノードより単方向エッジを辿った先にあるノードのみをその両端として有すること、であることを第三の特徴とする。
【００２７】
さらに、本発明は、前記モーショングラフ修正部は、前記局所ループ発生要因ノードより単方向エッジを辿った先のノードを一端として有し、前記局所ループ発生要因ノードをもう一端として有する双方向エッジが１つしか存在しない場合に、当該双方向エッジを削除することによって修正を行い、前記局所ループ発生要因ノードより単方向エッジを辿った先のノードを一端として有し、前記局所ループ発生要因ノードをもう一端として有する双方向エッジが１つしか存在しない場合に、当該双方向エッジを削除することによって修正を行うことを第四の特徴とする。
【００２８】
また、本発明は、上記目的を達成するため、予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成方法であって、複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成ステップと、前記第一のモーショングラフにおいて複数のエッジが接続されている各ノードにつき、その遷移特性に基づいて接続されているエッジを修正して前記第二のモーショングラフを生成するモーショングラフ修正ステップと、前記第二のモーショングラフに基づいて、前記各ノードの遷移特性のもとで、前記所定の時系列データに即した動きデータを生成する動き生成ステップと、を備えることを第五の特徴とする。
【発明の効果】
【００２９】
前記第一又は第五の特徴によれば、ノードの遷移特性に基づいてエッジが修正された第二のモーショングラフに基づいて動きデータを生成するので、滑らかで且つ多様な動きデータを生成することができる。
【００３０】
前記第二の特徴によれば、複数の双方向エッジが接続されているノードを多様性を低下させうるものとして、その遷移特性に基づいて接続されている双方向エッジを修正することにより、多様性を改善させ、且つ動きの滑らかさを維持した動きデータを生成することができるようになる。
【００３１】
前記第三の特徴によれば、多様性を低下させる原因となる局所ループ発生要因ノードを特定して、多様性及び動きの滑らかさを両立した動きデータを生成することができるようになる。
【００３２】
前記第四の特徴によれば、局所ループ発生要因ノードに接続されている双方向エッジを修正することで多様性及び動きの滑らかさを両立した動きデータを生成することができるようになる。
【図面の簡単な説明】
【００３３】
【図１】一実施形態に係る動き生成装置の機能ブロック図である。
【図２】一実施形態に係る動き生成装置の機能概要を説明する図である。
【図３】モーショングラフの概要を説明する図である。
【図４】グラフの強連結成分分解を例で説明する図である。
【図５】ノード再接続部における最小距離法の処理のフローチャートを示す図である。
【図６】ノード再接続部において再接続の候補対象から除外するものと、除外しないものとの具体例を示す図である。
【図７】ノード再接続部における閾値制御法の処理のフローチャートを示す図である。
【図８】図5のフローによるグラフの更新の例を示す図である。
【図９】図7のフローによるグラフの更新の例を示す図である。
【図１０】局所ループ発生要因ノードや、局所ループの解消手法を説明するための図である。
【図１１】一実施形態に係る動き生成装置の機能ブロック図である。
【図１２】モーショングラフにおける同期限度(SC)の例を示す図である。
【図１３】動き生成のために課される、双方向エッジを連続して遷移しない(双方向エッジの次は単方向エッジを遷移する)制約を説明するための図である。
【発明を実施するための形態】
【００３４】
図1は本発明の一実施形態に係る動き生成装置の機能ブロック図である。動き生成装置1は、音情報解析部2、動きデータベース3、モーショングラフ生成部4、モーショングラフ修正部5、動き生成部6及び動き再生部7を備える。なお後述するように、動き生成装置1はこれらの機能ブロックのうちの一部のみを備えて構成されていてもよい。
【００３５】
モーショングラフ生成部4は、キーフレーム抽出部41、単方向エッジ設定部42及び双方向エッジ設定部43を含む。モーショングラフ修正部5は、グラフ分割部51、ノード再接続部52及びノード再修正部53を含む。動き生成部6は、同期部61及び合成部62を含む。
【００３６】
図2は、図1の動き生成装置1の機能概要を説明する図である。(1)に示すように、音楽や音声といった音情報を持つファイル（wavやmp3など）が入力されると、音情報解析部2が当該音情報を解析してその特徴を得る。(2)に示すように、動き生成部6が当該音特徴に合った動きを探索する。(3)に示すようにその探索対象はモーショングラフである。モーショングラフは動きデータベース3、モーショングラフ生成部4及びモーショングラフ修正部5によって用意される。(4)に示すように、当該モーショングラフ上のパスのうち、音特徴に合ったパスが探索結果となる。(5)に示すように、動き生成部5はさらに当該探索結果に従う動きを生成し、(6)に示すように、動き再生部7が当該生成された動きを適宜入力音情報と同時進行させながら再生する。
【００３７】
ここで、入力される音はファイル中の全ての時間分の音情報でもよいし、ファイル中の一部の音情報だけ読み出して、その一部の音情報に基づき、動きを生成し再生することを音情報が終了するまで逐次行ってもよい。
【００３８】
図3はモーショングラフの概要を説明する図である。(1)に示すように、動きデータベースには複数の動きデータ1〜Nが保存されている。当該データは典型的にはMoCapデータであって、実際にMotion Captureシステムなどにより収録されたMoCapデータを保存するMoCapデータベースとして動きデータベース3を用意しておく。
【００３９】
動きデータベース3の中の動きデータの各々に対して、モーショングラフ生成部4において音情報に対する時間的な同期のために必要となる動きビート抽出処理や、動きの滑らかさを制御するために必要となるエッジ接続判定処理を行い、(2)に示すようにモーショングラフを生成する。なおモーショングラフ修正部5においてさらにモーショングラフの修正が行われるが、モーショングラフの形式自体は同じである。ここでは当該形式を、モーショングラフ生成部4の各部の機能と共に説明する。
【００４０】
キーフレーム抽出部41は各動きデータより動きのビートフレームを複数抽出して、各々をモーショングラフにおけるノードとなす。当該各動きデータにおける複数定められたノードは(2)に○として示されている。ビートフレームとは、動きデータの時系列上の１フレームであって、動きのビートを表しているフレームである。
【００４１】
MoCapデータにおける当該ビートの抽出に関しては、以下の非特許文献3に開示された次のような技術を利用することができる。MoCapデータには基準となるポーズのフレームには、ルート（腰）や各関節の3次元座標が、その後のフレームにおいては、基準ポーズからの相対的な位置などが含まれる。このMoCapデータから各時刻における各関節の3次元座標を求めて、関節数×3次元のベクトルの時系列として動きを表すことができる。この動きを一定の分析幅で分割して、分析幅の対象となる区間のデータに対して主成分分析を適用することで、動きのグローバルな成分（最も大きな変化の方向）が第1主成分の主成分得点に抽出される。この主成分得点が極大及び極小となる時刻のフレームを動きのビートフレーム（ノード）とする。
【００４２】
[非特許文献3] J. Xu et al., "Beat induction from motion capture data using short-term principal component analysis," 映像情報メディア学会論文誌 2010
【００４３】
なお、動きデータは必ずしもMoCapデータではなく、上述ように各関節等の3次元座標が直接与えられている形式のデータなどが利用できるならば、当該各形式のデータを利用するようにしてもよい。
【００４４】
なお、キーフレーム抽出部41はより一般には、ビートフレームの代りに、動きデータの時間変化においてある特徴を持ったキーフレームを抽出してノードとなす。例えば、動きデータを所定の時間幅で区切り、その1つの区間で、最も変化の大きいフレームとしてキーフレームが得られ、当該キーフレームがノードに割り当てられる。
【００４５】
ビートフレームとはキーフレームの一種であって、音に合わせた動きを生成する際に好ましいキーフレームである。以下、ノードにビートフレームを採用するものとして説明するが、本発明はより一般のキーフレームをノードに採用しても実施可能である。
【００４６】
単方向エッジ設定部42は、動きビート抽出により定まったノード間であって、同じ動きデータに由来して且つ時間軸上で互いに隣接する関係にあるノード間に、時間方向の単方向エッジを設定する。当該単方向エッジは図3の(2)に単方向矢印として概念的に示されている。
【００４７】
単方向エッジ設定部42はさらに、設定した単方向エッジの各々に重みを付与する(図3では不図示)。各単方向エッジは、ノードであるビートフレーム同士の間にある一連のフレームに対応する。ここでビートフレーム間には、1ビート分の長さに対応する数だけ当該一連のフレームが存在する。その1ビート分のフレーム群の各関節の3次元座標に対して、主成分分析した際に求まる第1主成分の固有値（主成分空間上の分散）は、動きの盛り上がり(活発さ)を表すものであるので、単方向エッジ設定部は当該活発さに基づく重みを各単方向エッジに付与する。例えば、当該固有値をそのままの値で、重みとする。当該詳細は特許文献1に詳しい。
【００４８】
双方向エッジ設定部43は、動きビート抽出により定まったノード間であって、単方向エッジが設定されておらず、且つ各ノードに対応する動きデータのフレームが表すポーズ同士が所定基準で類似していると判定されるノード間に、双方向エッジを設定する。当該類似判定はポーズ間に距離を定義することで行われる。類似しないと判定されたノード間にはエッジは何も設定されない。当該設定された双方向エッジは図3の(2)に双方向矢印として概念的に示されている。
【００４９】
双方向エッジ設定部43はさらに、各双方向エッジに当該類似度合いに基づく重みを付与する(図3では不図示)。これら類似度や重み等の詳細は特許文献1に詳しい。この際、本発明では特に、類似度合いが所定基準（ただし、類似判定自体とは異なる所定基準）で大きい場合は、ある一定の基準重みを付与するようにすることで、双方向エッジに付与される重みに上限を設けるようにしてもよい。
【００５０】
以上のように、各部が求めたノードと単方向／双方向エッジ及びそれらの重みとの集合として、モーショングラフ生成部4はモーショングラフを生成する。こうして、元の動きデータ上で、同一の動きデータ内で隣接しているビートフレーム間は全て時間進行方向の単方向エッジで接続され、当該単方向エッジが接続されておらず且つ似ているビートフレーム間は双方向エッジで接続され、各エッジに重みが付与される。
【００５１】
すなわち、双方向エッジが設定されうる箇所は、[1]同一の動きデータに属するノード間であって単方向エッジが設定されない、すなわち隣接していないノード間と、[2]互いに異なる動きデータに属するノード間である。そして、当該[1]又は[2]に該当する全ノード間のうち対応するポーズ同士が所定基準で類似するものにつき、実際に双方向エッジが設定され、重みが付与される。なおまた、ノード間に単方向エッジと双方向エッジとが同時に設定されることはない。
【００５２】
当該モーショングラフに基づいて新たな動きデータを生成することができる。この際、モーショングラフにおいて隣接するノード間を、単方向又は双方向エッジの定める方向に移動して得られるノードの遷移系列に対応する新たな動きデータが生成される。単方向エッジの定める方向の逆方向へは遷移することができない。双方向エッジにおいては両方向へ遷移可能である。
【００５３】
また、双方向エッジを遷移する際には、図13にて説明したように、その双方向エッジの先に存在する単方向エッジを含めて遷移する。すなわち、双方向エッジとその先に存在する単方向エッジの組み合わせによって遷移し、それが1ビート間隔分の動きを生成することに相当する。これは、図13にて説明したように、双方向エッジで接続された2つのノード間に対応する動きを生成する際に、後に述べるブレンディングという手法で、当該各ノードの前後の動きフレーム情報を利用するためである。逆に言えば、双方向エッジで遷移した先の前後に単方向エッジがないようなノードには遷移できない。
【００５４】
モーショングラフ修正部5は、モーショングラフ生成部4の生成したモーショングラフを、そのグラフ構造に基づいて修正する。なお以下適宜、モーショングラフをグラフと略称する。
【００５５】
グラフ分割部51は、グラフを部分グラフへと分割する。その意義は非特許文献2と同様に次の通りである。上述のとおり従来技術において、固定の閾値のみに基づいて双方向エッジを接続したグラフの場合に動きの滑らかさを担保しようとすると、ループのサイズが小さくなる場合がある。そのグラフを利用して生成された動きは多様性が低い可能性がある。従って、適応的な基準（例えば，当該ノード間の属性によって閾値を変えるなど）によって、双方向エッジを接続判定が行えることが望ましい。その際に1つ1つのノード間に対して適応的な基準を設定するのは難しいため、本発明においてはグラフを部分グラフに分割してその部分グラフ毎に基準を設定する。
【００５６】
グラフ分割部51は具体的には、グラフを強連結成分分解することで、強連結である極大な部分グラフに分割する。グラフが強連結であるというのは、グラフ中の任意の2ノードを選択した際に、あるノードから別のノードへたどり着く道が必ず存在することである。極大な部分グラフとは、強連結である部分グラフが強連結である小さな部分グラフを包含するような場合に、最もノード数が多くなるような部分グラフのことを指す。よって強連結である極大な部分グラフは、モーショングラフから音楽に合うパスを探索した際のループとなりうるものであって、且つサイズが極大となるものである。
【００５７】
図4に、グラフの強連結成分分解を例で示す。(1)まず、任意に始点となるノードを選択し、その始点ノードから深さ優先探索を行う。深さ優先探索において、葉ノードまでたどり着いた後に葉ノードから順次親ノードに戻る際に、当該ノードの全ての子ノードが既に探索済みであれば、もしくは子ノードが存在しなければ、当該ノードに通し番号（ポストオーダー、順番）を割り当て、当該ノードの親ノードに戻り、深さ優先探索を進める。これにより、全てのノードに対して、ポストオーダーが割り当てられる。
【００５８】
(1)ではポストオーダー割り当て前の状態のノードa〜lに対して、ノードaを始点としてポストオーダー1〜8が割り当てられ、次に割り当てられていないeから探索してeにポストオーダ9が割り当てられ、最後にまだ割り当てられていないiから探索して10〜12が割り当てられている。
【００５９】
(2)次に、グラフのエッジの向きを反対にした逆グラフを作成する。(3)この逆グラフにおいて、まだ探索されていない（強連結成分に含まれていない）ノードのうち、最もオーダーが大きいノードを始点として、そのノードから深さ優先探索を行う。深さ優先探索でたどることができたノードが1つの強連結成分であり、これを全ノードが強連結成分に含まれるまで繰り返す。最終的に得られた強連結成分の集合が，強連結である極大な部分グラフである。当該部分グラフの例が(3)においてD1〜D6として示されている。
【００６０】
ノード再接続部52は、グラフ分割部51により得られた複数の強連結成分の間に新たに双方向エッジを設定して、ノード間を接続する。具体的には強連結成分のうち1番大きい（ノード数が最も多い）強連結成分と2番目に大きい強連結成分を選択し、このそれぞれに属するノード間を接続する手法を取ることができる。ここでは、当該接続手法を2種類示す。図5に「最小距離法」に、図7に「閾値制御法」に係るフローチャートを示す。
【００６１】
図5の最小距離法では、1番大きい強連結成分に属する各ノードと、2番目に大きい強連結成分に属する各ノード間の組み合わせで、距離が最小であった2つのノード間を双方向エッジで接続（強連結成分が結合）し、それを新たなグラフとして更新する。なお、ノード間に単方向エッジと双方向エッジとが同時に設定されることを防止するため、各ノード間の組み合せにおいて、既に単方向エッジが設定されているものについては、双方向エッジを設定する候補対象から除外するものとする。
【００６２】
また、ノード間の組み合わせにおいて、どちらか少なくとも一方のノードから出ている単方向エッジが、強連結成分の外に接続されている場合は、双方向エッジを設定する候補対象から除外する。図6に当該除外対象と、除外対象でないものとの具体例を示す。
【００６３】
ここでは2つの強連結成分A及びB間のノードの組み合わせに双方向エッジを設定して接続する場合を例とし、(1)には候補対象から除外し双方向エッジを連続させないようにする例(a)、(b)及び(c)が、(2)には候補対象に含まれ双方向エッジを連続するようにしてもよい例(d)及び(e)が示されている。なお、ノードに付記されている数字はSC(同期限度)である。
【００６４】
(1)に示した候補対象から除外する例では(a)、(b)及び(c)の全てにおいて少なくとも強連結成分Bの側のノードから出ている単方向エッジが当該強連結成分Bの外に接続されている。残り時間が十分に長い際のSCの制約(第一制約)と、双方向エッジの次は必ず単方向エッジで遷移する制約(第二制約)との両制約を考慮すると、これらの双方向エッジにて強連結成分AからBに移動するような遷移による動きが実際に生成されることはない。Bに移動した後、第二制約によってBの外のSCがゼロのノードに遷移せねばならないが、SCがゼロであるノードへの遷移は原則的には第一制約によって禁止されるためである。
【００６５】
なお、SCがゼロであるノードへの遷移は、遷移後の音楽の残り時間がゼロとなるとき、すなわち音楽の終わりとなるときのみに限って例外的に、可能となる。
【００６６】
よって、(1)の例のような双方向エッジは実際の動き生成において双方向エッジとして活用されないので、設けても無意味な双方向エッジとして候補対象から除外する。一方、双方向エッジの両端のノードから出ている単方向エッジが当該ノードの属する強連結成分の内部へ接続されている(2)のような例は、上記両制約のもと実際の動き生成において双方向エッジとして活用されるので、候補対象となる。
【００６７】
図5の最小距離法の説明に戻る。最小距離法では、図6で説明したような候補対象となる組み合わせのうち、1番大きい強連結成分に属する各ノードと、2番目に大きい強連結成分に属する各ノード間の組み合わせで、距離が最小であった2つのノード間を双方向エッジで接続（強連結成分が結合）し、それを新たなグラフとして更新する。
【００６８】
当該更新を続けることで、残りの強連結成分数が0になるか、接続終了指標の値が接続終了閾値の値以上と（十分なループのサイズになれば）、フローは終了する。終了しない間は同様の手順で、双方向エッジの接続を行いグラフを更新していく。接続終了指標は最大強連結成分に属するノードの数でもよいしエッジ数でもよい。また、結合を繰り返した際の回数でもよい。具体的な各ステップは以下の通りである。
【００６９】
(ステップS2)結合回数のカウンタpを初期値0に設定する。(ステップS3)p回結合した現在の状態のグラフGpに対してグラフ分割部51を適用して、強連結成分を求める。なお、当該p回目の結合前のグラフGp-1において最大と2番目の強連結成分を１つの強連結成分としたものがGpにおける強連結成分であるので、図4で説明したようなアルゴリズムを再度適用する必要はない。
【００７０】
(ステップS4)グラフGpにおける強連結成分を含まれるノード数が多い順でソートする。(ステップS5)ソート結果より、ノード数が最大となる強連結成分D_1stを選択する。
【００７１】
(ステップS6)当該p回連結した時点の最大強連結成分D_1stに基づいて算出される接続終了指標M(D_1st)が、当該フローを終了する基準である所定の接続終了閾値THM未満(以下でもよい)であるかを判断し、未満であればフローを継続すべくステップS7へ進み、未満でなければステップS11へ進んでフローを終了する。
【００７２】
ここで、接続終了指標M(D_1st)は、当該D_1stに含まれるノード数n=n(p)、当該D_1stに含まれるエッジ数e=e(p)及び当該時点での結合回数pの所定関数fとして次のように算出される。
M(D_1st) ＝ f(n, e, p)
【００７３】
特に、関数fはn,e,pの３変数関数ではなくて、それらのうちの1変数のみ又は2変数の関数であってもよい。通常、関数fはn, e, pのいずれに関しても増加関数として設ける。また接続終了閾値THMは定数として設けておけばよい。
【００７４】
(ステップS7)ノード数最大のD_1stに対して、ノード数が2番目に多い強連結成分D_2ndをステップS4のソート結果より選択する。
【００７５】
(ステップS8)当該最大のD_1stに属するノードと2番目のD_2ndに属するノードとの組み合わせのうち、図6で説明した候補対象となる組み合わせについてノード間距離を求め、距離が最小となるノードの間に双方向エッジを設定する。当該距離は双方向エッジ設定部43で説明したのと同様のポーズ間距離を用いる。さらにステップS8では当該設定した双方向エッジに、双方向エッジ設定部43で説明したのと同様の重みを付与し、当該追加設定した双方向エッジ及び重みをグラフGpに追加することで、次の処理対象としてのグラフGp+1となす。
【００７６】
(ステップS9)結合回数カウンタpを１だけ増分する。(ステップS10)結合回数カウンタpが所定の上限回数P未満であるか判断し、未満であればステップS3に戻ってフローを継続する。未満でなければステップS10に進んでフローを終了する。
【００７７】
上述の例では、距離が最小となるノード間を接続する場合について述べたが、最小値に限らず最大値、中央値又は平均値をとったノード間を接続してもよい。なお、距離の最小値はノード間類似度の最大値に、距離の最大値はノード間類似度の最小値に対応する。
【００７８】
一方、図7の閾値制御法を以上の図5の最小距離法との差異点を抽出して説明すると次の通りである。
【００７９】
[図5のステップS8に対して図6のステップS80]1番大きい強連結成分D_1stに属する各ノードと、2番目に大きい強連結成分D_2ndに属する各ノード間の組み合わせであって図6で説明した候補対象となる組み合わせの距離が、双方向エッジの接続判定閾値TH_pより小さい全ての組み合わせを双方向エッジで接続する。重みは同様に付与する。
【００８０】
[図5のステップS2に対して図6のステップS20]上記ステップS80にて用いる接続判定閾値TH_pは、毎回同じの定数としてではなく複数設定し、結合が繰り返される度に更新されるようにする。すなわち、フローを開始するに際して予め各p回における閾値TH_pを閾値集合TH={TH_0, TH_1, ..., TH_P-1}として設けておく。例えば、TH_0を定めた上で、各p=0, 1, ..., P-1につき次のようにする。
TH_p+1 ＝ r*TH_p    (ここでrはr>1の定数)
【００８１】
こうすれば、1回目の接続判定においては「慎重に」双方向エッジを設定するため、厳しめの（小さい）接続判定閾値を設定し、繰り返される毎に定数rを乗じて段々緩めていく（大きくしていく）ことができる。これら接続判定閾値は、ユーザ（動き生成装置1の提供者）が適当に設定する。定数rを乗ずる以外にも、「TH_p+1 ＞ TH_p」の関係があるような任意の閾値集合を設定してよい。
【００８２】
その他の、例えば図5のステップS3に対して図7のステップS30等、類似の番号を付してあるステップについては共通である。なお、図5のステップS8及び図7のステップS80における別実施例として、D_1stのノードとD_2ndのノードとの間で図6の候補対象となるものの距離を求めて所定のノード間に双方向エッジ及び重みを付与する代わりに、D_1stのノードとD_2nd以下すなわちノード数の多さが2番目以降の全ての強連結成分のノードとの間で図6の候補対象となるものの距離を求めて同様に双方向エッジ及び重みを付与するようにしてもよい。また、2番目以降の全てではなく2番目以降所定のn番目までとしてもよい。
【００８３】
以上のように、図5または図7のフローによって本発明では次のような効果が得られる。すなわち、ループ内の遷移による動きの滑らかさは保持した上で、ループのサイズを拡大することができるため、その修正されたモーショングラフを利用して動きを生成した場合に一定の滑らかさを維持した上で多様性が向上する。
【００８４】
図5の場合と図7の場合の違いは、その効果に関して次の通りである。図5の場合、ループ間で最小距離をとるノード間を接続するため、ループ間を遷移する場合は滑らかさが損なわれる可能性もあるが、そのような遷移の発生を最小限に抑えることができる。また新たに閾値設定する必要がないため、パラメータ設定が容易となる。
【００８５】
図7の場合、ループ間で所定の接続判定閾値を満たすノード全ての組みが接続されるため、動きの多様性が向上しやすい。動きの滑らかさに関しては接続判定閾値をどう設定するかによるが、適切な接続判定閾値が設定することでループ間で多くの双方向エッジが接続される。よって、動きの滑らかさを一定に保ったまま図5の場合よりも多様性の向上に重点を置くことができる。
【００８６】
図8及び図9はそれぞれ、図5及び図7のフローを適用する例を示す図であり、両図において各フローを適用する前の、モーショングラフ生成部4の出力したグラフG0が(1)に示されており、当該グラフの例は図3の(3)で示したのと同様(ただし、逆グラフから元の向きに戻してある)である。
【００８７】
図8の(2)は一回目の接続により、D_1stであるD1に属するノードgと、D_2ndであるD2に属するノードjとの間に新たに双方向エッジが設けられ、グラフG0がG1へ更新されている。さらに２回目の接続により、D_1stであるD1∪D2に属するノードhと、D_2ndであるD3に属するノードdとの間に新たに双方向エッジが設けられ、(3)に示すようにグラフG1がG2へ更新されている。なお、図示していないが、ノードd及びhはそれぞれ自身より出て自身と同じ強連結成分に属するノードに至る単方向エッジが接続されているものとする。
【００８８】
図9の(2)は一回目の接続により、D_1stであるD1に属するノードg及びhと、D_2nd以降の1つの強連結成分であるD2に属するノードjとの間で合計2本の新たな双方向エッジが設けられ、グラフG0がG1へ更新されている。さらに２回目の接続により、D_1stであるD1∪D2に属するノードhと、D_2nd以降の1つの強連結成分であるD3に属するノードdとの間で合計2本の新たに双方向エッジが設けられ、(3)に示すようにグラフG1がG2へ更新されている。なお、図示していないが、ノードd及びhはそれぞれ自身より出て自身と同じ強連結成分に属するノードに至る単方向エッジが接続されているものとする。なおまた当該例では、D_2nd以降の1つの強連結成分との間で接続されているが、2つ以上の強連結成分との間で接続される場合もある。
【００８９】
本発明の特徴的構成であるノード再修正部53では、ノード再接続部52によって修正されたモーショングラフ(再接続を施されたモーショングラフ)に対して、または、ノード再接続部52の適用を省略した未修正のモーショングラフ（モーショングラフ生成部4によって生成された時点におけるモーショングラフ）に対して、エッジの接続(すなわちノード間接続)を再修正することで、モーショングラフを修正する。すなわち、ノード再接続部52の適用はオプションであって省略してもよいが、適用した場合は、前述のような動きの滑らかさと多様性とをさらに増す効果が得られる。
【００９０】
ノード再修正部53の適用の意義は次の通りである。グラフの構造的には強連結であり本来ならばその内部の全ノードを偏りなく遷移できるはずのノード群であっても、図13で説明したパス遷移の制約により、強連結な部分グラフのうちの一部のノードのみしか遷移できなくなる（局所的なループに陥る）場合がある。
【００９１】
そこで、ノード再修正部53は局所的なループを解消すべく、図13のパスの制約を考慮しない条件においてグラフの構造的に強連結であるような部分グラフに対して、エッジの接続を再修正することによってグラフの再修正を行う。なお前述の通り、再修正するグラフは、ノード再接続部52で修正されたモーショングラフであってもよいし、当該修正を施さない状態のモーショングラフであってもよい。また、修正しない場合であっても、グラフ分割部51を適用して強連結成分を求めておいてからノード再修正部53を適用するものとする。
【００９２】
図10は、当該局所ループの発生例や、ノード再修正部53による当該局所ループの解消を説明するための図である。(1)及び(2)におけるノード2が、局所ループを発生させてしまう要因となるノードの例である。局所ループ発生要因ノードは、複数の双方向エッジが接続されているが、図13の制約によって、当該複数の双方向エッジのうちの一部分しか実際の動き生成に際しては利用されないようになってしまうノードである。
【００９３】
具体的には、当該ノードには双方向エッジが複数接続されているものの、当該ノードから単方向エッジで辿れる先のノード群に関して、当該ノードよりも後のノードに接続される双方向エッジ以外しか持たない場合に、複数接続された双方向エッジのうちの一部分のみしか動き生成に利用されなくなる局所ループに陥ることがある。
【００９４】
(1)の例では、一度「1→2→3」と遷移すると、その後は「(2→3→4)→(2→3→4)→…」という局所ループに陥る。図13の制約により双方向エッジによる遷移「4→2」の後は必ず単方向エッジによる遷移「2→3」で遷移せねばならず、「(2→3→4)→2→7」や「(2→3→4)→2→8」の動きは生成できないためである。すなわち、ノード2には3つの双方向エッジ「2−4」、「2−7」及び「2−8」が接続されているが、「2−4」のみしか動き生成時には選択されなくなる場合があるので、ノード2は局所ループ発生要因ノードである。
【００９５】
なお、ノード7及び8はそれぞれノード2以外にも接続先ノードを有し、それらの接続先ノードからさらに先への遷移を可能とするが、(1)においてはノード2を原因とする
局所ループの説明部分を強調するために図示を省略している。後述の(2)、(10)、(20)及び(21)についても同様である。
【００９６】
(2)の例でも同様に、一度「1→2→3」と遷移すると、その後は「(2→3→4)→(2→3→…)」又は「((2→3→4→5)→(2→3…))」という局所ループに陥る。すなわち、ノード2には4つの双方向エッジ「2−4」、「2−5」、「2−7」及び「2−8」が接続されているが、「2−4」及び／又は「2−5」のみしか動き生成時には選択されなくなる場合があるので、ノード2は局所ループ発生要因ノードである。
【００９７】
一方、(3)のノード2は、接続されている2つの双方向エッジ「2−4」及び「2−5」が図13の制約を課しても全て選択されうるので、局所ループ発生要因ノードではない。
【００９８】
こうした(1)(2)のような局所ループ発生を解消すべく、ノード再修正部53はグラフの再修正を行う。具体的には、[1]局所ループ発生要因ノードの検出と、[2]局所ループ改善のためのノード再接続と、の2ステップで行う。具体的なステップは、それぞれ以下のとおりである。
【００９９】
[1]局所ループ発生要因ノードの検出
全ノード(i)を対象に、以下の＜手順1＞〜＜手順5＞にて示される操作を行う。
【０１００】
＜手順1＞当該ノード(i)について、次の命題１が真ならば＜手順2＞へ進み、偽ならば当該ノード(i)は局所ループ発生要因ノードではないと判定して＜手順5＞へ進む。
【０１０１】
[命題1] 当該ノード(i)には、もう一方のノードが(k)である双方向エッジ(i,k)が少なくとも1つ接続されており、且つノード(k)には、当該ノード(i)から単方向エッジのみをその方向に従って辿り着くことができない。
【０１０２】
命題1はすなわち、当該ノード(i)には、当該ノード(i)より単方向エッジのみでは辿り着くことができない先のノード(k)に対して接続される双方向エッジ(i,k)が少なくとも1つ接続されている、というものである。
【０１０３】
＜手順2＞当該ノード(i)について、次の命題2が真ならば＜手順3＞へ進み、偽ならば当該ノード(i)は局所ループ発生要因ノードではないと判定して＜手順5＞へ進む。
【０１０４】
[命題2]当該ノード(i)には、命題1における双方向ノード(i,k)とは別に、そのもう一方のノード(j)が当該ノード(i)より単方向エッジのみをその方向に従って辿り着くことのできるノード(j)であるような、双方向ノード(i,j)が少なくとも１つ接続されている。
【０１０５】
命題2はすなわち、該ノード(i)には、当該ノード(i)より単方向エッジのみで辿り着くことができる先のノード(j)に対して接続される双方向エッジ(i,j)が少なくとも1つ接続されている、というものである。
【０１０６】
＜手順3＞当該ノード(i)について、次の命題3が真ならば＜手順4＞へ進み、偽ならば当該ノード(i)は局所ループ発生要因ノードではないと判定して＜手順5＞へ進む。
【０１０７】
[命題3]当該ノード(i)より単方向エッジのみで遷移した先(x)に、当該ノード(i)以外を端のノード(y)として有する双方向エッジ(x,y)が存在しない、または、そのような双方向エッジ(x,y)が存在していて、かつその双方向エッジ(x,y)が当該ノード(i)より先の単方向エッジを辿れるノード(y)にのみ接続されている。
【０１０８】
命題3の「または」部分以降はすなわち、そのような双方向エッジ(x,y)が存在していて、一方のノード(x)が当該ノード(i)から単方向エッジで辿れる先であるのに対して、もう一方のノード(y)が次の(3−1)にも(3−2)にも該当しない、というものである。
(3−1)ノード(y)は、当該ノード(i)より前に接続する、すなわち当該ノード(i)より単方向エッジのみを逆方向に辿った先のノードである。
(3−2)ノード(y)は、当該ノード(i)の元の動きデータとは別の動きデータに属するノードである。
【０１０９】
＜手順4＞当該ノード(i)は局所ループ発生要因ノードであると判定し、＜手順5＞へ進む。
【０１１０】
＜手順5＞全ノードにつき局所ループ発生要因ノードであるか否かの判定が終了していれば、「[1]局所ループ発生要因ノードの検出」を終了し、終了していなければ、未判定の次の対象ノード(i+1)につき、＜手順1＞を実行する。
【０１１１】
[2]局所ループ解消のためのノード再接続
上記[1]で検出された全ての局所ループ発生要因ノードに対して、以下の＜手順A＞〜＜手順C＞にて示される操作を行う。 
【０１１２】
＜手順A＞当該局所ループ発生要因ノードから、単方向エッジで辿れる先に遷移可能な双方向エッジが2つ以上存在すれば＜手順B＞へ進み、1つしか存在しなければ、その双方向エッジを削除することで、当該局所ループ発生要因ノードによる局所ループを解消した後に＜手順C＞へ進む。
【０１１３】
例えば、図10の(1)の局所ループ発生要因ノード2については、単方向エッジで辿れる先に遷移可能な双方向エッジが(2,4)の1つしか存在しないので、(10)に示すように、当該双方向エッジ(2,4)を削除を削除することによって、局所ループを解消する。
【０１１４】
＜手順B＞当該局所ループ発生要因ノードから単方向エッジで辿れる先へ接続している2つ以上の双方向エッジの接続先のうちの１つと、当該ノードの1つ前のノード（１つの単方向エッジで当該ノードに辿り着くノード）とを双方向エッジで接続することによって、局所ループを解消した後に＜手順C＞へ進む。
【０１１５】
この際、2つ以上ある双方向エッジの接続先のうち、当該局所ループ発生要因ノードから最も遠い（単方向エッジで遷移数が最大）ノードを対象とすることで、より滑らかなも動きが少しでも長く継続して生成されるようにしてもよい。例えば図10の(2)の局所ループ発生要因ノード2に対して、最も遠いノード5と、当該ノード2の1つ前のノード1とを(20)に示すように双方向エッジで接続することによって、局所ループを解消する。
【０１１６】
逆に最も近い(単方向エッジで遷移数が最小)ノードを対象として、より多様な動きを生成させるようにしてもよい。また、2つ以上ある双方向エッジの接続先のうちの１つではなく全てと、当該局所ループ発生要因ノードの１つ前のノードとを双方向エッジで接続するようにしてもよい。
【０１１７】
またこの際、1つ前のノードと接続する代わりに、当該局所ループ発生要因ノードから双方向エッジのみで遷移可能なノード(単方向エッジで辿り着けないノード)と接続してもよい。例えば図10の(2)の局所ループ発生要因ノード2による局所ループを(20)に示すように解消する代わりに、(21)に示すように、当該ノード2から双方向エッジ(のみ)で遷移可能なノード7及び8のうち例えばノード8と接続することによって、局所ループを解消する。
【０１１８】
(21)のように解消した場合、「2→3」と遷移した後に「4→2→8」又は「5→2→8」の遷移が起こることはないが、ループ後の「2→8」が不可能なため遷移できなかったノード8の側へと「5→8」によって遷移可能となるので、(20)と比べていわば間接的に局所ループを解消することとなる。
【０１１９】
なお、当該局所ループ発生要因ノードから双方向エッジのみで遷移可能なノードが複数ある場合、それらの全てとの間で双方向エッジを設けてもよい。さらに追加して、単方向エッジで逆向きに辿った１つ前のノードと当該局所ループ発生要因ノードとの間にも双方向エッジを設けて(20)と(21)の両者を同時に適用するようにしてもよい。
【０１２０】
以上まとめると、＜手順B＞では以下のグループ1のノードのいずれかとグループ2のノードのいずれかとの任意の組み合わせを両端として有する新たに双方向エッジを設けることができる。これら組み合わせの全てに対して双方向エッジを設けてもよいし、その一部分にのみ設けてもよい。
【０１２１】
[グループ1]局所ループ発生要因から単方向エッジで辿る先のノードであって、当該ノードと局所ループ発生要因ノードとの間に双方向エッジが接続されているノード
[グループ2]局所ループ発生要因の1つ前のノード(当該ノードから1つの単方向エッジで局所ループ発生要因ノードに到達するノード)、局所ループ発生要因ノードから双方向エッジのみで遷移可能なノード
【０１２２】
なおまた、上記まとめのように1つの局所ループ発生要因ノードに対して複数の双方向エッジを設ける代わりに、これら複数の双方向エッジにおける当該局所ループ発生要因ノードともう一方のノードとに対して双方向エッジ設定部43と同様にして算出される類似度に基づく重みが最大(ノード間の距離が最小)のものを選ぶようにしてもよい。
【０１２３】
＜手順C＞全ての局所ループ発生要因ノードについて再接続による局所ループの解消処理が終了していれば、「[2]局所ループ解消のためのノード再接続」は終了する。そうでなければ、未処理の局所ループ発生要因ノードを対象として＜手順A＞に戻って繰り返す。
【０１２４】
このように、再接続には＜手順A＞にて双方向エッジを削除する場合と、＜手順B＞にて新たな双方向エッジを設ける場合とがある。＜手順B＞にて新たな双方向エッジを設ける場合は、双方向エッジ設定部43で算出される類似度に基づく重みを当該エッジに付与するものとする。
【０１２５】
なお、＜手順B＞にて図10の(20)に示したように当該ノードの(2つ前や3つ前などではなく)1つ前と接続することで、当該ノードに時間的に近い方が似ている可能性が高く、滑らかな動きが生成されると共に、利用されていない双方向エッジを速やかに利用させるようにするという効果を、グラフの微修正によって得ることができるようになる。同様に＜手順B＞にて双方向エッジ(のみ)で遷移可能なノードに接続する場合も、利用されていない双方向エッジの側への遷移がグラフの微修正によって可能になるという効果がある。
【０１２６】
なお、＜手順A＞にて削除することで局所ループを解消する別実施例として、単方向エッジで辿れる先に遷移可能な1つのみ存在する双方向エッジを削除する代わりに、当該双方向エッジの単方向エッジで辿れる先を一端として有する新たな双方向エッジを＜手順B＞と同様に1つまたは複数設けるようにしてもよい。例えば図10の(1)の局所ループを解消するために、双方向エッジ(2,4)は削除せずそのまま残しておいて、新たに双方向エッジ(1,4)又は(4,8)若しくは(4,7)のいずれか少なくとも１つを設けるようにしてもよい。
【０１２７】
音情報解析部2は、音楽ファイルや音声ファイルなどとして入力された音情報に対して、音のビートや音の盛り上がり情報などの特徴量の抽出を行う。具体的には例えば、音楽ファイルや音声ファイルから入力された音情報データより、以下の非特許文献3で示される手法を利用して、ビートの時刻と、ビートの間隔と、各ビート区間における盛り上がりの音特徴量とを抽出することができる。
【０１２８】
[非特許文献3] M.Goto，"An Audio-based Real-time Beat Tracking System for Music With or Without Drum-sounds"，Journal of New Music Research，2001
【０１２９】
動き生成部6では、音情報解析部2で得られた音特徴量に基づき、モーショングラフ修正部5で修正して生成された新たなモーショングラフを利用して、音楽に合わせた動きを生成する。
【０１３０】
具体的には、まず同期部61が、音の最初のビート時刻において、モーショングラフの初期ノードから遷移するパスを決定する（音と動きの先頭の同期をとる）。ここで初期ノードには、元の個別の動きデータの最初のビートフレームに相当するノードが選択される（複数動きデータがあれば、そのいずれかから選択する）。遷移するパス（生成する動き）は、特許文献1や非特許文献1に示されているように、音の盛り上がり方と動きの盛り上がり方（単方向エッジの重み）がパタンとして似ている（両者の差分が小さい）かによって決定される。
【０１３１】
具体的には同期部61は、特許文献1に示されているように、音と動きの盛り上がりに関するコスト関数を定義し、始点から遷移候補ノードに遷移するまでに累積するコストが最小となるパスを動的計画法によって求め、最適パスとして選択する。その際に、双方向エッジで遷移する際には、上述の双方向エッジにおいて重み（閾値で下限設定）がペナルティとして作用する。さらにコスト関数を、２回以上経過するエッジのコストが高くなるよう、例えば既に通過した回数の多さや、直前に通過した時点からの遷移数の少なさに応じて高コストとなるよう設計してもよい。
【０１３２】
なお、図12で説明したSC(同期限度)や、図13で説明したような双方向エッジを連続して遷移しないようにする制限は、当該コスト関数に盛り込まれる。
【０１３３】
合成部62は、この最適パスでモーショングラフ上のノード間を遷移しながら、各ノードに対応する動きデータの断片を連結することによって新たな動きデータを生成する。実際には、ノード自体はビートフレームのポーズを表しているため、遷移に伴う動きデータ断片の連結によって動きが生成されることになる。
【０１３４】
当該連結に際して、単方向エッジによる遷移であれば、ビートフレーム間のフレームが実際に存在するため、それをそのまま生成すべき動きデータの各断片として利用して連結すればよい。こうして、ある１つの動きデータから抽出されたノードを単方向エッジによって順次遷移するパスに対しては、合成部62は当該元の動きデータと一致する動きデータを生成する。
【０１３５】
しかしながら遷移パスが双方向エッジの場合は、ビートフレーム同士は異なる動きデータに属するものであるか、同一の動きデータに属しても隣接していないものである。すなわち、当該ビートフレーム間のフレームは実際には存在しない。そこで、合成部62は当該フレームを合成する。その際に、ブレンディングという技術を用いる。ビートフレーム及びその前後のフレームを考慮して、両者の間で平均化を施すことによって、ある動きから別の動きに遷移する際の動きを滑らかに生成することができる。これには、特許文献1と同様の手法を用いればよい。
【０１３６】
動き再生部7は、動き生成部6で生成された新たな動きデータを、ＰＣのディスプレイや携帯端末などで音情報と共に提示する。ユーザによって選択された音情報を再生しつつ、動き生成部で生成された音情報と同期し、かつ音の盛り上がりと動きの盛り上がりも相関のある動きを、適当に選択された3Dキャラクタ（CGモデル）が行っている映像を再生する。音のビートと動きデータのビート(ノード)との同期に際して、動きデータの時間軸を適宜伸縮してよい。
【０１３７】
以上のように、本発明によれば、音と同時にキャラクタの動きを再生可能なコンテンツを楽しむユーザにとっては、従来の動きの滑らかさを維持した上で、その多様性が向上するため、飽きずにコンテンツを見ることができる。技術的には、動き生成時の制約（パスの遷移による制約）を考慮した上で、元のモーショングラフの構造をある程度保ちつつモーショングラフのループサイズの制御や局所ループに陥らないためのグラフ構造を制御することが可能である。
【０１３８】
すなわち、グラフ構造的特性のみを考慮するのではなく、そのモーショングラフを利用して動きを生成する際のパス遷移の制約を考慮した上で、モーショングラフを再構築し、当該再構築されたモーショングラフから動きデータを生成することで、滑らかであり且つ多様な動きデータを生成することができるようになる。
【０１３９】
図11は、本発明の一実施形態に係る動き生成装置1の機能ブロック図である。当該実施形態では、動き生成装置1は、モーショングラフ生成部4、モーショングラフ修正部5及び動き生成部6を備える。当該各部の機能は以上説明してきたものと同様である。図1の構成との差異が次の[A]〜[C]の通りである。
【０１４０】
[A]動きデータベース3を備える代わりに(1)に示すように、動きデータベース3に保存されているのと同様な複数の動きデータをモーショングラフ生成部4で読み込むようにする。
【０１４１】
[B]音情報解析部2を備えて入力音を解析する代わりに(2)に示すように、予め区間分けされ特徴量が各区間に定義された所定の時系列データ(有限長)を、動き生成部6で読み込むようにする。当該時系列データは音情報に限らず、任意の種類のデータが利用できる。当該各区間で定義された特徴量を前述の音情報の場合における各ビート区間の盛り上がりに相当するものとして扱うことで、動き生成部6は前述の場合と同様に動きを生成することができる。
【０１４２】
[C]動き再生部7を省略して(3)に示すように、動きデータを出力させるようにする。
【０１４３】
すなわち、本発明は音情報に限定されず、上記のような形式を有する所定の時系列データであれば、データの種類を問わず適用可能であって、当該任意の種類の時系列データに基づいて当該時系列データにおける特徴量の変化系列に即した動きデータを生成することができる。特徴量には、当該時系列データの種類に応じた所望のものを採用することができ、予めそのような特徴量を求めて時系列データに対応づけておけばよい。
【符号の説明】
【０１４４】
1…動き生成装置、2…音情報解析部、3…動きデータベース、4…モーショングラフ生成部、5…モーショングラフ修正部、6…動き生成部、7…動き再生部、41…キーフレーム抽出部、42…単方向エッジ設定部、43…双方向エッジ設定部、51…グラフ分割部、52…ノード再接続部、53…ノード再修正部、61…同期部、62…合成部
【図１】
2013218480.tif 000003
【図２】
2013218480.tif 000004
【図３】
2013218480.tif 000005
【図４】
2013218480.tif 000006
【図５】
2013218480.tif 000007
【図６】
2013218480.tif 000008
【図７】
2013218480.tif 000009
【図８】
2013218480.tif 000010
【図９】
2013218480.tif 000011
【図１０】
2013218480.tif 000012
【図１１】
2013218480.tif 000013
【図１２】
2013218480.tif 000014
【図１３】
2013218480.tif 000015