頻域內用於位移估算的區塊匹配的製作方法
2023-04-27 08:59:56 1
專利名稱：頻域內用於位移估算的區塊匹配的製作方法
技術領域：
本發明涉及在位移估算的區塊匹配時，使用頻域內低頻信息產生位移向量的方法，因區塊匹配(block matching)的處理只適用於低頻信息，並不適用於全頻範圍，所以減少數字動畫計算的複雜性。
背景技術：
對於一般計算機、電視、行動電話等屏幕上的數字動畫處理，為了減少存儲器空間，或是減少數據傳輸時的帶寬，都使用了數字動畫壓縮技術。目前在數字動畫壓縮技術最常用的格式包括MPEG-2、MPEG-4、AVS與H.264，這幾種格式都使用位移估算(motionestimation)的方法在時域中對比前後數據的關聯性，再壓縮其數據量。一般的連續動畫每秒必須提供20～30張畫面，以使畫面流暢，連續兩張畫面中相同的圖像必須使用位移估算決定其移動關係。
位移估算的方法之一是將屏幕畫面以16×16的256個像素矩陣作為一個巨塊(Macro-Block，MB)切割，然後為每一個MB找出與前一張畫面相關的最佳位移向量(motion vector)。請參考圖1，其中圖(a)與圖(b)是兩張連續的畫面。但傳送(或儲存)圖(b)畫面時，只需傳送火車的位移向量(虛線箭號所示)，然後補上圖(a)中被火車遮住的背景畫面，並配合原有的火車與背景畫面數據，就可以產生圖(b)。此一方法可大量減少傳送頻寬(或減少存儲器的容量)，但此一方法卻顯著地增加了計算的複雜度。
計算圖(a)中某一個MB的位移向量時，必須將圖(a)MB中每一個像素與圖(b)某一MB中每一個對應像素相減再取絕對值(FullSearch，全搜尋)，然後將256個絕對差異值相加而得到一「累加絕對差異值」(SAD)。如此逐一與圖(b)中所有比較點周圍的MB計算得到許多累加絕對差異值，累加絕對差異值最小者的比較點位置即為所求，其與圖(a)比較點的位置差異、即所謂的位移向量。為了減少計算量，通常設定一個較小的畫面搜尋範圍(Searching Range)，在此搜尋範圍中搜尋得到的累加絕對差異值如果小於預先的設定值，則相對於該比較點位置差異即為所謂的位移向量。
請參考第2圖，以往全搜尋方法的位移估算，如果搜尋範圍為32×32像素(pixels)，MB(Macro-Block)的大小若為16×16，對於某一個MB若欲求取其位移向量，必須對該MB及所有其它MB作運算，因此共有17×17＝289次MB的比較(MB在搜尋範圍中移動，只有17×17的範圍，不讓MB超出搜尋範圍)。每一次比較均依「最小累加絕對差異值」(MAD)的方法運算，將兩個MB其中對應兩像素之值先相減，相減後取其絕對值，然後累加，共需767次運算(相減256次，取絕對值256次，累加255次，256+256+255＝767)。因為共有289次MB的比較，每一次比較需767次運算，所以共需289×767＝221,663次運算才能完成一個MB對同一個搜尋範圍的搜尋，為其找到位移向量。其它相鄰的MB亦須221,663次運算。
若一張畫面為720×480的圖像，則其畫面可分割成1350個MB。每個MB緊緊相連，但無重迭，然而搜尋範圍雖與近鄰的搜尋範圍大量重迭，但每個MB均需重新計算。若欲完成這種畫面的位移向量估算，總運算量約為2.99×108次(1350×221,663)。一般的連續動畫每秒最少必須提供22張畫面，因此其每秒總運算量約為6.58×109次(22×2.99×108)。
由此可看出，全搜尋方法的運算複雜度太高，因此迫使系統採用較高的系統時鐘與較大的數位訊號處理器(DSP)，結果電力消耗極大，使可攜式電子用品的電池無法負荷，亦無法達成低成本的目標。因此許多新方法因應而生，這些新方法可歸類為兩大類一是減少比較點的數目，二是減少計算次數。兩大類的方法可同時運用，以使計算量降至最低。
減少比較點的數目有許多方法，較常採用的有三步驟搜尋(ThreeStep Search，TSS)，四步驟搜尋(Four Step Search，FSS)等。其概要就是在所設定的搜尋範圍中找出數點，選其最小的MAD值，在此一最小的MAD值附近，再作進一步的區域化運算。
減少計算次數的方法較少，常用的是運用不等式如下SUM(ABS(a-b))＞＝ABS(SUM(a)-SUM(b))其中a、b分別代表兩個MB的各個點的像素值。此不等式的意義是兩個MB對應像素絕對差異值之和(即前述MAD運算)大於或等於兩個MB各自像素值之和的絕對差異值(稱為粗略計算)。
上述所有方法都適用於時域(timing domain)，不過將時域轉成頻域後，發明人發現區塊匹配算法可以進一步改進。
發明內容
因此本發明提供一種減少計算量之方法，只需極小部分的硬體改變以及視頻壓縮方法的少許修改，而在頻域中進行位移估算。因為人眼對高頻域不如低頻域敏銳，所以本發明只取低頻信息以找到位移估算的位移向量。
位移估算是在兩張數字動畫畫面的相同圖像之間定出位移關係之用的；視頻壓縮則使用DCT(離散餘弦轉換)程序將一圖像輸入從時域轉成頻域的數據，然後將該數據以直流、低頻、高頻的順序排列；使用量化方式減少該數據中的高頻多餘部分。
本發明方法在上述量化方式之後將位移估算應用於兩張數字動畫畫面的頻域數據，以使計算量減少。
圖1表示位移估算中的位移向量。
圖2表示已有技術中全搜尋位移估算的示意圖。
圖3表示MPEG-4系統在視頻壓縮時所用的典型方塊圖。
圖4表示視頻壓縮所用的樣品圖片。
圖5表示樣品圖片經過DCT轉換後的結果。
圖6表示DCT轉換中的鋸齒狀順序。
圖7表示根據本發明建議在視頻壓縮中使用的系統方塊圖。
具體實施例方式
目前大部分的視頻標準都使用不同的方法壓縮數據，因為人眼對高頻範圍的敏感度不如對低頻範圍的敏感度，所以大部分的視頻壓縮標準使用DCT(Discrete Cosine Transfer，離散餘弦轉換)程序將圖像輸入由時域轉成頻域；然後將數據以直流、低頻、高頻的順序排列；使用量化的方式減少高頻多餘部分；使用VLC(Variable LengthCoding，可變長度編碼)降低編碼空間中的冗餘部分；把經過反壓縮、反DCT(inverse DCT)與反VLC(inverse VLC)的數據最後在時域中使用位移估算減少前後兩張圖片之間的重複部分，請參閱圖3的MPEG-4系統在視頻壓縮所用的典型方塊圖。
參考圖4與圖5，示出視頻壓縮所用的樣品圖片。視頻壓縮使用DCT程序將樣品圖片的圖像由時域(圖4)轉成頻域(圖5)，將數據以直流、低頻、高頻的順序作鋸齒狀(或其它形狀)排列(請見圖6)；然後使用量化方塊(圖3中的「Q」)壓縮人類不敏感的高頻信息，最後使用VLC在編碼空間中壓縮數據，經由一緩衝器(圖3)輸出圖像編碼。
請再次參考圖3，為了達到時間性的壓縮，在反量化(iQ)、返回排列(iF，反鋸齒狀/其它形狀)及反DCT(iDCT)後完成位移估算(ME)的區塊匹配，在所有信息都已在時域恢復後，即可對時域中的數據使用位移估算中的區塊匹配算法。
請參考圖7，本發明提出一種新方法。因為所有的區塊匹配法都可以適用於頻域，所以位移估算可以在反DCT(iDCT)程序之前執行，如圖7中箭號1、2所示。因為人眼只對低頻信息有感應，所以只要比較低頻信息找到最佳匹配點即可，可以剔除高頻信息。例如，可以在8×8DCT方塊(圖5)中每64位只取起初的8位來作位移估算，於是使計算的複雜性降低到原來計算的12.5％。如果必要時，部分位移估算可以在iDCT之後完成。因為所有的比較方法都可以適用於頻域，就像在時域一樣，而且因為剔除了高頻信息而減少了比較點，所以計算複雜性得以降低。
本發明使用已有的方塊/方法，只改變處理的順序，達到了減少計算量的目的。
本發明的精神與範圍僅受限於下述權利要求書，不受限於上述
權利要求
1.一種在頻域中用於區塊匹配的位移估算方法，位移估算是在兩張數字動畫畫面的相同圖像之間定出位移關係之用的；視頻壓縮則使用DCT(離散餘弦轉換)程序將一圖像輸入從時域轉成頻域的數據，然後將該數據以直流、低頻、高頻的順序排列；使用量化方式減少該數據中的高頻多餘部分；該方法則在該量化方式之後將該位移估算應用於兩張數字動畫畫面的該頻域的數據，以減少計算量。
全文摘要
本發明提供一種減少計算量的方法，只需極小部分的硬體改變以及視頻壓縮算法的少許修改，而在頻域中進行位移估算。因為人眼對高頻領域不如低頻領域敏銳，所以本發明只取低頻信息以找到位移估算的位移向量。
文檔編號H04N7/26GK1805544SQ20051000569
公開日2006年7月19日 申請日期2005年1月13日 優先權日2005年1月13日
發明者陳永森, 高得畬, 唐英原 申請人:普誠科技股份有限公司