JPH04233677A - セルフクロッキング記号形状コードを復号するための二値画像処理方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】〔発明の分野〕本発明はセルフクロッキン
グ記号（ｇｌｙｐｈ）形状コードを復号する技術に関し
、特にこのようなコードのビットマップ画像空間表現を
復号するため、形態的フィルタリング及びピクセル探索
処理のような二値画像処理技術に関する。

【０００２】〔発明の背景〕普通紙は現在でもなお人間
が読み取り可能な情報を蓄積し、伝達するための優れた
記録媒体であるが、電子文書処理システムの出現によっ
て、人間が通常伝達する人間によって読み取り可能な情
報が適宜の機械読み取り可能なディジタル・データを前
記媒体に書き込むことによって補足されれば、普通紙及
びその他の形式のハードコピー文書の機能的な活用が大
幅に促進されるであろうことは明白になった。この機械
読み取り可能なデータによって、文書が通常の入力走査
機構によってシステムへと走査される時、ハードコピー
文書は種々の方法で前記文書処理システムと能動的に相
互作用することが可能になるであろう。

【０００３】一般に、ディジタル・データは一連の空間
的位置にマークが存在するか否かによって、又は前記位
置でマークに関連する遷移があるか、ないかのいずれか
によってデータを符号化するパターンに従って記録媒体
上に二次元マークを書き込むことによって記録される。 通常は磁気及び光学式ディジタル・データの記録がこの
符号化方式と適応する。更に、用紙上にディジタル・デ
ータを記録するために従来提案されているバー・コード
も前述の符号化方式と適応する。米国特許第４，６９２
，６０３号明細書「印刷されたビット符号化データの光
学式読み取り機構及び読み取り方法」、米国特許第４，
７２８，７８３号明細書及び米国特許第４，７５４，１
２７号明細書「ディジタル式に符号化されたデータを印
刷されたデータストリップへと変換する方法と装置」及
び米国特許第４，７８２，２２１号明細書「ビット符号
化された情報とスキャナ・コントラストを含む印刷デー
タストリップ」を参照されたい。

【０００４】前述のバー・コードを更にやや詳しく考察
すると、その視覚的外見はデータに左右されるので大き
く変動し、まだらの外見になりがちであることが分かる
。このまだらは高画質の印刷文書の簡潔かつ明確な外見
とは容易に見分けられるので、見る人によっては審美的
に受入れ難いものになる。更に、これらのバー・コード
の別の欠点はそれが意図するオーバヘッドである。特に
、前述の特許に則して考察すると、このオーバヘッドは
データ・クロックを保存するための登録マーク及び所定
のコード行に沿って符号化されるビット数のような符号
化されたデータの機構を説明するための見出し情報を含
んでいる。

【０００５】従って、特に機械読み取り可能なデータが
人間により読み取り可能な情報と視覚的に並列されて記
録される用途においては、普通紙及びその他のハードコ
ピー記録媒体にディジタル・データを記録するための比
較的効率よく、視覚的に改良されたコードが緊急の課題
であることは明白である。更に、このようなコードから
ディジタル・データを復元する効率がよく確実な技術が
必要であることは明白であろう。更に、ハードコピー文
書に記録された画像はしばしば複写されるので、かなり
の画像ひずみを許容できるデータ符号化及び復号技術が
あれば好適であることも明白であろう。

【０００６】〔発明の概要〕前述の、及びその他の必要
性に対応して、本発明はセルフクロッキング記号形状コ
ードのビットマップ画像空間表現を復号し、かつこのよ
うなコードの復号中に遭遇する曖昧性（場合により“誤
り”とも呼ばれる）の数と位置を追跡するための二値画
像処理技術を提供するものである。本発明の実施例で実
行される画像処理のかなりの部分は形態的フィルタリン
グ処理を利用して実施されるが、それはこのような処理
にともなう並行処理性のためである。更に、本発明に従
って実行される誤り検出は達成される復号の確実性を高
めるため、スターン（Ｓｔｅａｒｎ）らの復号処理方法
のような別の復号処理による誤りの統計と関連させ、ま
たは比較することができる。

【０００７】〔図面の簡単な説明〕本発明の更に他の特
徴と利点は添付図面を参照した本発明の以下の詳細な説
明よって明らかにされよう。図１は本発明の種々の側面
を実行し、かつその利点を活用するための電子文書処理
システムの簡略構成図である。図２は図１に示した文書
処理システム用の代表的なプロセッサ／インタフェース
の機能構成図である。図３Ａは回転変形の記号形状から
成る比較的簡単なセルフクロッキング二値記号コードに
より達成されるビット符号化を図示したコード図である
。図３Ｂは回転変形の記号形状における二値データのビ
ット符号化を示した別のコード図である。図３Ｃは図３
Ａに示した形式の回転変形の記号形状用の代表的なセル
構造及び代表的な印刷されたピクセル・パターンの図で
ある。図４は第１の記号コード復号プロセスの高レベル
の機能流れ図である。図５は図４に示した復号プロセス
の実現の記号中心の位置決め、ラベル付け及び分類ステ
ップのより詳細な流れ図である。図６は図５に示したオ
プションの較正プロセスによる再較正のための予測され
るラベル付けされた記号中心位置のビットマップ画像で
ある。図７は図４に示した復号プロセスの前述の実施例
の記号読出し／誤り検出ステップの比較的詳細な流れ図
である。図８および図９は比較的低密度と、比較的高密
度の記号コードのそれぞれを復号するために利用される
ピクセル探索領域を示す図面である。図１０は記号形状
の符号化と復号が誤り修正コード（ＥＣＣ）を含むデー
タのために利用されるシステムの高レベルの機能構成図
である。図１１は記号コード画像の周期性に従って構成
された大型のフィルタを利用して記号の中心又はその近
傍のＯＮピクセルを分離するために記号コードのスキャ
ン・インされたビットマップ画像をフィルタリングする
ための形態的フィルタリング・プロセスの機能構成図で
ある。図１２は代表的な記号コードのビットマップ画像
である。図１３は図１２に示したビットマップ画像に図
１１に示したフィルタリング・プロセスを適用した場合
の効果を示すビットマップ画像である。図１４は図１３
に示したビットマップ画像に図１１のフィルタリング・
プロセスの第２レベルのフィルタリングを反復的に再適
用した効果を示す別のビットマップ画像である。図１５
は反復された第２レベルのフィルタリング・プロセスの
機能構成図である。図１６は記号中心を空間的に分離す
るための別の形態的フィルタリング・プロセスによりフ
ィルタリングされた記号コードのビットマップ画像であ
る。図１７は図１６に示したビットマップ画像内のピク
セル・パターンの境界ボックス拡張を示す図面である。 図１８は空間的に比較的低密度の記号コードの場合、図
１６に示したビットマップ画像内の個々の記号関連ピク
セル・パターンの重心を特定することによって、又は、
前記パターンもしくは図１７に示した境界ボックスの拡
張において行われる薄化プロセスによって達成可能であ
る記号中心ピクセルの分離を示すビットマップ画像であ
る。図１９はより高密度の記号コードの記号の空間的分
離を促進するために大型のフィルタを使用した予備的な
形態的フィルタリング・プロセスの機能構成図である。 図２０は図１９のフィルタリング・プロセスが記号中心
位置にホールを発生した場合にＯＮビクセルを記号の中
心位置に復元するために利用できる形態的ビットマップ
画像修復プロセスの機能構成図である。図２１は図１７
に示したビットマップ又は図２０に示した画像修復プロ
セスで薄化プロセスを実行することによって作成できる
ような比較的高密度の記号コードの記号中心のビットマ
ップ画像である。図２２は図２１に示したビットマップ
画像を作成するために利用できる反復的な形態的薄化プ
ロセスの機能構成図である。図２３は小さい、ゆるやか
に突き合わせされたヒット−ミス・フィルタを利用した
記号中心ピクセルを分離するための形態的プロセスの機
能構成図である。図２４はビットマップ画像空間に記号
の中心を位置決めし、かつ、その形状に従って記号を分
類するためにビットマップ・コード画像の畳み込みフィ
ルタリングを利用した復号プロセスの機能流れ図である
。図２５Ａおよび図２５Ｂは各々がフィルタによって強
く突き合わせされた記号形状を有する、畳み込みされた
重みなし、及び重み付のフィルタリングの結果を示す図
である。図２６は図２４に示した復号プロセスの変形さ
れた実施例の部分流れ図である。

【０００８】〔実施態様の詳細な説明〕Ａ．例示的環境
さて図面を、特に図１を参照すると、本発明の代表的な
環境を説明するための電子文書処理システム２１が図示
されている。標準的な実施のために、文書処理システム
２１は主記憶装置２３と、大容量記憶装置２４と、選択
されたハードコピー文書のディジタル表現をプロセッサ
２２へと走査するための入力走査機構２５と、プロセッ
サ２２のファイル・ディレクトリ（図示せず）にリスト
されたファイルの選択された一つを表出するハードコピ
ーを印刷するためのプリンタ２６とから構成されている
。更に、ユーザーがプロセッサ２２、入力走査機構２５
及びプリンタ２６と対話するためのユーザー・インタフ
ェース２７も備えてある。

【０００９】ユーザー・インタフェース２７はユーザー
が入力走査機構２５とプリンタ２６用の制御命令を入力
し、かつプロセッサ２２用の画像編集及び処理命令を入
力するための入力装置を集合的に表すものであることが
理解されよう。更に、インタフェース２７はユーザーが
例えばプログラム制御のようにユーザーその他によって
入力される命令に応答して実行される操作に対するフィ
ードバックを受けるための出力装置をも表している。例
えば、ユーザー・インタフェース２７は基本的にユーザ
ー命令を入力するためのキーボード等と、ユーザーに対
してプロセッサ２２により実行されている処理を視覚化
するためのモニタと、ユーザーがモニタによりディスプ
レーされているプロセスからデータを選択し、かつ前記
プロセスへとデータを入力する双方又は一方のためにカ
ーソルを移動できるようにするカーソル制御装置とを備
えている。（これらの従来の装置はいずれも図示せず）

【００１０】図示した文書処理システム２１は集中化さ
れているので、全ての制御命令と全ての画像編集・処理
命令がプログラム制御のもとでプロセッサ２２によって
実行されるものとの前提で簡略化されている。しかし、
実際にはこれらの命令の実行は幾つかの異なるプロセッ
サによって処理することができ、その幾つか、又は全て
は独自の主記憶装置を、また独自の大容量記憶装置さえ
有することができる。同様に、入力走査機構２５とプリ
ンタ２６の双方又は一方は点線２８，２９のそれぞれに
よって示されるように独自のユーザー・インタフェース
を有することができる。実際に文書処理システム２１は
遠隔入力走査機構及び遠隔プリンタの双方又は一方（図
示せず）によって操作するための分散されたアーキテク
チャを有するように再構成することも可能であろう。デ
ータは専用通信リンク又は切り換え通信網（これも図示
せず）を介してこのような遠隔走査機構及びプリンタ端
末機から、かつそこへと転送可能であろう。

【００１１】通例は入力走査機構２５は所定の空間的解
像度、例えば３００ｓ．ｐ．ｉ×３００ｓ．ｐ．ｉ（ス
ポット／インチ）で各ハードコピー入力文書の画像を走
査するビットマップ走査機構である。操作に際しては、
走査機構２５は走査された画像の個々に分解された画素
（一般に“ピクセル”又は“ペル”と呼ばれる）を対応
するディジタル値へと変換し、これらのディジタル値を
組み立てて、スキャン・インされた値に該当するピクセ
ルの空間的関係を保存するデータ構造（“ビットマップ
画像として知られる”）を作成する。以下の説明は走査
機構２５がスキャン・インされた画像のピクセルを単一
のビット・ディジタル値（すなわち“１”又は“０”）
へと変換するためのモノクロ走査機構である用途に焦点
を当てるが、走査機構２５は必要ならば適宜のしきい値
論理と共にビデオ・ビックアップ素子及びいわゆるビデ
オ“フレーム・グラバー”を使用して文書等のビットマ
ップ画像を捕獲することが可能であることは明白であろ
う。

【００１２】一方、プリンタ２６は一般にビットマップ
された画像ファイルのディジタル値をプリンタが普通紙
のような適宜の記録媒体に印刷する画像の空間的に対応
するピクセルへとマッピングするためのいわゆるビット
マップ・プリンタである。プロセッサ２２はビットマッ
プされた画像ファイルを処理し、かつ記憶し、かつこの
ようなファイルを必要に応じてプリンタ２６へと転送す
るように構成することができる。あるいは、図２に示す
ようにプロセッサ２２は印刷用に選択された電子文書フ
ァイルのＰＤＬ（ページ記述言語）記述をプリンタ２６
へと転送するためのＰＤＬドライバ３１を備えることも
できる。このように、プリンタ２６はこのようなＰＤＬ
記述を分解して、対応するビットマップされた画像ファ
イルを作成するためのＰＤＬ分解器３２を有するものと
して図示されている。更に別の形式のプリンタ及びプロ
セッサ／プリンタ・インタフェースが考えられるが、以
下の説明上、プリンタ２６はプロセッサ２２からＰＤＬ
ファイルを受領するビットマップ・プリンタであるもの
と想定する。

【００１３】Ｂ．記号符号化 図示の通り、プリンタ２６が単独又は人間が読み取り可
能な情報と並行して、記録媒体に機械読み取り可能なデ
ィジタル・データの記号を印刷するようにする記号符号
器３３がある。ある種の用途では、記号符号器３３は電
子文書ファイルをＰＤＬ記述へと変換する前に符号化記
号を電子文書ファイルへと挿入するためにプロセッサ２
２と共に配置してもよい。しかし、別の用途では、記号
符号器３３は符号化記号をプリンタ２６用に備えられた
ラスタフォーマット化されたビットマップ画像ファイル
へと挿入されることが必要であり、又は望ましい。記号
へと符号化されたデータのＰＤＬ記述は幾つかの異なる
フォーマットを有することができ、その中にはこのよう
なデータが符号化されるコードのカプセル化されたビッ
トマップ表現、個々の符号化された記号のビットマップ
表現用の字体記述及びレイアウト位置（このようなビッ
トマップが存在し、又はプリンタ２６の字体ディレクト
リにダウン・ロード可能であると想定した場合）、及び
符号化された記号用のビットマップのビット・バイ・ビ
ット記述が含まれる。

【００１４】更に詳細には、図２及び図３Ａに示すよう
に、符号器３３に供給されるディジタル・データ３５は
記号３６の形状に符号化され、符号器３３によってプリ
ンタ２６がこれを記録媒体に印刷するようにされる。こ
れらの記号はセルフクロッキング記号コードを形成する
が、それは記録媒体に印刷されるコードが符号化された
データ値の各々ごとに別個の記号３６を有しているから
である。実際には図３Ｃに示すように、印刷された記号
３６の各々はほぼ長方形の、二次元のピクセル位置配列
３７内のピクセル・パターン（以後、“記号セル”又は
“データ・セル”と呼ぶ）によって形成される。例えば
図３Ｃを参照のこと。これらの記号を形成するデータ・
セル３７は通常は所定の空間フォーマット化ルールに従
って記録媒体上にタイリングされ、それによって連続す
るデータ値用の符号化記号３６は所定のテンプレートも
しくはパターンに従って空間的に分散される。例えば、
連続するデータ値用の符号化記号３６を含むデータ・セ
ル３７はルール的かつ反復的な論理データ・ブロックフ
ォーマット化ルールに従って記録媒体上に適宜に印刷さ
れ、印刷されたデータ・セルが例えば１６セル×１６セ
ルの論理ブロックフォーマットのような所定のサイズの
論理ブロックの二次元配列に空間的に編成されるように
される。

【００１５】記号の符号化は明らかに多くの異なる形態
が可能であり、そのうちのあるものは単一ビット・ディ
ジタル値の符号化に適しており、別のあるものは多重ビ
ット値の符号化に適している。例えば、単一ビット値（
“１”及び“０”）は細長い、多重ピクセルの記号によ
って符号化することが便利であり、その各々はそこで符
号化されるデータ値が“１”であるか“０”であるかに
応じて記録媒体の横軸から約＋４５°又は−４５°の角
度に傾斜した軸に沿って位置決めされた所定数の隣接す
る“ＯＮ”（すなわち黒）ピクセルから構成される。 このような記号はいわゆる“回転変形”記号の例である
が、それは単なる回転操作によって互いにマッピング可
能であるためである。これらは又、著しいひずみ及び画
像の劣化がある場合でも容易に判別できる記号の例でも
ある。その理由は普通の形状には劣化しないからである
。

【００１６】記号３６の全てが同数の“ＯＮ”ビクセル
を有するように記号を選択することの重要な利点は、印
刷された記号コードが、カーソルの観察者によって密度
が高い記号が観察されるとグレー・スケールの外見を有
するほぼ均一なテクスチャを有することである。従って
、この利点は記号３６の回転及び輪郭の双方又は一方（
ここでは集合的に“形状”と呼ぶ）でデータを符号化す
ることによって実現できることは特筆に値する。例えば
、単一ビット・ディジタル値は明確に異なる輪郭を有す
る回転変形記号によって符号化することができるが、“
１”及び“０”のそれぞれの符号化用の“０Ｎ”ピクセ
ルの数は同数である。例として図３Ｂを参照されたい。 印刷された記号コードのグレー・トーンの外見は記号の
ＯＮピクセル内容を増減することによって見かけがよい
グレー・トーンへと“同調”することができる。更に、
印刷された記号コードのグレー・トーンの外見は、いわ
ゆるグレー・スケール画素値に従って（図示しない手段
によって）変調することができ、それによって印刷され
たコードにグレー・スケールの画質を付与することがで
きよう。

【００１７】柄文字符号化は単に２ｎ　の許容できる記
号の形状を有するコードを使用することによって理論上
は任意の所定のビット長ｎのディジタル値の符号化へと
拡大することができるが、その場合、コードはその記号
の形状が互いに確実に判別できるように注意して選択さ
れる必要がある。何故ならば、そのような識別は符号化
されたデータを性格に復元するために不可欠であるから
である。

【００１８】Ｃ．記号コードの復号 １．概要 さて図４を参照すると、本発明に従って従来型の印刷記
号コードはそれらのビットマップ画像を処理することに
よって復号されることができる。図示のようにこのよう
な記号コードを復号するための画像処理技術は相当量の
画像ひずみ及び劣化を許容できるので、スキャン・イン
されたフォトコピー及びファクシミリ・コピーに含まれ
るコードは、スキャン・インされた文書が原本から多す
ぎる生成要素が除去されていない限りは復号することが
できる。勿論、印刷された記号コードは符号化されたデ
ータを復元するためにコードを復号する適宜の電子文書
処理システムを使用し、かつ、次に符号化された全く同
一のデータを有するコードを再印刷することによって再
生することができ、その際、復号及び再符号化は基本的
に本明細書に記載されているように実行される。

【００１９】ある種の復号器では、記号コードを復号す
るために実行される画像処理は先ず、ビットマップ画像
空間のＸ−Ｙ座標に記号を位置指定し、次にデータが符
号化された空間順に記号を指標付けするためのテーブル
を構成し、次にその中に符号化されたデータ値を順次抽
出するために記号を指標順に分析する。別の復号器では
、画像処理は同時に中心をビットマップ画像空間に位置
決めしつつ、記号をその空間によって分類することによ
って、記号の復号された値はビットマップ画像空間に好
適に指標付けされる。しかし、これらの空間的に指標付
けされた復号データ値は、一連の順序を時間領域に再記
憶することが必要な場合は、空間順を統括する空間的テ
ンプレートもしくはパターンに従って分類することがで
きる。

【００２０】２．二値画像処理による復号ａ．序 本発明の復号プロセスに更に焦点を当てると、図４に示
したプロセスでは記号コードのビットマップ画像は先ず
、例えばステップ４１において記号のおおよその、すな
わち外見上の中心を分離するため形態的に及び（又は）
ピクセル探索技術を利用して処理される。次にコーナー
の記号の外見上の中心のような、これらの記号の外見上
の中心の所定の一つを基準点として用いて、記号コード
が複写及び（又は）スキャン・インされている間に記号
コードに発生することがある歪み誤差及びＸ及びＹ座標
の縮尺誤差のそれぞれをを補償するためにステップ４２
で適宜の歪み及びＸ及びＹの縮尺補正要素が計算される
。理解されるように、これらの補正要素は記号の中心を
ラベル付けするステップが記号の中心から記号の中心（
あるいは更に精密には次の記号中心の予測位置）へと飛
び越しできるようにするベクトルを計算するために用い
られる。このように、相対的に位置測定されたピクセル
探索ステップによって、例えばステップ４３でＸ及びＹ
の画像空間座標を有する各々の記号の外見上の中心ピク
セルを充分にラベル付けすることができる。画像のノイ
ズ成分にはラベルが付与されないので、この時点で著し
いノイズは効果的に拒絶される。

【００２１】データは一般に論理ブロック毎に、セル毎
の順序で符号化されることを想起されたい。そのため、
ステップ４５に示すように、記号用のＸ−Ｙ座標ラベル
は一般にデータ符号化の空間的順序に従って分類され、
それによってデータが符号化されたと同じ順序で記号を
逐次アドレス指定するための指標テーブルが構成される
。あるいは、必要ならば、記号がアクセスされる順序で
記号の選択された一つを復号するためにステップ４５で
指標が構成されるように、ビットマップ画像空間内の単
数又は複数の予め選択された位置で記号を無作為にアク
セスするためにポインタ（図示せず）を備えてもよい。 例えば、ビットマップ画像空間内で任意の２つの所定の
記号中心のＸ及びＹ座標がそれぞれ互いに変位される方
向及び記号中心の数を計算することによって、任意の一
つの記号の中心からビットマップ画像空間の別の任意の
記号の中心へと前記ポインタを比較的迅速に移動するた
めに直送式Ｘ−Ｙシークを利用することができる。 このような方向情報と中間の記号中心のカウントがあれ
ば、先ず、ポインタが所定数の中間記号中心をスキップ
するまで、ボインタを記号の中心から記号の中心へと例
えばＸ軸に沿って指定の方向に増分的にシフトし、次に
、別の軸、すなわちＹ軸に沿ってポインタを意図する行
き先へと増分的にシフトするために前記のプロセスを反
復することによって適正なシークを実行することができ
る。

【００２２】記号コードから符号化されたデータを復元
するためには、ステップ５１で２ｎ　の許容される記号
の形状の各々ひとつに突き合わせされたフィルタによっ
て、コードのビットマップ画像の２ｎ　のコピー（ここ
にｎは各々の記号内で符号化されたデータ値のビット長
）がそれぞれフィルタリングされる。例えば、これらの
画像の各々は許容される記号の形状の各々一つ（しかも
一つだけ）にゆるやかに突き合わせされたヒット・ミス
・フィルタに従って形態的に処理することができる。そ
れによってビットマップ画像の２ｎ　の異なってフィル
タリングされたバージョンが生成される。更に詳細に述
べると、ヒット・マス・フィルタリングの結果、フィル
タリングされた画像の任意の一つにおける任意の所定の
記号中心、すなわち“データ・ラベル”位置に近似する
ピクセル・パターンは所定の画像を作成するために使用
されるヒット・ミス・フィルタと、所定のデータ・ラベ
ル位置との突き合わせの精密さに左右される。（すなわ
ち突き合わせが近いほど、より多数の“ＯＮ”ピクセル
がｅデータ・ラベル位置に近似する。）従って、フィル
タリングされた画像のピクセル・パターンがステップ５
２で論理的符号化順に（又は乱アクセス順に）データ・
ラベル位置毎に比較され、ステップ５３で、連続する記
号の一つに符号化されたデータ値が判定され、かつ逐次
読み出される。

【００２３】ｂ．定義 復号処理を更に詳細に検討する前に、“形態的な画像処
理操作”を説明するための用語の幾つかを簡単に説明す
ることが有用であろう。

【００２４】“形態的な処理”とはビットマップ画像（
“ソース画像”と呼ばれる）での処理であり、これは別
のビットマップ画像（“行き先画像”と呼ばれる）を作
成するため、ソース画像を有する各ピクセル位置で局域
内ルールを用いる。便宜上、ソース画像及び行き先画像
は時として“ピクセルマップ”画像と呼ばれ、処理速度
は各“ピクセル”での処理操作速度とみなすことができ
る。“ビットマップ”と“ピクセルマップ”はある種の
データ構造では同義語であり、“ビット”及び“ピクセ
ル”はこのようなデータ構造の内容を説明するために互
換的に用いられる。

【００２５】“構造体要素“（ＳＥ）とは選択された形
態的な処理を利用してソース画像から情報を抽出するた
めにソース画像を探査するための、一般にサイズが比較
的小さく、形状が比較的単純な画像対象のことである。 本明細書で以下に述べるＳＥは二値ＳＥである。これら
のＳＥは“０Ｎ”ピクセルを表示するために●を用い、
又、“ＯＦＦ”ピクセルを表示するために○を用いて図
示される。それらの中心はビデオクロスによって表示さ
れる。ＳＥには更に“ドント・ケヤ”（どちらでも良い
）ピクセルも含まれ、このようなピクセルは白抜きの正
方形で示されることに留意されたい。

【００２６】以下の用語は二値形態的処理に特有の用語
である。

【００２７】“ＥＲＯＳＩＯＮ”（侵食）は“ｏｎ”（
１）又は“ｏｆｆ”（０）ピクセルをソース画像内の各
ピクセル位置用の行き先画像へと書き込むためにＳＥに
よって二値ソース画像を探索する操作であり、その際、
所定の任意の位置に書き込まれるピクセルの論理レベル
は所定のピクセル位置の中心にある時にＳＥがソース画
像によって突き合わせされるかどうかによって左右され
る。突き合わせされるＳＥが“ヒット”と“ミス”の双
方を含んでいる場合は、突き合わせ処理は一般に“ヒッ
ト・ミス”変換と呼ばれる。しかし、説明を簡略にする
ため、ＥＲＯＳＩＯＮの定義はこのようなヒット・ミス
変換を含むように拡大されている。

【００２８】“ＤＩＬＡＴＩＯＮ”（膨張）は二値ソー
ス画像をＳＥで探索して、ＳＥをソース画像内の全ての
“ＯＮ”ピクセルの位置に対応する中心上の行き先画像
を書き込むことによって実行される処理操作である。こ
こで用いるＤＩＬＡＴＩＯＮはＳＥ内の“ヒット”のみ
のためにに定義されており、“ミス”は無視される。こ
のように、膨張された行き先画像はソース画像の全ての
１−ピクセルに変換されたＳＥの全ての複製の集合であ
る。

【００２９】“ＯＰＥＮＩＮＧ”（開）はソース画像内
でのＳＥへの突き合わせ毎に行き先画像内でＳＥを複製
する操作である。これは同じＳＥによって侵食された画
像のＤＩＬＡＴＩＯＮに先行する、ＳＥによるソース画
像のＥＲＯＳＩＯＮと同義である。ＥＲＯＳＩＯＮとＤ
ＩＬＡＴＩＯＮの前記の定義を保持するために、ＳＥ内
の“ヒット”だけによるＤＩＬＡＴＩＯＮに先行する、
“ヒット”と“ミス”の双方を含むＳＥによるＥＲＯＳ
ＩＯＮを含むようにＯＰＥＮＩＮＧ操作の定義を拡大し
ている。

【００３０】“ＣＬＯＳＩＮＧ”（閉）は膨張された画
像のＥＲＯＳＩＯＮに先行するソース画像のＤＩＬＡＴ
ＩＯＮから成る操作である。画像のＣＬＯＳＩＮＧはビ
ット反転されたソース画像で実行されるＯＰＥＮＩＮＧ
のビット反転と同義である。前述のＤＩＬＡＴＩＯＮの
定義に鑑み、ＣＬＯＳＩＮＧはここではＳＥ内の“ヒッ
ト”のみのために定義されており、“ミス”は無視され
ることが理解されよう。

【００３１】形態的な処理操作は変換上、不変量である
。換言すると、ソース画像は変換される前に変形される
ことができるので、結果はその他の方法で変更すること
なく同じ量だけ変換もしくはシフトされる。これはソー
ス画像内の各ビットもしくはピクセルが同じルールに従
って処理されるので、これらの操作が高度の並行処理で
実行されることを意味する。

【００３２】“ヒット”だけから成るＳＥによって実行
されるＥＲＯＳＩＯＮ、ＤＩＬＡＴＩＯＮ、ＯＰＥＮＩ
ＮＧ及びＣＬＯＳＩＮＧの操作は幾何学的に“増分”さ
れた操作である。従って、第１の画像が第２の画像内に
含まれている場合は、第１の画像でこのようなＳＥによ
って実行される前記操作は第２の画像にも含まれる。更
に、ＣＬＯＳＩＮＧは“拡張的”であり、ＯＰＥＮＩＮ
Ｇは“非拡張的”である。従って、ソースがＣＬＯＳＩ
ＮＧによって変換される場合はソース画像が行き先画像
内に含まれ、ソースがＯＰＥＮＩＮＧによって変換され
る場合は行き先画像がソース画像内に含まれる。ＯＰＥ
ＮＩＮＧ及びＣＬＯＳＩＮＧ操作の結果はＳＥの中心位
置とは関わりない。更に、ＯＰＥＮＩＮＧ及びＣＬＯＳ
ＩＮＧ操作は補償能力がある。すなわちこれらの操作は
変換された画像に再適用されても変換された画像を変化
させない。

【００３３】形態的な操作を説明する上でしばしば用い
られるその他の用語は次の通りである。

【００３４】“４−接続領域”とはＯＮ（“１”）ピク
セルの集合であり、完全にＯＮピクセルの集合内にあり
、水平又は垂直の１ピクセルの移動のみから成る、これ
らのピクセルの何れか２つの間の経路を発見できるよう
な領域である。

【００３５】“８−接続領域”とはＯＮ（“１”）ピク
セルの集合であり、完全にＯＮピクセルの集合内にあり
、水平、垂直又は対角線方向の１ピクセルの移動のみか
ら成る、これらのピクセルの何れか２つの間の経路を発
見できるような領域である。

【００３６】“ヒット−ミス”ＳＥとは非ゼロのＯＮピ
クセルの集合と、非ゼロのＯＦＦ（“０”ピクセルの集
合を指定するＳＥであり、これらの２つの集合は重複し
ない。（すなわち交叉しない）“ゆるやかに”突き合わ
せされたフィルタはそれが突き合わせされたピクセル・
パターンの比較的少ないピクセルを指定し、一方、“強
く”突き合わせされたフィルタはそれが突き合わせされ
たピクセル・パターンのうちの大きい比率のピクセルを
指定する。

【００３７】“ヒットのみ”ＳＥは非ゼロのＯＮピクセ
ルの集合を指定するＳＥである。

【００３８】ｃ．詳細な実施例 さて図５を参照すると、一般に受け入れられている実施
形態を保ちつつ、記号復号プログラムを実行するために
使用されるプロセッサ及び主記憶装置資源は、復号プロ
グラムが呼び出される毎にステップ６１で再度初期化さ
れる。図１に示した実施例では、プロセッサ２２はその
主記憶装置２３と、又、必要ならばその大容量記憶装置
２４（図１）と通信して記号復号処理を実行するが、復
号処理は主記憶装置２３又は別個の記憶システム（図示
せず）を使用して別個のプログラム内蔵プロセッサ（図
示せず）の制御のもとでも実行できることは明白であろ
う。

【００３９】ｉ．クロック回復 システムが所定の記号コードを復号するために初期化さ
れると、コードのビットマップ画像のコピーが例えばス
テップ６２で主記憶装置に装填され、次にこの画像はス
テップ６３で変換されて、コードの各記号用に少なくと
も一つの、しかし数個未満の中心に位置決めされたビッ
ト、すなわち“ピクセル”からなる同一の縮尺されたビ
ットマップ画像が得られる。後述するように、変換を行
うステップ６３は一般に記号が印刷される空間密度に適
合するようにされる。何故ならば、高密度の記号は低密
度の記号よりも印刷、複写及び走査中に生ずるぼやけに
よって分離しがたく併合され易いからである。スキャン
・インされた記号が良く分離されると、各々の中心の近
傍で単一ピクセルに収縮することができる。一方、スキ
ャン・インされた記号が接触する場合は、これらの記号
は先ずフィルタリングによって互いに分離され、その後
、収縮することができる。この時点で、変換ステップ６
３は記号コードのスキャン・インされたビットマップを
コードの各データ・セルのおおよその中心で単一ピクセ
ルを含むビットマップへと変換する。しかし、これは必
ずしも不可欠ではないことを理解されたい。

【００４０】ｉｉ．歪み及び縮尺の判定実際には、復号
されるべき記号コードのスキャン・インされた画像は水
平から時計回り、又は逆時計回り方向に歪むことがあり
、かつ、そのＸ軸及びＹ軸の双方又は一方に沿った異な
る大きさの縮尺誤差によりひずむことがある。そのため
、ステップ６５で、（図示のように）記号毎のベースで
、又はデータ・ブロック毎のベースで（図示せず）、又
は画像歪み取り及び再基準化プロセス（これも図示せず
）を利用して前記誤差を修正するための歪み及び縮尺補
正要素を計算する措置が取られている。

【００４１】明らかであるように、歪み及び縮尺補正要
素は周知の、又は判定可能である公称の（すなわち誤差
がない）空間関係を有する、スキャン・インされたビッ
トマップ画像空間内の３つまたはそれ以上の基準共線点
のいずれかのＸ−Ｙ座標から計算することができる。こ
れらの基準点の一つは変換上、不変量の基準位置を確定
するために選択されるので、歪み及び縮尺誤差は別の基
準点の各々の実際位置と公称の位置とが前記の空間的に
定められた基準位置から変位する距離と角度とを比較す
ることによって判定することができる。

【００４２】既に指摘したように、データ符号化された
記号は一般にほぼ方形のデータ配列もしくはデータ・ブ
ロック内の所定の空間密度で印刷さるので、データ・セ
ルを規定する記号の中心（本明細書では一般に記号中心
と呼ばれる）は通常はほぼ長方形の構成に配置される。 従って、歪み及び縮尺補正要素は印刷された記号コード
の少なくとも３つのコーナー記号の外見上の中心ピクセ
ルのＸ−Ｙビットマップ画像空間座標から適切に計算さ
れる。（しかし、いわゆる“基準点”の必要な特性の前
述の説明から、他の任意の独自に識別可能な記号の外見
上の中心をコーナー記号の外見上の中心の代わりに、又
はそれに加えて用いることができることは明白である。 ）このように、図示のとおり、ステップ６５で歪み及び
縮尺補正要素を計算するのに必要な情報が全て収集され
たことがステップ６８で判定されるまで、選択されたコ
ーナー・ピクセルの連続するＸ−Ｙ座標はステップ６６
で特定され、ステップ６７で記憶される。

【００４３】しかし、このような歪み及び縮尺補正要素
を計算するために、コーナー記号の外見上の中心の代わ
りに、又はそれに加えて他の任意の独自に識別可能な記
号の外見上の中心を利用できることは再度理解すること
が必要であり、その場合はいわゆる“基準点”の必要な
特性の前述の説明を参照されたい。更に、コーナー記号
の中心ピクセルは六角形の格子パターンのような別の種
類の記号コード・パターン用の歪み及び縮尺補正要素を
計算するために利用できることを理解されたい。

【００４４】適宜の歪み及び縮尺補正要素を計算するた
めに充分な精度を備えたコーナー・ピクセルのＸ−Ｙ座
標を特定するために、変換ステップ６３で得られる変換
されたビットマップで比較的直送式の画像分析を実行す
ることができる。外見上の記号中心ピクセルのビットマ
ップ画像が左から右、及び上から下の順序で走査される
場合は、遭遇する最初のＯＮピクセルは画像の左上（Ｕ
Ｌ）コーナーのピクセル又は右上（ＵＲ）コーナーの近
傍のピクセルのいずれかである。この曖昧性を解決する
ため、このピクセルは仮にＵＬコーナーのピクセルとし
て受入れられるが、左にＭ以上のピクセルがあり、仮に
受入れられたピクセルの下にＮ未満の走査線がある、任
意の引き続き走査されたピクセルにＵＬコーナー・ピク
セルの行き先を付与するには受入れられない。

【００４５】ある場合にはＵＬコーナーの記号が不明で
あることがあるので、記号コードの第１行目の第２の記
号のおおよその中心を表すピクセルを仮にＵＬコーナー
・ピクセルであると特定してもよい。しかし、記号、も
しくはデータ・セルの中心から中心の垂直の平均間隔よ
りも（走査線内で）わずかに大きくＮを選択すると、Ｎ
の走査線の走査中の任意の時点で、仮に受入れられたピ
クセルの左から約１つのデータ・セル分の距離でＯＮピ
クセルに遭遇した場合は、前記の誤差はＵＬコーナー・
ピクセル位置をビットマップ画像に帰することによって
検出され、かつ修正されることができる。別の場合には
、第２行のデータ内の第１の記号のおおよその中心をマ
ークするピクセルがＵＬコーナー・ピクセルのやや左に
あることがある。しかし、Ｍをデータ・セルの（プリン
タのピクセル、すなわちペル内の）平均的な中心から中
心への水平変位の適宜に大きい分数（例えば約１／２）
の値に選択すると、ビットマップ画像が例えば２０°未
満しか歪んでいない場合はこの逸れは基本的に無視され
る。簡略に述べると、ＭとＮの好ましい値は印刷された
記号のペル内のデータ・セルのサイズによって左右され
る。データ・セルのサイズが１０ペル×１０ペルである
場合は、Ｍは約５ピクセルに等しく選択され、Ｎは約１
５の走査線に等しく選択されることが適切である。 比較すると、５ペル×５ペルの場合は、一般にＭは約３
ピクセルに等しく選択され、Ｎは一般に約８の走査線に
等しく選択される。

【００４６】スキャン・インされた記号コード・パター
ンのＵＬコーナーを位置指定するための前述のプロセス
は、スキャン・インされるコード・パターンの右上（Ｕ
Ｒ）コーナー、左下（ＬＬ）コーナー及び右下（ＬＲ）
コーナーの記号の外見上の中心ピクセルを位置決めする
ための対応するプロセスを付与するために直送式アナロ
ジーによって拡張できるものである。これらのコーナー
・ピクセルのＸ−Ｙ座標は（０，０）基準座標を、例え
ばＵＬコーナーでのピクセルへと割当て、かつ、次に別
のコーナー・ピクセルの全ての座標を前記基準座標と照
合することによってビットマップ画像空間内で特定する
ことができる。

【００４７】あるいは、コーナー記号のいずれか又は全
ての外見上の中心ピクセルはＵＬ及びＬＲについては右
上方に、又、ＵＲ及びＬＬについては左上方に傾斜した
走査線に沿って単一又は複数回の走査を行うことによっ
て発見することができる。この走査線は最初は記号コー
ド・パターンの外側の安全距離に位置しているが、各々
の連続する走査毎に目標のコーナー記号の方向に増分的
にシフトして、次第に前記化文字に接近する。従って、
目標のコーナー記号の外見上の中心ピクセルは通常はこ
の走査プロセスが遭遇する最初の“ＯＮ”ピクセルであ
る。

【００４８】印刷された記号のデータ・セルのサイズと
、印刷された記号のコード・パターンの外見上の中心ピ
クセルのＸ−Ｙビットマップ画像空間座標が定まると、
記号コードのビットマップ画像の回転及び縮尺は前述の
ように確定することができる。あるいは、フーリェ変換
又はワルシュ変換のような周波数変換を記号コードのス
キャン・インされたビットマップ又は記号中心ピクセル
のビットマップの００れかで実行することによって、記
号の周期性を確定することができる。

【００４９】ｉｉｉ　．飛び越し、探索及びラベルこの
ように、記号コードのビットマップ画像内の隣接する記
号の中心間の平均ピクセル数もステップ８０において計
算できることが明らかであろう。この情報があれば、飛
び越し及び探索プロセスを例えば外見上の記号中心のビ
ットマップ画像のＵＬコーナー・ピクセルで開始して、
印刷された記号コードの空０的に近接した連続する行か
ら空間的に近接した連続する記号の外見上の中心のおお
よそのＸ−Ｙビットマップ画像空間の座標をステップ７
１で特定し、ステップ７２でこれを記憶することが可能
である。この座標ラベル付けプロセスはＵＬコーナー・
ピクセルからその右側の近隣の予期される位置への飛び
越しによって開始される。その位置でＯＮピクセルが発
見されれば、ピクセルにはそのＸ−Ｙ座標がラベル付け
され、次にプロセスは次の近接する記号の予期される中
心位置に飛び越す。これに対して、プロセスが予期され
る中心位置にＯＮピクセルを発見しなかった場合は、プ
ロセスは代表的には拡張ダイアモンド状、又は螺旋状の
探索パターンを用いて拡張された探索を実行し、予期さ
れた中心位置から一つの方向又は別の方向の幾つかのピ
クセル位置内にＯＮピクセルがあるかどうかを判定する
。ある場合は、それが遭遇した最初の“ＯＮ”ピクセル
にＸ−Ｙ座標をラベル付けし、次に次の隣接する記号の
予測中心位置へと飛び越す。逆に、探索によって隣接す
るＯＮピクセルを発見しなかった場合は、プロセスは次
の記号の中心ピクセルを位置決めするために飛び越す前
に、記号の中心ピクセルを発見すると予測される位置に
適宜に戻って、その位置にＸ−Ｙ座標をラベル付けする
。このプロセスはスキャン・インされた記号コードの記
号毎に、又、行毎に継続され、各々の、又、全ての記号
中心位置についてビットマップ画像空間にＸ−Ｙ座標の
ラベルを付与する。

【００５０】ｉｖ．再較正された記号中心のラベル付け
（オプション） 図６に示すように、記号中心が記号中心ビットマップ画
像内で良く分離されない場合は、前述の飛び越しにより
実行される記号中心のラベル付けには誤りが含まれるこ
とがある。高密度の記号コードのスキャン・インされた
ビットマップ画像から記号中心ビットマップ画像を作成
するために利用できる変換プロセスには前記の分離が全
ての記号中心でなされることを保証しないものがあるの
で、前記画像の記号中心用にＸ−Ｙ座標ラベルを再計算
するためのオプションの較正プスセスがある。

【００５１】図５を参照すると、このオプションの較正
プロセスは所定の記号中心の集合の重心からの記号中心
ピクセルの平均距離に基づいて、これらの集合の各々の
内部の全ての記号中心ピクセル用にＸ−Ｙ座標を再計算
するために単数又は複数の記号中心ピクセルの集合の重
心のＸ−Ｙ座標を利用することが示されている。この較
正は記号中心ビットマップ画像の重心に対して記号中心
ピクセルのＸ−Ｙ座標を較正するために一度だけ実施し
てもよい。あるいは、図示のように、ステップ８３で確
定される各々の重心に対して記号中心ピクセルの連続す
る集合（例えば１６×１６のブロック）のＸ−Ｙ座標を
ステップ８２で較正するため、ステップ８１で前記の較
正を反復してもよい。

【００５２】ｖ．符号化されたデータ値の時間領域への
復元 Ｘ−Ｙラベルが記号中心ピクセルに付与され、それらの
必要な全ての較正が完了した後、通常、Ｘ−Ｙ座標ラベ
ルは論理ブロック・シーケンスに記憶され、それによっ
てデータが前記ラベルを付与された記号へと符号化され
る順序に従って逐次前記ラベルが再度順序付けされる。 更に、ステップ８５に示すように、増分する指標値が再
度順序付けされたラベルに割当てられるので、これらの
ラベルは分類された順に容易に検索することができる。

【００５３】ｖｉ．記号の形状からのデータ値の確定図
７を参照すると、記号に指標付けされたＸ−Ｙ座標が付
与されると、記号コードは論理シーケンスで個々の記号
の形状を分析することによって復号し、逐次個々の記号
に符号化されたデータ値を判定することができる。この
記号の形状分析を実施するため、ステップ１０１でスキ
ャン・インされた記号コードのビットマップ画像はステ
ップ１０２で複数の異なるフィルタに従って別個にフィ
ルタリングされ、その各々は許容される記号形状の各々
の一つからのピクセルをパスし、かつ、別の記号形状の
全てからのピクセルを抑制するためにステップ１０３で
選択される。このような理由から、フィルタは許容され
る記号の形状のそれぞれの一つに個々に“同調”される
と言うことができる。ビットマップ・フィルタリングは
図７に示すように直列でおこなってもよく、図４に示す
ように並列で行ってもよい。いずれの場合も、フィルタ
リングされたビットマップはステップ１０４で記憶され
るので、以下に説明するように復号プロセスの記号毎の
分析ステップ中に検索することができる。

【００５４】フィルタリングされたビットマップ画像を
得るには、記号コードのビットマップ画像は複数の異な
る弱いヒット−ミス・フィルタに従って独立した操作に
よって形態的に侵食されることが有利である。前記フィ
ルタの各々は異なる一つの許容できる記号の形状には比
較的よく適合され、他の全ての形状には比較的不十分に
しか適合されない。これらのフィルタは記号の形状（す
なわち、記号の形状を規定する“ＯＮ”及び“ＯＦＦ”
ピクセルのパターン）をゆるやかにしか指定しないので
“ゆるやかな”ヒット−ミス・フィルタと呼ばれる。そ
の結果、ソース画像内での適合する記号のフィルタリン
グによって一般に、適合する記号の中心の近傍で幾つか
のＯＮピクセルが目標画像、すなわちフィルタリングさ
れた画像へと書き込まれ、一方、非適合記号のフィルタ
リングによって、仮にある場合でも、著しく少ないＯＮ
ピクセルが非適合記号の中心の近傍でＯＮビクセルが目
標とされる画像へと書き込まれる。言い換えると、フィ
ルタリングによって特定の画像を生成するために利用さ
れるフィルタによって充分に適合された記号については
、前記フィルタによって適合されない、もしくは不十分
にしか適合されない記号についてよりも著しく多数のＯ
Ｎピクセルがフィルタリングされた画像に書き込まれる
。

【００５５】フィルタリングされたビットマップ画像の
全てが構成されたことがステップ１０５で判定された後
、ステップ１０６で記号指標ポインタ１０７が復号され
るべき最初の記号用の指標値にセットされ、それによっ
て記憶装置からの最初の記号用のＸ−Ｙ画像空間座標の
ラベルが検索される。ステップ１１１でこのラベルは復
号されるべき記号のほぼ中心でフィルタリングされたビ
ットマップ画像を連続して空間的にアドレス指定するた
めに使用されるので、これらの画像の各々が含む前記特
定の記号の中心の近傍のＯＮピクセルはステップ１１２
でカウントすることができる。一方、これらのカウント
はステップ１１３でデータ配列の別個のセルに記憶され
る。

【００５６】代表的には、ピクセルのカウントはアドレ
ス指定された記号のラベル付けされた中心点で開始され
、次にそこから外側に移動して記号の中心点を中心とす
る選択された数の次第に大きくなる正方形内にあるＯＮ
ピクセルの数をカタウントすることによって行われる。 この“方形リング”探索パターンは１ピクセル位置／リ
ングの比率で全方向に伸張するが、探索は復号されてい
る記号用のデータ・セルに限定される。例えば、図８に
示すように、記号毎に１０×１０ペルのデータ・セルを
使用して９００ビット／平方インチの密度で書き込まれ
る記号コードには３つのリングの探索が適当である。こ
れとは対照的に、図９に示すように、５×５ペルのデー
タ・セルを使用して３６００ビット／平方インチの密度
で書き込まれる記号コードには２つのリングの探索が適
当である。いずれの場合も、最も内側のリングはＸ−Ｙ
座標のラベル付けされた記号の中心点である。

【００５７】ステップ１１５（図７）で所定の記号につ
いての全てのピクセル・カウントが累積されたことが確
認されると、それらのピクセル・カウントを含むデータ
配列はステップ１１６でカウント値のランク順に記憶さ
れるので、ステップ１１７では２つの最大カウントを比
較のためにそこから直送式に抽出することができる。ス
テップ１２１で判定された結果、これらのカウントが等
しくない場合は、最大カウントを生じた記号の形状に関
連するデータ値はステップ１２１で所定の記号用の指標
に割当てられる。これに対して、比較検査１２１によっ
て２つの最大カウントが等しいことが判定されると、誤
りカウントが増分されて、発生する復号の曖昧性の数が
追跡され、曖昧性又は“誤差”がどこで生じたかを指示
するために曖昧な記号のＸ−Ｙ座標ラベルが記憶される
。次に、ステップ１２６で復号されるべき記号が更にあ
ることが判定されると、ステップ１０７で記号の指標値
が増分されて、カウント及び比較スプロセスが次の記号
について反復される。

【００５８】ｖｉｉ．　　誤差修正符号化を利用したシ
ステム図１０に示すように、記号形状の符号化と復号は
誤差修正コードを含むデータ用に利用することができる
。その目的のため、データはステップ１３１で記号形状
に符号化され、次に符号化された記号形状はステップ１
３２でラスタ形式に変換されるので、これらの形状はビ
ットマップ・プリンタによって普通紙のような適宜の記
録媒体に印刷されることができる。引き続いて、印刷さ
れた画像（これには人間が読み取り可能な情報と記号コ
ードとが含まれる）が入力走査プロセス１３４によって
ビットマップ画像に変換される。このビットマップ画像
はステップ１３５で記号コードのスキャン・インされた
画像を分離するためにパージングされるので、ステップ
１３６で前述の復号プロセスを利用して復号されたデー
タ値を記号もしくはデータ指標に割り当てることができ
る。次に記号に復号されたデータはステップ１３７で、
誤差修正された形式の元のデータを得るために誤差修正
コード復号器によって処理される。

【００５９】ｖｉｉｉ．記号中心ピクセルを分離するた
めの変換 記号形状コードの記号の中心を特定する問題に戻って、
その機能を果たすための３つの異なる技術を説明する。 図５のステップ６３で記号コードのスキャン・インされ
たビットマップ画像を記号中心ピクセルのビットマップ
へと変換する２つの方法をこの項で説明し、このような
変換を必要としない第３の方法は次の項で説明する。従
って、この項では、変換プロセス６３は記号の評価とは
別個の異なるステップとして記号中心を分離するために
実行されるものと想定する。理解されるように、変換プ
ロセス６３は記号コードの周期性を表す大型のフィルタ
（これらのフィルタは代表的には２−６サイクルの長さ
である。）を利用し、又は、個々の記号形状を表す小型
フィルタ（これらのフィルタは通常は記号よりもやや小
さい）を利用して実行することができる。

【００６０】先ず大型フィルタによる変換６３の実行を
考察すると、密度が低い記号コードの記号（すなわち６
ペル×６ペルのように小さい記号セルを使用して約２５
００記号／平方インチの密度で印刷される記号）は通常
は記号コードのスキャン・インされたビットマップ画像
内で適度によく分離される。従って図１１に示すように
、それらの外見上の中心ピクセルは一般にステップ１４
１において大型の水平ヒット−ミス・フィルタ及びステ
ップ１４２において大型の垂直ヒット−ミス・フィルタ
に従ってスキャン・インされたビットマップ画像１４０
（図１２参照）を「開」（０ＰＥＮＩＮＧ）することに
よって充分な精度で特定することができる。これらの０
ＰＥＮＩＮＧ操作の結果、ステップ１４３でビット論理
和されて、比較的小さい対角線ＯＮピクセル構造を有す
る第１レベルのフィルタリングされたビットマップ画像
が構成される。次に、フィルタリングされたビットマッ
プ画像はステップ１４４及び１４５でそれぞれ水平及び
垂直のヒット−ミス・フィルタに従って「開」され、こ
れらの操作の結果はステップ１４６でビット論理積演算
されて、更に小さい対角線構造と小さい垂直及び水平構
造を有する第２レベルのフィルタリングされたビットマ
ップ画像が得られる。図１３を参照されたい。第２レベ
ルでフィルタリングされた画像（図１４参照）のＯＮピ
クセル構造を更に縮小する必要がある場合は、図１５に
示すようにステップ１５１−１５６で第２レベルのフィ
ルタリング・プロセスを更に一度又はそれ以上反復して
もよい。

【００６１】図１９に示すように、密度がより高い記号
（すなわち５×５ペルのように小さい記号セルを用いた
３６００記号／平方インチに及ぶ密度）記号中心ピクセ
ルを位置指定するには、ステップ１６１及び１６２で大
型の水平及び垂直のヒットのみのフィルタにそれぞれ従
って記号コードのビットマップ画像が適宜に「開」され
、これらのプロセスの結果は次にステップ１６３でビッ
ト論理積演算されて、よりよく分離されたマークからな
るビットマップ画像が構成される。

【００６２】画像「開」操作１６１，１６２のビット論
理積演算１６３は生成されるビットマップ画像内の記号
中心位置に意図しないホールを生ずることがあるが、こ
れらのホールは埋めることができる。その目的のため、
変換プロセス６３（図５）のこのような特定のバージョ
ンには更に充填及び修復プロセスの一度又はそれ以上の
反復を含めることができる。図２０に示すこの充填及び
修復プロセスを実行するためには、フィルタリングされ
たビットマップは先ず大型の水平及び垂直のヒットのみ
用フィルタにそれぞれ従ってステップ１７１及び１７２
で膨張され、かつ、次にビットマップ画像が伸張するこ
とを防止するためステップ１７３でビット論理積演算さ
れる。一方、この画像は大型のヒットのみ用のフィルタ
又は大型のヒット−ミス・フィルタのいずれかに従って
ステップ１７４と１７５で「開」され、次に「開」操作
１７４と１７５の結果はステップ１７６でビット論理積
演算される。

【００６３】充填及び修復プロセスが完了すると、ビッ
トマップ画像は少なくとも幾つかの記号位置で幾つかの
ＯＮピクセルに近接する。しかし、画像は薄化操作が停
止されるま，で反復的な薄化プロセスを実施することに
よって記号当たり約１ピクセル分だけ薄化することがで
きる。図２２に示すように、この薄化プロセスはステッ
プ１９０で薄化されるべきビットマップ画像のコピーに
よって、又、４つのヒット−ミスＳＥ，１９１−１９４
のそれぞれ第１組によって開始される。これらのヒット
−ミス・フィルタ１９１−１９４はそれぞれ０°，９０
°，１８０°及び２７０°の角度での２つのＯＮピクセ
ルと１つのＯＦＦピクセルの空間的シーケンスを指定す
る。薄化プロセスの最小の反復中、先ずビットマップが
第１のＳＥ１９１に従ってステップ１９６でＸ論理和さ
れ、次に侵食されたビットマップが薄化さている画像１
９０とステップ１９６でＸ論理和され、それによって単
一のＯＮビクセルがＳＥ１９１の方位に複数のＯＮピク
セルを含む各々の記号位置から薄化、すなわち“トリミ
ング”され、その際、トリミングされるピクセルはＳＥ
１９１の中心位置と位置合わせされたピクセルである。 この最初の薄化に続いて、ＳＥ指標１９７が増分されて
、連続する残りの構造要素１９２−１９４を用いて薄化
された画像での侵食及びＸ論理和ステップ１９５及び１
９６を反復するので、過剰なＯＮピクセルが全ての水平
及び（又は）垂直の隣接するＯＮピクセルの集合からの
所定の並行順でトリミングされる。

【００６４】ステップ１９８で判定される薄化プロセス
の各々の反復後、薄化されたビットマップ画像はステッ
プ１９９でビットマップ画像１９０と比較される。画像
が同一である場合は、薄化プロセスは停止され、そこで
プロセスは完了する。同一ではない場合は、薄化された
画像はステップ１９０でコピーされ、次にプロセスは画
像を更に薄くするために反復される。

【００６５】例えば４ペル×４ペルのように小さい記号
セルに例えば５６２５記号／平方インチまでに及ぶ空間
密度を有する更に高い密度の記号コードも媒体の密度コ
ードの変換のための前述と同じプロセスを利用して記号
の外見上の中心を位置決めするために変換することがで
きる。しかし、これらの密度が更に高いコードを変換す
るには一般に充填及び修復プロセス１７１−１７６を何
度か繰り返す必要がある。（図２０）

【００６６】あるいは、前述したように、変換プロセス
６３（図５）は許容できる記号形状にゆるやかに適合さ
れた小型のヒット−ミス・フィルタを利用して実行する
ことができる。これを達成するには、図２３に示すよう
に、許容できる記号形状のそれぞれ一つにゆるやかに適
合された小さいＳＥに従ってステップ２０１と２０２で
侵食され、次にこれらの侵食の結果がステップ２０３で
ビット論理和され、より小さいマークもしくはピクセル
・パターンからなるフィルタリングされたビットマップ
画像が構成される。例えば、回転変形記号が用いられる
場合は、侵食２０１，２０２の結果のビット論理和２０
３はより小さい、より環状のビットもしくはピクセル・
パターンからなるフィルタリングされたビットマップを
生成する。図１６を参照されたい。このフィルタリング
されたビットマップは一般に各記号の中心の近傍に幾つ
かのピクセルを含んでいる。

【００６７】従って、前述の種類の薄化プロセス（図２
２参照）は通常はフィルタリングされたビットマップを
記号当たり約１つのＯＮピクセルまで薄くするために必
要である。この薄化プロセスに先行して、薄化によって
各記号の最も中心位置のＮＯピクセルをより精確に分離
できるように記号位置におけるピクセル・パターンの境
界ボックスを拡張させることができる。このような境界
ボックスの拡張によって作成されたビットマップ画像の
例は図１７を参照されたい。

【００６８】フィルタリングされたビットマップ（図１
６）又は境界が拡張されたその対向部分の薄化は全ての
記号中心が単一の、分離されたＯＮピクセルによって確
実に規定される前に停止してもよい。空間密度が高いコ
ードの場合は、それによって飛び越し、探索及びラベル
付けプロセス７１−７３（図５）中に著しいラベル付け
の誤りが生ずる可能性があるが、通常はオプションの較
正プロセスによって復号プロセスの記号評価ステップが
図７のステップ１０７において、記号毎に追跡可能であ
るようにに充分精確に記号中心ラベルを再較正すること
ができる。

【００６９】３．畳み込みフィルタリングによる復号図
２４を参照すると、ステップ２１１でコードのビットマ
ップ画像から記号形状コードの記号を復号する畳み込み
フィルタリング・プロセスが示されている。図示のとお
り、このプロセスは外見上の中心ピクセルをＸ−Ｙ画像
に位置決めするために記号を収縮しなくても実行するこ
とができる。そうする代わりに、ビットマップ画像２１
１はステップ２１２でｎの異なるフィルタで別個に畳み
込みされ、そのフィルタの各々はｎの許容される記号形
状の対応する一つと強く適合される。このような畳み込
みによって作成された画像は、今度はビットマップ画像
空間内のＸ−Ｙ座標位置を特定し、一方、ほぼ同時にス
テップ２２１−２２４で復号のために形状で記号を分類
するためにステップ２１３−２１８で記号毎に処理され
、あるいは、ビットマップ画像はデータ・セル毎にｎの
整合されたフィルタの集合で畳み込みされる。更に、拡
張された畳み込み画像を供給して、異なる記号どうしを
補足的に判別するために各々の許容される記号形状毎に
多重の畳み込みを行うことができることが理解されよう
。

【００７０】図２５Ａ及び２５Ｂに示すように、畳み込
みフィルタリングはステップ２２８及び２２９のそれぞ
れで重みなし、又は重み付け処理されることができる。 重みなしフィルタは二値の正又は負の値から成り、一方
、重み付きフィルタは正及び負の双方又は一方のグレー
・スケール値からなっている。フィルタ２２９のような
重み付フィルタが使用される場合は、これらのフィルタ
は整合された記号形状のより明確な特徴を強調するため
に、又、別の記号形状のより明確な特徴を弱めるために
重み付けされることが有利である。

【００７１】より詳細に述べると、図２４に示すプロセ
スに従って記号コードを復号するために、ステップ２３
１で周知の互いの公称の間隔関係の３つ、又はそれ以上
の非共線基準点が記号コード・ビットマップ画像空間に
位置決めされて、ステップ２３２でビットマップ・歪み
及びＸ及びＹ座標の縮尺補正要素が計算される。Ｘ及び
Ｙ座標の縮尺補正要素はステップ２３３で、ビットマッ
プ画像空間のＸ軸及びＹ軸のそれぞれに沿った記号の中
心から中心までの平均変位を較正するために利用される
。これらの較正が行われる変位値は記号が印刷された（
プリンタ・ペルにおける）空間密度の以前の知識又は、
急速フーリェ変換又は急速ワルシュ変換のような周波数
変換によって確定された記号コードのビットマップ画像
の周期性のいずれかによって計算することができる。一
方、ステップ２１３では、歪み補正要素が利用されて、
Ｘ及びＹ変位ベクトルの角度が設定され、それによって
画像処理がビットマップ画像空間の一つの記号位置から
次の記号の予測位置へと充分な精度で飛び越しして、次
の記号の中心を比較的小さい局部領域を探索することに
よって位置決めできるようにされる。この局域的探索は
拡張菱形状又は拡張方形リング状の探索パターンに従っ
て適切に実行される。簡略に述べると、この復号プロセ
スと前述の復号プロセスの予備ステップはほぼ同一であ
ることが明らかであろう。しかし、このプロセスの場合
は二値符号化プロセスよりも記号コード・ビットマップ
画像の予備処理が大幅に少なくて済むことも明らかであ
る。

【００７２】記号コードはステップ２１３で始まって、
例えばＵＬコーナー記号（その中心を位置決めする適切
なプロセスについては既に説明した。）のほぼ中心で記
号毎に復号される。復号を実行するため、ビットマップ
画像はステップ２１２でｎの記号突き合わせフィルタに
よって畳み込みされる。それによってｎのグレー・スケ
ールが作成され、その各々はｎの許容される記号形状の
それぞれの一つに比較的強く適合されたフィルタに対す
る記号コード画像の畳み込みされた応答を表している。 局域的探索はステップ２１４でこれらの畳み込み画像の
各々で、符号化されている記号のおおよその、すなわち
見積りの位置から行われ、ステップ２１５で、その特定
の記号用に各々の画像が含む最大畳み込み値にＸ−Ｙ画
像空間座標がラベル付けされる。図２４に示すように、
これらの局域的最大畳み込み値はステップ２１４で畳み
込みされた画像から読み出され、かつステップ２１５で
それらのＸ−Ｙビットマップ画像空間座標によって指標
付けされるが、局域の最大値は別の実施例では、これら
の局域の最大値を囲む小さい領域から畳み込み値の合計
を指標付けするために利用できることが理解されよう。

【００７３】ｎの畳み込み画像についての指標付けされ
た畳み込み値（すなわち局域の最大値又は合計値）はス
テップ２１６でランク付けされた順に分類され、次にス
テップ２１７で２つの最高値が比較される。ステップ２
２１で双方の値が等しくないと判定された場合は、処理
されている記号のデータ値は畳み込みと照合して復号さ
れて、より大きい値が生成され、その畳み込み値用のＸ
−Ｙラベルが復号されたデータ値に割当てられ、そのデ
ータがビットマップ画像空間内で指標付けされる。ステ
ップ２２２を参照されたい。一方、ステップ２２１で２
つの最大値が等しいものと判定された場合は、それらの
うちの選択された一つのＸ−Ｙラベルが誤り位置を特定
するために記録され、ステップ２２３で誤りカウントが
増分される。その後、ステップ２２４に示すように、畳
み込みと照合することにより見積りされた復号データ値
が付与されて選択された畳み込み値が生成され、選択さ
れた畳み込み値用のＸ−Ｙラベルすなわち指標が復号デ
ータ値をビットマップ画像空間に指標付けするために復
号データ値に割当てられる。

【００７４】ステップ２１８で復号されるべき別の記号
があることが判定されると、前述のプロセスは次の記号
を復号するために反復される。復号されるべき別の記号
がある場合には、復号プロセスは前述の飛び越し及び探
索ルーチンを利用して次の記号へと前進するために、以
前復号された隣接する記号のビットマップ画像空間のＸ
−Ｙ座標（すなわち指標位置）を利用する。

【００７５】図２６を参照すると、この復号プロセスの
ノイズ耐性を高めるため、復号されている記号の局域の
最大畳み込み値の各々はステップ２３１で小さい周囲領
域からの次の隣接する畳み込み値と合計される。例えば
、畳み込み値は各々の畳み込み画像で分析されている記
号の局域の最大値を中心とする小さい菱形又は方形の領
域から画像毎に累積されることができる。ステップ２３
３で判定されるこれらの局域の最大値のＸ−Ｙ座標は次
にステップ２３４でそれぞれの画像から累積された畳み
込み値の合計をラベル付けするために用いられ、次に合
計はステップ２３５でランク付けされた順に分類される
。この時点からは、復号プロセスはこの形式の復号の前
述のバージョンと同様である。

【００７６】結論前述のとおり、本発明はセルフクロッ
キング記号コードのビットマップ画像空か表現を復号し
、かつ、このようなコードの復号中に遭遇する曖昧性（
しばしば“誤差”と呼ばれる）の数と位置を追跡するた
めの二値画像処理技術を提供するものである。更に、画
像処理の本質的な部分は形態的なフィルタリング操作を
利用して行われ、このような操作がもたらす並行処理の
利点を活用していることが明らかである。更に、本発明
に従って実行される誤り検出は実行される復号の信頼性
を高めるために、本明細書に引用されているスターンら
の畳み込みフィルタリング・プロセスのような一つ又は
それ以上の別の復号プロセスにより誤りの統計と関連さ
せ、かつ比較できることが分かる。

【図面の簡単な説明】

【図１】　　本発明の種々の側面を実行し、かつその利
点を活用するための電子文書処理システムの簡略構成図
である。

【図２】　　図１に示した文書処理システム用の代表的
なプロセッサ／インタフェースの機能構成図である。

【図３】　　Ａは回転変形の記号形状から成る比較的簡
単なセルフクロッキング二値記号コードにより達成され
るビット符号化を図示したコード図、Ｂは回転変形の記
号形状における二値データのビット符号化を示した別の
コード図、Ｃは図３Ａに示した形式の回転変形の記号形
状用の代表的なセル構造及び代表的な印刷されたピクセ
ル・パターンの図である。

【図４】　　第１の記号コード復号プロセスの高レベル
の機能流れ図である。

【図５】　　図４に示した復号プロセスの実現の記号中
心の位置決め、ラベル付け及び分類ステップのより詳細
な流れ図である。

【図６】　　図５に示したオプションの較正プロセスに
よる再較正のための予測されるラベル付けされた記号中
心位置のビットマップ画像である。

【図７】　　図４に示した復号プロセスの前述の実施例
の記号読出し／誤り検出ステップの比較的詳細な流れ図
である。

【図８】　　比較的低密度と、比較的高密度の記号コー
ドのそれぞれを復号するために利用されるピクセル探索
領域を示す図面である。

【図９】　　比較的低密度と、比較的高密度の記号コー
ドのそれぞれを復号するために利用されるピクセル探索
領域を示す図面である。

【図１０】　　記号形状の符号化と復号が誤り修正コー
ド（ＥＣＣ）を含むデータのために利用されるシステム
の高レベルの機能構成図である。

【図１１】　　記号コード画像の周期性に従って構成さ
れた大型のフィルタを利用して記号の中心又はその近傍
のＯＮピクセルを分離するために記号コードのスキャン
・インされたビットマップ画像をフィルタリングするた
めの形態的フィルタリング・プロセスの機能構成図であ
る。

【図１２】　　代表的な記号コードのビットマップ画像
である。

【図１３】　　図１２に示したビットマップ画像に図１
１に示したフィルタリング・プロセスを適用した場合の
効果を示すビットマップ画像である。

【図１４】　　図１３に示したビットマップ画像に図１
１のフィルタリング・プロセスの第２レベルのフィルタ
リングを反復的に再適用した効果を示す別のビットマッ
プ画像である。

【図１５】　　反復された第２レベルのフィルタリング
・プロセスの機能構成図である。

【図１６】　　記号中心を空間的に分離するための別の
形態的フィルタリング・プロセスによりフィルタリング
された記号コードのビットマップ画像である。

【図１７】　　図１６に示したビットマップ画像内のピ
クセル・パターンの境界ボックス拡張を示す図面である
。

【図１８】　　空間的に比較的低密度の記号コードの場
合、図１６に示したビットマップ画像内の個々の記号関
連ピクセル・パターンの重心を特定することによって、
又は、前記パターンもしくは図１７に示した境界ボック
スの拡張において行われる薄化プロセスによって達成可
能である記号中心ピクセルの分離を示すビットマップ画
像である。

【図１９】　　より高密度の記号コードの記号の空間的
分離を促進するために大型のフィルタを使用した予備的
な形態的フィルタリング・プロセスの機能構成図である
。

【図２０】　　図１９のフィルタリング・プロセスが記
号中心位置にホールを発生した場合にＯＮビクセルを記
号の中心位置に復元するために利用できる形態的ビット
マップ画像修復プロセスの機能構成図である。

【図２１】　　図１７に示したビットマップ又は図２０
に示した画像修復プロセスで薄化プロセスを実行するこ
とによって作成できるような比較的高密度の記号コード
の記号中心のビットマップ画像である。

【図２２】　　図２１に示したビットマップ画像を作成
するために利用できる反復的な形態的薄化プロセスの機
能構成図である。

【図２３】　　小さい、ゆるやかに突き合わせされたヒ
ット−ミス・フィルタを利用した記号中心ピクセルを分
離するための形態的プロセスの機能構成図である。

【図２４】　　ビットマップ画像空間に記号の中心を位
置決めし、かつ、その形状に従って記号を分類するため
にビットマップ・コード画像の畳み込みフィルタリング
を利用した復号プロセスの機能流れ図である。

【図２５】　　Ａ，Ｂは各々がフィルタによって強く突
き合わせされた記号形状を有する、畳み込みされた重み
なし、及び重み付のフィルタリングの結果を示す図であ
る。

【図２６】　　図２４に示した復号プロセスの変形され
た実施例の部分流れ図である。

【符号の説明】

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　セルフクロッキング記号形状コードに
   よって復号される個々の全てのデータがそれぞれの記号
   によって表現されるように、ディジタル・データ値を符
   号化する型を有する記号から成る前記コードのビットマ
   ップ画像空間表現を復号する処理方法であって、前記記
   号はｎ個の許容される記号の集合から選択され、前記記
   号は各々所定のディジタル・データ値の符号化用に予め
   割当てられ、前記記号は空間フォーマット化ルールにほ
   ぼ従って前記ビットマップ画像空間に空間的に配分され
   る形式の処理方法であって、この処理方法は次のステッ
   プを含む：互いに所定の公称の間隔を有する少なくとも
   ３つの非共線基準点を前記ビットマップ画像空間に配置
   する；前記ビットマップ画像空間内の前記基準点の間隔
   関係を決定する；前記ビットマップ画像空間内の前記基
   準点の間隔関係から歪み補正要素を計算する；前記記号
   コードの前記ビットマップ画像空間用のＸ縮尺補正要素
   とＹ縮尺補正要素を決定し、前記歪み及び縮尺補正要素
   に従って前記空間フォーマット化ルールを較正する；前
   記ビットマップ画像空間内の第１の前記記号のおおよそ
   の中心位置を特定する；前記ｎ個の許容画像の各々につ
   いて少なくとも一つの型突き合わせ判別フィルタに従っ
   て前記記号コードの前記ビットマップ画像空間表現をフ
   ィルタリングして、少なくともｎ個のフィルタリングさ
   れた前記記号コードの表現を供給する；前記較正された
   空間フォーマット化ルールにほぼ従って前記記号コード
   の前記フィルタリングされた表現の全てを空間的に標本
   抽出して、前記フィルタの各々によってフィルタリング
   された前記記号コードの各々について相対的フィルタ突
   き合わせ強度値を得る；ここで、前記標本抽出は前記較
   正された空間フォーマット化ルールにほぼ従って前記記
   号の所定の一つのほぼ中心位置から開始され，そこから
   記号のほぼ中心位置から記号のほぼ中心位置へと継続さ
   れるものである；前記フィルタの全てに関して前記記号
   各々のフィルタ突き合わせ強度値を記号ごとに比較して
   前記記号の形状を分類する；そして前記記号に予め割当
   てられたデータ値に従って前記形状分類された記号に復
   号されたデータを割当てる。