(57)【特許請求の範囲】
【請求項１】
所定のパターンを含んだ情報記録画像内における所定のパターンの位置を検出する方法であって、
（ａ）画素サイズの単位で、前記情報記録画像中の前記所定のパターンの概略位置を検出するステップと、
（ｂ）前記ステップ（ａ）で検出した概略位置と、前記情報記録画像内の領域と前記所定のパターンの基準画像との間の類似度の分布の重心とに基づいて、画素サイズ未満の単位で、前記情報記録画像内における前記所定のパターンの詳細位置を検出するステップであって、
（ｂ１）前記情報記録画像内の前記ステップ（ａ）で検出した概略位置周辺の領域と前記所定のパターンの基準画像の解像度を上げるステップと、
（ｂ２）前記ステップ（ｂ１）で求めた上げられた解像度の前記情報記録画像内の領域と前記ステップ（ｂ１）で求めた上げられた解像度の前記所定パターンの基準画像の間の詳細類似度を詳細パターンマッチング処理を行うことにより計算するステップと、
（ｂ３）前記ステップ（ｂ２）で求めた詳細類似度の分布の重心位置を計算するステップと、
（ｂ４）前記ステップ（ｂ３）で求めた重心位置に基づいて、前記情報記録画像内における前記所定のパターンの詳細位置を決定するステップと、
を有することを特徴とする画像内パターン位置検出方法。
【請求項２】
前記ステップ（ａ）は更に、
（ａ１）前記情報記録画像内の領域と前記所定パターンの基準画像の間の概略類似度をパターンマッチング処理を行うことにより計算するステップと、
（ａ２）前記ステップ（ａ１）で求めた概略類似度に基づいて、前記情報記録画像内における前記所定のパターンの概略位置を決定するステップと、
を有することを特徴とする請求項１記載の画像内パターン位置検出方法。
【請求項３】
前記ステップ（ｂ）は更に、
（ｂ１１）前記ステップ（ａ）でパターンマッチング処理を行うことで求められた概略類似度を用いて、前記情報記録画像内の領域と前記所定パターンの基準画像の間の詳細類似度を計算するステップと、
（ｂ１２）前記ステップ（ｂ１１）で求めた詳細類似度の分布の重心位置を計算するステップと、
（ｂ１３）前記ステップ（ｂ１２）で求めた重心位置に基づいて、前記情報記録画像内における前記所定のパターンの詳細位置を決定するステップと、
を有することを特徴とする請求項１記載の画像内パターン位置検出方法。
【請求項４】
前記ステップ（ｂ１１）は、前記概略類似度を画素サイズ未満の単位で線形補間することにより前記詳細類似度を計算することを特徴とする請求項３記載の画像内パターン位置検出方法。
【請求項５】
前記情報記録画像は読み取り画像中に含まれており、
前記読み取り画像中の前記情報記録画像の領域を判定するステップをさらに有することを特徴とする請求項１記載の画像内パターン位置検出方法。
【請求項６】
所定のパターンを含んだ情報記録画像内における所定のパターンの位置を検出する装置であって、
画素サイズの単位で、前記情報記録画像中の前記所定のパターンの概略位置を検出する概略位置検出手段と、
前記概略位置検出手段で検出した概略位置と、前記情報記録画像内の領域と前記所定のパターンの基準画像との間の類似度の分布の重心とに基づいて、画素サイズ未満の単位で、前記情報記録画像内における前記所定のパターンの詳細位置を検出する詳細位置検出手段であって、前記情報記録画像内の前記概略位置検出手段で検出した概略位置周辺の領域と前記所定のパターンの基準画像の解像度を上げる高解像度化手段と、前記高解像度化手段で求めた上げられた解像度の前記情報記録画像内の領域と前記高解像度化手段で求めた上げられた解像度の前記所定パターンの基準画像の間の詳細類似度を詳細パターンマッチング処理を行うことにより計算する類似度計算手段と、前記類似度計算手段で求めた詳細類似度の分布の重心位置を計算する重心計算手段と、前記重心計算手段で求めた重心位置に基づいて、前記情報記録画像内における前記所定のパターンの詳細位置を決定する位置決定手段とを有する詳細位置検出手段と、
を有することを特徴とする画像内パターン位置検出装置。
【請求項７】
前記概略位置検出手段は更に、
前記情報記録画像内の領域と前記所定パターンの基準画像の間の概略類似度をパターンマッチング処理を行うことにより計算する類似度計算手段と、
前記類似度計算手段で求めた概略類似度に基づいて、前記情報記録画像内における前記所定のパターンの概略位置を決定する位置決定手段と、
を有することを特徴とする請求項６記載の画像内パターン位置検出装置。
【請求項８】
前記詳細位置検出手段は更に、
前記概略位置検出手段でパターンマッチング処理を行うことで求められた概略類似度を用いて、前記情報記録画像内の領域と前記所定パターンの基準画像の間の詳細類似度を計算する類似度計算手段と、
前記類似度計算手段で求めた詳細類似度の分布の重心位置を計算する重心計算手段と、
前記重心計算手段で求めた重心位置に基づいて、前記情報記録画像内における前記所定のパターンの詳細位置を決定する位置決定手段と、
を有することを特徴とする請求項６記載の画像内パターン位置検出装置。
【請求項９】
前記類似度計算手段は、前記概略類似度を画素サイズ未満の単位で線形補間することにより前記詳細類似度を計算することを特徴とする請求項８記載の画像内パターン位置検出装置。
【請求項１０】
前記情報記録画像は読み取り画像中に含まれており、
前記読み取り画像中の前記情報記録画像の領域を判定する領域判定手段をさらに有することを特徴とする請求項６記載の画像内パターン位置検出装置。
【請求項１１】
前記請求項１〜５のいづれかに記載の、画像内パターン位置検出方法をコンピュータに実行させるためのプログラム。
【請求項１２】
前記請求項１〜５のいづれかに記載の、画像内パターン位置検出方法をコンピュータに実行させるためのプログラムが記録された記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、光学的な情報記録に利用される２次元画像記録・再生における画像内パターン位置検出方法、装置、プログラムおよびプログラムが記録された記録媒体に関する。
【０００２】
【従来の技術】
情報を２次元画像として記録し再生する方法に、２次元コードとして知られているＱＲコード（株式会社デンソーによって１９９４年に発表されたコードで日本工業規格（ＪＩＳ  Ｘ  ０５１０）として認定されている。：Ｑｕｉｃｋ  Ｒｅｓｐｏｎｓｅ  Ｃｏｄｅ）や、データマトリクス（Ｕｎｉｔｅｄ  Ｐａｒｃｅｌ  Ｓｅｒｖｉｃｅ社によって１９８０年代後半に発表されたコード。）がある。２次元コードとは、水平方向と垂直方向の２方向に情報を持たせることによって記録させる方法であって、１次元コード、例えばバーコードと比べると数十倍から数百倍の情報を記録できる特徴を持っている。
【０００３】
２次元コードは、情報を切り出すための切り出しシンボルと各セルの位置と大きさを表すためのタイミングマークなどを持っている。従って、情報が記憶された２次元画像は、切り出しシンボル、タイミングマークおよび実際の記録情報からなる。情報の再生は、ＣＣＤ（Ｃｈａｒｇｅｄ  Ｃｏｕｐｌｅｄ  Ｄｅｖｉｃｅ）カメラなどの受光装置で画像を読み込み２値化画像に変換された後、切り出しシンボルとタイミングマークを検出し、画像上のどの画素が黒か白かを判定することにより行われる。
【０００４】
ＱＲコードは、データマトリクスとは切り出しシンボルの検出方法が異なっている。ＱＲコードは３頂点に設けられた矩形の切り出しシンボルを持っており、この切り出しシンボルは特定のパルス信号が見知されるようなデザインとなっている。この方法により高速な切り出し位置検出を行っている。
【０００５】
一方、データマトリクスは、切り出しシンボルがＬ型のガイドラインになっており、ＱＲコードのようにパルス検出によりガイドラインを検出することができず、何らかのソフト処理が必要となっている。
【０００６】
【発明が解決しようとする課題】
しかしながら上述したような従来技術においては以下のような解決すべき課題があった。
【０００７】
上述した従来の技術において、一般的な２次元コードは黒か白を表現する１画素の大きさが、読み取り装置の一画素の大きさより遙かに大きくなっている。つまり、１画素を検出する場合に、読み取り装置の複数の画素で検出を行うので、白か黒を判断することが容易となり、ノイズなどによる検出エラーが少ないことになる。しかしながら、小さな範囲に大量の情報を記憶することが難しくなることから、記憶密度の上昇を望むのは難しかった。
【０００８】
また、ホログラム画像のようなノイズの大きな２次元画像では、コントラストが悪く白と黒の中間色である灰色の部分が増え、白か黒かの判断が非常に難しくなり、ＱＲコードのような特定のパルス信号を検出することが難しかった。
【０００９】
また、読み取り装置の１画素単位でのデータの取り込み、および位置検出を行うため記録画像の画素と読み取り装置の画素間に画素ずれを起こした場合において、位置検出が画素単位でしか行えないため詳細な検出が難しく、正確な位置の検出も難しかった。
【００１０】
本発明はこれらの課題に鑑みてなされたものであり、ＱＲコードやデータマトリクスのような手法では記憶および再生が難しいノイズの大きな２次元画像を、高密度に効率よく記憶することのできる情報の２次元画像記録・再生における画像内パターン位置検出方法、装置、プログラムおよびプログラムが記録された記録媒体を提供することを目的とする。
【００１１】
【課題を解決するための手段】
前記課題を解決するために、本発明は、所定のパターンを含んだ情報記録画像内における所定のパターンの位置を検出する方法であって、（ａ）画素サイズの単位で、前記情報記録画像中の前記所定のパターンの概略位置を検出するステップと、（ｂ）前記ステップ（ａ）で検出した概略位置と、前記情報記録画像内の領域と前記所定のパターンの基準画像との間の類似度の分布の重心とに基づいて、画素サイズ未満の単位で、前記情報記録画像内における前記所定のパターンの詳細位置を検出するステップと、を有することを特徴とする画像内パターン位置検出方法を提供する。
【００１２】
また、本発明では、前記ステップ（ａ）は更に、（ａ１）前記情報記録画像内の領域と前記所定パターンの基準画像の間の概略類似度をパターンマッチング処理を行うことにより計算するステップと、（ａ２）前記ステップ（ａ１）で求めた概略類似度に基づいて、前記情報記録画像内における前記所定のパターンの概略位置を決定するステップと、を有することを特徴とする。
【００１３】
また、本発明では、前記ステップ（ｂ）は更に、（ｂ１）前記情報記録画像内の前記ステップ（ａ）で検出した概略位置周辺の領域と前記所定のパターンの基準画像の解像度を上げるステップと、（ｂ２）前記ステップ（ｂ１）で求めた上げられた解像度の前記情報記録画像内の領域と前記ステップ（ｂ１）で求めた上げられた解像度の前記所定パターンの基準画像の間の詳細類似度を詳細パターンマッチング処理を行うことにより計算するステップと、（ｂ３）前記ステップ（ｂ２）で求めた詳細類似度の分布の重心位置を計算するステップと、（ｂ４）前記ステップ（ｂ３）で求めた重心位置に基づいて、前記情報記録画像内における前記所定のパターンの詳細位置を決定するステップと、を有することを特徴とする。
【００１４】
また、本発明では、前記ステップ（ｂ）は更に、（ｂ１１）前記ステップ（ａ）でパターンマッチング処理を行うことで求められた概略類似度を用いて、前記情報記録画像内の領域と前記所定パターンの基準画像の間の詳細類似度を計算するステップと、（ｂ１２）前記ステップ（ｂ１１）で求めた詳細類似度の分布の重心位置を計算するステップと、（ｂ１３）前記ステップ（ｂ１２）で求めた重心位置に基づいて、前記情報記録画像内における前記所定のパターンの詳細位置を決定するステップと、を有することを特徴とする。
【００１５】
また、本発明では、前記ステップ（ｂ１１）は、前記概略類似度を画素サイズ未満の単位で線形補間することにより前記詳細類似度を計算することを特徴とする。
【００１６】
また、本発明では、前記情報記録画像は読み取り画像中に含まれており、前記読み取り画像中の前記情報記録画像の領域を判定するステップをさらに有することを特徴とする。
【００１７】
さらに、本発明は、所定のパターンを含んだ情報記録画像内における所定のパターンの位置を検出する装置であって、画素サイズの単位で、前記情報記録画像中の前記所定のパターンの概略位置を検出する概略位置検出手段と、前記概略位置検出手段で検出した概略位置と、前記情報記録画像内の領域と前記所定のパターンの基準画像との間の類似度の分布の重心とに基づいて、画素サイズ未満の単位で、前記情報記録画像内における前記所定のパターンの詳細位置を検出する詳細位置検出手段と、を有することを特徴とする画像内パターン位置検出装置を提供する。
【００１８】
また、本発明では、前記概略位置検出手段は更に、前記情報記録画像内の領域と前記所定パターンの基準画像の間の概略類似度をパターンマッチング処理を行うことにより計算する類似度計算手段と、前記類似度計算手段で求めた概略類似度に基づいて、前記情報記録画像内における前記所定のパターンの概略位置を決定する位置決定手段と、を有することを特徴とする。
【００１９】
また、本発明では、前記詳細位置検出手段は更に、前記情報記録画像内の前記概略位置検出手段で検出した概略位置周辺の領域と前記所定のパターンの基準画像の解像度を上げる高解像度化手段と、前記高解像度化手段で求めた上げられた解像度の前記情報記録画像内の領域と前記高解像度化手段で求めた上げられた解像度の前記所定パターンの基準画像の間の詳細類似度を詳細パターンマッチング処理を行うことにより計算する類似度計算手段と、前記類似度計算手段で求めた詳細類似度の分布の重心位置を計算する重心計算手段と、前記重心計算手段で求めた重心位置に基づいて、前記情報記録画像内における前記所定のパターンの詳細位置を決定する位置決定手段と、を有することを特徴とする。
【００２０】
また、本発明では、前記詳細位置検出手段は更に、前記概略位置検出手段でパターンマッチング処理を行うことで求められた概略類似度を用いて、前記情報記録画像内の領域と前記所定パターンの基準画像の間の詳細類似度を計算する類似度計算手段と、前記類似度計算手段で求めた詳細類似度の分布の重心位置を計算する重心計算手段と、前記重心計算手段で求めた重心位置に基づいて、前記情報記録画像内における前記所定のパターンの詳細位置を決定する位置決定手段と、を有することを特徴とする。
【００２１】
また、本発明では、前記類似度計算手段は、前記概略類似度を画素サイズ未満の単位で線形補間することにより前記詳細類似度を計算することを特徴とする。
【００２２】
また、本発明では、前記情報記録画像は読み取り画像中に含まれており、前記読み取り画像中の前記情報記録画像の領域を判定する領域判定手段をさらに有することを特徴とする。
【００２３】
さらに、本発明は、上述した画像内パターン位置検出方法をコンピュータに実行させるためのプログラムを提供する。
【００２４】
さらに、本発明は、上述した画像内パターン位置検出方法をコンピュータに実行させるためのプログラムが記録された記録媒体を提供する。
【００２５】
【発明の実施の形態】
次に本発明の実施の形態について図面を参照して説明する。
【００２６】
図１は本発明の実施の形態の読み取り画像位置検出のための情報記録部１０を示すブロック図である。情報記録部１０は、位置決めパターン生成手段１１と、位置決めパターン埋め込み手段１２から構成される。
【００２７】
位置決めパターン生成手段１１は、位置決めを行うために必要な所定のパターンを生成し、位置決めパターン埋め込み手段１２は、位置決めパターン生成手段１１により生成された所定のパターンを記録する情報１３に埋め込み、記録画像１４を作成する。
【００２８】
次に情報記録部１０を構成する各手段の動作について詳細に説明する。
【００２９】
位置決めパターン生成手段１１は、位置決めを行うために必要な所定のパターン（位置決めパターン）を生成する。図３は位置決めパターンの例を示す図である。今、ビット０を白（空白）、ビット１を黒（斜線）で表現するとき、位置決めパターン３３は図３に示すように、中心から１（黒），０（白），１（黒），０（白）のように構成されている。ここで「０」と「１」とを白と黒を用いて表現しているのは、意味のある値に対する意であり、理論を反転させても「０」と「２５５」のような値を用いることも本発明の技術範疇に含まれる。従って、中心から０，１，０，１と入れ替えても、ビット０を黒、ビット１を白と入れ替えてもよい。
【００３０】
また、図３に示す位置決めパターン３４や位置決めパターン３５のように１と０が連続する数を変えても良い。例えば位置決めパターン３５では中心から１を表す画素数が２個、０を表す画素数が５個、１を表す画素数が３個、０を表す画素数が１個と表現している。その画素数は対象とする画像の大きさや記録・再生機構によって任意であり、ただあまり大きくすると、記録領域が減ってしまうことから、記録密度が減少することになる。位置決めパターン３３のような小さな位置決めパターンであっても、後述する概略位置検出手段と詳細位置検出手段により位置検出が行えるため、位置検出精度と記録領域から位置決めパターンを決定する。
【００３１】
位置決めパターン埋め込み手段１２は、記録する情報１３に位置決めパターンを埋め込み、記録画像１４を作成する。図４は、位置決めパターンの埋め込み例を示す図である。位置決めパターン４１〜４４が、それぞれ角の位置検出を行うために、４つ角に埋め込まれている。記録する情報は情報記録領域４５に記録される。位置決めパターン４１〜４４と情報記録領域４５の全体が実際の記録画像となる。また、位置決めパターンは、記録領域の大きさや形などにより、必要な個数、適当な位置に埋め込んでかまわない。
【００３２】
図２は本発明の実施の形態の読み取り画像位置検出のための位置検出部２０を示すブロック図である。位置検出部２０は、記録領域判定手段２２、概略位置検出手段２３、詳細位置検出手段２４から構成され、位置決めのための所定のパターンが埋め込まれた画像を読み取って得られた読み取り画像である画像２１が入力され、詳細な位置座標２５が出力される。
【００３３】
図５は位置検出部２０の処理の流れを示すフローチャートである。取り込まれた読み取り画像５０に対し、記録領域判定手段２２が、画像の縦と横方向それぞれについて画素値の総和を計算し（ステップ５１）、画素値の集中している部分を記録領域と判定して切り出す（ステップ５２）。
【００３４】
次に概略位置検出手段２３が、読み取り画像中の記録領域にある所定のパターンと、位置決めのために埋め込んでおいた基準となる所定のパターン（位置決めパターン）との間の類似度を計算し（ステップ５３）、類似度の最も高い画素を読み取り画像中の所定のパターンの概略位置と決定する（ステップ５４）。
【００３５】
次に、詳細位置検出手段２４が、位置決めパターンと読み取り画像中の所定のパターンの画像について擬似的に解像度を上げ（ステップ５５）、詳細なパターンマッチング処理を行って類似度を算出する（ステップ５６）か、あるいは概略位置を検出する段階で算出された類似度とその重ね合わせから詳細なパターンマッチング処理と同等の類似度を算出する（ステップ５７）。
【００３６】
そして、詳細位置検出手段２４は、ステップ５５、５６で算出された類似度か、あるいはステップ５７で算出された類似度を用いて、類似度分布の重心位置を計算し（ステップ５８）、重心位置から読み取り画像にある所定のパターンの詳細な位置を決定する（ステップ５９）。
【００３７】
次に位置検出部２０を構成する各手段の動作について詳細に説明する。
【００３８】
記録領域判断手段２２は、記録画像を取り込む読み取り装置などによって読み取った読み取り画像から、記録領域部分を検出しその領域を取り出す。図６は記録領域を検出する手順を示す図である。読み取り装置などによって読み取った読み取り画像６１は、記録画像の記録領域６４を含んでいる。記録領域判定手段２２は、読み取り画像６１から記録領域６４を検出し切り出す。
【００３９】
まず、読み取り画像６１の横軸方向を考える。横方向の各画素に対し、縦方向の全ての画素の画素値の総和６２を求める。次に読み取り画像６１の縦軸方向を考える。縦方向の各画素に対し、横方向の全ての画素の画素値の総和６３を求める。横軸方向の画素値の総和６２と縦軸方向の画素値の総和６３が集中している部分を記録領域６４であると判断し、その部分周辺の領域６５を切り出す。
【００４０】
概略位置検出手段２３は、記録領域判定手段２２により切り出された画像に対し、位置決めのために埋め込んでおいた基準となる所定のパターン（位置決めパターン）を用いてパターンマッチング処理を行い、埋め込まれている各所定のパターンに対し最も類似度の高い位置を、所定のパターンの概略位置として検出する。図７はこのパターンマッチング処理を示す図である。画像７１は読み取り画像中の記録領域にある所定のパターン付近を表しており、画像７４は位置決めパターンを表している。
【００４１】
パターンマッチング処理では、記録領域のすべての画素、あるいは候補となり得る画素について位置決めパターン７４との類似度を計算する。ここでは、パターンマッチング処理方法を２種類説明する。
【００４２】
記録領域画像７１の画素７２について位置決めパターン７４との類似度を計算する場合、検出したい位置を位置決めパターン７４の中心画素７５とする（検出したい位置は位置決めパターン７４の中心である必要はない）と、記録領域画像７１の画素７２と位置決めパターン７４の画素７５を一致させ、記録領域画像７１と位置決めパターン７４の間でパターンマッチング処理を行う。
【００４３】
第１の方法では、記録領域画像７１と位置決めパターン７４の対応する画素の画素値の差を計算し、位置決めパターン７４に相当する領域７３内の全ての画素について求めた画素値の差の絶対値を足し合わせ、得られた値を画素７２の類似度とする。もし、領域７３と位置決めパターン７４が完全に一致すれば、類似度は０となる。
【００４４】
第２の方法では、記録領域画像７１と位置決めパターン７４の対応する画素の画素値の積を計算し、位置決めパターン７４に相当する領域７３内の全ての画素について求めた画素値の積を足し合わせ、得られた値を画素７２の類似度とする。この場合、類似度が一番大きい画素において、領域７３と位置決めパターン７４が最も一致していることになる。
【００４５】
次にパターンマッチング処理により求めた類似度を用いて、類似度が一番高い画素を検出し、その画素を読み取り画像中の所定のパターンの概略位置とする。
【００４６】
詳細位置検出手段２４は、基準となる所定のパターン（位置決めパターン）と概略位置検出手段２３によって検出された所定のパターンの画像に対し、擬似的に画像の解像度を上げ、詳細なパターンマッチング処理を行って類似度を算出するか、あるいは概略位置を検出する段階で算出された類似度とその重ね合わせから詳細なパターンマッチング処理と同等の類似度を算出する。そして、詳細位置検出手段２４は、算出された類似度を用いて類似度分布の重心位置を計算し、重心位置から所定のパターンの詳細位置を決定する。
【００４７】
ここでは、詳細な類似度を算出する方法を２種類、重心位置の計算と詳細位置の決定と併せて説明する。
【００４８】
詳細な類似度を計算する第１の方法を説明する。まず、位置決めパターンの画像の解像度を擬似的に上げる。次に概略位置検出手段２３によって検出された概略位置付近の画像の解像度を擬似的に上げる。解像度を上げる領域は、詳細な位置決めの候補となる画素により規定する。図８は擬似的な高解像度化の手順を示す図である。今、高解像度化の対象として位置決めパターンの２掛ける２の画像領域を考える。各画素の解像度をｎ倍に上げる場合には、各画素をｎ掛けるｎの部分領域に分割し、それらの部分領域に元の画素の画素値を割り当て新しい画素とする。このようにして、ｎ＝５の場合の画像８２を、画像８１を高解像度化して求めることができる。
【００４９】
同様に、記録領域画像の概略位置付近（詳細な位置決めの対象となる領域）の解像度を上げる。
【００５０】
次に、高解像度化した記録領域画像に対し、高解像度化した位置決めパターンを用いて、概略位置検出手段２３と同様のパターンマッチング処理を行い、得られた結果を高解像度後の類似度とする。
【００５１】
ここで、詳細な位置決めの対象となる領域とは、概略位置を中心とした詳細位置検出の対象となる領域に対し、高解像度化した位置決めパターンを用いて類似度を計算するために必要な領域である。例えば、概略位置を中心として３掛ける３画素の領域から詳細な位置検出を行うのに、７掛ける７画素の位置決めパターンを用いる場合には、９掛ける９画素の領域が必要となる。
【００５２】
次に詳細な類似度を計算する第２の方法を説明する。この方法では、概略位置検出手段２３によって算出した類似度を元に、擬似的にパターンマッチング処理の結果を算出する。
【００５３】
まず簡単のために、１次元の場合を考える。図９は、１次元の場合の処理を示す図である。ここで、位置決めパターンの画素数をｍ、各画素の値をＧｉ、記録領域画像の対応する画素の値をＸｉとする。位置決めパターンの各画素と記録領域画像の各画素の位置が一致しているとすると、パターンマッチング処理の結果Ｆは、図１０に示す式９５のように表せる。
【００５４】
この位置から、位置決めパターンを１／ｎ画素ずつ右へシフトさせたときのパターンマッチング処理の結果ＦｓとＦとの差分を考える。画像全体の結果は各画素ごとの結果の総和であるので、ある１画素についての結果Ｆｓ’を考える。記録領域画像９１のその画素の値をＸｊ、その画素の左隣りの画素の値をＸｋ、位置決めパターン９２のその画素の値をＧｊ、その画素の左隣りの画素の値をＧｋとする。以下では、概略類似度をパターンマッチング処理を第１の方法で行うことにより計算した場合について、具体的な式を用いて説明する。左隣りの画素に対するパターンマッチング処理の結果Ｆｓ’は｜Ｇｋ−Ｘｋ｜である。記録領域画像９３に対し位置決めパターン９４を右へ１／ｎだけシフトさせたとき、パターンマッチング処理の結果は、位置決めパターンの画素ｋの１／ｎ部分だけが｜Ｇｋ−Ｘｊ｜となり、その他の部分は変化しないため、図１０に示す式９６のように表せる。従って、シフト前の結果との差分Ｓは、図１０に示す式９７のように表せる。
【００５５】
位置決めパターンをさらに右へ１／ｎだけシフトさせた時（合計で２／ｎシフトした時）も、パターンマッチング処理の結果は、位置決めパターンの画素ｋの１／ｎ部分だけが新たに｜Ｇｋ−Ｘｊ｜となり、その他の部分は変化しないため、図１０に示す式９８のように表せ、シフト前の結果との差分Ｓは図１０に示す式９９のように表せる。
【００５６】
この２／ｎシフト後の差分Ｓは、１／ｎシフト後の差分Ｓと同じである。つまり、１／ｎ画素分ずつシフトさせたときの各画素毎のパターンマッチング処理の結果Ｆｓ’は等差数列を形成する。
【００５７】
画像全体の結果Ｆｓは各画素毎の結果Ｆｓ’の総和であるから、パターンマッチング処理全体での結果Ｆｓも同様に等差数列を形成する。そして、ｎ回シフトさせた後の結果は隣の画素についての結果と完全に一致するので、これは記録領域画像と位置決めパターンが１画素右にずれている時のパターンマッチング処理の結果と一致する。
【００５８】
ある位置でのパターンマッチング処理の結果をＦ（ｋ）、その右隣でのパターンマッチング処理の結果をＦ（ｋ＋１）とすると、それらの間でｘ回シフトさせたときのパターンマッチング処理の結果は、図１０に示す式１００のように表せる。但し、ｘは０≦ｘ≦ｎとなる整数である。式１００は、画素を高解像度化した後のパターンマッチング処理の結果、即ち、詳細類似度Ｆｓが、画素を高解像度化する前のパターンマッチング処理の結果、即ち概略類似度Ｆを線形補間したものであることを示している。
【００５９】
よって、高解像度化する前のパターンマッチング処理の結果を用いて、高解像度化後のパターンマッチング処理の結果を擬似的に得ることができる。これは左へのシフトと、上下へのシフトにおいても同様であり、２次元（左右方向と上下方向）にシフトする場合は、これら結果の重ね合わせで計算できる。以上では、パターンマッチング処理の第１の方法による結果を用いる場合を示したが、パターンマッチング処理の第２の方法による結果を用いる場合には、式１００において、Ｆ（ｋ）およびＦ（ｋ＋１）をパターンマッチング処理の第２の方法によって得られる類似度に置換すればよいことが全く同様の考え方によって導出される。
【００６０】
次に、２次元的にシフトする場合のパターンマッチング処理の結果を、図８に示したように解像度を上げると仮定した場合について説明する。ここで、記録領域画像の画素の座標を（ｋ，ｌ）とし、画素（ｋ，ｌ）において概略位置検出手段２３により算出された類似度をＦ（ｋ，ｌ）とする。この類似度は、パターンマッチング処理の第１の方法、第２の方法のいづれによって得られたものであっても構わない。
【００６１】
また、高解像度化の倍率をｎとし、座標（ｋx，ｌy）を（ｋ，ｌ，ｘ，ｙ）として表現し、詳細なパターンマッチング処理の結果をＦｓ（ｋ，ｌ，ｘ，ｙ）とする。なお、ｘ（０≦ｘ≦ｎ）、ｙ（０≦ｙ≦ｎ）は、画素のシフト量を表している。この場合、図１１に示す式１０１の関係が成り立ち、高解像度化した画像の座標（ｋ，ｌ）に当たる画素から横方向にｘ／ｎ画素、縦方向にｙ／ｎ画素だけシフトさせたときのパターンマッチング処理の結果、即ち高解像度化後の類似度は、図１１に示す式１０２によって算出できる。式１０２は、２次元の場合においても１次元の場合と同様、画素を高解像度化した後のパターンマッチング処理の結果、即ち、詳細類似度Ｆｓが、画素を高解像度化する前のパターンマッチング処理の結果、即ち概略類似度Ｆを線形補間したものであることを示している。
【００６２】
ここで説明した詳細な類似度を計算する第２の方法は、第１の方法と同じ計算結果を得ることができ、さらに第１の方法に比べ圧倒的に計算量を減らすことができるため、処理の高速化に有利となる。
【００６３】
詳細な類似度を計算する第１の方法または第２の方法により、図１２に示すような詳細な類似度の分布を表す類似度分布画像１１１が得られる。この類似度分布画像１１１は、概略類似度をパターンマッチング処理の第１の方法を行うことにより計算した場合の一例を示している。ここで実線１１２は元の画素の境界を表し、破線１１３は高解像度化した後の画素の境界を表す。図１２は、高解像度化の倍率がｎ＝３の場合を示しており、類似度を表す画素値１１４を、黒を０、白を２５５として２５６段階のグレースケールによって表している。すなわち、黒に最も近い画素が類似度の一番高い画素となっている。なお、概略類似度をパターンマッチング処理の第２の方法を行うことにより計算した場合には、黒および白が表す画素値の大小関係がこの例と逆になるだけで、以下の処理の考え方に変わりはない。実際に詳細位置検出を行うときは、類似度を画像化したり２５６段階のグレースケール化する必要はなく、類似度を数値として扱えばよい。
【００６４】
この例では、座標（Ｐ１ｘ，Ｐ１ｙ）の画素が類似度が一番高いとする。ここで、擬似的に画像の解像度を上げていることと、画像のノイズと、記録画像の画素と画像の読み取り装置の画素との間の画素ずれのため、座標（Ｐ１ｘ，Ｐ１ｙ）が求めたい正確な詳細位置であるとは言えない。そこで、類似度分布画像１１１から類似度の重心を求めることにより、真の記録位置を推定する。
【００６５】
具体的には、例えば図１３に示す式１２１，１２２や、図１４に示す式１３１，１３２，１３３でこれを行う。図１３の場合、Ａが類似度の高い画素の集合（詳細位置の候補の集合）、ＮがＡに含まれる画素の数、Ｐｘが画素Ｐのｘ座標値，Ｐｙが画素Ｐのｙ座標値とする。そのとき、検出位置（Ｐ２ｘ，Ｐ２ｙ）は図１３に示す式１２１，１２２によって計算できる。
【００６６】
また、図１４の場合、Ａが類似度の高い画素の集合、あるいは全画素集合、Ｗ（Ｐ）が画素Ｐの重み関数、ＰｘとＰｙがそれぞれ画素Ｐのｘ座標値とｙ座標値、ＭがＡに含まれる画素の重み関数Ｗ（Ｐ）の総和とする。そのとき、検出位置（Ｐ２ｘ，Ｐ２ｙ）は図１４に示す式１３１，１３２によって計算できる。この計算で用いる重み関数Ｗ（Ｐ）は、概略類似度をパターンマッチング処理の第１の方法を行うことで計算した場合には、例えば、高解像度化した画素Ｐの詳細類似度Ｆｓ（Ｐ）の補数とし、概略類似度をパターンマッチング処理の第２の方法を行うことにより計算した場合には、例えば詳細類似度Ｆｓ（Ｐ）そのものとする。
【００６７】
最後に、図１３または図１４の式で得られた座標（Ｐ２ｘ，Ｐ２ｙ）を、読み取り画像中の所定のパターンの詳細位置として検出する。
【００６８】
以上説明した本発明の実施の形態は、記録時に、記録したい情報の２次元画像に対し、中心から外側に向けて１，０，１というパターンを持った矩形領域画像を４つの頂点に配置し、位置検出の際は、記録領域を含む２次元画像に対し、縦方向と横方向のそれぞれについて、画像の画素値の総和を計算し、画素値の集中する度合いから記録領域を判断し、その領域を取り出し、１，０，１なるパターンを持った位置決め情報画像によってパターンマッチングを行いおおよその記録位置を検出し、その位置付近に対し、画素数の拡大を行って詳細なパターンマッチング処理を行った後、マッチング結果の上位いくつかの候補の分布の重心から記録位置を計算し検出することを最も主要な特徴とする。
【００６９】
また、従来のＱＲコードにおいては、切り出しシンボルの特定のパルス信号が見知されていたのに対し、本発明においては、３段階のパターンマッチング処理によって記録位置の検出を行っている点を特徴とする。
【００７０】
また、パターンマッチング処理の方法において、その他のコードの位置検出法とは、段階的に処理を行い、候補の分布から記録位置を計算し、アナログ的に記録位置を検出する点が異なる。
【００７１】
記録する２次元画像には、位置検出用の位置決め情報画像が組み込まれており、これをパターンマッチング処理する事により位置検出を行うため、パルス信号を検出し位置検出を行う手法よりも、画像のノイズや歪みに強い位置検出が可能である。
【００７２】
また、段階的に詳細な検出を行うパターンマッチング処理と、検出位置の候補の分布の重心から最終的な検出位置を計算することにより、画像のノイズや歪みに強い、精度の高い位置検出が可能となる。
【００７３】
なお、以上説明した実施の形態は、本発明の理解を容易にするために記載されたものであって、本発明を限定するために記載されたものではない。したがって、上記の実施の形態に開示された各要素は、本発明の技術的範囲に属する全ての設計変更や均等物をも含む趣旨である。
【００７４】
【発明の効果】
以上説明したように、本発明によれば、情報を２次元画像によって記録した場合においてノイズが大きい場合や、記録密度を増加させるために位置決めのための画像が小さい場合に、その記録領域の位置を検出でき、また、記録画像と画像の読み取り装置の間で画素ずれを起こしていても、記録位置の候補となる画素の分布の重心から正確な記録位置を検出できる情報の２次元画像記録・再生における画像内パターン位置検出方法、装置、プログラムおよびプログラムが記録された記録媒体を提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態において用いられる情報記録部を示すブロック図。
【図２】本発明の一実施形態において用いられる位置検出部を示すブロック図。
【図３】本発明の一実施形態において用いられる位置決めパターンの３つの例を示す図。
【図４】本発明の一実施形態において用いられる位置決めパターンが埋め込まれた記録画像の例を示す図。
【図５】図２の位置検出部による処理のフローチャート。
【図６】図２の位置検出部による、記録領域の検出の手順の例を説明する図。
【図７】図２の位置検出部による、パターンマッチング処理の例を説明する図。
【図８】図２の位置検出部による、擬似的に画像の解像度を上げる手順の例を説明する図。
【図９】本発明の一実施形態における詳細な類似度を計算する第２の方法を１次元の場合について説明する図。
【図１０】本発明の一実施形態における詳細な類似度を計算する第２の方法で用いる式を１次元の場合について示す図。
【図１１】本発明の一実施形態における詳細な類似度を計算する第２の方法で用いる式を２次元の場合について示す図。
【図１２】本発明の一実施形態において図２の位置検出部により用いられる類似度分布の例を示す図。
【図１３】本発明の一実施形態における類似度分布の重心を計算する第１の方法で用いる式を示す図。
【図１４】本発明の一実施形態における類似度分布の重心を計算する第２の方法で用いる式を示す図。
【符号の説明】
１０…情報記録部
１１…位置決めパターン生成手段
１２…位置決めパターン埋め込み手段
１３…記録する情報
１４…記録画像
２０…位置検出部
２１…読み取り画像
２２…記録領域判定手段
２３…概略位置検出手段
２４…詳細位置検出手段
２５…詳細位置座標
３３…位置決めパターンの例１
３４…位置決めパターンの例２
３５…位置決めパターンの例３
４１〜４４…位置決めパターン
４５…情報の記録領域
【図１】
0004002156.tif 000002
【図２】
0004002156.tif 000003
【図３】
0004002156.tif 000004
【図４】
0004002156.tif 000005
【図５】
0004002156.tif 000006
【図６】
0004002156.tif 000007
【図７】
0004002156.tif 000008
【図８】
0004002156.tif 000009
【図９】
0004002156.tif 000010
【図１０】
0004002156.tif 000011
【図１１】
0004002156.tif 000012
【図１２】
0004002156.tif 000013
【図１３】
0004002156.tif 000014
【図１４】
0004002156.tif 000015