JPH01251180A - 輪郭検出装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は２値画像の輪郭を検出ずろ装置に関するしので
ある。

Ｂ１発明の概要 本発明は、被写体をラスタスキャンして得られた黒白に
対応する２値化画素データに基づき黒白の境界に相当す
る輪郭を検出する装置において、２画素×２画素の画素
データを順次に取り出し、ｌライン前に取り出した画素
データに基づいて、例えばラスタスキャンＹ方向の輪郭
画素間の接続関係を求め、この関係及び画素データの配
列パターンの各情報を含むコマンド列を作成し、これら
コマンド列に基づいて、輪郭要素を系列化したテーブル
を作成するとともに輪郭ベクトルを求め、且つ各輪郭毎
の輪郭ヘクトル系列のベクトル座標データを記載するテ
ーブルを設けることによって、画像メモリの容量、ハー
ドウェア構成及び処理時間が画像サイズや解像度に影響
されることがなく、更に輪郭の取り出しを容易に行うこ
とができるようにしたものである。

Ｃ０従来の技術 文字や図形等のパターンを処理する場合、例えば、書類
や図面等の被写体をイメージスキャナ等の人力装置で操
作して得られる黒と白の２値画像データ（入カバターン
）に変換し、この２値画像データから対象物の輪郭画素
を抽出し、情報圧縮処理や対象物の認識処理を行ってい
る。

このうち、２値画像データから対象物の輪郭画素を抽出
するための従来方式は、第２５図に示すような動作を示
す。これは以下のような処理の流れで記述できる。

■まず、２値画像データをすべて、専用画像メモリＭに
記憶する。

■次に、このメモリＭから検出対象となろ′ｒの輪郭の
始点となる点、例えば、点Ｐ１を探す。

■この点Ｐ、に隣接する点を順次追跡抽出して対象物Ｔ
の輪郭画素を抽出する。

Ｂ１発明が解決しようとする課題 このように、従来の輪郭画素抽出方式においては、１画
面分の２値画像データを記憶するための専用メモリを必
要とする。これは、入力する書類や図面のサイズが大き
くなればなるほど、また、高解像度にするほどメモリが
大容量になる欠点を有する。

ハードウェア構成の点からいえば、画像メモリは入力画
像の縦横サイズに比例して大きくなるため、場合によっ
てはメモリボードの追加を考慮した構成が必要となる。

例えば、ＡＯサイズを対象とする画像メモリは、Ａ４サ
イズの画像メモリに比べて、１６倍もの容量を必要とし
ており、Ａ４サイズのメモリボードが１枚で構成される
ときでらＡＯサイズは１６枚も必要である。

次に、処理時間にも大きな影響がある。従来の方式では
、画像メモリに１画面分が記憶されるまでの待ち時間が
必要であり、また、輪郭を抽出するためには、逐次追跡
をソフトウェアで行う必要があり、これらも対象の画像
のサイズや解像度に比例して、処理時間に影響を与える
ことになる。

以上をまとめると、従来の輪郭抽出方式では、単に画像
サイズを大きくしたり、解像度を高くするだけで、ハー
ドウェア構成、処理時間等に影響する欠点があり、さら
には、製品外観や価格などにも影響を及ぼす要因となっ
ていた。

本発明はこのような課題を解決するためになされたもの
であり、画像メモリの容量、ハードウェア構成及び処理
時間が画像サイズや解像度に影響されろことがなく、更
に輪郭の取り出しを容易に行うことができる輪郭検出装
置を提供することを目的とする。

０１課題を解決するための手段 第１図は本発明の構成を示す図であり、ｌは輪郭抽出部
である。この輪郭抽出部Ｉは、第２図に示すように被写
体をラスタスキャンして得られた黒白に対応する２値化
画素データを取り込んで、縦横２画素×２画素の画素デ
ータをスキャンラインに沿って順次に取り出し、この画
素データに基づいて輪郭検出用のコマンド列を作成して
後段の輪郭解析部２に出力する。輪郭解析部２は萌記コ
マンド列に基づいて第１のテーブル格納部３内の輪郭要
素テーブル３４、輪郭管理テーブル３５及び輪郭接続テ
ーブル３６の記載を更新する。また輪郭解析部２は輪郭
要素テーブル３４と輪郭管理テーブル３５を使用して１
輪郭画素系列を構成する各点のうち始点からみて極大と
なる点を抽出する巨視的処理部３１と、この処理で抽出
された連続する２点の間にある最大距離となる点を設定
したしきい値との関係からいくつか抽出する微視的処理
部３２とを備え、この処理により抽出された点の輪郭ベ
クトルを第１の輪郭ベクトル系列テーブル３３１に記載
し、その記載を更新する。

ここで輪郭要素とは互いに隣接した２個の黒画素を結ぶ
ベクトルに相当するものであり、これを結合することに
よって輪郭が構成される。そして輪郭要素テーブル３４
とは、第３図に示すように輪郭要素とこれら輪郭要素群
よりなる輪郭とに対して各々固有の符号を付すと共に、
輪郭要素毎に、その座標及び方向と輪郭要素が所属する
輪郭の符号と輪郭要素の前後に夫々接続されている他の
輪郭要素の符号とを記載するためのものである。また輪
郭管理テーブル３５とは第４図に示すように輪郭毎に先
端及び終端に位置する輪郭要素の符号を記載するための
ものであり、輪郭接続テーブル３６とは、第５図に示す
ようにラスタスキャン方向に並ぶ座標とその座標に前端
または後端が存在する未接続の輪郭要素の符号とその輪
郭要素の未接続端の前後端の区別とを対応させて記載す
るためのらのである。また第１の輪郭ベクトル系列テー
ブルとは第２６図のように輪郭ベクトル系列毎に始点座
標の符号を記載するためのらのである。

また、第２のテーブル格納部１１内には、第２７図のよ
うな解析された輪郭の数（セグメント数）及び各輪郭（
セグメント）毎の輪郭ベクトル数を記載するための輪郭
ベクトル系列管理テーブル３７と、第２８図のような各
輪郭（セグメント）　ｈｊの輪郭ベクトル系列のベクト
ル座標データを輪郭ベクトル系列管理テーブル３７の各
輪郭（セグメント）に対応して記載するための第２の輪
郭ベクトル系列テーブル３３ｂとが設けられている。

１１作用 輪郭抽出部ｌより出力されるコマンド列は、そのときに
取り出された２画素×２画素の画素データに係る画素と
輪郭要素との接続関係の情報、及び当該画素データの黒
白の配列パターンの情報を含む接続・パターンコードと
、当該画素データのＸ座標を示す座標コードとを組み合
わせてなる。

前記接続関係の一例を第６図に示すと、同図（イ）の大
枠で囲まれた２画素×２画素の画素データを取り込んだ
ときには、この画素データのＸ座標Ｘｎに位置する輪郭
要素の前端が接続されているという情報になる。この例
では、画素データの座標としては、紙面に向かって右下
に位置する画素Ｐ１の座標をとっている。また同図（ロ
）の大枠で囲まれた画素データを取り込んだときには、
この画素データのＸ座標より一つ前の座標Ｘ　ｎ−＋に
位置する輪郭要素の後端が接続されているという情報に
なる。なお第６図中○印を有する枠は黒画素を示し、○
印を有しない枠は白画素を示している。

そして例えば第６図（イ）の大枠に着目すると、この場
合の接続・パターンコードは、上述の接続情報と太枠内
の黒白の配列パターンの情報とを含み、コマンド列は、
この接続・パターンコードと画素Ｐ、のＸ座標を示す座
標コードとの組み合わせとなる。なおこの座標コードに
ついては輪郭解析部２側にて、コマンド列の取り込みの
タイミングに同期して発生させることもできる。

このようにして得たコマンド列が輪郭解析部２に取り込
まれると次のような処理が行われる。今第７図の大枠の
画素データに関するコマンド列が取り込まれたとすると
、点線で示す輪郭要素Ｃｊを輪郭要素テーブルに登録し
、その方向渣び座標を記入すると共に、当該輪郭要素Ｃ
ｊの前後に夫々接続されている他の輪郭要素の番号を接
続要素番号側に記入する。この場合輪郭要素Ｃｊは輪郭
要素Ｃｉの前方に位置するので、輪郭要素Ｃｊの欄に係
る後方接続側にＣｉを記入し、輪郭要素Ｃｊの欄に係る
前方接続側にＣｉを記入する。更に輪郭要素Ｃｊの所属
する輪郭の番号をこの例ではＳｉを輪郭番号欄に記入す
る。輪郭要素の方向については例えば８連結の場合、第
８図に示すように上下、左右、斜めの方向に対応してａ
、〜ａ８が規定され、また４連結の場合、上下、左右の
４方向が規定される。そして輪郭管理テーブル３５の輪
郭番号Ｓｉについて、先端の輪郭要素番号欄をＣｉから
Ｃｊに更新すると共に、輪郭接続テープル３６における
当該画素データのＸ座標について、未接続の輪郭要素番
号の前方接続の欄をＣｉからＣｊに更新する。ところで
実際の処理においては、輪郭要素Ｃｉに接続されるべき
要素は輪郭接続テーブル３６により明らかにされている
ため、輪郭要素テーブル３４の輪郭要素番号Ｃｊ欄に係
る前方接続棚のＣｊの記載は、輪郭接続テーブル３６を
参照して行われる。以上において所属輪郭番号は、ラス
タスキャンの進行に伴って別々に発生した二つの輪郭が
接続されて一つの輪郭になった場合には一方が他方に統
合されて同一になる。

解析処理部２の処理結果は、第２６図に示す第１の輪郭
ベクトル系列テーブルに、輪郭ベクトル系列番号及び始
点座標データが記載される。

前記のようにして輪郭解析部２で解析処理が行われ系列
化された輪郭の数（セグメント敗ｉ）及び各輪郭毎の輪
郭ベクトル数（ｍｉ）は、第２７図の輪郭ベクトル系列
管理テーブル３７に記載される。また各輪郭毎の輪郭ベ
クトル系列のベクトル座標データ（Ｘｉ、Ｙｉ）は、前
記輪郭ベクトル系列管理テーブル３７の各輪郭に対応し
て第２８図の第２の輪郭ベクトル系列テーブル３３ｂに
記・載される。

Ｇ　実施例 本発明の実施例では、第９図に示すように内部バス１４
に輪郭抽出部１、輪郭解析部２及び第１のテーブル格納
部としての内部メモリ１５を結合して、各部間の情報の
受は渡しを内部バス１４を通じて行うように構成し、更
に内部バス１４をバスインターフェイス１６を介してメ
インバス１７に結合し、これにより輪郭検出装置１８で
得られた情報を外部機器に与えるように構成している。

尚、図中１９は主制御部、２０は第２のテーブル格納部
としての主メモリ、２Ｉは２値画像人力処理部、２２は
２値画像人力装置、２３は入出力処理部である。

次に輪郭抽出部１から発生するコマンド列の具体例に関
して述べる。第１０図及び第１＋図は、谷々２画素×２
画素の画素データの黒白の配列パターンとこの画素デー
タに対する輪郭要素の接続関係との成立関係を示す図で
あり、第１０図は８連結、第１１図は４連結の場合に夫
々相当する。

これら図において左端の縦に並ぶ４コマの窓は第１２図
に示すように２画素×２画素の画素データ（ｄｏ−ｄ３
）を示し、Ｉｌｌ、ｒＯＪが立っている部分は夫々黒画
素、白画素に相当する。また上端の横に並ぶ４コマの窓
は、第１３図に示すように、上側左右の２コマが夫々画
素データのＸ座標Ｘ　ｎ−１における前方接続の輪郭要
素の有無及びＸ座標Ｘｎにおける前方接続の輪郭要素の
有無を示し、下側左右の２コマか夫々画素データのＸ座
標Ｘ　ｒｌ−１における後方接続の輪郭要素の有無及び
Ｘ座標Ｘ。における後方接続の輪郭要素の有無を示す接
続フラグであり、ＮＪ、ｒＯＪは夫々接続有り、接続無
しを意味している。例えば第６図（イ）の大枠で囲まれ
た画素領域における接続フラグは、（ｘｎ、ｙｎ、）の
座標位置にて輪郭要素の前端が当該画素領域に接続され
ているから、第１０図の接続フラグ欄の左から５番目の
ように右上のコマのみがＩｌｌの窓で表わされろ。

そして第１０図、第１＋図において、画素データ及び接
続フラグの項の交差する部分が空白であるということは
、このような画素データ及び接続フラグの組み合わせに
対しては輪郭解析部２にて処理を行う必要がないことを
意味する。○が記入された組み合わせのどきは、輪郭解
析部２にて処理を行う必要があり、その組み合わせに対
応した接続・パターンコードが輪郭抽出部Ｉにて発生す
る。×が記入された組み合わせについては、そのような
組み合わせが存在しないことを表わす。△が記入された
組み合わせについては、ランレンゲの符号化を実施する
ときのみ、その組み合わけに対応した接続・パターンコ
ードが発生する。なお第６図、第７図においては、輪郭
要素の発生方向（ベクトルの向き）を考慮せずに描いて
いるが、実際には輪郭要素を、物体（または黒画像部）
の外縁に沿って右回りに向くように発生させており、こ
の発生の仕方に対応させて第１Ｏ図及び第１１図の成立
関係図を作成している。

萌記コマンド列はこのようにして得られた接続・パター
ンコードの他に読み出しレディコードや座標コード等が
含まれ、その−例を挙げろと第１４図のように表わされ
る。同図中Ａ、は読み出しレディコードであり、画素デ
ータ及び接続フラグの組み合わせが第１Ｏ図、第１１図
の×、あるいは×及び△に相当するときにはコマンド列
を無効とする乙のである。Ａ、は画素データのＸ座標、
Ａ３゜Ａ４は画素データの下側左右に並ぶ二つの画素の
黒、白を示すコードであり、ランレングス化を実施する
場合には、Ａ　３　、　Ａ　４か必要である。Ａ５は１
頁（全ライン）の終わりを示ずＥＯＰ　（ＥＮＤＯＦ　
　ＰＡＧＥ）コード、八〇は１ラインの終わりを示すＥ
ＯＩ’（（ＥＮＤ　　ＯＦ　　ＲＯＷ）コード、Ａ７は
接続・パターンコードである。

次いで輪郭抽出部ｌの具体的構成例を第１５図を参照し
ながら説明する。画素データラッチ１０１には信号線５
及び後述するラインメモリ１０５から画素データが入力
される。このラッチはこれら人力されたデータから、第
１２図に示すような２画素×２画素、すなわち互いに隣
接する４画素のデータｄ。−ｄ３を取り込み、ラッチす
る。

アドレス発生回路１０８は、第２図に示したラスタスキ
ャンの進行に応じてＸ座標及びＹ座標を発生させる。こ
の回路は発生させた座標を後述するラインメモリ１０５
、周辺判定回路１０９、並びに前方フラグメモリ１０６
に与えると共に、信号線８を通じて輪郭解析部２にコマ
ンド列の一部として送出する。

ラインメモリ１０５はアドレス発生回路１０８か発生さ
せたＹ座標より１小さいＹ座標、すなわち上記画素デー
タラッチ１０１がラッチした画素データｄ、、ｄ３のＹ
座標の画素データを画素データラッチ＋０２の出力から
取り込み、順次記憶する。

前方フラグメモリ１０６はＸ座標の数と同じ数のアドレ
スを持ち（例えば、Ｘ座標の数が５１２のとき、このメ
モリのアドレスの数も５１２）、画素データ内のある画
素に輪郭要素の面端が接続されかつその輪郭要素が他の
輪郭要素に接続されていないとき、その画素のＸ座標に
対応するアドレスに論理ＮＪのデータを書き込む。

一方、後方フラグメモリ＋０７も座標と同じ数のアドレ
スを持つが、このメモリには、ある画素に輪郭要素の後
端が接続されかつその輪郭要素が他の輪郭要素に接続さ
れていないとき、その画素のＸ座標に対応するアドレス
に論理ＮＪのデータが書き込まれる。

接続フラグラッチ１０２は、前方フラグメモリ１０６、
後方フラグメモリ１０７および後述する接続フラグ変更
回路１０４の出ツノデータを、輪郭画素の接続状態を示
すデータとして保持する。

周辺判定回路１０９は、アドレス発生回路１０８が発生
するＸ及びＹ座標をもとに、処理の対象となる４つの画
素ｄ。−ｄ３が、画面の境界からはみ出しているか否か
を判定する。画面の周囲から処理画素がはみ出している
場合には、所定の信号を画素データラッチ１０１および
接続フラグデータ１０２に出力する。これらのラッチは
、この信号を受は取ると、画面の境界からはみ出した画
素については、強制的に白画素（背景となる画素）とす
る。

コマンド発生回路１０３は画素データラッチ１０１が出
力する４つの画素データ及び接続フラグラッチ１０２が
出力するフラグデータをもとに輪郭追跡を行うための所
定のコマンドを輪郭解Ｆｆｒ部２に対して発生する。コ
マンド発生回路１０３はこのとき、処理を実施する必要
があるか否かを示す読み出しレディ信号を信号線６を通
じて、また前記接続・パターンコードを信号線７を通じ
て輪郭解析部２に送る。

接続フラグ変更回路１０４は、輪郭解析部２が上記コマ
ンドに従って処理を実施した後、画素の接続状態が変化
するので、処理後の接続フラグを、画素データラッチ１
０１と接続フラグラッチ１０２の出力データとをもとに
求め、前方フラグメモリ１０６、後方フラグメモリ１０
７、並びに接続フラグラッチ１０２に出力する。

次に第１５図に示す回路の動作を説明する。アドレス発
生回路１０８は、ラスタスキャンの進行に従って、最も
新しくサンプリングされ、信号線５から入力された画素
データに対応するＸ及びＹアドレスを発生させ、出力す
る。

画素データラッチ１０１は、ラスタスキャンによってサ
ンプリングされた画素データが信号線５から人力される
と、ラインメモリ１０５からの画素データと共にこれら
を順次受は取り、第１２図に示すような２画素×２画素
、すなわち互いに隣接する４画素のデータｄ。−ｄ３を
ラッチする。

ラインメモリ１０５は、画素データラッチｌＯ１が出力
する画素データｄｌを取り込むことによって一行前の画
素データ、すなわちＹアドレスが現在信号線５から入力
されている画素データｄ。

のＹアドレスより１小さい行の画素データを一行分記憶
している。そして、信号線５から画素データｄ。、ｄｒ
が画素データラッチ１０１に順次入力されたとき、ライ
ンメモリ１０５は、アドレス発生回路１０８が出力する
上記アドレスデータをもとに、画素データｄｔ、ｄ３を
順次向ラッチに出力する。これにより、画素データラッ
チ１０１は隣接する４つの画素データｄ。−ｄ３をラッ
チすることができる。

接続フラグ変更回路１０４は、上記画素データｄ　ｏ−
ｄ　３と接続フラグラッチ１０２の出力データとを乙と
に、４つの接続フラグデータを発生ずる。

４つのデータの内、二つは第１３図に示す接続フラグの
上側２コマに相当する前方接続フラグデータ、他の二つ
は下側２コマに相当する後方接続フラグデータである。

接続フラグデータ及びその発生について第１６図を用い
て詳しく説明する。画面Ｐには例として二つの画ｅ、Ａ
、Ｂが示されており、これらの画像は○が書き込まれた
画素によってそれぞれ構成されている。図中、太線で囲
んだ４つの画像が現在、輪郭追跡処理の対象となってい
る画素である。

一方、画面Ｐの上に示したＲは各Ｘ座標の前方接続フラ
グデータ、Ｔは各Ｘ座標の後方接続フラグデータをそれ
ぞれ表わしている。各データは座標の順に描かれており
、右のものはとそのＸ座標は大きい。そして、空白のも
のはフラグデータの値が「０」、Ｉが書き込まれている
ものは値が「１」であることを示す。

具体的に説明すると、画素ｅｌには輪郭要素Ｃａの後端
が接続されているのでこの画素のＸ座標の後方接続フラ
グデータＴｌはｒｌＪとなっている。逆に、画素ｅ２に
は輪郭要素ｃｂの前端が接続されているのでそのＸ座標
の油力接続フラグデータＲ２は「１」となっている。同
様に、画素ｅ３に対応する後方接続フラグデータＴ４は
「ｌ」、画素ｅ４に対応する後方接続フラグデータＲ４
も「１」となっている。その他のフラグデータは、対応
する画素に輪郭要素が接続されていないので、すべて「
０」となっている。

これら前方及び後方接続フラグデータは、それぞれ前方
フラグメモリ１０６及び後方フラグメモリ１０７のＸ座
標に対応する所定のアドレスに、後述のように接続フラ
グ変更回路＋０４によって書き込まれる。

第１６図中太線で囲まれた４つの画素が処理の対象とな
っているとき、前方フラグメモリ１０６及び後方フラグ
メモリ１０７はそれぞれ、左側の処理対象画素のＸ座標
に対応する接続フラグデータＲ２，Ｔ２を出力する。一
方、接続フラグ変更回路１０４は、右側の処理対象画素
のＸ座標に対応する接続フラグデータＲ３，Ｔ３を出力
する。

接続フラグラッチ１０２はこれらをラッチし、コマンド
発生回路１０３と接続フラグ変更回路１０４とに出力す
る。

接続フラグ変更回路１０４は上記４ビツトの接続フラグ
データ及び画素データラッチ１０１からの画素データｄ
０〜ｄ３を受は取り、輪郭要素追跡処理後のフラグデー
タを求める。すなわち、追跡処理によって、画素ｅ２に
は、第１７図に示すように、輪郭要素ｃｂに次の輪郭要
素Ｃｃが接続されるので、接続フラグ変更回路１０４は
、前方接続フラグデータＲ２を「０」とし、前方接続フ
ラグデータＲ３をｒｌＪとする。後方接続フラグデータ
については、輪郭要素の後端が単独で存在しない状態が
継続されているので変更は行わない。

接続フラグ変更回路１０４は上記変更処理後のフラグデ
ータＲ２，Ｔ２を萌方フラグメモリ１０６及び後方フラ
グメモリ１０７の所定のアドレスに記憶さＵ゛、変更処
理後のフラグデータＲ３，Ｔ３を接続フラグデータ１０
２に出力してラッチさＵ゛、次の処理に備える。

そしてコマンド発生回路＋０３では、画素データラッヂ
ｌｏｔからの画素データｄ。−ｄ３及び接続フラグラッ
チ１０２からの４ビツトのフラグデータをらとに、接続
・パターンコードを発生ずると共に、２画素×２画素の
画素データのうち下側二つのデータｄ。、ｄ＋も出力し
、これらコードが信号線７を介して輪郭解析部２に与え
られる。更にコマンド発生回路１０３は読み出しレディ
コードを信号線６に出力し、例えばランレングス化を実
施しない場合、接続・パターンコードが第１０図、第１
１図の○印に相当するものであるときには、読み出しレ
ディコートをＮＪとし、△印またはＸ印に相当するもの
であるときには「０」とする。また周辺判定回路１０９
には信号線９を通じて１頁の終わりを示ずＥＯＰ信号及
び１ラインの終わりを示ずＥＯＲ信号が入力され、この
結果ここから信号線６にＥＯＰコート及びＥＯＲコード
が出力される。こうして信号線６には、アドレス発生回
路１０８よりの画素データのＸ座標を示す座標コードと
共にＥＯＰコード及びＥＯＲコードが与えられ、これら
コードが輪郭解析部２に与えられる。

以上において、上述実施例のように第１０図。

第１１図に示す組み合わせに応じて読み出しレディコー
ドを発生さ仕れば孤立画素をノイズとして除去できる利
点がある。即ち孤立画素に対して発生する画素データの
パターンは第１８図（イ）〜（ニ）のように４種類ある
が、この場合この画素に対しては輪郭要素の接続は存在
しないので、読み出しレディコードは「０」となり、従
って輪郭解析部２では処理が行われていないからである
。

ただしランレングス化を実施する場合には第１８図（イ
）、（ロ）のパターンのときに読み出しレディコードは
ｒｌＪとなるが、輪郭追跡処理とは無関係である。

次に輪郭解析部２で行われる輪郭画素系列化処理と輪郭
ベクトル系列化処理を説明する。先ず第１９図に示すよ
うにＹアドレスを０とした後コマンド列を取り込み、こ
のコマンド列の中にＥＯＰの指示がされている場合には
処理を終了し、指示かされていない場合にはＦＯＲの指
示がされているか否かを判断する。ＦＯＲの指示がされ
ている場合にはＹアドレスを一つ加算してコマンド列を
取り込み、指示がされていない場合には内部メモリ１５
内に格納されている各テーブル（第３図〜第５図参照）
を更新する。

各テーブルの更新のフローは第２０図に示すようであり
、同図中のステップＳＴ、〜ＳＴ３は以下の通りである
。

ＳＴ、・・・輪郭要素が単独で新たに発生しているか否
かの判断を行う。

ＳＴ、・・・輪郭要素が発生ずると同時に既に存在して
いる輪郭要素と接続されるか否かの判断を行う。

ＳＴ３・・・既に発生している二つの輪郭要素の端部が
２画素×２画素の画像データの中に存在するか否かの判
断を行う。

次いで第２０図中の処理１〜３の内容について述べると
、処理ｌでは第２１図に示すようにステップＳ　Ｔ　Ｉ
−９Ｔ　４が実行される。各ステ・ツブＳＴ。

〜ＳＴ４は以下の通りである。

ＳＴＩ・・・第３図に示す輪郭要素テーブル及び第４図
に示す輪郭管理テーブルにて輪郭要素番号Ｃｉと輪郭番
号Ｓｉとを新たに確保する。

Ｓ　Ｔ　ｔ・・・輪郭要素テーブルのＣｉ番目の方向、
座標の欄に該当事項を、接続要素番号の前　。

方接続及び後方接続の両側にＮ０ＮＥ （該当するものがないことを示すコード）を、所属輪郭
番号の欄にＳｉを夫々書き込む。

Ｓ　Ｔ　３・・・輪郭管理テーブルのＳｉ番目の先端の
輪郭要素番号及び終端の輪郭要素番号の両側にＣｉを書
き込む。

ＳＴ、・・・第５図に示す輪郭接続テーブルの前方接続
及び後方接続の該当する欄に夫々Ｃｉを書き込む。

処理２では第２２図に示すようにステップＳＴ。

〜ＳＴｅか実行される。各ステップＳＴ、〜ＳＴｅは以
下の通りである。

Ｓ　Ｔ　＋・・・輪郭要素テーブルにて輪郭要素番号Ｃ
１を新たに確保する。

ＳＴ、・・・輪郭接続テーブルの該当欄から接続先の輪
郭要素番号Ｃｊを求め、当該欄をＮ０ＮＨに書き換える
。

ＳＴ３・・・輪郭要素テーブルのＣｊ番目の前方接続及
び後方接続の欄の該当する方にＣｉを書き込むと共に所
属輪郭番号の欄から Ｃｊが属する輪郭番号Ｓｋを求める。

ＳＴ４・・・輪郭要素テーブルのＣ４番目の方向、座標
の欄に該当する事項を、前方接続及び後方接続の欄の該
当する方にＣｊを、他方にＮ０ＮＥを、所属輪郭番号欄
にＳｋを夫々書き込む。

ＳＴ、・・・輪郭管理テーブルのＳｋ番目の先端の輪郭
要素番号及び終端の輪郭要素番号の欄のうち該当する方
をＣｉに書き換える。

ＳＴ、・・・輪郭接続テーブルの該当する欄にＣｉを書
き込む。

処理３では、第２３図に示すようにステップＳ　Ｔ　Ｉ
””　Ｓ　Ｔ　ｓが実行される。各ステップＳＴ、〜５
Ｔｌｌは以下の通りである。

ＳＴ、・・・輪郭接続テーブルの該当欄から接続の対象
となる二つの輪郭要素Ｃｉ、Ｃｊを求め、当該欄をＮ０
ＮＥに書き換える。

ＳＴ、・・・輪郭要素テーブルのＣｉ番目の前方接続及
び後方接続の両側のうち該当する方にＣｊを書き込むと
共に所属輪郭番号の判からＣｉが所属する輪郭番号Ｓｋ
を求める。

ＳＴ３・・・輪郭要素テーブルのＣｊ番目の前方接続及
び後方接続の両側のうち該当する方にＣｉを書き込むと
共に所属輪郭番号の欄からＣｊが所属する輪郭番号Ｓσ
を求める。

ＳＴ、・・・ＳｋとＳＱとが同じ番号か否か判断する。

Ｓｒ１・・・輪郭管理テーブルのＳｋ番口の先端の輪郭
要素番号及び終端の輪郭要素番号のうち接続の対象とな
っていない方の輪郭要素番号Ｃｍを求め、Ｓｋ番目の各
欄を Ｎ　ＯＮ　Ｅ　ｉ、：書き換える。

ＳＴｅ・・・輪郭管理テーブルのＳ夕番目の先端の輪郭
要素番号及び終端の輪郭要素番号のうち接続の対象とな
っている端部側の欄をＣｍに書き換える。

第２４図は上記の処理１〜３と２画素×２画素の画素デ
ータの取り出し位置との関係を示す図であり、同図中数
字は輪郭要素の番号、点線の四角形は画素データ、黒点
は黒画素を夫々示す。画素データＤ、に対して生成され
たコマンド列の処理は処理ｌに該当し、画素データＤ、
に対して生成されたコマンド列の処理は処理２に該当す
る。また画素データＤ３．Ｄ、に対して生成されたコマ
ンド列は夫々処理３におけろＳｋとＳρが等しい場合及
び異なる場合に相当する。

次に輪郭ベクトル系列化処理について説明する。

この輪郭ベクトル系列化処理は巨視的処理及び微視的処
理を行った後、第２６図に示す第２の輪郭ベクトル系列
テーブル３３ａを更新するものである。

第２９図（ａ）は巨視的処理部３Ｉの説明図であり、こ
の図において、ある画像ｌ＼についての輪郭系列Ｐｏ（
Ｘｏ、Ｙｏ）、Ｐ＋（Ｘｉ、Ｙｌ）−Ｐ＋（Ｘｉ、　Ｙ
１）−Ｐｎ（Ｘ、、、Ｙｏ）［ただしＰ、は輪郭追跡の
始点とする）が与えられたとき、下記条件１を満たすよ
うな点Ｐ、を直線近似点として全抽出する。

［（１”＋−＋≦ｌ’ｔ）ｎ　（１”＋＞　Ｉ’＋−１
）ｎ　（１’ｔ≧Ｉ”ｔｈ）］・・・条件ま ただし、ｌ！□はＰ。とＰｌの距離の２乗（（Ｉ）式に
示す）、Ｉ’ｔｈはしきい値の２乗である。

１”＋−（Ｘｉ−Ｘｏ）　！＋（Ｙ＋−Ｙｏ）　’　　
・（１）第２９図（ｂ）は微視的処理部３２の説明図で
、この第２９図（ｂ）において、ある画像Ａについての
輪郭系列点Ｐ、、Ｐ、、・・・Ｐ、、、ｐ、・・・Ｐ、
から直線近似点ｑ。（−Ｐｏ）　、Ｑｌ、　Ｑｌ・・・
ｑ　＋（−Ｐ　１）。

ｑｌｌ−１（＝ＰＪ）、・・・ｑ　ｎ　（−Ｐ。）を以
下の手順により求める。現在抽出された直線近似点のう
ち連続する２点（第２９図（ｂ）に示す）、Ｑ　ｌ＋　
Ｑ　ｌ”１（最初はｑｏと巨視的処理部３１で得られた
ｑ１）の間の点Ｐについて次に示す条件２を満たすよう
な点をｑｌ、１として抽出（ｑ＋□をｑｌ、２に変えろ
処理を含む）して同様の処理を繰り返す。そして条件２
を満たすような点がなければＱ　１６１＋　Ｑ　＋ｈｔ
間について同様の処理を繰り返す。この処理を全ての点
Ｐが満足しなくなるまで繰り返す。

ｌｄｌ’□８≧ｄ　ｌ”ｔｈｌ　　・・・条件まただし
、ｄ　１．、、　：各ｄ１の最大値ｄ　Ｉ’ｍａｘ＝ｍ
ａｘ　［−、ｄ　１２Ｊ、　−］ ｄｌ；線分ｑＩ＋　Ｑ　ｌ＋１から各Ｐ点までの距離ｄ
　１ｔｈ　：線分Ｑ　ｌ、　　Ｑ　１＊１の大きさによ
って変わるしきい値でｄＩｔｈ＝α・して与えられる。

なお、αは係数で第２９図（ｃ）に示す例で、例えば、
αは第２９図（ｃ）になるように値をテーブル化すれば
よい。また、α＝１．２・・・といった定数で持てば単
純にＬに比例したしきい値となる。

次にｄｌの求め方について第２９図（ｄ）を用いて述べ
る。

一一−−−−→　−＞　　　　−一→　−〉（ｑ＋Ｑ＋
＊＋”　ｑ＋Ｐ、１）−ｌｑ＋ｑ＋、＋ｌｌｑ＋Ｐ　Ｊ
１ｃｏｓＯＪ＝（Ｘｋ−ＸＩＸＹＪ　　Ｙυ＋（Ｙｋ−
Ｙｌ）（ＸＪ−ＸｈここでＸｈ　　Ｘ＋＝ｄＸｈ、Ｙ、
＋　　Ｙｌ”ｄＹＪ。

Ｙｈ　　Ｙ＋＝ｄ　Ｙｈ、ＸＪ　　Ｘ’ｌ＝ｄ　ＸＪと
おくと上記式は次のようになる。

−〉 一’−Ｉ　Ｑ　ＩＰ　Ｊ　ｌ　２ＣＯ８２θ、＝（ｄ　
Ｘｈｘ　ｄ　ＹＪ＋　ｄ　ＹｋＸ　ｄ　Ｘ、４）’／−
：ｌ　２−一−−→　。

ｄｌｊ＝　ｌ　ｑ＋Ｐ、１１ｓ＋ｎｏ。

−〉−）−〉 ｄｌｊ’＝ｌｑ＋Ｐａｌ’ｓｉｎ’θＪ＝ｌＱＩＰＪｌ
’　ＩＱＩＰＪｌ’ｃＯ８”θ３−〉−〉 ”ｌ　ＱＩＰＪＩ’　（ｄ　ｘ、ｘ　ｄ　ＹＪ＋　ｄ　
ＹｉｔＸ　ｄ　ＸＪ）’／　Ｉ　Ｑ　＋　Ｑ　ｔＪ”＝
　ｄ　ｘＪ”＋ｄｙＪ”−ＣｄＸｋＸｄ　ＹＪ十ｄ　Ｙ
ｌｉＸｄ　ＸＪ）”／ｄ　Ｘｋ”＋ｄ　Ｙｍ”上記から
三角関数や平方根計算が省略できる。

前記巨視的処理及び微視的処理が行われた結果、第２６
図の第１の輪郭ベクトル系列テーブル３３ユの記載は更
新される。

次に、上記のような処理により内部メモリ１５の各テー
ブル（第３図、第４図、第５図、第２６図）に記載され
、系列化された結果は、主制御部１９によって主メモリ
２０の輪郭ベクトル系列管理テーブル３７（第２７図）
及び第２の輪郭ベクトル系列テーブル３３ｂ（第２８図
）に記載される。すなわち輪郭ベクトル系列管理テーブ
ル３７には、セグメント数ｉと各セグメント毎の輪郭ベ
クトル数ｍｉが記載される。また第２の輪郭ベクトル系
列テーブル３３ｂには、各セグメント毎の輪郭ベクトル
系列のベクトル座標データＸｉ、Ｙｉが前記輪郭ベクト
ル系列管理テーブル３７の各セグメントに対応して記載
されろ。尚セグメントとは一つの図形（又は文字等）を
１輪郭単位に分離したものであり輪郭と等価である。さ
らに主制御部１９は、輪郭ベクトル系列管理テープ、ル
（第２７図）及び第２の輪郭ベクトル系列テーブル３３
ｂ（第２８図）に記載された内容を入出力処理部２３に
引き渡す。次に入出力処理部２３は、前記記載内容をワ
ークステーション等にシリアル又はパラレル等の通信手
段を用いて出力する。

このように輪郭解析部２の処理結果の輪郭数及び該輪郭
毎の輪郭ベクトル数のデータと、各輪郭毎の輪郭ベクト
ル系列のベクトル座標データのみを第２のテーブル格納
部としての主メモリ２０に格納するだけで２値画像の低
味のある図形の輪郭を検出することができるので、図形
（文字）等の大幅な圧縮化が図れる。例えばｒＭＪとい
う文字の場合、従来方式によると第３０図（ａ）の白部
分と破線部分で示される白黒情報を総て保存する必要が
あるのに対し、本願発明によれば第３０図（ｂ）の黒丸
の点の情報を保存するだけで良い。

Ｈ、発明の効果 本発明によれば、２画素×２画素の画素データに係る画
素と輪郭要素との接続関係、皮びその画素データの黒白
の配列パターンを知ることにより輪郭要素の配列状態を
認識しており、前記接続関係についてはＩライン萌に取
り出した画素データに基づいて作成できるから、従来の
ように１画面分の画像データを記憶する方式に比べて大
幅に画像メモリを節約することができ、システム全体を
コンパクト化できる。ここにラインメモリは、−般的な
１６画索／ｙの分解能においてＡＯサイズでも長尺方向
で約１９０００ビツトであり、たかだか数キロバイトも
あればＡ４からＡＯサイズまでをカバーできることにな
り、その程度のメモリを持つことで画像サイズや解像度
に影響されないハードウェア回路を実現できろ。

また１ラインのスキャニング時間を単位として処理を行
うため、１画面の人力時間とほぼ等しい時間（最大１ラ
イン分の遅延時間）に輪郭を抽出できるため、従来方式
の処理時間に比べ大幅な高速処理が可能となった。

また、原画に忠実なベクトル化が行える。特に曲線部に
対するベクトル化の生態が非常に良い。

また、座標値系列なので本質的に拡大、縮小。

回転操作が容易に行える。

更に第１及び第２のテーブル格納部を用いて輪郭ベクト
ル系列化されたベクトル座標データの保存を行うだけで
２値画像の意味のある図形の輪郭を検出することができ
、図形（文字）情報の大幅な圧縮化が図れる。

【図面の簡単な説明】

第１図は本発明のハードウェア構成を示すブロック図、
第２図はラスタスキャンの様子を示す説明図、第３図は
輪郭要素テーブルを示す説明図、第４図は輪郭管理テー
ブルを示す説明図、第５図は輪郭接続テーブルを示す説
明図、第６図（イ）。 （ロ）は、各々画素データと輪郭要素との関係を示す説
明図、第７図は輪郭要素間の接続状態を示す説明図、第
８図は輪郭要素の方向を示す説明図、第９図は本発明の
ハードウェア構成を示す構成図、第１０図及び第１Ｉ図
は画素データと接続関係との成立関係を示す説明図、第
１２図は画素データを示す説明図、第１３図は接続フラ
グを示す説明図、第１４図はコマンド列を示す説明図、
第１５図は輪郭抽出部を示す回路図、第１６図及び第１
７図は各々接続フラグデータの説明図、第１８図は孤立
画素のパターンを示すパターン図、第１９図は輪郭解析
部の全体処理を示すフローチャート、第２０図はテーブ
ル更新処理を示すフローチャート、第２１図〜第２３図
は夫々処理１〜３を示すフローチャート、第２４図はテ
ーブル更新処理と画素データの位置との関係を示す説明
図、第２５図は従来の輪郭画素抽出態様を示す説明図、
第２６図は第１の輪郭ベクトル系列テーブルの説明図、
第２７図は輪郭ベクトル系列管理テーブルの説明図、第
２８図は第２の輪郭ベクトル系列テーブルの説明図、第
２９図（ａ）〜第２９図（ｄ）は巨視的処理及び微視的
処理の処理内容を示す説明図、第３０図（ａ）、（ｂ）
は格納データの説明図である。 １・・・輪郭抽出部、２・・輪郭解析部、３・９．第１
のテーブル格納部、４・・第２のテーブル格納部、１４
・・・内部バス、１５・・内部メモリ、１６・・・バス
インタフェース、１７・・・メインバス、１８・・・輪
郭検出装置、１９・・・主制御部、２０・・・主メモリ
、２１・・・２値画像入力処理部、２２・・・２値画像
人力装置、２３・・・入出力処理部、３１・・・巨視的
処理部、３２・・・微視的処理部、３３ａ、３３ｂ・・
・輪郭ベクトル系列テーブル、３４・・・輪郭要素テー
ブル、３５・・・輪郭管理テーブル、３６・・・輪郭接
続テーブル、３７・・・輪郭ベクトル系列管理テーブル
。 第１図 本発明の構成図 １　輪郭抽出ｆｉＩ３３　ａ、　３３　ｂ−ＮＩＦＩＩ
ベクトル系列テーブル２　輪郭解析部　　　　　　　　
　３４　・輪ｎ要素テーブル３　第１のテーブル格納部
　　　　３５・・輪郭管理テーブル４・・第２のテーブ
ル格納部　　　３６・輪部接続テーブル３１　巨視的処
理部　　　　　　　　３７・・輪郭ベクトル系列３２・
微視的処理部　　　　　　　　　　　管理テーブル第２
図 ラスタスキャンの説明図 第３図 輪郭要素テーブルの説明図 輪郭管理テーブルの説明図 第５図 輪郭接続テーブル 第６図 面素データと輪郭要素との関係図 （イ）　　　　　　　　　　　　　　　　（ロ）Ｘｎ−
Ｉ　　Ｘｎ　　　　　　　　　　　　　　ＸＴＩ−Ｉ　
　Ｘｎ第９図 実施例の構成図 １・輪部抽出部　　　　　　　１８・輪郭検出装置２・
・輪郭解析部　　　　　　　１９・・・主制御部Ｉ４・
・内部パス　　　　　　　　２ｏ・・主メモリ１５・内
部メモリ　　　　　　　２！・・・２値画像入方処理部
１６・・・パスイノタフエース　　　２２・・２値画像
入力装置１７・メインパス　　　　　　　２３・・・入
出力処理部第１０図 面素データと接続関係との成立間系図 第１１図 面素データと接続関係との成立間系図 １工１１工１ 第１２図　　　　　　第１３図 面素データの説明図　　　　　　　　　　接続フラグの
説明図コマンド列の説明図 第１５図 輪郭抽出部の回路図 第１６図 接続フラグデータの説明図 第１７図 接続フラグデータの説明図 第１８図 孤立画素のパターン説明図 （イ）　　　　　　　　　　　　　　（ロ）（ハ）　　
　　　　　　　　　（ニ） 第１９図 輪郭解析部の全体処理のフローチャー１・第２０図 更新処理のフローチャート 第２１図　　　　　第２２図 処理１のフローチャート　　　　　　処理２のフローチ
ャート第２３図 処理３のフローチャート 第２４図 更新処理と画素データの位置との関係区第２５図 従来の輪郭画素抽出Ｂ様図 第２６図 第１の輪郭ベクトル系列テーブルの説明図輪郭ベクトル
系列管理テーブルの説明図第２８図 第２の輪郭ベクトル系列テーブルの説明図巨視的及こ （ａ） （Ｃ） Ｆ微視的処理の説明図 （ｂ） Ｐ） （ｄ） ＰＩ　（ＸＩ、’／ｌ） 第３０ 格納データＣ 白黒情報を全て保存 １図 〉説明図 （ｂ） 黒丸の点だけを保存

Claims (1)

【特許請求の範囲】
1. （１）被写体をラスタスキャンして得られた黒白に対応
   する２値化画素データに基づき、黒白の境界に相当する
   輪郭を検出する装置において、縦横２画素×２画素の画
   素データをスキャンラインに沿って順次に取り出し、互
   いに隣接した２個の黒画素を結ぶベクトルに相当する輪
   郭要素と当該画素データに係る画素との接続関係を、１
   ライン前にて取り出した画素データに基づいて作成前記
   輪郭要素とこれら輪郭要素群よりなる輪郭とに対して各
   々固有の符号を付すと共に、輪郭要素毎に、その座標及
   び方向と輪郭要素が所属する輪郭の符号と輪郭要素の前
   後に夫々接続されている他の輪郭要素の符号とを記載す
   るための輪郭要素テーブルと、輪郭毎に先端及び終端に
   位置する輪郭要素の符号を記載するための輪郭管理テー
   ブルと、ラスタスキャン方向に並ぶＸ座標とその座標に
   前端または後端が位置する未接続の輪郭要素の符号とそ
   の輪郭要素の未接続端の前後端の区別とを対応させて記
   載するための輪郭接続テーブルとを格納する第１のテー
   ブル格納部と、 すると共に、前記接続関係の情報と当該画素データの黒
   白の配列パターンの情報とを含むコマンド列を作成して
   出力する輪郭抽出部と、 前記輪郭抽出部よりのコマンド列に基づいて前記第１の
   テーブル格納部内の各テーブルの記載を更新すると共に
   、輪郭要素テーブルの前記他の輪郭要素の符号の更新に
   ついては輪郭接続テーブルを参照して行い、且つ前記輪
   郭要素テーブルと輪郭管理テーブルから１輪郭画素系列
   を構成する各点のうち始点からみて極大となる点を抽出
   するとともに、抽出された連続する２点の間にある最大
   距離となる点を抽出した輪郭ベクトルを第１の輪郭ベク
   トル系列テーブルに格納する輪郭解析部と、前記輪郭解
   析部で解析された輪郭の数及び各輪郭毎の輪郭ベクトル
   数を記載するための輪郭ベクトル系列管理テーブルと、
   各輪郭毎の輪郭ベクトル系列のベクトル座標データを前
   記輪郭ベクトル系列管理テーブルの各輪郭に対応して記
   載するための第２の輪郭ベクトル系列テーブルとを格納
   する第２のテーブル格納部とを設けてなることを特徴と
   する輪郭検出装置。