トップ :: H 電気 :: H04 電気通信技術




【発明の名称】 小型セキュリティマークの検出のための方法
【発明者】 【氏名】ジガン ファン
【要約】 【課題】小型セキュリティマーク（ＭＳＭ）を効率的に検出するための方法を提供する。

【構成】本発明の方法は、受信された、小型セキュリティマークを含むディジタル画像をサブサンプリングし、解像度の低減された画像を生成し、前記画像に対して最大／最小ポイント検出が実行され、検出された最大／最小ポイント間のロケーション距離に従って、１つ以上のクラスタにグループ分けする。各クラスタグループ構成は、所定のテンプレート構成に適合するかどうかチェックされる。そして適合するクラスタグループ構成について、解像度の低減された画像と受信した画像との間でマークの位置及び形状の検証が実行される。
【特許請求の範囲】
【請求項１】
ドキュメント及び画像内の小型セキュリティマーク形状構成の検出のための方法であって、前記小型セキュリティマークが、データマーク、または、データマークとアンカーマークの組合せを含みうる方法であって、
受信した画像をサブサンプリングすることであって、前記受信した画像が、少なくとも１つの前記小型セキュリティマークの可能な受容物のディジタル表現からなり、前記サブサンプリングが、前記受信した画像の解像度の低減された画像を生成し、
最大／最小ポイント検出を実行し、
前記最大／最小ポイントを、前記最大／最小ポイント間のロケーション距離に従って、少なくとも１つのクラスタにグループ分けし、
グループ構成を、前記クラスタが所定のテンプレート構成に適合するかどうかチェックし、
前記解像度の低減された画像と前記受信した画像との間で、マークの位置及び形状構成を検証するために、形状検証を実行すること、
を含む方法。
【請求項２】
前記グループ構成をチェックすることがさらに、
前記少なくとも１つのクラスタにおけるポイントの数が、前記所定のテンプレートにおけるポイントの数と等しいか否かを判断し、
前記少なくとも１つのクラスタにおけるポイントの数が、前記テンプレートにおけるポイントの数と等しくない場合に、前記クラスタを廃棄し、
前記少なくとも１つのクラスタにおけるポイントの数が、前記テンプレートにおけるポイントの数に等しい場合に、アンカーポイントが前記クラスタ内に定義されているか否かを判断することであって、前記アンカーポイントが、小型セキュリティマーク形状構成内の他のマークとは異なる少なくとも１つの属性を有するマークを備え、
前記アンカーポイントが定義されていない場合、前記少なくとも１つのクラスタにおけるポイント間の距離を、前記所定のテンプレートにおけるポイント間の距離と照合し、
前記アンカーポイントが定義されている場合、前記クラスタ内の前記アンカーポイントを、前記所定のテンプレートにおけるアンカーポイントと照合し、
前記少なくとも１つのクラスタにおける前記アンカーポイントと残りのマークとの間の距離を計算して、前記距離を結合距離マトリクス内に配置することであって、前記結合距離マトリクスが、前記少なくとも１つのクラスタについてのアンカー及び非アンカー距離を含み、
前記結合距離マトリクスと結合テンプレートマトリクスを比較することであって、前記結合テンプレートマトリクスが、前記所定のテンプレートにおけるポイント間の前記アンカー及び非アンカー距離を記録し、
誤差測定を最小にし、
前記誤差測定が所定のしきい値よりも小さいか否かを判断し、
前記所定のしきい値を超えている場合、前記少なくとも１つのクラスタを廃棄し、
前記所定のしきい値を超えていない場合、前記少なくとも１つのクラスタと前記所定のテンプレートとの一致を検証するための、さらなるテスト動作を実行すること、
を含む、請求項１に記載の方法。
【請求項３】
前記少なくとも１つのクラスタ内のポイント間の距離と、前記所定のテンプレートにおけるポイント間の距離とを照合することが、
前記少なくとも１つのクラスタ内のポイントの数をチェックし、
前記少なくとも１つのクラスタ内のポイント間の距離を計算して、前記距離を距離マトリクス内に配置し、
前記距離マトリクスとテンプレートマトリクスとを比較することであって、前記テンプレートマトリクスが、前記所定のテンプレートにおけるポイント間の距離を記録し、
誤差測定を最小にし、
前記誤差測定が所定のしきい値よりも小さいか否かを判断し、
前記所定のしきい値を超えている場合、前記少なくとも１つのクラスタを廃棄し、
前記所定のしきい値を超えていない場合、前記少なくとも１つのクラスタと前記所定のテンプレートとの一致を検証するための、さらなるテスト動作を実行すること、
を含む、請求項２に記載の方法。
【請求項４】
前記クラスタ内の前記アンカーポイントを前記所定のテンプレートにおける前記アンカーポイントと照合することが、
前記少なくとも１つのクラスタにおけるアンカーポイントの数をチェックし、
前記少なくとも１つのクラスタ内の前記アンカーポイント間の距離を計算して、前記距離をアンカーポイント距離マトリクス内に配置し、
前記アンカーポイント距離マトリクスとテンプレートアンカーポイント距離マトリクスとを比較することであって、前記テンプレートアンカーポイント距離マトリクスが、前記所定のテンプレートにおけるアンカーポイント間の距離を記録し、
誤差測定を最小にし、
前記誤差測定が所定のしきい値よりも小さいか否かを判断し、
前記所定のしきい値を超えている場合、前記少なくとも１つのクラスタを廃棄し、
前記所定のしきい値を超えていない場合、前記少なくとも１つのクラスタと前記所定のテンプレートとの一致を検証するための、さらなるテスト動作を実行すること、
を含む、請求項２に記載の方法。
【発明の詳細な説明】【技術分野】
【０００１】
本発明は、全般的に、偽造防止のための方法及びシステムに関し、より具体的には、ドキュメントまたは画像内の小型セキュリティマークを自動的に検出するシステム及び方法に関する。
【背景技術】
【０００２】
現在の偽造防止システムは、主に、ディジタル画像信号及びドキュメント（文書）への情報（例えば、著作権表示、セキュリティコード、識別情報等）の挿入を可能にする技術である、電子透かしの使用に基づいている。このようなデータは、信号に関連する、または、信号の作者に関する情報（例えば、名前、場所等）を表すビットからなる群（グループ）に含まれることができる。画像のための最も一般的な電子透かし技術は空間または周波数領域で機能し、透かしを付加し、この透かしを信号から除去するのに様々な空間及び周波数領域技術を用いる。
【０００３】
空間電子透かしの場合、最も簡単な方法は、階調またはカラー画像内の選択した画素の最下位のビットを反転させることを含む。この方法は、画像が人のよる変更、または、ノイズの多い変更にさらされない場合にのみ、良好に機能する。よりロバストな透かしは、透かしが紙に付加されるのと同様の方法で、画像に埋め込むことができる。このような方法は、画像の領域上に透かし記号を重ね合わせ、画像内の変更された多様な画素値に対して、透かし用の一定の強度値を付加することができる。この結果生じる透かしは、透かし強度の（それぞれ、大または小の）値により、可視または不可視とすることができる。
【０００４】
空間透かしは、色分解を用いて適用することもできる。この手法においては、透かしは、色バンドのうちの１つのみで現れる。この種の透かしは、目で見えにくく、通常の観察状態では検出するのが困難である。しかし、画像の色が、印刷またはゼログラフィ（複写）のために分離されると、透かしはすぐに現れる。このことは、透かしを色バンドから除去することができない限り、このドキュメントをプリンタに対して無意味なものにする。この手法は、ジャーナリストが透かしの入っていないバージョンをフォトストックハウス（ｐｈｏｔｏ−ｓｔｏｃｋｈｏｕｓｅ）から購入する前にディジタル写真を調べるために、商業的に用いられている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
電子透かし技術を利用することに関して、いくつかの欠点がある。透かしを取り出すために、一般に、抽出ハードウェアおよび／またはソフトウェアが用いられる。電子透かしは、通常、相当大きな専有面積を有するため、電子透かしの読取りに用いられる検出器は、多くの場合、かなりのバッファリング容量を必要とし、これは検出コストの増大につながる。
【０００６】
代替的な偽造防止システム、すなわち、小型セキュリティマークは、この問題を改善するのに用いることができる。小型セキュリティマーク（Ｍｉｎｉａｔｕｒｅ Ｓｅｃｕｒｉｔｙ Ｍａｒｋ；ＭＳＭ）は、特定の形状構成を形成する小さな、実質的に不可視のマークで構成されている。ＭＳＭは、保護すべきドキュメントまたは画像に埋め込むことができる。ドキュメントまたは画像がスキャンされ、処理されてプリンタへ送られると、画像ングシステム内のＭＳＭ検出器は、埋め込まれたＭＳＭマークを認識して、偽造の企てを無効にすることができる。ＭＳＭは、非常にシンプルで安価な検出器のみを必要とするという点で、透かし等の現存する技術に優る利点を有する。従って、ＭＳＭは、費用対効果の高い方法で多くのデバイスに適用することができる。
【０００７】
本発明はこのような小型セキュリティマーク（ＭＳＭ）を効率的に検出するための方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様は、上述した背景説明で述べた問題及び本願明細書に引用した技術に対する改善された解決法を提供する。これらの例には、ドキュメント及び画像内の小型セキュリティマーク形状の検出のための改善された方法が示されており、上記小型セキュリティマークは、データマーク、または、データマークとアンカーマークの組合せを含んでもよい。上記方法は、小型セキュリティマークの可能な受容物のディジタル表現である受信画像をサブサンプリングして、受信した画像の解像度の低減された画像を生成することを含む。最大／最小ポイント検出が実行され、上記最大／最小ポイントは、上記最大／最小ポイント間のロケーション距離に従って、１つ以上のクラスタにグループ分けされる。グループ構成は、上記クラスタが、所定のテンプレート構成に適合するかどうかチェックされる。そして、解像度の低減された画像と受信した画像との間でマークの位置及び形状構成を検証照合するために、形状検証が実行される。
【０００９】
代替的態様としては、ドキュメント及び画像内の小型セキュリティマーク形状構成の検出のためのシステムが開示されている。上記小型セキュリティマークは、データマーク、または、データマークとアンカーマークの組合せを含んでもよい。上記システムは、小型セキュリティマークの可能な受容物のディジタル表現である受信画像をサブサンプリングして、受信した画像の解像度の低減された画像を生成する。そして、上記システムは、最大および／または最小ポイントを検出し、これらのポイントは、上記最大および／または最小ポイント間のロケーション距離に従って、１つ以上のクラスタにグループ分けされる。上記システムは、上記クラスタが所定のテンプレート構成に適合するかどうか、グループ構成をチェックする。そして、解像度の低減された画像と受信した画像との間で、マークの位置及び形状構成を検証するために、形状検証が実行される。
【００１０】
また別の態様としては、プログラムコードがコンピュータによって実行されると、コンピュータに、ドキュメント及び画像内の小型セキュリティマーク形状構成の検出のための方法ステップを実行させる、コンピュータ可読プログラムコードが格納されたコンピュータ可読記憶媒体が開示されている。小型セキュリティマークは、データマーク、または、データマークとアンカーマークの組合せを含んでもよい。上記方法は、小型セキュリティマークの可能な受容物のディジタル表現である受信画像をサブサンプリングして、上記受信した画像の解像度の低減された画像を生成することを含む。最大／最小ポイント検出が実行され、上記最大／最小ポイントは、上記最大／最小ポイント間のロケーション距離に従って、１つ以上のクラスタにグループ分けされる。グループ構成は、上記クラスタが、所定のテンプレート構成に適合するかどうかチェックされる。そして、解像度の低減された画像と受信した画像との間でマークの位置及び形状構成を検証するために、形状検証が実行される。
【００１１】
上記態様において、前記グループ構成をチェックすることは、さらに、前記少なくとも１つのクラスタにおけるポイントの数が、前記所定のテンプレートにおけるポイントの数と等しいか否かを判断し、前記少なくとも１つのクラスタにおけるポイントの数が、前記テンプレートにおけるポイントの数と等しくない場合に、前記クラスタを廃棄し、前記少なくとも１つのクラスタにおけるポイントの数が、前記テンプレートにおけるポイントの数に等しい場合に、アンカーポイントが前記クラスタ内に定義されているか否かを判断することであって、前記アンカーポイントが、小型セキュリティマーク形状構成内の他のマークとは異なる少なくとも１つの属性を有するマークを備え、前記アンカーポイントが定義されていない場合、前記少なくとも１つのクラスタにおけるポイント間の距離を、前記所定のテンプレートにおけるポイント間の距離と照合し、前記アンカーポイントが定義されている場合、前記クラスタ内の前記アンカーポイントを、前記所定のテンプレートにおけるアンカーポイントと照合し、前記少なくとも１つのクラスタにおける前記アンカーポイントと残りのマークとの間の距離を計算して、前記距離を結合距離マトリクス内に配置することであって、前記結合距離マトリクスが、前記少なくとも１つのクラスタについてのアンカー及び非アンカー距離を含み、前記結合距離マトリクスと結合テンプレートマトリクスを比較することであって、前記結合テンプレートマトリクスが、前記所定のテンプレートにおけるポイント間の前記アンカー及び非アンカー距離を記録し、誤差測定を最小にし、前記誤差測定が所定のしきい値よりも小さいか否かを判断し、前記所定のしきい値を超えている場合、前記少なくとも１つのクラスタを廃棄し、前記所定のしきい値を超えていない場合、前記少なくとも１つのクラスタと前記所定のテンプレートとの一致を検証するための、さらなるテスト動作を実行すること、を含んでよい。
【００１２】
また、前記少なくとも１つのクラスタ内のポイント間の距離と、前記所定のテンプレートにおけるポイント間の距離とを照合することは、前記少なくとも１つのクラスタ内のポイントの数をチェックし、前記少なくとも１つのクラスタ内のポイント間の距離を計算して、前記距離を距離マトリクス内に配置し、前記距離マトリクスとテンプレートマトリクスとを比較することであって、前記テンプレートマトリクスが、前記所定のテンプレートにおけるポイント間の距離を記録し、誤差測定を最小にし、前記誤差測定が所定のしきい値よりも小さいか否かを判断し、前記所定のしきい値を超えている場合、前記少なくとも１つのクラスタを廃棄し、前記所定のしきい値を超えていない場合、前記少なくとも１つのクラスタと前記所定のテンプレートとの一致を検証するための、さらなるテスト動作を実行すること、を含んでよい。
【００１３】
また、前記クラスタ内の前記アンカーポイントを前記所定のテンプレートにおける前記アンカーポイントと照合することは、前記少なくとも１つのクラスタにおけるアンカーポイントの数をチェックし、前記少なくとも１つのクラスタ内の前記アンカーポイント間の距離を計算して、前記距離をアンカーポイント距離マトリクス内に配置し、前記アンカーポイント距離マトリクスとテンプレートアンカーポイント距離マトリクスとを比較することであって、前記テンプレートアンカーポイント距離マトリクスが、前記所定のテンプレートにおけるアンカーポイント間の距離を記録し、誤差測定を最小にし、前記誤差測定が所定のしきい値よりも小さいか否かを判断し、前記所定のしきい値を超えている場合、前記少なくとも１つのクラスタを廃棄し、前記所定のしきい値を超えていない場合、前記少なくとも１つのクラスタと前記所定のテンプレートとの一致を検証するための、さらなるテスト動作を実行すること、を含んでよい。
【発明を実施するための最良の形態】
【００１４】
自動ＭＳＭ検出システムは、効率的で低コストであるという利点を有する。ＭＳＭは、３つの点で画像内容及びノイズと区別される。すなわち、ＭＳＭは、画像背景とは異なる相当の色差を有し、各ＭＳＭは、所定の形状（円、正方形等）を有し、ＭＳＭは、特定の予め決められたパターンを形成する。階層的ＭＳＭの場合、パターンは、２つの層、すなわち、固定パターンを有する下部層と、下部層グループの相対位置及び方向を指定する上部層とに分解することができる。本願明細書における議論では、ＭＳＭという用語は、階層的ＭＳＭ及び非階層的ＭＳＭの両方を含むものとする。ＭＳＭの構成及び特徴は、共に本出願の同じ譲受人に譲渡され、かつ全体を本願明細書に組み込む、Ｆａｎの同時係属中の米国特許出願第１１／３１７，７６８号明細書（「小型セキュリティマークを使用した偽造防止（“Ｃｏｕｎｔｅｒｆｅｉｔ Ｐｒｅｖｅｎｔｉｏｎ Ｕｓｉｎｇ Ｍｉｎｉａｔｕｒｅ Ｓｅｃｕｒｉｔｙ Ｍａｒｋｓ”）」）と、Ｆａｎの米国特許出願第１１／４７２，６９５号明細書（「階層的小型セキュリティマーク（“Ｈｉｅｒａｒｃｈｉｃａｌ Ｍｉｎｉａｔｕｒｅ Ｓｅｃｕｒｉｔｙ Ｍａｒｋｓ”）」）とに記載されている。
【００１５】
本システムは、アナライザと、マーク形状情報を記憶するデータベースとを含む。本検出方法は、効率的に分析することができる粗い画像を準備するためのサブサンプリングを含む。粗い画像を用い、マークと背景との間の色差等のマーク特徴を利用して最大／最小ポイントが検出される。対象とするマークからなるグループが分離され、マークが所定のパターンを形成するか否かを判断するために評価される。そして、マークの形状が検証される。
【００１６】
様々なコンピュータ環境は、ＭＳＭを検出する上記システム及び方法がその上に存在するネットワークをサポートする能力を組み込むことができる。以下の議論は、上記方法及びシステムを実施することができる適切なコンピュータ環境の簡潔で全般的な説明を提供しようとするものである。必要ではないが、上記方法及びシステムは、単一のコンピュータによって実行されるプログラムモジュール等のコンピュータが実行可能な命令の一般的な文脈で説明する。一般的に、プログラムモジュールは、特定のタスクを実行し、または、特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含む。また、当業者は、上記方法及びシステムを、携帯端末、マルチプロセッサシステム、マイクロプロセッサベースまたはプログラム可能な（プログラマブル）家庭用電化製品、ネットワーク型ＰＣ、ミニコンピュータ、メインフレームコンピュータ等を含む他のコンピュータシステム構成を用いて実施できることを正しく認識するであろう。
【００１７】
図１を参照すると、ドキュメントおよび／または画像内のＭＳＭを検出するシステムの一つの例示的な実施形態の機能ブロック図が描かれている。本願明細書において用いるセキュリティマークは、画像、グラフィック、写真、ドキュメント、テキストの本体等の受容物に適用することができる任意のマーク（例えば、凹型（depression）、圧痕（impression）、浮き彫り、オーバーレイ等）とすることができる。セキュリティマークは、検出することができ、抽出することができ、および／または解釈することができる情報を含むことができる。このような情報は、セキュリティマークに含まれている情報が適切であることを確認（検証）することにより、偽造を防止するのに利用されることができ、それによって、セキュリティマークが適用された受容物の信頼性を確認することができる。
【００１８】
一つの実施例において、セキュリティマークは、少なくとも１つのデータマークと、少なくとも２つのアンカーマークとを含むＭＳＭ構成を有する。ＭＳＭは、様々な色及び形状を有してもよい。具体的には、１つのＭＳＭ構成内のアンカーマークは、上記少なくとも１つのデータマークとは異なる少なくとも１つの属性（例えば、サイズ、形状、色等）を有する。これにより、アンカーマークは、データマークと全く同じ属性を有することはない。
【００１９】
１つ以上のデータマークの位置、サイズおよび／または形状は、データマークに含まれる情報を決定することができる。例えば、ＭＳＭ構成は、１９のデータマークと、２つのアンカーマークとを含むことができる。アンカーマーク及びデータマークのサイズ、形状及び色は、アンカーマークを互いに区別することができるため、知ることができる。また、各ＭＳＭ構成内のアンカーマークの位置は互いに知ることができ、１つ以上のデータマークに対しても知ることができる。このようにして、ＭＳＭ構成に関連する１つ以上のアルゴリズムを用いて、ＭＳＭ構成に情報を記憶することができ、また、ＭＳＭ構成から情報を抽出することができる。１つ以上のアルゴリズムは、マークの位置、サイズ、形状及び色のうちの少なくとも１つを用いてＭＳＭ構成にデータを記憶することができ、および／またはＭＳＭ構成からデータを抽出することができる。
【００２０】
アンカーマークは、ＭＳＭ構成の検出及び抽出に用いられるコンピュータ（計算）処理上のオーバーヘッドの量を制限するのに用いることができる。例えば、画像（及びそれに適用されるＭＳＭ構成）の回転、シフトおよび／または縮尺が分からないため、より大きな検出要件が必要となる可能性がある。その結果として、マークの数が増加するにつれて、計算の複雑さが指数関数的に増大する可能性がある。一般的に、アンカーマークは、ＭＳＭ構成の位置の素早い判断を可能にすることができる。具体的には、ＭＳＭ構成内の少なくとも１つのデータマークのアンカーマークに対する位置は、素早く判断することができる。このようにして、余計な計算オーバーヘッドを軽減することができる。また、ＭＳＭ構成は、電子透かしよりも小さな専有面積で実装でき、このことは、バッファリングストレージ（容量）要件を低くすることができる。これは、より多数のデータマークおよび／またはアンカーマークを用いる場合に特に有益である。一つの態様において、検出器はまずアンカーマークを識別し、次にアンカーマークを用いて、位置、方向及び縮尺パラメータを判断する。これらのパラメータは、データマークを線形計算の複雑性（計算量）で検出するために適用することができる。
【００２１】
図１に示すように、本発明のシステムは、ＭＳＭ検出（抽出）モジュール１３０と、アルゴリズム格納部１１０と、解釈モジュール１６０とを含む。これらのデバイスは、ダイレクトシリアル接続等の、データの伝送を可能にするどのような種類のリンクであってもよいデータ通信リンクを介して結合されている。
【００２２】
検出モジュール１３０は、１つ以上のアルゴリズムを用いて、１つ以上のセキュリティマークに含まれる情報を抽出することができる。アルゴリズムは、特定のセキュリティマークによって表されるデータを解釈するために、１つ以上の公式、等式、方法等を含むことができる。一つの実施例において、セキュリティマークは、データが２つ以上のアンカーマークと１つ以上のデータマークとによって表されるＭＳＭ構成である。検出モジュール１３０はアナライザ（分析部）１４０を含み、アナライザ１４０は、ＭＳＭ構成が特定の位置に存在することを確認するために、データマーク同士の互いに対する位置、および／またはデータマークの２つ以上のアンカーマークに対する位置、ならびにアンカーマーク同士の互いに対する位置を解析する。マークのサイズ、形状、色、方向等も、１つ以上のＭＳＭ構成に含まれる情報を抽出するために解析することができる。また、検出モジュール１３０はデータベース１５０を含み、データベースは各ＭＳＭについてのマーク形状情報（円形、正方形等）を含む。
【００２３】
アルゴリズム格納部１１０は、後の使用のための１つ以上のアルゴリズムを格納し、編成し、編集し、視覚化（表示）し、および検索するのに用いることができる。一つの態様において、検出モジュール１３０は、アルゴリズム格納部１１０から１つ以上のアルゴリズムを取得して、ＭＳＭ構成に含まれる情報を判断することができる。別の態様においては、検出モジュール１３０は、１つ以上のセキュリティマークから情報を抽出し、そのような情報を、後の使用のためにアルゴリズム格納部１１０へ転送するために適切なアルゴリズム、手法等を判断することができる。
【００２４】
解釈実行モジュール１６０は、検出モジュール１３０によって１つ以上のセキュリティマークから抽出されたデータに関する意味を判断することができる。このような判断は、セキュリティマークの位置、セキュリティマークが施されている受容物、システムの位置、１つ以上の所定の条件等の１つ以上の条件に基づいて行われる。加えて、ルックアップテーブル、データベース等を解釈モジュール１６０が用いて、セキュリティマークから抽出したデータの意味を判断することができる。一つの実施例において、セキュリティマークは、セキュリティマークが施されている受容物に関連する。例えば、データ文字列“５ｊｒｗｍ３８ｆ６ｈｏ”は、１００ドル紙幣と１００ユーロ紙幣とに適用された場合では、異なる意味を有する可能性がある。
【００２５】
ＭＳＭを検出するために実行される特定の方法は、一連のフローチャートを参照して以下に説明するステップからなる。これらのフローチャートは、上記方法が、コンピュータが実行可能な命令で形成されたコンピュータプログラムを構成する実施形態を示す。フローチャートを参照して上記方法を説明することにより、当業者は、このような命令を含むソフトウェアプログラムを開発して、上記方法をコンピュータシステム上で実行できる。そのようなプログラムを書くために用いられる言語は、Fortran等の手続き型、または、Ｃ＋＋等のオブジェクトベースとすることができる。当業者は、これらのステップの変更または組合せを、本願明細書の開示の範囲を逸脱することなく実行することができることを理解するであろう。
【００２６】
次に、図２について説明すると、フローチャートは、ドキュメントおよび／または画像内のＭＳＭを検出する方法の例示的な実施形態を示す。ステップ２１０において、サブサンプリングが実行されて、元の画像の解像度を低減したバージョンが生成され、このバージョンは、より効率的に解析することができる。このサブサンプリング及びこれに関連するローパスプリスムージング（低域事前平滑化）は、ＭＳＭマークを不鮮明なスポットに変えて、その形状情報を失わせる。サブサンプリング係数は、結果として生じるマークのサイズが、解像度の低減された画像内の約１つの画素に変わるように選択される。サブサンプリングプロセスは周知であり、例えば、Ａ．Ｒｏｓｅｎｆｅｌｄ及びＡ．Ｃ．Ｋａｋによる“Ｄｉｇｉｔａｌ Ｐｉｃｔｕｒｅ Ｐｒｏｃｅｓｓｉｎｇ（ディジタル画像処理）”（Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ、１９８２年）等のテキストに載っている。最大／最小ポイント（最大／最小画素値を有する地点）検出は、ステップ２２０で実行され、解像度の低減された画像を、各ウィンドウが複数の画素を有する状態で、ばらばらのウィンドウに分割する。各ウィンドウにおいて、最大および／または最小ポイントが、可能性があるＭＳＭロケーションとして検出される。ＭＳＭマークの色により、異なる色空間に対して処理を行うことができ、最大または最小のいずれかのポイントを識別することができる。例えば、マークが、Ｌ*ａ*ｂ*のＬ*成分（ＣＩＥ（国際照明委員会）色度標準）色空間内の背景よりも暗い場合、Ｌ*内の最小値画素がチェックされうる。ウィンドウのサイズは、同じウィンドウ内に２つのマークが現れないという制約下で、可能な限り大きくなるように選定される。
【００２７】
ステップ２３０において、上記システムは、最大／最小ポイントのグループ分けを実行し、このグループ分けはステップ２２０で検出されたポイントを、それらのロケーション距離に従ってクラスタにグループ分けすることを含む。その距離が所定のしきい値よりも小さい２つのポイントは、同じグループ内にあると考えられ、クラスタの候補である。グループ構成のチェックはステップ２４０において、ステップ２３０で得られたグループが所定のテンプレート構成に適合（マッチング）するかどうかチェックされることで行われ、以下に図３を参照してより詳細に説明する。ステップ２５０において、システムは、解像度を低減したバージョンではなく、元の解像度で形状検証を実行する。グループ構成のチェックを満たすグループ内の（解像度の低減された画像の）各ポイントから、元の画像における対応する位置が見出される。円形等の回転不変形状を有するマークの場合には、テンプレートマッチングを適用することができる。そうでない場合、テンプレート（または、マーク）は、まず、グループの配向方向に従って回転させなければならない。
【００２８】
次に、図３及び図４について説明すると、フローチャートは、グループ構成のチェックのための例示的な実施形態を示しており、このチェックは、最大／最小ポイントのグループ分けによって得られたグループを、各グループについて所定のテンプレート構成と照合（マッチング）する。各グループに対して、上記システムはステップ３１０において、グループ内のポイントの数がテンプレートにおけるポイントの数と等しいか否かを判断する。等しくない場合、ステップ３２０においてそのグループは廃棄される。残りのグループに対してステップ３３０において、アンカーポイントが割当てられているか否かに関して判断が行われる。１つのグループに含まれるポイントの数が比較的小さい階層的ＭＳＭの場合には一般的であるように、アンカーポイントが割当てられていない場合には、以下に図４に関してより詳細完全に説明するように、ステップ３４０においてグループ内のポイント間の距離をテンプレートにおけるポイント間の距離と照合する。
【００２９】
次に、図４を参照すると、上記グループ内のポイントと、上記テンプレート内のポイントとを照合する（上記ステップ３４０）方法がより詳細に記載されている。ステップ４１０において、グループ内のポイントの数がチェックされる。ステップ４２０において、グループ内のポイント間の距離が計算され、Ｎ×ＮマトリクスＤとして作表され、ここで、Ｎはグループ内のポイントの数であり、Ｄ（ｉ，ｊ）は、ポイントｉとポイントｊとの間の距離である。ステップ４３０において、マトリクスＤは、テンプレートにおけるポイント間の距離を記録する別のＮ×ＮマトリクスであるマトリクスＴと比較される。マッチングは、例えば以下のような誤差測定によって遂行される。
【００３０】
Ｅ１＝Ｍｉｎi,j［Σm,n>m｜Ｄ（ｉ，ｊ）−Ｔ（ｍ，ｎ）｜］
【００３１】
マトリクスは対称であり、かつ対角線上の値は常に０であるため、指数ｍは、１からＮまでにわたり、指数ｎは、Ｍ＋１からＮまでにわたる。上記システムはステップ４４０において、Ｅ１が所定のしきい値よりも小さいか否かを判断する。しきい値を超えていない場合、グループは、ステップ４５０においてテスト続行される。そうでない（超えている）場合、ステップ４６０においてそのグループは廃棄される。階層的ＭＳＭの場合、定義された関係に基づいた処理により、グループが所定の特定の関係を構成するか否かを判断するために、追加的なテストが必要である。例えば、ＭＳＭが３つの同一パターンのグループを必要とし、３つの同一パターンのグループのうちの２つが同じ方向であり、かつ３つめのグループが９０度回転した状態を要件とする場合、グループのうちのいずれかがθ、θ、θ＋９０°のパターンを含むか否かを判断するために、グループの方向が評価されることになる。
【００３２】
図３に戻って、アンカーポイントが定義されている場合（これは大きなグループの場合に一般的である）、グループ内のアンカーポイントを上記テンプレートにおけるアンカーポイントと照合する。アンカーポイントは通常、グループ内のその他のポイント（非アンカーポイント）と色が異なり、これにより容易に識別可能である。そして、ステップ３５０において、グループ内のアンカーポイントをテンプレートにおけるアンカーポイントと照合することで、図４の方法を、グループ内の全てのポイントにではなくアンカーポイントにのみ適用されることを除いて、適用する。グループ及びテンプレートにおけるアンカーポイントを照合した後、ステップ３６０において、グループ内のアンカーポイントと、その他のポイントとの間の距離が計算される。それらの距離は、Ｋ×ＭマトリクスＤ１に作表され、この場合、Ｋ及びＭは、それぞれアンカーポイント及び非アンカーポイントの数であり、Ｄ（ｍ，ｉ）は、ポイントｍとポイントｉとの間の距離である。ステップ３７０においてマトリクスＤ１は、テンプレートについてアンカー及び非アンカーの距離を記録するマトリクスＴ１と照合される。この例示的な実施形態において、マッチングは、例えば以下のように、誤差測定を最小化することによって遂行される。
【００３３】
Ｅ２＝Ｍｉｎi［Σm,n｜Ｄ（ｍ，ｉ）−Ｔ（ｍ，ｎ）｜］
【００３４】
ステップ３８０において、上記システムはＥ２が所定のしきい値よりも小さいか否かを判断する。誤差がしきい値よりも小さい場合には、そのグループはステップ３９０において、テスト続行されることになる。そうでない場合、そのグループはステップ３２０において廃棄される。
【図面の簡単な説明】
【００３５】
【図１】ドキュメントおよび／または画像内のＭＳＭの検出のためのシステムの一つの例示的な実施形態の機能ブロック図である。
【図２】ドキュメントおよび／または画像内のＭＳＭを検出する方法の一つの例示的な実施形態の概要を示すフローチャートである。
【図３】グループ構成チェックの一つの例示的な実施形態の概要を示すフローチャートである。
【図４】グループ内のＭＳＭロケーションポイントをテンプレート構成と照合する方法の一つの例示的な実施形態の概要を示すフローチャートである。
【符号の説明】
【００３６】
１２０ 検出コンポーネント
１３０ 抽出モジュール
１４０ アナライザ（分析部）
１５０ データベース
１６０ 解釈モジュール
【出願人】 【識別番号】５９６１７０１７０
【氏名又は名称】ゼロックス コーポレイション
【氏名又は名称原語表記】ＸＥＲＯＸ ＣＯＲＰＯＲＡＴＩＯＮ
【出願日】 平成１９年８月６日（２００７．８．６）
【代理人】 【識別番号】１０００７９０４９
【弁理士】
【氏名又は名称】中島 淳

【識別番号】１０００８４９９５
【弁理士】
【氏名又は名称】加藤 和詳
【公開番号】 特開２００８−４８４００（Ｐ２００８−４８４００Ａ）
【公開日】 平成２０年２月２８日（２００８．２．２８）
【出願番号】 特願２００７−２０４５４６（Ｐ２００７−２０４５４６）