(57)【要約】  変換マトリクスを含む変換関数を使用して時間ドメインから周波数ドメインへ及びそれとは逆にデジタル信号を変換する方法であって、デジタル信号は、複数のブロックへとグループ分けされるデータ記号で構成され、各ブロックが所定数のデータ記号を含むような方法。この方法は、デジタル信号の２つのブロックを１つの変換エレメントにより変換するプロセスを備え、変換エレメントは、２つのサブマトリクスを含むブロック対角マトリクスに対応し、各サブマトリクスは、変換マトリクスを備え、且つ変換エレメントは、複数のリフトステージを備え、更に、各リフトステージは、補助的な変換及び丸めユニットによるデジタル信号のブロックの処理を含む。【選択図】図３
2007507790.tif 000002
【特許請求の範囲】
【請求項１】
変換マトリクスを含む変換関数を使用して時間ドメインから周波数ドメインへ及びそれとは逆にデジタル信号を変換する方法であって、デジタル信号は、複数のブロックへとグループ分けされるデータ記号で構成され、各ブロックが所定数のデータ記号を含むような方法において、
前記デジタル信号の２つのブロックを１つの変換エレメントにより変換するステップを備え、前記変換エレメントは、２つのサブマトリクスを含むブロック対角マトリクスに対応し、各サブマトリクスは、前記変換マトリクスを備え、且つ前記変換エレメントは、複数のリフトステージを備え、更に、各リフトステージは、補助的な変換及び丸めユニットによる前記デジタル信号のブロックの処理を含むようにした方法。
【請求項２】
前記変換関数は、ＤＣＴ−Ｉ変換関数、ＤＣＴ−ＩＶ変換関数、ＤＦＴ−Ｉ変換関数、ＤＦＴ−ＩＶ変換関数、ＤＳＴ−Ｉ変換関数、ＤＳＴ−ＩＶ変換関数、ＤＷＴ−Ｉ変換関数、又はＤＷＴ−ＩＶ変換関数である、請求項１に記載の方法。
【請求項３】
各リフトステージはリフトマトリクスに対応し、該リフトマトリクスは、４つのサブマトリクスと、これらサブマトリクスの２つとして２つの可逆整数マトリクスを一方の対角方向に、且つこれらサブマトリクスの他の２つとして変換マトリクス及びゼロを他方の対角方向に伴うようなブロック三角形マトリクスである、請求項１又は２に記載の方法。
【請求項４】
各リフトマトリクスにおける前記可逆整数マトリクスは、恒等マトリクス又は負の恒等マトリクスである、請求項３に記載の方法。
【請求項５】
前記変換エレメントは、３つのリフトステージを備える、請求項１から４のいずれかに記載の方法。
【請求項６】
オーディオ信号又はビデオ信号が前記デジタル信号として使用される、請求項１から５のいずれかに記載の方法。
【請求項７】
変換マトリクスを含む変換関数を使用して時間ドメインから周波数ドメインへ及びそれとは逆にデジタル信号を変換する装置であって、デジタル信号は、データ記号で構成されて、複数のブロックへと分割され、各ブロックが所定数のデータ記号を含むような装置において、
前記デジタル信号の２つのブロックを１つの変換エレメントにより変換するための変換ユニットを備え、前記変換エレメントは、２つのサブマトリクスを含むブロック対角マトリクスに対応し、各サブブロックは、前記変換マトリクスを備え、且つ前記変換エレメントが複数のリフトステージを備えるようにした装置。
【請求項８】
前記変換ユニットは、前記デジタル信号のブロックを処理するために各リフトステージに対する補助的な変換ユニットを備える、請求項７に記載の装置。
【請求項９】
前記変換ユニットは、前記デジタル信号のブロックを処理するために各リフトステージに対する丸めユニットを備える、請求項７又は８に記載の装置。
【請求項１０】
前記変換ユニットは、
複数のデータブロックを受け取るように結合されると共に、各データブロックをＭＤＣＴ係数へとドメイン変換するように構成された変更型離散的コサイン変換装置と、
前記ＭＤＣＴ係数の各々を受け取るように結合された量子化装置であって、それに応答して、量子化されたＭＤＣＴ係数を発生するように動作できる量子化装置と、
前記量子化されたＭＤＣＴ係数を受け取るように結合されたビットストリームエンコーダであって、それに応答して、知覚的にコード化されたビットストリームを発生するビットストリームエンコーダと、
前記量子化されたＭＤＣＴ係数を受け取るように結合された逆量子化装置であって、前記ＭＤＣＴ係数を非量子化状態に回復させるように動作できる逆量子化装置と、
前記回復されたＭＤＣＴ係数を受け取るように結合されると共に、整数値のＭＤＣＴ係数を発生するように動作できる丸めユニットと、
を備える請求項７から９のいずれかに記載の装置。
【請求項１１】
前記変換ユニットは、更に、
前記データブロックを受け取るように結合されると共に、それに応答して、ＩｎｔＭＤＣＴ係数を発生するように動作できる逆変更型離散的コサイン変換装置と、
各ＩｎｔＭＤＣＴ係数と整数値のＭＤＣＴ係数との間の差を計算して、各残余ＭＤＣＴ係数を発生するための手段と、
前記残余ＭＤＣＴ係数を受け取るように結合されると共に、それに応答して、ロスなしの改善ビットストリームを発生するように動作できるエントロピーコーダと、
を備える請求項１０に記載の装置。
【請求項１２】
前記変換ユニットは、更に、
前記知覚コード化ビットストリームを受け取るように結合されると共に、それに応答して、デコードされたビットストリームを出力するように動作できるビットストリームデコーダと、
前記デコードされたビットストリームを受け取るように結合され、それに応答して、回復されたＭＤＣＴ係数を発生するための逆量子化装置と、
前記回復されたＭＤＣＴ係数を受け取るように結合されると共に、各ＭＤＣＴ係数を整数値へと丸めるように動作できる丸めユニットと、
前記回復されたＭＤＣＴストリームを受け取るように結合され、それに応答して、前記知覚コード化信号の再構成されたコピーを発生するための逆ＭＤＣＴ装置と、
を備える請求項１１に記載の装置。
【請求項１３】
前記変換ユニットは、更に、
前記ロスなしのビットストリームを受け取るように結合されると共に、それに応答して、残余ＩｎｔＭＤＣＴ係数を発生するように動作できるエントロピーデコーダと、
前記残余ＩｎｔＭＤＣＴ係数を整数値のＭＤＣＴ係数に加算して、ＩｎｔＭＤＣＴ係数を発生するための手段と、
前記整数値のＭＤＣＴ係数及び前記ＩｎｔＭＤＣＴ係数の加算を受け取るように結合されて、ロスなしにコード化されたオーディオ信号の再構成されたコピーを発生するための逆ＩｎｔＭＤＣＴ装置と、
を備える請求項１２に記載の装置。
【請求項１４】
プログラムが記録されたコンピュータ読み取り可能な媒体であって、前記プログラムは、変換マトリクスを含む変換関数を使用して時間ドメインから周波数ドメインへ及びそれとは逆にデジタル信号を変換する方法をコンピュータで実行させるように適応され、前記デジタル信号は、データ記号で構成されて、複数のブロックへと分割され、各ブロックが所定数のデータ記号を含むようなコンピュータ読み取り可能な媒体において、
前記デジタル信号の２つのブロックを１つの変換エレメントにより変換するためのコードを備え、前記変換エレメントは、２つのサブマトリクスを含むブロック対角マトリクスに対応し、各サブブロックは、前記変換マトリクスを備え、且つ前記変換エレメントは、複数のリフトステージを備え、更に、各リフトステージは、補助的な変換及び丸めユニットによる前記デジタル信号のサブブロックの処理を含むようにしたコンピュータ読み取り可能な媒体。
【発明の詳細な説明】
【関連出願へのクロスレファレンス】
【０００１】
本出願は、２００３年９月２９日に出願された米国プロビジョナル特許出願第６０／５０７，２１０号、及び２００３年９月２９に出願された米国プロビジョナル特許出願第６０／５０７，４４０号の優先権の利益を請求するもので、これら各々の内容は、その全体を全ての目的で参考としてここに援用する。
【０００２】
更に、以下の共通に所有する特許出願は、本出願と同日に出願されたもので、その全体をここに援用する。
【０００３】
「Methodfor Performing a Domain Transformation of a Digital Signal from the Time Domaininto the Frequency Domain and Vice Versa」、代理人ドケット第Ｐ１００４４２号；及び
【０００４】
「Processand Device for Determining a Transforming Element for a Given Transformation Function,Method and Device for Transforming a Digital Signal from the Time Domain intothe Frequency Domain and Vice Versa and Computer Readable Medium」、代理人ドケット第Ｐ１００４５２号。
【背景】
【０００５】
本発明は、時間ドメインから周波数ドメインへ及びそれとは逆にデジタル信号を変換する方法に係る。
【０００６】
ドメイン変換、例えば、離散的コサイン変換（ＤＣＴ）は、近代的な信号処理産業において広く使用されている。近年、ＤＣＴの変形で、整数ＤＣＴと称されるものが、ロスのないコード化アプリケーションにおいて重要な役割を果たすことから、多大な研究上の関心を集めている。「ロスのない」という語は、デコーダが、エンコードされたビットストリームからソース信号の厳密なコピーを発生できることを意味する。
【０００７】
ＤＣＴは、実数値型ブロック変換である。入力ブロックが整数のみで構成されても、ＤＣＴの出力ブロックは、非整数成分を含むことができる。便宜上、入力ブロックは、入力ベクトルと称され、出力ブロックは、出力ベクトルと称される。ベクトルが整数成分しか含まない場合には、それが整数ベクトルと称される。ＤＣＴとは対照的に、整数ＤＣＴは、整数入力ベクトルから整数出力ベクトルを発生する。同じ整数入力ベクトルに対して、整数ＤＣＴの整数出力ベクトルは、ＤＣＴの実数出力ベクトルを厳密に近似する。従って、整数ＤＣＴは、スペクトル分析においてＤＣＴの全ての良好なプロパティを保持する。
【０００８】
整数ＤＣＴの重要なプロパティは、可逆性である。可逆性とは、整数逆ＤＣＴ（ＩＤＣＴ）が存在し、整数ＤＣＴが入力ベクトルｘから出力ベクトルｙを発生する場合に、整数ＩＤＣＴがベクトルｙからベクトルｘを回復できることを意味する。時々、整数ＤＣＴは、順方向変換とも称され、一方、整数ＩＤＣＴは、逆方向又は逆変換とも称される。
【０００９】
整数変更型離散的コサイン変換（ＩｎｔＭＤＣＴ）と称される変換が近年提案されて、ＩＳＯ／ＩＥＣ  ＭＰＥＧ−４オーディオ圧縮に使用されている。このＩｎｔＭＤＣＴは、そのプロパティ、即ち変更型離散的コサイン変換（ＭＤＣＴ）から導出することができる。「Signal Processing with Lapped Transforms」、Artech House、１９９２年におけるH. S. Malvar著の開示は、ギブンズ(Givens)回転の列をＤＣＴ−ＩＶブロックと共にカスケード構成とすることでＭＤＣＴの効率的な実現を与える。ギブンズ回転は、整数対整数のマッピングを行うための３つのリフトステップへと因数分解できることが良く知られている。例えば、R. Geiger, T. Sporer, J. Koller, K. Brandenburg著の「Audio Coding based onInteger Transforms」、ＡＥＳ第１１１回コンベンション、米国、ニューヨーク、２００１年９月、を参照されたい。
【００１０】
それ故、ＩｎｔＭＤＣＴの実現は、整数ＤＣＴ−ＩＶの効率的な実施に依存する。整数変換は、各ギブンズ回転を３つのリフトステップに置き換えることによりそれらのプロートタイプから直接コンバートすることができる。各リフトステップには１つの丸め演算があるので、整数変換の全丸め回数は、プロートタイプ変換のギブンズ回転回数の３倍である。離散的三角法変換（例えば、離散的フーリエ変換（ＤＦＴ）又は離散的コサイン変換（ＤＣＴ））の場合に、それに伴うギブンズ回転の回数は、通常、Ｎｌｏｇ２Ｎレベルにあり、ここで、Ｎは、ブロックのサイズであり、即ちデジタル信号が分割される各ブロックに含まれるデータ記号の量である。従って、全丸め回数も、直接コンバートされる整数変換のファミリーに対して、Ｎｌｏｇ２Ｎレベルにある。丸めのために、整数変換は、そのフローティングポイントプロートタイプしか近似しない。丸めの回数と共に近似エラーが増加する。
【００１１】
それ故、デジタル信号をより効率的な仕方でドメイン変換するためのシステム及び方法が要望される。
【発明の概要】
【００１２】
本発明は、デジタル信号をドメイン変換するためのシステム及び方法であって、入力データの２つのブロックが同じオペレーションにおいて同時にドメイン変換されるようなシステム及び方法を提供する。この構成は、有効な丸め演算の回数、ひいては、近似エラーを減少させる。
【００１３】
本発明の一実施形態において、変換関数を使用してデジタル信号を時間ドメインから周波数ドメインへ及びそれとは逆に変換するための方法が提供される。変換関数は、変換マトリクスを含み、デジタル信号は、複数のブロックへとグループ分けされたデータ記号を含み、各ブロックは所定数のデータ記号を含む。この方法は、デジタル信号の２つのブロックを１つの変換エレメントで変換することを備え、この変換エレメントは、２つのサブマトリクスを含むブロック対角マトリクスに対応し、各サブマトリクスは、変換マトリクスを含むと共に、変換エレメントは、複数のリフトステージを含み、更に、各リフトステージは、補助的な変換及び丸めユニットによるデジタル信号のブロックの処理を含む。
【００１４】
本発明のこれら及び他の特徴は、添付図面及び特定実施形態の詳細な説明から良好に理解されよう。
【特定の実施形態の詳細説明】
【００１５】
図１は、本発明の実施形態によるオーディオエンコーダ１００の構成を示す図である。このオーディオエンコーダ１００は、変更型離散的コサイン変換（ＭＤＣＴ）に基づく従来の知覚ベースレイヤーコーダと、整数変更型離散的コサイン変換（ＩｎｔＭＤＣＴ）に基づくロスなし改善コーダとを備えている。
【００１６】
例えば、マイクロホン１１０により発生されてアナログ／デジタルコンバータ１１１によりデジタル化されたオーディオ信号１０９が、オーディオエンコーダ１００へ供給される。このオーディオ信号１０９は、複数のデータ記号を含む。このオーディオ信号１０９は、複数のブロックに分割され、各ブロックは、デジタル信号の複数のデータ記号を含み、又、各ブロックは、変更型離散的コサイン変換（ＭＤＣＴ）装置１０１により変換される。ＭＤＣＴ係数は、知覚モジュール１０２の助けで量子化装置１０３により量子化される。知覚モデルは、量子化エラーにより生じる可聴歪が低くなるように量子化装置１０３を制御する。量子化されたＭＤＣＴ係数は、その後、ビットストリームエンコーダ１０４によりエンコードされ、このエンコーダは、ロスのある知覚コード化出力ビットストリーム１１２を発生する。
【００１７】
ビットストリームエンコーダ１０４は、その入力を、ハフマンコード化又はランレングスコード化のような標準的な方法により、ロスのないように圧縮して、その入力より平均ビットレートが低い出力を発生する。又、入力オーディオ信号１０９は、ＩｎｔＭＤＣＴ装置１０５にも供給され、この装置は、ＩｎｔＭＤＣＴ係数を発生する。量子化装置１０３の出力である量子化されたＭＤＣＴ係数は、ＩｎｔＭＤＣＴ係数を予想するのに使用される。量子化されたＭＤＣＴ係数は、逆量子化装置１０６へ供給され、その出力（回復され又は非量子化のＭＤＣＴ係数）は、丸めユニット１０７へ供給される。
【００１８】
丸めユニットは、供給されたＭＤＣＴ係数を整数値へ丸め、整数値ＭＤＣＴとＩｎｔＭＤＣＴ係数との間の差である残余ＩｎｔＭＤＣＴ係数は、エントロピーコーダ１０８によりエントロピーコード化される。このエントロピーエンコーダは、ビットストリームエンコーダ１０４と同様のもので、その入力の平均ビットレートをロスなしに減少して、ロスなしの改善ビットストリーム１１３を発生する。このロスなしの改善ビットストリーム１１３は、知覚コード化ビットストリーム１１２と一緒に、入力オーディオ信号１０９を再構成するに必要な情報を最小限のエラーで搬送する。
【００１９】
図２は、図１に示すオーディオコーダ１００に対応する本発明の実施形態によるオーディオデコーダ２００の構成を示す。知覚コード化ビットストリーム２０７は、ビットストリームデコーダ２０１へ供給され、このデコーダは、図１のビットストリームエンコーダ１０４の動作に対して逆の動作を実行して、デコードされたビットストリームを発生する。デコードされたビットストリームは、逆量子化装置２０２へ供給され、その出力（回復されたＭＤＣＴ係数）は、逆ＭＤＣＴ装置２０３へ供給される。従って、再構成された知覚コード化オーディオ信号２０９が得られる。
【００２０】
ロスなしの改善ビットストリーム２０８は、エントロピーデコーダ２０４へ供給され、このデコーダは、図１のエントロピーエンコーダ１０８の動作とは逆の動作を実行し、対応する残余ＩｎｔＭＤＣＴ係数を発生する。逆量子化装置２０２の出力は、丸め装置２０５によって丸められて、整数値ＭＤＣＴ係数を発生する。この整数値ＭＤＣＴ係数は、残余ＩｎｔＭＤＣＴ係数に加算されて、ＩｎｔＭＤＣＴ係数を発生する。最終的に、逆ＩｎｔＭＤＣＴは、逆ＩｎｔＭＤＣＴ装置２０６によりＩｎｔＭＤＣＴ係数に適用されて、再構成されたロスなしのコード化オーディオ信号２１０を発生する。
【００２１】
図３は、ＤＣＴ−ＩＶを変換として使用すると共に、３つのリフトステージ、即ち第１リフトステージ３０１、第２リフトステージ３０２及び第３リフトステージ３０３を使用する本発明による方法の実施形態を示すフローチャート３００である。この方法は、好ましくは、図１のＩｎｔＭＤＣＴ装置１０５及び図２の逆ＩｎｔＭＤＣＴ装置２０６に使用されて、各々、ＩｎｔＭＤＣＴ及び逆ＩｎｔＭＤＣＴを実施する。図３において、ｘ１及びｘ２は、各々、デジタル信号の第１及び第２ブロックである。ｚは、中間信号であり、そしてｙ１及びｙ２は、各々、デジタル信号の第１及び第２ブロックに対応する出力信号である。
【００２２】
上述したように、ＤＣＴ−ＩＶアルゴリズムは、ロスなしのオーディオコード化において重要な役割を演じる。
【００２３】
【数１】
2007507790.tif 000003
【００２４】
従って、この実施形態では、本発明による変換エレメントに対応する変換マトリクスは、次の通りである。
【数２】
2007507790.tif 000004
【００２５】
リフトマトリクスの数、ひいては、変換エレメントにおけるリフトステージの数は、ＤＣＴ−ＩＶが変換関数である本発明のこの実施形態では、３である。
【００２６】
Ｎポイント実数入力シーケンスｘ（ｎ）のＤＣＴ−ＩＶは、次のように定義される。
【数３】
2007507790.tif 000005
【００２７】
ここで、ｘ１、ｘ２を２つの整数Ｎｘ１列ベクトルとする。これら列ベクトルｘ１、ｘ２は、本発明では１つの変換エレメントにより変換されるデジタル信号の２つのブロックに対応する。ｘ１、ｘ２のＤＣＴ−ＩＶ変換は、各々、ｙ１、ｙ２である。
【数４】
2007507790.tif 000006
【００２８】
（５）及び（６）を合成すると、次のようになる。
【数５】
2007507790.tif 000007
【００２９】
前記対角マトリクスは、変換エレメントが、本発明により、対応しているブロック対角マトリクスである。
【００３０】
これは、前記式が次のような簡単な代数変更により変化された場合にも、本発明の範囲内である。
【数６】
2007507790.tif 000008
【００３１】
式（１０）は、（３）におけるＤＣＴ−ＩＶプロパティを使用して容易に照合することができる。式（１０）を用いると、式（８）は、次のように表わすことができる。
【数７】
2007507790.tif 000009
【００３２】
式（１１）における３つのリフトマトリクスは、図３に示す３つのリフトステージに対応する。
【００３３】
式（１１）から、１つの変換エレメントで２つの整数ＤＣＴ−ＩＶを計算する次の整数ＤＣＴ−ＩＶアルゴリズムが導出される。
【００３４】
図４は、ＤＣＴ−ＩＶを変換関数として使用する本発明による方法の実施形態を示す。この実施形態は、ＩｎｔＭＤＣＴを実施するために図１に示すオーディオコーダ１００に使用される。図３と同様に、ｘ１及びｘ２は、入力デジタル信号の２つのブロックであり、ｚは、中間信号であり、そしてｙ１及びｙ２は、出力信号の対応ブロックである。
【００３５】
図４に示す３つのリフトステージは、式（１１）における３つのリフトマトリクスに対応する。
【００３６】
図４に示すように、時間対周波数ドメインの整数変換は、次のように決定される。
【００３７】
第１ステージ４０１において、ｘ２がＤＣＴ−ＩＶ変換４０２により変換され、次いで、ＤＣＴ−ＩＶ係数が丸められる（４０３）。丸められたＤＣＴ−ＩＶ係数は、次いで、ｘ１４０４に加算される。従って、中間信号ｚが発生される。従って、中間信号ｚは、次の式を満足する。
【数８】
2007507790.tif 000010
【００３８】
第２ステージ４０５において、ｚがＤＣＴ−ＩＶ変換４０６により変換され、ＤＣＴ−ＩＶ係数が丸められる（４０７）。次いで、丸められたＤＣＴ−ＩＶ係数から、ｘ１が減算される。従って、出力信号ｙ１が発生される。従って、出力信号ｙ１は、次の式を満足する。
【数９】
2007507790.tif 000011
【００３９】
第３ステージ４０９において、ｙ１がＤＣＴ−ＩＶ変換４１０により変換され、次いで、ＤＣＴ−ＩＶ係数が丸められる（４１１）。丸められたＤＣＴ−ＩＶ係数が、次いで、ｚから減算される。従って、出力信号ｙ２が発生される。従って、出力信号ｙ２は、次の式を満足する。
【数１０】
2007507790.tif 000012
【００４０】
図５は、ＤＣＴ−ＩＶを変換関数として使用する本発明の方法の実施形態に基づいて逆変換を行うためのアルゴリズムを示す。この実施形態は、逆ＩｎｔＭＤＣＴを実施するために図２に示すオーディオデコーダ２００に使用される。図５に示すアルゴリズムは、図４に示すアルゴリズムの逆である。異なる信号ｙ１、ｙ２、ｘ１、ｘ２、ｚに対する表示は、図４の表示に対応して選択されたものである。
【００４１】
図５に示すように、周波数対時間ドメインの整数変換は、次のように決定される。
【００４２】
第１ステージ５０１において、ｙ１がＤＣＴ−ＩＶ変換５０２により変換され、ＤＣＴ−ＩＶ係数が丸められる（５０３）。丸められたＤＣＴ−ＩＶ係数は、次いで、ｙ２に加算される（５０４）。従って、中間信号ｚが発生される。従って、中間信号ｚは、次の式を満足する。
【数１１】
2007507790.tif 000013
【００４３】
第２ステージ５０５において、ｚがＤＣＴ−ＩＶ変換５０６により変換され、ＤＣＴ−ＩＶ係数が丸められる。次いで、その丸められたＤＣＴ−ＩＶ係数から、ｙ１が減算される。従って、信号ｘ２が発生される。従って、信号ｘ２は、次の式を満足する。
【数１２】
2007507790.tif 000014
【００４４】
第３ステージ５０９において、ｘ２がＤＣＴ−ＩＶ変換５１０により変換され、ＤＣＴ−ＩＶ係数が丸められる（５１１）。この丸められたＤＣＴ−ＩＶ係数が、次いで、ｚから減算される。従って、信号ｘ１が発生される。従って、ｘ１は、次の式を満足する。
【数１３】
2007507790.tif 000015
【００４５】
式（１３ａ）から（１３ｃ）に基づくアルゴリズムは、式（１２ａ）から（１２ｃ）に基づくアルゴリズムに対して逆であることが明らかである。従って、図１及び２に示すエンコーダ及びデコーダに使用した場合には、これらアルゴリズムは、ロスのないオーディオコード化のための方法及び装置をもたらす。
【００４６】
以下に述べる本発明の実施形態では、上述した方法がイメージアーカイブシステムに使用される。
【００４７】
式（１２ａ）から（１２ｃ）及び（１３ａ）から（１３ｃ）は、更に、２つのＮｘＮ整数ＤＣＴ−ＩＶを比較するために、３つのＮｘＮＤＣＴ−ＩＶ、３つのＮｘ１丸め、及び３つのＮｘ１加算が必要であることを示している。それ故、１つのＮｘＮ整数ＤＣＴ−ＩＶについては、平均が次のようになる。
【数１４】
2007507790.tif 000016
但し、ＲＣ（．）は、全丸め回数であり、ＡＣ（．）は、全演算回数である。直接コンバートされる整数ＤＣＴ−ＩＶアルゴリズムに比して、ここに提案する整数ＤＣＴ−ＩＶアルゴリズムは、ＲＣをレベルＮｌｏｇ２ＮからＮへ減少する。
【００４８】
式（１５）で示されたように、ここに提案する整数ＤＣＴ−ＩＶアルゴリズムの演算の複雑さは、ＤＣＴ−ＩＶアルゴリズムより約５０％も高い。しかしながら、ＲＣも考慮した場合には、ここに提案するアルゴリズムの合成複雑さ（ＡＣ＋ＲＣ）は、直接コンバート式の整数アルゴリズムを著しく越えることはない。アルゴリズムの複雑さの厳密な分析は、使用するＤＣＴ−ＩＶアルゴリズムに依存する。
【００４９】
図４及び５に示すように、ここに提案する整数ＤＣＴ−ＩＶアルゴリズムは、構造が簡単でモジュール状である。これは、何らかの既存のＤＣＴ−ＩＶアルゴリズムをそのＤＣＴ−ＩＶ計算ブロックに使用することができる。ここに提案するアルゴリズムは、ＩｎｔＭＤＣＴを要求するアプリケーション、例えば、ＭＰＥＧ−４オーディオ拡張３参照モデル０に適している。
【００５０】
図６は、本発明の実施形態によるイメージアーカイブシステムの構成を示す。
【００５１】
図６において、イメージソース６０１、例えば、カメラは、アナログイメージ信号を発生する。このイメージ信号は、アナログ／デジタルコンバータ６０２により処理されて、それに対応するデジタルイメージ信号を発生する。このデジタルイメージ信号は、時間ドメインから周波数ドメインへの変換を含むロスなしのイメージエンコーダ６０３によりロスなしにエンコードされる。この実施形態では、時間ドメインは、イメージの座標スペースに対応する。ロスなしのコード化イメージ信号が、記憶装置６０４、例えば、ハードディスク又はＤＶＤに記憶される。イメージが必要とされるときには、ロスなしのコード化イメージ信号が、記憶装置６０４からフェッチされて、ロスなしのイメージデコーダ６０５へ送られ、このデコーダは、ロスなしのイメージエンコーダ６０３に対応するもので、ロスなしのコード化イメージ信号をデコードして、データロスを伴わずに元のイメージ信号を再構成する。
【００５２】
イメージ信号のこのようなロスなしのアーカイブは、例えば、イメージが半導体ウェハのエラーマップであって、後で分析するためにこれを記憶しなければならない場合に、重要である。
【００５３】
本発明のこの実施形態において、図３から５に示す方法の実施形態は、ロスなしのイメージエンコーダ６０３及びロスなしのイメージデコーダ６０５に使用される。上述したように、図３から５に示す方法の実施形態は、可逆の変換を提供し、従って、特に、ロスなしのイメージコード化方法を提供する。
【００５４】
本発明による方法は、オーディオ及びイメージ信号に限定されない。他のデジタル信号、例えば、ビデオ信号も、本発明の方法により変換することができる。
【００５５】
以下、本発明により時間ドメインから周波数ドメインへ及びそれとは逆にデジタル信号を変換する方法の更に別の実施形態を説明する。
【００５６】
本発明のこの実施形態では、ドメイン変換がＤＣＴ変換であり、従って、ブロックサイズＮは、何らかの整数である。一実施形態では、Ｎが２の累乗である。
【００５７】
【数１５】
2007507790.tif 000017
【００５８】
【数１６】
2007507790.tif 000018
【００５９】
各リフトマトリクスＬ２Ｎに対して、リフトステージの可逆の整数対整数マッピングは、ここに援用する参照文献「Factoring Wavelet Transforms into Lifting Steps」、Tech. Report、I. Daubechies及びW. Sweldens著、Bell Laboratories, LucentTechnologies、１９９６年、に説明された２ｘ２リフトステップと同様に実現される。唯一の相違は、単一の変数ではなく、ベクトルに丸め演算が適用されることである。
【００６０】
他の実施形態の前記説明において、リフトマトリクスに対してリフトステージをいかに実現するかは既に述べた。従って、リフトマトリクスに対応するリフトステージの説明は、以下では省略する。
【００６１】
【数１７】
2007507790.tif 000019
【００６２】
前記式の右側を構成しているマトリクスは、次のように説明される。
【００６３】
Ｐ１は、次式で与えられる第１の置換マトリクスである。
【数１８】
2007507790.tif 000020
【００６４】
Ｐ２は、第２の置換マトリクスであり、その一例が、次のＭＡＴＬＡＢスクリプトにより発生される。
【数１９】
2007507790.tif 000021
【００６５】
一例として、Ｎが４であるときには、Ｐ２が次のような８ｘ８マトリクスである。
【数２０】
2007507790.tif 000022
【００６６】
Ｐ３は、第３の置換マトリクスであり、その一例が、次のＭＡＴＬＡＢスクリプトにより発生される。
【数２１】
2007507790.tif 000023
【００６７】
一例として、Ｎが４であるときには、Ｐ３が次のような８ｘ８マトリクスである。
【数２２】
2007507790.tif 000024
【００６８】
【数２３】
2007507790.tif 000025
【００６９】
【数２４】
2007507790.tif 000026
【００７０】
【数２５】
2007507790.tif 000027
【００７１】
【数２６】
2007507790.tif 000028
【００７２】
【数２７】
2007507790.tif 000029
【００７３】
【数２８】
2007507790.tif 000030
【００７４】
【数２９】
2007507790.tif 000031
【００７５】
【数３０】
2007507790.tif 000032
【００７６】
式（４２）から、次元Ｎｘ１の２つの入力信号に対して整数ＤＣＴを計算することができる。
【００７７】
式（４２）は、ＤＣＴ−ＩＶ変換ドメインを記述するリフトマトリクス因数分解を与えるので、そのリフトマトリクスを、ここに示すように使用して、与えられた入力信号のドメイン変換を計算することができる。
【００７８】
式（４２）は、次のようにして導出することができる。
【００７９】
次の分解は、Wang、Zhongde著の「On Computing the Discrete Fourier and Cosine Transforms」、IEEE Transactions onAcoustics, Speech and Signal Processing、第ＡＳＳＰ−３３巻、第４号、１９８５年１０月、からの開示を使用して導出することができる。
【数３１】
2007507790.tif 000033
【００８０】
【数３２】
2007507790.tif 000034
【００８１】
【数３３】
2007507790.tif 000035
【００８２】
【数３４】
2007507790.tif 000036
【００８３】
【数３５】
2007507790.tif 000037
【００８４】
この実施形態では、ドメイン変換を計算するときに、４Ｎ回の丸め演算しか必要とされず、これについて、以下に述べる。
【００８５】
ここで、各々、α（＊）を実数加算の回数とし、μ（＊）を実数乗算の回数とし、γ（＊）を実数丸めの回数とする。ここに提案するＩｎｔＤＣＴアルゴリズムの場合、次のようになる。
α（ＩｎｔＤＣＴ）＝１１Ｎ＋３α（ＤＣＴ−ＩＶ）
μ（ＩｎｔＤＣＴ）＝９Ｎ＋３μ（ＤＣＴ−ＩＶ）
γ（ＩｎｔＤＣＴ）＝８Ｎ
【００８６】
前記結果は、データサンプルの２つのブロックに対するものである。というのは、ここに提案するＩｎｔＤＣＴアルゴリズムは、それらを一緒に処理するからである。従って、データサンプルの１つのブロックに対して、計算の回数が半減し、次のようになる。
α１（ＩｎｔＤＣＴ）＝５．５Ｎ＋１．５α（ＤＣＴ−ＩＶ）
μ１（ＩｎｔＤＣＴ）＝４．５Ｎ＋１．５μ（ＤＣＴ−ＩＶ）
γ１（ＩｎｔＤＣＴ）＝４Ｎ
但し、α１、μ１及びγ１は、各々、１つのサンプルブロックに対する実数加算の回数、実数乗算の回数、及び実数丸めの回数である。
【００８７】
ＤＣＴ−ＩＶ計算の場合には、ここに援用する参照文献「Signal Processing with lapped Transforms」、H. S. Malvar著、マサチューセッツ州ノルウッド、アーテック・ハウス、１９９２年、第１９９−２０１ページ、に掲載されたＦＦＴベースのアルゴリズムを使用することができ、これについては、
α（ＤＣＴ−ＩＶ）＝１．５Ｎｌｏｇ２Ｎ
μ（ＤＣＴ−ＩＶ）＝０．５Ｎｌｏｇ２Ｎ＋Ｎ
その結果、次のようになる。
α１（ＩｎｔＤＣＴ）＝２．２５Ｎｌｏｇ２Ｎ＋５．５Ｎ
μ１（ＩｎｔＤＣＴ）＝０．７５Ｎｌｏｇ２Ｎ＋６Ｎ
【００８８】
以下、時間ドメインから周波数ドメインへ及びそれとは逆にデジタル信号を変換する方法の更に別の実施形態を説明する。
【００８９】
この実施形態では、離散的高速フーリエ変換（ＦＦＴ）がドメイン変換として使用される。
【００９０】
Ｆを、正規化されたＦＦＴのＮｘＮ変換マトリクスとする。
【数３６】
2007507790.tif 000038
但し、Ｎは、変換サイズであり、ｍ及びｎは、マトリクス指数である。
【００９１】
この実施形態のもとでは、次元ＮｘＮの置換マトリクスＰは、指数０又は１を含むマトリクスである。これにＮｘ１ベクトル（入力信号のマトリクス表示）を乗算した後、ベクトルにおけるエレメントの順序が変更される。
【００９２】
この実施形態では、リフトマトリクスは、次の式の２Ｎｘ２Ｎマトリクスとして定義される。
【数３７】
2007507790.tif 000039
但し、Ｐ１及びＰ２は、２つの置換マトリクスであり、Ｏは、ＮｘＮのゼロマトリクスであり、Ａは、任意のＮｘＮマトリクスである。リフトマトリクスＬについては、Ｉ．ダウベッチーズ氏のここに援用する前記参照文献における２ｘ２リフトステップと同様に実現される。しかしながら、上述したように、単一の変数ではなく、丸めがベクトルに適用される。Ｌの転置、ＬＴも、リフトマトリクスであることが明らかであろう。
【００９３】
更に、Ｔを２Ｎｘ２Ｎ変換マトリクスとする。
【数３８】
2007507790.tif 000040
【００９４】
従って、変更型変換マトリクスＴ（従って、ドメイン変換それ自体）は、リフトマトリクス因数分解として表現することができる。
【数３９】
2007507790.tif 000041
【００９５】
式（５３）において、かぎカッコ内のブランクスペースは、全てゼロのマトリクスエレメントを表わす。
【００９６】
式（５１）から明らかなように、リフトマトリクスの因数分解は、ここに述べる方法を使用して２つのＮｘ１複素数ベクトルに対する整数ＦＦＴを計算するのに使用できる。
【００９７】
この実施形態のもとでは、ドメイン変換の計算は、３Ｎ回の丸め演算しか必要とせず、これについて、以下に述べる。
α（＊）を実数加算の回数とする。
μ（＊）を実数乗算の回数とする。
γ（＊）を実数丸め演算の回数とする。
【００９８】
ここに提案するＩｎｔＦＦＴアルゴリズムの場合に、次のものが得られる。
α（ＩｎｔＦＦＴ）＝６Ｎ＋３α（ＦＦＴ）
μ（ＩｎｔＦＦＴ）＝３μ（ＦＦＴ）
γ（ＩｎｔＦＦＴ）＝６Ｎ
【００９９】
前記結果は、データサンプルの２つのブロックに対するものである。というのは、ここに提案するＩｎｔＦＦＴアルゴリズムは、それらを一緒に処理するからである。従って、データサンプルの１つのブロックに対して、計算の回数が半減し、次のようになる。
α１（ＩｎｔＦＦＴ）＝３Ｎ＋１．５α（ＦＦＴ）
μ１（ＩｎｔＦＦＴ）＝１．５μ（ＦＦＴ）
γ１（ＩｎｔＦＦＴ）＝３Ｎ
但し、α１、μ１及びγ１は、各々、１つのサンプルブロックに対する実数加算の回数、実数乗算の回数、及び実数丸め演算の回数である。
【０１００】
ＦＦＴ計算に対して、スプリット−ラディックスＦＦＴ（ＳＲＦＦＴ）アルゴリズムを使用することができ、これについては、
α（ＳＲＦＦＴ）＝３Ｎｌｏｇ２Ｎ−３Ｎ＋４
μ（ＳＲＦＦＴ）＝Ｎｌｏｇ２Ｎ−３Ｎ＋４
その結果、次のようになる。
α１（ＩｎｔＦＦＴ）＝４．５Ｎｌｏｇ２Ｎ−１．５Ｎ＋６
μ１（ＩｎｔＦＦＴ）＝１．５Ｎｌｏｇ２Ｎ−４．５Ｎ＋６
【０１０１】
図７は、上述したＤＣＴ変換技術及び上述したＦＦＴドメイン変換の変換精度を評価するのに使用される順方向及び逆方向変換コーダを示す。テストは、ここに援用する「Coding of Moving Pictures and Audio: Work plan for Evaluation ofInteger MDCT for FGS to Lossless Experimentation Framework」、ＩＳＯ／ＩＥＣ  ＪＴＣ  １／ＳＣ  ２９／ＷＧ  １１  Ｎ５５７８、Pattaya、Thailand、２００３年３月、に記載されたＭＰＥＧ−４ロスなしオーディオコードグループにより提案された評価規格に基づいて変換の平均２乗エラー（ＭＳＥ）を測定することを含む。
【０１０２】
より詳細には、ＩｎｔＤＣＴ及び整数逆ＤＣＴ（ＩｎｔＩＤＣＴ）に対するＭＳＥは、次のように表わされる。
【数４０】
2007507790.tif 000042
但し、エラー信号ｅは、図１の場合と同様に、ＩｎｔＤＣＴについてはｅｆ、及びＩｎｔＩＤＣＴについてはｅｔである。Ｋは、評価に使用されるサンプルブロックの合計数である。
【０１０３】
ＩｎｔＦＦＴ及び整数逆ＦＦＴ（ＩｎｔＩＦＦＴ）に対するＭＳＥは、次のように表わされる。
【数４１】
2007507790.tif 000043
【０１０４】
両ドメイン変換の場合に、１５個の異なるタイプの音楽ファイルで合計４５０秒が４８ｋＨｚ／１６ビットテストセットに使用された。表１は、テスト結果を示す。
【０１０５】
表１から明らかなように、本発明のシステム及び方法を使用して生じたＭＳＥは、非常に僅かであり、そして従来のシステムとは異なり、処理部とっくサイズとは実質的に独立したものである。ＤＣＴ−ＩＶドメイン変換を参照すれば、ＭＳＥは、４０９６ビットまでのブロックザイズＮの増加と共に僅かに増加するだけである。ＦＦＴのＭＳＥは、いっそう良好で、４０９６ビットまでのブロックサイズに対して０．４の一定ＭＳＥを示す。本発明の実証された性能を、より長いブロックサイズに対する現在の能力及び増加するニーズの観点から見ると、本発明の効果が明らかとなろう。
【表１】
2007507790.tif 000044
【０１０６】
援用する参照文献
以下の文書を、参考としてここに援用する。
H.S. Malvar著、「SignalProcessing with Lapped Transforms」、Artech House、１９９２年；
R.Geiger, T. Sporer, J. Koller, K. Brandenburg著、「Audio Coding based on Integer Transforms」、ＡＥＳ第１１１回コンベンション、米国、ニューヨーク、２００１年９月；
Wang,Zhongde著、「OnComputing the Discrete Fourier and Cosine Transforms」、IEEE Transactions onAcoustics, Speech and Signal Processing、第ＡＳＳＰ−３３巻、第４号、１９８５年１０月；
I.Daubechies及びW.Sweldens著、「Factoringwavelet transforms into lifting steps」、Tech. Report, Bell Laboratories, Lucent Technologies、１９９６年；
S.Oraintara, Y. J. Chen及びT. Q. Nguyen著、「Integer fast Fourier transform」、IEEE Trans. Signal Processing、第５０巻、第３号、２００２年３月、第６０７−６１８ページ；
P.Hao及びQ. Shi著、「Matrix factorization forreversible integer mapping」、IEEE Trans. Signal Processing、第４９巻、第１０号、２００１年１０月、第２３１４−２３２４ページ；
G.Plonka及びM.Tasch著、「Invertible integer DCTalgorithms」、Appl.Comput. Harmon. Anal. 12: 70-88、２００３年；
Y.H. Zeng、L. Z.Cheng、G. A. Bi及びAlex C. Kot著、「Integer DCTs and fastalgorithms」、IEEETrans. Signal Processing、第４９巻、第１１号、２００１年１１月、第２７７４−２７８２ページ；
J.Wang, J. Sun及びS.Yu著、「1-D and2-D transforms from integers to integers」、in Proc. Int. Conf. Acoustics, Speech and Signal Processing、香港、２００３年、第ＩＩ巻、第５４９−５５２ページ；及び
「Codingof Moving Pictures and Audio: Work plan for Evaluation of Integer MDCT for FGSto Lossless Experimentation Framework」、ISO/IEC JTC 1/SC 29/WG 11 N5578, Pattaya, Thailand、２００３年３月。
【図面の簡単な説明】
【０１０７】
【図１】本発明の実施形態によるオーディオエンコーダの構成を示す図である。
【図２】図１に示すオーディオコーダに対応する、本発明の実施形態によるオーディオデコーダの構成を示す図である。
【図３】本発明による方法の実施形態を示すフローチャートである。
【図４】ＤＣＴ−ＩＶを変換関数として使用する本発明による方法の実施形態を示す図である。
【図５】図４に示す本発明の方法の実施形態に基づく逆変換のアルゴリズムを示す図である。
【図６】本発明の実施形態によるイメージアーカイブシステムの構成を示す図である。
【図７】ここに提案するシステム及び方法の性能を評価するのに使用される順方向及び逆方向変換コーダを示す図である。
【符号の説明】
【０１０８】
１００・・・オーディオエンコーダ、１０１・・・変更型離散的コサイン変換（ＭＤＣＴ）、１０２・・・知覚モジュール、１０３・・・量子化装置、１０４・・・ビットストリームエンコーダ、１０５・・・ＩｎｔＭＤＣＴ装置、１０６・・・逆量子化装置、１０７・・・丸めユニット、１０８・・・エントロピーコーダ、１０９・・・オーディオ信号、１１０・・・マイクロホン、１１１・・・アナログ／デジタルコンバータ、１１２・・・知覚コード化出力ビットストリーム、１１３・・・ロスなしの改善ビットストリーム、２００・・・オーディオでコーダ、２０１・・・ビットストリームデコーダ、２０２・・・逆量子化装置、２０３・・・逆ＭＤＣＴ装置、２０４・・・エントロピーデコーダ、２０５・・・丸め装置、２０６・・・逆ＩｎｔＭＤＣＴ装置、２０７・・・知覚コード化ビットストリーム、２０８・・・ロスなしの改善ビットストリーム、２０９・・・再構成された知覚コード化オーディオ信号、３０１・・・第１リフトステージ、３０２・・・第２リフトステージ、３０３・・・第３リフトステージ
【図１】
2007507790.tif 000045
【図２】
2007507790.tif 000046
【図３】
2007507790.tif 000047
【図４】
2007507790.tif 000048
【図５】
2007507790.tif 000049
【図７】
2007507790.tif 000050
【図６】
2007507790.tif 000051
【国際調査報告】
2007507790.tif 000052
2007507790.tif 000053
2007507790.tif 000054