(57)【要約】【課題】モーショングラフを利用した動き生成において、動きの滑らかさと多様性とを両立した動きを生成することのできる動き生成装置及び方法を提供する。【解決手段】モーショングラフ生成部4は、動きの滑らかさを確保できる第一のモーショングラフを構築する。モーショングラフ修正部5は、第一のモーショングラフを修正して新たな双方向エッジを設定し、動きの多様性をも確保できるような第二のモーショングラフへと修正する。動き生成部6は入力時系列データに合った動きデータを第二のモーショングラフを探索して構築する。第二のモーショングラフにおける双方向エッジ設定には、強連結成分分解によって得た部分グラフの間においてエッジ設定を行う。【選択図】図9
2013120479.tif 000002
【特許請求の範囲】
【請求項１】
予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成装置であって、
複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成部と、
前記第一のモーショングラフの各ノードをグループに分類し、互いに異なるグループに属し且つ類似するノード間にエッジを設けて第二のモーショングラフを生成するモーショングラフ修正部と、
前記第二のモーショングラフに基づいて、前記所定の時系列データに即した動きデータを生成する動き生成部とを備えることを特徴とする動き生成装置。
【請求項２】
前記モーショングラフ生成部は、
前記複数の動きデータの各々より各動きデータの時間変化に基づいて複数のキーフレームを抽出してノードとなすキーフレーム抽出部と、
同一の動きデータに属して隣接するノード間に単方向エッジを設ける単方向エッジ設定部と、
互いに異なる動きデータに属して第一の所定基準で類似するノード間と、同一の動きデータに属しており且つ隣接しておらず前記第一の所定基準で類似するノード間と、に双方向エッジを設ける双方向エッジ設定部とを含み、
当該ノードと、単方向及び双方向エッジとによって前記第一のモーショングラフを生成することを特徴とする請求項1に記載の動き生成装置。
【請求項３】
前記単方向エッジ設定部は、同一の動きデータに属して隣接するノード間に時間方向の単方向エッジを設けると共に、当該同一の動きデータのうち当該ノード間に存在するデータの時間変化に基づく重みを付与し、
前記双方向エッジ設定部は、互いに異なる動きデータに属して前記第一の所定基準で類似するノード間及び同一の動きデータに属して単方向エッジが設けられておらず前記第一の所定基準で類似するノード間に双方向エッジを設けると共に、当該類似する度合いに基づく重みを付与し、
前記モーショングラフ生成部は当該ノードと、単方向及び双方向エッジ並びにその重みとによって前記第一のモーショングラフを生成することを特徴とする請求項2に記載の動き生成装置。
【請求項４】
前記単方向エッジ設定部は、前記同一の動きデータのうち前記ノード間に存在するデータに対応する動きの活発さに基づく重みを付与することを特徴とする請求項3に記載の動き生成装置。
【請求項５】
前記モーショングラフ修正部は、
前記第一のモーショングラフを複数の部分グラフへと分割するグラフ分割部と、
前記複数の部分グラフのうちの異なるものに属し且つ第二の所定基準で類似するノード間に前記第二のモーショングラフを生成するための双方向エッジを設けると共に、当該類似する度合いに基づく重みを付与するノード再接続部とを含むことを特徴とする請求項3または4に記載の動き生成装置。
【請求項６】
前記グラフ分割部が強連結成分分解によって前記第一のモーショングラフを複数の部分グラフへと分割することを特徴とする請求項5に記載の動き生成装置。
【請求項７】
前記ノード再接続部が、前記分割された複数の部分グラフのうちのノード数が最大となる部分グラフの各ノードと、それ以外の部分グラフに属する各ノードとの間で前記第二の所定基準で類似するノード間に前記双方向エッジを設けることを特徴とする請求項5または6に記載の動き生成装置。
【請求項８】
前記ノード再接続部が、前記分割された複数の部分グラフのうちのノード数が最大となる部分グラフの各ノードと、ノード数が２番目に多い部分グラフに属する各ノードとの間で前記第二の所定基準で類似するノード間に前記双方向エッジを設けることを特徴とする請求項7に記載の動き生成装置。
【請求項９】
前記第二の所定基準がノード間の類似度のうちの最大、最小、中間値又は平均値のいずれかであることを要求する基準である、または前記第二の所定基準がノード間の類似度が所定の閾値条件を満たすことを要求する基準であることを特徴とする請求項5ないし8のいずれかに記載の動き生成装置。
【請求項１０】
前記ノード再接続部が、前記第二の所定基準で類似するノード間に前記双方向エッジを設ける都度、当該双方向エッジを設けられた部分グラフ同士を単一の部分グラフに更新すると共に、当該更新された部分グラフのもとで前記第二の所定基準で類似するノード間に前記双方向エッジを設けることを繰り返すことを特徴とする請求項5ないし9のいずれかに記載の動き生成装置。
【請求項１１】
前記第二の所定基準が、前記部分グラフを更新する回数又は前記部分グラフのうちのノード数が最大となる部分グラフのノード数若しくはエッジ数のうちの少なくとも1つの関数であることを特徴とする請求項10に記載の動き生成装置。
【請求項１２】
前記動き生成部は、
前記第二のモーショングラフ内の各パスの中から、各パスに順次現れるエッジの重みと前記所定の時系列データの各区間に順次現れる特徴量とに所定の関数を適用して得られるコストを最小とするパスを動的計画法により求め、前記所定の時系列データに同期するパスとして決定する同期部と、
前記同期するパスに順次現れるノードに対応する前記複数の動きデータの断片を順次連結し、双方向エッジの両端のノードに対応する断片同士を当該連結する際には平均化を施すことで前記所定の時系列データに即した動きデータを生成する合成部とを含むことを特徴とする請求項5ないし11のいずれかに記載の動き生成装置。
【請求項１３】
予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成方法であって、
複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成ステップと、
前記第一のモーショングラフの各ノードをグループに分類し、互いに異なるグループに属し且つ類似するノード間にエッジを設けて第二のモーショングラフを生成するモーショングラフ修正ステップと、
前記前記第二のモーショングラフに基づいて、前記所定の時系列データに即した動きデータを生成する動き生成ステップとを備えることを特徴とする動き生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き生成に関し、特に、一旦構築したモーショングラフをそのループ構造に基づいて再構築することで、より多様な動きの生成を可能とする動き生成装置及び方法に関する。
【背景技術】
【０００２】
動きデータの一種として、MoCap(Motion Capture；モーションキャプチャ)データがある。MoCapデータの収録は、画像や映像データの取得に比べてコストがかかる。そのため、新たな動きの生成するために、元のMoCapデータを組み合わせて再利用することが行われる。その際に、短時間の動き要素の間の関係をMotion Graph(モーショングラフ)と呼ばれるグラフ構造で表現する方法がある。
【０００３】
特許文献1では、音楽と同期した動きを自動生成するために、事前に収録された動きの構造を考慮可能なMotion Graphを利用している。事前に、MoCapデータから動きのビートを抽出し、そのビートフレームをグラフのノードとする。元のMoCapデータで連続しているビートフレームを表すノード間は、時間軸に沿って単方向エッジで接続する。一方で、連続していないノード間は、ビートフレームの類似度の大きさにより、双方向エッジで接続し，類似度の大きさを双方向エッジの重みとして与える。
【０００４】
さらに、MoCapデータから取得される動きの盛り上がり情報によって単方向エッジに重みを与えることで、Motion Graphが構築される。このMotion Graphを利用することで、入力された音楽から抽出されるビートと動きのビートを合わせた上で、音楽の盛り上がりの傾向と似ている盛り上がりのパタンを持つ動きを、エッジ接続されたノード間のみを遷移することで、音楽と同期しかつ滑らかな動きを生成可能としている。
【０００５】
非特許文献1では、Motion Graphのフレームワークを利用した音楽と同期した動きの自動生成において、音楽の残り時間がMotion Graph上で遷移可能な時間（デッドエンド（遷移するパスがないノード）に到達するまでの時間）が短い場合に動きが生成できなくなる問題を指摘しており、その改善のためにSynchronization Capacityという制約を導入することで、音楽の残り時間に対して最後まで動きを生成可能なノードのみを遷移候補として選択できるようにすることで、デッドエンドへの到達回避の保証をしている。
【０００６】
図10は、当該非特許文献1に紹介された音楽の残り時間に対して，動きが必ず生成できることを保証するためのパラメータとしてのSynchronization Capacity（SC）の概要を示す図である。音楽に同期した動きを生成する場合、音楽より早く動きが終わってしまうことは好ましくない。そのため、音楽と少なくとも同じ長さの動きを生成できることが望まれる。そこでSCを導入する。具体的には、各ノードに対して自身から遷移可能なノードの数の最大値としてSCを定義する。図10では、○として示す各ノード内に記載された数がSCである。
【０００７】
例えば、グラフ中のループに含まれるノードに関して言えば、永続的に遷移可能となるため、SC=∞となる。ループ外にあるノードで、遷移可能なエッジの先にループが含まれる場合も同様である。しかし、遷移可能なエッジの先にループが含まれない場合そのノードのSCは、デッドエンドに到達するまでに遷移できるノードの最大数である。
【０００８】
音楽が入力されて、ある時刻において音楽の残り時間がわかると、その残り時間だけ遷移可能なノードのみが、遷移候補ノードとして選ばれることになる。例えばある現在時刻におけるノードが図10のN1であって、音楽の残り時間が2ノードの長さ未満であれば、遷移候補ノードは同図のN2及びN3の部分のノードとなるが、音楽の残り時間が2ノードの長さ以上であれば、遷移候補ノードはN3の部分のノード（N3のうち、SCが0のデッドエンドノード（一番右端のノードを除く）のみとなる。
【０００９】
従って、音楽が無限時間だけあると考えると、ループ中に含まれる（その先にループを持つ）ノードのみに遷移することになる。この制約により、音楽が終了する前に動きの生成ができなくなる現象を防ぐことはできる。しかしながら、ループを形成しているノード群（部分グラフ）のみに遷移が集中するため、ループに含まれるノード数が少ない（ループサイズが小さい）場合、同じような動きが頻発する。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開 2010-267069号公報
【非特許文献】
【００１１】
【非特許文献１】J. Xu et al., "MOTION SYNTHESIS FOR SYNCHRONIZING WITH STREAMING MUSIC BY SEGMENT-BASED SEARCH ON METADATA MOTION GRAPHS," IEEE ICME, 2011
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上記のようにSC=無限大のノード群のみを遷移候補として、短時間のループ内で同じ動きが繰り返される現象が頻発すると、コンテンツとして単調なものになるという点で問題となる。従って、ループサイズは大きいことが望ましい。その一方で、コンテンツとして不自然にならないよう動きの滑らかさを担保するために、特許文献1及び非特許文献1の従来技術では固定の閾値に基づき双方向エッジ接続判定をしている。当該双方向エッジで接続された部分がループとなるため、固定の閾値を緩める（大きくする）ことによって、双方向エッジで接続される箇所を増加させ、ループサイズを大きくすることは可能である。しかしながら、その閾値を緩めることによって、本来似ていないポーズ同士からも動きを生成可能となるため、動きの滑らかさが失われるという問題がある。
【００１３】
また、当該閾値は、ビートフレーム間での遷移によって生成される動きの滑らかさを担保するためのものであり、エッジ接続判定に用いる閾値はグラフで固定値である。このため従来技術においては、コンテンツとしての価値を高める生成された動きの多様性が確保できない。
【００１４】
すなわち、特許文献1や非特許文献1の従来技術において、音楽など一定の長さの間継続する、当該音楽の流れに即した動きを生成する場合に、動きの滑らかさを確保しようとすると生成される動きが単調となり多様性が失われ、多様性を確保しようとすると滑らかさが失われてしまい、コンテンツ価値を高めるための動きの多様性と滑らかさとが同時に確保できないという課題があった。
【００１５】
本発明の目的は上記の従来技術の課題を解決し、動きの滑らかさを維持しつつ多様な動きを生成することのできる動き生成装置及び方法を提供することにある。
【課題を解決するための手段】
【００１６】
上記目的を達成するため、本発明は、予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成装置であって、複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成部と、前記第一のモーショングラフの各ノードをグループに分類し、互いに異なるグループに属し且つ類似するノード間にエッジを設けて第二のモーショングラフを生成するモーショングラフ修正部と、前記第二のモーショングラフに基づいて、前記所定の時系列データに即した動きデータを生成する動き生成部とを備えることを第一の特徴とする。
【００１７】
また本発明は、前記モーショングラフ生成部は、複数の動きデータの各々より各動きデータの時間変化に基づいて複数のキーフレームを抽出してノードとなすキーフレーム抽出部と、同一の動きデータに属して隣接するノード間に時間方向の単方向エッジを設けると共に、当該ノード間の動きの活発さに基づく重みを付与する単方向エッジ設定部と、互いに異なる動きデータに属して第一の所定基準で類似するノード間と、同一の動きデータに属しており且つ隣接しておらず前記第一の所定基準で類似するノード間と、に双方向エッジを設けると共に、当該類似する度合いに基づく重みを付与する双方向エッジ設定部とを含み、前記ノードと、単方向及び双方向エッジ並びにその重みとによって前記第一のモーショングラフを生成し、前記モーショングラフ修正部は、前記第一のモーショングラフを複数の部分グラフへと分割するグラフ分割部と、前記複数の部分グラフのうちの異なるものに属し且つ第二の所定基準で類似するノード間に前記第二のモーショングラフを生成するための双方向エッジを設けると共に、当該類似する度合いに基づく重みを付与するノード再接続部とを含み、前記グラフ分割部が強連結成分分解によって前記第一のモーショングラフを複数の部分グラフへと分割することを第二の特徴とする。
【００１８】
また上記目的を達成するため、本発明は、予め区間分けされ各区間における特徴量が定義された所定の時系列データに即した動きデータを生成する動き生成方法であって、複数の動きデータの各々より複数のキーフレームを抽出してノードとなし、類似するノード間にエッジを設けることで第一のモーショングラフを生成するモーショングラフ生成ステップと、前記第一のモーショングラフにおける所定基準を満たすの各ノードをグループに分類し、互いに異なるグループに属し且つ類似するノード間にエッジを設けて第二のモーショングラフを生成するモーショングラフ修正ステップと、前記前記第二のモーショングラフに基づいて、前記所定の時系列データに即した動きデータを生成する動き生成ステップとを備えることを第三の特徴とする。
【発明の効果】
【００１９】
前記第一又は第三の特徴によれば、第一のモーショングラフを動きの滑らかさが確保できるように構築しておいて、所属ノードをグループ分けし、異なるグループに属して且つ類似するノード間にエッジを追加した第二のモーショングラフに修正して当該第二のモーショングラフから動きを生成することで、動きの滑らかさに加えて多様性も確保した動きを生成することができる。
【００２０】
前記第二の特徴によれば、第一のモーショングラフを強連結成分分解により部分グラフへと分割し、当該部分グラフ同士の間で第二のモーショングラフにおいて追加するエッジを設けるようにすることで、簡素な基準判断処理に基づいて動きの滑らかさ及び多様性を確保した動きを生成することができる。
【図面の簡単な説明】
【００２１】
【図１】一実施形態に係る動き生成装置の機能ブロック図である。
【図２】一実施形態に係る動き生成装置の機能概要を説明する図である。
【図３】モーショングラフの概要を説明する図である。
【図４】グラフの強連結成分分解を説明する図である。
【図５】ノード再接続部における最小距離法の処理のフローチャートを示す図である。
【図６】ノード再接続部における閾値制御法の処理のフローチャートを示す図である。
【図７】図5のフローによるグラフの更新の例を示す図である。
【図８】図6のフローによるグラフの更新の例を示す図である。
【図９】一実施形態に係る動き生成装置の機能ブロック図である。
【図１０】従来技術の説明図である。
【発明を実施するための形態】
【００２２】
図1は本発明の一実施形態に係る動き生成装置の機能ブロック図である。動き生成装置1は、音楽解析部2、動きデータベース3、モーショングラフ生成部4、モーショングラフ修正部5、動き生成部6及び動き再生部7を備える。なお後述するように、動き生成装置1はこれらの機能ブロックのうちの一部のみを備えて構成されていてもよい。
【００２３】
モーショングラフ生成部4は、キーフレーム抽出部41、単方向エッジ設定部42及び双方向エッジ設定部43を含む。モーショングラフ修正部5は、グラフ分割部51及びノード再接続部52を含む。動き生成部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データにおける当該ビートの抽出に関しては、以下の非特許文献2に開示された次のような技術を利用することができる。MoCapデータには基準となるポーズのフレームには、ルート（腰）や各関節の3次元座標が、その後のフレームにおいては、基準ポーズからの相対的な位置などが含まれる。このMoCapデータから各時刻における各関節の3次元座標を求めて、関節数×3次元のベクトルの時系列として動きを表すことができる。この動きを一定の分析幅で分割して、分析幅の対象となる区間のデータに対して主成分分析を適用することで、動きのグローバルな成分（最も大きな変化の方向）が第1主成分の主成分得点に抽出される。この主成分得点が極大及び極小となる時刻のフレームを動きのビートフレーム（ノード）とする。
【００３０】
[非特許文献2] 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]に該当する全ノード間のうち対応するポーズ同士が所定基準で類似するものにつき、実際に双方向エッジが設定され、重みが付与される。なおまた、ノード間に単方向エッジと双方向エッジとが同時に設定されることはない。
【００４０】
当該モーショングラフに基づいて新たな動きデータを生成することができる。この際、モーショングラフにおいて隣接するノード間を、単方向又は双方向エッジの定める方向に移動して得られるノードの遷移系列に対応する新たな動きデータが生成される。単方向エッジの定める方向の逆方向へは遷移することができない。双方向エッジにおいては両方向へ遷移可能である。
【００４１】
本発明の特徴的構成であるモーショングラフ修正部5は、モーショングラフ生成部4の生成したモーショングラフを、そのグラフ構造に基づいて修正する。なお以下適宜、モーショングラフをグラフと略称する。
【００４２】
グラフ分割部51は、グラフを部分グラフへと分割する。その意義は次の通りである。上述のとおり従来技術において、固定の閾値のみに基づいて双方向エッジを接続したグラフの場合に動きの滑らかさを担保しようとすると、ループのサイズが小さくなる場合がある。そのグラフを利用して生成された動きは多様性が低い可能性がある。従って、適応的な基準（例えば，当該ノード間の属性によって閾値を変えるなど）によって、双方向エッジを接続判定が行えることが望ましい。その際に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に「最小距離法」に、図6に「閾値制御法」に係るフローチャートを示す。
【００４８】
図5の最小距離法では、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に属するノードとの全ての組合せについてノード間距離を求め、距離が最小となるノードの間に双方向エッジを設定する。当該距離は双方向エッジ設定部43で説明したのと同様のポーズ間距離を用いる。さらにステップS8では当該設定した双方向エッジに、双方向エッジ設定部43で説明したのと同様の重みを付与し、当該追加設定した双方向エッジ及び重みをグラフGpに追加することで、次の処理対象としてのグラフGp+1となす。
【００５７】
(ステップS9)結合回数カウンタpを１だけ増分する。(ステップS10)結合回数カウンタpが所定の上限回数P未満であるか判断し、未満であればステップS3に戻ってフローを継続する。未満でなければステップS10に進んでフローを終了する。
【００５８】
上述の例では、距離が最小となるノード間を接続する場合について述べたが、最小値に限らず最大値、中央値又は平均値をとったノード間を接続してもよい。なお、距離の最小値はノード間類似度の最大値に、距離の最大値はノード間類似度の最小値に対応する。
【００５９】
一方、図6の閾値制御法を以上の図5の最小距離法との差異点を抽出して説明すると次の通りである。
【００６０】
[図5のステップS8に対して図6のステップS80]
1番大きい強連結成分D_1stに属する各ノードと、2番目に大きい強連結成分D_2ndに属する各ノード間の組み合わせの距離が、双方向エッジの接続判定閾値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に対して図6のステップS30等、類似の番号を付してあるステップについては共通である。なお、図5のステップS8及び図6のステップS80における別実施例として、D_1stのノードとD_2ndのノードとの間で距離を求めて所定のノード間に双方向エッジ及び重みを付与する代わりに、D_1stのノードとD_2nd以下すなわちノード数の多さが2番目以降の全ての強連結成分のノードとの間で距離を求めて同様に双方向エッジ及び重みを付与するようにしてもよい。また、2番目以降の全てではなく2番目以降所定のn番目までとしてもよい。
【００６４】
以上のように、図5または図6のフローによって本発明では次のような効果が得られる。すなわち、ループ内の遷移による動きの滑らかさは保持した上で、ループのサイズを拡大することができるため、その修正されたモーショングラフを利用して動きを生成した場合に一定の滑らかさを維持した上で多様性が向上する。
【００６５】
図5の場合と図6の場合の違いは、その効果に関して次の通りである。図5の場合、ループ間で最小距離をとるノード間を接続するため、ループ間を遷移する場合は滑らかさが損なわれる可能性もあるが、そのような遷移の発生を最小限に抑えることができる。また新たに閾値設定する必要がないため、パラメータ設定が容易となる。
【００６６】
図6の場合、ループ間で所定の接続判定閾値を満たすノード全ての組みが接続されるため、動きの多様性が向上しやすい。動きの滑らかさに関しては接続判定閾値をどう設定するかによるが、適切な接続判定閾値が設定することでループ間で多くの双方向エッジが接続される。よって、動きの滑らかさを一定に保ったまま図5の場合よりも多様性の向上に重点を置くことができる。
【００６７】
図7及び図8はそれぞれ、図5及び図6のフローを適用する例を示す図であり、両図において各フローを適用する前の、モーショングラフ生成部4の出力したグラフG0が(1)に示されており、当該グラフの例は図3の(3)で示したのと同様(ただし、逆グラフから元の向きに戻してある)である。
【００６８】
図7の(2)は一回目の接続により、D_1stであるD1に属するノードgと、D_2ndであるD2に属するノードjとの間に新たに双方向エッジが設けられ、グラフG0がG1へ更新されている。さらに２回目の接続により、D_1stであるD1∪D2に属するノードhと、D_2ndであるD3に属するノードdとの間に新たに双方向エッジが設けられ、(3)に示すようにグラフG1がG2へ更新されている。
【００６９】
図8の(2)は一回目の接続により、D_1stであるD1に属するノードg及びhと、D_2nd以降の1つの強連結成分であるD2に属するノードjとの間で合計2本の新たな双方向エッジが設けられ、グラフG0がG1へ更新されている。さらに２回目の接続により、D_1stであるD1∪D2に属するノードg及びhと、それぞれD_2nd以降の1つの強連結成分であるD5に属するノードc及びD3に属するノードdとの間で合計2本の新たに双方向エッジが設けられ、(3)に示すようにグラフG1がG2へ更新されている。
【００７０】
音楽解析部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に示されているように、音楽と動きの盛り上がりに関するコスト関数を定義し、始点から遷移候補ノードに遷移するまでに累積するコストが最小となるパスを動的計画法によって求め、最適パスとして選択する。その際に、双方向エッジで遷移する際には、上述の双方向エッジにおいて重み（閾値で上限設定）がペナルティとして作用する。さらにコスト関数を、２回以上経過するエッジのコストが高くなるよう、例えば既に通過した回数の多さや、直前に通過した時点からの遷移数の少なさに応じて高コストとなるよう設計してもよい。
【００７５】
合成部62は、この最適パスでモーショングラフ上のノード間を遷移しながら、各ノードに対応する動きデータの断片を連結することによって新たな動きデータを生成する。実際には、ノード自体はビートフレームのポーズを表しているため、遷移に伴う動きデータ断片の連結によって動きが生成されることになる。
【００７６】
当該連結に際して、単方向エッジによる遷移であれば、ビートフレーム間のフレームが実際に存在するため、それをそのまま生成すべき動きデータの各断片として利用して連結すればよい。こうして、ある１つの動きデータから抽出されたノードを単方向エッジによって順次遷移するパスに対しては、合成部62は当該元の動きデータと一致する動きデータを生成する。
【００７７】
しかしながら遷移パスが双方向エッジの場合は、ビートフレーム同士は異なる動きデータに属するものであるか、同一の動きデータに属しても隣接していないものである。すなわち、当該ビートフレーム間のフレームは実際には存在しない。そこで、合成部62は当該フレームを合成する。その際に、ブレンディングという技術を用いる。ビートフレーム及びその前後のフレームを考慮して、両者の間で平均化を施すことによって、ある動きから別の動きに遷移する際の動きを滑らかに生成することができる。これには、特許文献1と同様の手法を用いればよい。
【００７８】
動き再生部7は、動き生成部6で生成された新たな動きデータを、ＰＣのディスプレイや携帯端末などで音楽と共に提示する。ユーザによって選択された音楽を再生しつつ、動き生成部で生成された音楽と同期し、かつ音楽の盛り上がりと動きの盛り上がりも相関のある動きを、適当に選択された3Dキャラクタ（CGモデル）が行っている映像を再生する。音楽のビートと動きデータのビート(ノード)との同期に際して、動きデータの時間軸を適宜伸縮してよい。
【００７９】
以上のように、本発明によれば、音楽と同時にキャラクタの動きを再生可能なコンテンツを楽しむユーザにとっては、従来の動きの滑らかさを維持した上で、その多様性が向上するため、飽きずにコンテンツを見ることができる。技術的には、元のモーショングラフの構造をある程度保ちつつモーショングラフのループサイズを制御することができるようになる。
【００８０】
図9は、本発明の一実施形態に係る動き生成装置1の機能ブロック図である。当該実施形態では、動き生成装置1は、モーショングラフ生成部4、モーショングラフ修正部5及び動き生成部6を備える。当該各部の機能は以上説明してきたものと同様である。図1の構成との差異が次の[A]〜[C]の通りである。
【００８１】
[A]動きデータベース3を備える代わりに(1)に示すように、動きデータベース3に保存されているのと同様な複数の動きデータをモーショングラフ生成部4で読み込むようにする。
【００８２】
[B]音楽解析部2を備えて入力音楽を解析する代わりに(2)に示すように、予め区間分けされ特徴量が各区間に定義された所定の時系列データ(有限長)を、動き生成部6で読み込むようにする。当該時系列データは音楽に限らず、任意の種類のデータが利用できる。当該各区間で定義された特徴量を前述の音楽の場合における各ビート区間の盛り上がりに相当するものとして扱うことで、動き生成部6は前述の場合と同様に動きを生成することができる。
【００８３】
[C]動き再生部7を省略して(3)に示すように、動きデータを出力させるようにする。
【００８４】
すなわち、本発明は音楽に限定されず、上記のような形式を有する所定の時系列データであれば、データの種類を問わず適用可能であって、当該任意の種類の時系列データに基づいて当該時系列データにおける特徴量の変化系列に即した動きデータを生成することができる。特徴量には、当該時系列データの種類に応じた所望のものを採用することができ、予めそのような特徴量を求めて時系列データに対応づけておけばよい。
【符号の説明】
【００８５】
1…動き生成装置、4…モーショングラフ生成部、5…モーショングラフ修正部、6…動き生成部、41…キーフレーム抽出部、42…単方向エッジ設定部、43…双方向エッジ設定部、51…グラフ分割部、52…ノード再接続部、61…同期部、62…合成部
【図１】
2013120479.tif 000003
【図２】
2013120479.tif 000004
【図３】
2013120479.tif 000005
【図４】
2013120479.tif 000006
【図５】
2013120479.tif 000007
【図６】
2013120479.tif 000008
【図７】
2013120479.tif 000009
【図８】
2013120479.tif 000010
【図９】
2013120479.tif 000011
【図１０】
2013120479.tif 000012