(57)【要約】情報埋め込みは、ベクトルデータから多角形を構成する頂点を抽出し、埋め込み情報に基づいて、多角形の辺上に存在する点の個数を変更することで埋め込み処理を行う。情報読み取りは、情報埋め込み済みベクトルデータから、多角形の辺上に存在する点を抽出し、所定の規則により、埋め込み情報を読み取る。
2005020563.tif 000002
【特許請求の範囲】
【請求項１】
多角形の情報を含むベクトルデータから多角形を構成する頂点の情報を抽出する抽出部と、
前記抽出部により抽出された頂点の情報を利用し、回転操作に対してロバストな態様で、前記ベクトルデータに埋め込み情報を埋め込む情報埋め込み部とを備える情報埋め込み装置。
【請求項２】
前記情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の点の総数を操作する請求の範囲第１項記載の情報埋め込み装置。
【請求項３】
前記情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の特定点間の距離を操作する請求の範囲第１項記載の情報埋め込み装置。
【請求項４】
前記情報埋め込み部は、埋め込み情報に基づいて、多角形の辺上に存在する点の個数を変更する請求の範囲第１項記載の情報埋め込み装置。
【請求項５】
前記情報埋め込み部は、多角形の辺上に点を挿入する請求の範囲第１項記載の情報埋め込み装置。
【請求項６】
前記情報埋め込み部は、多角形の辺から離れた位置に点を挿入する請求の範囲第１項記載の情報埋め込み装置。
【請求項７】
前記情報埋め込み部は、多角形の辺上に存在する点の個数を定数Ｎ（Ｎは２以上の整数）で割った剰余の値と、埋め込み情報の値Ｍ（Ｍは非負整数、Ｍ＜Ｎ）とが一定の対応関係を持つように、多角形の辺上に存在する点の個数を変更する請求の範囲第１項記載の情報埋め込み装置。
【請求項８】
前記一定の対応関係は、前記剰余の値と、前記埋め込み情報の値Ｍとが等しいという関係である請求の範囲第７項記載の情報埋め込み装置。
【請求項９】
前記情報埋め込み部は、定数Ｎ（Ｎは２以上の整数）を入力する定数情報入力部と、
前記抽出部により抽出された頂点の個数を前記定数Ｎで割った剰余を計算する剰余計算部と、
前記剰余計算部が計算した剰余と埋め込み情報とが一定の対応関係を持つように、前記多角形の辺上に挿入する点の個数を決定する挿入個数決定部と、
前記挿入個数決定部により決定された個数の点を多角形に挿入する挿入実行部とを備える請求の範囲第４項記載の情報埋め込み装置。
【請求項１０】
前記定数Ｎは、多角形の頂点数に依存しない定数である請求の範囲第１項記載の情報埋め込み装置。
【請求項１１】
情報埋め込み済ベクトルデータから、多角形上の点を抽出する抽出部と、
前記抽出部により抽出された点の個数と所定の規則とに基づいて、埋め込み情報を読み取る情報読み取り部とを備える情報読み取り装置。
【請求項１２】
前記所定の規則は、前記抽出部により抽出された点の個数を定数Ｎ（Ｎは２以上の整数）で割った剰余の値と、埋め込み情報の値とが、一定の対応関係を持つという規則である請求の範囲第１１項記載の情報読み取り装置。
【請求項１３】
前記一定の対応関係は、前記剰余の値と前記埋め込み情報の値Ｍとが、等しいという関係である請求の範囲第１２項記載の情報読み取り装置。
【請求項１４】
前記情報読み取り部は、
前記抽出部により抽出された点の個数を算出する個数算出部と、
定数Ｎ（Ｎは２以上の整数）を入力する定数情報入力部と、
前記個数算出部により算出された個数を前記定数Ｎで割った剰余を計算する剰余計算部と、
前記剰余計算部により計算された剰余に基づいて埋め込み情報を読み取る情報読み取り部とを備える請求の範囲第１１項記載の情報読み取り装置。
【請求項１５】
前記情報埋め込み部は、埋め込み情報に基づいて、前記多角形に関する複数の幾何学要素の対応関係が変化するように前記多角形について予め設定された代表点を変化させる請求の範囲第１項記載の情報埋め込み装置。
【請求項１６】
前記代表点は、前記多角形の頂点を含む請求の範囲第１５項記載の情報埋め込み装置。
【請求項１７】
前記複数の幾何学要素は、前記多角形の対角線と、前記多角形の重心と、前記多角形の頂点と前記多角形の代表点とからなる群から選択されたものである請求の範囲第１５項記載の情報埋め込み装置。
【請求項１８】
前記対角線は、最長の対角線である請求の範囲第１７項記載の情報埋め込み装置。
【請求項１９】
前記情報埋め込み部は、前記最長の対角線が最長性を保つように前記代表点を変化させる請求の範囲第１８項記載の情報埋め込み装置。
【請求項２０】
前記対応関係は、前記複数の幾何学要素間の距離で表現される請求の範囲第１５項記載の情報埋め込み装置。
【請求項２１】
前記情報埋め込み部は、前記埋め込み情報の値と前記複数の幾何学要素との対応関係を決定する対応関係決定部と、
前記対応関係決定部により決定された対応関係に基づいて、前記代表点を変化させる埋め込み部とを備える請求の範囲第１５項記載の情報埋め込み装置。
【請求項２２】
前記代表点は、前記多角形の重心である請求の範囲第１５項記載の情報埋め込み装置。
【請求項２３】
前記代表点は、施設位置を指示する請求の範囲第１５項記載の情報埋め込み装置。
【請求項２４】
情報埋め込み済ベクトルデータから多角形上の点を抽出する抽出部と、
前記抽出部により抽出された点と、前記多角形に関する複数の幾何学要素の対応関係とに基づいて、前記ベクトルデータに埋め込まれた情報を読み取る情報読み取り部とを備える情報読み取り装置。
【請求項２５】
前記複数の幾何学要素は、前記多角形の対角線と、前記多角形の重心と、前記多角形の頂点と前記多角形の代表点とからなる群から選択されたものである請求の範囲第２４項記載の情報読み取り装置。
【請求項２６】
前記情報読み取り部は、前記抽出部により抽出された点と、前記多角形に関する複数の幾何学要素の対応関係とを検討する対応関係検討部と、
前記対応関係検討部の検討結果に基づいて、前記ベクトルデータに埋め込まれた情報を読み取る読み取り部とを備える請求の範囲第２４項記載の情報読み取り装置。
【請求項２７】
前記情報埋め込み部は、前記抽出部により抽出された頂点のうち、隣り合う２つの頂点間に挿入すべき挿入点を決定する挿入部と、
前記挿入部により決定された挿入点を前記隣り合う２つの頂点間に挿入する埋め込み部とを備え、
前記挿入部は、前記抽出部により抽出された頂点により構成される第１の図形の重心と、前記挿入部により決定された少なくとも３個の挿入点により構成される第２の図形の重心との関係を、埋め込み情報にしたがって変更する請求の範囲第１項記載の情報埋め込み装置。
【請求項２８】
前記第１の図形は、前記抽出部により抽出された多角形であり、前記第２の図形は、前記挿入部が決定した全ての挿入点により構成される請求の範囲第２７項記載の情報埋め込み装置。
【請求項２９】
前記第１の図形の重心と前記第２の図形の重心との関係は、前記第１の図形の重心と前記第２の図形の重心とが、一致するか否かにより評価される請求の範囲第２７項記載の情報埋め込み装置。
【請求項３０】
情報埋め込み済ベクトルデータから多角形の複数の点を抽出する抽出部と、
前記抽出部により抽出された複数の点を、第１の集合と第２の集合に分類し、前記第１の集合に属する複数の点から構成される第１の図形の重心と、前記第２の集合に属する複数の点から構成される第２の図形の重心とを求める分類部と、
前記第１の図形の重心と前記第２の図形の重心との距離を算出する算出部と、
前記算出部により算出された距離に基づいて埋め込まれた情報を読み取る読み取り部とを備える情報読み取り装置。
【請求項３１】
情報埋め込み済ベクトルデータから多角形の複数の点を抽出する抽出部と、
前記抽出部により抽出された複数の点に基づいて埋め込まれた情報を読み取る情報読み取り部とを備え、
前記情報読み取り部は、
前記抽出部により抽出された複数の点を、第１の集合と第２の集合とに分類し、前記第１の集合に属する複数の点から構成される第１の図形の重心と、前記第２の集合に属する複数の点から構成される第２の図形の重心とを求める分類部と、
前記第１の図形の重心と前記第２の図形の重心との距離を算出する算出部と、
前記算出部により算出された距離に基づいて埋め込まれた情報を読み取る読み取り部とを備える情報読み取り装置。
【請求項３２】
前記分類部は、前記抽出部により抽出された複数の点に連続番号を付し、前記連続番号の偶奇により前記抽出部により抽出された複数の点を分類する請求の範囲第３１項記載の情報読み取り装置。
【請求項３３】
多角形の情報を含むベクトルデータから多角形を構成する頂点の情報を抽出する抽出プロセスと、
前記抽出プロセスにおいて抽出された頂点の情報を利用し、前記ベクトルデータの座標系が回転操作されても埋め込み情報が保持される態様で、前記ベクトルデータに埋め込み情報を埋め込む情報埋め込みプロセスとを備えるプログラムをコンピュータ読み取り可能に記録した記録媒体。
【請求項３４】
機器固有値を保持する機器固有値保持部と、
前記機器固有値保持部が保持する機器固有値を埋め込み情報に含め多角形の情報を含むベクトルデータに埋め込み情報を埋め込む情報埋め込み装置とを備え、
前記情報埋め込み装置は、
前記ベクトルデータから多角形を構成する頂点の情報を抽出する抽出部と、
前記抽出部により抽出された頂点の情報を利用し、回転操作に対してロバストな態様で、前記ベクトルデータに埋め込み情報を埋め込む情報埋め込み部とを備える電子機器。
【請求項３５】
前記情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の点の総数を操作する請求の範囲第３４項記載の電子機器。
【請求項３６】
前記情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の特定点間の距離を操作する請求の範囲第３４項記載の電子機器。
【請求項３７】
前記埋め込み情報は、著作権情報を格納する第１ビット領域の値と前記機器固有値を格納する第２ビット領域の値とから構成される請求の範囲第３４項記載の電子機器。
【発明の詳細な説明】
【技術分野】  本発明は、ベクトルデータに埋め込み情報を埋め込む情報埋め込み装置及びその関連技術に関するものである。
【背景技術】  カーナビゲーションシステムやインターネットの普及に伴い、電子地図の需要が高まっている。電子地図のようなデジタルコンテンツに対しては、容易にそのコピーを作成することができる。このため、不正コピーが増加傾向にあり、著作権保護が重要な問題となっている。
文献１（日本国特開２００１−７８０１９号公報）は、次のような情報埋め込み手法を開示する。
図３４を用いて、文献１が開示する情報の埋め込み方法を説明する。図３４の各図において、横軸、縦軸は、それぞれ、ｘ座標軸、ｙ座標軸である。
まず、埋め込み対象点Ａから、基準点Ｓが算出される。より具体的には、基準点Ｓは、埋め込み対象点Ａの座標の下位桁を、埋め込み情報に応じてマスクして求められる。
図３４（ａ）の斜線領域は、埋め込み対象点Ａに対して、基準点Ｓがとりうる範囲を示す。
また、図３４（ａ）の斜線領域は、図３４（ｂ）の領域αと図３４（ｃ）の領域βに分けられる。領域αは、埋め込み情報「１」の場合に使用され、領域βは埋め込み情報「０」の場合に使用される。
即ち、埋め込み情報「１」の場合、埋め込み対象点Ａは、例えば図３４（ｂ）の点Ｂへ移動され、埋め込み情報「０」の場合、埋め込み対象点Ａは、例えば図３４（ｃ）の点Ｂへ移動される。
埋め込み情報（「１」または「０」）を読み出すには、上述と同様に、基準点Ｓが求められ、領域α（図３４（ｂ））と領域β（図３４（ｃ））とが求められる。そして、点Ｂが領城αと領域βのいずれに属するかによって、埋め込み情報が定められる。
また、文献２（日本国特開２００２−３００３７４号公報）は、次の技術を開示する。
まず、図３５（ａ）に示すように、２つの基準点Ａ、Ｂが抽出される。これらの基準点Ａ、Ｂは、いずれも図形の端点である。
次に、基準点Ａ、Ｂのｘ座標に基づいて、基準点ＡＢ間がｎ等分（ここでは、ｎ＝５）され、各区間に１ビットの情報が埋め込まれる。
ここで、情報「０」が埋め込まれる場合、区間内にある点の個数が偶数個にされ、情報「１」を埋め込む場合、区間内にある点の個数が奇数個にされる。
また、埋め込み情報を読み出すには、上述と同様に、各区間を定め、これらの区間内の点の個数が奇数／偶数のいずれであるかにより、埋め込み情報の値が「１」／「０」のいずれであるかを決定すればよい。
文献１、２では、情報の埋め込み時と情報の読み出し時の間で、ｘｙ座標系が変化する場合を予定しておらず、当然、それに対応していない。したがって、情報の埋め込み時と情報の読み出し時の間に、図形が回転操作されると、操作後のベクトルデータのみから、埋め込み情報を正確に読み出すことができなくなる。
この点は、例えば、地図データのように、回転操作が何度も発生する場合において、顕著となり、文献１、２の手法は、このような性質を持つベクトルデータには、事実上適用できない。
【発明の開示】
そこで本発明は、ベクトルデータの回転操作に対応できる情報埋め込み装置を提供することを目的とする。
第１の発明に係る情報埋め込み装置は、多角形の情報を含むベクトルデータから多角形を構成する頂点の情報を抽出する抽出部と、抽出部により抽出された頂点の情報を利用し、回転操作に対してロバストな態様で、ベクトルデータに埋め込み情報を埋め込む情報埋め込み部とを備える。
この構成により、ベクトルデータが回転操作を受けても、埋め込み情報が保持され、後に埋め込み情報を読み出す際に支障を生じない。
第２の発明に係る情報埋め込みは、情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の点の総数を操作する。
この構成において、多角形の点の総数は、多角形が回転しても変化しないし、悪意の第三者が埋め込み情報を無効にするため、多角形の点を移動したとしても、後に埋め込み情報を読み出す際に支障を生じない。
第３の発明に係る情報埋め込み装置は、情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の特定点間の距離を操作する。
この構成において、多角形の特定点間の距離は、多角形が回転しても変化せず、後に埋め込み情報を読み出す際に支障を生じない。
第４の発明に係る情報埋め込みは、情報埋め込み部は、埋め込み情報に基づいて、多角形の辺上に存在する点の個数を変更する。
この構成により、多角形の点の総数が変化する。
第５の発明に係る情報埋め込み装置は、情報埋め込み部は、多角形の辺上に点を挿入する。
この構成により、点が挿入された後も、多角形の形状は変化しない。
第６の発明に係る情報埋め込みは、情報埋め込み部は、多角形の辺から離れた位置に点を挿入する。
この構成により、点の挿入により、多角形の形状をひずませることができる。
第７の発明に係る情報埋め込み装置は、情報埋め込み部は、多角形の辺上に存在する点の個数を定数Ｎ（Ｎは２以上の整数）で割った剰余の値と、埋め込み情報の値Ｍ（Ｍは非負整数、Ｍ＜Ｎ）とが一定の対応関係を持つように、多角形の辺上に存在する点の個数を変更する。
第８の発明に係る情報埋め込み装置は、一定の対応関係は、剰余の値と、埋め込み情報の値Ｍとが等しいという関係である。
第９の発明に係る情報埋め込み装置は、情報埋め込み部は、定数Ｎ（Ｎは２以上の整数）を入力する定数情報入力部と、抽出部により抽出された頂点の個数を定数Ｎで割った剰余を計算する剰余計算部と、剰余計算部が計算した剰余と埋め込み情報とが一定の対応関係を持つように、多角形の辺上に挿入する点の個数を決定する挿入個数決定部と、挿入個数決定部により決定された個数の点を多角形に挿入する挿入実行部とを備える。
これらの構成により、剰余の値と埋め込み情報の値との対応関係から、埋め込み情報を容易に特定できる。
第１０の発明に係る情報埋め込み装置は、定数Ｎは、多角形の頂点数に依存しない定数である。
この構成により、多角形の辺数がどうであっても、一定の規則で埋め込み情報を埋め込める。
第１１の発明に係る情報読み取り装置は、情報埋め込み済ベクトルデータから、多角形上の点を抽出する抽出部と、抽出部により抽出された点の個数と所定の規則とに基づいて、埋め込み情報を読み取る情報読み取り部とを備える。
第１２の発明に係る情報読み取り装置は、所定の規則は、抽出部により抽出された点の個数を定数Ｎ（Ｎは２以上の整数）で割った剰余の値と、埋め込み情報の値とが、一定の対応関係を持つという規則である。
第１３の発明に係る情報読み取り装置は、一定の対応関係は、剰余の値と埋め込み情報の値Ｍとが、等しいという関係である。
これらの構成により、回転操作によって失われない埋め込み情報を、確実に読み取ることができる。
第１４の発明に係る情報読み取り装置は、情報読み取り部は、抽出部により抽出された点の個数を算出する個数算出部と、定数Ｎ（Ｎは２以上の整数）を入力する定数情報入力部と、個数算出部により算出された個数を定数Ｎで割った剰余を計算する剰余計算部と、剰余計算部により計算された剰余に基づいて埋め込み情報を読み取る情報読み取り部とを備える。
この構成により、剰余に基づいて、埋め込み情報を特定できる。
第１５の発明に係る情報埋め込み装置は、情報埋め込み部は、埋め込み情報に基づいて、多角形に関する複数の幾何学要素の対応関係が変化するように多角形について予め設定された代表点を変化させる。
第１６の発明に係る情報埋め込み装置は、代表点は、多角形の頂点を含む。
第１７の発明に係る情報埋め込み装置は、複数の幾何学要素は、多角形の対角線と、多角形の重心と、多角形の頂点と多角形の代表点とからなる群から選択されたものである。
これらの構成により、多角形の幾何学的性質を反映し、多角形に埋め込み情報を埋め込むことができる。
第１８の発明に係る情報埋め込み装置は、対角線は、最長の対角線である。
第１９の発明に係る情報埋め込み装置は、情報埋め込み部は、最長の対角線が最長性を保つように代表点を変化させる。
これらの構成により、対象となる対角線を容易に特定できる。
第２０の発明に係る情報埋め込み装置は、対応関係は、複数の幾何学要素間の距離で表現される。
この構成により、距離により対応関係を表現できる。
第２１の発明に係る情報埋め込み装置は、情報埋め込み部は、埋め込み情報の値と複数の幾何学要素との対応関係を決定する対応関係決定部と、対応関係決定部により決定された対応関係に基づいて、代表点を変化させる埋め込み部とを備える。
第２２の発明に係る情報埋め込み装置は、代表点は、多角形の重心である。
これらの構成により、多角形の幾何学的性質を反映し、多角形に埋め込み情報を埋め込むことができる。
第２３の発明に係る情報埋め込みは、代表点は、施設位置を指示する。
この構成により、多角形の形状を変更せず、多角形に埋め込み情報を埋め込むことができる。
【図面の簡単な説明】図１は、本発明の実施の形態１における情報埋め込み装置の機能ブロック図である。
図２は、本発明の実施の形態１における情報埋め込み装置のフローチャートである。
図３（ａ）から図３（ｄ）は、本発明の実施の形態１における多角形の例示図である。
図４（ａ）は、本発明の実施の形態１における多角形の例示図である。
図４（ｂ）は、本発明の実施の形態１における埋め込み情報の関係図である。
図５（ａ）から図５（ｅ）は、本発明の実施の形態１における情報埋め込み例の説明図である。
図６（ａ）は、本発明の実施の形態１における多角形の例示図である。
図６（ｂ）は、本発明の実施の形態１における埋め込み情報の関係図である。
図７（ａ）から図７（ｅ）は、本発明の実施の形態１における情報埋め込み例の説明図である。
図８は、本発明の実施の形態２における情報読み取り装置の機能ブロック図である。
図９は、本発明の実施の形態２における情報読み取り装置のフローチャートである。
図１０（ａ）から図１０（ｂ）は、本発明の実施の形態２における埋め込み情報の関係図である。
図１１は、本発明の実施の形態における情報埋め込み／読み取り装置のブロック図である。
図１２は、本発明の実施の形態３における情報埋め込み装置の機能ブロック図である。
図１３は、本発明の実施の形態３における情報埋め込み装置のフローチャートである。
図１４（ａ）から図１４（ｃ）は、本発明の実施の形態３における多角形の例示図である。
図１５（ａ）から図１５（ｂ）は、本発明の実施の形態３における重心の説明図である。
図１６は、本発明の実施の形態４における情報読み取り装置の機能ブロック図である。
図１７は、本発明の実施の形態４における情報読み取り装置のフローチャートである。
図１８（ａ）から図１８（ｂ）は、本発明の実施の形態４における多角形の例示図である。
図１９は、本発明の実施の形態５における情報埋め込み装置の機能ブロック図である。
図２０は、本発明の実施の形態５における情報埋め込み装置のフローチャートである。
図２１（ａ）から図２１（ｃ）は、本発明の実施の形態５における多角形の例示図である。
図２２は、本発明の実施の形態６における情報読み取り装置の機能ブロック図である。
図２３は、本発明の実施の形態６における情報読み取り装置のフローチャートである。
図２４（ａ）から図２４（ｂ）は、本発明の実施の形態６における多角形の例示図である。
図２５は、本発明の実施の形態７における情報埋め込み装置の機能ブロック図である。
図２６は、本発明の実施の形態７における情報埋め込み装置のフローチャートである。
図２７（ａ）から図２７（ｂ）は、本発明の実施の形態７における重心の説明図である。
図２８は、本発明の実施の形態８における情報読み取り装置の機能ブロック図である。
図２９は、本発明の実施の形態８における情報埋め込み装置のフローチャートである。
図３０（ａ）から図３０（ｂ）は、本発明の実施の形態８における重心の説明図である。
図３１（ａ）は、本発明の実施の形態９における電子機器のシステム構成図、
図３１（ｂ）は、本発明の実施の形態９における電子機器の機能ブロック図である。
図３２（ａ）は、本発明の実施の形態９における埋め込み情報のデータ構成図である。
図３２（ｂ）は、本発明の実施の形態９における不正複写摘発の手順図である。
図３３は、本発明の実施の形態９における電子機器のフローチャートである。
図３４（ａ）から図３４（ｃ）は、従来の情報埋め込み／情報読み取りの説明図である。
図３５（ａ）から図３５（ｂ）は、従来の情報埋め込み／情報読み取りの説明図である。
【発明を実施するための最良の形態】  以下、図面を参照しながら、本発明の実施の形態を説明する。
（実施の形態１）
以下、図面を参照しながら、本発明の実施の形態１を説明する。図１は、本発明の実施の形態１における情報埋め込み装置の機能ブロック図である。
図１に示すように、この情報埋め込み装置は、抽出部１と、情報埋め込み部２とを備える。情報埋め込み部２は、定数情報入力部３と挿入個数決定部４と剰余計算部５と挿入実行部６とを備える。情報埋め込み部２は、抽出部１により抽出された頂点の情報を利用し、ベクトルデータの座標系が編集されても埋め込み情報が保持される態様でベクトルデータに埋め込み情報を埋め込む。
抽出部１は、多角形の情報を含むベクトルデータを入力し、このベクトルデータから多角形を構成する複数の頂点の情報を抽出する。
定数情報入力部３は、定数Ｎ（２以上の整数）を入力する。
剰余計算部５は、抽出された頂点の個数を、定数情報入力部３により決定された定数Ｎで割った剰余の値を計算する。また、挿入個数決定部４は、剰余計算部５により計算された剰余の値と、埋め込み情報の値とが、一定の対応関係（本形態では、両者が等しい）を持つように、多角形への挿入点の個数を決定する。
挿入実行部６は、挿入個数決定部４により決定された個数の挿入点を、抽出された多角形の辺上に挿入し、それにより、埋め込み情報の埋め込みを実行する。
図２は、本発明の実施の形態１における情報埋め込み装置のフローチャートである。
図２に示すように、ステップ１０にて、抽出部１１が入力されたベクトルデータから多角形を抽出し、さらに、ステップ１１にて、抽出した多角形の頂点を抽出する。
ステップ１２にて、定数情報入力部３が定数Ｎを入力する。
ステップ１３にて、剰余算出部５が、抽出された頂点の個数を定数Ｎで割った剰余の値を計算する。ステップ１４にて、挿入個数決定部４が、剰余の値を埋め込み情報の値とする。
挿入実行部６は、ステップ１５にて、挿入点を挿入する辺を決め、ステップ１６にて、挿入すべき個数分の点を、抽出された多角形の辺上に挿入し、それにより、埋め込み情報の埋め込みが実行される。
なお、ステップ１２で入力された定数Ｎは、情報読み取りの際に、鍵情報として使用される。
本形態では、抽出された多角形が四角形であり、四角形の辺上への点の挿入により情報を埋め込む。
図３（ａ）は、抽出された多角形の例（四角形、各頂点Ｐ１（ｘ１、ｙ１）、Ｐ２（ｘ２，ｙ２）、Ｐ３（ｘ３，ｙ３）、Ｐ４（ｘ４，ｙ４））を示す。図３（ａ）の例では、抽出された多角形の頂点の個数は「４」である。
さて、定数Ｎ＝Ｎ０とし、埋め込み情報Ｍ＝Ｍ０とする。このとき、挿入される点の個数と抽出された多角形の頂点の個数「４」との和を、Ｎ０で割った剰余の値が、Ｍ０に等しくなるように、挿入する点の個数が決められる。即ち、Ｍ０個の点を挿入することで、埋め込み情報Ｍ０を埋め込む。
本形態では、剰余の値と埋め込み情報Ｍ０とが等しいという、一定の対応関係を用いる。しかしながら、一定の対応関係としては、この例に限られるものではなく、一方から他方が一意に定められるものであれば、任意に変更できる。例えば、Ｎ０＝４、Ｍ０＝２ならば、３個の点を挿入するとしてもよい。
さて本形態では、次のようにして点を挿入する。
すなわち、図３（ａ）に示す多角形Ｐ１Ｐ２Ｐ３Ｐ４の四辺のうち、三辺Ｐ１Ｐ２，Ｐ２Ｐ３，Ｐ３Ｐ４上へそれぞれ点を挿入する。
このとき、図３（ｂ）に示すように、三辺Ｐ１Ｐ２、Ｐ２Ｐ３、Ｐ３Ｐ４の各辺の中点Ｑ１（ｘ５、ｙ５）、Ｑ２（ｘ６、ｙ６）、Ｑ３（ｘ７、ｙ７）を挿入点とする。なお、挿入点は、中点でなくても差し支えない。
抽出された多角形は、図３（ｃ）に示すような凹多角形や図３（ｄ）に示すように「内部にループを有する」ような多角形でも良い。
図４（ａ）は、抽出された多角形の例（四角形、各頂点Ｐ１（０，１００）、Ｐ２（０，０）、Ｐ３（１００，０）、Ｐ４（１００，１００））を示す。
図４（ｂ）は、図４（ａ）の示すような四角形に対し、埋め込み情報の値と剰余の値との対応関係を示す。
ここで、抽出された多角形の頂点の個数をＺとし、定数をＮとし、挿入点の個数をＱとし、ＺとＱの和をＷとする。また、埋め込み情報の値をＭとする。
このような値Ｚ、Ｎ、Ｍ、Ｑ、剰余の値の対応関係があるとき、値Ｍを変化させると、値Ｑが変化する。
図４（ｂ）は、Ｚ＝４、Ｎ＝４の場合に、Ｍ＝０，１，２，３の各値を埋め込む例を示す。剰余の値が、それぞれ、０、１、２、３となるように挿入すべき個数Ｑを決定すると、それぞれ、Ｑ＝０、１、２、３となる。
図５は、抽出された多角形が四角形であり、定数Ｎが４であるとき、図４（ｂ）の対応関係を用いて、四角形の辺上に点を挿入する例を示す。
図５（ａ），（ｂ），（ｃ），（ｄ），（ｅ）において、点Ｐｉ（ｉ＝１，２，３，４）は、抽出された四頂点であり、点Ｑｉ（ｉ＝１，２、３）は、挿入点である。
図５（ａ）は、抽出された多角形が四角形（頂点：Ｐ１，Ｐ２，Ｐ３，Ｐ４）であり、埋め込み前の多角形を示す。
図５（ｂ）は、定数Ｎが４であるとき、情報「０」を埋め込む例を示す。この例は、図４（ｂ）において情報「０」を埋め込む場合に該当する。このとき、Ｗの値「４」を、Ｎの値「４」で割った剰余は、「０」であり、埋め込み情報Ｍの値は「０」である。
図５（ｃ）は、定数Ｎが４であるとき、情報「１」を埋め込む例を示す。この例は、図４（ｂ）において情報「１」を埋め込む場合に該当する。このとき、Ｗの値「５」をＮの値「４」で割った剰余の値は、「１」であり、埋め込み情報Ｍの値は「１」である。このため、図５（ｃ）に示すように、辺Ｐ１Ｐ２の中点を挿入点Ｑ１とする。
図５（ｄ）は、定数Ｎが４であるとき、情報「２」を埋め込む例を示す。この例は、図４（ｂ）において情報「２」を埋め込む場合に該当する。このとき、Ｗの値「６」を、Ｎの値「４」で割った剰余の値は、「２」であり、埋め込み情報Ｍの値は「２」である。このため、図５（ｄ）に示すように、辺Ｐ１Ｐ２の中点Ｑ１と、辺Ｐ２Ｐ３の中点Ｑ２とが、挿入点として選ばれる。
図５（ｅ）は、定数Ｎが４であるとき、情報「３」を埋め込む例を示す。この例は、図４（ｂ）において、情報「３」を埋め込む場合に該当する。このとき、Ｗの値「７」を、Ｎの値「４」で割った剰余の値は、「３」であり、埋め込み情報Ｍの値は「３」である。このため、図５（ｅ）に示すように、辺Ｐ１Ｐ２上の中点Ｑ１と、辺Ｐ２Ｐ３上の中点Ｑ２と、辺Ｐ３Ｐ４上の中点Ｑ３とが、挿入点として選ばれる。
次に、抽出された多角形が五角形である場合について説明する。なお、六角形以上の多角形についても本発明は同様に適用できる。
図６（ａ）の五角形は、Ｐ１（０，１００）、Ｐ２（０，０）、Ｐ３（１００，０）、Ｐ４（１２０，５０）、Ｐ５（１００，１００）という５つの頂点を持つ。
図６（ｂ）は、図６（ａ）の示すような五角形に対し、埋め込み情報の値を変化させた時の挿入する点の個数の変化を示す。
図６（ｂ）の各値Ｍ、Ｚ、Ｑ、Ｗ及び剰余は、図４（ａ）と同様である。
図６（ｂ）は、Ｚ＝５、Ｎ＝４の場合に、Ｍ＝０，１，２，３の各値を埋め込む例を示す。剰余の値が、それぞれ、０、２、１、３となるように、挿入点の個数Ｑを決定すると、それぞれ、Ｑ＝３，１，０，２となる。
図７は、抽出された多角形が五角形であり、定数Ｎが４であるとき、図６（ｂ）の対応関係を用いて、五角形の辺上に挿入点を挿入する例を示す。
図７（ａ），（ｂ），（ｃ），（ｄ），（ｅ）において、点Ｐｉ（ｉ＝１，２，３，４，５）は、抽出された五頂点であり、点Ｑｉ（ｉ＝１，２，３）は、挿入点である。
図７（ａ）は、抽出された多角形が五角形（頂点：Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５）であり、埋め込み前の状態を示す。
図７（ｂ）は、定数Ｎが４であるとき、情報「０」を埋め込む例を示す。この例は、図６（ｂ）において情報「０」を埋め込む場合に該当する。このとき、Ｗの値「８」をＮの値「４」で割った剰余の値は「０」であり、埋め込み情報Ｍの値は「０」、挿入点の個数Ｑは「３」である。
したがって、図７（ｂ）に示すように、辺Ｐ１Ｐ５の中点Ｑ１と、辺Ｐ４Ｐ５の中点Ｑ２と、辺Ｐ３Ｐ４の中点Ｑ３とが、挿入点に選ばれる。
図７（ｃ）は、定数Ｎが４であるとき、情報「１」を埋め込む例を示す。この例は、図６（ｂ）において情報「１」を埋め込む場合に該当する。このとき、Ｗの値「６」を、Ｎの値「４」で割った剰余の値は、「２」であり、埋め込み情報Ｍの値は「１」、挿入点の個数Ｑは「１」である。したがって、図７（ｃ）に示すように、辺Ｐ１Ｐ５の中点Ｑ１が挿入点として選ばれる。
図７（ｄ）は、定数Ｎが４であるとき、情報「２」を埋め込む例を示す。この例は、図６（ｂ）において情報「２」を埋め込む場合に該当する。このとき、Ｗの値「５」を、Ｎの値「４」で割った剰余の値は、「１」であり、埋め込み情報Ｍの値は「２」、挿入点の個数Ｑは「０」である。したがって、この場合には、挿入点が無い。
図７（ｅ）は、定数Ｎが４であるとき、情報「３」を埋め込む例を示す。この例は、図６（ｂ）において情報「３」を埋め込む場合に該当する。
このとき、Ｗの値「７」を、Ｎの値「４」で割った剰余の値は、「３」であり、埋め込み情報Ｍの値は「３」、挿入点の個数Ｑは「２」である。したがって、図７（ｅ）に示すように、辺Ｐ１Ｐ５の中点Ｑ１と、辺Ｐ２Ｐ３の中点Ｑ２とが挿入点として選ばれる。
本形態は、次のように変更できる。
（変更点１）剰余と埋め込み情報との対応関係は、変更してよい。
（変更点２）多角形の辺上に埋め込む対象が無い場合は、辺から離れた位置に挿入点を挿入してもよい。
本形態によれば、次の効果がある
（効果１）従来例のように、基準パラメータ、変化パラメータを設定する必要がない。
（効果２）多角形の辺上に点を挿入すれば、挿入前の多角形の形状変化を抑えることができる。
（効果３）悪意の第三者が、多角形を構成する頂点のうち１つ又は複数の頂点を移動し、ベクトルデータを改ざんし埋め込み情報を消そうと試みても、そのような操作を無効にできる。なぜなら、多角形の頂点をいくら移動しても、頂点の個数を変更することはできず、埋め込み情報の保持及びその後の読み取りに支障がないからである。
（実施の形態２）
図８は、本発明の実施の形態２における情報読み取り装置の機能ブロック図である。
図８に示すように、この情報読み取り装置は、抽出部１０と、情報読み取り部１１とを備える。情報読み取り部１１は、個数算出部１２と定数情報入力部１３と剰余計算部１４と読み取り部１５とを備える。
抽出部１０は、情報が埋め込まれたベクトルデータから多角形を抽出し、さらに抽出した多角形の頂点を抽出する。
個数算出部１２は、多角形の頂点数を算出する。
定数情報入力部１３は、２以上の整数である定数Ｎを入力する。
剰余計算部１４は、個数算出部１２により算出された個数を、定数情報入力部１３により入力された定数Ｎで割った剰余を計算する。
読み取り部１５は、この剰余から埋め込み情報を読み取る。
図９は、本発明の実施の形態２における情報埋め込み装置のフローチャートである。
ステップ２０にて、抽出部１０は、ベクトルデータから、多角形を抽出する。
ステップ２１にて、個数算出部１２は、抽出された多角形の項点数を算出する。
ステップ２２にて、定数情報入力部１３は、定数Ｎを入力する。
ステップ２３にて、剰余計算部１４は、頂点数を定数Ｎで割った剰余を計算する。
ステップ２４にて、読み取り部１５は、この剰余に基づいて埋め込み情報を読み取る。
ここで、抽出された多角形の辺上に存在する点の個数をＷとし、埋め込み情報の値をＭとする。実施の形態１に対応し、実施の形態２では、四角形について図１０（ａ）、図１０（ｂ）に示す表を用意する。図１０（ａ）は、Ｎの値が「４」のとき、個数Ｗを定数Ｎで割った剰余の値と、埋め込み情報Ｍの値との対応関係を示す。また、図１０（ａ）に示すような対応関係を、埋め込み装置側と読み取り装置側の双方で、電子透かし鍵情報として、取り決めておく。
たとえば、抽出された多角形の頂点の個数Ｗが「５」であるとき、Ｎの値「４」による剰余Ｒの値は「１」となり、読み取り部１５は、図１０（ｂ）の関係を用いて、埋め込み情報Ｍの値は「１」であると読み取る。
また、図１０（ｂ）により、挿入前の多角形の頂点数は「４」であり、挿入点の個数Ｑは「１」であることがわかる。なお、五角形についても、基本的に上述と同様な処理を行える。
本形態によれば、次の効果がある。
（効果１）図１０（ａ）、図１０（ｂ）に示す対応関係を用いて、埋め込み情報を読み取ることができる。
（効果２）図１０（ｂ）に示すように、多角形の頂点数を含めた対応関係を用いているので、埋め込み情報の値だけでなく、挿入点の個数も明らかになる。
なお、実施の形態１、２あるいは後述する全ての形態における情報埋め込み装置、及び読み取り装置の各構成要素をプログラムとして構築し、コンピュータにインストールする、または、ネットワークを介して流通させることも可能である。
図１１に示すように、このプログラムは、典型的には、ＣＤ−ＲＯＭやフレキシブルディスク等の記憶媒体３１に格納され、ドライブ３０、Ｉ／Ｏ２９を介してハードディスク等の記憶装置２８にインストールされる。
そして、ＣＰＵ２５が、ＲＯＭ２６、ＲＡＭ２７、ハードディスク２８等をアクセスしながら、このプログラムを実行すれば、上記各形態における情報埋め込み装置、及び読み取り装置が実現されることになる。
（実施の形態３）
図１２は、本発明の実施の形態３における情報埋め込み装置の機能ブロック図である。この情報埋め込み装置は、抽出部４１と情報埋め込み部４２とを備える。情報埋め込み部４２は、対応関係決定部４３と埋め込み部４４とを備える。
実施の形態１と同様に、抽出部４１は、ベクトルデータを入力し、このベクトルデータに含まれる多角形の頂点を抽出する。
対応関係決定部４３は、複数の幾何学要素について、埋め込み情報の値と複数の幾何学要素との対応関係を決定する。複数の幾何学要素は、多角形の対角線と、多角形の重心と、多角形の頂点と多角形の代表点とからなる群から選択されたものである。本形態では、多角形の対角線と多角形の重心とが選択される。
幾何学要素の対応関係は、「多角形の対角線と、多角形の重心との距離」、「多角形の対角線と、多角形の代表点との距離」及び「多角形の重心と多角形の代表点との距離」のいずれかにより表現できる。
本形態では、「多角形の対角線と、多角形の重心との距離」によりこの対応関係を表現する。
また、埋め込み情報が２値であるとき、上記複数の距離から選択された距離について閾値Ｔを定めておき、上記選択された距離がＴ以下であるとき情報「０」を埋め込むものとし、上記選択された距離がＴを超えるとき情報「１」を埋め込むものとする。以上が、本形態の対応関係である。
埋め込み部４４は、対応関係決定部４３により決定された対応関係に基づいて、多角形の代表点を変化させることにより埋め込み処理を行う。代表点は、頂点であっても良いし、多角形の幾何学的性質を表さない点（例えば、多角形に単に付加された点等）でもよい。本形態における代表点は、多角形の重心である。
図１３は、本発明の実施の形態３における情報埋め込み装置のフローチャートである。抽出部４１は、ステップ３０で、入力されたベクトルデータから、多角形を抽出し、ステップ３１で、多角形の頂点を抽出する。
対応関係決定部４３は、ステップ３２で、多角形の幾何学要素として、多角形の重心と最長の対角線とを求め、ステップ３３で、抽出された対角線の重心の座標と最長の対角線とを求める。
対応関係決定部４３は、ステップ３４で、埋め込み情報を入力し、ステップ３５で、埋め込み情報と、幾何学要素の対応関係を決定する。対応関係決定部４３は、ステップ３６で、埋め込み情報「０」であるとき、対角線の重心と最長の対角線との間の距離が閾値Ｔ以下（本形態では、この距離はゼロ）になるように、多角形の頂点のうち特定の頂点の座標を定める。また、対応関係決定部４３は、ステップ３６で、埋め込み情報「１」であるとき、対角線の重心と最長の対角線との間の距離が閾値Ｔを超えるように、多角形の頂点のうち特定の頂点の座標を定める。
なおここで、最長の対角線を選定することの利点は、同一の長さの対角線が複数存在する場合を除き、対角線を一意に特定できることである。
図１４（ａ）〜図１４（ｃ）は、本発明の実施の形態３における情報埋め込み過程を示す。
図１４（ａ）は、情報が埋め込まれる前の多角形を例示する。この例では、多角形は、４つの頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００）を持つ四角形である。
多角形が四角形であるとき、本形態における複数の幾何学要素は、四角形の最長の対角線と四角形の重心である。図１４（ａ）の四角形Ｐ１Ｐ２Ｐ３Ｐ４において、最長の対角線は、Ｐ１Ｐ３（＝Ｐ２Ｐ４）である。また、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）である。
幾何学要素の配置情報として、重心Ｇと最長の対角線Ｐ１Ｐ３との距離を求める。重心Ｇと最長の対角線Ｐ１Ｐ３との距離は、重心Ｇから最長の対角線Ｐ１Ｐ３へ下ろした垂線の足Ｈまでの長さである。
ここで、この距離は、次式を用いて求められる。
2005020563.tif 000003
この距離の取りうる値の範囲は、一般には、「０」以上の任意の実数である。ここで、埋め込み情報を、「０」または「１」とし、閾値Ｔ（本形態ではＴ＝１）を導入する。
そして、埋め込み情報「０」のときこの距離を閾値Ｔ以下とし、埋め込み情報「１」のときこの距離が閾値Ｔを超えるようにする。
より具体的には、埋め込み情報が「０」ならば、重心Ｇと最長の対角線Ｐ１Ｐ３との距離が「０」以上閾値Ｔ「１」以下になるように、また、埋め込み情報が「１」ならば、重心Ｇと最長の対角線Ｐ１Ｐ３との距離が閾値Ｔ「１」より大になるように、重心Ｇと最長の対角線Ｐ１Ｐ３の距離に関係する頂点（図１４（ｃ）の例では、頂点Ｐ２）を操作する。
図１４（ｂ）は、情報「０」が埋め込まれた例を示す。この例では、重心Ｇが最長の対角線Ｐ１Ｐ３上にあるので、重心Ｇと最長の対角線Ｐ１Ｐ３との距離は「０」である。
図１４（ｃ）は、情報「１」が埋め込まれた例を示す。埋め込み後の四角形Ｐ１Ｐ３Ｐ４Ｐ５（頂点Ｐ１（０、１００）、Ｐ２（２０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））の重心Ｇの座標は、（５５、５０）となり、最長の対角線はＰ１Ｐ３となる。よって、重心Ｇと最長の対角線Ｐ１Ｐ３との距離は「３．５」（＞Ｔ）となる。
本形態は、次のように変更できる。
（１）最長の対角線の位置を保ちながら重心が変化するように頂点を操作したが、逆に、重心の位置を保ちながら対角線の位置が変化する（ただし、最長性を保ちながら）ように頂点を操作してもよい。
（２）埋め込み情報（「０」、「１」）は、入れ替えてもよい。
（３）閾値Ｔの値を「１」としたが、それ以外の「０」以上の任意の値に置き換えることができる。
（４）図１４の例では、多角形の全ての頂点座標を用いて重心Ｇを求めた。しかしながら、多角形の外接矩形の重心や内接矩形の重心を用いても良い。例えば、多角形が図１５（ａ）に示された五角形Ｐ１Ｐ２Ｐ３Ｐ４Ｐ５であるとき、その外接矩形Ｐ１Ｐ３Ｐ４Ｐ５の重心Ｇ１を求めても良い。あるいは、その内接矩形Ｑ１Ｑ２Ｐ４Ｐ５の重心Ｇ２を求めても良い。
重心Ｇ１を用いるときには、多角形を構成する一部の頂点Ｐ２を用いずに重心を求めることになる。あるいは、重心Ｇ２を用いるときには、多角形の頂点には本来含まれない仮想の頂点Ｑ１、Ｑ２を用いて重心を求めることになる。
また、多角形が図１５（ｂ）に示された八角形Ｐ５Ｐ６Ｐ７Ｐ８Ｐ９Ｐ１０Ｐ１１Ｐ１２であるとき、その外接矩形Ｑ３Ｑ４Ｐ１１Ｐ１２の重心Ｇ３を求めても良い。あるいは、その内接矩形Ｐ５Ｐ１０Ｐ１１Ｐ１２の重心Ｇ４を求めても良い。
重心Ｇ３を用いるときには、多角形を構成する一部の頂点Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０を用いず、しかも本来多角形の頂点ではない仮想の頂点Ｑ３、Ｑ４を用いて重心を求めることになる。あるいは、重心Ｇ４を用いるときには、多角形を構成する一部の頂点Ｐ６、Ｐ７、Ｐ８、Ｐ９を用いずに、重心を求めることになる。
いずれにしても、使用する重心の求め方が一意に定めうるものであれば、重心の求め方は任意に設定できる。この点は、後述する各形態においても同様にあてはまる。
（実施の形態４）
図１６は、本発明の実施の形態４における情報読み取り装置の機能ブロック図である。この情報埋め込み装置は、抽出部５１と情報読み取り部５２とを備える。情報読み取り部５２は、対応関係検討５３と読み取り部５４とを備える
抽出部５１は、多角形の情報を含むベクトルデータ（実施の形態３による情報が埋め込まれたもの）を入力し、このベクトルデータから多角形を構成する頂点の情報を抽出する。
次に、対応関係検討部５３は、実施の形態３の対応関係決定部４３が使用する対応関係と同じ対応関係を検討する。この対応関係における幾何学要素は、多角形の重心と最長の対角線である。勿論、閾値Ｔについても、実施の形態３と同じ閾値Ｔが使用される。即ち、対応関係検討部５３は、多角形の重心と最長の対角線との距離を求め、この距離を読み取り部５４へ出力する。
読み取り部５４は、対応関係検討部５３が求めた距離と閾値Ｔとを比較し、比較結果に基づいて、埋め込まれた情報を読み取る。より具体的には、この距離が閾値Ｔ以下ならば、情報「０」を読み取り、この距離が閾値Ｔより大ならば、情報「１」を読み取る。
図１７は、本発明の実施の形態４における情報読み取り装置のフローチャートである。抽出部５１は、ステップ４０で、入力されたベクトルデータから多角形を抽出し、ステップ４１で、多角形の頂点を抽出する。
対応関係検討部５３は、ステップ４２で、幾何学要素として、多角形の重心と最長の対角線とを選択し、ステップ４３で、多角形の重心と最長の対角線とを求める。対応関係検討部５３は、ステップ４４で、上記対応関係を検討し、上記距離を算出して読み取り部５４へ出力する。
読み取り部５４は、ステップ４５で、上記大小比較を行い、その結果、埋め込み情報（「０」または「１」）が読み取られる。
抽出された多角形が、図１８（ａ）に示すように、四角形Ｐ１Ｐ２Ｐ３Ｐ４（頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））であるとき、最長の対角線は、Ｐ１Ｐ３（＝Ｐ２Ｐ４）である。また、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）である。また、その重心Ｇ（５０，５０）と最長の対角線Ｐ１Ｐ３との距離は、「０」である。したがって、埋め込まれている情報の値は、「０」と判定される。
あるいは、抽出された多角形が、図１８（ｂ）に示すように、四角形Ｐ１Ｐ２Ｐ３Ｐ４（頂点Ｐ１（０、１００）、Ｐ２（２０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））であるとき、最長の対角線は、Ｐ１Ｐ３である。また、その重心Ｇ（５５，５０）と最長の対角線Ｐ１Ｐ３との距離は「３．５」（＞Ｔ）である。したがって、埋め込み情報の値は、「１」と判定される。
なお、実施の形態１、２において、埋め込み情報の値の範囲を変化させれば、２値（「０」と「１」）以外の多値にも拡張できる。たとえば、幾何学要素を対角線と重心とし、Ｎ個（Ｎは２以上の整数）の埋め込み情報が「０」、「１」、…、「Ｎ−１」であるとする。また、幾何学要素の配置情報を、二つの幾何学要素の距離、すなわち、対角線と重心の距離に関する情報とし、距離をｄ（ｄは０以上の実数）で表すとする。このとき、「「０」の情報が埋め込まれている」は「ｄが０以上１／Ｎ未満であるような対角線と重心の配置状態」、「「１」の情報が埋め込まれている」は「ｄが１／Ｎ以上２／Ｎ未満であるような対角線と重心の配置状態」、・・・、「「Ｎ」の情報が埋め込まれている」は「ｄが（Ｎ−１）／Ｎ以上であるような対角線と重心の配置状態」というようにそれぞれ対応関係を定めればよい。
実施の形態２によれば、次の効果がある。
（効果１）埋め込み情報の値の範囲を変化させることで、２値（「０」と「１」）以外の多値にも拡張できる。
（効果２）幾何学要素の配置状態を用いて読み取るため、回転操作への耐性が高い。
本形態は、次のように変更できる。
（１）埋め込み情報（「０」、「１」）は、入れ替えてよい。
（２）閾値Ｔの値を「１」としたが、それ以外の「０」以上の任意の値に置き換えることができる。
（実施の形態５）
図１９は、本発明の実施の形態５における情報埋め込み装置の機能ブロック図である。この情報埋め込み装置は、抽出部６１と情報埋め込み部６２とを備える。情報埋め込み部６２は、対応関係決定部６３と埋め込み部６４を備える。
実施の形態１と同様に、抽出部６１は、ベクトルデータを入力し、このベクトルデータに含まれる多角形の頂点を抽出する。
対応関係決定部６３は、幾何学要素を、多角形の対角線と、多角形の重心と、多角形の代表点とからなる群から選択し、選択した幾何学要素の配置情報との対応関係を決定する。本形態では、代表点を多角形の幾何学的性質には直接関係しない施設位置とする。ここで、施設とは、例えば、家屋、学校、病院等の建物等であり、施設位置とは、多角形によりその外形が表示される施設の名称あるいはその略称が、多角形に関連して表示される位置をいう。
また、本形態の幾何学要素は、多角形の重心であり、対応関係は、多角形の重心Ｇと施設位置の距離により表現される。この距離について、実施の形態１と同様に閾値Ｔ（本形態ではＴ＝１）を定め、情報「０」を埋め込む場合には、この距離が閾値Ｔ以下になるようにし、情報「１」を埋め込む場合には、この距離が閾値Ｔを超えるようにする。なお、対応関係決定部６３は、この距離を操作するについて、重心Ｇや頂点等を操作するのではなく、施設位置を操作する。
図２０は、本発明の実施の形態５における情報読み取り装置のフローチャートである。抽出部７１は、ステップ５０で、入力されたベクトルデータから、多角形を抽出し、ステップ５１で、多角形の頂点を抽出する。
対応関係決定部６３は、ステップ５２で、幾何学要素として、多角形の重心を選択し、多角形の代表点として、施設位置を選択する。対応関係決定部６３は、ステップ５３で、多角形の重心と施設位置との距離を算出する。
対応関係決定部６３は、ステップ５４で、埋め込み情報を入力し、ステップ５５で、入力された埋め込み情報の値にしたがって、抽出された多角形の施設位置を決定する。対応関係決定部６３は、情報「０」を埋め込む場合には、この距離が閾値Ｔ以下になるようにし、情報「１」を埋め込む場合には、この距離が閾値Ｔを超えるようにする。埋め込み部６４は、ステップ５５にて、決定された施設位置に、多角形の施設位置を移動する。これにより、情報が埋め込まれる。
図２１（ａ）は、情報が埋め込まれる前の多角形（四角形Ｐ１Ｐ２Ｐ３Ｐ４：頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））を例示する。この多角形は、代表点として施設位置（座標：（３０、２０））を有する。
図２１（ａ）の四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）である。
図２１（ｂ）は、図２１（ａ）の四角形に情報「０」が埋め込まれた例を示す。施設位置の座標は（５０、５０）であり、重心Ｇと施設位置との距離は、「０」である。
図２１（ｃ）は、図２１（ａ）の四角形に情報「１」が埋め込まれた例を示す。施設位置の座標は（３０、２０）であり、重心Ｇと施設位置との距離は「３６．１」（＞Ｔ）である。
本形態によれば、従来例のように、基準を必要としない。
本形態は、次のように変更できる。
（１）二つの幾何学要素のうち一つを重心としたが、対角線としても同様の操作で情報を埋め込むことができる。
（２）埋め込み情報（「０」、「１」）は、入れ替えてよい。
（３）施設位置の座標を変更したが、逆に、重心の位置を変更してもよい。ただし、重心を変化させる場合は、四角形の頂点の座標を変化させるので形状変化が生じる。よって、施設位置を変化させるほうが望ましい。
（４）閾値Ｔの値を「１」としたが、それ以外の「０」以上の任意の値に置き換えることができる。
（実施の形態６）
図２２は、本発明の実施の形態４における情報読み取り装置の機能ブロック図である。本形態の情報読み取り装置は、実施の形態５における情報埋め込み装置によって、情報が埋め込まれたベクトルデータを処理する。この情報読み取り装置は、抽出部７１と情報読み取り部７２とを備える。情報読み取り部７２は、対応関係検討部７３と読み取り部７４とを備える
抽出部７１は、多角形の情報を含むベクトルデータ（実施の形態５による情報が埋め込まれたもの）を入力し、このベクトルデータから多角形を構成する頂点の情報を抽出する。
対応関係検討部７３は、実施の形態５と同じ対応関係を検討する。より具体的には、対応関係検討部７３は、多角形の重心と施設位置との距離を算出し、読み取り部７４へ出力する。勿論、閾値Ｔは、実施の形態５と同じものを用いる。
読み取り部７４は、埋め込み情報を読み取る。より具体的には、読み取り部７４は、上記距離が閾値Ｔ以下の場合、情報「０」を読み取り、上記距離が閾値Ｔを超える場合、情報「１」を読み取る。
図２３は、本発明の実施の形態６における情報読み取り装置のフローチャートである。
抽出部７１は、ステップ６０で、入力されたベクトルデータから、多角形が抽出し、ステップ６１で、多角形の頂点を抽出する。
対応関係検討部７３は、ステップ６２で、幾何学要素として、多角形の重心を選択し、多角形の代表点として施設位置を選択する。対応関係検討部７３は、ステップ６３で、多角形の重心と施設位置との距離を算出し、ステップ６４で、対応関係を検討する。読み取り部７４は、ステップ６５で、距離が閾値Ｔ以下の場合、情報「０」を読み取り、距離が閾値Ｔを超える場合、情報「１」を読み取る。
抽出された多角形が、図２４（ａ）に示すように、四角形Ｐ１Ｐ２Ｐ３Ｐ４（頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））であり、その施設位置の座標が（５０、５０）であるとき、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）である。また、重心Ｇと施設位置との距離は、「０」（＜Ｔ）である。したがって、情報「０」が埋め込まれていると判定される。
また、抽出された多角形が、図２４（ｂ）に示すように、四角形Ｐ１Ｐ２Ｐ３Ｐ４（頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））であり、その施設位置の座標が（３０、２０）であるとき、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）であり、重心Ｇと施設位置との距離は「３６．１」（＞Ｔ）である。したがって、情報「０」が埋め込まれていると判定される。
なお、本形態によれば、実施の形態２と同様に、埋め込み情報の値の範囲を変化させることで、２値（「０」または「１」）以外の多値にも拡張できる。
本形態は、次のように変更できる。
（１）埋め込み情報（「０」、「１」）は、入れ替えてよい。
（２）埋め込み情報の値の範囲を決める値を「１」としたが、それ以外で「０」以上の任意の値に置き換えることができる。
（３）距離のとりうる値の範囲を変化させること、すなわち、幾何学要素の配置情報を変化させることができる。
（実施の形態７）
図２５は、本発明の実施の形態７における情報埋め込み装置の機能ブロック図である。この情報埋め込み装置は、抽出部８１と情報埋め込み部８２とを備える。情報埋め込み部８２は、挿入部８３と埋め込み部８４とを備える。
抽出部８１は、多角形の定義情報を含むベクトルデータを入力し、多角形を構成する複数の頂点を抽出する。
挿入部８３は、抽出部８１により抽出された複数の頂点のうち、隣り合う２つの頂点間に挿入すべき挿入点（その個数Ｎ；但し、本形態ではＮ＝１）を決定する。例えば、多角形が四角形であるときには、多角形の頂点数は「４」であるから、挿入点の数は「４」になる。
埋め込み部８４は、挿入部８３により決定された全ての挿入点を、抽出された多角形に埋め込む。
次に、図２７を参照しながら、挿入点と埋め込み情報との関係を説明する。なお以下、埋め込み情報の値は１ビット（「０」または「１」）であるとする。
埋め込み前の多角形が、図２７（ａ）に示す四角形Ｐ１Ｐ２Ｐ３Ｐ４であるとする。このとき、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇ１は、２つの対角線Ｐ１Ｐ３、Ｐ２Ｐ４の交点に他ならない。
図２７（ｂ）に示すように、挿入点Ｑ１、Ｑ２、Ｑ３、Ｑ４を、それぞれ線分Ｐ１Ｐ２、Ｐ２Ｐ３、Ｐ３Ｐ４、Ｐ４Ｐ１の中点であるとすると、挿入点Ｑ１、Ｑ２、Ｑ３、Ｑ４により構成される四角形Ｑ１Ｑ２Ｑ３Ｑ４の重心Ｇ２は、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇ１に一致する。
本形態では、重心Ｇ１、Ｇ２が一致する場合を、埋め込み情報の値が「０」である場合に対応させる。なお誤差等による許容範囲を確保するため、小さな閾値Ｔ（例えば、Ｔ＝１）を導入し、重心Ｇ１Ｇ２間の距離が閾値Ｔ以下であるとき、２つの重心Ｇ１、Ｇ２は一致するものとみなす。
一方、図２７（ｃ）では、４つの挿入点Ｑ１、Ｑ２、Ｑ３、Ｑ４により構成される四角形Ｑ１Ｑ２Ｑ３Ｑ４の重心Ｇ２が、重心Ｇ１から離れ、重心Ｇ１Ｇ２間の距離は閾値Ｔを超える。本形態では、２つの重心Ｇ１、Ｇ２が一致しない場合（より厳密には、重心Ｇ１Ｇ２間の距離が閾値Ｔを超える場合）を、埋め込み情報の値が「１」である場合に対応させる。
図２６において、挿入部８３は、上述した関係（埋め込み情報の値と２つの重心間の距離との関係）を満足するように、複数の挿入点を決定する。
図２６は、本発明の実施の形態７における情報埋め込み装置のフローチャートである。ステップ７０にて、抽出部８１は、ベクトルデータから多角形を構成する複数の頂点を抽出し、挿入部８３へ抽出された複数の頂点の情報を出力する。
ステップ７１にて、挿入部８３は、埋め込み情報の値をチェックし、この値が「０」ならばステップ７２へ処理を進め、この値が「１」ならばステップ７３へ処理を進める。
ステップ７２では、挿入部８３は、例えば、図２７（ｂ）に示すように、挿入点により構成される多角形の重心が、抽出された多角形の重心に一致するように、全ての挿入点を決定する。
ステップ７３では、挿入部８３は、例えば、図２７（ｃ）に示すように、挿入点により構成される多角形の重心が、抽出された多角形の重心から閾値Ｔより大きな距離だけ離れるように、全ての挿入点を決定する。
ステップ７４では、埋め込み部８４が、挿入部８３により決定された挿入点を、抽出された多角形に埋め込み、その結果を情報埋め込み済ベクトルデータとして出力する。
本形態では、点の挿入に際し、点Ｐ１と点Ｐ２、点Ｐ２と点Ｐ３、点Ｐ３と点Ｐ４、点Ｐ４と点Ｐ１の各々を結ぶ直線上に挿入点を配置しているので、情報埋め込みのデータからオリジナルデータの形状変化を抑えることができる。
本形態は、次のように変更できる。
（１）抽出した各頂点の間に一つずつ新たな点を挿入したが、これに限定されるものではない。挿入点の個数Ｎを「１」より大にすれば、埋め込み情報が多値の場合にも対応できる。
（２）埋め込みに関する対応関係として、情報「０」を埋め込む場合、重心Ｇ１と重心Ｇ２の距離が閾値Ｔ以下、情報「１」を埋め込む場合、重心Ｇ１と重心Ｇ２の距離が閾値Ｔより大きくなるように操作したが、「０」と「１」を入れ替えた逆の場合でも同様の効果が得られる。また、閾値Ｔ＝１としたが、これに限定されるものではない。
（４）埋め込み処理について、情報「０」を埋め込む場合、点Ｐ１と点Ｐ２、点Ｐ２と点Ｐ３、点Ｐ３と点Ｐ４、点Ｐ４と点Ｐ１の中点に挿入点Ｑｉを、情報「１」を埋め込む場合、中点からずらすように挿入点Ｑｉを挿入したが、これに限定されるものではない。
（実施の形態８）
図２８は、本発明の実施の形態８における情報読み取り装置の機能ブロック図である。この情報読み取り装置は、抽出部９１と情報読み取り部９２とを備える。情報読み取り部９２は、分類部９３と重心間距離算出部９４と読み取り部９５とを備える。
抽出部９１は、情報埋め込み済ベクトルデータ（実施の形態７による情報が埋め込まれたもの）を入力し、このベクトルデータから多角形の複数の点を抽出する。
情報読み取り部９２は、抽出部９１により抽出された複数の点に基づいて埋め込まれた情報を読み取る。
分類部９３は、抽出部９１により抽出された複数の点を、第１の集合と第２の集合とに分類し、第１の集合に属する複数の点から構成される第１の図形の重心と、第２の集合に属する複数の点から構成される第２の図形の重心とを求める。より詳しくは、分類部９３は、抽出部により抽出された複数の点に連続番号を付し、連続番号の偶奇により抽出部により抽出された複数の点を分類する。以上は、実施の形態７と同じく挿入点の個数Ｎ＝１であるためである。個数Ｎを「１」より大にするときには、抽出部により抽出された複数の点は、第１の集合、第２の集合、．．．、第（Ｎ＋１）の集合に分類されることになる。
重心間距離算出部９４は、第１の図形の重心と第２の図形の重心との距離を算出する。
読み取り部９５は、重心間距離算出部９４により算出された距離に基づいて埋め込まれた情報を読み取る。
図２９は、本形態の情報読み取り装置のフローチャートである。ステップ８０にて、抽出部９１は、情報埋め込み済ベクトルデータから多角形を抽出し、ステップ８１にて、抽出した多角形から複数の頂点を抽出する。なおこの状態では、実施の形態７における頂点と挿入点とは区別されておらず、単なる頂点として取り扱われる。
ステップ８１にて、分類部９３は、複数の頂点に連続番号Ｍ（Ｍ＝１，２，…）を付与する。ステップ８３にて、分類部９３は、連続番号Ｍの偶奇により、これらの頂点を、２つの頂点群に分類する。これらの頂点群の一方は、実施の形態７における頂点を要素とする集合であり、他方は同じく実施の形態７における挿入点を要素とする集合である。
ステップ８４にて、分類部９３は、一方の集合に属する頂点群から構成される多角形を第１の多角形とし、他方の集合に属する頂点群から構成される多角形を第２の多角形とする。そして、分類部９３は、第１，第２の多角形の情報を、重心間距離算出部９４へ出力する。
ステップ８５にて、重心間距離算出部９３は、第１の多角形の重心と第２の多角形の重心とを求め、これらの重心間の距離を算出し（ステップ８５）、その距離を読み取り部９５へ出力する。
ステップ８６にて、読み取り部９５は、算出された距離と閾値Ｔとを大小比較し、この距離が閾値Ｔ以下なら（図３０（ａ）参照）、情報「０」が埋め込まれていると判定し、この距離が閾値Ｔを超えるなら（図３０（ｂ）参照）。情報「１」が埋め込まれていると判定する（ステップ８７）。
本形態によれば、次のような効果がある。
（効果１）回転操作に依存しない情報を利用した情報読み取りであるため、回転操作が加えられたベクトルデータからでも埋め込み情報の読み取りができる。
本形態は、次のように変更できる。
（１）剰余（偶奇）による分類で、二つの集合に分類したが、これに限定されるものではない。
（２）閾値Ｔ＝１としたが、これに限定されるものではない。
本発明によれば、多角形の辺上に新たな点を挿入することで、オリジナルデータの形状変化を抑えた情報埋め込みができる。しかも、回転操作に依存しない多角形を構成する点の個数を操作することで、回転操作が加えられたベクトルデータや、オリジナルデータが入手できない場合であっても、埋め込み情報を正しく読み取れる。
（実施の形態９）
次に、図３１〜図３３を参照しながら、実施の形態９について説明する。実施の形態１から実施の形態８は、情報埋め込み装置又は情報読み取り装置に関する。本形態では、情報埋め込み装置を電子機器に装備し、ベクトルデータの不正複写を抑制する。本形態では、ベクトルデータは、地図データであり、電子機器は、この地図データを使用するカーナビゲーション装置である。しかしながら、本発明の情報埋め込み装置及び情報読み取り装置は、ＧＰＳ機能を搭載した携帯電話、ポリゴンを使用するコンピュータグラフィクス装置等、ベクトルデータを使用する各種の電子機器に応用することができる。
図３１（ａ）は、本発明の実施の形態９における電子機器のシステム構成図、図３１（ｂ）は、同機能ブロック図である。
図３１（ａ）に示すシステムは、不正複写を行う侵害者のものであることを想定している。侵害者は、正当な記録媒体１００を購入し、カーナビゲーション装置２００に正当な記録媒体１００をセットし、カーナビゲーション装置２００に接続されたパーソナルコンピュータ２３０により不正複写を行い不正な記録媒体２５０を得ようとしている。また、侵害者は、パーソナルコンピュータ２３０に接続されたプリンタ２３１を用いて印刷を行い不正な紙媒体２５１を得ようとしている。
カーナビゲーション装置２００のうち、ＧＰＳ用アンテナ２０５は、静止衛星と通信し、現在位置や方位を知るための情報を入力する。表示部２０１は、現在の位置、方位、周囲の道路や建物などを表示する。カーナビゲーション装置２００が搭載される自動車の向きや位置は、種々変化するから、正当な記録媒体１００から読み出された地図データは、頻繁に回転操作を受け、図３１（ａ）に例示するように、表示部２０１上にわかりやすく表示される。ボタン２０２及び十字キー２０３は、図３１（ｂ）に示す操作入力部２１６に相当し、ユーザの操作入力を受け付ける。
カーナビゲーション装置２００は入出力ポート２０４を装備し、入出力ポート２０４を介して外部の機器（例えば、パーソナルコンピュータ２３０等）と通信できるようになっている。このようなポートが設けられていなくても、侵害者は、カーナビゲーション装置２００の一部を破壊して正当な記録媒体１００のデータを強引に複写することもありうるから、ここでは、ポートが設けられている場合を想定する。
図３１（ｂ）に示すように、カーナビゲーション装置２００は、次の要素を備える。
制御部２１０は、図３３のフローチャートに従いカーナビゲーション装置２００の各要素を制御する。機器固有値保持部２１２は、このカーナビゲーション装置２００に固有に付与された固有値を保持する。固有値は、カーナビゲーション装置２００をユニークに区別できれば任意であるが、例えば、製品のロット番号、製造工場名及び製造日時等を示す値を使用すればよい。
情報埋め込み装置２１３、情報読み取り装置２１８は、実施の形態１から７のいずれの構成でも良い。本形態では、図３２（ａ）に示す埋め込み情報を使用する。この埋め込み情報は、多値である。しかしながら、１ビットの埋め込み／読み取りしかできない情報埋め込み装置や情報読み取り装置を用いても、地図データは、きわめて多数の建物、道路等のベクトルを含むから、例えば、１番目のベクトルに最上位ビットを割り当て、２番目のベクトルに最上位に次ぐ上位のビットを割り当て、以下同様に割り当てていけば（つまり、ビットの関係が一意に決定できるようにすれば）、多値の埋め込み情報に対応できる。勿論、割り当てのルールが悪意の第三者に見破られにくいように構成することが望ましい。
カーナビゲーション処理部２１１は、カーナビゲーション処理を行う。なお、本発明は、カーナビゲーション処理そのものに特徴を有するわけではないから、カーナビゲーション処理に関する詳細な説明は省略する。
一時記憶部２１４は、ＲＡＭ等からなり、制御部２１０が処理の都合上必要とするデータを保存する。
ハッシュ値演算部２１９は、制御部２１０から値を入力すると、ハッシュ関数を用いてそのハッシュ値を求め、求めたハッシュ値を制御部２１０へ返す。
インターフェイス２１５は、制御部２１０と外部のデバイスとの通信を仲介する。図３１（ｂ）の例では、インターフェイス２１５には、操作入力部２１６と表示部２０１と入出力ポート２０４とドライブ２１７とが接続されている。ドライブ２１７は、正当な記録媒体１００に記録されているデータを読み出す。本形態では、カーナビゲージョン装置２００は、正当な記録媒体１００のような記録媒体を介して地図データを入力することにしているが、ネットワークを経由して地図データを入力する場合にも、本発明は同様に適用できる。また、正当な記録媒体１００は、例えば、ＤＶＤ−ＲＯＭやＣＤ−ＲＯＭのような読み取り専用の記録媒体でも差し支えない。なぜなら、不正複写が行われた先（海賊版）の記録媒体に後述するような情報を書き込めれば十分だからである。
次に、図３２（ａ）、図３２（ｂ）を参照しながら、埋め込み情報の取り扱いを説明する。
まず、上述したように本形態の埋め込み情報は、図３２（ａ）に示す多値データである。埋め込み情報は、第１ビット領域に著作権者情報（例えば、著作者の氏名又は名称等）の値を格納し、第２ビット領域に電子機器の機器固有値（機器固有値保持部２１２が保持している）を格納する。第１ビット領域及び第２ビット領域の各ビット長は、適宜選択すればよい。各ビット長を長くすれば、信頼性が高くなるが、処理負担が重くなる。各ビット長は、このトレードオフの関係を考慮して定める。より望ましくは、著作権を管理する団体で規格化しておくと良い。
図３２（ｂ）の上段に示すように、正当な記録媒体１００を販売する権原を備えた著作権者（著作権者１）あるいはそのライセンスを得た者は、埋め込み情報の第１ビット領域を、著作権者１を示す著作権者情報の値とし、第２ビット領域を、著作権者１を示す著作権者情報の値のハッシュ値とする。そして、著作権者１は、情報埋め込み装置１０５を用いて、この埋め込み情報を地図データに埋め込んだ埋め込み済地図データを作成し、それを正当な記録媒体１００に記録し、記録済の正当な記録媒体１００を販売する。勿論、上述したようにネットワーク経由で配送しても良い。
図３２（ｂ）の中段に示すように、機器１を使用する侵害者は、カーナビゲーション装置２００及びパーソナルコンピュータ２３０を用いて不正な記録媒体２５０を、第三者に販売する意図を持って作成する。また、侵害者は、カーナビゲーション装置２００、パーソナルコンピュータ２３０及びプリンタ２３１を用いて、不正な紙媒体２５１を第三者に販売する意図を持って作成する。そして、侵害者は、不正な記録媒体２５０や不正な紙媒体２５１を他者に販売し利益を得る。このとき、第２ビット領域には、著作権者情報の値のハッシュ値ではなく、カーナビゲーション装置２００（機器１）の機器固有値が埋め込まれている。
図３２（ｂ）の下段に示すように、検査者（著作権者でもよい）は、海賊版とおぼしき不正な記録媒体２５０や不正な紙媒体２５１を入手し、情報読み取り装置３０１を用いて埋め込み情報を読み出す。なお、前処理部３００は、情報読み取り装置３０１に情報埋め込み済地図データを出力するために必要な前処理を行う。
検査者は、読み出された埋め込み情報の第１ビット領域から不正な記録媒体２５０あるいは不正な紙媒体２５１の著作権者情報として著作権者１を示す値を得て、著作権者の確認を行える。また、第２ビット領域の値が第１ビット領域の値のハッシュ値か否かをチェックする。もしハッシュ値ならば、不正な記録媒体２５０あるいは不正な紙媒体２５１は、正当に販売されたものであると判断できるが、不正な記録媒体２５０あるいは不正な紙媒体２５１には、カーナビゲーション装置２００（機器１）の機器固有値が埋め込まれているから、不正複写物であると判定できる。しかも、その不正複写は、カーナビゲーション装置２００（機器１）を用いて実施されたと確認できる。これにより、カーナビゲーション装置２００（機器１）を使用する侵害者の責任を追及できる。
次に、図３３を参照しながら、カーナビゲーション装置２００の処理の流れを説明する。まず、ステップ９０にて、制御部２１０は、ドライブ２１７に記録媒体１００がロードされ読み取り可能になるまで待つ。
ステップ９１にて、制御部２１０は、記録媒体１００から地図データを読み出し、情報読み取り装置２１８を用いて第１ビット領域及び第２ビット領域の値を読み出す。
ステップ９２にて、制御部２１０は、第２ビット領域の値が、機器固有値保持部２１２が保持する固有値と一致するかチェックする。一致していれば、ステップ９６へ処理が移り、一致していなければ、ステップ９３へ処理が移る。
ステップ９３では、制御部２１０は、ハッシュ値演算部２１９に第１ビット領域の値によるハッシュ値を求めさせ、このハッシュ値と第２ビット領域の値とが一致するかどうかチェックする（ステップ９４）。一致しなければ、ステップ９５にて、制御部２１０は不正複写が行われている旨警告し処理を打ち切る。これにより、不正複写された記録媒体は、事実上使用できないことになる。一致していれば、処理がステップ９６へ移る。
ステップ９６では、制御部２１０は、必要な地図データを読み出し、一時記憶部２１４へ読み出した地図データを格納する。次に、制御部２１０は、ステップ９７にて、この地図データに、第２ビット領域を機器固有値とする埋め込み情報を埋め込み、埋め込み済地図データを一時記憶部２１４へ格納する（ステップ９８）。
そして、制御部２１０は、埋め込み済地図データをカーナビゲーション処理部２１１へ出力しナビゲーション処理させる。カーナビゲーション処理部２１１は、ステップ９９にて、ＧＰＳ用アンテナ２０５から現在の自動車の位置、向き等の情報を得て、埋め込み済地図データに基づくナビゲーション処理を行う。このとき、地図データは頻繁に回転操作をうけることになる。
ステップ１００にて、制御部２１０は、カーナビゲーション処理部２１１から処理結果を入力し、インターフェイス２１５を介し表示部２０１へ表示をさせる。このように、インターフェイス２１５へは埋め込み済地図データが出力されるから、インターフェイス２１５に接続された入出力ポート２０４を介してパーソナルコンピュータ２３０へ地図データを転送しても、転送された地図データは機器固有値が埋め込まれた地図データとなる。したがって、パーソナルコンピュータ２３０を用いて、不正な記録媒体２５０や不正な紙媒体２５１を得ても、侵害者は、自身が不正複写を行った痕跡を、不正な記録媒体２５０や不正な紙媒体２５１に知らずに残す結果となる。
そして、制御部２１０は、ステップ１０１にて、ステップ９６以下の処理を繰り返す。
なお、一般には、紙媒体による不正複写が行われている場合、海賊版とおぼしき紙媒体とオリジナルとにおいて、不正複写されたかどうかが不明になることが多い。それは、印刷された状態では、ほとんどの場合、地図データがオリジナルの状態から回転操作されていることによる。
しかしながら、図３２（ｂ）のようにすると、本発明に係る情報埋め込みが回転操作にロバストであることから、不正な紙媒体２５１に基づいて直ちに不正を摘発することができ、好都合である。
産業上の利用分野
本発明は、例えば地図データ等のベクトルデータを取り扱う情報処理装置等において好適に利用できる。
【図１】
2005020563.tif 000004
【図２】
2005020563.tif 000005
2005020563.tif 000006
2005020563.tif 000007
2005020563.tif 000008
2005020563.tif 000009
2005020563.tif 000010
【図８】
2005020563.tif 000011
【図９】
2005020563.tif 000012
2005020563.tif 000013
【図１１】
2005020563.tif 000014
【図１２】
2005020563.tif 000015
【図１３】
2005020563.tif 000016
2005020563.tif 000017
2005020563.tif 000018
【図１６】
2005020563.tif 000019
【図１７】
2005020563.tif 000020
2005020563.tif 000021
【図１９】
2005020563.tif 000022
【図２０】
2005020563.tif 000023
2005020563.tif 000024
【図２２】
2005020563.tif 000025
【図２３】
2005020563.tif 000026
2005020563.tif 000027
【図２５】
2005020563.tif 000028
【図２６】
2005020563.tif 000029
2005020563.tif 000030
【図２８】
2005020563.tif 000031
【図２９】
2005020563.tif 000032
2005020563.tif 000033
2005020563.tif 000034
2005020563.tif 000035
【図３３】
2005020563.tif 000036
2005020563.tif 000037
2005020563.tif 000038
【手続補正書】
【提出日】平成18年2月10日(2006.2.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
多角形の情報を含むベクトルデータから多角形を構成する頂点の情報を抽出する抽出部と、
前記抽出部により抽出された頂点の情報を利用し、回転操作に対してロバストな態様で、前記ベクトルデータに埋め込み情報を埋め込む情報埋め込み部とを備える情報埋め込み装置。
【請求項２】
前記情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の点の総数を操作する請求の範囲第１項記載の情報埋め込み装置。
【請求項３】
前記情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の特定点間の距離を操作する請求の範囲第１項記載の情報埋め込み装置。
【請求項４】
前記情報埋め込み部は、埋め込み情報に基づいて、多角形の辺上に存在する点の個数を変更する請求の範囲第１項記載の情報埋め込み装置。
【請求項５】
前記情報埋め込み部は、多角形の辺上に点を挿入する請求の範囲第１項記載の情報埋め込み装置。
【請求項６】
前記情報埋め込み部は、多角形の辺から離れた位置に点を挿入する請求の範囲第１項記載の情報埋め込み装置。
【請求項７】
前記情報埋め込み部は、多角形の辺上に存在する点の個数を定数Ｎ（Ｎは２以上の整数）で割った剰余の値と、埋め込み情報の値Ｍ（Ｍは非負整数、Ｍ＜Ｎ）とが一定の対応関係を持つように、多角形の辺上に存在する点の個数を変更する請求の範囲第１項記載の情報埋め込み装置。
【請求項８】
前記一定の対応関係は、前記剰余の値と、前記埋め込み情報の値Ｍとが等しいという関係である請求の範囲第７項記載の情報埋め込み装置。
【請求項９】
前記情報埋め込み部は、定数Ｎ（Ｎは２以上の整数）を入力する定数情報入力部と、
前記抽出部により抽出された頂点の個数を前記定数Ｎで割った剰余を計算する剰余計算部と、
前記剰余計算部が計算した剰余と埋め込み情報とが一定の対応関係を持つように、前記多角形の辺上に挿入する点の個数を決定する挿入個数決定部と、
前記挿入個数決定部により決定された個数の点を多角形に挿入する挿入実行部とを備える請求の範囲第４項記載の情報埋め込み装置。
【請求項１０】
前記定数Ｎは、多角形の頂点数に依存しない定数である請求の範囲第１項記載の情報埋め込み装置。
【請求項１１】
情報埋め込み済ベクトルデータから、多角形上の点を抽出する抽出部と、
前記抽出部により抽出された点の個数と所定の規則とに基づいて、埋め込み情報を読み取る情報読み取り部とを備える情報読み取り装置。
【請求項１２】
前記所定の規則は、前記抽出部により抽出された点の個数を定数Ｎ（Ｎは２以上の整数）で割った剰余の値と、埋め込み情報の値とが、一定の対応関係を持つという規則である請求の範囲第１１項記載の情報読み取り装置。
【請求項１３】
前記一定の対応関係は、前記剰余の値と前記埋め込み情報の値Ｍとが、等しいという関係である請求の範囲第１２項記載の情報読み取り装置。
【請求項１４】
前記情報読み取り部は、
前記抽出部により抽出された点の個数を算出する個数算出部と、
定数Ｎ（Ｎは２以上の整数）を入力する定数情報入力部と、
前記個数算出部により算出された個数を前記定数Ｎで割った剰余を計算する剰余計算部と、
前記剰余計算部により計算された剰余に基づいて埋め込み情報を読み取る情報読み取り部とを備える請求の範囲第１１項記載の情報読み取り装置。
【請求項１５】
前記情報埋め込み部は、埋め込み情報に基づいて、前記多角形に関する複数の幾何学要素の対応関係が変化するように前記多角形について予め設定された代表点を変化させる請求の範囲第１項記載の情報埋め込み装置。
【請求項１６】
前記代表点は、前記多角形の頂点を含む請求の範囲第１５項記載の情報埋め込み装置。
【請求項１７】
前記複数の幾何学要素は、前記多角形の対角線と、前記多角形の重心と、前記多角形の頂点と前記多角形の代表点とからなる群から選択されたものである請求の範囲第１５項記載の情報埋め込み装置。
【請求項１８】
前記対角線は、最長の対角線である請求の範囲第１７項記載の情報埋め込み装置。
【請求項１９】
前記情報埋め込み部は、前記最長の対角線が最長性を保つように前記代表点を変化させる請求の範囲第１８項記載の情報埋め込み装置。
【請求項２０】
前記対応関係は、前記複数の幾何学要素間の距離で表現される請求の範囲第１５項記載の情報埋め込み装置。
【請求項２１】
前記情報埋め込み部は、前記埋め込み情報の値と前記複数の幾何学要素との対応関係を決定する対応関係決定部と、
前記対応関係決定部により決定された対応関係に基づいて、前記代表点を変化させる埋め込み部とを備える請求の範囲第１５項記載の情報埋め込み装置。
【請求項２２】
前記代表点は、前記多角形の重心である請求の範囲第１５項記載の情報埋め込み装置。
【請求項２３】
前記代表点は、施設位置を指示する請求の範囲第１５項記載の情報埋め込み装置。
【請求項２４】
情報埋め込み済ベクトルデータから多角形上の点を抽出する抽出部と、
前記抽出部により抽出された点と、前記多角形に関する複数の幾何学要素の対応関係とに基づいて、前記ベクトルデータに埋め込まれた情報を読み取る情報読み取り部とを備える情報読み取り装置。
【請求項２５】
前記複数の幾何学要素は、前記多角形の対角線と、前記多角形の重心と、前記多角形の頂点と前記多角形の代表点とからなる群から選択されたものである請求の範囲第２４項記載の情報読み取り装置。
【請求項２６】
前記情報読み取り部は、前記抽出部により抽出された点と、前記多角形に関する複数の幾何学要素の対応関係とを検討する対応関係検討部と、
前記対応関係検討部の検討結果に基づいて、前記ベクトルデータに埋め込まれた情報を読み取る読み取り部とを備える請求の範囲第２４項記載の情報読み取り装置。
【請求項２７】
前記情報埋め込み部は、前記抽出部により抽出された頂点のうち、隣り合う２つの頂点間に挿入すべき挿入点を決定する挿入部と、
前記挿入部により決定された挿入点を前記隣り合う２つの頂点間に挿入する埋め込み部とを備え、
前記挿入部は、前記抽出部により抽出された頂点により構成される第１の図形の重心と、前記挿入部により決定された少なくとも３個の挿入点により構成される第２の図形の重心との関係を、埋め込み情報にしたがって変更する請求の範囲第１項記載の情報埋め込み装置。
【請求項２８】
前記第１の図形は、前記抽出部により抽出された多角形であり、前記第２の図形は、前記挿入部が決定した全ての挿入点により構成される請求の範囲第２７項記載の情報埋め込み装置。
【請求項２９】
前記第１の図形の重心と前記第２の図形の重心との関係は、前記第１の図形の重心と前記第２の図形の重心とが、一致するか否かにより評価される請求の範囲第２７項記載の情報埋め込み装置。
【請求項３０】
情報埋め込み済ベクトルデータから多角形の複数の点を抽出する抽出部と、
前記抽出部により抽出された複数の点を、第１の集合と第２の集合に分類し、前記第１の集合に属する複数の点から構成される第１の図形の重心と、前記第２の集合に属する複数の点から構成される第２の図形の重心とを求める分類部と、
前記第１の図形の重心と前記第２の図形の重心との距離を算出する算出部と、
前記算出部により算出された距離に基づいて埋め込まれた情報を読み取る読み取り部とを備える情報読み取り装置。
【請求項３１】
情報埋め込み済ベクトルデータから多角形の複数の点を抽出する抽出部と、
前記抽出部により抽出された複数の点に基づいて埋め込まれた情報を読み取る情報読み取り部とを備え、
前記情報読み取り部は、
前記抽出部により抽出された複数の点を、第１の集合と第２の集合とに分類し、前記第１の集合に属する複数の点から構成される第１の図形の重心と、前記第２の集合に属する複数の点から構成される第２の図形の重心とを求める分類部と、
前記第１の図形の重心と前記第２の図形の重心との距離を算出する算出部と、
前記算出部により算出された距離に基づいて埋め込まれた情報を読み取る読み取り部とを備える情報読み取り装置。
【請求項３２】
前記分類部は、前記抽出部により抽出された複数の点に連続番号を付し、前記連続番号の偶奇により前記抽出部により抽出された複数の点を分類する請求の範囲第３１項記載の情報読み取り装置。
【請求項３３】
多角形の情報を含むベクトルデータから多角形を構成する頂点の情報を抽出する抽出プロセスと、
前記抽出プロセスにおいて抽出された頂点の情報を利用し、前記ベクトルデータの座標系が回転操作されても埋め込み情報が保持される態様で、前記ベクトルデータに埋め込み情報を埋め込む情報埋め込みプロセスとを備えるプログラムをコンピュータ読み取り可能に記録した記録媒体。
【請求項３４】
機器固有値を保持する機器固有値保持部と、
前記機器固有値保持部が保持する機器固有値を埋め込み情報に含め多角形の情報を含むベクトルデータに埋め込み情報を埋め込む情報埋め込み装置とを備え、
前記情報埋め込み装置は、
前記ベクトルデータから多角形を構成する頂点の情報を抽出する抽出部と、
前記抽出部により抽出された頂点の情報を利用し、回転操作に対してロバストな態様で、前記ベクトルデータに埋め込み情報を埋め込む情報埋め込み部とを備える電子機器。
【請求項３５】
前記情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の点の総数を操作する請求の範囲第３４項記載の電子機器。
【請求項３６】
前記情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の特定点間の距離を操作する請求の範囲第３４項記載の電子機器。
【請求項３７】
前記埋め込み情報は、著作権情報を格納する第１ビット領域の値と前記機器固有値を格納する第２ビット領域の値とから構成される請求の範囲第３４項記載の電子機器。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトルデータに埋め込み情報を埋め込む情報埋め込み装置及びその関連技術に関するものである。
【背景技術】
【０００２】
カーナビゲーションシステムやインターネットの普及に伴い、電子地図の需要が高まっている。電子地図のようなデジタルコンテンツに対しては、容易にそのコピーを作成することができる。このため、不正コピーが増加傾向にあり、著作権保護が重要な問題となっている。
【０００３】
文献１（日本国特開２００１−７８０１９号公報）は、次のような情報埋め込み手法を開示する。
【０００４】
図３４を用いて、文献１が開示する情報の埋め込み方法を説明する。図３４の各図において、横軸、縦軸は、それぞれ、ｘ座標軸、ｙ座標軸である。
【０００５】
まず、埋め込み対象点Ａから、基準点Ｓが算出される。より具体的には、基準点Ｓは、埋め込み対象点Ａの座標の下位桁を、埋め込み情報に応じてマスクして求められる。
【０００６】
図３４（ａ）の斜線領域は、埋め込み対象点Ａに対して、基準点Ｓがとりうる範囲を示す。
【０００７】
また、図３４（ａ）の斜線領域は、図３４（ｂ）の領域αと図３４（ｃ）の領域βに分けられる。領域αは、埋め込み情報「１」の場合に使用され、領域βは埋め込み情報「０」の場合に使用される。
【０００８】
即ち、埋め込み情報「１」の場合、埋め込み対象点Ａは、例えば図３４（ｂ）の点Ｂへ移動され、埋め込み情報「０」の場合、埋め込み対象点Ａは、例えば図３４（ｃ）の点Ｂへ移動される。
【０００９】
埋め込み情報（「１」または「０」）を読み出すには、上述と同様に、基準点Ｓが求められ、領域α（図３４（ｂ））と領域β（図３４（ｃ））とが求められる。そして、点Ｂが領域αと領域βのいずれに属するかによって、埋め込み情報が定められる。
【００１０】
また、文献２（日本国特開２００２−３００３７４号公報）は、次の技術を開示する。
【００１１】
まず、図３５（ａ）に示すように、２つの基準点Ａ、Ｂが抽出される。これらの基準点Ａ、Ｂは、いずれも図形の端点である。
【００１２】
次に、基準点Ａ、Ｂのｘ座標に基づいて、基準点ＡＢ間がｎ等分（ここでは、ｎ＝５）され、各区間に１ビットの情報が埋め込まれる。
【００１３】
ここで、情報「０」が埋め込まれる場合、区間内にある点の個数が偶数個にされ、情報「１」を埋め込む場合、区間内にある点の個数が奇数個にされる。
【００１４】
また、埋め込み情報を読み出すには、上述と同様に、各区間を定め、これらの区間内の点の個数が奇数／偶数のいずれであるかにより、埋め込み情報の値が「１」／「０」のいずれであるかを決定すればよい。
【００１５】
文献１、２では、情報の埋め込み時と情報の読み出し時の間で、ｘｙ座標系が変化する場合を予定しておらず、当然、それに対応していない。したがって、情報の埋め込み時と情報の読み出し時の間に、図形が回転操作されると、操作後のベクトルデータのみから、埋め込み情報を正確に読み出すことができなくなる。
【００１６】
この点は、例えば、地図データのように、回転操作が何度も発生する場合において、顕著となり、文献１、２の手法は、このような性質を持つベクトルデータには、事実上適用できない。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
そこで本発明は、ベクトルデータの回転操作に対応できる情報埋め込み装置を提供することを目的とする。
【００１８】
第１の発明に係る情報埋め込み装置は、多角形の情報を含むベクトルデータから多角形を構成する頂点の情報を抽出する抽出部と、抽出部により抽出された頂点の情報を利用し、回転操作に対してロバストな態様で、ベクトルデータに埋め込み情報を埋め込む情報埋め込み部とを備える。
【００１９】
この構成により、ベクトルデータが回転操作を受けても、埋め込み情報が保持され、後に埋め込み情報を読み出す際に支障を生じない。
【００２０】
第２の発明に係る情報埋め込みは、情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の点の総数を操作する。
【００２１】
この構成において、多角形の点の総数は、多角形が回転しても変化しないし、悪意の第三者が埋め込み情報を無効にするため、多角形の点を移動したとしても、後に埋め込み情報を読み出す際に支障を生じない。
【００２２】
第３の発明に係る情報埋め込み装置は、情報埋め込み部は、埋め込み情報に基づいて、情報が埋め込まれた多角形の特定点間の距離を操作する。
【００２３】
この構成において、多角形の特定点間の距離は、多角形が回転しても変化せず、後に埋め込み情報を読み出す際に支障を生じない。
【００２４】
第４の発明に係る情報埋め込みは、情報埋め込み部は、埋め込み情報に基づいて、多角形の辺上に存在する点の個数を変更する。
【００２５】
この構成により、多角形の点の総数が変化する。
【００２６】
第５の発明に係る情報埋め込み装置は、情報埋め込み部は、多角形の辺上に点を挿入する。
【００２７】
この構成により、点が挿入された後も、多角形の形状は変化しない。
【００２８】
第６の発明に係る情報埋め込みは、情報埋め込み部は、多角形の辺から離れた位置に点を挿入する。
【００２９】
この構成により、点の挿入により、多角形の形状をひずませることができる。
【００３０】
第７の発明に係る情報埋め込み装置は、情報埋め込み部は、多角形の辺上に存在する点の個数を定数Ｎ（Ｎは２以上の整数）で割った剰余の値と、埋め込み情報の値Ｍ（Ｍは非負整数、Ｍ＜Ｎ）とが一定の対応関係を持つように、多角形の辺上に存在する点の個数を変更する。
【００３１】
第８の発明に係る情報埋め込み装置は、一定の対応関係は、剰余の値と、埋め込み情報の値Ｍとが等しいという関係である。
【００３２】
第９の発明に係る情報埋め込み装置は、情報埋め込み部は、定数Ｎ（Ｎは２以上の整数）を入力する定数情報入力部と、抽出部により抽出された頂点の個数を定数Ｎで割った剰余を計算する剰余計算部と、剰余計算部が計算した剰余と埋め込み情報とが一定の対応関係を持つように、多角形の辺上に挿入する点の個数を決定する挿入個数決定部と、挿入個数決定部により決定された個数の点を多角形に挿入する挿入実行部とを備える。
【００３３】
これらの構成により、剰余の値と埋め込み情報の値との対応関係から、埋め込み情報を容易に特定できる。
【００３４】
第１０の発明に係る情報埋め込み装置は、定数Ｎは、多角形の頂点数に依存しない定数である。
【００３５】
この構成により、多角形の辺数がどうであっても、一定の規則で埋め込み情報を埋め込める。
【００３６】
第１１の発明に係る情報読み取り装置は、情報埋め込み済ベクトルデータから、多角形上の点を抽出する抽出部と、抽出部により抽出された点の個数と所定の規則とに基づいて、埋め込み情報を読み取る情報読み取り部とを備える。
【００３７】
第１２の発明に係る情報読み取り装置は、所定の規則は、抽出部により抽出された点の個数を定数Ｎ（Ｎは２以上の整数）で割った剰余の値と、埋め込み情報の値とが、一定の対応関係を持つという規則である。
【００３８】
第１３の発明に係る情報読み取り装置は、一定の対応関係は、剰余の値と埋め込み情報の値Ｍとが、等しいという関係である。
【００３９】
これらの構成により、回転操作によって失われない埋め込み情報を、確実に読み取ることができる。
【００４０】
第１４の発明に係る情報読み取り装置は、情報読み取り部は、抽出部により抽出された点の個数を算出する個数算出部と、定数Ｎ（Ｎは２以上の整数）を入力する定数情報入力部と、個数算出部により算出された個数を定数Ｎで割った剰余を計算する剰余計算部と、剰余計算部により計算された剰余に基づいて埋め込み情報を読み取る情報読み取り部とを備える。
【００４１】
この構成により、剰余に基づいて、埋め込み情報を特定できる。
【００４２】
第１５の発明に係る情報埋め込み装置は、情報埋め込み部は、埋め込み情報に基づいて、多角形に関する複数の幾何学要素の対応関係が変化するように多角形について予め設定された代表点を変化させる。
【００４３】
第１６の発明に係る情報埋め込み装置は、代表点は、多角形の頂点を含む。
【００４４】
第１７の発明に係る情報埋め込み装置は、複数の幾何学要素は、多角形の対角線と、多角形の重心と、多角形の頂点と多角形の代表点とからなる群から選択されたものである。
【００４５】
これらの構成により、多角形の幾何学的性質を反映し、多角形に埋め込み情報を埋め込むことができる。
【００４６】
第１８の発明に係る情報埋め込み装置は、対角線は、最長の対角線である。
【００４７】
第１９の発明に係る情報埋め込み装置は、情報埋め込み部は、最長の対角線が最長性を保つように代表点を変化させる。
【００４８】
これらの構成により、対象となる対角線を容易に特定できる。
【００４９】
第２０の発明に係る情報埋め込み装置は、対応関係は、複数の幾何学要素間の距離で表現される。
【００５０】
この構成により、距離により対応関係を表現できる。
【００５１】
第２１の発明に係る情報埋め込み装置は、情報埋め込み部は、埋め込み情報の値と複数の幾何学要素との対応関係を決定する対応関係決定部と、対応関係決定部により決定された対応関係に基づいて、代表点を変化させる埋め込み部とを備える。
【００５２】
第２２の発明に係る情報埋め込み装置は、代表点は、多角形の重心である。
【００５３】
これらの構成により、多角形の幾何学的性質を反映し、多角形に埋め込み情報を埋め込むことができる。
【００５４】
第２３の発明に係る情報埋め込みは、代表点は、施設位置を指示する。
【００５５】
この構成により、多角形の形状を変更せず、多角形に埋め込み情報を埋め込むことができる。
【発明を実施するための最良の形態】
【００５６】
以下、図面を参照しながら、本発明の実施の形態を説明する。
【００５７】
（実施の形態１）
以下、図面を参照しながら、本発明の実施の形態１を説明する。図１は、本発明の実施の形態１における情報埋め込み装置の機能ブロック図である。
【００５８】
図１に示すように、この情報埋め込み装置は、抽出部１と、情報埋め込み部２とを備える。情報埋め込み部２は、定数情報入力部３と挿入個数決定部４と剰余計算部５と挿入実行部６とを備える。情報埋め込み部２は、抽出部１により抽出された頂点の情報を利用し、ベクトルデータの座標系が編集されても埋め込み情報が保持される態様でベクトルデータに埋め込み情報を埋め込む。
【００５９】
抽出部１は、多角形の情報を含むベクトルデータを入力し、このベクトルデータから多角形を構成する複数の頂点の情報を抽出する。
【００６０】
定数情報入力部３は、定数Ｎ（２以上の整数）を入力する。
【００６１】
剰余計算部５は、抽出された頂点の個数を、定数情報入力部３により決定された定数Ｎで割った剰余の値を計算する。また、挿入個数決定部４は、剰余計算部５により計算された剰余の値と、埋め込み情報の値とが、一定の対応関係（本形態では、両者が等しい）を持つように、多角形への挿入点の個数を決定する。
【００６２】
挿入実行部６は、挿入個数決定部４により決定された個数の挿入点を、抽出された多角形の辺上に挿入し、それにより、埋め込み情報の埋め込みを実行する。
【００６３】
図２は、本発明の実施の形態１における情報埋め込み装置のフローチャートである。
【００６４】
図２に示すように、ステップ１０にて、抽出部１１が入力されたベクトルデータから多角形を抽出し、さらに、ステップ１１にて、抽出した多角形の頂点を抽出する。
【００６５】
ステップ１２にて、定数情報入力部３が定数Ｎを入力する。
【００６６】
ステップ１３にて、剰余算出部５が、抽出された頂点の個数を定数Ｎで割った剰余の値を計算する。ステップ１４にて、挿入個数決定部４が、剰余の値を埋め込み情報の値とする。
【００６７】
挿入実行部６は、ステップ１５にて、挿入点を挿入する辺を決め、ステップ１６にて、挿入すべき個数分の点を、抽出された多角形の辺上に挿入し、それにより、埋め込み情報の埋め込みが実行される。
【００６８】
なお、ステップ１２で入力された定数Ｎは、情報読み取りの際に、鍵情報として使用される。
【００６９】
本形態では、抽出された多角形が四角形であり、四角形の辺上への点の挿入により情報を埋め込む。
【００７０】
図３（ａ）は、抽出された多角形の例（四角形、各頂点Ｐ１（ｘ１、ｙ１）、Ｐ２（ｘ２，ｙ２）、Ｐ３（ｘ３，ｙ３）、Ｐ４（ｘ４，ｙ４））を示す。図３（ａ）の例では、抽出された多角形の頂点の個数は「４」である。
【００７１】
さて、定数Ｎ＝Ｎ０とし、埋め込み情報Ｍ＝Ｍ０とする。このとき、挿入される点の個数と抽出された多角形の頂点の個数「４」との和を、Ｎ０で割った剰余の値が、Ｍ０に等しくなるように、挿入する点の個数が決められる。即ち、Ｍ０個の点を挿入することで、埋め込み情報Ｍ０を埋め込む。
【００７２】
本形態では、剰余の値と埋め込み情報Ｍ０とが等しいという、一定の対応関係を用いる。しかしながら、一定の対応関係としては、この例に限られるものではなく、一方から他方が一意に定められるものであれば、任意に変更できる。例えば、Ｎ０＝４、Ｍ０＝２ならば、３個の点を挿入するとしてもよい。
【００７３】
さて本形態では、次のようにして点を挿入する。
【００７４】
すなわち、図３（ａ）に示す多角形Ｐ１Ｐ２Ｐ３Ｐ４の四辺のうち、三辺Ｐ１Ｐ２，Ｐ２Ｐ３，Ｐ３Ｐ４上へそれぞれ点を挿入する。
【００７５】
このとき、図３（ｂ）に示すように、三辺Ｐ１Ｐ２、Ｐ２Ｐ３、Ｐ３Ｐ４の各辺の中点Ｑ１（ｘ５、ｙ５）、Ｑ２（ｘ６、ｙ６）、Ｑ３（ｘ７、ｙ７）を挿入点とする。なお、挿入点は、中点でなくても差し支えない。
【００７６】
抽出された多角形は、図３（ｃ）に示すような凹多角形や図３（ｄ）に示すように「内部にループを有する」ような多角形でも良い。
【００７７】
図４（ａ）は、抽出された多角形の例（四角形、各頂点Ｐ１（０，１００）、Ｐ２（０，０）、Ｐ３（１００，０）、Ｐ４（１００，１００））を示す。
【００７８】
図４（ｂ）は、図４（ａ）の示すような四角形に対し、埋め込み情報の値と剰余の値との対応関係を示す。
【００７９】
ここで、抽出された多角形の頂点の個数をＺとし、定数をＮとし、挿入点の個数をＱとし、ＺとＱの和をＷとする。また、埋め込み情報の値をＭとする。
【００８０】
このような値Ｚ、Ｎ、Ｍ、Ｑ、剰余の値の対応関係があるとき、値Ｍを変化させると、値Ｑが変化する。
【００８１】
図４（ｂ）は、Ｚ＝４、Ｎ＝４の場合に、Ｍ＝０，１，２，３の各値を埋め込む例を示す。剰余の値が、それぞれ、０、１、２、３となるように挿入すべき個数Ｑを決定すると、それぞれ、Ｑ＝０、１、２、３となる。
【００８２】
図５は、抽出された多角形が四角形であり、定数Ｎが４であるとき、図４（ｂ）の対応関係を用いて、四角形の辺上に点を挿入する例を示す。
【００８３】
図５（ａ），（ｂ），（ｃ），（ｄ），（ｅ）において、点Ｐｉ（ｉ＝１，２，３，４）は、抽出された四頂点であり、点Ｑｉ（ｉ＝１，２、３）は、挿入点である。
【００８４】
図５（ａ）は、抽出された多角形が四角形（頂点：Ｐ１，Ｐ２，Ｐ３，Ｐ４）であり、埋め込み前の多角形を示す。
【００８５】
図５（ｂ）は、定数Ｎが４であるとき、情報「０」を埋め込む例を示す。この例は、図４（ｂ）において情報「０」を埋め込む場合に該当する。このとき、Ｗの値「４」を、Ｎの値「４」で割った剰余は、「０」であり、埋め込み情報Ｍの値は「０」である。
【００８６】
図５（ｃ）は、定数Ｎが４であるとき、情報「１」を埋め込む例を示す。この例は、図４（ｂ）において情報「１」を埋め込む場合に該当する。このとき、Ｗの値「５」をＮの値「４」で割った剰余の値は、「１」であり、埋め込み情報Ｍの値は「１」である。このため、図５（ｃ）に示すように、辺Ｐ１Ｐ２の中点を挿入点Ｑ１とする。
【００８７】
図５（ｄ）は、定数Ｎが４であるとき、情報「２」を埋め込む例を示す。この例は、図４（ｂ）において情報「２」を埋め込む場合に該当する。このとき、Ｗの値「６」を、Ｎの値「４」で割った剰余の値は、「２」であり、埋め込み情報Ｍの値は「２」である。このため、図５（ｄ）に示すように、辺Ｐ１Ｐ２の中点Ｑ１と、辺Ｐ２Ｐ３の中点Ｑ２とが、挿入点として選ばれる。
【００８８】
図５（ｅ）は、定数Ｎが４であるとき、情報「３」を埋め込む例を示す。この例は、図４（ｂ）において、情報「３」を埋め込む場合に該当する。このとき、Ｗの値「７」を、Ｎの値「４」で割った剰余の値は、「３」であり、埋め込み情報Ｍの値は「３」である。このため、図５（ｅ）に示すように、辺Ｐ１Ｐ２上の中点Ｑ１と、辺Ｐ２Ｐ３上の中点Ｑ２と、辺Ｐ３Ｐ４上の中点Ｑ３とが、挿入点として選ばれる。
【００８９】
次に、抽出された多角形が五角形である場合について説明する。なお、六角形以上の多角形についても本発明は同様に適用できる。
【００９０】
図６（ａ）の五角形は、Ｐ１（０，１００）、Ｐ２（０，０）、Ｐ３（１００，０）、Ｐ４（１２０，５０）、Ｐ５（１００，１００）という５つの頂点を持つ。
【００９１】
図６（ｂ）は、図６（ａ）の示すような五角形に対し、埋め込み情報の値を変化させた時の挿入する点の個数の変化を示す。
【００９２】
図６（ｂ）の各値Ｍ、Ｚ、Ｑ、Ｗ及び剰余は、図４（ａ）と同様である。
【００９３】
図６（ｂ）は、Ｚ＝５、Ｎ＝４の場合に、Ｍ＝０，１，２，３の各値を埋め込む例を示す。剰余の値が、それぞれ、０、２、１、３となるように、挿入点の個数Ｑを決定すると、それぞれ、Ｑ＝３，１，０，２となる。
【００９４】
図７は、抽出された多角形が五角形であり、定数Ｎが４であるとき、図６（ｂ）の対応関係を用いて、五角形の辺上に挿入点を挿入する例を示す。
【００９５】
図７（ａ），（ｂ），（ｃ），（ｄ），（ｅ）において、点Ｐｉ（ｉ＝１，２，３，４，５）は、抽出された五頂点であり、点Ｑｉ（ｉ＝１，２，３）は、挿入点である。
【００９６】
図７（ａ）は、抽出された多角形が五角形（頂点：Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５）であり、埋め込み前の状態を示す。
【００９７】
図７（ｂ）は、定数Ｎが４であるとき、情報「０」を埋め込む例を示す。この例は、図６（ｂ）において情報「０」を埋め込む場合に該当する。このとき、Ｗの値「８」をＮの値「４」で割った剰余の値は「０」であり、埋め込み情報Ｍの値は「０」、挿入点の個数Ｑは「３」である。
【００９８】
したがって、図７（ｂ）に示すように、辺Ｐ１Ｐ５の中点Ｑ１と、辺Ｐ４Ｐ５の中点Ｑ２と、辺Ｐ３Ｐ４の中点Ｑ３とが、挿入点に選ばれる。
【００９９】
図７（ｃ）は、定数Ｎが４であるとき、情報「１」を埋め込む例を示す。この例は、図６（ｂ）において情報「１」を埋め込む場合に該当する。このとき、Ｗの値「６」を、Ｎの値「４」で割った剰余の値は、「２」であり、埋め込み情報Ｍの値は「１」、挿入点の個数Ｑは「１」である。したがって、図７（ｃ）に示すように、辺Ｐ１Ｐ５の中点Ｑ１が挿入点として選ばれる。
【０１００】
図７（ｄ）は、定数Ｎが４であるとき、情報「２」を埋め込む例を示す。この例は、図６（ｂ）において情報「２」を埋め込む場合に該当する。このとき、Ｗの値「５」を、Ｎの値「４」で割った剰余の値は、「１」であり、埋め込み情報Ｍの値は「２」、挿入点の個数Ｑは「０」である。したがって、この場合には、挿入点が無い。
【０１０１】
図７（ｅ）は、定数Ｎが４であるとき、情報「３」を埋め込む例を示す。この例は、図６（ｂ）において情報「３」を埋め込む場合に該当する。
【０１０２】
このとき、Ｗの値「７」を、Ｎの値「４」で割った剰余の値は、「３」であり、埋め込み情報Ｍの値は「３」、挿入点の個数Ｑは「２」である。したがって、図７（ｅ）に示すように、辺Ｐ１Ｐ５の中点Ｑ１と、辺Ｐ２Ｐ３の中点Ｑ２とが挿入点として選ばれる。
【０１０３】
本形態は、次のように変更できる。
【０１０４】
（変更点１）剰余と埋め込み情報との対応関係は、変更してよい。
【０１０５】
（変更点２）多角形の辺上に埋め込む対象が無い場合は、辺から離れた位置に挿入点を挿入してもよい。
【０１０６】
本形態によれば、次の効果がある
（効果１）従来例のように、基準パラメータ、変化パラメータを設定する必要がない。
【０１０７】
（効果２）多角形の辺上に点を挿入すれば、挿入前の多角形の形状変化を抑えることができる。
【０１０８】
（効果３）悪意の第三者が、多角形を構成する頂点のうち１つ又は複数の頂点を移動し、ベクトルデータを改ざんし埋め込み情報を消そうと試みても、そのような操作を無効にできる。なぜなら、多角形の頂点をいくら移動しても、頂点の個数を変更することはできず、埋め込み情報の保持及びその後の読み取りに支障がないからである。
【０１０９】
（実施の形態２）
図８は、本発明の実施の形態２における情報読み取り装置の機能ブロック図である。
【０１１０】
図８に示すように、この情報読み取り装置は、抽出部１０と、情報読み取り部１１とを備える。情報読み取り部１１は、個数算出部１２と定数情報入力部１３と剰余計算部１４と読み取り部１５とを備える。
【０１１１】
抽出部１０は、情報が埋め込まれたベクトルデータから多角形を抽出し、さらに抽出した多角形の頂点を抽出する。
【０１１２】
個数算出部１２は、多角形の頂点数を算出する。
【０１１３】
定数情報入力部１３は、２以上の整数である定数Ｎを入力する。
【０１１４】
剰余計算部１４は、個数算出部１２により算出された個数を、定数情報入力部１３により入力された定数Ｎで割った剰余を計算する。
【０１１５】
読み取り部１５は、この剰余から埋め込み情報を読み取る。
【０１１６】
図９は、本発明の実施の形態２における情報埋め込み装置のフローチャートである。
【０１１７】
ステップ２０にて、抽出部１０は、ベクトルデータから、多角形を抽出する。
【０１１８】
ステップ２１にて、個数算出部１２は、抽出された多角形の項点数を算出する。
【０１１９】
ステップ２２にて、定数情報入力部１３は、定数Ｎを入力する。
【０１２０】
ステップ２３にて、剰余計算部１４は、頂点数を定数Ｎで割った剰余を計算する。
【０１２１】
ステップ２４にて、読み取り部１５は、この剰余に基づいて埋め込み情報を読み取る。
【０１２２】
ここで、抽出された多角形の辺上に存在する点の個数をＷとし、埋め込み情報の値をＭとする。実施の形態１に対応し、実施の形態２では、四角形について図１０（ａ）、図１０（ｂ）に示す表を用意する。図１０（ａ）は、Ｎの値が「４」のとき、個数Ｗを定数Ｎで割った剰余の値と、埋め込み情報Ｍの値との対応関係を示す。また、図１０（ａ）に示すような対応関係を、埋め込み装置側と読み取り装置側の双方で、電子透かし鍵情報として、取り決めておく。
【０１２３】
たとえば、抽出された多角形の頂点の個数Ｗが「５」であるとき、Ｎの値「４」による剰余Ｒの値は「１」となり、読み取り部１５は、図１０（ｂ）の関係を用いて、埋め込み情報Ｍの値は「１」であると読み取る。
【０１２４】
また、図１０（ｂ）により、挿入前の多角形の頂点数は「４」であり、挿入点の個数Ｑは「１」であることがわかる。なお、五角形についても、基本的に上述と同様な処理を行える。
【０１２５】
本形態によれば、次の効果がある。
【０１２６】
（効果１）図１０（ａ）、図１０（ｂ）に示す対応関係を用いて、埋め込み情報を読み取ることができる。
【０１２７】
（効果２）図１０（ｂ）に示すように、多角形の頂点数を含めた対応関係を用いているので、埋め込み情報の値だけでなく、挿入点の個数も明らかになる。
【０１２８】
なお、実施の形態１、２あるいは後述する全ての形態における情報埋め込み装置、及び読み取り装置の各構成要素をプログラムとして構築し、コンピュータにインストールする、または、ネットワークを介して流通させることも可能である。
【０１２９】
図１１に示すように、このプログラムは、典型的には、ＣＤ−ＲＯＭやフレキシブルディスク等の記憶媒体３１に格納され、ドライブ３０、Ｉ／Ｏ２９を介してハードディスク等の記憶装置２８にインストールされる。
【０１３０】
そして、ＣＰＵ２５が、ＲＯＭ２６、ＲＡＭ２７、ハードディスク２８等をアクセスしながら、このプログラムを実行すれば、上記各形態における情報埋め込み装置、及び読み取り装置が実現されることになる。
【０１３１】
（実施の形態３）
図１２は、本発明の実施の形態３における情報埋め込み装置の機能ブロック図である。この情報埋め込み装置は、抽出部４１と情報埋め込み部４２とを備える。情報埋め込み部４２は、対応関係決定部４３と埋め込み部４４とを備える。
【０１３２】
実施の形態１と同様に、抽出部４１は、ベクトルデータを入力し、このベクトルデータに含まれる多角形の頂点を抽出する。
【０１３３】
対応関係決定部４３は、複数の幾何学要素について、埋め込み情報の値と複数の幾何学要素との対応関係を決定する。複数の幾何学要素は、多角形の対角線と、多角形の重心と、多角形の頂点と多角形の代表点とからなる群から選択されたものである。本形態では、多角形の対角線と多角形の重心とが選択される。
【０１３４】
幾何学要素の対応関係は、「多角形の対角線と、多角形の重心との距離」、「多角形の対角線と、多角形の代表点との距離」及び「多角形の重心と多角形の代表点との距離」のいずれかにより表現できる。
【０１３５】
本形態では、「多角形の対角線と、多角形の重心との距離」によりこの対応関係を表現する。
【０１３６】
また、埋め込み情報が２値であるとき、上記複数の距離から選択された距離について閾値Ｔを定めておき、上記選択された距離がＴ以下であるとき情報「０」を埋め込むものとし、上記選択された距離がＴを超えるとき情報「１」を埋め込むものとする。以上が、本形態の対応関係である。
【０１３７】
埋め込み部４４は、対応関係決定部４３により決定された対応関係に基づいて、多角形の代表点を変化させることにより埋め込み処理を行う。代表点は、頂点であっても良いし、多角形の幾何学的性質を表さない点（例えば、多角形に単に付加された点等）でもよい。本形態における代表点は、多角形の重心である。
【０１３８】
図１３は、本発明の実施の形態３における情報埋め込み装置のフローチャートである。抽出部４１は、ステップ３０で、入力されたベクトルデータから、多角形を抽出し、ステップ３１で、多角形の頂点を抽出する。
【０１３９】
対応関係決定部４３は、ステップ３２で、多角形の幾何学要素として、多角形の重心と最長の対角線とを求め、ステップ３３で、抽出された対角線の重心の座標と最長の対角線とを求める。
【０１４０】
対応関係決定部４３は、ステップ３４で、埋め込み情報を入力し、ステップ３５で、埋め込み情報と、幾何学要素の対応関係を決定する。対応関係決定部４３は、ステップ３６で、埋め込み情報「０」であるとき、対角線の重心と最長の対角線との間の距離が閾値Ｔ以下（本形態では、この距離はゼロ）になるように、多角形の頂点のうち特定の頂点の座標を定める。また、対応関係決定部４３は、ステップ３６で、埋め込み情報「１」であるとき、対角線の重心と最長の対角線との間の距離が閾値Ｔを超えるように、多角形の頂点のうち特定の頂点の座標を定める。
【０１４１】
なおここで、最長の対角線を選定することの利点は、同一の長さの対角線が複数存在する場合を除き、対角線を一意に特定できることである。
【０１４２】
図１４（ａ）〜図１４（ｃ）は、本発明の実施の形態３における情報埋め込み過程を示す。
【０１４３】
図１４（ａ）は、情報が埋め込まれる前の多角形を例示する。この例では、多角形は、４つの頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００）を持つ四角形である。
【０１４４】
多角形が四角形であるとき、本形態における複数の幾何学要素は、四角形の最長の対角線と四角形の重心である。図１４（ａ）の四角形Ｐ１Ｐ２Ｐ３Ｐ４において、最長の対角線は、Ｐ１Ｐ３（＝Ｐ２Ｐ４）である。また、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）である。
【０１４５】
幾何学要素の配置情報として、重心Ｇと最長の対角線Ｐ１Ｐ３との距離を求める。重心Ｇと最長の対角線Ｐ１Ｐ３との距離は、重心Ｇから最長の対角線Ｐ１Ｐ３へ下ろした垂線の足Ｈまでの長さである。
【０１４６】
ここで、この距離は、次式を用いて求められる。
2005020563.tif 000039
【０１４７】
この距離の取りうる値の範囲は、一般には、「０」以上の任意の実数である。ここで、埋め込み情報を、「０」または「１」とし、閾値Ｔ（本形態ではＴ＝１）を導入する。
【０１４８】
そして、埋め込み情報「０」のときこの距離を閾値Ｔ以下とし、埋め込み情報「１」のときこの距離が閾値Ｔを超えるようにする。
【０１４９】
より具体的には、埋め込み情報が「０」ならば、重心Ｇと最長の対角線Ｐ１Ｐ３との距離が「０」以上閾値Ｔ「１」以下になるように、また、埋め込み情報が「１」ならば、重心Ｇと最長の対角線Ｐ１Ｐ３との距離が閾値Ｔ「１」より大になるように、重心Ｇと最長の対角線Ｐ１Ｐ３の距離に関係する頂点（図１４（ｃ）の例では、頂点Ｐ２）を操作する。
【０１５０】
図１４（ｂ）は、情報「０」が埋め込まれた例を示す。この例では、重心Ｇが最長の対角線Ｐ１Ｐ３上にあるので、重心Ｇと最長の対角線Ｐ１Ｐ３との距離は「０」である。
【０１５１】
図１４（ｃ）は、情報「１」が埋め込まれた例を示す。埋め込み後の四角形Ｐ１Ｐ３Ｐ４Ｐ５（頂点Ｐ１（０、１００）、Ｐ２（２０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））の重心Ｇの座標は、（５５、５０）となり、最長の対角線はＰ１Ｐ３となる。よって、重心Ｇと最長の対角線Ｐ１Ｐ３との距離は「３．５」（＞Ｔ）となる。
【０１５２】
本形態は、次のように変更できる。
【０１５３】
（１）最長の対角線の位置を保ちながら重心が変化するように頂点を操作したが、逆に、重心の位置を保ちながら対角線の位置が変化する（ただし、最長性を保ちながら）ように頂点を操作してもよい。
【０１５４】
（２）埋め込み情報（「０」、「１」）は、入れ替えてもよい。
【０１５５】
（３）閾値Ｔの値を「１」としたが、それ以外の「０」以上の任意の値に置き換えることができる。
【０１５６】
（４）図１４の例では、多角形の全ての頂点座標を用いて重心Ｇを求めた。しかしながら、多角形の外接矩形の重心や内接矩形の重心を用いても良い。例えば、多角形が図１５（ａ）に示された五角形Ｐ１Ｐ２Ｐ３Ｐ４Ｐ５であるとき、その外接矩形Ｐ１Ｐ３Ｐ４Ｐ５の重心Ｇ１を求めても良い。あるいは、その内接矩形Ｑ１Ｑ２Ｐ４Ｐ５の重心Ｇ２を求めても良い。
【０１５７】
重心Ｇ１を用いるときには、多角形を構成する一部の頂点Ｐ２を用いずに重心を求めることになる。あるいは、重心Ｇ２を用いるときには、多角形の頂点には本来含まれない仮想の頂点Ｑ１、Ｑ２を用いて重心を求めることになる。
【０１５８】
また、多角形が図１５（ｂ）に示された八角形Ｐ５Ｐ６Ｐ７Ｐ８Ｐ９Ｐ１０Ｐ１１Ｐ１２であるとき、その外接矩形Ｑ３Ｑ４Ｐ１１Ｐ１２の重心Ｇ３を求めても良い。あるいは、その内接矩形Ｐ５Ｐ１０Ｐ１１Ｐ１２の重心Ｇ４を求めても良い。
【０１５９】
重心Ｇ３を用いるときには、多角形を構成する一部の頂点Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ１０を用いず、しかも本来多角形の頂点ではない仮想の頂点Ｑ３、Ｑ４を用いて重心を求めることになる。あるいは、重心Ｇ４を用いるときには、多角形を構成する一部の頂点Ｐ６、Ｐ７、Ｐ８、Ｐ９を用いずに、重心を求めることになる。
【０１６０】
いずれにしても、使用する重心の求め方が一意に定めうるものであれば、重心の求め方は任意に設定できる。この点は、後述する各形態においても同様にあてはまる。
【０１６１】
（実施の形態４）
図１６は、本発明の実施の形態４における情報読み取り装置の機能ブロック図である。この情報埋め込み装置は、抽出部５１と情報読み取り部５２とを備える。情報読み取り部５２は、対応関係検討５３と読み取り部５４とを備える
抽出部５１は、多角形の情報を含むベクトルデータ（実施の形態３による情報が埋め込まれたもの）を入力し、このベクトルデータから多角形を構成する頂点の情報を抽出する。
【０１６２】
次に、対応関係検討部５３は、実施の形態３の対応関係決定部４３が使用する対応関係と同じ対応関係を検討する。この対応関係における幾何学要素は、多角形の重心と最長の対角線である。勿論、閾値Ｔについても、実施の形態３と同じ閾値Ｔが使用される。即ち、対応関係検討部５３は、多角形の重心と最長の対角線との距離を求め、この距離を読み取り部５４へ出力する。
【０１６３】
読み取り部５４は、対応関係検討部５３が求めた距離と閾値Ｔとを比較し、比較結果に基づいて、埋め込まれた情報を読み取る。より具体的には、この距離が閾値Ｔ以下ならば、情報「０」を読み取り、この距離が閾値Ｔより大ならば、情報「１」を読み取る。
【０１６４】
図１７は、本発明の実施の形態４における情報読み取り装置のフローチャートである。抽出部５１は、ステップ４０で、入力されたベクトルデータから多角形を抽出し、ステップ４１で、多角形の頂点を抽出する。
【０１６５】
対応関係検討部５３は、ステップ４２で、幾何学要素として、多角形の重心と最長の対角線とを選択し、ステップ４３で、多角形の重心と最長の対角線とを求める。対応関係検討部５３は、ステップ４４で、上記対応関係を検討し、上記距離を算出して読み取り部５４へ出力する。
【０１６６】
読み取り部５４は、ステップ４５で、上記大小比較を行い、その結果、埋め込み情報（「０」または「１」）が読み取られる。
【０１６７】
抽出された多角形が、図１８（ａ）に示すように、四角形Ｐ１Ｐ２Ｐ３Ｐ４（頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））であるとき、最長の対角線は、Ｐ１Ｐ３（＝Ｐ２Ｐ４）である。また、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）である。また、その重心Ｇ（５０，５０）と最長の対角線Ｐ１Ｐ３との距離は、「０」である。したがって、埋め込まれている情報の値は、「０」と判定される。
【０１６８】
あるいは、抽出された多角形が、図１８（ｂ）に示すように、四角形Ｐ１Ｐ２Ｐ３Ｐ４（頂点Ｐ１（０、１００）、Ｐ２（２０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））であるとき、最長の対角線は、Ｐ１Ｐ３である。また、その重心Ｇ（５５，５０）と最長の対角線Ｐ１Ｐ３との距離は「３．５」（＞Ｔ）である。したがって、埋め込み情報の値は、「１」と判定される。
【０１６９】
なお、実施の形態１、２において、埋め込み情報の値の範囲を変化させれば、２値（「０」と「１」）以外の多値にも拡張できる。たとえば、幾何学要素を対角線と重心とし、Ｎ個（Ｎは２以上の整数）の埋め込み情報が「０」、「１」、・・・、「Ｎ−１」であるとする。また、幾何学要素の配置情報を、二つの幾何学要素の距離、すなわち、対角線と重心の距離に関する情報とし、距離をｄ（ｄは０以上の実数）で表すとする。このとき、「「０」の情報が埋め込まれている」は「ｄが０以上１／Ｎ未満であるような対角線と重心の配置状態」、「「１」の情報が埋め込まれている」は「ｄが１／Ｎ以上２／Ｎ未満であるような対角線と重心の配置状態」、・・・、「「Ｎ」の情報が埋め込まれている」は「ｄが（Ｎ−１）／Ｎ以上であるような対角線と重心の配置状態」というようにそれぞれ対応関係を定めればよい。
【０１７０】
実施の形態２によれば、次の効果がある。
【０１７１】
（効果１）埋め込み情報の値の範囲を変化させることで、２値（「０」と「１」）以外の多値にも拡張できる。
【０１７２】
（効果２）幾何学要素の配置状態を用いて読み取るため、回転操作への耐性が高い。
【０１７３】
本形態は、次のように変更できる。
【０１７４】
（１）埋め込み情報（「０」、「１」）は、入れ替えてよい。
【０１７５】
（２）閾値Ｔの値を「１」としたが、それ以外の「０」以上の任意の値に置き換えることができる。
【０１７６】
（実施の形態５）
図１９は、本発明の実施の形態５における情報埋め込み装置の機能ブロック図である。この情報埋め込み装置は、抽出部６１と情報埋め込み部６２とを備える。情報埋め込み部６２は、対応関係決定部６３と埋め込み部６４を備える。
【０１７７】
実施の形態１と同様に、抽出部６１は、ベクトルデータを入力し、このベクトルデータに含まれる多角形の頂点を抽出する。
【０１７８】
対応関係決定部６３は、幾何学要素を、多角形の対角線と、多角形の重心と、多角形の代表点とからなる群から選択し、選択した幾何学要素の配置情報との対応関係を決定する。本形態では、代表点を多角形の幾何学的性質には直接関係しない施設位置とする。ここで、施設とは、例えば、家屋、学校、病院等の建物等であり、施設位置とは、多角形によりその外形が表示される施設の名称あるいはその略称が、多角形に関連して表示される位置をいう。
【０１７９】
また、本形態の幾何学要素は、多角形の重心であり、対応関係は、多角形の重心Ｇと施設位置の距離により表現される。この距離について、実施の形態１と同様に閾値Ｔ（本形態ではＴ＝１）を定め、情報「０」を埋め込む場合には、この距離が閾値Ｔ以下になるようにし、情報「１」を埋め込む場合には、この距離が閾値Ｔを超えるようにする。なお、対応関係決定部６３は、この距離を操作するについて、重心Ｇや頂点等を操作するのではなく、施設位置を操作する。
【０１８０】
図２０は、本発明の実施の形態５における情報読み取り装置のフローチャートである。抽出部７１は、ステップ５０で、入力されたベクトルデータから、多角形を抽出し、ステップ５１で、多角形の頂点を抽出する。
【０１８１】
対応関係決定部６３は、ステップ５２で、幾何学要素として、多角形の重心を選択し、多角形の代表点として、施設位置を選択する。対応関係決定部６３は、ステップ５３で、多角形の重心と施設位置との距離を算出する。
【０１８２】
対応関係決定部６３は、ステップ５４で、埋め込み情報を入力し、ステップ５５で、入力された埋め込み情報の値にしたがって、抽出された多角形の施設位置を決定する。対応関係決定部６３は、情報「０」を埋め込む場合には、この距離が閾値Ｔ以下になるようにし、情報「１」を埋め込む場合には、この距離が閾値Ｔを超えるようにする。埋め込み部６４は、ステップ５５にて、決定された施設位置に、多角形の施設位置を移動する。これにより、情報が埋め込まれる。
【０１８３】
図２１（ａ）は、情報が埋め込まれる前の多角形（四角形Ｐ１Ｐ２Ｐ３Ｐ４：頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））を例示する。この多角形は、代表点として施設位置（座標：（３０、２０））を有する。
【０１８４】
図２１（ａ）の四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）である。
【０１８５】
図２１（ｂ）は、図２１（ａ）の四角形に情報「０」が埋め込まれた例を示す。施設位置の座標は（５０、５０）であり、重心Ｇと施設位置との距離は、「０」である。
【０１８６】
図２１（ｃ）は、図２１（ａ）の四角形に情報「１」が埋め込まれた例を示す。施設位置の座標は（３０、２０）であり、重心Ｇと施設位置との距離は「３６．１」（＞Ｔ）である。
【０１８７】
本形態によれば、従来例のように、基準を必要としない。
【０１８８】
本形態は、次のように変更できる。
【０１８９】
（１）二つの幾何学要素のうち一つを重心としたが、対角線としても同様の操作で情報を埋め込むことができる。
【０１９０】
（２）埋め込み情報（「０」、「１」）は、入れ替えてよい。
【０１９１】
（３）施設位置の座標を変更したが、逆に、重心の位置を変更してもよい。ただし、重心を変化させる場合は、四角形の頂点の座標を変化させるので形状変化が生じる。よって、施設位置を変化させるほうが望ましい。
【０１９２】
（４）閾値Ｔの値を「１」としたが、それ以外の「０」以上の任意の値に置き換えることができる。
【０１９３】
（実施の形態６）
図２２は、本発明の実施の形態４における情報読み取り装置の機能ブロック図である。本形態の情報読み取り装置は、実施の形態５における情報埋め込み装置によって、情報が埋め込まれたベクトルデータを処理する。この情報読み取り装置は、抽出部７１と情報読み取り部７２とを備える。情報読み取り部７２は、対応関係検討部７３と読み取り部７４とを備える
抽出部７１は、多角形の情報を含むベクトルデータ（実施の形態５による情報が埋め込まれたもの）を入力し、このベクトルデータから多角形を構成する頂点の情報を抽出する。
【０１９４】
対応関係検討部７３は、実施の形態５と同じ対応関係を検討する。より具体的には、対応関係検討部７３は、多角形の重心と施設位置との距離を算出し、読み取り部７４へ出力する。勿論、閾値Ｔは、実施の形態５と同じものを用いる。
【０１９５】
読み取り部７４は、埋め込み情報を読み取る。より具体的には、読み取り部７４は、上記距離が閾値Ｔ以下の場合、情報「０」を読み取り、上記距離が閾値Ｔを超える場合、情報「１」を読み取る。
【０１９６】
図２３は、本発明の実施の形態６における情報読み取り装置のフローチャートである。
【０１９７】
抽出部７１は、ステップ６０で、入力されたベクトルデータから、多角形が抽出し、ステップ６１で、多角形の頂点を抽出する。
【０１９８】
対応関係検討部７３は、ステップ６２で、幾何学要素として、多角形の重心を選択し、多角形の代表点として施設位置を選択する。対応関係検討部７３は、ステップ６３で、多角形の重心と施設位置との距離を算出し、ステップ６４で、対応関係を検討する。読み取り部７４は、ステップ６５で、距離が閾値Ｔ以下の場合、情報「０」を読み取り、距離が閾値Ｔを超える場合、情報「１」を読み取る。
【０１９９】
抽出された多角形が、図２４（ａ）に示すように、四角形Ｐ１Ｐ２Ｐ３Ｐ４（頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））であり、その施設位置の座標が（５０、５０）であるとき、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）である。また、重心Ｇと施設位置との距離は、「０」（＜Ｔ）である。したがって、情報「０」が埋め込まれていると判定される。
【０２００】
また、抽出された多角形が、図２４（ｂ）に示すように、四角形Ｐ１Ｐ２Ｐ３Ｐ４（頂点Ｐ１（０、１００）、Ｐ２（０、０）、Ｐ３（１００、０）、Ｐ４（１００、１００））であり、その施設位置の座標が（３０、２０）であるとき、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇの座標は、（５０、５０）であり、重心Ｇと施設位置との距離は「３６．１」（＞Ｔ）である。したがって、情報「０」が埋め込まれていると判定される。
【０２０１】
なお、本形態によれば、実施の形態２と同様に、埋め込み情報の値の範囲を変化させることで、２値（「０」または「１」）以外の多値にも拡張できる。
【０２０２】
本形態は、次のように変更できる。
【０２０３】
（１）埋め込み情報（「０」、「１」）は、入れ替えてよい。
【０２０４】
（２）埋め込み情報の値の範囲を決める値を「１」としたが、それ以外で「０」以上の任意の値に置き換えることができる。
【０２０５】
（３）距離のとりうる値の範囲を変化させること、すなわち、幾何学要素の配置情報を変化させることができる。
【０２０６】
（実施の形態７）
図２５は、本発明の実施の形態７における情報埋め込み装置の機能ブロック図である。この情報埋め込み装置は、抽出部８１と情報埋め込み部８２とを備える。情報埋め込み部８２は、挿入部８３と埋め込み部８４とを備える。
【０２０７】
抽出部８１は、多角形の定義情報を含むベクトルデータを入力し、多角形を構成する複数の頂点を抽出する。
【０２０８】
挿入部８３は、抽出部８１により抽出された複数の頂点のうち、隣り合う２つの頂点間に挿入すべき挿入点（その個数Ｎ；但し、本形態ではＮ＝１）を決定する。例えば、多角形が四角形であるときには、多角形の頂点数は「４」であるから、挿入点の数は「４」になる。
【０２０９】
埋め込み部８４は、挿入部８３により決定された全ての挿入点を、抽出された多角形に埋め込む。
【０２１０】
次に、図２７を参照しながら、挿入点と埋め込み情報との関係を説明する。なお以下、埋め込み情報の値は１ビット（「０」または「１」）であるとする。
【０２１１】
埋め込み前の多角形が、図２７（ａ）に示す四角形Ｐ１Ｐ２Ｐ３Ｐ４であるとする。このとき、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇ１は、２つの対角線Ｐ１Ｐ３、Ｐ２Ｐ４の交点に他ならない。
【０２１２】
図２７（ｂ）に示すように、挿入点Ｑ１、Ｑ２、Ｑ３、Ｑ４を、それぞれ線分Ｐ１Ｐ２、Ｐ２Ｐ３、Ｐ３Ｐ４、Ｐ４Ｐ１の中点であるとすると、挿入点Ｑ１、Ｑ２、Ｑ３、Ｑ４により構成される四角形Ｑ１Ｑ２Ｑ３Ｑ４の重心Ｇ２は、四角形Ｐ１Ｐ２Ｐ３Ｐ４の重心Ｇ１に一致する。
【０２１３】
本形態では、重心Ｇ１、Ｇ２が一致する場合を、埋め込み情報の値が「０」である場合に対応させる。なお誤差等による許容範囲を確保するため、小さな閾値Ｔ（例えば、Ｔ＝１）を導入し、重心Ｇ１Ｇ２間の距離が閾値Ｔ以下であるとき、２つの重心Ｇ１、Ｇ２は一致するものとみなす。
【０２１４】
一方、図２７（ｃ）では、４つの挿入点Ｑ１、Ｑ２、Ｑ３、Ｑ４により構成される四角形Ｑ１Ｑ２Ｑ３Ｑ４の重心Ｇ２が、重心Ｇ１から離れ、重心Ｇ１Ｇ２間の距離は閾値Ｔを超える。本形態では、２つの重心Ｇ１、Ｇ２が一致しない場合（より厳密には、重心Ｇ１Ｇ２間の距離が閾値Ｔを超える場合）を、埋め込み情報の値が「１」である場合に対応させる。
【０２１５】
図２６において、挿入部８３は、上述した関係（埋め込み情報の値と２つの重心間の距離との関係）を満足するように、複数の挿入点を決定する。
【０２１６】
図２６は、本発明の実施の形態７における情報埋め込み装置のフローチャートである。ステップ７０にて、抽出部８１は、ベクトルデータから多角形を構成する複数の頂点を抽出し、挿入部８３へ抽出された複数の頂点の情報を出力する。
【０２１７】
ステップ７１にて、挿入部８３は、埋め込み情報の値をチェックし、この値が「０」ならばステップ７２へ処理を進め、この値が「１」ならばステップ７３へ処理を進める。
【０２１８】
ステップ７２では、挿入部８３は、例えば、図２７（ｂ）に示すように、挿入点により構成される多角形の重心が、抽出された多角形の重心に一致するように、全ての挿入点を決定する。
【０２１９】
ステップ７３では、挿入部８３は、例えば、図２７（ｃ）に示すように、挿入点により構成される多角形の重心が、抽出された多角形の重心から閾値Ｔより大きな距離だけ離れるように、全ての挿入点を決定する。
【０２２０】
ステップ７４では、埋め込み部８４が、挿入部８３により決定された挿入点を、抽出された多角形に埋め込み、その結果を情報埋め込み済ベクトルデータとして出力する。
【０２２１】
本形態では、点の挿入に際し、点Ｐ１と点Ｐ２、点Ｐ２と点Ｐ３、点Ｐ３と点Ｐ４、点Ｐ４と点Ｐ１の各々を結ぶ直線上に挿入点を配置しているので、情報埋め込みのデータからオリジナルデータの形状変化を抑えることができる。
【０２２２】
本形態は、次のように変更できる。
【０２２３】
（１）抽出した各頂点の間に一つずつ新たな点を挿入したが、これに限定されるものではない。挿入点の個数Ｎを「１」より大にすれば、埋め込み情報が多値の場合にも対応できる。
【０２２４】
（２）埋め込みに関する対応関係として、情報「０」を埋め込む場合、重心Ｇ１と重心Ｇ２の距離が閾値Ｔ以下、情報「１」を埋め込む場合、重心Ｇ１と重心Ｇ２の距離が閾値Ｔより大きくなるように操作したが、「０」と「１」を入れ替えた逆の場合でも同様の効果が得られる。また、閾値Ｔ＝１としたが、これに限定されるものではない。
【０２２５】
（４）埋め込み処理について、情報「０」を埋め込む場合、点Ｐ１と点Ｐ２、点Ｐ２と点Ｐ３、点Ｐ３と点Ｐ４、点Ｐ４と点Ｐ１の中点に挿入点Ｑｉを、情報「１」を埋め込む場合、中点からずらすように挿入点Ｑｉを挿入したが、これに限定されるものではない。
【０２２６】
（実施の形態８）
図２８は、本発明の実施の形態８における情報読み取り装置の機能ブロック図である。この情報読み取り装置は、抽出部９１と情報読み取り部９２とを備える。情報読み取り部９２は、分類部９３と重心間距離算出部９４と読み取り部９５とを備える。
【０２２７】
抽出部９１は、情報埋め込み済ベクトルデータ（実施の形態７による情報が埋め込まれたもの）を入力し、このベクトルデータから多角形の複数の点を抽出する。
【０２２８】
情報読み取り部９２は、抽出部９１により抽出された複数の点に基づいて埋め込まれた情報を読み取る。
【０２２９】
分類部９３は、抽出部９１により抽出された複数の点を、第１の集合と第２の集合とに分類し、第１の集合に属する複数の点から構成される第１の図形の重心と、第２の集合に属する複数の点から構成される第２の図形の重心とを求める。より詳しくは、分類部９３は、抽出部により抽出された複数の点に連続番号を付し、連続番号の偶奇により抽出部により抽出された複数の点を分類する。以上は、実施の形態７と同じく挿入点の個数Ｎ＝１であるためである。個数Ｎを「１」より大にするときには、抽出部により抽出された複数の点は、第１の集合、第２の集合、...、第（Ｎ＋１）の集合に分類されることになる。
【０２３０】
重心間距離算出部９４は、第１の図形の重心と第２の図形の重心との距離を算出する。
【０２３１】
読み取り部９５は、重心間距離算出部９４により算出された距離に基づいて埋め込まれた情報を読み取る。
【０２３２】
図２９は、本形態の情報読み取り装置のフローチャートである。ステップ８０にて、抽出部９１は、情報埋め込み済ベクトルデータから多角形を抽出し、ステップ８１にて、抽出した多角形から複数の頂点を抽出する。なおこの状態では、実施の形態７における頂点と挿入点とは区別されておらず、単なる頂点として取り扱われる。
【０２３３】
ステップ８１にて、分類部９３は、複数の頂点に連続番号Ｍ（Ｍ＝１，２，・・・）を付与する。ステップ８３にて、分類部９３は、連続番号Ｍの偶奇により、これらの頂点を、２つの頂点群に分類する。これらの頂点群の一方は、実施の形態７における頂点を要素とする集合であり、他方は同じく実施の形態７における挿入点を要素とする集合である。
【０２３４】
ステップ８４にて、分類部９３は、一方の集合に属する頂点群から構成される多角形を第１の多角形とし、他方の集合に属する頂点群から構成される多角形を第２の多角形とする。そして、分類部９３は、第１，第２の多角形の情報を、重心間距離算出部９４へ出力する。
【０２３５】
ステップ８５にて、重心間距離算出部９３は、第１の多角形の重心と第２の多角形の重心とを求め、これらの重心間の距離を算出し（ステップ８５）、その距離を読み取り部９５へ出力する。
【０２３６】
ステップ８６にて、読み取り部９５は、算出された距離と閾値Ｔとを大小比較し、この距離が閾値Ｔ以下なら（図３０（ａ）参照）、情報「０」が埋め込まれていると判定し、この距離が閾値Ｔを超えるなら（図３０（ｂ）参照）。情報「１」が埋め込まれていると判定する（ステップ８７）。
【０２３７】
本形態によれば、次のような効果がある。
【０２３８】
（効果１）回転操作に依存しない情報を利用した情報読み取りであるため、回転操作が加えられたベクトルデータからでも埋め込み情報の読み取りができる。
【０２３９】
本形態は、次のように変更できる。
【０２４０】
（１）剰余（偶奇）による分類で、二つの集合に分類したが、これに限定されるものではない。
【０２４１】
（２）閾値Ｔ＝１としたが、これに限定されるものではない。
【０２４２】
本発明によれば、多角形の辺上に新たな点を挿入することで、オリジナルデータの形状変化を抑えた情報埋め込みができる。しかも、回転操作に依存しない多角形を構成する点の個数を操作することで、回転操作が加えられたベクトルデータや、オリジナルデータが入手できない場合であっても、埋め込み情報を正しく読み取れる。
【０２４３】
（実施の形態９）
次に、図３１〜図３３を参照しながら、実施の形態９について説明する。実施の形態１から実施の形態８は、情報埋め込み装置又は情報読み取り装置に関する。本形態では、情報埋め込み装置を電子機器に装備し、ベクトルデータの不正複写を抑制する。本形態では、ベクトルデータは、地図データであり、電子機器は、この地図データを使用するカーナビゲーション装置である。しかしながら、本発明の情報埋め込み装置及び情報読み取り装置は、ＧＰＳ機能を搭載した携帯電話、ポリゴンを使用するコンピュータグラフィクス装置等、ベクトルデータを使用する各種の電子機器に応用することができる。
【０２４４】
図３１（ａ）は、本発明の実施の形態９における電子機器のシステム構成図、図３１（ｂ）は、同機能ブロック図である。
【０２４５】
図３１（ａ）に示すシステムは、不正複写を行う侵害者のものであることを想定している。侵害者は、正当な記録媒体１００を購入し、カーナビゲーション装置２００に正当な記録媒体１００をセットし、カーナビゲーション装置２００に接続されたパーソナルコンピュータ２３０により不正複写を行い不正な記録媒体２５０を得ようとしている。また、侵害者は、パーソナルコンピュータ２３０に接続されたプリンタ２３１を用いて印刷を行い不正な紙媒体２５１を得ようとしている。
【０２４６】
カーナビゲーション装置２００のうち、ＧＰＳ用アンテナ２０５は、静止衛星と通信し、現在位置や方位を知るための情報を入力する。表示部２０１は、現在の位置、方位、周囲の道路や建物などを表示する。カーナビゲーション装置２００が搭載される自動車の向きや位置は、種々変化するから、正当な記録媒体１００から読み出された地図データは、頻繁に回転操作を受け、図３１（ａ）に例示するように、表示部２０１上にわかりやすく表示される。ボタン２０２及び十字キー２０３は、図３１（ｂ）に示す操作入力部２１６に相当し、ユーザの操作入力を受け付ける。
【０２４７】
カーナビゲーション装置２００は入出力ポート２０４を装備し、入出力ポート２０４を介して外部の機器（例えば、パーソナルコンピュータ２３０等）と通信できるようになっている。このようなポートが設けられていなくても、侵害者は、カーナビゲーション装置２００の一部を破壊して正当な記録媒体１００のデータを強引に複写することもありうるから、ここでは、ポートが設けられている場合を想定する。
【０２４８】
図３１（ｂ）に示すように、カーナビゲーション装置２００は、次の要素を備える。
【０２４９】
制御部２１０は、図３３のフローチャートに従いカーナビゲーション装置２００の各要素を制御する。機器固有値保持部２１２は、このカーナビゲーション装置２００に固有に付与された固有値を保持する。固有値は、カーナビゲーション装置２００をユニークに区別できれば任意であるが、例えば、製品のロット番号、製造工場名及び製造日時等を示す値を使用すればよい。
【０２５０】
情報埋め込み装置２１３、情報読み取り装置２１８は、実施の形態１から７のいずれの構成でも良い。本形態では、図３２（ａ）に示す埋め込み情報を使用する。この埋め込み情報は、多値である。しかしながら、１ビットの埋め込み／読み取りしかできない情報埋め込み装置や情報読み取り装置を用いても、地図データは、きわめて多数の建物、道路等のベクトルを含むから、例えば、１番目のベクトルに最上位ビットを割り当て、２番目のベクトルに最上位に次ぐ上位のビットを割り当て、以下同様に割り当てていけば（つまり、ビットの関係が一意に決定できるようにすれば）、多値の埋め込み情報に対応できる。勿論、割り当てのルールが悪意の第三者に見破られにくいように構成することが望ましい。
【０２５１】
カーナビゲーション処理部２１１は、カーナビゲーション処理を行う。なお、本発明は、カーナビゲーション処理そのものに特徴を有するわけではないから、カーナビゲーション処理に関する詳細な説明は省略する。
【０２５２】
一時記憶部２１４は、ＲＡＭ等からなり、制御部２１０が処理の都合上必要とするデータを保存する。
【０２５３】
ハッシュ値演算部２１９は、制御部２１０から値を入力すると、ハッシュ関数を用いてそのハッシュ値を求め、求めたハッシュ値を制御部２１０へ返す。
【０２５４】
インターフェイス２１５は、制御部２１０と外部のデバイスとの通信を仲介する。図３１（ｂ）の例では、インターフェイス２１５には、操作入力部２１６と表示部２０１と入出力ポート２０４とドライブ２１７とが接続されている。ドライブ２１７は、正当な記録媒体１００に記録されているデータを読み出す。本形態では、カーナビゲーション装置２００は、正当な記録媒体１００のような記録媒体を介して地図データを入力することにしているが、ネットワークを経由して地図データを入力する場合にも、本発明は同様に適用できる。また、正当な記録媒体１００は、例えば、ＤＶＤ−ＲＯＭやＣＤ−ＲＯＭのような読み取り専用の記録媒体でも差し支えない。なぜなら、不正複写が行われた先（海賊版）の記録媒体に後述するような情報を書き込めれば十分だからである。
【０２５５】
次に、図３２（ａ）、図３２（ｂ）を参照しながら、埋め込み情報の取り扱いを説明する。
【０２５６】
まず、上述したように本形態の埋め込み情報は、図３２（ａ）に示す多値データである。埋め込み情報は、第１ビット領域に著作権者情報（例えば、著作者の氏名又は名称等）の値を格納し、第２ビット領域に電子機器の機器固有値（機器固有値保持部２１２が保持している）を格納する。第１ビット領域及び第２ビット領域の各ビット長は、適宜選択すればよい。各ビット長を長くすれば、信頼性が高くなるが、処理負担が重くなる。各ビット長は、このトレードオフの関係を考慮して定める。より望ましくは、著作権を管理する団体で規格化しておくと良い。
【０２５７】
図３２（ｂ）の上段に示すように、正当な記録媒体１００を販売する権原を備えた著作権者（著作権者１）あるいはそのライセンスを得た者は、埋め込み情報の第１ビット領域を、著作権者１を示す著作権者情報の値とし、第２ビット領域を、著作権者１を示す著作権者情報の値のハッシュ値とする。そして、著作権者１は、情報埋め込み装置１０５を用いて、この埋め込み情報を地図データに埋め込んだ埋め込み済地図データを作成し、それを正当な記録媒体１００に記録し、記録済の正当な記録媒体１００を販売する。勿論、上述したようにネットワーク経由で配送しても良い。
【０２５８】
図３２（ｂ）の中段に示すように、機器１を使用する侵害者は、カーナビゲーション装置２００及びパーソナルコンピュータ２３０を用いて不正な記録媒体２５０を、第三者に販売する意図を持って作成する。また、侵害者は、カーナビゲーション装置２００、パーソナルコンピュータ２３０及びプリンタ２３１を用いて、不正な紙媒体２５１を第三者に販売する意図を持って作成する。そして、侵害者は、不正な記録媒体２５０や不正な紙媒体２５１を他者に販売し利益を得る。このとき、第２ビット領域には、著作権者情報の値のハッシュ値ではなく、カーナビゲーション装置２００（機器１）の機器固有値が埋め込まれている。
【０２５９】
図３２（ｂ）の下段に示すように、検査者（著作権者でもよい）は、海賊版とおぼしき不正な記録媒体２５０や不正な紙媒体２５１を入手し、情報読み取り装置３０１を用いて埋め込み情報を読み出す。なお、前処理部３００は、情報読み取り装置３０１に情報埋め込み済地図データを出力するために必要な前処理を行う。
【０２６０】
検査者は、読み出された埋め込み情報の第１ビット領域から不正な記録媒体２５０あるいは不正な紙媒体２５１の著作権者情報として著作権者１を示す値を得て、著作権者の確認を行える。また、第２ビット領域の値が第１ビット領域の値のハッシュ値か否かをチェックする。もしハッシュ値ならば、不正な記録媒体２５０あるいは不正な紙媒体２５１は、正当に販売されたものであると判断できるが、不正な記録媒体２５０あるいは不正な紙媒体２５１には、カーナビゲーション装置２００（機器１）の機器固有値が埋め込まれているから、不正複写物であると判定できる。しかも、その不正複写は、カーナビゲーション装置２００（機器１）を用いて実施されたと確認できる。これにより、カーナビゲーション装置２００（機器１）を使用する侵害者の責任を追及できる。
【０２６１】
次に、図３３を参照しながら、カーナビゲーション装置２００の処理の流れを説明する。まず、ステップ９０にて、制御部２１０は、ドライブ２１７に記録媒体１００がロードされ読み取り可能になるまで待つ。
【０２６２】
ステップ９１にて、制御部２１０は、記録媒体１００から地図データを読み出し、情報読み取り装置２１８を用いて第１ビット領域及び第２ビット領域の値を読み出す。
【０２６３】
ステップ９２にて、制御部２１０は、第２ビット領域の値が、機器固有値保持部２１２が保持する固有値と一致するかチェックする。一致していれば、ステップ９６へ処理が移り、一致していなければ、ステップ９３へ処理が移る。
【０２６４】
ステップ９３では、制御部２１０は、ハッシュ値演算部２１９に第１ビット領域の値によるハッシュ値を求めさせ、このハッシュ値と第２ビット領域の値とが一致するかどうかチェックする（ステップ９４）。一致しなければ、ステップ９５にて、制御部２１０は不正複写が行われている旨警告し処理を打ち切る。これにより、不正複写された記録媒体は、事実上使用できないことになる。一致していれば、処理がステップ９６へ移る。
【０２６５】
ステップ９６では、制御部２１０は、必要な地図データを読み出し、一時記憶部２１４へ読み出した地図データを格納する。次に、制御部２１０は、ステップ９７にて、この地図データに、第２ビット領域を機器固有値とする埋め込み情報を埋め込み、埋め込み済地図データを一時記憶部２１４へ格納する（ステップ９８）。
【０２６６】
そして、制御部２１０は、埋め込み済地図データをカーナビゲーション処理部２１１へ出力しナビゲーション処理させる。カーナビゲーション処理部２１１は、ステップ９９にて、ＧＰＳ用アンテナ２０５から現在の自動車の位置、向き等の情報を得て、埋め込み済地図データに基づくナビゲーション処理を行う。このとき、地図データは頻繁に回転操作をうけることになる。
【０２６７】
ステップ１００にて、制御部２１０は、カーナビゲーション処理部２１１から処理結果を入力し、インターフェイス２１５を介し表示部２０１へ表示をさせる。このように、インターフェイス２１５へは埋め込み済地図データが出力されるから、インターフェイス２１５に接続された入出力ポート２０４を介してパーソナルコンピュータ２３０へ地図データを転送しても、転送された地図データは機器固有値が埋め込まれた地図データとなる。したがって、パーソナルコンピュータ２３０を用いて、不正な記録媒体２５０や不正な紙媒体２５１を得ても、侵害者は、自身が不正複写を行った痕跡を、不正な記録媒体２５０や不正な紙媒体２５１に知らずに残す結果となる。
【０２６８】
そして、制御部２１０は、ステップ１０１にて、ステップ９６以下の処理を繰り返す。
【０２６９】
なお、一般には、紙媒体による不正複写が行われている場合、海賊版とおぼしき紙媒体とオリジナルとにおいて、不正複写されたかどうかが不明になることが多い。それは、印刷された状態では、ほとんどの場合、地図データがオリジナルの状態から回転操作されていることによる。
【０２７０】
しかしながら、図３２（ｂ）のようにすると、本発明に係る情報埋め込みが回転操作にロバストであることから、不正な紙媒体２５１に基づいて直ちに不正を摘発することができ、好都合である。
【産業上の利用可能性】
【０２７１】
本発明は、例えば地図データ等のベクトルデータを取り扱う情報処理装置等において好適に利用できる。
【図面の簡単な説明】
【０２７２】
【図１】本発明の実施の形態１における情報埋め込み装置の機能ブロック図である。
【図２】本発明の実施の形態１における情報埋め込み装置のフローチャートである。
【図３】（ａ）から（ｄ）は、本発明の実施の形態１における多角形の例示図である。
【図４】（ａ）は、本発明の実施の形態１における多角形の例示図である。（ｂ）は、本発明の実施の形態１における埋め込み情報の関係図である。
【図５】（ａ）から（ｅ）は、本発明の実施の形態１における情報埋め込み例の説明図である。
【図６】（ａ）は、本発明の実施の形態１における多角形の例示図である。（ｂ）は、本発明の実施の形態１における埋め込み情報の関係図である。
【図７】（ａ）から（ｅ）は、本発明の実施の形態１における情報埋め込み例の説明図である。
【図８】本発明の実施の形態２における情報読み取り装置の機能ブロック図である。
【図９】本発明の実施の形態２における情報読み取り装置のフローチャートである。
【図１０】（ａ）から（ｂ）は、本発明の実施の形態２における埋め込み情報の関係図である。
【図１１】本発明の実施の形態における情報埋め込み／読み取り装置のブロック図である。
【図１２】本発明の実施の形態３における情報埋め込み装置の機能ブロック図である。
【図１３】本発明の実施の形態３における情報埋め込み装置のフローチャートである。
【図１４】（ａ）から（ｃ）は、本発明の実施の形態３における多角形の例示図である。
【図１５】（ａ）から（ｂ）は、本発明の実施の形態３における重心の説明図である。
【図１６】本発明の実施の形態４における情報読み取り装置の機能ブロック図である。
【図１７】本発明の実施の形態４における情報読み取り装置のフローチャートである。
【図１８】（ａ）から（ｂ）は、本発明の実施の形態４における多角形の例示図である。
【図１９】本発明の実施の形態５における情報埋め込み装置の機能ブロック図である。
【図２０】本発明の実施の形態５における情報埋め込み装置のフローチャートである。
【図２１】（ａ）から（ｃ）は、本発明の実施の形態５における多角形の例示図である。
【図２２】本発明の実施の形態６における情報読み取り装置の機能ブロック図である。
【図２３】本発明の実施の形態６における情報読み取り装置のフローチャートである。
【図２４】（ａ）から（ｂ）は、本発明の実施の形態６における多角形の例示図である。
【図２５】本発明の実施の形態７における情報埋め込み装置の機能ブロック図である。
【図２６】本発明の実施の形態７における情報埋め込み装置のフローチャートである。
【図２７】（ａ）から（ｂ）は、本発明の実施の形態７における重心の説明図である。
【図２８】本発明の実施の形態８における情報読み取り装置の機能ブロック図である。
【図２９】本発明の実施の形態８における情報埋め込み装置のフローチャートである。
【図３０】（ａ）から（ｂ）は、本発明の実施の形態８における重心の説明図である。
【図３１】（ａ）は、本発明の実施の形態９における電子機器のシステム構成図、（ｂ）は、本発明の実施の形態９における電子機器の機能ブロック図である。
【図３２】（ａ）は、本発明の実施の形態９における埋め込み情報のデータ構成図である。（ｂ）は、本発明の実施の形態９における不正複写摘発の手順図である。
【図３３】本発明の実施の形態９における電子機器のフローチャートである。
【図３４】（ａ）から（ｃ）は、従来の情報埋め込み／情報読み取りの説明図である。
【図３５】（ａ）から（ｂ）は、従来の情報埋め込み／情報読み取りの説明図である。
【国際調査報告】
2005020563.tif 000040
2005020563.tif 000041
2005020563.tif 000042
2005020563.tif 000043