JPH0215783A - データ変換回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は画像の符号化データなどのランレングス表現を
含んだデータを元のマｌ−ＩＪクス配列のデータに逆変
換するデータ変換回路に関するものである。

従来の技術 画像データなどのように周囲のデータとの相関が強く冗
長性のあるデータの場合にはデータ量圧縮のためにラン
レングス表現を用いることが多い。

たとえば、直交変換による画像データの圧縮符号化の場
合には変換係数の符号化の過程でランレングス表現が用
いられる。第７図＆には、直交変換による画像データの
符号化処理の一般的な手順を。

同図ｂ［は、ａの処理に対応して生成されるデータを示
す。原画像データ１０１をｍ行ｎ列（ｍ。

ｎ≧１）からなるブロック毎に分割して、ブロック画像
データ１０２を読み出す。このブロック画像データに対
して直交変換を施してブロック変換係数１０３を得る。

直交変換としてはアダマール変換、離散コサイン変換な
どを用いることが多い。

直交変換を施すことによって得られる変換係数１０３に
はデータの分布に偏りがあるため、非線型な量子化処理
を行なうことによってビット数を低減させた量子化変換
係数１０４を得る。次に量子化されたマトリクス配列の
変換係数全蓄積あるいは伝送するだめに１次元のデータ
列に変換するだめのデータ変換を行ない、１次元変換デ
ータ１０６を得る。この時、後で詳しく説明するような
変換係数の分布の傾向からランレングス表現を含むよう
なデータ・フォーマットを採用する。更にデータ圧縮効
率の改善を図るために１次元変換データ１０５に対して
可変長符号化処理（たとえばハフマン符号化）を行なっ
て可変長符号化データ１０６を求め、こｉ′Ｌを圧縮画
像データ１０７に追加する。実際にはデータ変換処理と
可変長符号化処理は同時に行なわれ、量子化変換係数か
ら直接、可変長符号化データに変換する場合も考えられ
るが１本質的な差異はないのでここでは説明の都合上、
２つの処理を分離して考える。以上の一連の処理を、ブ
ロック単位毎にくり返すことにより、原画像データ１０
１を圧縮画像データ１０Ｔに変換する。以下に、ブロッ
ク変換係数１０３から１次元変換データ１０６′を求め
るまでの過程をより詳細に説明する。ブロック画像デー
タ１０２゜ブロック変換係数１０３．量子化変換係数１
０４の具体例を第８図ａ、ｂ、ｃにそれぞれ示す。第８
図の例では、８行８列からなるマトリクス配列のデータ
を、ブロック単位にしている。直交変換としてアダマー
ル変換や離散コサイン変換を用いた場合には一般的には
変換係数の左上部分（第８図すに網かけを施して示す部
分）には大きな係数値が、それ以外の部分には小さな係
数値が出現することが知られている。たとえば離散コサ
イン変換によって得られるブロック変換係数のほとんど
は、第９図ａ−ｄに示す４種類の分布状態のいずれかに
分類できることが実験的にも確認されている。ここで、
ブロック内の左上部（図中に網かけで示した部分）には
、比較的大きな係数値が分布し、それ以外の部分には小
さな係数値（→０）が分布することを示している。従っ
てブロック変換係数に対して非線型量子化処理全行なう
と、ブロックの左上部には圧縮画像データに対応する量
子化変換係数が分布し、そｎ以外の部分には量子化変換
係数として０が並ぶことになる。第８図す。

Ｃにはブロック変換係数ａｉｊ（１≦１．コ≦８）が量
子化処理によって量子化変換係数人、ｊに変換された例
を示している。同図において、ブロックの左上部以外の
量子化変換係数は、値が０になることを明示的に示して
いる（第８図Ｃ）。次に、蓄積あるいは伝送を目的とし
て、マトリクス配列の１１量子化変換係数を１次元のデ
ータ列に変換する処理を説明する。一般的な手法として
は第１０図＆に示すように、ラスタ・スキャン状にブロ
ック内の量子化変換係数を走査して１次元のデータ列に
変換する。この時５前記の量子化変換係数の分布特性を
応用して更に圧縮効果を得る手法が考えられる。すなわ
ち、第８図Ｃの例でも明らかなように、ブロック内の左
上部を除く部分には係数値としてＯが連続する傾向があ
るため、この部分を０の連続する長さ（ラン長）で表現
する手法である。第１１図に詳しい処理手順を示す。同
ｌｅａは。

第８図Ｃの量子化変換係数をラスタ・スキャン状に走査
して並べた係数列である。これに対して、０以外の変換
係数はそのままで、係数０の部分はラン長表現Ｌ１〜Ｌ
６で表現した第１１図すのデータ列が、第７図すの１０
６に対応する１次元変換データである。第１１図すの最
後のデータ”′Ｔ″は、ブロック単位のデータの終りを
示すターミネータ符号である。ただしデータ数全カウン
トすればターミネータは必ずしも必要ではない。当然、
本来の係数データＡｉｉと、ラン長データＬｋ、ターミ
ネータＴｆｉ区別ができるような符号体系にする必要が
ある。

係数Ｏが多く、しかも、偏って分布しているフロックは
ど、このようなデータ変換による圧縮効果が期待できる
。−まだ、更に圧縮効率を改善するために第１０図すに
示すようにジグザグ状に走査する手法も提案されている
。（例えば、特許公開番号：昭６１−１２３２８０号、
「画像データ圧縮装置」）次に、このようにして得られ
た１次元変（るデータに対して更に圧縮効率を改善する
ために、第１１図すの各データＡ工ｊ、Ｌｋ、Ｔなどを
、可変長符号化して可変長符号化データ（第７図すの１
０６）に変換して、これを圧縮画像データに追加する。

実際には量子化変換係数をラン長表現を含む１次元変換
データに変換する際に可変長符号化も同時に行なうこと
も可能である。次に、符号化された圧縮画像データの復
号処理について説明する。＠１２図ａは、復号処理手順
を示す図であり、同６ｂは各処理に対応して生成される
データを示す。、復号処理手順は基本的に第１１図の符
号化処理手順の逆である。圧縮画像データ１０７から１
ブロツクに対応する可変長符号化データ１０６を読み出
す。ブロック単位のデータは第１１図すのターミネータ
符号＋１　Ｔ　１１に対応するデータによって分離でき
る。次に可変長符号化データ１０６を復号化処理して１
次元変換データ１０５に戻し、さらに元のマトリクス配
列の量子化変換係数１０４に逆データ変換処理する。復
号処理では、第７図すのブロック変換係数１０３に相当
するデータは完全に再生できないため量子化変換係数１
０４に対して逆直交変換処理を行なってブロック画像デ
ータ１０８’ｉ求め、これを再生画像データ１０９内の
ブロック・データとして再生処理を行なう。ここで、プ
０７り画像データ１０８と再生画像データ１０９は、第
７図すのブロック画像データ１０２と原画像データ１０
１に対応するものであるが、量子化処理のだめに完全に
元の値には戻らず一般的には完全に同じものとはならな
い。

発明が解決しようとする課題 このような従来の復号化処理においては、復号化処理に
要する時間、特にランレングス表現によってデータ圧縮
が施された１次元変換データ１０６から量子化変換係数
１０４を再生する時の処理時間の遅さが問題となってい
た。すなわち従来の復号処理では量子化変換係数１０４
を再生する逆データ変換処理１１０では、圧縮データか
ら元のｍ行ｎ列のマトリクス配列の全データを再生処理
するため、この処理に要する時間が、圧縮データのみを
扱うブロック読み出し処理１１１や、復号化処理１１２
に比べ犬きくなってしまい、逆データ変換処理１１０の
処理速度が全体の処理速度に影響を与えるという課題が
あった。

課題を解決するための手段 上記課題を解決するため１本発明ではランレングス表現
を含む１次元のデータ・フォーマ、トカら元のマトリク
ス配列のデータ群に逆変換するデータ変換回路として、
前記マトリクス配列と同じ配列で、各要素が変換前の元
のデータを格納するのに十分なビット幅（語長）を有す
る第１のメモリと、前記マトリクス配列と同じ配列で、
各要素が１ビットから成る第２のメモリと、前記第１の
メモリの出力データを選択入力データとして与え、前記
第２のメモリの出力データを選択制御信号として与え、
この選択制御信号の値に応じて前記選択入力データをそ
の捷ま選択出力データとするか否かを制御するデータ選
択回路を有する構成をとっている。

作用 上記構成をとることによって、圧縮された１次元データ
・フォーマットの変換データを元のマトリクス配列のデ
ータに展開（逆変換）する際に、前記第１のメモリには
０以外の有効な情子化係数データのみを書き込み、同メ
モリの読み出しに。

前記第２のメモリの出力による制御によって全画素の読
み出し全可能ならしめ、処理の高速化を図ることができ
る、。

実施例 実施例１ 以下に図面を用いながら本発明の第１の実施例を説明す
る。第１図は本発明のデータ変換回路の一実施例を示す
ブロック図である。処理の流れは第１２図の４号処理手
順に対応する。第１図の１は、圧縮画像データから１ブ
ロック分の可変長符号化データ１０６を読み出すように
制御するブロック読出し回路、２は可変長符号化データ
１０６全復号してランレングス表現を含むデータ・フォ
ーマットの１次元変換データ１０５に戻す復号回路、８
け１次元変換データ１０６を元のマ）　ＩＪクス配列の
量子化変換係数１０４に逆変換する本発明にかかる変換
回路である。変換回路８は逆変換された係数を格納する
第１のメモリ３と、逆変換された係数が０か否かを識別
するフラグ信号を格Ｗ１する第２のメモリ４と、第２の
メモリの出力に応じて第１のメモリの出力の通過を制御
して量子化変換係数１０４を出力するデータ選択回路５
から構成される。７は第２のメモリの制御のために必要
に応じて（＝Ｊ加されるアクセス制御回路である。

６はデータ変換回路８で得られだ量子化変換係数１０４
からブロック画像データ１０８を再生する逆１′［交変
換回路である。

第２図はデータ変換回路８の動作全詳しく説明する図で
ある。１１は第１のメモリ３の内容を示したものである
。第１のメモリへのデータの書込みは復号回路の出力デ
ータである１次元変換データ１０６のうち、○でない係
数データ人ｉｊ１すなわちラン長表現されていない係数
データのみを該当するアドレスに格納していく。同図の
“′Ｘ″は、書き換えが行なわれず以前のデータを保持
していることを示す。一方、１２は第２のメモリ４の内
容を示したものである。第２のメモリへのデータの書込
みは１次元変換データ１０５のうち０でない係数データ
Ａｉｊに相当するアドレスには＋１１１１を書込み、そ
れ以外の係数０の部分（ラン長表現されている）にはＯ
′”を書込む。逆直又変換回路６へ量子化変換係数１０
４を出力する場合のメモリ読み出しにおいては、第１の
メモリ３および第２のメモリ４に同じアドレスを与え１
両者を同時に読み出す。第２のメモリ４の出力１１４は
データ選択回路６の選択制御信号として与えられる。

データ選択回路６の動作としては、第１のメモリ３への
アクセスがデータの書き換えが行なわれた部分（同図中
の゛′Ｘ″以外の部分）への読み出しアクセスの場合に
は選択制御信号１１４が１゛′となり、第１のメモリ３
の出力１１３をそのまま量子化変換係数１０４として出
力し、第１のメモリ３へのアクセスがデータの書き換え
が行なわれなかった部分（同図中の１１　Ｘ　Ｉ＋の部
分）への読み出しアクセスの場合には選択制御信号１１
４が０”２となり、第１のメモリ３の出力１１３の如何
にかかわらず量子化変換係数としてＯ゛′を出力するよ
うにデータ選択を行なう。

第３（２）には、データ選択回路６の具体的な構成例を
示す。第３図ａは、多値データを扱うマルチプレクサ１
３によってデータ選択回路を構成した例であり、選択入
力人には第１のメモリ３の出力１１３を接続し、第２の
選択人力Ｂには固定値としてＯを与える。選択制御信号
ＳＫは第２のメモリ４の出力１１４を接続して１選択制
御信号が′○”の時にはマルチプレクサの出力１０４が
°゛０“になるように制御する。第３図ｔ）［ＡＮＤゲ
ートを用いてデータ選択回路６を構成した例であり、０
１、〜ｃｏｕｘビットから成る第１のメモリ３の出力デ
ータの各ビット信号であり、・ｌ−＋〜ｅｏはデータ選
択回路６の出力データの各ビット信号である。選択制御
信号１１４が′１“′の時１１Ｃｕ６１＝Ｃ１となり、
１１４が′０”の時には入力データ１１３はマスクされ
て０が出力される。

第１１のような構成をとった場合、多値データを扱う必
要のある第１のメモリ３に比べ、第２のメモリ４は各要
素が１ピツトであるためコスト的にも高速なメモリの使
用が可能である。従って１次元変換データから元のマト
リクス配列に対応して１ピツトのデータを展開していく
時間も第１のメモリに比べれば短くてすむ。あるいは、
１次元変換データ１０５からの逆変換に先立って毎回筒
２のメモリ４の内容を全クリアしてから第１のメモリ３
の書きかえと同時に第２のメモリ４の必要なアドレスの
みにフラグ！１”を書いていくという方法も考えられる
。次に、第１図に示したアクセス制御回路７ｆｔ用いて
第２のメモリを制御する場合の実施例を示す。前提とし
て第２のメモリ４は第１のメモリ３に比ベアクセス速度
が速く、第１のメモリのリード・アクセス期間中に第２
のメモリのリードモディファイ・ライト・アクセスが行
なえるという条件を設定している。この前提は前述のメ
モリの容量と価格、性能の点からも不自然ではない。第
４図は第１及び第２のメモリに関するタイムチャートで
あり、＆　ＮＯは第１のメモリの信号を示し、６〜ｉＨ
第２のメモリの信号を示している。２つのメモリは常に
同時に、同じアドレスにアクセスするため信号ａとｄは
同じものである。以下では第２図に示すように第１．第
２のメモリにマトリクス配列のデータが書き込まれてお
り、逆直交変換のために量子化変換係数１０４を読み出
そうとする時の動作を説明する。第２のメモリ４は第１
のメモリ３０１周期中にリードのモードとこれに続くラ
イトのモード（リード・モディファイ・ライト）を有し
ている（第４図のｅ）。

第１の周期Ｔ１ではメモリのアドレス１の内容を読み出
す。この時の第２のメモリの出力データｆハ１１１”で
あり、これをラッチパルスｇで保持して選択信号りとす
る。続いて第２のメモＩＪ　Ｈライト期間に入り、ライ
トパルスｉのタイミングでメモリのアドレス１にデータ
（ｔ　□　ＩＩを書き込む。この結果、周期Ｔ１の終了
時には第２のメモリの１番目のアドレスの以前の内容は
選択信号りとして保持されると共に、同メモリの１番目
のアドレスの内容ｔｄ　”Ｏ”にクリアされる。周期Ｔ
１の後半には第１のメモリ３のｉ番目のアドレスの内容
すすなわちＤｉが確定するので、これをデータ選択回路
６への入力データ（第２図中の１１３）として与え、第
２のメモリの内容を保持している選択信号りをデータ選
択回路５への選択制御信号（第２図中の１１４）として
与えると選択出力ｃ（７＜２図中の１０４）としてＤｉ
が得られる。一方、第２の周期Ｔ２では第２のメモリの
ｉ＋１番目のアドレスの内容では”ｏ”であり、従って
選択信号りも′０゛が保持される。それに続くライト期
間の動作は周期Ｔ１と同じであり、無条件にデータ゛°
０″を書き込む。すなわち、第２のメモリハ内容の読み
出しを行なうと必ず該当アドレスの内容が′０”にクリ
アされるようにアクセス制御回路７によって制御されて
いる。第２の周期Ｔ２の後半では、第１のメモリ３のｉ
＋１番目のアドレスの出力データｂとして”１−１−＋
が出力されるが。

選択信号りが°°０”に保持されているためＤ１＋。

はデータ選択回路６を通過できず選択出力Ｃ°（第２図
中の１０４）は°゛Ｏ”となる。

逆直交変換回路が第１及び第２のメモリの全内容を読み
出し終えた時点では第２のメモリの内容は全て゛０゛ク
リアされた状態となっている。次のブロックの処理にあ
たっては１次元変換データ１０６のうち、０でない係数
データムｉｊに相当するアドレスに対してのみ、第１の
メモリでは係数Ａｌｊを、第２のメモリではフラグピッ
）　ＩＪｌｌを書きこみ、係数データが０の部分（ラン
レングス表現されている部分）については無視をするこ
とによって従来に比べ非常に高速に第２図に示すような
量子化変換係数の展開（逆変換）を行なうことができる
。

実施例２ 第６図は１本発明にかかる第２の実施例を示す図である
。本発明にかかるデータ変換回路８を除く部分の構成お
よび動作は７１！Ｊ１図に示した実施例の場合と同じで
ある。よって以下では、データ変換回路８の構成のみを
詳細に説明する。バッファ・メモリ１０は、第１図の実
施例における第１のメモリに相当するもので、逆変換さ
れたマトリクス配列の係数を格納する多値データ・メモ
リである。

アクセス制御回路１４は、第１図のアクセス制御回路７
と同様の動作をするもので、第６図の例では係数を格納
する多値メモリの方をリード・アクセス後、リード・モ
ディファイ・ライトによって１１　（）　Ｉ＋クリアす
るように制御する。バッファ・メモリ１０の内容は読み
出されてクリアされる前にデータ保持回路９にラッチさ
れて、データ変換回路８の出力データ１０４となる。第
６図はバッファ・メモリ１０およびアクセス制御回路１
４の動作を説明するタイムチャートである。メモリ１０
はリード・アクセスに続くライト・アクセスによって同
一のアドレス内容にデータ゛０″がｐ）き込まれる。リ
ード・アクセスで読み出された出力データＣ１ｔ’１．
ラッチパルスｅ（第６図中の１１６に相当する）でデー
タ保持回路９にとりこまれ、保持データｆとして逆直交
変換回路６へ出力される。

バッファ・メモリ１０が上記のように制御されるため、
１次元変換データをバッファ・メモリ内に展開（逆変換
）する際には０以外の係数データのみをバッファ・メモ
リ１ｏに書きこめば良いためメモリ・アクセスの回数を
かなり少なくすることができる。

発明の効果 以上述べてきたように、本発明によれば、簡単な回路を
付加するだけで、ランレングス表現された変換データか
らの展開（逆変換）を高速に行なうことができ、ブロッ
ク単位のくり返し処理全体の高速化に寄与することがで
きるなど実用的に大きな効果を期待できる。

特に、処理を高速化するために逆直交変換回路を複数組
用意してトグル処理を行なう場合などしては有用である
。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック構成図、第２
図は本発明にかかるメモリの内容例を示す図、第３図は
データ選択回路の具体構成例を示す回路図、第４図は本
発明にかかるデータ変換回路の動作を説明するタイムチ
ャート、第６図は本発明の第２の実施例を示すブロック
構成図、第６図は第２の実施例の動作を説明するタイム
チャート、第７図は従来の直交変換符号化の処理フロー
を示す図、第８図は第７図の処理フローに対応するデー
タの例の説明図、第９図は直交変換係数の分布を示す図
、第１０図は変換係数のスキャン方法を説明する図、第
１１図はスキャンした変換係数と１次元変換データとの
対応を示す図、第１２図は従来の直交変換復号化の処理
フローを示す図である。 ３・・・・・・第１のメモリ、４・・・・・・第２のメ
モリ、６・・・・・・データ選択回路、７，１４・・・
・・・アクセス制御回路、８・・・・・・データ変換回
路、９・・・・・・データ保持回路、１ｏ・・・・・・
バッファ・メモリ、１０４・・・・・・−量子化変換係
数、１Ｑ６・・・・・・１次元変換データ。 ／′ａｒ 図 第 図 どｔ） り／Ｉ／−パル久 ７ノ 第 図 （々〕 （ｂ） ｌ？ 第 図 （ｂ）ｊ−Ｅ９モーＦ’　　　　　　Ｅ’ｅＱｄ　　　
　　　　Ｖｒ＃　　　　　　Ｒ，−ｅｒｃ／ｐうＡＬ八
へヌ 第 図 （ａノ フロヅ装置り龜データ （ｂ） デＵ、・ツク笈拶Ｉ糸孜 （Ｃ）量子化？Ｊ、横螺孜 ４〇− 区 ≦ 第１２図 ＩＱ）

Claims (5)

【特許請求の範囲】
1. （１）ｍ行ｎ列（ｍ、ｎ≧１）から成るマトリクス配列
   のデータ群に対して、少なくとも１つ以上のランレング
   ス表現を含む１次元のデータ・フォーマットへの変換処
   理を施して得られた変換データを、元のマトリクス配列
   のデータ群に逆変換するデータ変換回路であって、前記
   マトリクス配列と同じ配列で、各要素が変換前の元のデ
   ータを格納するのに十分なビット幅（語長）を有する第
   １のメモリと、前記マトリクス配列と同じ配列で、各要
   素が１ビットから成る第２のメモリと、前記第１のメモ
   リの出力データを選択入力データとして与え、前記第２
   のメモリの出力データを選択制御信号として与え、この
   選択制御信号の値に応じて前記選択入力データをそのま
   ま選択出力データとするか否かを制御するデータ選択回
   路を有することを特徴とするデータ変換回路。
2. （２）第２のメモリが、データの読み出しアクセス後に
   、その内容がクリアされるように構成されていることを
   特徴とする特許請求の範囲第１項に記載のデータ変換回
   路。
3. （３）元のマトリクス配列のデータ群がブロック分割さ
   れた画像データの直交変換係数であることを特徴とする
   特許請求の範囲第１項または第２項に記載のデータ変換
   回路。
4. （４）ｍ行ｎ列（ｍ、ｎ≧１）から成るマトリクス配列
   のデータ群に対して、少なくとも１つ以上のランレング
   ス表現を含む１次元のデータ・フォーマットへの変換処
   理を施して得られた変換データを、元のマトリクス配列
   のデータ群に逆変換するデータ変換回路であって、前記
   マトリクス配列と同じ配列で、各要素が変換前の元のデ
   ータを格納するのに十分なビット幅（語長）を有するバ
   ッファ・メモリを有し、このバッファ・メモリがデータ
   の読み出しアクセス後に、その内容がクリアされるよう
   に構成されていることを特徴とするデータ変換回路。
5. （５）元のマトリクス配列のデータ群がブロック分割さ
   れた画像データの直交変換係数であることを特徴とする
   特許請求の範囲第４項に記載のデータ変換回路。