情報処理装置、コンピュータプログラム、および情報処理方法
【課題】 ３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データに対する電子透かしなどの付加情報の埋め込みにおいて、データの改ざんが検出されやすくする。
【解決手段】 図形データ２３における複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む。
【解決手段】 図形データ２３における複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、コンピュータプログラム、および情報処理方法に関するものである。
【背景技術】
【０００２】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データに対して電子透かしを埋め込む技術が提案されている（例えば非特許文献１，２参照）。
【０００３】
非特許文献１に記載の技術では、電子透かしの埋込処理において、頂点が挿入頂点（mark vertex）、調節頂点（adjusting vertex）などに分類され、挿入頂点の頂点データ（ｘ１，ｘ２，ｘ３）のｘ１座標に、挿入頂点であることを示す情報が埋め込まれ、ｘ２座標に電子透かしが埋め込まれ、ｘ３座標に電子透かしのハッシュ値が埋め込まれる。
【０００４】
ｘ２座標に電子透かしを埋め込みｘ３座標にハッシュ値を埋め込む際には、まず、挿入頂点に隣接する頂点のｘ２座標値の重心とｘ３座標値の重心が計算され、それらの値と、電子透かしの値およびハッシュ値とから一意に得られる値が頂点データのｘ２座標およびｘ３座標にそれぞれ代入される。そして、ｘ２座標への電子透かしの埋め込みおよびｘ３座標へのハッシュ値の埋め込みに起因して発生するｘ２座標値の重心の変動とｘ３座標値の重心の変動を補償するために、調節頂点の位置（ｘ２座標値およびｘ３座標値）が調節される。
【０００５】
そして、電子透かしの取出処理において、各頂点の頂点データのｘ１座標の値に基づいて挿入頂点が特定され、挿入頂点の頂点データのｘ２座標およびｘ３座標から電子透かしおよびハッシュ値を取り出し、取り出した電子透かしのハッシュ値を計算し、計算したハッシュ値と取り出したハッシュ値とを比較して認証が行う。計算したハッシュ値と取り出したハッシュ値とが同一であれば、改ざんがないと判断され、認証に成功する。
【０００６】
しかし、この方法では、頂点データの各座標が浮動小数点の実数データである場合、丸め誤差などの演算誤差が発生するため、改ざんがない場合でも、電子透かしの取出処理において、計算したハッシュ値と取り出したハッシュ値とが一致しないことがあり、実用的ではない。
【０００７】
非特許文献２に記載の技術では、電子透かしの埋込処理において、互いに隣接しないように挿入頂点（mark vertex）が指定され、挿入頂点の頂点データ（ｘ１，ｘ２，ｘ３）におけるｘ１座標の浮動小数点実数データの仮数部の一部に、挿入頂点であることを示す情報が埋め込まれ、ｘ２座標の浮動小数点実数データの仮数部の一部に電子透かしが埋め込まれ、ｘ３座標の浮動小数点実数データの仮数部の一部に電子透かしのハッシュ値が埋め込まれる。
【０００８】
ｘ２座標に電子透かしを埋め込みｘ３座標にハッシュ値を埋め込む際には、まず、挿入頂点に隣接する頂点のｘ２座標値の浮動小数点実数データの仮数部の一部についての重心とｘ３座標値の浮動小数点実数データの仮数部の一部について重心が計算され、それらの値と電子透かしの値およびハッシュ値との間のビット演算により得られる排他的論理和が頂点データのｘ２座標およびｘ３座標にそれぞれ代入される。
【０００９】
そして、電子透かしの取出処理において、各頂点の頂点データのｘ１座標の値に基づいて挿入頂点が特定され、挿入頂点の頂点データのｘ２座標およびｘ３座標からビット演算で電子透かしおよびハッシュ値を取り出し、取り出した電子透かしのハッシュ値を計算し、計算したハッシュ値と取り出したハッシュ値とを比較して認証が行う。計算したハッシュ値と取り出したハッシュ値とが同一であれば、改ざんがないと判断され、認証に成功する。
【００１０】
非特許文献２に記載の技術では、ビット演算で挿入頂点のｘ２座標およびｘ３座標に対する電子透かしおよびハッシュ値の埋め込みおよび取り出しが行われるため、上述のような浮動小数点演算の丸め誤差などの演算誤差が発生しない。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】「A public fragile watermarking scheme for 3D model authentication」、Chang-Min Chou, Din-Chang Tseng著、Computer-Aided Design, Volume 38, Issue 11, November 2006
【非特許文献２】「A numerically stable fragile watermarking scheme for authenticating 3D models」、Wei-Bo Wang et al.著、Computer-Aided Design, Volume 40, Issue 5, May 2008
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上述の非特許文献２に記載の技術では、挿入頂点の頂点データにおけるｘ３座標の浮動小数点実数データの仮数部の一部にのみ、電子透かしのハッシュ値が埋め込まれるため、仮数部の残りの部分が改ざんされた場合でも、認証に成功してしまうという問題がある。また、埋め込める情報量が非特許文献１の方法と比較して、減少してしまうという問題点もある。
【００１３】
本発明は、上記の問題に鑑みてなされたものであり、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データに対する電子透かしなどの付加情報の埋め込みにおいて、データの改ざんが検出されやすくなるようにする情報処理装置、コンピュータプログラム、および情報処理方法を得ることを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するために、本発明では以下のようにした。
【００１５】
本発明に係る情報処理装置は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段と、記憶手段から３次元図形データを読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む情報埋込手段とを備える。
【００１６】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれるため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００１７】
また、本発明に係る情報処理装置は、上記の情報処理装置に加え、次のようにしてもよい。この場合、情報処理装置は、複数の頂点の一部または全部を、挿入頂点、調節頂点、および孤立頂点に分類する頂点分類手段をさらに備える。挿入頂点は、調節頂点と対になり、頂点データに付加情報を埋め込む頂点である。調節頂点は、挿入頂点と対になり、挿入頂点への付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点である。孤立頂点は、隣接する頂点がすべて調節頂点であり、頂点データに付加情報を埋め込む頂点である。そして、情報埋込手段は、挿入頂点の頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部に、挿入頂点であることを示す所定の第１識別値を埋め込み、孤立頂点の頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部に、当該頂点が孤立頂点であることを示す所定の第２識別値を埋め込む。この第２識別値は、第１識別値とは異なる。
【００１８】
また、本発明に係る情報処理装置は、上記の情報処理装置のいずれかに加え、次のようにしてもよい。この場合、情報処理装置は、複数の頂点の一部または全部を、挿入頂点および調節頂点に分類する頂点分類手段をさらに備える。挿入頂点は、調節頂点と対になり、頂点データに付加情報を埋め込む頂点である。調節頂点は、挿入頂点と対になり、挿入頂点への付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点である。そして、情報埋込手段は、挿入頂点に隣接する頂点の頂点データにおける一座標および別座標の浮動小数点実数データの仮数部の一部から座標ごとに所定のパラメータ値を整数演算で計算し、調節頂点の頂点データにおける一座標および別座標の浮動小数点実数データの仮数部の一部を、所定のパラメータ値の変動を補償するために変更する。
【００１９】
これにより、所定のパラメータの値が整数演算で計算されるため、丸め誤差などの演算誤差が発生せず、付加情報の取り出し時に、この所定のパラメータを使用した認証を正確に行うことができる。
【００２０】
本発明に係るコンピュータプログラムは、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段を有する情報処理装置におけるコンピュータを、記憶手段から３次元図形データを読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む情報埋込手段として機能させる。
【００２１】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれるため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００２２】
本発明に係る情報処理方法は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶手段から読み出すステップと、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込むステップと、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込むステップとを備える。
【００２３】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれるため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００２４】
本発明に係る情報処理装置は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段と、記憶手段から３次元図形データを読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う情報取出手段とを備える。
【００２５】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれているため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００２６】
また、本発明に係る情報処理装置は、上記の情報処理装置に加え、次のようにしてもよい。この場合、情報処理装置は、ある頂点の頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部の値が所定の第１識別値である場合、その頂点を挿入頂点と特定し、仮数部の一部の値が所定の第２識別値である場合、その頂点を孤立頂点と特定する頂点種類特定手段をさらに備える。挿入頂点は、調節頂点と対になり、頂点データに付加情報を埋め込む頂点である。調節頂点は、挿入頂点と対になり、挿入頂点への付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点である。孤立頂点は、隣接する頂点がすべて調節頂点であり、頂点データに付加情報を埋め込む頂点である。第２識別値は、第１識別値とは異なる。そして、情報取出手段は、挿入頂点および孤立頂点の頂点データについて、付加情報および符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う。
【００２７】
本発明に係るコンピュータプログラムは、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段を有する情報処理装置におけるコンピュータを、記憶手段から３次元図形データを読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う情報取出手段として機能させる。
【００２８】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれているため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００２９】
本発明に係る情報処理方法は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶手段から読み出すステップと、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出すステップと、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出すステップと、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行うステップとを備える。
【００３０】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれているため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【発明の効果】
【００３１】
本発明によれば、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データに対する電子透かしなどの付加情報の埋め込みにおいて、データの改ざんが検出されやすくなる。
【図面の簡単な説明】
【００３２】
【図１】図１は、本発明の実施の形態に係る情報処理装置の構成を示すブロック図である。
【図２】図２は、図１におけるＣＰＵでプログラムが実行されることにより実現される処理部を示すブロック図である。
【図３】図３は、本発明の実施の形態における各頂点データの構造の一例を示す図である。
【図４】図４は、本発明の実施の形態における付加情報の埋め込みについて説明するフローチャートである。
【図５】図５は、本発明の実施の形態における挿入頂点および調節頂点の分類について説明する図である。
【図６】図６は、本発明の実施の形態における付加情報の取り出しについて説明するフローチャートである。
【発明を実施するための形態】
【００３３】
以下、図に基づいて本発明の実施の形態を説明する。
【００３４】
図１は、本発明の実施の形態に係る情報処理装置の構成を示すブロック図である。図１に示す情報処理装置１は、コンピュータを内蔵しており、各種プログラムを実行して演算や処理を実行する。情報処理装置１としては、例えばパーソナルコンピュータが使用される。
【００３５】
端末装置１において、ＣＰＵ（Central Processing Unit）１１は、プログラムに記述された処理を実行する演算処理装置である。また、ＲＯＭ（Read Only Memory）１２は、プログラムおよびデータを予め記憶した不揮発性のメモリである。また、ＲＡＭ（Random Access Memory）１３は、プログラムを実行する際にそのプログラムおよびデータを一時的に記憶するメモリである。
【００３６】
ＣＰＵ１１、ＲＯＭ１２およびＲＡＭ１３は、バスやコントローラチップを介して互いに接続されており、さらに、バス、コントロールチップ、インタフェースなどを介して記憶装置１４、表示装置１５、および入力装置１６に接続されている。
【００３７】
記憶装置１４は、図示せぬオペレーティングシステム、各種プログラム、および各種データを格納する記録媒体を有する装置である。記憶装置１４としては、不揮発性半導体メモリ、ハードディスク駆動装置、ディスクアレイ装置などが使用される。また、表示装置１５は、操作画面などを表示する装置である。表示装置１５としては、例えば液晶ディスプレイが使用される。入力装置１６は、操作画面に対する操作を入力するための装置である。入力装置１６としては、例えばキーボードやマウスが使用される。
【００３８】
この実施の形態では、記憶装置１４には、埋め込みプログラム２１、取り出しプログラム２２、および図形データ２３が記憶されている。なお、プログラム２１，２２を、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどの可搬性のある記録媒体に記録し、その記録媒体から情報処理装置１にインストールするようにしてもよい。
【００３９】
埋め込みプログラム２１は、電子透かしなどの付加情報を図形データ２３に埋め込むためのコンピュータプログラムである。
【００４０】
取り出しプログラム２２は、電子透かしなどの付加情報を埋め込まれた図形データからその付加情報を取り出すためのコンピュータプログラムである。
【００４１】
図形データ２３は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データである。図形データ２３は、例えば、ＳＴＬ形式のデータである。
【００４２】
ＣＰＵ１１は、ＲＯＭ１２または記憶装置１４に格納されているプログラムをＲＡＭ１３にロードして実行する。これにより、プログラムに記述された処理を実行する処理部が実現される。
【００４３】
図２は、図１におけるＣＰＵ１１でプログラム２１，２２が実行されることにより実現される処理部を示すブロック図である。
【００４４】
この実施の形態では、付加情報を図形データ２３に埋め込むために埋め込みプログラム２１が実行されることにより、頂点分類部３１および情報埋込部３２が実現され、付加情報を埋め込まれた図形データから付加情報を取り出すために取り出しプログラム２２が実行されることにより、頂点種類特定部４１および情報取出部４２が実現される。
【００４５】
図３は、本発明の実施の形態における各頂点データの構造の一例を示す図である。
【００４６】
図３（Ａ）は、ＩＥＥＥ７５４で規定されている浮動小数点実数データのデータ構造を示す図である。Ｓ（１ビット）は、符号ビットであり、ＥＸＰ（８ビット）は、指数部であり、ＦＲＡＣ（２３ビット）は、仮数部である。
【００４７】
頂点データが浮動小数点実数データである場合において、付加情報を埋め込む頂点データ（ｘ１，ｘ２，ｘ３）については、各座標ｘ１，ｘ２，ｘ３の浮動小数点実数データの仮数部ＦＲＡＣの一部ｎｘｉ（ｉ＝１，２，３）が変更される。図３（Ｂ）に示すように、ここでは、ｎｘｉは、例えば、下位の所定ビット長（ここでは５ビット）の部分とされる。
【００４８】
頂点分類部３１は、図形データ２３について、頂点間のリンクに基づいて、複数の頂点の一部または全部を、挿入頂点、調節頂点、および孤立頂点に分類する。挿入頂点は、調節頂点と対となり、頂点データに付加情報を埋め込む頂点である。調節頂点は、挿入頂点と対になり、挿入頂点への付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点である。孤立頂点は、隣接する頂点がすべて調節頂点であり、頂点データに付加情報を埋め込む頂点である。なお、ある頂点とその頂点に隣接する頂点とは１本のリンクで直接接続されている。
【００４９】
この実施の形態では、上述のパラメータは、ｘ２座標およびｘ３座標のそれぞれについての重心ｎｘｃ２，ｎｘｃ３であって、式（１）で示される。
【００５０】
【数１】
【００５１】
ここで、Ｎ（ｖ）は、注目頂点（挿入頂点または孤立頂点）に隣接する頂点（つまり、注目頂点との間にリンクがある頂点）の集合であり、ｎｘｊは、各隣接頂点のｘｊ座標のデータの所定部分（図３（Ｂ）の場合、連続する下位５ビット）の値であり、｜Ｎ（ｖ）｜は、注目頂点に隣接する頂点の個数である。Ｍａｘｉは、ｎｘｉの最大値ｍａｘｉに１を加算した数値である。例えば、ｎｘｉのビット長が５である場合、Ｍａｘｉは３２である。ｋｅｙｊ（ｊ＝２，３）は、剰余演算ｍｏｄの値域を調節するためのｘ２座標（ｊ＝２）とｘ３座標（ｊ＝３）の所定の拡散係数である。なお、ｋｅｙｊは秘匿され公開されない。
【００５２】
情報埋込部３２は、ＲＡＭ１３または記憶装置１４から図形データ２３を読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標（ここではｘ２座標）の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標（ここではｘ３座標）の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む。この実施の形態では、一方向性関数は、ハッシュ関数である。
【００５３】
具体的には、情報埋込部３２は、挿入頂点の頂点データにおける残りの座標（ここではｘ１座標）の浮動小数点実数データの仮数部の一部ｎｘ１に、挿入頂点であることを示す所定の第１識別値を埋め込み、孤立頂点の頂点データにおける残りの座標（ここではｘ１座標）の浮動小数点実数データの仮数部の一部に、当該頂点が孤立頂点であることを示す所定の第２識別値を埋め込む。この第２識別値は、第１識別値とは異なる。
【００５４】
例えば、情報埋込部３２は、挿入頂点および孤立頂点のｘ１座標について、式（２）に従って、元のｎｘ１にｎｘ’１を代入する。つまり、仮数部のうち、ｎｘ１の部分が変更される。
【００５５】
【数２】
【００５６】
ここで、ｋｅｙは、第１識別値であり、第２識別値は、ｋｅｙ／２となる。なお、ｋｅｙは、ｎｘ１と同一のビット長のデータであり、ｋｅｙ／２は整数となる。なお、ｋｅｙは秘匿され公開されない。
【００５７】
挿入頂点および孤立頂点のいずれでもない頂点のｎｘ１が、ｋｅｙおよびｋｅｙ／２のいずれかと同一である場合には、ｎｘ’１は、ｋｅｙ／３とされる。なお、ｋｅｙ／３も整数となる。挿入頂点および孤立頂点のいずれでもない頂点について、ｎｘ１がｋｅｙおよびｋｅｙ／２のいずれでもない場合、ｎｘ’１＝ｎｘ１とされる。
【００５８】
また、例えば、情報埋込部３２は、挿入頂点および孤立頂点のｘ２座標およびｘ３座標について、式（３）に従って、ビット演算（式（３）ではビットごとの排他的論理和）でｎｘ’ｊを計算し、ｎｘ２にｎｘ’２を代入し、ｎｘ３にｎｘ’３を代入する。
【００５９】
【数３】
【００６０】
ここで、ｗｉは、ｉ番目の電子透かしなどの付加情報であり、ｈはハッシュ関数であり、Ｎｖｈは、仮数部における、ｎｘｊ以外の残りの部分の値である。
【００６１】
この実施の形態では、情報埋込部３２は、ｗｉとＮｖｈを引数として、ハッシュ関数ｈの値を計算し、そのハッシュ関数ｈの値とｎｘｃ３との排他的論理和をｎｘ’３として計算する。
【００６２】
また、情報埋込部３２は、挿入頂点に隣接する頂点の頂点データにおける一座標（ここではｘ２座標）および別座標（ここではｘ３座標）の浮動小数点実数データの仮数部の一部から、座標ごとに所定のパラメータ値を整数演算で計算し、調節頂点の頂点データにおける一座標（ここではｘ２座標）および別座標（ここではｘ３座標）の浮動小数点実数データの仮数部の一部を、所定のパラメータ値の変動を補償するために変更する。
【００６３】
この実施の形態では、式（３）に従って挿入頂点の頂点データが変更されるため、調節頂点のｘ２座標およびｘ３座標のデータにおける、ｎｘｊと同一の所定部分（図３（Ｂ）の場合、下位５ビット）ｎｘ’ａｄの値が、式（４）に従って変更される。
【００６４】
【数４】
【００６５】
ここで、Ｎ（ｍｖ）は、挿入頂点に隣接する頂点から調節頂点を除いた集合である。ｋは、０または１の値を有する係数であって、式（４）の右辺第１項から第２項を減算して得られる値が負である場合にはｋ＝１とし、式（４）の右辺第１項から第２項を減算して得られる値が正である場合にはｋ＝０とする。つまり、ｎｘ’ａｄが５ビットである場合、ｎｘ’ａｄの値は、０から３１（つまり、ｍａｘｉ）のいずれかの値であり、負とはならないため、このように計算される。
【００６６】
また、頂点種類特定部４１は、ある頂点の頂点データにおける、後述の付加情報および符号の取り出し元となる２つの座標以外の残りの座標（ここではｘ１座標）の浮動小数点実数データの仮数部の一部の値が上述の第１識別値である場合、その頂点を挿入頂点と特定し、仮数部の一部の値が上述の第２識別値である場合、その頂点を孤立頂点と特定する。
【００６７】
情報取出部４２は、この実施の形態に示す方法で付加情報を埋め込まれた３次元図形データ（図示せず）を、ＲＡＭ１３または記憶装置１４から読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標（ここではｘ２座標）の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標（ここではｘ３座標）の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う。この一方向性関数は、付加情報を埋め込む際に使用される上述の一方向性関数と同一の関数である。
【００６８】
具体的には、情報取出部４２は、挿入頂点および孤立頂点の頂点データについて、付加情報および符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う。
【００６９】
情報取出部４２は、挿入頂点および孤立頂点の頂点データについて、式（１）に従って、ｘ２座標およびｘ３座標の重心ｎｘｃ２，ｎｘｃ３を計算するとともに、ｘ２座標およびｘ３座標のデータの仮数部の所定部分ｎｘ’２，ｎｘ’３を抽出し、式（５）に従って、付加情報ｗ’ｉおよび符号（埋め込み時のハッシュ値）ｈ’ｉを取り出す。なお、ｗ’ｉは、ｉ番目の付加情報を示し、ｈ’ｉは、ｉ番目の符号を示している。つまり、挿入頂点および孤立頂点の数が合計ｎ個であれば、ｎ対の付加情報および符号が取り出される。
【００７０】
【数５】
【００７１】
次に、上記情報処理装置の動作について説明する。ここでは、付加情報の埋め込みの際の動作と、付加情報の取り出しの際の動作とについて説明する。
【００７２】
（１）付加情報の埋め込み
【００７３】
図４は、本発明の実施の形態における付加情報の埋め込みについて説明するフローチャートである。
【００７４】
まず、頂点分類部３１は、図形データ２３を読み出し、図形データ２３における頂点を注目頂点として１つずつ選択し、分類処理を行っていく。
【００７５】
最初に、頂点分類部３１は、図形データ２３におけるすべての頂点を調節頂点候補とする（ステップＳ１）。例えば、各頂点の頂点データに関連付けて、その頂点の種類を示す頂点種類データがＲＡＭ１３上に設けられ、そのデータの初期値が、調節頂点候補を示す値とされる。
【００７６】
次に、頂点分類部３１は、注目頂点としてまだ処理していない頂点があるか否かを判定する（ステップＳ２）。
【００７７】
注目頂点としてまだ処理していない（つまり、挿入頂点、調節頂点および孤立頂点として確定しておらず、注目頂点として選択されていない）１または複数の頂点がある場合、頂点分類部３１は、その１または複数の頂点から１つの頂点を注目頂点として選択し（ステップＳ３）、その注目頂点に隣接する頂点を図形データ２３に基づいて特定し、その隣接する頂点の頂点種類データを参照して、その注目頂点に隣接する頂点がすべて調節頂点であるか否かを判定する（ステップＳ４）。
【００７８】
その注目頂点に隣接する頂点がすべて調節頂点である場合、頂点分類部３１は、その注目頂点を孤立頂点に分類し、その注目頂点の頂点種類データの値を、孤立頂点であることを示す値とする（ステップＳ５）。
【００７９】
一方、その注目頂点に隣接する頂点の少なくとも１つが調節頂点ではない場合、頂点分類部３１は、その注目頂点に隣接する頂点の少なくとも１つが調節頂点候補であるか否かを判定する（ステップＳ６）。
【００８０】
その注目頂点に隣接する頂点のいずれも調節頂点候補ではない場合、この注目頂点の処理を終了し、ステップＳ２に戻る。
【００８１】
一方、その注目頂点に隣接する頂点の少なくとも１つが調節頂点候補である場合、頂点分類部３１は、その注目頂点を挿入頂点とし、その注目頂点に隣接する調節頂点候補の１つを選択し、その選択した頂点を、その挿入頂点と対をなす調節頂点とする（ステップＳ７）。このとき、頂点分類部３１は、その注目頂点の頂点種類データの値を、挿入頂点であることを示す値とし、その選択した隣接頂点の頂点種類データの値を、調節頂点であることを示す値とする。また、この２つの頂点が対であることを示す情報も頂点種類データに含められる。
【００８２】
そして、頂点分類部３１は、その注目頂点に隣接する頂点のうちの、調節頂点以外の頂点を調節頂点候補から外す（ステップＳ８）。このとき、頂点分類部３１は、その注目頂点に隣接する頂点のうちの、調節頂点以外の頂点の頂点種別データの値を、調節頂点候補の値から、別の所定値へ変更する。
【００８３】
ステップＳ７，Ｓ８において挿入頂点と調節頂点との対が選択された後、この注目頂点の処理を終了し、ステップＳ２に戻る。
【００８４】
このようにして、図形データ２３についての一部または全部の頂点のそれぞれが、挿入頂点、調節頂点、および孤立頂点のいずれかに分類される。
【００８５】
ここで、具体例について説明する。図５は、本発明の実施の形態における挿入頂点および調節頂点の分類について説明する図である。図５（Ａ）は、図形データ２３による頂点およびリンクの一例を示している。この図形には、頂点＃１から頂点＃７が存在している。
【００８６】
まず、これらの頂点＃１〜＃７は、調節頂点候補とされる（ステップＳ１）。次に、頂点＃１が選択される（ステップＳ３）。頂点＃１について、隣接する頂点の少なくとも１つが調節頂点ではなく（ステップＳ４）、かつ隣接する頂点の少なくとも１つが調節頂点候補であるので（ステップＳ６）、図５（Ｂ）に示すように、頂点＃１は挿入頂点とされ、それに隣接する頂点のうちの頂点＃４が調節頂点とされる（ステップＳ７）。なお、図５において、黒丸の頂点は挿入頂点を表し、白丸の頂点は調節頂点を表している。そして、その他の隣接頂点である、頂点＃２、頂点＃３、および頂点＃５は、調節頂点候補から外される（ステップＳ８）。
【００８７】
次に、頂点種類が未確定である頂点＃２が選択される（ステップＳ３）。頂点＃２について、隣接する頂点の少なくとも１つが調節頂点ではなく（ステップＳ４）、かつ隣接する頂点の少なくとも１つが調節頂点候補であるので（ステップＳ６）、図５（Ｃ）に示すように、頂点＃２は挿入頂点とされ、それに隣接する頂点のうちの頂点＃６が調節頂点とされる（ステップＳ７）。そして、その他の隣接する調節頂点候補の頂点＃７は、調節頂点候補から外される（ステップＳ８）。
【００８８】
次に、頂点種類が未確定である頂点＃３が選択される（ステップＳ３）。頂点＃３について、隣接する頂点の少なくとも１つが調節頂点ではなく（ステップＳ４）、かつ隣接する頂点のいずれも調節頂点候補ではないので（ステップＳ６）、頂点＃３についての処理は終了する。
【００８９】
次に、頂点種類が未確定である頂点＃５が選択される（ステップＳ３）。頂点＃５について、隣接する頂点の少なくとも１つが調節頂点ではなく（ステップＳ４）、かつ隣接する頂点の少なくとも１つが調節頂点候補であるので（ステップＳ６）、図５（Ｄ）に示すように、頂点＃５は挿入頂点とされ、それに隣接する頂点のうちの頂点＃７が調節頂点とされる（ステップＳ７）。
【００９０】
そして、頂点種類が未確定である未処理の頂点がなくなったため、ここで、頂点種類の分類処理は終了される。
【００９１】
上述のようにして、頂点種類が分類された後、情報埋込部３２は、挿入頂点、調節頂点、孤立頂点、およびそれら以外について、まず、その頂点種類に応じて、式（２）に従って、Ｘ（ｘ１）座標を変更する（ステップＳ９）。つまり、情報埋込部３２は、頂点種類データの値に基づいて頂点種類を特定し、式（２）に従って、変更後のＸ（ｘ１）座標の値を特定し、その頂点の頂点データのＸ（ｘ１）座標の値をその特定した値で変更する。
【００９２】
次に、情報埋込部３２は、各挿入頂点について、Ｙ（ｘ２）座標およびＺ（ｘ３）座標の値を、式（３）に従って変更する（ステップＳ１０）。さらに、情報埋込部３２は、その挿入頂点と対をなす調節頂点について、Ｙ（ｘ２）座標およびＺ（ｘ３）座標の値を、式（４）に従って変更する（ステップＳ１１）。
【００９３】
また、情報埋込部３２は、各孤立頂点について、Ｙ（ｘ２）座標およびＺ（ｘ３）座標の値を、式（３）に従って変更する（ステップＳ１２）。
【００９４】
このようにして、図形データ２３から、付加情報が埋め込まれた図形データが生成される。なお、頂点種別データは、図形データへの付加情報の埋め込み時のみに使用され、付加情報が埋め込まれた図形データには付加されていない。このようにして生成された図形データは、例えば記憶装置１４に記憶される。
【００９５】
（２）付加情報の取り出し
【００９６】
上述のようにして付加情報が埋め込まれた図形データからは、付加情報を取り出すことが可能である。
【００９７】
図６は、本発明の実施の形態における付加情報の取り出しについて説明するフローチャートである。
【００９８】
頂点種類特定部４１は、注目頂点としてまだ処理していない頂点があるか否かを判定する（ステップＳ２１）。
【００９９】
注目頂点としてまだ処理していない１または複数の頂点がある場合、頂点種類特定部４１は、その１または複数の頂点から１つの頂点を注目頂点として選択し（ステップＳ２２）、その注目頂点の頂点種別がその注目頂点の頂点データにおけるＸ（ｘ１）座標の値に基づいて特定する（ステップＳ２３）。式（２）に示す分類に基づいて、頂点種別が特定される。
【０１００】
そして、その注目頂点の頂点種別が挿入頂点である場合（ステップＳ２４）、情報取出部４２は、その注目頂点の頂点データにおけるＹ（ｘ２）座標およびＺ（ｘ３）座標の値から、式（５）に従って付加情報ｗ’と符号ｈ’を取り出す（ステップＳ２５）。
【０１０１】
次に、情報取出部４２は、この付加情報ｗ’とｘ３座標の仮数部のｎｘ３以外の残りのビット領域Ｎｖｈ’とを引数として、式（３）におけるハッシュ関数ｈの値を計算し、その値と符号ｈ’とを比較し、両者が一致した場合、付加情報ｗ’が正しい（改ざんされていない）ものと認め、両者が一致しない場合、付加情報ｗ’が正しくない（改ざんされている）ものと認める（ステップＳ２６）。
【０１０２】
一方、その注目頂点の頂点種別が挿入頂点ではなく孤立頂点である場合（ステップＳ２７）、情報取出部４２は、その注目頂点の頂点データにおけるＹ（ｘ２）座標およびＺ（ｘ３）座標の値から、式（５）に従って付加情報ｗ’と符号ｈ’を取り出す（ステップＳ２８）。
【０１０３】
次に、情報取出部４２は、この付加情報ｗ’とｘ３座標の仮数部のｎｘ３以外の残りのビット領域Ｎｖｈ’とを引数として、式（３）におけるハッシュ関数ｈの値を計算し、その値と符号ｈ’とを比較し、両者が一致した場合、付加情報ｗ’が正しい（改ざんされていない）ものと認め、両者が一致しない場合、付加情報ｗ’が正しくない（改ざんされている）ものと認める（ステップＳ２９）。
【０１０４】
このようにして付加情報が埋め込まれた図形データから付加情報が取り出され、その付加情報の認証が行われる。
【０１０５】
以上のように、上記実施の形態によれば、付加情報の埋め込みにおいて、図形データ２３における複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む。
【０１０６】
また、上記実施の形態によれば、その付加情報の取り出しにおいて、図形データにおける複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う。
【０１０７】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれるため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【０１０８】
なお、上述の実施の形態は、本発明の好適な例であるが、本発明は、これらに限定されるものではなく、本発明の要旨を逸脱しない範囲において、種々の変形、変更が可能である。
【０１０９】
例えば、上記実施の形態において、ハッシュ関数に別の引数を追加してもよい。
【０１１０】
また、上記実施の形態では、図１に示す情報処理装置では、付加情報の埋め込みおよび付加情報の取り出しの両方を実行可能であるが、付加情報の埋め込みおよび付加情報の取り出しの一方のみを実行可能な装置としてもよい。
【０１１１】
また、上記実施の形態において、図形データがポリゴンデータである場合、ある頂点から延びるポリゴンの辺をリンクとするようにしてもよい。
【０１１２】
また、上記実施の形態において、ハッシュ関数の代わりに、他の一方向性関数を使用するようにしてもよい。
【０１１３】
また、上記実施の形態において、埋め込み時に変更される仮数部におけるビット部分の長さは、５ビットに限定されるものではない。
【産業上の利用可能性】
【０１１４】
本発明は、例えば、電子透かしの埋め込みおよび取り出しに適用可能である。
【符号の説明】
【０１１５】
１３ ＲＡＭ（記憶手段の一例）
１４ 記憶装置（記憶手段の一例）
２１ 埋め込みプログラム（コンピュータプログラムの一例）
２２ 取り出しプログラム（コンピュータプログラムの一例）
２３ 図形データ（３次元図形データの一例）
３１ 頂点分類部（頂点分類手段の一例）
３２ 情報埋込部（情報埋込手段の一例）
４１ 頂点種類特定部（頂点種類特定手段の一例）
４２ 情報取出部（情報取出手段の一例）
【技術分野】
【０００１】
本発明は、情報処理装置、コンピュータプログラム、および情報処理方法に関するものである。
【背景技術】
【０００２】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データに対して電子透かしを埋め込む技術が提案されている（例えば非特許文献１，２参照）。
【０００３】
非特許文献１に記載の技術では、電子透かしの埋込処理において、頂点が挿入頂点（mark vertex）、調節頂点（adjusting vertex）などに分類され、挿入頂点の頂点データ（ｘ１，ｘ２，ｘ３）のｘ１座標に、挿入頂点であることを示す情報が埋め込まれ、ｘ２座標に電子透かしが埋め込まれ、ｘ３座標に電子透かしのハッシュ値が埋め込まれる。
【０００４】
ｘ２座標に電子透かしを埋め込みｘ３座標にハッシュ値を埋め込む際には、まず、挿入頂点に隣接する頂点のｘ２座標値の重心とｘ３座標値の重心が計算され、それらの値と、電子透かしの値およびハッシュ値とから一意に得られる値が頂点データのｘ２座標およびｘ３座標にそれぞれ代入される。そして、ｘ２座標への電子透かしの埋め込みおよびｘ３座標へのハッシュ値の埋め込みに起因して発生するｘ２座標値の重心の変動とｘ３座標値の重心の変動を補償するために、調節頂点の位置（ｘ２座標値およびｘ３座標値）が調節される。
【０００５】
そして、電子透かしの取出処理において、各頂点の頂点データのｘ１座標の値に基づいて挿入頂点が特定され、挿入頂点の頂点データのｘ２座標およびｘ３座標から電子透かしおよびハッシュ値を取り出し、取り出した電子透かしのハッシュ値を計算し、計算したハッシュ値と取り出したハッシュ値とを比較して認証が行う。計算したハッシュ値と取り出したハッシュ値とが同一であれば、改ざんがないと判断され、認証に成功する。
【０００６】
しかし、この方法では、頂点データの各座標が浮動小数点の実数データである場合、丸め誤差などの演算誤差が発生するため、改ざんがない場合でも、電子透かしの取出処理において、計算したハッシュ値と取り出したハッシュ値とが一致しないことがあり、実用的ではない。
【０００７】
非特許文献２に記載の技術では、電子透かしの埋込処理において、互いに隣接しないように挿入頂点（mark vertex）が指定され、挿入頂点の頂点データ（ｘ１，ｘ２，ｘ３）におけるｘ１座標の浮動小数点実数データの仮数部の一部に、挿入頂点であることを示す情報が埋め込まれ、ｘ２座標の浮動小数点実数データの仮数部の一部に電子透かしが埋め込まれ、ｘ３座標の浮動小数点実数データの仮数部の一部に電子透かしのハッシュ値が埋め込まれる。
【０００８】
ｘ２座標に電子透かしを埋め込みｘ３座標にハッシュ値を埋め込む際には、まず、挿入頂点に隣接する頂点のｘ２座標値の浮動小数点実数データの仮数部の一部についての重心とｘ３座標値の浮動小数点実数データの仮数部の一部について重心が計算され、それらの値と電子透かしの値およびハッシュ値との間のビット演算により得られる排他的論理和が頂点データのｘ２座標およびｘ３座標にそれぞれ代入される。
【０００９】
そして、電子透かしの取出処理において、各頂点の頂点データのｘ１座標の値に基づいて挿入頂点が特定され、挿入頂点の頂点データのｘ２座標およびｘ３座標からビット演算で電子透かしおよびハッシュ値を取り出し、取り出した電子透かしのハッシュ値を計算し、計算したハッシュ値と取り出したハッシュ値とを比較して認証が行う。計算したハッシュ値と取り出したハッシュ値とが同一であれば、改ざんがないと判断され、認証に成功する。
【００１０】
非特許文献２に記載の技術では、ビット演算で挿入頂点のｘ２座標およびｘ３座標に対する電子透かしおよびハッシュ値の埋め込みおよび取り出しが行われるため、上述のような浮動小数点演算の丸め誤差などの演算誤差が発生しない。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】「A public fragile watermarking scheme for 3D model authentication」、Chang-Min Chou, Din-Chang Tseng著、Computer-Aided Design, Volume 38, Issue 11, November 2006
【非特許文献２】「A numerically stable fragile watermarking scheme for authenticating 3D models」、Wei-Bo Wang et al.著、Computer-Aided Design, Volume 40, Issue 5, May 2008
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上述の非特許文献２に記載の技術では、挿入頂点の頂点データにおけるｘ３座標の浮動小数点実数データの仮数部の一部にのみ、電子透かしのハッシュ値が埋め込まれるため、仮数部の残りの部分が改ざんされた場合でも、認証に成功してしまうという問題がある。また、埋め込める情報量が非特許文献１の方法と比較して、減少してしまうという問題点もある。
【００１３】
本発明は、上記の問題に鑑みてなされたものであり、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データに対する電子透かしなどの付加情報の埋め込みにおいて、データの改ざんが検出されやすくなるようにする情報処理装置、コンピュータプログラム、および情報処理方法を得ることを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するために、本発明では以下のようにした。
【００１５】
本発明に係る情報処理装置は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段と、記憶手段から３次元図形データを読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む情報埋込手段とを備える。
【００１６】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれるため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００１７】
また、本発明に係る情報処理装置は、上記の情報処理装置に加え、次のようにしてもよい。この場合、情報処理装置は、複数の頂点の一部または全部を、挿入頂点、調節頂点、および孤立頂点に分類する頂点分類手段をさらに備える。挿入頂点は、調節頂点と対になり、頂点データに付加情報を埋め込む頂点である。調節頂点は、挿入頂点と対になり、挿入頂点への付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点である。孤立頂点は、隣接する頂点がすべて調節頂点であり、頂点データに付加情報を埋め込む頂点である。そして、情報埋込手段は、挿入頂点の頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部に、挿入頂点であることを示す所定の第１識別値を埋め込み、孤立頂点の頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部に、当該頂点が孤立頂点であることを示す所定の第２識別値を埋め込む。この第２識別値は、第１識別値とは異なる。
【００１８】
また、本発明に係る情報処理装置は、上記の情報処理装置のいずれかに加え、次のようにしてもよい。この場合、情報処理装置は、複数の頂点の一部または全部を、挿入頂点および調節頂点に分類する頂点分類手段をさらに備える。挿入頂点は、調節頂点と対になり、頂点データに付加情報を埋め込む頂点である。調節頂点は、挿入頂点と対になり、挿入頂点への付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点である。そして、情報埋込手段は、挿入頂点に隣接する頂点の頂点データにおける一座標および別座標の浮動小数点実数データの仮数部の一部から座標ごとに所定のパラメータ値を整数演算で計算し、調節頂点の頂点データにおける一座標および別座標の浮動小数点実数データの仮数部の一部を、所定のパラメータ値の変動を補償するために変更する。
【００１９】
これにより、所定のパラメータの値が整数演算で計算されるため、丸め誤差などの演算誤差が発生せず、付加情報の取り出し時に、この所定のパラメータを使用した認証を正確に行うことができる。
【００２０】
本発明に係るコンピュータプログラムは、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段を有する情報処理装置におけるコンピュータを、記憶手段から３次元図形データを読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む情報埋込手段として機能させる。
【００２１】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれるため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００２２】
本発明に係る情報処理方法は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶手段から読み出すステップと、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込むステップと、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込むステップとを備える。
【００２３】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれるため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００２４】
本発明に係る情報処理装置は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段と、記憶手段から３次元図形データを読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う情報取出手段とを備える。
【００２５】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれているため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００２６】
また、本発明に係る情報処理装置は、上記の情報処理装置に加え、次のようにしてもよい。この場合、情報処理装置は、ある頂点の頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部の値が所定の第１識別値である場合、その頂点を挿入頂点と特定し、仮数部の一部の値が所定の第２識別値である場合、その頂点を孤立頂点と特定する頂点種類特定手段をさらに備える。挿入頂点は、調節頂点と対になり、頂点データに付加情報を埋め込む頂点である。調節頂点は、挿入頂点と対になり、挿入頂点への付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点である。孤立頂点は、隣接する頂点がすべて調節頂点であり、頂点データに付加情報を埋め込む頂点である。第２識別値は、第１識別値とは異なる。そして、情報取出手段は、挿入頂点および孤立頂点の頂点データについて、付加情報および符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う。
【００２７】
本発明に係るコンピュータプログラムは、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段を有する情報処理装置におけるコンピュータを、記憶手段から３次元図形データを読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う情報取出手段として機能させる。
【００２８】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれているため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【００２９】
本発明に係る情報処理方法は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶手段から読み出すステップと、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出すステップと、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出すステップと、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行うステップとを備える。
【００３０】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれているため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【発明の効果】
【００３１】
本発明によれば、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データに対する電子透かしなどの付加情報の埋め込みにおいて、データの改ざんが検出されやすくなる。
【図面の簡単な説明】
【００３２】
【図１】図１は、本発明の実施の形態に係る情報処理装置の構成を示すブロック図である。
【図２】図２は、図１におけるＣＰＵでプログラムが実行されることにより実現される処理部を示すブロック図である。
【図３】図３は、本発明の実施の形態における各頂点データの構造の一例を示す図である。
【図４】図４は、本発明の実施の形態における付加情報の埋め込みについて説明するフローチャートである。
【図５】図５は、本発明の実施の形態における挿入頂点および調節頂点の分類について説明する図である。
【図６】図６は、本発明の実施の形態における付加情報の取り出しについて説明するフローチャートである。
【発明を実施するための形態】
【００３３】
以下、図に基づいて本発明の実施の形態を説明する。
【００３４】
図１は、本発明の実施の形態に係る情報処理装置の構成を示すブロック図である。図１に示す情報処理装置１は、コンピュータを内蔵しており、各種プログラムを実行して演算や処理を実行する。情報処理装置１としては、例えばパーソナルコンピュータが使用される。
【００３５】
端末装置１において、ＣＰＵ（Central Processing Unit）１１は、プログラムに記述された処理を実行する演算処理装置である。また、ＲＯＭ（Read Only Memory）１２は、プログラムおよびデータを予め記憶した不揮発性のメモリである。また、ＲＡＭ（Random Access Memory）１３は、プログラムを実行する際にそのプログラムおよびデータを一時的に記憶するメモリである。
【００３６】
ＣＰＵ１１、ＲＯＭ１２およびＲＡＭ１３は、バスやコントローラチップを介して互いに接続されており、さらに、バス、コントロールチップ、インタフェースなどを介して記憶装置１４、表示装置１５、および入力装置１６に接続されている。
【００３７】
記憶装置１４は、図示せぬオペレーティングシステム、各種プログラム、および各種データを格納する記録媒体を有する装置である。記憶装置１４としては、不揮発性半導体メモリ、ハードディスク駆動装置、ディスクアレイ装置などが使用される。また、表示装置１５は、操作画面などを表示する装置である。表示装置１５としては、例えば液晶ディスプレイが使用される。入力装置１６は、操作画面に対する操作を入力するための装置である。入力装置１６としては、例えばキーボードやマウスが使用される。
【００３８】
この実施の形態では、記憶装置１４には、埋め込みプログラム２１、取り出しプログラム２２、および図形データ２３が記憶されている。なお、プログラム２１，２２を、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどの可搬性のある記録媒体に記録し、その記録媒体から情報処理装置１にインストールするようにしてもよい。
【００３９】
埋め込みプログラム２１は、電子透かしなどの付加情報を図形データ２３に埋め込むためのコンピュータプログラムである。
【００４０】
取り出しプログラム２２は、電子透かしなどの付加情報を埋め込まれた図形データからその付加情報を取り出すためのコンピュータプログラムである。
【００４１】
図形データ２３は、３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データである。図形データ２３は、例えば、ＳＴＬ形式のデータである。
【００４２】
ＣＰＵ１１は、ＲＯＭ１２または記憶装置１４に格納されているプログラムをＲＡＭ１３にロードして実行する。これにより、プログラムに記述された処理を実行する処理部が実現される。
【００４３】
図２は、図１におけるＣＰＵ１１でプログラム２１，２２が実行されることにより実現される処理部を示すブロック図である。
【００４４】
この実施の形態では、付加情報を図形データ２３に埋め込むために埋め込みプログラム２１が実行されることにより、頂点分類部３１および情報埋込部３２が実現され、付加情報を埋め込まれた図形データから付加情報を取り出すために取り出しプログラム２２が実行されることにより、頂点種類特定部４１および情報取出部４２が実現される。
【００４５】
図３は、本発明の実施の形態における各頂点データの構造の一例を示す図である。
【００４６】
図３（Ａ）は、ＩＥＥＥ７５４で規定されている浮動小数点実数データのデータ構造を示す図である。Ｓ（１ビット）は、符号ビットであり、ＥＸＰ（８ビット）は、指数部であり、ＦＲＡＣ（２３ビット）は、仮数部である。
【００４７】
頂点データが浮動小数点実数データである場合において、付加情報を埋め込む頂点データ（ｘ１，ｘ２，ｘ３）については、各座標ｘ１，ｘ２，ｘ３の浮動小数点実数データの仮数部ＦＲＡＣの一部ｎｘｉ（ｉ＝１，２，３）が変更される。図３（Ｂ）に示すように、ここでは、ｎｘｉは、例えば、下位の所定ビット長（ここでは５ビット）の部分とされる。
【００４８】
頂点分類部３１は、図形データ２３について、頂点間のリンクに基づいて、複数の頂点の一部または全部を、挿入頂点、調節頂点、および孤立頂点に分類する。挿入頂点は、調節頂点と対となり、頂点データに付加情報を埋め込む頂点である。調節頂点は、挿入頂点と対になり、挿入頂点への付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点である。孤立頂点は、隣接する頂点がすべて調節頂点であり、頂点データに付加情報を埋め込む頂点である。なお、ある頂点とその頂点に隣接する頂点とは１本のリンクで直接接続されている。
【００４９】
この実施の形態では、上述のパラメータは、ｘ２座標およびｘ３座標のそれぞれについての重心ｎｘｃ２，ｎｘｃ３であって、式（１）で示される。
【００５０】
【数１】
【００５１】
ここで、Ｎ（ｖ）は、注目頂点（挿入頂点または孤立頂点）に隣接する頂点（つまり、注目頂点との間にリンクがある頂点）の集合であり、ｎｘｊは、各隣接頂点のｘｊ座標のデータの所定部分（図３（Ｂ）の場合、連続する下位５ビット）の値であり、｜Ｎ（ｖ）｜は、注目頂点に隣接する頂点の個数である。Ｍａｘｉは、ｎｘｉの最大値ｍａｘｉに１を加算した数値である。例えば、ｎｘｉのビット長が５である場合、Ｍａｘｉは３２である。ｋｅｙｊ（ｊ＝２，３）は、剰余演算ｍｏｄの値域を調節するためのｘ２座標（ｊ＝２）とｘ３座標（ｊ＝３）の所定の拡散係数である。なお、ｋｅｙｊは秘匿され公開されない。
【００５２】
情報埋込部３２は、ＲＡＭ１３または記憶装置１４から図形データ２３を読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標（ここではｘ２座標）の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標（ここではｘ３座標）の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む。この実施の形態では、一方向性関数は、ハッシュ関数である。
【００５３】
具体的には、情報埋込部３２は、挿入頂点の頂点データにおける残りの座標（ここではｘ１座標）の浮動小数点実数データの仮数部の一部ｎｘ１に、挿入頂点であることを示す所定の第１識別値を埋め込み、孤立頂点の頂点データにおける残りの座標（ここではｘ１座標）の浮動小数点実数データの仮数部の一部に、当該頂点が孤立頂点であることを示す所定の第２識別値を埋め込む。この第２識別値は、第１識別値とは異なる。
【００５４】
例えば、情報埋込部３２は、挿入頂点および孤立頂点のｘ１座標について、式（２）に従って、元のｎｘ１にｎｘ’１を代入する。つまり、仮数部のうち、ｎｘ１の部分が変更される。
【００５５】
【数２】
【００５６】
ここで、ｋｅｙは、第１識別値であり、第２識別値は、ｋｅｙ／２となる。なお、ｋｅｙは、ｎｘ１と同一のビット長のデータであり、ｋｅｙ／２は整数となる。なお、ｋｅｙは秘匿され公開されない。
【００５７】
挿入頂点および孤立頂点のいずれでもない頂点のｎｘ１が、ｋｅｙおよびｋｅｙ／２のいずれかと同一である場合には、ｎｘ’１は、ｋｅｙ／３とされる。なお、ｋｅｙ／３も整数となる。挿入頂点および孤立頂点のいずれでもない頂点について、ｎｘ１がｋｅｙおよびｋｅｙ／２のいずれでもない場合、ｎｘ’１＝ｎｘ１とされる。
【００５８】
また、例えば、情報埋込部３２は、挿入頂点および孤立頂点のｘ２座標およびｘ３座標について、式（３）に従って、ビット演算（式（３）ではビットごとの排他的論理和）でｎｘ’ｊを計算し、ｎｘ２にｎｘ’２を代入し、ｎｘ３にｎｘ’３を代入する。
【００５９】
【数３】
【００６０】
ここで、ｗｉは、ｉ番目の電子透かしなどの付加情報であり、ｈはハッシュ関数であり、Ｎｖｈは、仮数部における、ｎｘｊ以外の残りの部分の値である。
【００６１】
この実施の形態では、情報埋込部３２は、ｗｉとＮｖｈを引数として、ハッシュ関数ｈの値を計算し、そのハッシュ関数ｈの値とｎｘｃ３との排他的論理和をｎｘ’３として計算する。
【００６２】
また、情報埋込部３２は、挿入頂点に隣接する頂点の頂点データにおける一座標（ここではｘ２座標）および別座標（ここではｘ３座標）の浮動小数点実数データの仮数部の一部から、座標ごとに所定のパラメータ値を整数演算で計算し、調節頂点の頂点データにおける一座標（ここではｘ２座標）および別座標（ここではｘ３座標）の浮動小数点実数データの仮数部の一部を、所定のパラメータ値の変動を補償するために変更する。
【００６３】
この実施の形態では、式（３）に従って挿入頂点の頂点データが変更されるため、調節頂点のｘ２座標およびｘ３座標のデータにおける、ｎｘｊと同一の所定部分（図３（Ｂ）の場合、下位５ビット）ｎｘ’ａｄの値が、式（４）に従って変更される。
【００６４】
【数４】
【００６５】
ここで、Ｎ（ｍｖ）は、挿入頂点に隣接する頂点から調節頂点を除いた集合である。ｋは、０または１の値を有する係数であって、式（４）の右辺第１項から第２項を減算して得られる値が負である場合にはｋ＝１とし、式（４）の右辺第１項から第２項を減算して得られる値が正である場合にはｋ＝０とする。つまり、ｎｘ’ａｄが５ビットである場合、ｎｘ’ａｄの値は、０から３１（つまり、ｍａｘｉ）のいずれかの値であり、負とはならないため、このように計算される。
【００６６】
また、頂点種類特定部４１は、ある頂点の頂点データにおける、後述の付加情報および符号の取り出し元となる２つの座標以外の残りの座標（ここではｘ１座標）の浮動小数点実数データの仮数部の一部の値が上述の第１識別値である場合、その頂点を挿入頂点と特定し、仮数部の一部の値が上述の第２識別値である場合、その頂点を孤立頂点と特定する。
【００６７】
情報取出部４２は、この実施の形態に示す方法で付加情報を埋め込まれた３次元図形データ（図示せず）を、ＲＡＭ１３または記憶装置１４から読み出し、複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標（ここではｘ２座標）の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標（ここではｘ３座標）の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う。この一方向性関数は、付加情報を埋め込む際に使用される上述の一方向性関数と同一の関数である。
【００６８】
具体的には、情報取出部４２は、挿入頂点および孤立頂点の頂点データについて、付加情報および符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う。
【００６９】
情報取出部４２は、挿入頂点および孤立頂点の頂点データについて、式（１）に従って、ｘ２座標およびｘ３座標の重心ｎｘｃ２，ｎｘｃ３を計算するとともに、ｘ２座標およびｘ３座標のデータの仮数部の所定部分ｎｘ’２，ｎｘ’３を抽出し、式（５）に従って、付加情報ｗ’ｉおよび符号（埋め込み時のハッシュ値）ｈ’ｉを取り出す。なお、ｗ’ｉは、ｉ番目の付加情報を示し、ｈ’ｉは、ｉ番目の符号を示している。つまり、挿入頂点および孤立頂点の数が合計ｎ個であれば、ｎ対の付加情報および符号が取り出される。
【００７０】
【数５】
【００７１】
次に、上記情報処理装置の動作について説明する。ここでは、付加情報の埋め込みの際の動作と、付加情報の取り出しの際の動作とについて説明する。
【００７２】
（１）付加情報の埋め込み
【００７３】
図４は、本発明の実施の形態における付加情報の埋め込みについて説明するフローチャートである。
【００７４】
まず、頂点分類部３１は、図形データ２３を読み出し、図形データ２３における頂点を注目頂点として１つずつ選択し、分類処理を行っていく。
【００７５】
最初に、頂点分類部３１は、図形データ２３におけるすべての頂点を調節頂点候補とする（ステップＳ１）。例えば、各頂点の頂点データに関連付けて、その頂点の種類を示す頂点種類データがＲＡＭ１３上に設けられ、そのデータの初期値が、調節頂点候補を示す値とされる。
【００７６】
次に、頂点分類部３１は、注目頂点としてまだ処理していない頂点があるか否かを判定する（ステップＳ２）。
【００７７】
注目頂点としてまだ処理していない（つまり、挿入頂点、調節頂点および孤立頂点として確定しておらず、注目頂点として選択されていない）１または複数の頂点がある場合、頂点分類部３１は、その１または複数の頂点から１つの頂点を注目頂点として選択し（ステップＳ３）、その注目頂点に隣接する頂点を図形データ２３に基づいて特定し、その隣接する頂点の頂点種類データを参照して、その注目頂点に隣接する頂点がすべて調節頂点であるか否かを判定する（ステップＳ４）。
【００７８】
その注目頂点に隣接する頂点がすべて調節頂点である場合、頂点分類部３１は、その注目頂点を孤立頂点に分類し、その注目頂点の頂点種類データの値を、孤立頂点であることを示す値とする（ステップＳ５）。
【００７９】
一方、その注目頂点に隣接する頂点の少なくとも１つが調節頂点ではない場合、頂点分類部３１は、その注目頂点に隣接する頂点の少なくとも１つが調節頂点候補であるか否かを判定する（ステップＳ６）。
【００８０】
その注目頂点に隣接する頂点のいずれも調節頂点候補ではない場合、この注目頂点の処理を終了し、ステップＳ２に戻る。
【００８１】
一方、その注目頂点に隣接する頂点の少なくとも１つが調節頂点候補である場合、頂点分類部３１は、その注目頂点を挿入頂点とし、その注目頂点に隣接する調節頂点候補の１つを選択し、その選択した頂点を、その挿入頂点と対をなす調節頂点とする（ステップＳ７）。このとき、頂点分類部３１は、その注目頂点の頂点種類データの値を、挿入頂点であることを示す値とし、その選択した隣接頂点の頂点種類データの値を、調節頂点であることを示す値とする。また、この２つの頂点が対であることを示す情報も頂点種類データに含められる。
【００８２】
そして、頂点分類部３１は、その注目頂点に隣接する頂点のうちの、調節頂点以外の頂点を調節頂点候補から外す（ステップＳ８）。このとき、頂点分類部３１は、その注目頂点に隣接する頂点のうちの、調節頂点以外の頂点の頂点種別データの値を、調節頂点候補の値から、別の所定値へ変更する。
【００８３】
ステップＳ７，Ｓ８において挿入頂点と調節頂点との対が選択された後、この注目頂点の処理を終了し、ステップＳ２に戻る。
【００８４】
このようにして、図形データ２３についての一部または全部の頂点のそれぞれが、挿入頂点、調節頂点、および孤立頂点のいずれかに分類される。
【００８５】
ここで、具体例について説明する。図５は、本発明の実施の形態における挿入頂点および調節頂点の分類について説明する図である。図５（Ａ）は、図形データ２３による頂点およびリンクの一例を示している。この図形には、頂点＃１から頂点＃７が存在している。
【００８６】
まず、これらの頂点＃１〜＃７は、調節頂点候補とされる（ステップＳ１）。次に、頂点＃１が選択される（ステップＳ３）。頂点＃１について、隣接する頂点の少なくとも１つが調節頂点ではなく（ステップＳ４）、かつ隣接する頂点の少なくとも１つが調節頂点候補であるので（ステップＳ６）、図５（Ｂ）に示すように、頂点＃１は挿入頂点とされ、それに隣接する頂点のうちの頂点＃４が調節頂点とされる（ステップＳ７）。なお、図５において、黒丸の頂点は挿入頂点を表し、白丸の頂点は調節頂点を表している。そして、その他の隣接頂点である、頂点＃２、頂点＃３、および頂点＃５は、調節頂点候補から外される（ステップＳ８）。
【００８７】
次に、頂点種類が未確定である頂点＃２が選択される（ステップＳ３）。頂点＃２について、隣接する頂点の少なくとも１つが調節頂点ではなく（ステップＳ４）、かつ隣接する頂点の少なくとも１つが調節頂点候補であるので（ステップＳ６）、図５（Ｃ）に示すように、頂点＃２は挿入頂点とされ、それに隣接する頂点のうちの頂点＃６が調節頂点とされる（ステップＳ７）。そして、その他の隣接する調節頂点候補の頂点＃７は、調節頂点候補から外される（ステップＳ８）。
【００８８】
次に、頂点種類が未確定である頂点＃３が選択される（ステップＳ３）。頂点＃３について、隣接する頂点の少なくとも１つが調節頂点ではなく（ステップＳ４）、かつ隣接する頂点のいずれも調節頂点候補ではないので（ステップＳ６）、頂点＃３についての処理は終了する。
【００８９】
次に、頂点種類が未確定である頂点＃５が選択される（ステップＳ３）。頂点＃５について、隣接する頂点の少なくとも１つが調節頂点ではなく（ステップＳ４）、かつ隣接する頂点の少なくとも１つが調節頂点候補であるので（ステップＳ６）、図５（Ｄ）に示すように、頂点＃５は挿入頂点とされ、それに隣接する頂点のうちの頂点＃７が調節頂点とされる（ステップＳ７）。
【００９０】
そして、頂点種類が未確定である未処理の頂点がなくなったため、ここで、頂点種類の分類処理は終了される。
【００９１】
上述のようにして、頂点種類が分類された後、情報埋込部３２は、挿入頂点、調節頂点、孤立頂点、およびそれら以外について、まず、その頂点種類に応じて、式（２）に従って、Ｘ（ｘ１）座標を変更する（ステップＳ９）。つまり、情報埋込部３２は、頂点種類データの値に基づいて頂点種類を特定し、式（２）に従って、変更後のＸ（ｘ１）座標の値を特定し、その頂点の頂点データのＸ（ｘ１）座標の値をその特定した値で変更する。
【００９２】
次に、情報埋込部３２は、各挿入頂点について、Ｙ（ｘ２）座標およびＺ（ｘ３）座標の値を、式（３）に従って変更する（ステップＳ１０）。さらに、情報埋込部３２は、その挿入頂点と対をなす調節頂点について、Ｙ（ｘ２）座標およびＺ（ｘ３）座標の値を、式（４）に従って変更する（ステップＳ１１）。
【００９３】
また、情報埋込部３２は、各孤立頂点について、Ｙ（ｘ２）座標およびＺ（ｘ３）座標の値を、式（３）に従って変更する（ステップＳ１２）。
【００９４】
このようにして、図形データ２３から、付加情報が埋め込まれた図形データが生成される。なお、頂点種別データは、図形データへの付加情報の埋め込み時のみに使用され、付加情報が埋め込まれた図形データには付加されていない。このようにして生成された図形データは、例えば記憶装置１４に記憶される。
【００９５】
（２）付加情報の取り出し
【００９６】
上述のようにして付加情報が埋め込まれた図形データからは、付加情報を取り出すことが可能である。
【００９７】
図６は、本発明の実施の形態における付加情報の取り出しについて説明するフローチャートである。
【００９８】
頂点種類特定部４１は、注目頂点としてまだ処理していない頂点があるか否かを判定する（ステップＳ２１）。
【００９９】
注目頂点としてまだ処理していない１または複数の頂点がある場合、頂点種類特定部４１は、その１または複数の頂点から１つの頂点を注目頂点として選択し（ステップＳ２２）、その注目頂点の頂点種別がその注目頂点の頂点データにおけるＸ（ｘ１）座標の値に基づいて特定する（ステップＳ２３）。式（２）に示す分類に基づいて、頂点種別が特定される。
【０１００】
そして、その注目頂点の頂点種別が挿入頂点である場合（ステップＳ２４）、情報取出部４２は、その注目頂点の頂点データにおけるＹ（ｘ２）座標およびＺ（ｘ３）座標の値から、式（５）に従って付加情報ｗ’と符号ｈ’を取り出す（ステップＳ２５）。
【０１０１】
次に、情報取出部４２は、この付加情報ｗ’とｘ３座標の仮数部のｎｘ３以外の残りのビット領域Ｎｖｈ’とを引数として、式（３）におけるハッシュ関数ｈの値を計算し、その値と符号ｈ’とを比較し、両者が一致した場合、付加情報ｗ’が正しい（改ざんされていない）ものと認め、両者が一致しない場合、付加情報ｗ’が正しくない（改ざんされている）ものと認める（ステップＳ２６）。
【０１０２】
一方、その注目頂点の頂点種別が挿入頂点ではなく孤立頂点である場合（ステップＳ２７）、情報取出部４２は、その注目頂点の頂点データにおけるＹ（ｘ２）座標およびＺ（ｘ３）座標の値から、式（５）に従って付加情報ｗ’と符号ｈ’を取り出す（ステップＳ２８）。
【０１０３】
次に、情報取出部４２は、この付加情報ｗ’とｘ３座標の仮数部のｎｘ３以外の残りのビット領域Ｎｖｈ’とを引数として、式（３）におけるハッシュ関数ｈの値を計算し、その値と符号ｈ’とを比較し、両者が一致した場合、付加情報ｗ’が正しい（改ざんされていない）ものと認め、両者が一致しない場合、付加情報ｗ’が正しくない（改ざんされている）ものと認める（ステップＳ２９）。
【０１０４】
このようにして付加情報が埋め込まれた図形データから付加情報が取り出され、その付加情報の認証が行われる。
【０１０５】
以上のように、上記実施の形態によれば、付加情報の埋め込みにおいて、図形データ２３における複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号を埋め込む。
【０１０６】
また、上記実施の形態によれば、その付加情報の取り出しにおいて、図形データにおける複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した符号と仮数部の残りの部分とから一方向性関数により得られる値で、取り出した符号の認証を行う。
【０１０７】
これにより、少なくともその仮数部の残りの部分と付加情報とから一方向性関数により得られる符号が埋め込まれるため、付加情報の取り出しの際に、データの改ざんが検出されやすくなる。
【０１０８】
なお、上述の実施の形態は、本発明の好適な例であるが、本発明は、これらに限定されるものではなく、本発明の要旨を逸脱しない範囲において、種々の変形、変更が可能である。
【０１０９】
例えば、上記実施の形態において、ハッシュ関数に別の引数を追加してもよい。
【０１１０】
また、上記実施の形態では、図１に示す情報処理装置では、付加情報の埋め込みおよび付加情報の取り出しの両方を実行可能であるが、付加情報の埋め込みおよび付加情報の取り出しの一方のみを実行可能な装置としてもよい。
【０１１１】
また、上記実施の形態において、図形データがポリゴンデータである場合、ある頂点から延びるポリゴンの辺をリンクとするようにしてもよい。
【０１１２】
また、上記実施の形態において、ハッシュ関数の代わりに、他の一方向性関数を使用するようにしてもよい。
【０１１３】
また、上記実施の形態において、埋め込み時に変更される仮数部におけるビット部分の長さは、５ビットに限定されるものではない。
【産業上の利用可能性】
【０１１４】
本発明は、例えば、電子透かしの埋め込みおよび取り出しに適用可能である。
【符号の説明】
【０１１５】
１３ ＲＡＭ（記憶手段の一例）
１４ 記憶装置（記憶手段の一例）
２１ 埋め込みプログラム（コンピュータプログラムの一例）
２２ 取り出しプログラム（コンピュータプログラムの一例）
２３ 図形データ（３次元図形データの一例）
３１ 頂点分類部（頂点分類手段の一例）
３２ 情報埋込部（情報埋込手段の一例）
４１ 頂点種類特定部（頂点種類特定手段の一例）
４２ 情報取出部（情報取出手段の一例）
【特許請求の範囲】
【請求項１】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段と、
前記記憶手段から前記３次元図形データを読み出し、前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくとも前記仮数部の残りの部分と前記付加情報とから一方向性関数により得られる符号を埋め込む情報埋込手段と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記複数の頂点の一部または全部を、挿入頂点、調節頂点、および孤立頂点に分類する頂点分類手段を備え、
前記挿入頂点は、前記調節頂点と対になり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記調節頂点は、前記挿入頂点と対になり、前記挿入頂点への前記付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点であり、
前記孤立頂点は、隣接する頂点がすべて前記調節頂点であり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記情報埋込手段は、前記挿入頂点の前記頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部に、前記挿入頂点であることを示す所定の第１識別値を埋め込み、前記孤立頂点の前記頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部に、当該頂点が前記孤立頂点であることを示す所定の第２識別値を埋め込み、
前記第２識別値は、前記第１識別値とは異なること、
を特徴とする請求項１記載の情報処理装置。
【請求項３】
前記複数の頂点の一部または全部を、挿入頂点および調節頂点に分類する頂点分類手段を備え、
前記挿入頂点は、前記調節頂点と対になり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記調節頂点は、前記挿入頂点と対になり、前記挿入頂点への前記付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点であり、
前記情報埋込手段は、前記挿入頂点に隣接する頂点の頂点データにおける一座標および別座標の浮動小数点実数データの仮数部の一部から座標ごとに前記所定のパラメータ値を整数演算で計算し、前記調節頂点の頂点データにおける一座標および別座標の浮動小数点実数データの仮数部の一部を、前記所定のパラメータ値の変動を補償するために変更すること、
を特徴とする請求項１記載の情報処理装置。
【請求項４】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段を有する情報処理装置におけるコンピュータを、
前記記憶手段から前記３次元図形データを読み出し、前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくとも前記仮数部の残りの部分と前記付加情報とから一方向性関数により得られる符号を埋め込む情報埋込手段
として機能させるコンピュータプログラム。
【請求項５】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶手段から読み出すステップと、
前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込むステップと、
その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくとも前記仮数部の残りの部分と前記付加情報とから一方向性関数により得られる符号を埋め込むステップと、
を備えることを特徴とする情報処理方法。
【請求項６】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段と、
前記記憶手段から前記３次元図形データを読み出し、前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した前記符号と前記仮数部の残りの部分とから一方向性関数により得られる値で、取り出した前記符号の認証を行う情報取出手段と、
を備えることを特徴とする情報処理装置。
【請求項７】
ある頂点の前記頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部の値が所定の第１識別値である場合、その頂点を挿入頂点と特定し、前記仮数部の一部の値が所定の第２識別値である場合、その頂点を孤立頂点と特定する頂点種類特定手段を備え、
前記挿入頂点は、調節頂点と対になり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記調節頂点は、前記挿入頂点と対になり、前記挿入頂点への前記付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点であり、
前記孤立頂点は、隣接する頂点がすべて前記調節頂点であり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記第２識別値は、前記第１識別値とは異なり、
前記情報取出手段は、前記挿入頂点および前記孤立頂点の前記頂点データについて、前記付加情報および前記符号を取り出し、少なくとも取り出した前記符号と前記仮数部の残りの部分とから一方向性関数により得られる値で、取り出した前記符号の認証を行うこと、
を特徴とする請求項６記載の情報処理装置。
【請求項８】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段を有する情報処理装置におけるコンピュータを、
前記記憶手段から前記３次元図形データを読み出し、前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した前記符号と前記仮数部の残りの部分とから一方向性関数により得られる値で、取り出した前記符号の認証を行う情報取出手段
として機能させるコンピュータプログラム。
【請求項９】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを前記記憶手段から読み出すステップと、
前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出すステップと、
その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出すステップと、
少なくとも取り出した前記符号と前記仮数部の残りの部分とから一方向性関数により得られる値で、取り出した前記符号の認証を行うステップと、
を備えることを特徴とする情報処理方法。
【請求項１】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段と、
前記記憶手段から前記３次元図形データを読み出し、前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくとも前記仮数部の残りの部分と前記付加情報とから一方向性関数により得られる符号を埋め込む情報埋込手段と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記複数の頂点の一部または全部を、挿入頂点、調節頂点、および孤立頂点に分類する頂点分類手段を備え、
前記挿入頂点は、前記調節頂点と対になり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記調節頂点は、前記挿入頂点と対になり、前記挿入頂点への前記付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点であり、
前記孤立頂点は、隣接する頂点がすべて前記調節頂点であり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記情報埋込手段は、前記挿入頂点の前記頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部に、前記挿入頂点であることを示す所定の第１識別値を埋め込み、前記孤立頂点の前記頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部に、当該頂点が前記孤立頂点であることを示す所定の第２識別値を埋め込み、
前記第２識別値は、前記第１識別値とは異なること、
を特徴とする請求項１記載の情報処理装置。
【請求項３】
前記複数の頂点の一部または全部を、挿入頂点および調節頂点に分類する頂点分類手段を備え、
前記挿入頂点は、前記調節頂点と対になり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記調節頂点は、前記挿入頂点と対になり、前記挿入頂点への前記付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点であり、
前記情報埋込手段は、前記挿入頂点に隣接する頂点の頂点データにおける一座標および別座標の浮動小数点実数データの仮数部の一部から座標ごとに前記所定のパラメータ値を整数演算で計算し、前記調節頂点の頂点データにおける一座標および別座標の浮動小数点実数データの仮数部の一部を、前記所定のパラメータ値の変動を補償するために変更すること、
を特徴とする請求項１記載の情報処理装置。
【請求項４】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段を有する情報処理装置におけるコンピュータを、
前記記憶手段から前記３次元図形データを読み出し、前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込み、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくとも前記仮数部の残りの部分と前記付加情報とから一方向性関数により得られる符号を埋め込む情報埋込手段
として機能させるコンピュータプログラム。
【請求項５】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶手段から読み出すステップと、
前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部に付加情報を埋め込むステップと、
その頂点データにおける別座標の浮動小数点実数データの仮数部の一部に、少なくとも前記仮数部の残りの部分と前記付加情報とから一方向性関数により得られる符号を埋め込むステップと、
を備えることを特徴とする情報処理方法。
【請求項６】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段と、
前記記憶手段から前記３次元図形データを読み出し、前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した前記符号と前記仮数部の残りの部分とから一方向性関数により得られる値で、取り出した前記符号の認証を行う情報取出手段と、
を備えることを特徴とする情報処理装置。
【請求項７】
ある頂点の前記頂点データにおける残りの座標の浮動小数点実数データの仮数部の一部の値が所定の第１識別値である場合、その頂点を挿入頂点と特定し、前記仮数部の一部の値が所定の第２識別値である場合、その頂点を孤立頂点と特定する頂点種類特定手段を備え、
前記挿入頂点は、調節頂点と対になり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記調節頂点は、前記挿入頂点と対になり、前記挿入頂点への前記付加情報の埋め込みに起因して発生する所定のパラメータ値の変動を補償するために座標値を変更させられる頂点であり、
前記孤立頂点は、隣接する頂点がすべて前記調節頂点であり、前記頂点データに前記付加情報を埋め込む頂点であり、
前記第２識別値は、前記第１識別値とは異なり、
前記情報取出手段は、前記挿入頂点および前記孤立頂点の前記頂点データについて、前記付加情報および前記符号を取り出し、少なくとも取り出した前記符号と前記仮数部の残りの部分とから一方向性関数により得られる値で、取り出した前記符号の認証を行うこと、
を特徴とする請求項６記載の情報処理装置。
【請求項８】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを記憶する記憶手段を有する情報処理装置におけるコンピュータを、
前記記憶手段から前記３次元図形データを読み出し、前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出し、その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出し、少なくとも取り出した前記符号と前記仮数部の残りの部分とから一方向性関数により得られる値で、取り出した前記符号の認証を行う情報取出手段
として機能させるコンピュータプログラム。
【請求項９】
３次元図形を構成する複数の頂点に対応する複数の頂点データを有する３次元図形データを前記記憶手段から読み出すステップと、
前記複数の頂点データのうちの少なくとも１つの頂点データについて、その頂点データにおける一座標の浮動小数点実数データの仮数部の一部から付加情報を取り出すステップと、
その頂点データにおける別座標の浮動小数点実数データの仮数部の一部から符号を取り出すステップと、
少なくとも取り出した前記符号と前記仮数部の残りの部分とから一方向性関数により得られる値で、取り出した前記符号の認証を行うステップと、
を備えることを特徴とする情報処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−１６９７３２（Ｐ２０１２−１６９７３２Ａ）
【公開日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願番号】特願２０１１−２６９９３（Ｐ２０１１−２６９９３）
【出願日】平成２３年２月１０日（２０１１．２．１０）
【出願人】（５０６２０９４２２）地方独立行政法人 東京都立産業技術研究センター (134)
【Ｆターム（参考）】
【公開日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願日】平成２３年２月１０日（２０１１．２．１０）
【出願人】（５０６２０９４２２）地方独立行政法人 東京都立産業技術研究センター (134)
【Ｆターム（参考）】
[ Back to top ]