補差點數據儲存方法

2023-06-15 12:24:46

專利名稱：：補差點數據儲存方法
技術領域：
：本發明是關於在視頻編碼與解碼系統中的補差點運算(interpolation)，且特別是關於視頻編碼與解碼系統中的補差點數據儲存方法。
背景技術：
：在目前視頻編碼與解碼系統中，動態估計(motionestimation)具有1/2、1/4、1/8點的精準度，而此非整數點不存在於外部存儲器之中，為利用存在外部存儲器的整數點計算而來。所以在視頻編碼與解碼系統中，無論動態估計或動態才卜4嘗(motioncompensation),只要涉及非整悽t點的動態向量(motionvector),都會使用補差點運算。舉例而言，如圖1所示，在H.264視頻系統規格中，其1/2點位置像素(pixel)的值為利用六組係數(six-tap)的有限脈沖響應濾波器(finiteimpulseresponse,簡稱為FIR)所計算出來。圖l當中，白色方塊(如A、B、C、D等)表示整數點位置，而內含線條的方塊(如aa、bb、h、m等)表示需要補差點運算的1/2點位置。b點位置像素的值為算式(E-5F+20G+20H-5I+J)/32的值取整數值。h點位置像素的值為算式(A-5C+20G+20M-5R+T)/32的值取整數值。由上述算式得知，計算1/2點位置像素的值需4個乘法運算。以目前最為普遍的圖像格式CIF格式(commonintermediateformat,簡稱CIF)而言，每一畫面(frame)具有352*288個像素，計算CIF格式所有1/2點位置像素的值需(703*575-352*288(整數點))*4=1,211，396個乘法運算，約120萬個乘法運算；計算所有1/8點位置像素的值約需5000萬個乘法運算。其中1/4點位置像素的值可以利用加法器與位移器，因此不列於評估。此外，在CIF格式中，所有1/2點位置具有703*575-352*288(整數點)=302,846個像素，即表示儲存所有1/2點位置像素的值約需296Kbytes的存儲器空間；儲存所有1/8點位置像素的值約需6Mbytes的存儲器空間。由於補差點為利用外部存儲器儲存的整數點推演而來，若考慮外部存儲器頻寬為16位，則為了計算1/2、1/4及1/8點位置像素的值，各需抓取整個畫面的整數點數據，也就是要4爪取396*256*1.5/16=76032次。由上列敘述可知，在視頻編碼與解碼系統中，計算補差點的運算量與所需儲存補差點的存儲器空間所費極大，而且需多次讀取儲存整數點的外部存儲器。
發明內容本發明提供一種補差點數據儲存方法，利用暫存區(memorybuffer)存在於高速緩存(cache)中，藉以儲存計算過的補差點數據，可降低運算量與存儲器存取次數。本發明還提供一種補差點數據儲存方法，採用有效利用存儲器空間的儲存方式，藉以避免上述暫存區空間的浪費。本發明的一較佳實施例為利用動態向量差(motionvectordifference)的大小分布比例來分析圖像，藉以決定暫存區存在於高速緩存的空間大小。補差點為利用動態向量找到參考畫面的宏區塊(macroblock)，藉以計算出補差點，而這些動態向量對應參考畫面的宏區塊，在一般彼此間關聯性強的圖像會有較多重迭之處，因此利用此一暫存區儲存前些計算過的補差點，避免重複計算的運算量以及對外部存儲器讀取整數點位置像素的次數。本發明另一較佳實施例為該暫存區存在於高速緩存中的儲存方式。利用這些補差點對應於外部存儲器內的邏輯坐標的小數點部分，將暫存區劃分為多個區域，使用這些區域儲存非整數點位置的補差點數據。如此不需要保留整數點位置也能在暫存區內迅速搜尋補差點數據，兼具節省高速緩存空間與提高效率的優點。本發明還提供一種補差點數據儲存方法，包括判斷暫存區內是否儲存非整數點的補差點數據；若該暫存區已儲存該補差點數據，則提供該補差點數據；以及若該暫存區未儲存該補差點數據，則自存儲器讀取鄰近該非整數點的整數點數據，據以計算該補差點數據，然後將該補差點數據存入該暫存區。本發明還提供一種補差點數據儲存方法，包括將暫存區劃分為多個區域；以及使用該些區域儲存多個非整數點的補差點數據；其中，每一上述非整數點的每一邏輯坐標的小數部分與同一區域的另一上述非整數點的對應邏輯坐標的小數部分皆相同。本發明還提供一種補差點數據儲存方法，包括將暫存區劃分為多個區域；使用該些區域儲存多個非整數點的補差點數據，其中，每一上述非整數點的每一邏輯坐標的小數部分與同一區域的另一上述非整數點的對應邏輯坐標的小數部分皆相同；若特定非整數點的補差點數據已儲存於該暫存區，則直接提供該補差點數據；以及若該暫存區未儲存該特定非整數點的補差點數據，則自存儲器讀取鄰近該特定非整數點的整數點數據，據以計算該補差點數據，然後將該補差點數據存入該暫存區。為讓本發明的上述和其它目的、特徵和優點能更明顯易懂，下文特舉本發明的較佳實施例，並配合所附圖式，作詳細說明如下。圖1為一般視頻編碼與解碼系統的補差點運算示意圖。圖2為本發明一實施例的補差點數據暫存區示意圖。圖3及圖4為本發明一實施例的存儲地址旋轉示意圖。圖5為本發明一實施例的分區域儲存方法示意圖。[主要元件標號說明]200:高速緩存的暫存區201、202:宏方塊203:宏方塊的重迭部分310、320:補差點數據暫存區在參考畫面的對應邊界315、325:參考畫面的非整數點宏區塊500:補差點數據暫存區501、502、503:暫存區內的儲存區域511、521、531:暫存區內的非整數點數據MV1、MV2:動態向量具體實施例方式以下較佳實施例的說明以視頻編碼器或視頻解碼器為例。本實施例的視頻編碼器或視頻解碼器使用外部存儲器儲存參考畫面(referenceframe)整數點位置像素的數據，並使用內建的高速緩存做為暫存區，儲存之前計算過的非整數點位置像素的值。若欲降低系統運算量與外部存儲器存取頻率，可以利用容量較大的高速緩存儲存計算過的補差點數據，但是太大的高速緩存會造成電路面積與價格上的問題。因此本實施例使用相對較小的暫存區，例如32*32像素，加上存儲地址旋轉的觀念(細節後述)，就可以有效降低系統運算量與外部存儲器存取頻率，同時也不需要太大的高速緩存。在本實施例中，每當需要一個非整數點的補差點數據，會先判斷暫存區內是否儲存這個非整數點的補差點數據，若有儲存就直接取出使用，不用重複計算。反之，若暫存區沒儲存這個補差點數據，就從外部存儲器讀取鄰近上述非整數點的整數點數據，據以計算所需的補差點數據，然後將計算得出的補差點凝:據存入暫存區，以後就能重複使用。圖2繪示上述方法的一個範例。請參照圖2，200是用來儲存補差點數據的暫存區。假設目前畫面的某一宏區塊根據動態向量MV1對應到參考畫面的非整數點宏區塊201，而且根據動態向量MV2對應到參考畫面的非整數點宏區塊202。計算宏區塊201的補差點數據時，已將這些補差點邀:據存入暫存區200。當需要宏區塊202的補差點勒:據時，兩宏區塊重迭部分203的補差點數據可由暫存區200直接提供，不用重複計算。就宏區塊202而言，原本需要31*31*4=3844個乘法運算，扣掉重迭部分203之後只需31*4-16*2=368個乘法運算，節省了約90.4%的計算量。本實施例的暫存區大小不限定32*32像素。實際上，本實施例是先統計至少一個視步貞數據流(videobitstream)的動態向量差(MVD:motionvectordifference)的大小分布，然後根據上述大小分布決定暫存區的大小。所謂動態向量差的大小，在此定義為動態向量差的各坐標分量的最大值。例如某個動態向量差為(a，b),若a大於b,則此動態向量差的大小為a,否則為b。本實施例分析三個S見頻悽t據流，其名稱為News、Silent及Football,分別可以代表低頻、中頻及高頻的視頻圖像。視頻數據流News主要為播報新聞，其圖像移動變化小；視頻數據流Silent主要為手語動作，其圖像移動集中在部分區域，移動變化較News高；視頻數據流Footbal1為美式足球運動場景，運動員與球移動變化大。以上三個視頻數據流皆為CIF規格，分析結果如下列的表1所示。tableseeoriginaldocumentpage8表l各種視頻數據流的動態向量差分析統計表表l當中，絕大部分的動態向量差皆小於32像素，所以本實施例的暫存區大小設定為32*32像素。若集中處理高頻視頻，可使用64*64像素的暫存區；若集中處理低頻視頻，則16*16像素的暫存區就已經足夠。總之暫存區大小可視動態向量差的大小分布比例做調整，例如設定暫存區的最小邊長必須大於所有視頻數據流的所有動態向量差當中，一個預設比例的動態向量差。本實施例的暫存區是二維陣列，會對應到參考畫面中一個同等大小的區域，因為暫存區大小有限，難免會有非整數點的宏區塊超出暫存區邊界。請參照圖3。假設暫存區原本在參考畫面中的對應邊界為310,其左上角在參考畫面的邏輯坐標為(2.5，3.5),右下角在參考畫面的邏輯坐標為(34.5，35.5),以左上角為起點。邊界310可容納宏區塊315,其左上角在參考畫面的邏輯坐標為(18.5,19.5)，右下角在參考畫面的邏輯坐標為(34.5,35.5)。宏區塊315的非整數點邏輯坐標都是根據目前畫面的某一宏區塊與其動態向量計算得出。圖3當中，另一宏區塊325的左上角邏輯坐標為(20.5，21.5)，右下角邏輯坐標為(36.5，37.5)。對目前的邊界310而言，若要儲存宏區塊325的補差點數據，就有部分非整數點會超出範圍。在本實施例中，若有非整數點超出暫存區邊界，就調整暫存區的起點的邏輯坐標，使這個非整數點落入暫存區的新邊界。在圖3的範例，為了容納宏區塊325的補差點數據，會將暫存區的起點邏輯坐標從(2.5，3.5)移動至(4.5,5.5),也就是將暫存區邊界從310移動至320。補差點數據在暫存區內的存取是根據其真實坐標，暫存區內的真實坐標不同於參考畫面的邏輯坐標。每當暫存區的起點移動時，起點的邏輯坐標與真實坐標會同步移動，如此已儲存在暫存區內的補差點數據就不必因為起點移動而跟隨挪移。非整數點的真實坐標計算方法是，對上述非整數點的每一個邏輯坐標，計算此邏輯坐標減去起點的對應邏輯坐標加上起點的對應真實坐標的結果，以上述結果作為此非整數點的此邏輯坐標的對應真實坐標。上述的每一個邏輯坐標是指對應每一個坐標軸的不同子坐標，而上述不同子坐標之間的對應關係是指對應同一坐標軸。例如圖3的範例中，暫存區邊界310的起點邏輯坐標為(2.5,3.5)，起點真實坐標為[O]。宏區塊315左上角的x邏輯坐標為18.5，將其減去起點的x邏輯坐標2.5再加上起點的x真實坐標O，結果為16,此即為宏區塊315左上角的x真實坐標。同理，宏區塊315左上角的y邏輯坐標為19.5,將其減去起點的y邏輯坐標3.5再加上起點的y真實坐標O，結果為16,此即為宏區塊315左上角的y真實坐標。當暫存區邊界從310移動至320之後，新的起點邏輯坐標為(4.5,5.5),新的起點真實坐標為[2][2]。將宏區塊315左上角的邏輯坐標(18.5，19.5)減去起點邏輯坐標(4.5,5.5)再加上起點真實坐標[2][2],結果是同樣的真實坐標[16][16]。從上述結果可知，由於起點的邏輯坐標與真實坐標同步移動，同一非整數點在邊界移動前後的真實坐標相同，因此其補差點數據不必跟隨起點移動而在暫存區內挪移。移動起點位置之後，非整數點的真實坐標仍有可能超出暫存區界限，例如圖3當中，宏區塊325右下角的真實坐標為[34][34],超出最大可容許坐標[31][31]。此時本實施例的對策為存儲地址旋轉，如圖4所示，將真實坐標超出暫存區右側的非整數點儲存在暫存區左側，將真實坐標超出暫存區下端的非整數點儲存在暫存區上端，反之亦然。更精確地說，就是若有非整數點的對應某一坐標軸的真實坐標小於暫存區對應同一坐標軸的坐標下限，則將此真實坐標加上暫存區對應同一坐標軸的邊長。反之，若有非整數點的對應某一坐標軸的真實坐標大於暫存區對應同一坐標軸的坐標上限，則將此真實坐標減去暫存區對應同一坐標軸的邊長。例如宏區塊325右上角的邏輯坐標為(36.5，21.5)，真實坐標為[34][18],其x真實坐標超出暫存區的x軸上限31，必須減去暫存區的x軸邊長32，然後根據調整後的真實坐標[2][18]在暫存區內作存取。同理，宏區塊325左下角的邏輯坐標為(20.5，37.5),真實坐標為[18][34]，其y真實坐標超出暫存區的y軸上限31，必須減去暫存區的y軸邊長32，然後根據調整後的真實坐標[18][2]在暫存區內作存取。以下請參照圖5,在圖5的暫存區500當中，除了非整數點(以x標示)以外，也保留了整數點的儲存位置(以o標示)。這是為了便於在暫存區500之內搜尋非整數點的補差點數據，然而這樣會浪費存儲空間。反之，若為了節省高速緩存而不保留整數點位置，則需要較複雜的尋址運算以決定非整數點的儲存位置。為了兼顧存儲空間與運算效率，本實施例採用如圖5所示的方法，將暫存區劃分為多個區域，然後將非整數點的補差點數據分散儲存在上述區域。區域501儲存x坐標為1/2,y坐標為整數點的非整數點數據，例如511。區域502儲存y坐標為1/2，x坐標為整數點的非整數點數據，例如521。區域503儲存x、y坐標皆為1/2的非整數點數據，例如531。如此每個區域中的非整數點都呈規律排列，不僅容易尋址，也能避免整數點空間的存儲浪費。圖5的分區儲存方法是以1/2點為例，其實上述的分區儲存方法也適用於其它種非整數點，例如1/4點或1/8點。1/4點的暫存區應分為42-1=15個區域，1/8點的暫存區應分為82-1=63個區域，依此類推。一般原則是每一個區域中，每一個非整數點對應每一個坐標軸的邏輯坐標的小數部分，與同一區域的另一個非整數點的對應同一坐標軸的邏輯坐標的小數部分皆相同。例如圖5的區域502中，每一個非整數點的x邏輯坐標小數部分皆為0,而且每一個非整數點的y邏輯坐標小數部分皆為0.5。此外，每一個區域的非整數點的邏輯坐標小數部分所構成的集合各不相同。例如圖5的範例中，區域501的非整數點的邏輯坐標小數部分的集合為{0.5，0},區域502為{0，0,5}，區域503為(0.5,0.5},三個區域的集合各不相同。以下說明本實施例的實驗結果。本實施例的實驗環境為H.264解碼端，分別測試CIF格式的視頻數據流News、Silent以及Football,比較國際標準糹且織(ISO:InternationalStandardsOrganization)的參考石馬JM8.2以及本實施例的方法，評估計算1/2點位置像素的值所需的乘法計算量(乘法運算次數)與每一畫面的存儲器存取量。實驗結果如以下的表2、表3及表4所示。從下列表格可看出，本實施例和已知的JM8.2相比，確實可降^f氐乘法計算量與存儲器存取頻率。tableseeoriginaldocumentpage10表2CIF視頻數據流News的實驗結果Stableseeoriginaldocumentpage11表4CIF視頻數據流Football的實驗結果綜上所述，本實施例採用相對較小的暫存區以儲存先前計算的補差點數據，可降低補差點的運算量，降低自外部存儲器讀取整數點數據的頻率，而且不需要太大的高速緩存。本實施例也採用分區域儲存非整數點數據的方式，以維持簡易的尋址運算，並且避免浪費暫存區空間。本發明的應用不限於視頻編碼與解碼，任何需要重複計算補差點的運算系統皆可應用。計算補差點所需的整數點數據不限於取自參考畫面，也可以取自二維以上的任意數據陣列。相對於上述的運算系統，整數點數據除了儲存在外部存儲器，也可以儲存在內建的一般存儲器。雖然本發明已以較佳實施例揭露如上，然其並非用以限定本發明，任何本領域技術人員，在不脫離本發明的精神和範圍內，當可作些許的更動與潤飾，因此本發明的保護範圍當視所附的權利要求範圍所界定者為準。權利要求1.一種補差點數據儲存方法，包括將暫存區劃分為多個區域；以及使用該些區域儲存多個非整數點的補差點數據；其中，每一上述非整數點的每一邏輯坐標的小數部分與同一區域的另一上述非整數點的對應邏輯坐標的小數部分皆相同。2.根據權利要求1所述的補差點數據儲存方法，其中，每一上述非整數點的每一邏輯坐標的小數部分的集合與不同區域的另一上述非整數點的每一邏輯坐標的小數部分的集合皆不相同。3.根據權利要求1所述的補差點數據儲存方法，其中該補差點數據儲存方法應用於^L頻編碼或^L頻解碼。4.根據權利要求3所述的補差點數據儲存方法，還包括統計至少一視頻數據流的動態向量差的大小分布；以及才艮據上述大小分布決定該暫存區的大小。5.—種補差點數據儲存方法，包括-.將暫存區劃分為多個區域；使用該些區域儲存多個非整數點的補差點數據，其中，每一上述非整數點的每一邏輯坐標的小數部分與同一區域的另一上述非整數點的對應邏輯坐標的小數部分皆相同；若特定非整數點的補差點數據已儲存於該暫存區，則直接提供該補差點數據；以及若該暫存區未儲存該特定非整數點的補差點數據，則自存儲器讀取鄰近該特定非整數點的整數點數據，據以計算該補差點數據，然後將該補差點數據存入該暫存區。6.根據權利要求5所述的補差點數據儲存方法，其中，該暫存區儲存的每一上述非整數點的每一邏輯坐標的小數部分的集合與不同區域的另一上述非整數點的每一邏輯坐標的小數部分的集合皆不相同。7.根據權利要求5所述的補差點數據儲存方法，還包括若該特定非整數點超出該暫存區的邊界，則調整該暫存區的起點的邏輯坐標，使該特定非整數點落入該暫存區的邊界。8.根據權利要求7所述的補差點數據儲存方法，還包括對該特定非整數點的每一邏輯坐標，計算該邏輯坐標減去該起點的對應邏輯坐標加上該起點的對應真實坐標的結果，以上述結果作為該特定非整數點的該邏輯坐標的對應真實坐標；若該特定非整數點的該真實坐標小於該暫存區的對應下限，則將該真實坐標加上該暫存區的對應邊長；若該特定非整數點的該真實坐標大於該暫存區的對應上限，則將該真實坐標減去該暫存區的對應邊長；以及使用該特定非整數點的上述真實坐標存取該暫存區。9.根據權利要求5所述的補差點數據儲存方法，其中該補差點數據儲存方法由運算系統執行，該暫存區儲存於該運算系統的高速緩存，儲存該些整數點數據的該存儲器為該運算系統的外部存儲器。10.根據權利要求9所述的補差點數據儲存方法，其中該運算系統為視頻編碼器或視頻解碼器，而且該補差點數據儲存方法還包括統計至少一視頻數據流的動態向量差的大小分布；以及才艮據上述大小分布決定該暫存區的大小。全文摘要本發明提供一種補差點數據儲存方法，運用存在於高速緩存中的暫存區，以及存儲重迭記錄的觀念，儲存計算過的補差點數據，避免重複計算，藉以降低系統運算量並降低自外部存儲器讀取整數點來計算補差點的次數。此外本發明提供此暫存區的數據儲存方式，利用存儲地址旋轉的觀念，以儲存超出暫存區邊界的補差點數據。本發明亦根據補差點坐標小數部分的不同組合，將補差點數據分多個區域儲存，藉以節省暫存區存儲空間，而且便於在暫存區內搜尋補差點數據。文檔編號H04N7/32GK101568032SQ20091014106公開日2009年10月28日申請日期2006年10月17日優先權日2006年10月17日發明者高榮揚申請人:財團法人工業技術研究院