(57)【要約】【課題】グラフィカルバーコード（１６）（すなわち、埋め込み情報（１４）を符号化した、目立たないグラフィックス変調を含む画像）を自動的に抽出するシステムおよび方法を提供する。【解決手段】この自動抽出方式によれば、埋め込み情報（１４）を符号化した情報包含グラフィックス変調を保存するとともに、複合画像（２２）に含まれるマーキング等の汚損アーチファクトを回避するように、グラフィカルバーコード（１６）を複合画像（２６）から切り離すことができる。得られる抽出グラフィカルバーコード（５０）は、外部からのマーキングおよび画像の汚損等のノイズに特に敏感でありうる復号化システム（４６）の要件に適合したフォーマットに容易に処理することができる。加えて、この自動抽出方式は、検出の失敗および不正確な検出に堅牢に対処する
2004533071.tif 000002
【特許請求の範囲】
【請求項１】
入力画像（２６）からグラフィックス符号化された情報（１４）を含むグラフィカルバーコード（５０）を抽出する方法であって、
検出されたグラフィカルバーコード候補（５０）の推定位置座標に基づいて、前記入力画像（２６）から非グラフィカルバーコード領域をトリミングすることであって、それによって、復号化するトリミング済グラフィカルバーコード候補（５０）を生成するトリミングすること
を含むグラフィカルバーコードを抽出する方法。
【請求項２】
検出されたグラフィカルバーコード候補（５０）の推定位置座標に基づいてトリミングする前に、前記入力画像（２６）をクロッピングすることであって、それによって、前記検出されたグラフィカルバーコードを含む包含画像領域が生成されるクロッピングすること
をさらに含む請求項１記載のグラフィカルバーコードを抽出する方法。
【請求項３】
前記検出されたグラフィカルバーコード候補（５０）の角度向きを計算すること
をさらに含む請求項１記載のグラフィカルバーコードを抽出する方法。
【請求項４】
前記非グラフィカルバーコード領域は、前記検出されたグラフィカルバーコード候補（５０）の前記計算された角度向きに対応する直交軸に沿って輝度値を合算することによって得られる輝度ヒストグラムプロファイル（１１２、１１４）に基づいてトリミングされる
請求項３記載のグラフィカルバーコードを抽出する方法。
【請求項５】
前記非グラフィカルバーコード領域は、しきい値を前記輝度ヒストグラムプロファイル（１１２、１１４）に適用することに基づいてトリミングされる
請求項４記載のグラフィカルバーコードを抽出する方法。
【請求項６】
前記非グラフィカルバーコード領域は、予期されるグラフィカルバーコードの次元と前記輝度ヒストグラムプロファイル（１１２、１１４）との比較に基づいてトリミングされる
請求項４記載のグラフィカルバーコードを抽出する方法。
【請求項７】
前記非グラフィカルバーコード領域をトリミングする前に、前記検出されたグラフィカルバーコード候補（５０）をデスキューすることをさらに含む
請求項３記載のグラフィカルバーコードを抽出する方法。
【請求項８】
前記入力画像（２６）を回転させ、該回転された入力画像を処理することであって、それによって、前記回転前にグラフィカルバーコード候補（５０）が前記入力画像（２６）において検出されないことに応答してグラフィカルバーコード候補（５０）が検出される、回転させ、該回転された入力画像を処理すること
をさらに含む請求項１記載のグラフィカルバーコードを抽出する方法。
【請求項９】
第１のトレーニングサンプルに基づいて前記入力画像（２６）において前記グラフィカルバーコード候補（５０）が検出されないことに応答して、第２のトレーニングサンプルに基づいて、グラフィカルバーコード候補（５０）を検出すること
をさらに含む請求項１記載のグラフィカルバーコードを抽出する方法。
【請求項１０】
前記第２のトレーニングサンプルは前記第１のトレーニングサンプルを回転させたものである
請求項９記載のグラフィカルバーコードを抽出する方法。
【請求項１１】
抽出された第１のグラフィカルバーコード候補（５０）が前記グラフィカルバーコード（１６）に対応しないという決定に応答して、前記入力画像において検出された第２のグラフィカルバーコード候補（５０）を抽出すること
をさらに含む請求項１記載のグラフィカルバーコードを抽出する方法。
【請求項１２】
前記トリミング済グラフィカルバーコード候補（５０）を解像度スケーリングすることを
さらに含む請求項１記載のグラフィカルバーコードを抽出する方法。
【請求項１３】
入力画像（２６）からグラフィックス符号化された情報（１４）を含むグラフィカルバーコード（５０）を抽出するシステムであって、グラフィカルバーコード抽出器（４４）
を備え、
該グラフィカルバーコード抽出器（４４）は、検出されたグラフィカルバーコード候補（５０）の推定位置座標に基づいて前記入力画像（２６）から非グラフィカルバーコード領域をトリミングして、復号化するトリミング済グラフィカルバーコード候補（５０）を生成するように構成される
グラフィカルバーコードを抽出するシステム。
【請求項１４】
前記グラフィカルバーコード抽出器（４４）は、検出されたグラフィカルバーコード候補（５０）の推定位置座標に基づいてトリミングする前に、前記入力画像（２６）をクロッピングして、前記検出されたグラフィカルバーコードを含む包含画像領域を生成するように構成される
請求項１３記載のグラフィカルバーコードを抽出するシステム。
【請求項１５】
前記非グラフィカルバーコード領域は、前記検出されたグラフィカルバーコード候補（５０）について計算された角度向きに対応する直交軸に沿って輝度値を合算することによって得られる輝度ヒストグラムプロファイル（１１２、１１４）に基づいてトリミングされる
請求項１３記載のグラフィカルバーコードを抽出するシステム。
【請求項１６】
前記グラフィカルバーコード抽出器（４４）は、前記非グラフィカルバーコード領域をトリミングする前に、前記検出されたグラフィカルバーコード候補（５０）をデスキューするように構成される
請求項１３記載のグラフィカルバーコードを抽出するシステム。
【請求項１７】
前記グラフィカルバーコード抽出器（４４）は、回転前にグラフィカルバーコード候補（５０）が前記入力画像（２６）において検出されないことに応答して、前記入力画像（２６）を回転させ、該回転された入力画像を処理してグラフィカルバーコード候補（５０）を検出するように構成される
請求項１３記載のグラフィカルバーコードを抽出するシステム。
【請求項１８】
前記グラフィカルバーコード抽出器（４４）は、第１のトレーニングサンプルに基づいて前記入力画像（２６）においてグラフィカルバーコード候補（５０）が検出されないことに応答して、第２のトレーニングサンプルに基づいてグラフィカルバーコード候補（５０）を検出するように構成される
請求項１３記載のグラフィカルバーコードを抽出するシステム。
【請求項１９】
前記グラフィカルバーコード抽出器（４４）は、抽出された第１のグラフィカルバーコード候補（５０）が前記グラフィカルバーコード（１６）に対応しないという決定に応答して、前記入力画像（２６）において検出された第２のグラフィカルバーコード候補（５０）を抽出するように構成される
請求項１３記載のグラフィカルバーコードを抽出するシステム。
【請求項２０】
コンピュータ可読媒体に存在し、コンピュータ可読命令を含むコンピュータプログラムであって、前記コンピュータ可読命令は、コンピュータに、
検出されたグラフィカルバーコード候補（５０）の推定位置座標に基づいて、前記入力画像（２６）から非グラフィカルバーコード領域をトリミングさせて、復号化するトリミング済グラフィカルバーコード候補（５０）を生成させる
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフィカルバーコードを自動的に抽出するシステムおよび方法に関する。
【０００２】
［関連出願の相互参照］
本願は、参照により本明細書にそれぞれ援用される以下の同時係属中の出願に関連する。
Doron Shaked他による「A Method and Apparatus for Generating and Decoding a Visually Significant Bar Code」と題する２０００年５月２５日出願の米国特許出願第０９／５７９，０７０号、Renato Keshet他による「System and Method for Counterfeit Protection」と題する１９９９年１０月２８日出願の米国特許出願第０９／４２９，５１５号、Jonathan Yen他による「Authenticable Graphical Bar Codes」と題する２０００年１２月１日出願の米国特許出願第０９／７２８，２９２号、およびDoron Shaked他による「Generating and Decoding Graphical Bar Codes」と題する、本願と同日出願の米国特許出願第    号（代理人整理番号１００１６６５６−１）。
【背景技術】
【０００３】
［背景］
一般的なバーコードシンボルは、データ要素またはキャラクタを表す、様々な幅の棒と空間が並列になったパターンである。
棒はバイナリ１のストリングを表し、空間はバイナリ０のストリングを表す。
従来の「一次元」バーコードシンボルは、一次元においてのみ変化する一連の棒と空間を含む。
一次元バーコードシンボルは、比較的小さい情報記憶容量を有する。
「二次元」バーコードは、一次元バーコードシンボルよりも多くの情報を含む機械可読シンボルに対する増えつつあるニーズに応えるために開発された。
二次元バーコードシンボルの情報記憶容量は、バーコードパターンを二次元で変化させることによって一次元バーコードに比して増えている。
一般的な二次元バーコード規格としては、ＰＤＦ４１７、Ｃｏｄｅ１、およびＭａｘｉｃｏｄｅが挙げられる。
一次元および二次元バーコードシンボルは通常、プリントされているバーコードシンボルを電気信号に変換する光学走査技法によって（たとえば、機械的に走査されるレーザービームにより、または自己走査電荷結合素子（ＣＣＤ）により）読み取られる。
電気信号はデジタル化されて復号化され、プリントされているバーコードシンボルに符号化されたデータが復元される。
【０００４】
バーコードは、低情報コンテンツ用途（たとえば、自動価格タグ付けおよび在庫管理）および比較的高情報コンテンツの用途（たとえば、自動郵便読み取りおよび郵便分配システム用に郵便の住所および郵便料金を符号化すること、またプリントされたページの圧縮した内容を符号化すること）を含む様々な用途に使用することができる。
【特許文献１】
米国特許第６０８２６１９号
【特許文献２】
ＥＰ０９６２８８３
【発明の開示】
【０００５】
［概要］
本明細書で使用される場合、「グラフィカルバーコード」という用語は、埋め込み情報を符号化する、目立たないグラフィックス変調を含む画像を広く指す。
【０００６】
本発明は、入力画像からグラフィカルバーコードを自動的に抽出する本発明の方式（システムおよび方法）を特徴とする。
特に、本発明は、埋め込み情報を符号化する情報包含グラフィックス変調を保存するとともに、複合画像に含まれるマーキング等の汚損アーチファクトを回避するように、グラフィカルバーコードを複合画像から切り離せるようにする。
得られる抽出グラフィカルバーコードは、外部からのマーキングおよび画像の汚損等のノイズに特に敏感でありうる復号化システムの要件に適合したフォーマットに容易に処理することができる。
加えて、本発明の自動抽出方式は、検出の失敗および不正確な検出に堅牢に対処する。
【０００７】
本発明の一態様では、検出されたグラフィカルバーコード候補の推定位置座標に基づいて、非グラフィカルバーコード領域が入力画像からトリミングされ、復号化するトリミング済グラフィカルバーコード候補が生成される。
【０００８】
本発明の実施形態は、以下の特徴の１つまたは複数を含みうる。
【０００９】
実施形態によっては、入力画像は、検出されたグラフィカルバーコード候補の推定位置座標に基づいてトリミングする前にクロッピングされ、検出されたグラフィカルバーコードを含む包含画像領域が生成される。
【００１０】
実施形態によっては、検出されたグラフィカルバーコード候補の角度向きが計算される。
非グラフィカルバーコード領域が、検出されたグラフィカルバーコード候補の計算された角度向きに対応する直交軸に沿って輝度値を合算することによって得られる輝度ヒストグラムプロファイルに基づいてトリミングすることができる。
たとえば、非グラフィカルバーコード領域は、しきい値を輝度ヒストグラムプロファイルに適用することに基づいてトリミングすることができる。
非グラフィカルバーコード領域は、予期されるグラフィカルバーコードの次元と輝度ヒストグラムプロファイルとの比較に基づいてトリミングすることもできる。
【００１１】
検出されたグラフィカルバーコード候補は、好ましくは、非グラフィカルバーコード領域がトリミングされる前にデスキューされる。
【００１２】
入力画像が処理されて、グラフィカルバーコード候補が検出されることが好ましい。
回転前に入力画像においてグラフィカルバーコード候補が検出されないことに応答して、入力画像を回転させることができ、回転させた入力画像を処理してグラフィカルバーコード候補を検出することができる。
グラフィカルバーコード候補は、第１のトレーニングサンプルに基づいて入力画像においてグラフィカルバーコード候補を検出されないことに応答して、第２のトレーニングサンプルに基づいて検出することができる。
第２のトレーニングサンプルは、第１のトレーニングサンプルを回転させたものであることができる。
抽出された第１のグラフィカルバーコード候補がグラフィカルバーコードに対応しないという決定に応答して、入力画像中の第２のグラフィカルバーコード候補を抽出することができる。
【００１３】
トリミングされたグラフィカルバーコード候補は、解像度スケーリングすることも可能である。
【００１４】
本発明の他の特徴および利点は、図面および特許請求の範囲を含む、以下の説明から明らかになろう。
【発明を実施するための最良の形態】
【００１５】
［詳細な説明］
以下の説明において、同様の参照番号を使用して同様の要素を識別する。
さらに、図面は例示的な実施形態の主な特徴を図で示すことを意図する。
図面は、実際の実施形態のあらゆる特徴を示すことも、また図示の要素の相対的な寸法を示すことも意図しておらず、一定の比率で描かれたものではない。
【００１６】
図１を参照すると、一実施形態では、グラフィカルバーコードを複合画像中に組み込むシステム１０は、情報１４をグラフィカルバーコード１６中に符号化するように構成されたエンコーダ１２を備える。
エンコーダ１２は、コンピュータまたは他のプログラム可能なプロセッサ上で実行可能な１つまたは複数のプログラムモジュールとして実施することができる。
以下に詳細に説明するように、エンコーダ１２は、情報１４をグラフィックス符号化したものとともに基本画像１８を変調して、グラフィカルバーコード１６を生成する。
基本画像１８は、ロゴ（たとえば、企業ロゴ）、グラフィックス、ピクチャ、テキスト、画像、または視認性を有する任意のパターンを含む任意のグラフィカルパターンであることができる。
情報１４は、テキスト、ピクチャ、画像、ボーダーまたは基本画像１８の背景のグラフィカルデザイン中に埋め込み、グラフィカルバーコード１６を生成することが可能である。
情報１４は、２値画像（たとえば、白黒のドットパターン）、マルチレベル画像（たとえば、グレーレベル画像）、またはマルチレベルカラー画像の形のグラフィカルバーコード１６に埋め込むことができる。
システム１０は、グラフィカルバーコード１６を複合画像２２中に組み込むように構成された文書プロセッサ２０も備える。
文書プロセッサ２０は、従来の文書処理アプリケーションプログラムであってもよく、または他の文書処理アプリケーションプログラムであってもよい。
システム１０は、複合画像２２のハードコピー２６を生成するプリンタ２４を備えることができる。
プリンタ２４は、従来のプリンタ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＬａｓｅｒＪｅｔ（登録商標）プリンタ）であってもよく、または専用ラベルプリント装置であってもよい。
ハードコピー２６は、預金引き出し認可署名のグラフィカルバーコードが記された銀行為替手形（または小切手）、認証証明書のグラフィカルバーコードが記された株券または債券、および料金別納郵便物の証印のグラフィカルバーコードが記された封筒を含む多種多様なプリントされた材料のいずれか１つの形であることができる。
他の実施形態では、複合画像２２は、他のプリントプロセスによってレンダリングすることができる。
たとえば、実施形態によっては、グラフィカルバーコード１６は、文書に物理的に取り付けて複合画像２２を生成しうるタグの形であることができる。
複合画像２２は、電子フォーマットでレンダリングしてもよい。
【００１７】
実施形態によっては、埋め込み情報１４を基本画像１８中に直接埋め込むのではなく、エンコーダ１２は、情報１４から確証となる署名付きのメッセージを生成するようにプログラムすることができ、次にこの署名付きメッセージをグラフィカルバーコード１６中に組み込むことができる。
このような確証となる署名付きメッセージは、Jonathan Yen他による「Authenticable Graphical Bar Codes」と題する２０００年１２月１日出願の米国特許出願第０９／７２８，２９２号に記載の符号化プロセスによって生成することが可能である。
【００１８】
図２Ａおよび図２Ｂを参照すると、Doron Shaked他による「A Method and Apparatus for Generating and Decoding a Visually Significant Bar code」と題する２０００年５月２５日出願の同時係属中の米国特許出願第０９／５７９，０７０号に記載のグラフィックス符号化方式に従って基本画像１８をグラフィックス変調することによって、グラフィカルバーコード１６を生成することができる。
このグラフィックス変調プロセスによれば、基本画像１８が複数のサブマトリックスに分割される（ステップ３０）。
基本画像１８の１つまたは複数の領域が基準目印用に確保される（ステップ３２）。
確保されないサブマトリックスは、選択されたグラフィックス符号化プロセスに基づいて２値バーコードマトリックスに変換される（ステップ３４）。
たとえば、グラフィックス符号化の一実施形態では、図２Ｂに示す２×２ハーフトーンパターン（またはマトリックス）に基づく２ビット符号化プロセスにより、情報１４を２値レベル画像に符号化することができる。
このグラフィックス符号化プロセスによれば、基本画像１８中のサブマトリックスはしきい値処理プロセスおよび２値レベルハーフトーン化プロセスを受ける。
たとえば、一実施形態では、５０％未満のグレーレベルを有する、基本画像１８中のサブマトリックスは、図２Ｂの２５％行にある４つのバーコードマトリックスのうちの１つで符号化される。
少なくとも５０％のグレーレベルを有する、基本画像１８中のサブマトリックスは、図２Ｂの７５％行にある４つのバーコードマトリックスの１つで符号化される。
他の実施形態では、符号化しきい値レベルが５０％よりも大きくても、または小さくてもよい。
基本画像１８のサブマトリックスのレンダリングに使用される特定のバーコードマトリックスが、符号化される情報に基づいて選択される。
たとえば、「１１」を７５％グレーレベルサブマトリックスロケーションに符号化すべき場合、バーコードマトリックス３６がそのサブマトリックスのレンダリングに使用される。
同様に、「０１」を２５％グレーレベルサブマトリックスロケーションに符号化すべき場合、バーコードマトリックス３８がそのサブマトリックスのレンダリングに使用される。
【００１９】
概して、図２Ａおよび図２Ｂのグラフィックス符号化プロセスは、ｎビット符号化マッピングに拡張することが可能である。
但し、ｎは１以上の整数値を有する。
たとえば、一実施形態では、情報は、３×３ハーフトーンパターンに基づいて５ビット符号化プロセスで符号化される。
他の実施形態では、グラフィカルバーコード１６は、Doron Shaked他による「Generating and Decoding Graphical Bar Codes」と題する本願と同日に出願の同時係属中の米国特許出願第    （代理人整理番号１００１６６５６−１）に記載のグラフィックス符号化方式に従って基本画像１８をグラフィックス変調することによって生成することができる。
【００２０】
図３を参照すると、得られる複合画像２２は、多種多様な画像のいずれか１つの形であることができる。
たとえば、この特定の例示的な実施形態では、複合画像２２は覚え書き文書の形である。
グラフィカルバーコード１６は、多種多様な方法のいずれか１つで復号画像２２中に組み込むことができる。
たとえば、グラフィカルバーコード１６は、複合画像２２のどこにあってもよく、またいずれの角度の向きであってもよい、図３の実施形態では、グラフィカルバーコード１６は複合画像２２の右上角に配置され、複合画像２２の正常な（すなわち真っ直ぐな）向きに対して４５度反時計回りに回転している。
グラフィカルバーコード１６は、他の印がない複合画像領域（すなわち、「白色」画像領域）に配置されることが好ましいが、意図的に、または非意図的に、複合画像２２の印のある領域上に配置することも可能である。
実施形態によっては、グラフィカルバーコード１６を、印のない（すなわち白色の）境界領域で取り囲まれた状態で複合画像２２中に取り込むことができ、これによって以下に述べる自動抽出プロセスの正確性および堅牢性が向上するものもある。
グラフィカルバーコード１６のロケーションおよび角度向きは、複合画像２２のハードコピー２６の処理中に変更しうることに留意されたい。
たとえば、時間の経過に伴って、１つまたはいくつかの連続したコピー動作または走査動作で、グラフィカルバーコード１６のロケーション、またはグラフィカルバーコード１６の角度向き、あるいはこれら両方を変更することができる。
【００２１】
図４に示すように、一実施形態では、グラフィカルバーコード１６から情報１４を自動的に抽出するシステム４０は、スキャナ４２、グラフィカルバーコード抽出器４４およびデコーダ４６を備える。
スキャナ４２は、従来のデスクトップ光学スキャナ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＳｃａｎＪｅｔ（登録商標）ポータブルスキャナ）であっても、ポータブルスキャナ（たとえば、米国カリフォルニア州パロアルトに所在のHewlett-Packard社から市販されているＣａｐＳｈａｒｅ（登録商標）スキャナ）であっても、または従来のファクシミリ機であってもよい。
グラフィカルバーコード抽出器４４およびデコーダ４６は、コンピュータまたは他のプログラム可能なプロセッサ上で動作可能な１つまたは複数のプログラムモジュールの形であることができる。
動作にあたり、スキャナ４２はハードコピー２６を読み込んで、デジタル化された走査画像４８を生成する。
グラフィカルバーコード抽出器４４は、走査画像４８内で検出された１つまたは複数のグラフィカルバーコード候補５０のロケーションおよび角度向きを求め、グラフィカルバーコード候補５０を複合画像２２から抽出する。
実施形態によっては、デコーダ４６は、グラフィカルバーコード候補５０と基本画像１８との比較に基づいてグラフィカルバーコード候補５０から情報１４を抽出するものもある。
情報１４が確証となる署名付きメッセージ中に符号化される実施形態では、デコーダ４６は、署名付きメッセージを復号化して復号化メッセージ５２を生成するように構成しうる。
次に、従来の誤り修正コード復号化プロセスを用いて、得られた署名付きメッセージを復号化することができる。
【００２２】
上に説明したように、情報をグラフィカルバーコード１６中に符号化する固有の方法により、復号化プロセスは、外部からのマーキングおよび画像の汚損等のノイズに特に敏感である。
したがって、情報１４をグラフィカルバーコード１６から抽出するためには、たとえば、複合画像２２に含まれるマーキングによるグラフィカルバーコード１６の汚損を回避することによって、情報を含むグラフィックス変調符号化情報１４を保存するように、グラフィカルバーコード１６を複合画像２２から切り離されなければならない。
加えて、抽出されたグラフィカルバーコード１６を、復号化に適したフォーマットに処理しなければならない。
たとえば、実施形態によっては、デコーダ４６がグラフィカルバーコードデータを処理できるようになるには、前もってグラフィカルバーコードにデスキューおよび解像度スケーリングを行わなければならないものもある。
【００２３】
図５〜図１１を参照すると、一実施形態では、グラフィカルバーコード抽出器４４は、以下のようにして複合画像２２から１つまたは複数のグラフィカルバーコード候補を自動的に抽出することができる。
【００２４】
まず図５〜図７を参照すると、グラフィカルバーコード抽出器４４はまず、複合画像２２中のグラフィカルバーコード候補を検出する（図５のステップ６０）。
一実施形態では、検出プロセスは、Renato Keshet他による「System and Method for Counterfeit Protection」と題する１９９９年１０月２８日出願の米国特許出願第０９／４２９，５１５号に記載の画像検出システムによって実施される。
この画像検出システムは、オフライントレーニング手順およびオンライン検出手順を実行するように構成されている。
トレーニング手順は、グラフィカルバーコード１６の１つまたは複数のトレーニングサンプル（ｉ＝０，・・・，Ｌ−１とインデックスが付けられる）から、グラフィカルバーコード１６の検出記述子を含むパラメータファイルを導き出すことを含む。
この検出手順は、パラメータファイルを使用して複合画像２２を処理して、複合画像２２の中の１つまたは複数の領域がグラフィカルバーコード１６に合致するか否かを判定することを含む。
トレーニング手順はトレーニングモジュール６２（図６）によって実施され、検出手順は検出モジュール６４（図８）によって実施される。
【００２５】
図６に示すように、トレーニングモジュール６２は、カーネルテンプレートセレクタ６６およびテンプレートパラメータコンピュータ６８を含む。
カーネルテンプレートセレクタ６６は、カーネルセレクタ７０およびテンプレートセレクタ７２を含む。
カーネルセレクタ７０は、汎用カーネルおよびカスタマイズカーネルのいずれか一方を選択するように構成される。
テンプレートセレクタ７２は、グラフィカルバーコードトレーニングサンプルからカーネル依存テンプレートまたはカーネル独立テンプレートのいずれか一方を抽出するように構成される。
動作にあたり、カーネルおよびテンプレートが選択された後、テンプレートパラメータコンピュータ６８がテンプレートをカーネル上に投影させて投影値を導き出し、これを使用して、オンライン検出手順中に検出モジュール６４が使用すべき間隔数が定められる。
テンプレートパラメータコンピュータ６８は、定められた間隔をパラメータファイルに記憶する。
パラメータファイルは、複数の入力パラメータ、選択されたカーネルの係数および文書パラメータも含む。
カーネルテンプレートセレクタ６６の動作は、以下の表１において識別される入力パラメータに基づいて制御可能である。
【００２６】
【表１】
2004533071.tif 000003
【００２７】
Renato Keshet他による「System and Method for Counterfeit Protection」と題する１９９９年１０月２８日出願の米国特許出願第０９／４２９，５１５号に説明されるように、テンプレートは、グラフィカルバーコードトレーニングサンプルからの循環抽出である。
所与のグラフィカルバーコードトレーニングサンプルを特徴付けるために使用されるテンプレートの数は、オフライントレーニング手順中に選択して、検出速度と検出精度との間で所望のトレードオフを得ることができる。
テンプレートの直径（ピクセル単位）は、積ＮＲによっておおよそ与えられる。
但し、ＮおよびＲはカーネルサイズおよびデシメーションレートそれぞれである。
ＮおよびＲの値は固定であるため、テンプレートは、グラフィカルバーコードトレーニングサンプル内の中心位置によって一意に特徴付けられる。
テンプレートは、画像内に完全に収まっている必要があるため、それぞれの中心の軌跡は画像ドメインを浸食させたものである。
特に、グラフィカルバーコードトレーニングサンプルがａ×ｂの矩形内にある場合、中心軌跡は同軸の（ａ−ＮＲ）×（ｂ−ＮＲ）の矩形である。
本明細書では、この中心軌跡を「サーチウィンドウ」として表される。
実用的な理由から、サーチウィンドウは同軸の（ａ−√２ＮＲ）×（ｂ−√２ＮＲ）の矩形として定義することができる。
これにより、テンプレートを回転したものを計算することができる。
【００２８】
カーネルはＮ×Ｎピクセル画像であり、このＮ×Ｎピクセル画像をオンライン手順中に調べるべき入力画像（たとえば、走査画像４８）との線形重畳に使用して、入力画像がグラフィカルバーコードトレーニングサンプルの複製を含むか否かを判定する。
このような重畳の結果が、オンライン画像検出手順中に検出モジュールによって解析される。
各カーネルが可能な限り円に近いことが好ましい。
２つのタイプのカーネル、すなわち等方性および非等方性がある。
等方性および非等方性カーネルの数は、入力パラメータＫISOおよびＫNONそれぞれによって決まる。
理想的には、等方性カーネルは、向きの角度に依存しない（たとえば、同心環からなる）２Ｄ実関数である。
Renato Keshet他による「System and Method for Counterfeit Protection」と題する１９９９年１０月２８日出願の米国特許出願第０９／４２９，５１５号に説明されているように、サンプル関数を利用してカーネルを導き出すため、等方性カーネルは上で説明した理想的な概念を近似したものとみなされる。
これら等方性カーネルの主な所望の属性は、所与の円形画像を回転させたものすべてを等方性カーネル上に（内積により）投影した場合、その結果は一定である（すなわち、回転角度に依存しない）。
非等方性カーネルは、以下の属性を満たす複雑なカーネルである。
すなわち、
（ａ）非等方性カーネルと所与の円形画像を回転させたものとの間の内積の絶対値が回転角度に依存しない、また
（ｂ）上記内積の位相が、回転角度の倍数に定数を加算したものに等しい。
【００２９】
図７に示すように、特定の例示的な一実施形態では、７つのテンプレート７６（白および黒の円内にある画像部分に対応する）が、グラフィカルバーコードトレーニングサンプル７４に選択される。
本実施形態では、以下の入力パラメータがさらに選択される。
すなわち、２つの等方性カーネル、２つの非等方性カーネル、６４個の回転増分、４×サブサンプリングレート（すなわち、Ｒ＝４）、およびカーネルサイズ９×９ピクセル（すなわち、Ｎ＝９）。
トレーニングモジュール６２による処理後、グラフィカルバーコードトレーニングサンプル７４に対応するグラフィカルバーコード候補を、トレーニングモジュール６２によって生成されるパラメータファイルに基づいて検出モジュール６４によって検出することができる。
【００３０】
図８を参照すると、一実施形態では、検出モジュール６４は、候補セレクタ８０およびジオメトリック検証器８２を含む。
候補セレクタ８０は、オンライン検出手順中に入力画像（たとえば、走査画像４８）およびパラメータファイルを受け取るように構成される。
候補セレクタ８０は、線形整合フィルタ８４およびしきい値処理器８６を含む。
線形整合フィルタ８４は、入力画像の部分を、オフライントレーニング手順中に選択されたカーネル上に投影するように設計される。
次に、得られた投影値が、しきい値処理器８６によって、パラメータファイルに定義されている間隔を使用して比較される。
すべての間隔について比較を満足させる入力画像の部分が、宣言されるテンプレート整合候補である。
これらテンプレート整合候補の座標はジオメトリック検証器８２に送られる。
ジオメトリック検証器８２は、予め定義される基準を使用してテンプレート整合候補をグラフィカルバーコードトレーニングサンプル７４のテンプレートと幾何学的に比較して、入力画像がグラフィカルバーコードトレーニングサンプルの複製であるか否かを判定するように構成される。
予め定義された基準が満たされた場合、入力画像はグラフィカルバーコードトレーニングサンプルの複製（または整合）であると判定される。
【００３１】
図９に示すように、動作にあたり、複合画像２２内の各位置（ｍ，ｎ）毎に、候補セレクタ８０が（ｍ，ｎ）を中心とするＮ×Ｎブロック９０をチェックして、そのブロックがテンプレート整合候補であるか否かを判定する。
特に、予め選択された各走査角毎に、ブロック９０のカラープレーン（ｃとインデックス付与される）が、候補セレクタ８０の線形整合フィルタ８４により等方性および非等方性カーネル（ｋとインデックス付与される）上に投影され、投影値ｖ［ｋ］［ｃ］（ｍ，ｎ）が得られる。
次に、これらの値が、パラメータファイルに含まれるテンプレート（τ＝０，１，・・・，Ｌ−１）毎に、しきい値処理器８６によって間隔しきい値と比較される。
パラメータファイルに基づいて行われうるテストとしては、色間隔チェック、輝度間隔チェック、およびブロックがエネルギ関数ｅ：
【００３２】
ｅ（ｍ，ｎ）＝ΣcΣk｜ｖ［ｋ］［ｃ］（ｍ，ｎ）｜2
の局所極大に対応するか否かのチェックが挙げられる。
ブロックは、特定のパラメータセットに関して上記テストをすべてパスする場合、テンプレート整合とみなされ、この場合、そのブロックの向き間隔Δγが推定され、整合パラメータｉ、τ、ｍ、ｎおよびΔγが整合リストに追加され、これがジオメトリック検証器８２に渡される。
【００３３】
検出モジュールの検出速度を向上させるために、間隔チェックはパイプライン化された方法で行われる。
たとえば、カーネルｋのカラーチェックは、前のカーネルＫ−１がカラーチェックをパスした場合にのみ行われる。
輝度チェックは、ブロックがすべてのカラーチェックをパスした場合にのみ同じパイプライン化様式で行われる。
最後に、局所極大テストは、ブロックが前のすべてのテストにパスした場合にのみ行われる。
【００３４】
ジオメトリック検証器８２は、候補セレクタ８０によって識別されたテンプレート整合を検証する。
特に、ジオメトリック検証器８２は、以下の要件を満たす整合リスト中のＬｅテンプレート候補の組み合わせを探す。
・Ｌｅ候補すべてが同じグラフィカルバーコードトレーニングサンプル７４に対応する。
・Ｌｅ候補が異なるテンプレート数τを有し、最初の２つのテンプレート（τ＝０およびτ＝１）が存在する。
・最初の２つのテンプレート（すなわち、ｍ、ｎにより与えられる各位置）間の距離が、パラメータファイル中に与えられているものとおおよそ整合すべきである。
・τ≧２のテンプレートの文書座標がパラメータファイル中に与えられているものと整合すべきである。
整合リスト中のＬｅ候補セットが上記要件を満たす場合、このセットは整合であるとジオメトリ検証器８２によって宣言される。
【００３５】
トレーニングモジュール６２および検出モジュール６４を含む検出システムの動作および実施に関するさらなる詳細は、Renato Keshet他による「System and Method for Counterfeit Protection」と題する１９９９年１０月２８日出願の米国特許出願第０９／４２９，５１５号から得ることができる。
【００３６】
再び図５を参照すると、１つまたは複数のグラフィカルバーコード候補整合が検出されると（ステップ１００）、ジオメトリック検証器８２が、グラフィカルバーコード抽出器４４の別のプログラムモジュールに、第１の検出グラフィカルバーコード候補の一対の対角の位置座標の推定値を渡す（ステップ１０２）。
この情報から、グラフィカルバーコード抽出器４４は、検出されたグラフィカルバーコード候補の向き角度および残りの対角対の位置座標を求めることができる。
【００３７】
図１０に示すように、第１の検出グラフィカルバーコード候補の角位置の推定値が計算された後、走査画像４８をクロッピングして、検出されたグラフィカルバーコード候補およびおそらく走査画像４８に含まれる外部からのマーキング１０５を含む包含画像領域１０４にサイズダウンすることができる（ステップ１０６）。
包含画像領域１０４のサイズは、所望の許容レベルを達成するための重畳カーネルのサイズおよびサブサンプリング係数に基づいて決定することができる。
走査画像４８をクロッピングして包含領域１０４にサイズダウンすることで、続く処理ステップに必要な計算量が低減する。
【００３８】
図１１を参照すると、本発明の画像領域１０４は、検出されたグラフィカルバーコード候補の計算された向き角度に基づいてデスキューされ、デスキュー包含画像領域１０８が生成される（ステップ１１０）。
次に、デスキュー包含画像領域１０８は、輝度ヒストグラムプロファイル１１２、１１４の計算を含む一次元解析によってトリミングされる（ステップ１１６）。
輝度ヒストグラムプロファイルは、検出されたグラフィカルバーコード候補の計算された角度向きに対応する直交軸（ｘ，ｙ）に沿って輝度値を合算することによって計算される。
非グラフィカルバーコード領域は、しきい値を輝度ヒストグラムプロファイル１１２に適用することによって、デスキュー包含画像領域１０８の左側および右側からトリミングすることができる。
たとえば、デスキュー包含画像領域１０８の左側および右側を、ヒストグラムが選択されたしきい値未満になるデスキュー包含画像領域のサイドエッジ付近の場所でトリミングすることができる。
概して、しきい値処理アルゴリズムは、デスキュー包含領域１０８の中心から開始し、ヒストグラムが選択されたしきい値未満になるまで、左右外側に向けて移動する。
選択されたしきい値は経験的に決定することが可能である。
同様にして、非グラフィカルバーコード領域も、しきい値を輝度ヒストグラムプロファイル１１４に適用することによって、デスキュー包含画像領域１０８の上側および下側からトリミングすることができる。
【００３９】
しきい値をドット密度プロファイル１１２、１１４に適用することに加えて、トリミング座標場所の選択は、グラフィカルバーコードトレーニングサンプル７４の次元の知識に基づいて改良することができる。
たとえば、しきい値処理ステップ後に１つのみのトリミング場所を比較的高精度で決定することができる場合、その他のトリミング場所は、グラフィカルバーコードトレーニングサンプルの対応する軸方向の次元だけ、正確に決定されたトリミング場所から離間された軸場所に選択することができる。
実施形態によっては、適用されたしきい値よりも大きいドットカウントを有するデスキュー包含画像１０８の領域は、デスキュー包含領域１０８のエッジ付近のドット密度プロファイル１１２、１１４の急上昇領域を、予め規定されるピクセル数（Δ）よりも越えている場合、拒絶する（そして、ノイズ領域として取り扱う）ことができるものもある。
予め規定されるピクセル数（Δ）は経験的に決定しうる。
【００４０】
実施形態によっては、デコーダ４６により実施される復号化アルゴリズムでは、得られるトリミング済グラフィカルバーコード候補が特定の解像度を有する必要がありうるものもある。
こういった実施形態では、トリミング済グラフィカルバーコード候補を、復号化に適した解像度にスケーリング（拡大または縮小）することができる（ステップ１１８）。
【００４１】
次に、スケーリングされたグラフィカルバーコード候補をデコーダ４６によって復号化しうる（ステップ１２０）。
グラフィカルバーコード候補が首尾よく復号化される場合（ステップ１２２）、抽出プロセスは停止する（ステップ１２４）。
しかし、グラフィカルバーコード候補を首尾よく復号化することができない場合（ステップ１２２）、抽出プロセスは、走査画像４８において検出された次のグラフィカルバーコード候補（もしあれば）について繰り返される（ステップ１００）。
【００４２】
グラフィカルバーコード候補が走査画像４８で検出されない場合、または抽出プロセスがデコーダ４６による復号化可能なグラフィカルバーコードの抽出に失敗した場合（ステップ１００）、走査画像４８を増分量だけ回転させる（ステップ１２６）ことができ、そして抽出プロセスを繰り返すことができる（ステップ６０）。
走査画像４８を回転させる量は、検出プロセス（図９参照）中に使用される連続走査間の回転角未満のものと決定される。
たとえば、ターゲット画像抽出器４４が、６４の可能な回転角にわたって走査画像４８を走査するようにプログラムされる場合、連続走査間の角度はおおよそ５．６度であり、この場合、走査画像４８を０度と５．６度の間の角度（たとえば、２．８度）だけ増分的に回転させることができる。
走査画像４８を何回か（Ｒ回）回転させた後でもグラフィカルバーコードの抽出が成功しない場合（ステップ１２８）、グラフィカルバーコード抽出プロセスは終了する（ステップ１３０）。
【００４３】
実施形態によっては、入力画像におけるグラフィカルバーコード候補の検出の失敗を受けて、検出モジュール６４がグラフィカルバーコード候補の検出に使用するトレーニングサンプルを変更しうる。
たとえば、検出モジュール６４はまず、非回転トレーニングサンプルに基づいてグラフィカルバーコード候補を検出しようと試みることができる。
非回転トレーニングによりいずれの候補も得られない場合、トレーニングサンプルを回転させたもの（たとえば、９０度回転させる）を使用して、グラフィカルバーコード候補を検出しようと試みることができる。
このプロセスが終了する前に、１つまたは複数の追加トレーニングサンプルを、入力画像中のグラフィカルバーコード候補を検出するベースとして使用することができる。
トレーニングサンプルは、走査画像４８を回転させたものに基づいて検出を繰り返す前、後、またはこの代わりに変更することができる（ステップ１２６）。
【００４４】
要約すれば、上記実施形態は、入力画像からグラフィカルバーコードを自動的に抽出する新規の手法を提供する。
特に、これら実施形態では、埋め込み情報を符号化した情報包含グラフィックス変調を保存するとともに、複合画像に含まれるマーキング等の汚損アーチファクトを回避するように、グラフィカルバーコードを複合画像から切り離すことができる。
得られる抽出グラフィカルバーコードは、外部からのマーキングおよび画像の汚損等のノイズに特に敏感でありうる復号化システムの要件に適合したフォーマットに容易に処理することができる。
加えて、これら実施形態は、検出の失敗および不正確な検出に堅牢に対処する。
【００４５】
本明細書に述べたシステムおよび方法は、任意の特定のハードウェア構成またはソフトウェア構成に限定されず、むしろ、デジタル電子回路内、またはコンピュータハードウェア、ファームウェア、またはソフトウェア内を含む、任意の計算または処理環境で実施することができる。
エンコーダ、文書プロセッサ、グラフィカルバーコード抽出器およびデコーダモジュールは、部分的に、コンピュータプロセッサによる実行のために機械可読記憶装置に有形に具体化されたコンピュータプログラム製品に実施することができる。
実施形態によっては、これらモジュールは、好ましくは、高水準手続き型またはオブジェクト指向プログラミング言語で実施されるが、所望であれば、アルゴリズムはアセンブリ言語または機械語で実施してもよい。
いずれの場合でも、プログラミング言語はコンパイル言語またはインタープリタ言語であることができる。
本明細書に述べた符号化、文書処理、抽出および復号化の各方法は、たとえば、プログラムモジュールに編成された命令をコンピュータプロセッサが実行して、入力データに対して動作することによってこれら方法を実行し、出力を生成することによって行うことができる。
適切なプロセッサとしては、たとえば、汎用および専用マイクロプロセッサの両方が挙げられる。
概して、プロセッサは命令およびデータを読み取り専用メモリおよび／またはランダムアクセスメモリから受け取る。
コンピュータプログラム命令を有形に具体化するために適した記憶装置としては、たとえば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイス等の半導体メモリ素子を含むすべての形の不揮発性メモリ、すなわち内部ハードディスクおよび取り外し可能ディスク等の磁気ディスク、磁気光学ディスクおよびＣＤ−ＲＯＭが挙げられる。
上記技術はいずれも、特別に設計されたＡＳＩＣ（特性用途向け集積回路）によって捕捉するか、または組み込むことができる。
【００４６】
他の実施形態も特許請求の範囲内にある。
【図面の簡単な説明】
【００４７】
【図１】符号化情報を含むグラフィカルバーコードを複合画像中に組み込み、複合画像のハードコピーをプリントするシステムのブロック図である。
【図２Ａ】基本画像をグラフィックス符号化情報とともにレンダリングする方法の流れ図である。
【図２Ｂ】２ビット二値レベルグラフィカルコードに情報をマッピングするテーブルである。
【図３】図１のシステムによって生成される複合画像の線図である。
【図４】複合画像のハードコピーからグラフィカルバーコードを自動的に抽出し、抽出されたグラフィカルバーコードから情報を復号化するシステムのブロック図である。
【図５】複合画像からグラフィカルバーコードを自動的に抽出する方法の流れ図である。
【図６】グラフィカルバーコード検出システムのトレーニングモジュールのブロック図である。
【図７】グラフィカルバーコード、およびグラフィカルバーコードの特徴であるパラメータファイルを図６のトレーニングモジュールによって生成しうるテンプレート領域を画定する７つの重複した円の線図である。
【図８】グラフィカルバーコード検出システムの検出モジュールのブロック図である。
【図９】図３の複合画像、および複数の回転方向に沿って処理されるカーネル領域の線図である。
【図１０】図３の複合画像からクロッピングされ、かつ検出グラフィカルバーコード候補を含む包含画像領域の線図である。
【図１１】グラフィカルバーコード候補が一対の直交軸と、直交軸に沿って輝度値を合算することによって得られる一対のヒストグラムとに位置合わせされるように回転された図１０の包含画像領域の線図である。
【符号の説明】
【００４８】
１２・・・エンコーダ、
１８・・・基本画像、
２０・・・文書プロセッサ、
２４・・・プリンタ、
４２・・・スキャナ、
４４・・・グラフィカルバーコード抽出器、
４６・・・デコーダ、
６２・・・トレーニングモジュール、
６４・・・検出モジュール、
６６・・・カーネルテンプレートセレクタ、
６８・・・テンプレートパラメータコンピュータ、
７０・・・カーネルセレクタ、
７２・・・テンプレートセレクタ、
６２・・・トレーニングモジュール、
６６・・・カーネルテンプレートセレクタ、
６８・・・テンプレートパラメータコンピュータ、
７０・・・カーネルセレクタ、
７２・・・テンプレートセレクタ、
８０・・・候補セレクタ、
８２・・・ジオメトリック検証器、
８４・・・線形整合フィルタ、
８６・・・しきい値処理器、
【図１】
2004533071.tif 000004
【図２Ａ】
2004533071.tif 000005
【図２Ｂ】
2004533071.tif 000006
【図３】
2004533071.tif 000007
【図４】
2004533071.tif 000008
【図５】
2004533071.tif 000009
【図６】
2004533071.tif 000010
【図７】
2004533071.tif 000011
【図８】
2004533071.tif 000012
【図９】
2004533071.tif 000013
【図１０】
2004533071.tif 000014
【図１１】
2004533071.tif 000015
【国際公開パンフレット】
2004533071.tif 000016
2004533071.tif 000017
2004533071.tif 000018
2004533071.tif 000019
2004533071.tif 000020
2004533071.tif 000021
2004533071.tif 000022
2004533071.tif 000023
2004533071.tif 000024
2004533071.tif 000025
2004533071.tif 000026
2004533071.tif 000027
2004533071.tif 000028
2004533071.tif 000029
2004533071.tif 000030
2004533071.tif 000031
2004533071.tif 000032
2004533071.tif 000033
2004533071.tif 000034
2004533071.tif 000035
2004533071.tif 000036
2004533071.tif 000037
2004533071.tif 000038
2004533071.tif 000039
2004533071.tif 000040
2004533071.tif 000041
2004533071.tif 000042
【国際調査報告】
2004533071.tif 000043
2004533071.tif 000044
2004533071.tif 000045
2004533071.tif 000046