(57)【特許請求の範囲】
【請求項１】
入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置であって、
前記入力画像からエッジ線を検出する検出手段と、
前記検出手段が検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定手段と、
前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定手段と、
前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割手段と、
前記分割手段により分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定手段と、
前記分割手段により分割されたそれぞれのメッシュを符号化し、前記色設定手段により設定された色情報を含む符号化データを出力する符号化手段と、
を備え、
前記第２の特徴点設定手段は、前記検出手段が検出したエッジ線のうち、前記規定のエッジ強度未満のエッジ線を弱エッジ線とし、該弱エッジ線から規定距離だけ離間した位置に前記複数の第２の特徴点を設定する
ことを特徴とする画像処理装置。
【請求項２】
入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置であって、
前記入力画像からエッジ線を検出する検出手段と、
前記検出手段が検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定手段と、
前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定手段と、
前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割手段と、
前記分割手段により分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定手段と、
前記分割手段により分割されたそれぞれのメッシュを符号化し、前記色設定手段により設定された色情報を含む符号化データを出力する符号化手段と、
を備え、
前記第２の特徴点設定手段は、前記入力画像における局所的な領域内での勾配の大きさ、平均色からの分散や誤差のいずれかによって算出される画像変動量が相対的に大きい領域に相対的に多くの第２の特徴点を設定する
ことを特徴とする画像処理装置。
【請求項３】
前記第２の特徴点設定手段は、前記画像変動量に基づいて前記入力画像を再帰的に細分割し、細分割された各領域に応じて前記複数の第２の特徴点を設定することを特徴とする請求項２に記載の画像処理装置。
【請求項４】
入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置であって、
前記入力画像からエッジ線を検出する検出手段と、
前記検出手段が検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定手段と、
前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定手段と、
前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割手段と、
前記分割手段により分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定手段と、
前記分割手段により分割されたそれぞれのメッシュを符号化し、前記色設定手段により設定された色情報を含む符号化データを出力する符号化手段と、
を備え、
前記第２の特徴点設定手段は、前記検出手段が検出したエッジ線のエッジ強度と該エッジ線の周辺画素における画素値の変化の程度との少なくとも一方に応じて、該エッジ線から規定距離だけ離間した位置に前記複数の第２の特徴点を設定する
ことを特徴とする画像処理装置。
【請求項５】
前記第２の特徴点設定手段は、前記第１の特徴点設定手段が設定した前記複数の第１の特徴点のうち同一のエッジ線に沿って隣接する２つの特徴点で挟まれるエッジ線の区間のエッジ強度と該区間の周辺画素における画素値の変化の程度との少なくとも一方に応じて、該エッジ線から規定距離だけ離間した位置に前記複数の第２の特徴点を設定することを特徴とする請求項４に記載の画像処理装置。
【請求項６】
前記複数の第２の特徴点のうち、前記複数の第１の特徴点の何れかとの距離が所定距離以下である第２の特徴点を削除する削除手段を更に備えることを特徴とする請求項１乃至３の何れか一項に記載の画像処理装置。
【請求項７】
前記複数の第２の特徴点のうち、前記複数の第１の特徴点の何れか、又は、前記複数の第２の特徴点の他の何れかとの距離が所定距離以下である第２の特徴点を削除する削除手段を更に備えることを特徴とする請求項１乃至５の何れか一項に記載の画像処理装置。
【請求項８】
前記分割手段は、前記強エッジ線に沿って隣接する２つの第１の特徴点を結ぶ辺が全てが何れかのメッシュの一辺となるように前記複数のメッシュに分割する分割することを特徴とする請求項１乃至７の何れか一項に記載の画像処理装置。
【請求項９】
前記分割手段は、前記強エッジ線に沿って隣接する２つの第１の特徴点を結ぶ辺に対して、該強エッジ線への曲線近似を行う曲線化手段を含むことを特徴とする請求項１乃至８の何れか一項に記載の画像処理装置。
【請求項１０】
入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置が行う画像処理方法であって、
検出手段が、前記入力画像からエッジ線を検出する検出工程と、
第１の特徴点設定手段が、前記検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定工程と、
第２の特徴点設定手段が、前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定工程と、
分割手段が、前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割工程と、
色設定手段が、前記分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定工程と、
符号化手段が、前記分割されたそれぞれのメッシュを符号化し、前記設定された色情報を含む符号化データを出力する符号化工程と、
を含み、
前記第２の特徴点設定工程において、前記第２の特徴点設定手段は、前記検出手段が検出したエッジ線のうち、前記規定のエッジ強度未満のエッジ線を弱エッジ線とし、該弱エッジ線から規定距離だけ離間した位置に前記複数の第２の特徴点を設定する
ことを特徴とする画像処理方法。
【請求項１１】
入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置が行う画像処理方法であって、
検出手段が、前記入力画像からエッジ線を検出する検出工程と、
第１の特徴点設定手段が、前記検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定工程と、
第２の特徴点設定手段が、前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定工程と、
分割手段が、前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割工程と、
色設定手段が、前記分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定工程と、
符号化手段が、前記分割されたそれぞれのメッシュを符号化し、前記設定された色情報を含む符号化データを出力する符号化工程と、
を含み、
前記第２の特徴点設定工程において、前記第２の特徴点設定手段は、前記入力画像における局所的な領域内での勾配の大きさ、平均色からの分散や誤差のいずれかによって算出される画像変動量が相対的に大きい領域に相対的に多くの第２の特徴点を設定する
ことを特徴とする画像処理方法。
【請求項１２】
入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置が行う画像処理方法であって、
検出手段が、前記入力画像からエッジ線を検出する検出工程と、
第１の特徴点設定手段が、前記検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定工程と、
第２の特徴点設定手段が、前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定工程と、
分割手段が、前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割工程と、
色設定手段が、前記分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定工程と、
符号化手段が、前記分割されたそれぞれのメッシュを符号化し、前記設定された色情報を含む符号化データを出力する符号化工程と、
を含み、
前記第２の特徴点設定工程において、前記第２の特徴点設定手段は、前記検出手段が検出したエッジ線のエッジ強度と該エッジ線の周辺画素における画素値の変化の程度との少なくとも一方に応じて、該エッジ線から規定距離だけ離間した位置に前記複数の第２の特徴点を設定する
ことを特徴とする画像処理方法。
【請求項１３】
コンピュータを請求項１乃至９の何れか一項に記載の画像処理装置の各手段として機能させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像をベクトル表現する画像処理技術に関し、特にラスタ画像をメッシュ群により表現するメッシュ符号化技術に関するものである。
【背景技術】
【０００２】
従来から、画像をベクトル表現する技術は広く知られている。ベクトル表現された画像は、拡大縮小時に画質劣化が少ない、編集がし易い、高い圧縮率を実現できるなどの利点がある。また、イラストや文字をベクトル表現する場合には、オブジェクトの輪郭をベジェ、スプライン関数などで近似する手法が用いられている。オブジェクトの領域内は、単一色、線形グラデーション、放射状グラデーションなどで塗ることができるが、複雑なグラデーションの表現は困難である。
【０００３】
複雑なグラデーションを含むオブジェクトをベクトル表現するには、例えば、米アドビシステムズ社のＩｌｌｕｓｔｒａｔｏｒ（登録商標）のグラディエント・メッシュ・ツールが用いられる。グラディエント・メッシュでは、メッシュに色と勾配を与えて３次関数を生成することで複雑なグラデーションを含むオブジェクトを描画できる（特許文献１）。
【０００４】
グラディエント・メッシュは４頂点から成る曲線メッシュであるが、３頂点から成る曲線メッシュにより、複雑なグラデーションをベクトル表現する技術が知られている（非特許文献１）。画像内のエッジを線分群（以下、エッジ線と呼ぶ）として抽出し、当該エッジ線を再現する３頂点曲線メッシュ群を構成することでベクトル表現を行う。ここで３頂点曲線メッシュとは、メッシュの頂点数が３であり、頂点間を結ぶメッシュの辺が直線または曲線であるものとする。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第４２２００１０号公報
【非特許文献】
【０００６】
【非特許文献１】Tian Xia, Binbin Liao, and Yizhou Yu, "Patch-Based Image Vectorization with Automatic Curvilinear Feature Alignment", ACM SIGGRAPH Asia 2009, Vol.28, No.5.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
自然画像のような色が複雑に変化するオブジェクトを３頂点曲線メッシュ群によりベクトル表現することを考える。直線メッシュに対して曲線メッシュは、オブジェクトの形状や特徴を曲線で近似するため、より少ないメッシュ数でオブジェクトを近似できる。
【０００８】
ただし、３頂点曲線メッシュ群で画像を精度良く近似するためには、エッジ線を適切に再現し、且つ、画像の大域的な色変化や弱いエッジの特徴を捉えたメッシュ群を生成する必要がある。そこで、画像内のエッジ線を抽出し、画像の全画素を頂点としてエッジ線を再現する初期メッシュ群を生成し、当該初期メッシュ群からメッシュ簡略化によりメッシュ数を削減することにより３頂点曲線メッシュ群を生成する方法が知られている。ただし、この方法では、メッシュ群を簡略化する度に色変化を計算する必要があるため、画像近似精度は良いものの計算量が多くなってしまう。また、画像内のエッジ線を抽出し、当該エッジ線上の点と画像をサブサンプリングした点とを頂点とし、ドロネー三角形分割から３頂点曲線メッシュ群を生成する方法がある。ただし、この方法ではエッジ線は再現可能なものの、エッジ線以外の部分では単純なサブサンプリングを用いているため、不要なメッシュが多くなってしまう。
【０００９】
本発明は上述の問題点に鑑みなされたものであり、画像近似精度の良い効率的なメッシュ群を生成するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述の１以上の問題点を解決するため、本発明の画像処理装置は以下の構成を備える。すなわち、入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置において、前記入力画像からエッジ線を検出する検出手段と、前記検出手段が検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定手段と、前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定手段と、前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割手段と、前記分割手段により分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定手段と、前記分割手段により分割されたそれぞれのメッシュを符号化し、前記色設定手段により設定された色情報を含む符号化データを出力する符号化手段と、を備え、前記第２の特徴点設定手段は、前記検出手段が検出したエッジ線のうち、前記規定のエッジ強度未満のエッジ線を弱エッジ線とし、該弱エッジ線から規定距離だけ離間した位置に前記複数の第２の特徴点を設定する。
又は、入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置において、前記入力画像からエッジ線を検出する検出手段と、前記検出手段が検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定手段と、前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定手段と、前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割手段と、前記分割手段により分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定手段と、前記分割手段により分割されたそれぞれのメッシュを符号化し、前記色設定手段により設定された色情報を含む符号化データを出力する符号化手段と、を備え、前記第２の特徴点設定手段は、前記入力画像における局所的な領域内での勾配の大きさ、平均色からの分散や誤差のいずれかによって算出される画像変動量が相対的に大きい領域に相対的に多くの第２の特徴点を設定する。
あるいは、入力画像を複数のメッシュに分割し、分割したメッシュを符号化するメッシュ符号化処理を行う画像処理装置において、前記入力画像からエッジ線を検出する検出手段と、前記検出手段が検出したエッジ線のうち、規定のエッジ強度以上のエッジ線を強エッジ線とし、該強エッジ線上に複数の第１の特徴点を設定する第１の特徴点設定手段と、前記入力画像上に、前記複数の第１の特徴点とは異なる複数の第２の特徴点を設定する第２の特徴点設定手段と、前記複数の第１の特徴点と前記複数の第２の特徴点とを統合した特徴点集合を用いて、前記入力画像を、該特徴点集合内の各点を頂点とする複数のメッシュに分割する分割手段と、前記分割手段により分割されたそれぞれのメッシュの各頂点に対して、前記第１の特徴点に対応する頂点に対しては該頂点に対応する位置の前記強エッジ線における両側２色の色情報を設定し、前記第２の特徴点に対応する頂点に対しては該頂点に対応する位置の１色の色情報を設定する色設定手段と、前記分割手段により分割されたそれぞれのメッシュを符号化し、前記色設定手段により設定された色情報を含む符号化データを出力する符号化手段と、を備え、前記第２の特徴点設定手段は、前記検出手段が検出したエッジ線のエッジ強度と該エッジ線の周辺画素における画素値の変化の程度との少なくとも一方に応じて、該エッジ線から規定距離だけ離間した位置に前記複数の第２の特徴点を設定する。
【発明の効果】
【００１１】
本発明によれば、画像近似精度の良い効率的なメッシュ群を生成可能とする技術を提供することができる。
【図面の簡単な説明】
【００１２】
【図１】第１実施形態に係る画像処理装置の機能構成を示すブロック図である。
【図２】特徴線検出部１０２が行う処理を説明するための図である。
【図３】第１の特徴点設定部１０３が行う第１の特徴点設定処理を説明するための図である。
【図４】特徴線に対するサンプリング点決定処理の過程を示す図である。
【図５】第２の特徴点設定部１０４が行う第２の特徴点設定処理を説明するための図である。
【図６】特徴点統合部１０５が行う処理を説明するための図である。
【図７】メッシュ生成部１０６が行う処理の動作フローチャートである。
【図８】メッシュの辺の曲線化処理を説明するための図である。
【図９】生成された３頂点曲線メッシュ群の例を例示的に示す図である。
【図１０】３頂点曲線メッシュの形状及び色情報のサンプリング点を例示的に示す図である。
【図１１】色情報を保持するサンプリング点の例を示す図である。
【図１２】色設定部１０７が行う処理を説明するための図である。
【図１３】コンピュータのハードウェア構成例を示す図である。
【図１４】第２実施形態で第２の特徴点設定部１０４が行う処理を説明するための図である。
【図１５】第３実施形態で第２の特徴点設定部１０４が強エッジに対し行う処理を説明するための図である。
【図１６】第３実施形態で第２の特徴点設定部１０４が弱エッジに対し行う処理を説明するための図である。
【図１７】第３実施形態で特徴点統合部１０５が行う特徴点統合の処理を説明するための図である。
【図１８】第３実施形態で特徴点統合部１０５が行う第２の特徴点の削除の処理を説明するための図である。
【図１９】第３実施形態で生成された３頂点曲線メッシュ群の例を例示的に示す図である。
【発明を実施するための形態】
【００１３】
以下に、図面を参照して、この発明の好適な実施の形態を詳しく説明する。なお、以下の実施の形態はあくまで例示であり、本発明の範囲を限定する趣旨のものではない。
【００１４】
（第１実施形態）
＜概要＞
第１実施形態では、入力画像を複数のメッシュに分割し、分割したメッシュ毎に符号化するメッシュ符号化処理を行う画像処理装置について説明する。特に、入力画像に対してエッジ抽出処理を行い、強エッジに基づいて第１の特徴点を弱エッジに基づいて第２の特徴点をそれぞれ設定し、これらの２種類の特徴点をメッシュの頂点に利用する。また、第１の特徴点に対応する頂点には２色の色情報を割り当て、第２の特徴点に対応する頂点には１色の色情報を割り当てる。この構成により、画像近似精度の良い効率的なメッシュ群を生成する。
【００１５】
＜前提技術＞
はじめに、３頂点曲線メッシュについて説明する。なお、３頂点を結ぶ曲線としては、ベジェ曲線、Ｂ−スプライン等の様々な種類の曲線を用いることが可能である。以下の説明では、３頂点曲線メッシュにパラメトリック曲面の一つである３頂点のベジェパッチを用いる。ベジェパッチの中でも特に３次のベジェパッチでは、メッシュの各辺が３次のベジェ曲線となるため、３頂点曲線メッシュを生成したのちにユーザによる編集が容易という利点がある。Ｐ１、Ｐ２、Ｐ３を頂点とする３次のベジェパッチ内の点は以下の式で表される。
【００１６】
【数１】
0005888989.tif 000002
【００１７】
ここで、ｓ、ｔ、ｕはパッチのパラメータである。また、ｐ１、ｐ２、ｐ３は、それぞれ頂点Ｐ１、Ｐ２、Ｐ３の座標値である。更に、ｃ１〜ｃ７は曲線パッチの形状を定めるパラメータである。特に、ｃ１〜ｃ６はベジェパッチの輪郭を決める３つのベジェ曲線の制御点に対応するパラメータである。一方、ｃ７はベジェパッチの輪郭には関与しないパラメータであり、ベジェパッチの頂点の座標と、輪郭を成すベジェ曲線の制御点に対応するパラメータとに基づいて以下のように決定されるパラメータである。
【００１８】
【数２】
0005888989.tif 000003
【００１９】
＜装置構成および各部の動作＞
図１は、第１実施形態に係る画像処理装置の機能ブロック図である。図１に示すように、画像処理装置は、画像入力部１０１、特徴線検出部１０２、第１の特徴点設定部１０３、第２の特徴点設定部１０４、特徴点統合部１０５、メッシュ生成部１０６、色設定部１０７、出力部１０８を有している。
【００２０】
画像入力部１０１には、処理対象となるラスタ画像が入力される。なお、入力される画像は、カラー画像、グレー画像、白黒画像のいずれでも構わない。なお、入力画像は矩形画像でも構わないし、画像の一部をベクトル化したい場合には背景部を透過色に設定した画像等、切り出された領域が与えられても良い。
【００２１】
特徴線検出部１０２により入力画像上の特徴を表す曲線形状の特徴線を構成する。ここでは第１の特徴点設定部１０３で用いられる特徴線と、第２の特徴点設定部１０４で用いられる特徴線の２種類の特徴線を構成する。第１実施形態では特徴線としてエッジ線を用いる。以下の説明では、特徴線検出部１０２を、エッジ検出部１０２−１と、エッジ線構成部１０２−２とに分けて説明する。
【００２２】
エッジ検出部１０２−１では入力画像のエッジとなる画素を検出する。第１実施形態ではキャニー法という既知の方法を用いるが、他の手法を用いても構わない。またキャニー法が効果的に機能するように、入力画像に明るさ調整、エッジ強調などの前処理を施しても構わない。
【００２３】
エッジ線構成部１０２−２ではエッジ検出部１０２−１で抽出されたエッジ画素のうち、隣接するもの同士を結ぶ線分を構成することで、エッジを再現する線分群を構成する。隣接画素を結んで線分群を構成する際に、注目画素の上、下、左、右にある４つの画素が隣接しているとみなす４連結接続がある。また、当該４方向に加えて右上、右下、左上、左下にある４つの画素も隣接していると見なす８連結接続もある。第１実施形態では８連結接続を用いる。エッジ検出部１０２−１においてキャニー法を用いた結果に対して、８連結接続で隣接しているとみなせる画素を結ぶと、以下で説明するようにエッジ線として望ましくない結果が得られる場合がある。
【００２４】
図２は、特徴線検出部１０２が行う処理、特に、エッジ線構成部１０２−２が行う処理を説明する図である。部分画像２００ａ内の四角はそれぞれ画素を表し、エッジ検出においてエッジと見なされた画素を斜線で示している。これらエッジ画素に対して８連結接続で隣接した画素を結ぶと部分画像２００ｂに示すようにエッジ画素２０１、２０２、２０３を結ぶループが発生してしまう。そのため、部分画像２００ａのようなエッジが検出された場合は、ループのないエッジ線によって結ばれるべきである。そこで、ここでは８連結接続を行う前に、Ｈｉｌｄｉｔｃｈ細線化法という既知の手法を適用することでこの問題を解決する。Ｈｉｌｄｉｔｃｈ細線化を行うと、部分画像２００ｂに示したエッジ画素２０１はエッジ画素でないと判断される。その結果、部分画像２００ｃに示すように、エッジ画素がループのない１つのエッジ線によって結ばれることになる。
【００２５】
特徴線検出部１０２で構成する特徴線としては、エッジ抽出処理で検出されるエッジ線の他、ベクトル化対象オブジェクトの輪郭を用いることも可能である。ここでオブジェクトとは、入力画像内にある文字や物体像等を指している。入力画像の一部をベクトル表現するという目的で、入力画像の一部が透過色に設定されている場合は、透過色と非透過色の境界に有る画素がオブジェクトの輪郭画素となる。なお、オブジェクトの輪郭画素からの線分群の構成は、エッジ線構成部１０２−２と同様の手順に従って隣接する画素同士をつなぎ合わせることで実現できる。なお、特徴線のさらに別の例としては、入力画像の領域分割における境界線が考えられる。領域分割は最近傍法を用いたもの、ＥＭアルゴリズムを利用したものなど、多くの手法が知られている。
【００２６】
第１実施形態においては、エッジ検出部１０２−１は、互いに異なる２つのエッジ閾値を用いることにより、２通りのエッジを抽出する。具体的には、規定のエッジ強度以上のエッジ線である”強エッジ”（画像３００ａ）、規定のエッジ強度未満のエッジ線である”強エッジ”と”弱エッジ”の双方（画像５００ａ）を抽出する。これは例えば、濃度変化の基準として２通りの閾値を用い、キャニー法を利用してそれぞれの閾値に対してエッジ画素を抽出している。その後、抽出された２通りのエッジ画素は、それぞれエッジ線構成部１０２−２により特徴線として構成される。なお、画像の強エッジの画素と弱エッジの画素が得られるのであれば、異なるエッジ抽出フィルタを用いるなど他の方法を用いても構わない。
【００２７】
図３は、第１の特徴点設定部１０３が行う第１の特徴点設定処理を説明するための図である。画像３００ａは、第１の特徴点設定部１０３に入力される強エッジの特徴線を例示的に示している。第１の特徴点設定部１０３は、強エッジ線上に、図４に示される処理に従って第１の特徴点を設定（サンプリング）する処理を行う。設定処理の結果、画像３００ｂの黒丸で示されるような第１の特徴点が設定される。
【００２８】
図４（ａ）は、特徴線である線分群を示しており、４０１、４０２、４０３、４０４、４０５はそれぞれ特徴線を構成する頂点である。まず、図４（ｂ）に示すように、特徴線の端点である頂点４０１を起点として、頂点４０２が削除され、頂点４０１と頂点４０３を近似曲線の端点として、頂点４０２を近似するように近似関数４０６を生成する。ここで近似関数は、３次のベジェ関数を最小自乗近似により生成しているが、Ｂ−スプライン関数など他の関数を用いても構わない。生成した近似関数４０６と削除した頂点４０２との距離から誤差を計算し、誤差が閾値以内であれば次の頂点を削除する。ここでは、誤差の閾値は１画素としている。
【００２９】
誤差が閾値以内である場合、隣接する次の頂点に対する処理に進む。つまり、図４（ｃ）に示すように、頂点４０３を削除し、頂点４０１と頂点４０４とを近似曲線の端点として、頂点４０２と４０３を近似するように近似関数４０７を生成する。そして、近似関数４０７と頂点４０２、４０３との誤差を計算する。
【００３０】
誤差が閾値以内である場合、隣接する次の頂点に対する処理に進む。つまり、図４（ｄ）に示すように、頂点４０４を削除し、頂点４０１と頂点４０５とを近似曲線の端点として頂点４０２、４０３、４０４を近似するように近似関数４０８を生成する。近似関数４０８と頂点４０２、４０３、４０４との誤差を計算する。ここで近似関数４０８と頂点４０２、４０４との誤差が閾値を超えたとする。このとき近似関数４０８は採用せず、前に生成された近似関数４０７が有効な近似関数として採用される。
【００３１】
上述の処理を経て、図４（ｅ）（図４（ｃ）と同じ）に示すように、特徴線の端点である頂点４０１を起点として、頂点４０２、４０３は削除され、近似曲線の端点である頂点４０４は削除されず残ることになる。そして、この例では、特徴線の端点である頂点４０１と４０５、及び近似曲線の端点である頂点４０４がそれぞれ第１の特徴点として設定される。なお、ここでは、５個の頂点を含む特徴線に対して説明を行ったが、より多い頂点を含む特徴線に対しても上述と同様の処理を繰り返すことにより第１の特徴点として設定される。また、ここでは、特徴線の端点を起点として隣接頂点を順番に削除して近似関数を生成していく例について説明したが、特徴線の端点間を均等にサンプリングするなど他の方法を用いて第１の特徴点を設定しても構わない。
【００３２】
図５は、第２の特徴点設定部１０４が行う第２の特徴点設定処理を説明するための図である。画像５００ｂは、第２の特徴点設定部１０３に入力される弱エッジの特徴線を例示的に示している。ここで、弱エッジを示す画像５００ｂは、例えば、エッジ検出部１０２−１により得られる画像３００ａ（強エッジのみ）と画像５００ａ（強エッジと弱エッジ）との差分を導出することにより得られる。つまり、弱エッジ線は、規定のエッジ強度未満のエッジ線を意味する。
【００３３】
第２の特徴点設定部１０４は、画像５００ｂに示される特徴線（弱エッジ）から規定距離だけ離間した位置の画素を第２の特徴点として設定（サンプリング）する。例えば、特徴線に沿って、各特徴線の端点から５画素置きに特徴線から３画素の距離にある画素を第２の特徴点として設定する。設定処理の結果、画像５００ｃの白抜き黒丸で示されるような第２の特徴点が設定される。ただし、特徴線の周辺画素をサンプリングするのであれば、他の方法を用いても構わない。
【００３４】
図６は、特徴点統合部１０５の処理を説明する図である。特徴点統合部１０５では、第１の特徴点設定部１０３で得られた第１の特徴点と、第２の特徴点設定部１０４で得られた第２の特徴点を統合する。画像３００ｂで示される第１の特徴点と、画像５００ｃで示される第２の特徴点を統合した特徴点集合を図６（ａ）に示す。図６（ａ）において、第１の特徴点は黒丸で示され、第２の特徴点は白抜き黒丸で示される。
【００３５】
なお、メッシュ数の増大を防ぐため、第１の特徴点に近接した第２の特徴点が存在する場合、当該第２の特徴点を削除するよう構成するとよい。例えば、第１の特徴点から所定距離以下（３画素以内）に第２の特徴点が存在する場合、当該第２の特徴点を削除する。図６（ａ）においては、第１の特徴点に隣接している第２の特徴点である頂点６０１、６０２が削除される。
【００３６】
図６（ｂ）は、特徴点統合部１０５で最終的に生成されるデータを例示的に示しており、特徴点データと辺データとを含む。なお、辺データは、特徴線（強エッジ）上で隣接する第１の特徴点同士を接続して生成する。以降で説明するように、特徴点はメッシュの頂点として利用され、辺データは、生成されるメッシュの一辺として利用される。
【００３７】
メッシュ生成部１０６の処理について図７〜図９を参照して説明する。メッシュ生成部１０６は、特徴線（強エッジ）を再現する３頂点曲線メッシュ群を生成する機能部である。つまり、３頂点曲線メッシュ群を構成する複数の３頂点曲線メッシュの各々の形状情報を生成する。
【００３８】
図７は、メッシュ生成部１０６の処理を説明するフローチャートである。以下の、ステップに先立って、特徴点統合部１０５により出力される特徴点データと辺データとがメッシュ生成部１０６に入力される。
【００３９】
ステップＳ７０１では、曲線化対象とする辺を設定する。ここでは、特徴点統合部１０５で生成した辺データ（すなわち、第１の特徴点同士を結ぶ辺）が曲線化対象とする辺として設定される。
【００４０】
ステップＳ７０２では、３頂点直線メッシュ群を生成する。例えば、ステップＳ７０１で設定した辺を制約条件として制約付きドロネー三角形分割を利用することにより、当該設定した辺が各メッシュの辺となる３頂点直線メッシュ群を生成する。ここで、各メッシュの頂点は特徴点集合内の各点から選択される。なお、制約付きドロネー三角形分割は、点群と制約条件を与えると、与えられた点群を頂点とし、かつ制約条件を満たす直線メッシュを生成するアルゴリズムである。ここで制約条件とは点群の一部を結ぶ線分である。ただし、特徴点統合部１０５で生成した辺データを再現するメッシュを生成さえすれば、他の方法を用いても構わない。
【００４１】
ステップＳ７０３では、曲線化対象の全ての辺が曲線化済みか判断する。曲線化していない辺があるとき、ステップＳ７０４の処理に進む。そして、ステップＳ７０４では、曲線化対象で曲線化されていない辺を一つ選択し、ステップＳ７０５では、特徴線を近似するようにメッシュの辺を曲線近似する曲線化処理を行う。その後ステップＳ７０３に戻り、全ての辺が曲線化済みと判断した場合、曲線化処理を終了する。
【００４２】
図８は、メッシュの辺の曲線化処理を説明するための図である。ここでは、頂点８０１と８０２を接続する辺８０５が曲線化処理の対象となっている。そして、頂点８０１と８０２を端点とし頂点８０３、８０４を近似するような近似関数により辺８０７を生成する。なお、第１実施形態では、第１の特徴点設定部１０３で生成した３次のベジェ関数をそのままメッシュの辺として利用可能であるため、曲線を再計算する必要はない。
【００４３】
以上の処理により、図９に示されるような３頂点曲線メッシュ群９００が入力画像に対して生成される。つまり、入力画像を複数の３頂点曲線メッシュの形状を決定することができる。
【００４４】
色設定部１０７は、メッシュ生成部１０６で生成された３頂点曲線メッシュ群に含まれる各３頂点曲線メッシュの色を規定する色情報を生成し設定する機能部である。なお、色情報を生成するには様々な方法が考えられ、例えば、各メッシュに対して一色を生成してもよい。この場合、一色の決定方法としては、メッシュの内部領域に対応する入力画像の画素の色平均を用いることが考えられる。一方、メッシュ内の色をより複雑に表現する方法としてメッシュに対して色を表現する関数を生成する方法が考えられる。例えば非特許文献１ではＲＧＢの３成分に対して、メッシュ内の色を塗る薄板スプライン関数を入力画像の色を元に生成している。
【００４５】
第１実施形態では、メッシュを更に微小な３頂点からなるメッシュに細分割し、その微小な細分割メッシュの頂点をサンプリング点として、該サンプリング点に対応する入力画像の位置から色を取得する。レンダリングの際は、それら微小な三角形内の色を双線形補間で補うことで、メッシュの色を塗ることができる。
【００４６】
図１０は、３頂点曲線メッシュの形状及び色情報のサンプリング点を例示的に示す図である。図１０（ａ）は、１つの３頂点曲線メッシュの形状を例示的に示す図である。１００１、１００２、１００３はメッシュの頂点、１００４から１００９はメッシュの制御点である。メッシュの形状情報はメッシュ生成部１０６で算出されている。一方、図１０（ｂ）は３頂点曲線メッシュの色情報を示す。各サンプリング点１０１０から１０２４について、それぞれ色情報（ＲＧＢ値）を持つ。なお、色情報としてＣＭＹＫなど他の色空間の情報を保持するよう構成してもよい。なお、グレー画像の場合は、輝度情報を保持するよう構成するとよい。色情報を保持するサンプリング点は、ベジェパッチを規則的に分割することで導出される。図１０（ｂ）では、色情報のサンプリング点として１５点を使用する例を示しているが、ベジェパッチの辺を分割する数を変更し、サンプリング数を変更しても構わない。
【００４７】
図１１は、色情報を保持するサンプリング点の例を示す図である。図１１（ａ）では辺の分割数が１であり、サンプリング点の数は３個となる。また、図１１（ｂ）〜（ｄ）は、それぞれ、辺の分割数が２、３、４の例を示しており、サンプリング点の数はそれぞれ６個、１０個、１５個となる。
【００４８】
また、色設定部１０７は、メッシュ生成部１０６が生成した各々の３頂点曲線メッシュに対して、特徴線上の辺に対しては２種類の色（強エッジ線における両側２色）を割り当てる。これにより、特徴線（強エッジ線）をまたぐ際に起こる急峻な色変化の表現を可能とする。
【００４９】
図１２は、色設定部１０７が行う処理を説明するための図である。図１２（ａ）に示す頂点１２０１〜１２０５は、特徴線上では無い領域に存在する頂点である。この場合、色設定部１０７は、各頂点に対し１色の色情報を設定する。一方、図１２（ｂ）に示す頂点１２０６〜１２１０は、特徴線上に存在する頂点である。この場合、色設定部１０７は、各頂点に対し２色の色情報を設定する。特に、図１２（ｂ）では、特徴線上に存在する頂点１２０６〜１２１０の各々に対し、白色及び黒色の２色の色情報（輝度値）を設定する例を示している。
【００５０】
つまり、第１の特徴点に対応する頂点に対しては２色の色情報を設定し、辺（特徴線）を挟んで色が不連続となるように色表現を行い、強エッジの急峻な勾配を表現している。一方、第２の特徴点に対応する頂点に対しては１色の色情報を設定し、辺を挟んで色が連続的に変化するように色表現を行う。
【００５１】
出力部１０８では、メッシュ生成部１０６で決定された３頂点曲線メッシュの形状情報と、色設定部１０７により決定された色情報とに基づいて、各メッシュに対するメッシュ符号化データを生成して出力する。なお、画像入力部１０１により入力されたラスタ画像の全域に対するメッシュ符号化データ群を生成するよう構成してもよいし、当該ラスタ画像の特定部分に対する１以上のメッシュ符号化データのみを生成するよう構成してもよい。
【００５２】
以上説明したとおり第１実施形態によれば、強エッジに基づく第１の特徴点と弱エッジに基づく第２の特徴点との２種類の特徴点をメッシュの頂点に利用する。更に、第１の特徴点に対応する頂点には２色の色情報を設定し、第２の特徴点に対応する頂点には１色の色情報を設定する。このように構成することにより、画像近似精度の良い効率的なメッシュ群を生成可能となる。
【００５３】
（変形例）
上述の画像処理装置の各部はハードウェアにより構成しても良いが、当該各部の一部又は全部をコンピュータプログラムとして実装しても良い。すなわち、コンピュータのＣＰＵが当該コンピュータプログラムを実行することで、上述の画像処理装置の機能を実現する。
【００５４】
図１３は、上述した第１実施形態に係る画像処理装置として適用可能なコンピュータのハードウェア構成を示す図である。
【００５５】
ＣＰＵ１３０１は、ＲＡＭ１３０２やＲＯＭ１３０３に格納されているコンピュータプログラムやデータを用いて、コンピュータ全体の制御を行うと共に、画像処理装置が行うものとして説明した上述の各処理を実行する。即ち、図１に示した各部が行うものとして上述した各処理を実行する。
【００５６】
ＲＡＭ１３０２は、コンピュータ読み取り可能な記憶媒体の一例である。ＲＡＭ１３０２は、外部記憶装置１３０７や記憶媒体ドライブ１３０８からロードされたコンピュータプログラムやデータ、Ｉ／Ｆ（インターフェース）１３０９を介して外部装置から受信したデータなどを一時的に記憶するためのエリアを有する。更に、ＲＡＭ１３０２は、ＣＰＵ１３０１が各種の処理を実行する際に用いるワークエリアを有する。即ち、ＲＡＭ１３０２は、各種のエリアを適宜提供することができる。ＲＯＭ１３０３は、コンピュータ読み取り可能な記憶媒体の一例であり、コンピュータの設定データや、ブートプログラムなどが格納されている。
【００５７】
キーボード１３０４、マウス１３０５は、コンピュータの操作者が操作することで、各種の指示をＣＰＵ１３０１に対して入力することができる。表示装置１３０６は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ１３０１による処理結果を画像や文字などをもって表示することができる。例えば、画像入力部１０１により入力されたラスタ画像を表示したり、メッシュ生成部１０６で決定された３頂点曲線メッシュ群を表示したりすることができる。
【００５８】
外部記憶装置１３０７は、コンピュータ読み取り記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置１３０７には、ＯＳ（オペレーティングシステム）や、図１に示した各部の機能をＣＰＵ１３０１に実現させるためのコンピュータプログラムが格納される。また、画像入力部１０１により入力されたラスタ画像のデータ、既知の情報として説明した情報等が格納される。外部記憶装置１３０７に保存されているコンピュータプログラムやデータは、ＣＰＵ１３０１による制御に従って適宜ＲＡＭ１３０２にロードされ、ＣＰＵ１３０１による処理対象となる。
【００５９】
記憶媒体ドライブ１３０８は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置１３０７やＲＡＭ１３０２に出力する。なお、外部記憶装置１３０７に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ１３０８に読み取らせても良い。
【００６０】
Ｉ／Ｆ１３０９は、外部装置をコンピュータに接続する為のものである。例えば、ディジタルカメラなど、ラスタ画像を取得するための装置を、このＩ／Ｆ１３０９に接続し、この装置から入力画像をＩ／Ｆ１３０９を介してＲＡＭ１３０２や外部記憶装置１３０７に取得するようにしても良い。１３１０は、上述の各部を繋ぐバスである。
【００６１】
このような構成において、コンピュータの電源がＯＮになると、ＣＰＵ１３０１はＲＯＭ１３０３に格納されているブートプログラムに従って、外部記憶装置１３０７からＯＳをＲＡＭ１３０２にロードする。この結果、キーボード１３０４、マウス１３０５を介した情報入力操作が可能となり、表示装置１３０６にＧＵＩを表示することが可能となる。ユーザが、キーボード１３０４やマウス１３０５を操作し、外部記憶装置１３０７に格納された画像処理用アプリケーションプログラムの起動指示を入力すると、ＣＰＵ１３０１はこのプログラムをＲＡＭ１３０２にロードし、実行する。これにより、コンピュータは上述の画像処理装置として機能することになる。
【００６２】
（第２実施形態）
＜概要＞
第２実施形態では、入力画像に対してエッジ抽出処理を行い、強エッジに基づいて第１の特徴点を設定し、画像のアクティビティに応じた領域細分割処理に基づいて第２の特徴点を設定する。これらの２種類の特徴点をメッシュの頂点に利用すると共に、第１の特徴点に対応する頂点には２色の色情報を割り当て、第２の特徴点に対応する頂点には１色の色情報を割り当てる。
【００６３】
＜装置構成および各部の動作＞
第２実施形態に係る画像処理装置の構成は第１実施形態に係る画像処理装置の構成（図１）と同様である。ただし、第２の特徴点設定部１０４における動作が第１実施形態とは異なる。そのため、以下では、第２実施形態とは異なる部分についてのみ主に説明する。
【００６４】
第２実施形態では、特徴線検出部１０２は、第１の特徴点設定部１０３で用いられる特徴線である強エッジのみを検出する。すなわち、エッジ検出部１０２−１は強エッジのエッジ画素のみ抽出する。そして、エッジ線構成部１０２−２は、抽出された強エッジ画素に基づいて特徴線（図３の画像３００ａ）を構成する。
【００６５】
一方、第２の特徴点設定部１０４は、以下で説明するように、入力画像内の各領域の”アクティビティ”に応じて入力画像を再帰的に細分割する。そして、細分割された領域サイズに対応させて第２の特徴点を設定することにより、第２の特徴点の配置密度を変化させる。ここで、画像の”アクティビティ”とは、画像内での局所的な変動量を表す。例えば、細分割領域内での勾配の大きさ、平均色からの分散や誤差などである。
【００６６】
図１４は、第２実施形態に係る第２の特徴点設定部１０４の処理を説明する図である。
【００６７】
まず、サンプリング点設定画像１４００ａに示すように、入力画像の四隅の頂点を色のサンプリング点として設定し、入力画像における対応する座標の色をサンプリングする。サンプリングした４頂点から生成される補間画像と入力画像との誤差を求め、誤差が閾値以上である場合、当該領域を４つの領域に細分割（サブディビジョン）する。第２実施形態では、細分化対象領域の中心を通るように等分に細分割することを想定するが、他の細分割方法を用いても構わない。
なお、補間画像は４頂点からの双一次補間で生成されることを想定するが、４頂点の色の平均値を補間画像とするなど他の補間画像生成方法を用いても構わない。また、ここでは、誤差の閾値としては色差を用いることを想定し、例えば、ＲＧＢ各２５６階調（８ビット階調）での平均色差”１０”を閾値として用いている。
【００６８】
補間画像と入力画像との誤差が閾値以上である場合、サンプリング点設定画像１４００ａは、サンプリング点設定画像１４００ｂに示されるように細分割される。そして、細分化により得られた４つの領域の各々の四隅に頂点を設定し、入力画像における対応する座標の色をサンプリングする。更に、４つの領域の各々について、サンプリングした４頂点から生成される補間画像と入力画像との誤差を求める。誤差が閾値以上である領域に対しては、更に細分割を行い、サンプリング点設定画像１４００ｂは、サンプリング点設定画像１４００ｃに示されるように細分割される。
【００６９】
同様に、再帰的に細分割化を繰り返し、すべての領域の誤差が設定した閾値内に収まったとき、細分割を終了する。サンプリング点設定画像１４００ｄは、細分割化処理が終了した状態を例示的に示す図である。このように設定された格子点が第２の特徴点として設定される。
【００７０】
すなわち、第２実施形態では、画像変動量（画像の”アクティビティ”）が相対的に大きい領域に対して、第２の特徴点を集中的に（高密度に）設定する。このように設定された第２の特徴点をメッシュの頂点として用いることにより、第１実施形態に比較し、画像の大域的な特徴を捉えたメッシュ群を生成することができる。
【００７１】
（第３実施形態）
＜概要＞
第３実施形態では、入力画像に対してエッジ抽出処理を行い、強エッジに基づいて第１の特徴点を設定し、抽出したエッジの強度、もしくは、抽出したエッジ周辺の濃度変化に基づいて第２の特徴点を設定する。これらの２種類の特徴点をメッシュの頂点に利用すると共に、第１の特徴点に対応する頂点には２色の色情報を割り当て、第２の特徴点に対応する頂点には１色の色情報を割り当てる。
【００７２】
＜装置構成および各部の動作＞
第３実施形態に係る画像処理装置の構成は第１実施形態に係る画像処理装置の構成（図１）と同様である。ただし、第２の特徴点設定部１０４における動作が第１実施形態、及び、第２実施形態とは異なる。そのため、以下では、第１及び第２実施形態とは異なる部分についてのみ主に説明する。
【００７３】
第３実施形態では、特徴線検出部１０２は、第１実施形態と同様に、第１の特徴点設定部１０３で用いられる特徴線である強エッジと、第２の特徴点設定部１０４で用いられる特徴線である弱エッジを検出する。すなわち、エッジ検出部１０２−１は強エッジのエッジ画素と弱エッジ画素とを抽出する。そして、エッジ線構成部１０２−２は、抽出された強エッジ画素と弱エッジ画素に基づいて、それぞれ特徴線、即ち、”強エッジ”（図３の画像３００ａ）と”弱エッジ”（図５の画像５００ａ）を構成する。ただし、第３実施形態においては、強エッジを、第１の特徴点設定部のみならず、第２の特徴点設定部でも用いる点が第１実施形態とは異なる。
【００７４】
第２の特徴点設定部１０４は、以下で説明するように、抽出したエッジの強度、もしくは、抽出したエッジ周辺の濃度変化に基づいて、特徴線の周囲に第２の特徴点を設定する。
【００７５】
図１５は、第３実施形態に係る第２の特徴点設定部１０４が実行する強エッジに対する処理を説明する図である。また、図１６は、第３実施形態に係る第２の特徴点設定部１０４が実行する弱エッジに対する処理を説明する図である。
【００７６】
画像１５００ａは強エッジ（図３の画像３００ａと同じ）を示したものであり、画像１５００ｂは第１の特徴点（図３の画像３００ｂと同じ）を黒丸で表わしたものである。また、画像１５００ｃでは、強エッジの周囲に設定された第２の特徴点を白抜き黒丸で表したものである。また、画像１６００ｂは（図５の画像５００ｂと同じ）は、弱エッジの特徴線を例示的に示している。ここで、弱エッジを示す画像５００ｂは、第１実施形態と同様、画像１５００ａ（強エッジのみ）と画像１６００ａ（強エッジと弱エッジ）との差分を導出することにより得られる。そして、画像１６００ｃは、規定のエッジ強度未満のエッジ線である弱エッジ線の周囲に設定された第２の特徴点を白抜き黒丸で表現したものである。
【００７７】
第２の特徴点設定部１０４は、画像１５００ｂに示される第１の特徴点の中で、同一特徴線上に存在しかつ隣接する第１の特徴点間に挟まれる特徴線の部分区間に着目する。部分区間のそれぞれに対し、それぞれの特徴線部分に対応する各画素におけるエッジ強度の平均値を求める。それぞれの特徴線部分に対して求めたエッジ強度の平均値を、予め指定されるｎ個の閾値に基づいて（ｎ＋１）段階に区分する。そして、それぞれの段階に応じた既定距離だけ、対応する部分区間の中間点から該中間点位置における特徴線の法線方向に離間した位置の画素を第２の特徴点として設定（サンプリング）する。尚、エッジ強度が低いほど、エッジの周囲での色変化が少ないものとして、より遠い距離にある位置に第２の特徴点設定し、エッジ強度が高いほど、エッジ周囲での色変化が急激であるとして、より近い距離に第２の特徴点を設定するのが好適である。
【００７８】
例えば、第１の特徴点１５０１と第１の特徴点１５０２との間に挟まれる部分区間に対しては、第２の特徴点１５０３と第２の特徴点１５０４とが設定される。これらは、当該部分区間の両側にそれぞれ１点ずつ設定される。同様に、第１の特徴点１５０５と第１の特徴点１５０６との間に挟まれる部分区間に対しては、第２の特徴点１５０７と第２の特徴点１５０８とが設定される。
【００７９】
ここで、画像１５００ｃにおいては、第１の特徴点１５０１と第１の特徴点１５０２との間に挟まれる部分区間の方が、第１の特徴点１５０５と第１の特徴点１５０６との間に挟まれる部分区間よりもエッジ強度の平均が高い場合を例示的に示している。そのため、第２の特徴点１５０３及び第２の特徴点１５０４は、第２の特徴点１５０７及び第２の特徴点１５０８よりも、対応する特徴線の部分区間のそれぞれの中間点により近い位置に設定されている。設定処理の結果、画像１５００ｃの白抜き黒丸で示されるような第２の特徴点が設定される。
【００８０】
閾値の個数ｎは例えば２であり（つまり３段階に区分）、既定距離は例えば、エッジ強度の低い段階から順に９，７，５画素とする。ここで、各部分区間のエッジ強度の平均値は、各部分区間を挟む両端の２つの第１の特徴点のエッジ強度の平均により設定しても良い。また、エッジ強度の代わりに、各部分区間の中間点から法線方向に並ぶ各画素の濃度を中間点から当該中間点より離れる方向に順次求め、濃度の変化に着目してもよい。この場合には、周辺画素における画素値（濃度）の変化の程度が予め定める閾値以下となる位置をもって第２の特徴点位置と定めるとよい。
【００８１】
尚、第２の特徴点設定部１０４は、画像１６００ｂに示される特徴線（弱エッジ）に対しても、第２の特徴点を設定する。例えば、特徴線に沿って、各特徴線上の各画素におけるエッジ強度の平均値を求める。求めたエッジ強度の平均値を、予め指定されるｍ個の閾値に基づいて（ｍ＋１）段階に区分する。そして、それぞれの段階に応じた既定距離だけ、当該部分区間の中間点から該中間点位置における特徴線の法線方向に離間した位置の画素を第２の特徴点として設定（サンプリング）する。例えば、弱エッジ１６０１に対しては、第２の特徴点１６０２と第２の特徴点１６０３とが設定される。これらもまた、当該弱エッジの両側にそれぞれ１点ずつ設定される。弱エッジの場合も、強エッジと同様に、エッジ強度が低いほどより遠い距離にある位置に設定し、エッジ強度が高いほどより近い距離に第２の特徴点を設定するのが好適である。
【００８２】
閾値の個数ｍは例えば１であり（つまり２段階に区分）、既定距離は例えば、エッジ強度の低い段階から順に４，３画素とする。これは、弱エッジ線上には第１の特徴点は存在しないため、第２の特徴点同士の間隔を、ほぼ強エッジ上の第１の特徴点と第２の特徴点との間隔と同等と見なしていることに相当する。ここで、各部分区間のエッジ強度の平均値は、それぞれの弱エッジ上の各画素のエッジ強度の平均により設定しても良い。また、強エッジの場合と同様に、エッジ強度の代わりに、各部分区間の中間点から法線方向に並ぶ各画素の濃度を中間点から当該中間点より離れる方向に順次求め、濃度の変化に着目してもよい。この場合も、周辺画素における画素値の変化の程度が予め定める閾値以下となる位置を第２の特徴点位置として設定するとよい。
【００８３】
図１７（ａ）は、上述の処理により得られた第１の特徴点及び第２の特徴点を、基となる強エッジ線及び弱エッジ線とともに示した図である。また、図１７（ｂ）は、第１の特徴点と第２の特徴点のみを示した図である。
【００８４】
尚、第３実施形態においては、第１の特徴点に近接した第２の特徴点が存在する場合に、当該第２の特徴点を削除するよう特徴点統合部１０５を構成しても良い。また、近接する複数の第２の特徴点が存在する場合に、これらの一部を削除するよう構成してもよい。例えば、所定距離以下（３画素以内）に第２の特徴点が２つ存在する場合、何れか一方の第２の特徴点を削除するとよい。
【００８５】
図１８は、上述の削除処理後における、第１の特徴点と第２の特徴点を合わせて示した図である。また、図１９は、入力画像に対して、メッシュ生成部１０６を経て生成される３頂点曲線メッシュ群１９００を表す図である。
【００８６】
上述のように、第３実施形態では、強エッジに基づく第１の特徴点と、エッジの強度、もしくは、抽出したエッジ周辺の濃度変化に基づく第２の特徴点との２種類の特徴点をメッシュの頂点に利用する例について説明した。このように設定された第２の特徴点をメッシュの頂点として用いることにより、第１実施形態や第２の実施形態に比較し、中間色帯の影響による色の滲みの発生を抑制することが可能となる。例えば、オブジェクト領域の境界付近には、多くの場合にエッジが存在し、それらに隣接してオブジェクト内部と外部の中間色となっている狭い遷移領域が付随することが多い。つまり、第３の実施形態においては、これらの遷移領域（中間色帯）による滲みの発生を抑制しつつ、より画像近似精度の良い効率的なメッシュ群を生成可能となる。
【００８７】
なお、上述の第３実施形態においては、第２の特徴点を設定する距離を決定する際に、エッジ強度閾値を利用して複数の段階に区分するものとして説明した。しかしながら、強エッジと弱エッジでそれぞれ既定の距離を１つずつ定めておき、これらの既定距離を用いて第２の特徴点を設定してもよい。例えば、既定距離を、例えば、強エッジに対しては７画素、弱エッジに対しては３画素と定めてもよい。これにより、処理負荷を低減することが出来、演算時間の短縮や回路規模の縮小が可能となる。
【００８８】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
0005888989.tif 000004
【図２】
0005888989.tif 000005
【図３】
0005888989.tif 000006
【図４】
0005888989.tif 000007
【図５】
0005888989.tif 000008
【図６】
0005888989.tif 000009
【図７】
0005888989.tif 000010
【図８】
0005888989.tif 000011
【図９】
0005888989.tif 000012
【図１０】
0005888989.tif 000013
【図１１】
0005888989.tif 000014
【図１２】
0005888989.tif 000015
【図１３】
0005888989.tif 000016
【図１４】
0005888989.tif 000017
【図１５】
0005888989.tif 000018
【図１６】
0005888989.tif 000019
【図１７】
0005888989.tif 000020
【図１８】
0005888989.tif 000021
【図１９】
0005888989.tif 000022