對有損及無損的2－d數據壓縮的可逆轉換的製作方法
2023-06-19 04:28:56
專利名稱：對有損及無損的2－d數據壓縮的可逆轉換的製作方法
技術領域：
本發明一般涉及基於塊轉換的數字媒體(如視頻和圖像)壓縮。
背景技術：
基於塊轉換的編碼轉換編碼是用於許多音頻、圖像和視頻壓縮系統中的壓縮技術。未壓縮的數字圖像和視頻通常表示成在安排成二維(2-D)網格中的圖像或視頻幀的位置處的圖形元素的或顏色的樣本，並按此形式捕捉。這稱為圖像或視頻的空間域表示。例如，圖像的通常格式包括安排成網格的24比特的彩色圖形元素樣本的流。每個樣本是一個數，表示在如RGB、或YIQ等顏色空間內網格中象素位置處的顏色成分。各種圖像和視頻系統可使用採樣的各種不同的顏色、空間和時間解析度。類似地，數字音頻通常表示成按時間採樣的音頻信號流。例如，通常的音頻格式包括以規則的時間間隔採集的音頻信號的16比特幅值樣本的流。
未壓縮的數字音頻、圖像和視頻信號會消耗大量的存儲和傳輸容量。轉換編碼通過將信號的空間域表示轉換成頻率域(或其他類似的轉換域)表示，並隨後降低該轉換域表示的某些通常較少可感知的頻率分量從而減少了數字音頻、圖像和視頻的大小。與減少圖像或視頻在空間域中顏色或空間解析度或減少音域在時間域的解析度相比，這通常產生數位訊號少得多的可感知的質量降低。
更具體說，圖1中示出的典型的基於塊轉換的編解碼器100將未壓縮的數字圖像的象素劃分成固定大小的二維塊(X1…Xn)，每塊可能與其他塊交疊。進行空間一頻率分析的線性轉換120-121被應用到每一塊，將塊中的空間樣本轉換成通常表示在該塊間隔上對應頻帶內數位訊號的強度的一組頻率(或轉換)係數。為了壓縮，轉換係數可以有選擇地量化130(即如通過丟棄係數值的低有效位比特或將較高解析度數據集的值設成低解析度來降低解析度)，並熵編碼(entropy)或變長度編碼130成壓縮的數據流。在解碼時，轉換系統逆向地轉換170-171，以近似地重建原始的顏色/空間採樣的圖像/視頻信號(重建塊 塊轉換120-121可定義成在大小為N的矢量x上的數學運算。最常用的運算是線性乘法，產生轉換域輸出y＝Mx，M是轉換矩陣。當輸入數據任意長時，它被分段成N大小的矢量，且對每一段應用塊轉換。為了數據壓縮的目的，選擇可逆的塊轉換。換言之，矩陣M是可逆的。在多維情況(如圖像和視頻)，塊轉換通常作為可分離的操作實現。沿著數據的每個維度(即行或列)可分別地應用矩陣乘法。
為了壓縮，轉換係數(矢量y的分量)可以有選擇地量化(即如通過丟棄係數值的低有效位比特或將較高解析度數據集中的值映射成低解析度來降低解析度)，並還熵編碼或變長度編碼成壓縮的數據流。
在解碼器150中的解碼時，如圖1所示在解碼器150方應用這些操作的逆(解量化/熵解碼160和逆塊轉換170-171)。在重建數據時，應用逆矩陣M-1(逆轉換170-171)，作為轉換域數據的乘子。在應用到轉換域數據時，逆轉換近似地重建原始的時間域或空間域數字媒體。
在許多基於塊轉換的編碼應用中，轉換希望是可逆的，以根據量化因子同時支持有損和無損壓縮。例如，對於無量的情況(通常表示成量化因子為1)，利用可逆轉換的編解碼器能在解碼時精確地再現輸入數據。然而在這些應用中的可逆性要求限制了在設計編解碼器方面的轉換的挑選。
諸如MPEG和Windows Media等的許多圖像和視頻壓縮系統使用基於離散餘弦轉換(DCT)的轉換。眾所周知，DCT具有導致幾乎最優數據壓縮的令人滿意的能量緊緻特性。在這些壓縮系統中，在壓縮系統的編碼器和解碼器內的重建環路中採用逆DCT(IDCT)來重建各個圖像塊。DCT由N.Ahmed，T.Nalarajan和K.R.Rao，「Discrete Cosine Transforme」，IEEE Transaction on Computers，C-23(January 1974)，pp 90-93描述。在「IEEE Standard Specification forthe Implementations of 8×8 Inverse Discrete osine Trnform」，IEEEStd，1180-1990，December 6，1990中描述IDCT的示例實施。
用於實現可逆2D數據壓縮器的傳統數據轉換通常受到一個或多個下列主要缺點的困擾，1.在需要複雜的熵編碼方案的各轉換係數之間不相等的範數；2.對如DCT那樣最優轉換的不良近似；和3.高計算複雜性。
2D轉換的常規實現可分離的2D轉換通常通過對數據的各行完成1D轉換，隨後對數據的列的1D轉換來實現(反之亦然)。見A.K.Jain，Fundamentals of Digital ImagePrecessing，Prentice Hall，1989。在矩陣表示中，令T表示轉換矩陣而X是2D數據。用T的可分離2D轉換由下式中的Y定義Y＝TXT』 (1)確實，行方向和列方向轉換可以是不同的，例如，數據矩陣可以是非方形的(如大小為4×8)，或行方向和列方向轉換可分別是DCT和離散的正弦(DCT)轉換。在此情況，前乘子和後乘子是不同的(T1和T2)，且轉換由下式給出。
Y＝T1×T』2(2)例如圖2示出以兩階段實現的2D 4×4DCT。第一階段中，使用4點1D DCT轉換數據矩陣的諸列。在第二階段，沿著行應用4點1D DCT。帶著無限的算術精度，此次序可交換而不改變輸出。
4點1D DCT能作為在4個輸入數據值上的乘法和加法運算的序列實現，如圖3所示的信號流圖表示。在此示意圖中的值c和s分別是π/8的餘弦和正弦。對有損編解碼器此可分離的轉換方法效果很好。無損編解碼器更難以實現。即使用單位量化，上述結合其可分離的逆DCT或IDCT描述的可分離的2D DCT也不保證產生與原始輸入的精確到比特的匹配。這是由於圖3中的除數引起在編碼器和解碼器之間不能抵消的捨入誤差。
提升為了用基於塊轉換的編解碼器實現無損壓縮，必須用無損轉換代替上述4×42D DCT。僅當每個1D轉換是無損或可逆的，才可使用可分離的轉換。雖然對可逆1D轉換存在多種選擇，但基於「提升(lifting)」的選擇是最希望的。提升是使用逐次「剪切(share)」進行矩陣-矢量乘法的過程。剪切定義成操作數向量與矩陣的乘法，該矩陣是一個單位矩陣加上一個非零的非對角元素。在此過程期間的任何處可發生一個或多個矢量系統的符號逆轉而不失一般性。
過去，提升通過階梯或格柵過濾器結構實現。提升或基於逐次剪切的技術已在圖解法中使用。見A.Tanaka，M.Kameyame，S.Kazama，和O.Watanabe，「Arotation method for raster image using skew tramformation」，Proc.IEEEConf.On Computer Vision和Pattern Recognition，pages 272-277，June 1986；和A.W.Paeth，「A fast algorithm for general raster rotation，」Proceedings of Graphics Interface』86，pages 77-81，May 1986。事實上可認為Gauss-Jordan消元法是提升的表現形式。
一個簡單的2點運算是由轉換矩陣TH=12111-1]]>給出的Hadamard轉換。為實現基於提升(可逆的)1D Hadamard轉換通常採用兩種方法。第一個是如圖4所示在提升步驟中實現歸一化的或與比例無關的Hadamard轉換。第二方法是如圖5所示允許比例在兩個轉換係數之間不同。
使用提升的問題提升不是沒有問題。在圖4所示的第一Hadamard轉換方法中，兩個轉換係數被歸一化。對實現諸如4或8點DCT的多級轉換這是希望的。然而，此實現方法受到兩個主要缺點的困擾一首先，每個2點Hadamard轉換需要三個非一般的(即大計算量的)提升步驟，而其次，在諸提升步驟的捨入誤差會導致低通能量「洩漏」到高頻項，引起壓縮效率的降低。在此第一方法中，使用近似tan(8)38]]>和cos(4)34]]>導致AC基本函數
。雖然與要求的
的差異看來不是過分大，幅值64的DC信號產生洩漏到編碼更花費時間的高頻帶的2單位的AC響應。
第二方法(圖5)使用普通的提升步驟。然而，低通項用 因子放大，而高通項用 因子縮小(或相反)。兩個係數的解析度有1比特的不同。在兩維中，與低-低項相比高-高項在解析度中低2比特。串聯的轉換階段只會增加差異。由於係數的不同範圍熵編碼更難以實現。
總之，用基於提升的無損轉換的問題是1.在各轉換係數之間可能的不相等比例，使得熵編碼機制更複雜。
2.對希望的轉換基本函數的不良近似，這會引起如DC洩漏到AC帶的不希望的效果。
3.潛在的高計算複雜性，尤其是若基於提升的實現設計成很好近似於希望的轉換。
發明內容
數字媒體編碼/解碼系統基於可分離的2D塊轉換，它具有涉及現有技術轉換的所述問題和缺陷的在此描述的各種實現。尤其是，可分離的2D轉換及其逆的對的所述實現具有一系列為減少計算的複雜度(即減少非一般的運算的數目)安排的提升步驟。此轉換對具有類似於DCT的能量緊緻特性，並還是無損及與比例無關的。術語「無損」意為對轉換的原始整個輸入能被恢復而若假設無量化因素沒有由於從其整體轉換係數的逆轉換產生的誤差。「與比例無關」指的是轉換對的基本函數被相等地確定比例，它也意味著最終的轉換矩陣是正交的。
此轉換對的一個所述實現是4×4轉換，但也能擴展到其他大小(如8×8)。此外，可使用轉換對的串聯來實現分級的金字塔結構和更大的轉換。例如，一個所述實現使用轉換的兩級串聯。在第二轉換階段，轉換被應用到在宏功能塊中產生的16個DC係數。因為轉換類似於DCT，它可用於實現帶有極好的速率一失真性能和壓縮效率的無損到有損的數字媒體編解碼器(即其量化參數能從無損設置到有損設置變化的編解碼器)。
本發明的另外特徵和優點將從下面參考附圖進行的實施例的詳細描述明白。
圖1是現有技術傳統的基於塊轉換的編解碼器的方框圖。
圖2是現有技術中在兩階段實現的2D 4×4 DCT的方框圖。
圖3是現有技術中ID 4×4 DCT的信號流圖。
圖4是現有技術中使用提升的歸一化的2-點Hadamard轉換的信號流圖。
圖5是現有技術中普通的2-點Hadamard轉換轉換的信號流圖。
圖6是基於改善的可逆2D轉換的編碼器的流程圖。
圖7是基於改善的可逆2D轉換的解碼器的流程圖。
圖8是可逆2×2Hadamard轉換的歸一化的基於提升的實現的信號流圖。
圖9是以C程式語言寫的用於實現圖8的歸一化的可逆2×2Hadamard轉換的程序表。
圖10是圖8的歸一化可逆2×2Hadamard轉換之逆的信號流圖。
圖11是Jodd轉換的歸一化的基於提升的實現的信號流圖。
圖12是用於實現圖11的歸一化Jodd轉換的以C程式語言寫的程序表。
圖13是圖11的Jodd轉換之逆的歸一化的基於提升的版本的信號流圖。
圖14是Jodd-odd轉換的歸一化的基於提升的實現的信號流圖。
圖15是用於實現圖14的歸一化Jodd-odd轉換的以C程式語言寫的程序表。
圖16是圖14的Jodd-odd之逆的歸一化的基於提升的版本的信號流圖。
圖17是示出轉換和逆轉換運算的圖中2×2數據的排序的示意圖。
圖18是示出當1D垂直DCT和1D水平DCT分別應用到4×4數據輸入的列和行時分別實現的2D DCT的信號流圖。
圖19是示出通過在兩個階段交替水平和垂直轉換操作實現的可逆的與比例無關的2D轉換的信號流圖。
圖20是示出在圖6的編碼器中實現改善的可逆2D轉換的第一階段中對其應用圖8的2×2Hadamard轉換的4×4的數據塊的點的示意圖。
圖21是示出在圖6的編碼器中實現改善的可逆2D轉換的第二階段中對其應用圖8的2×2Hadamard轉換、圖11的Jodd轉換、和圖14的Jodd-odd轉換的4×4轉換係數塊的點的示意圖。
圖22是示出在圖7的解碼器中實現逆2D轉換的第一階段中對其應用圖8的2×2Hadamard轉換、圖11的Jodd轉換、和圖14的Jodd-odd轉換的4×4轉換係數塊的點的示意圖。
圖23是示出用於圖6的編碼器和圖7的解碼器中的正和逆2D轉換的轉換係數的排序的示意圖。
圖24是用於實現帶有圖6和圖7的改善的空間—域交疊的轉換的基於塊轉換的編解碼器的合適計算環境的方框圖。
圖25是用於圖11和14中示出的可逆2×2轉換的歸一化基於提升的實現的結構的信號流圖。
具體實施例方式
下面描述涉及到利用改善的可逆的與比例無關的2D轉換的數字媒體壓縮系統或編解碼器。為說明起見，結合改善的轉換的壓縮系統的實施例是圖像或視頻壓縮系統。另外，改善的轉換也能加入到其他2D數據的壓縮系統或編解碼器，轉換不要求數字媒體壓縮系統以特定編碼格式編碼經壓縮的數字媒體數據。
1.編碼器/解碼器圖6和7是在基於下面詳述的改善的可逆的與比例無關的2D轉換650的代表性2維(2D)數據編碼器600和解碼器700中採用的過程的普遍的示圖。該圖給出在加入2D數據編碼器和解碼器的壓縮系統中使用和應用此轉換的普通的和簡化的圖示。在基於此轉換的可選編碼器中，對2D數據壓縮可使用比在此代表性編碼器的解碼器中示出的過程有附加的或更少的過程。例如，某些編碼器/解碼器也可包括顏色轉換、顏色格式、比例編碼、無損編碼、宏功能塊模式等。改善的2D轉換允許壓縮系統(編碼器和解碼器)根據基於量化參數從無損到有損變化的量化提供2D數據的有損和/無損的壓縮。
2D數據編碼器600產生壓縮的比特流620，它是作為該編碼器的輸入給出的2D數據610的更緊緻表示(對典型輸入而言)。例如，2D數據輸入可以是圖像、視頻序列的幀，或其他具有二維的數據。2D數據編碼器將輸入數據鋪墊(630)成宏塊，在此代表性編碼器中它們是16×16象素大小。2D數據編碼器還將每一宏塊鋪墊成4×4塊(632)。「正向交疊」操作符(640)被應用到在塊之間的每條邊界，此後使用可逆的與比例無關的轉換(650)轉換每個4×4的塊。接著每個4×4轉換塊的DC係數660經過類似的處理鏈(鋪墊、正向交疊、隨後4×4的塊轉換)。最終的DC轉換係數和AC轉換係數被量化(670)、熵編碼(680)並包裝化(690)。
解碼器執行逆過程。在解碼器方，從它們的相應包提取(710)轉換係數比特，從中係數本身被解碼(720)和解量化(730)。通過應用逆轉換重新生成DC係數(740)，而DC係數的平面(plane)使用穿過DC塊邊界應用的合適的平滑算符被「逆交疊」。接著，通過將4×4逆轉換(750)應用到從該比特流解碼的DC係數和AC係數(742)重新生成整個數據。最後，在最終圖像平面中的塊邊界是經過濾的逆向交疊(760)。這就產生重新構造的2D數據輸出。
2.改善的可逆的與比例無關轉換的實現如由A.K.Jain，Fundamentals of Digital Image Processing，PrenticeHall.1989中所述，可分離的2D轉換可作為在1D中排序的數據上操作的1D轉換實現，產生類似的排序的矢量結果。由在可分離情況中使用的前乘子和後乘子的Kronecker乘積產生等價的轉換矩陣。若x和y標記從在(2)中的它們的2D表示重新排離的數據和轉換向量，它們的關係由下式給出y＝Jx (3)其中J＝Kron(T1，T2)。
雖然等式(2)中示出的2D轉換的可分離實現在計算上比等式(3)中的更有效(在漸近的意義上)存在某些情況，後者的表示導出希望的特性。例如，由於單級矩陣乘法(它本意上是在若干數位訊號處理器(DSD)上支持的操作)基於等式(3)的實現比等式(2)具有較低的等待時間。對於這裡描述的改善的可逆的與比例無關的轉換，2×2步驟的1D表示導致與比例無關的可逆結構。
此外，可分離的2D轉換能作為較簡單的1D轉換的串聯實現。假設轉換矩陣T1和T2能如下分解T1＝T1AT1B(4)T2＝T2AT2B矩陣乘法運算的關聯性可如下用於重新排序2D轉換(2)Y＝T1×T2′＝(T1AT1B)×(T2B′ T2A′)＝T1A(T1B×T2B′)T2A′(5)導致串聯的1D實現。
y＝Kron(T1A，T2A)·Kron(T1B，T2B)·x (6)諸如DCT的轉換可被公式化成基本的2點轉動運算的串聯。能使用(6)的結構公式化2D DCT，使具有某些希望的特性，這將在下面詳述。
A.2D Hadamard轉換作為1D運算實現的2D Hadamard轉換通過Kronecker乘積產生，JH=Kron(TH,TH)=1211111-11-111-1-11-1-11---(7)]]>有趣的是可能只使用普通的提升步驟實現對應等式(7)的與比例無關的可逆轉換。此方式的實現示作在圖8中的信號流圖800。在圖9中示出消除某些多餘運算的相應C++代碼。在此代碼表900中，「swap(x，y)」是交換其自變量值的函數。
從上述可見，能只使用普通的提升步驟公式化歸一的可逆2D Hadamard轉換，雖然對可爭議的「更簡單的」1D Hadamard情況這是不可能的！雖然轉換矩陣本身是對合的(好JH是其本身的逆)，無損重建要求提升步驟被小心地求逆使能精確地再現任何捨入影響。在圖10中給出圖8中結構800的逆1000-在此情況結構1000等同於正轉換。注意，轉換係數B和C在信號流圖中被置換。
在圖6的編碼器600中的可逆的與比例無關的2D轉換650使用對4×4DCT的近似。下面描述證明了轉換650的整個轉換過程能作為三個基本2×2轉換運算的串聯實現，它們是2×2Hadamard轉換和Odd rotateY＝TR×TH′Odd-odd rotateY＝TR×TR′ (8)其中二點旋轉矩陣TR如下給出TR=14+221+211-(1+2)---(9)]]>通過計算前轉換和後轉換矩陣的Kronecker乘積(近似到4位小數)獲得等式(8)的1D實現J^odd=Kron(TR,TH)=0.65330.65330.27060.27060.6533-0.65330.2706-0.27060.27060.2706-0.6533-0.65330.2706-02706-0.65330.6533---(10)]]>和J^odd-odd=Kron(TR,TR)=0.85360.35360.35360.14640.3536-0.85360.1464-0.35360.35360.1464-0.8536-0.35360.1464-0.3536-0.35360.8536---(11)]]>記號^表示希望的轉換矩陣。從實際實現得出的近似不帶此記號。對2×2Hadamard轉換，希望的轉換矩陣和它的近似是等同的。因而，JH用於標記在1D中實現的2×2Hadamard轉換而沒有任何二義性。接著，我們注意Jodd和Jodd-odd的提升實現。
B.Jodd的實現Jodd轉換1100的與比例無關的基於提升的實現示作圖11中的信號流圖和圖12中的C++代碼程序表1200。可以看到，第一和最後的提升階段等同於Hadamard轉換情況，除了普通的剪切處，在中間階段應用兩個非一般的提升旋轉。每個非一般的旋轉以三個步驟實現，乘3和移位3或4個比特。因而通過使用6個非一般的提升步驟，Jodd能以可逆的與比例無關的方式實現。
得出的ID轉換矩陣Jodd示於下面等式(12)，它與(10)中 的原始公式近似一致。可以看到得到的矩陣的第二和第四行之和為零，這意味著沒有DC洩漏到AC帶。雖然需要的2D旋轉只是在結構中的近似，但達到了希望的特性。
Jodd=0.64580.64580.28390.28390.6523-0.65230.2773-0.27730.27730.2773-0.6523-0.65230.2839-0.2839-0.64580.6458---(12)]]>雖然旋轉矩陣Jodd是對合的(即它是本身的逆)，在信號流圖或代碼的兩次順序的應用中捨入誤差不會消除。在信號流圖或C++代碼中通過提升步驟求逆導出Jodd的無損逆，以複製正轉換方面的捨入誤差。在圖13中示出Jodd的逆1300的信號流圖一代碼能類似地導出。
C.Jodd-odd的實現Jodd-odd轉換1400是兩次旋轉構成的，它們均不是Hadamard轉換。有趣的是Jodd-odd能用比Jodd更少的非一般提升步驟實現。這是由於TR與其本身的Kronecker乘積的對稱屬性。在圖14和15中分別示出Jodd-odd轉換1400的信號流圖及其C++代碼的程序表1500。
可以看到，為實現Jodd-odd只藉助三個非一般提升步驟實現的一個非一般的旋轉是需要的。此旋轉對應於與比例無關的lD 2一點Hadamard轉換。
Jodd-odd=0.85940.32230.32230.14060.3750-0.85940.1406-0.37500.37500.1406-0.8594-0.37500.1406-0.3223-0.32230.8594---(13)]]>關於這裡考慮的其他轉換，在等式(13)中表示的Jodd-odd是對合的，雖然不是其本身的精確到比特的逆。如圖16所示，通過對用於正轉換的信號流圖的求逆獲得Jodd-odd的無損的逆1600。
D.上述2×2轉換實現的標記法和推導在這裡使用這些三個可逆的與比例無關的轉換的可逆的與比例無關的2D轉換的描述中應用下列要點。首先，在圖17中示出導致上面信號流圖和C++代碼的2×2數據的排序1700。在左邊示出空間域點，在右邊示出對應的頻率域點。這裡引入使用4個灰度級表示4個數據點的顏色編碼，以便於下面對可逆的與比例無關的2D轉換的描述。
2點轉換或旋轉常常定義成下述運算y=cossin-sincosx---(14)]]>而不是對合形式y=cossinsin-cosx---(15)]]>這兩個公式基本上等同，因為它們僅在第二轉換係數的符號上有差別。這裡使用後一個表示(15)，雖然本文檔中的整個推導同樣可應用到前一公式(14)。
上面定義的基本2×2轉換JH、Jodd和Jodd-odd的結構通過注意到每個2點轉換是旋轉而被構造。此外，二個2點旋轉的Kronecker乘積如下給出T=Kroncossin-sincos,cossin-sincos---(16)]]>然後我們定義算符H如下H=1000010001/210-1/2001100101-1000100001---(17)]]>H代表非歸一化雙蝶形運算，並能使用提升有效地實現。
下面的分解有HKroncossin-sincoscossin-sincosH-1=cos(-)-sin(-)00sin(-)cos(-)0000cos(+)sin(+)00-sin(+)cos(+)]]>基於此，類型T的Kronecker乘積能作為3個階段的串聯實現
A.通過使用提升步驟的H定義的雙蝶形運算。
B.在第一對組件之間及在第二對組件之間的2點旋轉，和C.在步驟A中執行的雙蝶運算的逆。
對專門的情況JH，甚至存在更簡單的分解，它在圖8中示作信號流圖800，並如上描述。對其他情況(如Jodd和Jodd-odd)，最終結構能歸納為如圖25所示的流圖2500。
注意上述轉換(還有它們的逆)的信號流圖，觀察在它們結構中的基本相似性。轉換的第一階段是在a-d和b-c係數之間的提升運算。類似地，最後階段是逆提升過程(忽視符號和係數交換)。相應地，逆轉換的第一階段是在A和D之間和在B和C之間的提升運算，在最後階段是逆運算。在對角元素之間的提升步驟是這裡給出的組合的2D 2×2轉換的顯著特徵。
下一節討論近似4×4DCT/IDCT的無損的與比例無關的轉換的結構。雖然在此詳細的技術討論中給出轉換的一個示例實施例，使能用帶有其他2×2的基本可逆的基於提升的轉換的附加定義的同樣過程，以產生帶有希望特性的更高難數的可逆轉換的實施例。
E.無損的，與比例無關的轉換如圖3的信號流圖中所示，4點DCT能縮減成4個蝶形運算的序列。第一階段包括在輸入數據上執行2點Hadamard運算(即輸入數據索引號0和3的一個2點Hadamard運算；和輸入索引號1和2的第二個Hadamard運算)的兩個蝶形運算。第二階段包括產生偶數頻率分量(索引號0和2)的第一階段的低通結果的一個2點Hadamard運算和產生奇數頻率分量(索引號1和3)的一個2點旋轉π/8。
在兩個維度中，DCT能分別地實現每個4×4輸入數據的列的垂直1D 4點DCT；隨後是各行的水平1D 4點DCT(或相反)。在圖18中這畫成可分離的DCT實現1800。另外，如圖19的交叉DCT實現1900所示，使用等式(5)的原理，上述兩個1D DCT階段可在水平和垂直方向之間交替。
此外，在遵循上述方法時可進一步組合相應的垂直和水平階段。例如，第一階段是在「內部」和「外部」輸入元素上的2點Hadamard轉換。水平和垂直階段能合併成在16個輸入數據元素上的4次應用2×2 2D Hadamard轉換，每次轉換被應用到輸入點的對稱組。同樣地，第二階段的水平和垂直步驟可合併成一個2×2Hadamard轉換和三個2×2轉換，其中兩個是移項。應看到，後三個2×2轉換實際上是以前定義的Jodd和Jodd-odd轉換的2D再映射。
更具體說，通過重新安排各轉換運算成2×2Hadamard、Jodd和Jodd-odd轉換的排列實現可逆的與比例無關的2D轉換650(圖6)。此轉換650的兩個階段分別如圖20和圖21中所示那樣完成。每個階段包括4個2×2轉換，它們可在階段中以任何次序、或同時執行。
對逆2D轉換750(圖7)，諸階段次序上相反，且在每個轉換階段內的步驟使用在正轉換過程中的步驟的逆。如前指出，可逆2×2Hadamard轉換JH在精確到比特或無損的意義上是其自己的逆。因而，逆光子(Photon)轉換的第二階段僅是正光子轉換的第一階段，如圖20所示。在圖22中畫出逆光子轉換的第一階段2200。在此階段的4個步驟(對於正轉換情況，這能以任意次序或同時執行)應用如前定義的JH、Jodd和Jodd-odd的逆，並重映射回到2D 2×2空間。
在遵循圖20和圖21中示出的改善的正2D轉換的步驟之後，得到的轉換係數如圖23所示那樣排序。在那個次序中，對於使用圖22和20中的步驟逆轉換的係數採取同樣的排序2300。
正2D轉換650的上述改善實現包括對每個4×4塊的JH的5次應用、Jodd的2次應用和Jodd-odd的1次應用。在逆2D轉換750的實現中包括這些轉換同樣數目的應用。因此，對每一塊非一般提升步驟步驟的總數是5×0+2×6+1×3＝15，以實現無損的正或逆2D轉換。這是約每個象素1個非一般步驟。非一般步驟是公式(3×x+r)＞＞k的運算，其中x是運算數，r和k是確定捨入和比特移位的常數。k是2、3或4。類似地，每個塊存在17個單位置的右移位(即x＞＞1)。加、減和非操作不計在此總計之中。
在比較中，考慮在圖18中示出的2D DCT的可分離的實現1800。假設，每個4點DCT使用3個如圖3所示的2點歸一化Hadamard運算實現，且使用3個非一般提升步驟實現旋轉π/8。對正或逆轉換每個4×4塊的非一般提升運算的總數是2×4×3＝24。單個位置右移的總數也是24。這些數目比改善的正轉換650和逆轉換750的實現高約50％，不考慮最終的轉換產生帶範圍在1/4到2的(或若避免無理數範圍的基本函數，到4)範數的基本函數的事實。相反，改善的轉換650的所有基本函數是單位範數。
F.對4:2:0顏色空間的改善的轉換在編碼器600(圖6)和解碼器700(圖7)的一個示例實施例中，使用YUV4:2:0顏色空間來表示在圖像(或視頻幀)中象素的顏色。在此示例的編解碼器中，在YUV 4:2:0顏色空間中的宏功能塊被定義成亮度(Y)通道中象素的16×16鋪墊塊，和在色度(U和V)通道中的8×8鋪墊塊。這些被進一步分成4×4塊，它們使用上述轉換650被編碼轉換。4×4轉換650被應用到亮度通道的DC係數。然而，在一個宏功能塊中只可得到2×2色度樣本。然後，示例的編解碼器將JH應用於每個宏功能塊中DC色度值應用，如上所述，JH是可逆的與比例無關的2×2Hadamard轉換。因此，保持示例編解碼器格式的宏功能塊結構，且為了處理4:2:0格式在編解碼器中無需引入另外的轉換。
G.最小化捨入誤差在包括右比特移位的JH、Jodd和Jodd-odd轉換的提升步驟中引入捨入誤差。這些捨入誤差具有已知的偏差，並能在轉換過程中建立。例如，已知，公式x+＝(y＞＞1)的步驟與其數學等價x＝x+y/2相比導致x的值中-1/4的偏差。這是因為(y＞＞1)是下捨入的除以2，若y是偶數它是精確的，若y是奇數差1/2。因而概率上看，它偏差-1/4。在包括提升的整數到整數轉換中捨入誤差是不可避免的，但希望在整個系統中使偏差極小化。
前面示作C++編碼片斷的JH、Jodd和Jodd-odd的公式對被除或右比特移位的操作數增加了變化的因素。選擇這些因素使偏差最小化。尤其是，在使用圖9中C++代碼表900的JH的(到無偏差輸入的)第一階段運算之後在4個轉換係數中的偏差可示作[1/4-1/4-1/4-1/4]。在改善的2D轉換650(圖6)中的JH的第二階段在第一階段的DC值上運算，即在已經偏差1/4的係數上運算。第二階段運算的結果產生[3/4-1/4-1/4-1/4]的偏差。因為第一係數是DC的DC，可預期是大的，且3/4的相對較高的偏差不影響編碼性能。
為了最小化轉換偏差，在Jodd和Jodd-odd中的非一般提升步驟提供選擇捨入因素的自由度。對Jodd-odd的C++編碼表1500(圖15)示出，有時候偏離中心的捨入規則(如a+＝(3b+5)＞＞3)導致更小的整體偏差，尤其是當輸入數據本身偏差時。對改善的2D轉換步驟Jodd和Jodd-odd，所有輸入偏差到-1/4。
通常，編解碼器的定義限於位流解碼器的定義。此規則的一個例外是對無損編解碼器作出的，因為為了無損重建的輸入數據編碼器和解碼器必須完全匹配。在有損到無損的編解碼器的情況中，這在編碼器和解碼器雙方定義。然而，當編碼器以純有損方式操作時，某些截斷或增強是可能的，它給出比在編解碼技術規範中定義的基線性能更好的性能(在速率一失真，或計算周期計算方面)。
改善編碼器性能的一個方法關係到轉換係數偏差。在編碼器600/解碼器700的某些實施例中通過對每個4×4的塊完成下列過程有可能減少偏差的影響1.通過乘m＝2k(通常m＝4效果很好)放大4×4塊。
2.在該塊上完成改善的2D轉換650。
3.使用量化器量化該塊，量化器是最初希望的量化參數的m倍(例如若在步驟1希望的QP是8且m＝4，則使用量化因子(QP)32)。
在解碼器700方沒有改變，在同一比特速率下可能有更好的PSNR數。當然，對無損編碼它不能用。
3.計算環境上述帶有改善的可逆的與比例無關的2D轉換的編解碼器可以在各種執行數字媒體信號處理的設備的任一個上執行，包括計算機；圖像和視頻記錄、傳輸和接收設備；可攜式視頻播放器；視頻會議等。數字媒體編碼技術能在硬體線路中和在如圖24所示的計算機或其他計算環境中執行的數字媒體處理軟體中實現。
圖24示出在其中實現描述的實施例的合適的計算環境2400的一般例子。計算環境(2400)對本發明的使用或功能範圍不試圖提出任何限制，因為本發明能在各種通用或專用計算中實現。
參考圖24，計算環境(2400)至少包括一個處理單元(2410)和存儲器(2420)。在圖24中，此大部分基本配置(2430)包括在虛線內。處理單元(2410)執行計算機可執行指令並可以是真實的或虛擬的處理器。在多處理系統中，多處理單元執行計算機可執行指令以增加處理能力。存儲器(2420)可以是易失存儲器(如寄存器、高速緩衝器、RAM)、非易失存儲器(如ROM、EEPROM、快閃記憶體等)或兩者的某種組合。存儲器(2420)存儲實現所述編碼器/解碼器和轉換的軟體(2480)。
計算機環境可具有另外特徵。例如，計算環境(2400)包括存儲裝置(2440)、一個或多個輸入設備(2450)、一個或多個輸出設備(2460)、和一個或多個通信連接(2470)。諸如總線、控制器、或網絡的互連機制(未示出)互連計算環境(2400)的諸組件。通常，作業系統軟體(未示出)為其他在計算環境(2400)中執行的軟體提供操作環境，並協調計算環境(2400)的諸組件的活動。
存儲裝置(2440)能是可移除的或不可移除的，並包括磁碟、磁帶或盒式磁帶、CD-ROM、CD-RW、DVD、或任何其他介質，它們有用於存儲信息並能在計算環境(2400)中被訪問。存儲裝置(2440)存儲用改善的SDLT實現編解碼器的軟體(2480)指令。
輸入設備(2450)能是接觸輸入設備，如鍵盤、滑鼠、輸入筆或軌跡球；語音輸入設備；掃描設備；或其他提供輸入到計算環境(2400)的設備。對聲頻，輸入設備(2450)可以是音效卡或以模擬或數字方式接收音頻輸入的類似設備、或提供音頻樣本給計算環境的CD-ROM閱讀器。輸出設備(2460)能是顯示器、印表機、擴音器、CD-寫入器或從計算設備(2400)提供輸出的其他設備。
通信連接(2470)使能通過通信媒體通信到另外計算實體。通信媒體傳遞諸如計算機可執行指令、存儲的音頻或視頻信息、或其他調製數據信號的數據等信息。調製數位訊號是具有以在信號中編碼信息的方式設置或改變的一個或多個特徵的信號。例如且不作限止，通信媒體包括用電、光、RF、紅外、聲音、或其它載體實現的有線或無線技術。
這裡的數字介質處理技術能在計算機可讀介質的一般情況中描述。計算機可讀介質是在計算環境中能被訪問的任何可用介質。例如而非限止，對計算環境(2400)，計算機可讀介質包括存儲器(2420)、存儲裝置(2440)、通信媒體、和上述的任何組合。
這裡的數字介質處理技術能以諸如包括在程序模塊中在真實或虛擬的目標處理器上的計算環境中執行的計算機可執行指令的一般環境中描述。通常，程序模塊包括例程、程序、庫、對象、類、組件、數據結構等，它們執行特定任務或實現特定的抽象數據類型。如在各種實施例希望那樣，程序模塊的功能可在程序模塊之間組合或分割。程序模塊的計算機可執行指令可在本地或分布式計算環境中執行。
為表示的原因，詳細描述使用如「確定」、「生成」、「調節」、和「應用」等術語以描述在計算環境中的計算機操作。這些術語是對由計算機執行的操作的高級抽象，且不應與人類執行的動作混淆。對應這些術語的實際計算機操作按其實現而改變。
考慮可應用本發明原理的許多可能的實施例，我們要求，可能落入下面權利要求及其等價物的範圍和精神的所有那些實施例為我們的發明。
權利要求
1.一種完成可逆的與比例無關的2維塊轉換的方法，所述轉換被定義成在數字媒體數據的2維塊上水平和垂直地應用的1維轉換，所述方法包括在二個或更多階段從水平和垂直的1維轉換的交替操作的每一個中，將在重新安排成一組作為提升步驟實現的基本轉換的相應階段中的操作應用到在2維塊中值的獨立子集。
2.如權利要求1所述的方法，其特徵在於，所述第一階段中還包括將2×2Hadamard轉換應用到在值的2維塊中的獨立4值子集。
3.如權利要求2所述的方法，其特徵在於，所述4值子集包括在2維塊的諸角處的4值的組；在2維塊的中心的4值的組；在2維塊的水平邊中心的4值的組；和在2維塊的垂直邊中心的4值的組。
4.如權利要求1所述的方法，其特徵在於，在所述第二階段中還包括將一組轉換應用到在值的2維塊中的獨立4值子集，所述轉換組中的至少一個以3階段的串聯形式實現，所述3階段包括由使用提升步驟的運算符H定義的雙蝶形運算，其中H=1000010001/210-1/2001100101-1000100001;]]>在第1對組件值之間和第二對組件值之間分別的2點旋轉；和所述雙蝶形運算之逆。
5.如權利要求1所述的方法，其特徵在於還在第二階段中包括將一組轉換應用到值的2維塊中的獨立4值子集，所述轉換組包括2×2Hadamard轉換、作為2點Hadamard轉換和2點旋轉矩陣的Kronecher乘積導出的2×2odd旋轉轉換、和作為諸2點旋轉矩陣的Kronecher乘積導出的2×2odd-odd旋轉轉換。
6.帶有減少捨入誤差偏差的權利要求1的方法，其特徵在於，所述方法還包括對包括除法或右比特移位的蝶形運算，在相應的蝶形運算之前添加變化因素到被除的或被右比特移位的操作數。
7.對有損壓縮帶有減少捨入誤差偏差的權利要求1的方法，其特徵在於，所述方法還包括在轉換前通過乘一因子縮放2維塊；執行所述轉換；和通過一量化器量化得到的轉換係數，所述量化器等於希望的量化器乘以所述因子。
8.執行權利要求1的2維轉換之逆的方法，執行所述逆的方法包括在2個或更多階段從水平和垂直的1維轉換的交替操作的每一個中，將在重新安排成作為提升步驟實現的一組基本轉換的相應階段中的操作應用到在2維塊中值的諸獨立子集。
9.如權利要求8所述的方法，其特徵在於，在所述第一階段還包括將一組轉換應用到值的2維塊中的獨立4值子集，所述轉換組包括2×2Hadamard轉換、作為2點Hadamard轉換和2點旋轉矩陣的Kronecher乘積導出的2×2odd旋轉轉換、作為各2點旋轉矩陣的Kronecher乘積導出的2×2odd-odd旋轉轉換。
10.如權利要求9所述的方法，其特徵在於，所述4值子集包括2維塊的左上、右上、左下、右下處的4個值的組。
11.如權利要求9所述的方法，其特徵在於，通過下列精確到4位小數的等式給出2×2Hadamard轉換、2×2odd旋轉轉換、和2×2odd-odd旋轉轉換 和
12.如權利要求8所述的方法，其特徵在於，還包括在所述第二階段將2×2Hadamard轉換應用到在值的2維塊中的獨立4值子集。
13.一個用基於塊轉換編碼執行2維數字媒體數據的有損/無損壓縮的有損/無損壓縮系統的編碼器，所述編碼器使用定義成垂直和水平地應用到數字媒體數據的2維塊的4點轉換的可逆的與比例無關的2維轉換，所述編碼器包括用於緩存要編碼的2維數字媒體數據的緩存存儲器；用於通過在兩個或更多階段的從水平和垂直的1維4點轉換的交替操作的每一個中，將在相應階段中重新安排成作為提升步驟實現的一組基本的2×2轉換的操作應用到在2維塊中獨立的4值子集，將所述轉換應用到數字媒體數據的2維塊的處理器。
14.如權利要求13所述的編碼器，其特徵在於，所述基本轉換包括2×2Hadamard轉換、作為2點Hadamard轉換和2點旋轉矩陣的Kronecher乘積導出的2×2odd旋轉轉換、作為各2點旋轉矩陣的Kronecher乘積導出的2×2odd-odd旋轉轉換。
15.如權利要求13所述的編碼器，其特徵在於，所述處理器在第一階段將2×2Hadamard轉換應用到包括在數字媒體塊的角、中心、頂/底邊和左—右邊處的4值組的相應數字媒體塊的4值子集。
16.如權利要求13所述的編碼器，其特徵在於，所述處理器在第二階段將2×2Hadamard轉換應用到在所述相應數字媒體塊的左上方的4值子集；將2×2Hadamard轉換、作為2×2Hadamard轉換和2點旋轉矩陣的Kronecher乘積導出的2×2odd旋轉轉換應用到在所述相應數字媒體塊的右上方及左下方的4值子集；和將作為所述2點旋轉矩陣與其本身的Kronecher乘積導出的2×2odd-odd旋轉轉換應用到在所述相應數字媒體塊的右下方的4值子集。
17.一個用基於塊轉換解碼執行壓縮的2維數字媒體數據的有損/無損解壓縮的權利要求13的有損/無損壓縮系統的解碼器，所述解碼器使用所述可逆的與比例無關的2維轉換的逆，所述解碼器包括用於緩存所述壓縮的2維數字媒體數據的塊的轉換係數的緩存存儲器；用於通過在兩個或更多階段的從水平和垂直的1維4點逆轉換的交替操作中的每一個，將在相應階段中重新安排成作為提升步驟實現的一組基本的2×2轉換的操作應用到在2維塊中獨立的4值子集，將所述逆轉換應用到數字媒體數據的2維塊的處理器。
18.如權利要求17所述的解碼器，其特徵在於，所述基本轉換包括2×2Hadamard轉換、作為2點Hadamard轉換和2點旋轉矩陣的Kronecher乘積導出的2×2odd旋轉轉換、作為各2點旋轉矩陣的Kronecher乘積導出的2×2odd-odd旋轉轉換。
19.如權利要求18所述的解碼器，其特徵在於，所述處理器在第一階段將2×2Hadamard轉換應用到在所述相應數字媒體塊的左上方的4值子集；將2×2Hadamard轉換、作為2點Hadamard轉換和2點旋轉矩陣的Kronecher乘積導出的2×2odd旋轉轉換應用到在所述相應數字媒體塊的右上方及左下方的4值子集；和將作為諸所述各2點旋轉矩陣的Kronecher乘積導出的2×2odd-odd旋轉轉換應用到所述相應數字媒體塊的右下方的4值子集。
20.如權利要求18所述的解碼器，其特徵在於，所述處理器在第二階段將2×2Hadamard轉換應用到包括在數字媒體塊的角、中心、頂/底邊和左—右邊處的4值組的相應數字媒體塊的4值子集。
全文摘要
2D轉換及其逆具有作為一系列為了減少計算複雜性(即減少非一般操作的數目)安排的提升步驟的實現。此轉換對具有類似於離散餘弦轉換(DCT)的能量緊緻特性，且還是無損和與比例無關的。與作為分別應用到2D數據塊的行和列的1D DCT轉換實現的可分離的DCT轉換相比較，該轉換操作被重新安排成包括2×2Hadamard轉換和加入提升旋轉的2×2轉換的基本轉換的串聯。這些基本轉換具有作為提升操作的序列的實現。
文檔編號H04N7/30GK1791222SQ20051012713
公開日2006年6月21日 申請日期2005年11月17日 優先權日2004年12月17日
發明者S·斯裡尼瓦杉 申請人:微軟公司