(57)【要約】      （修正有）【課題】二次元アニメーションの作成をよりスムーズに行う方法を提供する。【解決手段】特徴量を持った複数の画素からなる一方の画像に含まれる複数の閉領域と、他方の画像に含まれる複数の閉領域とを比較して、一方の画像の第１の閉領域を選定するステップと、前記第１の閉領域に含まれる複数の画素の各々が持つ特徴量と、前記他方の画像に含まれる複数の画素の各々が持つ特徴量に基づく、前記第１の閉領域と、前記他方の画像に含まれる複数の閉領域との近似の度合いによって、前記他方の画像を探索するステップと、前記一方の画像の第３の閉領域に、前記他方の画像の第４の閉領域が対応していることが既知であって、前記第１の閉領域が前記第３の閉領域と隣接している場合に、前記第４の閉領域に隣接している複数の閉領域のうち、前記近似の度合いが最も近似している１つの閉領域を、前記第２の閉領域に特定するステップと、を有する。【選択図】なし【特許請求の範囲】
【請求項１】
一方の画像に含まれる複数の閉領域と、他方の画像に含まれる複数の閉領域とを、比較することによって、一方の画像の第１の閉領域に対応する、第２の閉領域を、他方の画像からコンピュータが特定する方法であって、前記一方の画像及び前記他方の画像の各々は、複数の画素で構成されており、前記複数の画素の各々は、特徴量を持ち、当該方法は、
前記第１の閉領域を選定するステップと、
前記第１の閉領域に含まれる複数の画素の各々が持つ特徴量と、前記他方の画像に含まれる複数の画素の各々が持つ特徴量とから、前記第１の閉領域と、前記他方の画像に含まれる複数の閉領域との近似の度合いを求めることで、前記他方の画像を探索するステップと、
前記一方の画像の第３の閉領域に、前記他方の画像の第４の閉領域が対応していることが既知であって、前記第１の閉領域が前記第３の閉領域と隣接している場合に、前記他方の画像に含まれる複数の閉領域であって、前記第４の閉領域に隣接する複数の閉領域のうち、前記近似の度合いが最も近似していることを示す１つの閉領域を、前記第２の閉領域に特定するステップと、
を有する方法。
【請求項２】
前記選定するステップは、
前記第３の閉領域に接している閉領域が複数存在する場合、前記複数の接している閉領域のうち、前記第３の閉領域に接している長さがより長い閉領域であって、前記他方の画像において、対応する閉領域が特定されていない閉領域を、前記第１の閉領域に特定するステップ、
を含む請求項１記載の方法。
【請求項３】
前記選定するステップは、
前記一方の画像に存在する第５の閉領域であって、前記他方の画像に含まれる閉領域のとの対応関係が特定されている第５の閉領域に対して前記第１の閉領域が隣接する長さが、前記第３の閉領域に対して前記第１の閉領域が隣接する長さよりも長い第５の閉領域に隣接する第６の閉領域であって、前記第５の閉領域に隣接する長さが、前記第５の閉領域に対して前記第１の閉領域が隣接する長さよりも長い、前記他方の画像に含まれる閉領域のとの対応関係が特定されていない第６の閉領域が存在する場合、前記第６の閉領域を、前記第１の閉領域に特定し直すステップ、
を更に含む請求項２記載の方法。
【請求項４】
前記近似の度合いを求めるステップは、
対応が既知である前記一方の画像の閉領域と前記他方の画像の閉領域の移動ベクトルを用いて、前記第１の閉領域に対応する、前記他方の画像における閉領域の前記探索を開始するための近似度を求める移動ベクトルの初期の値を決定するステップ、
を含む請求項１ないし３のうちいずれか１項記載の方法。
【請求項５】
前記第１の閉領域が、前記第１の閉領域の境界線に接しない第１の複数の閉領域を持つ場合であって、前記第２の閉領域が、前記第２の閉領域に接しない第２の複数の閉領域を持ち、前記第１の複数の閉領域の数と前記第２の閉領域の数が等しい場合、主成分分析を用いることで、前記第１の複数の閉領域の主成分方向と、前記第２の複数の閉領域の主成分方向を重ねることで得られる相対位置の関係に基づき、前記第１の複数の閉領域の各々と、前記第２の複数の閉領域の各々との対応付けを行うステップ、
を更に有する請求項１ないし４のうちいずれか１項に記載の方法。
【請求項６】
請求項１ないし５のうちいずれか１項に記載の方法を、コンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の閉領域を含む少なくとも２つの画像内に存在する領域を対応づける方法、及びプログラムに関する。
【背景技術】
【０００２】
複数の二次元画像を作成し、複数の二次元画像の各々を時系列的に順次表示することによって、二次元アニメーションを作成することが一般に行われている。二次元アニメーションは、手書きなどで作成された静止画像を時間軸上の各フレームに対応づけて再生することで、動画を構成する表現技法である。
【０００３】
古くは、手書きの画像を複数枚作成し、複数枚の画像を順次映画フィルムに撮影し、映画フィルムを投影することによって、テレビや映画などの漫画（二次元アニメーション）を制作することが行われてきた。複数の画像は、それぞれ、キャラクタなどの動きを少しずつ変えた画像となっているため、複数の画像を連続的に表示することによって、動きのあるキャラクタの動画が生成できる。また、より原始的な技法として、複数の紙に描かれた複数毎の画像を、指によってパラパラとめくることによって、動きのあるキャラクタを表現するパラパラ漫画などが存在していた。
【０００４】
一般的な、二次元アニメーションは、以下の工程で作成されることが多い。
・行程（１）原画の作成：一連の動画の画像のうちの所定のタイミングに散在する要のフレームであるキーフレームに含まれる画像を原画と呼ぶ。主にデザイナーが原画を作成する。
・行程（２）中割り画像の作成：時間軸上、あるキーフレームと次のキーフレームとの間に位置し、前後の原画をなめらかに補間した画像（この画像を「中割り画像」という）を作成する。
・行程（３）彩色：原画と中割り画像の中に存在する複数の閉領域の着色を行う。
・行程（４）撮影：原画と背景との合成、及び中割り画像と背景との合成を行い各々のフレームを作成する。
【０００５】
上記行程（１）の原画については、デザイナーが作成するのが基本である。原画は、動きのあるキャラクタの特徴的な動作部分をデザイナーが手書き又は、コンピュータグラフィクスのソフトウエア等を用いて作成する。通常、デザイナーは、動画の全てのフレームを作成することはなく、キーフレームのための原画を描く。幾つかのフレームを隔てて原画が描かれる。
【０００６】
上記行程（２）は、中割り画像の作成である。１つの原画と、時間的にその次に位置する原画との間は、デザイナー以外の者が中割り画像を作成する場合が多い。中割り画像は、時間軸上で隣り合う原画の間に位置する空白のフレームに用いられる画像である。中割り画像を作成する目的は、なめらかな動画を作成するために、時間軸上で隣り合う原画を含むキーフレームを補間した画像を作成することで、空白のフレームを埋めることである。
【０００７】
したがって、中割り画像は、動画全体がスムーズなものとなるように描かれる。中割り画像は、手書きで作成されていることが多いが、原画に比べて、作成する枚数が多くなるため、多くのリソースが必要となる。また、自動的に中割り画像を作成することも試みられているが、自然な動画を作成する上で、自動的な中割り画像の作成には困難を伴う。
【０００８】
上記行程（３）は、彩色である。原画及び中割り画像は、共に、線画で描かれていることが多いため、線画によって形成されたそれぞれの閉領域を、適切な色で着色する作業（彩色）が行われる。彩色についても、ディジタル化された処理が普及している。
【０００９】
上記工程（４）は、撮影である。古くは、各フレームが銀塩フィルムに撮影されていた。撮影工程（４）は、ディジタル化された処理が普及しており、ディジタルの動画が生成される。
【００１０】
上記工程（２）及び工程（３）については、手作業を必要とする部分が多く、繁雑な作業をオペレータが行う割合が多い。これは、原画に存在する複数のオブジェクトの画像が重なり合っていたり、変形していたりするためである。すなわち、２つの原画における対応する閉領域が変形し、又は対応する交点（閉領域の境界線が交わる交点など）が移動してしまうため、自動的な対応付けが困難となることなどに起因している。
【００１１】
２つの画像に存在する対応する交点を発見する技術としては以下の技術が存在する。
【００１２】
２枚のキーフレームとなるビットマップイメージのそれぞれに、双方のビットマップイメージの対応し合う位置関係を示すためのコントロールポイントを指定し、その対応するコントロールポイント間を結んだ直線上に決定された内分点にコントロールポイントを変更することにより補間フレームを生成する技術が存在する（例えば、特許文献１）。
【００１３】
また、効率よくマッチング処理を行うため、マッチング部が、動的計画法を用いて、第１形状データの輪郭点とマッチングする第２形状データの輪郭点を求める技術が存在する（例えば、特許文献２）。
２つの画像に存在する対応する閉領域を発見する技術としては以下の技術が存在する。
【００１４】
例えば、頭や手などの閉領域をチェーンとしてリスト化して記憶しておき、閉領域の特徴をトラッキングする技術が存在する（例えば、非特許文献１参照）。
【００１５】
また、輪郭のマッチングを行い、似ている画像閉領域を対応づける技術が存在する（例えば、非特許文献２参照）。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開平１１−７５３９号公報
【特許文献２】特開２０１５−１１５０４７号公報
【非特許文献】
【００１７】
【非特許文献１】P.  Garcia  Trigo，H.  Johan，T.  Imagire，and  T.  Nishita．  Interactive  Region  Matching  for  2D  Animation  Coloring  Based  on  Feature's  Variation．  IEICE  ransactions(E92-D)，No.6，pp.1289-1295  (2009)．
【非特許文献２】J.  S.  Madeira，A.  Stork，and  M.  H.  Gross．  An  approach  to  computer-supported  cartooning．The  Visual  Computer，Vol.12，No.1，pp.1-17  (1996)．
【発明の概要】
【発明が解決しようとする課題】
【００１８】
上述のように、中割り画像の作成工程（２）では、中割り画像の作成に多くのリソースを必要とする。また、彩色工程（３）には、手作業を伴う彩色の行程が存在する。この彩色の工程では、原画及び中割り画像の各々に対して、対応する閉領域に同じ彩色を施す必要がある。したがって、彩色を行う場合には、複数の原画及び複数の中割り画像の各々のフレームに存在する対応する閉領域を特定する作業が必要である。通常、対応する閉領域の判断は、オペレータによる目視の作業が必要とされる。
【００１９】
以下に開示する実施形態は、特に中割り画像の作成工程及び彩色行程等における、オペレータの作業の軽減を図ることにより、二次元アニメーションの作成をよりスムーズに行うことができるようにすることを目的とする。
【課題を解決するための手段】
【００２０】
一実施形態は、一方の画像に含まれる複数の閉領域と、他方の画像に含まれる複数の閉領域とを、比較することによって、一方の画像の第１の閉領域に対応する、第２の閉領域を、他方の画像からコンピュータが特定する方法であって、前記一方の画像及び前記他方の画像の各々は、複数の画素で構成されており、前記複数の画素の各々は、特徴量を持ち、当該方法は、前記第１の閉領域を選定するステップと、前記第１の閉領域に含まれる複数の画素の各々が持つ特徴量と、前記他方の画像に含まれる複数の画素の各々が持つ特徴量とから、前記第１の閉領域と、前記他方の画像に含まれる複数の閉領域との近似の度合いを求めることで、前記他方の画像を探索するステップと、前記一方の画像の第３の閉領域に、前記他方の画像の第４の閉領域が対応していることが既知であって、前記第１の閉領域が前記第３の閉領域と隣接している場合に、前記他方の画像に含まれる複数の閉領域であって、前記第４の閉領域に隣接する複数の閉領域のうち、前記近似の度合いが最も近似していることを示す１つの閉領域を、前記第２の閉領域に特定するステップと、を有する方法を提供する。
【発明の効果】
【００２１】
二次元アニメーションの作成工程における人的作業負担を軽減させることにより、二次元アニメーションの作成をよりスムーズに行うことができる。
【図面の簡単な説明】
【００２２】
【図１】原画及び中割り画像を含む複数のフレームにより二次元アニメーションを構成する例を示す図である。
【図２】原画を構成する各画素の特徴抽出の例を示す図である。
【図３】原画を構成する各閉領域を管理する表の例を示す図である。
【図４】複数の閉領域を含む２つの画像のそれぞれの閉領域を対応づける手法の例を示す図である。
【図５】複数の閉領域を含む２つの画像のそれぞれの閉領域の対応づけの結果を示す図である。
【図６】領域の対応付けの例を示すフローチャートである。
【図７】複数の閉領域を含む２つの画像のそれぞれに存在する交点の対応付けの例を示す図である。
【図８】複数の閉領域を含む２つの画像のそれぞれの交点の対応づけの結果を示す図である。
【図９】複数の閉領域を含む２つの画像のそれぞれに存在する交点の対応付けの際に発生する第１の課題の例を示す図である。
【図１０】複数の閉領域を含む画像に存在する交点及び境界線を修正する処理の例を示す図である。
【図１１】複数の閉領域を含む画像に存在する交点及び境界線を修正する処理の結果に基づいて、交点の対応付けの例を示す図である。
【図１２】２つの交点をまとまりとして捉えた場合に、それらの周囲に存在する複数の閉領域のパターンが同一である場合を発見するフローチャートである。
【図１３】交点の対応付けを行う処理を示すフローチャートである。
【図１４】中割り画像を自動的に作成する第１の例を示す図である。
【図１５】複数の中割り画像を生成する例を示す図である。
【図１６】孤立した閉路上に交点が無い場合に交点を付与する例を示す図である。
【図１７】２つの原画の片方が孤立した閉路を持つ場合の交点の処理の例を示す図である。
【図１８】原画をレイヤーに分ける処理を行う例、閉領域の一部が対応している場合の処理の例を示す図である。
【図１９】本実施形態のハードウエア構成の例を示す図である。
【図２０】原画１から対応付けする閉領域を選択する手順の例を示す図である。
【図２１】対応付けにおける初期の移動ベクトルを設定する例を示す図である。
【図２２】注目する未対応の閉領域を選択する手順の例を示す図である。
【図２３】対応先領域を求める一例を示す図である。
【図２４】主成分分析を説明するための、一般的な図である。
【図２５】主成分分析を用いて、閉領域に包含された複数の閉領域の対応付けの例を示す図である。
【図２６】対応する閉領域の各々に包含される複数の閉領域の各々の対応関係を見いだす手順の例を以下に示す図である。
【発明を実施するための形態】
【００２３】
図１は、原画及び中割り画像を含む複数のフレームにより二次元アニメーションを構成する例を示す図である。
【００２４】
図１には、時間軸ｔが示されている。デザイナーが、原画１と原画２とを描く。時刻ｔ１からｔ２までの間、原画１を含むフレームが表示される。そして、時刻ｔ３から原画２を含むフレームが表示される。この場合、時刻ｔ２からｔ３のフレームを空白の画像とすることはできないため、中割り画像Ｎを作成して、中割り画像Ｎを含むフレームを時刻ｔ２からｔ３までの間表示することで、動画がスムーズに表示されるようにすることができる。図１の例では、中割り画像Ｎを１つ追加する場合を例示しているが、実際には、原画１と原画２との間に、２つ以上の中割り画像を作成する場合もある。図１は、説明を簡略化するために、１つの中割り画像Ｎが図示されている。
【００２５】
原画１と原画２との中間の動きを表現する画像を生成することができれば、中割り画像Ｎを自動的に描くことができる。中割り画像Ｎを描くためには、例えば原画１と原画２における主要な交点の対応関係がわかっていれば、例えば、対応する交点どうしの位置を補間した交点（例えば中点）を求めることによって、中割り画像において対応する交点を求めてもよい。例えば、原画１の交点１１と原画２の交点２１は、対応する交点であることがわかる。したがって、例えば、交点１１の座標と、交点２１の座標を補間した交点（例えば中点）の座標）（例えばフレームの画素位置）を求めることによって、中割り画像Ｎの交点Ｎ１の座標を求めることができる。
【００２６】
原画１と原画２における各交点の対応関係は以下のとおりである。すなわち、原画１における交点１１、交点１２、交点１３、交点１４は、それぞれ原画２における交点２１、交点２２、交点２３、交点２４に対応している。原画１及び原画２におけるこれらの複数の交点の対応付けを発見することができれば、中割り画像Ｎの複数の交点Ｎ１、交点Ｎ２、交点Ｎ３、交点Ｎ４の座標は、例えば、原画１と原画２との対応する交点を補間することで、求めることができる。
【００２７】
上記の処理では、原画１の各交点と原画２の各交点の対応関係が既知であることを前提として説明した。しかしながら、現実には、原画１の各交点と原画２の各交点の対応関係をオペレータの指示に頼ることは、オペレータに多くの労力を強いることとなる。したがって、原画１の各交点と原画２の各交点の対応関係を自動的に推定することが求められる。
【００２８】
図７に移る。図７は、原画１の交点１３と原画２の交点２３が対応関係にあることを推定するために、複数の閉領域を含む２つの画像のそれぞれに存在する交点の対応付けの例を示す図である。
【００２９】
図７（Ａ）の交点１３の周辺を拡大した図が図７（Ｃ）である。また、図７（Ｂ）の交点２３の周辺を拡大した図が図７（Ｄ）である。
【００３０】
図７（Ｃ）に示されるように、交点１３は、背景Ｙと、閉領域１Ｂと、閉領域１Ｃとで作られる境界線上の交点であることがわかる。図７（Ｄ）に示されるように、交点２３は、背景Ｙと、閉領域２Ｂと、閉領域２Ｃとで作られる境界線上の交点であることがわかる。
【００３１】
ここで、閉領域２Ｂが閉領域１Ｂと対応関係にあること、及び閉領域１Ｃと閉領域２Ｃとが対応関係にあることが既知であると仮定する。なお、背景Ｙは、原画１と原画２とで同種の背景であり対応関係にあることが既知であると仮定する。図７（Ｃ）における交点１３の周囲に存在する複数の閉領域は、左回りに閉領域１Ｂ、背景Ｙ、閉領域１Ｃの順に存在しており、同様に図７（Ｄ）における交点２３の周囲に存在する複数の閉領域は、左回りに閉領域１Ｂに対応する閉領域２Ｂ、背景Ｙ、閉領域１Ｃに対応する閉領域２Ｃの順に存在している。このことから、交点１３と交点２３は、対応関係にあることを自動的に推定することが可能である。
【００３２】
上記の推定においては、原画１の交点１３の周りに存在する複数の閉領域と、原画２の周りに存在する複数の閉領域同士の対応関係が既知であることを前提とした。しかしながら、原画１の複数の閉領域と原画２の複数の閉領域のそれぞれの対応関係を、オペレータの指示に頼ることは、オペレータに多くの労力を強いることとなる。したがって、原画１の各交点と原画２の各交点との対応関係を、可能な限り自動的に推定することが求められる。
【００３３】
図１に戻ると、上記のことは、原画１の閉領域１Ａ、閉領域１Ｂ及び閉領域１Ｃが、それぞれ原画２の閉領域２Ａ、閉領域２Ｂ及び閉領域２Ｃと対応することを、自動的に推定することが求められる。
【００３４】
以上のことから、時間的に連続する２つの原画１及び原画２の時間軸上の中間に位置する中割り画像Ｎを自動的に生成するためには、上記の手順と逆の推定の処理を以下のとおり実行することが求められる。
（ａ）原画１と原画２とにおいて、それぞれに存在する閉領域の対応づけを推定すること。
（ｂ）閉領域の対応付けの情報を用いて、原画１と原画２とにおいて、それぞれに存在する閉領域を分ける境界線の交点の対応づけを推定すること。
（ｃ）対応づけられた交点を補間する交点の座標を求めること。
（ｄ）原画１と原画２の対応する閉領域の形状及び補間された交点の座標を用いて、中割り画像を生成すること。
【００３５】
なお、上記（ａ）の行程において、閉領域の対応付けが行われるため、例えば原画１の彩色の指定を行えば、略自動的に原画２における対応する閉領域の彩色が行える。更に、上記工程（ｄ）において生成された中割り画像においても、原画における閉領域と対応する閉領域がわかるため、中割り画像の閉領域の彩色も略自動で行うことができることとなる。
【００３６】
したがって、上述の従来技術の説明では、中割り画像の作成の工程の後に彩色の工程が位置していたが、本実施形態では、中割り画像の作成工程と、彩色の工程が逆の順序になってもよいことがわかる。
【００３７】
以下、順に、詳細な実施形態を説明する。
【００３８】
＜１＞実施形態１：閉領域の対応付け
＜１−１＞  用語の定義
実施形態１では、２つの原画に存在する複数の閉領域の対応付けを自動的に行うための処理の例を示す。なお、以下の実施形態１は、処理の一例であって、この例に限られるものではない。
【００３９】
図２は、原画を構成する各画素の特徴抽出の例を示す図である。
【００４０】
ここで、図２（Ａ）を用いて、以下の定義を行う。
【００４１】
「閉領域」：画像において、線で閉じられた領域を「閉領域」と呼ぶ。たとえば、図２（Ａ）において、閉領域１Ａ、閉領域１Ｃ及び閉領域１Ｂは、それぞれ線で閉じられた「閉領域」である。原画の背景は、閉領域ではない。また、直線及び点も画像も閉領域ではない。
【００４２】
「境界線」：閉領域を囲む線を境界線という。境界線を隔てて閉領域と閉領域又は背景とが隣接することになる。
【００４３】
「隣接」：閉領域Ａと閉領域Ｂとが、境界線Ｘで接している場合、閉領域Ａと閉領域Ｂとは、境界線Ｘで隣接しているという。
【００４４】
「交点」：境界線が交わっている点、あるいは境界線の端点（端の点）を交点と呼ぶ。
【００４５】
「画素」：画像に存在する二次元平面に等間隔にメッシュを定義して、メッシュの各交点の座標位置に存在する画像の構成要素を画素と呼ぶ。画素は、ディジタル画像を構成する各画素に対応させてもよい。
【００４６】
「方位」：図２（Ａ）において、画素Ｐ１から例えば上下左右の４つの方向を「方位」という。そして上下左右のそれぞれの方位に伸びる半直線Ｕ、Ｄ、Ｌ、Ｒを定義する。半直線Ｕ、Ｄ、Ｌ、Ｒは、画素Ｐ１からそれぞれ上、下、左、右に伸びる半直線である。なお、図２（Ａ）の例では、上下左右の４つの方位にそれぞれ半直線を定義したが、方位の数は、４つに限られるものではない。
【００４７】
「交差回数」：図２（Ａ）において、例えば、画素Ｐ１から上の方位に伸びる半直線Ｕが、原画１を構成する閉領域１Ａとの境界線において、Ｕ１１で交差している。この場合、画素Ｐ１の上方位の交差回数は１であると定義される。同様に画素Ｐ１の左の方位に伸びる半直線Ｌが、原画１を構成する閉領域１Ａ、１Ｃ、１Ｂとの境界線とＬ１１、Ｌ１２、Ｌ１３で交差している。この場合、画素Ｐ１の左方位の交差回数は３であると定義される。同様に画素Ｐ１の下の方位に伸びる半直線Ｄが、原画１を構成する閉領域Ａ１との境界線と、Ｄ１１で交差している。この場合、画素Ｐ１の下方位の交差回数は１であると定義される。同様に画素Ｐ１の右の方位に伸びる半直線Ｒが、原画１を構成する閉領域１Ａとの境界線と、Ｒ１１で交差している。この場合、画素Ｐ１の右方位の交差回数は１であると定義される。
【００４８】
「境界線までの距離」：図２（Ａ）において、例えば、画素Ｐ１から、画素Ｐ１を含む閉領域と、初めて交差するまでの距離を「境界線までの距離」と定義する。図２（Ａ）において、画素Ｐ１の上方位の境界線までの距離は、α１である。境界線までの距離の単位は、たとえば、画素数であってもよい。
【００４９】
たとえば、画素が、ある閉領域に属している場合には、その画素は、いずれの方位においても、必ずその閉領域の境界線と交差することとなるため、交差回数は１以上となる。画素が、背景に属している場合には、交差回数がゼロの場合があり得る。
【００５０】
＜１−２＞  原画の構成要素
図１及び図１８などに示す原画は、多くの場合線画であり、例えば以下のような要素で構成されている。
（ａ）閉領域（境界線で閉じた領域）
（ｂ）閉領域から分岐する線分（分岐線分）
（ｃ）閉領域に包含され孤立する線分（孤立線分）
２つの原画の間に存在する分岐線分と孤立線分は、閉領域の境界線との相対座標を比較することにより、対応付けが可能である。したがって、まず、２つの原画の間の閉領域の対応付けを行うことが望ましい。実施形態１では、閉領域の対応付けの例を示す。
【００５１】
＜１−３＞  彩色と中割り画像の生成の順序
上述の、従来技術の例においては、中割り画像を作成した後に、原画と中割り画像の彩色が行われる手順を示した。しかしながら、本実施形態１では、原画の各閉領域の対応付けをまず行うため、この段階で、原画の対応する閉領域に彩色を施すことが可能である。まず、原画間で閉領域の対応付けを行う。そして、複数の原画で、対応する閉領域には、彩色において同じ色が塗られることになる。このようにすれば、彩色を原画毎に行う手間を省くことができる。
【００５２】
加えて、２つの原画の間に閉領域の対応付けが既になされていれば、時間軸上で２つの原画の間に位置する中割り画像をその後生成した場合にも、その中割り画像に含まれる閉領域と２つの原画の閉領域との対応付けが容易に行える。
【００５３】
したがって、まず原画における閉領域の対応付けを行った後、彩色を行い、その後に生成された中割り画像に含まれる閉領域に、略自動的彩色を行うことができる。
【００５４】
＜１−４ａ＞  原画の画素の特徴ベクトルの定義
本実施形態では、原画に存在する画素Ｐの特徴Ｖ（Ｐ）を、８次元ベクトルで以下のように定義する。
【００５５】
Ｖ（Ｐ）＝（ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ６，ｃ７）      （式１）
ここで、ｃ０乃至ｃ７を、以下のように定義する。なお、βは、定数である。
画素Ｐから上下左右の境界線までの距離を、それぞれαｕ、αｄ、αｌ、αｒとすると、
ｃ０＝１／（αｕ＋β）  ただし、上方位の交差回数が１である場合。その他の場合ｃ０＝０
ｃ１＝１／（αｒ＋β）  ただし、右方位の交差回数が１である場合。その他の場合ｃ１＝０
ｃ２＝１／（αｄ＋β）  ただし、下方位の交差回数が１である場合。その他の場合ｃ２＝０
ｃ３＝１／（αｌ＋β）  ただし、左方位の交差回数が１である場合。その他の場合ｃ３＝０
ｃ４＝１／（αｕ＋β）  ただし、上下左右の４つの方位の交差回数がいずれも２以上であり、かつ上方位の交差回数が上下左右の４つの方位の交差回数のうち最小である場合。その他の場合ｃ４＝０
ｃ５＝１／（αｒ＋β）  ただし、上下左右の４つの方位の交差回数がいずれも２以上であり、かつ右方位の交差回数が上下左右の４つの方位の交差回数のうち最小である場合。その他の場合ｃ５＝０
ｃ６＝１／（αｄ＋β）  ただし、上下左右の４つの方位の交差回数がいずれも２以上であり、かつ下方位の交差回数が上下左右の４つの方位の交差回数のうち最小である場合。その他の場合ｃ６＝０
ｃ７＝１／（αｌ＋β）  ただし、上下左右の４つの方位の交差回数がいずれも２以上であり、かつ左方位の交差回数が上下左右の４つの方位の交差回数のうち最小である場合。その他の場合ｃ７＝０
なお、ｃ０，ｃ１，ｃ２，ｃ３については、交差回数が１の方位が複数ある場合は、交差回数が１の方位に対応する特徴ベクトルの要素に値を持つことになる。また、ｃ４，ｃ５，ｃ６，ｃ７については、交差回数が２以上で最小の値の方位が複数ある場合は、その最小の交差回数の複数の方位に対応する特徴ベクトルの要素に値を持つことになる。
【００５６】
画素Ｐが背景又は境界線に属する画素である場合には、ｃ０＝ｃ１＝ｃ２＝ｃ３＝ｃ４＝ｃ５＝ｃ６＝ｃ７＝０とする。
【００５７】
なお、上述の規則は例示に過ぎず、これに限定されるものではない。特徴ベクトルのその他の要素の決定方法としては、たとえば、以下のような規則（ａ）又は（ｂ）が挙げられる。
【００５８】
（ａ）上記規則においては、同じ交差回数が複数ある場合には、その複数の方位のすべてに、特徴ベクトルの要素を持つように定めた。しかしながらそのようにせずに、上下左右の方位にあらかじめ優先順位を設けておき、同じ交差回数の方位が複数ある場合には、同じ交差回数を持つ方位のうちで、優先順位の一番高い方位における境界線までの距離のみを採用してもよい。そして、特徴ベクトルのその他の要素は、ゼロとしてもよい。
【００５９】
（ｂ）特徴ベクトルのうちｃ０，ｃ１，ｃ２及びｃ３の成分は、交差回数が１となる方位が存在するときに、交差回数が１となる方位のうち、境界線までの距離が一番小さいαを用いた特徴量１／（α＋β）を、境界線までの距離が一番小さいαの方位の要素に持つように定めてもよい。そして、特徴ベクトルのうちｃ４，ｃ５，ｃ６及びｃ７の成分は、交差回数として１となる方位が存在せずかつ全ての方位で交差回数が２以上となるときに、４つの方位のうちで、境界線までの距離が一番小さいαを用いた特徴量１／（α＋β）を、境界線までの距離が一番小さいαの方位の要素に持つようにしてもよい。そして、それ以外の方位の特徴ベクトルの要素はゼロとしてもよい。
【００６０】
上述の例は、いずれもｃ０及びｃ４は上方位の成分を表す。ｃ１及びｃ５は右方位の成分を表す。ｃ２及びｃ６は下方位の成分を表す。ｃ０３及びｃ７は左方位の成分を表す。
【００６１】
背景に存在する画素の特徴ベクトルの成分は、全てが零であるとしてもよい。
【００６２】
なお、上記の特徴ベクトルは、すでに指摘したように一例であって、課題を達成するための特徴ベクトルは他の形式であってもよい。更に、例えば、特徴ベクトルは、上下左右の４つの方位を次元とする４次元ベクトルであってもよい。４つの方位において最も交差回数の少ない方位の境界線までの距離に基づく関数を、対応する方位の次元の要素として、その他の次元の要素の値を零としてもよい。
【００６３】
＜１−４ｂ＞  特徴ベクトルの性質
上記の特徴ベクトルは、以下の性質を持つ。
【００６４】
本実施形態１では、原画は、線で構成された線画であると仮定している。原画が描かれる対象をオブジェクトと呼ぶ。オブジェクトは、複数の線画で描かれており、複数の閉領域を含む。
【００６５】
オブジェクトと背景との境界線は、オブジェクト内に存在する閉領域間の境界線よりも、識別性が高い。これは、背景と接している境界線は、オブジェクトのシルエットを構成する輪郭とも呼べる線であり、オブジェクトの内部に存在する線よりも、オブジェクトの特徴をより強く現している境界線であることが経験則上わかっているためである。
【００６６】
上記の交差回数が１である場合は、その方位に存在する境界線が背景との境にあることを示している。これに対して、交差回数が２以上である方位に存在する境界線は、オブジェクト内に入り込んだ境界線であり、背景とは接していない境界線である。
【００６７】
上記に定義した各画素が持つ特徴ベクトルは、少なくとも１つでも、交差回数が１の方位があれば、その方位における、境界線までの距離を優先して利用する。交差回数が１の方位が複数存在する場合には、その複数の方位のうち一番短い、境界線までの距離を用いて特徴ベクトルの成分を生成する。交差回数が１の方位がなければ、交差回数が２以上の方位のうち、最も値の小さい境界線までの距離を採用する。
【００６８】
このように、交差回数が１である境界線までの距離を優先して用いる理由は、背景と接している境界線を重要視するためである。
【００６９】
そして、採用された境界線までの距離をαとすると、１／（α＋β）を計算し、上記８次元ベクトルの所定のベクトル成分の値とし、その他のベクトル成分の値はゼロとする。ここで、βは、定数である。定数βをαに足す理由は、境界線上でαがゼロとなるため、ベクトル成分の値が無限大になるのを避けるために設定する。また、どの程度の閉領域の大きさを対象とするか、どの程度、境界線の近辺で大きな値の成分を特徴として持たせるかにも依存する。境界線までの距離αが分母に存在するため、ベクトルの成分１／（α＋β）は、閉領域内において境界線に近い画素であればあるほど、大きな値をとること（増加関数）になる。このようにαを分母に置くことによって、閉領域のうち、境界線に近い部分に対して、より大きな特徴量を持たせることができる。このように、境界線に近い部分に対して、より大きな特徴量を持たせることは、境界線の形状をより重視するように特徴を持たせることができる。これは、オブジェクトの閉領域の中央付近よりも、境界線に近い部分にその形状の特徴が現れるため、この特徴ベクトルを用いることにより、後述するコスト関数を用いて、原画同士の閉領域の対応付けを高い確率で推定できるようにするためである。なお、特徴量１／（α＋β）は、一例であって、この特徴量に限定されるものではない。特徴量は、閉領域の内部において、境界線付近で大きな値をとるような関数を選ぶことにより、閉領域の境界線付近を強調する関数であることが望ましい。
【００７０】
＜１−５＞  画素の特徴ベクトルの例
（１）画素Ｐ１の特徴ベクトル（図２（Ａ））
画素Ｐ１の４つの方位の交差回数は以下のとおりである。
【００７１】
上方位において画素Ｐ１は、Ｕ１１で交差しているため、上方位の交差回数は１である。
【００７２】
右方位において画素Ｐ１は、Ｒ１１で交差しているため、右方位の交差回数は１である。
【００７３】
下方位において画素Ｐ１は、Ｄ１１で交差しているため、下方位の交差回数は１である。
【００７４】
左方位において画素Ｐ１は、Ｌ１１、Ｌ１２、Ｌ１３で交差しているため、左方位の交差回数は３である。
【００７５】
そして、画素Ｐ１は、交差回数１回の方位が上方位、右方位、下方位に存在する。上方位の境界からの距離がα１Ｕである。右方位の境界からの距離がα１Ｒである。下方位の境界からの距離がα１Ｄである。したがって、画素Ｐ１の特徴ベクトルＶ（Ｐ１）は、以下のとおりである。
Ｖ（Ｐ１）＝（１／（α１Ｕ＋β），１／（α１Ｒ＋β），１／（α１Ｄ＋β），０，０，０，０，０）
（２）画素Ｐ２の特徴ベクトル（図２（Ｂ））
画素Ｐ２の４つの方位の交差回数は以下のとおりである。
【００７６】
上方位において画素Ｐ２は、Ｕ２１、Ｕ２２で交差しているため、上方位の交差回数は２である。
【００７７】
右方位において画素Ｐ２は、Ｒ２１、Ｒ２２で交差しているため、右方位の交差回数は２である。
【００７８】
下方位において画素Ｐ２は、Ｄ２１、Ｄ２２で交差しているため、下方位の交差回数は２である。
【００７９】
左方位において画素Ｐ２は、Ｌ２１、Ｌ２２で交差しているため、左方位の交差回数は２である。
【００８０】
そして、図２（Ｂ）においては、交差回数が１である方位は存在せず、画素Ｐ２は、交差回数２以上の方位のうち最も小さい交差回数の値は２であり、その方位は、４つの方位全てである。上方位の境界線からの距離がα２Ｕである。右方位の境界線からの距離がα２Ｒである。下方位の境界線からの距離がα２Ｄである。左方位の境界線からの距離がα２Ｌである。したがって、画素Ｐ２の特徴ベクトルＶ（Ｐ２）は、以下のとおりである。
Ｖ（Ｐ２）＝（０，０，０，０，１／（α２Ｕ＋β），１／（α２Ｒ＋β），１／（α２Ｄ＋β），１／（α２Ｌ＋β））
（３）画素Ｐ３の特徴ベクトル（図２（Ｃ））
画素Ｐ３の４つの方位の交差回数は以下のとおりである。
【００８１】
上方位において画素Ｐ３は、Ｕ３１、Ｕ３２で交差しているため、上方位の交差回数は２である。
【００８２】
右方位において画素Ｐ３は、Ｒ３１、Ｒ３２で交差しているため、右方位の交差回数は２である。
【００８３】
下方位において画素Ｐ３は、Ｄ３１で交差しているため、下方位の交差回数は１である。
【００８４】
左方位において画素Ｐ３は、Ｌ３１、Ｌ３２で交差しているため、左方位の交差回数は２である。
【００８５】
そして、図２（Ｃ）においては、交差回数が１である方位が存在するため、画素Ｐ３の特徴を計算する場合には、下方位の境界線からの距離が、交差回数１の方位のα３Ｄを採用する。したがって、画素Ｐ３の特徴ベクトルＶ（Ｐ３）は、以下のとおりである。
Ｖ（Ｐ３）＝（０，０，１／（α３Ｄ＋β），０，０，０，０，０）
＜１−６＞  ２つの原画を構成する閉領域を大きい順に並べた管理表の作成
図１に示す原画１と原画２とに含まれる複数の閉領域を対応づける前処理として、各原画に存在する複数の閉領域を、面積の大きい順に並べた表を作ってもよい。この表を作ることによって、面積の大きい閉領域から対応付けの評価を行うことができる。このような表を作る理由は、面積が大きい閉領域について、対応関係を早期に確定させて、対応候補から除いておく方が、面積の小さい閉領域の対応関係を先に確定してゆくよりも、閉領域の対応関係が見つけやすく、その対応関係の確度も高くなるという経験則があるからである。したがって、対応する可能性の高い順番に対応関係をチェックするようにするために、このような表を作る意味がある。
【００８６】
図３（Ａ）は、図１の原画１の３つの閉領域（閉領域１Ａ、閉領域１Ｂ、閉領域１Ｃ）を、面積の大きい順に並べた管理表である。Ｎｏ．は閉領域の大きい順を示し、閉領域インデックスは、閉領域にラベリングされたインデックス（例えば１Ａ）が付される。インデックスは、閉領域毎にユニークな識別を自動的に付与してもよい。画素数は、それぞれの閉領域に含まれる画素の数を表し、面積に比例した数値となるため、面積を現す数として代用してもよい。なお、画素数は、例えば、閉領域の面積が大きい順にソートする場合に用いてもよい。「対応付け」の欄は、全て零（０）が初期値として記憶されている。後述する閉領域の対応付けが終了した閉領域には、例えば１を記憶させるようにする。そして、１が記憶された閉領域は、対応付けの処理が終了したことを示すため、以後の対応付けの処理の対象から除いてもよい。また、後述するように、対応付けが一部分しか完了していない閉領域は、「対応付け」を１に変更せず、０のままとして、その後の対応付けの処理の対象となるようにしてもよい。この処理の例は後述する。
【００８７】
図３（Ｂ）は、図１の原画２における各閉領域を、面積の大きい順に並べた管理表である。
【００８８】
＜１−７＞  閉領域の対応付け
原画１と原画２とにそれぞれ存在する閉領域の対応を推定する例を以下に示す。
【００８９】
閉領域の対応付けを行う際には、すでに述べたように、経験則として、一方の原画（例えば原画１）の閉領域の面積が大きい閉領域は、他方の原画の対応している可能性の高い閉領域を見つけやすくかつその対応関係の確度も高いといえる。したがって、以下では、まず原画１で一番大きい面積の閉領域から順に取り出し、取り出された閉領域を以下に例示するコスト関数Ｅを用いて近似度を計算する。例えば、コスト関数Ｅが小さいほど近似していると判断し、コスト関数Ｅを最小にする移動ベクトル（最適な移動ベクトル）を求め、更に最適な移動ベクトルを用いて、原画１から取り出された閉領域と最も重なりの大きな原画２の閉領域を見つけて、この組み合わせを、対応する閉領域のペアと推定してもよい。或いは、このようにして見つけた閉領域のペアを表示して、オペレータに確認を促してもよい。この際に、オペレータが、対応付けの推定が誤っていることを入力させるようにして、このペアの対応付けをキャンセルさせてもよい。この場合には、次に重なりの大きな対応する閉領域をみつけて、ペアの候補として表示してもよい。あるいは、次に最適なベクトルを用いて、原画１の閉領域と最も重なりの大きな原画２の閉領域を見つけて、次のペアの候補として表示してもよい。
【００９０】
例えば、図３（Ａ）の原画１に存在するｉ個の閉領域Ｄｉ（３個の閉領域１Ａ、１Ｂ、１Ｃ）のうちで一番大きな閉領域を占める閉領域１Ａをまず取り出し、閉領域１Ａに含まれる画素ｐ全てに対して、図３（Ｂ）の原画２に重ねて、移動ベクトルδを動かしながら閉領域Ａ１に対するコスト関数Ｅ（Ｄｉ，δ）を式２によって計算してもよい。
【００９１】
【数１】
2018067103.tif 000002
ここで、ｐ＋δは、原画２とその背景とを移動ベクトルδだけずらし、閉領域Ｄｉ（例えば閉領域１Ａ）と重ねたときの、閉領域Ｄｉ（例えば閉領域１Ａ）内の画素ｐの位置に重なる原画２又は背景の位置である。Ｖ１（ｐ）は、原画１の閉領域Ｄｉ（例えば閉領域１Ａ）の画素位置ｐにおける画素の特徴ベクトルである。そして、Ｖ２（ｐ＋δ）は、原画２及びその背景の画素位置ｐ＋δにおける画素の特徴ベクトルである。原画１の閉領域Ｄｉ（例えば閉領域１Ａ）の画素位置ｐに重なる原画２が閉領域内部である場合（例えば閉領域２Ａ内部）には、原画１と原画２の特徴ベクトルの差の二乗を計算し積算する（式２上段）。原画１の閉領域Ｄｉ（例えば閉領域１Ａ）の画素位置ｐに重なる原画２が閉領域内部でない場合（例えば背景や境界線）には、式２の下段の計算を行い、定数γを積算する。γを積算する意味は、背景部分との重なりについては、比較的大きな定数γを加えることにより、コスト関数が大きくなり、ペナルティを与えるためである。γは、原画の全体のピクセル数あるいは、閉領域のピクセル数によって妥当な値を選択する。たとえば、γ＝２などの定数を設定すればよい。
【００９２】
なお、原画２のp+δの位置が閉領域内部でない場合、式２の下段の計算を行うこととしたが、たとえば、すでに対応付けがなされた原画２における閉領域は、背景等と同じ扱いとして、式２の下段の計算を行ってもよい。
【００９３】
なお、特徴ベクトルは、既に式１に示した。
【００９４】
移動ベクトルδは、例えば画素を単位とする二次元の移動ベクトルであり、原画１の閉領域Ｄｉ（例えば閉領域１Ａ）を取り出し、原画２及びその背景を移動ベクトルδだけ移動させて両者を重ね合わせるために用いるベクトルである。そして、上記式２のコスト関数Ｅを最小にする二次元の移動ベクトルδ＊ｉを求める。例えば、閉領域１Ａと原画２及びその背景とをδの値を変化させながら、コスト関数Ｅが最小となるδ＊ｉを以下の式のように求める。
δ＊ｉ＝argminδＥ（Ｄｉ，δ）                      （式３）
ここで、argminδＥ（Ｄｉ，δ）とは、Ｅ（Ｄｉ，δ）の値を最小とする引数δを求めることを意味する。
【００９５】
そして、例えば原画１の１つの閉領域Ｄｉ（例えば閉領域１Ａ）に対して、網羅的にδを変化させて原画２及び背景を重ねてコスト関数Ｅを計算し、コスト関数Ｅを最小にするように、上記式３を満足するδ＊ｉを求める。あるいは、コスト関数Ｅの網羅的な計算の途中において、コスト関数Ｅの最小値（計算途中の極小値）が所定の計算回数の中で更新されなくなった場合には、網羅的なδの計算を途中で打ち切って、それまでに得られたコスト関数の最小値を採用してもよい。あるいは、大きな面積の閉領域に対してのコスト関数Ｅの計算においては、例えば、原画１の閉領域の１つおきの画素に限定して、コスト関数Ｅを計算し計算量を減少させることで、計算速度を速めてもよい。
【００９６】
この移動ベクトルδ＊ｉを用いたときに、閉領域Ｄｉ（例えば閉領域１Ａ）と原画２との間で、閉領域の重なる面積（例えば画素数）が最大となる原画２の閉領域が原画１の閉領域Ｄｉに対応する原画２の閉領域であると推定することができる。
【００９７】
以下、図４を用いて、対応関係の推定の一例を具体的に示す。
【００９８】
説明をわかりやすくするために、原画１の閉領域１Ｃに対応する原画２の閉領域を求める例を、図４を用いて示す。
【００９９】
図４（Ａ）において、原画１の閉領域１Ｃを取り出し、原画２にそのまま重ねる。そして、この状態で、閉領域Ｃ１についてコスト関数Ｅ（Ｃ１，δ）を求める。δの初期値はゼロベクトルである。なお、移動ベクトルδは、図４では、１Ｃを動かすように描かれているが、式２では、原画２の項の座標位置に足されている。移動ベクトルδは、相対的な重ね合わせの位置関係を規定するベクトルであるから、図においては、直感的にわかりやすくするために、原画１から取り出した閉領域を移動させるベクトルとして描いている点に留意すべきである。式２と図４の記載は、相対的な表現に関して、同義である。
【０１００】
その後、移動ベクトルδを網羅的に変化させて、コスト関数Ｅ（Ｃ１，δ）を最小にするδ＊を図４（Ｂ）に示されているように求める。
【０１０１】
図４（Ｂ）に示されるように、原画２の閉領域のうち、閉領域Ｃ１との重なりの面積が一番大きな、原画２の閉領域を求める。この場合、閉領域２Ｃと閉領域１Ｃとは、領域Ｓ１において重なっている。そして、閉領域２Ａと閉領域１Ｃとは、領域Ｓ２において重なっている。これらの重なりのうち、一番大きな重なりは、Ｓ２であることがわかる。したがって、一番大きな重なりの領域を共有する閉領域１Ｃと閉領域２Ｃとが対応することが推定される。
【０１０２】
このようにして、原画１の閉領域１Ｃと原画２の閉領域２Ｃとの対応付けの推定がなされた。この推定を表示して、オペレータに確認を促してもよい。あるいは、オペレータの確認を得ずに、対応付けを確定させてもよい。仮に、オペレータが、対応付けの推定が間違っている旨を入力した場合には、次に重なりの面積が大きい領域（図４（Ｂ））の場合には、閉領域１Ｃと閉領域２Ａとのペアを表示して、次の候補の対応を推定し表示してもよい。
【０１０３】
あるいは、オペレータが、対応付けの推定が間違っている旨を入力した場合には、コスト関数が移動ベクトルδ＊の次に小さくなった移動ベクトルδを用いて、Ｃ１との重なりの面積が一番大きな原画２の閉領域を、閉領域Ｃ１に対応する次の閉領域の候補として、推定し、表示して、オペレータに確認を促してもよい。
【０１０４】
図５は、閉領域の対応表が示されている。以上の結果によって、原画１と原画２にそれぞれ存在する閉領域の対応関係が確定し、図５の対応表が記憶される。この対応表を用いて、原画１において、彩色を行えば、原画２における彩色は自動的に行うことができる。
【０１０５】
＜１−８＞  領域の対応付けの動作
図６は、領域の対応付けの例を示すフローチャートである。
【０１０６】
ステップＳ１００でパラメータｉ及びｊを初期化する。パラメータｉは、例えば図３（Ａ）に示すように原画１の閉領域を面積の大きい順に並べた際の順番（Ｎｏ）であってもよい。ｉは、原画１の各閉領域を一意に特定できる番号であればよい。パラメータｊは、例えば図３（Ｂ）に示すように原画２の閉領域を面積の大きい順に並べた際の順番（Ｎｏ）であってもよい。ｊは、原画２の各閉領域を一意に特定できる番号であればよい。
【０１０７】
ステップＳ１０２で、一方の画像（原画１）から１つの閉領域ｉ（例えば閉領域１Ａ）を抽出する。
【０１０８】
ステップＳ１０４で、閉領域Ｄｉと他方の原画とからコスト関数Ｅ（Ｄｉ，δ）を算出する。
【０１０９】
ステップＳ１０６で、δを網羅的に変化させたかがチェックされる。チェックが「いいえ」であれば、ステップＳ１３２に移る。チェックが「はい」であれば、ステップＳ１０８に移る。
【０１１０】
ステップＳ１３２でδを所定の値だけ変化させる。
【０１１１】
ステップＳ１０８で、コスト関数Ｅ（Ｄｉ，δ）が最小となる場合の移動ベクトルδ＊１を保存する。
【０１１２】
ステップＳ１１０で、δ＊１を用いて、閉領域Ｄｉと重なる面積が最大の他方の原画の閉領域Ｄｊを閉領域Ｄｉに対応する領域と推定する。
【０１１３】
ステップＳ１５２で、閉領域の対応を表示し、オペレータに確認を促してもよい。対応が間違っていると入力された場合には、次のペアの候補を表示させてもよい。また、オペレータの指示により、閉領域の正しい対応関係が入力されてもよい。この時に、彩色の指示を促してもよい。
【０１１４】
ステップＳ１５４で、対応関係が確定された原画１の閉領域Ｄｉと原画２の閉領域Ｄｊとを、その後の対応関係の処理の対象から除いてもよい。この操作は、図３の対応付けフラグを用いてもよい。
【０１１５】
ステップＳ１１２で、ｉ＝Ｉとなったかがチェックされる。すなわち、原画１における閉領域全てに対して、対応付けの処理が完了したかがチェックされる。このチェックが「いいえ」であれば、ステップＳ１３４に移る。このチェックが「はい」であれば、全体の処理を終了させてもよい。
【０１１６】
ステップＳ１３４でｉをインクリメントする。この操作によって、原画１の次の閉領域をステップＳ１０２で抽出できる。
【０１１７】
実施形態１の処理フローの概要は以上のとおりである。
【０１１８】
＜２＞  実施形態２：交点の対応付け
＜２−１＞  交点の対応付けの処理の詳細
以下に、原画１と原画２のそれぞれに存在する交点の対応付けについて説明する。交点の対応付けの情報は、原画１と原画２とを補間した画像の生成に利用することができる。
【０１１９】
図７は、複数の閉領域を含む２つの画像のそれぞれに存在する交点の対応付けの例を示す図である。
【０１２０】
すでに説明した処理によって、原画１と原画２との間の各閉領域の対応付けが完了していることを前提とする。図７（Ａ）の原画１の丸で囲んだ閉領域の拡大図が図７（Ｃ）に示されている。そして、図７（Ｂ）の原画２の丸で囲んだ閉領域の拡大図が図７（Ｄ）に示されている。既に、閉領域２Ｂは閉領域１Ｂと対応していることがわかっており、閉領域２Ｃは閉領域１Ｃと対応していることがわかっている。また、原画１及び原画２には、同じ背景Ｙが存在している。
【０１２１】
既に説明したように、図７（Ｃ）における交点１３の周囲に存在する複数の閉領域は、左回りに閉領域１Ｂ、背景Ｙ、閉領域１Ｃの順に存在しており、同様に図７（Ｄ）における交点２３の周囲に存在する複数の閉領域は、左回りに閉領域１Ｂに対応する閉領域２Ｂ、背景Ｙ、閉領域１Ｃに対応する閉領域２Ｃの順に存在している。したがって、交点１３に接する閉領域の位置関係のパターンは、交点２３に接する閉領域の位置関係のパターンと一致していることがわかる。このことから、交点１３と交点２３とが対応関係にあることを自動的に推定することが可能である。このようにして、対応付けされた閉領域の情報を用いることによって、対応する交点の対応付けを自動的に推定することができる。この推定結果を画面に表示して、オペレータに最終的な対応関係の確定を促してもよい。或いは、推定された交点の対応関係を、自動的に確定させてもよい。
【０１２２】
図８は、複数の閉領域を含む２つの画像のそれぞれの交点の対応づけの結果を示す図である。対応づけられた交点の情報は、図８に示す交点の対応表によって、記憶することができる。
【０１２３】
図９は、複数の閉領域を含む２つの画像のそれぞれに存在する交点の対応付けの際に発生する第１の課題の例を示す図である。図９においては、前提として、閉領域１Ａと２Ａ、閉領域１Ｂと２Ｂ、閉領域１Ｃと２Ｃ、閉領域１Ｄと２Ｄ、がそれぞれ対応する閉領域であると仮定する。
【０１２４】
この場合、図９（Ａ）の原画１においては、交点Ｐ１１の周囲に、左回りに閉領域１Ａ、１Ｄ、１Ｂが存在する。これに対して、図９（Ｂ）の原画２においては、交点Ｐ２１に閉領域２Ａ、２Ｄ、２Ｃが存在する。この例では、交点Ｐ１１と交点Ｐ２１とは、周囲に同じパターンで対応する閉領域が存在しないため、対応する交点ではないと判断される。原画１の交点Ｐ１１に対応する交点が原画２には存在しない。
【０１２５】
しかしながら、図９（Ａ）の２つの交点（交点Ｐ１１及び交点Ｐ１２）及び図９（Ｂ）（交点Ｐ２１及び交点Ｐ２２）をまとまりとして捉えた場合には、原画１の交点Ｐ１１と交点Ｐ１２の周りに左回りに閉領域１Ａ、１Ｄ、１Ｃ，１Ｂが存在し、原画２の交点Ｐ２１と交点Ｐ２２の周りに左回りに閉領域２Ａ、２Ｄ、２Ｃ，２Ｂが存在し、閉領域の対応関係を考慮すると、同一のパターンで閉領域が存在していることがわかる。
【０１２６】
図９の例においても、以下の処理を行うことにより、交点どうしの対応付けを行うことができる。
【０１２７】
図１０は、複数の閉領域を含む画像に存在する交点及び境界線を修正する処理の例を示す図である。
【０１２８】
図９（Ａ）において原画１を選択する、原画１の代わりに原画２を選択してもよい。図１０（Ａ）に示されるように選択された原画１に存在する２つの交点（交点Ｐ１１、交点Ｐ１２）のうち、１つを削除する。図１０（Ａ）の場合には、交点Ｐ１２を消去する。削除する交点は、いずれの交点であってもよい。これによって、閉領域の境界線Ｌｄｂ、Ｌｂｃ、Ｌｃｄが残る。なお、交点のうち、交点の角度が小さい方の交点（すなわち交点Ｐ１２でＬｃｄとＬｂｃが領域１Ｃ側でなす角度の方が、交点Ｐ１１でＬａｄとＬａｂが領域１Ａ側でなす角度より小さいため、この場合は、交点Ｐ１２）を優先して削除するようにしてもよい。
【０１２９】
図１０（Ｂ）に示すように、境界線ＬｂｃをＬｄｂに沿って交点Ｐ１１まで延ばす。延長されたＬｂｃの交点Ｐ１１の位置の交点を交点Ｐ１１１とする。
【０１３０】
図１０（Ｃ）に示すように、境界線ＬｃｄをＬｄｂに沿って交点Ｐ１１まで延ばす。延長されたＬｃｄの交点Ｐ１１の位置の交点を交点Ｐ１１２とする。
【０１３１】
なお、上記操作の後、Ｌｄｂは削除してもよい。なお、Ｌｄｂの削除のタイミングはこの時に限られるものではなく、他のタイミングで削除してもよい。
【０１３２】
図１０（Ｄ）に示すように、この結果、交点Ｐ１２が削除され、境界線Ｌｂｃが延長され、交点Ｐ１１の位置に交点Ｐ１１１が設定された。境界線Ｌｂｃが延長され、交点Ｐ１１の位置に交点Ｐ１１２が設定された。このため、交点Ｐ１１は、交点Ｐ１１１と交点Ｐ１１２の２つに分割されたと考えることができる。なお、延長された境界線Ｌｂｃと、延長された境界線Ｌｃｄとは、離れて描かれているが、図を分かりやすくするために離れて描かれているのであって、実際は、同一線上に存在する。その他の図においても同様である。
【０１３３】
図１１は、複数の閉領域を含む画像に存在する交点及び境界線を修正する処理の結果に基づいて、交点の対応付けの例を示す図である。
【０１３４】
先に示した図１０の処理によって、図１１（Ａ）では、交点Ｐ１２が削除され、境界線Ｌｂｃが延長され、交点Ｐ１１の位置に交点Ｐ１１１が設定された。境界線Ｌｂｃが延長され、交点Ｐ１１の位置に交点Ｐ１１２が設定された。このため、交点Ｐ１１は、交点Ｐ１１１と交点Ｐ１１２の２つに分割された。
【０１３５】
図１１（Ｂ）に示すように、原画２は、そのまま２つの交点Ｐ２１及び交点Ｐ２２が存在している。図１１（Ｃ）の交点の対応表に示されるように、原画１の交点Ｐ１１１と原画２の交点Ｐ２１とを対応づける。そして、原画１の交点Ｐ１１２と原画２の交点２２とを対応づける。そして、図１１（Ａ）の交点Ｐ１１１と交点Ｐ１１２との間は、長さ零の境界線が存在していることとする。また、交点Ｐ１１１は、境界線Ｌａｂと接続させ、交点Ｐ１１２は境界線Ｌａｄと接続させる。交点Ｐ１１は削除してもよい。なお、交点Ｐ１１の削除のタイミングは、この時に限られるものではなく、他のタイミングで削除してもよい。
【０１３６】
以上の処理を行うことにより、図９のように対応付けが行えなかった交点に対しても、いずれかの原画の１つの交点を削除し、上記の処理を施すことによって、交点の対応付けが行える。
【０１３７】
［交点の対応付けの動作］
図１２は、図９に示したように、原画１と原画２のそれぞれの１つの交点どうしでは対応付けができない場合であって、２つの交点をまとまりとして捉えた場合に、それらの周囲に存在する複数の閉領域のパターンが同一である場合を発見するフローチャートである。理解を助けるために、図１２のフローチャート及び下記の説明において、括弧書きで図９に示した符号を例示として示す。なお、図１２のフローチャートは、図９の例に限定されるものではない。
【０１３８】
ステップＳ３００において、一方の原画（原画１）において点の対応付けが行えなかった複数の点のうち、２つの閉領域（１Ｄ，１Ｂ）の境界線上（Ｌｄｂ）に存在する隣り合う２つの交点（Ｐ１１，Ｐ１２）の組ｑの集合Ｑを抽出する。
【０１３９】
ステップＳ３０２において、他方の原画（原画２）において点の対応付けが行えなかった複数の点のうち、２つの閉領域（２Ａ，２Ｃ）の境界線（Ｌａｃ）上に存在する隣り合う２つの交点（Ｐ２１，Ｐ２２）の組ｒの集合Ｒを抽出する。
【０１４０】
ステップＳ３０４は、ステップＳ３１４との間で、集合Ｑに含まれる要素ｑを、１つずつ取り出して処理を行う繰り返しの処理を示す。
【０１４１】
ステップＳ３０６は、ステップＳ３１２との間で、集合Ｒに含まれる要素ｒを、１つずつ取り出して処理を行う繰り返しの処理を示す。
【０１４２】
ステップＳ３０８で、ｑに含まれる２つの交点（Ｐ１１，Ｐ１２）の少なくとも１つに接する複数の閉領域の並びのパターン（左回りに１Ａ，１Ｄ，１Ｃ，１Ｂ）が、ｒに含まれる２つの交点（Ｐ２１，Ｐ２２）の少なくとも１つに接する複数の閉領域（２Ａ，２Ｄ，２Ｃ，２Ｂ）のそれぞれに対応する一方の原画の閉領域の並びのパターン（左回りに１Ａ，１Ｄ，１Ｃ，１Ｂ）と一致するか否かをチェックする。
【０１４３】
ステップＳ３１０は、ステップＳ３０８におけるチェックが一致しているか否かを判断する。チェックが一致していればステップＳ３２０に進む。チェックが一致していなければ、ステップＳ３１２に進む。
【０１４４】
ステップＳ３２０で、ｒとｑとが対応すると認識し、ｓ＝（ｒ，ｑ）として、要素ｓを集合Ｓに加え、記憶する。
【０１４５】
以上の処理を行うことにより、図９に示すような、２つの交点どうしの対応関係を抽出することができる。
【０１４６】
図１３は、図１２で抽出した２つの交点の組を要素ｓとする集合から、要素ｓを１つずつ取り出して、交点の対応付けを行う処理を示すフローチャートである。理解を助けるために、図１２のフローチャート及び下記の説明において、括弧書きで図９に示した符号を例示として示す。
【０１４７】
ステップＳ４００は、集合Ｓから１つずつ要素ｓを取り出して、ステップＳ４１２との間で処理を繰り返すことを示している。
【０１４８】
ステップＳ４０２で、１つの交点の削除を行う。なお、図１２のフローチャートは、図９の例に限定されるものではない。なお、以下に示すように、集合を定義する。
ｓ∈Ｓ
ｓ＝（ｑ，ｒ）
ｑ∈交点Ｐ１１，交点Ｐ１２  （一方の原画（原画１）に含まれる交点）
ｒ∈交点Ｐ２１，交点Ｐ２２  （他方の原画（原画２）に含まれる交点）
このステップＳ４０２においては、一方の原画の交点の組（ｑ）に含まれる２つの交点（Ｐ１１，Ｐ１２）のうちいずれか１つの交点（Ｐ１２）を削除する。
【０１４９】
ステップＳ４０４で、削除された交点（Ｐ１２）に接続されており、残された交点（Ｐ１２）に接続されていない２つの境界線（Ｌｂｃ，Ｌｃｄ）を特定する。
【０１５０】
Ｓ４０６で、特定された２つの境界線（Ｌｂｃ，Ｌｃｄ）の各々を、削除された交点（Ｐ１２）と残された交点（Ｐ１１）とを結ぶ境界線（Ｌｄｂ）に沿って、残された交点（Ｐ１１）まで延長する。
【０１５１】
ステップＳ４０８で、延長された２つの境界線（Ｌｂｃ，Ｌｃｄ）の一方の境界線（Ｌｂｃ）の延長された端に第１の交点（Ｐ１１１）を生成し、前記一方の境界線（Ｌｂｃ）を境に隣接する２つの閉領域（１Ｂ，１Ｃ）に対応する他方の原画（原画２）の閉領域（２Ｂ，２Ｃ）の境界線（Ｌ２ｂｃ）上の点（Ｐ２１）を、生成された前記第１の交点（Ｐ１１１）に対応させる。交点Ｐ１１１は、境界線Ｌａｂに接続させる。同様に、延長された２つの境界線（Ｌｂｃ，Ｌｃｄ）の他方の境界線（Ｌｃｄ）の延長された端に第２の交点（Ｐ１１２）を生成し、前記一方の境界線（Ｌｄｃ）を境に隣接する２つの閉領域（１Ｄ，１Ｃ）に対応する他方の原画（原画２）の閉領域（２Ｄ，２Ｃ）の境界線（Ｌ２ｃｄ）上の点（Ｐ２２）を、生成された前記第２の交点（Ｐ１１２）に対応させる。交点Ｐ１１２は、境界線Ｌａｄに接続させる。
【０１５２】
ステップＳ４１０で、残された交点（Ｐ１１）を削除する。生成された２つの交点（Ｐ１１１，Ｐ１１２）は、長さ零の境界線で結ばれているとする。境界線Ｌｄｂを削除してもよい。交点Ｐ１１を消去してもよい。
【０１５３】
以上の処理を行うことによって、図９のパターンに対して、交点の対応付けの処理を行うことができる。
【０１５４】
図１４は、図１１、図１２及び図１３の処理が適用された２つの原画に対する中割り画像Ｎを生成する例を示している。
【０１５５】
図１４の中割り画像Ｎに示されるように、原画１の交点Ｐ１１１が中割り画像の交点ＮＰ１１１に対応し、原画１の交点Ｐ１１２が中割り画像の交点ＮＰ１１２に対応する。そして、原画１では長さが零であった境界線が、中割り画像Ｎにおける交点ＮＰ１１１と交点ＮＰ１１２との間に境界線Ｌａｃとして表示されていることがわかる。このようにして、交点の対応付けを行うことにより、中割り画像を自動的に生成することが可能である。
【０１５６】
なお、中割り画像Ｎを生成する場合には、各境界線の形状についても補間を行い、なめらかな中割り画像が生成されるようにしてもよい。或いは、対応する交点、対応する境界線、対応する閉領域の情報等を用いて、モーフィングの技術により、中割り画像Ｎを生成するようにしてもよい。また、２つの原画にそれぞれ存在する閉領域を構成しない線及び点等については、閉領域及び交点の対応関係から、それらの対応関係を推測することが可能である場合が多い。なお、２つの原画に存在する閉領域、線、点などのうち、対応関係が推測不可能であるものについては、オペレータに対して、対応関係の指定を行うよう促してもよい。最終的に、オペレータの指示もなされておらず、対応関係が不明である閉領域、線、点などについては、周囲の閉領域、線、点など補間の位置関係から、中割り画像における位置関係を決定してもよい。モーフィングの技術に見られるように、２つの原画に存在する全ての構成要素の対応関係が判明していなくても、モーフィングの技術等を利用することにより、中割り画像を生成することは可能である。
【０１５７】
図１５は、図１４に示した例と同様の例であって、中割り画像を複数生成した場合の例を示している。原画５と原画６との間に、時間軸に沿ってＮ０１からＮ１０までの１０個の中割り画像が生成されている。原画及び中割り画像は、それぞれ、動画の１フレームに対応する。図１５の場合には、原画５、１０個の中割り画像、原画６の１２のフレームが連続して表示され、スムーズな動画が再生されることとなる。
【０１５８】
図１６は、交点の無い閉領域の境界線に端点を付与することで交点を作る例を示す図である。この例の場合には、原画７と原画８とにそれぞれ１つずつの交点（交点Ｐ５１及び交点Ｐ６１）が図示されている。それぞれの原画における閉領域の交点の数は、複数であってもよい。この場合には、まず、２つの閉領域を１つの平面上に置く。これら２つの閉領域の間のハウスドルフ距離を求める。次に一方の閉領域の境界線上の全ての点について、他方の閉領域の境界線上の点からの距離が最小となるそれぞれの点を求め、一方の閉領域の点と他方の閉領域の点とを対応づけた２点の組の集合を作る。それぞれの組において、２点間の距離がハウスドルフ距離と等しい組を、対応のついた交点としてそれぞれの閉領域に付与する。なお、２点間の距離がハウスドルフ距離と等しい点の組が複数ある場合は任意の組を選択して対応のついた交点としてもよい。
【０１５９】
ハウスドルフ距離ｄＨは、一般に、２つの集合Ａと集合Ｂがある場合に、集合Ａのどの点であっても少なくとも距離ｄＨだけ進めば集合Ｂのどれかの点に到達できる。同じく、集合Ｂのどの点であっても少なくとも距離ｄＨだけ進めば集合Ａのどれかの点に到達できる。このような距離ｄＨをハウスドルフ距離と言う。図１６の場合には、同一平面上に置いた、原画７と原画８において、原画７に含まれる複数の画素が集合Ａに対応し、原画８に含まれる画素が集合Ｂに対応する。
【０１６０】
なお、必ずしもハウスドルフ距離を採用する必要はなく、閉領域で、形状の似ている位置の点を、対応する交点として採用してもよい。また、パターン認識などの手法を用いて、類似するパターン上に存在する点どうしを対応する交点としてもよい。
【０１６１】
図１７は、２つの原画の片方が孤立した閉路を持つ場合の交点の処理の例を示す図である。原画９は、孤立した閉路と直線が存在している。原画１０Ａでは、直線と円が接触しており、交点Ｐ１０１及び交点Ｐ１０２が存在している。
【０１６２】
この場合には、原画９と原画１０Ａとで、交点の対応付けが行えない。したがって、以下のようにすることが望ましい。
【０１６３】
すなわち、原画１０Ｂに示されるように、交点Ｐ１０１及び交点Ｐ１０２を削除する。そして、交点Ｐ１０１に接続していた直線と、交点Ｐ１０２に接続していた直線を延長して、一つの直線にする。さらに、交点Ｐ１０１に接続していた円の端点と、交点Ｐ１０２に接続していた円の端点とを接続して、一つの円形状の図を作る。次に、原画９及び原画１０Ｂに、図１６で示した手法を用いて新たな交点を設ける。例えば、交点Ｐ０９３と、交点Ｐ１０３を設ける。この場合、図１６を用いて説明したように、平面上に２つの円形状の図を置いた場合に、これらの２つの円の間のハウスドルフ距離を用いて、交点を付与してもよい。
【０１６４】
図１８は、原画をレイヤーに分けて、処理を行う例を示す図である。原画１１には、笛の上部１１Ａと笛の下部１１Ｂが存在している。そして、原画１２にも、笛の上部１２Ａと笛の下部１２Ｂが存在している。このような笛の部分の画像の周辺では、２つの原画における交点の対応付けが単純に行えないことがある。すなわち、図７及び図９に関連して例示した交点の対応付けの処理によっても、なお、対応付けが行えない交点を含む閉領域が存在することがある。このような閉領域に対しては、その閉領域を切り出し、別のレイヤー（層）に移動させ、交点の対応付けの処理をレイヤー毎に別個に行うことが有効である。
【０１６５】
すなわち、原画１１及び原画１２の笛の部分をそれぞれ別のレイヤーにコピーし、基の原画からは、笛の画像部分を削除する。この操作を行うと、人間の部分のレイヤーと笛の部分のレイヤーに原画を分けて、交点の対応付けの処理をすることができる。レイヤーに分けるか否かの判断手法としては、図９のパターンが周辺に多く発生する閉領域を他のレイヤーに移すことが有効である。
【０１６６】
なお、一部の閉領域を他のレイヤーに移し、他のレイヤーに移した画像を原画から削除することが望ましい。この際に、削除された部分の周辺が空白となってしまい、閉領域が存在しない部分が発生する場合がある。すなわち、一部の閉領域を他のレイヤーに移動させた残りの画像の空白部分には、閉領域が存在せず、閉領域が開いた形の分岐線が存在する場合がある。この場合には、分岐線をそのまま残して、分岐線の端の点（端点）を特定し、一方の原画と他方の原画とで、端点どうしの対応付けを行ってもよい。あるいは、対応付けが行えない交点が残ってしまう場合には、オペレータに対して指示を行うよう促してもよい。
【０１６７】
あるいは、上記の場合には、閉領域を削除した部分の周辺に存在する線分を延長して、つなぎ合わせる処理を行うことにより、閉領域を形成することが可能である。原画をレイヤーに分けて、交点の対応付けを行う際には、新たに生成された閉領域の対応付けの処理を行うことが必要となる場合がある。この場合には、レイヤーに移す前に存在した閉領域を結合させることにより、多くの場合対処することができる。なお、対処することができない場合には、再度、閉領域の対応付けを部分的に再度行うことも有効である。
＜３＞  実施形態３：中割り画像の形成の変形例
以上のようにして、２つの原画の閉領域の対応付け、交点の対応付けを順番に行うことにより、２つの原画の各部の対応付けが行える。
【０１６８】
中割り画像は、２つの原画の交点の位置を補間することで行えるが、閉領域の対応関係、閉領域の境界線の形状、対応する交点を結んだ境界線の対応関係等をも勘案して、総合的に原画の補間を行うことがより自然な中割り画像を作成する上で有利である。
【０１６９】
また、閉領域の画像の対応付けの際に、オペレータに彩色の指示を促すことで、彩色の処理と、閉領域の確認とをまとめてオペレータに促すことができる。
【０１７０】
例えば原画１と原画２との閉領域の対応付けを行い、次に原画２と原画３の閉領域の対応付けを行うように、順番に対応付けを行うようにしてもよい。この場合、原画１と原画２との閉領域の対応付けの際に彩色の指示をオペレータが行えば、原画２と原画３との閉領域の対応付けの際の彩色は、略自動で行えることとなる。しかも、中割り画像の彩色は、原画の彩色から容易に推定できるので、中割り画像の彩色も略自動で行えることとなる。
【０１７１】
＜４＞  実施形態４（閉領域の対応付けの変形例）
図１８を用いて、一方の原画の２つの閉領域が、他方の原画における１つの閉領域に対応する場合の処理の例を以下に説明する。
【０１７２】
図１８において、原画１１における閉領域１１０及び閉領域１１１は、原画１２における閉領域１２１に対応している。この場合には、閉領域の対応付けが多対１の形式になっている。このような状況は、閉領域の前側に、多のオブジェクトが重なっている原画の場合に発生しやすい。このような場合にも対処するためには、例えば、以下のような処理を行えばよい。
【０１７３】
まず、原画１１の閉領域１１０に対応する原画１２の閉領域を、上述の実施形態１で推定する。この推定によって、閉領域１１０に対応する閉領域として１２１が推定される。この時点で、対応する閉領域１１０と閉領域１２１とを画面に表示して、オペレータに確認を促す。オペレータは、閉領域の対応付けとして、原画１１の閉領域１１１が残っていることがわかる。このため、推定は、部分的に正しいことを入力する。この入力においては、原画１１の領域１１０は、以後の閉領域の対応の対象から除外し、閉領域１２１は、以後の閉領域の対象から除外しないように、オペレータが指示を行えばよい。この指示は、図３に示した表の対応付けの欄におけるフラグの処理で実現できる。すなわち、領域１１０の対応付けのフラグを１として、以後の対応付けの対象から除外する。これに対して、領域１２１の対応付けの欄は、フラグを０のままとし、以後の対応付けにおいても、考慮されるようにすればよい。オペレータは、この時、併せて、彩色の指示を行ってもよい。オペレータの彩色の指示によって、閉領域１１０と閉領域１２１が同じ色で彩色されるが、閉領域１２１は、閉領域の推定対象としての状態を保持することができる。
【０１７４】
その後、原画１１の閉領域１１１の対応付けの処理の際に、再度、原画１２の閉領域１２１が、対応する旨の推定がなされることとなるので、この対応付けが表示され、オペレータへの指示の入力が促された際に、オペレータは、対応付けが正しいことを入力する。このオペレータの指示によって、図３に示す閉領域１１１の対応付けのフラグと、閉領域１２１の対応付けのフラグが、いずれも０から１に置き換えられ、これらの閉領域は、以後の閉領域の対応付けの推定の処理の対象から除かれることとなる。
【０１７５】
なお、図３の対応付けの欄を使わないこととすれば、閉領域の対応付けとして、１対多、多対１、多対多の閉領域の対応付けを許容することができる。この場合にも、対応付けが正しいか否かの指示をオペレータが入力するように促してもよい。
【０１７６】
＜５＞  ハードウエア構成
図１９は、各実施形態のハードウエア構成１７００を示す図である。
【０１７７】
ハードウエア構成１７００は、ＣＰＵ１７１０、メモリ１７２０、通信制御部１７３０、入出力インタフェース１７４０、表示制御部１７５０、ドライブ制御部１７６０、及び印刷制御部１７７０を有する。
【０１７８】
そして、通信制御部１７３０には、インターネットなどのネットワークが接続される。入出力インタフェース１７４０には、入出力装置１７４２が接続される。表示制御部１７５０には、表示装置１７５２が接続される。ドライブ制御部１７６０は、記憶媒体１７６２を読み書きすることができる。印刷制御部１７７０には、プリンタ１７７２が接続される。
【０１７９】
記憶媒体１７６２は、ＲＡＭ、ＲＯＭ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ハードディスク、メモリーカード等であってもよい。
【０１８０】
以上説明した実施形態の方法は，コンピュータにより実行され得る。また，実施形態の方法は，コンピュータに実行させるプログラムとして，インプリメントされてもよい。プログラムの一部又は前部は、オペレーティングシステムにより実行されてもよい。また、プログラムの一部がハードウエアにより実現されてもよい。プログラムは記憶媒体１７６２に記憶されてもよい。
【０１８１】
なお，上述の実施形態において，方法のステップ又はプログラムのステップは、矛盾のない限り，同時に，又は順序を入れ替えて実行されてもよい。
【０１８２】
以上の実施形態は，ハードウエアの装置としてインプリメントされ得る。
【０１８３】
以上の実施形態は，請求項に記載された発明を限定するものではなく，例示として取り扱われることは言うまでもない。
【０１８４】
なお、原画及び中割り画像に含まれる閉領域並びに背景は、領域の一例である。原画、中割り画像、背景は、画像を構成する要素の例である。境界線は、閉領域の輪郭の一部を構成する要素となり得る。
【０１８５】
＜５＞実施形態５
実施形態５は、閉領域の対応付けに係る実施形態１の変形例である。
【０１８６】
図２０は、原画１から対応付けする閉領域を選択する手順の例を示す図である。既に、原画１と原画２との間で、グレーで示された二組の閉領域が対応づけられている。すなわち、原画１の閉領域１Ｐは、原画２の閉領域２Ｐに対応づけられている。加えて、原画１の閉領域１Ｑは、原画２の閉領域２Ｑに対応づけられている。対応付けを行う順番は、原則として面積の大きな閉領域から対応付けを行うことが望ましい。以下の説明では、対応付けが終了している閉領域を既対応の閉領域と呼び、対応付けが未だ行われていない閉領域を未対応の閉領域と呼ぶ。
【０１８７】
本実施形態では、原則として、直前に対応付けが完了した既対応の閉領域であって、原画像１に存在する既対応の閉領域に隣接する未対応の閉領域のうち、その既対応の閉領域に隣接する境界線の長さが長い未対応の閉領域を、注目する閉領域とする。原画像２の既対応の閉領域に隣接する未対応の閉領域のうち、この注目する閉領域に対応する原画２の閉領域を探索することになる。境界線の長さは、隣接する境界線のピクセル数を数えることによって計測してもよい。
【０１８８】
図２０においては、直前に対応づけられた、原画１に存在する閉領域が閉領域１Ｑである。この１Ｑに隣接する未対応の閉領域は、閉領域１Ｓのみであるため、閉領域１Ｓに注目する。複数の未対応の閉領域が閉領域１Ｑに隣接している場合には、閉領域１Ｑに隣接する境界の長さが一番長い閉領域を注目する閉領域として選択すればよい。このように、既に対応付けが確定している領域に隣接する未対応の領域のうち、隣接する境界の長さが一番長い閉領域を選ぶことによって、対応付けの確度がより高くなる。
【０１８９】
この注目している未対応の閉領域１Ｓに注目して、たとえば、実施形態１を用いて、コスト計算を行い、コストが最小となる閉領域を、原画２の閉領域２Ｑに隣接する閉領域の中で探索する。この探索によって、閉領域１Ｓに対応する閉領域として、閉領域Ｓ２が特定される。
【０１９０】
なお、上記の例では、注目する閉領域として閉領域１Ｓを選択したが、以下のようにして、他の未対応の閉領域を注目する閉領域として特定してもよい。
【０１９１】
すなわち、上記の例では、閉領域１Ｓが注目領域として特定されたが、更に、閉領域１Ｓに対して既対応の閉領域が複数隣接している場合には、例えば以下のようにする。閉領域１Ｓには、既対応の閉領域として閉領域１Ｑと閉領域１Ｐが隣接している。閉領域１Ｓが閉領域１Ｑに対して隣接する長さは、点２０１１から点２０１２までの境界線の長さである（この場合、「隣接長さ２０１１−２０１２」と略記する、以下同様）。閉領域１Ｓが閉領域１Ｐと隣接する長さは、隣接長さ２０１２−２０１３である。この場合、閉領域１Ｓに関して、閉領域１Ｐとの隣接長さの方が、閉領域１Ｑとの隣接長さより長いため、基準となる閉領域を、閉領域１Ｑから閉領域１Ｐに置き換える。
【０１９２】
そして、基準となる閉領域１Ｐに隣接する未対応の閉領域のうち、隣接する境界線の長さが一番長い未対応の閉領域を注目する閉領域とする。この場合、閉領域１Ｐに対して、閉領域１Ｓとの間の境界線の長さは、隣接長さ２０１２−２０１３である。閉領域１Ｒとの間の隣接長さは、隣接長さ２０２１−２０２２である。閉領域１Ｔとの間の隣接長さは、隣接長さ２０２２−２０３１である。この場合、隣接長さ２０２１−２０２２が最も長いため、注目する未対応閉領域として、閉領域１Ｒが選択されることとなる。
【０１９３】
実施形態１を用いて、コスト計算を実施し、注目する閉領域１Ｒに対応する、原画２の閉領域として、閉領域２Ｒが特定される。
【０１９４】
上記のように、注目領域を更に変更する理由は、隣接長さが長い閉領域ほどその閉領域の境界線の長さは長い可能性が高く、境界線の長さが長い閉領域はその面積も大きい可能性が高いと考えられるため、より隣接長さの長い閉領域を選択することで、既対応の閉領域に隣接する閉領域のうち、より面積の大きな未対応の閉領域を、注目する閉領域としてより優先するためである。加えて、このようにすることによって、第１の原画において既対応の閉領域と未対応の閉領域との隣接長さが長いほど、第２の原画において対応する既対応の閉領域と対応する未対応の閉領域とが隣接している可能性が高くなることが挙げられる。このような、基準の既対応の閉領域への戻りを再帰的に行ってもよい。あるいは、上記のように１回だけ行ってもよい。なお、基準となる既対応の閉領域に隣接する、注目すべき閉領域がなくなった場合には、例えば、基準となる閉領域に隣接する既対応の閉領域のうちから、大きい順に、基準となる閉領域を変更してゆけばよい。
【０１９５】
上記の処理を行う場合には、注目する閉領域の順番は、例えば、閉領域１Ｒ、閉領域１Ｓ、閉領域１Ｔとなる。
【０１９６】
なお、閉領域１Ｓ、閉領域２Ｓ、閉領域１Ｑ、閉領域２Ｑ、閉領域１Ｐ、閉領域１Ｒは、それぞれ、第１の閉領域、第２の閉領域、第３の閉領域、第４の閉領域、第５の閉領域、第６の閉領域の一例である。
【０１９７】
図２１は、対応付けにおける初期の移動ベクトルを設定する例を示す図である。
【０１９８】
図２１において、閉領域１Ｒに対応する原画２に含まれる閉領域を探索する場合の例を示している。実施形態１では、閉領域１Ｒの位置から、閉領域１Ｒの位置を少しずつ動かしながら、順次コスト計算を行って、原画２における対応する閉領域を探索した。本実施形態では、コスト計算を行う初期の位置を、ベクトル１ＲＶだけずらした位置から開始するようにする。
【０１９９】
ベクトル１ＲＶは、例えば、次のようにして求める。すなわち、閉領域１Ｒに隣接する既対応の閉領域の移動ベクトル（１ＰＶ）をベクトル１ＲＶとするのである。あるいは、閉領域１Ｒに隣接する既対応の閉領域が複数存在する場合は、これらの複数の既対応の移動ベクトルを、面積加重をかけて平均してベクトル１ＲＶを求めてもよい。隣接関係がある閉領域は、略同じ方向に移動している確率が高いため、対応付けのコスト計算の開始位置を、閉領域１Ｒからベクトル１ＲＶだけ離れた位置から開始することが、例えば所定の閾値以下にコスト計算の値が収束するまでの計算時間を、より短くすることができる可能性が高くなる。なお、１ＲＶの求め方は、上記の例に限定されるものではない。例えば、閉領域１Ｒの周囲の一定の範囲に存在する既対応の領域の移動ベクトルの面積加重平均を計算して、１ＲＶを求めてもよい。コスト計算の値が所定の閾値以下になったところで、計算を打ち切ればよい。このような、コスト計算における初期の位置ベクトルを導入することにより、より少ない計算量で、閉領域の対応づけを行うことができる。なお、１ＱＧ、１ＰＧ、１ＲＧは、それぞれの閉領域の面積の重心である。重心は、各ベクトルの起点となるものであるが、ベクトルの起点は、重心に限られるものではない。
【０２００】
図２２は、注目する未対応の閉領域を選択する手順の例を示す図である。
【０２０１】
ステップＳ５００で、直近に対応関係が確定した領域を基準閉領域１Ｑとする。
【０２０２】
ステップＳ５０２で、基準閉領域１Ｑに隣接する未対応領域のうち、基準閉領域１Ｑと接する境界の長さが最長の閉領域１Ｓを求める。
【０２０３】
ステップＳ５０４で、閉領域１Ｓに隣接する閉領域であって、既に対応関係が確立している閉領域のうち、閉領域１Ｓと接する境界の長さが最長の隣接閉領域１Ｐが存在する場合、閉領域１Ｐを基準閉領域に採用する。存在しない場合は、基準閉領域１Ｑをそのまま基準閉領域として採用する。基準閉領域が閉領域１Ｐとなった場合は、基準閉領域１Ｐに隣接する未対応閉領域のうち、基準閉領域１Ｐと接する境界の長さが最長の閉領域１Ｒを求める。
【０２０４】
図２３は、対応先領域を求める一例を示す図である。
【０２０５】
ステップＳ６００で、基準閉領域１Ｐに隣接する未対応閉領域のうち、基準閉領域１Ｐと接する境界の長さが最長の閉領域１Ｒを求める。
【０２０６】
ステップＳ６０２で、閉領域１Ｒに隣接する全ての既に対応関係が確定した閉領域の移動ベクトルを面積加重平均し、探索のための初期の移動ベクトルδを求める。
【０２０７】
ステップＳ６０４で、閉領域１Ｒをδだけ移動させた位置からコスト計算を開始し、
コストが最小となるベクトルδ＊を求める。
【０２０８】
ステップＳ６０６で、閉領域１Ｒに隣接するすべての既に対応関係が確定した閉領域の移動ベクトルとδ＊とを面積加重平均し、δ＊を更新する。
【０２０９】
ステップＳ６０８で、閉領域１Ｒの重心１ＲＧをδ＊だけ移動させた点ｐを求める。
ステップＳ６１０で、Ｐが基準閉領域１Ｐに対応する閉領域２Ｐの隣接領閉域に含まれるかをチェックする。ステップＳ６１０のチェック結果が「はい」であれば、ステップＳ６１４に移動する。ステップＳ６１０のチェック結果が「いいえ」であれば、ステップＳ６１２に移動する。
【０２１０】
ステップＳ６１２で、閉領域２Ｐの隣接閉領域の中でｐとの距離が最短の重心２ＲＧを持つ領域２Ｒを選択し、δ＊を２ＲＧ−１ＲＧで更新する。
【０２１１】
ステップＳ６１４で、δ＊で移動させた領域１Ｒと重複する面積が最大の閉領域２Ｐの隣接閉領域を閉領域１Ｒの対応先閉領域とする。
【０２１２】
なお、上記のステップＳ６１０からステップＳ６１４は、閉領域１Ｐに対応する閉領域２Ｐに隣接する閉領域を、閉領域１Ｒの対応先の閉領域として特定するための一例である。
【０２１３】
図２４は、主成分分析を説明するための、一般的な図である。
【０２１４】
主成分分析は、複数の標本値から、特徴的な成分を表す方向（主成分方向）を抽出する手法であり、当業者に周知の手法である。図２４においては、複数のデータを二次元の直行する座標上にプロットした場合に、複数のデータの分散が一番大きい方向（主成分方向）を求めたグラフである。データの各々を主成分方向に観察することによって、データの各々の特徴をより顕著に把握することが可能となる。
【０２１５】
図２５は、主成分分析を用いて、複数の閉領域に包含された閉領域の対応付けの例を示す図である。
【０２１６】
図２５において、原画１の顔の閉領域に存在する２つの眉毛、二つの目、口は、顔の閉領域の最も外側の境界線に接しておらず、顔の閉領域が、眉毛、二つの目、口で構成される閉領域を包含している。原画２についても同様である。
【０２１７】
なお、原画１の顔の閉領域と原画２の顔の閉領域は、対応づけが終了しているものとする。また、両者の閉領域の中に包含される閉領域の数は、等しいものと仮定する。この場合に、対応する閉領域の各々に包含される複数の閉領域の各々の対応関係を見いだす手順の例を以下に示す。
【０２１８】
図２６は、対応する閉領域の各々に包含される複数の閉領域の各々の対応関係を見いだす手順の例を以下に示す図である。
【０２１９】
ステップＳ７００で、原画１の閉領域Ｍ１に包含される閉領域の重心ＭＧ１を求め、重心ＭＧ１を原点とする直行座標軸で、閉領域Ｍ１に包含される閉領域の各々の座標を求める。
【０２２０】
ステップＳ７０２で、原画１の閉領域Ｍ１に包含される閉領域の主成分方向Ｓ１を求める。
【０２２１】
ステップＳ７０４で、原画２の閉領域Ｍ２に包含される閉領域の重心ＭＧ２を求め、重心ＭＧ２を原点とする直行座標軸で、閉領域Ｍ２に包含される閉領域の各々の座標を求める。
【０２２２】
ステップＳ７０６で、原画２の閉領域Ｍ２に包含される閉領域の主成分方向Ｓ２を求める。
【０２２３】
ステップＳ７０８で、主成分方向Ｓ１及びＳ２を用いて、閉領域Ｍ１に包含される閉領域の各々に対応する閉領域Ｍ２に包含される閉領域の各々を求める。対応は、例えば、主成分方向を合わせた後に、相対的な座標位置の距離が近い閉領域同士を対応する閉領域とすればよい。
【０２２４】
なお、包含される閉領域の数が異なる場合には、最も外側の境界線に接触している内側の閉領域のうち、最も外側の境界線に接触している長さが著しく小さい領域を、包含される複数の閉領域に加えてもよい。このようにすることによって、包含される複数の閉領域の数を一致させることができる。
【符号の説明】
【０２２５】
Ｌａｂ  境界線
Ｌａｃ  境界線
Ｌｂｃ  境界線
Ｌｃｄ  境界線
Ｌｄｂ  境界線
Ｌｄｅ  境界線
Ｐ１２  削除する交点
Ｐ１１１  Ｐ１１の位置に設定される交点
Ｐ１１２  Ｐ１１の位置に設定される交点
【図１】
2018067103.tif 000003
【図２】
2018067103.tif 000004
【図３】
2018067103.tif 000005
【図４】
2018067103.tif 000006
【図５】
2018067103.tif 000007
【図６】
2018067103.tif 000008
【図７】
2018067103.tif 000009
【図８】
2018067103.tif 000010
【図９】
2018067103.tif 000011
【図１０】
2018067103.tif 000012
【図１１】
2018067103.tif 000013
【図１２】
2018067103.tif 000014
【図１３】
2018067103.tif 000015
【図１４】
2018067103.tif 000016
【図１５】
2018067103.tif 000017
【図１６】
2018067103.tif 000018
【図１７】
2018067103.tif 000019
【図１８】
2018067103.tif 000020
【図１９】
2018067103.tif 000021
【図２０】
2018067103.tif 000022
【図２１】
2018067103.tif 000023
【図２２】
2018067103.tif 000024
【図２３】
2018067103.tif 000025
【図２４】
2018067103.tif 000026
【図２５】
2018067103.tif 000027
【図２６】
2018067103.tif 000028
【手続補正書】
【提出日】平成29年8月18日(2017.8.18)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０１８９
【補正方法】変更
【補正の内容】
【０１８９】
この注目している未対応の閉領域１Ｓに注目して、たとえば、実施形態１を用いて、コスト計算を行い、コストが最小となる閉領域を、原画２の閉領域２Ｑに隣接する閉領域の中で探索する。この探索によって、閉領域１Ｓに対応する閉領域として、閉領域２Ｓが特定される。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０２０９
【補正方法】変更
【補正の内容】
【０２０９】
ステップＳ６０８で、閉領域１Ｒの重心１ＲＧをδ＊だけ移動させた点Ｐを求める。
ステップＳ６１０で、点Ｐが基準閉領域１Ｐに対応する閉領域２Ｐの隣接領閉域に含まれるかをチェックする。ステップＳ６１０のチェック結果が「はい」であれば、ステップＳ６１４に移動する。ステップＳ６１０のチェック結果が「いいえ」であれば、ステップＳ６１２に移動する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０２１０
【補正方法】変更
【補正の内容】
【０２１０】
ステップＳ６１２で、閉領域２Ｐの隣接閉領域の中で点Ｐとの距離が最短の重心２ＲＧを持つ領域２Ｒを選択し、δ＊を２ＲＧ−１ＲＧで更新する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０２１４
【補正方法】変更
【補正の内容】
【０２１４】
主成分分析は、複数の標本値から、特徴的な成分を表す方向（主成分方向）を抽出する手法であり、当業者に周知の手法である。図２４においては、複数のデータを二次元の直交する座標上にプロットした場合に、複数のデータの分散が一番大きい方向（主成分方向）を求めたグラフである。データの各々を主成分方向に観察することによって、データの各々の特徴をより顕著に把握することが可能となる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０２１９
【補正方法】変更
【補正の内容】
【０２１９】
ステップＳ７００で、原画１の閉領域Ｍ１に包含される閉領域の重心ＭＧ１を求め、重心ＭＧ１を原点とする直交座標軸で、閉領域Ｍ１に包含される閉領域の各々の座標を求める。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０２２１
【補正方法】変更
【補正の内容】
【０２２１】
ステップＳ７０４で、原画２の閉領域Ｍ２に包含される閉領域の重心ＭＧ２を求め、重心ＭＧ２を原点とする直交座標軸で、閉領域Ｍ２に包含される閉領域の各々の座標を求める。
【手続補正７】
【補正対象書類名】図面
【補正対象項目名】図２３
【補正方法】変更
【補正の内容】
【図２３】
2018067103.tif 000029
【手続補正書】
【提出日】平成29年11月9日(2017.11.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
一方の画像に含まれる複数の閉領域と、他方の画像に含まれる複数の閉領域とを、比較することによって、一方の画像の第１の閉領域に対応する、第２の閉領域を、他方の画像からコンピュータが特定する方法であって、前記一方の画像及び前記他方の画像の各々は、複数の画素で構成されており、前記複数の画素の各々は、特徴量を持ち、当該方法は、
前記第１の閉領域を選定するステップと、
前記第１の閉領域に含まれる複数の画素の各々が持つ特徴量と、前記他方の画像に含まれる複数の画素の各々が持つ特徴量とから、前記第１の閉領域と、前記他方の画像に含まれる複数の閉領域との近似の度合いを求めることで、前記他方の画像を探索するステップと、
前記一方の画像の第３の閉領域に、前記他方の画像の第４の閉領域が対応していることが既知であって、前記第１の閉領域が前記第３の閉領域と隣接している場合に、前記他方の画像に含まれる複数の閉領域であって、前記第４の閉領域に隣接する複数の閉領域のうち、前記近似の度合いが最も近似していることを示す１つの閉領域を、前記第２の閉領域に特定するステップと、
を有する方法であって、
前記選定するステップは、
前記第３の閉領域に接している閉領域が複数存在する場合、前記複数の接している閉領域のうち、前記第３の閉領域に接している長さがより長い閉領域を、前記第１の閉領域に特定するステップ、
を含む、方法。
【請求項２】
前記選定するステップは、
前記第３の閉領域に接している閉領域が複数存在する場合、前記複数の接している閉領域のうち、前記第３の閉領域に接している長さがより長い閉領域であって、前記他方の画像において、対応する閉領域が特定されていない閉領域を、前記第１の閉領域に特定するステップ、
を含む請求項１記載の方法。
【請求項３】
前記選定するステップは、
前記一方の画像に存在する第５の閉領域であって、前記他方の画像に含まれる閉領域との対応関係が特定されている第５の閉領域に対して前記第１の閉領域が隣接する長さが、前記第３の閉領域に対して前記第１の閉領域が隣接する長さよりも長い第５の閉領域に隣接する第６の閉領域であって、前記第５の閉領域に隣接する長さが、前記第５の閉領域に対して前記第１の閉領域が隣接する長さよりも長い、前記他方の画像に含まれる閉領域との対応関係が特定されていない第６の閉領域が存在する場合、前記第６の閉領域を、前記第１の閉領域に特定し直すステップ、
を更に含む請求項２記載の方法。
【請求項４】
前記近似の度合いを求めるステップは、
対応が既知である前記一方の画像の閉領域と前記他方の画像の閉領域の移動ベクトルを用いて、前記第１の閉領域に対応する、前記他方の画像における閉領域の前記探索を開始するための近似度を求める移動ベクトルの初期の値を決定するステップ、
を含む請求項１ないし３のうちいずれか１項記載の方法。
【請求項５】
前記第１の閉領域が、前記第１の閉領域の境界線に接しない第１の複数の閉領域を持つ場合であって、前記第２の閉領域が、前記第２の閉領域に接しない第２の複数の閉領域を持ち、前記第１の複数の閉領域の数と前記第２の閉領域の数が等しい場合、主成分分析を用いることで、前記第１の複数の閉領域の主成分方向と、前記第２の複数の閉領域の主成分方向を重ねることで得られる相対位置の関係に基づき、前記第１の複数の閉領域の各々と、前記第２の複数の閉領域の各々との対応付けを行うステップ、
を更に有する請求項１ないし４のうちいずれか１項に記載の方法。
【請求項６】
請求項１ないし５のうちいずれか１項に記載の方法を、コンピュータに実行させるプログラム。