JPH0789376B2 - ディジタル輪郭線の符号化方法 - Google Patents

Description

【発明の詳細な説明】 ＜産業上の利用分野＞ 本発明は、例えばファクシミリ等の入力装置から読み込
まれたディジタル図形の画像データにおけるディジタル
輪郭線の符号化方法に関するものである。

＜従来の技術＞ ファクシミリ等から読み込まれたディジタル図形におけ
る、黒画素領域の最外郭の部分である輪郭線を抽出する
ことは、そのディジタル図形の特徴を記述するためにき
わめて重要な２次元情報となる。このとき、大量のディ
ジタル輪郭線データを限られた記憶装置上に蓄積する、
あるいは伝送するためには、ディジタル輪郭線データに
符号化を施してデータ量を圧縮する必要がある。

このようなディジタル輪郭線の符号化法として第８図
（ａ），（ｂ）に表わす、Freemanのチェイン符号化法
が従来より知られている。

この方法は、ディジタル輪郭線の１画素を中心として、
第８図（ａ）に示す矢印０〜７の８方向に画素を追跡
し、符号化を行なうものである。このチェイン符号は、
ディジタル輪郭線を構成する画素１個に対し、８個の記
号で表わされるので、１リンク（連結した２個の画素の
組）当たりの符号化ビット数は３ビットとなる。

例えば、第８図（ｂ）に示すようなディジタル輪郭線の
符号化は、始点座標p_sより“007010776545654544233221
2"と表わされる。

しかしながら、このようなチェイン符号化法では、例え
ば細かな曲折の少ない輪郭線を記述する場合等、ディジ
タル輪郭線を忠実に記述する必要のない場合に、ディジ
タル輪郭線を１画素ずつ符号化（３ビット）していくた
め無駄があり、符号化効率を１リンク当たり３ビット以
下に向上させることはできない。

＜発明が解決しようとする問題点＞ 本発明が解決しようとする問題点は、ディジタル輪郭線
を忠実に記述する必要がない場合に、符号化効率を向上
させることであり、本発明の目的は、チェイン符号化法
より有効なディジタル輪郭線の符号化方法を実現するこ
とを目的とする。

＜問題を解決するための手段＞ 上記した問題を解決する本発明の概要は、次の通りであ
る。

ディジタル図形の画像データが格納された画像メモリ部
と、このディジタル図形の輪郭線抽出・符号化アルゴリ
ズムとこの符号化の結果を格納する主メモリ部と、レジ
スタ群を有し輪郭線抽出・符号化アルゴリズム及び数値
演算を実行するプロセッサ部とを具備し、輪郭線を忠実
に記述する必要のない場合のディジタル輪郭線の符号化
方法であって、 （イ）ディジタル図形の１点を始点として主メモリ部に
格納し１画素単位に順次追跡を行う工程と、 （ロ）追跡点の内より予め設定された画素抽出間隔に基
づいて抽出点を決定する工程と、 （ハ）前記画素抽出間隔をｎ（≧２）とするとき2^k-1≦
ｎ＜2^kを満足する正整数ｋを求めてこれよりセグメント
長ｄ＝ｋ＋１を前記主メモリ部に設定する工程と、 （ニ）現在の抽出点と１つ前の抽出点との差分ベクトル
を求めてそのX,Y成分を、前記画素抽出間隔ｎの値で決
定されるセグメント長ｄに対応するビット数で１つのセ
グメントとして主メモリ部内に格納する工程と、 （ホ）工程（ニ）を追跡点が始点に戻るまで繰り返す工
程と、 （ヘ）始点の座標、セグメントの数、セグメント長及び
各セグメントの差分ベクトルのX,Y成分からなる符号化
列のデータ・フォーマットをディジタル輪郭線の符号化
情報とする工程と を有することを特徴とするディジタル輪郭線の符号化方
法である。

＜作用＞ 本発明のディジタル輪郭線の符号化方法は、１画素単位
に順次追跡を行ない、予め設定された画素抽出間隔に基
づいて抽出点を決定し、現在の抽出点と１つ前の抽出点
との差分ベクトルを求めてそのX,Y成分をディジタル輪
郭線の符号化情報とする。

＜実施例＞ 本発明の方法を実現するのに好適な装置の例を第１図に
構成ブロック図として示す。

この図において、１はファクシミリ等の入力装置から読
み込まれたディジタル画像の図形データを格納する画像
メモリ部、２はディジタル輪郭線の抽出・符号化アルゴ
リズム及びその符号化結果等を格納する主メモリ部、３
は数値演算及びディジタル輪郭線の抽出・符号化アルゴ
リズムを実行するプロセッサ3₁とその結果を一時格納す
るレジスタ群3₂よりなるプロセッサ部であり、画像メモ
リ部１、主メモリ部２、プロセッサ部３はシステム・バ
スSBに相互に接続され、プロセッサ部３は画像メモリ部
１、主メモリ部２にアクセス可能である。

本発明が取り扱う対象は第４図に示すような画像メモリ
部１におけるディジタル画像のディジタル輪郭線であ
り、画面の左から右へＸ成分（０≦Ｘ≦Ｍ）、画面の上
から下へＹ成分（０≦Ｙ≦Ｎ）を有し、各画素は座標
（X,Y）で参照できるものである。但し、X,Y,M,Nは非負
の整数である。

次に、第５図（ａ），（ｂ）を用いて本発明の符号化方
法の原理を説明する。

従来の符号化法は第８図（ａ），（ｂ）に示したよう
に、ディジタル輪郭線を１画素単位に追跡し、抽出して
符号化していたが、本発明の方法は第５図（ａ），
（ｂ）に示すように、画素の追跡は１画素単位に行なう
が、抽出は予め設定された画素抽出間隔に基づいて行な
い（P_s,P_1n,P_2n,…P_l-1n）、現在の抽出点P_jnと１つ前
の抽出点P_j-1nとの差分ベクトルa_j（a₁,a₂,…,a_l）を求
め、このX,Y成分（ΔX_j,ΔY_j）（１≦ｊ≦l,P_0n＝P_s）
を符号化情報として用いる。

以下に、本発明のディジタル輪郭線の符号化方法の工程
手順（アルゴリズム）を第２図のフローチャートを用い
て詳しく説明する。

（１）はじめに、画像メモリ部１上をスキャンして、最
上行かつ最左側の黒画素の点をディジタル図形の輪郭線
上の１点として抽出し、始点P_sとする。

（２）始点P_sの座標値（X_s,Y_s）をレジスタRX_s,RY_sにそ
れぞれ格納するとともに、主メモリ部２に格納する。

（３）ディジタル輪郭線の画素抽出間隔をｎ（≧２）と
するとき、2^K-1≦ｎ＜2^kを満足する正整数ｋを求め、セ
グメント長ｄ＝ｋ＋１として主メモリ部２に格納する。

（４）レジスタRX_s,RY_sの内容をレジスタRX_a,RY_aにそれ
ぞれセットする。

（５）レジスタｉに初期値０をセットする。

（６）セグメント数をカウントするレジスタｌに初期値
０をセットする。

（７）レジスタCNTRに初期値ｎ−１をセットする。ｎの
値は追跡点（画素）抽出間隔である。

（８）点P_i（X_i,Y_i）を輪郭線上の現在の追跡点とする
とき、次の追跡点P_i+1を求め、その座標値（X_i+1,
Y_i+1）をレジスタRX,RYにそれぞれ格納する。この輪郭
線の抽出法は、従来の例に挙げた３×３のマスクを用い
る方法、２×２のマスクを用いる方法等があるが、ここ
では８連結の形で輪郭線を抽出するものとする。

（９）レジスタｉの内容に１を加算する。

（10）レジスタRX,RYの内容からレジスタRX_s,RY_sの内容
を減算することにより、追跡点P_i+1と始点P_sとの距離D
X,DYをそれぞれ求める。

（11）DX,DYの値をチェックし、DX＝DY＝０の場合
｛Ｙ｝は（17）ステップに進み、DX＝DY＝０でない場合
｛Ｎ｝は（12）ステップに進む。

（12）レジスタCNTRの内容から１を減算する。

（13）レジスタCNTRの内容をチェックし、CNTR＝０でな
い場合｛Ｎ｝は（８）ステップからの操作を繰り返し、
CNTR＝０の場合｛Ｙ｝は（14）ステップを実行する。

（14）現在の抽出点P_i+1の座標値が格納されているレジ
スタRX,RYの内容から、前回の抽出点の座標値が格納さ
れているレジスタRX_a,RY_aの内容を減算し、現在の抽出
点と１つ前の抽出点との差分ベクトルa_i（ΔX,ΔＹ）を
求め、主メモリ部２に格納する。ここで、求めた差分ベ
クトルa_iの成分ΔX,ΔＹは各々（３ステップで求めたセ
グメント長ｄに対応するビット数で、主メモリ部２上に
て１つのセグメントとして格納する。

（15）現在の抽出点の座標値P_i+1が格納されているレジ
スタRX,RYの内容をレジスタRX_a,RY_aにそれぞれセットす
る。

（16）レジスタｌの内容に１を加算し、ステップ（７）
からの操作を繰り返す。

一方、（11）において、DX＝DY＝０の場合｛Ｙ｝は、デ
ィジタル輪郭線が閉じたことを意味し、（17）ステップ
を実行する。

（17）始点座標値P_sが格納されているレジスタRX_s,RY_s
の内容から、最終抽出点の座標値が格納されているレジ
スタRX_a,RY_aの内容をそれぞれ減算することにより、最
後の抽出点との差分ベクトルのX,Y成分をそれぞれ求
め、主メモリ部１に格納する。但し、このとき、RX＝RX
_s,RY＝RY_sである。

（18）レジスタｌの内容を１加算する。

（19）レジスタｌの内容をセグメント数として主メモリ
部２に格納する。

（20）操作終了（END）。

以上の手順に従って本発明の方法は実行される。

このようにして、本発明の方法によって得られた符号化
列のデータ・フォーマットは第３図に示すようになる。

符号化列は、ディジタル輪郭線の始点座標値P_s（X_s,
Y_s），セグメント数l,セグメント長ｄ（＝ｋ＋１）及び
第１から第ｌまでの差分ベクトル（ΔX_j,ΔY_j）（ｊ＝
1,2,…,l）の値により構成される。また、差分ベクトル
（ΔX_j,ΔY_j）は、２の補数形式で表現される。

ここで、 始点座標値P_sを表わす符号化ビット数をC_s、 セグメント数ｌを表わす符号化ビット数をCl、 セグメント長ｄを表わす符号化ビット数をCd、 各セグメントの差分ベクトル（ΔX_j,ΔY_j）を表わす符
号化ビット数をＣ_Δ とすると、本発明の方法によるｌ個のセグメントからな
るディジタル輪郭線の符号化ビット数Ｃは、 Ｃ＝C_S＋C_l＋C_d＋Ｃ_Δ・ｌ で表わされる。

また、Ｃ_Δ＝2dであるから、 Ｃ＝C_S＋C_l＋C_d＋2d・ｌ となる。一般に、 C_S＋C_l＋C_d≪2d・ｌ であるから、 Ｃ≒2d・ｌ となる。

一方、ディジタル輪郭線の総構成画素数をＬ、Ｌを表わ
す符号化ビット数をC_Lとすると、従来のチェイン符号化
法の符号化ビット数C_fは、 C_f＝C_S＋C_L＋3L で表わされ、一般に、 C_S＋C_L≪3L であるから、 C_f≒3L となる。

ここに、 ｌ≒L/n（2^k-1≦ｎ＜2^k,d＝ｋ＋１） であるから、チェイン符号化法と、本発明の方法による
符号化ビット数の比C/C_fは、 C/C_f≒2d・l/3L ＝2d/3n ＝２（ｋ＋１）/3n となる。

例えば、ｎ＝３の場合、ｄ＝３であるから、 C/C_f＝2/3 となり、チェイン符号化法と本発明の方法による符号化
法とを比較すると、符号化ビット数を2/3程度に圧縮す
ることができる。

即ち、１リンク当たりの符号化ビット数を従来必要であ
った３ビットから２ビット程度に圧縮することができ
る。

第６図（ａ），（ｂ）に本発明の方法を実際に用いて差
分ベクトルを求めた抽出例を表わす。

第６図（ａ）はディジタル輪郭線に対して、始点P
_s（X_s,Y_s）より抽出間隔ｎ＝３とし、抽出点P₁₃,P₂₃,
…,P₁₁₃を求め、更にこれらの抽出点の差分ベクトルa₁,
a₂,…,a₁₂を求めた例である。

第６図（ａ）で求めた各差分ベクトルの成分の値は、主
メモリ部２内に第６図（ｂ）示すデータ・フォーマット
で格納される。

即ち、始点座標値P_s（X_s,Y_s）、セグメント数ｌ＝12、
セグメント長ｄ＝３、差分ベクトルa_j（ｊ＝1,2,…,1
2）のX,Y成分の値より構成される。但し、差分ベクトル
の各成分の値は２の補数形式で表わされる。

次に、この符号化情報に従って、復号を行なった結果を
第７図に示す。

復号は、始点座標P_s（X_s,Y_s）を出発点としてセグメン
ト長ｄより差分ベクトルa_jのX,Y成分をセグメント数ｌ
だけ、順次切り出して、その都度差分ベクトルより近似
ベクトルを計算してこの近似ベクトルに対応する線図形
を輪郭線として再現すれば良い。

第７図において、それぞれのブロックは輪郭線として再
現したものであり、点線で示すブロックは原図形の画素
を表わし、斜線を施したブロックは原図形からずれた画
素を表わしている。

以上のように、本発明の方法によれば、ディジタル輪郭
線を忠実に記述する必要がない場合に、符号化ビット数
を削減することができる。

＜発明の効果＞ 本発明のディジタル輪郭線の符号化方法は、１画素単位
に順次追跡を行ない、予め設定された画素抽出間隔に基
づいて抽出点を決定し、現在の抽出点と１つ前の抽出点
との差分ベクトルを求めてそのX,Y成分をディジタル輪
郭線の符号化情報とするので、ディジタル輪郭線を忠実
に記述する必要がない場合に符号化効率を向上させるこ
とができる。

本発明によれば、画素抽出間隔ｎより2^k-1≦ｎ＜2^kとな
る整数ｋを求めてセグメント長ｄ＝ｋ＋１を決定して、
差分ベクトルのX,Y成分をそれぞれこのビット長さｄで
格納するため、値ｄで決まる符号化列のデータ・フォー
マットの長さは画素抽出間隔ｎに対応した符号化情報と
することができ、従来のチェイン符号化方法よりも符号
化効率の高い符号化方法を実現できる。

更に、画素抽出間隔ｎを大きくすればもとのディジタル
輪郭線を粗く近似でき、画素抽出間隔ｎを小さくすれば
もとのディジタル輪郭線を細かく近似することができ
る。このように、ディジタル輪郭線の複雑さ、または所
望の近似度に応じた差分ベクトルによる符号化方法を実
現できる。

例えば、画素を追跡する際の画素抽出間隔を３とすれ
ば、１リンク（連結した２つの画素の組）当たりのビッ
ト数を３ビットから２ビット程度に圧縮できる。

また、復号は、始点座標、セグメント数、セグメント
長、差分ベクトルの情報より近似ベクトルに対応する線
図形を再現することにより、簡単に行なうことができ
る。

【図面の簡単な説明】

第１図は本発明のディジタル輪郭線の符号化方法を実施
するための装置の構成ブロック図、第２図は本発明のデ
ィジタル輪郭線の符号化方法の工程手順（アルゴリズ
ム）を表わすフローチャート、第３図は本発明の方法に
よって得られたデータのフォーマットを表わす図、第４
図は本発明の方法が対象とする図形を表わす図、第５図
（ａ），（ｂ）は本発明の方法の原理を説明するための
図、第６図（ａ），（ｂ）は本発明の方法を実際の図形
に適用した際の図、第７図は本発明の方法によって得ら
れたデータにより復号を行なった結果を表わす図、第８
図（ａ），（ｂ）は従来のチェイン符号化法を説明する
ための図である。 １……画像メモリ部、２……主メモリ部、３……プロセ
ッサ部、3₁……プロセッサ、3₂……レジスタ群。

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｇ０６Ｆ 15/66 ４１０

Claims (1)

【特許請求の範囲】
1. 【請求項１】ディジタル図形の画像データが格納された
   画像メモリ部と、このディジタル図形の輪郭線抽出・符
   号化アルゴリズムとこの符号化の結果を格納する主メモ
   リ部と、レジスタ群を有し前記輪郭線抽出・符号化アル
   ゴリズム及び数値演算を実行するプロセッサ部とを具備
   し、前記輪郭線を忠実に記述する必要のない場合のディ
   ジタル輪郭線の符号化方法であって、 （イ）前記ディジタル図形の１点を始点として前記主メ
   モリ部に格納し１画素単位に順次追跡を行う工程と、 （ロ）追跡点の内より予め設定された画素抽出間隔に基
   づいて抽出点を決定する工程と、 （ハ）前記画素抽出間隔をｎ（≧２）とするとき2^k-1≦
   ｎ＜2^kを満足する正整数ｋを求めてこれよりセグメント
   長ｄ＝ｋ＋１を前記主メモリ部に設定する工程と、 （ニ）現在の抽出点と１つ前の抽出点との差分ベクトル
   を求めてそのX,Y成分を、前記画素抽出間隔ｎの値で決
   定される前記セグメント長ｄに対応するビット数で１つ
   のセグメントとして前記主メモリ部内に格納する工程
   と、 （ホ）前記工程（ニ）を追跡点が前記始点に戻るまで繰
   り返す工程と、 （ヘ）前記始点の座標、前記セグメントの数、前記セグ
   メント長及び各セグメントの差分ベクトルのX,Y成分か
   らなる符号化列のデータ・フォーマットをディジタル輪
   郭線の符号化情報とする工程と を有することを特徴とするディジタル輪郭線の符号化方
   法。