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