図面 (/)

技術 圧縮器、圧縮/伸長システム、ルックアップテーブル作成方法、及び、記録媒体

出願人 株式会社リコー
発明者 エドワードエルシュワルツアーマドザンディ
出願日 1998年4月20日 (22年8ヶ月経過) 出願番号 1998-109413
公開日 1998年12月4日 (22年0ヶ月経過) 公開番号 1998-322219
状態 特許登録済
技術分野 計算機・関数発生器 画像処理 特定演算一般(初等関数/乱数発生/非基数) データ変換 TV信号の圧縮,符号化方式 TV信号の圧縮,符号化方式 圧縮、伸長・符号変換及びデコーダ
主要キーワード ミスマッチ量 ミスマッチ誤差 共通因数 点効率 連続近似 精度試験 交換候補 入力ペア
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1998年12月4日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

ロスレス、ロッシーいずれにもできる可逆DCTと、それを用いた圧縮伸長システムを実現する。

解決手段

入力データ100は本発明の可逆DCTを用いる圧縮器101に入力される。圧縮器101の出力は、本発明の可逆IDCを用いる伸長器102でも在来のJPEG伸長器などの任意のIDCを用いる伸長器103でも処理できる。伸長器102を使用すればロスレスの圧縮/伸長となり、伸長器103を使用すればロッシーの圧縮/伸長となる。

概要

背景

離散コサイン変換(DCT)は、ロッシー(損失のある)画像圧縮に一般的に使われる無理変換である。DCTは一般にロッシー画像圧縮で使用される。DCTは、JPEG標準MPEG標準及び米国の次世代HDTVの多くのモードに用いられる。これら各種標準に関する解説については、ISO標準文書ISO/IEC10918(JPEG),11172(MPEG1),13818(MPEG2)、及び、William B.Pennebakerand Joan L.Mitchell,”JPEG Still Image Data CompressionStandard,”1993を参照されたい。DCTの基底ベクトルは無理値を持つ。理論上、整数入力の結果として無理変換係数が得られる。したがって、そのような変換を厳密に行うには無限の精度が要求される。変換係数は、圧縮に使うためには、有限表現へ丸められねばならない。

大抵の変換手段では、係数の整数への丸めは、あらゆる整数入力に対して異なった出力が得られることを保証するものではない。よって、逆DCTで入力を厳密に再構成することは不可能である。量子化無しの順DCT変換逆DCT変換による誤差系統誤差と呼ばれる。この系統誤差が、差分又は誤差画像を生じさせないロスレス圧縮におけるDCTの利用の妨げとなっている。

実際的なDCT実行手段では、変換基底ベクトルも丸められる。ある変換実行手段と理想的な変換実行手段(すなわち高精度浮動小数点の実行手段)との間の差はミスマッチと呼ばれる。データの相互交換のためには低ミスマッチが要求される。ミスマッチ量と、速度、コスト、その他の要求される特性の間にはトレードオフの関係があるといってよい。

本明細書においてAllenのパラメタライズド(パラメータがつけられた)変換(APT)と呼ぶパラメタライズド変換は、DCT又はDCTに任意的に近い無理変換を実施できる高速変換の仲間である。APTは一般化Chen変換(GCT)とも呼ばれる。APTの詳細については、J.Allen,”Generalized ChenTransform:A Fast Transform for Image Compression,”Journal ofElectronic Imaging,vol.3(4),October 1994,pgs.341−347、J.Allen,”An Approach to Fast Transform Coding in Software,”Signal Processing Image Communication,Vol.8,pp.3−1,1996、及び、米国特許第5,129,015号を参照されたい。

概要

ロスレス、ロッシーいずれにもできる可逆DCTと、それを用いた圧縮/伸長システムを実現する。

入力データ100は本発明の可逆DCTを用いる圧縮器101に入力される。圧縮器101の出力は、本発明の可逆IDCを用いる伸長器102でも在来のJPEG伸長器などの任意のIDCを用いる伸長器103でも処理できる。伸長器102を使用すればロスレスの圧縮/伸長となり、伸長器103を使用すればロッシーの圧縮/伸長となる。

目的

本発明の目的は、可逆のブロックベース変換、例えば可逆DCTなどと、それを使用する圧縮器、並びに、そのような圧縮器を使用したロスレス又はロッシーの圧縮/伸長システムを提供することである。本発明の他の目的は、系統誤差がなく、かつミスマッチがない(又は低い)DCT変換を提供することである。本発明のもう一つの目的は、可逆DCTに使用するための丸めオフセットルックアップテーブルの生成方法を提供することである。その他の本発明の目的は以下の説明から明らかになろう。

効果

実績

技術文献被引用数
2件
牽制数
3件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

逆離散コサイン変換(DCT)を有することを特徴とする圧縮器

請求項2

可逆離散コサイン変換(DCT)を有する圧縮器と、伸長器とを具備することを特徴とする圧縮伸長システム

請求項3

該伸長器が可逆逆DCTを有する伸長器であることを特徴とする請求項2記載の圧縮/伸長システム。

請求項4

該伸長器が逆DCTを有する従来の伸長器からなることを特徴とする請求項2記載の圧縮/伸長システム。

請求項5

該DCTが複数の2点回転からなることを特徴とする請求項1記載の圧縮器。

請求項6

複数の2点回転が変換からなることを特徴とする請求項5記載の圧縮器。

請求項7

該変換のそれぞれが平衡スケールファクタを持つことを特徴とする請求項6記載の伸長器。

請求項8

第1の複数の回転、該第1の複数の回転の出力の第1の組と接続され、かつ、Bの回転を含む第2の複数の回転を有する4点パラメタライズド変換、及び該第1の複数の回転の出力の第2の組と接続され、Aの回転とCの回転を含む補助マトリックスを具備し、該第1の複数の回転、該4点パラメタライズド変換及び該補助マトリックスは可逆ブロックベース変換として働くことを特徴とするブロックベース変換の圧縮器。

請求項9

入力と、変換入力値変換出力値へのマッピングを有するルックアップテーブルを含む少なくとも1つの変換を有する可逆DCTとを具備し、該マッピングは、丸めが入力を同じ変換値マップするところの第1のグループからの入力を、丸めに利用されなかったであろう変換出力へマップすることを特徴とする圧縮器。

請求項10

丸めオフセットのためのルックアップテーブルを作成するための方法であって、初期丸めを用いて入力値の変換出力値への第1のマッピングを生成するステップ、及び該第1のマッピンにおける衝突の各行に対し(ただし、衝突は入力の同じ変換出力値へのマッピングである)、該初期丸めで用いられないであろう変換出力値を提供するために必要とされ、それぞれが該初期丸めに用いられないであろう変換出力値からなるエキストラを、それぞれ含む行の数を求めるステップ、各衝突に対し1つのエキストラを提供するために部分エキストラ行が必要なときに、ある行内の均等に間隔をおいたある個数のエキストラを選択するステップ、エキストラを列順ソートするステップ、該ルックアップテーブル内で使用するための第2のマッピングを生成するためエキストラを衝突に列順に割り当てるステップ、を含むことを特徴とするルックアップテーブル作成方法

請求項11

丸めオフセットのためのルックアップテーブルを作成するための方法であって、複数の入力の同じ変換出力値へのマッピングが存在する各衝突に対し、初期丸めで使用されないであろう変換出力値が存在する各エキストラに対し、所定の基準に基づき他のエキストラとの交換を割り出すステップ、及び該交換を実行するステップ、を含むことを特徴とするルックアップテーブル作成方法。

請求項12

可逆ブロックベース変換と、該可逆ブロックベース変換の出力より得られるデータを符号化するため該可逆ブロックベース変換に接続されたコーダとを具備する圧縮器。

請求項13

コンピュータに、入力データを受け取るステップ及び可逆DCT変換を実行するステップを実行させるためのプログラムが格納されたことを特徴とするコンピュータが読み出し可能な記録媒体

技術分野

0001

本発明は、圧縮及び伸長システムの分野に係り、特に、可逆ロスレス損失のない)離散コサイン変換(DCT)ベースの圧縮に関する。

背景技術

0002

離散コサイン変換(DCT)は、ロッシー(損失のある)画像圧縮に一般的に使われる無理変換である。DCTは一般にロッシー画像圧縮で使用される。DCTは、JPEG標準MPEG標準及び米国の次世代HDTVの多くのモードに用いられる。これら各種標準に関する解説については、ISO標準文書ISO/IEC10918(JPEG),11172(MPEG1),13818(MPEG2)、及び、William B.Pennebakerand Joan L.Mitchell,”JPEG Still Image Data CompressionStandard,”1993を参照されたい。DCTの基底ベクトルは無理値を持つ。理論上、整数入力の結果として無理変換係数が得られる。したがって、そのような変換を厳密に行うには無限の精度が要求される。変換係数は、圧縮に使うためには、有限表現へ丸められねばならない。

0003

大抵の変換手段では、係数の整数への丸めは、あらゆる整数入力に対して異なった出力が得られることを保証するものではない。よって、逆DCTで入力を厳密に再構成することは不可能である。量子化無しの順DCT変換逆DCT変換による誤差系統誤差と呼ばれる。この系統誤差が、差分又は誤差画像を生じさせないロスレス圧縮におけるDCTの利用の妨げとなっている。

0004

実際的なDCT実行手段では、変換基底ベクトルも丸められる。ある変換実行手段と理想的な変換実行手段(すなわち高精度浮動小数点の実行手段)との間の差はミスマッチと呼ばれる。データの相互交換のためには低ミスマッチが要求される。ミスマッチ量と、速度、コスト、その他の要求される特性の間にはトレードオフの関係があるといってよい。

0005

本明細書においてAllenのパラメタライズド(パラメータがつけられた)変換(APT)と呼ぶパラメタライズド変換は、DCT又はDCTに任意的に近い無理変換を実施できる高速変換の仲間である。APTは一般化Chen変換(GCT)とも呼ばれる。APTの詳細については、J.Allen,”Generalized ChenTransform:A Fast Transform for Image Compression,”Journal ofElectronic Imaging,vol.3(4),October 1994,pgs.341−347、J.Allen,”An Approach to Fast Transform Coding in Software,”Signal Processing Image Communication,Vol.8,pp.3−1,1996、及び、米国特許第5,129,015号を参照されたい。

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

0006

本発明の目的は、可逆のブロックベース変換、例えば可逆DCTなどと、それを使用する圧縮器、並びに、そのような圧縮器を使用したロスレス又はロッシーの圧縮/伸長システムを提供することである。本発明の他の目的は、系統誤差がなく、かつミスマッチがない(又は低い)DCT変換を提供することである。本発明のもう一つの目的は、可逆DCTに使用するための丸めオフセットルックアップテーブルの生成方法を提供することである。その他の本発明の目的は以下の説明から明らかになろう。

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

0007

以下に列挙した構成の圧縮器、圧縮/伸長システム、方法及び記録媒体などが本発明に含まれる。

0008

(1)可逆離散コサイン変換(DCT)を有する圧縮器。
(2)(1)の圧縮器と伸長器とを有する圧縮/伸長システム。
(3)伸長器が可逆逆DCTを有する伸長器である、(2)の圧縮/伸長システム。
(4)伸長器が逆DCTを有する従来の伸長器からなる(2)の圧縮/伸長システム。
(5)DCTが複数の2点回転からなる(1)の圧縮器。
(6)複数の2点回転が変換からなる(5)の圧縮器。
(7)変換のそれぞれが平衡スケールファクタを持つ(6)の伸長器。
(8)各変換の両方の出力のスケールファクタが等しい(7)の圧縮器。
(9)ある変換の2つの出力のスケールファクタの積が1である(7)の圧縮器。
(10)ある変換の出力の両方のスケールファクタが1未満である(7)の圧縮器。
(11)複数の2点回転のそれぞれが可逆である(5)の圧縮器。
(12)複数の2点回転が内部丸めをしない(11)の圧縮器。
(13)2点回転の少なくとも1つがS変換からなる(5)の圧縮器。
(14)2点回転の少なくとも1つが不平衡5,1変換からなる(5)の圧縮器。
(15)2点回転の少なくとも1つが平衡5,1変換からなる(5)の圧縮器。
(16)2点回転の少なくとも1つが6,1変換からなる(5)の圧縮器。
(17)2点回転の少なくとも1つが12,5変換からなる(5)の圧縮器。
(18)2点回転の少なくとも1つが3,2変換からなる(5)の圧縮器。
(19)2点回転の少なくとも1つが4,3変換からなる(5)の圧縮器。
(20)2点回転の少なくとも1つがラダーフィルタからなる(5)の圧縮器。
(21)ラダーフィルタ内で実行される各乗算の結果が整数値に丸められる(20)の圧縮器。
(22)2点回転の少なくとも1つがその入力の関数である丸めオフセットを持つ(5)の圧縮器。
(23)2点回転の少なくとも1つがその入力の和と差の、ある除数モジュロとした剰余の関数である丸めオフセットを持つ(5)の圧縮器。

0009

(24)第1の複数の回転;該第1の複数の回転の出力の第1の組と接続され、かつ、Bの回転を含む第2の複数の回転を有する4点パラメタライズド変換;及び該第1の複数の回転の出力の第2の組と接続され、Aの回転とCの回転を含む補助マトリックスからなり;該第1の複数の回転、該4点パラメタライズド変換及び該補助マトリックスは可逆ブロックベース変換として働くブロックベース変換圧縮器。

0010

(25)Bの回転が12,5変換からなる(24)の圧縮器。
(26)第1の複数の回転が2点回転からなる(24)の圧縮器。
(27)補助マトリックスが、該第1の複数の回転の第1の2つの出力と接続された2つの入力を有する第1の2点回転;該第1の2点回転の各出力と接続された乗算器ペア;該乗算器のペアの出力と該第1の複数の回転の第2の出力を受け取るように接続された2点回転の第1のペア、及び該2点回転の第1のペアの出力を受け取るように接続された前記Cの回転及び前記Aの回転からなる(24)の圧縮器。

0011

(28)入力;及び、変換入力値変換出力値へのマッピングを有するルックアップテーブルを含む少なくとも1つの変換を有する可逆DCTを具備し、該マッピングは、丸めが入力を同じ変換値マップするところの第1のグループからの入力を、丸めに利用されなかったであろう変換出力へマップする圧縮器。
(29)少なくとも1つの変換が1以上の行列式を持つ(28)の圧縮器。
(30)丸めオフセットのためのルックアップテーブルを作成するための方法であって:初期丸めを用いて入力値の変換出力値への第1のマッピングを生成するステップ;及び該第1のマッピンにおける衝突の各行に対し(ただし、衝突は入力の同じ変換出力値へのマッピングである)、該初期丸めで用いられないであろう変換出力値を提供するために必要とされ、それぞれが該初期丸めに用いられないであろう変換出力値からなるエキストラを、それぞれ含む行の数を求めるステップ、各衝突に対し1つのエキストラを提供するために部分エキストラ行が必要なときに、ある行内の均等に間隔をおいたある個数のエキストラを選択するステップ、エキストラを列順ソートするステップ、該ルックアップテーブル内で使用するための第2のマッピングを生成するためエキストラを衝突に列順に割り当てるステップ、を含む方法。

0012

(31)入力値と変換出力値のペアを交換するステップをさらに含む(30)の方法。
(32)入力値と変換出力値のトリプレットを回転させるステップをさらに含む(31)の方法。

0013

(33)丸めオフセットのためのルックアップテーブルを作成するための方法であって:複数の入力の同じ変換出力値へのマッピングが存在する各衝突に対し、初期丸めで使用されないであろう変換出力値が存在する各エキストラに対し、所定の基準に基づき他のエキストラとの交換を割り出すステップ、及び該交換を実行するステップ、を含む方法。
(34)所定の基準が二乗誤差であり、二乗誤差が減少する交換が割り出される(33)の方法。

0014

(35)可逆ブロックベース変換と、該可逆ブロックベース変換の出力から得られるデータを符号化するため該可逆ブロックベース変換に接続されたコーダを具備する圧縮器。

0015

(36)変換がDFT変換からなる(35)の圧縮器。
(37)変換がコサイン変換からなる(35)の圧縮器。
(38)変換がサイン変換からなる(35)の圧縮器。
(39)変換がHadamard変換からなる(35)の圧縮器。
(40)変換がHaar変換からなる(35)の圧縮器。
(41)変換がSlant変換からなる(35)の圧縮器。
(42)変換がKarhunen-Loeve変換からなる(35)の圧縮器。
(43)変換が高速KL変換からなる(35)の圧縮器。
(44)変換がシヌソイド変換からなる(35)の圧縮器。
(45)変換がSVD変換からなる(35)の圧縮器。
(46)変換が重複又は直交変換からなる(35)の圧縮器。

0016

(47)プロセッサで実行された時に該プロセッサに以下のステップを実行させる命令系列を有する実行可能プログラムを格納したコンピュータ読み出し可能な記録媒体:入力データを受け取るステップ;及び可逆DCT変換を実行するステップ。
(48)命令系列が、可逆DCT変換を実行することによって生成された係数を量子化するステップを該プロセッサにさらに実行させ、該量子化はスケールファクタを用いて行われる(47)の記録媒体。
(49)命令系列が、ジグザグ順序付けのステップ;0のランレングスを生成するステップ;及び、Huffmanコーディングを実行するステップ、を該プロセッサにさらに実行させる(47)の記録媒体。
(50)命令系列が、各データに対する文脈を生成するステップ;各文脈に関連した確率予測値を生成するステップ;及び、文脈及び確率予測値に基づきビットストリームを生成するステップを該プロセッサにさらに実行させる(47)の記録媒体。

発明を実施するための最良の形態

0017

本発明によれば、可逆のブロックベース変換、例えば可逆DCTなどが提供される。本発明のDCTは、ロスレス圧縮/伸長システムに使用可能なDCTベースの圧縮器/伸長器に導入し得る。本発明によれば、系統誤差がなく、かつミスマッチがない(又は低い)DCT変換も提供される。可逆の離散コサイン変換(DCT)は、あるシステムの圧縮器の一部かもしれない。このシステムは、ロスレス伸長用の可逆の逆DCTを用いる伸長器、又はロッシー伸長用の逆DCTを用いる在来の伸長器を含むかもしれない。一実施例では、圧縮器は、多重回転(例えば2点(2×2)整数回転)、4点パラメタライズド変換、及び補助マトリックスを有するDCT圧縮器を含む。この4点変換はBの回転からなるが、補助マトリックスはAの回転とCの回転からなる。本発明によれば、可逆DCTに使用するための丸めオフセット用ルックアップテーブルの生成方法も提供される。

0018

以下、本発明の実施の形態を説明する。以下の詳細な説明において、本発明を完全に理解できるようにするため、変換の種類、係数サイズ等々の様々な具体例が示される。しかし、当業者には、そのような具体例によらずに本発明を実施し得ることが明白になろう。他方、本発明をいたずらに難解にしないため、周知の構造及びデバイスブロック図の形式で表し、詳しくは示さない。

0019

以下の詳細説明のかなりの部分は、コンピュータメモリ内のデータビットに対する演算アルゴリズム及び記号表現によって与えられる。このようなアルゴリズム記述及び表現は、データ処理技術分野の当業者によって、その研究の内容を他の当業者に対し最も効率的に伝えるために用いられる手段である。あるアルゴリズムがあり、それが概して、希望する結果に至る自己矛盾のないステップ系列だと考えられるとしよう。これらのステップは、物理量の物理的処理を必要とするものである。必ずという訳ではないが、これらの物理量は記憶、転送、結合、比較、その他処理が可能な電気的または磁気的信号の形をとるのが普通である。これらの信号をビット、値、要素、記号文字、用語、数値等で表わすのが、主に慣用上の理由から、時に都合がよいことが分かっている。

0020

しかしながら、このような用語や同様の用語は、適切な物理量と関係付けられるべきであり、また、これら物理量につけた便宜上のラベルに過ぎないということに留意すべきである。以下の説明から明らかなように、特に断わらない限り、「処理」「演算」「計算」「判定」「表示」等々の用語を用いて論じることは、コンピュータシステムレジスタ及びメモリの内部の物理的(電子的)な量として表現されたデータを処理して、コンピュータシステムのメモリまたはレジスタ、同様の情報記憶装置情報伝送装置あるいは表示装置の内部の同様に物理量として表現された他のデータへ変換する、コンピュータシステムあるいは同様の電子演算装置の作用及びプロセスを指すものである。このようなコンピュータは一般に、データを処理するために1つ又はそれ以上のプロセッサを使用し、それらプロセッサは1つ又はそれ以上のバスを介し1つ又はそれ以上のメモリと接続される。

0021

本発明はまた、本明細書に述べる操作を実行するための装置にも関係する。この装置は、要求される目的に専用に作られてもよいし、あるいは、汎用コンピュータ内蔵プログラムにより選択的に駆動または再構成したものでもよい。そのようなプログラムは、それに限定されないが、コンピュータのシステムバスにそれぞれ接続されたフロッピーディスク光ディスクCD−ROM光磁気ディスクリードオンリーメモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気カード又は光カード、あるいは電子的命令の格納に適したその他の媒体のようなコンピュータの読み出し可能な記憶媒体に格納してよい。本明細書に提示されるアルゴリズム及び表示は、本質的に、どのような特定のコンピュータ、その他装置とも関わりがない。様々な汎用マシンを本明細書に述べたところに従ったプログラムと一緒に利用してよいが、必要とされる方法のステップの実行のためのより特化した装置を作るほうが好都合であるかもしれない。これら多様なマシンに要求される構造は以下の説明より明らかになろう。さらに、いかなる特定のプログラミング言語とも関連付けることなく本発明を説明する。本明細書において述べるように、本発明の教えるところを実現するために多様なプログラミング言語を使用し得ることが理解されよう。

0022

概要>本発明は、DCTベースの圧縮をロッシーにもロスレスにもできる可逆変換を提供する。可逆変換は、その圧縮結果からオリジナルを再構成可能で整数演算によって実施される効率変換である。可逆変換の一例は、APTを拡張したものである。

0023

本発明の可逆変換は、係数の最下位ビット冗長性がない点で、効率(もしくは略効率)変換である。すなわち、本発明の変換は、(他の方法では系統誤差を排除するために用いられるであろう)多ビットの精度を必要としない点で効率がよい。効率の良さは、差分画像のある非可逆変換を用いるよりも優れたロスレス圧縮に通じる。可逆APT実行手段を構成するいくつかの方法について後述する。可逆APTは、ビデオオーサリングシステムなどに多くのアプリケーションがある。

0024

変換係数は任意の精度に丸められてよいが、本発明は変換係数を整数に丸める。整数への丸めよりも粗く丸めることは、情報を消去するので、一種の量子化である。整数への丸めよりも細かく丸めると、変換係数の最下位ビットに冗長度が持ち込まれ圧縮の妨げになる。

0025

本発明は、系統誤差のないDCT変換を提供する。系統誤差がないため、その変換は可逆変換つまりロスレス変換である。これらの可逆変換はロスレス圧縮に利用可能である。

0026

本発明は、ミスマッチの低い可逆DCT変換を提供する。±1の量子化係数ミスマッチのための最小量子化マトリックスが与えられる。この最小以上の量子化が用いられると、得られる係数を任意の逆DCTで使用可能である。

0027

本発明は、ハードウェア又はソフトウェア、あるいはその組合せによって実施してよい。

0028

<システムの概要>本発明の可逆DCTは、入力された元のデータを正確に獲得するための可逆の逆DCTを含むロスレスシステムにも、従来の(可逆でない)逆DCTを含むロッシーシステムにも使用し得る。従来のDCTも可逆DCTの出力を扱うことができる。可逆DCTの真のDCTとのミスマッチは十分に低く、普通のDCTと同じ結果を正確に得られるからである。すなわち、従来のDCT復号化器を有するMPEG又はJPEG復号化器を、本発明の可逆DCTと一緒に用いることができる。

0029

図1はロスレス及びロッシーDCTベース圧縮/伸長システムの一実施例のブロック図である。なお、本発明をDCTベースのシステムによって説明することがあるが、他のブロックベースの変換にも本発明を適用できることに注意されたい。

0030

図1において、入力データ(例えば入力画像)は本発明の可逆DCTベース圧縮器101によって圧縮される。入力画像100は、メモリから取り込まれ、あるいは通信路から受信されるであろう。なお、そのメモリも通信路も本発明を煩雑にしないため図示されていない。入力画像は、カメラデジタイザスキャナフレームグラバー(grabber)、その他の周知の装置又は類似装置によって生成されるであろう。この圧縮の結果は複数の係数であり、通信路又は記憶装置へ出力される。なお、DCTベース圧縮器の後又はその前で別の種類の圧縮がなされてもよい。

0031

ロスレス圧縮の場合には、原データを正確に再構成するため、量子化されない係数に対し可逆の逆DCT(IDCT)を有する伸長器102が使用される。ロッシー圧縮の場合には、変換係数を量子化してから、任意の逆DCT(IDCT)を使用する伸長器103によって伸長してよい。前述のように、このロッシー伸長器は、JPEG又はMPEG準拠の復号化器のような従来システムで構わない。

0032

一実施例では、DCT圧縮器は画素成分をDCT変換に取り込み、このDCT変換の出力がジグザグ順序付けされることにより周波数係数が生成される。そして、この係数は一般にロスレス・エントロピー符号化される。同様に、逆DCT伸長器では、周波数係数はロスレス・エントロピー復号化されてからジグザグ逆順序付けブロックに入力され、次にIDCT変換に入力されて画素成分が復元される。

0033

圧縮器101は通信路又は記憶装置104を介して伸長器102,103に接続されるように表されている。それらは物理的には全く相互接続されていなくてもよい。すなわち、その圧縮器を使ってデータを圧縮して記憶し、全く独立した伸長システムが、その圧縮情報又はそのコピーアクセスしてもよい。

0034

図2は、本発明の圧縮器の一実施例のブロック図を示す。図2において、当該圧縮器は入力データの色空間変換又はサブサンプリングを行う色空間/サブサンプリングブロック121を有する。このブロック121はオプショナルなブロックであり、圧縮器によっては含まれないかもしれない。一実施例では、ブロック121によって実行される色空間変換は可逆である。

0035

色空間/サブサンプリングブロック121の出力は可逆DCT122に接続される。可逆DCT122より出力される変換値はジグザク順序付けブロック123の入力へ接続され、同ブロック123は周知のジグザグ順序付けを行う。なお、このジグザグ順序付けブロック123もオプショナルである。ジグザグ順序付けブロック123の出力はランレングスブロック124に接続され、同ブロックは0のランレングスを検出する。ランレングスブロック124の出力はハフマン(Huffman)コーダ125の入力に接続され、ハフマン符号化が行われる。ハフマン符号化ブロック(ハフマンコーダ)124の出力はシグナリング(signaling)ブロック126の入力に接続され、同ブロックは復号化器が符号化データを効率的に復号化できるようにするため、使用された量子化又は符号化オプションのタイプを復号化器に通知するための信号を発生する。

0036

希望するならば、スケールファクタを用いる量子化127を、可逆DCTブロック122の後又はジグザグ順序付けブロック123の前に適用してもよい。このようなスケールファクタを用いる量子化については、より詳しく後述する。

0037

図3は、本発明の圧縮器の他の実施例のブロック図である。図3において、色空間/サブサンプリングブロック121は可逆DCT122に接続される。可逆DCT122の出力はオプショナルな、スケールファクタを用いる量子化ブロック127に接続される。スケールファクタを用いる量子化ブロック127の出力は文脈モデル133の入力に接続される。文脈モデル133はデータに対する文脈を発生する。この文脈は確率予測マシン(PEM)134へ送られる。PEM134は、受け取った文脈に基づいて、データの確率予測値を発生する。これらの確率予測値はビットストリーム・ジェネレータ(BG)135へ出力され、同ジェネレータは文脈モデル133からの文脈とPEM134からの確率予測値に基づいて、出力ビットストリームを生成する。ビットストリーム・ジェネレータ135の出力はシグナリングブロック126に接続される。

0038

図4は、ビデオオーサリングシステムへの本発明の応用例のブロック図である。図4において、1つ以上の入力装置、例えばカメラ201がビデオ画像撮影又は取得する。撮影中に、ビデオ画像はカメラ201に接続されたロスレス圧縮器202によってロスレス圧縮される。これによって、一実施例では、帯域幅とメモリの約2分の1の節約が可能であり、しかも劣化を生じない。すなわち、歪みがない。ビデオの最終的な目標圧縮率は一般的に100:1のロッシー圧縮であるが、最初のロスレス圧縮は、画質向上、デジタルエフェクト及び高画質のI−フレームとなるフレームのための情報を保存する(ビデオ圧縮の場合)。I−フレームはビデオ圧縮分野で周知であり、MPEGやHDTVのような圧縮標準に従って静止画像と同様に圧縮される。

0039

圧縮器202の出力は抽出ブロック203に接続される。編集のため、量子化DCT係数が抽出ブロック203によって抽出され、(必要なら変換符号化され(transcoded))、そして抽出ブロック203に接続されたモーションJPEG伸長器204へ送られる。抽出ブロック203は、どのフレームが必要とされるか決定し、及び/又は、各係数のある一定数のビットだけを選択することによって動作するかもしれない。例えば、後記の図31は捨てるビット数(換言すれば、どのビットを保存するか)を示している。他の実施例では、抽出ブロック203は、一部のブロックだけを選択することによって画像のクリッピングを行うかもしれない。

0040

モーションJPEG伸長器204は、安価な装置か任意の従来の装置でよい。圧縮データは既にDCT変換ドメインにあるから、様々なカットを試みたり様々な量子化で試すために必要な計算が減少する。このように、この実施例によれば、あまり多くの追加処理をせずに、情報をリアルタイムのビデオとして観察することができる。

0041

編集者がどの情報を保存するか(例えば、どのフレームを最終バージョンに残すか)決定した後、原データを復元するためにロスレス伸長器、例えば伸長器205を用いることができる。なお、データは、編集後のデータだけを格納しているか、元の入力データの全部又は一部を格納している記憶装置から取り出されるだろう。後者の場合、伸長のための適切な情報をアクセスするために何らかのロジック又は処理が必要となろう。このような処理/ロジックは当業者にとって周知であろう。

0042

圧縮歪み誇張される可能性がなければ、必要に応じ、原データの画質向上もしくは前処理のための画質向上メカニズム206を伸長器205に接続してもよい。かかる画質向上もしくは前処理の例として、画像の部分拡大スローモーションを行うためのフレーム間内挿尖鋭化ノイズ除去等々がある。このような画質向上メカニズムは当該技術分野では周知である。

0043

任意の画質向上処理の後で、MPEG圧縮器207が動き補償を含む完全なMPEG圧縮を行って最終的な圧縮データを生成する。このMPEG圧縮器207は当該技術分野では周知である。

0044

可逆DCTは、どのようなロスレス圧縮のアプリケーションに使用してもよいが、従来のロッシーDCTベースシステムと一緒に使用する場合に最も効果的である。従来システムとの互換性が問題でなければ、他の統合型ロッシー/ロスレス圧縮システム、例えば可逆ウェーブレットによる圧縮システムが使用されても構わないだろう。

0045

本発明は、任意のブロックベース変換又は2点回転に分解可能な任意の非重複変換へ拡張し得る。例えば、本発明はDFT/一元DFT、コサイン、サイン、Hadamard、Slant、Karhunen-Loeve、高速KC、シヌソイド変換、SVD変換、重複直交変換(LOT)等々の変換と共に使用し得る。Jain, AnilK.,”Fundamentals of Digital Processing,”Prentice-Hall,Inc.1989,pgs.132-138 を参照されたい。これらの例と後述の例が与えられれば、他の変換の実現は当業者には明白であろう。

0046

<APTによる高速DCT分解>Allenのパラメタライズド変換(APT)は、公式には一般化Chen変換(GCT)と呼ばれるが、DCTと、他の関連変換のファミリーを”整数回転”の縦続(cascade)に変形する。一実施例では、各回転は、その行列式の絶対値が1の変換からなる。本発明は、DCTを多数の可逆成分に伸長することによって可逆DCTを得る。このDCTは、個々のパーツが可逆であるから可逆である。

0047

図5は、1D8点順APTのブロック図を示す。APT変換の大部分は、回転角度の逆正接によってラベル付けされた2点回転からなる。(これらの回転は、”時計回り”で行列式が−1であるものとして示されている。)図5において、8点変換は、4つの45゜(arctan=1)初期回転340、4点APT320、”補助マトリックス”330に分けることができる。補助マトリックス330は、2つの乗算と複数の2点回転を含む。

0048

このように、順APT変換を構成する3組の回転がある。まず、1組の2点(2×2)回転301〜304は入力ステージとなる。回転301〜304のそれぞれの出力は、2点回転305〜308からなる4点APTブロック320の入力に接続され、また、2点回転309,312〜315と乗算器310,311からなる補助マトリックス330に接続される。

0049

詳しくは、回転301は2つの入力データサンプルに対応する入力0,7を受け取り、回転305の入力に対する出力と、回転312の入力に対する出力を生成する。回転302は入力データサンプル1,6を受け取るように接続され、2つの出力、すなわち回転306の入力に対する出力と、回転309の入力に対する出力とを与える。回転303は入力データサンプル2,5を受け取るように接続されて2つの出力を生成し、その一方の出力は回転306の他方の入力に接続され、他方の出力は回転309の他方の入力に接続される。回転304は入力データサンプル3,4を受け取るように接続されて2つの出力を生成し、その一方の出力は回転305の他方の入力に接続され、他方の出力は回転313の他方の入力に接続される。

0050

回転305は2つの出力を生成するが、その一方の出力は回転307の入力に接続され、他方の出力は回転308の入力に接続される。回転306は2つの出力を生成し、その一方の出力は回転307の他方の入力に接続され、他方の出力は回転308の他方の入力に接続される。これらの入力に応答して、回転307は0出力と4出力を生成し、回転308は2出力と6出力を生成する。

0051

補助マトリックス330に関しては、回転309は、R乗算ブロック310,311に接続される2つの出力を生成する。R乗算ブロック310の出力は回転312の他方の入力に接続され、R乗算ブロック311の出力は回転313の他方の入力に接続される。回転312は、その入力に応答して、回転314,315に接続される2つの出力を生成する。同様に、回転313は、その入力に応答して、回転314,315の入力に接続される2つの出力を生成する。これらの出力に応答して、回転314,315は1出力及び7出力と3出力及び5出力をそれぞれ生成する。A,B,C回転について以下に詳述する。一実施例では、回転301〜304のそれぞれはS変換かもしれない。しかし、その場合、ミスマッチに苦しむかもしれない。

0052

図5に示す補助マトリックスはChen形式のものである。J.Allen in,”Generalized Chen Transform for Image Compression,” Jounal ofElectronic Imaging,Vol.3(4),October 1994,pgs.341−347に述べられているHeinとAllen,J.Allen による補助マトリックスの代案図7に示す。図7において、当該補助マトリックスは(ある角度の)6つの回転からなる。回転角度が45゜(すなわちarctan=1)の1対の回転がそれぞれ2つの入力を受け取って2つの出力を生成するように接続される。回転401,402のそれぞれの出力の一方は回転403の入力に接続され、回転401,402の他方の2つの出力は回転404の入力に接続される。これらの入力に応答して、回転403,404は2つの出力を生成する。回転403,404はB回転からなる。回転403,404のそれぞれの出力の一方は回転405の入力に接続され、回転403,404のそれぞの他方の出力は回転406の入力に接続される。回転405,406はそれぞれA回転、B回転からなる。回転405,406はそれぞれ2つの出力1,7と5,3を生成する。

0053

一実施例では、回転は2点(2×2)回転である。各回転は2点変換もしくはフィルタからなるかもしれない。

0054

出力はDCTにマッチするようスケーリングされる。すなわち、本発明が生成する出力は、浮動小数点DCTによれば得られるであろう出力とマッチするように変化させるためのスケールファクタを用いる必要がある。ロッシー圧縮/伸長の場合、スケールファクタは量子化ファクタと組み合わせられてよい。各出力用のスケールファクタは、各2点回転のための各スケールファクタの積から決定することができる。図5に示した形式の2点回転マトリックスの場合、各回転の両方の出力のためのスケールファクタは次式によって与えられる。

0055

0056

0057

0058

分離可能な2次元(2D)64点DCT(APT)は、8つの1D8点DCT(APT)、1つの転置、及び、別の8つの1D,8点DCT(APT)によって実現できる。

0059

図6は、同じスケールファクタを有するAPTの中間値を示す。図6において、各網掛け線は同じスケールファクタを持つ入力を示す。同一のスケールファクタを用いることは2点変換の除数を拘束する。例えば、殆どの1の回転(309以外の全ての回転)は両方の出力に対し同じスケールファクタを持つ必要がないので、S変換のような不平衡変換を用いてよい。これに対して、1の回転とRによる乗算(309)の縦続は、出力に関し入力と同じスケールファクタを持たなければならない。

0060

図6において、回転307に対する2つの入力は同一のスケールファクタを有する。回転308に対する2つの入力は同一のスケールファクタを有する。回転314に対する2つの入力は同一のスケールファクタを有し、回転315に対する2つの入力は同一のスケールファクタを有する。回転305と回転306の入力は同じスケールファクタを有する。このことは、回転305の場合に、回転301,304それぞれからの上側の枝を拘束することになろう。回転312,313に関しては、それらの入力が同じスケールファクタを有するだけではなく、回転301,304それぞれからの下側の枝が全て同一のスケールファクタを有する。回転301,304から出る下側の枝のスケールファクタは回転302,303から出る下側の枝のスケールファクタと同じであるから、補助マトリックスに対する全ての入力のスケールファクタが同一である。2つの出力のスケールファクタの積が膨張量である。したがって、効率をよくするには、両方のスケールファクタの積を理想的には1にして膨張を防がなければならない。一実施例では、可逆にするため、両方のスケールファクタが1である。他の実施例では、スケールファクタは僅かに異なってもよい。例えば、両方のスケールファクタを0.99にしてよい。

0061

図19は、3つの異なった実施例のためのAPTパラメータの値を示す。最初のパラメータの組はDCTとなる無理数である。圧縮のためのDCT実行手段(APTその他)は、これらの無理値を使用できない。現実のDCT実行手段はすべて無理パラメータを近似する(その近似値は非常に正確な高精度浮動小数点近似値であるが)。APTは小さな整数による有理近似値を使うため、扱いやすい可逆実行手段となる。

0062

図19は、単純さとミスマッチとの兼ね合いを図る3組のAPTパラメータを示す。APT1は簡単で圧縮用に好適である。他の例であるAPT2とAPT3は、より精密な無理変換の近似である。APT3はCCITTRec.H.261(IEE規格1180-1990)精度試験満足する。

0063

可逆変換において、APTパラメータの選び方がミスマッチの唯一の原因ではない。可逆の効率変換では、変換の各ステップにおいて注意深い(可逆の)整数への丸めを行う必要がある。これらの丸め処理もミスマッチの原因となる。浮動小数点の実行手段と同じ結果をもたらす方法は効率可逆のものであるはずがないので、多少のミスマッチは避けがたい。通常、丸めに起因するミスマッチはパラメータの選び方に起因するミスマッチより大きいから、APT1パラメータは良好な一つの選択である。しかし、本発明の手法は他のパラメータに適用してもよい。

0064

なお、これらのAPTパラメータを、他の可逆又は不可逆の変換が得られるように調整してもよい。

0065

<可逆DCT実行手段>本発明において、APTの構成要素中の各2点回転は可逆とされる。各2点回転を可逆にすれば、各ステップを逆にしてよいのでAPT全体が可逆になる。効率のほかに、2つの性質、すなわちスケールファクタが平衡していること、内部の丸めがないことが望ましい。

0066

2点変換が”平衡”スケールファクタを持つのは、両方の出力のスケールファクタが同一であるときである。変換が効率変換(又は略効率変換)となるために、その行列式は±1(又は、ほぼ±1)である。行列式が±1にされると、2つの出力のスケールファクタの積は1である。両方のスケールファクタが1であることが望ましい。別の実施例では、一方のスケールファクタが他方のスケールファクタの逆数である。この場合、一方のスケールファクタは1より大きい。かくして、行列式が±1になる。1を超えるスケールファクタは量子化の原因となり、結果としてミスマッチを生じさせる。

0067

なお、前出の式中のスケールファクタは、効率変換でないAPTのためのものであるから、それらの積は1ではない。両方のスケールファクタを1未満にすると、低ミスマッチを見込むのに適した丸めとなるが、そのようなシステムは可逆効率変換ではない。

0068

各ステップでの丸めは可逆性を与える。”内部丸めのない”2点回転とは、各ステップの出力で最大でも2つの丸め操作しか行われないことを意味する。ステップ内部に付加的な丸め操作がある実行手段もある。例えば、後述のラダーフィルタ手段である。余分な丸めはミスマッチを増加させる。

0069

DCTは、ロッシー圧縮に用いられるときには、順変換逆変換の両方に同じ変換を使用できるようにユニタリである。しかし、本発明では、可逆実行手段の場合、逆変換は丸めを逆転させる。したがって、逆変換は、図6に示したデータフローとは逆のデータフローを持ち、それぞれの順方向の2点変換と乗算は対応した逆変換で置き換えられる。

0070

<内部丸めもルックアップテーブルも用いない可逆実行手段>本発明は、一実施例において、内部丸めもルックアップテーブルも必要としない2点回転及び乗算の可逆実行手段を提供する。これらは、このタイプの効率平衡2点回転を持つパラメータにとって重要な構成要素である。平衡変換でない又は略効率変換にすぎない、いくつかの2点変換を以下に説明する。ラダーフィルタとルックアップフィルタの代案が提供される。

0071

しばしば、オフセットの選び方によって達成される可逆性が支配される。何故あるオフセットだけで可逆変換となるかについて以下に説明する。

0072

”1”:1,1-変換,S-T変換−不平衡
一実施例において、”1”ブロックは次の変換によって実現される。ただし、aとbは順変換の入力であり、xとyは順変換の出力である。

0073

0074

一実施例では、スケールファクタはそれぞれ√2と1/√2である。

0075

”A”:5,1-変換−不平衡
次に示すものは”A”回転の一実施例である。

0076

0077

ただし、回復される最下位ビットは次式で与えられる(すなわち、切り捨てられたビット):
δ≡(5y-13) mod 26
本実施例では、スケールファクタはそれぞれ√26と1/√26である。

0078

”A”:5,1-変換−平衡,非効率
次に示すものはA回転の別の実施例である。

0079

0080

この変換の行列式は26/25=1.04である。したがって、その冗長度はlog21.04=0.06ビットである。これは非効率変換ではあるが、ロスレス圧縮に使用できるほど効率変換に近い。平衡であるので、平衡効率変換より、ロッシー圧縮の目的に有益である。一実施例では、スケールファクタは両方とも5/√26 である。

0081

”A”:60,11-変換−平衡,効率
”A”回転の他の実施例は次の通りである。

0082

0083

この変換は平衡・効率変換である。この変換は11,60,61を使うが、これはピタラスのトリプレットa,b,cで、b+1=c かつ a2=2b+1である。しかし、結果の60/11≒5.4545 は7π/16≒5.0273 のあまりよい近似値ではない。ここでは、平衡、効率であることと計算の容易さのため、DCTへの近似度犠牲にされている。この場合、スケールファクタは共に1である。

0084

”B”:12,5-変換
次に示すものは”B”回転の一実施例である。

0085

0086

これは平衡・効率変換である。数値5,12,13 は、ピタゴラスのトリプレットa,b,c で、b+1=cかつa2=2b+1である。これは非常に良好な4点APT(DCT)である。スケールファクタは共に1である。

0087

なお、オフセットは可逆性にとって非常に重要である。上式の順変換の両方のオフセットとして+6を選ぶと可逆変換になるが、他のオフセットでは可逆変換とはならない。例えば、下式におけるようにオフセットが両方とも0であると、入力a=0,b=0と入力a=1,b=0に対する結果は共にx=0,y=0である。

0088

0089

この結果から、オフセットの選び方で可逆性を制御できることが明らかである。

0090

両方のオフセットが+5である別の例を下に示す。この場合、入力a=4,b=0と入力a=4,b=1に対する結果は共にx=4,y=1である。

0091

0092

殆どのオフセットのペアで、可逆変換とはならない。オフセット(0...12)の可能な169個のペアの中で、可逆性が得られるのは、 0,10;1,5;2,0;3,8;4,3;5,11;6,6;7,1;8,9;9,4;10,12;11,7 の13個のペアだけである。

0093

”C”:3,2-変換−不平衡
”C”回転の一実施例は次の通りである。

0094

0095

これは効率変換である。この場合、スケールファクタは√13と1/√13である。

0096

”C”:3,2-変換−和の増加が不平衡
和の増加が不平衡であっても効率変換である、”C”回転の他の実施例は次のとおりである。

0097

0098

この場合、スケールファクタはそれぞれ1√13と√13である。不平衡変換においては、和をそれより大きい除数で除算するのが好都合である。これは係数サイズの最小の増加につながる。しかし、和はより視覚的に適切な係数につながる。差に対し大きな除数を使って、より大きな和の増加を許容すると、視覚的により適切な係数でのミスマッチが低くなる。

0099

”C”:4,3-係数−平衡
平衡変換である、”C”回転の他の実施例は次の通りである。

0100

0101

この変換は平衡・効率変換である。数値の組3,4,5はピタゴラスのトリプレットa,b,cで、b+1=cかつa2=2b+1である。しかし、4/3≒1.3333は、tan 5π/16≒1.4966 に対するあまり良い近似値ではない。スケールファクタは共に1である。

0102

乗数”R”:√2
一実施例では、乗法因子に√2の整数近似値を用いる。R因子は補助マトリックスを正規化する。

0103

0104

<DCT以外の変換>図8は、8点Hadamard変換を示す。図8において、回転501〜512は、tan(π/4)=1 の2点回転からなる。回転501は、入力データサンプル0,7を受け取って回転505,507への出力を生成するように接続される。回転502は、入力データサンプル1,6を受け取って回転506,508への出力を発生するように接続される。回転503は入力データサンプル2,5を受け取って回転506,508への出力を生成するように接続され、また、回転504は入力データサンプル3,4を受け取って回転505,508に対する出力を生成するように接続される。

0105

回転505は、その入力に応答し、回転509,510に対する出力を生成する。回転506も、その入力に応答してと回転509,510に対する出力を生成する。回転509はその入力に応答して出力サンプル0,4を生成し、また、回転510はその入力に応答して出力サンプル2,6を生成する。

0106

回転507は回転511,512に対する出力を生成する。回転508も回転511,512に対する出力を生成する。これらの入力に応答し、回転505は出力サンプル1,5を生成し、回転512は出力サンプル3,7を生成する。

0107

図9は8点Harr変換を示す。図9において、当該Harr変換は、それぞれtan(π/4)=1の2点回転である回転520〜526からなる。回転520は入力データサンプル0,1を受け取って、出力データサンプル4と回転524への出力を生成するように接続される。回転521は入力データサンプル2,3を受け取って、回転524への出力と出力データサンプル5を生成するように接続される。回転522は入力データサンプル4,5を受け取って回転525への出力と出力データサンプル6を生成するように接続される。回転523は入力データサンプル6,7を受け取って回転525への出力と出力データサンプル7を生成するように接続される。回転524は、その入力に応答して出力データサンプル2と回転526への出力を生成する。回転525は回転525への出力と出力データサンプル3を生成する。回転526は、その入力に応答してサンプル0,1を出力する。

0108

図10は4点サイン変換の一実施例を示す。図10において、当該サイン変換は回転531〜534からなる。回転531,532はtan(π/4)=1の2点回転からなり、回転533,534はDの回転からなる。なお、Dはtan(0.1762π)として示されている。

0109

回転531は入力データサンプル0,3を受け取って回転533,534への出力を生成するように接続され、回転532は入力データサンプル2,1を受け取って回転533,534に対する出力を生成するように接続される。それらの各入力に応答し、回転533は出力データサンプル1,2を生成し、回転534は出力サンプル3,1を出力する。

0110

図11は、4点Slant(傾斜)変換の一実施例を示す。図11において、当該Slant変換は回転540〜543からなる。回転540〜542はtan(π/4)=1の2点回転からなり、回転543はtan(0.1024π)の2点回転からなる。回転540は入力データサンプル0,3を受け取って回転542,543への出力を生成するように接続され、回転541は入力データサンプル2,1を受け取って回転542,543への出力を生成するように接続される。回転542は入力に応答して出力データサンプル0,2を生成し、回転543は入力に応答して出力データサンプル3,1を生成する。以上に述べた例から、当業者は他の変換も実現できるであろう。

0111

<ラダーフィルタによる効率・可逆2点回転>ラダーフィルタを使って、どのような2点回転も可逆・効率・平衡形で実現できる。ラダーフィルタは両方のスケールファクタが1に等しい。下記の式は行列式が1の(反時計回り)回転のためのラダーフィルタ分解である。

0112

0113

可逆かつ有効であるために、図12及び図13に示すように、各乗算の後に整数への丸めが続く。可逆であるために、無理数による乗算が順変換と逆変換において同様に行われる。

0114

図12に、入力610,611を持つラダーフィルタ手段が示されている。入力611は乗算器602に接続され、この乗算器602は(cosθ-1)/sinθを入力610に掛ける。この乗算の結果はブロック603で最近整数に丸められる。この丸めの結果は加算器604によって入力611と加算される。加算器604の出力は乗算器606に接続され、sinθと乗算される。この結果はブロック605で整数に丸められる。丸めの結果は加算器601によって入力610と加算される。加算器601の出力は当該ラダーフィルタの一方の出力612である。加算器601の出力は乗算器607にも入力され、(cosθ-1)/sinθと乗算される。この乗算の結果はブロック608で整数に丸められる。丸めの結果は、加算器609によって、加算器604の出力と加算される。加算器609の出力は当該ラダーフィルタの他方の出力613である。

0115

図13において、2つの入力701,702が当該ラダーフィルタに入力する。入力701は乗算器703に入力されて(cosθ-1)/sinθと乗算される。この乗算の結果はブロック704で整数に丸められる。この丸めの結果は、減算器705によって入力702から減算される。減算器705の出力は乗算器706の入力に接続され、sinθと乗算される。この乗算の結果はブロック707で整数に丸められる。丸め結果は減算器708によって入力701より減算される。減算器708の出力は当該ラダーフィルタの一方の出力712である。

0116

減算器708の出力は乗算器709の入力にも接続され、(cosθ-1)/sinθと乗算される。この乗算の結果はブロック710で整数に丸められる。この丸めの結果は減算器711によって減算器705の出力から減算される。減算器711の出力は当該ラダーフィルタの他方の出力である。

0117

3つの丸め操作の影響と無理乗算の実行精度の影響によりミスマッチ誤差が生じる。しばしば、ラダーフィルタ手段は他の手段よりも大きなミスマッチ誤差がある。

0118

DCT全体を2×2回転に分解しないで、もっと大きなラダーフィルタを作成できる。例えば、下に示すような3つのマトリックスに分解することにより、4点DCTをラダーフィルタとして実現できる。

0119

0120

これらマトリックスは以下の定数を含んでいる。

0121

0122

このように、本発明は、新規な4点可逆変換を提供するとともに、4点(4×4)回転のための効率・可逆2×2分解を行う。

0123

なお、以上の説明中の変換には2点DCT、4点APT、8点非自明なマトリックスが含まれていたが、本発明は例えば16×16など他のサイズへ拡張されてもよい。

0124

<効率・可逆2点回転のためのルックアップテーブル>ラダーフィルタを使用して、任意の2点回転のための効率・可逆手段を作ることができる。本発明は、丸めを改善した効率・可逆変換を作るための、ルックアップテーブルをベースにした丸め制御方法及び装置を提供する。改良された丸めはミスマッチ誤差を減らす。平衡変換を作成でき、また、ある変換が平衡のときには両方のスケールファクタが1である。

0125

行列式が1以上の変換の場合、入力値の変換値への1対1又は1対多のマッピングが可能である。可逆変換にとっては、1対1のマッピングだけが重要である。行列式が1より少し大きい変換の場合、少数の可能な変換値を未使用としてよく、また、マッピングは1対1として扱ってよい。

0126

丸めオフセットを固定的に選択したのでは可逆にすることができない2点整数回転がある。例えば、次式を考える。これは、図19にAPTパラメータRとして示された近似値による45゜回転である。

0127

0128

これは、丸めオフセットが定数の場合には可逆でない。しかし、丸めオフセットが入力の関数であれば、その関数を可逆にできる。すなわち、丸めが入力の関数として変化する。さらに、この場合、丸めオフセットは、入力の和及び差のモジュロ181(=除数)剰余の関数にすぎない。この関数の一例について図20と関連させて以下に説明する。したがって、181×181=32761個の丸めオフセットのペアしかない。一実施例では、上式のモジュロ部は除かれる。

0129

図14は、45゜回転のための入力値の出力変換値へのマッピング部分を表している。上記等式は次のように表すことができる。

0130

0131

入力の和と差がそれぞれsとdである(s=a+b,d=a−b)。なお、差と和のパリティは同じである、すなわち両方が偶数であるか両方が奇数である。網掛けされた四角は、発生し得ない値のペア(そのパリティが同一でないから)を示す。網掛けされていない値のペアだけが実際に発生する。sとdを√2で割って普通の整数への丸めを行った値も示されている。太線は同じs/√2とd/√2を持つ値のペアをグループ化している。網掛けされていない四角を1つ有する全ての太線領域については既にマッピングは1対1である。網掛けされていない四角を2つ有する領域は、”衝突”又は”孔”が生じる問題があることを示しており、この領域においては、普通の丸めは2つの可能な入力を同じ変換値にマップし、それら両方の入力が同じ答えを与えてしまうことになる。1つの網掛けされた四角だけの領域は”エキストラ(extra)”、すなわち普通の丸めに利用されない変換出力値を意味している。矢印は、適切な丸めによって、衝突であるところの入力に対するエキストラの出力値を用いマッピングを1対1にできるようにする方法を示している。

0132

例えば、s入力とd入力が2と2である場合、その出力は1,1にはならず、0,2となろう(矢印801を参照)。逆変換を行う時には、ルックアップテーブルの0,2のためのエントリーは、出力1,1を指すであろう。行列式≧1の条件は、各衝突に対し少なくと1つのエキストラが存在することを保証する。衝突が近傍のエキストラによって表現されるならば、丸めによるミスマッチは減少し、おそらく最小化されるだろう。

0133

図15は、近似値1/√2≒29/41=0.7073を用いる45゜回転の場合の衝突("o")とエキストラ("+")を示す。(可能性のあるもの全部を1ページに表示できるように、分母として、181に代え、より小さな41が使われている。分母が181の場合の対応図は同様である。) 本例では、行列式は非常に1に近く(1.0006である)、エキストラの個数は衝突の個数と等しい。ペアを持たない衝突又はエキストラの個数は変換の膨張を表す。

0134

図20は、近似値1/√2≒5/7=0.7143を用いる5゜変換のためのマッピングの例を示す。これはあまり正確ではなく、また、その分母は全ての可能な入力ペア(和、差)が1ページに列挙可能になるような小さな値である。各ペア毎に二乗誤差の和が列挙されている。なお、両方の入力が0の時以外は、最良の整数への丸めが用いられたとしても多少の誤差がある。ペアの最近整数への丸めの平均RMSEは1/√2≒0.289である。近似値5/7では25個の可能な入力ペア中、4個の衝突がある。この近似値では、これらの4個の衝突がRMSEを0.6529に増加させる。”丸めオフセット”欄は、ルックアップテーブルの出力である。順変換の場合には”和、差入力”欄が入力であり、逆変換の場合には”可逆性のための整数出力”欄が入力である。

0135

図19に示した近似値128/181はかなり正確である。分子の128は2のベキ乗で、計算に都合がよい。行列式は1.0002(log21.0002=0.0003ビット)で、これは非常に効率に近い。適切なルックアップテーブルによれば、平均RMSEは0.4434であり、ピーク誤差は1.92である。

0136

<順計算>2×2DCTのための回転の完全な順計算は次のようになされる。ここでは、近似値1/√2≒128/181を用いる。まず、順変換を計算するため、入力a,bの和と差が下式により計算される。
和(sum)=a+b
差(difference)=a−b 。

0137

次に、下式により和と差が181で割り算され、剰余が保存される。(なお、実行手段によっては、除算の高速化のため128/181≒181/256が用いられることがある。)
ss=和/181
dd=差/181
s=和 mod 181
d=差 mod 181 。

0138

ルックアップテーブルは、モジュロ181値s,dのペアが同じパリティを持つ(s,dが共に偶数であるか共に奇数である)と仮定する。ssとddが同じパリティを持たないとにきは、その一方のモジュロ値のパリティが変更される。この変更は、値が0...180の範囲内に納まるようになされる。下の擬似コードにおいて、”^”は排他的ORを意味する。このステップは奇数の分母の場合に必要とされ、偶数の分母の場合には必要でない。

0139

擬似コードは以下のとおりである:if(ssが奇数かつddが偶数)又は(ssが偶数かつddが奇数)
if(d==180)
s'=s^1
else
d'=d^1 。

0140

1/2の平方根とs,dの積は、128/181(又は181/256)又はルックアップテーブルを使って決定できる。丸めオフセットはルックアップテーブル内に見つかるであろう。一実施例では、丸めオフセットは−1...1であるので、ルックアップテーブルのデータ幅を2ビットにできる。ssとddで表された入力の平方根はそれぞれ128ssと128ddであり、これらはシフトで実行してよい。
x=sqrt(1/2)*s'+LUT_f[s',d']+128*ss
y=sqrt(1/2)*d'+LUT_g[s',d']+128*dd 。

0141

これは次の等式のためのものである:

0142

0143

また、ルックアップテーブルがs(又はd)の平方根と丸めオフセットを返してもよい。一実施例では、そのようなルックアップテーブルは7ビットのデータ幅を持つ。
x=LUT_sqrt1/2_f[s',d']+128*ss
y=LUT_sqrt1/2_g[s',d']+128*dd 。

0144

sとdの値は0から180まで変化するが、全てのペアが発生するわけではない。fとgが次元(10)の配列の場合に、1Dルックアップテーブルをs+181*dで指標付けすると、メモリロケーションのほぼ半分が無駄になるであろう。181は奇数であるから、s'/2+181*d'/2を使うと境界条件をうまく処理できない。次の指標付け方法を用いることができる。
指標=s'/2+d'*90+(d+1)/2 。

0145

図18は本発明による回転の一実施例のブロック図である。図18において、入力a,bは加算器1201によって加算されて和(s)が得られ、また入力a,bは減算器1201に入力されて差a−b(d)が求められる。和(s)は除算器1203に入力され128で除算される。除算器1203の剰余出力はパリティ訂正ブロック1205の入力に接続され、また、商出力は乗算器1206に接続される。減算器1202の差出力は除算器1204に入力され、除算器1204はそれを181で除算し、剰余をパリティ訂正ブロック1205の他方の入力へ出力し、また商を乗算器1207の入力へ出力する。パリティ訂正ブロック1205は前述のパリティ訂正を行ってs'とd'を出力し、このs'とd'はルックアップテーブル(LUT)1208と乗算器1209,1210へそれぞれ接続される。

0146

乗算器1206は除算器1203より出力されたssに128を乗算し、その結果を加算器1211へ出力する。乗算器1207は除算器1204の出力ddに128を乗算し、その結果を加算器1212へ出力する。乗算器1209は、s'に1/2の平方根を乗算して結果を加算器1211へ出力し、また、乗算器1210はd'に1/2の平方根を乗算し結果を加算器1212へ出力する。

0147

LUT1208は前述のfとgを生成し、それらを加算器1211,1212へそれぞれ出力する。加算器1211はその入力を加算して回転のx出力を発生し、他方、加算器1212はその入力を加算してy出力を生成する。

0148

<逆計算>一実施例では、完全な逆計算をするために、近似値1/√2≒128/181が用いられる。

0149

まず、下式により、入力x,yが128によって除算され、その剰余が保存される。
ss=x/128
dd=y/128
i=x mod 128
j=y mod 128 。

0150

次に、モジュロ128値は2の平方根と乗算され、そして丸めオフセットが減算される。(これは1つのLUTに併合可能である。) iとjは0から127までの値であるから、複雑な指標付け方法を必要とせずに、ルックアップテーブルのエントリーの全て(又は使用されないエキストラがあるときには殆ど)を使用できる。
s=sqrt(2)*i−LUT_f_inverse[i,j]
d=sqrt(2)*j−LUT_g_inverse[i,j] 。

0151

その後、奇数分母に関しssパリティがddパリティと同じでない場合に対する補正が、一実施例では次の擬似コードに従って行われる:if(ssが奇数かつddが偶数)又は(ssが偶数かつddが奇数)
if(d==180)
s'=s^1
else
d'=d^1 。

0152

次式に従って和と差が計算される:
和=s'+181*ss
差=d'+181*dd 。

0153

最後に、次式に従って、和と差が再び元の値に変換される:
a=和/2+(差+1)/2
b=和/2−差/2 。

0154

この逆計算は、図18に示したものと同様の方法で実行してよいが、その方向は逆になる。そのような実行手段は、当業者にとって図18を検討すれば明白であろう。

0155

<丸めオフセットのためのテーブルルックアップの作成>全ての孔に対しエキストラが割り当てられる。ルックアップテーブルが非常に小さい場合には、最適マッピングを探すために全数探索を使用してよい。大きなルックアップテーブルに対しては、それを逐次改良するために利用可能ないくつかの手法がある。

0156

第1の手法は、エキストラを衝突へ決定論的に割り当てる方法である。一実施例では、エキストラ数は衝突数を下回らない。エキストラは、飛び飛びの衝突に割り当てられる。この手法は高速であり、またプロセスを両端で折り返すことができる。また、この手法によれば、ルックアップテーブルを進行中に生成し得るので、ルックアップテーブルを送る必要がなくなる。

0157

各衝突行に対しカレント衝突行中の全ての衝突のためエキストラを用意するのに必要となるエキストラ行数を決定する、1つのエキストラ行の一部が必要とされるならば、該行内の適当数のエキストラを均等間隔で選択する、そのエキストラ全てを列順に処理されるようにソートする、エキストラを列順に衝突へ割り当てる。

0158

発生間隔はエキストラに対する衝突の相対的個数に基づいて決まる。衝突数をエキストラ数で除算することにより、指標因数が生成される。それぞれについて最も近い整数に丸めることにより、使用すべき衝突を示す整数の集合を得る。

0159

説明のため、図15に示した衝突とエキストラのパターンを考える。144個の衝突が12行×8個のパターンで存在する。144個のエキストラが8行×9個と9行×8個のパターンで存在する。初めの3行の衝突についての割り当ては以下のとおりである。その他の衝突行も同様にして割り当てられる。

0160

第1行の12個の衝突
列3,7,13,17,21,27,31に8個のエキストラがある第1エキストラ行を用いる第2エキストラ行の9個のエキストラ中の4個のエキストラを用いる、列4,14,24,34のエキストラを用いる
割り当て(エキストラ行,エキストラ列→衝突列)は、1,3→2;2,4→6;1,7→8;1,13→12;2,14→16;1,17→18;1,21→22;2,24→26;1,27→30;1,31→32;2,34→36;1,37→40 である
第2行の12個の衝突
第2エキストラ行の9個のエキストラ中から残りの5個のエキストラを用いる、列0,10,28,38のエキストラを用いる
第3エキストラ行の8個のエキストラ中の7個のエキストラを用いる、列3,7,13,17,21,27,31のエキストラを用いる
割り当て(エキストラ行,エキストラ列→衝突列)は、2,0→2;3,3→6;3,7→8;2,10→12;3,13→16;3,17→18;2,20→22;3,21→26;3,27→30;2,28→32;3,31→36;2,38→40 である
第3行の12個の衝突
第3エキストラ行の8個のエキストラ中の残りの1個のエキストラを用いる、列37のエキストラを用いる
第4エキストラ行の列0,4,10,14,20,24,28,34,38の9個のエキストラを用いる
第5エキストラ行の8個のエキストラ中の2個のエキストラを用いる、列3,21のエキストラを用いる
割り当て(エキストラ行,エキストラ列→衝突列)は、4,0→2;5,3→6;4,4→8;4,10→12;4,14→16;4,20→18;5,21→22;4,24→26;4,28→30;4,34→32;3,37→36;4,39→40 。

0161

初めのマッピングが与えられれば、傾斜降下法(ミスマッチが減少するならエキストラ/衝突割り当てを交換)又は類似の最適化法(例えば模擬アニーリングなど)によってマッピングを改善することができる。もう一つの最適化法が、B.Kerninghan,Lin,An Efficient Heuristic Procedure forPartitioning Graphics,Bell Syst.Tech.J.,pp.291-307,1970 に記載されている。最適化は、衝突とエキストラだけを考慮して行われても、全ての入力値及び出力値を考慮して行われてもよい。最適化は、入力及び出力のペアを交換(swap)することによって行われても、入力及び出力のトリプレットを回転することによって行われてもよい。一実施例では、二乗誤差を減少させる交換又は回転が、それ以上の改善が不可能になるまで行われる。

0162

下記の擬似コードは、高水準の最適化法の一実施例である。これは改善手順を説明するものである。この方法は、ペア(前の割り当て)の交換を考慮に入れている。未割り当てのエキストラを割り当て済みの衝突−エキストラのペアと交換することを考慮に入れている。誤差が変わらない、すなわち誤差の方向だけが問題である交換も考慮にいれている。誤差を変化させない交換は、将来の交換が誤差を改善させる場合に行われる、すなわち3つのペアに関する三重の交換又は回転の一部である。

0163

for 各衝突
現在の割り当ての二乗誤差を計算する
do
for 各エキストラ
エキストラペア交換を"未交換"(例えば-1)に初期化する
エキストラ三重交換を"未交換"(例えば-1)に初期化する
交換獲得を0に初期化する
for K=先頭交換候補エキストラ(例えば0)to 最終交換候補エキス
ラ(例えばエキストラ数-1)
エキストラ[k]のより良い割り当てを探索する
if より良い割り当てが見つかる
交換を実行する
while より良い割り当てが見つかる。

0164

角度qの回転の場合、二乗誤差を計算するため以下の手順を用いてよい。
XCを第1の衝突座標とする
YCを第2の衝突座標とする
XEを第1のエキストラ座標とする
YEを第2のエキストラ座標とする
SIN=sinqとする
COS=cosqとする
二乗誤差=(COS*XC-round(COS*XE))^2+(COS*YC-round(COS*YE))^2 。

0165

前記”エキストラ[k]のより良い割り当てを探索する”ルーチンの一実施例の擬似コードは以下のとおりである:
最良交換のための二乗誤差の最良改善を0に初期化する
エキストラ[k]とエキストラ[n,n>k]の間で最良ペア交換を探索する
if 最良ペア交換は交換しないときと同じ二乗誤差を有する
エキストラ[k],エキストラ[n],エキストラ[m,m>n又はn>m>k]の間で
最良三重交換を探索する
if エキストラ[n]又はエキストラ[k]又はエキストラ[m]は交換のマー
クが付けられている
最良三重交換を無視する
if 最良交換は二乗誤差を減少させる
if エキストラ[n]はペア交換のマークが付いている
エキストラに”未交換”のエキストラ[n]と交換
するマークを付ける
if エキストラ[n]は三重交換のマークが付いている
エキストラに”未交換”のエキストラ[n]と交換
するマークを付ける
if エキストラ[k]に三重交換のマークが付いている
エキストラに”未交換”のエキストラ[k]と交換
するマークを付ける
if 三重交換が最良交換でありかつエキストラ[m]に三重
交換のマークが付いている
エキストラに”未交換”のエキストラ[n]と交換
するマークをつける
if ペア交換が最良交換である
エキストラ[n]にエキストラ[k]と交換するマーク
を付ける
エキストラ[k]にエキストラ[n]と交換するマーク
を付ける
else
エキストラ[n]に三重交換するマークを付ける
エキストラ[k]に三重交換するマークを付ける
エキストラ[m]にエキストラ[n]及びエキストラ
[k]と三重交換するマークを付ける。

0166

前記”最良ペア交換を探索する”ルーチンの一実施例のための擬似コードは以下のとおりである:
for 各エキストラ[n]
交換誤差=エキストラ[n],衝突[k]の二乗誤差+エキストラ[k],衝突[n]
の二乗誤差 を計算する
現在誤差=エキストラ[n],エキストラ[k]の現在の割り当ての二乗誤差
の和 を計算する
本改善=現在誤差−交換誤差
if (本改善>=0)かつ(本改善>=最良改善)
最良改善=本改善
これまでに見つかった最良交換はnである。

0167

前記”最良三重交換を探索する”ルーチンの一実施例のための擬似コードは以下のとおりである:
for 各エキストラ[n]
交換誤差=エキストラ[m],衝突[k]の二乗誤差+エキストラ[n],衝突[m]
の二乗誤差+エキストラ[k],衝突[n]の二乗誤差 を計算す

現在誤差=現在誤差−交換誤差 を計算する
if (本改善>=0)かつ(本改善>=最良改善)
最良改善=本改善
これまでに見つかった最良交換はnである。

0168

前記”交換を実行する”ルーチンの一実施例のための擬似コードは以下のとおりである:
for 各エキストラ[k]
if エキストラ[k]にマークが付けられている
n=エキストラ[k]と交換すべきエキストラ
if n<k
エキストラ[n]とエキストラ[k]を交換する
現在の割り当ての二乗誤差を計算する。

0169

<略平衡DCT実行手段>ルックアップテーブルをベースとした丸めは、低ミスマッチの任意の2点回転を実現可能である。本発明は、ルックアップテーブル手法(又は他の手法)によって効率かつ略平衡で可逆的に実行可能な変換を生成できる。

0170

平衡効率変換となるのは、その行列式が完全平方な時である。略平衡変換は、変換マトリックス内の全ての値にある定数を乗算することによって作られる。その定数は、行列式を2つの極めて近い因数に因数分解できるように選ばれる。図21は略平衡変換のいくつかの例を示す。

0171

図21LCM欄には、分子の共通因数を消去後の分母の最小公倍数が記されている。この変換を実行するりら、LCM2 のサイズのルックアップテーブルで十分である。大きな値は、LCDで除算されて商と剰余に分けられる。図21中の変換に必要とされるルックアップテーブルは全て大きすぎ、具体例を容易には理解できない。一例として、乗数2を持つ2,1略平衡変換を以下に説明する。

0172

0173

2つの除数は5と4で、これは平衡比1.25を持つ。この例は102=100のテーブルサイズしか必要とせず、テーブルは単純な構造を持つ。

0174

図22は、その変換のためのルックアップテーブルである。四角形以外はすべて下式によって決定されてる。四角形はエキストラに割り当てられた衝突を指している。

0175

0176

図16は、aとbが0....10の範囲内のときに上式より発生するx,yのペアをプロットしたものである。丸印と矢印は衝突のエキストラへのマッピングを示す。

0177

<8×8変換>前述の様々な基本要素を各種の8×8可逆APTに使用してよく、そのいくつかを図23に示す。図5に示した補助マトリックスのChen分解が用いられるが、例外的にHeinのラベルが付けられたAPTは図7に示した補助マトリックスを使用する。”効率”と”効率Hein”は、内部丸めもルックアップテーブルもない前述の逆実行手段の基本単位を使用するが、例外的に補助マトリックス内の"1"と"R"はルックアップテーブルを使って処理される。もう一つのAPTは、ラダーフィルタ基本単位を使用する。”略効率”APTは平衡に近く良好なロッシー性能につながる。”略効率”APTは、行列式が1.04である(log210.4=0.06ビットの冗長度)。

0178

一実施例では、有限状態マシンFSM)エントロピーコーダ及び自明な文脈モデルが、図3に示すような様々な変換によってロスレスの符号化及び復号化を行う。FSMコーダの一例が米国特許第5,272,478号、同第5,363,099号及び同第5,475,388号に示されており、これら各米国特許は引用により本明細書に組み込まれる。

0179

図24は、1D8点効率可逆APTの場合の係数のサイズの増加(ビット数)を示す。この変換では、例えば、入力が8ビットのときに、合計64ビットの入力は18ビット分増加し、結果として82ビットの出力となる。2D8×8変換の場合の増加は、1D結果を水平方向と垂直方向に適用することにより求めることができる。

0180

図25は、1D8点”略効率”可逆APTの場合の係数のサイズの増加を示す。この変換では例えば、入力が8ビットのときに、合計64ビットの入力は21ビット分増加し、結果として85ビットの出力となる(すべてのビットの増加を合計した場合)。また、例えば、水平係数2と垂直係数3について1D結果が水平方向と垂直方向に適用される場合、さらに10ビット(2+8=10)増加する。良好な圧縮結果が得られるのは冗長な最下位ビットがないからである;すなわち、増加分は大部分が圧縮しやすい上位のビットである。

0181

APTは、可逆であるためには、浮動小数点DCTと違う係数を出力しなければならので、多少のミスマッチは避けられない。しかし、可逆APTは量子化しなければロスレスである。このロスレス性は、可逆APTの逆変換に系統誤差がないことを見込んでいる。(?The lossless feature allows for no systemicerror is the inverse transform is the inverse reversible APT.)アプリケーションのため必要な場合には、可逆APT係数を元の画素に逆変換した後、精密なDCT係数が必要とされるなら浮動小数点DCTによって、順変換してもよい。

0182

図26乃至図28は、様々な8×8APTのための最小量子化マトリックスを示す。最小量子化マトリックスは、それを適用しても真のDCT係数と±1しか違わない可逆APT係数が得られる程度以上の量子化を提供する。最小量子化値が小さいほど、変換のミスマッチが少なくなる。DC量子化特性値(quantizer)は左上コーナーに示され、AC量子化特性値は標準的なDCT順(ジグザグ順でない)に配列されている。”8×8”効率可逆APTとラダーフィルタAPTは共に、DC係数とそれに近い係数のために比較的大きな最小量子化特性値を持つ。したがって、これら変換は、低圧縮率/高品質のときにDCTを良く近似するにすぎない。”略効率”APTは一般にもっと小さな最小値を持ち、またDCとその近傍については非常に小さな最小値を持つ。このAPTは典型的なJPEG圧縮率のときにDCTを良く近似する。

0183

”略効率”APTは、”C”APTパラメータを用いて生成された係数において最大のミスマッチ(最高の最小量子化特性値)を持つ。ルックアップテーブル・ベースの”C”2点回転は、もっとミスマッチを減少させるであろう。

0184

いくつかの変換のための最小量子化マトリックスの構造を、APTスケールファクタ・マトリックスの構造によって説明する。ラダーフィルタ手段は例外であり、そのスケールファクタ・マトリックス中の値はすべて1である。図29図30は、8×8効率可逆APTと”略効率”APTのためのスケールファクタを示す。(1を超える)大きなスケールファクタは大きな最小量子化値をもたらす。

0185

<ロッシー・コーディング>可逆APTを用いるロッシー・コーディングは、まず可逆APTを用いてロスレス符号化を行う。その復号化はロッシーであり、JPEG復号化器のような従来のDCTベース伸長器を使用してよい。

0186

可逆APT係数は、JPEGなどのロッシー圧縮システムで普通のAPT係数と同様な方法で使用し得る。JPEG量子化マトリックスが選ばれる。各量子化特性値が対応したAPTスケールファクタによって除算されることにより、新たな量子化特性値・スケールファクタ結合値が得られる。APTと量子化特性値・スケールファクタ結合値は、JPEGにおけるDCTと量子化の代わりとして用いられる。どのような量子化マトリックスを用いてもよい。ただし、スケールファクタが量子化特性値より大きいと、ミスマッチが生じる。

0187

他の実施例では、量子化の除算/乗算は、所要ビットを選択するシフト操作で置き換えられる。これは計算コストを減らし、また、多くのビットを選択するほど高い品質を得ることができ、全ビットが選択された時にロスレスとなる、埋め込みもしくは多重使用システムを可能にする。量子化特性値は、対応したスケールファクタで除算された時に2のベキ乗(又はほぼ2のベキ乗)となるような値に選ばれる。

0188

JPEGには連続近似と呼ばれるプログレッシブ・モードがある。(このモードは、あまりよく知られておらず、JPEGのベースラインシーケンシャル・モードほどは利用されていない。) 特定のJPEG量子化に帰着する桁揃え(alignment)スキームを選ぶことができる。これを使用することにより、スペクトル選択を用いなくてもベースライン・シーケンシャル・データに非常に近いものにし得る、連続近似の最初のステージのための符号化データを生成することができる。連続近似は、残存データビットプレーン別に埋め込み法で符号化されることを許すプログレッシブJPEGもスペクトル選択を有する。スペクトル選択は、指定された係数のビットプレーンだけが符号化されることを許す。既に十分に説明した係数に対して、あるビットプレーンにおいてどの係数がビットを有するのか指定するためにスペクトル選択を用いることができる。最初のステージに対し大きな量子化値が用いられると、係数の全て(又は殆ど)はビットプレーン符号化されることになろう。

0189

JPEGのプログレッシブモードを使用したくないならば、様々な忠実度のシーケンシャル・ロスレスJPEGコードストリームを生成するため変換符号化(transcoding)を用いることができる。必ずしもJPEG互換でなくてよいが、何らかの方法でAPT係数をロスレス符号化することができる。ストリームを生成するため、ロスレス復号化が実行され、所要の量子化が除算又はシフト操作によって行われる。量子化された係数を、次に、JPEGコンパチブルの方法で符号化することができる。変換符号化中にDCTが必要とされないので、可逆APTを利用しないロスレス・コーディング方法に比べ、計算量が節減される。

0190

図31は、”略効率”8×8可逆APTを利用する場合の各APT係数の右シフトすべきビットの例を示す。これは量子化/スケールファクタ2n に対応する(ただし、nは右シフトすべきビット数である)。図32図31のシフトを実現する等価なJPEG量子化マトリックスである。図32は、JPEGで一般的に使用されている精神物理学的に重みづけされた輝度量子化テーブルと似ている。

0191

図33図34は、”略効率”8×8可逆APTを使用する場合に均一量子化に近づけるためシフトすべきビットと対応した量子化特性値を示す。均一量子化は、平均二乗誤差(MSE)距離による最良のレート/歪みを与える。

0192

実装上の問題点>可逆APTは、各ステップでスケーリングと丸めが行われるため、普通のAPTに比べ計算コストが高い。この弱点を一部補うため、可逆APTのためのレジスタ幅が減らされる。レジスタ幅が小さいことと計算に使用されるパラメータが簡単であることは、実装を容易にする。ソフトウェアの場合、乗除算演算をルックアップテーブルで置き換えることができる。ハードウェアの場合、専用の低コストのN乗算回路及び1/N除算回路を用いることができる。

0193

例えば、後記しかつ図17に示す2つのルックアップテーブルによる”B”2点回転の一部の実装を考える。ハードウェアの場合、この2つのルックアップテーブルを専用ロジックによって置き換えてもよい。

0194

0195

図17において、LUT1101,1102は以下のように動作する:

0196

0197

これは次の結果を生じる:
x=d1+d2 (r1+r2<13のとき)
x=d1+d2+1 (r1+r2≧13のとき) 。

0198

統合されたロッシー・ロスレス圧縮のための可逆変換は、最も一般的な符号化画像のための変換である離散コサイン変換(DCT)を包含するように拡張される。可逆のAllenのパラメタライズド変換(APT)は、それぞれが可逆的に実行される”整数回転”の縦続としてDCTを実行する。可逆APT変換のエントロピーは、可逆ウェーブレット係数のエントロピーと同様であることが分かっている。浮動小数点DCTに対し”略平衡”可逆APTのミスマッチは十分に低いため、従来のJPEG復号化器をロッシー伸長のために使用できる。

0199

以上の説明を読めば当業者には本発明の多くの変形及び修正が明白となるであろうから、説明のために図示、説明された特定の実施例は限定することを意図したものでは決してないものと理解されるべきである。

発明の効果

0200

以上の説明から明らかなように、本発明によれば、DCTベースの圧縮をロスレスにもロッシーにもできる新規な可逆変換と、それを用いた圧縮器/伸長器並びに圧縮/伸長システムを実現できる等々、画像データ等の圧縮/伸長に関し多大な効果を得られるものである。

図面の簡単な説明

0201

図1ロスレス・ロッシーDCTベース圧縮/伸長システムの一実施例のブロック図である。
図2本発明の圧縮器の一実施例のブロック図である。
図3本発明の圧縮器の他の実施例のブロック図である。
図4ビデオオーサリングシステムの一実施例のブロック図である。
図51次元(1D)8点パラメタライズド順変換の一実施例のブロック図を示す。
図6同じスケールファクタを有する、パラメタライズド変換における中間値を示す。
図7図5の補助マトリックスのHein形を示す。
図8本発明による8点Hadmard変換の一実施例のブロック図である。
図9本発明による8点Haar変換の一実施例のブロック図である。
図10本発明による4点サイン変換の一実施例のブロック図である。
図11本発明による4点Slant(傾斜)変換の一実施例のブロック図である。
図122点回転の順ラダーフィルタの一実施例を示す。
図132点回転の逆ラダーフィルタの一実施例を示す。
図1445゜回転のためのマッピングの一部を示す。
図1545゜回転のためのエキストラ("+")と衝突("o")を示す。
図162,1略平衡変換における衝突とエキストラのプロットである。
図17"B"2点回転の一部であるルックアップテーブルの一実施例を示す。
図18本発明による回転の一実施例のブロック図である。
図19APTパラメータを示す。
図205゜回転のためのマッピング例を示す。
図21略平衡変換の例を示す。
図222,1略平衡変換のためのルックアップテーブルを示す。
図238×8可逆APTを生成するための基本単位を示す。
図248点効率可逆APTの係数サイズ増加を示す。
図258点”略効率”可逆APTの係数サイズ増加を示す。
図268×8効率可逆APTのための最小量子化マトリックスを示す。
図27ラダーフィルタを使用する8×8効率可逆APTのための最小量子化マトリックスを示す。
図288×8”略効率”可逆APTのための最小量子化マトリックスを示す。
図298×8効率可逆APTのためのスケールファクタを示す。
図308×8”略効率”可逆APTのためのスケールファクタを示す。
図31”精神視覚”シフトベース量子化のため右シフトするビットを示す。
図32”精神視覚”シフトのための量子化マトリックスを示す。
図33”正規化”シフトベース量子化のため右シフトするビットを示す。
図34”正規化”シフトの量子化マトリックスを示す。
符号化の説明
101 可逆DCTを用いる圧縮器102 可逆IDCTを用いる伸長器103 任意のIDCTを用いる伸長器器104通信路又は記憶装置121 色空間/サブサンプリングブロック122 可逆DCT123ジグザグ順序付けブロック124ランレングスブロック125ハフマンコーダ126シグナリングブロック127量子化ブロック133文脈モデル134確率予測マシン135ビットストリームジェネレータ201カメラ202ロスレス圧縮器203抽出ブロック204モーションJPEG伸長器205 ロスレス伸長器206画質向上ブロック207MPEG圧縮器301〜309 回転310,311乗算312〜315 回転320 4点APT330 補助マトリックス340 45゜初期回転401〜406 回転501〜512 回転520〜526 回転531〜534 回転540〜543 回転602,606,607乗算器603,605,608 丸めブロック604,609加算器703,707,709 乗算器704,707,709 丸めブロック705,708,711減算器1101,1102 ルックアップテーブル(LUT)1201,1211,1212 加算器1202 減算器1203,1204除算器1205パリティ訂正ブロック1206,1207 乗算器1208 ルックアップテーブル(LUT)1209,1210 乗算器

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ