JPS6214876B2 - - Google Patents
Info
- Publication number
- JPS6214876B2 JPS6214876B2 JP54065393A JP6539379A JPS6214876B2 JP S6214876 B2 JPS6214876 B2 JP S6214876B2 JP 54065393 A JP54065393 A JP 54065393A JP 6539379 A JP6539379 A JP 6539379A JP S6214876 B2 JPS6214876 B2 JP S6214876B2
- Authority
- JP
- Japan
- Prior art keywords
- contour
- match
- encoding method
- encoding
- value
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
- 238000000034 method Methods 0.000 claims description 45
- 238000013144 data compression Methods 0.000 claims description 5
- 238000010586 diagram Methods 0.000 description 12
- 238000007906 compression Methods 0.000 description 5
- 230000006835 compression Effects 0.000 description 5
- 230000001131 transforming effect Effects 0.000 description 2
- 230000006866 deterioration Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
Landscapes
- Image Processing (AREA)
- Image Analysis (AREA)
Description
【発明の詳細な説明】
本発明は輪郭符号化方法に関する。
2次元2値の画像情報をフアクシミリ伝送する
場合や、画像データとして電子計算機の記憶装置
に格納する場合等において、画像自体に含まれる
冗長性を除去してデータ圧縮を行なう手法は重要
である。データ圧縮の一手法としてパターンの輪
郭部に注目し、輪郭の出発点の位置と輪郭の進行
方向を符号化する輪郭符号化方式は優れた圧縮特
性をもつ。本発明はこの輪郭符号化方式において
輪郭の進行方向を符号化する際、過去の輪郭の形
状を利用し次の輪郭方向を予測する手段を用いる
ことによつて、さらに圧縮特性を向上させること
を目的とする。
場合や、画像データとして電子計算機の記憶装置
に格納する場合等において、画像自体に含まれる
冗長性を除去してデータ圧縮を行なう手法は重要
である。データ圧縮の一手法としてパターンの輪
郭部に注目し、輪郭の出発点の位置と輪郭の進行
方向を符号化する輪郭符号化方式は優れた圧縮特
性をもつ。本発明はこの輪郭符号化方式において
輪郭の進行方向を符号化する際、過去の輪郭の形
状を利用し次の輪郭方向を予測する手段を用いる
ことによつて、さらに圧縮特性を向上させること
を目的とする。
輪郭符号化方式とは、第1図のようなパターン
の輪郭情報を、輪郭先頭アドレス(X,Y)と、
その位置から黒画素を常に左(あるいは右)にみ
て輪郭線を追従しながら輪郭が進行する方向を符
号化する方式である。また第2図のように画像情
報をあらかじめm×n画素(第2図では16×16)
からなるブロツクに分割し、各ブロツク内で独立
に輪郭符号化を行なうことにより、符号化する時
の画像メモリバツフアを小さくしたり、符号のビ
ツト誤りによる再生画品質が著しく損われること
を防ぐような方式も考えられる。
の輪郭情報を、輪郭先頭アドレス(X,Y)と、
その位置から黒画素を常に左(あるいは右)にみ
て輪郭線を追従しながら輪郭が進行する方向を符
号化する方式である。また第2図のように画像情
報をあらかじめm×n画素(第2図では16×16)
からなるブロツクに分割し、各ブロツク内で独立
に輪郭符号化を行なうことにより、符号化する時
の画像メモリバツフアを小さくしたり、符号のビ
ツト誤りによる再生画品質が著しく損われること
を防ぐような方式も考えられる。
輪郭の進行方向として、パターンの輪郭部を構
成する画素の輪郭線を追従する90゜刻み屈折法
(第1図、第2図の実線の矢印)と、輪郭部を構
成する画素の中心部を追従する45゜刻み屈折法
(第1図、第2図の破線の矢印)などが考えられ
る。90゜刻み屈折法を第3図に基づいて説明す
る。黒部を常に左にみてパターンの輪郭部を構成
する黒画素の輪郭線の進行方向を第3図aのよう
に、右折、直進、左折のそれぞれに対して−1,
0,+1とした時、第1図に輪郭情報は第3図b
のようになる。ここで輪郭先頭アドレス(X,
Y)を、ライン走査を行ない最初に見つけた黒画
素とすると、輪郭の最初の方向は下向きであるこ
とは固定化されるため、輪郭情報は最初の輪郭方
向(下向き)と次の輪郭方向との関係から開始す
ればよい。また第2図のブロツクに対して適用し
た場合、第3図cのようになる。ここで(X1,
Y1),(X2,Y2),…はブロツク内のアドレスであ
り、第1図の場合と同様先頭アドレスによつて最
初の輪郭方向が固定化されるため、輪郭情報は最
初の輪郭方向と次の輪郭方向との関係から開始す
ればよい。
成する画素の輪郭線を追従する90゜刻み屈折法
(第1図、第2図の実線の矢印)と、輪郭部を構
成する画素の中心部を追従する45゜刻み屈折法
(第1図、第2図の破線の矢印)などが考えられ
る。90゜刻み屈折法を第3図に基づいて説明す
る。黒部を常に左にみてパターンの輪郭部を構成
する黒画素の輪郭線の進行方向を第3図aのよう
に、右折、直進、左折のそれぞれに対して−1,
0,+1とした時、第1図に輪郭情報は第3図b
のようになる。ここで輪郭先頭アドレス(X,
Y)を、ライン走査を行ない最初に見つけた黒画
素とすると、輪郭の最初の方向は下向きであるこ
とは固定化されるため、輪郭情報は最初の輪郭方
向(下向き)と次の輪郭方向との関係から開始す
ればよい。また第2図のブロツクに対して適用し
た場合、第3図cのようになる。ここで(X1,
Y1),(X2,Y2),…はブロツク内のアドレスであ
り、第1図の場合と同様先頭アドレスによつて最
初の輪郭方向が固定化されるため、輪郭情報は最
初の輪郭方向と次の輪郭方向との関係から開始す
ればよい。
次に45゜刻み屈折法を第4図に基づいて説明す
る。黒部を常に左にみてパターンの輪郭部を構成
する黒画素の中心部の進行方向は第4図aのよう
に、右折から左折を段階に応じて−2〜+4とし
た時(注、黒部を左にみて輪郭部の黒画素の中心
部を追従するため、右折−3に相当する進行方向
は存在しない)、第1図の輪郭情報は第4図bの
ようになる。ここで輪郭先頭アドレス(X,Y)
を、90゜刻み屈折法の場合と同様にライン走査を
行ない最初に見つけた黒画素としても、輪郭の最
初の方向は一義的に決まらないため、最初の輪郭
情報は仮の輪郭方向(下向き)と最初の輪郭方向
との関係から開始する。また第2図のブロツクに
対して45゜刻み屈折法を適用した場合、第4図c
のようになる。ここで先頭アドレスは第3図cと
同様であるが、最初の輪郭方向は固定化されない
ため、最初の輪郭情報は先頭アドレスに依存した
仮の輪郭方向(ブロツクの上境界の場合下向き、
ブロツクの右境界の場合左向き等)と最初の輪郭
方向との関係から開始する。
る。黒部を常に左にみてパターンの輪郭部を構成
する黒画素の中心部の進行方向は第4図aのよう
に、右折から左折を段階に応じて−2〜+4とし
た時(注、黒部を左にみて輪郭部の黒画素の中心
部を追従するため、右折−3に相当する進行方向
は存在しない)、第1図の輪郭情報は第4図bの
ようになる。ここで輪郭先頭アドレス(X,Y)
を、90゜刻み屈折法の場合と同様にライン走査を
行ない最初に見つけた黒画素としても、輪郭の最
初の方向は一義的に決まらないため、最初の輪郭
情報は仮の輪郭方向(下向き)と最初の輪郭方向
との関係から開始する。また第2図のブロツクに
対して45゜刻み屈折法を適用した場合、第4図c
のようになる。ここで先頭アドレスは第3図cと
同様であるが、最初の輪郭方向は固定化されない
ため、最初の輪郭情報は先頭アドレスに依存した
仮の輪郭方向(ブロツクの上境界の場合下向き、
ブロツクの右境界の場合左向き等)と最初の輪郭
方向との関係から開始する。
さて第3図b,c,第4図b,cの輪郭情報を
符号化する場合、従来は個々の輪郭進行情報に対
して個々の符号を割り当てるのが一般的であつ
た。この際、それぞれの進行方向の出現頻度の統
計的性質を利用して、出現頻度の多いものには短
かい符号長の符号を、出現頻度の少ないものには
長い符号長の符号をあらかじめ割り当て、総符号
長の圧縮効率の向上を図る方式が知られている。
たとえば90゜刻み屈折法に対しては第5図、45゜
刻み屈折法に対しては第6図のような符号割り当
てが行なわれる。また第7図のように輪郭進行情
報を複数個組み合わせて符号化することによりさ
らに圧縮効率を上げる方式が考えられている。
符号化する場合、従来は個々の輪郭進行情報に対
して個々の符号を割り当てるのが一般的であつ
た。この際、それぞれの進行方向の出現頻度の統
計的性質を利用して、出現頻度の多いものには短
かい符号長の符号を、出現頻度の少ないものには
長い符号長の符号をあらかじめ割り当て、総符号
長の圧縮効率の向上を図る方式が知られている。
たとえば90゜刻み屈折法に対しては第5図、45゜
刻み屈折法に対しては第6図のような符号割り当
てが行なわれる。また第7図のように輪郭進行情
報を複数個組み合わせて符号化することによりさ
らに圧縮効率を上げる方式が考えられている。
本発明は、この輪郭情報の符号化に際して、輪
郭がもつ曲率の性質を利用して、さらに圧縮効率
を上げるものである。
郭がもつ曲率の性質を利用して、さらに圧縮効率
を上げるものである。
以下本発明の一実施例を図面に基づいて説明す
る。まず符号化するために次の輪郭方向を予測し
ようとしている近傍の曲率ρを次の式で定義す
る。
る。まず符号化するために次の輪郭方向を予測し
ようとしている近傍の曲率ρを次の式で定義す
る。
ここでd-iは既知となつた過去の進行方向を上
記に説明したように数値化した値であり、またw
-iはそれぞれのd-iに対する重み関数であり、近
傍をより重視するために、 0≦w-(i+1)≦w-i≦w0=1 という性質をもたせる。
記に説明したように数値化した値であり、またw
-iはそれぞれのd-iに対する重み関数であり、近
傍をより重視するために、 0≦w-(i+1)≦w-i≦w0=1 という性質をもたせる。
そこで次の輪郭方向を予測する第1図の方法に
ついて説明する。多くのパターンでは巨視的にみ
て輪郭の大部分が曲率0すなわち直線的であるこ
とを利用して とし、これを変形して次の輪郭進行方向の予測値
<d0>の計算式(2)を得ることができる。ただし
w0=1とする。
ついて説明する。多くのパターンでは巨視的にみ
て輪郭の大部分が曲率0すなわち直線的であるこ
とを利用して とし、これを変形して次の輪郭進行方向の予測値
<d0>の計算式(2)を得ることができる。ただし
w0=1とする。
符号化する場合、(2)式によつて求められた次の
輪郭進行方向の予測値<d0>が実際の輪郭進行方
向に最も近かつた場合、一致したことを示す1ビ
ツト(たとえば0)、また一致しなかつた場合、
一致しなかつたことを示す1ビツト(たとえば
1)とそれに続けて予測値と実際の値との差を符
号化したものを付加する。
輪郭進行方向の予測値<d0>が実際の輪郭進行方
向に最も近かつた場合、一致したことを示す1ビ
ツト(たとえば0)、また一致しなかつた場合、
一致しなかつたことを示す1ビツト(たとえば
1)とそれに続けて予測値と実際の値との差を符
号化したものを付加する。
ここで90゜刻み屈折法に対してこの方法を適用
した例について述べる。(2)式でw-1=1,w-i=
0(i≧2)とすると <d0>=−d-1 となり、符号割り当ては第8図aのようなものと
なり、一致した時は0,一致しなかつた時は11ま
たは10の符号化した値で表わされる。第3図bの
輪郭情報は第8図bのように符号化され、第5図
による符号化に比べ総符号長が短縮される。
した例について述べる。(2)式でw-1=1,w-i=
0(i≧2)とすると <d0>=−d-1 となり、符号割り当ては第8図aのようなものと
なり、一致した時は0,一致しなかつた時は11ま
たは10の符号化した値で表わされる。第3図bの
輪郭情報は第8図bのように符号化され、第5図
による符号化に比べ総符号長が短縮される。
ここで第5図の符号を第8図aの符号に変換す
る回路実施例を第9図に示す。第5図の符号はク
ロツク(CLK)に同期して本回路のI1,I0に入力
される。ただし直進に対応する符号は1ビツトで
あるためI1=0,I0=x(0,1のどちらでもよ
い)とする。この入力符号(I1,I0)はクロツク
(CLK)により2個のフリツプフロツプ(F/
F)に一時的に記憶され、次の符号と共に読出し
専用メモリ(ROM)のアドレス線(a3〜a0)に入
力される。ROMの内容を第9図bのようにして
おけば、ROMからの出力信号(O1,O0)とし
て、第8図aに対応する符号を得ることができ
る。ただしO1=0の時はO0は意味をもたないも
のとする。
る回路実施例を第9図に示す。第5図の符号はク
ロツク(CLK)に同期して本回路のI1,I0に入力
される。ただし直進に対応する符号は1ビツトで
あるためI1=0,I0=x(0,1のどちらでもよ
い)とする。この入力符号(I1,I0)はクロツク
(CLK)により2個のフリツプフロツプ(F/
F)に一時的に記憶され、次の符号と共に読出し
専用メモリ(ROM)のアドレス線(a3〜a0)に入
力される。ROMの内容を第9図bのようにして
おけば、ROMからの出力信号(O1,O0)とし
て、第8図aに対応する符号を得ることができ
る。ただしO1=0の時はO0は意味をもたないも
のとする。
さらに90゜刻み屈折法に対して(2)式を適用した
他の例について述べる。(2)式でW-1=W-2=1,
w-3=1/2,w−i=0(i≧4)とすると <d0>=−(d-1+d-2+d-3/2) となり、符号割り当ては第10図aのようなもの
となる。第3図bの輪郭情報は第10図bのよう
に符号化され、第8図bによる符号化に比べさら
に総符号長が短縮される。
他の例について述べる。(2)式でW-1=W-2=1,
w-3=1/2,w−i=0(i≧4)とすると <d0>=−(d-1+d-2+d-3/2) となり、符号割り当ては第10図aのようなもの
となる。第3図bの輪郭情報は第10図bのよう
に符号化され、第8図bによる符号化に比べさら
に総符号長が短縮される。
次に輪郭方向を予測する第2の方法について説
明する。多くのパターンでは巨視的にみて輪郭の
曲率が急変することが少ないことを利用して、 とし、これを変形して次の輪郭進行方向の予測値
<d0>の計算式(3)を得ることができる。ただし
w0=1とする。
明する。多くのパターンでは巨視的にみて輪郭の
曲率が急変することが少ないことを利用して、 とし、これを変形して次の輪郭進行方向の予測値
<d0>の計算式(3)を得ることができる。ただし
w0=1とする。
<d0>=Σ(w−(i-1)−w−i)d-i…(3)
符号化する場合は第1の方法と同様に、(3)式に
よつて求められた予測値<d0>が実際の輪郭進行
方向に最も近かつた場合、一致したことを示す1
ビツト(たとえば0)、または一致しなかつた場
合、一致しなかつたことを示す1ビツト(たとえ
ば1)とそれに続けて予測値と実際の値との差を
符号化したものを付加する。この方法によれば以
前の曲率を保存しようとする輪郭進行方向を予測
するため、大きなデータ圧縮効率の向上を見込む
ことができる。
よつて求められた予測値<d0>が実際の輪郭進行
方向に最も近かつた場合、一致したことを示す1
ビツト(たとえば0)、または一致しなかつた場
合、一致しなかつたことを示す1ビツト(たとえ
ば1)とそれに続けて予測値と実際の値との差を
符号化したものを付加する。この方法によれば以
前の曲率を保存しようとする輪郭進行方向を予測
するため、大きなデータ圧縮効率の向上を見込む
ことができる。
以上説明してきたように、本発明は輪郭符号化
方式に対して輪郭線のもつ性質を利用した輪郭進
行方向の予測手法を用いるので、より一層のデー
タ圧縮効果を得ることができる。
方式に対して輪郭線のもつ性質を利用した輪郭進
行方向の予測手法を用いるので、より一層のデー
タ圧縮効果を得ることができる。
第1図、第2図は輪郭符号化方式を説明する
図、第3図は輪郭符号化方式の1つである90゜刻
み屈折法を説明する図、第4図は輪郭符号化方式
の他の1つである45゜刻み屈折法を説明する図、
第5図は90゜刻み屈折法の符号割り当て例を説明
する図、第6図は45゜刻み屈折法の符号割り当て
例を説明する図、第7図はデータ圧縮効率を改善
する目的で第5図の進行方向を2つ組にした従来
例を説明する図、第8図aは90゜刻み屈折法に本
発明の輪郭進行方向予測手法を適用した例の符号
化した値を説明する図、第8図bは第3図bの輪
郭情報を符号化した値を説明する図、第9図aは
第8図の回路実施例を示すブロツク図、第9図b
は該回路に使用されるROMの内容を説明する
図、第10図a,bは90゜刻み屈折法に本発明の
輪郭進行方向予測手法を適用した他の例を説明す
る図である。
図、第3図は輪郭符号化方式の1つである90゜刻
み屈折法を説明する図、第4図は輪郭符号化方式
の他の1つである45゜刻み屈折法を説明する図、
第5図は90゜刻み屈折法の符号割り当て例を説明
する図、第6図は45゜刻み屈折法の符号割り当て
例を説明する図、第7図はデータ圧縮効率を改善
する目的で第5図の進行方向を2つ組にした従来
例を説明する図、第8図aは90゜刻み屈折法に本
発明の輪郭進行方向予測手法を適用した例の符号
化した値を説明する図、第8図bは第3図bの輪
郭情報を符号化した値を説明する図、第9図aは
第8図の回路実施例を示すブロツク図、第9図b
は該回路に使用されるROMの内容を説明する
図、第10図a,bは90゜刻み屈折法に本発明の
輪郭進行方向予測手法を適用した他の例を説明す
る図である。
Claims (1)
- 【特許請求の範囲】 1 2次元2値画像情報のパターン輪郭部に注目
し、その輪郭の出発点の位置と輪郭の進行方向を
符号化することによつて画像情報に含まれる冗長
を取除き、データ圧縮を図る方法において、輪郭
の進行方向を、直進に対しては0,左折に対して
はその角度に比例した正(または負)の数値、お
よび右折に対しては同様に角度に比例した負(ま
たは正)の数値、あるいはこれら3者に対して一
定値を加えたものをそれぞれ割り当てて数値化
し、順次符号化していく際、パターンの輪郭線の
もつ統計的性質を利用して、過去の進行方向
d−1,d−2,……から次式 f(d−1,d−2,……) を計算し、これに最も近い値d0を次の方向として
予測し、これが実際の方向と一致した場合には一
致したことを示す1ビツトの情報(たとえば
0)、また一致しなかつた場合には一致しなかつ
たことを示す1ビツトの情報(たとえば1)とそ
れに続けて予測値と実際の値との差を符号化した
ものを付加し、輪郭情報をデータ圧縮することを
特徴とする輪郭符号化方法。 2 多くのパターンでは巨視的にみて輪郭の大部
分が曲率0すなわち直線的であることを利用し
て、 w-i:過去の進行方向に対する重み 関数で0≦w-(i+1)≦w-i≦1 とすることを特徴とする特許請求の範囲第1項記
載の輪郭符号化方法。 3 多くのパターンでは巨視的にみて輪郭の曲率
が急変することが少ないことを利用して、 w-i:過去の進行方向に対する重み 関数で0≦w-(i+1)≦w-i≦w0=1 とすることを特徴とする特許請求の範囲第1項記
載の輪郭符号化方法。 4 w-1=1,w-i=0(i≧2) とすることを特徴とする特許請求の範囲第2項記
載の輪郭符号化方法。 5 w-1=w-2=1,w-3=0.5w-i=0(i≧
4) とすることを特徴とする特許請求の範囲第2項記
載の輪郭符号化方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6539379A JPS55157076A (en) | 1979-05-25 | 1979-05-25 | Profile coding method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP6539379A JPS55157076A (en) | 1979-05-25 | 1979-05-25 | Profile coding method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS55157076A JPS55157076A (en) | 1980-12-06 |
| JPS6214876B2 true JPS6214876B2 (ja) | 1987-04-04 |
Family
ID=13285704
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP6539379A Granted JPS55157076A (en) | 1979-05-25 | 1979-05-25 | Profile coding method |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS55157076A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03274020A (ja) * | 1990-03-23 | 1991-12-05 | Nippon Seiki Co Ltd | 液晶表示装置 |
-
1979
- 1979-05-25 JP JP6539379A patent/JPS55157076A/ja active Granted
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03274020A (ja) * | 1990-03-23 | 1991-12-05 | Nippon Seiki Co Ltd | 液晶表示装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS55157076A (en) | 1980-12-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7221483B2 (en) | Image encoding method and apparatus, image decoding method and apparatus, image processing apparatus, image formation apparatus, and computer-executable programs | |
| JP3108479B2 (ja) | 符号化復号化方法およびその装置 | |
| JP3364074B2 (ja) | ビットプレーン符号化装置 | |
| JPH09135358A (ja) | 算術符号を用いた画像符号化装置 | |
| JP2009509404A (ja) | 移動物体境界のための適応影響エリアフィルタ | |
| CN115914640A (zh) | 一种用于车联网的数据压缩方法 | |
| JP2000513195A (ja) | データ圧縮のための方法及び装置 | |
| KR20030071019A (ko) | 3차원 메쉬 영상의 점진적 부호화 방법 | |
| US6909746B2 (en) | Fast robust data compression method and system | |
| JPS5929020B2 (ja) | 2次元ブロック符号化方法 | |
| JP3139460B2 (ja) | 2値文書画像の符号化方法および符号化装置 | |
| JPH0723238A (ja) | 画像データ圧縮及び復元装置 | |
| JPH1098620A (ja) | 画像処理装置 | |
| JP2537246B2 (ja) | 画像符号化方式 | |
| JP3111958B2 (ja) | パタン符号化を用いた符号化装置及び符号化方法 | |
| JPH0123034B2 (ja) | ||
| JP2513654B2 (ja) | 画像符号化装置 | |
| JP3481644B2 (ja) | 画像圧縮装置 | |
| JPH0993440A (ja) | 多値画像処理装置 | |
| JP2001268369A (ja) | 画像データ符号化装置、画像データ符号化方法、記録媒体及び画像形成装置 | |
| JP3085017B2 (ja) | 符号化装置及び復号化装置 | |
| JPS6318384B2 (ja) | ||
| JP2002218250A (ja) | 画像符号化装置および画像符号化方法および記録媒体 | |
| JPH09121286A (ja) | 画像データの圧縮方法及び装置 | |
| JPH0727400B2 (ja) | 学習型ベクトル量子化器 |