調色圖象的壓縮及其m陣符號集的比特狀態編碼的二進位化的製作方法
2023-09-16 23:14:25 2
專利名稱：調色圖象的壓縮及其m陣符號集的比特狀態編碼的二進位化的製作方法
本份專利文件的一部分公開含有受版權保護的內容。版權的持有者不反對任何人對此專利商標局的專利文件或記錄的精確形式出現的專利文件或專利公開進行靜態複印，然而在其他方面卻保留所有的版權。
受讓給本專利申請的受讓人的、名稱為「並行數據解碼和編碼的方法和設備」的美國專利NO.＿＿＿＿＿(美國專利申請號NO.08/016,035；1993年二月十四提交的)被援引在這裡以便供所有目的而做為參考，並且在下文被稱之為「ABS編碼器」基準。
本發明涉及圖象壓縮領域。尤其涉及利用熵編碼並行熵編碼器的調色圖象(palettized image)的壓縮。
一般來說，圖象壓縮是以數位化圖象來操做的。為了實現圖象的數位化，在該圖象上的許多點上對該圖象進行取樣，這些被取樣的圖象經常稱為象素。每個象素具有在該圖象中的位置和象素的顏色。舉例來說，圖象可由1024乘768個象素的二維矩陣來表示，其中每個象素具有一個24個比特的值。每個象素值可以表示一個不同的顏色，因此允許該圖象將制用224，即16777216個可能的顏色來表示。
在許多應用中，每個象素值是與該圖象被數位化的當時的某一具體顏色相關的。利用這種設計，一個給定象素的顏色可以由該象素的值來確定。在另外一些應用中，數字圖象是已調色的圖象。在調色圖象中，每個象素值對於顏色而言不是固定的，而是指向一個顏色調色表的指示字。當一個調色化的圖象要被顯示時，象素的顏色是利用作為調色表的一個指數的象素值確定的，該調色表確定每個象素值和分配給該象素值的顏色之間的關係。
調色化(palettization)是從一組所有可能的顏色中選出幾種顏色，例如16777216(224)種顏色中的256(28)種顏色，和由從所選出的幾種顏色中的一種代替任意一種顏色的方法。結果，一個調色化圖象可以有效地作為代碼薄表被存儲(繼續上面的例子)，對於256個變址的每個而言，所選顏色的全部24比特的顏色描述，接著在該圖象中每個象素的8比特變址。因此發現通過僅一次全面描述所選擇的顏色和涉及每個象素僅輸入一個變址到代碼薄可以節約存儲空間。
由於對於表示一個圖象所需數據數量的緣故，在許多圖象應用場合中，圖象的壓縮都是重要的。在上述的例子中，表示一個單一的未壓縮的圖象需要24×1024×768、或18×874×368比特(2,359,296位元組)，或者在調色化圖象的情況下，需要8×1024×768比特(6,291,456比特)。對於運動圖象壓縮甚至更為重要了，這種圖象要求諸如每秒30幅圖象的高幀速率圖象的連續碼流。壓縮不僅僅節約圖象存儲的存儲器，壓縮還允許通過有限帶寬的信道使圖象有效地傳送。當然，對於諸如運動圖象的應用，圖象中須能夠被足以使它們以幀速率顯示地快速解壓縮。當進行預先壓縮的時候，常常這種應用要求實時解壓縮。在一些進行預先壓縮的實施例中，到解壓縮器的輸入是壓縮的數據的數據塊，該數據塊可以被存儲在一個存儲器中和在壓縮以後的任何時間被解壓縮。
壓縮操作進行多少程度的一個度量是壓縮比。壓縮比是未壓縮數據對已壓縮數據量值的比。壓縮質量的另外一個度量是數據能夠以多快的速度被壓縮和被解壓縮。在許多應用中，壓縮的速度不象解壓縮的速度那麼重要，因為壓縮不需要實時地進行。
經常由於許多數據特徵是已知的，使壓縮比得以改善。一般，通常數字圖象是波形量化的結果，因此它們保存許多原有信號的特徵，諸如象素顏色值的相對連續性的存在。對於調色化圖象而言，通常不存在這種連續性，和不能直接被用於改善壓縮比。
對於調色化圖象，兩個象素值之間的顏色差不能必然地從這些象素值中推導出來，因為象素值不代表象素的顏色。而它們僅代表顏色值的代碼表的變址，或調色表的變址。壓縮調色圖象的問題可以歸結為壓縮一個輸符號序列的問題，其中每個輸入符號是在M-ary符號集中的一個符號。
Y.Chin等人在出版物ICASSP-93，第5卷，第325-328頁中的文章」調色圖象的露希壓縮」描述了調色化圖象的露希壓縮的一個例子。在通常露希壓縮獲得較好的壓縮比的同時，許多應用不能容許由露希壓縮產生的失真，和固化要求較小損耗的壓縮。對於較小損耗壓縮而言，一個信號被壓縮為一個已壓縮信號，該信號可以被從已壓縮的信號中精確地恢復原來的信號，因此不引入失真。
從上面的描述看出，需要一種用於壓縮和解壓縮調色圖象的改進的方法和設備。
利用本發明的優點，提供了改進的調色圖象壓縮，這種改進的壓縮允許圖象被有效地壓縮和快速的去解壓縮。
在本發明的一個實施例中，輸入的符號是在M-ary符號集中的符號和根據輸入數據的前後關係模型被二進位化，這裡選擇二進位化是利用二進位編碼器提供良好的壓縮。編碼器變換輸入符號為碼字，而解碼器變換碼字為輸入符號。具體的二進位化是由一符號變換表確定的，該表將每個輸入符號映射為一個二進位值數。這種映射是由要被壓縮的圖象確定的，和一般作為附加信息與被壓縮的圖象一起被傳送。
用於產生變換表的映射的一種方法是每次分配給一個輸入符號一個變址。該分配給輸入符號的變址是該變址比特、輸入符號的分布、輸入符號的前後關係、和已經被分配的符號與變址的函數。對於一個具體的輸入符號而言，從剩餘未分配的各變址中分配一個變址，對於已知已經分配的變址而言，提供最小部分比特狀態熵和對於各輸入符號分配各變址。然而這種方法對於已知的一組符號分布和上下文而言可能不會達到可能的整體的最小比特狀態熵，對於一個可行的計算量來說，僅提供良好的「局部」最小值。
然後，被變換的輸入數據通過一個前後關係模塊、概率估算模塊、和一個比特發生器，其輸出是被壓縮的數據。相反的地程用於去壓縮該數據。如果必要，該變換表作為附加數據被從壓縮器傳送到解壓縮器。在變換表預先固定的情況下，不需要傳送該表。
在本發明的另一個方面，在利用少量存儲器的前後關係模塊的情況下，而利用一個前後關係模塊對調色圖象提供良好的壓縮效果。
在本發明的另一個方面，壓縮和解壓縮是以並行執行的，和到壓縮器的輸入被緩衝的被重新排序，置於一個正在被編碼的比特與確定前後關係的各比特之間的空間，和對該正在被編碼的比特進行編碼。一個比特與其前後關係的各比特之間的空間被安排得有足夠的延時，以便當該比特到達解壓縮器時候比特的解碼取決於該各前後關係比特的情況下該前後關係比特能被全面地解碼。解壓縮器包括一個用於執行相反重新排序的裝置，以便解壓縮器的輸出是和壓縮器的輸入一樣。在一些實施例中，並行壓縮器的輸出帶有在多個並行解壓縮器端分離各個信道所需的非常少量的附加信息來通過一個單一的通信信道。
在一些具體的實施例中，輸入符號是從256個符號的符號集中選出的，由一個適當的數字計算機執行該變換過程，壓縮過程是以非實時執行的，而解壓縮過程是以實時執行的。利用256個輸入符號，變換表產生256個字節。在一個具體實例中，變換表是根據整個某些組圖象或圖象部分輸入符號的概率分布的，和對於每組圖象或圖象部分新的變換表被從壓縮器傳送到解壓縮器。
通過參照本說明書的其餘部分和所附加圖的實現對於本發明的特點與優點的進一步理解。
圖1是一個數據壓縮系統的框圖，示出了一個壓縮器和一個解壓縮器；圖2是表示在圖1中的壓縮的框圖；圖3是表示在圖1中的解壓縮器的框圖；圖4是一個存儲前後關係箱概率表的存儲器的詳圖；圖5是包括一個根據變換表變換M-ary符號的變換器的數據壓縮系統的框圖；圖6是一個變址優化器的框圖，該優化器根據要被壓縮的數據塊的數據前後關係產生變換表；圖7是由一個變址優化器確定適合的變換表所執行的過程的流程圖；圖8是說明由圖2和圖3的前後關係模塊實現的各種前後關係模塊；圖9是一種並行壓縮系統的框圖；圖10是利用一條單一信道的並行壓縮系統的框圖；圖11是說明重新排序緩衝器的操做的框圖；圖12是表示一種前後關係狀態的記錄邏輯圖；和圖13(a)和(b)是管道編碼器(pipeline coder)的時間圖，該編碼器同時能夠處理多個輸入符號。
下面的描述分別幾個部分。第一部分描述熵編碼。第二部分描述當利用熵編碼時，利用變換改善壓縮。第三部分描述如何前後關係模塊化能夠通過更精確地估算符號概率而改善熵編碼性能。前後關係模塊化可以被用於或不被用於變換。第四部分描述如何並行壓縮和解壓縮被用於改善數據速率。最後，第五部分描述如何緩衝被用於簡化並行實現和仍然保持允許數據被並行壓縮的原因。
熵編碼器在數據壓縮技術領域是公知的。編碼輸入符號為輸出碼字的熵編碼器是一種損耗較小的過程，即原來輸入符號可以僅從輸出碼字中提取。熵編碼器被如此命名是由它試圖實現由各輸入符號的熵確定的接近理論上限的壓縮比。通常編碼器和解碼器被設計為解碼器是編碼器的反變換。術語「編碼器」(coder)是指一種裝置，該裝置或者是一個編碼器，或者是一個解碼器，或者是二者兼有。
這裡不描述熵編碼器的全部細節，而僅描述與本發明相關的某些細節。在熵編碼器中，從輸入端讀入一些輸入符號和一個或多個輸入符號產生一個碼字的輸出。特定的輸入符號(或多個符號)與輸出碼字的組合是由所利用的碼確定的。在一個優化系統中，所用的碼是根據各輸入符號的概率分布選擇的。在一種自適應熵編碼器中，所利用的碼可以隨概率分布改變。如果概率分布估算的好，或精確地已知，並且利用了對於那種概率分布的優化碼，則將產生良好的壓縮。
如果輸入符號是各個比特(即，一個符號是0或是1)，則該編碼器是二進位熵編碼器。二進位熵編碼器優於其他的熵編碼器，這其中硬體的簡化是重要的。ABS編碼器是一種二進位編碼器。在二進位熵編碼器中，輸入的各符號被送到一個比特發生器，該發生器在其輸入端接收一個或多個比特和為所接收的這些輸入比特輸出一個碼字。如果該比特發生器在輸入碼流中設置「0」和「1」的概率分布指示，則它可以利用該信息選擇適當的碼字的利用。另一方面，該比特發生也可能按照由概率估算模塊確的僅僅被指令利用哪一種碼。這些碼可能按照比特發生器確定平均輸出碼字對於實際輸入符號的概率分布而言太長或太短而改變。對於更為詳細的細節，參考ABS編碼器參考資料。
「0」和「1」的概率分布對於良好的估算是重要的。如果利用二進位熵編碼器，要被壓縮的圖象的象素值首先需要被二進位化，這些象素值是來自一個M-ary符號集，其中M大於2。在某些情況下，正如所證明的那樣，具體的二進位化的選擇影響輸入到二進位熵編碼器的比特碼流的熵，和正如上面所解釋的那樣，該熵設置一個多少比特發生器能夠壓縮輸入比特碼流的限制。這裡的區別不是清楚的，即「象素輸入符號」或「象素符號」用於表示輸入到一個壓縮器的被二進位化之前要被壓縮的數據單元1和「二進位輸入符號」用於表示一個輸入到二進位熵編碼器的比特發生器的一個輸入符號。
對於非調色化圖象數據，象素符號可以按照意味著該象素值的色信息被二進位化。例如，假設一個象素值取256個值之一，和該所取的值表示該象素的顏色。在這種情況下，如果類似的顏色由類似的8比特值代表，則可以可靠地假設，00001100與00001101在顏色上對00001100與11111111更近似。在多個本文中討論過的例子中，M是256，和在M-ary符號集中的符號是由k比特二進位代表示的，其中k＝8。應當理解為，M和K的其他值也是可能的，包括不是2的偶數冪的M值，唯一的限制是k≥log2M。
再回到這個例子，因為在通常的圖象中，相鄰的象素常常是類似的顏色，表示每個象素所要求的多個比特通過的該象素與一個相鄰象素之間象素顏色值的差表示每個象素可以被減少。這種數據的預處理一般導至較好的壓縮，因為代表各個值所需的比特數與該一組值的熵有關。但是，在調色圖象的情況下，兩個顏色之間的一種特定的關係不意味著來自那種另比特表示的比特之間的相關性。例如，在調色圖象中，00001100與00001101可能是非常不同的顏色和00001100與1111111可能是近乎相同的顏色。全取決於調色。
因此，通過精確地估算比特碼流的概率分布，和通過選擇輸入象素符號的二進位化，該二進位化對比特發生器提供一種低熵比特碼流，調色化圖象的壓縮能夠被改善。前述問題的解決方案討論在下面題目為「前後關係的模式」部分和後面問題的解決方案討論在下面題目「變換」的部分。
解壓縮對於一個正確解碼來自輸出碼字的輸入符號的解壓縮器而言，解壓縮器需要知道哪種碼被用於哪種碼字，除非編碼器不是一種自適應編碼器和利用一種固定碼。因為指示該碼的發送數據的附加信息將會減少壓縮的有用程度，解壓縮器應能夠從碼字中提取出該碼的指示。如果用於一個已知二進位符號的碼是由概率估算確定的，這是可能的，因為該估算僅取決於已經被編碼為碼字的各比特。如果這是事實，利用反饋環和存儲關於輸入符號被恢復的信息的方式，解壓縮器可以確定什麼碼被用已被解碼的數據。
上下文模式更精確地概率估算，更優化的所用碼是被壓縮的數據。一種改善概率估算的方法是保持對多個前後關係進行概率估算。在本文中所用的一個輸入象素的前後關係與該輸入象素有確定關係的一個象素或多個象素。例如，在一種前後關係模式中，一個輸入象素的前後關係是由上面的輸入象素的象素確定的。當進行確定一個比特發生器的輸入的比特碼流的一個比特的前後關係時，其前後關係是由與該輸入比特有確定關係的一些象素和或一些比特提供的。這種關係是由前後關係模式確定的。
圖8是五種前後關係模式的說明圖。在各種模式中，指針P表示上下文應用的輸入到當前輸入符號的比特發生器的當前輸入比特的比特位置。在所有示出的前後關係中，前後關係是從一些當前輸入符號的比特子集、由P指示的比特位置得到的，和在該圖象中對於當前輸入符號的象素上面的象素的符號比特稱為「上面」符號。應當理解為，其他象素，諸如當前象素左右的象素，或其他未示出的前後關係模式可能同樣很好的地工作。
每個前後關係模式規範了該前後關係如何被確定的，和能夠被容易計算的可能的前後關係數目。每於每種前後關係模式而言，去保留概率估算，和當一個符號具有那種前後關係出現時利用那種概率估算。術語「前後關係箱(context bin)」常常用於表示一個符號落入哪個前後關係。參照圖8，前後關係模式(a)是一處比特位置前後關係模式。利用這種模式，該前後關係僅僅是比特位置，該前後關係要求k前後關係箱。其中k＝8，這是一種前後關係箱的合理數。
前後關係模式(b)是一種比特平面前後關係模式，這樣命名是由於對於每個比特平面有一組M個前後關係。因此，有M×K(2048個，在M＝256，K＝8的情況下)前後關係。
一個值得注意的特點是，在模式(a)和(b)中當前象素的前後關係用於表示當前象素的各比特是獨立的。
前後關係模式(c)是一種取決於比特狀態的前後關係模式，其中如果當前比特和前面各比特在當前符號中，前後關係由該比特位置確定。在這種模式中，存在2k-1個前後關係(當P在第一個比特時，為1前後關係，對於P在一個比特時，為2前後關係，如此類推)。對於K＝8時，這種模式提供255個前後關係。注意，一個比特的前後關係並不依靠其值，對於這些比特也不需要編碼，以便解碼器不需要這些未解碼的比特去確定如何解碼一個比特(圖8假設一種頂對底和左對右處理序列)。
前後關係模式(d)是一種良好的前後關係模式，該模式計入前面象素的所有比特和在當前比特之前的輸入象素的各個比特。這種前後關係模式組合了模式(b)和(c)的信息，和從而提供了M×(2K-1)個前後關係。在這種前後關係模式可能提供細微的前後關係區分的同時，對於存儲各前後關係的值的所需存儲器的壓縮器或解壓縮器的硬體實現來說可能會價格過高。對於M＝256和K＝8，這種模式要求65280個前後關係。如果每個內容要求8比特存儲量，這種前後關係模式僅為此目的將要求14k存儲器。然而，這種前後關係模式優於模式(a)和(b)的是利用這種模式的壓縮器的性能是良好的，而無論所用的二進位化怎樣，因為當前象素的以前比特被用於確定前後關係。
前後關係模式(e)是一種混合前後關係模式，該模式已可看出是一種在存儲器要求與前後關係模式質量之間的良好折中。在這種模式中，前後關係是當前輸入符號的P-1以前的比特和前面符號的K-(P-1)的後比特。這要求每個比特位置2K前後關係(對於K＝8，為2048前後關係)。
一般情況下，壓縮器與解壓縮器之間前後關係模式是固定的，而防止壓縮器和解壓縮器轉換前後關係模式是毫無必要的，只要它們確定在任何給定時間利用哪一個前後關係模式就可以了。如果可變的上下文模式是允許的，必須有保證那些前後關係模式是相同的機制，例如通信信道附加信息指示當前的前後關係模式。
作為解釋如各圖所示的數據壓縮系統的基礎，提供了上面熵編碼與前後關係模式的討論，現在將要描述這些系統。參照圖1，示出了按照本發明用於壓縮由M-ary符號集組成的各符號的數據的一個數據壓縮系統100的實施例，該系統包括壓縮器102、信道104和解壓縮器106。到壓縮器102的輸入信號是每個代表在一個圖象中的象素值的輸入象素符號的碼流，不過其他類型的數據也可以利用。由壓縮器102將輸入象素符號變換為已壓縮的碼字，通過信道104轉移到解壓縮器106。僅從接收的各碼字，和可能的壓縮器102操作的知識和一個變換表(如果使用的話)，解壓縮器106使來的輸入符號或其等效信號。在某些情況下，原來的輸入符號被從一種表示翻譯為變換表示和該數據壓縮系統處理被解壓縮的符號，並不執行逆變換。
本發明的一個好處是對於調色圖象的象素值的輸入符號增加了壓縮比。因此，無論信道104是否具有有限的帶寬，由本發明提供的壓縮是都有用。信道104的例子包括諸如存在於圖象存儲器與顯示裝置，或存儲裝置與用業存儲圖象的裝置之間的通信信道。信道104還可以表示在具有存儲器裝置形式中被壓縮的數據的轉移，諸如遊戲存儲部件(game cartridge)，數據在一個位置上被壓縮。在後者的情況下，信道104的帶寬限制表現為用於存儲的裝置中的可用存儲器的數量限制。
參照圖2，壓縮器102包括前後關係模塊108(1)、概率估算模塊(PEM)110(1)、比特發生器112(1)、前後關係存儲器114(1)，和前後關係箱概率存儲器116(1)。括號中的號碼用於區分出現在壓縮器102和在壓縮器106兩者中相同編號的部件。通常可用於壓縮器102或者解壓縮器106的部件的標號是不用括號的號碼表示的。雖然本發明是結合示於圖2的一個具體壓縮器102描述的，其他壓縮器同樣也能很好地工作。例如，不是所有的壓縮器要求所示的在PEM UO和比特發生器112之間進行連接，和PEM 110可能依靠並非由比特發生器112提供的數據去更新其概率估算。
前後關係模塊108(1)連接到壓縮器102的輸入端和由此接收輸入象素符號。如果使用變換器，到壓縮器102的輸入信號是被變換的輸入象素碼流。前後關係模塊108(1)包括兩個輸出，前後關係箱識別輸出和判決輸出，這兩個輸出都到PEM 110(1)。假設輸入是對K比特符號二進位化的，則前後關係模塊108(1)對每個輸入象素符號輸出k個二進位的「判決」。對於每個判決，前後關係模塊108(1)還輸出一個上下文箱識別符。
前後關係模塊108(1)還連接到存儲器114(1)去尋址其中的數據單元和相對於在輸入碼流中出現的符號向該單元讀/寫數據，按照需要確定出現在其輸入端上的輸入象素碼流的前後關係。在存儲器114(1)中具體的數據單元布局取決於前後關係的模式。
PEM 110(1)接收來自前後關係模塊108 (1)的兩個輸入和具有到比特發生器112(1)的兩個輸出一個概率級別(Pclass)輸出，和一個結果輸出。PEM 110(1)也連接到存儲器116(1)，去尋址其中的數據單元和讀出和修改這些數據單元的值，和連接到比特發生器112(1)，接收一個表更新信號。對於每個到PEM 110(1)的判決輸入，PEM110(1)輸出一個結果比特和一個Pclass。結果比特取決於判決輸入比特和與該判決輸入比特相關的前後關係箱的最可能的比特符號(MPS)。結果比特指示是否該判決輸入比特是或不是MPS。MPS的反是最低可能性符號(LPS)(該MPS是0或1，因為比特發生器編碼二進位符號)。
比特發生器112(1)接收結果比特碼流和其相關的Pclass。因此，比特發生器112(1)接收對於每個輸入到前後關係模塊108(1)的象素符號的K個結果比特和相關的Pclass。從這兩個輸入碼流中，比特發生器112(1)產生壓縮的碼字的碼流，正如在ABS編碼器基準中所解釋的那樣。利用適當設計的比特發生器，可以從輸出的碼字恢復結果比特碼流，和該碼字包括1，於輸入比特碼流的比特。Plass值用於選擇一種碼，用於編碼該比特碼流。另一方面，PEM 110(1)可能為每個前後關係存儲MPS和LPS的概率分布和提供概率給比特發生器。
正如ABS編碼器基準所教導的，在輸入碼流中一些二進位碼可以被優化為特定的符號(「0」或「1」)的概率。例如，在比特發生器的輸入端如果「0」和「1」近似相等，則優化碼是未壓縮的碼，即對於每個比特輸入一比特輸出。一個碼的優化是利用多麼接近輸入比特的理論熵的平均碼字長度確定的。
因為壓縮由102每次按一個象素符號操作的和PEM 110和比特發生器112每次按該象素的一個比特操作的，所以「當前」象素和「當前」比特的概念具有含義，和被用於下面解釋壓縮器102和解壓縮器106的操作的描述中。然而，應當理解為，在一個複雜的壓縮器中，各符號可能不按每次一個操作，但是「當前」符號的概念仍然是可用的。還應當理解為，單元可以工作在一種管道方式，以致於對於一級的當前符號可能不同於另一級的當前符號。
在壓縮操作中，壓縮器102按次序接收每個輸入象素符號和輸出碼字的碼流，雖然不需要對固定數目的輸入符號輸出一個碼字。在進行處理一個象素符號中，該符號被二進位化和該二進位化輸出到前後關係模塊108(1)。前後關係模塊108(1)以比特狀態為基礎估算該二進位化量，在該模塊的判決輸出與識別該比特的前後關係的前後關係箱識別符一起輸出每個比特。例如，如果所用前後關係模式是比特位置前後關係模式，則該前後關係箱識別符僅指示在該輸入象素符號的二進位化量中的該比特的位置。對於比特位置前後關係而言，僅僅指向當前比特的指示符需要存儲，但對於其他前後關係模式影響其他象素上下文的每個象素要被存儲在存儲器114中。如果前後關係模式包括上面當前象素的象素，則應當在存儲器114中足夠存儲一行象素。
在構成一個圖象的兩維象素矩陣中輸出符號代表象素顏色的情況，掃描的次序不像對於正文的數據塊那樣重要，其中前後關係通常是由一個接正當前字母的字母提供的。然而僅僅作為一個例子，這種討論是假設該兩維矩陣是以一種預定次序掃描進入壓縮器102的，例如從頂行到底行，和在每行中從左向右。利用這種掃描次序，上面當前的象素可被用作前後關係，因為上面象素到需要為當前象素提供上下文時將已然被解碼，和因為，在典型的圖象中，當前象素直接上面的象素常常是其顏色與該當前象素相類似。
對於前後關係象素是上面當前象素的象素是無關緊要的，和在許多前後關係模式都是可能的情況下，從剛剛被壓縮的數據流中成功的低耗損解壓縮要求當前比特的前後關係模式不包括在該當前比將要被解碼時尚未被解碼的比特和符號。幾個例子將會清楚地說明這一點。
如果前後關係模式是一個「比特位置」前後關係，當前比特的前後關係是在當前輸入象素中的比特位置，和對於該前後關係的前後關係識別符將代表該當前前後關係，在K比特二進位化的符號的情況下，提供K個上下文。然而，如果該當前比特的前後關係確定所用的碼去解碼該比特，則該比特能夠被正確解碼之前就需要知道該前後關係。因此，處理的次序應當保證該比特被解碼之前就要知道當前比特的前後關係。
對於由前後關係模塊在其判決輸出中的每個比特輸出，PEM110(1)接收該判決和對於該判決的前後關係箱識別符。基於這種判決，對於該判決的前後關係箱的MPS，PEM 110(1)輸出一個結果比特和一個相關的Pclass。下面討論MPS和Pclass是如何被確定的。
Pclass是由前後關係模塊108(1)在判決信號線上對在比特碼流輸出中如何類似於MPS的估算。而通過掃描所有輸入數據，在輸入數據中的MPS和LPS的概率分布是可能確定的，壓縮將不取決於整個概率分布，因為在對碼字解碼之前該分布對於解壓縮器是允用的。因此，僅取決於以前被編碼的比特的估算被利用。正如在ABS編碼器參考資料所解釋的那樣，比特發生器112(1)利用Pclass確定哪種碼用於編碼結果比特碼流。因為一個碼在整個概率分布範圍內是優化的，Pclass確定一個概率值的範圍，並因此確定相應概率級別。這些概率級別每一前後關係的一個被存儲在存儲器116中。存儲器116還為每個前後關係存儲MPS。圖4表示存儲器116的布局。開始，每個前後關係的Pclass是指示50％MPS的概率的Pclass(且是LPS50％的Pclass)；而且MPS可以從0和1中任選。
正如ABS編碼器基準教導的那樣，在熵編碼器中的一種壓縮數據的方法是種用一種將MPS的遊程長度減至表示該遊程長度的一個碼字。原來的碼流通過由該碼字指示的多個MPS比特的輸出，接著LPS予以重建，除了MPS比特的遊程長於被斷開為多於一個碼字的最大遊程。
在一個碼字輸出之後，比特發生器112(1)通知PEM110(1)是否發生MPS比特的最大遊程。這種指示是在表更新信號線上提供的。如果遇到最大遊程長度，比特發生器112(1)通知PEM110(1)更新Pclass表，指示該MPS比的估算的更近似。如果未遇到最大遊程，Pclass被改變，指示該MPS不如以前估算的近似。
解壓縮恰恰是壓縮的逆過程各碼字被解碼為結果比特碼流，輸出比特碼流被變換為判決比特碼流，和被裝配為象素符號，而後輸出。參照圖3，解壓縮器106包括前後關係模塊108(2)、PEM110(2)、比特發生器112(2)、存儲器114(2)和存儲器116(2)。在解壓縮器106(2)中各模塊的互聯對於比特碼流而言是壓縮器102相反的，但是對於關於比特流的信息來說是相同的方向，因此形成兩個反饋環。
一個反饋環確定用於編碼一個碼字的碼。知道所用的碼使比特發生器112(2)解碼該比特流。所用的碼是由PEM110(2)提供的Pclass確定的。如同PEM110(1)一樣，Pclass是由前後關係和在表更新線上的信號確定的。前後關係是由關於以前比特的信息和存儲在存儲器114(2)中的象素確定的。反饋環具有可以由若干比特來度量的某些延遲。該延遲可以取決於接收的碼字而改變，和對於多數實施例，該延遲可以被限制在一個最大值。如果該延遲最大值是X比特，則當前比特的前後關係將不取決於該X比特，該X比特在判決比特流中領先於該當前比特。這保證當前比特能夠被已經由解壓縮器106處理過的信息解碼。這種要求存在一些具體問題，這些問題為本發明所解決，其中數據需要的並行方式被壓縮。
變換如上所述，二進位熵編碼器能壓縮數據高達理論上的限制。任何二進位化的調色數據能夠與其他形式圖象一樣容易地被用於顯示，然而，結果是一些二進位量對於一些前後關係模式提供了比其他的低的熵。這種優點可以通過在壓縮口102的前端附加一個變換器提供的，其中該變換器選擇一種二進位量，為要被壓縮的數據提供低的熵。變換器的相反物，即解變換器可以被置於解壓縮器106的輸出端，或由於變換造成符號集空間的變化可以改善顏色調色的清晰度。在一些實施例中，變換表甚至可能是在壓縮之前被固定和存儲在壓縮器和解壓縮器中。
圖5表示一個變換的數據壓縮系統158，該系統包括連接到壓縮器102的輸入端的變換器160，為2XM表的變換表162，和可選擇的去變換器1640信號線166表示指示變換表到解壓縮器106的轉移，如果變換不是固定的話。因為變換表162僅為2XM，隨著被壓縮的數據傳送它不會引入過多的附加信息。
變換器160和去變換器164的操作直接給出一個具體的變換表162。變換器160利用來自其輸入端的象素符號檢索表162，和讀出相應的變換值。該值作為輸入前後關係壓縮器102的二進位化符號被輸出。在表162中的變換值是如此可逆操作的，即，在變換表162的一個入口精確地保持任何已知的變換值。因此，當解壓縮器106的輸出被施加到去變換器164，該輸出帶有該壓縮系統的延遲是與壓縮器的輸入一樣的，如果利用變換，則去變換器164執行相反的變換和輸出會有原有M矩陣象素符號的變址。如上所述，如果實際上不需要原來的M-陣象素符號，可以利用知道的二進位化的量，則不需要解變換器164。
圖6是變換表發生器200的框圖，該發生器用於從輸入數據塊中生成在表162中的各變換值。發生器200可以由專用硬體實現，或者由適當編程的數字計算機實現。利用通用數字計算機常常是低成本的，特別對於非實時壓縮，雖然比專用硬體顯得慢一些。幸運地是，多數應用允許壓縮在先進行，並非實時的。
到發生器200輸入是象素符號的數據塊。這具數據塊可以是要壓縮的整個圖象或一些圖象取樣的子集，或甚至圖象的一部分。然而，其中的壓縮可以用非實時方式進行，一般對於利用整個數據集作為到發生器200的輸入來說是不成問題的。在一些實施例中，圖象數據是分組為16或256個圖象的數據塊，和對於每個圖象數據塊產生變換表。
再參照圖6，發生器200包括一個次序固定模塊204、有條件概率分布累加器206用於保持對於(i∶o到M-1和c∶o到N-1)的Pc(Si)值的有條件概率表208，Pc(Si)是在前後關係Cc中出現的輸入符號Si的概率，用於保持對於(c∶o到N-1)的Pc(Cc)值的前後關係概率表209，Pc(Cc)是出現在輸入數據塊中前後關係Cc的概率，連接輸出到變換表162的期望熵趨於最小裝置，用於保持對於(c∶o到N-1)的PCP(c)值的部分有條件概率表212(「PCP表」)PCP(c)是正如下在解釋的前後關係Cc的部分有條件概率，用於保持對於(k∶1到k和c∶o到N-1)的PPCP(k.c)值的部分位置概率表212(「PPCP」表)PPCP(c)正如下面解釋的那樣是前後關係Cc和比特位置k的部分位置有條件概率和正如下面解釋的那樣用於保持對於(j∶1到M-1)的PBE(j)值的部分比特狀態熵表216。在伴隨圖7的流程圖閱讀描述以後各種表的使用將變得更為明顯。
發生器200按以下方式操作，次序固定模塊204變換來自數據塊202的每個符號為一個排序符號Si，(其中i∶o到M-1)。因為變換表162的作用是重新排序各符號，特定的所用次序對於系統的其餘操作而言是不重要的。在一種可能的實施例中，在數據塊202中的各符號已經作為k比特二進位值(k≥log2M)被存儲，在這種情況下模塊204是不需要的。在另外的實施中，So分配給數據塊202中最繁頻的象素符號，S1分配給次最頻繁的符號，以此類推，SM-1給最不頻繁的符號。存在有時稱為第零序的、或無前後關係的符號頻度分布。
如果利用模塊204，從數據塊202中讀出象素符號和傳送排序的符號的二進位表示到累加器206，累加器累加到表208和209的概率。熵最小裝置210而後讀出表208和209的內容，從中讀出各值和寫這些值到表212、214和216中，以便產生其主輸出，該輸出變換為表162的內容。在一些實施例中，趨於最小裝置210保持表162的變址分配的內部表，和在其他實施例中，趨於最小裝置210確定哪些變址是查表162指定的。
變換表發生器200的操作最好結合圖6參照如圖7所示流程圖來理解。流程圖示出方框300、302、304、306、308、310、312、314、316、318、320、322、324、326和328。方框300表示從一個數據塊產生一個變換表過程的開始。在方框302和306中的步驟一般是由累加器206執行的，在方框304中的步驟是由模塊204執行的，而其餘一般是由熵趨於最小裝置210執行的。流程是從方框302到方框328按方框序號進行的，以方框328按所指示或者終結或者環路返回方框316。
在方框302中，累加器206清除表208和209。在方框304中，如果利用模塊204的話，排序輸入符號為So-SM-1，而在方框304中，累加器206填充表208和209。表填充以後，表208含有對於每個前後關係和一個輸入符號組合的入口，其中表208的入口(c.i)表示給定前後關係Cc出現的符號Si的概率。當被填充時，表209含有對於每個前後關係的一個入口，其中表209的入口c表示與符號無關的出現前後關係Cc的概率。對於i有M個可能的值，和前後關係是{Co、……CN-1}，給出N個可能的前後關係。因此，表208會有M×N個入口和表209含有M個入口。
在一個實施例中，在N＝M的情況下，前後關係是對於被取為Si的上面象素的象素的符號。在另外一些實施例中，前後關係是對於左邊(N＝M)象素的符號，或該前後關係是兩個符號(N＝M2)。然而，利用兩個符號的前後關係將對每個輸入符號要求M2個前後關係，和因此，表208和209對於M的最大值將是非常大的。在還有一些其他的實施例中，存在少於M個前後關係。例如，如果所有可能的符號被分組為小於M的值，和對於一個前後關係象素的前後關係是含有上面前後關係象素的象素的組，則將出現少於M的前後關係。例如，如果所有的符號被分組為每四個符號一組的各個組，N將為M/4。當然，對於這種減少前後關係將是有益的，某些分組符號的智能裝置將被利用。
在方框308中，趨於最小裝置210設置一個i→0的可變環，和初始化變換表162、PCP(c)表212和PPCP(k，c)表214。雖然方框308被表示在方框306之後，它們的次序可能是反的，因為沒有哪個步驟取決於其他步驟的結果。變換表162利用標識符或其他公知方式指示已被初始化，指示在表162中所有入口是空的和在其中未分配變址。通過對所有c設置PCP(c)＝0，PCP表被初始化，和通過對所有k和c設置PPCP(k.c)＝0，該PPCP表被初始化。
在方框310中，趨於最小裝置210分配變址0至So，和相應更新變換表。
在方框312中，通過對於每個c設置PCP(c)＝Pc(So)，趨於最小裝置210為增加的變址So更新PPCP(c)表。
在方框314中，趨於最小裝置210通過為個(c.k)對設置PPCP(k.c)＝Pc(So)，為增加的變址So更新PPCP(c)表，其中分配的變址的底數2表示的第k個比特是1。當首次分配的變址是0時，這個步驟是不需要的，因為沒有變址的各比特是1，但是在非零變址被首次分配時，這個步驟是需要的。
在方框316中，趨於最小裝置增加i，在首次通過方框316的情況下，結果為i＝1。方框316通過方框328的過程對於每個i在0和M-1之間重複，假設在變換表中的一個變址對應於每個環的一個符號，當然，在i＝M-1情況下的最後的環實際上不需要，因為僅僅在要分配給SM-1那個點上將保留一個變址。
在方框318，按照PCP(c)＝PCP(c)＋Pc(Si)，PCP表對於符號Si被更新。在該步驟以後，在符號集A′所接收的符號的已知前後關係Cc和符號集，A′＝{So，……Si}的概率是在PCP表的第c個入口的PCP(c)。
在方框320，對於每個未分配變址產生部分比特狀態熵(PBE)值。該未分配的變址(在這點上其號為M-i)在表162中被找到並在趨於最小裝置210內部記憶。對於已經被分配的給出指數0-i-1的指數j和符號Si的部分比特狀態熵PBE(j.Si)由方程1-3表示。PBE(j,Si)=CEC[P(Cc)k=1KH(PA,c,k,j,si)]---(1)]]>PA,c,k,j,si=[sA,bk(r(s))=Pc(s)]+bk(j)=Pc(Si)[sAPc(s)]+Pc(Si)---(2)]]>H(P)=-xpp(x)log2(x)---(3)]]>其中A′是i個已分配的符號的符號集，H(p)是概率分布P的熵，bk(x)是基數2的x表示的第k比特的值，和r(s)是對於符號s的變換值。
在方框322，趨於最小裝置210從所有計算的值中選擇PBE(j.Si)的最小值和設置等於該最小值的j的變量x。
在方框324，趨於最小裝置210為Si分配x作為該變換值和在表162中指示這種分配。
在方框326中，趨於最小裝置210按照對於所有c和所有k的PPCP(c.k)＝PPCP(c.k)＋Pc(Si)為Si和x更新PPCP(c.k)表，其中bk(x)＝1。在該步驟以後，對於給定的前後關係Cc和符號集A′＝{So、……Si}，該接收的符號的變換值的第k比特是1和接收的符號在該符號集A′中的概率是PPCP(c.k)。
在方框328中，趨於最小裝置210檢查是否兩個或多個變換值尚未被分配。這是這樣一種情況，即如果在這個數據塊中是M-2或更小，則意味著該M-1指數已被分配。最後的指數被分配給SM-1。
在方程2中的分母是PCP(c)，該PCP(c)通過在方框318中對每次增加到符號集A′中的符號Si加Pc(Si)而被更新。如果j是Si的指數，方程2的分子是PPCP(k.c)。因為被更新的PPCP(k.c)的值取決於指數j對Si的分配，在方框326中，在選擇x＝j以後，PPCP(k.c)被更新。當然，由於H是比特狀態熵的函數，因為P(0)＋P(1)＝1，方程2僅需對於β＝0，或β＝1而被計算。另外，因為H是一個比特狀態的熵，方程3實際上簡化為H(x)＝－X*log2x－(1-x)*log2(1-k)在圖7中表示的過程的最終結果是在變換表162中各個變換值的分配，該分配被變換器160用於將輸入的象素符號變換為一個二進位量，該二進位量通常產生比如果不進行變換時要好的壓縮。
上面各部分描述了通過自適應編碼、前後關係模式和變換是如何改善壓縮比的。在解壓縮器中，自適應編碼和前後關係模式要求反饋環，因為在該方法中對於來自一個碼字流的比特被解碼，取決於關於以前被解碼的比特和符號的信息。如果解壓縮器需要實時地快速解碼該碼字流，並行處理將可以用於提高更大的數據通過量。
一種這樣的並行處理實施方案如下所述。利用比特位置前後關係模式(見圖8(a))，在象素值中的每個比特由八個並行編碼器元之一處理，每個編碼器被專用於一個比特位置。利用這種安排，該比特的上下文對於一個編碼器是已知的，因為該比特位置是唯一的前後關係和對於該編碼器該比特位置是已知的，因為對於一個特定的編碼器來說，它是恆定的。但是，在利用其他前後關係模式提供更好的壓縮的情況下，並行的編碼器就不是這樣簡單。
例如，採取如圖8(c)所示的取決比特狀態前後關係模式。如果象素的每個比特被發送到一單獨的解碼器，則這些比特不能以並行被解碼，因為所提高的正在被解碼的比特必須首先提供該正在被解碼比特的前後關係才能被解碼。因此，一些前後關係模式的利用施加強制性的並行處理。
在本發明的一個方面，允許使用優選的前後關係模式和允許在利用那種前後關係模式下在編碼器中並行處理，提供了一種獨特的重新排序緩衝器。圖9和圖10表示一個重新排序緩衝器和其相反的一個去重新排序緩衝器是如何連接到並行編碼器的，和圖1l更為詳細地表示該重新排序緩衝器的操作。
給出一個優選的前後關係模式以後，施加到並行編碼器上有兩個強制性處理。第一，如果每級將是獨立的，則在一個並行周期中處理一組比特，這些比特都不會影響其他比特的前後關係。第二，如果該上下文數據在每個比特之後要被更新，在被並行處理的一組比特中設有兩個比特共享一個前後關係。圖12表示會有前後關係數據的前後關係記錄，該記錄可能當具有一個給定前後關係的比特被處理時而被復新。這個記錄可能是諸如圖4所示的存儲器116的一個表的一行。
在圖9中，表示出一個按照本發明的並行壓縮系統400，該系統具有重新排序緩衝器402、去復用器404、N個並行級406(0、……N-1)、復用器408和去排序緩衝器410。系統400可以利用或不利用變換。每級406包括類似於壓縮器102的壓縮器412、信道414、和類似於去壓縮器106的解壓縮器416。
圖10表示另外一種組態450，其中交叉器452用於將信道414(0、……N-1)的數據組合為一條單一信道454，和去交叉器456用於分離單一信道454的數據返回到每級的單獨信道。
再次參照圖9，輸入到系統400的符號流由重新排序緩衝器404緩衝。重新排序緩衝器404按照下面詳細解釋的接收每符號k(在圖8中，k＝8)比特的比特流，和輸出該比特到去復用器404，該去復用器分配被重新排序的比特到各並行編碼器。在第i個並行級中406(i)中，壓縮器412(i)將分配給406(i)的比特壓縮為碼字，該碼字不通過信道414(i)傳送，和由解壓縮器416(i)解壓縮。所有級的輸出而後由復用器408組合，復用器408的輸出共組合到去排序緩衝器410，該緩衝器執行重新排序緩衝404的相反操作。雖然如所示在並行編碼器中，每級分配一個單獨的前後關係，但可以按應用的需要，重新排序允許的其他方式分割各並行級的靈活性。例如，每級可以被分配一個Pclass、一組包括多個前後關係，或者在各個級中平均分配數據的特殊分割。
圖11(a)表示一種重新排序的緩衝器502，該緩衝器用於具有四個並行級的編碼器和取決於比特狀態的正下文模式，儘管這種緩衝器還可以用於其他的組態，諸如8個或N個並行級，每象素不同的比特數、或者不同的前後關係模式。四個輸入字節(如左邊所述的各象素被輸入到緩衝器502)和八個四比特數據塊表示為從緩衝器502輸出。輸出的數據塊每並行編碼因知一個地輸出到並行編碼器，因此每個輸出數據塊代表一組的並行處理的比特。如果輸入的各比特為未重新排序的情況，輸入到並行編碼器的數據塊恰好是象素A(A7-A4)的四個最高有效位，接著是象素A(A3-A0)的四個最低有效位，而後是象素B(B7-B4)的四個最高有效位，等等。正如從上面討論應當明確看出的，當取決於比特狀態的模式利用時，一組被並行處理的比特將不是獨立的，因為A4從其位置(4)得到其前後關係和比特A7、A6和A5的值是相同的比特組中的。
為解決這個問題，緩衝器502為象素A、B、C和D重新排序該輸入比特，正如所輸出的數據塊(以並行處理的各組比特)正如所輸出的數據塊9以並行處理的各組比特)D7-C7-B7-A7、D6-C6-B6-A6等等。利用這種重新排序，沒有一個比特對於前後關係在其組中依靠任何其他比特。但是，如果是兩個比特，仍然可以共享一個前後關係。例如，D7和C7在取決比特狀態前後關係模式中可能共享一個前後關係，取決於比特狀態的前後關係是該比特的位置以及該左邊的比特。對於D7和C7，該比特的位置是相同的，而且在其左邊沒有比特(圖11的上面)。
利用圖11(b)所示的重新排序緩衝器，該第二個限制與該第一個限制一起被解決了。在該緩衝器中，被分組為各數據塊的各個比特是從不同的象素中取出的，而且還是取自不同的比特位置。其中比特位置是前後關係的一部分，具有不同比特位置的比特將其有不同的上下文。因此，由緩衝器504輸出的各數據塊(並行處理的各比特組)，D7-C6-B5-A4、D6-C5-B4-A3等等一直到第九數據塊H7-G6-F5-E4，每個數據塊包括對於前後關係不取決於在它們的數據塊中的其他比特和不與在它們的數據塊中任何其他比特共享一個前後關係。沒有表示出輸入象素E、F、G和H，但示出接著的象素D。
在圖1l(b)中，沒有在象素A以前的各象素，說明該緩衝器的狀態接著復位。在緩衝器復位以後在第一個並行步驟中，僅具有一個比特的(來自象素A)的數據塊被處理。在下一個並行步驟中來自象素A的一個比特和來自象素B的一個比特被處理。然而各比特的交錯和前後關係衝突的避免意味著在一次復位以後不是所有並行的級將被用於前面的幾個數據塊，這種利用對於任何合理的圖象尺寸是重要的。在圖11(b)的情況中，僅出現在前面三個數據塊。
圖13(a)-(b)表示類似的對於施加到並行編碼器的限制，對於設置於管道編碼器的前後關係模式的限制。圖13(a)和(b)表示如圖11所示正在進行的象素A-D管道編碼器的過程，利用圖13(a)表示以未重新排序的次序的正在進行的比特的一種管道，而圖13(b)表示以重新排序的次序的當前的比特的一種管道。在本圖中，每一列標註時間t，和表示由一個管道級正在操作的比特。表示在這個例子中的各級是一個輸入級、三個中間級(IS-1、IS-2和IS-3)、和兩個輸出級。
在該例子中，假設一個比特經處理且用於在第一輸出級中確定其其比特的前後關係，但不是立即被利用。另外，假設IS-1的處理取決於正被處理的比特的前後關係，和正在利用取決比特狀態前後關係模式。利用取決比特狀態前後關係模式，劃圈的比特A2取決於A3、A4、A5、A6和A7。在圖13(a)中，這可能意味著，比特A2的處理不能繼續進行，至少直至比特A3和A4全都到達第一輸出級(比特A5-A7已經通過過第一輸出段)。這種延遲可能損害管道處理的益處。
為了解決這個問題，可以利用諸如緩衝器502這樣一個重新排序緩衝器，實現如圖13(b)的效果。在該例子中，從比特B7得到其上下文的劃圈的比特B6在一個早些時候被輸出到第一輸出級，且因此當B6在IS-1中要被處理時是可以利用的。
以上的描述是說明性的，而不是限制性的。對本專業的技術人員來說當閱讀了這份公開以後，本發明的許多變形將是顯而易見的。因此，本發明的範圍不同參照上述描述確定的，而應當是參照所附的權利要求書連同其各個等同物的所有範圍確定的。
權利要求
1.一種壓縮輸入符號的方法，其中每個輸入符號是從代表在調色圖象中的一個象素的M個符號的符號集中選擇的，轉變為由較少比特表示的碼字和來自該碼字的輸入符號可以被解碼，該方法包括以下步驟選擇一個前後關係模式；讀出輸入符號的M陣的輸入碼流；利用在上述輸入碼流期間所述前後關係模式的指示確定一個上下文分布；在所述輸入碼流期間的所述前後關係中確定所述M陣輸入符號的分布；分配一個第一二進位序列到該符號集中的M個符號的一個第一符號，其中所述二進位序列是k比特，k是一個大於或等於log2M的整數；分配後續的各二進位序更到該符號集中M個符號的各後續的符號，其中該後續的二進位序列是從所有未分配的二進位序列中選擇的二進位序列，這在該符號集中已被分配二進位序列和選擇二進位序列的部分符號集期間產生最小部分比特狀態熵，從而形成用於變換任何M陣符號到其賦予的二進位化量的變換表；重複所述分配後續的二進位序列的步驟，至少直至M-1個二進位序列被分配給各個符號；分配剩餘二進位序列到剩餘的符號，因此完成所述變換表；利用所述變換表對每個M陣輸入符號進行二進位化形成一個比特流；和對所述比特流進行熵編碼形成在被壓縮的碼字流中的碼字。
2.權利要求1的方法，其中所述部分比特狀態熵是在所有前後關係和所有k比特二進位序列位置期間的部分比特熵的和，其中部分比特熵是一個部分位置有條件概率與一個部分有條件概率之比的熵。
3.權利要求1的方法，還包括傳送所述被壓縮的碼字流和所述變換表到一個解壓縮器的步驟。
4.權利要求3的方法，還包括在恢復作為被解碼比特流的所述比特流的傳送以後，解壓縮被壓縮的碼字流的步驟。
5.權利要求4的方法，還包括用所述變換表的反方向變換所述被解碼的比特流的步驟。
6.權利要求的方法，還包括以下步驟傳送所述被壓縮的碼字流到解壓縮器；在恢復作為被解碼比特流的所述比特流的傳送以後解壓縮所述被壓縮的碼字流；和按照從以前被變換的所述被解碼的比特流的各部分得到的上下文模式變換所述被解碼的比特流。
7.權利要求1的方法，其中所述前後關係模式是一種比特位置上下文模式，其中一個比特的前後關係是由所述比特在其二進位量中的位置確定的。
8.權利要求1的方法，其中所述前後關係模式是一種比特平面上下文模式，其中一個比特的前後關係是由所述的比特在其二進位量中的位置的一個前後關係符號確定的。
9.權利要求1的方法，其中所述前後關係模式是一種取決比特狀態的前後關係模式，其中一個比特的前後關係，(如果有的話)是由所述比特的二進位時的以前被處理的各比特確定的。
10.權利要求1的方法，其中所前後關係模式是一種取決第一馬爾克夫比特狀態前後關係模式，其中一個比特的前後關係(如果有的話)是由所述比特的二進位量和一個前後關係符號確定的。
11.權利要求1的方法，其中所述前後關係模式是一種混合的上下文模式，其中一個比特的前後關係(如果有的話)是由所述比特的二進位量的以前已處理過的各比特和一個前後關係符號的二進位量的比特確定的。
12.一種壓縮輸入符號的方法，其中每個輸入符號是從代表在調色圖象中的一個象素的M個符號的符號集中選擇的，轉變為較少比特表示的碼字和來自該碼字的輸入符號可以被解碼，該方法包括以下步驟讀出輸入符號的M陣的輸入碼流；二進位化所述M陣輸入符號為一個二進位的符號碼流；對每個二進位符號的每個比特識別一個前後關係，其中對於所述每個比特的一個前後關係是由所述每個比特在所述每個二進位化的符號中的位置和一個前後關係符號確定的，該前後關係符號不同於所述每個二進位的符號並與所術每個二進位化的符號有一種預先確定的關係，所述預定關係是這樣的，即當解碼時，所述每個二進位化符號在所述前後關係符號的後被解碼；對於所述前後關係確定一個二進位熵碼；按照從所述碼流的所述每個比特的前後關係和所述碼流的所述每個比特的值確定的所述二進位熵碼對所述二進位化符號的碼流的每個比特進行編碼。
13.一種壓縮輸入符號的方法，其中每個輸入符號是從代表在調色象素中的一個象素的M個符號的符號集中選擇的，轉變為由較少比特表示的碼字和來自該碼字的輸入符號可以被解碼，該方法包括以下步驟讀出M陣輸入符號的輸入碼流；二進位化所述M陣輸入符號為二進位化的符號的碼流；識別每個二進位化的符號的每個二進位比特的一個前後關係，其中所述每個比特的前後關係是由所述每個比特在所述每二進位化符號中的位置和一個前後關係符號的二進位化的各比特確定的，所述上下文符號是在以對所述每個二進位符號的預定關係上不同於所述每個二進位化符號的一個符號，所述預定關係是這樣的，當解碼時，所述每個二進位化的符號在所述前後關係符號以後被解碼；對所述各前後關係確定一個二進位熵碼；按照由所述碼流的所述每個比特和前後關係和所述碼流的所述每個比特的值所確定的所述二進位熵碼對所述二進位化的符號的碼流的每個比特進行編碼。
14.一種用於壓縮M陣的符號的壓縮設備，每個符號代表在一種調色圖象的一個象素值和從一個M個符號的符號集中選擇出來，轉變為以較少比特表示的一些碼字和從這些碼字中可以提取該M陣符號，該壓縮裝置包括用於確定在所述輸入碼流中各符號分布的裝置；為M個可能的符號的每一個確定二進位量的變換表發生器，所述二進位化量是依據該M陣符的分布，其中所述二進位化量是由一個變換表表示的；用於按照所述變換表將每個M陣符號的二進位化量轉變為一個二進位序列的變換裝置，因此變換代表調色圖象的M陣符號為一個二進位比特流；壓縮所述二進位比特流和輸出一個產生的碼字流的二進位熵編碼壓縮器；其中所述二進位化量是從該二進位化輸入碼流的最小的比特狀態熵中選擇的。
15.權利要求14的壓縮設備，其中所述二進量產生在所有可能的二進位化量以外的局部最小值。
16.權利要求14的壓縮設備，其中所述二進位序列是一個k比特的固定長度，其中k是大於或等於log2M。
17.權利要求14的壓縮設備，其中所述二進位熵編碼壓縮器包括一個前後關係模塊，一個概率估算模塊、和一個比特發生器。
18.一種熵編碼器，其中輸入符號是根據由前後關係符號提供的上下文編碼的，該輸入符號還是一些輸入符號，包括符號重新排序裝置，連接到該熵編碼器的符號輸入端，用於將來自輸入碼流次序重新排序輸入符號為重新排序碼流次序；前後關係模塊，連接到所述符號重新排序裝置的輸出端，該模塊接收按所述重新排序的碼流次序的輸入符號和存儲輸入的符號，按照需要從所述當前輸入符號的前後關係符號確定當前輸入符號的前後關係；概率估算器，連接去接收來自所述前後關係模塊的所述當前輸入符號和所述當前輸入符號的前後關係，用於估算給定其前後關系所述當前輸入符號出現的概率；和比特發生器，連接到所述概率估算器，用於基於由所述概率估算器提供的概率估算產生碼字，所述碼字是所述輸入符號的重新排序的碼流一種被壓縮的表示；其中所述符號重新排序裝置重新排序輸入符號以致於使在所述重新排序碼流中所述當前輸入符號與所述當前輸入符號的前後關係符號之間的被重新排序的距離大於在所述輸入碼流中所述當前輸入符號與所述當前輸入符號的前後關係符號之間原來距離。
19.權利要求18的設備，還包括一個解碼器，所述解碼器包括第二前後關係模塊，該模塊存儲被解碼的輸入符號，按照需要確定當前輸入符號的前後關係；第二概率估算器，連接去從所述第二前後關係模塊接收所述當前輸入符號的前後關係；第二比特發生器，連接去接收由所述比特發生器輸出的所述碼字，用於根據由所述第二概率估算器提供的概率估算從所述碼字中產生符號碼流；符號重新排序裝置，連接到所述第二前後關係模塊的符號輸出，用於從所述重新排序的碼流次序到所述輸入碼流次序重新排序被解碼的輸碼流，因此增加所述被解碼的前後關係符號與所述被解碼的當前輸入符號之間的延遲。
20.權利要求19的設備，還包括一個用於並行解碼所述碼字的裝置，其中所述增加的延遲；在按照所述解碼器的需要提供前後關係符號的同時，足以允許進行並行解碼。
21.一種熵編碼器，其取自輸入比特碼流的多個比特被並行編碼，包括前後關係模塊，該模塊接收一個輸入比特和輸出與所述輸入比特成對的與所述輸入比特相關的一個前後關係，所述前後關係由至少一個以前的輸入比特、所述輸入比特在各輸入符號中的位置和一種預定的前後關係模式所確定；前後關係敏感並行編碼器，連接去接收來自所述前後關係模塊的成對的輸出，該編碼器根據給定的所述成對的前後關係輸入比特的概率估算產生碼字，所述碼字是所述輸入比特碼流的被壓縮的表示，所述並行編碼器包括用於形成輸入比特的並行碼流，分組N個比特為一組比特的裝置；和多個N編碼級，每級處理來自這樣被分組的比特組的一個輸入比特；和比特重新排序裝置，連接在用於比特碼流的輸入端與所述上下文模塊之間，用於如此重新排序輸入比特，即在一組比特中的一個比特獨立於在所述一組比特中的其他各比特。
22.權利要求21的熵編碼器，其中所述比特重新排序裝置還如此排序所述輸入比特碼流，即沒有在一組比特中的兩個比特共享一個公共前後關係並行被處理。
23.一種熵編碼器，其中從輸入比特碼流中提取多個比特左級管道中被編碼，包括前後關係模塊，該模塊接收一個輸入比特和輸出與所述輸入比特成對的所述輸入比特的一個相關的前後關係，所述前後關係是由至少一個以前的輸入比特、所述輸入比特的在輸入符號中的位置和一種預定的前後關係模式確定的；前後關係敏感的管道編碼器，被連接為接收來自所述前後關係模塊的成對的輸出，該編碼器根據給定的成對的前後關係的輸入比特的概率估算產生碼字，所述碼字是所述輸入比特碼流的一種被壓縮的代表，和所述管道編碼器包括一個輸入級，該級處理由所述前後關係模塊輸出的輸入比特；多個中間級，這些級處理所述輸入級的輸出，每級以一種管道方式連接到其它級，其中至少一級是前後關係敏感級，該級根據所述輸入比特的成對的前後關係處理輸入比特；和所述多個中間級的最後級的輸出端；和比特重新排序裝置，連接在用於輸入比特碼流的輸入端與所述前後關係模塊之間，用於如此重新排序各輸入比特，即，當所述給定比特在所述前後關係敏感級中被進行處理時，該給定比特的前後關係獨立於在所述多個中間級被進行處理的其它比特。
24.權利要求23的熵編碼器，其中所述比特重新排序裝置還如此排序所述輸入比特流，即在任何給定時間在管道中沒有兩個比特共享一個公共的前後關係。
全文摘要
本發明提供一種用於調色圖象壓縮的改進方法和設備。在M陣符號集中的輸入符號根據輸入數據的前後關係模式被二進位化，其中二進位化被選擇，由二進位編碼器提供良好的壓縮。具體的二進位化是由映射每個輸入符號為多個二進位值的一個變換表確定的。該映射是由要被壓縮的圖象確定的，和一般作為附加信息隨被壓縮的圖象傳送。該映射是二進位化量的比特狀態熵的局部最小值。
文檔編號H03M7/42GK1117222SQ9510273
公開日1996年2月21日 申請日期1995年2月22日 優先權日1994年2月23日
發明者A·曾迪, D·G·施託克, J·艾倫 申請人:株式會社理光