(57)【要約】【課題】３次元形状モデルに対し、その形状を変形したりすること無く、また３角形ポリゴンメッシュで表現できないようなデータについても透かし情報を埋め込み、またこの情報を抽出することができる情報埋込装置並びに情報抽出装置を提供する。【解決手段】３次元形状モデルへ透かし情報を埋め込むときには、透かし情報を入力し、３次元形状モデルの要素のインデックス値に透かし情報を付加して変更することにより、透かし情報を３次元形状モデルに埋め込む。また、３次元形状モデルへ埋め込まれた透かし情報を抽出するときには、３次元形状モデルから透かし情報を付加されたインデックス値をもつ要素を抽出し、該要素のインデックス値から透かし情報を抽出して出力するようにした。【選択図】図１
2005269244.tif 000002
【特許請求の範囲】
【請求項１】
３次元形状モデルへ透かし情報を埋め込む情報埋込装置であって、透かし情報を入力する透かし情報入力手段と、前記３次元形状モデルの要素のインデックス値に前記透かし情報を付加して変更することにより、前記透かし情報を前記３次元形状モデルに埋め込む透かし情報埋込手段とを備えることを特徴とする情報埋込装置。
【請求項２】
請求項１に記載の情報埋込装置において、前記３次元形状モデルの要素を順序付ける要素順序付手段を備え、前記透かし情報埋込手段は、前記要素順序付手段で順序付けられた要素のインデックス値に前記透かし情報を付加するようにしたことを特徴とする情報埋込装置。
【請求項３】
請求項１または２に記載の情報埋込装置において、前記３次元形状モデルを構成する要素は、頂点、稜線、面、多角形、曲線、曲面のいずれかであることを特徴とする情報埋込装置。
【請求項４】
請求項２に記載の情報埋込装置において、前記要素順序付手段は、前記３次元形状モデルの座標系の原点から各要素の座標までの距離をもとに該要素を順序付けるようにしたことを特徴とする情報埋込装置。
【請求項５】
３次元形状モデルへ埋め込まれた透かし情報を抽出する情報抽出装置であって、前記３次元形状モデルから前記透かし情報を付加されたインデックス値をもつ要素を抽出し、該要素のインデックス値から透かし情報を抽出する透かし情報抽出手段と、前記抽出した透かし情報を出力する透かし情報出力手段とを備えたことを特徴とする情報抽出装置。
【請求項６】
請求項５に記載の情報抽出装置において、前記透かし情報抽出手段で抽出した要素を順序付ける抽出要素順序付手段を備え、前記透かし情報抽出手段は、前記抽出要素順序付手段で順序付けられた要素の順序で、抽出した透かし情報を並び替えるようにしたことを特徴とする情報抽出装置。
【請求項７】
請求項５または６に記載の情報抽出装置において、前記３次元形状モデルを構成する要素は、頂点、稜線、面、多角形、曲線、曲面のいずれかであることを特徴とする情報抽出装置。
【請求項８】
請求項６に記載の情報抽出装置において、前記抽出要素順序付手段は、前記３次元形状モデルの座標系の原点から各要素の座標までの距離をもとに該要素を順序付けるようにしたことを特徴とする情報抽出装置。
【請求項９】
３次元形状モデルへ透かし情報を埋め込む情報埋込方法であって、透かし情報を入力し、前記３次元形状モデルの要素のインデックス値に前記透かし情報を付加して変更することにより、前記透かし情報を前記３次元形状モデルに埋め込むことを特徴とする情報埋込方法。
【請求項１０】
３次元形状モデルへ埋め込まれた透かし情報を抽出する情報抽出方法であって、前記３次元形状モデルから前記透かし情報を付加されたインデックス値をもつ要素を抽出し、該要素のインデックス値から透かし情報を抽出して出力することを特徴とする情報抽出方法。
【請求項１１】
３次元形状モデルへ透かし情報を埋め込むとともに、透かし情報を埋め込まれた３次元形状モデルから透かし情報を抽出する情報埋込抽出システムであって、透かし情報を入力する透かし情報入力手段と、前記３次元形状モデルの要素のインデックス値に前記透かし情報を付加して変更することにより、前記透かし情報を前記３次元形状モデルに埋め込む透かし情報埋込手段と、前記３次元形状モデルから前記透かし情報を付加されたインデックス値をもつ要素を抽出し、該要素のインデックス値から透かし情報を抽出する透かし情報抽出手段と、前記抽出した透かし情報を出力する透かし情報出力手段とを備えたことを特徴とする情報埋込抽出システム。
【請求項１２】
コンピュータに、請求項１乃至４のいずれかに記載の情報埋込装置の機能、または、請求項５乃至８のいずれかに記載の情報抽出装置の機能、または、請求項１１に記載の情報埋込抽出システムの機能を実行させるためのプログラム。
【請求項１３】
請求項１２に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報埋込装置および情報埋込方法、並びに、情報抽出装置および情報抽出方法、並びに、情報埋込抽出システム、並びに、プログラムおよび記録媒体に関し、特に、３次元形状モデルを定義するデータの中に、著作権やその他の情報を埋め込む技術および埋め込まれた情報を抽出する技術に関する。
【背景技術】
【０００２】
３次元形状モデルは、工業製品をはじめさまざまな設計の分野で利用の普及がすすんでいる。この３次元形状モデルは、製品の設計データとしての位置付けにあるものが多いので、機密度の高い情報として扱われる機会が増えている。
【０００３】
これまでにも、機密の高い電子文書が意図せず漏洩したり、改竄されてしまった場合の対策として、何らかの方法で透かし情報を埋め込む以下のような種類の方法が提案されている。
【０００４】
（１）テキスト文章に埋め込む方法（特許文献１）。
特許文献１は、情報を埋め込むときには、ある単語の前にある空白の長さとその単語に引き続く空白の長さの組み合わせを１つの符号単位とし、前後の長さの比率を署名データのビット値に応じて変化させることで、符号に著作権を保護するための証明データを埋め込む。また、抽出するときには、単語の前後の空白の長さの比率の違いに応じて署名データを抽出する。これにより、第３者に見破られることなく、多くの署名情報を電子文書内に埋め込むことができる。
【０００５】
（２）画像に埋め込む方法（非特許文献１）
非特許文献１は、２次元の静止画像を構成する各ピクセルの明度をわずかに変更して透かし情報を埋め込む。
【０００６】
３次元形状モデルそのものに透かし情報を埋め込む方法としては、形状モデルを定義するパラメータの冗長性に情報を埋め込む方法が一般的に提案されている。
【０００７】
（３）ウェーブレット変換処理を施して埋め込む方法（特許文献２）
特許文献２は、３次元形状のオリジナルモデルＶ0のデータにウェーブレット変換処理を行い、このウェーブレット変換処理により生成されるＷＴ係数ベクトルに透かしデータを埋め込んで、そのＷＴ係数ベクトルに基づいて、３次元形状逆変換手段が、透かしデータを埋め込んだ３次元形状モデル（流通モデルＶ’0 ）のデータを作成する。
これにより、視覚的な変化の影響をほとんど受けずに電子情報データを埋め込むことができる。低解像のウェーブレット係数に埋め込むことにより、大域的に電子情報データを埋め込むことが可能となるので、局所的な削除、変形等に耐性をもたせることができ、頑強な電子透かし情報を得る。
【０００８】
（４）自由曲面メッシュの制御点に埋め込む方法（特許文献３）
特許文献３は、透かし情報の埋込み用パラメータを設定し、３次元形状モデルの各曲面メッシュに対して、透かし情報の埋込み処理を行うメッシュと、埋込み処理を行わないメッシュとを選別し、選別された各曲面メッシュの集合の中の所定のメッシュに対して、埋込み用パラメータに指定された分割比率を有する制御点を新しく生成し、当該制御点が、所定の曲面上にあり、かつ、所定の曲面メッシュと同数の制御点を有する分割メッシュを生成する。
これにより、３次元形状モデルに、埋込みの前後で３次元形状モデルの形状が大略保存され、又、攻撃・侵害を受けた場合でも、埋込んだ電子透かし情報が失われたり、復元不可能とならない、攻撃に対して頑強な耐性のある電子透かし情報を得る。
【０００９】
（５）幾何・位相のパラメータを変更して埋め込む包括的方法（特許文献４）
特許文献４は、多面体、直線、点の集合、または曲面から構成される３次元形状モデルの幾何形状を定義する幾何パラメータを、頂点の座標値を微小量ずらしたり、三角形ポリゴンメッシュの分割の仕方を変更することにより、種々の情報を３次元形状モデルへ、可視または不可視の状態で埋め込む。また、幾何パラメータを数値パラメータ及び位相に分けて、各々を変更して情報を埋め込む。
逆に、抽出するときは変更された幾何パラメータを検出することにより、埋め込まれた情報を取り出す。
【特許文献１】特開平９−１８６６０３号公報
【特許文献２】特開２０００−８２１５６号公報
【特許文献３】特開２００３−９９８０５号公報
【特許文献４】特開平１０−３３４３７２号公報
【非特許文献１】小野束著、「電子透かしとコンテンツ保護」、オーム社、２００１年２月１４日、４３〜１１６頁
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述の従来の方法では、以下のような問題点があった。
まず、特許文献１または非特許文献１のようなテキスト文章や画像データへの透かし情報埋め込み方法は、３次元データの表現形式と著しく異なっているのでそのまま適用することはできない。
特許文献２の方法は、三角形ポリゴンメッシュから構成される３次元形状モデルに、特許文献３の方法は、自由曲面の集合として定義される３次元形状モデルにしか適用できないという問題がある。
【００１１】
また、特許文献４の方法では、３角形ポリゴンメッシュの分割方法を変更することによって情報を埋め込む方法が提案されており、この方法ならば形状が変更されるということはないが、３角形ポリゴンメッシュで形状が表現されないと適用できないという問題がある。もちろん、もともと自由曲面で表されるデータに対して、３角形ポリゴンメッシュへの分割処理を適宜施したり、ポリゴンメッシュ情報を保存しておくことによって埋め込むことは可能であるが、データサイズが拡大した場合に、メッシュ分割処理のオーバーヘッドや、メッシュデータの容量の増大といった弊害を招くことになる。
【００１２】
本発明は、上述のような実情を考慮してなされたものであって、３次元形状モデルに対し、その形状を変形したりすること無く、また３角形ポリゴンメッシュで表現できないようなデータについても透かし情報を埋め込み、またこの情報を抽出することができる情報埋込装置および情報埋込方法、並びに、情報抽出装置および情報抽出方法、並びに、情報埋込抽出システム、並びに、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、請求項１に記載の発明は、３次元形状モデルへ透かし情報を埋め込む情報埋込装置であって、透かし情報を入力する透かし情報入力手段と、前記３次元形状モデルの要素のインデックス値に前記透かし情報を付加して変更することにより、前記透かし情報を前記３次元形状モデルに埋め込む透かし情報埋込手段とを備えることを特徴とする。
【００１４】
請求項２に記載の発明は、請求項１に記載の情報埋込装置において、前記３次元形状モデルの要素を順序付ける要素順序付手段を備え、前記透かし情報埋込手段は、前記要素順序付手段で順序付けられた要素のインデックス値に前記透かし情報を付加するようにしたことを特徴とする。
【００１５】
請求項３に記載の発明は、請求項１または２に記載の情報埋込装置において、前記３次元形状モデルを構成する要素は、頂点、稜線、面、多角形、曲線、曲面のいずれかであることを特徴とする。
【００１６】
請求項４に記載の発明は、請求項２に記載の情報埋込装置において、前記要素順序付手段は、前記３次元形状モデルの座標系の原点から各要素の座標までの距離をもとに該要素を順序付けるようにしたことを特徴とする。
【００１７】
請求項５に記載の発明は、３次元形状モデルへ埋め込まれた透かし情報を抽出する情報抽出装置であって、前記３次元形状モデルから前記透かし情報を付加されたインデックス値をもつ要素を抽出し、該要素のインデックス値から透かし情報を抽出する透かし情報抽出手段と、前記抽出した透かし情報を出力する透かし情報出力手段とを備えたことを特徴とする。
【００１８】
請求項６に記載の発明は、請求項５に記載の情報抽出装置において、前記透かし情報抽出手段で抽出した要素を順序付ける抽出要素順序付手段を備え、前記透かし情報抽出手段は、前記抽出要素順序付手段で順序付けられた要素の順序で、抽出した透かし情報を並び替えるようにしたことを特徴とする。
【００１９】
請求項７に記載の発明は、請求項５または６に記載の情報抽出装置において、前記３次元形状モデルを構成する要素は、頂点、稜線、面、多角形、曲線、曲面のいずれかであることを特徴とする。
【００２０】
請求項８に記載の発明は、請求項６に記載の情報抽出装置において、前記抽出要素順序付手段は、前記３次元形状モデルの座標系の原点から各要素の座標までの距離をもとに該要素を順序付けるようにしたことを特徴とする。
【００２１】
請求項９に記載の発明は、３次元形状モデルへ透かし情報を埋め込む情報埋込方法であって、透かし情報を入力し、前記３次元形状モデルの要素のインデックス値に前記透かし情報を付加して変更することにより、前記透かし情報を前記３次元形状モデルに埋め込むことを特徴とする。
【００２２】
請求項１０に記載の発明は、３次元形状モデルへ埋め込まれた透かし情報を抽出する情報抽出方法であって、前記３次元形状モデルから前記透かし情報を付加されたインデックス値をもつ要素を抽出し、該要素のインデックス値から透かし情報を抽出して出力することを特徴とする。
【００２３】
請求項１１に記載の発明は、３次元形状モデルへ透かし情報を埋め込むとともに、透かし情報を埋め込まれた３次元形状モデルから透かし情報を抽出する情報埋込抽出システムであって、透かし情報を入力する透かし情報入力手段と、前記３次元形状モデルの要素のインデックス値に前記透かし情報を付加して変更することにより、前記透かし情報を前記３次元形状モデルに埋め込む透かし情報埋込手段と、前記３次元形状モデルから前記透かし情報を付加されたインデックス値をもつ要素を抽出し、該要素のインデックス値から透かし情報を抽出する透かし情報抽出手段と、前記抽出した透かし情報を出力する透かし情報出力手段とを備えたことを特徴とする。
【００２４】
請求項１２に記載の発明は、コンピュータに、請求項１乃至４のいずれかに記載の情報埋込装置の機能、または、請求項５乃至８のいずれかに記載の情報抽出装置の機能、または、請求項１１に記載の情報埋込抽出システムの機能を実行させるためのプログラムである。
請求項１３に記載の発明は、請求項１２に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００２５】
本発明によれば、３次元形状モデルに対し、その表現形式に依存せず、また形状を変形すること無く、透かし情報を埋め込み、また抽出することができる。
【発明を実施するための最良の形態】
【００２６】
以下、図面を参照して本発明の情報埋込装置および情報抽出装置に係る好適な実施形態を説明する。
図１は、本発明の実施形態に係る情報埋込装置および情報抽出装置の機能構成を示すブロック図である。同図において、情報埋込装置１０は、透かし情報入力手段１１、透かし情報変換手段１２、要素順序付手段１３、透かし情報埋込手段１４、３次元形状モデルＤＢ１５、透かし情報付３次元形状モデルＤＢ３０とから構成されている。
また、情報抽出装置２０は、透かし情報抽出手段２１、抽出要素順序付手段２２、透かし情報逆変換手段２３、透かし情報出力手段２４、透かし情報付３次元形状モデルＤＢ３０とから構成されている。
【００２７】
まず、３次元形状モデルへ透かし情報を埋め込む方法について説明する。
情報埋込装置１０は、著作権やその他の情報を透かし情報として入力し、この透かし情報を指定された３次元形状モデルに埋め込んで、透かし情報付３次元形状モデルを出力する。
３次元形状モデルＤＢ１５は、透かし情報を埋め込む対象である３次元形状モデルの幾何情報および位相情報を格納する。この３次元形状モデルＤＢ１５には、１つ以上の３次元形状モデルが格納されているので、ユーザは情報埋め込みに当たって、埋め込み対象となる３次元形状モデルをキーボードやマウスによって指定する。
【００２８】
透かし情報入力手段１１は、ユーザが指定した３次元形状モデルに埋め込むべき透かし情報をキーボードやファイルから入力する。以下の説明では、透かし情報は、テキストからなる著作権やその他の情報を対象とするものとする。
【００２９】
透かし情報変換手段１２は、入力された透かし情報を数値に変換し、埋め込める形に変換する。この変換は、可逆の変換ができればどのようなものを用いてもよい（例えば、文字コードを用いれば、この変換作業は必要がない）が、ここでは、アルファベット文字の順序を用いるものとする。
例えば、文字列「ａ−ｐ−ｐ−ｌ−ｅ」をアルファベット文字の順序の数で変換すると、「１−１６−１６−１２−５」となる（「−」は説明のための区切りで実際には挿入されない）。すべての透かし情報が数値変換されるまでこの処理を繰り返す（図２参照）。
【００３０】
要素順序付手段１３は、指定された３次元形状モデルを構成する各頂点に対して順序付けをする。この順序付けの方法は、順序が一意に決まり、透かし情報の埋め込み前後で、順序が変わらない方法であればどのような方法で求めてもよい。
ここでは、座標系の原点から頂点までの距離でソートして順序付けをする。同距離の頂点があれば、いずれか１つの頂点を採用しその他の頂点は無視し、次に距離の遠い頂点を対象とし、すべての頂点に順序付けをするまで処理を繰り返す。
【００３１】
この順序付けについて、図３を用いて説明する。図３は、８つの頂点からなり、ＸＹＺ各軸に平行で、各辺の長さがＸ＝２０，Ｙ＝２０，Ｚ＝３０であり、頂点インデックスが「１−２−３−４−５−６−７−８」と表されている直方体のモデルである。このモデルに埋め込む場合には、座標系の原点［０，０，０］からの各頂点までの距離を計算すると、頂点インデックスは、「１−２−４−３−５−６−８−７」と順序付けされる（図２参照）。
【００３２】
透かし情報埋込手段１４は、数値に変換された透かし情報を３次元形状モデルに埋め込んで透かし情報付３次元形状モデルＤＢ３０へ格納する。
透かし情報を要素順序付手段１３で求めた順序にしたがって、頂点インデックス情報を変更し付加する。ここで、変更により頂点インデックス値が重複しないように、頂点インデックスの値の最大値の一桁上位の桁に、透かし情報変換手段１２で変換した数値を加える。以下この桁を「埋め込み桁」とする。
例えば、頂点インデックスの最大値が５００であった場合、埋め込み桁に情報を埋め込むため、透かし情報の数値に１０００を乗じた上で加えればよい。透かし情報をすべて埋め込むまでこの処理を繰り返す。
【００３３】
上記例では、頂点インデックスの最大値は８であるから、これより１桁上位にするには埋め込み桁を１０とすればよい。即ち、透かし情報変換手段１２で求めた値に埋め込み桁を表す「１０」を乗じて、頂点インデックスの値を加えた値が新しい頂点インデックス値となる（図２参照）。
図３に示した直方体形状モデルにテキスト「ａｐｐｌｅ」を埋め込んだ場合、図３の頂点インデックスは、埋め込み前は「１−２−４−３−５−６−８−７」であるが、埋め込み後は「１１−１６２−１６４−１２３−５５−６−８−７」となり、図４に示すように埋め込まれる。ここで、頂点インデックス「６−８−７」は、埋め込み対象となる文字がないためそのままの値となっている。
【００３４】
次に、情報埋込装置１０の動作の流れを図５のフローチャートを用いて説明する。
まず、ユーザが指定した３次元形状モデルに埋め込むべき透かし情報（著作権やその他のテキスト情報）をキーボードやファイルから入力する（ステップＳ１０）。
【００３５】
可逆の変換方法を用いて、透かし情報であるテキストを数値に変換し、埋め込める形に変換する（ステップＳ１１）。例えば、変換方式をアルファベット文字の順序とすれば、文字列「ａ−ｐ−ｐ−ｌ−ｅ」は、「１−１６−１６−１２−５」（「−」は説明のための区切りで実際には挿入されない。）となる。
【００３６】
透かし情報の埋め込み前後で順序が変わらず一意に決まる順序付け方法によって、３次元形状モデルを構成する各頂点を順序付ける（ステップＳ１２）。
例えば、座標系の原点から頂点までの距離でソートして順序付けをする。同距離のものがあった場合は、最初のものだけ採用して後は無視し、より距離の遠い次の頂点に移行し、すべての頂点が順序付けされるまで処理を繰り返す。
【００３７】
図３の直方体形状モデル（各辺の長さがＸ＝２０，Ｙ＝２０，Ｚ＝３０）の場合、頂点インデックス「１−２−３−４−５−６−７−８」は、「１−２−４−３−５−６−８−７」と順序付けされる。
【００３８】
なお、ステップＳ１１とステップＳ１２の処理は互いに独立な処理なので、同時並行で処理することも可能である。
【００３９】
透かし情報をステップＳ１２で求めた頂点の順序に従って、変更によりインデックスが重複しないように、頂点のインデックス値の最大値の一桁上位の桁に、ステップＳ１１で変換した数値を加えて、透かし情報をすべて埋め込むまでこの処理を繰り返し、すべて埋め込みが終了すると、透かし情報付３次元形状モデルＤＢ３０へ書き出す（ステップＳ１３）。
図３の直方体形状モデルにテキスト「ａｐｐｌｅ」を埋め込んだ場合、埋め込み前の頂点インデックスは「１−２−４−３−５−６−８−７」であるが、埋め込み後は「１１−１６２−１６４−１２３−５５−６−８−７」となる。
【００４０】
次に、３次元形状モデルに埋め込まれた透かし情報を抽出する方法について説明する。
情報抽出装置２０は、埋め込まれた透かし情報を３次元形状モデルから抽出する処理を行う。
透かし情報抽出手段２１は、透かし情報付３次元形状モデルＤＢ３０から埋め込まれた透かし情報を抽出する。これは、透かし情報付３次元形状モデルＤＢ３０中のすべての頂点のうち、頂点インデックスの埋め込み桁が０でない（情報が埋め込まれている）頂点を選別し、埋め込み桁より下の桁の値を除去し残った数値から、数値化された透かし情報として抽出する。
【００４１】
例えば、透かし情報付３次元形状モデルＤＢ３０中の頂点個数から頂点インデックスの最大値を求め、これより１桁上位の桁を埋め込み桁とする。
次に、透かし情報付３次元形状モデルＤＢ３０中のすべての頂点に対して、埋め込み桁以上の桁の値と埋め込み桁未満の桁の値とに分け、埋め込み桁以上の桁の値が０でない（情報が埋め込まれている）頂点だけを残す。この埋め込み桁以上の桁の値が数値化された透かし情報であり、埋め込み桁未満の桁の値が実際の頂点インデックスの値である。
図４の例では、頂点インデックス「１１−１６２−１２３−１６４−５５−６−８−７」から「（１、１）−（１６、２）−（１２、３）−（１６、４）−（５、５）」が選別される。ここで、括弧内の左の数値が透かし情報、右の数値が頂点インデックスの値である。
【００４２】
抽出要素順序付手段２２は、選別された頂点を要素順序付手段１３で頂点を順序付けた方法と同じ方法で順序付ける。
この順序付けを、座標系の原点から頂点までの距離でソートして順序付けをしていた場合、透かし情報抽出手段２１で選別されたすべての頂点「１−２−３−４−５」に対して原点からの距離でソートすると「１−２−４−３−５」が求められ、この順序で抽出した透かし情報を並べ替えると「１−１６−１６−１２−５」となる。
【００４３】
透かし情報逆変換手段２３は、抽出要素順序付手段２２で並べ替えられた透かし情報を逆変換して、変換前の透かし情報であるテキスト情報を復元する。ここで、数値化された透かし情報が文字コードをそのまま使用しているのであれば、この透かし情報逆変換手段２２を省略することができる。
図４の例では、数値列「１−１６−１６−１２−５」を「ａｐｐｌｅ」というテキストに変換する。
透かし情報出力手段２４は、透かし情報逆変換手段２３で抽出された透かし情報のテキストを、必要に応じ画像表示装置や出力装置を通じて表示・印刷し、また、記憶装置へ保存する。
【００４４】
次に、情報抽出装置２０の動作の流れを図６のフローチャートを用いて説明する。
まず、ユーザが透かし情報を取り出す対象を指示し、透かし情報付３次元形状モデルＤＢ３０の中からその対象データを取り出す（ステップＳ２０）。
取り出された透かし情報付３次元形状モデルから埋め込まれた透かし情報を抽出する（ステップＳ２１）。
例えば、透かし情報付３次元形状モデルＤＢ３０中の頂点個数から頂点インデックスの最大値を求め、これより１桁上位の桁を埋め込み桁とする。
次に、透かし情報付３次元形状モデル中のすべての頂点に対して、埋め込み桁以上の桁の値と埋め込み桁未満の桁の値とに分け、埋め込み桁以上の桁の値が０でない（情報が埋め込まれている）頂点だけを残す。この埋め込み桁以上の桁の値が数値化された透かし情報であり、埋め込み桁未満の桁の値が実際の頂点インデックスの値である。
【００４５】
次に、選別された頂点を要素順序付手段１３で頂点を順序付けた方法と同じ方法で順序付け、この順序で抽出した透かし情報を並べ替える（ステップＳ２２）。
この順序付けを、座標系の原点から頂点までの距離でソートして順序付けをしていた場合、透かし情報抽出手段２１で選別されたすべての頂点「１−２−３−４−５」に対して原点からの距離でソートすると「１−２−４−３−５」が求められ、この順序で抽出した透かし情報を並べ替えると「１−１６−１６−１２−５」となる。
【００４６】
次に、ステップＳ２２で並べ替えられた透かし情報を逆変換して、変換前の透かし情報であるテキスト情報を復元し、必要に応じ画像表示装置や出力装置を通じて表示・印刷し、また、記憶装置へ保存する（ステップＳ２３）。
図４の例では、数値列「１−１６−１６−１２−５」を「ａｐｐｌｅ」というテキストに変換する。
【００４７】
尚、上述した実施形態では、埋め込む対象として頂点のインデックスを利用したが、埋め込む対象は、３次元形状モデルを構成する、頂点、稜線、面、多角形、曲線、曲面など、インデキシングされた要素であればいずれでもよい。
また、３次元形状モデルのデータ構造も、ソリッド／サーフェース／ワイヤーフレーム／三角形ポリゴンメッシュ等の種類は問わない。
【００４８】
さらに、透かし情報もアルファベット文字列に限定されるものではなく、画像情報や音声情報とした場合であっても数値変換可能であれば本発明を適用することができる。例えば、これらの情報をバイト単位等の所定の長さに区切り、この区切られた情報の１つ１つを数値情報に変換すればよい。
また、情報の埋め込み順序および抽出する順序についても、順序数自体を透かし情報として埋め込んでおき、抽出時にその埋め込まれた順序情報をもとに情報を抽出するようにしてもよい。
【００４９】
さらに、上記の実施形態では、情報埋込装置と情報抽出装置を独立な装置としたが、もちろん両装置の機能を併せ持った１つの情報埋込抽出システムとして構成してもよい。
【００５０】
さらに、本発明は上述した実施形態のみに限定されたものではない。上述した実施形態の情報埋込装置、情報抽出装置および情報埋込抽出システムを構成する各機能を装置ごとにプログラム化し、予めＣＤ−ＲＯＭ等の記録媒体に書き込んでおき、このＣＤ−ＲＯＭをＣＤ−ＲＯＭドライブのような媒体駆動装置を搭載したコンピュータに装着して、これらのプログラムをコンピュータのメモリあるいは記憶装置に格納して、実行することによって、本発明の目的を達成することができる。
この場合、記録媒体から読み出されたプログラム自体が上述した実施形態の機能を実現することになり、そのプログラムおよびそのプログラムを記録した記録媒体も本発明を構成することになる。
【００５１】
尚、記録媒体としては半導体媒体（例えば、ＲＯＭ、不揮発性メモリカード等）、光媒体（例えば、ＤＶＤ、ＭＯ、ＭＤ、ＣＤ−Ｒ等）、磁気媒体（例えば、磁気テープ、フレキシブルディスク等）のいずれであってもよい。
【００５２】
また、ロードしたプログラムを実行することにより上述した実施形態の機能が実現されるだけでなく、そのプログラムの指示に基づき、オペレーティングシステムあるいは他のアプリケーションプログラム等と共同して処理することによって上述した実施形態の機能が実現される場合も含まれる。
【００５３】
市場に流通させる場合には、可搬型の記録媒体にプログラムを格納して流通させたり、インターネット等の通信網を介して接続されたサーバコンピュータの記憶装置に格納しておき、通信網を通じて他のコンピュータに転送することもできる。この場合、このサーバコンピュータの記憶装置も本発明の記録媒体に含まれる。
【００５４】
なお、コンピュータでは、可搬型の記録媒体上のプログラム、または転送されてくるプログラムを、コンピュータに接続した記憶装置にインストールし、そのインストールされたプログラムを実行することによって上述した実施形態の機能が実現される。
このように、本発明の各装置の機能をプログラム化し、記録媒体に記録して頒布することによって、コスト、可搬性、汎用性を向上させることができる。
【図面の簡単な説明】
【００５５】
【図１】本発明の実施形態に係る情報埋込装置および情報抽出装置の機能構成を示すブロック図である。
【図２】透かし情報、変換後の透かし情報、埋め込み先の頂点インデックス、埋め込み後のインデックス値の対応例である。
【図３】透かし情報埋め込み前の形状モデル例である。
【図４】図３の形状モデルに対して、透かし情報埋め込み後の形状モデル例である。
【図５】情報埋込装置の動作の流れを示すフローチャートである。
【図６】情報抽出装置の動作の流れを示すフローチャートである。
【符号の説明】
【００５６】
１０…情報埋込装置、１１…情報入力手段、１２…情報変換手段、１３…要素順序付手段、１４…情報埋込手段、１５…３次元形状モデルＤＢ、２０…情報抽出装置、２１…情報抽出手段、２２…抽出要素順序付手段、２３…情報逆変換手段、２４…情報出力手段、３０…透かし情報付３次元形状モデルＤＢ。
【図１】
2005269244.tif 000003
【図２】
2005269244.tif 000004
【図３】
2005269244.tif 000005
【図４】
2005269244.tif 000006
【図５】
2005269244.tif 000007
【図６】
2005269244.tif 000008