多技術熵編碼系統和方法
2023-04-24 21:45:16
專利名稱：多技術熵編碼系統和方法
技術領域：
本發明涉及數據壓縮，以及更具體地，涉及基於它們的出現概率來高效地編碼數據元素。
背景技術：
直接數位化的靜態圖像和視頻需要許多「位」。因此，通常為了存儲、傳輸、和其它應用而壓縮圖像和視頻。大多數的圖像和視頻壓縮器共享一個具有各種變化的基本結構。如圖1所示，該基本結構包括三個級變換級、量化級、以及熵編碼級。
視頻「編解碼器」(壓縮器/解壓器)用於通過在圖像質量、處理器要求(即，成本/功率消耗)、和壓縮比率(即，結果數據速率)之間進行平衡來降低數據通訊流所需的數據速率。當前可用的壓縮方法提供了不同的折衷(trade-offs)範圍，並產生了多個編解碼方案，其中，每個方案被最優化以滿足特定應用的需要。
視頻壓縮器中變換級的目的在於收集源圖片的能量(energy)或信息以通過利用圖片或序列內局部相似和圖案來將其轉換為最大可能的壓縮形式。壓縮器被設計為在「典型」輸入上很好地工作，而忽略掉壓縮「隨機的」或「不合理的」輸入對其造成的故障。
諸如MPEG-2的許多圖像壓縮和視頻壓縮方法使用離散餘弦變換(DCT)，作為變換級。
諸如MPEG-4結構的一些較新的圖像壓縮和視頻壓縮方法使用各種小波變換，作為變換級。
小波變換包括以一維或多於一維的形式重複應用小波濾波器對到數據集。對於圖像壓縮，可以使用2D小波變換(水平和垂直)。對於視頻數據流，可以使用3D小波變換(水平、垂直、和時間)。
現有技術圖2示出了當前可用的各種壓縮算法中的折衷實例100。如圖所示，這種壓縮算法包括基於小波的編解碼器102和基於DCT的編解碼器104，它們包括不同的MPEG視頻分配方案。
與基於DCT的編解碼器算法不同，2D和3D小波因其賞心悅目的圖像質量和靈活的壓縮比被高度評價，促使JPEG委員會採用小波算法作為其JPEG2000靜態圖像標準。不幸地是，相對於DCT的可選方案，大多數的小波實施使用非常複雜的算法，需要很好的處理能力。另外，小波對於時間壓縮提出了特別地挑戰，使得3D小波尤其困難。
由於這些原因，相對於諸如MPEG的高容量工業標準編解碼器，小波沒有提供成本競爭性的優勢，因此，僅在小型應用中被採用。因此需要一種商業上可行的3D小波實施，其針對三個主要市場階段的低功耗和低成本進行最優化。
例如，小型攝像機越來越普及，並且數位化處理其信號的優勢是明顯的。例如，一些國家中蜂窩電話市場的最快發展階段是具有圖像和視頻片斷功能的電話階段。大多數數字靜態相機具有視頻片斷功能。在移動無線手機市場，這些靜態圖片和視頻短片的傳輸需要更大的裝置電池容量。現有的視頻編碼標準和數位訊號處理器給電池帶來更大壓力。
另一個新的應用是個人視頻記錄器(PVR)，其允許觀眾暫停直播TV和定時轉換節目。這些裝置使用數字硬碟存儲器來記錄視頻，並要求對來自電纜的模擬視頻進行視頻壓縮。為了提供如畫中畫和邊看邊錄的功能，這些單元需要多個視頻壓縮編碼器。
另一個正在發展的應用領域是用於監視和安全視頻的數字視頻記錄器(DVR)。待存儲的輸入視頻的每個信道也都需要壓縮編碼。為了利用方便、靈活的數字網絡傳輸結構，經常在攝像機內使視頻數位化。即使具有較舊的複雜記錄器結構，也使用多信道壓縮編碼器。
當然，大量的其它市場可從對低功耗和低成本最優化的商業上可行的壓縮方案中獲利。
熵編碼熵編碼(在文獻中也稱作「源編碼」)的目標通常是從消息或信息源中生成短消息，其隨後被解碼回原始消息，最好與原始消息完全相同。典型地，通過把源消息分割成「符號」並且逐個符號地處理消息來實現，而不是通過在超大的密碼本中查找較大的塊或甚至整個輸入消息(例如，圖像或視頻GOP)來完成。
對固定長度的輸入符號工作且為每個可變長度的位串生成的熵編碼器類在文獻中稱作「可變編碼器組」。
編碼符號的兩種典型方法給出待編碼的輸入符號，一種編碼方法在於將符號作為索引並且在被稱作「密碼本」的表中查找該符號。在密碼本中找到的項是該符號的編碼的輸出。典型地，該密碼本足夠大，以便為每個可能的符號提供項。
在一些實施方式中，對表的單一隨機存取非常快速且高效。然而，在其它的實施方式中，對大表的隨機存取相對較慢(由於高速緩衝存儲器的加載)或者成本相對較高(由於，諸如在FPGA或ASIC內的晶片級存儲器成本)。
用於編碼符號的第二個典型方案在於對其表達式(通常是二進位位串)進行一些計算操作，其生成編碼輸出作為其結果。這樣，無需大密碼本即可生成輸出。
在一些實施方式中，這種計算相當快速且高效。然而，在其它的實施方式中，需要多步計算並且相對較慢。
解碼器必須能夠確定解碼回符號的每個可變長度位串(即，代碼字)的長度。這通常通過對具有「Huffman前綴特徵」的代碼字排序(無代碼字是任一其它代碼字的前綴)來完成。
分布上述熵編碼通過利用這些符號中的非一致概率來工作。當符號具有高出現概率(意味著其在消息或源中頻繁出現)時，使用短代碼字對它進行編碼。當符號具有低出現概率(意味著其在消息或源中很少出現)時，使用較長代碼字對它進行編碼。這樣，具有許多短代碼字和少數長代碼字的編碼輸出通常比輸入短。
由Shannon(C.E.Shannon，The Mathematical Theory ofCommunications，Bell System Technical Journal，July October1948)描述的最優化編碼具有與其源輸入中的對應符號的出現概率反對數相關的每個輸出代碼字的長度。這通常不能準確地得到，但是代碼器設計儘量接近它。
因此，為了設計有效的熵編碼，這些符號的概率分布為已知、測得、近似、或假定的。
對於一些分布，編碼的計算方法可用很少的步驟來完成，而對於其它的分布來說需要許多步驟來計算好的編碼。
在視頻壓縮工作中，量化係數的概率分布有時是難以使用的。換句話說，分布不是具有已知快速計算編碼的分布，而可能值的數量需要的密碼本過大而不適於可用的查找存儲。
因此，需要的是與已知或測量的概率分布最優化匹配，而又無需超大查找表的編碼方案。
發明內容
公開了一種用於無需使用超大查找表編碼數據的具有與已知或測量的概率分布最優化匹配的系統、方法、和電腦程式產品。根據本發明構造的編碼器組合使用兩種或多種不同的編碼方法。
根據本發明的一個方面，使用表查找的Huffman編碼與計算代碼字生成(例如，通過使用指數Golomb方程式)相結合。在小的Huffman表中查找最經常出現的元素，而用該方程式對其餘的元素進行編碼。這種方案提供了使用表查找的Huffman編碼(即，與已知或測量的概率分布最優化匹配)與簡單計算編碼(即，無查找的快速計算)的優勢相結合的優點，而避免了完整的Huffman編碼(即，需要支持極大表)的缺陷。
根據另一方面，使用兩個或多個方程式編碼數據。在單個方程式不能精確地適合數據類型的情況下，可以使用不同的方程式，每個方程式用於數據的不同部分，以更好地描述整個數據概率分布。
根據再一方面，使用與一個或多個方程式相結合的多個表來編碼數據。多個方程式用於數據的多個部分，其中，方程式精確地描述了數據部分的概率分布。表可散布有這些方程式，以覆蓋這些方程式中的間隙，例如，在非快速計算編碼是已知的地方。
圖1示出了根據一個實施例用於壓縮/解壓縮數據的方框圖。
圖2示出了在當前可用的各種壓縮算法中的折衷實例。
具體實施例方式
圖1示出了根據一個實施例用於壓縮/解壓縮數據的方框圖200。這個方框圖200中包括編碼器部201和解碼器部203，它們一起構成「編解碼器」。編碼器部201包括用於壓縮數據以存儲到文件208中的變換模塊202、量化器204、以及熵編碼器206。為了執行這種文件208的解壓縮，解碼器部203包括用於解壓縮數據以便應用(即，查看視頻數據的情況等)的熵解碼器210、反量化器212、以及逆變換模塊214。在使用中，出於去相關的目的，變換模塊202對多個像素(在視頻數據的情況下)執行可逆變換，其經常是線性的。接下來，量化器204實現變換值的量化，此後，熵編碼器206負責對量化的變換係數的熵編碼。
根據本發明構造的編碼器組合使用兩種或多種不同的編碼方法。應用大係數值(其在輸入源中具有低出現概率)的負指數和小係數值(最頻繁出現，在輸入源中具有最高概率值)的小表來很好地接近一些量化視頻數據分布。因此，根據一個方面，只有小表可以使用，簡單計算方法和選擇應用兩種技術(表或計算)中哪一種的方法。
根據本發明另一方面，選擇哪種技術應用於哪種數據元素或符號可以是簡單的大小檢測。在該實例中，待熵編碼的符號總是正的，其範圍從1到215-1。值零除外。簡單檢測該符號，以確定它是否小於固定常數。倘若如此，則使用該常數的相同大小的表。否則，使用該計算方法。
對於該實施例中的小(高頻)值，使用查找表內的Huffman代碼字。對於大(低頻)值，使用方程式(例如，使用指數Golomb類型方程式)計算代碼字。這種實施可以逐個符號地編碼，而不保存被編碼的符號的歷史記錄。恆定長度的符號以16位輸入到編碼器，並且輸出長度從1位(高頻值)到16位(低頻值)變化。
編碼器兩個部分中的每一個分別具有Huffman前綴特徵。換句話說，用於編碼器的一個部分中的符號的代碼字與用於該編碼器相同部分中另一符號的代碼字的開頭部分不同。具有用於許多應用的典型概率分布範圍，用於編碼器的兩個部分的組合代碼也具有Huffman前綴特徵，使得在代碼字的輸出流中不需要額外的標記位來指示解碼器一個代碼字在何處結束以及下個代碼字在何處開始。
實例算法1該實例算法接受符號S作為輸入，S為以二進位形式表示的16位正的非零整數。它生成位串W作為輸出。
步驟1如果S＞15，跳轉到步驟3。
步驟2在以下給定的表1中查找S，以發現值B和長度L。
W由B的低階L位組成。
將W添加到輸出位流中。結束。
步驟3從最左端的包括「1」位開始對數S+8內的有效位計數。調用計數C。
步驟4W包含2C-1位C-1個「0」位，隨後是S+8的C個有效位。
將W添加到輸出位流中。結束。
用於實例算法1的表1
出於比較的目的，如果沒有使用表1，則下列表2提供了應由以上步驟3和步驟4(代碼字的計算生成)為小於16的符號值提供的輸出。通過比較這兩個表可以看出，與表2的計算生成方法相比，使用表1的Huffman表方法為一些更頻繁出現的符號提供了更短的代碼字。
用於實例算法1的表2
性能當該實例的方法在一些計算機平臺上執行時，達到了高性能的目標，這是因為-它為大多數常見情形提供了任選的Huffman編碼；-為了最優化匹配測量的概率分布的那個部分，其只需能容易地適於有限存儲的小表；-其對於少見情形使用非常簡單的指數-Golomb編碼計算；-不管什麼樣的符號，操作都很迅速。
可將各種改進應用於本發明的上述實例實施。例如，可以修改熵編碼器，象編碼以上無符號(只是正的)的符號一樣編碼有符號的數字符號。為了高效地編碼，將該表內的每個L項加1，把符號位添加到每個B值，並且包括負的符號的表項。下列表3提供了實例。在該表中，0符號項允許較快的直接查找。由於該0符號項是不使用的偽項，因此其內容不重要。
對於如算法2的情況，將以上簡單算法稍作修改。
實例算法2該算法接受符號S作為輸入，S為以二進位表示的16位整數(不允許有零值)。它生成位串W作為輸出，用於逐位添加到正在生成的壓縮位流中。
步驟1如果S的絕對值大於15，則跳轉到步驟3。
步驟2在下列表3中查找S，以找到值B和長度L。
W由B的低階L位組成。
將W添加到輸出位流中。結束。
步驟3從最左端包括「1」位開始對數字S+8的絕對值內的有效位計數。稱之為C。
步驟4W包含2C位C-1個「0」位，其後是S+8的絕對值的C個有效位，再其後是S的符號位。
將W添加到輸出位流中。結束。
用於實例算法2的表3
在以上實例中，使用表查找(與已知或測量的概率分布最優化匹配)的Huffman編碼的優點可以與簡單計算編碼(例如，指數-Golomb(無查找的快速計算))的優點相結合，而避免了完整Huffman編碼(極大表)的缺點。我們還描述了一種方法，其對於常用的情形通過將符號位結合到查找表中來更快地編碼有符號的符號數據，而不會將額外的位引人到輸出中。
在與以上所述的方法類似的方法中，可以採用表查找和計算生成的各種組合。例如，可使用兩個不同的方程式，每一個均被應用於正在編碼的符號的不同子集中。使用這種組合的優勢在於單個已知的方程式不能很好地與特定數據類型的概率分布相匹配，但是兩個或多個方程式相組合提供了更接近的匹配。另一優勢在於更常見的符號可採用更簡單的方程式，以提高編碼的整體處理速度。
多個方程式中的每一個均可以應用相同的通用類型的方程式，或者可以把不同類型的方程式組合起來。一些不同類型的方程式或可方便地應用於根據本發明構造的系統中的處理的實例包括指數Golomb、Golomb、Golomb-Rice(或Rice-Golomb)編碼以及算術編解碼器。以非逐個符號方式工作的算術編解碼器還包括諸如二元單調(DM)編解碼器(如2005年1月25日出版的題為System andMethod for a Dyadic-Monotonic(DM)Codec的美國專利第6,847,317號中所述)和CABAC的子類型。
在另一實施例中，使用與一個或多個方程式相結合的多個表來編碼數據。方程式被用於數據的多個部分，其中，這些方程式精確地描述了該數據部分的概率分布。表可以散布有這些方程式，以覆蓋在其中非快速計算編碼為已知的間隙。
其創造性地證實了當系統被設計為提供或者其提供期望用於編碼的區別符號的數目和查找表中區別符號的數目之間的特定關係時，可以在編碼器中獲得有優勢的效率。當系統如此設計或提供包含有多個區別符號(其表示在熵編碼中典型地處理的符號的全體(或頻率)的確定百分數時)的表，可以獲得其他優勢。
例如，在組合有查找表和至少一個方程式的應用的編碼器的特定實施例中，可以發現為表示為典型待編碼的區別符號的0％到50％的符號提供查找表是有優勢的。出於本公開的目的，該百分數被稱為「表區別符號百分數(或TDSP)」。更具體地，該範圍可以表示為期望典型地給出用於編碼的全體區別符號的0％到30％，更具體地為0％到10％，甚至更具體地為0％到3％，甚至更具體地為0％到1％，甚至更具體地為0％到0.1％，以及更具體地為0％到0.01％。
另外，該表可以創造性地設計為包括多個符號，其總體上包含典型地給出用於編碼的符號的全體(或頻率)的100％到50％。出於該公開的目的，該百分數被稱為「表集合頻率百分數(或TAFP)」。更具體地，這些多個符號總體上包括為典型地給出用於編碼的符號全體(或頻率)的100％到70％，更具體地為100％到80％，甚至更具體地為100％到85％，更具體地為100％到90％，以及更具體地為100％到95％。
例如，在根據本發明的一個壓縮方案中，待編碼的區別符號的總數為32,766個符號。列舉了期望在提供給編碼器的數據中具有高頻率的15個區別符號提供給查找表。因此，這些15個符號包括區別符號總數的大約0.046％。因而，該實施例具有約0.046％的表區別符號百分數。然而，可以發現，在典型的操作中，該15個符號代表了大約90％的給出用於編碼的集合符號出現事件。因此，該實例具有約90％的表集合頻率百分數。這樣15個符號的相對小的表可以處理壓倒性多數的符號的編碼(近似地，90％的給出用於編碼的符號)。
另外，在本發明的範圍內可以設想，提供使用多個查找或其它表的編碼技術，以及其中，基於多個表的組合來計算該表區別符號百分數和該表集合頻率百分數。
本發明的附加的特徵包括提供了具有至少一個查找表和至少一個編碼方程式的組合的編碼器，其中，給出了表區別符號百分數和特定的表集合頻率百分數的特定組合。例如，有利的組合包括具有從100％到70％的TAFP的0％到5％之間的TDSP。另外的有利組合在下列表4中示出。
表4
雖然以上為本發明的優選實施例的完整的描述，可以使用不同的替換、修改和類似物。因此，以上所述不應該被看作是對本發明的範圍的限定，本發明的範圍由所附的權利要求限定。
權利要求
1.一種壓縮數據的方法，包括使用並行的至少兩種編碼技術的組合對輸入數據流進行熵編碼，所述編碼技術中的每一種處理所述數據流的不同部分。
2.根據權利要求1所述的方法，其中，所述至少兩種編碼技術包括Huffman查找表和計算生成。
3.根據權利要求2所述的方法，其中，所述計算生成為指數-Golomb類型的。
4.根據權利要求2所述的方法，其中，所述輸入數據流包括一系列待編碼的符號，每個符號均具有大小，以及其中，使用所述Huffman查找表對具有小於固定常數的大小的符號進行編碼，以及使用所述計算生成對具有不小於所述的固定常數的大小的符號進行編碼。
全文摘要
一種具有與已知或測量的概率分布最優匹配的系統、方法、和電腦程式產品不使用過大的查找表來編碼數據。根據本發明構造的編碼器(201)組合使用兩種或多種不同的編碼方法。在一個實施例中，應用表查找的Huffman編碼與計算生成相結合，例如，通過使用指數Golomb方程式。在小的Huffman表中查找最經常出現的元素，而應用方程式來編碼其餘的元素。在另一實施例中，使用兩個或多個方程式來編碼數據。在再一實施例中，使用與一個或多個方程式相結合的多個表來編碼數據。
文檔編號G06K9/46GK101052972SQ200580037714
公開日2007年10月10日 申請日期2005年9月22日 優先權日2004年9月22日
發明者威廉·C·林奇, 克拉西米爾·D·克拉羅夫, 史蒂文·E·桑德斯 申請人:液滴技術有限公司