(57)【要約】【課題】電子透かしの形態で挿入されたデータが誤って検出されてしまう可能性を極力減らす。【解決手段】複数の情報シンボルを複数のグループに分割し、各グループに対しパリティを付加する第１パリティ付加ステップと、複数の情報シンボルを基に、これらの複数の情報シンボルを含むエラー訂正符号語を生成するエラー訂正符号語生成ステップを有し、情報シンボルを表す周波数成分であって、振幅が非ゼロであり、二次元周波数空間において同一円上に配置されるものの数を所定値とし、各パリティを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置し、エラー訂正符号語に含まれる各検査シンボルを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置する。【選択図】図６
2011120268.tif 000002
【特許請求の範囲】
【請求項１】
複数の情報シンボルを複数のグループに分割し、各グループに対し偶数パリティ又は奇数パリティを付加する第１パリティ付加ステップと、
前記複数の情報シンボルを基に、これらの複数の情報シンボルを含むエラー訂正符号語を生成するエラー訂正符号語生成ステップと、
を有し、
情報シンボルを表す周波数成分であって、振幅が非ゼロであり、二次元周波数空間において同一円上に配置されるものの数を所定値とし、各偶数パリティ又は各奇数パリティを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置し、前記エラー訂正符号語に含まれる各検査シンボルを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置することを特徴とする符号化方法。
【請求項２】
請求項１に記載の符号化方法において、
パリティとそれの基となる情報シンボルが、前記二次元周波数空間において、同一放射半直線上に並ばないようにしたことを特徴とする符号化方法。
【請求項３】
請求項１又は２に記載の符号化方法において、
パリティとそれの基となる情報シンボルが、前記二次元周波数空間において、所定数以上同一円周上に並ばないようにしたことを特徴とする符号化方法。
【請求項４】
請求項１乃至３の何れか１項に記載の情報シンボルの符号化方法により生成された符号語を復号する復号方法において、
前記偶数パリティ又は奇数パリティを用いてパリティチェックを行う第１エラー検出ステップと、
前記エラー訂正符号語を用いてエラー検出を行う第２エラー検出ステップと、
前記第１エラー検出ステップ、前記第２エラー検出ステップ又はその双方においてエラーが検出された場合に、
前記エラー訂正符号語を用いてエラー訂正を行うエラー訂正ステップと、
前記エラー訂正を行った後に、前記二次元周波数空間において、前記同一円上に配置される非ゼロの周波数成分の数が所定数であるか否かを検査する検査ステップと、
前記検査ステップで、前記同一円上に配置される非ゼロの周波数成分の数が所定数であることが確認された場合に、前記偶数パリティ又は奇数パリティを用いてパリティチェックを再度行う第３エラー検出ステップと、
前記第３エラー検出ステップにおいて、エラーが検出されない場合に、現在の情報シンボルを基にＩＤを検出するＩＤ検出ステップと、
を有することを特徴とする復号方法。
【請求項５】
複数の情報シンボルを複数のグループに分割し、各グループに対し偶数パリティ又は奇数パリティを付加する第１パリティ付加手段と、
前記複数の情報シンボルを基に、これらの複数の情報シンボルを含むエラー訂正符号語を生成するエラー訂正符号語生成手段と、
を備え、
情報シンボルを表す周波数成分であって、振幅が非ゼロであり、二次元周波数空間において同一円上に配置されるものの数を所定値とし、各偶数パリティ又は各奇数パリティを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置し、前記エラー訂正符号語に含まれる各検査シンボルを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置することを特徴とする符号化装置。
【請求項６】
請求項５に記載の符号化装置において、
パリティとそれの基となる情報シンボルが、前記二次元周波数空間において、同一放射半直線上に並ばないようにしたことを特徴とする符号化装置。
【請求項７】
請求項５又は６に記載の符号化装置において、
パリティとそれの基となる情報シンボルが、前記二次元周波数空間において、所定数以上同一円周上に並ばないようにしたことを特徴とする符号化装置。
【請求項８】
請求項５乃至７の何れか１項に記載の情報シンボルの符号化装置により生成された符号語を復号する復号装置において、
前記偶数パリティ又は奇数パリティを用いてパリティチェックを行う第１エラー検出手段と、
前記エラー訂正符号語を用いてエラー検出を行う第２エラー検出手段と、
前記第１エラー検出手段、前記第２エラー検出手段又はその双方においてエラーが検出された場合に、
前記エラー訂正符号語を用いてエラー訂正を行うエラー訂正手段と、
前記エラー訂正を行った後に、前記二次元周波数空間において、前記同一円上に配置される非ゼロの周波数成分の数が所定数であるか否かを検査する検査手段と、
前記検査手段で、前記同一円上に配置される非ゼロの周波数成分の数が所定数であることが確認された場合に、前記偶数パリティ又は奇数パリティを用いてパリティチェックを再度行う第３エラー検出手段と、
前記第３エラー検出手段において、エラーが検出されない場合に、現在の情報シンボルを基にＩＤを検出するＩＤ検出手段と、
を備えることを特徴とする復号装置。
【請求項９】
請求項１乃至４の何れか１項に記載の方法をコンピュータに行わせるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報シンボルの符号化方法及びその装置並びに情報シンボルの復号方法及び復号装置に関し、特に、二次元周波数空間に配置する情報シンボルを符号化するための符号化方法及びその装置並びに二次元周波数空間に配置された情報シンボルを復号するための復号方法及びその装置に関する。
【背景技術】
【０００２】
バーコードを印刷物やホームページに表示し、このバーコードをカメラで撮影し、撮影されたバーコードを基に、例えばＵＲＬ等のデータを得る方法が普及しているが、このような方法では、バーコードにより印刷物やホームページの体裁が下がってしまう。
【０００３】
このような問題を解決するために、画像にデータを表す電子透かしを挿入する方法が提案されている。この方法を利用すれば、撮影された画像からデータを得ることができるので、バーコードが不要となる。
【０００４】
このような方法に係る発明として、挿入装置は、拡大縮小率検出用パターン、回転角検出用パターン、候補位置のうち挿入データにより組み合わされる位置にデータパターンを設定し、全てのパターンを合わせて逆フーリエ変換し、原画像に変換により得た画像を加算し、検出装置は、画像をブロックに分割し、各ブロックのデータをフーリエ変換して各ブロックの各周波数成分の振幅を得て、各周波数成分の振幅をブロック間で加算して各周波数毎の総和振幅を得て、拡大縮小率検出用パターンで画像の拡大縮小率を検出し、回転角検出用パターンで画像の回転角を検出し、拡大縮小率及び回転角が補正された総和振幅で候補位置にあるもののうち相対的に大きな値を示す所定数の総和振幅の位置の組み合わせを基にデータを検出するような発明がある（例えば、特許文献１参照。）この発明は、特にカメラで画像を撮影した場合に、画像の縮尺が変化し、また、画像が回転してしまい、このためにデータを表す電子透かしを検出することができなくなってしまうという問題を解決するために、画像の拡大縮小率及び回転角度を検出するための電子透かしを画像に埋め込んでおくものである。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−１５３９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１に記載されている発明によれば、候補位置のうち挿入データにより組み合わされる位置にデータパターンを設定することにより、データが誤って検出される可能性を下げているが、これだけでは不十分である場合がある。例えば、誤ってデータが検出されると、ユーザに撮影した画像と全く関係がないコンテンツが提供されたりして、コンテンツ提供を運用する組織の信用が下がってしまう可能性がある。
【０００７】
そこで、本発明は、電子透かしの形態で挿入されたデータが誤って検出されてしまう可能性を極力減らすことを可能とする、情報シンボルの符号化方法及びその装置並びに情報シンボルの復号方法及び復号装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の第１の観点によれば、複数の情報シンボルを複数のグループに分割し、各グループに対し偶数パリティ又は奇数パリティを付加する第１パリティ付加ステップと、前記複数の情報シンボルを基に、これらの複数の情報シンボルを含むエラー訂正符号語を生成するエラー訂正符号語生成ステップと、を有し、情報シンボルを表す周波数成分であって、振幅が非ゼロであり、二次元周波数空間において同一円上に配置されるものの数を所定値とし、各偶数パリティ又は各奇数パリティを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置し、前記エラー訂正符号語に含まれる各検査シンボルを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置することを特徴とする符号化方法が提供される。
【０００９】
上記の符号化方法において、パリティとそれの基となる情報シンボルが、前記二次元周波数空間において、同一放射半直線上に並ばないようにしてもよい。
【００１０】
上記の符号化方法において、パリティとそれの基となる情報シンボルが、前記二次元周波数空間において、所定数以上同一円周上に並ばないようにしてもよい。
【００１１】
本発明の第２の観点によれば、上記の情報シンボルの符号化方法により生成された符号語を復号する復号方法において、前記偶数パリティ又は奇数パリティを用いてパリティチェックを行う第１エラー検出ステップと、前記エラー訂正符号語を用いてエラー検出を行う第２エラー検出ステップと、前記第１エラー検出ステップ、前記第２エラー検出ステップ又はその双方においてエラーが検出された場合に、前記エラー訂正符号語を用いてエラー訂正を行うエラー訂正ステップと、前記エラー訂正を行った後に、前記二次元周波数空間において、前記同一円上に配置される非ゼロの周波数成分の数が所定数であるか否かを検査する検査ステップと、前記検査ステップで、前記同一円上に配置される非ゼロの周波数成分の数が所定数であることが確認された場合に、前記偶数パリティ又は奇数パリティを用いてパリティチェックを再度行う第３エラー検出ステップと、前記第３エラー検出ステップにおいて、エラーが検出されない場合に、現在の情報シンボルを基にＩＤを検出するＩＤ検出ステップと、を有することを特徴とする復号方法が提供される。
【００１２】
本発明の第３の観点によれば、複数の情報シンボルを複数のグループに分割し、各グループに対し偶数パリティ又は奇数パリティを付加する第１パリティ付加手段と、前記複数の情報シンボルを基に、これらの複数の情報シンボルを含むエラー訂正符号語を生成するエラー訂正符号語生成手段と、を備え、情報シンボルを表す周波数成分であって、振幅が非ゼロであり、二次元周波数空間において同一円上に配置されるものの数を所定値とし、各偶数パリティ又は各奇数パリティを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置し、前記エラー訂正符号語に含まれる各検査シンボルを振幅がゼロである周波数成分と振幅が非ゼロである周波数成分との対で表し、この対を二次元周波数空間において同一円上に配置することを特徴とする符号化装置が提供される。
【００１３】
上記の符号化装置において、パリティとそれの基となる情報シンボルが、前記二次元周波数空間において、同一放射半直線上に並ばないようにしてもよい。
【００１４】
上記の符号化装置において、パリティとそれの基となる情報シンボルが、前記二次元周波数空間において、所定数以上同一円周上に並ばないようにしてもよい。
【００１５】
本発明の第４の観点によれば、上記の情報シンボルの符号化装置により生成された符号語を復号する復号装置において、前記偶数パリティ又は奇数パリティを用いてパリティチェックを行う第１エラー検出手段と、前記エラー訂正符号語を用いてエラー検出を行う第２エラー検出手段と、前記第１エラー検出手段、前記第２エラー検出手段又はその双方においてエラーが検出された場合に、前記エラー訂正符号語を用いてエラー訂正を行うエラー訂正手段と、前記エラー訂正を行った後に、前記二次元周波数空間において、前記同一円上に配置される非ゼロの周波数成分の数が所定数であるか否かを検査する検査手段と、前記検査手段で、前記同一円上に配置される非ゼロの周波数成分の数が所定数であることが確認された場合に、前記偶数パリティ又は奇数パリティを用いてパリティチェックを再度行う第３エラー検出手段と、前記第３エラー検出手段において、エラーが検出されない場合に、現在の情報シンボルを基にＩＤを検出するＩＤ検出手段と、を備えることを特徴とする復号装置が提供される。
【００１６】
本発明の第５の観点によれば、上記の方法をコンピュータに行わせるためのプログラムが提供される。
【発明の効果】
【００１７】
本発明によれば、電子透かしの形態で挿入されたデータが誤って検出されてしまう可能性を極力減らすことが可能となる。誤って検出される可能性がある程度ある場合には、検出エラーとする。そうすれば、ユーザは、再度画像の撮影からやり直しをすることができ、その結果、次回には正しくデータを検出することができる可能性が生じる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態１による電子透かしの周波数空間におけるパターンを示す図である。
【図２】本発明の実施形態による電子透かし挿入装置の構成を示すブロック図である。
【図３】本発明の実施形態による電子透かし検出装置の構成を示すブロック図である。
【図４】本発明の実施形態１による電子透かし検出方法を示すフローチャート（１／２）である。
【図５】本発明の実施形態１による電子透かし検出方法を示すフローチャート（２／２）である。
【図６】本発明の実施形態２による電子透かしの周波数空間におけるパターンを示す図である。
【図７】本発明の実施形態２による電子透かし検出方法を示すフローチャート（１／２）である。
【図８】本発明の実施形態２による電子透かし検出方法を示すフローチャート（２／２）である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明を実施するための最良の形態について詳細に説明する。
【００２０】
［実施形態１］
本実施形態では、電子透かし挿入装置は、原画像に、ＩＤに対応した電子透かしを挿入する。
【００２１】
ＩＤを表す情報ビットは、全部で２４ビットあるが、これは、Ａグループ、Ｂグループ及びＣグループに分割される。Ａグループの情報ビットの数は１１であり、Ｂグループの情報ビットの数は１１であり、Ｃグループの情報ビットの数は２である。１個の情報ビットには、周波数空間にある半円上の１個の点が対応する。半円上に１個の点があれば、空間周波数の性質上、原点を中心として点対称の位置にもう１個の点が存在するが、以下では、半円のみに着目して説明をする。
【００２２】
図１は、ＩＤに対応した電子透かしを周波数領域で見た図である。
【００２３】
図１において、三角で示す６個の点は、カメラ等で撮影された電子透かし入り画像の回転角度及び拡大縮小率を検出するための点である。撮影された画像は、フーリエ変換されるが、その後、これらの６個の点を利用して周波数領域にある点の位置の補正が行われる。すなわち、これらの６個の点を利用して、２次元周波数空間の回転角度及びスケールが補正される。
【００２４】
図１を参照すると、Ａグループの１１個の情報ビットに対応する点は１１個ある。これらの点は、円２の５個の点ａ１、ａ２、ａ３、ａ４、ａ５、円３の４個の点ａ６、ａ７、ａ８、ａ９及び円４の２個の点ａ１０、ａ１１である。
【００２５】
Ｂグループの１１個の情報ビットに対応する点は、１１個ある。これらの点は、円２の４個の点ｂ１、ｂ２、ｂ３、ｂ４、円３の３個の点ｂ５、ｂ６、ｂ７及び円４の４個の点ｂ８、ｂ９、ｂ１０、ｂ１１である。
【００２６】
Ｃグループの２個の情報ビットに対応する点は、２個ある。これらの点は、円２の１個の点ｃ１及び円３の１個の点ｃ２である。
【００２７】
また、円毎に点をみると、円２には、情報ビットに対応する点が１０個あり、円３には、情報ビットに対応する点が８個あり、円４には、情報ビットに対応する点が６個ある。
【００２８】
Ａグループの１１個の情報ビットに対しては、４個の検査ビットが付加さる。１１個の情報ビットと４個の検査ビットが１つのハミング符号語を構成し、これは１誤り訂正能力を有する。１個の情報ビットには、空間周波数にある半円上の１個の点が対応するのに対し、１個の検査ビットには、空間周波数にある半円上の２個の点が対応する。
【００２９】
Ａグループの４個の検査ビットに対応する点は８個（すなわち、４対）ある。これらの点は、円１の８個の点ａ１２−１、ａ１２−２、ａ１３−１、ａ１３−２、ａ１４−１、ａ１４−２、ａ１５−１、ａ１５−２である。ａ１２−１とａ１２−２が一対を成し、これらは相補的な値を取る。すなわち、片方が１であれば他方はゼロである。同様に、ａ１３−１とａ１３−２が一対を成し、ａ１４−１とａ１４−２が一対を成し、ａ１５−１とａ１５−２が一対を成す。
【００３０】
ＢグループについてもＡグループについてと同様であり、Ｂグループの４個の検査ビットに対応する点は８個（すなわち、４対）ある。これらの点は、円１の８個の点ｂ１２−１、ｂ１２−２、ｂ１３−１、ｂ１３−２、ｂ１４−１、ｂ１４−２、ｂ１５−１、ｂ１５−２である。ｂ１２−１とｂ１２−２が一対を成し、ｂ１３−１とｂ１３−２が一対を成し、ｂ１４−１とｂ１４−２が一対を成し、ｂ１５−１とｂ１５−２が一対を成す。
【００３１】
Ｃグループの２個の情報ビットに対しては、ハミング符号語を構成するための検査ビットが付加されない。従って、Ｃグループの２個の情報ビットに対し、ハミング符号語を用いたエラー訂正が行われることはない。
【００３２】
その代わりに、Ｃグループの２個の情報ビットに対し１個のパリティが付加される。また、１個のパリティに対応する点は２個であり、これらは相補的な値を取る。すなわち、片方が１であれば他方はゼロである。これらの点は、円４の２個の点ｃ３−１、ｃ３−２である。
【００３３】
ハミング符号語を構成するためのパリティとは別に、Ａグループの１１個の情報ビット、Ｂグループの１１個の情報ビット、Ｃグループの２個の情報ビットに対し、６個の偶数パリティが付加される。但し、偶数パリティの代わりに奇数パリティを用いてもよい。パリティ計算の基とならない情報ビットはない。すなわち、Ａグループの１１個の情報ビット、Ｂグループの１１個の情報ビット、Ｃグループの２個の情報ビットの各々に対しては、少なくとも１つのパリティが付加される。従って、Ａグループの１１個の情報ビット、Ｂグループの１１個の情報ビット、Ｃグループの２個の情報ビットのうちの少なくとも１つの情報ビットにおいて誤りが発生しているならば、６個の偶数パリティそれぞれを用いた６個のパリティチェックのうちの少なくとも１つのパリティチェックにおいて誤りが検出されることとなる。
【００３４】
例えば、Ａ〜Ｃグループには、２４個の情報ビットがあるが、この２４個の情報ビットを４ビットずつ６分割し、各４ビットに対し１つの偶数パリティを設けるようにしてもよい。また、２４個の情報ビットを重複を排除せずにｎビット（ｎ＞４）ずつ６分割し、各ｎビットに対し１つの偶数パリティを設けるようにしてもよい。
【００３５】
６個の偶数パリティそれぞれに対しては２個の点が対応する。従って、６個の偶数パリティに対しては、合計で１２個の点が対応する。各パリティに対する２個の点は、相補的な値を取る。すなわち、片方が１であれば他方はゼロである。従って、６個の偶数パリティには、円２にある一対の点ｄ１、ｄ２、円２にある一対の点ｅ１、ｅ２、円２にある一対の点ｆ１、ｆ２、円３にある一対の点ｇ１、ｇ２、円３にある一対の点ｈ１、ｈ２及び円３にある一対の点ｉ１、ｉ２が対応する。
【００３６】
Ｃグループの２個の情報ビットに対する１個の偶数パリティ（この代わりに奇数パリティを用いてもよい。）及びＡ〜Ｃグループの２４（＝１１＋１１＋２）個の情報ビットに対する６個の偶数パリティを合わせると７個の偶数パリティが存在することとなるが、この７個の偶数パリティに対して、１個の偶数パリティ（この代わりに奇数パリティを用いてもよい。）が付加される。この偶数パリティに対しては２個の点が対応する。これらは相補的な値を取る。すなわち、片方が１であれば他方はゼロである。７個の偶数パリティに対して付加される偶数パリティ（すなわち、偶数パリティに対して付される偶数パリティ）に対応する点は、一対の点ｊ１、ｊ２である。
【００３７】
次に、原画像に対し、ＩＤに対応する電子透かしを挿入する電子透かし挿入装置について図２を参照して説明する。なお、図２に示す電子透かし挿入装置は、ハードウェア、ソフトウェア又はそれらの組合せにより構成することができる。
【００３８】
図２を参照すると、ＩＤ入力部１１は、ＩＤを入力する。ＩＤは、例えば、ＵＲＬに対応したり、関連画像の識別情報を表したりする。
【００３９】
情報点生成部１３は、ＩＤを基に情報点を生成する。上述したように、円２に１０個の情報点、円３に８個の情報点、円４に６個の情報点が在り、各円において、データ値がゼロである点の数とデータ値が１である点の数が等しくなるようにしている。従って、情報点によって表すことができるＩＤは、１０Ｃ５×８Ｃ４×６Ｃ３＝３５２８００通りである。
【００４０】
また、回転角度と拡大縮小率を検出するための点は円１に２個、円４に２個、円５に２個あり、各円において片方の点のデータ値が１であれば、他方の点のデータ値はゼロである。更に、パリティに対応する一対の点は、同一円に存在し、片方の点のデータ値が１であれば、他方の点のデータ値はゼロである。従って、各円に存在するデータ値が１である点の数が定まっている。具体的には、円１に存在するデータ値が１である点の数は９であり、円２に存在するデータ値が１である点の数は９であり、円３に存在するデータ値が１である点の数は７であり、円４に存在するデータ値が１である点の数は５であり、円５に存在するデータ値が１である点の数は１である。このように、データ値が１である点の数が各円において定まっているため、それだけでもエラーに対して強くなっている。なお、データ値が１である点には、所定値の振幅の周波数成分が加算される。
【００４１】
ハミング符号パリティ生成部１５は、グループＡの１１個の情報点に対してハミング符号語の生成式に従って、４個のパリティを生成し、同様に、グループＢの１１個の情報点に対してハミング符号語の生成式に従って、４個のパリティを生成する。
【００４２】
ハミング符号パリティ点生成部１７は、ハミング符号パリティ生成部１５により生成された８個のパリティに従って、これらを表す１６個の点ａ１２−１、ａ１２−２、・・・、ａ１５−１、ａ１５−２、ｂ１２−１、ｂ１２−２、・・・、ｂ１５−１、ｂ１５−２を生成する。
【００４３】
偶数パリティ生成部１９は、Ａ〜Ｃグループに属する２４個の情報点を基に、所定のパリティ生成式に従って、６個のパリティを生成する。また、Ｃグループに属する２個の情報点に対するパリティも生成する。更に、これらの合わせて７個のパリティについてのパリティも生成する。従って、合わせて８個のパリティを生成する。
【００４４】
偶数パリティ点生成部２１は、偶数パリティ生成部１９が生成した８個のパリティに対応した１６個のパリティ点ｃ３−１、ｃ３−２、ｄ１、ｄ２、ｅ１、ｅ２、・・・、ｊ１、ｊ２を生成する。
【００４５】
合成部２３は、情報点生成部１３が生成した情報点、ハミング符号パリティ点生成部１７が生成したパリティ点及び偶数パリティ生成部２１が生成したパリティ点を合成する。具体的には、２次元周波数空間においてデータ値が１である点に所定のレベルの周波数成分を配置する。
【００４６】
逆フーリエ変換部２５は、合成部２３の出力を逆フーリエ変換する。逆フーリエ変換における点の数は、原画像の点の数と等しくてもよいが、原画像よりも少なくして、同一パターンが連続するようにしてもよい。例えば、原画像のサイズが２０４８×２０４８であれば、逆フーリエ変換のサイズを２０４８×２０４８としてもよいが、例えば、１２８×１２８として、１２８×１２８のパターンが縦横に１６個ずつ連続して、２０４８×２０４８の領域を覆うようにしてもよい。
【００４７】
加算部２９は、画像入力部２７が入力した原画像に対して、逆フーリエ変換部２５からの出力を加算して、電子透かし入り画像を生成する。
【００４８】
次に、誤りの検出及び訂正の方法について図３、図４及び図５を参照して説明する。なお、図３に示す電子透かし検出装置は、ハードウェア、ソフトウェア又はそれらの組合せにより構成することができる。
【００４９】
まず、フーリエ変換部５１は、読み取った画像をフーリエ変換する（ステップＳ１０１）。次に、絶対値算出部５３は、各周波数成分の絶対値を求める（ステップＳ１０３）。次に、補正部５５は、回転角度検出用の点及び拡大縮小率検出用の点を用いて、回転角度及びスケールを補正する（ステップＳ１０５）。
【００５０】
次に、点検出部５７は、各点の値がゼロであるか１であるかを検出する（ステップＳ１０７）。この検出のためには、閾値以上となるレベルの信号が埋め込まれている可能性がある点（データ値が１である可能性がある点）に窓を設け、窓を通過した周波数成分のうち絶対値レベルが閾値以上である点のうちレベルが高い順の所定数の点の値が１であるとする。窓を通過した周波数成分のうち絶対値レベルが閾値以上である点の数が所定数に達しない場合には、閾値を下げて、窓を通過した周波数成分のうち絶対値レベルが閾値以上である点の数が所定数に達するようにするが、或る程度まで下げても窓を通過した周波数成分のうち絶対値レベルが閾値以上である点の数が所定数に達しない場合には、制御部６７は、エラーフラグを立ててエラー終了する。
【００５１】
図１の例でいえば、円１にある情報点の数がゼロであり、パリティ点の数が１６であり、回転角度・拡大縮小率検出用の点の数が２であるが、パリティ点のうち８個の点が閾値以上となるレベルの信号が埋め込まれている点であり、回転角度・拡大縮小率検出用の点のうち１個の点が閾値以上となるレベルの信号が埋め込まれている点であるため、合わせて９個の点を検出することとなる。例えば、窓を通過した点のうち絶対値レベルが閾値以上である点の数が１１個であれば、絶対値レベルが高い順の９個の点に１が埋め込まれているとする。
【００５２】
同様に、円２にある情報点の数が１０であり、パリティ点の数が８であり、回転角度・拡大縮小率検出用の点の数がゼロであるが、情報点のうち５個の点が閾値以上となるレベルの信号が埋め込まれている点であり、パリティ点のうち４個の点が閾値以上となるレベルの信号が埋め込まれている点であるため、合わせて９個の点を検出することとなる。例えば、窓を通過した点のうち絶対値レベルが閾値以上である点の数が１１個であれば、絶対値レベルが高い順の９個の点に１が埋め込まれているとする。
【００５３】
同様に、円３にある情報点の数が８であり、パリティ点の数が６であり、回転角度・拡大縮小率検出用の点の数がゼロであるが、情報点のうち４個の点が閾値以上となるレベルの信号が埋め込まれている点であり、パリティ点のうち３個の点が閾値以上となるレベルの信号が埋め込まれている点であるため、合わせて７個の点を検出することとなる。例えば、窓を通過した点のうち絶対値レベルが閾値以上である点の数が１０個であれば、絶対値レベルが高い順の７個の点に１が埋め込まれているとする。
【００５４】
同様に、円４にある情報点の数が６であり、パリティ点の数が２であり、回転角度・拡大縮小率検出用の点の数が２であるが、情報点のうち３個の点が閾値以上となるレベルの信号が埋め込まれている点であり、パリティ点のうち１個の点が閾値以上となるレベルの信号が埋め込まれている点であり、回転角度・拡大縮小率検出用の点のうち１個の点が閾値以上となるレベルの信号が埋め込まれている点であるため、合わせて５個の点を検出することとなる。例えば、窓を通過した点のうち絶対値レベルが閾値以上である点の数が６個であれば、絶対値レベルが高い順に５個の点に１が埋め込まれているとする。
【００５５】
図４に戻り、上述したように、各点の値が検出できなかった場合には（ステップＳ１０９でＮＯ）、制御部６７は、エラーフラグを立ててエラー終了する。各点の値が検出できない場合とは、例えば、閾値を或る程度まで下げても、閾値以上となる所定数の点が検出できない場合である。
【００５６】
次に、パリティチェック部５９は、データに付加された偶数パリティを用いた、合わせて６個のパリティチェック（点ｄ１、ｄ２に対応するパリティを用いたパリティチェック、点ｅ１、ｅ２に対応するパリティを用いたパリティチェック、点ｆ１、ｆ２に対応するパリティを用いたパリティチェック、点ｇ１、ｇ２に対応するパリティを用いたパリティチェック、点ｈ１、ｈ２に対応するパリティを用いたパリティチェック、点ｉ１、ｉ２に対応するパリティを用いたパリティチェック）を行う（ステップＳ１１１）。
【００５７】
全てのパリティチェックにおいて、パリティエラーが検出されなければ（ステップＳ１１３でＹＥＳ）、全てのデータ点に誤りが含まれていない可能性が非常に高いため、ＩＤ検出部６５は、直ちに、ＩＤの検出を行う（ステップＳ１１５）。
【００５８】
ここでＩＤの検出とは、各円毎の値が１であるデータ点の位置の組合せに基づいたＩＤの検出のことである。図１の例では、円２にはデータ点が１０個あり、円３にはデータ点が８個あり、円４にはデータ点が６個あり、それぞれの円において値が１である点の数と値がゼロである点の数は半々であるため、１０Ｃ５×８Ｃ４×６Ｃ３＝３５２８００通りのＩＤのうちの１つのＩＤを検出する。
【００５９】
他方、少なくとも１つのパリティチェックにおいて、パリティエラーが検出されたならば（ステップＳ１１３でＮＯ）、何れかのデータ点に誤りが含まれている可能性もあるが、パリティ自体に誤りが含まれている可能性もある。
【００６０】
そのため、この場合には、パリティ自体に誤りが含まれているかどうかを確認するために、パリティチェック部５９は、パリティに付加されたパリティを用いたパリティチェック（点ｄ１、ｄ２に対応するパリティ、点ｅ１、ｅ２に対応するパリティ、点ｆ１、ｆ２に対応するパリティ、点ｇ１、ｇ２に対応するパリティ、点ｈ１、ｈ２に対応するパリティ、点ｉ１、ｉ２に対応するパリティに対して付加されたパリティ（点ｊ１、ｊ２がこれに対応する）を用いたパリティチェック）をおこなう（ステップＳ１１７）。
【００６１】
パリティに付加されたパリティを用いたパリティチェックでエラーが検出された場合には（ステップＳ１１９でＮＯ）、データに付加されたパリティに誤りがある可能性がある。すなわち、データに誤りが含まれていることがステップＳ１１１、Ｓ１１３で確認できたが、これからハミング符号語等による誤り訂正をしても、その後に、誤り訂正が正しく行えたか否かをパリティを用いて検出すること（ステップＳ１３３）ができない。従って、この場合には、制御部６７は、エラーフラグを立ててエラー終了する。
【００６２】
このようにして、エラー訂正できたとしても、それが誤訂正である確率を低くしている。これは、誤訂正して誤ったＩＤを検出してしまうと、誤ったコンテンツなどをユーザに提供することとなるが、これが致命的となるからである。他方、エラー終了して、ユーザにそれを知らせれば、ユーザは再度画像の撮影を試みて、その後正しくＩＤを検出することができる可能性が残される。従って、ステップＳ１１９でＮＯであれば、エラー終了して、誤訂正が検出できない事態を避けることとしている。
【００６３】
パリティに付加されたパリティを用いたパリティチェックでエラーが検出されなかった場合には（ステップＳ１１９でＹＥＳ）、エラー訂正部６１は、Ａグループ及びＢグループでハミング符号語を用いたエラー訂正を試みる（ステップＳ１２１）。
【００６４】
Ａグループ、Ｂグループ又はその双方でハミング符号語を用いた誤り訂正ができなかった場合には（具体的には、本例では、ハミング符号語を用いた誤り訂正では１誤り訂正のみしかできないので、２誤りが検出された場合には）（ステップＳ１２３でＮＯ）、制御部６７は、エラーフラグを立ててエラー終了する。本例では、Ａグループで２誤り検出された場合、Ｂグループで２誤り検出された場合又は双方のグループで２誤り検出された場合には、エラー終了する。
【００６５】
ステップＳ１２３でＹＥＳである場合とは、Ａグループ及びＢグループそれぞれにおける誤りの数が１以下であり、ステップＳ１２３を経た後には、Ａグループ及びＢグループの双方に誤りが残っていない場合である。
【００６６】
しかし、まだ、Ｃグループについては、誤りが残っている可能性がある。また、ステップＳ１２１で誤訂正がされた可能性が僅かながらもある。そこで、各円において、値が１のデータが埋め込まれているデータ点の数が正しいか否かをみる（ステップＳ１２５）。本例では、円２において値が１となったデータ点の数が５であり、円３において値が１となったデータ点の数が４であり、円４において値が１となったデータ点の数が３であるか否かを確認する。
【００６７】
ステップＳ１２５での判断が否定的である場合には、Ｃグループのデータ値に誤りがある可能性がある。そこで、Ｃグループに属する点のうちステップＳ１２５での判断結果が否定的であった円に属する点のデータ値を反転し、その円において、値が１のデータが埋め込まれている点の数が正しくなったか否かをみる（ステップＳ１２７）。具体的には、円２についてステップＳ１２５での判断が否定的であれば、点Ｃ１のデータ値を反転してみて、円２において、値が１のデータが埋め込まれている点の数が正しくなったか否かをみる。円３についてステップＳ１２５での判断が否定的であれば、点Ｃ２のデータ値を反転してみて、円３において、値が１のデータが埋め込まれている点の数が正しくなったか否かをみる。円２及び円３についてステップＳ１２５での判断が否定的であれば、円２及び円３の双方についてこの操作と判断を行う。
【００６８】
反転してみて、正しくならなかった円があるならば（ステップＳ１２７でＮＯ）、ステップＳ１２５での判断が否定的となった原因はグループＣのデータ値に誤りがあることではなく、グループＡ、グループＢ又はその双方に誤りが残っていることを意味するので、制御部６７は、エラーフラグを立ててエラー終了する。
【００６９】
反転してみて、正しくなったならば（ステップＳ１２７でＹＥＳ）、ステップＳ１２５での判断が否定的となった原因はグループＣのデータ値に誤りがあることである可能性が極めて高い。そこで、そうである場合には、Ｃグループにおいて、反転後のデータ値を用いてパリティチェックを行う（ステップＳ１２９）。
【００７０】
ステップＳ１２９でのパリティチェックの結果が誤りであれば、ステップＳ１２５での判断が否定的となった原因はグループＣのデータ値に誤りがあることであると結論づけることができない。すなわち、グループＡやグループＢに誤りがある可能性がある。このため、ステップＳ１２９でのパリティチェックの結果に誤りがあれば（ステップＳ１３１でＮＯ）、制御部６７は、エラーフラグを立ててエラー終了する。
【００７１】
ステップＳ１２９でのパリティチェックの結果が正しければ（ステップＳ１３１でＹＥＳ）、ステップＳ１２５での判断結果が否定的となった原因はグループＣのデータ値に誤りがあることであるとほぼ確定できる。そこで、再度、ステップＳ１１１と同様なパリティチェックを行い（ステップＳ１３３）、パリティエラーがなければ、ＩＤの検出を行う（ステップＳ１１５）。
【００７２】
また、ステップＳ１２５での判断結果が肯定的である場合には、ステップＳ１２１で、ハミング符号語を用いた誤り訂正が正しく行われた可能性が高いため、再度、ステップＳ１１１と同様なパリティチェックを行い（ステップＳ１３３）、パリティエラーがなければ、ＩＤの検出を行う（ステップＳ１１５）。
【００７３】
［実施形態２］
実施形態１における電子透かしの周波数空間における分布は図１に示すようなものであるが、実施形態２における電子透かしの周波数空間における分布は図６に示すようなものである。
【００７４】
実施形態１では、２４個の情報ビットを１１個の情報ビットより構成されるＡグループ、１１個の情報ビットより構成されるＢグループ及び２個の情報ビットより構成されるＣグループに分割した。これに対し、実施形態２では、２４個の情報ビットを４個の情報ビットより成るＡグループ、４個の情報ビットより成るＢグループ、４個の情報ビットより成るＣグループ、４個の情報ビットより成るＤグループ、４個の情報ビットより成るＥグループ及び４個の情報ビットより成るＦグループに分割する。
【００７５】
実施形態１では、Ａグループ及びＢグループのみに対しハミング符号語を構成するようにしたが、実施形態２では、Ａグループ乃至Ｆグループの全てに対してハミング符号語を構成するようにする。また、実施形態１では、１１個の情報ビットに対し４個の検査ビットを付加することによりハミング符号語を構成したが、実施形態２では、４個の情報ビットに対し３個の検査ビットを付加することによりハミング符号語を構成する。両方とも１誤り訂正能力を有するハミング符号語である。
【００７６】
具体的には、実施形態２では、Ａグループの４個の情報ビットに対し３個の検査ビットを付加することによりハミング符号語を構成する。Ｂグループ乃至Ｆグループに対しても同様である。
【００７７】
また、実施形態２では、実施形態１とは異なり、ハミング符号語から洩れる情報ビット（実施形態１でのＣグループに属するような情報ビット）は存在しない。
【００７８】
図６を参照すると、点ａ１〜ａ４は、グループＡに属する4個の情報ビットに対応する点である。また、実施形態１と同様に、１個の検査ビットに対しては一対の点が対応する。従って、Ａグループに属する３個の検査ビットに対応する点は６個あり、これらは、点ａ５−１、ａ５−２、ａ６−１、ａ６−２、ａ７−１、ａ７−２である。点ａ５−１と点ａ５ー２が一対となり、これが１つの検査ビットに対応する。点ａ５−１と点ａ５ー２の値は相補的である。すなわち、片方のデータ値が１であれば、他方のデータ値はゼロである。
【００７９】
グループＢ乃至グループＦについても、グループＡと同様である。従って、例えば、Ｂグループの情報ビットに対応する点はｂ１、ｂ２、ｂ３、ｂ４であり、Ｂグループの検査ビットに対応する点は、ｂ５−１、ｂ５−２、ｂ６−１、ｂ６−２、ｂ７−１、ｂ７−２である。ｂ５−１及びｂ５−２は対を成し１つの検査ビットに対応し、ｂ６−１及びｂ６−２は対を成し１つの検査ビットに対応し、ｂ７−１及びｂ７−２は対を成し１つの検査ビットに対応する。
【００８０】
次に、偶数パリティについて説明する。但し、上記と同様に偶数パリティの代わりに奇数パリティを用いてもよい。
【００８１】
偶数パリティは、合計で４個生成される。各偶数パリティは、６個の情報ビットに対して設けられる。従って、合計で、２４（＝４×６）個の情報ビット（ａ１〜ａ４、・・・、ｆ１〜ｆ４）を網羅し、偶数パリティが付けられない情報ビットは存在しないこととなる。また、偶数パリティは、別々のハミング符号語の構成要素である情報ビットに対して設けられる。すなわち、或る偶数パリティは、情報ビットａi、ｂj、ｃk、ｄl、ｅm、ｆn（ｉ、ｊ、ｋ、ｌ、ｍ、ｎは１乃至４の何れかの値）に対して設けられる。
【００８２】
また、１つの偶数パリティに対しては、一つの相補的な点が対応する。図６の例では、点ｉ１、ｉ２が第１の偶数パリティに対応し、点ｊ１、ｊ２が第２の偶数パリティに対応し、点ｋ１、ｋ２が第３の偶数パリティに対応し、点ｌ１、ｌ２が第４の偶数パリティに対応する。
【００８３】
第１の偶数パリティは、点ａ４、ｂ３、ｃ１、ｄ２、ｅ１、ｆ４に対応する情報ビットを基に算出される。
【００８４】
第２の偶数パリティは、点ａ３、ｂ４、ｃ２、ｄ１、ｅ４、ｆ１に対応する情報ビットを基に算出される。
【００８５】
第３の偶数パリティは、点ａ１、ｂ２、ｃ４、ｄ３、ｅ２、ｆ３に対応する情報ビットを基に算出される。
【００８６】
第４の偶数パリティは、点ａ２、ｂ１、ｃ３、ｄ４、ｅ３、ｆ２に対応する情報ビットを基に算出される。
【００８７】
また、点ａ１〜ａ４、ｂ１〜ｂ４、・・・、ｆ１〜ｆ４の分布からわかるように、それぞれの偶数パリティは、可能な限り異なった円にある点に対応する情報ビットを基に算出される。更に、点ａ１〜ａ４、ｂ１〜ｂ４、・・・、ｆ１〜ｆ４の分布からわかるように、それぞれの偶数パリティは、可能な限り異なった放射線にある点に対応する情報ビットを基に算出される。このような分布を用いることにより、撮影後の各偶数パリティの値に含まれるエラーができるかぎりランダムになるようにしている。例えば、同一放射線にある点に対応する情報ビットを基に偶数パリティを計算すると、２誤りのために、誤りが検出されない可能性が大きくなってしまうが、上述のような分布を選定することにより、２誤りのために誤りが検出されないことが生ずる可能性を低く抑えることができる。
【００８８】
図６において三角で表す点は、回転角度や拡大縮小を補正するための点であるが、この詳細についての説明は省略する。
【００８９】
次に、原画像に対し、ＩＤに対応する電子透かしを挿入する電子透かし挿入装置について図２を参照して説明する。
【００９０】
図２を参照すると、ＩＤ入力部１１は、ＩＤを入力する。ＩＤは、例えば、ＵＲＬに対応したり、関連画像の識別情報を表したりする。
【００９１】
情報点生成部１３は、ＩＤを基に情報点を生成する。円１に８個の情報点、円２に１０個の情報点、円３に６個の情報点が在り、各円において、データ値がゼロである点の数とデータ値が１である点の数が等しくなるようにしている。従って、情報点によって表すことができるＩＤは、８Ｃ４×１０Ｃ５×６Ｃ３＝３５２８００通りである。
【００９２】
また、回転角度と拡大縮小率を検出するための点は円１に２個あり、円３に２個あり、片方の点のデータ値が１であれば、他方の点のデータ値はゼロである。更に、パリティに対応する一対の点は、同一円に存在し、片方の点のデータ値が１であれば、他方の点のデータ値はゼロである。従って、各円に存在するデータ値が１である点の数が定まっている。具体的には、円１に存在するデータ値が１である点の数は１４であり、円２に存在するデータ値が１である点の数は１２であり、円３に存在するデータ値が１である点の数は１０である。このように、データ値が１である点の数が各円において定まっているため、それだけでもエラーに対して強くなっている。なお、データ値が１である点には、所定値の振幅の周波数成分が加算される。
【００９３】
ハミング符号パリティ生成部１５は、グループＡの４個の情報点に対してハミング符号語の生成式に従って、３個のパリティを生成し、同様に、グループＢ〜Ｆそれぞれの４個の情報点に対してハミング符号語の生成式に従って、３個のパリティを生成する。
【００９４】
ハミング符号パリティ点生成部１７は、ハミング符号パリティ生成部１５により生成された１８個のパリティに従って、これらを表す３６個の点ａ５−１、ａ５−２、ａ６−１、ａ６−２、ａ７−１、ａ７−２、・・・、ｆ５−１、ｆ５−２、ｆ６−１、ｆ６−２、ｆ７−１、ｆ７−２を生成する。
【００９５】
偶数パリティ生成部１９は、Ａ〜Ｆグループに属する２４個の情報点を基に、所定のパリティ生成式に従って、４個のパリティを生成する。
【００９６】
偶数パリティ点生成部２１は、偶数パリティ生成部１９が生成した４個のパリティに対応した８個のパリティ点ｉ１、ｉ２、ｊ１、ｊ２、ｋ１、ｋ２、ｌ１、ｌ２を生成する。
【００９７】
合成部２３は、情報点生成部１３が生成した情報点、ハミング符号パリティ点生成部１７が生成したパリティ点及び偶数パリティ生成部２１が生成したパリティ点を合成する。具体的には、２次元周波数空間においてデータ値が１である点に所定のレベルの周波数成分を配置する。
【００９８】
逆フーリエ変換部２５は、合成部２３の出力を逆フーリエ変換する。逆フーリエ変換における点の数は、原画像の点の数と等しくてもよいが、原画像よりも少なくして、同一パターンが連続するようにしてもよい。例えば、原画像のサイズが２０４８×２０４８であれば、逆フーリエ変換のサイズを２０４８×２０４８としてもよいが、例えば、１２８×１２８として、１２８×１２８のパターンが縦横に１６個ずつ連続して、２０４８×２０４８の領域を覆うようにしてもよい。
【００９９】
加算部２９は、画像入力部２７が入力した原画像に対して、逆フーリエ変換部２５からの出力を加算して、電子透かし入り画像を生成する。
【０１００】
次に、誤りの検出及び訂正の方法について図３、図７及び図８を参照して説明する。
【０１０１】
まず、フーリエ変換部５１は、読み取った画像をフーリエ変換する（ステップＳ２０１）。次に、絶対値算出部５３は、各周波数成分の絶対値を求める（ステップＳ２０３）。次に、補正部５５は、回転角度検出用の点及び拡大縮小率検出用の点を用いて、回転角度及びスケールを補正する（ステップＳ２０５）。
【０１０２】
次に、点検出部５７は、各点の値がゼロであるか１であるかを検出する（ステップＳ２０７）。この検出のためには、閾値以上となるレベルの信号が埋め込まれている可能性がある点（データ値が１である可能性がある点）に窓を設け、窓を通過した周波数成分のうち絶対値レベルが閾値以上である点のうちレベルが高い順の所定数の点の値が１であるとする。窓を通過した周波数成分のうち絶対値レベルが閾値以上である点の数が所定数に達しない場合には、閾値を下げて、窓を通過した周波数成分のうち絶対値レベルが閾値以上である点の数が所定数に達するようにするが、或る程度まで下げても窓を通過した周波数成分のうち絶対値レベルが閾値以上である点の数が所定数に達しない場合には、制御部６７は、エラーフラグを立ててエラー終了する。
【０１０３】
図６の例でいえば、円１にある情報点の数が８であり、パリティ点の数が１８であり、回転角度・拡大縮小率検出用の点の数が２であるが、情報点のうち４個の点が閾値以上となるレベルの信号が埋め込まれている点であり、パリティ点のうち９個の点が閾値以上となるレベルの信号が埋め込まれている点であり、回転角度・拡大縮小率検出用の点のうち１個の点が閾値以上となるレベルの信号が埋め込まれている点であるため、合わせて１４個の点を検出することとなる。例えば、窓を通過した点のうち絶対値レベルが閾値以上である点の数が１６個であれば、絶対値レベルが高い順の１４個の点に１が埋め込まれているとする。
【０１０４】
同様に、円２にある情報点の数が１０であり、パリティ点の数が１４であるが、情報点のうち５個の点が閾値以上となるレベルの信号が埋め込まれている点であり、パリティ点のうち７個の点が閾値以上となるレベルの信号が埋め込まれている点であるため、合わせて１２個の点を検出することとなる。例えば、窓を通過した点のうち絶対値レベルが閾値以上である点の数が１５個であれば、絶対値レベルが高い順の１２個の点に１が埋め込まれているとする。
【０１０５】
同様に、円３にある情報点の数が６であり、パリティ点の数が１２であり、回転角度・拡大縮小率検出用の点の数が２であるが、情報点のうち３個の点が閾値以上となるレベルの信号が埋め込まれている点であり、パリティ点のうち６個の点が閾値以上となるレベルの信号が埋め込まれている点であり、回転角度・拡大縮小率検出用の点のうち１個の点が閾値以上となるレベルの信号が埋め込まれている点であるため、合わせて１０個の点を検出することとなる。例えば、窓を通過した点のうち絶対値レベルが閾値以上である点の数が１２個であれば、絶対値レベルが高い順の１０個の点に１が埋め込まれているとする。
【０１０６】
図７に戻り、上述したように、各点の値が検出できなかった場合には（ステップＳ２０９でＮＯ）、制御部６７は、エラーフラグを立ててエラー終了する。各点の値が検出できない場合とは、例えば、閾値を或る程度まで下げても、閾値以上となる所定数の点が検出できない場合である。
【０１０７】
次に、パリティチェック部５９は、データに付加された偶数パリティを用いた、合わせて４個のパリティチェック（点ｉ１、ｉ２に対応するパリティを用いたパリティチェック、点ｊ１、ｊ２に対応するパリティを用いたパリティチェック、点ｋ１、ｋ２に対応するパリティを用いたパリティチェック、点ｌ１、ｌ２に対応するパリティを用いたパリティチェック）を行う（ステップＳ２１１）。
【０１０８】
何れかのパリティチェックにおいて、パリティエラーが検出されたならば（ステップＳ２１３でＮＯ）、ハミング符号語を用いたエラー訂正をするためにステップＳ２２１に進む。
【０１０９】
全てのパリティチェックにおいて、パリティエラーが検出されなければ（ステップＳ２１３でＹＥＳ）、ハミング符号語を用いたエラー検出を行う（ステップＳ２１５）。
【０１１０】
パリティを用いたエラー検出においても、ハミング符号語を用いたエラー検出においてもエラーが検出されない場合には（ステップＳ２１３でＹＥＳ、ステップＳ２１７でＹＥＳ）、全てのデータ点に誤りが含まれていない可能性が非常に高いため、ＩＤ検出部６５は、直ちに、ＩＤの検出を行う（ステップＳ２１９）。
【０１１１】
ここでＩＤの検出とは、各円毎の値が１であるデータ点の位置の組合せに基づいたＩＤの検出のことである。図６の例では、円１にはデータ点が８個あり、円２にはデータ点が１０個あり、円３にはデータ点が６個あり、それぞれの円において値が１である点の数と値がゼロである点の数は半々であるため、８Ｃ４×１０Ｃ５×６Ｃ３＝３５２８００通りのＩＤのうちの１つのＩＤを検出する。
【０１１２】
ハミング符号語を用いたエラー検出においてエラーが検出されたならば（ステップＳ２１７でＮＯ）、ハミング符号語を用いたエラー訂正をするためにステップＳ２２１に進む。
【０１１３】
ハミング符号語を用いたエラー訂正（ステップＳ２２１）においては、６個のハミング符号語のそれぞれについて１誤り訂正を試みる。
【０１１４】
いずれかのハミング符号語について、エラー訂正に失敗したならば（具体的には、本例では、ハミング符号語を用いた誤り訂正では１誤り訂正のみしかできないので、２誤りが検出された場合には）（ステップＳ２２３でＮＯ）、制御部６７は、エラーフラグを立ててエラー終了する。
【０１１５】
全てのハミング符号語について、エラー訂正に成功したならば、各円において、データ値が１である点の数が規定値通りであるか否かを調べる（ステップＳ２２５）。具体的には、円１については、全部で２８個の点のうちの１４個の点のデータ値が１であり、円２については、全部で２４個の点のうちの１２個の点のデータ値が１であり、円３については、全部で２０個の点のうちの１０個の点のデータ値が１であるか否かを調べる。
【０１１６】
ステップＳ２２５でのチェック結果が否定的であれば、誤訂正された可能性があるため、制御部６７は、エラーフラグを立ててエラー終了する。
【０１１７】
ステップＳ２２５でのチェック結果が肯定的であれば、再度、ステップＳ２１１と同様に、データに付加された偶数パリティを用いた、合わせて４個のパリティチェック（点ｉ１、ｉ２に対応するパリティを用いたパリティチェック、点ｊ１、ｊ２に対応するパリティを用いたパリティチェック、点ｋ１、ｋ２に対応するパリティを用いたパリティチェック、点ｌ１、ｌ２に対応するパリティを用いたパリティチェック）を行う（ステップＳ２２７）。
【０１１８】
何れかのパリティチェックにおいて、パリティエラーが検出されたならば（ステップＳ２２９でＮＯ）、誤訂正された可能性があるため、制御部６７は、エラーフラグを立ててエラー終了する。
【０１１９】
全てのパリティチェックにおいて、パリティエラーが検出されなければ（ステップＳ２２９でＹＥＳ）、正しく訂正されたと判断できるため、ステップＳ２１９に進み、ＩＤ検出部６５は、ＩＤの検出を行う。
【０１２０】
ステップＳ１２９でのパリティチェックの結果が誤りであれば、ステップＳ１２５での判断が否定的となった原因はグループＣのデータ値に誤りがあることであると結論づけることができない。すなわち、グループＡやグループＢに誤りがある可能性がある。このため、ステップＳ１２９でのパリティチェックの結果に誤りがあれば（ステップＳ１３１でＮＯ）、制御部６７は、エラーフラグを立ててエラー終了する。
【０１２１】
ステップＳ１２９でのパリティチェックの結果が正しければ（ステップＳ１３１でＹＥＳ）、ステップＳ１２５での判断結果が否定的となった原因はグループＣのデータ値に誤りがあることであるとほぼ確定できる。そこで、再度、ステップＳ１１１と同様なパリティチェックを行い（ステップＳ１３３）、パリティエラーがなければ、ＩＤの検出を行う（ステップＳ１１５）。
【０１２２】
また、ステップＳ１２５での判断結果が肯定的である場合には、ステップＳ１２１で、ハミング符号語を用いた誤り訂正が正しく行われた可能性が高いため、再度、ステップＳ１１１と同様なパリティチェックを行い（ステップＳ１３３）、パリティエラーがなければ、ＩＤの検出を行う（ステップＳ１１５）。
【０１２３】
［実施形態３］
実施形態１及び実施形態２では、２次元周波数空間に複数の円を設け、各円において、データ値が１となりうる点を所定数ｎだけ所定位置に定め、実際にデータ値が１となる点の数も所定数ｍ（＜ｎ）としていた。そして、データ値が１となる点には、所定の非ゼロの振幅となる周波数成分を配置していた。こうすることにより、カメラにより撮影した画像に対し、フーリエ変換と回転角度と拡大縮小率の補正と振幅の算出を行った後に、円上の所定位置の周波数成分の振幅が大きい順に所定数個の点を検出し、それらの点の成すパターンによりＩＤを復元することができた。
【０１２４】
実施形態３は、データ値が１となりうる点を所定数ｎだけ所定位置に定め、実際にデータ値を１とする点の数も所定数ｍ（＜ｎ）とする点においては、実施形態１及び実施形態２と共通する。しかし、実施形態３では、データ値が１となりうる点の位置を円上の位置ではない位置とする。例えば、格子状にｎ１×ｎ２（＝ｎ）個の位置を定め、そのうちｍ（＜ｎ１×ｎ２）個の点をデータ値が１となる点とする。このようにしても、フーリエ変換と回転角度と拡大縮小率の補正と振幅の算出を行った後に、格子上の所定位置の周波数成分の振幅が大きい順に所定数個の点を検出し、それらの点の成すパターンによりＩＤを復元することができる。
【符号の説明】
【０１２５】
１１  ＩＤ入力部
１３  情報点生成部
１５  ハミング符号パリティ生成部
１７  ハミング符号パリティ生成部
１９  偶数パリティ生成部
２１  偶数パリティ点生成部
２３  合成部
２５  逆フーリエ変換部
２７  画像入力部
２９  加算部
５１  フーリエ変換部
５３  絶対値算出部
５５  補正部
５７  点検出部
５９  パリティチェック部
６１  エラー訂正部
６３  点数点検部
６５  ＩＤ検出部
６７  制御部
【図１】
2011120268.tif 000003
【図２】
2011120268.tif 000004
【図３】
2011120268.tif 000005
【図４】
2011120268.tif 000006
【図５】
2011120268.tif 000007
【図６】
2011120268.tif 000008
【図７】
2011120268.tif 000009
【図８】
2011120268.tif 000010