(57)【要約】【課題】動画像の被写体の輪郭線について輪郭線の対応点を精度高く、少ないズレで決定する対応点決定装置を提供する。【解決手段】輪郭線の抽出処理Ｓ１０１により、複数のフレームからなる動画像に含まれる被写体のマスク画像から輪郭線を多角形近似して得られる代表点を得る。次に、連結リスト作成処理Ｓ１０２により、ＤＰマッチング処理により、各フレームの代表点の対応関係を連結リストとして得る。次に、アンカーポイントのユーザ設定Ｓ１０３により、少なくとも２つのキーフレームを選択させ、対応するアンカーポイントを設定させる。対応点決定処理Ｓ１０４により、連結リストを探索してキーフレーム間のフレームｆにおける両アンカーポイントに対応する点ａｐ１６８、ａｐ２６９を求め、両キーフレームからフレームｆまでのフレーム数に応じてａｐ１６８−ａｐ２６９間の代表点を対応点Ｑ６０と決定する。【選択図】図２
2014191695.tif 000002
【特許請求の範囲】
【請求項１】
複数のフレームの２次元画像から成る動画像の被写体について、前記被写体の輪郭線上の対応点を決定する対応点決定装置であって、
各フレームの前記被写体の輪郭線を多角形近似した複数の頂点を前記各フレームの前記被写体の代表点として抽出する代表点抽出手段と、
前記各フレームについて、前記各フレームの各代表点と、隣接するフレームの代表点との対応関係を記述した連結リストを作成する連結リスト作成手段と、
少なくとも２つのキーフレームを選択させ、各キーフレームの対応する代表点をアンカーポイントとして指定させるアンカーポイント設定手段と、
前記キーフレーム間の各フレームについて、前記キーフレームのアンカーポイントと、前記キーフレームと前記キーフレーム間の各フレームの連結リストから、前記キーフレーム間の各フレームのアンカーポイントを決定する対応点決定手段と、
を具備することを特徴とする対応点決定装置。
【請求項２】
前記連結リスト作成手段は、当該フレームについて、前後の各フレームとの間で、代表点間の距離の総和をコストとするダイナミックプログラミングマッチング処理により、前記コストを最小とする当該フレームの代表点と前後の各フレームの代表点の対応関係を求めて、連結リストとする
ことを特徴とする請求項１に記載の対応点決定装置。
【請求項３】
前記対応点決定手段は、当該フレームの前の前記キーフレームから当該フレームの１つ前のフレームまでの各フレームの前記連結リストを順に参照して、当該フレームの前の前記キーフレームの前記アンカーポイントに対応する当該フレームの代表点を求め第１のアンカーポイント対応点とし、当該フレームの後の前記キーフレームから当該フレームの１つ後のフレームまでの各フレームの前記連結リストを順に参照して、当該フレームの後の前記キーフレームの前記アンカーポイントに対応する当該フレームの代表点を求め第２のアンカーポイント対応点とし、当該フレームから当該フレームの前のキーフレームまでのフレーム数を第１のフレーム数、当該フレームから当該フレームの後のキーフレームまでのフレーム数を第２のフレーム数としたとき、前記第１及び第２のアンカーポイント対応点間を第１のフレーム数対第２のフレーム数に分割する点に最も近い代表点を、当該フレームのアンカーポイントとする
ことを特徴とする請求項１または請求項２に記載の対応点決定装置。
【請求項４】
前記アンカーポイント設定手段は、前記キーフレーム、及び、前記アンカーポイントを指定可能なグラフィック・ユーザ・インタフェースを表示させる
ことを特徴とする請求項１乃至請求項３のいずれかに記載の対応点決定装置。
【請求項５】
複数のフレームの２次元画像から成る動画像の被写体について、前記被写体の輪郭線上の対応点を決定する対応点決定方法であって、
コンピュータが、
各フレームの前記被写体の輪郭線を多角形近似した複数の頂点を前記各フレームの前記被写体の代表点として抽出する代表点抽出ステップと、
前記各フレームについて、前記各フレームの各代表点と、隣接するフレームの代表点との対応関係を記述した連結リストを作成する連結リスト作成ステップと、
少なくとも２つのキーフレームを選択させ、各キーフレームの対応する代表点をアンカーポイントとして指定させるアンカーポイント設定ステップと、
前記キーフレーム間の各フレームについて、前記キーフレームのアンカーポイントと、前記キーフレームと前記キーフレーム間の各フレームの連結リストから、前記キーフレーム間の各フレームのアンカーポイントを決定する対応点決定ステップと、
を実行することを特徴とする対応点決定方法。
【請求項６】
コンピュータを、複数のフレームの２次元画像から成る動画像の被写体について、前記被写体の輪郭線上の対応点を決定する対応点決定装置として機能させるためのプログラムであって、
コンピュータを、
各フレームの前記被写体の輪郭線を多角形近似した複数の頂点を前記各フレームの前記被写体の代表点として抽出する代表点抽出手段、
前記各フレームについて、前記各フレームの各代表点と、隣接するフレームの代表点との対応関係を記述した連結リストを作成する連結リスト作成手段、
少なくとも２つのキーフレームを選択させ、各キーフレームの対応する代表点をアンカーポイントとして指定させるアンカーポイント設定手段、
前記キーフレーム間の各フレームについて、前記キーフレームのアンカーポイントと、前記キーフレームと前記キーフレーム間の各フレームの連結リストから、前記キーフレーム間の各フレームのアンカーポイントを決定する対応点決定手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像処理における輪郭線の対応点を決定する技術に関し、更に詳しくは、動画像処理における被写体輪郭線の各フレームにおける対応点を決定する技術に関する。
【背景技術】
【０００２】
動画像処理においては、データ量の圧縮や、立体視を実現する処理において、被写体の輪郭線をフレーム間で対応付ける必要があり、対応点決定方法が提案されている（例えば、特許文献１、特許文献２）。
【０００３】
特許文献１には、ＤＰ（Ｄｙｎａｍｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ）マッチングを用いて、動画の隣接するフレーム間で対応点を求める発明が開示されている。これは、それぞれのフレームにおいて、オブジェクト（被写体）の輪郭線上に代表点を取り、その代表点ごとに、曲率に基づく特徴量を求め、この特徴量をコストとして、ＤＰマッチングによりコストが最小となる代表点の対応付けを決定するものである。
【０００４】
一方、特許文献２には、動画のフレームにキーとなるキーフレームを複数設け、複数のキーフレームの画像の被写体の輪郭線上に対応するアンカーポイントを設け、アンカーポイントが輪郭線全体の何％の位置にあるかを各アンカーポイントの位置情報として記憶しておき、２つのキーフレーム間のフレームの当該被写体の輪郭線上の対応点を、当該フレームから両キーフレームまでのフレーム数に応じて両キーフレームのアンカーポイントの位置情報を元に内挿することにより決定する発明が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１０−２４８０５２号公報
【特許文献２】特願２０１２−２２２８４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１の方法は、隣り合うフレームに対して代表点の対応付け処理を行うため、フレームが進むに従って対応点にズレが生じる可能性があるという問題がある。
【０００７】
また、特許文献２の方法は、アンカーポイントの位置情報として輪郭線全体の何％の位置にあるかを用いて、キーフレーム間のフレームの対応点を内挿入しているが、輪郭線の長さは、フレーム毎に異なるため、対応点にズレが生じるという問題がある。
【０００８】
本発明は、前述した問題点に鑑みてなされたものであり、その目的とするところは、ズレのない対応点を決定可能な動画像の輪郭線における対応点決定装置等を提供することである。
【課題を解決するための手段】
【０００９】
前述した目的を達成するために、第１の発明は、複数のフレームの２次元画像から成る動画像の被写体について、前記被写体の輪郭線上の対応点を決定する対応点決定装置であって、各フレームの前記被写体の輪郭線を多角形近似した複数の頂点を前記各フレームの前記被写体の代表点として抽出する代表点抽出手段と、前記各フレームについて、前記各フレームの各代表点と、隣接するフレームの代表点との対応関係を記述した連結リストを作成する連結リスト作成手段と、少なくとも２つのキーフレームを選択させ、各キーフレームの対応する代表点をアンカーポイントとして指定させるアンカーポイント設定手段と、前記キーフレーム間の各フレームについて、前記キーフレームのアンカーポイントと、前記キーフレームと前記キーフレーム間の各フレームの連結リストから、前記キーフレーム間の各フレームのアンカーポイントを決定する対応点決定手段と、を具備することを特徴とする対応点決定装置である。
【００１０】
第１の発明によって、連結リスト作成手段により、各フレーム間の代表点の対応点を記述した連結リストを求めるとともに、アンカーポイント設定手段により、動画中に最低２つ選択されたキーフレームについて、対応するアンカーポイントを設定させ、対応点決定手段により、連結リストと、キーフレームのアンカーポイントを用いて全フレームについて、アンカーポイントの対応点を決定することが可能であり、ズレの少ない輪郭線の対応付けが可能となる。
【００１１】
第１の発明において、前記連結リスト作成手段は、当該フレームについて、前後の各フレームとの間で、代表点間の距離の総和をコストとするダイナミックプログラミングマッチング処理により、前記コストを最小とする当該フレームの代表点と前後の各フレームの代表点の対応関係を求めて、連結リストとする。
あるフレームの連結リストは、当該フレームの代表点と対応する前の隣接フレーム及び後の隣接フレームの代表点を記述する。
【００１２】
第１の発明において、前記対応点決定手段は、当該フレームの前の前記キーフレームから当該フレームの１つ前のフレームまでの各フレームの前記連結リストを順に参照して、当該フレームの前の前記キーフレームの前記アンカーポイントに対応する当該フレームの代表点を求め第１のアンカーポイント対応点とし、当該フレームの後の前記キーフレームから当該フレームの１つ後のフレームまでの各フレームの前記連結リストを順に参照して、当該フレームの後の前記キーフレームの前記アンカーポイントに対応する当該フレームの代表点を求め第２のアンカーポイント対応点とし、当該フレームから当該フレームの前のキーフレームまでのフレーム数を第１のフレーム数、当該フレームから当該フレームの後のキーフレームまでのフレーム数を第２のフレーム数としたとき、前記第１及び第２のアンカーポイント対応点間を第１のフレーム数対第２のフレーム数に分割する点に最も近い代表点を、当該フレームのアンカーポイントとする。
【００１３】
第１の発明において、前記アンカーポイント設定手段は、前記キーフレーム、及び、前記アンカーポイントを指定可能なグラフィック・ユーザ・インタフェースを表示させることが望ましい。
【００１４】
第２の発明は、複数のフレームの２次元画像から成る動画像の被写体について、前記被写体の輪郭線上の対応点を決定する対応点決定方法であって、コンピュータが、各フレームの前記被写体の輪郭線を多角形近似した複数の頂点を前記各フレームの前記被写体の代表点として抽出する代表点抽出ステップと、前記各フレームについて、前記各フレームの各代表点と、隣接するフレームの代表点との対応関係を記述した連結リストを作成する連結リスト作成ステップと、少なくとも２つのキーフレームを選択させ、各キーフレームの対応する代表点をアンカーポイントとして指定させるアンカーポイント設定ステップと、前記キーフレーム間の各フレームについて、前記キーフレームのアンカーポイントと、前記キーフレームと前記キーフレーム間の各フレームの連結リストから、前記キーフレーム間の各フレームのアンカーポイントを決定する対応点決定ステップと、を実行することを特徴とする対応点決定方法である。
【００１５】
第３の発明は、コンピュータを、複数のフレームの２次元画像から成る動画像の被写体について、前記被写体の輪郭線上の対応点を決定する対応点決定装置として機能させるためのプログラムであって、コンピュータを、各フレームの前記被写体の輪郭線を多角形近似した複数の頂点を前記各フレームの前記被写体の代表点として抽出する代表点抽出手段、前記各フレームについて、前記各フレームの各代表点と、隣接するフレームの代表点との対応関係を記述した連結リストを作成する連結リスト作成手段、少なくとも２つのキーフレームを選択させ、各キーフレームの対応する代表点をアンカーポイントとして指定させるアンカーポイント設定手段、前記キーフレーム間の各フレームについて、前記キーフレームのアンカーポイントと、前記キーフレームと前記キーフレーム間の各フレームの連結リストから、前記キーフレーム間の各フレームのアンカーポイントを決定する対応点決定手段、として機能させるためのプログラムである。
【発明の効果】
【００１６】
本発明により、ズレのない対応点を決定可能な動画像の輪郭線における対応点決定装置等を提供することが可能になる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施形態に係る対応点決定装置の構成を示すハードウエア構成図
【図２】本実施形態に係る対応点決定装置の処理の流れを示すフローチャート
【図３】図２のステップ１０１の輪郭線の抽出処理の詳細を示すフローチャート
【図４】入力画像群の一例を示す図
【図５】輪郭線の一例を示す図
【図６】輪郭線の代表点２７の一例を示す図
【図７】動画像における輪郭線の代表点の説明図
【図８】図２のステップ１０２の連結リスト作成処理の詳細を示すフローチャート
【図９】隣接するフレームの対応点を決定するＤＰマッチングの説明図
【図１０】連結リスト３０を説明する図
【図１１】図２のステップ１０２のアンカーポイントのユーザ設定処理の詳細を示すフローチャート
【図１２】アンカーポイント設定画面例（１）５０を示す図
【図１３】アンカーポイント設定画面例（２）５１を示す図
【図１４】図２のステップ１０４の対応点決定処理の詳細を示すフローチャート
【図１５】図２のステップ１０４の対応点決定処理の詳細を示すフローチャート（続き）
【図１６】対応点決定処理を説明する図
【発明を実施するための形態】
【００１８】
以下、添付図面に基づいて、本発明に係る動画像の対応点決定装置の好適な実施形態について詳細に説明する。
【００１９】
図１は、本発明の実施形態に係る対応点決定装置１のハードウエア構成図である。尚、図１のハードウエア構成は一例であり、用途、目的に応じて様々な構成を採ることが可能である。
【００２０】
対応点決定装置１は、制御部１１、記憶部１２、メディア入出力部１３、通信制御部１４、入力部１５、表示部１６、周辺機器Ｉ／Ｆ部１７等が、バス１８を介して接続される。
【００２１】
制御部１１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等で構成される。
【００２２】
ＣＰＵは、記憶部１２、ＲＯＭ、記録媒体等に格納されるプログラムをＲＡＭ上のワークメモリ領域に呼び出して実行し、バス１８を介して接続された各装置を駆動制御し、対応点決定装置１が行う後述する処理を実行する。ＲＯＭは、不揮発性メモリであり、対応点決定装置１のブートプログラムやＢＩＯＳ等のプログラム、データ等を恒久的に保持している。ＲＡＭは、揮発性メモリであり、記憶部１２、ＲＯＭ、記録媒体等からロードしたプログラム、データ等を一時的に保持するとともに、制御部１１が各種処理を行う為に使用するワークエリアを備える。
【００２３】
記憶部１２は、ＨＤＤ（ハードディスクドライブ）等であり、制御部１１が実行するプログラム、プログラム実行に必要なデータ、ＯＳ（オペレーティングシステム）等が格納される。プログラムに関しては、ＯＳ（オペレーティングシステム）に相当する制御プログラムや、後述する処理を対応点決定装置１に実行させるためのアプリケーションプログラムが格納されている。これらの各プログラムコードは、制御部１１により必要に応じて読み出されてＲＡＭに移され、ＣＰＵに読み出されて各種の手段として実行される。
【００２４】
メディア入出力部１３（ドライブ装置）は、データの入出力を行い、例えば、ＣＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＤＶＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）等のメディア入出力装置を有する。
【００２５】
通信制御部１４は、通信制御装置、通信ポート等を有し、対応点決定装置１とネットワーク間の通信を媒介する通信インタフェースであり、ネットワークを介して、他の装置間との通信制御を行う。ネットワークは、有線、無線を問わない。
【００２６】
入力部１５は、データの入力を行い、例えば、キーボード、マウス等のポインティングデバイス、テンキー等の入力装置を有する。入力部１５を介して、対応点決定装置１に対して、操作指示、動作指示、データ入力等を行うことができる。
【００２７】
表示部１６は、ＣＲＴモニタ、液晶パネル等のディスプレイ装置、ディスプレイ装置と連携して対応点決定装置１のビデオ機能を実現するための論理回路等（ビデオアダプタ等）を有する。
【００２８】
周辺機器Ｉ／Ｆ（インタフェース）部１７は、対応点決定装置１に周辺機器を接続させるためのポートであり、周辺機器Ｉ／Ｆ部１７を介して対応点決定装置１は周辺機器とのデータの送受信を行う。周辺機器Ｉ／Ｆ部１７は、ＵＳＢやＩＥＥＥ１３９４やＲＳ−２３２Ｃ等で構成されており、通常複数の周辺機器Ｉ／Ｆを有する。周辺機器との接続携帯は有線、無線を問わない。
【００２９】
バス１８は、各装置間の制御信号、データ信号等の授受を媒介する経路である。
【００３０】
図２は、対応点決定装置１が実行する輪郭線の対応点決定処理の流れを示すフローチャートである。
【００３１】
ステップ１０１において、対応点決定装置１の制御部１１（以下、制御部１１ともいう。）は、動画像の入力画像群を読み込み、動画像の被写体の輪郭線を抽出する処理を実行する。輪郭線の抽出処理（ステップ１０１）の詳細については後述する。
動画像は複数のフレームの２次元画像等からなる。
【００３２】
次に、ステップ１０２において、制御部１１は、ステップ１０１により抽出された輪郭線の情報を元に、隣接するフレームの輪郭線の対応点を示す連結リストを作成する連結リスト作成処理を実行する。
連結リスト作成処理（ステップ１０２）の詳細については後述する。
【００３３】
次に、ステップ１０３において、制御部１１は、動画像を構成する複数のフレームからキーフレームを少なくとも２つ選択し、キーフレームの被写体の輪郭線上で対応する点をアンカーポイントとして指定させるアンカーポイントのユーザ設定処理を実行する。
アンカーポイントのユーザ設定処理（ステップ１０３）の詳細については後述する。
【００３４】
次に、ステップ１０４において、制御部１１は、ステップ１０２において作成した連結リストと、ステップ１０３において設定されたアンカーポイントの情報を元に、キーフレーム間の各フレームの対応点を決定する処理を実行する。
対応点決定処理（ステップ１０４）の詳細については後述する。
【００３５】
図３は、図２のステップ１０１の輪郭線の抽出処理の詳細を説明するフローチャートである。また、図４〜図７は、輪郭線の抽出処理を説明する図であり、図４〜図７を参照して輪郭線の抽出処理について説明する。
【００３６】
まず、ステップ１１１において、制御部１１は、対応点決定装置１に２次元画像Ｐの被写体のマスク画像Ｍを得る。
【００３７】
図４は、入力画像群を説明する図であり、図４（ａ）は、複数のフレームからなる動画像の２次元画像Ｐのうちの５フレーム分の２次元画像Ｐ１〜Ｐ５（（Ａ）〜（Ｅ））を示している。例えば、単位時間当たり所定のフレーム数（通常、１秒間に３０フレーム）のカラー静止画像が含まれており、各画素がＲＧＢ各２５６段階の階調を持つ。
【００３８】
例えば、図４（Ａ）の２次元画像Ｐ１は、サッカーをしている１人の人を被写体としており、図４（Ｂ）の２次元画像Ｐ２は、図４（Ａ）の２次元画像Ｐ１と同様の被写体の他にもう一人の人からなる２つの被写体で構成されている。図４（Ｃ）〜（Ｅ）の２次元画像Ｐ３〜Ｐ５は、図４（Ａ）の２次元画像Ｐ１と同様の１つの被写体で構成されている。
【００３９】
マスク画像Ｍは、動画像の各フレームの２次元画像Ｐを構成する特定の被写体を識別するための２値化画像である。マスク画像Ｍは、２次元画像Ｐに基づいてフォトレタッチソフトなどを用いて手作業で生成してもよいし、別途ソフトウエアを用いて自動的に生成してもよい。
【００４０】
図４（ｂ）は、図４（ａ）に示した２次元画像Ｐ１〜Ｐ５（（Ａ）〜（Ｅ））におけるサッカーをしている１人の被写体に関するマスク画像Ｍ１〜Ｍ５（（Ａ）〜（Ｅ））を示す図である。
【００４１】
次に、制御部１１は、ステップ１１１で得たマスク画像Ｍの輪郭線を求める（ステップ１１２）。
輪郭線は、マスク画像Ｍの２値の境界を示す線である。輪郭線は、制御部１１が輪郭線検出処理を行って生成するようにしてもよいし、ユーザがマウス等を使用して入力してもよい。
【００４２】
図５は、図４（ｂ）（（Ａ）〜（Ｅ））のマスク画像Ｍ１〜Ｍ５についての輪郭線２１〜２５を示す図である。輪郭線２１〜２５は、いずれも１ストロークで描画されている。
【００４３】
次に、制御部１１は、ステップ１１２で得た輪郭線２１〜２５の代表点２７を求める（ステップ１１３）。代表点２７は、１ストロークからなる輪郭線２１〜２５に多角形近似処理を施すことにより、多角形の頂点として得ることができる。
【００４４】
図６は、図５（Ａ）に示したマスク画像Ｍ１の輪郭線２１の代表点ａｉ（ｉ＝１〜ｍ）２７を示す図である。図５（Ａ）に示したマスク画像Ｍ１の輪郭線２１に多角形近似処理を施し、頂点として得られた点が代表点ａｉ（ｉ＝１〜ｍ）２７である。
代表点ａｉ（ｉ＝１〜ｍ）２７は、例えば、同図に示すように、輪郭線２１のマスク画像上での最上部、かつ、最も左に位置する代表点を代表点ａ１とし、矢印Ａ方向に左回りに順に代表点ａ２、ａ３、・・・とし、輪郭線２１を一周して、代表点ａ１の右側の代表点ａｍをとする。
【００４５】
ステップ１１３では、制御部１１は、動画像に含まれる全ての被写体について、当該被写体が含まれる全フレームの当該被写体の輪郭線の代表点２７を求める。
図７は、複数のフレームからなる動画像における１つの被写体の輪郭線の代表点を説明する図である。
【００４６】
１つの被写体が、動画像における当該被写体の開始フレーム２８から終了フレーム２９までに連続して含まれているとする。
その場合、開始フレーム２８から終了フレーム２９までの各フレームについて、当該被写体の輪郭線の代表点２７が求められる。
【００４７】
例えば、開始フレーム２８のマスク画像Ｍ１の輪郭線２１の代表点は代表点ａ１〜ａｍであり、終了フレーム２９のマスク画像Ｍ５の輪郭線２５の代表点は代表点ｄ１〜ｄｎであり、代表点の数は、各フレームによって異なる。
これは、各フレームの輪郭線の多角形近似処理による頂点の数が異なるからである。
【００４８】
以上の輪郭線の抽出処理（図２のステップ１０１：図３のステップ１１１〜ステップ１１３）により、動画像の被写体について、各フレームの輪郭線の代表点２７が抽出され、制御部１１は、抽出された各代表点の位置座標が記憶部１２に格納する。
【００４９】
次に、制御部１１は、図２のステップ１０２において、図２のステップ１０１により抽出された輪郭線の代表点の位置座標を元に、隣接するフレームの輪郭線の対応点を示す連結リストを作成する連結リスト作成処理を実行する。
図８は、図２のステップ１０２の連結リスト作成処理の詳細を説明するフローチャートである。
【００５０】
まず、制御部１１は、フレーム番号を示す変数ｆに開始フレーム２８のフレーム番号を代入する（ステップ１２１）。変数ｆは、連結リストを作成するフレームの番号を示す。連結リストは、被写体の輪郭線の代表点２７が存在する開始フレーム２８から終了フレーム２９間の各フレームについて作成される。
【００５１】
次に、制御部１１は、記憶部１２に格納されているフレームｆの代表点ａi (ｉ＝１、２、・・・、Ｉ)の座標を読み込む（ステップ１２２）。代表点ａiの個数はＩ個であるとする。
【００５２】
次に、制御部１１は、フレームｆが開始フレーム２８であるか否かを判定する（ステップ１２３）。
フレームｆが開始フレーム２８でない場合には（ステップ１２３のＮｏ）、ステップ１２４、ステップ１２５の処理を実行し、フレームｆと隣接する前のフレームｆ−１の代表点の対応関係を示す連結リストを作成する。一方、フレームｆが開始フレーム２８の場合には（ステップ１２３のＹｅｓ）、前のフレームは存在しないので、ステップ１２４、１２５をスキップしてステップ１２６に進む。
【００５３】
ステップ１２４において、制御部１１は、隣接する前のフレームｆ−１の代表点ｂｊ (ｊ＝１、２、・・・、Ｊ)の座標を読み込む。代表点ｂｊの個数はＪ個であるとする。
【００５４】
ステップ１２５において、制御部１１は、フレームｆの代表点ａiと隣接する前のフレームの代表点ｂｊについてＤＰマッチング処理を行い、フレームｆの各代表点ａiについてのフレームｆ−１の対応点候補ｂｊを求め、連結リストとして記憶部１２に格納する。
【００５５】
図９は、ＤＰマッチングを説明する図、図１０は、連結リストを説明する図である。
図９（ａ）に示すように、フレームｆの輪郭線の各代表点ａi (ｉ＝１、２、・・・、Ｉ)
について、隣接する前のフレームｆ−１の代表点ｂｊ (ｊ＝１、２、・・・、Ｊ)から対応点を求めるＤＰマッチング処理について説明する。
【００５６】
フレームｆの代表点ａiとフレームｆ−１の代表点ｂｊとの対応付けを次式で表す。
【００５７】
【数１】
2014191695.tif 000003
ＤＰマッチングとは、式（１）を最適化する問題である。
フレームｆの代表点ａiとフレームｆ−１の代表点ｂｊとの対応付けのコストｄを次式で表す。
【００５８】
【数２】
2014191695.tif 000004
このとき、次式（３）を最小化するｕｉを求めればよい。
【００５９】
【数３】
2014191695.tif 000005
この最適化問題は、図９（ｂ）に示すように、横軸にフレームｆの代表点ａiの番号ｉ（ｉ＝１、２、・・・、Ｉ）、縦軸にフレームｆ−１の代表点ｂｊの番号ｊ（ｊ＝１、２、・・・、Ｊ）とするＤＰ平面３５における最適経路問題に置き換えることができる。
【００６０】
格子点（１、１）を始点として格子点（ｉ、ｊ）に至るまでの累積コストｇ（ｉ、ｊ）を次式（４）で表し、各格子点における累積コストｇ（ｉ、ｊ）を計算する。
【００６１】
【数４】
2014191695.tif 000006
【００６２】
このとき、次式（５）は、格子点（ｉ、ｊ）に至るパスの中で累積コストが最小となるパスを選択する式である。各格子点において、どのパスを選択したかをラベルとして記憶しておく。
【数５】
2014191695.tif 000007
【００６３】
各格子点の累積コストｇ（ｉ、ｊ）を求めた後、ｉ＝Ｉにおける格子点の累積コストｇ（Ｉ、ｊ）を最小にするｊ＝ｕＩを開始点として、ｉ＝Ｉ−１、Ｉ−２、・・・、１の順に格子点の累積コストｇ（ｉ、ｊ）を最小にするｊ＝ｕｉを探索することにより、ｕ１、ｕ２、・・・、ｕＩを決定する。
これにより、フレームｆの代表点ａ１、ａ２、・・・、ａＩについてのフレームｆ−１のＩ個の対応点候補ｂｊ（ｊ＝ｕ１、ｕ２、・・・、ｕＩ）が求まる。
【００６４】
図１０は、連結リストを説明する図である。
図１０（ａ）は、フレームｆの輪郭線の代表点と、隣接するフレームｆ−１、フレームｆ＋１の代表点の対応点候補例を説明する図である。
【００６５】
制御部１１が図８のステップ１２５を実行することにより、フレームｆの代表点ａ１、ａ２、ａ３、ａ４、ａ５、ａ６の各々に対応する、隣接する前のフレームｆ−１の対応点候補ｂ１、ｂ２、ｂ３、ｂ４、ｂ５、ｂ６が求まり、図１０（ｂ）に示すように、フレームｆの連結リスト３０として、フレームｆの代表点ａ１、ａ２、ａ３、ａ４、ａ５、ａ６３１に対する前フレームｆ−１の対応点候補ｂ１、ｂ２、ｂ３、ｂ４、ｂ５、ｂ６３２が記憶部１２に格納される。
【００６６】
図８に戻って、次に、制御部１１は、ステップ１２６において、フレームｆが終了フレーム２９か否かを判定する。
フレームｆが終了フレーム２９でない場合には（ステップ１２６のＮｏ）、ステップ１２７、ステップ１２８の処理を実行し、フレームｆと隣接する後のフレームｆ＋１の代表点の対応関係を示す連結リストを作成する。一方、フレームｆが終了フレーム２９の場合には（ステップ１２６のＹｅｓ）、後のフレームは存在しないので連結リスト作成処理を終了する。
【００６７】
ステップ１２７において、制御部１１は、隣接する後のフレームｆ＋１の代表点ｃｋ(ｋ＝１、２、・・・、Ｋ)の座標を読み込む。フレームｆ＋１の代表点ｃｋの個数はｋ個であるとする。
【００６８】
ステップ１２８において、制御部１１は、フレームｆの代表点ａiと隣接する後のフレームの代表点ｃｋについて前述の前のフレームｆ−１との場合と同様にＤＰマッチング処理を行い、フレームｆの各代表点ａiについてのフレームｆ＋１の対応点候補ｃｋを求め、連結リストとして記憶部１２に格納する。
【００６９】
図１０（ａ）に示すように、フレームｆの代表点ａ１、ａ２、ａ３、ａ４、ａ５、ａ６とフレームｆ＋１の代表点ｃ１、ｃ２、ｃ３、ｃ４、ｃ５、ｃ６、ｃ７、ｃ８、ｃ９、ｃ１０、ｃ１１との対応関係を、代表点間の距離をコストとした累積コストを最小にするようにＤＰマッチングを実行することにより、代表点間の対応関係が例えば、ａ１−ｃ１、ａ２−ｃ３、ａ３−ｃ４、ａ４−ｃ６、ａ５−ｃ９、ａ６−ｃ１１のように求まる。
【００７０】
これにより、図１０（ｂ）に示すように、フレームｆの連結リスト３０として、フレームｆの代表点ａ１、ａ２、ａ３、ａ４、ａ５、ａ６３１に対する後フレームｆ＋１の対応点候補ｃ１、ｃ３、ｃ４、ｃ６、ｃ９、ｃ１１３３が記憶部１２に格納される。
【００７１】
図８に戻って、次に、制御部１１は、ステップ１２９において、フレーム番号の変数ｆを１インクリメントし、ステップ１２２に戻り、ステップ１２２〜１２９の処理を繰り返す。
フレームｆが終了フレーム２９の場合には、ステップ１２４、ステップ１２５により前フレームｆ−１の対応点候補ｂｊを決定し、連結リスト３２を作成した後、ステップ１２６が「Ｙｅｓ」となり、全フレームについての連結リスト３０の作成を完了する。
【００７２】
図１０（ｃ）は、図１０（ａ）のフレームｆ＋１についての連結リスト３０’の例を示している。
フレームｆ＋１の代表点ｃｋの個数は１１個、前フレームｆの代表点ａｉの個数は６個のため、フレームｆ＋１の代表点ｃ１〜ｃ１１３１についての前フレームｆの対応点候補３２は重複するものが存在する。すなわち、代表点ｃ１およびｃ２の対応点候補３２がどちらもａ１ということが起こりうる。
【００７３】
全フレームの連結リスト３０の作成が完了すると、制御部１１は、図２のステップ１０３に進み、アンカーポイントのユーザ設定処理を実行する。
図１１は、アンカーポイントのユーザ設定処理（ステップ１０３）の詳細を示すフローチャートである。
アンカーポイントは、マスク画像の輪郭線に沿っていくつか設定される点であり、本実施形態の対応点決定装置１では、２つ以上のキーフレームで対応するアンカーポイントを設定することにより、キーフレーム間のフレームについてアンカーポイントに対応する対応点を決定する。
【００７４】
まず、制御部１１は、表示部１６に、アンカーポイント入設定画面５０を表示させる（ステップ１３１）。
図１２、図１３は、アンカーポイント設定画面例５０を示す図である。
図１２、図１３の例の場合、アンカーポイント設定画面５０、５０’には、画面表示領域５１、マスク切り替えプルダウン５２、フレーム選択スライダ５３、アンカーポイント設定用表示領域５４、アンカーポイント設定用ボタン５５、５６、キーフレーム設定用ボタン５８、５９、終了ボタン５７が表示されている。
【００７５】
画面表示領域５１には、マスク切り替えプルダウン５２で選択されたマスク画像について、フレーム選択スライダ５３で選択されたフレームのマスク画像が表示される。
アンカーポイント設定用表示領域５４には、設定するアンカーポイントの番号（例えば、「アンカーポイント１」）、及び、マウス切り替えプルダウン５２で選択されたマスク画像が存在するフレームの範囲が表示される。
【００７６】
次に、制御部１１は、新規のアンカーポイント番号を設定させる（ステップ１３２）。
アンカーポイント設定ボタン群の新規設定ボタン５５をユーザがクリックすることにより、新規に作成するアンカーポイント番号（例えば、「アンカーポイント１」が設定され、アンカーポイント設定用表示領域５４に表示される。
【００７７】
次に、制御部１１は、キーフレームＦを選択させる（ステップ１３３）。
フレーム選択スライダ５３をスライドさせることにより、選択されたフレームのマスク画像が画像表示領域５１に表示されるので、ユーザは、フレーム選択スライダ５３をスライドさせてアンカーポイントを設定したいフレームを探し、キーフレームとしてキーフレーム設定ボタン５８をクリックすることによりキーフレームを設定することが可能である。
図１２の例では、キーフレームＦ１４０が設定され、画像表示画面にはキーフレームＦ１４０のマスク画像の輪郭線２１が表示されている。
【００７８】
次に、制御部１１は、第１のアンカーポイントＡＰ１４８をキーフレームＦ１４０の輪郭線上に設定させる（ステップ１３４）。
画像表示エリア５１に表示されているマスク画像の輪郭線２１上を、例えばマウス等のポインティングデバイスによりカーソル（矢印）４５を合わせて移動させると、輪郭線２１上の代表点の位置にアンカーポイントを指定することが可能になり、所望の位置にカーソルを合わせて例えばマウスのボタンをクリックすることにより、アンカーポイントＡＰ１４８が設定できる。
【００７９】
１つのアンカーポイント番号について、対応するアンカーポイントＡＰは少なくとも２つのキーフレームで指定する必要がある。
次に、ステップ１３５において、制御部１１は、新たなキーフレームＦにアンカーポイントＡＰを設定するか否かを判定する。例えば、１つのアンカーポイント番号（例えば「アンカーポイント１」）に対して１つのキーフレームのアンカーポイントしか設定されていない場合には、ステップ１３５は「Ｙｅｓ」となり、ステップ１３３に戻って新たなキーフレームＦ（例えばキーフレームＦ２４１）を設定させ、ステップ１３４において、対応するアンカーポイントＡＰを設定させるようにすればよい。
【００８０】
図１３は、アンカーポイント番号１について第２のキーフレームＦ２４１を設定し、第１のキーフレームＦ１４０のアンカーポイントＡＰ１４８に対応するアンカーポイントＡＰ２４９を設定しているアンカーポイント設定画面例５０’を示している。
【００８１】
同じアンカーポイント番号（例えば「アンカーポイント１」）について３つ以上のキーフレームを設けて、対応するアンカーポイントを設定するようにしてもよい。
この場合、ステップ１３５が「Ｙｅｓ」となり、ステップ１３３〜１３５の処理を繰り返す。
【００８２】
同一のアンカーポイント番号に対して新たなキーフレームを設定しない場合（ステップ１３５の「Ｎｏ」）、制御部１１は、新たなアンカーポイント番号を設定するか否かを判定し（ステップ１３６）、新たにアンカーポイント番号を設定する場合には（ステップ１３６のＹｅｓ）、ステップ１３２に戻り、ステップ１３２〜１３６の処理を繰り返す。
新たなアンカーポイント番号を設定しない場合（ステップ１３６のＮｏ）は、アンカーポイントのユーザ設定処理（図２のステップ１０３）を終了する。
【００８３】
アンカーポイントのユーザ設定処理（図２のステップ１０３）が終了すると、制御部１１は、次に、対応点決定処理を実行する（図２のステップ１０４）。
図１４、図１５は、対応点決定処理（図２のステップ１０４）の詳細を説明するフローチャートである。また、図１６は、対応点Ｑの求め方を説明する図である。
対応点決定処理（図２のステップ１０４）では、連結リスト作成処理（図２のステップ１０２及び図８）で作成した連結リスト３０と、アンカーポイントのユーザ設定処理（図２のステップ１０３及び図１１）で設定された複数のキーフレームで対応するアンカーポイントＡＰを使用してキーフレーム間のアンカーポイント対応点を決定する。
【００８４】
今、２つのキーフレームＦ１４０とＦ２４１にそれぞれ設定したアンカーポイントＡＰ１４８、ＡＰ２４９に基づいて、２つのキーフレーム間のフレームについてのアンカーポイント対応点Ｑ６０を求めるものとする。
【００８５】
図１６（ａ）に示すように、キーフレームＦ１とキーフレームＦ２の間にある全てのフレームについて、アンカーポイントＡＰの対応点Ｑ６０を決定する。
まず、制御部１１は、対応点Ｑ６０を決定するフレームｆの初期値として「Ｆ１＋１」を設定する（ステップ１４１）。
【００８６】
次に、制御部１１は、キーフレームＦ１４０の連結リスト３０を読み込み、アンカーポイントＡＰ１４８を代表点３１として、１つ後のフレームＦ１＋１の対応点候補３３を読み出し、ａｐ１６８とする（ステップ１４２）。
【００８７】
制御部１１は、次に、処理で使用する数値Ｉとインデックスｉを設定する（ステップ１４３）。
数値Ｉは、対応点Ｑ６０を決定するフレームｆとキーフレームＦ１との間のフレーム数を示し、インデックスｉには初期値１を設定する。
【００８８】
次に、制御部１１は、インデックスｉが数値Ｉよりも小さいか否かを判定し（ステップ１４４）、小さい場合には（ステップ１４４のＹｅｓ）、フレームＦ１＋ｉのフレームの連結リスト３０を読み込み、先に求めたａｐ１６８を代表点３１として、後のフレームの対応点候補３３を読み出し、再度ａｐ１６８とする（ステップ１４５）。
【００８９】
次に、制御部１１は、インデックスｉを１インクリメントし、ステップ１４４に戻る。
ステップ１４４〜ステップ１４６により、図１６（ａ）に示すように、キーフレームＦ１から、対応点Ｑ６０を決定するフレームｆまでの各連結リスト３０を順次参照して、アンカーポイントＡＰ１４８に対応する対応点候補を順を追って探索し、ステップ１４４でｉ＝Ｉになった時点で（ステップ１４４のＮｏ）、対応点Ｑ６０を決定するフレームｆにおける対応点候補ａｐ１６８を得る。
【００９０】
次に、制御部１１は、キーフレームＦ２から対応点Ｑ６０を決定するフレームｆまで遡って、キーフレームＦ２のアンカーポイントＡＰ１４９に対応するフレームｆにおける対応点候補ａｐ２６９を得る処理を実行する（ステップ１４７〜ステップ１５１）。
【００９１】
すなわち、まず、キーフレームＦ２４１の連結リスト３０を読み込み、アンカーポイントＡＰ２４９を代表点３１として、１つ前のフレームＦ１−１の対応点候補３２を読み出し、ａｐ２６９とする（ステップ１４７）。
【００９２】
制御部１１は、次に、処理で使用する数値Ｊとインデックスｊを設定する（ステップ１４８）。
数値Ｊは、対応点Ｑ６０を決定するフレームｆとキーフレームＦ２との間のフレーム数を示し、インデックスｊには初期値１を設定する。
【００９３】
次に、制御部１１は、インデックスｊが数値Ｊよりも小さいか否かを判定し（ステップ１４９）、小さい場合には（ステップ１４９のＹｅｓ）、フレームＦ２−ｊのフレームの連結リスト３０を読み込み、先に求めたａｐ２６９を代表点３１として、前のフレームの対応点候補３２を読み出し、再度ａｐ２６９とする（ステップ１５０）。
【００９４】
次に、制御部１１は、インデックスｊを１インクリメントし、ステップ１４９に戻る。
ステップ１４９〜ステップ１５１により、図１６（ａ）に示すように、キーフレームＦ２から、対応点Ｑ６０を決定するフレームｆまでの各連結リスト３０を順次遡って参照して、アンカーポイントＡＰ２４９に対応する対応点候補を順を追って探索し、ステップ１４８でｊ＝Ｊになった時点で（ステップ１４９のＮｏ）、対応点Ｑ６０を決定するフレームｆにおける対応点候補ａｐ２６９を得る。
【００９５】
次に、制御部１１は、図１５のステップ１５２に進み、図１６（ｂ）に示すように、対応点Ｑ６０を決定するフレームｆの対応点候補ａｐ１６８及びａｐ２６９を結ぶ直線をＩ：Ｊに分割する点に最も近い代表点を抽出し、対応点Ｑ６０とする。
以上の処理により、フレームｆについての、アンカーポイントＡＰ１４８及びＡＰ２４９との対応点Ｑ６０が決定され、制御部１１は、対応点Ｑ６０の座標を記憶部１２に格納する。
【００９６】
次に、制御部１１は、ｆを１インクリメントし（ステップ１５３）、ｆがキーフレームＦ２よりも小さいか否かを判定し（ステップ１５４）、小さい場合（ステップ１５４のＹｅｓ）は、図１４のステップ１４２に戻り、ステップ１４２〜ステップ１５４の処理を繰り返す。
これにより、キーフレームＦ１とＦ２の間の全てのフレームｆについての対応点Ｑ６０を決定することが可能になる。
【００９７】
以上の処理により、本実施形態に係る対応点決定装置１は、連結リスト３０と、アンカーポイントＡＰを使用することにより、隣接する前後のフレームの対応関係だけでなく、２つのキーフレームに設定したアンカーポイントに基づいた対応点Ｑを決定することが可能になり、精度の高いズレのない対応点決定を可能とする。これにより、輪郭線の堅牢な対応付けが可能になる。
【００９８】
以上、添付図を参照しながら、本発明の実施の形態を説明したが、本発明の技術的範囲は、前述した実施の形態に左右されない。当業者であれば、特許請求の範囲に記載された技術的思想の範疇内において各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【００９９】
１…………対応点決定装置
２１、２２、２３、２４、２５………輪郭線
２７………代表点
２８………開始フレーム
２９………終了フレーム
３０………連結リスト
３２………前のフレームの対応点候補
３３………後のフレームの対応点候補
４０、４１………キーフレーム
４８、４９………アンカーポイント
６０………対応点
【図１】
2014191695.tif 000008
【図２】
2014191695.tif 000009
【図３】
2014191695.tif 000010
【図４】
2014191695.tif 000011
【図５】
2014191695.tif 000012
【図６】
2014191695.tif 000013
【図７】
2014191695.tif 000014
【図８】
2014191695.tif 000015
【図９】
2014191695.tif 000016
【図１０】
2014191695.tif 000017
【図１１】
2014191695.tif 000018
【図１２】
2014191695.tif 000019
【図１３】
2014191695.tif 000020
【図１４】
2014191695.tif 000021
【図１５】
2014191695.tif 000022
【図１６】
2014191695.tif 000023