画像処理装置、画像処理方法
【課題】 グラディエント・メッシュによるオブジェクトの近似を効率的に行うための技術を提供すること。
【解決手段】 メッシュ構造生成部102は、オブジェクト領域を包含する包含領域を複数のメッシュに分割し、メッシュ毎に、各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める。そして、1以上の頂点がオブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する。そして、オブジェクト領域内メッシュのうち、1以上の頂点がオブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する。そして、補正対象メッシュを構成する頂点群のうちオブジェクト領域の外部に位置している外部頂点の位置情報を、オブジェクト領域の枠部上の位置を示す位置情報に更新する。
【解決手段】 メッシュ構造生成部102は、オブジェクト領域を包含する包含領域を複数のメッシュに分割し、メッシュ毎に、各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める。そして、1以上の頂点がオブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する。そして、オブジェクト領域内メッシュのうち、1以上の頂点がオブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する。そして、補正対象メッシュを構成する頂点群のうちオブジェクト領域の外部に位置している外部頂点の位置情報を、オブジェクト領域の枠部上の位置を示す位置情報に更新する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ラスタ画像をグラディエント・メッシュで近似する際に、複雑な形状のオブジェクトをグラディエント・メッシュで表現するための解像度フリー表現技術に関するものである。
【背景技術】
【0002】
従来、イラストや文字の解像度フリー表現には、オブジェクトの輪郭をベジェ、スプライン関数などで関数近似する手法が用いられている。オブジェクト領域内は、単一色、線形グラデーション、放射状グラデーションなどで塗りつぶすことができるが、複雑なグラデーションの表現は困難である。
【0003】
解像度フリーで複雑なグラデーションを含むオブジェクトを描画するためには、Adobe Illustrator(登録商標)のグラディエント・メッシュ・ツールが一般に用いられている。グラディエント・メッシュでは、メッシュに色と勾配を与えて三次関数を生成することで複雑なオブジェクトを描画することができる(特許文献1、2)。
【0004】
ラスタ画像中のオブジェクトを解像度フリー表現に変換するとき、イラストや文字などの色変化の少ないオブジェクトに関しては、前述のベジェ、スプライン関数を用いた方法により表現できる。
【0005】
自然画像のような色が複雑に変化するオブジェクトを解像度フリー表現に変換する技術は幾つか提案されており、大きく3つのカテゴリに分類できる。三角形メッシュを用いた手法、高次のパラメトリック曲面を用いた手法、メッシュ以外の表現を用いた手法、である。
【0006】
三角形メッシュを用いた方法では、オブジェクトの直線的なエッジを忠実に表現できる。しかし、滑らかな曲線を表現するとき、線形メッシュで曲線を忠実に近似することは困難であり、忠実に近似するためには多数のメッシュを用いなければならない。
【0007】
高次のパラメトリック曲面を用いた手法では、曲線の表現も可能であり、より少ないメッシュ数で特徴曲線を近似することができる。高次のパラメトリック曲面を用いる手法としては、ベジェパッチを細分割して近似誤差を低減する手法(非特許文献1)、グラディエント・メッシュを用いて画像を近似する手法などが挙げられる(特許文献3、非特許文献3)。
【0008】
メッシュ以外の表現を用いた手法では、画像の特徴線をベジェ曲線で近似し、曲線の両側に色情報を付加し、曲線の色を用いた偏微分方程式を解いて画像を描画するディフュージョン・カーブと呼ばれる解像度フリー表現手法が提案されている(非特許文献2)。また、境界曲線と特徴曲線と関連付けられた色を用いてカラー・グラディエントを生成する手法も提案されている(特許文献4)。
【0009】
複雑な形状のオブジェクトをメッシュで近似するために、幾つかの方法が提案されている。パラメトリック曲面を用いた手法(特許文献3、非特許文献3)では、4頂点から成る規則メッシュを生成するため、オブジェクトの近似に頂点を過剰に与えてしまうことがある。また、適応的にメッシュ頂点を除去してオブジェクトを近似する手法(特許文献5)、メッシュの頂点をオブジェクト境界上に移動する手法(特許文献6)では、メッシュを直線で接続しているため、曲線近似が困難であるという課題も残る。
【先行技術文献】
【特許文献】
【0010】
【特許文献1】特開平11−345347号公報
【特許文献2】特許第4220010号公報
【特許文献3】米国特許出願公開第2008/0278479号明細書
【特許文献4】特許第3989451号公報
【特許文献5】特許第2815571号公報
【特許文献6】特開平11−25293号公報
【非特許文献】
【0011】
【非特許文献1】Brian Price,William Barrett,「Object−based vectorization for interactive image editing」,In proceedings of Pacific Graphics 2006,2006,vol.22,no.9−11,p.661−670.
【非特許文献2】Alexandrina Orzan,Adrien Bousseau,Holger Winnemoller,Pascal Barla,Joelle Thollot,David Salesin,「Diffusion Curves:A Vector Representation for Smooth−Shaded Images」,In proceedings of SIGGRAPH 2008,2008,vol.27.
【非特許文献3】Yu−Kun Lai,Shi−Min Hu,Ralph R.Martin,「Automatic and Topology−Preserving Gradient Mesh Generation for Image Vectorization」,ACM SIGGRAPH 2009,ACM Transaction on Graphics,Vol.28,No.3.
【発明の概要】
【発明が解決しようとする課題】
【0012】
自然画像のような色が複雑に変化するオブジェクトを解像度フリー表現に変換するとき、高次のパラメトリック曲面を用いることで、少ないメッシュ数でオブジェクトを近似できる。しかし、オブジェクトの形状が複雑であるとき、表現能力、演算量、データ量について課題も残る。以下にその課題について説明する。
【0013】
上述のベジェパッチを細分割して近似誤差を低減する手法では、高次のメッシュを用いるため、オブジェクト境界の近似を忠実に行うことができる。しかし、近似誤差を低減するためにメッシュを細分割しているため、オブジェクトの色変化が複雑な部分ではメッシュの数が増え、データ量が増大してしまう。
【0014】
上述のグラディエント・メッシュを用いて画像を近似する手法では、色変化が複雑なオブジェクトにおいても、より少ないメッシュ数(データ量)で解像度フリー表現できる。しかしこれらの手法では、4頂点から成る規則メッシュを生成するため、オブジェクトの形状によっては、オブジェクトの色が単純な部分にもメッシュ頂点を過剰に与えてしまうことがある。また、過剰なメッシュ頂点による画質の劣化、演算量の増大などの問題も残る。
【0015】
本発明は以上の問題に鑑みて成されたものであり、グラディエント・メッシュによるオブジェクトの近似を効率的に行うための技術を提供することを目的とする。
【課題を解決するための手段】
【0016】
本発明の目的を達成するために、例えば、本発明の画像処理装置は以下の構成を備える。即ち、画像処理装置であって、画像からオブジェクトの領域をオブジェクト領域として抽出する手段と、前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割手段と、前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める手段と、前記複数のメッシュのうち、該メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第1の特定手段と、前記第1の特定手段が特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第2の特定手段と、前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新手段と、前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理手段とを備えることを特徴とする。
【発明の効果】
【0017】
本発明の構成によれば、グラディエント・メッシュによるオブジェクトの近似を効率的に行うことができる。
【図面の簡単な説明】
【0018】
【図1】画像処理装置の機能構成例を示すブロック図。
【図2】メッシュ構造生成部102が行う処理のフローチャート。
【図3】メッシュ適合部103が行う処理のフローチャート。
【図4】オブジェクト領域の一例を示す図。
【図5】第3の実施形態で扱うオブジェクト領域の一例を示す図。
【図6】ステップS201〜S203を説明する図。
【図7】ステップS301〜S305を説明する図。
【図8】グラディエント・メッシュ表現を説明する図。
【図9】コンピュータのハードウェア構成例を示す図。
【図10】メッシュ構造生成部102が行う処理のフローチャート。
【図11】ステップS1001,S1002における処理を説明する図。
【発明を実施するための形態】
【0019】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載の構成の具体的な実施例の1つである。
【0020】
[第1の実施形態]
図1を用いて、本実施形態に係る画像処理装置の機能構成例について説明する。オブジェクト抽出部101には、1以上のオブジェクトを含む画像が入力される。この「オブジェクト」とは、文字や物体像などを指し示しており、本実施形態では、この「オブジェクト」は、色のグラデーションを有しているものとして説明する。即ち、本実施形態では、色のグラデーションを有するオブジェクトに対するメッシュ符号化を行う。
【0021】
そしてオブジェクト抽出部101は、この入力画像からオブジェクトの領域をオブジェクト領域として抽出する処理を行う。図4に、抽出されたオブジェクト領域の一例を示す。抽出にはグラブ・カット法という既知の方法を用いるが、他の抽出手法を用いても構わない。抽出されたオブジェクト領域のデータには、オブジェクト領域401の内部402を構成する各画素の画素値と、枠部(オブジェクト領域の境界線)403を構成する各画素の座標位置が含まれている。本実施形態では、画素値は、RGBのそれぞれの色成分が8ビットで表現されているものとして説明するが、グレースケール、CMYKなどの色成分の種別、一つの色成分を構成するビット数、についてはこれに限定するものではない。また、オブジェクト領域のデータの構成については、オブジェクト領域の枠部403を構成する各画素の座標位置、オブジェクト領域の内部402を構成する各画素の画素値、が導出できるのであれば、他のデータ構成であっても良い。そしてオブジェクト抽出部101は、抽出したオブジェクト領域のデータを、後段のメッシュ構造生成部102に送出する。
【0022】
図2を用いて、メッシュ構造生成部102が、オブジェクト領域のデータを用いて行う処理について説明する。ステップS201では、メッシュ構造生成部102は、入力画像においてオブジェクト領域を包含する包含領域を求め、求めた包含領域を複数の矩形(メッシュ)に分割することで、この複数のメッシュを生成する。本実施形態では、4つの頂点から構成されるメッシュを生成するが、3つの頂点から構成されるメッシュを生成しても良い。
【0023】
ステップS202ではメッシュ構造生成部102は、ステップS201で生成したそれぞれのメッシュについて頂点データを求める。着目メッシュについて求めた頂点データは着目メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報、で構成されている。また、ステップS202ではメッシュ構造生成部102は、ステップS201で生成した各メッシュを構成する頂点間の接続関係を示す構造データも生成する。
【0024】
ここで、図8を用いて、グラディエント・メッシュ表現について簡単に説明する。グラディエント・メッシュ(メッシュ)は、4つの頂点(頂点0〜頂点3)のそれぞれについての以下の情報によって表現されるものである。
【0025】
・ 頂点i(i=0〜3)の位置情報mi
・ 頂点iにおけるu方向、v方向の勾配情報mui、mvi
・ 頂点iにおける色情報ci
・ 頂点iにおける色のu方向、v方向の勾配情報cui、cvi
図8に示す如く、メッシュの形状は3次関数によって表現され、メッシュ内の座標m(u、v)は以下の式で導出される。
【0026】
【数1】
【0027】
u、vは、0〜1の範囲内の実数である。また、muviは、頂点iにおけるu方向及びv方向の微分値を示すが、一般にはmuviには0を設定する。即ち、メッシュの形状は、頂点の位置情報と勾配情報とによって決まる。なお、勾配情報は、メッシュの輪郭の曲線形状を表していることが分かる。
【0028】
なお、メッシュ内の座標m(u、v)における色Col(u、v)は、以下の置き換え手順1〜3を行ってから、上記の式を計算することで求めることができる。
【0029】
(置き換え手順1) 上記の式において、座標m(u、v)を色Col(u、v)に置き換える
(手順2) 上記の式において、頂点0〜3の位置情報(m0、m1、m2、m3)を、頂点0〜3の色情報(c0、c1、c2、c3)に置き換える
(手順3) 上記の式において、頂点0〜3におけるu方向、v方向の勾配情報(mu0、mv0、mu1、mv1、mu2、mv2、mu3、mv3)を、頂点0〜3における色のu方向、v方向の勾配情報(cu0、cv0、cu1、cv1、cu2、cv2、cu3、cv3)に置き換える。
【0030】
なお、頂点0〜3の色のu方向及びv方向の微分値を示すcuv0、cuv1、cuv2、cuv3には0を設定する。即ち、メッシュ内の色は、頂点の色情報と色の勾配情報とによって決まる。なお、色の勾配情報を0としてレンダリングを行っても良い。本実施形態では、色の勾配情報は0として説明する。
【0031】
上記のようなグラディエント・メッシュ表現は一般に用いられており、その詳細については特許文献3、非特許文献3で説明されているため、これ以上の詳細な説明は省略する。
【0032】
なお、ここではグラディエント・メッシュのメッシュ勾配、及び色勾配の設定方法を示したが、メッシュの形状がパラメトリック曲面として表現され、メッシュ内のグラデーションさえ表現できれば、他の表現方法であっても構わない。例えば、三角形ベジェパッチでメッシュの形状を表現し、メッシュ内の色はRBFs(Radial Basis Functions)曲面で表現するなどの方法を用いても構わない。
【0033】
次に、図6(a)を用いて、ステップS201及びS202における処理を、具体例を挙げて説明する。図6(a)の場合、ステップS201では、メッシュ構造生成部102は、オブジェクト領域401を包含する包含領域690を求め、求めた包含領域690を複数のメッシュに分割する。図6(a)において602は、分割された複数のメッシュのうちの1つを示しており、601は、メッシュ602を構成する頂点群のうちの1つを示している。ここで、頂点601は、オブジェクト領域401の外部に位置している。
【0034】
図6(a)では、包含領域690は長方形であるが、オブジェクト領域を包含する領域であれば、その形状は長方形以外であっても良い。また、図6(a)では、包含領域690を縦横均等に分割しているが、分割方法についてはこれに限定するものではない。
【0035】
次に、ステップS202では、メッシュ構造生成部102は、分割されたそれぞれのメッシュについて、メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める。勾配情報としては何れも0とする。色情報については、頂点がオブジェクト領域401の外部に位置している場合、この頂点の色情報として、0を設定する。一方、頂点がオブジェクト領域401の内部に位置している場合、この頂点の色情報として、この頂点の位置に対応する、オブジェクト領域401上の画素の色情報を設定する。もちろん、頂点がオブジェクト領域401の内部に位置している場合、この頂点の色情報として、この頂点の位置に対応するオブジェクト領域401上の画素の周辺画素の色情報の平均値を設定する等、他の方法を用いて色情報を設定しても良い。また、勾配情報についても、一定値を設定する等、他の方法を用いて勾配情報を設定しても良い。
【0036】
また上記の通り、ステップS202ではメッシュ構造生成部102は、構造データも生成するが、本実施形態では、この構造データには、各メッシュが必要か否かのフラグ情報が含まれている。すべてのメッシュのフラグ情報が「必要」を示している状態が初期状態となる。もちろん、各頂点に番号を振り、必要となるメッシュに4つの頂点番号を保持させてメッシュ構造を表現するなど、他の構造表現を用いても構わない。
【0037】
図2に戻って、ステップS203でメッシュ構造生成部102は、ステップS201で生成したそれぞれのメッシュの各頂点の位置情報を参照する。そしてメッシュ構造生成部102は、ステップS201で得たそれぞれのメッシュのうち「メッシュを構成する頂点群のうち1以上の頂点がオブジェクト領域の内部に位置しているメッシュ」を、オブジェクト領域内メッシュとして特定(第1の特定)する。ここでは、オブジェクト領域を閉領域として定義することによって、オブジェクト領域に対する頂点の内外判定を行っているが、もちろん、陰関数を用いる等、他の判定方法を用いても構わない。そしてメッシュ構造生成部102は、構造データ内の非オブジェクト領域内メッシュのフラグ情報を「不必要」に更新する。これにより、非オブジェクト領域内メッシュ(に係るデータ)を削除対象とすることができる。
【0038】
ステップS204ではメッシュ構造生成部102は、構造データを参照し、フラグ情報が「不必要」となっているメッシュの頂点データを削除する。
【0039】
図6(b)を用いて、ステップS203及びステップS204について説明する。図6(b)には、図6(a)に示したメッシュ群から、頂点データを削除したメッシュを除いたメッシュ(オブジェクト領域内メッシュ)が残っている。この残ったオブジェクト領域内メッシュによりオブジェクト領域を近似していることが分かる。
【0040】
即ち、係る処理によれば、オブジェクト領域を包含するように複数のメッシュによりオブジェクト領域の概形を近似できる。そしてメッシュ構造生成部102は、構造データ、オブジェクト領域内メッシュについての頂点データ、を後段のメッシュ適合部103に送出する。
【0041】
図3を用いて、メッシュ適合部103の動作について説明する。先ずステップS301においてメッシュ適合部103は、オブジェクト領域内メッシュの頂点データをメッシュ構造生成部102から取得する。そして、メッシュ適合部103は、それぞれのオブジェクト領域内メッシュのうち「オブジェクト領域内メッシュを構成する頂点群のうち1以上の頂点がオブジェクト領域外にあるオブジェクト領域内メッシュ」を補正対象メッシュとして特定(第2の特定)する。そしてメッシュ適合部103は、特定したそれぞれの補正対象メッシュのうち未だ選択していない補正対象メッシュの頂点データを選択する。
【0042】
次にステップS302ではメッシュ適合部103は、次のような処理を行う。即ち、ステップS301で選択した頂点データ(選択頂点データ)内のそれぞれの頂点の位置情報のうち、オブジェクト領域外にある頂点(外部頂点)の位置情報を、オブジェクト領域の枠部上の位置を示す位置情報に更新する。即ち、外部頂点の位置情報を、外部頂点をオブジェクト領域の枠部上に移動させた後の外部頂点の位置情報に更新する。これにより、補正対象メッシュを構成する全ての頂点の位置情報は、何れもオブジェクト領域内(若しくはオブジェクト領域の枠部上)の位置を示していることになる。そしてメッシュ適合部103は、この更新処理後、外部頂点の色情報として、外部頂点の更新済み位置情報が示す位置に対応するオブジェクト領域の枠部上の位置における画素の色情報を設定する。
【0043】
そしてステップS304ではメッシュ適合部103は、ステップS302による処理後の、選択頂点データ内のそれぞれの位置情報(必要に応じてオブジェクト領域の枠部)を用いて、選択頂点データ内のそれぞれの勾配情報を再計算する。
【0044】
そしてステップS305ではメッシュ適合部103は、全ての補正対象メッシュの頂点データを選択したか否かを判断する。この判断の結果、選択したと判断した場合には図3のフローチャートに従った処理を終了し、未だ選択していない頂点データがあると判断した場合には、処理をステップS301に戻す。そしてステップS301では、未だ選択していない頂点データを選択し、この選択した頂点データを用いてステップS302以降の処理を行う。
【0045】
図7を用いて、ステップS301〜S305の処理について、具体例を挙げて説明する。メッシュ602は上記の通り、オブジェクト領域401の外部に位置する頂点601を有している。然るにこのメッシュ602は補正対象メッシュであり、頂点601は外部頂点であるので、この頂点601の位置情報を、オブジェクト領域401の枠部上の位置を示す位置情報に更新する。これにより、図7(a)に示す如く、頂点601の位置はオブジェクト領域401の枠部上に移動することになる。なお、メッシュ602は頂点601以外にも外部頂点を2つ有しているので、この2つの外部頂点のそれぞれについても同様の処理を行う。その結果、図7(a)に示す如く、メッシュ602を構成する4つの頂点は何れもオブジェクト領域401の内部(3つは枠部上)に位置することになる。
【0046】
ここで、補正対象メッシュの外部頂点の移動方向は、この補正対象メッシュが有する外部頂点の数に応じて異なる。補正対象メッシュの外部頂点の数が1の場合、この補正対象メッシュの4つの頂点のうち外部頂点の対角にある頂点(対角頂点)を特定し、外部頂点と対角頂点との間を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点の更新後の位置とする。
【0047】
補正対象メッシュの外部頂点の数が2の場合、一方の外部頂点(外部頂点1)と、外部頂点1と隣接する補正対象メッシュの非外部頂点と、を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点1の更新後の位置とする。同様に、他方の外部頂点(外部頂点2)と、外部頂点2と隣接する補正対象メッシュの非外部頂点と、を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点2の更新後の位置とする。
【0048】
補正対象メッシュの外部頂点の数が3の場合、何れの外部頂点も、外部頂点と隣接する補正対象メッシュの非外部頂点とを結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点の更新後の位置とする。
【0049】
なお、外部頂点の更新後の位置をオブジェクト領域の枠部上の位置に更新する為の処理については、上記の処理に限定するものではなく、他の処理によって実現させても良い。例えば、オブジェクト領域の枠部上で外部頂点から最も近い位置を求め、この求めた位置を外部頂点の更新後の位置としても良い。
【0050】
外部頂点の位置情報を更新した後のメッシュ602を図7(b)に示す。そして位置情報の更新を行うと、次に、図7(c)に示す如く、メッシュ602の形状がオブジェクト領域401の枠部403に沿うように、外部頂点601(図6(b)では更にもう1つの外部頂点)の勾配情報を更新する。ここでは、オブジェクト領域401の枠部403を表現しているメッシュ602の部分と、オブジェクト領域401の枠部403との距離誤差が減少するように反復的にメッシュの勾配情報を更新する。もちろん、外部頂点でのオブジェクト領域401の枠部403の微分係数を用いて勾配情報を求める等、他の方法を用いても構わない。
【0051】
なお、ステップS304における処理は、メッシュ群によるオブジェクト領域の形状の近似精度を高める為のものであり、高い精度を要求しないのであれば、ステップS304における処理は省いても構わない。
【0052】
また、メッシュ適合部103は、図3のフローチャートに従った処理を終了した後、構造データ、それぞれのオブジェクト領域内メッシュの頂点データ、を後段の符号化部104に送出する。
【0053】
図1に戻って、符号化部104は、メッシュ適合部103による上記処理によって得られたメッシュデータを符号化して管理する。メッシュデータには、以下の項目がテキストとして記されている。
【0054】
・ メッシュのx方向の頂点数、メッシュのy方向の頂点数、領域数等を含むヘッダ
・ それぞれのメッシュの頂点データ
・ 構造データ
本実施形態では、符号化部104は、このような項目の内容が記されたテキストデータとしてのメッシュデータをzip符号化して管理しているが、非可逆符号化を含めた他の符号化方法を用いても構わない。もちろん、頂点データを導出できるのであれば、他のデータ記述方法でも構わない。同様に、構造データについても、上記の内容が得ることができるのであれば、そのデータ構造については特に限定するものではない。
【0055】
以上の説明により、本実施形態によれば、オブジェクト領域の形状に合わせて不規則構造を持ったメッシュ群を生成するので、メッシュ群によるオブジェクト領域の形状の近似を効率的に行うことができる。
【0056】
<第1の実施形態の変形例>
図1に示した各部はハードウェアで構成しても良いが、ソフトウェア(コンピュータプログラム)として実装しても良い。この場合、このソフトウェアは、PC(パーソナルコンピュータ)等、一般のコンピュータのメモリにインストールされることになる。そしてこのコンピュータのCPUがこのインストールされたソフトウェアを実行することで、このコンピュータは、上述の画像処理装置の機能(図1に示した各部の機能)を実現することになる。即ち、このコンピュータは、上述の画像処理装置に適用することができる。図9を用いて、第1の実施形態に係る画像処理装置として適用可能なコンピュータのハードウェア構成例について説明する。
【0057】
CPU901は、RAM902やROM903に格納されているコンピュータプログラムやデータを用いて、コンピュータ全体の制御を行うと共に、画像処理装置が行うものとして説明した上述の各処理を実行する。即ち、図1に示した各部が行うものとして上述した各処理を実行する。
【0058】
RAM902は、コンピュータ読み取り可能な記憶媒体の一例である。RAM902は、外部記憶装置907や記憶媒体ドライブ908からロードされたコンピュータプログラムやデータ、I/F(インターフェース)909を介して外部装置から受信したデータなどを一時的に記憶するためのエリアを有する。更に、RAM902は、CPU901が各種の処理を実行する際に用いるワークエリアを有する。即ち、RAM902は、各種のエリアを適宜提供することができる。ROM903は、コンピュータ読み取り可能な記憶媒体の一例であり、コンピュータの設定データや、ブートプログラムなどが格納されている。
【0059】
キーボード904、マウス905は、コンピュータの操作者が操作することで、各種の指示をCPU901に対して入力することができる。表示装置906は、CRTや液晶画面などにより構成されており、CPU901による処理結果を画像や文字などでもって表示することができる。例えば、上記入力画像を表示したり、抽出したオブジェクト領域やオブジェクト領域内メッシュを明示的に表示したり、メッシュ符号化の過程で求めたパラメトリック曲面を表示したりすることができる。
【0060】
外部記憶装置907は、コンピュータ読み取り可能な記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置907には、OS(オペレーティングシステム)や、図1に示した各部の機能をCPU901に実現させるためのコンピュータプログラムやデータ、上記入力画像のデータ、既知の情報として説明した情報等が保存されている。外部記憶装置907に保存されているコンピュータプログラムやデータは、CPU901による制御に従って適宜RAM902にロードされ、CPU901による処理対象となる。
【0061】
記憶媒体ドライブ908は、CD−ROMやDVD−ROMなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置907やRAM902に出力する。なお、外部記憶装置907に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ908に読み取らせても良い。
【0062】
I/F909は、外部装置をコンピュータに接続する為のものである。例えば、ディジタルカメラなど、上記入力画像を取得するための装置を、このI/F909に接続し、この装置から入力画像をI/F909を介してRAM902や外部記憶装置907に取得するようにしても良い。910は、上述の各部を繋ぐバスである。
【0063】
上記構成において、本コンピュータの電源がONになると、CPU901はROM903に格納されている上記ブートプログラムに従って、外部記憶装置907からOSをRAM902にロードする。この結果、キーボード904、マウス905を介した情報入力操作が可能となり、表示装置906にGUIを表示することが可能となる。ユーザが、キーボード904やマウス905を操作し、外部記憶装置907に格納された画像処理用アプリケーションプログラムの起動指示を入力すると、CPU901はこのプログラムをRAM902にロードし、実行する。これにより、本コンピュータが上記の画像処理装置として機能することになる。
【0064】
CPU901が実行する画像処理用アプリケーションプログラムは、基本的に図1の各処理部、及び図2、図3の各ステップに相当する関数を備えることになる。ここで、符号化したグラディエント・メッシュのデータは外部記憶装置907に保存することになる。
【0065】
[第2の実施形態]
本実施形態では、第1の実施形態に加え、オブジェクト領域の形状の近似精度を高めるための前処理を行う。以下では、第1の実施形態と異なる点のみについて説明する。即ち、以下に説明する点以外については、第1の実施形態と同様である。
【0066】
図10を用いて、メッシュ構造生成部102の動作について説明する。ステップS1001ではメッシュ構造生成部102は、オブジェクト領域を包含する包含領域を求め、求めた包含領域を複数の矩形領域に分割する。即ち、オブジェクト領域を包含するように格子をオブジェクト領域上に生成する。ステップS1002ではメッシュ構造生成部102は、矩形領域毎に特徴点を設定する。そして隣接する特徴点間を結ぶことで、特徴点を頂点とするメッシュを生成する。
【0067】
図11(a)、(b)を用いて、ステップS1001、S1002における処理について、具体例を挙げて説明する。図11(a)の場合、ステップS1001では、メッシュ構造生成部102は、オブジェクト領域401を包含するように包含領域1102をオブジェクト領域上に生成し、この包含領域1102を複数の矩形領域に分割する。1103は分割された矩形領域のうちの1つである。
【0068】
次に、矩形領域毎に、メッシュの頂点として用いる特徴点を設定する。ここで、矩形領域内に枠部403が含まれているか否かに応じて、この矩形領域に対する特徴点の設定方法が異なる。
【0069】
矩形領域内に枠部403が含まれている場合、この含まれている枠部403上で最も曲率が高い位置に特徴点を設定する。一方、矩形領域内に枠部403が含まれていない場合、この矩形領域の中央位置に特徴点を設定する。例えば、矩形領域1103内にはオブジェクト領域401の枠部403は含まれていないので、この矩形領域1103内の中央位置に特徴点(黒丸)を設定する。もちろん、1つの矩形領域に対して1つの特徴点を設定するのであれば、他の方法を用いて設定しても良い。
【0070】
そしてこのようにして設定した特徴点を頂点とするメッシュ群を、図11(b)に示す如く生成する。即ち、矩形領域の数がN×Mの場合、生成されるメッシュの数もN×Mとなる。なお、メッシュの外側にある頂点がオブジェクト領域の内側に入らなければ、メッシュ生成方法には他の方法を用いても良い。
【0071】
[第3の実施形態]
第1,2の実施形態では、オブジェクト領域は、その内部が埋まっているものとして説明した。本実施形態では、ドーナッツ型のような、内部に穴が空いているオブジェクト領域(非オブジェクト領域を囲むように構成されているオブジェクト領域)を用いる場合について説明する。以下では、第1の実施形態と異なる点のみについて説明する。即ち、以下に説明する点以外については、第1の実施形態と同様である。
【0072】
オブジェクト抽出部101は第1の実施形態と同様に動作してオブジェクト領域のデータを生成するのであるが、本実施形態では更に、入力画像を構成する各画素がオブジェクト領域内であるかオブジェクト領域外であるかを示すマスク画像も生成する。また、本実施形態では、図5(a)に示したような穴1201の枠部を構成する各画素の座標位置のデータも、オブジェクト領域のデータに含まれる。
【0073】
メッシュ構造生成部102は、枠部を構成する各画素の座標位置のデータを用いて閉領域を特定し、更にマスク画像においてこの閉領域内の画素の値を特定することで、この閉領域が穴の部分であるか否かを特定することができる。そしてこの閉領域が穴であれば、この穴の部分をオブジェクト領域外として扱い、以降は第1の実施形態と同様の処理を行う。その結果、図5(b)に示す如く、穴の部分のメッシュを除外することができる。
【0074】
[その他の実施形態]
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア(プログラム)を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ(またはCPUやMPU等)がプログラムを読み出して実行する処理である。
【技術分野】
【0001】
本発明は、ラスタ画像をグラディエント・メッシュで近似する際に、複雑な形状のオブジェクトをグラディエント・メッシュで表現するための解像度フリー表現技術に関するものである。
【背景技術】
【0002】
従来、イラストや文字の解像度フリー表現には、オブジェクトの輪郭をベジェ、スプライン関数などで関数近似する手法が用いられている。オブジェクト領域内は、単一色、線形グラデーション、放射状グラデーションなどで塗りつぶすことができるが、複雑なグラデーションの表現は困難である。
【0003】
解像度フリーで複雑なグラデーションを含むオブジェクトを描画するためには、Adobe Illustrator(登録商標)のグラディエント・メッシュ・ツールが一般に用いられている。グラディエント・メッシュでは、メッシュに色と勾配を与えて三次関数を生成することで複雑なオブジェクトを描画することができる(特許文献1、2)。
【0004】
ラスタ画像中のオブジェクトを解像度フリー表現に変換するとき、イラストや文字などの色変化の少ないオブジェクトに関しては、前述のベジェ、スプライン関数を用いた方法により表現できる。
【0005】
自然画像のような色が複雑に変化するオブジェクトを解像度フリー表現に変換する技術は幾つか提案されており、大きく3つのカテゴリに分類できる。三角形メッシュを用いた手法、高次のパラメトリック曲面を用いた手法、メッシュ以外の表現を用いた手法、である。
【0006】
三角形メッシュを用いた方法では、オブジェクトの直線的なエッジを忠実に表現できる。しかし、滑らかな曲線を表現するとき、線形メッシュで曲線を忠実に近似することは困難であり、忠実に近似するためには多数のメッシュを用いなければならない。
【0007】
高次のパラメトリック曲面を用いた手法では、曲線の表現も可能であり、より少ないメッシュ数で特徴曲線を近似することができる。高次のパラメトリック曲面を用いる手法としては、ベジェパッチを細分割して近似誤差を低減する手法(非特許文献1)、グラディエント・メッシュを用いて画像を近似する手法などが挙げられる(特許文献3、非特許文献3)。
【0008】
メッシュ以外の表現を用いた手法では、画像の特徴線をベジェ曲線で近似し、曲線の両側に色情報を付加し、曲線の色を用いた偏微分方程式を解いて画像を描画するディフュージョン・カーブと呼ばれる解像度フリー表現手法が提案されている(非特許文献2)。また、境界曲線と特徴曲線と関連付けられた色を用いてカラー・グラディエントを生成する手法も提案されている(特許文献4)。
【0009】
複雑な形状のオブジェクトをメッシュで近似するために、幾つかの方法が提案されている。パラメトリック曲面を用いた手法(特許文献3、非特許文献3)では、4頂点から成る規則メッシュを生成するため、オブジェクトの近似に頂点を過剰に与えてしまうことがある。また、適応的にメッシュ頂点を除去してオブジェクトを近似する手法(特許文献5)、メッシュの頂点をオブジェクト境界上に移動する手法(特許文献6)では、メッシュを直線で接続しているため、曲線近似が困難であるという課題も残る。
【先行技術文献】
【特許文献】
【0010】
【特許文献1】特開平11−345347号公報
【特許文献2】特許第4220010号公報
【特許文献3】米国特許出願公開第2008/0278479号明細書
【特許文献4】特許第3989451号公報
【特許文献5】特許第2815571号公報
【特許文献6】特開平11−25293号公報
【非特許文献】
【0011】
【非特許文献1】Brian Price,William Barrett,「Object−based vectorization for interactive image editing」,In proceedings of Pacific Graphics 2006,2006,vol.22,no.9−11,p.661−670.
【非特許文献2】Alexandrina Orzan,Adrien Bousseau,Holger Winnemoller,Pascal Barla,Joelle Thollot,David Salesin,「Diffusion Curves:A Vector Representation for Smooth−Shaded Images」,In proceedings of SIGGRAPH 2008,2008,vol.27.
【非特許文献3】Yu−Kun Lai,Shi−Min Hu,Ralph R.Martin,「Automatic and Topology−Preserving Gradient Mesh Generation for Image Vectorization」,ACM SIGGRAPH 2009,ACM Transaction on Graphics,Vol.28,No.3.
【発明の概要】
【発明が解決しようとする課題】
【0012】
自然画像のような色が複雑に変化するオブジェクトを解像度フリー表現に変換するとき、高次のパラメトリック曲面を用いることで、少ないメッシュ数でオブジェクトを近似できる。しかし、オブジェクトの形状が複雑であるとき、表現能力、演算量、データ量について課題も残る。以下にその課題について説明する。
【0013】
上述のベジェパッチを細分割して近似誤差を低減する手法では、高次のメッシュを用いるため、オブジェクト境界の近似を忠実に行うことができる。しかし、近似誤差を低減するためにメッシュを細分割しているため、オブジェクトの色変化が複雑な部分ではメッシュの数が増え、データ量が増大してしまう。
【0014】
上述のグラディエント・メッシュを用いて画像を近似する手法では、色変化が複雑なオブジェクトにおいても、より少ないメッシュ数(データ量)で解像度フリー表現できる。しかしこれらの手法では、4頂点から成る規則メッシュを生成するため、オブジェクトの形状によっては、オブジェクトの色が単純な部分にもメッシュ頂点を過剰に与えてしまうことがある。また、過剰なメッシュ頂点による画質の劣化、演算量の増大などの問題も残る。
【0015】
本発明は以上の問題に鑑みて成されたものであり、グラディエント・メッシュによるオブジェクトの近似を効率的に行うための技術を提供することを目的とする。
【課題を解決するための手段】
【0016】
本発明の目的を達成するために、例えば、本発明の画像処理装置は以下の構成を備える。即ち、画像処理装置であって、画像からオブジェクトの領域をオブジェクト領域として抽出する手段と、前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割手段と、前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める手段と、前記複数のメッシュのうち、該メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第1の特定手段と、前記第1の特定手段が特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第2の特定手段と、前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新手段と、前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理手段とを備えることを特徴とする。
【発明の効果】
【0017】
本発明の構成によれば、グラディエント・メッシュによるオブジェクトの近似を効率的に行うことができる。
【図面の簡単な説明】
【0018】
【図1】画像処理装置の機能構成例を示すブロック図。
【図2】メッシュ構造生成部102が行う処理のフローチャート。
【図3】メッシュ適合部103が行う処理のフローチャート。
【図4】オブジェクト領域の一例を示す図。
【図5】第3の実施形態で扱うオブジェクト領域の一例を示す図。
【図6】ステップS201〜S203を説明する図。
【図7】ステップS301〜S305を説明する図。
【図8】グラディエント・メッシュ表現を説明する図。
【図9】コンピュータのハードウェア構成例を示す図。
【図10】メッシュ構造生成部102が行う処理のフローチャート。
【図11】ステップS1001,S1002における処理を説明する図。
【発明を実施するための形態】
【0019】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載の構成の具体的な実施例の1つである。
【0020】
[第1の実施形態]
図1を用いて、本実施形態に係る画像処理装置の機能構成例について説明する。オブジェクト抽出部101には、1以上のオブジェクトを含む画像が入力される。この「オブジェクト」とは、文字や物体像などを指し示しており、本実施形態では、この「オブジェクト」は、色のグラデーションを有しているものとして説明する。即ち、本実施形態では、色のグラデーションを有するオブジェクトに対するメッシュ符号化を行う。
【0021】
そしてオブジェクト抽出部101は、この入力画像からオブジェクトの領域をオブジェクト領域として抽出する処理を行う。図4に、抽出されたオブジェクト領域の一例を示す。抽出にはグラブ・カット法という既知の方法を用いるが、他の抽出手法を用いても構わない。抽出されたオブジェクト領域のデータには、オブジェクト領域401の内部402を構成する各画素の画素値と、枠部(オブジェクト領域の境界線)403を構成する各画素の座標位置が含まれている。本実施形態では、画素値は、RGBのそれぞれの色成分が8ビットで表現されているものとして説明するが、グレースケール、CMYKなどの色成分の種別、一つの色成分を構成するビット数、についてはこれに限定するものではない。また、オブジェクト領域のデータの構成については、オブジェクト領域の枠部403を構成する各画素の座標位置、オブジェクト領域の内部402を構成する各画素の画素値、が導出できるのであれば、他のデータ構成であっても良い。そしてオブジェクト抽出部101は、抽出したオブジェクト領域のデータを、後段のメッシュ構造生成部102に送出する。
【0022】
図2を用いて、メッシュ構造生成部102が、オブジェクト領域のデータを用いて行う処理について説明する。ステップS201では、メッシュ構造生成部102は、入力画像においてオブジェクト領域を包含する包含領域を求め、求めた包含領域を複数の矩形(メッシュ)に分割することで、この複数のメッシュを生成する。本実施形態では、4つの頂点から構成されるメッシュを生成するが、3つの頂点から構成されるメッシュを生成しても良い。
【0023】
ステップS202ではメッシュ構造生成部102は、ステップS201で生成したそれぞれのメッシュについて頂点データを求める。着目メッシュについて求めた頂点データは着目メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報、で構成されている。また、ステップS202ではメッシュ構造生成部102は、ステップS201で生成した各メッシュを構成する頂点間の接続関係を示す構造データも生成する。
【0024】
ここで、図8を用いて、グラディエント・メッシュ表現について簡単に説明する。グラディエント・メッシュ(メッシュ)は、4つの頂点(頂点0〜頂点3)のそれぞれについての以下の情報によって表現されるものである。
【0025】
・ 頂点i(i=0〜3)の位置情報mi
・ 頂点iにおけるu方向、v方向の勾配情報mui、mvi
・ 頂点iにおける色情報ci
・ 頂点iにおける色のu方向、v方向の勾配情報cui、cvi
図8に示す如く、メッシュの形状は3次関数によって表現され、メッシュ内の座標m(u、v)は以下の式で導出される。
【0026】
【数1】
【0027】
u、vは、0〜1の範囲内の実数である。また、muviは、頂点iにおけるu方向及びv方向の微分値を示すが、一般にはmuviには0を設定する。即ち、メッシュの形状は、頂点の位置情報と勾配情報とによって決まる。なお、勾配情報は、メッシュの輪郭の曲線形状を表していることが分かる。
【0028】
なお、メッシュ内の座標m(u、v)における色Col(u、v)は、以下の置き換え手順1〜3を行ってから、上記の式を計算することで求めることができる。
【0029】
(置き換え手順1) 上記の式において、座標m(u、v)を色Col(u、v)に置き換える
(手順2) 上記の式において、頂点0〜3の位置情報(m0、m1、m2、m3)を、頂点0〜3の色情報(c0、c1、c2、c3)に置き換える
(手順3) 上記の式において、頂点0〜3におけるu方向、v方向の勾配情報(mu0、mv0、mu1、mv1、mu2、mv2、mu3、mv3)を、頂点0〜3における色のu方向、v方向の勾配情報(cu0、cv0、cu1、cv1、cu2、cv2、cu3、cv3)に置き換える。
【0030】
なお、頂点0〜3の色のu方向及びv方向の微分値を示すcuv0、cuv1、cuv2、cuv3には0を設定する。即ち、メッシュ内の色は、頂点の色情報と色の勾配情報とによって決まる。なお、色の勾配情報を0としてレンダリングを行っても良い。本実施形態では、色の勾配情報は0として説明する。
【0031】
上記のようなグラディエント・メッシュ表現は一般に用いられており、その詳細については特許文献3、非特許文献3で説明されているため、これ以上の詳細な説明は省略する。
【0032】
なお、ここではグラディエント・メッシュのメッシュ勾配、及び色勾配の設定方法を示したが、メッシュの形状がパラメトリック曲面として表現され、メッシュ内のグラデーションさえ表現できれば、他の表現方法であっても構わない。例えば、三角形ベジェパッチでメッシュの形状を表現し、メッシュ内の色はRBFs(Radial Basis Functions)曲面で表現するなどの方法を用いても構わない。
【0033】
次に、図6(a)を用いて、ステップS201及びS202における処理を、具体例を挙げて説明する。図6(a)の場合、ステップS201では、メッシュ構造生成部102は、オブジェクト領域401を包含する包含領域690を求め、求めた包含領域690を複数のメッシュに分割する。図6(a)において602は、分割された複数のメッシュのうちの1つを示しており、601は、メッシュ602を構成する頂点群のうちの1つを示している。ここで、頂点601は、オブジェクト領域401の外部に位置している。
【0034】
図6(a)では、包含領域690は長方形であるが、オブジェクト領域を包含する領域であれば、その形状は長方形以外であっても良い。また、図6(a)では、包含領域690を縦横均等に分割しているが、分割方法についてはこれに限定するものではない。
【0035】
次に、ステップS202では、メッシュ構造生成部102は、分割されたそれぞれのメッシュについて、メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める。勾配情報としては何れも0とする。色情報については、頂点がオブジェクト領域401の外部に位置している場合、この頂点の色情報として、0を設定する。一方、頂点がオブジェクト領域401の内部に位置している場合、この頂点の色情報として、この頂点の位置に対応する、オブジェクト領域401上の画素の色情報を設定する。もちろん、頂点がオブジェクト領域401の内部に位置している場合、この頂点の色情報として、この頂点の位置に対応するオブジェクト領域401上の画素の周辺画素の色情報の平均値を設定する等、他の方法を用いて色情報を設定しても良い。また、勾配情報についても、一定値を設定する等、他の方法を用いて勾配情報を設定しても良い。
【0036】
また上記の通り、ステップS202ではメッシュ構造生成部102は、構造データも生成するが、本実施形態では、この構造データには、各メッシュが必要か否かのフラグ情報が含まれている。すべてのメッシュのフラグ情報が「必要」を示している状態が初期状態となる。もちろん、各頂点に番号を振り、必要となるメッシュに4つの頂点番号を保持させてメッシュ構造を表現するなど、他の構造表現を用いても構わない。
【0037】
図2に戻って、ステップS203でメッシュ構造生成部102は、ステップS201で生成したそれぞれのメッシュの各頂点の位置情報を参照する。そしてメッシュ構造生成部102は、ステップS201で得たそれぞれのメッシュのうち「メッシュを構成する頂点群のうち1以上の頂点がオブジェクト領域の内部に位置しているメッシュ」を、オブジェクト領域内メッシュとして特定(第1の特定)する。ここでは、オブジェクト領域を閉領域として定義することによって、オブジェクト領域に対する頂点の内外判定を行っているが、もちろん、陰関数を用いる等、他の判定方法を用いても構わない。そしてメッシュ構造生成部102は、構造データ内の非オブジェクト領域内メッシュのフラグ情報を「不必要」に更新する。これにより、非オブジェクト領域内メッシュ(に係るデータ)を削除対象とすることができる。
【0038】
ステップS204ではメッシュ構造生成部102は、構造データを参照し、フラグ情報が「不必要」となっているメッシュの頂点データを削除する。
【0039】
図6(b)を用いて、ステップS203及びステップS204について説明する。図6(b)には、図6(a)に示したメッシュ群から、頂点データを削除したメッシュを除いたメッシュ(オブジェクト領域内メッシュ)が残っている。この残ったオブジェクト領域内メッシュによりオブジェクト領域を近似していることが分かる。
【0040】
即ち、係る処理によれば、オブジェクト領域を包含するように複数のメッシュによりオブジェクト領域の概形を近似できる。そしてメッシュ構造生成部102は、構造データ、オブジェクト領域内メッシュについての頂点データ、を後段のメッシュ適合部103に送出する。
【0041】
図3を用いて、メッシュ適合部103の動作について説明する。先ずステップS301においてメッシュ適合部103は、オブジェクト領域内メッシュの頂点データをメッシュ構造生成部102から取得する。そして、メッシュ適合部103は、それぞれのオブジェクト領域内メッシュのうち「オブジェクト領域内メッシュを構成する頂点群のうち1以上の頂点がオブジェクト領域外にあるオブジェクト領域内メッシュ」を補正対象メッシュとして特定(第2の特定)する。そしてメッシュ適合部103は、特定したそれぞれの補正対象メッシュのうち未だ選択していない補正対象メッシュの頂点データを選択する。
【0042】
次にステップS302ではメッシュ適合部103は、次のような処理を行う。即ち、ステップS301で選択した頂点データ(選択頂点データ)内のそれぞれの頂点の位置情報のうち、オブジェクト領域外にある頂点(外部頂点)の位置情報を、オブジェクト領域の枠部上の位置を示す位置情報に更新する。即ち、外部頂点の位置情報を、外部頂点をオブジェクト領域の枠部上に移動させた後の外部頂点の位置情報に更新する。これにより、補正対象メッシュを構成する全ての頂点の位置情報は、何れもオブジェクト領域内(若しくはオブジェクト領域の枠部上)の位置を示していることになる。そしてメッシュ適合部103は、この更新処理後、外部頂点の色情報として、外部頂点の更新済み位置情報が示す位置に対応するオブジェクト領域の枠部上の位置における画素の色情報を設定する。
【0043】
そしてステップS304ではメッシュ適合部103は、ステップS302による処理後の、選択頂点データ内のそれぞれの位置情報(必要に応じてオブジェクト領域の枠部)を用いて、選択頂点データ内のそれぞれの勾配情報を再計算する。
【0044】
そしてステップS305ではメッシュ適合部103は、全ての補正対象メッシュの頂点データを選択したか否かを判断する。この判断の結果、選択したと判断した場合には図3のフローチャートに従った処理を終了し、未だ選択していない頂点データがあると判断した場合には、処理をステップS301に戻す。そしてステップS301では、未だ選択していない頂点データを選択し、この選択した頂点データを用いてステップS302以降の処理を行う。
【0045】
図7を用いて、ステップS301〜S305の処理について、具体例を挙げて説明する。メッシュ602は上記の通り、オブジェクト領域401の外部に位置する頂点601を有している。然るにこのメッシュ602は補正対象メッシュであり、頂点601は外部頂点であるので、この頂点601の位置情報を、オブジェクト領域401の枠部上の位置を示す位置情報に更新する。これにより、図7(a)に示す如く、頂点601の位置はオブジェクト領域401の枠部上に移動することになる。なお、メッシュ602は頂点601以外にも外部頂点を2つ有しているので、この2つの外部頂点のそれぞれについても同様の処理を行う。その結果、図7(a)に示す如く、メッシュ602を構成する4つの頂点は何れもオブジェクト領域401の内部(3つは枠部上)に位置することになる。
【0046】
ここで、補正対象メッシュの外部頂点の移動方向は、この補正対象メッシュが有する外部頂点の数に応じて異なる。補正対象メッシュの外部頂点の数が1の場合、この補正対象メッシュの4つの頂点のうち外部頂点の対角にある頂点(対角頂点)を特定し、外部頂点と対角頂点との間を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点の更新後の位置とする。
【0047】
補正対象メッシュの外部頂点の数が2の場合、一方の外部頂点(外部頂点1)と、外部頂点1と隣接する補正対象メッシュの非外部頂点と、を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点1の更新後の位置とする。同様に、他方の外部頂点(外部頂点2)と、外部頂点2と隣接する補正対象メッシュの非外部頂点と、を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点2の更新後の位置とする。
【0048】
補正対象メッシュの外部頂点の数が3の場合、何れの外部頂点も、外部頂点と隣接する補正対象メッシュの非外部頂点とを結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点の更新後の位置とする。
【0049】
なお、外部頂点の更新後の位置をオブジェクト領域の枠部上の位置に更新する為の処理については、上記の処理に限定するものではなく、他の処理によって実現させても良い。例えば、オブジェクト領域の枠部上で外部頂点から最も近い位置を求め、この求めた位置を外部頂点の更新後の位置としても良い。
【0050】
外部頂点の位置情報を更新した後のメッシュ602を図7(b)に示す。そして位置情報の更新を行うと、次に、図7(c)に示す如く、メッシュ602の形状がオブジェクト領域401の枠部403に沿うように、外部頂点601(図6(b)では更にもう1つの外部頂点)の勾配情報を更新する。ここでは、オブジェクト領域401の枠部403を表現しているメッシュ602の部分と、オブジェクト領域401の枠部403との距離誤差が減少するように反復的にメッシュの勾配情報を更新する。もちろん、外部頂点でのオブジェクト領域401の枠部403の微分係数を用いて勾配情報を求める等、他の方法を用いても構わない。
【0051】
なお、ステップS304における処理は、メッシュ群によるオブジェクト領域の形状の近似精度を高める為のものであり、高い精度を要求しないのであれば、ステップS304における処理は省いても構わない。
【0052】
また、メッシュ適合部103は、図3のフローチャートに従った処理を終了した後、構造データ、それぞれのオブジェクト領域内メッシュの頂点データ、を後段の符号化部104に送出する。
【0053】
図1に戻って、符号化部104は、メッシュ適合部103による上記処理によって得られたメッシュデータを符号化して管理する。メッシュデータには、以下の項目がテキストとして記されている。
【0054】
・ メッシュのx方向の頂点数、メッシュのy方向の頂点数、領域数等を含むヘッダ
・ それぞれのメッシュの頂点データ
・ 構造データ
本実施形態では、符号化部104は、このような項目の内容が記されたテキストデータとしてのメッシュデータをzip符号化して管理しているが、非可逆符号化を含めた他の符号化方法を用いても構わない。もちろん、頂点データを導出できるのであれば、他のデータ記述方法でも構わない。同様に、構造データについても、上記の内容が得ることができるのであれば、そのデータ構造については特に限定するものではない。
【0055】
以上の説明により、本実施形態によれば、オブジェクト領域の形状に合わせて不規則構造を持ったメッシュ群を生成するので、メッシュ群によるオブジェクト領域の形状の近似を効率的に行うことができる。
【0056】
<第1の実施形態の変形例>
図1に示した各部はハードウェアで構成しても良いが、ソフトウェア(コンピュータプログラム)として実装しても良い。この場合、このソフトウェアは、PC(パーソナルコンピュータ)等、一般のコンピュータのメモリにインストールされることになる。そしてこのコンピュータのCPUがこのインストールされたソフトウェアを実行することで、このコンピュータは、上述の画像処理装置の機能(図1に示した各部の機能)を実現することになる。即ち、このコンピュータは、上述の画像処理装置に適用することができる。図9を用いて、第1の実施形態に係る画像処理装置として適用可能なコンピュータのハードウェア構成例について説明する。
【0057】
CPU901は、RAM902やROM903に格納されているコンピュータプログラムやデータを用いて、コンピュータ全体の制御を行うと共に、画像処理装置が行うものとして説明した上述の各処理を実行する。即ち、図1に示した各部が行うものとして上述した各処理を実行する。
【0058】
RAM902は、コンピュータ読み取り可能な記憶媒体の一例である。RAM902は、外部記憶装置907や記憶媒体ドライブ908からロードされたコンピュータプログラムやデータ、I/F(インターフェース)909を介して外部装置から受信したデータなどを一時的に記憶するためのエリアを有する。更に、RAM902は、CPU901が各種の処理を実行する際に用いるワークエリアを有する。即ち、RAM902は、各種のエリアを適宜提供することができる。ROM903は、コンピュータ読み取り可能な記憶媒体の一例であり、コンピュータの設定データや、ブートプログラムなどが格納されている。
【0059】
キーボード904、マウス905は、コンピュータの操作者が操作することで、各種の指示をCPU901に対して入力することができる。表示装置906は、CRTや液晶画面などにより構成されており、CPU901による処理結果を画像や文字などでもって表示することができる。例えば、上記入力画像を表示したり、抽出したオブジェクト領域やオブジェクト領域内メッシュを明示的に表示したり、メッシュ符号化の過程で求めたパラメトリック曲面を表示したりすることができる。
【0060】
外部記憶装置907は、コンピュータ読み取り可能な記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置907には、OS(オペレーティングシステム)や、図1に示した各部の機能をCPU901に実現させるためのコンピュータプログラムやデータ、上記入力画像のデータ、既知の情報として説明した情報等が保存されている。外部記憶装置907に保存されているコンピュータプログラムやデータは、CPU901による制御に従って適宜RAM902にロードされ、CPU901による処理対象となる。
【0061】
記憶媒体ドライブ908は、CD−ROMやDVD−ROMなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置907やRAM902に出力する。なお、外部記憶装置907に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ908に読み取らせても良い。
【0062】
I/F909は、外部装置をコンピュータに接続する為のものである。例えば、ディジタルカメラなど、上記入力画像を取得するための装置を、このI/F909に接続し、この装置から入力画像をI/F909を介してRAM902や外部記憶装置907に取得するようにしても良い。910は、上述の各部を繋ぐバスである。
【0063】
上記構成において、本コンピュータの電源がONになると、CPU901はROM903に格納されている上記ブートプログラムに従って、外部記憶装置907からOSをRAM902にロードする。この結果、キーボード904、マウス905を介した情報入力操作が可能となり、表示装置906にGUIを表示することが可能となる。ユーザが、キーボード904やマウス905を操作し、外部記憶装置907に格納された画像処理用アプリケーションプログラムの起動指示を入力すると、CPU901はこのプログラムをRAM902にロードし、実行する。これにより、本コンピュータが上記の画像処理装置として機能することになる。
【0064】
CPU901が実行する画像処理用アプリケーションプログラムは、基本的に図1の各処理部、及び図2、図3の各ステップに相当する関数を備えることになる。ここで、符号化したグラディエント・メッシュのデータは外部記憶装置907に保存することになる。
【0065】
[第2の実施形態]
本実施形態では、第1の実施形態に加え、オブジェクト領域の形状の近似精度を高めるための前処理を行う。以下では、第1の実施形態と異なる点のみについて説明する。即ち、以下に説明する点以外については、第1の実施形態と同様である。
【0066】
図10を用いて、メッシュ構造生成部102の動作について説明する。ステップS1001ではメッシュ構造生成部102は、オブジェクト領域を包含する包含領域を求め、求めた包含領域を複数の矩形領域に分割する。即ち、オブジェクト領域を包含するように格子をオブジェクト領域上に生成する。ステップS1002ではメッシュ構造生成部102は、矩形領域毎に特徴点を設定する。そして隣接する特徴点間を結ぶことで、特徴点を頂点とするメッシュを生成する。
【0067】
図11(a)、(b)を用いて、ステップS1001、S1002における処理について、具体例を挙げて説明する。図11(a)の場合、ステップS1001では、メッシュ構造生成部102は、オブジェクト領域401を包含するように包含領域1102をオブジェクト領域上に生成し、この包含領域1102を複数の矩形領域に分割する。1103は分割された矩形領域のうちの1つである。
【0068】
次に、矩形領域毎に、メッシュの頂点として用いる特徴点を設定する。ここで、矩形領域内に枠部403が含まれているか否かに応じて、この矩形領域に対する特徴点の設定方法が異なる。
【0069】
矩形領域内に枠部403が含まれている場合、この含まれている枠部403上で最も曲率が高い位置に特徴点を設定する。一方、矩形領域内に枠部403が含まれていない場合、この矩形領域の中央位置に特徴点を設定する。例えば、矩形領域1103内にはオブジェクト領域401の枠部403は含まれていないので、この矩形領域1103内の中央位置に特徴点(黒丸)を設定する。もちろん、1つの矩形領域に対して1つの特徴点を設定するのであれば、他の方法を用いて設定しても良い。
【0070】
そしてこのようにして設定した特徴点を頂点とするメッシュ群を、図11(b)に示す如く生成する。即ち、矩形領域の数がN×Mの場合、生成されるメッシュの数もN×Mとなる。なお、メッシュの外側にある頂点がオブジェクト領域の内側に入らなければ、メッシュ生成方法には他の方法を用いても良い。
【0071】
[第3の実施形態]
第1,2の実施形態では、オブジェクト領域は、その内部が埋まっているものとして説明した。本実施形態では、ドーナッツ型のような、内部に穴が空いているオブジェクト領域(非オブジェクト領域を囲むように構成されているオブジェクト領域)を用いる場合について説明する。以下では、第1の実施形態と異なる点のみについて説明する。即ち、以下に説明する点以外については、第1の実施形態と同様である。
【0072】
オブジェクト抽出部101は第1の実施形態と同様に動作してオブジェクト領域のデータを生成するのであるが、本実施形態では更に、入力画像を構成する各画素がオブジェクト領域内であるかオブジェクト領域外であるかを示すマスク画像も生成する。また、本実施形態では、図5(a)に示したような穴1201の枠部を構成する各画素の座標位置のデータも、オブジェクト領域のデータに含まれる。
【0073】
メッシュ構造生成部102は、枠部を構成する各画素の座標位置のデータを用いて閉領域を特定し、更にマスク画像においてこの閉領域内の画素の値を特定することで、この閉領域が穴の部分であるか否かを特定することができる。そしてこの閉領域が穴であれば、この穴の部分をオブジェクト領域外として扱い、以降は第1の実施形態と同様の処理を行う。その結果、図5(b)に示す如く、穴の部分のメッシュを除外することができる。
【0074】
[その他の実施形態]
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア(プログラム)を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ(またはCPUやMPU等)がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項1】
画像処理装置であって、
画像からオブジェクトの領域をオブジェクト領域として抽出する手段と、
前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割手段と、
前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める手段と、
前記複数のメッシュのうち、該メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第1の特定手段と、
前記第1の特定手段が特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第2の特定手段と、
前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新手段と、
前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理手段と
を備えることを特徴とする画像処理装置。
【請求項2】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が1つである場合、前記補正対象メッシュにおいて前記外部頂点と対角にある頂点を特定し、該特定した頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項1に記載の画像処理装置。
【請求項3】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が2つである場合、それぞれの前記外部頂点について、
前記補正対象メッシュにおいて前記外部頂点と隣接する非外部頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項1に記載の画像処理装置。
【請求項4】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が3つである場合、それぞれの前記外部頂点について、
前記補正対象メッシュにおける非外部頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項1に記載の画像処理装置。
【請求項5】
前記管理手段は、前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を符号化してから管理することを特徴とする請求項1乃至4の何れか1項に記載の画像処理装置。
【請求項6】
前記分割手段は、
前記包含領域を複数の矩形領域に分割する手段と、
前記複数の矩形領域のそれぞれについて、該矩形領域内に特徴点を設定する手段と、
前記特徴点を頂点とするメッシュを生成する手段と
を備えることを特徴とする請求項1乃至5の何れか1項に記載の画像処理装置。
【請求項7】
画像処理装置が行う画像処理方法であって、
画像からオブジェクトの領域をオブジェクト領域として抽出する工程と、
前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割工程と、
前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める工程と、
前記複数のメッシュのうち、該メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第1の特定工程と、
前記第1の特定工程で特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第2の特定工程と、
前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新工程と、
前記更新工程による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理工程と
を備えることを特徴とする画像処理方法。
【請求項8】
コンピュータを、請求項1乃至6の何れか1項に記載の画像処理装置が有する各手段として機能させるためのコンピュータプログラム。
【請求項1】
画像処理装置であって、
画像からオブジェクトの領域をオブジェクト領域として抽出する手段と、
前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割手段と、
前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める手段と、
前記複数のメッシュのうち、該メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第1の特定手段と、
前記第1の特定手段が特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第2の特定手段と、
前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新手段と、
前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理手段と
を備えることを特徴とする画像処理装置。
【請求項2】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が1つである場合、前記補正対象メッシュにおいて前記外部頂点と対角にある頂点を特定し、該特定した頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項1に記載の画像処理装置。
【請求項3】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が2つである場合、それぞれの前記外部頂点について、
前記補正対象メッシュにおいて前記外部頂点と隣接する非外部頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項1に記載の画像処理装置。
【請求項4】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が3つである場合、それぞれの前記外部頂点について、
前記補正対象メッシュにおける非外部頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項1に記載の画像処理装置。
【請求項5】
前記管理手段は、前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を符号化してから管理することを特徴とする請求項1乃至4の何れか1項に記載の画像処理装置。
【請求項6】
前記分割手段は、
前記包含領域を複数の矩形領域に分割する手段と、
前記複数の矩形領域のそれぞれについて、該矩形領域内に特徴点を設定する手段と、
前記特徴点を頂点とするメッシュを生成する手段と
を備えることを特徴とする請求項1乃至5の何れか1項に記載の画像処理装置。
【請求項7】
画像処理装置が行う画像処理方法であって、
画像からオブジェクトの領域をオブジェクト領域として抽出する工程と、
前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割工程と、
前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める工程と、
前記複数のメッシュのうち、該メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第1の特定工程と、
前記第1の特定工程で特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち1以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第2の特定工程と、
前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新工程と、
前記更新工程による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理工程と
を備えることを特徴とする画像処理方法。
【請求項8】
コンピュータを、請求項1乃至6の何れか1項に記載の画像処理装置が有する各手段として機能させるためのコンピュータプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2011−221619(P2011−221619A)
【公開日】平成23年11月4日(2011.11.4)
【国際特許分類】
【出願番号】特願2010−87349(P2010−87349)
【出願日】平成22年4月5日(2010.4.5)
【出願人】(000001007)キヤノン株式会社 (59,756)
【Fターム(参考)】
【公開日】平成23年11月4日(2011.11.4)
【国際特許分類】
【出願日】平成22年4月5日(2010.4.5)
【出願人】(000001007)キヤノン株式会社 (59,756)
【Fターム(参考)】
[ Back to top ]