(57)【特許請求の範囲】
【請求項１】
空間上において１個の点と他の点とが線で結ばれて表現される図形を示す図形情報に他の情報を埋め込む情報埋込装置であって、
空間上における複数の点をそれぞれ示す位置情報を含む図形情報を記憶している図形情報記憶手段と、
埋込対象となる埋込情報を記憶している埋込情報記憶手段と、
前記埋込情報を読み出す読出手段と、
前記複数の点から１個の点を選択する点選択手段と、
読み出した前記埋込情報を、選択された前記点を示す位置情報の下位桁に埋め込む埋込手段とを備え、
前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、
前記図形情報記憶手段は、少なくとも前記３個の点をそれぞれ示す位置情報を含み、
前記点選択手段は、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択する
ことを特徴とする情報埋込装置。
【請求項２】
前記埋込手段は、
選択された前記点を示す位置情報のうちの下位の特定の桁を対象桁として選択する桁選択手段と、
読み出した前記埋込情報に基づいて、選択された前記対象桁が示す値を更新する更新手段とを含み、
前記更新手段は、前記第２の点が、前記第１の点及び前記第３の点を結ぶ線と、略平行して移動するように、前記対象桁が示す値を更新する
ことを特徴とする請求項１に記載の情報埋込装置。
【請求項３】
前記空間は、２次元空間であり、前記空間の座標系は、直交するＸ座標軸とＹ座標軸とから構成され、
前記更新手段は、前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度に応じて、前記対象桁が示す値を更新する
ことを特徴とする請求項２に記載の情報埋込装置。
【請求項４】
各点を示す位置情報は、前記座標系において、当該点を示すＸ座標値とＹ座標値とを含み、
前記桁選択手段は、
前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度αを算出する算出手段と、
算出された前記角度αが
（ａ）−２２．５°≦角度α＜２２．５°又は１５７．５°≦角度α＜２０２．５°の第１の範囲、
（ｂ）２２．５°≦角度α＜６７．５°、１１２．５°≦角度α＜１５７．５°、２０２．５°≦角度α＜２４７．５°又は２９２．５°≦角度α＜３３７．５°の第２の範囲、又は
（ｃ）６７．５°≦角度α＜１１２．５°又は２４７．５°≦角度α＜２９２．５°の第３の範囲のいずれの範囲内に入るかを判断する判断手段と、
第１の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択し、
第２の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値及びＹ座標値をそれぞれ複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択し、
第３の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＹ座標値を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択する副桁選択手段とを含む
ことを特徴とする請求項３に記載の情報埋込装置。
【請求項５】
前記副桁選択手段は、前記複数の桁のうちの最下位桁を対象桁として選択し、
前記更新手段は、前記最下位桁が示す値を更新する
ことを特徴とする請求項４に記載の情報埋込装置。
【請求項６】
前記読出手段は、前記埋込情報を複数桁のｎ（ｎは、正整数、ｎ＞１）進数で表現するときに、前記複数桁のうちの１個の桁が示す値を埋込値として抽出し、
ｎ＝ｍであり、
前記更新手段は、抽出した前記埋込値を選択された前記対象桁が示す値に上書きすることにより、前記対象桁が示す値を更新する
ことを特徴とする請求項５に記載の情報埋込装置。
【請求項７】
前記読出手段は、前記埋込情報を複数桁のｎ（ｎは、正整数、ｎ＞１）進数で表現するときに、前記複数桁のうちの１個の桁が示す値を埋込値として抽出し、
ｎ＜ｍであり、
前記更新手段は、抽出した前記埋込値に、所定の変換アルゴリズムを施して変換値を生成し、生成した変換値を選択された前記対象桁が示す値に上書きし、
前記所定の変換アルゴリズムは、ｎ種の数字をｍ種の数字のいずれかに変換し、逆変換アルゴリズムにより、変換された数字から元の数字が生成される
ことを特徴とする請求項５に記載の情報埋込装置。
【請求項８】
空間上において１個の点と他の点とが線で結ばれて表現される図形を示す図形情報から埋め込まれた埋込情報を抽出する情報抽出装置であって、
請求項１に記載の情報埋込装置により埋込情報が埋め込まれた図形情報を記憶している図形情報記憶手段と、
前記図形情報記憶手段に記憶されている図形情報を読み出す読出手段と、
前記複数の点から１個の点を選択する点選択手段と、
選択された前記点を示す位置情報から、埋込情報を抽出する抽出手段とを備え、
前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、
前記図形情報記憶手段は、少なくとも３個の点をそれぞれ示す位置情報を含み、
前記点選択手段は、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択する
ことを特徴とする情報抽出装置。
【請求項９】
前記抽出手段は、
選択された前記点を示す位置情報を複数桁のｍ（ｍは、正整数、ｍ＞１）進数
で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択する
桁選択手段と、
選択された対象桁が示す値を埋込値として抽出する値抽出手段と、
１桁のｍ進数で表現される埋込値に対応する値であって、１桁のｎ（ｎは、正整数、ｎ＞１）進数で表現される抽出値を、埋込情報の１桁として生成する値生成手段と
を備えることを特徴とする請求項８に記載の情報抽出装置。
【請求項１０】
前記空間は、２次元空間であり、前記空間の座標系は、直交するＸ座標軸とＹ座標軸とから構成され、
前記値抽出手段は、前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度に応じて、前記抽出値を生成する
ことを特徴とする請求項９に記載の情報抽出装置。
【請求項１１】
各点を示す位置情報は、前記座標系において、当該点を示すＸ座標値とＹ座標値とを含み、
前記桁選択手段は、
前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度αを算出する算出手段と、
算出された前記角度αが
（ａ）−２２．５°≦角度α＜２２．５°又は１５７．５°≦角度α＜２０２．５°の第１の範囲、
（ｂ）２２．５°≦角度α＜６７．５°、１１２．５°≦角度α＜１５７．５°、２０２．５°≦角度α＜２４７．５°又は２９２．５°≦角度α＜３３７．５°の第２の範囲、又は
（ｃ）６７．５°≦角度α＜１１２．５°又は２４７．５°≦角度α＜２９２．５°の第３の範囲のいずれの範囲内に入るかを判断する判断手段と、
第１の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択し、
第２の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値及びＹ座標値をそれぞれ複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択し、
第３の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＹ座標値を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択する副桁選択手段とを含む
ことを特徴とする請求項１０に記載の情報抽出装置。
【請求項１２】
前記副桁選択手段は、前記複数の桁のうちの最下位桁を対象桁として選択し、
前記値抽出手段は、前記最下位桁が示す値を埋込値として抽出する
ことを特徴とする請求項１１に記載の情報抽出装置。
【請求項１３】
ｎ＝ｍであり、
前記値生成手段は、前記埋込値を前記抽出値として生成する
ことを特徴とする請求項１２に記載の情報抽出装置。
【請求項１４】
ｎ＜ｍであり、
前記値生成手段は、抽出した前記埋込値に、請求項７に記載の逆変換アルゴリズムを施して埋込値を生成する
ことを特徴とする請求項１２に記載の情報抽出装置。
【請求項１５】
空間上において１個の点と他の点とが線で結ばれて表現される図形を示す図形情報に他の情報を埋め込む情報埋込装置で用いられる情報埋込方法あって、
前記情報埋込装置は、空間上における複数の点をそれぞれ示す位置情報を含む図形情報を記憶している図形情報記憶手段と、埋込対象となる埋込情報を記憶している埋込情報記憶手段とを備え、
前記情報埋込方法は、
前記埋込情報を読み出す読出ステップと、
前記複数の点から１個の点を選択する点選択ステップと、
読み出した前記埋込情報を、選択された前記点を示す位置情報の下位桁に埋め込む埋込ステップ手段とを含み、
前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、
前記図形情報記憶手段は、少なくとも前記３個の点をそれぞれ示す位置情報を含み、
前記点選択ステップは、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択する
ことを特徴とする情報埋込方法。
【請求項１６】
空間上において１個の点と他の点とが線で結ばれて表現され
る図形を示す図形情報に他の情報を埋め込むコンピュータで用いられる情報埋込プログラムを記録しているコンピュータ読み取り可能な記録媒体であって、
前記コンピュータは、空間上における複数の点をそれぞれ示す位置情報を含む図形情報を記憶している図形情報記憶手段と、埋込対象となる埋込情報を記憶している埋込情報記憶手段とを備え、
前記情報埋込プログラムは、
前記埋込情報を読み出す読出ステップと、
前記複数の点から１個の点を選択する点選択ステップと、
読み出した前記埋込情報を、選択された前記点を示す位置情報の下位桁に埋め込む埋込ステップ手段とを含み、
前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、
前記図形情報記憶手段は、少なくとも前記３個の点をそれぞれ示す位置情報を含み、
前記点選択ステップは、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択する
ことを特徴とする記録媒体。
【請求項１７】
空間上において１個の点と他の点とが線で結ばれて表現され
る図形を示す図形情報に他の情報を埋め込むコンピュータで用いられる情報埋込プログラムであって、
前記コンピュータは、空間上における複数の点をそれぞれ示す位置情報を含む図形情報を記憶している図形情報記憶手段と、埋込対象となる埋込情報を記憶している埋込情報記憶手段とを備え、
前記情報埋込プログラムは、
前記埋込情報を読み出す読出ステップと、
前記複数の点から１個の点を選択する点選択ステップと、
読み出した前記埋込情報を、選択された前記点を示す位置情報の下位桁に埋め込む埋込ステップ手段とを含み、
前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、
前記図形情報記憶手段は、少なくとも前記３個の点をそれぞれ示す位置情報を含み、
前記点選択ステップは、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択する
ことを特徴とする情報埋込プログラム。
【請求項１８】
空間上において１個の点と他の点とが線で結ばれて表現される図形を示す図形情報から埋め込まれた埋込情報を抽出する情報抽出装置で用いられる情報抽出方法であって、
前記情報抽出装置は、請求項１に記載の情報埋込装置により埋込情報が埋め込まれた図形情報を記憶している図形情報記憶手段を備え、
前記情報抽出方法は、
前記図形情報記憶手段に記憶されている図形情報を読み出す読出ステップと、
前記複数の点から１個の点を選択する点選択ステップと、
選択された前記点を示す位置情報から、埋込情報を抽出する抽出ステップとを含み、
前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、
前記図形情報記憶手段は、少なくとも３個の点をそれぞれ示す位置情報を含み、
前記点選択ステップは、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択する
ことを特徴とする情報抽出方法。
【請求項１９】
空間上において１個の点と他の点とが線で結ばれて表現される図形を示す図形情報から埋め込まれた埋込情報を抽出するコンピュータで用いられる情報抽出プログラムを記録しているコンピュータ読み取り可能な記録媒体であって、
前記コンピュータは、請求項１に記載の情報埋込装置により埋込情報が埋め込まれた図形情報を記憶している図形情報記憶手段を備え、
前記情報抽出プログラムは、
前記図形情報記憶手段に記憶されている図形情報を読み出す読出ステップと、
前記複数の点から１個の点を選択する点選択ステップと、
選択された前記点を示す位置情報から、埋込情報を抽出する抽出ステップとを含み、
前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、
前記図形情報記憶手段は、少なくとも３個の点をそれぞれ示す位置情報を含み、
前記点選択ステップは、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択する
ことを特徴とする記録媒体。
【請求項２０】
空間上において１個の点と他の点とが線で結ばれて表現され
る図形を示す図形情報から埋め込まれた埋込情報を抽出するコンピュータで用いられる情報抽出プログラムであって、
前記コンピュータは、請求項１に記載の情報埋込装置により埋込情報が埋め込まれた図形情報を記憶している図形情報記憶手段を備え、
前記情報抽出プログラムは、
前記図形情報記憶手段に記憶されている図形情報を読み出す読出ステップと、
前記複数の点から１個の点を選択する点選択ステップと、
選択された前記点を示す位置情報から、埋込情報を抽出する抽出ステップとを含み、
前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、
前記図形情報記憶手段は、少なくとも３個の点をそれぞれ示す位置情報を含み、
前記点選択ステップは、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択する
ことを特徴とする情報抽出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、図形情報に他の情報を埋め込む技術及び図形情報から埋め込まれた他の情報を抽出する技術に関する。
【０００２】
【従来の技術】
近年、インターネット利用の急速な広がりに伴い、公共機関や企業、個人間でマルチメディア情報の閲覧、授受、取引き等が頻繁に行われている。
特に、デジタルカメラやデジタルイメージスキャナなどにより取り込まれた写真画像であるデジタル画像に関しては、直接視覚に訴えることができるため付加価値の高いデジタルコンテンツとして流通するようになっている。
【０００３】
このようにデジタル画像の普及に伴い、その作成者の著作権をいかに保護するか問題になっている。
この問題点を解決するために、電子透かし技術を用いて、デジタル画像に著作権情報を埋め込むことが行われている。
【０００４】
【発明が解決しようとする課題】
しかしながら、最近では写真画像だけではなく、線画中心の地図情報もインターネットの中で送受信されており、これらの地図情報についてその著作権を効果的に保護したいという要望がある。
本発明は、図形情報を見た目に分からないように変えて、他の情報を埋め込む情報埋込装置、情報埋込方法及び情報埋込プログラム、並びに情報が埋め込まれた図形情報から他の情報を抽出する情報抽出装置、情報抽出方法及び情報抽出プログラムを提供することを目的とする。
【０００５】
【課題を解決するための手段】
上記目的を達成するために、本発明は、図形情報に他の情報を埋め込む情報埋込装置であって、線形状を指定する２次元の点情報及び前記線形状に関する属性情報から構成される図形データに対して、前記点情報の予め設定されたより最下位の桁の値を奇数あるいは偶数に変更する。ここで、埋め込みたい情報を０と１とからなるデジタルデータにしておき、埋め込みたい情報が１なら、前記桁を奇数に変え、埋め込みたい情報が０なら、前記桁を偶数に変える。このように、変更する桁をより最下位の桁に設定し、点のＸ座標値、Ｙ座標値を僅かに変えることにより、図形情報を見た目に分からないように変えて、他の情報を図形情報に埋め込むことができる。
【０００６】
このようにして前記情報埋込装置により、図形情報に他の情報が埋め込まれるので、情報抽出装置は、点情報の特定の桁が偶数であれば、０を抽出し、奇数であれば、１を抽出することにより、前記他の情報を抽出する。
また、前記情報埋込装置は、複数の点情報の中で、１個の点情報が隣接する他の点情報と予め設定された距離Ｒ以上に離れている場合のみ、当該点情報を埋め込み対象とし、前記埋め込み対象の点情報に他の情報を埋め込む。また、当該点情報が前記隣接する他の地点データと前記距離Ｒ以上離れていない場合は、当該点情報を埋め込み対象としない。これにより、図形情報を見た目に分からないように変えて、他の情報を図形情報に埋め込むことができる。
【０００７】
このようにして前記情報埋込装置により、図形情報に他の情報が埋め込まれるので、情報抽出装置は、１個の点情報が隣接する他の点情報と予め設定された距離Ｒ以上に離れている場合のみ、当該点情報に他の情報が埋め込まれていると見做して、当該点情報から他の情報を抽出する。
【０００８】
【発明の実施の形態】
１．第１の実施の形態
本発明に係る第１の実施の形態としての情報埋込システム１０について説明する。
情報埋込システム１０は、図１に示す情報埋込装置１と図１１に示す情報抽出装置２とから構成される。
【０００９】
１．１  情報埋込装置１の構成
ここでは、情報埋込装置１の構成について説明する。
情報埋込装置１は、図１に示すように、埋込情報入力部１１、埋込情報記憶部１２、暗号鍵入力部１３、暗号化部１４、暗号化埋込情報記憶部１５、元地図記憶部１６、読込部１７、情報埋込部１８及び埋込地図記憶部１９から構成されている。
【００１０】
情報埋込装置１は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＯＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサは、前記コンピュータプログラムに従って動作することにより、情報埋込装置１は、その機能を達成する。
【００１１】
（１）埋込情報入力部１１
埋込情報入力部１１は、具体的には、キーボード、マウスなどから構成され、利用者から埋込情報Ｆの入力を受け付け、受け付けた埋込情報Ｆを埋込情報記憶部１２へ書き込む。ここで、前記埋込情報Ｆを２進数で表現したときに、ｎ個の２値の値から構成されるものとする。
【００１２】
埋込情報Ｆは、一例として、著作権者を識別する名前である。
（２）埋込情報記憶部１２
埋込情報記憶部１２は、具体的には、ハードディスクユニットから構成され、埋込情報Ｆを記憶する領域を備えている。
（３）暗号鍵入力部１３
暗号鍵入力部１３は、具体的には、キーボード、マウスなどから構成され、利用者から暗号鍵Ｋの入力を受け付ける。ここでは、暗号鍵Ｋは、０以上、１以下の数値である。暗号鍵入力部１３は、受け付けた暗号鍵Ｋを暗号化部１４へ出力する。
【００１３】
（４）暗号化部１４
暗号化部１４は、暗号鍵入力部１３から暗号鍵Ｋを受け取り、埋込情報記憶部１２から埋込情報Ｆを読み出す。
暗号化部１４は、埋込情報Ｆのビット長ｎを取り出す。
暗号化部１４は、変数ｉ＝１、２、３、・・・、ｎについて、（式１）によりｆ（ｉ）を算出する。
（式１）  ｆ（ｉ）＝ｌｏｇ（暗号鍵Ｋ×ｉ）  （ｉ＝１、２、・・・、ｎ）
次に、ｎ個のｆ（ｉ）の少数点以下１桁を取り出す。具体的には、ｆ（ｉ）＝０．３１４であれば、１桁の数値「３」を取り出す。次に、取り出した１桁の数値に対して四捨五入を施して２値の値「０」又は「１」を得る。すなわち、取り出した１桁の数値が０〜４のいずれかであれば、２値の値「０」を得、取り出した１桁の数値が５〜９のいずれかであれば、２値の値「１」を得る。次に、得られたｎ個の２値の値を、ｉ＝１、２、・・・、ｎに対応づけて並べて、ｎ個の２値の値からなるビット列である暗号演算列Ｅを得る。
【００１４】
次に、暗号化部１４は、（式２）により、得られた暗号演算列Ｅと読み出した埋込情報Ｆとに排他的論理和を施して暗号化埋込情報Ｇを生成する。
（式２）  暗号化埋込情報Ｇ＝暗号演算列Ｅ（ＸＯＲ）埋込情報Ｆ
ここで、ＸＯＲは、排他的論理和を示す演算子である。
さらに、暗号化部１４は、生成された暗号化埋込情報Ｇの末尾に終了符号を付加する。ここで、終了符号は、一例として、「０１１１１１１０」であり、ビット列の最後を示すものである。
【００１５】
次に、暗号化部１４は、上のようにして生成された暗号化埋込情報Ｇを暗号化埋込情報記憶部１５へ書き込む。
暗号化埋込情報Ｇの一例を図４に示す。
（５）暗号化埋込情報記憶部１５
暗号化埋込情報記憶部１５は、具体的には、ハードディスクユニットから構成され、暗号化埋込情報Ｇを記憶する領域を備えている。
【００１６】
（６）元地図記憶部１６
元地図記憶部１６は、具体的には、ハードディスクユニットから構成され、あらかじめ元地図情報を記憶している。
元地図情報は、図２に一例として示すように、２次元空間において、線画を描くための情報を含んでいる。
【００１７】
元地図情報は、１以上の線画情報を含んでおり、各線画情報は、図形種別と、複数の点の位置情報と、色情報と、線種情報とから構成される。
図形種別は、描く図形の種類を示す。図２に示す線画情報１０１及び１０２において、種類は、それぞれ「Ｌｉｎｅ」及び「Ｐｏｌｙｇｏｎ」であり、「Ｌｉｎｅ」は、複数の点を順に線で結ぶことにより、１本の線を描くことを示し、「Ｐｏｌｙｇｏｎ」は、複数の点を順に線で環状に結ぶことにより、多角形を描くことを示している。
【００１８】
複数の点の位置情報のそれぞれは、２次元空間におけるＸ座標値とＹ座標値とを含む。ここで、Ｘ座標値とＹ座標値とは、１０進法で表現されている。
色情報は、描く図形の色を示す。
線種情報は、描く図形の線の種類を示す。例えば、実線、破線、一点鎖線などである。
【００１９】
線画情報１０１は、座標（１２３４５、５６７）と、座標（１２３４０、５６４）と、・・・とを線でこの順に結ぶことにより、１本の線を描くことを示している。ここで、線の色は、赤であり、線種は、実線である。
また、線画情報１１１は、座標（４６７８、４０１）と、座標（４６７０、３８７）と、・・・とを線でこの順に結ぶことにより、１個の多角形を描くことを示している。ここで、線の色は、青であり、線種は、破線である。
【００２０】
元地図情報に基づいて描かれた線画としての地図の一例を図３に示す。
（７）読込部１７
読込部１７は、元地図記憶部１６から元地図情報を読み出し、読み出した元地図情報を埋込地図記憶部１９へ埋込地図情報として書き込む。
（８）埋込地図記憶部１９
埋込地図記憶部１９は、具体的には、ハードディスクユニットから構成され、埋込地図情報を記憶する領域を備えている。
【００２１】
（９）情報埋込部１８
情報埋込部１８は、埋込地図記憶部１９から埋込地図情報内に含まれている位置情報を構成する座標値を１個ずつ順に読み出す。ここで、位置情報は、Ｘ座標値とＹ座標値とを含むので、Ｘ座標値とＹ座標値とを交互に読み出すことになる。
【００２２】
次に、情報埋込部１８は、読み出した座標値を１０進法で表現するときの、指定桁Ａ（ｉ）を取り出す。ここで、指定桁は、前記座標値の最下位桁であるとする。
次に、情報埋込部１８は、暗号化埋込情報記憶部１５に記憶されている暗号化埋込情報Ｇを２進法で表現するときに、暗号化埋込情報Ｇから１ビットＧ（ｉ）を順に読み出す。
【００２３】
次に、情報埋込部１８は、図５に示す表に従って、座標値の指定桁を更新する。
（ａ）暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合
（ａ−１）座標値の指定桁Ａ（ｉ）が偶数であるとき
Ａ（ｉ）に対してなにもしない。あるいは、Ａ（ｉ）にＡ（ｉ）を代入する演算を行ってもよい。
【００２４】
（ａ−２）座標値の指定桁Ａ（ｉ）が奇数であるとき
（式３）により指定桁を更新する。
（式３）Ａ（ｉ）＝Ａ（ｉ）＋１
（ｂ）暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合
（ｂ−１）座標値の指定桁Ａ（ｉ）が偶数であるとき
（式３）により指定桁を更新する。
【００２５】
（ｂ−２）座標値の指定桁Ａ（ｉ）が奇数であるとき
Ａ（ｉ）に対してなにもしない。あるいは、Ａ（ｉ）にＡ（ｉ）を代入する演算を行ってもよい。
次に、情報埋込部１８は、更新されたＡ（ｉ）を、埋込地図記憶部１９の元の座標値の指定桁に上書きする。
【００２６】
情報埋込部１８は、上記の演算を暗号化埋込情報Ｇを構成する全てのビットに対して行う。
（具体例）
次に、情報埋込部１８による図５に示す表に基づく座標値の指定桁の更新について、図２、図４及び図６に示す例を用いて、具体的に説明する。
【００２７】
図２における指定桁１０２が示す値「５」が取り出され、図４における暗号化埋込情報Ｇの値１２２「０」が取り出されると、値１２２「０」は偶数であり、指定桁１０２が示す値「５」は奇数であるので、値「５」に１を加算して値「６」を得、得られた値「６」を図６の指定桁１３２に上書きする。
図２における指定桁１０３が示す値「７」が取り出され、図４における暗号化埋込情報Ｇの値１２３「１」が取り出されると、値１２３「１」は奇数であり、指定桁１０３が示す値「７」は奇数であるので、指定桁１０３が示す値「７」は、図６の指定桁１３３においても変わることはなく、値「７」である。
【００２８】
１．２  情報埋込装置１の動作
ここでは、情報埋込装置１の動作について説明する。
（１）情報埋込装置１の全体の概要動作
情報埋込装置１の全体の概要動作について、図７に示すフローチャートを用いて説明する。
【００２９】
埋込情報入力部１１は、利用者から埋込情報Ｆの入力を受け付け、受け付けた埋込情報Ｆを埋込情報記憶部１２へ書き込み（ステップＳ１０１）、次に、暗号鍵入力部１３は、利用者から暗号鍵Ｋの入力を受け付け、受け付けた暗号鍵Ｋを暗号化部１４へ出力する（ステップＳ１０２）。
さらに、暗号化部１４は、暗号鍵Ｋを用いて埋込情報Ｆに暗号化アルゴリズムを施して暗号化埋込情報Ｇを生成し、生成した暗号化埋込情報Ｇを暗号化埋込情報記憶部１５へ書き込む（ステップＳ１０３）。
【００３０】
次に、読込部１７は、元地図記憶部１６から元地図情報を読み出し、読み出した元地図情報を埋込地図記憶部１９へ埋込地図情報として書き込み（ステップＳ１０４）、情報埋込部１８は、埋込地図情報へ暗号化埋込情報Ｇを埋め込む（ステップＳ１０５）。
（２）暗号化部１４の動作
暗号化部１４の動作について、図８に示すフローチャートを用いて説明する。
【００３１】
暗号化部１４は、暗号鍵入力部１３から暗号鍵Ｋを受け取り（ステップＳ１２１）、暗号演算列Ｅを生成し（ステップＳ１２２）、埋込情報記憶部１２から埋込情報Ｆを読み出す（ステップＳ１２３）。次に、暗号化部１４は、暗号列Ｅと埋込情報Ｆとに排他的論理和を施して暗号化埋込情報Ｇを生成し（ステップＳ１２４）、生成された暗号化埋込情報Ｇの末尾に終了符号を付加し（ステップＳ１２５）、生成された暗号化埋込情報Ｇを暗号化埋込情報記憶部１５へ書き込む（ステップＳ１２６）。
【００３２】
次に、ステップＳ１２２に示す暗号演算列Ｅの生成動作の詳細について、図９に示すフローチャートを用いて説明する。
暗号化部１４は、変数ｉに０の値を初期値として設定する（ステップＳ１４１）。
次に、暗号化部１４は、変数ｉに１の値を加算し（ステップＳ１４２）、変数ｉがｎより大きければ（ステップＳ１４３でＹＥＳ）、暗号演算列Ｅの生成動作の処理を終了する。
【００３３】
変数ｉがｎより大きくなければ（ステップＳ１４３でＮＯ）、暗号化部１４は、ｆ（ｉ）＝ｌｏｇ（Ｋ×ｉ）を演算し（ステップＳ１４４）、次にｆ（ｉ）の少数点以下１桁を取り出し（ステップＳ１４５）、取り出した１桁を２値化してものをＥ（ｉ）とし（ステップＳ１４６）、次にステップＳ１４２へ戻って処理を繰り返す。
【００３４】
（３）情報埋込部１８の動作
情報埋込部１８の動作について、図１０に示すフローチャートを用いて説明する。
情報埋込部１８は、変数ｉに０の値を初期値として設定する（ステップＳ１６１）。
【００３５】
次に、情報埋込部１８は、変数ｉに１の値を加算し（ステップＳ１６２）、変数ｉがｎより大きければ（ステップＳ１６３でＹＥＳ）、情報埋込部１８の処理を終了する。
変数ｉがｎより大きくなければ（ステップＳ１６３でＮＯ）、情報埋込部１８は、座標値の指定桁Ａ（ｉ）を取り出し（ステップＳ１６４）、暗号化埋込情報Ｇ（ｉ）を取り出す（ステップＳ１６５）。
【００３６】
次に、情報埋込部１８は、Ｇ（ｉ）が０か１かを判断し、０である場合（ステップＳ１６６）、さらに、Ａ（ｉ）が偶数か奇数かを判断し、偶数であるとき（ステップＳ１６７）、ステップＳ１６２へ戻って処理を繰り返す。
偶数であるとき（ステップＳ１６７）、情報埋込部１８は、Ａ（ｉ）に１の値を加算し（ステップＳ１６８）、Ａ（ｉ）を上書きし（ステップＳ１６９）、ステップＳ１６２へ戻って処理を繰り返す。
【００３７】
情報埋込部１８は、Ｇ（ｉ）が０か１かを判断し、１である場合（ステップＳ１６６）、さらに、Ａ（ｉ）が偶数か奇数かを判断し、偶数であるとき（ステップＳ１７０）、Ａ（ｉ）に１の値を加算し（ステップＳ１７１）、Ａ（ｉ）を上書きし（ステップＳ１７２）、ステップＳ１６２へ戻って処理を繰り返す。
奇数であるとき（ステップＳ１７０）、情報埋込部１８は、ステップＳ１６２へ戻って処理を繰り返す。
【００３８】
１．３  情報抽出装置２の構成
ここでは、情報抽出装置２の構成について説明する。
情報抽出装置２は、図１１に示すように、埋込地図記憶部２１、情報抽出部２２、暗号化埋込情報記憶部２３、暗号鍵入力部２４、復号部２５及び埋込情報記憶部２６から構成されている。
【００３９】
情報抽出装置２は、具体的には、情報埋込装置１と同様に、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＯＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサは、前記コンピュータプログラムに従って動作することにより、情報抽出装置２は、その機能を達成する。
【００４０】
（１）埋込地図記憶部２１
埋込地図記憶部２１は、具体的には、ハードディスクユニットから構成され、情報埋込装置１により生成された埋込地図情報を記憶している。
（２）情報抽出部２２
情報抽出部２２は、埋込地図記憶部２１の埋込地図情報内に含まれている位置情報を構成する座標値を１個ずつ順に読み出す。ここで、位置情報は、Ｘ座標値とＹ座標値とを含むので、Ｘ座標値とＹ座標値とを交互に読み出すことになる。
【００４１】
次に、情報抽出部２２は、読み出した座標値を１０進法で表現するときの、指定桁Ａ（ｉ）を取り出す。ここで、指定桁は、前記座標値の最下位桁であるとする。
次に、情報抽出部２２は、Ａ（ｉ）が偶数か奇数かを判断し、奇数であるなら、暗号化埋込情報Ｇの１ビットであるＧ（ｉ）に１の値を設定する。偶数であるなら、暗号化埋込情報Ｇの１ビットであるＧ（ｉ）に０の値を設定する。
【００４２】
情報埋込部１８は、上記の演算を埋込地図記憶部２１の埋込地図情報内に含まれている位置情報を構成する全ての座標値に対して行う。
最後に、情報埋込部１８は、暗号化埋込情報Ｇを暗号化埋込情報記憶部２３に書き込む。
（３）暗号化埋込情報記憶部２３
暗号化埋込情報記憶部２３は、具体的には、ハードディスクユニットから構成され、暗号化埋込情報Ｇを記憶する領域を備えている。
【００４３】
（４）暗号鍵入力部２４
暗号鍵入力部２４は、暗号鍵入力部１３と同様であるので、説明を省略する。
（５）復号部２５
復号部２５は、暗号鍵入力部２４から暗号鍵Ｋを受け取り、暗号化埋込情報記憶部２３から暗号化埋込情報Ｇを読み出す。次に、復号部２５は、読み出した暗号化埋込情報Ｇの末尾から終了符号を削除し、その後に、暗号化埋込情報Ｇのビット長ｎを取り出す。
【００４４】
復号部２５は、暗号化部１４と同様にして暗号演算列Ｅを得る。
次に、復号部２５は、（式４）により、得られた暗号演算列Ｅと暗号化埋込情報Ｇとに排他的論理和を施して埋込情報Ｆを生成する。
（式４）  埋込情報Ｆ＝暗号演算列Ｅ（ＸＯＲ）暗号化埋込情報Ｇ
次に、復号部２５は、上のようにして生成された埋込情報Ｆを埋込情報記憶部２６へ書き込む。
【００４５】
（６）埋込情報記憶部２６
埋込情報記憶部２６は、具体的には、ハードディスクユニットから構成され、埋込情報Ｆを記憶する領域を備えている。
１．４  情報抽出装置２の動作
ここでは、情報抽出装置２の動作について説明する。
【００４６】
（１）情報抽出装置２の概要動作
情報抽出装置２の全体の概要動作について、図１２に示すフローチャートを用いて説明する。
情報抽出部２２は、埋込地図記憶部に記憶されている埋込地図情報から暗号化埋込情報Ｇを抽出し、抽出した暗号化埋込情報Ｇを暗号化埋込情報記憶部２３に書き込む（ステップＳ１８１）。次に、暗号鍵入力部２４は、暗号鍵Ｋの入力を受け付け、入力を受け付けた暗号鍵Ｋを復号部２５へ出力する（ステップＳ１８２）。
【００４７】
次に、復号部２５は、暗号化埋込情報記憶部２３から暗号化埋込情報Ｇを読み出し、読み出した暗号化埋込情報Ｇを復号して埋込情報Ｆを生成し、生成した埋込情報Ｆを埋込情報記憶部２６へ書き込む（ステップＳ１８３）。
（２）情報抽出部２２の動作
情報抽出部２２の動作について、図１３に示すフローチャートを用いて説明する。
【００４８】
情報抽出部２２は、変数ｉに０の値を初期値として設定する（ステップＳ２０１）。
次に、情報抽出部２２は、変数ｉに１の値を加算し（ステップＳ２０２）、終了符号を検出すれば（ステップＳ２０３でＹＥＳ）、暗号化埋込情報Ｇの末尾の終了符号を除去し（ステップＳ２０８）、終了符号の除去された暗号化埋込情報Ｇを暗号化埋込情報記憶部２３へ書き込み（ステップＳ２０９）、情報抽出部２２の処理を終了する。
【００４９】
終了符号を検出しなければ（ステップＳ２０３でＮＯ）、情報抽出部２２は、座標値の指定桁Ａ（ｉ）を取り出す（ステップＳ２０４）。
次に、情報抽出部２２は、Ａ（ｉ）が偶数か奇数かを判断し、奇数であるとき（ステップＳ２０５）、「１」をＧ（ｉ）に代入し（ステップＳ２０６）、ステップＳ２０２へ戻って処理を繰り返す。
【００５０】
偶数であるとき（ステップＳ２０５）、情報抽出部２２は、「０」をＧ（ｉ）に代入し（ステップＳ２０７）、ステップＳ２０２へ戻って処理を繰り返す。
（３）復号部２５の動作
復号部２５の動作について、図１４に示すフローチャートを用いて説明する。復号部２５は、暗号鍵Ｋを受け取り（ステップＳ２２１）、暗号演算列Ｅを生成し（ステップＳ２２２）、暗号化埋込情報Ｇを暗号化埋込情報記憶部２３から読み出し（ステップＳ２２３）、埋込情報Ｆ＝Ｅ（ＸＯＲ）Ｇを演算し（ステップＳ２２４）、得られた埋込情報Ｆを埋込情報記憶部２６へ書き込む（ステップＳ２２５）。
【００５１】
１．５  まとめ
以上説明したように、情報埋込装置１は、線形状を指定する２次元の地点データおよび前記線形状に関する属性データから構成される地図データに対して、前記地点データの予め設定された桁の値を奇数あるいは偶数に変更するものであり、２次元地点データのＸＹ座標値に関して予め設定した下位の桁を僅かに変え、奇数あるいは偶数にすることにより、地図上見た目にわからず、他の情報を生埋め込むことができる。
【００５２】
また、情報埋込装置１により図５に示す規則により他の情報が地図情報に埋め込まれるので、情報抽出装置２は、他の情報が埋め込まれた座標値の桁が偶数であるか奇数であるかにより、２値の「０」または「１」を生成するので、地図情報から、前記埋め込まれた他の情報を抽出することができる。
１．６  変形例
情報埋込システム１０において、埋込情報を２値のビット列、すなわち、２進数により表現し、埋込情報の埋込み先である各点の座標値の最下位桁を１０進数により表現しているが、次に示すようにしてもよい。
【００５３】
埋込情報を複数桁のａ（ａは、正整数、ａ＞１）進数で表現し、前記複数桁のうちの１個の桁が示す値を埋込値として抽出する。
また、各点を示す位置情報を複数桁のｂ（ｂは、正整数、ｂ＞１）進数で表現し、前記複数桁のうちの特定の１個の桁を埋込の対象桁とする。
（１）第１の変形例
ａ＝ｂの場合における変形例について説明する。
【００５４】
ここで、一例として、ａ＝１０、ｂ＝１０とする。
情報埋込装置１の情報埋込部１８は、抽出した前記埋込値を前記対象桁が示す値に上書きすることにより、前記対象桁が示す値を更新する。
情報抽出装置２の情報抽出部２２は、前記対象桁が示す値を、そのまま埋込値として抽出する。
【００５５】
（２）第２の変形例
ａ＝ｂの場合における別の変形例について説明する。
ここで、一例として、ｄ＝ａ＝ｂ＝７とする。
情報埋込装置１の情報埋込部１８は、埋込地図情報から座標値を取り出し、取り出した座標値をｄで割り、商と余りを算出する。
【００５６】
ここで、  座標値  ＝  商  ×  ｄ  ＋  余り  である。
次に、情報埋込部１８は、次の式により、新たな座標値を算出する。
新たな座標値  ＝  商  ×  ｄ  ＋  埋込値
次に、情報埋込部１８は、算出した新たな座標値を埋込地図情報に上書きする。
【００５７】
情報抽出装置２の情報抽出部２２は、埋込地図情報から座標値を取り出し、取り出した座標値をａで割り、余りを算出し、算出した余りを埋込値とする。
次に、具体例を図１５を用いて示す。
情報埋込装置１の情報埋込部１８は、埋込地図情報から座標値２０１「１２３４５」を取り出し、取り出した座標値を「７」で割り、商「１７６３」と余り「４」を算出する。次に、埋込値２０２「６」を取り出す。
【００５８】
次に、以下の式により、新たな座標値２０３を算出する。
１７６３×７＋６＝１２３４７
算出した座標値２０３「１２３４７」を埋込地図情報に上書きする。
情報抽出装置２の情報抽出部２２は、埋込地図情報から座標値２０３「１２３４７」を取り出し、取り出した座標値２０３「１２３４７」を「７」で割り、余り「６」を算出し、算出した余り「６」を埋込値とする。
【００５９】
（情報埋込部１８の動作）
情報埋込部１８の動作について、図１６に示すフローチャートを用いて説明する。
情報埋込部１８は、変数ｉに０の値を初期値として設定する（ステップＳ２４１）。
【００６０】
次に、情報埋込部１８は、変数ｉに１の値を加算し（ステップＳ２４２）、変数ｉがｎより大きければ（ステップＳ２４３でＹＥＳ）、情報埋込部１８の処理を終了する。ここで、ｎは、暗号化埋込情報Ｇ’の桁数である。
変数ｉがｎより大きくなければ（ステップＳ２４３でＮＯ）、情報埋込部１８は、座標値Ｂ（ｉ）を取り出し（ステップＳ２４４）、暗号化埋込情報Ｇ’（ｉ）を取り出す（ステップＳ２４５）。
【００６１】
次に、情報埋込部１８は、Ｂ（ｉ）をｄで割ったときの商を算出し（ステップＳ２４６）、Ｂ’（ｉ）＝ｄ×商＋Ｇ’（ｉ）を算出し（ステップＳ２４７）、Ｂ（ｉ）へＢ’（ｉ）を上書きし（ステップＳ２４８）、さらに、ステップＳ２４２へ戻って処理を繰り返す。
（情報抽出部２２の動作）
情報抽出部２２の動作について、図１７に示すフローチャートを用いて説明する。
【００６２】
情報抽出部２２は、変数ｉに０の値を初期値として設定する（ステップＳ２６１）。
次に、情報抽出部２２は、変数ｉに１の値を加算し（ステップＳ２６２）、終了符号を検出すれば（ステップＳ２６３でＹＥＳ）、暗号化埋込情報Ｇ’の末尾の終了符号を除去し（ステップＳ２６７）、終了符号の除去された暗号化埋込情報Ｇ’を暗号化埋込情報記憶部２３へ書き込み（ステップＳ２６８）、情報抽出部２２の処理を終了する。
【００６３】
終了符号を検出しなければ（ステップＳ２６３でＮＯ）、情報抽出部２２は、座標値Ｂ（ｉ）を取り出す（ステップＳ２６４）。
次に、情報抽出部２２は、Ｂ（ｉ）をｄで割ったときの余りを算出し（ステップＳ２６５）、算出した余りをＧ’（ｉ）に代入し（ステップＳ２６６）、ステップＳ２６２へ戻って処理を繰り返す。
【００６４】
（３）第３の変形例
ａ＜ｂの場合の変形例について説明する。
ここで、一例として、ａ＝４、ｂ＝１０とする。
情報埋込装置１の情報埋込部１８は、前記埋込値に、次に示す変換アルゴリズムを施して変換値を生成し、生成した変換値を前記対象桁が示す値に上書きする。
【００６５】
変換アルゴリズムでは、前記所定の変換アルゴリズムは、ａ種の数字をｂ種の数字のいずれかに変換する。埋込値が０なら、変換値を０、１、２のいずれかの値とする。また、埋込値が１なら、変換値を３、４のいずれかの値とする。また、埋込値が２なら、変換値を５、６、７のいずれかの値とする。また、埋込値が３なら、変換値を８、９のいずれかの値とする。
【００６６】
この変換アルゴリズムにおいて、変換値の対象となる値が複数個存在するが、そのうちのいずれかを採用する場合、元の対象桁に最も近い値を採用するようにすることもできる。これにより、元の図形の形状に近似するように、他の情報を図形情報に埋め込むことができる。
情報抽出装置２の情報抽出部２２は、前記対象桁が示す値に、前記変換アルゴリズムの逆変換アルゴリズムを施して、埋込値を抽出する。
【００６７】
逆変換アルゴリズムでは、逆変換アルゴリズムにより、変換された数字から元の数字が生成される。対象桁が示す値が、０、１、２のいずれかの値であれば、埋込値として０を抽出する。対象桁が示す値が、３、４のいずれかの値であれば、埋込値として１を抽出する。対象桁が示す値が、５、６、７のいずれかの値であれば、埋込値として２を抽出する。対象桁が示す値が、８、９のいずれかの値であれば、埋込値として３を抽出する。
【００６８】
なお、上記の変換アルゴリズムにおいて、４種の数字と１０種の数字との対応付けを次にように表現する。
（０，１，２，３）＝（（０，１，２），（３，４），（５，６，７），（８，９））
上記において、左辺は、４種の数字の組み合せを示し、右辺は、１０種の数字の組み合せを示しており、４種の数字のうちの「０」は、１０種の数字のうちの「０、１、２」に対応していることを示している。その他の数字についても同様である。
【００６９】
上記の変換アルゴリズムにおいて、ａ種の数字とｂ種の数字との対応付けは、上記の例に限定されない。以下のような対応付けを用いるとしてもよい。
（０，１，２，３）＝（（０，４，８），（１，５），（２，６，９），（３，７））
この対応づけにおいては、４種の数字のうちの「０」は、１０種の数字のうちの「０、４、８」に対応している。このように、「０、４、８」は、連続する値ではなく、散らばった値である。
【００７０】
この対応付けを用いると、変換アルゴリズムにおいて、上記と同様に、変換値の対象となる値が複数個存在し、そのうちのいずれを採用するかは、元の対象桁に最も近い値を採用するようにする。このとき、例えば、「０、４、８」は、連続する値ではなく、散らばった値であるので、元の値により近い値を選択することができるようになる。これにより、元の図形の形状に近似するように、他の情報を図形情報に埋め込むことができる。
【００７１】
１．７  具体例
第１の実施の形態の具体例として、１つの線分上での地点間の平均距離が約１００ドットの道路地図に対して、埋め込みデータとしてＪＩＳ７コードで年月日を１０文字（例２００１：０１：０１）を、実際に埋め込んでみたが、視覚上全く問題なかった。なお、暗号化部が使用する数式は以下に示す式として、ｙの小数１桁目の値を四捨五入した。
【００７２】
ｙ＝ｌｏｇ（Ｃｘ）
ここで、ｌｏｇは自然対数である。
２．第２の実施の形態
本発明に係る第２の実施の形態としての情報埋込システム２０について説明する。
【００７３】
情報埋込システム２０は、情報埋込システム１０と同様の構成であり、情報埋込装置１と情報抽出装置２とから構成される。ここでは、情報埋込システム１０との相違点を中心にして説明する。
２．１  情報埋込装置１の構成
情報埋込部１８の構成について説明する。他の構成部は、情報埋込システム１０と同じであるので、説明を省略する。
【００７４】
（１）点の位置情報の読出し
情報埋込部１８は、埋込地図記憶部１９から埋込地図情報内に含まれている線画情報のうち、３個以上の点の位置情報を含む線画情報を選択し、選択した線画情報の中から３個の点の位置情報を順に読み出す。これらの３個の点の位置情報は、連続して線画情報内に並べられているものである。
【００７５】
このように、３個の点の位置情報を順に読み出すので、読み出されていない位置情報が２個以下になると、情報埋込部１８は、読み出しを終了する。
ここで、前記３個の点の位置情報をｐ（ｊ−１）、ｐ（ｊ）、ｐ（ｊ＋１）で示す。また、各位置情報は、Ｘ座標値とＹ座標値とを含む。また、各座標値は、１０進法で表現するものとする。
【００７６】
前記３個の位置情報ｐ（ｊ−１）、ｐ（ｊ）、ｐ（ｊ＋１）により示される３個の点を図１８（ａ）に示す。図１８（ａ）において、横軸は、Ｘ座標軸であり、縦軸は、Ｙ座標軸である。
次に、情報埋込部１８は、暗号化埋込情報記憶部１５に記憶されている暗号化埋込情報Ｇを２進法で表現するときに、暗号化埋込情報Ｇから１ビットＧ（ｉ）を順に読み出す。
【００７７】
（２）距離の判定と埋込
次に、情報埋込部１８は、点ｐ（ｊ−１）と点ｐ（ｊ）との距離を算出する。点ｐ（ｊ−１）の座標を（Ｘｊ−１  、Ｙｊ−１  ）とし、点ｐ（ｊ）の座標を（Ｘｊ  、Ｙｊ  ）とすると、
点ｐ（ｊ−１）と点ｐ（ｊ）との距離＝
ＳＱＲＴ（  （Ｙｊ  −Ｙｊ−１  ）＊＊２＋（Ｘｊ  −Ｘｊ−１  ）＊＊２  ）
により算出される。ここで、ＳＱＲＴは、平方根の演算を示し、＊＊は、べき乗の演算を示す。また、同様にして、点ｐ（ｊ）と点ｐ（ｊ＋１）との距離を算出する。
【００７８】
次に、点ｐ（ｊ−１）と点ｐ（ｊ）との距離が所定値Ｒ以上であり、かつ点ｐ（ｊ）と点ｐ（ｊ＋１）との距離が所定値Ｒ以上であるか否かを判断する。両方の距離が所定値Ｒ以上である場合に、後述するようにして点ｐ（ｊ）にＧ（ｉ）を埋め込み、そうでない場合には、埋込みを行わない。
上記の処理は、図１８（ａ）に示すように、点ｐ（ｊ）を中心とする半径Ｒの円Ｃ１内に、点ｐ（ｊ−１）及び点ｐ（ｊ＋１）が存在するか否かを判断するものである。
【００７９】
点ｐ（ｊ）にＧ（ｉ）を埋め込む場合に、埋込みの後の点をｐ’（ｊ）とすると、情報埋込部１８は、点ｐ（ｊ−１）と点ｐ’（ｊ）との距離を算出し、点ｐ’（ｊ）と点ｐ（ｊ＋１）との距離を算出し、次に、点ｐ（ｊ−１）と点ｐ’（ｊ）との距離が所定値Ｒ以上であり、かつ点ｐ’（ｊ）と点ｐ（ｊ＋１）との距離が所定値Ｒ以上であるか否かを判断する。両方の距離が所定値Ｒ以上である場合に、次の３点ｐ（ｊ＋２）、ｐ（ｊ＋３）、ｐ（ｊ＋４）を用いてＧ（ｉ＋１）の埋込みを行う。そうでない場合には、次の３点ｐ（ｊ＋２）、ｐ（ｊ＋３）、ｐ（ｊ＋４）を用いて、再度Ｇ（ｉ）の埋込みを行う。
【００８０】
ここで、ｊ＝ｉ×３−１である。
（３）傾きの算出と領域判定
次に、情報埋込部１８は、図１８（ａ）に示すように、点ｐ（ｊ−１）と点ｐ（ｊ＋１）とを結ぶ線Ｌ１に平行し、点ｐ（ｊ）を通る線Ｌ２と、Ｘ座標とがなす角度、言い換えると、線Ｌ２の傾きを次の式により算出する。
【００８１】
角度＝ａｒｃｔａｎ（（Ｙｊ＋１  −Ｙｊ−１  ）／（Ｘｊ＋１  −Ｘｊ−１  ））
ここで、点ｐ（ｊ−１）の座標を（Ｘｊ−１  、Ｙｊ−１  ）とし、点ｐ（ｊ＋１）の座標を（Ｘｊ＋１  、Ｙｊ＋１  ）とする。
図１９に示すように、点ｐ（ｊ）を中心とするＸ−Ｙ座標系を想定する。次に、点ｐ（ｊ）を通り、Ｘ軸となす角度が、それぞれ２２．５度、６７．５度、１１２．５度、１５７．５度である直線Ｑ１、Ｑ２、Ｑ３、Ｑ４を想定する。
【００８２】
次に、この２次元空間を、領域Ｒ１、Ｒ２、Ｒ３に分割する。
ここで、領域Ｒ１は、Ｘ軸を含み、直線Ｑ１とＱ４とにより挟まれる領域である。また、領域Ｒ３は、Ｙ軸を含み、直線Ｑ２とＱ３とにより挟まれる領域である。また、領域Ｒ２は、前記２次元空間において、領域Ｒ１と領域Ｒ３とを除く領域である。
【００８３】
次に、情報埋込部１８は、線Ｌ２が領域Ｒ１、Ｒ２、Ｒ３のいずれに属するかを判断する。
線Ｌ２が領域Ｒ１に属すると判断する場合に、情報埋込部１８は、後述する領域Ｒ１の埋込処理を行う。また、線Ｌ２が領域Ｒ２に属すると判断する場合に、後述する領域Ｒ２の埋込処理を行う。また、線Ｌ２が領域Ｒ３に属すると判断する場合に、後述する領域Ｒ３の埋込処理を行う。
【００８４】
（４）領域Ｒ１の埋込処理
線Ｌ２が領域Ｒ１に属すると判断する場合に、図２０（ａ）に示すように、情報埋込部１８は、暗号化埋込情報Ｇ（ｉ）が０（偶数）であるか、１（奇数）であるかを判断し、また、ｐ（ｊ）のＸ座標値の最下位桁が偶数であるか奇数であるかを判断する。
（ａ）暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合
（ａ−１）ｐ（ｊ）のＸ座標値の最下位桁が偶数であるとき
情報埋込部１８は、なにもしない。又は、ｐ（ｊ）のＸ座標値の最下位桁の値をｐ（ｊ）のＸ座標値の最下位桁に上書きする。
【００８５】
（ａ−２）ｐ（ｊ）のＸ座標値の最下位桁が奇数であるとき
情報埋込部１８は、ｐ（ｊ）が図１８（ｂ）に示す頂点Ｔの方向へ移動するように、ｐ（ｊ）のＸ座標値の最下位桁の値に１を加算し、又は１を引き、ｐ（ｊ）のＸ座標値の最下位桁に上書きする。
（ｂ）暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合
（ｂ−１）ｐ（ｊ）のＸ座標値の最下位桁が奇数であるとき
情報埋込部１８は、なにもしない。又は、ｐ（ｊ）のＸ座標値の最下位桁の値をｐ（ｊ）のＸ座標値の最下位桁に上書きする。
【００８６】
（ｂ−２）ｐ（ｊ）のＸ座標値の最下位桁が偶数であるとき
情報埋込部１８は、ｐ（ｊ）が頂点Ｔの方向へ移動するように、ｐ（ｊ）のＸ座標値の最下位桁の値に１を加算し、又は１を引き、ｐ（ｊ）のＸ座標値の最下位桁に上書きする。
（５）領域Ｒ２の埋込処理
線Ｌ２が領域Ｒ２に属すると判断する場合に、図２０（ｂ）に示すように、情報埋込部１８は、暗号化埋込情報Ｇ（ｉ）が０（偶数）であるか、１（奇数）であるかを判断し、また、ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁が共に偶数であるか否か、またはｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁が共に奇数であるか否かを判断する。
（ａ）暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合
（ａ−１）ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁が共に偶数であるとき情報埋込部１８は、なにもしない。又は、ｐ（ｊ）のＸ座標値及びＹ座標値のの最下位桁の値を、それぞれｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁に上書きする。
【００８７】
（ａ−２）ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁の少なくとも一方が奇数であるとき、ｐ（ｊ）が頂点Ｔの方向へ移動するように、Ｘ座標値及びＹ座標値の最下位桁が共に偶数となるように、１の値を加算し、又は１の値を引く。このとき、次の３ケースが想定される。
（ａ−２−１）Ｘ座標値及びＹ座標値の最下位桁の両方が奇数であるとき
Ｘ座標値及びＹ座標値のそれぞれの最下位桁に１の値を加算し、又は１の値を引き、Ｘ座標値及びＹ座標値のそれぞれの最下位桁に上書きする。
【００８８】
（ａ−２−２）Ｘ座標値の最下位桁のみが奇数であるとき
Ｘ座標値の最下位桁に１の値を加算し、又は１の値を引き、Ｘ座標値の最下位桁に上書きする。
（ａ−２−３）Ｙ座標値の最下位桁のみが奇数であるとき
Ｙ座標値の最下位桁に１の値を加算し、又は１の値を引き、Ｙ座標値の最下位桁に上書きする。
（ｂ）暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合
（ｂ−１）ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁が共に奇数であるとき情報埋込部１８は、なにもしない。又は、ｐ（ｊ）のＸ座標値及びＹ座標値のの最下位桁の値を、それぞれｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁に上書きする。
【００８９】
（ｂ−２）ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁の少なくとも一方が偶数であるとき
ｐ（ｊ）が頂点Ｔの方向に移動するように、Ｘ座標値及びＹ座標値の最下位桁が共に奇数となるように、１の値を加算し、又は１の値を引く。このとき、次の３ケースが想定される。
【００９０】
（ｂ−２−１）Ｘ座標値及びＹ座標値の最下位桁の両方が偶数であるとき
ｐ（ｊ）が頂点Ｔの方向に移動するように、Ｘ座標値及びＹ座標値のそれぞれの最下位桁に１の値を加算し、又は１の値を引く。Ｘ座標値及びＹ座標値のそれぞれの最下位桁に上書きする。
（ｂ−２−２）Ｘ座標値の最下位桁のみが偶数であるとき
ｐ（ｊ）が頂点Ｔの方向に移動するように、Ｘ座標値の最下位桁に１の値を加算し、又は１の値を引き、Ｘ座標値の最下位桁に上書きする。
【００９１】
（ｂ−２−３）Ｙ座標値の最下位桁のみが偶数であるとき
ｐ（ｊ）が頂点Ｔの方向に移動するように、Ｙ座標値の最下位桁に１の値を加算し、又は１の値を引き、Ｙ座標値の最下位桁に上書きする。
（６）領域Ｒ３の埋込処理
線Ｌ２が領域Ｒ３に属すると判断する場合に、図２０（ｃ）に示すように、情報埋込部１８は、暗号化埋込情報Ｇ（ｉ）が０（偶数）であるか、１（奇数）であるかを判断し、また、ｐ（ｊ）のＹ座標値の最下位桁が偶数であるか奇数であるかを判断する。
（ａ）暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合
（ａ−１）ｐ（ｊ）のＹ座標値の最下位桁が偶数であるとき
情報埋込部１８は、なにもしない。又は、ｐ（ｊ）のＹ座標値の最下位桁の値をｐ（ｊ）のＹ座標値の最下位桁に上書きする。
【００９２】
（ａ−２）ｐ（ｊ）のＹ座標値の最下位桁が奇数であるとき
情報埋込部１８は、ｐ（ｊ）が頂点Ｔの方向へ移動するように、ｐ（ｊ）のＹ座標値の最下位桁の値に１を加算し、又は１を引き、ｐ（ｊ）のＹ座標値の最下位桁に上書きする。
（ｂ）暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合
（ｂ−１）ｐ（ｊ）のＹ座標値の最下位桁が奇数であるとき
情報埋込部１８は、なにもしない。又は、ｐ（ｊ）のＹ座標値の最下位桁の値をｐ（ｊ）のＹ座標値の最下位桁に上書きする。
【００９３】
（ｂ−２）ｐ（ｊ）のＹ座標値の最下位桁が偶数であるとき
情報埋込部１８は、ｐ（ｊ）が頂点Ｔの方向へ移動するように、ｐ（ｊ）のＹ座標値の最下位桁の値に１を加算し、または１を引き、ｐ（ｊ）のＹ座標値の最下位桁に上書きする。
（７）その他の処理
情報埋込部１８は、上記の処理を暗号化埋込情報Ｇを構成する全てのビットに対して行う。
【００９４】
２．２  情報埋込装置１の動作
情報埋込部１８の動作について説明する。他の構成部は、情報埋込システム１０と同じであるので、説明を省略する。
（１）情報埋込部１８全体の概要動作
情報埋込部１８全体の概要動作について、図２１に示すフローチャートを用いて説明する。
【００９５】
情報埋込部１８は、変数ｉに０の値を初期値として設定する（ステップＳ３０１）。
次に、情報埋込部１８は、変数ｉに１の値を加算し（ステップＳ３０２）、変数ｉがｎより大きければ（ステップＳ３０３でＹＥＳ）、情報埋込部１８の処理を終了する。
【００９６】
変数ｉがｎより大きくなければ（ステップＳ３０３でＮＯ）、暗号化埋込情報Ｇ（ｉ）を取り出す（ステップＳ３０４）。次に、ｊ＝ｉ×３−１を算出し（ステップＳ３０５）、連続する３点の位置情報ｐ（ｊ−１）、ｐ（ｊ）、ｐ（ｊ＋１）を取り出し（ステップＳ３０６）、ｐ（ｊ）とｐ（ｊ−１）との距離がＲ以上であり、かつｐ（ｊ）とｐ（ｊ＋１）との距離がＲ以上である場合に（ステップＳ３０７でＹＥＳ）、Ｇ（ｉ）のｐ（ｊ）への埋込み処理を行い（ステップＳ３０８）、さらに、ｐ’（ｊ）とｐ（ｊ−１）との距離がＲ以上であり、かつｐ’（ｊ）とｐ（ｊ＋１）との距離がＲ以上である場合に（ステップＳ３０９でＹＥＳ）、ステップＳ３０２へ戻って処理を繰り返す。
【００９７】
ｐ（ｊ）とｐ（ｊ−１）との距離がＲ以上でなく、又はｐ（ｊ）とｐ（ｊ＋１）との距離がＲ以上でない場合に（ステップＳ３０７でＮＯ）、情報埋込部１８は、ステップＳ３０５へ戻って処理を繰り返す。
ｐ’（ｊ）とｐ（ｊ−１）との距離がＲ以上でなく、又はｐ’（ｊ）とｐ（ｊ＋１）との距離がＲ以上でない場合に（ステップＳ３０９でＮＯ）、情報埋込部１８は、ステップＳ３０５へ戻って処理を繰り返す。
【００９８】
（２）暗号化埋込情報Ｇ（ｉ）の埋込動作
情報埋込部１８における暗号化埋込情報Ｇ（ｉ）の埋込動作について、図２２に示すフローチャートを用いて説明する。なお、この動作は、図２１に示すフローチャートのステップＳ３０８の詳細である。
情報埋込部１８は、直線Ｌ２の傾きを算出する（ステップＳ３２１）。次に、傾きが−２２．５度以上かつ２２．５度未満、又は１５７．５度以上かつ２０２．５度未満であるとき（ステップＳ３２２）、Ｒ１領域の埋込処理を行い（ステップＳ３２３）、埋め込み処理を終了する。
【００９９】
傾きが２２．５度以上かつ６７．５度未満、１１２．５度以上かつ１５７．５度未満、２０２．５度以上かつ２４７．５度未満、又は２９２．５度以上かつ３３７．５度未満であるとき（ステップＳ３２２）、Ｒ２領域の埋込処理を行い（ステップＳ３２４）、埋め込み処理を終了する。
傾きが６７．５度以上かつ１１２．５度未満、又は２４７．５度以上かつ２９２．５度未満であるとき（ステップＳ３２２）、Ｒ３領域の埋込処理を行い（ステップＳ３２５）、埋め込み処理を終了する。
【０１００】
（３）Ｒ１領域の埋込動作
情報埋込部１８におけるＲ１領域の埋込動作について、図２３に示すフローチャートを用いて説明する。なお、この動作は、図２２に示すフローチャートのステップＳ３２３の詳細である。
情報埋込部１８は、暗号化埋込情報Ｇ（ｉ）が０（偶数）であるか、１（奇数）であるかを判断し、また、ｐ（ｊ）のＸ座標値の最下位桁が偶数であるか奇数であるかを判断する。
【０１０１】
暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合（ステップＳ３４１）、ｐ（ｊ）のＸ座標値の最下位桁が偶数であるとき（ステップＳ３４２）、情報埋込部１８は、なにもしないで、Ｒ１領域の埋込動作を終了する。
暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合（ステップＳ３４１）、ｐ（ｊ）のＸ座標値の最下位桁が奇数であるとき（ステップＳ３４２）、情報埋込部１８は、ｐ（ｊ）のＸ座標値の最下位桁の値に１を加算し、又は１を引き、ｐ（ｊ）のＸ座標値の最下位桁に上書きし（ステップＳ３４３）、Ｒ１領域の埋込動作を終了する。
【０１０２】
暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合（ステップＳ３４１）、ｐ（ｊ）のＸ座標値の最下位桁が奇数であるとき（ステップＳ３４４）、情報埋込部１８は、なにもしないで、Ｒ１領域の埋込動作を終了する。
暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合（ステップＳ３４１）、ｐ（ｊ）のＸ座標値の最下位桁が偶数であるとき（ステップＳ３４４）、情報埋込部１８は、ｐ（ｊ）のＸ座標値の最下位桁の値に１を加算し、又は１を引き、ｐ（ｊ）のＸ座標値の最下位桁に上書きし（ステップＳ３４５）、Ｒ１領域の埋込動作を終了する。
【０１０３】
（４）Ｒ２領域の埋込動作
情報埋込部１８におけるＲ２領域の埋込動作について、図２４に示すフローチャートを用いて説明する。なお、この動作は、図２２に示すフローチャートのステップＳ３２４の詳細である。
情報埋込部１８は、暗号化埋込情報Ｇ（ｉ）が０（偶数）であるか、１（奇数）であるかを判断し、また、ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁が共に偶数であるか否か、またはｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁が共に奇数であるか否かを判断する。
【０１０４】
暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合（ステップＳ３６１）、ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁が共に偶数であるとき（ステップＳ３６２）、情報埋込部１８は、なにもしないで、Ｒ２領域の埋込動作を終了する。
暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合（ステップＳ３６１）、ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁の少なくとも一方が奇数であるとき（ステップＳ３６２）、Ｘ座標値及びＹ座標値の最下位桁が共に偶数となるように、１の値を加算し、又は１の値を引き（ステップＳ３６３）、Ｒ２領域の埋込動作を終了する。
【０１０５】
暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合（ステップＳ３６１）、ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁が共に奇数であるとき（ステップＳ３６４）、情報埋込部１８は、なにもしないで、Ｒ２領域の埋込動作を終了する。
暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合（ステップＳ３６１）、ｐ（ｊ）のＸ座標値及びＹ座標値の最下位桁の少なくとも一方が偶数であるとき（ステップＳ３６４）、Ｘ座標値及びＹ座標値の最下位桁が共に奇数となるように、１の値を加算し、又は１の値を引き（ステップＳ３６５）、Ｒ２領域の埋込動作を終了する。
【０１０６】
（５）Ｒ３領域の埋込動作
情報埋込部１８におけるＲ３領域の埋込動作について、図２５に示すフローチャートを用いて説明する。なお、この動作は、図２２に示すフローチャートのステップＳ３２４の詳細である。
情報埋込部１８は、暗号化埋込情報Ｇ（ｉ）が０（偶数）であるか、１（奇数）であるかを判断し、また、ｐ（ｊ）のＹ座標値の最下位桁が偶数であるか奇数であるかを判断する。
【０１０７】
暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合（ステップＳ３８１）、ｐ（ｊ）のＹ座標値の最下位桁が偶数であるとき（ステップＳ３８２）、情報埋込部１８は、なにもしないで、Ｒ３領域の埋込動作を終了する。
暗号化埋込情報Ｇ（ｉ）が０（偶数）である場合（ステップＳ３８１）、ｐ（ｊ）のＹ座標値の最下位桁が奇数であるとき（ステップＳ３８２）、情報埋込部１８は、ｐ（ｊ）のＹ座標値の最下位桁の値に１を加算し、又は１を引きｐ（ｊ）のＹ座標値の最下位桁に上書きし（ステップＳ３８３）、Ｒ３領域の埋込動作を終了する。
【０１０８】
暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合（ステップＳ３８１）、ｐ（ｊ）のＹ座標値の最下位桁が奇数であるとき（ステップＳ３８４）、情報埋込部１８は、なにもしないで、Ｒ３領域の埋込動作を終了する。
暗号化埋込情報Ｇ（ｉ）が１（奇数）である場合（ステップＳ３８１）、ｐ（ｊ）のＹ座標値の最下位桁が偶数であるとき（ステップＳ３８４）、情報埋込部１８は、ｐ（ｊ）のＹ座標値の最下位桁の値に１を加算し、又は１を引き、ｐ（ｊ）のＹ座標値の最下位桁に上書きし（ステップＳ３８５）、Ｒ３領域の埋込動作を終了する。
【０１０９】
２．２  情報抽出装置２の構成
情報抽出部２２の構成について説明する。他の構成部は、情報埋込システム１０と同じであるので、説明を省略する。
（１）点の位置情報の読出し
情報抽出部２２は、情報埋込部１８と同様に、埋込地図記憶部２１から埋込地図情報内に含まれている線画情報のうち、３個以上の点の位置情報を含む線画情報を選択し、選択した線画情報の中から３個の点の位置情報を順に読み出す。これらの３個の点の位置情報は、連続して線画情報内に並べられているものである。
【０１１０】
このように、３個の点の位置情報を順に読み出すので、読み出されていない位置情報が２個以下になると、情報抽出部２２は、読み出しを終了する。
ここで、前記３個の点の位置情報をｐ（ｊ−１）、ｐ（ｊ）、ｐ（ｊ＋１）で示す。また、各位置情報は、Ｘ座標値とＹ座標値とを含む。また、各座標値は、１０進法で表現するものとする。
【０１１１】
前記３個の位置情報ｐ（ｊ−１）、ｐ（ｊ）、ｐ（ｊ＋１）により示される３個の点を図１８（ａ）に示す。図１８（ａ）において、横軸は、Ｘ座標軸であり、縦軸は、Ｙ座標軸である。
（２）距離の判定と抽出
次に、情報抽出部２２は、情報埋込部１８と同様に、点ｐ（ｊ−１）と点ｐ（ｊ）との距離、及び点ｐ（ｊ）と点ｐ（ｊ＋１）との距離を算出する。
【０１１２】
次に、情報抽出部２２は、点ｐ（ｊ−１）と点ｐ（ｊ）との距離が所定値Ｒ以上であり、かつ点ｐ（ｊ）と点ｐ（ｊ＋１）との距離が所定値Ｒ以上であるか否かを判断する。両方の距離が所定値Ｒ以上である場合に、後述するようにして点ｐ（ｊ）からＧ（ｉ）を抽出し、そうでない場合には、抽出を行わない。
（３）傾きの算出と領域判定
次に、情報抽出部２２は、情報埋込部１８と同様にして、点ｐ（ｊ−１）と点ｐ（ｊ＋１）とを結ぶ線Ｌ１に平行し、点ｐ（ｊ）を通る線Ｌ２と、Ｘ座標とがなす角度、言い換えると、線Ｌ２の傾きを算出する。
【０１１３】
また、図１９に示すように、領域Ｒ１、Ｒ２、Ｒ３を想定する。
次に、情報抽出部２２は、線Ｌ２が領域Ｒ１、Ｒ２、Ｒ３のいずれに属するかを判断する。
線Ｌ２が領域Ｒ１に属すると判断する場合に、情報抽出部２２は、後述する領域Ｒ１の抽出処理を行う。また、線Ｌ２が領域Ｒ２に属すると判断する場合に、後述する領域Ｒ２の抽出処理を行う。また、線Ｌ２が領域Ｒ３に属すると判断する場合に、後述する領域Ｒ３の抽出処理を行う。
【０１１４】
（４）領域Ｒ１の抽出処理
線Ｌ２が領域Ｒ１に属すると判断する場合に、情報抽出部２２は、ｐ（ｊ）のＸ座標値の最下位桁が偶数であるか奇数であるかを判断し、ｐ（ｊ）のＸ座標値の最下位桁が偶数である場合、Ｇ（ｉ）に０の値を代入し、ｐ（ｊ）のＸ座標値の最下位桁が奇数である場合、Ｇ（ｉ）に１の値を代入する。
【０１１５】
（５）領域Ｒ２の抽出処理
線Ｌ２が領域Ｒ２に属すると判断する場合に、情報抽出部２２は、ｐ（ｊ）のＸ座標値の最下位桁及びＹ座標値の最下位桁が共に偶数であるか、又は共に奇数であるかを判断し、共に偶数である場合、Ｇ（ｉ）に０の値を代入し、共に奇数である場合、Ｇ（ｉ）に１の値を代入する。
【０１１６】
（６）領域Ｒ３の抽出処理
線Ｌ２が領域Ｒ３に属すると判断する場合に、情報抽出部２２は、ｐ（ｊ）のＹ座標値の最下位桁が偶数であるか奇数であるかを判断し、偶数である場合、Ｇ（ｉ）に０の値を代入し、奇数である場合、Ｇ（ｉ）に１の値を代入する。
（７）その他の処理
情報抽出部２２は、前記３個の点の位置情報の読み出しを終了すると、暗号化埋込情報Ｇの末尾から終了符号を除去し、終了符号の除去された暗号化埋込情報Ｇを暗号化埋込情報記憶部２３へ書き込む。
【０１１７】
２．３  情報抽出装置２の動作
情報抽出部２２の動作について説明する。他の構成部の動作は、情報埋込システム１０と同じであるので、説明を省略する。
（１）情報抽出部２２の概要動作
情報抽出部２２の概要動作について、図２６に示すフローチャートを用いて説明する。
【０１１８】
情報抽出部２２は、変数ｉに０の値を初期値として設定する（ステップＳ４０１）。
次に、情報抽出部２２は、変数ｉに１の値を加算し（ステップＳ４０２）、終了符号を検出すれば（ステップＳ４０３でＹＥＳ）、暗号化埋込情報Ｇの末尾の終了符号を除去し（ステップＳ４０７）、終了符号の除去された暗号化埋込情報Ｇを暗号化埋込情報記憶部２３へ書き込み（ステップＳ４０８）、情報抽出部２２の処理を終了する。
【０１１９】
終了符号を検出しなければ（ステップＳ４０３でＮＯ）、情報抽出部２２は、ｊ＝ｉ×３−１を算出し（ステップＳ４０４）、連続する３点の位置情報ｐ（ｊ−１）、ｐ（ｊ）、ｐ（ｊ＋１）を取り出し（ステップＳ４０５）、ｐ（ｊ）からの抽出処理を行い（ステップＳ４０６）、ステップＳ４０２へ戻って処理を繰り返す。
【０１２０】
（２）ｐ（ｊ）からの抽出処理動作
情報抽出部２２におけるｐ（ｊ）からの抽出処理動作について、図２７に示すフローチャートを用いて説明する。なお、この動作は、図２６に示すフローチャートのステップＳ４０６の詳細である。
情報抽出部２２は、直線Ｌ２の傾きを算出する（ステップＳ４２１）。次に、傾きが−２２．５度以上かつ２２．５度未満、又は１５７．５度以上かつ２０２．５度未満であるとき（ステップＳ４２２）、Ｒ１領域の抽出処理を行い（ステップＳ４２３）、抽出処理を終了する。
【０１２１】
傾きが２２．５度以上かつ６７．５度未満、１１２．５度以上かつ１５７．５度未満、２０２．５度以上かつ２４７．５度未満、又は２９２．５度以上かつ３３７．５度未満であるとき（ステップＳ４２２）、Ｒ２領域の抽出処理を行い（ステップＳ４２４）、抽出処理を終了する。
傾きが６７．５度以上かつ１１２．５度未満、又は２４７．５度以上かつ２９２．５度未満であるとき（ステップＳ４２２）、Ｒ３領域の抽出処理を行い（ステップＳ４２５）、抽出処理を終了する。
【０１２２】
（３）Ｒ１領域の抽出動作
情報抽出部２２におけるＲ１領域の抽出動作について、図２８に示すフローチャートを用いて説明する。なお、この動作は、図２７に示すフローチャートのステップＳ４２３の詳細である。
情報抽出部２２は、ｐ（ｊ）のＸ座標値の最下位桁が偶数であるか奇数であるかを判断し、ｐ（ｊ）のＸ座標値の最下位桁が偶数である場合（ステップＳ４４１）、Ｇ（ｉ）に０の値を代入し（ステップＳ４４２）、ｐ（ｊ）のＸ座標値の最下位桁が奇数である場合（ステップＳ４４１）、Ｇ（ｉ）に１の値を代入する（ステップＳ４４３）。
【０１２３】
（４）Ｒ２領域の抽出動作
情報抽出部２２におけるＲ２領域の抽出動作について、図２９に示すフローチャートを用いて説明する。なお、この動作は、図２７に示すフローチャートのステップＳ４２４の詳細である。
情報抽出部２２は、ｐ（ｊ）のＸ座標値の最下位桁及びＹ座標値の最下位桁が共に偶数であるか、又は共に奇数であるかを判断し、共に偶数である場合（ステップＳ４６１）、Ｇ（ｉ）に０の値を代入し（ステップＳ４６２）、共に奇数である場合（ステップＳ４６１）、Ｇ（ｉ）に１の値を代入する（ステップＳ４６３）。
【０１２４】
（５）Ｒ３領域の抽出動作
情報抽出部２２におけるＲ３領域の抽出動作について、図３０に示すフローチャートを用いて説明する。なお、この動作は、図２７に示すフローチャートのステップＳ４２５の詳細である。
情報抽出部２２は、ｐ（ｊ）のＹ座標値の最下位桁が偶数であるか奇数であるかを判断し、偶数である場合（ステップＳ４８１）、Ｇ（ｉ）に０の値を代入し（ステップＳ４８２）、奇数である場合（ステップＳ４８１）、Ｇ（ｉ）に１の値を代入する（ステップＳ４８３）。
【０１２５】
２．４  具体例
第２の実施の形態の具体例として、上記と同じく１つの線分上での地点間の平均距離が約１００ドットの道路地図に対して、Ｒ＝５０ドット、埋め込みデータとしてＪＩＳ７コードで年月日を１０文字（例２００１：０１：０１）を埋め込んだが、視覚上全く問題なかった。
【０１２６】
２．５  第２の実施の形態のまとめ
第２の実施の形態では、線として連続する３地点データを１組のデータとし、ｊ番目の地点データＰ（ｊ）が、（ｊ−１）番目の地点データＰ（ｊ−１）及び（ｊ＋１）番目の地点データＰ（ｊ＋１）と距離Ｒ以上離れているかどうかを判定し、肯定された場合のみ埋め込みを行う。埋め込みは、Ｐ（ｊ−１）とＰ（ｊ＋１）を結ぶ直線に平行する直線であって、Ｐ（ｊ）を通る直線Ｌの方向に近似する方向に、Ｐ（ｊ）を移動させることにより行う。ここで、移動幅は、２次元座標上の最少単位とする。
【０１２７】
このようにすると、第１に、距離ＲをＰ（ｊ）の移動幅に対して十分大きくとれば、Ｐ（ｊ）の移動が視覚的に判りにくい。第２に、直線Ｌと平行にＰ（ｊ）を移動させることにより新たな凹凸発生を防ぐことができる。第３に、移動方向を地点Ｐ（ｊ−１）と地点Ｐ（ｊ＋１）の中点方向にすることにより、線分Ｐ（ｊ−１）Ｐ（ｊ）と線分Ｐ（ｊ）Ｐ（ｊ＋１）の加えた距離変化を少なくさせ、線分変化の視覚的ズレを最少に抑えることができる。前記距離変化を少なくさせる理由は図１８（ｂ）からもわかるように、線分Ｐ（ｊ−１）Ｐ（ｊ）と線分Ｐ（ｊ）Ｐ（ｊ＋１）の加えた距離が一定なのは同図の楕円ＥＣ上であり、そこから離れるほど両線分を加えた距離が増えて行くことになるため、同図の頂点に近づく方向が距離増加を抑える方向だからである。その他、地点Ｐ（ｊ）を移動させた結果、地点Ｐ（ｊ−１）および地点Ｐ（ｊ＋１）との距離がＲより小さくなる場合には、同じ埋め込み情報を再度次の３点の位置情報に埋め込む。
【０１２８】
このような理由から、本発明の第２の実施の形態では、データ埋め込みによる視覚的地図のズレを最小限に抑えると共に、埋め込んだデータは隣接する地点との距離判定により全て読み出せるというメリットを有する。
なお、上記実施の形態では１つの線分上の地点Ｐ（ｊ−１）、Ｐ（ｊ）、Ｐ（ｊ＋１）を１組として扱ったが、線分に関係なく地点Ｐ（ｊ）がその他の全ての地点と距離Ｒ以上であれば、地図の２次元空間上で１ドット分移動させることにより別情報を埋め込んでも良い。但し、その場合埋め込んだ結果、他地点との距離がＲ以下になればそのまま残し埋め込んでないものとして扱い、同じ情報を次の埋め込み候補地点に埋め込む必要がある。
【０１２９】
３．まとめ
以上のように本発明によれば、線形状を指定する２次元の地点データおよび前記線形状に関する属性データから構成される地図データに対して、前記地点データの予め設定された桁の値を奇数あるいは偶数に変更することにより、２次元地点データのＸＹ座標値に関して予め設定した下位の桁を僅か変え、地図上見た目にわからず、新たな符号を作ることができるという大きな第１のメリットを有する。こうして、第３者に埋め込む場所を秘匿し、地図データそのものも最小限の変更で済む。ここで、前記下位の桁を最下位桁としてもよい。これにより地図の変更を最小限に留めることができる。
【０１３０】
また、複数の２次元地点データの中で、当該の地点データが隣接する他の地点データと予め設定された距離Ｒ以上に離れている場合のみ埋め込み対象データとし、前記埋め込み対象データに別データを順次埋め込んで行き、前記隣接する他の地点データと前記距離Ｒ以上離れていない場合は、再度別な前記埋め込み対象データにデータ埋め込みを行い、データ埋め込み後前記距離Ｒ以上離れている場合のみ埋め込み地点とし、前記別データを読み出す場合は、前記埋め込み地点に関して地点データの予め設定された桁の値の奇数あるいは偶数の判定を行うことにより、隣接する地点間の距離がある程度離れたものを埋め込み対象にすることで、地点のズレを見た目に一層わからなくし、且つ埋め込んだデータを読み出すときは地点間の距離がＲ以上という判定で容易にデータを読み出せるという第２のメリットを有する。
【０１３１】
加えて、１つの線形状を指定する複数の２次元地点で、当該地点Ｐ（ｊ）と前後地点Ｐ（ｊ−１）、Ｐ（ｊ＋１）に関して前記Ｐ（ｊ）が前記Ｐ（ｊ−１）および前記Ｐ（ｊ＋１）と予め設定された距離Ｒ以上離れている場合、前記Ｐ（ｊ）を前記Ｐ（ｊ−１）と前記Ｐ（ｊ＋１）を結ぶ直線の平行方向に、且つ前記Ｐ（ｊ−１）と前記Ｐ（ｊ＋１）の中点に向けて２次元座標上で所定距離以下移動させ、移動させた結果前記Ｐ（ｊ）が前記Ｐ（ｊ−１）および前記Ｐ（ｊ＋１）と前記距離Ｒ以上離れていない場合のみ、前記直線の垂直方向に２次元座標上で前記所定距離以下移動させることにより、データ埋め込みによる形状変化に関して、出来るだけ突起やへこみを無くすという事と地点移動により埋め込み対象から外れることを避けられるという第３のメリットを有し、その実用的効果には大なるものがある。
【０１３２】
前記別データを読み出す場合は、前記埋め込み地点に関して地点データの予め設定された桁の値の奇数あるいは偶数の判定を行うことにより前記別データを読み出す。また、１つの線形状を指定する複数の２次元地点の中の地点Ｐ（ｊ）を所定距離以下移動させる場合、前記所定距離が２次元座標上の水平方向ならびに垂直方向の最小単位であるようにしてもよい。これにより地図の変更を最小限に留めることができる。
【０１３３】
なお、本発明を上記の実施の形態に基づいて説明してきたが、本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
（１）上記の実施の形態では、地図情報に他の情報を埋め込むとしているが、地図情報に限定されない。空間上における複数の点の座標と、各点を結ぶ命令とからなるコンピュータグラフィクスなどの図形情報においても同様に適用できる。
【０１３４】
（２）上記の実施の形態では、２次元空間上の図形情報に適用しているが、３次元空間上の図形に適用してもよい。
（３）上記の実施の形態において、座標値の最下位桁に１を加えるようにしているが、座標値の最下位桁から１を引くとしてもよい。
また、各座標系における最小の単位を加えたり、引いたりしてもよい。
【０１３５】
（４）暗号化部１４は、上記に示すようにして、暗号鍵Ｋを用いて、埋込情報記憶Ｆを暗号化して暗号化埋込情報Ｇを生成するとしているが、暗号化アルゴリズムとして、ＤＥＳやＲＳＡなどの他の暗号アルゴリズムを用いてるとしてもよい。また、暗号データ作成に関しても、数式と数値の四捨五入という考え方を利用したが、数値を０あるいは１に変換するテーブル等を用いて暗号データ配列を作成しても問題はない。
【０１３６】
（５）上記の実施の形態において、埋め込む対象として地点座標の最少桁としたが、見た目に問題なければ、最少桁より上位の桁であっても構わない。
（６）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
【０１３７】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フロッピーディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。
【０１３８】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク等を経由して伝送するものとしてもよい。
また、本発明は、マイクロプロセッサとメモリとを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムに従って動作するとしてもよい。
【０１３９】
また、前記プログラム又は前記デジタル信号を前記記録媒体に記録して移送することにより、又は前記プログラム又は前記デジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
（７）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
【０１４０】
【発明の効果】
以上説明したように、本発明は、空間上において１個の点と他の点とが線で結ばれて表現される図形を示す図形情報に他の情報を埋め込む情報埋込装置であって、空間上における複数の点をそれぞれ示す位置情報を含む図形情報を記憶している図形情報記憶手段と、埋込対象となる埋込情報を記憶している埋込情報記憶手段と、前記埋込情報を読み出す読出手段と、読み出した前記埋込情報を前記図形情報に含まれる位置情報の下位桁に埋め込む情報埋込手段とを備える。
【０１４１】
この構成によると、埋込情報を図形情報に含まれる位置情報の下位桁に埋め込むので、図形情報を見た目に分からないように変えて、他の情報を埋め込むことができる。
また、本発明は、空間上において１個の点と他の点とが線で結ばれて表現される図形を示す図形情報に他の情報を埋め込む情報埋込装置であって、空間上における複数の点をそれぞれ示す位置情報を含む図形情報を記憶している図形情報記憶手段と、埋込対象となる埋込情報を記憶している埋込情報記憶手段と、前記埋込情報を複数桁のｎ（ｎは、正整数、ｎ＞１）進数で表現するときに、前記複数桁のうちの１個の桁が示す値を埋込値として抽出する抽出手段と、前記複数の点から１個の点を選択する点選択手段と、選択された前記点を示す位置情報を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの下位の特定の１個の桁を対象桁として選択する桁選択手段と、抽出した前記埋込値に基づいて、前記対象桁が示す値を更新する更新手段とを備える。
【０１４２】
この構成によると、埋込情報を複数桁のｎ（ｎは、正整数、ｎ＞１）進数で表現するときにおける、前記複数桁のうちの１個の桁が示す埋込値に基づいて、選択された前記点を示す位置情報を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときにおける、前記複数桁のうちの下位の特定の１個の桁が示す値を更新するので、図形情報を見た目に分からないように変えて、また、埋込情報の一部を一部の位置情報に確実に埋め込むことができる。
【０１４３】
ここで、前記桁選択手段は、前記複数の桁のうちの最下位桁を対象桁として選択し、前記更新手段は、前記最下位桁が示す値を更新するように構成してもよい。
この構成によると、位置情報を構成する複数の桁のうちの最下位桁が示す値を更新するので、埋込情報を図形情報に埋め込む際に、図形情報が変形する度合いを最小限とすることができる。
【０１４４】
ここで、ｎ＝ｍであり、前記更新手段は、抽出した前記埋込値を選択された前記対象桁が示す値に上書きすることにより、前記対象桁が示す値を更新するように構成してもよい。
この構成によると、ｎ＝ｍであり、抽出した埋込値を選択された対象桁が示す値に上書きすることにより、前記対象桁が示す値を更新するので、単純な操作により他の情報を図形情報に埋め込むことができる。
【０１４５】
ここで、ｎ＜ｍであり、前記更新手段は、抽出した前記埋込値に、所定の変換アルゴリズムを施して変換値を生成し、生成した変換値を選択された前記対象桁が示す値に上書きし、前記所定の変換アルゴリズムは、ｎ種の数字をｍ種の数字のいずれかに変換し、逆変換アルゴリズムにより、変換された数字から元の数字が生成されるように構成してもよい。
【０１４６】
この構成によると、ｎ＜ｍであり、抽出した前記埋込値に、所定の変換アルゴリズムを施して変換値を生成し、生成した変換値を選択された前記対象桁が示す値に上書きするので、空間上の点を示す位置情報をｎより大きいｍ進数で表現できる。これにより、位置情報の表現方法を多様にできる。
ここで、前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、前記図形情報記憶手段は、少なくとも前記３個の点をそれぞれ示す位置情報を含み、前記点選択手段は、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択するように構成してもよい。
【０１４７】
この構成によると、前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択するので、第２の点に埋込情報を埋め込むことにより、図形情報を見た目に分からないように変えることができる。
【０１４８】
ここで、前記空間は、２次元空間であり、前記空間の座標系は、直交するＸ座標軸とＹ座標軸とから構成され、前記更新手段は、前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度に応じて、前記対象桁が示す値を更新するように構成してもよい。
この構成によると、前記空間は、２次元空間であり、前記空間の座標系は、直交するＸ座標軸とＹ座標軸とから構成され、前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度に応じて、前記対象桁が示す値を更新するので、図形情報を見た目に分からないように変えることができる。
【０１４９】
ここで、各点を示す位置情報は、前記座標系において、当該点を示すＸ座標値とＹ座標値とを含み、前記桁選択手段は、前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度αを算出する算出手段と、算出された前記角度αが（ａ）−２２．５°≦角度α＜２２．５°又は１５７．５°≦角度α＜２０２．５°の第１の範囲、（ｂ）２２．５°≦角度α＜６７．５°、１１２．５°≦角度α＜１５７．５°、２０２．５°≦角度α＜２４７．５°又は２９２．５°≦角度α＜３３７．５°の第２の範囲、又は（ｃ）６７．５°≦角度α＜１１２．５°又は２４７．５°≦角度α＜２９２．５°の第３の範囲のいずれの範囲内に入るかを判断する判断手段と、第１の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択し、第２の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値及びＹ座標値をそれぞれ複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択し、第３の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＹ座標値を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択する副桁選択手段とを含むように構成してもよい。
【０１５０】
この構成によると、第１の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値を更新し、第２の範囲に入ると判断される場合に、Ｘ座標値及びＹ座標値を更新し、第３の範囲に入ると判断される場合に、Ｙ座標値を更新するので、図形情報を見た目に分からないように変えることができる。特に、データ埋め込みによる形状変化に関して、出来るだけ突起やへこみを無くすということができる。
【０１５１】
また、本発明は、空間上において１個の点と他の点とが線で結ばれて表現される図形を示す図形情報から埋め込まれた埋込情報を抽出する情報抽出装置であって、前記情報埋込装置により埋込情報が埋め込まれた図形情報を記憶している図形情報記憶手段と、前記図形情報記憶手段に記憶されている図形情報を読み出す読出手段と、読み出した前記図形情報から埋込情報を抽出する抽出手段とを備える。
【０１５２】
この構成によると、前記情報埋込装置により埋込情報が埋め込まれた図形情報から埋込情報を抽出することができる。
また、本発明は、この構成によると、前記情報埋込装置により埋込情報が埋め込まれた図形情報から埋込情報を確実に抽出することができる。
ここで、前記桁選択手段は、前記複数の桁のうちの最下位桁を対象桁として選択し、前記値抽出手段は、前記最下位桁が示す値を埋込値として抽出するように構成してもよい。
【０１５３】
この構成によると、複数桁のうちの最下位桁を対象桁として選択するので、確実に埋込値を抽出することができる。
ここで、ｎ＝ｍであり、前記値生成手段は、前記埋込値を前記抽出値として生成するように構成してもよい。
この構成によると、単純な構成により容易に埋込値を抽出できる。
【０１５４】
ここで、ｎ＜ｍであり、前記値生成手段は、抽出した前記埋込値に、請求項５に記載の逆変換アルゴリズムを施して埋込値を生成するように構成してもよい。この構成によると、多様に表現された位置情報から埋込値を確実に抽出できる。
ここで、前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、前記図形情報記憶手段は、少なくとも３個の点をそれぞれ示す位置情報を含み、前記点選択手段は、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択するように構成してもよい。
【０１５５】
この構成によると、前記空間上において少なくとも３個の点が存在し、第１の点と第２の点とが線で結ばれ、第２の点と第３の点とが線で結ばれて図形が表現されており、前記第１の点と前記第２の点との距離が所定値Ｒ以上であり、前記第２の点と前記第３の点との距離が所定値Ｒ以上である場合に、前記複数の点から前記１個の点として前記第２の点を選択するので、第２の点から埋込情報を抽出することにより、確実に埋込情報を抽出することができる。
【０１５６】
ここで、前記空間は、２次元空間であり、前記空間の座標系は、直交するＸ座標軸とＹ座標軸とから構成され、前記値抽出手段は、前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度に応じて、前記抽出値を生成するように構成してもよい。
この構成によると、前記空間は、２次元空間であり、前記空間の座標系は、直交するＸ座標軸とＹ座標軸とから構成され、前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度に応じて、埋込値を抽出するので、確実に埋込情報を抽出することができる。
【０１５７】
ここで、各点を示す位置情報は、前記座標系において、当該点を示すＸ座標値とＹ座標値とを含み、前記桁選択手段は、前記第１の点及び前記第３の点を結ぶ線と、前記Ｘ座標軸とがなす角度αを算出する算出手段と、算出された前記角度αが（ａ）−２２．５°≦角度α＜２２．５°又は１５７．５°≦角度α＜２０２．５°の第１の範囲、（ｂ）２２．５°≦角度α＜６７．５°、１１２．５°≦角度α＜１５７．５°、２０２．５°≦角度α＜２４７．５°又は２９２．５°≦角度α＜３３７．５°の第２の範囲、又は（ｃ）６７．５°≦角度α＜１１２．５°又は２４７．５°≦角度α＜２９２．５°の第３の範囲のいずれの範囲内に入るかを判断する判断手段と、第１の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択し、第２の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値及びＹ座標値をそれぞれ複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択し、第３の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＹ座標値を複数桁のｍ（ｍは、正整数、ｍ＞１）進数で表現するときに、前記複数桁のうちの特定の１個の桁を対象桁として選択する副桁選択手段とを含むように構成してもよい。
【０１５８】
この構成によると、第１の範囲に入ると判断される場合に、選択された前記点を示す位置情報に含まれるＸ座標値から埋込値を抽出し、第２の範囲に入ると判断される場合に、Ｘ座標値及びＹ座標値から埋込値を抽出し、第３の範囲に入ると判断される場合に、Ｙ座標値から埋込値を抽出するので、確実に埋込情報を抽出することができる。
【図面の簡単な説明】
【図１】情報埋込装置１の構成を示すブロック図である。
【図２】元地図情報のデータ構造の一例を示す。
【図３】元地図情報に基づいて描いた地図の一例である。
【図４】暗号化埋込情報Ｇのデータ構造の一例を示す。
【図５】情報埋込装置１により地図情報に他の情報を埋め込むための規則を示す表である。
【図６】埋込情報が埋め込まれた埋込地図情報のデータ構造の一例を示す。
【図７】情報埋込装置１の全体の概要動作を示すフローチャートである。
【図８】暗号化部１４の動作を示すフローチャートである。
【図９】暗号演算列Ｅの生成動作の詳細を示すフローチャートである。
【図１０】情報埋込部１８の動作を示すフローチャートである。
【図１１】情報抽出装置２の構成を示すブロック図である。
【図１２】情報抽出装置２の全体の概要動作を示すフローチャートである。
【図１３】情報抽出部２２の動作を示すフローチャートである。
【図１４】復号部２５の動作を示すフローチャートである。
【図１５】第２の変形例における地図情報、埋込情報、埋込地図情報の一例を示す。
【図１６】情報埋込部１８の動作を示すフローチャートである。
【図１７】情報抽出部２２の動作を示すフローチャートである。
【図１８】（ａ）３個の位置情報ｐ（ｊ−１）、ｐ（ｊ）、ｐ（ｊ＋１）が配置される２次元空間を示す。
（ｂ）ｐ（ｊ）の移動方向を示す概念図である。
【図１９】２次元空間における領域Ｒ１、Ｒ２、Ｒ３を示す。
【図２０】情報埋込部１８による埋込処理の規則を示す。
（ａ）領域Ｒ１における規則を示す。
（ｂ）領域Ｒ２における規則を示す。
（Ｃ）領域Ｒ３における規則を示す。
【図２１】情報埋込部１８全体の概要動作を示すフローチャートである。
【図２２】情報埋込部１８における暗号化埋込情報Ｇ（ｉ）の埋込動作を示すフローチャートである。
【図２３】情報埋込部１８におけるＲ１領域の埋込動作を示すフローチャートである。
【図２４】情報埋込部１８におけるＲ２領域の埋込動作を示すフローチャートである。
【図２５】情報埋込部１８におけるＲ３領域の埋込動作を示すフローチャートである。
【図２６】情報抽出部２２の概要動作を示すフローチャートである。
【図２７】情報抽出部２２におけるｐ（ｊ）からの抽出処理動作を示すフローチャートである。
【図２８】情報抽出部２２におけるＲ１領域の抽出動作を示すフローチャートである。
【図２９】情報抽出部２２におけるＲ２領域の抽出動作を示すフローチャートである。
【図３０】情報抽出部２２におけるＲ３領域の抽出動作を示すフローチャートである。
【符号の説明】
１  情報埋込装置
１１  埋込情報入力部
１２  埋込情報記憶部
１３  暗号鍵入力部
１４  暗号化部
１５  暗号化埋込情報記憶部
１６  元地図情報記憶部
１７  読込部
１８  情報埋込部
１９  埋込地図記憶部
２  情報抽出装置
２１  埋込地図記憶部
２２  情報抽出部
２３  暗号化埋込情報記憶部
２４  暗号鍵入力部
２５  復号部
２６  埋込情報記憶部
【図１】
0003576107.tif 000002
【図２】
0003576107.tif 000003
【図３】
0003576107.tif 000004
【図４】
0003576107.tif 000005
【図５】
0003576107.tif 000006
【図６】
0003576107.tif 000007
【図７】
0003576107.tif 000008
【図８】
0003576107.tif 000009
【図９】
0003576107.tif 000010
【図１０】
0003576107.tif 000011
【図１１】
0003576107.tif 000012
【図１２】
0003576107.tif 000013
【図１３】
0003576107.tif 000014
【図１４】
0003576107.tif 000015
【図１５】
0003576107.tif 000016
【図１６】
0003576107.tif 000017
【図１７】
0003576107.tif 000018
【図１８】
0003576107.tif 000019
【図１９】
0003576107.tif 000020
【図２０】
0003576107.tif 000021
【図２１】
0003576107.tif 000022
【図２２】
0003576107.tif 000023
【図２３】
0003576107.tif 000024
【図２４】
0003576107.tif 000025
【図２５】
0003576107.tif 000026
【図２６】
0003576107.tif 000027
【図２７】
0003576107.tif 000028
【図２８】
0003576107.tif 000029
【図２９】
0003576107.tif 000030
【図３０】
0003576107.tif 000031