(57)【要約】【課題】  電子透かしの埋め込まれた印刷画像の撮影画像から透かしを検出するためには、撮影画像から原画像領域を高精度で抽出しなければならない。【解決手段】  エッジ検出フィルタ部４２は、撮影画像に含まれる原画像領域のエッジを検出し、エッジ上の点を頂点探索開始点Ｖｓとして求める。エッジ追跡部４４は、頂点探索開始点Ｖｓから原画像領域の頂点方向にエッジラインを追跡し、エッジラインの端点を求め、原画像領域の暫定頂点Ｖｅとする。フーリエ変換処理部４６は、暫定頂点Ｖｅの周辺の画像にフーリエ変換処理を施す。位相角算出部４７は、フーリエ変換後の低周波数成分の位相角を算出する。頂点位置ずれ調整部４８は、算出された位相角にもとづき、真の頂点位置からの暫定頂点Ｖｅのずれを求め、暫定頂点Ｖｅの位置ずれを調整した最終検出頂点Ｖｆを求める。画像領域抽出部４１は、最終検出頂点Ｖｆの座標値をもとに撮影画像から原画像領域を抽出する。【選択図】  図５
2005182164.tif 000002
【特許請求の範囲】
【請求項１】
原画像が印刷された印刷媒体の撮影画像を取得する画像入力部と、
前記撮影画像における検査画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定する画像領域判定部とを含むことを特徴とする画像領域判定装置。
【請求項２】
前記画像領域判定部は、前記検査画像領域を空間周波数領域に変換した場合の低周波数成分の位相角にもとづいて、前記原画像領域のエッジを検出するエッジ検出部を含むことを特徴とする請求項１に記載の画像領域判定装置。
【請求項３】
前記画像領域判定部は、前記検査画像領域を空間周波数領域に変換した場合の低周波数成分の位相角にもとづいて、前記原画像領域の頂点の位置を特定する頂点特定部を含むことを特徴とする請求項１または２に記載の画像領域判定装置。
【請求項４】
前記エッジ検出部により検出されたエッジの端点を前記原画像領域の暫定的な頂点として、前記暫定的な頂点付近の検査画像領域を空間周波数領域に変換した場合の低周波数成分の位相角にもとづいて、前記暫定的な頂点の位置ずれを調整する頂点特定部を含むことを特徴とする請求項２に記載の画像領域判定装置。
【請求項５】
前記頂点特定部は、前記原画像領域の暫定的な頂点付近の検査画像領域を空間周波数領域に変換した場合の低周波数成分の位相角と、前記暫定的な頂点の位置に前記原画像領域の真の頂点があると仮定した場合の参照画像領域を空間周波数領域に変換した場合の低周波数成分の位相角との差にもとづいて、前記暫定的な頂点の真の位置からのずれを求めることを特徴とする請求項３または４に記載の画像領域判定装置。
【請求項６】
原画像が印刷された印刷媒体の撮影画像を取得する画像入力部と、
前記撮影画像における検査画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定する画像領域判定部と、
判定された前記原画像領域の撮影による歪みを補正する画像補正部とを含むことを特徴とする画像補正装置。
【請求項７】
電子透かしが埋め込まれた原画像が印刷された印刷媒体の撮影画像を取得する画像入力部と、
前記撮影画像における検査画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定する画像領域判定部と、
判定された前記原画像領域の撮影による歪みを補正する画像補正部と、
補正された前記原画像領域から前記電子透かしを抽出する抽出部とを含むことを特徴とする電子透かし抽出装置。
【請求項８】
原画像が印刷された印刷媒体の撮影画像を取得するステップと、
前記撮影画像における検査点付近の画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定するステップとを含むことを特徴とする画像領域判定方法。
【請求項９】
前記原画像領域を判定するステップは、前記検査点付近の画像領域を空間周波数領域に変換した場合の低周波数成分の実軸成分が実質的に零である場合に、前記検査点が前記原画像領域のエッジ上にあると判定するエッジ検出ステップを含むことを特徴とする請求項８に記載の画像領域判定方法。
【請求項１０】
前記原画像領域を判定するステップは、前記検査点を前記エッジに沿って走査しながら前記エッジ検出ステップを繰り返すことにより、エッジラインを追跡するステップをさらに含むことを特徴とする請求項９に記載の画像領域判定方法。
【請求項１１】
前記原画像領域を判定するステップは、前記原画像領域の暫定的な頂点付近の画像領域を空間周波数領域に変換した場合の低周波数成分の位相角と、前記暫定的な頂点の位置に前記原画像領域の真の頂点があると仮定した場合の参照画像領域を空間周波数領域に変換した場合の低周波数成分の位相角との差にもとづいて、前記暫定的な頂点の真の位置からのずれを求めるステップを含むことを特徴とする請求項８から１０のいずれかに記載の画像領域判定方法。
【請求項１２】
前記原画像領域を判定するステップは、前記エッジラインの追跡により得られる前記エッジラインの端点を前記原画像領域の暫定的な頂点として、前記暫定的な頂点付近の画像領域を空間周波数領域に変換した場合の低周波数成分の位相角と、前記暫定的な頂点の位置に前記原画像領域の真の頂点があると仮定した場合の参照画像領域を空間周波数領域に変換した場合の低周波数成分の位相角との差にもとづいて、前記暫定的な頂点の真の位置からのずれを求めることを特徴とする請求項１０に記載の画像領域判定方法。
【請求項１３】
電子透かしが埋め込まれた原画像が印刷された印刷媒体の撮影画像を取得するステップと、
前記撮影画像における検査画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定するステップと、
判定された前記原画像領域の撮影による歪みを補正するステップと、
補正された前記原画像領域から前記電子透かしを抽出するステップとをコンピュータに実行させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理技術に関し、特に電子透かしの埋め込まれた印刷画像を撮影した画像の原画像領域を判定する画像領域判定方法、ならびにその方法を利用可能な画像領域判定装置、画像補正装置および電子透かし抽出装置に関する。
【背景技術】
【０００２】
電子透かしが埋め込まれたデジタル画像を印刷媒体に印刷し、印刷された画像をデジタルカメラやスキャナ等で撮影して再度デジタル化して埋め込まれた電子透かしを検出するシステムがある。たとえば、チケットやカードを利用者に発行する際に、発行者や利用者に関する識別情報などを電子透かしとして視覚的に検知できないように画像に埋め込んでチケットやカードに印刷する。チケットやカードの利用時に、その電子透かしを検出することにより、偽造や不正入手などの不正行為を防止することができる。また、複写機やプリンタで画像を印刷する際に、著作権情報や機器の識別番号等を電子透かしとして埋めこんで印刷することにより、著作物、有価証券等の不正コピーを防止することができる。
【０００３】
一般にデジタルカメラやスキャナを用いて印刷画像を撮影してデジタル化すると、撮影画像には、撮影機器のレンズの形状や焦点距離に依存したレンズ歪みや、撮影時の光軸の傾きに起因する透視歪みが生じ、印刷画像と撮影画像の間で画素のずれが現れる。そのため、印刷画像に埋め込まれた電子透かしを撮影画像から正しく抽出することは困難であり、撮影画像の歪み補正が必要となる。
【０００４】
特許文献１には、画像の周囲に基準枠を付加して印刷し、基準枠の付加された印刷画像を撮影して、基準枠をもとに撮影画像の画像領域の大きさを算出し、撮影画像の歪みを補正する技術が開示されている。
【特許文献１】特開２００３−１１０８４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
撮影による画像歪みを補正するためには、まず撮影画像に含まれる原画像領域を正確に抽出する必要がある。原画像領域の画像枠をエッジ抽出処理によって抽出するのが一般的であるが、撮影画像には歪みがある上、撮影状況によってはノイズが含まれるため、高精度でエッジを抽出することは難しい。原画像領域を正確に抽出できなかった場合、画像歪みの補正が正しくなされる保証がなくなる。その結果、原画像領域に埋め込まれた電子透かしの検出に失敗したり、検出精度が落ちるなどの問題が生じる。
【０００６】
特許文献１に開示された技術では、電子透かしの埋め込まれた画像を印刷する際に、画像の周囲に基準枠を付加して印刷する必要があり、手間がかかり、印刷画像の見映えも悪くなる。
【０００７】
本発明はこうした状況に鑑みてなされたもので、その目的は、印刷画像を撮影した画像において原画像領域を簡易な方法で正確に判定することのできる画像領域判定技術を提供することにある。また、別の目的は、その画像領域判定技術を利用して、撮影による画像歪みを補正することのできる画像補正技術、さらには電子透かしの埋め込まれた印刷画像を撮影した画像から電子透かしを高い精度で検出することのできる電子透かし抽出技術を提供することにある。
【課題を解決するための手段】
【０００８】
本発明のある態様は画像領域判定装置に関する。この装置は、原画像が印刷された印刷媒体の撮影画像を取得する画像入力部と、前記撮影画像における検査画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定する画像領域判定部とを含む。前記画像領域判定部は、前記検査画像領域を空間周波数領域に変換した場合の低周波数成分の位相角にもとづいて、前記原画像領域のエッジを検出するエッジ検出部を含んでもよい。前記画像領域判定部は、前記検査画像領域を空間周波数領域に変換した場合の低周波数成分の位相角にもとづいて、前記原画像領域の頂点の位置を特定する頂点特定部を含んでもよい。
【０００９】
空間周波数領域への変換には、たとえばフーリエ変換を用いることができる。印刷媒体を撮影すると、原画像の印刷領域の周辺の余白部分も合わせて撮影されるため、撮影画像から余白部分を取り除いた原画像領域を抽出することが必要になるが、この構成によれば、空間周波数領域における周波数成分を用いて頂点やエッジなどの原画像領域の特徴点を検出するため、撮影画像に含まれるノイズの影響を受けることなく、撮影領域から原画像領域を高精度で抽出することができる。
【００１０】
前記頂点特定部は、前記原画像領域の暫定的な頂点付近の検査画像領域を空間周波数領域に変換した場合の低周波数成分の位相角と、前記暫定的な頂点の位置に前記原画像領域の真の頂点があると仮定した場合の参照画像領域を空間周波数領域に変換した場合の低周波数成分の位相角との差にもとづいて、前記暫定的な頂点の真の位置からのずれを求めてもよい。この暫定的な頂点は、前記エッジ検出部により検出されたエッジの端点であってもよく、何らかの手法でおおまかに求めたものであってもよい。エッジ検出部により検出されるエッジの端点が原画像領域のおおよその頂点の位置を与えるものであっても、頂点特定部はその頂点の位置の精度を改善することができる。
【００１１】
本発明の別の態様は画像補正装置に関する。この装置は、原画像が印刷された印刷媒体の撮影画像を取得する画像入力部と、前記撮影画像における検査画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定する画像領域判定部と、判定された前記原画像領域の撮影による歪みを補正する画像補正部とを含む。
【００１２】
本発明のさらに別の態様は電子透かし抽出装置に関する。この装置は、電子透かしが埋め込まれた原画像が印刷された印刷媒体の撮影画像を取得する画像入力部と、前記撮影画像における検査画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定する画像領域判定部と、判定された前記原画像領域の撮影による歪みを補正する画像補正部と、補正された前記原画像領域から前記電子透かしを抽出する抽出部とを含む。
【００１３】
本発明のさらに別の態様は画像領域判定方法に関する。この方法は、原画像が印刷された印刷媒体の撮影画像を取得するステップと、前記撮影画像における検査点付近の画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定するステップとを含む。
【００１４】
前記原画像領域を判定するステップは、前記検査点付近の画像領域を空間周波数領域に変換した場合の低周波数成分の実軸成分が実質的に零である場合に、前記検査点が前記原画像領域のエッジ上にあると判定するエッジ検出ステップを含んでもよい。「実質的に零である」とは、ノイズの影響を考慮した誤差の範囲で、零に近いことをいう。
【００１５】
前記原画像領域を判定するステップは、前記検査点を前記エッジに沿って走査しながら前記エッジ検出ステップを繰り返すことにより、エッジラインを追跡するステップをさらに含んでもよい。ここで「エッジに沿って走査」とは、エッジに平行に走査するだけではなく、所定の幅でエッジと垂直な方向への走査も組み合わせて走査することも含める。エッジに沿った走査により、エッジラインの端点に到達すると、その端点が原画像領域の頂点の暫定的な位置を与える。
【００１６】
本発明のさらに別の態様はコンピュータプログラムに関する。このプログラムは、電子透かしが埋め込まれた原画像が印刷された印刷媒体の撮影画像を取得するステップと、前記撮影画像における検査画像領域を空間周波数領域に変換した場合の周波数成分の位相にもとづいて、前記撮影画像における原画像領域を判定するステップと、判定された前記原画像領域の撮影による歪みを補正するステップと、補正された前記原画像領域から前記電子透かしを抽出するステップとをコンピュータに実行させる。
【００１７】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１８】
本発明によれば、印刷画像を撮影した画像において原画像領域を高精度で判定することができる。それにより、撮影による歪みを正確に補正することができ、また、電子透かしの埋め込まれた印刷画像を撮影した画像の場合、原画像領域から電子透かしを高い精度で検出することができる。
【発明を実施するための最良の形態】
【００１９】
本発明の実施の形態に係る電子透かしシステムは、図１の電子透かし埋め込み装置１００と図３の電子透かし抽出装置２００とを含み、電子透かし埋め込み装置１００によって電子透かしの埋め込まれた印刷画像が生成され、電子透かし抽出装置２００によって印刷画像を撮影して、埋め込まれた電子透かしが抽出される。電子透かし埋め込み装置１００は、たとえば、チケットやカードの発行に用いられ、電子透かし抽出装置２００は、チケットやカードの偽造を発見するために用いられる。どちらの装置もネットワーク上の端末からアクセスされるサーバとして構成してもよい。
【００２０】
図１は、実施の形態に係る電子透かし埋め込み装置１００の構成図である。これらの構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされた画像処理機能および電子透かし埋め込み機能のあるプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００２１】
画像形成部１０は、入力されたデジタル画像Ｉを印刷時の解像度に変換する。埋め込み部１２は、画像形成部１０によって印刷時の解像度に変換されたデジタル画像Ｉに透かし情報Ｘを埋め込む。
【００２２】
印刷部１４は、埋め込み部１２により透かし情報Ｘが埋め込まれたデジタル画像Ｉを紙やカードなどの印刷媒体に印刷し、印刷画像Ｐを生成する。なお、同図では、印刷部１４は電子透かし埋め込み装置１００の構成要素であるが、印刷部１４を電子透かし埋め込み装置１００の外部に設け、プリンタによって構成してもよく、その場合は、電子透かし埋め込み装置１００とプリンタは、周辺機器の接続ケーブルまたはネットワークで接続される。
【００２３】
図２は、出力された印刷画像Ｐを説明する図である。印刷媒体２４上に電子透かしの埋め込まれたデジタル画像Ｉ（原画像ともいう）が印刷されており、原画像の印刷された領域２０（以下、単に原画像領域２０という）の周囲には通常、印刷媒体２４の余白部分が存在する。
【００２４】
図３は、実施の形態に係る電子透かし抽出装置２００の構成図である。これらの構成も、ＣＰＵ、メモリなどのハードウエア、画像処理機能および電子透かし抽出機能のあるソフトウエアの任意の組み合わせによっていろいろな形で実現することができる。
【００２５】
撮影部３０は、電子透かし埋め込み装置１００により生成された印刷画像Ｐを撮影し、印刷画像Ｐをデジタル化する。同図では、撮影部３０は電子透かし抽出装置２００の構成要素であるが、撮影部３０を電子透かし抽出装置２００の外部に設け、デジタルカメラやスキャナによって構成してもよく、その場合は、電子透かし抽出装置２００と、デジタルカメラまたはスキャナは、周辺機器の接続ケーブルまたはネットワークで接続される。特にデジタルカメラに無線通信機能がある場合は、デジタルカメラで取り込まれた撮影画像が無線で電子透かし抽出装置２００に送信される。
【００２６】
図４は、撮影された印刷画像Ｐを説明する図である。撮影部３０は、印刷画像Ｐを撮影するとき、印刷媒体２４の原画像領域２０全体を撮影するが、通常、原画像領域２０の周囲の余白部分も撮影する。すなわち撮影領域２６は、一般に、印刷媒体２４上で原画像領域２０よりも広い範囲である。このように撮影部３０による撮影画像には、印刷媒体２４の余白部分も含まれているため、原画像領域２０の切り出しが必要となる。
【００２７】
図３の画像領域判定部３２は、撮影部３０により取り込まれた撮影画像に含まれる原画像の領域を判定し、図４の撮影領域２６から余白部分を取り除いた原画像領域２０を抽出する。
【００２８】
図５は、画像領域判定部３２の詳細な構成を説明する図である。エッジ検出部３８は、撮影部３０により撮影された撮影領域２６に含まれる原画像領域２０のエッジを検出し、さらにそのエッジを追跡してエッジの端点を取得する。頂点特定部４０は、エッジ検出部３８が取得したエッジの端点をもとに、原画像領域２０の頂点の位置を特定する。画像領域抽出部４１は、頂点特定部４０により特定された頂点にもとづいて撮影領域２６から原画像領域２０を抽出し、画像補正部３４に与える。
【００２９】
エッジ検出部３８と頂点特定部４０の構成を詳しく説明する。エッジ検出部３８のエッジ検出フィルタ部４２は、撮影領域２６に対してエッジ検出フィルタによるエッジ検出処理を施して、撮影領域２６内の原画像領域２０のエッジを検出し、最初に検出したエッジ上の点を頂点探索開始点Ｖｓとしてエッジ追跡部４４に与える。エッジ追跡部４４は、フーリエ変換処理などにより、頂点探索開始点Ｖｓから原画像領域２０の頂点方向にエッジラインを追跡することで、エッジラインの端点を検出し、その端点を原画像領域２０の暫定頂点Ｖｅとして頂点特定部４０に与える。
【００３０】
頂点特定部４０のフーリエ変換処理部４６は、暫定頂点Ｖｅの周辺の画像にフーリエ変換処理を施す。位相角算出部４７は、フーリエ変換後の低周波数成分の位相角を算出する。頂点位置ずれ調整部４８は、算出された位相角にもとづき、真の頂点位置からの暫定頂点Ｖｅのずれを求め、暫定頂点Ｖｅの位置ずれを調整した最終検出頂点Ｖｆを求め、画像領域抽出部４１に与える。
【００３１】
画像領域抽出部４１は、最終検出頂点Ｖｆの座標値をもとに撮影領域２６から原画像領域２０を抽出し、画像補正部３４に与える。画像領域抽出部４１は、最終検出頂点Ｖｆ以外に、エッジ検出部３８により検出されるエッジも利用して、原画像領域２０を抽出してもよい。
【００３２】
図６は、エッジ検出部３８および頂点特定部４０により原画像領域２０が判定される様子を説明する図である。撮影領域２６は長方形ＥＦＨＧ、原画像領域２０は長方形ＡＢＤＣで図示されている。撮影領域２６の長方形ＥＦＨＧの大きさは、縦ｈｅｉｇｈｔ画素、横ｗｉｄｔｈ画素である。以下では、横方向をｘ軸、縦方向をｙ軸とする座標系を設定する。
【００３３】
エッジ検出部３８のエッジ検出フィルタ部４２は、撮影領域２６の中心Ｏを求め、撮影領域２６の左上の頂点Ｅから中心Ｏに向けて、傾きθのエッジ走査方向５０を定める。エッジ検出フィルタ部４２は、頂点Ｅからエッジ走査方向５０に沿って撮影領域２６を走査し、エッジ検出フィルタなどを用いて、原画像領域２０のエッジを検出する。これにより、エッジ走査方向５０と原画像領域２０の辺ＡＣとの交点Ｉにおいて、最初にエッジが検出される。この交点Ｉが頂点探索開始点Ｖｓである。
【００３４】
その後、エッジ追跡部４４は、左向きに頂点走査方向５２を定め、点Ｉから頂点走査方向５２に沿って撮影領域２６を走査し、フーリエ変換処理などを利用して、原画像領域２０のエッジラインを追跡する。エッジ追跡部４４による頂点走査方向５２に沿ったエッジラインの追跡は、エッジラインの端点が検出された時点で停止する。この端点が暫定頂点Ｖｅである。
【００３５】
さらに、頂点特定部４０は、エッジ追跡部４４により得られた暫定頂点Ｖｅの位置ずれを調整して、原画像領域２０の頂点Ａの座標を最終検出頂点Ｖｆとして求める。
【００３６】
なお、エッジ追跡部４４が頂点Ａを探索する向きは、同図の例では左向きであったが、エッジ走査方向５０が原画像領域２０の辺ＡＢと交わる場合は、頂点Ａを探索する向きは、上向きとなることに留意する。
【００３７】
撮影領域２６の右下の頂点Ｈを走査開始点として、原画像領域２０の右下の頂点Ｄを探索する場合は、エッジ検出フィルタ部４２は、エッジ走査方向５４に沿った走査により、原画像領域２０の辺ＣＤ上の点Ｌにおいて最初にエッジを検出する。エッジ追跡部４４は、下向きに頂点走査方向５６を定め、点Ｌから頂点走査方向５６に沿ってエッジラインを追跡し、辺ＣＤの端点付近で停止し、暫定頂点Ｖｅを取得する。頂点特定部４０は、暫定頂点Ｖｅの位置ずれを調整して、原画像領域２０の頂点Ｄを最終検出頂点Ｖｆとして求める。
【００３８】
ここでも、エッジ追跡部４４が頂点Ｄを探索する向きは、同図の例では下向きであったが、エッジ走査方向５４が原画像領域２０の辺ＢＤと交わる場合は、頂点Ｄを探索する向きは、右向きとなることに留意する。
【００３９】
撮影領域２６の左下の頂点Ｆを走査開始点として、原画像領域２０の左下の頂点Ｂを探索する場合、撮影領域２６の右上の頂点Ｇを走査開始点として、原画像領域２０の右上の頂点Ｃを探索する場合も同様の処理が行われる。
【００４０】
図３の画像補正部３４は、画像領域判定部３２により抽出された原画像領域２０の歪み補正を行う。撮影部３０によって印刷画像Ｐを取り込む際、撮影画像にはレンズ歪みや透視歪みが生じる。画像補正部３４は、埋め込まれた電子透かしを正確に抽出できるように、画像に生じた歪みを補正する。
【００４１】
図７（ａ）、（ｂ）は、原画像領域２０の歪みを説明する図である。図７（ａ）は、撮影による歪みのない理想的な状態の原画像領域２０を示したものであり、矩形ＡＢＤＣは長方形である。図７（ｂ）は、撮影による歪みのある原画像領域２０を示したものである。デジタルカメラで撮影した場合、印刷媒体２４を正確に真上から撮影することは難しく、光軸のずれにより透視歪みが生じる。ここでは透視歪みを強調して矩形ＡＢＤＣを図示しているが、一般にはレンズの歪曲収差により樽型や糸巻き型のレンズ歪みも生じている。画像補正部３４は、図７（ｂ）のような歪みの生じた矩形ＡＢＤＣを４頂点の座標値を用いて幾何変換することにより、図７（ａ）の歪みのない長方形ＡＢＤＣに変形する。
【００４２】
図３の透かし抽出部３６は、画像補正部３４によって歪み補正された原画像領域２０の透かし埋め込み領域から透かしビットを検出することにより、透かし情報Ｘを抽出する。透かしビットを検出する際、埋め込み領域に歪みがあると、透かしの検出が困難になるが、画像補正部３４により歪みが補正されているため、透かしの検出精度が保証される。
【００４３】
以上の構成による電子透かし抽出装置２００による電子透かし抽出手順を説明する。
【００４４】
図８は、電子透かし抽出手順の全体的な流れを示すフローチャートである。撮影部３０は印刷画像Ｐを撮影する（Ｓ１０）。画像領域判定部３２は画像領域判定処理を行い、撮影画像から原画像領域２０を抽出する（Ｓ１２）。画像補正部３４は、原画像領域２０に画像補正処理を施し、撮影による歪みを補正する（Ｓ１４）。透かし抽出部３６は、補正後の原画像領域２０から透かし情報Ｘを検出する処理を行う（Ｓ１６）。
【００４５】
図９は、図８の画像領域判定処理Ｓ１２の大まかな流れを示すフローチャートである。エッジ検出部３８のエッジ検出フィルタ部４２は、撮影領域２６に含まれる原画像領域２０のエッジを検出する処理を行う（Ｓ２０）。エッジ追跡部４４は、原画像領域２０のエッジラインを追跡して、エッジラインの端点を原画像領域２０の暫定頂点Ｖｅとして取得する処理を行う（Ｓ２２）。頂点特定部４０は、暫定頂点Ｖｅをもとに、原画像領域２０の頂点の位置を正確に特定する処理を行う（Ｓ２４）。
【００４６】
図１０は、図９のエッジ検出処理Ｓ２０の詳細な手順を示すフローチャートである。エッジ検出フィルタ部４２は、撮影領域２６のサイズ（ｗｉｄｔｈ，ｈｅｉｇｈｔ）を取得し（Ｓ３０）、撮影領域２６のアスペクト比ｗｉｄｔｈ／ｈｅｉｇｈｔを算出する（Ｓ３２）。また、エッジ検出フィルタの出力値の閾値Ｔを設定する（Ｓ３４）。
【００４７】
エッジ検出フィルタ部４２は、走査開始点の座標（ｉ，ｊ）を設定する（Ｓ３６）。走査開始点は、図５に示す撮影領域２６の４隅Ｅ、Ｆ、Ｇ、Ｈのいずれかに設定される。ここでは、左上の頂点Ｅを走査開始点として設定し、左上の頂点Ａを検出する場合を説明する。ｘ座標値ｉにアスペクト比ｗｉｄｔｈ／ｈｅｉｇｈｔを加算し、ｙ座標値ｊに１を加算することにより、検査点（ｉ，ｊ）を定め、走査開始点から撮影画像の中心に向かう走査方向に沿って探索を進める（Ｓ３８）。
【００４８】
なお、左下の頂点Ｆを走査開始点として設定し、左下の頂点Ｂを検出する場合は、ｘ座標値ｉにアスペクト比ｗｉｄｔｈ／ｈｅｉｇｈｔを加算し、ｙ座標値ｊから１を減算することにより、検査点（ｉ，ｊ）を定める。また、右上の頂点Ｇを走査開始点として設定し、右上の頂点Ｃを検出する場合は、ｘ座標値ｉからアスペクト比ｗｉｄｔｈ／ｈｅｉｇｈｔを減算し、ｙ座標値ｊに１を加算することにより、検査点（ｉ，ｊ）を定める。また、右下の頂点Ｈを走査開始点として設定し、右下の頂点Ｄを検出する場合は、ｘ座標値ｉからアスペクト比ｗｉｄｔｈ／ｈｅｉｇｈｔを減算し、ｙ座標値ｊから１を減算することにより、検査点（ｉ，ｊ）を定める。
【００４９】
エッジ検出フィルタ部４２は、検査点（ｉ，ｊ）を中心とする小領域にエッジ検出フィルタを施し、エッジ検出フィルタによる出力値Ｐを計算する（Ｓ４０）。出力値Ｐが閾値Ｔを超えた場合（Ｓ４２のＹ）、エッジが検出されたと判定し、エッジ方向を特定し（Ｓ４４）、エッジが検出されたときの検査点の座標（ｉ，ｊ）を頂点探索開始点Ｖｓの座標（ｉｓ，ｊｓ）として取得する（Ｓ４６）。出力値Ｐが閾値Ｔを超えない場合（Ｓ４２のＮ）、ステップＳ３８に戻り、検査点の座標値をインクリメントして、さらにエッジ検出フィルタによる走査を続ける。
【００５０】
図１１（ａ）〜（ｄ）は、エッジ検出フィルタを説明する図である。エッジ検出フィルタ部４２は、テンプレート・マッチングの方法を用いたエッジ検出フィルタリングを行う。具体的には、エッジ検出フィルタの一例として、Ｐｒｅｗｉｔｔオペレータを用いて、エッジラインとエッジ方向を検出する。同図には、Ｐｒｅｗｉｔｔオペレータのマスクパターンと、そのマスクパターンにより検出されるエッジパターンが示されている。
【００５１】
図１１（ａ）は、上向きのエッジを検出するためのマスクパターン６０と、そのマスクパターン６０により検出されるエッジパターン６１である。エッジ検出フィルタ部４２は、検査点を中心とする縦横３画素の検査領域にこのマスクパターン６０を適用し、検査領域内の各画素の画素値にマスクパターン６０のマスクの値を乗じて和をとることで、出力値Ｐを計算する。出力値Ｐが閾値Ｔよりも大きい場合、検査点がエッジライン上にあり、同図に示す上向きのエッジパターン６１が検出されたと判定する。ここで、エッジの向きは、エッジラインに垂直であって、画素の暗い方から明るい方に向かう方向、すなわち輝度値の小さい方から輝度値の大きい方に向かう方向に定義されることに注意する。
【００５２】
同様に、図１１（ｂ）は、下向きのエッジを検出するためのマスクパターン６２と、それにより検出されるエッジパターン６３、図１１（ｃ）は、左向きのエッジを検出するためのマスクパターン６４とそれにより検出されるエッジパターン６５、図１１（ｄ）は、右向きのエッジを検出するためのマスクパターン６６とそれにより検出されるエッジパターン６７を示す。
【００５３】
図１０のステップＳ４０〜Ｓ４４では、エッジ検出フィルタ部４２は、検査点（ｉ，ｊ）を中心とする縦横３画素の検査領域に対して、撮影領域２６の左上の隅Ｅから走査を開始する場合は、図１１（ａ）、図１１（ｃ）に示す上向き、左向きのエッジを検出するマスクパターン６０、６４を適用して、それぞれの出力値Ｐを計算し、いずれかのマスクパターンによる出力値Ｐが閾値Ｔを超えた場合に、エッジが検出されたものと判定し、閾値Ｔを超えた方のマスクパターンにより、エッジの方向を特定する。すなわち、エッジが検出された時点で検査点Ｖはエッジライン上にあり、エッジが上向きか左向きかが特定され、このときの検査点Ｖの座標（ｉ，ｊ）が頂点探索開始点Ｖｓの座標（ｉｓ，ｊｓ）となる。
【００５４】
同様に、撮影領域２６の左下の隅Ｆから走査を開始する場合は、エッジ検出フィルタ部４２は、図１１（ｂ）、図１１（ｃ）に示す下向き、左向きのエッジを検出するマスクパターン６２、６４を適用して出力値Ｐを計算する。また、撮影領域２６の右上の隅Ｇから走査を開始する場合は、図１１（ａ）、図１１（ｄ）に示す上向き、右向きのエッジを検出するマスクパターン６０、６６を適用して出力値Ｐを計算する。撮影領域２６の右下の隅Ｈから走査を開始する場合は、図１１（ｂ）、図１１（ｄ）に示す下向き、右向きのエッジを検出するマスクパターン６２、６６を適用して出力値Ｐを計算する。
【００５５】
図１２（ａ）、（ｂ）は、エッジ検出フィルタにより原画像領域２０のエッジが検出される様子を説明する図である。図１２（ａ）では、撮影領域２６の左上の頂点Ｅからエッジ走査方向５０に沿って、上向きのエッジを検出するマスクパターン６０と左向きのエッジを検出するマスクパターン６４とが検査点Ｖを中心とする検査領域に適用され、検査点Ｖが原画像領域２０の上辺に到達したときに、上向きのエッジを検出するマスクパターン６０による出力値Ｐが閾値Ｔを超え、上向きのエッジ方向７０が検出される。このときの検査点Ｖを頂点探索開始点Ｖｓとする。
【００５６】
同様に、図１２（ｂ）では、撮影領域２６の右下の頂点Ｈからエッジ走査方向５４に沿って、下向きのエッジを検出するマスクパターン６２と右向きのエッジを検出するマスクパターン６６とが検査点Ｖを中心とする検査領域に適用され、検査点Ｖが原画像領域２０の右辺に到達したときに、右向きのエッジを検出するマスクパターン６６による出力値Ｐが閾値Ｔを超え、右向きのエッジ方向７２が検出される。このときの検査点Ｖを頂点探索開始点Ｖｓとする。
【００５７】
図１３は、図９のエッジライン追跡処理Ｓ２２の詳細な手順を説明するフローチャートである。エッジ追跡部４４は、図１０のエッジ検出処理Ｓ２０で最終的に得られた頂点探索開始点Ｖｓの座標（ｉｓ，ｊｓ）を検査点Ｖの座標（ｉ，ｊ）に代入する（Ｓ５０）。エッジ検出のために画像領域を走査する幅（以下、単に走査幅という）ｄを所定の値に設定する（Ｓ５１）。図１０のエッジ検出処理Ｓ２０で特定されたエッジ方向が横向きである場合（Ｓ５２のＹ）、縦方向走査処理を行い（Ｓ５４）、エッジ方向が横向きでない場合（Ｓ５２のＮ）、横方向走査処理を行う（Ｓ５６）。縦方向走査処理Ｓ５４または横方向走査処理Ｓ５６により、原画像領域２０のエッジラインが追跡され、エッジラインの端点が暫定頂点Ｖｅの座標（ｉｅ，ｊｅ）として取得される（Ｓ５８）。
【００５８】
図１４は、図１３の縦方向走査処理Ｓ５４の詳細な手順を説明するフローチャートである。この縦方向走査処理Ｓ５４では、エッジ検出部３８が、図１５に示す縦横Ｎ画素の検査領域８０を空間周波数領域に変換したときの低周波数成分の位相角に基づいて、原画像領域２０のエッジを検出する。なお、一例としてＮは１６である。なお、ここでは、左上の頂点Ａを検出する場合を説明する。
【００５９】
ステップＳ６０では、エッジ追跡のスタート位置が設定される。前記頂点探索開始点Ｖｓのｘ座標、ｙ座標をそれぞれ（i，ｊ）としたとき、エッジ追跡のスタート位置である検査点Ｖのｘ座標、ｙ座標はそれぞれ、（i−ｄ／２，ｊ）に設定される。なお、一例として、走査幅ｄは８であり、前記Ｎより小さい値に設定される。なお、図１５において、紙面右側がiの正方向であり、紙面下側がｊの正方向である。
【００６０】
ステップＳ６２では、エッジ追跡部４４により、前記検査点Ｖを中心とする縦横Ｎ画素の検査領域８０にフーリエ変換処理が施される。ここで、検査領域８０の各画素の輝度値をｈ（ｘ、ｙ）とし、検査領域８０にフーリエ変換処理として離散フーリエ変換を行った結果をＨ（ｕ，ｖ）とすると、Ｈ（ｕ，ｖ）は、式（１）のように表現される。
Ｈ（ｕ，ｖ）
＝Σｙ＝０Ｎ-１Σｘ＝０Ｎ-１
｛ｈ'（ｘ，ｙ）ｅｘｐ［−ｉ２π（ｕｘ＋ｖｙ）／Ｎ］｝
ｕ，ｖ＝０，１，２，…，Ｎ−１  （１）
但し、
ｈ'（ｘ，ｙ）＝ｈ（ｘ−ｉ＋（Ｎ＋ｄ）／２，ｙ−ｊ＋Ｎ／２）
なお、式（１）において、指数関数ｅｘｐ［］の中で用いられるｉは虚数単位であり、ｘ座標値を表すｉとは区別される。
【００６１】
ステップＳ６４では、エッジ追跡部４４により、検査領域８０のフーリエ変換の水平方向の交流成分における最低周波数成分（以下、最低水平周波数成分という）の実数成分、即ち、Ｈ（１，０）の実数成分Ｈｒ（１，０）が取得される。
【００６２】
ここで、式（１）は、次のように変形することができる。
Ｈ（ｕ，ｖ）
＝Σｙ＝０Ｎ−１｛ｅｘｐ［−ｉ２πｖｙ／Ｎ］｝
×Σｘ＝０Ｎ−１｛ｈ'（ｘ，ｙ）ｅｘｐ［−ｉ２πｕｘ／Ｎ］｝  （２）
【００６３】
したがって、Ｈ（１，０）は、
Ｈ（１，０）
＝Σｙ＝０Ｎ−１Σｘ＝０Ｎ−１｛ｈ'（ｘ，ｙ）ｅｘｐ［−ｉ２πｘ／Ｎ］｝  （３）
となる。ところで、ｈ（ｘ，ｙ）が複素数である場合、
ｈ（ｘ，ｙ）＝ｈｒ（ｘ，ｙ）＋ｉｈｉ（ｘ，ｙ）  （４）
と表現することができる。したがって、ｈ（ｘ，ｙ）ｅｘｐ［−ｉ２πｘ／Ｎ］は、次式のように変形できる。
ｈ（ｘ，ｙ）ｅｘｐ［−ｉ２πｘ／Ｎ］
＝ｈ（ｘ、ｙ）｛ｃｏｓ［２πｘ／Ｎ］−ｉｓｉｎ［２πｘ／Ｎ］｝
＝ｈｒ（ｘ，ｙ）｛ｃｏｓ［２πｘ／Ｎ］−ｉｓｉｎ［２πｘ／Ｎ］｝
＋ｈｉ（ｘ，ｙ）｛ｓｉｎ［２πｘ／Ｎ］−ｉｃｏｓ［２πｘ／Ｎ］｝  （５）
【００６４】
ここで、検査領域８０の各画素の輝度値ｈ（ｘ、ｙ）の虚数成分は０であるとすると、
ｈ（ｘ，ｙ）ｅｘｐ［−ｉ２πｘ／Ｎ］
＝ｈｒ（ｘ，ｙ）｛ｃｏｓ［２πｘ／Ｎ］−ｉｓｉｎ［２πｘ／Ｎ］｝  （６）
となる。ゆえに、Ｈ（１，０）は、
Ｈ（１，０）＝Σｙ＝０Ｎ−１Σｘ＝０Ｎ−１
｛ｈｒ'（ｘ，ｙ）（ｃｏｓ［２πｘ／Ｎ］−ｉｓｉｎ［２πｘ／Ｎ］）｝  （７）
但し、
ｈｒ'（ｘ，ｙ）＝ｈｒ（ｘ−ｉ＋（Ｎ＋ｄ）／２，ｙ−ｊ＋Ｎ／２）
となる。
【００６５】
また、Ｈ（１，０）の実数成分Ｈｒ（１，０）、虚数成分Ｈｉ（１，０）はそれぞれ、
Ｈｒ（１，０）
＝Σｙ＝０Ｎ−１Σｘ＝０Ｎ−１ｈｒ'（ｘ，ｙ）ｃｏｓ［２πｘ／Ｎ］  （８ｒ）
Ｈｉ（１，０）
＝−Σｙ＝０Ｎ−１Σｘ＝０Ｎ−１ｈｒ'（ｘ，ｙ）ｓｉｎ［２πｘ／Ｎ］  （８ｉ）
となる。
【００６６】
上記Ｈ（１，０）の値は、検査領域８０における輝度値ｈ（ｘ、ｙ）の分布によって異なる。以下３つの例（Ａ）、（Ｂ）、（Ｃ）を挙げて説明する。
【００６７】
（Ａ）ｈ（ｘ，ｙ）が一様分布のとき
即ち、
ｈ（ｘ，ｙ）＝ｍ      （９）
但し、ｉ−Ｎ／２≦ｘ≦ｉ＋Ｎ／２―１  かつ、
ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１
である場合、
Ｈｒ（１，０）
＝ｍΣｙ＝０Ｎ−１Σｘ＝０Ｎ−１ｃｏｓ［２πｘ／Ｎ］
Ｈｉ（１，０）
＝−ｍΣｙ＝０Ｎ−１Σｘ＝０Ｎ−１ｓｉｎ［２πｘ／Ｎ］
となるが、ここで、
Σｘ＝０Ｎ−１ｃｏｓ［２πｘ／Ｎ］＝０
Σｘ＝０Ｎ−１ｓｉｎ［２πｘ／Ｎ］＝０
であるから、
Ｈｒ（１，０）＝Ｈｉ（１，０）＝０  
となり、Ｈ（１，０）の実数成分Ｈｒ（１，０）、虚数成分Ｈｉ（１，０）は、ともに０になる。
【００６８】
（Ｂ）検査領域８０の中央の検査点Ｖに原画像領域２０と余白領域のエッジがある場合、例えば、
ｈ（ｘ，ｙ）
＝ｍ１  （ｉ−Ｎ／２≦ｘ≦ｉ−１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１）；
ｍ２  （ｉ≦ｘ＜ｉ＋Ｎ／２―１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１）  （１０）
（但し、ｍ１：余白領域の輝度、ｍ２：原画像領域２０の輝度であり、ｍ１＜ｍ２）
のとき、
Ｈｒ（１，０）
＝Σｙ＝０Ｎ−１Σｘ＝０Ｎ／２−１ｍ１ｃｏｓ［２πｘ／Ｎ］
＋Σｙ＝０Ｎ−１Σｘ＝Ｎ／２Ｎ−１ｍ２ｃｏｓ［２πｘ／Ｎ］  （１１ｒ）
Ｈｉ（１，０）
＝−Σｙ＝０Ｎ−１Σｘ＝０Ｎ／２−１ｍ１ｓｉｎ［２πｘ／Ｎ］
−Σｙ＝０Ｎ−１Σｘ＝Ｎ／２Ｎ−１ｍ２ｓｉｎ［２πｘ／Ｎ］  （１１ｉ）
【００６９】
ここで、
Σｘ＝０Ｎ／２−１ｃｏｓ［２πｘ／Ｎ］＝Σｘ＝Ｎ／２Ｎ−１ｃｏｓ［２πｘ／Ｎ］＝０
であるから、
Ｈｒ（１，０）＝０
Ｈｉ（１，０）
＝−Ｎ×（ｍ１Σｘ＝０Ｎ／２−１ｓｉｎ［２πｘ／Ｎ］
＋ｍ２Σｘ＝Ｎ／２Ｎ−１ｓｉｎ［２πｘ／Ｎ］）
となり、Ｈ（１，０）の実数成分Ｈｒ（１，０）は０となるが、虚数成分Ｈｉ（１，０）は０にはならない。
【００７０】
（Ｃ）検査領域８０の中央の検査点Ｖではないところに原画像領域２０と余白領域のエッジがある場合、例えば、
ｈ（ｘ、ｙ）
＝ｍ１  （０≦ｘ≦Ｎ／４−１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１）；
ｍ２  （Ｎ／４≦ｘ＜Ｎ−１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１）  （１２）
（但しｍ１≠ｍ２）
である場合、
Ｈｒ（１，０）
＝Σｙ＝０Ｎ−１Σｘ＝０Ｎ／４−１ｍ１ｃｏｓ［２πｘ／Ｎ］
＋Σｙ＝０Ｎ−１Σｘ＝Ｎ／４Ｎ−１ｍ２ｃｏｓ［２πｘ／Ｎ］
Ｈｉ（１，０）
＝−Σｙ＝０Ｎ−１Σｘ＝０Ｎ／４−１ｍ１ｓｉｎ［２πｘ／Ｎ］
−Σｙ＝０Ｎ−１Σｘ＝Ｎ／４Ｎ−１ｍ２ｓｉｎ［２πｘ／Ｎ］
となり、Ｈ（１，０）の実数成分Ｈｒ（１，０）及び虚数成分Ｈｉ（１，０）は０にはならない。
【００７１】
ステップＳ６６では、前記Ｈ（１，０）が０であるかどうかが評価される。Ｈ（１，０）の実数成分Ｈｒ（１，０）が０でなければ、上記（Ｂ）の説明から、前記検査点Ｖ（ｉ，ｊ）は、原画像領域２０と余白領域のエッジ上にはないものとみなされる。そして、ステップＳ６８へ進み、検査点Ｖのｘ座標値ｉが１だけインクリメントされ、検査点Ｖがｘ軸方向に移動される。そして、ステップＳ６２では、新しい検査点Ｖを中心とする縦横Ｎ画素の検査領域８０にフーリエ変換処理が施される。
【００７２】
上記ステップＳ６６において、Ｈ（１，０）の実数成分Ｈｒ（１，０）が０であれば、前記検査点Ｖ（ｉ，ｊ）は、原画像領域２０と余白領域のエッジ上にあるものとみなされ、その検査点Ｖにおいてエッジが検出されたと判定される。
【００７３】
なお、図１４において、Ｈ１，０は上記Ｈｒ（１，０）のことを、Ｈ０，１はＨｒ（０，１）のことを意味している。また、以後の文中で登場するＨ１，０及びＨ０，１も同様のことを意味する。また、以後の文中で登場するフーリエ変換の（１，０）成分、フーリエ変換の（０，１）成分はそれぞれＨ（１，０）、Ｈ（０，１）のことを指すものとする。
【００７４】
エッジが検出されると、ステップＳ７０では、検査領域８０のフーリエ変換の垂直方向の交流成分における最低周波数成分（以下、最低垂直周波数成分という）の実数成分、即ちＨ（０，１）の実数成分Ｈｒ（０，１）が取得され、記憶される。ここで、ステップＳ７０では、新しく得られた実数成分Ｈｒ（０，１）が次回のステップＳ７０の実行時まで一時的にメモリに記憶され、後述のようにステップＳ７１でその内容が読み出され、ステップＳ７２で実数成分Ｈｒ（０，１）の変化量の計算に利用される。
【００７５】
式（８ｒ）の導出と同様の方法により、Ｈｒ（０，１）、Ｈｉ（０，１）は、
Ｈｒ（０，１）
＝Σｘ＝０Ｎ−１Σｙ＝０Ｎ−１ｈｒ'（ｘ，ｙ）ｃｏｓ［２πｙ／Ｎ］  （１３ｒ）
Ｈｉ（０，１）
＝−Σｘ＝０Ｎ−１Σｙ＝０Ｎ−１ｈｒ'（ｘ，ｙ）ｓｉｎ［２πｙ／Ｎ］  （１３ｉ）
となる。上記Ｈｒ（０，１）、Ｈｉ（０，１）の値も、検査領域８０における輝度値ｈ（ｘ，ｙ）の分布によって異なる。以下３つの例（Ｄ）、（Ｅ）、（Ｆ）の例を挙げて説明する。
【００７６】
（Ｄ）検査領域８０の中央の検査点Ｖに原画像領域２０と余白領域のエッジがあるが、検査領域８０内に原画像領域２０の頂点がない場合、例えば、
ｈ（ｘ、ｙ）
＝ｍ１  （ｉ−Ｎ／２≦ｘ≦ｉ−１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１）；
ｍ２  （ｉ≦ｘ＜ｉ＋Ｎ／２―１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１）  （１４）
のとき、
Ｈｒ（０，１）
＝Σｘ＝０Ｎ／２−１ｍ１Σｙ＝０Ｎ−１ｃｏｓ［２πｙ／Ｎ］
＋Σｘ＝Ｎ／２Ｎ−１ｍ２Σｙ＝０Ｎ−１ｃｏｓ［２πｙ／Ｎ］  （１５ｒ）
Ｈｉ（０，１）
＝−Σｘ＝０Ｎ／２−１ｍ１Σｙ＝０Ｎ−１ｓｉｎ［２πｙ／Ｎ］
−Σｘ＝Ｎ／２Ｎ−１ｍ２Σｙ＝０Ｎ−１ｓｉｎ［２πｙ／Ｎ］  （１５ｉ）
となる。
【００７７】
ここで、
Σｙ＝０Ｎ−１ｃｏｓ［２πｙ／Ｎ］＝Σｙ＝０Ｎ−１ｓｉｎ［２πｙ／Ｎ］＝０
であるから、
Ｈｒ（０，１）＝Ｈｉ（０，１）＝０
となる。
【００７８】
（Ｅ）検査領域８０内に原画像領域２０の頂点がある場合（但し、検査点Ｖと頂点は一致しないものとする）、例えば、
ｈ（ｘ、ｙ）
＝ｍ１  （ｉ−Ｎ／２≦ｘ≦ｉ−１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１）；
ｍ１  （ｉ≦ｘ＜ｉ＋Ｎ／２―１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／４−１）；
ｍ２  （ｉ≦ｘ＜ｉ＋Ｎ／２―１、ｊ＋Ｎ／４≦ｙ≦ｊ＋Ｎ／２―１）  （１６）
のとき、
Ｈｒ（０，１）  
＝Σｘ＝０Ｎ／２−１ｍ１Σｙ＝０Ｎ−１ｃｏｓ［２πｙ／Ｎ］
＋Σｘ＝Ｎ／２Ｎ−１ｍ１Σｙ＝０３Ｎ／４−１ｃｏｓ［２πｙ／Ｎ］
＋Σｘ＝Ｎ／２Ｎ−１ｍ２Σｙ＝３Ｎ／４Ｎ−１ｃｏｓ［２πｙ／Ｎ］  （１７ｒ）
Ｈｉ（０，１）
＝−Σｘ＝０Ｎ／２−１ｍ１Σｙ＝０Ｎ−１ｓｉｎ［２πｙ／Ｎ］
−Σｘ＝Ｎ／２Ｎ−１ｍ１Σｙ＝０３Ｎ／４−１ｓｉｎ［２πｙ／Ｎ］
−Σｘ＝Ｎ／２Ｎ−１ｍ２Σｙ＝３Ｎ／４Ｎ−１ｓｉｎ［２πｙ／Ｎ］  （１７ｉ）
となる。
【００７９】
ここで、
Σｙ＝０Ｎ−１ｃｏｓ［２πｙ／Ｎ］＝Σｙ＝０Ｎ−１ｓｉｎ［２πｙ／Ｎ］＝０
であるから、
Ｈｒ（０，１）  
＝Σｘ＝Ｎ／２Ｎ−１ｍ１Σｙ＝０３Ｎ／４−１ｃｏｓ［２πｙ／Ｎ］
＋Σｘ＝Ｎ／２Ｎ−１ｍ２Σｙ＝３Ｎ／４Ｎ−１ｃｏｓ［２πｙ／Ｎ］
＝Ｎ／２×（ｍ１Σｙ＝０３Ｎ／４−１ｃｏｓ［２πｙ／Ｎ］
＋ｍ２Σｙ＝３Ｎ／４Ｎ−１ｃｏｓ［２πｙ／Ｎ］）  （１８ｒ）
Ｈｉ（０，１）  
＝−Σｘ＝Ｎ／２Ｎ−１ｍ１Σｙ＝０３Ｎ／４−１ｓｉｎ［２πｙ／Ｎ］
−Σｘ＝Ｎ／２Ｎ−１ｍ２Σｙ＝３Ｎ／４Ｎ−１ｓｉｎ［２πｙ／Ｎ］  
＝−Ｎ／２×（ｍ１Σｙ＝０３Ｎ／４−１ｓｉｎ［２πｙ／Ｎ］
＋ｍ２Σｙ＝３Ｎ／４Ｎ−１ｓｉｎ［２πｙ／Ｎ］）  （１８ｉ）
となり、Ｈ（０，１）の実数成分Ｈｒ（０，１）及び虚数成分Ｈｉ（０，１）は０にならない。
【００８０】
（Ｆ）検査点Ｖと頂点が一致した場合、即ち、
ｈ（ｘ、ｙ）
＝ｍ１  （ｉ−Ｎ／２≦ｘ≦ｉ−１、ｊ−Ｎ／２≦ｙ≦ｊ＋Ｎ／２―１）；
ｍ１  （ｉ≦ｘ＜ｉ＋Ｎ／２―１、ｊ−Ｎ／２≦ｙ≦ｊ−１）；
ｍ２  （ｉ≦ｘ＜ｉ＋Ｎ／２―１、ｊ≦ｙ≦ｊ＋Ｎ／２―１）  （１９）
のとき、
Ｈｒ（０，１）  
＝Σｘ＝０Ｎ／２−１ｍ１Σｙ＝０Ｎ−１ｃｏｓ［２πｙ／Ｎ］
＋Σｘ＝Ｎ／２Ｎ−１ｍ１Σｙ＝０Ｎ／２−１ｃｏｓ［２πｙ／Ｎ］
＋Σｘ＝Ｎ／２Ｎ−１ｍ２Σｙ＝Ｎ／２Ｎ−１ｃｏｓ［２πｙ／Ｎ］  （２０ｒ）
Ｈｉ（０，１）
＝−Σｘ＝０Ｎ／２−１ｍ１Σｙ＝０Ｎ−１ｓｉｎ［２πｙ／Ｎ］
−Σｘ＝Ｎ／２Ｎ−１ｍ１Σｙ＝０Ｎ／２−１ｓｉｎ［２πｙ／Ｎ］
−Σｘ＝Ｎ／２Ｎ−１ｍ２Σｙ＝Ｎ／２Ｎ−１ｓｉｎ［２πｙ／Ｎ］  （２０ｉ）
となる。
【００８１】
ここで、
Σｙ＝０Ｎ−１ｃｏｓ［２πｙ／Ｎ］
＝Σｙ＝０Ｎ／２−１ｃｏｓ［２πｙ／Ｎ］＝Σｙ＝Ｎ／２Ｎ−１ｃｏｓ［２πｙ／Ｎ］
＝０であり、
Σｙ＝０Ｎ−１ｓｉｎ［２πｙ／Ｎ］＝０
であるから、
Ｈｒ（０，１）＝０、
Ｈｉ（０，１）
＝−Ｎｍ１／２Σｙ＝０Ｎ／２−１ｓｉｎ［２πｙ／Ｎ］
＝−Ｎｍ２／２Σｙ＝Ｎ／２Ｎ−１ｓｉｎ［２πｙ／Ｎ］
となる。Ｈ（０，１）のうち、実数成分Ｈｒ（０，１）は０となる。
【００８２】
ステップＳ７１では、前回のステップＳ７０の実行時に記憶したＨｒ（０，１）がメモリから読み出される。ステップＳ７２では、ステップＳ７０において今回新しく取得されたＨｒ（０，１）とメモリに記憶されていた前回のＨｒ（０，１）とを比較し、その変化量が所定の閾値よりも大きいかどうかが評価される。ここで、Ｈｒ（０，１）が０でない場合は、上記（Ｅ）の場合に該当する。すなわち、検査領域８０内に原画像領域２０の頂点があるということである。ただし、頂点が検査領域８０の端付近にある場合は、Ｈｒ（０，１）の値は０にはならないものの、大きな値をとることはない。検査点を垂直方向にずらしていくにつれ、原画像領域２０の頂点は検査領域８０の中央部に近づいていくが、これに伴って、Ｈｒ（０，１）は徐々に大きくなっていく。したがって、Ｈｒ（０，１）の変化量が所定の閾値より大きい場合は、原画像領域２０の頂点は検査領域８０の中央部に近づいてきたものとみなし、ステップＳ５４の一連の処理は終了する。
【００８３】
一方、ステップＳ７２においてＨｒ（０，１）の変化量が所定の閾値以下であると判断された場合は、ステップＳ７４へ進む。ステップＳ７４では、ｊが１だけデクリメントされる。即ち、検査点Ｖは、左上の頂点Ａを探索するために、図１５の紙面上側に移動する。そして、ステップＳ６０以降の処理が繰り返される。
【００８４】
図１５は、左上の頂点Ａを探索する場合における縦方向走査処理Ｓ５４が行われる様子を説明する図である。図１０のエッジ検出処理Ｓ２０で最終的に得られた頂点探索開始点Ｖｓ（ｉ，ｊ）を中心として、エッジ検出処理Ｓ２０で特定されたエッジ方向７４にｄ画素の幅をもつ走査幅７６が設定される。頂点探索開始点Ｖｓ（ｉ，ｊ）をエッジ方向７４にｄ／２画素だけずらすことにより、縦方向走査処理Ｓ５４の走査のスタート位置である検査点Ｖ（ｉ−ｄ／２，ｊ）が設定される。エッジ検出部３８は、この検査点Ｖにおいて縦横Ｎ画素からなる検査領域８０を設定し、検査領域８０の画素値をフーリエ変換する。画素数Ｎはたとえば１６に設定される。
【００８５】
エッジ検出部３８は、検査領域８０を検出されたエッジ方向７４と平行な走査方向７８に１画素ずつシフトさせながらフーリエ変換処理を行い、最低水平周波数成分の実軸成分Ｈ１，０の値が０になることにより、検査点Ｖが原画像領域２０のエッジライン上に到達したことを検出する。検査点Ｖがエッジライン上に到達すると、エッジ方向とは垂直な走査方向７９に沿って、検査領域８０を上向きに１画素だけシフトさせ、同じようにｄ／２だけ検査領域８０をずらした位置をスタート位置として、エッジ方向と並行な走査方向７８にエッジ検出を続ける。これが、ステップＳ６０〜Ｓ６８の走査処理である。
【００８６】
なお、検査領域８０を横向き、上向きにシフトさせる量が、１画素でなくてもよく、２画素以上Ｎ画素以下であってもよい。また、二分探索法を用いて走査範囲を絞り込みながら、走査を行ってもよい。
【００８７】
なお、図１４と図１５では、左上の頂点Ａを縦方向に探索して検出する場合を説明した。左下の頂点Ｂを検出する場合は、ステップＳ７４において、検査点Ｖのｙ座標値ｊが１だけインクリメントされるように変更する。また、右上の頂点Ｃを検出する場合は、ステップＳ６０において、検査点Ｖのｘ座標値ｉがi＋ｄ／２に設定され、ステップＳ６８において、検査点Ｖのｘ座標値ｉが１だけデクリメントされるように変更する。また、右下の頂点Ｄを検出する場合は、ステップＳ６０において、検査点Ｖのｘ座標ｉがi＋ｄ／２に設定され、ステップＳ６８において、検査点Ｖのｘ座標値ｉが１だけデクリメントされ、ステップＳ７４において、検査点Ｖのｙ座標値ｊが１だけインクリメントされるように変更する。
【００８８】
ところで、輝度値分布がｈ'（ｘ，ｙ）である縦横Ｎ画素の検査領域８０の座標をｘ方向（水平方向）にｋだけシフトさせたｈ'（ｘ−ｋ，ｙ）のフーリエ変換を求めると、次のようになる。
Ｆ｛ｈ'（ｘ−ｋ，ｙ）｝
＝Σｙ＝０Ｎ-１Σｘ＝０Ｎ-１
｛ｈ'（ｘ−ｋ，ｙ）ｅｘｐ［−ｉ２π（ｕｘ＋ｕｋ＋ｖｙ）／Ｎ］｝
＝ｅｘｐ（−ｉ２πｕｋ／Ｎ）Ｈ（ｕ，ｖ）  （２１）
【００８９】
式（２１）は、輝度値分布がｋ画素分だけｘ方向（水平方向）にシフトすると、フーリエ変換後の信号空間においては、信号の位相角が２πｕｋ／Ｎだけシフトすることを意味する。逆にいえば、フーリエ変換後の信号の位相角のシフト量２πｕｋ／Ｎを角周波数ω＝２πｕ／Ｎで除算することにより、原信号のシフト量を求めることができる。
【００９０】
なお、上記ステップＳ６６では、検査点Ｖを中心としたフーリエ変換の実数成分Ｈ１，０が０である場合にエッジが検出されたものと判定したが、これに代えて、前記実数成分Ｈ１，０が所定の値以下である場合にエッジが検出されたものと判定するものであっても良い。これにより、原画像領域２０及び余白部分の輝度値が均一でない場合、たとえばノイズに起因し、場所によってばらついている場合でも、エッジ位置を正しく検出することができる。あるいは、実数成分Ｈ１，０の絶対値が最小となるような前記検査点Ｖがエッジ位置であるとみなすものであっても良い。
【００９１】
図１６（ａ）〜（ｄ）は、検査領域８０のフーリエ変換の最低水平周波数成分により横方向のエッジが判定される原理を説明する図である。図１６（ａ）のように、検査領域８０の中心点Ｖがちょうど原画像領域２０のエッジライン上に存在するとき、フーリエ変換の最低水平周波数成分である（１，０）成分は、図１６（ｄ）に示す実数部を実軸Ｒｅ、虚数部を虚軸Ｉｍにとった座標系の単位円上で、実軸成分が０の虚軸Ｉｍ上のベクトル９０で表される。
【００９２】
一方、図１６（ｂ）のように、検査領域８０の中心点Ｖが原画像領域２０の横方向のエッジラインからｋ画素だけ左にずれているときは、フーリエ変換の最低水平周波数成分である（１，０）成分は、図１６（ｄ）に示すように、Ｉｍ軸に対して位相角が−ωｋをなすベクトル９２で表され、このときの実軸成分Ｈ１，０は負である。また、図１６（ｃ）のように、検査領域８０の中心点Ｖが原画像領域２０の横方向のエッジラインからｋ画素だけ右にずれているときは、フーリエ変換の最低水平周波数成分である（１，０）成分は、図１６（ｄ）に示すように、Ｉｍ軸に対して位相角がωｋをなすベクトル９１で表され、このときの実軸成分Ｈ１，０は正である。
【００９３】
したがって、フーリエ変換の（１，０）成分の実軸成分Ｈ１，０の値が０であれば、そのときの検査領域８０の中心点Ｖがエッジライン上にあると判定でき、（１，０）成分の実軸成分Ｈ１，０の値が０でなければ、中心点Ｖがエッジラインからずれていると判定できる。この性質に基づき、図１４のステップＳ６６では、実軸成分Ｈ１，０の値が０であるかどうかでエッジ検出を判定している。なお、実際の検出においては、ノイズによる影響があるため、実軸成分Ｈ１，０の値が正確に０でなくても、０に近い場合に、エッジ検出の判定を行ってよい。
【００９４】
エッジ検出の判定精度を高めるため、最低周波数成分（１，０）だけでなく、２番目の低周波数成分（２，０）についても実軸成分Ｈ２，０が０であるかどうかを合わせて評価してもよい。さらに高周波の成分を用いてもよいが、高周波になるほどノイズの影響を受けやすいことに注意する。
【００９５】
ここで、フーリエ変換の最低周波数成分（１，０）における角周波数ωは、検査領域８０の画素数Ｎを用いて、ω＝２π／Ｎと表されることから、位置ずれｋが画素数Ｎの半分である場合の位相角はωｋ＝（２π／Ｎ）×（Ｎ／２）＝πであり、このときの最低周波数成分（１，０）は、虚軸Ｉｍ上の負の向きのベクトル９３となる。このときが位置ずれｋの検出限界となるから、最低周波数成分（１，０）の位相角ωｋによって検出可能な位置ずれｋの範囲は−Ｎ／２≦ｋ＜Ｎ／２である。
【００９６】
また、２番目の低周波数成分（２，０）における角周波数ωは、ω＝４π／Ｎであり、一般にフーリエ変換の周波数成分（ｉ，０）における角周波数ωは、ω＝（２π／Ｎ）×ｉであるから、２番目の低周波数成分（２，０）をエッジ検出に用いた場合、検出可能な位置ずれｋの範囲は、−Ｎ／４≦ｋ＜Ｎ／４に狭まる。一般に周波数成分（ｉ，０）を用いた場合、検出可能な位置ずれｋの範囲は、−Ｎ／（２ｉ）≦ｋ＜Ｎ／（２ｉ）に狭まる。
【００９７】
図１６（ａ）〜（ｄ）では、検査領域８０のフーリエ変換の最低水平周波数成分すなわち（１，０）成分の実軸成分Ｈ１，０により横方向のエッジの検出が可能であることを説明したが、同様に、検査領域８０のフーリエ変換の最低垂直周波数成分すなわち（０，１）成分の実軸成分Ｈ０，１により縦方向のエッジの検出が可能である。
【００９８】
図１７は、図１４のステップＳ７２の縦方向走査の停止条件を説明する図である。検査領域８０を縦方向に１画素ずつシフトして縦方向の走査を続け、同図のように、検査領域８０内に原画像領域２０の頂点Ａが入ったとする。このとき検査領域の中心点（検査点）Ｖは、原画像領域２０のエッジライン上にあるが、原画像領域２０の頂点Ａからずれている。
【００９９】
このとき、検査領域８０の中心点Ｖが原画像領域２０の上辺のエッジラインからずれているために、検査領域８０のフーリエ変換の低周波垂直成分すなわち（０，１）成分の実軸成分Ｈ０，１の値は非零である。縦方向走査により、検査領域８０内に原画像領域２０の頂点Ａが入ることにより、（０，１）成分の実軸成分Ｈ０，１の値に変化が生じるため、この変化をとらえて、縦方向走査を終了する。ステップＳ７２では（０，１）成分の実軸成分Ｈ０，１の変化量と所定の閾値の大小関係にもとづいて停止の判定を行ったが、これに代えて、実軸成分Ｈ０，１と所定の閾値の大小関係にもとづいて停止の判定を行ってもよい。この場合、図１４のステップＳ７１の処理は不要である。縦方向走査の停止時点での検査点Ｖをエッジラインの端点とみなし、検査点Ｖの座標値を暫定頂点Ｖｅの座標値として取得する。
【０１００】
図１８は、図１３の横方向走査処理Ｓ５６の詳細な手順を説明するフローチャートである。横方向走査処理Ｓ５６は、図１４の縦方向走査処理Ｓ５４と走査方向が異なるだけで、処理としては同じである。なお、ここでは、左上の頂点Ａを検出場合を説明する。
【０１０１】
エッジ追跡部４４は、検査点Ｖのｙ座標値を示す変数ｊから走査幅ｄの１／２を減算することにより、検査点Ｖのスタート位置を設定する（Ｓ８０）。エッジ追跡部４４は、検査点Ｖ（ｉ，ｊ）を中心とする縦横Ｎ画素の検査領域にフーリエ変換処理を施す（Ｓ８２）。エッジ追跡部４４は、検査領域のフーリエ変換の（０，１）成分の実軸成分Ｈ０，１を取得し（Ｓ８４）、実軸成分Ｈ０，１が０でない場合（Ｓ８６のＮ）、ｙ座標値ｊを１だけインクリメントして、検査点Ｖをｙ軸方向に移動させ（Ｓ８８）、新しい検査点Ｖについてフーリエ変換処理Ｓ８２を続ける。
【０１０２】
実軸成分Ｈ０，１が０である場合（Ｓ８６のＹ）、その検査点Ｖにおいてエッジが検出されたと判定し、次にフーリエ変換の（１，０）成分の実軸成分Ｈ１，０を取得し（Ｓ９０）、実軸成分Ｈ１，０を閾値と比較して、横方向走査の停止条件の成否を調べる（Ｓ９２）。停止条件が成立する、すなわち実軸成分Ｈ１，０が閾値よりも大きい場合（Ｓ９２のＹ）、横方向走査処理を終了してリターンする。停止条件が成立しない、すなわち実軸成分Ｈ１，０が閾値以下である場合（Ｓ９２のＮ）、検査点Ｖのｘ座標値ｉを１だけデクリメントして、左上の頂点Ａを探索するために、左向きに検査点Ｖを移動させ（Ｓ９４）、ステップＳ８０以降の処理を繰り返す。
【０１０３】
なお、図１８では、左上の頂点Ａを横方向に探索して検出する場合を説明した。左下の頂点Ｂを検出する場合は、ステップＳ８０において、検査点Ｖのｙ座標値ｊがｊ＋ｄ／２に設定され、ステップＳ８８において、検査点Ｖのｙ座標値ｊが１だけデクリメントされるように変更する。また、右上の頂点Ｃを検出する場合は、ステップＳ９４において、検査点Ｖのｘ座標値ｉが１だけインクリメントされるように変更する。また、右下の頂点Ｄを検出する場合は、ステップＳ８０において、検査点Ｖのｙ座標ｊがｊ＋ｄ／２に設定され、ステップＳ８８において、検査点Ｖのｙ座標値ｊが１だけデクリメントされ、ステップＳ９４において、検査点Ｖのｘ座標値ｉが１だけインクリメントされるように変更する。
【０１０４】
図１４の縦方向走査処理Ｓ５４および図１８の横方向走査処理Ｓ５６では、検査点を１画素ずつシフトさせて、その都度、検査領域に対するフーリエ変換を求めた。しかしながら、図１６（ａ）〜（ｄ）で説明したように、検査領域８０の中心点Ｖとエッジラインとのずれｋが、フーリエ変換後の空間では、虚軸Ｉｍとなす位相角ωｋとして現れることを利用すれば、位相角ωｋを角周波数ωで除算することにより、位置ずれｋを求めることができる。したがって、検査領域８０内にエッジラインが入った時点でのフーリエ変換処理の結果から、検査領域８０の中心点Ｖとエッジラインのずれｋを算出して、その後の検査領域８０の走査とフーリエ変換処理を省略して、エッジラインの位置を求めてもよい。この方法によれば、フーリエ変換処理の回数を減らすことができる。
【０１０５】
図１９は、図９の頂点位置特定処理Ｓ２４の詳細な手順を説明するフローチャートである。この処理において、頂点特定部４０のフーリエ変換処理部４６および位相角算出部４７は、暫定頂点Ｖｅの位置ずれ検出処理を行い、真の頂点の位置に対する暫定頂点Ｖｅのｘ軸方向のずれｄｉｆｆ＿ｘとｙ軸方向のずれｄｉｆｆ＿ｙとを求める。
【０１０６】
図２０（ａ）、（ｂ）は、暫定頂点Ｖｅの位置ずれを説明する図である。図２０（ａ）は、縦方向走査処理Ｓ５４または横方向走査処理Ｓ５６の走査が終わった時点での検査領域８０と原画像領域２０の関係を示す。検査領域８０の中心点すなわち暫定頂点Ｖｅ（ｉｅ，ｊｅ）は、原画像領域２０の真の頂点Ａの位置からｘ軸方向にｄｉｆｆ＿ｘ、ｙ軸方向にｄｉｆｆ＿ｙだけずれている。このようなずれが生じるのは、縦方向走査処理Ｓ５４および横方向走査処理Ｓ５６では、検査領域８０内に原画像領域２０の頂点が入った時点で、走査を停止し、それ以降の探索を行わないためである。また、ノイズの影響により、エッジの追跡だけでは正確な頂点位置を判定できないためでもある。
【０１０７】
図２０（ｂ）は、検査領域８０の中心点すなわち暫定頂点Ｖｅと、原画像領域２０の頂点Ａとが一致している理想的な状態を示したものである。図２０（ｂ）の理想的な状態における検査領域８０の画像は参照画像として、図２０（ａ）の実際の検査領域８０における暫定頂点Ｖｅの位置ずれの調整のために利用される。
【０１０８】
頂点特定部４０のフーリエ変換処理部４６は、図１３の縦方向走査処理Ｓ５４または横方向走査処理Ｓ５６により得られた暫定頂点Ｖｅのｘ座標値ｉｅ、ｙ座標値ｊｅをそれぞれ変数ｉ，ｊに代入し（Ｓ１００）、暫定頂点Ｖｅを中心とする所定のサイズの頂点周辺画像を抽出する（Ｓ１１０）。この頂点周辺画像として、図２０（ａ）に示した暫定頂点Ｖｅを中心とする縦横Ｎ画素の検査領域８０を用いることができる。
【０１０９】
次に、フーリエ変換処理部４６は、暫定頂点Ｖｅの位置ずれを検出するために、頂点周辺画像と同一サイズの参照画像を設定する（Ｓ１１２）。この参照画像として、図２０（ｂ）に示した原画像領域２０の頂点Ａを中心とする縦横Ｎ画素の検査領域８０を用いることができる。原画像の４隅の画像を何らかの形で事前に取得しておき、余白部分が白色の場合、４隅の画像を背景が白地の画像に貼り付けることで、図２０（ｂ）の参照画像を生成することができる。あるいは、図２０（ｂ）の参照画像は、白地の背景に図２０（ａ）の原画像領域２０の輝度値と実質的に同一な輝度値をもつ画像を人工的に生成して貼り付けることにより生成してもよい。
【０１１０】
フーリエ変換処理部４６は、頂点周辺画像と参照画像のそれぞれにフーリエ変換処理を施す（Ｓ１１４）。位相角算出部４７は、頂点周辺画像と参照画像のそれぞれのフーリエ変換の最低水平周波数成分すなわち（１，０）成分の位相角α１、α２を算出する（Ｓ１１６）。また、位相角算出部４７は、頂点周辺画像と参照画像のそれぞれのフーリエ変換の最低垂直周波数成分すなわち（０，１）成分の位相角β１、β２を算出する（Ｓ１１８）。
【０１１１】
頂点位置ずれ調整部４８は、暫定頂点Ｖｅのｙ軸方向の位置ずれｄｉｆｆ＿ｙを（α２−α１）／（２π／Ｎ）により算出し（Ｓ１２０）、暫定頂点Ｖｅのｘ軸方向の位置ずれｄｉｆｆ＿ｘを（β２−β１）／（２π／Ｎ）により算出する（Ｓ１２２）。
【０１１２】
頂点位置ずれ調整部４８は、変数ｉからｘ軸方向のずれｄｉｆｆ＿ｘを減算し、変数ｊからｙ軸方向のずれｄｉｆｆ＿ｙを減算することにより、最終検出頂点Ｖｆの座標（ｉ，ｊ）を求める（Ｓ１２４）。ここで、ｘ軸方向のずれｄｉｆｆ＿ｘ、ｙ軸方向のずれｄｉｆｆ＿ｙは、真の頂点のｘ、ｙ座標からのずれの方向により正負の符号がつけられた整数値であるとする。
【０１１３】
図２１は、頂点周辺画像と参照画像のフーリエ変換の低周波数成分の位相角の関係を説明する図である。同図は、頂点周辺画像と参照画像のフーリエ変換の最低水平周波数成分すなわち（１，０）成分を実軸Ｒｅと虚軸Ｉｍからなる座標系の単位円上の点で示したものであり、頂点周辺画像のフーリエ変換の（１，０）成分１２０の位相角はα１、参照画像のフーリエ変換の（１，０）成分１２２の位相角はα２であり、位相差Δα＝α２−α１が生じる。この位相差は、暫定頂点Ｖｅが真の頂点の位置からｙ軸方向にｄｉｆｆ＿ｊだけずれていることにより生じる。
【０１１４】
図１６（ａ）〜（ｄ）で既に説明したように、画像上のｋ画素のずれは、フーリエ変換後の空間ではωｋの位相差として現れ、最低周波数成分については、角周波数ω＝２π／Ｎであるから、位相差を（２π／Ｎ）で除算することにより、位置ずれｋを算出することができる。すなわち、暫定頂点Ｖｅのｙ軸方向のずれｄｉｆｆ＿ｊは位相差Δαを（２π／Ｎ）で除算することで求められる。同様に、暫定頂点Ｖｅのｘ軸方向のずれｄｉｆｆ＿ｉについては、頂点周辺画像と参照画像のフーリエ変換の最低垂直周波数成分である（０，１）成分の位相角β１、β２を求め、その位相差Δβ＝β２−β１を（２π／Ｎ）で除算することで求められる。
【０１１５】
また、上記のように頂点周辺画像と参照画像の両方を利用することにより、撮影部３０による撮影時のノイズ等による悪影響を除去することができる。
【０１１６】
以上、画像領域判定処理Ｓ１２の詳細な手順を図９〜図２１で説明した。上記の縦方向走査処理Ｓ５４および横方向走査処理Ｓ５６では、検査領域の画像のフーリエ変換の低周波数成分を評価することによりエッジを検出したが、エッジ検出フィルタを用いてエッジを検出してもよい。以下、エッジ検出フィルタによるエッジ検出手順を説明する。
【０１１７】
縦横Ｎ画素の検査領域に対して、横方向のエッジ、縦方向のエッジを検出するためのフィルタを設定し、畳み込み演算を利用したフィルタ演算の出力値を求める。ここではＮ＝４の場合を説明する。検査領域の画像（以下、入力信号ともいう）をｘ（ｉ，ｊ）とし、フィルタ演算による出力信号をｙ（ｍ，ｎ）とする。またエッジ検出フィルタをｈ（ｉ，ｊ）とする。フィルタ演算を次式のタップ数Ｌ＝４の畳み込み演算で行う。
ｙ（ｍ，ｎ）＝Σｉ＝０３Σｊ＝０３ｈ（ｍ−ｉ，ｎ−ｊ）ｘ（ｉ，ｊ）
【０１１８】
図２２（ａ）〜（ｃ）は、エッジ検出フィルタｈ（ｉ，ｊ）と入力信号ｘ（ｉ，ｊ）の例を説明する図である。図２２（ａ）は、横方向のエッジを検出するフィルタｈ（ｉ，ｊ）と、そのフィルタを用いた畳み込み演算によるレスポンスが最も大きくなる入力信号ｘ（ｉ，ｊ）を示す。ここで、エッジの方向は、エッジラインに垂直な方向に定義されていることに注意する。
【０１１９】
図２２（ｂ）は、縦方向のエッジを検出するフィルタｈ（ｉ，ｊ）と、そのフィルタを用いた畳み込み演算によるレスポンスが最も大きくなる入力信号ｘ（ｉ，ｊ）を示す。図２２（ｃ）は、左上の頂点を検出するフィルタｈ（ｉ，ｊ）と、そのフィルタを用いた畳み込み演算によるレスポンスが最も大きくなる入力信号ｘ（ｉ，ｊ）を示す。
【０１２０】
図２３は、エッジ検出フィルタによる縦方向走査処理Ｓ５４を説明するフローチャートである。なお、ここでは、左上の頂点Ａを検出場合を説明する。エッジ検出フィルタの出力信号の閾値を設定する（Ｓ１３０）。頂点探索開始点Ｖｓのｘ座標値ｉから走査幅ｄの１／２を減算して、エッジの走査開始点を設定する（Ｓ１３２）。
【０１２１】
エッジ追跡部４４は、検査点Ｖ（ｉ，ｊ）を中心とする縦横Ｎ画素の領域の２次元画像信号に対して、タップ数Ｌの横方向エッジ検出フィルタによる畳み込み演算を計算し、２次元出力信号ｙ１を求める（Ｓ１３４）。ここでタップ数Ｌは画素数Ｎに等しい。
【０１２２】
２次元出力信号ｙ１の値が閾値以下である場合（Ｓ１３６のＮ）、ｘ座標値ｉを１だけインクリメントして、検査領域をｘ軸方向にシフトさせ（Ｓ１３８）、ステップＳ１３４のフィルタ演算を繰り返す。
【０１２３】
２次元出力信号ｙ１の値が閾値を超えた場合（Ｓ１３６のＹ）、横方向のエッジが検出されたと判定し、次に、点（ｉ，ｊ）を中心とした２次元画像信号に対して、タップ数Ｌの縦方向エッジ検出フィルタによる畳み込み演算を計算し、２次元出力信号ｙ２を求める（Ｓ１４０）。
【０１２４】
２次元出力信号ｙ２の値が閾値を超えた場合（Ｓ１４２のＹ）、縦方向走査処理を終了しリターンする。２次元出力信号ｙ２の値が閾値以下である場合（Ｓ１４２のＮ）、ｙ座標値ｊをタップＬだけデクリメントして、左上の頂点Ａを探索するために、検査領域を上向きにシフトさせ（Ｓ１４４）、ステップＳ１３２以降のエッジ検出を継続する。
【０１２５】
なお、図２３では、左上の頂点Ａを縦方向に探索して検出する場合を説明した。左下の頂点Ｂを検出する場合は、ステップＳ１４４において、検査点Ｖのｙ座標値ｊがＬだけインクリメントされるように変更する。また、右上の頂点Ｃを検出する場合は、ステップＳ１３２において、検査点Ｖのｘ座標値ｉがi＋ｄ／２に設定され、ステップＳ１３８において、検査点Ｖのｘ座標値ｉが１だけデクリメントされるように変更する。また、右下の頂点Ｄを検出する場合は、ステップＳ１３２において、検査点Ｖのｘ座標ｉがi＋ｄ／２に設定され、ステップＳ１３８において、検査点Ｖのｘ座標値ｉが１だけデクリメントされ、ステップＳ１４４において、検査点Ｖのｙ座標値ｊがＬだけインクリメントされるように変更する。
【０１２６】
エッジ検出フィルタによる横方向走査処理Ｓ５６についても、検出するエッジ方向と走査方向を変えれば、同様の手順で実施することができる。
【０１２７】
なお、図２２（ｃ）に示した頂点を検出するためのフィルタを用いれば、エッジ検出フィルタで頂点を検出することもできる。しかしながら、エッジ検出フィルタによる方法は、ノイズに弱いため、頂点の正確な位置を特定するには、フーリエ変換の低周波数成分を用いて位相差から位置ずれを求める方法が有効である。
【０１２８】
以上述べたように、実施の形態の電子透かし抽出装置２００では、撮影画像に含まれる原画像領域を判定する際、検査領域を空間周波数領域に変換し、変換後の信号の位相角に基づいて、原画像領域の頂点を高精度に求めることができる。空間周波数領域に変換したときの低周波数成分を利用するため、撮影画像に撮影による画像の歪みやノイズがある場合でも、正確に頂点を求めることができる。電子透かし抽出装置２００は、このようにして原画像領域を正確に抽出した上で、撮影による歪みを補正し、補正された原画像領域から電子透かしを抽出するため、透かしの検出精度が向上する。
【０１２９】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【０１３０】
そのような変形例として、上記の説明では、原画像領域２０の４頂点をすべて特定し、４頂点の座標値をもとに原画像領域２０を抽出したが、原画像領域２０の対角線上にある２頂点のみを求めるように構成してもよい。撮影領域２６の撮影による歪みが左右対称であるなら、対角線上にある２頂点の座標値から線対称を仮定して原画像領域２０を抽出することが可能である。また、撮影画像の歪みが撮影機器のレンズによるものだけであるなら、原画像領域２０のいずれかひとつの頂点のみを特定し、レンズ歪みが撮影領域２６の中心に関して点対称であることを利用して、原画像領域２０を抽出することも可能である。
【０１３１】
上記の説明では、原画像領域２０を抽出するために、フーリエ変換後の信号の位相角を利用して、原画像領域２０の各頂点の座標値を高い精度で求めたが、同じ位相角を用いた方法で、原画像領域２０の各辺を高い精度で求めてもよい。撮影による歪みにより原画像領域２０の各辺は歪曲している。原画像領域２０の各辺を正確に特定することで、原画像領域２０をより厳密に抽出し、歪み補正の精度を高めることができる。
【０１３２】
上記の透かし検出処理において、透かし検出に失敗した場合、画像領域判定部３２は、エッジ検出フィルタの閾値などのパラメータを変えて、原画像領域２０の判定処理を再度行ってもよい。また、透かし検出に失敗した場合、画像補正部３４が撮影部３０に印刷画像Ｐの再撮影を要求してもよい。
【０１３３】
なお上記実施例では、エッジ検出フィルタ部４２はＰｒｅｗｉｔｔオペレータを用いてエッジラインとエッジ方向を検出していたが、これに代えて、フーリエ変換フィルタを用いてエッジラインとエッジ方向を検出するものであっても良い。
【０１３４】
図２４のフローチャートを参照して、フーリエ変換フィルタを用いたエッジライン及びエッジ方向の検出手順を説明する。なお、図２４において、図１０のエッジ検出処理Ｓ２０の手順を示すフローチャートと処理を同じくする処理ステップについては同じステップ番号を割り当て、かかる処理ステップについての説明は省略する。
【０１３５】
ステップＳ２０４では、検査点（ｉ，ｊ）を中心とした縦横Ｎ画素の検査領域８０の輝度値に係る２次元ＦＦＴが行われる。ここではＮは２のべき乗に相当する数（８、１６、６４等）である。
【０１３６】
ステップＳ２０５では、Ｈｒ（１，０）、Ｈｒ（０，１）、Ｈｉ（１，０）、Ｈｉ（０，１）の値が取得される。ここでＨｒ（ｘ，ｙ）、Ｈｉ（ｘ，ｙ）の定義は、エッジ追跡部４４の処理に関する説明で定義したものと同じである。
【０１３７】
ステップＳ２０６では、上記Ｈｒ（１，０）、Ｈｒ（０，１）、Ｈｉ（１，０）、Ｈｉ（０，１）の全てが０であるかどうかが判断される。検査領域８０内の全ての画素の輝度値は同じである場合、上記４変数は全てが０になる。ステップＳ３６で取得した走査開始点が余白領域であるならば、ステップＳ２０６でｙｅｓと判定された場合は、検査領域８０内は全て余白領域である。このとき、ステップＳ３８において、検査点のｘ座標値ｉにアスペクト比ｗｉｄｔｈ／ｈｅｉｇｈｔを加算し、ｙ座標値ｊに１を加算して、ステップＳ２０４に戻り、探索を続ける。
【０１３８】
ステップＳ２０６において、上記４変数のいずれかが０ではないと判断されたら、検査領域８０内に余白領域と原画像領域２０のエッジがあるものと判断される。
【０１３９】
ステップＳ２０９では、Ｈｒ（１，０）、Ｈｒ（０，１）の両方が０であるかどうかが判断される。検査点（ｉ，ｊ）が余白領域と原画像領域２０のエッジ上にある場合、この両方の変数が０になる。Ｈｒ（１，０）、Ｈｒ（０，１）の少なくとも一方が０でない場合（Ｓ２０９のＮ）、ステップＳ３８において、検査点のｘ座標値ｉにアスペクト比ｗｉｄｔｈ／ｈｅｉｇｈｔを加算し、ｙ座標値ｊに１を加算して、ステップＳ２０４に戻り、探索を続ける。
【０１４０】
Ｈｒ（１，０）、Ｈｒ（０，１）の両方が０である場合（Ｓ２０９のＹ）、ステップＳ２１０において、Ｈｉ（１，０）が０であるかどうかが判断される。Ｈｉ（１，０）が０である場合（Ｓ２１０のＹ）、前記エッジの方向が水平方向（ｘ軸方向）であると判断される（Ｓ２１１）。Ｈｉ（１，０）が０でない場合（Ｓ２１０のＮ）、ステップＳ２０６において４変数Ｈｒ（１，０）、Ｈｒ（０，１）、Ｈｉ（１，０）、Ｈｉ（０，１）のいずれかが０ではなかったことから、Ｈｉ（０，１）が０であることがわかり、前記エッジの方向が垂直方向（ｙ軸方向）であると判定される（Ｓ２１２）。このようにして、フーリエ変換フィルタを用いても、エッジラインとエッジ方向を検出することができる。
【０１４１】
また、上記実施例では、エッジ追跡部４４が縦方向のエッジ走査処理（Ｓ５４）を行う際、検査点Ｖをｘ方向に走査させつつＨｒ（１，０）の値を評価することにより余白領域と原画像領域２０のエッジ位置を特定していた。これに代えて、Ｈｒ（１，０）とＨｉ（１，０）から導かれるＨ（１，０）の位相角、すなわちａｒｃｔａｎ［Ｈｉ（１，０）／Ｈｒ（１，０）］が検査点とエッジ位置からの距離に比例する性質を利用して、前記位相角に基づいてエッジ位置を特定するものであっても良い。かかる方法によれば、撮影条件が良好ではない場合はエッジ位置を誤判定するおそれがあるが、検査点Ｖをｘ方向に走査させながらエッジ位置を特定する方法と比較すれば、エッジ位置の特定を高速に行うことができる。
【０１４２】
上記の実施例は、透かし入り画像の原画像領域２０の頂点の検出に関するものであったが、上記で説明した頂点検出方法は、それ以外の一般的な画像においても適用できるものであり、特に電子透かしの用途に限られない。
【図面の簡単な説明】
【０１４３】
【図１】実施の形態に係る電子透かし埋め込み装置の構成図である。
【図２】図１の電子透かし埋め込み装置から出力される印刷画像を説明する図である。
【図３】実施の形態に係る電子透かし抽出装置の構成図である。
【図４】図３の電子透かし抽出装置により撮影された印刷画像を説明する図である。
【図５】図３の画像領域判定部の詳細な構成を説明する図である。
【図６】図５のエッジ検出部および頂点特定部により原画像領域が判定される様子を説明する図である。
【図７】原画像領域の撮影による歪みを説明する図である。
【図８】図３の電子透かし抽出装置による電子透かし抽出手順の全体的な流れを示すフローチャートである。
【図９】図８の画像領域判定処理の大まかな流れを示すフローチャートである。
【図１０】図９のエッジ検出処理の詳細な手順を示すフローチャートである。
【図１１】エッジ検出フィルタを説明する図である。
【図１２】エッジ検出フィルタにより原画像領域のエッジが検出される様子を説明する図である。
【図１３】図９のエッジライン追跡処理の詳細な手順を説明するフローチャートである。
【図１４】図１３の縦方向走査処理の詳細な手順を説明するフローチャートである。
【図１５】左上の頂点を探索する場合における縦方向走査処理が行われる様子を説明する図である。
【図１６】検査領域のフーリエ変換の最低水平周波数成分により横方向のエッジが判定される原理を説明する図である。
【図１７】図１４の縦方向走査の停止条件を説明する図である。
【図１８】図１３の横方向走査処理の詳細な手順を説明するフローチャートである。
【図１９】図９の頂点位置特定処理の詳細な手順を説明するフローチャートである。
【図２０】暫定頂点の位置ずれを説明する図である。
【図２１】頂点周辺画像と参照画像のフーリエ変換の低周波数成分の位相角の関係を説明する図である。
【図２２】エッジ検出フィルタと入力信号の例を説明する図である。
【図２３】エッジ検出フィルタによる縦方向走査処理を説明するフローチャートである。
【図２４】フーリエ変換フィルタを用いたエッジライン及びエッジ方向の検出手順を説明するフローチャートである。
【符号の説明】
【０１４４】
１０  画像形成部、  １２  埋め込み部、  １４  印刷部、  ２０  原画像領域、  ２４  印刷媒体、  ２６  撮影領域、  ３０  撮影部、  ３２  画像領域判定部、  ３４  画像補正部、  ３６  透かし抽出部、  ３８  エッジ検出部、  ４０  頂点特定部、  ４１  画像領域抽出部、  ４２  エッジ検出フィルタ部、  ４４  エッジ追跡部、  ４６  フーリエ変換処理部、  ４７  位相角算出部、  ４８  頂点位置ずれ調整部、  １００  電子透かし埋め込み装置、  ２００  電子透かし抽出装置。
【図１】
2005182164.tif 000003
【図２】
2005182164.tif 000004
【図３】
2005182164.tif 000005
【図４】
2005182164.tif 000006
【図５】
2005182164.tif 000007
【図６】
2005182164.tif 000008
【図７】
2005182164.tif 000009
【図８】
2005182164.tif 000010
【図９】
2005182164.tif 000011
【図１０】
2005182164.tif 000012
【図１１】
2005182164.tif 000013
【図１２】
2005182164.tif 000014
【図１３】
2005182164.tif 000015
【図１４】
2005182164.tif 000016
【図１５】
2005182164.tif 000017
【図１６】
2005182164.tif 000018
【図１７】
2005182164.tif 000019
【図１８】
2005182164.tif 000020
【図１９】
2005182164.tif 000021
【図２０】
2005182164.tif 000022
【図２１】
2005182164.tif 000023
【図２２】
2005182164.tif 000024
【図２３】
2005182164.tif 000025
【図２４】
2005182164.tif 000026