(57)【要約】【課題】実施形態によれば、使用するメモリ量をより少なくすることができる画像処理装置、方法、及びプログラムを提供することができる。【解決手段】分割部は、統合点の座標毎の変形コストのうち、最小の値を持つ変形コストが所定の閾値以上である場合に、仮想点を前記メッシュに挿入し、仮想点を含む前記三角形パッチを分割する。変形部は、統合点の座標毎の変形コストのうち、最小の値を持つ変形コストが所定の閾値未満である場合に、統合点を持つ稜線における仮想点の他端の頂点を、当該変形コストを持つ統合点の座標の位置に移動させ、三角形パッチを変形させる。【選択図】図１
2012048662.tif 000002
【特許請求の範囲】
【請求項１】
位置及び輝度で定義される仮想空間において、
入力されたピクセル画像の角のピクセルに対応する点を頂点とする、複数の三角形パッチを含むメッシュを生成する生成部と、
前記ピクセル画像の各ピクセルの輝度と、前記各ピクセルに対応する前記三角形パッチの輝度との差に基づいて、前記入力画像に対する前記三角形パッチの画質の近似度を算出し、さらに、前記差が最大となる最大ピクセルを算出する第１算出部と、
前記近似度が所定の閾値未満であるか否かを判定する第１判定部と、
前記近似度が所定の閾値未満である場合に、前記最大ピクセルの座標に、仮想の点である仮想点を挿入し、前記仮想点を含む前記三角形パッチの各頂点と、前記仮想点とを結ぶ稜線を生成し、前記稜線毎に、前記仮想点と前記頂点とを統合した点である統合点の座標を算出し、前記統合点の座標毎に、複数の三角形パッチとの距離に基づく変形コストを算出する第２算出部と、
前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値未満であるか否かを判定する第２判定部と、
前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値以上である場合に、前記仮想点を前記メッシュに挿入し、前記仮想点を含む前記三角形パッチを分割する分割部と、
前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値未満である場合に、前記統合点を持つ前記稜線における前記仮想点の他端の前記頂点を、当該変形コストを持つ前記統合点の座標の位置に移動させ、前記三角形パッチを変形させる変形部と
を備える画像処理装置。
【請求項２】
前記第２算出部は、
前記仮想空間において、前記稜線の端点である前記頂点を共有する、複数の前記三角形パッチに対する距離の総和が最小となる点を、前記統合点として算出する
請求項１記載の画像処理装置。
【請求項３】
前記第２算出部は、
前記仮想空間において、前記稜線の両端点である前記仮想点と前記頂点との中点を、前記統合点として算出する
請求項１記載の画像処理装置。
【請求項４】
前記分割部により分割された前記三角形パッチを含む前記メッシュ、又は、前記変形部により変形された前記三角形パッチを含むメッシュに含まれる一の前記三角形パッチの外接円が、他の前記三角形パッチの頂点を含まないように、前記メッシュを補正する補正部と、
前記メッシュを描画する描画部をさらに備える
請求項１乃至３記載の画像処理装置。
【請求項５】
生成部が、位置及び輝度で定義される仮想空間において、入力されたピクセル画像の角のピクセルに対応する点を頂点とする、複数の三角形パッチを含むメッシュを生成し、
第１算出部が、前記ピクセル画像の各ピクセルの輝度と、前記各ピクセルに対応する前記三角形パッチの輝度との差に基づいて、前記入力画像に対する前記三角形パッチの画質の近似度を算出し、さらに、前記差が最大となる最大ピクセルを算出し、
第１判定部が、前記近似度が所定の閾値未満であるか否かを判定し、
第２算出部が、前記近似度が所定の閾値未満である場合に、前記最大ピクセルの座標に、仮想の点である仮想点を挿入し、前記仮想点を含む前記三角形パッチの各頂点と、前記仮想点とを結ぶ稜線を生成し、前記稜線毎に、前記仮想点と前記頂点とを統合した点である統合点の座標を算出し、前記統合点の座標毎に、複数の三角形パッチとの距離に基づく変形コストを算出し、
第２判定部が、前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値未満であるか否かを判定し、
前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値以上である場合に、分割部が、前記仮想点を前記メッシュに挿入し、前記仮想点を含む前記三角形パッチを分割し、
前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値未満である場合に、変形部が、前記統合点を持つ前記稜線における前記仮想点の他端の前記頂点を、当該変形コストを持つ前記統合点の座標の位置に移動させ、前記三角形パッチを変形させる
画像処理方法。
【請求項６】
画像を編集するためにコンピュータを、
位置及び輝度で定義される仮想空間において、入力されたピクセル画像の角のピクセルに対応する点を頂点とする、複数の三角形パッチを含むメッシュを生成する手段と、
前記ピクセル画像の各ピクセルの輝度と、前記各ピクセルに対応する前記三角形パッチの輝度との差に基づいて、前記入力画像に対する前記三角形パッチの画質の近似度を算出し、さらに、前記差が最大となる最大ピクセルを算出する手段と、
前記近似度が所定の閾値未満であるか否かを判定する手段と、
前記近似度が所定の閾値未満である場合に、前記最大ピクセルの座標に、仮想の点である仮想点を挿入し、前記仮想点を含む前記三角形パッチの各頂点と、前記仮想点とを結ぶ稜線を生成し、前記稜線毎に、前記仮想点と前記頂点とを統合した点である統合点の座標を算出し、前記統合点の座標毎に、複数の三角形パッチとの距離に基づく変形コストを算出する手段と、
前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値未満であるか否かを判定する手段と、
前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値以上である場合に、前記仮想点を前記メッシュに挿入し、前記仮想点を含む前記三角形パッチを分割する手段と、
前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値未満である場合に、前記統合点を持つ前記稜線における前記仮想点の他端の前記頂点を、当該変形コストを持つ前記統合点の座標の位置に移動させ、前記三角形パッチを変形させる手段として
機能させるための画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、画像処理装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
写真等のピクセル画像を、三角形面等の幾何学形状であるパッチの集合であるメッシュを用いて近似した近似画像を作成することにより、解像度変換等の画像の加工を行ないやすくする画像処理方法がある。
【０００３】
このような画像処理方法では、ピクセル画像の各ピクセルの輝度に基づいて、輝度情報を持つ複数のパッチでピクセル画像を近似したメッシュを作成して描画する。
【０００４】
このような画像処理方法では、描画するためのメッシュのデータ量を少なくすることができるものが望まれている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第４２２００１０号公報
【非特許文献】
【０００６】
【非特許文献１】M. Garland and P. S. Heckbert, “Surface simplification using quadric error metrics” In Computer Graphics (Proc. SIGGRAPH 97), pages 209−216, ACM Press, New York, 1997
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明が解決しようとする課題は、描画するためのメッシュのデータ量を少なくすることができる画像処理装置、方法、及びプログラムを提供することである。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明の実施形態に係る画像処理装置は、生成部と、第１算出部と、第１判定部と、第２算出部と、第２判定部と、分割部と、変形部とを備える。生成部は、位置及び輝度で定義される仮想空間において、入力されたピクセル画像の角のピクセルに対応する点を頂点とする、複数の三角形パッチを含むメッシュを生成する。第１算出部は、前記ピクセル画像の各ピクセルの輝度と、前記各ピクセルに対応する前記三角形パッチの輝度との差に基づいて、前記入力画像に対する前記三角形パッチの画質の近似度を算出し、さらに、前記差が最大となる最大ピクセルを算出する。第１判定部は、前記近似度が所定の閾値未満であるか否かを判定する。第２算出部は、前記近似度が所定の閾値未満である場合に、前記最大ピクセルの座標に、仮想の点である仮想点を挿入し、前記仮想点を含む前記三角形パッチの各頂点と、前記仮想点とを結ぶ稜線を生成し、前記稜線毎に、前記仮想点と前記頂点とを統合した点である統合点の座標を算出し、前記統合点の座標毎に、複数の三角形パッチとの距離に基づく変形コストを算出する。第２判定部は、前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値未満であるか否かを判定する。前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値以上である場合に、分割部は、前記仮想点を前記メッシュに挿入し、前記仮想点を含む前記三角形パッチを分割する。前記統合点の座標毎の前記変形コストのうち、最小の値を持つ前記変形コストが所定の閾値未満である場合に、変形部は、前記統合点を持つ前記稜線における前記仮想点の他端の前記頂点を、当該変形コストを持つ前記統合点の座標の位置に移動させ、前記三角形パッチを変形させることを特徴とする。
【図面の簡単な説明】
【０００９】
【図１】第１の実施の形態に係る画像処理装置１の構成を表すブロック図。
【図２】画像処理装置１の処理を表すフローチャート。
【図３】第１の実施の形態における仮想空間を表す図。
【図４】第２算出部１０５による三角形パッチの分割の様子を表す概念図。
【図５】統合点Ｐｎを表す一例図。
【図６】変形部１０８による三角形パッチの変形を表す一例図。
【発明を実施するための形態】
【００１０】
以下、本発明の実施形態について図面を参照して詳細に説明する。
【００１１】
本願明細書と各図において、既出の図に関して前述したものと同様の要素には同一の符号を付して詳細な説明は適宜省略する。
【００１２】
（第１の実施の形態）
第１の実施の形態に係る画像処理装置１は、ピクセル座標（ｘ，ｙ）及び輝度Ｉｃで表現されるピクセル画像を、ピクセル座標（ｘ，ｙ）と輝度Ｉの座標系（ｘ，ｙ，Ｉ）で定義される仮想空間においてメッシュに変換し、描画するものである。
【００１３】
画像処理装置１は、ピクセル画像を基に、複数枚（例えば２枚）のパッチを含む初期のメッシュを生成する。画像処理装置１は、当該メッシュとピクセル画像とを比較し、新たに頂点を挿入してメッシュに含まれるパッチ数を増やすか、又は既存の頂点を移動させてメッシュを変形させるかを判定する。
【００１４】
これにより、パッチの数を抑制しながら、ピクセル画像と比較して画質劣化の少ないメッシュを生成する。
【００１５】
図１は、画像処理装置１の構成を表すブロック図である。画像処理装置１は、入力部１１と、処理部１２と、描画部１３と、記憶部３１とを備える。処理部１２は、生成部１０１と、評価部１０２と、第１算出部１０３と、第１判定部１０４と、第２算出部１０５と、第２判定部１０６と、分割部１０７と、変形部１０８と、補正部１０９とを含む。処理部１２は、ＣＰＵ及びＣＰＵが用いるメモリにより実現されてよい。記憶部３１は、ＣＰＵが用いるメモリにより実現されてよい。描画部１３は、ＧＰＵ及びＧＰＵが用いるメモリにより実現されてよい。
【００１６】
入力部１１は、ピクセル画像（入力画像）を入力する。入力画像は、各ピクセル（ｘ，ｙ）の各色成分ｃの輝度Ｉｃ（例えば、ｃ＝（Ｒ，Ｇ，Ｂ）である）を含むピクセルデータ（ｘ，ｙ，Ｉｃ）を持つ。記憶部３１は、入力部１１から得られる入力画像を記憶するとともに、生成されるメッシュを記憶する。本実施形態では、ピクセルの中心をピクセルのｘｙ座標として説明する。入力画像は、静止画や、動画の１フレームの画像を、ピクセルデータに変換した画像であってよい。
【００１７】
生成部１０１は、入力画像全体の角にあたるピクセルのピクセルデータを記憶部３１から読み出す。入力画像が四角形である場合、生成部１０１は、入力画像全体の４つの角（四隅）にある、一の色成分ｃのピクセルデータＰ１（ｘ１，ｙ１，Ｉｃ１）、Ｐ２（ｘ２，ｙ２，Ｉｃ２）、Ｐ３（ｘ３，ｙ３，Ｉｃ３）、Ｐ４（ｘ４，ｙ４，Ｉｃ４）を記憶部３１から読み出す。なお、本実施の形態では、入力画像が四角形である場合について説明する。
【００１８】
生成部１０１は、仮想空間において、入力画像全体の四隅のピクセルデータＰ１（ｘ１，ｙ１，Ｉｃ１）、Ｐ２（ｘ２，ｙ２，Ｉｃ２）、Ｐ３（ｘ３，ｙ３，Ｉｃ３）、Ｐ４（ｘ４，ｙ４，Ｉｃ４）を頂点にする。
【００１９】
生成部１０１は、頂点Ｐ１〜Ｐ４のうち、対角に位置する２組の頂点（例えば、Ｐ１とＰ３、Ｐ２とＰ４）の輝度Ｉｃの差が小さい方の頂点間を結ぶ稜線を生成する。
【００２０】
生成部１０１は、稜線の両端点である２つ頂点と、他の２つの頂点とを結ぶ稜線を生成し、２枚の三角形パッチを含む初期のメッシュを生成する。メッシュは、各頂点の座標の情報と、各頂点間の稜線の接続関係（例えば、頂点Ｐ１は頂点Ｐ２、Ｐ３、Ｐ４と稜線で接続される）を表す情報とを含むデータにより、表現することができる。
【００２１】
また、生成部１０１は、各頂点の識別番号である「頂点ＩＤ」を、各頂点に付与してよい。各稜線の識別番号である「稜線ＩＤ」を、各稜線に付与してよい。各三角形パッチの識別番号である「パッチＩＤ」を、各三角形パッチに付与してよい。生成部１０１は、初期のメッシュを記憶部３１に書き込む。生成部１０１は、一の三角形パッチを、位置（ｘ，ｙ）における輝度Ｉ（ｘ，ｙ）で表現される面の式により表わされてよい。
【００２２】
評価部１０２は、メッシュに含まれる全ての三角形パッチの近似度Ｓ（後述）が算出されたかを評価する。
【００２３】
第１算出部１０３は、近似度Ｓが算出されていない一の三角形パッチ（例えば、パッチＩＤ＝１）を記憶部３１から選択して読み出す。
【００２４】
第１算出部１０３は、入力画像のピクセルデータ（ｘ，ｙ，Ｉｃ）を記憶部３１から読み出す。このとき、第１算出部１０３は、当該三角形パッチにｘｙ座標が含まれる部分のピクセルデータ（ｘ，ｙ，Ｉｃ）を記憶部３１から読み出す。
【００２５】
第１算出部１０３は、入力画像におけるピクセルデータ（ｘ，ｙ，Ｉｃ）の輝度Ｉｃと、ｘｙ座標が一致する三角形パッチ上の点にあたる輝度Ｉ（ｘ，ｙ）との差をピクセルデータ毎に求める。第１算出部１０３は、当該差に基づいて、三角形パッチが近似する部分の入力画像に対する、三角形パッチの画質の近似の程度を表す近似度Ｓを算出する。
【００２６】
第１算出部１０３は、近似度Ｓを算出する際に、三角形パッチとの輝度の差が最大となる入力画像のピクセルデータ（最大ピクセルデータと呼ぶ）Ｐｓ（ｘｓ，ｙｓ，Ｉｃｓ）を求める。第１算出部１０３は、近似度Ｓと最大ピクセルデータＰｓとを第１判定部１０４に供給する。
【００２７】
第１判定部１０４は、近似度Ｓが所定の閾値未満か否かを判定する。近似度Ｓが所定の閾値未満の場合、第１判定部１０４は、座標Ｐｓ（ｘｓ，ｙｓ，Ｉｃｓ）を第２算出部１０５に通知する。近似度Ｓが所定の閾値未満の場合、第１判定部１０４は、評価部１０２に上述した評価を行なうよう通知する。
【００２８】
第２算出部１０５は、メッシュを記憶部３１から読み出す。第２算出部１０５は、メッシュおける座標Ｐｓに仮想の点である仮想点を挿入する（以降、仮想点Ｐｓと呼ぶ）。
【００２９】
第２算出部１０５は、仮想点Ｐｓと、仮想点Ｐｓを含む三角形パッチの各頂点とを結ぶ３本の稜線を生成し、三角形パッチを分割する。第２算出部１０５は、それとともに、分割前の三角形パッチをメッシュから除去する。
【００３０】
第２算出部１０５は、稜線毎に、稜線の両端の点（仮想点Ｐｓと一の頂点）を一つに統合した点である統合点Ｐｎ（ｎ＝１，２，３）の座標を求める。詳しくは後述する。第２算出部１０５は、稜線毎に、他の三角形パッチに対する統合点Ｐｎの距離の総和を表す「変形コスト」を算出する。詳しくは後述する。第２算出部１０５は、稜線毎の変形コストを第２判定部１０６に供給する。
【００３１】
第２判定部１０６は、稜線毎に算出された変形コストのうち、最小の値を持つ変形コストが、予め定められた所定の閾値未満であるか否かを判定する。変形コストが所定の閾値以上である場合、第２判定部１０６は、仮想点Ｐｓの座標（ｘｓ，ｙｓ，Ｉｃｓ）を分割部１０７に通知する。
【００３２】
分割部１０７は、記憶部３１からメッシュを読み出す。分割部１０７は、通知された仮想点Ｐｓをメッシュに挿入し、仮想点Ｐｓと、仮想点Ｐｓを含む三角形パッチの各頂点とを稜線で結び、三角形パッチを分割する。分割部１０７は、それとともに、分割前の三角形パッチをメッシュから除去する。
【００３３】
変形コストが所定の閾値未満である場合、第２判定部１０６は、３本の稜線の中で、最小の変形コストを持つ稜線の端点のうち、仮想点Ｐｓに対して他端の頂点の頂点ＩＤと、当該稜線に対応する統合点Ｐｎの座標とを変形部１０８に通知する。
【００３４】
変形部１０８は、記憶部３１からメッシュを読み出す。変形部１０８は、通知された頂点ＩＤを持つ頂点を、通知された統合点の座標に移動させ、三角形パッチを変形させる。
【００３５】
補正部１０９は、分割部１０７により分割されたメッシュ、又は、変形部１０８により変更されたメッシュに含まれる複数の三角形パッチがＤｅｌａｕｎａｙ三角形分割の規則に従うようにメッシュの稜線をスワップさせ、メッシュを補正する。なおこの時、メッシュの境界にあたる稜線については、スワップを行わないこととしても良い。Ｄｅｌａｕｎａｙ三角形分割とは、各三角形の外接円が他の点を内部に含まない三角形に分割することをいう。
【００３６】
補正部１０９は、補正したメッシュを記憶部３１に書き込むことにより、メッシュを更新する。
【００３７】
描画部１３は、メッシュを描画する。
【００３８】
図２は、画像処理装置１の処理を表すフローチャートである。
【００３９】
入力部１１は、ピクセル画像（入力画像）を入力する（Ｓ２０１）。入力部１１は、入力画像を記憶部３１に書き込む。
【００４０】
生成部１０１は、初期のメッシュを生成する（Ｓ２０２）。図３は、本実施の形態における仮想空間を表す図である。本実施形態では、図３（ａ）に示すように、生成部１０１は、入力画像全体の四隅にある、一の色成分ｃのピクセルデータＰ１（ｘ１，ｙ１，Ｉｃ１）、Ｐ２（ｘ２，ｙ２，Ｉｃ２）、Ｐ３（ｘ３，ｙ３，Ｉｃ３）、Ｐ４（ｘ４，ｙ４，Ｉｃ４）を記憶部３１から読み出し、仮想空間における頂点とする。
【００４１】
生成部１０１は、頂点Ｐ１〜Ｐ４のうち、対角に位置する２組の頂点の輝度Ｉｃの差（絶対値）を計算する（Ｓ２０３）。例えば、頂点Ｐ１と頂点Ｐ３とから、頂点Ｐ１の輝度と頂点Ｐ３の輝度の差α＝｜Ｉｃ１−Ｉｃ３｜を計算する。頂点Ｐ２と頂点Ｐ４とから、頂点Ｐ２の輝度と頂点Ｐ４の輝度の差β＝｜Ｉｃ２−Ｉｃ４｜を計算する。
【００４２】
生成部１０１は、αとβを比較し、輝度の差が小さい方の頂点間を結ぶ稜線Ｌ０を生成する。生成部１０１は、当該稜線の両端の頂点と他の頂点とを結ぶ稜線を生成することにより、２枚の三角形パッチを含む初期のメッシュを生成する。
【００４３】
例えば、α＜βであるとき、生成部１０１は、図３（ｂ）に示すように、頂点Ｐ１と頂点Ｐ３とを結ぶ稜線Ｌ０を生成する。生成部１０１は、稜線Ｌ０の両端の頂点（頂点Ｐ１及び頂点Ｐ３）と、他の頂点（頂点Ｐ２及び頂点Ｐ４）とを結ぶ稜線（稜線Ｌ１、Ｌ２、Ｌ３、Ｌ４）を生成することにより、２枚の三角形パッチを含む初期のメッシュを生成する。生成部１０１は、初期のメッシュを記憶部３１に書き込む。
【００４４】
評価部１０２は、メッシュに含まれる全ての三角形パッチの近似度Ｓが算出されたかを評価する（Ｓ２０３）。例えば、パッチＩＤ毎に近似度Ｓが算出されたことを示すフラグを設け、記憶部３１に記憶しておき、評価部１０２は、当該フラグを用いてステップＳ２０３における評価を行ってもよい。
【００４５】
ステップＳ２０３における判定がＮＯの場合、第１算出部１０３は、近似度Ｓが算出されていない一の三角形パッチ（例えば、パッチＩＤ＝１）を記憶部３１から選択して読み出す（Ｓ２０４）。第１算出部１０３は、当該三角形パッチのｘｙ座標に、ピクセル座標（ｘ，ｙ）が対応する部分の、入力画像のピクセルデータ（ｘ，ｙ，Ｉｃ）を記憶部３１から読み出す。
【００４６】
第１算出部１０３は、入力画像におけるピクセルデータ（ｘ，ｙ，Ｉｃ）の輝度Ｉｃと、ｘｙ座標が一致する三角形パッチ上の点にあたる輝度Ｉ（ｘ，ｙ）との差をピクセルデータ毎に求める。第１算出部１０３は、当該差に基づいて、三角形パッチが近似する部分の入力画像に対する、三角形パッチの近似度Ｓを算出する（Ｓ２０５）。
【００４７】
第１算出部１０３は、近似度Ｓを算出する際に、三角形パッチとの輝度の差が最大となる入力画像のピクセルデータ（最大ピクセルデータと呼ぶ）Ｐｓ（ｘｓ，ｙｓ，Ｉｃｓ）を求める。
【００４８】
例えば、第１算出部１０３は、ピクセルの輝度Ｉｃ（ｘ，ｙ）と、三角形パッチの輝度Ｉ（ｘ，ｙ）との差「Ｉ（ｘ，ｙ）−Ｉｃ（ｘ，ｙ）」をピクセル毎に算出してよい。このとき、第１算出部１０３は、最大ピクセルデータＰｓ（ｘｓ，ｙｓ，Ｉｃｓ）を求める。第１算出部１０３は、輝度の差「Ｉ（ｘ，ｙ）−Ｉｃ（ｘ，ｙ）」を用いて近似度Ｓを算出してよい。第１算出部１０３は、例えば、式１を用いて近似度Ｓを算出してよい。
【数１】
2012048662.tif 000003
【００４９】
式１におけるＴは、三角形パッチのｘｙ座標に含まれるピクセルに対して「Ｉ（ｘ，ｙ）−Ｉｃ（ｘ，ｙ）」の２乗和を計算することを示している。
【００５０】
なお、本実施形態において、第１算出部１０３は、以上のようにして近似度Ｓを算出したが、これに限られない。第１算出部１０３は、入力画像に対する三角形パッチの画質を評価することができる手法であれば、いかなる手法を用いて近似度Ｓを算出しても構わない。
【００５１】
第１算出部１０３は、近似度Ｓと最大ピクセルデータＰｓとを第１判定部１０４に供給する。第１判定部１０４は、近似度Ｓが所定の閾値未満か否かを判定する（Ｓ２０６）。近似度Ｓが所定の閾値未満の場合、第１判定部１０４は、座標Ｐｓ（ｘｓ，ｙｓ，Ｉｃｓ）を第２算出部１０５に通知する。
【００５２】
図４は、第２算出部１０５による三角形パッチの分割の様子を表す概念図である。なお、ここからは説明のため、三角形パッチの枚数が６枚のメッシュに対する処理を説明する。
【００５３】
第２算出部１０５は、メッシュを記憶部３１から読み出す。第２算出部１０５は、メッシュにおける座標Ｐｓに仮想の点である仮想点Ｐｓを挿入する（Ｓ２０７）（図４（ａ））。
【００５４】
第２算出部１０５は、仮想点Ｐｓと、仮想点Ｐｓを含む三角形パッチの各頂点とを結ぶ３本の稜線（稜線Ｌ’１、Ｌ’２、Ｌ’３）を生成し、三角形パッチを分割する（Ｓ２０８）（図４（ｂ））。第２算出部１０５は、それとともに、分割前の三角形パッチをメッシュから除去する。
【００５５】
第２算出部１０５は、稜線毎に、稜線の両端の点（仮想点Ｐｓと一の頂点）を一つに統合した点である統合点Ｐｎ（ｎ＝１，２，３）の座標を算出する（Ｓ２０９）。
【００５６】
なお、第２算出部１０５は、仮想点Ｐｓを含む三角形パッチと、少なくとも一の頂点を共有する複数の三角形パッチのみを記憶部３１から読み出してもよい。
【００５７】
図５は、統合点Ｐｎを表す一例図である。図５（ａ）は、仮想点Ｐｓを挿入して、三角形パッチを分割したメッシュを表す（図４（ｂ）と同様）。図５（ｂ）は、稜線Ｌ’１の両端の点である仮想点Ｐｓと点Ｐ６とから算出した統合点Ｐ１を表す図である。
【００５８】
統合点Ｐｎは、統合点Ｐｎに対して稜線の他端をなす頂点を共有する、他の三角形パッチとの距離の総和が最小となる点として算出されてよい。ここでいう「三角形パッチとの距離」とは、ある三角形パッチを無限平面とした場合に、統合点Ｐｎから当該無限平面に下ろした垂線の長さをいう。例えば、統合点Ｐ１は、稜線Ｌ’１の他端をなす頂点Ｐ６を共有する、三角形パッチＰ１Ｐ２Ｐ６、三角形パッチＰ２Ｐ３Ｐ６、三角形パッチＰ３Ｐ５Ｐ６に対する、各々の距離の総和（本実施形態では、これを「変形コスト」と定義する）が最小となる点として算出される。なお、ある稜線において、統合点Ｐｎに対する他端の点が、入力画像の最も外側のピクセルに対応する頂点（例えば、図５における頂点Ｐ１〜Ｐ４）である場合は、統合点Ｐｎは当該最も外側のピクセルに対応する頂点にしてよい。
【００５９】
なお、統合点Ｐｎの算出方法は、以上に述べた方法でなくてもよい。例えば、稜線の中点を統合点としてもよい。また、変形コストについても、以上に述べた方法でなくてもよい。例えば、稜線の両端点に隣接する三角形パッチの近似度Ｓの平均値と、評価対象とする三角形パッチを分割せずに、統合点Ｐｎに対応する頂点を移動した後にその頂点に隣接する三角形パッチの近似度Ｓの平均値とを求め、それらの差の絶対値を変形コストとしてもよい。また、例えば、非特許文献１記載の手法を用いることもできる。
【００６０】
第２判定部１０６は、稜線毎に算出された変形コストのうち、最小の値を持つ変形コストが、予め定められた所定の閾値未満であるか否かを判定する（Ｓ２１０）。
【００６１】
ステップＳ２１０における判定がＮＯの場合、第２判定部１０６は、仮想点Ｐｓの座標（ｘｓ，ｙｓ，Ｉｃｓ）を分割部１０７に通知する。
【００６２】
分割部１０７は、記憶部３１からメッシュを読み出す。分割部１０７は、図４と同様に、通知された仮想点Ｐｓを読み出したメッシュに挿入する。分割部１０７は、仮想点Ｐｓと、仮想点Ｐｓを含む三角形パッチの各頂点とを稜線で結び、三角形パッチを分割する（Ｓ２１１）。分割部１０７は、それとともに、分割前の三角形パッチをメッシュから除去する。
【００６３】
ステップＳ２１０における判定がＹＥＳの場合、第２判定部１０６は、３本の稜線の中で、最小の変形コストを持つ稜線の端点のうち、仮想点Ｐｓでない方の頂点の頂点ＩＤと、当該稜線に対応する統合点Ｐｎの座標とを変形部１０８に通知する。
【００６４】
変形部１０８は、記憶部３１からメッシュを読み出す。変形部１０８は、通知された頂点ＩＤを持つ頂点を、通知された統合点の座標に移動し、三角形パッチを変形させる（Ｓ２１２）。図６は、変形部１０８による三角形パッチの変形を表す一例図である。例えば、図５において、統合点Ｐ１の変形コストが所定の閾値未満の場合、変形部１０８は、頂点Ｐ６を統合点Ｐ１の座標まで移動させ、三角形パッチを変形させる。
【００６５】
補正部１０９は、分割部１０７により分割されたメッシュ、又は、変形部１０８により変更されたメッシュに含まれる複数の三角形パッチがＤｅｌａｕｎａｙ三角形分割の規則に従うようにメッシュの稜線をスワップさせ、メッシュを補正する（Ｓ２１３）。補正部１０９は、補正したメッシュを記憶部３１に書き込むことにより、メッシュを更新する。このとき、補正部１０９は、更新したメッシュに対して、頂点ＩＤ、稜線ＩＤ、パッチＩＤを割り当て直しても構わない。その後、ステップＳ２０３に遷移する。
【００６６】
ステップＳ２０３における判定がＹＥＳの場合、描画部１３は、記憶部３１からメッシュを読み出し、メッシュを描画する（Ｓ２１４）。描画部１３は、表示すべき画像の大きさに応じて、メッシュをｘ軸及びｙ軸方向に拡大・縮小してよい。なお、描画部１３は、コンピュータ・グラフィックスの分野における公知の手法を用いて、メッシュを描画してよい。
【００６７】
（第２の実施の形態）
本実施の形態の変形例における画像処理装置は、入力画像がＲＧＢの色成分を持つカラー画像である場合に、各色成分の輝度Ｉｃではなく、輝度信号Ｙを用いてメッシュを作成する点が異なる。
【００６８】
入力画像がＲＧＢの色成分を持つカラー画像である場合、入力部１１は、入力画像の色成分ＲＧＢを輝度信号Ｙに変換し、記憶部３１に記憶する。その後の処理（ステップＳ２０２〜Ｓ２１３）は、同様に行う。
【００６９】
描画部１３は、記憶部３１から入力画像を読み出し、入力画像の色成分ＲＧＢと、メッシュの輝度信号Ｙとに基づいて、メッシュを描画する。
【００７０】
これにより、色成分毎にメッシュを作成する処理コスト及びメモリの使用量を少なくすることができる。
【００７１】
以上、上述した実施の形態により、パッチの数を抑制しながら、ピクセル画像と比較して画質劣化の少ないメッシュを生成する。パッチの数を抑制することにより、メモリ使用量を抑えることができる。
【００７２】
これまで、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７３】
１  画像処理装置
１１  入力部
１２  処理部
１３  描画部
３１  記憶部
１０１  生成部
１０２  評価部
１０３  第１算出部
１０４  第１判定部
１０５  第２算出部
１０６  第２判定部
１０７  分割部
１０８  変形部
１０９  補正部
【図１】
2012048662.tif 000004
【図２】
2012048662.tif 000005
【図３】
2012048662.tif 000006
【図４】
2012048662.tif 000007
【図５】
2012048662.tif 000008
【図６】
2012048662.tif 000009