JPS61294585A - 画像信号の変換符号化方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は画像信号の符号化に関する。

（従来の技術） 変換符号化、とくに直交変換を用いた符号化は画像信号
の冗長性を大巾に除去でき能率が高いことが知られてい
る。しかしながら、変換を行うための演算が膨大なため
、各種の高速演算法が提案されるほどである。フーリエ
変換の場合を例にとるとクーリーとチューキイ（Ｃｏｏ
ｌｅｙ　ａｎｄ　Ｔｕｋｅｙ）による高速フーリエ変換
（ＦＦＴ）やライノブラード（Ｗｉｎｏｇｒａｄ）によ
るＦＦＴが良く知られている。画像信号の符号化におい
てはその実部を用いるコサイン変換が用いられることが
多いが、これに対しても高速演算法が考案されている。

たとえば、ウェア・シラン・チェノ（Ｗｅｎ−Ｈｓｉｕ
ｎｇ　Ｃｈｅｎ）他による論文「アファーストコンビュ
テイショナルアルゴリズム７ォーザディスクリートコサ
イントランスフォームＪ　（”Ａ　Ｆａｓｔ　Ｃｏｍｐ
ｕｔａｔｉｏｎａｌ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔ
ｈｅＤｉｓｃｒｅｔｅ　Ｃｏ５１ｎｅ　Ｔｒａｎｓｆｏ
ｒｍ”、　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ
Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、　ｖｏｌ、　Ｃ０Ｍ−
２５，Ｎｏ、９．　Ｓｅｐｔｅｍｂｅｒ１９７７　）に
高速離散コサイン変換の算法が述べられている。

（発明が解決しようする問題点） これらの高速算法は、いずれにせよ全ての変換係数を求
めるための算法であるため、画像の低ビツトレート符号
化において頻繁に行われる微小な値をもつ変換係数の切
捨てにより特定の菫（通常はゼロ）となることが多い場
合には無駄な演算をしていることになる。また、高速演
算法を用いても所要演算法は依然として多く、これを２
１−ドウエアにて実現すると相当複雑でかつ大きなもの
となる。本発明は変換に要する演算を大幅に減らしハー
ドウェア化が容易な変換方式を提供することを目的とす
る。

（発明の構成） 本発明によれば、画像信号を変換し、得られる変換係数
を量子化し符号化するに当り、量子化により特定の値に
集中することが多い変換係数を含むあらかじめ定められ
た変換係数については変換に際して実行される演算を省
略することを特徴とする画像信号の変換符号化方式が得
られる。

（発明の原理） 任意の２次元変換（Ｃ）を用いてＮライン×Ｎ画素毎に
ブロック化された画像（Ｘ）を変換した結果をＦとする
時、ＦとＸの関係は一般に Ｆ：ｃ、ｘ、ｃ’ｒ で表わされる。Ｆは２次元の変換係数行列（以下変換係
数と略記する。）である。通常の符号化ではこのＦは量
子化されて取り得る値に制限を受ける。また、この量子
化した結果を伝送する場合にはとくにゼロが多いと情報
量が少なくなり都合が良い。

変換係数Ｆは、画像自身のもつスペクトル特性を周波数
に対応付ける時、低周波領域にエネルギーが集中し、高
周波領域のエネルギーは小さいのが普通であり、この高
域成分を表わす変換係数の値は小さく量子化によりゼロ
となることが多い。この高域成分に対応する係数は、複
雑な柄をもつ画面を変換した場合にのみ大きくなること
がある。

したがって、複雑な柄の画像が入力された時に高域成分
に対応する係数がゼロとなった時の、逆変換後の再生画
像の若干のボケを許容するとこの高域成分に対応する係
数を得るに必要な演算は省略することができる。たとえ
ば、第１図に例として示すように変換係数Ｆの左上隅（
ＤＣ成分に相当）を含むｎＸｎの領域（斜線部）に含ま
れる低域成分のみ符号化すれば良いものとするとＮライ
ン×Ｎ画素のブロックからなる画像（Ｘ）に対して変換
マトリックスＣは斜線で示した部分以外は全てゼロとす
ることができる。ＣＴはマトリックスＣの転置である。

すなわち、第１図に示すようにＣ，Ｘ−ＣＴなる行列演
算を行った結果は左辺のＦの斜線部以外はすべてゼロと
なる。この時のＸ、ＣＴの演算数、たとえば乗算数はＣ
の斜線部に含まれたものだけで済むため、ｎＸＮｘＮ回
である。したがってＣ，Ｘ−ＣＴの演算に現われる乗算
数は２ｎＸＮＸＮ回である。全ての係数を算出するもの
と仮定すると、Ｃ，Ｘ−ＣＴの演算には２Ｎ３の乗算が
含まれることになる。

また、信号の変換を実行するに際してはたとえばフーリ
エ変換におけるＦＦＴのように、高速演算が適用される
ことが多い。変換として１６次の離散コサイン変換（Ｄ
ＣＴ）を用いた時の、チェノ（Ｗ、Ｈ，Ｃｈｅｎ。

Ｖ、Ｓ、Ｐａｔｅｎｔ　４．３８５．３６３．　Ｍａｙ
　２４．１９８３）による高速ＤＣＴ算法の例を第２図
に示す。Ｘｏ−Ａ’１５は一次元の入力信号で、Ｆｏ−
Ｆ１ａは一次元のＤＣＴにより得られる係数を表わす。

第２図に示されている計算は、たとえば第１図における
変換マトリックスＣを画像Ｘの中の任意の１行に対して
適用した場合を示す。したがってＸ−ＣＴの演算におい
ては、第２図の例をＮ回にわたり順次具なる画像Ｘの行
に適用することになる。ＣＴにおいて、左側のｎ列のみ
ゼロでない場合には第２図における演算結果Ｆ１５から
Ｆｎまでの変換結果は結果として全てゼロにされるため
計算する必要がない。

Ｆ１ａからＦｎまでの演算にのみ用いられている乗算は
第２図によると、ｎ＝４として合計２４回になり、Ｆ１
ａからＦｏまでの全ての計算した時の乗算数（４８）の
１／２となる。すなわち、チェノによる高速算法を用い
た時で画像Ｘの各行に対する計算ではｎ＝４すなわちｎ
／Ｎ　＝　１／４の時に乗算数は１／２となる。高速算
法を用いずに直接計算すると２ｎ　Ｘ　Ｎ２／２Ｎ３＝
　ｎ／Ｎ　＝　１／４となる。以上はＸ、ＣＴの演算に
ついて説明したが、Ｃ０Ｘ、ＣＴについても同様に高速
算法を用いると１／２、直接計算すると１／４となる。

他の例として、ｎ＝８のときには高速算法では乗算数は
、１６回だけ減少できるので（４８−１６）／４８＝２
／３となる。直接計算すると８１１６＝１１２となる。

この演算回数の減少は、変換回路を構成する場合には使
用する乗算器の数の減少に対応する。

（実施例） 以下図面を参照しながら実施例について詳しく説明する
。第３図に本発明に関る符号化・復号化装置の全体ブロ
ック図に示す。図において、画像信号は線１０００を介
して走査変換回路１０に入力され、ブロック化される。

ブロックの大きさは一般的にはＮＸＮの正方形でかつＮ
は２のべき乗がよく用いられる。このブロック化された
画像信号は線２０００を介して直交変換回路２０へ供給
され、ＮＸＮの直交変換をうける。この時、第１図に示
したように左上隅のｎＸｎの係数を得るに必要な計算の
み実行される。

この直交変換回路２０については後に詳述する。直交変
換回路２０の出力である変換係数は線３０００を介して
、量子化器３０へ供給され、量子化される。この時、左
上隅のｎｘｎの変換係数以外は常にゼロとなっている。

量子化された変換係数は線４０００を介して符号変換回
路４０に供給され、たとえばハフマン符号のような能率
の良い符号で表現される。符号変換回路４０については
後に詳述する。符号変換された変換係数は線５０００を
介して受信側の符号逆変換回路５０に供給される。線５
０００は、伝送システムにおいては伝送路であり、記録
・再生システムにおいては記録媒体である。この符号逆
変換回路５０についても後に詳述する。符号逆変換され
た変換係数は線６０００を介して直交逆変換回路６０に
おいて直交逆変換され、時間領域の画像信号に復元され
る。この復元された画像信号は線７０００を介し、走査
逆変換回路７０に供給され、ここでブロック化されてい
る信号は元の時系列に従った画像信号に走査逆変換され
る。そして、受信側における復号された画像信号として
線８０００を介して出力される。

つぎに、第４図及び第５図を参照しながら、直交変換回
路２０の構成について説明する。簡単のため、Ｘ−ＣＴ
の演算において第１，２行（各々Ｘ□４．ｘ−する。た
だし１≦ｊ≦Ｎとする。）とＣＴ（ｊ行、ｉ列にある画
素をＣｊｉと略記する）との演算について説明する。あ
る時刻においてシフトレジスタａ（ＳＲａと略記）２１
０にＸｌｌ〜ＸＩＮなるＸの第１行の画像信号が格納さ
れているものとする。ここで５Ｒａ２１０は画像信号を
１サンプルづつ直列にシフトし、Ｎサンプルづつ並列に
出力可能な構成になっているものとする。このＮサンプ
ルの画像信号は線２１００を介して並列にスイッチ２２
０に供給される。スイッチ２２０では、５Ｒａ２１０か
らの画像信号が選択され、線２０３０を介して積和回路
２３０に供給される。積和回路２３０においては、係数
メモリ２４０から線４０３０を介して並列に供給される
第１列の係数と画像信号Ｘとの間で積和演算、たとえば
Ｘの第１行とＣＴの第１列の場合には ΣＸ１７　’　ＣＪｌ・ Ｊ虐ｌ を実行し、その結果を線３０５０を介してバッファメモ
リ２５０へ供給する。第４図の例では写、・５・ｃ。

などのＮ個の積和計算（正確にはＮ個の積と（Ｎ−１）
個の和）が一度に並列に実行される場合を例にとってい
る。このＸの第１行についてＣＴの第２列から第ｎ列ま
での積和演算が続けて実行されるが、この間にＸの第２
行の画像信号がシフトレジスタｂ（ＳＲｂと略記）２１
１に線２０００を介して供給され直列にシフトされた後
に線２１１０を介してＮサンプル並列出力をする。そし
て、Ｘの第１行についての演算が終了すると、スイッチ
２２０は５Ｒｂ２１１の出力を選択し、Ｘの第１行に対
するのと同様の積和演算を行い演算結果を線３０５０を
介して出力する。こうして得られる画像信号ＸのＸ、Ｃ
Ｔによる変換結果は−たんバッファメモＩＪ　２５０に
格納され、つぎに行われるＣ・（Ｘ−ＣＴ）の演算時に
線５０６０を介して出力される。このバッファメモリ２
５０は、Ｘ−ＣＴの演算結果が、１−Ｎの順序の各列に
ついてまず行方向に実行されて得られるものであれば、
いわゆるｆｉｒｓｔ−ｉｎ　ｆｉｒｓｔ−ｏｕｔメモリ
で実現できるが、もし反対に１〜Ｎの順序の各行につい
てまず列方向に実行されて得られる場合には入力データ
と出力データの関係が２次元マトリックスの転置関係に
なるようにして読みだされる。いわば、走査線を変換す
る機能をもったメモリで実現される。

このバッファメモリ２５０の出力は線５０６０を介して
シフトレジスタｅ（ＳＲｃと略記）２６０またはシフト
レジスタｄ（ＳＲｄ）２６１のいずれかに供給され、直
列シフトがなされる。、５Ｒｃ２６０と５Ｒｄ２６１は
５Ｒａ２１０と５Ｒｂ２１１の関係と同一の動作を行う
。すなわち５Ｒｃ２６０が入力および直列シフトで用い
られている時には５Ｒｄ２６１はＮデータを線２１６０
を介して並列出力し、逆に５Ｒｄ２６１が入力直列シフ
トで用いられている時には５Ｒｃ２６０はＮデータを線
２６００を介して並列出力することになる。スイッチ２
７０はこの２系統のＮデータの並列出力を選択し、線７
０８０を介して積和回路２８０へ供給する。積和回路２
８０の動作は先の積和回路２３０と同一で、Ｘ、ＣＴの
演算結果と係数メモリ２９０より線９０８０を介して供
給される係数ＣｉｊとのＮ個の積和演算を行う。こうし
て得られた変換係数Ｆは、線３０００を介して量子化器
３０へ供給される。

次に第５図を用いて、係数メモリ２４０の構成と動作に
ついて説明する。簡単のために第１図におけるｎ＝４と
して説明するが、４以外でも勿論以下の説明は当てはま
るメモリＡ２４２にはＣｊｌ（ｊ＝１〜Ｎ）がメモリＢ
２４３にはＣｊ２、メモリＣ２４４にはＣｊ３．メモリ
Ｄ２４５にはＣｊ４、がそれぞれ格納されている。Ｘ−
ＣＴの演算において、まず第１行、第１列目の演算を行
う時には、メモリＡ２４２がセレクタ２４１により選択
され、線４２４１および線４０３０を介してＮ個の係数
Ｃｊｌ（ｉ：１〜Ｎ）が出力され、ｘ、ｊ（ｊ＝１〜Ｎ
）と積和演算がなされる。

以下同様に、たとえば第１行、第２列目の演算を行う時
にはメモリＢ２４３が選択され線４３４１と４０３０を
介してＮ個の係数が出力される。この係数メモリＡ−Ｄ
においては、加算あるいは減算のみを実行する場合には
該当する係数を＋１あるいは−１とすれば良いというこ
とは明らかである。

つぎに、第６図及び７図を参照して前述のチェ２による
高速アルゴリズムに対して本発明を適用した場合の実施
例について説明する。

走査変換されてブロック化された画像信号は線２０００
を介してまずバッファ８１０に供給される。このバッフ
ァ８１０は第４図中の５Ｒａ２１０．５Ｒｂ２１１およ
びスイッチ２２０からなっており、Ｎデータを並列出力
し、次の演算器ａ８２０に供給する。演算器ａ８２０〜
演算器ｅ８２４と演算器ａ’　８４０〜演算器ｅ’　８
４４の各演算器はすべて第７図に示す基本構成で実現す
ることができる。すなわち、入力信号（Ｎ並列）を分配
８０１により振り分けて出力し、これに対して係数器８
０３より供給される係数（最大で２Ｎ並列）を乗算器８
０２において乗じ、その結果は加算器８０４において加
算され、１段分の演算が終了する。これを、第２図を用
いて説明する。第１段においては、入力データＸ。〜Ｘ
１゜（Ｎ、＝１６とする）の並びかえを分配器８０１に
おいて行い、加算に対しては＋１、減算に対しては−１
なる係数を与えて乗算および加算を行うことにより処理
が終了する。この分配器８０１はＮデータの並列入力に
対し、並び換えた後に最大で２Ｎデータの並列出力が可
能であることが必要である。また乗算器８０２は最大で
２Ｎ並列の乗算が実行可能とする。同様に加算器８０４
も最大でＮ並列の加算が可能なものとする。第２図を実
現するための構成としては、第１゜２．４段については
分配器８０１の分配規則を変更するだけで、第７図の乗
算器がそれぞれ演算器ａ８２０、演算３ｂ８２１、演算
器ｄ８２３として使用できる。この時の係数は＋１か−
１のみでよい。第３段については、第２図中に示すよう
に係数としては＋１．−１．　＋Ｃ４゜−Ｃ４，＋Ｃ８
，−Ｃ８，＋８４を係数器８０３に用意しておく。第５
段も同様である。とくに第５段においてｎ＝４とする場
合には第８図に示すようにＦ４〜Ｆ１５の出力は固定的
にゼロにされるため、これを計算するのに必要な積、和
は不要である。

したがって、第６図と第８図とを対比させると演算器ａ
８２０〜演算器ｅ８２４は第１〜５段目の各演算を実行
することになる。バッファ８３０はこうして得られるＦ
Ｏ〜Ｆ１５（Ｆ４〜Ｆ１５はゼロ）の計１６（Ｎ＝１６
の場合）の係数を−たん記憶し、中間結果としてＮデー
タ並列に演算器ａ’　８４０に供給する。以下、演算器
ａ’　８４０〜演算器ｅ’　８４４の動作は第８図に従
い、かつ演算器ａ８２０〜演算器ｅ８２４と同一で、演
算器ｅ’　８４４より出力されるデータが２次元の直交
変換を行った時の最終的な変換結果である。この係数は
Ｎ並列で出力されるため、バッファ８５０においては並
列−直列変換を行い係数を１個づつ順に線３０００を介
して出力し、量子化器３０に供給する３、直交変換が省
略された変換係数に対しては特定の値たとえばゼロを出
力すればよい。

本発明の近似的な直交変換に対する直交逆変換としては
、近似していない逆変換と近似した逆変換のいずれも適
用可能である。近似していない逆変換は通常の場合と同
じである。近似した逆変換も、近似した直交変換を実行
する第４図あるいは第６図における係数を逆変換用に置
換するだけでよく、直交変換時に演算されない係数に対
応する逆変換マトリックス内の要素は特定の値たとえば
ゼロにしておいて、実効的に演算を省略できる。

つぎに第９図及び１０図を参照してこの不等長符号への
表現方法とその復号方法について説明する。

第９図に、符号変換回路４０の構成例を示す、１個づつ
直列に出力される変換係数（量子化後）は線４０００を
介して係数符号器４１０とゼロ検出器４２０へ同時に供
給される。係数符号器４１０は、多数の画像信号に対し
て統計的に求めた係数の分布より得られるハフマン符号
などの高能率符号をゼロでない入力変換係数に対応付け
て出力する符号変換を行い、多重化器４７１に供給する
。ゼロ検出器４２０は入力変換係数がゼロであるか否か
を判定し、その結果を線４２００を介してラン長計数器
４３０と多重化器４７０に供給する。ラン長計数４３０
は、線４２００を介して供給される信号がゼロを検出し
ていることを示している時には、そのゼロの連続する数
を計数し、計数結果を線４３４４を介してラン長符号器
４４０に供給する。

制御回路４５０はこの符号変換の実行制御する機能を有
し、画像信号の水平・垂直同期信号の存在位置の指定お
よび、これの符号変換結果の選択を線４５００を介して
同期信号符号器４６０と多重化器４７０に供給する。ラ
ン長符号器４４０は、線４３４４を介して供給するラン
長を符号に変換して多重化器４７０へと出力する。この
ラン長を表わす符号とゼロでない係数を表わす符号は互
いに区別できることが必要であることは言うまでもない
。同期信号符号器４６０は、同期信号が存在する時これ
を表わす符号を多重化器４７０に出力する。多重化器４
７０は、供給する３種の符号を多重化して線５０００を
介して出力するが、その選択は線４２００と４５００を
介してそれぞれ供給される、入力された係数がゼロか否
かを表わす信号、同期信号の存在を表わす信号に従う、
すなわち、同期信号が存在する時には同期信号を表わす
符号、係数がゼロでない時には係数の符号変換結果（係
数符号器４１０の出力）、そしてゼロの時にはラン長の
符号変換結果がそれぞれ選択され多重化される。

なお、ゼロなる係数が多数連続し、その後に同期信号が
来る場合にはこの最後のラン長は符号化しなくても復号
時には正しく復号することが出来るので省略することが
可能である。この時には制御回路４５０より線４５４３
を介して同期信号の発生をラン長計数器４３０に知らせ
、その計数値をリセットする。また、多重化器４７０に
対してはさらに最後のラン長を表わす符号は無視するよ
うに線４５００を介して指令する。

つぎに、符号逆変換回路５０の構成について第１０図を
参照して説明する。

線５０００を介して供給された符号変換された変換係数
は係数復号器５１０、ラン長復号器５４０、同期信号復
号器５６０に供給される。係数復号５５１０はゼロでな
い係数の符号逆変換を行い、その結果を線５１５７を介
してスイッチ５７０へ、また逆変換中であることを示す
信号を線５１５５を介して制御回路５５０へそれぞれ供
給する。ラン長復号器５４０はゼロなる変換係数が連続
する長さくラン長）を表わす符号を逆変換し、その長さ
に応じてゼロなる信号を発生し線５４５７を介してスイ
ッチ５７０に供給すると同時に、線５４５５を介してラ
ン長を復号している最中であることを示す信号を線５４
５５を介して、それぞれ供給する。同期信号復号器５６
０は符号化された同期信号の存在を検出し、その結果を
制御回路５５０に伝える。

制御回路５５０は、これら同期信号を表わす信号、線５
１５５、５４５５をそれぞれ介して供給される信号を用
いてスイッチ５７０の選択を制御する。また同期信号の
直前にあるランが符号変換されなかった場合には、最後
のゼロでない係数のっぎから同期信号が発生する直前ま
での時間はスイッチ５７０がゼロを出力するように指令
するが、この指令およびスイッチ５７０での選択は線５
５５７を介して行われる。

（発明の効果） 本発明を実用に供すると、符号化能率は高いがこれを実
現するのに複雑なハードウェア、あるいは多数の加算、
乗算が必要な直交変換が大巾に簡略化できるようになり
、その効果は非常に高い。

【図面の簡単な説明】

第１図は本発明の詳細な説明する図、第２図は離散コサ
イン変換の高速算法の１例を示す図、第３図。 第４図、第５図、第６図、第７図、第９図、第１０図は
本発明に関る実施例を示す図、第８図は本発明に関る離
散コサイン変換の高速算法の１例を示す図である。 図において、 ｌＯは走査変換回路、２０は直交変換回路、３０は量子
化器、４０は符号変換回路、５０は符号逆変換回路、６
０は直交逆変換回路、７０は走査逆変換回路、である。 ”ＩＩ　　　　　　　Ｃ１１ 心 α〕 ＊ 亭　　ｑ　　図

Claims (1)

1. 【特許請求の範囲】 １、画像信号を変換し、得られる変換係数を量子化し符
   号化するに当り、量子化により特定の値に集中すること
   が多い変換係数を含むあらかじめ定められた変換係数に
   ついては変換に際して実行される演算を省略することを
   特徴とする画像信号の変換符号化方式。 ２、演算が省略された変換係数に対してあらかじめ定め
   られた特定の値を付与することを特徴とする特許請求の
   範囲第１項記載の画像信号の変換符号化方式。