(57)【要約】【課題】  グラディエント・メッシュによるオブジェクトの近似を効率的に行うための技術を提供すること。【解決手段】  メッシュ構造生成部１０２は、オブジェクト領域を包含する包含領域を複数のメッシュに分割し、メッシュ毎に、各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める。そして、１以上の頂点がオブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する。そして、オブジェクト領域内メッシュのうち、１以上の頂点がオブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する。そして、補正対象メッシュを構成する頂点群のうちオブジェクト領域の外部に位置している外部頂点の位置情報を、オブジェクト領域の枠部上の位置を示す位置情報に更新する。【選択図】  図１
2011221619.tif 000002
【特許請求の範囲】
【請求項１】
画像処理装置であって、
画像からオブジェクトの領域をオブジェクト領域として抽出する手段と、
前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割手段と、
前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める手段と、
前記複数のメッシュのうち、該メッシュを構成する頂点群のうち１以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第１の特定手段と、
前記第１の特定手段が特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち１以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第２の特定手段と、
前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新手段と、
前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が１つである場合、前記補正対象メッシュにおいて前記外部頂点と対角にある頂点を特定し、該特定した頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が２つである場合、それぞれの前記外部頂点について、
前記補正対象メッシュにおいて前記外部頂点と隣接する非外部頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記更新手段は、前記補正対象メッシュを構成する頂点群のうち前記外部頂点が３つである場合、それぞれの前記外部頂点について、
前記補正対象メッシュにおける非外部頂点と前記外部頂点とを結ぶ線分を求め、該求めた線分と前記オブジェクト領域の枠部との交点の位置を示す位置情報を、前記外部頂点の位置情報とする
ことを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記管理手段は、前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を符号化してから管理することを特徴とする請求項１乃至４の何れか１項に記載の画像処理装置。
【請求項６】
前記分割手段は、
前記包含領域を複数の矩形領域に分割する手段と、
前記複数の矩形領域のそれぞれについて、該矩形領域内に特徴点を設定する手段と、
前記特徴点を頂点とするメッシュを生成する手段と
を備えることを特徴とする請求項１乃至５の何れか１項に記載の画像処理装置。
【請求項７】
画像処理装置が行う画像処理方法であって、
画像からオブジェクトの領域をオブジェクト領域として抽出する工程と、
前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割工程と、
前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める工程と、
前記複数のメッシュのうち、該メッシュを構成する頂点群のうち１以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第１の特定工程と、
前記第１の特定工程で特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち１以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第２の特定工程と、
前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新工程と、
前記更新工程による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理工程と
を備えることを特徴とする画像処理方法。
【請求項８】
コンピュータを、請求項１乃至６の何れか１項に記載の画像処理装置が有する各手段として機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラスタ画像をグラディエント・メッシュで近似する際に、複雑な形状のオブジェクトをグラディエント・メッシュで表現するための解像度フリー表現技術に関するものである。
【背景技術】
【０００２】
従来、イラストや文字の解像度フリー表現には、オブジェクトの輪郭をベジェ、スプライン関数などで関数近似する手法が用いられている。オブジェクト領域内は、単一色、線形グラデーション、放射状グラデーションなどで塗りつぶすことができるが、複雑なグラデーションの表現は困難である。
【０００３】
解像度フリーで複雑なグラデーションを含むオブジェクトを描画するためには、Ａｄｏｂｅ  Ｉｌｌｕｓｔｒａｔｏｒ（登録商標）のグラディエント・メッシュ・ツールが一般に用いられている。グラディエント・メッシュでは、メッシュに色と勾配を与えて三次関数を生成することで複雑なオブジェクトを描画することができる（特許文献１、２）。
【０００４】
ラスタ画像中のオブジェクトを解像度フリー表現に変換するとき、イラストや文字などの色変化の少ないオブジェクトに関しては、前述のベジェ、スプライン関数を用いた方法により表現できる。
【０００５】
自然画像のような色が複雑に変化するオブジェクトを解像度フリー表現に変換する技術は幾つか提案されており、大きく３つのカテゴリに分類できる。三角形メッシュを用いた手法、高次のパラメトリック曲面を用いた手法、メッシュ以外の表現を用いた手法、である。
【０００６】
三角形メッシュを用いた方法では、オブジェクトの直線的なエッジを忠実に表現できる。しかし、滑らかな曲線を表現するとき、線形メッシュで曲線を忠実に近似することは困難であり、忠実に近似するためには多数のメッシュを用いなければならない。
【０００７】
高次のパラメトリック曲面を用いた手法では、曲線の表現も可能であり、より少ないメッシュ数で特徴曲線を近似することができる。高次のパラメトリック曲面を用いる手法としては、ベジェパッチを細分割して近似誤差を低減する手法（非特許文献１）、グラディエント・メッシュを用いて画像を近似する手法などが挙げられる（特許文献３、非特許文献３）。
【０００８】
メッシュ以外の表現を用いた手法では、画像の特徴線をベジェ曲線で近似し、曲線の両側に色情報を付加し、曲線の色を用いた偏微分方程式を解いて画像を描画するディフュージョン・カーブと呼ばれる解像度フリー表現手法が提案されている（非特許文献２）。また、境界曲線と特徴曲線と関連付けられた色を用いてカラー・グラディエントを生成する手法も提案されている（特許文献４）。
【０００９】
複雑な形状のオブジェクトをメッシュで近似するために、幾つかの方法が提案されている。パラメトリック曲面を用いた手法（特許文献３、非特許文献３）では、４頂点から成る規則メッシュを生成するため、オブジェクトの近似に頂点を過剰に与えてしまうことがある。また、適応的にメッシュ頂点を除去してオブジェクトを近似する手法（特許文献５）、メッシュの頂点をオブジェクト境界上に移動する手法（特許文献６）では、メッシュを直線で接続しているため、曲線近似が困難であるという課題も残る。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開平１１−３４５３４７号公報
【特許文献２】特許第４２２００１０号公報
【特許文献３】米国特許出願公開第２００８／０２７８４７９号明細書
【特許文献４】特許第３９８９４５１号公報
【特許文献５】特許第２８１５５７１号公報
【特許文献６】特開平１１−２５２９３号公報
【非特許文献】
【００１１】
【非特許文献１】Ｂｒｉａｎ  Ｐｒｉｃｅ，Ｗｉｌｌｉａｍ  Ｂａｒｒｅｔｔ，「Ｏｂｊｅｃｔ−ｂａｓｅｄ  ｖｅｃｔｏｒｉｚａｔｉｏｎ  ｆｏｒ  ｉｎｔｅｒａｃｔｉｖｅ  ｉｍａｇｅ  ｅｄｉｔｉｎｇ」，Ｉｎ  ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｐａｃｉｆｉｃ  Ｇｒａｐｈｉｃｓ  ２００６，２００６，ｖｏｌ．２２，ｎｏ．９−１１，ｐ．６６１−６７０．
【非特許文献２】Ａｌｅｘａｎｄｒｉｎａ  Ｏｒｚａｎ，Ａｄｒｉｅｎ  Ｂｏｕｓｓｅａｕ，Ｈｏｌｇｅｒ  Ｗｉｎｎｅｍｏｌｌｅｒ，Ｐａｓｃａｌ  Ｂａｒｌａ，Ｊｏｅｌｌｅ  Ｔｈｏｌｌｏｔ，Ｄａｖｉｄ  Ｓａｌｅｓｉｎ，「Ｄｉｆｆｕｓｉｏｎ  Ｃｕｒｖｅｓ：Ａ  Ｖｅｃｔｏｒ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｆｏｒ  Ｓｍｏｏｔｈ−Ｓｈａｄｅｄ  Ｉｍａｇｅｓ」，Ｉｎ  ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＳＩＧＧＲＡＰＨ  ２００８，２００８，ｖｏｌ．２７．
【非特許文献３】Ｙｕ−Ｋｕｎ  Ｌａｉ，Ｓｈｉ−Ｍｉｎ  Ｈｕ，Ｒａｌｐｈ  Ｒ．Ｍａｒｔｉｎ，「Ａｕｔｏｍａｔｉｃ  ａｎｄ  Ｔｏｐｏｌｏｇｙ−Ｐｒｅｓｅｒｖｉｎｇ  Ｇｒａｄｉｅｎｔ  Ｍｅｓｈ  Ｇｅｎｅｒａｔｉｏｎ  ｆｏｒ  Ｉｍａｇｅ  Ｖｅｃｔｏｒｉｚａｔｉｏｎ」，ＡＣＭ  ＳＩＧＧＲＡＰＨ  ２００９，ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｇｒａｐｈｉｃｓ，Ｖｏｌ．２８，Ｎｏ．３．
【発明の概要】
【発明が解決しようとする課題】
【００１２】
自然画像のような色が複雑に変化するオブジェクトを解像度フリー表現に変換するとき、高次のパラメトリック曲面を用いることで、少ないメッシュ数でオブジェクトを近似できる。しかし、オブジェクトの形状が複雑であるとき、表現能力、演算量、データ量について課題も残る。以下にその課題について説明する。
【００１３】
上述のベジェパッチを細分割して近似誤差を低減する手法では、高次のメッシュを用いるため、オブジェクト境界の近似を忠実に行うことができる。しかし、近似誤差を低減するためにメッシュを細分割しているため、オブジェクトの色変化が複雑な部分ではメッシュの数が増え、データ量が増大してしまう。
【００１４】
上述のグラディエント・メッシュを用いて画像を近似する手法では、色変化が複雑なオブジェクトにおいても、より少ないメッシュ数（データ量）で解像度フリー表現できる。しかしこれらの手法では、４頂点から成る規則メッシュを生成するため、オブジェクトの形状によっては、オブジェクトの色が単純な部分にもメッシュ頂点を過剰に与えてしまうことがある。また、過剰なメッシュ頂点による画質の劣化、演算量の増大などの問題も残る。
【００１５】
本発明は以上の問題に鑑みて成されたものであり、グラディエント・メッシュによるオブジェクトの近似を効率的に行うための技術を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の目的を達成するために、例えば、本発明の画像処理装置は以下の構成を備える。即ち、画像処理装置であって、画像からオブジェクトの領域をオブジェクト領域として抽出する手段と、前記オブジェクト領域を包含する包含領域を求め、該求めた包含領域を複数のメッシュに分割する分割手段と、前記複数のメッシュのそれぞれについて、該メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める手段と、前記複数のメッシュのうち、該メッシュを構成する頂点群のうち１以上の頂点が前記オブジェクト領域の内部に位置しているメッシュを、オブジェクト領域内メッシュとして特定する第１の特定手段と、前記第１の特定手段が特定したそれぞれのオブジェクト領域内メッシュのうち、該オブジェクト領域内メッシュを構成する頂点群のうち１以上の頂点が前記オブジェクト領域の外部に位置しているオブジェクト領域内メッシュを、補正対象メッシュとして特定する第２の特定手段と、前記補正対象メッシュを構成する頂点群のうち前記オブジェクト領域の外部に位置している頂点を外部頂点とし、該外部頂点の位置情報を、前記オブジェクト領域の枠部上の位置を示す位置情報に更新する更新手段と、前記更新手段による更新処理後、前記オブジェクト領域内メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を管理する管理手段とを備えることを特徴とする。
【発明の効果】
【００１７】
本発明の構成によれば、グラディエント・メッシュによるオブジェクトの近似を効率的に行うことができる。
【図面の簡単な説明】
【００１８】
【図１】画像処理装置の機能構成例を示すブロック図。
【図２】メッシュ構造生成部１０２が行う処理のフローチャート。
【図３】メッシュ適合部１０３が行う処理のフローチャート。
【図４】オブジェクト領域の一例を示す図。
【図５】第３の実施形態で扱うオブジェクト領域の一例を示す図。
【図６】ステップＳ２０１〜Ｓ２０３を説明する図。
【図７】ステップＳ３０１〜Ｓ３０５を説明する図。
【図８】グラディエント・メッシュ表現を説明する図。
【図９】コンピュータのハードウェア構成例を示す図。
【図１０】メッシュ構造生成部１０２が行う処理のフローチャート。
【図１１】ステップＳ１００１，Ｓ１００２における処理を説明する図。
【発明を実施するための形態】
【００１９】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載の構成の具体的な実施例の１つである。
【００２０】
［第１の実施形態］
図１を用いて、本実施形態に係る画像処理装置の機能構成例について説明する。オブジェクト抽出部１０１には、１以上のオブジェクトを含む画像が入力される。この「オブジェクト」とは、文字や物体像などを指し示しており、本実施形態では、この「オブジェクト」は、色のグラデーションを有しているものとして説明する。即ち、本実施形態では、色のグラデーションを有するオブジェクトに対するメッシュ符号化を行う。
【００２１】
そしてオブジェクト抽出部１０１は、この入力画像からオブジェクトの領域をオブジェクト領域として抽出する処理を行う。図４に、抽出されたオブジェクト領域の一例を示す。抽出にはグラブ・カット法という既知の方法を用いるが、他の抽出手法を用いても構わない。抽出されたオブジェクト領域のデータには、オブジェクト領域４０１の内部４０２を構成する各画素の画素値と、枠部（オブジェクト領域の境界線）４０３を構成する各画素の座標位置が含まれている。本実施形態では、画素値は、ＲＧＢのそれぞれの色成分が８ビットで表現されているものとして説明するが、グレースケール、ＣＭＹＫなどの色成分の種別、一つの色成分を構成するビット数、についてはこれに限定するものではない。また、オブジェクト領域のデータの構成については、オブジェクト領域の枠部４０３を構成する各画素の座標位置、オブジェクト領域の内部４０２を構成する各画素の画素値、が導出できるのであれば、他のデータ構成であっても良い。そしてオブジェクト抽出部１０１は、抽出したオブジェクト領域のデータを、後段のメッシュ構造生成部１０２に送出する。
【００２２】
図２を用いて、メッシュ構造生成部１０２が、オブジェクト領域のデータを用いて行う処理について説明する。ステップＳ２０１では、メッシュ構造生成部１０２は、入力画像においてオブジェクト領域を包含する包含領域を求め、求めた包含領域を複数の矩形（メッシュ）に分割することで、この複数のメッシュを生成する。本実施形態では、４つの頂点から構成されるメッシュを生成するが、３つの頂点から構成されるメッシュを生成しても良い。
【００２３】
ステップＳ２０２ではメッシュ構造生成部１０２は、ステップＳ２０１で生成したそれぞれのメッシュについて頂点データを求める。着目メッシュについて求めた頂点データは着目メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報、で構成されている。また、ステップＳ２０２ではメッシュ構造生成部１０２は、ステップＳ２０１で生成した各メッシュを構成する頂点間の接続関係を示す構造データも生成する。
【００２４】
ここで、図８を用いて、グラディエント・メッシュ表現について簡単に説明する。グラディエント・メッシュ（メッシュ）は、４つの頂点（頂点０〜頂点３）のそれぞれについての以下の情報によって表現されるものである。
【００２５】
・  頂点ｉ（ｉ＝０〜３）の位置情報ｍｉ
・  頂点ｉにおけるｕ方向、ｖ方向の勾配情報ｍｕｉ、ｍｖｉ
・  頂点ｉにおける色情報ｃｉ
・  頂点ｉにおける色のｕ方向、ｖ方向の勾配情報ｃｕｉ、ｃｖｉ
図８に示す如く、メッシュの形状は３次関数によって表現され、メッシュ内の座標ｍ（ｕ、ｖ）は以下の式で導出される。
【００２６】
【数１】
2011221619.tif 000003
【００２７】
ｕ、ｖは、０〜１の範囲内の実数である。また、ｍｕｖｉは、頂点ｉにおけるｕ方向及びｖ方向の微分値を示すが、一般にはｍｕｖｉには０を設定する。即ち、メッシュの形状は、頂点の位置情報と勾配情報とによって決まる。なお、勾配情報は、メッシュの輪郭の曲線形状を表していることが分かる。
【００２８】
なお、メッシュ内の座標ｍ（ｕ、ｖ）における色Ｃｏｌ（ｕ、ｖ）は、以下の置き換え手順１〜３を行ってから、上記の式を計算することで求めることができる。
【００２９】
（置き換え手順１）  上記の式において、座標ｍ（ｕ、ｖ）を色Ｃｏｌ（ｕ、ｖ）に置き換える
（手順２）  上記の式において、頂点０〜３の位置情報（ｍ０、ｍ１、ｍ２、ｍ３）を、頂点０〜３の色情報（ｃ０、ｃ１、ｃ２、ｃ３）に置き換える
（手順３）  上記の式において、頂点０〜３におけるｕ方向、ｖ方向の勾配情報（ｍｕ０、ｍｖ０、ｍｕ１、ｍｖ１、ｍｕ２、ｍｖ２、ｍｕ３、ｍｖ３）を、頂点０〜３における色のｕ方向、ｖ方向の勾配情報（ｃｕ０、ｃｖ０、ｃｕ１、ｃｖ１、ｃｕ２、ｃｖ２、ｃｕ３、ｃｖ３）に置き換える。
【００３０】
なお、頂点０〜３の色のｕ方向及びｖ方向の微分値を示すｃｕｖ０、ｃｕｖ１、ｃｕｖ２、ｃｕｖ３には０を設定する。即ち、メッシュ内の色は、頂点の色情報と色の勾配情報とによって決まる。なお、色の勾配情報を０としてレンダリングを行っても良い。本実施形態では、色の勾配情報は０として説明する。
【００３１】
上記のようなグラディエント・メッシュ表現は一般に用いられており、その詳細については特許文献３、非特許文献３で説明されているため、これ以上の詳細な説明は省略する。
【００３２】
なお、ここではグラディエント・メッシュのメッシュ勾配、及び色勾配の設定方法を示したが、メッシュの形状がパラメトリック曲面として表現され、メッシュ内のグラデーションさえ表現できれば、他の表現方法であっても構わない。例えば、三角形ベジェパッチでメッシュの形状を表現し、メッシュ内の色はＲＢＦｓ（Ｒａｄｉａｌ  Ｂａｓｉｓ  Ｆｕｎｃｔｉｏｎｓ）曲面で表現するなどの方法を用いても構わない。
【００３３】
次に、図６（ａ）を用いて、ステップＳ２０１及びＳ２０２における処理を、具体例を挙げて説明する。図６（ａ）の場合、ステップＳ２０１では、メッシュ構造生成部１０２は、オブジェクト領域４０１を包含する包含領域６９０を求め、求めた包含領域６９０を複数のメッシュに分割する。図６（ａ）において６０２は、分割された複数のメッシュのうちの１つを示しており、６０１は、メッシュ６０２を構成する頂点群のうちの１つを示している。ここで、頂点６０１は、オブジェクト領域４０１の外部に位置している。
【００３４】
図６（ａ）では、包含領域６９０は長方形であるが、オブジェクト領域を包含する領域であれば、その形状は長方形以外であっても良い。また、図６（ａ）では、包含領域６９０を縦横均等に分割しているが、分割方法についてはこれに限定するものではない。
【００３５】
次に、ステップＳ２０２では、メッシュ構造生成部１０２は、分割されたそれぞれのメッシュについて、メッシュを構成する各頂点の位置情報、勾配情報、色情報、色の勾配情報を求める。勾配情報としては何れも０とする。色情報については、頂点がオブジェクト領域４０１の外部に位置している場合、この頂点の色情報として、０を設定する。一方、頂点がオブジェクト領域４０１の内部に位置している場合、この頂点の色情報として、この頂点の位置に対応する、オブジェクト領域４０１上の画素の色情報を設定する。もちろん、頂点がオブジェクト領域４０１の内部に位置している場合、この頂点の色情報として、この頂点の位置に対応するオブジェクト領域４０１上の画素の周辺画素の色情報の平均値を設定する等、他の方法を用いて色情報を設定しても良い。また、勾配情報についても、一定値を設定する等、他の方法を用いて勾配情報を設定しても良い。
【００３６】
また上記の通り、ステップＳ２０２ではメッシュ構造生成部１０２は、構造データも生成するが、本実施形態では、この構造データには、各メッシュが必要か否かのフラグ情報が含まれている。すべてのメッシュのフラグ情報が「必要」を示している状態が初期状態となる。もちろん、各頂点に番号を振り、必要となるメッシュに４つの頂点番号を保持させてメッシュ構造を表現するなど、他の構造表現を用いても構わない。
【００３７】
図２に戻って、ステップＳ２０３でメッシュ構造生成部１０２は、ステップＳ２０１で生成したそれぞれのメッシュの各頂点の位置情報を参照する。そしてメッシュ構造生成部１０２は、ステップＳ２０１で得たそれぞれのメッシュのうち「メッシュを構成する頂点群のうち１以上の頂点がオブジェクト領域の内部に位置しているメッシュ」を、オブジェクト領域内メッシュとして特定（第１の特定）する。ここでは、オブジェクト領域を閉領域として定義することによって、オブジェクト領域に対する頂点の内外判定を行っているが、もちろん、陰関数を用いる等、他の判定方法を用いても構わない。そしてメッシュ構造生成部１０２は、構造データ内の非オブジェクト領域内メッシュのフラグ情報を「不必要」に更新する。これにより、非オブジェクト領域内メッシュ（に係るデータ）を削除対象とすることができる。
【００３８】
ステップＳ２０４ではメッシュ構造生成部１０２は、構造データを参照し、フラグ情報が「不必要」となっているメッシュの頂点データを削除する。
【００３９】
図６（ｂ）を用いて、ステップＳ２０３及びステップＳ２０４について説明する。図６（ｂ）には、図６（ａ）に示したメッシュ群から、頂点データを削除したメッシュを除いたメッシュ（オブジェクト領域内メッシュ）が残っている。この残ったオブジェクト領域内メッシュによりオブジェクト領域を近似していることが分かる。
【００４０】
即ち、係る処理によれば、オブジェクト領域を包含するように複数のメッシュによりオブジェクト領域の概形を近似できる。そしてメッシュ構造生成部１０２は、構造データ、オブジェクト領域内メッシュについての頂点データ、を後段のメッシュ適合部１０３に送出する。
【００４１】
図３を用いて、メッシュ適合部１０３の動作について説明する。先ずステップＳ３０１においてメッシュ適合部１０３は、オブジェクト領域内メッシュの頂点データをメッシュ構造生成部１０２から取得する。そして、メッシュ適合部１０３は、それぞれのオブジェクト領域内メッシュのうち「オブジェクト領域内メッシュを構成する頂点群のうち１以上の頂点がオブジェクト領域外にあるオブジェクト領域内メッシュ」を補正対象メッシュとして特定（第２の特定）する。そしてメッシュ適合部１０３は、特定したそれぞれの補正対象メッシュのうち未だ選択していない補正対象メッシュの頂点データを選択する。
【００４２】
次にステップＳ３０２ではメッシュ適合部１０３は、次のような処理を行う。即ち、ステップＳ３０１で選択した頂点データ（選択頂点データ）内のそれぞれの頂点の位置情報のうち、オブジェクト領域外にある頂点（外部頂点）の位置情報を、オブジェクト領域の枠部上の位置を示す位置情報に更新する。即ち、外部頂点の位置情報を、外部頂点をオブジェクト領域の枠部上に移動させた後の外部頂点の位置情報に更新する。これにより、補正対象メッシュを構成する全ての頂点の位置情報は、何れもオブジェクト領域内（若しくはオブジェクト領域の枠部上）の位置を示していることになる。そしてメッシュ適合部１０３は、この更新処理後、外部頂点の色情報として、外部頂点の更新済み位置情報が示す位置に対応するオブジェクト領域の枠部上の位置における画素の色情報を設定する。
【００４３】
そしてステップＳ３０４ではメッシュ適合部１０３は、ステップＳ３０２による処理後の、選択頂点データ内のそれぞれの位置情報（必要に応じてオブジェクト領域の枠部）を用いて、選択頂点データ内のそれぞれの勾配情報を再計算する。
【００４４】
そしてステップＳ３０５ではメッシュ適合部１０３は、全ての補正対象メッシュの頂点データを選択したか否かを判断する。この判断の結果、選択したと判断した場合には図３のフローチャートに従った処理を終了し、未だ選択していない頂点データがあると判断した場合には、処理をステップＳ３０１に戻す。そしてステップＳ３０１では、未だ選択していない頂点データを選択し、この選択した頂点データを用いてステップＳ３０２以降の処理を行う。
【００４５】
図７を用いて、ステップＳ３０１〜Ｓ３０５の処理について、具体例を挙げて説明する。メッシュ６０２は上記の通り、オブジェクト領域４０１の外部に位置する頂点６０１を有している。然るにこのメッシュ６０２は補正対象メッシュであり、頂点６０１は外部頂点であるので、この頂点６０１の位置情報を、オブジェクト領域４０１の枠部上の位置を示す位置情報に更新する。これにより、図７（ａ）に示す如く、頂点６０１の位置はオブジェクト領域４０１の枠部上に移動することになる。なお、メッシュ６０２は頂点６０１以外にも外部頂点を２つ有しているので、この２つの外部頂点のそれぞれについても同様の処理を行う。その結果、図７（ａ）に示す如く、メッシュ６０２を構成する４つの頂点は何れもオブジェクト領域４０１の内部（３つは枠部上）に位置することになる。
【００４６】
ここで、補正対象メッシュの外部頂点の移動方向は、この補正対象メッシュが有する外部頂点の数に応じて異なる。補正対象メッシュの外部頂点の数が１の場合、この補正対象メッシュの４つの頂点のうち外部頂点の対角にある頂点（対角頂点）を特定し、外部頂点と対角頂点との間を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点の更新後の位置とする。
【００４７】
補正対象メッシュの外部頂点の数が２の場合、一方の外部頂点（外部頂点１）と、外部頂点１と隣接する補正対象メッシュの非外部頂点と、を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点１の更新後の位置とする。同様に、他方の外部頂点（外部頂点２）と、外部頂点２と隣接する補正対象メッシュの非外部頂点と、を結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点２の更新後の位置とする。
【００４８】
補正対象メッシュの外部頂点の数が３の場合、何れの外部頂点も、外部頂点と隣接する補正対象メッシュの非外部頂点とを結ぶ線分とオブジェクト領域の枠部との交点の位置を、外部頂点の更新後の位置とする。
【００４９】
なお、外部頂点の更新後の位置をオブジェクト領域の枠部上の位置に更新する為の処理については、上記の処理に限定するものではなく、他の処理によって実現させても良い。例えば、オブジェクト領域の枠部上で外部頂点から最も近い位置を求め、この求めた位置を外部頂点の更新後の位置としても良い。
【００５０】
外部頂点の位置情報を更新した後のメッシュ６０２を図７（ｂ）に示す。そして位置情報の更新を行うと、次に、図７（ｃ）に示す如く、メッシュ６０２の形状がオブジェクト領域４０１の枠部４０３に沿うように、外部頂点６０１（図６（ｂ）では更にもう１つの外部頂点）の勾配情報を更新する。ここでは、オブジェクト領域４０１の枠部４０３を表現しているメッシュ６０２の部分と、オブジェクト領域４０１の枠部４０３との距離誤差が減少するように反復的にメッシュの勾配情報を更新する。もちろん、外部頂点でのオブジェクト領域４０１の枠部４０３の微分係数を用いて勾配情報を求める等、他の方法を用いても構わない。
【００５１】
なお、ステップＳ３０４における処理は、メッシュ群によるオブジェクト領域の形状の近似精度を高める為のものであり、高い精度を要求しないのであれば、ステップＳ３０４における処理は省いても構わない。
【００５２】
また、メッシュ適合部１０３は、図３のフローチャートに従った処理を終了した後、構造データ、それぞれのオブジェクト領域内メッシュの頂点データ、を後段の符号化部１０４に送出する。
【００５３】
図１に戻って、符号化部１０４は、メッシュ適合部１０３による上記処理によって得られたメッシュデータを符号化して管理する。メッシュデータには、以下の項目がテキストとして記されている。
【００５４】
・  メッシュのｘ方向の頂点数、メッシュのｙ方向の頂点数、領域数等を含むヘッダ
・  それぞれのメッシュの頂点データ
・  構造データ
本実施形態では、符号化部１０４は、このような項目の内容が記されたテキストデータとしてのメッシュデータをｚｉｐ符号化して管理しているが、非可逆符号化を含めた他の符号化方法を用いても構わない。もちろん、頂点データを導出できるのであれば、他のデータ記述方法でも構わない。同様に、構造データについても、上記の内容が得ることができるのであれば、そのデータ構造については特に限定するものではない。
【００５５】
以上の説明により、本実施形態によれば、オブジェクト領域の形状に合わせて不規則構造を持ったメッシュ群を生成するので、メッシュ群によるオブジェクト領域の形状の近似を効率的に行うことができる。
【００５６】
＜第１の実施形態の変形例＞
図１に示した各部はハードウェアで構成しても良いが、ソフトウェア（コンピュータプログラム）として実装しても良い。この場合、このソフトウェアは、ＰＣ（パーソナルコンピュータ）等、一般のコンピュータのメモリにインストールされることになる。そしてこのコンピュータのＣＰＵがこのインストールされたソフトウェアを実行することで、このコンピュータは、上述の画像処理装置の機能（図１に示した各部の機能）を実現することになる。即ち、このコンピュータは、上述の画像処理装置に適用することができる。図９を用いて、第１の実施形態に係る画像処理装置として適用可能なコンピュータのハードウェア構成例について説明する。
【００５７】
ＣＰＵ９０１は、ＲＡＭ９０２やＲＯＭ９０３に格納されているコンピュータプログラムやデータを用いて、コンピュータ全体の制御を行うと共に、画像処理装置が行うものとして説明した上述の各処理を実行する。即ち、図１に示した各部が行うものとして上述した各処理を実行する。
【００５８】
ＲＡＭ９０２は、コンピュータ読み取り可能な記憶媒体の一例である。ＲＡＭ９０２は、外部記憶装置９０７や記憶媒体ドライブ９０８からロードされたコンピュータプログラムやデータ、Ｉ／Ｆ（インターフェース）９０９を介して外部装置から受信したデータなどを一時的に記憶するためのエリアを有する。更に、ＲＡＭ９０２は、ＣＰＵ９０１が各種の処理を実行する際に用いるワークエリアを有する。即ち、ＲＡＭ９０２は、各種のエリアを適宜提供することができる。ＲＯＭ９０３は、コンピュータ読み取り可能な記憶媒体の一例であり、コンピュータの設定データや、ブートプログラムなどが格納されている。
【００５９】
キーボード９０４、マウス９０５は、コンピュータの操作者が操作することで、各種の指示をＣＰＵ９０１に対して入力することができる。表示装置９０６は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ９０１による処理結果を画像や文字などでもって表示することができる。例えば、上記入力画像を表示したり、抽出したオブジェクト領域やオブジェクト領域内メッシュを明示的に表示したり、メッシュ符号化の過程で求めたパラメトリック曲面を表示したりすることができる。
【００６０】
外部記憶装置９０７は、コンピュータ読み取り可能な記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置９０７には、ＯＳ（オペレーティングシステム）や、図１に示した各部の機能をＣＰＵ９０１に実現させるためのコンピュータプログラムやデータ、上記入力画像のデータ、既知の情報として説明した情報等が保存されている。外部記憶装置９０７に保存されているコンピュータプログラムやデータは、ＣＰＵ９０１による制御に従って適宜ＲＡＭ９０２にロードされ、ＣＰＵ９０１による処理対象となる。
【００６１】
記憶媒体ドライブ９０８は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置９０７やＲＡＭ９０２に出力する。なお、外部記憶装置９０７に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ９０８に読み取らせても良い。
【００６２】
Ｉ／Ｆ９０９は、外部装置をコンピュータに接続する為のものである。例えば、ディジタルカメラなど、上記入力画像を取得するための装置を、このＩ／Ｆ９０９に接続し、この装置から入力画像をＩ／Ｆ９０９を介してＲＡＭ９０２や外部記憶装置９０７に取得するようにしても良い。９１０は、上述の各部を繋ぐバスである。
【００６３】
上記構成において、本コンピュータの電源がＯＮになると、ＣＰＵ９０１はＲＯＭ９０３に格納されている上記ブートプログラムに従って、外部記憶装置９０７からＯＳをＲＡＭ９０２にロードする。この結果、キーボード９０４、マウス９０５を介した情報入力操作が可能となり、表示装置９０６にＧＵＩを表示することが可能となる。ユーザが、キーボード９０４やマウス９０５を操作し、外部記憶装置９０７に格納された画像処理用アプリケーションプログラムの起動指示を入力すると、ＣＰＵ９０１はこのプログラムをＲＡＭ９０２にロードし、実行する。これにより、本コンピュータが上記の画像処理装置として機能することになる。
【００６４】
ＣＰＵ９０１が実行する画像処理用アプリケーションプログラムは、基本的に図１の各処理部、及び図２、図３の各ステップに相当する関数を備えることになる。ここで、符号化したグラディエント・メッシュのデータは外部記憶装置９０７に保存することになる。
【００６５】
［第２の実施形態］
本実施形態では、第１の実施形態に加え、オブジェクト領域の形状の近似精度を高めるための前処理を行う。以下では、第１の実施形態と異なる点のみについて説明する。即ち、以下に説明する点以外については、第１の実施形態と同様である。
【００６６】
図１０を用いて、メッシュ構造生成部１０２の動作について説明する。ステップＳ１００１ではメッシュ構造生成部１０２は、オブジェクト領域を包含する包含領域を求め、求めた包含領域を複数の矩形領域に分割する。即ち、オブジェクト領域を包含するように格子をオブジェクト領域上に生成する。ステップＳ１００２ではメッシュ構造生成部１０２は、矩形領域毎に特徴点を設定する。そして隣接する特徴点間を結ぶことで、特徴点を頂点とするメッシュを生成する。
【００６７】
図１１（ａ）、（ｂ）を用いて、ステップＳ１００１、Ｓ１００２における処理について、具体例を挙げて説明する。図１１（ａ）の場合、ステップＳ１００１では、メッシュ構造生成部１０２は、オブジェクト領域４０１を包含するように包含領域１１０２をオブジェクト領域上に生成し、この包含領域１１０２を複数の矩形領域に分割する。１１０３は分割された矩形領域のうちの１つである。
【００６８】
次に、矩形領域毎に、メッシュの頂点として用いる特徴点を設定する。ここで、矩形領域内に枠部４０３が含まれているか否かに応じて、この矩形領域に対する特徴点の設定方法が異なる。
【００６９】
矩形領域内に枠部４０３が含まれている場合、この含まれている枠部４０３上で最も曲率が高い位置に特徴点を設定する。一方、矩形領域内に枠部４０３が含まれていない場合、この矩形領域の中央位置に特徴点を設定する。例えば、矩形領域１１０３内にはオブジェクト領域４０１の枠部４０３は含まれていないので、この矩形領域１１０３内の中央位置に特徴点（黒丸）を設定する。もちろん、１つの矩形領域に対して１つの特徴点を設定するのであれば、他の方法を用いて設定しても良い。
【００７０】
そしてこのようにして設定した特徴点を頂点とするメッシュ群を、図１１（ｂ）に示す如く生成する。即ち、矩形領域の数がＮ×Ｍの場合、生成されるメッシュの数もＮ×Ｍとなる。なお、メッシュの外側にある頂点がオブジェクト領域の内側に入らなければ、メッシュ生成方法には他の方法を用いても良い。
【００７１】
［第３の実施形態］
第１，２の実施形態では、オブジェクト領域は、その内部が埋まっているものとして説明した。本実施形態では、ドーナッツ型のような、内部に穴が空いているオブジェクト領域（非オブジェクト領域を囲むように構成されているオブジェクト領域）を用いる場合について説明する。以下では、第１の実施形態と異なる点のみについて説明する。即ち、以下に説明する点以外については、第１の実施形態と同様である。
【００７２】
オブジェクト抽出部１０１は第１の実施形態と同様に動作してオブジェクト領域のデータを生成するのであるが、本実施形態では更に、入力画像を構成する各画素がオブジェクト領域内であるかオブジェクト領域外であるかを示すマスク画像も生成する。また、本実施形態では、図５（ａ）に示したような穴１２０１の枠部を構成する各画素の座標位置のデータも、オブジェクト領域のデータに含まれる。
【００７３】
メッシュ構造生成部１０２は、枠部を構成する各画素の座標位置のデータを用いて閉領域を特定し、更にマスク画像においてこの閉領域内の画素の値を特定することで、この閉領域が穴の部分であるか否かを特定することができる。そしてこの閉領域が穴であれば、この穴の部分をオブジェクト領域外として扱い、以降は第１の実施形態と同様の処理を行う。その結果、図５（ｂ）に示す如く、穴の部分のメッシュを除外することができる。
【００７４】
［その他の実施形態］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
2011221619.tif 000004
【図２】
2011221619.tif 000005
【図３】
2011221619.tif 000006
【図４】
2011221619.tif 000007
【図５】
2011221619.tif 000008
【図６】
2011221619.tif 000009
【図７】
2011221619.tif 000010
【図８】
2011221619.tif 000011
【図９】
2011221619.tif 000012
【図１０】
2011221619.tif 000013
【図１１】
2011221619.tif 000014