JPH0937262A

JPH0937262A - 画像処理装置及び方法

Info

Publication number: JPH0937262A
Application number: JP7178708A
Authority: JP
Inventors: Hiroshi Kajiwara; 浩梶原; Koji Hirabayashi; 康二平林; Tadashi Yoshida; 正吉田
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1995-07-14
Filing date: 1995-07-14
Publication date: 1997-02-07

Abstract

(57)【要約】【課題】画像データを高い圧縮効率で、かつ画素値の
誤差を制御して符号化することを目的とする。【解決手段】画像の予測符号化を行う画像処理装置に
おいて、前記画像の画素値を予測する予測手段と、前記
予測手段による予測の結果に基づいて、前記画像の画素
値を±ｅの範囲で変換する画像変換手段と、前記画像変
換手段により変換された画像と、前記予測手段による予
測の結果とに基づいて、前記画像に関するパラメータを
符号化する符号化手段とを有することを特徴とする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本願発明は画像を符号化する
画像処理装置及び方法に関するものである。

【０００２】

【従来の技術】画像の符号化方法は、復号した際に元の
画像を完全に復元する情報保存型の符号化方法と、元の
画像との間に誤差を生じる情報非保存型の符号化方法の
二つに大別される。

【０００３】情報保存型の符号化方法としてＤＰＣＭ符
号化が広く知られている。一般的なＤＰＣＭ符号化によ
れば、符号化対象画素の周囲にある符号化済の画素、即
ち左画素（これをＡとする）、上画素（同様にＢ）、左
斜め画素（同様にＣ）を用いて符号化対象画素の予測値
を例えば式（Ａ＋Ｂ−Ｃ）を用いて算出し、これと符号
化対象画素値との差分が符号化されるものである。

【０００４】情報非保存型の符号化方法は元の画像を完
全に復元することができない反面、高い圧縮率を得るこ
とが可能であることから、膨大な画像データを扱う場合
や、多少の誤差が問題にならない場合には情報非保存型
の符号化方式を利用することが多い。ＪＰＥＧのベース
ライン方式は情報非保存型の符号化方法のひとつであ
る。

【０００５】

【発明が解決しようとする課題】従来の画像の符号化で
は、符号化データの量に応じて情報量を制御していたた
め、符号化したい画像の実際の画素値と、この画像を符
号化・復号化した後の画像の画素値との誤差をある程度
までは許す（誤差の範囲を制限したい）様な画像などに
対し、高い圧縮効率で、かつ画素値の誤差を一定値以内
で符号化することができないという問題があった。

【０００６】上述の問題を解決するために本願発明は、
画像データを高い圧縮効率で、かつ画素値の誤差を制御
して符号化することを目的とする。

【０００７】また、多値データを高い圧縮効率で、かつ
画素値の誤差を制御して符号化することを別の目的とす
る。

【０００８】

【課題を解決するための手段】上述の課題を解決するた
め、本願発明の請求項１に記載の画像符号化装置は、画
像の予測符号化を行う画像処理装置において、前記画像
の画素値を予測する予測手段と、前記予測手段による予
測の結果に基づいて、前記画像の画素値を±ｅの範囲で
変換する画像変換手段と、前記画像変換手段により変換
された画像と、前記予測手段による予測の結果とに基づ
いて、前記画像に関するパラメータを符号化する符号化
手段とを有することを特徴とする。

【０００９】

【発明の実施の形態】

（第１の実施の形態）次に、本願発明について簡単に説
明する。

【００１０】図１に本願発明に係る第１の実施の形態の
処理の流れを示す。同図においてＳ０は、後述する基準
ハフマンテーブルを設定するステップ、Ｓ１は画像デー
タを読み込むステップ、Ｓ２は画像データから最大ブロ
ックサイズ（ここでは16×１６画素）でブロックデータ
を取り出すステップ、Ｓ３はブロック分割方法及び符号
化方法を決定するステップ、Ｓ４はＳ３で決定したブロ
ック分割方法及び符号化方法を参照情報として保存する
ステップ、Ｓ５は参照情報に従って、出力された後述す
る差分値（予測誤差）の出現頻度の統計をとるステッ
プ、Ｓ６はＳ２で取り出されたブロックデータを後述す
る架空ブロックのデータに書き換えるステップ、Ｓ７は
画像の終端を判定するステップ、Ｓ８はＳ５でとった差
分値統計に基づいて最適なハフマンテーブルを作成する
ステップ、Ｓ９はループ終了を判定するステップ、Ｓ９
は参照情報に基づいて画像全体の符号化処理を行うステ
ップである。

【００１１】本実施の形態について簡単に説明する。本
実施の形態の符号化は、非可逆符号化ではなく、実際の
画像が示す画素値と、符号化する画像の画素値の誤差を
最大±ｅの範囲で認める符号化方法であり、これをニア
ロスレス符号化と呼ぶ。

【００１２】ここでは符号化されるブロックの最大サイ
ズを１６×16画素とし、16×16画素，８×８画素，４×
４画素のいずれかで符号化処理を行う。各ブロックの符
号化方法として、予測方法の異なる６種類の予測符号化
方法（＃０〜＃５番）、２種類の平面符号化方法（＃
６、＃７番）、及び、ブロック内が二値であった場合の
みに使用可能なランレングス符号化方法（＃８番）が選
択可能であるとする（図２参照）。

【００１３】まず、ブロックの符号化に用いるこれら９
種類の符号化方法について簡単に説明する。図３に各符
号化方法による符号データの構造を示す。

【００１４】＃０番から＃５番は予測符号化方法であ
り、各々、図２（ａ）に示す周辺画素Ａ，Ｂ，Ｃを用い
てＡ＋Ｂ−Ｃ，Ｂ，Ａ，Ｂ＋（Ａ−Ｃ）／２，Ａ＋（Ｂ
−Ｃ）／２，（Ａ＋Ｂ＋Ｃ）／３を予測値とし、注目画
素と予測値との差分をハフマン符号化する。ハフマンテ
ーブルはブロックサイズ毎に用意され、ブロックのサイ
ズに応じた別々のハフマンテーブルを用いて符号化され
る。

【００１５】＃６番と＃７番は平面符号化方法である。
＃６番では、ブロック内の左上隅の画素値をc0として、
ブロックの画素値を近似する平面Ｐ（ｘ，ｙ）＝ａｘ＋
ｂｙ＋c0を求め、ａ，ｂ，c0の値、及び、この近似平面
とブロック内画素値との差分をハフマン符号化する。

【００１６】このときに、ａ，ｂが一定値以内の場合に
はc0は前に出現したc0との差分c0’をハフマン符号化
し、一定値以上の場合にはc0の値そのものを符号化す
る。また、ａ，ｂ，c0の後にフラグを設け、ブロック内
の差分値が全て０となる場合には、差分データを付加し
ないようにする。

【００１７】＃７番はブロック内の画素値が全て同じ、
即ち、ａ＝ｂ＝０の平面である場合に使用され、上述の
c0’をハフマン符号化する。図４に＃６番と＃７番でc
0' を符号化する際に使用するハフマンテーブルの一例
を示す。同図において”Ｓ”はサインビットを表してお
り、c0の差分値の符号により０または１が入る。また、
c0が14以上と−14以下の場合には差分値を用いずに、Ｅ
ＳＣコードの後にc0の値を付加するものとする。

【００１８】＃８番は、ランレングス符号化方法であ
り、ブロック内の画素値が２つだけの場合のみに使用さ
れる。例えば、輝度の高い方の画素を白、低い方の画素
を黒とすると、図５に示す順序でブロック内の画素をス
キャンし、ランレングスに変換してこれを符号化する。
符号化にはあらかじめ定めた白（高輝度値）ラン用、黒
（低輝度値）ラン用のハフマンテーブルを使用し、ブロ
ック内の最後のランはＥＯＢコードに置き換えて符号化
するものとする。

【００１９】次に、本実施の形態における処理の流れを
図１を用いて詳細に説明する。

【００２０】まずステップＳ０では、ブロックの符号化
で使用される基準ハフマンテーブルが設定される。これ
は、予め複数の画像で求めた予測符号化、その他で発生
する予測誤差の統計情報に基づいて作成されたハフマン
テーブルを読み込み、16×１6 画素の予測符号化用ハフ
マンテーブル８×８画素の予測符号化用ハフマンテーブ
ル、４×４画素の予測符号化用ハフマンテーブル、平面
符号化用ハフマンテーブルを設定する。

【００２１】また、これらハフマンテーブルをＳ８で新
たに作成する際に用いる４つのカウンタ、即ち16×16画
素の予測符号化用カウンタ、８×８画素の予測符号化用
カウンタ、４×４画素の予測符号化用カウンタ、平面符
号化用カウンタの値を全て０に初期化する。

【００２２】また、符号化方法( ＃０〜＃８) を示す情
報をハフマン符号化するためのハフマンテーブルを各ブ
ロックサイズ毎に用意し、これらのハフマンテーブルを
Ｓ８で新たに作成する際に用いる符号化番号カウンタを
用意し、このカウンタの値も０にする。

【００２３】ステップＳ１では、符号化する画像データ
を符号化処理用のメモリ上に読み込む。

【００２４】ステップＳ２では、符号化対象画像からブ
ロックデータ（最大ブロックサイズ16×16画素) を順に
取り出す。ただし、取り出したブロックの上と左の１ラ
インについても予測符号化用の参照領域として取り出
す。

【００２５】ステップＳ３では、ステップＳ１で取り出
した最大サイズのブロック（16×16画素）について、ブ
ロックを更に符号化に適したサイズのブロック（符号化
対象ブロック）に分割するブロック分割方法、及び各符
号化対象ブロックに適した符号化方法（＃０〜＃８）を
決定すると共に、これに合わせて最大ブロック内の画素
値を実際の画素値と誤差±ｅの範囲で書き換える。これ
により、差分値（予測誤差）を小さくして符号化するこ
とができる。また、差分値が数種類の値のみになる様に
±ｅの範囲で書き換えることにより、この差分値の情報
量を減少させることもできる。以下にステップ３の処理
についての詳細な説明を記す。

【００２６】このステップＳ３のルーチンは、再帰構造
を持つルーチンであり、最大ブロック、またはこのブロ
ックを何度か分割した正方ブロック（これを処理対象ブ
ロックと呼び、処理の流れに応じてサイズが異なる。）
を、サブブロックに分割（４分割）した場合の総符号量
と、分割しない場合の符号量を比較し、ブロックを分割
するかどうかを選択し（図６参照）、ブロック分割情報
と符号化方法を示す情報情報を含む参照情報と、参照情
報に基づいて選択されたブロックを符号化した際の符号
量を出力する。

【００２７】図７は、ステップＳ３における最大ブロッ
ク（処理対象ブロック）の符号化方法と分割方法を選択
する際に用いる反復処理の流れを詳細に示したものであ
る。

【００２８】図７において、Ｓ30は処理対象ブロックの
サイズを調べるステップであり、処理対象ブロックが最
小ブロックサイズ（４×４画素）ならばＳ33に進み、違
う場合はＳ20及びＳ23に進む。

【００２９】Ｓ20は処理対象ブロックをコピーしてブロ
ックＡを生成するステップであり、処理対象ブロックを
ブロックＡとして、この反復処理のためのメモリ領域に
コピーする。Ｓ21はブロックＡを符号化した際の符号量
ＬＡが最小になる最適な符号化方法を選択するステップ
である。この選択の方法の詳細については後述する。

【００３０】Ｓ22はＳ21で選択された符号化方法を用い
た際の発生符号量ＬＡを出力するステップである。

【００３１】また、Ｓ23はＳ20と同様に処理対象ブロッ
クをコピーしてブロックＢを生成するステップであり、
Ｓ24はブロックＢを４分割してサブブロックを生成する
ステップ、Ｓ25は各サブブロックについてＳ21と同様に
最適な符号化方法（最適符号化方法）を選択するステッ
プである。

【００３２】Ｓ26は４つのサブブロックの夫々をＳ25で
選択された符号化方法を用いて符号化した際の符号量を
合計した総符号量ＬＢを出力するステップである。

【００３３】Ｓ27では、Ｓ22で出力されたＬＡと、Ｓ29
で出力されたＬＢを比較し、ＬＡ＜ＬＢならばＳ28へ、
ＬＡ≧ＬＢならばＳ29へ進むステップである。

【００３４】Ｓ28では、ブロックＡの処理対象ブロック
のサイズを符号化対象ブロックのサイズとして決定する
ステップであり、この処理対象ブロックの範囲に対する
ブロック分割方法を決定するための反復処理を終える。
この反復処理のＳ28において、ブロックＡ、即ち符号化
対象ブロックは、Ｓ21の符号化方法の選択の際に生成さ
れた後述する架空ブロックの画素値（誤差±ｅの範囲）
に書き換えられる。また、Ｓ31に進み、ブロックの分割
情報及びＳ21で選択された符号化方法と符号量ＬＡを参
照情報として生成する。

【００３５】Ｓ29では、４つのサブブロックブロックで
構成されるブロックＢを、この反復処理の始めに用いた
処理対象ブロックの範囲にコピーするステップであり、
４つのサブブロックの夫々を処理対象ブロックに置き換
え、上述のブロック分割方法を決定するための反復処理
を始めから繰り返す。

【００３６】Ｓ32では、最小ブロックサイズの処理対象
ブロックの最適符号化方法を選択する。Ｓ33では、その
際の符号量Ｌを出力する。Ｓ34では、符号化対象ブロッ
クはＳ32で生成された後述する架空ブロックの画素値に
書き換えられる。Ｓ35ではブロックに対応する最適符号
化方法と符号量Ｌを生成する。

【００３７】以上で、ステップＳ３における最大ブロッ
ク（または処理対象ブロック）の符号化方法とブロック
分割方法とを選択する際に用いる反復処理の流れの説明
を終わる。

【００３８】次に、ステップＳ21、Ｓ25、Ｓ32での最適
符号化方法の選択について詳細に説明する。

【００３９】図４は、最適符号化方法を選択する流れを
示す図である。ここでは選択可能な全符号化方法の符号
量を推定し、最適な符号化方法を選択する処理を行う。

【００４０】この符号量推定の処理の前に各々の方法に
適した形でブロックデータの書き換えを行う。図８にお
いて、Ｓ40は符号化方法＃０番により発生する符号量Ｌ
ｎ（０）を初期化するステップ、Ｓ41は予測値Ａ＋Ｂ−
Ｃを求めるステップ、Ｓ42は誤差±ｅの範囲でブロック
内の画素値を書き換えるステップ、Ｓ43は差分値に対す
るハフマン符号長をＬｎ（０）に１画素分加算するステ
ップ、Ｓ44はブロックの終端を判定するステップであ
り、ブロックを符号化した際の符号量が生成出来たらＳ
61に進む。

【００４１】この処理をmode０とすると、mode１〜mode
５は、各々＃１〜＃５番の符号化方法に対応する処理で
あり、上述と同様の処理を行う。

【００４２】Ｓ45は、符号化方法＃６番と＃７番の符号
化方法に関する初期化ステップであり近似平面とブロッ
ク内の画素値が完全に一致したかどうかを示すフラグ(F
LAG)を用意し、これを１（完全一致）に初期設定する。
また＃６番に対する符号長を示すパラメータＬｎ（６）
を０とし、＃７番に対する符号長を示すパラメータＬｎ
（７）をＬｎ（０）〜Ｌｎ（８）の中で最小値にならな
い程度の値に設定する。Ｓ46は、ブロック内の画素値を
誤差±ｅの範囲で変化させたらブロック内を同一画素値
にすることが可能かどうかを判定するステップ、Ｓ47は
先に説明した＃６のブロック近似平面Ｐ（ｘ，ｙ）＝ａ
ｘ＋ｂｙ＋c0を求めるステップ、Ｓ48は、誤差±ｅの範
囲で画素値を書き換え、架空ブロックを構成するための
画素値を生成する画素単位のステップ、Ｓ49は生成され
た画素値と近似平面Ｐ（ｘ，ｙ）との差分値に対するハ
フマン符号長をＬｎ( ６) に加算するステップである。
Ｓ50は、差分値( 予測誤差) が０であるかどうかを判定
するステップであり、ブロック内に１つでも近似平面と
異なる画素値が存在してしまう場合には、Ｓ51でFLAGが
０に設定される。またＳ52でブロックの終端を判定す
る。

【００４３】Ｓ53は、FLAGの値を判定するステップであ
り、FLAG＝０ならば、Ｓ49で生成された画素毎の差分値
の符号量と、近似平面Ｐ（ｘ，ｙ）を示すパラメータ
ａ，ｂ，c0（c0' ）の符号量とを加算しＬｎ（６）とし
（Ｓ54) 、Ｓ61に進む。

【００４４】FLAG＝１（近似平面とブロック画素値が完
全に一致している）ならば、近似平面の情報のみを符号
化すれば良いのでパラメータａ，ｂ，c0（c0')の符号量
をＬｎ（６）に置き換え（Ｓ55）、Ｓ61に進む。

【００４５】また、Ｌｎ（６）の値が求まる時には、Ｌ
ｎ（７）をＬｎ（０）〜Ｌｎ（８）の中で最小値になら
ない程度の値に設定する様にする。

【００４６】Ｓ56はc0（c0’) の符号量をＬｎ（７）の
値とすると共に、Ｌｎ（６）をＬｎ（０〜Ｌｎ（８）の
中で最小値にならない程度の値に設定する様にする。そ
してＳ64では、ブロック内の画素値が全てc0になる様
に、±ｅの範囲でブロックデータを書き換え（架空ブロ
ックを生成し）Ｓ61へ進む。

【００４７】Ｓ57は、ブロック内が２つの画素値で表さ
れているかどうかを判定するステップであり、２つの画
素値で表されている場合にはＳ58に進み、異なる場合に
は、Ｌｎ（８）をＬｎ（０）〜Ｌｎ（８）の中で最小値
にならない程度の値に設定し、Ｓ61に進む。

【００４８】Ｓ58は、画素値をランレングスに変換する
ステップである。Ｓ59は、このランレングスを符号化し
た際の発生符号量Ｌｎ( ８) を求め、Ｓ61へ進む。

【００４９】Ｓ61は、Ｌｎ（０）〜Ｌｎ（８）の値を比
較し、最小値及び対応する最適な符号化方法を選択する
ステップである。Ｓ62は、夫々のmode（mode０〜mode
８）において、±ｅの範囲で画素値を書き換えて生成さ
れた架空ブロックの内、Ｓ61で選択された符号化方法に
対応する架空ブロックを保存するステップであり、Ｓ63
は最適な符号化方法及び符号量を出力する。

【００５０】ステップＳ61の前までの処理が各方法の符
号量を求めるものであるが、これらは各々別のメモリ領
域に処理対象ブロック（またはサブブロック）をコピー
してから処理するものする。よって最適符号化方法を選
択する際のブロックデータの書き換えは元の処理対象ブ
ロックには影響しないものとする。

【００５１】ステップＳ40〜Ｓ44について詳細に説明す
る。ステップＳ40〜Ｓ44は、＃０番による発生符号量Ｌ
ｎ（０）を求めるものである。

【００５２】Ｓ41〜Ｓ44はブロック内の画素を左上から
順にラスタ処理するループであり、処理された画素（Ｓ
42で書き換えられた画素）は、以後の注目画素の参照画
素として元の画素値と置き換えられる。参照画素（Ａ，
Ｂ，Ｃ）が、Ｓ２で取り出す16×16画素のブロックの領
域外にある場合には、その前の最大ブロックのループ処
理（Ｓ２〜Ｓ７）までにＳ６で書き換えられたブロック
データの画素値を用いることになる。

【００５３】まず、ステップＳ40でＬｎ（０）には０が
設定される。ステップＳ41では着目画素値Ｘと周辺画素
値Ａ，Ｂ，Ｃから予測値（Ｐとする。）＝Ａ＋Ｂ−Ｃを
生成し、差分値（Ｄとする）＝Ｘ−Ｐを求める。ステッ
プＳ42では、（１）式により、修正差分値（Ｄ’とす
る）を求め、着目画素をＤ’＋Ｐに書き換える。（１）
式において↓ｘ↓は、小数点以下の切り捨てを表す。

【００５４】Ｄ’＝ ↓（Ｄ＋α）／（２ｅ＋１）↓ × （２ｅ＋１）・・・（１） α ＝（Ｄ／｜Ｄ｜） × ｅ・・・（２）図11は、ｅ＝３であり差分値Ｄが４となった場合の修正
差分値Ｄ’を例示したものである。図11に表す様に、差
分値Ｄ（−１０〜１０）の個数に比べ、差分値Ｄ’（−
７，０，７）の個数の方が少ないので、差分値を示す情
報が非常に減少することになる。また差分値が予測値と
完全に一致する可能性も高くなる。

【００５５】この例では、修正される画素値（修正画素
値Ｘ’とする）＝Ｘ＋３となる。ステップＳ43では、書
き換えられた修正画素値Ｘ’と予測値Ｐとの差分値、即
ち修正差分値Ｄ’を、処理対象ブロック（またはサブブ
ロック）のサイズ用のハフマンテーブルでハフマン符号
化し、発生した符号長をＬｎ（０）に加算する。ステッ
プＳ44でブロックの終端まで処理が終了したかどうかを
判断し、終了した場合にはステップＳ61へ処理を移し、
終了しない場合には次の画素に着目してステップＳ41か
らの処理を繰り返す。これにより＃０番の符号化方法を
用いた場合の発生符号量Ｌｎ（０）が求まる。また、＃
１番から＃５番までは予測方法のみことなるものであ
り、発生符号量Ｌｎ（１〜５）の求め方は＃０番の場合
と同様であるので、詳細な説明を省略する。

【００５６】次に、ステップＳ45〜Ｓ56、及びＳ64につ
いて詳細に説明する。ステップＳ45は＃６番と＃７番に
関し、変数の初期設定を行うステップであり、＃６番に
より発生する符号量Ｌｎ（６）に０を、＃７番により発
生する符号量Ｌｎ（７）に十分大きな値を設定する。ま
た、＃６番において差分値が全て０であるかどうかを判
定するために使用する変数FLAGに１を代入する。ステッ
プＳ46ではブロック内の画素値の最大値（ｍａｘ）と最
小値（ｍｉｎ）を求め、ｍａｘ−ｍｉｎが２ｅ＋１より
も小さい場合には＃７番の符号化方法に対応する処理
（ステップＳ56以降) へ分岐し、そうでない場合には＃
６番の符号化方法に対応する処理（ステップＳ47以降）
へ進む。

【００５７】ステップＳ47ではブロック内の画素値から
近似平面を求める。ステップＳ48からステップＳ52まで
はブロック内の画素値を順に処理するものであり、ステ
ップＳ48では、ブロック内の着目画素値Ｘと、ステップ
Ｓ47で求めた近似平面上で夫々の着目画素の位置に該当
する値Ｐから差分値Ｄ＝Ｘ−Ｐを求め、ステップＳ４２
と同様にして修正差分値Ｄ’を算出し、着目画素をＤ’
＋Ｐで書き換える。ステップＳ４９では、書き換えられ
た修正画素値Ｘ’と予測値Ｐとの差分値を、平面符号化
用のハフマンテーブルでハフマン符号化し、その符号長
をＬｎ（６）に加算する。

【００５８】ステップＳ５０は、修正画素値Ｘ’と予測
値Ｐとの差分値が０であるかどうかを判定し、０でない
場合にはステップＳ51でFLAGに０を代入する。ステップ
Ｓ52ではブロックの終端を判定し、終端でない場合に
は、ブロック内の次の画素についてＳ48から処理を続け
る。ステップＳ53は、FLAGの値を判定するステップであ
り、０ならばステップＳ54へ、そうでなければステップ
Ｓ55へ処理を移す。ステップＳ54では、ａ，ｂ，c0の符
号量にFLAG用の１ビットを加えたものをＬｎ（６）に加
算する。ステップＳ55では、ａ，ｂ，c0の符号量にFLAG
用の１ビットを加えたものを新たなＬｎ（６）の値とし
て代入する。

【００５９】また、ステップＳ46により＃７番の符号化
方法の利用が可能であると判断された場合には、ステッ
プＳ56で（ｍａｘ−ｍｉｎ）／２の商をc0として、c0を
符号化した際の符号量をＬｎ（７）に代入すると共に、
Ｌｎ（６）に十分大きな値を代入する。

【００６０】ステップＳ64ではブロック内の画素値を全
てc0に書き換える。これらの処理により＃６番及び＃７
番の符号化方法を用いた際の発生符号量Ｌｎ（６），Ｌ
ｎ（７）を求めることができる。

【００６１】次に、ステップＳ57〜Ｓ60について詳細に
説明する。ステップＳ57は、＃８番の符号化方法の使用
が可能であるかどうかを判定するステップであり、ブロ
ック内の画素値を調べ、出現する画素値が２つの値であ
ればステップＳ58に、そうでなければステップＳ50へ処
理を移す。

【００６２】ステップＳ50では、Ｌｎ（８）に十分大き
な値を代入する。ステップＳ58では、ブロック内の２つ
の画素値の内、輝度値の高い方を白、低い方を黒とし
て、図５に示す順序でスキャンし、白と黒のランレング
スデータに変換する。ステップＳ59では、出現する２つ
の画素値を表すための符号の符号量と、上述のランレン
グスデータを予め用意された＃８番専用のハフマンテー
ブルを用いてハフマン符号化したときの符号量とを加え
て、＃８番による発生符号量Ｌｎ（８）を求める。

【００６３】以上に説明した処理によって、＃０番から
＃８番までの符号化方法による発生符号量Ｌｎ（０）〜
Ｌｎ（８）が求まると、ステップＳ61で、これらの中か
ら最小値となる最小符号量を求め、この最小符号量と、
符号化方法を示す符号の符号量とを加えたものをブロッ
クの符号量ｌ（図７の符号量ＬＡ、または総符号量ＬＢ
を構成する４つの符号量の内の１つ、または符号量Ｌ）
として保存し、更に符号化方法の番号（ｉとする）を示
す情報も保存する。

【００６４】ステップＳ62では、番号ｉの符号化方法を
用いる際に生成された架空ブロックを保存する。この架
空ブロックはステップＳ28及びステップＳ34において符
号化対象ブロックを決定する（元の画素値と書き換え
る）際に用いられ、最終的にはステップＳ６のブロック
データの書き換えに用いられることになる。

【００６５】ステップＳ63では番号ｉと符号量ｌを出力
し、最適符号化方法の選択（図７のＳ21、Ｓ25、Ｓ32に
対応）処理を終わる。以上で、ステップＳ21、Ｓ25、Ｓ
32での最適符号化方法の選択についての説明を終わる。

【００６６】上述の処理により、ステップＳ３における
ブロック分割情報と最適符号化方法が決定する。

【００６７】図９は、ブロック分割方法と、分割された
各々の符号化対象ブロックに対して割る当てられる符号
化方法の一例を示す図である。この図５に基づく参照情
報を図10に示す。以上でＳ３に関する詳細な説明を終わ
る。

【００６８】次に、ステップＳ４では、Ｓ３で得られた
参照情報をメモリ上に保存する。

【００６９】ステップＳ５では、各符号化対象ブロック
に対して選択された符号化方法の番号ｉについて、各ブ
ロックサイズ毎に用意された符号化番号カウンタにより
符号化方法＃０〜＃８の出現回数をカウントすると共
に、＃０番から＃６番ならばその方法で符号化したとき
の修正差分値Ｄ’の出現回数を、符号化方法に対応する
カウンタ( ＃０番から＃５番ならば、各ブロックサイズ
に対応する予測符号化用カウンタ、＃６番ならば平面符
号化用カウンタ) に加算する。

【００７０】ステップＳ６では、ステップＳ３( Ｓ28、
Ｓ34に基づく。）において架空ブロックで書き換えられ
た符号化対象ブロックのデータを用いて、Ｓ２で取り出
したブロックの画素値を書き換える。

【００７１】ステップＳ７では、画像の終端を判定し、
画像の終端ブロックでなければ次のブロックについてス
テップＳ２からの処理を行い、終端であればステップＳ
８へ処理を移す。

【００７２】ここでＳ２〜Ｓ７までのループ処理は、ブ
ロック単位にブロックデータ（架空ブロック）を書き換
えて画像データとする処理である。よって、Ｓ３の符号
化方法の選択処理で用いる参照画素（Ａ，Ｂ，Ｃまたは
c0など）が、Ｓ２で取り出す16×16画素のブロックの領
域外にある場合には、その前のループ処理までにＳ６で
書き換えられたブロックデータの画素値を用いることに
なる。

【００７３】ステップＳ８では、16×16画素の予測符号
化用カウンタ、８×８画素の予測符号化用カウンタ、４
×４画素の予測符号化用カウンタ、平面符号化用カウン
タの値に基づき、16×16画素の予測符号化用ハフマンテ
ーブル、８×８画素の予測符号化用ハフマンテーブル、
４×４画素の予測符号化用ハフマンテーブル、平面符号
化用ハフマンテーブルを再構築する。また、各ブロック
サイズ毎に用意された符号化方法の番号カウンタによ
り、最適符号化方法＃０〜＃８の出現回数をカウント
し、このカウントの統計に基づいて、符号化方法の番号
を符号化するためのハフマンテーブルを構築する。

【００７４】ステップＳ９は、最適化処理ループ( Ｓ０
〜Ｓ８) の終了を判定し、予め設定された回数のループ
が終了した場合にはステップＳ９へ、そうでない場合に
はステップＳ０へと分岐する。この場合、初回の最適化
処理ループのＳ０と、２回目以降の最適化処理ループの
Ｓ０は処理が異なり、２回目以降のＳ０では前回のＳ８
で作成された最適ハフマンテーブルを基準ハフマンテー
ブルに代入して用いる。

【００７５】ステップＳ10では、保存されている参照情
報を参照し、Ｓ６で書き換えられた画像データを実際に
符号化する。図12は、ステップＳ10での符号化処理の流
れを示したものである。図12において、Ｓ80はハフマン
テーブルを符号化するステップ、Ｓ81は画像から最大サ
イズ（16×16画素）のブロックデータを取り出すステッ
プ、Ｓ82はこのブロックデータに対応する参照情報を取
り出すステップ、Ｓ83は参照情報に従ってブロックデー
タを符号化するステップ、Ｓ84は画像の終端を判定する
ステップである。以下に詳細な説明を記す。

【００７６】まず、ステップＳ80では、16×16画素の符
号化番号用ハフマンテーブル、８×８画素の符号化番号
用ハフマンテーブル、４×４の符号化番号用ハフマンテ
ーブル、16×16画素の予測符号化用ハフマンテーブル、
８×８画素の予測符号化用ハフマンテーブル、４×４の
予測符号化用ハフマンテーブル、平面符号化用ハフマン
テーブルについて、各ハフマンテーブルの構造を示した
情報をハフマンテーブル情報として出力する。

【００７７】ステップＳ81では、画像データから順に、
最大ブロックサイズでブロックデータを取り出す。ステ
ップＳ82では、ブロックデータに対する参照情報をメモ
リから取り出す。

【００７８】ステップＳ83では、参照情報と、参照情報
に従って最大ブロックサイズのブロックデータを符号化
したデータとを符号化データ列として出力する。

【００７９】ステップＳ84では画像の終端を判定し、未
処理のブロックがある場合には次のブロックについてス
テップＳ81から処理を行う。

【００８０】以上の処理により、画像データに対する符
号化データ列を生成し、出力する。

【００８１】以上で第１の実施の形態の説明を終わる。

【００８２】（その他の実施の形態）本願発明は、上述
の実施の形態に限定されるものではない。例えば、上述
の実施の形態では、最大ブロックサイズを16×16画素と
してブロックの分割を行ったが、128 ×128 画素等もっ
と大きなブロックサイズに設定しても構わない。

【００８３】また、ブロック分割の方法としてブロック
を同サイズに４分割する方法を挙げたが、ブロックサイ
ズを可変にしても良い。

【００８４】また、第１の実施の形態では図７の様に処
理対象ブロックの符号量とこれを４分割した複数のサブ
ブロック符号量とに基づいて、ブロック分割して符号化
対象ブロックを決定していたが、最大ブロック（16×16
画素）から最小ブロック（４×４）までの全てのブロッ
クについての符号量を求めてからこれら全ての符号量に
基づいてブロック分割しても良い。

【００８５】また、初めに最小ブロックの符号量を求
め、このブロックをサブブロックと見なし、図６の様に
４つのサブブロック（４×４画素）の総符号量とこれら
を合わせた領域のブロック（８×８画素）の符号量とに
基づき仮のブロック分割方法と符号量を決定し、４つの
決定された領域（８×８画素）の総符号量と決定された
領域（８×８画素）から構成される更に大きなブロック
（16×16画素）の符号量とに基づき新たに仮のブロック
分割方法を決定し、最大ブロックサイズまでこれを繰り
返すことにより符号化対象ブロックを決定する様にして
も良い。

【００８６】また、選択可能なブロック符号化方法とし
て予測符号化方法と平面符号化方法、ランレングス符号
化方法を用いたが、予測方法を変えるなどして適用方法
を変えたり、あるいはマルコフモデル符号化方法等、別
の符号化方法を用いても良いことは言うまでもない。更
に、上述の実施の形態では各符号化方法におけるエント
ロピー符号方法としてハフマン符号化を用いているが、
勿論これは算術符号化等、他のエントロピー符号化方法
を用いてもよい。

【００８７】また、Ｓ６ではブロックデータの書き換え
作業を行うことなく、このブロックデータを書き換えた
画像を符号化した際の予測誤差の値（Ｓ３で生成）を保
存しておくだけでも良い。この場合Ｓ10では、書き換え
られたブロックデータを用いて再度符号化するのではな
く、Ｓ３ですでに求められた予測誤差（修正差分値）の
値を用いて符号化すれば良いことになる。ただし、各画
素に対応する差分値を記憶すると、例えば図８のＳ41に
おける複数の画素値（Ａ，Ｂ，Ｃ）を参照して予測符号
化を行う様な処理に対し、これらの参照画素値を生成す
る回路構成、処理手順が複雑になる。よって第１の実施
の形態では、修正差分値を記憶する方法でなく、修正画
素値を記憶する方法を用いる。

【００８８】また、図13は第１の実施の形態の符号化処
理を行うための回路構成の一例を示したものであり、１
は画像データの符号化及び復号化をソフトウエア処理で
行うことができるＣＰＵ制御部、２は画像データを取り
込む画像入力部、３は画像データを印刷するプリンタ
部、４は画像データを表示する表示部、５はＣＰＵ制御
部１で符号化されたデータを送信、または外部機器から
送信された符号化データを受信することができる通信制
御部、６は画像情報を記憶する画像メモリである。

【００８９】

【発明の効果】以上の様に本願発明によれば、画像内の
画素値またはブロックを変換することにより、比較的簡
単な回路構成または処理手順を用いて、画像データを高
い圧縮効率で、かつ画素値の誤差が制御された符号化を
行うことができる。

【００９０】また、多値データを高い圧縮効率で、かつ
画素値の誤差を制御して符号化することができる。

【図面の簡単な説明】

【図１】本願発明に係る第１の実施の形態の処理の流れ
を示す図

【図２】符号化方法の種類、及び画素の位置関係を示す
図

【図３】符号化データ内の画像データの部分を表す図

【図４】ｃ０’のを符号化するためのハフマンコード表
を説明する図

【図５】＃８番の符号化方法の際にランレングスをスキ
ャンする方法を表す図

【図６】処理対象ブロックをサブブロックに分割する様
子を表す図

【図７】Ｓ３の処理の流れを説明する図

【図８】Ｓ２１、Ｓ２５、Ｓ３２の処理の流れを説明す
る図

【図９】最大ブロックの分割方法、及び符号化データ形
態の一例を示す図

【図１０】差分値を修正差分値に変換する様子を示す図

【図１１】Ｓ１０の符号化処理の流れを説明する図

【図１２】本願発明を実現するための回路構成の一例を
示す図

【図１３】第１の実施の形態を実現するための回路構成
を示す図

【符号の説明】Ｓ０基準ハフマンテーブルを設定するステップＳ１画像データを読み込むステップＳ２画像データから最大ブロックサイズでブロックデ
ータを取り出すステップＳ３ブロック分割方法及び符号化方法を決定するステ
ップＳ４参照情報を保存するステップＳ５符号化するデータについての統計を取るステップＳ６画像データを架空ブロックで書き換えるステップＳ７画像の終端を判定するステップＳ８最適ハフマンテーブルを生成するステップＳ９ループ終了を判定するステップＳ１０参照情報に従って実際に画像を符号化するステ
ップ

Claims

【特許請求の範囲】

【請求項１】画像の予測符号化を行う画像処理装置に
おいて、前記画像の画素値を予測する予測手段と、前記予測手段による予測の結果に基づいて、前記画像の
画素値を±ｅの範囲で変換する画像変換手段と、前記画像変換手段により変換された画像と、前記予測手
段による予測の結果とに基づいて、前記画像に関するパ
ラメータを符号化する符号化手段とを有することを特徴
とする画像処理装置。
【請求項２】前記予測手段による予測の方法は、複数
個存在することを特徴とする請求項１に記載の画像処理
装置。
【請求項３】前記画像に関するパラメータは、前記画
像変換手段により変換された画像の画素値と、前記予測
手段により予測された予測値との差分値であることを特
徴とする請求項１に記載の画像処理装置。
【請求項４】前記画像の画素値は多値で表されている
ことを特徴とする請求項１に記載の画像処理装置。
【請求項５】前記符号化手段による符号化は、画像の
ブロック単位に異なる処理を行うことを特徴とする請求
項１に記載の画像処理装置。
【請求項６】前記画像変換手段による変換は、画素値
の許容誤差を±ｅとして行うことを特徴とする請求項１
に記載の画像処理装置。
【請求項７】画像の予測符号化を行う画像処理方法に
おいて、前記画像の画素値を予測する予測ステップと、前記予測ステップでの予測の結果に基づいて、前記画像
の画素値を±ｅの範囲で変換する変換ステップと、前記変換ステップで変換された画像と、前記予測ステッ
プでの予測の結果とに基づいて、前記画像に関するパラ
メータを符号化する符号化ステップとを有することを特
徴とする画像処理方法。
【請求項８】画像をブロック画像毎に予測符号化する
画像処理装置において、前記ブロック画像に対応する予測パラメータを発生する
発生手段と、前記発生手段により発生した予測パラメータによる前記
ブロック画像の予測誤差が、所定値になる様に前記ブロ
ック画像を変換する変換手段と、前記変換手段により変換されたブロック画像を、前記発
生手段により発生した予測パラメータを用いて符号化す
る符号化手段とを有することを特徴とする画像処理装
置。
【請求項９】前記発生手段により発生した予測パラメ
ータは、ブロック内の各画素値に対応して存在すること
を特徴とする請求項８に記載の画像処理装置。
【請求項１０】画像をブロック画像毎に予測符号化す
る画像処理方法において、前記ブロック画像に対応する予測パラメータを発生する
発生ステップと、前記発生ステップで発生した予測パラメータによる前記
ブロック画像の予測誤差が、所定値になる様に前記ブロ
ック画像を変換する変換ステップと、前記変換ステップで変換されたブロック画像を、前記発
生ステップで発生した予測パラメータを用いて符号化す
る符号化ステップとを有することを特徴とする画像処理
方法。
【請求項１１】画像を、差分符号化方法を用いて符号
化する画像処理装置において、差分値の値を制限する制限手段と、前記画像の画素値に対する予測値を発生する予測手段
と、前記制限手段により制限された値と、前記予測手段によ
り発生した予測値とに基づいて前記画像の画素値を変換
する変換手段と、前記変換手段により変換された画素値と前記予測手段に
より発生した予測値との差分値を符号化する符号化手段
とを有することを特徴とする画像処理装置。
【請求項１２】前記差分符号化方法は、複数種類存在
することを特徴とする請求項１１に記載の画像処理装
置。
【請求項１３】前記制限手段により制限された差分値
は、複数個あり、この複数個の差分値が離散的な整数に
なる様に該差分値を設定することを特徴とする請求項１
１に記載の画像処理装置。
【請求項１４】画像を、差分符号化することが可能な
画像処理方法において、差分値の値を制限する制限ステップと、前記画像の画素値に対する予測値を発生する発生ステッ
プと、前記制限ステップで制限された値と、前記発生ステップ
で発生した予測値とに基づいて前記画像の画素値を変換
する変換ステップと、前記変換ステップで変換された画素値と、前記予測ステ
ップで発生した予測値との差分値を符号化する符号化ス
テップとを有することを特徴とする画像処理方法。
【請求項１５】多値データを入力する入力手段と、前記入力手段により入力された多値データを用いて差分
値を出力する出力手段と、前記出力手段で出力された差分値が許容誤差に対応する
所定値以内の間隔で離散的に配置した値になる様に、該
差分値を制御する制御手段と、前記制御手段により制御された差分値を符号化する符号
化手段とを有することを特徴とする画像処理装置。
【請求項１６】前記多値データは、多値画像データで
あることを特徴とする請求項１５に記載の画像処理装
置。
【請求項１７】前記差分値は、前記多値データから予
測される予測値と、前記多値データの値との差分値であ
ることを特徴とする請求項１５に記載の画像処理装置。
【請求項１８】前記制御手段による制御は、前記差分
値が離散的に配置される様にすることを特徴とする請求
項１５に記載の画像処理装置。
【請求項１９】前記符号化手段による符号化は、前記
制御手段により制御された差分値の統計に基づいて該差
分値をエントロピー符号化を用いることを特徴とする請
求項１５に記載の画像処理装置。
【請求項２０】多値データを入力する入力ステップ
と、前記入力ステップで入力された多値データを用いて差分
値を出力する出力ステップと、前記出力ステップで出力された差分値が許容誤差に対応
する所定値以内の間隔で離散的に配置した値になる様
に、該差分値を制御する制御ステップと、前記制御ステップで制御された差分値を符号化する符号
化ステップとを有することを特徴とする画像処理方法。