画像位置推定装置、電子透かし検出装置及び方法並びにプログラム
【課題】複製前の画像と複製後の画像との位置合わせの精度を向上させることができる画像位置推定装置、複製前後の画像で推定された位置関係を基に電子透かし情報を検出する電子透かし検出装置及びこれらの方法並びにこれらの装置としてコンピュータを機能させるためのプログラムを提供する。
【解決手段】境界線推定部２が、複製画像を画像解析して、複製画像で元画像に含まれる画像領域と元画像に含まれない画像領域との境界線を推定し、位置推定方式選択部３が、複製画像でとり得る境界線の位置関係を選択基準として、元画像の辺と複製画像の辺又は境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定方式を有し、境界線推定部２によって複製画像から推定された境界線の位置関係を解析した結果に基づいて、複数の位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択する。
【解決手段】境界線推定部２が、複製画像を画像解析して、複製画像で元画像に含まれる画像領域と元画像に含まれない画像領域との境界線を推定し、位置推定方式選択部３が、複製画像でとり得る境界線の位置関係を選択基準として、元画像の辺と複製画像の辺又は境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定方式を有し、境界線推定部２によって複製画像から推定された境界線の位置関係を解析した結果に基づいて、複数の位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複製前の画像と複製後の画像の位置関係を推定する画像位置推定装置、複製前後の画像で推定された位置関係を基に電子透かし情報を検出する電子透かし検出装置及びこれらの方法並びにこれらの装置としてコンピュータを機能させるためのプログラムに関するものである。
【背景技術】
【０００２】
画像を複製する過程で編集等の処理を施して変形すると、複製前の画像を参照できない場合、複製前の画像と複製後の画像との位置関係が特定できないことがある。
一方、編集を一切行わないデジタル複製の場合や、コントラスト調整等の軽微な補正は行うが、画像の切取（トリミング）や拡大縮小を施さない場合には、複製前の画像と複製後の画像との位置関係は完全に保存される。
すなわち、複製前の画像の左上から横にｘ画素目、縦にｙ画素目の位置は、複製後の画像の左上から横にｘ画素目、縦にｙ画素目の位置に対応する。
しかしながら、一般的には、画像を複製する過程において、編集により、切取、拡大縮小、アスペクト比（縦横比）の変更が加えられる場合が多い。
【０００３】
また、映画の海賊版を得るため、映画館のスクリーンに投影された画像をビデオカメラで撮影して画像を複製した場合、複製後の画像に射影変換（透視投影変換）が加わって、長方形のスクリーンの画像が歪む。
このような場合に、複製前の画像を参照せずに、複製後の画像のみから複製前の画像との位置関係を特定することを可能にした従来の技術が、特許文献１及び特許文献２に開示されている。
特許文献１，２の技術では、複製後の画像から電子透かしを検出する際、射影変換を利用して複製前の画像と複製後の画像との位置合わせを行う。なお、複製前の画像と複製後の画像との位置合わせに関する技術自体は、電子透かし検出に適用先が限定されるものではない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００４−１２９２５９号公報
【特許文献２】特開２００９−１００２９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来では、射影変換を利用することにより、数学的には複製前の画像と複製後の画像との位置合わせが可能である。しかしながら、射影変換のみを利用するため、位置合わせを高い精度で行うことができないという課題があった。
【０００６】
ここで、画像に埋め込まれた電子透かし情報を検出することを目的として、電子透かし情報を埋め込んだ際の画像（複製前の画像）と、これを複製した後に流通した画像（複製後の画像）との間で位置合わせを行う場合を例に挙げる。
【０００７】
この場合、位置合わせのための射影変換で使用する画像中の特徴点自体が、電子透かし技術によって画像に埋め込まれていると、検出された特徴点には、位置的な誤差が含まれている可能性がある。従って、検出された特徴点をそのまま利用して射影変換を行うと、複製前の画像と複製後の画像との位置合わせに誤差が生じる要因となり得る。
【０００８】
さらに、複製後の画像の多くが、射影変換歪みを被るまで手を加えられていないことを考慮すると、位置合わせの際、特徴点の位置的な誤差に起因して、射影変換歪みが無駄に加わり、複製前の画像と複製後の画像との位置合わせ結果における誤差を助長する可能性もある。
【０００９】
この発明は、上記のような課題を解決するためになされたもので、複製前の画像と複製後の画像との位置合わせの精度を向上させることができる画像位置推定装置、複製前後の画像で推定された位置関係を基に電子透かし情報を検出する電子透かし検出装置及びこれらの方法、並びにこれらの装置としてコンピュータを機能させるためのプログラムを得ることを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係る画像位置推定装置は、第２の画像を画像解析して、当該第２の画像で第１の画像に含まれる画像領域と第１の画像に含まれない画像領域との境界線を推定する境界線推定部と、第２の画像でとり得る境界線の位置関係を選択基準として、第１の画像の辺と第２の画像の辺又は境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、境界線推定部によって第２の画像から推定された境界線の位置関係を解析した結果に基づいて、複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択部を備えるものである。
【００１１】
この発明に係る電子透かし検出装置は、上記画像位置推定装置と、画像位置推定装置の選択部により選択された位置推定情報から、第１の画像と第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される第２の画像の位置を特定して、当該第２の画像から電子透かし情報を検出する電子透かし情報検出部とを備えるものである。
【発明の効果】
【００１２】
この発明の画像位置推定装置によれば、境界線推定部が、第２の画像を画像解析して、当該第２の画像で第１の画像に含まれる画像領域と第１の画像に含まれない画像領域との境界線を推定し、選択部が、第２の画像でとり得る境界線の位置関係を選択基準として、第１の画像の辺と第２の画像の辺又は境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、境界線推定部によって第２の画像から推定された境界線の位置関係を解析した結果に基づいて、複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する。このように構成することにより、元画像である第１の画像とこれを元に生成された画像中に第１の画像の全部又は一部を含む第２の画像との位置合わせの精度を向上させることができるという効果がある。
【００１３】
この発明の電子透かし検出装置によれば、上記選択部によって選択された位置推定情報から、第１の画像と第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される第２の画像の位置を特定して、当該第２の画像から電子透かし情報を検出する。このように構成することで、第１の画像と画像中に第１の画像の全部又は一部を含む第２の画像との位置合わせが正確に行われ、電子透かし情報検出の成功率を高めることができるという効果がある。
【図面の簡単な説明】
【００１４】
【図１】この発明の実施の形態１による画像位置推定装置の構成例を示すブロック図である。
【図２】実施の形態１の画像位置推定装置による動作の流れを示すフローチャートである。
【図３】境界線の推定処理を説明するための図である。
【図４】実施の形態１における位置推定方式の一例を示す図である。
【図５】実施の形態２における境界線の推定処理を説明するための図である。
【図６】実施の形態２における位置推定方式の一例を示す図である。
【図７】この発明の実施の形態３による電子透かし検出装置の構成を示すブロック図である。
【図８】実施の形態３の電子透かし検出装置による動作の流れを示すフローチャートである。
【図９】実施の形態３における位置推定方式の一例を示す図である。
【図１０】この発明の実施の形態４による画像位置推定装置の構成を示すブロック図である。
【図１１】実施の形態４の画像位置推定装置による動作の流れを示すフローチャートである。
【図１２】実施の形態４における特徴点の検出処理を説明するための図である。
【図１３】実施の形態４における位置推定方式の一例を示す図である。
【図１４】この発明の実施の形態５による電子透かし検出装置の構成を示すブロック図である。
【図１５】実施の形態５の電子透かし検出装置による動作の流れを示すフローチャートである。
【図１６】この発明の実施の形態６による電子透かし検出装置の構成を示すブロック図である。
【図１７】実施の形態６の画像位置推定装置による動作の流れを示すフローチャートである。
【発明を実施するための形態】
【００１５】
実施の形態１．
図１は、この発明の実施の形態１による画像位置推定装置の構成例を示すブロック図である。図１において、実施の形態１の画像位置推定装置１は、複製前の画像（以下、元画像と呼称する）（第１の画像）とこの画像を複製した画像（以下、複製画像と呼称する）（第２の画像）において、一方の画像の任意な位置に対応する他方の画像の位置を推定する装置である。
なお、この画像位置推定装置１に扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態１で扱われる画像が複製されたものであることを、画像位置推定装置１の動作要件とするものではない。本発明でいう複製画像（第２の画像）は、画像中に、元画像である第１の画像の全部又は一部を含む画像であればよい。例えば、トリミングなどの画像処理により、第１の画像が完全に含まれない場合も第２の画像として取り扱う。
【００１６】
また、図１に示すように、画像位置推定装置１は、境界線推定部２及び位置推定方式選択部３を備える。境界線推定部２は、入力した複製画像（図１で画像と表記）を画像解析することにより、元画像に含まれる領域と含まれない領域との境界線を推定する構成部である。位置推定方式選択部（選択部）３は、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式（位置推定情報）を有しており、複製画像と境界線推定部２で推定した境界線とを解析した結果に基づいて、複数の位置推定方式のうち、対象画像に対応する位置推定方式を選択する構成部である。
【００１７】
なお、上述した境界線推定部２及び位置推定方式選択部３は、画像位置推定装置１を構成するコンピュータのＣＰＵが、本発明の趣旨に従う画像位置推定プログラムを実行することにより、上記のコンピュータにおいて、ソフトウェアとハードウェアが協働した具体的な手段として実現することができる。また、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式は、上記コンピュータが備える記憶装置に記憶される。
【００１８】
次に動作について説明する。
図２は、実施の形態１の画像位置推定装置による動作の流れを示すフローチャートであり、画像位置の推定手順の一例を示している。以降では、図１に示す構成を、図２に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、境界線推定部２及び位置推定方式選択部３にそれぞれ入力される。境界線推定部２は、入力した複製画像を画像解析することで、この複製画像の元画像に含まれる領域と含まれない領域との境界線として、上境界線、下境界線、左境界線、右境界線を推定する（ステップＳＴ１；境界線推定ステップ）。
【００１９】
この実施の形態１では、境界線推定部２が、複製画像の上下左右に、単色の領域、単調なテクスチャを持つ領域、自然画の周囲にある明らかに自然画とは異なる画像的性質を持つ領域などを画像解析によって特定し、これらの領域を上下方向及び左右方向の直線で区切って排除することにより、残された長方形の領域の上下左右の辺（線分）を、それぞれ上境界線、下境界線、左境界線、右境界線と推定する。
【００２０】
なお、上境界線の推定に失敗した場合や上境界線が存在しないと判断した場合は、複製画像の上辺（線分）を上境界線であると推定する。また、下境界線、左境界線、右境界線についても、同様に推定失敗や存在しないと判断した場合には、下境界線、左境界線、右境界線が、それぞれ、複製画像の下辺、左辺、右辺に一致すると推定するものとする。
【００２１】
また、境界線推定部２による境界線推定のアルゴリズムとしては、画像処理を用いた既存又は新規の様々な実現例が考えられる。この実施の形態１では、以下のアルゴリズムを採用する。
【００２２】
先ず、境界線推定部２は、複製画像から、画素値がほぼ一定である一定範囲の領域を検出し、検出した領域とこれ以外の領域との上下方向又は左右方向の境界線を推定する。
図３は、境界線の推定処理を説明するための図であり、様々な複製画像の上下左右の辺と境界線との関係を示している。上述のアルゴリズムでは、図３（ｂ）、図３（ｃ）及び図３（ｆ）にそれぞれ示すような画像からは、黒領域（画素値がほぼ一定である一定範囲の領域）が検出され、この黒領域との境目に境界線を設定することができる。
【００２３】
例えば、図３（ｂ）に示す画像では、上境界線と下境界線が、黒領域と風景画像領域（元画像を示す画像領域）との間に設定される。また、図３（ｃ）に示す画像は、左境界線と右境界線が、黒領域と風景画像領域との間に設定される。図３（ｆ）に示す画像では、上下左右の４境界線が、黒領域と風景画像領域との間に設定される。
【００２４】
次に、境界線推定部２は、複製画像から、画素値の種類が少数であって、かつ画像の空間領域に高周波成分を殆ど含まない領域を検出して、検出した領域とこれ以外の領域との上下方向又は左右方向の境界線を推定する。
例えば、画素値の種類の数（色の数）をカウントして色の数に関する所定の閾値と比較するとともに、高周波成分の検出に関する所定の閾値を用いて、空間領域における高周波成分を判定する。境界線推定部２は、色の数及び高周波成分が上記の各閾値以下と判定された領域を検出する。
【００２５】
このアルゴリズムによれば、図３（ｅ）に示すように、風景画像領域とは異なる領域、例えば、文字データの表示欄等が表示されている画像において、この文字データ表示欄の領域と風景画像領域との間の境界線（図３（ｅ）では左境界線と下境界線）が適切に推定される可能性を高めることができる。
【００２６】
続いて、境界線推定部２は、複製画像から、画像の空間領域の周波数成分スペクトルの分布が類似する領域を検出して、検出した領域とこれ以外の領域との上下方向又は左右方向の境界線を推定する。例えば、画像領域の周波数成分スペクトルをそれぞれ抽出し、スペクトル分布と所定の類似範囲にある画像領域を検出する。
このアルゴリズムにより、図３（ｄ）に示すように、画像サイズが足りない余白部分に一定の模様の画像領域がある画像において、この一定の模様の画像領域と風景画像領域との間の境界線（図３（ｄ）では左境界線と右境界線）が適切に推定される。
【００２７】
上述した各アルゴリズムで推定した境界線を基にして最終的な位置推定に失敗したり、境界線自体が存在しないと判定された場合には、境界線が、複製画像の辺に一致するものとして推定される。例えば、図３（ｂ）の画像であれば、境界線推定部２が、左右の境界線の推定に失敗している。この場合、図３（ｂ）に示す画像の左辺が左境界線と一致し、右辺が右境界線に一致すると最終的に判断される。
【００２８】
なお、上述のアルゴリズム以外にも、高度な画像処理を施すことによって、さらに高い精度で上下左右の境界を推定できる。つまり、境界線推定部２は、上下左右方向の境界線を推定して出力する任意の構成とすることができる。
【００２９】
勿論、境界線推定部２で推定された境界線が必ず有用になるとは限らない。
例えば、境界線を推定するアルゴリズムに不備がある場合の推定の失敗や、元画像に黒帯等の周辺領域が付属しており、何ら編集を加えていないにもかかわらず、本来の目的である元画像の境界線とは異なる上記の黒帯領域とこれ以外の領域との境界線が検出されるような場合には、推定された境界線は有用でない。このような場合、最終的な位置の推定に失敗する可能性がある。
【００３０】
境界線推定部２は、様々な方法で位置推定方式選択部３に上下左右の境界線を指定することができる。この実施の形態１では、上境界線と下境界線は、複製画像の上辺からの距離（単位は画素数）で指定し、左境界線と右境界線は、複製画像の左辺からの距離で指定する。
この他にも、画像左上を原点とし、右方向をｘ軸、下方向をｙ軸とする座標平面を割り当て、左右及び上下に隣接する２画素間の距離をｘ軸及びｙ軸上で１の大きさとしてスケーリングすることにより、上下左右の境界線を線分として捉えた場合の両端に当たる２点で指定することもできる。
なお、境界線の指定は、上下左右の境界線を装置１内部で特定可能な指定方法であればどのような方法であってもよい。
【００３１】
図２のフローチャートの説明に戻る。
位置推定方式選択部３は、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式を有している。
上述のようにして、境界線推定部２で推定された境界線が指定されると、位置推定方式選択部３は、入力した複製画像とこの複製画像について境界線推定部２が推定した境界線とを解析して、この解析結果が選択判断基準を満足する位置推定方式を、複数の位置推定方式のうちから選択する（ステップＳＴ２；位置推定方式選択ステップ）。
【００３２】
実施の形態１では、位置推定方式選択部３に予め設定される位置推定方式は、図４に示す方式１から方式３までの３通りと仮定する。つまり、位置推定方式選択部３は、方式１から方式３が登録された選択候補リストを保持し、この選択候補リストから複製画像に適した位置推定方式を選択する。
具体的には、推定された境界線が、方式１から順に選択判断基準を満たすかどうか確認して、満たす場合にはその方式を選択し、満たさない場合には、次に方式の選択判断基準を満たすかどうかを確認する。この選択判断基準は、画面内における境界線の位置関係であり、例えば境界線間の距離や境界線と辺との距離の関係で規定される。
なお、図４に示す方式において、方式１と方式２で選択判断基準を満たさない場合は、方式３を選択する。
【００３３】
図４において、方式１は、元画像の上辺、下辺、左辺、右辺が、複製画像の左境界線、右境界線、下境界線、上境界線にそれぞれ対応する位置関係を示す位置推定方式である。これは、元画像が９０度左回りに回転した場合に相当する。方式１の選択判断基準は、上下境界線間の距離が左右境界線間の距離より長いことであり、この条件を満たす場合に、位置推定方式選択部３は、方式１を選択する。
【００３４】
方式１の選択判断基準の条件を満たさない場合、位置推定方式選択部３は、方式２の選択判断基準を満たすかどうかを検証する。方式２の選択判断基準を満たす場合に、位置推定方式選択部は、方式２を選択する。
方式２は、元画像の上辺、下辺、左辺、右辺が、複製画像の上境界線、下境界線、左境界線、右境界線にそれぞれ対応する位置関係を示す位置推定方式である。これは、元画像が回転されずにそのまま上下左右の境界線内部に配置された場合に相当する。
【００３５】
位置推定方式選択部３は、方式２の選択判断基準を満たさない場合に、方式３を選択する。方式３は、元画像の上辺、下辺、左辺、右辺が、複製画像の上辺、下辺、左辺、右辺にそれぞれ対応する位置関係を示す位置推定方式である。
このようにして選択された位置推定方式は、処理対象の複製画像とその元画像との位置関係の推定結果として、位置推定方式選択部３から出力される。
【００３６】
実施の形態１の画像位置推定装置１は、元画像がテレビ画面や映画館のスクリーンに投影された映像のように、縦よりも横のサイズが１倍から３倍程度長い画像に有効である。このような元画像を複製した複製画像が方式１の選択判断基準を満たす場合には、この複製画像又はこの複製画像内の境界線で囲まれた長方形部分が縦長となる。これは、元画像が回転した画像である可能性が高いので、９０度左回りに回転したものとして位置を推定することにより、回転を考慮しない場合と比較して正しく位置を推定できる。
【００３７】
また、方式２では、複製画像内の境界線で囲まれた長方形部分が、縦長の場合及び横長過ぎる場合を除いて、この長方形部分が元画像に一致すると仮定することで、そうしない場合に比べ、複製画像の上下左右に黒帯が挿入されている場合などに位置推定の精度を高めることができる。
【００３８】
なお、複製画像内の境界線で囲まれた長方形部分が横長過ぎる場合は、推定された境界線の位置の信憑性が低いと考えられるため、方式２のように境界線で囲まれた領域内部の画像が元画像に対応するとした場合、位置推定の精度を損なう可能性がある。この場合には、方式３のように、元画像全体が複製画像全体に当たると仮定する対応関係で位置推定することで、位置推定の精度の劣化を防ぐことができる。
【００３９】
以上のように、この実施の形態１によれば、境界線推定部２が、複製画像を画像解析して、複製画像で元画像に含まれる画像領域と元画像に含まれない画像領域との境界線を推定し、位置推定方式選択部３が、複製画像でとり得る境界線の位置関係を選択基準として、元画像の辺と複製画像の辺又は境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定方式を有しており、境界線推定部２によって複製画像から推定された境界線の位置関係を解析した結果に基づいて、複数の位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択する。このように構成することにより、元画像と複製画像との位置合わせの精度を向上させることができる。
【００４０】
また、上記実施の形態１において、境界線推定部２が、境界線の推定に失敗した場合や境界線が存在しないと判断した場合、境界線を元画像の辺に対応すると推定した。
この場合、境界線推定部２は、上境界線、下境界線、左境界線、右境界線のそれぞれの情報を位置推定方式選択部３に与える。
このようにする代わりに、境界線の推定に失敗した場合や境界線が存在しないと判断した場合には、境界線推定部２が、「境界線なし」であることを示す情報を位置推定方式選択部３に与えるようにしてもよい。
例えば、境界線推定部が、元画像の上辺、下辺、左辺とはそれぞれ異なる、複製画像の上境界線、下境界線、左境界線を推定し、右境界線の検出に失敗した場合、上境界線、下境界線、左境界線の情報と、「右境界線がない」という情報を位置推定方式選択部３に与える。また、位置推定方式選択部３は、右境界線を必要とする方式（図４の方式１及び方式２）を選択肢から外して位置推定方式を選択する（図４の場合では、方式３が選択される）ことができる。
このようにすることで、選択を検討すべき方式の候補を事前に絞ることができるので、処理量を削減することができる。
【００４１】
さらに、上記実施の形態１では、位置推定方式選択部３が選択対象とする各方式で、前提とされる対応関係が、図４に示す内容である場合を示した。しかしながら、これは、位置推定方式で前提とする対応関係の一例であって、他の対応関係を設定してもよい。
例えば、方式１の前提とする対応関係を、元画像の上辺、下辺、左辺、右辺がそれぞれ複製画像の右境界線、左境界線、上境界線、下境界線に対応するとしてもよい。これは、複製画像が、元画像を９０度右回りに回転したものである場合に相当する。
このようにすることで、元画像に９０度右回りの回転が加えられた場合に適切に位置を推定することができる。
【００４２】
この他、元画像の上辺、下辺、左辺、右辺がそれぞれ複製画像の上境界線、下境界線、左辺、右辺に対応する位置関係を示す位置推定方式を選択肢としてもよい。
この方式を選択することで、元画像の上下のみに黒帯等の領域が付加された場合に適切に位置を推定できるようになる可能性が高まり、左右に黒帯等の領域が付加される可能性が低い場合に有効である。
【００４３】
さらに、他の方式を追加したり判断基準を変更することを許容する構成を設けることにより、位置推定方式選択部３が、任意の位置推定方式を備えるようにしてもよい。
例えば、位置推定方式選択部３が、画像位置推定装置１を構成するコンピュータが備える表示装置（モニタ）及び入力装置（キーボード、マウス、タッチパネル等）を用いて、新たな位置推定方式の内容、既存の位置推定方式で前提とされる対応関係、及び選択判断基準の少なくとも一つを設定入力するためのＧＵＩ（Graphical User Interface）を提供する。入力装置を用いて新たな方式や選択判断基準が入力されると、位置推定方式選択部３は、入力された内容で位置推定方式の選択候補リストを更新する。
【００４４】
実施の形態２．
この実施の形態２における画像位置推定装置は、上記実施の形態１と構成自体は同一であるが、上記実施の形態１とは、境界線を左右方向及び上下方向に限定しない点と、境界線の推定に失敗した場合や境界線が存在しないと判断した場合に「境界線をなし」と推定する点で異なる。
そこで、実施の形態２による画像位置推定装置の構成については、上記実施の形態１で示した図１を参照し、画像位置推定の手順については、上記実施の形態１で示した図２を参照する。
なお、実施の形態２においても、上記実施の形態１と同様に、画像位置推定装置１に扱われる画像を“複製画像”と呼称するが、これは、“元画像”と区別するためであって、この実施の形態２で扱われる画像が複製されたものであることを、画像位置推定装置１の動作要件とするものではない。
【００４５】
次に動作について説明する。
以降では、図１に示す構成を図２に示す各処理ステップの動作に対応付けて説明する。
上記実施の形態１と同様に、処理対象の複製画像は、境界線推定部２及び位置推定方式選択部３にそれぞれ入力される。境界線推定部２は、入力した複製画像を画像解析することにより、この複製画像の元画像に含まれる領域と含まれない領域との境界線として、上境界線、下境界線、左境界線、右境界線を推定する（ステップＳＴ１；境界線推定ステップ）。
【００４６】
実施の形態２では、境界線推定部２が、複製画像の上下左右に、単色の領域、単調なテクスチャを持つ領域、自然画の周囲にある明らかに自然画とは異なる画像的性質を持つ領域などを画像解析によって特定し、これらの領域を４本の直線（上下方向及び左右方向に限られない）で区切って排除することにより、残された長方形の領域の上下左右の辺（線分）を、それぞれ上境界線、下境界線、左境界線、右境界線と推定する。
また、上境界線の推定に失敗した場合や上境界線が存在しないと判断した場合は、「上境界線なし」と推定する。下境界線、左境界線、右境界線についても、同様に推定失敗や存在しないと判断した場合には「下境界線なし」、「左境界線なし」、「右境界線なし」と推定する。
【００４７】
このように、実施の形態２では、上記実施の形態１と異なり、複製画像中の単色の領域や単調なテクスチャを持つ領域、自然画とは異なる画像的性質を持つ領域を、斜め方向も許容される、左右方向及び上下方向に限られない境界線で区切って排除し、また境界線の推定に失敗したり、境界線が存在しないと判断した場合には「境界線なし」と推定する。
境界線推定部２による境界線推定アルゴリズムとしては、画像処理を用いた既存又は新規の様々な実現例が考えられる。実施の形態２では、以下のアルゴリズムを採用する。
【００４８】
先ず、境界線推定部２は、上記実施の形態１と同様に、画素値や画素値の周波数成分などの画像的特徴を処理することで、単色の領域、単調なテクスチャを持つ領域、自然画の周囲にある明らかに自然画と異なる画像的性質を持つ領域などを判断し、これらの領域を直線で区切って排除し、境界線を推定する。ただし、この実施の形態２では、境界線を上下方向及び左右方向に限らず、斜めでもよいものとして推定する。
【００４９】
図５は、実施の形態２における境界線の推定処理を説明するための図であり、様々な複製画像の上下左右の辺と境界線との関係を示している。図５（ａ）に示した複製画像は、元画像（風景画像領域）を小さな画像サイズで斜めに複製している。
上記実施の形態１で示した画像位置推定装置が、この図５（ａ）の複製画像において、上下左右の境界線を推定した場合、図５（ｂ）に示すように風景画像領域の矩形の頂点をそれぞれ含む境界線が上下左右の境界線として推定される。このため、風景画像領域以外の黒領域が含まれ、風景画像領域のみを切り出す境界線を推定できない。
【００５０】
これに対して、この実施の形態２による画像位置推定装置では、図５（ｃ）に示すように斜め方向にも境界線を推定するために、図５（ａ）に示すような複製画像であっても、風景画像領域のみを切り出す境界線の推定が可能である。この境界線推定アルゴリズムとしては、下記のものが挙げられる。
【００５１】
先ず、黒領域と風景画像領域との境界として、斜め方向の４本の境界線を求め、線分としてのこれら４境界線の中点をそれぞれ算出する。４境界線の中点のうち、画像中で最も上に位置する境界線を上境界線と推定し、残りの境界線の中点のうち、画像中で最も下に位置する境界線を下境界線と推定し、残り２境界線の中点のうち、画像の左側にある境界線を左境界線と推定し、画像の右側にある境界線を右境界線と推定する。
【００５２】
また、同様に斜め方向の４本の境界線を求めて４境界線の中点をそれぞれ算出した後、図５（ａ）に示す複製画像の下辺を水平線とした場合に、当該画像中の当該水平線からの仰角が４５度を超える境界線のうち、中点が最も左にある境界線を左境界線と推定し、最も右にある境界線を右境界線と推定し、残りの２境界線のうち、中点が画像の上側にある境界線を上境界線と推定して、残りの１境界線を下境界線と推定するアルゴリズムを採用することもできる。
【００５３】
境界線推定部２は、これらのアルゴリズムに従って推定した上下左右の境界線が、時計回りに上境界線、右境界線、下境界線、左境界線となっていなければ、４境界線の推定に失敗したと判断する。
また、この他に、境界線推定部２が、境界線の推定において、境界線４境界線の中から上述のアルゴリズムに従って上境界線のみを選定し、残りは、上境界線から時計回りに右境界線、下境界線、左境界線と選定するようにしてもよい。
さらに、この実施の形態２では、黒領域と元画像を示す画像領域との境界線として斜め方向の境界線を推定し、画像中の位置から上下左右の境界線として選定することができるアルゴリズムであれば、上記のアルゴリズムの内容に限定されるものではない。
【００５４】
境界線推定部２によって推定された上下左右の境界線は、例えば、下記の方法で、位置推定方式選択部３に指定される。
複製画像の左上の頂点を原点とし、この原点から右方向にｘ軸、下方向をｙ軸とした２次元座標平面を割り当て、左右及び上下に隣接する２画素間の距離をｘ軸及びｙ軸上で、１の大きさとしてスケーリングし、上下左右の境界線を線分として捉えた場合の線分両端にあたる２点を用いて境界線を指定する。
例えば、上境界線は、上境界線と左境界線との交点の座標と、上境界線と右境界線との交点の座標との組み合わせで指定するか、上境界線が存在しないことを示す識別子で表現する。下境界線、左境界線、右境界線についても同様である。
【００５５】
位置推定方式選択部３は、境界線推定部２で推定された境界線が指定されると、入力した複製画像とこの複製画像について境界線推定部２が推定した境界線とを解析して、この解析結果が選択判断基準を満足する位置推定方式を、複数の位置推定方式のうちから選択する（ステップＳＴ２；位置推定方式選択ステップ）。
【００５６】
この実施の形態２では、位置推定方式選択部３に予め設定される位置推定方式は、図６に示す方式１から方式３までの３通りと仮定する。つまり、位置推定方式選択部３は、方式１から方式３が登録された選択候補リストを保持し、この選択候補リストから複製画像に適した位置推定方式を選択する。
具体的には、推定された境界線が、方式１から順に選択判断基準を満たすかどうか確認して、満たす場合にはその方式を選択し、満たさない場合には、次に方式の選択判断基準を満たすかどうかを確認する。なお、図６に示す方式において、方式１と方式２で選択判断基準を満たさない場合は、方式３を選択する。
【００５７】
図６において、方式１は、元画像の上辺、下辺、左辺、右辺が、複製画像の左境界線、右境界線、下境界線、上境界線にそれぞれ対応する位置関係を示す位置推定方式である。これは、元画像が９０度左回りに回転した場合に相当する。方式１の選択判断基準は、左右境界線間の距離が上下境界線間の距離より長いことであり、この条件を満たす場合に、位置推定方式選択部３は、方式１を選択する。
【００５８】
方式１の選択判断基準の条件を満たさない場合、位置推定方式選択部３は、方式２の選択判断基準を満たすかどうかを検証する。方式２の選択判断基準を満たす場合に、位置推定方式選択部は、方式２を選択する。
方式２は、元画像の上辺、下辺、左辺、右辺が、複製画像の上境界線、下境界線、左境界線、右境界線にそれぞれ対応する位置関係を示す位置推定方式である。これは、元画像が回転されずにそのまま上下左右の境界線内部に配置された場合に相当する。
【００５９】
位置推定方式選択部３は、方式２の選択判断基準を満たさない場合に、方式３を選択する。方式３は、元画像の上辺、下辺、左辺、右辺が、複製画像の上辺、下辺、左辺、右辺にそれぞれ対応する位置関係を示す位置推定方式である。
このようにして選択された位置推定方式は、処理対象の複製画像とその元画像との位置関係の推定結果として、位置推定方式選択部３から出力される。
【００６０】
実施の形態２の画像位置推定装置１は、元画像がテレビ画面や映画館のスクリーンに投影された映像のように、縦よりも横のサイズが１倍から３倍程度長い画像であり、かつ、スクリーンを上映中に撮影した場合のように、長方形の元画像が歪んで撮影された複製画像に有効である。複製画像は、上述のように元画像が回転しているか否かを各位置推定方式の選択判断基準から推定することができる。
【００６１】
以上のように、この実施の形態２によれば、境界線推定部２が、複製画像上で推定する境界線を左右方向及び上下方向に限定せず、境界線の推定に失敗した場合や境界線が存在しないと判断した場合に「境界線をなし」と推定する。このように構成することにより、上記実施の形態１と比べ、さらに元画像と複製画像との位置合わせの精度を向上させることができる。
【００６２】
なお、上記実施の形態２では、境界線推定部２が、上下左右の方向に限らない線分の境界線を推定する場合を示したが、上下境界線が水平方向（左右方向）に近い場合や左右境界線が鉛直方向（上下方向）に近い場合などは、特別に水平方向の境界線や鉛直方向の境界線とすることもできる。
例えば、境界線推定部２が、上下境界線の水平方向に対する角度が一定角度以内である場合には、上記実施の形態１で示した境界線推定アルゴリズムに切り替え、水平方向の上下境界線を推定したり、左右境界線の鉛直方向に対する角度が一定角度以内である場合には、上記実施の形態１で示した境界線推定アルゴリズムに切り替えて、鉛直方向の左右境界線を推定したりすることもできる。
このようにすることで、上下方向又は左右方向の境界線が、画像処理上の誤差によって完全には上下方向又は左右方向とならない場合に、その誤差の影響を排除することができる。なお、上記実施の形態１で示した境界線推定アルゴリズム以外のアルゴリズムを採用してもよく、境界線推定部２は、上下左右の境界線を推定して出力する任意の構成とすることができる。
【００６３】
実施の形態３．
この実施の形態３では、元画像に埋め込まれた電子透かし情報を複製画像から検出する電子透かし検出装置について説明する。
図７は、この発明の実施の形態３による電子透かし検出装置の構成を示すブロック図である。図７において、実施の形態３の電子透かし検出装置１Ａは、元画像と元画像を複製した複製画像において、一方の画像の任意な位置に対応する他方の画像の位置の対応関係を推定し、この対応関係を基に電子透かし情報を検出して電子透かし情報及び電子透かし情報検出の成否を出力する装置である。
なお、電子透かし検出装置１Ａに扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態３で扱われる画像が複製されたものであることを、電子透かし検出装置１Ａの動作要件とするものではない。
【００６４】
また、図７に示すように、電子透かし検出装置１Ａは、境界線推定部２、位置推定方式選択部３及び電子透かし情報検出部４を備える。境界線推定部２は、入力した複製画像（図７で画像と表記）を画像解析することで、元画像に含まれる領域と含まれない領域との境界線を推定する構成部である。位置推定方式選択部３は、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式を有し、複製画像と境界線推定部２で推定した境界線とを解析した結果に基づいて、複数の位置推定方式のうち、対象画像に対応する位置推定方式を選択する構成部である。
さらに、電子透かし情報検出部４は、位置推定方式選択部３で選択された位置推定方式に従い、複製画像と元画像との位置関係の対応付けを行い、この位置関係に基づいて電子透かし情報を検出し、検出された電子透かし情報及び電子透かし情報の検出の成否を出力する構成部である。
【００６５】
なお、境界線推定部２、位置推定方式選択部３及び電子透かし情報検出部４は、電子透かし検出装置１Ａを構成するコンピュータのＣＰＵが、本発明の趣旨に従う画像位置推定及び電子透かし検出用プログラムを実行することにより、上記のコンピュータにおいて、ソフトウェアとハードウェアが協働した具体的な手段として実現することができる。
また、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式は、上記コンピュータが備える記憶装置に記憶される。
【００６６】
次に動作について説明する。
図８は、実施の形態３の電子透かし検出装置による動作の流れを示すフローチャートであり、画像位置の推定及び電子透かし検出手順の一例を示している。以降では、図７に示す構成を、図８に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、境界線推定部２、位置推定方式選択部３、及び電子透かし情報検出部４にそれぞれ入力される。境界線推定部２は、上記実施の形態１と同様の処理で、入力した複製画像を画像解析することによって、この複製画像の元画像に含まれる領域と含まれない領域との境界線として、上境界線、下境界線、左境界線、右境界線を推定する（ステップＳＴ１ａ；境界線推定ステップ）。
【００６７】
位置推定方式選択部３は、境界線推定部２にて推定された境界線が指定されると、入力した複製画像とこの複製画像について境界線推定部２が推定した境界線とを解析して、この解析結果が選択判断基準を満足する位置推定方式を、複数の位置推定方式のうちから選択する（ステップＳＴ２ａ；位置推定方式選択ステップ）。
【００６８】
続いて、電子透かし情報検出部４が、位置推定方式選択部３により選択された位置推定方式に基づいて、複製画像と元画像との位置関係の対応付けを行い、この位置関係から、電子透かし情報の検出処理を行う（ステップＳＴ３ａ；電子透かし情報検出ステップ）。元画像の特定の位置に電子透かし情報が埋め込まれている場合は、位置推定方式選択部３で選択された位置推定方式によって、複製画像と元画像との位置関係の対応付けが可能であるから、電子透かし情報を検出することができる。なお、本発明において、電子透かし自体は、特定の電子透かし技術を想定していない。つまり電子透かし技術は、既に様々な方式が公知となっており、これらのうちのいずれかの方式を適用してもよい。
【００６９】
通常、電子透かし情報は、誤り検出符号を含んでいるので、電子透かし情報の検出結果から、電子透かし情報の検出の成否を判断できる。実施の形態３においても、電子透かし情報が誤り検出符号を含んでいるものとする。
電子透かし情報検出部４は、電子透かし情報の検出処理において誤り検出符号から電子透かし情報の検出の成否を判断する（ステップＳＴ４ａ；成否判断ステップ）。
【００７０】
電子透かし情報検出部４にて電子透かし情報の検出に失敗すると（ステップＳＴ４ａ；失敗）、位置推定方式選択部３は、まだ選択していない選択可能な位置推定方式が残っているか否かを判定する（ステップＳＴ５ａ；選択可否判定ステップ）。
このとき、選択可能な位置推定方式が残っていれば（ステップＳＴ５ａ；ＹＥＳ）、ステップＳＴ２ａの処理に戻り、位置推定方式選択部３が、残りの位置推定方式を選択して、選択可能な残りの位置推定方式が無くなるまで（ステップＳＴ５ａ；ＮＯ）、ステップＳＴ２ａ以降の処理を繰り返す。
【００７１】
位置推定方式選択部３は、２度目以降の位置推定方式の選択において、以前に選択した位置推定方式を選択肢から外し、その上で、１度目と同じ手順で位置推定方式を一つ選択する。電子透かし情報検出部４は、位置推定方式選択部３にて選択された位置推定方式を使用して、再度電子透かし情報の検出を試みる。この処理を繰り返す。位置推定方式選択部３に予め設定された（例えば、図４の表の方式１から方式３の）位置推定方式のうち、選択可能な位置推定方式の候補がなくなった上で、電子透かし情報の検出に失敗すると、最終的に電子透かし情報の検出失敗として、処理を終了する。
【００７２】
このようにすることで、もし最初に選択した位置推定方式が不適切であったとしても、より適切な位置推定方式を選んで、電子透かし情報の検出をやり直すことができる。
このため、位置推定方式選択及び電子透かし情報検出を一度しか実施しない構成と比べて、電子透かし情報の検出成功率を向上させることができる。
【００７３】
図４に示す位置推定方式の選択候補リストから位置推定方式を選択する場合を例にとって、具体的な位置推定方式選択のやり直しの手順を説明する。位置推定方式選択部３が、方式１を選択してから、その後選択をやり直す場合、方式１を選択肢から除き、方式２と方式３のどちらかを選択する。
【００７４】
方式２の選択判断基準を満たしていれば方式２を選択し、そうでなければ方式３を選択する。３度目の選択では、残りの位置推定方式が方式３であれば、方式３を選択するが、残りの位置推定方式が方式２であっても、２度目の選択で選択判断基準を満たしていないため、方式２は選択されず、選択可能な位置推定方式が残っていないとして、最終的に電子透かし情報の検出を失敗として終了する。
【００７５】
このように、あくまで選択基準を満たさない方式は、選択しないとするアルゴリズムの他、位置推定方式の選択をやり直す場合には、選択判断基準を緩めて設定し直し、残りの位置推定方式を全て選択対象とするアルゴリズムを採用してもよい。
また、選択判断基準を設けず、方式１から順番に選択していき、選択肢となる位置推定方式がなくなったら、最終的に電子透かし情報の検出を失敗として終了するアルゴリズムも考えられる。
【００７６】
上述のような位置推定方式の選択のやり直しを行うアルゴリズムは、様々な形態が可能である。位置推定方式選択部３は、電子透かし情報検出部４が電子透かし情報の検出に成功するか、選択可能な位置推定方式がなくなるまで、選択可能な位置推定方式の中から位置推定方式を選択する構成であれば、任意の構成とすることができる。
【００７７】
なお、上述の説明では、位置推定方式選択部３を、上記実施の形態１の画像位置推定装置１の位置推定方式選択部と同様の構成とした。従って、図４の位置推定方式の候補リストから位置推定方式を選択することになる。
【００７８】
一方、位置推定方式の候補リストは、図４の代わりに、図９に示すリストを採用しても構わない。図９に示す候補リストでは、位置推定方式として方式１が選択され、その後に位置推定方式の選択をやり直す際に方式２が選択される。方式２は、図９に示すように、元画像の上辺、下辺、左辺、右辺がそれぞれ複製画像の右境界線、左境界線、上境界線、下境界線に対応する位置推定方式である。これは、元画像が９０度右回りに回転した場合に相当する。
【００７９】
元画像が９０度右回りに回転してアスペクト比が変更され、その周囲を黒領域で補充された複製画像が対象である場合を例に挙げる。この場合、図４に示す位置推定方式の候補リストから位置推定方式を選択するアルゴリズムであると、境界線内部の画像の長方形が縦長であることから、元画像が回転している可能性があるとして方式１を選択することができるが、方式１は、元画像が９０度左回りに回転されている場合に相当するので、位置合わせに成功しない。
【００８０】
これに対して、図９に示す位置推定方式の候補リストから位置推定方式を選択するアルゴリズムを採用すると、方式１を選択して位置関係を推定してから、電子透かし情報の検出に失敗した場合、次に図９の候補リスト中の方式２が選択され、正しく位置関係を推定することができる。従って、電子透かし情報検出の成功率を高めることができる。
【００８１】
また、上述の説明では、境界線推定部２が、上記実施の形態１の画像位置推定装置１の境界線推定部２と同様の構成であり、かつ、位置推定方式選択部３が、上記実施の形態１の画像位置推定装置１の位置推定方式選択部３と同様の構成である場合を示した。
しかしながら、この実施の形態３では、境界線推定部２を上記実施の形態２の画像位置推定装置１の境界線推定部と同様の構成とし、かつ、位置推定方式選択部３を上記実施の形態２で示した位置推定方式選択部３と同様の構成とすることもできる。
このように構成すると、複製画像が元画像をカメラで撮影して複製された画像である場合など、複製の過程で元画像の長方形に射影変換歪が加えられた場合であっても、元画像と複製画像との位置関係を推定し、複製画像から元画像に埋め込まれた電子透かし情報を検出する装置を構成することができる。
この構成において、電子透かし情報の検出に失敗した場合に位置推定方式の選択をやり直して、再度電子透かし情報の検出を試みることで、電子透かし情報検出の成功率を高めることができる。
【００８２】
この他にも、実施の形態３による電子透かし検出装置１Ａとして、境界線推定部２が推定した上下左右の境界線に関する情報を利用し、位置推定方式選択部３が位置推定方式の候補リストから位置推定方式を選択し、選択のやり直しの場合には、まだ選択されていない位置推定方式から選択する動作をする構成あれば、任意の構成とすることができる。
【００８３】
以上のように、この実施の形態３によれば、位置推定方式選択部３によって選択された位置推定方式から、元画像と複製画像との間で位置の対応付けを行い、この対応関係に基づいて、元画像で電子透かし情報が埋め込まれた箇所に対応すると推定される複製画像の位置を特定して、当該複製画像から電子透かし情報を検出する。このように構成することで、元画像と複製画像との位置合わせが正確に行われ、電子透かし情報検出の成功率を高めることができる。
【００８４】
実施の形態４．
この実施の形態４では、得られた複製画像とその元画像との位置関係を推定する画像位置推定装置について説明する。
図１０は、この発明の実施の形態４による画像位置推定装置の構成を示すブロック図である。図１０において、実施の形態４の画像位置推定装置１Ｂは、元画像とこの画像を複製した複製画像とにおいて、一方の画像の任意な位置に対応する他方の画像の位置を推定する装置である。なお、この画像位置推定装置１Ｂに扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態４で扱われる画像が複製されたものであることを、画像位置推定装置１Ｂの動作要件とするものではない。
【００８５】
また、図１０に示すように、画像位置推定装置１Ｂは、特徴点検出部５及び位置推定方式選択部３ａを備える。特徴点検出部５は、得られた複製画像を画像解析することにより、元画像に予め埋め込んであった特徴点を検出する構成部である。
位置推定方式選択部３ａは、複製画像と元画像に予め埋め込んだ特徴点との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式を有し、複製画像と特徴点検出部５で検出された特徴点とを解析した結果に基づいて、複数の位置推定方式のうち、対象画像に対応する位置推定方式を選択する構成部である。
【００８６】
なお、特徴点検出部５及び位置推定方式選択部３ａは、画像位置推定装置１Ｂを構成するコンピュータのＣＰＵが、本発明の趣旨に従う画像位置推定プログラムを実行することにより、上記のコンピュータにおいて、ソフトウェアとハードウェアが協働した具体的な手段として実現することができる。また、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式は、上記コンピュータが備える記憶装置に記憶される。
【００８７】
次に動作について説明する。
図１１は、実施の形態４の画像位置推定装置による動作の流れを示すフローチャートであり、画像位置の推定手順の一例を示している。以降では、図１０に示す構成を、図１１に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、特徴点検出部５及び位置推定方式選択部３ａにそれぞれ入力される。特徴点検出部５は、入力した複製画像を画像解析することにより、この複製画像の元画像に予め埋め込んであった特徴点を検出する（ステップＳＴ１ｂ；特徴点検出ステップ）。
【００８８】
ここでは、特徴点検出部５が、例えば、図１２に示すような元画像に設定した座標系において、長方形の元画像の、上から４分の１で、かつ左から４分の１の位置、上から４分の１で、かつ右から４分の１の位置、下から４分の１で、かつ左から４分の１の位置、下から４分の１で、かつ右から４分の１の位置に、４つの特徴点がそれぞれ設定されているものと仮定する。なお、実施の形態４では、各特徴点をＰS1、ＰS2、ＰS3、ＰS4と呼ぶ。
【００８９】
特徴点を埋め込む方法としては、特徴点が中心となる、ある程度の半径を有した可視の円を元画像に上書きする方法が挙げられる。
また、この他、画像の画素値の最下位ビット（least significant bit;LSB)に対して、特徴点情報を与える方法がある。例えば、最下位ビット値が“１”ならば、特徴点が中心となる、ある程度の半径を有する円に含まれる画素とし、また最下位ビット値が“０”ならば、この円に含まれない画素とする。
あるいは、電子透かし技術によって秘密裏に特徴点を埋め込む方法などが考えられる。
【００９０】
実施の形態４では、画像の画素値の最下位ビットに特徴点情報を与える方法で、元画像に特徴点が設定されているものと想定する。また、この実施の形態４では、特徴点という用語はあくまで点として扱い、特徴点を表す、ある程度の半径を持った円について言う場合は、特徴点を表す円と表現する。
【００９１】
図１２のように、元画像が、横６４０画素及び縦４８０画素の場合を例に挙げて詳細に説明する。この元画像に対して、画像左上を原点として、右方向をｘ軸、下方向をｙ軸とする座標平面を割り当て、左右及び上下に隣接する２画素間の距離をｘ軸及びｙ軸上で、１の大きさとしてスケーリングし、特徴点ＰS1、ＰS2、ＰS3、ＰS4の座標（ｘ，ｙ）は、それぞれ（１６０，１２０）、（４８０，１２０）、（１６０，３６０）、（４８０，３６０）となる。
【００９２】
各特徴点をどの画素に割り当てるかは、様々な実装によることができる。
この実施の形態４では、左上から横方向（ｘ軸）にｍ画素目（１≦ｍ≦６４０）でありかつ、縦ｎ画素目（１≦ｎ≦４８０）の画素位置（ｍ，ｎ）が、座標（ｍ−０．５，ｎ−０．５）に当たるものとする。ここで、特徴点を表す円に含まれる画素であるか否かは、その画素の座標が特徴点を表す円の内部に含まれるかどうかで判断することができる。
【００９３】
特徴点ＰS1を例にとると、特徴点ＰS1を表す円の式は、下記の通りになる。
（ｘ−１６０）2＋（ｙ−１２０）2≦ｒ2 ・・・（１）
但しｒは、円の半径である。
【００９４】
特徴点ＰS1の情報を有する画素（ｍ，ｎ）は、（ｍ−１６０．５）2＋（ｎ−１２０．５）2≦ｒ2を満たす画素となる。この画素において画素値の最下位ビットを“１”とする。他の特徴点についても、同様に特徴点の情報を持つ画素の画素値の最下位ビットを“１”とする。そして、特徴点の情報を有さない画素の画素値の最下位ビットを“０”とする。
【００９５】
このようにすることにより、画像に特徴点を表す円を設定することができる。円の半径の設計は任意だが、余りに小さいと、画像が縮小処理された場合に検出しにくくなる恐れがある。半径を大きくすることで、縮小処理に対する耐性が生まれる。
【００９６】
このように、元画像に４つの特徴点を表す円を設定すると、特徴点検出部５によって、画素値の最下位ビットに特徴点の情報が埋め込まれていることを想定した場合の、具体的な動作は、下記のようになる。なお、図１２に示すように、特徴点の検出対象となる複製画像が、横３６０画素、縦２４０画素である場合を例に挙げて説明する。
【００９７】
先ず、特徴点検出部５は、複製画像の各画素の最下位ビットが“０”か“１”かを調べる。これにより、最下位ビットが“０”である画素の画像領域と、最下位ビットが“１”である画素が含まれる画像領域が発見される。この最下位ビットが“１”である画素の集まり（画像領域）が特徴点を表す円に対応し、この画素の集まりの中心点を画像処理等で推定することにより、特徴点の座標が推定される。図１２の例では、特徴点が最大で４つ検出される。検出された特徴点のうち、左上のもの、右上のもの、左下のもの、右下のものを、それぞれＰD1、ＰD2、ＰD3、ＰD4と呼ぶことにする。
【００９８】
なお、検出に成功した特徴点が３つ以下となる場合もある。この場合には、欠損したと考えられる特徴点を推定する。例えば、特徴点が３つ検出された場合で、それら特徴点の位置関係から右上の特徴点が欠損したと判断し得る場合、ＰD2を検出失敗し、ＰD1、ＰD3、ＰD4の検出に成功したものと判断する。特徴点が一つも検出されないという結果もあり得る。
【００９９】
特徴点の位置関係を判断するアルゴリズムは、様々なものが考えられる。
例えば、検出された４つの特徴点のうち、ｘ座標値＋ｙ座標値が最も小さい特徴点を、ＰD1とし、最も大きい特徴点をＰD4、ｘ座標−ｙ座標が最も小さい特徴点をＰD3、最も大きい特徴点をＰD2とするアルゴリズムが考えられる。
この他にも、先ず、ＰD1を推定し、ＰD1から複製画像中央に向かって最も左側にある特徴点をＰD2、最も右側にある特徴点をＰD3、残りをＰD4とするアルゴリズムも可能である。
ｘ座標が０以上１８０以下でｙ座標が０以上１２０以下の特徴点をＰD1とし、ｘ座標が１８０以上３６０以下でｙ座標が０以上１２０以下の特徴点をＰD2とし、ｘ座標が０以上１８０以下でｙ座標が１２０以上２４０以下の特徴点をＰD3とし、ｘ座標が１８０以上３６０以下でｙ座標が１２０以上２４０以下の特徴点をＰD4とするアルゴリズムを採用しても構わない。このアルゴリズムの場合は、検出された特徴点が３つ以下であっても使用可能である。
【０１００】
また、誤検出により、特徴点が５つ以上検出される可能性もある。このような場合は、特徴点の位置関係や検出時の特徴点の確からしさ（画像処理の計算上、本当に特徴点でありそうな可能性の高さ）から特徴点を４つに絞る処理を加えればよい。
【０１０１】
なお、特徴点検出部５は、特徴点の位置関係の判断アルゴリズムとして、上述したもの以外の採用も可能であり、特徴点の埋め込み方法、埋め込まれる位置に応じて、適切なアルゴリズムを備えていれば、任意の構成とすることができる。
【０１０２】
図１１のフローチャートの説明に戻る。
位置推定方式選択部３ａは、得られた複製画像及び特徴点検出部５が判断した０個以上の特徴点を解析し、元画像と複製画像との位置関係を推定する方式のうち、当該複製画像に適したものを選択する（ステップＳＴ２ｂ；位置推定方式選択ステップ）。
【０１０３】
ここで、説明上の便宜のため、図１２に示すように、元画像の上辺、下辺、左辺、右辺を、それぞれ線分ｅS1、線分ｅS2、線分ｅS3、線分ｅS4とする。また、元画像の中心を点ＣSとする。元画像における４つの特徴点を、左上、右上、左下、右下の順にそれぞれ点ＰS1、点ＰS2、点ＰS3、点ＰS4とする。複製画像の上辺、下辺、左辺、右辺をそれぞれ、線分ｅD1、線分ｅD2、線分ｅD3、線分ｅD4とする。複製画像の中心を点ＣDとする。さらに、複製画像から検出された特徴点のうち、特徴点検出部５によって相対的に左上、右上、左下、右下の位置にあると判断されたものを、それぞれ点ＰD1、点ＰD2、点ＰD3、点ＰD4とする。
【０１０４】
実施の形態４では、位置推定方式選択部３ａが選択する位置推定方式は、図１３に示す候補リストにおける、方式１、方式５から方式９、方式１２、方式１３の８通りとする。
位置推定方式選択部３ａは、方式１から順に選択判断基準を満たすか否かを確認し、満たす場合はその方式を選択し、満たさない場合は次の方式が選択判断基準を満たすかどうかを確認する。これを繰り返すことにより、得られた複製画像に適した位置推定方式を選択する。なお、方式１、方式５から方式９、方式１２の全７方式で選択判断基準を満たさない場合には、方式１３を選択する。
【０１０５】
図１３において、方式１は、元画像の上辺、下辺、左辺、右辺が、それぞれ複製画像の上辺、下辺、左辺、右辺に対応する位置関係を示す位置推定方式である。方式１は、下記の計算式（１）の関係を満たすか否かで選択判断される。
｜ｆ（ＰS1）ＰD1｜2＋｜ｆ（ＰS2）ＰD2｜2＋｜ｆ（ＰS3）ＰD3｜2＋｜ｆ（ＰS4）ＰD4｜2≦α2（ｆ（｜ｅS1｜）2＋ｆ（｜ｅS3｜）2） ・・・（２）
【０１０６】
計算式（１）において、ｆは位置推定方式が前提とする対応関係を満たす写像である。αは非負定数、｜ａ｜は線分ａの長さを表す。なお、ｆ（｜線分｜）は、線分の両端の２点をそれぞれｆで写像した後の２点を結ぶ線分の長さを表す。
ｆ（ＰS1）は、方式１の前提である元画像の上辺、下辺、左辺、右辺が、それぞれ複製画像の上辺、下辺、左辺、右辺に対応するという前提が成り立つ際の、元画像上の左上の特徴点ＰS1に対応する複製画像上の座標を表している。
ＰD1は、特徴点検出部５が検出した特徴点のうち、複製画像の左上に位置する特徴点の座標である。従って、｜ｆ（ＰS1）ＰD1｜は、複製画像上で特徴点が本来あるべき位置と、特徴点検出部５によって検出された位置との間の距離を表している。
【０１０７】
なお、特徴点ＰD1が検出されなかった場合には、｜ｆ（ＰS1）ＰD1｜を“０”と評価する。また、特徴点ＰD2、ＰD3、ＰD4が検出されなかった場合においても、同様に｜ｆ（ＰS2）ＰD2｜、｜ｆ（ＰS3）ＰD3｜、｜ｆ（ＰS4）ＰD4｜をそれぞれ“０”と評価する。
つまり、上記計算式（２）の不等式は、位置推定方式を方式１と仮定した場合に、特徴点の誤差二乗和が一定の範囲内に抑えられているかどうかを評価している。
図１２の例に当てはめると、ｆ（ＰS1）、ｆ（ＰS2）、ｆ（ＰS3）、ｆ（ＰS4）、ｆ（｜ｅS1｜）、ｆ（｜ｅS3｜）は、それぞれ（９０，６０）、（２７０，６０）、（９０，１８０）、（２７０，１８０）、３６０、２４０である。
【０１０８】
この不等式評価は、元画像と複製画像との関係において、前提とする各辺が一致するという対応関係と、特徴点の対応関係との両立性を判定しているのに他ならない。
つまり、計算式（２）の不等式において、左辺値が大きくなるということは、特徴点の検出状況を見る限り、各辺一致という方式１の前提である対応関係には無理があるということになる。
【０１０９】
計算式（２）の不等式が成り立つ場合、位置推定方式選択部３ａは方式１を選択する。方式１は、ｆ（ｅS1）＝ｅD1、ｆ（ｅS2）＝ｅD2、ｆ（ｅS3）＝ｅD3、ｆ（ｅS4）＝ｅD4を前提とする直交変換であるので、図１２の例に当てはめると、（ｘ’，ｙ’）＝ｆ（ｘ，ｙ）は、ｘ’＝０．５６２５ｘ及びｙ’＝０．５ｙとなる。
元画像の位置に対応する複製画像の位置を推定することは、写像ｆを推定することに他ならない。従って、この写像ｆが推定の結果であり、位置推定方式選択部３ａの出力となる。
【０１１０】
特徴点検出部５が特徴点を一つも検出しなかった場合、方式１は無条件に選択される。計算式（１）の不等式が成り立たない場合、位置推定方式選択部３ａは、図１３に示す候補リストの方式５以降の位置推定方式から選択を試みる。
【０１１１】
方式５は、元画像の上辺及び下辺が複製画像の上辺及び下辺にそれぞれ対応しており、元画像の上下方向及び左右方向が複製画像の上下方向及び左右方向となり、元画像の中心が複製画像の中心を通る上下方向の線上の点に対応し、複製画像から検出された一つ以上の特徴点が元画像に設定された一つ以上の特徴点に対応する位置関係を示す位置推定方式である。この方式５は、方式１と異なり、特徴点が一つも検出されなかった場合、写像ｆを特定できない。すなわち、方式５が採用されない。
【０１１２】
方式５において、ＰD2とＰD4の少なくとも一方及びＰD1とＰD3の少なくとも一方が検出された場合、下記式（３）に従う対応関係が前提となる。
ｆ（ｅS1）＝ｅD1、
ｆ（ｅS2）＝ｅD2、
ｘ（ｆ（ＰS1））
＝ｘ（ＣD）−（ｘ（ｍｉｄ（ＰD2ＰD4））−ｘ（ｍｉｄ（ＰD1ＰD3）））／２、
ｘ（ｆ（ＰS4））
＝ｘ（ＣD）＋（ｘ（ｍｉｄ（ＰD2ＰD4））−ｘ（ｍｉｄ（ＰD1ＰD3）））／２、ｆ（ＣS）＝ＣD
・・・（３）
【０１１３】
ここで、ｍｉｄ（ａ）は線分ａの中点である。線分ａの両端のうち、少なくとも一方が定義されていない（検出できなかった）場合、ｍｉｄ（ａ）は、定義されている方の点を表すものとする。なお、ｘ（Ａ）は点Ａのｘ座標を表している。図１２の例に当てはめると、Ｃs＝（３２０，２４０）、ＣD＝（１８０，１２０）である。
この場合、特徴点検出部５が検出した特徴点が、ＰD1＝（５９，８２）、ＰD2＝（３０２，７８）、ＰD3＝（６３，１６１）、ＰD4＝（２９８，１５７）であると、ｘ（ｆ（１６０，１２０））＝６０．５、ｘ（ｆ（４８０，３６０））＝２９９．５となって、（ｘ’，ｙ’）＝ｆ（ｘ，ｙ）は、ｘ’＝０．７４６８７５ｘ−５９及びｙ’＝０．５ｙとなる。
【０１１４】
上述の写像ｆを前提として、方式５の選択判断基準を、計算式（２）の不等式にて評価する。この不等式の評価は、元画像と複製画像との関係において、特徴点の対応関係と、特徴点以外の対応関係である、上下辺の一致、上下方向及び左右方向の一致、元画像の中心が複製画像の中心を通る上下方向の線の上の点という対応関係との両立性を判定しているのに他ならない。不等式が成り立てば、位置推定方式選択部３ａは方式５を選択する。
【０１１５】
これまで、ＰD2とＰD4の少なくとも一方及びＰD1とＰD3の少なくとも一方が検出されたものとして説明したが、方式５は、特徴点が一つ以上検出されていれば適用できる。例えば、ＰD3のみ検出された場合、ＰD2とＰD4がともに検出できなかった場合に相当するので、前提とする対応関係は、下記式（４）のようになる。
ｆ（ｅS1）＝ｅD1、
ｆ（ｅS2）＝ｅD2、
ｘ（ｆ（ＰS1））＝ｘ（ＰD3）、
ｆ（ＣS）＝ＣD
・・・（４）
【０１１６】
上記式（４）の前提で写像ｆを算出して、選択判断基準を、上記計算式（２）の不等式で評価する。この他の場合においても、図１３に従って写像ｆの算出及び選択判断基準の不等式評価を行う。このようにして、位置推定方式を吟味していき、方式１２の選択判断基準を満たさない場合は、方式１３を選択する。
【０１１７】
このように、実施の形態４による画像位置推定装置１Ｂは、位置推定方式選択部３ａによって、特徴点検出部５で複製画像から検出した特徴点の位置関係を計算し、この位置関係に応じて選択する位置推定方式を変更する。これにより、特徴点に応じた適切な位置推定方式を、その都度選択することができるので、元画像と複製画像との位置関係を推定する際の精度を向上できる。
【０１１８】
以上のように、この実施の形態４によれば、特徴点検出部５が、複製画像を画像解析して、当該複製画像で元画像に設定された特徴点に対応する特徴点を検出し、位置推定方式選択部３ａが、元画像の特徴点に対応して複製画像でとり得る特徴点の位置関係を選択基準として、元画像の辺及び特徴点と複製画像の辺及び当該複製画像から検出された特徴点との間で推定される対応関係がそれぞれ規定された複数の位置推定方式を有しており、特徴点検出部５によって複製画像から検出された特徴点の位置関係を解析した結果に基づいて、複数の位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択する。このように構成することでも、元画像と複製画像との位置合わせの精度を向上させることができる。
【０１１９】
なお、上記実施の形態４では、画像の画素値の最下位ビットに特徴点情報を与える方法によって元画像に特徴点を設定する場合を示した。この方法で特徴点を設定した場合に、階調（画素の深さ、ｄｅｐｔｈ）の削減、画像圧縮、画素値に低域通過フィルタが施される等により、最下位ビットの情報が書き換わる可能性がある。この場合は、特徴点情報の検出が困難となるかも知れない。これに対しては、上述の処理に対して耐性のある電子透かし技術で特徴点情報を与えることで、特徴点情報に強い画像処理耐性を持たせる。
【０１２０】
また、実施の形態４の画像位置推定装置１Ｂにおいても、元画像への特徴点の埋め込みに電子透かし技術を使用してもよく、元画像に特徴点を与える方法は任意の方法であってよい。但し、特徴点検出部５は、その特徴点埋め込み方法に応じた特徴点検出方法を備える必要がある。
【０１２１】
さらに、上記実施の形態４では、位置推定方式の選択判断基準の不等式を計算式（２）としたが、これは一例であり、他の式を採用してもよい。例えば、下記式（５）を、各位置推定方式の選択判断基準の不等式としても構わない。この不等式（５）は、選択判断基準の不等式として有用である。
｜ｆ（ＰS1）ＰD1｜＋｜ｆ（ＰS2）ＰD2｜＋｜ｆ（ＰS3）ＰD3｜＋｜ｆ（ＰS4）ＰD4｜≦α（ｆ（｜ｅS1｜）＋ｆ（｜ｅS3｜）） ・・・（５）
【０１２２】
また、上記実施の形態４において、位置推定方式ごとに異なる選択判断基準の不等式を採用してもよい。つまり、位置推定方式選択部３ａは、元画像と複製画像との関係において、特徴点の対応関係と特徴点以外の対応関係との両立性を判定する任意の方法を採用した構成を適用できる。
【０１２３】
さらに、上記実施の形態４の構成に対して上記実施の形態１で示した境界線推定部２を備え、位置推定方式選択部３ａが、元画像の特徴点に対応して複製画像でとり得る特徴点の位置関係を選択基準として、元画像に設定された特徴点と複製画像から検出された特徴点との間で推定される対応関係が規定された位置推定方式と、複製画像でとり得る境界線の位置関係及び元画像の特徴点に対応して複製画像でとり得る特徴点の位置関係を選択基準として、元画像の辺と複製画像の辺又は境界線との間で推定される対応関係と、元画像に設定した特徴点と複製画像から検出された特徴点との対応関係が規定された位置推定方式と、複製画像でとり得る境界線の位置関係及び元画像の特徴点に対応して複製画像でとり得る特徴点の位置関係を選択基準として、元画像の辺と複製画像の辺との間で推定される対応関係と、元画像に設定された特徴点と複製画像から検出された特徴点との対応関係が規定された位置推定方式とを有しており、境界線推定部２によって複製画像から推定された境界線の位置関係又は特徴点検出部５によって複製画像から検出された特徴点の位置関係を解析した結果に基づいて、自身が有する位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択する。このように構成することで、さらに元画像と複製画像との位置合わせの精度を向上させることができる。
【０１２４】
実施の形態５．
この実施の形態５では、上記実施の形態４の特徴点検出部５を備えた電子透かし検出装置について説明する。
図１４は、この発明の実施の形態５による電子透かし検出装置の構成を示すブロック図である。図１４において、実施の形態５の電子透かし検出装置１Ｃは、元画像と元画像を複製した複製画像において、一方の画像の任意な位置に対応する他方の画像の位置の対応関係を推定し、この対応関係を基に電子透かし情報を検出して電子透かし情報及び電子透かし情報検出の成否を出力する装置である。
なお、電子透かし検出装置１Ｃに扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態５で扱われる画像が複製されたものであることを、電子透かし検出装置１Ｃの動作要件とするものではない。
【０１２５】
図１４に示すように、電子透かし検出装置１Ｃは、特徴点検出部５、位置推定方式選択部３ａ及び電子透かし情報検出部４を備える。ここで、特徴点検出部５及び位置推定方式選択部３ａは、上記実施の形態４で図１０を用いて説明した構成と同様である。また、電子透かし情報検出部４は、上記実施の形態３で図７を用いて説明した構成と同様である。
【０１２６】
次に動作について説明する。
図１５は、実施の形態５の電子透かし検出装置による動作の流れを示すフローチャートであり、画像位置の推定及び電子透かし検出手順の一例を示している。以降では、図１４に示す構成を、図１５に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、特徴点検出部５、位置推定方式選択部３ａ及び電子透かし情報検出部４にそれぞれ入力される。特徴点検出部５は、入力した複製画像を画像解析することにより、この複製画像の元画像に予め埋め込んであった特徴点を検出する（ステップＳＴ１ｃ；特徴点検出ステップ）。特徴点検出部５による特徴点検出は、上記実施の形態４と同様である。
【０１２７】
位置推定方式選択部３ａは、得られた複製画像及び特徴点検出部５が判断した０個以上の特徴点を解析し、元画像と複製画像との位置関係を推定する方式のうち、当該複製画像に適したものを選択する（ステップＳＴ２ｃ；位置推定方式選択ステップ）。位置推定方式選択部３ａの処理は、上記実施の形態４と同様であるが、複製画像に適した位置推定方式が特定できなかった際の選択やり直しの処理が異なる。この処理については後述する。
【０１２８】
続いて、電子透かし情報検出部４が、位置推定方式選択部３により選択された位置推定方式に基づいて、複製画像と元画像との位置関係の対応付けを行い、この位置関係から、電子透かし情報の検出処理を行う（ステップＳＴ３ｃ；電子透かし情報検出ステップ）。
【０１２９】
次に、電子透かし情報検出部４は、電子透かし情報の検出の成否を判断する（ステップＳＴ４ｃ；成否判断ステップ）。実施の形態５においても、電子透かし情報が誤り検出符号を含んでいるとした場合、電子透かし情報検出部４は、電子透かし情報の検出処理で得られた誤り検出符号から電子透かし情報の検出の成否を判断する。
【０１３０】
電子透かし情報検出部４にて電子透かし情報の検出に失敗すると（ステップＳＴ４ｃ；失敗）、位置推定方式選択部３ａは、まだ選択していない選択可能な位置推定方式が残っているか否かを判定する（ステップＳＴ５ｃ；選択可否判定ステップ）。
このとき、選択可能な位置推定方式が残っていれば（ステップＳＴ５ｃ；ＹＥＳ）、ステップＳＴ２ｃの処理に戻り、位置推定方式選択部３ａが、残りの位置推定方式を選択し、選択可能な残りの位置推定方式が無くなるまで（ステップＳＴ５ｃ；ＮＯ）、ステップＳＴ２ｃ以降の処理を繰り返す。
【０１３１】
このように、実施の形態５の電子透かし検出装置１Ｃは、電子透かし情報の検出に失敗すると、位置推定方式の選択からやり直す。このようにすることで、もし最初に選択した位置推定方式が不適切であったとしても、より適切な位置推定方式を選んで、電子透かし情報の検出をやり直すことができる。これにより、位置推定方式の選択及び電子透かし情報の検出をそれぞれ一度しか実施しない構成と比べて、電子透かし情報の検出成功率を向上させることができる。
【０１３２】
位置推定方式選択部３ａは、２度目以降の位置推定方式の選択において、以前に選択した位置推定方式を選択肢から外し、その上で、１度目と同じ手順で位置推定方式を一つ選択する。選択された位置推定方式を使用して電子透かし情報検出部４が再度電子透かし情報の検出を試みる。この処理を、用意された位置推定方式（例えば、図１３に示す方式１、方式５から方式９、方式１２、方式１３）のうち、選択可能な位置推定方式の候補がなくなった上で、電子透かし情報の検出に失敗したら、位置推定方式選択部３ａは、最終的に電子透かし情報の検出を失敗として終了する。
【０１３３】
図１３に示す候補リストの中の方式１、方式５から方式９、方式１２、方式１３の位置推定方式から選択する場合を例に挙げて、具体的に位置推定方式の選択やり直しの手順を説明する。
位置推定方式選択部３ａは、方式１を選択した後に位置推定方式の選択をやり直す場合、方式１を選択肢から除き、方式５から方式９、方式１２、方式１３の中から選択する。
方式５の選択基準を満たしていれば方式５を、そうでなければ、方式６以降の選択判断基準を満たしているかどうかを順に計算し、選択判断基準を満たしている方式のうち、最も方式番号の若い方式を選択する。
【０１３４】
さらに位置推定方式選択をやり直す場合、位置推定方式選択部３ａは、それまで選んだ選択肢を全て除外し、残った位置推定方式のうち選択可能のものがなくなるか、電子透かし情報の検出に成功するまで、位置推定方式選択を繰り返す。
なお、特徴点検出部５が検出した特徴点の数によって、位置推定方式の選択が異なる。特徴点が一つも検出されなかった場合は、方式１しか選択できない。従って、この場合に方式１を選択した後は、選択可能な位置推定方式が残っていないので、位置推定方式選択部３ａは、処理を終了する。
特徴点が１つだけ検出された場合は、選択可能な位置推定方式は、方式１、方式５から方式７の４方式のみである。特徴点が２つ又は３つ検出された場合、方式１、方式５から方式９、方式１２の７つの方式が選択可能である。特徴点が４つ検出された場合のみ、これらに加えて方式１３が選択可能となる。
【０１３５】
以上のように、この実施の形態５によれば、位置推定方式選択部３ａにより選択された位置推定方式から、元画像と複製画像との間で位置の対応付けを行い、この対応関係に基づいて、元画像で電子透かし情報が埋め込まれた箇所に対応すると推定される複製画像の位置を特定して、当該複製画像から電子透かし情報を検出する電子透かし情報検出部４を備える。このように構成することで、元画像と複製画像との位置合わせが正確に行われ、電子透かし情報検出の成功率を高めることができる。
【０１３６】
また、上記実施の形態５によれば、位置推定方式選択部３ａが、特徴点検出部５にて複製画像から検出された特徴点の位置関係を計算し、選択する位置推定方式を変更する上、電子透かし情報の検出に失敗すると、位置推定方式の選択をやり直すことができる。
このため、特徴点を有効に活用して元画像と複製画像との位置関係を推定する際の精度を向上させつつ、位置推定方式の再選択により最終的な電子透かし情報の検出率を向上させることができる。
【０１３７】
実施の形態６．
この実施の形態６では、上記実施の形態１の境界線推定部２及び上記実施の形態４の特徴点検出部５を備えた電子透かし検出装置について説明する。
図１６は、この発明の実施の形態６による電子透かし検出装置の構成を示すブロック図である。図１６において、実施の形態６の電子透かし検出装置１Ｄは、元画像と元画像を複製した複製画像において、一方の画像の任意な位置に対応する他方の画像の位置の対応関係を推定し、この対応関係を基に電子透かし情報を検出して電子透かし情報及び電子透かし情報検出の成否を出力する装置である。
なお、電子透かし検出装置１Ｄに扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態６で扱われる画像が複製されたものであることを、電子透かし検出装置１Ｄの動作要件とするものではない。
【０１３８】
また、図１６に示すように、電子透かし検出装置１Ｄは、境界線推定部２、特徴点検出部５、位置推定方式選択部３ｂ及び電子透かし情報検出部４を備える。ここで、境界線推定部２は、上記実施の形態１で図１を用いて説明した構成と同様である。また、電子透かし情報検出部４は、上記実施の形態３で図７を用いて説明した構成と同様であり、特徴点検出部５は、上記実施の形態４で図１０を用いて説明した構成と同様である。
【０１３９】
位置推定方式選択部３ｂは、複製画像と元画像との間で推定され得る位置関係を示し、かつ複製画像と元画像に予め埋め込んだ特徴点との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式を有し、複製画像と境界線推定部２で推定した境界線とを解析した結果に基づいて、複数の位置推定方式のうち、対象画像に対応する位置推定方式を選択するとともに、複製画像と特徴点検出部５で検出された特徴点とを解析した結果に基づいて、対象画像に対応する位置推定方式を選択する構成部である。
【０１４０】
次に動作について説明する。
図１７は、実施の形態６の電子透かし検出装置による動作の流れを示すフローチャートであり、画像位置の推定及び電子透かし検出手順の一例を示している。以降では、図１６に示す構成を、図１７に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、境界線推定部２、位置推定方式選択部３ｂ、特徴点検出部５及び電子透かし情報検出部４にそれぞれ入力される。境界線推定部２は、入力した複製画像を画像解析することで、この複製画像の元画像に含まれる領域と含まれない領域との境界線として、上境界線、下境界線、左境界線、右境界線を推定する（ステップＳＴ１ｄ；境界線推定ステップ）。境界線推定部２による境界線の推定は、上記実施の形態１と同様である。
【０１４１】
特徴点検出部５は、入力した複製画像を画像解析することで、この複製画像の元画像に予め埋め込んであった特徴点を検出する（ステップＳＴ２ｄ；特徴点検出ステップ）。特徴点検出部５による特徴点検出は、上記実施の形態４と同様である。
【０１４２】
位置推定方式選択部３ｂは、得られた複製画像、境界線推定部２が推定した上境界線、下境界線、左境界線、右境界線、特徴点検出部５が検出した０個以上の特徴点を解析し、元画像と複製画像との位置関係を推定する位置推定方式のうち、当該複製画像に適したものを選択する（ステップＳＴ３ｄ；位置推定方式選択ステップ）。
【０１４３】
ここでは、説明上の便宜のため、上記実施の形態４の図１２を例に挙げて説明する。
図１２において、元画像の上辺、下辺、左辺、右辺を、それぞれ線分ｅS1、線分ｅS2、線分ｅS3、線分ｅS4とする。元画像の中心を点ＣSとする。元画像の４つの特徴点の中心を、左上、右上、左下、右下の順にそれぞれ点ＰS1、点ＰS2、点ＰS3、点ＰS4とする。また、複製画像の上辺、下辺、左辺、右辺を、それぞれ線分ｅD1、線分ｅD2、線分ｅD3、線分ｅD4とする。複製画像の中心を点ＣDとする。複製画像から検出された特徴点のうち、特徴点検出部５によって相対的に左上、右上、左下、右下の位置にあると判断されたものを、それぞれ点ＰD1、点ＰD2、点ＰD3、点ＰD4とする。
【０１４４】
境界線推定部２によって推定された上境界線、下境界線、左境界線、右境界線を、それぞれ線分ｂD1、ｂD2、ｂD3、ｂD4とする。この実施の形態６では、位置推定方式選択部３ｂが選択する位置推定方式は、図１３の候補リストにおける方式１から方式１３までの１３通りとする。
【０１４５】
位置推定方式選択部３ｂは、方式１から順に選択判断基準を満たすかどうかを確認し、満たす場合はその方式を選択し、満たさない場合は次の方式が選択判断基準を満たすかどうかを確認する。これを繰り返して、方式１から方式１２までの全ての方式で選択判断基準を満たさない場合は方式１３を選択する。
【０１４６】
このようにして位置推定方式を選択することにより、特徴点検出部５が検出した特徴点の個数に応じて採用する位置推定方式が適切に選択される。検出された特徴点が０個の場合は、方式１が選択される。検出された特徴点が１個の場合は、方式１から方式７までの位置推定方式の中から選択される。これは、検出された特徴点が１個の場合に方式７の選択判断基準を必ず満たす（不等式左辺が０になる）からである。
【０１４７】
検出された特徴点が２個又は３個の場合、方式１２まで選択判断基準を満たさない可能性がある。この場合、位置推定方式選択部３ｂは、特徴点検出部５に検出された特徴点の組み合わせに対して適用可能な位置推定方式のうち、方式番号が最後のものを選択する。
例えば、ＰD1、ＰD2、ＰD4が検出され、方式１２まで選択判断基準を満たさない場合は、方式１２を選択する。ＰD1、ＰD2が検出され、方式１０まで選択判断基準を満たさない場合は、方式１０を選択する（方式１１と方式１２は適用できないため）。検出された特徴点が４個の場合は、方式１２まで選択判断基準を満たさない場合は、方式１３を選択するものとする。
【０１４８】
図１７のフローチャートの説明に戻る。
電子透かし情報検出部４は、位置推定方式選択部３ｂが選択した位置推定方式を基に、複製画像と元画像との位置関係の対応付けを行い、この位置関係から、電子透かし情報の検出処理を行う（ステップＳＴ４ｄ；電子透かし情報検出ステップ）。
次に、電子透かし情報検出部４は、電子透かし情報の検出の成否を判断する（ステップＳＴ５ｄ；成否判断ステップ）。
【０１４９】
元画像の特定の位置に電子透かし情報が埋め込まれている場合、電子透かし情報検出部４は、位置推定方式選択部３ｂが選択した位置推定方式に基づいて、複製画像と元画像との位置関係の対応付けを認識して電子透かし情報を検出する。実施の形態６においても、電子透かし情報が誤り検出符号を含んでいるとした場合、電子透かし情報検出部４は、電子透かし情報の検出処理で得られた誤り検出符号から電子透かし情報の検出の成否を判断する。
【０１５０】
電子透かし情報検出部４にて電子透かし情報の検出に失敗すると（ステップＳＴ５ｄ；失敗）、位置推定方式選択部３ｂは、まだ選択していない選択可能な位置推定方式が残っているか否かを判定する（ステップＳＴ６ｄ；選択可否判定ステップ）。
このとき、選択可能な位置推定方式が残っていれば（ステップＳＴ６ｄ；ＹＥＳ）、ステップＳＴ３ｄの処理に戻り、位置推定方式選択部３ｂが、残りの位置推定方式を選択し、選択可能な残りの位置推定方式が無くなるまで（ステップＳＴ６ｄ；ＮＯ）、ステップＳＴ３ｄ以降の処理を繰り返す。
【０１５１】
このように、実施の形態６の電子透かし検出装置１Ｄは、電子透かし情報の検出に失敗すると、位置推定方式の選択からやり直す。このようにすることで、もし最初に選択した位置推定方式が不適切であったとしても、より適切な位置推定方式を選んで、電子透かし情報の検出をやり直すことができる。これにより、位置推定方式の選択及び電子透かし情報の検出をそれぞれ一度しか実施しない構成と比べて、電子透かし情報の検出成功率を向上させることができる。
【０１５２】
位置推定方式選択部３ｂは、２度目以降の位置推定方式の選択において、以前に選択した位置推定方式を選択肢から外し、その上で、１度目と同じ手順で位置推定方式を一つ選択する。選択された位置推定方式を使用して電子透かし情報検出部４が再度電子透かし情報の検出を試みる。この処理を、用意された位置推定方式（例えば、図１３に示す方式１から方式１３）のうち、特徴点の数に応じて使用可能な位置推定方式を全て選択し終え、選択可能な位置推定方式の候補がなくなった上で、電子透かし情報の検出に失敗すると、最終的に電子透かし情報の検出が失敗したものとして処理を終了する。
【０１５３】
以上のように、この実施の形態６では、境界線推定部２が、複製画像を画像解析して、複製画像で元画像に含まれる画像領域と元画像に含まれない画像領域との境界線を推定するとともに、特徴点検出部５が、複製画像を画像解析して、当該複製画像で元画像に設定された特徴点に対応する特徴点を検出し、位置推定方式選択部３ｂが、境界線推定部２によって複製画像から推定された境界線の位置関係又は特徴点検出部５によって複製画像から検出された特徴点の位置関係を解析した結果に基づいて、自身が有する位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択して、電子透かし情報検出部４が、選択された位置推定方式から、元画像と複製画像との間で位置の対応付けを行い、この対応関係に基づいて、元画像で電子透かし情報が埋め込まれた箇所に対応すると推定される複数画像の位置を特定して、当該複数画像から電子透かし情報を検出する。このように構成することで、元画像と複製画像との位置合わせが正確に行われ、電子透かし情報検出の成功率を高めることができる。
【０１５４】
上記実施の形態６では、位置推定方式選択部３ｂにより選択可能な各位置推定方式が、図１３に示す対応関係を前提とする場合を示したが、これは一例であって、他の対応関係を前提としてもよい。
例えば、最小二乗誤差法（最小二乗法）を適用して対応関係を設定する方法もある。
この方法は、図１３に示す選択判断基準の不等式の左辺値が、右辺値に対して小さくなるように写像ｆを決定することに他ならない。このような対応関係の設定の仕方は複数通りあり、どの方法で装置１Ｄに設定しても構わない。
【０１５５】
また、画像に設定される特徴点が４つである場合を示したが、それ以外の個数の特徴点を元画像に埋め込んでも構わない。
例えば、特徴点をＰS1一つだけしか埋め込まない方法を前提として、装置１Ｄを構成することも可能である。この場合、特徴点が一つしかないので、方式１から方式７までしか適用できない。このため、位置推定方式選択部３ｂは、方式１から方式７までの位置推定方式から位置推定方式を選択する。
また、この場合は、選択判断基準である上記計算式（２）の不等式の左辺は、第１項のみ評価し、第２項から第４項を０として扱えばよい。特徴点を２つあるいは３つとする場合も同様に、適用可能な位置推定方式のみを選択肢とし、選択判断基準の不等式の左辺で無関係な項を無視すればよい。
さらに、特徴点を５つ以上とすることもできる。この場合は、選択判断基準の不等式の左辺は、それぞれの特徴点の誤差二乗和となるため、全５項となる。
元画像に特徴点が５つ以上埋め込まれている場合は、特徴点検出部５が、複製画像から５つ以上の特徴点を検出する可能性があるが、このとき、方式５から方式１３において、写像ｆを適切に推定する対応関係を設定しなければならない。このような場合、最小二乗誤差法を適用するなどして、得られた特徴点の全てから推定される最も確からしい写像ｆを決定すればよい。
【０１５６】
また、特徴点を使用しない実装も可能である。この場合は、特徴点を必要とする方式５から方式１３は適用できない。方式１から方式４の４つの選択肢から位置推定方式を選択することになる。しかし、特徴点がないため、位置推定方式の選択判断をすることができない。
このような場合、位置推定方式選択部３ｂは、方式１から順に選択する。
方式１に基づいて電子透かし情報検出部４が電子透かし検出に失敗すると、位置推定方式選択部３ｂは、次に方式２、またその次に方式３と順番に位置推定方式を選択し、選択された位置推定方式に基づいて、電子透かし情報検出部４が、電子透かし情報の検出を試みる。この後、電子透かし情報検出部４が、方式４に基づく電子透かし情報の検出に失敗すると、最終的に電子透かし情報の検出が失敗としたと判断して処理を終了する。
以上のように、元画像に埋め込む特徴点の数に制限はないため、元画像に設定する特徴点の数に応じて適切に特徴点検出部５及び位置推定方式選択部３ｂを構成すれば、任意個の特徴点を使用する電子透かし検出装置１Ｄを構成可能である。
【０１５７】
上述の説明では、元画像に設定する特徴点の位置は、図１２に示したように、長方形の元画像の、上から４分の１で、かつ左から４分の１の位置、上から４分の１で、かつ右から４分の１の位置、下から４分の１で、かつ左から４分の１の位置、下から４分の１で、かつ右から４分の１の位置としたが、長方形の元画像に対する相対的な位置さえ明確であれば、特徴点の位置は任意とすることができる。
さらに、画像に設定されている特徴点の形状が円である場合を示したが、三角形や四角形など、他の形状でもよく、任意の形状とすることができる。
このように、特徴点の位置や形状に制限はないため、元画像に設定する特徴点の位置や形状に応じて適切に特徴点検出部５及び位置推定方式選択部３ｂを構成すれば、元画像上の任意の位置にある、任意の形状の特徴点を使用する電子透かし検出装置１Ｄを構成することができる。
【０１５８】
また、位置推定方式選択部３ｂが選択した位置推定方式は、電子透かし情報検出部４に出力されるが、位置推定方式が選択されたということは、この位置推定方式が前提とする対応関係が選択されたことを意味し、写像ｆも特定される。
従って、電子透かし情報検出部４は、位置推定方式選択部３ｂで選択された位置推定方式を受け取ることにより、写像ｆについての情報を取得している。
【０１５９】
このような、位置推定方式選択部３ｂと電子透かし情報検出部４との間の情報のやり取りは、具体的には様々な実現方法が可能である。
一つは、射影変換を前提として、位置推定方式選択部３ｂから電子透かし情報検出部４には、射影変換ｆを一意に特定するパラメータ群のみを渡す方法が考えられる。
方式１から方式１３までの全位置推定方式は全て射影変換であり、直交変換や直交変換と平行移動の組み合わせは、数学的には射影変換の特別な場合に相当する。
よって、上記のようにパラメータのみを渡す実装が可能である。この場合、方式番号を位置推定方式選択部３ｂから電子透かし情報検出部４に渡す必要はなく、また、電子透かし情報検出部４が、図１３に示すような位置推定方式の候補リストを保持する必要もないため、実装が簡略化される。
この他には、位置推定方式選択部３ｂが、選択した位置推定方式に基づいて、元画像の画素と複製画像の画素とのマッピング情報を作成し、これを電子透かし情報検出部４に渡す方法である。
このようにしても、位置推定方式選択部３ｂは、選択した位置推定方式を電子透かし情報検出部４に伝えたことになる。電子透かし情報検出部４では、位置推定方式選択部３ｂから入力したマッピング情報を基に、元画像と複製画像との位置関係を把握し、元画像のある特定の場所に埋め込まれた電子透かし情報の検出を試みることが可能である。
なお、この場合、電子透かし情報検出部４は、改めて写像ｆを用いた位置推定の計算をする必要がなくなるため、処理が高速化される。
【０１６０】
勿論、位置推定方式選択部３ｂから電子透かし情報検出部４に方式番号を渡すように実装することもできる。この場合は、電子透かし情報検出部４は、写像ｆを特定できないため、位置推定方式選択部３ｂは、方式番号に加えて、特徴点の情報も渡さなければならない。電子透かし情報検出部４は、位置推定方式選択部３ｂから受け取った方式番号と特徴点の情報を使用して、図１３のような位置推定方式の候補リストを参照し、位置推定方式を選択するための選択判断の計算を改めて行う必要がある。
このように、位置推定方式は、その方式番号だけを指すのではなく、画像の位置を推定する指針として、写像ｆを特定するのに必要となる情報である。
【０１６１】
上記実施の形態６では、位置推定方式選択部３ｂが、図１３に示す候補リストのうち、方式１から方式１３を方式１から順に選択判断基準を満たすかどうか判定し、満たす場合にそれ以降の方式の選択判断を行わない場合を示した。
この場合についても他の処理が考えられる。例えば、位置推定方式選択部３ｂが、境界線推定部２に推定された境界線及び特徴点検出部５に検出された特徴点から、適用可能な位置推定方式の全てにおいて下記式（６）を計算し、この計算結果が小さいものから優先して選択する。
（｜ｆ（ＰS1）ＰD1｜2＋｜ｆ（ＰS2）ＰD2｜2＋｜ｆ（ＰS3）ＰD3｜2＋｜ｆ（ＰS4）ＰD4｜2）／（ｆ（｜ｅS1｜）2＋ｆ（｜ｅS3｜）2）
・・・（６）
【０１６２】
上述の選択方法を採用することで、図１３に示す候補リストにおいて、方式番号が下位に位置する位置推定方式であっても、優先して選択することができる。これにより、電子透かし情報の検出完了までに必要な位置推定方式の選択やり直し回数が低減する可能性がある。
【０１６３】
また、単に上記式（６）の計算値が小さいものから優先して選択するのでなく、上記式（６）の計算値がα2を超えた時点で、適用可能な位置推定方式が残されていても処理を打ち切るようにしてもよい。このようにすることで、電子透かし情報の検出成功の可能性が低い場合に、成功する可能性の低い位置推定方式の選択及び電子透かし情報の検出の試行を抑制することができ、全体の計算量を削減できる。
勿論、上記式（６）に限らず、他の計算式を使用することもできる。さらに、位置推定方式の選択やり直し回数に上限を設け、選択可能な位置推定方式が残されていても処理を打ち切ることも可能である。このようにしても、成功する可能性の低い位置推定方式の選択及び電子透かし情報の検出の試行を抑制することができ、全体の計算量を削減できる。
【０１６４】
さらに、これまでの説明は、画像の画素値の最下位ビットを使用して特徴点を設定する場合を示したが、この方法では、特徴点の一つ一つを区別できない。このため、特徴点検出部５が、元画像の、左上、右上、左下、右下に特徴点が設定される前提で、複製画像の左上の特徴点（ＰD1）、右上の特徴点（ＰD2）、左下の特徴点（ＰD3）、右下の特徴点（ＰD4）をそれぞれ元画像の左上の特徴点（ＰS1）、右上の特徴点（ＰS2）、左下の特徴点（ＰS3）、右下の特徴点（ＰS4）に対応すると判断した。
【０１６５】
これに対して、電子透かし技術を利用して、検出時に検出された特徴点が元画像の特徴点のどれに対応するのかを判定できる特徴点埋め込み方法をとった場合には、ＰS1に相当する特徴点が複製画像の左下から検出され、ＰS3に相当する特徴点が複製画像の左上から検出される可能性もある。この場合、左下にＰD1、左上にＰD3が検出されるため、例えば、元画像の上辺、下辺、左辺、右辺が、それぞれ複製画像の上辺、下辺、左辺、右辺に対応する位置関係を示す位置推定方式よりも、元画像の上辺、下辺、左辺、右辺が、それぞれ複製画像の下辺、上辺、左辺、右辺に対応する位置関係を示す位置推定方式が採用される。このような位置推定方式は図１３の候補リストにはないが、特徴点を区別する場合には設けることが望ましい。
【０１６６】
上述の位置推定方式が示す位置関係は、複製の過程で元画像が上下反転した場合に起こり得る。特徴点を位置推定方式上で区別しない場合、画像の上下反転は検出できないが、検出された個々の特徴点が元画像の特徴点のどれに対応するか判定できるように挿入されていれば、上下反転を検出して、適切な位置推定を行うことができる。
特徴点が区別できれば、上下反転のみならず、左右反転、上下左右反転、９０度回転、１８０度回転などの検出も可能となる。
従って、位置推定方式にて個々の特徴点を区別する情報を与えておき、これに基づいて特徴点検出部５が特徴点を区別して検出し、位置推定方式選択部３ｂが区別ある特徴点を使用して適切に位置推定方式を選択することにより、複製画像に反転や回転の処理が加えられていても、元画像との適切な位置推定が可能である。
【０１６７】
さらに、これまでの説明では、位置推定方式を、図１３の候補リストから選択する場合を示したが、位置推定方式選択部３，３ａ，３ｂが、図１３に記載のもの以外の位置推定方式を用意し、選択肢とすることもできる。例えば、前段落で述べた、反転や回転に対応した位置推定方式を選択肢として用意することができる。
この他、図１３に記載していないが、元画像の上辺が複製画像の上境界線に、元画像の左辺が複製画像の左辺にそれぞれ対応し、元画像の上下方向及び左右方向がそれぞれ複製画像のちょうど上下方向及び左右方向となり、複製画像から検出された一つ以上の特徴点が元画像に設定された一つ以上の特徴点のどれか一つに対応するとする対応関係を前提とする位置推定方式が考えられる。
【０１６８】
また、元画像の上辺及び下辺が、複製画像の上境界線及び下境界線にそれぞれ対応し、元画像の中心が、複製画像において元画像に含まれると推定された領域の中心を通る上下方向の線上の点に対応しており、元画像の上下方向及び左右方向が、複製画像のちょうど上下方向及び左右方向にそれぞれ対応し、複製画像から検出された一つ以上の特徴点が元画像に設定された一つ以上の特徴点のどれか一つに対応するという対応関係を前提とする位置推定方式なども考えられる。
【０１６９】
さらに、図１３で示した方式１から方式１３の位置推定方式では、直線は必ず直線に写像されるが、直線が曲線に歪むような強烈な歪みが複製の過程で与えられても複製画像から元画像の位置を推定できる位置推定方式を選択肢として用意してもよい。
例えば、カメラ撮影で元画像が複製された場合に、カメラのレンズ歪の補正をモデル化した写像を取り入れた位置推定方式を選択肢として加える。これにより、カメラのレンズ歪まで考慮した精度の高い位置推定が可能となる。
このように、位置推定方式選択部３，３ａ，３ｂが選択肢として用意する位置推定方式は、任意に設定可能である。
【符号の説明】
【０１７０】
１，１Ｂ 画像位置推定装置、１Ａ，１Ｃ，１Ｄ 電子透かし検出装置、２ 境界線推定部、３，３ａ，３ｂ 位置推定方式選択部、４ 電子透かし情報検出部、５ 特徴点検出部。
【技術分野】
【０００１】
この発明は、複製前の画像と複製後の画像の位置関係を推定する画像位置推定装置、複製前後の画像で推定された位置関係を基に電子透かし情報を検出する電子透かし検出装置及びこれらの方法並びにこれらの装置としてコンピュータを機能させるためのプログラムに関するものである。
【背景技術】
【０００２】
画像を複製する過程で編集等の処理を施して変形すると、複製前の画像を参照できない場合、複製前の画像と複製後の画像との位置関係が特定できないことがある。
一方、編集を一切行わないデジタル複製の場合や、コントラスト調整等の軽微な補正は行うが、画像の切取（トリミング）や拡大縮小を施さない場合には、複製前の画像と複製後の画像との位置関係は完全に保存される。
すなわち、複製前の画像の左上から横にｘ画素目、縦にｙ画素目の位置は、複製後の画像の左上から横にｘ画素目、縦にｙ画素目の位置に対応する。
しかしながら、一般的には、画像を複製する過程において、編集により、切取、拡大縮小、アスペクト比（縦横比）の変更が加えられる場合が多い。
【０００３】
また、映画の海賊版を得るため、映画館のスクリーンに投影された画像をビデオカメラで撮影して画像を複製した場合、複製後の画像に射影変換（透視投影変換）が加わって、長方形のスクリーンの画像が歪む。
このような場合に、複製前の画像を参照せずに、複製後の画像のみから複製前の画像との位置関係を特定することを可能にした従来の技術が、特許文献１及び特許文献２に開示されている。
特許文献１，２の技術では、複製後の画像から電子透かしを検出する際、射影変換を利用して複製前の画像と複製後の画像との位置合わせを行う。なお、複製前の画像と複製後の画像との位置合わせに関する技術自体は、電子透かし検出に適用先が限定されるものではない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００４−１２９２５９号公報
【特許文献２】特開２００９−１００２９６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来では、射影変換を利用することにより、数学的には複製前の画像と複製後の画像との位置合わせが可能である。しかしながら、射影変換のみを利用するため、位置合わせを高い精度で行うことができないという課題があった。
【０００６】
ここで、画像に埋め込まれた電子透かし情報を検出することを目的として、電子透かし情報を埋め込んだ際の画像（複製前の画像）と、これを複製した後に流通した画像（複製後の画像）との間で位置合わせを行う場合を例に挙げる。
【０００７】
この場合、位置合わせのための射影変換で使用する画像中の特徴点自体が、電子透かし技術によって画像に埋め込まれていると、検出された特徴点には、位置的な誤差が含まれている可能性がある。従って、検出された特徴点をそのまま利用して射影変換を行うと、複製前の画像と複製後の画像との位置合わせに誤差が生じる要因となり得る。
【０００８】
さらに、複製後の画像の多くが、射影変換歪みを被るまで手を加えられていないことを考慮すると、位置合わせの際、特徴点の位置的な誤差に起因して、射影変換歪みが無駄に加わり、複製前の画像と複製後の画像との位置合わせ結果における誤差を助長する可能性もある。
【０００９】
この発明は、上記のような課題を解決するためになされたもので、複製前の画像と複製後の画像との位置合わせの精度を向上させることができる画像位置推定装置、複製前後の画像で推定された位置関係を基に電子透かし情報を検出する電子透かし検出装置及びこれらの方法、並びにこれらの装置としてコンピュータを機能させるためのプログラムを得ることを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係る画像位置推定装置は、第２の画像を画像解析して、当該第２の画像で第１の画像に含まれる画像領域と第１の画像に含まれない画像領域との境界線を推定する境界線推定部と、第２の画像でとり得る境界線の位置関係を選択基準として、第１の画像の辺と第２の画像の辺又は境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、境界線推定部によって第２の画像から推定された境界線の位置関係を解析した結果に基づいて、複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択部を備えるものである。
【００１１】
この発明に係る電子透かし検出装置は、上記画像位置推定装置と、画像位置推定装置の選択部により選択された位置推定情報から、第１の画像と第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される第２の画像の位置を特定して、当該第２の画像から電子透かし情報を検出する電子透かし情報検出部とを備えるものである。
【発明の効果】
【００１２】
この発明の画像位置推定装置によれば、境界線推定部が、第２の画像を画像解析して、当該第２の画像で第１の画像に含まれる画像領域と第１の画像に含まれない画像領域との境界線を推定し、選択部が、第２の画像でとり得る境界線の位置関係を選択基準として、第１の画像の辺と第２の画像の辺又は境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、境界線推定部によって第２の画像から推定された境界線の位置関係を解析した結果に基づいて、複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する。このように構成することにより、元画像である第１の画像とこれを元に生成された画像中に第１の画像の全部又は一部を含む第２の画像との位置合わせの精度を向上させることができるという効果がある。
【００１３】
この発明の電子透かし検出装置によれば、上記選択部によって選択された位置推定情報から、第１の画像と第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される第２の画像の位置を特定して、当該第２の画像から電子透かし情報を検出する。このように構成することで、第１の画像と画像中に第１の画像の全部又は一部を含む第２の画像との位置合わせが正確に行われ、電子透かし情報検出の成功率を高めることができるという効果がある。
【図面の簡単な説明】
【００１４】
【図１】この発明の実施の形態１による画像位置推定装置の構成例を示すブロック図である。
【図２】実施の形態１の画像位置推定装置による動作の流れを示すフローチャートである。
【図３】境界線の推定処理を説明するための図である。
【図４】実施の形態１における位置推定方式の一例を示す図である。
【図５】実施の形態２における境界線の推定処理を説明するための図である。
【図６】実施の形態２における位置推定方式の一例を示す図である。
【図７】この発明の実施の形態３による電子透かし検出装置の構成を示すブロック図である。
【図８】実施の形態３の電子透かし検出装置による動作の流れを示すフローチャートである。
【図９】実施の形態３における位置推定方式の一例を示す図である。
【図１０】この発明の実施の形態４による画像位置推定装置の構成を示すブロック図である。
【図１１】実施の形態４の画像位置推定装置による動作の流れを示すフローチャートである。
【図１２】実施の形態４における特徴点の検出処理を説明するための図である。
【図１３】実施の形態４における位置推定方式の一例を示す図である。
【図１４】この発明の実施の形態５による電子透かし検出装置の構成を示すブロック図である。
【図１５】実施の形態５の電子透かし検出装置による動作の流れを示すフローチャートである。
【図１６】この発明の実施の形態６による電子透かし検出装置の構成を示すブロック図である。
【図１７】実施の形態６の画像位置推定装置による動作の流れを示すフローチャートである。
【発明を実施するための形態】
【００１５】
実施の形態１．
図１は、この発明の実施の形態１による画像位置推定装置の構成例を示すブロック図である。図１において、実施の形態１の画像位置推定装置１は、複製前の画像（以下、元画像と呼称する）（第１の画像）とこの画像を複製した画像（以下、複製画像と呼称する）（第２の画像）において、一方の画像の任意な位置に対応する他方の画像の位置を推定する装置である。
なお、この画像位置推定装置１に扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態１で扱われる画像が複製されたものであることを、画像位置推定装置１の動作要件とするものではない。本発明でいう複製画像（第２の画像）は、画像中に、元画像である第１の画像の全部又は一部を含む画像であればよい。例えば、トリミングなどの画像処理により、第１の画像が完全に含まれない場合も第２の画像として取り扱う。
【００１６】
また、図１に示すように、画像位置推定装置１は、境界線推定部２及び位置推定方式選択部３を備える。境界線推定部２は、入力した複製画像（図１で画像と表記）を画像解析することにより、元画像に含まれる領域と含まれない領域との境界線を推定する構成部である。位置推定方式選択部（選択部）３は、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式（位置推定情報）を有しており、複製画像と境界線推定部２で推定した境界線とを解析した結果に基づいて、複数の位置推定方式のうち、対象画像に対応する位置推定方式を選択する構成部である。
【００１７】
なお、上述した境界線推定部２及び位置推定方式選択部３は、画像位置推定装置１を構成するコンピュータのＣＰＵが、本発明の趣旨に従う画像位置推定プログラムを実行することにより、上記のコンピュータにおいて、ソフトウェアとハードウェアが協働した具体的な手段として実現することができる。また、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式は、上記コンピュータが備える記憶装置に記憶される。
【００１８】
次に動作について説明する。
図２は、実施の形態１の画像位置推定装置による動作の流れを示すフローチャートであり、画像位置の推定手順の一例を示している。以降では、図１に示す構成を、図２に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、境界線推定部２及び位置推定方式選択部３にそれぞれ入力される。境界線推定部２は、入力した複製画像を画像解析することで、この複製画像の元画像に含まれる領域と含まれない領域との境界線として、上境界線、下境界線、左境界線、右境界線を推定する（ステップＳＴ１；境界線推定ステップ）。
【００１９】
この実施の形態１では、境界線推定部２が、複製画像の上下左右に、単色の領域、単調なテクスチャを持つ領域、自然画の周囲にある明らかに自然画とは異なる画像的性質を持つ領域などを画像解析によって特定し、これらの領域を上下方向及び左右方向の直線で区切って排除することにより、残された長方形の領域の上下左右の辺（線分）を、それぞれ上境界線、下境界線、左境界線、右境界線と推定する。
【００２０】
なお、上境界線の推定に失敗した場合や上境界線が存在しないと判断した場合は、複製画像の上辺（線分）を上境界線であると推定する。また、下境界線、左境界線、右境界線についても、同様に推定失敗や存在しないと判断した場合には、下境界線、左境界線、右境界線が、それぞれ、複製画像の下辺、左辺、右辺に一致すると推定するものとする。
【００２１】
また、境界線推定部２による境界線推定のアルゴリズムとしては、画像処理を用いた既存又は新規の様々な実現例が考えられる。この実施の形態１では、以下のアルゴリズムを採用する。
【００２２】
先ず、境界線推定部２は、複製画像から、画素値がほぼ一定である一定範囲の領域を検出し、検出した領域とこれ以外の領域との上下方向又は左右方向の境界線を推定する。
図３は、境界線の推定処理を説明するための図であり、様々な複製画像の上下左右の辺と境界線との関係を示している。上述のアルゴリズムでは、図３（ｂ）、図３（ｃ）及び図３（ｆ）にそれぞれ示すような画像からは、黒領域（画素値がほぼ一定である一定範囲の領域）が検出され、この黒領域との境目に境界線を設定することができる。
【００２３】
例えば、図３（ｂ）に示す画像では、上境界線と下境界線が、黒領域と風景画像領域（元画像を示す画像領域）との間に設定される。また、図３（ｃ）に示す画像は、左境界線と右境界線が、黒領域と風景画像領域との間に設定される。図３（ｆ）に示す画像では、上下左右の４境界線が、黒領域と風景画像領域との間に設定される。
【００２４】
次に、境界線推定部２は、複製画像から、画素値の種類が少数であって、かつ画像の空間領域に高周波成分を殆ど含まない領域を検出して、検出した領域とこれ以外の領域との上下方向又は左右方向の境界線を推定する。
例えば、画素値の種類の数（色の数）をカウントして色の数に関する所定の閾値と比較するとともに、高周波成分の検出に関する所定の閾値を用いて、空間領域における高周波成分を判定する。境界線推定部２は、色の数及び高周波成分が上記の各閾値以下と判定された領域を検出する。
【００２５】
このアルゴリズムによれば、図３（ｅ）に示すように、風景画像領域とは異なる領域、例えば、文字データの表示欄等が表示されている画像において、この文字データ表示欄の領域と風景画像領域との間の境界線（図３（ｅ）では左境界線と下境界線）が適切に推定される可能性を高めることができる。
【００２６】
続いて、境界線推定部２は、複製画像から、画像の空間領域の周波数成分スペクトルの分布が類似する領域を検出して、検出した領域とこれ以外の領域との上下方向又は左右方向の境界線を推定する。例えば、画像領域の周波数成分スペクトルをそれぞれ抽出し、スペクトル分布と所定の類似範囲にある画像領域を検出する。
このアルゴリズムにより、図３（ｄ）に示すように、画像サイズが足りない余白部分に一定の模様の画像領域がある画像において、この一定の模様の画像領域と風景画像領域との間の境界線（図３（ｄ）では左境界線と右境界線）が適切に推定される。
【００２７】
上述した各アルゴリズムで推定した境界線を基にして最終的な位置推定に失敗したり、境界線自体が存在しないと判定された場合には、境界線が、複製画像の辺に一致するものとして推定される。例えば、図３（ｂ）の画像であれば、境界線推定部２が、左右の境界線の推定に失敗している。この場合、図３（ｂ）に示す画像の左辺が左境界線と一致し、右辺が右境界線に一致すると最終的に判断される。
【００２８】
なお、上述のアルゴリズム以外にも、高度な画像処理を施すことによって、さらに高い精度で上下左右の境界を推定できる。つまり、境界線推定部２は、上下左右方向の境界線を推定して出力する任意の構成とすることができる。
【００２９】
勿論、境界線推定部２で推定された境界線が必ず有用になるとは限らない。
例えば、境界線を推定するアルゴリズムに不備がある場合の推定の失敗や、元画像に黒帯等の周辺領域が付属しており、何ら編集を加えていないにもかかわらず、本来の目的である元画像の境界線とは異なる上記の黒帯領域とこれ以外の領域との境界線が検出されるような場合には、推定された境界線は有用でない。このような場合、最終的な位置の推定に失敗する可能性がある。
【００３０】
境界線推定部２は、様々な方法で位置推定方式選択部３に上下左右の境界線を指定することができる。この実施の形態１では、上境界線と下境界線は、複製画像の上辺からの距離（単位は画素数）で指定し、左境界線と右境界線は、複製画像の左辺からの距離で指定する。
この他にも、画像左上を原点とし、右方向をｘ軸、下方向をｙ軸とする座標平面を割り当て、左右及び上下に隣接する２画素間の距離をｘ軸及びｙ軸上で１の大きさとしてスケーリングすることにより、上下左右の境界線を線分として捉えた場合の両端に当たる２点で指定することもできる。
なお、境界線の指定は、上下左右の境界線を装置１内部で特定可能な指定方法であればどのような方法であってもよい。
【００３１】
図２のフローチャートの説明に戻る。
位置推定方式選択部３は、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式を有している。
上述のようにして、境界線推定部２で推定された境界線が指定されると、位置推定方式選択部３は、入力した複製画像とこの複製画像について境界線推定部２が推定した境界線とを解析して、この解析結果が選択判断基準を満足する位置推定方式を、複数の位置推定方式のうちから選択する（ステップＳＴ２；位置推定方式選択ステップ）。
【００３２】
実施の形態１では、位置推定方式選択部３に予め設定される位置推定方式は、図４に示す方式１から方式３までの３通りと仮定する。つまり、位置推定方式選択部３は、方式１から方式３が登録された選択候補リストを保持し、この選択候補リストから複製画像に適した位置推定方式を選択する。
具体的には、推定された境界線が、方式１から順に選択判断基準を満たすかどうか確認して、満たす場合にはその方式を選択し、満たさない場合には、次に方式の選択判断基準を満たすかどうかを確認する。この選択判断基準は、画面内における境界線の位置関係であり、例えば境界線間の距離や境界線と辺との距離の関係で規定される。
なお、図４に示す方式において、方式１と方式２で選択判断基準を満たさない場合は、方式３を選択する。
【００３３】
図４において、方式１は、元画像の上辺、下辺、左辺、右辺が、複製画像の左境界線、右境界線、下境界線、上境界線にそれぞれ対応する位置関係を示す位置推定方式である。これは、元画像が９０度左回りに回転した場合に相当する。方式１の選択判断基準は、上下境界線間の距離が左右境界線間の距離より長いことであり、この条件を満たす場合に、位置推定方式選択部３は、方式１を選択する。
【００３４】
方式１の選択判断基準の条件を満たさない場合、位置推定方式選択部３は、方式２の選択判断基準を満たすかどうかを検証する。方式２の選択判断基準を満たす場合に、位置推定方式選択部は、方式２を選択する。
方式２は、元画像の上辺、下辺、左辺、右辺が、複製画像の上境界線、下境界線、左境界線、右境界線にそれぞれ対応する位置関係を示す位置推定方式である。これは、元画像が回転されずにそのまま上下左右の境界線内部に配置された場合に相当する。
【００３５】
位置推定方式選択部３は、方式２の選択判断基準を満たさない場合に、方式３を選択する。方式３は、元画像の上辺、下辺、左辺、右辺が、複製画像の上辺、下辺、左辺、右辺にそれぞれ対応する位置関係を示す位置推定方式である。
このようにして選択された位置推定方式は、処理対象の複製画像とその元画像との位置関係の推定結果として、位置推定方式選択部３から出力される。
【００３６】
実施の形態１の画像位置推定装置１は、元画像がテレビ画面や映画館のスクリーンに投影された映像のように、縦よりも横のサイズが１倍から３倍程度長い画像に有効である。このような元画像を複製した複製画像が方式１の選択判断基準を満たす場合には、この複製画像又はこの複製画像内の境界線で囲まれた長方形部分が縦長となる。これは、元画像が回転した画像である可能性が高いので、９０度左回りに回転したものとして位置を推定することにより、回転を考慮しない場合と比較して正しく位置を推定できる。
【００３７】
また、方式２では、複製画像内の境界線で囲まれた長方形部分が、縦長の場合及び横長過ぎる場合を除いて、この長方形部分が元画像に一致すると仮定することで、そうしない場合に比べ、複製画像の上下左右に黒帯が挿入されている場合などに位置推定の精度を高めることができる。
【００３８】
なお、複製画像内の境界線で囲まれた長方形部分が横長過ぎる場合は、推定された境界線の位置の信憑性が低いと考えられるため、方式２のように境界線で囲まれた領域内部の画像が元画像に対応するとした場合、位置推定の精度を損なう可能性がある。この場合には、方式３のように、元画像全体が複製画像全体に当たると仮定する対応関係で位置推定することで、位置推定の精度の劣化を防ぐことができる。
【００３９】
以上のように、この実施の形態１によれば、境界線推定部２が、複製画像を画像解析して、複製画像で元画像に含まれる画像領域と元画像に含まれない画像領域との境界線を推定し、位置推定方式選択部３が、複製画像でとり得る境界線の位置関係を選択基準として、元画像の辺と複製画像の辺又は境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定方式を有しており、境界線推定部２によって複製画像から推定された境界線の位置関係を解析した結果に基づいて、複数の位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択する。このように構成することにより、元画像と複製画像との位置合わせの精度を向上させることができる。
【００４０】
また、上記実施の形態１において、境界線推定部２が、境界線の推定に失敗した場合や境界線が存在しないと判断した場合、境界線を元画像の辺に対応すると推定した。
この場合、境界線推定部２は、上境界線、下境界線、左境界線、右境界線のそれぞれの情報を位置推定方式選択部３に与える。
このようにする代わりに、境界線の推定に失敗した場合や境界線が存在しないと判断した場合には、境界線推定部２が、「境界線なし」であることを示す情報を位置推定方式選択部３に与えるようにしてもよい。
例えば、境界線推定部が、元画像の上辺、下辺、左辺とはそれぞれ異なる、複製画像の上境界線、下境界線、左境界線を推定し、右境界線の検出に失敗した場合、上境界線、下境界線、左境界線の情報と、「右境界線がない」という情報を位置推定方式選択部３に与える。また、位置推定方式選択部３は、右境界線を必要とする方式（図４の方式１及び方式２）を選択肢から外して位置推定方式を選択する（図４の場合では、方式３が選択される）ことができる。
このようにすることで、選択を検討すべき方式の候補を事前に絞ることができるので、処理量を削減することができる。
【００４１】
さらに、上記実施の形態１では、位置推定方式選択部３が選択対象とする各方式で、前提とされる対応関係が、図４に示す内容である場合を示した。しかしながら、これは、位置推定方式で前提とする対応関係の一例であって、他の対応関係を設定してもよい。
例えば、方式１の前提とする対応関係を、元画像の上辺、下辺、左辺、右辺がそれぞれ複製画像の右境界線、左境界線、上境界線、下境界線に対応するとしてもよい。これは、複製画像が、元画像を９０度右回りに回転したものである場合に相当する。
このようにすることで、元画像に９０度右回りの回転が加えられた場合に適切に位置を推定することができる。
【００４２】
この他、元画像の上辺、下辺、左辺、右辺がそれぞれ複製画像の上境界線、下境界線、左辺、右辺に対応する位置関係を示す位置推定方式を選択肢としてもよい。
この方式を選択することで、元画像の上下のみに黒帯等の領域が付加された場合に適切に位置を推定できるようになる可能性が高まり、左右に黒帯等の領域が付加される可能性が低い場合に有効である。
【００４３】
さらに、他の方式を追加したり判断基準を変更することを許容する構成を設けることにより、位置推定方式選択部３が、任意の位置推定方式を備えるようにしてもよい。
例えば、位置推定方式選択部３が、画像位置推定装置１を構成するコンピュータが備える表示装置（モニタ）及び入力装置（キーボード、マウス、タッチパネル等）を用いて、新たな位置推定方式の内容、既存の位置推定方式で前提とされる対応関係、及び選択判断基準の少なくとも一つを設定入力するためのＧＵＩ（Graphical User Interface）を提供する。入力装置を用いて新たな方式や選択判断基準が入力されると、位置推定方式選択部３は、入力された内容で位置推定方式の選択候補リストを更新する。
【００４４】
実施の形態２．
この実施の形態２における画像位置推定装置は、上記実施の形態１と構成自体は同一であるが、上記実施の形態１とは、境界線を左右方向及び上下方向に限定しない点と、境界線の推定に失敗した場合や境界線が存在しないと判断した場合に「境界線をなし」と推定する点で異なる。
そこで、実施の形態２による画像位置推定装置の構成については、上記実施の形態１で示した図１を参照し、画像位置推定の手順については、上記実施の形態１で示した図２を参照する。
なお、実施の形態２においても、上記実施の形態１と同様に、画像位置推定装置１に扱われる画像を“複製画像”と呼称するが、これは、“元画像”と区別するためであって、この実施の形態２で扱われる画像が複製されたものであることを、画像位置推定装置１の動作要件とするものではない。
【００４５】
次に動作について説明する。
以降では、図１に示す構成を図２に示す各処理ステップの動作に対応付けて説明する。
上記実施の形態１と同様に、処理対象の複製画像は、境界線推定部２及び位置推定方式選択部３にそれぞれ入力される。境界線推定部２は、入力した複製画像を画像解析することにより、この複製画像の元画像に含まれる領域と含まれない領域との境界線として、上境界線、下境界線、左境界線、右境界線を推定する（ステップＳＴ１；境界線推定ステップ）。
【００４６】
実施の形態２では、境界線推定部２が、複製画像の上下左右に、単色の領域、単調なテクスチャを持つ領域、自然画の周囲にある明らかに自然画とは異なる画像的性質を持つ領域などを画像解析によって特定し、これらの領域を４本の直線（上下方向及び左右方向に限られない）で区切って排除することにより、残された長方形の領域の上下左右の辺（線分）を、それぞれ上境界線、下境界線、左境界線、右境界線と推定する。
また、上境界線の推定に失敗した場合や上境界線が存在しないと判断した場合は、「上境界線なし」と推定する。下境界線、左境界線、右境界線についても、同様に推定失敗や存在しないと判断した場合には「下境界線なし」、「左境界線なし」、「右境界線なし」と推定する。
【００４７】
このように、実施の形態２では、上記実施の形態１と異なり、複製画像中の単色の領域や単調なテクスチャを持つ領域、自然画とは異なる画像的性質を持つ領域を、斜め方向も許容される、左右方向及び上下方向に限られない境界線で区切って排除し、また境界線の推定に失敗したり、境界線が存在しないと判断した場合には「境界線なし」と推定する。
境界線推定部２による境界線推定アルゴリズムとしては、画像処理を用いた既存又は新規の様々な実現例が考えられる。実施の形態２では、以下のアルゴリズムを採用する。
【００４８】
先ず、境界線推定部２は、上記実施の形態１と同様に、画素値や画素値の周波数成分などの画像的特徴を処理することで、単色の領域、単調なテクスチャを持つ領域、自然画の周囲にある明らかに自然画と異なる画像的性質を持つ領域などを判断し、これらの領域を直線で区切って排除し、境界線を推定する。ただし、この実施の形態２では、境界線を上下方向及び左右方向に限らず、斜めでもよいものとして推定する。
【００４９】
図５は、実施の形態２における境界線の推定処理を説明するための図であり、様々な複製画像の上下左右の辺と境界線との関係を示している。図５（ａ）に示した複製画像は、元画像（風景画像領域）を小さな画像サイズで斜めに複製している。
上記実施の形態１で示した画像位置推定装置が、この図５（ａ）の複製画像において、上下左右の境界線を推定した場合、図５（ｂ）に示すように風景画像領域の矩形の頂点をそれぞれ含む境界線が上下左右の境界線として推定される。このため、風景画像領域以外の黒領域が含まれ、風景画像領域のみを切り出す境界線を推定できない。
【００５０】
これに対して、この実施の形態２による画像位置推定装置では、図５（ｃ）に示すように斜め方向にも境界線を推定するために、図５（ａ）に示すような複製画像であっても、風景画像領域のみを切り出す境界線の推定が可能である。この境界線推定アルゴリズムとしては、下記のものが挙げられる。
【００５１】
先ず、黒領域と風景画像領域との境界として、斜め方向の４本の境界線を求め、線分としてのこれら４境界線の中点をそれぞれ算出する。４境界線の中点のうち、画像中で最も上に位置する境界線を上境界線と推定し、残りの境界線の中点のうち、画像中で最も下に位置する境界線を下境界線と推定し、残り２境界線の中点のうち、画像の左側にある境界線を左境界線と推定し、画像の右側にある境界線を右境界線と推定する。
【００５２】
また、同様に斜め方向の４本の境界線を求めて４境界線の中点をそれぞれ算出した後、図５（ａ）に示す複製画像の下辺を水平線とした場合に、当該画像中の当該水平線からの仰角が４５度を超える境界線のうち、中点が最も左にある境界線を左境界線と推定し、最も右にある境界線を右境界線と推定し、残りの２境界線のうち、中点が画像の上側にある境界線を上境界線と推定して、残りの１境界線を下境界線と推定するアルゴリズムを採用することもできる。
【００５３】
境界線推定部２は、これらのアルゴリズムに従って推定した上下左右の境界線が、時計回りに上境界線、右境界線、下境界線、左境界線となっていなければ、４境界線の推定に失敗したと判断する。
また、この他に、境界線推定部２が、境界線の推定において、境界線４境界線の中から上述のアルゴリズムに従って上境界線のみを選定し、残りは、上境界線から時計回りに右境界線、下境界線、左境界線と選定するようにしてもよい。
さらに、この実施の形態２では、黒領域と元画像を示す画像領域との境界線として斜め方向の境界線を推定し、画像中の位置から上下左右の境界線として選定することができるアルゴリズムであれば、上記のアルゴリズムの内容に限定されるものではない。
【００５４】
境界線推定部２によって推定された上下左右の境界線は、例えば、下記の方法で、位置推定方式選択部３に指定される。
複製画像の左上の頂点を原点とし、この原点から右方向にｘ軸、下方向をｙ軸とした２次元座標平面を割り当て、左右及び上下に隣接する２画素間の距離をｘ軸及びｙ軸上で、１の大きさとしてスケーリングし、上下左右の境界線を線分として捉えた場合の線分両端にあたる２点を用いて境界線を指定する。
例えば、上境界線は、上境界線と左境界線との交点の座標と、上境界線と右境界線との交点の座標との組み合わせで指定するか、上境界線が存在しないことを示す識別子で表現する。下境界線、左境界線、右境界線についても同様である。
【００５５】
位置推定方式選択部３は、境界線推定部２で推定された境界線が指定されると、入力した複製画像とこの複製画像について境界線推定部２が推定した境界線とを解析して、この解析結果が選択判断基準を満足する位置推定方式を、複数の位置推定方式のうちから選択する（ステップＳＴ２；位置推定方式選択ステップ）。
【００５６】
この実施の形態２では、位置推定方式選択部３に予め設定される位置推定方式は、図６に示す方式１から方式３までの３通りと仮定する。つまり、位置推定方式選択部３は、方式１から方式３が登録された選択候補リストを保持し、この選択候補リストから複製画像に適した位置推定方式を選択する。
具体的には、推定された境界線が、方式１から順に選択判断基準を満たすかどうか確認して、満たす場合にはその方式を選択し、満たさない場合には、次に方式の選択判断基準を満たすかどうかを確認する。なお、図６に示す方式において、方式１と方式２で選択判断基準を満たさない場合は、方式３を選択する。
【００５７】
図６において、方式１は、元画像の上辺、下辺、左辺、右辺が、複製画像の左境界線、右境界線、下境界線、上境界線にそれぞれ対応する位置関係を示す位置推定方式である。これは、元画像が９０度左回りに回転した場合に相当する。方式１の選択判断基準は、左右境界線間の距離が上下境界線間の距離より長いことであり、この条件を満たす場合に、位置推定方式選択部３は、方式１を選択する。
【００５８】
方式１の選択判断基準の条件を満たさない場合、位置推定方式選択部３は、方式２の選択判断基準を満たすかどうかを検証する。方式２の選択判断基準を満たす場合に、位置推定方式選択部は、方式２を選択する。
方式２は、元画像の上辺、下辺、左辺、右辺が、複製画像の上境界線、下境界線、左境界線、右境界線にそれぞれ対応する位置関係を示す位置推定方式である。これは、元画像が回転されずにそのまま上下左右の境界線内部に配置された場合に相当する。
【００５９】
位置推定方式選択部３は、方式２の選択判断基準を満たさない場合に、方式３を選択する。方式３は、元画像の上辺、下辺、左辺、右辺が、複製画像の上辺、下辺、左辺、右辺にそれぞれ対応する位置関係を示す位置推定方式である。
このようにして選択された位置推定方式は、処理対象の複製画像とその元画像との位置関係の推定結果として、位置推定方式選択部３から出力される。
【００６０】
実施の形態２の画像位置推定装置１は、元画像がテレビ画面や映画館のスクリーンに投影された映像のように、縦よりも横のサイズが１倍から３倍程度長い画像であり、かつ、スクリーンを上映中に撮影した場合のように、長方形の元画像が歪んで撮影された複製画像に有効である。複製画像は、上述のように元画像が回転しているか否かを各位置推定方式の選択判断基準から推定することができる。
【００６１】
以上のように、この実施の形態２によれば、境界線推定部２が、複製画像上で推定する境界線を左右方向及び上下方向に限定せず、境界線の推定に失敗した場合や境界線が存在しないと判断した場合に「境界線をなし」と推定する。このように構成することにより、上記実施の形態１と比べ、さらに元画像と複製画像との位置合わせの精度を向上させることができる。
【００６２】
なお、上記実施の形態２では、境界線推定部２が、上下左右の方向に限らない線分の境界線を推定する場合を示したが、上下境界線が水平方向（左右方向）に近い場合や左右境界線が鉛直方向（上下方向）に近い場合などは、特別に水平方向の境界線や鉛直方向の境界線とすることもできる。
例えば、境界線推定部２が、上下境界線の水平方向に対する角度が一定角度以内である場合には、上記実施の形態１で示した境界線推定アルゴリズムに切り替え、水平方向の上下境界線を推定したり、左右境界線の鉛直方向に対する角度が一定角度以内である場合には、上記実施の形態１で示した境界線推定アルゴリズムに切り替えて、鉛直方向の左右境界線を推定したりすることもできる。
このようにすることで、上下方向又は左右方向の境界線が、画像処理上の誤差によって完全には上下方向又は左右方向とならない場合に、その誤差の影響を排除することができる。なお、上記実施の形態１で示した境界線推定アルゴリズム以外のアルゴリズムを採用してもよく、境界線推定部２は、上下左右の境界線を推定して出力する任意の構成とすることができる。
【００６３】
実施の形態３．
この実施の形態３では、元画像に埋め込まれた電子透かし情報を複製画像から検出する電子透かし検出装置について説明する。
図７は、この発明の実施の形態３による電子透かし検出装置の構成を示すブロック図である。図７において、実施の形態３の電子透かし検出装置１Ａは、元画像と元画像を複製した複製画像において、一方の画像の任意な位置に対応する他方の画像の位置の対応関係を推定し、この対応関係を基に電子透かし情報を検出して電子透かし情報及び電子透かし情報検出の成否を出力する装置である。
なお、電子透かし検出装置１Ａに扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態３で扱われる画像が複製されたものであることを、電子透かし検出装置１Ａの動作要件とするものではない。
【００６４】
また、図７に示すように、電子透かし検出装置１Ａは、境界線推定部２、位置推定方式選択部３及び電子透かし情報検出部４を備える。境界線推定部２は、入力した複製画像（図７で画像と表記）を画像解析することで、元画像に含まれる領域と含まれない領域との境界線を推定する構成部である。位置推定方式選択部３は、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式を有し、複製画像と境界線推定部２で推定した境界線とを解析した結果に基づいて、複数の位置推定方式のうち、対象画像に対応する位置推定方式を選択する構成部である。
さらに、電子透かし情報検出部４は、位置推定方式選択部３で選択された位置推定方式に従い、複製画像と元画像との位置関係の対応付けを行い、この位置関係に基づいて電子透かし情報を検出し、検出された電子透かし情報及び電子透かし情報の検出の成否を出力する構成部である。
【００６５】
なお、境界線推定部２、位置推定方式選択部３及び電子透かし情報検出部４は、電子透かし検出装置１Ａを構成するコンピュータのＣＰＵが、本発明の趣旨に従う画像位置推定及び電子透かし検出用プログラムを実行することにより、上記のコンピュータにおいて、ソフトウェアとハードウェアが協働した具体的な手段として実現することができる。
また、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式は、上記コンピュータが備える記憶装置に記憶される。
【００６６】
次に動作について説明する。
図８は、実施の形態３の電子透かし検出装置による動作の流れを示すフローチャートであり、画像位置の推定及び電子透かし検出手順の一例を示している。以降では、図７に示す構成を、図８に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、境界線推定部２、位置推定方式選択部３、及び電子透かし情報検出部４にそれぞれ入力される。境界線推定部２は、上記実施の形態１と同様の処理で、入力した複製画像を画像解析することによって、この複製画像の元画像に含まれる領域と含まれない領域との境界線として、上境界線、下境界線、左境界線、右境界線を推定する（ステップＳＴ１ａ；境界線推定ステップ）。
【００６７】
位置推定方式選択部３は、境界線推定部２にて推定された境界線が指定されると、入力した複製画像とこの複製画像について境界線推定部２が推定した境界線とを解析して、この解析結果が選択判断基準を満足する位置推定方式を、複数の位置推定方式のうちから選択する（ステップＳＴ２ａ；位置推定方式選択ステップ）。
【００６８】
続いて、電子透かし情報検出部４が、位置推定方式選択部３により選択された位置推定方式に基づいて、複製画像と元画像との位置関係の対応付けを行い、この位置関係から、電子透かし情報の検出処理を行う（ステップＳＴ３ａ；電子透かし情報検出ステップ）。元画像の特定の位置に電子透かし情報が埋め込まれている場合は、位置推定方式選択部３で選択された位置推定方式によって、複製画像と元画像との位置関係の対応付けが可能であるから、電子透かし情報を検出することができる。なお、本発明において、電子透かし自体は、特定の電子透かし技術を想定していない。つまり電子透かし技術は、既に様々な方式が公知となっており、これらのうちのいずれかの方式を適用してもよい。
【００６９】
通常、電子透かし情報は、誤り検出符号を含んでいるので、電子透かし情報の検出結果から、電子透かし情報の検出の成否を判断できる。実施の形態３においても、電子透かし情報が誤り検出符号を含んでいるものとする。
電子透かし情報検出部４は、電子透かし情報の検出処理において誤り検出符号から電子透かし情報の検出の成否を判断する（ステップＳＴ４ａ；成否判断ステップ）。
【００７０】
電子透かし情報検出部４にて電子透かし情報の検出に失敗すると（ステップＳＴ４ａ；失敗）、位置推定方式選択部３は、まだ選択していない選択可能な位置推定方式が残っているか否かを判定する（ステップＳＴ５ａ；選択可否判定ステップ）。
このとき、選択可能な位置推定方式が残っていれば（ステップＳＴ５ａ；ＹＥＳ）、ステップＳＴ２ａの処理に戻り、位置推定方式選択部３が、残りの位置推定方式を選択して、選択可能な残りの位置推定方式が無くなるまで（ステップＳＴ５ａ；ＮＯ）、ステップＳＴ２ａ以降の処理を繰り返す。
【００７１】
位置推定方式選択部３は、２度目以降の位置推定方式の選択において、以前に選択した位置推定方式を選択肢から外し、その上で、１度目と同じ手順で位置推定方式を一つ選択する。電子透かし情報検出部４は、位置推定方式選択部３にて選択された位置推定方式を使用して、再度電子透かし情報の検出を試みる。この処理を繰り返す。位置推定方式選択部３に予め設定された（例えば、図４の表の方式１から方式３の）位置推定方式のうち、選択可能な位置推定方式の候補がなくなった上で、電子透かし情報の検出に失敗すると、最終的に電子透かし情報の検出失敗として、処理を終了する。
【００７２】
このようにすることで、もし最初に選択した位置推定方式が不適切であったとしても、より適切な位置推定方式を選んで、電子透かし情報の検出をやり直すことができる。
このため、位置推定方式選択及び電子透かし情報検出を一度しか実施しない構成と比べて、電子透かし情報の検出成功率を向上させることができる。
【００７３】
図４に示す位置推定方式の選択候補リストから位置推定方式を選択する場合を例にとって、具体的な位置推定方式選択のやり直しの手順を説明する。位置推定方式選択部３が、方式１を選択してから、その後選択をやり直す場合、方式１を選択肢から除き、方式２と方式３のどちらかを選択する。
【００７４】
方式２の選択判断基準を満たしていれば方式２を選択し、そうでなければ方式３を選択する。３度目の選択では、残りの位置推定方式が方式３であれば、方式３を選択するが、残りの位置推定方式が方式２であっても、２度目の選択で選択判断基準を満たしていないため、方式２は選択されず、選択可能な位置推定方式が残っていないとして、最終的に電子透かし情報の検出を失敗として終了する。
【００７５】
このように、あくまで選択基準を満たさない方式は、選択しないとするアルゴリズムの他、位置推定方式の選択をやり直す場合には、選択判断基準を緩めて設定し直し、残りの位置推定方式を全て選択対象とするアルゴリズムを採用してもよい。
また、選択判断基準を設けず、方式１から順番に選択していき、選択肢となる位置推定方式がなくなったら、最終的に電子透かし情報の検出を失敗として終了するアルゴリズムも考えられる。
【００７６】
上述のような位置推定方式の選択のやり直しを行うアルゴリズムは、様々な形態が可能である。位置推定方式選択部３は、電子透かし情報検出部４が電子透かし情報の検出に成功するか、選択可能な位置推定方式がなくなるまで、選択可能な位置推定方式の中から位置推定方式を選択する構成であれば、任意の構成とすることができる。
【００７７】
なお、上述の説明では、位置推定方式選択部３を、上記実施の形態１の画像位置推定装置１の位置推定方式選択部と同様の構成とした。従って、図４の位置推定方式の候補リストから位置推定方式を選択することになる。
【００７８】
一方、位置推定方式の候補リストは、図４の代わりに、図９に示すリストを採用しても構わない。図９に示す候補リストでは、位置推定方式として方式１が選択され、その後に位置推定方式の選択をやり直す際に方式２が選択される。方式２は、図９に示すように、元画像の上辺、下辺、左辺、右辺がそれぞれ複製画像の右境界線、左境界線、上境界線、下境界線に対応する位置推定方式である。これは、元画像が９０度右回りに回転した場合に相当する。
【００７９】
元画像が９０度右回りに回転してアスペクト比が変更され、その周囲を黒領域で補充された複製画像が対象である場合を例に挙げる。この場合、図４に示す位置推定方式の候補リストから位置推定方式を選択するアルゴリズムであると、境界線内部の画像の長方形が縦長であることから、元画像が回転している可能性があるとして方式１を選択することができるが、方式１は、元画像が９０度左回りに回転されている場合に相当するので、位置合わせに成功しない。
【００８０】
これに対して、図９に示す位置推定方式の候補リストから位置推定方式を選択するアルゴリズムを採用すると、方式１を選択して位置関係を推定してから、電子透かし情報の検出に失敗した場合、次に図９の候補リスト中の方式２が選択され、正しく位置関係を推定することができる。従って、電子透かし情報検出の成功率を高めることができる。
【００８１】
また、上述の説明では、境界線推定部２が、上記実施の形態１の画像位置推定装置１の境界線推定部２と同様の構成であり、かつ、位置推定方式選択部３が、上記実施の形態１の画像位置推定装置１の位置推定方式選択部３と同様の構成である場合を示した。
しかしながら、この実施の形態３では、境界線推定部２を上記実施の形態２の画像位置推定装置１の境界線推定部と同様の構成とし、かつ、位置推定方式選択部３を上記実施の形態２で示した位置推定方式選択部３と同様の構成とすることもできる。
このように構成すると、複製画像が元画像をカメラで撮影して複製された画像である場合など、複製の過程で元画像の長方形に射影変換歪が加えられた場合であっても、元画像と複製画像との位置関係を推定し、複製画像から元画像に埋め込まれた電子透かし情報を検出する装置を構成することができる。
この構成において、電子透かし情報の検出に失敗した場合に位置推定方式の選択をやり直して、再度電子透かし情報の検出を試みることで、電子透かし情報検出の成功率を高めることができる。
【００８２】
この他にも、実施の形態３による電子透かし検出装置１Ａとして、境界線推定部２が推定した上下左右の境界線に関する情報を利用し、位置推定方式選択部３が位置推定方式の候補リストから位置推定方式を選択し、選択のやり直しの場合には、まだ選択されていない位置推定方式から選択する動作をする構成あれば、任意の構成とすることができる。
【００８３】
以上のように、この実施の形態３によれば、位置推定方式選択部３によって選択された位置推定方式から、元画像と複製画像との間で位置の対応付けを行い、この対応関係に基づいて、元画像で電子透かし情報が埋め込まれた箇所に対応すると推定される複製画像の位置を特定して、当該複製画像から電子透かし情報を検出する。このように構成することで、元画像と複製画像との位置合わせが正確に行われ、電子透かし情報検出の成功率を高めることができる。
【００８４】
実施の形態４．
この実施の形態４では、得られた複製画像とその元画像との位置関係を推定する画像位置推定装置について説明する。
図１０は、この発明の実施の形態４による画像位置推定装置の構成を示すブロック図である。図１０において、実施の形態４の画像位置推定装置１Ｂは、元画像とこの画像を複製した複製画像とにおいて、一方の画像の任意な位置に対応する他方の画像の位置を推定する装置である。なお、この画像位置推定装置１Ｂに扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態４で扱われる画像が複製されたものであることを、画像位置推定装置１Ｂの動作要件とするものではない。
【００８５】
また、図１０に示すように、画像位置推定装置１Ｂは、特徴点検出部５及び位置推定方式選択部３ａを備える。特徴点検出部５は、得られた複製画像を画像解析することにより、元画像に予め埋め込んであった特徴点を検出する構成部である。
位置推定方式選択部３ａは、複製画像と元画像に予め埋め込んだ特徴点との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式を有し、複製画像と特徴点検出部５で検出された特徴点とを解析した結果に基づいて、複数の位置推定方式のうち、対象画像に対応する位置推定方式を選択する構成部である。
【００８６】
なお、特徴点検出部５及び位置推定方式選択部３ａは、画像位置推定装置１Ｂを構成するコンピュータのＣＰＵが、本発明の趣旨に従う画像位置推定プログラムを実行することにより、上記のコンピュータにおいて、ソフトウェアとハードウェアが協働した具体的な手段として実現することができる。また、複製画像と元画像との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式は、上記コンピュータが備える記憶装置に記憶される。
【００８７】
次に動作について説明する。
図１１は、実施の形態４の画像位置推定装置による動作の流れを示すフローチャートであり、画像位置の推定手順の一例を示している。以降では、図１０に示す構成を、図１１に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、特徴点検出部５及び位置推定方式選択部３ａにそれぞれ入力される。特徴点検出部５は、入力した複製画像を画像解析することにより、この複製画像の元画像に予め埋め込んであった特徴点を検出する（ステップＳＴ１ｂ；特徴点検出ステップ）。
【００８８】
ここでは、特徴点検出部５が、例えば、図１２に示すような元画像に設定した座標系において、長方形の元画像の、上から４分の１で、かつ左から４分の１の位置、上から４分の１で、かつ右から４分の１の位置、下から４分の１で、かつ左から４分の１の位置、下から４分の１で、かつ右から４分の１の位置に、４つの特徴点がそれぞれ設定されているものと仮定する。なお、実施の形態４では、各特徴点をＰS1、ＰS2、ＰS3、ＰS4と呼ぶ。
【００８９】
特徴点を埋め込む方法としては、特徴点が中心となる、ある程度の半径を有した可視の円を元画像に上書きする方法が挙げられる。
また、この他、画像の画素値の最下位ビット（least significant bit;LSB)に対して、特徴点情報を与える方法がある。例えば、最下位ビット値が“１”ならば、特徴点が中心となる、ある程度の半径を有する円に含まれる画素とし、また最下位ビット値が“０”ならば、この円に含まれない画素とする。
あるいは、電子透かし技術によって秘密裏に特徴点を埋め込む方法などが考えられる。
【００９０】
実施の形態４では、画像の画素値の最下位ビットに特徴点情報を与える方法で、元画像に特徴点が設定されているものと想定する。また、この実施の形態４では、特徴点という用語はあくまで点として扱い、特徴点を表す、ある程度の半径を持った円について言う場合は、特徴点を表す円と表現する。
【００９１】
図１２のように、元画像が、横６４０画素及び縦４８０画素の場合を例に挙げて詳細に説明する。この元画像に対して、画像左上を原点として、右方向をｘ軸、下方向をｙ軸とする座標平面を割り当て、左右及び上下に隣接する２画素間の距離をｘ軸及びｙ軸上で、１の大きさとしてスケーリングし、特徴点ＰS1、ＰS2、ＰS3、ＰS4の座標（ｘ，ｙ）は、それぞれ（１６０，１２０）、（４８０，１２０）、（１６０，３６０）、（４８０，３６０）となる。
【００９２】
各特徴点をどの画素に割り当てるかは、様々な実装によることができる。
この実施の形態４では、左上から横方向（ｘ軸）にｍ画素目（１≦ｍ≦６４０）でありかつ、縦ｎ画素目（１≦ｎ≦４８０）の画素位置（ｍ，ｎ）が、座標（ｍ−０．５，ｎ−０．５）に当たるものとする。ここで、特徴点を表す円に含まれる画素であるか否かは、その画素の座標が特徴点を表す円の内部に含まれるかどうかで判断することができる。
【００９３】
特徴点ＰS1を例にとると、特徴点ＰS1を表す円の式は、下記の通りになる。
（ｘ−１６０）2＋（ｙ−１２０）2≦ｒ2 ・・・（１）
但しｒは、円の半径である。
【００９４】
特徴点ＰS1の情報を有する画素（ｍ，ｎ）は、（ｍ−１６０．５）2＋（ｎ−１２０．５）2≦ｒ2を満たす画素となる。この画素において画素値の最下位ビットを“１”とする。他の特徴点についても、同様に特徴点の情報を持つ画素の画素値の最下位ビットを“１”とする。そして、特徴点の情報を有さない画素の画素値の最下位ビットを“０”とする。
【００９５】
このようにすることにより、画像に特徴点を表す円を設定することができる。円の半径の設計は任意だが、余りに小さいと、画像が縮小処理された場合に検出しにくくなる恐れがある。半径を大きくすることで、縮小処理に対する耐性が生まれる。
【００９６】
このように、元画像に４つの特徴点を表す円を設定すると、特徴点検出部５によって、画素値の最下位ビットに特徴点の情報が埋め込まれていることを想定した場合の、具体的な動作は、下記のようになる。なお、図１２に示すように、特徴点の検出対象となる複製画像が、横３６０画素、縦２４０画素である場合を例に挙げて説明する。
【００９７】
先ず、特徴点検出部５は、複製画像の各画素の最下位ビットが“０”か“１”かを調べる。これにより、最下位ビットが“０”である画素の画像領域と、最下位ビットが“１”である画素が含まれる画像領域が発見される。この最下位ビットが“１”である画素の集まり（画像領域）が特徴点を表す円に対応し、この画素の集まりの中心点を画像処理等で推定することにより、特徴点の座標が推定される。図１２の例では、特徴点が最大で４つ検出される。検出された特徴点のうち、左上のもの、右上のもの、左下のもの、右下のものを、それぞれＰD1、ＰD2、ＰD3、ＰD4と呼ぶことにする。
【００９８】
なお、検出に成功した特徴点が３つ以下となる場合もある。この場合には、欠損したと考えられる特徴点を推定する。例えば、特徴点が３つ検出された場合で、それら特徴点の位置関係から右上の特徴点が欠損したと判断し得る場合、ＰD2を検出失敗し、ＰD1、ＰD3、ＰD4の検出に成功したものと判断する。特徴点が一つも検出されないという結果もあり得る。
【００９９】
特徴点の位置関係を判断するアルゴリズムは、様々なものが考えられる。
例えば、検出された４つの特徴点のうち、ｘ座標値＋ｙ座標値が最も小さい特徴点を、ＰD1とし、最も大きい特徴点をＰD4、ｘ座標−ｙ座標が最も小さい特徴点をＰD3、最も大きい特徴点をＰD2とするアルゴリズムが考えられる。
この他にも、先ず、ＰD1を推定し、ＰD1から複製画像中央に向かって最も左側にある特徴点をＰD2、最も右側にある特徴点をＰD3、残りをＰD4とするアルゴリズムも可能である。
ｘ座標が０以上１８０以下でｙ座標が０以上１２０以下の特徴点をＰD1とし、ｘ座標が１８０以上３６０以下でｙ座標が０以上１２０以下の特徴点をＰD2とし、ｘ座標が０以上１８０以下でｙ座標が１２０以上２４０以下の特徴点をＰD3とし、ｘ座標が１８０以上３６０以下でｙ座標が１２０以上２４０以下の特徴点をＰD4とするアルゴリズムを採用しても構わない。このアルゴリズムの場合は、検出された特徴点が３つ以下であっても使用可能である。
【０１００】
また、誤検出により、特徴点が５つ以上検出される可能性もある。このような場合は、特徴点の位置関係や検出時の特徴点の確からしさ（画像処理の計算上、本当に特徴点でありそうな可能性の高さ）から特徴点を４つに絞る処理を加えればよい。
【０１０１】
なお、特徴点検出部５は、特徴点の位置関係の判断アルゴリズムとして、上述したもの以外の採用も可能であり、特徴点の埋め込み方法、埋め込まれる位置に応じて、適切なアルゴリズムを備えていれば、任意の構成とすることができる。
【０１０２】
図１１のフローチャートの説明に戻る。
位置推定方式選択部３ａは、得られた複製画像及び特徴点検出部５が判断した０個以上の特徴点を解析し、元画像と複製画像との位置関係を推定する方式のうち、当該複製画像に適したものを選択する（ステップＳＴ２ｂ；位置推定方式選択ステップ）。
【０１０３】
ここで、説明上の便宜のため、図１２に示すように、元画像の上辺、下辺、左辺、右辺を、それぞれ線分ｅS1、線分ｅS2、線分ｅS3、線分ｅS4とする。また、元画像の中心を点ＣSとする。元画像における４つの特徴点を、左上、右上、左下、右下の順にそれぞれ点ＰS1、点ＰS2、点ＰS3、点ＰS4とする。複製画像の上辺、下辺、左辺、右辺をそれぞれ、線分ｅD1、線分ｅD2、線分ｅD3、線分ｅD4とする。複製画像の中心を点ＣDとする。さらに、複製画像から検出された特徴点のうち、特徴点検出部５によって相対的に左上、右上、左下、右下の位置にあると判断されたものを、それぞれ点ＰD1、点ＰD2、点ＰD3、点ＰD4とする。
【０１０４】
実施の形態４では、位置推定方式選択部３ａが選択する位置推定方式は、図１３に示す候補リストにおける、方式１、方式５から方式９、方式１２、方式１３の８通りとする。
位置推定方式選択部３ａは、方式１から順に選択判断基準を満たすか否かを確認し、満たす場合はその方式を選択し、満たさない場合は次の方式が選択判断基準を満たすかどうかを確認する。これを繰り返すことにより、得られた複製画像に適した位置推定方式を選択する。なお、方式１、方式５から方式９、方式１２の全７方式で選択判断基準を満たさない場合には、方式１３を選択する。
【０１０５】
図１３において、方式１は、元画像の上辺、下辺、左辺、右辺が、それぞれ複製画像の上辺、下辺、左辺、右辺に対応する位置関係を示す位置推定方式である。方式１は、下記の計算式（１）の関係を満たすか否かで選択判断される。
｜ｆ（ＰS1）ＰD1｜2＋｜ｆ（ＰS2）ＰD2｜2＋｜ｆ（ＰS3）ＰD3｜2＋｜ｆ（ＰS4）ＰD4｜2≦α2（ｆ（｜ｅS1｜）2＋ｆ（｜ｅS3｜）2） ・・・（２）
【０１０６】
計算式（１）において、ｆは位置推定方式が前提とする対応関係を満たす写像である。αは非負定数、｜ａ｜は線分ａの長さを表す。なお、ｆ（｜線分｜）は、線分の両端の２点をそれぞれｆで写像した後の２点を結ぶ線分の長さを表す。
ｆ（ＰS1）は、方式１の前提である元画像の上辺、下辺、左辺、右辺が、それぞれ複製画像の上辺、下辺、左辺、右辺に対応するという前提が成り立つ際の、元画像上の左上の特徴点ＰS1に対応する複製画像上の座標を表している。
ＰD1は、特徴点検出部５が検出した特徴点のうち、複製画像の左上に位置する特徴点の座標である。従って、｜ｆ（ＰS1）ＰD1｜は、複製画像上で特徴点が本来あるべき位置と、特徴点検出部５によって検出された位置との間の距離を表している。
【０１０７】
なお、特徴点ＰD1が検出されなかった場合には、｜ｆ（ＰS1）ＰD1｜を“０”と評価する。また、特徴点ＰD2、ＰD3、ＰD4が検出されなかった場合においても、同様に｜ｆ（ＰS2）ＰD2｜、｜ｆ（ＰS3）ＰD3｜、｜ｆ（ＰS4）ＰD4｜をそれぞれ“０”と評価する。
つまり、上記計算式（２）の不等式は、位置推定方式を方式１と仮定した場合に、特徴点の誤差二乗和が一定の範囲内に抑えられているかどうかを評価している。
図１２の例に当てはめると、ｆ（ＰS1）、ｆ（ＰS2）、ｆ（ＰS3）、ｆ（ＰS4）、ｆ（｜ｅS1｜）、ｆ（｜ｅS3｜）は、それぞれ（９０，６０）、（２７０，６０）、（９０，１８０）、（２７０，１８０）、３６０、２４０である。
【０１０８】
この不等式評価は、元画像と複製画像との関係において、前提とする各辺が一致するという対応関係と、特徴点の対応関係との両立性を判定しているのに他ならない。
つまり、計算式（２）の不等式において、左辺値が大きくなるということは、特徴点の検出状況を見る限り、各辺一致という方式１の前提である対応関係には無理があるということになる。
【０１０９】
計算式（２）の不等式が成り立つ場合、位置推定方式選択部３ａは方式１を選択する。方式１は、ｆ（ｅS1）＝ｅD1、ｆ（ｅS2）＝ｅD2、ｆ（ｅS3）＝ｅD3、ｆ（ｅS4）＝ｅD4を前提とする直交変換であるので、図１２の例に当てはめると、（ｘ’，ｙ’）＝ｆ（ｘ，ｙ）は、ｘ’＝０．５６２５ｘ及びｙ’＝０．５ｙとなる。
元画像の位置に対応する複製画像の位置を推定することは、写像ｆを推定することに他ならない。従って、この写像ｆが推定の結果であり、位置推定方式選択部３ａの出力となる。
【０１１０】
特徴点検出部５が特徴点を一つも検出しなかった場合、方式１は無条件に選択される。計算式（１）の不等式が成り立たない場合、位置推定方式選択部３ａは、図１３に示す候補リストの方式５以降の位置推定方式から選択を試みる。
【０１１１】
方式５は、元画像の上辺及び下辺が複製画像の上辺及び下辺にそれぞれ対応しており、元画像の上下方向及び左右方向が複製画像の上下方向及び左右方向となり、元画像の中心が複製画像の中心を通る上下方向の線上の点に対応し、複製画像から検出された一つ以上の特徴点が元画像に設定された一つ以上の特徴点に対応する位置関係を示す位置推定方式である。この方式５は、方式１と異なり、特徴点が一つも検出されなかった場合、写像ｆを特定できない。すなわち、方式５が採用されない。
【０１１２】
方式５において、ＰD2とＰD4の少なくとも一方及びＰD1とＰD3の少なくとも一方が検出された場合、下記式（３）に従う対応関係が前提となる。
ｆ（ｅS1）＝ｅD1、
ｆ（ｅS2）＝ｅD2、
ｘ（ｆ（ＰS1））
＝ｘ（ＣD）−（ｘ（ｍｉｄ（ＰD2ＰD4））−ｘ（ｍｉｄ（ＰD1ＰD3）））／２、
ｘ（ｆ（ＰS4））
＝ｘ（ＣD）＋（ｘ（ｍｉｄ（ＰD2ＰD4））−ｘ（ｍｉｄ（ＰD1ＰD3）））／２、ｆ（ＣS）＝ＣD
・・・（３）
【０１１３】
ここで、ｍｉｄ（ａ）は線分ａの中点である。線分ａの両端のうち、少なくとも一方が定義されていない（検出できなかった）場合、ｍｉｄ（ａ）は、定義されている方の点を表すものとする。なお、ｘ（Ａ）は点Ａのｘ座標を表している。図１２の例に当てはめると、Ｃs＝（３２０，２４０）、ＣD＝（１８０，１２０）である。
この場合、特徴点検出部５が検出した特徴点が、ＰD1＝（５９，８２）、ＰD2＝（３０２，７８）、ＰD3＝（６３，１６１）、ＰD4＝（２９８，１５７）であると、ｘ（ｆ（１６０，１２０））＝６０．５、ｘ（ｆ（４８０，３６０））＝２９９．５となって、（ｘ’，ｙ’）＝ｆ（ｘ，ｙ）は、ｘ’＝０．７４６８７５ｘ−５９及びｙ’＝０．５ｙとなる。
【０１１４】
上述の写像ｆを前提として、方式５の選択判断基準を、計算式（２）の不等式にて評価する。この不等式の評価は、元画像と複製画像との関係において、特徴点の対応関係と、特徴点以外の対応関係である、上下辺の一致、上下方向及び左右方向の一致、元画像の中心が複製画像の中心を通る上下方向の線の上の点という対応関係との両立性を判定しているのに他ならない。不等式が成り立てば、位置推定方式選択部３ａは方式５を選択する。
【０１１５】
これまで、ＰD2とＰD4の少なくとも一方及びＰD1とＰD3の少なくとも一方が検出されたものとして説明したが、方式５は、特徴点が一つ以上検出されていれば適用できる。例えば、ＰD3のみ検出された場合、ＰD2とＰD4がともに検出できなかった場合に相当するので、前提とする対応関係は、下記式（４）のようになる。
ｆ（ｅS1）＝ｅD1、
ｆ（ｅS2）＝ｅD2、
ｘ（ｆ（ＰS1））＝ｘ（ＰD3）、
ｆ（ＣS）＝ＣD
・・・（４）
【０１１６】
上記式（４）の前提で写像ｆを算出して、選択判断基準を、上記計算式（２）の不等式で評価する。この他の場合においても、図１３に従って写像ｆの算出及び選択判断基準の不等式評価を行う。このようにして、位置推定方式を吟味していき、方式１２の選択判断基準を満たさない場合は、方式１３を選択する。
【０１１７】
このように、実施の形態４による画像位置推定装置１Ｂは、位置推定方式選択部３ａによって、特徴点検出部５で複製画像から検出した特徴点の位置関係を計算し、この位置関係に応じて選択する位置推定方式を変更する。これにより、特徴点に応じた適切な位置推定方式を、その都度選択することができるので、元画像と複製画像との位置関係を推定する際の精度を向上できる。
【０１１８】
以上のように、この実施の形態４によれば、特徴点検出部５が、複製画像を画像解析して、当該複製画像で元画像に設定された特徴点に対応する特徴点を検出し、位置推定方式選択部３ａが、元画像の特徴点に対応して複製画像でとり得る特徴点の位置関係を選択基準として、元画像の辺及び特徴点と複製画像の辺及び当該複製画像から検出された特徴点との間で推定される対応関係がそれぞれ規定された複数の位置推定方式を有しており、特徴点検出部５によって複製画像から検出された特徴点の位置関係を解析した結果に基づいて、複数の位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択する。このように構成することでも、元画像と複製画像との位置合わせの精度を向上させることができる。
【０１１９】
なお、上記実施の形態４では、画像の画素値の最下位ビットに特徴点情報を与える方法によって元画像に特徴点を設定する場合を示した。この方法で特徴点を設定した場合に、階調（画素の深さ、ｄｅｐｔｈ）の削減、画像圧縮、画素値に低域通過フィルタが施される等により、最下位ビットの情報が書き換わる可能性がある。この場合は、特徴点情報の検出が困難となるかも知れない。これに対しては、上述の処理に対して耐性のある電子透かし技術で特徴点情報を与えることで、特徴点情報に強い画像処理耐性を持たせる。
【０１２０】
また、実施の形態４の画像位置推定装置１Ｂにおいても、元画像への特徴点の埋め込みに電子透かし技術を使用してもよく、元画像に特徴点を与える方法は任意の方法であってよい。但し、特徴点検出部５は、その特徴点埋め込み方法に応じた特徴点検出方法を備える必要がある。
【０１２１】
さらに、上記実施の形態４では、位置推定方式の選択判断基準の不等式を計算式（２）としたが、これは一例であり、他の式を採用してもよい。例えば、下記式（５）を、各位置推定方式の選択判断基準の不等式としても構わない。この不等式（５）は、選択判断基準の不等式として有用である。
｜ｆ（ＰS1）ＰD1｜＋｜ｆ（ＰS2）ＰD2｜＋｜ｆ（ＰS3）ＰD3｜＋｜ｆ（ＰS4）ＰD4｜≦α（ｆ（｜ｅS1｜）＋ｆ（｜ｅS3｜）） ・・・（５）
【０１２２】
また、上記実施の形態４において、位置推定方式ごとに異なる選択判断基準の不等式を採用してもよい。つまり、位置推定方式選択部３ａは、元画像と複製画像との関係において、特徴点の対応関係と特徴点以外の対応関係との両立性を判定する任意の方法を採用した構成を適用できる。
【０１２３】
さらに、上記実施の形態４の構成に対して上記実施の形態１で示した境界線推定部２を備え、位置推定方式選択部３ａが、元画像の特徴点に対応して複製画像でとり得る特徴点の位置関係を選択基準として、元画像に設定された特徴点と複製画像から検出された特徴点との間で推定される対応関係が規定された位置推定方式と、複製画像でとり得る境界線の位置関係及び元画像の特徴点に対応して複製画像でとり得る特徴点の位置関係を選択基準として、元画像の辺と複製画像の辺又は境界線との間で推定される対応関係と、元画像に設定した特徴点と複製画像から検出された特徴点との対応関係が規定された位置推定方式と、複製画像でとり得る境界線の位置関係及び元画像の特徴点に対応して複製画像でとり得る特徴点の位置関係を選択基準として、元画像の辺と複製画像の辺との間で推定される対応関係と、元画像に設定された特徴点と複製画像から検出された特徴点との対応関係が規定された位置推定方式とを有しており、境界線推定部２によって複製画像から推定された境界線の位置関係又は特徴点検出部５によって複製画像から検出された特徴点の位置関係を解析した結果に基づいて、自身が有する位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択する。このように構成することで、さらに元画像と複製画像との位置合わせの精度を向上させることができる。
【０１２４】
実施の形態５．
この実施の形態５では、上記実施の形態４の特徴点検出部５を備えた電子透かし検出装置について説明する。
図１４は、この発明の実施の形態５による電子透かし検出装置の構成を示すブロック図である。図１４において、実施の形態５の電子透かし検出装置１Ｃは、元画像と元画像を複製した複製画像において、一方の画像の任意な位置に対応する他方の画像の位置の対応関係を推定し、この対応関係を基に電子透かし情報を検出して電子透かし情報及び電子透かし情報検出の成否を出力する装置である。
なお、電子透かし検出装置１Ｃに扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態５で扱われる画像が複製されたものであることを、電子透かし検出装置１Ｃの動作要件とするものではない。
【０１２５】
図１４に示すように、電子透かし検出装置１Ｃは、特徴点検出部５、位置推定方式選択部３ａ及び電子透かし情報検出部４を備える。ここで、特徴点検出部５及び位置推定方式選択部３ａは、上記実施の形態４で図１０を用いて説明した構成と同様である。また、電子透かし情報検出部４は、上記実施の形態３で図７を用いて説明した構成と同様である。
【０１２６】
次に動作について説明する。
図１５は、実施の形態５の電子透かし検出装置による動作の流れを示すフローチャートであり、画像位置の推定及び電子透かし検出手順の一例を示している。以降では、図１４に示す構成を、図１５に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、特徴点検出部５、位置推定方式選択部３ａ及び電子透かし情報検出部４にそれぞれ入力される。特徴点検出部５は、入力した複製画像を画像解析することにより、この複製画像の元画像に予め埋め込んであった特徴点を検出する（ステップＳＴ１ｃ；特徴点検出ステップ）。特徴点検出部５による特徴点検出は、上記実施の形態４と同様である。
【０１２７】
位置推定方式選択部３ａは、得られた複製画像及び特徴点検出部５が判断した０個以上の特徴点を解析し、元画像と複製画像との位置関係を推定する方式のうち、当該複製画像に適したものを選択する（ステップＳＴ２ｃ；位置推定方式選択ステップ）。位置推定方式選択部３ａの処理は、上記実施の形態４と同様であるが、複製画像に適した位置推定方式が特定できなかった際の選択やり直しの処理が異なる。この処理については後述する。
【０１２８】
続いて、電子透かし情報検出部４が、位置推定方式選択部３により選択された位置推定方式に基づいて、複製画像と元画像との位置関係の対応付けを行い、この位置関係から、電子透かし情報の検出処理を行う（ステップＳＴ３ｃ；電子透かし情報検出ステップ）。
【０１２９】
次に、電子透かし情報検出部４は、電子透かし情報の検出の成否を判断する（ステップＳＴ４ｃ；成否判断ステップ）。実施の形態５においても、電子透かし情報が誤り検出符号を含んでいるとした場合、電子透かし情報検出部４は、電子透かし情報の検出処理で得られた誤り検出符号から電子透かし情報の検出の成否を判断する。
【０１３０】
電子透かし情報検出部４にて電子透かし情報の検出に失敗すると（ステップＳＴ４ｃ；失敗）、位置推定方式選択部３ａは、まだ選択していない選択可能な位置推定方式が残っているか否かを判定する（ステップＳＴ５ｃ；選択可否判定ステップ）。
このとき、選択可能な位置推定方式が残っていれば（ステップＳＴ５ｃ；ＹＥＳ）、ステップＳＴ２ｃの処理に戻り、位置推定方式選択部３ａが、残りの位置推定方式を選択し、選択可能な残りの位置推定方式が無くなるまで（ステップＳＴ５ｃ；ＮＯ）、ステップＳＴ２ｃ以降の処理を繰り返す。
【０１３１】
このように、実施の形態５の電子透かし検出装置１Ｃは、電子透かし情報の検出に失敗すると、位置推定方式の選択からやり直す。このようにすることで、もし最初に選択した位置推定方式が不適切であったとしても、より適切な位置推定方式を選んで、電子透かし情報の検出をやり直すことができる。これにより、位置推定方式の選択及び電子透かし情報の検出をそれぞれ一度しか実施しない構成と比べて、電子透かし情報の検出成功率を向上させることができる。
【０１３２】
位置推定方式選択部３ａは、２度目以降の位置推定方式の選択において、以前に選択した位置推定方式を選択肢から外し、その上で、１度目と同じ手順で位置推定方式を一つ選択する。選択された位置推定方式を使用して電子透かし情報検出部４が再度電子透かし情報の検出を試みる。この処理を、用意された位置推定方式（例えば、図１３に示す方式１、方式５から方式９、方式１２、方式１３）のうち、選択可能な位置推定方式の候補がなくなった上で、電子透かし情報の検出に失敗したら、位置推定方式選択部３ａは、最終的に電子透かし情報の検出を失敗として終了する。
【０１３３】
図１３に示す候補リストの中の方式１、方式５から方式９、方式１２、方式１３の位置推定方式から選択する場合を例に挙げて、具体的に位置推定方式の選択やり直しの手順を説明する。
位置推定方式選択部３ａは、方式１を選択した後に位置推定方式の選択をやり直す場合、方式１を選択肢から除き、方式５から方式９、方式１２、方式１３の中から選択する。
方式５の選択基準を満たしていれば方式５を、そうでなければ、方式６以降の選択判断基準を満たしているかどうかを順に計算し、選択判断基準を満たしている方式のうち、最も方式番号の若い方式を選択する。
【０１３４】
さらに位置推定方式選択をやり直す場合、位置推定方式選択部３ａは、それまで選んだ選択肢を全て除外し、残った位置推定方式のうち選択可能のものがなくなるか、電子透かし情報の検出に成功するまで、位置推定方式選択を繰り返す。
なお、特徴点検出部５が検出した特徴点の数によって、位置推定方式の選択が異なる。特徴点が一つも検出されなかった場合は、方式１しか選択できない。従って、この場合に方式１を選択した後は、選択可能な位置推定方式が残っていないので、位置推定方式選択部３ａは、処理を終了する。
特徴点が１つだけ検出された場合は、選択可能な位置推定方式は、方式１、方式５から方式７の４方式のみである。特徴点が２つ又は３つ検出された場合、方式１、方式５から方式９、方式１２の７つの方式が選択可能である。特徴点が４つ検出された場合のみ、これらに加えて方式１３が選択可能となる。
【０１３５】
以上のように、この実施の形態５によれば、位置推定方式選択部３ａにより選択された位置推定方式から、元画像と複製画像との間で位置の対応付けを行い、この対応関係に基づいて、元画像で電子透かし情報が埋め込まれた箇所に対応すると推定される複製画像の位置を特定して、当該複製画像から電子透かし情報を検出する電子透かし情報検出部４を備える。このように構成することで、元画像と複製画像との位置合わせが正確に行われ、電子透かし情報検出の成功率を高めることができる。
【０１３６】
また、上記実施の形態５によれば、位置推定方式選択部３ａが、特徴点検出部５にて複製画像から検出された特徴点の位置関係を計算し、選択する位置推定方式を変更する上、電子透かし情報の検出に失敗すると、位置推定方式の選択をやり直すことができる。
このため、特徴点を有効に活用して元画像と複製画像との位置関係を推定する際の精度を向上させつつ、位置推定方式の再選択により最終的な電子透かし情報の検出率を向上させることができる。
【０１３７】
実施の形態６．
この実施の形態６では、上記実施の形態１の境界線推定部２及び上記実施の形態４の特徴点検出部５を備えた電子透かし検出装置について説明する。
図１６は、この発明の実施の形態６による電子透かし検出装置の構成を示すブロック図である。図１６において、実施の形態６の電子透かし検出装置１Ｄは、元画像と元画像を複製した複製画像において、一方の画像の任意な位置に対応する他方の画像の位置の対応関係を推定し、この対応関係を基に電子透かし情報を検出して電子透かし情報及び電子透かし情報検出の成否を出力する装置である。
なお、電子透かし検出装置１Ｄに扱われる画像を“複製画像”と呼称したが、これは、“元画像”と区別するためであって、この実施の形態６で扱われる画像が複製されたものであることを、電子透かし検出装置１Ｄの動作要件とするものではない。
【０１３８】
また、図１６に示すように、電子透かし検出装置１Ｄは、境界線推定部２、特徴点検出部５、位置推定方式選択部３ｂ及び電子透かし情報検出部４を備える。ここで、境界線推定部２は、上記実施の形態１で図１を用いて説明した構成と同様である。また、電子透かし情報検出部４は、上記実施の形態３で図７を用いて説明した構成と同様であり、特徴点検出部５は、上記実施の形態４で図１０を用いて説明した構成と同様である。
【０１３９】
位置推定方式選択部３ｂは、複製画像と元画像との間で推定され得る位置関係を示し、かつ複製画像と元画像に予め埋め込んだ特徴点との間で推定され得る様々な位置関係をそれぞれ示す複数の位置推定方式を有し、複製画像と境界線推定部２で推定した境界線とを解析した結果に基づいて、複数の位置推定方式のうち、対象画像に対応する位置推定方式を選択するとともに、複製画像と特徴点検出部５で検出された特徴点とを解析した結果に基づいて、対象画像に対応する位置推定方式を選択する構成部である。
【０１４０】
次に動作について説明する。
図１７は、実施の形態６の電子透かし検出装置による動作の流れを示すフローチャートであり、画像位置の推定及び電子透かし検出手順の一例を示している。以降では、図１６に示す構成を、図１７に示す各処理ステップの動作に対応付けて説明する。
処理対象の複製画像は、境界線推定部２、位置推定方式選択部３ｂ、特徴点検出部５及び電子透かし情報検出部４にそれぞれ入力される。境界線推定部２は、入力した複製画像を画像解析することで、この複製画像の元画像に含まれる領域と含まれない領域との境界線として、上境界線、下境界線、左境界線、右境界線を推定する（ステップＳＴ１ｄ；境界線推定ステップ）。境界線推定部２による境界線の推定は、上記実施の形態１と同様である。
【０１４１】
特徴点検出部５は、入力した複製画像を画像解析することで、この複製画像の元画像に予め埋め込んであった特徴点を検出する（ステップＳＴ２ｄ；特徴点検出ステップ）。特徴点検出部５による特徴点検出は、上記実施の形態４と同様である。
【０１４２】
位置推定方式選択部３ｂは、得られた複製画像、境界線推定部２が推定した上境界線、下境界線、左境界線、右境界線、特徴点検出部５が検出した０個以上の特徴点を解析し、元画像と複製画像との位置関係を推定する位置推定方式のうち、当該複製画像に適したものを選択する（ステップＳＴ３ｄ；位置推定方式選択ステップ）。
【０１４３】
ここでは、説明上の便宜のため、上記実施の形態４の図１２を例に挙げて説明する。
図１２において、元画像の上辺、下辺、左辺、右辺を、それぞれ線分ｅS1、線分ｅS2、線分ｅS3、線分ｅS4とする。元画像の中心を点ＣSとする。元画像の４つの特徴点の中心を、左上、右上、左下、右下の順にそれぞれ点ＰS1、点ＰS2、点ＰS3、点ＰS4とする。また、複製画像の上辺、下辺、左辺、右辺を、それぞれ線分ｅD1、線分ｅD2、線分ｅD3、線分ｅD4とする。複製画像の中心を点ＣDとする。複製画像から検出された特徴点のうち、特徴点検出部５によって相対的に左上、右上、左下、右下の位置にあると判断されたものを、それぞれ点ＰD1、点ＰD2、点ＰD3、点ＰD4とする。
【０１４４】
境界線推定部２によって推定された上境界線、下境界線、左境界線、右境界線を、それぞれ線分ｂD1、ｂD2、ｂD3、ｂD4とする。この実施の形態６では、位置推定方式選択部３ｂが選択する位置推定方式は、図１３の候補リストにおける方式１から方式１３までの１３通りとする。
【０１４５】
位置推定方式選択部３ｂは、方式１から順に選択判断基準を満たすかどうかを確認し、満たす場合はその方式を選択し、満たさない場合は次の方式が選択判断基準を満たすかどうかを確認する。これを繰り返して、方式１から方式１２までの全ての方式で選択判断基準を満たさない場合は方式１３を選択する。
【０１４６】
このようにして位置推定方式を選択することにより、特徴点検出部５が検出した特徴点の個数に応じて採用する位置推定方式が適切に選択される。検出された特徴点が０個の場合は、方式１が選択される。検出された特徴点が１個の場合は、方式１から方式７までの位置推定方式の中から選択される。これは、検出された特徴点が１個の場合に方式７の選択判断基準を必ず満たす（不等式左辺が０になる）からである。
【０１４７】
検出された特徴点が２個又は３個の場合、方式１２まで選択判断基準を満たさない可能性がある。この場合、位置推定方式選択部３ｂは、特徴点検出部５に検出された特徴点の組み合わせに対して適用可能な位置推定方式のうち、方式番号が最後のものを選択する。
例えば、ＰD1、ＰD2、ＰD4が検出され、方式１２まで選択判断基準を満たさない場合は、方式１２を選択する。ＰD1、ＰD2が検出され、方式１０まで選択判断基準を満たさない場合は、方式１０を選択する（方式１１と方式１２は適用できないため）。検出された特徴点が４個の場合は、方式１２まで選択判断基準を満たさない場合は、方式１３を選択するものとする。
【０１４８】
図１７のフローチャートの説明に戻る。
電子透かし情報検出部４は、位置推定方式選択部３ｂが選択した位置推定方式を基に、複製画像と元画像との位置関係の対応付けを行い、この位置関係から、電子透かし情報の検出処理を行う（ステップＳＴ４ｄ；電子透かし情報検出ステップ）。
次に、電子透かし情報検出部４は、電子透かし情報の検出の成否を判断する（ステップＳＴ５ｄ；成否判断ステップ）。
【０１４９】
元画像の特定の位置に電子透かし情報が埋め込まれている場合、電子透かし情報検出部４は、位置推定方式選択部３ｂが選択した位置推定方式に基づいて、複製画像と元画像との位置関係の対応付けを認識して電子透かし情報を検出する。実施の形態６においても、電子透かし情報が誤り検出符号を含んでいるとした場合、電子透かし情報検出部４は、電子透かし情報の検出処理で得られた誤り検出符号から電子透かし情報の検出の成否を判断する。
【０１５０】
電子透かし情報検出部４にて電子透かし情報の検出に失敗すると（ステップＳＴ５ｄ；失敗）、位置推定方式選択部３ｂは、まだ選択していない選択可能な位置推定方式が残っているか否かを判定する（ステップＳＴ６ｄ；選択可否判定ステップ）。
このとき、選択可能な位置推定方式が残っていれば（ステップＳＴ６ｄ；ＹＥＳ）、ステップＳＴ３ｄの処理に戻り、位置推定方式選択部３ｂが、残りの位置推定方式を選択し、選択可能な残りの位置推定方式が無くなるまで（ステップＳＴ６ｄ；ＮＯ）、ステップＳＴ３ｄ以降の処理を繰り返す。
【０１５１】
このように、実施の形態６の電子透かし検出装置１Ｄは、電子透かし情報の検出に失敗すると、位置推定方式の選択からやり直す。このようにすることで、もし最初に選択した位置推定方式が不適切であったとしても、より適切な位置推定方式を選んで、電子透かし情報の検出をやり直すことができる。これにより、位置推定方式の選択及び電子透かし情報の検出をそれぞれ一度しか実施しない構成と比べて、電子透かし情報の検出成功率を向上させることができる。
【０１５２】
位置推定方式選択部３ｂは、２度目以降の位置推定方式の選択において、以前に選択した位置推定方式を選択肢から外し、その上で、１度目と同じ手順で位置推定方式を一つ選択する。選択された位置推定方式を使用して電子透かし情報検出部４が再度電子透かし情報の検出を試みる。この処理を、用意された位置推定方式（例えば、図１３に示す方式１から方式１３）のうち、特徴点の数に応じて使用可能な位置推定方式を全て選択し終え、選択可能な位置推定方式の候補がなくなった上で、電子透かし情報の検出に失敗すると、最終的に電子透かし情報の検出が失敗したものとして処理を終了する。
【０１５３】
以上のように、この実施の形態６では、境界線推定部２が、複製画像を画像解析して、複製画像で元画像に含まれる画像領域と元画像に含まれない画像領域との境界線を推定するとともに、特徴点検出部５が、複製画像を画像解析して、当該複製画像で元画像に設定された特徴点に対応する特徴点を検出し、位置推定方式選択部３ｂが、境界線推定部２によって複製画像から推定された境界線の位置関係又は特徴点検出部５によって複製画像から検出された特徴点の位置関係を解析した結果に基づいて、自身が有する位置推定方式のうちから、当該複製画像に対応した位置推定方式を選択して、電子透かし情報検出部４が、選択された位置推定方式から、元画像と複製画像との間で位置の対応付けを行い、この対応関係に基づいて、元画像で電子透かし情報が埋め込まれた箇所に対応すると推定される複数画像の位置を特定して、当該複数画像から電子透かし情報を検出する。このように構成することで、元画像と複製画像との位置合わせが正確に行われ、電子透かし情報検出の成功率を高めることができる。
【０１５４】
上記実施の形態６では、位置推定方式選択部３ｂにより選択可能な各位置推定方式が、図１３に示す対応関係を前提とする場合を示したが、これは一例であって、他の対応関係を前提としてもよい。
例えば、最小二乗誤差法（最小二乗法）を適用して対応関係を設定する方法もある。
この方法は、図１３に示す選択判断基準の不等式の左辺値が、右辺値に対して小さくなるように写像ｆを決定することに他ならない。このような対応関係の設定の仕方は複数通りあり、どの方法で装置１Ｄに設定しても構わない。
【０１５５】
また、画像に設定される特徴点が４つである場合を示したが、それ以外の個数の特徴点を元画像に埋め込んでも構わない。
例えば、特徴点をＰS1一つだけしか埋め込まない方法を前提として、装置１Ｄを構成することも可能である。この場合、特徴点が一つしかないので、方式１から方式７までしか適用できない。このため、位置推定方式選択部３ｂは、方式１から方式７までの位置推定方式から位置推定方式を選択する。
また、この場合は、選択判断基準である上記計算式（２）の不等式の左辺は、第１項のみ評価し、第２項から第４項を０として扱えばよい。特徴点を２つあるいは３つとする場合も同様に、適用可能な位置推定方式のみを選択肢とし、選択判断基準の不等式の左辺で無関係な項を無視すればよい。
さらに、特徴点を５つ以上とすることもできる。この場合は、選択判断基準の不等式の左辺は、それぞれの特徴点の誤差二乗和となるため、全５項となる。
元画像に特徴点が５つ以上埋め込まれている場合は、特徴点検出部５が、複製画像から５つ以上の特徴点を検出する可能性があるが、このとき、方式５から方式１３において、写像ｆを適切に推定する対応関係を設定しなければならない。このような場合、最小二乗誤差法を適用するなどして、得られた特徴点の全てから推定される最も確からしい写像ｆを決定すればよい。
【０１５６】
また、特徴点を使用しない実装も可能である。この場合は、特徴点を必要とする方式５から方式１３は適用できない。方式１から方式４の４つの選択肢から位置推定方式を選択することになる。しかし、特徴点がないため、位置推定方式の選択判断をすることができない。
このような場合、位置推定方式選択部３ｂは、方式１から順に選択する。
方式１に基づいて電子透かし情報検出部４が電子透かし検出に失敗すると、位置推定方式選択部３ｂは、次に方式２、またその次に方式３と順番に位置推定方式を選択し、選択された位置推定方式に基づいて、電子透かし情報検出部４が、電子透かし情報の検出を試みる。この後、電子透かし情報検出部４が、方式４に基づく電子透かし情報の検出に失敗すると、最終的に電子透かし情報の検出が失敗としたと判断して処理を終了する。
以上のように、元画像に埋め込む特徴点の数に制限はないため、元画像に設定する特徴点の数に応じて適切に特徴点検出部５及び位置推定方式選択部３ｂを構成すれば、任意個の特徴点を使用する電子透かし検出装置１Ｄを構成可能である。
【０１５７】
上述の説明では、元画像に設定する特徴点の位置は、図１２に示したように、長方形の元画像の、上から４分の１で、かつ左から４分の１の位置、上から４分の１で、かつ右から４分の１の位置、下から４分の１で、かつ左から４分の１の位置、下から４分の１で、かつ右から４分の１の位置としたが、長方形の元画像に対する相対的な位置さえ明確であれば、特徴点の位置は任意とすることができる。
さらに、画像に設定されている特徴点の形状が円である場合を示したが、三角形や四角形など、他の形状でもよく、任意の形状とすることができる。
このように、特徴点の位置や形状に制限はないため、元画像に設定する特徴点の位置や形状に応じて適切に特徴点検出部５及び位置推定方式選択部３ｂを構成すれば、元画像上の任意の位置にある、任意の形状の特徴点を使用する電子透かし検出装置１Ｄを構成することができる。
【０１５８】
また、位置推定方式選択部３ｂが選択した位置推定方式は、電子透かし情報検出部４に出力されるが、位置推定方式が選択されたということは、この位置推定方式が前提とする対応関係が選択されたことを意味し、写像ｆも特定される。
従って、電子透かし情報検出部４は、位置推定方式選択部３ｂで選択された位置推定方式を受け取ることにより、写像ｆについての情報を取得している。
【０１５９】
このような、位置推定方式選択部３ｂと電子透かし情報検出部４との間の情報のやり取りは、具体的には様々な実現方法が可能である。
一つは、射影変換を前提として、位置推定方式選択部３ｂから電子透かし情報検出部４には、射影変換ｆを一意に特定するパラメータ群のみを渡す方法が考えられる。
方式１から方式１３までの全位置推定方式は全て射影変換であり、直交変換や直交変換と平行移動の組み合わせは、数学的には射影変換の特別な場合に相当する。
よって、上記のようにパラメータのみを渡す実装が可能である。この場合、方式番号を位置推定方式選択部３ｂから電子透かし情報検出部４に渡す必要はなく、また、電子透かし情報検出部４が、図１３に示すような位置推定方式の候補リストを保持する必要もないため、実装が簡略化される。
この他には、位置推定方式選択部３ｂが、選択した位置推定方式に基づいて、元画像の画素と複製画像の画素とのマッピング情報を作成し、これを電子透かし情報検出部４に渡す方法である。
このようにしても、位置推定方式選択部３ｂは、選択した位置推定方式を電子透かし情報検出部４に伝えたことになる。電子透かし情報検出部４では、位置推定方式選択部３ｂから入力したマッピング情報を基に、元画像と複製画像との位置関係を把握し、元画像のある特定の場所に埋め込まれた電子透かし情報の検出を試みることが可能である。
なお、この場合、電子透かし情報検出部４は、改めて写像ｆを用いた位置推定の計算をする必要がなくなるため、処理が高速化される。
【０１６０】
勿論、位置推定方式選択部３ｂから電子透かし情報検出部４に方式番号を渡すように実装することもできる。この場合は、電子透かし情報検出部４は、写像ｆを特定できないため、位置推定方式選択部３ｂは、方式番号に加えて、特徴点の情報も渡さなければならない。電子透かし情報検出部４は、位置推定方式選択部３ｂから受け取った方式番号と特徴点の情報を使用して、図１３のような位置推定方式の候補リストを参照し、位置推定方式を選択するための選択判断の計算を改めて行う必要がある。
このように、位置推定方式は、その方式番号だけを指すのではなく、画像の位置を推定する指針として、写像ｆを特定するのに必要となる情報である。
【０１６１】
上記実施の形態６では、位置推定方式選択部３ｂが、図１３に示す候補リストのうち、方式１から方式１３を方式１から順に選択判断基準を満たすかどうか判定し、満たす場合にそれ以降の方式の選択判断を行わない場合を示した。
この場合についても他の処理が考えられる。例えば、位置推定方式選択部３ｂが、境界線推定部２に推定された境界線及び特徴点検出部５に検出された特徴点から、適用可能な位置推定方式の全てにおいて下記式（６）を計算し、この計算結果が小さいものから優先して選択する。
（｜ｆ（ＰS1）ＰD1｜2＋｜ｆ（ＰS2）ＰD2｜2＋｜ｆ（ＰS3）ＰD3｜2＋｜ｆ（ＰS4）ＰD4｜2）／（ｆ（｜ｅS1｜）2＋ｆ（｜ｅS3｜）2）
・・・（６）
【０１６２】
上述の選択方法を採用することで、図１３に示す候補リストにおいて、方式番号が下位に位置する位置推定方式であっても、優先して選択することができる。これにより、電子透かし情報の検出完了までに必要な位置推定方式の選択やり直し回数が低減する可能性がある。
【０１６３】
また、単に上記式（６）の計算値が小さいものから優先して選択するのでなく、上記式（６）の計算値がα2を超えた時点で、適用可能な位置推定方式が残されていても処理を打ち切るようにしてもよい。このようにすることで、電子透かし情報の検出成功の可能性が低い場合に、成功する可能性の低い位置推定方式の選択及び電子透かし情報の検出の試行を抑制することができ、全体の計算量を削減できる。
勿論、上記式（６）に限らず、他の計算式を使用することもできる。さらに、位置推定方式の選択やり直し回数に上限を設け、選択可能な位置推定方式が残されていても処理を打ち切ることも可能である。このようにしても、成功する可能性の低い位置推定方式の選択及び電子透かし情報の検出の試行を抑制することができ、全体の計算量を削減できる。
【０１６４】
さらに、これまでの説明は、画像の画素値の最下位ビットを使用して特徴点を設定する場合を示したが、この方法では、特徴点の一つ一つを区別できない。このため、特徴点検出部５が、元画像の、左上、右上、左下、右下に特徴点が設定される前提で、複製画像の左上の特徴点（ＰD1）、右上の特徴点（ＰD2）、左下の特徴点（ＰD3）、右下の特徴点（ＰD4）をそれぞれ元画像の左上の特徴点（ＰS1）、右上の特徴点（ＰS2）、左下の特徴点（ＰS3）、右下の特徴点（ＰS4）に対応すると判断した。
【０１６５】
これに対して、電子透かし技術を利用して、検出時に検出された特徴点が元画像の特徴点のどれに対応するのかを判定できる特徴点埋め込み方法をとった場合には、ＰS1に相当する特徴点が複製画像の左下から検出され、ＰS3に相当する特徴点が複製画像の左上から検出される可能性もある。この場合、左下にＰD1、左上にＰD3が検出されるため、例えば、元画像の上辺、下辺、左辺、右辺が、それぞれ複製画像の上辺、下辺、左辺、右辺に対応する位置関係を示す位置推定方式よりも、元画像の上辺、下辺、左辺、右辺が、それぞれ複製画像の下辺、上辺、左辺、右辺に対応する位置関係を示す位置推定方式が採用される。このような位置推定方式は図１３の候補リストにはないが、特徴点を区別する場合には設けることが望ましい。
【０１６６】
上述の位置推定方式が示す位置関係は、複製の過程で元画像が上下反転した場合に起こり得る。特徴点を位置推定方式上で区別しない場合、画像の上下反転は検出できないが、検出された個々の特徴点が元画像の特徴点のどれに対応するか判定できるように挿入されていれば、上下反転を検出して、適切な位置推定を行うことができる。
特徴点が区別できれば、上下反転のみならず、左右反転、上下左右反転、９０度回転、１８０度回転などの検出も可能となる。
従って、位置推定方式にて個々の特徴点を区別する情報を与えておき、これに基づいて特徴点検出部５が特徴点を区別して検出し、位置推定方式選択部３ｂが区別ある特徴点を使用して適切に位置推定方式を選択することにより、複製画像に反転や回転の処理が加えられていても、元画像との適切な位置推定が可能である。
【０１６７】
さらに、これまでの説明では、位置推定方式を、図１３の候補リストから選択する場合を示したが、位置推定方式選択部３，３ａ，３ｂが、図１３に記載のもの以外の位置推定方式を用意し、選択肢とすることもできる。例えば、前段落で述べた、反転や回転に対応した位置推定方式を選択肢として用意することができる。
この他、図１３に記載していないが、元画像の上辺が複製画像の上境界線に、元画像の左辺が複製画像の左辺にそれぞれ対応し、元画像の上下方向及び左右方向がそれぞれ複製画像のちょうど上下方向及び左右方向となり、複製画像から検出された一つ以上の特徴点が元画像に設定された一つ以上の特徴点のどれか一つに対応するとする対応関係を前提とする位置推定方式が考えられる。
【０１６８】
また、元画像の上辺及び下辺が、複製画像の上境界線及び下境界線にそれぞれ対応し、元画像の中心が、複製画像において元画像に含まれると推定された領域の中心を通る上下方向の線上の点に対応しており、元画像の上下方向及び左右方向が、複製画像のちょうど上下方向及び左右方向にそれぞれ対応し、複製画像から検出された一つ以上の特徴点が元画像に設定された一つ以上の特徴点のどれか一つに対応するという対応関係を前提とする位置推定方式なども考えられる。
【０１６９】
さらに、図１３で示した方式１から方式１３の位置推定方式では、直線は必ず直線に写像されるが、直線が曲線に歪むような強烈な歪みが複製の過程で与えられても複製画像から元画像の位置を推定できる位置推定方式を選択肢として用意してもよい。
例えば、カメラ撮影で元画像が複製された場合に、カメラのレンズ歪の補正をモデル化した写像を取り入れた位置推定方式を選択肢として加える。これにより、カメラのレンズ歪まで考慮した精度の高い位置推定が可能となる。
このように、位置推定方式選択部３，３ａ，３ｂが選択肢として用意する位置推定方式は、任意に設定可能である。
【符号の説明】
【０１７０】
１，１Ｂ 画像位置推定装置、１Ａ，１Ｃ，１Ｄ 電子透かし検出装置、２ 境界線推定部、３，３ａ，３ｂ 位置推定方式選択部、４ 電子透かし情報検出部、５ 特徴点検出部。
【特許請求の範囲】
【請求項１】
第１の画像と画像中に前記第１の画像の全部又は一部を含む第２の画像との間で、一方の画像中の位置に対応する他方の画像中の位置を推定する画像位置推定装置において、
前記第２の画像を画像解析して、当該第２の画像で前記第１の画像に含まれる画像領域と前記第１の画像に含まれない画像領域との境界線を推定する境界線推定部と、
前記第２の画像でとり得る境界線の位置関係を選択基準として、前記第１の画像の辺と前記第２の画像の辺又は前記境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、前記境界線推定部によって前記第２の画像から推定された境界線の位置関係を解析した結果に基づいて、前記複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択部とを備えたことを特徴とする画像位置推定装置。
【請求項２】
第１の画像と画像中に前記第１の画像の全部又は一部を含む第２の画像との間で、一方の画像中の位置に対応する他方の画像中の位置を推定する画像位置推定装置において、
前記第２の画像を画像解析して、当該第２の画像で前記第１の画像に設定された特徴点に対応する特徴点を検出する特徴点検出部と、
前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の辺及び特徴点と前記第２の画像の辺及び当該第２の画像から検出された特徴点との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、前記特徴点検出部によって前記第２の画像から検出された特徴点の位置関係を解析した結果に基づいて、前記複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択部とを備えたことを特徴とする画像位置推定装置。
【請求項３】
前記第２の画像を画像解析して、当該第２の画像で前記第１の画像に設定された特徴点に対応する特徴点を検出する特徴点検出部を備え、
前記選択部は、
前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像に設定された特徴点と前記第２の画像から検出された特徴点との間で推定される対応関係が規定された第１の位置推定情報と、
前記第２の画像でとり得る境界線の位置関係及び前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の辺と前記第２の画像の辺又は前記境界線との間で推定される対応関係と、前記第１の画像に設定した特徴点と前記第２の画像から検出された特徴点との対応関係が規定された第２の位置推定情報と、
前記第２の画像でとり得る境界線の位置関係及び前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の辺と前記第２の画像の辺との間で推定される対応関係と、前記第１の画像に設定された特徴点と前記第２の画像から検出された特徴点との対応関係が規定された第３の位置推定情報とを有しており、
前記境界線推定部によって前記第２の画像から推定された境界線の位置関係又は前記特徴点検出部によって前記第２の画像から検出された特徴点の位置関係を解析した結果に基づいて、自身が有する位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択することを特徴とする請求項１記載の画像位置推定装置。
【請求項４】
前記選択部は、前記第１の画像の各辺の関係、前記第２の画像でとり得る境界線の位置関係及び前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の上下方向及び左右方向が前記第２の画像の上下方向及び左右方向にそれぞれ対応する位置関係を示す第４の位置推定情報を有することを特徴とする請求項２又は請求項３記載の画像位置推定装置。
【請求項５】
前記選択部は、前記第１の画像の各辺の関係、前記第２の画像でとり得る境界線の位置関係及び前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の中心が、前記第２の画像で前記第１の画像に含まれると推定された領域の中心を通る上下方向の線上又は左右方向の線上の点、若しくはこれらの線の交点に対応する位置関係を示す第５の位置推定情報を有することを特徴とする請求項４記載の画像位置推定装置。
【請求項６】
前記選択部は、前記第１の画像の各辺の関係、前記境界線推定部によって前記第２の画像から推定された境界線の位置関係及び前記特徴点検出部によって前記第２の画像から検出された特徴点の位置関係を解析した結果に基づいて、前記位置選択情報に規定されている全ての対応関係のうち、前記第１の画像に設定した特徴点及びこれに対応して前記第２の画像から検出された特徴点の対応関係と、これ以外の対応関係とが両立するか否かを判定し、これら対応関係が両立した判定結果が得られると、当該位置推定情報を選択することを特徴とする請求項２から請求項５のうちのいずれか１項記載の画像位置推定装置。
【請求項７】
請求項１から請求項６のうちのいずれか１項記載の画像位置推定装置と、
前記画像位置推定装置の選択部により選択された位置推定情報から、第１の画像と前記第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、前記第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される前記第２の画像の位置を特定して、当該第２の画像から前記電子透かし情報を検出する電子透かし情報検出部とを備えた電子透かし検出装置。
【請求項８】
前記選択部は、
前記電子透かし情報検出部が電子透かし情報の検出に失敗すると、前記位置推定情報の選択をやり直し、
前記電子透かし情報検出部は、
前記選択部によって新たに選択された位置推定情報から、第１の画像と前記第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、前記第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される前記第２の画像の位置を特定して、当該第２の画像から前記電子透かし情報を検出することを特徴とする請求項７記載の電子透かし検出装置。
【請求項９】
境界線推定部と選択部とを備えた画像位置推定装置によって、第１の画像と、画像中に前記第１の画像の全部又は一部を含む第２の画像との間で、一方の画像中の位置に対応する他方の画像中の位置を推定する画像位置推定方法において、
前記境界線推定部が、前記第２の画像を画像解析して、当該第２の画像で前記第１の画像に含まれる画像領域と前記第１の画像に含まれない画像領域との境界線を推定する境界線推定ステップと、
前記選択部が、前記第２の画像でとり得る境界線の位置関係を選択基準として、前記第１の画像の辺と前記第２の画像の辺又は前記境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、前記境界線推定部によって前記第２の画像から推定された境界線の位置関係を解析した結果に基づいて、前記複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択ステップとを備えたことを特徴とする画像位置推定方法。
【請求項１０】
特徴点検出部と選択部とを備えた画像位置推定装置によって、第１の画像と、画像中に前記第１の画像の全部又は一部を含む第２の画像との間で、一方の画像中の位置に対応する他方の画像中の位置を推定する画像位置推定方法において、
前記特徴点検出部が、前記第２の画像を画像解析して当該第２の画像で前記第１の画像に設定された特徴点に対応する特徴点を検出する特徴点検出ステップと、
前記選択部が、前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の辺及び特徴点と前記第２の画像の辺及び当該第２の画像から検出された特徴点との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、前記特徴点検出部によって前記第２の画像から検出された特徴点の位置関係を解析した結果に基づいて、前記複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択ステップとを備えたことを特徴とする画像位置推定方法。
【請求項１１】
請求項１又は請求項２記載の画像位置推定装置と、電子透かし情報検出部とを備えた電子透かし検出装置の電子透かし検出方法において、
前記画像位置推定装置の選択部が、自身が有する位置推定情報から、第２の画像に対応する位置推定情報を選択する選択ステップと、
前記電子透かし情報検出部が、前記選択部により選択された位置推定情報から、第１の画像と前記第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、前記第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される前記第２の画像の位置を特定して、当該第２の画像から前記電子透かし情報を検出する電子透かし情報検出ステップとを備えた電子透かし検出方法。
【請求項１２】
前記選択部ステップにおいて、
前記選択部が、前記電子透かし情報検出部が電子透かし情報の検出に失敗すると、前記位置推定情報の選択をやり直し、
前記電子透かし情報検出ステップにおいて、
前記電子透かし情報検出部が、前記選択部によって新たに選択された位置推定情報から、第１の画像と前記第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、前記第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される前記第２の画像の位置を特定して、当該第２の画像から前記電子透かし情報を検出することを特徴とする請求項１１記載の電子透かし検出方法。
【請求項１３】
請求項１から請求項６のうちのいずれか１項記載の画像位置推定装置としてコンピュータを機能させるためのプログラム。
【請求項１４】
請求項７又は請求項８記載の電子透かし検出装置としてコンピュータを機能させるためのプログラム。
【請求項１】
第１の画像と画像中に前記第１の画像の全部又は一部を含む第２の画像との間で、一方の画像中の位置に対応する他方の画像中の位置を推定する画像位置推定装置において、
前記第２の画像を画像解析して、当該第２の画像で前記第１の画像に含まれる画像領域と前記第１の画像に含まれない画像領域との境界線を推定する境界線推定部と、
前記第２の画像でとり得る境界線の位置関係を選択基準として、前記第１の画像の辺と前記第２の画像の辺又は前記境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、前記境界線推定部によって前記第２の画像から推定された境界線の位置関係を解析した結果に基づいて、前記複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択部とを備えたことを特徴とする画像位置推定装置。
【請求項２】
第１の画像と画像中に前記第１の画像の全部又は一部を含む第２の画像との間で、一方の画像中の位置に対応する他方の画像中の位置を推定する画像位置推定装置において、
前記第２の画像を画像解析して、当該第２の画像で前記第１の画像に設定された特徴点に対応する特徴点を検出する特徴点検出部と、
前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の辺及び特徴点と前記第２の画像の辺及び当該第２の画像から検出された特徴点との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、前記特徴点検出部によって前記第２の画像から検出された特徴点の位置関係を解析した結果に基づいて、前記複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択部とを備えたことを特徴とする画像位置推定装置。
【請求項３】
前記第２の画像を画像解析して、当該第２の画像で前記第１の画像に設定された特徴点に対応する特徴点を検出する特徴点検出部を備え、
前記選択部は、
前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像に設定された特徴点と前記第２の画像から検出された特徴点との間で推定される対応関係が規定された第１の位置推定情報と、
前記第２の画像でとり得る境界線の位置関係及び前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の辺と前記第２の画像の辺又は前記境界線との間で推定される対応関係と、前記第１の画像に設定した特徴点と前記第２の画像から検出された特徴点との対応関係が規定された第２の位置推定情報と、
前記第２の画像でとり得る境界線の位置関係及び前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の辺と前記第２の画像の辺との間で推定される対応関係と、前記第１の画像に設定された特徴点と前記第２の画像から検出された特徴点との対応関係が規定された第３の位置推定情報とを有しており、
前記境界線推定部によって前記第２の画像から推定された境界線の位置関係又は前記特徴点検出部によって前記第２の画像から検出された特徴点の位置関係を解析した結果に基づいて、自身が有する位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択することを特徴とする請求項１記載の画像位置推定装置。
【請求項４】
前記選択部は、前記第１の画像の各辺の関係、前記第２の画像でとり得る境界線の位置関係及び前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の上下方向及び左右方向が前記第２の画像の上下方向及び左右方向にそれぞれ対応する位置関係を示す第４の位置推定情報を有することを特徴とする請求項２又は請求項３記載の画像位置推定装置。
【請求項５】
前記選択部は、前記第１の画像の各辺の関係、前記第２の画像でとり得る境界線の位置関係及び前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の中心が、前記第２の画像で前記第１の画像に含まれると推定された領域の中心を通る上下方向の線上又は左右方向の線上の点、若しくはこれらの線の交点に対応する位置関係を示す第５の位置推定情報を有することを特徴とする請求項４記載の画像位置推定装置。
【請求項６】
前記選択部は、前記第１の画像の各辺の関係、前記境界線推定部によって前記第２の画像から推定された境界線の位置関係及び前記特徴点検出部によって前記第２の画像から検出された特徴点の位置関係を解析した結果に基づいて、前記位置選択情報に規定されている全ての対応関係のうち、前記第１の画像に設定した特徴点及びこれに対応して前記第２の画像から検出された特徴点の対応関係と、これ以外の対応関係とが両立するか否かを判定し、これら対応関係が両立した判定結果が得られると、当該位置推定情報を選択することを特徴とする請求項２から請求項５のうちのいずれか１項記載の画像位置推定装置。
【請求項７】
請求項１から請求項６のうちのいずれか１項記載の画像位置推定装置と、
前記画像位置推定装置の選択部により選択された位置推定情報から、第１の画像と前記第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、前記第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される前記第２の画像の位置を特定して、当該第２の画像から前記電子透かし情報を検出する電子透かし情報検出部とを備えた電子透かし検出装置。
【請求項８】
前記選択部は、
前記電子透かし情報検出部が電子透かし情報の検出に失敗すると、前記位置推定情報の選択をやり直し、
前記電子透かし情報検出部は、
前記選択部によって新たに選択された位置推定情報から、第１の画像と前記第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、前記第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される前記第２の画像の位置を特定して、当該第２の画像から前記電子透かし情報を検出することを特徴とする請求項７記載の電子透かし検出装置。
【請求項９】
境界線推定部と選択部とを備えた画像位置推定装置によって、第１の画像と、画像中に前記第１の画像の全部又は一部を含む第２の画像との間で、一方の画像中の位置に対応する他方の画像中の位置を推定する画像位置推定方法において、
前記境界線推定部が、前記第２の画像を画像解析して、当該第２の画像で前記第１の画像に含まれる画像領域と前記第１の画像に含まれない画像領域との境界線を推定する境界線推定ステップと、
前記選択部が、前記第２の画像でとり得る境界線の位置関係を選択基準として、前記第１の画像の辺と前記第２の画像の辺又は前記境界線との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、前記境界線推定部によって前記第２の画像から推定された境界線の位置関係を解析した結果に基づいて、前記複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択ステップとを備えたことを特徴とする画像位置推定方法。
【請求項１０】
特徴点検出部と選択部とを備えた画像位置推定装置によって、第１の画像と、画像中に前記第１の画像の全部又は一部を含む第２の画像との間で、一方の画像中の位置に対応する他方の画像中の位置を推定する画像位置推定方法において、
前記特徴点検出部が、前記第２の画像を画像解析して当該第２の画像で前記第１の画像に設定された特徴点に対応する特徴点を検出する特徴点検出ステップと、
前記選択部が、前記第１の画像の特徴点に対応して前記第２の画像でとり得る特徴点の位置関係を選択基準として、前記第１の画像の辺及び特徴点と前記第２の画像の辺及び当該第２の画像から検出された特徴点との間で推定される対応関係がそれぞれ規定された複数の位置推定情報を有しており、前記特徴点検出部によって前記第２の画像から検出された特徴点の位置関係を解析した結果に基づいて、前記複数の位置推定情報のうちから、当該第２の画像に対応した位置推定情報を選択する選択ステップとを備えたことを特徴とする画像位置推定方法。
【請求項１１】
請求項１又は請求項２記載の画像位置推定装置と、電子透かし情報検出部とを備えた電子透かし検出装置の電子透かし検出方法において、
前記画像位置推定装置の選択部が、自身が有する位置推定情報から、第２の画像に対応する位置推定情報を選択する選択ステップと、
前記電子透かし情報検出部が、前記選択部により選択された位置推定情報から、第１の画像と前記第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、前記第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される前記第２の画像の位置を特定して、当該第２の画像から前記電子透かし情報を検出する電子透かし情報検出ステップとを備えた電子透かし検出方法。
【請求項１２】
前記選択部ステップにおいて、
前記選択部が、前記電子透かし情報検出部が電子透かし情報の検出に失敗すると、前記位置推定情報の選択をやり直し、
前記電子透かし情報検出ステップにおいて、
前記電子透かし情報検出部が、前記選択部によって新たに選択された位置推定情報から、第１の画像と前記第２の画像との間で位置の対応付けを行い、この対応関係に基づいて、前記第１の画像で電子透かし情報が埋め込まれた箇所に対応すると推定される前記第２の画像の位置を特定して、当該第２の画像から前記電子透かし情報を検出することを特徴とする請求項１１記載の電子透かし検出方法。
【請求項１３】
請求項１から請求項６のうちのいずれか１項記載の画像位置推定装置としてコンピュータを機能させるためのプログラム。
【請求項１４】
請求項７又は請求項８記載の電子透かし検出装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１１−１１４４５５（Ｐ２０１１−１１４４５５Ａ）
【公開日】平成２３年６月９日（２０１１．６．９）
【国際特許分類】
【出願番号】特願２００９−２６７３３２（Ｐ２００９−２６７３３２）
【出願日】平成２１年１１月２５日（２００９．１１．２５）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２３年６月９日（２０１１．６．９）
【国際特許分類】
【出願日】平成２１年１１月２５日（２００９．１１．２５）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]