JPH0645948A - 直交変換装置及び逆直交変換装置 - Google Patents

Abstract

(57)【要約】 【目的】 所要ハード・ウエア量が少なく、かつＤＣＴ
の符号化効率に近い効率の直交変換装置及び逆直交変換
装置を可能にする。 【構成】 ４次の直交変換を［ｙi ］＝［ｔij］・［ｘ
j ］により実行し、変換行列［ｔij］のａ1 ，ａ2 の値
を、４次のＤＣＴの変換行列［ｄij］の各要素の値と異
ならしめた直交変換装置、及び、４次の逆直交変換を
［ｙi ］＝ｚ・［ｕij］・［ｘj ］により実行する逆直
交変換装置。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は画像や音声の高能率符号
化に用いる直交変換装置及び逆直交変換装置に関する。

【０００２】

【従来の技術】画像や音声のデジタル化に伴って、高能
率符号化技術が重要になってきている。高能率符号化の
有効な手段として、直交変換符号化がある。よく用いら
れる直交変換としてアダマール変換、ＤＣＴ（ディスク
リート・コサイン・トランスフォーメーション）等があ
る。

【０００３】次式は４次のＤＣＴに用いる変換行列［ｄ
ij］（ｉ、ｊ＝１、２、３、４）である。

【０００４】

【数１】

【０００５】ここで、Ｃｐ（ｐ＝１、２、３）は

【数２】 を表している。

【０００６】また、逆変換行列［ｖij］は

【０００７】

【数３】 ここでＴは転置行列であることを示す。

【０００８】４次のＤＣＴは４の入力データからなる列
ベクトル［ｘj ］に対して４ケの出力データからなる列
ベクトル［ｙi ］を次式によって求めるものである
（ｉ、ｊ＝１、２、３、４）。 ［ｙi ］＝［ｄij］・［ｘj ］ −−−（１） ところが、（１）式の演算では４ケの出力データを求め
るために１６個の多数の乗算が必要となる。このため乗
算回数を減少させる高速アルゴリズムが発表されてい
る。

【０００９】図３は４次の高速ＤＣＴ変換装置の構成図
であり、上記した（１）式の演算を具現化したものであ
る。

【００１０】同図中に示す破線は正負の反転を示してお
り、Ｃｉ、

【数４】 、１／２はＣｉ倍

【００１１】、

【数４】倍、１／２倍する乗算を示しており、矢印の交
点は加算を示している。１／２倍については右方向への
１ビット・シフトで結果が得られるため除いて考える
と、この場合３回の乗算が必要である。

【００１２】一方、アダマール変換は入力データの加算
と減算のみで変換を行うことができるためにＤＣＴに比
べて変換装置に必要となるハード・ウエアの量が小さく
てすむが、高能率符号化に利用する場合、入力データの
持つ情報を特定の出力データに集中させる効率がＤＣＴ
に比べて劣ることが知られている。

【００１３】

【発明が解決しようとする課題】以上のように、ＤＣＴ
では変換装置のハード・ウエア量が大きくなり、また、
アダマール変換では符号化効率が劣るという問題があっ
た。本発明はこのような従来技術の問題点を解決するこ
とを目的とする。

【００１４】

【課題を解決するための手段】上述した課題を解決する
ために、本発明は下記の構成になる直交変換装置及び逆
直交変換装置を提供する。

【００１５】４次の直交変換を、［ｙi ］＝［ｔij］・
［ｘj ］ 但し、［ｙi ］：４出力データからなる列ベクトル ［ｔij］：４行４列の変換行列 ［ｘj ］：４入力データからなる列ベクトル ｉ，ｊ：１、２、３、４ の演算により行う直交変換装置であって、前記変換行列
［ｔij］を構成する４行の内、２行分の各行の要素をａ
1 ，ａ2（実数）によって、 ａ1 ，ａ2 ，−ａ2 ，−ａ1 、 ａ2 ，−ａ1 ，ａ1 ，−ａ2 、 と配列し、かつ、前記ａ1 ：ａ2 を、ｍ：１またはｍ：
２（ｍは自然数）に設定したことを特徴とする直交変換
装置。

【００１６】上記した直交変換装置に対する逆直交変換
装置であって、４次の逆直交変換を、［ｙi ］＝ｚ・
［ｕij］・［ｘj ］ 但し、［ｙi ］：４出力データからなる列ベクトル ｚ：実数値 ［ｕij］：４行４列の変換行列［ｔij］の転置行列 ［ｘj ］：４入力データからなる列ベクトル ｉ，ｊ：１、２、３、４ の演算により行うことを特徴とする逆直交変換装置。

【００１７】

【実施例】本発明は前記した構成により比較的、所要ハ
ード・ウエア量が少なく、かつＤＣＴの符号化効率に近
い効率の直交変換装置を可能にするものである。さらに
各直交成分に対する最後の乗算を除いた乗算の乗数とし
て、簡単な自然数を乗数とした乗算と加減算を行なう構
成とすることでさらにハード・ウエア量を小さくするこ
とができる。 ［実施例 １］本発明の直交変換装置の一実施例になる
４次の直交変換の変換行列［ｔij］を次式に示す。

【００１８】

【数５】 ここで、ａ1 ：ａ2 ＝ｍ：ｎ として、ｍ＝２、ｎ＝１
である。

【００１９】本実施例の直交変換は、４つの入力データ
ｘ1 、ｘ2 、ｘ3 、ｘ4 よりなる列ベクトル［ｘj ］

【００２０】

【数６】 と、４つの出力データｙ1 、ｙ2 、ｙ3 、ｙ4 よりなる
列ベクトル［ｙi ］

【００２１】

【数７】 ただし、Ｔは転置を表わす。と変換行列［ｔij］によっ
て、 ［ｙi ］＝［ｔij］・［ｘj ］ −−−（２） で表わされる。

【００２２】また、逆変換を表わす行列［ｕij］を

【００２３】

【数８】 とする。

【００２４】図１は本発明の直交変換装置の一実施例構
成図であり、また、図３と同様の描き方であるので説明
は省く。

【００２５】さて、入力データや出力データ、及び、演
算途中のデータ等をすべて２の補数

【００２６】表示の２進デジタル値で表わす場合を考え
る。この時、データに乗ずる乗数が

【数９】 であるときには、データの符号ビットを拡張しながらｎ
ビットだけ左（ｎが正の時）あるいは右（ｎが負の時）
方向にデータをシフトすれば良いことが知られている。

【００２７】例として、乗数２とデータ５の乗算を考え
る。データ５を８ビットの２の補数表示の２進デジタル
値で表わすと、

【００２８】

【数１０】 である。２×５は符号ビットを残して、他のビットを
１ビット左方向にシフトし、空いたビットに０を入れる
ことで得られる。すなわち

【００２９】

【数１１】 である。が空いたビットに入れた０である。

【００３０】同様に、乗数

【数１２】 とデータ（−５）の乗算は、データ（−５）が

【００３１】

【数１３】 であり、４×（−５）は符号ビットを残して、他のビ
ットを２ビット左方向にシフトすることで得られる。す
なわち

【００３２】

【数１４】 である。が空いたビットに入れた０である。

【００３３】以上のことから、データに乗ずる乗数が

【数９】であるときには、そうでない場合（特に乗数を
２進デジタル値で表した時に値が１のビットの数が多い
場合）に比べ、乗算のためのハード・ウエアが小さくな
るというのは自明である。図１の構成はこのことを利用
したものである。

【００３４】すなわち、直交成分ｙ1 、ｙ2 、ｙ3 、ｙ
4 を得るための最後の乗算を除けば、残りの乗算である
２倍は上記のビット・シフトで結果を得ることができ
る。また１／２倍については図３と同様に除いて考え
る。

【００３５】従って、図１ではハード・ウエア規模の大
きい乗算器の数を２ケにすることができ、４次のＤＣＴ
に比べよりハード・ウエア量の小さい直交変換装置を提
供できる。さらに図１では直交成分ｙ2 、ｙ4 を得るた
めの最後の乗算の乗数として

【００３６】、

【数１５】 の無理数を示しているが、これを８１／２５６等で近似
しても良い。 また入力データを画像データとして、垂
直４画素、水平４画素の入力データからなるブロック
［ｘij］に対して、本発明の変換を２次元に拡張して行
った結果を垂直４データ、水平４データからなるブロッ
ク［ｙij］とすると

【００３７】

【数１６】 である。従って、図１の変換を２回行なえばよいが、そ
の場合、変換全体で２×４×２＝１６ケの乗算器が必要
となる。これに対して、図１の各出力ｙj に対する最後
の乗算を省いた演算に等価な変換の変換行列を［ｔ’i
j］とすると

【００３８】

【数１７】 この［ｔ’ij］によって

【００３９】

【数１８】 を求め、その結果の垂直４データ、水平４データからな
るブロック［ｙ’ij］に対して、各ｙ’ij毎にｙ’ij＝
ｙijにするための乗算を行なう構成にすることで、全体
の乗算器の数を１２ケに減らすことができる。

【００４０】次に、前記逆変換行列［ｕij］を用いた逆
変換の場合は、上記の直交成分ｙ1

【００４１】、ｙ2 、ｙ3 、ｙ4 を得るために乗じた最
後の乗数

【数１５】、１／２をまず入力データに対して乗じ、そ
れらの乗算結果に対して前記［ｔ’ij］の行列の転置行
列で表される演算を行なうことで、以上で述べた変換の
場合と同様に乗算器の数を減らすことができる。

【００４２】図２は本発明の逆直交変換装置の一実施例
構成図である。

【００４３】ところで、一般的に人間の視覚や聴覚は高
域の歪に対してより鈍感である。このため高能率符号化
では低域を表わす直交成分に対して大きな重みづけを行
い、高域を表わす直交成分については小さな重みづけを
することが多い。そのための重みづけの乗算を前記直交
変換の出力データに対して行なっても良いが、図１の直
交成分ｙ1 、ｙ2 、ｙ3 、ｙ4 を得るための最後の乗算
と共用することも可能である。

【００４４】この時、図１のｙ1 、ｙ2 、ｙ3 、ｙ4 を
得るための最後の乗算の乗数を

【数１５】、１／２と重みづけのための乗数を乗じた値
とすれば良い。このようにすることで、高能率符号化全
体の演算量をさらに少なくし、符号化装置のハード・ウ
エア量を減らすことが可能である。

【００４５】また、本実施例の直交変換を２次元に拡張
し、画像の高能率符号化に適用したところ、その効率は
２次元の４次ＤＣＴに比べ若干劣るものの、２次元の４
次アダマール変換に比べると良い結果が得られた。 ［実施例 ２］本発明の第２の実施例の、４次の疑似直
交変換の変換行列［ｔij］を次式に示す。

【００４６】

【数１９】 ここで、ａ1 ：ａ2 ＝ｍ：ｎとして、ｍ＝５、ｎ＝２で
ある。本実施例の場合も、図１と同様に変換装置の構成
を直交成分ｙ1 、ｙ2 、ｙ3 、ｙ4 を得るための最後の
乗算を除いて、他の乗算を５倍と２倍にする。５倍＝４
倍＋１倍であるから、前記のビット・シフトと１回の加
算で乗算結果を得ることができる。従って、実施例１と
同様にハード・ウエア規模の大きい乗算器の数を２ケに
することができ、４次のＤＣＴに比べ、よりハード・ウ
エア量の小さい直交変換装置を提供できる。

【００４７】上述したように、本発明は、特に、次の
(1) 〜(3) に特徴がある。 (1) 上記した変換行列［ｔij］の各行各列における要素
比ａ1 ：ａ2 が簡単な自然数比ｍ：ｎにおけるｎが１ま
たは２であること (2) ［ｙi ］＝［ｔij］・［ｘj ］による直交変換にお
ける変換行列［ｔij］の第２，４行と列ベクトル［ｘj
］との演算の最後の乗算を除いた演算が、 ｍ・（ｘ1 −ｘ4 ）＋ｎ・（ｘ2 −ｘ3 ） ｎ・（ｘ1 −ｘ4 ）＋ｍ・（ｘ2 −ｘ3 ） を求めるための演算であること

【００４８】

【発明の効果】本発明の直交変換装置は、上記したよう
に、４次の直交変換に係わる４行４列の変換行列［ｔi
j］のａ1 ，ａ2 の値を４次のＤＣＴにおける変換行列
［ｄij］の各要素の値と異ならしめたから、４次の直交
変換における高能率符号化に利用した時の効率が４次の
ＤＣＴとほぼ同程度で得られ、また、直交変換装置のハ
ードウェア量をＤＣＴのそれに比べて小さくすることが
できる効果がある。

【００４９】また、本発明の逆直交変換装置は、上記し
たように、４次の逆直交変換に係わる４行４列の変換行
列［ｔij］の転置行列を［ｕij］としたから、４次の逆
直交変換における高能率符号復号化に利用した時の効率
が４次の逆ＤＣＴとほぼ同程度で得られ、また、逆直交
変換装置のハードウェア量を逆ＤＣＴのそれに比べて小
さくすることができる効果がある。

【図面の簡単な説明】

【図１】本発明の直交変換装置の一実施例構成図であ
る。

【図２】本発明の逆直交変換装置の一実施例構成図であ
る。

【図３】４次の高速ＤＣＴ変換装置の構成図である。

【符号の説明】

ａ0 ，ａ2 行列要素 ［ｄij］ ＤＣＴにおける４行４列の変換行列 ［ｔij］ ４行４列の変換行列 ［ｕij］ ４行４列の変換行列［ｔij］の転置行列 ［ｘj ］ ４入力データからなる列ベクトル ［ｙi ］ ４出力データからなる列ベクトル ｚ 実数値

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成４年９月７日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】００３６

【補正方法】変更

【補正内容】

【００３６】

【数１５】の無理数を示しているが、これを８１／２５
６等で近似しても良い。また、最後の乗算の乗数の大き
さを所定の範囲内の値とするために、最後の乗算の乗数
を２^Ｂ倍（Ｂは整数）し、最後の乗算を除いた乗算の乗
数を２^−Ｂ倍した値としても良く、その場合でも、最後
の乗算を除いた乗算をビット・シフトと加算によって行
なうことができるのは当然である。さらに、入力データ
を画像データとして、垂直４画素、水平４画素の入力デ
ータからなるブロック［ｘｉｊ］に対して、本発明の変
換を２次元に拡張して行った結果を垂直４データ、水平
４データからなるブロック［ｙｉｊ］とすると

Claims (2)

【特許請求の範囲】
1. 【請求項１】４次の直交変換を、［ｙi ］＝［ｔij］・
   ［ｘj ］ 但し、［ｙi ］：４出力データからなる列ベクトル ［ｔij］：４行４列の変換行列 ［ｘj ］：４入力データからなる列ベクトル ｉ，ｊ：１、２、３、４ の演算により行う直交変換装置であって、 前記変換行列［ｔij］を構成する４行の内、２行分の各
   行の要素をａ1 ，ａ2（実数）によって、 ａ1 ，ａ2 ，−ａ2 ，−ａ1 、 ａ2 ，−ａ1 ，ａ1 ，−ａ2 、 と配列し、かつ、 前記ａ1 ：ａ2 を、ｍ：１またはｍ：２（ｍは自然数）
   に設定したことを特徴とする直交変換装置。
2. 【請求項２】請求項１記載の直交変換装置に対する逆直
   交変換装置であって、 ４次の逆直交変換を、［ｙi ］＝ｚ・［ｕij］・［ｘj
   ］ 但し、［ｙi ］：４出力データからなる列ベクトル ｚ：実数値 ［ｕij］：４行４列の変換行列［ｔij］の転置行列 ［ｘj ］：４入力データからなる列ベクトル ｉ，ｊ：１、２、３、４ の演算により行うことを特徴とする逆直交変換装置。