JPS59854B2 - ゾウシユウエンエンコ−デイングソウチ - Google Patents

Description

【発明の詳細な説明】 本発明は周縁の追跡走査を下にしてオブジェクトの内境
界及び外境界をエンコードすることによる像データ圧縮
に関する。

約２２×２８糎の大きさの１ページでさえも、黒白像を
表わす極めて数の多いプール・コード化された点から成
る２次元アレイは多くの用途において圧縮を必要とする
ほどに大きいものであるということはこの分野ではよく
知られている。

このような像の有する冗長性を減少させる諸技法の内の
典型的な技法は２段階処理を利用する。先ず、像は先行
するペル（絵素）及び走査線についての情報を下にして
各々の絵素の黒白状態を予測しうる予測装置（プリホワ
イトナー）を通過される。予測装置は予測した状態が正
しいか間違つているかに従つてエンコーダヘｏ若しくは
１を転送する。第２の処理で、結果の不正像はラン・レ
ングス・エンコーデイング（ｒｕｎｌｅｎｇｔｈｅｎｃ
ｏｄｉｎｇ）によつて圧縮される。このような予測した
後ラン・レングス・エンコーデイングを施す技法の例は
例えば米国特許第３８１３４８５号に見出される。一般
に、予測した後ラン・レングス・エンコーデイングを施
す技法は２つの欠点を有する。第１に、各々の走査線が
先行する走査線の情報と関係なしに別個に処理されると
いう点において１次元的である。第２に、像操作処理が
圧縮された像データに関して都合よく処理され得ない。
このことは部分的には、予測した後ラン・レングス・エ
ン、コーディングを施す技法が元の像では見出されるで
あろうコード化点間の或る関連データを圧縮された像の
中では不明瞭にするという事実から来る。又、エンコー
デイングがオブジエクトに関してエンコーデイングを施
すのではなく走査線に関して施される。この関連データ
は圧縮されたデータを元に戻せば回復されうる。しかし
ながら、データが圧縮された形式で存在していても関連
データがないことは圧縮されたデータに遂行されるどの
ような処理も非常に長たらしいものであり、要するにそ
の像をたマ拡大することに等価であるということを意味
する。像の圧縮をなしうる他の方法としてオブジエクト
の境界のエンコーデイングは１次元技法の欠点も関連デ
ータの喪失も除きうる。本明細書においては、像は複数
のコード化点が２次元に配列されたもの（２次元アレイ
）として考慮される。コード化点の各々は黒又は白の絵
素を表わすブール値で表わされる。複数の黒絵素から成
る拡がり領域はその周りに単一の外境界を有していれば
１連結されたオブジェクトと定義される。上記で示唆し
たように、白い背景を持つた黒いオブジエクトの外側輪
部の境界をエンコーデイングする概念は新しいものでは
ない。

この結果を達成する方法ばＰｉｃｔｕｒｅＰｒＯｃｅｓ
ｓｉｎｇｂｙＣＯｍｐｕｔｅｒ′５〔Ａｃａｄｅｍｉｃ
Ｐｒｅｓｓ，ＮｅｗＹＯｒｋ！ＬｉｂｒａｒｙＯｆＣＯ
ｎｇｒｅｓｓ屋７８−８４２５５〕の第１３４乃至第１
３８頁に見出されうる。諸オブジエクトの境界輪部のリ
スクを位置付け組織化する幾つかの方法乃至アルゴリズ
ムは文献の中に見出されうる。しかしながら、これらの
方法乃至アルゴリズムの大部分はクレー・スケール（Ｇ
ｒｅｙｓｃａｌｅ）の情報を処理するようにみえる。文
献の中に見出される幾つかの白黒アルゴリズムは少なく
とも部分的にはラスタを下にしており、従つて走査し終
るのにはコード化点配列上を何回も走査する必要がある
。又、これらの白黒アルゴリズムは像の処理のためには
処理途中の像平面を構成する１時貯蔵リスト若しくは１
時貯蔵タツグを頻繁に参照する必要がある。このような
従来の典型的な方法乃至アルゴリズムは処理されつ＼あ
る絵素毎に幾つかの貯蔵ビツトを必要とする。この必要
性は既につながつている諸絵素を同定し、境界絵素を内
部絵素から区別するための要請から来る。本発明の１つ
の目的はオブジエクトの外側輪部及び内側輪部の境界を
エンコードすることを下にして像データを圧縮する方法
及び装置を提供するにある。内側輪部及び外側輪部に関
するデータが保存されているという点においてこのよう
な圧縮されたデータに対し像の操作を行い易くするとい
うことも関連した目的である。これらの目的は各々黒ペ
ル又は白ペルを表わすブール値で表わされる複数のコー
ド化点で構成された２次元配列（２次元アレイ）の中で
オブジエクトの境界をエンコードする方法及び装置によ
つて達成される。

本発明において、複数の黒ペルから成る拡がり領域がそ
の周りに閉じた単一の外側周縁によつて特徴付けられる
とき“連接されたオブジエクト”が存在すると呼ばれ、
この拡がり領域内に複数の内側輪部が存在することもあ
り、夫夫の内側輪部は複数の白ペルからなる拡がり領域
（ホール（ＨＯｌｅ）と呼ばれる）の周縁を定める。本
発明の方法は最初の黒ペルが見出されるまで像配列をラ
スタ走査することを目論んでいる。最初の黒ペルが現わ
れると、その像配列座標の位置が記録される。この位置
からオブジエクトの外側周縁が周縁追跡装置によつてエ
ンコードされていく。この周縁追跡装置は”カーソル”
をオブジエクトの周りを時計式方向に移動させる。周縁
追跡装置はたどつていく各々の黒ペルを鎖式連結コーデ
イング方式（ＣｈａｉｎｌｌｎｋｃＯｄｅｄｆＯｒｍ）
で一連の不連続な異なつた方位角として記録する。この
ような記録はオブジエクトの周りを一周するまで続けら
れる。オブジエクトを検索し位置決めし、その外側境界
をエンコードした後、オブジエクトの内側境界を位置決
めし、該オブジエクトを像配列から除くことが本発明で
は必要である。

これはラスタ走査処理で同一オブジエクトに再度遭遇さ
せないことにある。これらのステツプはオブジエクトを
１ペルの幅に相当する外側輪部帯を処理し、オブジエク
トが縮小されるように遭遇される各々の黒ペルのブール
値を補数化することによつて達成される。オブジエクト
はオブジエクトを単一の符号化点に減少させるのに必要
な回数だけ周回される。本発明の方法は更に各々のペル
が任意の輪部帯に沿つて遭遇されるとき、そのペルがオ
ブジエクトを破砕しないならば該ペルは補数化されると
いうことを目論んでいる。破砕ということは第２表及び
第３表に示されるようにオブジエクトを２つに分けるこ
とを意味する。内側輪部上の或るコ一ド化点が周縁とし
てたどられる諸コード化点から成る軌跡の進行方向（時
計式方向）の右側に隣接する白ペルとして最初に検出さ
れるならば、本発明の方法は中断されることになるが、
縮小されたオブジエクトの内側境界と縮小されつ＼ある
周縁に関してくぼみとなる部分（薄い部分）とを区別す
るために処理が続けられる。内側境界即ちホールが遭遇
されたということが判定されたならば、内側境界はその
親オブジエクトと同じ方式で記録される。

更に、内側境界内のペルの値は１時に１つの輪部帯だけ
補数化される。この処理はホールが黒のオブジエクトで
ある〔その処理が連続的である即ちホールの中に更にホ
ールが続く如き他のオブジエクトがある〕が如き方式で
元のオブジエクトか単一のコード化点になるまで続けら
れる。本発明の方法は幾つかの制限を受ける。

第１に、ホールについては周縁が対角線上をたどられな
いということ即ちＸ，ｙ方向における直線的な動きだけ
が許される。第２に、周縁と像境界とは交差しないとい
うことである。従つて、周縁追跡装置が像境界上にある
とき、境界の他方の側に隣接する諸ペルをマスクするこ
とによつて境界と交差しないようにカーソルを拘束する
必要がある。本発明は圧縮されたコード列の中に内側境
界と外側境界との間の相対的位置関係を有意義に保つて
いる。本発明は外側輪部と同じシーケンシヤルな方式で
内側輪部を検索し追跡し得、従つて像は圧縮されていな
い形式とは区別される圧縮された形式で処理され、この
場合内側境界と外側境界との相対的位置関係は保たれて
おり且つオブジエクトは走査線方式とは異なつて閉周縁
間の相対的位置関係を保つて処理される。伸張処理（Ｄ
ｅｃＯｍｐｒｅｓｓｉＯｎｐｒＯｃｅｓｓ）は上述の圧
縮されたコード化信号列に応答して元の像を再構成する
。

それには４つの基本ステツプがある。これらのステツプ
は境界をデコードすること、境界をたどること、ホール
に関しテストすること及びホールを縮めることである。
本質的には、各各のオブジエクト（ホール）の境界が初
期的に黒い像のメモリへ書込まれ、（境界内の）内部が
満される。良好な実施例の説明 思い出されるように、像は複数のブール・コード化点（
各々のコード化点は黒又は白のペルを表わす。

）から成る２次元の配列（アレイ）として定義される。
複数の黒ペルから成る拡がり領域（連接領域）の各々は
夫々オブジエクトとして認識され、１つのオブジエクト
は閉じた単一の外側輪部によつて特徴付けられそして夫
々ホールとして認識される複数の白ペルから成る各拡が
り領域を囲む諸内側輪部を選択的に有する。この実施例
のために、オブジエクトは更に連接した８つの黒ペルの
セツトとして定義され、他方ホールは連接した４つの白
ペル（これらの白ペルはいづれも像の周縁とはならない
）のセツトとして定義されることもある。こ＼で、オブ
ジエクト及びホールは各”縁部”によつて囲まれている
。縁部は反対の輝度を有する、複数の隣接する４ペル対
から成つている０最後に、オブジエクトの周縁は縁部の
黒ペルから成り、他方ホールの周縁は縁部の白ペル並び
に黒コード化点及び白コード化点から成る隣接する８対
の内の白ペルから構成される。従つて、黒のオブジエク
トの境界は連接した８つの黒ペルのセツトから成つてお
り、白いホールの境界は連接した４つの白ペルのセツト
から成つている。差し当つて、周縁追跡に関する付加的
な１つの概念を考えることにする。周縁追跡手段はオブ
ジエクトの周縁コード化点から隣接する周縁コード化点
へ時計式方向にカーソルを動かすメカニズムと考えられ
る。座標は左から右まで１個の単位を有し上から下まで
Ｊ個の単位を有する。それ故、周縁追跡手段は輝度の同
じ値を有する隣接するコード化点へ移動しなければなら
ないという制限のため前の移動方向から出来るだけすば
やく左へまわる。カーソルが黒のオブジエクトの周縁を
たどる場合には、カーソルは最左端の黒ペルの方向をと
る。右回りが最後の滞留のために許される。本発明の良
好な実施例は絵素当り僅かに１貯蔵ビツトを必要とする
という点で制限される。本発明の実施例はその方法がこ
とごとくシーケンシヤル処理であり、そして限定された
スタツク・メモリへ１時的に書込まれる数少ないＩ及び
Ｊ座標を除いて過去のエンコードされた信号を貯えるど
のような能力も必要でないという点において制限される
。本実施例においては、スタツク・メモリはモードの変
更が最新に生じたコード化点の信号を貯えるための限定
されたメモリである。最後に、実施例は非常に簡単な機
能ブ田ンクから成るように制限されている。本発明の最
も初歩的な構成は像を貯える直交型アンダム・アクセス
・メモリ、輪部追跡手段、及びスタツクから成る。像部
分の鎖式連結コーデングは例えば、ローテーシヨン（Ｒ
ＯｔａｔｉＯｎ）、拡大スムージング（Ｓｍ−０ｔｈｉ
ｎｇ）、マツチング（Ｍａｔｃｈｉｎｇ）及びエデイチ
イング（Ｅｄｉｔｉｎｇ）のような操作処理を容易にす
るということはＡｕｔＯｍａｔｉｃＩｎｔｅｒｐｒｅｔ
ａｔｉＯｎＣｌａｓｓｉｆｉｃａｔｉＯｎＯｆＩｍａｇ
ｅｓＣＡ．Ｇｒａｓｓｅｌｌｉ，ＥｄＩｔＯｒ９Ａｃａ
ｄｅｍｉｃＰｒｅｓｓ，ＮｅｗＹＯｒｋ，ｌ９６９ＦＬ
．Ｃ．７６−８４２２５〕の第１５５頁乃至第１７４頁
に掲載されている６ＡＲｅｖｉｅｗ０ｆＲｅ１ｅｖａｎ
ｔＰｒ０ｂ１ｅｍｓｉｎｔｈｅＰｒ０ｃｅｓｓｉｎｇ０
ｆＬｉｎｅＤｒａｗｉｎｇＤａｔａ゛なる論文でよく知
られている。

本発明では、像データが上記の操作を受入れうるオブジ
エクト及びホールの境界のリストを形成するように変換
される。これに加えて、ホールの境界が親オブジエクト
の境界に属するものとして同定され、又ホール内にある
オブジエクトも又同様に同定される如き非常に重要な属
性がオブジエクト及びホールに関する鎖式連結コーデイ
ングの各閉周縁間の関連付けにある。本発明の方法は任
意の黒白像から成るオブジエクト及びホールの境界を鎖
式連結コーデイング形式でエンコードすることにある。

本発明の方法は４つのステツプ即ち（１）オブジエクト
を検索すること、（２）その境界を記録すること、（３
）オブジエクトを縮めること、及び（４）ホールに関し
てテストすることから成る。複数のコード化点から成る
２次元のコード化点配列の中のオブジエクトの検索は行
順次式（ラスタ走査方式）で（左から右へ、そして上か
ら下へ）なされる。

黒絵素が遭遇されるとき、オブジエクトが見出されたこ
とになる。見出された各々のオブジエタトの境界は周縁
がたどられるにつれて鎖式連結コーデイング形式でエン
コードされる。見出されたオブジエクトがダブル・オブ
ジエクト（後述）であるということがあるが、このよう
な場合にはエンコーデイングに先立つて周縁追跡手段が
オブジエタトの周りに沿つてカーソルを移動させること
が必要になる。エンコードされたデータは出発コード化
点（１，ｊ位置）並びに或る境界コード化点から次の境
界コード化点までの一連の不連続な移動方向から成る。
出発コード化点に戻つたときその境界についてのエンコ
ーデイング・プロセスは終了する。隔離されたコード化
点が存在するような場合には、特殊コードを付加する必
要があるが、これは該コードがなければデコーダは元の
コード化点に戻つたかどうかを検出し得ないからである
。オブジエクトの境界がエンコードされた後、遭遇した
各々の検出可能な絵素（ペル）を補数化するように周縁
追跡手段の動作を続けることによつてオブジエクトは縮
小される。

この処理において、周縁追跡手段は縮小せんとするオブ
ジエクトの周縁の周りを何回も廻ることがある。場合に
よつては、縮小化プロセス中に、ホールの存在を検出す
ることがある。これは時計式方向の周縁追跡中の移動方
向の右側に白ペルが隣接して現われることによつて表示
される。他方、これは又起りうることだが、縮小されつ
＼あるオブジエクトの薄い部分であることもある。これ
らの可能性のうちのどちらが発生したかを決めるために
、ホールに関するテストの処理が開始される。このテス
トは、周縁追跡手段がその出発コード化点まで戻るまで
、連接された４つの白ペルから成る周縁の内の１つの白
ペルから次の同様の白ペルまで順次に動かすことによつ
て存在するかもしれないホールの周縁をたどることから
成る。移動方向はその移動が左回りか右回りかに従つて
重み付けられる。左回りは正の重み付けを割当てられ、
他方右回りは負の重み付けを割当てられる０このことが
この点にホールが存在しているか否かについての判定を
可能にする。このテストに関しては詳細に後述する。ホ
ールが確かに検出された場合には、周縁追跡手段による
記録処理が行われる即ちホールの境界が鎖式連結コーデ
イング形式でエンコードされる。然る後に、ホールは縮
小される即ち大きさに関して減少される。然る後に、元
のオブジエクトの縮小が続行される。ホールの縮小中に
別個のオブジエクト例えばホール内のオブジエクトが遭
遇されるならば、オブジエクトに関するテストの処理が
開始される。このテストは像部分に関するテストが連接
された８つの黒ペルから成る周縁に関して処理されると
いうことを除いてホールに関するテストと同じである。
プロセス・トリ一の種々の分岐点での帰還アトレスのリ
ストを維持するために後人先出（ＬＩＦＯ）スタツク方
式のスタツク・メモリが必要とされる。

ＮＸｎの像に必要なスタツク・メモリの最大深さはｎ×
２である。これは各々の１ペル幅の同心円的な縮小像の
ために必要になる。実際には、必要とされるスタツク深
さはこれよりもかなり小さい。第１に、像が走査される
とき、量子化ノイズがこのような像の中の何本かの走査
線を切つたり、本にさせる。第２に、経済的な面から１
００万のコード化点から成る像が圧縮されて同一の大き
さの複数のサブアレイ若しくはウインドウへ変えられる
。代表的なウインドウの大きさは１２８×１２８のペル
から成る。元のオブジエクトの大きさが零まで減少され
てしまつた（スタツクが空になることを意味する）後に
、次のオブジエクトの検索が黒ペルを最初に検出するコ
ード化点までラスタ走査方式で開始される。

このラスタ検索処理がすべての像コード化点を走査し終
えたとき像アレイが完全にエンコードされたものと考え
られる。次に、第１３図を参照すれば、２つのホールを
含むオブジエクトを本発明に従つて圧縮符号化する図式
ステツプが示されている。

第１３図のａには、複数の１及びＯから成るアレイがホ
ールを有する代表的なオブジエクトを表わすようにして
配置されている。左から右へ、そして左へ戻つての、順
次に上から下へ進むラスタ走査処理は該処理がオブジエ
クトの頂点に出会うまで一連のＯを発生し続ける。２進
の１によつて表わされる最初の黒ペルが出て来ると、そ
のアレイ座標が記録され、それから周縁追跡手段はその
オブジニクトの境界に沿つて進んでいき、その出発コー
ド化点に戻るまで順次に遭遇される周縁黒ペル毎に異な
る一連の方位角を記録する。

このことが本発明の第２ステツプ即ち外側境界の記録処
理に当たる。第１３図のｂ及びｃはオブジエクトの周回
を繰返し各々周回中に外側帯内の削除可能なペルを除去
することによつてオブジエクトを縮小する即ちその大き
さに関して減少させるステツプを例示している。この処
理は、オブジエクトがその大きさに関して零まで減少さ
れるか又はカーソルの移動方向の右側に白ペルが初めて
現われるまで、続けられる。ホールと見込まれた周縁を
先ずたどつていき対応する一連の異なる方位角を順次に
記録することによつてホールに関するテストがなされる
。そのシーケンスが時計式方向において閉じるならば、
内側輪部及び内部の諸コード化点はそれらが黒いオブジ
エクトであつたと同じ方式で処理される。このことは第
１３図のＤ，ｅ及びｆに示されている。次に、第１０及
び第１１Ｂ図を参照し、圧縮された鎖式連結データの伸
張即ちデコーデイングを考える際に、像を再構成するの
に圧縮の場合と同じ機能的プロツク即ち２次元像メモリ
、周縁追跡手段及びスタツクを使うということに注意さ
れたい。伸張方法は境界をデコードし、周縁をたどり、
ホールに関するテストを行い、、そしてホールを縮小す
る各ステツプから成る。第１０図に示されるように、境
界デコード・ステツプはコード化されたデータを受取り
鎖式連結データによつて指定される輪部に沿つての像コ
ード化点を黒くする。このステツプは出発コード化点と
の一致を見出すことによつて黙示的に終了される。隔離
コード化点のある場合に１つの例外がある。この場合に
は、第１表に示されるようにステツプの終了に特殊コー
ドが用いられる。このステツプは又オブジエクトの中に
ホールを作り出すのに使用され、その場合には各々のコ
ード化点を白にする。周縁追跡ステツプは境界デコード
ステツプによつて発生された境界をたどり、存在するか
も知れないホールを探す。

この処理中に、ホールが移動方向の右側にある反対輝度
の諸コード化点として検出される。又、像の伸張中に使
われるホールという言葉は正しいがあいまいになること
がある。ホールは、そのあいまいさを避けるためオブジ
エクトの外側周縁の内側にある複数の白ペルから成るグ
ループとして参照する場合がある。各出発境界点の座標
に戻つて来たとき周縁追跡ステツプは終了される。

このステツプでホールが見出されたならばホールに関す
るテスト処理が開始される。このテスト処理がホールの
存在を表示するとき、ホールはホール縮小処理でホール
内の各コード化点を白くされる。オブジエクトの周縁を
構成する諸ペルのセツトは８つのペルを単位（境界）と
して連接されている。

この周縁セツトの中に連接された４つのペルから成る幾
つかのホールを含むことがある。これらの各々は元のオ
ブジエクトを再構成するために各コード化点を白くされ
ねばならない。この処理をするメカニズムは各々のホー
ルの中には４つのペルを単位として連接され境界ペルを
構成しなければならないペルが存在するという観察を下
にしている。同じ議論が内側の黒いコード化点を囲むと
ころの４つのペルを単位として連接された白い周縁にも
適用される。内側の諸黒いコード化点から成るこれらの
グールプは８つのペルを単位として連接されているもの
と考えられねばならない。圧縮方法及び論理的にその反
対処理である伸張方法の夫々のステツプは第１０図にモ
ード切換ダイヤグラムに示されている。概念的に云えば
、本発明の方法を実施する装置は像アレイを貯えるメモ
リ、輪部（周縁）追跡手段、及び各閉周縁間の相対的な
位置付けが完了したこと（各々の周縁を追跡し処理し終
つて戻つて来たこと）を検出するためのＩ，ｊ座標を保
持するためのスタツク・メモリを含むと云いうる。輪部
のコーデイングは像をメモリに入れ、像アレイをラスタ
方式で検索することによつて始まる。黒ペルが見出され
たとき、そのデカルト座標１，Ｊが貯えられる。然る後
に、周縁追跡手段は外側境界を一連の不連続で異なつた
方位角として記録する。カーソルの移動方向において白
ペルが検出されるまでオブジエクトはその大きさにおい
て縮められる。白ペルが検出されると、ホールに関する
テストが開始され、スタツク・メモリは増分される。即
ち、隣接する黒ペルが遭遇された位置がスタツク・メモ
リに貯えられる。ホール・テストが肯定であるならば、
ホールが記録され、そしてオブジエクトがその大きさに
おいて縮められたと同じ方式でホール内の検出可能なペ
ルを夫々補数化して除くことによつてこれらのペルを黒
にする。この処理は、ホールが完全に黒で満されるか又
はそのホールの中に存在しうる処理対象を表わす黒ペル
がカーソルの移動方向の右側に現われるまで、続けられ
る。次に、第１１Ａ図と一緒に第１０図を参照するなら
ば、装置が圧縮コーデイングを遂行しつ＼ありラスタ検
索モードにあつて黒ペルが見出されたということを示す
ならば、境界記録モードへ切換えられ、適切なペル位置
計数器の内容が黒ペル座標に設定される。

一方、第１２Ａ図を参照するならば、圧縮モードにおけ
る記録のためのフロー・チヤートが示されている。従つ
て、第１１Ａ及び第１１Ｂ図とこのための制御フロー・
チヤート第１２Ａ乃至第１２Ｅ図とを合わせてみると、
圧縮処理ステツプ及び伸張処理ステツプの各々のための
適切なデータ転送及びテストが明確になる。こ＼で、第
１図を参照すると、装置の論理及びデータ・フローが示
されている。未圧縮のデータはワイヤ対１（入力）及び
３（出力）を経てラスタ・データ入出力装置５を介して
送受される。同様に、圧縮データはワイヤ対２３（出力
）及び２５（入力）を経てエンコーダーデコーダ２１を
介して送受される。像アレイはワイヤ１、ラスタ入出力
装置５を経て供給されランダム・アクセス・メモリ１１
へ貯えられる一連のラスタコード化点から構成されるの
がよい。ランダム・アクセス・メモリは既に提案されて
いる直交型であつたならば、像アレイは装置がラスタ検
索モードであるかの如くラスタ方式で読出される。輪部
追跡装置１５は又本明細書では周縁追跡装置と類義語で
ある。

装置１５はメモリ１１からの像アレイ・データに応答し
、システム内の他の主要な諸装置例えばエンコーダーデ
コーダ２１、プロセス制御発生装置４５、並びに輪部閉
完了検出器及び１．Ｊコード化点計数器２９と協働する
。輪部追跡装置の論理的な詳細は第２乃至第７Ｃ図に示
されている。ついでに云えば、エンコーダーデコーダ２
１は第８Ａ乃至第８Ｃ図に示されており、．Ｊコード化
点計数器及び輪部閉完了検出器２９は第９Ａ乃至第９Ｂ
′″図に示されている。明らかになるように、鎖式連結
コーデイングによる輪部の圧縮及び伸張は概して複合し
た主題として取扱われている。以下において、構成と機
能とを組合わせて説明する。例えば、アレイ・フイール
ド内の諸オブジエクトを圧縮したいとき、本発明の方法
は黒ペルが見出されるまでラスタ方式で順次に検索する
必要がある。

そして、直交型ランダム・アクセス・メモＩＪｌｌは第
１４図に示されるメモリ・アドレス計数器を必要とする
。該計数器は初期的にＯへセツトされる。メモリ・アド
レス計数器が増分されるとき、像データの諸ワードがシ
ーケンシヤルに取出される。サイクル毎に、ワードがい
かなる黒ビツト構成を有するかどうかを判定するために
ワード全体が並列に調べられる。所定の黒ビツト構成に
ないならば、次のワードがメモリから取出される。所定
の黒ビツト構成にあるならば、取出されたメモリ・ワー
ドの８ビツトが第１４図に示される３ビツト・ペル計数
器の制御の下に左から右へ個別に調べられる。メモリ・
アドレス計数器とラスタ検索ペル計数器の組合わせが黒
ペルの１．Ｊ座標を決定する。この組合わせの出力が．
Ｊコード化点計数器２９のアツプ・ダウン計数器及び第
９Ａ図に示されるＲＳ入力を経て初期１入力及び初期Ｊ
入カへ供給される。各周縁追跡動作毎にカーソルの．Ｊ
座標が複数の１．Ｊ座標計数器に維持されているという
ことを認識されたい。

これらの計数器は３つの手段の内の１つ、即ち、第１に
は黒ペルが初期的に見出されるラスタ検索からの信号、
第２には像が伸張されつ＼ある場合のデコーダ２１から
の信号、そして第３にはスタツク（ＲＡＭ）３７が減分
される場合のスタツクからの信号によつて初期設定され
る。ついでに云えば、各々の境界の１．Ｊ座標はコーデ
イング及びデコーデイングのための圧縮されたデータの
一部である。初期値１及び初期値Ｊは周縁追跡手段が初
期コード化点に戻つたことの検出を可能にするため諸ラ
ツチへ同時に貯えられる。

初期コード化点への戻りは１．Ｊと初期１．Ｊとが等し
いことを第９Ｂ及び第９Ｂ″″図の比較器が示すときに
検出される。周縁追跡動作中、カーソルはその現１．Ｊ
コード化点から隣接するコード化点へシーケンシヤルに
歩進する。この歩進動作はＩ及びＪ又はＩ若しくはＪの
内のいずれかを増計数又は減計数させることによつてな
される。このことは第９Ｂ及び第９Ｂ″″図に示されて
おり、第４図の線２７によつて制御される。第２図に示
される輪部追跡装置１５はオブジエクト若しくはホール
の周縁の周りを時計式方向に或るコード化点から隣接す
るコード化点へカーソルをシーケンシヤルに移動させる
。基本的な考えは次のペル位置が前のカーソル位置と同
じ輝度即ち黒若しくは白でなければならないという制限
の下で出来るだけすばやく左へ廻すことにある。輪部追
跡装置１５は第４図の諸ラツチ４０９に貯えられている
直前の移動方向を受取り、連接するペルに関する８つの
移動方向の諸値を正しい順序で第３図の次期移動方向発
生装置３２９に示される優先順位エンコーダ３５９へ与
える。このことが同一輝度のペルの内のどのペルが最高
優先順位を有するかを決定する。ノ 諸直前移動方向ラツチ４０９は輪部追跡装置１５によつ
て使われるのに加えて４つの源の内の任意のものからの
信号を貯えることが出来る。

例えば、これらのラツチはデコーダ２１（第１２Ｅ図に
おける記録モード若しくは伸長モード）からの信号、再
初期設定のために生ずるスタツクからの信号、又は第２
図並び第７Ａ／７Ｃ図に輪部追跡装置の一部として示さ
れるホール有無検出器３０３からの信号を貯える。次に
、第７Ａ図を参照すると、存在することのあるホールの
ペルが方向及び輝度によつてどのようにして同定される
かということが示されている。

問題としているペルはカーソルの移動方向の右側に存在
する。これらの方向は具体的に云えば、Ｍ＋５、Ｍ＋６
、Ｍ＋７又はその他の８を法とするＭである。例えば、
ＭがＯであるならば、最後の移動は右向きに水平な方向
であつた。従つて、Ｍ＋５、Ｍ＋６、Ｍ＋７は夫々、左
下向きの５、下向きの６、及び右下向きの７である。こ
のことは、カーソルが水平に右（Ｍ＝０）へ動いている
ならば移動方向の右側ということは下向きであるという
ことから、容易に判る。選択回路７０９，７０３及び７
０５は優先順位を下にして（ａ）対角線方向でなく且つ
（ｂ）最も右廻りの方向を選択するのに用いられる。選
択回路７０１は第３図の次期移動方向発生装置３２９に
よつて発生される対応する白ペルに関する値を選択する
のに用いられる。次に、第７Ｂ図を参照すると、存在す
ることのあるホールのペルの存在を検出するのに必要な
組合わせ論理回路３０３を主として図示している。

該回路は向き変更発生装置、方向弁別装置７１３、及び
第７Ｃ図に詳細に示されるホール評価装置７１１を含む
。向き変更発生装置は次の移動方向１０１から前の移動
方向を差引く。

向き変更発生装置は３本の出力線６０２上に３つの出力
を発生し、これらの出力はデコーダへ与えられ、デコー
ダからｔ−＋２（左９０度）、ｔ−０（直進）、ｔ−一
３（右１３５度）、ｔ−一４（１８０度右に廻れ）等の
出力が発生される。３本の線６０２は信号４７（サイン
・ビツト）を発生するように時計式／反時計式累算器に
よつて用いられる。

ホールに関するテスト中に境界が時計式方向又は反時計
式方向に横切られたか否かをこの信号が示す。このこと
は夫々の移動方向を合計しその結果のサイン・ビツトを
見ることによつて達成される。３本の線６０２上の信号
をデコードされて得られた信号，６０１はエンコーダ２
１及び第７Ｂ図の残りから成る組合わせ論理回路で用い
られる。

該論理回路は線６０１上に発生されたカーソル移動方向
の右にある隣接する各ペルの実際の輝度信号を結合する
ことによつて存在することのあるホールのコード化点の
存在を線３０９上に表示する。信号３１０はカーソルが
位置するコード化点が縮小モードにおいて削除可能であ
るか否を示す。この機能は削除のための基準を与える第
１及び第２表に示されている。これらの表において、相
対的な変位方向ｔは−４≦ｔ≦３（但し、−ｔ及び＋ｔ
は夫々、右廻り及び左廻りを表わす。）の範囲内にある
実整数によつて表わされている。第１表においては、変
位方向ｔはカーソルの移動を生じさせるためのエンコー
ダーデコーダ２１（第８図）で用いられる２つのコード
と一緒に示されている。引続いて掲載される削除基準表
において使用される最低位桁ビツトＬＳＢは３×３ペル
・アレイ内の゛４”として示されるペル位置からのカー
ソルの移動が対角線方向又は非対角線方向にあつたか否
かを示すことにある。

第２表はペル位置１６゛のペルが白であるならばホール
に関するテストが開始される如きオブジエクトのための
削除しうる基準である。

第３表は６が黒であるならばオブジエクトに関するテス
トが開始される如きホールのための削除しうる基準であ
る。

上記の諸例においては、コード化点”４”を常にカーソ
ルが来たコード化点として選んである。

コード化点４からの移動が対角線方向か又は非対角線方
向にあつたか否かをＬＳＢが示する云われるのはこの点
に関してである。次に、第７Ｃ図を参照すると、ホール
評価装置７１１のための論理回路が示されている。

ホール評価装置７１１は信号△を発生する回路７１５を
含む。△はカーソルが出発コード化点から出ていく方位
角とカーソルが出発コード化点に戻る方位角との間の相
対的な方位角差を表わしている。例えば、△−４である
ならば、カーソルが出発コード化点から出る隣接するペ
ルとカーソルが出発コード化点へ戻つて来る隣接ペルと
は同じである。出発コード化点（ペル）で隣接するペル
に関する計数値３０５と組合わされる上記情報はダブル
・オブジエクトの検出を可能にし、このことは線４７上
の信号によつて示される。ホールに関するテスト・ステ
ツプの完了は方位角（移動方向）の累算のサインを下に
しての判定を生じさせる。

この判定が無視若しくは延期されるとき幾つかの重要な
例外がある。第１の例外は像の周縁がテスト中に遭遇さ
れるときに生ずる。このことを検出するのが都合よけれ
ば、上記テストは処理の最後までに至らずに停止される
のがよい。というのは、ホール又はホール内のオブジエ
クトは像周縁上にコード化点を含み得ないからである。
他の選択は像に人為的な白の周縁を与えテスト結果に応
答させることにある（周縁追跡手段はこの白周縁上を進
み、それ以上には進まない）。第２の例外は周縁追跡手
段がホールの境界全体を横切ることなしに出発コード化
点に戻ることがある（例えば、出発点が僅かに１ペルの
幅を有するホールの領域内に位置することがある。）と
いう事実によつて惹起される。この場合にも、２つの選
択がある。第１には、他のホールに関するテストが結局
は、削除可能なコード化点で開始されねばならないから
、テストは処理の最後まで至るずに終了されることがあ
る。第２には、出発コード化点が２（若しくは３）回再
遭遇されるまでテストが続けられる。用いうる構成は妥
協案である即ちテストが出発点が２回現われることで完
了されるならばそのテストは続けられるが、もしそうで
ないならばテストは早期に終了される。この選択は境界
記録ステツプの必要性を下にしている。この状態を検出
するために、たとえ結果が予じめ決められていたとして
もオブジエクトに関する検索ステツプが黒絵素を見出す
度毎にオブジエクトに関するテスト・ステツプをとる必
要がある。（このことは混乱を避けるために初めの方で
は述べなかつた。）初期移動方向が１時貯えられ、テス
トの最終移動方向から８を法として差引かれる。例えば
、カーソルが出発コード化点（ペル）から出ていく隣接
するペルとカーソルが出発コード化点へ戻つて来る隣接
するペルとが同一であるならば上記演算結果は４である
。オブジエクトに関する検索ステツプによつて見出され
るコード化点に僅かに２つの可能性即ち△−４で且つＮ
−２である場合及び△−５で且つＮ−３である場合が存
在する。これらの場合の１つが生ずると、コード化され
た鎖式ヘツダの中の特殊な゛ダブル・オブジェクトピッ
トがオンに切換えられる。ダブル・オブジエクト（ホー
ル）の可能性を除去しうるが、すべての鎖式開始点を左
上に持つていくことは不可能である。オブジエクト（ホ
ール）に関するテスト毎に存在することのあるダブル・
オブジエクト（ホール）についての検査がなされる。

これは付加的な２つのテスト即ち△−５で且つＮ−４で
あることのテスト（オブジエクトのみに関するテスト）
、及び△−６で且つＮ−３であることのテスト（ホール
のみに関するテスト）がなされることを必要とする。テ
ストされつ＼あるコード化点セツトが結局ホール（オブ
ジエクト）でなかつたということを、開始コード化点が
２回現われた後の最終結果が示しうるから、ダブル・ホ
ール（オブジエクト）が検出された後にホール（オブジ
エクト）に関するテストを続ける必要があるということ
に注意されたい。（このことは又、境界記録ステツプを
通常の方向に向けて開始させるように、オブジエクトに
関する検索ステツプで見出されたオブジエクトでなされ
る。）ホールに関するテストが多重オブジエクトのため
に早期に終了されるのは出発コード化点が同じ輝度を有
する３つの隣接するコード化点（これらの内のいづれも
互いに隣接していない。

）を有するときである。デコード処理中には、ダブル・
ホール（オブジエクト）がたまたま遭遇されるならば、
ホール（オブジエクト）に関するテストは早期に終了さ
れる。この場合には、２種類のダブル・オブジエクト状
態（その１つはテストされつ＼あるホール（オブジエク
ト）に関連付けられ、他の１つは元のエンコードされた
オブジエクト（ホーノ（ハ）に関連付けられ、追跡ステ
ツプ中に出発コード化点が２回現われる。）を生ずる可
能性がある。

【図面の簡単な説明】

第１図は輪部圧縮一伸長装置の装置論理及びデータ・フ
ローを示す図、第２図は第１図に示される境界追跡装置
のためのデータ・フローを示す図、第３図は直前の移動
方向及びカーソルが現在位置しているペルの周りの８つ
のペルの黒又は白に応答してカーソルの次の移動方向を
決定する第２図の次期移動方向発生装置を示す図、第４
図は直前移動方向を表わす信号を発生する第２図の直前
移動方向レジスタを示す図、第５図はホール若しくはオ
ブジエクトとしての隣接するペルの表示に応答してマス
クされた隣接ペルを表わす信号を発生する第２図のカー
ソルによる隣接ペル選択論理を示す図、第６図は第５図
のカーソルによる隣接ペル選択論理からのマスクされた
隣接ペルの表示に応答して、カーソルが位置している輪
部に沿つてのコード化点と同じ輝度を有する隣接ペル番
号を発生する論理を示す図、第７Ａ１第７Ｂ及び第７Ｃ
図はオブジエクトの内部に存在するホール（又は逆の状
態において）に属する白ペルが存在するか否かを決定す
るために境界に沿つて諸隣接ペルを評価するホール検出
回路を示す図、第８Ａ図はオブジエクト又はホールの内
側境界若しくは外側境界に沿つてのカーソルの一連の動
きに従う一連の不連続な方位角のためのコード・ワ・−
ドを発生するエンコーダを示す図、第８Ｂ１第８Ｃ及び
第８Ｃ″図は鎖式連結コード化データを輪部に変換する
デコーダを示す図、第９図は第９Ｂ１第９Ｂ′及び第９
Ｗ図の組合わせ方を示す図、第９Ａ１第９Ｂ１第９Ｂ″
及び第９Ｖ図は選択回路及び内側輪部又は外側輪部の引
続いて周縁を追跡するための初期座標を貯える計数器を
示す図、第１０、第１１Ａ及び第１１Ｂ図は主要な装置
状態及び圧縮モード及び伸長モードの切換えを図表形式
で示す図、第１２Ａ乃至第１２Ｅ図は主要モードの各々
のためのフロー・チヤート・を示す図、第１３図は主要
な圧縮ステツプでのオブジエクトの処理状況を示す図、
第１４図はラスタ検索メカニズムの詳細な論理を示す図
である。 １１・・・・・・ランダム・アクセス・メモリ、１５・
・・・・・輪部追跡装置、２９・・・・・・輪部閉完了
検出器及び１．Ｊ位置計数器、２１・・・・・・エンコ
ーダーデコーダ、３７・・・・・・スタツク・メモリ。

Claims (1)

【特許請求の範囲】
1. １ ビット・アドレス可能なランダム・アクセス・メモ
   リに記憶された黒ペルよりなる、白黒像のオブジェクト
   の周縁をエンコードするための装置において、前記メモ
   リの像を所定の順序でアクセスする手段であつて、オブ
   ジェクトの最初の黒ペルに出合つたことを指示する手段
   及び前記最初の黒ペルのメモリ座標を指示する手段を含
   むものと、前記アクセス手段に応答する手段であつて、
   連接する黒ペルに出合うように前記オブジェクトの外側
   周縁を追跡し各出合つた連接する黒ペルの相対位置を指
   示する手段を含むものと、前記追跡手段に応答し各出合
   つた黒ペルの相対位置を所定のコード化フォーマットで
   エンコードする手段と、前記メモリに接続され前記追跡
   手段に応答して各出合つた黒ペルを白に変え前記オブジ
   ェクトを縮小させて前記メモリから削除するための制御
   手段であつて、前記エンコード手段に接続され前記追跡
   手段に応答して前記追跡手段が再び前記最初の黒ペルに
   出合つたとき前記エンコード手段を滅勢する手段を含む
   ものと、を有する像周縁エンコーデイング装置。