(57)【特許請求の範囲】
【請求項１】
３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストを計算する曲率コスト計算部と、
前記３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストを計算する経路長コスト計算部と、
前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストを計算する２点間コスト計算部と、
前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列を特徴頂点列として生成する特徴頂点列生成部と
を含む画像処理装置。
【請求項２】
前記曲率コスト、および前記経路長コストのそれぞれに付加する重みを設定する重み設定部をさらに含み、
前記２点間コスト計算部は、前記曲率コスト、および前記経路長コストに対して、前記重み設定部により設定された重みを付加して、前記３次元形状内における所定の２点間の経路におけるコストを計算する
請求項１に記載の画像処理装置。
【請求項３】
前記特徴頂点列を構成する点の数を間引いて簡略化するための割合を設定する簡略化割合設定部と、
前記特徴頂点列生成部により求められた特徴頂点列の点の数を、前記簡略化割合設定部により設定された割合で間引くことにより前記特徴頂点列を簡略化する簡略化部をさらに含む
請求項１に記載の画像処理装置。
【請求項４】
前記特徴頂点列生成部により生成された、前記３次元形状における、前記特徴頂点列を構成する点を選択することにより、前記特徴頂点列を編集する編集部をさらに含む
請求項１に記載の画像処理装置。
【請求項５】
３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストを計算する曲率コスト計算部と、
前記３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストを計算する経路長コスト計算部と、
前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストを計算する２点間コスト計算部と、
前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列を特徴頂点列として生成する特徴頂点列生成部と
を含む画像処理装置の画像処理方法において、
前記曲率コスト計算部における、前記３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストを計算する曲率コスト計算ステップと、
前記経路長コスト計算部における、前記３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストを計算する経路長コスト計算ステップと、
前記２点間コスト計算部における、前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストを計算する２点間コスト計算ステップと、
前記特徴頂点列生成部における、前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列を特徴頂点列として生成する特徴頂点列生成ステップと
を含む画像処理方法。
【請求項６】
３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストを計算する曲率コスト計算ステップと、
前記３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストを計算する経路長コスト計算ステップと、
前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストを計算する２点間コスト計算ステップと、
前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列を特徴頂点列として生成する特徴頂点列生成ステップと
を含む処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、画像処理装置および方法、並びにプログラムに関し、特に、特徴的な頂点からなる特徴頂点列を容易で、かつ、適切に選択できるようにした画像処理装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
形状の頂点選択は、３次元形状データを編集する上で重要な基本動作の一つである。特に、リッジ（ridge）のような特徴線に沿った頂点列の選択は、形状の変形操作に重要な操作であり、形状を作成する際やアニメーションを作成する上で必要な手順である。
【０００３】
３次元形状全体の特徴線を抽出する手法として、例えば、３次元の物体のスキャンデータ(造形データ)を用いて、予め複数の３次元物体形状の曲面のパラメータを保持し、計測結果に類似したものを利用する手法が提案されている（特許文献１参照）。ここでは、３次元の物体の計測結果を用いる場合について提案されたものであるが、３次元形状データに当てはめて利用することで、同様の効果を奏することが可能である。
【０００４】
また、一般的なソフトウェアにおいては、例えば、頂点列を選択するにあたり１点１点選択する手法、閉領域の頂点を選択する手法、およびペイントにより選択する手法の３種類の手法が主に使用されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平０８−０３０８０９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した形状の作成やアニメーションの作成といった３次元形状を編集するような場合、形状全体の特徴線を抽出することはできるものの、使用者の意図に沿って局所的に特徴的な頂点列を選択するためには、１点１点手作業で選択するしかなく、形状編集に膨大な作業量と作業時間が費やされている。
【０００７】
本技術はこのような状況に鑑みてなされたものであり、特に、与えられた３次元形状の特徴的な頂点を使用者の入力に基づいて選択することで、３次元形状の特徴線に沿った頂点列の選択を容易で、かつ適切に実現できるようにするものである。
【課題を解決するための手段】
【０００８】
本技術の一側面の画像処理装置は、３次元形状を構成する頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストを計算する曲率コスト計算部と、前記３次元形状を構成する頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストを計算する経路長コスト計算部と、前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストを計算する２点間コスト計算部と、前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列を特徴頂点列として生成する特徴頂点列生成部とを含む。
【０００９】
前記曲率コスト、および前記経路長コストのそれぞれに付加する重みを設定する重み設定部をさらに含ませるようにすることができ、前記２点間コスト計算部には、前記曲率コスト、および前記経路長コストに対して、前記重み設定部により設定された重みを付加して、前記３次元形状内における所定の２点間の経路におけるコストを計算させるようにすることができる。
【００１０】
前記特徴頂点列を構成する点の数を間引いて簡略化するための割合を設定する簡略化割合設定部と、前記特徴頂点列生成部により求められた特徴頂点列の点の数を、前記簡略化割合設定部により設定された割合で間引くことにより前記特徴頂点列を簡略化する簡略化部をさらに含ませるようにすることができる。
【００１１】
前記特徴頂点列生成部により生成された、前記３次元形状における、前記特徴頂点列を構成する点を選択することにより、前記特徴頂点列を編集する編集部をさらに含ませるようにすることができる。
【００１２】
本技術の一側面の画像処理方法は、３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストを計算する曲率コスト計算部と、前記３次元形状を構成するための頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストを計算する経路長コスト計算部と、前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストを計算する２点間コスト計算部と、前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列を特徴頂点列として生成する特徴頂点列生成部とを含む画像処理装置の画像処理方法において、前記曲率コスト計算部における、前記３次元形状を構成する頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストを計算する曲率コスト計算ステップと、前記経路長コスト計算部における、前記３次元形状を構成する頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストを計算する経路長コスト計算ステップと、前記２点間コスト計算部における、前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストを計算する２点間コスト計算ステップと、前記特徴頂点列生成部における、前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列を特徴頂点列として生成する特徴頂点列生成ステップとを含む。
【００１３】
本技術の一側面のプログラムは、３次元形状を構成する頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストを計算する曲率コスト計算ステップと、前記３次元形状を構成する頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストを計算する経路長コスト計算ステップと、前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストを計算する２点間コスト計算ステップと、前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列を特徴頂点列として生成する特徴頂点列生成ステップとを含む処理をコンピュータに実行させる。
【００１４】
本技術の一側面においては、３次元形状を構成する頂点、辺、および面からなる形状情報に基づいて、前記各辺の曲率に基づいた曲率コストが計算され、前記３次元形状を構成する頂点、辺、および面からなる形状情報に基づいて、前記各辺における経路長に基づいた経路長コストが計算され、前記曲率コスト、および前記経路長コストに基づいて、前記３次元形状内における所定の２点間の経路におけるコストが計算され、前記３次元形状における、前記所定の２点間のコストが最小となる、前記所定の２点間の経路上に存在する点からなる列が特徴頂点列として生成される。
【００１５】
本技術の一側面の画像処理装置は、独立した装置であっても良いし、画像処理を行うブロックであっても良い。
【発明の効果】
【００１６】
本技術の一側面によれば、３次元形状における特徴頂点列を容易で、かつ、適切に選択することが可能となる。
【図面の簡単な説明】
【００１７】
【図１】本技術を適用した特徴頂点列選択装置の一実施の形態の構成例を示す図である。
【図２】特徴頂点列選択処理を説明するフローチャートである。
【図３】表示部に表示される表示画像の例を説明する図である。
【図４】曲率コスト計算処理を説明するフローチャートである。
【図５】経路長コスト計算処理を説明するフローチャートである。
【図６】特徴頂点列生成処理を説明するフローチャートである。
【図７】重みつまみの操作を説明するための表示画像の例を説明する図である。
【図８】特徴頂点列簡略化処理を説明するフローチャートである。
【図９】簡略化割合つまみの操作を説明するための表示画像の例を説明する図である。
【図１０】特徴頂点列編集処理を説明するフローチャートである。
【図１１】外形形状の変形操作を説明するための表示画像の例を説明する図である。
【図１２】汎用のパーソナルコンピュータの構成例を説明する図である。
【発明を実施するための最良の形態】
【００１８】
＜特徴頂点選択装置の構成例＞
図１は、本技術を適用した特徴頂点選択装置の一実施の形態の構成例を示している。図１の特徴頂点選択装置１１は、３次元形状におけるオブジェクトの曲率に基づいて、使用者より入力される２点間において、リッジ（ridge）を構成する頂点の配列からなる特徴頂点列を容易で、かつ、適切に選択できるようにするものである。
【００１９】
より具体的には、特徴頂点列選択装置１１は、３Ｄ（３次元）形状データ記憶部３１、曲率コスト計算部３２、経路長コスト計算部３３、特徴頂点列生成部３４、表示部３５、特徴頂点列簡略化部３６、操作部３７、始点終点入力部３８、コスト重み入力部３９、および簡略化割合入力部４０を備えている。
【００２０】
３Ｄ形状データ記憶部３１は、３次元形状を構成する点、辺、および面を配置するために必要とされるデータが記憶されている。すなわち、例えば、点であれば３次元空間内におけるオブジェクトを構成するための座標位置のデータであり、辺であれば、３次元空間内におけるオブジェクトを構成するための線分を定義する直線を表現する点と点の接続情報のデータであり、面であれば、３次元空間内におけるオブジェクトを構成するための面を定義する辺、点の接続情報のデータなどである。
【００２１】
曲率コスト計算部３２は、３Ｄ形状データ記憶部３１に記憶された３次元形状を構成する点、辺、および面を配置するために必要とされるデータに基づいて、LCD（Liquid Crystal Display）などのディスプレイなどからなる表示部３５に表示される（表現される）３次元空間内に表示される各点を接続する辺における曲率コストを計算し、計算結果を特徴頂点列生成部３４に供給する。曲率コストとは、例えば、曲率そのものの値であってもよいし、曲率に基づいて所定の関数等により計算される値でもよい。
【００２２】
経路長コスト計算部３３は、３Ｄ形状データ記憶部３１に記憶された３次元形状を構成する点、辺、および面を配置するために必要とされるデータに基づいて、LCDなどのディスプレイなどからなる表示部３５に表示される（表現される）３次元空間内に表示される各点を接続する辺における経路長コストを計算し、計算結果を特徴頂点列生成部３４に供給する。経路長コストとは、例えば、経路長そのものの値であってもよいし、経路長に基づいて所定の関数等により計算される値でもよい。
【００２３】
操作部３７は、マウスやキーボード、または操作ボタンなど、使用者からの入力を受け付けるとともに、受け付けた操作内容に対応する操作信号を、始点終点入力部３８、コスト重み入力部３９、または簡略化割合入力部４０に供給する。
【００２４】
始点終点入力部３８は、操作部３７からの操作信号に基づいて、特徴頂点列を求めるべき始点の座標位置、および終点の座標位置の情報の入力を受け付け、受け付けた始点、および終点の座標情報を特徴頂点列生成部３４に供給する。
【００２５】
コスト重み入力部３９は、操作部３７からの操作信号に基づいて、曲率コスト、および経路長コストのそれぞれに割り付けられる重みの情報の入力を受け付けて、入力を受け付けた重みの情報を特徴頂点列生成部３４に供給する。より詳細には、コスト重み入力部３９は、スライダーバー表示制御部３９ａを備えており、操作部３７が操作されて、ポインタが横方向（左右方向）に所定の距離だけドラッグされると、スライダーバー表示制御部３９ａは、ポインタを利用した重みを入力するためのスライダーバーを表示部３５に表示する。さらに、コスト重み入力部３９は、スライダーバー表示制御部３９ａにより表示部３５に表示されたスライダーバーがポインタにより操作されると操作内容に応じた重みの情報の入力を受け付ける。
【００２６】
簡略化割合入力部４０は、操作部３７からの操作信号に基づいて、簡略化の割合を設定する簡略化割合の入力情報を受け付けて、受け付けた簡略化割合の情報を特徴頂点列生成部３４に供給する。より詳細には、簡略化割合入力部４０は、スライダーバー表示制御部４０ａを備えており、操作部３７が操作されて、ポインタが縦方向（上下方向）に所定の距離だけドラッグされると、スライダーバー表示制御部４０ａは、ポインタを利用した簡略化割合を入力するためのスライダーバーを表示部３５に表示する。さらに、簡略化割合入力部４０は、スライダーバー表示制御部４０ａにより表示部３５に表示されたスライダーバーがポインタにより操作されると操作内容に応じた簡略化割合の情報の入力を受け付ける。
【００２７】
特徴頂点列生成部３４は、コスト計算部３４ａを備えており、始点終点入力部３８より供給される始点、および終点間の曲率コスト計算部３２より供給される曲率コストと、経路長コスト計算部３３により供給される経路長コストとに、コスト重みとして指定された重みを付して、コスト計算部３４ａのコスト計算方法を更新して、計算されるコストの和が最小となる経路を計算し、計算された経路上に存在する点により構成される列からなる特徴頂点列を計算し、特徴頂点列簡略化部３６に供給する。
【００２８】
特徴頂点列簡略化部３６は、特徴頂点列の情報に含まれる特徴頂点列より、簡略化割合の情報に基づいて、特徴頂点を等間隔に間引いて、間引いた結果となる特徴頂点列の情報を表示部３５に供給して、表示部３５に表示させる。
【００２９】
特徴頂点列編集部４１は、操作部３７の操作内容に応じて、特徴頂点列生成部３４により生成された特徴頂点列を構成する頂点のいずれかが選択されて、移動されると、選択された頂点の移動に伴って、選択された頂点が属する特徴頂点列の編集を受け付けて、編集結果を３Ｄ形状データ記憶部３１に記憶させる。この結果、３Ｄ形状データ記憶部３１に記憶された３Ｄ形状データが編集されることになる。
【００３０】
＜特徴頂点列選択処理＞
次に、図２のフローチャートを参照して、特徴頂点列選択処理について説明する。
【００３１】
ステップＳ１１において、特徴頂点列生成部３４は、表示部３５を制御して、操作画面となる表示画像を表示する。表示画像は、例えば、図３で示されるようなものである。図３の表示画像Ｇ１においては、３次元形状が表示される表示欄が設けられる。また、図中下部には、左側に経路長を優先することを示すLengthが表示され、右側に曲率を優先することを示すCurvatureが表示されているスライダーバーＳＬ１が表示され、スライダーバーＳＬ１上に表示された重みつまみＴが、図中の左右に操作されることにより重みが設定される。さらに、図３の表示画像Ｇ１においては、自動車の外装フレームからなるオブジェクトＯＢ１が表示されている。また、始点Ｐ（ｓ１）、および終点Ｐ（ｅ１）が表示されており、それらを結ぶ特徴頂点列Ｌ１が表示されている。
【００３２】
ステップＳ１１において、曲率コスト計算部３２は、３Ｄ形状データ記憶部３１に記憶された３次元形状を構成する点、辺、および面を配置するために必要とされるデータに基づいて、曲率コスト計算処理を実行し、扱うべき３次元空間内における各辺の曲率コストを計算する。尚、曲率コスト計算処理については、図４のフローチャートを参照して、詳細を後述する。
【００３３】
ステップＳ１２において、経路長コスト計算部３３は、３Ｄ形状データ記憶部３１に記憶された３次元形状を構成する点、辺、および面を配置するために必要とされるデータに基づいて、経路長コスト計算処理を実行し、扱うべき３次元形状における各辺の経路長コストを計算する。尚、経路長コスト計算処理については、図５のフローチャートを参照して、詳細を後述する。
【００３４】
ステップＳ１３において、特徴頂点列生成部３４は、操作部３７が操作されて始点終点入力部３８に始点および終点の情報が入力されたか否かを判定する。ステップＳ１３において、例えば、図３で示されるように、操作部３７が操作されて始点終点入力部３８より始点および終点の座標が、例えば、図３の始点Ｐ（ｓ１）、および終点Ｐ（ｅ１）で示されるように入力された場合、処理は、ステップＳ１４に進む。
【００３５】
ステップＳ１４において、特徴頂点列生成部３４は、入力された曲率コスト、および経路長コスト、並びに、始点終点の座標情報に基づいて、特徴点列生成処理を実行し、特徴点列を生成し、生成した特徴頂点列を特徴頂点列簡略化部３６に供給する。尚、特徴頂点列生成処理については、図６のフローチャートを参照して、詳細を後述するものとする。
【００３６】
ステップＳ１５において、特徴頂点列簡略化部３６は、特徴頂点列生成部３４より供給されてくる特徴頂点列の情報と、簡略化割合入力部４０より供給されてくる簡略化割合の情報とに基づいて、特徴頂点列簡略化処理を実行し、特徴頂点列を簡略化し、表示部３５に供給して表示させる。尚、特徴頂点列簡略化処理については、図８のフローチャートを参照して後述するものとする。
【００３７】
ステップＳ１６において、操作部３７が操作されて、処理の完了が指示されたか否かが判定され、完了が指示されていない場合、処理は、ステップＳ１３に戻る。すなわち、処理の完了が指示されるまで、ステップＳ１３乃至Ｓ１６の処理が繰り返される。そして、ステップＳ１６において、完了が指示されると処理が終了する。
【００３８】
以上の処理により、始点および終点の座標の情報に加えて、後述する重み、並びに簡略化割合の情報が入力されると、対応する特徴頂点列が選択されて、表示部３５に表示される。
【００３９】
＜曲率コスト計算処理＞
次に、図４のフローチャートを参照して、曲率コスト計算処理について説明する。
【００４０】
ステップＳ３１において、曲率コスト計算部３２は、３Ｄ形状データ記憶部３１に記憶されている３次元形状を構成する辺の情報のうち、未処理の辺のいずれかを処理対象辺ｅに設定する。
【００４１】
ステップＳ３２において、曲率コスト計算部３２は、処理対象辺ｅについて、曲率コストＨ（ｅ）を計算する。具体的には、曲率コスト計算部３２は、処理対象辺ｅの曲率そのものを曲率コストＨ（ｅ）とするようにしてもよいし、処理対象辺ｅの曲率を所定の関数に入力して計算される値を曲率コストＨ（ｅ）としてもよい。
【００４２】
ステップＳ３３において、曲率コスト計算部３２は、計算した曲率コストＨ（ｅ）を３Ｄ形状データ記憶部３１に記憶させる。
【００４３】
ステップＳ３４において、曲率コスト計算部３２は、３Ｄ形状データ記憶部３１に記憶されている３次元形状を構成する辺の情報のうち、未処理の辺が存在するか否かを判定する。ステップＳ３４において、未処理の辺が存在する場合、処理は、ステップＳ３１に戻り、それ以降の処理が繰り返される。すなわち、全ての辺が処理対象辺ｅに設定されて、全ての辺について曲率コストＨ（ｅ）が計算されるまで、ステップＳ３１乃至Ｓ３４の処理が繰り返される。そして、ステップＳ３４において、未処理の辺が存在しないとみなされた場合、処理は、終了する。
【００４４】
すなわち、以上の処理により、３Ｄ形状データ記憶部３１に記憶されている３次元形状を構成する辺の情報の全てについて曲率コストが計算されて、３Ｄ形状データ記憶部３１に記憶される。
【００４５】
＜経路長コスト計算処理＞
次に、図５のフローチャートを参照して、経路長コスト計算処理について説明する。
【００４６】
ステップＳ５１において、経路長コスト計算部３３は、３Ｄ形状データ記憶部３１に記憶されている３次元形状を構成する辺の情報のうち、未処理の辺のいずれかを処理対象辺ｅに設定する。
【００４７】
ステップＳ５２において、経路長コスト計算部３３は、処理対象辺ｅについて、経路長コストＬ（ｅ）を計算する。具体的には、経路長コスト計算部３３は、処理対象辺ｅの経路長そのものを経路長コストＬ（ｅ）とするようにしてもよいし、処理対象辺ｅの経路長を所定の関数に入力して計算される値を経路長コストＬ（ｅ）としてもよい。
【００４８】
ステップＳ５３において、経路長コスト計算部３３は、計算した経路長コストＬ（ｅ）を３Ｄ形状データ記憶部３１に記憶させる。
【００４９】
ステップＳ５４において、経路長コスト計算部３３は、３Ｄ形状データ記憶部３１に記憶されている３次元形状を構成する辺の情報のうち、未処理の辺が存在するか否かを判定する。ステップＳ５４において、未処理の辺が存在する場合、処理は、ステップＳ５１に戻り、それ以降の処理が繰り返される。すなわち、全ての辺が処理対象辺ｅに設定されて、全ての辺について経路長コストＬ（ｅ）が計算されるまで、ステップＳ５１乃至Ｓ５４の処理が繰り返される。そして、ステップＳ５４において、未処理の辺が存在しないとみなされた場合、処理は、終了する。
【００５０】
すなわち、以上の処理により、３Ｄ形状データ記憶部３１に記憶されている３次元形状を構成する辺の情報の全てについて経路長コストが計算されて、３Ｄ形状データ記憶部３１に記憶される。
【００５１】
＜特徴頂点列生成処理＞
次に、図６のフローチャートを参照して、特徴頂点列生成処理について説明する。
【００５２】
ステップＳ７１において、コスト重み入力部３９のスライダーバー表示制御部３９ａは、操作部３７が所定の操作がなされて、コストの重みｗを入力するためのスライダーバーを表示するように要求されたか否かを判定する。ステップＳ７１において、例えば、操作部３７が操作されて、ポインタが所定の距離より長い距離だけ水平方向にドラッグされ、所定の操作がなされたと見なされた場合、処理は、ステップＳ７２に進む。尚、コストの重みｗを入力するためのスライダーバーを表示させるための所定の操作は、所定の距離より長い距離だけ水平方向にドラッグされる操作以外の操作であってもよいし、別途、表示を要求するためのボタン等を設けるようにして、そのボタンが操作されたときスライダーバーを表示するようにしてもよい。
【００５３】
ステップＳ７２において、スライダーバー表示制御部３９ａは、例えば、図３で示されるようなスライダーバーＳＬ１を表示部３５に表示させ、コストの重みｗの入力を受け付けられる状態にする。このような処理により、スライダーバーＳＬ１を操作に必要なときだけ、容易な操作により表示させることが可能となり、不必要な状態においては表示させないようにすることが可能となる。
【００５４】
ステップＳ７３において、特徴頂点列生成部３４は、操作部３７でスライダーバーＳＬ１上の重みつまみＴが操作されることにより、コストの重みｗ（０＜ｗ＜１）が入力されて、特徴頂点列の生成処理が指示されているか否かを判定する。すなわち、図３で示される重みつまみＴが、操作部３７が操作されることによりスライダーバーＳＬ１上の新たな位置に設定されると、重みｗが設定されたものとみなし、処理は、ステップＳ７４に進む。
【００５５】
ステップＳ７４において、特徴頂点列生成部３４は、コスト計算部３４ａを制御して、重みｗに基づいて、始点から終点までの経路上に存在する辺の組み合わせ毎に、曲率コストＨ（ｅ）の総和Ｈ、および経路長コストＬ（ｅ）の総和Ｌを用いた、コストＣ（＝（１−ｗ）×Ｌ＋ｗ×Ｈ）の計算方法を設定させる。
【００５６】
ステップＳ７５において、特徴頂点列生成部３４は、コスト計算部３４ａを制御して、始点から終点までの経路上に存在する辺の全ての組み合わせ毎のコストＣ（＝（１−ｗ）×Ｌ＋ｗ×Ｈ）を全て計算させる。さらに、特徴頂点列生成部３４は、計算結果とされるコストＣのうち、コストＣが最小値をとる辺の組み合わせからなる経路を最短経路として計算する。すなわち、特徴頂点列生成部３４は、コストＣに基づいて、始点および終点間の最短経路問題を解くことにより最短経路を計算する。
【００５７】
ステップＳ７６において、特徴頂点列生成部３４は、最短経路上に存在する点からなる頂点の列を特徴頂点列として生成し、特徴頂点列簡略化部３６に供給する。
【００５８】
尚、ステップＳ７１において、スライダーバーの表示が要求されない場合、または、ステップＳ７３において、重みｗが入力されておらず、新たな特徴頂点列の生成が指示されない場合、ステップＳ７４乃至Ｓ７６の処理がスキップされる。
【００５９】
ステップＳ７７において、特徴頂点列生成部３４は、操作部３７が操作されて特徴頂点列生成処理の完了が指示されたか否かを判定し、完了が指示されていない場合、処理は、ステップＳ７１に戻る。すなわち、処理の完了が指示されるまで、スライダーバーの表示要求、および、重みｗの入力が受け付けられて、重みｗが入力される度に特徴頂点列が再計算により生成される。そして、ステップＳ７７において、操作部３７が操作されて、処理の完了が入力されると、処理が終了する。
【００６０】
以上の処理により、例えば、図７の表示画像Ｇ１１の重みつまみＴ１で示されるように、経路長を優先するようにスライダーバーＳＬ１の左端に操作されると、重みｗ＝０に設定され、図３で示されるような特徴頂点列Ｌ１が、図７の表示画像Ｇ１１の特徴頂点列Ｌ１１で示されるように、経路長が優先されて頂点列が選択される。逆に、例えば、図７の表示画像Ｇ１２の重みつまみＴ２で示されるように、曲率を優先するようにスライダーバーＳＬ１の右端に操作されると、重みｗ＝１に設定され、図７の表示画像Ｇ１２の特徴頂点列Ｌ１２で示されるように、曲率が優先されて折り目に沿って頂点列が選択される。尚、スライダーバーＳＬ１は、操作がなされた後は、所定時間が経過したところで表示しない状態とするようにしてもよい。このようにすることで、スライダーバーＳＬ１を必要なタイミングにだけ表示させることが可能となる。
【００６１】
＜特徴頂点列簡略化処理＞
次に、図８のフローチャートを参照して、特徴頂点列簡略化処理について説明する。
【００６２】
ステップＳ９１において、簡略化割合入力部４０のスライダーバー表示制御部４０ａは、操作部３７が所定の操作がなされて、簡略化割合ｄを入力するためのスライダーバーを表示するように要求されたか否かを判定する。ステップＳ９１において、例えば、操作部３７が操作されて、ポインタが所定の距離より長い距離だけ垂直方向にドラッグされ、所定の操作がなされたと見なされた場合、処理は、ステップＳ９２に進む。尚、簡略化割合ｄを入力するためのスライダーバーを表示させるための所定の操作は、所定の距離より長い距離だけ垂直方向にドラッグされる操作以外の操作であってもよいし、別途、表示を要求するためのボタン等を設けるようにして、そのボタンが操作されたときスライダーバーを表示するようにしてもよい。
【００６３】
ステップＳ９２において、スライダーバー表示制御部４０ａは、例えば、図９の表示画像Ｇ２１で示されるようなスライダーバーＳＬ２、および簡略化割合つまみＴ１１を表示部３５に表示させ、簡略化割合ｄの入力を受け付けられる状態にする。図９においては、スライダーバーＳＬ２の上端にDenseと表示され、特徴頂点の密度が高くなる方向に制御するとき、簡略化割合つまみＴ１１が操作され、下端に、Sparseと表示され、特徴頂点の密度が低くなる方向に制御するとき、簡略化割合つまみＴ１１が操作される。このような処理により、スライダーバーＳＬ２を操作に必要なときだけ、容易な操作により表示させることが可能となり、不必要な状態においては表示させないようにすることが可能となる。
【００６４】
ステップＳ９３において、特徴頂点列簡略化部３６は、操作部３７でスライダーバーＳＬ２上の簡略化割合つまみが操作されて、簡略化割合入力部４０より簡略化割合が入力されたか否かを判定する。すなわち、例えば、図９で示される簡略化割合つまみＴ１１が、操作部３７が操作されることによりスライダーバーＳＬ２上の新たな位置に設定されると、簡略化割合ｄが設定されたものとみなす。図９においては、簡略化割合つまみＴ１１は、表示画像Ｇ２１においては、上方向に操作されている。
【００６５】
ステップＳ９３において、例えば、簡略化割合ｄが操作されて入力された場合、処理は、ステップＳ９４に進む。
【００６６】
ステップＳ９４において、特徴頂点列簡略化部３６は、簡略化割合ｄに基づいて、特徴頂点列を構成する特徴頂点の密度の粗密を調整する。
【００６７】
ステップＳ９５において、特徴頂点列簡略化部３６は、簡略化割合ｄに基づいて、調整された特徴頂点を接続して新たな特徴頂点列を生成する。
【００６８】
ステップＳ９６において、操作部３７が操作されて処理が完了したことが指示されたか否かが判定され、完了が指示されていない場合、処理は、ステップＳ９１に戻る。すなわち、完了が指示されるまで、ステップＳ９１乃至Ｓ９６の処理が繰り返される。そして、ステップＳ９６において、完了が指示されると、処理が終了する。尚、スライダーバーＳＬ２は、操作がなされた後は、所定時間が経過したところで表示しない状態とするようにしてもよい。このようにすることで、スライダーバーＳＬ２を必要なタイミングにだけ表示させることが可能となる。
【００６９】
すなわち、図９の左部で示されるように、簡略化割合つまみＴ１１がスライダーバーＳＬ２上の最も密度の高い上方向に操作されて、簡略化割合ｄが１である場合については、全ての特徴頂点を残した状態で特徴頂点列Ｌ２１が表示される。すなわち、特徴頂点が多いと図９の表示画像Ｇ２１の特徴頂点列Ｌ２１で示されるように、円周上に配置されるべきものが、画像上のノイズがあるような形状となるが、図９の右部の表示画像Ｇ２２で示されるように、簡略化割合つまみＴ１２で示されるようにスライダーバーＳＬ２上の下方向に操作されることにより、簡略化割合ｄが、例えば、０．７５程度にされることにより、特徴頂点の密度が等間隔で低下されることで、特徴頂点列Ｌ２２で示されるように外形形状が美しく補正される。尚、図９においては、Ｐ（ｓ２）が始点を表しており、Ｐ（ｅ２）が終点を表している。また、簡略化割合ｄについては、最大値は１程度であるが、最小値は、例えば、０．７５などにしてもよいし、それ以外の値であってもよい。ただし、最小値が０になってしまうと特徴頂点列が構成できない状態となるため、その設定は、残すべき形状などにより調整できるようにしてもよい。
【００７０】
＜特徴頂点列編集処理＞
次に、図１０のフローチャートを参照して、特徴頂点列編集処理について説明する。尚、この処理は、特徴頂点選択処理により特徴頂点列が選択された状態でなされる処理である。
【００７１】
すなわち、ステップＳ１１１において、特徴頂点列編集部４１は、操作部３７が操作されて、特徴頂点列選択処理により生成された特徴頂点列を構成するいずれかの頂点が選択されたか否かを判定し、選択されるまで同様の操作を繰り返す。ステップＳ１１１において、例えば、図１１の左部における表示画像Ｇ３１で示されるように、下唇の３次元形状における曲率を優先した特徴頂点列Ｌ３１が求められることにより、下唇の外形形状が特定され、さらに、この特徴頂点列Ｌ３１上の頂点Ｔ３１が選択されると、処理は、ステップＳ１１２に進む。
【００７２】
ステップＳ１１２において、特徴頂点列編集部４１は、選択された頂点Ｔ３１が属する特徴頂点列を構成する頂点のデータを３Ｄ形状データ記憶部３１より読み出す。すなわち、図１１の場合、選択された頂点である頂点Ｔ３１の属する特徴頂点列Ｌ３１に属する全ての頂点のデータが読み出される。
【００７３】
ステップＳ１１３において、特徴頂点列編集部４１は、選択された頂点Ｔ３１が属する特徴頂点列を構成する頂点のデータに基づいて、拡張された範囲の頂点のデータを３Ｄ形状データ記憶部３１より読み出す。すなわち、図１１の場合、選択された頂点である頂点Ｔ３１の属する特徴頂点列Ｌ３１の近傍に存在する特徴頂点列Ｌ３１’，Ｌ３１’’に属する全ての頂点のデータが拡張された範囲の頂点のデータとして読み出される。尚、拡張される範囲については、図１１においては、特徴頂点列Ｌ３１に対して図中の上下に特徴頂点列が１本ずつ拡張される例として特徴頂点列Ｌ３１’，Ｌ３１’’が設定される例について説明しているが、拡張される範囲はこれ以上の本数の特徴頂点列を含む範囲であってもよい。
【００７４】
ステップＳ１１４において、特徴頂点列編集部４１は、操作部３７が操作されて、選択された頂点が移動したか否かを判定する。ステップＳ１１４において、例えば、図１１の右部で示されるように、頂点Ｔ３１が矢印で示される水平方向、および垂直方向に移動されて、頂点Ｔ３２へと移動されると、処理は、ステップＳ１１５に進む。
【００７５】
ステップＳ１１５において、特徴頂点列編集部４１は、移動された頂点と、その他の頂点により構成される特徴頂点列、並びに、拡張された特徴頂点列を、例えば、スプライン処理するなどして再計算する。すなわち、図１１の場合、頂点Ｔ３２と、それ以外の特徴頂点列を構成する頂点との位置関係がスプライン処理されるように再計算されることにより、特徴頂点列Ｌ３２が求められることになる。また、特徴頂点列編集部４１は、拡張された範囲となる特徴頂点列Ｌ３１’，Ｌ３１’’に属する頂点についても、頂点Ｔ３１の移動に伴って再計算し、特徴頂点列Ｌ３２’，Ｌ３２’’として算出する。尚、拡張された範囲となる特徴頂点列Ｌ３２’，Ｌ３２’’に属する頂点の移動量については、移動された頂点Ｔ３２からの距離に応じて移動量を小さくするようにしてもよい。このようにすることで、１個の頂点の移動に伴う周辺の頂点の移動量を自然なものに設定することが可能となる。
【００７６】
ステップＳ１１６において、特徴頂点列編集部４１は、再計算して求められた特徴頂点列を構成する頂点のデータを、３Ｄ形状データ記憶部３１に更新して記憶させる。
【００７７】
ステップＳ１１７において、表示部３５は、このようにして更新して記憶された特徴頂点列を構成する頂点のデータに基づいて、変形された特徴頂点列Ｌ３２を表示する。
【００７８】
尚、ステップＳ１１４において、選択された頂点が移動されない場合、処理は、ステップＳ１１１に戻る。
【００７９】
このような処理により、例えば、図１１の左部における表示画像Ｇ３１で示されるように、下唇の３次元形状における曲率を優先した特徴頂点列Ｌ３１が求められることにより、下唇の外形形状が特定され、さらに、この特徴頂点列Ｌ３１上の頂点Ｔ３１を矢印で示される水平方向、および垂直方向に移動させて、例えば、図１１の右部の表示画像Ｇ３２で示される頂点Ｔ３２とすることにより、特徴頂点列Ｌ３１を特徴頂点列Ｌ３２に変化させて、下唇の外形形状を変形することが可能となる。また、このとき、特徴頂点列Ｌ３１の周辺の特徴頂点列Ｌ３１’，Ｌ３１’’についても、特徴頂点列Ｌ３１の変化に対応して、変化させることが可能となるので、唇の全体の形状を自然な状態で変形させることが可能となる。
【００８０】
以上の処理により、始点および終点を特定し、曲率コストＣ、および経路長コストＬのそれぞれを優先するための重みｗ、さらに、特徴頂点列の簡略化割合ｄが入力されることにより、容易で、かつ、適切に特徴頂点列を選択することが可能となる。また、重みつまみ、および簡略化割合つまみを操作するだけで、特徴頂点列を変化させながら、所望とする特徴頂点列が選択されるまで、繰り返し操作をすることが可能であるため、容易で、かつ、適切に特徴頂点列を選択することが可能となる。
【００８１】
ところで、上述した一連の処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【００８２】
図１２は、汎用のパーソナルコンピュータの構成例を示している。このパーソナルコンピュータは、CPU(Central Processing Unit)１００１を内蔵している。CPU１００１にはバス１００４を介して、入出力インタ-フェイス１００５が接続されている。バス１００４には、ROM(Read Only Memory)１００２およびRAM(Random Access Memory)１００３が接続されている。
【００８３】
入出力インタ-フェイス１００５には、ユーザが操作コマンドを入力するキーボード、マウスなどの入力デバイスよりなる入力部１００６、処理操作画面や処理結果の画像を表示デバイスに出力する出力部１００７、プログラムや各種データを格納するハードディスクドライブなどよりなる記憶部１００８、LAN（Local Area Network）アダプタなどよりなり、インターネットに代表されるネットワークを介した通信処理を実行する通信部１００９が接続されている。また、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory)、DVD(Digital Versatile Disc)を含む）、光磁気ディスク（ＭＤ(Mini Disc)を含む）、もしくは半導体メモリなどのリムーバブルメディア１０１１に対してデータを読み書きするドライブ１０１０が接続されている。
【００８４】
CPU１００１は、ROM１００２に記憶されているプログラム、または磁気ディスク、光ディスク、光磁気ディスク、もしくは半導体メモリ等のリムーバブルメディア１０１１ら読み出されて記憶部１００８にインストールされ、記憶部１００８からRAM１００３にロードされたプログラムに従って各種の処理を実行する。RAM１００３にはまた、CPU１００１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【００８５】
以上のように構成されるコンピュータでは、CPU１００１が、例えば、記憶部１００８に記憶されているプログラムを、入出力インタフェース１００５及びバス１００４を介して、RAM１００３にロードして実行することにより、上述した一連の処理が行われる。
【００８６】
コンピュータ（CPU１００１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブルメディア１０１１に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【００８７】
コンピュータでは、プログラムは、リムーバブルメディア１０１１をドライブ１０１０に装着することにより、入出力インタフェース１００５を介して、記憶部１００８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部１００９で受信し、記憶部１００８にインストールすることができる。その他、プログラムは、ROM１００２や記憶部１００８に、あらかじめインストールしておくことができる。
【００８８】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【００８９】
また、本明細書において、システムとは、複数の構成要素（装置、モジュール（部品）等）の集合を意味し、すべての構成要素が同一筐体中にあるか否かは問わない。したがって、別個の筐体に収納され、ネットワークを介して接続されている複数の装置、及び、１つの筐体の中に複数のモジュールが収納されている１つの装置は、いずれも、システムである。
【００９０】
なお、本技術の実施の形態は、上述した実施の形態に限定されるものではなく、本技術の要旨を逸脱しない範囲において種々の変更が可能である。
【００９１】
例えば、本技術は、１つの機能をネットワークを介して複数の装置で分担、共同して処理するクラウドコンピューティングの構成をとることができる。
【００９２】
また、上述のフローチャートで説明した各ステップは、１つの装置で実行する他、複数の装置で分担して実行することができる。
【００９３】
さらに、１つのステップに複数の処理が含まれる場合には、その１つのステップに含まれる複数の処理は、１つの装置で実行する他、複数の装置で分担して実行することができる。
【符号の説明】
【００９４】
１１  特徴頂点列選択装置，  ３１  ３Ｄ形状データ記憶部，  ３２  曲率コスト計算部，  ３３  経路長コスト部，  ３４  特徴頂点列生成部，  ３４ａ  コスト計算部，  ３５  表示部，  ３６  特徴頂点列簡略化部，  ３７  操作部，  ３８  始点終点入力部，  ３９  コスト重み入力部，  ３９ａ  スライダーバー表示制御部，  ４０  簡略化割合入力部，  ４０ａ  スライダーバー表示制御部，  ４１  特徴頂点列編集部
【要約】
【課題】特徴頂点列を容易で、かつ、適切に求められるようにする。
【解決手段】曲率コスト計算部３２が、３Ｄ形状データ記憶部３１に記憶されている各辺ｅの曲率コストＨ（ｅ）を計算する。経路長コスト計算部３３が、３Ｄ形状データ記憶部３１に記憶されている各辺ｅの経路長コストＬ（ｅ）を計算する。特徴頂点列生成部３４は、操作部３７が操作されて、始点終点入力部３８より供給されてくる始点および終点間の辺が接続されて構成される経路上の経路長コストＬ（ｅ）の総和Ｌ、および曲率コストＨ（ｅ）の総和Ｈ、並びにコスト重み入力部３９より供給されてくる重みｗに基づいて、コストＣ（＝（１−ｗ）×Ｌ＋ｗ×Ｈ）を計算し、最小となる経路を構成する点を特徴頂点列として求める。本技術は、３次元形状の編集ソフトウェアプログラムに適用することができる。
【選択図】図１【図１】
0005531087.tif 000002
【図２】
0005531087.tif 000003
【図３】
0005531087.tif 000004
【図４】
0005531087.tif 000005
【図５】
0005531087.tif 000006
【図６】
0005531087.tif 000007
【図７】
0005531087.tif 000008
【図８】
0005531087.tif 000009
【図９】
0005531087.tif 000010
【図１０】
0005531087.tif 000011
【図１１】
0005531087.tif 000012
【図１２】
0005531087.tif 000013