(57)【要約】  変換符号化データの逆変換を計算する方法及び関連の装置が記述されている。主たる実施例において、８×８離散コサイン変換（ＤＣＴ）２００は、係数の列（２０２，２０４，２０６）に構成され、最後の係数は、既知の方法でミスマッチを制御するように選択的に変更される。逆ＤＣＴは、全体がゼロ値係数（２０４）により構成されるグループに対して短縮された処理を施すように選択的に行われる。短縮された処理を施すかどうかを選択する目的で、包含される非ゼロ値係数だけがミスマッチ制御のために変更された係数である場合にデータグループ（２０６）がゼロ値グループとみなされる。さらに、変更された係数が出力について有する作用が予め計算され、その予め計算された値が非ゼロ係数を無視するために補償するのに用いられる。
2007527055.tif 000002
【特許請求の範囲】
【請求項１】
変換符号化データの逆変換を計算する方法であって、前記符号化データは、係数のグループに構成され、少なくとも１つの係数は、ミスマッチを制御するように選択的に変更され、前記逆変換は、全体がゼロ値係数により構成されるグループに対して短縮された処理を施すように選択的に行われ、短縮された処理を施すかどうかを選択する目的で、包含される非ゼロ値係数だけがミスマッチ制御のために変更される係数である場合にデータグループがゼロ値グループとみなされる、方法。
【請求項２】
請求項１に記載の方法であって、前記変換符号化データは、離散コサイン変換符号化データである、方法。
【請求項３】
請求項２に記載の方法であって、前記離散コサイン変換符号化データは、ＭＰＥＧ１又はＭＰＥＧ２符号化ビデオデータの一部を形成する、方法。
【請求項４】
請求項１ないし３のうちいずれか１つに記載の方法であって、前記データは、２次元行列に構成される、方法。
【請求項５】
請求項４に記載の方法であって、前記２次元行列は、８×８行列である、方法。
【請求項６】
請求項１ないし５のうちいずれか１つに記載の方法であって、複数の１次元逆変換の２パス手法が適用される、方法。
【請求項７】
請求項６に記載の方法であって、各データグループは、初めに垂直逆変換が行われるか又は水平逆変換が行われるかによって、前記行列の列又は行とされる、方法。
【請求項８】
請求項６又は７に記載の方法であって、第２パスの逆変換ルーチンは、非ゼロ値グループの組み合わせに基づいて行われる、方法。
【請求項９】
請求項８に記載の方法であって、第２パスの処理実行可能コードの複数のバリエーションが予め記憶され、各バリエーションは、第１パスに存在する非ゼログループの組み合わせに対応し、前記コードは、どの係数に対して計算が行われるかを決める、方法。
【請求項１０】
請求項９に記載の方法であって、前記第２パスのコードは、非処理入力グループからのデータを無視するように適合化される、方法。
【請求項１１】
請求項１ないし５のうちいずれか１つに記載の方法であって、ダイレクト２次元実現形態が用いられる、方法。
【請求項１２】
請求項１１に記載の方法であって、前記ゼロとみなされるグループは、２次元ブロックの係数である、方法。
【請求項１３】
請求項４ないし１２のうちいずれか１つに記載の方法であって、前記ミスマッチ制御のために変更された係数は、最後の係数であり、前記行列の右下隅の係数である、方法。
【請求項１４】
請求項１ないし１３のうちいずれか１つに記載の方法であって、前記ミスマッチ制御のために変更された係数を含むデータグループの逆変換は、予め計算され前記逆変換を計算する際に用いられる、方法。
【請求項１５】
請求項１ないし１４のうちいずれか１つに記載の方法であって、各データグループの逆変換は、ミスマッチ変更を減らして、非ゼロ係数があるデータグループについて計算され、ミスマッチが呈されたときに、予め計算された出力値が当該変更された係数を有するデータグループのために用いられる、方法。
【請求項１６】
請求項１ないし１４のうちいずれか１つに記載の方法であって、非ゼロデータグループの数及びそれらの位置の各々は、当該グループのいずれかについての逆変換を行う前に判定され、非ゼログループ及びそれらの位置の状況によって、複数の可能なルーチンからルーチンが選択される、方法。
【請求項１７】
請求項１６に記載の方法であって、
・前記グループのサブセットの外に少なくとも１つの非ゼログループがある場合に、全てのグループにつき当該逆変換が計算され、
・前記サブセットの外に非ゼログループがない場合、当該逆変換は、前記サブセットに対して計算されその残りのグループについては計算されず、当該変更された係数が非ゼロである場合に、予め計算された値は、当該逆変換において当該変更係数の作用を再現するために用いられる、
方法。
【請求項１８】
請求項１７に記載の方法であって、前記サブセットは、第１の３つのグループを有する、方法。
【請求項１９】
請求項１７又は１８に記載の方法であって、前記ルーチンはさらに、
・当該非ゼロデータグループだけが前記第１のグループである場合に、当該逆変換は、当該非ゼロデータグループに対してのみ２次元で計算され、当該変更された係数が非ゼロである場合、当該変更係数が各出力値につき有する作用の予め計算された値が付加され、及び／又は
・当該ＤＣ係数だけが非ゼロである場合、全ての出力値は当該ＤＣ係数の値にセットされ、前記変更係数が非ゼロである場合、当該変更係数が各出力値につき有する作用の予め計算された値が付加される、
方法。
【請求項２０】
変換符号化データの逆変換を計算する手段を有する復号装置であって、前記符号化データは、係数のグループに構成され、少なくとも１つの係数は、ミスマッチを制御するように選択的に変更され、全体がゼロ値係数により構成されるグループに対して短縮された処理を施すように前記逆変換を選択的に行う手段がさらに設けられ、短縮された処理を施すかどうかを選択する目的で、包含される非ゼロ値係数だけがミスマッチ制御のために変更される係数である場合にデータグループがゼロ値グループとみなされる、装置。
【請求項２１】
請求項２０に記載の装置であって、前記変換符号化データは、離散コサイン変換符号化データである、装置。
【請求項２２】
請求項２１に記載の装置であって、前記離散コサイン変換符号化データは、ＭＰＥＧ２符号化ビデオデータの一部を形成する、装置。
【請求項２３】
請求項２０ないし２２のうちいずれか１つに記載の装置であって、前記データは、２次元行列に構成される、装置。
【請求項２４】
請求項２３に記載の装置であって、前記２次元行列は、８×８行列である、装置。
【請求項２５】
請求項２０ないし２４のうちいずれか１つに記載の装置であって、複数の１次元逆変換の２パス手法を適用する装置。
【請求項２６】
請求項２５に記載の装置であって、各データグループは、初めに垂直逆変換が行われるか又は水平逆変換が行われるかによって、前記行列の列又は行とされる、装置。
【請求項２７】
請求項２５又は２６に記載の装置であって、第２パスの逆変換ルーチンは、非ゼロ値グループの組み合わせに基づいて行われるように構成された装置。
【請求項２８】
請求項２７に記載の装置であって、第２パスの処理実行可能コードの複数のバリエーションを予め記憶する手段を有し、各バリエーションは、第１パスに存在する非ゼログループの組み合わせに対応し、前記コードは、どの係数に対して計算が行われるかを決める、装置。
【請求項２９】
請求項２８に記載の装置であって、前記第２パスのコードは、非処理入力グループからのデータを無視するように適合化される、装置。
【請求項３０】
請求項２０ないし２４のうちいずれか１つに記載の装置であって、ダイレクト２次元実現形態を用いるように構成された装置。
【請求項３１】
請求項３０に記載の装置であって、前記ゼロとみなされたグループは、２次元ブロックの係数である、装置。
【請求項３２】
請求項２３ないし３１のうちいずれか１つに記載の装置であって、前記ミスマッチ制御のために変更された係数は、最後の係数であり、前記行列の右下隅の係数である、装置。
【請求項３３】
請求項２０ないし３２のうちいずれか１つに記載の装置であって、前記ミスマッチ制御のために変更された係数を含むデータグループの逆変換を事前に計算する手段が設けられ、当該事前計算は、前記逆変換を計算する際に用いられる、装置。
【請求項３４】
請求項２０ないし３３のうちいずれか１つに記載の装置であって、ミスマッチ制御による変更を減らして当該係数のいずれかが非ゼロであるときのみデータグループの逆変換を計算する手段が設けられ、ミスマッチが呈されたときに予め計算された出力値が当該変更係数を有するデータグループのために用いられる、装置。
【請求項３５】
請求項２０ないし３３のうちいずれか１つに記載の装置であって、非ゼロデータグループの数及びそれらの位置の各々を、当該グループのいずれかの逆変換を行う前に判定する手段と、非ゼログループの数及びそれらの位置によって、複数の可能なルーチンからルーチンを選択する手段とを具備する装置。
【請求項３６】
請求項３５に記載の装置であって、
・前記グループのサブセットの外に少なくとも１つの非ゼログループがある場合に、全てのグループにつき当該逆変換が計算され、
・前記サブセットの外に非ゼログループがない場合、当該逆変換は、前記サブセットに対して計算されその残りのグループについては計算されず、当該変更された係数が非ゼロである場合に、予め計算された値は、当該逆変換において当該変更係数の作用を再現するために用いられる、
ように構成された装置。
【請求項３７】
請求項２６に記載の装置であって、前記サブセットは、第１の３つのグループを有する、装置。
【請求項３８】
請求項３６又は３７に記載の装置であって、
・当該非ゼロデータグループの数が１である場合に、当該逆変換は、当該非ゼロデータグループに対してのみ２次元で計算され、当該変更された係数が非ゼロである場合、当該変更係数が各出力値につき有する作用の予め計算された値が付加され、及び／又は
・ＤＣ係数だけが非ゼロである場合、全ての出力値は当該ＤＣ係数の値にセットされ、前記変更係数が非ゼロである場合、当該変更係数が各出力値につき有する作用の予め計算された値が付加される、
ように構成された装置。
【請求項３９】
プログラム可能な処理器に、請求項１ないし１９のうちいずれか１つに記載の方法のステップを行わせ又は請求項２０ないし３８のうちいずれか１つに記載の装置を実現させるプログラム命令を記録した記録担体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ符号化／復号に関し、特にミスマッチ制御が考慮されたＭＰＥＧビデオ復号のための逆離散コサイン変換の高速実施法のような逆変換の計算に関する。
【背景技術】
【０００２】
２次元８×８離散コサイン変換（ＤＣＴ）は、ＭＰＥＧ１及びＭＰＥＧ２ビデオ符号化のようなＭＰＥＧ（Moving Picture Expert Group）規格の中核に用いられる。ＤＣＴ（符号化に用いられるもの）と逆ＤＣＴ（復号に用いられるもの）の双方を素早く計算する方法が多数発表されている。しかし、これらは、その結果を素早く計算する数学的方法を説明するものである。
【０００３】
ＭＰＥＧ復号は、可変長復号、ＩＱ／ＤＣＴステージ及び動き復元フェーズなどの幾つかのパートを含む。ＩＱ及びＤＣＴフェーズは、２つの態様で用いられる。一方の態様は、いわゆる「イントラ」マクロブロック内のものであり、出力画像値がＤＣＴの出力により直接記述されるものであり、他方の態様は、「非イントラ」又は「インター」マクロブロック内のもので、ＤＣＴ出力が動き復元のトップにおける出力の付加により誤りを訂正するための項目として用いられる。
【０００４】
逆量子化（ＩＱ）ステージは、ビットストリームにおいて符号化された値を逆ＤＣＴ変換への入力のために用意される値に変換する。
【０００５】
ソフトウェアにおける２次元８×８ＩＤＣＴを実現する標準的な方法は、長さ８の複数の１次元ＩＤＣＴを用いることによるものである。これは、初めに１次元で（例えば上から下へと各行において）行われ、その後に他の次元において（例えば左から右へと各列において）行われる。この明細書全体を通して、ＩＤＣＴは初めに列データに対して作用し、その後に行について作用することを前提にしている。ただ、かかる方法は、順序を逆にして行う実現形態やダイレクト２次元ＩＤＣＴを用いた実現形態に適用可能となっている。
【０００６】
ゼロ値入力データがゼロ値出力データをもたらすことはＩＤＣＴの特質である。さらに、最初の（すなわち左上又はＣＤの）係数に近いほど係数は非ゼロになる可能性が高い。まさしく、左上の隅から離れた量子化された係数は、ゼロ又はゼロ近傍となる可能性が高いという事実のために、ＩＤＣＴがビデオ符号化に有益なのである。
【０００７】
ＩＤＣＴの実現形態の簡単なケースとして、入力値の全てのセットにつき完全な８×８変換を行うことが想定される。しかし、ＩＤＣＴ変換への既知の領域のゼロ入力データは無視されるようにして幾つかのソフトウェア実現形態がセットアップされることが知られている。大抵これは、どの方法を用いるべきかを判定する値の計算を可能とするＩＱループにおいて何らかのロジックを含むものである。
【０００８】
かかる２つの方法を以下に説明する。１つは、ルーピング方法であり、列ＩＤＣＴを列における係数の１つが非ゼロである場合にのみ計算するものである。この場合、１列を処理するように実行されるコードのセクションがあり、このコードは非ゼロ入力係数を有するそれら列について専ら実行される。
【０００９】
他の方法は、ＩＤＣＴが実行される前にＩＤＣＴルーチンの高度に最適化された多数のバージョンのうちの１つを用いるように判定がなされるものである。これらルーチンは、ゼロとみなされた係数列／行の種々の構成において異なる。この場合、予め定義されたルーチンのセットから、８×８ブロックを正しく変換することができ、どの列が非ゼロ係数を有するかの情報が与えられる最も素早いルーチンを選択する処理がある。
【００１０】
これらの例の方法のどちらも、全てゼロの係数の多数の列又は行があることを前提として、ＩＤＣＴ毎に行われなければならない動作（乗算や加算など）の数を減らす。
【００１１】
標準的用法においては、実行されるこれらＩＤＣＴタイプの各々の可能性が相当に高いと予想される。しかしながら、ＭＰＥＧ２ビデオ符号化においては、ミスマッチ制御として知られた特定の方法は、列の使用が非常に乏しい場合でも入力データセットの高い割合において最後の係数の最下位ビットを変える。ミスマッチ制御の作用は、当該符号化器がＩＤＣＴの入力における係数の合計が偶数の場合に最後の係数の最下位ビットを反転することである。
【００１２】
この係数は、逆に非ゼロ係数を含む可能性の最も低い列にある。上述した（列に対してルーピングする）最初の方法において、これは、ミスマッチビットがセットされた全てであっても最後の列が完全に処理されることになることを意味する。
【００１３】
２番目の方法が用いられると、デコーダは、最後の列が全てゼロである場合にのみ有益な最適化されたルーチンを使用することができないことが多い。この列は、（ミスマッチ制御とは別に）非ゼロ値を含む可能性が最も低いので、代表的ＭＰＥＧストリーム統計値に基づいて構成された沢山の最適化ルーチンは、この列がゼロとなる場合に専ら有益となる。当該ミスマッチビットの存在により、より高価なルーチンの使用が強制されることになる。
【００１４】
ミスマッチ制御の実施は、ＭＰＥＧ２規格に準拠するために必要とされる。その目的は、ＩＤＣＴの丸め誤差が動き予測を通じる前のものから各々が生じている画像のセットにわたり累積することを回避することである。ミスマッチ制御及びその実現についての説明は、例えば米国特許出願に係る文献のＵＳ６４５６６６３及びＵＳ５６０４５０２にある。しかしながら、どちらも上で明らかにした特定の問題に対処するものではない。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明の目的は、ミスマッチ状態を考慮に入れることによって簡略化しＩＤＣＴ演算などの逆変換の速度を向上することである。
【課題を解決するための手段】
【００１６】
本発明は、１つ目の態様において、変換符号化データの逆変換を計算する方法であって、前記符号化データは、係数のグループに構成され、少なくとも１つの係数は、ミスマッチを制御するように選択的に変更され、前記逆変換は、全体がゼロ値係数により構成されるグループに対して短縮された処理を施すように選択的に行われ、短縮された処理を施すかどうかを選択する目的で、包含される非ゼロ値係数だけがミスマッチ制御のために変更される係数である場合にデータグループがゼロ値グループとみなされる、方法を提供する。
【００１７】
当該変換符号化データは、例えばＭＰＥＧ２符号化ビデオデータの一部のとしての離散コサイン変換符号化データとすることができる。
【００１８】
かかるデータは、２次元の（例えば８×８の）行列に構成することができる。複数の１次元逆変換の２パス手法を適用してもよく、各データグループは、最初に垂直逆変換又は水平逆変換がなされたかどうかによって、当該行列の列又は行とすることができる。
【００１９】
非ゼロ値グループの組み合わせに基づいて第２パスの逆変換ルーチンを行ってもよい。これは、予め記憶された第２パスの処理実行可能コードの多数のバリエーションを持ち、各バリエーションが、第１パスに存在する非ゼログループの組み合わせに対応し、当該コードがどの係数につき計算が行われるかにつき決定するようにすることによって達成可能である。さらに、第２パスのコードは、未処理の入力グループからのデータを無視するように適合可能である。そうでない場合、列がゼロとみなされた場合に第２パスの前にメモリの列をクリアする必要がでてくる。
【００２０】
当該２パス手法に代えて、ダイレクト２次元の実施形態を用いてもよく、ゼロとみなされたグループは、２次元ブロックの係数とすることができる。ここでも、純粋にミスマッチ制御のために設定された係数は、省略された処理が適用されるかどうかを判定する目的で無視されることが可能である。
【００２１】
好ましくは、ミスマッチ制御のために変えられた係数は、最後の係数であり、当該行列の右下の隅にある係数である。
【００２２】
好適な実施例においては、ミスマッチ制御のために変えられた係数を含むデータグループの逆変換は、予め計算され逆変換を計算する際に用いられる。この予め計算された逆変換は、必要に応じて１次元又は２次元とされることになる。
【００２３】
第１の実施例において、各データグループの逆変換は、ミスマッチ制御のための変更をなす前に非ゼロ係数を含むデータグループのためだけに計算され、ミスマッチを呈した場合は、予め計算された出力値が当該変更された係数を有するデータグループのために用いられる。
【００２４】
計算を省略する決定がグループ毎に行われることは必須ではない。どのコースに従うかを決定する負担は、それ自体の費用をもたらすので、ある予め規定されたルーチンを定義することが好ましく、かかるルーチンはある範囲の条件について適用されるのがよい。
【００２５】
したがって代替実施例では、非ゼロデータグループの数及びそれらの位置の各々は、当該グループのいずれかについての逆変換が行われる前に決定され、非ゼログループの構成及びそれらの位置に応じて多数の可能なルーチンからルーチンが選択される。
【００２６】
１つの実施例においては、
・前記グループのサブセットの外に少なくとも１つの非ゼログループがある場合に、当該サブセットが第１の３つのグループを有する可能性を持ち、全てのグループにつき当該逆変換が計算され、
・前記サブセットの外に非ゼログループがない場合、当該逆変換は、前記サブセットに対して計算されその残りのグループについては計算されず、当該変更された係数が非ゼロである場合に、予め計算された値は、当該逆変換において当該変更係数の作用を再現するために用いられる。
【００２７】
これらルーチンは、さらに、次のようにさらに最適化されるようにしてもよい。すなわち、
・当該非ゼロデータグループだけが第１の列である場合に、当該逆変換は、当該非ゼロデータグループに対してのみ２次元で計算され、当該変更された係数が非ゼロである場合、当該変更係数が各出力値につき有する作用の予め計算された値が付加され、及び／又は
・当該ＤＣ（すなわち左上の）係数だけが非ゼロである場合、全ての出力値は当該ＤＣ係数の値にセットされ、前記変更係数が非ゼロである場合、当該変更係数が各出力値につき有する作用の予め計算された値が付加される、
というものである。
【００２８】
本発明の他の態様においては、変換符号化データの逆変換を計算する手段を有する復号装置であって、前記符号化データは、係数のグループに構成され、少なくとも１つの係数は、ミスマッチを制御するように選択的に変更され、全体がゼロ値係数により構成されるグループに対して短縮された処理を施すように前記逆変換を選択的に行う手段がさらに設けられ、短縮された処理を施すかどうかを選択する目的で、包含される非ゼロ値係数だけがミスマッチ制御のために変更される係数である場合にデータグループがゼロ値グループとみなされる、装置が提供される。
【００２９】
この装置に関する他の任意の特徴は、付記された請求項に記載されるようなものである。
【００３０】
本発明のさらに他の態様においては、プログラマブルプロセッサに上述した方法のステップを行わせるための又は上述したような装置を実現させるためのプログラム命令が記録されている記録担体が提供される。
【００３１】
以下、本発明の実施例を添付図面に基づき専ら例を挙げて説明する。
【発明を実施するための最良の形態】
【００３２】
図１は、本発明の実施例に用いられるＭＰＥＧデコーダを示している。このデコーダは、可変長デコーダ（ＶＬＤ）１１０（ｄｅｍｕｘＶＬＤ）、逆量子化器１１２（Ｑ−１）、逆離散コサイン変換（ＩＤＣＴ）処理１１４（ＩＤＣＴ）、動きバッファ１１６（ＭＢ）、加算処理１１８及びピクチャオーダリング処理１２０（ＰＯＲＤ）といった機能からなる。
【００３３】
通常は、ＭＰＥＧ符号化ビデオ（MPEG coded video）は、（しばしばバッファ（図示せず）を介して）ＶＬＤ１１０に供給され、量子化されたＤＣＴ係数に復号（デコード）され、逆量子化器１１２によって逆量子化される。これらＤＣＴ係数は、その後ＩＤＣＴ処理１１４に送られ、ここで当該係数について逆ディジタルコサイン変換を行って、空間画素データを出力する。これは、イントラフレームの場合、いずれもピクチャオーダリング処理部１２０に直接送られる。イントラフレームでない場合、動きバッファ１１６及び加算処理１１８により行われる動き補償がある。本説明は、ＩＤＣＴ処理１１４だけに関するものであり、デコーダの他の機能はこれ以上説明しない。
【００３４】
本説明を通じて、（複数１次元ＩＤＣＴの２段手法を用いた）ＩＤＣＴの１つの実現形態が説明される。この特許出願における幾つかの思想は、他の実現形態（ダイレクト２次元ＩＣＤＴなど）に適用可能である。
【００３５】
ＩＣＤＴを計算する最初の方法の例が図２に基づいて示される。これは、（（本例では）最初に行われる垂直変換として）列２０２，２０４，２０６に構成された８×８変換２００を示しており、各列は、８つの係数によって構成される。白い列２０２は、少なくとも１つの非ゼロ係数を含むもの（非ゼロ列）である。ハッチングされた列２０４は、全てゼロの係数を有するもの（ゼロ列）である。８番目の（塗り潰された）列２０６は、８行目にミスマッチ係数を含む（係数［７，７］の最下位ビットによりミスマッチが示される）。
【００３６】
ＤＣＴの特質により、当該変換の左上の隅［１，１］では非ゼロ係数となる可能性が最も高く、右下の隅に近づくにつれて可能性が低くなる。したがって、多くの変換は、列全体がゼロの部分が当該変換の右に偏った形を呈する。ゼロのＩＤＣＴはゼロなので、ゼロ列は完全なＩＤＣＴを必要としない。したがって、ゼロ列についてＩＤＣＴを行わないことにより、計算時間が短縮可能となる。
【００３７】
図２においては、４つの非ゼロ列２０２と３つのゼロ列２０４（列８は後で考察される）がある。ＩＤＣＴがこの変換について行われた場合、判定されているその列の出力の前に非ゼロ係数の存在についてチェックされる。非ゼロ列２０２に直面した場合、ＩＤＣＴはその列について行われ、その後に次の列がチェックされる。これに対し、ゼロ列２０４に直面した場合は、スキップ（省略）されてＩＤＣＴは行われない。その代わり、この列に対してその出力が単にゼロにセットされる。
【００３８】
今度は列８の２０６に移ると、これはミスマッチ係数（すなわちミスマッチ制御によりセットされた係数［７，７］）を含む。この列に対して係数データがない場合及びミスマッチがある場合、ミスマッチ係数は８番目の列において非ゼロ係数だけである。この位置については係数データがないので、この値はゼロか又は１である。いずれのケースも、列全体の出力値が予め計算される（そしてゼロの場合には自明にゼロとなる）。これは、多くのケースで見られるように、ミスマッチがセットされたとしても、この列に対してＩＤＣＴを計算する必要がないことを意味している。これにより、ミスマッチ制御なしでこの列が多くのケースでゼロになりがちであるので重要な節約が呈される。
【００３９】
図３は、上記方法のフローチャート図である。ステップ４００では、対象とされている列（ここでは第１列）がゼロ値列かどうかが判定される。ゼロ値列ではない場合、４０２においてＩＣＤＴがこの列につき行われる。ゼロ値列である場合、４０４で列出力がゼロにセットされる。４０６では、対象の列がインクリメントされる。４０８では、対象としている列が最終列であるかどうかが判定される。最終列でない場合、ステップ４００〜４０６がこの次の列につき繰り返される。一方、この列が最後であれば、ステップ４１０でこの列の状態が判定される。非ゼロ係数でミスマッチ係数以外の場合は、４１４でＩＤＣＴがこの列につき行われる。当該列がゼロならば、４１２において出力がゼロにセットされる。この列に対してミスマッチ係数だけがセットされていると、４１６において当該出力が予め計算された値にセットされる。
【００４０】
さらに、実際に存在する（すなわち非ゼロの）列の組み合わせに基づいて第２パスのルーチンを実行することにより効率的利用をなすことができる。これは、第２のパスをループとする第１のパスを行う上記方法と同様である。例えば列０，３及び４が専ら第１のパスにおいて処理された列ならば、第２パスの処理における演算の多くは不必要である。これは、多くの入力値（列１，２，５，６及び７に対するもの）がゼロであることを知っているからである。したがって、第１のパスにおいて実際に存在する列の色々な組み合わせについて記憶されたループコードについて多数のバリエーションを有することは、より良いことである。２５６のケース全てについてバリエーションを記憶させることは恐らく現実的ではない。多量のコードにかかわるＩキャッシュの問題を生じる可能性があるからである。これらのケースの多くはまずありえないと考えられるので、比較的少数のバリエーションだけの記憶により重要な利益を得ることができる。
【００４１】
さらに、完全な行処理が常に行われると、列がゼロとみなされる第１のパスの間にメモリの列をクリアする必要が出てくる。対照的に、第２パスのコードが未処理の入力列からのデータを無視するように選ばれる場合、当該値が使われることがないので、当該クリア動作は必要なく、効率的となる。
【００４２】
ＩＤＣＴを計算する第２の方法は、図４ａから図４ｄに関連して示される。この方法において、使用有（率）は、最初のステップのようにして決定される。非ゼロ列の数及び位置によって、ＩＤＣＴを計算するための特定のルーチンが用いられる。このようなルーチンは、例えば最初の（第１の）３つの列を処理することだけでよい。さらに、ミスマッチ係数はミスマッチがセットされ列使用が乏しい場合に専ら１のままなので、多数の異なる状況についてＩＤＣＴにつき有する作用を予め計算し、ＩＤＣＴを計算するときにこれらの予め計算されたものを用いることができる。なお、上述した第２パスのルーチンもこの方法に適用することができる。
【００４３】
この方法においては、最初の３つの外側に非ゼロ列があるかどうかが判定される。非ゼロ列があれば、完全なＩＤＣＴが従来通り計算される。このような状況は図４ａに描かれている。これは、列３の後に多数の非ゼロ列２０２がある状況を示している。したがって、列１及び５が非ゼロであるときなど、列３の後に単一の非ゼロ列しかない場合でも、完全なＩＤＣＴが計算される。
【００４４】
図４ｂは、列８の２０６がミスマッチをセットさせる可能性のあるものとして（本例では［７，７］）、２以上の非ゼロ列２０２があるものの最初の３列の外にはない場合の変換を示している。ここでは、最初の３つの列のＩＤＣＴだけが従来のように計算される。列４ないし７は、単にゼロにセットされるのに対して、列８の係数は、ミスマッチがセットされると当該予め計算された値にセットされる。
【００４５】
図４ｃは、第１の列２０２だけが非ゼロである場合の変換を示している。この場合、最初の（非ゼロの）列だけが、ＩＤＣＴを計算させる。そして水平ＩＤＣＴが計算されるが、これは、各行において最初の値に等しいという点で高速で自明なものである。そして、ミスマッチがセットされると、当該ミスマッチが各出力位置において呈する作用の予め計算された値が付加される。
【００４６】
図４ｄは、唯ひとつの非ゼロ係数４２０（［０，０］におけるＤＣ係数）を伴う変換を示している。この場合、全ての画素のＩＤＣＴは、スケール（倍率変更）された入力値と明らかに等しい。ここでミスマッチがセットされると、各出力は、この値と、当該ミスマッチがこの値について呈する作用のパーポジションの予め計算された値（per-position pre-calculated value）との合計値にセットされる。
【００４７】
図５は、この第２の方法のフローチャート図である。５００においては、（ミスマッチ係数＝１だけを含む場合に列をゼロとしてカウントして）最初の３つの外側に非ゼロ列があるかどうかが判定される。あれば、５０４において完全なＩＤＣＴが計算される。なければ、５０２において（ミスマッチ係数を引いて）非ゼロ列の数が１を超えるかどうかが判定される。超えていれば、５０６において、部分的なＩＤＣＴが最初の３つの列について行われ、次の４つの列は出力をゼロにセットする。５０８においては、ミスマッチ係数がセットされているか否かが判定される。セットされていなければ、５１２において列８の出力が０にセットされる。セットされていれば、５１０において当該出力が予め計算された値にセットされる。
【００４８】
一方、５０２において非ゼロ列の数が１であれば、ステップ５１４においてこの列において単一の非ゼロ係数だけがあるか否かが判定される。ないとすれば、列５１６においてこの列に対してＩＤＣＴが行われ、その後に水平ＩＤＣＴ５１８が続く。そして５２０においては、ミスマッチ係数がセットされているか否かが判定される。セットされていれば、５２２において当該予め計算された値が前に述べたように当該出力に付加される。
【００４９】
これに対して、５１４において単一の非ゼロ係数がある場合には、スケールされた入力５２４に当該出力がセットされ、５２６でミスマッチが判定され、見つかれば、５２８において当該出力がこれと前にも説明したような予め計算されたパーポジション値（per-position value）との和にセットされる。
【００５０】
なお、以上の説明は例を示したものに過ぎず、本発明の主旨及び範囲から逸脱することなく他の例や実施例が想定される。特に、当該計算の順序は任意であり、列の前に行を計算することができる。また、提示した第２の方法のルーチンも特定の例に過ぎず、他のルーチンも想定可能であるし、これらルーチンは、細かい部分（実行されるべき特定のルーチンに必要な非ゼロ列の数など）で異なるものとすることができる。
【００５１】
上述した複数１次元ＩＤＣＴの２段手法に代えて、ダイレクト２次元ＩＤＣＴ実現形態を用いてもよい。これにより、入力係数空間の一部をゼロとみなすことができる一定の場合となる。これにより、かなりの数学的冗長性が生じる（ゼロを乗じることは極めて有益ではない）。したがって、１次元の実現形態におけるように、種々の出力領域をゼロとみなすことができるケースが生じる。但しこの場合、それらを省略した行／列にする必要はないが、その代わり、（例えば）左上の４×４領域に存在する係数のような２次元ブロックとしてもよい。これらブロックは、１次元の実現形態に関連して説明したケースと同様に選択可能である。したがって、こうした例の如く、位置［７，７］における係数にあるミスマッチ設定ビットに対する規定をなしてもよい。
【図面の簡単な説明】
【００５２】
【図１】ＭＰＥＧデコーダのブロック図。
【図２】本発明の第１の方法を用いて行われるＩＤＣＴの前の８×８離散コサイン変換を示す図。
【図３】本発明の第１の方法のフローチャート図。
【図４ａ】本発明の第２の方法を用いて行われるＩＤＣＴの前の第１の８×８離散コサイン変換を示す図。
【図４ｂ】本発明の第２の方法を用いて行われるＩＤＣＴの前の第２の８×８離散コサイン変換を示す図。
【図４ｃ】本発明の第２の方法を用いて行われるＩＤＣＴの前の第３の８×８離散コサイン変換を示す図。
【図４ｄ】本発明の第２の方法を用いて行われるＩＤＣＴの前の第４の８×８離散コサイン変換を示す図。
【図５】本発明の第２の方法のフローチャート図。
【図１】
2007527055.tif 000003
【図２】
2007527055.tif 000004
【図３】
2007527055.tif 000005
【図４ａ】
2007527055.tif 000006
【図４ｂ】
2007527055.tif 000007
【図４ｃ】
2007527055.tif 000008
【図４ｄ】
2007527055.tif 000009
【図５】
2007527055.tif 000010
【国際調査報告】
2007527055.tif 000011
2007527055.tif 000012
2007527055.tif 000013