JP3977661B2 - Filter coefficient conversion method and filter coefficient conversion apparatus - Google Patents

Description

【００４４】
また、図２に示す通り、ハイパスフィルタＨ₁（ｚ）は、７タップに対応したフィルタ係数ｈ₁（−４），ｈ₁（−３），…，ｈ₁（１），ｈ₁（２）を有し、入力データ列とフィルタ係数ｈ₁（−４）〜ｈ₁（２）とを畳み込み演算する乗算器１３₁〜１３₇および加算器１４を有している。このハイパスフィルタＨ₁（ｚ）は、次式（２）に従って、奇数番目のデータＸ（２ｎ＋１）に関して選択的に畳み込み演算を実行し、データＹ（２ｎ＋１）を出力する。
【００４５】
【数２】

【００４６】
次に、ＩＤＷＴを実現するＦＩＲ型フィルタについて説明する。図２３に示した合成側のローパスフィルタＧ₀（ｚ）と、ハイパスフィルタＧ₁（ｚ）とをそれぞれｚ変換を用いて表現すると、次式（３），（４）のようになる。
【００４７】
【数３】

【００４８】
上式（３），（４）中、フィルタ係数ｇ₀（ｋ）（ｋ＝−３〜３）とｇ₁（ｋ）（ｋ＝−３〜５）とはインパルス応答を示し、また、ｚ^-kはｋ次の遅延を示している。
【００４９】
図２３に示した合成側のフィルタバンクは、以下に説明するポリフェーズ分解により変形されることができる。図３に、アップサンプラ３０とフィルタＧ（ｚ）との組み合わせを模式的に示す。フィルタＧ（ｚ）は、フィルタ係数ｈ（ｋ）（ｋ：整数）を有するＦＩＲ型フィルタである。アップサンプラ３０は、入力信号ｙ（ｎ）の各値の間にゼロ値を挿入するアップサンプリング処理を行い、フィルタＧ（ｚ）は、そのアップサンプラ３０からの出力データを補間した信号ｘ（ｎ）を出力する。フィルタＧ（ｚ）は、ｚ変換を用いた伝達関数で、Ｇ（ｚ）＝Ｒ₀（ｚ²）ｚ^-1＋Ｒ₁（ｚ²）の形に変形され得る。このような表現は「タイプ２のポリフェーズ分解」と呼ばれている。２フェーズに分解された各フィルタＲ₀（ｚ²），Ｒ₁（ｚ²）は、「ポリフェーズフィルタ」と呼ばれる。
【００５０】
以上のフィルタのポリフェーズ表現に基づくと、ＦＩＲ型フィルタＧ（ｚ）は、図４に示すように、２つのポリフェーズフィルタＲ₀（ｚ²），Ｒ₁（ｚ²）と遅延素子３２と加算器３３とで表現される。すなわち、第１のポリフェーズフィルタＲ₀（ｚ²）の出力信号は、遅延素子３２で１周期遅延した後に、加算器３３において第２のポリフェーズフィルタＲ₁（ｚ²）の出力信号と加算される。更に、図４のフィルタ構成は、図５に示すフィルタ構成と等価である。従って、出力信号ｘ（ｎ）は、各フィルタＲ₀（ｚ），Ｒ₁（ｚ）の出力信号を交互に出力したものといえる。
【００５１】
ところで、図２３に示した合成側のローパスフィルタＧ₀（ｚ）とハイパスフィルタＧ₁（ｚ）とは、ｚ変換を用いた伝達関数で次式（３Ａ），（４Ａ）のように変形され得る。
【００５２】
【数４】

【００５３】
上式（３Ａ）中、Ｒ₀（ｚ²），Ｒ₁（ｚ²）は、合成側ローパスフィルタＧ₀（ｚ）を構成するポリフェーズフィルタを示し、上式（４Ａ）中、Ｋ₀（ｚ²），Ｋ₁（ｚ²）は、合成側ハイパスフィルタＧ₁（ｚ）を構成するポリフェーズフィルタを示している。
【００５４】
よって、前述のポリフェーズ表現に基づくと、図６に示す合成側のフィルタバンクは、図７に示すフィルタ構成に変形され得る。図６，図７において、符号３４，３５，３４Ａ，３４Ｂ，３５Ａ，３５Ｂはアップサンプラを示しており、符号３６，３８，４０は加算器、３７，３９は遅延素子を示している。
【００５５】
従って、ローパスフィルタ側の加算器３８の出力信号ｘ₀（ｎ）は、各ポリフェーズフィルタＲ₀（ｚ），Ｒ₁（ｚ）の出力信号ｒ₀，ｒ₁を交互に出力したものとなり、ハイパスフィルタ側の加算器４０の出力信号ｘ₁（ｎ）は、各ポリフェーズフィルタＫ₀（ｚ），Ｋ₁（ｚ）の出力信号ｋ₀，ｋ₁を交互に出力したものとなる。この結果、加算器３６の出力信号ｘ（ｎ）のうち、偶数番目の出力信号ｘ（２ｋ）は、各ポリフェーズフィルタＲ₀（ｚ），Ｋ₀（ｚ）の出力信号の和ｒ₀＋ｋ₀とし、奇数番目の出力信号ｘ（２ｋ＋１）は、各ポリフェーズフィルタＲ₁（ｚ），Ｋ₁（ｚ）の出力信号の和ｒ₁＋ｋ₁とすることができる。
【００５６】
以上のポリフェーズ表現に従って、合成側のフィルタバンクを実現するＦＩＲ型フィルタを構成できる。図８および図９は、合成側のＦＩＲ型フィルタの構成を示す模式図である。これらＦＩＲ型フィルタは、フィルタ処理とアップサンプリング処理とを同時並行に実行する。また、これらＦＩＲ型フィルタには、圧縮画像２０を構成するデータ列…，Ｙ（２ｎ−３），Ｙ（２ｎ−２），…，Ｙ（２ｎ＋４），Ｙ（２ｎ＋５），…が入力している。
【００５７】
図８に示す７タップのＦＩＲ型フィルタは、上記各ポリフェーズフィルタＲ₀（ｚ²），Ｋ₀（ｚ²）のフィルタ係数ｇ₀（−２），ｇ₀（０），ｇ₀（２），ｇ₁（−２），ｇ₁（０），ｇ₁（２），ｇ₁（４）を使用し、これらフィルタ係数と入力データ列とを畳み込み演算する乗算器２１₀，２１₁，…，２１₆および加減算器２２を有している。このＦＩＲ型フィルタは、次式（５）に従って畳み込み演算を実行して偶数番目のデータＸ（２ｎ）を合成する。
【００５８】
【数５】

【００５９】
また、図９に示す９タップのＦＩＲ型フィルタは、上記各ポリフェーズフィルタＲ₁（ｚ²），Ｋ₁（ｚ²）のフィルタ係数ｇ₀（−３），ｇ₀（−１），ｇ₀（１），ｇ₀（３），ｇ₁（−３），ｇ₁（−１），ｇ₁（１），ｇ₁（３），ｇ₁（５）を使用し、これらフィルタ係数と入力データ列とを畳み込み演算する乗算器２３₁，…，２３₉および加算器２４を有している。このＦＩＲ型フィルタは、次式（６）に従って畳み込み演算を実行して奇数番目のデータＸ（２ｎ＋１）を合成する。
【００６０】
【数６】

【００６１】
チェス盤歪みの回避条件．
次に、上記チェス盤歪みの回避条件について説明する。図３において、フィルタへの入力信号ｙ（ｎ）として単位ステップ信号が印加されるとき、出力信号ｘ（ｎ）は、フィルタＧ（ｚ）のインパルス応答ｈ（ｋ）の総和であり、この総和は時間経過と共に一定値に収束することが望ましい。一方、図５において、入力信号ｙ（ｎ）に対応する出力信号ｘ（ｎ）は、各ポリフェーズフィルタＲ₀（ｚ），Ｒ₁（ｚ）の出力信号を交互に出力したものに等しい。入力信号ｙ（ｎ）として単位ステップ信号が印加されるとき、各ポリフェーズフィルタＲ₀（ｚ），Ｒ₁（ｚ）のインパルス応答の総和が交互に出力される。従って、各ポリフェーズフィルタＲ₀（ｚ），Ｒ₁（ｚ）のインパルス応答の総和が相違する場合は、ｎの値に応じて交互に異なる値が出力され、一定値に収束しないという現象が起きる。チェス盤歪みはこの種の現象を表していると考えられる。
【００６２】
従って、チェス盤歪みの回避条件は、少なくとも、各ポリフェーズフィルタのＲ₀（ｚ），Ｒ₁（ｚ）のインパルス応答の総和が一致することである。
【００６３】
フィルタ係数変換処理．
次に、本発明の第１の実施の形態に係るフィルタ係数変換方法とその装置について説明する。図１０は、本実施の形態に係るフィルタ係数変換装置１の概略構成を示す機能ブロック図である。このフィルタ係数変換装置１は、外部から入力する実数型フィルタ係数５を分数に丸め込み表現した値（＝Ｎ／２^M；Ｎ，Ｍは１以上の整数）の分母（＝２^M）の次数Ｍを決定する次数決定手段２と、その分子Ｎの整数値を選択して分解側の整数型のフィルタ係数（丸め込み値）６を出力する丸め込み値選択手段３と、合成側の整数型フィルタ係数を算出する係数算出手段３Ａと、入力する分解側および合成側の整数型フィルタ係数が所定条件を満たすか否かを判定する条件判定手段４と、を備えて構成されている。尚、実数型フィルタ係数５を丸め込み表現した値（＝Ｎ／２^M）は１０進表現の値であり、実際の処理では、当該値はデジタル値で表現される。
【００６４】
以上の構成を有するフィルタ係数変換装置１を用いた分解側フィルタ係数の変換処理を、図１１のフローチャートを参照しつつ以下に詳説する。この変換処理では、分解側ローパスフィルタＨ₀（ｚ）のフィルタ係数が整数型の値に変換される。変換元の実数型フィルタとしては、９×７タップのドビシス（Daubechies）フィルタを採用することができる。以下の表１，表２に、ドビシスフィルタのフィルタ係数＜ｈ₀（ｎ）＞，＜ｈ₁（ｎ）＞，＜ｇ₀（ｎ）＞，＜ｇ₁（ｎ）＞を示す。＜ｈ＞は、フィルタ係数ｈが実数型係数であることを表す記号である。
【００６５】
【表１】

【００６６】
【表２】

【００６７】
ステップＳＴ１では、このフィルタ係数変換装置１に、実数型フィルタ係数＜ｈ₀（ｎ）＞が入力する。入力したフィルタ係数＜ｈ₀（ｎ）＞は、次数決定手段２と丸め込み値選択手段３とにそれぞれ伝達する。続くステップＳＴ２では、次数決定手段２は、入力した実数型フィルタ係数＜ｈ₀（ｎ）＞を丸め込み表現した値（＝Ｎ₀（ｎ）／２^M＝ｈ₀（ｎ））の分母（＝２^M）の次数Ｍを決定し、その値Ｍを丸め込み値選択手段３に出力する。
【００６８】
丸め込み値選択手段３は、ｎ番目の丸め込み値（＝Ｎ₀（ｎ）／２^M）の番号ｎがゼロ値の場合は、ステップＳＴ３，ＳＴ４の処理を実行し、番号ｎがゼロ値以外の場合は、ステップＳＴ５，ＳＴ６の処理を実行する。ステップＳＴ３では、整数型フィルタ係数の系列のうち中央位置の丸め込み値ｈ₀（０）に着目し、この丸め込み値ｈ₀（０）の分子Ｎ₀（０）が偶数であり、且つ、丸め込み値ｈ₀（０）と当該実数型フィルタ係数＜ｈ₀（０）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ₀（０）を選択する。続くステップＳＴ４では、選択した分子Ｎ₀（０）を当該分母２^Mで除算した丸め込み値ｈ₀（０）が算出される。
【００６９】
一方、ステップＳＴ５では、整数型フィルタ係数の系列のうち中央位置の丸め込み値ｈ₀（ｎ）（ｎ：ゼロ以外の整数）に着目し、この丸め込み値ｈ₀（ｎ）と当該実数型フィルタ係数＜ｈ₀（ｎ）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ₀（ｎ）を選択する。整数値Ｎ₀（ｎ）は必ずしも偶数である必要はない。続くステップＳＴ６では、選択した分子Ｎ₀（ｎ）を当該分母２^Mで除算した丸め込み値ｈ₀（ｎ）が算出される。
【００７０】
以上のようにステップＳＴ４，ＳＴ６において、丸め込み値選択手段３が整数型フィルタ係数ｈ₀（ｎ）を条件判定手段４に出力した後、条件判定手段４は、ステップＳＴ７以後の処理を実行する。ステップＳＴ７では、分解側ローパスフィルタＨ₀（ｚ）のインパルス応答ｈ₀（ｎ）の総和の絶対値を示すＤＣ成分Ｇ_DCを算出し、当該ＤＣ成分Ｇ_DCが所定値に一致するという規格化条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用する場合、ＤＣ成分Ｇ_DCの値は「１」に一致しなければならない。ＤＣ成分Ｇ_DCの算出式は、次式（７）の通りである。
【００７１】
【数７】

【００７２】
前記ステップＳＴ７で規格化条件が満たされていた場合は、ステップＳＴ８に処理が移行し、規格化条件が満たされていなかった場合は、ステップＳＴ９で規格化条件を満たすように規格化が行われた後に、ステップＳＴ８に処理が移行する。
【００７３】
次のステップＳＴ８では、係数算出手段３Ａは、分解側フィルタと合成側フィルタとが双直交性を満たすという双直交条件を用いて、合成側のハイパスフィルタＧ₁（ｚ）の整数型フィルタ係数ｇ₁（ｎ）を算出し、条件判定手段４に出力する。その双直交条件は次式（８）の通りである。
【００７４】
【数８】

【００７５】
ステップＳＴ１０では、条件判定手段４において、前記ステップＳＴ８で算出された合成側フィルタ係数ｇ₁（ｎ）を用いて、合成側のハイパスフィルタＧ₁（ｚ）を構成する各ポリフェーズフィルタＫ₀（ｚ²），Ｋ₁（ｚ²）のインパルス応答の総和の絶対値が一致するという束縛条件が成立するか否かが判定される。この束縛条件は、ハイパスフィルタＧ₁（ｚ）の偶数番目のフィルタ係数の総和の絶対値と奇数番目のフィルタ係数の総和の絶対値とが一致することと同じである。ＪＰＥＧ２０００方式を採用した場合は、当該束縛条件に、更に、その総和の絶対値が１／２になる条件が付加される。ＪＰＥＧ２０００方式を採用した場合の束縛条件は次式（９）の通りである。
【００７６】
【数９】

【００７７】
前記ステップＳＴ１０で束縛条件が成立していなかった場合は、条件判定手段４は、当該整数型フィルタ係数ｈ₀（ｎ），ｇ₁（ｎ）の算出に失敗したとみなし、本フィルタ係数変換処理は終了する。他方、前記ステップＳＴ１０で束縛条件が成立していた場合は、次のステップＳＴ１１に処理が移行し、条件判定手段４は、整数型フィルタ係数ｈ₀（ｎ），ｇ₁（ｎ）を確定して出力する。
【００７８】
以上のフィルタ係数変換処理により、９×７タップのドビシスフィルタのフィルタ係数を変換した係数値ｈ₀（ｎ），ｇ₁（ｎ）を、それぞれ以下の表３，表４に示す。
【００７９】
【表３】

【００８０】
【表４】

【００８１】
次に、分解側ハイパスフィルタＨ₁（ｚ）のフィルタ係数の変換処理を、図１２のフローチャートを参照しつつ以下に詳説する。先ず、ステップＳＴ２０では、上記フィルタ係数変換装置１に、実数型フィルタ係数＜ｈ₁（ｎ）＞が入力する。入力したフィルタ係数＜ｈ₁（ｎ）＞は、次数決定手段２と丸め込み値選択手段３とにそれぞれ伝達する。続くステップＳＴ２１では、次数決定手段２は、入力した実数型フィルタ係数＜ｈ₁（ｎ）＞を丸め込み表現した値（＝Ｎ₁（ｎ）／２^M＝ｈ₁（ｎ））の分母（＝２^M）の次数Ｍを決定し、その値Ｍを丸め込み値選択手段３に出力する。
【００８２】
丸め込み値選択手段３は、ｎ番目の丸め込み値（＝Ｎ₁（ｎ）／２^M）の番号ｎがゼロ値の場合は、ステップＳＴ２２，ＳＴ２３の処理を実行し、番号ｎがゼロ値以外の場合は、ステップＳＴ２４，ＳＴ２５の処理を実行する。ステップＳＴ２２では、丸め込み値ｈ₁（ｎ）の分子Ｎ₁（−１）が偶数であり、且つ、丸め込み値ｈ₁（−１）と当該実数型フィルタ係数＜ｈ₁（−１）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ₁（−１）を選択する。続くステップＳＴ２３では、選択した分子Ｎ₁（−１）を当該分母２^Mで除算した丸め込み値ｈ₁（−１）が算出される。
【００８３】
一方、ステップＳＴ２４では、丸め込み値ｈ₁（ｎ）（ｎ：−１以外の整数）と当該実数型フィルタ係数＜ｈ₁（ｎ）＞との差分絶対値が最小となるという条件を満たす整数値Ｎ₁（ｎ）を選択する。その整数値Ｎ₁（ｎ）は必ずしも偶数である必要はない。続くステップＳＴ２５では、選択した分子Ｎ₁（ｎ）を当該分母２^Mで除算した丸め込み値ｈ₁（ｎ）が算出される。
【００８４】
以上のようにステップＳＴ２３，ＳＴ２５において、丸め込み値選択手段３が整数型フィルタ係数ｈ₁（ｎ）を条件判定手段４に出力した後、条件判定手段４は、ステップＳＴ２６以後の処理を実行する。ステップＳＴ２６では、プラスマイナス１の値を交互にとる交番信号が印加された場合の分解側ハイパスフィルタＨ₁（ｚ）の応答の総和の絶対値（以下、ナイキスト成分Ｄ_Nyquistと呼ぶ。）を算出し、当該ナイキスト成分Ｄ_Nyquistが所定値に一致するという規格化条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用する場合は、ナイキスト成分Ｄ_Nyquistの値は「２」に一致しなければならない。このナイキスト成分Ｄ_Nyquistの算出式は、次式（１０）の通りである。
【００８５】
【数１０】

【００８６】
前記ステップＳＴ２６で規格化条件が満たされていた場合は、ステップＳＴ２７に処理が移行し、規格化条件が満たされていなかった場合は、ステップＳＴ２８で規格化条件を満たすように規格化が行われた後に、ステップＳＴ２７に処理が移行する。
【００８７】
次のステップＳＴ２７では、分解側フィルタと合成側フィルタとが双直交性を満たすという双直交条件（上式（８））を用いて、合成側のローパスフィルタＧ₀（ｚ）の整数型フィルタ係数ｇ₀（ｎ）が算出される。
【００８８】
次のステップＳＴ２９では、前記ステップＳＴ２７で算出された合成側フィルタ係数ｇ₀（ｎ）を用いて、合成側のローパスフィルタＧ₀（ｚ）を構成する各ポリフェーズフィルタＲ₀（ｚ²），Ｒ₁（ｚ²）のインパルス応答の総和が一致するという束縛条件が成立するか否かが判定される。ＪＰＥＧ２０００方式を採用した場合は、当該束縛条件に、更に、その総和が「１」になる条件が付加される。ＪＰＥＧ２０００方式を採用した場合の束縛条件は次式（１１）の通りである。
【００８９】
【数１１】

【００９０】
この束縛条件が成立するとき、各ポリフェーズフィルタのインパルス応答の総和が一致するため、上述した通り、復号化画像中のチェス盤歪みを回避することが可能となる。
【００９１】
前記ステップＳＴ２９で束縛条件が成立していなかった場合は、条件判定手段４は、当該整数型フィルタ係数ｈ₁（ｎ），ｇ₀（ｎ）の算出に失敗したとみなし、本フィルタ係数変換処理は終了する。他方、前記ステップＳＴ２９で束縛条件が成立していた場合は、次のステップＳＴ３０に処理が移行し、条件判定手段４は、整数型フィルタ係数ｈ₁（ｎ），ｇ₀（ｎ）を確定して出力する。
【００９２】
以上のフィルタ係数変換処理に従って、９×７タップのドビシスフィルタのフィルタ係数を変換し、その結果得られた整数型の係数値ｈ₁（ｎ），ｇ₀（ｎ）を以下の表５，表６に示す。
【００９３】
【表５】

【００９４】
【表６】

【００９５】
以上の通り、この第１の実施の形態では、上記ステップＳＴ２９（図１２）で、ローパスフィルタを構成する各ポリフェーズフィルタのインパルス応答の総和が一致するという条件が成立するか否かの判定処理を行っている。このため、ＩＤＷＴで低域成分を合成する際に当該低域成分にチェス盤歪みが混入しないように、比較的低いビット精度で、高精度の整数型フィルタ係数を算出できる。
【００９６】
また、上記ステップＳＴ１０（図１１）では、ハイパスフィルタを構成する各ポリフェーズフィルタのインパルス応答の総和の絶対値が一致するという条件が成立するか否かの判定処理が行われている。このため、分解側と合成側の各フィルタの構成要件を満たしつつ、チェス盤歪みを回避できるように高精度の整数型フィルタ係数を算出できる。
【００９７】
更に、上記ステップＳＴ３（図１１）とステップＳＴ２２（図１２）とでは、整数型フィルタ係数の系列のうち、中央の値に相当するｈ₀（０），ｈ₁（−１）の分子が共に偶数に選択される。このため、整数型フィルタ係数をより高い精度で算出できる。
【００９８】
従って、ソフトウェアまたはハードウェアにおいて、上記整数型フィルタ係数を用いて固定小数点演算でＤＷＴとＩＤＷＴとを効率良く実行することが可能となる。特にハードウェアを採用する場合は、全ての整数型フィルタ係数の分母が共通の２の巾乗をもつことから、除算処理をビットシフト演算で効率良く行うことができる。従って、入出力ピンの数が少ない小回路規模のハードウェア構成を実現することが可能である。
【００９９】
第２の実施の形態．
次に、本発明の第２の実施の形態について説明する。本実施の形態に係るリフティング係数変換方法とその装置は、リフティング構成を使用したＤＷＴおよびＩＤＷＴに適用される方法と装置である。最初に、リフティング構成を概説した後に、本実施の形態に係るリフティング係数変換処理を説明する。
【０１００】
リフティング構成．
図１３は、１ステージのみ（１次の分解レベルのみ）のＤＷＴとＩＤＷＴとを実現するフィルタ構成を示す図である。このような構成によるＤＷＴはポリフェーズＤＷＴと呼ばれている。図１３中、符号４１，４６は遅延素子、４２，４３はダウンサンプラ、４４，４５はアップサンプラを示している。また、図中のＰ_c（ｚ），Ｐ（ｚ）^-1はポリフェーズ行列と称されている。
【０１０１】
順変換においては、入力データＸ（ｋ）（ｋ：整数）は、分岐してダウンサンプラ４２と遅延素子４１とに伝達し、ダウンサンプラ４２は偶数番目のデータＸ（２ｎ＋４）（ｎ：整数）を出力し、一方、遅延素子４１の出力信号をダウンサンプリングするダウンサンプラ４３は、奇数番目のデータＸ（２ｎ＋３）を出力する。すなわち、入力データＸ（ｋ）は、偶数番目のデータＸ（２ｎ＋４）と奇数番目のデータＸ（２ｎ＋３）とに分離されて、ポリフェーズ行列Ｐ_c（ｚ）に入力することになる。このポリフェーズ行列Ｐ_c（ｚ）からは、低域成分（ＬＰ）Ｙ（２ｎ）と高域成分（ＨＰ）Ｙ（２ｎ＋１）とが出力される。
【０１０２】
他方、逆変換においては、ポリフェーズ行列Ｐ（ｚ）^-1は、入力データＹ（２ｎ），Ｙ（２ｎ＋１）に対して、ポリフェーズ行列Ｐ（ｚ）の逆変換を実行し、データＸ（２ｎ−２），Ｘ（２ｎ−３）を復元して出力する。偶数番目のデータＸ（２ｎ−２）はアップサンプラ４４と遅延素子４６とを経て加算器４７に伝達し、奇数番目のデータＸ（２ｎ−３）はアップサンプラ４５を経て加算器４７に伝達し、加算器４７は元のデータＸ（ｋ）を合成する。
【０１０３】
順変換のポリフェーズ行列Ｐ_c（ｚ）と逆変換のポリフェーズ行列Ｐ（ｚ）^-1は、リフティング構成と称する手法で構築できる。リフティング構成については、例えば、文献「W.Sweldens, I. Daubechies, "Factoring Wavelet Transforms into Lifting Steps", J. Fourier Anal., Vol.4, No.3, pp.247-269, 1998」に記述されている。
【０１０４】
順変換は図１４に示すリフティング構成で実現され、逆変換は図１５に示すリフティング構成で実現される。図１４中、符号５１，５３，５８，５９はｚ変換形式の伝達関数で表される２タップのＦＩＲ型フィルタを示しており、符号５４，５６，６０は遅延素子、６２は入力信号に係数１／κを乗算して出力する乗算器、６３は入力信号に係数κを乗算して出力する乗算器、５２，５５，５７は加算器、を示している。
【０１０５】
また、図１５中、符号７２，７５，７８，８１はｚ変換形式の伝達関数で表される２タップのＦＩＲ型フィルタを示しており、符号７０は入力信号に係数κを乗算して出力する乗算器、７１は入力信号に係数１／κを乗算して出力する乗算器、７４，７７，８０は遅延素子、７３，７６，７９，８２は減算器、を示している。
【０１０６】
図１４と図１５に現れる係数α，β，γ，δ，κは、リフティング係数と呼ばれており、９×７タップのドビシスフィルタのリフティング構成では実数型の値をもつ。
【０１０７】
また、図１４に示す分解側リフティング構成により、入力データＸ（ｋ）は、奇数番目のデータＸ（２ｎ＋３）と偶数番目のデータＸ（２ｎ＋４）とに分解される。また、中間データＹ’（２ｎ＋３），Ｙ’’（２ｎ＋２），Ｙ’’’（２ｎ＋１），Ｙ’’’’（２ｎ）が次々と生成されて、最終的にデータＹ（２ｎ），Ｙ（２ｎ＋１）が出力される。この分解側リフティング構成は、図１６に示すように、データを示す黒点と、各黒点間を結ぶ線分とからなるツリー図で表現することができる。各黒点近傍には、当該黒点を示すデータが表示されている。例えば、左端の各黒点に対応して、それぞれ、入力データ列Ｘ（２ｎ），Ｘ（２ｎ＋１），…，Ｘ（２ｎ＋４）が表示されている。また、各黒点間を結ぶ線分の近傍には係数が表示されている。例えば、データＸ（２ｎ）を示す黒点とデータＹ’（２ｎ＋１）を示す黒点との間の線分近傍には係数αが表示されている。
【０１０８】
図１６に示す分解側リフティング構成は、次の規則（Ａ），（Ｂ），（Ｃ）に基づいて解釈されるものである。（Ａ）黒点を示すデータは、左方から右方へ延びる線分に沿って伝達する。（Ｂ）黒点間を結ぶ線分は、当該線分を伝達するデータに当該係数を乗算する。（Ｃ）黒点は、各線分に沿って左方から入力するデータを加算して右方へ延びる線分に出力する。従って、その分解側リフティング構成は次式（１２）と等価である。
【０１０９】
【数１２】

【０１１０】
また、図１５に示す合成側リフティング構成により、入力データ列Ｙ（２ｎ＋４），Ｙ（２ｎ＋５）に対して、中間データＸ’’’（２ｎ＋４），Ｘ’’（２ｎ＋５），…が次々と生成されて、最終的に合成データＸ（ｋ）が出力される。この合成側リフティング構成も、図１７に示す黒点と線分とからなるツリー図で表現することが可能であり、次式（１３）と等価である。
【０１１１】
【数１３】

【０１１２】
９×７タップのドビシスフィルタのリフティング構成を採用した場合のリフティング係数α，β，γ，δ，κの正確な値を次式（１４）に示す。
【０１１３】
【数１４】

【０１１４】
また、以下の表７に、ドビシスフィルタの分解側フィルタ係数ｈ₀（ｎ），ｈ₁（ｎ）をリフティング係数α，β，γ，δ，κ，１／κで構成したものを示し、以下の表８に、ドビシスフィルタの合成側フィルタ係数ｇ₀（ｎ），ｇ₁（ｎ）をリフティング係数α，β，γ，δ，κ，１／κで構成したものを示す。
【０１１５】
【表７】

【０１１６】
【表８】

【０１１７】
リフティング係数変換処理．
次に、本発明の第２の実施の形態に係るリフティング係数変換方法とその装置について説明する。図１８は、本実施の形態に係るリフティング係数変換装置９０の概略構成を示す機能ブロック図である。このリフティング係数変換装置９０は、外部から入力する実数型リフティング係数を分数に丸め込み表現した値（＝Ｎ／２^M；Ｎ，Ｍは１以上の整数）の分母（＝２^M）の次数Ｍを決定する次数決定手段９１と、後述する評価式に基づいてその分子Ｎの整数値を探索する係数評価手段９３と、この係数評価手段９３に対して探索範囲を指示する探索範囲決定手段９２と、係数評価手段９３から出力された整数型リフティング係数を抽出する係数抽出手段９４と、を備えて構成されている。
【０１１８】
以上の構成を有するリフティング係数変換装置９０を用いたリフティング係数の変換処理を、図１９のフローチャートを参照しつつ以下に詳説する。最初のステップＳＴ１では、変換元の実数型リフティング係数がリフティング係数変換装置９０に入力する。次数決定手段９１は、実数型リフティング係数α，β，γ，δ，κ，１／κの各々について丸め込み表現した値（＝Ｎ／２^M）の分母（＝２^M）の次数Ｍを決定し、その値Ｍを係数評価手段９３に出力する。併行して、探索範囲決定手段９２は、各実数型リフティング係数の探索範囲を決定して係数評価手段９３に出力する。
【０１１９】
次のステップＳＴ４１Ａ以後において、係数評価手段９３は、指定された探索範囲内で、後述する評価式の値（以下、評価値と呼ぶ。）と、この値に対応する整数型リフティング係数とを算出する。すなわち、ステップＳＴ４１Ａ〜ＳＴ４６Ａと、ステップＳＴ４１Ｂ〜４６Ｂとの間でループを形成し、指定された探索範囲で整数型リフティング係数α，β，γ，δ，κ，１／κの分子を小刻みに順次変化させる。そして、ステップＳＴ４７では、そのループにおいて変化させた整数型リフティング係数の全ての組み合わせについて、以下に説明する評価値が算出される。
【０１２０】
上記の表８，表９によれば、上式（９）は次式（１５）のように表される。
【０１２１】
【数１５】

【０１２２】
また、上式（１１）は次式（１６）のように表される。
【０１２３】
【数１６】

【０１２４】
前記評価式は、上式（１５）の中辺の値と右辺の値との差分絶対値の和と，（１６）の中辺の値と右辺の値との差分絶対値の和とを加算したものであり、次式（１７）で表現される。
【０１２５】
【数１７】

【０１２６】
次のステップＳＴ４８では、係数抽出手段９４は、前記係数評価手段９３から入力する評価値の組み合わせのうち、最小の評価値をとる整数型リフティング係数の組み合わせ（α，β，γ，δ，κ，１／κ）を確定して出力する。ここで、上記したＤＣ成分Ｇ_DCおよびナイキスト成分Ｄ_Nyquistがそれぞれ所定値をとるという条件が成立するか否かを判定してもよい。
【０１２７】
以上のリフティング係数変換処理の計算結果の例を、以下の表９，表１０，表１１に示す。表９および表１１の中の「範囲」は、上記探索範囲の変動幅の上下限値を示している。すなわち、上記探索範囲は、実数型リフティング係数から下限値を引いた値から、同実数型リフティング係数に上限値を足した値までの範囲である。例えば、表９に示す次数Ｍ＝５に対応する変動幅の上下限値は「±１」であるから、係数αの探索範囲は、＜α＞−１から＜α＞＋１、となる（但し、＜α＞は実数型リフティング係数）。本例では、各分母の次数Ｍの値に応じて、全ての整数型リフティング係数に共通の探索範囲が設定されている。表９と表１０は分離して表示されているが、各次数Ｍに対応する探索範囲は同じである。また、表１１中の「評価式」の値は上記評価値を意味している。
【０１２８】
【表９】

【０１２９】
【表１０】

【０１３０】
【表１１】

【０１３１】
以上の通り、この第２の実施の形態では、評価値がゼロ値に近くなるように整数型フィルタ係数が選択されることで、比較的低いビット精度で、チェス盤歪みを低減し得る高精度の整数型フィルタ係数を算出することが可能となる。
【０１３２】
【発明の効果】
以上の如く、本発明の請求項１に係るフィルタ係数変換方法および請求項７に係るフィルタ係数変換装置によれば、上記工程（ｄ）および条件判定手段により、合成側の各ポリフェーズフィルタのインパルス応答の総和の絶対値が一致することになり、この結果、チェス盤歪みを回避し得るような、比較的低いビット精度で高精度の整数型フィルタ係数を算出することが可能となる。従って、ソフトウェアまたはハードウェアで、ＤＷＴとＩＤＷＴとを固定小数点演算で効率良く実行することが可能となる。特に、固定小数点演算を行うハードウェアを採用する場合は、全ての整数型フィルタ係数の分母が共通の２の巾乗をもつことから、除算処理を効率の良いビットシフト演算で行うことができる。従って、入出力ピンの数が少ない小規模な回路構成を実現することが可能である。
【０１３３】
しかもチェス盤歪みを回避できるように、より高い精度で整数型フィルタ係数を算出できる。
【０１３４】
請求項２および請求項８によれば、分解側と合成側の各フィルタの構成要件を満たすように、整数型フィルタ係数を算出できる。
【０１３５】
請求項３および請求項９によれば、上記ローパスフィルタのフィルタ係数の総和の絶対値であるＤＣ成分を所定値に一致させて、ＪＰＥＧ２０００方式などの規格に適合した整数型フィルタ係数を得ることが可能となる。
【０１３６】
請求項４および請求項１０によれば、上記交番信号を印加されたハイパスフィルタの応答の総和の絶対値であるナイキスト成分を所定値に一致させて、ＪＰＥＧ２０００方式などの規格に適合した整数型フィルタ係数を得ることが可能となる。
【０１３７】
請求項５，６および請求項１１，１２によれば、ＦＩＲ型フィルタを用いてウェーブレット変換とその逆変換とを実現できる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係る分解側のＦＩＲ型ローパスフィルタの構成を示す模式図である。
【図２】本発明の第１の実施の形態に係る分解側のＦＩＲ型ハイパスフィルタの構成を示す模式図である。
【図３】アップサンプラとフィルタとの組み合わせを示す模式図である。
【図４】図３に示すフィルタ構成のポリフェーズ表現を示す模式図である。
【図５】図３に示すフィルタ構成の他のポリフェーズ表現を示す模式図である。
【図６】合成側のフィルタバンクを示す模式図である。
【図７】図６に示すフィルタバンクのポリフェーズ表現を示す模式図である。
【図８】合成側のＦＩＲ型フィルタの構成を示す模式図である。
【図９】合成側のＦＩＲ型フィルタの構成を示す模式図である。
【図１０】第１の実施の形態に係るフィルタ係数変換装置の概略構成を示す機能ブロック図である。
【図１１】第１の実施の形態に係るフィルタ係数変換方法を示すフローチャートである。
【図１２】第１の実施の形態に係るフィルタ係数変換方法を示すフローチャートである。
【図１３】１ステージのＤＷＴとＩＤＷＴとを実現するフィルタ構成を示す図である。
【図１４】分解側フィルタバンクのリフティング構成を示す模式図である。
【図１５】合成側フィルタバンクのリフティング構成を示す模式図である。
【図１６】分解側リフティング構成を示すツリー図である。
【図１７】合成側リフティング構成を示すツリー図である。
【図１８】本発明の第２の実施の形態に係るリフティング係数変換装置の概略構成を示す機能ブロック図である。
【図１９】第２の実施の形態に係るリフティング係数変換方法を示すフローチャートである。
【図２０】ＪＰＥＧ２０００方式に基づいた画像符号化装置の概略構成を示す機能ブロック図である。
【図２１】ＪＰＥＧ２０００方式に基づいた画像復号化装置の概略構成を示す機能ブロック図である。
【図２２】１次元ＤＷＴを実現する２分割フィルタバンク群の構成例を示す模式図である。
【図２３】１次元ＩＤＷＴを実現する２分割フィルタバンク群の構成例を示す模式図である。
【図２４】２次元ＤＷＴを施された画像データを模式的に示す図である。
【符号の説明】
１ フィルタ係数変換装置
２ 次数決定手段
３ 丸め込み値選択手段
４ 条件判定手段
９０ リフティング係数変換装置
９１ 次数決定手段
９２ 探索範囲決定手段
９３ 係数評価手段
９４ 係数抽出手段[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an image compression / decompression technique using wavelet transform, particularly discrete wavelet transform.
[0002]
[Prior art]
As one of high-efficiency encoding methods for image data, an image encoding method using a discrete wavelet transform (DWT) and a decoding method thereof are employed. The encoding method based on DWT is a JPEG2000 (Joint Photographic Experts Group 2000) method established by ISO (International Organization for Standardization) as an alternative to the conventional method based on Discrete Cosine Transform (DCT). It is adopted. Compared with DCT, DWT can avoid (1) block-like noise (block distortion) appearing in a decoded image because both ends of the transform base of DCT do not converge, and (2) quantum of high-band components of an image signal. Many excellent advantages such as avoidance of noise (mosquito noise) appearing in the contour portion of the decoded image due to the conversion, and (3) obtaining a high-quality restored image with a high compression ratio have.
[0003]
FIG. 20 is a functional block diagram showing a schematic configuration of the image encoding device 100 based on the JPEG2000 system. Hereinafter, an image compression conversion (forward conversion) procedure will be outlined with reference to FIG. First, an image signal input to the image coding apparatus 100 is subjected to a level shift operation in which a DC level shift unit 102 subtracts half of the dynamic range from each signal value. This level shift calculation is executed when the input signal is a positive integer such as an RGB signal, but the value is a signed integer such as a color difference signal (Cb, Cr) in the YCbCr signal. Is omitted.
[0004]
Next, the color conversion unit 103 executes color space conversion processing for converting the color space of the input data from the DC level shift unit 102 from, for example, an RGB color space to a YCbCr color space. The image data subjected to the color space conversion processing is output to the tiling unit 104, and each frame is divided into a plurality of rectangular block regions. Each divided block area is called a “tile”. The DWT unit 105 performs DWT for each tile unit on the image data input from the tiling unit 104 and outputs the wavelet transform coefficient to the quantization unit 106. In this example, block-based conversion in which DWT is executed on a tile-by-tile basis is adopted. Instead, the input data is buffered for a plurality of lines and vertically filtered, and the result is obtained. A line-based DWT in which horizontal filtering is performed on the data string may be employed. In general, block-based DWT is preferable from the viewpoint of improving conversion efficiency and image quality, and line-based DWT is preferable from the viewpoint of reducing memory usage.
[0005]
The quantization unit 106 performs scalar quantization on the input wavelet transform coefficient, and outputs the resulting quantized coefficient to the entropy encoder 101. When lossless (lossless) encoding is performed, scalar quantization is not performed, and post-quantization described later is employed. Further, the quantization unit 106 selects a specific region (ROI; Region Of Interest) designated by the ROI unit 107, makes the quantization process for the ROI different from that of other regions, and selectively selects the image quality of the specific region. It has the function to improve.
[0006]
Next, the entropy encoder 101 has a functional block that determines the encoding order of input quantization coefficients, performs information source encoding, and outputs the encoded data obtained as a result. FIG. 20 shows functional blocks that perform block-based bit-plane encoding called EBCOT (Embedded Block Coding with Optimized Truncation). That is, the quantized coefficient input to the entropy encoder 101 is converted into a bit model suitable for processing in the subsequent arithmetic encoding unit 109 in the coefficient bit modeling unit 108, and the arithmetic encoding unit 109 performs arithmetic encoding. After that, the bit truncation unit 110 performs post-quantization (truncation).
[0007]
Then, the bit stream generation unit 111 generates a bit stream in which the encoded data input from the entropy encoder 101 and additional information (header information, layer configuration, scalability, quantization table, etc.) are multiplexed, and a compressed image Output as.
[0008]
Next, the procedure for decoding the compressed image will be outlined with reference to FIG. FIG. 21 is a functional block diagram illustrating a schematic configuration of an image decoding device 120 that decodes a compressed image. The bit stream extraction unit 121 separates the additional information and the encoded data from the input compressed image, and outputs the extracted encoded data to the entropy decoder 122. In the entropy decoder 122, the arithmetic decoding unit 123 performs transmission-side arithmetic decoding on the input data, and the coefficient bit modeling unit 124 performs quantization obtained by restoring the bit model of the input data. Output coefficients. Next, the inverse quantization unit 125 performs inverse quantization on the input quantization coefficient and outputs a wavelet transform coefficient obtained as a result.
[0009]
The wavelet transform coefficient output from the inverse quantization unit 125 is subjected to inverse discrete wavelet transform (IDWT; Inverse DWT) in tile units in the IDWT unit 127, synthesized into one frame in the tile synthesis unit 128, and then in the color conversion unit 129. Converted to the original color space. The DC level shift unit 130 performs a level shift operation for adding half of the dynamic range to each signal value input from the color conversion unit 129, and outputs a decoded image obtained as a result.
[0010]
As specific means for realizing the DWT, (1) a method of recursively dividing a low-frequency component into two by repeatedly using a two-divided filter bank that divides the image signal into a high-frequency component and a low-frequency component; (2) a method using a lifting scheme based on a polyphase representation is known. Hereinafter, a method for realizing DWT using a two-part filter bank will be described, and a method for realizing DWT and IDWT using a lifting configuration will be described later.
[0011]
FIG. 22 is a schematic diagram illustrating a configuration example of a two-divided filter bank group that realizes one-dimensional DWT (forward conversion). The two-part filter bank is a low-pass filter H that passes low-frequency components. ₀ (Z) and a high-pass filter H that passes high-frequency components ₁ (Z) and down samplers 140L,..., 142L, 140H,. One-dimensional DWT is configured by repeatedly using this two-divided filter bank. The down samplers 140L to 142L and 140H to 142H thin out every other input signal and output the signal by halving the signal length. The input image is decomposed into a high-frequency component (H) and a low-frequency component (L) at a decomposition level 1, and the low-frequency component (L) is further converted into a high-frequency component (LH) at the next decomposition level 2. ) And a low frequency component (LL), and in the next decomposition level 3, the low frequency component (LL) is further decomposed into a high frequency component (LLH) and a low frequency component (LLL). Thus, four band components (LLL, LLH, LH, H) are finally obtained by recursively dividing the low band component.
[0012]
On the other hand, FIG. 23 is a schematic diagram illustrating a configuration example of a two-divided filter bank group that realizes one-dimensional IDWT (inverse transformation). The two-part filter bank is a low-pass filter G that allows low-frequency components to pass. ₀ (Z) and a high-pass filter G that passes high-frequency components ₁ (Z), up-samplers 150L,..., 154L, 150H,..., Or 154H, and adders 151, 153, or 155. One-dimensional IDWT is configured by repeatedly applying this two-divided filter bank. The upsamplers 150L to 154L and 150H to 154H insert one zero value between each signal value to double the signal length. The four band components (LLL, LLH, LH, H) are input to the two-divided filter bank group.
[0013]
At synthesis level 1, the first component (LLL) is the upsampler 150L and the low-pass filter G. ₀ (Z) is input to the adder 151, and the second component (LLH) is the upsampler 150H and the high-pass filter G. ₁ The result is input to the adder 151 through (z). The adder 151 is connected to each filter G ₀ (Z), G ₁ The components input from (z) are combined to generate a band component (LL). At the next synthesis level 2, the band component (LL) output from the adder 151 is the upsampler 152L and the low-pass filter G. ₀ (Z) is input to the adder 153, and the band component (LH) is the upsampler 152H and the high-pass filter G. ₁ The result is input to the adder 153 through (z). The adder 153 is connected to each filter G ₀ (Z), G ₁ A band component (L) is generated by synthesizing input components from (z). At the synthesis level 3, the band component (L) output from the adder 153 is the upsampler 154L and the low-pass filter G. ₀ (Z) is input to the adder 155, and the band component (H) is the upsampler 154H and the high-pass filter G. ₁ The signal is input to the adder 155 through (z). Finally, the adder 155 ₀ (Z), G ₁ The components input from (z) are combined to generate and output a decoded image.
[0014]
When performing two-dimensional DWT on a two-dimensional image, the input image is applied in the order of the vertical direction and the horizontal direction by applying the two-part filter bank shown in FIG. 22 in the horizontal direction and the vertical direction at each decomposition level. Each band is divided. FIG. 24 is a diagram schematically illustrating image data 160 that has been subjected to two-dimensional DWT. The band component HH1 in the figure includes a horizontal high-frequency component (H) and a vertical high-frequency component (H) of the input image, and the band component HL1 is a horizontal high-frequency component (H ) And a vertical low frequency component (L), and the band component LH1 includes a horizontal low frequency component (L) and a vertical high frequency component (H). A band component LL1 (not shown) including bidirectional low-frequency components in the horizontal direction and the vertical direction is further decomposed into four band components HH2, HL2, LH2, and LL2 at the decomposition level 2, and the next decomposition level 3 The band component LL2 is decomposed into four band components HH3, HL3, LH3 and LL3. In FIG. 24, an example of the third-order decomposition level is shown. However, in the JPEG2000 system, generally, third-order to eighth-order or higher decomposition levels are employed.
[0015]
[Problems to be solved by the invention]
The DWT is roughly classified into a real type DWT in which wavelet transform coefficients are composed of real numbers and an integer type DWT in which wavelet transform coefficients are composed of integers. The real type DWT has the advantage that the image quality of the decoded image is better than that of the integer type DWT by calculating the wavelet transform coefficient by floating point arithmetic.
[0016]
On the other hand, the integer type DWT can perform lossless compression (reversible compression) compared to the real type DWT. In the integer type DWT, since the wavelet transform coefficient can be calculated by fixed point arithmetic, efficient processing can be performed by software or hardware. Specifically, there is an advantage that a low-cost fixed-point processor with a small number of input / output pins and a small circuit configuration can be realized. In general, the digital filter H shown in FIGS. ₀ (Z), H ₁ (Z), G ₀ (Z), G ₁ For (z), a 5 × 3 tap filter is employed in the case of an integer type DWT, and a 9 × 7 tap filter is employed in the case of a real number type DWT.
[0017]
As a technique for performing real type DWT with high efficiency, there is a method of rounding real type filter coefficients into integer type filter coefficients and performing fixed point arithmetic. In this method, filter coefficients expressed in floating point are converted (rounded) into binary expressed filter coefficients. However, if a real type filter coefficient is simply rounded to a binary representation value closest to the filter coefficient, if the accuracy of the value is low, the decoded image will be referred to as a checkerboard distortion. There is a problem that the distortion of the shape appears. To avoid such a problem, the rounding process must be executed with very high bit precision.
[0018]
A filter bank that realizes DWT can also be expressed by a lifting configuration described later. The filter coefficient can be composed of lifting coefficients α, β, γ, δ, κ, 1 / κ described later. When a DWT having a lifting configuration is performed by fixed-point arithmetic, since the lifting coefficient value must be converted from a real type value to an integer type value, the same problem as described above occurs.
[0019]
In view of the above problems, the present invention aims to calculate integer filter coefficients and integer lifting coefficients that can avoid chessboard distortion and the like with relatively low bit precision and high accuracy. A filter coefficient conversion method, a filter coefficient conversion device, a lifting coefficient conversion method, and a lifting coefficient conversion device are provided.
[0020]
[Means for Solving the Problems]
In order to solve the above problem, the invention according to claim 1 Discrete for compressing image signals A group of filters on the decomposition side for realizing the wavelet transform; For decoding compressed images Reverse Discrete A filter coefficient conversion method for converting a filter coefficient with a synthesis-side filter group for realizing a wavelet transform from a real type filter coefficient to an integer type filter coefficient expressed by a fraction, (a) an integer type filter at a conversion destination Coefficient N / 2 ^M Determining the order M of the denominator of (N, M: integer greater than or equal to 1), and (b) the integer filter so that the difference absolute value between the integer filter coefficient and the real filter coefficient is minimized. Select the numerator N of coefficients, and select the integer filter coefficient series on the decomposition side. , Limiting the numerator N of the center coefficient of the series to an even number (C) a step of calculating a synthesis-side integer filter coefficient series using the decomposition-side integer filter coefficients calculated in the step (b); and (d) the step (c) ) Is determined whether or not the condition that the absolute value of the sum of the even-numbered coefficients matches the absolute value of the sum of the odd-numbered coefficients among the integer filter coefficients on the synthesizing side calculated in (1) is satisfied. And a process.
[0022]
Claim 2 The invention according to claim 1 The filter coefficient conversion method according to claim 1, wherein, in the step (c), the synthesis-side integer filter coefficient series includes the decomposition-side integer filter coefficient and the synthesis-side integer filter coefficient that are bi-orthogonal. It is calculated using the condition of satisfying the property.
[0023]
Claim 3 The invention according to claim 1 Or 2 (F) The absolute value of the sum of the filter coefficients of the low-pass filter in the filter group on the decomposition side among the integer filter coefficients on the decomposition side calculated in the step (b). A step of determining whether or not a normalization condition that the value matches a predetermined value is satisfied.
[0024]
Claim 4 The invention according to claim 1 to claim 1 3 The filter coefficient conversion method according to claim 1, wherein (g) the high-pass filter of the decomposition-side filter group using the decomposition-side integer filter coefficient calculated in the step (b). Calculating an absolute value of the sum of responses when alternating signals that alternately take on a plus / minus value of 1 are applied, and determining whether or not a normalization condition that the absolute value matches a predetermined value is satisfied Are further provided.
[0025]
Claim 5 The invention according to claim 1 to claim 1 4 The filter coefficient conversion method according to any one of the above, wherein the filter group includes an FIR filter having a finite tap.
[0026]
Claim 6 The invention according to claim 5 With the filter coefficient conversion method described Ah Thus, the FIR filter is a 9 × 7 tap Daubechies filter.
[0027]
Next, the claim 7 The invention according to Discrete for compressing image signals A group of filters on the decomposition side for realizing the wavelet transform; For decoding compressed images Reverse Discrete A filter coefficient conversion device that converts a filter coefficient with a synthesis-side filter group that realizes wavelet transform from a real type filter coefficient to an integer type filter coefficient expressed by a fraction, and is a conversion destination integer type filter coefficient N / 2 ^M Order determining means for determining the order M of the denominator (N, M: an integer of 1 or more), and the integer filter coefficient so that the absolute difference between the integer filter coefficient and the real filter coefficient is minimized. And a sequence of integer-type filter coefficients on the decomposition side obtained by rounding the real-type filter coefficients. , Limiting the numerator N of the center coefficient of the series to an even number Rounding value selection means for calculating, coefficient calculation means for calculating a series of integer type filter coefficients on the synthesis side using the integer type filter coefficients on the decomposition side calculated by the rounding value selection means, and integers on the synthesis side And a condition determination means for determining whether or not a condition that the absolute value of the sum of even-numbered coefficients of the type filter coefficients matches the absolute value of the sum of odd-numbered coefficients is satisfied. To do.
[0029]
Claim 8 The invention according to claim 7 In the filter coefficient conversion device described above, the synthesis-side integer filter coefficient series uses a condition that the decomposition-side integer filter coefficient and the synthesis-side integer filter coefficient satisfy bi-orthogonality. Is calculated.
[0030]
Claim 9 The invention according to claim 7 Or 8 The filter coefficient conversion device according to any one of the above, wherein the condition determination unit further includes a sum of filter coefficients of a low-pass filter in the decomposition-side filter group of the decomposition-side integer filter coefficients. Is provided with means for determining whether or not a normalization condition that the absolute value of is equal to a predetermined value is satisfied.
[0031]
Claim 1 0 The invention according to claim 7 ~ 9 The filter coefficient conversion device according to any one of the above, wherein the condition determination unit further adds a plus or minus to a high-pass filter in the decomposition-side filter group using the decomposition-side integer filter coefficient. Means for calculating an absolute value of a sum of responses when an alternating signal that alternately takes a value of 1 is applied, and determining whether a normalization condition that the absolute value matches a predetermined value is satisfied Is.
[0032]
Claim 1 1 The invention according to claim 7 ~ 10 The filter coefficient conversion apparatus according to any one of the above, wherein the filter group includes an FIR filter having a finite tap.
[0033]
Claim 1 2 The invention according to claim 1 1 The filter coefficient conversion device according to claim 1, wherein the FIR filter is a 9 × 7 tap Daubechies filter.
[0038]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, various embodiments of the present invention will be described.
[0039]
First embodiment.
As described above, as specific means for realizing DWT and IDWT, there are a method using the two-divided filter bank shown in FIGS. 22 and 23 and a method using a lifting configuration. The filter coefficient conversion method and apparatus according to the present embodiment are a method and apparatus applied to DWT and IDWT using a two-part filter bank.
[0040]
Hereinafter, the decomposition-side filter H shown in FIG. ₀ (Z), H ₁ (Z) and the synthesis-side filter G shown in FIG. ₀ (Z), G ₁ Both (z) are composed of finite impulse response (FIR) type filters and have real type filter coefficients of 9 × 7 taps.
[0041]
Configuration of FIR filter.
First, an FIR filter that realizes DWT will be described. In the decomposition-side filter bank shown in FIG. 22, one of the down samplers 140L to 142L is connected to each low-pass filter H. ₀ In the data string output from (z), only the even-numbered samples are retained and the odd-numbered samples are discarded, and the other down-samplers 140H to 142H ₁ In the data string output from (z), a thinning process is performed in which only odd-numbered samples are retained and even-numbered samples are discarded. Thus, each filter H ₀ (Z), H ₁ The data output from (z) is separated into two phases (polyphase) of even and odd numbers and subjected to thinning processing. However, the filter H ₀ (Z), H ₁ It is not efficient to perform the filtering process on all input data regardless of whether (z) is even or odd. In the present embodiment, the low-pass filter H ₀ (Z) executes the filtering process only for the even-numbered data string, and the high-pass filter H ₁ (Z) executes the filtering process only for odd-numbered data strings, and as a result, each filter H ₀ (Z), H ₁ In (z), filter processing and thinning-out processing are executed simultaneously in parallel for each phase.
[0042]
FIG. 1 shows an FIR low-pass filter H on the decomposition side. ₀ FIG. 2 is a schematic diagram showing the configuration of (z), and FIG. 2 shows an FIR type high-pass filter H on the decomposition side. ₁ It is a schematic diagram which shows the structure of (z). The input image 10 is composed of input data strings,..., X (2n-4), X (2n-3),..., X (2n), ..., X (2n + 4),. As shown in FIG. ₀ (Z) is a filter coefficient h corresponding to 9 taps. ₀ (-4), h ₀ (-3), ..., h ₀ (3), h ₀ (4), the input data string and the filter coefficient h ₀ (-4) to h ₀ Multiplier 11 that performs a convolution operation with (4) ₁ ~ 11 ₉ And an adder 12. This low-pass filter H ₀ (Z) selectively performs a convolution operation on even-numbered data X (2n) according to the following equation (1), and outputs data Y (2n).
[0043]
[Expression 1]

[0044]
Further, as shown in FIG. ₁ (Z) is a filter coefficient h corresponding to 7 taps. ₁ (-4), h ₁ (-3), ..., h ₁ (1), h ₁ (2), the input data string and the filter coefficient h ₁ (-4) to h ₁ Multiplier 13 for performing a convolution operation with (2) ₁ ~ 13 ₇ And an adder 14. This high pass filter H ₁ (Z) selectively performs a convolution operation on odd-numbered data X (2n + 1) according to the following equation (2), and outputs data Y (2n + 1).
[0045]
[Expression 2]

[0046]
Next, an FIR type filter for realizing IDWT will be described. The low pass filter G on the synthesis side shown in FIG. ₀ (Z) and the high-pass filter G ₁ When (z) is expressed using z-transform, the following equations (3) and (4) are obtained.
[0047]
[Equation 3]

[0048]
In the above formulas (3) and (4), the filter coefficient g ₀ (K) (k = -3 to 3) and g ₁ (K) (k = −3 to 5) indicates an impulse response, and z ^-k Indicates a k-th order delay.
[0049]
The synthesis-side filter bank shown in FIG. 23 can be modified by polyphase decomposition described below. FIG. 3 schematically shows a combination of the upsampler 30 and the filter G (z). The filter G (z) is an FIR type filter having a filter coefficient h (k) (k: integer). The upsampler 30 performs an upsampling process for inserting a zero value between the values of the input signal y (n), and the filter G (z) is a signal x (n) obtained by interpolating the output data from the upsampler 30. ) Is output. The filter G (z) is a transfer function using z-transform, and G (z) = R ₀ (Z ² Z ^-1 + R ₁ (Z ² ). Such an expression is called “type 2 polyphase decomposition”. Each filter R decomposed into two phases ₀ (Z ² ), R ₁ (Z ² ) Is called a “polyphase filter”.
[0050]
Based on the polyphase representation of the filter described above, the FIR filter G (z) has two polyphase filters R as shown in FIG. ₀ (Z ² ), R ₁ (Z ² ), A delay element 32, and an adder 33. That is, the first polyphase filter R ₀ (Z ² ) Is delayed by one cycle by the delay element 32 and then added by the second polyphase filter R in the adder 33. ₁ (Z ² ) Output signal. Furthermore, the filter configuration of FIG. 4 is equivalent to the filter configuration shown in FIG. Therefore, the output signal x (n) ₀ (Z), R ₁ It can be said that the output signal (z) is alternately output.
[0051]
By the way, the synthesis-side low-pass filter G shown in FIG. ₀ (Z) and high-pass filter G ₁ (Z) is a transfer function using z-transform and can be modified as in the following equations (3A) and (4A).
[0052]
[Expression 4]

[0053]
In the above formula (3A), R ₀ (Z ² ), R ₁ (Z ² ) Is the synthesis-side low pass filter G ₀ (Z) represents a polyphase filter, and in the above equation (4A), K ₀ (Z ² ), K ₁ (Z ² ) Is the synthesis-side high-pass filter G ₁ The polyphase filter which comprises (z) is shown.
[0054]
Therefore, based on the above-described polyphase expression, the synthesis-side filter bank shown in FIG. 6 can be transformed into the filter configuration shown in FIG. 6 and 7, reference numerals 34, 35, 34A, 34B, 35A, and 35B indicate upsamplers, reference numerals 36, 38, and 40 indicate adders, and reference numerals 37 and 39 indicate delay elements.
[0055]
Therefore, the output signal x of the adder 38 on the low-pass filter side. ₀ (N) indicates each polyphase filter R ₀ (Z), R ₁ Output signal r of (z) ₀ , R ₁ Output signal x of the adder 40 on the high pass filter side. ₁ (N) indicates each polyphase filter K ₀ (Z), K ₁ Output signal k of (z) ₀ , K ₁ Are output alternately. As a result, among the output signals x (n) of the adder 36, the even-numbered output signal x (2k) is converted into each polyphase filter R. ₀ (Z), K ₀ Sum of output signals of (z) r ₀ + K ₀ The odd-numbered output signal x (2k + 1) is output from each polyphase filter R ₁ (Z), K ₁ Sum of output signals of (z) r ₁ + K ₁ It can be.
[0056]
In accordance with the above polyphase expression, an FIR filter that realizes a filter bank on the synthesis side can be configured. 8 and 9 are schematic diagrams showing the configuration of the FIR filter on the synthesis side. These FIR filters execute filter processing and upsampling processing in parallel. Further, these FIR filters are inputted with data strings..., Y (2n-3), Y (2n-2),..., Y (2n + 4), Y (2n + 5),. Yes.
[0057]
The 7-tap FIR filter shown in FIG. ₀ (Z ² ), K ₀ (Z ² ) Filter coefficient g ₀ (-2), g ₀ (0), g ₀ (2), g ₁ (-2), g ₁ (0), g ₁ (2), g ₁ Using (4), a multiplier 21 that performs a convolution operation on these filter coefficients and the input data string ₀ , 21 ₁ , ..., 21 ₆ And an adder / subtractor 22. This FIR type filter performs a convolution operation according to the following equation (5) to synthesize even-numbered data X (2n).
[0058]
[Equation 5]

[0059]
Further, the 9-tap FIR filter shown in FIG. ₁ (Z ² ), K ₁ (Z ² ) Filter coefficient g ₀ (-3), g ₀ (-1), g ₀ (1), g ₀ (3), g ₁ (-3), g ₁ (-1), g ₁ (1), g ₁ (3), g ₁ (5) is used to multiply the filter coefficient and the input data string by a multiplier 23. ₁ , ..., 23 ₉ And an adder 24. This FIR type filter synthesizes odd-numbered data X (2n + 1) by executing a convolution operation according to the following equation (6).
[0060]
[Formula 6]

[0061]
Conditions for avoiding chessboard distortion.
Next, conditions for avoiding the chessboard distortion will be described. In FIG. 3, when the unit step signal is applied as the input signal y (n) to the filter, the output signal x (n) is the sum of the impulse responses h (k) of the filter G (z), and this sum It is desirable to converge to a constant value over time. On the other hand, in FIG. 5, the output signal x (n) corresponding to the input signal y (n) ₀ (Z), R ₁ This is equivalent to the output signal of (z) being alternately output. When a unit step signal is applied as the input signal y (n), each polyphase filter R ₀ (Z), R ₁ The sum of impulse responses (z) is alternately output. Therefore, each polyphase filter R ₀ (Z), R ₁ When the sums of the impulse responses of (z) are different, different values are output alternately according to the value of n, and a phenomenon occurs in which the values do not converge to a constant value. Chessboard distortion is considered to represent this kind of phenomenon.
[0062]
Therefore, the chessboard distortion avoidance condition is at least the R of each polyphase filter. ₀ (Z), R ₁ The sum of the impulse responses of (z) matches.
[0063]
Filter coefficient conversion process.
Next, a filter coefficient conversion method and apparatus according to the first embodiment of the present invention will be described. FIG. 10 is a functional block diagram showing a schematic configuration of the filter coefficient conversion apparatus 1 according to the present embodiment. This filter coefficient converting apparatus 1 is a value obtained by rounding a real type filter coefficient 5 inputted from the outside into a fraction (= N / 2). ^M ; N and M are integers of 1 or more) denominator (= 2) ^M ) Order determining means 2 for determining the order M, rounded value selecting means 3 for selecting an integer value of the numerator N and outputting an integer type filter coefficient (rounded value) 6 on the decomposition side, and an integer on the combining side The coefficient calculation means 3A for calculating the type filter coefficient, and the condition determination means 4 for determining whether or not the input decomposition type and synthesis side integer type filter coefficients satisfy a predetermined condition. A value obtained by rounding off the real type filter coefficient 5 (= N / 2) ^M ) Is a decimal representation value. In actual processing, the value is represented by a digital value.
[0064]
The conversion processing of the decomposition side filter coefficient using the filter coefficient conversion apparatus 1 having the above configuration will be described in detail below with reference to the flowchart of FIG. In this conversion process, the decomposition-side low-pass filter H ₀ The filter coefficient of (z) is converted into an integer value. As the real filter of the conversion source, a 9 × 7 tap Daubechies filter can be employed. Tables 1 and 2 below show the filter coefficient <h ₀ (N)>, <h ₁ (N)>, <g ₀ (N)>, <g ₁ (N)>. <H> is a symbol representing that the filter coefficient h is a real type coefficient.
[0065]
[Table 1]

[0066]
[Table 2]

[0067]
In step ST1, the filter coefficient conversion device 1 is supplied with a real filter coefficient <h ₀ (N)> is input. Input filter coefficient <h ₀ (N)> is transmitted to the degree determining means 2 and the rounded value selecting means 3, respectively. In subsequent step ST2, the order determining means 2 determines that the input real type filter coefficient <h ₀ (N)> rounded expression (= N ₀ (N) / 2 ^M = H ₀ (N)) denominator (= 2) ^M ) Is determined, and the value M is output to the rounded value selection means 3.
[0068]
The rounding value selection means 3 is the nth rounding value (= N ₀ (N) / 2 ^M ) Is a zero value, the processing of steps ST3 and ST4 is executed, and when the number n is a non-zero value, the processing of steps ST5 and ST6 is executed. In step ST3, the rounded value h at the center position in the series of integer filter coefficients. ₀ Focusing on (0), this rounding value h ₀ Molecule N of (0) ₀ (0) is an even number and the rounding value h ₀ (0) and the real filter coefficient <h ₀ An integer value N that satisfies the condition that the difference absolute value from (0)> is minimized. ₀ Select (0). In the subsequent step ST4, the selected molecule N ₀ (0) for the denominator 2 ^M Rounded value h divided by ₀ (0) is calculated.
[0069]
On the other hand, in step ST5, the rounded value h at the center position in the series of integer filter coefficients. ₀ Focusing on (n) (n: integer other than zero), this rounding value h ₀ (N) and the real type filter coefficient <h ₀ An integer value N that satisfies the condition that the difference absolute value from (n)> is minimized. ₀ Select (n). Integer value N ₀ (N) is not necessarily an even number. In the subsequent step ST6, the selected molecule N ₀ (N) for the denominator 2 ^M Rounded value h divided by ₀ (N) is calculated.
[0070]
As described above, in steps ST4 and ST6, the rounded value selection means 3 performs integer type filter coefficient h. ₀ After outputting (n) to the condition determining means 4, the condition determining means 4 executes the processes after step ST7. In step ST7, the decomposition-side low pass filter H ₀ Impulse response h of (z) ₀ DC component G indicating the absolute value of the sum of (n) _DC And the DC component G _DC It is determined whether or not a normalization condition is satisfied that is equal to a predetermined value. When JPEG2000 is used, DC component G _DC The value of must match "1". DC component G _DC The calculation formula is as the following formula (7).
[0071]
[Expression 7]

[0072]
If the standardization condition is satisfied in step ST7, the process proceeds to step ST8. If the standardization condition is not satisfied, normalization is performed in step ST9 so as to satisfy the standardization condition. Then, the process proceeds to step ST8.
[0073]
In the next step ST8, the coefficient calculation means 3A uses the bi-orthogonal condition that the decomposition-side filter and the synthesis-side filter satisfy the bi-orthogonality and uses the synthesis-side high-pass filter G. ₁ Integer filter coefficient g of (z) ₁ (N) is calculated and output to the condition determining means 4. The bi-orthogonal condition is as shown in the following equation (8).
[0074]
[Equation 8]

[0075]
In step ST10, the condition determination means 4 uses the synthesis-side filter coefficient g calculated in step ST8. ₁ Using (n), the high-pass filter G on the synthesis side ₁ Each polyphase filter K constituting (z) ₀ (Z ² ), K ₁ (Z ² It is determined whether or not a constraint condition that the absolute value of the sum of the impulse responses of () matches is satisfied. This constraint condition is the high-pass filter G ₁ This is the same as the absolute value of the sum of the even-numbered filter coefficients in (z) matches the absolute value of the sum of the odd-numbered filter coefficients. When the JPEG2000 system is adopted, a condition that the absolute value of the sum is 1/2 is further added to the binding condition. The constraining condition when the JPEG2000 method is adopted is as shown in the following formula (9).
[0076]
[Equation 9]

[0077]
If the binding condition is not satisfied in step ST10, the condition determining means 4 determines that the integer filter coefficient h ₀ (N), g ₁ The calculation of (n) is considered to have failed, and this filter coefficient conversion process ends. On the other hand, if the binding condition is satisfied in step ST10, the process proceeds to the next step ST11, where the condition determination means 4 determines that the integer filter coefficient h ₀ (N), g ₁ Determine (n) and output.
[0078]
The coefficient value h obtained by converting the filter coefficient of the 9 × 7 tap Dobysys filter by the above filter coefficient conversion processing ₀ (N), g ₁ (N) is shown in the following Tables 3 and 4, respectively.
[0079]
[Table 3]

[0080]
[Table 4]

[0081]
Next, the decomposition side high-pass filter H ₁ The filter coefficient conversion process (z) will be described in detail below with reference to the flowchart of FIG. First, in step ST20, the filter coefficient conversion apparatus 1 is supplied with a real type filter coefficient <h. ₁ (N)> is input. Input filter coefficient <h ₁ (N)> is transmitted to the degree determining means 2 and the rounded value selecting means 3, respectively. In subsequent step ST21, the order determining means 2 receives the input real filter coefficient <h ₁ (N)> rounded expression (= N ₁ (N) / 2 ^M = H ₁ (N)) denominator (= 2) ^M ) Is determined, and the value M is output to the rounded value selection means 3.
[0082]
The rounding value selection means 3 is the nth rounding value (= N ₁ (N) / 2 ^M ) Is a zero value, the processes of steps ST22 and ST23 are executed, and when the number n is a non-zero value, the processes of steps ST24 and ST25 are executed. In step ST22, the rounding value h ₁ Molecule N of (n) ₁ (-1) is an even number and the rounding value h ₁ (-1) and the real type filter coefficient <h ₁ An integer value N that satisfies the condition that the difference absolute value with respect to (-1)> is minimized. ₁ Select (-1). In the subsequent step ST23, the selected molecule N ₁ (-1) for the denominator 2 ^M Rounded value h divided by ₁ (-1) is calculated.
[0083]
On the other hand, in step ST24, the rounding value h ₁ (N) (n: integer other than −1) and the real type filter coefficient <h ₁ An integer value N that satisfies the condition that the difference absolute value from (n)> is minimized. ₁ Select (n). Its integer value N ₁ (N) is not necessarily an even number. In the subsequent step ST25, the selected molecule N ₁ (N) for the denominator 2 ^M Rounded value h divided by ₁ (N) is calculated.
[0084]
As described above, in steps ST23 and ST25, the rounded value selection means 3 performs integer type filter coefficient h. ₁ After outputting (n) to the condition determining means 4, the condition determining means 4 executes the processing after step ST26. In step ST26, the decomposition-side high-pass filter H in the case where an alternating signal that alternately takes a value of plus or minus 1 is applied. ₁ (Z) absolute value of sum of responses (hereinafter referred to as Nyquist component D) _Nyquist Call it. ) And the Nyquist component D _Nyquist It is determined whether or not a normalization condition is satisfied that is equal to a predetermined value. Nyquist component D when JPEG2000 is used _Nyquist The value of must match "2". This Nyquist component D _Nyquist The calculation formula is as the following formula (10).
[0085]
[Expression 10]

[0086]
If the normalization condition is satisfied in step ST26, the process proceeds to step ST27. If the normalization condition is not satisfied, normalization is performed in step ST28 so as to satisfy the normalization condition. Then, the process proceeds to step ST27.
[0087]
In the next step ST27, using the bi-orthogonal condition (the above equation (8)) that the decomposition-side filter and the synthesis-side filter satisfy the bi-orthogonality, the synthesis-side low-pass filter G ₀ Integer filter coefficient g of (z) ₀ (N) is calculated.
[0088]
In the next step ST29, the synthesis-side filter coefficient g calculated in the step ST27. ₀ Using (n), the low-pass filter G on the synthesis side ₀ Each polyphase filter R constituting (z) ₀ (Z ² ), R ₁ (Z ² It is determined whether or not a constraint condition that the sum of the impulse responses of () matches is satisfied. When the JPEG2000 system is adopted, a condition that the sum is “1” is further added to the binding condition. The constraining condition when the JPEG2000 system is adopted is as shown in the following formula (11).
[0089]
[Expression 11]

[0090]
When this constraint condition is satisfied, the sum of the impulse responses of the polyphase filters matches, so that the chessboard distortion in the decoded image can be avoided as described above.
[0091]
If the binding condition is not satisfied in step ST29, the condition determining means 4 determines that the integer filter coefficient h ₁ (N), g ₀ The calculation of (n) is considered to have failed, and this filter coefficient conversion process ends. On the other hand, if the constraint condition is satisfied in step ST29, the process proceeds to the next step ST30, where the condition determination means 4 determines that the integer filter coefficient h ₁ (N), g ₀ Determine (n) and output.
[0092]
According to the above filter coefficient conversion process, the filter coefficient of the 9 × 7 tap Dovisys filter is converted, and the resulting integer coefficient value h ₁ (N), g ₀ (N) is shown in Tables 5 and 6 below.
[0093]
[Table 5]

[0094]
[Table 6]

[0095]
As described above, in the first embodiment, it is determined whether or not the condition that the sum of the impulse responses of the polyphase filters constituting the low-pass filter matches is satisfied in step ST29 (FIG. 12). It is carried out. For this reason, when synthesizing a low frequency component with IDWT, a highly accurate integer filter coefficient can be calculated with relatively low bit accuracy so that chessboard distortion is not mixed in the low frequency component.
[0096]
In step ST10 (FIG. 11), a determination process is performed to determine whether or not the condition that the sum of the absolute values of the impulse responses of the polyphase filters constituting the high-pass filter matches is satisfied. Therefore, it is possible to calculate the integer filter coefficients with high accuracy so as to avoid the chessboard distortion while satisfying the constituent requirements of the filters on the decomposition side and the synthesis side.
[0097]
Further, in step ST3 (FIG. 11) and step ST22 (FIG. 12), h corresponding to the center value in the series of integer filter coefficients. ₀ (0), h ₁ Both molecules of (-1) are selected to be an even number. For this reason, the integer filter coefficient can be calculated with higher accuracy.
[0098]
Accordingly, it is possible to efficiently execute DWT and IDWT by fixed-point arithmetic using the integer filter coefficient in software or hardware. In particular, when hardware is employed, the denominator of all integer filter coefficients has a common power of 2, so that the division process can be efficiently performed by a bit shift operation. Therefore, it is possible to realize a small-scale hardware configuration with a small number of input / output pins.
[0099]
Second embodiment.
Next, a second embodiment of the present invention will be described. The lifting coefficient conversion method and apparatus according to the present embodiment is a method and apparatus applied to DWT and IDWT using a lifting configuration. First, after an outline of the lifting configuration, the lifting coefficient conversion processing according to the present embodiment will be described.
[0100]
Lifting configuration.
FIG. 13 is a diagram showing a filter configuration for realizing DWT and IDWT of only one stage (only the first-order decomposition level). A DWT having such a configuration is called a polyphase DWT. In FIG. 13, reference numerals 41 and 46 denote delay elements, 42 and 43 denote downsamplers, and 44 and 45 denote upsamplers. Also, P in the figure _c (Z), P (z) ^-1 Is called a polyphase matrix.
[0101]
In the forward conversion, the input data X (k) (k: integer) branches and is transmitted to the down sampler 42 and the delay element 41, and the down sampler 42 receives even-numbered data X (2n + 4) (n: integer). On the other hand, the down sampler 43 that down-samples the output signal of the delay element 41 outputs odd-numbered data X (2n + 3). That is, the input data X (k) is separated into even-numbered data X (2n + 4) and odd-numbered data X (2n + 3), and the polyphase matrix P _c (Z) is input. This polyphase matrix P _c From (z), a low frequency component (LP) Y (2n) and a high frequency component (HP) Y (2n + 1) are output.
[0102]
On the other hand, in the inverse transformation, the polyphase matrix P (z) ^-1 Performs inverse transformation of the polyphase matrix P (z) on the input data Y (2n), Y (2n + 1), restores the data X (2n-2), X (2n-3) and outputs them To do. The even-numbered data X (2n−2) is transmitted to the adder 47 through the upsampler 44 and the delay element 46, and the odd-numbered data X (2n−3) is transmitted to the adder 47 through the upsampler 45. The adder 47 synthesizes the original data X (k).
[0103]
Polyphase matrix P of forward transformation _c (Z) and inverse polyphase matrix P (z) ^-1 Can be constructed by a technique called a lifting configuration. The lifting structure is described, for example, in the document “W. Sweldens, I. Daubechies,“ Factoring Wavelet Transforms into Lifting Steps ”, J. Fourier Anal., Vol. 4, No. 3, pp. 247-269, 1998”. Has been.
[0104]
The forward transformation is realized with the lifting configuration shown in FIG. 14, and the inverse transformation is realized with the lifting configuration shown in FIG. In FIG. 14, reference numerals 51, 53, 58, and 59 denote 2-tap FIR filters represented by z-transform transfer functions, reference numerals 54, 56, and 60 denote delay elements, and 62 denotes a coefficient for an input signal. A multiplier that multiplies 1 / κ and outputs it, 63 is a multiplier that multiplies the input signal by a coefficient κ, and 52 is output, and 52, 55, and 57 are adders.
[0105]
In FIG. 15, reference numerals 72, 75, 78, and 81 denote 2-tap FIR filters represented by z-transform transfer functions, and reference numeral 70 multiplies an input signal by a coefficient κ and outputs the result. A multiplier 71 is a multiplier that multiplies an input signal by a coefficient 1 / κ and outputs it, 74, 77, and 80 are delay elements, and 73, 76, 79, and 82 are subtractors.
[0106]
The coefficients α, β, γ, δ, and κ appearing in FIGS. 14 and 15 are called lifting coefficients, and have a real type value in the lifting configuration of the 9 × 7 tap Dovisys filter.
[0107]
Further, with the decomposition-side lifting configuration shown in FIG. 14, the input data X (k) is decomposed into odd-numbered data X (2n + 3) and even-numbered data X (2n + 4). Further, intermediate data Y ′ (2n + 3), Y ″ (2n + 2), Y ′ ″ (2n + 1), Y ″ ″ (2n) are generated one after another, and finally data Y (2n), Y (2n + 1) is output. As shown in FIG. 16, the decomposition-side lifting configuration can be expressed by a tree diagram including black dots indicating data and line segments connecting the black dots. In the vicinity of each black spot, data indicating the black spot is displayed. For example, input data strings X (2n), X (2n + 1),..., X (2n + 4) are displayed corresponding to the black dots at the left end. In addition, coefficients are displayed in the vicinity of line segments connecting the black spots. For example, a coefficient α is displayed in the vicinity of a line segment between a black point indicating data X (2n) and a black point indicating data Y ′ (2n + 1).
[0108]
The disassembly-side lifting configuration shown in FIG. 16 is interpreted based on the following rules (A), (B), and (C). (A) Data indicating a black spot is transmitted along a line segment extending from left to right. (B) The line segment connecting the black spots is multiplied by the coefficient by the data transmitting the line segment. (C) Black dots are added to the data input from the left along each line segment and output to the line segment extending to the right. Therefore, the decomposition side lifting configuration is equivalent to the following equation (12).
[0109]
[Expression 12]

[0110]
Further, with the composition-side lifting configuration shown in FIG. 15, intermediate data X ′ ″ (2n + 4), X ″ (2n + 5),... Are successively generated for the input data string Y (2n + 4), Y (2n + 5). Finally, the composite data X (k) is output. This combining-side lifting configuration can also be expressed by a tree diagram including black dots and line segments shown in FIG. 17 and is equivalent to the following equation (13).
[0111]
[Formula 13]

[0112]
The following formula (14) shows the exact values of the lifting coefficients α, β, γ, δ, and κ when the lifting configuration of the 9 × 7 tap Dovisys filter is adopted.
[0113]
[Expression 14]

[0114]
Table 7 below shows the decomposition-side filter coefficient h of the Dovisys filter. ₀ (N), h ₁ (N) is composed of lifting coefficients α, β, γ, δ, κ, 1 / κ, and Table 8 below shows the synthesis-side filter coefficient g of the Dovisys filter. ₀ (N), g ₁ (N) is composed of lifting coefficients α, β, γ, δ, κ, 1 / κ.
[0115]
[Table 7]

[0116]
[Table 8]

[0117]
Lifting coefficient conversion process.
Next, a lifting coefficient conversion method and apparatus according to the second embodiment of the present invention will be described. FIG. 18 is a functional block diagram showing a schematic configuration of the lifting coefficient conversion apparatus 90 according to the present embodiment. This lifting coefficient conversion apparatus 90 is a value obtained by rounding a real type lifting coefficient input from the outside into a fraction (= N / 2). ^M ; N and M are integers of 1 or more) denominator (= 2) ^M ), A coefficient evaluation means 93 that searches for an integer value of the numerator N based on an evaluation formula described later, and a search range that instructs the coefficient evaluation means 93 to specify a search range. The determination means 92 and the coefficient extraction means 94 for extracting the integer type lifting coefficient output from the coefficient evaluation means 93 are provided.
[0118]
The lifting coefficient conversion process using the lifting coefficient converter 90 having the above configuration will be described in detail below with reference to the flowchart of FIG. In the first step ST <b> 1, the conversion source real type lifting coefficient is input to the lifting coefficient converter 90. The order determining means 91 rounds and expresses each of the real type lifting coefficients α, β, γ, δ, κ, 1 / κ (= N / 2). ^M ) Denominator (= 2) ^M ) And the value M is output to the coefficient evaluation means 93. In parallel, the search range determining unit 92 determines the search range of each real type lifting coefficient and outputs it to the coefficient evaluating unit 93.
[0119]
After the next step ST41A, the coefficient evaluation means 93 calculates a value of an evaluation expression (to be referred to as an evaluation value hereinafter) and an integer type lifting coefficient corresponding to this value within the designated search range. To do. That is, a loop is formed between steps ST41A to ST46A and steps ST41B to 46B, and the numerators of integer type lifting coefficients α, β, γ, δ, κ, 1 / κ are sequentially small in the specified search range. Change. In step ST47, evaluation values described below are calculated for all combinations of integer type lifting coefficients changed in the loop.
[0120]
According to Table 8 and Table 9 above, the above equation (9) is expressed as the following equation (15).
[0121]
[Expression 15]

[0122]
Further, the above equation (11) is expressed as the following equation (16).
[0123]
[Expression 16]

[0124]
The evaluation formula adds the sum of absolute differences between the values of the middle side and the right side of the above equation (15) and the sum of absolute differences of the values of the middle side and the right side of (16). Which is expressed by the following equation (17).
[0125]
[Expression 17]

[0126]
In the next step ST48, the coefficient extracting means 94 is a combination of integer-type lifting coefficients (α, β, γ, δ, κ, etc.) that takes the smallest evaluation value among the evaluation value combinations input from the coefficient evaluation means 93. 1 / κ) is determined and output. Here, the above-described DC component G _DC And Nyquist component D _Nyquist It may be determined whether or not a condition that each takes a predetermined value is satisfied.
[0127]
Examples of calculation results of the above lifting coefficient conversion processing are shown in Table 9, Table 10, and Table 11 below. “Range” in Table 9 and Table 11 indicates the upper and lower limit values of the fluctuation range of the search range. That is, the search range is a range from a value obtained by subtracting the lower limit value from the real number type lifting coefficient to a value obtained by adding the upper limit value to the real number type lifting coefficient. For example, since the upper and lower limit values of the fluctuation range corresponding to the order M = 5 shown in Table 9 are “± 1”, the search range of the coefficient α is <α> −1 to <α> +1 (provided that , <Α> is a real type lifting coefficient). In this example, a common search range is set for all integer type lifting coefficients according to the value of the order M of each denominator. Although Table 9 and Table 10 are displayed separately, the search range corresponding to each order M is the same. Further, the value of “evaluation formula” in Table 11 means the evaluation value.
[0128]
[Table 9]

[0129]
[Table 10]

[0130]
[Table 11]

[0131]
As described above, in the second embodiment, the integer type filter coefficient is selected so that the evaluation value is close to zero, so that the chessboard distortion can be reduced with relatively low bit accuracy. It is possible to calculate the integer type filter coefficient.
[0132]
【The invention's effect】
As described above, the filter coefficient conversion method and claim according to claim 1 of the present invention. 7 According to the filter coefficient conversion apparatus according to the above, the absolute value of the sum of the impulse responses of the polyphase filters on the synthesis side is matched by the step (d) and the condition determination means. It is possible to calculate a high-precision integer filter coefficient with relatively low bit precision that can be avoided. Therefore, DWT and IDWT can be efficiently executed by fixed-point arithmetic with software or hardware. In particular, when hardware that performs fixed-point arithmetic is adopted, the denominator of all integer filter coefficients has a common power of 2, so that division processing can be performed by efficient bit shift arithmetic. Therefore, it is possible to realize a small circuit configuration with a small number of input / output pins.
[0133]
Moreover Integer filter coefficients can be calculated with higher accuracy so that chessboard distortion can be avoided.
[0134]
Claim 2 And claims 8 According to the above, integer filter coefficients can be calculated so as to satisfy the constituent requirements of the respective filters on the decomposition side and the synthesis side.
[0135]
Claim 3 And claims 9 According to the above, it is possible to obtain an integer filter coefficient conforming to a standard such as the JPEG2000 system by matching the DC component, which is the absolute value of the sum of the filter coefficients of the low-pass filter, with a predetermined value.
[0136]
Claim 4 And claims 10 According to the present invention, the Nyquist component, which is the absolute value of the sum of responses of the high-pass filter to which the alternating signal is applied, is made to coincide with a predetermined value, and an integer filter coefficient that conforms to a standard such as the JPEG2000 system can be obtained Become.
[0137]
Claim 5, 6 And claims 11, 12 According to the above, wavelet transformation and its inverse transformation can be realized using an FIR filter.
[Brief description of the drawings]
FIG. 1 is a schematic diagram showing a configuration of an FIR low-pass filter on the decomposition side according to a first embodiment of the present invention.
FIG. 2 is a schematic diagram showing a configuration of a decomposition-side FIR type high-pass filter according to the first embodiment of the present invention.
FIG. 3 is a schematic diagram showing a combination of an upsampler and a filter.
4 is a schematic diagram showing a polyphase expression of the filter configuration shown in FIG. 3. FIG.
5 is a schematic diagram showing another polyphase expression of the filter configuration shown in FIG. 3. FIG.
FIG. 6 is a schematic diagram showing a filter bank on the synthesis side.
7 is a schematic diagram showing a polyphase representation of the filter bank shown in FIG. 6. FIG.
FIG. 8 is a schematic diagram showing a configuration of a synthesis-side FIR filter.
FIG. 9 is a schematic diagram showing a configuration of a synthesis-side FIR filter.
FIG. 10 is a functional block diagram showing a schematic configuration of a filter coefficient conversion device according to the first embodiment.
FIG. 11 is a flowchart showing a filter coefficient conversion method according to the first embodiment.
FIG. 12 is a flowchart showing a filter coefficient conversion method according to the first embodiment.
FIG. 13 is a diagram showing a filter configuration for realizing one-stage DWT and IDWT.
FIG. 14 is a schematic diagram showing a lifting configuration of a decomposition-side filter bank.
FIG. 15 is a schematic diagram showing a lifting configuration of a synthesis-side filter bank.
FIG. 16 is a tree diagram showing a disassembly-side lifting configuration.
FIG. 17 is a tree diagram showing a composition-side lifting configuration;
FIG. 18 is a functional block diagram showing a schematic configuration of a lifting coefficient conversion apparatus according to a second embodiment of the present invention.
FIG. 19 is a flowchart showing a lifting coefficient conversion method according to the second embodiment.
FIG. 20 is a functional block diagram illustrating a schematic configuration of an image encoding device based on the JPEG2000 system.
FIG. 21 is a functional block diagram illustrating a schematic configuration of an image decoding apparatus based on the JPEG2000 system.
FIG. 22 is a schematic diagram illustrating a configuration example of a two-divided filter bank group that realizes one-dimensional DWT.
FIG. 23 is a schematic diagram illustrating a configuration example of a two-divided filter bank group that realizes a one-dimensional IDWT.
FIG. 24 is a diagram schematically showing image data subjected to two-dimensional DWT.
[Explanation of symbols]
1 Filter coefficient converter
Second order determination means
3 Rounding value selection means
4 Condition judging means
90 Lifting coefficient converter
91 Order determining means
92 Search range determining means
93 Coefficient evaluation means
94 Coefficient extraction means

Claims (12)

Filter coefficients of the decomposition side filter group for realizing the discrete wavelet transform for compressing the image signal and the synthesis side filter group for realizing the inverse discrete wavelet transform for decoding the compressed image are real type filter coefficients. Is a filter coefficient conversion method for converting into an integer type filter coefficient expressed by a fraction,
(A) determining an order M of a denominator of an integer type filter coefficient N / 2 ^M (N, M: an integer of 1 or more) of a conversion destination;
(B) A numerator N of the integer filter coefficient is selected so that a difference absolute value between the integer filter coefficient and the real filter coefficient is minimized, and a sequence of integer filter coefficients on the decomposition side is determined as the sequence And calculating the numerator N of the center coefficient to an even number ,
(C) calculating a synthesis-side integer filter coefficient series using the decomposition-side integer filter coefficients calculated in the step (b);
(D) The condition that the absolute value of the sum of the even-numbered coefficients and the absolute value of the sum of the odd-numbered coefficients of the synthesis-side integer filter coefficients calculated in the step (c) match. Determining whether or not to do;
A filter coefficient conversion method comprising: 2. The filter coefficient conversion method according to claim 1, wherein in the step ( c), the synthesis-side integer filter coefficient series includes the decomposition-side integer filter coefficient and the synthesis-side integer filter coefficient. The filter coefficient conversion method is calculated using the condition that satisfies the orthogonality . A filter coefficient conversion method according to claim 1 or 2,
(F) Standardization that, among the decomposition-side integer filter coefficients calculated in the step (b), the absolute value of the sum of the filter coefficients of the low-pass filter in the decomposition-side filter group matches a predetermined value. Determining whether a condition is satisfied,
A filter coefficient conversion method further comprising : The filter coefficient conversion method according to any one of claims 1 to 3,
(G) When an alternating signal that alternately takes a value of plus or minus 1 is applied to a high-pass filter in the decomposition-side filter group using the decomposition-side integer filter coefficient calculated in the step (b) Calculating the absolute value of the sum of the responses of and determining whether a normalization condition that the absolute value matches a predetermined value is satisfied,
A filter coefficient conversion method further comprising: 5. The filter coefficient conversion method according to claim 1, wherein the filter group includes an FIR filter having a finite tap . A filter coefficient conversion method according to claim 5, wherein said FIR filter is of 9 × 7 taps Dobishisu (Daubechies) filter, the filter coefficient transform methods. Filter coefficients of the decomposition side filter group for realizing the discrete wavelet transform for compressing the image signal and the synthesis side filter group for realizing the inverse discrete wavelet transform for decoding the compressed image are real type filter coefficients. A filter coefficient conversion device for converting to an integer filter coefficient expressed in fractions,
  Integer filter coefficient for conversion N / 2 ^M Order determining means for determining the order M of the denominator of (N, M: an integer equal to or greater than 1);
  The numerator N of the integer type filter coefficient is selected so that the difference absolute value between the integer type filter coefficient and the real number type filter coefficient is minimized, and the decomposition type integer type filter coefficient obtained by rounding the real type filter coefficient Rounding value selection means for calculating the series by limiting the numerator N of the center coefficient of the series to an even number;
  Coefficient calculating means for calculating a sequence of integer filter coefficients on the synthesis side using the integer filter coefficients on the decomposition side calculated by the rounded value selection means;
  Condition determining means for determining whether or not the condition that the absolute value of the sum of the even-numbered coefficients and the absolute value of the sum of the odd-numbered coefficients of the integer-type filter coefficients on the combining side is satisfied,
A filter coefficient conversion apparatus comprising: The filter coefficient conversion device according to claim 7,
The synthesis-side integer filter coefficient series is calculated using a condition that the decomposition-side integer filter coefficient and the synthesis-side integer filter coefficient satisfy bi-orthogonality.
Filter coefficient conversion device. The filter coefficient conversion device according to any one of claims 7 and 8 ,
The condition determination means further satisfies a normalization condition that an absolute value of a sum of filter coefficients of a low-pass filter in the decomposition-side filter group of the decomposition-side integer filter coefficients matches a predetermined value. A filter coefficient conversion device comprising means for determining whether or not . The filter coefficient conversion device according to any one of claims 7 to 9 ,
The condition determining means further uses the integer filter coefficient on the decomposition side to generate a response when an alternating signal that alternately takes a value of plus or minus 1 is applied to a high-pass filter in the filter group on the decomposition side. A filter coefficient conversion device comprising means for calculating an absolute value of a sum and determining whether a normalization condition that the absolute value matches a predetermined value is satisfied . The filter coefficient conversion apparatus according to any one of claims 7 to 10, wherein the filter group includes an FIR filter having a finite tap . 12. The filter coefficient conversion apparatus according to claim 11 , wherein the FIR filter is a 9 × 7 tap Daubechies filter .

Images