在視頻壓縮系統中進行運動估測的方法及相關裝置的製作方法

2023-05-24 17:48:21

專利名稱：在視頻壓縮系統中進行運動估測的方法及相關裝置的製作方法
技術領域：
本發明涉及一種用於一視頻壓縮系統中進行運動估測的方法及相關裝置，特別涉及一種使用不同於已知技術的成本函數進行運動估測的方法及相關裝置。
背景技術：
近幾年來，多媒體技術蓬勃的發展，而隨著多媒體技術的發展，有越來越多種的視頻壓縮標準陸續被提出。舉例來說，各種版本的MPEG技術即是用來以數字形式儲存以及傳輸視頻數據的壓縮標準。至於其它的視頻壓縮標準則還有ITU H.261、H.263以及ISO 10918等等。
MPEG所提出的國際視頻標準定義了一種用來壓縮數字視頻的規格。動態的視頻是由一連串的畫面(picture)所組成，而每一個畫面可以看成是由許多像素(pixel)所組成的二維數組，每一個畫面亦可以稱為動態視頻中一個單一的幀(frame)。而在MPEG所提出的國際視頻標準中，是定義了四種不同種類的畫面，分別是I畫面，不參考其它的畫面而編碼得出；P畫面，參考之前的I畫面或P畫面，經由運動估測(motion estimation)而編碼得出；B畫面，參考之前以及之後的I畫面或P畫面，經由運動估測而編碼得出；以及D畫面，使用於快速前搜模式(fast forward search mode)之中。
而使用上述各種國際視頻標準的視頻壓縮系統通常都會使用到以區塊(block)或是宏區塊(macroblock)為基礎的運動估測技術，以消除掉時間上的重複性(temporal redundancy)。在進行運動估測時，對於一目前畫面(current picture)中的一目前編碼區塊，視頻壓縮系統會從一目標畫面(target picture)中找出與該目前編碼區塊最相似的一個最吻合區塊(bestmatching block)。此時對於目前編碼區塊，視頻壓縮系統只需儲存(或傳送)計算出的運動向量(motion vector)以及殘餘值(residual)，即可代表該目前編碼區塊中所包含的信息(殘餘值是用來表示目前編碼區塊與最吻合區塊間像素值的差異狀況)。
而在已知技術中，當視頻壓縮系統欲從一搜尋區域(search range)內找尋一個最吻合區塊時，通常會使用一種稱為「絕對差異總和」(sum ofabsolute difference)的成本函數(cost function)，如以下所示SAD(x,y)=i=i0i1j=j0j1|Ci,j-Pi+x,j+y|]]>其中，(x，y)為搜尋區域內的一個候選運動向量，(i1-i0)×(j1-j0)為目前編碼區塊的大小，Ci，j為目前編碼區塊內的一像素，Pi+x，j+y則為目標畫面中搜尋區域內的一像素。
已知技術的視頻壓縮系統會從搜尋區域中，找出一個可以使得上述成本函數達到最小值的一個候選運動向量(x，y)，作為目前編碼區塊的最適運動向量(x1，y1)。這樣的作法主要是為了要找出一個具有最小殘餘值的最吻合區塊，如此一來即可使得對於殘餘值達到較好的壓縮程度。但是用上述方法找出的最適運動向量(x1，y1)卻不見得可以達到較好的壓縮程度，因此美國第5,847,776號的專利案件提出了另一種成本函數，在尋找最適運動向量的過程中，除了考慮上述的絕對差異總和之外，亦將運動向量的大小列入考慮，如此一來即可在找出的最適運動向量以及相對應的殘餘值間取得平衡。
然而，有很多種視頻壓縮系統在對殘餘值進行壓縮時，都會使用離散餘弦轉換(discrete cosine transform，DCT)的算法，將位於空間領域(spatialdomain)的殘餘值轉換至頻率領域(frequency domain)。然後使用相對應的量化矩陣(quantization matrix)以及可隨系統選定的位率(bit rate)改變的量化步長(quantization step)Qp，對位於頻率領域的殘餘值進行量化程序。因為量化後的矩陣是二維矩陣，所以系統還會使用鋸尺掃瞄(zig-zagscan)或是交錯掃瞄(alternate scan)的方式將量化後的二維數據掃描成一維的數據，最後再進行可變長度編碼(Variable length coding)的運算。
在進行可變長度編碼的運算時，若位於頻率領域的殘餘值的頻率分布範圍越小，最後編碼出來的殘餘值的編碼長度(code length)通常就會越短(這也就代表了對於殘餘值達到了較好的壓縮程度)。但是使用已知技術或是美國第5,847,776號的專利案件所提出的方法，所找出的最吻合區塊不見的有辦法使得位於頻率領域的殘餘值具有小的頻率分布範圍。此時即使找出的最吻合區塊可以使得空間領域上的殘餘值具有最小的絕對差異總和，但是經過離散餘弦轉換、量化程序、鋸尺掃瞄(或是其它的掃瞄方式)、以及可變長度編碼等等的運算之後，所得到的殘餘值卻不見得會有最短的編碼長度，故不見得可以達到最好的壓縮效果。這是已知技術所面臨的一個主要問題。

發明內容
因此本發明的主要目的在於提供一種使用不同於已知技術的成本函數(cost function)的方法及相關裝置，以解決上述已知技術所面臨的問題。
根據本發明的一申請專利範圍，是揭露一種用於一視頻壓縮系統中進行運動估測的方法，該視頻壓縮系統將一目前畫面分成多個區塊，該方法包含有以下步驟對於該目前畫面中的一目前編碼區塊，逐步檢視一搜尋區域內的多個候選運動向量(x，y)，其中該目前編碼區塊包含有(i1-i0)×(j1-j0)個像素；對於每一個候選運動向量(x，y)，計算一成本函數的值；以及將該搜尋區域內可使該成本函數得出最小值的候選運動向量(x，y)設為該目前編碼區塊的最適運動向量(x1，y1)。該成本函數如以下所示CF(x,y)=i=i0i1j=j0j1{|Ci,j-Pi+x,j+y|+h(Qp,Ci,j,Pi+x,j+y)}]]>其中Ci，j為該目前編碼區塊內的一像素，Pi+x，j+y為一目標畫面中該搜尋區域內的一像素，Qp則為一量化步長。
根據本發明的又一申請專利範圍，是揭露一種用於一視頻壓縮系統中進行運動估測的裝置，該視頻壓縮系統將一目前畫面分成多個區塊，對於該目前畫面中的一目前編碼區塊，該裝置可自一搜尋區域內多個候選運動向量(x，y)中決定出一最適運動向量(x1，y1)，其中該目前編碼區塊中包含有(i1-i0)×(j1-j0)個像素，該裝置包含有一絕對差異計算單元，用來計算出|Ci，j-Pi+x，j+y|的值，其中Ci，j為該目前編碼區塊中的一像素，Pi+x，j+y為一目標畫面中該搜尋區域內的一像素；一空間變化計算模塊，用來計算出一函數h(Qp，Ci，j，Pi+x，j+y)的值，其中Qp為一量化步長；以及一運動向量決定模塊，耦合於該絕對差異計算單元與該空間變化計算模塊，用來計算一成本函數的值，並將該搜尋區域內的可使該成本函數得出最小值的候選運動向量(x，y)設定為該目前編碼區塊的最適運動向量(x1，y1)。該成本函數如以下所示CF(x,y)=i=i0i1j=j0j1{|Ci,j-Pi+x,j+y|+h(Qp,Ci,j,Pi+x,j+y)}]]>本發明的一個優點在於，由於所使用的成本函數會受到該目前編碼區塊相對於一候選運動向量(x，y)所對應到的區塊的像素值差異的變化狀況所影響，故使用本發明所提出的方法及相關裝置可以確保計算出的最適運動向量相對應的殘餘值經過處理之後可以有較好的壓縮效率。
附圖簡述

圖1為本發明所提出的方法的實施例流程圖。
圖2為本發明所提出的裝置的實施例功能方塊圖。
圖式的符號說明200裝置220絕對差異計算單元240空間變化計算模塊242第一計算單元244第二計算單元246乘法器260運動向量決定模塊262加法器264累加器270決定單元272比較器274儲存器具體實施方式
請參閱圖1，圖1為本發明所提出的方法的實施例流程圖。本發明所提出的方法可用於一視頻壓縮系統中，以進行運動估測，該視頻壓縮系統將一目前畫面分成多個區塊。以下將詳述圖一中的各步驟步驟110對於該目前畫面中的一目前編碼區塊，逐步檢視一搜尋區域內的多個候選運動向量(x，y)，其中該目前編碼區塊包含有(i1-i0)×(j1-j0)個像素。
步驟120對於每一個候選運動向量(x，y)，計算以下的成本函數CF(x,y)=i=i0i1j=j0j1{|Ci,j-Pi+x,j+y|+h(Qp,Ci,j,Pi+x,j+y)}]]>
其中Ci，j為該目前編碼區塊內的一像素，Pi+x，j+y為一目標畫面中該搜尋區域內的一像素，Qp則為一量化步長(quantization step)。
步驟130將該搜尋區域內可使該成本函數得出最小值的候選運動向量(x，y)設為該目前編碼區塊的最適運動向量(x1，y1)。
本發明的方法與已知技術所使用的方法有一個最大的不同點，就是本發明方法所使用的成本函數不僅考慮到了絕對差異總和(即|Ci，j-Pi+x，j+y|項)，亦考慮到了相關於量化步長Qp以及絕對差異總和分布情形的項次(即h(Qp，Ci，j，Pi+x，j+y)項)。
舉例來說，函數h(Qp，Ci，j，Pi+x，j+y)可以表示為K×f(Qp)×g(|Ci，j-Pi+x，j+y|)，而K為一常數，函數f(Qp)則為一單調增加函數(monotonic increasingfunction)，即當Qp的值越大時，函數f(Qp)的值也就會越大，此時h(Qp，Ci，j，Pi+x，j+y)對於成本函數值的影響就會越重要。至於函數g(|Ci，j-Pi+x，j+y|)，則是用來大致計算出目前編碼區塊相對於此時的候選運動向量(x，y)所對應到的區塊的像素差異值的變化狀況(即反映了位於頻率領域的殘餘值的分布範圍)，當i=i0i1j=j0j1g(|Ci,j-Pi+x,j+y|)]]>的值越小，通常就代表了使用此一候選運動向量(x，y)會造成計算出的殘餘值經由散餘弦轉換、量化程序、鋸尺掃瞄(或是其它的掃瞄方式)、以及可變長度編碼等等的運算之後可以達到較好的壓縮效率。
以下則舉出函數g(|Ci，j-Pi+x，j+y|)的一個例子 至於ad_max與ad_min則如以下式子所示 在上述的例子中，每當一組(i，j)值所對應到函數g(|Ci，j-Pi+x，j+y|)的值被計算出來之後，ad_max與ad_min的值即可進行更新，以在計算後續的(i，j)的組合所對應到函數g(|Ci，j-Pi+x，j+y|)的值時使用。
以大小為2×3的區塊為例，此時(i1-i0)＝2、(j1-j0)＝3，若在該搜尋區域內只有兩個候選運動向量，分別對應到一第一區塊合一第二區塊；該目前編碼區塊相對於第一區塊像素差異的絕對值為{8，9，6，8，7，6}，該目前編碼區塊相對於第二區塊像素差異的絕對值為{5，10，4，22，0，0}。使用已知技術以絕對差異總和做為成本函數的計算方法，對第一區塊及第二區塊算出的成本函數值分別會是第一區塊8+9+6+8+7+6＝44第二區塊5+10+4+22＝41故此時已知技術會以第二區塊作為該目前編碼區塊的最吻合區塊。
然而若使用上述實施例的計算方法，假設K＝1、f(Qp)＝1，則對第一區塊及第二區塊算出的成本函數值則分別會是第一區塊[8+0]+[9+(9-8)]+[6+(8-6)]+[8+0]+[7+0]+[6+0]＝47第二區塊[5+0]+[10+(10-5)]+[4+(5-4)]+[22+(22-10)]+
+
＝63很明顯的，使用上述實施例所提出的計算方式，第一區塊會被選擇為該目前編碼區塊的最吻合區塊，這點與已知技術具有明顯的不同。
而若使用上述實施例所提出的函數g(|Ci，j-Pi+x，j+y|)，則本發明所提出的成本函數可以化簡為CF(x,y)=i=i0i1j=j0j1|Ci,j-Pi+x,j+y|+Kf(Qp)(ad_max-ad_min)]]>其中ad_max與ad_min分別為從(i，j)＝(i0，j0)到(i，j)＝(i1，j1)之間|Ci，j-Pi+x，j+y|的最大值以及最小值。
也就是說，使用本發明的方法，若是該目標畫面中一候選運動向量(x，y)所對應到的區塊相對於該目前編碼區塊的像素差異值的分布範圍越大(在上述的例子中即為最大值與最小值間的差異越大)，則計算成本函數所得到的值也就會越大，而這樣的區塊就較不容易被選擇作為該目前編碼區塊的最吻合區塊。
請參閱圖2，圖2為本發明用於一視頻壓縮系統中進行運動估測的裝置200的示意圖。該視頻壓縮系統將一目前畫面分成多個區塊，對於該目前畫面中的一目前編碼區塊，裝置200可自一搜尋區域內多個候選運動向量(x，y)中決定出一最適運動向量(x1，y1)，其中該目前編碼區塊中包含有(i1-i0)×(j1-j0)個像素。在圖2中，裝置200包含有一絕對差異計算單元220，用來計算出|Ci，j-Pi+x，j+y|的值，其中Ci，j為該目前編碼區塊中的一像素，Pi+x，j+y為一目標畫面中該搜尋區域內的一像素；一空間變化計算模塊240，用來計算出一函數h(Qp，Ci，j，Pi+x，j+y)的值，其中Qp為一量化步長；以及一運動向量決定模塊260，耦合於絕對差異計算單元220與空間變化計算模塊240，用來計算以下的成本函數CF(x,y)=i=i0i1j=j0j1{|Ci,j-Pi+x,j+y|+h(Qp,Ci,j,Pi+x,j+y)}]]>並將該搜尋區域內的可使該成本函數得出最小值的候選運動向量(x，y)設定為該目前編碼區塊的最適運動向量(x1，y1)。
舉例來說，如同之前所述，函數h(Qp，Ci，j，Pi+x，j+y)可以表示為K×f(Qp)×g(|Ci，j-Pi+x，j+y|)，故於裝置200中，空間變化計算模塊240中包含有一第一計算單元242，用來計算出函數g(|Ci，j-Pi+x，j+y|)的值；一第二計算單元244，用來計算出函數f(Qp)的值；以及一乘法器246，耦合於第一計算單元242與第二計算單元244，用來計算出K×f(Qp)×g(|Ci，j-Pi+x，j+y|)的值。
至於運動向量決定模塊260則包含有一加法器262，耦合於絕對差異計算單元220與空間變化計算模塊240，用來計算出|Ci，j-Pi+x，j+y|+h(Qp，Ci，j，Pi+x，j+y)的值；一累加器264，耦合於加法器262，用來出計算該成本函數的值；以及一決定單元270，耦合於累加器246，用來將該搜尋區域內可使該成本函數得出最小值的候選運動向量(x，y)設定為該目前編碼區塊的最適運動向量(x1，y1)。
而為了使決定單元270具有儲存成本函數最小值的功能以及比較不同候選運動向量所計算出成本函數值的大小的功能，在圖2中，決定單元270則包含有一比較器272，耦合於累加器264，用來輸出最適運動向量(x1，y1)；以及一儲存器274，耦合於272比較器，用來儲存該成本函數出現過的最小值。
使用本發明所提出的方法及相關裝置，可以依據不同於已知技術的成本函數計算出一目前編碼區塊於一搜尋區域內的最適運動向量。由於本發明所使用的成本函數會受到該目前編碼區塊相對於一候選運動向量(x，y)所對應到的區塊的像素值差異的變化狀況所影響，故使用本發明所提出的方法及相關裝置可以確保計算出的最適運動向量相對應的殘餘值經過處理(即上述的散餘弦轉換、量化程序、鋸尺掃瞄、可變長度編碼等等的運算)之後可以有較好的壓縮效率。
以上所述僅為本發明的較佳實施例，凡依本發明申請專利範圍所做的均等變化與修飾，皆應屬本發明專利的涵蓋範圍。
權利要求
1.一種用於一視頻壓縮系統中進行運動估測的方法，該視頻壓縮系統將一目前畫面分成多個區塊，該方法包含有以下步驟對於該目前畫面中的一目前編碼區塊，逐步檢視一搜尋區域內的多個候選運動向量(x，y)，其中該目前編碼區塊包含有(i1-i0)×(j1-j0)個像素；對於每一個候選運動向量(x，y)，計算以下的成本函數CF(x,y)=i=i0i1j=j0j1{|Ci,j-Pi+x,j+y|+h(Qp,Ci,j,Pi+x,j+y)}]]>其中，Ci，j為該目前編碼區塊內的一像素，Pi+x，j+y為一目標畫面中該搜尋區域內的一像素，Qp則為一量化步長；以及將該搜尋區域內可使該成本函數得出最小值的候選運動向量(x，y)設為該目前編碼區塊的最適運動向量(x1，y1)。
2.如權利要求1所述的方法，其中，函數h(Qp，Ci，j，Pi+x，j+y)可以表示為K×f(Qp)×g(|Ci，j-Pi+x，j+y|)，而K為一常數、函數f(Qp)為一單調增加函數。
3.如權利要求1所述的方法，其中，若其它條件不變，則當Qp的值越大時，函數h2(Qp，Ci，j，Pi+x，j+y)的值即會越大。
4.一種用於一視頻壓縮系統中進行運動估測的裝置，該視頻壓縮系統將一目前畫面分成多個區塊，對於該目前畫面中的一目前編碼區塊，該裝置可自一搜尋區域內多個候選運動向量(x，y)中決定出一最適運動向量(x1，y1)，其中該目前編碼區塊中包含有(i1-i0)×(j1-j0)個像素，該裝置包含有一絕對差異計算單元，用來計算出|Ci，j-Pi+x，j+y|的值，其中Ci，j為該目前編碼區塊中的一像素，Pi+x，j+y為一目標畫面中該搜尋區域內的一像素；一空間變化計算模塊，用來計算出一函數h(Qp，Ci，j，Pi+x，j+y)的值，其中Qp為一量化步長；以及一運動向量決定模塊，耦合於該絕對差異計算單元與該空間變化計算模塊，用來計算以下的成本函數CF(x,y)=i=i0i1j=j0j1{|Ci,j-Pi+x,j+y|+h(Qp,Ci,j,Pi+x,j+y)}]]>並將該搜尋區域內的可使該成本函數得出最小值的候選運動向量(x，y)設定為該目前編碼區塊的最適運動向量(x1，y1)。
5.如權利要求4所述的裝置，其中，函數h(Qp，Ci，j，Pi+x，j+y)可以表示為K×f(Qp)×g(|Ci，j-Pi+x，j+y|)，而K為一常數、函數f(Qp)為一單調增加函數。
6.如權利要求5所述的裝置，其中，該空間變化計算模塊包含有一第一計算單元，用來計算出函數g(|Ci，j-Pi+x，j+y|)的值；一第二計算單元，用來計算出函數f(Qp)的值；以及一乘法器，耦合於該第一計算單元與該第二計算單元，用來計算出K×f(Qp)×g(|Ci，j-Pi+x，j+y|)的值。
7.如權利要求4所述的裝置，其中，該運動向量決定模塊包含有一加法器，耦合於該絕對差異計算單元與該空間變化計算模塊，用來計算出|Ci，j-Pi+x，j+y|+h(Qp，Ci，j，Pi+x，j+y)的值；一累加器，耦合於該加法器，用來出計算該成本函數的值；以及一決定單元，耦合於該累加器，用來將該搜尋區域內可使該成本函數得出最小值的候選運動向量(x，y)設定為該目前編碼區塊的最適運動向量(x1，y1)。
8.如權利要求7所述的裝置，其中，該決定單元包含有一比較器，耦合於該累加器，用來輸出該最適運動向量(x1，y1)；以及一儲存器，耦合於該比較器，用來儲存該成本函數出現過的最小值。
9.如權利要求4所述的裝置，其中，若其它條件不變，則當Qp的值越大時，函數h(Qp，Ci，j，Pi+x，j+y)的值即會越大。
全文摘要
本發明揭露了一種使用於一視頻壓縮系統中進行運動估測的方法及相關裝置，可使用不同於已知技術的成本函數(cost function)計算出一目前編碼區塊的一最適運動向量。本發明所使用的成本函數不僅考量到傳統的「絕對差異總和」，亦考量到量化步長、該目前編碼區塊相對於一目標畫面中一搜尋區域內的區塊間，像素差異值的變化狀況，故使用本發明的成本函數可以使找出的最適運動向量所對應到的殘餘值經過處理後可以有較好的壓縮效率。
文檔編號H04N7/32GK1622635SQ200310117949
公開日2005年6月1日 申請日期2003年11月26日 優先權日2003年11月26日
發明者何鎮在 申請人:聯發科技股份有限公司