JPH0554139A - ２値画像の輪郭追跡方式 - Google Patents

Abstract

(57)【要約】 【目的】 ２値画像の輪郭追跡を高速に行う。 【構成】 画素の周囲８画素の白／黒各画素を判別する
ことによって、その画素の追跡方向を定義する。そし
て、この追跡方向を有する全てのパターンにパターン番
号を付与する。さらに、周囲８画素のうち、上記各パタ
ーンごとに追跡方向を定義された画素のフラグを「１」
として、８ビットの２進数および１６進数で表現する。
このとき、境界画素でない画素の追跡方向フラグは「０
０」となる。そして、上記パターン番号に対応させた追
跡方向フラグを記憶させておく。この状態で、画像の全
ての境界画素にこの追跡方向フラグを付け、追跡方向フ
ラグから境界画素を検索して起点とし、この起点から追
跡方向に添って追跡すると共に、追跡済みの境界点の追
跡方向フラグを「００」に変更して行き、全ての追跡方
向フラグが「００」になるまで追跡を行うと画像の輪郭
を求めることができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、画素の集合（ドットパ
ターン）として構成された画像（文字パターン）の輪郭
を抽出してベクトル化を自動的に行う２値画像の輪郭追
跡方式に関するものである。

【０００２】

【従来の技術】従来より、スキャナ等により読取った文
字をアウトラインデータに変換して使用したり、ＲＯＭ
等の記憶装置に格納されたドットパターンとして構成さ
れた文字パターンを拡大・縮小して使用するために、文
字パターンの輪郭をベクトル化処理している。このベク
トル化を自動的に行う２値画像の輪郭追跡方式は、従来
から種々のものが考えられている。例えば、特開昭62-1
31382 号及び特開昭64-91176号には、入力された２値画
像を縦横各２倍に拡大してから、画素が黒（１）か白
（０）かを判別して、輪郭を追跡するための起点を検索
し、さらに、この起点となる画素に接する上下左右斜め
の８画素を時計回りに調べて、画素が０から１に変化し
た方向に移動することにより、輪郭となる境界画素の中
心を追跡する方式が開示されている。

【０００３】

【発明が解決しようとする課題】従来の２値画像の輪郭
追跡方式において、２値画像を縦横各２倍に拡大してか
ら、輪郭を追跡している場合には、４倍の画像データ量
を処理しなければならず、大容量のメモリと処理時間と
を必要としていた。そして、境界画素を追跡する際に、
追跡方向に境界画素が複数あると、どちらの方向に追跡
すれば良いか迷うことがあった。また、起点を検索した
り、境界画素を追跡する際に、毎回画素が０から１に変
化する方向を調べているので、処理量が多くなり、時間
がかかるという課題があった。そこで本発明は、データ
量を少なくして処理時間を短くした２値画像の輪郭追跡
方式を提供することを目的とする。

【０００４】

【課題を解決するための手段】上記目的を達成するため
の手段として、２値画像の輪郭となる境界画素のいくつ
かを抽出してベクトル化を行う２値画像の輪郭追跡方式
において、周囲の画素に対応した追跡コードを前記２値
画像の画素に付し、この追跡コードを追跡することによ
り得られる前記境界画素を用いてベクトル化を行うこと
を特徴とする２値画像の輪郭追跡方式を提供しようとす
るものである。

【０００５】

【作用】本発明は、２値画像において、画素の周囲８画
素の有無（白黒の判別）による追跡方向のフラグを定義
し、全ての画素にこのフラグを付与して、境界画素か否
かを判別し、この境界画素に付された追跡方向フラグに
沿って追跡するものである。

【０００６】

【実施例】本発明の２値画像の輪郭追跡方式の一実施例
を図面と共に説明する。まず、黒画素の周囲８画素の白
／黒各画素を判別することによって、その黒画素から隣
接する黒画素への追跡方向を定義する。その際、追跡方
向は２方向（後述する共有点のときは４方向、境界画素
とならないときは０方向）とし、黒画素の塊の内側へは
追跡せず、かつ、１点のみで接している斜め方向の黒画
素へは追跡しないようにして、隣接する黒画素への追跡
方向を定める。即ち、図１（Ａ）に示すような黒画素か
らなる画像がある場合に、境界画素ａの追跡方向は、境
界画素ａとその周囲８画素とを示した同図（Ｂ）におい
て、方向a1,a2 となるよう定義し、黒画素の塊の内側へ
の方向であるa3〜a5の方向及び白画素への方向には追跡
しないようにする。同様に、図１（Ａ）の境界画素ｂの
追跡方向は、境界画素ｂとその周囲８画素とを示した同
図（Ｃ）において、方向b1,b2 となるよう定義し、１点
のみで接している斜め方向の黒画素（方向b3）には追跡
しないようにする。この様にして、例えば、図２（Ａ）
〜（Ｆ）に示すように画素の周囲８画素の白／黒各画素
の全てのパターンについて境界画素を追跡するように各
々２つづつの追跡方向を定義する。このとき、図２
（Ａ），（Ｃ）に示すパターンを反時計回りに９０゜回
転させたものと、図２（Ｆ），（Ｄ）に示すパターンと
が一致するので、追跡方向も一致するように、回転対象
となるパターン同志が回転して同じパターンとなったと
きに同じ追跡方向となるように定義する。

【０００７】そして、定義した追跡方向を各パターンご
とに記憶するために、全てのパターンに次のようなパタ
ーン番号を付与する。即ち、図３（Ａ）に示すように、
中心画素の番号を９として、その周囲８画素にそれぞれ
１〜８の番号を付け、その番号の各画素が黒画素である
ときのフラグを「１」とし、白画素であるときのフラグ
を「０」として、画素に付けた各番号を各ビットのケタ
として９ビットの２進数で表現し、これを１０進数に直
したものを各パターンのパターン番号とすると、全部で
０〜５１１の５１２種類のパターンが得られる（図３
（Ｂ）〜（Ｄ）に具体例を示す）。

【０００８】さらに、１〜８の番号を付けた周囲８画素
のうち、上記各パターンごとに追跡方向を定義された画
素（境界画素）のフラグを「１」として、図４（Ａ）に
示すように、画素に付けた各番号を各ビットのケタとし
て８ビットの２進数および１６進数で表現する（図４
（Ｂ）〜（Ｄ）に図３（Ｂ）〜（Ｄ）に示した各パター
ン番号における具体例を示す）。このとき、白画素は境
界画素とはならないので追跡方向は存在せず、白画素が
中心となるパターン（パターン番号０〜２５５）の追跡
方向フラグは全て「００」となる。同様に、中心が黒画
素であっても、その黒画素が境界画素でないときは、追
跡方向フラグは「００」となる。そして、上記パターン
番号に対応させてこの追跡方向を示す図５にのようなテ
ーブルをＲＯＭなどに記憶させておく。

【０００９】この様に、各パターンごとに追跡方向を定
義して記憶しておくことにより、画像の輪郭追跡を高速
に行うことができる。図６（Ａ）のような画像が入力さ
れたとき、まず、この画像の全ての画素に対して記憶し
ている追跡方向フラグを付与し、追跡方向フラグが「０
０」である画素を無視すると、境界画素だけが残る（同
図（Ｂ))。そこで、この境界画素のうち一つを起点とし
て、２方向ある追跡方向のどちらか一方の方向に隣接す
る境界画素へ移動すると共に、起点となる境界画素の追
跡方向フラグを「００」に変更する。そして、この隣接
する境界画素では、２方向ある追跡方向の一方の側から
追跡されてきたことになるので、他の方向へ追跡すると
共に、追跡方向フラグを「００」に変更する。以下同様
にして、追跡方向フラグの示す方向にしたがって追跡し
ていくと共に、追跡し終わった境界画素の追跡方向フラ
グを「００」に変更していくと、全ての追跡方向フラグ
が「００」となったとき、全ての境界画素を追跡したこ
とになる（同図（Ｃ))。

【００１０】そして、この追跡した境界画素から幾つか
を選んでベクトル化を行う。ベクトル化の方法として
は、図７（Ａ）〜（Ｃ）に示すように、境界画素とベク
トルとの距離をｄとし、その許容値をｄmax として予め
設定しておき、その許容値ｄmax より距離ｄが大きくな
らないようにして、ベクトルの折れ曲り点となる境界画
素を決めていく。例えば、同図（Ａ）のように画素ｃを
ベクトルの始点とし、画素ｆをベクトルの終点とする
と、画素ｃと画素ｆとの間の画素のうちで最もベクトル
からの距離がある画素ｅとベクトルとの距離ｄがｄ≦ｄ
max であり、同図（Ｂ）のように画素ｆを終点としたと
きの距離ｄがｄ＞ｄmax となるようなときには、画素ｆ
をベクトルの終点とし、同図（Ｃ）に示すように画素ｆ
を次のベクトルの始点として、ベクトルの終点となる画
素を検索していく。この方法では、許容値ｄmax の値を
変えることにより、データ量や要求される画像の品質に
合わせたベクトルの質を設定することができる。

【００１１】次に、境界画素が共有点である場合につい
て考える。図８（Ａ）に示すような画像の境界画素を抽
出すると、同図（Ｂ）のようになり、画素ｈは、上側の
輪郭線αと下側の輪郭線βとの両方の輪郭線を共有する
共有点となる。このとき、この共有点の追跡方向を２方
向だけ定義すると、一方の輪郭線しか追従することがで
きないので、この共有点となる画素には、４方向の追跡
方向を定義する。このとき、画素ｈとその周囲の画素を
図９（Ａ）に示し、その周囲の画素に図４（Ａ）と同様
の番号をつけると、画素ｈの追跡方向は、画素の番号
１，２，４，５の４方向となる。よって、この番号のケ
タのフラグを「１」として８ビットの２進数および１６
進数で表現すると「１Ｂ」（１６進）となる。また、図
９（Ａ）のパターン番号は、画素番号１，２，４，５，
９が黒画素であることから、「２８３」となる。したが
って、この場合、図５に示すテーブルのパターン番号２
８３の欄に「１Ｂ」のフラグを記憶させておく。

【００１２】ところが、例えば、画素番号４の方向から
共有点である画素ｈに追跡されたとき、追跡していく方
向は、画素番号１，２，５の３方向があり、どの方向に
追跡すれば良いか特定することができないので、共有点
の場合は、このテーブルだけでは不十分である。特に、
追跡方向が交差してしまうと、ベクトル化が困難とな
る。したがって、輪郭線が交差しないように直前の追跡
方向を考慮して次の追跡方向を予め決定しておく必要が
ある。そこで、図１０に示すようなテーブルを予め別に
記憶しておき、画素ｈが追跡されて、図５のテーブルに
よって、パターン番号２８３の欄の「１Ｂ」のフラグが
指定されたときは、図１０のテーブルを参照して、追跡
方向を決定するようにする。この場合、画素番号１の方
向から追跡されてきたときには、画素番号５の方向へ追
跡し、画素番号２のときは画素番号４、画素番号４のと
きは画素番号２、画素番号５のときは画素番号１と追跡
することにより、追跡方向を図９（Ｂ）のように交差す
ることなく追跡することができる。なお、共有点では、
一度目の追跡では、追跡方向フラグを「００」に変換せ
ず、２度目の追跡のときに「００」に変換する。また、
共有点は、図１１（Ａ）〜（Ｒ）に示すように全部で１
８種類であり、この１８種類の各々のパターンに対し
て、図１０と同様のテーブルを作成しておき、図５のテ
ーブルから参照されるようにしておく。なお、図１１
（Ａ）〜（Ｄ），（Ｅ）〜（Ｈ），（Ｉ）〜（Ｌ），
（Ｍ）〜（Ｐ），（Ｑ）と（Ｒ）に示すパターンは、そ
れぞれ回転対象であり、回転させて同じパターンとした
ときに、追跡方向も同じとなる（図１１（Ａ），
（Ｅ），（Ｉ），（Ｍ），（Ｑ）のみ追跡方向を示
す）。以上説明した２値画像の輪郭追跡方式を用いて境
界画素を抽出し、追跡した結果の一例を図１２（Ａ）に
示し、この境界画素とベクトルとの距離の許容値ｄmax
を１．５ドット（画素）としてベクトル化した例を同図
（Ｂ）に示す。

【００１３】

【発明の効果】本発明の２値画像の輪郭追跡方式は、入
力された画像に予め定義した追跡方向を当てはめていく
だけで境界画素を追跡することができるので、毎回追跡
方向を検索する必要はなく、処理時間が速くなる。ま
た、画素を縦横各２倍に拡大する（４倍のデータ量を扱
う）ことなく追跡することができるので、大容量のメモ
リは不要であり、処理時間もさらに速くなるという効果
がある。

【図面の簡単な説明】

【図１】（Ａ）は２値画像の一例を示す概念図であり、
（Ｂ）および（Ｃ）は本発明の２値画像の輪郭追跡方式
に使用する追跡コードの一実施例を示す概念図である。

【図２】（Ａ）〜（Ｆ）は図１に示した追跡コードの他
の実施例を示す概念図である。

【図３】（Ａ）はパターン番号を示す概念図であり、
（Ｂ）〜（Ｄ）はその一例を示す概念図である。

【図４】（Ａ）は追跡方向をフラグ化するための概念図
であり、（Ｂ）〜（Ｄ）はその一例を示す概念図であ
る。

【図５】パターン番号と追跡方向フラグの対応関係を示
す図である。

【図６】（Ａ）は２値画像の一例を示す概念図であり、
（Ｂ）はその輪郭画素を示す概念図、（Ｃ）はその輪郭
画素を追跡したものを示す概念図である。

【図７】（Ａ）〜（Ｃ）はベクトル化を説明するための
概念図である。

【図８】（Ａ）は２値画像の一例を示す概念図、（Ｂ）
はその輪郭画素を示す概念図である。

【図９】（Ａ），（Ｂ）は共有点の追跡方向を示す概念
図である。

【図１０】図９に示した共有点の追跡方向の対応関係を
示す図である。

【図１１】（Ａ）〜（Ｒ）はそれぞれ共有点の例を示す
概念図である。

【図１２】（Ａ）は２値画像を本発明の２値画像の輪郭
追跡方式の一実施例によって抽出した全境界画素を追跡
したものを示す概念図、（Ｂ）はそれをベクトル化した
一実施例を示す概念図である。

【符号の説明】

ａ〜ｃ，ｅ〜ｈ 画素

Claims (1)

【特許請求の範囲】
1. 【請求項１】２値画像の輪郭となる境界画素のいくつか
   を抽出してベクトル化を行う２値画像の輪郭追跡方式に
   おいて、 周囲の画素に対応した追跡コードを前記２値画像の画素
   に付し、この追跡コードを追跡することにより得られる
   前記境界画素を用いてベクトル化を行うことを特徴とす
   る２値画像の輪郭追跡方式。