JPH0251978A - 画像符号化装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔目　次〕 撮要 産業上の利用分野 従来の技術（第５図、第６図） 発明が解決しようとする課題（第７図、第８図）課題を
解決するための手段（第１図） 作用 実施例（第２図〜第４図） 発明の効果 〔概　要〕 直交変換符号化方式による画像符号化装置に関し、 直交変換データの内容に対応して逆直交変換処理の高速
演算を実現し、画像データの復元処理の高速化を可能に
することを目的とし、 原画像データの直交変換を行なう直交変換部と、この直
交変換処理により得られた直交変換データに所定のビッ
ト割当てを行なって量子化し、量子化された直交変換デ
ータを画像蓄積部その他に送出する量子化部と、この量
子化された直交変換データを取り込みその逆量子化を行
なう逆量子化部と、この逆量子化処理により得られた直
交変換データの逆直交変換を行ない、復元画像データを
得る逆直交変換部とを備えた画像符号化装置において、
量子化された直交変換データから、そのビット割当てが
零でない部分を示す非零情報を抽出する非零抽出手段を
備え、逆直交変換部は、非零情報に対応した逆直交変換
を行なう複数の演算手段と、非零情報に応じてこの複数
の演算手段の一つを選択する選択手段とを含み構成する
。

〔産業上の利用分野〕 本発明は、直交変換符号化方式により画像データの符号
化を行ない、またその復号化により画像データの復元を
行なう画像符号化装置に関する。

特に、画像データの復元処理の高速化を可能にする画像
符号化装置に関する。

〔従来の技術〕

膨大な画像データを効率的に蓄積するためには、符号化
によるデータ量の圧縮が必要になる。この画像符号化方
式には各種の方式が提案されているが、圧縮率が高くか
つ復元画像の劣化が少ない高品質の画像符号化方式とし
ては、予測符号化、ブロック符号化、直交変換符号化、
ベクトル量子化などがある。

このような画像符号化方式の中で直交変換符号化方式は
、画像の性質や人間の視覚特性を効率よく利用して圧縮
率を高め、高品質化を図った優れた方式と言える。すな
わち、この直交変換符号化方式は、原画像データを直交
変換により空間周波数スペクトルのパラメータに変換し
た後に量子化し、復元はその逆の処理を行なうことによ
り、高圧縮率かつ高品質な画像符号化を可能にしている
。

第５図は、直交変換符号化方式の一つであるコサイン変
換方式を用いた従来の画像符号化装置の構成を示すブロ
ック図である。

図において、入力部５０１は、原画像５０３を例えば２
５６　Ｘ　２５６画素に標本化して圧縮部５１０に送出
する。圧縮部５１０では、入力された原画像データをブ
ロック分割部５１１に取り込み、例えば３２　Ｘ　３２
　（１０２４）個のブロックに分け、それぞれ８×８画
素の部分画像データとして、各ブロックごとにコサイン
変換部５１３および量子化部５１５を介してデータ圧縮
が行なわれる。

一般に、ＮＸＮ　（上述の例ではＮ＝８）画素の部分画
像データをｆ（ｍ、ｎ）（ｍ、ｎは０，１．２゜・・・
、Ｎ−１）とすると、コサイン変換部５１３では次式に
基づ（コサイン変換が行なわれる。

−・・−（１） ただし、ｕ、ｖは０，１，２．−、Ｎ−１ｃ（ｕ、ｖ）
＝　　　　　　（ｕ＝ｖ＝ｏ）＝　１　　（その他） このようにして得られたＮＸＮ画素に対応するＮＸＮ個
の２次元のコサイン変換データＦ（ｕ、ｖ）は、各ブロ
ックの部分画像データｆ　（ｍ、　ｎ　）に対する２次
元の空間周波数スペクトル分布を示すデータとなる。な
お、その分布は画像の種類に応じて統計的偏りを有する
。

続いて、量子化部５１５では、直交変換後のデータの統
計的偏りおよび人間の視覚特性の空間周波数に対する感
度その他を考慮し、コサイン変換データＦ（ｕ、ｖ）に
適当な量子化ビット数を割当て、量子化（符号化）によ
るデータ圧縮が行なわれる。

ここで得られた圧縮データ（量子化されたコサイン変換
データ）は、画像蓄積部５２１に蓄積される。また、蓄
積されたデータは所定の操作（例えば検索処理）に応じ
て復元部５３０に転送される。

復元部５３０では、量子化部５１５と逆の処理を行なう
逆量子化部５３１で、ＮＸＮ個のコサイン変換データＦ
’（ｕ、ｖ）が復号化され、続いて逆コサイン変換部５
３３で次式に基づ（逆コサイン変換が行なわれ、各ブロ
ックの復元部分画像データｆ’（ｍ、ｎ）が得られる。

ただし、ｍ、ｎは０，１，２．−、Ｎ−１このようにし
て得られたＮＸＮ画素の復元部分画像データｆ’（ｍ、
ｎ）は、もとの部分画像データｆ　（ｍ、　ｎ　）によ
く対応しており、各プロ・ンクごとの復元部分画像デー
タを例えば１０２４個得る二色により、表示部５０５に
はもとの原画像によく対応した２５６　Ｘ　２５６画素
の復元画像５０７を表示させることができる。

第６図は、このような画像符号化装置を用いた画像デー
タベースシステムの一例を示すブロック図である。

なお、第５図に示す画像符号化装置の各部と同様のもの
は同一符号で示す。

図において、原画像５０３はスキャナその他の入力部５
０１で読み込まれて圧縮部５１０に送出され、ここで圧
縮された画像データはホストコンピュータ５４１を介し
て画像データベース（画像蓄積部５２１）５４３に蓄積
される。画像データベース５４３に蓄積された画像デー
タは、ユーザからの要求によって検索されると、ホスト
コンピュータ５４１、通信網（ＬＡＮ、その他）５４５
を介して、転送効率を高めるために圧縮されたままの形
で各復元部５３０に転送され、表示部５０５には上述し
た復元処理により得られた復元画像５０７が表示される
。

〔発明が解決しようとする課題〕

ところで、このような直交変換符号化方式では、（１）
式および（２）式に示すように、２次元の画像データに
対して膨大な数の乗算と加算の各演算処理が必要であり
、直交変換およびその逆直交変換に伴う処理時間が長く
なる問題点があり、その高速化が要求されている。

この要求に応える高速化の一例として、例えば画像デー
タの逆直交変換処理では、（２）式に示す２次元逆コサ
イン変換の式を次式に示すように、縦方向と横方向の各
１次元逆コサイン変換に分解することにより、バタフラ
イ演算による高速演算アルゴリズムを利用した高速処理
が可能になっている。なお、（１）式においても同様で
ある。

このような高速演算アルゴリズムの利用により、演算回
数がＮ２のオーダからＮ　Ｉｏｇ２　Ｎのオーダになり
、従来においても相応の高速化が実現されているが、特
に第６図に示すような複数のユーザにより画像データベ
ースが検索されるシステムでは、復元処理の頻度が高く
なっており、その逆直交変換処理における一層の高速化
が望まれている。

ここで、圧縮部５１０の量子化部５１５で量子化された
直交変換データのビット割当ての状態、および逆コサイ
ン変換部５３３の処理に用いられる高速演算アルゴリズ
ムについて説明する。

第７図は、量子化されたコサイン変換データのビット割
当ての一例を示す図である。

図において、ｕ（０〜７）Ｘｖ　（０〜７）の各周波数
スペクトル成分には、０〜８ビツトのビット割当てが行
なわれる。例えば、Ｕ＝Ｏ１Ｖ＝０の直流スペクトル成
分には８ビツトが割当てられる。なお、量子化された直
交変換データにはビット割当てが「０」の部分が多く含
まれているが、これは、画像が近くの濃度どうしの相関
が一般的に高く、低周波スペクトルに情報が集中する傾
向にあるためである。

第８図は、１次元の高速逆コサイン変換アルゴリズムを
説明する図である。

図において、「・」は接点端子、「Ｏ」は加算演算であ
り、線上の正弦関数値、余弦関数値および「−１」の各
値は、それらの値がそれぞれ乗算されることを示してい
る。

ここで、その−例を示すと、出力Ｘは、となり、出力ｙ
は、 となり、出力２は −ｙ となり、この２と他方のルート（Ｆ′１、Ｆ’５、Ｆ’
３、Ｆ′７）から得られた同様の演算結果とにより、復
元部分画像データｆ′３およびＦ′４を算出することが
できる（文献：　　Ｗ、Ｈ，ＣＨＥＮ　、　Ｃ，Ｈ，Ｓ
ＭＩＴＨ、Ｓ、Ｃ。

ＦＲＡＬＩＣＫ　　、　　”　　Ａ　　　Ｆａｓｔ　　
　Ｃｏｍｐｕｔａｔｉｏｎ　　　Ａｌｇｏｒｉｔｂｍｆ
ｏｒ　　　Ｄｉｓｃｒｅｔｅ　　　Ｃｏ５１ｎｅ　　　
Ｔｒａｎｓｆｏｒｍ　　　　　Ｉ　　Ｅ　Ｅ　Ｅ丁ＲＡ
ＮＳＡＣＴＩＯＮＳ　　ＯＮ　　ＣＯＭＭＵＮＩＣＡＴ
ＩＯＮＳ、　　Ｖｏｌ、Ｃ０Ｍ−２５゜Ｎα９．　１９
７７）　　。

このような高速演算アルゴリズムにより、８個のコサイ
ン変換データＦ′。〜Ｆ’７から、８個の復元部分画像
データｆ′。〜ｆ′、を高速に算出することができるが
、この高速演算アルゴリズムでは、乗算回数がその処理
速度を大きく左右しているといえる。

したがって、Ｆ′。〜Ｆ′７がすべて非零であれば１６
回の乗算処理が必要となるが、例えばＦ’＋があらかじ
め「Ｏｊとわかっていれば、Ｆ’７に対応するｃｏｓ　
（７π／１６）と−５ｉｎ（７π／１６）の乗算は不要
となって乗算回数は１４回となり、乗算回数の削減に伴
う処理の高速化を実現できることがわかる。

なお、２次元のコサイン変換データＦ’（ＬＩＩＶ）か
ら、その復元部分画像データｆ′（ｍ、ｎ）を演算する
には、ｖ、ｎの各値ごとにｕ、ｍについて高速演算アル
ゴリズムを繰り返すので、その影響はさらに大きいと言
える。

本発明は、以上説明した直交変換データのビット割当て
の状況と、高速演算アルゴリズムの高速化への可能性と
を鑑み、直交変換データの内容に対応して逆直交変換処
理の高速演算を実現し、画像データの復元処理の高速化
を可能にする画像符号化装置を提供することを目的とす
る。

〔課題を解決するための手段〕

第１図は、本発明の原理ブロック図である。

図において、直交変換部１０１は、原画像データの直交
変換を行なう構成である。

量子化部１０３は、この直交変換処理により得られた直
交変換データに所定のビット割当てを行なって量子化し
、量子化された直交変換データを画像蓄積部その他に送
出する構成である。

逆量子化部１０５は、この量子化された直交変換データ
を取り込み、その逆量子化を行なう構成である。

非零抽出手段１１１は、量子化された直交変換データか
ら、そのビット割当てが零でない部分を示す非零情報を
抽出する構成である。

逆直交変換部１０７は、非零情報に対応した逆直交変換
を行なう複数の演算手段１１３と、非零情報に応じてこ
の複数の演算手段の一つを選択する選択手段１１５とを
含み、逆量子化処理により得られた直交変換データの逆
直交変換を行ない、復元画像データを得る構成である。

〔作　用〕

本発明は、量子化された直交変換データに、ビット割当
てが零である部分が多く含まれていることから、非零抽
出部１１１でビット割当てが零でない部分を示す非零情
報を抽出し、非零情報に対応した逆直交変換を行なう複
数の演算手段１１３の一つを、その非零情報に応じて選
択することにより、ビット割当てが零である部分に対す
る無駄な演算が回避され、逆直交変換処理の高速演算が
実現される。

すなわち、直交変換データの内容に対応した演算手段に
よる逆直交変換処理を行なうことにより、画像データの
復元処理の高速化を可能にすることができる。

〔実施例〕

以下、図面に基づいて本発明の実施例について詳細に説
明する。

第２図は、本発明画像符号化装置の要部構成の一例を示
すブロック図である。

ここでは、復元部の構成例を示すが、画像符号化装置を
構成する他の入力部、圧縮部（ブロック分割部、コサイ
ン変換部および量子化部）、および表示部は、第５図に
示す従来の画像符号化装置の各部と同等の構成である。

図において、画像蓄積部から転送される量子化されたコ
サイン変換データは、復元部の逆量子化部２０１に取り
込まれ、逆量子化（復号化）処理により所定のコサイン
変換データＦ’（ｕ、ｖ）が得られる。

この２次元のコサイン変換データＦ’（ｕ　＋　ｖ　）
は、縦方向および横方向ごとにそれぞれ逆コサイン変換
を行なう各１次元逆コサイン変換部２１０．２２０に順
次送出される。

各１次元逆コサイン変換部２１０．２２０ば、コサイン
変換データＦ’（ｕ、ｖ）の各方向ごとに後述する所定
の非零情報に対応して、それぞれ最小の演算回数により
逆コサイン変換を行なう複数の演算部２１１゜〜２１１
）ｌ−１，２２１゜〜２２１　Ｎ−。

と、その一つを選択するマルチプレクサ（ＭＰＸ）２１
３．２２３とを有し、バッファ回路２３１を介して接続
される。

また、画像蓄積部から転送される量子化されたコサイン
変換データは分岐して、各方向ごとにそのビット割当て
が零でない部分を示す非零情報を抽出する非零抽出部２
４１に取り込まれ、得られた各非零情報は選択制御部２
４３に送出される。

選択制御部２４３は、この非零情報に応じて、各マルチ
プレクサ２１３．２２３にそれぞれ対応する選択制御信
号を送出する。

なお、本実施例では、非零抽出手段（第１図、１１１）
として非零抽出部２４１を設け、逆直交変換部１０７の
演算手段（同、１１３）として、各演算部２１１゜〜２
１ＩＮ−７，２２１゜〜２２１Ｎ−１を設け、選択手段
（同、１１５）として選択制御部２４３およびマルチプ
レクサ２１３．２２３が設けられる。

第３図は、各１次元逆コサイン変換部２１０．２２０の
動作を説明する図である。

以下、第２図および第３図を参照して本実施例の動作に
ついて説明する。

まず、１ブロツクの量子化されたコサイン変換データの
処理の始めに、バッファ回路２３１が初期化される。

第３図（ａ）は、逆量子化部２０１で得られた２次元の
コサイン変換データＦ’（ｕ、ｖ）の状態を示す。

斜線で示すところは、ビット割当ての非零部分に対応す
る。ここで、ｕ、ｖはそれぞれＯｌｌ、・・・７とし、
各１次元のコサイン変換データをそれぞれＦ′。、Ｆ’
ｌ　、・・・、Ｆ′、とする。

非零抽出部２４１では、縦方向（Ｖ方向）の非零個数を
各Ｕごとに求め、さらに横方向（Ｕ方向）の最大非零個
数を求める。すなわち、Ｕ＝Ｏ１■、２．３．４に対す
るＶ方向の各非零個数５．４．３．２、■と、Ｕ方向の
非零最大個数５とを求め、非零情報として選択制御部２
４３に送出する。

選択制御部２４３では、この非零情報に基づいて各１次
元逆コサイン変換部２１０．２２０の所定の演算部を選
択するための選択制御信号を作成し、各マルチプレクサ
２１３．２２３に送出する。

なお、演算部２１１゜、２２１゜は、各１次元のコサイ
ン変換データＦ’ｏのみが非零である場合の逆コサイン
変換の演算処理を行ない、演算部２１１１．２２１１　
は、コサイン変換データＦ′。およびＦ’＋のみが非零
である場合の演算処理を行ない、以下同様に演算部２１
１？、２２１．は、コサイン変換データＦ′。〜Ｆ′７
のすべてが非零である場合の演算処理を行なう構成であ
る。

したがって、選択制御部２４３は、まずＵ＝０の列（Ｆ
’。〜Ｆ’４が非零）に対応する演算部として、１次元
逆コサイン変換部２１０の演算部２１１４を選択するよ
うにマルチプレクサ２１３を制御し、続いてｕ＝１．２
．３．４のそれぞれに対応して、各演算部２１１３．２
１１Ｋ、２１１．．２１１゜を選択させる。

この縦方向に対する逆コサイン変換の結果（第３図［有
］））は、バッファ回路２３１に一旦格納される。

次に、選択制御部２４３は、横方向（Ｕ方向）の非零最
大個数５に対応する演算部とし、１次元逆コサイン変換
部２２０の演算部２２１４を選択するようにマルチプレ
クサ２２３を制御し、バッファ回路２３１内のデータを
横方向に逆コサイン変換し、部分画像データｆ’（ｍ、
ｎ）（第３図（Ｃ））の復元を行なうことができる。

このように、各コサイン変換データの非零情報に応じて
、最小の演算回数により逆コサイン変換を行なう演算部
をそれぞれ選択することにより、全体としてその高速化
を実現することができる。

なお、以上説明した実施例では、非零情報の抽出を復元
部で行なう構成を示したが、画像データの符号化を行な
う圧縮部において、量子化されたコサイン変換データの
非零情報の抽出を行ない、その非零情報を蓄積データに
付加することにより画像蓄積部を介して復元部に通知し
、非零抽出部２４１がその情報を取り出す構成としても
よい。

また、選択手段（第１図、１１５）として、選択制御部
２４３から出力される選択制御信号によりマルチプレク
サ２１３．２２３を切り替える構成を示したが、その選
択制御信号に応じて所定の演算部の動作をイネーブルす
る構成としてもよい。

ここで、各１次元のコサイン変換データＦ′。〜Ｆ’ｔ
の・非零個数と、対応する演算部で行なわれる乗算回数
の関係を次表に示す。

なお、この表かられかるように、各非零情報に対応して
、それぞれ最小の演算回数により逆コサイン変換を行な
う演算部を設ける場合に対して、例えばＦ′。に対する
逆コサイン変換、Ｆ′。、Ｆ′１に対する逆コサイン変
換、Ｆ’、　、、７に対する逆コサイン変換、およびＦ
′。〜Ｆ′、に対する逆コサイン変換を行なう４個の演
算部に集約させても、ある程度の高速化を期待すること
ができる。

表 一般に、画像の濃淡変化の大小に応じて量子化ビット数
の割当てを変えてデータの圧縮率の向上を図っているが
、各ブロックごとのビット割当ての状態を４つのクラス
に分類し、それぞれのクラスに対応した逆直交変換処理
における乗算回数について、その−例を以下に示す。

第４図は、クラス分けされたビット割当ての状態を示す
図である。

第４図（ａ）は、非零部分がＵ＝Ｏ１Ｖ＝Ｏの斜線部分
であるビット割当ての状Ｂ（クラス１）を示す。この場
合の乗算回数は、■方向およびＵ方向に対して各１回の
合計２回である。

第４図（ｂ）は、非零部分がｕ＝０．ｌ、２，３、Ｖ＝
０．１，２．３の斜線部分であるビット割当ての状Ｂ（
クラス２）を示す。この場合の乗算回数は、■方向に対
して８＋６＋４＋１＝１９回、Ｕ方向に対して８　Ｘ　
４〜３２回の合計５１回である。

第４図（Ｃ）は、非零部分がｕ　＝　Ｏ〜７、ｖ−〇〜
７の斜線部分であるビット割当ての状態（クラス３）を
示す。この場合の乗算回数は、■方向に対して１６＋１
４＋１２＋１０＋　８　＋　６　＋　４　＋１〜７１回
、Ｕ方向に対して１６Ｘ　８〜１２８回の合計１９９回
である。

第４図（Ｃ）は、非零部分がｕ　＝　Ｏ〜７、■＝０〜
７のすべてであるビット割当ての状態（クラス４）を示
す。この場合の乗算回数は、各方向に対して１６回をＵ
方向およびＶ方向に各８回行なうために１６Ｘ　８　Ｘ
　２〜２５６回である。

なお、各ブロックごとの従来の乗算回数は、非零部分の
状態に左右されないために、クラス４と同様の２５６回
であった。

したがって、クラス当たりのブロック数が等しいければ
、平均して （２＋５１＋１９９＋２５６）／４　＝１２７となり、
従来の乗算回数２５６に比べて約半分になるので、逆直
交変換処理の大幅な高速化を実現することができる。

〔発明の効果〕

上述したように、本発明によれば、直交変換データの非
零情報に対応した逆直交変換処理が行なわれ、演算回数
の削減による高速化が実現されるので、直交変換符号化
方式により圧縮された画像データの復元処理を高速に行
なうことが可能になり、実用的には極めて有用である。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明画像符号化装置の要部構成の一例を示す
ブロック図、 第３図は各１次元逆コサイン変換部の動作を説明する図
、 第４図はクラス分けされたビット割当ての状態を説明す
る図、 第５図は従来の画像符号化装置の構成を示すブロック図
、 第６図は画像データベースシステムの一例を示すブロッ
ク図、 第７図は量子化されたコサイン変換データのビット割当
ての一例を示す図、 第８図は１次元の高速逆コサイン変換アルゴリズムを説
明する図である。 図において、 １０１は直交変換部、 １０３は量子化部、 １０５は逆量子化部、 １０７は逆直交変換部、 １１１は非零抽出部、 １１３は演算手段、 １１５は選択手段、 ２０１は逆量子化部、 ２１０．２２０は１次元逆コサイン変換部、２１１．２
２１は演算部、 ２１３．２２３はマルチプレクサ（ＭＰＸ）、２３１は
バッファ回路、 ２４１は非零抽出部、 ２４３は選択制御部である。 本庄ｇｔｌ倭理７−ｏ−，７０ 第１図 Ｃａ） ７つスラ６ゝ１丁３尺ヒ゛・、、Ｙ劃ち１山」（態、第 図 （Ｕ’） ｉ子Ｉｔｓ赦にコ塩゛ソ変換示−７のヒ゛７（−すゴ当
］）多“ｊ第７図

Claims (1)

【特許請求の範囲】
1. （１）原画像データの直交変換を行なう直交変換部（１
   ０１）と、 この直交変換処理により得られた直交変換データに所定
   のビット割当てを行なって量子化し、量子化された直交
   変換データを画像蓄積部その他に送出する量子化部（１
   ０３）と、 この量子化された直交変換データを取り込み、その逆量
   子化を行なう逆量子化部（１０５）と、この逆量子化処
   理により得られた直交変換データの逆直交変換を行ない
   、復元画像データを得る逆直交変換部（１０７）と を備えた画像符号化装置において、 前記量子化された直交変換データから、そのビット割当
   てが零でない部分を示す非零情報を抽出する非零抽出手
   段（１１１）を備え、 前記逆直交変換部（１０７）は、前記非零情報に対応し
   た逆直交変換を行なう複数の演算手段（１１３）と、前
   記非零情報に応じてこの複数の演算手段の一つを選択す
   る選択手段（１１５）とを含む ことを特徴とする画像符号化装置。