使用後向自適應規則進行整數數據的無損自適應Golomb/Rice編碼和解碼的製作方法

2023-05-20 12:40:31

專利名稱：使用後向自適應規則進行整數數據的無損自適應Golomb/Rice編碼和解碼的製作方法
技術領域：
本發明一般涉及數字數據的處理，尤其是使用具有新穎的後向自適應規則的Golomb/Rice編碼進行整數數據的無損編碼與解碼的改進方法和系統。
背景技術：
隨著計算機數據(諸如文本、音頻、視頻、圖像和程序文件)的大小持續增長，數據壓縮正變得越來越重要。數據壓縮是一種將數字數據編碼為比原始數據使用更少比特的經編碼表示的方法。以較少比特表示數據意味著數據佔據較少的存儲空間並需要較小的傳輸帶寬。
通常，數據壓縮通過預測最常出現的數據並將之以較少的空間存儲來壓縮數據。具體地，數據壓縮涉及至少兩個不同的任務(1)定義一數據模型來預測輸入數據的概率；以及(2)用編碼器從這些概率生成代碼。此外，某些數據壓縮技術在數學上變換並量化數據以達到甚至更大的壓縮。
壓縮技術可以是無損或有損的。無損壓縮技術是可逆的，從而編碼前的原始數據和解碼後的解壓縮數據的每一比特都是相同的。有損壓縮利用了數據中有很多可以扔掉的重複而在質量上有更多損失這一事實。有損壓縮接受某些原始數據的損失以便得到更高的壓縮。
無損壓縮一般用於壓縮文本或二進位數據，而有損壓縮一般用於音頻、圖像和視頻數據。然而，即使有損壓縮技術有時也使用無損壓縮技術。例如，兩種常用的壓縮(或編碼)技術是變換編碼和預測編碼。對於這些種類的壓縮系統，原始數據經變換並隨後被量化(捨入到最近的整數)，或者根據(固定或自適應的)信號模型進行預測，且預測誤差(原始和預測的數據之間的差異)隨後被量化。在這兩種情況下，經量化的數據是整數形式的。一旦獲得這些整數，就要用無損壓縮技術來編碼經量化的值，以減少表示該數據所需要的比特數。
這些整數值集合通常有相關聯的概率分布函數(PDF)。這些PDF具有這樣的分布當在預測編碼中數據性質由預測者很好地模型化時，預測誤差應在大多數時間接近於零。類似地，在變換編碼中，大多數量化變換係數為零。圖1示出對於這些整數值的典型概率分布；零是最可能的值，而非零值的概率隨數量增加呈接近指數級下降。數據具有圖1所示的概率分布，因為使用無損壓縮編碼的數據不是原始數據。圖1是通過量化變換係數或預測誤差所得的整數數據。
從數學上講，問題是要找出編碼包含N個整數的向量x的有效解決方案。每個元素x(n)，n＝0，1，...，N-1，有一個按照類似於圖1的概率分布的值，因而最可能值為零，而距零更遠的值具有快速減少的概率。
像圖1中這樣的概率分布的簡單數學模型是拉普拉斯(Laplacian)分布，或者雙邊幾何(TSG)分布，由參數θ特徵化P(x,)=1-1+|x|----(1)]]>注意，參數θ控制當|x|增長時概率的衰減速率。θ值越大，衰減越快。參數θ可直接相關於概率，當x＝0時，即P(0，θ)＝(1-θ)/(1+θ)。同樣，源碼元的期望絕對值是E[|x|]=21-2---(2)]]>源的熵按比特/碼元給出，如下式H(x)=log2(1+1-)-21-2log2-----(3)]]>因此，一個好的編碼器應將x的N個值的向量映射到包含不多於N·H(x)個比特(理論最小值)的比特流。
拉普拉斯分布是媒體壓縮系統中的常用模型，用於預測編碼器(如大多數無損音頻和圖像編碼器)中的預測誤差，或者用於量化變換係數(如大多數有損音頻、圖像和視頻編碼器)。
對於具有拉普拉斯/TSG分布的源有多種建議的編碼器。一個簡單而有效的編碼器是Golomb/Rice編碼器。首先，通過以下簡單的可逆映射將TSG源值x映射到非負值uu=Q(x)=2x,x0-2x-1,x0------(4)]]>即，等效於將u視作重新排序的字母表的索引{0，-1，+1，-2，+2，...}。新源u具有接近幾何源的概率分布，對它而言Golomb碼是最優的，因為它們是幾何源的Huffman碼，只要適當地選擇Golomb參數。
Golomb/Rice(G/R)碼的一個示例示於表1，示出參數m的幾個值。應該注意，當m等於二的冪時，使用了參數k，它通過m＝2k與m相關。G/R碼優於Huffman碼的主要優點在於對於任意輸入值，二進位碼字可通過簡單的規則來計算。因此，不需要存儲表。這對現代處理器特別有用，對它們而言，從存儲表條目的存儲位置讀取可能比執行若干指令花更長時間。易於明白，參數m確定多少連續的碼字具有相同的比特數。這也表明計算碼字涉及計算u/m。其中u是輸入值。對於大多數處理器，整數除法採用多次循環，因而G/R碼對於一般的m並沒有吸引力。當選擇了對應於Rice碼的m＝2k，則除法u/m可用位移來代替，因為u/m＝u＞＞k(其中＞＞表示右移運算符)。從而，對於任意輸入u計算G/R碼是容易的；只需計算p＝u＞＞k和v＝u-(p＜＜k)。隨後通過將具有p個1的串與v的k位二進位表示串接來形成代碼。

表1從表1中顯而易見，G/R參數k的選擇必須依賴於源的統計量。當u增加時，概率衰減得越慢，因此應選擇更大的k。否則，碼字長度增長過太。選擇k的簡單規則是對於給定輸入值u的碼字長度應接近於該值出現概率以2為底的對數。
儘管G/R碼對於幾何分布源是最優的，但對於經由公式4的映射從拉普拉斯/TSG源編碼碼元並非最優。這是因為對於具有TSG分布的輸入變量x，從公式4得到的變量u具有接近但不完全是幾何的概率分布。實際上，性能足夠接近於最優(例如，一般具有比熵少5％的速率)，因此G/R碼相當流行。TSG源的最優碼包括一組四個代碼變量，在大多數情況下，實現它們且按5％或更少來改進壓縮更為複雜。因此，在大多數情況下，G/R編碼器在性能和簡便之間提供最佳折衷。
在圖1中，概率分布由單個參數表示，即指數衰減速率。衰減速率越快，則更可能是零值。這意味著在許多情況下零是很可能的，使得幾個零連串變得非常可能。換言之，如果概率分布衰減速率足夠快，則編碼連串是個好方法。編碼零連串意味著僅有幾個比特用於處理輸入數據中的許多項。
例如，如果數據與預測編碼中預測器所使用的模型相匹配，則預測誤差更可能為零。但即使有了好模型，偶爾有個大值也是可能的。這會在到達邊界時發生，諸如像素值從背景值到前景值。不時地會出現大數字。當這種現象發生時，比遊程編碼更有用的一種類型的編碼技術被稱為「遊程Golomb/Rice(RLGR)」編碼技術。一種這樣的RLFT編碼技術在美國專利第6,771,828號，Malvar的題為「System andMethod for Progressively Transform Coding Digital Data(用於漸進變換編碼數字數據的系統和方法)」和美國專利第6,477,280號，Malvar的題為「Lossless AdaptiveEncoding of Finite Alphabet Data(有限字母數據的無損自適應編碼)」中公開。
事實上，隨著數據源變化，概率將不保持常量而隨時間變化。這對於例如圖像和音頻都是真實的。通常，這些輸入數據中的概率變化可用大量不同的方法來處理。在JPEG中，例如，有一熵編碼器(Huffman編碼器)，其中不同長度的碼字用於要編碼的不同值。Huffman表通常是預先設計的，即，通常是獲得大量圖像、測試它們的概率、並構造用於所有圖像的平均模型。這種方法的一個問題是對於圖像的每個部分，編碼效率上都有損耗，因為熵編碼器使用的概率模型平均上很好，但對圖像的某個部分不夠好。
從表1可看出，Golomb/Rice碼有兩個主要問題(1)概率衰減參數θ，或者等價的概率P(x＝0)必須已知，因此k的近似值才能確定；以及(2)如果衰減參數太小，則熵H(x)比1小，且因而Golomb/Rice碼不是最理想的，因為其平均碼字長度不能小於1比特/碼元。
實際上，第一個問題(最優Golomb/Rice參數的估算)通常是通過將輸入向量劃分成預定長度的塊來解決的。對於每個塊，編碼器兩次通過數據。第一次通過時，計算輸入值的平均量。為此，參數θ可從公式2估算，且可確定相應的最優k。在第二次通過時，編碼器通過首先輸出二進位形式的k的值，隨後是塊內數據值的Golomb/Rice碼的串接串，來生成該塊的比特流。這是實際上所有使用Golomb/Rice碼的無損壓縮系統中都使用的方法，諸如用於無損圖像壓縮的JPEG-LS、用於無損音頻壓縮的SHORTEN及其它等。這被稱為「按塊自適應」或者「前向自適應」模型。前向自適應模型在以下意義上上是前向的編碼器在編碼前先考察數據、測量統計參數(通常是平均量)、隨後基於該參數編碼並將用於編碼數據的參數值放入首部，以便由解碼器使用。數據被拆成小部分，即塊，而不是試圖同時編碼所有數據。對於每個塊，測量該塊的統計量，對於與緩衝區的內容相匹配的數據部分測量統計參數，且將熵編碼器調整到該參數。在編碼文件中，插入首部，指示用於編碼該數據塊的參數值。
實踐中的第二個問題，即，具有非常低的熵的編碼源，通常是使用按塊自適應或前向自適應模型來解決的，且如果塊中輸入碼元的平均量的值小到足以使估算的熵H(x)小於1，則編碼器使用遊程編碼而非Golomb/Rice編碼。
儘管這些方法在實踐中用得很好，但有兩個主要缺點。一個缺點是編碼器需要兩次讀取每個輸入塊，這樣在數據上執行兩次通過第一次計算平均量以確定Golomb/Rice參數，而第二次執行真正的編碼。這要求編碼器執行附加的工作並增加了複雜性。在某些應用中，編碼時間不是問題，但對於例如數位相機而言，它會減慢編碼過程或增加隨機存取存儲器的開銷。具體而言，前向自適應模型必須先考察數據並測量統計量，找出模型參數，然後編碼。如果編碼器在具有大量處理能力的個人計算機上運行，則這不是個問題。然而，如果用手機拍照，照片要由手機自己編碼，而其處理能力相當有限。
第二個但最重要的缺點涉及選擇塊尺寸的難度。如果塊尺寸太大，則統計量在塊內會劇烈變化。另一方面，如果塊尺寸太小，則必須告知解碼器哪個參數用於編碼該數據塊的額外開銷變得難以承擔。對於每個塊，編碼器必須存儲正用於編碼該塊的參數值。從某種觀點看，編碼小塊所需要的額外開銷對於所得到的壓縮是不值得的。這就造成了權衡。一方面，如果用了小塊，則塊的統計量可匹配，但測量統計量是困難的，因為只有幾個數，且編碼的額外開銷是巨大的。另一方面，如果使用大塊，則問題是統計量在塊內變動巨大。實際上，很難找到這兩個矛盾因素之間的折衷，因此塊尺寸通常被選擇在128和1,048個樣值之間，取決於要編碼的數據類型。
一種解決方案是在編碼器中使用後向自適應技術。採用後向自適應，編碼始於解碼器和編碼器對每個塊達成初始狀態的一致。換言之，每個參數被初始化為預定值，隨後編碼開始。每次當編碼器產生一輸出碼元，該碼元即可立即被發送至解碼器，因為解碼器知道用於編碼它的參數值。在編碼器輸出碼元後，它就按照預定的自適應規則計算用於編碼參數的新值，這取決於所輸出的碼元。解碼器知道該參數自適應規則，因此它也可計算用於編碼參數的新值。因而，編碼參數可在每個編碼的碼元後調整，且編碼器和解碼器始終是同步的，即，解碼器追蹤編碼參數中的變化。這意味著編碼器不需要向解碼器發送有關什麼參數用於編碼該數據方面的任何額外開銷信息。
因此，所需的是一種提供有效壓縮並能處理和編碼可能出現的任何輸入整數的無損Golomb/Rice(G/R)編碼器和解碼器(編解碼器)和方法。此外，還需要的是一種通過使用後向自適應技術提供對輸入數據的快速追蹤和有效壓縮來避免上述前向自適應所存在問題的自適應G/R編解碼器和方法。

發明內容
此處所公開的本發明包括用於整數數據無損編碼和解碼的自適應Golomb/Rice(G/R)編碼器和解碼器(編解碼器)和方法。該自適應G/R編解碼器和方法使用了具有新穎的自適應規則的新穎後向自適應技術。使用後向自適應，該自適應G/R編解碼器和方法快速獲知輸入數據的統計量中的任何變化。此外，該自適應G/R編解碼器和方法能夠編碼任何輸入整數值。
該自適應G/R編解碼器和方法還使用了在每個編碼碼元後調整編碼參數的新穎的自適應規則。不需要概率表或碼字表，因而該自適應G/R編解碼器和方法可適用於小存儲器的情況。該自適應G/R編解碼器和方法因此很適於現代處理器，其存儲器訪問通常比指令取出和執行花費更多的周期。它也適於只有有限存儲器和有限處理能力的小型設備，因為該自適應G/R編解碼器和方法不需要緩衝塊中的輸入數據，也不需要兩次處理每個數據值。
該自適應G/R和方法的主要優點之一是在生成的每個碼字後調整和更新G/R參數(k)。這使得輸入數據的統計量中的任何變化都能被很快追蹤到。不需要將G/R參數發送到解碼器的額外開銷，因為它們的變化都能被解碼器追蹤。由於自適應規則是簡單的，使用後向自適應的計算複雜度很低。因而，該自適應G/R編解碼器和方法對許多實際應用都有吸引力。
該自適應G/R方法包括使用編碼和自適應規則。編碼規則規定下一輸入值x是通過先經簡單的1-1映射規則(當x＞0時u＝2x，當x＜0時u＝-2x-1)將它映射到非負值u上、然後使用帶有參數k的Golomb/Rice編碼器編碼來編碼的，因此輸出碼字被表示為GR(u，k)。
在編碼了碼元後，使用自適應規則。該自適應G/R方法使用簡單而新穎的自適應規則。對於k的自適應規則如下。從輸入值u(記住G/R編碼器總是在u值上運算)，通過p＝u＞＞k計算臨時值p(其中＞＞表示右移運算符)。如果p＝0，則k的經比例縮放的形式，稱為K，減少第五整數常數B3。如果p＝1，則k保持不變。如果p＞1，則K增加p。以這種方法，在生成每個碼字後，參數k對於第一和第二模式中的G/R編碼器而更新。隨後計算用於生成下一碼字的k值為k＝K/L，其中L是固定參數(記住如果L選為二的冪，則除以L的除法只是位移運算)。
從以上自適應規則的描述中可以看到，該自適應G/R方法還可包括稱為「小數自適應」的特徵。小數自適應允許對自適應速度的更精細控制。首先，定義比例縮放參數L，且L的值一般設為二的冪。接著，定義經比例縮放的G/R參數K＝k*L。當對k使用自適應規則時，經比例縮放的參數值K根據所生成的碼字增加或減少整數常數。在K的自適應後，最終的參數值k通過k＝K/L來計算。用這種方式，K的整數增量可看作k的小數增量，它允許對k值的更平滑控制，從而能更好地追蹤輸入統計量中的變化。如果k在每個編碼碼元後按整數增量調整，其值將波動太大。參數值中的這種噪聲將導致壓縮比(以直接二進位形式存儲輸入數據所需的比特數與存儲已編碼比特流所需的比特數之比)的下降。在一經測試的實施例中，比例縮放參數等於十六，且G/R參數的值基於數字數據的衰減參數。
一種自適應G/R編碼器包括結合上述自適應G/R方法的模塊和裝置。
數字整數數據包括具有值的整數向量。值是這樣的，對每個值，最可能的值是零，且非零值具有隨非零值增加而減少的概率。該自適應G/R方法還包括用於編碼和解碼數據的過程。該過程包括使用自適應Golomb/Rice(G/R)編碼和G/R參數k來編碼數字整數數據的每個值x，以及定義小數G/R參數為K＝k*L，其中L是比例縮放參數。該過程還包括在編碼了每個數字整數數據的每個值x後，使用具有自適應規則的後向自適應技術來更新小數G/R參數，以及將數字整數數據的編碼值追加至比特流中。該過程還包括使用G/R解碼器解碼比特流以精確地恢復數字整數數據的每個值x。
自適應G/R解碼器和方法通過使用對應於以上編碼規則的解碼規則並使用上述相同的自適應規則來工作。解碼器處的解碼規則反轉了前述的編碼器處的編碼規則。即，解碼器根據GR參數k的當前值，按所需多少從輸入比特流(或文件)中讀取多個比特。以這種方法，解碼器按照表1讀取對應於有效的Golomb/Rice碼GR(u，k)的完整碼字。由於Golomb/Rice碼對每個參數k是唯一可解碼的，因此解碼器隨後可解碼該碼字。換言之，解碼器可確定目前在解碼器處的碼元值u。從u，解碼器可簡單地通過使用1-1逆映射規則來確定相應的數據值x。具體而言，如果u是偶數，則x＝u/2，而當u是奇數時，則x＝-(u+1)/2。執行上述解碼過程來將輸入碼字解碼成完全匹配在編碼器處所見到的輸出值或值串。這樣，解碼過程是無損的。
在如上所述地解碼了來自輸入比特流或文件的碼字後，解碼器則如以上對編碼器所述的相同自適應規則地計算。以這種方式，解碼器將以與編碼器完全相同的方法調整參數值k。從而，參數將具有用於解碼下一比特流(或文件)碼字的正確值。


本發明可通過參考以下描述和示出本發明各方面的附圖來進一步理解。通過結合附圖閱讀以下本發明的詳細描述，其它特徵和優點將是顯而易見的，附圖作為示例示出了本發明的原理。
現在參考附圖，其中相同的參考標號通篇表示相應的部件圖1示出適用於此處所公開的自適應遊程Golomb/Rice(RLGR)編碼器和方法的整數值的典型概率分布。
圖2A是示出此處所公開的自適應Golomb/Rice(G/R)編解碼器和方法的編碼器部分的示例性實現的框圖。
圖2B是示出此處所公開的自適應Golomb/Rice(G/R)編解碼器和方法的解碼器部分的示例性實現的框圖。
圖3示出其中可實現圖2所示的自適應G/R編解碼器的合適的計算系統環境的示例。
圖4是示出圖2所示的自適應G/R編碼器的組件的概括框圖。
圖5是示出圖2和4所示的自適應G/R編碼器和方法的概括操作的概括流程圖。
圖6是進一步示出圖5所示的自適應G/R編碼器和方法的細節的流程圖。
圖7是圖4所示的自適應G/R編解碼器和方法的Golomb/Rice(G/R)參數自適應模塊的操作的詳細流程圖。
圖8是圖7所示的Golomb/Rice(G/R)參數自適應模塊所使用的自適應值的計算的流程圖。
圖9是一工作示例，示出圖2和4所示的自適應G/R編碼器的編碼細節，包括G/R參數k自適應規則。
具體實施例方式
在本發明的以下描述中，對附圖進行了參考，附圖構成本發明的一部分，其中作為說明給出可實施本發明的特定示例。要理解，也可使用其它實施例且可作出結構性變化，而不脫離本發明的範圍。
I.介紹此處所公開的自適應Golomb/Rice(G/R)編解碼器和方法可用於各種各樣的壓縮應用中。例如，該自適應G/R編解碼器和方法可用於資料庫應用來編碼索引。索引一般是具有類似於圖1的概率分布的正整數數字，因為對於索引，小值比大值更可能。另一示例是將該自適應G/R編解碼器和方法用於編碼硬碟的磁頭位置。直到硬碟滿之前，數據更可能位於硬碟開始處而不是末尾處。因此，小磁頭值比大磁頭值更可能，因而整數數據具有類似於圖1的概率分布。
這裡所公開的RLGR編解碼器和方法是用於整數數據的無損壓縮的改進技術。包含整數值的向量由編碼器映射到比特流中，它稍後可由解碼器精確重建。為改進性能使用後向自適應，該自適應G/R編解碼器和方法快速獲知和自適應輸入數據的統計量中的變化。
該自適應G/R編解碼器和方法使用了一種在每個編碼的碼元後調整G/R參數的後向自適應策略。概率表或碼字表是不需要的，它們使自適應G/R編解碼器和方法適合於很小的存儲器情況。因而該自適應G/R編解碼器和方法特別適合現代處理器，其中存儲器訪問通常比指令取出和執行花費更多的周期。
該自適應G/R編解碼器和方法與以前各種熵編碼器相比的一個關鍵優點是其後向自適應策略快速獲知數據的統計量中的變化。因而，實際上該自適應G/R編解碼器和方法展示出比諸如Huffman編碼器、塊自適應Golomb/Rice編碼器或上下文自適應算術編碼器等其它各種編碼器更好的性能。使用後向自適應策略用於編碼參數的另一個優點是不需要概率估算器。該自適應G/R編解碼器和方法還有另一個優點是它在每個編碼的碼元之後執行自適應，只在數據上通過一次，這樣比使用按塊或前向自適應的編碼器產生更好的壓縮結果和更快的編碼。
II.概覽圖2A和B是方框圖，示出此處所公開的自適應Golomb/Rice(G/R)編解碼器和方法的示例性實現。在圖2A中，示出了自適應G/R編解碼器和方法的編碼器部分的框圖。在圖2B中，示出了自適應G/R編解碼器和方法的解碼器部分的框圖。應該注意，圖2A和B只是其中可實現和使用自適應G/R編解碼器和方法的幾種方式中的兩種。
參考圖2A，自適應G/R編碼器200運行在第一計算設備210上。自適應G/R編碼器200輸入並處理整數數據220。一般而言，給定整數數據220，諸如包含整數值的向量，自適應G/R編碼器200將整數數據220編碼或映射為已編碼比特流230。整數數據220一般包含整數向量，因而大多數可能值為零且任意非零值具有隨值增長而減少的概率。這種類型的整數數據一般具有類似於圖1所示的概率分布函數(PDF)。在編碼了整數數據後，已編碼比特流230可被存儲或發送。
參考圖2B，G/R解碼器240駐留在第二計算設備250上。應該注意，儘管示出為單獨的計算設備，但第一計算設備210和第二計算設備250可以是同一計算設備。換言之，G/R編碼器200和解碼器240可駐留在同一計算設備上。一般而言，G/R解碼器240處理編碼器比特流230並輸出經重建的整數數據260。因為自適應G/R編碼器200執行整數數據220的無損編碼，因此G/R解碼器240可讀取已編碼比特流230，並精確地重建包含在整數數據220中的原始數據向量。
應該注意，在實際應用中，設備或儀器可包含G/R編碼器而不包含G/R解碼器(例如，數位相機)。同樣地，設備或儀器可包含G/R解碼器而不包含G/R編碼器(例如，數字音頻播放器或數字圖像查看器)。
III.示例性操作環境自適應Golomb/Rice(G/R)編解碼器和方法被設計為在計算環境中和計算設備上運行，諸如圖2所示的第一計算設備210和第二計算設備250。現在將討論自適應G/R編解碼器和方法在其中運行的計算環境。以下討論旨在提供可在其中實現自適應Golomb/Rice(G/R)編碼器和方法的適當計算環境的簡要概括描述。
圖3示出可在其中實現圖2所示的自適應G/R編解碼器和方法的適當計算系統環境的示例。計算系統環境300隻是適當計算環境的一個示例，而不旨在對本發明使用範圍或功能提出任何限制。計算環境300不應被解釋為對於示例性操作環境300中所示任意一個組件或其組合具有任何依賴或需求。
自適應G/R編解碼器和方法可用大量其它通用或專用計算系統環境或配置來操作。眾所周知的適於自適應G/R編解碼器和方法使用的計算系統、環境和/或配置的示例包括，但不限於，個人計算機、伺服器計算機、諸如蜂窩電話和PDA等手持式、膝上型或移動計算機或通信設備、多處理器系統、基於微處理器的系統、機頂盒、可編程消費電子產品、網絡PC、小型機、大型計算機、可包括任意以上系統或設備的分布式計算環境等等。
自適應G/R編解碼器和方法可在諸如程序模塊等由計算機執行的計算機可執行指令的通用上下文環境中描述。一般而言，程序模塊包括例程、程序、對象、組件、數據結構等，它們執行特定任務或實現特定抽象數據類型。自適應G/R編解碼器和方法還可在分布式計算環境中實施，其中任務由通過通信網絡連接的遠程處理設備執行。在分布式計算環境中，程序模塊可位於包括存儲器存儲設備在內的本地和遠程計算機存儲介質中。參考圖3，用於實現自適應G/R編解碼器和方法的示例性系統包括計算機310形式的通用計算設備。計算機310是圖2所示第一計算設備210和第二計算設備250的示例。
計算機310的組件可包括，但不限於，處理單元320、系統存儲器330和將包括系統存儲器的各種系統組件耦合到處理單元320的系統總線321。系統總線321可以是任意幾種類型的總線結構的任一種，包括存儲器總線或存儲器控制器、外圍總線或外部總線、和/或使用任意各種各樣總線體系結構的任一種的局部總線。作為示例，而非限制，這樣的體系結構包括工業標準體系結構(ISA)總線、微通道體系結構(MSA)總線、擴展ISA(EISA)總線、視頻電子技術標準協會(VESA)局部總線以及外圍部件互連(PCI)總線，也稱為Mezzanine總線。
計算機310通常包括各種計算機可讀介質。計算機可讀介質可以是能夠被計算機訪問的任何可用介質，包括易失性和非易失性介質、可移動和不可移動介質。作為示例，而非限制，計算機可讀介質可包括計算機存儲介質和通信介質。計算機存儲介質包括以用於諸如計算機可讀指令、數據結構、程序模塊或其它數據等信息的存儲的方法或技術實現的任何易失性和非易失性、可移動和不可移動介質。
計算機存儲介質包括，但不限於，RAM、ROM、EEPROM、快閃記憶體或其它存儲器技術、CD-ROM、數字多功能盤(DVD)或者其它光碟存儲、磁盒、磁帶、磁碟存儲或者其它磁存儲設備，或者可用於存儲需要的信息並且可由計算機310訪問的任何其它介質。通信介質一般具體化為在如載波或其它傳送機制等已調製數據信號中的計算機可讀指令、數據結構、程序模塊或其它數據，並且包括任何信息傳遞介質。
注意，術語「已調製數據信號」意指以將信息編碼到該信號中的方式設置或改變其一個或多個特徵的信號。作為示例，而非限制，通信介質包括有線介質，諸如有線網絡或者直接線連接，以及無線介質，諸如聲學、RF、紅外和其它無線介質。任何上述內容的組合也包括在計算機可讀介質的範圍內。
系統存儲器330包括以易失性和/或非易失性存儲器形式的計算機存儲介質，諸如只讀存儲器(ROM)331和隨機存取存儲器(RAM)332。基本輸入/輸出系統333(BIOS)一般存儲在ROM 331中，它包含諸如在啟動期間幫助在計算機310內各元件間傳送信息的基本例程。RAM 332一般包含由處理單元320可直接訪問和/或目前正運行的數據和/或程序模塊。作為示例而非限制，圖3示出作業系統334、應用程式335、其它程序模塊336和程序數據337。
計算機310還可包括其它可移動/不可移動、易失性/非易失性計算機存儲介質。僅作為示例，圖3示出讀寫不可移動非易失性磁介質的硬碟驅動器341、讀寫可移動非易失性磁碟352的磁碟驅動器351，以及讀寫如CD-ROM或其它光介質等可移動非易失性光碟356的光碟驅動器355。
可在示例性操作環境中使用的其它可移動/不可移動、易失性/非易失性計算機存儲介質包括，但不限於，磁帶盒、快閃記憶體卡、數字多功能盤、數字錄像帶、固態RAM、固態ROM等等。硬碟驅動器341一般通過諸如接口340等不可移動存儲器接口連接到系統總線321，而磁碟驅動器351和光碟驅動器355一般通過諸如接口350等可移動存儲器接口連接到系統總線321。
以上討論並在圖3中示出的驅動器及其相關聯的計算機存儲介質為計算機310提供了計算機可讀指令、數據結構、程序模塊和其它數據的存儲。例如，在圖3中，硬碟驅動器341被示出為存儲作業系統344、應用程式345、其它程序模塊346和程序數據347。注意這些組件可以相同或不同於作業系統334、應用程式335、其它程序模塊336和程序數據337。作業系統344、應用程式345、其它程序模塊346和程序數據347在這裡給出不同的標號是為了指出至少它們是不同的副本。用戶可通過諸如鍵盤362和定點設備361(通常指滑鼠、軌跡球或觸摸板)等輸入設備將命令和信息輸入到計算機310。
其它輸入設備(未示出)可包括話筒、操縱杆、遊戲墊、圓盤式衛星天線、掃描儀、無線電接收器或者電視或廣播視頻接收器等等。這些和其它輸入設備通過耦合到系統總線321的用戶輸入接口360連接到處理單元320，但也可通過其它接口和總線結構，如並行埠、遊戲埠或通用串行總線(USB)來連接。監示器391或其它類型的顯示設備也通過接口，如視頻接口390連接到系統總線321。除了監示器以外，計算機還可包括其它外設輸出設備，諸如揚聲器397和印表機396，它們可通過輸出外圍接口395連接。
計算機310可使用到一或多個遠程計算機，如遠程計算機380的邏輯連接在網絡化環境中工作。遠程計算機380可以是個人計算機、伺服器、路由器、網絡PC、對等設備或其它普通網絡節點，並且一般包括上面相對於計算機310所述的許多或所有元件，儘管在圖3中所示的只有存儲器存儲設備381。圖3所示的邏輯連接包括區域網(LAN)371和廣域網(WAN)373，但也可包括其它網絡。這樣的網絡環境在辦公室、企業範圍計算機網絡、企業內部網際網路和網際網路中是很常見的。
當在LAN環境中使用時，計算機310通過網絡接口或適配器370連接到LAN371。當在廣域網環境中使用時，計算機310一般包括數據機372或通過WAN373，如網際網路建立通信的其它裝置。數據機372可以是內置或外置的，通過用戶輸入接口360或其它適當機制連接到系統總線321。在網絡化環境中，相對於計算機310描述的程序模塊或其部分可存儲在遠程存儲器存儲設備中。作為示例而非限制，圖3例示了遠程應用程式385駐留在存儲器設備381上。要理解，所示的網絡連接是示例性的，並且可使用在計算機之間建立通信鏈路的其它手段。
IV.系統組件圖4是示出圖2所示的自適應G/R編碼器200組件的總框圖。自適應G/R編碼器接收輸入值(或值串)400作為輸入。使用Golomb/Rice編碼模塊410來編碼輸入值(或串)400以獲得碼字420。在每個輸入值(或串)400的編碼後，編碼參數被自適應來追蹤輸入數據的統計量。
Golomb/Rice(G/R)參數自適應模塊430用於使用後向自適應技術和新穎的自適應規則來更新原始G/R參數。這產生經更新的G/R參數445。G/R參數的自適應將在下面詳細討論。一旦參數被更新，下一個輸入值450將由自適應G/R編碼器200用更新後的G/R參數440來處理。
V.操作概覽現在將討論如圖2和4所示的自適應G/R編碼器200的操作和其中所使用的方法。圖5是總流程圖，示出圖2和4所示的自適應G/R編碼器和方法的總操作。該方法始於輸入要編碼的數字數據(框500)。在一個經測試的實施例中，輸入數字數據是具有整數值元素的向量形式的整數數據。應該注意，每個輸入數字數據值可以是任意整數值，而不限於特定的範圍(例如，二進位或二進位加符號，因為這在其它熵編碼器中很常見)。接下來，使用G/R參數來編碼數字數據(框510)。
數字數據是使用被初始化為某一值的G/R參數來編碼的。然而，由於輸入數字數據的統計量可以變化，因此G/R編碼器200是自適應的。這種自適應使得自適應G/R編碼器200能夠追蹤輸入數字數據的統計量並快速自適應到那些統計量，以提供更高的編碼效率。自適應G/R編碼器200和方法使用後向自適應技術來更新G/R參數(框520)。G/R參數的這種更新在編碼了輸入數字數據的每個值或值串後發生。此外，後向自適應技術包括新穎的自適應規則，這將在下面詳細討論。然後，輸出已編碼數字數據(框530)。接下來，使用剛才描述的方法處理輸入數字數據的下一值或串。G/R參數的更新值用於編碼下一輸入值或串。一直重複這個過程，直到所有數字數據都被編碼成已編碼比特流。
圖6是一流程圖，示出圖5所示的自適應G/R編碼器和方法的進一步細節。特別地，數字數據的值或串作為輸入接收(框600)。接下來，使用G/R參數編碼輸入值或串(框610)。在編碼了輸入值或串後，更新G/R參數。該自適應過程始於定義一經比例縮放的G/R參數(框520)。該經比例縮放的G/R參數用來減慢G/R參數的自適應，這樣可更緊密地追蹤最優參數值。經比例縮放的G/R參數將在下面更詳細地討論。接下來，使用後向自適應技術和新穎的自適應規則來更新經比例縮放的G/R參數(框630)。經編碼的輸入值或串被追加到已編碼比特流後，且輸入要編碼的下一個數字數據值或串(框640)。該過程重新開始，用更新後的經比例縮放的G/R參數編碼下一值或串。
VI.操作細節現在將討論以上所述圖4、5和6的自適應G/R編碼器200和方法的操作細節。
Golomb/Rice(G/R)參數自適應模塊圖7是圖4所示的自適應G/R編碼器200和方法的Golomb/Rice(G/R)參數自適應模塊430的操作的詳細流程圖。一般而言，G/R參數自適應模塊430使用具有新穎的自適應規則的後向自適應技術來更新初始G/R參數。更新是在編碼數字數據的每個值或串後執行的。
該操作始於接收初始G/R參數(框705)和自適應值(框710)作為輸入，稍後將描述其計算。隨後做出關於自適應值是否等於零的判斷(框715)。如果是，則自適應規則將使經比例縮放的G/R參數減少一整數常數(框720)。
如果自適應值不等於零，則做出關於自適應值是否等於一的判斷(框725)。如果是，則自適應規則保持經比例縮放的G/R參數不變(框730)。如果不是，則自適應規則將經比例縮放的G/R參數增加自適應值(框735)。
一旦G/R參數已被更新，用更新後的G/R參數替換當前G/R參數(框740)。這可通過將經比例縮放的G/R模式參數除以固定比例縮放因子並保留結果的整數部分來獲得。由於自適應按照整數步長調整經比例縮放的G/R模式參數，因此實際G/R參數就象它是由小數步長來自適應的一樣。再一次，這是「小數自適應」的示例，它允許對自適應速度的更精細控制。當然，如果G/R參數保持不變(框730)，則不進行更新，且當前G/R參數是相同的。最後，輸出更新後的G/R參數(框745)。
圖8是圖7所示的Golomb/Rice(G/R)參數自適應模塊430使用的自適應值的計算的詳細流程圖。參考圖7和9，自適應值計算模塊800產生作為圖7的流程圖的輸入的自適應值(框710)。該操作始於接收兩個輸入，即當前G/R參數值(框805)和輸入值(框810)。接著，輸入值右移與G/R參數值相同的位數(框820)。結果值就是自適應值，隨後輸出它(框830)。
VII.工作示例為了更全面地理解這裡所公開的自適應G/R編碼器和方法，給出示例性工作示例的操作細節。應該注意，這個工作示例只是其中可實現自適應G/R編碼器和方法的一種方法。
自適應Golomb/Rice(G/R)編解碼器和方法是在以上提到的美國專利第6,477,280號中公開的PTC熵編碼器的擴展。然而，美國專利第6,477,280號的PTC熵編碼器是用於編碼二進位數據的(一般是整數數據的位平面)。此處所公開的自適應G/R編碼器和方法可使用任意輸入值來編碼整數數據。換言之，此處所公開的自適應G/R編碼器和方法可編碼任意字母的數據。
此處所公開的自適應G/R編碼器和方法的一個優點是，不象PTC熵編碼器，不需要了解輸入數據的最大可能數。相反，自適應G/R編碼器和方法可處理任意大小的輸入值，不論有多大。這意味著自適應G/R編碼器假設輸入數據具有如圖1所示的拉普拉斯分布，當突然有大數字出現在輸入數據中，自適應G/R編碼器和方法能夠編碼這個大數字。儘管大數字將比小數字使用更多比特，但大數字仍將被編碼。然而，使用更多比特只在大數字出現時才自承其果，而不是對每個其它值。這歸因於以下提出的新模式選擇和自適應規則。
用PTC熵編碼器，接收輸入數據、分解成位平面、然後用G/R編碼器編碼每個位平面。在此處所公開的自適應G/R編解碼器和方法中，自適應G/R編解碼器被擴展成直接處理拉普拉斯數據。這有自適應G/R編解碼器和方法使用單次通過編碼的優點，使得它比PTC熵編碼器要快得多。
PTC熵編碼器的輸入數據具有拉普拉斯分布，其中小數字更可能。有時，小數字有更多可能，使得編碼零連串對於比特流的特定部分更加有效。然而，PTC熵編碼器將拾取數據，在最高位平面上進行一次通過，並回去在下一位平面上進行一次通過。例如，如果數據是16位，通過首先在位#16上完成並編碼。當然，大多數數據將是零，因為該位只對很大的數分割，然後繼續向下。當到了位#5、4、3、2和1，這些位具有許多零和一，這意味著它到達了編碼它們已沒有什麼幫助的一點。通常最低位是隨機的，以至於用一個比特來編碼這個位，即每個輸入比特都直接複製到輸出。PTC熵編碼帶來的問題是位平面上的編碼需要幾次通過數據。具體而言，PTC熵編碼器不得不編碼最高位、下一位、然後再下一位等等。顯然，這花費了太大量的時間，而且在某些情況下，PTC熵編碼器比此處所公開的自適應G/R編碼器和方法慢1.5到3倍。
編碼規則自適應G/R編解碼器和方法使用基於G/R參數k的新穎的編碼規則。表2給出自適應G/R編解碼器和方法用於將整數值x映射到二進位比特流的編碼規則。

表2
在這個工作示例中，定義映射值u。自適應G/R編碼器和方法的輸入值x可正可負。輸入值x映射到值u，其中u只有正值。因而，帶符號的輸入值x被轉換成不帶符號的等價表示u。公式4給出從x到u的映射。具體而言，該映射表示，0映射到0、1映射到1、-1映射到2、2映射到3、-2映射到4等等，因而u值總是正的。這完成後，就可使用G/R表(表1)，因為G/R表只用於非零值。這種映射使得自適應G/R編解碼器和方法能處理任何輸入字母。換言之，由於使用了G/R表(它可處理任何輸入數)，因此輸入字母可以是無限的，且自適應G/R編解碼器和方法可處理任意大小的數字輸入。自適應G/R編解碼器和方法只受限於作業系統可處理的數字的大小。應該注意，實際上，G/R編碼表1不需要存儲在存儲器中。很容易明白，表條目具有足夠的結構，使得對於任意u值和編碼參數k，都能方便地計算出碼字。
給定u數據，表2規定使用自適應G/R編碼器和表1例示的G/R編碼規則來編碼輸入值x的映射值u。因而，用於編碼x的碼字基於u和k值。G/R參數k是使用後向自適應技術和創新自適應規則來更新的，如以下詳細討論。表2中的規則精確定義了編碼器如何編碼，這意味著解碼器可使用表2中的同樣規則來恢復(或解碼)已編碼數據。
小數自適應小數自適應使用經比例縮放的G/R參數K來代替G/R參數k。小數自適應是減慢自適應的一種方法。使用沒有小數自適應的自適應G/R編解碼器和方法是可能的。然而，如果沒有小數自適應，則自適應通常變化太快，而無法正確追蹤用於輸入數據的最優參數。
在這個工作示例中，k參數的自適應是使用經比例縮放的K參數來完成的。因而，更新K而非k。k和K之間的關係如下k＝K/L，其中L是如上解釋的比例縮放參數。因此，當進行自適應時，自適應K值，而K除以L就獲得k值。注意，所有值都是整數，所以通過k＝K/L，意味著是結果的整數部分。還要記住，固定比例縮放參數L被設為等於2的冪的值(例如L＝16)，則除以L的除法可通過位移運算來有效執行。
小數自適應是較佳的，因為自適應G/R編解碼器和方法對生成的每個代碼都進行了G/R參數k的調整。換言之，在編碼了輸入值或串後，執行自適應規則。如果k直接通過整數值變化來自適應，則由於它們是整數，所有可做的是保持相同或至少增減1。然而，假設輸入數據變得更大，意味著參數應該增加。
小數自適應允許k的小數增加。例如，k可以用.5代替1來增加。然而，這是不允許的，因為k是整數參數。因此小數自適應執行K的整數增加，且用L除以K給出k的小數增加。這保證了參數k沒有振蕩。
作為使用自適應，定義一個標誌是可能的，這樣如果數據有增減，在增減該參數前通過則某些數量的編碼周期。可定義追蹤編碼周期數的新參數。換言之，該參數將追蹤在參數改變前條件(輸入數據增加或減少)發生了多少次。但是應該注意，這一技術是經試驗的，且小數自適應提供了較好的結果。
Golomb/Rice(k)參數自適應G/R參數k在編碼了每個輸入值或串後被自適應。當使用小數自適應時，實際上自適應經比例縮放的G/R參數K，而非直接自適應k。表3給出用於G/R參數k的自適應規則。在編碼了值u後，通過自適應值p＝u＞＞k來控制自適應，這意味著u向右移k位。在自適應後，k的值被設為k＝K/L，其中L是常數。在這個工作示例中，L＝16。

表3表1的G/R碼取決於參數k。例如，如果一個不完全連串後的值為13，13的GR碼是「1111111111110」(對於k＝0)，且如果k＝1，則為「11111101」。k越大，則表示13的數將越小。而k越小，則表示13的數將越大。因而，參數k必須已知。這意味著如果對k選擇了合適的值，自適應G/R編解碼器和方法會完成得很好。但是，使用k的大值並不總是有利的，因為這將對於輸入數據的較小值產生較長串，如表1所示。換言之，k值的合適選擇取決於輸入數據。如果值為13，則使用k的大值是個好主意。但是，假設不完全連串後的值為「1」。則k的較小值是所希望的。因而，對於不完全連串之後的小值，使用小k更好，而對於大值，使用大k更好。因此，k的選擇與值的概率有關。在現有技術中，有對為此目的的大量理論成果如果輸入數據的概率已知(例如，如果輸入數據是拉普拉斯，其中存在控制衰減的單個參數)，則有眾所周知的公式，從中可計算要使用的衰減參數，即參數k。這平均起來使映射使用儘可能少的比特。
因而，k參數是自適應的是很重要的。以這種方法，如果在輸入數據上有大值出現，則k應該增加，因為對於大值，k越大越好。另一方面，如果有較小值出現，則k應該減少。直觀上，能夠明白，對於大數字，k應該增加，而對於小數字，k應該減少。因此，只要k以足夠小的幅度改變(諸如當使用小數自適應時)，對於輸入數據的最優參數將總是被正確地追蹤。
表3所示的k的自適應規則是相當新穎的。在自適應G/R編解碼器和方法中，任何值都可出現，因此這個值必須被編碼。編碼是使用自適應G/R編碼器和G/R參數k來完成的。參考表3，輸入數據是x。輸入數據x可以是任何整數，小x更可能(可以是正的或是負的)。但是，G/R編碼只用於正數。x的直接映射(見公式4)用於將x映射成u。k的自適應是由自適應值p來控制的，p被定義為u向右移k位。因而，自適應值p是u的按比例縮小形式。或者，等價地，p參數是近似於u/2k的整數。向右移k位等於將此數除以2k。例如，如果一個數向右移5位，這就與將此數除以32(即25)相同。餘數被捨去，而只使用商。
參考表3，如果自適應值p等於零，則K被更新並由K減少一整數常數B3來替換。如果自適應值p等於一，則K不變。如果自適應值p大於一，則K被更新並由K減少自適應值p來替換。
如果p的自適應值等於一，這意味著u值接近於2k，且就是對它們而言參數k是正確的那些值。因此，如表3所示，沒有變化。如果自適應值p的值是0，這意味著輸入值小於2k。即要開始減少k(因為輸入值小於2k)。自適應值p大於1的情況是不太可能的，因為輸入值不可能非常大。但如果數字是大的且p＞1，則要開始增加k參數。
自適應G/R編碼器圖9是示出圖2和4所示自適應G/R編碼器200的編碼細節的工作示例，包括G/R參數k自適應規則。該過程開始(框905)於讀取輸入值u(框910)。自適應G/R編碼器200的兩個主要過程是G/R編碼(框915)和G/R參數自適應(框920)。
G/R編碼過程915始於計算自適應值p和v(框925)。向比特流追加等於一的p個比特(框930)。v的k位二進位值則被追加在該比特流後(框935)。這些操作包括如表1所定義的自適應Golomb/Rice編碼器。
G/R參數自適應過程920包括確定自適應值p是否等於一(框940)。如果是，則自適應值p保持不變(點945)。否則，做出關於自適應值p是否等於零的另一判斷(框950)。如果不是，則K被更新並用K減少一整數常數B3來替換(框955)。否則，K被更新並用K增加自適應值p來替換(框960)。最後，該過程設置k等於K除以L(框965)，並且該過程結束(框970)。
結果該工作示例的自適應G/R編解碼器和方法已在圖像、音頻和地圖數據壓縮的應用中實現。在這些應用中使用自適應G/R編解碼器和方法的結果是壓縮比可與最複雜熵編碼器相比，但以更簡單的實現方式。
特別地，對於用於整數數據的現有熵編碼器，自適應G/R編解碼器和方法對於大量如圖1中的源碼元概率分布達到了接近於理論最大值(由源熵所規定的)壓縮比。作為示例，眾所周知的Golomb/Rice和Huffman編碼器只對於每碼元1個比特或更高些的源熵有效。
VIII.解碼自適應G/R編解碼器和方法還包括可基於上述編碼器精確實現的解碼器。參考圖2B，計算設備(框250)可以只實現G/R解碼器240。自適應G/R解碼器240和方法從已編碼比特流接收碼字(框230)。接著，自適應G/R解碼器240通過應用上文對於自適應G/R編碼器200所述的逆規則來解碼碼字。接下來，G/R參數使用與自適應G/R編碼器的規則完全相同的規則來自適應。最後，輸出解碼後的(或重建的)整數數據(框260)。
由於編碼規則是唯一可解碼的，且解碼器的自適應規則與編碼器的相同，因此前面描述的編碼規則和自適應規則也精確地描述了解碼器的操作。
本發明的以上描述已為說明和描述之途而給出。它並不旨在窮盡本發明或將本發明限於所公開的精確形式。各種修改和變體鑑於以上示教都是可能的。本發明範圍不受本發明詳細描述所限，而只受所附權利要求書所限。
權利要求
1.一種用於處理數字數據的方法，其特徵在於，包括使用Golomb/Rice(G/R)參數編碼所述數字數據的輸入值以生成所述輸入值的碼字；在生成所述碼字後使用具有自適應規則的後向自適應技術來更新G/R參數；以及對所述數字數據的每個值重複所述編碼和更新。
2.如權利要求1所述的方法，其特徵在於，還包括定義一自適應值；以及當所述自適應值等於零時，減少所述G/R參數。
3.如權利要求2所述的方法，其特徵在於，還包括當所述自適應值等於零時，使所述G/R參數減少一整數常數。
4.如權利要求2所述的方法，其特徵在於，還包括當所述自適應值等於一時，保持所述G/R參數不變。
5.如權利要求4所述的方法，其特徵在於，還包括當所述自適應值大於一時，增加所述G/R參數。
6.如權利要求5所述的方法，其特徵在於，還包括當所述自適應值大於一時，使所述G/R參數增加所述自適應值。
7.如權利要求1所述的方法，其特徵在於，還包括定義一比例縮放參數；以及定義一經比例縮放的G/R參數為等於所述G/R參數乘以所述比例縮放參數。
8.如權利要求7所述的方法，其特徵在於，還包括在生成所述碼字後，通過使用具有自適應規則的後向自適應技術更新所述經比例縮放的G/R參數而非所述G/R參數。
9.如權利要求8所述的方法，其特徵在於，還包括設置所述經比例縮放的參數等於十六；以及基於所述數字數據的衰減參數確定所述G/R參數的值。
10.如權利要求1所述的方法，其特徵在於，所述數字數據還包括具有如下值的整數向量(a)對於每個值為零的最可能值；以及(b)非零值，它具有按所述非零值增加而減少的概率。
11.一種具有用於執行如權利要求1所述的計算機可執行指令的計算機可讀介質。
12.一種具有用於編碼具有整數值的數字整數數據的計算機可執行指令的計算機可讀介質，其特徵在於，包括使用自適應Golomb/Rice(G/R)編碼和G/R參數k來編碼所述整數值的每一個，以對所述整數值的每一個生成一碼字；使用所述G/R參數k來定義一經比例縮放的G/R參數K；以及在生成每個碼字後使用後向自適應規則來更新所述經比例縮放的G/R參數K。
13.如權利要求12所述的計算機可讀介質，其特徵在於，還包括定義一比例參數L；以及定義所述經比例縮放的G/R參數K為K＝k乘以L。
14.如權利要求13所述的計算機可讀介質，其特徵在於，還包括設置所述經比例縮放的參數等於是二的冪的值。
15.如權利要求12所述的計算機可讀介質，其特徵在於，所述數字整數數據還包括包含N個整數的向量x，且其中，所述向量x的每個元素x(n)，其中n＝0到N-1，具有這樣的概率分布最可能值為零且距零更遠的值有著快速下降的概率。
16.如權利要求15所述的計算機可讀介質，其特徵在於，所述概率分布由以下公式給定P(x,)=1-1+|x|]]>並且其中，參數θ控制當x的絕對值增長時概率的衰減速率。
17.如權利要求12所述的計算機可讀介質，其特徵在於，還包括定義一自適應值p；以及當p＝0時用(K-B3)代替K，其中，B3是一整數常數。
18.如權利要求17所述的計算機可讀介質，其特徵在於，還包括當p＝1時保持K不變。
19.如權利要求18所述的計算機可讀介質，其特徵在於，還包括當p＞1時用(K+p)代替K。
20.如權利要求17所述的計算機可讀介質，其特徵在於，還包括定義一參數u，當x＞0時它為2x；定義u，當x＜0時它為-2x-1；以及定義p＝u＞＞k，意指p等於u向右移k位。
21.一種用於編碼和解碼數字整數數據的計算機實現的過程，其特徵在於，包括使用自適應Golomb/Rice(G/R)編碼和G/R參數k來編碼所述數字整數數據的每個值x；定義一經比例縮放的G/R參數為K＝k*L，其中L是比例縮放參數；在編碼了所述數字整數數據的每個值x後，使用具有自適應規則的後向自適應技術來更新所述經比例縮放G/R參數K；將所述數字整數數據的已編碼值追加到比特流中；以及使用G/R解碼器解碼所述比特流，來精確恢復所述數字整數數據的每個值x。
22.如權利要求21所述的計算機實現的過程，其特徵在於，還包括當x＞0時用映射參數u＝2x代替x；當x＜0時用u＝-2x-1代替x；以及定義一自適應參數p為u向右移k位，p＝u＞＞k。
23.如權利要求22所述的計算機實現的過程，其特徵在於，所述自適應規則還包括當p＝0時用(K-B3)代替K，其中B3是一整數常數。
24.如權利要求23所述的計算機實現的過程，其特徵在於，所述自適應規則還包括當p＝1時保持K不變。
25.如權利要求24所述的計算機實現的過程，其特徵在於，所述自適應規則還包括當p＞1時用(K+P)代替K。
26.一個或多個其上具有計算機可讀指令的計算機可讀介質，當由一個或多個處理器執行所述指令時，使一個或多個處理器實現如權利要求21所述的計算機實現的過程。
27.一種用於編碼包含整數值的數字整數數據的自適應Golomb/Rice(G/R)編碼器，其特徵在於，包括一具有G/R參數k的Golomb/Rice(G/R)編碼器，用於編碼所述整數值；以及一用於在編碼了所述整數值的每一個後使用具有自適應規則的後向自適應技術來更新G/R參數k的裝置。
28.如權利要求27所述的自適應G/R編碼器，其特徵在於，所述自適應規則還包括一用於如下更新所述G/R參數k的裝置定義一自適應值p；當p＝0時使k減少一整數常數；當p＝1時保持k不變，以及當p＞1時使k增加p。
29.如權利要求28所述的自適應G/R編碼器，其特徵在於，還包括一用於如下定義經比例縮放的G/R參數K的裝置定義一比例參數L；定義S＝s*L；以及定義K＝k*L。
30.如權利要求29所述的自適應G/R編碼器，其特徵在於，還包括一用於用所述自適應規則更新K而非k的裝置。
31.一種用於解碼已編碼比特流的方法，其特徵在於，包括從所述已編碼比特流接收一碼字；用一Go1omb/Rice(G/R)參數解碼所述碼字；在解碼所述代碼字後使用具有自適應規則的後向自適應技術來更新所述G/R參數；以及對所述已編碼比特流的每個碼字重複所述解碼和更新過程，以恢復重建的數字數據。
32.如權利要求31所述的方法，其特徵在於，還包括定義一自適應值；當所述自適應值等於零時減少所述G/R參數；當所述自適應值等於一時保持所述G/R參數不變；以及當所述自適應值大於一時增加所述G/R參數。
33.如權利要求32所述的方法，其特徵在於，還包括當所述自適應值等於零時使所述G/R參數減少一整數常數。
34.如權利要求32所述的方法，其特徵在於，還包括當所述自適應值大於一時使所述G/R參數增加所述自適應值。
35.如權利要求31所述的方法，其特徵在於，還包括定義一比例縮放參數；以及定義一經比例縮放的G/R參數為等於所述G/R參數乘以所述比例縮放參數。
36.一種具有用於執行如權利要求31所述的方法的計算機可執行指令的計算機可讀介質。
37.一種用於解碼已由一編碼過程編碼為已編碼比特流的數字整數數據的過程，所述編碼過程使用一Golomb/Rice(G/R)參數來編碼所述數字整數數據的輸入值以生成所述輸入值的碼字、在生成所述碼字後使用具有自適應規則的後向自適應技術更新所述G/R參數、並對所述數字整數數據的每個輸入值重複所述編碼和更新，所述過程包括從所述已編碼比特流接收一串碼字；使用自適應G/R解碼和G/R參數k來解碼每個碼字；用所述G/R參數k定義經比例縮放的G/R參數K；以及在解碼每個碼字後使用所述具有自適應規則的後向自適應技術來更新所述經比例縮放的G/R參數K。
38.如權利要求37所述的過程，其特徵在於，還包括定義一自適應值p；以及當p＝0時用(K-B3)代替所述經比例縮放的G/R參數K，其中B3是一整數常數。
39.如權利要求37所述的過程，其特徵在於，還包括當p＝1時保持所述經比例縮放的G/R參數K不變。
40.如權利要求37所述的過程，其特徵在於，還包括當p＞1時用(K+p)代替所述經比例縮放的G/R參數K。
全文摘要
一種使用具有新穎的自適應規則的新穎後向自適應技術進行整數數據的無損自適應Golomb/Rice(G/R)編碼的方法和系統。該自適應G/R編碼器和解碼器(編解碼器)及方法使用了在生成每個碼字後調整G/R參數的自適應規則。這些自適應規則包括定義一自適應值並根據該自適應值調整G/R參數。如果自適應值等於零，則使G/R參數減少一整數常數。如果自適應值等於一，則G/R參數保持不變。如果自適應值大於一，則使G/R參數增加該自適應值。此外，該自適應G/R編碼器和方法包括小數自適應，它根據G/R參數定義了經比例縮放的G/R參數，並更新和調整該經比例縮放的G/R參數來減慢自適應速率。
文檔編號G06T9/00GK1783144SQ20051010888
公開日2006年6月7日 申請日期2005年9月29日 優先權日2004年10月29日
發明者H·S·馬爾瓦 申請人:微軟公司