(57)【特許請求の範囲】
【請求項１】
論理的に順序付けられたデータグリフから構成される自己クロッキンググリフ符号を空間的に参照するための方法であって、前記データグリフは、情報を前記データグリフに符号化するための予め定められたシンボルセットから選択され、
予め定められた空間的なフォーマッティング規則に従って、前記論理的に順序付けられたデータグリフを記録媒体上の２次元フィールドに書き込むステップと、
同期符号を前記フィールド内に書き込むステップであって、前記同期符号が前記データグリフから識別可能である論理的に順序付けされたグリフから構成され、更に前記同期符号が前記同期符号のグリフと前記データグリフとの間の予め定められた幾何学的関係を確立する少なくとも１つの追加規則を加えて前記空間的なフォーマティング規則に従って、前記フィールドに書き込まれ、このことによって、前記フィールド内のデータグリフの少なくとも幾つかの論理的な順序付けが前記幾何学的な関係に基づいた前記同期符号のグリフから推定されるステップと、
を備える自己クロッキンググリフ符号の空間的参照方法。
【請求項２】
符号化された情報を記憶するための光学的に可読レコードであって、
記録媒体を有し、
前記情報を符号化するための自己クロッキングデータ符号を有し、前記データ符号が２次元の空間フォーマッティング規則に名目的に従って空間的に分散される中心に前記記録媒体に書き込まれるデータグリフから構成され、前記データグリフが前記情報を符号化するために光学的に識別可能なシンボルからの有限セットから選択される各シンボルによって定義され、
前記データ符号に絶え間ない空間参照を確立するための少なくとも１つの自己クロッキング同期符号を有し、前記同期符号が前記データグリフと識別可能であり、更に前記同期符号のグリフ及び前記データグリフ間の予め定められた幾何学的関係を確立する少なくとも１つの追加規則を加えて前記空間的なフォーマティング規則に名目的に従って前記記録媒体に書き込まれ、このことによって、データグリフの少なくとも幾つかの論理的な順序付けが同期符号のグリフとの幾何学的な関係から推定され得る、
ことを備える、光学的に可読レコード。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、普通紙の様なグラフィック（図形）記録媒体上へデジタル情報を記録するための自己クロッキンググリフ符号(self-clocking glyph codes) に関する。更に詳細には、本発明は自己クロッキング符号の同種型視覚的外観を保持しながら幾何学的ひずみや物理的損傷に対してこのようなグリフ符号の許容範囲を増大させるための技法に関する。
【０００２】
【従来の技術及び発明が解決しようとする課題】
図１に示される様な基本的な自己クロッキンググリフ符号（コード）は一般的に長く伸びたスラッシュのようなシンボル（記号）、即ち”グリフ(glyph) ”２２及び２３のアレイ２１から構成される。これらは、記録媒体２５の垂直方向の軸２４に関して約−４５°及び＋４５°の角度に傾斜される長い軸で書き込まれ、”１”及び”０”のビット値をそれぞれグリフの各々に符号化する又は反対にグリフの各々をビット値に復号化する。これらの符号は”自己クロッキング”である。なぜならばこれらの符号はそれらが符号化する値毎に光学的に検出可能なシンボル（”グリフ”）を含んでいるからである。この”自己クロッキング”は、１度復号化処理が符号に関して適切に空間的に配向されると、グリフの検出が復号（デコード）処理をその符号と明示的に同期させることを意味する。明白になるように、この暗示的な（暗黙の）同期はグリフ全体が正しい論理的順序で検出されるか、そうでない場合は正しい論理的順序でカウントされる限り有効である。一方、もし同期が失われると、暗示的な同期を復元するものはないので、一般的に同期の喪失により暗示的に同期された復号化プロセスが致命的誤り（エラー）を受ける原因となる。
【０００３】
グリフ２２及び２３の各々は、一般的に”オン”及び”オフ”ピクセルの認識可能なパターンをピクセル位置の２次元アレイ（即ち、”シンボルセル(symbol cell) ”）中に書き込むことによって定義される。一般規則として、グリフのボディ（本体）を形成するピクセル（即ち”オン”ピクセル）は、シンボルセル内のほぼ中心にある継続的ピクセル位置に書き込まれる。そして、他の、即ち”オフ”ピクセルはシンボルセルの残りのピクセル位置に書き込まれて、グリフのエッジを区別し、そのグリフの近隣からグリフを分離するコントラスト囲み(contrast surround) を提供する。
【０００４】
続いて、シンボルセルは通常、予め選択された空間的なフォーマティング規則に従って記録媒体上にタイル(tile)されるので、グリフが符号化するデータ値の論理的順序は、グリフが記録媒体上にマッピングされる空間的順序で維持される。例えば、シンボルセルは、正則(regular) 及び反復(repeat)空間フォーマティング規則に従って記録媒体上に書き込まれる。その規則はグリフ符号化を予め定められた大きさの論理的データブロックの２次元の矩形アレイにマップするために選択される。これらのデータブロックは左部から右部、頂部から底部の論理的順序で記録媒体上に適切に編成される。
【０００５】
自己クロキンググリフ符号を復号化するために既存の技法は、参照（基準）グリフの中心で又は中心付近で初期化されるように設計されて、その参照グリフがグリフ符号の残りの符号（例えば、グリフの矩形アレイの上部左側コーナー）に関して周知の空間的位置を専有する。従って、この参照グリフを正確に位置付けることは、明確にグリフ符号による復号処理のような空間的な同期化のキー（鍵）となる。
【０００６】
復号化処理の同期初期化は、自己クロッキンググリフ符号を順序通りに復号化するのに必要な条件であるが、符号を正確に復号化するのに十分な条件にはなりえない。その理由は、グリフ符号パターンのスキャン−イン画像は、スキュー及び／又はスケーリング(scaling) （拡大／縮小）の誤りのためにしばしば歪むからである。この理由のために、従来の復号化処理は一般的に認識可能な位置に３つ以上の参照（基準）グリフの相対的な空間位置を決定することを試みていた。そして、これらの位置がスキュー及びスケーリング訂正ファクタを計算するのに十分な精度で互いに関して（例えばグリフの矩形アレイのコーナーアレイ等）周知の名目非共直線的な関係を有する。次にこれらの訂正ファクタを使用して、グリフからグリフへ進みながら復号処理が行う飛び越し（ジャンプ）の方向及び大きさを示すベクトルの角度及び大きさを調節する。
【０００７】
認識されるように、復号化処理がグリフ符号との適切な空間的な同期を確立して維持するのを妨げるものはいかなるものでも、復号化を失敗させるという恐れがある。実際に、一般規則として、同期して読むことができるグリフから隔離されるあらゆるグリフは、特にグリフ符号パターンの内側において非同期的である。空間的な同期は勿論、復号化処理がグリフに符号化されるデータの論理的な順序を維持できることを必要とする。符号が結果として得られる復号化誤りを訂正するために十分な誤り訂正機能（即ち、誤り訂正符号保護）を有していれば、グリフの限られた数に悪影響を及ぼす少ない同期誤りは許容可能であるが、より拡張した同期誤りは一般的に符号化情報の不完全な読み取りの原因となってしまう。最終的に、この性能の劣化は十分に深刻になり、許容できなくなり得る。
【０００８】
従って、矩形のグリフパターンのコーナー（角）グリフのような、ある種のキー（鍵）グリフの空間的なロケーション（位置）から計算される広域の想像上の参照（想像上の基準）(imaginal reference)を用いることによってグリフ復号化処理を空間的に同期化することの重要な欠点の１つは、様々なファクタのためにそれらのキーグリフの１つ以上の空間的なロケーションが有効参照（基準）を計算するだけの十分な精度で決定できないことであり、このことによって復号化処理はグリフ符号との空間的な同期を得る及び／又は維持することができないということは明白だろう。更に、有効で広域な参照（基準）を計算できる時でさえ、復号化処理には同期を喪失するかもしれないという明らかなリスクをがある。例えば、グリフ符号のスキャン−イン画像は著しく劣化されて、復号化処理がグリフのある行から隣接する行へ間違って分岐する、又はグリフをカウント（考慮）せずにグリフを飛ばす、又は画像の損傷領域の読み取り不能グリフの数を数え間違える等の原因となる可能性がある。不運にも、周知の自己クロッキンググリフ符号またはその関係する復号化処理のどれも、同期が一度喪失されると、復号化処理が適切な同期を再確立することはできない。従って、同期の喪失のために、一般的にこれらの既存の復号化処理は不可逆の失敗モード(irreversible failure mode) になってしまう。
【０００９】
自己クロッキンググリフ符号の復号化中に適切な空間的な同期を確立して且つ維持するのに伴う問題は、復号器(decoder) の非同期的動作を検出するための信頼できる技法の欠如のために一層ひどくなっている（混ぜ合わされた）。フォーマットされた符号のあらゆる予め定められたセグメントの数え間違いが同期喪失を示すとういう理論に基づいて、グリフの中心はこれらの符号の復号化中に数えられていた。これは、グリフ符号パターンの部分（例えば、その周囲の一部分など）が見つからない、あるいは検出不可能である場合、弱同期検査処理となる。従って、復号化処理は、結果が無効であるという注意（警告）を発することなく無効な結果を提供する。
【００１０】
９０°、１８０°、２７０°の画像回転及び反射は、グリフ符号パターンの回転画像変形及び鏡像変形となり、これらの変形はグリフの外見上の空間的順序、及び／又は個々のグリフの外見上の回転的な配向を変更できる。実際にこのことは、例えばグリフが記録媒体の長手方向軸に関して±４５°で配向されるスラッシュ状のシンボルであり、それぞれハイ（”１”）及びロー（”０”）論理レベルビットを符号化する場合のような、グリフがデータ値をグリフの回転的な配向に符号化する場合に、特に重要な問題になる。その理由は、このようなグリフは回転的な対称性を有するパターンに書き込まれることがよくあるからである。不運にも、スキャン−イングリフ符号パターンの配向はしばしば、幾らかの曖昧性を伴う。例えば、正方形のシンボルセルに書き込まれる上述されたタイプのスラッシュ状のグリフの正方形アレイから構成されるグリフ符号の場合、一般的に４倍の回転的曖昧性があると共に、このようなグリフの矩形アレイから構成されるグリフ符号の場合２倍の曖昧性がある。
【００１１】
商業的に利用可能な２次元データ符号の幾つかは、１つ以上の符号の境界線に沿って特有の（区別できる）参照（基準）マークを有し、これらのマークはスケーリングのため及びその復号化を明示的で空間的に同期化するために使用され得る。しかしながらこれらの参照マークは視覚的に特有なので、これらの符号の視覚的などぎつさを増してしまいがちである。自己クロッキンググリフ符号の主要な利点の１つは、符号のどぎつくない視覚的外観により、その符号が美的に好ましくなる傾向があるということである。従って、そられの符号をこのような強い視覚的インパクトを有する参照パターンで補うことは逆効果である。
【００１２】
【課題を解決するための手段と作用】
本発明に従って、自己クロッキンググリフ符号はデータグリフから構成され、データグリフは論理的に順序付けられるデータ値及び１つ以上のマルチグリフ同期符号パターンを符号化する。同期符号パターンの各々はデータグリフと区別できるが、単数又は複数の同期符号パターンは、データグリフに明示的な空間参照を提供する。従って、単数又は複数の同期符号パターンのグリフは、データグリフと同じ空間的なフォーマティング規則に加えて、少なくとも１つの追加のフォーマティング規則に従って記録媒体に書き込まれる。その追加のフォーマティング規則は、データグリフの少なくとも有効数(significant number)（≫１）の論理的な順番が単数又は複数の同期符号パターンから推定されるような、単数又は複数の同期符号パターンと、空間的にフォーマットされたデータグリフの対応するグリとの間の予め定められた幾何学的関係を確立する。同期符号パターンの各々は、データグリフと同じ有限シンボルセットから選ばれるグリフから構成されることが好ましいので、単数又は複数の同期符号パターンは一般的にデータグリフのあらゆるパターンに関して固有である適切に高い統計学的な確率を有するグリフパターンにより定義される。
【００１３】
請求項１に記載の本発明は、論理的に順序付けられたデータグリフから構成される自己クロッキンググリフ符号を空間的に参照するための方法であって、前記データグリフは、情報を前記データグリフに符号化するための予め定められたシンボルセットから選択され、予め定められた空間的なフォーマッティング規則に従って、前記論理的に順序付けられたデータグリフを記録媒体上に２次元フィールドで書き込むステップと、同期符号を前記フィールド内に書き込むステップであって、前記同期符号が前記データグリフから識別可能である論理的に順序付けされたグリフから構成され、更に前記同期符号が前記同期符号のグリフと前記データグリフとの間の予め定められた幾何学的関係を確立する少なくとも１つの追加規則を加えて前記空間的なフォーマティング規則に従って、前記フィールドに書き込まれ、このことによって、前記フィールド内のデータグリフの少なくとも幾つかの論理的な順序付けが前記幾何学的な関係に基づいた前記同期符号のグリフから推定されるステップと、を備える。
【００１４】
請求項２に記載の本発明は、符号化された情報を記憶するための光学的に可読レコードであって、記録媒体と、前記情報を符号化するための自己クロッキングデータ符号であって、前記データ符号が２次元の空間フォーマッティング規則に名目的に従って空間的に分散される中心に前記記録媒体に書き込まれるデータグリフから構成され、前記データグリフは前記情報を符号化するために光学的に識別可能なシンボルからの有限セットから選択される各シンボルによって定義される、自己クロッキングデータ符号と、前記データ符号に絶え間ない空間参照を確立するための少なくとも１つの自己クロッキング同期符号であって、前記同期符号が前記データグリフと識別可能であり、更に前記同期符号のグリフ及び前記データグリフ間の予め定められた幾何学的関係を確立する少なくとも１つの追加規則を加えて前記空間的なフォーマティング規則に名目的に従って前記記録媒体に書き込まれ、このことによって、データグリフの少なくとも幾つかの論理的な順序付けが同期符号のグリフとの幾何学的な関係から推定され得る、前記自己クロッキング同期符号と、を備える。
【００１５】
【実施例】
本発明に従って、図２に示されるように、自己クロッキンググリフ符号３１は２次元の分散同期符号パターン(distributed sync code pattern) ３３と共にデータ符号３２を含む。明確に示すために、データ符号３２は記録媒体３５の長手方向の軸（処理方向矢印３６参照）に関して−４５°に傾斜されるスラッシュ状のシンボル又は”グリフ”３４から構成されて示されると共に、同期符号パターン３３がその長手方向軸に関して＋４５°に傾斜されるグリフ３７から構成されて示される。実施において、もちろんデータグリフ３４の角度的な配向(angular orientation) は、そのグリフ３４が符号化するそれぞれのデータ値に従って変更される。更に、同期符号グリフ３７の角度的な配向はまた、本明細書中で後で十分に説明されるように、値の巡回的な(cyclic)又は非巡回的な(acyclic) 系列（シーケンス）に従って変更され得る。従って、所与のデータグリフ３４と所与の同期グリフ３７の間の記号的な区別(symbolic distinction)は全くなくなくてもよい。実際に、本発明のより詳細な特徴の１つと一致して、データグリフ３４及び同期グリフ３７は好ましくは同一有限シンボルセット（集合）の潜在的に同一のメンバ（member) である。その理由は、この同一メンバであることによって、同期符号パターン３３はデータ符号３２と視覚的に有効に混合（ブレンド）されるからである（図８参照）。更に複合符号(composite code)３１の視覚的な同種性を高めるために、同期符号パターン３３は同一記号の長いラン(run) のような視覚的に特色のあるグリフパターンを避けるように良好に選択される。
【００１６】
更に詳細には本発明と一致して、同期符号で符号化されたグリフパターン３３（本明細書において”同期符号パターン”と呼ばれることもある）は、グリフの予め定められた巡回的な又は非巡回的なパターンから構成され、このパターンは十分に特色があり、許容可能な高い統計的信頼性によってデータ符号３２から曖昧性が取り除かれる。この同期符号パターン３３はデータ符号３２と同じ空間フォーマッティング規則に従って記録媒体３５に書き込まれるが、同期符号パターン３３のフォーマッティングは更に、少なくとも１つの追加の規則によって支配される。そしてその規則は同期符号パターン３３のグリフ３７の空間的な位置決めと近くのデータグリフ３４の空間的な位置決めとの間の局所化された幾何学的関係を確立する。同期符号パターン３３のグリフが符号化する同期符号値の論理的順序付けは、予め決められる。従って、同期符号パターン３３は、データグリフ３４の論理的な順序付けを決定するために局所化された空間参照（基準）を定義する。
【００１７】
明らかになるように、同期符号パターン３３の複製性(replicability) は、そのパターンが提供する空間的参照が、元の画像及び／又はそれらの複合符号３１のコピーが損傷される場合に生じる喪失を受けるに過ぎない複合符号３１（複合符号３１がハードコピーの複製(replica) を提供するためにフォトコピー( 電子写真）若しくはファクシミリ伝送によって、又は電子表現を提供するビットマップ入力走査によって複製される時のような）の写しを残すことを確実にする。良好に、同期符号パターン３３は複合符号３１中に分散されて、それは、提供される空間参照の密度がデータグリフ３４の全てを局所的に参照するのに十分なように選択される。その事象において、複製されている間にデータ符号３２が受けるあらゆる非線形歪みは、同期符号パターン３３の対応する局所化された非線形歪みによって追跡される。
【００１８】
理論上、同期符号パターン３３は多くの異なる形態（フォーム）をとることができる。一方、実施に際し、同期符号パターン３３は線形パターン（又は非線形実現では隣接グリフセル領域内）として書き込まれることが都合がよい。その理由はこれらのタイプの部分パターン（サブパターン）は空間的に分散されたグリフの非線形パターンよりもより容易に識別されるからである。例えば、同期符号パターン３３はグリフ３７の線形部分パターンから構成され、これらの部分パターンは、空間的にフォーマットされるグリフ符号３１（又はその論理部分セット−図４参照）を一方向（図２参照）又は複数の異なる方向（図３参照）にスパンする（またがる）ためデータグリフ３４と同一の中心間の間隔で書き込まれる。
【００１９】
線形同期符号グリフパターン（即ち、線形空間系列（シーケンス）で書き込まれる同期符号符号化グリフのパターン）に焦点をあてると、このような同期符号パターンは、線形同期符号部分パターンの２次元アレイによって多少概略的に定義されることが理解されよう。この場合、部分パターンの各々は予め決められた同期方向と平行して走るほぼ真っ直ぐな線に沿ってｍ番目（この場合、ｍは整数である）のグリフ全てで構成される。ｍ＝１の縮退的な場合は微細な粒度の明示的な同期を提供する。その理由は同期符号パターンは隣接グリフから構成されるからである。一方、荒い粒度の明示的な同期の場合、データグリフ３４の自己クロッキング特性によって提供される暗示的な同期が、データグリフの存在が確実に検出できる時は何時でも、又は検出されたデータグリフが正確に暗号化され得るか否かに関係なく、有効であるので満足できる。あらゆる事象において、所与の細分性ｍの線形同期符号部分パターンが使用される時、（１）同期方向に位置合わせ（整合）されて、（２）ｍ−１の中間グリフによって互いから分離されるグリフから構成されるグリフの各々のセットは、同期解除誤り(desynchronizing fault) （即ち、同期エラー(synchronization errors)が見られる場合を除き、適切な系列内に全同期グリフを含む又は同期グリフを含まないのいずれかである。
【００２０】
図２におけるパターン３３のような平行で、長手方向に分離された線形部分パターンから構成される同期符号パターンは、自己クロッキング符号３２の復号化中に同期符号符号化グリフのパターンの内包がどの様に容易に同期を確立して且つ維持するかについての興味深い例である。この実施例において、同期符号部分パターン３３ａ−３３ｄはデータ符号３２の主軸（即ち、標準的な直交座標空間における横方向又はｘ軸方向）と平行位置合わせされて書き込まれ、且つこれらの部分パターン３３ａ−３３ｄは同期符号符号化グリフ３７から構成され、それらがデータグリフ３４と同じｘ軸に沿った中心間のスペーシング（間隔）に書き込まれる。更に、同期符号部分パターン３３ａ−３３ｄは各々がそのｘ軸方向に沿ってデータ符号３２をスパンするのに十分な長さがある。そして、これらの同期符号部分パターン３３ａ−３３ｄは、データ符号３２の行（ライン）の所定の定数によって複合符号パターン３１の直交軸（即ち長手方向のｘ軸又はｙ軸）に沿って互いから空間的に変位される。
【００２１】
あらゆる２つの隣接する同期符号部分パターン（例えば部分パターン３３ａと３３ｂのような）のグリフ３７が中心に置かれるｘ、ｙ座標が与えられると、その隣接する同期符号部分パターン同士の間にある、データグリフ３４の予想される中心位置（ロケーション）は、２つの同期符号部分パターンの互いに論理的に対応する位置を占有するグリフ３７を対にすることによって、及び次にこれらの論理的対のグリフのｘとｙ座標の間を線形補間することによって識別され得る。この処理は同期符号部分パターン３３ａ−３３ｄの強い明示的な同期を軸方向に提供する。その理由はその軸に沿った非線形歪みを感知できるからである。より弱い同期は、補間によって直交位置が隣接同期符号部分パターン３３ａ−３３ｄの間隔から決定されるので、部分パターン３３ａ−３３ｄと直交するように提供される。
【００２２】
幸いにも、データグリフ３４の自己クロッキング特性によって提供される暗示的な同期は、平行な同期符号部分パターン３３ａ−３３ｄの間に配されるデータグリフ３４を読み込みながら、復号化処理の同期を維持するのに十分である。例えば２つの隣接する同期符号部分パターンに論理的に対応する位置を占有する同期符号グリフ３７同士の間に論理的に位置合わせされるデータグリフ３４は、（１）論理対同期符号グリフ３７の１つで復号化処理を明示的に再同期化するすることによって、そして（２）次に、データグリフ毎に同期符号グリフ３７の対の第２番目に向けて復号化処理を進めることによって、”最善努力ベーシス(best efforts basis)" によって好適に識別される。この処理は、同期符号グリフ３７の論理的な組み合わせ化(pairing；ペアリング) が交互に（順々に）繰り返される。局所的な損傷が、データグリフ３４の幾つかを、それらグリフの論理的な順序付けを確実に決定するるのに要求される精度で識別するという試みを失敗させるので、この処理は最善努力処理であることが理解される。一方、同期喪失（ロス）は容易に検出される。その関係において、復号化処理が２つの論理的に対にされた同期符号グリフ３７の間で論理的に位置合わせされるデータグリフ３４をサーチしている間に読み込まれるデータグリフ３４の数は、予想されたデータグリフ３４の数が検出されたか否かの信頼性のある指標(indication)であるということが留意されるだろう。更に、論理的に対にされた同期符号グリフ３７を一方から他方へ追跡する場合の復号化処理の成功又は失敗は、介在するデータグリフ３４の読み込み中に同期が保持されたか否かの強力な指標である。従って、同期誤り（エラー）が生じれば、適切な矯正的な及び／又は訂正的な動作を取ることができる。この動作は、例えば誤りを訂正できるだけの誤り訂正能力があるような場合ユーザには見えなくてもよい、又はこの動作は例えば復号結果が無効及び／又は不完全であることをユーザに知らせるような徹底的な手段(drastic measures)を伴ってもよい。
【００２３】
図３に示されるように、暗示的な空間同期参照（基準）としてデータグリフ３４に頼ることの計算的な不確実性は、同期符号パターン４３を用いることによって回避できる。この場合、同期符号パターン４３は、共同して複合符号パターン(composite code pattern)３１を（そのｘ軸及びｙ軸に沿って）スパンする複数の非平行線形同期符号部分パターン４３ａ及び４３ｂから構成される。２つのこのような部分パターン４３ａ及び４３ｂは、例えば複合符号パターン３１の画像の１次元又は２次元の歪みの結果として生じやすい同期誤りを十分減少できる。更に、使用される同期符号が、以下に更に詳細に説明されるデジタル符号の幾つかによって提供されるような同期符号部分パターンの各々のある程度一定のスパンに対して独特のアドレスを提供する場合、１対の非平行同期線は、個々のデータグリフ３４、近隣データグリフの群（グループ）、及び／又はデータグリフの全ての線の落伍（ドロップアウト）によって生じた同期誤りを更に減少できる。
【００２４】
複合符号パターン３１の同期符号部分パターン４３ａ及び４３ｂのグリフ３７のｘ及びｙ座標からのｘ軸及びｙ軸に平行する方向への線形的な補外は、データグリフ３４の予想中心位置で交差する線を提供し、それによってデータグリフ３４の明示的な空間同期参照を提供する。実施に際し、複合符号パターン３１のスキャンイン画像(scanned in image)は幾分スキューされるが、複合符号パターン３１のｘ軸及びｙ軸に関して同期符号部分パターン４３ａ及び４３ｂの角度的な配向が周知である場合、あらゆるわづかのスキュー誤りは取り除かれる。特に、その情報は広域の又は局所的なスキュー補正ファクタを計算するために使用可能であり、このファクタは、同期符号ストリング４３ａ及び４３ｂを複合符号パターン３１のｘ軸及びｙ軸に関して適切な角度で配向する。主軸に沿って複合符号パターン３１に共同してスパンするあらゆる２つの非平行同期符号ストリングは満足するものであるが、そのｘ軸及びｙ軸に沿って複合符号パターン３１をスパンする２つの直交する同期符号ストリング４３ａ及び４３ｂはそれぞれ、わかりやすい例を提供するために示される。
【００２５】
更に図４乃至１１に示されるように、平行な線形同期符号部分パターンの内の２つの非共直線組は、格子状の同期符号パターン５３を形成するために使用可能であり、このパターン５３は矩形又は平行四辺形のような構成を有する同期符号セル５４ａ−５４ｉの２次元のタイル（タイル張りされた）アレイから構成される。このような同期符号パターンのグリフ３７が中心となるｘ，ｙ座標は識別でき、グリフ３７は同期符号の格子に従うこうとによって複合符号パターン３１全体がシステム的に復号化され得る。この格子の最も多い頂点へのパスは４つのあるので、１つ以上の別のパスに沿ってグリフ３７の論理的な順序付けを決定するというあらゆる試みが損傷によって失敗する時でさえ、同期符号パターン５３の殆ど全ての所与のグリフ３７は論理的に順序付けられた同期符号グリフ（同期符号パターン５３の近隣グリフの値に対して予め定められた論理的順序を課せるこの概念については、以下で更に詳細に説明される）のパスに従うことによって到達可能である。例えば図１０を参照すると、重ね書き８１、８２及び８３は格子状の符号パターン５３の部分を部分的に消す。重ね書き８１の閉じた線の形状(closed lines geometry) のためにその内側の同期グリフに到達することは阻止されるが、同期符号グリフ上の開いた線の重ね書き８２及び８３の回りに移動させることは可能である。
【００２６】
明らかになるように、同期符号パターン５３のような２次元の同期符号の格子を使用することにより、同期符号グリフ３７で終端される両端部を有するデータグリフ３４の行又は列（row or column)のようなグリフの線形アレイに読み込まれるデータグリフ３４の数の積極的検査(positive verification) を可能にする。このことは、このような同期符号パターンが同期符号格子により完全に閉じ込められたデータグリフ３４の読み込み中に、グリフの隣接行への枝分かれが生じなかったという実質的な検査を可能にするということを意味する。格子セル５４ａ−５４ｉの寸法は（同期符号グリフの計数によって測定されるように）均一であることが便利である。その理由は、これが巡回同期符号の周期性を許容するからであり、これらの符号については以下で説明されるが同期符号パターン５３の周期性と整合（突合せ）される。図４は同期符号パターン５３のそれぞれのセル５４ａ−５４ｉがデータグリフ３４の６×６のアレイを含んで示されるが、実施する場合には、あらゆるＭ×Ｎの格子を使用できることは理解されるだろう。例えば、格子パターン５３のセル５４ａ−５４ｉの各々は、データグリフ３４の１６×１６のアレイから構成される論理的なデータブロックを好適に構成し、そのことによって同期符号パターン５３を含むことのオーバーヘッド（over-head)費用を減少でき、データグリフ３４の復号化を明示的に同期するために必要とされる空間参照を提供する。
【００２７】
周知であるように、色々な記述(description) のデジタル符号は、通信信号を同期するために、広範囲にわたって利用されてきた。これは一般的に一次元同期の問題である。一方、本発明は二次元同期の問題で処理する。一方、理解されるように、極めて効果的な二次元の同期符号パターンは、一次元のデジタル符号の組み合わせを用いて実現され得る。更に、これらの二次元同期符号パターンの幾つかは、自己クロッキンググリフ符号の構造及び／又は情報内容の絶対的及び相対的論理アドレス指定、このような自己クロッキンググリフ符号の情報内容の配向的な曖昧性除去、及び損傷及び／又は歪みに対する許容範囲の向上を含むより詳細なアプリケーションに関する興味深い属性を有する。
【００２８】
デジタル同期符号を空間的に適切に順序付けられて且つ比較的容易に識別されるグリフパターンと関連付けることが基本的に有利であることは明確である。上述された線形グリフ符号パターンはこれらの一般的な基準を満足させるパターンの良い例である。
【００２９】
更に、思い出されるように、平行線の同期符号パターン（図２参照）でさえ、二次元に関して、即ちその線に沿って且つその線を横切るように同期情報を提供できる。さらに、線上のグリフの系列（シーケンス）が予め定義されたデジタル同期符号を符号化するという積極的確認（positive confirmation)が、例えばグリフの部分領域のエッジ等の横断位置に関してその行（ライン）を位置合わせ符号にするということは明白になる。１１１１１１１１... 又は１０１０１０１０... のような単純な繰り返しのデジタル符号はこの目的のために使用可能である。明確なようにこれらの符号を検出することは容易であるが、これらは線に沿って限定されるアドレス指定情報及び最小の絶対アドレス指定情報を提供する。さらに、これらの反復性の符号の高度な対称性は配向の曖昧性を解決するのに少ししか役立たない（このことについては更に詳細に後述される）。
【００３０】
たとえデジタル符号自体が上述された単純な符号系列（シーケンス）のような特有のアドレス指定を欠くとしても、同期符号の非平行線形ストリング（図３乃至１１）から構成される同期符号パターンの交点は、同期の参照として役立つことができることは理解されるだろう。例えば、図４のような同期符号を符号化するグリフの２組の交差する線形部分パターンは二次元の絶対的な位置合わせ機能を提供できる。特に、これらの線形グリフストリングの各々が同期符号を符号化する確認は、同期符号グリフにより構成されるグリフ領域又はセルの線形境界を確立して、且つその構成（フレーム）された領域は内側グリフ位置の予め定められたパターンを有することで知られている（その理由は、空間的なフォーマティング規則が周知であるからである）。
【００３１】
いわゆる極大長系列（ＭＬＳ;maximal length sequences)に従う巡回デジタル符号系列は、適切に構成されたデジタルシフトレジスタによって、又はのぞましいＭＬＳのビットレベル記述（Solomom W. Golomb による" シフトレジスタ系列(Shift Register Sequences)" 、Holden-Day,Inc. 1967年を参照) を参照することによって生成され得る。次に、これらのＭＬＳデジタル系列は、そのＭＬＳデジタル系列を二次元グリフ符号のより複雑な処理のために極めて有益にするという特性を有することがわかっている。
【００３２】
更に詳細には、ＭＬＳを生成するｎステージ（段）シフトレジスタが、長さＬ＝２n −１の２進系列を生成することは周知であり、ここにおいて長さｎのそれぞれの部分列(subsequence) は固有である。従って、少なくとの長さ１＝ｎのあらゆる部分列は、系列に沿った位置を定義し、従って局所同期参照及びＬの周期的な曖昧さを備える局所アドレスを定義する。このようなシフトレジスタ系列の継続は期間Ｌを有する巡回周期的である。例えば、ｎ＝３である場合、Ｌ＝７となり且つ対応するＭＬＳシフトレジスタビット系列はＳ＝00111010011101... となる。従って、所望されれば、ｎが容易に選択されて、あらゆる所与の有限長さのビットストリング内でビット系列Ｓを繰り返さないほどの大きさになることは明白であろう。更に一般的には、グリフの空間的に順序付けられたアレイが、非反復シフトレジスタ部分列のビットの１つずつの値を論理的順序に符号化すると、グリフによって符号化されるビット値はグリフのアレイを横切るように絶対１次元アドレス指定を提供することが観測される。明らかになるように、この絶対アドレス指定特性は、論理的に順序付けられた非反復シフトレジスタの部分列のマッピングからグリフの空間的に順序付けられたパターンへ続くので、同期符号グリフの線形パターンに限定されるわけではない。
【００３３】
一般規則として、ＭＬＳ系列はｎ＞２に対して対称的(symmetric) ではない。長さｎのＭＬＳ部分列を定義するアドレスは順方向及び逆方向（例えば１０１）に対称的になり得るが、長さ２ｎより小に延出する系列は対称性をブレーク（破壊）するだろう。理解されるように、このＭＬＳ符号の特性は、グリフパターンの対称性の曖昧さ除去を援助できる。
【００３４】
既に指摘されたように、ｎステージシフトレジスタ極大長系列はビット長Ｌ＝２n −１の巡回周期(cyclic period) を有し、これは”丸められた(round) ”２進数よりも正確に１だけ少ない。従って、ｎ＝１、２、４、５、６、７、... の場合、Ｌ＝１、３、７、１５、３１、６３、１２７... となる。これらのビット長は、例えばニブル（４）、バイト（８）、ブロック（５１２×８）等のデジタルデータが一般的にアセンブルされる丸め２進単位とは自然には一致しない。このことは、ＭＬＳ符号が、便利な２進単位に配列されるデータブロックを高精度にスパンしないという欠点を有することを示すので意義がある。
【００３５】
一方、幸いにも、２n −１の極大長系列を備えるｎステージシフトレジスタに関して、１と２ｎの間のどの巡回周期も非線形シフトレジスタへの２n −１の単純な標準的な変更のうちの１つによってそれから得ることができることが示された〔Ｇｏｌｏｍｂ，ｏｐ，ページ１９２から１９４〕。多くの場合、その結果としてえられた系列は、極大長系列の部分列となる。例えば；
極大（Maximal) n=4, L=15, S=111000100110101111000....
打ち切り(Truncated) L'=8, S=11100010.111000....
極大（Maximal) n=5, L=31, S=0000100101100111110001101110101.
打ち切り(Truncated)L'=17, S=00001001011001111.00001...
（各５ビット部分列は固有であることに留意せよ）
【００３６】
一般的に巡回打ち切り系列(cyclic truncated sequences)を含むこれらの巡回符号(cyclic code) は、各サイクル内に（即ち、印刷されたグリフ符号の各局所領域内に）固有のｎビット部分列アドレス指定を提供する。
【００３７】
Ｌ＝２n −１の極大長系列を備えるｎステージシフトレジスタは一般的にｎ個の１に隣接する（ｎ−１）個の０の部分列を含む。従ってこのような系列は（ｎ−１）個の０に隣接する１個以上（即ち、”ｒ”）の追加の０を挿入することによって、埋め込まれることができる。１つの０の加算は、丸め２進値である周期長(period length) （Ｌ’＝２n ）の系列を与える。従って、グリフ符号においてこのタイプの埋め込み（padding)を使用して、同期符号の各サイクルを、便利な２進フォーマットに書き込まれたデータ符号のブロックと位置合わせ（整合）することができる。２つ以上の０を挿入することによって、（１）”偶数”２進フォーマットを備えるデータブロック、と共に（２）同期符号グリフ横方向（横切る）線のような別の目的のために使用可能な追加グリフの１つ以上の領域と、位置合わせ可能である。理解されるように、この０の埋め込みは、ｎ個の１が直ぐ後に続き且つｎ個の１が曖昧でなく明瞭に識別される０のストリングを除いて、符号に沿った明瞭なアドレスとして、全部のｎビット部分列の固有性(uniqueness)を保持する有用な特性を有する。
【００３８】
例：
n=2, r=0, L'=3, S=011011  ( 注意：対照的)
ｎ＝２，  ｒ＝１，  Ｌ’＝４，  Ｓ＝００１１００１１    （  注意：ビット反転＝系列の逆転；対称的）
n=2, r=2, L'=5, S=0001100011.
ｎ＝３，  ｒ＝０，  Ｌ’＝７，  Ｓ＝００１１１０１００１１１０１
ｎ＝３，  ｒ＝１，  Ｌ’＝８，  Ｓ＝０００１１１０１０００１１１０１    ［  注意：ビット反転＝系列の逆転]
ｎ＝３，  ｒ＝２，  Ｌ’＝９，  Ｓ＝００００１１１０１００００１１１０１．
ｎ＝４，  ｒ＝０，  Ｌ’＝１５，  Ｓ＝０００１１１１０１０１１００１０００１１１１０１０１１００１
ｎ＝４，  ｒ＝１，  Ｌ’＝１６，  Ｓ＝００００１１１１０１０１１００１００００１１１１０１０１１００１
ｎ＝４，  ｒ＝２，  Ｌ’＝１７，  Ｓ＝０００００１１１１０１０１１００１０００００１１１１０１０１１００１．
【００３９】
（ＭＬＳ符号のような）予め定められた長さの部分列内で固有のアドレス指定できる周期的な同期符号を用いて、同期グリフの交差する横（横切る）方向のパターンのグリフ位置に方向的な操舵(directional steering)を提供できることは認識された。従って、前記のタイプの周期的な同期符号を使用する時、同期グリフの横方向の線の間隔を周期的な同期符号の周期（期間）に整合させることは有用であり、従って、周期的な同期符号と横方向の同期グリフとの間の横方向参照は一貫する。
【００４０】
同期符号の交差するストリング同士の間の一貫した横方向参照のメンテナンスは、勿論、図４乃至８に示される格子状のグリフ符号パターンを含むより興味深いグリフ符号パターンの幾つかまで拡張できる。更に詳細には、周期的な同期符号を符号化する平行なグリフ符号部分パターンの２つの交差するセットが両方の同期符号に適合する周期的な時間間隔(interval)で間隔(spacing) を空けることができることは明白である。更に、その両方の符号の周期的な間隔を整合させる（突き合わせる）間隔が、同期のインタロックする周期的な格子(grid)を各交点の近隣の同一ビットパターンで生じることが示される。実際に、このことは正方形の格子内の符号0011101 に関して、図５に示される。更にこれは図６乃至８にも適用され、ここで同期符号パターンは、上述された２つの０ビット埋め込みで１７ビットの巡回符号(cycle code)を符号化する正方形の格子のグリフストリングである。図６及び図７は、別々に印刷された同期格子及びデータグリフを示す。一方、図８は組み合わされた又は複合グリフ符号を示し、このグリフ符号は同期符号が可変データによって符号化されたグリフと目に見えるように均一にブレンドすることを示す。
【００４１】
幾分、より一般的なレベルで、交差ストリンググリフが線形アドレス情報を符号化し、且つ共通のグリフを共有する場合、共有グリフに符号化された値は、好ましくは符号化された系列の両方と一致する。一方、そうでなければ同期符号が、単純な符号（111 又は1010) のような明らかな固有のアドレス指定を提供しない場合、例えば1111101111111 又は101010001010等の交差位置の識別を容易にするために同期化系列の一方又は両方と一致しないように交点グリフを配置することが有利である。
【００４２】
図９に示されるように、繰り返し周期的同期系列の変換の曖昧性は、”予約(reserved)”グリフ５８ａ乃至５８ｉに追加の予め定められたデータを書き込むことによって克服できる。この場合、これらの予約グリフは周知の順序を有し、且つ符号化された同期符号グリフに関して予め定められた位置にある。耐久性(robustness)のために、この追加情報を符号化する場合に好ましくは予約されるグリフは、同期符号グリフ３７と空間的に隣接する。これらの予約グリフに符号化される追加情報は物理的及び／又は論理的データブロックの識別を含む。例えば本発明が意図する巡回同期符号は、適切なデータブロックの特定の情報をこれらの予約グリフ５８ａ−５８ｉに符号化することによって補われ、同期符号がデータブロックベースでデータグリフ及び予約グリフ５８ａ−５８ｉを同期化するために使用可能であり、全体のグリフ符号パターンに関して物理的にデータブロックを識別するために用いられる。従って、図９は９つのデータブロック５４ａ−５４ｉがあり、これらのブロックは、巡回ＭＬＳ符号〔ｎ＝４、Ｌ’＝１６（１つの０で埋められる）〕で囲まれて、且つ例えば２３（これはタイル状フォーマットの２列３行のデータブロックの適切な識別子である）に対応する00100011等の２つの１６進符号数の形式でブロック座標を与える上部左コーナーにある１バイトのデータでラベル付けされる。
【００４３】
データブロック５４ａ−５４ｉの物理的なアドレス指定は、データブロック５４ａ−５４ｉのあらゆるブロックに記録されるデータへランダムアクセス（乱呼び出し）のためのパワフル（強力な）索引付けメカニズムを提供する。更に所望されれば、この索引付けは階層的に拡張され、例えばページ索引値（インデックス）、ボリューム索引値、及び予約グリフ５８ａ−５８ｉ中に書き込まれるデータ内の同様の論理的な相関器(correlators) 等を含むことができる。次に、標準ランダムアクセス技法を用いて、グリフ読み取り処理を１つのデータブロックから同じグリフ符号パターン又は異なるグリフ符号パターン内の別のデータブロックへ進めることができる。
【００４４】
明らかになるように、本明細書において先に提案された線形同期グリフパターンは、グリフのこの論理的に順序付けられたソーティング（分類）を容易にするが、以下でより詳細に説明されるように、可能性のある全体の回転曖昧性、及びグリフの整数による変換(translation) の不確実性はなお存在する。従って、Ｌビットの周期（期間）を有する巡回同期符号が使用されると、この同期符号で符号化されるグリフを識別するための検査は、周知の同期符号に整合するｋビットの論理的に順序付けられた部分列を符号化するグリフを探索する。この場合、ｋの長さはは同期符号の１周期内の同期化されたアドレスを固有に十分に定義できる。次に、ｋ＋Ｌがｍ又はｍよりも大きくなる場合、同期符号の変換段階(translation phase) にランダムに整合するこの部分列の確率は、Ｌ／２k となる。なお、この場合、ｍは同期符号の全線(full line) 中の同期グリフの総数である。次に、有効系列の数はＬから（ｍ−ｋ）へ減らされ、（ｍ−ｋ）／２k のランダムな整合確率をもたらす。
【００４５】
一度、試験的に有効同期符号の部分列がわかると、次に行われる検査は、部分列が空間的なフォーマッティング規則に従って部分列を論理的に拡張するグリフのそれぞれの復号値によって拡張されるので、一般的に特定の部分列が周知の同期符号に対して整合し続けることを確認するために行われる。言い換えると、明白な同期符号パターンは更に、ｋを増大する部分列をもたらす復号値が周知の同期符号に整合し続けることを確認することによって、描写(delineate) 及び検査される。一般的に適切な同期識別は、データを同期と誤って識別する確率が許容可能であるとみなされると、得られる。殆どのアプリケーションの場合、ｋに依存する指数確率(exponential probability) の急成長のために、この状況は満足され、同時に同期検査のために適度にサイズ形成されたｋを使用する。
【００４６】
図１０及び１１に示されるように、同期符号のこのクラスの双方向及びインタロッキング論理属性によって提供される追加の同期検査ツールは、同期符号パターンがグリフ符号の局所的な損傷及び／又は劣化によって分裂（即ち、間違って論理的に壊される）する時に、グリフ符号の復号化のための指数の明示的な空間同期を再確立するのに、特に役立つ。
【００４７】
理解されるように、同期の絶対検査はまた、図３に示されるようにグリフ中心の合同のパターン(congruent pattern) がない場合の同期符号グリフの幾何学的に固有の部分列を予め定め、検出することによって、グリフ符号パターンに境界をなしている有限領域内で得られ得る。グリフがない”落伍(dropout)"の場合には、このような同期符号パターンをビットレベル（即ち、デジタル領域内）でのあらゆるパターン整合を実行する必要はなく画像領域内で検査できる。例えば、グリフ符号がグリフ中心の矩形アレイ上に書き込まれる場合、グリフの予め定められた行列に書き込まれ、完全にアレイをスパンする（図３のように、境界グリフを含む）同期符号パターンは、同期符号と幾何学的に識別可能である。このような幾何学的に識別可能な同期符号パターンはまた、境界特徴を参照するというよりもむしろ、グリフを同期パターンから数えて分けることで参照される絶対２次元アドレス指定の度合いを提供する。
【００４８】
予め定められた同期符号を符号化するグリフ及び可変データグリフを含むグリフアレイを復号化する場合、予め定められた同期符号グリフが最初に復号化される。例えば、格子状の同期符号パターンの場合、復号化はあらゆる所望されるロケーション（位置）で開始されることができる。同期符号符号化グリフのそばで位置付けするために、グリフのあり得る同期部分列は、同期パターンのセクション（部分）を確実に含むほど十分に大きな局所領域において検査される。配向の曖昧性に関する問題がある場合、これらのあり得る同期部分列は満足ゆく結果が見つかるまであり得る配向の各々に関して評価される。周知の同期パターンの初期セクションが見つかると、同期パターンは次に１グリフずつ拡張される。グリフ符号系列が損傷によって塞がれる場合は、別の同期パターンパス（経路）に続いてもよい。隣接領域への飛び越しが要求されると、それはデジタル同期符号アドレス指定特性によって論理的に接続され得る。同期グリフができる限り完全に位置づけされると、可変データは局所同期グリフ符号が参照し、且つ確認する論理的な順序で読み込むことができる。任意であるが、同期グリフロケーションの格子は、可変データグリフの予想される画像位置を補間するために使用可能である。
【００４９】
或いは、同期符号は、データ符号が復号化値の２次元アレイに変形された後だけに使用されてもよい。この事象の場合、同期符号は記録装置のフィードフォワードモード(feed forward mode) で使用され、データの追加、落伍、共有のような復号化誤りを訂正するために要求されるような復号化値を訂正する。
【００５０】
【発明の効果】
本発明によって自己クロッキング符号の同種型視覚的外観を保持しながら幾何学的ひずみや物理的損傷に対してこのようなグリフ符号の許容範囲を増大させるための技法が提供される。
【図面の簡単な説明】
【図１】基本的な２次元のフォーマッティング規則に従って書き込まれた標準的な自己クロッキンググリフ符号の略拡大図。
【図２】本発明に従って同期的符号パターンを含むブロックフォーマトされた自己クロッキンググリフ符号の略拡大図。
【図３】本発明の更に詳細な態様に従って非共直線的な同期符号パターンを含むブロックフォーマトされた自己クロッキンググリフ符号の略拡大図。
【図４】本発明の更に詳細な態様に従って２次元の同期符号系列の格子状のフレーム構造を有するグリフ符号パターンの略拡大図。
【図５】重なり合う２次元の同期符号の格子状の構成を有するグリフ符号パターンの略拡大図。
【図６】図４に示されたタイプのグリフ符号パターンの同期符号構成要素及びデータ符号構成要素のフルサイズの図である。
【図７】図５に示されたタイプのグリフ符号パターンの同期符号構成要素及びデータ符号構成要素のフルサイズの図である。
【図８】図６及び図７に示される同期符号及びデータ符号の構成要素から構成される復号グリフ符号パターンのフルサイズの図である。
【図９】アドレス可能に延出された２次元同期符号及び内部ブロックラベルの格子状の構成を有する多数の論理データのブロックフォーマットされたグリフ符号パターンの略拡大図。
【図１０】グリフ符号パターンの損傷の回りを移動するための格子状の同期符号パターンの使用を示す。
【図１１】歪んだグリフ符号パターンを明示的に同期化するための格子状同期符号パターンの使用を示す。
【符号の説明】
３１    復号符号
３２    データ符号
３３    同期符号パターン
３４    データグリフ
３５    記録媒体
３７    同期符号グリフ
【図１】
0003642813.tif 000002
【図２】
0003642813.tif 000003
【図３】
0003642813.tif 000004
【図４】
0003642813.tif 000005
【図５】
0003642813.tif 000006
【図６】
0003642813.tif 000007
【図７】
0003642813.tif 000008
【図８】
0003642813.tif 000009
【図９】
0003642813.tif 000010
【図１０】
0003642813.tif 000011
【図１１】
0003642813.tif 000012