(57)【特許請求の範囲】
【請求項１】
４対１統合可能な位相構造を有する３角形ポリゴンで構成される元の３次元形状モデルのデータについて、４つの３角形ポリゴンを１つの３角形ポリゴンに統合するための変換処理を、３次元形状変換手段が行う工程と、
前記変換処理により現れなくなった頂点を終点とし、その頂点に隣接する前記変換処理後の３角形ポリゴンの３つの頂点のうちの２つの頂点を結ぶ線分の中点を始点とする変換係数ベクトルに、電子情報データ埋め込み手段が電子情報データを埋め込む工程と、
前記電子情報データを埋め込んだ変換係数ベクトルに基づいて、前記電子情報データを埋め込んだ３次元形状モデルのデータを３次元形状逆変換手段が作成する工程と
を有することを特徴とする電子情報データ埋め込み方法。
【請求項２】
前記電子情報データ埋め込み手段が前記変換係数ベクトルに電子情報データを埋め込む工程とは、
前記変換係数ベクトルのベクトル長に基づいて、前記電子情報データを埋め込む前記変換係数ベクトルを選択する工程と、
前記元の３次元形状モデルに対する埋め込んだ３次元形状モデルの頂点移動量の許容範囲に基づいて前記電子情報データをスカラー量に変換し、選択した前記変換係数ベクトルのベクトル長とその変換係数ベクトルに対応する低解像モデルの線分の線分長との線分比の値に加算する工程と、
前記電子情報データのスカラー量を加算した線分比の値に基づいて、変換係数ベクトルを作成する工程と
を有するものであることを特徴とする請求項１記載の電子情報データ埋め込み方法。
【請求項３】
前記電子情報データを埋め込む前記変換係数ベクトルを選択する工程は、変換係数ベクトルのベクトル長に基づいた選択に加え、ビット列で構成されるキーの成分に基づいた選択を行うことを特徴とする請求項２記載の電子情報データ埋め込み方法。
【請求項４】
４対１統合可能な位相構造を有する３角形ポリゴンで構成される元の３次元形状モデルのデータ及び電子情報データを埋め込んだ３次元形状モデルのデータに、それぞれ４つの３角形ポリゴンを１つの３角形ポリゴンに統合するための変換処理をオリジナルモデル変換手段が行う工程と、
変換処理により、３次元形状モデルのデータ及び電子情報データを埋め込んだ３次元形状モデルのデータからそれぞれ生成された、前記変換処理により現れなくなった頂点を終点とし、その頂点に隣接する前記変換処理後の３角形ポリゴンの３つの頂点のうちの２つの頂点を結ぶ線分の中点を始点とする変換係数ベクトルのベクトル長とその変換係数ベクトルに対応する低解像モデルの線分の線分長との線分比の値をオリジナルモデル線分比算出手段が算出する工程と、
電子情報データ抽出手段が、前記電子情報データが埋め込まれた前記変換係数ベクトルを特定し、特定した前記変換係数ベクトルに基づいて、元の３次元形状モデル及び電子情報データを埋め込んだ３次元形状モデルにおいて、それぞれ対応する線分比の差分を算出し、算出した前記差分に基づいて電子情報データを抽出する工程と
を有することを特徴とする電子情報データ抽出方法。
【請求項５】
４対１統合可能な位相構造を有する３角形ポリゴンで構成される３次元形状モデルのデータが入力されると、４つの３角形ポリゴンを１つの３角形ポリゴンに統合するための変換処理を行う３次元形状変換手段と、
該３次元形状変換手段の変換処理により現れなくなった頂点を終点とし、その頂点に隣接する前記変換処理後の３角形ポリゴンの３つの頂点のうちの２つの頂点を結ぶ線分の中点を始点とする変換係数ベクトルに電子情報データを埋め込む電子情報データ埋め込み手段と、
前記電子情報データを埋め込んだ変換係数ベクトルに基づいて、逆変換処理を行い、前記電子情報データを埋め込んだ３次元形状モデルのデータを作成する３次元形状逆変換手段と
を備えたことを特徴とする電子情報データ埋め込み装置。
【請求項６】
４対１統合可能な位相構造を有する３角形ポリゴンで構成される元の３次元形状データであるオリジナルモデルのデータが入力されると、４つの３角形ポリゴンを１つの３角形ポリゴンに統合するための変換処理により多重解像度表現を行うオリジナルモデル変換手段と、
電子情報抽出対象となる対象モデルのデータが入力されると、前記変換処理により多重解像度表現を行う対象モデル変換手段と、
前記オリジナルモデル変換手段により生成された、前記変換処理により現れなくなった頂点を終点とし、その頂点に隣接する前記変換処理後の３角形ポリゴンの３つの頂点のうちの２つの頂点を結ぶ線分の中点を始点とする変換係数ベクトルのベクトル長とその変換係数ベクトルに対応する低解像モデルの線分の線分長との線分比の値を算出するオリジナルモデル線分比算出手段と、
前記対象モデル変換手段により生成された前記変換係数ベクトルのベクトル長とその変換係数ベクトルに対応する低解像モデルの線分の線分長との線分比の値を算出する対象モデル線分比算出手段と、
前記電子情報データが埋め込まれた前記変換係数ベクトルを特定し、その変換係数ベクトルに基づいて、３次元形状モデル及び電子情報データを埋め込んだ３次元形状モデルにおいて、それぞれ対応する線分比の差分を算出して、その差分に基づいて電子情報データを抽出する電子情報データ抽出手段と
を備えたことを特徴とする電子情報データ抽出装置。
【請求項７】
請求項１〜３のいずれかに記載の電子情報データ埋め込み方法のすべての工程を、コンピュータに実行させるプログラムを記録した記録媒体。
【請求項８】
請求項４に記載の電子情報データ抽出方法のすべての工程を、コンピュータに実行させるプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ支援３次元入力システムで作成された３次元形状デジタルモデルを情報管理する方法に関するものである。特に３次元デジタルコンテンツの著作権保護等のために、電子情報データを電子透かしとして埋め込む方法である。
【０００２】
【従来の技術】
近年、テキスト、イメージ（静止画）、動画、音声等のデジタルメディアと呼ばれるデータに対し、不正な複製や編集を防止するために様々な対策が行われている。ここでは、３次元形状モデルに施される対策について考える。
【０００３】
３次元形状モデルに対して、データの不正な複製等を防止するための方法としては、３次元形状データフォーマットが有するコメントや属性のフィールドに著作権情報のデータを付加するものがある。しかし、この方法を用いたとしても、コメントや属性のフィールドは容易に削除することができ、著作権情報を付加してもすぐに取り除かれてしまうので、有効な方法とはいえない。
【０００４】
そこで、著作権情報を、電子情報データである透かしデータとしてデジタルメディアに埋め込み、ある処理を施せば、著作権情報が電子透かしとして抽出できるようにする方法がある。この方法を３次元形状モデルのデジタルメディアに利用する場合について考える。
【０００５】
透かしデータを３次元形状モデルに埋め込む方法として、３次元形状モデルを３角形ポリゴンの集合で構成し、それらの３角形ポリゴンをさらに４つの３角形に分割して、その間に構成される３角形（どの３角形ポリゴンの頂点も含まない３角形）に透かし情報データ（著作権情報）を埋め込む方法が提案されている。この方法を用いると、３次元形状モデルに影響を与えずに埋め込まれた著作権情報を取り除くのは、フィールドに著作権情報を付加したときよりも格段に難しくなる。
【０００６】
【発明が解決しようとする課題】
しかし、上記のような３角形ポリゴンを４つに分割し、その間の３角形にデータを埋め込むという方法は、３次元形状モデルの視覚的な変化に対しては何も考慮されていない。
【０００７】
したがって、透かしデータのような、形状に関するデータとは無関係のデータを冗長的に埋め込むと、透かし情報データを埋め込んだモデルの形状は、オリジナルモデルの形状とは異なる形状に変形してしまう可能性がある。また、上記の方法は、オリジナルの形状モデルの３角形ポリゴンの各頂点の座標と、それに対応した埋め込まれた後の形状モデルの各頂点の座標との差（以下、誤差という）の許容量を考慮せずに透かしデータを埋め込む。したがって、これも変形の原因となりうる。さらに、上記の方法は、透かしデータを埋め込むポリゴンの領域が局所的である。
【０００８】
したがって、当該箇所の形状に対して削除又は変形が施された場合には、埋め込んだ透かしデータも失われ、電子透かしが機能を満たせる程度に抽出できない可能性がある（つまり、変形等に関して頑強ではなくなってしまう）という問題点があった。
【０００９】
本発明は上記のような問題点を解決するためになされたものであり、３次元形状データに、著作権情報等を含む透かしデータ等の電子情報データを埋め込む場合に、埋め込んだ３次元形状モデルの視覚的変化を考慮し、誤差の制御を行うことができ、また形状モデルの削除又は変形を受けた場合でも、埋め込んだ情報が失われず、頑強な電子情報データ埋め込み方法を得ることを目的とする。
【００１０】
【課題を解決するための手段】
本発明に係る電子情報データ埋め込み方法は、４対１統合可能な位相構造を有する３角形ポリゴンで構成される元の３次元形状モデルのデータについて、４つの３角形ポリゴンを１つの３角形ポリゴンに統合するための変換処理を、３次元形状変換手段が行う工程と、変換処理により現れなくなった頂点を終点とし、その頂点に隣接する変換処理後の３角形ポリゴンの３つの頂点のうちの２つの頂点を結ぶ線分の中点を始点とする変換係数ベクトルに、電子情報データ埋め込み手段が電子情報データを埋め込む工程と、電子情報データを埋め込んだ変換係数ベクトルに基づいて、電子情報データを埋め込んだ３次元形状モデルのデータを３次元形状逆変換手段が作成する工程とを有している。
【００１１】
また、本発明に係る電子情報データ埋め込み手段が電子情報データ埋め込み方法の変換係数ベクトルに電子情報データを埋め込む工程とは、変換係数ベクトルのベクトル長に基づいて、電子情報データを埋め込む変換係数ベクトルを選択する工程と、埋め込んだ３次元形状モデルの、元の３次元形状モデルに対する頂点移動量の許容範囲に基づいて電子情報データをスカラー量に変換し、選択した変換係数ベクトルのベクトル長とその変換係数ベクトルに対応する低解像モデルの線分の線分長との線分比の値に加算する工程と、電子情報データのスカラー量を加算した線分比に基づいて、変換係数ベクトルを作成する工程とを有するものである。
【００１２】
また、本発明に係る電子情報データ埋め込み方法の電子情報データを埋め込む変換係数ベクトルを選択する工程は、変換係数ベクトルのベクトル長に基づいた選択に加え、ビット列で構成されるキーの成分に基づいた選択を行う。
【００１３】
また、本発明に係る電子情報データ抽出方法は、４対１統合可能な位相構造を有する３角形ポリゴンで構成される元の３次元形状モデルのデータ及び電子情報データを埋め込んだ３次元形状モデルのデータに、それぞれ４つの３角形ポリゴンを１つの３角形ポリゴンに統合するための変換処理をオリジナルモデル変換手段が行う工程と、変換処理により、３次元形状モデルのデータ及び電子情報データを埋め込んだ３次元形状モデルのデータからそれぞれ生成された、変換処理により現れなくなった頂点を終点とし、その頂点に隣接する変換処理後の３角形ポリゴンの３つの頂点のうちの２つの頂点を結ぶ線分の中点を始点とする変換係数ベクトルのベクトル長とその変換係数ベクトルに対応する低解像モデルの線分の線分長との線分比の値をオリジナルモデル線分比算出手段が算出する工程と、電子情報データ抽出手段が、電子情報データが埋め込まれた変換係数ベクトルを特定し、特定した変換係数ベクトルに基づいて、元の３次元形状モデル及び電子情報データを埋め込んだ３次元形状モデルにおいて、それぞれ対応する線分比の差分を算出し、算出した差分に基づいて電子情報データを抽出する工程とを有するものである。
【００１４】
また、本発明に係る電子情報データ埋め込み装置は、４対１統合可能な位相構造を有する３角形ポリゴンで構成される３次元形状モデルのデータが入力されると、４つの３角形ポリゴンを１つの３角形ポリゴンに統合するための変換処理を行う３次元形状変換手段と、３次元形状変換手段の変換処理により現れなくなった頂点を終点とし、その頂点に隣接する変換処理後の３角形ポリゴンの３つの頂点のうちの２つの頂点を結ぶ線分の中点を始点とする変換係数ベクトルに電子情報データを埋め込む電子情報データ埋め込み手段と、電子情報データを埋め込んだ変換係数ベクトルに基づいて、逆変換処理を行い、電子情報データを埋め込んだ３次元形状モデルのデータを作成する３次元形状逆変換手段とを備えている。
【００１５】
また、本発明に係る電子情報データ抽出装置は、４対１統合可能な位相構造を有する３角形ポリゴンで構成される元の３次元形状データであるオリジナルモデルのデータが入力されると、４つの３角形ポリゴンを１つの３角形ポリゴンに統合するための変換処理により多重解像度表現を行うオリジナルモデル変換手段と、電子情報抽出対象となる対象モデルのデータが入力されると、変換処理により多重解像度表現を行う対象モデル変換手段と、オリジナルモデル変換手段により生成された、変換処理により現れなくなった頂点を終点とし、その頂点に隣接する変換処理後の３角形ポリゴンの３つの頂点のうちの２つの頂点を結ぶ線分の中点を始点とする変換係数ベクトルのベクトル長とその変換係数ベクトルに対応する低解像モデルの線分の線分長との線分比の値を算出するオリジナルモデル線分比算出手段と、対象モデル変換手段により生成された変換係数ベクトルのベクトル長とその変換係数ベクトルに対応する低解像モデルの線分の線分長との線分比の値を算出する対象モデル線分比算出手段と、電子情報データが埋め込まれた変換係数ベクトルを特定し、その変換係数ベクトルに基づいて、３次元形状モデル及び電子情報データを埋め込んだ３次元形状モデルにおいて、それぞれ対応する線分比の差分を算出して、その差分に基づいて電子情報データを抽出する電子情報データ抽出手段とを備えている。
【００１６】
また、本発明に係る電子情報データ埋め込み方法のプログラムを記録した記録媒体は、上記の電子情報データ埋め込み方法のすべての工程を、コンピュータに実行させる電子情報データ埋め込み方法のプログラムを記録する。
【００１７】
また、本発明に係る電子情報データ抽出方法のプログラムを記録した記録媒体は、上記の電子情報データ抽出方法のすべての工程を、コンピュータに実行させる電子情報データ埋め込み方法のプログラムを記録する。
【００１８】
【発明の実施の形態】
実施形態１．
図１は本発明の第１の実施の形態に係る電子情報埋め込み方法及び抽出方法を実現するためのシステムのブロック図である。図において、１は３次元形状変換手段である。３次元形状変換手段１は、オリジナル３次元形状ポリゴンモデル（以下、オリジナルモデルＶ0 という）のデータについて、ウェーブレット変換を行い、多重解像度表現への変換を行う。２は電子透かし埋め込み手段である。電子透かし埋め込み手段２は、３次元形状変換手段１で多重解像度表現として表されたデータに、著作権情報等を表す電子透かしとなる透かしデータＢを埋め込む。３は３次元形状逆変換手段である。３次元形状逆変換手段３は、透かしデータＢを埋め込んだ後のデータに、逆変換を行い、実際に頒布等を行う３次元形状ポリゴンモデル（以下、流通モデルＶ’0 という）のデータを作成する。４は透かし情報抽出手段である。透かし情報抽出手段４は、電子透かしを抽出しようとする対象のモデル（以下、対象モデルＶ”0 という）から透かしデータＢを抽出する。
【００１９】
図２は電子透かし埋め込み手段２の構成を表すブロック図である。図において、２Ａは線分比算出部である。線分比算出部２Ａは、３次元形状変換手段１により算出された変換係数ベクトル（以下、変換係数ベクトルという）のノルム（ベクトル長）と、ある線分長との線分比を算出する。２Ｂは係数選択部である。係数選択部２Ｂは、透かしデータＢを埋め込む変換係数ベクトルを選択する。２Ｃは透かしデータ埋め込み部である。透かしデータ埋め込み部２Ｃは、係数選択部２Ｂが選択した変換係数ベクトルとある線分長との線分比に対し、透かしデータを埋め込む。２Ｄは係数ベクトル作成部である。埋め込んだ後の線分比に基づいて、あらためて変換係数ベクトルを作成する。
【００２０】
図３は透かし情報抽出手段４の構成を表すブロック図である。図において、４Ａはオリジナルモデル変換部である。オリジナルモデル変換部４Ａは、３次元形状変換手段１と同様に、オリジナルモデルＶ0 のデータについて、変換を行い、多重解像度表現を行う。４Ｂは対象モデル変換部である。対象モデル変換部４Ｂも、対象モデルＶ”0 のデータについて、変換を行い、多重解像度表現を行う。４Ｃはオリジナルモデル線分比算出部である。オリジナルモデル線分比算出部４Ｃは、線分比算出部２Ａと同じように、オリジナルモデル変換部４Ａが算出した変換係数ベクトルとある線分長との比を算出する。４Ｄは対象モデル線分比算出部である。対象モデル線分比算出部４Ｄも、対象モデル変換部４Ｂが算出した変換係数ベクトルとある線分長との比を算出する。４Ｅは透かしデータ抽出部である。オリジナルモデル線分比算出部４Ｃ及び対象モデル線分比算出部４Ｄがそれぞれ算出した比に基づいて、透かしデータＢを抽出する。
【００２１】
図４は本発明の入出力構成を示すシステムのブロック図である。図において、４０１はコマンド解析／処理部である。コマンド解析／処理部４０１は、入出力機構４０５を介して表示装置４０６、マウス４０７及びキーボード４０８と接続され、入力されるコマンドの解析及び処理を行う。また、３次元形状のデータに基づいて表示装置４０６への３次元形状の表示処理を行ったり、透かしデータＢに基づいて電子透かしの表示処理を行ったりする。４０２は幾何処理部である。幾何処理部４０２は、本実施の形態の埋め込み方法や抽出方法に基づいて、実際に３次元オリジナル形状モデルに透かしデータＢを埋め込んだり、透かしデータＢを抽出したりする部分である。４０３は記憶処理部である。記憶処理部２０３は、図形記憶領域４０４にオリジナルモデルＶ0 のデータや透かしデータＢを埋め込んだ３次元形状モデルのデータ等を記憶するための処理を行う。４０５は入出力機構である。入出力機構４０５は、コマンド解析／処理部４０１、幾何処理部４０２、記憶処理部４０３及び図形情報記憶領域４０４により構築された部分と表示装置４０６、マウス４０７及びキーボード４０８とのインターフェイスとなる部分である。
【００２２】
図５は図４のシステムを実際にハード構成する場合の計算機システムの構成図である。本実施の形態の電子情報データを埋め込んだり、抽出したりする方法は、実際には、例えばＣＰＵを有するコンピュータ上で埋め込み又は抽出を行うためのプログラムに基づいて処理されることになる。図５では中央計算機５０１、主記憶装置５０２、入出力制御装置５０３、マウス４０７、キーボード４０８、外部記憶装置５０４及び表示装置４０６をシステムバス５０５で接続した計算機システムで構成されている。またこれに類似するような計算機システムで構成される場合もある。
【００２３】
本実施の形態は、変換に基づいてオリジナルモデルＶ0 のデータを多重解像度表現のデータに変換し、その変換により生成される変換係数ベクトルのノルムとその変換係数ベクトルに対応して定められる線分長との線分比を算出し、その線分比に対して誤差の許容量を考慮しつつ、透かしデータＢを埋め込んでいくものである。埋め込んで作成された線分比に基づいて、あらためて変換係数ベクトルを作成し、その変換係数ベクトルで逆変換を施して流通モデルＶ’0 として作成する。線分比に埋め込みを行うので、形状の全体の拡大縮小（一様のスケーリング）等のアフィン変換に対しても耐性を保つことができる。
【００２４】
また、透かしデータＢを抽出する場合、対象モデルＶ”0 （例えば、流通モデルＶ’0 と同一のものか又は流通モデルＶ’0 に対して削除、変形等を施したもの）に対して、変換を行い、線分比を算出し、オリジナルモデルＶ0 の線分比との差分を算出する。この差分値に基づいて、変換係数ベクトルに埋め込まれた透かしデータＢを抽出して電子透かしとして表示を行うものである。
【００２５】
次に上記の図に基づいて、電子情報データの埋め込み方法について説明する。記憶処理部４０３等から３次元形状変換手段１に、オリジナルモデルＶ0 のデータが入力される。その際、解像度表現を行う最大レベルｄも定められる。ここで、オリジナルモデルは、３角形ポリゴンの面数が４d で割り切れるような位相構造を有していることが条件となる。これは、後に示すように変換を用いて３角形ポリゴンの４対１統合処理を行うためである。ここで、オリジナルモデルＶ0 のデータとは、例えば、各頂点の座標値及びその座標値の関係（どの３つの座標値で３角形ポリゴンの頂点を形成するか）を行列で表現したデータのことである。
【００２６】
３次元形状変換手段１は、変換処理を行って、３角形ポリゴンの４対１統合処理を行う。４対１統合処理とは、隣接する４つの３角形ポリゴンを１つの３角形ポリゴンに近似し、統合する処理である。
【００２７】
図６は、変換による３角形ポリゴンの４対１統合を表す図である。３次元形状変換手段１は、４対１統合処理により、オリジナルモデルＶ0 上の４つの３角形ポリゴンを、より平坦な１つの３角形に近似する。この部分は形状モデルの低周波成分を表すものである。また、４つの３角形ポリゴンを平坦な１つの３角形ポリゴンとして近似することにより、元の４つの３角形ポリゴンの凹凸は失われる。この失われた凹凸が変換係数ベクトルとして表される。したがって、変換係数ベクトルは、形状モデルの高周波成分を表すものである。このように、ウェーブレット変換は、形状モデルの周波数成分を分離することができる。ここで、高周波成分である変換係数ベクトルの大きさが大きい部分は、形状の細かい凹凸や起伏が激しい部分を表す。このような部分に若干の変化が生じていても、人間の視覚には影響が少ない。その点で高周波部分は、透かしデータを埋め込む部分としては都合がよい。透かしデータを埋め込むために高周波数成分の大きさの評価が行いやすいという点で、ウェーブレット変換は透かしデータの埋め込みに適している。
【００２８】
４対１統合処理により、オリジナルモデルＶ0 を低解像レベルに近似し、その際に失われた詳細部を変換係数ベクトルとして表す。これを、最大レベルｄまで行う。ここで、３次元ポリゴン形状モデルの変換は、次式（１）及び（２）により行われる。ここで、Ｖj は解像度レベルｊにおけるモデルを表す行列である。また、Ａj+1 は、低解像レベルへの近似Ｖj+1 （低周波成分）を算出するための解析フィルタである。さらに、Ｂj+1 は、Ｖj+1 への近似の際に、失われたＶj の詳細部を有する変換係数ベクトルＷj+1 （高周波成分）を算出するための解析フィルタである。
Ｖj+1 ＝Ａj+1 Ｖj                                           …（１）
Ｗj+1 ＝Ｂj+1 Ｖj                                           …（２）
【００２９】
図７は３次元ポリゴンモデルの多重解像度表現を表す図である。逆変換は、次式（３）で表される。ここで、Ｐj+1 は、Ｖj+1 の３角形の頂点の間に新たな中点を作り出す再構成フィルタである。また、Ｑj+1 は、その新たな中点の位置を、その解像度のモデルがもっていた元の頂点位置まで補正するための再構成フィルタである。
Ｖj ＝Ｐj+1 Ｖj+1 ＋Ｑj+1 Ｗj+1                             …（３）
【００３０】
Ｌａｚｙウェーブレットを用いた場合、変換係数ベクトルは、４対１統合されるときに低解像度では現れない頂点を終点とし、その頂点に隣接する低解像度でも残った２つの頂点（統合処理された後の３角形ポリゴンの３つの頂点のうちの２つ）を結ぶ線分の中点を始点とするベクトルとなる。
【００３１】
４対１統合処理により、少なくとも低解像近似モデルＶd 並びに各解像レベルの変換係数ベクトル及び線分長を有する多重解像度表現のデータは、電子透かし埋め込み手段２に送信される。また、ビット列数ｋの集合で構成された透かしデータＢが電子透かし埋め込み手段２に入力される。また、その際に、オペレータが指定するモデル全体の誤差許容量εも定められる。
【００３２】
図８は線分比算出部２Ａが算出する線分比の対象となる２つの線分長を表す図である。ここで、ｉは頂点のインデックスを表す。線分比算出部２Ａは、オリジナルモデルについて、変換係数ベクトルのノルム‖ｗi j ‖と低解像レベルで残った２つの頂点を結ぶ線分の線分長ｌi j との線分比を算出する。線分比をαi j とすると、次式（４）で表される。
αi j ＝‖ｗi j ‖／ｌi j                                   …（４）
【００３３】
ここで、オリジナルモデルの線分比αi j を算出するのは、透かし情報が埋め込まれた後に逆変換により新たに生成した頂点の座標（つまり、１レベル高解像になったときに生成される座標）に隣接する低解像度レベルの頂点の座標は、オリジナルモデルの対応する頂点の座標との間でずれが生じているからである。ずれを含んだ頂点を結ぶ線分との線分比を算出したとしても、オリジナルモデルの線分比を用いて透かし情報データを抽出するのは不可能である。透かし情報データを抽出するには、透かしデータＢを埋め込む前の線分比が、オリジナルモデルの対応する線分比と等しくなければならない。そのために、線分比は、オリジナルモデルのものを用いるのである。このように、変換係数ベクトルのノルムに基づいて埋め込みを行うので、剛体変換に対しても耐性をもたせられる。また、線分比を透かしデータＢの埋め込みに用いることにより、一様のスケーリング等に対して耐性をもたせられる。したがって、頑強な電子透かしを埋め込むことができる。
【００３４】
一方、係数選択部２Ｂは、透かしデータＢを埋め込む変換係数ベクトルを選択する。これは、上述しているように、形状モデルの変化の起伏が激しい（つまり、変換係数ベクトルのノルムが大きい）部分に透かしデータＢを埋め込んでも、人間の視覚に与える影響が少ないと考えられるからである。また、ここで抽出の際の鍵ともなる埋め込みキーＣを用いることにする。埋め込みキーＣは、例えば、Ｃ＝（１０１１００１…）のようなランダムなビット列である。
【００３５】
まず、各変換係数ベクトルと埋め込みキーＣの各成分とを対応させる。そして、埋め込みキーＣの１の成分と対応する変換係数ベクトルを取り出す。取り出した変換係数ベクトルに対して、変換係数ベクトルのノルム‖ｗi j ‖を算出し、ノルムがある基準よりも大きな変換係数ベクトルを埋め込みを行う変換係数ベクトルとして選択する。ここで、ある基準としては、別途指定した埋め込み下限値であるμを採用し、‖ｗi j ‖＞μを満たす変換係数ベクトルを選択する。このようにして選択された変換係数ベクトルに対し、透かしデータＢが埋め込まれる。
【００３６】
ここで、Ｌａｚｙウェーブレットを用いた場合、変換係数ベクトルの最大許容誤差δ及び最大レベルｄにより、オリジナルモデルＶ0 に対する埋め込みが行われた３次元形状モデル（流通モデルＶ’0 ）の頂点移動量の最大値をΔMAX とすると、ΔMAX は次式（５）で表される。
ΔMAX ＝（ｄ＋１）・δ／２                                  …（５）
【００３７】
オペレータが指定した形状全体の誤差許容量εは、ΔMAX ≦εを満たせばよいので、これを用いて変換係数に対する最大許容誤差δを表すと、次式（６）のようになる。（６）式から変換係数ベクトルの最大許容誤差δを算出する。このδの値を変換係数ベクトルの透かしデータ埋め込みによって生ずる最大許容誤差値とする。
δ＝２ε／（ｄ＋１）                                        …（６）
【００３８】
透かしデータ埋め込み部２Ｃは、選択された変換係数ベクトルの線分比αi j に対し、透かしデータＢの埋め込みを行う。透かしデータＢの埋め込みは次のようにして行う。（６）式により、各頂点の埋め込みにより生じる最大許容誤差δの上限が制限されていることから、選択されたすべての変換係数ベクトルに対して同じオーダーで透かしデータＢを埋め込むことができる。変換係数ベクトルのノルム‖ｗi j ‖を１０p オーダー（例えば、‖ｗi j ‖＝０．０２１ならば、ｐ＝−２）、最大許容誤差δを１０r オーダー（例えば、δ＝０．００００５２ならば、ｒ＝−５）、埋め込みにより生じる変換係数ベクトルのノルムの変化の下限値μを１０q オーダー（例えば、μ＝０．０００００００７１ならば、ｑ＝−８）とする。ここでｐ＞ｒ＞ｑである。線分比αi j を１０s オーダーとすると、埋め込まれる透かしデータＢによるベクトル長の変化は、線分比αi j に対するオーダーでは、１０r-p+s 〜１０q-p+s のオーダーの範囲内であることが必要条件となる。これは、１０p オーダーの‖ｗi j ‖に対して、埋め込まれる透かしデータＢが１０r 〜１０q オーダーの範囲にあるという関係を有するからである。これを１０s オーダーである線分比αi j に対応させた場合に、（４）式よりｌi j は１０p-s オーダーとなるので、線分比αi j に対しては、１０r-p+s 〜１０q-p+s のオーダーの範囲内であることが必要となる。また、透かしデータＢの下限値μを設定したのは、透かしデータＢの埋め込みにより、３角形ポリゴンの各頂点の座標値を操作することになるので、計算誤差に含まれる可能性が大きい最下位ビット付近を使用しないようにするためである。
【００３９】
透かしデータＢのｋビット（ｋ≦ｒ−ｑ）のビット列（ｂ1 ，…，ｂk ）を線分比に埋め込むために、次式（７）により、ビット列をスカラー量βi j として算出し、次式（８）のようにαi j に加算する。透かしデータＢが埋め込まれない線分比に関しては、スカラー量βi j ＝０である。
βi j ＝ｂ1 ×１０r-p+s ＋ｂ2 ×１０r-p+s-1 ＋…＋ｂk ×１０r-p+s-k+1 …（７）
【００４０】
【数１】
0004189705.tif 000002
【００４１】
係数ベクトル作成部２Ｄは、（８）式により算出された線分比に基づいて、新たに透かしデータＢを埋め込んだ変換係数ベクトルを次式（９）により作成する。
【００４２】
【数２】
0004189705.tif 000003
【００４３】
３次元形状逆変換手段３は、係数ベクトル作成部２Ｄにより作成された変換係数ベクトルについて逆変換を行う。逆変換は、式（２）と同様の関係を有する次式（１０）で表される。
【００４４】
【数３】
0004189705.tif 000004
【００４５】
次に図１及び図３に基づいて、透かし情報抽出手段４による電子透かしの抽出方法について説明する。対象モデルＶ”0 からの電子透かし抽出には、オリジナルモデルＶ0 が必要となる。オリジナルモデル変換部４Ａは、３次元形状変形手段１と同様に、（１）式及び（２）式に基づいてオリジナルモデルＶ0 のデータの４対１統合処理により、多重解像度表現を行う。また、対象モデル変換部４Ｂについても、対象モデルＶ”0 のデータの４対１統合処理を行う。
【００４６】
オリジナルモデル線分比算出部４Ｃは、オリジナルモデル変換部４Ａから多重解像度表現のデータ（ここでは、変換係数ベクトルｗi j 及び線分長ｌi j ）が送信されると、線分比算出部２Ａと同様に、（４）式に基づいてオリジナルモデルにおける線分比を算出する。また、対象モデル線分比算出部４Ｄも、線分比算出部２Ａと同様に、（４）式に基づいて対象モデルにおける線分比を算出する。
【００４７】
透かし情報抽出部４Ｅは、埋め込みキーＣ及び誤差許容量εにより算出された最大許容誤差δに基づいて、係数選択部２Ｂで選択された変換係数ベクトルを特定する。これは、たとえ、埋め込み時に透かしデータＢを埋め込む変換係数ベクトルとして選択されずに透かしデータが埋め込まれなかった変換係数ベクトルであっても、逆変換等の過程で、埋め込みの影響により頂点がずれて線分長ｌi j が変わることがあり、その線分比は、オリジナルモデルと同じ線分比となるとは限らなくなるからである。そのため、埋め込みにより線分比間に差分が生じたものと線分長ｌi j が変わることにより線分比間に差分が生じたものとを区別し、選択された変換係数ベクトルを特定する必要がある。
【００４８】
変換係数ベクトルが特定されると、その変換係数ベクトルにおいて、オリジナルモデル線分比算出部４Ｃが算出した線分比と対象モデル線分比算出部４Ｄが算出した線分比のそれぞれ対応するものの差分を算出する。この差分は、スカラー量βi j を表す。誤差許容量ε、ビット列数ｋ及びオリジナルモデルの多重解像度表現のデータにより、埋め込みが行われたオーダーが算出可能である。そこで（７）式に基づいて、透かしデータＢのビット列（ｂ1 ，…，ｂk ）を算出する。これを繰り返し、透かしデータＢを抽出する。抽出された透かしデータＢに基づいて、表示装置４０６に電子透かしが表示される。
【００４９】
図９は本実施の形態の透かしデータの埋め込み方法及び抽出方法の操作環境を示す図である。透かしデータＢの埋め込みを誤差許容量εを変えながら行ったものである。ε＝０．０１では、オリジナルモデルＶ0 と見分けがつかない状態となっている。オペレータは、流通モデルＶ’0 として頒布できると判断するまで、各パラメータを変えながら、透かしデータＢの埋め込み処理を繰り返し行い、流通モデルＶ’0 を作成する。流通モデルＶ’0 は、剛体変換やスケーリング等のアフィン変換等により様々に変換可能である。このような変換を行ったとしても、電子透かしの抽出対象となる対象モデルＶ”0 からは、透かしデータＢが抽出でき、電子透かしを表示することができる。
【００５０】
以上のように第１の実施の形態によれば、３次元形状変換手段１が、４対１統合可能な位相構造をもつ３角形ポリゴンのオリジナルモデルＶ0 のデータに変換処理を施して多重解像度表現のデータとし、電子透かし埋め込み手段２が、３次元形状モデルの形状の変化が激しい部分を表す変換係数ベクトルに透かしデータを埋め込み、３次元形状逆変換手段３が、透かしデータを埋め込んだ３次元形状モデルのデータを作成するようにしたので、視覚的な変化の影響をほとんど受けずに透かしデータを埋め込むことができる。また、低解像の変換係数に透かしデータを埋め込むことにより、広範囲に透かしデータを埋め込むことが可能となるので、局所的な削除、剛体変形、アフィン変換等に耐性をもたせることができ、頑強な電子透かしを得ることができる。また、電子透かし埋め込み手段２の線分比算出部２Ａが、オリジナルモデルについて、変換係数ベクトルのノルム‖ｗi j ‖と低解像レベルで残った２つの頂点を結ぶ線分の線分長ｌi j との線分比αi j を算出し、係数選択部２Ｂが、透かしデータを埋め込む変換係数ベクトルを選択し、透かしデータ埋め込み部２Ｃが、誤差許容量εに基づいて、ビット列の透かしデータをスカラー量βi j に変換し、線分比αi j に加算して新たな変換係数ベクトルを作成するようにしたので、透かしデータを埋め込んだ後の頂点移動量を制御することができ、適切な範囲内での制御を行うことができる。したがって、３次元形状モデルの視覚的な変化の影響をほとんど受けることなく、透かしデータを埋め込むことができる。また変換係数ベクトルの選択には、ランダムなビット列の埋め込みキーＣを用いるので、埋め込みキーＣの保持者だけが透かしデータの抽出を行うこともでき、セキュリティ、秘密保護等に役立つ。４対１統合可能な位相構造をもつ３角形ポリゴンでオリジナルモデルを構成することにより、変換を用いて多重解像度表現を行うことが容易となる。
【００５１】
さらに、透かしデータ抽出手段４のオリジナルモデル変換部４Ａ及び対象モデル変換部４Ｂが、変換により、それぞれのモデルのデータを多重解像度表現のデータに変換し、オリジナルモデル線分比算出部４Ｃ及び対象モデル線分比算出部４Ｄにより、それぞれの変換係数ベクトルに基づいた線分比を算出し、透かしデータ抽出部４Ｅが許容誤差ε、埋め込みキーＣ等に基づいて、埋め込みが行われた変換係数ベクトルを特定し、その変換係数ベクトルの差分を算出して、それぞれの変換係数ベクトルからビット列の透かしデータを抽出し、全体としての透かしデータを抽出するようにしたので、埋め込まれた電子情報データを効率よく抽出することができる。
【００５２】
実施形態２．
なお、上述の第１の実施の形態においては、変換を行うのに、Ｌａｚｙウェーブレットを用いたが、本発明はそれに限定されるものではなく、球面ウェーブレット、ｋ−ｄｉｓｋウェーブレット等、他のウェーブレットでも適用が可能である。ただ、Ｌａｚｙウェーブレットでは、変換係数ベクトルは、４対１統合されるときに低解像レベルでは現れない頂点を終点とし、その頂点に隣接する低解像レベルで残った２つの頂点（統合された後の３角形ポリゴンの３つの頂点のうちの２つ）を結ぶ線分の中点を始点とするベクトルとして表される。このため、変換係数ベクトルのもつ幾何学的な意味（低解像にすることにより失われる高解像部分の詳細表示）が明確である。それに比べて、他のウェーブレットでは変換係数ベクトルの意味が直感的に理解しづらくなる。また、このため、頂点移動量の最大値をΔMAX と最大許容誤差δとの関係を表す（５）式を用いて誤差制御ができなくなる。したがって、他のウェーブレットを用いる場合は（５）式及び（６）式の部分は、別の式を用いる必要がある。
【００５３】
実施形態３．
上述の実施の形態では、１つの透かしデータを用いて埋め込みを行ったが、本発明ではこれに限定されるものではなく、誤差の範囲内で、複数の透かしデータを用いて埋め込みを行うことも可能である。
【００５４】
実施形態４．
上述の実施の形態では、変換係数ベクトルの選択に埋め込みキーＣを用いたが、これは、セキュリティを高めるために用いたものであって、選択には必ず必要なものではない。したがって、埋め込みキーＣを用いなくても、変換係数ベクトルを選択することができる。
【００５５】
【発明の効果】
以上のように本発明によれば、３次元形状モデルのデータに変換処理を施し、３次元形状モデルの形状の変化が激しい部分となる変換係数ベクトルに電子情報データを埋め込んで、電子情報データを埋め込んだ３次元形状モデルのデータを作成するようにしたので、視覚的な変化の影響をほとんど受けずに電子情報データを埋め込むことができる。低解像の変換係数に埋め込むことにより、大域的に電子情報データを埋め込むことが可能となるので、局所的な削除、変形等に耐性をもたせることができ、頑強な電子透かし等の電子情報を得ることができる。
【００５６】
また、本発明によれば、元の３次元形状を４対１統合可能な位相構造をもつ３角形ポリゴンで構成するので、変換を用いて多重解像度表現を行うことが容易となる。
【００５７】
また、本発明によれば、変換処理において、電子情報データ埋め込みによる３次元形状モデルの頂点の移動量の制御を単純な式に基づいて行うことができる。
【００５８】
また、本発明によれば、電子情報データを埋め込む際に、電子情報データを埋め込む変換係数ベクトルを選択し、頂点移動量の許容範囲に基づいて電子情報データをスカラー量に変換して線分比の値に加算してその線分比に基づいて、電子情報データを埋め込んだ変換係数ベクトルを作成するようにしたので、電子情報データを埋め込んだ後の頂点移動量を制御することができ、適切な範囲内での制御を行うことができる。したがって、３次元形状モデルの視覚的な変化の影響をほとんど受けることなく、電子情報データを埋め込むことができる。
【００５９】
また、本発明によれば、電子情報データを埋め込む変換係数ベクトルの選択にビット列で構成されるキーの成分に基づいた選択を行うようにしたので、キーをランダムに定めることにより、キーの保持者だけが電子情報データの抽出を行うこともでき、セキュリティ、秘密保護等に役立つ。
【００６０】
また、本発明によれば、３次元形状モデルのデータ及び電子情報データを埋め込んだ３次元形状モデルのデータに、それぞれ変換処理を行い、それぞれの線分比の値を算出し、電子情報データが埋め込まれた変換係数ベクトルを特定して、その変換係数ベクトルに対し、線分比の値の差分を算出して電子情報データを抽出するようにしたので、変換処理により、埋め込まれた電子情報データを効率よく抽出することができる。
【００６１】
また、本発明によれば、３次元形状変換手段が４対１統合可能な位相構造を有する３角形ポリゴンで構成される３次元形状モデルのデータを変換し、電子情報データ埋め込み手段が変換係数ベクトルに電子情報データを埋め込んで、３次元形状逆変換手段が、電子情報データを埋め込んだ変換係数に逆変換処理を行い、電子情報データを埋め込んだ３次元形状モデルのデータを作成するようにしたので、３次元形状モデルが４対１統合可能な位相構造を有する３角形ポリゴンであることが条件となるが、視覚的な変化の影響をほとんど受けない、しかも局所的な削除、変形等に耐性をもたせた頑強な電子情報を得ることができる。
【００６２】
また、本発明によれば、オリジナルモデル変換手段が、元の３次元形状データを変換し、また、対象モデル変換手段が、電子情報抽出対象となる対象モデルのデータを変換し、オリジナルモデル線分比算出手段及び対象モデル線分比算出手段がそれぞれ線分比を算出して、電子情報データ抽出手段が、電子情報データが埋め込まれた変換係数ベクトルを特定し、その変換係数ベクトルの３次元形状モデル及び電子情報データを埋め込んだ３次元形状モデルの、それぞれ対応する線分比の値の差分を算出して、その差分に基づいて電子情報データを抽出するようにしたので、変換処理により、埋め込まれた電子情報データを効率よく抽出することができる。
【００６３】
また、本発明の記録媒体は、３次元形状モデルのデータに変換処理を施させ、３次元形状モデルの形状の変化が激しい部分となる変換係数ベクトルに電子情報データを埋め込ませ、電子情報データを埋め込んだ３次元形状モデルのデータを作成させるようにコンピュータに実行させるプログラムを記録しているので、視覚的な変化の影響をほとんど受けずに、電子情報データを埋め込むことができる。しかも埋め込まれた電子情報データは局所的な削除、変形等に耐性をもたせたものとなるので、頑強な電子透かし等の電子情報を得ることができる。
【００６４】
また、本発明の記録媒体は、３次元形状モデルのデータ及び電子情報データを埋め込んだ３次元形状モデルのデータに、それぞれ変換処理を行わせ、それぞれの線分比を算出させ、電子情報データが埋め込まれた変換係数ベクトルを特定させて、その変換係数ベクトルに対し、線分比値の差分を算出させて電子情報データを抽出させるようにコンピュータに実行させるプログラムを記録しているので、変換処理を行わせることにより、埋め込まれた電子情報データを効率よく抽出することができる。
【図面の簡単な説明】
【図１】  本発明の第１の実施の形態に係る電子情報埋め込み方法及び抽出方法を実現するためのシステムのブロック図である。
【図２】  透かし情報埋め込み手段２の構成を表すブロック図である。
【図３】  透かし情報抽出手段４の構成を表すブロック図である。
【図４】  本発明の入出力構成を示すシステムのブロック図である。
【図５】  図４のシステムを実際にハード構成する場合の構成図である。
【図６】  変換による３角形ポリゴンの４対１統合を表す図である。
【図７】  ３次元ポリゴンモデルの多重解像度表現を表す図である。
【図８】  線分比算出部２Ａが算出する線分比の対象となる２つの線分長を表す図である。
【図９】  操作環境を示す図である。
【符号の説明】
１  ３次元形状変換手段
２  電子透かし埋め込み手段
２Ａ  線分比算出部
２Ｂ  係数選択部
２Ｃ  透かしデータ埋め込み部
２Ｄ  係数ベクトル作成部
３  ３次元形状逆変換手段
４  透かし情報抽出手段
４Ａ  オリジナルモデル変換部
４Ｂ  対象モデル変換部
４Ｃ  オリジナルモデル線分比算出部
４Ｄ  対象モデル線分比算出部
４Ｅ  透かし情報抽出部
【図１】
0004189705.tif 000005
【図２】
0004189705.tif 000006
【図３】
0004189705.tif 000007
【図４】
0004189705.tif 000008
【図５】
0004189705.tif 000009
【図６】
0004189705.tif 000010
【図７】
0004189705.tif 000011
【図８】
0004189705.tif 000012
【図９】
0004189705.tif 000013