(57)【要約】２次元の記号は、記号を含む２値画像を形成することによって復号される。２値画像は、記号のコントラスト画像を最初に形成して、そのコントラスト画像を２値化することによって構成され得る。２値画像は、デジタル化に使用される記号のマージンを生成するために使用される。記号のマージンを決定するために２値画像を使用することによって、マージンの場所が効率的に、かつマーク付けされた表面における不規則性または光源角度によって引き起こされる記号のコントラスト変動の存在のもとで、突き止められ得る。デジタル化は、決定されたマージンに基づいて進行する。【特許請求の範囲】
【請求項１】
記号を復号する方法であって、
グレイスケール画像を２値画像に変換することと、
該２値画像を使用して、該記号のアウトラインを決定することと、
該アウトラインに基づいて該記号をデジタル化することと
を含む、方法。
【請求項２】
前記２値画像の各画素は、該画素の対応する群が、前記グレイスケール画像における前記記号に属する可能性を示す、請求項１に記載の方法。
【請求項３】
前記２値画像における画素は、次の処理の前に電子メモリに格納されていない、請求項１に記載の方法。
【請求項４】
前記２値画像における画素値は、次の処理のために必要とされるときに決定される、請求項３に記載の方法。
【請求項５】
前記グレイスケール画像は、
バーコードのグレイスケール画像の境界を横断することと、
該バーコードの該境界に、またはその近くに位置する画素の特徴に対応するデータのセットを収集することと、
該バーコードの該境界に、またはその近くに位置する画素の特徴に対応する該データのセットに基づいて、該グレイスケール画像を２値化することと
によって２値化画像に変換される、請求項１に記載の方法。
【請求項６】
前記グレイスケール画像の前記境界は、
前記記号の一部を形成するシード画素または画素の群を選択することと、
該シード画素から始めて、該記号の境界が遭遇されるまで、画素の放射状経路を横断することと、
２値化された類似の表現を有する隣接する画素の群を横断して、該記号の前記アウトラインを形成する境界画素の位置を突き止めることと
によって横断される、請求項５に記載の方法。
【請求項７】
前記隣接した画素の群は、該隣接する画素の群が前記境界画素の位置を突き止めるために横断されるとき２値化される、請求項６に記載の方法。
【請求項８】
前記グレイスケール画像は、前記境界画素の特徴に対応するデータのセットに合う２値化平面を形成することによって２値化される、請求項６に記載の方法。
【請求項９】
前記２値画像における隣接した前景画素の近接した群を合体させ、該隣接した前景画素の合体した群のアウトラインを横断して、記号のマージン線を見出すことを含む、請求項６に記載の方法。
【請求項１０】
前記隣接した前景画素の群のアウトラインは、隣接した前景画素間の、所与の数の背景画素のスペースを跳び越えることによって横断される、請求項９に記載の方法。
【請求項１１】
各マージン線を、それが記号に交差するまでシフトさせることにより、該マージン線を、それが前記記号の境界と平行になるまで交差の点のまわりでピボット回転させることにより、該マージン線を整列させることを含む、請求項９に記載の方法。
【請求項１２】
平行線の統計的組み合わせを実行して、前記記号の境界に直交する単一の線プロファイルに変えることによって、少なくとも１つの太線を引き、最初の重要な縁を決定することを含む、請求項１１に記載の方法。
【請求項１３】
前記アウトラインを成す前記各マージン線で前記記号の切片を分析し、４つのマージン線それぞれのモジュールの周期性を決定することによって、該記号の周期性を生成することにより、該記号がデジタル化される、請求項１２に記載の方法。
【請求項１４】
前記４つのマージン線の前記モジュールの周期性に対応するグリッド間隔を有するグリッドを構成することを含む、請求項１３に記載の方法。
【請求項１５】
それぞれが前記記号における隣接したモジュールのセットを含むタイルで前記グリッドを埋めることを含み、各タイル内で、既知のモジュールの状態は未知のモジュールの状態を決定するために使用される、請求項１４に記載の方法。
【請求項１６】
前記グリッドは最初に、グリッドコーナにおいてタイルで埋められ、その後、グリッド縁においてタイルで埋められ、埋め込みは概ねグリッド縁から、重複リングの順序で進行する、請求項１５に記載の方法。
【請求項１７】
デジタル化された記号を復号することを含む、請求項１に記載の方法。
【請求項１８】
前記グレイスケール画像は、画像化バーコードスキャナで得られる、請求項１に記載の方法。
【請求項１９】
前記２値画像の各画素は、１バイトとして格納される、請求項１に記載の方法。
【請求項２０】
前記２値画像の各画素は、１バイトより大きいとして格納される、請求項１に記載の方法。
【請求項２１】
前記２値画像の各画素は、１バイト未満として格納される、請求項１に記載の方法。
【請求項２２】
コンピュータ読み取り可能な媒体であって、該コンピュータ読み取り可能な媒体は、記号を復号するために、その上に格納されたコンピュータ実行可能なインストラクションを有し、該インストラクションは、
グレイスケール画像を２値画像に変換することと、
該２値画像を使用して該記号のアウトラインを決定することと、
該アウトラインに基づいて該記号をデジタル化することと
を含む、コンピュータ読み取り可能な媒体。
【請求項２３】
前記２値画像の各画素は、該画素の対応する群が、前記グレイスケール画像における前記記号に属する可能性を示す、請求項２２に記載のコンピュータ読み取り可能な媒体。
【請求項２４】
前記２値画像における画素は、次の処理の前に電子メモリに格納されていない、請求項２２に記載のコンピュータ読み取り可能な媒体。
【請求項２５】
前記２値画像における画素値は、次の処理のために必要とされるときに決定される、請求項２４に記載のコンピュータ読み取り可能な媒体。
【請求項２６】
前記グレイスケール画像を２値画像に変換するための前記インストラクションは、
バーコードのグレイスケール画像の境界を横断することと、
該バーコードの境界に、またはその近くに位置する画素の特徴に対応するデータのセットを収集することと、
該バーコードの境界に、またはその近くに位置する画素の特徴に対応する該データのセットに基づいて、該グレイスケール画像を２値化することと
を含む、請求項２２に記載のコンピュータ読み取り可能な媒体。
【請求項２７】
前記グレイスケール画像の境界を横断するための前記インストラクションは、
前記記号の一部を形成するシード画素または画素の群を選択することと、
該シード画素から始めて、該記号の境界が遭遇されるまで、画素の放射状経路を横断することと、
２値化された類似の表現を有する隣接する画素の群を横断して、該記号の前記アウトラインを形成する境界画素の位置を突き止めることと
を含む、請求項２６に記載のコンピュータ読み取り可能な媒体。
【請求項２８】
前記隣接する画素の群は、該隣接する画素の群が前記境界画素の位置を突き止めるために横断されるときに２値化される、請求項２７に記載のコンピュータ読み取り可能な媒体。
【請求項２９】
前記グレイスケール画像を２値化するための前記インストラクションは、
前記境界画素の特徴に対応するデータのセットに合う２値化平面を形成することを含む、請求項２７に記載のコンピュータ読み取り可能な媒体。
【請求項３０】
前記インストラクションは、前記２値画像における隣接した前景画素の近接した群を合体させ、該前景画素に隣接する合体した群のアウトラインを横断して、記号のマージン線を見出すこととを含む、請求項２７に記載のコンピュータ読み取り可能な媒体。
【請求項３１】
前記隣接した前景画素の群のアウトラインを横断するためのインストラクションは、
該隣接した前景画素間の所与の数の背景画素のスペースを跳び越えることを含む、請求項３０に記載のコンピュータ読み取り可能な媒体。
【請求項３２】
前記インストラクションは、
各マージン線を、それが記号に交差するまでシフトさせることにより、該マージン線を、それが記号の境界と平行になるまで交差の点のまわりでピボット回転させることにより、マージン線を整列させることを含む、請求項３１に記載のコンピュータ読み取り可能な媒体。
【請求項３３】
前記インストラクションは、平行線の統計的組み合わせを実行して、前記記号の境界に直交する単一の線プロファイルに変えることによって、少なくとも１つの太線を引き、最初の重要な縁を決定することを含む、請求項３２に記載のコンピュータ読み取り可能な媒体。
【請求項３４】
前記記号をデジタル化するための前記インストラクションは、前記アウトラインを成す前記各マージン線で前記記号の切片を分析し、４つのマージン線それぞれのモジュールの周期性を決定することによって、該記号の周期性を生成することを含む、請求項３３に記載のコンピュータ読み取り可能な媒体。
【請求項３５】
前記インストラクションは、前記４つのマージン線の前記モジュールの周期性に対応するグリッド間隔を有するグリッドを構成することを含む、請求項３４に記載のコンピュータ読み取り可能な媒体。
【請求項３６】
前記インストラクションは、それぞれが前記記号における隣接したモジュールのセットを含むタイルで前記グリッドを埋めることを含み、各タイル内で、既知のモジュールの状態は未知のモジュールの状態を決定するために使用される、請求項３５に記載のコンピュータ読み取り可能な媒体。
【請求項３７】
前記グリッドを埋めるための前記インストラクションは、該グリッドを最初に、グリッドコーナにおいてタイルで埋めて、その後、グリッド縁においてタイルで埋めて、埋め込みは概ね該グリッド縁から、重複リングの順序で進行する、請求項３６に記載のコンピュータ読み取り可能な媒体。
【請求項３８】
前記インストラクションは、デジタル化された記号を復号することを含む、請求項２２に記載のコンピュータ読み取り可能な媒体。
【請求項３９】
前記グレイスケール画像は、画像化バーコードスキャナで取得される、請求項２２に記載のコンピュータ読み取り可能な媒体。
【請求項４０】
前記２値画像の各画素は、１バイトとして格納される、請求項２２に記載のコンピュータ読み取り可能な媒体。
【請求項４１】
前記２値画像の各画素は、１バイトより大きいとして格納される、請求項２２に記載のコンピュータ読み取り可能な媒体。
【請求項４２】
前記２値画像の各画素は、１バイト未満として格納される、請求項２２に記載のコンピュータ読み取り可能な媒体。
【請求項４３】
記号を復号するための装置であって、該装置は、
グレイスケール画像を２値画像に変換するための手段と、
該２値画像を使用して、該記号のアウトラインを決定する手段と、
該アウトラインに基づいて該記号をデジタル化するための手段と
を含む、装置。
【請求項４４】
前記グレイスケール画像を前記２値画像に変換するための手段は、
バーコードのグレイスケール画像の境界を横断するための手段と、
該バーコードの境界に、またはその近くに位置する画素の特徴に対応するデータのセットを収集するための手段と、
該バーコードの境界に、またはその近くに位置する画素の特徴に対応する該データのセットに基づいて、該グレイスケール画像を２値化するための手段と
を含む、請求項４３に記載の装置。
【請求項４５】
前記グレイスケール画像の境界を横断するための手段は、
前記記号の一部を形成するシード画素または画素の群を選択するための手段と、
該シード画素から始めて、該記号の境界が遭遇されるまで、画素の放射状の経路を横断する手段と、
２値化された類似の表現を有する隣接する画素の群を横断して、該記号の前記アウトラインを形成する境界画素の位置を突き止めるための手段と
を含む、請求項４４に記載の装置。
【請求項４６】
前記隣接する画素の群を横断するための手段は、該隣接する画素の群が前記境界画素の位置を突き止めるために横断されるとき、画素を２値化する、請求項４５に記載の装置。
【請求項４７】
記号を復号する装置であって、該装置は
グレイスケール画像を２値画像に変換して、かつ該２値画像を使用して該記号のアウトラインを決定するフロントエンドプロセッサと、
該アウトラインに基づいて該記号をデジタル化するデジタイザと
を含む、装置。
【請求項４８】
前記フロントエンドプロセッサは、バーコードのグレイスケール画像の境界を横断して、該バーコードの境界に、またはその近くに位置する画素の特徴に対応するデータのセットを収集する輪郭ウォーカを含み、該フロントエンドプロセッサは、該バーコードの境界に、またはその近くに位置する該画素の特徴に対応する該データのセットに基づいて、該グレイスケール画像を２値化する、請求項４７に記載の装置。
【請求項４９】
前記輪郭ウォーカは、前記グレイスケール画像の境界を、
記号の一部を形成するシード画素または画素の群を選択することと、
該シード画素から出発し、該記号の境界が遭遇されるまで、画素の放射状の経路を横断することと、
２値化された類似の表現を有する隣接する画素の群を横断して、該記号の前記アウトラインを形成する境界画素の位置を突き止めることと
によって横断する、請求項４８に記載の装置。
【請求項５０】
前記輪郭ウォーカは、前記隣接する画素の群を、該隣接する画素の群が前記境界画素の位置を突き止めるために横断されるときに２値化する、請求項４９に記載の装置。
【請求項５１】
デジタル化された記号を復号する復号器を含む、請求項４７に記載の装置。
【請求項５２】
前記グレイスケール画像を取得する画像化バーコードスキャナを含む、請求項４７に記載の装置。
【請求項５３】
２次元バーコード記号を復号する方法であって、該方法は、
グレイスケール画像をコントラスト画像に変換することであって、各画素は、該グレイスケール画像における画素の所与の群における画素の間でのコントラストのレベルを示す、ことと、
該コントラスト画像を使用して該バーコード記号のアウトラインを決定することと、
該アウトラインに基づいて該グレイスケール画像をデジタル化することと
を含む、方法。
【請求項５４】
前記コントラスト画像の所与の画素は、前記グレイスケール画像における対応する画素の群における最も明るい画素と最も暗い画素との間での明るさの相違によって決定される、請求項５３に記載の方法。
【請求項５５】
前記コントラスト画像の他のいかなる画素も、前記所与の画素に対応する前記グレイスケール画像において、画素の群における任意の画素に依存しない、請求項５３に記載の方法。
【請求項５６】
前記バーコードを成す前景画素のためのコントラストのレベル、および該バーコードの背景を形成する画素のためのコントラストのレベルを決定することを含む、請求項５３に記載の方法。
【請求項５７】
スレッショルド表面を形成することを含み、該スレッショルド表面は、前記バーコードの前景を成す前景画素のためのコントラストのレベル、および該バーコードの背景を形成する画素のためのコントラストのレベルの関数である、請求項５３に記載の方法。
【請求項５８】
前記バーコード記号の前記アウトラインを決定するために使用される２値画像に達するするために、前記スレッショルド表面を使用して、前記コントラスト画像を２値化することを含む、請求項５７に記載の方法。
【請求項５９】
２値画像において、隣接した前景画素の群を横断して、前記バーコード記号の前記アウトラインを形成するマージン線の位置を突き止めることを含む、請求項５８に記載の方法。
【請求項６０】
前記２値画像における隣接した前景画素の近接した群を合体させ、該隣接した前景画素の合体した群のアウトラインを横断して、前記バーコード記号のマージン線を見出すことを含む、請求項５８に記載の方法。
【請求項６１】
各マージン線を、それが前記バーコードに交差するまでシフトさせることにより、該マージン線を、それがバーコードの境界と平行になるまで交差の点のまわりでピボット回転させることにより、該マージン線を整列させることを含む、請求項５９に記載の方法。
【請求項６２】
平行線の統計的組み合わせを実行して、前記バーコードの境界に直交する単一のプロファイルに変えることによって、少なくとも１つの太線を引き、最初の重要な縁を決定することを含む、請求項６１に記載の方法。
【請求項６３】
前記アウトラインを成す各マージン線で前記バーコードの切片を分析し、４つの該マージン線それぞれのモジュールの周期性を決定することによって、該バーコード記号の周期性を生成することにより、前記グレイスケール画像がデジタル化される、請求項５３に記載の方法。
【請求項６４】
前記４つのマージン線の前記モジュールの周期性に対応するグリッド間隔を有するグリッドを構成することを含む、請求項６３に記載の方法。
【請求項６５】
それぞれが前記バーコード記号における隣接したモジュールのセットを含むタイルでグリッドを埋めることを含み、各タイル内で、既知のモジュールの状態は未知のモジュールの状態を決定するために使用される、請求項６４に記載の方法。
【請求項６６】
前記グリッドは最初に、グリッドコーナにおいてタイルで埋められ、その後、グリッド縁においてタイルで埋められ、埋め込みは概ね該グリッド縁から、重複リングの順序で進行する、請求項６５に記載の方法。
【請求項６７】
２次元バーコード記号を復号する装置であって、該装置は、
グレイスケール画像サンプラーであって、該グレイスケール画像サンプラーは、各画素が、グレイスケール画像において、対応する画素の群における画素間のコントラストのレベルを指示するコントラスト画像を構成し、該コントラスト画像を分析して、該バーコード記号の前景における前景画素に対応する第１コントラストのレベル、および該バーコード記号の背景における画素に対応する第２コントラストのレベルを決定し、該第１および該第２コントラストのレベルの機能に基づいてスレッショルド表面を形成し、２値画像を構成するために該スレッショルド表面に基づいてコントラスト画像を２値化することによって、該バーコード記号のグレイスケール画像の副次標本バージョンを構成する、グレイスケール画像サンプラーと、
所定の数の画素よりも少ない数の隣接した前景画素の群の間の空間を跳び越えることによって、２値画像における該隣接した前景画素の群を横断するマージン検知器と、
所定の数の画素よりも少ない数の隣接した前景画素の群の間の空間を跳び越えることによって、２値画像における該隣接した前景画素の群を横断するマージン検知器と、
検知された各マージン線でバーコードの切片を分析することにより、かつ該各マージン線のモジュールの周期性を決定することにより該バーコード記号の周期性を生成することによって；該マージン線のモジュールの周期性に対応するグリッド間隔を有するグリッドを構成することによって；かつ記号モジュールの１群を含むタイルでグリッドを埋めることであって、該モジュールはそれぞれ既知の状態を有する周囲の該タイルの状態に基づいて決定される状態を有することによって、復号するための該グレイスケール画像をデジタル化するために該マージン線を使用するデジタイザと
を含む、装置。
【請求項６８】
コンピュータ読み取り可能な媒体であって、該コンピュータ読み取り可能な媒体は、該コンピュータ読み取り可能な媒体上に格納された、２次元バーコード記号を復号化する方法ステップを実行するための、コンピュータによって実行可能なインストラクションを有しており、該方法ステップは、
各画素が、グレイスケール画像における画素の所与の群における画素間のコントラストのレベルを指示するコントラスト画像に、グレイスケール画像を変換することと、
該コントラスト画像を使用してバーコード記号のアウトラインを決定することと、
該アウトラインに基づいてグレイスケール画像をデジタル化することと
を含む、コンピュータ読み取り可能な媒体。
【請求項６９】
前記コントラスト画像の所与の画素は、前記グレイスケール画像における対応する画素の群における画素の間のコントラストのレベルによって決定される、請求項６８に記載のコンピュータ読み取り可能な媒体。
【請求項７０】
前記方法ステップは、前記バーコードを成す前景画素のためのコントラストのレベル、および該バーコードの背景を形成する画素のためのコントラストのレベルを決定することを含む、請求項６８に記載のコンピュータ読み取り可能な媒体。
【請求項７１】
前記バーコードを成す前景画素のためのコントラストのレベル、および該バーコードの背景を形成する画素のためのコントラストのレベルは、位置の関数として変化する、請求項７０に記載のコンピュータ読み取り可能な媒体。
【請求項７２】
前記方法ステップは、スレショルド表面を形成することを含み、該スレショルド表面は、前記バーコードを成す前景画素のためのコントラストのレベル、および該バーコードの背景を形成する画素のためのコントラストのレベルの関数である、請求項７１に記載のコンピュータ読み取り可能な媒体。
【請求項７３】
前記方法ステップは、前記バーコード記号のアウトラインを決定するために使用される２値画像に達するために、前記スレショルド表面を使用して、前記コントラスト画像を２値化することを含む、請求項７２に記載のコンピュータ読み取り可能な媒体。
【請求項７４】
前記方法ステップは、前記バーコード記号のアウトラインを形成するマージン線の位置を突き止めるために、前記２値画像を横断することを含む、請求項７３に記載のコンピュータ読み取り可能な媒体。
【請求項７５】
前記方法ステップは、隣接する前景画素の群の間のスペースを跳び越えることによって前記バーコード記号のマージン線を見つけるために、前記２値画像における隣接する前景画素の群のアウトラインを横断することを含み、該スペースは、所与の数の画素よりも小さい、請求項７３に記載のコンピュータ読み取り可能な媒体。
【請求項７６】
各マージン線を、それが前記バーコードに交差するまでシフトさせることにより、該マージン線を、それが前記バーコード境界と平行になるまで交差の点のまわりでピボット回転させることにより、該マージン線を整列させることを含む、請求項７４に記載の方法。
【請求項７７】
前記方法ステップは、平行線の統計的組み合わせを実行して、前記バーコードの境界に直交する単一の線プロファイルに変えることによって、少なくとも１つの太線を引き、最初の重要な縁を決定することを含む、請求項７５に記載のコンピュータ読み取り可能な媒体。
【請求項７８】
前記方法ステップは、前記アウトラインを成す４つのマージン線それぞれで前記バーコードの切片を分析し、前記バーコード記号の周期性を生成し、生成された該周期性を使用して該４つのマージン線それぞれのモジュールの幅を決定することを含む、請求項６８に記載のコンピュータ読み取り可能な媒体。
【請求項７９】
前記方法ステップは、４つのマージン線のモジュールの周期性に対応するグリッド間隔を有するグリッドを構成することを含む、請求項６８に記載のコンピュータ読み取り可能な媒体。
【請求項８０】
前記方法ステップは、それぞれが前記バーコード記号における隣接したモジュールのセットを含むタイルで、前記グリッドを埋めること含み、各タイルの内で、既知のモジュールの状態は未知のモジュールの状態を決定するために使用される、請求項７９に記載のコンピュータ読み取り可能な媒体。
【請求項８１】
前記グリッドは最初に、グリッドコーナにおいてタイルで埋められ、その後、グリッド縁においてタイルで埋められ、埋め込みは概ね該グリッド縁から、重複リングの順序で進行する、請求項８０に記載のコンピュータ読み取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（技術分野）
本発明は一般にバーコードスキャナの分野に関し、より詳細には、直接部分マーキングでの使用のために適合されるバーコードスキャナに関する。
【背景技術】
【０００２】
（発明の背景）
データがアレイ方式でレイアウトされる概ね長方形のコードから成る２次元バーコードの使用がますます人気となっている。２次元バーコードは有利である。なぜならば、それらは英数字データばかりではなく、２値データも保持し得、かつ普通、エラー訂正機能を含み得るからである。加えて、２次元バーコードは、より小さなスペースにはるかにより多くの情報を格納することができるので、伝統的な１次元バーコードよりも著しくより効率的である。
【０００３】
ＤａｔａＭａｔｒｉｘは、エラー検知および訂正の両方を含む工業規格２次元バーコード規約である。各ＤａｔａＭａｔｒｉｘ記号は、長方形のアレイで配置された、名目上の正方形モジュールを含むデータ領域から成る。暗いモジュールは、２値の１であり、明るいモジュールは２値の０である。ＸまたはＹ次元に対しては、特定の最小または最大はない。データ領域は、ファインダパターン、すなわち幅が１モジュールであり、記号の４つの側すべてが地味なゾーン（ｑｕｉｔｅ  ｚｏｎｅ）によって囲まれているデータ領域に対する周辺によって取り囲まれている。２つの隣接する側は、物理的なサイズ、方向および記号のゆがみを規定するために主に使用される切れ目のない暗い線である。２つの相対する側は、交互に暗くかつ明るいモジュールから成る。これらは、セルの構成を規定するために主に使用されるが、物理的なサイズおよびゆがみを決定する際に補助ともなる。ＤａｔａＭａｔｒｉｘ記号表現のうちで人気の形式は、ＥＣＣ２００として公知であり、これはリードソロモンエラー訂正を使用する。
【０００４】
ＤａｔａＭａｔｒｉｘ記号は小型サイズであるため、ＤａｔａＭａｔｒｉｘ記号は、直接部分マーキングにおける使用のためには理想的なものとなっている。直接部分マーキングにおいては、ＤａｔａＭａｔｒｉｘ記号は、部分に当てられるラベルに印刷されるのに対して、マーク付けされる部分に直接的に印刷される。直接部分マーキングは、ＤａｔａＭａｔｒｉｘ記号は、必ずしも完全に平らな表面、または均一な反射率特性を有する表面に印刷され得るわけではないという事実によって引き起こされる難問を提示する。加えて、データモジュールは、例えば、金属部分が、部分をドットピーニング（ｄｏｔ−ｐｅｅｎｉｎｇ）することによってマーク付けされるような場合におけるように、正方形のモジュールの代わりに円形のドットとして印刷され得る。
【発明の開示】
【課題を解決するための手段】
【０００５】
（概要）
記号は、デジタル化において使用される記号マージンを生成するために使用される画像の２値化バージョンを形成することによって、入力グレイスケール画像から復号される。グレイスケール画像の２値化バージョンは、記号の境界に位置する画素についての情報を収集することによって、かつ収集された情報に基づいて２値化することによって、局所的にオンデマンドで形成され得る。記号のマージンを決定するために、グレイスケール画像の２値化バージョンを使用することによって、マージンの場所が効率的に、かつマーク付けされた表面における不規則性または表面を横切る照明の変動によって引き起こされる記号のコントラスト変動の存在のもとにあって、突き止められ得る。
【０００６】
例えばバーコード記号のような記号のアウトラインは、２値画像を使用して決定される。画像はその際、既知の状態を有する画素から成るアウトラインに基づいてデジタル化される。
【０００７】
記述される実施形態においては、記号の境界の輪郭（ｃｏｎｔｏｕｒ）は横断される。スレショルド（ｔｈｒｅｓｈｏｌｄ）表面が形成されるが、それは、記号の境界に位置する局所画素の特徴の関数である。グレイスケール画像は、スレショルド表面を使用して２値化されて、バーコード記号のアウトラインを決定するために使用される２値画像に達する。２値画像における隣接する前景画素の群は横断されることにより、バーコード記号のマージン線の場所を突き止めて、横断は随意に所与の数の画素のジャンプを含み得る。あるいは、２値画像における隣接する前景画素の群は合体し得て、合体した隣接する画素のアウトラインは横断されて、バーコード記号のマージン線を見出す。マージン線は、各マージン線がバーコードと交差するまで各マージン線をシフトさせ、かつマージン線をマージン線がバーコード境界と平行になるまで交差の点の周りでピボット回転させることによって、整列される。少なくとも１つの太線が、バーコード境界に対して直角に引かれて、最初の重要な縁を決定するために横断される。
【０００８】
バーコード記号の周期性は、アウトラインを成す４つのマージン線それぞれでバーコードの切片を分析することによって、かつ４つのマージン線それぞれのモジュールの周期性を決定することによって決定される。４つのマージン線の分析によって決定されるモジュールの周期性に対応するグリッド間隔を有するグリッドが、構成される。グリッドはタイルで埋められ、各タイルは、バーコード記号において、隣接するモジュールのセットを含み、未知の状態を有するタイルにおける各モジュールは、既知の状態を有するタイルにおけるモジュールとの比較に基づいて分析することにより、１つの状態を割り当てられる。タイルにおけるモジュールの状態を決定する処理は、４つのマージン線の分析の間に決定された既知のモジュールを含むマージンに沿った最初のタイルから始まり得る。
【発明を実施するための最良の形態】
【０００９】
（詳細な説明）
次の好ましい実施形態の詳細な記述において、本明細書の一部を形成する添付の図面について参照がなされ、その図面の中で、本発明が実施され得る特定の実施形態が、例示として示される。他の実施形態が利用され得、構造的な変更が本明細書の範囲から逸脱することなくなされ得ることを理解されたい。
【００１０】
画像化（ｉｍａｇｉｎｇ）を基礎とする直接部分マーキングスキャナが図１の１０で概略示される。スキャナ１０は、一次元および二次元両方のバーコード記号を画像化および復号することに加えて、画像およびシグネチャをキャプチャすることもできる。本発明の１つの好ましい実施形態においては、スキャナ１０は、仕入れおよび在庫管理の目的でバーコードを読み取るために、商店、倉庫または工場を歩いたり乗り物で移動したりするユーザによって携帯および使用され得るハンドヘルド携帯用読み取り機である。
【００１１】
しかしながら、本発明の直接部分マーキング復号システムは、以下に説明されるように、画像化を基礎とする任意のタイプの自動スキャナと関連して、有利に使用され得ることが認識されるべきである。加えて、この記述の目的のために、ＤａｔａＭａｔｒｉｘ画像がスキャナの標的であるが、任意の直接部分マーキングのコンベンションが、本発明の復号システムによって有利に復号され得る。
【００１２】
スキャナ１０は、トリガ１２が引かれるかまたは押される場合に、商品に直接的にマーク付けされている標的のＤａｔａＭａｔｒｉｘ記号１４（図示されず）の読み取りを開始するためのスキャナ回路網を含む直接部分マーキングマイクロプロセッサ８０に結合されているトリガ１２を含む。スキャナ１０は、標的に光を向ける、焦点調節レンズとＣＣＤ画像化装置と照明ソース４１とを含むカメラ２０を含む。焦点調節レンズは、標的のＤａｔａＭａｔｒｉｘ１４から反射される光の焦点を、ＣＣＤ画像化装置のフォトセンサまたは画素のアレイに当てる。所定の間隔で、画素アレイの画素は読み取られ、画素アレイ上でレンズによって焦点を当てられるものであれば、例えばＤａｔａＭａｔｒｉｘ記号１４などいかなるものの画像でも表現するアナログ信号を生成する。カメラからのアナログ画像信号は、アナログデジタル変換機７０によって、グレイスケールバージョンにデジタル化され、グレイスケール画像は、メモリ１５０に格納される。格納されたグレイスケール画像は、直接部分マーキングＤａｔａＭａｔｒｉｘ記号を復号することに適合した格納されたプログラムステップを使用して、マイクロプロセッサ８０によって復号される。復号されたデータは、ＤａｔａＭａｔｒｉｘ記号１４におけるコード化されたデータ／情報を表現し、データ出力端子対１００を介して出力され、かつ／または表示装置１１０を介してスキャナ１０のユーザに表示される。ＤａｔａＭａｔｒｉｘ記号１４の良好な「読み取り」を達成すると、スピーカ１２０は、バーコードがうまく読み取られたことをユーザに示すために、マイクロプロセッサによって作動される。同時に、１つ以上のインジケータ光（図１に示されず）が、読み取りが成功したことを示す追加的な指示を提供するために作動され得る。
【００１３】
ＤａｔａＭａｔｒｉｘ記号スキャナ１０はさらに、ユーザが正しく読み取り機を標的のＤａｔａＭａｔｒｉｘ記号１４に向ける際に補助するために、可視照準パターン４２を生成するための照準システム４０を含む。１つの好ましい実施形態において、照準システム４０は、半導体レーザアレイおよびレンズを含む。あるいは、照準装置４０は、ＬＥＤまたは当技術者に公知の照明の別のソースを利用し得る。パターン４２は、図１に示されるように、単一のドット４６と整列している中央「クロスヘア」パターン４２ｂを囲む複数の長方形のブラケット４２ａを含むパターンであり得る。照準パターンは、レンズの近くまたはレンズ内で組み立てられる、図示されない回析光学素子によって生成され得る。
【００１４】
図２は、ＤａｔａＭａｔｒｉｘ記号のグレイスケール画像７４を復号するマイクロプロセッサ８０に格納されたさまざまな機能プログラムモジュールの構成図である。モジュールは、直接マーク付けされた部分からスキャンされたＤａｔａＭａｔｒｉｘ画像を分析するための格納されたプログラムステップを含むフロントエンドプロセッサ１３０および直接部分マーキング（「ＤＰＭ」）デジタイザ１８０を含む。フロントエンドプロセッサ１３０は、スキャンされたＤａｔａＭａｔｒｉｘ記号のアウトラインを生成し、そのアウトラインはＤＰＭデジタイザ１８０に入力される。ＤＰＭデジタイザは、復号器１９０による復号のために、ＤａｔａＭａｔｒｉｘ画像における暗いモジュールと明るいモジュールとを区別するために、アウトラインおよび元のグレイスケールＤａｔａＭａｔｒｉｘ画像を使用する。
【００１５】
（記号アウトラインを見出すためのフロントエンドプロセシング）
図３および図４は、スキャンされたＤａｔａＭａｔｒｉｘ記号のためのアウトラインを生成するために、フロントエンドプロセッサによって使用され得る１つの方法を例示する。フロントエンドプロセッサは、ＤａｔａＭａｔｒｉｘ記号のアウトラインに対応する四辺形を生成する。上記アウトラインは、記号によって占められたエリアのすぐ外に画素として規定される。従って、ドットのほぼ円形の外側の「シャドー」は記号の一部としては含まれない。
【００１６】
ここで図３を参照して、フロントエンドプロセッサ３００の作動の方法は、流れ図形式で概説される。グレイスケールＤａｔａＭａｔｒｉｘ記号画像（図４Ａを参照）は、フロントエンドプロセッサに入力される。３２０において、画像の切片が、ＤａｔａＭａｔｒｉｘ記号内にあり、この記述の目的ために「ｐｒｅｆ」と呼ばれる点の場所を突き止めるために捜索される。処理時間は、画像全体ではなく画像の切片を分析することによって、節約される。分析される一片は、照準するクロスヘアの場所で分析されるが、これは、オペレータは、記号を直接的に照準することが仮定されたうえでのことである。３２０において実行される分析は、記号内に最もありそうな単一の画素の場所、および記号の近傍におけるノイズのレベルの最初の推定を戻す。ありそうな画素が見つからない場合は、上記方法は、３３０および４６０で終了する。
【００１７】
多くのＤＰＭＤａｔａＭａｔｒｉｘ記号の三次元的性質およびマーク付けされた表面が取り得る曲率のために、ＤａｔａＭａｔｒｉｘ記号の「ドット」、または満たされた／プリントされたモジュールは、記号のあるエリアでは「明るく」現われ得、また別のアリアでは「暗く」現われ得る。最初にデジタル化された画像の複雑さを減らすために、フロントエンドプロセッサは、ＤａｔａＭａｔｒｉｘ記号のアウトラインを見つける目的のためだけに使用される、３４０で元の画像のコントラストバージョンを構成する。場所の分かった点、「ｐｒｅｆ」から、コントラスト画像は、図４Ｂに示されるコントラスト画像のように構成される。コントラスト画像の構成の出発点は、切片分析からの点「ｐｒｅｆ」である。対照画像は、一回で１ブロックの画像を分析することによって、かつ各記号の「近傍」のみがコンバートされるように、隣接したブロックのみを強いコントラストでコンバートすることによって形成され、実行時間を節約する。画素が訪問される順番は、点「ｐｒｅｆ」から始まる深さ優先探索アルゴリズム（ｄｅｐｔｈ−ｆｉｒｓｔ  ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ）によって制御される。コンバージョンは、入力画像の４つの隣接した画素の正方形を必要とし、４つの入力画素のうち最も明るいものと最も暗いものとの差を値とする単一の画素を出力し、この差が局所的なコントラストの指示を与える。
【００１８】
いったんコントラスト画像が構成されると、コントラスト画像は、ＤａｔａＭａｔｒｉｘ記号を取り囲む「地味なゾーン」アウトラインの場所を突き止めるために、３５０で分析される。地味なゾーンは、センタアウトタイプ発見ルーチンを実行することによって場所が突き止められる。点「ｐｒｅｆ」から始まって、多くの太線が縁に向かって外側へ放射状に引かれる。この場合、太線は、例えばＳＵＭまたはＭＡＸのような統計学の演算子が、隣接する線にわたって画素の射影に適用された場合に生成される線プロフィールである。生成された線プロフィールは、記号の内部に自然に起こる穴を「ふさぐ」ためにＭＡＸ機能を使用する。線は、約２２．５度で、均等に離されている。アルゴリズムは、地味なゾーンが発見されるまで、シード点「ｐｒｅｆ」から線に沿って歩く。各線に対して、地味なゾーンにおける点および記号上の最後の点が記録される。このようにして、図４Ｆにおいて記号の外で分散して見られるように、背景または「満たされていない」モジュールと、前景または「満たされた」モジュールとを表す点の２つのセットが、後のプロセスのために利用される。点の背景セットはスターまたはマージン点と呼ばれる。
【００１９】
３６０において、２値画像（図４Ｃ）が、コントラスト画像から形成される。２値化は、ノイズを抑制するための効果的な方法であり、２値画像を処理するためのアルゴリズムは非常に効率がよい。直接的にグレイスケール画像を処理することと比較される場合は、２値画像は、縁の場所の精度が落ちる原因となる傾向があるが、精度のこの損失は、２値画像がＤａｔａＭａｔｒｉｘ記号を取り囲む地味なゾーン内で、マージン線の場所を突き止めるためのみに使用される場合は、許容可能である。従って、記述された実施形態は、正確な縁の場所を正確に突き止めることで、２値画像に依存することを避けながら、２値画像を処理する効率を高める。２値画像のために「満たされた」モジュールを「満たされていない」モジュールから識別するために使用されるスレショルド（ｔｈｒｅｓｈｏｌｄ）表面または平面は、３５０において、出力された２セットの点それぞれによって形成された平面を平均することによって計算される。２値画像は、スレショルド平面より上のコントラスト画像の任意の画素に黒色（前景）を割り当て、スレショルド平面より下の画素には白（背景）を割り当てる。２値化処理は、マージン点すべてを、すなわちマージン点の枠を含むコントラスト画像の長方形の小領域のみに有利に適用される。結果として収穫される２値画像は、ＤａｔａＭａｔｒｉｘ記号よりもわずかに大きいのみであり、周囲の領域ではなく、記号がさらなる分析ステップの焦点であることを確実なものにする。
【００２０】
３７０において、マージンの最初のセットが、連続した地味なゾーンまたはマージン点を接続することによって生成されて、マージン線を生み出し、マージン線は、図４Ｂにおいて、記号の上側および両側の外側の不連続なアウトラインとして見られ得る。必要であれば、点をスキップ（ｓｋｉｐ）して、マージン点の間に「背景」線を引く試みがなされる。背景線は、そのプロファイルの９５％がスレショルド平面より下である線である。結果は普通、例えば、図４Ｂにおける記号の上側および両側を取り巻くぎざぎざの線のような部分的アウトラインであるが、不連続線のセットであったりまたはまったく線などないこともあり得る。隣接したマージン線は合体して、図４Ｄにおける記号の上側および両側を取り囲む明るい白線によって示されるように、記号を囲むために必要とされる最小数のマージン線を生じる。理想的には、４つのマージン線が見い出され、記号の方向の大まかな指示を与える。新しいマージン点が、既存の線の形状に基づいて創造され得て、アウトラインの質を向上させる。
【００２１】
３８０において、マージン線がチェックされ、丁度４つの線が見出されない場合は、３９０でマージンを再生成するための試みがなされる。２値画像の隣接する満たされた／前景の画素がＤａｔａＭａｔｒｉｘ記号の特徴的な「Ｌ」を含む多数の「ブロッブ（ｂｌｏｂ）」を形成するという仮定に基づいてマージンを再生成するための２つの方法が試みられる。最初に、非常に派手な（ｎｏｉｓｙ）画像で起こるように、３７０からのマージン線が１つ以下である場合は、点「ｐｒｅｆ」に最も近いブロッブが特定される。輪郭ウォーカ（ｃｏｎｔｏｕｒ  ｗａｌｋｅｒ）はブロッブを横断して、２つの特定の数の画素のうちの１つの穴を飛び越えて、アウトラインを回復する。図４Ｅにおいてグレイの線として見られる輪郭は、ＤａｔａＭａｔｒｉｘ記号の特徴的な「Ｌ」の場所を突き止めるために捜索されて、ＤａｔａＭａｔｒｉｘ記号の特徴的な「Ｌ」は、正方形／長方形アウトラインを完成するもう１つ別のルーチンへ送られ得る。第２の再生成ルーチンは、例えば上に見出された「Ｌ」のような少なくとも２つの最適化されたマージン線を必要とする。最も長い最適化されたマージン線が、記号の方向を推定するために使用される。ほぼ直交する２つの太線は、１つは記号と整列するが、それらは、４つの新しいマージン点を見つけようと試みて、シード点を通って引かれる。これらの点は、前景／背景境界の前景側に起こる。新しいマージン点は、輪郭ウォーカを４度シードするために使用される。最も大きい「Ｌ」を生む輪郭が選択され、４つの最適化されたマージン線がこの輪郭から抽出される。これら４つの最適化されたマージン線は４００または４２０へ入力されて、そこで記号の大まかな整列が実行される。
【００２２】
輪郭ウォーカは、２値化されたＤａｔａＭａｔｒｉｘ画像において、隣接する前景画素によって形成されたブロッブの境界を見出す。ＤａｔａＭａｔｒｉｘ記号はしばしば細分化されて複数のブロッブとなるので、輪郭ウォーカは、不連続なブロッブを橋渡しするためのジャンプが許される。最大のジャンプステップのサイズは、２画素から４画素までの間から選択され得る。加えて、輪郭ウォーカは、異なるジャンプサイズを使用して、連続して同じ画像が要求され得る。輪郭ウォーカは、その輪郭がたどられるべきブロッブ上のシード点から出発する。シード点は、ブロッブの縁上に存在する必要はない。ルーチンは常に、時計回り方向に輪郭の外側を歩く。「ループバスタ（ｌｏｏｐ  ｂｕｓｔｅｒ）」特徴は、輪郭ウォーカが、ギャップをジャンプするという設計上のその特徴のゆえに、時計と逆回りのデッド（ｄｅａｄ）ループで終わってしまわないことを確実なものにする。輪郭ウォーカは、図４Ｅに示されるようなマーク付けされたビットマップならびに最も上の、最も下の、最も左のおよび最も右の輪郭における点の座標を入力する。穴をジャンプする輪郭ウォーカに対する別法は、領域成長または拡張技術を使用することによって、ブロッブ間の穴を橋渡し、または埋めることである。そのとき、規則的な輪郭ウォーカは、合体したブロッブのアウトラインを規定し得る。このアプローチは、「ジャンプする」輪郭ウォーカと類似する結果を生み出すが、より遅いことがあり得る。
【００２３】
図４Ｄにおいて明るい白線として示されている４つの最適化されたマージン線、および２値画像が、記号のアウトラインの大まかな整列を見出すために、４００または４２０で入力される。図３において見られるように、大まかな縁の整列が、３７０で生成された、または３９０で再生成された４つのマージン線上で実行され得る。各マージン線は、それが記号をカットする（ｃｕｔ）まで、その出発位置からシード点に向かってシフトされる。マージンが記号をカットする点は、ピボット点として規定されて、上記の線は、それが記号境界線と平行になるまで、そのピボット点の周りで回転される。この整列は、２値画像上でなされるので、それは大まかな整列であり、図４Ｆにおいて明るいグレイのアウトラインとして示される。４１０または４３０において、大まかに整列された境界線はチェックされて、例えば、相対する線の間の角度をチェックして、それが小さいことを確認することによって、またはコードアウトラインの縦横比が極度にゆがんでいないことを決定することによって、大まかに整列された境界線が意味をなすかどうかを決定する。大まかに整列された境界線が、許容可能な限界以内である場合は、記号の微細な整列が、元のグレイスケール画像上で実行される。
【００２４】
グレイスケール画像上で、微細な記号整列４４０を実行するために、２つの太い線が、記号の各側の縁に対して直角に引かれる。上記の線は、記号の外側から内側へ引かれ、記号の境界を横切る。ＳＵＭ機能が、各太線のプロファイルを生成するために使用される。プロファイルは、最初の重要な縁を見出すための、記号の外側から内側への試験官（ｅｘａｍｉｎｅｒ）である。これは、記号の境界上に２つの点を生み出し、どちらの端も１つあり、かつ図４Ｆにおける明るい白線で示されるように記号の境界を正確に規定し、かつ４５０で報告される。
【００２５】
図６は、デジタル化のために、標的の記号のアウトラインを決定するために、グレイスケール画像に作用するフロントエンド処理方法３００’を例示する。方法３００’によると、記号の輪郭または境界は、３６０でグレイスケール画像を２値化するために使用される境界画素情報を集めるために横断される。３２０で、グレイスケール画像は、参照またはシード点「ＰＲＥＦ」を見出すために分析される。点ＰＲＥＦは、記号内にある可能性が最も高い点として選択される。多くの技術が、ＰＲＥＦを見出すために使用され得る。例えば、ＰＲＥＦは、ユーザが画像化スキャナを向けるかまたは画像をスキャンする点として選択され、局所的な統計量が重大かつ相関している注目点として選択され得る。許容可能なＰＲＥＦが、３３０において見出され得ない場合は、上記方法は終了する。
【００２６】
３５０’において、記号のアウトラインが、輪郭ウォーカ、例えば、ステップ３８０を参照して上述されたような輪郭ウォーカを使用して横断される。輪郭ウォーカは、グレイスケール画像に作用して、ＰＲＥＦから出発して、記号の背景が遭遇されるまで、ＰＲＥＦから放射する画素の経路をたどる。輪郭ウォーカは、グレイスケール画像の隣接する満たされた／前景の画素は、記号のアウトラインを表す多くのブロッブを形成するという仮定に基づいて、グレイスケール画像のアウトラインを横断する。このようにして、記号の輪郭が構成されて、同時に、記号の境界での画素に関する情報が、画像における画素の位置の関数として収集される。例えば、周囲の画素に対する画素のコントラストのレベルまたは画素に関する統計的な情報のような情報であり得るこの画素情報は、３６０’で２値画像を計算するために使用される。この点以降、方法３００’は、記号のコーナがデジタル化のために報告される４５０を上述のように通過して進行する。
【００２７】
（ＤＰＭデジタイザ）
ＤＰＭデジタイザ１８０（図２）は、記号のマーク付けされたモジュールそれぞれが、明瞭なドットとして形成されるドット付けされたＤａｔａＭａｔｒｉｘ記号を処理するように適合される。しかしながら、デジタイザはなおも、概ね正方形の接続された記号モジュールで、通常の形式で印刷されたＤａｔａＭａｔｒｉｘに対処し得る。図５は、５１０で入力されるフロントエンドプロセッサ１３０によって提供される画像アウトラインを使用して、グレイスケール画像７４を復号するために、ＤＰＭデジタイザおよびＤＰＭ腹号器（図２）によって使用され得る１つの方法５００の流れ図の例示である。
【００２８】
記号を復号するための最初のステップは、記号におけるモジュールの周期性を決定することである。周期性は、印刷された表面における不規則性または明確なスキャン角度のために、記号における位置の機能として変化し得る。５２０で、記号モジュールの周期性は、フロントエンドプロセッサによって引き出されたアウトラインを使用して、記号の各側に沿って決定される。周期性の分析は、２つのパスにおいて、すなわち、概略的な分析パスおよび微細な分析パスにおいて実行され、双方ともグレイスケール画像上で実行される。概略的な分析において、固定された幅の切片が、周期性の指示を見出すために分析される。分析は、自己相関方法または高速フーリエ変換、または周期性抽出のために公知の任意の他の方法いずれかを使用して実行され得る。４つの側からこのようにして引き出された周期性は、結合されて、２つの数に到着して、その２つの数は、アウトラインの各側に沿ったモジュールの最初の列を覆う画素のアンカースワッス（ａｎｃｈｏｒ  ｓｗａｔｈ）の幅を表すが、相対する側の各対を１つの数が表す。周期性分析は、すべての側に対して成功しないことがあり得る。例えば、１つの側が切れ目のない線からなる場合は、その周期性は見出され得ない。
【００２９】
周期性の微細な分析において、最初のパスで引き出されるアンカースワッスの幅は、アウトラインの各側に沿ってアンカーを求めてスキャンするために使用される。サンプルは、２つのスレショルドを介して３つのカテゴリー（黒、白および背景）に分類される。単一線に沿ったすべてのアンカーは、同じ色付けのブロッブから選択される。各アンカーはまた、スキップされた（損傷を受けているか、または検知されなかったかいずれかの）アンカー点を補償するために、インデックスを与えられる。すべての側がアンカーを生み出すことができるわけではない。個々のドットで形成されていないＤａｔａＭａｔｒｉｘの既知の切れ目のない側に対しては、このステップは回避される。
【００３０】
各側に沿ったアンカーに対してただ１つの色が使用されるけれども、これは、画像コントラスト逆転のための適切な取り扱いを除外しない。なぜならば、異なる側は、異なる色付けのアンカーを許容するからである。異なる色付けのアンカーを有する２つの隣り合う側は、グリッドを形成する場合、アンカーの段階的な位相シフトを生み出す。
【００３１】
５３０において、グリッドは、５２０で決定された周期性を使用して生成される。グリッドを生成することに加えて、５３０において、４つの側からの、おそらく一貫性のない周期性分析結果の意味を理解するために、発見的方法による試みがなされる。発見的方法によって決定された可能性は、ＤａｔａＭａｔｒｉｘに対する法定コードサイズと比較される。発見的方法の結果は、どちらの側がドットから成るか、どちらが切れ目がないかの指示を含み、かつどのコーナがＤａｔａＭａｔｒｉｘ記号の出発コーナか、または記号が生成される方向にある左肩コーナか、ならびに横列および縦列の数の見地からのグリッドサイズをも暗示する。
【００３２】
出発コーナおよびグリッドサイズがいったん決定されると、グリッドが、モジュールの最も外側の列の中心線の（４つの）交差点を使用して生成される。中心線それぞれは、アンカー列の中心線であり得るし、または切れ目のない縁の整列ルーチンから引き出され得る。４つの交差点すべてが、分解されるわけではない場合、グリッドは既知のアンカーを使用して生成される。これは、例えば、アンカーが４つの側のうちの２つに見出されるのみの場合に起こる。
【００３３】
５４０において、グリッドは、ＤａｔａＭａｔｒｉｘ記号の各モジュールに対応して、プリントマークの存在または非存在を表す２つの値のうち１つを使用してデジタル化される。デジタル化は、一度に１タイル実行されて、各タイルは５×５セットのモジュールを含む。デジタル化は、コーナのタイルから始まり、縁沿いのタイルへと進む。タイルの完全なリングがデジタル化されると、内側の次の層がデジタル化されるが、次のリングからのタイルは、それぞれわずかにブートストラップ（ｂｏｏｔｓｔｒａｐ）のために重なる。この処理は、デジタル化されるべきモジュールがもはやなくなるか、または矛盾する入力条件のために１つのタイルがデジタル化され得なくなるまで、繰り返される。この処理は、局所のモジュールの規定のみが、所与のタイルの入力条件を決定するために使用されることを確実なものにする。なぜならば、局所のモジュールの規定は、記号内で画像コントラスト逆転に応じるためにシフトし得るからである。
【００３４】
タイルにおける任意の未知のモジュールの状態は、タイルにおける既知のモジュールの状態に基づいて決定される。最初は、既知のモジュールは、デジタル化が開始されたばかりのときは、選択されたＤａｔａＭａｔｒｉｘのサイズの予測に基づいて、ドットとして、または非ドットとして知られているようなモジュールである。後に、処理が内側のタイルに対して行われているとき、既知のモジュールはこれまでにデジタル化されたタイルからのものである。次に、マッチしたフィルタが、入力されたモジュールに基づいて生み出される。入力された各モジュールに対し、同じ数の画素が標本として抽出される。異なるモジュール内の同じ相対的な位置からの画素が、ドットを非ドットから分離する際に統計学上の重要性を提示するものを求めて分析される。次に、このマッチしたフィルタが、未知のモジュールすべてに適合されて、Ｏｔｓｕスレショルディングアルゴリズムがドットを非ドットから分離するために使用される。
【００３５】
ＤａｔａＭａｔｒｉｘ記号は、多くのタイルにきちんと分離され得ないので、いくつかのモジュールは２度以上、各度ごとに異なるタイルのコンテクスト内でデジタル化され得る。異なるタイルとは異なるデジタル化結果を有する任意のモジュールは、ＤａｔａＭａｔｒｉｘの復号に対しては削除箇所としてマーク付けされる。５５０において、復号器が３度コールされるが、一度は本来の削除箇所へマップされた削除箇所に対して、一度はドットへ、および一度は非ドットへの３度である。これらの試みのうちどれ１つとして成功した復号を生ぜず、かつ記号はなおも再整列されない（５７５）場合は、記号は５８０で再整列され、デジタル化が再び始まる。
【００３６】
フロントエンドプロセッサによって生成されたアウトラインを使用して、復号することができなかった記号を再整列するために、もとのグレイスケール画像がアクセスされて、正しいアウトラインを決定するための試みを行う。上記再整列は、概略的なパス周期性分析で決定されるモジュールの幅を利用する。ドットから成る側の場合は、各側は、４つの等しい長さのセグメントに分けられて、各セグメントの中心は、いくつかの平行位置の標準偏差を計算することによって求められる。結果として生じる４つの点を寄せ集めて最小２乗線を形成する場合に、異常値（ｏｕｔｌｉｅｒ）がチェックされ、もし見つかれば除外される。切れ目のない側の場合、幅があまりにも広い場所では中間点は考慮されない（これは、縁モジュールは次のものに接続され得ていることを意味する）ことを確かめながら、切れ目のない側の中間点はチェックされる。次に、新しいアウトライン側は、５２０での周期性生成の微細分析パスで使用される。
【００３７】
上記から理解され得るように、記述された２次元記号デジタル化システムは、記号の境界を決定するためにグレイスケール画像の２値化バージョンを使用することによって、かつ復号のためにデジタル化される画像を構成するために境界情報を使用することによって、不規則な表面上に印刷された２次元の記号を効率的に処理する。本発明は、ある程度詳細に記述されたけれども、本発明は、添付された特許請求の範囲の精神または範囲内にある、開示されたデザインからの変容例および変更例すべてを含むことが意図されている。
【図面の簡単な説明】
【００３８】
【図１】図１は、本発明の一実施形態に従って構成された復号システムを有する画像化を基礎とする直接部分マーキングスキャナの概略構成図である。
【図２】図２は、図１の復号システムの概略構成図である。
【図３】図３は、本発明の一実施形態に従って記号を処理するために、図２のフロントエンドプロセッサによって使用される例示的な方法を概説する流れ図である。
【図４Ａ】図４Ａは、図３の方法の実行の間、作用を受けた画像である。
【図４Ｂ】図４Ｂは、図３の方法の実行の間、作用を受けた画像である。
【図４Ｃ】図４Ｃは、図３の方法の実行の間、作用を受けた画像である。
【図４Ｄ】図４Ｄは、図３の方法の実行の間、作用を受けた画像である。
【図４Ｅ】図４Ｅは、図３の方法の実行の間、作用を受けた画像である。
【図４Ｆ】図４Ｆは、図３の方法の実行の間、作用を受けた画像である。
【図５】図５は、図２のＤＰＭデジタイザによって使用される例示的な方法を概説する流れ図である。
【図６】図６は、本発明の一実施形態に従って、記号を処理するために、図２のフロントエンドプロセッサによって使用される例示的な方法を概説する流れ図である。
【図１】
2008533546.tif 000002
【図２】
2008533546.tif 000003
【図３】
2008533546.tif 000004
【図４Ａ】
2008533546.tif 000005
【図４Ｂ】
2008533546.tif 000006
【図４Ｃ】
2008533546.tif 000007
【図４Ｄ】
2008533546.tif 000008
【図４Ｅ】
2008533546.tif 000009
【図４Ｆ】
2008533546.tif 000010
【図５】
2008533546.tif 000011
【図６】
2008533546.tif 000012
【国際調査報告】
2008533546.tif 000013