WO2006106863A1

WO2006106863A1 - 画像処理システムおよび画像処理プログラム

Info

Publication number: WO2006106863A1
Application number: PCT/JP2006/306727
Authority: WO
Inventors: Takeo Igarashi
Original assignee: University of Tokyo NUC
Current assignee: University of Tokyo NUC
Priority date: 2005-04-01
Filing date: 2006-03-30
Publication date: 2006-10-12
Anticipated expiration: 2007-10-01
Also published as: US20090213143A1; EP1865467B1; US8063917B2; JP4613313B2; CN101147172A; EP1865467A1; EP1865467A4; JP2006285765A; CN101147172B

Abstract

　著しく短い処理時間で、オブジェクトが自然に変形できる。画像処理システム１０は、三角形メッシュにおける固定すべき点および移動される点を含む、複数のハンドル位置を示す情報に基づいて、オリジナル形状の三角形メッシュについて、その回転および拡大／縮小を許容しつつ、オリジナル三角形メッシュと、処理後の中間的な三角形メッシュとの間の差異を表現した２次の誤り計量が最小となるような、中間的な三角形メッシュのデータを生成する第１のメッシュ生成部３６と、中間的な三角形メッシュについて、その回転および平行移動を許容しつつ、不均一な歪、伸縮および拡大／縮小を許容しない状態で、中間的な三角形メッシュと、最終的な三角形メッシュとの間の差異を表現した誤り計量が最小となるような、最終的な三角形メッシュのデータを生成する第２のメッシュ生成部３８と、を備える。

Description

明細書

画像処理システムおよび画像処理プログラム

技術分野

[0001] 本発明は、表示されたオブジェクトを自在に変形させることができる画像処理装置および画像処理プログラムに関する。

背景技術

[0002] 画像中の 2次元のオブジェクトを、ユーザの指示にしたがって操作する、たとえば、移動、回転、伸縮、曲げるための技術が提案されている。従来、このような操作のために、画像中のオブジェクトを三角形のメッシュで仕切り、そのメッシュを変形させることで、オブジェクトを変形させていた。

[0003] 形状を操作する手法として、予め定義されたスケルトンを利用することが知られている。ユーザが、スケルトンの形状を操作すると、画像処理システムが、操作されたスケルトンの形状にしたがって、全体の形状を調整する。し力しながら、スケルトン形状の定義は、簡単な処理ではなぐアメーバのような明瞭なスケルトン構造をもたないォブジェタトに対しては有効ではな、と、う問題点があった。

[0004] 他の公知の手法として、フリー'フォーム 'デフォーメーシヨン（Free Form Deformati on: FFD)が知られている。ユーザが、空間を複数のドメインに分割し、かつ、各ドメインを定義する制御ポイントを動かすことによりドメインを操作する。し力しながら、 FFD の設定は面倒であり、ユーザは、数多くの頂点を手動で操作する必要があるという問題点があった。

非特許文献 1： "ラプラシアン'サーフェイス ·エディティング（Laplacian SurfaceEditing) " (オルガ'ソルキネ (Orga Solkine)他著、ユーログラフィクス ZACM SIGGRAPH シンポジウム（Eurographics/ACM SIGGRAPH Symposium)、 179— 188)、 [on line ] , 2004年 7月 9日、 [平成 17年 2月 23日検索]、インターネット、 <URL:http://ww w— sop.inna.fr/ geometnca/ events/ sgp2004/ program.html

発明の開示

発明が解決しょうとする課題 [0005] 非特許文献 1には、 2次元オブジェクトを構成する三角形メッシュのそれぞれを拡大 Z縮小、回転させて、新たな三角形メッシュを生成し、新たな三角形メッシュに基づく 2次元オブジェクトを表示させる手法が提案されて、る。

[0006] この場合にも、オブジェクトの変形が自然であり、かつ、その処理時間が短いようなシステムやプログラムが望まし、。

[0007] 本発明は、オブジェクトが自然に変形でき、かつ、その処理時間も著しく短い画像処理システムおよび画像処理プログラムを提供することを目的とする。課題を解決するための手段

[0008] 本発明は、スケルトンや FFDを用いずに、形状を操作する手法を提供する。ユーザは、ハンドルとして、オブジェクトの内側に複数のポイントを設定し、これらハンドルを所望の位置に移動させる。

[0009] 次いで、画像処理システムは、局所的な形状のひずみを最小化させつつ、与えられたノヽンドルの位置にしたがって、全体の形状を変形させる。本発明に力かる手法によれば、オブジェクトの形状を自然に変形することができ、かつ、従来のオブジェクトの埋め込まれた空間自体を歪ませる手法と比較して、処理結果、つまり、オブジェクトの動きは、実際の世界でのオブジェクトの振る舞いに近、ものとなる。

[0010] 本発明においては、歪を最小限にするために、形状の構成を見出すために、基本的には、 2つのステップの閉じた (繰り返し演算に頼らず一通りの計算で結果がでる）アルゴリズムが設けられる。従来の手法では、物理ベースのシミュレーション、あるいは、非線形の最適化が用いられていた。しかしながら、ユーザとの間の対話的な操作 (インタラクション)では、これらの手法は低速である。

[0011] キーポイントは、二次の誤り計量を適切に設計して、最小化の問題を、線形の連立方程式として定式ィ匕することにある。インタラクションの冒頭で連立方程式を解くことにより、画像処理システムは、単一の行列の乗算により解を見出すことができる。理想的には、ある形状の全ての属性を取り扱うような単一の二次の誤り関数を有するのが望ましいが、このような単一の誤り関数を設計することは困難である。そこで、本発明においては、上記最小化の問題点を、回転方向の問題と、大きさの問題とに分けた。これにより、本発明では、問題は、二つの最小二乗法の最小化の問題に分解され、それぞれが順番に解かれる。

[0012] より詳細には、本発明の目的は、変形すべきオブジェクトを構成する三角形メッシュのデータ力なるオリジナル形状データが記憶された記憶装置を有する画像処理システムにおいて、

前記入力装置からの、前記画像中の前記三角形メッシュにおける固定すべき点および移動される点を含む、複数のハンドル位置を示す情報に基づいて、前記オリジナル形状データを前記記憶装置から読み出して、当該オリジナル形状データが示すそれぞれのオリジナル三角形メッシュにつ、て、その回転および拡大 Z縮小を許容しつつ、オリジナル三角形メッシュと、処理後の中間的な三角形メッシュとの間の差異を表現した 2次の誤り計量が最小となるような、中間的な三角形メッシュのデータからなる中間的メッシュデータを生成し、前記記憶装置に記憶する第 1のメッシュ生成手段と、

前記中間的メッシュデータが示すそれぞれの中間的な三角形メッシュにつ、て、その回転および平行移動を許容しつつ、不均一な歪、伸縮および拡大 Z縮小を許容しない状態で、前記中間的な三角形メッシュと、最終的な三角形メッシュとの間の差異を表現した誤り計量が最小となるような、最終的な三角形メッシュのデータ力もなる最終メッシュデータを生成し、前記記憶装置に記憶する第 2のメッシュ生成手段と、を備えたことを特徴とする画像処理システムにより達成される。

[0013] 好ま、実施態様にぉ、ては、第 2のメッシュ生成手段が、前記オリジナル形状データが示すオリジナル三角形メッシュのそれぞれを回転および平行移動させて、中間的メッシュデータが示す対応する対応する中間的な三角形メッシュとの間の 2次の誤り計量を最小化させる、適合ィ匕された三角形メッシュのデータ力もなる適合メッシュデータを生成し、かつ、前記記憶装置に記憶し、

前記適合メッシュデータが示す三角形メッシュと、対応する最終的な三角形メッシュとの間の、三角形の辺を表すベクトルの差を示す 2次の誤り計量が最小となるような、最終的な三角形メッシュのデータ力もなる最終メッシュデータを生成し、かつ、前記記憶装置に記憶するように構成されて、る。

[0014] また、別の好ましい実施態様においては、さらに、前記記憶装置に記憶されたオリジナル形状データ、或いは、最終メッシュデータを読み出して、読み出されたデータに基づくオブジェクトを含む画像を生成する画像生成手段を備える。

より好ましい実施態様においては、さらに、オリジナル形状データが前記記憶装置に記憶されると、

(a)前記オリジナル形状データが示すそれぞれのオリジナル三角形メッシュの頂点座標に基づいて、

^ste l T stepl

匕 (v) =V G V

を満たす行列 G^stepl、および、

-_r^,ste 2 step 2

匕 (v) =V G V

を満たす行列 G^step2

(ただし、

E^steplは、 2n個の変数 vox, voy, vlx, vly, · · · , vnx, vnyによる 2次式で表された、第 1のメッシュ生成手段における 2次の誤り計量を表す関数

E^step2は、 2n個の変数 vox, voy, vlx, vly, · · · , vnx, vnyによる 2次式で表された、第 2のメッシュ生成手段による、適合メッシュデータが示す三角形メッシュおよび最終的な三角形メッシュの差異を表現した 2次の誤り計量を表す関数）

を算出し、

(b) VE^fittine{w} =G^fittinew+B^fittine=0

であるような、行列 G^fitting、および、当該 G^iittingの逆行列 G^fitting_1

(ただし、

E^iittingは、前記第 2のメッシュ生成手段における、前記オリジナル形状データが示す三角形メッシュおよび中間的な三角形メッシュの間の差異を表現した 2次の誤り計量を示す関数）

を算出するように構成されたレジストレーシヨン手段と、

前記入力装置からの情報により、ある位置にハンドルが配置、追加され、あるいは、ある位置のハンドルが削除されると、

(c)前記 G^steplおよび G^step2に関して、ハンドルにより拘束される頂点の成分を除去することにより、行列 G^step1'および G^step2'を算出し、 (d)前記行列 G^step1'および G^step2'の逆行列 G^stepl'^{_ 1}および G^step2'^_1を算出するコンパィレーシヨン手段と、を備えている。

[0016] また、さらに好ましい実施態様においては、前記入力装置からの情報により、いずれかの位置のハンドルが移動されると、

前記第 1のメッシュ生成手段が、

(e)前記ハンドルの移動に伴って、三角形メッシュにおける拘束された頂点の更新された位置を用いて、ベクトル B^stepl

(ただし、 VE^stepl{u} = G^step1' + B^stepl = 0

VE^stepl {v}は、 E^stepl {v} = v^TG^stepl _Vの偏微分）

を算出し、

(f)前記行列 G^stepl'^_1と前記 B^steplとを乗じて、三角形メッシュにおける自由な頂点に関する座標を含む、中間的なメッシュ三角形の中間的メッシュデータを生成するように構成され、かつ、

前記第 2のメッシュ生成手段が、

(g)前記中間的メッシュデータに基づいて、前記ベクトル B^fittingを算出し、

(h)前記行列 G^fitting_1と B^fittingとを乗じて、前記適合化された三角形の適合メッシュデータを生成し、

(i)前記適合メッシュデータに基づき、ベクトル B^step2'

(ただし、 VE^step2{u} =G^step2 u+B^step2' = 0

VE^step2{v}は、 E^step2{v} =v^TG^step2 _V+B^step2 _Vの偏微分）

を算出し、

(j)前記行列 G^step2'^_1とベクトル B^step2'とを乗じて、最終的な三角形メッシュの最終メッシュデータを生成するように構成されて、る。

[0017] ある実施態様においては、前記変形すべきオブジェクトが、前記三角形メッシュにより構成される 2次元オブジェクトである。或いは、前記変形すべきオブジェクトが曲線であっても良い。この場合には、画像処理システムは、前記曲線を示すポリラインのデータから、前記ラインを構成する頂点の近接する 3点ずつを結んで構成される三角形メッシュを生成し、当該三角形メッシュのデータを、記憶装置に記憶する初期三角形メッシュ生成手段を備える。また、本発明の目的は、変形すべきオブジェクトを構成する三角形メッシュのデータ力なるオリジナル形状データが記憶された記憶装置を有するコンピュータにより読み出し可能な、画像処理プログラムであって、前記コンピュータに、

前記入力装置からの、前記画像中の前記三角形メッシュにおける固定すべき点および移動される点を含む、複数のハンドル位置を示す情報に基づいて、前記オリジナル形状データを前記記憶装置から読み出して、当該オリジナル形状データが示すそれぞれのオリジナル三角形メッシュにつ、て、その回転および拡大 z縮小を許容しつつ、オリジナル三角形メッシュと、処理後の中間的な三角形メッシュとの間の差異を表す 2次の誤り計量が最小となるような、中間的な三角形メッシュのデータ力もなる中間的メッシュデータを生成し、前記記憶装置に記憶する第 1のメッシュ生成ステツプと、

前記中間的メッシュデータが示すそれぞれの中間的な三角形メッシュにつ、て、その回転および平行移動を許容しつつ、不均一な歪、伸縮および拡大 z縮小を許容しない状態で、前記中間的な三角形メッシュと、最終的な三角形メッシュとの間の差異を表す誤り計量が最小となるような、最終的な三角形メッシュのデータ力なる最終メッシュデータを生成し、前記記憶装置に記憶する第 2のメッシュ生成ステップと、を実行させることを特徴とする画像処理プログラムにより達成される。

好ましい実施態様においては、前記第 2のメッシュ生成ステップにおいて、前記コンピュータに、

前記オリジナル形状データが示すオリジナル三角形メッシュのそれぞれを回転および平行移動させて、中間的メッシュデータが示す対応する対応する中間的な三角形メッシュとの間の 2次の誤り計量を最小化させる、適合ィ匕された三角形メッシュのデータからなる適合メッシュデータを生成し、かつ、前記記憶装置に記憶するステップと、前記適合メッシュデータが示す三角形メッシュと、対応する最終的な三角形メッシュとの間の、三角形の辺を表すベクトルの差を示す 2次の誤り計量が最小となるような、最終的な三角形メッシュのデータ力もなる最終メッシュデータを生成し、かつ、前記記憶装置に記憶するステップとを、実行させる。 [0019] 別の好ましい実施態様においては、前記コンピュータに、さらに、前記記憶装置に記憶されたオリジナル形状データ、或いは、最終メッシュデータを読み出して、読み出されたデータに基づくオブジェクトを含む画像を生成する画像生成ステップを、実行させる。

[0020] より好ましい実施態様においては、さらに、オリジナル形状データが前記記憶装置に記憶されると、

^ste l T stepl

匕 (v) =V G V

を満たす行列 G^stepl、および、

-_r^,ste 2 step 2

匕 (v) =V G V

を満たす行列 G^step2

(ただし、

E^steplは、 2n個の変数 vox, voy, vlx, vly, · · · , vnx, vnyによる 2次式で表された、第 1のメッシュ生成ステップにおける 2次の誤り計量を表す関数

E^step2は、 2n個の変数 vox, voy, vlx, vly, · · · , vnx, vnyによる 2次式で表された、第 2のメッシュ生成ステップによる、適合メッシュデータが示す三角形メッシュおよび最終的な三角形メッシュの差異を表す 2次の誤り計量を表す関数）

を算出するステップと、

(b) VE^fitting{w} =G^fittinew+B^fittine=0

(ただし、

E^iittingは、前記第 2のメッシュ生成ステップにおける、前記オリジナル形状データが示す三角形メッシュおよび中間的な三角形メッシュの間の差異を表現する 2次の誤り計量を示す関数）

を算出するステップと、を前記コンピュータに実行させ、さらに、

前記入力装置からの情報により、ある位置にハンドルが配置、追加され、あるいは、ある位置のハンドルが削除されると、 (c)前記 G^steplおよび G^step2に関して、ハンドルにより拘束される頂点の成分を除去することにより、行列 G^step1'および G^step2'を算出するステップと、

(d)前記行列 G^step1'および G^step2'の逆行列 G^stepl'^{_ 1}および G^step2'^_1を算出するステツプと、を前記コンピュータに実行させる。

[0021] また、さらに好ましい実施態様においては、前記入力装置からの情報により、いずれかの位置のハンドルが移動されると、

前記第 1のメッシュ生成ステップにお、て、

(ただし、 VE^stepl{u} = G^step1' + B^stepl = 0

VE^stepl {v}は、 E^stepl {v} = v^TG^stepl _Vの偏微分）

を算出するステップと、

(f)前記行列 G^stepl'^_1と前記 B^steplとを乗じて、三角形メッシュにおける自由な頂点に関する座標を含む、中間的なメッシュ三角形の中間的メッシュデータを生成するステップと、を前記コンピュータに実行させ、かつ、

前記第 2のメッシュ生成ステップにお、て、

(g)前記中間的メッシュデータに基づいて、前記ベクトル B^fittingを算出するステップと

(h)前記行列 G^fitting_1と B^fittingとを乗じて、前記適合化された三角形の適合メッシュデータを生成するステップと、

(i)前記適合メッシュデータに基づき、ベクトル B^step2'

(ただし、 VE^step2{u} =G^step2 u+B^step2' = 0

VE^step2{v}は、 E^step2{v} =v^TG^step2 _V+B^step2 _Vの偏微分）

を算出するステップと、

(j)前記行列 G^step2'^_1とベクトル B^step2'とを乗じて、最終的な三角形メッシュの最終メッシュデータを生成するステップと、を前記コンピュータに実行させる。

[0022] ある実施態様にぉ、ては、前記変形すべきオブジェクトが、前記三角形メッシュにより構成される 2次元オブジェクトである。或いは、前記変形すべきオブジェクトが曲線であり、さらに、画像処理プログラム力コンピュータに、曲線を示すポリラインのデータから、前記ラインを構成する頂点の近接する 3点ずつを結んで構成される三角形メッシュを生成し、当該三角形メッシュのデータを、記憶装置に記憶する初期三角形メッシュ生成ステップを実行させても良、。

発明の効果

[0023] 本発明によれば、オブジェクトを自然に変形でき、かつ、その処理時間も著しく短!ヽ画像処理システムおよび画像処理プログラムを提供することが可能となる。

発明を実施するための最良の形態

[0024] 以下、添付図面を参照して、本発明の実施の形態について説明する。

[システム構成]

図 1は、本実施の形態にカゝかる画像処理システムのハードウェア構成を示すブロックダイヤグラムである。図 1に示すように、画像処理システム 10は、ノス 11を介して接続された、マウスやキーボードなどの入力装置 12、表示装置 14、 CDや DVDなどの可搬記憶媒体 18への読み書きを実行するドライバ 16、 CPU20、 ROM22、 RAM2 4、および、ハードディスクなどの外部記憶装置 26を備えている。すなわち、通常のノーソナルコンピュータに、当該パーソナルコンピュータに実行させる処理ステップ（これらについては後に詳細に説明する）を含むコンピュータプログラムを、インスト一ルすることにより実現される。

[0025] 図 2は、本実施の形態に力かる画像処理システムの機能ブロックダイヤグラムである。図 2に示すように、画像処理システム 10は、機能的には、初期メッシュ生成部 30、レジストレーシヨン処理部 32、コンパィレーシヨン処理部 34、および、第 1のメッシュ生成部 36、第 2のメッシュ生成部 38を備える。これらの機能は、主として CPU20により実現される。また、画像処理システム 10は、後述する画像データを記憶する記憶装置 40を備える。この機能は、主として、 RAM24により実現される。また、図 2に示すように、画像処理システム 10は、入力装置からの指示を受け入れて、初期メッシュ生成部 30などの構成部分に対して、当該指示を与え、或いは、生成されたデータに基づく画像を表示装置 14に出力するインタフェース (IZF) 42、および、記憶装置 40に記憶されたデータ (たとえば、オリジナル形状データ、最終メッシュデータ）に基づいて、オブジェクトを描画する画像生成部 52を有する。

[処理の概略]

初期メッシュ生成部 30は、画像中、ユーザにより操作させるべき 2次元形状のォブジェタトの内部に三角形のメッシュを生成する。初期メッシュ生成部 30は、得られたメッシュの頂点の座標を、オリジナル形状データ 44として記憶装置 40に記憶する。初期メッシュ生成部 30の処理は、従来力知られており、この処理は、本発明の一部をなすものではない。

[0026] 2次元形状のオブジェクトは、ベクトル 'グラフィクスであっても良いし、ビットマップィメージであっても良い。必要なことは、 2次元形状の境界が閉じた多角形として得られていれば良い。また、画像がビットマップイメージである場合には、背景を消去して、外側の輪郭をトレースしておくことで、境界を閉じた多角形とすることができる。初期メッシュ生成部 30は、境界が閉じた多角形の内側に、三角形のメッシュを生成し、その頂点の座標のデータを、オリジナル形状データ 44として記憶装置 40に記憶する。三角形メッシュを生成するためには、種々の手法が知られている。本実施の形態においては、ほぼ等辺の三角形を、境界が閉じた多角形の領域全体にわたって生成するのが望ましい。初期メッシュ生成部 30は、拘束デロー-分割を基点として、頂点の位置およびメッシュの連結を調整することで、繰り返しメッシュを修正する。最終的に得られたメッシュの座標のデータ力オリジナル形状データ 44として、後の処理に使用される。

[前処理]

また、レジストレーショ処理部 32およびコンパィレーシヨン処理部 34は、後に詳述する第 1のメッシュ生成部 36および第 2のメッシュ生成部 38における処理の前処理を実行する。レジストレーシヨン処理部 32は、ユーザが、入力装置 12を操作して、表示装置 14の画面上に表示された 2次元形状のオブジェクトに、メッシュが生成されたときに、必要な処理を実行する。また、コンパィレーシヨン処理部 34は、ハンドル力配置、追加或いは削除されたときに、必要な処理を実行する。

[0027] ここに、本明細書において、ハンドルは、ユーザがマウスを操作して、表示された 2 次元形状の上でクリックすることで、設定することができる。この際に、画像処理システム 10は、記憶装置 40中に、ハンドルの座標を記憶しておく。また、ハンドルを設定した状態で、或いは、ハンドルを指定して、ユーザが、マウスをドラッグすることで、ハンドルを移動させることができる。ハンドルの移動に伴って、システムは、記憶装置 40に記憶されたハンドルの座標を更新すれば良い。なお、ハンドルが配置、追加或いは削除された場合に、画像処理システム 10において実行される処理と、ハンドルが移動された場合に、画像処理システム 10において実行される処理とは異なる。これについては、図 8および図 9のフローチャートを参照して、再度詳細に説明する。

[0028] なお、以下、ユーザがハンドルを設定し、或いは、ハンドルを移動させて、それに応答して、システムが処理を実行することを、「インタラクション」とも称する。また、ユーザ力ハンドルの設定や移動により、 2次元形状のオブジェクトを変形させることを、「マ -ピユレーシヨン」とも称する。

[0029] ユーザは、形状の上に 1以上のハンドルを配置し、対話的にハンドルを移動させる（図 3の符号 (b)および (c)参照)。マウスを利用する場合に、ユーザは、アイコンを形状の上の所望の位置に配置して、クリックすることで、ハンドルを設定することができ、かつ、ドラッグにより設定したノヽンドルを移動することができる。

[0030] 現状では、本発明にお、て、ユーザは、ハンドルを任意の位置に配置して、メッシュ構造を、ハンドルを含むように変形できるようにして、る。

[0031] 第 1に、形状のマニピュレーションは、三角形のメッシュに適用される。次いで、システムは、元の線および画像を、元のメッシュ力も変形されたメッシュに写像する。

[0032] ベクトル ·グラフィクスを操作する場合に、メッシュの対応する三角形中、それぞれの頂点の重心座標 (barycentric coordinates)が利用される。ビットマップイメージを操作するときには、単純な線形写像が利用される。

[0033] 画像処理システムは、新たなハンドルが追加され、或いは、ハンドルが削除されたときに、追カ卩的な前処理を実行する（図 3の符号 (b) )。この処理を、「コンパィレーション」と称する。この処理は、入力としてハンドルの構成、つまり、どれがハンドルとして設定された頂点であるかを示す情報を取得し、出力として、処理結果の形状を返すような関数 (ノ、ンドルの座標を受け取ると残りのメッシュの頂点の位置を返す関数)を返す。インタラクションの間、画像処理システム 10は、更新されたハンドルの構成を関数に送る。

[メッシュ生成の概略]

本実施の形態では、第 1のメッシュ生成処理部 36および第 2のメッシュ生成処理部 38の 2つがシーケンシャルに処理を実行することで、メッシュ生成が実現される。このメッシュ生成において、アルゴリズムへの入力は、拘束されたメッシュベクトルの x—y 座標であり（図 4の符号 a参照）、出力は、処理されたメッシュ三角形のそれぞれに関連する歪みを最小化するような、拘束された頂点以外の、残りの自由な頂点の座標である（図 4の符号 d参照)。主たる問題は、どのように三角形の歪みを定義するかにある。本実施の形態においては、自由変数において二次の誤り計量 (error metric)をデザインして、単純な行列演算により最小化の問題を解決する。

[0034] 第 1のメッシュ生成処理部 36では、拘束された頂点の座標を与えたときに、歪みや非均一は伸縮を回避する一方、回転および拡大縮小は認められる誤り計量を最小ィ匕することにより、中間結果である中間的メッシュデータ 46が生成される（図 4の符号 b参照)。生成された中間的メッシュデータ 46は、記憶装置 40中に記憶される。

[0035] 引き続ぐ第 2のメッシュ生成処理部 38における処理は、 2つの連続する処理に分解される。第 2のメッシュ生成処理部 38は、まず、まず、スケールを変更することなぐもとの三角形 (第 1のメッシュ生成処理部 36で得られた中間的メッシュデータ 46に基づく三角形)を、さらに中間的な三角形に適合させる（図 4の符号 c参照)。第 2のメッシュ処理部 38は、この適合された三角形に関するデータを、適合メッシュデータ 48として、記憶装置 40に記憶する。次いで、第 2のメッシュ生成処理部 38は、最終的な処理結果 (最終メッシュデータ 50)に基づく三角形と、適合メッシュデータ 48に基づく三角形との間の相違を表す誤り計量を最小にするような、最終的な処理結果を算出する（図 4の符号 d参照)。このようにして得られた最終メッシュデータ 50が記憶装置 4 0に記憶される。また、 2次元形状のオブジェクトは、最終メッシュデータ 50に基づく三角形メッシュの集合として、表示装置 14の画面上に表示される。

[第 1のメッシュ生成部 36における処理]

本実施の形態に力かる第 1のメッシュ生成部 36の処理では、回転および拡大縮小を認める誤り関数を最小化することにより、中間結果である中間的メッシュデータ 46 を生成する。入力は、記憶装置 40に記憶された、オリジナル形状データ 44中の拘束された頂点の X— y座標であり、出力は、上記拘束された頂点以外の、残りの自由な頂点の X— y座標である。

[0036] 本発明に力かるアルゴリズムでは、物理ベースのシミュレーションやリラクゼーション方法のように、初期的な構成として、以前の結果を利用しないことに留意すべきである。本発明では、閉じた形態での解法を提供することができる。

[0037] 図 5は、本実施の形態に力かる第 1のメッシュ生成部による処理における誤り関数を説明する図である。図 5において、 v2^desiredは、平行移動、回転および拡大'縮小により、 νθおよび vlが、 vO'、 VI 'にそれぞれマッチするように、ターゲットとなる三角形の上に元の三角形を適合させる（フィットされる）ことにより取得される。

[0038] 第 1のメッシュ生成部 36の処理において、三角形 {vO, vl, v2}のための誤り関数は、以下のように定義される（図 5参照)。

[0039] オリジナル形状データに基づく三角形 (νθ' , νΐ ' , ν2' )における対応する三角形について、第 1のメッシュ生成部 36は、まず、 vO，および vl 'にて定義される局所座標における ν2'の相対座標 {x , y }を算出する。

01 01

[0040] [数 1]

vO、 vl、 xOlおよび yOlを与えると、第 1のメッシュ生成部 36は、 v2に対する望ましい位置 (これが v2^desiredに相当する）を算出することができる。

[0041] [数 2]

desired r *

v2 二 ^vo + ½ v₀v, + y₀, R₉₀ v₀ ν_γ where

( 2 )

v2に関する誤りは、以下のように表される

[数 3]

同様に、 vO^desiredおよび vl^desireaを算出することもできる。これにより、ある三角形に関する誤りを、以下のように表すことができる。

[0043] [数 4]

?=1,2,3 . . . (4) 全体のメッシュに対する誤りは、単に、メッシュ中の全ての三角形に対する誤りの合計となる。誤り計量は、 ν^τ= {ν , V , V , V , · · ·, V , V }において 2次であるた

ox oy lx ly nx ny

め、誤りを行列の形式で表すことができる。

Stenl r 1 Tハ stepl /「ヽ

[0044] E {v} =v G v … {5)

最小化は、関数 Eの自由変数 U^T二 {U ， U ， U ， U ， · · ·，！！， U }による偏微

ox oy lx ly mx my

分 VE^stepl{v}を 0とすることにより解決することができる。

[0045] VE^stepl{u}=G^stepl'+B^stepl = 0 · · · (6)

ここに、 G^step1'は、 G^steplの拘束された変数に関する成分を除去することにより得られた「2mX2m」の行列、 B^steplは、 G^steplおよび拘束された変数力も得られるサイズ「m」のベクトルである。 G^step1'は固定値であり、 B^steplのみが、マニピュレーション中に変化するため、インタラクションの冒頭で、 G^step1'の逆数を求めておくことで、単なる行列の乗算によって、「u」を算出することができる。実際には、 G^step1'の LU分解が算出され、記憶装置 40に記憶される。図 4の符号 bは、第 1のメッシュ生成部 36による処理結果の概略を示す。インタラクションの間に、単一の行列の乗算が必要とされるだけなので、演算速度を速めることが可能となる。

[0046] 上記式（5)によれば、 E^steplは、 V , V , V , V , · · ·, V , V という 2n個の変数の

Ox Oy lx oy nx ny

2次式で表すことができる。

[0047] たとえば、

E^stepl = a水 v 水 v +b水 V 水 V +c水 V 水 v という 2次式であったとすると、 G^steplは、以下のように求めることができる。

Ljstepl =

{a b}

{b c}

再度、図 4について説明すると、図 4において、与えられたノヽンドル構成 (handle con figuration)に対して（図 4の符号 a)、画像処理システム 10は、まず、拡大縮小を許すような誤り計量を最小化することにより、中間結果（中間的メッシュデータ 46)を生成する（図 4の符号 b)。次いで、画像処理システム 10は、オリジナル形状データ 44に基づく三角形を、中間結果（中間的メッシュデータ）中の対応する三角形に適合させて、適合メッシュデータ 48を取得する（図 4の符号 c)。最終的に、画像処理システム 10 は、適合した三角形と、最終結果中の対応する三角形との間の差異を最小化することにより、最終結果 (最終メッシュデータ 50)を生成する。

[第 2のメッシュ生成部 38における処理]

第 2のメッシュ生成部 38は、記憶装置 40に記憶された、中間的メッシュデータ 46 ( 全ての頂点の X— y座標）を入力として取得し、メッシュ中の三角形の大きさを調整することで、出力として、最終結果である最終メッシュデータ 50 (自由な頂点の更新された x—y座標）を出力として返す。

[適合メッシュデータの生成]

第 2のメッシュ生成部 38は、オリジナル形状データ 44に基づく各三角形を、中間的メッシュデータ 46に基づぐ対応する三角形と適合させる。ここでは、三角形の回転および平行移動を許容するが、歪みゃ不均一な伸縮や拡大縮小は許容されなヽ ( 図 4の符号 c参照)。適合メッシュデータを生成する適合処理は以下のとおりである。

[0048]

_vl ^intermediate, 、および、オリジナル形状データ 44に基づぐ対応する三角形 {νθ' , vl ' , ν2' }を与えたときに、三角形 {νθ' , vl ' , ν2' }と合同で、かつ、以下の関数を最小化する新たな三角形 {v0, vl, v2}を見出すことが問題となる（図 6参照)。図 6においては、平行移動および回転により、元の三角形が中間的な三角形に適合 (fitting)されている。

[0049] [数 5]

上記数式の解を直接得ることは容易ではないため、まず、拡大縮小を許容して誤りを最小化し、かつ、その後にスケールを調整することにより、近似している。第 1のメッシュ生成部 36の処理に関して、 v2を、 νθおよび vlを用いて以下のように表した。

[数 6] v₂ = v_Q + x_m v_Qv_l + γ_{Μ 90}ν₀ν_{

• · · ( 8 ) この式を、誤り関数に投入することにより、誤り関数は、 w^T= {v , V , V , V }の 4

Ox O lx ly つの自由変数の 2次式となる。 4つの自由変数を 0とするよう勾配 VE^fittingを設定することにより、 E^fittingを最小化することができる。結果は、単純な 4つの連立方程式となり、これを解けば良い。

[0051] VE^fitting{w} =G^fittingw+B^fittine=0 …（9)

上記数式を解くことにより、元の三角形 {νθ' , vl ' , ν2' }と類似する、新たに適合された三角形 {vO, vl, v2}を得ることができる。次いで、 I νθ，一 vl， I / I vO-vl

Iの因子で、適合された三角形を拡大縮小することにより、合同の三角形を得ることができる。本実施の形態においては、この適合処理を全ての三角形に対して施す。

[0052] G^fittingおよび B^fittin%、上記 G^stepl等と同様に算出することができる。 E^fittingが、 w= { vox, voy, vlx, vly}の 2次式で得られれば、それを wの各要素で偏微分した VE^fitt ^ingは、（9)式に表すようになる。

[0053] たとえば、

_{V E}fittin_{g = { dE/v άΕ/γ} , _dE/_v , dE/v }

Ox oy lx ly

dE/v =a 水 v +b 水 v +c 水 v +d水 v +e

Ox 0 ox o oy o lx o ly 0

dE/v =a 水 v +b 水 v +c 水 v +d 水 v +e

oy 1 ox 1 oy 1 lx 1 ly 1

dE/v =a 氺 v +b 氺 v +c 氺 v +d 氺 v +e

lx 2 ox 2 oy 2 lx 2 ly 2

dE/v =a 氺 v +b 氺 v +c 氺 v +d氺 v +e

ly 3 ox 3 oy 3 lx 3 ly 3 とすると、

^fitting―

{

{aO, bO, cO, dO}

{al, bl, cl, dl }

{a2, b2, c2, d2}

{a3, b3, c3, d3}

_B ^fitting= {eO, el, e2, e3}

となる。

[最終メッシュデータの生成]

次いで、第 2のメッシュ生成部 38は、最終的なメッシュデータに基づく三角形と、適合メッシュデータに基づく三角形との間の差異を最小化することで、拘束された頂点の与えられた X— y座標に対する、拘束された頂点以外の自由な頂点の最終的な X —y座標を算出する（図 4の符号 d参照)。ここでは、適合メッシュデータ 48のみが利用され、中間的メッシュデータ 46は利用されな、ことに留意すべきである。

[0054] 図 7に示す単一の三角形 {vO, vl, v2}を参照して説明する。図 7において、画像処理システム 10は、適合された三角形のエッジベクトルと、ターゲットとなる三角形のエッジベクトルとの間の相違を算出する。適合メッシュデータ 48に基づく三角形 {vo^fi1 ted, yetted, yetted}を与えると、以下の 2次の誤り関数を定義することができる。

[0055] [数 7]

Inst p 2 ^sに、，、， J^mm » , J 2

( (0,1),(1， (2_¾0)}

• • • ( 1 0 ) ここに、誤りは、頂点ではなくエッジ (ベクトル)であることに留意すべきである。すなわち、ここでは、適合された三角形の方向のみを利用し、その位置は無視される。

[0056] 以下の処理は、第 1のステップと同様に実現される。全てのメッシュに対する誤りは、行列の形式で表され得る。

[0057] E^step2{v} =v^TG^step v+B^step V · · · (11)

次いで、関数 Eの自由変数 uによる、偏微分 VE を 0にする。

[0058] VE^step2{u} =G^step2 u+B^step2' = 0 · · · (12)

G^step2'が固定値であり、 B^step2'がマニピュレーションの間に変化するため、インタラタシヨンの冒頭で、 G^step2'の逆関数を算出しておくことで、単なる行列の乗算によって、 uを算出することができる。実際には、 G^step2'の LU分解が算出され、記憶装置 40に

SC fedれる。

[0059] なお、上記 G^step2も、 G^steplと同様に、上記（11)式に基づく式変形により求めることができる。

[実際の処理]

図 8および図 9は、本実施の形態に力かる画像処理システム 10において実行される処理を示すフローチャートである。画像処理システム 10のレジストレーシヨン処理部 32、コンパィレーシヨン処理部 34、第 1のメッシュ生成部 36および第 2のメッシュ生成部 38は、処理に必要なデータを記憶装置 40から読み出し、また、処理で生成されたデータを、記憶装置 40に記憶する。

[0060] 初期メッシュ生成部 30は、周知の手法で、オブジェクトの内部に生成された三角形の頂点の座標を含むオリジナル形状データを生成し、記憶装置 40に記憶する (ステップ 801)。また、画像生成部 52は、オリジナル形状データが生成されると、記憶装置 40力ら、当該データを読み出して、たとえば、背景に、オリジナル形状データに基づく 2次元オブジェクトが配置されたような画像を生成する（ステップ 802)。

[0061] レジストレーショ処理部 32は、新たにオリジナル形状データが生成されると、起動して、記憶装置 40から、オリジナル形状データを読み出して、その頂点座標に基づいて、（5)式に示した行列 G^stepl、および、（11)式に示した G^step2を算出する (ステップ 8 03)。次いで、レジストレーシヨン処理部 32は、オリジナル形状データに基づく各三角形について、（9)式に示す行列 G^iittingおよびその逆行列 G^fitting_1を算出する (ステツプ 804)。算出された行列のデータは、記憶装置 40中に記憶される。これら G^stepl、 G^s ^tep2、 G^fittingおよび G^fitting_1は、新たにオリジナル形状データが作られない限り、再度算出されることはなく、以下の、ユーザとのインタラクションによるハンドルの配置など

、マニピュレーション中に、記憶装置 40中に格納され、必要に応じて読み出される。

[0062] ユーザが入力装置 12を操作して、表示装置 14の画面中に表示された 2次元ォブジェタトに、ハンドルを配置し、或いは、ハンドルを追加、削除すると (ステップ 805)、これに応答して、コンパィレーシヨン処理部 34が起動する。コンノィレーシヨン処理部 34は、ステップ 803で得られた G^stepl、 G^step2に基づき、ハンドルの設定により拘束される頂点に関する成分を除去することにより、（6)式に示した行列 G^step1'、および、（1 2)式に示した行列 G^step2'を生成する（ステップ 806)。次いで、コンパィレーシヨン処理部 34は、ステップ 806で生成した行列の逆行列 G^stepl'^_1、および、 G^step2'^{_ 1}を生成する (ステップ 807)。ステップ 807で得られた逆行列 G^stepl'^_1、および、 G^step2'^_1のデータは、記憶装置 40に記憶される。

[0063] 前述したように、 G^step1'、 G^step2'は、それぞれ、行列 G^stepl、 G^step2の拘束された成分を除くことにより得られた行列である。

[0064] たとえば、行列 G^steplが以下のように表されるとする。

丄

{

{aO, bO, cO, dO} ,

{al, bl, cl, dl } ,

{a2, b2, c2, d2} ,

{a3, b3, c3, d3} , v= iv , V , V , V )

このときに、 _Viを除けば、

{aO, bO} ,

{al, bl } , となる。

[0065] 次いで、ユーザが入力装置 12を操作して、いずれかのハンドルを移動させると (ステツプ 900)、第 1のメッシュ生成部 36および第 2のメッシュ生成部 38による演算が開始される。第 1のメッシュ生成部 36は、ハンドルの移動に伴った、拘束された頂点の更新された位置に基づ、て、 (6)式に示したベクトル B^steplを生成する (ステップ 901) 。（6)式に示すように、行列 G^step1'の逆行列 G^stepl'^_1と、 B^steplとの積力も中間座標のデータ（つまり、中間的メッシュデータ 46)を求めることができる。したがって、第 1のメッシュ生成部 36は、ステップ 806で算出し、記憶装置 40に記憶された G^stepl'^_1を読み出して、ステップ 901で得たベクトル B^steplと乗ずる（ステップ 902)。第 1のメッシュ生成部 36は、このようにして得られた結果を、中間的メッシュデータ 46として記憶装置 40に記憶する。

[0066] その後、第 2のメッシュ生成部 38が、記憶装置 40から、中間的メッシュデータ 46を読み出して、中間的メッシュデータ 46に基づく各三角形について、（9)式に示すベタトル B^fittingを算出する (ステップ 903)。ここで、（9)式に示すように、行列 G^fittingの逆行列 G^iitting_1と B^fittingとの積を得て、かつ、そのスケールを、 ( I vO' -vl ' | / | νθ-ν 1 I )にしたがって調整することで、適合された三角形の座標 (適合メッシュデータ)を取得することができる。そこで、第 2のメッシュ生成部 38は、ステップ 804で生成され、記憶装置 40に記憶されていた、 G^fitting_1を読み出して、ステップ 903で算出した B^iitti ^ngとの積をとり、かつ、そのスケールを調整する（ステップ 904)。このようにして得られたデータを、第 2のメッシュ生成部 40は適合メッシュデータとして、記憶装置 40に記憶する。

[0067] さらに、第 2のメッシュ生成部 38は、適合メッシュデータに基づく三角形の座標に基づいて、（11)式に示したベクトル B^step2を算出し (ステップ 905)、その後、ベクトル B^ste ^p2に基づいて (拘束された成分を除去することで)、ベクトル B^step2'を算出する (ステツプ 906)。

[0068] (12)式に示すように、行列 G^step2'の逆行列 G^step2'^_1と、 B^step2'との積から、最終的な座標のデータ (最終メッシュデータ 50)を取得することができる。そこで、第 2のメッシュ生成部 38は、ステップ 807で生成し、記憶装置 40に記憶していた G^step2'^_1を読み出して、ステップ 905で算出した B^step2'との積をとり、最終的な三角形の座標を取得する (ステップ 908)。この最終的な三角形の座標が、最終メッシュデータ 50として、記憶装置 40に記憶される。

[0069] このようにして、最終メッシュデータ 50が記憶装置 40に記憶されると、画像生成部 5 2は、最終メッシュデータ 50を読み出して、たとえば、背景に、オリジナル形状データに基づく 2次元オブジェクトが配置されたような画像を生成し、表示装置 14の画面上に表示する（ステップ 908)。

[0070] これ以降、ユーザの入力装置 12の操作によってハンドルが移動された場合には (ステツプ 900)、ステップ 901からステップ 907の処理が実行されて、最終メッシュデータが更新され、記憶装置 40中に記憶される。また、この更新された最終メッシュデータに基づいて、画像生成部 52が、画像を生成して表示装置 14の画面上に表示する。つまり、ハンドルが移動される限りにおいては、図 8に示す処理は実行されない。つまり、ベクトル B^stepl、 B^fitting、 B^step2および B^step2'生成および行列の乗算のみが実行されることで、オブジェクトを適切に変形させることが可能である。

[0071] また、ハンドルが配置、追加、削除された場合には、コンパィレーシヨン処理部 34により、行列 G^stepl'、 G^step2'およびこれらの逆行列の生成が行われる。し力しながら、レジストレーシヨン部 32の処理は、新たなオブジェクトのメッシュが生成されない限り、新たに実行する必要がない。

[0072] このように、本実施の形態によれば、バンドルの移動に伴う演算を軽減することができる。また、第 1のメッシュ生成部の処理では、三角形メッシュの回転および拡大縮小を認める誤り計量を最小化した中間的な三角形メッシュのデータである中間メッシュデータを生成、記憶する。また、第 2のメッシュ生成部の処理では、回転や平行移動を許容しつつ、歪、不均一な伸縮、回転縮小を許容しない誤り関数を最小化するように、最終的な三角形メッシュのデータを算出し、記憶する。このように、 2段階でメッシュを変形させることで、オブジェクトの自然な変形を実現することができる。

[0073] 本発明は、以上の実施の形態に限定されることなぐ特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。 [0074] たとえば、前記実施の形態においては、オペレータが、マウスを用いて、オブジェクト上にハンドルを、配置し、追加し、削除し、或いは、いずれかのハンドルを移動している。たとえば、図 2に示す例では、 3つのハンドルがオブジェクトに配置され、たとえば、オペレータが、右側のハンドルを、さらに右に移動させることで、オブジェクトが変形されている。しかしながら、ハンドルの配置等のためには、マウスに限定されるものではなぐ他の入力装置により、ハンドルの配置等を実現できることは言うまでもない。たとえば、マルチポイント 'トラッキング ·デバイスを利用することができる。マルチポイント 'トラッキング 'デバイスを利用する場合には、ユーザは、表示装置の画面上に表示されたオブジェクトを参照して、両手で直接、 2次元オブジェクトの形状をつかんで、その形状をマ-ピュレートすることができる。

[0075] また、オブジェクトを表す三角形メッシュのそれぞれに異なる重みを与え、形状の局地的な剛性を制御できるようにすることもできる。たとえば、特定の 1以上の三角形メッシュに、所定量（たとえば、 10000)の重みを与え、他の三角形メッシュに、「1」の重みを与えることで、所定量の重みが与えられた三角形メッシュが剛性を持ち、ハンドルに移動により変形を受け難、ようにすることができる。

[0076] また、本実施の形態においては、 2次元オブジェクトのマニピュレーションに、本発明が適用されたがこれに限定されるものではなぐ 3次元オブジェクトのマニピユレ一シヨンに本発明を適用することもできる。この場合、三角形オブジェクトに (X座標， y座標）に加えて、奥行きを表す z値を含む三次元の座標を与える。初期的に、 z値は「0」であるが、マニピュレーションの際に、異なるメッシュが重なるときに、予め決められていた重なりの順序 (いずれが手前に来るかの順序）にしたがって、 z値を与えることで、いずれかの三角形メッシュを手前に表すことが可能となる。

[0077] 本発明にかかる 2段階処理のアルゴリズム（つまり、第 1のメッシュ生成部および第 2 のメッシュ生成部を利用した処理)を、曲線の編集にも適用することができる。 2次元オブジェクトにおける三角形メッシュの代わりに、ポリラインを入力とする。本実施の形態におけるメッシュ生成部は、図 13に示すように、ポリラインに基づいて、複数の三角形メッシュを生成することで、曲線の編集に本発明を適用可能としている。

[0078] つまり、図 10Aに示すように、曲線が与えられると (ステップ 1001)、初期メッシュ生成部 30が、曲線を複数のポリラインに分割し、その座標データ等を、記憶装置 40〖こ記憶する (ステップ 1002)。次いで、初期メッシュ生成部 30は、たとえば、ポリラインの連続する 3つの頂点を結ぶ三角形つくり（ステップ 1003)、これを三角形メッシュとして、その座標のデータを、オリジナル形状データ 44として、記憶装置 40に記憶する（ステップ 1004)。以後の処理は、図 8および図 9を参照したものと同様である。なお、オリジナル形状データにぉ、て、 V、ずれの座標を連結することで曲線が形成されるかを示す情報 (接続情報)が含まれるのが望ま、。

[0079] 画像生成部 52は、図 10Bに示すように、記憶装置 40から最終メッシュデータ 50を読み出すと (ステップ 1011)、前記接続情報にしたがって、最終メッシュデータ 50に示す座標のいずれを接続すべきかを判断して、曲線を生成し (ステップ 1012)、表示装置 14の画面上に表示する

図 11は、表示装置の画面上に表示された曲線を編集する例を示す図である。本発明のように、第 1のメッシュ生成部および第 2のメッシュ生成部における処理が実行された場合には、曲線は、あた力も剛性を有しているように振舞う。その一方、たとえば、第 1のメッシュ生成部における処理のみが実行された場合には、曲線が勝手に拡大、縮小してしまう。図 11の上図において、ハンドル（図中、人間の手で示されている )を移動している。図 11の左側の図は、第 1のメッシュ生成部による処理のみを施した場合 (比較例）を示し、右側の図は、第 1のメッシュ生成部および第 2のメッシュ生成部の双方の処理を施した場合 (実施例）を示す。比較例では、引き伸ばされた領域が増大し、押しつぶされた領域が縮小している。その一方、本発明を適用した例（実施例）によれば、より自然な結果を得られている。

[0080] ユーザが、インタラクションの間、影響を及ぼすべき領域を直接調整することができるように、「ピーリング'インタフェース」を提供する。「ピーリング'インタフェース」においては、ユーザが、曲線をより遠くにドラッグするのにしたがって、影響を及ぼすべき領域が増大する（図 11参照)。これにより、ユーザは、予め影響を及ぼすべき領域を特定する必要が無くなり、また、インタラクションをより直観的にすることが可能となる。

[0081] 図 12は、「ピーリング」インタフェース」を利用した曲線の編集の例を示す図である。

ユーザが、曲線をさらに遠くに引っ張ると、影響を及ぼすべき領域が増大する（図中、左から右を参照)。また、ユーザは、予め領域を明瞭に特定することもできる（図中、左下参照)。

[0082] また、ドラッグに先立って、曲線の上にピンを配置することにより、ユーザが明瞭に影響を及ぼすべき領域を特定することも可能である。しかしながら、ピンを配置する場合には、局地的な変形だけが可能であり、ユーザが影響を及ぼすべき領域を変更することはできない。なお、実際の処理では、ユーザの入力に応答して、初期メッシュ生成部 30により、ピンの座標を記憶装置 40に記憶し、処理において、そのピンの座標を利用すれば良い。

図面の簡単な説明

[0083] [図 1]図 1は、本実施の形態に力かる画像処理システムのハードウェア構成を示すブロックダイヤグラムである。

[図 2]図 2は、本実施の形態に力かる画像処理システムの機能ブロックダイヤグラムである。

[図 3]図 3は、本実施の形態に力かる画像処理システムによる処理 (レジストレーシヨン

、コンパィレーシヨンおよびマニピュレーション）を概略的に示す図である。

[図 4]図 4は、本実施の形態にカゝかる画像処理システムによるハンドル構成の生成、第 1のメッシュ生成、 2段階の第 2のメッシュ生成を説明する図である。

[図 5]図 5は、本実施の形態に力かる第 1のメッシュ生成部による処理における誤り関数を説明する図である。

[図 6]図 6は、本実施の形態に力かる第 2のメッシュ生成部による処理における、第 1 のステップである適合ィ匕 (フィッティング)を説明する図である。

[図 7]図 7は、本実施の形態に力かる第 2のメッシュ生成部による処理における、第 2 のステップを説明する図である。

[図 8]図 8は、本実施の形態にカゝかる画像処理システム 10において実行される処理を示すフローチャートである。

[図 9]図 9は、本実施の形態にカゝかる画像処理システム 10において実行される処理を示すフローチャートである。

[図 10]図 10A、 Bは、それぞれ、本発明を、曲線の編集に利用した場合に、画像処理システム 10にて実行される処理を示すフローチャートである。

[図 11]図 11は、本発明を利用した曲線の編集の例を示す図である。

[図 12]図 12は、本発明を利用した曲線の編集の他の例を示す図である。

[図 13]図 13は、本発明を曲線の編集に利用した場合の三角形メッシュ生成を説明する図である。

符号の説明

10 画像処理システム

12 入力装置

14 表示装置

30 初期メッシュ生成部

32 レジストレーシヨン処理部

34 コンパィレーシヨン処理部

36 第 1のメッシュ生成部

38 第 2のメッシュ生成部

40 記憶装置

52 画像生成部

Claims

請求の範囲

[1] 変形すべきオブジェクトを構成する三角形メッシュのデータ力なるオリジナル形状データが記憶された記憶装置を有する画像処理システムにおいて、

前記中間的メッシュデータが示すそれぞれの中間的な三角形メッシュにつ、て、その回転および平行移動を許容しつつ、不均一な歪、伸縮および拡大 Z縮小を許容しない状態で、前記中間的な三角形メッシュと、最終的な三角形メッシュとの間の差異を表現した誤り計量が最小となるような、最終的な三角形メッシュのデータ力もなる最終メッシュデータを生成し、前記記憶装置に記憶する第 2のメッシュ生成手段と、を備えたことを特徴とする画像処理システム。

[2] 前記第 2のメッシュ生成手段が、前記オリジナル形状データが示すオリジナル三角形メッシュのそれぞれを回転および平行移動させて、中間的メッシュデータが示す対応する対応する中間的な三角形メッシュとの間の 2次の誤り計量を最小化させる、適合化された三角形メッシュのデータ力もなる適合メッシュデータを生成し、かつ、前記記憶装置に記憶し、

前記適合メッシュデータが示す三角形メッシュと、対応する最終的な三角形メッシュとの間の、三角形の辺を表すベクトルの差を示す 2次の誤り計量が最小となるような、最終的な三角形メッシュのデータ力もなる最終メッシュデータを生成し、かつ、前記記憶装置に記憶するように構成されたことを特徴とする請求項 1に記載の画像処理システム。

[3] さらに、前記記憶装置に記憶されたオリジナル形状データ、或!、は、最終メッシュデータを読み出して、読み出されたデータに基づくオブジェクトを含む画像を生成する画像生成手段を備えたことを特徴とする請求項 2に記載の画像処理システム。

さらに、オリジナル形状データが前記記憶装置に記憶されると、

匕 (V) =V V

を満たす行列 G^stepl、および、

-_r^,ste 2 r i T stet>2

匕 (v) =V G V

を満たす行列 G^step2

(ただし、

を算出し、

(b) VE^fittine{w} =G^fittinew+B^fittine=0

(ただし、

E^iittingは、前記第 2のメッシュ生成手段における、前記オリジナル形状データが示す三角形メッシュおよび中間的な三角形メッシュに関する 2次の誤り計量を示す関数）を算出するように構成されたレジストレーシヨン手段と、

(c)前記 G^steplおよび G^step2に関して、ハンドルにより拘束される頂点の成分を除去することにより、行列 G^step1'および G^step2'を算出し、

(d)前記行列 G^step1'および G^step2'の逆行列 G^stepl'^{_ 1}および G^step2'^_1を算出するコンパィレーシヨン手段と、を備えたことを特徴とする請求項 2または 3に記載の画像処理システム。

[5] 前記入力装置からの情報により、いずれかの位置のハンドルが移動されると、

前記第 1のメッシュ生成手段が、

(ただし、 VE^stepl{u} = G^step1' + B^stepl = 0

VE^stepl {v}は、 E^stepl {v} = v^TG^stepl _Vの偏微分）

を算出し、

前記第 2のメッシュ生成手段が、

(i)前記適合メッシュデータに基づき、ベクトル B^step2'

(ただし、 VE^step2{u} =G^step2 u+B^step2' = 0

VE^step2{v}は、 E^step2{v} =v^TG^step2 _V+B^step2 _Vの偏微分）

を算出し、

(j)前記行列 G^step2'^_1とベクトル B^step2'とを乗じて、最終的な三角形メッシュの最終メッシュデータを生成するように構成されたことを特徴とする請求項 4に記載の画像処理システム。

[6] 前記変形すべきオブジェクトが、前記三角形メッシュにより構成される 2次元オブジェタトであることを特徴とする請求項 1ないし 5の何れか一項に記載の画像処理システム

[7] 前記変形すべきオブジェクトが曲線であり、前記曲線を示すポリラインのデータから、前記ラインを構成する頂点の近接する 3点ずつを結んで構成される三角形メッシュを生成し、当該三角形メッシュのデータを、記憶装置に記憶する初期三角形メッシュ生成手段を備えたことを特徴とする請求項 1ないし 5の何れか一項に記載の画像処理システム。

[8] 変形すべきオブジェクトを構成する三角形メッシュのデータ力なるオリジナル形状データが記憶された記憶装置を有するコンピュータにより読み出し可能な、画像処理プログラムであって、前記コンピュータに、

前記入力装置からの、前記画像中の前記三角形メッシュにおける固定すべき点および移動される点を含む、複数のハンドル位置を示す情報に基づいて、前記オリジナル形状データを前記記憶装置から読み出して、当該オリジナル形状データが示すそれぞれのオリジナル三角形メッシュにつ、て、その回転および拡大 Z縮小を許容しつつ、オリジナル三角形メッシュと、処理後の中間的な三角形メッシュとの間の差異を表現した 2次の誤り計量が最小となるような、中間的な三角形メッシュのデータからなる中間的メッシュデータを生成し、前記記憶装置に記憶する第 1のメッシュ生成ステツプと、

前記中間的メッシュデータが示すそれぞれの中間的な三角形メッシュにつ、て、その回転および平行移動を許容しつつ、不均一な歪、伸縮および拡大 z縮小を許容しない状態で、前記中間的な三角形メッシュと、最終的な三角形メッシュとの間の差異を表現した誤り計量が最小となるような、最終的な三角形メッシュのデータ力もなる最終メッシュデータを生成し、前記記憶装置に記憶する第 2のメッシュ生成ステップと、を実行させることを特徴とする画像処理プログラム。

[9] 前記第 2のメッシュ生成ステップにおいて、前記コンピュータに、

前記オリジナル形状データが示すオリジナル三角形メッシュのそれぞれを回転および平行移動させて、中間的メッシュデータが示す対応する対応する中間的な三角形メッシュとの間の 2次の誤り計量を最小化させる、適合ィ匕された三角形メッシュのデータからなる適合メッシュデータを生成し、かつ、前記記憶装置に記憶するステップと、前記適合メッシュデータが示す三角形メッシュと、対応する最終的な三角形メッシュとの間の、三角形の辺を表すベクトルの差を示す 2次の誤り計量が最小となるような、最終的な三角形メッシュのデータ力もなる最終メッシュデータを生成し、かつ、前記記憶装置に記憶するステップとを、実行させることを特徴とする請求項 8に記載の画像処理プログラム。

[10] 前記コンピュータに、さらに、前記記憶装置に記憶されたオリジナル形状データ、或いは、最終メッシュデータを読み出して、読み出されたデータに基づくオブジェクトを含む画像を生成する画像生成ステップを、実行させることを特徴とする請求項 9に記載の画像処理プログラム。

[11] さらに、オリジナル形状データが前記記憶装置に記憶されると、

^ste l T stepl

匕 (v) =V G V

を満たす行列 G^stepl、および、

-_r^,ste 2 step 2

匕 (v) =V G V

を満たす行列 G^step2

(ただし、

E^step2は、 2n個の変数 vox, voy, vlx, vly, · · · , vnx, vnyによる 2次式で表された、第 2のメッシュ生成ステップによる、適合メッシュデータが示す三角形メッシュおよび最終的な三角形メッシュの差異を表現した 2次の誤り計量を表す関数）

を算出するステップと、

(b) VE^fitting{w} =G^fittinew+B^fittine=0

であるような、行列 G^fitting、および、当該 G^iittingの逆行列 C^fitting_1

(ただし、

E^iittingは、前記第 2のメッシュ生成ステップにおける、前記オリジナル形状データが示す三角形メッシュおよび中間的な三角形メッシュに関する 2次の誤り計量を示す関数 )

(d)前記行列 G^step1'および G^step2'の逆行列 G^stepl'^{_ 1}および G^step2'^_1を算出するステツプと、を前記コンピュータに実行させることを特徴とする請求項 9または 10に記載の画像処理プログラム。

[12] 前記入力装置からの情報により、いずれかの位置のハンドルが移動されると、

前記第 1のメッシュ生成ステップにお、て、

(ただし、 VE^stepl{u} = G^step1' + B^stepl = 0

VE^stepl {v}は、 E^stepl {v} = v^TG^stepl _Vの偏微分）

を算出するステップと、

前記第 2のメッシュ生成ステップにお、て、

(i)前記適合メッシュデータに基づき、ベクトル B^step2'

(ただし、 VE^step2{u} =G^step2 u+B^step2' = 0

VE^step2{v}は、 E^step2{v} =v^TG^step2 _V+B^step2 _Vの偏微分）

を算出するステップと、

(j)前記行列 G^step2'^_1とベクトル B^step2'とを乗じて、最終的な三角形メッシュの最終メッシュデータを生成するステップと、を前記コンピュータに実行させることを特徴とする請求項 11に記載の画像処理プログラム。

[13] 前記変形すべきオブジェクトが、前記三角形メッシュにより構成される 2次元オブジェタトであることを特徴とする請求項 8ないし 12の何れか一項に記載の画像処理プログラム。

前記変形すべきオブジェクトが曲線であり、さらに、前記コンピュータに、

前記曲線を示すポリラインのデータから、前記ラインを構成する頂点の近接する 3 点ずつを結んで構成される三角形メッシュを生成し、当該三角形メッシュのデータを、記憶装置に記憶する初期三角形メッシュ生成ステップを実行させることを特徴とする請求項 8ないし 12の何れか一項に記載の画像処理プログラム。