(57)【要約】【課題】画像において顔面構成要素を取り替える方法を提供する。【解決手段】顔面を含むオリジナル画像内に顔面特徴テンプレート画像をクローン作成して新画像を形成する方法。本方法は、オリジナル画像内の顔面及び顔面特徴を検出する段階と、オリジナル画像及びテンプレート画像を縮小する段階と、縮小されたテンプレート画像を縮小されたオリジナル画像内にクローン作成して新画像を形成する段階と、新画像を拡大する段階と、拡大された新画像を表示する段階とを含む。本方法は、得られる連立１次方程式が、トーマスアルゴリズムを適用して初期解を求め、初期解を使用する「共役勾配」アルゴリズムを適用して連立１次方程式の最終的な解を求めることによって解かれるポアソンクローニングを使用することができる。【選択図】図１
2008204466.tif 000002
【特許請求の範囲】
【請求項１】
顔面を含むオリジナル画像内に顔面特徴のテンプレート画像をクローン作成し、該顔面特徴を備えた該顔面の新画像を形成する方法であって、
オリジナル画像の顔面及び顔面特徴を検出する段階と、
前記オリジナル画像とテンプレート画像及びテンプレートマスクを有するテンプレートとのサイズを縮小する段階と、
前記縮小されたテンプレートマスクと前記縮小されたオリジナル画像上の前記顔面特徴の位置とに基づく位置において、該縮小されたオリジナル画像内に前記縮小されたテンプレート画像をクローン作成して新画像を形成する段階と、
前記新画像を拡大する段階と、
前記拡大された新画像を表示する段階と、
を含むことを特徴とする方法。
【請求項２】
前記顔面特徴に基づく位置において前記縮小されたオリジナル画像内に前記縮小されたテンプレート画像をクローン作成して前記新画像を形成する前記段階は、
前記顔面特徴の位置に基づく前記位置において前記縮小されたオリジナル画像上に前記縮小されたテンプレートマスクを配置し、該縮小されたオリジナル画像内に前記縮小されたテンプレート画像をクローン作成するクローニング区域を判断する段階と、
ポアソンクローニングを適用して、前記クローニング区域において前記縮小されたオリジナル画像内に前記縮小されたテンプレート画像をクローン作成して前記新画像を形成する段階と、
を含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記新画像を拡大する前記段階は、
前記新画像を直接拡大して、オリジナル画像での前記テンプレート画像に適合させ、該拡大された画像が既知のピクセル間のピクセルを欠落している段階と、
前記拡大された新画像の前記クローニング区域における前記既知のピクセルを前記テンプレート画像における対応するピクセルから差し引いて第１の差分画像を形成する段階と、
前記第１の差分画像に双１次内挿を適用して、該第１の差分画像の前記欠落したピクセルを満たす段階と、
前記テンプレート画像に前記第１の差分画像を付加し、前記拡大された新画像の第１の部分を形成する段階と、
前記拡大された新画像の前記クローニング区域の外側の前記既知のピクセルを前記オリジナル画像内の対応するピクセルから差し引いて第２の差分画像を形成する段階と、
前記第２の差分画像に双１次内挿を適用して、該第２の差分画像の前記欠落したピクセルを満たす段階と、
前記オリジナル画像に前記第２の差分画像を付加して、前記拡大された新画像の第２の部分を形成する段階と、
を含む、
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記新画像を拡大する前記段階の後で、かつ前記拡大された新画像を表示する前記段階の前に、
前記拡大された新しいものの前記第１及び前記第２の部分の間の欠落したピクセルの境界辺縁部内に前記テンプレート画像の一部分をそのオリジナルサイズでクローン作成する段階、
を更に含む、
ことを特徴とする請求項３に記載の方法。
【請求項５】
前記拡大された新画像の前記第１及び前記第２の部分の欠落したピクセルの境界辺縁部内に前記テンプレート画像の一部分をそのオリジナルサイズでクローン作成する前記段階は、
ポアソンクローニングを適用して、前記拡大された新画像の前記第１及び前記第２の部分の間の前記境界辺縁部内に前記テンプレート画像の前記部分をクローン作成する段階、
を含む、
ことを特徴とする請求項４に記載の方法。
【請求項６】
前記目標画像における前記交換顔面特徴とオリジナルコンテンツとの間の境界を平滑化する段階、
を更に含むことを特徴とする請求項４に記載の方法。
【請求項７】
境界を平滑化する前記段階は、
ポアソンクローニングを適用して、画像の境界内の全ピクセルが値０を有して画像内の境界の外側の全ピクセルが値２５５を有する目標画像内に、画像内の全ピクセルが値０を有するソース画像をクローン作成してアルファ画像を形成する段階と、
前記アルファ画像を使用して、前記拡大されたオリジナル画像とオリジナルサイズでの前記テンプレート画像とを融合させて前記新画像を形成する段階と、
を含む、
ことを特徴とする請求項６に記載の方法。
【請求項８】
ポアソンクローニングを適用する前記段階は、
連立１次方程式を作成する段階と、
トーマスアルゴリズムを適用して初期解を求める段階と、
前記初期解を使用する「共役勾配」アルゴリズムを適用して、前記連立１次方程式に対する最終的な解を求める段階と、
を含む、
ことを特徴とする請求項２、請求項５、又は請求項７に記載の方法。
【請求項９】
トーマスアルゴリズムを適用する前記段階は、
行に関して前記連立１次方程式に対する第１の解を求める段階と、
列に関して前記連立１次方程式に対する第２の解を求める段階と、
前記第１及び前記第２の解を平均して前記初期解を作り出す段階と、
を含む、
ことを特徴とする請求項７に記載の方法。
【請求項１０】
「共役勾配」アルゴリズムを適用する前記段階は、ブロック行列演算を適用して前記連立１次方程式に対する前記最終的な解を求める段階を含むことを特徴とする請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
本出願は、共に内容全体が引用により組み込まれ、かつ本出願人に譲渡された２００５年１２月３１日出願の代理人整理番号ＡＲＣ−Ｐ１４９である「モバイル装置上の顔面検出」という名称の米国特許出願出願番号第１１／３２３、６５３号、及び代理人整理番号ＡＲＣ−Ｐ１５５である「モバイル装置上の顔面特徴検出」という名称の米国特許出願出願番号第１１／３２３、６５４号に関連するものである。
本発明は、画像において顔面構成要素を交換する方法に関する。
【背景技術】
【０００２】
ポアソンクローニング／調合は、ソース画像を目標画像に挿入及び調合するツールである。ポアソンクローニングは、勾配領域とも呼ばれる変化の空間において行われる。クローニングの後、この変化は、画像内に再び取り込まれる。「Ａｄｏｂｅ  Ｐｈｏｔｏｓｈｏｐ」には、バージョン７．０以来「Ｈｅａｌｉｎｇ  Ｂｒｕｓｈ」と呼ばれる機能にポアソンクローニングが含まれている。
本特許又は出願ファイルは、カラーで作成された少なくとも１つの図面を含む。カラー図面付きの本特許又は特許出願公報の写しは、請求及び必要な手数料の支払いにより特許庁によって提供されることになる。
異なる図における同じ参照番号の使用は、類似又は同一要素を表している。
【０００３】
【特許文献１】米国特許出願出願番号第１１／３２３、６５３号
【特許文献２】米国特許出願出願番号第１１／３２３、６５４号
【非特許文献１】Ｐａｔｒｉｃｋ  Ｐｅｒｅｚ他著「ポアソン画像編集法」、マイクロソフト・リサーチＵＫ、２００３年
【発明の開示】
【課題を解決するための手段】
【０００４】
本発明の一実施形態では、顔面を含むオリジナル画像内に顔面特徴テンプレート画像をクローン作成して新画像を形成する方法を提供する。本方法は、オリジナル画像内の顔面及び顔面特徴を検出する段階と、オリジナル画像及びテンプレート画像を縮小する段階と、縮小されたテンプレート画像を縮小されたオリジナル画像内にクローン作成して新画像を形成する段階と、新画像を拡大する段階と、拡大された新画像を表示する段階とを含む。一実施形態では、本方法は、得られる連立１次方程式が、トーマスアルゴリズムを適用して初期解を求め、初期解を使用する「共役勾配」アルゴリズムを適用して連立１次方程式の最終的な解を求めることによって解かれるポアソンクローニングを使用する。
【発明を実施するための最良の形態】
【０００５】
図１は、本発明の一実施形態において目標画像の特徴をソース画像からの交換特徴と取り替える方法１００の流れ図である。一実施形態では、方法１００は、ユーモラスな写真を作成するために写真内の個人の顔面特徴を交換顔面特徴と取り替える。方法１００は効率的であり、そのためにそれは、ＡＲＭ９プロセッサを備えた携帯電話のような限られたＲＡＭ及び計算機能を備えた移動式及び手持ち式装置上のプロセッサで実行されるソフトウエアによって実施することができる。
【０００６】
段階１０１において、装置は、オリジナル画像２００を取り込み、又はその他の方法で受け取る（図２）。段階１０１に、段階１０２が続く。
段階１０２において、装置は、オリジナル画像２００の顔面２０２と、顔面２０２から顔面特徴とを検出する。顔面特徴は、顔面特徴点２０４（１つだけに番号を付けている）によって特定されている。顔面２０２及び顔面特徴点２０４を検出するための詳細は、本出願人に譲渡され、かつ内容全体が引用により組み込まれている２００５年１２月３１日出願の米国特許出願出願番号第１１／３２３、６５３号及び第１１／３２３、６５４号に説明している。装置は、新画像４００を作成するために顔面特徴を交換又は挿入することができるオリジナル画像２００上の領域（すなわち、区域）を特定するために、顔面特徴点２０４を後で使用する（図４）。顔面特徴は、髪、眉、目、耳、口、及び口ひげとすることができる。段階１０２に、段階１０３が続く。
【０００７】
段階１０３において、装置は、いくつかの顔面特徴テンプレートの１つを選択するようにユーザに促す。それに応答して、装置は、顔面特徴テンプレート３００の選択を受け取る（図３）。テンプレート３００は、顔面特徴のテンプレートマスク３０２及びテンプレート画像３０４を含む。装置は、後でテンプレートマスク３０２及び顔面特徴点２０４を使用して、ソース画像３０４でクローン作成される目標画像２００上の区域を特定する。段階１０３に、段階１０４が続く。
【０００８】
段階１０４において、装置は、新画像４００（図４）を作成するために、スマートクローニングを適用して、テンプレート３００の顔面特徴をオリジナル画像２００内に交換又は挿入する。第１に、装置は、顔面特徴点２０４とテンプレート３００の顔面特徴タイプとの間の所定の関係に基づいて、テンプレートマスク３０２をオリジナル画像２００上に配置する。次に、装置は、テンプレート画像３０４をオリジナル画像２００上のテンプレートマスク３０２によって特定された区域内にクローン作成する。装置は、オリジナル画像２００及びテンプレート画像３０４のカラーを適合させるために、自然にかつ継ぎ目なくクローニングを行う。スマートクローニングは、後に詳細に説明するポアソンクローニング９００（図９）を利用する方法１０００（図１０）に基づいている。
【０００９】
図５から図８は、スマートクローニング方法８００が必要な理由を示している。図５及び図６は、ユーザが別の画像５０２に挿入したい画像６０４の一部分６０２を示している。図７は、部分６０２の画像５０２への直接切り貼りを示している。得られた画像７０２は、画像５０２と部分６０２との間のカラーの違いが極めて明確に見えるので望ましくない。図８は、部分６０２の画像５０２へのスマートクローニングを示している。得られた画像８０２は、画像５０２と部分６０２が自然にかつ継ぎ目なく組み合わされることを示している。
【００１０】
図９は、ポアソンクローニングの方法９００において使用される記号を示しており、Ｓは、画像定義領域（すなわち、目標画像）であり、Ωは、境界∂Ωを有するＳの閉じた部分集合（すなわち、領域の周りに境界を有する、ソース画像でクローン作成される目標画像内の領域）であり、ｆ*は、Ｓから領域Ωの内部を差し引いた領域上に定められるスカラー関数（すなわち、クローン作成される領域を除いた目標画像の値）であり、ｆは、領域Ωの内部上に定められる未知のスカラー関数（すなわち、クローン作成される領域内の値）であり、ｇは、ソース関数（すなわち、目標画像内にクローン作成されるソース画像の値）であり、ｖは、ソース関数ｇのΩ上に定められるベクトル場である。この実施例において、ベクトル場ｖは、ソース関数ｇの勾配場である。ソース画像及び目標画像を自然にかつ継ぎ目なく組み合わせるために、結果関数ｆは、次式のように求められるべきである。
【００１１】
2008204466.tif 000003
【００１２】
方程式（１）は、ポアソン方程式の形式を有し、従って、本方法は、ポアソンクローニングと名付けられている。ポアソンクローニングの方法９００は、カラー画像がクローン作成される時に３つのカラーチャンネルの各々に対して別々に行われることに注意されたい。
【００１３】
個別の画像に関して、問題は、下に重なる離散ピクセル格子を使用して自然に離散化することができる。一般性を失うことなく、同じ記号は、連続的なオブジェクト及びそれらの個別の対応物に関して使用される。すなわち、領域Ｓ及びΩは、ここで無限離散格子上に定められる有限の点集合になる。領域Ｓは、画像の全ピクセル又はそれらの部分集合のみを含むことができることに注意されたい。領域Ｓ内の各ピクセルｐに関して、ＮPは、領域Ｓ内にあるその４接続近傍の集合であり、＜ｐ、ｑ＞は、ｑ∈ＮPであるようなピクセルの対を示し、境界∂Ωは、ここで｛ｐ∈＼Ω：ＮP∩Ω≠０｝に等しく、ｆPは、ピクセルｐにおける結果関数ｆの値である。更に導出すると、連立１次方程式は、次式のようになる。
【００１４】
2008204466.tif 000004
（２）
【００１５】
ここで、λ1は、ベクトル場ｖの作用を制御するためのパラメータである。ベクトル場ｖが、ソース関数ｇの勾配場である時には、ｖpq＝ｇp−ｇqになる。領域Ωの内部上に定められた結果関数ｆ（すなわち、クローン作成される領域内のピクセル値）を判断するために、この連立１次方程式を繰返し解くことができる。ポアソンクローニングに関するより詳細に関しては、Ｐａｔｒｉｃｋ  Ｐｅｒｅｚ他著「ポアソン画像編集法」、マイクロソフト・リサーチＵＫ、２００３年を参照されたい。
【００１６】
図１０は、本発明の一実施形態におけるスマートクローニング段階１０４（図１）において使用されるポアソンクローニングを備えた方法１０００の流れ図である。図１１Ａ、図１１Ｂ、及び図１１Ｃは、自然かつ継ぎ目のない方法でテンプレート画像３０４をオリジナル画像２００内にクローン作成する方法１０００の適用を示している。ポアソンクローニングを備えたスマートクローニング段階１０４をより詳細に説明するために、これ以降、図１０、図１１Ａ、図１１Ｂ、及び図１１Ｃを合わせて使用する。
【００１７】
図１０及び図１１Ａの段階１００２において、プロセッサは、オリジナル画像２００のサイズを縮小してオリジナル画像２００’を作成する。プロセッサはまた、テンプレート３００のテンプレートマスク３０２及びテンプレート画像３０４を縮小して、画像２００’のサイズに適合するテンプレートマスク３０２’及びテンプレート画像３０４’を作成することができる。一実施形態では、プロセッサは、段階サイズ４を使用するダウンサンプリングによって画像サイズを縮小する。段階１００２に、段階１００４が続く。
【００１８】
図１０及び図１１Ａの段階１００４において、プロセッサは、ポアソンクローニングを適用して、テンプレート画像３０４’をオリジナル画像２００’内にクローン作成し、新画像４００’を作成する。この段階におけるポアソンクローニングに関して、領域Ｓは、オリジナル画像２００’であり、領域Ωは、オリジナル画像２００’上のテンプレートマスク３０２’によって定められた領域であり、目標関数ｆ*は、領域Ωを除くオリジナル画像２００’のピクセル値であり、ソース関数ｇは、テンプレート画像３０４’のピクセル値である。一実施形態では、ポアソンクローニングにおいて作り出された連立１次方程式（２）は、後に詳細に説明する方法１２００を使用して繰返し解かれる。段階１００４に、段階１００６が続く。
【００１９】
図１０及び図１１Ｂの段階１００６において、プロセッサは、新画像４００’を拡大して、テンプレート３００の原寸に適合する新画像４００”を作成する。一実施形態では、プロセッサは、差分内挿アルゴリズムを使用して、部分３０４’及びそのソースであるテンプレート画像３０４の既知のピクセルから新画像４００’内の部分３０４’を拡大し、新画像４００”内の部分３０４”を作成する。プロセッサは、オリジナル画像２００からのピクセルで、拡大された新画像４００’内の対応するピクセルを満たすことにより、新画像４００’の残りを拡大し、拡大された新画像４００”の部分２００”を作成する。
【００２０】
図１１Ｄは、差分内挿アルゴリズムが部分３０４’を部分３０４”に拡大する方法を示している。第１に、プロセッサは、拡大される部分３０４’の結果が、その新サイズにおける既知のピクセル間のピクセルを欠落させるように、部分３０４’を画像３０４のサイズまで直接拡大する。次に、プロセッサは、拡大された部分３０４’の既知のピクセルをテンプレート画像３０４内の対応するピクセルから差し引き、差分画像１１１４を作成し、そこで、既知のピクセル差分を円で示し、欠落したピクセルを垂直及び水平格子線間の交点として示している。プロセッサは、差分画像１１１４に双１次内挿を適用し、差分画像１１１４内の欠落したピクセルを満たす。次に、この処理は、内挿された差分画像１１１４を画像３０４に付加し、部分３０４”を形成する。
【００２１】
欠落したピクセルを有する境界辺縁部１１０２が新画像４００”内の部分２００”と３０４”の間に存在し、これらのピクセルは、部分３０４’又は新画像２００’の残りのいずれにも属さないことに注意されたい。図１０及び図１１Ｂを再び参照すると、プロセッサは、ポアソンクローニングを適用して、新画像４００”の境界辺縁部１１０２内にテンプレート画像３０４の一部分をクローン作成し、新画像４００’’’を作成する。この段階におけるポアソンクローニングに関して、領域Ｓは、オリジナル画像２００”であり、領域Ωは、境界辺縁部１１０２であり、目標関数ｆ*は、領域Ωを除くオリジナル画像２００”のピクセル値であり、ソース関数ｇは、テンプレート画像３０４のピクセル値である。一実施形態では、ポアソンクローニングにおいて作り出された連立１次方程式（２）は、後に詳細に説明する方法１２００を使用して繰返し解かれる。段階１００６に、段階１００８が続く。
【００２２】
図１０及び図１１Ｃの段階１００８において、プロセッサは、ポアソンクローニングを使用して、アルファ画像１１１０を作成することにより、新画像４００’’’上のテンプレートマスク３０２によって定められた境界１１０４（図１１Ｂ）を滑らかにし、次に、アルファ画像１１１０を使用して、新画像４００’’’とオリジナル画像２００とを組み合わせて新画像４００を作成する。
この段階におけるポアソンクローニングに関して、領域Ｓは、新画像４００”と同じサイズを有する画像１１０６であり、領域Ωは、領域Ｓ上に配置されたテンプレートマスク３０２の境界であり、目標関数ｆ*は、テンプレートマスク３０２内の全ピクセルが０に設定され、かつテンプレートマスク３０２外の全ピクセルが２５５に設定された領域Ｓ上に定められたスカラー関数であり、ソース関数ｇは、全ピクセルが０に設定された画像１１０８である。一実施形態では、ポアソンクローニングにおいて作り出された連立１次方程式（２）は、後に詳細に説明する方法１２００を使用して繰返し解かれる。図に示すように、得られたアルファ画像１１１０は、ピクセルが内側の０から外側の２５５まで滑らかに変化する灰色の境界１１１２を有する。
【００２３】
アルファ画像１１１０を使用した新画像４００’’’とオリジナル画像２００の結合は、以下の公式によって達成される。
Ｒ＝（Ｉ1＋αｉ2）／２５５                                  （２．５）
ここで、Ｒは、新画像４００であり、Ｉ1は、新画像４００”であり、αは、アルファ画像１１１０であり、Ｉ2は、オリジナル画像２００である。アルファ画像１１１０内の灰色境界１１１２の滑らかな変化は、新画像４００内の滑らかな境界１１０４を提供する。
【００２４】
ポアソン方程式の解法
１００*１００ピクセルのサイズを有するテンプレート画像に関して、ポアソンクローニングは、１００*１００の１次方程式（２）の連立に帰すると考えられる。１次方程式のこの数は、特に、限られたＲＡＭ及び計算機能を有する移動式又は手持ち式装置に対しては計算上極めて過酷である。この連立式を迅速に解くために、２つの戦略が採用されている。第１に、上述のように、装置は、縮小されたテンプレート画像及びオリジナル画像にスマートクローニングを適用する。第２に、以下に説明するように、装置は、以下で「ブロック・トーマス−ＣＧ」と呼ぶ新規性のある方法１２００を適用して連立１次方程式（２）を解く。
【００２５】
図１２は、本発明の一実施形態における方法１２００の流れ図を示している。段階１２０２において、装置は、従来のトーマスアルゴリズムを適用し、連立１次方程式（２）を最初は行に関して、次に列に関して解く。次に、装置は、行に関する解と列に関する解を平均して、連立１次方程式（２）に対する初期解を作り出す。
行に関して連立式を解く時、ピクセルｐは、座標（ｘ、ｙ）を有し、近傍ＮPは、半径１を有する行区間（すなわち、行の３つの隣接するピクセルの近傍）である。全てのｘ∈（ａ、ｂ）及び全てのｉ＝−１、０、１に対して、行ｙ上の各接続した行区間Ω＝（ａ、ｂ）、∂Ω＝ａ又はｂに関して、１次方程式（２）は、次式のようになる。
【００２６】
2008204466.tif 000005
（３）
【００２７】
この連立式は、ＡＸ＝Ｙと同等であり、ここで、以下の通りである。
【００２８】
2008204466.tif 000006
（４）
【００２９】
行列Ａは、三重対角行列であるので、装置は、トーマスアルゴリズムを使用することによってこの連立式を解くことができる。更に、トーマスアルゴリズムは、僅かなメモリしか必要としない高速計算のために単なる加算、減算、及び桁送り演算で実施することができる。
【００３０】
列に関して連立式を解く時、近傍ＮPは、半径１を有する列区間（列の３つの隣接するピクセルの近傍）である。全てのｙ∈（ａ、ｂ）及び全てのｉ＝−１、０、１に対して、行ｘ上の各接続した列区間Ω＝（ａ、ｂ）、∂Ω＝ａ又はｂに関して、１次方程式（２）は、次式のようになる。
【００３１】
2008204466.tif 000007
（５）
【００３２】
この連立式もＡＸ＝Ｙと同等であり、ここで、Ａは、三重対角行列である。従って、装置は、単なる加算、減算、及び桁送り演算で実施されるトーマスアルゴリズムを使用してこの連立式を解くことができる。装置は、行に関して計算された解と列に関して計算された解との平均値として最終的な解を求める。この最終的な解は、段階１２０４におけるブロック「共役勾配（ＣＧ）」法に対しては初期解になる。
【００３３】
段階１２０４において、装置は、行及び列の両方を一緒に考慮する。１次方程式（２）は、ＡＸ＝Ｙの形式で書き換えられ、ここで、行列Ａは、次式のような対称ブロック行列として書かれる。
【００３４】
2008204466.tif 000008
（６）
【００３５】
行列Ａの全ての行は、テンプレートマスク内の対応する行を示している。各Ａiは、次式のように示される。
【００３６】
2008204466.tif 000009
2008204466.tif 000010
（７）
【００３７】
ここで、各Ａijは、上記の通りであり、各Ｃiは、Ｂi-1の転置であり、各Ｃiは、次式のように示すことができる。
【００３８】
2008204466.tif 000011
2008204466.tif 000012
（８）
【００３９】
ここで、各Ｃijは、上記の通りであり、特殊な左側行列は、テンプレートマスクによって判断されることになる。それは、依然として十分に規則的であるので、装置は、小さいメモリ内に左側行列を保存することができる。より具体的には、行列Ａijは、単純な２次元配列（行列形式、行列長）として説明され、極めて僅かなメモリ空間を使用して保存することができる。次に、装置は、ブロックＣＧ法１３００（図１３）を適用してこれらの方程式を解決する。
【００４０】
図１３は、本発明の一実施形態におけるブロックＣＧ法１３００の流れ図である。方法１３００は、段階１３０６、段階１３１０、段階１３１６、段階１３１８、段階１３２０、段階１３２４、段階１３２６、段階１３３０、及び段階１３３６における行列演算がブロック行列演算に分解されることを除いては、従来のＣＧ法に類似している。
ブロックＣＧ法１３００は、僅かなメモリしか必要としない高速計算のために単なる加算、減算、及び桁送り演算で実施することができる。更に、ブロックＣＧ法１３００は、ブロックＣＧ法１３００が数回の反復（例えば、典型的には２０よりも少ない反復）で満足するクローニング結果を迅速に見つけることになるように、段階１２０２のトーマスアルゴリズムから求められた初期解Ｘで開始する。一実施形態では、最大ループ数Ｎは、１０に設定され、満足する結果を求めるための閾値イプシロンは、０．０００００１に設定される。
開示した実施形態の特徴の様々な他の適応及び組合せは、本発明の特許請求の範囲である。特許請求の範囲は、多数の実施形態を包含している。
【図面の簡単な説明】
【００４１】
【図１】本発明の一実施形態においてオリジナル画像内に顔面特徴テンプレート画像をクローン作成するスマートクローニング方法の流れ図である。
【図２】本発明の一実施形態における特定された顔面及び顔面特徴を有するオリジナル画像を示す図である。
【図３】本発明の一実施形態におけるテンプレートマスク及びテンプレート画像を有する顔面特徴テンプレートを示す図である。
【図４】本発明の一実施形態において図１のスマートクローニング方法を図２のオリジナル画像及び図３のテンプレートに適用した結果を示す図である。
【図５】本発明の一実施形態において図１のスマートクローニング方法によって処理されたカラー変化を示す図である。
【図６】本発明の一実施形態において図１のスマートクローニング方法によって処理されたカラー変化を示す図である。
【図７】本発明の一実施形態において図１のスマートクローニング方法によって処理されたカラー変化を示す図である。
【図８】本発明の一実施形態において図１のスマートクローニング方法によって処理されたカラー変化を示す図である。
【図９】本発明の一実施形態における図１のスマートクローニング方法において使用されるポアソンクローニングにおける記号を示す図である。
【図１０】本発明の一実施形態の図１のスマートクローニング方法におけるスマートクローニング段階の流れ図である。
【図１１Ａ】本発明の一実施形態における図１０のスマートクローニング段階の適用を示す図である。
【図１１Ｂ】本発明の一実施形態における図１０のスマートクローニング段階の適用を示す図である。
【図１１Ｃ】本発明の一実施形態における図１０のスマートクローニング段階の適用を示す図である。
【図１１Ｄ】本発明の一実施形態における差分内挿法の適用を示す図である。
【図１２】本発明の一実施形態において図１０のスマートクローニング段階で作り出されたポアソンクローニングからの連立１次方程式を解くための「ブロック・トーマス−共役勾配（ＣＧ）」法の流れ図である。
【図１３】本発明の一実施形態において図１２の「ブロック・トーマス−ＣＧ勾配」法で使用される「ブロック共役勾配」アルゴリズムの流れ図である。
【符号の説明】
【００４２】
１００  一実施形態における本発明の方法
１０１  方法の段階
【図１】
2008204466.tif 000013
【図１０】
2008204466.tif 000014
【図１１Ａ】
2008204466.tif 000015
【図１１Ｂ】
2008204466.tif 000016
【図１１Ｃ】
2008204466.tif 000017
【図１２】
2008204466.tif 000018
【図１３】
2008204466.tif 000019
【図２】
2008204466.tif 000020
【図３】
2008204466.tif 000021
【図４】
2008204466.tif 000022
【図５】
2008204466.tif 000023
【図６】
2008204466.tif 000024
【図７】
2008204466.tif 000025
【図８】
2008204466.tif 000026
【図９】
2008204466.tif 000027
【図１１Ｄ】
2008204466.tif 000028
【外国語明細書】
2008204466.tif 000029
2008204466.tif 000030
2008204466.tif 000031
2008204466.tif 000032
2008204466.tif 000033
2008204466.tif 000034
2008204466.tif 000035
2008204466.tif 000036
2008204466.tif 000037
2008204466.tif 000038
2008204466.tif 000039
2008204466.tif 000040
2008204466.tif 000041
2008204466.tif 000042
2008204466.tif 000043
2008204466.tif 000044
2008204466.tif 000045
2008204466.tif 000046
2008204466.tif 000047
2008204466.tif 000048
2008204466.tif 000049
2008204466.tif 000050
2008204466.tif 000051