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