利用子波的視頻壓縮方案的製作方法

2023-05-13 06:35:06

專利名稱：利用子波的視頻壓縮方案的製作方法
技術領域：
本發明涉及視頻壓縮裝置和方法，特別涉及用於以數字格式大幅度壓縮視頻圖像信息而不大幅度降低圖像品質並同時提供實際恆定的數據輸出率的一種裝置和方法。
背景技術：
視頻圖像由多個一般稱為像素的獨立圖像元素構成，視頻圖像的像素是微小的彩色和/或黑白點，它們緊密地位於電子顯示器上以便當從遠處觀看像素集合時它們實際難以區分而是顯現為一幅圖像。例如，高解析度NTSC(全國電視系統委員會)幀由成千上萬的像素構成。形成一個NTSC視頻幀的像素可以由二進位數據值來表示，這些二進位數據值以數字形式規定了圖像的亮度(luma)(Y)、紅色度(Cr)和藍色度(Cb)的含量。高解析度NTSC視頻幀對於這樣的圖像的亮度含量一般包括720×480位元組的數字數據。每個NTSC幀的紅色度和藍色度含量包含360×480位元組的數據。以30幀/每秒(fps)的幀頻無線發送的實時NTSC視頻信號要求大量(約166兆比特/秒)的數據在發射機和接收機之間傳輸。
眾所周知，最好壓縮視頻數據以便使發送視頻數據所需要的帶寬最小。這一般通過處理具有極少或沒有被傳輸的一幅或多幅圖像的可感知內容的數據來實現。有一類用於壓縮視頻數據的方法包含使用子波變換。例如，授予Shapiro的美國專利第5,315,670、5,412,741、5,321,776、5,315,670和5,563,960號說明了基於子波變換的視頻壓縮的各種技術。簡而言之，表現為子波係數的視頻數據的子波變換提供了用於基於從視頻像素信息向保持頻率和空間特性的子波域的變換而編碼和解碼視頻圖像的方法。另外，Shapiro認識到提供了嵌入流作為輸出的壓縮方案的益處。嵌入流在流的開始處包含所有的低數據率。即，在壓縮方案壓縮數據時，首先輸出包含最主要和最重要信息內容的數據。在壓縮繼續時，另外的信息內容被添加到輸出流，進一步優化了被壓縮的視頻數據的整體品質。這使得當達到用於輸出流的任何目標數據率的時候壓縮編碼器停止編碼，因此使得可以得到恆定的輸出數據率。類似地，解壓縮輸出流的壓縮解碼器可以在任何點停止解碼，導致產生具有本應以被截短的流的數據率產生的品質的一幅圖像。嵌入流的這些性質可以簡化整個系統設計。
雖然Shapiro(見上)等已經公開了用於壓縮視頻數據的子波變換技術，許多這些現有技術未著重於視頻傳輸速度。而是，許多現有技術著重於再現的精確性，並且所有的這些現有技術因計算複雜而要求大量的處理能力。作為結果，這些現有技術壓縮方案一般不適用於用在消費品上，消費品的成本必須儘可能地低。能夠經濟地用在消費方面的計算效率高的視頻壓縮技術將是對現有技術的一個改進。而且，這樣的技術應當提供嵌入流的輸出。

發明內容
一般來說，本發明提供了一種計算簡單的技術，用於提供壓縮的視頻數據作為嵌入流。這是通過分級地識別可以邏輯地減小到高度緊密的(highlycompact)表示形式的數據塊來實現的。在本發明的一個實施例中，數據元素被邏輯地分到塊中。每個塊以按位的方式被檢查以判定是否該塊的數據元素可以以高度緊密的形式來表示。如果肯定，那麼在給定的位位置輸出整個塊的單比特表示。如果給定塊不可以以這種方式表示，則將其再分為更小尺寸的塊。這一識別合適的塊和再分的處理根據需要遞歸地重複直到達到最小的塊尺寸。
在本發明的另一個實施例中，經由通過重複對來自低級的表的單獨的數據元素進行邏輯「或」運算而形成縮小的數據元素的表來構建多個升序表。以這種方式，連續的高級的表是大數據元素塊的表示。遞歸地從最高級的表遞減並以按位的方式，遍歷多個升序表；基於縮小的數據元素，可以接受高度緊密形式的數據塊被識別。
本發明有益地利用了子波變換來提供可以按照本發明有利地壓縮的視頻數據。在初始像素調整後，計算子波係數並將其表示為多位二進位值。在本發明的一個實施例中，子波係數被表示為符號量值形式。子波係數被存儲在兩維的矩陣中並由它們表示的圖像的頻率分量來分級地集中在一起。如此處所公開的，子波係數隨後被作為輸入提供到壓縮處理。
與其他現有技術系統形成對比，這裡公開的和要求權利的本發明提供了計算效率高的手段，通過它視頻數據可以被高度壓縮而沒有不可接受的圖像降級，同時提供了嵌入的輸出流的益處。而且，雖然本發明針對其在視頻數據上的應用而特別說明，這裡教授的原理可以有益地應用到多種形式的數據。


圖1是按照本發明的無線視頻傳輸系統的框圖；圖2是按照本發明的用於壓縮視頻數據的裝置的框圖；圖3是按照本發明的用於解壓視頻數據的裝置的框圖；圖4圖解了按照本發明的多級子帶分解；圖5圖解了按照本發明的數據表示格式；圖6是圖解按照本發明的用於提供壓縮的視頻數據的第一方法的流程圖；圖7圖解了按照圖6的方法分析的示意性視頻數據；圖8是圖解按照本發明的用於提供解壓的視頻數據的第一方法的流程圖；圖9是圖解按照本發明的用於構建升序表的方法的流程圖；圖10A-10C圖解了按照圖9的方法構建的升序表；圖11是圖解按照本發明的用於提供壓縮的視頻數據的第二方法的流程圖；圖12是圖解按照本發明的用於提供解壓縮的視頻數據的第二方法的流程圖。
具體實施例方式
本發明可以參照圖1-12更全面地說明。
圖1示出了包括視頻發送機101和視頻接收機103的無線視頻系統100的框圖。視頻發送機101包括一個攝像機或其他圖像傳感器104，它提供代表由圖像傳感器104捕獲的圖像——例如由標號102所示的目標——的視頻信號106。視頻信號106可以包括數字或模擬信號，這是設計的選擇問題。在一個優選實施例中，視頻信號106包括以每秒30幀產生的NTSC視頻信號，但是也可以採用其他的幀頻。而且，如果其他視頻信號格式能夠被轉換為基於幀的、基於像素的格式，則可以使用其他視頻信號格式。
視頻圖像傳感器104向視頻處理器200傳輸視頻信號106，它隨後利用下面說明的技術變換和壓縮視頻信號106。所變換和壓縮的信息(被壓縮的視頻)110被提供給無線發送機112，它將被壓縮的視頻110調製到無線載波115上以通過天線114發送。所使用的無線載波或調製的具體形式對本發明來說並不重要。也要看到本發明不限定於無線系統。實際上，由載波115和相關的無線發送機112和無線接收機118產生的無線路徑可以被有線路徑或甚至無線和有線傳輸元件的組合來替換，如現有技術所公知。
視頻接收機103包括檢測和解調從天線116接收的無線載波115的無線接收機118。該無線接收機118解調無線載波115並由此產生接收的壓縮視頻120。接收的壓縮視頻120被視頻解壓器300處理以產生接收的視頻信號124。所接收的視頻信號124隨後被用來提供視頻圖像128用於在諸如電視或計算機監視器的顯示器126上顯示。所顯示的圖像128是由攝像傳感元件104檢測的目標102的的圖像的複製品。下面特別參照圖2和3進一步詳細討論視頻壓縮器200和視頻解壓器300。
圖2是圖1所示的視頻壓縮器200的框圖。雖然實際上任何適當快的微處理器可以作為視頻壓縮器200而起作用，本領域的技術人員應當理解大多數數位訊號處理器(DSP)在諸如子波變換計算的複雜運算中固有地優於通用微處理器。而且，可以期望利用可編程邏輯陣列或其他類似的硬體實施例來實現視頻壓縮器200。
最好是YCrCb像素形式的視頻信號202被作為輸入施加到離散子波變換204塊。在一個優選實施例中，視頻信號在施加到子波變換204之前被調整(未在圖2中示出)。例如，為了減少在視頻圖像中要處理的數據量，在抗混淆(anti-alias)濾波(被稱為抽取的處理)後，視頻圖像的每隔一個像素被丟棄。在接收機，在重建每隔一個像素時，被丟棄的插入像素通過利用保留的像素內插被丟棄像素的值而重建。一旦在水平和垂直平面上原始圖像的像素被抽取，來自保留像素的圖像信息內容被劃分成亮度、紅色度和藍色度分量，產生不同的三套像素。在這樣的實施例中，到子波變換204的輸入包括360×240位元組的亮度信息和針對所述每個色度圖像的180×120位元組。
子波變換204針對所有三種信號圖像而計算，即，亮度和紅色度和藍色度，導致三套子波係數的計算。離散子波變換的計算在本領域內是一般公知的。在一個優選實施例中，子波變換204執行下面的步驟
1.視頻信號數據被「像素擴展」以提高圖像數據的大小以便簡化在子波變換過程中發生的數據劃分。例如，360×240位元組的亮度數據被擴展成384×256位元組。
2.每個圖像在Y維上通過子波濾波器，分割圖像為低通區域和高通區域。
3.這些區域隨後在X維上通過子波濾波器，進一步分割這些區域為低通和高通區域，有效地產生四個區域。
4.在X和Y維上被低通濾波的那個區域再次按照(1)至(3)被處理，因此將此區域劃分成四個新的區域。
5.此處理被重複直到已經產生6級亮度信息和產生各自5級的紅色度和藍色度信息。當然，對亮度和/或色度信息也可能產生更大或更小的數量的級。
上述子波變換的整體效果是如圖4所示的多級子帶分解。存儲在輸入存儲區206中的數據包括子波濾波的亮度塊404、子波濾波的藍色度塊406和子波濾波的紅色度塊408。沿著圖4的垂直軸和水平軸顯示的尺寸僅僅是示意性的，其他的尺寸也可以被使用，這是設計選擇的問題。而且，雖然輸入存儲區206以兩維來表示以幫助理解，但是在實際中它包括一個存儲在存儲器中的表，此為現有技術所公知。每個塊404、406、408包括原始圖像的各種分量的空間頻率內容的多級的子帶分解。表示最低頻率的子帶被存儲在每個塊的左上角中，表示最高頻率的子帶被存儲在每個塊的右下角塊中。如現有技術所公知的，給出的圖像的大多數信息內容被包含在低頻(如平滑過渡區和/或連續顏色區)中，但是高頻數據(在目標之間的分界的銳邊)有助於在圖像中找到的更精細的細節。作為結果，那些存儲在低頻塊中的係數趨向於具有最高的值。例如，在亮度塊404最左上角的由標號412表示的子帶表示被變換圖像的最低頻率內容。相反地，在亮度塊404最右下角的由標號410表示的子帶表示被變換圖像的最高頻率內容。在本發明中所示的多級子帶分解的分級特性被支持使用，因為它對於產生嵌入流很有用。
再次參見圖2，子波變換204產生子波係數並如上所述將它們存儲在輸入存儲區206中。一旦存儲了子波係數，升序/降序鍵(ascending/descending key，ADK)壓縮器208可以開始壓縮處理以便提供被壓縮的數據212。在實際中，由收髮帶有各自功能的控制信號216、218的控制功能214來監控子波變換204和ADK壓縮器208處理的排序。在一個優選實施例中，控制功能214保持在逐幀的基礎上處理。例如，當子波濾波器204已經完成了視頻數據202(一幀)的處理並在輸入存儲區206中產生了新的子波係數的時候，它通知控制功能214。作為響應，控制功能214通知ADK壓縮器208它能夠開始處理新存儲的子波係數。期望控制功能214也可以向ADK壓縮器208提供用於通知ADK壓縮器208它應當在逐幀的基礎上輸出多少數據的幀大小數據，下面將進一步詳細說明。一旦ADK壓縮器208已經完成了其處理，它通知控制功能214，控制功能214隨後通知子波濾波器204它可以開始處理一個新的視頻數據幀。
視頻壓縮器200也包括符號量值轉換器210。在實際中，利用最有助於簡單的算術運算的數據表示，如二進位反碼或二進位補碼的數據表示，子波係數被存儲在輸入存儲區206中。然而，在下面的說明中將變得更清楚，當在要壓縮的數據中的二進位「1」位的出現數量被最小化的時候，ADK壓縮器208運行得最為高效。為此，符號量值轉換器210與ADK壓縮器208相結合將存儲在輸入存儲區206的數據轉換為符號量值格式，如圖5所示。圖5圖解了一個優選數據表示，包括N位量值表示502、符號位504和標記位506。在所示的示例中，N＝14。因為實際的數據被表示為量值，最高有效位將是二進位「0」數字的可能性最大。如現有技術所公知的，符號位504表示是否整個值是正或負。雖然符號位504被示出在最低有效位的位置，符號位504可以佔用任何位的位置，這由設計的考慮來決定。同樣，標記位506也可以佔用任何位的位置，這是設計的選擇問題。下面特別參照圖6和11更詳細地說明標記位506的使用。
圖3是圖1所示的視頻解壓器300的框圖。雖然實際上任何適當快的微處理器都可以作為視頻解壓器300來起作用，本領域的技術人員應當理解大多數數位訊號處理器(DSP)在諸如反子波變換計算的複雜運算中固有地優於通用微處理器。而且，可以期望利用可編程邏輯陣列或其他類似的硬體實施例來實現視頻壓縮器300。一般而言，視頻解壓器300執行與視頻解壓器200互補的運算以提供原始輸入的視頻信號的再現。
視頻解壓器300接收由按照本發明的一個視頻壓縮器提供的壓縮數據302。壓縮數據302被發送到ADK解壓器304。如下面將詳細說明的，ADK解壓器304首先再創建符號量值格式的子波係數並將它們存儲在輸出存儲區306中。而且，與符號量值轉換器308相結合，ADK解壓器304使得接收到的子波係數轉換為更適合於在反子波變換處理中使用的數據表示，如二進位補碼或二進位反碼數據表示。在此結束後，反子波變換310在接收的子波係數上操作以提供未壓縮的數據312。用於反子波變換的技術是本領域內公知的。與視頻壓縮器200的方式類似，視頻解壓器300包括控制功能314，它收發控制信號316、318以對ADK解壓器304和反子波變換310之間的操作排序。即，當ADK解壓器304完成解壓一幀數據時，它通知控制功能314，作為響應，控制功能314通知反子波變換310它可以開始處理了。當反子波變換310結束其操作時，它通知控制功能314，其隨後通知ADK解壓器它可以再次提供更為壓縮的數據。下面參照圖6-12說明ADK壓縮器和解壓器的各種實施例。
圖6是圖解用於提供壓縮的數據的第一方法的流程圖。圖6所圖解的步驟可以通過上述的視頻壓縮器200特別是ADK壓縮器208來實現。在步驟601，包含多個元素的視頻數據被提供作為輸入數據。在一個優選實施例中，視頻數據包括通過上述的多級子帶分解產生的子波係數(針對一個視頻幀的亮度、紅色度和藍色度分量的每個)；每個子波係數被作為輸入數據的一個分立的元素。當然，輸入數據可以包括除了子波係數之外的數據類型。在步驟602，與分量的任何一個相對應的數據元素被作為要分析的初始分量而訪問。在一個優選實施例中，亮度分量是初始分量。
在步驟603，記錄位位置對於每個Y、Cr和Cb分量被可選地識別。再次參見圖5，N位量值數據502可以被認為佔用了多個位位置(不包括符號位504和標記位506)。如圖5所圖解的，數據502包括14個不同的位位置，從最高有效位位置(標為「數據位13」)到最低有效位位置(標為「數據位0」)。在本發明的上下文中，對於給定的分量的記錄位的位置是與具有最大量值的元素的最高有效位(即具有二進位「1」值)相對應的位位置。因此，為了確定如亮度數據的記錄位的位置，搜索亮度數據以找到最大的量值。假定例如所有亮度數據的最大量值(進一步假設N位的量值，其中N＝14)為「00110111010010」。在此示例中，亮度數據的記錄位位置是標為「數據位11」的位位置，如圖5箭頭標出的「LBP」所示。此處理隨後對於紅色度和藍色度將被重複以提供三個記錄位位置。雖然這三個記錄位位置的值的每個都可以被提供作為輸出，在本優選實施例中，這三個記錄位位置的最大值隨後被提供作為壓縮處理的輸出。
如下面詳細說明的，本發明通過在給定的位位置定位具有二進位「0」值的數據元素的最大的可能塊而提供壓縮。在給定的位位置的這樣的數據塊隨後被在輸出數據流中的單個比特緊密地表示。在數據中給定的位位置找到的二進位「1」值必須被分離地發送。因此，記錄位位置表示在要壓縮的數據中搜索二進位「1」值的起始點；對於所有的數據元素，我們知道大於記錄位位置的在位位置的所有位值由二進位「0」值構成，因此沒有必要發送它們。這可以通過示例而更好地理解。
參見圖7，圖中有一個圖解的塊704A，包含標為「AAx」的數據元素，其中x可以是「A」、「B」、「C」和「D」。為了簡單起見，假設每個數據元素包含一個3位的量值，最高有效位的位置在最左面的位位置(位位置2)，最低有效位的位置在最右面的位位置(位位置0)，其間只有一位(位位置1)。還假設每個數據元素的值如下「AAA」是「010」、「AAB」是「001」、「AAC」是「011」、「AAD」是「000」。顯然，這些數值的最大量值為「011」，此數值的具有二進位「1」值的最高有效位位於位位置1。因此，位位置1被識別為記錄位位置。因為更高位位置的所有位(即位位置2)具有二進位「0」值，因而沒有必要發送它們。當接收機接收到記錄位位置時，它將自動假設，對於所有的數據元素(本例中限於「AAx」元素)，高於記錄位的位位置的位值是「0」。在此示例中，對記錄位位置的使用消除了發送四位數值的必要。當然，這一相同的思想可以被應用到包含更多位位置的數據表示並因此在可能的情況下提供更大的發送效率。
再次返回圖6，在步驟604初始化一個分析位位置。雖然該分析位位置可以被初始化為任何位位置，當記錄位位置已經被確定時，分析位位置最好被初始化為記錄位位置的值。無論如何，本領域的一般技術人員會認識到，通過將分析位位置初始化為更高有效位的位位置並且在分析過程繼續的時候將分析位位置遞減到更低有效位位置，便利了嵌入流的產生。而且在步驟604中也示出，一個遞歸指示符j被初始化為其最大值J。這裡說明的遞歸指示符僅僅被用於圖解的目的；本領域的一般技術人員會認識到，對於實現遞歸步驟存在很多技術。在圖6的實現方式中，在任何時間的遞歸指示符的數值指示目前考慮的大小塊，最大值J指示最大的可能塊正被考慮，同時逐漸變小的值與逐漸變小的塊尺寸相對應。
在步驟605，輸入數據(此處是所有的視頻數據)被邏輯地再分成多個塊。雖然在優選實施例中輸入數據被再分成4個相同大小的塊，輸入數據被邏輯再分的方法是設計選擇的問題。例如，再次參見圖7，圖中示出了已經被分成分離的塊702A-D的視頻數據700。在所示的示例中，第一塊702A包含16個標為「Axy」的數據元素，其中x和y都可以是「A」、「B」、「C」和「D」中的任何一個。類似的規則應用於塊702B-D。在步驟606，判定是否有任何塊剩餘需要處理。此處在圖7中圖解的示例中，存在多個塊剩餘需要處理，在步驟607選擇下一個可以獲得的要處理的塊，如第一塊702A。
在步驟608，判定是否目前考慮的塊有最小的塊尺寸。在一個優選實施例中，最小塊尺寸對應於12×8塊，即包含96個數據元素的塊。一旦得到了最小塊尺寸，就不再進一步細分塊以獲得緊密的表示。實際上，最小塊尺寸指示可獲得的「最深」遞歸水平，這從下面的討論中將會明顯。如果當前考慮的塊不具有最小塊尺寸，則處理在步驟612繼續。
在步驟612，當前考慮的最小大小的塊最好再分為多個M×M不重疊塊，其中M＝2。在最小塊尺寸是12×8的時候，這將導致24個2×2的塊。其他M的值也可以使用，而且進一步可以了解在步驟612建立的塊不必是方的。無論如何，在最小大小的塊中的每個子塊隨後被分析。即，對於每個子塊，按照下面的步驟確定和處理在每個數據元素的分析位位置的位值1)當遇到「0」位值時，輸出「0」併到下一個數據元素；2)當遇到「1」位值時，輸出「1」並查驗與此數據元素相關的標記位。如果此數據元素的標記位被置1，那麼該數據元素的符號位已經被輸出並且處理可以在下一個數據元素繼續。如果未置1標記位，輸出該數據元素的符號位，置1標記位並移到下一個元素。(此處理假設標記位被初始化清零。標記位的極性可以容易地被反轉以獲得相同的功能，在此情況下該標記位將初始化為1)此處理被重複直到在各個子塊中的每個數據元素的位位置的位值已經被輸出。對於給定的數據元素的標記位保證當該數據元素的第一個「1」位值被輸出時，對於該元素的符號位被輸出，並且它保證該元素的符號位僅僅被發送一次。用來遍歷在每個子塊中的元素的具體方式是設計選擇的問題。圖7圖解了一個示例。假設第一塊702A包含最小的塊尺寸。在此情況下，子塊704A-D通過「z」方式在子塊之間和在子塊本身內(由箭頭所示)被分析(如上所述)。因此，單獨的數據元素的處理將進行如下「AAA」、「AAB」、「AAC」、「AAD」、「ABA」、「ABB」、「ABC」、「ABD」、「ACA」、「ACB」、「ACC」、「ACD」、「ADA」、「ADB」、「ADC」和「ADD」。當然，也可以容易地採用在子塊之間和/或子塊內的其他方式。然後，處理在步驟613繼續，在此判定是否已經到了當前視頻幀的位界限。因為所提供的輸出是一個嵌入流(根據遞減分析位位置和結構中的元素的遍歷順序)，處理可以在任何點停止，即當達到分配給壓縮的視頻數據輸出的預定數量的位時。如果還未達到位界限，則在步驟606繼續在第j級的另外塊的處理。
如果在步驟608，所考慮的塊不具有最小塊尺寸，處理在步驟609繼續。在步驟609，判定是否當前塊的每個數據元素在分析位位置包含第一位值。(在一個優選實施例中，如圖6所示，第一位值是「0」位值，而第二位值是「1」位值)。如果肯定，則在步驟614輸出該第一位值(即一個「0」位)，作為在當前考慮的塊的分析位位置的所有數據元素的代表。例如，假設在第一塊702A內的每個數據元素(即元素「Axy」，其中x和y可以是「A」、「B」、「C」和「D」中的任何一個)在當前分析位位置包含一個「0」比特。一個單獨的「0」比特隨後被提供作為在該分析位位置的所有數據元素的輸出代表。在步驟613繼續處理，在此再次判定是否已經達到當前視頻幀的位界限。如果否定，處理在步驟606繼續。
然而，如果在步驟609確定了當前塊的任何數據元素在分析位位置包含第二位值(即一個「1」位)，那麼在步驟610輸出第二位值。此處的第二位值輸出將向接收方指示已經發生遞歸和處理將在更小的塊尺寸基礎上繼續。所以，也是在步驟610，當前塊(如第一塊702A)被指定為輸入塊(預備在步驟605進一步細分)，並且遞歸指示符j被減一，指示發生了至少一級的遞歸。如果在步驟611，還沒有超出正在被分析的當前幀的輸出位界限，則處理在步驟605繼續。在步驟605，輸入數據(現在是第一塊702A)再次被邏輯分成例如圖7所示的多個塊，產生標為704A-D的多個塊。注意在此處，最高級的更大的塊(即塊702B-D)還未被處理。在新一級的處理隨後按照上述的步驟606-614而進行。
步驟606和615相結合判定何時給定級的遞歸已經完成，指示下面兩者之一(i)對於整個幀的處理已經完成，或者，(ii)處理必須返回下一個最高遞歸級(即下一個最大塊尺寸)來繼續處理。例如，假設當前j＜J，標為704A-D的塊當前正在被處理，並且標為704D的塊按照步驟612或步驟614才完成了處理。在步驟606，在此級沒有更多個塊剩餘要處理，因此步驟615將確定處理還沒有完成最高遞歸級，因為j≠J。在步驟616，遞歸指示符被加一，並且在步驟606判定是否存在任何另外的在新的第j級的塊剩餘要被處理。因此，當完成了標為704D的塊時，遞歸指示符將加一而達到下一個最高級。在此級，標為702B-D的塊將仍需要被處理，整個步驟將重複。
當對於當前被分析的分量而言在當前分析位位置的所有數據元素的壓縮已經被執行的時候(即步驟615的「是」分支)，處理將在步驟617繼續。在步驟617，判定是否在當前的分析位位置更多的分量剩餘要被分析。在一個優選實施例中，亮度分量被首先在第一分析位位置分析，其後每個色度分量在第一位位置被分析。這個順序對於隨後的位位置重複直到位界限被達到或所有的分量在所有的位位置被處理。如果在當前的分析位位置還有分量剩餘要被分析，那麼與下一個分量相對應的數據元素在步驟618被訪問，並且處理返回步驟605以在當前分析位位置分析新分量。
然而，如果在當前分析位位置沒有分量剩餘要被分析，處理在步驟619繼續，在此判定是否還有位位置剩餘要被分析。如果否定，那麼所有的分量已經在所有可能的位位置被分析，並且對於幀的處理結束。(注意如果在達到位界限之前，所有的分量已經在所有的位位置被分析，則到達位界限的剩餘的位預算可以填充以假數據比特以便保持位邊界。)但是如果還有另外的位位置剩餘要被分析，則與初始分量(即與在步驟602選擇的分量相同的分量)相對應的數據元素在步驟620被訪問。在步驟621，下一個位位置被指定為分析位位置。在一個優選實施例中，步驟621包含將分析位位置減一以達到下一個最高有效位位置的步驟。處理可以隨後在步驟605恢復。
圖8是圖解用於提供解壓縮的視頻數據的第一方法的流程圖。圖8中圖解的步驟可以通過上述的視頻解壓器300特別是ADK解壓器304來實現。圖8中圖解的方法與上述的與圖6相關的方法互補。在步驟801，適合於存儲至少一幀的解壓視頻數據的數據存儲區被指定為一個輸出存儲區。在一個優選實施例中，解壓的視頻數據包含由亮度、紅色度和藍色度視頻分量的多級子帶分解產生的子波係數，每個子波係數被當作一個獨立的數據元素。在步驟802，接收到壓縮數據，如通過圖6圖解的方法而提供的壓縮數據。在一個優選實施例中，被壓縮的數據包含被壓縮的視頻數據和包括上述的記錄位位置的數據表示。在步驟803，用於存儲與各分量(Y，Cr，Cb)中的任一個相對應的解壓數據的輸出存儲區的那個部分被訪問作為要被合成的初始分量。在一個優選實施例中，亮度分量是初始分量。
在步驟804，一個合成位位置被初始化。在記錄位位置已經被提供的時候，合成位位置被初始化為與記錄位位置相同的值，但是可以使用任何位位置值，只要它同樣地跟蹤上述與圖6相關的分析位位置的進展。也是在步驟804，一個遞歸指示符j被初始化為其最大值J。與上述與圖6相關的遞歸指示符類似，圖8的遞歸指示符僅僅是許多可獲得的用於實現遞歸步驟的方法之一，在此描述僅僅用於說明的目的。
在步驟805，輸出存儲區被邏輯地細分成多個塊。具體而言，在此步驟創建的塊結構最好在空間定向和尺寸上與上述的步驟605的第一個重複操作產生的塊結構相同。以這種方式，由圖8的處理產生的解壓的視頻數據應當與原始壓縮的視頻數據相同(假設在發送期間在被壓縮的視頻數據中沒有發生不可改正的錯誤)。在解壓視頻數據的處理中，當解壓被壓縮的數據的時候，遵循與用來分析視頻數據的相同的空間形式。
在步驟806，判定是否在當前級上有任何塊剩餘要被處理(即要接收重新構建/解壓的視頻數據)。由於通過圖8的處理的第一路徑是在第J級，要被處理的塊將對應於最大可能的塊尺寸。在步驟807，選擇下一個可獲得的塊(對於第一個重複操作，這將是第一個可獲得的塊)，在步驟808，判定是否所選擇的塊包含最小尺寸的塊。如上所述，最小尺寸的塊對應於最深的遞歸級。如果當前選擇的塊不是最小尺寸的塊，處理在步驟809繼續。
在步驟809，對應於所考慮的塊的所接收的壓縮數據的一位被分析以確定其位值。如果該位包含一個第一位值(最好是一個「0」位值)，則處理在步驟814繼續，在此具有第一位值的位被存儲在形成當前選擇的塊的每個數據元素中的合成位位置。以這種方式，本發明可以提供大量數據的非常緊密的表示，尤其是當塊尺寸較大時。隨後，在步驟813，可選地判定是否已經達到當前視頻幀的位界限。如上所述，壓縮處理可以在當已經達到分配給被壓縮的視頻數據輸出的預定數量時的任一點停止。同樣，解壓處理可以在已經處理了預定數量的接收的壓縮視頻比特後停止。這又是被壓縮的視頻數據的嵌入流特性導致的結果。如果還沒有達到所述位界限，則在步驟806繼續進行在第j級另外的塊的處理。
但是，如果在步驟809分析的位包含第二位值(最好是一個「1」位值)，則處理在步驟810繼續，在此當前選擇的塊被指定為輸出存儲區，遞歸指示符j減一。實質上，對應於當前所選擇的塊和具有第二位值的所接收的比特作為一個標誌指示至少一個數據元素包含第二位值(在合成位位置)，並指示進一步的合成將在當前所選的塊內基於更小的塊而進行。如果在步驟811，還沒有超過正在被合成的當前幀的位界限，則處理在步驟805繼續。在步驟805，輸出存儲區(現在是在通過步驟806以及後面步驟的前一個路徑中所考慮的塊)被再次邏輯細分為多個塊。注意在此，在最高級(即前一個級)的更大的塊還沒有完全處理。隨後在新一級的處理按照步驟806及其後面的步驟進行。
隨著遞歸處理的繼續，將會達到一個點，在此，所考慮的結果發生的塊將具有最小的塊尺寸，如步驟808所確定的。當此發生時，在步驟812的處理實際上是上述與步驟612相關的處理的相反處理。在步驟812，當前考慮的最小尺寸的塊最好被再分成多個M×M塊，其中M＝2。又是如此，在最小塊尺寸是12×8之處，這將導致24個2×2塊。M的其他值也可以被使用，進一步會明白在步驟612建立的塊不需要是方的。無論如何，在最小尺寸的塊中的每個子塊的每個數據元素在合成位位置的位值被隨後合成。即，對於每個子塊，在每個數據元素的合成位位置的位值按照下面的步驟基於從壓縮的視頻數據所接收的比特而確定1)當遇到「0」位值時，存儲一個「0」並移向下一個數據元素；2)當遇到「1」時，存儲一個「1」並查驗與該數據元素相關的標記位。如果該數據元素的標記位被置位，那麼該數據元素的符號位已經被存儲，處理可以在下一個數據元素繼續。如果標記位未置位，則存儲下一個接收的比特作為該數據元素的符號位，對標記位置位並移向下一個元素。(此處理假設標記位被初始清除。標記位的極性可以容易地反轉以獲得相同的功能，此時標記位可以被初始置位)此處理被重複直到已經存儲了在各個子塊中的每個數據元素的位位置的位值。給定數據元素的標記位保證當存儲了該數據元素的第一「1」位值的時候該元素的符號位被存儲，並且它保證該元素的符號位僅僅被存儲一次。用於在每個子塊中遍歷多個元素的具體方式是設計選擇的問題，但是在任何情況下應當與分析/壓縮處理中使用的方式相同。
步驟806和815相結合判定何時已經完成了給定級的遞歸，這表示下面兩者之一(i)整個幀的處理已經完成，或(ii)處理必須返回下一個最高遞歸級(即下一個最大塊尺寸)來繼續處理。例如，假設當前j＜J，並且在(j)級的最後塊才完成處理(例如按照步驟812或步驟814)。在步驟806，將不再有(j)級的塊剩下要處理，因此步驟815將確定因為j≠J，所以還沒有完成最高遞歸級。在步驟816，遞歸指示符加一，在步驟806，判定是否在新的第j級有任何另外的塊被剩餘要處理。如果在新的第j級有塊被剩餘要處理，步驟806-814按上述執行。
當對於當前正在合成的分量來說在當前合成位位置的所有數據元素的重建已經執行的時候(即步驟815的「是」分支)，處理將在步驟817繼續。在步驟817，判定是否在當前合成位位置還有分量剩餘要被合成。在一個優選實施例中，在第一合成位位置亮度分量被首先合成，其後是在第一位位置每個色度分量合成。此順序對於後續的位位置重複直到達到位界限或所有的分量已經在所有的位位置被處理。如果在當前合成位位置還有分量剩餘要被合成，那麼在步驟818訪問用於存儲與下一個分量相對應的數據元素的輸出存儲區的那個部分。然後，處理返回步驟805以在當前合成位位置重建新的分量。
但是，如果在當前合成位位置沒有分量剩餘要被合成，則處理在步驟819繼續，在此確定是否還有任何位位置剩餘要被合成。如果否定，那麼所有分量已經在所有可能的位位置被合成，對該幀的處理結束。(注意如果在達到位界限之前，在所有位位置所有的分量已經被合成，則剩餘的從被壓縮的數據接收的比特最好是被提供假數據比特以便保持位邊界，並且可以被忽略)但是，如果有另外的位位置剩餘要被合成，則在步驟820訪問用於存儲與初始分量(即與在步驟803所選擇的相同的分量)相對應的數據元素的存儲區的那部分。其後，在步驟821，下一個位位置被指定為合成位位置。在一個優選實施例中，步驟821包含使合成位位置減一達到下一個最高有效位的步驟。隨後步驟可以在步驟805恢復。
與圖6和8相關的所說明的方法一起提供了用於數據壓縮和解壓的一種有效技術，該數據尤其是從分級的、多級子帶分解產生的子波係數。通過識別可以被緊密地表示的數據的最大可能的塊，本發明提供好的壓縮率與相對小的計算複雜程度。下面參照圖9-12說明了本發明的另一個實施例。圖9-12特別圖解了一種用於基於多個升序表的ADK壓縮/解壓的方法。升序表提供了子波係數的更加抽象的表示以使得最容易接受高度緊密表示方法的那些數據部分可以容易地被識別。
圖9圖解了用於構建升序表的方法。圖9所示的該方法可以通過視頻壓縮器200來實現，最好是在子波係數已經被計算後通過子波變換204，或者在子波數據實際壓縮之前通過ADK壓縮器208。無論如何實現，該方法在步驟901開始，在此子波係數被作為輸入而提供。最好，子波係數以與上述子波變換204相關的方式類似的方式而提供。從下面的討論中可以明顯看出，當亮度、紅色度和藍色度分量的每個被作為輸入提供時，對於這每個分量創建各自的升序表。隨後在步驟902，結果發生的子波係數(對應於Y、Cr或Cb之一)被存儲作為0級表，最好是按照上述的與圖4相關的安排而存儲。另外，在步驟903，級指數k被初始化為一(1)。級指數k僅僅是那些本領域的一般技術人員將認可為對於構建多個升序表有用的多個方法之一，如下所述。
在步驟904，(k-1)級表被再分為多個塊。對於通過步驟902的第一路徑，(k-1)級表對應於0級表。(k-1)級表被邏輯再分的方式是設計選擇的問題。在一個優選實施例中，(k-1)級表被再分成多個M×M不重疊塊，其中M＝2。當然可以使用其他塊尺寸；進一步可以期望也可以使用非方的塊尺寸。在步驟905，判定是否有任何(k-1)級表中的塊剩餘要被處理。如果肯定，在步驟906選擇下一個可獲得的塊。在步驟907，當前選擇的塊的多個數據元素被一起進行逐位或邏輯運算以提供縮小的數據元素。(為了解釋的目的，或運算以「·」符號表示。)在圖10A和10B中進一步圖解了此處理。
圖10A描述了多個2×2塊，每個包含多個數據元素。為了簡化的目的，每個數據元素包含一個單一比特的數據，數值如圖10A所示。四個2×2塊由標記1002所示。按照步驟907，第一塊的多個元素(包含標為「AAx」的數據元素，其中x為「A」、「B」、「C」和「D」中的任何一個)一起進行或運算，產生具有位值「1」的縮小的數據元素「AA」(「AAA」·「AAB」·「AAC」·「AAD」＝0·1·1·0＝1)。數據元素「AAA」、「AAB」、「AAC」和「AAD」被稱為縮小的數據元素「AA」的「孩子」。相同的步驟在第二、三和四塊的數據元素(分別包含標為「ABx」、「ACx」和「ADx」的數據元素，其中x為「A」、「B」、「C」和「D」中的任何一個)執行，產生標為「AB」、「AC」和「AD」的縮小的數據元素。實際上，每個縮小的數據元素的值指示在任一個其相關的孩子中一個「1」位值存在與否。在實際中，每個數據元素不是包含單一的位值，而是按照例如圖5所示的數據表示包含預定數量的位。在該情況下，在每個相對應的位位置的數據元素的位值被一起進行或運算(逐位或)，導致產生與其對應的孩子具有相同長度的縮小的數據元素。在步驟908，在(k)級表中的對應位置存儲每個縮小的數據元素。只要在當前級(k)還有塊要處理，就重複步驟905-908。當在創建減小的數據元素過程中使用2×2塊時，所產生的(k)級表是(k-1)級表的一半(在每維上)，如圖10A和10B所示。
當在步驟905確定在(k-1)級表中沒有更多的塊要處理的時候，處理在步驟909繼續，在此判定是否才完成的縮小的元素的表對應於最大級(K)的表。即圖9所示的處理將導致產生所處理的每個分量(Y，Cr，Cb)的K+1個表。表1圖解了按照圖9構建的升序表的優選參數。如表1所示，優選數值為，亮度分量K＝5，每個色度分量K＝4。當然，根據需要可以使用K的其他值。
表1

如果還沒有產生最大級(K)表，則級指數k在步驟910加一，處理在步驟904繼續。隨後，執行步驟904-908直到已經產生新的第k級的縮小的數據元素的表。例如，參見圖10B和10C，在由標號1004識別的2×2塊中的數據元素如上所述被縮小以提供縮小的數據元素1006(「A」)。注意在由標號1004識別的塊中的數據元素是縮小的數據元素1006的孩子；由標號1002識別的數據元素是縮小的數據元素1006的子孫。那些包括標為「Bx」、「Cx」和「Dx」的數據元素的塊被類似地處理以分別提供縮小的數據元素「B」、「C」和「D」，每個數據元素具有如上所述的類似的孩子/子孫關係，其中x是「A」、「B」、「C」和「D」之中的任一個。
最後，在步驟909確定，對於任何給定的分量(Y，Cr，Cb)，完成了縮小的係數的(K)級表。當此發生時，在步驟911進一步判定是否剩餘任何分量要處理。如果肯定，如上所述處理在步驟901繼續。如果否定，處理在步驟912繼續，在此遍歷升序表以便提供壓縮的數據，如下面特別參照圖11所述。如下面更詳細討論的，所述升序表提供了子波係數的緊密的表示並因此便利了壓縮的分析。
圖11圖解了用於特別基於如上所述參照圖9的升序表的使用而提供壓縮的數據的另一種方法。圖11圖解的方法可以通過上述的視頻壓縮器200特別是ADK壓縮器208來實現。假設在實施圖11的方法之前，如上所述的升序表已經針對要被壓縮的視頻幀的每個分量(Y，Cr，Cb)而被創建。在步驟1101，以與上述步驟602相同的方式針對每個Y，Cr，Cb分量而可選地識別記錄位位置。再一次，雖然三個記錄位位置的每個都可能被分別提供作為輸出，但是這三個記錄位位置的最大者最好被提供作為壓縮處理的輸出。在步驟1102，針對任一個分量的升序表被訪問作為要分析的初始分量，但是亮度分量的升序表被優選為初始分量。
在步驟1103，一個分析位位置被初始化。雖然該分析位位置可以被初始化為任一位位置，該分析位位置最好被初始化為記錄位位置的數值(當已經提供了一個記錄位位置的時候)並在其餘的壓縮處理中遞減。而且，在步驟1103，遞歸指示符j被初始化為其最大值J。此處所述的遞歸指示符僅用於說明的目的；本領域的一般技術人員將認識到，實現遞歸步驟有很多技術。在圖11圖解的實現方式中，任何給定的時間的遞歸指示符的值指示當前考慮的是哪一級的升序表；最大值J表示當前考慮的是最高級表，同時逐漸變小的數值對應於逐漸變低的表級。
在步驟1104，訪問(j)級的表。當j＝J時，所訪問的表是當前分析的分量的最高級的表。參見圖10所示的示例，圖10C中的縮小的係數的表是最高級的表。在步驟1105，判定是否當前遍歷的表是0級的表。如果否定，那麼在步驟1106判定是否剩餘(j)級表中的任何數據元素要分析。如果肯定，在步驟1107訪問下一個數據元素，並且在步驟1108判定是否該縮小的數據元素在分析位位置包括一個第一位值，其中在一個優選實施例中，該第一位值是「0」位值。(注意在步驟1108分析的任何數據元素是根據步驟1105的縮小的數據元素)如果在步驟1108檢測到第一位值，那麼在步驟1110，第一位值被提供作為在分析位位置的數據元素的所有子孫的輸出代表。再次參見圖10，假設所示的所有位值對應於第P個位位置以及分析位位置當前也被設置為第P個位位置。進一步假定當前考慮的數據元素是圖10B中標為「AB」的數據元素。在確定該「AB」數據元素在第P位位置包含一個「0」位值的時候，輸出一個「0」位值以便表示「AB」的每個子孫。以另一種方式來說，因為標為「ABx」的數據元素(其中x是「A」、「B」、「C」和「D」中的任一個)都在第P位位置包括「0」位值，輸出一個單一的「0」位值表示所有的四個數據元素是足夠充分的。壓縮因此而被提供，因為一個接收方將明白此「0」位值輸出代表所有的四個標為「ABx」的數據元素。當最高級表(J級)的一個數據元素在分析位位置包含一個「0」位值的時候，最大的壓縮被提供，因為它允許一個單一的輸出比特來代表在分析位位置的最大可能數量的子孫。在步驟1111，判定是否已經達到當前幀的位界限，如果否定，則如果有其他數據元素的話，在步驟1106繼續其他數據元素的處理。
如果在步驟1108檢測到任何數據縮小的數據元素的第二位值，那麼在步驟1109第二位值被提供作為輸出。此處的第二位值輸出將向接收方指示已經發生了遞歸以及處理將在下一個最低表級繼續。為此，遞歸指示符j減一。如果在步驟1112，被分析的當前幀的輸出位界限還沒有超過，則處理在步驟1104繼續，在此在步驟1108考慮的數據元素的孩子以上述的與步驟1104-1111相關的方式被分析。
對於0級表中的數據元素提供特殊的處理。再次參見圖10，標為「A」的數據元素將使得處理向下遞歸到標為「AA」的數據元素。同樣，處理將再次向下遞歸到「AA」的子孫，即數據元素「AAx」。因此在步驟1105，對j＝0的測試將為真，處理將在步驟1113繼續。在步驟1113，每個元素被以預定的順序分別地處理，該順序如上述的相關於圖7的「z」形式，但是也可以使用任何這樣的形式。對於每個數據元素，按照下面的步驟確定和處理在分析位位置的位值1)當遇到「0」位值時，輸出一個「0」並移向下一個數據元素；2)當遇到「1」時，輸出一個「1」並查驗與該數據元素相關的標記位。如果該數據元素的標記位被置位，那麼該數據元素的符號位已經被輸出，處理可以在下一個數據元素繼續。如果標記位未置位，輸出該數據元素的符號位，置位標記位並移向下一個元素。(該處理假定這些標記位被初始清除。標記位的極性可以容易地被反轉以獲得相同的功能，在此情況下，將初始置位)一旦0級數據元素已經以這種方式被處理，在步驟1114進行查驗以保證當前幀的位界限還沒有被超出。如果否定，遞歸指示符j在步驟1115加一，於是將處理返回下一個最高級(1級)用於那一級的另外元素——如果有的話——的處理。
當在步驟1106確定在給定的級(除了0級)沒有更多的元素剩餘要處理的時候，處理在步驟1116繼續以判定是否才結束的當前級是最高的級(J)。如果否定，遞歸指示符j在步驟1115加一，於是處理返回到下一個最高級用於處理該級的另外的元素——如果有的話。例如，參見圖10，當圖10A所示的標為「ADx」的數據元素已經根據步驟1113完成了處理的時候，處理將通過步驟1116和1115向上遞歸回到圖10B所示的表。由於在此級沒有更多的元素剩餘要處理(數據元素「AD」是此級要處理的最後的孩子數據元素)，因此處理將再次向上遞歸回到圖10A所示的表。在此級上，在步驟1116的測試將為真(數據元素「D」是在此級上要處理的最後的數據元素)，處理將在步驟1117繼續。
實質上，圖11的方法，在至今已經描述的位置，檢查在升序表的最高級表中發現的每個數據元素，並且在必要的地方向下遍歷樹結構(即每個數據元素的子孫)來識別那些可以最緊密地表示的數據元素。再次參見圖10，對於對應於標為「A」的縮小的數據元素的樹的遍歷將進行如下(假定還沒有符號位被輸出)。從「A」縮小的數據元素開始，遇到位值「1」，因此輸出一個「1」並考慮「A」的子孫(「AA」、「AB」、「AC」、「AD」)。「AA」縮小的數據元素也具有一個「1」值，因此輸出一個「1」並考慮「AA」的子孫(「AAA」、「AAB」、「AAC」、「AAD」)。注意在此例中，「AA」的子孫全是「0」級的數據元素。「AAA」數據元素是一個「0」，因此輸出一個「0」。「AAB」數據元素是一個「1」並且相應的標記位還沒有被置位(按照示例的規則)，因此輸出一個「1」，隨後跟隨著「AAB」的符號位，相應的標記位被置位。「AAC」數據元素是一個「1」，因此輸出一個「1」，隨後跟隨著「AAC」的符號位，相應的標記位被置位。「AAD」數據元素是一個「0」，因此輸出一個「0」。這就完成了「AA」的子孫的處理，因此處理繼續針對「A」的又一個子孫「AB」數據元素進行。「AB」數據元素是一個「0」，因此輸出一個「0」。「AC」元素也是一個「0」，因此輸出另一個「0」。「AD」數據元素是一個「1」，因此輸出一個「1」並且處理在0級繼續以考慮「AD」的子孫(「ADA」、「ADB」、「ADC」、「ADD」)。「ADA」數據元素是一個「1」，因此輸出一個「1」，隨後跟隨著「ADA」的符號位，相應的標記位被置位。「ADB」數據元素是一個「0」，因此輸出一個「0」。「ADC」數據元素是一個「1」，因此輸出一個「1」，隨後跟隨著「ADC」的符號位，相應的標記位被置位。最後，「ADD」數據元素是一個「0」，因此輸出一個「0」。這就完成了對於「A」數據元素和所有其子孫的處理。如果符號位由符號「s」表示，則通過遍歷「A」數據元素和其子孫產生的輸出結果為下列的位流1，1，0，1，s，1，s，0，0，0，1，1，s，0，1，s，0。遍歷「B」數據元素和其子孫產生的結果為下列的位流1，1，1，s，0，0，0，0，0，1，0，1，s，0，0。遍歷「C」數據元素和其子孫產生的結果為下列的位流1，0，1，1，s，0，0，0，0，1，1，s，0，1，s，0。最後，遍歷「D」數據元素和其子孫產生的結果為下列的位流1，1，0，0，1，s，0，0，1，1，s，0，1，s，0，0。
因此，在本例中，用於表示「A」、「B」、「C」和「D」數據元素的子孫的位的總數量是64位，包括符號位。相反，如果所有的「A」、「B」、「C」和「D」數據元素的子孫(和相對應的符號位，根據相同的規則)被輸出而未利用本發明，則需要總共76位。這對應於本例中所需要的數據數量的超過15％的無損縮小。當然，在更高表級的「0」值的出現提供了數據壓縮更大的機會。實際上，已經發現更高空間頻率的子波係數經常包括相當多個「0」位值(根據在圖像中的大多的信息在較低的空間頻率上發現的事實)。作為結果，可以利用較為普通的計算源來獲得子波係數數據的充分的壓縮率。例如，可以實時地獲得100∶1的壓縮率並具有可以接受的視頻質量。
再次返回圖11，當對於當前被分析的分量在當前分析位位置的所有數據元素的壓縮已經被執行的時候(即步驟1116的「是」分支)，處理將在步驟1117繼續。在步驟1117，判定是否在當前的分析位位置有更多的分量剩餘要被分析。在一個優選實施例中，亮度分量被首先在第一分析位位置分析，隨後是每個色度分量在第一位位置被分析。此順序對於後續位位置重複直到達到位界限或所有的分量在所有的位位置已經被處理。如果在當前分析位位置剩餘更多的分量要被分析，那麼針對下一個分量的升序表在步驟1118被訪問，處理返回步驟1104以在當前分析位位置分析新的分量。
但是，如果在當前分析位位置沒有剩餘更多的分量要被分析，處理在步驟1119繼續，在此判定是否剩餘任何更多個位位置要分析。如果否定，那麼所有的分量在所有可能的位位置已經被分析，對於該幀的處理結束。(注意如果在位界限被達到之前，所有的分量在所有的位位置已經被分析，則到達位界限的剩餘的位預算可以被填充假數據比特以便保持位邊界)但是，如果剩餘另外的位位置要被分析，則在步驟1120訪問針對初始分量的升序表(即與在步驟1102選擇的相同的分量)，並在步驟1121，下一個位位置被指定為分析位位置。在一個優選實施例中，步驟1121包括將分析位位置減一到達下一個最高有效位位置的步驟。處理隨後可以在步驟1104恢復。
圖12是一個流程圖，圖解了用於提供解壓的視頻數據的另一種方法。圖12圖解的步驟可以通過上述的視頻解壓器200特別是ADK解壓器304來實現。圖12圖解的該方法與上述與圖11相關的方法互補。在步驟1201，接收到壓縮數據，如利用圖11的方法提供的壓縮數據。在一個優選實施例中，壓縮的數據包含壓縮的視頻數據並包括如上所述的記錄位位置的數據表示。
在步驟1202，對應於任一分量(Y，Cr，Cb)的升序表的儲存區被訪問作為要合成的初始分量。在一個優選實施例中，亮度分量是初始分量。
在步驟1203初始化一個合成位位置。雖然該合成位位置可以被初始化到任何位位置，最好該合成位位置被初始化到記錄位位置值(當已經提供一個記錄位位置的時候)並且在餘下的解壓處理中遞減。而且，在步驟1203，遞歸指示符j被初始化為其最大值J。這裡所述的遞歸指示符僅僅用於說明的目的；因為本領域的一般技術人員會認識到，實現遞歸步驟有很多技術。在圖12所示的實現方式中，在任何給定時間的遞歸指示符的值表示當前考慮的是哪一級的升序表；最大值J表示最高級的表當前正在被合成，同時逐漸變小的值對應於逐漸變小的表級。
在步驟1204，訪問(j)級升序表的存儲區。當j＝J的時候，存儲區對應於當前重建的分量的最高級表。在步驟1206，判定在當前合成位位置是否在(j)級表中剩餘任何數據元素要被合成。如果肯定，在步驟1207訪問下一個數據元素，在步驟1208，判定是否當前重建的表是一個0級的表。如果否定，處理在步驟1208繼續，在此分析來自所接收的壓縮數據的下一個接收的比特。假定在傳輸過程中在所接收的壓縮數據中沒有發生不可糾正的錯誤，在步驟1208分析的接收的比特應當對應於當前考慮的數據元素。在步驟1209，判定是否所接收的比特包含一個第一位值，其中該第一位值是在一個優選實施例中的一個「0」位值。(注意在步驟1209考慮的任何數據元素是按照步驟1207的縮小的數據元素。)如果該第一位值在步驟1208被檢測到，那麼在步驟1212，該第一位值被存儲在當前縮小的數據元素的所有子孫中的合成位位置。例如，參見圖10，假定當前考慮的數據元素是圖10B中標為「AB」的數據元素。在確定對應於「AB」數據元素的接收的比特包含一個「0」位值的時候，一個「0」位值被存儲在每個「AB」的子孫(「ABA」、「ABB」、「ABC」和「ABD」)中的合成位位置。在實際中，所有的數據元素被初始化為全「0」位值，因此免除了實際向存儲器中寫入「0」位值的必要。在步驟1213，判定是否已經達到當前幀的位界限，如果否定，如果存在另外的數據元素，則在步驟1205繼續另外數據元素的處理。
如果在步驟1209檢測到第二位值，則表示必須發生到下一個最低表級的遞歸。為此，遞歸指示符j在步驟1210減一。應當注意圖12圖解的處理的整體目標是再建原被壓縮以提供壓縮的數據的數據元素，即0級表。作為結果，不嚴格要求更高級升序表(1級到J級)也被重建，雖然它們也可以被重建。如果更高級升序表被重建，那麼在步驟1210，第二位值也可以被存儲在(j)級表中的相應的數據元素中(在將遞歸指數減一之前)。如果在步驟1211，當前幀的位界限還沒有超過，處理在步驟1204繼續，在此在步驟1209考慮的數據元素的孩子以上述與步驟1204-1213相關的方式被分析。
當重建0級表中的那些數據元素的時候，提供特殊的處理。當在步驟1207判定所考慮的當前級滿足測試j＝0，處理在步驟1214繼續。在步驟1214，每個要涉及的數據元素以預定順序被分別處理，如上面與圖7相關所討論的「z」形式，雖然也可以使用任何這樣的形式。對於每個數據元素，在合成位位置的位值被基於從壓縮數據接收的比特而按照下面的步驟確定1)當遇到一個「0」位值時，存儲一個「0」，並移向下一個數據元素；2)當遇到一個「1」時，存儲一個「1」並查看與那個數據元素相關的標記位。如果那個數據元素的標記位被置位，那麼該數據元素的符號位已經被存儲，處理可以在下一個數據元素繼續。如果該標記位未置位，存儲下一個接收的比特作為該數據元素的符號位，對標記位置位並移向下一個元素。(此處理假定標記位被初始清除。標記位的極性可以容易地反轉以獲得相同的功能，在此情況下標記位將被初始置位。)此處理重複直到在各個子塊中的每個數據元素的位位置的位值已經被存儲。給定的數據元素的標記位保證當該數據元素的第一個「1」位值被存儲的時候存儲該元素的符號位，並且它保證該元素的符號位僅僅發送一次。遍歷數據元素使用的具體形式是設計選擇的問題，但是無論在何情況下，都應當與分析/壓縮處理中使用的形式相同。遞歸指示符j在步驟1215加一，於是使處理返回下一個最高級(1級)以處理該極的另外的元素——如果有的話。但是在此之前，在步驟1211進行查看以保證當前幀的位界限還沒有被超過。如果否定，則處理在步驟1204繼續。
當在步驟1205確定在給定級(除了0級)沒有剩餘更多的元素要處理，則處理在步驟1216繼續以判定是否才完成的當前級是最高級(J)。如果否定，遞歸指示符j在步驟1217加一，於是使處理返回下一個最高級以處理該極的另外的元素——如果有的話。當對於當前被合成的分量而言在當前合成位位置的所有數據元素的重建已經執行時(即步驟1216的「是」分支)，處理將在步驟1217繼續。在步驟1217，判定是否在當前合成位位置剩餘更多的分量要被合成。在一個優選實施例中，亮度分量被首先在第一合成位位置合成其後每個色度分量在第一位位置被合成。此順序對於後續位位置重複直到達到位界限或所有的分量在所有的位位置已經被處理。如果剩餘更多的分量在當前合成位位置要合成，那麼在步驟1218訪問對應於下一個分量的升序表的存儲區，處理返回步驟1204以在當前合成位位置重建新分量。
但是，如果在當前合成位位置沒有剩餘更多的分量要被合成，則處理在步驟1219繼續，在此判定是否剩餘任何更多的位位置要合成。如果否定，那麼所有的分量已經在所有可能的位位置被合成，對該幀的處理結束。(注意如果在達到位界限之前，所有的分量已經在所有的位位置被合成，則最好剩餘的來自壓縮數據的接收的比特是提供的假數據比特以便保持位邊界，這些接收的比特可以被忽略。)但是，如果剩餘另外的位位置要被合成，則在步驟1220訪問對應於初始分量的升序表的存儲區(即與在步驟1202選擇的相同的分量)，在步驟1221，下一個位位置被指定為合成位位置。在一個優選實施例中，步驟1221包含將合成位位置減一以達到下一個最高有效位位置的步驟。處理可以隨後在步驟1204恢復。
以上所述的僅僅是用來說明本發明的原理的應用。本領域的技術人員可以在不脫離本發明的精神和範圍的情況下實現其他的方案和方法。
權利要求
1.一種處理要壓縮的視頻數據的方法，該方法包括步驟(A)提供視頻數據作為輸入數據，輸入數據的每個數據元素以預定數量的比特表示；和(B)對於表示預定數量比特的多個位位置的至少一個位位置(i)對輸入數據的數據元素分組以提供多個數據塊，每個具有小於輸入數據的塊尺寸；(ii)當數據塊的所有數據元素在位位置包含一個第一位值的時候，輸出該第一位值作為在位位置的數據塊的所有數據元素的表示；和(iii)當數據塊的任何數據元素在位位置包含一個第二位值的時候，輸出該第二位值，並按照步驟(i)至(iii)遞歸地處理作為輸入數據的多個數據塊的每個數據塊，直到達到最小的塊尺寸。
2.如權利要求1的方法，其中步驟(B)還包含步驟(iv)當達到最小塊尺寸時，對於多個數據塊的每個數據塊，輸出一個數據比特代表在位位置的數據塊的每個數據元素。
3.如權利要求2的方法，其中步驟(B)(iv)還包含步驟(a)當代表數據元素的數據比特包含第二位值並當對應於數據元素的標記位未置位時，對於數據塊的每個數據元素，輸出對應於數據元素的一個符號位；和(b)將對應於數據元素的標記位置位。
4.如權利要求1的方法，還包含步驟(C)識別在視頻數據中具有最大量值的最大數據元素；(D)確定被設置為第二位值的最大數據元素的最高有效位以識別記錄位位置；和(E)輸出記錄位位置的數據表示。
5.如權利要求4的方法，其中多個位位置按照從記錄位位置到最低有效位位置的順序被處理。
6.如權利要求1的方法，其中最小塊尺寸對應於2×2塊。
7.如權利要求1的方法，其中視頻數據包括通過亮度數據、紅色度數據和藍色度數據中的任一個的子波變換而產生的子波係數。
8.如權利要求1的方法，其中以符號量值形式表示數據元素。
9.如權利要求1的方法，其中第一位值是一個二進位零值，第二位值是一個二進位一值。
10.一種處理要解壓的數據以提供解壓的視頻數據的方法，該方法包括步驟(A)提供數據存儲區作為輸出存儲區，該數據存儲區的每個數據元素由預定數量的比特表示；(B)接收壓縮的視頻數據以提供接收的比特；(C)對於代表預定數量的比特的多個位位置的至少一個位位置(i)對輸出存儲區的數據元素分組以提供多個數據塊，每個具有小於輸出存儲區的塊尺寸；(ii)當對應於多個數據塊的一個數據塊的接收的比特之一包含一個第一位值的時候，在位位置的數據塊的每個數據元素中存儲該第一位值；和(iii)當對應於多個數據塊的一個數據塊的接收的比特之一包含一個第二位值的時候，按照步驟(i)至(iii)遞歸地處理作為輸出存儲區的數據塊，直到達到最小的塊尺寸。
11.如權利要求10的方法，其中步驟(C)還包含步驟(iv)當多個數據塊的一個數據塊具有最小塊尺寸時，在數據塊的每個數據元素中存儲在位位置的接收比特的對應的一個。
12.如權利要求11的方法，其中步驟(C)(iv)還包含步驟(a)對於數據塊的每個數據元素，當接收的比特的對應的一個包含第二位值並當對應於數據元素的一個標記位未置位的時候，存儲接收的比特中後續接收的一個作為對應於數據元素的一個符號位；和(b)將對應於數據元素的標記位置位。
13.如權利要求10的方法，其中所接收的比特包含記錄位位置的數據表示，該記錄位位置表示被設置為第二位值的數據存儲區的數據元素的最高有效位。
14.如權利要求13的方法，其中多個位位置按照從記錄位位置到最低有效位位置的順序被處理。
15.如權利要求10的方法，其中最小塊尺寸對應於2×2塊。
16.如權利要求10的方法，其中解壓的視頻數據包括通過亮度數據、紅色度數據和藍色度數據中的任何一個的子波變換產生的子波係數。
17.如權利要求10的方法，其中數據元素以符號量值形式表示。
18.如權利要求10的方法，其中第一位值是一個二進位零值，第二位值是一個二進位一值。
19.一種處理要壓縮的視頻數據的方法，其中視頻數據已經通過離散的子波變換處理以提供子波係數，該方法包括步驟(A)在一個0級表中存儲作為數據元素的子波係數，每個子波係數由預定數量的比特表示，0級表構成多個升序表的一部分；(B)從J＝1到K，通過執行下面的步驟構建多個升序表的其他表(i)將來自(J-1)級表的數據元素分組以提供多個數據元素塊；(ii)對於多個數據元素塊的每個數據元素塊，通過對構成數據元素塊的數據元素進行逐位邏輯或運算而形成一個縮小的數據元素，其中數據元素塊的數據元素是該縮小的數據元素的孩子；和(iii)在多個升序表的(J)級表中存儲縮小的數據元素。
20.如權利要求19的方法，其中多個數據元素塊的每個數據元素塊包含一個2×2塊。
21.如權利要求19的方法，其中視頻數據包含亮度數據、紅色度數據和藍色度數據中的至少一個。
22.如權利要求19的方法，其中子波係數以符號量值的形式表示。
23.如權利要求19的方法，其中子波係數包含一個標記位。
24.如權利要求19的方法，還包含步驟(C)識別在0級表中的具有最大量值的一個最大子波係數；(D)確定被設置為二進位一值的最大子波係數的最高有效位以識別一個記錄位位置；和(E)輸出記錄位位置的數據表示。
25.如權利要求24的方法，還包括步驟(F)在多個升序表上執行至少一個降序樹搜索，其中每個降序樹搜索唯一地對應於在記錄位位置和一個最低有效位位置之間並包括這兩者的多個位位置的一個位位置。
26.如權利要求25的方法，其中每個降序樹搜索還包括步驟(i)遍歷多個升序表並識別在位位置的多個升序表的每個數據元素的二進位值，並按照下列步驟輸出壓縮的數據(a)當對於在0級表中的一個數據元素，一個二進位零值被識別的時候，輸出一個二進位零值來代表在位位置的數據元素；(b)當對於在0級表中的一個數據元素，一個二進位一值被識別的時候，輸出一個二進位一值來代表在位位置的數據元素；(c)當針對J＝1到K中的任一個，對於在(J)級表中的一個數據元素，一個二進位零值被識別的時候，輸出一個二進位零值來代表在位位置的數據元素的所有子孫，其後跳過對於在位位置的數據元素的所有子孫的識別步驟；和(d)當針對J＝1到K中的任一個，對於在(J)級表中的一個數據元素，一個二進位一值被識別的時候，輸出一個二進位一值，並按照步驟(a)至(d)遞歸地處理數據元素的孩子。
27.如權利要求26的方法，其中步驟(i)(b)還包括步驟(1)當對應於數據元素的標記位未置位的時候，輸出對應於該數據元素的一個符號位；和(2)對對應於數據元素的標記位置位。
28.如權利要求25的方法，其中位位置初始為記錄位位置並對於每次逐次的降序樹搜索減一。
29.如權利要求27的方法，還包括步驟(G)從J＝0到K，提供包含解碼的(J)級的表的多個解碼的升序表，該多個解碼的升序表的每個數據元素由預定數量的比特表示；(H)接收壓縮的數據和記錄位的數據表示；和(I)通過基於壓縮的數據來執行至少一個降序樹解碼而增加多個解碼的升序表，其中每個降序樹解碼唯一地對應於在記錄位位置和一個最低有效位位置之間並包括這兩者的多個位位置的一個解碼位位置。
30.如權利要求29的方法，其中每個降序樹解碼還包括步驟(J)遍歷多個解碼的升序表，並按照下面步驟在該多個解碼的升序表的每個數據元素中在解碼的位位置存儲壓縮數據的一個二進位值(i)當從壓縮數據識別一個二進位零值並且來自0級表的一個數據元素要被增加時，在該數據元素中在解碼的位位置存儲一個二進位零值；(ii)當從壓縮數據識別一個二進位一值並且來自解碼的0級表的一個數據元素要被增加時，在該數據元素中在解碼的位位置存儲一個二進位一值；(iii)當從壓縮數據識別一個二進位零值並且對於J＝1至K在解碼的(J)級表中的一個數據元素要被增加時，在該數據元素的解碼的0級表中的所有子孫內在解碼的位位置存儲一個二進位零值，並且其後跳過對於該數據元素的所有子孫在解碼的位位置存儲的步驟；和(iv)當從壓縮數據識別一個二進位一值並且對於J＝1至K在解碼的(J)級表中的一個數據元素要被增加時，在該數據元素在解碼的位位置存儲一個二進位一值，並且按照步驟(i)至(iv)遞歸地處理該數據元素的孩子。
全文摘要
表示視頻數據的數據元素最好被邏輯地劃分為多個塊。以逐位的方式查看每個塊以判定是否該塊的數據元素可以以高度緊密的形式表示。如果一個給定的塊不能以這種方式表示,則將其細分為多個具有更小尺寸的塊。這種識別合適的塊和細分的處理被遞歸地重複直到達到最小的塊尺寸。通過使用多個升序表(206)可以獲得同樣的結果,這些表是通過重複地形成縮小的數據元素的表而構建的。這多個升序表被遍歷,並且基於縮小的數據元素,識別能夠接受高度緊密形式的數據塊。子波變換(204)最好被用於提供要壓縮的視頻數據。
文檔編號H03M7/30GK1373968SQ00812675
公開日2002年10月9日 申請日期2000年7月20日 優先權日1999年7月23日
發明者德裡克·R·克拉克, 特迪·P·羅伯茨, 露辛達·E·謝弗, 肯尼思·A·斯託克 申請人:記憶鏈公司