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