画像処理装置、画像処理方法及び画像処理プログラム
【課題】画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集すること。
【解決手段】エッジがパラメトリック曲線で構成される曲面パッチではなく、直線境界を有するプリミティブパッチの識別子を用いて処理するので、レンダリングに係る計算コストを低減し、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。
【解決手段】エッジがパラメトリック曲線で構成される曲面パッチではなく、直線境界を有するプリミティブパッチの識別子を用いて処理するので、レンダリングに係る計算コストを低減し、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パラメトリック曲面を用いたベクトルデータで表される画像内の領域を編集する技術に関する。
【背景技術】
【０００２】
デジタルカメラやビデオカメラ等で撮影された画像は、一般に、ビットマップ形式で保存され、利用されることが多い。ビットマップデータは、画像を画素に分割し、あらゆる画像を様々な色の画素の集合として取り扱うため、ビットマップ形式の画像は写実性に優れているが、画像をオブジェクト単位で編集することは容易ではなく、拡大表示した際に画質の劣化が生じてしまう。なお、オブジェクトとは、画像内に撮影された意味のあるまとまりを意味し、例えば、人物、頭部、机、車両等の像に代表される。
【０００３】
一方、図形をベースとするベクトル形式のデータは、ベクトルデータが関数的な数値で表され、オブジェクト自体が数式に基づいて描画されるため、オブジェクト単位での編集が容易であり、拡大表示してもオブジェクトの正確性が保たれ、一定の画質が保持される。
【０００４】
このような背景下、現在では、ビットマップ形式の画像（以下、ビットマップ画像）をベクトル形式のデータに変換する手法が提案されている（非特許文献１、２参照）。これらの手法は、元のビットマップデータが持つ画質（すなわち写実性）を可能な限り損なわないようにして、できるだけ少ない数の図形要素を持つベクトルデータに変換することを特徴としている。
【０００５】
具体的には、図１３に示すように、撮影されたビットマップ画像内のオブジェクトを閉領域とみなし、その閉領域の輪郭及び内部を閉領域内の色の変化等に基づいて「辺がパラメトリック曲線で構成される三角形」や「辺がパラメトリック曲線で構成される矩形」に分割し、閉領域の輪郭や分割領域の境界をパラメトリック曲線で近似すると共に、その三角形又は矩形の内部の色をビットマップ画像内の一部の画素の色を参照して数式に基づいて補間することにより、ベクトルデータへの近似化な変換を実現している。以下、辺がパラメトリック曲線で構成される三角形や矩形を、「曲面パッチ」という。
【０００６】
この変換処理によって得られた三角形や矩形の各頂点の位置、各頂点や三角形内の色値、パラメトリック曲線の制御点等をベクトルデータとしてファイル形式又はデータベース形式で保存しておき、次処理において当該ベクトルデータを利用して画像を表示することにより、元のビットマップ画像のオブジェクトを近似的に生成（再現）可能となる。この生成処理により、パラメトリック曲面を用いたベクトルデータで表された画像が表示されるため、その画像内のオブジェクトの局所領域に対して所期する編集（オブジェクトの選択、選択領域の拡大や縮小、頂点移動等の画像処理）が可能となる。
【０００７】
なお、曲面パッチの色を補間する際は、曲面パッチを構成する頂点や適当にサンプリングされた点等の位置に対応するビットマップ画像上の画素位置の色情報を取得し、サンプリングされた点の位置以外の点の色値を何らかの数式を用いて近似的に計算することが一般的である。数式を用いて曲面パッチ内部の色値を計算することにより、オブジェクトのサイズが拡大された場合であっても、拡大後のオブジェクトの色を正確に表現でき、画質の劣化を防止することができる。
【０００８】
すなわち、曲面パッチ内部の色値としてビットマップ画像の各画素が有する色値をそのままデータとして保持する場合には、拡大時において輪郭部分に階段状の境界や色変化が現れてしまい画質が損なわれてしまうが、領域の幾何形状や領域内部の色情報を数式で計算可能なベクトル形式のデータ（ベクトルデータ）に変換しておくことにより、拡大した場合であってもなめらかな輪郭や色変化を表現することができる。
【０００９】
なお、曲面パッチは数学的処理が容易なことから、辺が次数３のパラメトリック曲線で表される双３次パッチが用いられることが多い。通常、この双３次パッチは、３次元的な曲面形状を表すために用いられるが、非特許文献１、２では、ビットマップ画像をオブジェクトの輪郭に沿って曲面パッチの形状を形成する処理や、曲面パッチ内部の色値の計算処理に用いている。
【００１０】
例えば、非特許文献１、２では、曲面パッチの辺が３次のＢｅｚｉｅｒ曲線又は当該曲線と等価な曲線が用いられている。また、非特許文献１では、画素位置（ｘ，ｙ）及び当該画素位置の色値ｈを変数としたときに、（ｘ，ｙ，ｈ）をＦｅｒｇｕｓｏｎパッチで表し、非特許文献２では、曲面パッチの形状（ｘ，ｙ）をＢｅｚｉｅｒ曲線で表し、画素位置（ｘ，ｙ）での色値を薄板スプライン補間手法を用いて計算している。
【００１１】
パラメトリック曲線は、一般に、画面の横軸方向の位置のパラメータをｕ（０≦ｕ≦１の実数）とし、縦軸方向の位置のパラメータをｖ（０≦ｖ≦１の実数）として、（ｕ，ｖ）で定まる点での位置ベクトルを（ｘ，ｙ，ｈ）とするベクトルデータで表現される。なお、ｘ，ｙ，ｈは、それぞれ、当該点における局所座標系のｘ軸，ｙ軸，ｈ軸のベクトル成分であり、（ｘ，ｙ）は曲面パッチ上の点の位置を意味し、ｈは（ｘ，ｙ）での色値を意味する。
【００１２】
そして、上記パラメータは、ｕ＝（ｕ，ｖ）や、添え字を付したｕｉ＝（ｕｉ，ｖｉ）等で表現され、ｘ，ｙ，ｈは、その表現形式を用いて以下の式（１）〜式（３）から計算される。
【００１３】
ｘｉ＝ｘ（ｕｉ，ｖｉ） ・・・式（１）
ｙｉ＝ｙ（ｕｉ，ｖｉ） ・・・式（２）
ｈｉ＝ｈ（ｕｉ，ｖｉ） ・・・式（３）
これら数式上はパラメータｕ，ｖに該当する位置を先に計算するように思われるが、実際にベクトルデータを画像としてレンダリング（色値の計算等）して表示する際には、曲面パッチ上の画素位置（ｘ，ｙ）を指定し、その位置でのパラメータ（ｕ，ｖ）の値を計算した上で、算出された（ｕ，ｖ）に対応する色値ｈ（ｕ，ｖ）を計算することになる。
【００１４】
このため、非特許文献１、２に開示されたようなベクトルデータを用いて画面を表示する方法は、同じサイズ（解像度）を持つビットマップ画像の表示に比べて計算コストが多大になる。
【００１５】
そこで、オブジェクトに対して近似的にあてはめられた複数の曲面パッチに識別子をそれぞれ付与し、編集する単位を指定されたオブジェクトに限定することにより、計算コストの低減を図る方法が用いられている。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】Yu-Kun Lai、外２名、“Automatic and Topology-Preserving Gradient Mesh Generation for Image Vectorization”、ACM Transactions on Graphics、Vol.28、No.3(SIGGRAPH 2009)、2009年8月、Article 85:1-8
【非特許文献２】Tian Xia、外２名、“Patch-based Image Vectorization with Automatic Curvilinear Feature Alignment”、ACM Transactions on Graphics、Vol.28、No.5(SIGGRAPH Asia 2009)、2009年12月、Article 115:1-10
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、利用される曲面パッチは曲線（パラメトリック曲線）により形成されるパラメトリック曲面により構成されているため、画像内のオブジェクトを変形するような場合には、曲面パッチの形状や曲面パッチ内部の色値の再計算に多くの処理時間を必要とし、変形後の画像の表示速度が遅いという問題があった。
【００１８】
本発明は、上記を鑑みてなされたものであり、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することを課題とする。
【課題を解決するための手段】
【００１９】
請求項１に記載の画像処理装置は、ビットマップ画像内のオブジェクトをパラメトリック曲面で近似した矩形又は三角形の曲面パッチのベクトルデータを記憶しておく記憶手段と、前記記憶手段からベクトルデータを読み出して、前記曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成する生成手段と、前記曲面パッチの２つの頂点を結ぶ曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分で前記プリミティブパッチを分割する分割手段と、前記ビットマップ画像の各画素に対応する配列データを生成し、分割されたプリミティブパッチの内部領域に対応する位置にプリミティブパッチを識別する識別子を格納する格納手段と、指定された画素位置に対応する識別子を前記配列データから取得し、取得された前記プリミティブパッチの識別子を用いて処理する処理手段と、を有することを特徴とする。
【００２０】
本発明によれば、辺がパラメトリック曲線で構成される曲面パッチではなく、直線境界を有するプリミティブパッチの識別子を用いて処理するため、レンダリングに係る計算コストを低減し、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。
【００２１】
請求項２に記載の画像処理装置は、請求項１に記載の画像処理装置において、頂点移動後のプリミティブパッチに対応する画素の色値を、当該頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、当該頂点及び当該サンプリング点の更新前の色値とを用いて決定することを特徴とする。
【００２２】
請求項３に記載の画像処理方法は、コンピュータにより行う画像処理方法において、ビットマップ画像内のオブジェクトをパラメトリック曲面で近似した矩形又は三角形の曲面パッチのベクトルデータを記憶手段に記憶しておくステップと、前記記憶手段からベクトルデータを読み出して、前記曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成するステップと、前記曲面パッチの２つの頂点を結ぶ曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分で前記プリミティブパッチを分割するステップと、前記ビットマップ画像の各画素に対応する配列データを生成し、分割されたプリミティブパッチの内部領域に対応する位置にプリミティブパッチを識別する識別子を格納するステップと、指定された画素位置に対応する識別子を前記配列データから取得し、取得された前記プリミティブパッチの識別子を用いて処理するステップと、を有することを特徴とする。
【００２３】
本発明によれば、辺がパラメトリック曲線で構成される曲面パッチではなく、直線境界を有するプリミティブパッチの識別子を用いて処理するため、レンダリングに係る計算コストを低減し、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。
【００２４】
請求項４に記載の画像処理方法は、請求項３に記載の画像処理方法において、頂点移動後のプリミティブパッチに対応する画素の色値を、当該頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、当該頂点及び当該サンプリング点の更新前の色値とを用いて決定することを特徴とする。
【００２５】
請求項５に記載の画像処理プログラムは、請求項３又は４に記載の画像処理方法における各ステップをコンピュータに実行させることを特徴とする。
【発明の効果】
【００２６】
本発明によれば、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。
【図面の簡単な説明】
【００２７】
【図１】画像処理装置の機能ブロック構成を示す図である。
【図２】画像処理装置の動作フローを示す図である。
【図３】ビットマップ画像の近似例及びラベルデータ例を示す図である。
【図４】ベクトルデータ例を示す図である。
【図５】ベクトルデータ例を示す図である。
【図６】曲線エッジを線分で近似する例を示す図である。
【図７】曲面パッチとパラメトリックパッチとの相関関係を示す図である。
【図８】曲線エッジの分割例を示す図である。
【図９】曲線エッジとプリミティブパッチの分割例を示す図である。
【図１０】プリミティブパッチの頂点移動例を示す図である。
【図１１】頂点移動後のプリミティブパッチの曲線、頂点、制御点の修正例を示す図である。
【図１２】頂点移動後の分割されたプリミティブパッチの曲線、頂点、制御点の修正例を示す図である。
【図１３】パラメトリック曲面での近似例を示す図である。
【発明を実施するための形態】
【００２８】
以下、三角形の曲面パッチ及び三角形のプリミティブパッチ（後述）を一例に用いて、本発明を実施する一実施の形態について説明する。但し、本発明は多くの異なる様態で実施することが可能であり、本実施の形態の記載内容に限定して解釈すべきではない。
【００２９】
すなわち、矩形の曲面パッチや矩形のプリミティブパッチを用いた場合であっても同様の作用効果を得ることができる。以下、三角形又は矩形の曲面パッチを単に曲面パッチといい、三角形又は矩形のプリミティブパッチを単にプリミティブパッチという。
【００３０】
また、曲面パッチの一辺を構成しているパラメトリック曲線は、Ｂｅｚｉｅｒ曲線（ベジェ曲線）や有理Ｂｅｚｉｅｒ曲線に代表されるが、その一辺を曲線ならしめる定理については何ら制限されない。
【００３１】
図１は、本実施の形態に係る画像処理装置の機能ブロック構成を示す図である。この画像処理装置は、データ記憶部１１と、ベクトルデータ読込／表示部１２と、識別子付与部１３と、第１ラベルデータ生成／記憶部１４と、識別子取得部１５と、画像処理部１６と、ベクトルデータ更新部１７と、プリミティブパッチ生成部１８と、曲線エッジ／線分エッジ評価部１９と、パラメトリック曲線分割部２０と、プリミティブ画像生成／表示部２１と、第２ラベルデータ生成／記憶部２２と、頂点移動受入部２３と、プリミティブ画像更新／表示部２４と、第２ラベルデータ更新／記憶部２５とで構成されている。
【００３２】
データ記憶部１１は、元のビットマップ画像内のオブジェクトをパラメトリック曲面で近似した曲面パッチを構成するベクトルデータを記憶しておく機能を有している。
【００３３】
ベクトルデータ読込／表示部１２は、データ記憶部１１のベクトルデータを読み込んで、そのベクトルデータを用いて曲面パッチを生成し、生成された曲面パッチに基づいてビットマップ画像（ラスタ画像）を生成して、ディスプレイに表示する機能を有している。すなわち、元のビットマップ画像に基づいて数値化・関数化されたベクトルデータから元のビットマップ画像を近似的に再現する機能を有している。
【００３４】
識別子付与部１３は、ベクトルデータ読込／表示部１２でのビットマップ画像生成中に生成された曲面パッチや当該曲面パッチを構成している辺（以下、曲線エッジ）に対して、各曲面パッチや各曲線エッジをそれぞれ識別する識別子を付与する機能を有している。
【００３５】
第１ラベルデータ生成／記憶部１４は、元のビットマップ画像と同サイズであって、そのビットマップ画像の各画素にそれぞれ対応するデータ領域を有する２次元配列データ（以下、第１ラベルデータ）を生成し、識別子付与部１３により付与された曲面パッチの識別子を曲面パッチの内部領域に対応する各位置にそれぞれ記憶（格納）する機能を有している。
【００３６】
識別子取得部１５は、ユーザによる編集処理要求を受け入れて、その要求により指定された画素範囲に対応するオブジェクトのパッチの識別子を第１ラベルデータ又は第２ラベルデータ（後述）から取得する機能を有している。
【００３７】
画像処理部１６は、識別子取得部１５で取得したパッチの識別子を用いて要求に応じた所定の処理（オブジェクトの選択、選択領域の拡大や縮小、頂点移動等の画像処理）を行う機能を有している。
【００３８】
ベクトルデータ更新部１７は、画像処理部１６の処理により修正等されたベクトルデータを用いて、データ記憶部１１のベクトルデータを更新（修正や追記等）する機能を有している。
【００３９】
プリミティブパッチ生成部１８は、曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成する機能を有している。
【００４０】
曲線エッジ／線分エッジ評価部１９は、曲面パッチの２つの頂点を結ぶ曲線エッジと、その曲線エッジに対応するプリミティブパッチの辺（以下、線分エッジ）との距離の差（エッジ成分長の差）を評価する機能を有している。
【００４１】
パラメトリック曲線分割部２０は、曲線エッジ／線分エッジ評価部１９での距離の差の評価に基づいて曲面パッチの曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分でプリミティブパッチを分割する機能を有している。
【００４２】
プリミティブ画像生成／表示部２１は、ベクトルデータ読込／表示部１２で生成された曲面パッチに基づくビットマップ画像からプリミティブパッチ（分割されたプリミティブパッチを含む）の内部領域に対応する画素位置の色値を取得し、プリミティブパッチに基づくプリミティブ画像を生成して、ディスプレイに表示する機能を有している。
【００４３】
第２ラベルデータ生成／記憶部２２は、第１ラベルデータ生成／記憶部１４と同様な領域を有する第２ラベルデータを生成し、プリミティブパッチ（分割されたプリミティブパッチを含む）の内部領域に対応する位置にプリミティブパッチを識別する識別子を記憶（格納）する機能を有している。
【００４４】
頂点移動受入部２３は、プリミティブ画像上において移動対象のプリミティブパッチの頂点の指定とその移動量を受け入れる機能を有している。
【００４５】
プリミティブ画像更新／表示部２４は、プリミティブパッチの頂点移動後の位置や移動量に基づいてプリミティブ画像を更新し、ディスプレイに表示する機能を有している。
【００４６】
第２ラベルデータ更新／記憶部２５は、プリミティブ画像の更新に伴って第２ラベルデータ内のプリミティブパッチの識別子を更新（修正等）する機能を有している。
【００４７】
次に、図２を参照しながら、本実施の形態に係る画像処理装置の動作について説明する。
【００４８】
最初に、曲面パッチに基づく処理方法について説明する。なお、本発明は、後述する線分によるプリミティブパッチに基づく処理方法を主な特徴とするが、当該処理方法は曲面パッチに基づいて生成された画像を利用することから、曲面パッチの処理方法を先に説明する。
【００４９】
まず、ベクトルデータ読込／表示部１２が、データ記憶部１１に記憶されているベクトルデータを読み込み、そのベクトデータを用いて曲面パッチの形状を生成し曲面パッチ内部の色値を補間することにより、指定された画像サイズでのビットマップ画像を生成する（Ｓ１０１、Ｓ１０３）。生成されたビットマップ画像例については図３（ａ）を参照されたい。
【００５０】
なお、ベクトルデータを用いビットマップ画像を生成する方法については、非特許文献２に記載されているため、その説明は省略する。
【００５１】
また、画像サイズが指定される理由については、ベクトルデータは生成されるビットマップ画像のサイズに依存しないため、画像を生成するにあたっては画像のサイズを必要とするからである。一般に、横方向がＷ（１以上の自然数）の画素、縦方向がＨ（１以上の自然数）の画素とされる。
【００５２】
ここで、ベクトルデータについて説明する。ここでのベクトルデータとは、曲面パッチを構築する関数を決定するための条件となるデータであり、例えば、図４に示すように、曲面パッチを構成する頂点のＩＤ、頂点の座標位置、頂点の色値等からなるデータテーブルや、曲面パッチの曲線エッジを制御する制御点、色補間する際に利用するサンプリング点等からなるデータテーブルにより構成されている。なお、ベクトルデータの書式や形式は任意に設定可能であり、その方式については何ら制限はない。
【００５３】
図２に戻り、ビットマップ画像を生成する際において、識別子付与部１３が、生成された複数の曲面パッチや各曲面パッチの複数の曲線エッジに対して識別子をそれぞれ付与する（Ｓ１０２）。
【００５４】
なお、このように付与される識別子としては、適宜採番した値を割り当てても良いし、ベクトルデータ内に識別子が含まれている場合には当該識別子を利用するようにしても良い。
【００５５】
次いで、ユーザによる編集処理がパッチ選択のみの場合には、第１ラベルデータ生成／記憶部１４が、元のビットマップ画像に対応する第１ラベルデータを生成し、識別子付与部１３によって付与された曲面パッチの識別子を当該曲面パッチの内部領域に対応する各位置にそれぞれ記憶する（Ｓ１０４、Ｓ１０５）。生成された第１ラベルデータ例については図３（ｂ）を参照されたい。
【００５６】
具体的には、各曲面パッチが占有する画像に対応する位置（ｉ，ｊ）（０≦ｉ＜Ｗ，０≦ｊ＜Ｈ）と当該位置での色値がそれぞれ計算されるので、例えばＴの識別子が付与された曲面パッチについては、計算された全ての位置（ｉ，ｊ）に対してＴを代入することにより第１ラベルデータを生成する。
【００５７】
次いで、ベクトルデータ読込／表示部１２が、Ｓ１０３で生成したビットマップ画像をディスプレイ上に表示する（Ｓ１０６）。
【００５８】
その後、識別子取得部１５が、ディスプレイに表示されたビットマップ画像に対する曲面パッチの選択処理を受け入れ、その選択により指定された画素範囲に対応する曲面パッチの識別子をＳ１０５で生成した第１ラベルデータから取得して、画像処理部１６が、その取得した曲面パッチの識別子を用いて処理を行う（Ｓ１０７〜Ｓ１０９）。
【００５９】
Ｓ１０８において曲面パッチの識別子を取得することにより、例えば複数の曲面パッチをまとめて一つのオブジェクトとして扱い、何らかのタグ情報を付与することができる。読み込んだベクトルデータに対して当該タグ情報を付与することにより、新たな情報をベクトルデータに追加することが可能となる。
【００６０】
例えば、（タグＩＤ，パッチ１のＩＤ，パッチ２のＩＤ，パッチ３のＩＤ，…）のようなリストをベクトルデータに付与することにより、当該タグＩＤを有するパッチＩＤを一度に取得することが可能となる。
【００６１】
最後に、ベクトルデータ更新部１７が、Ｓ１０９により更新されたベクトルデータを用いてデータ記憶部１１のベクトルデータを更新する（Ｓ１１０）。
【００６２】
なお、Ｓ１０７〜Ｓ１１０は、曲面パッチの選択処理が終了するまで繰り返される（Ｓ１１１）。
【００６３】
また、選択した曲面パッチを分かり易く示すために、ビットマップ画像上で選択された曲面パッチの色を変更するようにしてもよい。例えば、第１ラベルデータ上で同一識別子を有する位置に対応する画素位置の色値を同一色にすることにより実現する。
【００６４】
以上が曲面パッチに基づく基本的な処理方法である。パッチ選択等の識別子を扱う処理のみであればこれまで説明した処理方法でも良いが、ビットマップ画像内のオブジェクトを変形するような場合、すなわち、曲面パッチを構成する頂点を移動する場合には、移動後の曲面パッチの形状や内部の色値を再計算するのに多くの計算コストを必要とする。
【００６５】
ゆえに、その場合には、一般に高速に処理できる線分エッジを有するプリミティブ（ポリゴン：線分の辺を持つ三角形や矩形等の多角形）状のプリミティブパッチを用いて処理を行う。以下、プリミティブパッチに基づく処理方法について、引き続き図２を参照しながら説明する。
【００６６】
Ｓ１０４での判断処理において、ユーザによる編集処理がパッチ選択のみでない場合には、その選択された曲面パッチの曲線エッジにおいて未だ処理されていない曲線エッジがあるかどうかを判断し、未処理の曲線エッジがある場合には、ベクトルデータ読込／表示部１２及び識別子付与部１３が、データ記憶部１１のベクトルデータを用いて、曲面パッチや曲線エッジに関する情報リストを生成する（Ｓ１０４、Ｓ２０１〜Ｓ２０２）。生成されたリスト例については図５を参照されたい。このようなリストを予めデータ記憶部１１に記憶しておくようにしてもよい。
【００６７】
なお、図５に示す親パッチＩＤとは、後述の分割時に新たに生成されたパッチがどのパッチに属していたかを示す識別子である。また、親エッジＩＤとは、同様に、後述する分割時に新たに生成されたエッジがどのエッジに属していたかを示す識別子である。
【００６８】
次いで、図２に戻り、プリミティブパッチ生成部１８が、Ｓ２０２で生成された各リスト内のベクトルデータを用いて、曲面パッチの頂点を線分で結んだプリミティブパッチを生成する（Ｓ２０３）。
【００６９】
ここで、パラメトリック曲面の曲面パッチから線分のプリミティブパッチを生成する手法としては、図６（ｂ）に示すような輪郭をパラメトリック曲線とし内部のみを線分で結んで多角形を生成する方法や、図６（ｃ）に示すような輪郭をも線分で結んで多角形を生成する方法が挙げられる。ラベルデータの生成についても当該多角形を基準にして識別子を記憶することにより、いずれの方法であっても、頂点を移動した場合でも色値等の再計算コストを低減することができる。
【００７０】
ここで、図７に示すように、頂点の位置が同じであっても、元のベクトルデータが表している曲面パッチとプリミティブパッチとでは指定された画素位置の識別子が異なる場合がある。
【００７１】
そこで、図２に戻り、曲線エッジ／線分エッジ評価部１９が、曲面パッチを構成する曲線エッジの曲線距離と、その曲線エッジに対応するプリミティブパッチの線分エッジの直線距離との差を計算し、その距離の差が所定の閾値よりも大きい場合には、パラメトリック曲線分割部２０が、その曲線エッジを中点で分割する（Ｓ２０４〜Ｓ２０６）。
【００７２】
ここで、図８を参照しながら、距離の差の評価方法について説明する。例えば、２点間のチェス盤距離により評価することができる。２つの頂点ｖ１（ｘ１，ｙ１），ｖ２（ｘ２，ｙ２）のチェス盤距離ｄは以下の式（４）のように定義できる。
【００７３】
ｄ（ｖ１，ｖ２）＝ｍａｘ（｜ｘ１−ｘ２｜，｜ｙ１−ｙ２｜） ・・・式（４）
そして、曲線を構成する２つの頂点ｖ１，ｖ２と２つの制御点ｃ１，ｃ２とがｖ１，ｃ１，ｃ２，ｖ２の順に並んでいる場合には、曲線エッジの曲線距離を式（５）で算出し、線分エッジの直線距離については式（６）で算出する。
【００７４】
ｄ１＝ｄ（ｖ１，ｃ１）＋ｄ（ｃ１，ｃ２）＋ｄ（ｃ２，ｖ２） ・・・式（５）
ｄ２＝ｄ（ｖ１，ｖ２） ・・・式（６）
その後、ｄ１とｄ２との差が予め設定された所定の閾値よりも大きい場合には、曲線エッジを分割する。
【００７５】
その他、曲線エッジが式（１）〜式（３）において（ｕ，ｖ＝０）の位置で表されるような場合には、（ｕ＝１／２，ｖ＝０）の位置で分割するしてもよい。
【００７６】
なお、このようにパラメトリック曲線を分割する方法、すなわち、曲線形状を保持したままセグメント数を増やす方法については、「Curves and Surfaces for CAGD; 5th edition」（Gerald Farin著、Academic Press, 2002）（以下、参考文献１）に示されているように周知の技術である。
【００７７】
ここで、曲線エッジを分割すると、その曲線エッジを境界に有する２つのパッチに影響が及ぶため、プリミティブパッチを生成する前に、全ての曲線エッジについて分割するかどうかを判定し、分割対象と判断された曲線エッジを予め分割しておくようにしてもよい。
【００７８】
次いで、図２に戻り、パラメトリック曲線分割部２０が、上記参考文献１に記載された分割手法を利用して分割された各曲線エッジの制御点をそれぞれ生成し、各制御点について新たなＩＤを付与して、分割前の曲線エッジのＩＤに関連付けてデータテーブルに追加する（Ｓ２０６）。
【００７９】
次いで、パラメトリック曲線分割部２０が、分割された曲線エッジ上の分割点と、当該曲線エッジを境界に有する２つのプリミティブパッチの他の頂点（曲線エッジを構成する両頂点ではない頂点）とを結んで新たなエッジを追加し、その追加された新たなエッジでそれら２つのプリミティブパッチをそれぞれ分割し、分割されたプリミティブパッチやエッジについて新たなＩＤを付与し、分割前の曲線エッジのＩＤに関連付けてデータテーブルに追加する（Ｓ２０６〜Ｓ２０８）。
【００８０】
なお、Ｓ２０６の分割手順については図９を参照されたい。新たに追加されたエッジについては、特に曲線と対応付ける必要はなく、制御点を持たなくてもよい。
【００８１】
ここで、１つのパッチを構成する２つのエッジを分割する際は注意が必要である。あるパッチの頂点ｖ１，ｖ２，ｖ３がエッジｅ１＝（ｖ２，ｖ３），ｅ２＝（ｖ３，ｖ１），ｅ３＝（ｖ１，ｖ２）を有するとき、ｅ１を分割後にｅ２を分割した場合と、逆にｅ２を分割後にｅ１を分割した場合とでは分割結果が異なる場合がある。そこで、ある特定のプリミティブパッチのみを考慮するような場合には、そのパッチを構成するエッジの中で距離の差が大きいエッジから優先して分割し、分割が一意的になるようにしてもよい。また、すべてのパッチのエッジについて距離の際を事前に評価しておき、その距離の差が大きいものから順に分割し、エッジの分割が完了してからプリミティブパッチを分割してもよい。
【００８２】
なお、分割後のエッジについても距離の差が所定の閾値を超える場合には、当該距離の差が所定の閾値以下になるまで分割後のエッジを更に分割することを繰り返すようにしてもよいし、その分割回数を予め決めておくようにしてもよい。
【００８３】
次いで、プリミティブ画像生成／表示部２１が、Ｓ１０３で生成した曲面パッチに基づくビットマップ画像から、Ｓ２０３及びＳ２０６で生成されたプリミティブパッチの内部領域に対応する画素位置の色値を取得して、プリミティブパッチに基づくプリミティブ画像を生成する（Ｓ２０９）。生成されたプリミティブ画像例については図３（ｃ）を参照されたい。
【００８４】
なお、このプリミティブ画像は、Ｓ１０３で生成したビットマップ画像をそのまま用いても良いし、その複製を用いてもよい。
【００８５】
次いで、第２ラベルデータ生成／記憶部２２が、プリミティブ画像に対応する第２ラベルデータを生成し、プリミティブパッチの識別子をプリミティブパッチ（分割されたプリミティブパッチを含む）の内部領域に対応する各位置にそれぞれ記憶する（Ｓ２１０）。生成された第２ラベルデータ例については図３（ｄ）を参照されたい。
【００８６】
次いで、プリミティブ画像生成／表示部２１が、Ｓ２０９で生成したプリミティブ画像をディスプレイ上に表示する（Ｓ２１１）。
【００８７】
その後、識別子取得部１５が、ディスプレイに表示されたプリミティブ画像に対するプリミティブパッチの選択処理を受け入れ、その選択により指定された画素範囲に対応するプリミティブパッチの識別子をＳ２１０で生成した第２ラベルデータから取得して、画像処理部１６が、その取得したプリミティブパッチの識別子を用いて処理を行う（Ｓ２１２〜Ｓ２１４）。
【００８８】
最後に、ベクトルデータ更新部１７が、Ｓ２１４によって更新されたベクトルデータを用いてデータ記憶部１１のベクトルデータを更新する（Ｓ２１５）。
【００８９】
なお、Ｓ２１２〜Ｓ２１５は、プリミティブパッチの選択処理が終了するまで繰り返される（Ｓ２１６）。
【００９０】
また、曲面パッチをプリミティブで近似したプリミティブパッチについてのラベルデータであることから、図７を用いて説明したように、エッジ付近では正確な識別子ではなく隣接する識別子が取得される可能性があるが、プリミティブエッジによるラベル表現は後述する頂点の移動を高速に実現できるという効果がある。
【００９１】
引き続き図２を参照しながら、プリミティブパッチの頂点が移動した場合の動作について説明する。
【００９２】
Ｓ２１３の後、頂点移動受入部２３が、Ｓ２１１で表示されたプリミティブ画像上において、移動させる頂点座標の指定とその移動量を受け入れる（Ｓ３０１）。
【００９３】
次いで、プリミティブ画像更新／表示部２４が、Ｓ３０１で受け入れた移動後の位置や移動量に基づいてプリミティブ画像を修正する（Ｓ３０２）。
【００９４】
図１０に示したように、プリミティブパッチの頂点移動は頂点を共有する複数のプリミティブパッチに影響を与えるが、プリミティブパッチ内の色値は頂点移動によってプリミティブパッチの形状に変形が生じても容易に計算可能である。
【００９５】
例えば、頂点の移動については、上記参考文献１に示されたアファイン変換を用いることにより、移動後のプリミティブパッチ内部の座標値が移動前のどの位置から移動されたのかを容易に計算することができる。また、色値については、移動前の位置の色値を用いることにより、容易に計算することができる。
【００９６】
また、Ｓ３０２と同時に、第２ラベルデータ更新／記憶部２５が、Ｓ３０２での更新に伴って、第２ラベルデータ内のプリミティブパッチの識別子を修正する（Ｓ３０３）。移動対象となる頂点を含むプリミティブパッチのみ識別子を修正するため低コストで実現できる。
【００９７】
最後に、Ｓ２１５に進み、ベクトルデータ更新部１７が、Ｓ３０１で受け入れた移動後の位置や移動量に基づいてデータ記憶部１１のベクトルデータを更新する。
【００９８】
ここで、図１１又は図１２を参照しながら頂点移動があった場合のベクトルデータの更新例について説明する。図１１では、頂点とその頂点に関わる曲線エッジが示されている。曲線エッジを線分エッジで近似しても、制御点があれば曲線を容易に復元することができる。
【００９９】
図１１において、ｖ２の頂点をｖ２ａに移動させることにより、ｅ１の線分エッジをｅ１ａに移動させたとする。このとき、もとの曲線エッジを構成するための頂点ｖ１、ｖ２及び制御点ｃ１、ｃ２も影響を受けるが、本発明においては、ｖ２とｖ２に近い制御点ｃ２のみを移動させ、当該移動対象のみのベクトルデータを更新する。一方、ｃ２が位置的に決まらない場合はｃ２を移動させなくてもよいが、例えば、ｖ１とｃ２ａのユークリッド距離とｖ１とｃ２ａのユークリッド距離とが変化しないという拘束条件を用いてｃ２ａの座標値を決めてもよい。
【０１００】
図１２では、分割されたプリミティブパッチの頂点が移動する場合が示されている。この場合であっても、分割点において曲線エッジがなめらかに接続されていることから、上記と同様に、移動した頂点に近い方の制御点のみを移動させ、当該移動対象のみのベクトルデータを更新する。これにより、分割点においてエッジのなめらかな接続を保持することができる。
【０１０１】
すなわち、図２のＳ２１５において、ベクトルデータ更新部１７は、エッジが分割されていないパッチについては、移動対象の頂点と当該頂点に近い制御点のみのベクトルデータを更新する。
【０１０２】
また、必要に応じて、更新後のプリミティブ画像から適当なサンプリング点を抽出し、パッチ補間に必要な点座標と当該点座標における色値とを取得して、頂点移動後のプリミティブパッチに対応する画素の色値を決定して、ベクトルデータに追記してもよい。例えば、頂点移動後のプリミティブパッチに対応する画素の色値を、頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、その頂点及びサンプリング点の更新前の色値とを用いて決定して、ベクトルデータに追記する。
【０１０３】
一方、エッジが分割されたパッチについては、分割により増加したパッチについて、そのパッチを構成する頂点、制御点、サンプリング点、それら各点の色値をベクトルデータにそれぞれ追記する。また、増加した２以上のパッチの２以上の曲線エッジが１つのパラメトリック曲線で表すことができるように頂点及び制御点した後に、頂点、制御点、サンプリング点、それら各点の色値をベクトルデータにそれぞれ追記してもよい。
【０１０４】
また、必要に応じて、更新後のプリミティブ画像から適当なサンプリング点を抽出し、パッチ補間に必要な点座標と当該点座標における色値とを取得して、頂点移動後のプリミティブパッチに対応する画素の色値を決定して、ベクトルデータに追記してもよい。例えば、頂点移動後のプリミティブパッチに対応する画素の色値を、頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、その頂点及びサンプリング点の更新前の色値とを用いて決定して、ベクトルデータに追記する。
【０１０５】
なお、接続されている複数の曲線を１のパラメトリック曲線で近似する方法は、例えば、複数の曲線を構成する頂点や当該曲線上の適当な点を選定し、その頂点と適当な点を通るようなパラメトリック曲線を得られる制御点位置を計算しても良い。このような近似手法はデータフィッティングと呼ばれるものであり、例えば「An Algorithm for Automatically Fitting Digitized Curves」（Philip J. Schneider著、Graphics Gems, Morgan Kaufmann Publishers, pp.612-626, 1990.）に示されているように周知の技術である。
【０１０６】
本実施の形態によれば、エッジがパラメトリック曲線で構成される曲面パッチではなく、直線境界を有するプリミティブパッチの識別子を用いて処理するので、レンダリングに係る計算コストを低減し、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。また、高速表示に基づいて編集作業を元のベクトルデータに反映することができる。
【０１０７】
以下、そのように直線境界を有するプリミティブパッチの識別子を用いることによって得られる当該効果への作用について詳述しておく。
【０１０８】
辺がパラメトリック曲線で構成された曲面パッチによって構成された画像（これは、元のビットマップ画像を辺がパラメトリック曲線で構成された曲面パッチによって過不足なく分割されることと等価）を画面上にレンダリング（描画）する際は、ビットマップ画面上の各画素に対応する位置の色値を計算によって決定するが、この「各画素に対応する位置」がどの曲面パッチに属しているかを決定するのは容易ではない。
【０１０９】
これは、ある画素をひとつ選んだとしても、それがひとつの曲面パッチの内部にあるのか外部にあるのかを判定することですら、多くの計算を要するからである。例えば、ある位置（ｘ，ｙ）の画素が曲面パッチＰ１に含まれるか否かを判定するには、上記式（１）や式（２）から（ｕ，ｖ）の値を例えばニュートン−ラフソン法等を用いて数値計算によって近似的に求め、それが０≦ｕ≦１、０≦ｖ≦１にあるかどうかを評価することで判定することが一般的である。
【０１１０】
しかしながら、曲面パッチＰ１に含まれていなければ、別の曲面パッチＰ２について同様の計算を行うなど、当該画素を含む曲面パッチを見つけるまでこの判定を繰り返すことになる。
【０１１１】
これと同じ理由により、曲面パッチで構成された画像上で、ある画素をユーザが選択した際、それがどの曲面パッチの内部なのかを判定するのは容易ではない。
【０１１２】
そこで、曲面パッチによるベクトル化画像をレンダリングする際に、同時に曲面パッチの識別子を第１ラベルデータに書き込んでいき、画像生成後ある画素が選択された場合には、上記数式を用いた数値解析に基づく曲面パッチの内外判定ではなく、この第１ラベルデータ上の当該位置に格納されている識別子によって判定することにより、直ちに当該画素位置を含む曲面パッチを特定可能となる。
【０１１３】
しかしながら、この方法では、曲面パッチを変形させるなどの編集を加えた場合に、変形後の新しい画像をレンダリングするのも前述の理由により時間がかかるため、効率が良いとまではいえない。
【０１１４】
これに対し、辺が直線（線分）で構成されたプリミティブパッチは、比較的簡単な計算で、ある点が内部か外部かを判定することが可能となる。具体的には、三角形の内部に含まれるかどうかを単純に計算すればよく、矩形の場合には２つの三角形に対角線で分けて同じ計算を２回行えばよい。更には、第２ラベルデータに格納した識別子を内外判定に用いれば、そのような計算すら不要となる。また、プリミティブパッチ変形後の色の再計算や第２ラベルデータの更新についても画素の内外判定が容易なため、曲面パッチに比べて極めて少ない計算量で済むことになる。
【０１１５】
従って、レンダリングに係る計算コストを低減することが可能となり、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することが可能となる。
【０１１６】
最後に、本実施の形態で説明した画像処理装置はコンピュータで構成される。すなわち、画像処理装置を構成している各処理機能部は、メモリやハードディスク等の記憶手段、ＣＰＵ等の演算手段で実現され、プログラムで実行される。
【０１１７】
また、本実施の形態で説明した画像処理装置をプログラムとして光記憶装置や磁気記憶装置等の記録媒体に読出可能に記録し、この記録媒体をコンピュータに組み込んだり、若しくは記録媒体に記録されたプログラムを、任意の通信回線を介してコンピュータにダウンロードしたり、又は記録媒体からインストールし、該プログラムでコンピュータを動作させることにより、上述した各動作を画像処理装置として機能させることができるのは勿論である。
【符号の説明】
【０１１８】
１１…データ記憶部
１２…ベクトルデータ読込／表示部
１３…識別子付与部
１４…第１ラベルデータ生成／記憶部
１５…識別子取得部
１６…画像処理部
１７…ベクトルデータ更新部
１８…プリミティブパッチ生成部
１９…曲線エッジ／線分エッジ評価部
２０…パラメトリック曲線分割部
２１…プリミティブ画像生成／表示部
２２…第２ラベルデータ生成／記憶部
２３…頂点移動受入部
２４…プリミティブ画像更新／表示部
２５…第２ラベルデータ更新／記憶部
Ｓ１０１〜Ｓ１１１、Ｓ２０１〜Ｓ２１６、Ｓ３０１〜Ｓ３０３…ステップ
【技術分野】
【０００１】
本発明は、パラメトリック曲面を用いたベクトルデータで表される画像内の領域を編集する技術に関する。
【背景技術】
【０００２】
デジタルカメラやビデオカメラ等で撮影された画像は、一般に、ビットマップ形式で保存され、利用されることが多い。ビットマップデータは、画像を画素に分割し、あらゆる画像を様々な色の画素の集合として取り扱うため、ビットマップ形式の画像は写実性に優れているが、画像をオブジェクト単位で編集することは容易ではなく、拡大表示した際に画質の劣化が生じてしまう。なお、オブジェクトとは、画像内に撮影された意味のあるまとまりを意味し、例えば、人物、頭部、机、車両等の像に代表される。
【０００３】
一方、図形をベースとするベクトル形式のデータは、ベクトルデータが関数的な数値で表され、オブジェクト自体が数式に基づいて描画されるため、オブジェクト単位での編集が容易であり、拡大表示してもオブジェクトの正確性が保たれ、一定の画質が保持される。
【０００４】
このような背景下、現在では、ビットマップ形式の画像（以下、ビットマップ画像）をベクトル形式のデータに変換する手法が提案されている（非特許文献１、２参照）。これらの手法は、元のビットマップデータが持つ画質（すなわち写実性）を可能な限り損なわないようにして、できるだけ少ない数の図形要素を持つベクトルデータに変換することを特徴としている。
【０００５】
具体的には、図１３に示すように、撮影されたビットマップ画像内のオブジェクトを閉領域とみなし、その閉領域の輪郭及び内部を閉領域内の色の変化等に基づいて「辺がパラメトリック曲線で構成される三角形」や「辺がパラメトリック曲線で構成される矩形」に分割し、閉領域の輪郭や分割領域の境界をパラメトリック曲線で近似すると共に、その三角形又は矩形の内部の色をビットマップ画像内の一部の画素の色を参照して数式に基づいて補間することにより、ベクトルデータへの近似化な変換を実現している。以下、辺がパラメトリック曲線で構成される三角形や矩形を、「曲面パッチ」という。
【０００６】
この変換処理によって得られた三角形や矩形の各頂点の位置、各頂点や三角形内の色値、パラメトリック曲線の制御点等をベクトルデータとしてファイル形式又はデータベース形式で保存しておき、次処理において当該ベクトルデータを利用して画像を表示することにより、元のビットマップ画像のオブジェクトを近似的に生成（再現）可能となる。この生成処理により、パラメトリック曲面を用いたベクトルデータで表された画像が表示されるため、その画像内のオブジェクトの局所領域に対して所期する編集（オブジェクトの選択、選択領域の拡大や縮小、頂点移動等の画像処理）が可能となる。
【０００７】
なお、曲面パッチの色を補間する際は、曲面パッチを構成する頂点や適当にサンプリングされた点等の位置に対応するビットマップ画像上の画素位置の色情報を取得し、サンプリングされた点の位置以外の点の色値を何らかの数式を用いて近似的に計算することが一般的である。数式を用いて曲面パッチ内部の色値を計算することにより、オブジェクトのサイズが拡大された場合であっても、拡大後のオブジェクトの色を正確に表現でき、画質の劣化を防止することができる。
【０００８】
すなわち、曲面パッチ内部の色値としてビットマップ画像の各画素が有する色値をそのままデータとして保持する場合には、拡大時において輪郭部分に階段状の境界や色変化が現れてしまい画質が損なわれてしまうが、領域の幾何形状や領域内部の色情報を数式で計算可能なベクトル形式のデータ（ベクトルデータ）に変換しておくことにより、拡大した場合であってもなめらかな輪郭や色変化を表現することができる。
【０００９】
なお、曲面パッチは数学的処理が容易なことから、辺が次数３のパラメトリック曲線で表される双３次パッチが用いられることが多い。通常、この双３次パッチは、３次元的な曲面形状を表すために用いられるが、非特許文献１、２では、ビットマップ画像をオブジェクトの輪郭に沿って曲面パッチの形状を形成する処理や、曲面パッチ内部の色値の計算処理に用いている。
【００１０】
例えば、非特許文献１、２では、曲面パッチの辺が３次のＢｅｚｉｅｒ曲線又は当該曲線と等価な曲線が用いられている。また、非特許文献１では、画素位置（ｘ，ｙ）及び当該画素位置の色値ｈを変数としたときに、（ｘ，ｙ，ｈ）をＦｅｒｇｕｓｏｎパッチで表し、非特許文献２では、曲面パッチの形状（ｘ，ｙ）をＢｅｚｉｅｒ曲線で表し、画素位置（ｘ，ｙ）での色値を薄板スプライン補間手法を用いて計算している。
【００１１】
パラメトリック曲線は、一般に、画面の横軸方向の位置のパラメータをｕ（０≦ｕ≦１の実数）とし、縦軸方向の位置のパラメータをｖ（０≦ｖ≦１の実数）として、（ｕ，ｖ）で定まる点での位置ベクトルを（ｘ，ｙ，ｈ）とするベクトルデータで表現される。なお、ｘ，ｙ，ｈは、それぞれ、当該点における局所座標系のｘ軸，ｙ軸，ｈ軸のベクトル成分であり、（ｘ，ｙ）は曲面パッチ上の点の位置を意味し、ｈは（ｘ，ｙ）での色値を意味する。
【００１２】
そして、上記パラメータは、ｕ＝（ｕ，ｖ）や、添え字を付したｕｉ＝（ｕｉ，ｖｉ）等で表現され、ｘ，ｙ，ｈは、その表現形式を用いて以下の式（１）〜式（３）から計算される。
【００１３】
ｘｉ＝ｘ（ｕｉ，ｖｉ） ・・・式（１）
ｙｉ＝ｙ（ｕｉ，ｖｉ） ・・・式（２）
ｈｉ＝ｈ（ｕｉ，ｖｉ） ・・・式（３）
これら数式上はパラメータｕ，ｖに該当する位置を先に計算するように思われるが、実際にベクトルデータを画像としてレンダリング（色値の計算等）して表示する際には、曲面パッチ上の画素位置（ｘ，ｙ）を指定し、その位置でのパラメータ（ｕ，ｖ）の値を計算した上で、算出された（ｕ，ｖ）に対応する色値ｈ（ｕ，ｖ）を計算することになる。
【００１４】
このため、非特許文献１、２に開示されたようなベクトルデータを用いて画面を表示する方法は、同じサイズ（解像度）を持つビットマップ画像の表示に比べて計算コストが多大になる。
【００１５】
そこで、オブジェクトに対して近似的にあてはめられた複数の曲面パッチに識別子をそれぞれ付与し、編集する単位を指定されたオブジェクトに限定することにより、計算コストの低減を図る方法が用いられている。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】Yu-Kun Lai、外２名、“Automatic and Topology-Preserving Gradient Mesh Generation for Image Vectorization”、ACM Transactions on Graphics、Vol.28、No.3(SIGGRAPH 2009)、2009年8月、Article 85:1-8
【非特許文献２】Tian Xia、外２名、“Patch-based Image Vectorization with Automatic Curvilinear Feature Alignment”、ACM Transactions on Graphics、Vol.28、No.5(SIGGRAPH Asia 2009)、2009年12月、Article 115:1-10
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、利用される曲面パッチは曲線（パラメトリック曲線）により形成されるパラメトリック曲面により構成されているため、画像内のオブジェクトを変形するような場合には、曲面パッチの形状や曲面パッチ内部の色値の再計算に多くの処理時間を必要とし、変形後の画像の表示速度が遅いという問題があった。
【００１８】
本発明は、上記を鑑みてなされたものであり、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することを課題とする。
【課題を解決するための手段】
【００１９】
請求項１に記載の画像処理装置は、ビットマップ画像内のオブジェクトをパラメトリック曲面で近似した矩形又は三角形の曲面パッチのベクトルデータを記憶しておく記憶手段と、前記記憶手段からベクトルデータを読み出して、前記曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成する生成手段と、前記曲面パッチの２つの頂点を結ぶ曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分で前記プリミティブパッチを分割する分割手段と、前記ビットマップ画像の各画素に対応する配列データを生成し、分割されたプリミティブパッチの内部領域に対応する位置にプリミティブパッチを識別する識別子を格納する格納手段と、指定された画素位置に対応する識別子を前記配列データから取得し、取得された前記プリミティブパッチの識別子を用いて処理する処理手段と、を有することを特徴とする。
【００２０】
本発明によれば、辺がパラメトリック曲線で構成される曲面パッチではなく、直線境界を有するプリミティブパッチの識別子を用いて処理するため、レンダリングに係る計算コストを低減し、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。
【００２１】
請求項２に記載の画像処理装置は、請求項１に記載の画像処理装置において、頂点移動後のプリミティブパッチに対応する画素の色値を、当該頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、当該頂点及び当該サンプリング点の更新前の色値とを用いて決定することを特徴とする。
【００２２】
請求項３に記載の画像処理方法は、コンピュータにより行う画像処理方法において、ビットマップ画像内のオブジェクトをパラメトリック曲面で近似した矩形又は三角形の曲面パッチのベクトルデータを記憶手段に記憶しておくステップと、前記記憶手段からベクトルデータを読み出して、前記曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成するステップと、前記曲面パッチの２つの頂点を結ぶ曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分で前記プリミティブパッチを分割するステップと、前記ビットマップ画像の各画素に対応する配列データを生成し、分割されたプリミティブパッチの内部領域に対応する位置にプリミティブパッチを識別する識別子を格納するステップと、指定された画素位置に対応する識別子を前記配列データから取得し、取得された前記プリミティブパッチの識別子を用いて処理するステップと、を有することを特徴とする。
【００２３】
本発明によれば、辺がパラメトリック曲線で構成される曲面パッチではなく、直線境界を有するプリミティブパッチの識別子を用いて処理するため、レンダリングに係る計算コストを低減し、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。
【００２４】
請求項４に記載の画像処理方法は、請求項３に記載の画像処理方法において、頂点移動後のプリミティブパッチに対応する画素の色値を、当該頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、当該頂点及び当該サンプリング点の更新前の色値とを用いて決定することを特徴とする。
【００２５】
請求項５に記載の画像処理プログラムは、請求項３又は４に記載の画像処理方法における各ステップをコンピュータに実行させることを特徴とする。
【発明の効果】
【００２６】
本発明によれば、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。
【図面の簡単な説明】
【００２７】
【図１】画像処理装置の機能ブロック構成を示す図である。
【図２】画像処理装置の動作フローを示す図である。
【図３】ビットマップ画像の近似例及びラベルデータ例を示す図である。
【図４】ベクトルデータ例を示す図である。
【図５】ベクトルデータ例を示す図である。
【図６】曲線エッジを線分で近似する例を示す図である。
【図７】曲面パッチとパラメトリックパッチとの相関関係を示す図である。
【図８】曲線エッジの分割例を示す図である。
【図９】曲線エッジとプリミティブパッチの分割例を示す図である。
【図１０】プリミティブパッチの頂点移動例を示す図である。
【図１１】頂点移動後のプリミティブパッチの曲線、頂点、制御点の修正例を示す図である。
【図１２】頂点移動後の分割されたプリミティブパッチの曲線、頂点、制御点の修正例を示す図である。
【図１３】パラメトリック曲面での近似例を示す図である。
【発明を実施するための形態】
【００２８】
以下、三角形の曲面パッチ及び三角形のプリミティブパッチ（後述）を一例に用いて、本発明を実施する一実施の形態について説明する。但し、本発明は多くの異なる様態で実施することが可能であり、本実施の形態の記載内容に限定して解釈すべきではない。
【００２９】
すなわち、矩形の曲面パッチや矩形のプリミティブパッチを用いた場合であっても同様の作用効果を得ることができる。以下、三角形又は矩形の曲面パッチを単に曲面パッチといい、三角形又は矩形のプリミティブパッチを単にプリミティブパッチという。
【００３０】
また、曲面パッチの一辺を構成しているパラメトリック曲線は、Ｂｅｚｉｅｒ曲線（ベジェ曲線）や有理Ｂｅｚｉｅｒ曲線に代表されるが、その一辺を曲線ならしめる定理については何ら制限されない。
【００３１】
図１は、本実施の形態に係る画像処理装置の機能ブロック構成を示す図である。この画像処理装置は、データ記憶部１１と、ベクトルデータ読込／表示部１２と、識別子付与部１３と、第１ラベルデータ生成／記憶部１４と、識別子取得部１５と、画像処理部１６と、ベクトルデータ更新部１７と、プリミティブパッチ生成部１８と、曲線エッジ／線分エッジ評価部１９と、パラメトリック曲線分割部２０と、プリミティブ画像生成／表示部２１と、第２ラベルデータ生成／記憶部２２と、頂点移動受入部２３と、プリミティブ画像更新／表示部２４と、第２ラベルデータ更新／記憶部２５とで構成されている。
【００３２】
データ記憶部１１は、元のビットマップ画像内のオブジェクトをパラメトリック曲面で近似した曲面パッチを構成するベクトルデータを記憶しておく機能を有している。
【００３３】
ベクトルデータ読込／表示部１２は、データ記憶部１１のベクトルデータを読み込んで、そのベクトルデータを用いて曲面パッチを生成し、生成された曲面パッチに基づいてビットマップ画像（ラスタ画像）を生成して、ディスプレイに表示する機能を有している。すなわち、元のビットマップ画像に基づいて数値化・関数化されたベクトルデータから元のビットマップ画像を近似的に再現する機能を有している。
【００３４】
識別子付与部１３は、ベクトルデータ読込／表示部１２でのビットマップ画像生成中に生成された曲面パッチや当該曲面パッチを構成している辺（以下、曲線エッジ）に対して、各曲面パッチや各曲線エッジをそれぞれ識別する識別子を付与する機能を有している。
【００３５】
第１ラベルデータ生成／記憶部１４は、元のビットマップ画像と同サイズであって、そのビットマップ画像の各画素にそれぞれ対応するデータ領域を有する２次元配列データ（以下、第１ラベルデータ）を生成し、識別子付与部１３により付与された曲面パッチの識別子を曲面パッチの内部領域に対応する各位置にそれぞれ記憶（格納）する機能を有している。
【００３６】
識別子取得部１５は、ユーザによる編集処理要求を受け入れて、その要求により指定された画素範囲に対応するオブジェクトのパッチの識別子を第１ラベルデータ又は第２ラベルデータ（後述）から取得する機能を有している。
【００３７】
画像処理部１６は、識別子取得部１５で取得したパッチの識別子を用いて要求に応じた所定の処理（オブジェクトの選択、選択領域の拡大や縮小、頂点移動等の画像処理）を行う機能を有している。
【００３８】
ベクトルデータ更新部１７は、画像処理部１６の処理により修正等されたベクトルデータを用いて、データ記憶部１１のベクトルデータを更新（修正や追記等）する機能を有している。
【００３９】
プリミティブパッチ生成部１８は、曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成する機能を有している。
【００４０】
曲線エッジ／線分エッジ評価部１９は、曲面パッチの２つの頂点を結ぶ曲線エッジと、その曲線エッジに対応するプリミティブパッチの辺（以下、線分エッジ）との距離の差（エッジ成分長の差）を評価する機能を有している。
【００４１】
パラメトリック曲線分割部２０は、曲線エッジ／線分エッジ評価部１９での距離の差の評価に基づいて曲面パッチの曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分でプリミティブパッチを分割する機能を有している。
【００４２】
プリミティブ画像生成／表示部２１は、ベクトルデータ読込／表示部１２で生成された曲面パッチに基づくビットマップ画像からプリミティブパッチ（分割されたプリミティブパッチを含む）の内部領域に対応する画素位置の色値を取得し、プリミティブパッチに基づくプリミティブ画像を生成して、ディスプレイに表示する機能を有している。
【００４３】
第２ラベルデータ生成／記憶部２２は、第１ラベルデータ生成／記憶部１４と同様な領域を有する第２ラベルデータを生成し、プリミティブパッチ（分割されたプリミティブパッチを含む）の内部領域に対応する位置にプリミティブパッチを識別する識別子を記憶（格納）する機能を有している。
【００４４】
頂点移動受入部２３は、プリミティブ画像上において移動対象のプリミティブパッチの頂点の指定とその移動量を受け入れる機能を有している。
【００４５】
プリミティブ画像更新／表示部２４は、プリミティブパッチの頂点移動後の位置や移動量に基づいてプリミティブ画像を更新し、ディスプレイに表示する機能を有している。
【００４６】
第２ラベルデータ更新／記憶部２５は、プリミティブ画像の更新に伴って第２ラベルデータ内のプリミティブパッチの識別子を更新（修正等）する機能を有している。
【００４７】
次に、図２を参照しながら、本実施の形態に係る画像処理装置の動作について説明する。
【００４８】
最初に、曲面パッチに基づく処理方法について説明する。なお、本発明は、後述する線分によるプリミティブパッチに基づく処理方法を主な特徴とするが、当該処理方法は曲面パッチに基づいて生成された画像を利用することから、曲面パッチの処理方法を先に説明する。
【００４９】
まず、ベクトルデータ読込／表示部１２が、データ記憶部１１に記憶されているベクトルデータを読み込み、そのベクトデータを用いて曲面パッチの形状を生成し曲面パッチ内部の色値を補間することにより、指定された画像サイズでのビットマップ画像を生成する（Ｓ１０１、Ｓ１０３）。生成されたビットマップ画像例については図３（ａ）を参照されたい。
【００５０】
なお、ベクトルデータを用いビットマップ画像を生成する方法については、非特許文献２に記載されているため、その説明は省略する。
【００５１】
また、画像サイズが指定される理由については、ベクトルデータは生成されるビットマップ画像のサイズに依存しないため、画像を生成するにあたっては画像のサイズを必要とするからである。一般に、横方向がＷ（１以上の自然数）の画素、縦方向がＨ（１以上の自然数）の画素とされる。
【００５２】
ここで、ベクトルデータについて説明する。ここでのベクトルデータとは、曲面パッチを構築する関数を決定するための条件となるデータであり、例えば、図４に示すように、曲面パッチを構成する頂点のＩＤ、頂点の座標位置、頂点の色値等からなるデータテーブルや、曲面パッチの曲線エッジを制御する制御点、色補間する際に利用するサンプリング点等からなるデータテーブルにより構成されている。なお、ベクトルデータの書式や形式は任意に設定可能であり、その方式については何ら制限はない。
【００５３】
図２に戻り、ビットマップ画像を生成する際において、識別子付与部１３が、生成された複数の曲面パッチや各曲面パッチの複数の曲線エッジに対して識別子をそれぞれ付与する（Ｓ１０２）。
【００５４】
なお、このように付与される識別子としては、適宜採番した値を割り当てても良いし、ベクトルデータ内に識別子が含まれている場合には当該識別子を利用するようにしても良い。
【００５５】
次いで、ユーザによる編集処理がパッチ選択のみの場合には、第１ラベルデータ生成／記憶部１４が、元のビットマップ画像に対応する第１ラベルデータを生成し、識別子付与部１３によって付与された曲面パッチの識別子を当該曲面パッチの内部領域に対応する各位置にそれぞれ記憶する（Ｓ１０４、Ｓ１０５）。生成された第１ラベルデータ例については図３（ｂ）を参照されたい。
【００５６】
具体的には、各曲面パッチが占有する画像に対応する位置（ｉ，ｊ）（０≦ｉ＜Ｗ，０≦ｊ＜Ｈ）と当該位置での色値がそれぞれ計算されるので、例えばＴの識別子が付与された曲面パッチについては、計算された全ての位置（ｉ，ｊ）に対してＴを代入することにより第１ラベルデータを生成する。
【００５７】
次いで、ベクトルデータ読込／表示部１２が、Ｓ１０３で生成したビットマップ画像をディスプレイ上に表示する（Ｓ１０６）。
【００５８】
その後、識別子取得部１５が、ディスプレイに表示されたビットマップ画像に対する曲面パッチの選択処理を受け入れ、その選択により指定された画素範囲に対応する曲面パッチの識別子をＳ１０５で生成した第１ラベルデータから取得して、画像処理部１６が、その取得した曲面パッチの識別子を用いて処理を行う（Ｓ１０７〜Ｓ１０９）。
【００５９】
Ｓ１０８において曲面パッチの識別子を取得することにより、例えば複数の曲面パッチをまとめて一つのオブジェクトとして扱い、何らかのタグ情報を付与することができる。読み込んだベクトルデータに対して当該タグ情報を付与することにより、新たな情報をベクトルデータに追加することが可能となる。
【００６０】
例えば、（タグＩＤ，パッチ１のＩＤ，パッチ２のＩＤ，パッチ３のＩＤ，…）のようなリストをベクトルデータに付与することにより、当該タグＩＤを有するパッチＩＤを一度に取得することが可能となる。
【００６１】
最後に、ベクトルデータ更新部１７が、Ｓ１０９により更新されたベクトルデータを用いてデータ記憶部１１のベクトルデータを更新する（Ｓ１１０）。
【００６２】
なお、Ｓ１０７〜Ｓ１１０は、曲面パッチの選択処理が終了するまで繰り返される（Ｓ１１１）。
【００６３】
また、選択した曲面パッチを分かり易く示すために、ビットマップ画像上で選択された曲面パッチの色を変更するようにしてもよい。例えば、第１ラベルデータ上で同一識別子を有する位置に対応する画素位置の色値を同一色にすることにより実現する。
【００６４】
以上が曲面パッチに基づく基本的な処理方法である。パッチ選択等の識別子を扱う処理のみであればこれまで説明した処理方法でも良いが、ビットマップ画像内のオブジェクトを変形するような場合、すなわち、曲面パッチを構成する頂点を移動する場合には、移動後の曲面パッチの形状や内部の色値を再計算するのに多くの計算コストを必要とする。
【００６５】
ゆえに、その場合には、一般に高速に処理できる線分エッジを有するプリミティブ（ポリゴン：線分の辺を持つ三角形や矩形等の多角形）状のプリミティブパッチを用いて処理を行う。以下、プリミティブパッチに基づく処理方法について、引き続き図２を参照しながら説明する。
【００６６】
Ｓ１０４での判断処理において、ユーザによる編集処理がパッチ選択のみでない場合には、その選択された曲面パッチの曲線エッジにおいて未だ処理されていない曲線エッジがあるかどうかを判断し、未処理の曲線エッジがある場合には、ベクトルデータ読込／表示部１２及び識別子付与部１３が、データ記憶部１１のベクトルデータを用いて、曲面パッチや曲線エッジに関する情報リストを生成する（Ｓ１０４、Ｓ２０１〜Ｓ２０２）。生成されたリスト例については図５を参照されたい。このようなリストを予めデータ記憶部１１に記憶しておくようにしてもよい。
【００６７】
なお、図５に示す親パッチＩＤとは、後述の分割時に新たに生成されたパッチがどのパッチに属していたかを示す識別子である。また、親エッジＩＤとは、同様に、後述する分割時に新たに生成されたエッジがどのエッジに属していたかを示す識別子である。
【００６８】
次いで、図２に戻り、プリミティブパッチ生成部１８が、Ｓ２０２で生成された各リスト内のベクトルデータを用いて、曲面パッチの頂点を線分で結んだプリミティブパッチを生成する（Ｓ２０３）。
【００６９】
ここで、パラメトリック曲面の曲面パッチから線分のプリミティブパッチを生成する手法としては、図６（ｂ）に示すような輪郭をパラメトリック曲線とし内部のみを線分で結んで多角形を生成する方法や、図６（ｃ）に示すような輪郭をも線分で結んで多角形を生成する方法が挙げられる。ラベルデータの生成についても当該多角形を基準にして識別子を記憶することにより、いずれの方法であっても、頂点を移動した場合でも色値等の再計算コストを低減することができる。
【００７０】
ここで、図７に示すように、頂点の位置が同じであっても、元のベクトルデータが表している曲面パッチとプリミティブパッチとでは指定された画素位置の識別子が異なる場合がある。
【００７１】
そこで、図２に戻り、曲線エッジ／線分エッジ評価部１９が、曲面パッチを構成する曲線エッジの曲線距離と、その曲線エッジに対応するプリミティブパッチの線分エッジの直線距離との差を計算し、その距離の差が所定の閾値よりも大きい場合には、パラメトリック曲線分割部２０が、その曲線エッジを中点で分割する（Ｓ２０４〜Ｓ２０６）。
【００７２】
ここで、図８を参照しながら、距離の差の評価方法について説明する。例えば、２点間のチェス盤距離により評価することができる。２つの頂点ｖ１（ｘ１，ｙ１），ｖ２（ｘ２，ｙ２）のチェス盤距離ｄは以下の式（４）のように定義できる。
【００７３】
ｄ（ｖ１，ｖ２）＝ｍａｘ（｜ｘ１−ｘ２｜，｜ｙ１−ｙ２｜） ・・・式（４）
そして、曲線を構成する２つの頂点ｖ１，ｖ２と２つの制御点ｃ１，ｃ２とがｖ１，ｃ１，ｃ２，ｖ２の順に並んでいる場合には、曲線エッジの曲線距離を式（５）で算出し、線分エッジの直線距離については式（６）で算出する。
【００７４】
ｄ１＝ｄ（ｖ１，ｃ１）＋ｄ（ｃ１，ｃ２）＋ｄ（ｃ２，ｖ２） ・・・式（５）
ｄ２＝ｄ（ｖ１，ｖ２） ・・・式（６）
その後、ｄ１とｄ２との差が予め設定された所定の閾値よりも大きい場合には、曲線エッジを分割する。
【００７５】
その他、曲線エッジが式（１）〜式（３）において（ｕ，ｖ＝０）の位置で表されるような場合には、（ｕ＝１／２，ｖ＝０）の位置で分割するしてもよい。
【００７６】
なお、このようにパラメトリック曲線を分割する方法、すなわち、曲線形状を保持したままセグメント数を増やす方法については、「Curves and Surfaces for CAGD; 5th edition」（Gerald Farin著、Academic Press, 2002）（以下、参考文献１）に示されているように周知の技術である。
【００７７】
ここで、曲線エッジを分割すると、その曲線エッジを境界に有する２つのパッチに影響が及ぶため、プリミティブパッチを生成する前に、全ての曲線エッジについて分割するかどうかを判定し、分割対象と判断された曲線エッジを予め分割しておくようにしてもよい。
【００７８】
次いで、図２に戻り、パラメトリック曲線分割部２０が、上記参考文献１に記載された分割手法を利用して分割された各曲線エッジの制御点をそれぞれ生成し、各制御点について新たなＩＤを付与して、分割前の曲線エッジのＩＤに関連付けてデータテーブルに追加する（Ｓ２０６）。
【００７９】
次いで、パラメトリック曲線分割部２０が、分割された曲線エッジ上の分割点と、当該曲線エッジを境界に有する２つのプリミティブパッチの他の頂点（曲線エッジを構成する両頂点ではない頂点）とを結んで新たなエッジを追加し、その追加された新たなエッジでそれら２つのプリミティブパッチをそれぞれ分割し、分割されたプリミティブパッチやエッジについて新たなＩＤを付与し、分割前の曲線エッジのＩＤに関連付けてデータテーブルに追加する（Ｓ２０６〜Ｓ２０８）。
【００８０】
なお、Ｓ２０６の分割手順については図９を参照されたい。新たに追加されたエッジについては、特に曲線と対応付ける必要はなく、制御点を持たなくてもよい。
【００８１】
ここで、１つのパッチを構成する２つのエッジを分割する際は注意が必要である。あるパッチの頂点ｖ１，ｖ２，ｖ３がエッジｅ１＝（ｖ２，ｖ３），ｅ２＝（ｖ３，ｖ１），ｅ３＝（ｖ１，ｖ２）を有するとき、ｅ１を分割後にｅ２を分割した場合と、逆にｅ２を分割後にｅ１を分割した場合とでは分割結果が異なる場合がある。そこで、ある特定のプリミティブパッチのみを考慮するような場合には、そのパッチを構成するエッジの中で距離の差が大きいエッジから優先して分割し、分割が一意的になるようにしてもよい。また、すべてのパッチのエッジについて距離の際を事前に評価しておき、その距離の差が大きいものから順に分割し、エッジの分割が完了してからプリミティブパッチを分割してもよい。
【００８２】
なお、分割後のエッジについても距離の差が所定の閾値を超える場合には、当該距離の差が所定の閾値以下になるまで分割後のエッジを更に分割することを繰り返すようにしてもよいし、その分割回数を予め決めておくようにしてもよい。
【００８３】
次いで、プリミティブ画像生成／表示部２１が、Ｓ１０３で生成した曲面パッチに基づくビットマップ画像から、Ｓ２０３及びＳ２０６で生成されたプリミティブパッチの内部領域に対応する画素位置の色値を取得して、プリミティブパッチに基づくプリミティブ画像を生成する（Ｓ２０９）。生成されたプリミティブ画像例については図３（ｃ）を参照されたい。
【００８４】
なお、このプリミティブ画像は、Ｓ１０３で生成したビットマップ画像をそのまま用いても良いし、その複製を用いてもよい。
【００８５】
次いで、第２ラベルデータ生成／記憶部２２が、プリミティブ画像に対応する第２ラベルデータを生成し、プリミティブパッチの識別子をプリミティブパッチ（分割されたプリミティブパッチを含む）の内部領域に対応する各位置にそれぞれ記憶する（Ｓ２１０）。生成された第２ラベルデータ例については図３（ｄ）を参照されたい。
【００８６】
次いで、プリミティブ画像生成／表示部２１が、Ｓ２０９で生成したプリミティブ画像をディスプレイ上に表示する（Ｓ２１１）。
【００８７】
その後、識別子取得部１５が、ディスプレイに表示されたプリミティブ画像に対するプリミティブパッチの選択処理を受け入れ、その選択により指定された画素範囲に対応するプリミティブパッチの識別子をＳ２１０で生成した第２ラベルデータから取得して、画像処理部１６が、その取得したプリミティブパッチの識別子を用いて処理を行う（Ｓ２１２〜Ｓ２１４）。
【００８８】
最後に、ベクトルデータ更新部１７が、Ｓ２１４によって更新されたベクトルデータを用いてデータ記憶部１１のベクトルデータを更新する（Ｓ２１５）。
【００８９】
なお、Ｓ２１２〜Ｓ２１５は、プリミティブパッチの選択処理が終了するまで繰り返される（Ｓ２１６）。
【００９０】
また、曲面パッチをプリミティブで近似したプリミティブパッチについてのラベルデータであることから、図７を用いて説明したように、エッジ付近では正確な識別子ではなく隣接する識別子が取得される可能性があるが、プリミティブエッジによるラベル表現は後述する頂点の移動を高速に実現できるという効果がある。
【００９１】
引き続き図２を参照しながら、プリミティブパッチの頂点が移動した場合の動作について説明する。
【００９２】
Ｓ２１３の後、頂点移動受入部２３が、Ｓ２１１で表示されたプリミティブ画像上において、移動させる頂点座標の指定とその移動量を受け入れる（Ｓ３０１）。
【００９３】
次いで、プリミティブ画像更新／表示部２４が、Ｓ３０１で受け入れた移動後の位置や移動量に基づいてプリミティブ画像を修正する（Ｓ３０２）。
【００９４】
図１０に示したように、プリミティブパッチの頂点移動は頂点を共有する複数のプリミティブパッチに影響を与えるが、プリミティブパッチ内の色値は頂点移動によってプリミティブパッチの形状に変形が生じても容易に計算可能である。
【００９５】
例えば、頂点の移動については、上記参考文献１に示されたアファイン変換を用いることにより、移動後のプリミティブパッチ内部の座標値が移動前のどの位置から移動されたのかを容易に計算することができる。また、色値については、移動前の位置の色値を用いることにより、容易に計算することができる。
【００９６】
また、Ｓ３０２と同時に、第２ラベルデータ更新／記憶部２５が、Ｓ３０２での更新に伴って、第２ラベルデータ内のプリミティブパッチの識別子を修正する（Ｓ３０３）。移動対象となる頂点を含むプリミティブパッチのみ識別子を修正するため低コストで実現できる。
【００９７】
最後に、Ｓ２１５に進み、ベクトルデータ更新部１７が、Ｓ３０１で受け入れた移動後の位置や移動量に基づいてデータ記憶部１１のベクトルデータを更新する。
【００９８】
ここで、図１１又は図１２を参照しながら頂点移動があった場合のベクトルデータの更新例について説明する。図１１では、頂点とその頂点に関わる曲線エッジが示されている。曲線エッジを線分エッジで近似しても、制御点があれば曲線を容易に復元することができる。
【００９９】
図１１において、ｖ２の頂点をｖ２ａに移動させることにより、ｅ１の線分エッジをｅ１ａに移動させたとする。このとき、もとの曲線エッジを構成するための頂点ｖ１、ｖ２及び制御点ｃ１、ｃ２も影響を受けるが、本発明においては、ｖ２とｖ２に近い制御点ｃ２のみを移動させ、当該移動対象のみのベクトルデータを更新する。一方、ｃ２が位置的に決まらない場合はｃ２を移動させなくてもよいが、例えば、ｖ１とｃ２ａのユークリッド距離とｖ１とｃ２ａのユークリッド距離とが変化しないという拘束条件を用いてｃ２ａの座標値を決めてもよい。
【０１００】
図１２では、分割されたプリミティブパッチの頂点が移動する場合が示されている。この場合であっても、分割点において曲線エッジがなめらかに接続されていることから、上記と同様に、移動した頂点に近い方の制御点のみを移動させ、当該移動対象のみのベクトルデータを更新する。これにより、分割点においてエッジのなめらかな接続を保持することができる。
【０１０１】
すなわち、図２のＳ２１５において、ベクトルデータ更新部１７は、エッジが分割されていないパッチについては、移動対象の頂点と当該頂点に近い制御点のみのベクトルデータを更新する。
【０１０２】
また、必要に応じて、更新後のプリミティブ画像から適当なサンプリング点を抽出し、パッチ補間に必要な点座標と当該点座標における色値とを取得して、頂点移動後のプリミティブパッチに対応する画素の色値を決定して、ベクトルデータに追記してもよい。例えば、頂点移動後のプリミティブパッチに対応する画素の色値を、頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、その頂点及びサンプリング点の更新前の色値とを用いて決定して、ベクトルデータに追記する。
【０１０３】
一方、エッジが分割されたパッチについては、分割により増加したパッチについて、そのパッチを構成する頂点、制御点、サンプリング点、それら各点の色値をベクトルデータにそれぞれ追記する。また、増加した２以上のパッチの２以上の曲線エッジが１つのパラメトリック曲線で表すことができるように頂点及び制御点した後に、頂点、制御点、サンプリング点、それら各点の色値をベクトルデータにそれぞれ追記してもよい。
【０１０４】
また、必要に応じて、更新後のプリミティブ画像から適当なサンプリング点を抽出し、パッチ補間に必要な点座標と当該点座標における色値とを取得して、頂点移動後のプリミティブパッチに対応する画素の色値を決定して、ベクトルデータに追記してもよい。例えば、頂点移動後のプリミティブパッチに対応する画素の色値を、頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、その頂点及びサンプリング点の更新前の色値とを用いて決定して、ベクトルデータに追記する。
【０１０５】
なお、接続されている複数の曲線を１のパラメトリック曲線で近似する方法は、例えば、複数の曲線を構成する頂点や当該曲線上の適当な点を選定し、その頂点と適当な点を通るようなパラメトリック曲線を得られる制御点位置を計算しても良い。このような近似手法はデータフィッティングと呼ばれるものであり、例えば「An Algorithm for Automatically Fitting Digitized Curves」（Philip J. Schneider著、Graphics Gems, Morgan Kaufmann Publishers, pp.612-626, 1990.）に示されているように周知の技術である。
【０１０６】
本実施の形態によれば、エッジがパラメトリック曲線で構成される曲面パッチではなく、直線境界を有するプリミティブパッチの識別子を用いて処理するので、レンダリングに係る計算コストを低減し、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することができる。また、高速表示に基づいて編集作業を元のベクトルデータに反映することができる。
【０１０７】
以下、そのように直線境界を有するプリミティブパッチの識別子を用いることによって得られる当該効果への作用について詳述しておく。
【０１０８】
辺がパラメトリック曲線で構成された曲面パッチによって構成された画像（これは、元のビットマップ画像を辺がパラメトリック曲線で構成された曲面パッチによって過不足なく分割されることと等価）を画面上にレンダリング（描画）する際は、ビットマップ画面上の各画素に対応する位置の色値を計算によって決定するが、この「各画素に対応する位置」がどの曲面パッチに属しているかを決定するのは容易ではない。
【０１０９】
これは、ある画素をひとつ選んだとしても、それがひとつの曲面パッチの内部にあるのか外部にあるのかを判定することですら、多くの計算を要するからである。例えば、ある位置（ｘ，ｙ）の画素が曲面パッチＰ１に含まれるか否かを判定するには、上記式（１）や式（２）から（ｕ，ｖ）の値を例えばニュートン−ラフソン法等を用いて数値計算によって近似的に求め、それが０≦ｕ≦１、０≦ｖ≦１にあるかどうかを評価することで判定することが一般的である。
【０１１０】
しかしながら、曲面パッチＰ１に含まれていなければ、別の曲面パッチＰ２について同様の計算を行うなど、当該画素を含む曲面パッチを見つけるまでこの判定を繰り返すことになる。
【０１１１】
これと同じ理由により、曲面パッチで構成された画像上で、ある画素をユーザが選択した際、それがどの曲面パッチの内部なのかを判定するのは容易ではない。
【０１１２】
そこで、曲面パッチによるベクトル化画像をレンダリングする際に、同時に曲面パッチの識別子を第１ラベルデータに書き込んでいき、画像生成後ある画素が選択された場合には、上記数式を用いた数値解析に基づく曲面パッチの内外判定ではなく、この第１ラベルデータ上の当該位置に格納されている識別子によって判定することにより、直ちに当該画素位置を含む曲面パッチを特定可能となる。
【０１１３】
しかしながら、この方法では、曲面パッチを変形させるなどの編集を加えた場合に、変形後の新しい画像をレンダリングするのも前述の理由により時間がかかるため、効率が良いとまではいえない。
【０１１４】
これに対し、辺が直線（線分）で構成されたプリミティブパッチは、比較的簡単な計算で、ある点が内部か外部かを判定することが可能となる。具体的には、三角形の内部に含まれるかどうかを単純に計算すればよく、矩形の場合には２つの三角形に対角線で分けて同じ計算を２回行えばよい。更には、第２ラベルデータに格納した識別子を内外判定に用いれば、そのような計算すら不要となる。また、プリミティブパッチ変形後の色の再計算や第２ラベルデータの更新についても画素の内外判定が容易なため、曲面パッチに比べて極めて少ない計算量で済むことになる。
【０１１５】
従って、レンダリングに係る計算コストを低減することが可能となり、画質をできるだけ損なうことなく高速にベクトル化された画像を表示し編集することが可能となる。
【０１１６】
最後に、本実施の形態で説明した画像処理装置はコンピュータで構成される。すなわち、画像処理装置を構成している各処理機能部は、メモリやハードディスク等の記憶手段、ＣＰＵ等の演算手段で実現され、プログラムで実行される。
【０１１７】
また、本実施の形態で説明した画像処理装置をプログラムとして光記憶装置や磁気記憶装置等の記録媒体に読出可能に記録し、この記録媒体をコンピュータに組み込んだり、若しくは記録媒体に記録されたプログラムを、任意の通信回線を介してコンピュータにダウンロードしたり、又は記録媒体からインストールし、該プログラムでコンピュータを動作させることにより、上述した各動作を画像処理装置として機能させることができるのは勿論である。
【符号の説明】
【０１１８】
１１…データ記憶部
１２…ベクトルデータ読込／表示部
１３…識別子付与部
１４…第１ラベルデータ生成／記憶部
１５…識別子取得部
１６…画像処理部
１７…ベクトルデータ更新部
１８…プリミティブパッチ生成部
１９…曲線エッジ／線分エッジ評価部
２０…パラメトリック曲線分割部
２１…プリミティブ画像生成／表示部
２２…第２ラベルデータ生成／記憶部
２３…頂点移動受入部
２４…プリミティブ画像更新／表示部
２５…第２ラベルデータ更新／記憶部
Ｓ１０１〜Ｓ１１１、Ｓ２０１〜Ｓ２１６、Ｓ３０１〜Ｓ３０３…ステップ
【特許請求の範囲】
【請求項１】
ビットマップ画像内のオブジェクトをパラメトリック曲面で近似した矩形又は三角形の曲面パッチのベクトルデータを記憶しておく記憶手段と、
前記記憶手段からベクトルデータを読み出して、前記曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成する生成手段と、
前記曲面パッチの２つの頂点を結ぶ曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分で前記プリミティブパッチを分割する分割手段と、
前記ビットマップ画像の各画素に対応する配列データを生成し、分割されたプリミティブパッチの内部領域に対応する位置にプリミティブパッチを識別する識別子を格納する格納手段と、
指定された画素位置に対応する識別子を前記配列データから取得し、取得された前記プリミティブパッチの識別子を用いて処理する処理手段と、
を有することを特徴とする画像処理装置。
【請求項２】
頂点移動後のプリミティブパッチに対応する画素の色値を、当該頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、当該頂点及び当該サンプリング点の更新前の色値とを用いて決定することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
コンピュータにより行う画像処理方法において、
ビットマップ画像内のオブジェクトをパラメトリック曲面で近似した矩形又は三角形の曲面パッチのベクトルデータを記憶手段に記憶しておくステップと、
前記記憶手段からベクトルデータを読み出して、前記曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成するステップと、
前記曲面パッチの２つの頂点を結ぶ曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分で前記プリミティブパッチを分割するステップと、
前記ビットマップ画像の各画素に対応する配列データを生成し、分割されたプリミティブパッチの内部領域に対応する位置にプリミティブパッチを識別する識別子を格納するステップと、
指定された画素位置に対応する識別子を前記配列データから取得し、取得された前記プリミティブパッチの識別子を用いて処理するステップと、
を有することを特徴とする画像処理方法。
【請求項４】
頂点移動後のプリミティブパッチに対応する画素の色値を、当該頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、当該頂点及び当該サンプリング点の更新前の色値とを用いて決定することを特徴とする請求項３に記載の画像処理方法。
【請求項５】
請求項３又は４に記載の画像処理方法における各ステップをコンピュータに実行させることを特徴とする画像処理プログラム。
【請求項１】
ビットマップ画像内のオブジェクトをパラメトリック曲面で近似した矩形又は三角形の曲面パッチのベクトルデータを記憶しておく記憶手段と、
前記記憶手段からベクトルデータを読み出して、前記曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成する生成手段と、
前記曲面パッチの２つの頂点を結ぶ曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分で前記プリミティブパッチを分割する分割手段と、
前記ビットマップ画像の各画素に対応する配列データを生成し、分割されたプリミティブパッチの内部領域に対応する位置にプリミティブパッチを識別する識別子を格納する格納手段と、
指定された画素位置に対応する識別子を前記配列データから取得し、取得された前記プリミティブパッチの識別子を用いて処理する処理手段と、
を有することを特徴とする画像処理装置。
【請求項２】
頂点移動後のプリミティブパッチに対応する画素の色値を、当該頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、当該頂点及び当該サンプリング点の更新前の色値とを用いて決定することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
コンピュータにより行う画像処理方法において、
ビットマップ画像内のオブジェクトをパラメトリック曲面で近似した矩形又は三角形の曲面パッチのベクトルデータを記憶手段に記憶しておくステップと、
前記記憶手段からベクトルデータを読み出して、前記曲面パッチを構成する頂点を線分で結んだプリミティブパッチを生成するステップと、
前記曲面パッチの２つの頂点を結ぶ曲線エッジを分割し、分割された曲線エッジ上の分割点と当該曲面パッチの他の頂点とを結ぶ線分で前記プリミティブパッチを分割するステップと、
前記ビットマップ画像の各画素に対応する配列データを生成し、分割されたプリミティブパッチの内部領域に対応する位置にプリミティブパッチを識別する識別子を格納するステップと、
指定された画素位置に対応する識別子を前記配列データから取得し、取得された前記プリミティブパッチの識別子を用いて処理するステップと、
を有することを特徴とする画像処理方法。
【請求項４】
頂点移動後のプリミティブパッチに対応する画素の色値を、当該頂点移動により更新されたプリミティブの頂点及びプリミティブ画像内のサンプリング点の位置情報と、当該頂点及び当該サンプリング点の更新前の色値とを用いて決定することを特徴とする請求項３に記載の画像処理方法。
【請求項５】
請求項３又は４に記載の画像処理方法における各ステップをコンピュータに実行させることを特徴とする画像処理プログラム。
【図１】
【図２】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図３】
【図１３】
【図２】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図３】
【図１３】
【公開番号】特開２０１２−１２３６５５（Ｐ２０１２−１２３６５５Ａ）
【公開日】平成２４年６月２８日（２０１２．６．２８）
【国際特許分類】
【出願番号】特願２０１０−２７４３７３（Ｐ２０１０−２７４３７３）
【出願日】平成２２年１２月９日（２０１０．１２．９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年６月２８日（２０１２．６．２８）
【国際特許分類】
【出願日】平成２２年１２月９日（２０１０．１２．９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]