JPH1127679A

JPH1127679A - 画像符号化装置

Info

Publication number: JPH1127679A
Application number: JP17335697A
Authority: JP
Inventors: Kazuhiro Suzuki; 一弘鈴木; Taro Yokose; 太郎横瀬; Shinji Shishido; 信次宍戸
Original assignee: Fuji Xerox Co Ltd
Current assignee: Fujifilm Business Innovation Corp
Priority date: 1997-06-30
Filing date: 1997-06-30
Publication date: 1999-01-29
Anticipated expiration: 2017-06-30
Also published as: JP3855376B2

Abstract

(57)【要約】【課題】短い符号語長を割り当てられている複数の予
測部が同一の、かつ誤った予測を行うときに生じる冗長
度をなくして圧縮率を高くする。【解決手段】判定部４１０は、識別番号決定部４０８
の出力する識別番号に基づいて、注目画素と一致する予
測を行った予測部を判定し、この予測部より短い符号語
を割り当てられている予測部がある場合には、予測部と
識別番号との対応情報に基づいて、短い符号語の予測部
の組合せを決定する。判定部４１０は、減算部４０１〜
４０３の出力する予測誤差から、決定された組合せの予
測部の予測誤差をそれぞれ読み込み、一致するかを判定
する。一致した場合は、符号語の変更を符号化部５０に
対して通知する。符号語の変更により、予測が一致した
予測部により短い符号語が割り当てられる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、画像符号化装置に
関するものであり、特に多値の入力画像に対する可逆符
号化に関するものである。

【０００２】

【従来の技術】画像は一般に非常に大量のデータとなる
ので、蓄積や伝送の際には符号化によって圧縮するのが
一般的である。画像データの符号化手法は、可逆符号化
方式と非可逆符号化方式の２種類に大別される。後者の
場合、圧縮率によっては復号画像に視覚的な劣化を生ず
る可能性がある。

【０００３】近年、ＰＤＬ（ＰａｇｅＤｅｓｃｒｉｐ
ｔｉｏｎＬａｎｇｕａｇｅ）で記述される画像を代表
として、コンピュータで作成される画像（以下、総称し
てＣＧ画像と呼ぶ）が増加している。これらの画像は従
来のスキャンインされた画像に比較して、スキャン時の
雑音成分を含まないため、エッジ等において非可逆符号
化による画質劣化が非常に目立ちやすい。

【０００４】こうした画質劣化の問題は、入力された画
像と同一の復号画像が得られる可逆符号化を使用するこ
とで回避することができる。

【０００５】特願平９５−００１６１号（現在、未公
開）に開示される「画像符号化装置および画像復号装
置」は、こうした可逆の符号化を実現するためになされ
たものである。

【０００６】図８は特願平９５−００１６１号で提案し
た画像符号化復号装置の構成を示すブロック図である。

【０００７】同図において、１０は画像入力部、２０は
第１予測部、２１は第２予測部、２２は第３予測部、３
０は予測誤差算出部、４０は選択部、５０は符号化部、
６０は符号出力部であり、選択部４０において、４０
１，４０２，４０３は減算部、４０４，４０５，４０６
は零判定部、４０７はＡＮＤ、４０８は識別番号決定
部、４０９は多重化部、である。

【０００８】続いて同図に基づいて動作を説明する。

【０００９】第１予測部２０、第２予測部２１、第３予
測部２２は、それぞれ所定の手法で画像データ１００に
基づいて注目画素の画素値を予測し、予測値データ１１
０として選択部４０へ送出する。

【００１０】予測の手法としては、例えば図７（ａ）に
示されるような、予測の対象となる注目画素Ｘの周辺に
位置する画素ａ，ｂ，ｃ，ｄを読み出してこれらの画素
の値を予測値データ１１０とするものがある。

【００１１】予測誤差算出部３０は、所定の手法で画像
データ１００に基づいて注目画素の画素値を予測し、そ
の予測値を注目画素の実際の画素値から減算し、予測誤
差データ１２０として選択部４０へ送出する。

【００１２】選択部４０は画像データ１００と予測値デ
ータ１１０から注目画素における予測の一致／不一致を
検出する。

【００１３】第１予測部２０、第２予測部２１、第３予
測部２２から出力される予測値データ１１０は、それぞ
れ減算部４０１，４０２，４０３において画像データ１
００との差分が計算される。さらに、零判定部４０４，
４０５，４０６では差分が零であるかが判定され、零で
ある場合は識別番号決定部４０８に判定結果が通知さ
れ、零でない場合はＡＮＤ４０７に結果が通知される。
ＡＮＤ４０７は、減算部４０１，４０２，４０３で計算
された全ての差分が零でない場合を検出し、結果を識別
番号決定部４０８に通知する。

【００１４】識別番号決定部４０８は、零判定部４０
４，４０５，４０６の出力する判定結果とＡＮＤ４０７
の出力の４つの入力のそれぞれを一意に識別する識別番
号を保持し、入力されたものに対応する識別番号を多重
化部４０９に出力する。なお、識別番号の割当ては、固
定にされる場合と出現頻度の変動に応じて動的に変更さ
れる場合がある。

【００１５】多重化部４０９は、零判定部４０４，４０
５，４０６の判定結果のいずれかが零である場合、すな
わち、第１予測部２０、第２予測部２１、第３予測部２
２のいずれの予測器が的中したかは、これに対応する識
別番号を出力する。ＡＮＤ４０７の出力が検出された場
合、すなわち、第１予測部２０、第２予測部２１、第３
予測部２２のいずれの予測器も的中しなかった場合は、
これに対応する識別番号と予測誤差１２０を多重化して
予測状況データ１３０を符号化部５０に出力する図６
（ａ）は、予測状況データ１３０の構成を示す図であ
る。これは、予測が的中した予測部の識別番号のみ、あ
るいは、いずれも的中しなかったことを示す識別番号と
予測誤差データ１２０から構成される。

【００１６】符号化部５０では、予測状況データ１３０
の識別番号を対応する可変長の符号語で置き換えること
により可変長符号化する。

【００１７】図７（ｂ）は、識別番号に対する可変長符
号の割当ての例を説明する図である。

【００１８】図７（ａ）の予測器の構成において、周辺
画素ａ，ｂ，ｃ，ｄの画素値をそのまま予測値とする場
合、予測の的中率をａ＞ｂ＞ｃ＞ｄ＞（すべての予測が
はずれる確率）と仮定し、また、識別番号決定部４０８
は識別番号を発生確率の高いものから順に０，１，
２，．．．と割当てるとすると、図７（ｂ）の符号表が
得られる。可変長の符号語は、発生確率順に並べられた
識別番号に対して図７（ｃ）に示すハフマン符号のツリ
ーを構成して決定されている。

【００１９】図６（ｃ）は、図６（ｂ）に示す予測状況
データ１３０を可変長符号化して得られる符号データ１
４０を表している。

【００２０】符号出力部６０は、符号データ１４０を図
示されない伝送路、あるいは蓄積手段に対して出力す
る。

【００２１】以上の構成、及び動作で従来技術における
画像の符号化装置によって画像信号が可逆に符号化され
ることになる。

【００２２】

【発明が解決しようとする課題】ＣＧ（コンピュータ・
グラフィックス）画像には、（１）使用される画素値が
特定の値に偏ることが多い、（２）同一画素値が隣接画
素に存在することが多いという特徴を持つことが多い。

【００２３】先に説明した関連技術では、こうした特徴
を利用し、注目画素と同じ画素値を予測した予測器の識
別番号を符号化し、予測がはずれた場合は予測誤差を符
号化することでＣＧ画像の効率的な可逆符号化を実現し
ていた。また、この時、より符号化効率を高めるため
に、予測器ごとに的中率に応じた可変長の符号を割当て
ていた。

【００２４】しかし、先の関連技術においては次のよう
な問題があった。

【００２５】例えば、符号語長ｉ，ｊ，ｋ（ｉ≦ｊ＜ｋ
の自然数）の割当てられて３つの予測器を使用する場合
について考える。符号語長ｉとｊの予測器が同一の予測
値となり、これらの予測が的中した場合は、圧縮の観点
からは符号長の短い長さｉの符号語が常に選ばれ、長さ
ｊの符号語が選ばれることはない。

【００２６】一方、符号語長ｉとｊの予測器が同一の予
測値で、かつ、予測が的中しなかった場合に、符号語長
ｋが割当てられた予測器が的中することがあり、この
時、長さｊの符号語は使用されないにもかかわらず、長
さｋの符号語がそのまま使用されていた。

【００２７】本発明は上述した事情に鑑みてなされたも
ので、ＰＤＬで記述された画像をはじめとするコンピュ
ータ作成画像に対し、圧縮率の高い可逆符号化装置およ
び復号装置を提供することを目的とするものである。

【００２８】

【課題を解決するための手段】本発明の請求項１によれ
ば、上記課題を解決するために、画像を入力する画像入
力手段と、前記画像入力手段により入力した画像内の符
号化対象である注目画素の画素値をそれぞれ異なる予測
手法で予測する複数の予測手段と、前記画像入力手段に
より入力した画像内の注目画素の画素値と所定の予測手
法で予測された予測値との誤差を算出する予測誤差算出
手段と、前記複数の予測手段により予測した画素値と注
目画素の画素値とが一致するか否かを判断する一致判断
手段と、前記一致判断手段の判断出力に基づいて、前記
一致判断手段により一致すると判断された予測手段を識
別する識別情報と、前記予測誤差算出手段により算出さ
れた誤差とを、択一的に出力する選択手段と、前記選択
手段により出力された識別情報及び誤差を符号化する符
号化手段と、前記符号化手段により符号化された符号を
出力する出力手段とを備えた画像符号化装置において、
前記複数の予測手段の少なくとも一つの予測結果が一致
し、かつ、不一致と判定された少なくとも二つの予測手
段の予測した画素値が等しいことを判定し、前記符号化
手段において各々の予測手段に対応する識別情報に付与
される２進系列の長さに基づいて前記符号化手段におけ
る２進系列の割当て変更を通知する判定手段を備えたこ
とを特徴とする。

【００２９】また、本発明の請求項２によれば、上述の
請求項１記載の画像符号化装置において、前記複数の予
測手段のうちで、予測した画素値と注目画素の画素値と
が一致する予測手段の識別情報に長さｋ（ｋは自然数）
の２進系列が前記符号化手段により割当てられている時
に、前記複数の予測手段のうちで、予測した画素値と注
目画素の画素値とが一致しなかった予測手段で予測した
画素値が等しいものが複数存在し、かつ、これらの予測
手段の識別情報が前記符号化手段において長さｋよりも
短い２進系列が割当てられる場合、前記判定手段から２
進系列の割当て変更を通知を受けた時に、前記長さｋよ
りも短い２進系列のうちで最も長い２進系列を予測した
画素値と注目画素の画素値とが一致する予測手段の識別
情報に割当てることを特徴とする。

【００３０】また、本発明の請求項３によれば、請求項
１に記載の画像符号化装置において、前記符号化手段が
前記２進系列を符号語として可変長符号化して前記符号
を構成することを特徴とする。

【００３１】また、本発明の請求項４によれば、請求項
１に記載の画像符号化装置においては、前記符号化手段
が前記２進系列を算術符号化して前記符号を構成するこ
とを特徴とする。

【００３２】また、前記一致判断手段は、前記予測手段
により予測した画素値と注目画素の画素値との間の誤差
が所定の閾値以内のときに上記予測した画素値と注目画
素の画素値とが一致していると判断するようにしてもよ
い。

【００３３】以上の構成によれば、先の関連技術のよう
に複数の予測部のうち予測が的中した予測部の識別番号
を符号化するだけでなく、複数の予測部が同一の予測を
行い、かつ予測がはずれであった場合に使用されない符
号語が発生することに着目し、この冗長性を削減するよ
うに符号語の再割当てをすることで圧縮率をより高くす
ることができる。

【００３４】

【発明の実施の形態】以下、本発明の概念について説明
するが、はじめに説明の前提について述べる。

【００３５】以下の説明では、従来技術の項と同様に、
図７（ａ）の構成の予測器を使用し、注目画素Ｘの周辺
画素ａ，ｂ，ｃ，ｄの画素値を予測値とする。予測の的
中率は、ａ＞ｂ＞ｃ＞ｄ＞（すべての予測がはずれる確
率）と仮定し、識別番号は、発生確率の高いものから順
に０，１，２，．．．と割当てるものとする。ただし、
これらは説明のための仮定であって、本発明を限定する
ものではない。

【００３６】以上の前提から、発生確率順に並べられた
識別番号に対して図７（ｃ）に示すハフマン符号のツリ
ーが構成され、図７（ｂ）の識別番号と可変長符号語の
対応表が得られる。

【００３７】図２は、予測器内の画素の状態を説明する
図である。

【００３８】図２（ａ）のように、参照画素ｂ，ｃ、お
よび注目画素Ｘが同色（縦線の領域）の場合、参照画素
ｂが注目画素Ｘと一致することから２ビットの符号語
「１０」が出力される。注目画素ｃも同色ではあるが、
こちらを採用すると出力される符号語は３ビットの「１
１０」となるため、符号化を目的とする場合には選択さ
れることはない。

【００３９】図２（ｂ）は、図２（ａ）の注目画素Ｘを
復号する時の参照画素を示している。注目画素Ｘを復号
する場合、参照画素ｂとｃが同色（縦線の領域）であれ
ば、参照画素ｂと同色であることを示す符号語「１０」
の可能性はあっても、参照画素ｃと同色であることを示
す符号語「１１０」は、上述した理由から除外すること
ができる。

【００４０】今、図２（ｃ）のように参照画素ｂ，ｃが
同じ色（縦線の領域）で、参照画素ｄと注目画素Ｘが、
参照画素ｂ，ｃとは異なる同じ色（斜め線の領域）であ
る場合を考える。

【００４１】この場合は、参照画素ｄとの一致を示す４
ビットの符号語「１１１０」が出力される。しかし、上
述したように、参照画素ｃとの一致を示す符号語「１１
０」が使用されることはないので、参照画素ｄとの一致
を示す符号として一時的に再割当てすることが可能とな
る。復号の際にも、同様の取決めをすることで、１ビッ
トの情報が削減されることになる。

【００４２】図３は、４つの予測器（参照画素）を使用
した場合にビットの削減が可能な組合せを示すものであ
る。なお、予測器と符号語の対応関係は図７（ｂ）の表
を使用した。

【００４３】図３の第１列の予測器の予測が的中し、第
２列に示される予測器の予測誤差が一致する場合に第３
列の符号語の変更が可能であり、第４列はこの時削減さ
れるビット数を表している。

【００４４】例えば、予測器２が注目画素と一致してい
る場合、これらとは異なる色で予測器０と１（ａとｂ）
が一致しているときには、予測器１に割当てられた符号
「１０」が使用されることはないので、予測器２に割当
てられる符号語「１１０」の代わりに使用できる。

【００４５】図４は、図３に示される各条件を満たす場
合が実際の画像でどの程度発生するかを測定した結果で
ある。測定には、ＰＤＬで記述された２種類のＣＧ画像
を使用した。画像Ａは直線で構成される幾何学模様、画
像Ｂは、ＬＳＩの配線図である。画素数は、いずれも３
３１２×４６８０であり、色空間ＹＭＣＫのＫ成分を用
いている。

【００４６】図３に示される各条件で削減されるビット
数と、図４に示される画像Ａ，Ｂにおける各条件の発生
回数の積の総和から削減される符号量を求めることがで
きる。画像Ａの場合は、３４１，０８０ビット（４２，
６３５バイト）、画像Ｂの場合は、６６９，４２７ビッ
ト（８３，６７８バイト）の符号量が削減されることに
なる。

【００４７】

【実施例】本発明の第１の実施例について説明する。

【００４８】図１は、本発明の第１の実施例の構成を説
明するブロック図である。なお図８に示される従来技術
の構成と同一の構成については、同一番号を付して説明
を省略する。

【００４９】同図において、４１０は、減算部４０１，
４０２，４０３の出力する予測誤差信号と、識別番号決
定部４０８における予測部と識別番号の対応情報とに基
づいて図３の条件に該当する状態を検出し、符号化部５
０に符号変更情報を出力する判定部である。

【００５０】続いて図５のフローチャートに基づいて動
作について説明する。

【００５１】はじめに、判定部４１０は、識別番号決定
部４０８の出力する識別番号、すなわち注目画素と一致
する予測を行った予測器で図３の表の第１列の条件を満
たすものを検出する（図５−Ｓ１）。

【００５２】次に、判定部４１０は、識別番号決定部４
０８から予測部と識別番号の対応情報を得て、図３の表
の第２列、「予測値を比較する予測器の組合せ」を決定
する（図５−Ｓ２）。

【００５３】さらに、判定部４１０は、減算部４０１，
４０２，４０３の出力する予測誤差から、図５−Ｓ２で
決定された組合せの予測部の予測誤差をそれぞれ読み込
み（図５−Ｓ３）、一致するかを判定する（図５−Ｓ
４）。

【００５４】一致した場合は、図３の表の３列目の符号
語の変更を符号化部５０に対して通知する（図５−Ｓ
５）。

【００５５】以上の構成、及び動作により、本発明の画
像の符号化装置による画像の符号化が実行される。

【００５６】なお、復号動作については、符号化動作よ
り自明であるので説明を省略する。

【００５７】予測器の数、予測式はこれらに限定するも
のではない。

【００５８】また、的中した予測器の識別番号に割当て
る２進系列を可変長の符号とし、これを多重化して符号
データ１４０として出力しても良いし、割当てられた２
進系列を算術符号化し、その出力として符号データ１４
０を生成してもよい。

【００５９】また、予測した画素値と注目画素の画素値
との間の誤差が所定の閾値以内のときに、予測した画素
値と注目画素の画素値とが一致していると判断するよう
にしてもよい。

【００６０】

【発明の効果】以上、説明してきたように本発明よれ
ば、従来技術のように複数の予測部のうち予測が的中し
た予測部を符号化するだけでなく、複数の予測部が同一
の予測を行い、かつ予測がはずれであった場合に使用さ
れない符号語が発生することに着目し、符号語の再割当
てをすることで圧縮率をより高くすることができる。

【００６１】本発明の具体的な効果については、符号化
される画像の内容や可変長符号の割当て方に大きく依存
するものであるが、実施例の項に説明したように実際の
画像に対して符号量の削減効果が確認されている。

【図面の簡単な説明】

【図１】本発明の第１の実施例の構成を示すブロック
図である。

【図２】画素配置の説明図である。

【図３】符号の再割当てを説明する図である。

【図４】実際の画像での発生頻度を説明する図であ
る。

【図５】動作を説明するためのフローチャートであ
る。

【図６】データの構成を説明する図である。

【図７】符号化の説明図である。

【図８】従来技術の構成を示すブロック図である。

【符号の説明】

１０…画像入力部、２０…第１予測部、２１…第２予測部、２２…第３予測部、３０…予測誤差算出部、４０…選択部、５０…符号化部、５１…復号部、６０…符号出力部、１００…画像データ、１１０…予測値データ、１２０…予測誤差データ、１３０…予測状況データ、１４０…符号データ、４０１，４０２．４０３…減算器、４０４，４０５，４０６…零判定部、４０７…ＡＮＤ、４０８…識別番号決定部、４０９…多重化部、４１０…判定部

Claims

【特許請求の範囲】

【請求項１】画像を入力する画像入力手段と、前記画
像入力手段により入力した画像内の符号化対象である注
目画素の画素値をそれぞれ異なる予測手法で予測する複
数の予測手段と、前記画像入力手段により入力した画像
内の注目画素の画素値と所定の予測手法で予測された予
測値との誤差を算出する予測誤差算出手段と、前記複数
の予測手段により予測した画素値と注目画素の画素値と
が一致するか否かを判断する一致判断手段と、前記一致
判断手段の判断出力に基づいて、前記一致判断手段によ
り一致すると判断された予測手段を識別する識別情報
と、前記予測誤差算出手段により算出された誤差とを、
択一的に出力する選択手段と、前記選択手段により出力
された識別情報及び誤差を符号化する符号化手段と、前
記符号化手段により符号化された符号を出力する出力手
段とを備えた画像符号化装置において、前記複数の予測手段の少なくとも一つの予測結果が前記
注目画素の画素値と一致し、かつ、前記注目画素の画素
値と不一致と判定された少なくとも二つの予測手段の予
測した画素値が等しいことを判定し、前記符号化手段に
おいて各々の予測手段に対応する識別情報に付与される
２進系列の長さに基づいて前記符号化手段における２進
系列の割当て変更を通知する判定手段を備えたことを特
徴とする画像符号化装置。
【請求項２】前記符号化手段において、前記複数の予
測手段のうちで、予測した画素値と注目画素の画素値と
が一致する予測手段の識別情報に長さｋ（ｋは自然数）
の２進系列が割当てられている時に、前記複数の予測手段のうちで、予測した画素値と注目画
素の画素値とが一致しなかった予測手段で予測した画素
値が等しいものが複数存在し、かつ、これらの予測手段
の識別情報が前記符号化手段において長さｋよりも短い
２進系列が割当てられる場合、前記判定手段から２進系列の割当て変更を通知を受けた
時に、前記長さｋよりも短い２進系列のうちで最も長い
２進系列を予測した画素値と注目画素の画素値とが一致
する予測手段の識別情報に割当てることを特徴とする、
請求項１に記載の画像符号化装置。
【請求項３】前記符号化手段において、前記２進系列
を符号語として可変長符号化して前記符号を構成するこ
とを特徴とする請求項１に記載の画像符号化装置。
【請求項４】前記符号化手段において、前記２進系列
を算術符号化して前記符号を構成することを特徴とする
請求項１に記載の画像符号化装置。
【請求項５】前記一致判断手段は、前記予測手段によ
り予測した画素値と注目画素の画素値との間の誤差が所
定の閾値以内のときに上記予測した画素値と注目画素の
画素値とが一致していると判断する請求項１、２、３ま
たは４に記載の画像符号化装置。