JP3855376B2

JP3855376B2 - 画像符号化装置

Info

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

Description

【０００１】
【発明の属する技術分野】
本発明は、画像符号化装置に関するものであり、特に多値の入力画像に対する可逆符号化に関するものである。
【０００２】
【従来の技術】
画像は一般に非常に大量のデータとなるので、蓄積や伝送の際には符号化によって圧縮するのが一般的である。画像データの符号化手法は、可逆符号化方式と非可逆符号化方式の２種類に大別される。後者の場合、圧縮率によっては復号画像に視覚的な劣化を生ずる可能性がある。
【０００３】
近年、ＰＤＬ（ＰａｇｅＤｅｓｃｒｉｐｔｉｏｎＬａｎｇｕａｇｅ）で記述される画像を代表として、コンピュータで作成される画像（以下、総称してＣＧ画像と呼ぶ）が増加している。これらの画像は従来のスキャンインされた画像に比較して、スキャン時の雑音成分を含まないため、エッジ等において非可逆符号化による画質劣化が非常に目立ちやすい。
【０００４】
こうした画質劣化の問題は、入力された画像と同一の復号画像が得られる可逆符号化を使用することで回避することができる。
【０００５】
特願平９５−００１６１号（現在、未公開）に開示される「画像符号化装置および画像復号装置」は、こうした可逆の符号化を実現するためになされたものである。
【０００６】
図８は特願平９５−００１６１号で提案した画像符号化復号装置の構成を示すブロック図である。
【０００７】
同図において、１０は画像入力部、２０は第１予測部、２１は第２予測部、２２は第３予測部、３０は予測誤差算出部、４０は選択部、５０は符号化部、６０は符号出力部であり、選択部４０において、４０１，４０２，４０３は減算部、４０４，４０５，４０６は零判定部、４０７はＡＮＤ、４０８は識別番号決定部、４０９は多重化部、である。
【０００８】
続いて同図に基づいて動作を説明する。
【０００９】
第１予測部２０、第２予測部２１、第３予測部２２は、それぞれ所定の手法で画像データ１００に基づいて注目画素の画素値を予測し、予測値データ１１０として選択部４０へ送出する。
【００１０】
予測の手法としては、例えば図７（ａ）に示されるような、予測の対象となる注目画素Ｘの周辺に位置する画素ａ，ｂ，ｃ，ｄを読み出してこれらの画素の値を予測値データ１１０とするものがある。
【００１１】
予測誤差算出部３０は、所定の手法で画像データ１００に基づいて注目画素の画素値を予測し、その予測値を注目画素の実際の画素値から減算し、予測誤差データ１２０として選択部４０へ送出する。
【００１２】
選択部４０は画像データ１００と予測値データ１１０から注目画素における予測の一致／不一致を検出する。
【００１３】
第１予測部２０、第２予測部２１、第３予測部２２から出力される予測値データ１１０は、それぞれ減算部４０１，４０２，４０３において画像データ１００との差分が計算される。さらに、零判定部４０４，４０５，４０６では差分が零であるかが判定され、零である場合は識別番号決定部４０８に判定結果が通知され、零でない場合はＡＮＤ４０７に結果が通知される。ＡＮＤ４０７は、減算部４０１，４０２，４０３で計算された全ての差分が零でない場合を検出し、結果を識別番号決定部４０８に通知する。
【００１４】
識別番号決定部４０８は、零判定部４０４，４０５，４０６の出力する判定結果とＡＮＤ４０７の出力の４つの入力のそれぞれを一意に識別する識別番号を保持し、入力されたものに対応する識別番号を多重化部４０９に出力する。なお、識別番号の割当ては、固定にされる場合と出現頻度の変動に応じて動的に変更される場合がある。
【００１５】
多重化部４０９は、零判定部４０４，４０５，４０６の判定結果のいずれかが零である場合、すなわち、第１予測部２０、第２予測部２１、第３予測部２２のいずれの予測器が的中したかは、これに対応する識別番号を出力する。ＡＮＤ４０７の出力が検出された場合、すなわち、第１予測部２０、第２予測部２１、第３予測部２２のいずれの予測器も的中しなかった場合は、これに対応する識別番号と予測誤差１２０を多重化して予測状況データ１３０を符号化部５０に出力する
図６（ａ）は、予測状況データ１３０の構成を示す図である。これは、予測が的中した予測部の識別番号のみ、あるいは、いずれも的中しなかったことを示す識別番号と予測誤差データ１２０から構成される。
【００１６】
符号化部５０では、予測状況データ１３０の識別番号を対応する可変長の符号語で置き換えることにより可変長符号化する。
【００１７】
図７（ｂ）は、識別番号に対する可変長符号の割当ての例を説明する図である。
【００１８】
図７（ａ）の予測器の構成において、周辺画素ａ，ｂ，ｃ，ｄの画素値をそのまま予測値とする場合、予測の的中率をａ＞ｂ＞ｃ＞ｄ＞（すべての予測がはずれる確率）と仮定し、また、識別番号決定部４０８は識別番号を発生確率の高いものから順に０，１，２，．．．と割当てるとすると、図７（ｂ）の符号表が得られる。可変長の符号語は、発生確率順に並べられた識別番号に対して図７（ｃ）に示すハフマン符号のツリーを構成して決定されている。
【００１９】
図６（ｃ）は、図６（ｂ）に示す予測状況データ１３０を可変長符号化して得られる符号データ１４０を表している。
【００２０】
符号出力部６０は、符号データ１４０を図示されない伝送路、あるいは蓄積手段に対して出力する。
【００２１】
以上の構成、及び動作で従来技術における画像の符号化装置によって画像信号が可逆に符号化されることになる。
【００２２】
【発明が解決しようとする課題】
ＣＧ（コンピュータ・グラフィックス）画像には、（１）使用される画素値が特定の値に偏ることが多い、（２）同一画素値が隣接画素に存在することが多いという特徴を持つことが多い。
【００２３】
先に説明した関連技術では、こうした特徴を利用し、注目画素と同じ画素値を予測した予測器の識別番号を符号化し、予測がはずれた場合は予測誤差を符号化することでＣＧ画像の効率的な可逆符号化を実現していた。また、この時、より符号化効率を高めるために、予測器ごとに的中率に応じた可変長の符号を割当てていた。
【００２４】
しかし、先の関連技術においては次のような問題があった。
【００２５】
例えば、符号語長ｉ，ｊ，ｋ（ｉ≦ｊ＜ｋの自然数）の割当てられて３つの予測器を使用する場合について考える。符号語長ｉとｊの予測器が同一の予測値となり、これらの予測が的中した場合は、圧縮の観点からは符号長の短い長さｉの符号語が常に選ばれ、長さｊの符号語が選ばれることはない。
【００２６】
一方、符号語長ｉとｊの予測器が同一の予測値で、かつ、予測が的中しなかった場合に、符号語長ｋが割当てられた予測器が的中することがあり、この時、長さｊの符号語は使用されないにもかかわらず、長さｋの符号語がそのまま使用されていた。
【００２７】
本発明は上述した事情に鑑みてなされたもので、ＰＤＬで記述された画像をはじめとするコンピュータ作成画像に対し、圧縮率の高い可逆符号化装置および復号装置を提供することを目的とするものである。
【００２８】
【課題を解決するための手段】
本発明の請求項１によれば、上記課題を解決するために、画像を入力する画像入力手段と、前記画像入力手段により入力した画像内の符号化対象である注目画素の画素値をそれぞれ異なる予測手法で予測する複数の予測手段と、前記画像入力手段により入力した画像内の注目画素の画素値と所定の予測手法で予測された予測値との誤差を算出する予測誤差算出手段と、前記複数の予測手段により予測した画素値と注目画素の画素値とが一致するか否かを判断する一致判断手段と、前記一致判断手段により、前記複数の予測手段のうちいずれかの予測手段により予測した画素値と注目画素の画素値とが一致した場合には、前記一致すると判断された予測手段を出力し、前記一致すると判断されない場合には上記誤差を選択して出力する選択手段と、前記選択手段により出力された識別情報及び誤差を符号化する符号化手段と、前記符号化手段により符号化された符号を出力する出力手段とを備えた画像符号化装置において、前記複数の予測手段の少なくとも一つの予測結果が一致し、かつ、不一致と判定された少なくとも二つの予測手段の予測した画素値が等しいことを判定し、前記符号化手段において各々の予測手段に対応する識別情報に付与される可変長２進系列の長さに基づいて前記符号化手段における２進系列の割当て変更を行うと判定する判定手段を備えたことを特徴とする。
【００２９】
さらに、前記複数の予測手段のうちで、予測した画素値と注目画素の画素値とが一致する予測手段の識別情報に長さｋ（ｋは自然数）の可変長２進系列が前記符号化手段により割当てられている時に、前記複数の予測手段のうちで、予測した画素値と注目画素の画素値とが一致しなかった予測手段で予測した画素値が等しいものが複数存在し、かつ、これらの予測手段の識別情報が前記符号化手段において長さｋよりも短い２進系列が割当てられる場合、前記判定手段から２進系列の割当て変更の通知を受けた時に、前記長さｋよりも短い２進系列のうちで最も長い２進系列を予測した画素値と注目画素の画素値とが一致する予測手段の識別情報に割当てることを特徴とする。また、後に図３を参照して説明するような態様で、予測した画素値と注目画素の画素値とが一致する予測手段の識別情報に割当てられる２進系列の長さが、２進系列の割り当て変更前の長さより短くなるように、予測した画素値が等しい複数の予測手段のそれぞれの識別情報のうち一部に割り当てられていた前記長さｋより短い２進系列を、前記予測した画素値が等しい複数の予測手段の他の予測手段の識別情報に割り当ててもよい。
【００３０】
また、本発明の請求項２によれば、前記符号化手段がハフマン符号の２進系列を符号語として可変長符号化して前記符号を構成することを特徴とする。
【００３２】
また、前記一致判断手段は、前記予測手段により予測した画素値と注目画素の画素値との間の誤差が所定の閾値以内のときに上記予測した画素値と注目画素の画素値とが一致していると判断するようにしてもよい。
【００３３】
以上の構成によれば、先の関連技術のように複数の予測部のうち予測が的中した予測部の識別番号を符号化するだけでなく、複数の予測部が同一の予測を行い、かつ予測がはずれであった場合に使用されない符号語が発生することに着目し、この冗長性を削減するように符号語の再割当てをすることで圧縮率をより高くすることができる。
【００３４】
【発明の実施の形態】
以下、本発明の概念について説明するが、はじめに説明の前提について述べる。
【００３５】
以下の説明では、従来技術の項と同様に、図７（ａ）の構成の予測器を使用し、注目画素Ｘの周辺画素ａ，ｂ，ｃ，ｄの画素値を予測値とする。予測の的中率は、ａ＞ｂ＞ｃ＞ｄ＞（すべての予測がはずれる確率）と仮定し、識別番号は、発生確率の高いものから順に０，１，２，．．．と割当てるものとする。ただし、これらは説明のための仮定であって、本発明を限定するものではない。
【００３６】
以上の前提から、発生確率順に並べられた識別番号に対して図７（ｃ）に示すハフマン符号のツリーが構成され、図７（ｂ）の識別番号と可変長符号語の対応表が得られる。
【００３７】
図２は、予測器内の画素の状態を説明する図である。
【００３８】
図２（ａ）のように、参照画素ｂ，ｃ、および注目画素Ｘが同色（縦線の領域）の場合、参照画素ｂが注目画素Ｘと一致することから２ビットの符号語「１０」が出力される。注目画素ｃも同色ではあるが、こちらを採用すると出力される符号語は３ビットの「１１０」となるため、符号化を目的とする場合には選択されることはない。
【００３９】
図２（ｂ）は、図２（ａ）の注目画素Ｘを復号する時の参照画素を示している。注目画素Ｘを復号する場合、参照画素ｂとｃが同色（縦線の領域）であれば、参照画素ｂと同色であることを示す符号語「１０」の可能性はあっても、参照画素ｃと同色であることを示す符号語「１１０」は、上述した理由から除外することができる。
【００４０】
今、図２（ｃ）のように参照画素ｂ，ｃが同じ色（縦線の領域）で、参照画素ｄと注目画素Ｘが、参照画素ｂ，ｃとは異なる同じ色（斜め線の領域）である場合を考える。
【００４１】
この場合は、参照画素ｄとの一致を示す４ビットの符号語「１１１０」が出力される。しかし、上述したように、参照画素ｃとの一致を示す符号語「１１０」が使用されることはないので、参照画素ｄとの一致を示す符号として一時的に再割当てすることが可能となる。復号の際にも、同様の取決めをすることで、１ビットの情報が削減されることになる。
【００４２】
図３は、４つの予測器（参照画素）を使用した場合にビットの削減が可能な組合せを示すものである。なお、予測器と符号語の対応関係は図７（ｂ）の表を使用した。
【００４３】
図３の第１列の予測器の予測が的中し、第２列に示される予測器の予測誤差が一致する場合に第３列の符号語の変更が可能であり、第４列はこの時削減されるビット数を表している。
【００４４】
例えば、予測器２が注目画素と一致している場合、これらとは異なる色で予測器０と１（ａとｂ）が一致しているときには、予測器１に割当てられた符号「１０」が使用されることはないので、予測器２に割当てられる符号語「１１０」の代わりに使用できる。
【００４５】
図４は、図３に示される各条件を満たす場合が実際の画像でどの程度発生するかを測定した結果である。測定には、ＰＤＬで記述された２種類のＣＧ画像を使用した。画像Ａは直線で構成される幾何学模様、画像Ｂは、ＬＳＩの配線図である。画素数は、いずれも３３１２×４６８０であり、色空間ＹＭＣＫのＫ成分を用いている。
【００４６】
図３に示される各条件で削減されるビット数と、図４に示される画像Ａ，Ｂにおける各条件の発生回数の積の総和から削減される符号量を求めることができる。画像Ａの場合は、３４１，０８０ビット（４２，６３５バイト）、画像Ｂの場合は、６６９，４２７ビット（８３，６７８バイト）の符号量が削減されることになる。
【００４７】
【実施例】
本発明の第１の実施例について説明する。
【００４８】
図１は、本発明の第１の実施例の構成を説明するブロック図である。なお図８に示される従来技術の構成と同一の構成については、同一番号を付して説明を省略する。
【００４９】
同図において、４１０は、減算部４０１，４０２，４０３の出力する予測誤差信号と、識別番号決定部４０８における予測部と識別番号の対応情報とに基づいて図３の条件に該当する状態を検出し、符号化部５０に符号変更情報を出力する判定部である。
【００５０】
続いて図５のフローチャートに基づいて動作について説明する。
【００５１】
はじめに、判定部４１０は、識別番号決定部４０８の出力する識別番号、すなわち注目画素と一致する予測を行った予測器で図３の表の第１列の条件を満たすものを検出する（図５−Ｓ１）。
【００５２】
次に、判定部４１０は、識別番号決定部４０８から予測部と識別番号の対応情報を得て、図３の表の第２列、「予測値を比較する予測器の組合せ」を決定する（図５−Ｓ２）。
【００５３】
さらに、判定部４１０は、減算部４０１，４０２，４０３の出力する予測誤差から、図５−Ｓ２で決定された組合せの予測部の予測誤差をそれぞれ読み込み（図５−Ｓ３）、一致するかを判定する（図５−Ｓ４）。
【００５４】
一致した場合は、図３の表の３列目の符号語の変更を符号化部５０に対して通知する（図５−Ｓ５）。
【００５５】
以上の構成、及び動作により、本発明の画像の符号化装置による画像の符号化が実行される。
【００５６】
なお、復号動作については、符号化動作より自明であるので説明を省略する。
【００５７】
予測器の数、予測式はこれらに限定するものではない。
【００５８】
また、的中した予測器の識別番号に割当てる２進系列を可変長の符号とし、これを多重化して符号データ１４０として出力しても良いし、割当てられた２進系列を算術符号化し、その出力として符号データ１４０を生成してもよい。
【００５９】
また、予測した画素値と注目画素の画素値との間の誤差が所定の閾値以内のときに、予測した画素値と注目画素の画素値とが一致していると判断するようにしてもよい。
【００６０】
【発明の効果】
以上、説明してきたように本発明よれば、従来技術のように複数の予測部のうち予測が的中した予測部を符号化するだけでなく、複数の予測部が同一の予測を行い、かつ予測がはずれであった場合に使用されない符号語が発生することに着目し、符号語の再割当てをすることで圧縮率をより高くすることができる。
【００６１】
本発明の具体的な効果については、符号化される画像の内容や可変長符号の割当て方に大きく依存するものであるが、実施例の項に説明したように実際の画像に対して符号量の削減効果が確認されている。
【図面の簡単な説明】
【図１】本発明の第１の実施例の構成を示すブロック図である。
【図２】画素配置の説明図である。
【図３】符号の再割当てを説明する図である。
【図４】実際の画像での発生頻度を説明する図である。
【図５】動作を説明するためのフローチャートである。
【図６】データの構成を説明する図である。
【図７】符号化の説明図である。
【図８】従来技術の構成を示すブロック図である。
【符号の説明】
１０…画像入力部、
２０…第１予測部、
２１…第２予測部、
２２…第３予測部、
３０…予測誤差算出部、
４０…選択部、
５０…符号化部、
５１…復号部、
６０…符号出力部、
１００…画像データ、
１１０…予測値データ、
１２０…予測誤差データ、
１３０…予測状況データ、
１４０…符号データ、
４０１，４０２．４０３…減算器、
４０４，４０５，４０６…零判定部、
４０７…ＡＮＤ、
４０８…識別番号決定部、
４０９…多重化部、
４１０…判定部

Claims

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