画像処理装置、画像処理方法
【課題】 ３頂点曲線メッシュを効率的に符号化するための技術を提供すること。
【解決手段】 メッシュ毎に、辺毎の情報と該メッシュ中の頂点毎の色を記述したメッシュデータを生成する。辺毎に、該辺の情報と、該辺の両端の情報と、該辺がエッジ線から生成されたものか否かを示すフラグ値と、該辺上の各頂点の色と、該辺の制御点の座標と、を記述した辺データを生成する。
【解決手段】 メッシュ毎に、辺毎の情報と該メッシュ中の頂点毎の色を記述したメッシュデータを生成する。辺毎に、該辺の情報と、該辺の両端の情報と、該辺がエッジ線から生成されたものか否かを示すフラグ値と、該辺上の各頂点の色と、該辺の制御点の座標と、を記述した辺データを生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像をベクトル表現する画像処理技術に関する。特にラスタ画像を、メッシュで表現するベクトル表現技術に関するものである。
【背景技術】
【０００２】
従来から、画像をベクトル表現する技術は広く知られている。ベクトル表現された画像は、画像の拡大縮小時に画質劣化が少ない、画像の編集がし易い、高い圧縮率が実現できるなどの利点がある。
【０００３】
イラストや文字をベクトル表現する場合には、オブジェクトの輪郭をベジェ、スプライン関数などで近似する手法が用いられている。オブジェクトの領域内は、単一色、線形グラデーション、放射状グラデーションなどで塗ることができるが、複雑なグラデーションの表現は困難である。
【０００４】
複雑なグラデーションを含むオブジェクトをベクトル表現する場合には、Ａｄｏｂｅ Ｉｌｌｕｓｔｒａｔｏｒ（登録商標）のグラディエント・メッシュ・ツールが一般に用いられている。グラディエント・メッシュでは、メッシュに色と勾配を与えて３次関数を生成することで複雑なグラデーションを含むオブジェクトを描画できる（特許文献１）。
【０００５】
グラディエント・メッシュは４頂点から成る曲線メッシュであるが、３頂点から成る曲線メッシュにより、複雑なグラデーションをベクトル表現する技術が知られている（非特許文献１）。画像内のエッジを線分群として抽出し（以下エッジ線と呼ぶ）、エッジ線を再現する３頂点曲線メッシュを構成することでベクトル表現を行う。ここで、３頂点曲線メッシュとは、メッシュの頂点数が３であり、頂点間を結ぶメッシュの辺が直線または曲線であるものとする。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特登録０４２２００１０
【非特許文献】
【０００７】
【非特許文献１】Ｔｉａｎ Ｘｉａ， Ｂｉｎｂｉｎ Ｌｉａｏ， ａｎｄ Ｙｉｚｈｏｕ Ｙｕ， 「Ｐａｔｃｈ−Ｂａｓｅｄ Ｉｍａｇｅ Ｖｅｃｔｏｒｉｚａｔｉｏｎ ｗｉｔｈ Ａｕｔｏｍａｔｉｃ Ｃｕｒｖｉｌｉｎｅａｒ Ｆｅａｔｕｒｅ Ａｌｉｇｎｍｅｎｔ」， ＡＣＭ ＳＩＧＧＲＡＰＨ Ａｓｉａ ２００９， Ｖｏｌ．２８， Ｎｏ．５．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
自然画像のような色が複雑に変化するオブジェクトを曲線メッシュによりベクトル表現することを考える。直線メッシュに対して曲線メッシュは、オブジェクトの形状や特徴を曲線で近似するため、より少ないメッシュ数でオブジェクトを近似できる。
【０００９】
上述のグラディエント・メッシュを用いてオブジェクトを近似するとき、４頂点から成る曲線メッシュを規則格子状に構築する手法が知られている。この手法ではメッシュの接続関係を保持する必要がないため、データ表現として効率が良いが、メッシュ制御が局所的にできないため、複雑形状を近似するときにメッシュ数が増え、データ量が増大してしまう。
【００１０】
上述の３頂点曲線メッシュでは、メッシュ制御が局所的にできるため、少ないメッシュ数でオブジェクトを近似できる。従来、３頂点曲線メッシュはメッシュ単位に符号化され、メッシュ間で共有される頂点、辺、色を考慮していないため、符号化効率が低くデータ量が増大してしまう。
【００１１】
本発明は以上の問題に鑑みて成されたものであり、３頂点曲線メッシュを効率的に符号化するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の目的を達成するために、例えば、本発明の画像処理装置は、入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置であって、前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て手段と、前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる情報割り当て手段と、分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記情報割り当て手段が割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て手段が割り当てた色を示す情報と、を記述したメッシュデータを生成し、前記情報割り当て手段が情報を割り当てた辺毎に、該辺に対して前記情報割り当て手段が割り当てた情報と、該辺の両端位置の座標と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て手段が割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、分割したメッシュ毎に生成したメッシュデータ及び前記情報割り当て手段が情報を割り当てた辺毎に生成した辺データ、を含むデータを、前記入力画像の符号化データとして生成する生成手段とを備えることを特徴とする。
【発明の効果】
【００１３】
本発明の構成によれば、３頂点曲線メッシュの符号化を効率的に行うことができる。
【図面の簡単な説明】
【００１４】
【図１】画像処理装置の機能構成例を示すブロック図。
【図２】エッジ線として望ましくない結果を説明する図。
【図３】曲線メッシュ生成部１０３が行う処理のフローチャート。
【図４】メッシュ同士の重なりについて説明する図。
【図５】メッシュ生成方法を説明する図。
【図６】形状情報を説明する図。
【図７】符号化部１０５が生成する符号化データの構成例を示す図。
【図８】ベジエパッチの分割例を示す図。
【図９】コンピュータのハードウェア構成例を示すブロック図。
【図１０】復号する装置の機能構成例を示すブロック図。
【図１１】第３の実施形態で取り扱う３頂点曲線メッシュの形状情報、色情報を説明する図。
【発明を実施するための形態】
【００１５】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載した構成の具体的な実施例の一つである。
【００１６】
［第１の実施形態］
本実施形態に係る説明に先立って、先ず、曲線メッシュについて説明する。本実施形態では、曲線メッシュを構成する３つの頂点間を結ぶ曲線はベジェ曲線、Ｂ−スプライン等の如何なる曲線であっても良い。本実施形態では説明上、各曲線メッシュにパラメトリック曲面の１つである３頂点のベジェパッチを用いる。ベジェパッチの中でも特に３次のベジェパッチでは、曲線メッシュの各辺は３次のベジェ曲線となるため、曲線メッシュを生成したのちに、ユーザによる編集が容易であるというメリットがある。Ｐ１、Ｐ２、Ｐ３を頂点とする３次のベジェパッチ内の点は以下の式で表される。
【００１７】
【数１】
【００１８】
ここで、ｓ、ｔ、ｕはパッチ内の重心座標である。また、ｐ１，ｐ２，ｐ３はそれぞれ、頂点Ｐ１，Ｐ２，Ｐ３の座標値である。また、ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ６、ｃ７は、曲線パッチの形状を定めるパラメータである。
【００１９】
次に、入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュ（曲線メッシュ）を単位に符号化するメッシュ符号化処理を実行する画像処理装置の機能構成例について、図１のブロック図を用いて説明する。
【００２０】
画像入力部１０１には、ラスタ表現の入力画像が入力される。この入力画像はカラー画像、グレー画像、白黒画像のいずれでも構わない。また、入力画像は矩形画像でも構わないし、画像の一部をベクトル化したい場合には背景部を透過色に設定した画像等、切り出された領域が与えられても良い。そして画像入力部１０１は、この入力された入力画像を後段の特徴線構成部１０２に送出する。
【００２１】
特徴線構成部１０２は、画像入力部１０１から受け取った入力画像中に特徴線を構成する。本実施形態ではこの特徴線には、エッジ線を用いる。この場合、特徴線構成部１０２は、入力画像からエッジを構成する画素（エッジ画素）を抽出するエッジ抽出部と、エッジ抽出部が抽出したエッジ画素を連結させてエッジ線を構成するエッジ構成部と、を有することになる。
【００２２】
エッジ抽出部は、入力画像からキャニー法という既知の方法を用いてエッジ画素を抽出する。もちろん、他の方法を用いてエッジ画素を抽出しても良い。次にエッジ構成部は、抽出されたエッジ画素のうち、隣接するもの同士を結ぶ線分を構成することで、エッジを再現する線分群（エッジ線）を構成する。隣接するエッジ画素間を結んで線分群を構成する際に、注目エッジ画素の上、下、左、右にある４つの画素が隣接しているとみなす４連結接続がある。また、この４方向に加えて右上、右下、左上、左下にある４つの画素も隣接していると見なす８連結接続もある。本実施形態では８連結接続を用いる。
【００２３】
しかし、エッジ抽出部がキャニー法を用いて抽出したエッジ画素に対して、８連結接続で隣接しているとみなせる画素を結ぶと、エッジ線として望ましくない結果が得られる場合がある。このケースについて、図２を用いて説明する。
【００２４】
図２（ａ）〜（ｃ）には画像中のある領域を構成する画素群を示しており、１つの四角形が１つの画素を表している。また、斜線で示している四角形がエッジ抽出部が抽出したエッジ画素を表しており、斜線がない四角形がエッジ画素以外の画素（非エッジ画素）を表している。
【００２５】
図２（ａ）に示したエッジ画素群について、８連結接続で隣接したエッジ画素を結ぶと、図２（ｂ）に示すように、エッジ画素２０１、２０２、２０３を結ぶようなループが発生してしまう。図２（ａ）に示すようなエッジ画素が検出された場合、このようなループの発生を抑制する必要がある。そこで本実施形態では、８連結接続を行う前に、Ｈｉｌｄｉｔｃｈ細線化法という既知の手法を用いることで、この問題を解決する。図２（ａ）に示したエッジ画素群に対してＨｉｌｄｉｔｃｈ細線化を行うと、図２（ｂ）に示したエッジ画素２０１は非エッジ画素となる。その結果、図２（ｃ）に示すように、エッジ画素（２０４〜２０７）がループのない１つのエッジ線によって結ばれることになる。
【００２６】
なお、特徴線にはエッジ線以外にも、例えば入力画像中のオブジェクトの領域の輪郭などが考えられる。ここでオブジェクトとは、文字や物体像等を指している。
【００２７】
既に述べたように、入力画像の一部をベクトル化するという目的で、入力画像の一部が透過色に設定されている場合は、透過色と非透過色の境界に有る画素がオブジェクトの輪郭画素となる。オブジェクトの輪郭画素を１つの線分群にまとめる処理は、エッジ構成部が行う処理と同様の処理に従って隣接する画素同士をつなぎ合わせることで実現できる。これは、入力画像内の異なる属性の領域の間の境界線にある画素についても同様である。
【００２８】
また、特徴線構成部１０２は、入力画像を領域分割し、その境界線を特徴線としても良い。領域分割は最近傍法を用いたもの、ＥＭアルゴリズムを利用したものなど、多くの手法が知られている。
【００２９】
図１に戻って、曲線メッシュ生成部１０３は、特徴線が再現可能で且つメッシュ同士の重なりが無いように、入力画像をメッシュ群に分割する。曲線メッシュ生成部１０３が行う処理について、同処理のフローチャートを示す図３を用いて説明する。もちろん、図３のフローチャートに示した各ステップにおける処理の主体は何れも曲線メッシュ生成部１０３である。
【００３０】
先ずステップＳ３０１では、入力画像に対して初期メッシュ群を生成する。この初期メッシュは、エッジ線を再現するようなメッシュとして生成される。さらに、初期メッシュは、エッジ線を再現するメッシュの辺を、エッジ線に沿うように曲線化してもメッシュ同士が重ならないように生成する。
【００３１】
非特許文献１では、エッジ線を忠実に再現する十分に短い線分群をメッシュの辺とし、かつ、ラスタ画像の全画素を頂点とする直線メッシュを生成する。この生成方法について、図５（ａ）を用いて説明する。図５（ａ）において実線はエッジ線を示しており、点線はその他のメッシュの辺、黒い丸はラスタ画像中の画素を示している。エッジ線５０１、５０２、５０３、５０４は何れも、メッシュの辺として用いられている。
【００３２】
また他の例では、特徴線を忠実に再現する直線メッシュ、つまり特徴線を構成する全ての線分がメッシュの辺となる直線メッシュを生成する。このように生成した直線メッシュは、特徴線に沿った辺を曲線化するまでもなく特徴線を忠実に再現している為、曲線化に伴ってメッュ同士が重なるという問題は起きない。このケースについて図５（ｂ）を用いて説明する。
【００３３】
図５（ａ）と同様、実線はエッジ線を示しており、点線はその他のメッシュの辺、黒い丸はラスタ画像中の画素を示している。エッジ線５１１、５１２、５１３、５１４は何れも、メッシュの辺として用いられているが、ラスタ画像の画素を散乱的にサンプリングして頂点としている。このときのサンプリング頂点はラスタ画像の特徴量などから決定するが、エッジ線を再現するメッシュを生成することができるのであれば、他の方法を用いても構わない。ここでは、制約付きドロネー三角形分割を利用することで、特徴線を忠実に再現する直線メッシュを生成している。制約付きドロネー三角形分割は、点群と制約条件を与えると、与えられた点群を頂点とし、かつ制約条件を満たす直線メッシュを生成するアルゴリズムである。ここでの制約条件とは、点群の一部を結ぶ線分である。もちろん、エッジ線を再現するメッシュを生成することができるのであれば、他の方法を用いても構わない。
【００３４】
図３に戻って、ステップＳ３０７では、簡略化された曲線メッシュを生成する。簡略化された曲線の生成は、非特許文献１に記載の方法と同様の手順を踏むことで実現できる。つまり、初期メッシュのうち優先度の低いメッシュ同士を統合して大きなメッシュにまとめる処理と、エッジ線に沿うメッシュの辺を曲線化する処理と、を繰り返す。その曲線化の際に、メッシュ同士が重なってしまうような統合は行わないという制約を設けることで、メッシュ同士の重なりを防ぐ。
【００３５】
図４を用いて、メッシュ同士の重なりについて説明する。図４において、実線は特徴線を表現するメッシュの辺、点線は特徴線以外のメッシュの辺を示し、図４（ａ）、（ｃ）はメッシュの統合前、図４（ｂ）、（ｄ）は、それぞれ図４（ａ）、（ｃ）のメッシュの統合後である。
【００３６】
図４（ａ）、（ｂ）を例に、特徴線上の頂点４０２を頂点４０１に統合する場合を考える。特徴線を表現するメッシュの辺４０４、４０５は、統合された頂点４０２を近似するように統合・曲線化され、特徴線を表現するメッシュの辺４０７となる。また、図４（ｂ）で示されるように、特徴線以外のメッシュの辺４０６は、頂点４０２の統合により、頂点４０１に接続される。ここで、曲線で表現されているメッシュの辺４０７と直線で表現されているメッシュの辺４０６が交差していることが分かる。このような状態が、メッシュ同士が重なっている状態である。メッシュの重なりはベクトル表現してレンダリングした際、画質劣化の大きな原因となるため、極力避けなければならない。また図４（ｃ）、（ｄ）では、同様の処理を行ったとき、曲線で表現されているメッシュの辺４０７と直線で表現されているメッシュの辺４０６は交差していない。このような状態は、メッシュ同士が重なっていない良好な状態である。
【００３７】
以下では、簡略化された曲線生成処理（ステップＳ３０７）において、非特許文献１で述べられていない部分を補う形で説明する。曲線メッシュ生成処理（ステップＳ３０７）は基本的には、優先度の低いメッシュ同士を統合して大きなメッシュにまとめる処理（ステップＳ３０３）と、エッジ線に沿うメッシュの辺を曲線化する処理（ステップＳ３０４）と、を交互に繰り返す処理である。ステップＳ３０３及びステップＳ３０４における処理は公知であり、非特許文献１に記載の方法に従って行えば良い。なお非特許文献１ではステップＳ３０３において統合するメッシュを決定する優先度の基準にＱｕａｄｒｉｃ ｅｒｒｏｒ ｍｅｔｒｉｃ法という公知の手法を用いているが、面積の小さいメッシュから優先的に統合するなど、様々な方法が考えられる。また非特許文献１ではステップＳ３０４において特徴線をベジェ曲線によって近似しているが、本実施形態で既に述べたようにＢ−スプライン曲線等を用いてもかまわない。特徴線に沿うように曲線のパラメータを設定するアルゴリズムの詳細は非特許文献１では述べられていないが、本実施形態では最小二乗法を用いる。
【００３８】
次に、ステップＳ３０５における処理について説明する。ステップＳ３０５における処理の目的は、ステップＳ３０４でメッシュの辺を曲線化したことに伴い、メッシュ同士が重なっていないかどうかを判定することである。メッシュ同士が重なっているか否かの判定は、メッシュの辺同士が交差しているか否かを判定することで行う。メッシュの辺のうち、線分同士が重ならないことは保証できるため、重なりを判定するまでもない。重なりを判定する必要があるのは線分と曲線の組み合わせ、もしくは曲線と曲線の組み合わせである。
【００３９】
線分と曲線、曲線と曲線の重なりを判定する方法について詳細に述べる。曲線を十分な精度で近似する線分群に置き換えることで、線分と曲線、曲線と曲線の重なり判定はそれぞれ線分と線分群、線分群と線分群の重なり判定に置き換えることができ、それらの重なり判定は線分同士の重なり判定を繰り返すことで実現できる。２次元平面上の点（ｘ１，ｙ１）および（ｘ２，ｙ２）を結ぶ線分と、（ｘ３，ｙ３）および（ｘ４，ｙ４）を結ぶ線分が重なるかどうかは以下の（条件）を用いる。
【００４０】
（条件）
｛（ｘ１−ｘ２）×（ｙ３−ｙ１）＋（ｙ１−ｙ２）×（ｘ１−ｘ３）｝×｛（ｘ１−ｘ２）×（ｙ４−ｙ１）＋（ｙ１−ｙ２）×（ｘ１−ｘ４）｝＜０
かつ
｛（ｘ３−ｘ４）×（ｙ１−ｙ３）＋（ｙ３−ｙ４）×（ｘ３−ｘ１）｝×｛（ｘ３−ｘ４）×（ｙ２−ｙ３）＋（ｙ３−ｙ４）×（ｘ３−ｘ２）｝＜０
この条件が満たされると、２つの線分は重なっていると判定でき、この条件が満たされていない場合は、２つの線分は重なっていないと判定することができる。以上で述べた線分同士の重なり判定を行うことで、線分と曲線および曲線と曲線の重なりを判定することができる。
【００４１】
ステップＳ３０５における判定の結果、重なりがあると判定すれば、処理はステップＳ３０６に進む。一方、重なりがないと判定した場合には、処理はステップＳ３０２に戻る。
【００４２】
ステップＳ３０６では、各メッシュの状態を、最後に行ったステップＳ３０３およびステップＳ３０４の直前の状態に戻す。このように、メッシュ同士が重なるような統合を行ってしまった場合はその統合前の状態に戻すことで、常に重なりのないメッシュが作られることを保証する。ステップＳ３０６の後、再度ステップＳ３０３を実行する場合は、メッシュ同士の重なりを引き起こした統合は行わないようにしなければならない。
【００４３】
ステップＳ３０２では、ステップＳ３０７における処理を終えるか否かを判断する。終えると判断する基準には、例えばメッシュ数が初期メッシュの半分になった場合や、メッシュ数が入力画像に含まれる画素数の１／１００になった場合などが考えられる。また、ステップＳ３０５において一定回数（例えば１０回）以上連続で重なり有りと判定された場合などが考えられる。また、それらの条件の組み合わせても良い。
【００４４】
以上の処理により、入力画像を複数個のメッシュに分割する（入力画像上に複数個のメッシュを生成する）ことができる。
【００４５】
図１に戻って、色情報生成部１０４は、曲線メッシュ生成部１０３によって入力画像上に設定された各メッシュを塗るために必要な色情報を定める。色情報を生成する為には様々な方法が考えられる。その方法の１つとして考えられるのが、各メッシュを一色で塗る方法である。一色の定め方としては、メッシュの内部に含まれる画素の画素値の平均値を、このメッシュの色情報とする方法などがある。メッシュ内の色をより複雑に表現する方法としては、各メッシュに対して色を表現する関数を生成する方法が考えられる。例えば非特許文献１では、ＲＧＢの３成分に対して、メッシュ内の色を塗る薄板スプライン関数を入力画像の色を元に生成している。本実施形態では、各メッシュを更に微小な３頂点からなるメッシュ（サブメッシュ）に分割し、その微小なメッシュの頂点の画素の色を入力画像から取得し、該頂点に割り当てる（色割り当て）。レンダリングの際はそれら微小な三角形内の色を双線形補間で補うことで、各メッシュの色を塗ることができる。
【００４６】
符号化部１０５は、曲線メッシュ生成部１０３によって生成されたそれぞれのメッシュの形状情報、色情報生成部１０４が生成した各メッシュの色情報、を符号化し、入力画像に対する符号化データを生成する。
【００４７】
まず、各メッシュを構成するために必要な形状情報と色情報について説明する。図６（ａ）は、３頂点から成り且つ３頂点間が曲線で結ばれている（何れの辺も曲線で表現されている）メッシュ（曲線メッシュ）に係る形状情報を示す。６０１、６０２、６０３は曲線メッシュの頂点、６０４〜６０９は曲線メッシュの制御点である。
【００４８】
図６（ｂ）は、図６（ａ）に示した曲線メッシュに係る色情報を示す。６１０〜６２４は曲線メッシュ内におけるサブメッシュの頂点（サンプリング点）であり、それぞれのサンプリング点は色情報を有する。ここではサンプリング点はRGB値を色情報として有しているものとして説明するが、CMYKなど他の色空間における色情報を有するものとしても良い。また、入力画像がグレー画像である場合、サンプリング点は、対応する画素の輝度情報を色情報として保持することになる。サンプリング点は、ベジェパッチを規則的に分割することで導出される。ここではサンプリング点として１５点を用いているが、ベジェパッチの分割数を変更し、サンプリング点数を変更しても構わない。例えば、図８（ａ）では分割数が１であり、サンプリング数は３となる。また図８（ｂ）、（ｃ）、（ｄ）ではそれぞれ、分割数が２、３、４であり、サンプリング数は６、１０、１５点となる。
【００４９】
次に、符号化部１０５が、曲線メッシュ生成部１０３によって生成されたそれぞれのメッシュの形状情報、色情報生成部１０４が生成した各メッシュの色情報、を符号化することで生成する、符号化データの構成例について、図７を例に取り説明する。
【００５０】
図７（ａ）には、隣接する２つのメッシュ（曲線メッシュ）７２０，７２１を示しており、７０１、７０２、７０３、７０４は曲線メッシュの頂点、７０５〜７０９は曲線メッシュの辺、７１０〜７１９は曲線メッシュの制御点を示している。ここで、辺７０７は曲線メッシュ７２０の一辺であると共に、曲線メッシュ７２１の一辺でもあり、それぞれの曲線メッシュで共有されている辺（共有辺）である。
【００５１】
図７（ｂ）には、上記の曲線メッシュ７２０に対するサンプリング点７２２〜７３６、曲線メッシュ７２１に対するサンプリング点７３７〜７５１、を示している。然るに曲線メッシュ７２０に対する色情報は、サンプリング点７２２〜７３６のそれぞれにおける色情報から成り、メッシュ７２１に対する色情報は、サンプリング点７３７〜７５１のそれぞれにおける色情報から成る。ここで、上記の通り、辺７０７は曲線メッシュ７２０と曲線メッシュ７２１とで共有している。然るに、この辺７０７上にあるサンプリング点７２２とサンプリング点７４７とは同じ座標値であり、曲線メッシュ７２０と曲線メッシュ７２１とで座標を共有しているサンプリング点であることが分かる。これは、サンプリング点７２４及び７４８、サンプリング点７２７及び７４９、サンプリング点７３１及び７５０、サンプリング点７３６及び７５１、のそれぞれのセットについても同様である。
【００５２】
一方で、曲線メッシュのある一辺がエッジ線から生成された辺（エッジ線を再現可能なように生成された辺）であれば、この一辺上の各頂点は、この一辺を共有する一方の曲線メッシュの色と他方の曲線メッシュの色の２色を保持することになる。これは、エッジ線をまたぐ際に起こる急峻な色変化を表現している。
【００５３】
例えば、辺７０７がエッジ線上の辺である場合、メッシュ７２０側のサンプリング点７２２、７２４、７２７、７３１、７３６の色情報と、メッシュ７２１側のサンプリング点７４７、７４８、７４９、７５０、７５１の色情報を保持することになる。つまり、サンプリング点７２２とサンプリング点７４７は同一座標位置にあるものの、それぞれのサンプリング点は異なる色を保持する。また、サンプリング点７２４とサンプリング点７４８、サンプリング点７２７とサンプリング点７４９、サンプリング点７３１とサンプリング点７５０、サンプリング点７３６とサンプリング点７５１、のそれぞれのセットについても同様である。
【００５４】
一方、曲線メッシュのある一辺がエッジ線から生成された辺ではない場合、この一辺上の各頂点は、１色を保持することになる。例えば、辺７０７がエッジ線上以外のとき、サンプリング点７２２とサンプリング点７４７は同一座標にあり、かつ同じ色を保持する。サンプリング点７２４とサンプリング点７４８、サンプリング点７２７とサンプリング点７４９、サンプリング点７３１とサンプリング点７５０、サンプリング点７３６とサンプリング点７５１、のそれぞれのセットについても同様である。
【００５５】
本実施形態では、辺を共有する、辺上のサンプリング点を共有する、エッジ線上のサンプリング点は２種類の色を有する、という３頂点曲線メッシュの特徴を利用してメッシュ表現の効率化を図る。
【００５６】
そのために符号化部１０５は次のようにして符号化データを生成する。先ず、入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる（辺情報割り当て）。即ち、隣接する２つのメッシュ間で共有している辺も１つの辺と見なし、それぞれの辺に対して固有の情報を割り当てる。図７（ａ）の場合、辺７０５〜７０９のそれぞれに固有の情報を割り当てる。然るにメッシュ７２０と曲線メッシュ７２１とで共有する辺７０７にも１つの固有の情報が割り当てられる。この割り当ては符号化部１０５の動作前に行うようにしても良い。
【００５７】
このような情報割り当て処理で各辺に割り当てる「固有の情報」（固有情報）は、辺を一意に識別することができる情報であれば、如何なる情報であっても良い。例えば、辺を保持するメモリ上のアドレスであっても良いし、それぞれの辺に重複することなく割り当てた番号であっても良い。
【００５８】
そして符号化部１０５は、次の各種の情報が記述された符号化データを、メッシュ毎に生成する。即ち、１つのメッシュを構成するそれぞれの辺に割り当てた固有情報、該メッシュ中の各サブメッシュの頂点に割り当てた色を示す情報、が記述された符号化データを、該メッシュに対する符号化データとして生成する。そしてこのような符号化データを、メッシュ毎に生成する。
【００５９】
また、本実施形態では、固有情報を割り当てた辺毎に符号化データを生成するのであるが、１つの辺（着目辺）に対する符号化データには、次に列挙する情報が記述されている。
【００６０】
・ 着目辺に対して割り当てた固有情報
・ 着目辺の両端位置の座標
・ 着目辺が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値
・ 着目辺上の各頂点（サンプリング点）について割り当てた色を示す情報
・ メッシュ符号化処理の過程で着目辺に対して割り当てた着目辺の制御点の座標
然るにこのような情報が記された符号化データを、辺毎に生成する。そして符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、ヘッダ（辺の数、メッシュの数、メッシュの分割数、を含む）、をまとめて、入力画像に対する符号化データとし、出力する。
【００６１】
ここで、辺に対する符号化データを、辺７０７を例に取り説明する。辺７０７の符号化データを生成する際、「辺７０７に対して割り当てた固有情報」として、辺７０７を保持するメモリのアドレスや辺７０７に割り当てられた番号を記述する。
【００６２】
「辺７０７の両端位置の座標」として、辺７０７の両端の頂点７０１及び７０３のそれぞれのｘ座標値及びｙ座標値を記述する。「辺７０７が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値」として、辺７０７が入力画像中のエッジ線から生成されたものであるか否かに応じた値（例えば「生成されたものである」＝１、「生成されたものではない」＝０）を記述する。
【００６３】
「辺７０７上の各頂点（サンプリング点）について割り当てた色を示す情報」は、辺７０７が入力画像中のエッジ線から生成されたものであるか否かによって変わる。辺７０７が入力画像中のエッジ線から生成されたものである場合、サンプリング点７２２、７２４、７２７、７３１、７３６の色情報（メッシュ７２０用）、サンプリング点７４７、７４８、７４９、７５０、７５１の色情報（メッシュ７２１用）を記述する。
【００６４】
このとき、辺の両端の座標の記述順を辺の方向とし、辺の右側、左側の順番で、色情報を記述する。辺７０７の場合、頂点７０１の座標値、頂点７０３の座標値、の順に記述した場合、頂点７０１から頂点７０３に向かって辺の右側とし、サンプリング点７２２、７２４、７２７、７３１、７３６の色情報を記述する。次に左側として、サンプリング点７４７、７４８、７４９、７５０、７５１の色情報を記述する。もちろん辺に対して左右の判定さえできれば、他の記述方法を用いても構わない。
【００６５】
一方、辺７０７が入力画像中のエッジ線から生成されたものではない場合、サンプリング点７２２、７２４、７２７、７３１、７３６の色情報のみを記述する。ここで、本実施形態では色情報はＲＧＢ値を表すものとして説明しているため、ＲＧＢ置さえ導出できれば、サンプリング点間のＲＧＢ値の差分を用いるなど、他の表現を用いても構わない。
【００６６】
また、「メッシュ符号化処理の過程で辺７０７に対して割り当てた辺７０７の制御点の座標」としては、制御点７１５及び制御点７１４のそれぞれのｘ座標値及びｙ座標値を記述する。ここで、頂点の座標値については、ｘ座標値及びｙ座標値さえ導出することができるのであれば、如何なる情報を採用しても良い。例えば、頂点間の差分を保持するなど他の表現を用いても構わない。同様に制御点の座標値についても、ｘ座標値及びｙ座標値を導出することができるのであれば、如何なる情報を用いても良い。例えば、頂点との座標値の差分や制御点間の座標値の差分を保持するなど他の表現を用いても構わない。
【００６７】
また、制御点の座標値の記述順は、例えば、頂点７０１、７０３の順に座標値が記述されている場合、頂点７０１に対応する制御点７１５、頂点７０３に対応する制御点７１４の順に記述する。
【００６８】
次に、メッシュに対する符号化データを、メッシュ７２０を例に取り説明する。「メッシュ７２０を構成するそれぞれの辺に割り当てた固有情報」としては、辺７０５、７０７、７０６のそれぞれの辺の番号やアドレスを記述する。
【００６９】
このとき記述する最初の２辺、辺７０５と辺７０７が共有している頂点７０１を基準点とする。基準点となる頂点７０１から規則的にベジェパッチを分割することで、順番にサンプリング点が導出される。例えば、メッシュ７２０では、サンプリング点７２２〜７３６まで順番に導出される。然るに「メッシュ７２０中の各サブメッシュの頂点に割り当てた色を示す情報」としては、サンプリング点７２２〜７３６の色情報を、導出順（サンプリング点７２６、７２９、７３０、…の順）に記述する。
【００７０】
なお、符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、ヘッダ（辺の数、メッシュの数、メッシュの分割数、を含む）、をｚｉｐ符号化して管理しているが、非可逆符号化を含めた他の符号化方式を用いて管理しても良い。
【００７１】
従来では、メッシュ単位に符号化した場合には、辺上のサンプリング点の座標及び色を２回符号化しなければならなかったのに対し、本実施形態では１回で符号化でき、符号化効率の向上が図れる。
【００７２】
上記の処理をまとめると、次のようなものとなる。先ず、メッシュ符号化処理の過程で入力画像をメッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、入力画像中の該頂点の位置における色を割り当てる（色割り当て）。
【００７３】
次に、入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる（情報割り当て）。
【００７４】
次に、分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に割り当てた色を示す情報と、を記述したメッシュデータを生成する。
【００７５】
次に、情報を割り当てた辺毎に、以下の情報を記述した辺データを生成する。即ち、該辺に割り当てた情報、該辺の両端位置の座標、該辺が入力画像中のエッジ線から生成されたものか否かを示すフラグ値、該辺上の各頂点に割り当てた色を示す情報、メッシュ符号化処理の過程で該辺に割り当てられた該辺の制御点の座標、である。
【００７６】
そして最後に、分割したメッシュ毎に生成したメッシュデータ及び情報を割り当てた辺毎に生成した辺データ、を含むデータを、入力画像の符号化データとして生成する。
【００７７】
次に、符号化部１０５によって出力された、入力画像のメッシュ符号化結果を復号する画像処理装置について説明する。先ず、この復号処理を行う画像処理装置について、機能構成例を示す図１０のブロック図を用いて説明する。なお、図１０の構成を有する画像処理装置は、図１の構成を有する画像処理装置と別個の装置であっても良いし、同じ装置であっても良い。後者の場合、この画像処理装置は、図１に示した構成と図１０に示した構成とを有する装置であり、以下に説明する復号処理は、自身が符号化して生成した符号化データを一旦メモリに保持しておき、その後、この符号化データを復号することになる。
【００７８】
符号化データ入力部１００１は、符号化部１０５によって生成された入力画像の符号化結果である入力画像符号化データを取得し、取得した入力画像符号化データを後段の形状情報復元部１００２に送出する。
【００７９】
形状情報復元部１００２は、入力画像符号化データから３頂点曲線メッシュの形状情報を復元する。先ず形状情報復元部１００２は入力画像符号化データを取得すると、これを画像処理装置内の不図示のメモリに一旦格納する。そしてメッシュ毎の符号化データを参照する。着目メッシュの符号化データを参照すると、この符号化データ中に記述されている「着目メッシュを構成するそれぞれの辺に割り当てた固有情報」を参照する。そして「着目メッシュを構成するそれぞれの辺に割り当てた固有情報」で特定される辺の符号化データを入力画像符号化データから読み出す。そして読み出した辺の符号化データから基準点を復元し、復元した基準点から着目メッシュを復元する。
【００８０】
ここまでの処理を図７のメッシュ７２０を例に取り説明すると、メッシュ７２０の符号化データ中の「メッシュ７２０を構成するそれぞれの辺に割り当てた固有情報」を参照する。ここでは辺７０５、辺７０７、辺７０６の順に記述されている固有情報を参照する。そして記述順において最初の２辺である辺７０５と辺７０７のそれぞれの両端の座標位置を参照すると、辺７０５の何れか一端の座標位置と辺７０７の何れか一端の座標位置とは同じである。然るにこの同じ座標位置に対する頂点である頂点７０１を基準点とする。そして、基準点となる頂点７０１から反時計周りに辺を接続していく。まず辺７０５と辺７０７の位置関係（それぞれの両端の座標値から導出可能）から、辺７０５を選択する。そして、辺７０５の符号化データから頂点７０１、制御点７１０、頂点７０２、制御点７１１の座標位置を読み出すことで、これらを復元する。次に辺７０６の符号化データから制御点７１２、頂点７０３、制御点７１３の座標位置を読み出すことで、これらを復元する。最後に、辺７０７の符号化データから制御点７１４、制御点７１５の座標位置を読み出すことで、これらを復元する。
【００８１】
これらの復元処理により、メッシュ７２０の形状を一意に特定するために必要な情報（即ち形状情報）は復元されるので、結果としてメッシュ７２０の形状が復元されることになる。このような処理を、メッシュ毎に行うことで、それぞれの３頂点曲線メッシュの形状が復元される。
【００８２】
色情報復元部１００３は、形状情報復元部１００２で復元された３頂点曲線メッシュの形状情報を利用して、メッシュの色情報を復元する。この処理を図７を例に取り説明すると、基準点となる頂点７０１から、規則的にベジェパッチを分割することで、順番にサンプリング点が導出される。メッシュ７２０では、サンプリング点７２２〜７３６が導出される。
【００８３】
次にそれぞれのサンプリング点に色を割り当てる。まずメッシュ７２０の辺上のサンプリング点に色を割り当てる。基準点となる頂点７０１から反時計周りに色を復元する。先ず辺７０５の符号化データ中で色が並んでいる順番を確認する。例えば辺７０５の符号化データ中に辺７０５の両端の座標位置が頂点７０１、７０２の順に並んでいるとする。この場合、辺７０５の符号化データ中の「辺７０５上の各頂点（サンプリング点）について割り当てた色を示す情報」を、サンプリング点７２２、７２３、７２５、７２８、７３２の順に割り当てる。逆に頂点７０２、７０１の順に並んでいれば、辺７０５の符号化データ中の「辺７０５上の各頂点（サンプリング点）について割り当てた色を示す情報」を、サンプリング点７３２、７２８、７２５、７２３、７２２の順に割り当てる。次に、辺７０６の符号化データ中の「辺７０６上の各頂点（サンプリング点）について割り当てた色を示す情報」を、同様の処理によりサンプリング点７３３、７３４、７３５、７３６の順に割り当てる。最後に、辺７０７についても同様にしてサンプリング点７３１、７２７、７２４の順に色を割り当てる。
【００８４】
なお、この色割り当て処理は、辺７０７がエッジ線上の辺ではない場合の処理である。辺７０７がエッジ線上の辺である場合、辺７０７の左右どちらの色をメッシュ７２０に対して利用するか判断しなくてはならない。この判断は、色を復元している反時計周りの方向が、辺の両端（頂点）が記述されている順番と逆のとき、右側の色を使う。またその反対では、左側の色を使う。図７を例に取り説明すると、色を復元している反時計周りの方向は、頂点７０３から頂点７０１に向かう方向である。辺７０５の符号化データ中に座標値が頂点７０１、頂点７０３の順に並んでいるとき、メッシュ７２０の色として右側の色を使う。また、頂点７０３、頂点７０１の順に並んでいるとき、メッシュ７２０の色として左側の色を使う。以上の処理によりメッシュの辺上の色が復元される。
【００８５】
なお、辺７０７がエッジ線上の辺であるか否かは、辺７０７の符号化データ中の「辺７０７が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値」を参照すればよい。
【００８６】
残ったメッシュ７２０内のサンプリング点における色は、メッシュ７２０の符号化データ中に記述されている「メッシュ７２０中の各サブメッシュの頂点に割り当てた色」を用いても良いが、辺上の各頂点の色から補間により色を求めても良い。もちろん、辺上にはないサンプリング点の色を決める方法についてはこれに限るものではない。
【００８７】
ここまでの処理でメッシュの形状情報及び色情報が復元されたので、後はこれらの情報を用いれば入力画像が復元できる。然るに画像出力部１００４は、メッシュの形状情報及び色情報を用いて入力画像を復元し、復元した入力画像を出力画像として出力する。出力先については特に限定するものではなく、適当なメモリに格納しても良いし、表示装置に出力して表示させても良いし、ネットワークを介して外部の装置に対して送信しても良い。
【００８８】
＜第１の実施形態の変形例＞
図１，１０に示した各部はハードウェアで構成しても良いが、ソフトウェア（コンピュータプログラム）として実装しても良い。この場合、このソフトウェアは、ＰＣ（パーソナルコンピュータ）等、一般のコンピュータのメモリにインストールされることになる。そしてこのコンピュータのＣＰＵがこのインストールされたソフトウェアを実行することで、このコンピュータは、上述の画像処理装置の機能（図１，１０に示した各部の機能）を実現することになる。即ち、このコンピュータは、上述の画像処理装置に適用することができる。第１の実施形態に係る画像処理装置に適用可能なコンピュータのハードウェア構成例について、図９のブロック図を用いて説明する。
【００８９】
ＣＰＵ９０１は、ＲＡＭ９０２やＲＯＭ９０３に格納されているコンピュータプログラムやデータを用いて、コンピュータ全体の制御を行うと共に、画像処理装置が行うものとして説明した上述の各処理を実行する。即ち、図１，１０に示した各部が行うものとして上述した各処理を実行する。
【００９０】
ＲＡＭ９０２は、コンピュータ読み取り可能な記憶媒体の一例である。ＲＡＭ９０２は、外部記憶装置９０７や記憶媒体ドライブ９０８からロードされたコンピュータプログラムやデータ、Ｉ／Ｆ（インターフェース）９０９を介して外部装置から受信したデータなどを一時的に記憶するためのエリアを有する。更に、ＲＡＭ９０２は、ＣＰＵ９０１が各種の処理を実行する際に用いるワークエリアを有する。即ち、ＲＡＭ９０２は、各種のエリアを適宜提供することができる。ＲＯＭ９０３は、コンピュータ読み取り可能な記憶媒体の一例であり、コンピュータの設定データや、ブートプログラムなどが格納されている。
【００９１】
キーボード９０４、マウス９０５は、コンピュータの操作者が操作することで、各種の指示をＣＰＵ９０１に対して入力することができる。表示装置９０６は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ９０１による処理結果を画像や文字などでもって表示することができる。例えば、上記入力画像を表示したり、暫定的に設定したメッシュ、最終的に決定したメッシュ、復元画像等を表示したりすることができる。
【００９２】
外部記憶装置９０７は、コンピュータ読み取り可能な記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置９０７には、ＯＳ（オペレーティングシステム）や、図１，１０に示した各部の機能をＣＰＵ９０１に実現させるためのコンピュータプログラムやデータ、上記入力画像のデータ、既知の情報として説明した情報等が保存されている。外部記憶装置９０７に保存されているコンピュータプログラムやデータは、ＣＰＵ９０１による制御に従って適宜ＲＡＭ９０２にロードされ、ＣＰＵ９０１による処理対象となる。
【００９３】
記憶媒体ドライブ９０８は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置９０７やＲＡＭ９０２に出力する。なお、外部記憶装置９０７に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ９０８に読み取らせても良い。
【００９４】
Ｉ／Ｆ９０９は、外部装置をコンピュータに接続する為のものである。例えば、ディジタルカメラなど、上記入力画像を取得するための装置を、このＩ／Ｆ９０９に接続し、この外部装置から入力画像をＩ／Ｆ９０９を介してＲＡＭ９０２や外部記憶装置９０７に取得するようにしても良い。９１０は、上述の各部を繋ぐバスである。
【００９５】
上述構成において、本コンピュータの電源がＯＮになると、ＣＰＵ９０１はＲＯＭ９０３に格納されている上記ブートプログラムに従って、外部記憶装置９０７からＯＳをＲＡＭ９０２にロードする。この結果、キーボード９０４、マウス９０５を介した情報入力操作が可能となり、表示装置９０６にＧＵＩを表示することが可能となる。ユーザが、キーボード９０４やマウス９０５を操作し、外部記憶装置９０７に格納された画像処理用アプリケーションプログラムの起動指示を入力すると、ＣＰＵ９０１はこのプログラムをＲＡＭ９０２にロードし、実行する。これにより、本コンピュータが上記の画像処理装置として機能することになる。
【００９６】
ＣＰＵ９０１が実行する画像処理用のアプリケーションプログラムは、基本的に図１，１０に示す各構成要素に相当する関数を備えることになる。ここで、符号化データは外部記憶装置９０７に保存することになる。なお、このコンピュータは、以降の各実施形態に係る画像処理装置にも同様に適用可能であることは、以下の説明より明らかである。
【００９７】
［第２の実施形態］
第１の実施形態では、辺を共有する、辺上のサンプリング点を共有する、エッジ線上のサンプリング点は２種類の色を有する、という３頂点曲線メッシュの特徴を利用してメッシュ表現の効率化を図った。具体的には、辺情報とメッシュ情報を用いてデータの冗長性を削減している。本実施形態では頂点に係る情報を別個に管理し、辺情報として扱っていた頂点情報の冗長性を削減する。
【００９８】
本実施形態において入力画像を符号化する装置の構成は、図１に示した構成と同様であるが、符号化部１０５の動作のみが第１の実施形態と異なる。然るに以下では、本実施形態に係る符号化部１０５の動作について説明する。なお、メッシュ毎の符号化データの生成は第１の実施形態と同様にして行う。
【００９９】
符号化部１０５は、メッシュを生成するために入力画像上に設定された（実際にメッシュの頂点として使用されている）各頂点に対して、頂点毎に固有の情報を割り当てる（頂点情報割り当て）。この固有情報についても、それぞれの頂点を一意に識別することができる情報であれば、如何なる情報であっても良い。そして符号化部１０５は、メッシュを生成するために入力画像上に設定された（実際にメッシュの頂点として使用されている）頂点毎に、以下の情報が記述された頂点データを生成する。
【０１００】
・ 頂点の固有情報
・ 頂点の座標位置
また、符号化部１０５は、固有情報を割り当てた辺毎に符号化データを生成するのであるが、１つの辺（着目辺）に対する符号化データには、次に列挙する情報が記述されている。
【０１０１】
・ 着目辺に対して割り当てた固有情報
・ 着目辺の両端位置における頂点の固有情報
・ 着目辺が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値
・ 着目辺上の各頂点（サンプリング点）について割り当てた色を示す情報
・ メッシュ符号化処理の過程で着目辺に対して割り当てた着目辺の制御点の座標
このような情報が記された符号化データを、辺毎に生成する。そして符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、頂点毎に生成した頂点データ、ヘッダ（頂点の数、辺の数、メッシュの数、メッシュの分割数、を含む）、をまとめて、入力画像に対する符号化データとし、出力する。
【０１０２】
頂点データの記述を、図７を例に説明する。図７の場合、頂点データには、頂点７０１、７０２、７０３、７０４のそれぞれのｘ座標及びｘ座標と、頂点７０１、７０２、７０３、７０４のそれぞれの固有情報と、を記述する。頂点の座標位置は、ｘ座標、ｘ座標さえ導出できれば、頂点間の差分を保持するなど他の表現を用いても構わない。また、頂点に固有の情報には、頂点固有のアドレスが割り当てられてさえいれば、他の表現方法でも構わない。
【０１０３】
符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、頂点毎に生成した頂点データ、ヘッダ（頂点の数、辺の数、メッシュの数、メッシュの分割数、を含む）、をｚｉｐ符号化して管理している。しかし、非可逆符号化を含めた他の符号化方式を用いて管理しても良い。
【０１０４】
第１の実施形態では、頂点に接続されている辺の数の分だけ頂点座標を符号化しなければならなかったが、本実施形態の表現では、１回の符号化で表現でき符号化効率の向上が図れる。
【０１０５】
次に、本実施形態に係る符号化により生成された入力画像符号化データを復号する装置について説明する。この復号する装置は第１の実施形態と同様、図１０に示した構成を有するが、以下に説明する点のみが異なる。
【０１０６】
図７のメッシュ７２０を例に取り説明すると、形状情報復元部１００２は、メッシュ７２０の符号化データ中の「メッシュ７２０を構成するそれぞれの辺に割り当てた固有情報」を参照する。ここでは辺７０５、辺７０７、辺７０６の順に記述されている固有情報を参照する。そして記述順において最初の２辺である辺７０５と辺７０７のそれぞれの両端の頂点の固有情報に対応する座標位置を座標情報から取得して参照して、頂点７０１を基準点とする。そして、辺７０５と辺７０７の位置関係（それぞれの両端の座標値から導出可能）から、辺７０５を選択する。
【０１０７】
そして、辺７０５の符号化データ中の頂点７０１，７０２の固有情報から、頂点７０１，７０２の頂点データを特定し、特定した頂点データ、及び辺７０５の符号化データから頂点７０１、制御点７１０、頂点７０２、制御点７１１の座標位置を読み出す。これにより、これらを復元する。
【０１０８】
次に辺７０６の符号化データ中の頂点７０３の固有情報から、頂点７０３の頂点データを特定し、特定した頂点データ、及び辺７０６の符号化データから制御点７１２、頂点７０３、制御点７１３の座標位置を読み出す。これにより、これらを復元する。最後に、辺７０７の符号化データから制御点７１４、制御点７１５の座標位置を読み出すことで、これらを復元する。
【０１０９】
このような処理を、メッシュ毎に行うことで、３頂点曲線メッシュの形状が復元される。メッシュの色情報を復元する方法については第１の実施形態と同様にして行う。
【０１１０】
［第３の実施形態］
第１，２の実施形態では、メッシュの辺が曲線である３頂点曲線メッシュの表現を説明したが、本実施形態では、メッシュの辺が直線と曲線が混在している場合の３頂点曲線メッシュの表現について説明する。
【０１１１】
入力画像符号化データを生成する画像処理装置の構成は第１の実施形態と同様、図１に示した構成を有するが、符号化部１０５の動作のみが第１の実施形態と異なる。然るに以下では符号化部１０５の動作について重点的に説明する。
【０１１２】
本実施形態で取り扱う３頂点曲線メッシュの形状情報、色情報について図１１を用いて説明する。メッシュ１１１８を構成する頂点は頂点１１０１，１１０２，１１０３であり、頂点１１０１と頂点１１０２との間は曲線の辺、頂点１１０２と頂点１１０３との間は曲線の辺、頂点１１０１と頂点１１０３との間は直線の辺である。ここで、曲線の辺は制御点を伴って生成されるものであるが、直線の辺に関してはその両端さえ分かれば生成可能であるため、制御点は不要となる。
【０１１３】
本実施形態では第２の実施形態と同様に、頂点毎の頂点データ、メッシュ毎の符号化データ、辺毎の符号化データ、を生成するのであるが、辺毎の符号化データの構成のみが異なる。１つの辺（着目辺）に対する符号化データには、次に列挙する情報が記述されている。
【０１１４】
・ 着目辺に対して割り当てた固有情報
・ 着目辺の両端位置における頂点の固有情報
・ 着目辺が曲線であるか直線であるかを示すフラグ値
・ 着目辺が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値
・ 着目辺上の各頂点（サンプリング点）について割り当てた色を示す情報
・ メッシュ符号化処理の過程で着目辺に対して割り当てた着目辺の制御点の座標（着目辺が曲線である場合のみ）
このような情報が記された符号化データを、辺毎に生成する。例えば、図１１を例に取ると、辺１１０７は直線であるため、辺１１０７に対する符号化データには、次に列挙する情報が記述されている。
【０１１５】
・ 辺１１０７に対して割り当てた固有情報
・ 辺１１０７の両端位置における頂点１１０１，１１０３の固有情報
・ 辺１１０７が曲線であるか直線であるかを示すフラグ値（＝直線を示すフラグ値）
・ 辺１１０７が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値
・ 辺１１０７上の各頂点（サンプリング点）１１２０，１１２２，１１２５，１１２９，１１３４（辺１１０７が入力画像中のエッジ線から生成されたものである場合はこれに加えて頂点１１４５〜１１４９）について割り当てた色を示す情報
・ メッシュ符号化処理の過程で辺１１０７に対して割り当てた辺１１０７の制御点の座標としてＮＵＬＬ
そして符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、頂点毎に生成した頂点データ、ヘッダ（頂点の数、辺の数、メッシュの数、メッシュの分割数、を含む）をまとめて、入力画像に対する符号化データとし、出力する。
【０１１６】
符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、頂点毎に生成した頂点データ、ヘッダ（頂点の数、辺の数、メッシュの数、メッシュの分割数、を含む）、をｚｉｐ符号化して管理している。しかし、非可逆符号化を含めた他の符号化方式を用いて管理しても良い。
【０１１７】
次に、本実施形態に係る符号化により生成された入力画像符号化データを復号する装置について説明する。この復号する装置は第１の実施形態と同様、図１０に示した構成を有するが、以下に説明する点のみが異なる。
【０１１８】
図７のメッシュ７２０を例に取り説明すると、形状情報復元部１００２は、メッシュ７２０の符号化データ中の「メッシュ７２０を構成するそれぞれの辺に割り当てた固有情報」を参照する。ここでは辺７０５、辺７０７、辺７０６の順に記述されている固有情報を参照する。そして記述順において最初の２辺である辺７０５と辺７０７のそれぞれの両端の頂点の固有情報に対応する座標位置を座標情報から取得して参照して、頂点７０１を基準点とする。そして、辺７０５と辺７０７の位置関係（それぞれの両端の座標値から導出可能）から、辺７０５を選択する。
【０１１９】
そして、辺７０５の符号化データ中の「曲線か直線かを示すフラグ値」を参照する。図７の場合、このフラグ値は「曲線」を示すので、辺７０５の符号化データ中の頂点７０１，７０２の固有情報から、頂点７０１，７０２の頂点データを特定する。そして、特定した頂点データと辺７０５の符号化データから、頂点７０１、制御点７１０、頂点７０２、制御点７１１の座標位置を読み出すことで、これらを復元する。
【０１２０】
次に辺７０６の符号化データ中の「曲線か直線かを示すフラグ値」を参照する。図７の場合、このフラグ値は「曲線」を示すので、辺７０６の符号化データ中の頂点７０３の固有情報から、頂点７０３の頂点データを特定する。そして、特定した頂点データと辺７０６の符号化データから、頂点７０３、制御点７１２、制御点７１３の座標位置を読み出すことで、これらを復元する。
【０１２１】
最後に、辺７０７の符号化データ中の「曲線か直線かを示すフラグ値」を参照する。図７の場合、このフラグ値は「曲線」を示すので、辺７０７の符号化データから制御点７１４、制御点７１５を読み出すことで、これらを復元する。
【０１２２】
このような処理を、メッシュ毎に行うことで、３頂点曲線メッシュの形状が復元される。メッシュの色情報を復元する方法については第１の実施形態と同様にして行う。なお、第１〜３の実施形態は適宜組み合わせて使用することも可能であり、その組み合わせ方法については当業者であれば適宜考え得ることである。
【０１２３】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
本発明は、画像をベクトル表現する画像処理技術に関する。特にラスタ画像を、メッシュで表現するベクトル表現技術に関するものである。
【背景技術】
【０００２】
従来から、画像をベクトル表現する技術は広く知られている。ベクトル表現された画像は、画像の拡大縮小時に画質劣化が少ない、画像の編集がし易い、高い圧縮率が実現できるなどの利点がある。
【０００３】
イラストや文字をベクトル表現する場合には、オブジェクトの輪郭をベジェ、スプライン関数などで近似する手法が用いられている。オブジェクトの領域内は、単一色、線形グラデーション、放射状グラデーションなどで塗ることができるが、複雑なグラデーションの表現は困難である。
【０００４】
複雑なグラデーションを含むオブジェクトをベクトル表現する場合には、Ａｄｏｂｅ Ｉｌｌｕｓｔｒａｔｏｒ（登録商標）のグラディエント・メッシュ・ツールが一般に用いられている。グラディエント・メッシュでは、メッシュに色と勾配を与えて３次関数を生成することで複雑なグラデーションを含むオブジェクトを描画できる（特許文献１）。
【０００５】
グラディエント・メッシュは４頂点から成る曲線メッシュであるが、３頂点から成る曲線メッシュにより、複雑なグラデーションをベクトル表現する技術が知られている（非特許文献１）。画像内のエッジを線分群として抽出し（以下エッジ線と呼ぶ）、エッジ線を再現する３頂点曲線メッシュを構成することでベクトル表現を行う。ここで、３頂点曲線メッシュとは、メッシュの頂点数が３であり、頂点間を結ぶメッシュの辺が直線または曲線であるものとする。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特登録０４２２００１０
【非特許文献】
【０００７】
【非特許文献１】Ｔｉａｎ Ｘｉａ， Ｂｉｎｂｉｎ Ｌｉａｏ， ａｎｄ Ｙｉｚｈｏｕ Ｙｕ， 「Ｐａｔｃｈ−Ｂａｓｅｄ Ｉｍａｇｅ Ｖｅｃｔｏｒｉｚａｔｉｏｎ ｗｉｔｈ Ａｕｔｏｍａｔｉｃ Ｃｕｒｖｉｌｉｎｅａｒ Ｆｅａｔｕｒｅ Ａｌｉｇｎｍｅｎｔ」， ＡＣＭ ＳＩＧＧＲＡＰＨ Ａｓｉａ ２００９， Ｖｏｌ．２８， Ｎｏ．５．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
自然画像のような色が複雑に変化するオブジェクトを曲線メッシュによりベクトル表現することを考える。直線メッシュに対して曲線メッシュは、オブジェクトの形状や特徴を曲線で近似するため、より少ないメッシュ数でオブジェクトを近似できる。
【０００９】
上述のグラディエント・メッシュを用いてオブジェクトを近似するとき、４頂点から成る曲線メッシュを規則格子状に構築する手法が知られている。この手法ではメッシュの接続関係を保持する必要がないため、データ表現として効率が良いが、メッシュ制御が局所的にできないため、複雑形状を近似するときにメッシュ数が増え、データ量が増大してしまう。
【００１０】
上述の３頂点曲線メッシュでは、メッシュ制御が局所的にできるため、少ないメッシュ数でオブジェクトを近似できる。従来、３頂点曲線メッシュはメッシュ単位に符号化され、メッシュ間で共有される頂点、辺、色を考慮していないため、符号化効率が低くデータ量が増大してしまう。
【００１１】
本発明は以上の問題に鑑みて成されたものであり、３頂点曲線メッシュを効率的に符号化するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の目的を達成するために、例えば、本発明の画像処理装置は、入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置であって、前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て手段と、前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる情報割り当て手段と、分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記情報割り当て手段が割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て手段が割り当てた色を示す情報と、を記述したメッシュデータを生成し、前記情報割り当て手段が情報を割り当てた辺毎に、該辺に対して前記情報割り当て手段が割り当てた情報と、該辺の両端位置の座標と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て手段が割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、分割したメッシュ毎に生成したメッシュデータ及び前記情報割り当て手段が情報を割り当てた辺毎に生成した辺データ、を含むデータを、前記入力画像の符号化データとして生成する生成手段とを備えることを特徴とする。
【発明の効果】
【００１３】
本発明の構成によれば、３頂点曲線メッシュの符号化を効率的に行うことができる。
【図面の簡単な説明】
【００１４】
【図１】画像処理装置の機能構成例を示すブロック図。
【図２】エッジ線として望ましくない結果を説明する図。
【図３】曲線メッシュ生成部１０３が行う処理のフローチャート。
【図４】メッシュ同士の重なりについて説明する図。
【図５】メッシュ生成方法を説明する図。
【図６】形状情報を説明する図。
【図７】符号化部１０５が生成する符号化データの構成例を示す図。
【図８】ベジエパッチの分割例を示す図。
【図９】コンピュータのハードウェア構成例を示すブロック図。
【図１０】復号する装置の機能構成例を示すブロック図。
【図１１】第３の実施形態で取り扱う３頂点曲線メッシュの形状情報、色情報を説明する図。
【発明を実施するための形態】
【００１５】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載した構成の具体的な実施例の一つである。
【００１６】
［第１の実施形態］
本実施形態に係る説明に先立って、先ず、曲線メッシュについて説明する。本実施形態では、曲線メッシュを構成する３つの頂点間を結ぶ曲線はベジェ曲線、Ｂ−スプライン等の如何なる曲線であっても良い。本実施形態では説明上、各曲線メッシュにパラメトリック曲面の１つである３頂点のベジェパッチを用いる。ベジェパッチの中でも特に３次のベジェパッチでは、曲線メッシュの各辺は３次のベジェ曲線となるため、曲線メッシュを生成したのちに、ユーザによる編集が容易であるというメリットがある。Ｐ１、Ｐ２、Ｐ３を頂点とする３次のベジェパッチ内の点は以下の式で表される。
【００１７】
【数１】
【００１８】
ここで、ｓ、ｔ、ｕはパッチ内の重心座標である。また、ｐ１，ｐ２，ｐ３はそれぞれ、頂点Ｐ１，Ｐ２，Ｐ３の座標値である。また、ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ６、ｃ７は、曲線パッチの形状を定めるパラメータである。
【００１９】
次に、入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュ（曲線メッシュ）を単位に符号化するメッシュ符号化処理を実行する画像処理装置の機能構成例について、図１のブロック図を用いて説明する。
【００２０】
画像入力部１０１には、ラスタ表現の入力画像が入力される。この入力画像はカラー画像、グレー画像、白黒画像のいずれでも構わない。また、入力画像は矩形画像でも構わないし、画像の一部をベクトル化したい場合には背景部を透過色に設定した画像等、切り出された領域が与えられても良い。そして画像入力部１０１は、この入力された入力画像を後段の特徴線構成部１０２に送出する。
【００２１】
特徴線構成部１０２は、画像入力部１０１から受け取った入力画像中に特徴線を構成する。本実施形態ではこの特徴線には、エッジ線を用いる。この場合、特徴線構成部１０２は、入力画像からエッジを構成する画素（エッジ画素）を抽出するエッジ抽出部と、エッジ抽出部が抽出したエッジ画素を連結させてエッジ線を構成するエッジ構成部と、を有することになる。
【００２２】
エッジ抽出部は、入力画像からキャニー法という既知の方法を用いてエッジ画素を抽出する。もちろん、他の方法を用いてエッジ画素を抽出しても良い。次にエッジ構成部は、抽出されたエッジ画素のうち、隣接するもの同士を結ぶ線分を構成することで、エッジを再現する線分群（エッジ線）を構成する。隣接するエッジ画素間を結んで線分群を構成する際に、注目エッジ画素の上、下、左、右にある４つの画素が隣接しているとみなす４連結接続がある。また、この４方向に加えて右上、右下、左上、左下にある４つの画素も隣接していると見なす８連結接続もある。本実施形態では８連結接続を用いる。
【００２３】
しかし、エッジ抽出部がキャニー法を用いて抽出したエッジ画素に対して、８連結接続で隣接しているとみなせる画素を結ぶと、エッジ線として望ましくない結果が得られる場合がある。このケースについて、図２を用いて説明する。
【００２４】
図２（ａ）〜（ｃ）には画像中のある領域を構成する画素群を示しており、１つの四角形が１つの画素を表している。また、斜線で示している四角形がエッジ抽出部が抽出したエッジ画素を表しており、斜線がない四角形がエッジ画素以外の画素（非エッジ画素）を表している。
【００２５】
図２（ａ）に示したエッジ画素群について、８連結接続で隣接したエッジ画素を結ぶと、図２（ｂ）に示すように、エッジ画素２０１、２０２、２０３を結ぶようなループが発生してしまう。図２（ａ）に示すようなエッジ画素が検出された場合、このようなループの発生を抑制する必要がある。そこで本実施形態では、８連結接続を行う前に、Ｈｉｌｄｉｔｃｈ細線化法という既知の手法を用いることで、この問題を解決する。図２（ａ）に示したエッジ画素群に対してＨｉｌｄｉｔｃｈ細線化を行うと、図２（ｂ）に示したエッジ画素２０１は非エッジ画素となる。その結果、図２（ｃ）に示すように、エッジ画素（２０４〜２０７）がループのない１つのエッジ線によって結ばれることになる。
【００２６】
なお、特徴線にはエッジ線以外にも、例えば入力画像中のオブジェクトの領域の輪郭などが考えられる。ここでオブジェクトとは、文字や物体像等を指している。
【００２７】
既に述べたように、入力画像の一部をベクトル化するという目的で、入力画像の一部が透過色に設定されている場合は、透過色と非透過色の境界に有る画素がオブジェクトの輪郭画素となる。オブジェクトの輪郭画素を１つの線分群にまとめる処理は、エッジ構成部が行う処理と同様の処理に従って隣接する画素同士をつなぎ合わせることで実現できる。これは、入力画像内の異なる属性の領域の間の境界線にある画素についても同様である。
【００２８】
また、特徴線構成部１０２は、入力画像を領域分割し、その境界線を特徴線としても良い。領域分割は最近傍法を用いたもの、ＥＭアルゴリズムを利用したものなど、多くの手法が知られている。
【００２９】
図１に戻って、曲線メッシュ生成部１０３は、特徴線が再現可能で且つメッシュ同士の重なりが無いように、入力画像をメッシュ群に分割する。曲線メッシュ生成部１０３が行う処理について、同処理のフローチャートを示す図３を用いて説明する。もちろん、図３のフローチャートに示した各ステップにおける処理の主体は何れも曲線メッシュ生成部１０３である。
【００３０】
先ずステップＳ３０１では、入力画像に対して初期メッシュ群を生成する。この初期メッシュは、エッジ線を再現するようなメッシュとして生成される。さらに、初期メッシュは、エッジ線を再現するメッシュの辺を、エッジ線に沿うように曲線化してもメッシュ同士が重ならないように生成する。
【００３１】
非特許文献１では、エッジ線を忠実に再現する十分に短い線分群をメッシュの辺とし、かつ、ラスタ画像の全画素を頂点とする直線メッシュを生成する。この生成方法について、図５（ａ）を用いて説明する。図５（ａ）において実線はエッジ線を示しており、点線はその他のメッシュの辺、黒い丸はラスタ画像中の画素を示している。エッジ線５０１、５０２、５０３、５０４は何れも、メッシュの辺として用いられている。
【００３２】
また他の例では、特徴線を忠実に再現する直線メッシュ、つまり特徴線を構成する全ての線分がメッシュの辺となる直線メッシュを生成する。このように生成した直線メッシュは、特徴線に沿った辺を曲線化するまでもなく特徴線を忠実に再現している為、曲線化に伴ってメッュ同士が重なるという問題は起きない。このケースについて図５（ｂ）を用いて説明する。
【００３３】
図５（ａ）と同様、実線はエッジ線を示しており、点線はその他のメッシュの辺、黒い丸はラスタ画像中の画素を示している。エッジ線５１１、５１２、５１３、５１４は何れも、メッシュの辺として用いられているが、ラスタ画像の画素を散乱的にサンプリングして頂点としている。このときのサンプリング頂点はラスタ画像の特徴量などから決定するが、エッジ線を再現するメッシュを生成することができるのであれば、他の方法を用いても構わない。ここでは、制約付きドロネー三角形分割を利用することで、特徴線を忠実に再現する直線メッシュを生成している。制約付きドロネー三角形分割は、点群と制約条件を与えると、与えられた点群を頂点とし、かつ制約条件を満たす直線メッシュを生成するアルゴリズムである。ここでの制約条件とは、点群の一部を結ぶ線分である。もちろん、エッジ線を再現するメッシュを生成することができるのであれば、他の方法を用いても構わない。
【００３４】
図３に戻って、ステップＳ３０７では、簡略化された曲線メッシュを生成する。簡略化された曲線の生成は、非特許文献１に記載の方法と同様の手順を踏むことで実現できる。つまり、初期メッシュのうち優先度の低いメッシュ同士を統合して大きなメッシュにまとめる処理と、エッジ線に沿うメッシュの辺を曲線化する処理と、を繰り返す。その曲線化の際に、メッシュ同士が重なってしまうような統合は行わないという制約を設けることで、メッシュ同士の重なりを防ぐ。
【００３５】
図４を用いて、メッシュ同士の重なりについて説明する。図４において、実線は特徴線を表現するメッシュの辺、点線は特徴線以外のメッシュの辺を示し、図４（ａ）、（ｃ）はメッシュの統合前、図４（ｂ）、（ｄ）は、それぞれ図４（ａ）、（ｃ）のメッシュの統合後である。
【００３６】
図４（ａ）、（ｂ）を例に、特徴線上の頂点４０２を頂点４０１に統合する場合を考える。特徴線を表現するメッシュの辺４０４、４０５は、統合された頂点４０２を近似するように統合・曲線化され、特徴線を表現するメッシュの辺４０７となる。また、図４（ｂ）で示されるように、特徴線以外のメッシュの辺４０６は、頂点４０２の統合により、頂点４０１に接続される。ここで、曲線で表現されているメッシュの辺４０７と直線で表現されているメッシュの辺４０６が交差していることが分かる。このような状態が、メッシュ同士が重なっている状態である。メッシュの重なりはベクトル表現してレンダリングした際、画質劣化の大きな原因となるため、極力避けなければならない。また図４（ｃ）、（ｄ）では、同様の処理を行ったとき、曲線で表現されているメッシュの辺４０７と直線で表現されているメッシュの辺４０６は交差していない。このような状態は、メッシュ同士が重なっていない良好な状態である。
【００３７】
以下では、簡略化された曲線生成処理（ステップＳ３０７）において、非特許文献１で述べられていない部分を補う形で説明する。曲線メッシュ生成処理（ステップＳ３０７）は基本的には、優先度の低いメッシュ同士を統合して大きなメッシュにまとめる処理（ステップＳ３０３）と、エッジ線に沿うメッシュの辺を曲線化する処理（ステップＳ３０４）と、を交互に繰り返す処理である。ステップＳ３０３及びステップＳ３０４における処理は公知であり、非特許文献１に記載の方法に従って行えば良い。なお非特許文献１ではステップＳ３０３において統合するメッシュを決定する優先度の基準にＱｕａｄｒｉｃ ｅｒｒｏｒ ｍｅｔｒｉｃ法という公知の手法を用いているが、面積の小さいメッシュから優先的に統合するなど、様々な方法が考えられる。また非特許文献１ではステップＳ３０４において特徴線をベジェ曲線によって近似しているが、本実施形態で既に述べたようにＢ−スプライン曲線等を用いてもかまわない。特徴線に沿うように曲線のパラメータを設定するアルゴリズムの詳細は非特許文献１では述べられていないが、本実施形態では最小二乗法を用いる。
【００３８】
次に、ステップＳ３０５における処理について説明する。ステップＳ３０５における処理の目的は、ステップＳ３０４でメッシュの辺を曲線化したことに伴い、メッシュ同士が重なっていないかどうかを判定することである。メッシュ同士が重なっているか否かの判定は、メッシュの辺同士が交差しているか否かを判定することで行う。メッシュの辺のうち、線分同士が重ならないことは保証できるため、重なりを判定するまでもない。重なりを判定する必要があるのは線分と曲線の組み合わせ、もしくは曲線と曲線の組み合わせである。
【００３９】
線分と曲線、曲線と曲線の重なりを判定する方法について詳細に述べる。曲線を十分な精度で近似する線分群に置き換えることで、線分と曲線、曲線と曲線の重なり判定はそれぞれ線分と線分群、線分群と線分群の重なり判定に置き換えることができ、それらの重なり判定は線分同士の重なり判定を繰り返すことで実現できる。２次元平面上の点（ｘ１，ｙ１）および（ｘ２，ｙ２）を結ぶ線分と、（ｘ３，ｙ３）および（ｘ４，ｙ４）を結ぶ線分が重なるかどうかは以下の（条件）を用いる。
【００４０】
（条件）
｛（ｘ１−ｘ２）×（ｙ３−ｙ１）＋（ｙ１−ｙ２）×（ｘ１−ｘ３）｝×｛（ｘ１−ｘ２）×（ｙ４−ｙ１）＋（ｙ１−ｙ２）×（ｘ１−ｘ４）｝＜０
かつ
｛（ｘ３−ｘ４）×（ｙ１−ｙ３）＋（ｙ３−ｙ４）×（ｘ３−ｘ１）｝×｛（ｘ３−ｘ４）×（ｙ２−ｙ３）＋（ｙ３−ｙ４）×（ｘ３−ｘ２）｝＜０
この条件が満たされると、２つの線分は重なっていると判定でき、この条件が満たされていない場合は、２つの線分は重なっていないと判定することができる。以上で述べた線分同士の重なり判定を行うことで、線分と曲線および曲線と曲線の重なりを判定することができる。
【００４１】
ステップＳ３０５における判定の結果、重なりがあると判定すれば、処理はステップＳ３０６に進む。一方、重なりがないと判定した場合には、処理はステップＳ３０２に戻る。
【００４２】
ステップＳ３０６では、各メッシュの状態を、最後に行ったステップＳ３０３およびステップＳ３０４の直前の状態に戻す。このように、メッシュ同士が重なるような統合を行ってしまった場合はその統合前の状態に戻すことで、常に重なりのないメッシュが作られることを保証する。ステップＳ３０６の後、再度ステップＳ３０３を実行する場合は、メッシュ同士の重なりを引き起こした統合は行わないようにしなければならない。
【００４３】
ステップＳ３０２では、ステップＳ３０７における処理を終えるか否かを判断する。終えると判断する基準には、例えばメッシュ数が初期メッシュの半分になった場合や、メッシュ数が入力画像に含まれる画素数の１／１００になった場合などが考えられる。また、ステップＳ３０５において一定回数（例えば１０回）以上連続で重なり有りと判定された場合などが考えられる。また、それらの条件の組み合わせても良い。
【００４４】
以上の処理により、入力画像を複数個のメッシュに分割する（入力画像上に複数個のメッシュを生成する）ことができる。
【００４５】
図１に戻って、色情報生成部１０４は、曲線メッシュ生成部１０３によって入力画像上に設定された各メッシュを塗るために必要な色情報を定める。色情報を生成する為には様々な方法が考えられる。その方法の１つとして考えられるのが、各メッシュを一色で塗る方法である。一色の定め方としては、メッシュの内部に含まれる画素の画素値の平均値を、このメッシュの色情報とする方法などがある。メッシュ内の色をより複雑に表現する方法としては、各メッシュに対して色を表現する関数を生成する方法が考えられる。例えば非特許文献１では、ＲＧＢの３成分に対して、メッシュ内の色を塗る薄板スプライン関数を入力画像の色を元に生成している。本実施形態では、各メッシュを更に微小な３頂点からなるメッシュ（サブメッシュ）に分割し、その微小なメッシュの頂点の画素の色を入力画像から取得し、該頂点に割り当てる（色割り当て）。レンダリングの際はそれら微小な三角形内の色を双線形補間で補うことで、各メッシュの色を塗ることができる。
【００４６】
符号化部１０５は、曲線メッシュ生成部１０３によって生成されたそれぞれのメッシュの形状情報、色情報生成部１０４が生成した各メッシュの色情報、を符号化し、入力画像に対する符号化データを生成する。
【００４７】
まず、各メッシュを構成するために必要な形状情報と色情報について説明する。図６（ａ）は、３頂点から成り且つ３頂点間が曲線で結ばれている（何れの辺も曲線で表現されている）メッシュ（曲線メッシュ）に係る形状情報を示す。６０１、６０２、６０３は曲線メッシュの頂点、６０４〜６０９は曲線メッシュの制御点である。
【００４８】
図６（ｂ）は、図６（ａ）に示した曲線メッシュに係る色情報を示す。６１０〜６２４は曲線メッシュ内におけるサブメッシュの頂点（サンプリング点）であり、それぞれのサンプリング点は色情報を有する。ここではサンプリング点はRGB値を色情報として有しているものとして説明するが、CMYKなど他の色空間における色情報を有するものとしても良い。また、入力画像がグレー画像である場合、サンプリング点は、対応する画素の輝度情報を色情報として保持することになる。サンプリング点は、ベジェパッチを規則的に分割することで導出される。ここではサンプリング点として１５点を用いているが、ベジェパッチの分割数を変更し、サンプリング点数を変更しても構わない。例えば、図８（ａ）では分割数が１であり、サンプリング数は３となる。また図８（ｂ）、（ｃ）、（ｄ）ではそれぞれ、分割数が２、３、４であり、サンプリング数は６、１０、１５点となる。
【００４９】
次に、符号化部１０５が、曲線メッシュ生成部１０３によって生成されたそれぞれのメッシュの形状情報、色情報生成部１０４が生成した各メッシュの色情報、を符号化することで生成する、符号化データの構成例について、図７を例に取り説明する。
【００５０】
図７（ａ）には、隣接する２つのメッシュ（曲線メッシュ）７２０，７２１を示しており、７０１、７０２、７０３、７０４は曲線メッシュの頂点、７０５〜７０９は曲線メッシュの辺、７１０〜７１９は曲線メッシュの制御点を示している。ここで、辺７０７は曲線メッシュ７２０の一辺であると共に、曲線メッシュ７２１の一辺でもあり、それぞれの曲線メッシュで共有されている辺（共有辺）である。
【００５１】
図７（ｂ）には、上記の曲線メッシュ７２０に対するサンプリング点７２２〜７３６、曲線メッシュ７２１に対するサンプリング点７３７〜７５１、を示している。然るに曲線メッシュ７２０に対する色情報は、サンプリング点７２２〜７３６のそれぞれにおける色情報から成り、メッシュ７２１に対する色情報は、サンプリング点７３７〜７５１のそれぞれにおける色情報から成る。ここで、上記の通り、辺７０７は曲線メッシュ７２０と曲線メッシュ７２１とで共有している。然るに、この辺７０７上にあるサンプリング点７２２とサンプリング点７４７とは同じ座標値であり、曲線メッシュ７２０と曲線メッシュ７２１とで座標を共有しているサンプリング点であることが分かる。これは、サンプリング点７２４及び７４８、サンプリング点７２７及び７４９、サンプリング点７３１及び７５０、サンプリング点７３６及び７５１、のそれぞれのセットについても同様である。
【００５２】
一方で、曲線メッシュのある一辺がエッジ線から生成された辺（エッジ線を再現可能なように生成された辺）であれば、この一辺上の各頂点は、この一辺を共有する一方の曲線メッシュの色と他方の曲線メッシュの色の２色を保持することになる。これは、エッジ線をまたぐ際に起こる急峻な色変化を表現している。
【００５３】
例えば、辺７０７がエッジ線上の辺である場合、メッシュ７２０側のサンプリング点７２２、７２４、７２７、７３１、７３６の色情報と、メッシュ７２１側のサンプリング点７４７、７４８、７４９、７５０、７５１の色情報を保持することになる。つまり、サンプリング点７２２とサンプリング点７４７は同一座標位置にあるものの、それぞれのサンプリング点は異なる色を保持する。また、サンプリング点７２４とサンプリング点７４８、サンプリング点７２７とサンプリング点７４９、サンプリング点７３１とサンプリング点７５０、サンプリング点７３６とサンプリング点７５１、のそれぞれのセットについても同様である。
【００５４】
一方、曲線メッシュのある一辺がエッジ線から生成された辺ではない場合、この一辺上の各頂点は、１色を保持することになる。例えば、辺７０７がエッジ線上以外のとき、サンプリング点７２２とサンプリング点７４７は同一座標にあり、かつ同じ色を保持する。サンプリング点７２４とサンプリング点７４８、サンプリング点７２７とサンプリング点７４９、サンプリング点７３１とサンプリング点７５０、サンプリング点７３６とサンプリング点７５１、のそれぞれのセットについても同様である。
【００５５】
本実施形態では、辺を共有する、辺上のサンプリング点を共有する、エッジ線上のサンプリング点は２種類の色を有する、という３頂点曲線メッシュの特徴を利用してメッシュ表現の効率化を図る。
【００５６】
そのために符号化部１０５は次のようにして符号化データを生成する。先ず、入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる（辺情報割り当て）。即ち、隣接する２つのメッシュ間で共有している辺も１つの辺と見なし、それぞれの辺に対して固有の情報を割り当てる。図７（ａ）の場合、辺７０５〜７０９のそれぞれに固有の情報を割り当てる。然るにメッシュ７２０と曲線メッシュ７２１とで共有する辺７０７にも１つの固有の情報が割り当てられる。この割り当ては符号化部１０５の動作前に行うようにしても良い。
【００５７】
このような情報割り当て処理で各辺に割り当てる「固有の情報」（固有情報）は、辺を一意に識別することができる情報であれば、如何なる情報であっても良い。例えば、辺を保持するメモリ上のアドレスであっても良いし、それぞれの辺に重複することなく割り当てた番号であっても良い。
【００５８】
そして符号化部１０５は、次の各種の情報が記述された符号化データを、メッシュ毎に生成する。即ち、１つのメッシュを構成するそれぞれの辺に割り当てた固有情報、該メッシュ中の各サブメッシュの頂点に割り当てた色を示す情報、が記述された符号化データを、該メッシュに対する符号化データとして生成する。そしてこのような符号化データを、メッシュ毎に生成する。
【００５９】
また、本実施形態では、固有情報を割り当てた辺毎に符号化データを生成するのであるが、１つの辺（着目辺）に対する符号化データには、次に列挙する情報が記述されている。
【００６０】
・ 着目辺に対して割り当てた固有情報
・ 着目辺の両端位置の座標
・ 着目辺が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値
・ 着目辺上の各頂点（サンプリング点）について割り当てた色を示す情報
・ メッシュ符号化処理の過程で着目辺に対して割り当てた着目辺の制御点の座標
然るにこのような情報が記された符号化データを、辺毎に生成する。そして符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、ヘッダ（辺の数、メッシュの数、メッシュの分割数、を含む）、をまとめて、入力画像に対する符号化データとし、出力する。
【００６１】
ここで、辺に対する符号化データを、辺７０７を例に取り説明する。辺７０７の符号化データを生成する際、「辺７０７に対して割り当てた固有情報」として、辺７０７を保持するメモリのアドレスや辺７０７に割り当てられた番号を記述する。
【００６２】
「辺７０７の両端位置の座標」として、辺７０７の両端の頂点７０１及び７０３のそれぞれのｘ座標値及びｙ座標値を記述する。「辺７０７が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値」として、辺７０７が入力画像中のエッジ線から生成されたものであるか否かに応じた値（例えば「生成されたものである」＝１、「生成されたものではない」＝０）を記述する。
【００６３】
「辺７０７上の各頂点（サンプリング点）について割り当てた色を示す情報」は、辺７０７が入力画像中のエッジ線から生成されたものであるか否かによって変わる。辺７０７が入力画像中のエッジ線から生成されたものである場合、サンプリング点７２２、７２４、７２７、７３１、７３６の色情報（メッシュ７２０用）、サンプリング点７４７、７４８、７４９、７５０、７５１の色情報（メッシュ７２１用）を記述する。
【００６４】
このとき、辺の両端の座標の記述順を辺の方向とし、辺の右側、左側の順番で、色情報を記述する。辺７０７の場合、頂点７０１の座標値、頂点７０３の座標値、の順に記述した場合、頂点７０１から頂点７０３に向かって辺の右側とし、サンプリング点７２２、７２４、７２７、７３１、７３６の色情報を記述する。次に左側として、サンプリング点７４７、７４８、７４９、７５０、７５１の色情報を記述する。もちろん辺に対して左右の判定さえできれば、他の記述方法を用いても構わない。
【００６５】
一方、辺７０７が入力画像中のエッジ線から生成されたものではない場合、サンプリング点７２２、７２４、７２７、７３１、７３６の色情報のみを記述する。ここで、本実施形態では色情報はＲＧＢ値を表すものとして説明しているため、ＲＧＢ置さえ導出できれば、サンプリング点間のＲＧＢ値の差分を用いるなど、他の表現を用いても構わない。
【００６６】
また、「メッシュ符号化処理の過程で辺７０７に対して割り当てた辺７０７の制御点の座標」としては、制御点７１５及び制御点７１４のそれぞれのｘ座標値及びｙ座標値を記述する。ここで、頂点の座標値については、ｘ座標値及びｙ座標値さえ導出することができるのであれば、如何なる情報を採用しても良い。例えば、頂点間の差分を保持するなど他の表現を用いても構わない。同様に制御点の座標値についても、ｘ座標値及びｙ座標値を導出することができるのであれば、如何なる情報を用いても良い。例えば、頂点との座標値の差分や制御点間の座標値の差分を保持するなど他の表現を用いても構わない。
【００６７】
また、制御点の座標値の記述順は、例えば、頂点７０１、７０３の順に座標値が記述されている場合、頂点７０１に対応する制御点７１５、頂点７０３に対応する制御点７１４の順に記述する。
【００６８】
次に、メッシュに対する符号化データを、メッシュ７２０を例に取り説明する。「メッシュ７２０を構成するそれぞれの辺に割り当てた固有情報」としては、辺７０５、７０７、７０６のそれぞれの辺の番号やアドレスを記述する。
【００６９】
このとき記述する最初の２辺、辺７０５と辺７０７が共有している頂点７０１を基準点とする。基準点となる頂点７０１から規則的にベジェパッチを分割することで、順番にサンプリング点が導出される。例えば、メッシュ７２０では、サンプリング点７２２〜７３６まで順番に導出される。然るに「メッシュ７２０中の各サブメッシュの頂点に割り当てた色を示す情報」としては、サンプリング点７２２〜７３６の色情報を、導出順（サンプリング点７２６、７２９、７３０、…の順）に記述する。
【００７０】
なお、符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、ヘッダ（辺の数、メッシュの数、メッシュの分割数、を含む）、をｚｉｐ符号化して管理しているが、非可逆符号化を含めた他の符号化方式を用いて管理しても良い。
【００７１】
従来では、メッシュ単位に符号化した場合には、辺上のサンプリング点の座標及び色を２回符号化しなければならなかったのに対し、本実施形態では１回で符号化でき、符号化効率の向上が図れる。
【００７２】
上記の処理をまとめると、次のようなものとなる。先ず、メッシュ符号化処理の過程で入力画像をメッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、入力画像中の該頂点の位置における色を割り当てる（色割り当て）。
【００７３】
次に、入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる（情報割り当て）。
【００７４】
次に、分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に割り当てた色を示す情報と、を記述したメッシュデータを生成する。
【００７５】
次に、情報を割り当てた辺毎に、以下の情報を記述した辺データを生成する。即ち、該辺に割り当てた情報、該辺の両端位置の座標、該辺が入力画像中のエッジ線から生成されたものか否かを示すフラグ値、該辺上の各頂点に割り当てた色を示す情報、メッシュ符号化処理の過程で該辺に割り当てられた該辺の制御点の座標、である。
【００７６】
そして最後に、分割したメッシュ毎に生成したメッシュデータ及び情報を割り当てた辺毎に生成した辺データ、を含むデータを、入力画像の符号化データとして生成する。
【００７７】
次に、符号化部１０５によって出力された、入力画像のメッシュ符号化結果を復号する画像処理装置について説明する。先ず、この復号処理を行う画像処理装置について、機能構成例を示す図１０のブロック図を用いて説明する。なお、図１０の構成を有する画像処理装置は、図１の構成を有する画像処理装置と別個の装置であっても良いし、同じ装置であっても良い。後者の場合、この画像処理装置は、図１に示した構成と図１０に示した構成とを有する装置であり、以下に説明する復号処理は、自身が符号化して生成した符号化データを一旦メモリに保持しておき、その後、この符号化データを復号することになる。
【００７８】
符号化データ入力部１００１は、符号化部１０５によって生成された入力画像の符号化結果である入力画像符号化データを取得し、取得した入力画像符号化データを後段の形状情報復元部１００２に送出する。
【００７９】
形状情報復元部１００２は、入力画像符号化データから３頂点曲線メッシュの形状情報を復元する。先ず形状情報復元部１００２は入力画像符号化データを取得すると、これを画像処理装置内の不図示のメモリに一旦格納する。そしてメッシュ毎の符号化データを参照する。着目メッシュの符号化データを参照すると、この符号化データ中に記述されている「着目メッシュを構成するそれぞれの辺に割り当てた固有情報」を参照する。そして「着目メッシュを構成するそれぞれの辺に割り当てた固有情報」で特定される辺の符号化データを入力画像符号化データから読み出す。そして読み出した辺の符号化データから基準点を復元し、復元した基準点から着目メッシュを復元する。
【００８０】
ここまでの処理を図７のメッシュ７２０を例に取り説明すると、メッシュ７２０の符号化データ中の「メッシュ７２０を構成するそれぞれの辺に割り当てた固有情報」を参照する。ここでは辺７０５、辺７０７、辺７０６の順に記述されている固有情報を参照する。そして記述順において最初の２辺である辺７０５と辺７０７のそれぞれの両端の座標位置を参照すると、辺７０５の何れか一端の座標位置と辺７０７の何れか一端の座標位置とは同じである。然るにこの同じ座標位置に対する頂点である頂点７０１を基準点とする。そして、基準点となる頂点７０１から反時計周りに辺を接続していく。まず辺７０５と辺７０７の位置関係（それぞれの両端の座標値から導出可能）から、辺７０５を選択する。そして、辺７０５の符号化データから頂点７０１、制御点７１０、頂点７０２、制御点７１１の座標位置を読み出すことで、これらを復元する。次に辺７０６の符号化データから制御点７１２、頂点７０３、制御点７１３の座標位置を読み出すことで、これらを復元する。最後に、辺７０７の符号化データから制御点７１４、制御点７１５の座標位置を読み出すことで、これらを復元する。
【００８１】
これらの復元処理により、メッシュ７２０の形状を一意に特定するために必要な情報（即ち形状情報）は復元されるので、結果としてメッシュ７２０の形状が復元されることになる。このような処理を、メッシュ毎に行うことで、それぞれの３頂点曲線メッシュの形状が復元される。
【００８２】
色情報復元部１００３は、形状情報復元部１００２で復元された３頂点曲線メッシュの形状情報を利用して、メッシュの色情報を復元する。この処理を図７を例に取り説明すると、基準点となる頂点７０１から、規則的にベジェパッチを分割することで、順番にサンプリング点が導出される。メッシュ７２０では、サンプリング点７２２〜７３６が導出される。
【００８３】
次にそれぞれのサンプリング点に色を割り当てる。まずメッシュ７２０の辺上のサンプリング点に色を割り当てる。基準点となる頂点７０１から反時計周りに色を復元する。先ず辺７０５の符号化データ中で色が並んでいる順番を確認する。例えば辺７０５の符号化データ中に辺７０５の両端の座標位置が頂点７０１、７０２の順に並んでいるとする。この場合、辺７０５の符号化データ中の「辺７０５上の各頂点（サンプリング点）について割り当てた色を示す情報」を、サンプリング点７２２、７２３、７２５、７２８、７３２の順に割り当てる。逆に頂点７０２、７０１の順に並んでいれば、辺７０５の符号化データ中の「辺７０５上の各頂点（サンプリング点）について割り当てた色を示す情報」を、サンプリング点７３２、７２８、７２５、７２３、７２２の順に割り当てる。次に、辺７０６の符号化データ中の「辺７０６上の各頂点（サンプリング点）について割り当てた色を示す情報」を、同様の処理によりサンプリング点７３３、７３４、７３５、７３６の順に割り当てる。最後に、辺７０７についても同様にしてサンプリング点７３１、７２７、７２４の順に色を割り当てる。
【００８４】
なお、この色割り当て処理は、辺７０７がエッジ線上の辺ではない場合の処理である。辺７０７がエッジ線上の辺である場合、辺７０７の左右どちらの色をメッシュ７２０に対して利用するか判断しなくてはならない。この判断は、色を復元している反時計周りの方向が、辺の両端（頂点）が記述されている順番と逆のとき、右側の色を使う。またその反対では、左側の色を使う。図７を例に取り説明すると、色を復元している反時計周りの方向は、頂点７０３から頂点７０１に向かう方向である。辺７０５の符号化データ中に座標値が頂点７０１、頂点７０３の順に並んでいるとき、メッシュ７２０の色として右側の色を使う。また、頂点７０３、頂点７０１の順に並んでいるとき、メッシュ７２０の色として左側の色を使う。以上の処理によりメッシュの辺上の色が復元される。
【００８５】
なお、辺７０７がエッジ線上の辺であるか否かは、辺７０７の符号化データ中の「辺７０７が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値」を参照すればよい。
【００８６】
残ったメッシュ７２０内のサンプリング点における色は、メッシュ７２０の符号化データ中に記述されている「メッシュ７２０中の各サブメッシュの頂点に割り当てた色」を用いても良いが、辺上の各頂点の色から補間により色を求めても良い。もちろん、辺上にはないサンプリング点の色を決める方法についてはこれに限るものではない。
【００８７】
ここまでの処理でメッシュの形状情報及び色情報が復元されたので、後はこれらの情報を用いれば入力画像が復元できる。然るに画像出力部１００４は、メッシュの形状情報及び色情報を用いて入力画像を復元し、復元した入力画像を出力画像として出力する。出力先については特に限定するものではなく、適当なメモリに格納しても良いし、表示装置に出力して表示させても良いし、ネットワークを介して外部の装置に対して送信しても良い。
【００８８】
＜第１の実施形態の変形例＞
図１，１０に示した各部はハードウェアで構成しても良いが、ソフトウェア（コンピュータプログラム）として実装しても良い。この場合、このソフトウェアは、ＰＣ（パーソナルコンピュータ）等、一般のコンピュータのメモリにインストールされることになる。そしてこのコンピュータのＣＰＵがこのインストールされたソフトウェアを実行することで、このコンピュータは、上述の画像処理装置の機能（図１，１０に示した各部の機能）を実現することになる。即ち、このコンピュータは、上述の画像処理装置に適用することができる。第１の実施形態に係る画像処理装置に適用可能なコンピュータのハードウェア構成例について、図９のブロック図を用いて説明する。
【００８９】
ＣＰＵ９０１は、ＲＡＭ９０２やＲＯＭ９０３に格納されているコンピュータプログラムやデータを用いて、コンピュータ全体の制御を行うと共に、画像処理装置が行うものとして説明した上述の各処理を実行する。即ち、図１，１０に示した各部が行うものとして上述した各処理を実行する。
【００９０】
ＲＡＭ９０２は、コンピュータ読み取り可能な記憶媒体の一例である。ＲＡＭ９０２は、外部記憶装置９０７や記憶媒体ドライブ９０８からロードされたコンピュータプログラムやデータ、Ｉ／Ｆ（インターフェース）９０９を介して外部装置から受信したデータなどを一時的に記憶するためのエリアを有する。更に、ＲＡＭ９０２は、ＣＰＵ９０１が各種の処理を実行する際に用いるワークエリアを有する。即ち、ＲＡＭ９０２は、各種のエリアを適宜提供することができる。ＲＯＭ９０３は、コンピュータ読み取り可能な記憶媒体の一例であり、コンピュータの設定データや、ブートプログラムなどが格納されている。
【００９１】
キーボード９０４、マウス９０５は、コンピュータの操作者が操作することで、各種の指示をＣＰＵ９０１に対して入力することができる。表示装置９０６は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ９０１による処理結果を画像や文字などでもって表示することができる。例えば、上記入力画像を表示したり、暫定的に設定したメッシュ、最終的に決定したメッシュ、復元画像等を表示したりすることができる。
【００９２】
外部記憶装置９０７は、コンピュータ読み取り可能な記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置９０７には、ＯＳ（オペレーティングシステム）や、図１，１０に示した各部の機能をＣＰＵ９０１に実現させるためのコンピュータプログラムやデータ、上記入力画像のデータ、既知の情報として説明した情報等が保存されている。外部記憶装置９０７に保存されているコンピュータプログラムやデータは、ＣＰＵ９０１による制御に従って適宜ＲＡＭ９０２にロードされ、ＣＰＵ９０１による処理対象となる。
【００９３】
記憶媒体ドライブ９０８は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置９０７やＲＡＭ９０２に出力する。なお、外部記憶装置９０７に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ９０８に読み取らせても良い。
【００９４】
Ｉ／Ｆ９０９は、外部装置をコンピュータに接続する為のものである。例えば、ディジタルカメラなど、上記入力画像を取得するための装置を、このＩ／Ｆ９０９に接続し、この外部装置から入力画像をＩ／Ｆ９０９を介してＲＡＭ９０２や外部記憶装置９０７に取得するようにしても良い。９１０は、上述の各部を繋ぐバスである。
【００９５】
上述構成において、本コンピュータの電源がＯＮになると、ＣＰＵ９０１はＲＯＭ９０３に格納されている上記ブートプログラムに従って、外部記憶装置９０７からＯＳをＲＡＭ９０２にロードする。この結果、キーボード９０４、マウス９０５を介した情報入力操作が可能となり、表示装置９０６にＧＵＩを表示することが可能となる。ユーザが、キーボード９０４やマウス９０５を操作し、外部記憶装置９０７に格納された画像処理用アプリケーションプログラムの起動指示を入力すると、ＣＰＵ９０１はこのプログラムをＲＡＭ９０２にロードし、実行する。これにより、本コンピュータが上記の画像処理装置として機能することになる。
【００９６】
ＣＰＵ９０１が実行する画像処理用のアプリケーションプログラムは、基本的に図１，１０に示す各構成要素に相当する関数を備えることになる。ここで、符号化データは外部記憶装置９０７に保存することになる。なお、このコンピュータは、以降の各実施形態に係る画像処理装置にも同様に適用可能であることは、以下の説明より明らかである。
【００９７】
［第２の実施形態］
第１の実施形態では、辺を共有する、辺上のサンプリング点を共有する、エッジ線上のサンプリング点は２種類の色を有する、という３頂点曲線メッシュの特徴を利用してメッシュ表現の効率化を図った。具体的には、辺情報とメッシュ情報を用いてデータの冗長性を削減している。本実施形態では頂点に係る情報を別個に管理し、辺情報として扱っていた頂点情報の冗長性を削減する。
【００９８】
本実施形態において入力画像を符号化する装置の構成は、図１に示した構成と同様であるが、符号化部１０５の動作のみが第１の実施形態と異なる。然るに以下では、本実施形態に係る符号化部１０５の動作について説明する。なお、メッシュ毎の符号化データの生成は第１の実施形態と同様にして行う。
【００９９】
符号化部１０５は、メッシュを生成するために入力画像上に設定された（実際にメッシュの頂点として使用されている）各頂点に対して、頂点毎に固有の情報を割り当てる（頂点情報割り当て）。この固有情報についても、それぞれの頂点を一意に識別することができる情報であれば、如何なる情報であっても良い。そして符号化部１０５は、メッシュを生成するために入力画像上に設定された（実際にメッシュの頂点として使用されている）頂点毎に、以下の情報が記述された頂点データを生成する。
【０１００】
・ 頂点の固有情報
・ 頂点の座標位置
また、符号化部１０５は、固有情報を割り当てた辺毎に符号化データを生成するのであるが、１つの辺（着目辺）に対する符号化データには、次に列挙する情報が記述されている。
【０１０１】
・ 着目辺に対して割り当てた固有情報
・ 着目辺の両端位置における頂点の固有情報
・ 着目辺が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値
・ 着目辺上の各頂点（サンプリング点）について割り当てた色を示す情報
・ メッシュ符号化処理の過程で着目辺に対して割り当てた着目辺の制御点の座標
このような情報が記された符号化データを、辺毎に生成する。そして符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、頂点毎に生成した頂点データ、ヘッダ（頂点の数、辺の数、メッシュの数、メッシュの分割数、を含む）、をまとめて、入力画像に対する符号化データとし、出力する。
【０１０２】
頂点データの記述を、図７を例に説明する。図７の場合、頂点データには、頂点７０１、７０２、７０３、７０４のそれぞれのｘ座標及びｘ座標と、頂点７０１、７０２、７０３、７０４のそれぞれの固有情報と、を記述する。頂点の座標位置は、ｘ座標、ｘ座標さえ導出できれば、頂点間の差分を保持するなど他の表現を用いても構わない。また、頂点に固有の情報には、頂点固有のアドレスが割り当てられてさえいれば、他の表現方法でも構わない。
【０１０３】
符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、頂点毎に生成した頂点データ、ヘッダ（頂点の数、辺の数、メッシュの数、メッシュの分割数、を含む）、をｚｉｐ符号化して管理している。しかし、非可逆符号化を含めた他の符号化方式を用いて管理しても良い。
【０１０４】
第１の実施形態では、頂点に接続されている辺の数の分だけ頂点座標を符号化しなければならなかったが、本実施形態の表現では、１回の符号化で表現でき符号化効率の向上が図れる。
【０１０５】
次に、本実施形態に係る符号化により生成された入力画像符号化データを復号する装置について説明する。この復号する装置は第１の実施形態と同様、図１０に示した構成を有するが、以下に説明する点のみが異なる。
【０１０６】
図７のメッシュ７２０を例に取り説明すると、形状情報復元部１００２は、メッシュ７２０の符号化データ中の「メッシュ７２０を構成するそれぞれの辺に割り当てた固有情報」を参照する。ここでは辺７０５、辺７０７、辺７０６の順に記述されている固有情報を参照する。そして記述順において最初の２辺である辺７０５と辺７０７のそれぞれの両端の頂点の固有情報に対応する座標位置を座標情報から取得して参照して、頂点７０１を基準点とする。そして、辺７０５と辺７０７の位置関係（それぞれの両端の座標値から導出可能）から、辺７０５を選択する。
【０１０７】
そして、辺７０５の符号化データ中の頂点７０１，７０２の固有情報から、頂点７０１，７０２の頂点データを特定し、特定した頂点データ、及び辺７０５の符号化データから頂点７０１、制御点７１０、頂点７０２、制御点７１１の座標位置を読み出す。これにより、これらを復元する。
【０１０８】
次に辺７０６の符号化データ中の頂点７０３の固有情報から、頂点７０３の頂点データを特定し、特定した頂点データ、及び辺７０６の符号化データから制御点７１２、頂点７０３、制御点７１３の座標位置を読み出す。これにより、これらを復元する。最後に、辺７０７の符号化データから制御点７１４、制御点７１５の座標位置を読み出すことで、これらを復元する。
【０１０９】
このような処理を、メッシュ毎に行うことで、３頂点曲線メッシュの形状が復元される。メッシュの色情報を復元する方法については第１の実施形態と同様にして行う。
【０１１０】
［第３の実施形態］
第１，２の実施形態では、メッシュの辺が曲線である３頂点曲線メッシュの表現を説明したが、本実施形態では、メッシュの辺が直線と曲線が混在している場合の３頂点曲線メッシュの表現について説明する。
【０１１１】
入力画像符号化データを生成する画像処理装置の構成は第１の実施形態と同様、図１に示した構成を有するが、符号化部１０５の動作のみが第１の実施形態と異なる。然るに以下では符号化部１０５の動作について重点的に説明する。
【０１１２】
本実施形態で取り扱う３頂点曲線メッシュの形状情報、色情報について図１１を用いて説明する。メッシュ１１１８を構成する頂点は頂点１１０１，１１０２，１１０３であり、頂点１１０１と頂点１１０２との間は曲線の辺、頂点１１０２と頂点１１０３との間は曲線の辺、頂点１１０１と頂点１１０３との間は直線の辺である。ここで、曲線の辺は制御点を伴って生成されるものであるが、直線の辺に関してはその両端さえ分かれば生成可能であるため、制御点は不要となる。
【０１１３】
本実施形態では第２の実施形態と同様に、頂点毎の頂点データ、メッシュ毎の符号化データ、辺毎の符号化データ、を生成するのであるが、辺毎の符号化データの構成のみが異なる。１つの辺（着目辺）に対する符号化データには、次に列挙する情報が記述されている。
【０１１４】
・ 着目辺に対して割り当てた固有情報
・ 着目辺の両端位置における頂点の固有情報
・ 着目辺が曲線であるか直線であるかを示すフラグ値
・ 着目辺が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値
・ 着目辺上の各頂点（サンプリング点）について割り当てた色を示す情報
・ メッシュ符号化処理の過程で着目辺に対して割り当てた着目辺の制御点の座標（着目辺が曲線である場合のみ）
このような情報が記された符号化データを、辺毎に生成する。例えば、図１１を例に取ると、辺１１０７は直線であるため、辺１１０７に対する符号化データには、次に列挙する情報が記述されている。
【０１１５】
・ 辺１１０７に対して割り当てた固有情報
・ 辺１１０７の両端位置における頂点１１０１，１１０３の固有情報
・ 辺１１０７が曲線であるか直線であるかを示すフラグ値（＝直線を示すフラグ値）
・ 辺１１０７が入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値
・ 辺１１０７上の各頂点（サンプリング点）１１２０，１１２２，１１２５，１１２９，１１３４（辺１１０７が入力画像中のエッジ線から生成されたものである場合はこれに加えて頂点１１４５〜１１４９）について割り当てた色を示す情報
・ メッシュ符号化処理の過程で辺１１０７に対して割り当てた辺１１０７の制御点の座標としてＮＵＬＬ
そして符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、頂点毎に生成した頂点データ、ヘッダ（頂点の数、辺の数、メッシュの数、メッシュの分割数、を含む）をまとめて、入力画像に対する符号化データとし、出力する。
【０１１６】
符号化部１０５は、メッシュ毎に生成した符号化データ、辺毎に生成した符号化データ、頂点毎に生成した頂点データ、ヘッダ（頂点の数、辺の数、メッシュの数、メッシュの分割数、を含む）、をｚｉｐ符号化して管理している。しかし、非可逆符号化を含めた他の符号化方式を用いて管理しても良い。
【０１１７】
次に、本実施形態に係る符号化により生成された入力画像符号化データを復号する装置について説明する。この復号する装置は第１の実施形態と同様、図１０に示した構成を有するが、以下に説明する点のみが異なる。
【０１１８】
図７のメッシュ７２０を例に取り説明すると、形状情報復元部１００２は、メッシュ７２０の符号化データ中の「メッシュ７２０を構成するそれぞれの辺に割り当てた固有情報」を参照する。ここでは辺７０５、辺７０７、辺７０６の順に記述されている固有情報を参照する。そして記述順において最初の２辺である辺７０５と辺７０７のそれぞれの両端の頂点の固有情報に対応する座標位置を座標情報から取得して参照して、頂点７０１を基準点とする。そして、辺７０５と辺７０７の位置関係（それぞれの両端の座標値から導出可能）から、辺７０５を選択する。
【０１１９】
そして、辺７０５の符号化データ中の「曲線か直線かを示すフラグ値」を参照する。図７の場合、このフラグ値は「曲線」を示すので、辺７０５の符号化データ中の頂点７０１，７０２の固有情報から、頂点７０１，７０２の頂点データを特定する。そして、特定した頂点データと辺７０５の符号化データから、頂点７０１、制御点７１０、頂点７０２、制御点７１１の座標位置を読み出すことで、これらを復元する。
【０１２０】
次に辺７０６の符号化データ中の「曲線か直線かを示すフラグ値」を参照する。図７の場合、このフラグ値は「曲線」を示すので、辺７０６の符号化データ中の頂点７０３の固有情報から、頂点７０３の頂点データを特定する。そして、特定した頂点データと辺７０６の符号化データから、頂点７０３、制御点７１２、制御点７１３の座標位置を読み出すことで、これらを復元する。
【０１２１】
最後に、辺７０７の符号化データ中の「曲線か直線かを示すフラグ値」を参照する。図７の場合、このフラグ値は「曲線」を示すので、辺７０７の符号化データから制御点７１４、制御点７１５を読み出すことで、これらを復元する。
【０１２２】
このような処理を、メッシュ毎に行うことで、３頂点曲線メッシュの形状が復元される。メッシュの色情報を復元する方法については第１の実施形態と同様にして行う。なお、第１〜３の実施形態は適宜組み合わせて使用することも可能であり、その組み合わせ方法については当業者であれば適宜考え得ることである。
【０１２３】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置であって、
前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て手段と、
前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる情報割り当て手段と、
分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記情報割り当て手段が割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て手段が割り当てた色を示す情報と、を記述したメッシュデータを生成し、
前記情報割り当て手段が情報を割り当てた辺毎に、該辺に対して前記情報割り当て手段が割り当てた情報と、該辺の両端位置の座標と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て手段が割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、
分割したメッシュ毎に生成したメッシュデータ及び前記情報割り当て手段が情報を割り当てた辺毎に生成した辺データ、を含むデータを、前記入力画像の符号化データとして生成する生成手段と
を備えることを特徴とする画像処理装置。
【請求項２】
入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置であって、
前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て手段と、
前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる辺情報割り当て手段と、
前記入力画像上でメッシュを生成するために設定したそれぞれの頂点に対して固有の情報を割り当てる頂点情報割り当て手段と、
分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記辺情報割り当て手段が割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て手段が割り当てた色を示す情報と、を記述したメッシュデータを生成し、
前記辺情報割り当て手段が情報を割り当てた辺毎に、該辺に対して前記辺情報割り当て手段が割り当てた情報と、該辺の両端に位置する頂点に対して前記頂点情報割り当て手段が割り当てた情報と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て手段が割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、
前記入力画像上でメッシュを生成するために設定したそれぞれの頂点について、該頂点について前記頂点情報割り当て手段が割り当てた情報と、該頂点の座標位置と、を記述した頂点データを生成し、
分割したメッシュ毎に生成したメッシュデータ、前記辺情報割り当て手段が情報を割り当てた辺毎に生成した辺データ、前記入力画像上でメッシュを生成するために設定したそれぞれの頂点について生成した頂点データ、を含むデータを、前記入力画像の符号化データとして生成する生成手段と
を備えることを特徴とする画像処理装置。
【請求項３】
前記生成手段は、
着目辺が前記入力画像中のエッジ線から生成されたものである場合、該着目辺を共有する一方のメッシュの該着目辺上の頂点について前記色割り当て手段が割り当てた色を示す情報及び他方のメッシュの該着目辺上の頂点について前記色割り当て手段が割り当てた色を示す情報を、前記着目辺の辺データに記述し、
前記着目辺が前記入力画像中のエッジ線から生成されたものではない場合、前記着目辺を共有する一方のメッシュの前記着目辺上の頂点について前記色割り当て手段が割り当てた色を示す情報を、前記着目辺の辺データに記述する
ことを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記生成手段は、分割したメッシュ毎に生成したメッシュデータ及び前記情報割り当て手段が情報を割り当てた辺毎に生成した辺データ、を含むデータをｚｉｐ符号化して管理することを特徴とする請求項１乃至３の何れか１項に記載の画像処理装置。
【請求項５】
前記辺データには更に、辺が直線であるか曲線であるかを示すフラグ値が記述されており、前記制御点の座標は、該フラグ値が曲線であることを示した場合に該辺データに記述されることを特徴とする請求項１乃至４の何れか１項に記載の画像処理装置。
【請求項６】
請求項１乃至５の何れか１項に記載の画像処理装置の前記生成手段が生成した前記入力画像の符号化データを復号する画像処理装置であって、
前記符号化データ中の着目メッシュのメッシュデータに記述されている、該着目メッシュを構成するそれぞれの辺に対して前記情報割り当て手段が割り当てた情報を参照し、該情報で特定される該それぞれの辺の辺データを前記符号化データから読み出す読み出し手段と、
前記着目メッシュを複数のサブメッシュに分割し、着目辺について読み出した辺データに記述されている、該着目辺上の各頂点について前記色割り当て手段が割り当てた色のうち、実際に該各頂点に割り当てる色を、該辺データの前記フラグ値に応じて決定して割り当てる割り当て手段と、
それぞれのメッシュのメッシュデータ、それぞれの辺の辺データ、前記割り当て手段で割り当てた色、によって復元されるそれぞれのメッシュにより表される画像を出力する手段と
を備えることを特徴とする画像処理装置。
【請求項７】
入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置が行う画像処理方法であって、
前記画像処理装置の色割り当て手段が、前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て工程と、
前記画像処理装置の情報割り当て手段が、前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる情報割り当て工程と、
前記画像処理装置の生成手段が、分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記情報割り当て工程で割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て工程で割り当てた色を示す情報と、を記述したメッシュデータを生成し、
前記情報割り当て工程で情報を割り当てた辺毎に、該辺に対して前記情報割り当て工程で割り当てた情報と、該辺の両端位置の座標と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て工程で割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、
分割したメッシュ毎に生成したメッシュデータ及び前記情報割り当て工程で情報を割り当てた辺毎に生成した辺データ、を含むデータを、前記入力画像の符号化データとして生成する生成工程と
を備えることを特徴とする画像処理方法。
【請求項８】
入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置が行う画像処理方法であって、
前記画像処理装置の色割り当て手段が、前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て工程と、
前記画像処理装置の辺情報割り当て手段が、前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる辺情報割り当て工程と、
前記画像処理装置の頂点情報割り当て手段が、前記入力画像上でメッシュを生成するために設定したそれぞれの頂点に対して固有の情報を割り当てる頂点情報割り当て工程と、
前記画像処理装置の生成手段が、分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記辺情報割り当て工程で割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て工程で割り当てた色を示す情報と、を記述したメッシュデータを生成し、
前記辺情報割り当て工程で情報を割り当てた辺毎に、該辺に対して前記辺情報割り当て工程で割り当てた情報と、該辺の両端に位置する頂点に対して前記頂点情報割り当て工程で割り当てた情報と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て工程で割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、
前記入力画像上でメッシュを生成するために設定したそれぞれの頂点について、該頂点について前記頂点情報割り当て工程で割り当てた情報と、該頂点の座標位置と、を記述した頂点データを生成し、
分割したメッシュ毎に生成したメッシュデータ、前記辺情報割り当て工程で情報を割り当てた辺毎に生成した辺データ、前記入力画像上でメッシュを生成するために設定したそれぞれの頂点について生成した頂点データ、を含むデータを、前記入力画像の符号化データとして生成する生成工程と
を備えることを特徴とする画像処理方法。
【請求項９】
コンピュータを、請求項１乃至６の何れか１項に記載の画像処理装置の各手段として機能させるためのコンピュータプログラム。
【請求項１】
入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置であって、
前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て手段と、
前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる情報割り当て手段と、
分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記情報割り当て手段が割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て手段が割り当てた色を示す情報と、を記述したメッシュデータを生成し、
前記情報割り当て手段が情報を割り当てた辺毎に、該辺に対して前記情報割り当て手段が割り当てた情報と、該辺の両端位置の座標と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て手段が割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、
分割したメッシュ毎に生成したメッシュデータ及び前記情報割り当て手段が情報を割り当てた辺毎に生成した辺データ、を含むデータを、前記入力画像の符号化データとして生成する生成手段と
を備えることを特徴とする画像処理装置。
【請求項２】
入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置であって、
前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て手段と、
前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる辺情報割り当て手段と、
前記入力画像上でメッシュを生成するために設定したそれぞれの頂点に対して固有の情報を割り当てる頂点情報割り当て手段と、
分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記辺情報割り当て手段が割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て手段が割り当てた色を示す情報と、を記述したメッシュデータを生成し、
前記辺情報割り当て手段が情報を割り当てた辺毎に、該辺に対して前記辺情報割り当て手段が割り当てた情報と、該辺の両端に位置する頂点に対して前記頂点情報割り当て手段が割り当てた情報と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て手段が割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、
前記入力画像上でメッシュを生成するために設定したそれぞれの頂点について、該頂点について前記頂点情報割り当て手段が割り当てた情報と、該頂点の座標位置と、を記述した頂点データを生成し、
分割したメッシュ毎に生成したメッシュデータ、前記辺情報割り当て手段が情報を割り当てた辺毎に生成した辺データ、前記入力画像上でメッシュを生成するために設定したそれぞれの頂点について生成した頂点データ、を含むデータを、前記入力画像の符号化データとして生成する生成手段と
を備えることを特徴とする画像処理装置。
【請求項３】
前記生成手段は、
着目辺が前記入力画像中のエッジ線から生成されたものである場合、該着目辺を共有する一方のメッシュの該着目辺上の頂点について前記色割り当て手段が割り当てた色を示す情報及び他方のメッシュの該着目辺上の頂点について前記色割り当て手段が割り当てた色を示す情報を、前記着目辺の辺データに記述し、
前記着目辺が前記入力画像中のエッジ線から生成されたものではない場合、前記着目辺を共有する一方のメッシュの前記着目辺上の頂点について前記色割り当て手段が割り当てた色を示す情報を、前記着目辺の辺データに記述する
ことを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記生成手段は、分割したメッシュ毎に生成したメッシュデータ及び前記情報割り当て手段が情報を割り当てた辺毎に生成した辺データ、を含むデータをｚｉｐ符号化して管理することを特徴とする請求項１乃至３の何れか１項に記載の画像処理装置。
【請求項５】
前記辺データには更に、辺が直線であるか曲線であるかを示すフラグ値が記述されており、前記制御点の座標は、該フラグ値が曲線であることを示した場合に該辺データに記述されることを特徴とする請求項１乃至４の何れか１項に記載の画像処理装置。
【請求項６】
請求項１乃至５の何れか１項に記載の画像処理装置の前記生成手段が生成した前記入力画像の符号化データを復号する画像処理装置であって、
前記符号化データ中の着目メッシュのメッシュデータに記述されている、該着目メッシュを構成するそれぞれの辺に対して前記情報割り当て手段が割り当てた情報を参照し、該情報で特定される該それぞれの辺の辺データを前記符号化データから読み出す読み出し手段と、
前記着目メッシュを複数のサブメッシュに分割し、着目辺について読み出した辺データに記述されている、該着目辺上の各頂点について前記色割り当て手段が割り当てた色のうち、実際に該各頂点に割り当てる色を、該辺データの前記フラグ値に応じて決定して割り当てる割り当て手段と、
それぞれのメッシュのメッシュデータ、それぞれの辺の辺データ、前記割り当て手段で割り当てた色、によって復元されるそれぞれのメッシュにより表される画像を出力する手段と
を備えることを特徴とする画像処理装置。
【請求項７】
入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置が行う画像処理方法であって、
前記画像処理装置の色割り当て手段が、前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て工程と、
前記画像処理装置の情報割り当て手段が、前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる情報割り当て工程と、
前記画像処理装置の生成手段が、分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記情報割り当て工程で割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て工程で割り当てた色を示す情報と、を記述したメッシュデータを生成し、
前記情報割り当て工程で情報を割り当てた辺毎に、該辺に対して前記情報割り当て工程で割り当てた情報と、該辺の両端位置の座標と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て工程で割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、
分割したメッシュ毎に生成したメッシュデータ及び前記情報割り当て工程で情報を割り当てた辺毎に生成した辺データ、を含むデータを、前記入力画像の符号化データとして生成する生成工程と
を備えることを特徴とする画像処理方法。
【請求項８】
入力画像を、３頂点から成り且つ該３頂点間を結ぶ辺が直線または曲線であるメッシュを単位に符号化するメッシュ符号化処理を実行する画像処理装置が行う画像処理方法であって、
前記画像処理装置の色割り当て手段が、前記メッシュ符号化処理の過程で前記入力画像を前記メッシュを単位に分割し、該メッシュを複数のサブメッシュに分割し、該サブメッシュの各頂点に対して、前記入力画像中の該頂点の位置における色を割り当てる色割り当て工程と、
前記画像処理装置の辺情報割り当て手段が、前記入力画像上で隣接する２つのメッシュ間で共有しているメッシュ辺、何れのメッシュとも共有していないメッシュ辺、のそれぞれに対して固有の情報を割り当てる辺情報割り当て工程と、
前記画像処理装置の頂点情報割り当て手段が、前記入力画像上でメッシュを生成するために設定したそれぞれの頂点に対して固有の情報を割り当てる頂点情報割り当て工程と、
前記画像処理装置の生成手段が、分割したメッシュ毎に、該メッシュを構成するそれぞれの辺に対して前記辺情報割り当て工程で割り当てた情報と、該メッシュ中の各サブメッシュの頂点毎に前記色割り当て工程で割り当てた色を示す情報と、を記述したメッシュデータを生成し、
前記辺情報割り当て工程で情報を割り当てた辺毎に、該辺に対して前記辺情報割り当て工程で割り当てた情報と、該辺の両端に位置する頂点に対して前記頂点情報割り当て工程で割り当てた情報と、該辺が前記入力画像中のエッジ線から生成されたものであるか否かを示すフラグ値と、該辺上の各頂点について前記色割り当て工程で割り当てた色を示す情報と、前記メッシュ符号化処理の過程で該辺に対して割り当てられた該辺の制御点の座標と、を記述した辺データを生成し、
前記入力画像上でメッシュを生成するために設定したそれぞれの頂点について、該頂点について前記頂点情報割り当て工程で割り当てた情報と、該頂点の座標位置と、を記述した頂点データを生成し、
分割したメッシュ毎に生成したメッシュデータ、前記辺情報割り当て工程で情報を割り当てた辺毎に生成した辺データ、前記入力画像上でメッシュを生成するために設定したそれぞれの頂点について生成した頂点データ、を含むデータを、前記入力画像の符号化データとして生成する生成工程と
を備えることを特徴とする画像処理方法。
【請求項９】
コンピュータを、請求項１乃至６の何れか１項に記載の画像処理装置の各手段として機能させるためのコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−２２１３１９（Ｐ２０１２−２２１３１９Ａ）
【公開日】平成２４年１１月１２日（２０１２．１１．１２）
【国際特許分類】
【出願番号】特願２０１１−８７６９９（Ｐ２０１１−８７６９９）
【出願日】平成２３年４月１１日（２０１１．４．１１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２４年１１月１２日（２０１２．１１．１２）
【国際特許分類】
【出願日】平成２３年４月１１日（２０１１．４．１１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]