(57)【特許請求の範囲】
【請求項１】
平面において無間隔的に配列された、異なる光学特性を有する矩形の単元モジュールを含む矩形のコードパターンを備える二次元バーコードであって、
前記コードパターンにおける単元モジュールは、複数の矩形のマクロモジュールのそれぞれを分割したものであり、
前記マクロモジュールはNum×Num個の単元モジュールを含み、そのうち、Numは３よりも大きい自然数であり、
各マクロモジュールは、固定データ長を有するデータコードワードを記憶する単元モジュールと、
コードパターンにおけるこのマクロモジュールの位置を表現するクラスター番号を記憶する単元モジュールと、
を有し、
前記マクロモジュールは、最周辺の一回り全てが深い色の単元モジュールである黒枠マクロモジュールと、
最周辺の一回り全てが浅い色の単元モジュールである白枠マクロモジュールと、
からなり、
前記データコードワードと前記クラスター番号は枠以内の単元モジュールに格納され、
前記黒枠マクロモジュールと前記白枠マクロモジュールとがコードパターンにおいて交互に配列されることを特徴とする二次元バーコード。
【請求項２】
前記コードパターンはMnum×Mnum個の前記マクロモジュールを含み、
そのうち、Mnumは１よりも大きい奇数であり、
前記コードパターンの中央の前記マクロモジュールのクラスター番号は０であり、
前記コードパターンの中央から境界に向かって、前記マクロモジュールのクラスター番号は層に応じて順に増えていくことを特徴とする請求項１記載の二次元バーコード。
【請求項３】
異なる前記マクロモジュールにおいて、
前記クラスター番号情報を格納する、クラスター番号の単元モジュールの位置と個数が同じであり、
前記クラスター番号の単元モジュールに格納される値は、該マクロモジュールのコードパターンにおける層数が、前記クラスター番号の単元モジュールの最大な記憶値に対してモジュラス演算を行って取得した数値であることを特徴とする請求項２記載の二次元バーコード。
【請求項４】
バイナリデータストリームをコンピュータによりコードパターンに符号化する二次元バーコードの符号化方法であって、
該二次元バーコードは、
平面において無間隔的に配列された、異なる光学特性を有する矩形の単元モジュールを含む矩形のコードパターンを備える二次元バーコードであって、
前記コードパターンにおける単元モジュールは、複数の矩形のマクロモジュールのそれぞれを分割したものであり、
前記マクロモジュールはNum×Num個の単元モジュールを含み、そのうち、Numは３よりも大きい自然数であり、
各マクロモジュールは、固定データ長を有するデータコードワードを記憶する単元モジュールと、
コードパターンにおけるこのマクロモジュールの位置を表現するクラスター番号を記憶する単元モジュールと、
からなり、
該符号化方法は、
（ａ）先ず、前記バイナリデータストリームを特定なビット長を有する情報データコードワードに分割するステップと、
（ｂ）次に、前記情報データコードワードを、誤り訂正アルゴリズムにより計算し、誤り訂正コードワードを生成するステップと、
（ｃ）マクロモジュール各々の最周辺の一回りを構成する枠単元モジュールと、二つのクラスター番号の単元モジュールとを含む、コードパターンの本体部をメモリの中で生成するステップと、
（ｄ）コードパターンの中央から時計回りの螺旋方向に、データコードワードと誤り訂正コードワードをコードパターンに充填させることにより、コードパターンの画像ファイルを生成するステップと、
を含み、
前記ステップ（ｃ）において生成された前記マクロモジュールは、該マクロモジュールの枠単元モジュールが深い色のモジュール、或いは枠単元モジュールが浅い色のモジュールであり、
この両種のマクロモジュールがコードパターンにおいて交互に配列され、
前記データコードワード及びクラスター番号は枠内の単元モジュールに格納されることを特徴とする二次元バーコードの符号化方法。
【請求項５】
前記ステップ（ａ）において、
まず、前記マクロモジュールの行ごとに含まれる単元モジュールの個数Numを決定しておき、
次に、前記クラスター番号モジュールの個数をNum１０として、前記情報データコードワードの特定のビット長Num２０を、
Num×Num−（Num−１）×４−Num１０
により計算し、
前記ステップ（ｃ）においては、
先ず、前記情報データコードワードと誤り訂正コードワードとの個数の和を計算し、
この和が前記コードパターンに含まれるマクロモジュールの数（Mnum×Mnum）以下であり、
そのMnumは１よりも大きい奇数であることを特徴とする請求項４記載の二次元バーコードの符号化方法。
【請求項６】
前記コードパターンの中央に位置する前記マクロモジュールのクラスター番号は０であり、
前記コードパターンの中央から境界に向かって、前記マクロモジュールのクラスター番号は、層に応じて順に増えていくことを特徴とする請求項５記載の二次元バーコードの符号化方法。
【請求項７】
前記ステップ（ｃ）において、前記クラスター番号の単元モジュールに格納された値は、該マクロモジュールのコードパターンにおける位置に対する中央のマクロモジュールの層数が前記クラスター番号の単元モジュールの最大な記憶値に対してモジュラス演算を行って取得した数値であることを特徴とする請求項４記載の二次元バーコードの符号化方法。
【請求項８】
デジタルカメラとコンピュータによりコードパターンをバイナリデータストリームに回復する二次元バーコードの復号化方法であって、
該二次元バーコードは、
平面において無間隔的に配列された、異なる光学特性を有する矩形の単元モジュールを含む矩形のコードパターンを備える二次元バーコードであって、
前記コードパターンにおける単元モジュールは、複数の矩形のマクロモジュールのそれぞれを分割したものであり、
前記マクロモジュールはNum×Num個の単元モジュールを含み、そのうち、Numは３よりも大きい自然数であり、
各マクロモジュールは、固定データ長を有するデータコードワードを記憶する単元モジュールと、
コードパターンにおけるこのマクロモジュールの位置を表現するクラスター番号を記憶する単元モジュールと、
を有し、
前記マクロモジュールは、最周辺の一回り全てが深い色の単元モジュールである黒枠マクロモジュールと、
最周辺の一回り全てが浅い色の単元モジュールである白枠マクロモジュールと、
からなり、
該復号化方法は、
Ｉ. 写真を撮ることによりコードパターンの、画素ごとのグレイ値を含む画素マトリックスのグレイスケールデジタル画像を取得するステップと、
II. グレイスケールデジタル画像における異なる画素のグレイ値の分布を統計し、前記統計値に従って閾値を選択して、グレイスケール画像を２値画像に変換するステップと、
III. 前記２値画像における浅い色の画素の各々を検出し、それと隣接された上、下、左、右の四つの画素で少なくとも一つが深い色の画素であると、この画素は境界画素として標識され、境界画像が得られ、前記境界画像における直線を検出して直線方程式を取得し、且つ、前記直線方程式を解いてマクロモジュールごとの四角座標を求めるステップと、
IV. マクロモジュールごとの四角座標の補間値に基づいて、マクロモジュール内の単元モジュール各々の座標を算出するステップと、
V. 前記単元モジュールの座標に応じて、前記２値画像のデジタル信号から該単元モジュールに記憶された０又は１のビット数を読み出して、コードワードマトリックスを取得するステップと、
VI. （ａ）前記データマトリックスに対して、それぞれの四つの異なる方向から、既知のクラスター番号モジュールの位置と単元により、マクロモジュールごとの一つずつ可能的なクラスター番号を取得するステップと、
（ｂ）方向ごとに、それぞれに、マクロモジュールごとの可能的なクラスター番号と、その右方および下方に隣接されたマクロモジュールに応じた可能的なクラスター番号の差分の絶対値とをそれぞれに計算し、取得した絶対値を累計してこの方向の得点とするステップと、
（ｃ）その四つの方向の得点を比較し、その最少の得点の方向をコードパターンの正しい方向とするステップとによって、コードワードマトリックスの方向を判断するステップと、
VII. コードワードマトリックスの対称関係によって中央コードワードを決定するステップと、
VIII. 前記正しい方向と中央コードワードによって、中央コードワードから時計回りの方向に応じて前記データコードワードマトリックスをデータコードワードシーケンスに回復するステップと、
を含み、
前記ステップIIIにおいて境界画像を取得した後、黒枠マクロモジュールと白枠マクロモジュールが交互に配列された場合の対角において両種類の特定なパターンモードをモールディングボードとして、整合計算によりマクロモジュールごとの四角座標を検出し、そして直接にステップIVに入ることを特徴とする二次元バーコードの復号化方法。
【請求項９】
前記ステップVIIIにおいて、リード・ソロモン誤り訂正のアルゴリズムを用いて前記データコードワードシーケンスに存在する誤りを訂正することを特徴とする請求項８記載の二次元バーコードの復号化方法。
【請求項１０】
前記ステップVIIにおいて、コードパターンの中央に対応するマクロモジュールのデータコードワードが複数の可能性がある場合に、候補となる中央マクロモジュールのそれぞれに対して、層ごとにその周辺の全てのデータコードワードのクラスター番号を累計し、且つ、１回の累計ごとに、その累計の和からその位置の候補中央マクロモジュールに対する正しいクラスター番号値を差し引き、異なる中央マクロモジュールに対する得点を比較し、その最大な得点が得られたものを正しい中央と決定することを特徴とする請求項９記載の二次元バーコードの復号化方法。
【請求項１１】
前記ステップIIは、グレイスケール画像を重ならない又は一部が重なる領域に分割して、各領域のグレイスケール値の分布をそれぞれ統計し２値化の閾値を決定して２値化させられ、重なる領域は領域自身の閾値及びそれに隣接した領域の閾値を重み付き平均して該領域の２値化閾値として２値化させ、その２値化された各部分をさらにコードパターンに対応する２値化画像に組み合わせることを特徴とする請求項１０記載の二次元バーコードの復号化方法。
【請求項１２】
前記ステップIIIにおいて境界画像を取得するステップとは、前記２値画像における深い色の画素の各々を検出し、それと隣接された上、下、左、右の四つの画素で少なくとも一つが浅い色の画素であると、この画素が境界画素として標識されることを特徴とする請求項１１記載の二次元バーコードの復号化方法。
【発明の詳細な説明】
【産業上の利用分野】
【０００１】
本発明は、二次元バーコードと、データを符号化して当該二次元バーコードのコードパターンを生成し、このコードパターンを復号化してデータを復元させる方法に関するものである。
【従来の技術】
【０００２】
一般に、二次元バーコードは、特徴モード領域と、フォーマット情報領域と、データコードワード領域との三つの部分から構成される。その中、特徴モード領域は、アルゴリズムと定位コードパターンとを識別するように画像をガイドし、フォーマット情報領域は、コードパターンフォーマットとデータ誤り訂正との描写に関するパラメーターを格納し、データコードワード領域は、誤り訂正符号化アルゴリズムにより符号化されたデータを格納する。特徴モード領域とフォーマット情報領域がある程度まで破壊されると、コードパターンを識別することができなくなるため、この二つの領域がコードパターンにおいて致命的な領域(vulnerable area)となされ、二次元バーコードの信頼性が低減させられる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
図１に示されるように、PDF４１７コードの構成を示す図であって、コードパターンにおける左右両端の広さの異なる縦線がその特徴モード領域１０であり、コードパターンにおける左右両端の特徴モード領域１０内の一部がそのフォーマット情報領域２０であり、もし、特徴モード領域１０とフォーマット情報領域２０がある程度の破壊を受けたら、該コードパターンは正確に識別できない。
【０００４】
また、図２に示されるように、QRコードの構成を示す図であって、コードパターンにおける上部左右両角と下部左角からなる「回」字状の領域がその特徴モード領域３０であり、コードパターンにおける三つの角近傍にある特徴モード領域３０内に破線で囲んだ部分がそのフォーマット情報領域４０であり、もし特徴モード領域３０とフォーマット情報領域４０とがある程度の破壊を受けたら、該コードパターンは正確に識別できない。
【０００５】
本発明は、現有の二次元バーコードの特徴モード領域とフォーマット情報領域が比較的に集中され、破壊(vulnerable)されやすく、耐変形能力 (anti-deformation)が悪いという欠点を解決するためになされたものであり、二次元バーコードと、データを符号化して該二次元バーコードのコードパターンを生成し、このコードパターンを復号化してデータを復元する方法とを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る二次元バーコードは、矩形のコードパターンを備えるものであり、前記コードパターンは、平面において無間隔的に配列された、異なる光学特性を有する矩形の単元モジュールを含み、前記コードパターンにおける単元モジュールは、複数の矩形のマクロモジュールのそれぞれを分割したものであり、前記マクロモジュールは Num×Num個の単元モジュールを有し、そのうち、Numは３よりも大きい自然数であり、マクロモジュールごとに固定データ長を有するデータコードワードを記憶する単元モジュールと、コードパターンにおけるこのマクロモジュールの位置を表現するクラスター番号を記憶する単元モジュールとを有する。
【０００７】
本発明の実施の形態によると、本発明の二次元バーコードは、前記マクロモジュールは、周辺の一回り全てが濃い色の単元モジュールである黒枠マクロモジュールと、周辺の一回り全てが薄い色の単元モジュールである白枠マクロモジュールとを含み、前記データコードワードとクラスター番号が枠以内の単元モジュールに格納され、前記黒枠マクロモジュールと白枠マクロモジュールとがコードパターンにおいて交互に配列されたことを特徴とする。
【０００８】
また、本発明の二次元バーコードは、前記コードパターンがMnum×Mnum個の前記マクロモジュールを含み、そのうち、Mnumは１よりも大きい奇数であり、前記コードパターンの中央の前記マクロモジュールのクラスター番号は０であり、前記コードパターンの中央から境界に向かって、前記マクロモジュールのクラスター番号は層に応じて順に増えていくことを特徴とする。
【０００９】
また、本発明の二次元バーコードは、相異なる前記マクロモジュールにおいて、前記クラスター番号情報を格納するクラスター番号の単元モジュールの位置と個数が同じであり、前記クラスター番号の単元モジュールに格納される値は、該マクロモジュールのコードパターンにおける層数が、前記クラスター番号の単元モジュールの最大記憶値に対してモジュラス演算を行って取得した数値であることを特徴とする。
【００１０】
さらに、本発明は、バイナリデータストリームをコンピュータによりコードパターンに符号化する二次元バーコードの符号化方法であって、
（ａ）先ず、前記バイナリデータストリームを特定のビット長を有する情報データコードワードに分割するステップと、
（ｂ）次に、前記情報データコードワードを、誤り訂正アルゴリズムにより演算し、誤り訂正コードワードを生成するステップと、
（ｃ）マクロモジュール各々の枠単元モジュールと、二つのクラスター番号の単元モジュールとを含むコードパターンの主枠をメモリの中で生成するステップと、
（ｄ）コードパターンの中央から時計回りの螺旋方向に、データコードワードと誤り訂正コードワードをコードパターンに充填させることにより、コードパターンの画像ファイルを生成するステップと、を含む。
【００１１】
さらに、本発明は、デジタルカメラとコンピュータによりコードパターンをバイナリデータストリームに復元する二次元バーコードの復号化方法であって、
I. 写真を撮ることによりコードパターンの、画素ごとのグレイ値を含む画素マトリックスのグレイスケールデジタル画像を取得するステップと、
II. グレイスケールデジタル画像における異なる画素のグレイ値の分布を計算し、前記計算値に従って閾値を選択してグレイスケール画像を２値画像に変換するステップと、
III. 前記２値画像における薄い色の画素の各々を検出し、それと隣接した上、下、左、右の四つの画素で少なくとも一つが濃い色の画素であると、この画素は境界画素として認識し、境界画像が得られ、前記境界画像における直線を検出して直線方程式を取得し、且つ、前記直線方程式を解いてマクロモジュールごとの四角（よすみ）の座標を求めるステップと、
IV. マクロモジュールごとの四角の座標の補間値に基づいて、マクロモジュール内の単元モジュール各々の座標を算出するステップと、
V. 前記単元モジュールの座標に応じて、前記２値画像のデジタル信号から該単元モジュールに記憶された０又は１のビット値を読み出して、コードワードマトリックスを取得するステップと、
VI. （ａ）前記データマトリックスに対して、それぞれの四つの異なる方向から、既知のクラスター番号モジュールの位置と単元により、マクロモジュールごとに一つずつクラスター番号を取得するステップと、（ｂ）方向ごとに、それぞれに、マクロモジュールごとのクラスター番号と、その右方および下方に隣接したマクロモジュールに応じたクラスター番号の差分の絶対値とを計算し、取得した絶対値を累計してこの方向の得点とするステップと、（ｃ）その四つの方向の得点を比較し、最少得点の方向をコードパターンの正しい方向とするステップとによって、コードワードマトリックスの方向を判断するステップと、
VII. コードワードマトリックスの対称関係によって、中央コードワードを決定するステップと、
VIII. 前記正しい方向と中央コードワードによって、中央コードワードから時計回りの方向に応じて、前記データコードワードマトリックスをデータコードワードシーケンスに復元するステップと、を含む。
【００１２】
本発明に開示された二次元バーコードは単元モジュールをマクロモジュールに組み合わせ、マクロモジュールごとにコードパターンにおける位置を標識するクラスター番号の単元モジュールを設け、コードパターンにおいてマクロモジュールの各々が独立的に定位されるため、パターンが一旦に破損されたり汚されたりした部分をいずれも定位することができ、識別アルゴリズムは、現有のマトリックス式の二次元バーコードよりも、消去誤りの存在を有効に検出することができるため、誤り訂正性能を高めることができる。これは、コードワードストリームにおいて、RS誤り訂正アルゴリズムに対して、消去誤り（既知の位置の誤りを消去誤りと称する）の誤り訂正性能は代用誤り（未知の位置の誤りを代用誤りと称する）の誤り訂正性能の２倍にもあるからである。これにより、コードパターンの耐破損、耐汚染、耐変形能力が効果的に確保されるようになる。
【００１３】
また、コードワードずつに一つのマクロモジュールに対応付けているため、全てのコードワードがクラスターに分けられ、中央から外への時計回り方向に層ごとに配列され、同一層のコードワードのクラスター番号は同じであり、クラスター番号は最大になった後にまた０に戻り、このような配列方式は、復号化アルゴリズムを確実にガイドしてコードパターンの方向を定位し、さらに始めのコードワードを決定することができる。
【００１４】
また、異なるマクロモジュールのつなぎ合わせた所、すなわちマクロモジュールの四角に特定なパターンモードが形成されるため、マクロモジュールの各々とその周辺の他のマクロモジュールとの間に顕著な境界が存在するようになり、モールディングボード整合アルゴリズムにより速く確実にマクロモジュールの各々を検出して定位し、復号化方法を簡略化して、復号率を向上させることができる。境界の画像においてマクロモジュールの枠で著しい特徴を有する直線が形成されるため、直線のパラメーターを検出することにより、快速にコードパターンの回転角度を決定し、マクロモジュールの四角の座標を定位することができる。
【００１５】
さらに、白枠マクロモジュール及び黒枠マクロモジュールが交互に配列されるため、コードパターンにおいて、コードパターンの濃い色のモジュールと薄い色のモジュールの分布を均一に保持させるように白枠マクロモジュールと黒枠マクロモジュールが交互に配列され、コードパターンを識別する時の漏斗効果を回避し、コードワードを誤認する可能性を低減させる。
【００１６】
一方、符号化演算においては、所定の誤り訂正レベルを選んで分割されたコードワードのビットストリームに対して、形成されたコードパターンがフォーマット情報領域を必要としないように誤り訂正演算を行うことにより、従来の二次元バーコードよりも傷を受けやすい部品が一つ少なくなり、コードパターンの信頼性を向上させることになる。
【００１７】
なお、復号化の時、画像からデータへの転換は、単元モジュールを単位とすることではなく、マクロモジュールを単位（PDF４１７と同じ）として、その識別率が現在のいずれのマトリックス式二次元バーコードよりも高い（これは、デジタル画像において、マクロモジュールは、単元モジュールの形状が方形と大きく異なっても、いつも優れた方形の特徴を保持することができるからである）。
【００１８】
さらに、コードパターンは濃い色のマクロモジュールと薄い色のマクロモジュールとが交互に配列されているため、パターンには大面積の同色モジュールが現れることがなく、したがって、他の二次元バーコードで用いられるモジュールマスキング（masking）技術を略することができる。また、コードパターンにおいて、深い及び薄い色のモジュールの分布が均一であるため、サーマルプリンタ（バーコードの一番代表的な出力装置）はパターンを出力する場合に、プリントヘッドの発熱ユニットの冷熱が均一に交互する状態で動作するように確保させることができ、したがって、出力される画像の精度がよく確保される。
【発明の実施の形態】
【００１９】
符号化された情報は一連のバイナリ数であり、ビットストリームとして見てもよく、該ビットストリームはある一定の長さによって若干のビット数が同じのデータコードワードに分割され、更に、リード・ソロモン（Reed Solomon）符号化アルゴリズムを適用して誤り訂正コードワード（誤り訂正コードワードはコードパターンが復号化されてデータに復元する時に誤り訂正の役割を果たす）を生成し、誤り訂正コードワードはデータコードワードの中に組み込まれて、新しいビットストリームを形成し、さらに、一緒に符号化されて二次元バーコードになる。
【００２０】
図３に示されるように、本発明の二次元バーコードのコードパターンであって、このコードパターンは矩形であり、同様に矩形である複数のマクロモジュール、すなわち、図面のようなマクロモジュール５０１及びマクロモジュール５０２により構成される。マクロモジュールの各々が、更にNum×Num（Numは自然数、且つ、Num＞３）個の単元モジュールが矩形に配列されていて、それぞれの単元モジュールの形状も矩形であり、単元モジュールの各々が濃い色又は薄い色のいずれか一つであってもよいため、単元モジュールごとに１ビットの情報（濃い色は１、薄い色は０、又はその反対）が記憶されている。一つのコードワード（データコードワード及び誤り訂正コードワードを含む）はコードパターンにおける一つのマクロモジュールに対応付けている。
【００２１】
本発明の二次元バーコードのコードパターンは、２種類のマクロモジュールが横方向と縦方向との二つの方向で交互に配列されていて、それらは、白枠マクロモジュールと黒枠マクロモジュールである。図４は、本発明の二次元バーコードのコードパターンにおける白枠マクロモジュールと黒枠マクロモジュールの構成を示す図であり、マクロモジュールの各々が単元モジュール１００からなることがわかり、枠部２００と、コードワード記憶部と、クラスター番号部とを含む。マクロモジュールの最周辺の一回りの単元モジュールが枠部２００であり、すなわち枠単元モジュール２００はマクロモジュールの最外層に位置しており、マクロモジュールごとに一つ又は複数のクラスター番号モジュールを有することができ、該クラスター番号モジュールは、枠モジュールを除くどの場所にも位置することができる。
【００２２】
次に、一実施の形態によって本発明の二次元バーコードにおけるマクロモジュールについて詳細に説明する。図５に示されるように、本発明に係る実施の形態の二次元バーコードのコードパターンにおけるマクロモジュールの構成を示す図であって、その行ごとに６個の単元モジュール１００を有し、合計３６個あり、その最周辺の一回りの枠モジュール２００は合計２０個あり、枠モジュール内にはデータモジュール４００が合計１４個あり、クラスター番号モジュール３００は合計２個あることがわかる。図６に示されるように、本発明に係る二次元バーコードのコードパターンにおけるマクロモジュールの配列方式を示す図であって、濃い色のモジュールが黒枠モジュール、薄い色のモジュールが白枠モジュールであり、マクロモジュールの配列の順序は図面のシリアル番号で示され、これは、コードワードが記憶される順序（中央から外へ時計回りに螺旋式により配列）でもあり、コードパターンの各々の一辺におけるマクロモジュールの個数がMnum（Mnumは１よりも大きい奇数）であり、このコードパターンには合計してMnum×Mnum個のマクロモジュールがある。コードパターンにおけるマクロモジュールを中央から外へ向かって分層すると、１番目のモジュールが第１の層であり、２〜９番目のマクロモジュールが第２の層になされ、１０〜２５番目のマクロモジュールが第３の層になされ、これに準じて類推する。図６に示すように、コードパターンは合計３層のマクロモジュールを有する。同一層に位置するマクロモジュールは同じクラスター番号を有する。
【００２３】
第１の層のマクロモジュールを第０のクラスター、第２の層のマクロモジュールを第１のクラスター、第３の層のマクロモジュールを第３のクラスターと定義し、これに準じて類推する。マクロモジュールにおけるクラスター番号モジュール３００は、このクラスター番号を記憶するためのものであり、クラスター番号がクラスター番号モジュールの記憶範囲を超えると、クラスター番号モジュールが符号化可能な総数によりモジュラス演算を行う。例えば、マクロモジュールごとに二つのクラスター番号モジュールがあると、第１の層からクラスター番号はそれぞれに０、１、２、３、０、１、２、３、……のようになる。
【００２４】
図７に示されるように、本発明に係る二次元バーコードの符号化のプローチャートであって、先ず、最初のデータを特定なバイナリビット長を有する情報データコードワードに転換し、そして、リード・ソロモン符号化アルゴリズムを用いて、誤り訂正コードワードを生成して情報データコードワードに追加し、その後に、データコードワードと誤り訂正コードワードの個数によってコードパターンのサイズを決定し、メモリの中で、マクロモジュールの枠とマクロモジュールごとのクラスター番号モジュールとを含むコードパターンの主枠を生成し、コードパターンの中央から時計回りに螺旋方向に沿って、データコードワードと誤り訂正コードワードをコードパターンの中に充填させることにより、コードパターンの画像ファイルを生成し、符号化の動作が終了される。
【００２５】
復号化と符号化のフローは反対であり、復号化の前にマクロモジュールの大きさ、すなわちマクロモジュールごとに含まれている単元モジュール数及びその対応したコードワードのビット数を取得しておくとともに、それぞれのマクロモジュールの中のクラスター番号の単元モジュールの位置と単元モジュール数（一つの具体的な実施例に対しては、これらのパラメーターは予めに定められている）を取得する。次に、この復号化のステップについて説明する。
【００２６】
（１）デジタルカメラを用いて、写真を撮ることによりコードパターンのグレイスケール画像を取得する。このような画像信号のメモリの中での存在方式であって、画素ごとのグレイ値を含んだ画素マトリックスであってもよく、このようなグレイスケール画像を直接にディスプレイ装置で表示してもよい。
【００２７】
（２） グレイ画像における異なる画素のグレイ値の分布を計算する。例えば、柱状図統計を実行する。図１３に示されるようにグレイスケールの分布を示す柱状図であり、ダブルピークが明らかに見えられ、その左側のピーク値１０１は薄い色の画素の個数を、右側のピーク値１０３は濃い色の画素の個数を示し、両ピーク値間のグレイ値１０２は２値化された閾値として用いられる。
【００２８】
（３） 異なる画素のグレイ値の分布により閾値を定め、コードパターンのグレイスケール画像を２値画像に転換する。この閾値の定め方法は柱状図ダブルピーク法であってもよく、他の方法であってもよい。図８に示されるように、本発明の復号化方法によって取得した２値画像であるが、全ての画素の値が図において濃い色と薄い色との二つの色として現れている。
【００２９】
（４）上記２値画像に対して境界検出を行って、薄い色の画素の各々に対して、それと隣接した上、下、左、右の四つの画素のうち、濃い色の画素が一つだけあったら、該画素を境界画素と認識する。一方、濃い色の画素の各々に対して、それと隣接した上、下、左、右の四つの画素のうち、薄い色の画素が一つだけあったら、該画素を境界画素と認識してもよい。図９に示されるように、コードパターンの境界画像を示している。
【００３０】
（５） 上記した境界画像中の直線（連続又は連続しないものを含む）を検出して、直線方程式の組を取得する。コードパターンには交互に配列された白枠マクロモジュールと黒枠マクロモジュールがあるため、検出された直線がマクロモジュールの境界線を切り出す。図１０に示されたように、霍夫アルゴリズム（Hough Transform）を用いて、上記した境界画像の中で直線を検出した後の図である。
【００３１】
（６） 図１１に示すように、上記の直線方程式の組を解いてマクロモジュールごとの四角の座標を求める。
【００３２】
（７）マクロモジュールの四角の座標と既知の単元モジュールのサイズに基づいて、補間アルゴリズムを用いてマクロモジュール内の単元モジュール各々の中央座標を計算し、単元モジュールの中央座標によって、２値画像からこの単元モジュールに記憶されたビット値（０又は１）を読み取る。該単元モジュールに記憶されたビット値は、その中央座標の周辺の画素値を計算することにより定めてもよい。そして、上記したステップによって、復号化されたコードパターンに応じたデータコードワードマトリックスが得られる（データコードワードと誤り訂正コードワードを含み、コードワードずつにクラスター番号情報を含み、誤り訂正前にクラスター番号情報を消去させる必要がある）。
【００３３】
（８）復号化されたコードパターンの方向は写真を撮る場合、一定の回転角度が発生する可能性があるため、復号化の時にコードパターンの正しい方向を判断する必要があり、この判断のステップとして、（ａ）前記データマトリックスに対してそれぞれの四つの異なる方向から、既知のクラスター番号モジュールの位置と単元により、マクロモジュールごとの一つずつ可能的なクラスター番号を取得するステップと、（ｂ）方向ごとに対応するクラスター番号の組み合わせの中のクラスター番号の分布をそれぞれに計算した後に採点、つまり、マクロモジュールの各々に対して二つのクラスター番号の差の絶対値、すなわち、現在のマクロモジュールのクラスター番号と、その右方及び下方に隣接したマクロモジュールのクラスター番号との差の絶対値を累計する（すなわち、マクロモジュールごとのクラスター番号と、その右方および下方に隣接したマクロモジュールのクラスター番号の差分の絶対値とをそれぞれに計算し、取得した絶対値を累計する）ステップと、（ｃ）四つの方向に対してそれぞれ採点し、最少得点の方向をコードパターンの正しい方向とするステップとを含み、統計の観点から見ると、正しい方向におけるマクロモジュールごとの平均得点は１点であり、そして、誤った方向におけるマクロモジュールごとの平均得点は３点、すなわち、（０＋１＋２＋３）／４×２＝３である。
【００３４】
（９）対称の関係から、上記したデータコードワードマトリックスに、コードパターンの中央マクロモジュールに対応したデータコードワードを決定する。もし複数の可能性があったら、例えば、５×５個のマクロモジュールを有するコードパターンが、データコードワードマトリックスにおいて１行分のデータコードワードが欠けたら、その中央マクロモジュールは二つの可能性があり、この場合には、あらゆる可能性のある中央マクロモジュールに対して、クラスター番号の分布を計算する必要があり、正確な中央マクロモジュールを選択する。例えば、候補の中央データコードワードの周辺の第１の層のデータコードワードのクラスター番号を累計し、一回の累計を行うごとに、その累計の和から１を引いてから、また候補の中央データコードワードの周辺の第２の層のデータコードワードのクラスター番号を累計し、一回の累計を行うごとに、その累計の和から２を引き、これに準じて、層ごとに候補の中央データコードワードの周辺の全てのデータコードワードのクラスター番号をそれぞれに累計し、一回の累計を行うごとに、その累計の和からその位置を代表する正しいクラスター番号値を引き、異なる中央マクロモジュールに対する得点を比較し、最大の得点を持つのを正しい中央として決定する。
【００３５】
上記した計算結果に基づいて、正しい中央マクロモジュールと方向によりデータコードワードを読み取り、リード・ソロモン誤り訂正アルゴリズムを用いて、コードワードの中に存在可能な誤りに対して誤り訂正を行い、誤り訂正が成功したら、データコードワードが出力され、データコードワードをバイトデータに復元し、復号が終了することになる。
【００３６】
上記ステップ（２）、（３）において、グレイスケール画像を２値化する時に、グレイスケール画像をさらに、重複しないか又は一部が重複する幾つかの部分に分割することができ、そのそれぞれに対して、グレイスケール値の分布を計算して閾値を定め２値化され、重なる部分のグレイスケールの閾値を平均してから、２値化された各部分を一つに組み合わせる。
【００３７】
本発明の二次元バーコードのコードパターンにおいて、白枠マクロモジュールと黒枠マクロモジュールとを交互に配列することにより、異なるマクロモジュールのつなぎ合わせた所、つまり、マクロモジュールの四角において特定なパターンモードが形成され、図１２に示されるように、本発明のコードパターンの境界以内にマクロモジュールの四角が有する特定なパターンモードであって、灰色の領域はモールディングボードの内容に属するものではなく、濃い色と薄い色の領域のみがこのモールディングボードの内容に含まれる。モールディングボード整合の目的は、画像に所定の領域にモールディングボードと同じか又は似ているパターンであるか否かを発見するためである。モールディングボード整合アルゴリズムによって、快速で確実にマクロモジュールの各々を同時に検出し定位することができ、上記復号化のステップにおけるステップ（５）、（６）の代わりにこの方法を用いることができ、コードパターンにおけるマクロモジュールの各々を定位しその四角の座標を算出することにより、コードパターンの耐破損、耐汚染、耐変形能力が有力に確保させられる。これは、コードパターンに白枠マクロモジュールと黒枠マクロモジュールが交互に配列されて、マクロモジュールの各々がその周辺の他のマクロモジュールとの間に明らかな境界を有するようにするため、２値画像に対して境界検出を行った後に、マクロモジュールの枠に著しい特徴を有する直線が形成され、これによって、速くコードパターンの回転角度を決定し、マクロモジュールを定位するようにする。
【００３８】
モールディングボード整合アルゴリズムとして、先ずモールディングボードの大きさを決定し、モールディングボードが小さければ小さいほど計算量も小さいが、誤った整合結果が出る可能性も大きい。また、モールディングボードが大きいほど計算量も大きくて、整合結果が間違う可能性は小さい。本実施の形態においては、３２ピクセル×３２ピクセルであるモールディングボードが用いられ、モールディングボードにおける黒/白線の広さが４ピクセルである。
【００３９】
モールディングボード検出が２値画像において行われると演算量は小さい。回転してしまったコードパターンにおいて、効果的にモールディングボードを整合させるためには、モールディングボードをコードパターンと同じ角度に回転させる必要がある。
【００４０】
モールディングボードを整合する時に、モールディングボードを被検出画像に置くことができ、モールディングボードと画像とが重なる領域の同じ画素の個数を統計し、検出領域にモールディングボードと同じ形状の特徴があると、その統計値が大きい（モールディングボードの画素の個数の総量に近い）又は小さい（零に近くて、被検出領域のモールディングボードの色とは完全に反対色となる）、それでないと、統計値は中間値（例えば、真黒又は真白の領域の統計値がモールディングボードの画素総量の半分だけである）になされる。モールディングボードは、全ての整合領域を探し出すまで、被検出画像中で移動される。
【００４１】
画像において、その二つの特徴は互いに反対色であるため、一回のモールディングボードの整合によって、この二つの特徴（統計値が最大又は最小）が同時に検出されることができる。
【００４２】
マクロモジュールごとにいずれもクラスター番号の単元モジュールが含まれ、コードワードの各々が一つのマクロモジュールに対応するため、全てのコードワードがクラスターに分けられ、中央から外へ時計回りの方向で層ごとに配列され、同一層におけるコードワードのクラスター番号は同じであり、クラスター番号は最大になった後にまた０に戻り、このような配列方式は、復号化アルゴリズムを確実にガイドしてコードパターンの方向を定位し起点コードワードを決定することができる。
【００４３】
コードパターンにおいて白枠マクロモジュールと黒枠マクロモジュールが交互に配列されるため、コードパターンの濃い色のモジュールと薄い色のモジュールの分布が均一に保持させられ、コードパターンを識別する時の漏斗効果を回避することができ、コードワードが誤る可能性を低減させる。
【００４４】
符号化の演算において、コードワードが分割されたビットストリームに対して、所定の誤り訂正レベルを選択して誤り訂正の計算を行い、形成されるコードパターンのフォーマット情報を簡単になされ、従って、従来の二次元バーコードに比べると傷付けやすい部品が一つ少なくなり、コードパターンの信頼性を向上させる。
【００４５】
符号化復号化のフローにおいて、コードパターンの画像からデータへの互いの転換は、単元モジュールを単位とすることではなく、マクロモジュールを単位（PDF４１７と同じ）として行い、その識別率が今までのあらゆるマトリックス方式の二次元バーコードよりも高いものである。
【００４６】
コードパターンにおいて、マクロモジュールの各々が独立に定位することができるため、一旦にパターンに破損があったり汚されたりした部分をいずれも定位しておくことができ、識別アルゴリズムは、現有のマトリックス方式の二次元バーコードに比べると、消去誤り存在を有効に検出することができ、これによって、誤り訂正の性能が向上させることができる。これは、コードワードのストリームにおいて、未知の位置の誤りを代用誤りと称し、既知の位置の誤りを消去誤りと称する時、RS誤り訂正アルゴリズムに対しては、消去誤りの誤り訂正性が代用誤りの誤り訂正性の２倍であるからである。
【図面の簡単な説明】
【００４７】
【図１】図１はPDF４１７コードの構成を示す図である。
【図２】図２はQRコードの構成を示す図である。
【図３】図３は本発明に係る二次元バーコードのコードパターンの示す図である。
【図４】図４は本発明に係る二次元バーコードのコードパターンにおける白枠マクロモジュール及び黒枠マクロモジュールを示す図である。
【図５】図５は本発明に係る実施の形態の二次元バーコードのコードパターンにおけるマクロモジュールの構成を示す図である。
【図６】図６は本発明に係る二次元バーコードのコードパターンにおけるマクロモジュールの配列方式の示す図である。
【図７】図７は本発明に係る二次元バーコードの符号化プローチャートである。
【図８】図８は本発明に係る復号方法を適応して取得した２値画像を示す図である。
【図９】図９は本発明に係る復号方法を適応して２値画像に対して境界検出を行って取得した境界画像を示す図である。
【図１０】図１０は境界検出した後に霍夫アルゴリズムを用いて取得した直線効果の図である。
【図１１】図１１は直線方程を計算して求めたマクロモジュールごとの四角座標の示す図である。
【図１２】図１２は本発明に係るコードパターンがマクロモジュールの四角において持つ可能な特定なパターンモードを示す図である。
【図１３】図１３は閾値を決定するための柱状図である。
【符号の説明】
【００４８】
１０ 特徴モード領域
１００ 単元モジュール
１０１ ピーク値
１０２ グレイ値
１０３ ピーク値
２０ フォーマット情報領域
２００ 枠単元モジュール
３０ 特徴モード領域
３００ クラスター番号モジュール
４０ フォーマット情報領域
４００ データモジュール
５０１ マクロモジュール
５０２ マクロモジュール
【図１】
0004564813.tif 000002
【図２】
0004564813.tif 000003
【図３】
0004564813.tif 000004
【図４】
0004564813.tif 000005
【図５】
0004564813.tif 000006
【図６】
0004564813.tif 000007
【図７】
0004564813.tif 000008
【図８】
0004564813.tif 000009
【図９】
0004564813.tif 000010
【図１０】
0004564813.tif 000011
【図１１】
0004564813.tif 000012
【図１２】
0004564813.tif 000013
【図１３】
0004564813.tif 000014