JPH10322219A - 圧縮器、圧縮／伸長システム、ルックアップテーブル作成方法、及び、記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 ロスレス、ロッシーいずれにもできる可逆Ｄ
ＣＴと、それを用いた圧縮／伸長システムを実現する。 【解決手段】 入力データ１００は本発明の可逆ＤＣＴ
を用いる圧縮器１０１に入力される。圧縮器１０１の出
力は、本発明の可逆ＩＤＣを用いる伸長器１０２でも在
来のＪＰＥＧ伸長器などの任意のＩＤＣを用いる伸長器
１０３でも処理できる。伸長器１０２を使用すればロス
レスの圧縮／伸長となり、伸長器１０３を使用すればロ
ッシーの圧縮／伸長となる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、圧縮及び伸長シス
テムの分野に係り、特に、可逆ロスレス（損失のない）
離散コサイン変換（ＤＣＴ）ベースの圧縮に関する。

【０００２】

【従来の技術】離散コサイン変換（ＤＣＴ）は、ロッシ
ー（損失のある）画像圧縮に一般的に使われる無理変換
である。ＤＣＴは一般にロッシー画像圧縮で使用され
る。ＤＣＴは、ＪＰＥＧ標準、ＭＰＥＧ標準及び米国の
次世代ＨＤＴＶの多くのモードに用いられる。これら各
種標準に関する解説については、ＩＳＯ標準文書ISO／I
EC10918(JPEG)，11172(MPEG1)，13818(MPEG2)、及び、
Ｗilliam Ｂ．Ｐennebakerand Ｊoan Ｌ．Ｍitchel
l，”JPEG Ｓtill Ｉmage Ｄata ＣompressionＳtandar
d,”１９９３を参照されたい。ＤＣＴの基底ベクトルは
無理値を持つ。理論上、整数入力の結果として無理変換
係数が得られる。したがって、そのような変換を厳密に
行うには無限の精度が要求される。変換係数は、圧縮に
使うためには、有限の表現へ丸められねばならない。

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

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

【０００５】本明細書においてAllenのパラメタライズ
ド（パラメータがつけられた）変換（ＡＰＴ）と呼ぶパ
ラメタライズド変換は、ＤＣＴ又はＤＣＴに任意的に近
い無理変換を実施できる高速変換の仲間である。ＡＰＴ
は一般化Chen変換（ＧＣＴ）とも呼ばれる。ＡＰＴの詳
細については、Ｊ．Ａllen,”Ｇeneralized ＣhenＴran
sform：Ａ Ｆast Ｔransform for Ｉmage Ｃompressio
n,”Ｊournal ofＥlectronic Ｉmaging，vol.3(4)，Ｏc
tober １９９４，pgs.３４１−３４７、Ｊ.Ａllen,”Ａ
n Ａpproach to Ｆast Ｔransform Ｃoding in Ｓoftwa
re,”Ｓignal Ｐrocessing Ｉmage Ｃommunication，Vo
l.8，pp.３−１，１９９６、及び、米国特許第5,129,01
5号を参照されたい。

【０００６】

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

【０００７】

【課題を解決するための手段】以下に列挙した構成の圧
縮器、圧縮／伸長システム、方法及び記録媒体などが本
発明に含まれる。

【０００８】（１）可逆離散コサイン変換（ＤＣＴ）を
有する圧縮器。 （２）（１）の圧縮器と伸長器とを有する圧縮／伸長シ
ステム。 （３）伸長器が可逆逆ＤＣＴを有する伸長器である、
（２）の圧縮／伸長システム。 （４）伸長器が逆ＤＣＴを有する従来の伸長器からなる
（２）の圧縮／伸長システム。 （５）ＤＣＴが複数の２点回転からなる（１）の圧縮
器。 （６）複数の２点回転が変換からなる（５）の圧縮器。 （７）変換のそれぞれが平衡スケールファクタを持つ
（６）の伸長器。 （８）各変換の両方の出力のスケールファクタが等しい
（７）の圧縮器。 （９）ある変換の２つの出力のスケールファクタの積が
１である（７）の圧縮器。 （１０）ある変換の出力の両方のスケールファクタが１
未満である（７）の圧縮器。 （１１）複数の２点回転のそれぞれが可逆である（５）
の圧縮器。 （１２）複数の２点回転が内部丸めをしない（１１）の
圧縮器。 （１３）２点回転の少なくとも１つがＳ変換からなる
（５）の圧縮器。 （１４）２点回転の少なくとも１つが不平衡5,1変換か
らなる（５）の圧縮器。 （１５）２点回転の少なくとも１つが平衡5,1変換から
なる（５）の圧縮器。 （１６）２点回転の少なくとも１つが6,1変換からなる
（５）の圧縮器。 （１７）２点回転の少なくとも１つが12,5変換からなる
（５）の圧縮器。 （１８）２点回転の少なくとも１つが3,2変換からなる
（５）の圧縮器。 （１９）２点回転の少なくとも１つが4,3変換からなる
（５）の圧縮器。 （２０）２点回転の少なくとも１つがラダーフィルタか
らなる（５）の圧縮器。 （２１）ラダーフィルタ内で実行される各乗算の結果が
整数値に丸められる（２０）の圧縮器。 （２２）２点回転の少なくとも１つがその入力の関数で
ある丸めオフセットを持つ（５）の圧縮器。 （２３）２点回転の少なくとも１つがその入力の和と差
の、ある除数をモジュロとした剰余の関数である丸めオ
フセットを持つ（５）の圧縮器。

【０００９】（２４）第１の複数の回転；該第１の複数
の回転の出力の第１の組と接続され、かつ、Ｂの回転を
含む第２の複数の回転を有する４点パラメタライズド変
換；及び該第１の複数の回転の出力の第２の組と接続さ
れ、Ａの回転とＣの回転を含む補助マトリックスからな
り；該第１の複数の回転、該４点パラメタライズド変換
及び該補助マトリックスは可逆ブロックベース変換とし
て働くブロックベース変換圧縮器。

【００１０】（２５）Ｂの回転が12,5変換からなる（２
４）の圧縮器。 （２６）第１の複数の回転が２点回転からなる（２４）
の圧縮器。 （２７）補助マトリックスが、該第１の複数の回転の第
１の２つの出力と接続された２つの入力を有する第１の
２点回転；該第１の２点回転の各出力と接続された乗算
器のペア；該乗算器のペアの出力と該第１の複数の回転
の第２の出力を受け取るように接続された２点回転の第
１のペア、及び該２点回転の第１のペアの出力を受け取
るように接続された前記Ｃの回転及び前記Ａの回転から
なる（２４）の圧縮器。

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

【００１２】（３１）入力値と変換出力値のペアを交換
するステップをさらに含む（３０）の方法。 （３２）入力値と変換出力値のトリプレットを回転させ
るステップをさらに含む（３１）の方法。

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

【００１４】（３５）可逆ブロックベース変換と、該可
逆ブロックベース変換の出力から得られるデータを符号
化するため該可逆ブロックベース変換に接続されたコー
ダを具備する圧縮器。

【００１５】（３６）変換がＤＦＴ変換からなる（３
５）の圧縮器。 （３７）変換がコサイン変換からなる（３５）の圧縮
器。 （３８）変換がサイン変換からなる（３５）の圧縮器。 （３９）変換がHadamard変換からなる（３５）の圧縮
器。 （４０）変換がHaar変換からなる（３５）の圧縮器。 （４１）変換がSlant変換からなる（３５）の圧縮器。 （４２）変換がKarhunen-Loeve変換からなる（３５）の
圧縮器。 （４３）変換が高速ＫＬ変換からなる（３５）の圧縮
器。 （４４）変換がシヌソイド変換からなる（３５）の圧縮
器。 （４５）変換がＳＶＤ変換からなる（３５）の圧縮器。 （４６）変換が重複又は直交変換からなる（３５）の圧
縮器。

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

【００１７】

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

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

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

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

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

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

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

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

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

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

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

【００２８】＜システムの概要＞本発明の可逆ＤＣＴ
は、入力された元のデータを正確に獲得するための可逆
の逆ＤＣＴを含むロスレスシステムにも、従来の（可逆
でない）逆ＤＣＴを含むロッシーシステムにも使用し得
る。従来のＤＣＴも可逆ＤＣＴの出力を扱うことができ
る。可逆ＤＣＴの真のＤＣＴとのミスマッチは十分に低
く、普通のＤＣＴと同じ結果を正確に得られるからであ
る。すなわち、従来のＤＣＴ復号化器を有するＭＰＥＧ
又はＪＰＥＧ復号化器を、本発明の可逆ＤＣＴと一緒に
用いることができる。

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

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

【００３１】ロスレス圧縮の場合には、原データを正確
に再構成するため、量子化されない係数に対し可逆の逆
ＤＣＴ（ＩＤＣＴ）を有する伸長器１０２が使用され
る。ロッシー圧縮の場合には、変換係数を量子化してか
ら、任意の逆ＤＣＴ（ＩＤＣＴ）を使用する伸長器１０
３によって伸長してよい。前述のように、このロッシー
伸長器は、ＪＰＥＧ又はＭＰＥＧ準拠の復号化器のよう
な従来システムで構わない。

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

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

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

【００３５】色空間／サブサンプリングブロック１２１
の出力は可逆ＤＣＴ１２２に接続される。可逆ＤＣＴ１
２２より出力される変換値はジグザク順序付けブロック
１２３の入力へ接続され、同ブロック１２３は周知のジ
グザグ順序付けを行う。なお、このジグザグ順序付けブ
ロック１２３もオプショナルである。ジグザグ順序付け
ブロック１２３の出力はランレングスブロック１２４に
接続され、同ブロックは０のランレングスを検出する。
ランレングスブロック１２４の出力はハフマン（Huffma
n）コーダ１２５の入力に接続され、ハフマン符号化が
行われる。ハフマン符号化ブロック（ハフマンコーダ）
１２４の出力はシグナリング(signaling)ブロック１２
６の入力に接続され、同ブロックは復号化器が符号化デ
ータを効率的に復号化できるようにするため、使用され
た量子化又は符号化オプションのタイプを復号化器に通
知するための信号を発生する。

【００３６】希望するならば、スケールファクタを用い
る量子化１２７を、可逆ＤＣＴブロック１２２の後又は
ジグザグ順序付けブロック１２３の前に適用してもよ
い。このようなスケールファクタを用いる量子化につい
ては、より詳しく後述する。

【００３７】図３は、本発明の圧縮器の他の実施例のブ
ロック図である。図３において、色空間／サブサンプリ
ングブロック１２１は可逆ＤＣＴ１２２に接続される。
可逆ＤＣＴ１２２の出力はオプショナルな、スケールフ
ァクタを用いる量子化ブロック１２７に接続される。ス
ケールファクタを用いる量子化ブロック１２７の出力は
文脈モデル１３３の入力に接続される。文脈モデル１３
３はデータに対する文脈を発生する。この文脈は確率予
測マシン（ＰＥＭ）１３４へ送られる。ＰＥＭ１３４
は、受け取った文脈に基づいて、データの確率予測値を
発生する。これらの確率予測値はビットストリーム・ジ
ェネレータ（ＢＧ）１３５へ出力され、同ジェネレータ
は文脈モデル１３３からの文脈とＰＥＭ１３４からの確
率予測値に基づいて、出力ビットストリームを生成す
る。ビットストリーム・ジェネレータ１３５の出力はシ
グナリングブロック１２６に接続される。

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

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

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

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

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

【００４３】任意の画質向上処理の後で、ＭＰＥＧ圧縮
器２０７が動き補償を含む完全なＭＰＥＧ圧縮を行って
最終的な圧縮データを生成する。このＭＰＥＧ圧縮器２
０７は当該技術分野では周知である。

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

【００４５】本発明は、任意のブロックベース変換又は
２点回転に分解可能な任意の非重複変換へ拡張し得る。
例えば、本発明はＤＦＴ／一元ＤＦＴ、コサイン、サイ
ン、Ｈadamard、Ｓlant、Ｋarhunen-Ｌoeve、高速Ｋ
Ｃ、シヌソイド変換、ＳＶＤ変換、重複直交変換（ＬＯ
Ｔ）等々の変換と共に使用し得る。Ｊain, Ａnil
Ｋ.,”Ｆundamentals of Ｄigital Ｐrocessing,”Ｐre
ntice-Ｈall,Ｉnc.１９８９,pgs.132-138 を参照された
い。これらの例と後述の例が与えられれば、他の変換の
実現は当業者には明白であろう。

【００４６】＜ＡＰＴによる高速ＤＣＴ分解＞Ａllenの
パラメタライズド変換（ＡＰＴ）は、公式には一般化Ch
en変換（ＧＣＴ）と呼ばれるが、ＤＣＴと、他の関連変
換のファミリーを”整数回転”の縦続（cascade)に変形
する。一実施例では、各回転は、その行列式の絶対値が
１の変換からなる。本発明は、ＤＣＴを多数の可逆成分
に伸長することによって可逆ＤＣＴを得る。このＤＣＴ
は、個々のパーツが可逆であるから可逆である。

【００４７】図５は、１Ｄ８点順ＡＰＴのブロック図を
示す。ＡＰＴ変換の大部分は、回転角度の逆正接によっ
てラベル付けされた２点回転からなる。（これらの回転
は、”時計回り”で行列式が−１であるものとして示さ
れている。）図５において、８点変換は、４つの４５゜
(arctan=1)初期回転３４０、４点ＡＰＴ３２０、”補助
マトリックス”３３０に分けることができる。補助マト
リックス３３０は、２つの乗算と複数の２点回転を含
む。

【００４８】このように、順ＡＰＴ変換を構成する３組
の回転がある。まず、１組の２点（２×２）回転３０１
〜３０４は入力ステージとなる。回転３０１〜３０４の
それぞれの出力は、２点回転３０５〜３０８からなる４
点ＡＰＴブロック３２０の入力に接続され、また、２点
回転３０９，３１２〜３１５と乗算器３１０，３１１か
らなる補助マトリックス３３０に接続される。

【００４９】詳しくは、回転３０１は２つの入力データ
サンプルに対応する入力０，７を受け取り、回転３０５
の入力に対する出力と、回転３１２の入力に対する出力
を生成する。回転３０２は入力データサンプル１，６を
受け取るように接続され、２つの出力、すなわち回転３
０６の入力に対する出力と、回転３０９の入力に対する
出力とを与える。回転３０３は入力データサンプル２，
５を受け取るように接続されて２つの出力を生成し、そ
の一方の出力は回転３０６の他方の入力に接続され、他
方の出力は回転３０９の他方の入力に接続される。回転
３０４は入力データサンプル３，４を受け取るように接
続されて２つの出力を生成し、その一方の出力は回転３
０５の他方の入力に接続され、他方の出力は回転３１３
の他方の入力に接続される。

【００５０】回転３０５は２つの出力を生成するが、そ
の一方の出力は回転３０７の入力に接続され、他方の出
力は回転３０８の入力に接続される。回転３０６は２つ
の出力を生成し、その一方の出力は回転３０７の他方の
入力に接続され、他方の出力は回転３０８の他方の入力
に接続される。これらの入力に応答して、回転３０７は
０出力と４出力を生成し、回転３０８は２出力と６出力
を生成する。

【００５１】補助マトリックス３３０に関しては、回転
３０９は、Ｒ乗算ブロック３１０，３１１に接続される
２つの出力を生成する。Ｒ乗算ブロック３１０の出力は
回転３１２の他方の入力に接続され、Ｒ乗算ブロック３
１１の出力は回転３１３の他方の入力に接続される。回
転３１２は、その入力に応答して、回転３１４，３１５
に接続される２つの出力を生成する。同様に、回転３１
３は、その入力に応答して、回転３１４，３１５の入力
に接続される２つの出力を生成する。これらの出力に応
答して、回転３１４，３１５は１出力及び７出力と３出
力及び５出力をそれぞれ生成する。Ａ，Ｂ，Ｃ回転につ
いて以下に詳述する。一実施例では、回転３０１〜３０
４のそれぞれはＳ変換かもしれない。しかし、その場
合、ミスマッチに苦しむかもしれない。

【００５２】図５に示す補助マトリックスはＣhen形式
のものである。Ｊ.Ａllen in，”Ｇeneralized Ｃhen
Ｔransform for Ｉmage Ｃompression,” Ｊounal ofＥ
lectronic Ｉmaging，Vol.3(4)，Ｏctober １９９４，p
gs．３４１−３４７に述べられているＨeinとＡllen，
Ｊ．Ａllen による補助マトリックスの代案を図７に示
す。図７において、当該補助マトリックスは（ある角度
の）６つの回転からなる。回転角度が４５゜（すなわち
arctan=1）の１対の回転がそれぞれ２つの入力を受け取
って２つの出力を生成するように接続される。回転４０
１，４０２のそれぞれの出力の一方は回転４０３の入力
に接続され、回転４０１，４０２の他方の２つの出力は
回転４０４の入力に接続される。これらの入力に応答し
て、回転４０３，４０４は２つの出力を生成する。回転
４０３，４０４はＢ回転からなる。回転４０３，４０４
のそれぞれの出力の一方は回転４０５の入力に接続さ
れ、回転４０３，４０４のそれぞの他方の出力は回転４
０６の入力に接続される。回転４０５，４０６はそれぞ
れＡ回転、Ｂ回転からなる。回転４０５，４０６はそれ
ぞれ２つの出力１，７と５，３を生成する。

【００５３】一実施例では、回転は２点（２×２）回転
である。各回転は２点変換もしくはフィルタからなるか
もしれない。

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

【００５５】

【数１】

【００５６】

【数２】

【００５７】

【数３】

【００５８】分離可能な２次元（２Ｄ）６４点ＤＣＴ
（ＡＰＴ）は、８つの１Ｄ８点ＤＣＴ（ＡＰＴ）、１つ
の転置、及び、別の８つの１Ｄ，８点ＤＣＴ（ＡＰＴ）
によって実現できる。

【００５９】図６は、同じスケールファクタを有するＡ
ＰＴの中間値を示す。図６において、各網掛け線は同じ
スケールファクタを持つ入力を示す。同一のスケールフ
ァクタを用いることは２点変換の除数を拘束する。例え
ば、殆どの１の回転（３０９以外の全ての回転）は両方
の出力に対し同じスケールファクタを持つ必要がないの
で、Ｓ変換のような不平衡変換を用いてよい。これに対
して、１の回転とＲによる乗算（３０９）の縦続は、出
力に関し入力と同じスケールファクタを持たなければな
らない。

【００６０】図６において、回転３０７に対する２つの
入力は同一のスケールファクタを有する。回転３０８に
対する２つの入力は同一のスケールファクタを有する。
回転３１４に対する２つの入力は同一のスケールファク
タを有し、回転３１５に対する２つの入力は同一のスケ
ールファクタを有する。回転３０５と回転３０６の入力
は同じスケールファクタを有する。このことは、回転３
０５の場合に、回転３０１，３０４それぞれからの上側
の枝を拘束することになろう。回転３１２，３１３に関
しては、それらの入力が同じスケールファクタを有する
だけではなく、回転３０１，３０４それぞれからの下側
の枝が全て同一のスケールファクタを有する。回転３０
１，３０４から出る下側の枝のスケールファクタは回転
３０２，３０３から出る下側の枝のスケールファクタと
同じであるから、補助マトリックスに対する全ての入力
のスケールファクタが同一である。２つの出力のスケー
ルファクタの積が膨張量である。したがって、効率をよ
くするには、両方のスケールファクタの積を理想的には
１にして膨張を防がなければならない。一実施例では、
可逆にするため、両方のスケールファクタが１である。
他の実施例では、スケールファクタは僅かに異なっても
よい。例えば、両方のスケールファクタを０．９９にし
てよい。

【００６１】図１９は、３つの異なった実施例のための
ＡＰＴパラメータの値を示す。最初のパラメータの組は
ＤＣＴとなる無理数である。圧縮のためのＤＣＴ実行手
段（ＡＰＴその他）は、これらの無理値を使用できな
い。現実のＤＣＴ実行手段はすべて無理パラメータを近
似する（その近似値は非常に正確な高精度浮動小数点近
似値であるが）。ＡＰＴは小さな整数による有理近似値
を使うため、扱いやすい可逆実行手段となる。

【００６２】図１９は、単純さとミスマッチとの兼ね合
いを図る３組のＡＰＴパラメータを示す。ＡＰＴ１は簡
単で圧縮用に好適である。他の例であるＡＰＴ２とＡＰ
Ｔ３は、より精密な無理変換の近似である。ＡＰＴ３は
ＣＣＩＴＴ Ｒec.Ｈ．２６１（ＩＥＥＥ規格1180-199
0）精度試験を満足する。

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

【００６４】なお、これらのＡＰＴパラメータを、他の
可逆又は不可逆の変換が得られるように調整してもよ
い。

【００６５】＜可逆ＤＣＴ実行手段＞本発明において、
ＡＰＴの構成要素中の各２点回転は可逆とされる。各２
点回転を可逆にすれば、各ステップを逆にしてよいので
ＡＰＴ全体が可逆になる。効率のほかに、２つの性質、
すなわちスケールファクタが平衡していること、内部の
丸めがないことが望ましい。

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

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

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

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

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

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

【００７２】”１”：1,1-変換，S-T変換−不平衡 一実施例において、”１”ブロックは次の変換によって
実現される。ただし、ａとｂは順変換の入力であり、ｘ
とｙは順変換の出力である。

【００７３】

【数４】

【００７４】一実施例では、スケールファクタはそれぞ
れ√２と１／√２である。

【００７５】”Ａ”：5,1-変換−不平衡 次に示すものは”Ａ”回転の一実施例である。

【００７６】

【数５】

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

【００７８】”Ａ”：5,1-変換−平衡，非効率 次に示すものはＡ回転の別の実施例である。

【００７９】

【数６】

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

【００８１】”Ａ”：60,11-変換−平衡，効率 ”Ａ”回転の他の実施例は次の通りである。

【００８２】

【数７】

【００８３】この変換は平衡・効率変換である。この変
換は11，60，61を使うが、これはピタゴラスのトリプレ
ットa，b，cで、ｂ＋１＝ｃ かつ ａ²＝２ｂ＋１であ
る。しかし、結果の60／11≒5.4545 は７π／16≒5.027
3 のあまりよい近似値ではない。ここでは、平衡、効率
であることと計算の容易さのため、ＤＣＴへの近似度は
犠牲にされている。この場合、スケールファクタは共に
１である。

【００８４】”Ｂ”：12,5-変換 次に示すものは”Ｂ”回転の一実施例である。

【００８５】

【数８】

【００８６】これは平衡・効率変換である。数値5，1
2，13 は、ピタゴラスのトリプレットa，b，c で、ｂ＋
１＝ｃかつａ2＝２ｂ＋１である。これは非常に良好な
４点ＡＰＴ（ＤＣＴ）である。スケールファクタは共に
１である。

【００８７】なお、オフセットは可逆性にとって非常に
重要である。上式の順変換の両方のオフセットとして＋
６を選ぶと可逆変換になるが、他のオフセットでは可逆
変換とはならない。例えば、下式におけるようにオフセ
ットが両方とも０であると、入力ａ＝０，ｂ＝０と入力
ａ＝１，ｂ＝０に対する結果は共にｘ＝０，ｙ＝０であ
る。

【００８８】

【数９】

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

【００９０】両方のオフセットが＋５である別の例を下
に示す。この場合、入力ａ＝４，ｂ＝０と入力ａ＝４，
ｂ＝１に対する結果は共にｘ＝４，ｙ＝１である。

【００９１】

【数１０】

【００９２】殆どのオフセットのペアで、可逆変換とは
ならない。オフセット（0...12)の可能な１６９個のペ
アの中で、可逆性が得られるのは、 0,10；1,5；2,0；
3,8；4,3；5,11；6,6；7,1；8,9；9,4；10,12；11,7 の
１３個のペアだけである。

【００９３】”Ｃ”：3,2-変換−不平衡 ”Ｃ”回転の一実施例は次の通りである。

【００９４】

【数１１】

【００９５】これは効率変換である。この場合、スケー
ルファクタは√13と１／√13である。

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

【００９７】

【数１２】

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

【００９９】”Ｃ”：4,3-係数−平衡 平衡変換である、”Ｃ”回転の他の実施例は次の通りで
ある。

【０１００】

【数１３】

【０１０１】この変換は平衡・効率変換である。数値の
組３，４，５はピタゴラスのトリプレットａ，ｂ，ｃ
で、ｂ＋１＝ｃかつａ²＝２ｂ＋１である。しかし、４
／３≒1.3333は、tan 5π／16≒1.4966 に対するあま
り良い近似値ではない。スケールファクタは共に１であ
る。

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

【０１０３】

【数１４】

【０１０４】＜ＤＣＴ以外の変換＞図８は、８点Ｈadam
ard変換を示す。図８において、回転５０１〜５１２
は、tan(π／4)=1 の２点回転からなる。回転５０１
は、入力データサンプル０，７を受け取って回転５０
５，５０７への出力を生成するように接続される。回転
５０２は、入力データサンプル１，６を受け取って回転
５０６，５０８への出力を発生するように接続される。
回転５０３は入力データサンプル２，５を受け取って回
転５０６，５０８への出力を生成するように接続され、
また、回転５０４は入力データサンプル３，４を受け取
って回転５０５，５０８に対する出力を生成するように
接続される。

【０１０５】回転５０５は、その入力に応答し、回転５
０９，５１０に対する出力を生成する。回転５０６も、
その入力に応答してと回転５０９，５１０に対する出力
を生成する。回転５０９はその入力に応答して出力サン
プル０，４を生成し、また、回転５１０はその入力に応
答して出力サンプル２，６を生成する。

【０１０６】回転５０７は回転５１１，５１２に対する
出力を生成する。回転５０８も回転５１１，５１２に対
する出力を生成する。これらの入力に応答し、回転５０
５は出力サンプル１，５を生成し、回転５１２は出力サ
ンプル３，７を生成する。

【０１０７】図９は８点Ｈarr変換を示す。図９におい
て、当該Ｈarr変換は、それぞれtan(π／4)＝１の２点
回転である回転５２０〜５２６からなる。回転５２０は
入力データサンプル０，１を受け取って、出力データサ
ンプル４と回転５２４への出力を生成するように接続さ
れる。回転５２１は入力データサンプル２，３を受け取
って、回転５２４への出力と出力データサンプル５を生
成するように接続される。回転５２２は入力データサン
プル４，５を受け取って回転５２５への出力と出力デー
タサンプル６を生成するように接続される。回転５２３
は入力データサンプル６，７を受け取って回転５２５へ
の出力と出力データサンプル７を生成するように接続さ
れる。回転５２４は、その入力に応答して出力データサ
ンプル２と回転５２６への出力を生成する。回転５２５
は回転５２５への出力と出力データサンプル３を生成す
る。回転５２６は、その入力に応答してサンプル０，１
を出力する。

【０１０８】図１０は４点サイン変換の一実施例を示
す。図１０において、当該サイン変換は回転５３１〜５
３４からなる。回転５３１，５３２はtan(π／4)＝１の
２点回転からなり、回転５３３，５３４はＤの回転から
なる。なお、Ｄはtan(0.1762π)として示されている。

【０１０９】回転５３１は入力データサンプル０，３を
受け取って回転５３３，５３４への出力を生成するよう
に接続され、回転５３２は入力データサンプル２，１を
受け取って回転５３３，５３４に対する出力を生成する
ように接続される。それらの各入力に応答し、回転５３
３は出力データサンプル１，２を生成し、回転５３４は
出力サンプル３，１を出力する。

【０１１０】図１１は、４点Ｓlant（傾斜)変換の一実
施例を示す。図１１において、当該Ｓlant変換は回転５
４０〜５４３からなる。回転５４０〜５４２はtan(π／
4)＝１の２点回転からなり、回転５４３はtan(0.1024
π)の２点回転からなる。回転５４０は入力データサン
プル０，３を受け取って回転５４２，５４３への出力を
生成するように接続され、回転５４１は入力データサン
プル２，１を受け取って回転５４２，５４３への出力を
生成するように接続される。回転５４２は入力に応答し
て出力データサンプル０，２を生成し、回転５４３は入
力に応答して出力データサンプル３，１を生成する。以
上に述べた例から、当業者は他の変換も実現できるであ
ろう。

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

【０１１２】

【数１５】

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

【０１１４】図１２に、入力６１０，６１１を持つラダ
ーフィルタ手段が示されている。入力６１１は乗算器６
０２に接続され、この乗算器６０２は(cosθ-1)／sinθ
を入力６１０に掛ける。この乗算の結果はブロック６０
３で最近整数に丸められる。この丸めの結果は加算器６
０４によって入力６１１と加算される。加算器６０４の
出力は乗算器６０６に接続され、sinθと乗算される。
この結果はブロック６０５で整数に丸められる。丸めの
結果は加算器６０１によって入力６１０と加算される。
加算器６０１の出力は当該ラダーフィルタの一方の出力
６１２である。加算器６０１の出力は乗算器６０７にも
入力され、(cosθ-1)／sinθと乗算される。この乗算の
結果はブロック６０８で整数に丸められる。丸めの結果
は、加算器６０９によって、加算器６０４の出力と加算
される。加算器６０９の出力は当該ラダーフィルタの他
方の出力６１３である。

【０１１５】図１３において、２つの入力７０１，７０
２が当該ラダーフィルタに入力する。入力７０１は乗算
器７０３に入力されて(cosθ-1)／sinθと乗算される。
この乗算の結果はブロック７０４で整数に丸められる。
この丸めの結果は、減算器７０５によって入力７０２か
ら減算される。減算器７０５の出力は乗算器７０６の入
力に接続され、sinθと乗算される。この乗算の結果は
ブロック７０７で整数に丸められる。丸め結果は減算器
７０８によって入力７０１より減算される。減算器７０
８の出力は当該ラダーフィルタの一方の出力７１２であ
る。

【０１１６】減算器７０８の出力は乗算器７０９の入力
にも接続され、(cosθ-1)／sinθと乗算される。この乗
算の結果はブロック７１０で整数に丸められる。この丸
めの結果は減算器７１１によって減算器７０５の出力か
ら減算される。減算器７１１の出力は当該ラダーフィル
タの他方の出力である。

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

【０１１８】ＤＣＴ全体を２×２回転に分解しないで、
もっと大きなラダーフィルタを作成できる。例えば、下
に示すような３つのマトリックスに分解することによ
り、４点ＤＣＴをラダーフィルタとして実現できる。

【０１１９】

【数１６】

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

【０１２１】

【数１７】

【０１２２】このように、本発明は、新規な４点可逆変
換を提供するとともに、４点（４×４）回転のための効
率・可逆２×２分解を行う。

【０１２３】なお、以上の説明中の変換には２点ＤＣ
Ｔ、４点ＡＰＴ、８点非自明なマトリックスが含まれて
いたが、本発明は例えば１６×１６など他のサイズへ拡
張されてもよい。

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

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

【０１２６】丸めオフセットを固定的に選択したのでは
可逆にすることができない２点整数回転がある。例え
ば、次式を考える。これは、図１９にＡＰＴパラメータ
Ｒとして示された近似値による４５゜回転である。

【０１２７】

【数１８】

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

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

【０１３０】

【数１９】

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

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

【０１３３】図１５は、近似値1／√2≒29／41＝0.7073
を用いる４５゜回転の場合の衝突（"ｏ"）とエキストラ
（"＋"）を示す。（可能性のあるもの全部を１ページに
表示できるように、分母として、１８１に代え、より小
さな４１が使われている。分母が１８１の場合の対応図
は同様である。） 本例では、行列式は非常に１に近く
（1.0006である）、エキストラの個数は衝突の個数と等
しい。ペアを持たない衝突又はエキストラの個数は変換
の膨張を表す。

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

【０１３５】図１９に示した近似値128／181はかなり正
確である。分子の１２８は２のベキ乗で、計算に都合が
よい。行列式は1.0002（log²1.0002＝0.0003ビット）
で、これは非常に効率に近い。適切なルックアップテー
ブルによれば、平均ＲＭＳＥは0.4434であり、ピーク誤
差は1.92である。

【０１３６】＜順計算＞2×2ＤＣＴのための回転の完全
な順計算は次のようになされる。ここでは、近似値1/√
2≒128/181を用いる。まず、順変換を計算するため、入
力ａ，ｂの和と差が下式により計算される。 和(sum)＝ａ＋ｂ 差(difference)＝ａ−ｂ
。

【０１３７】次に、下式により和と差が１８１で割り算
され、剰余が保存される。（なお、実行手段によって
は、除算の高速化のため128/181≒181/256が用いられる
ことがある。） ｓｓ＝和／181 ｄｄ＝差／181 ｓ＝和 mod 181 ｄ＝差 mod 181
。

【０１３８】ルックアップテーブルは、モジュロ181値
ｓ，ｄのペアが同じパリティを持つ（ｓ，ｄが共に偶数
であるか共に奇数である）と仮定する。ｓｓとｄｄが同
じパリティを持たないとにきは、その一方のモジュロ値
のパリティが変更される。この変更は、値が0...180の
範囲内に納まるようになされる。下の擬似コードにおい
て、”＾”は排他的ＯＲを意味する。このステップは奇
数の分母の場合に必要とされ、偶数の分母の場合には必
要でない。

【０１３９】擬似コードは以下のとおりである：if（ss
が奇数かつddが偶数）又は（ssが偶数かつddが奇数） if（ｄ==180） ｓ'＝ｓ＾１ else ｄ'＝ｄ＾１ 。

【０１４０】1／2の平方根とｓ，ｄの積は、128／181
（又は181／256）又はルックアップテーブルを使って決
定できる。丸めオフセットはルックアップテーブル内に
見つかるであろう。一実施例では、丸めオフセットは−
１...１であるので、ルックアップテーブルのデータ幅
を２ビットにできる。ｓｓとｄｄで表された入力の平方
根はそれぞれ128ssと128ddであり、これらはシフトで実
行してよい。 ｘ＝sqrt(1／2)＊s'＋LUT_f[s',d']＋128＊ss ｙ＝sqrt(1／2)＊d'＋LUT_g[s',d']＋128＊dd
。

【０１４１】これは次の等式のためのものである：

【０１４２】

【数２０】

【０１４３】また、ルックアップテーブルがｓ（又は
ｄ）の平方根と丸めオフセットを返してもよい。一実施
例では、そのようなルックアップテーブルは７ビットの
データ幅を持つ。 ｘ＝LUT_sqrt1／2_f[s',d']＋128＊ss ｙ＝LUT_sqrt1／2_g[s',d']＋128＊dd
。

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

【０１４５】図１８は本発明による回転の一実施例のブ
ロック図である。図１８において、入力ａ，ｂは加算器
１２０１によって加算されて和（ｓ）が得られ、また入
力ａ，ｂは減算器１２０１に入力されて差ａ−ｂ（ｄ）
が求められる。和（ｓ）は除算器１２０３に入力され１
２８で除算される。除算器１２０３の剰余出力はパリテ
ィ訂正ブロック１２０５の入力に接続され、また、商出
力は乗算器１２０６に接続される。減算器１２０２の差
出力は除算器１２０４に入力され、除算器１２０４はそ
れを181で除算し、剰余をパリティ訂正ブロック１２０
５の他方の入力へ出力し、また商を乗算器１２０７の入
力へ出力する。パリティ訂正ブロック１２０５は前述の
パリティ訂正を行ってｓ'とｄ'を出力し、このｓ'とｄ'
はルックアップテーブル(LUT)１２０８と乗算器１２０
９，１２１０へそれぞれ接続される。

【０１４６】乗算器１２０６は除算器１２０３より出力
されたｓｓに１２８を乗算し、その結果を加算器１２１
１へ出力する。乗算器１２０７は除算器１２０４の出力
ｄｄに１２８を乗算し、その結果を加算器１２１２へ出
力する。乗算器１２０９は、ｓ'に１／２の平方根を乗
算して結果を加算器１２１１へ出力し、また、乗算器１
２１０はｄ'に１／２の平方根を乗算し結果を加算器１
２１２へ出力する。

【０１４７】ＬＵＴ１２０８は前述のｆとｇを生成し、
それらを加算器１２１１，１２１２へそれぞれ出力す
る。加算器１２１１はその入力を加算して回転のｘ出力
を発生し、他方、加算器１２１２はその入力を加算して
ｙ出力を生成する。

【０１４８】＜逆計算＞一実施例では、完全な逆計算を
するために、近似値1/√2≒128/181が用いられる。

【０１４９】まず、下式により、入力ｘ，ｙが１２８に
よって除算され、その剰余が保存される。 ss＝ｘ／128 dd＝ｙ／128 ｉ＝ｘ mod 128 ｊ＝ｙ mod 128 。

【０１５０】次に、モジュロ128値は２の平方根と乗算
され、そして丸めオフセットが減算される。（これは１
つのＬＵＴに併合可能である。） ｉとｊは０から127
までの値であるから、複雑な指標付け方法を必要とせず
に、ルックアップテーブルのエントリーの全て（又は使
用されないエキストラがあるときには殆ど）を使用でき
る。 ｓ＝sqrt(2)＊ｉ−LUT_f_inverse[i,j] ｄ＝sqrt(2)＊ｊ−LUT_g_inverse[i,j]
。

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

【０１５２】次式に従って和と差が計算される： 和＝ｓ'＋181＊ss 差＝ｄ'＋181＊dd
。

【０１５３】最後に、次式に従って、和と差が再び元の
値に変換される： ａ＝和／２＋(差+1)／２ ｂ＝和／２−差／２
。

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

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

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

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

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

【０１５９】説明のため、図１５に示した衝突とエキス
トラのパターンを考える。１４４個の衝突が１２行×８
個のパターンで存在する。１４４個のエキストラが８行
×９個と９行×８個のパターンで存在する。初めの３行
の衝突についての割り当ては以下のとおりである。その
他の衝突行も同様にして割り当てられる。

【０１６０】第１行の１２個の衝突 列3,7,13,17,21,27,31に８個のエキストラがある第１エ
キストラ行を用いる第２エキストラ行の９個のエキスト
ラ中の４個のエキストラを用いる、列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→4
0 である 第２行の１２個の衝突 第２エキストラ行の９個のエキストラ中から残りの５個
のエキストラを用いる、列0,10,28,38のエキストラを用
いる 第３エキストラ行の８個のエキストラ中の７個のエキス
トラを用いる、列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→4
0 である 第３行の１２個の衝突 第３エキストラ行の８個のエキストラ中の残りの１個の
エキストラを用いる、列３７のエキストラを用いる 第４エキストラ行の列0,4,10,14,20,24,28,34,38の９個
のエキストラを用いる 第５エキストラ行の８個のエキストラ中の２個のエキス
トラを用いる、列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→4
0 。

【０１６１】初めのマッピングが与えられれば、傾斜降
下法（ミスマッチが減少するならエキストラ／衝突割り
当てを交換）又は類似の最適化法（例えば模擬アニーリ
ングなど）によってマッピングを改善することができ
る。もう一つの最適化法が、Ｂ.Ｋerninghan，Ｌin，Ａ
n Ｅfficient Ｈeuristic Ｐrocedure forＰartitionin
g Ｇraphics，Ｂell Ｓyst．Ｔech．Ｊ.，pp.291-307,1
970 に記載されている。最適化は、衝突とエキストラだ
けを考慮して行われても、全ての入力値及び出力値を考
慮して行われてもよい。最適化は、入力及び出力のペア
を交換(swap)することによって行われても、入力及び出
力のトリプレットを回転することによって行われてもよ
い。一実施例では、二乗誤差を減少させる交換又は回転
が、それ以上の改善が不可能になるまで行われる。

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

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

【０１６４】角度ｑの回転の場合、二乗誤差を計算する
ため以下の手順を用いてよい。 XCを第１の衝突座標とする YCを第２の衝突座標とする XEを第１のエキストラ座標とする YEを第２のエキストラ座標とする SIN＝sinｑとする COS＝cosｑとする 二乗誤差＝(COS*XC-round(COS*XE))^2+(COS*YC-round(C
OS*YE))^2 。

【０１６５】前記”エキストラ[k]のより良い割り当て
を探索する”ルーチンの一実施例の擬似コードは以下の
とおりである： 最良交換のための二乗誤差の最良改善を０に初期化する エキストラ[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]と三重交換するマークを付ける。

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

【０１６７】前記”最良三重交換を探索する”ルーチン
の一実施例のための擬似コードは以下のとおりである： for 各エキストラ［ｎ］ 交換誤差＝エキストラ［ｍ］，衝突[k]の二乗誤差＋エキストラ[n],衝
突[m] の二乗誤差＋エキストラ[k],衝突[n]の二乗誤差 を計算す る 現在誤差＝現在誤差−交換誤差 を計算する if （本改善＞＝０）かつ（本改善＞＝最良改善） 最良改善＝本改善 これまでに見つかった最良交換はｎである。

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

【０１６９】＜略平衡ＤＣＴ実行手段＞ルックアップテ
ーブルをベースとした丸めは、低ミスマッチの任意の２
点回転を実現可能である。本発明は、ルックアップテー
ブル手法（又は他の手法）によって効率かつ略平衡で可
逆的に実行可能な変換を生成できる。

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

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

【０１７２】

【数２１】

【０１７３】２つの除数は５と４で、これは平衡比１.
２５を持つ。この例は１０²＝１００のテーブルサイズ
しか必要とせず、テーブルは単純な構造を持つ。

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

【０１７５】

【数２２】

【０１７６】図１６は、ａとｂが０....10の範囲内のと
きに上式より発生するｘ，ｙのペアをプロットしたもの
である。丸印と矢印は衝突のエキストラへのマッピング
を示す。

【０１７７】＜８×８変換＞前述の様々な基本要素を各
種の８×８可逆ＡＰＴに使用してよく、そのいくつかを
図２３に示す。図５に示した補助マトリックスのＣhen
分解が用いられるが、例外的にＨeinのラベルが付けら
れたＡＰＴは図７に示した補助マトリックスを使用す
る。”効率”と”効率Ｈein”は、内部丸めもルックア
ップテーブルもない前述の逆実行手段の基本単位を使用
するが、例外的に補助マトリックス内の"１"と"Ｒ"はル
ックアップテーブルを使って処理される。もう一つのＡ
ＰＴは、ラダーフィルタ基本単位を使用する。”略効
率”ＡＰＴは平衡に近く良好なロッシー性能につなが
る。”略効率”ＡＰＴは、行列式が１.０４である（log
²10.4＝0.06ビットの冗長度）。

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

【０１７９】図２４は、１Ｄ８点効率可逆ＡＰＴの場合
の係数のサイズの増加（ビット数）を示す。この変換で
は、例えば、入力が８ビットのときに、合計６４ビット
の入力は１８ビット分増加し、結果として８２ビットの
出力となる。２Ｄ8×8変換の場合の増加は、１Ｄ結果を
水平方向と垂直方向に適用することにより求めることが
できる。

【０１８０】図２５は、１Ｄ８点”略効率”可逆ＡＰＴ
の場合の係数のサイズの増加を示す。この変換では例え
ば、入力が８ビットのときに、合計６４ビットの入力は
２１ビット分増加し、結果として８５ビットの出力とな
る（すべてのビットの増加を合計した場合）。また、例
えば、水平係数２と垂直係数３について１Ｄ結果が水平
方向と垂直方向に適用される場合、さらに１０ビット
（２＋８＝１０）増加する。良好な圧縮結果が得られる
のは冗長な最下位ビットがないからである；すなわち、
増加分は大部分が圧縮しやすい上位のビットである。

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

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

【０１８３】”略効率”ＡＰＴは、”Ｃ”ＡＰＴパラメ
ータを用いて生成された係数において最大のミスマッチ
（最高の最小量子化特性値）を持つ。ルックアップテー
ブル・ベースの”Ｃ”２点回転は、もっとミスマッチを
減少させるであろう。

【０１８４】いくつかの変換のための最小量子化マトリ
ックスの構造を、ＡＰＴスケールファクタ・マトリック
スの構造によって説明する。ラダーフィルタ手段は例外
であり、そのスケールファクタ・マトリックス中の値は
すべて１である。図２９と図３０は、8×8効率可逆ＡＰ
Ｔと”略効率”ＡＰＴのためのスケールファクタを示
す。（１を超える）大きなスケールファクタは大きな最
小量子化値をもたらす。

【０１８５】＜ロッシー・コーディング＞可逆ＡＰＴを
用いるロッシー・コーディングは、まず可逆ＡＰＴを用
いてロスレス符号化を行う。その復号化はロッシーであ
り、ＪＰＥＧ復号化器のような従来のＤＣＴベース伸長
器を使用してよい。

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

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

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

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

【０１９０】図３１は、”略効率”8×8可逆ＡＰＴを利
用する場合の各ＡＰＴ係数の右シフトすべきビットの例
を示す。これは量子化／スケールファクタ２ⁿ に対応す
る（ただし、ｎは右シフトすべきビット数である）。図
３２は図３１のシフトを実現する等価なＪＰＥＧ量子化
マトリックスである。図３２は、ＪＰＥＧで一般的に使
用されている精神物理学的に重みづけされた輝度量子化
テーブルと似ている。

【０１９１】図３３と図３４は、”略効率”8×8可逆Ａ
ＰＴを使用する場合に均一量子化に近づけるためシフト
すべきビットと対応した量子化特性値を示す。均一量子
化は、平均二乗誤差（ＭＳＥ）距離による最良のレート
／歪みを与える。

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

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

【０１９４】

【数２３】

【０１９５】図１７において、ＬＵＴ１１０１，１１０
２は以下のように動作する：

【０１９６】

【数２４】

【０１９７】これは次の結果を生じる： ｘ＝ｄ１＋ｄ２ （ｒ１＋ｒ２＜１３のとき） ｘ＝ｄ１＋ｄ２＋１ （ｒ１＋ｒ２≧１３のとき）
。

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

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

【０２００】

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

【図面の簡単な説明】

【図１】ロスレス・ロッシーＤＣＴベース圧縮／伸長シ
ステムの一実施例のブロック図である。

【図２】本発明の圧縮器の一実施例のブロック図であ
る。

【図３】本発明の圧縮器の他の実施例のブロック図であ
る。

【図４】ビデオオーサリングシステムの一実施例のブロ
ック図である。

【図５】１次元（１Ｄ）８点パラメタライズド順変換の
一実施例のブロック図を示す。

【図６】同じスケールファクタを有する、パラメタライ
ズド変換における中間値を示す。

【図７】図５の補助マトリックスのＨein形を示す。

【図８】本発明による８点Ｈadmard変換の一実施例のブ
ロック図である。

【図９】本発明による８点Ｈaar変換の一実施例のブロ
ック図である。

【図１０】本発明による４点サイン変換の一実施例のブ
ロック図である。

【図１１】本発明による４点Ｓlant（傾斜）変換の一実
施例のブロック図である。

【図１２】２点回転の順ラダーフィルタの一実施例を示
す。

【図１３】２点回転の逆ラダーフィルタの一実施例を示
す。

【図１４】４５゜回転のためのマッピングの一部を示
す。

【図１５】４５゜回転のためのエキストラ("+")と衝
突("o")を示す。

【図１６】２，１略平衡変換における衝突とエキストラ
のプロットである。

【図１７】"Ｂ"２点回転の一部であるルックアップテー
ブルの一実施例を示す。

【図１８】本発明による回転の一実施例のブロック図で
ある。

【図１９】ＡＰＴパラメータを示す。

【図２０】５゜回転のためのマッピング例を示す。

【図２１】略平衡変換の例を示す。

【図２２】２，１略平衡変換のためのルックアップテー
ブルを示す。

【図２３】８×８可逆ＡＰＴを生成するための基本単位
を示す。

【図２４】８点効率可逆ＡＰＴの係数サイズ増加を示
す。

【図２５】８点”略効率”可逆ＡＰＴの係数サイズ増加
を示す。

【図２６】８×８効率可逆ＡＰＴのための最小量子化マ
トリックスを示す。

【図２７】ラダーフィルタを使用する８×８効率可逆Ａ
ＰＴのための最小量子化マトリックスを示す。

【図２８】８×８”略効率”可逆ＡＰＴのための最小量
子化マトリックスを示す。

【図２９】８×８効率可逆ＡＰＴのためのスケールファ
クタを示す。

【図３０】８×８”略効率”可逆ＡＰＴのためのスケー
ルファクタを示す。

【図３１】”精神視覚”シフトベース量子化のため右シ
フトするビットを示す。

【図３２】”精神視覚”シフトのための量子化マトリッ
クスを示す。

【図３３】”正規化”シフトベース量子化のため右シフ
トするビットを示す。

【図３４】”正規化”シフトの量子化マトリックスを示
す。

【符号化の説明】

１０１ 可逆ＤＣＴを用いる圧縮器 １０２ 可逆ＩＤＣＴを用いる伸長器 １０３ 任意のＩＤＣＴを用いる伸長器器 １０４ 通信路又は記憶装置 １２１ 色空間／サブサンプリングブロック １２２ 可逆ＤＣＴ １２３ ジグザグ順序付けブロック １２４ ランレングスブロック １２５ ハフマンコーダ １２６ シグナリングブロック １２７ 量子化ブロック １３３ 文脈モデル １３４ 確率予測マシン １３５ ビットストリームジェネレータ ２０１ カメラ ２０２ ロスレス圧縮器 ２０３ 抽出ブロック ２０４ モーションＪＰＥＧ伸長器 ２０５ ロスレス伸長器 ２０６ 画質向上ブロック ２０７ ＭＰＥＧ圧縮器 ３０１〜３０９ 回転 ３１０，３１１ 乗算 ３１２〜３１５ 回転 ３２０ ４点ＡＰＴ ３３０ 補助マトリックス ３４０ ４５゜初期回転 ４０１〜４０６ 回転 ５０１〜５１２ 回転 ５２０〜５２６ 回転 ５３１〜５３４ 回転 ５４０〜５４３ 回転 ６０２，６０６，６０７ 乗算器 ６０３，６０５，６０８ 丸めブロック ６０４，６０９ 加算器 ７０３，７０７，７０９ 乗算器 ７０４，７０７，７０９ 丸めブロック ７０５，７０８，７１１ 減算器 １１０１，１１０２ ルックアップテーブル（ＬＵＴ） １２０１，１２１１，１２１２ 加算器 １２０２ 減算器 １２０３，１２０４ 除算器 １２０５ パリティ訂正ブロック １２０６，１２０７ 乗算器 １２０８ ルックアップテーブル（ＬＵＴ） １２０９，１２１０ 乗算器

Claims (13)

【特許請求の範囲】
1. 【請求項１】 可逆離散コサイン変換（ＤＣＴ）を有す
   ることを特徴とする圧縮器。
2. 【請求項２】 可逆離散コサイン変換（ＤＣＴ）を有す
   る圧縮器と、伸長器とを具備することを特徴とする圧縮
   ／伸長システム。
3. 【請求項３】 該伸長器が可逆逆ＤＣＴを有する伸長器
   であることを特徴とする請求項２記載の圧縮／伸長シス
   テム。
4. 【請求項４】 該伸長器が逆ＤＣＴを有する従来の伸長
   器からなることを特徴とする請求項２記載の圧縮／伸長
   システム。
5. 【請求項５】 該ＤＣＴが複数の２点回転からなること
   を特徴とする請求項１記載の圧縮器。
6. 【請求項６】 複数の２点回転が変換からなることを特
   徴とする請求項５記載の圧縮器。
7. 【請求項７】 該変換のそれぞれが平衡スケールファク
   タを持つことを特徴とする請求項６記載の伸長器。
8. 【請求項８】 第１の複数の回転、該第１の複数の回転
   の出力の第１の組と接続され、かつ、Ｂの回転を含む第
   ２の複数の回転を有する４点パラメタライズド変換、及
   び該第１の複数の回転の出力の第２の組と接続され、Ａ
   の回転とＣの回転を含む補助マトリックスを具備し、 該第１の複数の回転、該４点パラメタライズド変換及び
   該補助マトリックスは可逆ブロックベース変換として働
   くことを特徴とするブロックベース変換の圧縮器。
9. 【請求項９】 入力と、変換入力値の変換出力値へのマ
   ッピングを有するルックアップテーブルを含む少なくと
   も１つの変換を有する可逆ＤＣＴとを具備し、該マッピ
   ングは、丸めが入力を同じ変換値にマップするところの
   第１のグループからの入力を、丸めに利用されなかった
   であろう変換出力へマップすることを特徴とする圧縮
   器。
10. 【請求項１０】 丸めオフセットのためのルックアップ
    テーブルを作成するための方法であって、 初期丸めを用いて入力値の変換出力値への第１のマッピ
    ングを生成するステップ、及び該第１のマッピンにおけ
    る衝突の各行に対し（ただし、衝突は入力の同じ変換出
    力値へのマッピングである）、 該初期丸めで用いられないであろう変換出力値を提供す
    るために必要とされ、それぞれが該初期丸めに用いられ
    ないであろう変換出力値からなるエキストラを、それぞ
    れ含む行の数を求めるステップ、 各衝突に対し１つのエキストラを提供するために部分エ
    キストラ行が必要なときに、ある行内の均等に間隔をお
    いたある個数のエキストラを選択するステップ、 エキストラを列順にソートするステップ、 該ルックアップテーブル内で使用するための第２のマッ
    ピングを生成するためエキストラを衝突に列順に割り当
    てるステップ、を含むことを特徴とするルックアップテ
    ーブル作成方法。
11. 【請求項１１】 丸めオフセットのためのルックアップ
    テーブルを作成するための方法であって、 複数の入力の同じ変換出力値へのマッピングが存在する
    各衝突に対し、 初期丸めで使用されないであろう変換出力値が存在する
    各エキストラに対し、 所定の基準に基づき他のエキストラとの交換を割り出す
    ステップ、及び該交換を実行するステップ、を含むこと
    を特徴とするルックアップテーブル作成方法。
12. 【請求項１２】 可逆ブロックベース変換と、該可逆ブ
    ロックベース変換の出力より得られるデータを符号化す
    るため該可逆ブロックベース変換に接続されたコーダと
    を具備する圧縮器。
13. 【請求項１３】 コンピュータに、入力データを受け取
    るステップ及び可逆ＤＣＴ変換を実行するステップを実
    行させるためのプログラムが格納されたことを特徴とす
    るコンピュータが読み出し可能な記録媒体。