JPH01100679A - 輪郭抽出方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、スキャナなどで読み取られ、計算機。

メモリに保持されるイメージデータ（文書中に見。

られるイラスト、印影９手書き文字、写真など）。

の輪郭を抽出する方法に関する。　　　　　　　１５〔
従来の技術〕 従来の装置は、時開ＢＥ　６０−”　１ｏｓｏｓ１号公
報に記。

載のように、原イメージの各画素の濃度を画素と。

とに求めるものでア夛、この種の従来装置は、メモリの
ビット・アクセスを必要とする。　　　　２゜〔発明が
解決しようとする問題点〕 上記従来技術は、ビット・アクセスの高速化に。

ついて配慮がされておらず、多大の処理時間を要・する
という問題があった。

本発明の目的は、上記ビット・アクセスでなく５゜ビッ
ト列アクセスによシ、高速な輪郭抽出方法を。

提供することにある。

〔問題点を解決するための手段〕

上記目的は、原イメージを格子状に分割して得。

られる小矩形であるセルを保持する原セル・バラ１，１
フアと、セルを９０＠回転したセルを保持する回転後。

セル・バッファと、上記原セル・バッファの内容。

を９０″回転して１回転後セル・バッファに転送する、
セル回転手段と、原セル・バッファ内の特定のビ。

ット列を一度に連続して取）出す第一のビット列＋５ 取り出し手段と１回転後セル・バッファ内の特定。

のビット列を一度に連続して取り出す第二のビット列数
シ出し手段とを設けることによシ達成される。

〔作用〕

輪郭抽出には、水平三画素（注目画素の左隣接・画素、
注目画素、注目画素の右隣接画素）と垂直三画素（注目
画素の下隣接画素、注目画素、注目・画素の上隣接画素
）へのアクセスが必要であるが、。

上記水平三画素は、上記第一のビット列数シ出し５手段
によシ、−度に取り出すことができる。また、。

上記セル回転手段は、垂直方向に連続するビット。

列を水平方向に連続するビット列に変換するので、。

上記垂直二画素は、上記第二のビット列数〕出し。

手段によ〕、−度に取り出すことができる。従う、。

て、ビット列アクセスができ、処理が高速化され。

る。

〔実施例〕

以下１本発明の一実施例を第１図により説明す。

る。第１図は本発明による一実施例の全体構成を、５示
すブロック図である。

第１図において、転送先メモリ１１０には、イメ。

−ジ・データが保持されている。上記転送先メモ。

す１１０内の一部分のイメージ・データ１２０の輪郭を
抽出して、転送先メモリ２１０内の一部分へ転送２゜、
３　。

するのであるが、この時、下記パラメータを指定・する
必要がある。

■　ｓａｄτ：転送先部分イメージ先頭アドレス　。

■　ｚｗ　　：　　　　　　　　　、　　　横軸（バイ
ト単位、）■　ｚｓｋｐｌ　：転速先アドレス・スキッ
プ長（パイ５ト単位） ■　＃Ａ　＝転送先部分イメージ高さ（ラスタ単。

位） ■　ｄａｄｒ　：部分イメージ（抽出した輪郭）転送。

先先頭アドレス　　　　　　　　　１゜■　ｄｚｋｐｌ
　：転送先アドレス・スキップ長（パイ。

ト単位） 第２図（６）、　（Ａ）　Ｋ　、上記各パラメータの説
明図を。

示す。

部分イメージ１２０の輪郭抽出は、これを横１０ド、。

ブト。縦１０ラスタの正方形領域（これを原セル′と呼
ぶ）に分割し、上記原セル単位に行なう。すなわち、第
２図において、原セルＣＪ１の輪郭を抽出し、これを輪
郭セルＣｄ１へ転送し９次ＩＣＣｓ２の輪郭を抽出し、
これを輪郭セルＣｄ２へ転送する。以．４　。

下、Ｃ８→Ｃｄｓ、Ｃｚａ→ＣｔＬａ　、と処理する（
原理・ル２輪郭セルは、左から右、上から下へと移動す
る）。

さて、ここで１輪郭抽出の原理を説明する。不メージは
白黒二値とし、黒画素の中から輪郭画素を選ぶこととす
る。また１選ばれた輪郭画素の色は黒１輪郭画素でない
画素の色は白とするものと。

する。第３図（α）は輪郭抽出すべき原イメージの例。

同図（ｂ）は、抽出した輪郭を示す。第３図から・分る
。

ように、１０ （１）原イメージのうちの白画素は１輪郭画素と。

しない。

（２）原イメージのうちの黒画素のうち、その上下、左
右の４つの隣接画素がすべて黒画素で。

ある時、その黒画素は１輪郭画素としない。、５（３）
原イメージのうちの黒画素のうち、その上。

下、左右の４つの隣接画素のいずれか一画一でも白画素
があれば、その黒画素は１輪郭磯素とする。

以上が０輪郭抽出の原理の説明である。第１■０におい
て、テーブル・メモリ１８０には、上記ルー・ルがテー
ブルとして格納されている。第４図にテ・−プル・メモ
リ１８０の構成例を示す。同図（ａ）は、・注目画素と
その隣接４画素を表わしたものであシ・。

ｂｌまたはｂ５が注目画素、　ｈｌは左隣接画素、　ｂ
５は右二隣接画累、　ｂ４は上隣接画素、　ｈ６は上隣
接画素であ・る。同図（ｈ）は、テーブル・メモリ１８
０の構成例で・あル、８バイト（＝６４ビット）で構成
される。メ。

そりの内容は。

である。なお、ハツチングを施した部分は参照し。

ないので任意でよい。本テーブル・メモリ１８０の。

参照方法は、まず、ｂｌ、　ｂｌ、　ｈｓの５ビツトの
ピッ。

ト値の組み合わせで表現される数値ｂｙｔａｄｒ　（０
＜、。

ｈｙｔａｄｒ≦７）で、テープＡ／−メモリ１８０のバ
イ′ト。

−７ドＬ／　、Ｋ　ｂｙｔａｄｒを求め１次に、４４．
　Ａｓ、　Ａ６の３゜ビットのビット値の組み合わせで
表現される数値。

ｂｉｔａｄｒ　（Ｑ≦ｈｉｔａｄｒ　≦７　）で、バイ
ト内ノヒット・アドレスｈｉｔａｄτを求める。さらに
、上記ｂｙｔαｄｒ２゜ｈｉｔａｄｒに位置するテーブ
ル・メモリ１８０内のピッ・トを取り出す。今、ｈｌ、
　ｂｌ、　ｂｓ＝１．　１．　１．　ｈａ−。

Ａｓ、　Ａ６：　０．　１　、　０．であったとすると
、　ｂｙｔａｄｒ。

＝７．　　ｂｉｔａｄｒ＝２．であシ、第４図（Ａ）に
大枠で示・したビットｂ（ビット値＝１）が取）出され
るこ５とになる。

第１図において、テーブル・メモリ１ａｏ　ｉｃは、。

第４図（Ａ）に示した値が設定されている。原セル・・
バッファ１４０は、転送先部分イメージのうちの原。

セル−個分を一時的に保持するためのセル・ノ（ツ１゜
ファでｓ、ｂ、回転後セル・バッファ１５０は、原セ。

ル・バッファ１４０に保持されている原セルを、右。

９０＠回転したセルを一時的に保持するためのセル・。

バッファである。また１輪郭セル・バッファ２００゜は
、抽出した輪郭を一時的に保持するための七へ。

・バッファである。

制御部１０は、転送先部分イメージ全体１２０の輪。

郭抽出を制御する部分である。制御部１０が些動さ。

れると１０は、原セル入力部２０．原セル回転部６０．
。

原セル輪郭抽出制御部４０１輪郭セル出力部５０を”２
０、７　。

この順序で起動する処理を転送先部分イメージ１２０内
のセル１５０の数だけ繰シ返す。第５図に処理）・ロー
を示す。

原セル入力部２０が起動されると、２０は、転送先・部
分イメージ内１２０の該当セルを原セル・バッフ５ア１
４０へ転送する。第６図（α）に転送先メモリ１２０・
内の原セルを、同図Ｃｈ）に原セル入力部２０によシ転
。

送済の原セルを示す。１バイト＝８ビツトである・から
、各セルは、こ九に合わせて横方向、縦方向。

とも同じ８ビツトのピッチで、１０ビツト、１０ラス、
。

りずつ入力する。従って、同一画素を複数回、原９セル
・バッファ１４ＯＫ入力するような画素が部分。

イメージ内に存在する。第６図（α）にハツチングを。

施した画素がこれである。またセルの横幅は１０ビ。

ットであるから、原セル・バッファ１４０の容量層。

原セル１ラスタ当）２バイトを割）当て、１０ラス。

り分、すなわち２０バイトを確保する。１ラスタ２、バ
イト（＝１６ビツト）のうちの残り６ビツトは使用しな
い。第７図に原セル入力部２０の処理フローを示す。ブ
ロック２０１０で、原セル内の１ラスク。。

φ　８　・ （＝２バイト）を転送先から転送先へ連続転送し・。

ブロック２０２０で、転送先先頭アドレスｃｓａｄｒを
。

次式によ）スキップする。

ｃｓａｄｒ　＝　ｃｚａｄｒ　−）−ｚｚｋｐｌ　＋　
（３Ｗ−２）　−−−−・・（１）　　　。

さらにブロック２０５０で、原セル内の全ラスタ（＝５
１０ラスタ）を転送したか否かを判定し、全ラスタ。

未転送の場合、再びブロック２０１０へ進み、全う。

スタ転送済の場合、原セル入力処理を終了する。。

原セル回転部３０が起動されると、５０は、原セル。

バッファ１４０に保持されている原セルを、右に９０一
回転して０回転後セル・バッファ１５０に転送する。

第８図（α）に、原セル・バッファ１４０に保持されて
。

いる原セルの各ビットの配置を、また同図Ｃｂ）に、。

回転後セル・バッファ１５０に保持される回転後セ。

ルの各ビットの配置を示す。本回転部５０は、公知、。

の方法（たとえば、特開昭６０−１４６３６７号公報）
で実現できるので、ここでは、処理フローは特に記載し
ない。

原セル輪郭抽出制御部４０が起動されると、４０は。

原セルの上下１ラスタおよび左右１ドツトを除いた部分
（第８図（α）に大枠で示した部分）の輪郭面。

素（横８ドツト＝１バイト、縦８ラスタ）を輪郭。

セル・バッファ２００に出力するように、水平５画。

素出力部６０．垂直３画素出力部７０９輪郭画累出力。

部８０．シフト・レジスタ９０２輪郭バイト出力部１０
（１，、。

の動作を制御する。その処理フローを第９図に示。

す。輪郭セルは横８ビツト×縦８ラスタ（計６４ビ。

ット）で構成されるが、その各々のビット値を、。

ビット毎に求める。走査は左→右、上→下の順に。

進める。第８図（α）の例では、ビット１２→１３→・
・：・・・１゜→１９→２２→２３→・・・・・・の順
に、ビット１２からビット。

８９までの各輪郭画素のビット値を求める。今、注。

目している画素がビット１２だとすると、第９図の。

ブロック４０１０で、注目画素の左隣接画素から３゜画
素分（ビット１１．１２．１ｇ）を原セル・バッファ１
４０からｂｙｔαｃｔｒレジスタ１６０に出力する。ブ
ロック４０２０では、注目画素の下隣接画素から３画素
分（ビット２２．１２．２　）を回転後セル・バッファ
１５０からｈｉ　ｔ　ａｄｒレジスタ１７０に出力する
。この時。

上記３画素は回転後セル・バッファから出力し。

原セル・バッファから出力しない。その理由は、・原セ
ル・バッファから出力する場合には、ビット・・アクセ
スが３画素分（３回）必要であるのに対。

して１回転後セル・バッファから出力する場合に。

は、目的の３画素が水平に連続して配置されてお５カ（
第８図（ｈ＞）３画素分まとめて１回で出力でき。

るためである。ブロック４０６０では、出力された。

上記ｈｙｔａｄｒ　、　ｈｉｔａｄｒ　、によシ、テー
プルーフ＋−Ｔ−１Ｊ。

１８０を参照して、目的の輪郭画素値１ビツトを得。

る。ブロック４０４０では、この輪郭画素値１ピツ１゜
トをシフト・レジスタ９０に取り込む。ブロック。

４０５０では、シフト・レジスタ９０に輪郭画素値が。

８ビツト（＝１バイト）分形成されたか否かを判。

定し、８ビツトに満たない場合は、注目画素を右。

に−画累分進め（今注目している画素がビット１２１゜
だとすればビット１３に進め）、再びブロック４０１０
に進む。輪郭画素値が８ビツト分形成されたら。

ブロック４０６０へ進み、シフトレジスタ９０の内容（
１バイト）を１輪郭セル・バッファ２００へ転送する。

さらにブロック４０７０で１輪郭セル８ラス、１１　。

りをすべて転送したか否かを判定し、転送済ラス・り数
が８ラスタに満たない場合は、注目画素を右・に１画素
分進め（今、注目している画素がビット・１９だとすれ
ば、ピッ）２２に進め）、再びブロック・４０１０へ進
む。転送済うスク数が８ラスタとなつ５たら処理を終了
する。

輪郭セル出力部５０が起動されると、５０は２輪郭。

セル・バッファ２００の内容を、転送先メモリ２１０゜
内の所定の輪郭セル位置へ転送する。第１０図に輪。

郭セル出力部５０の処理フローを示す。ブロック１．。

５０１０で輪郭セル・バッファ２００内の１ラヌタ（１
゜バイト）を転送先から転送先へ転送し、ブロック。

５０２０で転送先先頭アドレスｃｔｉａｄ、ｒを次式に
よシ。

スキップする。

ｃｄ、ａｔＬｒ　＝　ｃｄａｄｒ　＋　ｄｚｋｐｌ　　
　　−−・−・−−−・”　（２）　　　１゜さらにブ
ロック５０５０で輪郭セル・バッファ　２００゜内の全
テスク（８ラスタ）を転送したか否かを判。

余し、全ラスタ未転送の場合、再びブロック５０１０゜
へ進み、全ラスク転送済の場合１輪郭セル出力処６理を
終了する。

・　１２・ 以上が実施例の説明である。なお１本実施例で・は１輪
郭抽出について説明したが、抽出した輪郭・画素の画素
値をすべて白とし１輪郭画素以外の画・素値は、原イメ
ージの画素値をそのまま転送する・ようＫすれば、原イ
メージの細め処理ができる。５また。原イメージを白黒
反転し、上記細め処理を・適用すれば、原イメージの太
め処理も可能である・。

これらは、いずれも、テーブル・メモリ１８０の内・容
を変更するだけで実現できることはいうまでも・ない。

　　　　　　　　　　　　　　　　　　　　１゜〔発明
の効果〕 以上説明した如く１本発明によれば１画素ごと。

のビット・アクセスでなく、−度に複数ビットを。

取り出すビット列アクセスが可能で１Ｌ処理を。

高速化できるという効果がある。　　　　　　　１゜

【図面の簡単な説明】

第１図は本発明の一実施例の全体構成を示すブ。 ロック図、第２図は部分イメージの輪郭抽出時の。 指定パラメータの説明図、第３図は輪郭抽出の原。 理の説明図、第４図はテーブル・メモリの構成のつ。 説明図、第５図は制御部１０の処理フロー図、第６・図
は原セル入力部２０による原セルの入力範囲と、。 原セル入力後、原セル・バッファ１４０に保持され。 る原セルの説明図、＃Ｉｚ図は原セル入力部２０の処。 理フロー図、第８図は原セルと右９０°回転後のセル５
のビット配置の説明図、第９図は原セル輪郭抽出。 制御部４０の処理フロー図、第１０図は輪郭セル出力。 部５０の処理フロー図である。 １０・・・制御部、２０・・・原セル入力部、３０・・
・原セル回。 転部、４０・・・原セル輪郭抽出制御部、５０・・・輪
郭セル、。 出力部、６０・・・水平３画素出力部、７０・・・垂直
６画素。 出力部、８０・・・輪郭画素出力部、９０・・・シフト
・レジ。 スタ、１００・・・輪郭バイト出力部、１１０・・・転
送先メ。 モＩＪ、１２０・・・転送先部分イメージ、１３０・・
・原セル、。 １４０・・・原セル・バッファ、１５０・・・回転後セ
ル・ハ、５ッファ、１８０・・・テーブル・メモリ、１
９０・・・キャリーフラグ、２００・・・輪郭セル・バ
ッファ、２１０・・・転送先メモリ、２２０・・・輪郭
部分イメージ、２５０・・・輪、１５　。 第　２ 第　３ １３θ （ｂ） 図 （ｂ） Ｈ十同平例＋← 第　６ （（ＩＬ） （ｂ） 「 １＋ｕ 第　７　図 第８図 （ｂ） 第　ｑ　聞 １Ｆ）　　ｔｏ　　図

Claims (1)

【特許請求の範囲】
1. １、白黒二値イメージの輪郭を、注目画素の上下左右四
   つの隣接画素の画素値を参照することにより求める四画
   素参照による輪郭抽出方法において、原イメージを格子
   状に分割して得られる小矩形であるセルを保持する原セ
   ル・バッファと、セルを９０°回転したセルを保持する
   回転後セル・バッファと、セルの輪郭を保持する輪郭セ
   ル・バッファと、セルを原セル・バッファに取り込むセ
   ル入力手段と、原セル・バッファ内のセルを９０°回転
   して回転後セル・バッファに転送するセルの９０°回転
   手段と、注目画素の左隣接画素、注目画素、注目画素の
   右隣接画素、の水平三画素の各画素値は、原セル・バッ
   ファから一度に水平に取り込み、注目画素の下隣接画素
   、注日画素、注目画素の上隣接画素、の垂直三画素の各
   画素値は、上記回転後セル・バッファから一度に水平に
   取り込み、上記水平および垂直三画素の各画素値から、
   注目画素の画素値を求め、これを輪郭セル・バッファに
   出力する輪郭抽出手段と、上記輪郭セル・バッファの内
   容を出力する輪郭セル出力手段とを設け、上記垂直三画
   素を、上記回転後セル・バッファより一度に水平に取り
   込み、かつ原イメージ全体の輪郭抽出を、セルごとの輪
   郭抽出を繰り返すことによって行なうことを特徴とする
   輪郭抽出方法。