(57)【要約】【課題】複数画像にわたって、一括して処理されるべき閉領域を、好適かつ自動的に対応付けることを可能とするマッチング技術を提供することを課題とする。【解決手段】情報処理装置１によって、閉領域を有する複数の画像間で閉領域どうしを対応付けるプログラムに、閉領域の特徴量であって、閉領域内の各点の座標の成分を積和演算することで得られる特徴量、又は基準点に対する閉領域内の各点の距離の分布から得られる特徴量を抽出する特徴量抽出部２１と、特徴量抽出部２１によって抽出された、画像が有する各閉領域の特徴量に基づいて、第１の画像が有する各閉領域と第２の画像が有する各閉領域とを対応付ける閉領域対応付け部２３とを備えた。【選択図】図６
2014106713.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによって、閉領域を有する複数の画像間で前記閉領域どうしを対応付けるプログラムであって、
前記閉領域の特徴量であって、前記閉領域内の各点の座標の成分を積和演算することで得られる特徴量、又は基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量を抽出する特徴量抽出工程と、
前記特徴量抽出工程において抽出された、前記画像が有する各閉領域の前記特徴量に基づいて、第１の画像が有する各閉領域と第２の画像が有する各閉領域とを対応付ける閉領域対応付け工程と、
を備えるプログラム。
【請求項２】
請求項１における前記特徴量抽出工程において、前記閉領域内の各点の座標の成分を積和演算することで得られる特徴量として、前記閉領域の慣性主軸の角度を抽出するプログラム。
【請求項３】
前記特徴量抽出工程において、前記閉領域内の各点の座標の成分を積和演算することで得られる特徴量を、前記閉領域内の各点の座標の各成分から計算される共分散行列の固有値及び固有ベクトルに基づいて抽出する、
請求項１又は２に記載のプログラム。
【請求項４】
請求項１における前記特徴量抽出工程において、基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量として、前記閉領域の境界線上を動く動点の始点からの道のりを変数とする、該動点の基準点からの距離の関数を求め、求めた該関数に対してフーリエ変換をした結果から、所定よりも低周波数の成分を抽出するプログラム。
【請求項５】
請求項１における前記特徴量抽出工程において、基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量として、前記閉領域の境界線上の複数の点を所定の基準で選択し、選択した各点と基準点との距離を成分とするベクトルを抽出するプログラム。
【請求項６】
請求項１における前記特徴量抽出工程において、基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量として、基準点を原点とした前記閉領域内の各点の極座標における動径と偏角とを変量とする、２変量のヒストグラムを抽出するプログラム。
【請求項７】
前記特徴量抽出工程において、前記閉領域の特徴量として、特徴量の抽出対象の閉領域に隣接する各閉領域の重心に基づいて算出される座標である隣接領域重心位置を、更に抽出する、
請求項１から６の何れか１項に記載のプログラム。
【請求項８】
前記特徴量抽出工程において抽出された前記特徴量に基づいて、２つの閉領域間の相違の程度を示すコストを算出するコスト算出工程を更に備え、
前記閉領域対応付け工程は、対応付ける各閉領域間の前記コストの総和に基づいて、第１の画像が有する各閉領域を、第２の画像が有する１つ以下の前記閉領域と対応付ける、
請求項１から７の何れか１項に記載のプログラム。
【請求項９】
閉領域を有する複数の画像間で前記閉領域どうしを対応付ける方法であって、
コンピュータによって、
前記閉領域の特徴量であって、前記閉領域の各点の座標の成分を積和演算することで得られる特徴量、又は基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量を抽出する特徴量抽出工程と、
前記特徴量抽出工程において抽出された、前記画像が有する各閉領域の前記特徴量に基づいて、第１の画像が有する各閉領域と第２の画像が有する各閉領域とを対応付ける閉領域対応付け工程と、
が実行される方法。
【請求項１０】
閉領域を有する複数の画像間で前記閉領域どうしを対応付ける情報処理装置であって、
前記閉領域の特徴量であって、前記閉領域内の各点の座標の成分を積和演算することで得られる特徴量、又は基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量を抽出する抽出手段と、
前記抽出手段によって抽出された、前記画像が有する各閉領域の前記特徴量に基づいて、第１の画像が有する各閉領域と第２の画像が有する各閉領域とを対応付ける閉領域対応付け手段と、
を備える情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、閉領域を有する複数の画像間で閉領域どうしを対応付けるプログラム、情報処理方法、及び情報処理装置に関する。
【背景技術】
【０００２】
従来、手書きアニメーションの彩色工程では、紙に描かれた線画をスキャナによりデジタルデータ化し、コンピュータ上で、デジタルデータ化された画像１枚ずつを手作業で彩色するデジタルペインティングが行われている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第２８３５７５２号公報
【非特許文献】
【０００４】
【非特許文献１】GARCIA TRIGO, P., JOHAN, H., IMAGIRE, T., AND NISHITA,T. "Interactive region matching for 2D animation coloring based on feature’s variation." IEICE Transactions (E92-D) , 2009, 6, p.1289-1295.
【非特許文献２】MADEIRA, J. S., STORK, A., AND GROSS, M. H. "An approach to computer-supported cartooning." The Visual Computer12, 1996, 1, p.1-17.
【非特許文献３】QIU, J., SEAH, H. S. AND TIAN, F. "Auto coloring with character registration." In Proceedings of the 2006 internationalconference on Game research and development, CyberGames'06, 2006, p.25-32.
【非特許文献４】SIVIC, J., AND ZISSERMAN, A. "Video Google: A text retrieval approach to object matching in videos." In Proceedings of the International Conference on Computer Vision, 2003, vol. 2, p.1470-1477.
【非特許文献５】SYKORA, D., DINGLIANA, J., AND COLLINS, S. "As-rigid-as-possible image registration for hand-drawn cartoon animations." In Proceedings of the 7th International Symposium on Non-Photorealistic Animation and Rendering, NPAR '09, 2009, p. 25-33.
【非特許文献６】SYKORA, D., DINGLIANA, J., AND COLLINS, S. "Lazy-Brush: Flexible painting tool for hand-drawn cartoons." Computer Graphics Forum 28, 2009, 2, p.599-608.
【非特許文献７】SYKORA, D., BEN-CHEN, M., CADIK, M., WHITED, B., AND SIMMONS, M. "Textoons: practical texture mapping for hand-drawn cartoon animations." In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Non-Photorealistic Animation and Rendering, NPAR'11, 2011 , p. 75-84.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
例えば、手書きアニメーションの線画の彩色工程では、一般に、線画を１コマずつ手動で彩色することが行われている。手書きアニメーションの連続するコマの線画は、同一のキャラクタが描かれる等、同一色で彩色されるべき対応する閉領域を含む場合が多い。しかし、従来、このような閉領域の対応関係を好適かつ自動的に導く方法がなく、対応する領域を一括して彩色できないという問題があった。
【０００６】
本発明は、上記の問題に鑑み、複数画像にわたって、一括して処理されるべき閉領域を、好適かつ自動的に対応付けることを可能とするマッチング技術を提供することを課題と
する。
【課題を解決するための手段】
【０００７】
本発明では、上記課題を解決するために、以下の手段を採用した。すなわち、本発明は、コンピュータによって、閉領域を有する複数の画像間で前記閉領域どうしを対応付けるプログラムであって、前記閉領域の特徴量であって、前記閉領域内の各点の座標の成分を積和演算することで得られる特徴量、又は基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量を抽出する特徴量抽出工程と、前記特徴量抽出工程において抽出された、前記画像が有する各閉領域の前記特徴量に基づいて、第１の画像が有する各閉領域と第２の画像が有する各閉領域とを対応付ける閉領域対応付け工程と、を備えるプログラムである。
【０００８】
ここで、本発明において、画像は、白黒の線画であってもよく、色の濃淡や色彩を有する画像であってもよい。また、画像は、ラスタ画像であってもよく、ベクタ画像であってもよい。また、閉領域は、例えば、画像が線画である場合、線で囲われた閉じた領域である。
【０００９】
また、本発明において、特徴量は、１つのスカラ値だけでなく、ベクトル値、複数の値の組である場合も含む。また、閉領域内は、閉領域内部だけでなく、閉領域の境界線上に位置する場合を含む。また、閉領域内の各点は、閉領域内の有限個の点だけでなく無限個の点であってもよい。ラスタ画像における閉領域内の各点は、例えば、閉領域内のすべての画素に対応する有限個の点や、互いにｘ軸方向、及びｙ軸方向の距離が一定となるような閉領域内の有限個の点である。また、ベクタ画像における閉領域の各点は、例えば、閉領域内にとることができるすべての点（無限個の点）である。また、座標は、直交座標系に限られず、極座標系における座標も含む。また、閉領域内の各点の座標の成分を積和演算することで得られる特徴量は、積和演算以外の演算もあわせて行うことで得られる特徴量を含む。また、各点の距離の分布は、離散的な値の分布である場合と連続的な無限個の値の分布である場合との双方を含む。
【００１０】
また、本発明において、閉領域対応付け工程における対応付けには、第１の画像が有する閉領域のうち、その一部が第２の画像が有する閉領域と対応付けられない、対応付けも含まれる。例えば、第１の画像が有する閉領域の数と第２の画像が有する閉領域の数とが異なる場合に、多い閉領域の数を有する画像の一部の閉領域を対応付けないような対応付けも含まれる。また、閉領域対応付け工程における対応付けには、第１の画像が有する或る閉領域を、第２の画像が有する複数の閉領域と対応付ける、対応付けも含まれる。
【００１１】
本発明によれば、各閉領域内の各点から抽出される特徴量に基づいて画像間で閉領域どうしを対応付けるため、複数画像にわたって、一括して処理されるべき閉領域を、好適かつ自動的に対応付けることができる。
【００１２】
また、本発明に係るプログラムの特徴量抽出工程において、前記閉領域内の各点の座標を積和演算することで得られる特徴量として、前記閉領域の慣性主軸の角度を抽出してもよい。
【００１３】
ここで、本発明において、慣性主軸の角度は、ベクトルで表現されるものを含む。
【００１４】
また、本発明に係るプログラムの特徴量抽出工程において、前記閉領域内の各点の座標を積和演算することで得られる特徴量を、前記閉領域内の各点の座標の各成分から計算される共分散行列の固有値及び固有ベクトルに基づいて抽出してもよい。
【００１５】
また、本発明に係るプログラムの特徴量抽出工程において、閉領域内の重心と閉領域内に各点の座標の共分散行列とを求め、求めた前記重心及び前記共分散行列を、期待値及び共分散行列に持つ２次元正規分布において、所定の確率密度となる座標を通る楕円を求め、楕円を構成する成分から前記閉領域の特徴量を抽出してもよい。
【００１６】
また、本発明に係るプログラムの特徴量抽出工程において、基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量として、前記閉領域の境界線上を動く動点の始点からの道のりを変数とする、該動点の基準点からの距離の関数を求め、求めた該関数に対してフーリエ変換をした結果から、所定よりも低周波数の成分を抽出してもよい。
【００１７】
ここで、本発明において、フーリエ変換は、離散フーリエ変換を含む。
【００１８】
また、本発明に係るプログラムの特徴量抽出工程において、基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量として、前記閉領域の境界線上の複数の点を所定の基準で選択し、選択した各点と基準点との距離を成分とするベクトルを抽出してもよい。
【００１９】
また、本発明に係るプログラムの特徴量抽出工程において、基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量として、基準点を原点とした前記閉領域内の各点の極座標における動径と偏角とを変量とする、２変量のヒストグラムを抽出してもよい。
【００２０】
また、本発明に係るプログラムの特徴量抽出工程において、前記閉領域の特徴量として、特徴量の抽出対象の閉領域に隣接する各閉領域の重心に基づいて算出される座標である隣接領域重心位置を、更に抽出してもよい。
【００２１】
ここで、本発明において、隣接するとは、閉領域どうしがその境界線の一部を共有することをいう。
【００２２】
また、本発明に係るプログラムは、前記特徴量抽出工程において抽出された前記特徴量に基づいて、２つの閉領域間の相違の程度を示すコストを算出するコスト算出工程を更に備え、前記閉領域対応付け工程は、対応付ける各閉領域間の前記コストの総和に基づいて、第１の画像が有する各閉領域を、第２の画像が有する１つ以下の前記閉領域と対応付けてもよい。
【００２３】
ここで、本発明において、閉領域対応付け手段が行う対応付けには、第１の画像が有する或る閉領域を、第２の画像が有する閉領域と対応付けない、対応付けが含まれる。
【００２４】
また、本発明は、そのようなプログラムをコンピュータその他の装置、機械等が読み取り可能な記録媒体に記録したものでもよい。ここで、コンピュータ等が読み取り可能な記録媒体とは、データやプログラム等の情報を電気的、磁気的、光学的、機械的、又は化学的作用によって蓄積し、コンピュータ等から読み取ることができる記録媒体をいう。
【００２５】
また、本発明は、閉領域を有する複数の画像間で前記閉領域どうしを対応付ける方法であって、コンピュータによって、前記閉領域の特徴量であって、前記閉領域の各点の座標の成分を積和演算することで得られる特徴量、又は基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量を抽出する特徴量抽出工程と、前記特徴量抽出工程において抽出された、前記画像が有する各閉領域の前記特徴量に基づいて、第１の画像が有する各閉領域と第２の画像が有する各閉領域とを対応付ける閉領域対応付け工程が実行される方法であってもよい。
【００２６】
また、本発明は、閉領域を有する複数の画像間で前記閉領域どうしを対応付ける情報処理装置であって、前記閉領域の特徴量であって、前記閉領域内の各点の座標の成分を積和演算することで得られる特徴量、又は基準点に対する前記閉領域内の各点の距離の分布から得られる特徴量を抽出する抽出手段と、前記抽出手段によって抽出された、前記画像が有する各閉領域の前記特徴量に基づいて、第１の画像が有する各閉領域と第２の画像が有する各閉領域とを対応付ける閉領域対応付け手段を備える情報処理装置であってもよい。
【発明の効果】
【００２７】
本発明の一側面によれば、複数画像にわたって、一括して処理されるべき閉領域を、好適かつ自動的に対応付けることを可能とするマッチング技術を提供することができる。
【図面の簡単な説明】
【００２８】
【図１】実施形態１に係るプログラムが実行される情報処理装置の構成を示す概略図である。
【図２】実施形態１に係るプログラムが対応付ける複数の画像の例である。
【図３】実施形態１に係るプログラムが扱う閉領域の例を示す図である。
【図４】実施形態１に係るプログラムが実行される情報処理装置の機能構成の概略を示す図である。
【図５】閉領域の慣性主軸の例を示す図である。
【図６】各閉領域に係る代表の楕円の例を示す図である。
【図７】２画像間での閉領域どうしの対応付けの例を示すイメージ図である。
【図８】複数の画像間での閉領域どうしの対応付けの例を示すイメージ図である。
【図９】複数の画像間で閉領域どうしを対応付ける処理の流れ示すフローチャートである。
【図１０】２画像間で閉領域どうしを対応付ける処理の流れ示すフローチャートである。
【図１１】閉領域に係る動点の例を示す図である。
【図１２】動点と重心との距離の関数の例を示すグラフである。
【図１３】選択した各点と重心との距離を示すイメージ図である。
【発明を実施するための形態】
【００２９】
以下、本発明の実施の形態について、図面に基づいて説明する。本実施形態において、複数の画像は、アニメーションを構成する各フレーム（コマ）の線画として実施される。なお、以下に説明する実施の形態は、本発明を実施する一例を示すものであって、本発明を以下に説明する具体的構成に限定するものではない。本発明を実施するにあたっては、実施の形態に応じた具体的構成が適宜採用されることが好ましい。
【００３０】
≪実施形態１≫
＜構成＞
図１は、実施形態１に係るプログラムが実行される情報処理装置の構成を示す概略図である。
【００３１】
情報処理装置１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１２、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１３、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等の補助記憶装置１４、及び周辺機器を接続する外部インターフェース１５を備えたコンピュータである。
【００３２】
ＣＰＵ１１は、中央処理装置であり、ＲＡＭ１２等に展開された各種プログラムの命令
およびデータを処理することで、ＲＡＭ１２、補助記憶装置１４等を制御する。ＲＡＭ１２は、主記憶装置であり、ＣＰＵ１１によって制御され、各種命令やデータが書き込まれ、読み出される。補助記憶装置１４は、不揮発性の補助記憶装置であり、ＲＡＭ１２にロードされるＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）や本実施形態に係るプログラム等の各種プログラム、アニメーションの各フレームの線画等、主にコンピュータの電源を落としても保持したい情報が書き込まれ、読み出される。外部インターフェース１５には、スキャナ２が接続されている。スキャナ２は、紙媒体に描かれた複数の線画３を読み取る。読み取られた線画３は、デジタル画像として情報処理装置１に取り込まれ、アニメーションの各フレームを構成する。
【００３３】
図２は、実施形態１に係るプログラムが対応付ける複数の画像の例である。図２には、複数の画像として、アニメーションにおいて順に連続して表示されるフレームＦ１、Ｆ２、Ｆ３及びＦ４が示されている。本実施形態において、各フレームの線画は、所定の画像サイズのラスタ画像として与えられる。本実施形態において、各フレームは、左上の角を原点とし、水平右方向にｘ軸、垂直下方向にy軸を取った座標系有する。なお、各フレー
ムの線画は、ベクタ画像として与えられてもよい。ベクタ画像として与えられた場合は、プログラムは、与えられた画像を、ラスタ画像に変換して取り扱ってもよいし、ベクタ画像のまま取り扱ってもよい。
【００３４】
図３は、実施形態１に係るプログラムが扱う閉領域の例を示す図である。図３には、図２のフレームＦ１の線画が有する閉領域の例として、閉領域Ｒ１０１（斜線部分）、Ｒ１０２（網掛け部分）、及びＲ１０３（チェック部分）が示されている。フレームＦ１の線画が有する閉領域は、これらの閉領域に限らず、他の線（黒色の画素）で囲まれた部分すべて（白色の画素）が該当する。なお、濃淡を有する画像に対しては、所定以上の濃さを有する画素や線に囲われた部分を閉領域と扱ってもよい。また、彩色を有する画像に対しては、黒色の線で囲まれた部分を閉領域として扱い、黒色以外の色彩を無視してもよい。また、彩色を有する画像に対しては、所定の色彩を有する画素で囲われた部分を閉領域として扱ってもよい。
【００３５】
図４は、実施形態１に係るプログラムが実行される情報処理装置１の機能構成の概略を示す図である。本実施形態に係るプログラムは、ＲＡＭ１２に読み出され、ＣＰＵ１１によって実行されることで、特徴量抽出部２１、コスト算出部２２、及び閉領域対応付け部２３として機能する。なお、本実施形態では、情報処理装置１の備える各機能は、汎用プロセッサであるＣＰＵ１１によって実行されるが、これらの機能の一部又は全部は、１又は複数の専用プロセッサによって実行されてもよい。
【００３６】
本実施形態において、特徴量抽出部２１は、閉領域の特徴量であって、閉領域内の各点の座標の成分を積和演算することで得られる特徴量として、閉領域の慣性主軸の角度を抽出する。具体的には、特徴量抽出部２１は、閉領域内のすべての白色画素（各点に相当）の座標の各成分から計算される共分散行列の固有値及び固有ベクトルを算出し、算出した固有ベクトルから慣性主軸の角度を求める。
【００３７】
本実施形態において、特徴量抽出部２１は、閉領域の特徴量として、当該共分散行列の固有値、及び閉領域内の白色画素の平均座標（閉領域の重心の位置に相当する）を、更に抽出する。また、特徴量抽出部２１は、閉領域の特徴量として、特徴量の抽出対象の閉領域に隣接する各閉領域の重心に基づいて算出される座標である隣接領域重心位置を、更に抽出する。つまり、本実施形態の特徴量抽出部２１は、閉領域の特徴量として、閉領域の慣性主軸の角度、閉領域内の白色画素の座標の各成分から計算される共分散行列の固有値、閉領域内の白色画素の平均座標、及び隣接領域重心位置を抽出する。以下、詳細を説明する。
【００３８】
まず、特徴量抽出部２１は、閉領域ｉ内の全画素の平均座標ｔiを算出する。この平均
座標は閉領域の重心にあたる。次に、特徴量抽出部２１は、閉領域ｉ内の全画素の座標の共分散行列Ｃiを求める。ここで、共分散行列Ｃiを求めるにあたり、座標のｘ成分及びｙ成分を確率変数として扱う。共分散行列Ｃiは、閉領域ｉ内の全画素数をN、各画素の座標を示す縦ベクトルをｐm（ｍ＝１，２，…，Ｎ）、平均座標ｔiを縦ベクトルとして、数式１で表される。なお、記号Ｔは、ベクトルの転置を意味する。
【数１】
2014106713.tif 000003
【００３９】
本実施形態において、共分散行列Ｃiを求めることは、閉領域内の各点の座標の成分を
積和演算することに相当する。共分散行列Ｃiは、例えば、ｔiのｘ成分、ｙ成分をｔix、ｔiyとし、ｐmのｘ成分、ｙ成分をｐmx、ｐmyとして、数式２となる。
【数２】
2014106713.tif 000004
数式２より、ｘ座標成分の２乗の和（Σ）、ｙ座標成分の２乗の和、ｘ座標成分とｙ座標成分との積の和が演算されることがわかる。
【００４０】
次に、特徴量抽出部２１は、共分散行列Ｃiの大小の固有値を求め、大きい固有値をλimaxとし、小さい固有値をλiminとする。次に、特徴量抽出部２１は、固有値λimaxに対
する固有ベクトルｅimax、及び固有値λiminに対する固有ベクトルｅiminを求める。次に、特徴量抽出部２１は、固有ベクトルｅimaxの方向を、閉領域の特徴量である、慣性主軸の角度として抽出する。また、特徴量抽出部２１は、特徴量として、固有値λimax、λimin、平均座標ｔiも更に抽出する。
【００４１】
なお、固有値λimax及びλimin、固有ベクトルｅimax及びｅimin、並びに平均座標ｔi
により、閉領域内の白色画素の座標の分布を代表する楕円を構成することができる。閉領域iの座標の分布を代表する楕円の長軸Li及び短軸Siは、数式３で定義できる。
【数３】
2014106713.tif 000005
また、楕円の中心は、重心ｔiで定義できる。特徴量抽出部２１が抽出する、慣性主軸の
角度、固有値、及び平均座標は、それぞれ、この楕円の傾き、大きさ、及び重心に対応する。なお、この楕円は、重心ｔi及び共分散行列Ｃiを、期待値及び共分散行列に持つ２次元正規分布において、所定の確率密度となる座標を通る楕円とみることもできる。
【００４２】
図５は、閉領域の慣性主軸の例を示す図である。図５で、慣性主軸I１０１は、閉領域
Ｒ１０１に対する慣性主軸の角度（方向）を示している。楕円Ｅ１０１は、閉領域Ｒ１０
１内の各画素の座標の分布を代表する楕円である。重心Ｃ１０１は、閉領域Ｒ１０１の重心であり、楕円Ｅ１０１の重心（中心）である。慣性主軸I１０１の角度は、楕円Ｅ１０
１の長軸の方向と一致する。
【００４３】
図６は、各閉領域に係る代表の楕円の例を示す図である。図６には、フレームＦ１及びＦ２の各閉領域内の座標の分布を代表する楕円が示されている。図６において、特徴量抽出部２１によって抽出された特徴量（慣性主軸の角度、固有値、及び平均座標）は、各楕円により視覚的に示されている。
【００４４】
本実施形態によれば、共分散行列Ｃiは２行２列の行列であり、その固有値及び固有ベ
クトルの算出は比較的容易であるため、閉領域の形状全体を反映した特徴量を比較的少ない計算量で抽出することができる。
【００４５】
なお、本実施形態において、特徴量抽出部２１は、共分散行列Ｃiの固有ベクトルｅimaxから閉領域の慣性主軸の角度を求めたが、特徴量抽出部２１は、数式４により、慣性主
軸の角度θを抽出してもよい。
【数４】
2014106713.tif 000006
【００４６】
なお、特徴量抽出部２１が共分散行列Ｃiを求める際に用いる座標には、閉領域の境界
線上の画素の座標を含めてもよい。また、特徴量抽出部２１が共分散行列Ｃiを求める際
に用いる座標には、閉領域内の白色画素のうち、ｘ軸方向（水平方向）、ｙ軸方向（垂直方向）それぞれについて、所定ピクセルごとの間隔で、間引いた白色画素についての座標を採用してもよい。また、特徴量抽出部２１が共分散行列Ｃiを求める際に用いる座標に
は、乱数に基づいて選ばれた、閉領域内の所定数の白色画素についての座標を採用してもよい。
【００４７】
さらに、本実施形態において、特徴量抽出部２１は、数式５及び数式６で定義される隣接領域重心位置ｎiを算出して、これを閉領域ｉの特徴量として更に抽出する。
【数５】
2014106713.tif 000007
【数６】
2014106713.tif 000008
ここで、Ｏiは閉領域ｉに隣接する領域群、すなわち、境界線の一部を共有する領域群を
示す。ただし、Ｏiは、背景領域（境界線にフレームの端辺の一部または全部を含む領域
）も含む領域とする。また、αkは、閉領域ｉの面積である。また、βkは、閉領域ｉ境界線が閉領域ｋに接する程度を表す、０以上１以下の範囲の割合を示す。また、σ0は、所
定の係数を示す。また、数式５及び数式６では、閉領域ｋが背景領域である場合、αk＝
αi、ｔk＝ｔi、として、隣接領域重心位置ｎiを算出する。なお、本実施形態では、Ｏi
が背景領域を含むが、Ｏiが背景領域を含まない実施形態を採用してもよい。
【００４８】
連続するフレーム間では閉領域の隣接関係が類似している可能性が高い。本実施形態によれば、隣接する閉領域の特徴も加味して、当該閉領域の特徴量が抽出されるため、閉領域どうしの対応付けの精度を高めることができる。
【００４９】
本実施形態において、コスト算出部２２は、特徴量に基づいて、２つの閉領域間の相違の程度を示すコストを算出する。具体的には、特徴量抽出部２１は、閉領域ｉと閉領域ｊとのコストａijを数式７から数式１１までを用いて算出する。
【数７】
2014106713.tif 000009
【数８】
2014106713.tif 000010
【数９】
2014106713.tif 000011
【数１０】
2014106713.tif 000012
【数１１】
2014106713.tif 000013
【００５０】
数式７において、ｗangle、ｗscale、ｗpos、及びｗneighborは、各項の重み付けを目
的とした所定の定数である。数式７は、特徴量抽出部２１が抽出した慣性主軸の角度の相
違（あるいは座標の分布を代表する楕円間における傾きの相違）の程度を示すａijangle
、固有値の相違（あるいは座標の分布を代表する楕円間の大きさの相違）の程度を示すａijscale、重心の位置の相違の程度を示すａijpos、及び隣接領域重心位置の相違の程度を示すａijneighborの加重和として、コストａijを定義している。コストａijは、閉領域ｉの特徴量と閉領域ｊの特徴量とが同一の場合、０となる。なお、重心ｔi及びｔjは、フレームの大きさ（画像サイズ）に合わせて標準化された値として算出されてもよい。このようにすることで、異なる大きさのフレーム間でも好適な対応付けが可能となる。
【００５１】
なお、コストａijは、ａijneighborを考慮せずに、ａijangle、ａijscale、及びａijpos、の加重平均として定義することを採用してもよい。
【００５２】
本実施形態において、閉領域対応付け部２３は、線画が有する各閉領域の特徴量に基づいて算出されたコストの総和に基づいて、第１のフレームの線画が有する各閉領域を第２のフレームが有する１以下の閉領域と対応付ける。本実施形態において、第１のフレームと第２のフレームとは、例えばフレームＦ１とＦ２とのように、連続するフレームである。
【００５３】
まず、閉領域対応付け部２３は、第１のフレームｆの線画が有する各閉領域ｉと、第２のフレームｆ＋１の線画が有する各閉領域ｊと間のコストａijを要素とする、閉領域の対応付けに関するコスト表を算出する。このコスト表は、第１のフレームｆの領域数をＮf
、第２のフレームｆ＋１の領域数をＮf+1とすると、Ｎf行Ｎf+1列の表になる。次に、閉
領域対応付け部２３は、このコスト表を参照し、対応付ける閉領域間のコストの総和が最小となるように、各閉領域どうしを対応付ける。ここで、閉領域対応付け部２３は、各閉領域ｉを、最大１つの閉領域ｊと対付ける。また、閉領域対応付け部２３は、Ｎf＞Ｎf+1の場合は、第１のフレームの線画の閉領域のうち、（Ｎf−Ｎf+1）個の閉領域の対応付けを行わない。
【００５４】
より具体的には、閉領域対応付け部２３は、閉領域を点、対応付けを辺とし、各閉領域ｉと各閉領域ｊとを部集合とする、２部グラフのマッチングの問題を解く。閉領域対応付け部２３は、コストに基づき、ハンガリー法を用いて最大マッチングを求めることで、各領域どうしの対応付けを行う。
【００５５】
図７は、２画像間での閉領域どうしの対応付けの例を示すイメージ図である。図７には、フレームＦ１とＦ２との間での、各閉領域どうしの対応付けが示されている。図７では、対応付けは、各閉領域の重心どうしを線分で結ぶことによって表現されている。例えば、閉領域Ｒ１０１とＲ２０１との間、Ｒ１０２とＲ２０２との間、及び、Ｒ１０３とＲ２０３との間が対応付いている。
【００５６】
図８は、複数の画像間での閉領域どうしの対応付けの例を示すイメージ図である。図８には、フレームＦ１とＦ２との間、フレームＦ２とＦ３との間、及びフレームＦ３とＦ４との間で各閉領域どうしの対応付けが示されている。図８において、対応付けは、図７と同様に、各閉領域の重心どうしを線分で結ぶことによって表現されている。
【００５７】
図８において、フレームＦ２の閉領域の数は、フレームＦ３の閉領域の数より多い。そのため、例えば、閉領域対応付け部２３は、フレームＦ２の閉領域Ｒ２０２をフレームＦ３の閉領域と対応付けない。このことは、フレームＦ２の線画では、描かれているキャラクタの左耳を構成する閉領域Ｒ２０２が存在しているのに対し、フレームＦ３の線画では、描かれているキャラクタの左耳が隠れており、左耳を構成する閉領域が存在せず、閉領域Ｒ２０２と一括して同様の処理すべき閉領域がフレームＦ３に存在しないことを意味する。
【００５８】
また、図８において、フレームＦ３の閉領域の数は、フレームＦ４の閉領域の数より少ない。そのため、閉領域対応付け部２３は、例えば、フレームＦ４の閉領域Ｒ４０４をフレームＦ３の閉領域と対応付けない。
【００５９】
本実施形態に係るプログラムは、閉領域対応付け部２３による対応付けから、連続する複数のフレームにわたる、一連の各閉領域の対応付けの系列（以下「チェーン」という）を導くことができる。閉領域対応付け部２３は、フレームＦ１の閉領域Ｒ１０１とフレームＦ２の閉領域Ｒ２０１とを対応付け、閉領域Ｒ２０１とフレームＦ３の閉領域Ｒ３０１とを対応付け、閉領域Ｒ３０１とフレームＦ４の閉領域Ｒ４０１とを対応付ける。本実施形態に係るプログラムは、これらの対応付けから、閉領域Ｒ１０１、Ｒ２０１、Ｒ３０１、及びＲ４０１を対応付けるチェーンを導くことができる。
【００６０】
本実施形態によれば、例えば、ユーザが彩色処理対象の閉領域Ｒ１０１及びその色を指定した場合に、上述のチェーンによって、対応付いた閉領域Ｒ１０１、Ｒ２０１、Ｒ３０１、及びＲ４０１を一括して指定された色で彩色することを容易に実現でき、閉領域ごとに彩色する場合に比べ、線画の彩色にかかる労力を削減することが可能になる。
【００６１】
＜処理の流れ＞
図９及び図１０のフローチャートを用いて、本実施形態に係るプログラムの処理の流れを説明する。なお、フローチャートに示された処理の具体的な内容および順序は一例であり、処理内容および順序には、実施の形態に適したものが適宜採用されることが好ましい。
【００６２】
図９は、複数の画像間で閉領域どうしを対応付ける処理の流れ示すフローチャートである。この処理の流れは、ユーザが、新たにアニメーションを構成する各フレームの線画を情報処理装置１に取り込む操作をしたことを契機に開始される。
【００６３】
ステップＳ１０１では、本実施形態に係るプログラムが、スキャナ２を介して紙媒体の線画３をデジタル画像として取り込むことによって、連続するフレームの線画として、複数の画像を入力する。
【００６４】
ステップＳ１０２では、本実施形態に係るプログラムが、各フレームの線画が有する閉領域を検出する。本実施形態に係るプログラムは、線画内の各画素から、領域の内部と外部との境界となる画素（黒色）をスキャンすることで、閉領域を検出する。この際、本実施形態に係るプログラムは、塗りつぶしのアルゴリズム（シードフィル等）を利用することで、既に検出した閉領域と未検出の閉領域とを区別する。
【００６５】
なお、青色、赤色等の黒色以外の画素も境界となる画素として扱ってもよい。また、青色で囲まれる閉領域を、暗い色で彩色処理すべき閉領域として、黒色で囲まれる閉領域とは別に検出してもよい。また、赤色で囲まれる閉領域を、明るい色で彩色処理すべき閉領域として、黒色で囲まれる閉領域とは別に検出してもよい。そして、閉領域対応付け部２３は、このように別に検出された赤色で囲まれる閉領域どうしを対応付けてもよい。このようにすることで、明るい色で一括処理して彩色されるべき閉領域どうしを精度良く対応付けることができる。また、閉領域対応付け部２３は、このように別に検出された青色で囲まれる閉領域どうしを対応付けてもよい。このようにすることで、暗い色で一括処理して彩色されるべき閉領域どうしを精度良く対応付けることができる。
【００６６】
ステップＳ１０３では、特徴量抽出部２１が、閉領域の特徴量（慣性主軸の角度、閉領域内の白色画素の座標の各成分から計算される共分散行列の固有値、閉領域内の白色画素
の平均座標、及び隣接領域重心位置）を抽出する。
【００６７】
ステップＳ１０４からＳ１０７では、全フレーム間の閉領域どうしの対応付けがされる。ステップＳ１０４及びＳ１０７は、全フレーム間対応付けループを構成する。まず、ステップＳ１０４では、本実施形態に係るプログラムが、全フレーム間の閉領域どうしが対応付け済みであるか否かを判定する。ステップＳ１０４において、全フレーム間の閉領域どうしが対応付け済みであると判定されなかった場合は、処理は、ステップＳ１０５へ進む。ステップＳ１０４において、全フレーム間の閉領域どうしが対応付け済みであると判定された場合は、処理は、終了する。次に、ステップＳ１０５では、本実施形態に係るプログラムが、次の未処理の２フレーム間を処理対象に設定する。ステップＳ１０７では、処理が、ステップＳ１０４に戻る。
【００６８】
ステップＳ１０５では、処理対象の２フレーム間で各閉領域どうしが対応付けられる。ステップＳ１０５の具体的な処理の流れについては、後述する。
【００６９】
図１０は、２画像間で閉領域どうしを対応付ける処理の流れ示すフローチャートである。この処理の流れは、図９のステップＳ１０５の処理を詳しく示したものである。
【００７０】
ステップＳ２０１からＳ２０４では、コスト算出部２２がコスト表を算出する。ステップＳ２０１及びＳ２０４は、コスト表算出ループを構成する。まず、ステップＳ２０１では、コスト算出部２２が、全閉領域間のコストが算出済みであるか否かを判定する。ステップＳ２０１において、全閉領域間のコストが算出済みであると判定されなかった場合は、処理は、ステップＳ２０２へ進む。ステップＳ２０１において、全閉領域間のコストが算出済みであると判定された場合は、処理は、ステップＳ２０５へ進む。次に、ステップＳ２０２では、コスト算出部２２が、連続する複数フレームのうち、次の未処理の閉領域間を処理対象に設定する。ステップＳ２０４では、処理が、ステップＳ２０１に戻る。
【００７１】
ステップＳ２０３では、コスト算出部２２が、各閉領域の特徴量に基づいて、処理対象の２つの閉領域間のコスト（コスト表）を算出する。
【００７２】
ステップＳ２０５では、閉領域対応付け部２３が、コスト算出部２２によって算出されたコスト表を参照し、閉領域間のコストの総和が最小になるように、処理対象のフレーム間の各閉領域どうしを対応付ける。
【００７３】
以上述べたように、本実施形態によれば、複数フレームにわたって、一括して彩色等の処理されるべき閉領域を、好適かつ自動的に対応付けることができる。また、彩色済みの閉領域と未彩色の閉領域とを対応付けることにより、彩色済みの閉領域の色を用いて未彩色の閉領域を自動彩色することも容易となる。なお、一括して行われるべき処理は、彩色に限らず、移動、変形、文字や図形の付加等の処理であってもよい。
【００７４】
また、本実施形態によれば、各閉領域内の各点の座標の成分を積和演算することで得られる特徴量、又は基準点に対する閉領域内の各点の距離の分布から得られる特徴量に基づいて画像間で閉領域どうしを対応付けるため、複数の画像が色の濃淡情報のない線画等あっても、好適な対応付けができる。また、本実施形態によれば、閉領域全体の形状を考慮した特徴量に基づいて、より好適な閉領域どうしの対応付けができる。また、本実施形態によれば、座標軸に平行ではない方向の凹凸の変化等、複雑な閉領域の形状の特徴を特徴量に反映できる可能性がある。
【００７５】
また、本実施形態によれば、境界線をいくつかに分割した場合の各部の形状のみに基づいて特徴量を算出することと比較し、より閉領域の全体形状を反映した特徴量に基づき、
閉領域どうしを対応付けることができる。例えば、境界線について凹凸の変化が大きい場合であっても、好適な対応付けができる。また、本実施形態によれば、各フレームに複数の剛体を設定し、設定した剛体の回転や平行移動等の変形量によって、各フレーム間の閉領域（剛体）を対応付ける場合と比べ、フレーム間で境界線が複雑な変化をしている閉領域どうしも対応付きやすくなる。
【００７６】
また、本実施形態によれば、コストの総和に基づいて、第１の画像（フレーム）が有する各閉領域を、第２の画像（フレーム）が有する１つ以下の閉領域と対応付けられるため、単純に画像間の２つの閉領域の相違に基づいて、閉領域どうしを対応付ける場合と比較し、画像間全体として精度良く、各閉領域どうしを対応付けることができる。
【００７７】
≪実施形態２≫
上述の実施形態１では、特徴量抽出部２１が、閉領域内の各点の座標の成分を積和演算することで得られる特徴量として、閉領域の慣性主軸の角度等を抽出した。以下に説明する実施形態２では、特徴量抽出部２１が、基準点に対する閉領域内の各点の距離の分布から得られる特徴量として、閉領域の境界線上を動く動点の始点からの道のりを変数とする、当該動点の基準点からの距離の関数を求め、求めた当該関数に対してフーリエ変換をした結果から、所定よりも低周波数の成分を抽出する。なお、本実施形態に係るプログラムが実行される情報処理装置１の構成、情報処理装置１の機能である閉領域対応付け部２３、及び処理の流れは、実施形態１と同様である。
【００７８】
本実施形態においては、基準点として、閉領域の重心が採用される。また、距離としては、ユークリッド距離が採用される。また、動点の始点としては、境界線上の点のうち、重心からｘ軸方向に位置し、かつ最も重心に近い点が採用される。また、動点は、始点から反時計回り動き、境界線上を１周する。
【００７９】
図１１は、閉領域に係る動点の例を示す図である。図１１には、閉領域R１０１に対す
る動点Ｍ１０１が示されている。図１１では、点Ｐ１００が始点である。まず、特徴量抽出部２１は、始点Ｐ１００からの道のりを変数とする、動点Ｍ１０１と重心Ｃ１０１との距離の関数を求める。
【００８０】
図１２は、動点と重心との距離の関数の例を示すグラフである。図１２には、横軸を始点からの動点までの道のりl、縦軸を重心と動点との距離とした、関数ｃ（ｌ）のグラフ
曲線が示されている。このグラフは、図１１の閉領域Ｒ１０１の例と対応している。
【００８１】
次に、特徴量抽出部２１は、関数ｃ（ｌ）を所定より低い次数（例えば１６次）までフーリエ級数展開し、フーリエ記述子で記述した各項の係数を要素とした係数ベクトルを特徴量として抽出する。換言すると、所定よりも低周波数の成分を抽出したことになる。ここで、本実施形態における第ｎ項のフーリエ記述子の係数ｆnは、次数Ｎ、始点からの動
点までの道のりl、境界線の長さをＬ、重心と動点との距離を示す関数ｃ（ｌ）、及び虚
数単位ｉを用いて、数式１２で定義される。
【数１２】
2014106713.tif 000014
【００８２】
本実施形態において、コスト算出部２２は、特徴量である、複数の係数ｆnを要素とす
る係数ベクトルに基づいて、２つの閉領域間の相違の程度を示すコストを算出する。本実
施形態において、コスト算出部２２は、２つの閉領域の係数ベクトルのユークリッド距離をコストとして算出する。なお、コストの算出方法は、例えば、係数の次数によって加重されて算出される等、その他の方法が採用されてもよい。また、コスト算出部２２は、係数ベクトルから算出したコストと、実施形態１で説明した隣接領域重心位置の相違の程度を示すａijneighborとの加重和を算出し、算出した加重和をコストとして採用してもよい。
【００８３】
本実施形態によれば、係数ベクトルで閉領域の境界線を近似でき、次数を増やすほど高精度に境界線を近似する特徴量を抽出することが可能になる。
【００８４】
≪実施形態３≫
実施形態３では、特徴量抽出部２１は、基準点に対する閉領域内の各点の距離の分布から得られる特徴量として、閉領域の境界線上の複数の点を所定の基準で選択し、選択した各点と基準点との距離を成分とするベクトルを抽出する。なお、本実施形態に係るプログラムが実行される情報処理装置１の構成、及び情報処理装置１の機能である閉領域対応付け部２３、及び処理の流れは、実施形態１と同様である。
【００８５】
本実施形態においては、基準点として、閉領域の重心が採用される。また、本実施形態に係るプログラムは、実施形態２と同様に、閉領域に対して始点を定め、始点からの境界線に沿った道のりを取り扱う。まず、特徴量抽出部２１は、境界線の長さをＬとしたときに、境界線上の点であって、始点からの道のりが０、Ｌ／１６、２Ｌ／１６、３Ｌ／１６、…、１５Ｌ／１６となる１６点を選択する（境界線上の複数の点を所定の基準で選択することに相当する）。換言すると、特徴量抽出部２１は、境界線を１６等分する点を選択することになる。次に、特徴量抽出部２１は、選択した各点と重心との距離を成分とするベクトルを、閉領域の特徴量として抽出する。
【００８６】
図１３は、選択した各点と重心との距離を示すイメージ図である。図１３には、図１１の閉領域Ｒ１０１の例に対応する選択した各点と重心との距離のイメージが示されている。図１３において、横軸は点からの動点までの道のりlを示し、縦軸は選択した各点と重
心との距離を示す。図１３において、点Ｌ０１からＬ１６までは、それぞれ、始点からの道のりが０、Ｌ／１６、２Ｌ／１６、３Ｌ／１６、・・・・、１５Ｌ／１６となる、各点の道のりｌと重心との距離の関係を示す点である。特徴量抽出部２１は、特徴量として、点Ｌ０１からＬ１６までの縦座標が示す、重心との距離を要素とするベクトルを抽出する。
【００８７】
なお、本実施形態において、特徴量抽出部２１は、１６点を選択したが、より多くの点を選択すること採用してもよいし、より少ない点を選択することを採用してもよい。
【００８８】
本実施形態において、コスト算出部２２は、実施形態２と同様に、特徴量として抽出されたベクトルのユークリッド距離をコストとして算出する。
【００８９】
≪実施形態４≫
実施形態４では、特徴量抽出部２１は、基準点に対する閉領域内の各点の距離の分布から得られる特徴量として、基準点を原点とした閉領域内の各点の極座標における動径と偏角とを変量とする、２変量のヒストグラムを抽出する。なお、本実施形態に係るプログラムが実行される情報処理装置１の構成、及び情報処理装置１の機能である閉領域対応付け部２３、及び処理の流れは、実施形態１と同様である。
【００９０】
本実施形態において、基準点として閉領域の重心が採用される。また、２変量のヒストグラムとしては、Ｓｈａｐｅ  Ｃｏｎｔｅｘｔが採用される。コスト算出部２２は、カイ
二乗を用いて、特徴量であるヒストグラムの類似度を、２つの閉領域間の相違の程度を示すコストを算出する。
【００９１】
≪その他の実施形態≫
【００９２】
また、その他の実施形態として、各フレームの線画をベクタ画像として扱ってもよい。この際、特徴量抽出部２１は、閉領域iの面積をＡ、閉領域i内の点をｘとして、重心ｔi
及び共分散行列Ｃiを数式１３によって算出してもよい。
【数１３】
2014106713.tif 000015
そして、特徴量抽出部２１は、この共分散行列Ｃiの固有値及び固有ベクトルを算出し、
固有ベクトルから慣性主軸の角度を、閉領域内の各点の座標の成分を積和演算することで得られる特徴量として、抽出してもよい。また、この実施形態では、特徴量抽出部２１は、共分散行列Ｃiの固有ベクトルから慣性主軸の角度を求めたが、特徴量抽出部２１は、
閉領域i内の点をｘのｘ成分、ｙ成分をｘx、ｙy、ｔiのｘ成分、ｙ成分をｔix、ｔiyとして、数式１４により、慣性主軸の角度θを抽出してもよい。
【数１４】
2014106713.tif 000016
【００９３】
このようにすることで、ベクタ画像について、フレーム間の各閉領域どうしを好適に対応付けることができる。また、各フレームの線画は、ベクタ画像をラスタ画像に変換して取り扱ってもよい。
【符号の説明】
【００９４】
１  情報処理装置
２  スキャナ
３  線画
２１  特徴量抽出部
２２  コスト算出部
２３  閉領域対応付け部
【図１】
2014106713.tif 000017
【図２】
2014106713.tif 000018
【図３】
2014106713.tif 000019
【図４】
2014106713.tif 000020
【図５】
2014106713.tif 000021
【図６】
2014106713.tif 000022
【図７】
2014106713.tif 000023
【図８】
2014106713.tif 000024
【図９】
2014106713.tif 000025
【図１０】
2014106713.tif 000026
【図１１】
2014106713.tif 000027
【図１２】
2014106713.tif 000028
【図１３】
2014106713.tif 000029