(57)【特許請求の範囲】
【請求項１】
パラメトリック表現式によって表現される３次元曲面形状を用意するステップと、前記パラメトリック表現式が有理パラメトリック表現式である場合には、前記パラメトリック表現式の冗長性を有する重みパラメータを変更して、前記３次元曲面形状へ情報を埋め込むステップと、前記パラメトリック表現式が非有理パラメトリック表現式である場合には、該非有理パラメトリック表現式を有理パラメトリック表現式に変更することにより、冗長性を有する重みパラメータを付与し、該冗長性を有する重みパラメータを変更して、前記３次元曲面形状へ情報を埋め込むステップと、を有することを特徴とする３次元曲面形状への情報の埋め込み方法。
【請求項２】
３次元曲面形状集合を順序づけるステップと、前記順序にしたがって３次元曲面形状を順次選択し、選択した３次元曲面形状を対象として請求項１に記載の３次元曲面形状への情報の埋め込み方法によって、前記３次元曲面形状へ情報を埋め込むステップと、を有することを特徴とする３次元曲面形状集合への情報の埋め込み方法。
【請求項３】
前記パラメトリック表現式は、ベジェ曲面式であることを特徴とする、請求項１又は２に記載の３次元曲面形状への情報の埋め込み方法。
【請求項４】
前記パラメトリック表現式は、Ｂ−スプライン曲面式であることを特徴とする請求項１又は２に記載の３次元曲面形状への情報の埋め込み方法。
【請求項５】
請求項１乃至４のいずれかに記載の３次元曲面形状への情報の埋め込み方法によって３次元曲面形状へ埋め込まれた情報を取り出す３次元曲面形状からの情報の取り出し方法であって、前記情報が埋め込まれている３次元曲面形状を用意するステップと、前記冗長性を有する重みパラメータを検出することにより、前記情報を前記３次元曲面形状から取り出すステップと、を有することを特徴とする３次元曲面形状からの情報の取り出し方法。
【請求項６】
３次元曲面形状集合を順序づけるステップと、前記順序にしたがって３次元曲面形状を順次選択し、選択した３次元曲面形状を対象として請求項５に記載の３次元曲面形状からの情報取り出し方法によって、前記３次元曲面形状から情報を取り出すステップと、を有することを特徴とする３次元曲面形状集合からの情報の取り出し方法。
【請求項７】
パラメトリック表現式によって表現される３次元曲面形状を入力する入力部と、前記パラメトリック表現式が有理パラメトリック表現式である場合には、前記パラメトリック表現式の冗長性を有する重みパラメータを変更して、前記３次元曲面形状へ情報を埋め込み、前記パラメトリック表現式が非有理パラメトリック表現式である場合には、該非有理パラメトリック表現式を有理パラメトリック表現式に変更することにより、冗長性を有する重みパラメータを付与し、該冗長性を有する重みパラメータを変更して、前記３次元曲面形状へ情報を埋め込む情報埋め込み部と、を有することを特徴とする３次元曲面形状への情報埋め込み装置。
【請求項８】
請求項７に記載の３次元曲面形状への情報埋め込み装置によって３次元曲面形状へ埋め込まれた情報を取り出す３次元曲面形状からの情報取り出し装置であって、前記情報が埋め込まれている３次元曲面形状を入力する入力部と、前記冗長性を有する重みパラメータを検出することにより、前記情報を前記３次元曲面形状から取り出す情報取り出し部と、を有することを特徴とする３次元曲面形状からの情報取り出し装置。
【請求項９】
請求項１乃至４のいずれかに記載の３次元曲面形状への情報の埋め込み方法の各ステップ、または、請求項５または６に記載の３次元曲面形状からの情報の取り出し方法の各ステップをコンピュータに実行させるためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元ＣＡＤ／ＣＡＭ／ＣＡＥ／ＣＧなど３次元形状を扱う分野に応用可能な３次元曲面形状への情報の埋め込み方法、該方法により埋め込まれた情報の取り出し方法、装置、及びそれらの機能を実現するためのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
ディジタルメディアの普及によりディジタルコンテンツのコピーが容易になるとともに、不正コピーや改竄を防止するために、ディジタルコンテンツ中に著作権情報や配布経路情報などを埋め込む電子透かし技術の必要性が高まっている。２次元画像データや音声データを対象とした電子透かしについてはすでに多くの研究が行われているが、３次元形状データへの情報埋め込みの研究はまだ端緒が開かれたばかりである。例えば、特開平１０−３３４２７２号公報によれば、３次元形状をポリゴンモデル（３角形メッシュモデル）として近似表現し、当該ポリゴンモデルの幾何パラメータ（数値パラメータ及び位相）を変更することにより情報を埋め込んでいた。
【０００３】
【発明が解決しようとする課題】
上記の特開平１０−３３４２７２号公報に示された従来技術では、３次元形状データの主な用途はブラウザ上での表示であるという立場から、３次元形状の表現形式として近似表現形式であるポリゴンモデルを採用している。また、情報を埋め込むために当該ポリゴンモデルの数値パラメータ（頂点の座標値など）を微少に変更する場合には、ポリゴンモデルの表示をブラウザ上で目視してもユーザが気づかない程度ではあるものの、３次元形状自体を変更してしまうことになる。
【０００４】
しかしながら、３次元ＣＡＤ／ＣＡＭなどで３次元形状データを利用する場合には、常に３次元曲面形状を厳密に表現する必要があるため、ポリゴンモデルでは精度が不十分であり、また、たとえ微少といえども、情報の埋め込みが３次元曲面形状自体に影響を及ぼすことは望ましくない。
【０００５】
本発明は、上記の課題を解決するために、３次元曲面形状のポリゴンモデルではなく３次元曲面形状のパラメトリック表現式自体に情報を埋め込み、かつ、３次元曲面の幾何形状を変更することなく情報を埋め込むことができ、また埋め込んだ情報を取り出すことができる方法、装置、及びそれらの機能を実現するプログラムを記録した記録媒体を提供することを目的とする。
【０００７】
【課題を解決するための手段】
請求項１の発明は、パラメトリック表現式によって表現される３次元曲面形状を用意するステップと、前記パラメトリック表現式が有理パラメトリック表現式である場合には、前記パラメトリック表現式の冗長性を有する重みパラメータを変更して、前記３次元曲面形状へ情報を埋め込むステップと、前記パラメトリック表現式が非有理パラメトリック表現式である場合には、該非有理パラメトリック表現式を有理パラメトリック表現式に変更することにより、冗長性を有する重みパラメータを付与し、該冗長性を有する重みパラメータを変更して、前記３次元曲面形状へ情報を埋め込むステップと、を有することを特徴とするものである。
【０００８】
請求項２の発明は、３次元曲面形状集合を順序づけるステップと、前記順序にしたがって３次元曲面形状を順次選択し、選択した３次元曲面形状を対象として請求項１に記載の３次元曲面形状への情報の埋め込み方法によって、前記３次元曲面形状へ情報を埋め込むステップと、を有することを特徴とするものである。
請求項３の発明は、請求項１又は２に記載の３次元曲面形状への情報の埋め込み方法において、前記パラメトリック表現式は、ベジェ曲面式であることを特徴とするものである。
請求項４の発明は、請求項１又は２に記載の３次元曲面形状への情報の埋め込み方法において、前記パラメトリック表現式は、Ｂ−スプライン曲面式であることを特徴とするものである。
【０００９】
請求項５の発明は、請求項１乃至４のいずれかに記載の３次元曲面形状への情報の埋め込み方法によって３次元曲面形状へ埋め込まれた情報を取り出す３次元曲面形状からの情報の取り出し方法であって、前記情報が埋め込まれている３次元曲面形状を用意するステップと、前記冗長性を有する重みパラメータを検出することにより、前記情報を前記３次元曲面形状から取り出すステップと、を有することを特徴とするものである。
【００１０】
請求項６の発明は、３次元曲面形状集合を順序づけるステップと、前記順序にしたがって３次元曲面形状を順次選択し、選択した３次元曲面形状を対象として請求項５に記載の３次元曲面形状からの情報取り出し方法によって、前記３次元曲面形状集合から情報を取り出すステップと、を有することを特徴とするものである。
【００１１】
請求項７の発明は、パラメトリック表現式によって表現される３次元曲面形状を入力する入力部と、前記パラメトリック表現式が有理パラメトリック表現式である場合には、前記パラメトリック表現式の冗長性を有する重みパラメータを変更して、前記３次元曲面形状へ情報を埋め込み、前記パラメトリック表現式が非有理パラメトリック表現式である場合には、該非有理パラメトリック表現式を有理パラメトリック表現式に変更することにより、冗長性を有する重みパラメータを付与し、該冗長性を有する重みパラメータを変更して、前記３次元曲面形状へ情報を埋め込む情報埋め込み部と、を有することを特徴とするものである。
【００１２】
請求項８の発明は、請求項７に記載の３次元曲面形状への情報埋め込み装置によって３次元曲面形状へ埋め込まれた情報を取り出す３次元曲面形状からの情報取り出し装置であって、前記情報が埋め込まれている３次元曲面形状を入力する入力部と、前記冗長性を有する重みパラメータを検出することにより、前記情報を前記３次元曲面形状から取り出す情報取り出し部と、を有することを特徴とするものである。
請求項９の発明は、請求項１乃至４のいずれかに記載の３次元曲面形状への情報の埋め込み方法の各ステップ、または、請求項５または６に記載の３次元曲面形状からの情報の取り出し方法の各ステップをコンピュータに実行させるためのプログラムを記録したことを特徴とするものである。
【００１３】
【発明の実施の形態】
図１は、本発明による３次元曲面形状への情報埋め込み／取り出しを行う処理が適用される装置の一実施例におけるシステム構成を示すブロック図である。当該装置は、バス１、ＣＰＵ２、メモリ３、外部記憶装置４、入力装置５、表示装置６を備えるコンピュータシステム及びその上で動作するプログラムによって表現される。
【００１４】
図２は、本発明が適用される３次元曲面形状への情報埋め込み／取り出しを行う処理が適用される装置の一実施例における機能ブロック図である。当該装置は、入力部１１、３次元曲面形状集合順序づけ部１２、情報埋め込み部１３、情報取り出し部１４、出力部１５、表示部１６の各機能から構成される。
【００１５】
図３は、本発明により３次元曲面形状へ情報を埋め込む動作を説明するためのフローチャートである。まず、パラメトリック表現式によって表現される３次元曲面形状を用意し（ステップＳ１）、用意した３次元曲面形状のパラメトリック表現式が冗長性を有しているかどうかを判断する（ステップＳ２）。パラメトリック表現式が冗長性を有している場合、ステップＳ４で埋め込むべき情報を用意し、その埋め込むべき情報に対応して冗長性を有するパラメータを変更し（ステップＳ５）、情報が埋め込まれた３次元曲面形状を出力する（ステップＳ６）。
【００１６】
また、ステップＳ２でパラメトリック表現式が冗長性を有していない場合、パラメトリック表現式を変更して冗長性を有するパラメータを付与し（ステップＳ３）、その冗長性を有するパラメータを、埋め込むべき情報に対応して変更し（ステップＳ５）、情報を埋め込んだ３次元曲面形状を出力する（ステップＳ６）。
【００１７】
図４は、本発明により３次元曲面形状から情報を取り出す動作を説明するためのフローチャートである。まず、情報が埋め込まれている３次元曲面形状を用意する（ステップＳ１１）。そして３次元曲面形状のパラメトリック表現式における冗長性を有するパラメータを検出して情報を取り出し（ステップＳ１２）、取り出された情報を出力する（ステップＳ１３）。
【００１８】
以下に、以上の３次元曲面形状への情報の埋め込み、及び３次元曲面形状からの情報の取り出しについて、パラメトリック表現式がベジェ曲面式である場合とＢ−スプライン曲面式である場合の詳細を説明する。
【００１９】
Ｉ．ベジェ曲面式の場合
用意された３次元曲面形状のパラメトリック表現式が有理ベジェ曲面式である場合、表現式は冗長性を有している。すなわち、ｎ×ｍ次の有理ベジェ曲面式は次のとおりである。
【００２０】
【式１】
0003995378.tif 000002
【００２１】
ここで、曲面式（１）の分子分母のｗijを定数α倍しても当該３次元曲面の幾何形状は変わらないので、重みパラメータｗijは冗長性を有する。従って、例えばαｗ00の値を、埋め込むべき情報に対応して変更することによって、当該３次元曲面形状に情報を埋め込むことができる。
【００２２】
また、用意された３次元曲面形状のパラメトリック表現式が非有理ベジェ曲面式である場合、表現式は冗長性を有していない。すなわち、ｎ×ｍ次の非有理ベジェ曲面式は次のとおりである。
【００２３】
【式２】
0003995378.tif 000003
【００２４】
ここで、ｉ，ｊによらず一定の任意の重みパラメータｗijを用いれば、下記のＢｅｒｎｓｔｅｉｎ基底関数の一般的な性質により、曲面式（２）は曲面式（１）に変換することができる。
【００２５】
【式３】
0003995378.tif 000004
【００２６】
上記のとおり、ｗijの値は任意に指定できるので、重みパラメータｗijは冗長性を有する。従って、ｗijの値を埋め込むべき情報に対応して変更することによって、当該３次元曲面形状に情報を埋め込むことができる。以上、いずれの場合も、情報が埋め込まれている３次元曲面形状のパラメトリック表現式は有理ベジェ曲面式となるので、重みパラメータを検出することによって、埋め込まれた情報を取り出すことができる。
【００２７】
II．Ｂ−スプライン曲面式の場合
用意された３次元曲面形状のパラメトリック表現式が有理Ｂ−スプライン曲面式である場合、その表現式は冗長性を有している。すなわち、ｋ×ｌ次の有理Ｂ−スプライン曲面式（制御点数は（ｎ＋ｌ）×（ｍ＋ｌ））は次のとおりである。
【００２８】
【式４】
0003995378.tif 000005
【００２９】
ここで、曲面式（４）の分子と分母のｗijを定数α倍しても３次元曲面の幾何形状は変わらないので、重みパラメーターｗijは冗長性を有する。したがって、たとえばαｗ00の値を埋め込むべき情報に対応して変更することによって、当該３次元曲面形状に情報を埋め込むことができる。
また、用意された３次元曲面形状のパラメトリック表現式が非有理Ｂ−スプライン曲面式である場合、その表現式は冗長性を有していない。すなわち、ｋ×ｌ次の非有理Ｂ−スプライン曲面式（制御点数は（ｎ＋ｌ）×（ｍ＋ｌ））は次のとおりである。
【００３０】
【式５】
0003995378.tif 000006
【００３１】
ここで、ｉ，ｊによらず一定の任意の重みパラメータｗijを用いれば、Ｂ−スプライン基底関数の下記の一般的な性質により、曲面式（５）は曲面式（４）に変換することができる。
【００３２】
【式６】
0003995378.tif 000007
【００３３】
上記のとおり、ｗijの値は任意に指定できるので、重みパラメータｗijは冗長性を有する。従って、ｗijの値を埋め込むべき情報に対応して変更することによって、当該３次元曲面形状に情報を埋め込むことができる。
以上、いずれの場合も、情報が埋め込まれている３次元曲面形状のパラメトリック表現式は有理Ｂ−スプライン曲面式となるので、重みパラメータを検出することによって、当該情報を取り出すことができる。
【００３４】
次に、３次元曲面形状集合への情報の埋め込み及び取り出しについて説明する。３次元曲面形状集合を順序づければ、個々の３次元曲面形状へ埋め込むことができる情報量よりも多くの情報を埋め込むことができる。
【００３５】
図５は、本発明の他の実施例により３次元曲面形状集合へ情報を埋め込む動作を説明するためのフローチャートである。まず３次元曲面形状集合を用意し（ステップＳ２１）、その３次元曲面形状集合を順序づける（ステップＳ２２）。そして、すべての３次元曲面に情報が埋め込まれているかどうかを判断し（ステップＳ２３）、埋め込まれていれば、情報が埋め込まれた３次元曲面形状集合を出力する（ステップＳ２４）。
【００３６】
ステップＳ２３ですべての３次元曲面形状に情報が埋め込まれていない場合、埋め込むべき情報を用意し（ステップＳ２５）、順序にしたがって３次元曲面形状を選択し、当該３次元曲面形状のパラメトリック表現式の冗長性を有するパラメータを上記の埋め込むべき情報に対応して変更し（ステップＳ２６）、ステップＳ２３に戻る。
【００３７】
図６は、本発明の他の実施例により３次元曲面形状集合から情報を取り出す動作を説明するためのフローチャートである。まず情報が埋め込まれている３次元曲面形状集合を用意し（ステップＳ３１）、３次元曲面形状集合を順序づける（ステップＳ３２）。そしてすべての３次元曲面形状から情報が取り出されているかどうかを判断し（ステップＳ３３）、取り出されていれば、取り出された情報を出力する（ステップＳ３４）。
【００３８】
ステップＳ３３で、すべての３次元曲面形状から情報が取り出されていなければ、順序にしたがって３次元曲面形状を選択し、当該３次元曲面形状のパラメトリック表現式の冗長性を有するパラメータから情報を取り出し（ステップＳ３５）、ステップＳ３３に戻る。
【００３９】
以下に、以上の３次元曲面形状集合への情報の埋め込み及び取り出しにおいて、３次元曲面形状集合を順序づけるステップが、制御点の相加平均を利用する場合と、冗長性を有するパラメータに順序を埋め込む場合についてその詳細を説明する。
【００４０】
Ｉ．制御点の相加平均を利用する場合
用意された３次元曲面形状集合がｒ個の３次元曲面形状Ｓi（１≦ｉ≦ｒ）から構成されているとする。このとき、各３次元曲面形状Ｓiのパラメトリック表現式がｓ個の制御点Ｐij（１≦ｊ≦ｓ）を有するとすれば、各３次元曲面形状の制御点の相加平均Ａは、
【００４１】
【式７】
0003995378.tif 000008
【００４２】
また、各３次元曲面形状の制御点の重心の相加平均Ｇは、
【００４３】
【式８】
0003995378.tif 000009
【００４４】
によって求められる。ここで、各３次元曲面形状について距離ｄiを
【００４５】
【式９】
0003995378.tif 000010
【００４６】
として求めれば、ｄiが小さい順（または大きい順）に３次元曲面形状集合を順序づけることができる。異なる３次元曲面形状についてｄiが一致する場合は、それらの３次元曲面形状を情報の埋め込み及び取り出しの対象外とすればよい。以上のとおり、３次元曲面形状集合を順序づければ、当該３次元曲面形状集合へ情報を埋め込むことができ、情報を埋め込んだ３次元曲面形状集合から当該情報を取り出すことができる。
【００４７】
II．冗長性を有するパラメータに順序を埋め込む方法の場合
用意された３次元曲面形状集合に情報を埋め込む際に、当該３次元曲面形状集合を、任意に定めた順序によって順序づけることができる。すなわち、当該３次元曲面形状集合を構成する各３次元曲面形状のパラメトリック表現式における冗長性を有するパラメータを、埋め込むべき情報に対応して変更する際に、当該冗長性を有するパラメーターがＬビットで表現されているとすれば、そのうちのＩビットを、任意に定めた順序を表わすインデックスに対応して変更し、残りの（Ｌ−Ｉ）ビットを、埋め込むべき情報に対応して変更すればよい。
【００４８】
用意された３次元曲面形状集合が、以上のとおり、任意に定めた順序づけによって情報が埋め込まれた３次元曲面形状集合である場合、当該３次元曲面形状集合を構成する各３次元曲面形状のパラメトリック表現式の冗長性を有するパラメータのＩビットを検出してインデックスを取り出せば、当該３次元曲面形状集合を順序づけることができ、当該３次元曲面形状集合から当該情報を取り出すことができる。
【００５０】
【発明の効果】
本発明によると、パラメトリック表現式によって表現される３次元曲面形状へ情報を埋め込むことができる。このとき、元の表現式が有理パラメトリック表現式か非有理パラメトリック表現式かに関わらず情報を埋め込むことができる。
上記の３次元曲面形状のパラメトリック表現式は、ベジェ曲面式やＢ−スプライン曲面式の場合に本発明の効果を得ることができる。
【００５１】
さらに、３次元曲面形状集合へ情報を埋め込むことができる。このとき、個々の３次元曲面形状へ埋め込むことができる情報量よりも多くの情報を埋め込むことができる。
【００５２】
また、情報を埋め込まれた３次元曲面形状から情報を取り出すことができる。
【００５３】
また、情報を埋め込まれた３次元曲面形状集合から情報を取り出すことができる。
【図面の簡単な説明】
【図１】  本発明による３次元曲面形状への情報埋め込み／取り出しを行う処理が適用される装置の一実施例におけるシステム構成を示すブロック図である。
【図２】  本発明が適用される３次元曲面形状への情報埋め込み／取り出しを行う処理が適用される装置の一実施例における機能ブロック図である。
【図３】  本発明により３次元曲面形状へ情報を埋め込む動作を説明するためのフローチャートである。
【図４】  本発明により３次元曲面形状から情報を取り出す動作を説明するためのフローチャートである。
【図５】  本発明の他の実施例によりにより３次元曲面形状集合へ情報を埋め込む動作を説明するためのフローチャートである。
【図６】  本発明の他の実施例により３次元曲面形状集合から情報を取り出す動作を説明するためのフローチャートである。
【符号の説明】
１…バス、２…ＣＰＵ、３…メモリ、４…外部記憶装置、５…入力装置、６…表示装置、１１…入力部、１２…３次元曲面形状集合順序づけ部、１３…情報埋め込み部、１４…情報取り出し部、１５…出力部、１６…表示部。
【図１】
0003995378.tif 000011
【図２】
0003995378.tif 000012
【図３】
0003995378.tif 000013
【図４】
0003995378.tif 000014
【図５】
0003995378.tif 000015
【図６】
0003995378.tif 000016