用於視頻壓縮的增強的基於塊的運動估計算法的製作方法

2023-06-09 08:14:41

專利名稱：用於視頻壓縮的增強的基於塊的運動估計算法的製作方法
技術領域：
本發明通常涉及用於數位訊號壓縮、編碼和表示的方法和系統，並且更加確切地說，本發明涉及使用多幀運動估計(ME)的方法和系統。本發明進一步涉及一種電腦程式產品，諸如記錄媒體，承載可以由計算設備讀取的程序指令，以使得所述計算設備執行根據本發明的一種方法。
背景技術：
由於由現代多媒體應用使用的原始數字視頻數據(或者圖像序列)的巨大尺寸，必須對這種數據進行壓縮以便可以傳輸和存儲這些數據。存在許多重要視頻壓縮標準，包括ISO/IEC MPEG-1、MPEG-2、MPEG-4標準和ITU-T H.261、H.263、H.264標準。ISO/IEC MPEG-1/2/4標準廣泛地運用於娛樂業以發行電影、包括視頻壓縮光碟或者VCD(MPEG-1)的數字視頻廣播、數字視頻光碟或者數字多用途光碟或者DVD(MPEG-2)、可記錄DVD(MPEG-2)、數字視頻廣播、數字視頻廣播或者DVB(MPEG-2)、視頻點播或者VOD(MPEG-2)、在US中的高清晰度電視或者HDTV(MPEG-2)等等。MPEG-4標準比MPEG-2更加先進，可以在較低的比特率下實現高質量視頻，這使得其非常適合於網際網路、數字無線網絡(例如3G網絡)、多媒體信息服務(來自3GPP的MMS標準)等等上的視頻信息流。MPEG-4被下一代高清晰度DVD(HD-DVD)標準和MMS標準所接受。ITU-TH.261/3/4標準設計用於低延遲電視電話和視頻會議系統。早期的H.261標準設計為在p*64kbit/s下工作，p＝1，2，...，31。後期的H.263標準非常成功，被廣泛地用於現代電視會議系統，並且用於寬帶網絡和無線網絡中的視頻信息流，其中無線網絡包括在2.5G和3G網絡以及其他網絡中的多媒體信息服務(MMS)。最新標準，H.264(也稱作MPEG-4版本10，或者MPEG-4 AVC)是當前最新技術水平的視頻壓縮標準。它如此強大以至MPEG決定與Joint Video Team(JVT)的框架中的ITU-T聯合開發。新的標準在ITU-T中稱為的H.264，並且被稱作MPEG-4高級視頻編碼(MPEG-4AVC)，或者MPEG-4版本10。H.264用於HD-DVD標準、直接視頻廣播(DVB)標準並且可能用於MMS標準。基於H.264，當前在中國正在開發稱作視聽標準(AVS)的相關標準。AVS 1.0設計用於高清晰度電視(HDTV)。AVS-M設計用於移動應用。H.264具有超過MPEG-1/2/4及H.261/3標準的目標和主觀的視頻質量。除使用整數4×4離散餘弦變換(DCT)代替傳統的8×8 DCT以外，H.264[1]的基本編碼算法類似於H.263或者MPEG-4，並且還有額外的特點，包括I幀的幀間預測模式、用於運動估計/補償的多種塊大小以及多種參考坐標系、用於運動估計的四分之一像素精度、迴路內去塊效應(in-loopdeblocking)濾波器，內容自適應二進位算術編碼(context adaptivebinary arithmetic coding)，等等。
運動估計是大多數視頻壓縮標準(諸如MPEG-1/2/4和H.261/3/4)的核心部分，其充分利用時間冗餘度，因此其性能直接影響視頻編碼系統的壓縮效率、主觀視頻質量以及編碼速度。
在塊匹配運動估計(BMME)中，在ME中，對當前塊和參考塊之間的失真的最通用的測量是絕對差值的和(SAD)，對於一個N×N塊而言，定義為SAD(mvx,mvy)=m=0,n=0N-1|Ft(x+m,y+n)-Ft-1(x+m+mvx,y+n+mvy)|]]>其中Ft是當前幀，Ft-1是標準幀，(mvx，mvy)表示當前運動矢量(MV)。對於寬度＝X，高度＝Y，並且塊大小＝N×N的幀而言，在搜索範圍±W中需要對SAD進行評估以查找最優運動矢量的搜索點總數等於(XN)(YN)(2W+1)2,]]>對於X＝352，Y＝288，N＝16並且W＝32的情況下，其等於1673100。這是在視頻編碼器中消耗巨大計算能力的巨大數值。已經提出了許多快速算法[2]-[9]來減少在ME中搜索點的數目，例如三步搜索(TSS)[11]，2D對數搜索[12]，新三步搜索(NTSS)[3]，MVFAST[7]，以及PMVFAST[2]。MVFAST和PMVFAST顯著地優於前三個算法，因為它們使用中值運動矢量預測器作為搜索中心執行中心偏離ME，由此通過平滑運動矢量場降低了MV編碼的位的數目。
PMVFAST算法(其是對MVFAST及其它快速算法的重要改進，並且因而被MPEG標準[10]所接受)最初考慮一組MV預測器，包括中值、零點、左邊、頂部、右上方的和先前的共位(co-located)MV預測器。圖1舉例說明了當前塊、左塊、頂部塊、右上方塊、右右上方塊、以及右塊(其是″未來塊″，即，在當前塊之後被處理的塊)的位置。它計算每個預測的SAD代價。在後來的發展中，對PMVFAST進行修改以計算RD(速率失真)代價[13]來替代使用以下代價函數的SAD代價J(m，λmotion)＝SAD(s，c(m))+λmotion(R(m-p))(1)其中s是原始視頻信號，c是參考視頻信號，m是當前MV，p是當前塊的中值MV預測器，λmotion是Lagrange乘法器，R(m-p)表示用於編碼運動信息的位。在PMVFAST中的下一步驟是選擇具有最小代價的MV預測器，並且根據從MV預測器獲得的最小代價的值來執行數量大菱形搜索(diamond search)或者小菱形搜索。
在定義當前視頻編碼標準中獨立但是重要問題是使用亞像素預定矢量，包括半像素、1/4像素或者可能甚至1/8像素運動矢量，其提供對運動的更加精確的描述，並且可以提供整像素運動估計的大約1dB的PSNR增益。採用半像素精度，運動矢量可以採用等間距位置值，諸如0.0，0.5，1.0，1.5，2.0等等。採用1/4像素精度，運動矢量可以採用諸如0.00，0.25，0.50，0.75，1.00，1.25，1.50，1.75，2.00等等之類的位置值。採用1/8像素精度，運動矢量可以採用諸如0.000，0.125，0.250，0.375，0.500，0.625，0.750，0.875，1.000，1.125，1.250，1.375，1.500，1.625，1.750，1.875，2.000等等之類的位置值。
眾所周知，運動矢量分布趨向於中心偏移，這意味著運動矢量趨向於非常地接近於(0，0)。在圖6(a)中示出了這種情況，其示出為(0，0)MV使用完全搜索(FS)算法的在Foreman序列中的運動矢量分布。此外，如圖6(b)所示，運動矢量分布還向中值預測器(中值MV)偏移，它是在圖1中示出的運動矢量左塊、頂部塊和右上方塊的中值。此外，如圖6(c)所示，運動矢量還向在當前幀中的相鄰運動矢量(leftMV，topMV，topRightMV)和先前幀中所設置的運動矢量(preMV)偏移，如圖6(d)所示。這些可以都是用於當前矢量的運動矢量的可考慮的預測器，並且它們可以被用於PMVFAST。

發明內容
本發明目的是提供用於運動估計的新的並且有益的技術，其適用於數位訊號壓縮、編碼和表達的方法和系統。
特別是，本發明設法提供新的並且有益的有效運動估計技術，其可以例如應用在MPEG-1、MPEG-2、MPEG-4、H.261、H.263、H.264或AVS或者其它相關視頻編碼標準中。
本發明第一方面基於這樣的實現PMVFAST算法的運動估計儘管與在前技術相比確實具有優點，但是其並不是最佳的。在原理上，對於視頻中的每個幀，存在整體上使得整個幀的RD代價最小化的運動矢量場{mij，i＝0..M-1，j＝0..N-1}total_RD_Cost=i=0M-1j=0N-1[SAD(si,j,c(mi,j))+i,j(R(mi,j-pi,j))]---(2)]]>其中(i，j)表示在包含M×N個塊的幀中的第(i，j)個塊。對於固定Qp(其是量化參數)，λi，j＝λ＝恆量，而且pi，j＝median(mi，j-1，mi-1，j，mi-1，j+1)(3)
然而，考慮到整個幀的全部RD代價同時需要指數級的計算複雜性，這是不實際的。因而，PMVFAST和其它已知算法每次僅僅考慮僅一個塊的RD代價，而不是一幀中全部塊。
特別是，MVFAST或PMVFAST都沒有考慮當導出相對於當前塊的運動矢量時，這導致下一個塊的在中值MV預測器中的變化。這能夠影響整個運動矢量場的平滑。
一般地說，本發明的第一方面通過改善PMVFAST的代價定義和運動預測器候選的選擇而提出了一種新的ME算法。特別是，對於第一圖像的每個當前塊(當前塊可以是16×16，16×8，8×16，8×8，4×8，8×4，4×4或其它矩形長度，甚至非矩形)，根據一個代價函數來選擇第二圖像(參考圖像)的類似塊，所述代價函數包括兩項(i)當前塊與相似塊的不相似測量(例如SAD，SAE)的項，以及(ii)作為至少是對第一圖像的未來塊的運動矢量的預測的函數的項。
特別是，所提出的算法通過包含當前中值MV預測器並且還包含未來(即至今未處理)的編碼塊的估計中值MV預測器，使得改善運動場平滑性成為可能。
本發明的許多變化是可能的。特別是，所述塊可以具有任何大小和任何形狀。
可以有多個第二圖像(即多個參考值)並且所述搜索可以包括在所有第二圖像中的候選位置。
此外，可以為一起構成所述第一圖像中的較大區域的、並且採用由編碼數字所定義的編碼順序進行編碼的多個子塊執行所述新的代價函數。這些子塊無須具有相同大小或形狀。
本發明具有另一方面，其可以與本發明第一方面組合或獨立使用。
一般地說，本發明第二方面提出當對第一圖像(當前塊可以是16×16，16×8，8×16，8×8，4×8，8×4，4×4，或其它矩形大小，甚至非矩形)的當前塊進行編碼時，使用所選出的、具有從與已知技術中所使用的值不同的一組值中選出的位置值(即兩個軸線方向中的各自組件)的運動矢量進行編碼。
考慮一個可能的運動矢量預測器(0，0)。而整像素的常規技術允許運動矢量採用諸如-2.0，-1.0，0，1.0，2.0等的位置值，本發明第二方面提出修改接近於所述預測器的一組可能位置值。對於最接近0的位置值1.0，我們可以使用另一位置值諸如0.85，從而使得可允許的位置值將會包括-2.0，-0.85，0，0.85，2.0等等。其優點在於，在統計上，運動矢量趨向接近於0。並且，因而通過選擇更加接近於0的位置，我們將更加接近真實運動矢量，並且因而可以給出可以導致較高壓縮效率的更好的運動補償。
因而，在本發明一個特定表達中，可以選擇為至少一個軸方向選擇一組可能位置值，從而使得它們無法全部寫作Lm，其中m＝-...，2，-1，0，1，2...，並且L是常量(例如1個像素間隔，1/2像素間隔，或1/4像素間隔)；即，位置值是不均勻的。特別是，可以選擇為至少一個軸方向選擇一組可能位置值，從而使得它們無法全部寫作m/n，其中m＝-...，2，-1，0，1，2，...並且n是1或2的冪。
注意，本發明的第二方面並不局限於從一組非均勻的空間位置值中選擇位置值；與傳統的位置值組相比，也不局限於僅僅選擇最接近於零的兩個位置值。作為示例，在本發明的第二方面的另一個示例裡，位置值2.0可變成1.9，從而可允許的位置值將包括-1.9，-0.85，0，0.85，1.9等。
因而，在本發明第二方面的可替換的特定表達中，(為至少一個所述方向)選擇一組可能位置值，以包括可以寫作為LAmm/n的一個或多個位置值，其中m＝-...，2，-1，0，1，2..，n是1或2的冪，L是常量(例如1像素間隔，1/2像素間隔，或1/4像素間隔)，並且Am是小於1但是至少是0.75的值(對於不同的m值選擇性地不同)，更加優選地至少是0.80，並且最優選地至少是0.85。
我們已經發現Am的最佳值取決於視頻。
本發明第二方面的特定實施例的一個優點在於，它們所產生的運動矢量可以採用與常規算法相同的格式碼進行編碼，除了該位置值的常規碼應當分別解釋為該實施例所使用的可能位置值之外。例如，如果由特定實施例所使用的位置值是-1.9，-0.85，0，0.85，1.9等，則位置值1.0的常規碼應該解釋為0.85，並且位置值2.0的常規碼應該解釋為1.9，等。
根據本發明的第二方面的方法可以包括以下步驟定義搜索區域，在所述搜索區域內定義多個候選位置，所述多個候選位置包括由本發明第二方面的新的位置值所定義的一組多個位置。這些位置值是來自關鍵位置(例如，(0，0)運動矢量位置，預測運動矢量，等)處的候選位置的相應位移值。對於每個候選運動矢量而言，我們計算代價函數，所述代價函數是第一圖像中的當前塊與第二圖像中的所述候選運動矢量處的塊之間的相似度測量(例如SAD，SAE)的函數。可選地，其還可以是以下運動矢量的函數所述候選運動矢量、當前預測運動矢量，以及可選地，如本發明第一方面，一個或多個未來預測運動矢量。例如，可選地，如本發明第一方面，可以給定該代價函數。


現在將僅僅參考以下附圖描述本發明實施例作為示例，其中圖1示出了當前塊、左塊、頂部塊、右上方塊、右右上方塊、和右塊；圖2示出了Diff的典型分布，其是|mi，j+1-pi，j+1|與|mi,j-pi，j+1|之間的差異；圖3a示出了如本發明第一實施例所使用的巨大菱形搜索的搜索方式；圖3b示出了如本發明第一實施例中所使用的修改的巨大菱形搜索的搜索方式；圖4示出了如本發明第一實施例中所使用的小菱形搜索的搜索方式；圖5a和5b比較PMVFAST和本發明第一實施例的MV域的平滑性；圖6示出了對當前幀中的(a)(0，0)MV、(b)中值MV、(c)相鄰MV和先前幀中所配置的MV、(d)在先前幀中的右下方的MV(PreBottomRightMV)使用完全搜索(FS)算法得到的在Foreman序列中的運動矢量分布；
圖7是本發明第一實施例的流程圖。
具體實施例方式
本發明第一實施例採用了PMVFAST算法的許多特徵，但是是通過考慮幾個鄰近塊而不是僅僅一個塊來對PMVFAST(及其它現有算法)加以改進的。等式(2)和(3)示出，當前塊MV的選擇直接影響鄰近塊的RD代價，所述鄰近塊包括右塊(或第(i，j+1)塊)，左下方塊(或第(i+1，j-1)塊)，以及下方塊(或第(i+1，j)塊)。這是因為，當前MV將會影響這些鄰近塊的所預測MV，並且因此進而影響那些塊的最佳運動矢量。這些是「未來」塊，因為當處理當前塊時，還沒有對它們執行運動估計。我們無法與當前塊同時地計算這些未來塊的最佳運動矢量，因為我們將需要按照等式(2)同時計算整個幀中所有塊的最佳運動矢量，這將會非常複雜。
作為替代，為了評定在右塊或第(i，j+1)塊上的當前塊的當前MV的選擇的蘊含式，我們可以為等式(1)的當前塊的RD代價函數增加一項R(|mi，j+1-pi，j+1|)(4)其中，mi，j+1是基於當前塊的當前MV的右塊的最佳運動矢量，並且pi，j+1是基於當前塊的當前MV的右塊的中值MV預測器，即pi，j+1＝median(mi，j，mi-1，j+1，mi-1，j+2)(5)然而，等式(4)中的mi，j+1是未知的，因為右塊(未來塊)的運動估計還沒有執行。然而，我們注意到，|mi，j+1-pi，j+1|可以通過|mi，j-pi，j+1|很好地近似。讓Diff為|mi，j+1-pi，j+1|-|mi，j-pi，j+1|。我們對許多視頻測試順序進行實驗並且研究Diff的分布。圖2顯示了Foreman序列的概率密度函數(概率分布函數)，如圖2所示，典型的結果嚴重地偏向零。這意味著這兩個量在大部分情況中是基本相同的(在大約70％情況下相同，而在大約23％的情況下僅僅相差1)。這意味著，|mi，j-pi，j+1|是|mi，j+1-pi，j+1|的良好的近似。因此，R(|mi，j+1-pi，j+1|)可以由W*R(|mi，j-pi，j+1|)來近似，其中W＞0。同樣，我們可以對左下方塊和下方塊添加附加項到代價中。
對於第(i，j)塊，讓medianMV表示由等式3給出中值MV預測器。讓FmedianMV表示由等式(5)給出的未來中值MV預測器(用於右塊的中值MV預測器)。從而，FmedianMV是MV候選的函數。在此，第一實施例被稱為對於第(i，j)塊的「增強預測運動矢量場自適應搜索技術」(E-PMVFAST)。該實施例的步驟如下。
實施例的各步驟如下，示於圖7中。
對任何候選MV，如下定義代價。cost(MV)＝SAD+λ*[w*R(MV-medianMV)+(1-w)*R(MV-FmedianMV)](6)1.計算三個運動矢量預測器的代價(i)中值MV預測器(「medianMV」)，(ii)右塊的估計運動矢量(「futureMV」)，其定義為如下futureMV≡median(TopMV，TopRightMV，TopRightRightMV)和(iii)來自過去塊(「pastMV」)的MV預測器，其是先前的共位MV(「PreMV」)和遠離於medianMV的先前右下方的MV(「PreBottomRightMV」)中的一個，即pastMV≡arg maxMV∈{PreMv，PreBottomRightMV}{abs(MV-medianMV)}注意，項(ii)可以由用於另一鄰近未來塊(諸如左下方的、底部，和/或右下方的塊)的估計運動矢量來補充或代替。
還應當注意，在項(iii)中，先前右下方的MV可以由用於另一鄰近塊的先前MV預測器補充或替換。
注意，項(ii)和(iii)形代價發明的獨立方面。
如果以上任意一個MV預測器不可用(例如在幀的邊界)，則跳過該預測器。
2.如果運動矢量預測器的最小代價小於閾值T1，則停止搜索並且轉到步驟7。否則，選擇具有最小代價的運動矢量作為currentMV(當前MV)並且轉到下一步驟。注意，3個運動矢量預測器的代價可以採用預定順序來計算(例如medianMV，接著是futureMV，接著是pastMV)，並且在任何時刻，如果任何運動矢量預測器的代價小於特定閾值，則搜索可能停止並且轉到步驟7。
3.圍繞currentMV執行定向小菱形搜索的一次迭代。下面解釋定向小菱形搜索的概念。
4.如果最小代價小於閾值T2，則停止搜索並且轉到步驟7。否則，選擇具有最小代價的運動矢量作為currentMV並且轉到下一步驟。
5.如果(currentMV＝medianMV)並且當前最小代價小於閾值T3，則執行小菱形搜索並且轉到步驟7。
6.如果視頻不是隔行掃描，則執行大菱形搜索，如圖3(a)所示；否則，執行如圖3(b)所示的修改的大菱形搜索。在這些步驟中的每個步驟中，對菱形的每一標誌點評估代價函數。
7.選擇具有最小代價的MV。
在我們的實驗中，發現w的值大約0.8是有效。
現在解釋定向小菱形搜索的步驟。假定，centerMV是當前搜索中心，並且MV1，MV2，MV3和MV4是四個圍繞搜索點，如圖4所示。為每個MVi計算R(MVi-medianMV)。如果R(MVi-medianMV)＜R(centerMV-medianMV)，則計算MVi的SAD和代價。否則，忽略該MVi。選擇具有最低代價的MV作為currentMV。注意，定向方塊搜索的概念被認為是新的，並且構代價發明一個獨立方面，其無須與使用futureMV的概念相結合來執行。
大菱形搜索和修改的大菱形搜索的步驟是相同的，但是所述搜索是對於圖3(a)和3(b)中分別示出的點的所有集合而完成的。
我們現在考慮在本發明範圍內的實施例的多個可能的變體。
首先，注意，對於不同的塊，在代價函數中的加權係數w可以是不同的。此外，可選擇地，對於不同的MV候選所述w可以是不同的。特別地是，w的定義可以取決於諸如MV候選是否接近於medianMV和/或futureMV、或MV候選的X軸分量或Y軸分量是否與所述FmedianMV的X軸分量或Y軸分量相同之類的情況。
此外，代價函數可以不限制於等式(6)的形式。其可以是包括失真測量項(例如SAD、失真平方和(SSD)、平均偏差失真(MAD)、MSD等)和考慮了對當前塊和某些鄰近塊(例如右塊、下方塊、左下塊等)的運動矢量進行編碼所必需的位的項的任何函數。
此外，在步驟1中，futureMV的定義不局限於以上步驟1給出的形式。對於futureMV的兩個可能的替換定義是和futureMV≡median(leftMV，TopRightMV，TopRightRightMV)和futureMV≡median(medianMV，TopRightMV，TopRightRightMV)此外，在以上表達的步驟1中，pastMV被選為在先前幀中的可能MV(preMV和preBottomRlghtMV)的列表集合中距離medianMV最遠的一個。然而，要考慮的MV列表可以包含兩個以上可能的MV(例如preMV，preLeftMV，preRightMV，preTopMV，preTopLeftMV，preTopRightMV，preBottomMB，preBottomLeftMV，preBottomRightMV，等)。此外，來自一個以上先前編碼幀的MV可以包括在所述列表中(例如如果當前幀是幀N，則所述列表可以包含幀N-1，N-2，N-3，...)。如果當前幀是B幀，則先前編碼幀的列表可以包括未來P幀。
此外，在步驟1中，選擇pastMV為距離參考MV(在步驟1中的medianMV)最遠的可能的MV。其它參考MV也是可以的，包括leffMV、或TopMV、或TopRightMV、或某組合。從可能的MV的列表中進行選擇的其它方法也是可能的。
在步驟2中，所述3個運動矢量預測器的代價是在按照某種預定義順序中得到的。可能的預定義順序包括a)medianMV，隨後是futureMV，隨後是pastMVb)medianMV，隨後是pastMV，隨後是futureMVc)futureMV，隨後是medianMV，隨後是pastMVd)futureMV，隨後是pastMV，隨後是medianMVe)pastMV，隨後是medianMV，隨後是futureMVf)pastMV，隨後是futureMV，隨後是medianMV此外，雖然如以上表達，在步驟3中執行了定向小菱形搜索的一次迭代，可以應用一個以上的迭代。
模擬結果我們現在給出實施例E-PMVFAST的模擬結果。將所述實施例嵌入到H.264參考軟體JM9.3[13]中，並且使用各種QP、視頻序列、解析度和搜索範圍對其進行模擬。表1(a-c)和2(a-c)示出一些典型的模擬結果。PSNR(峰值信號與噪聲的比例)變化和BR(比特率)變化是相對於完全搜索(FS)的PSNR和比特率的變化。模擬結果示出，所提出的E-PMVFAST的比特率和PSNR趨向於與完全搜索和PMVFAST類似，但是在大範圍的視頻序列和比特率上，E-PMVFAST趨向於比PMVFAST快大約40％。E-PMVFAST的一個重要特徵在於，其運動矢量場趨向於非常地平滑，從而使得運動矢量可以比其它快速移動估計算法更加準確地表示對象的移動。
在圖5(a)以及5(b)中，左側的圖像示出(如短線)由PMVFAST算法獲得的運動矢量場，而右側的成像示出通過所述實施例獲得的相同成像的運動矢量。E-PMVFAST的運動矢量場顯著地比PMVFAST的運動矢量場更加平滑，特別是在所圈出的區域中。對於將感知轉換編碼(perceptual trans-coding)、速率控制、多種塊大小運動估計、多種標準幀運動估計等中的視頻運動內容進行分類而言，平滑的運動場非常有用。


表格1a-foreman CIF序列的模擬結果

表格1b-Coastguard CIF序列的模擬結果


表格1c-Hall CIF序列的模擬結果

表格2a-foreman QCIF序列的模擬結果


表格2b-Akiyo QCIF序列的模擬結果

表格2c-Coastguard QCIF序列的模擬結果我們現在轉向本發明的第二實施例，其示出了本發明的第二方面。
如上所述，常規完全整數像素允許運動矢量在每個方向上採用-2.0，-1.0，0，1.0，2.0等等的位置值。在本發明第二實施例中，選擇接近於預測器的可能位置值。對於最接近0的位置值，我們可以使用(代替1.0)另一位置值，諸如0.85，從而使得允許的位置值可以包括-2.0，-0.85，0，0.85，2.0等等。此優點在於，在統計上運動矢量趨向接近於0。因此，通過選擇更加接近0的位置，我們會更加接近於真實的運動矢量，並且因而可以給出可以導致較高壓縮效率的更好的運動補償。類似地，可以改變其它位置值。例如，可以將位置值2.0改變為1.9，從而使得允許的位置值會包括-1.9，-0.85，0，0.85，1.9等等。除了1.0的編碼運動矢量位置應當解釋為0.85，並且2.0的編碼運動矢量位置應當解釋為1.9以外，所提出的改變的優點在於可以使用相同運動矢量代碼。
半像素精度允許運動矢量採用諸如0.0，0.5，1.0，1.5，2.0等等之類的位置值。我們建議修改這些位置值，特別是那些接近於預測器的位置值。對於非常接近於0的位置值0.5，我們建議使用一個不同的值。例如，一種可能性是使用0.4代替0.5。換句話說，位置值將包括0.0，0.4，1.0，1.5，2.0。類似地，其它位置值可以被修改。例如，位置值1.0可以改變為0.9，從而使得該組新位置值將包括0.0，0.4，0.95，1.5，2.0等等。同樣，這可以有助於提高壓縮效率。類似地，可以修改其它位置值以提高壓縮效率。然而，改變這種位置能夠顯著地導致編碼器和解碼器兩者處的較高的計算效率。通常，大部分壓縮效率增益來自於將位置值改變為接近於預測器。
1/4像素精度允許運動矢量採用諸如0.00，0.25，0.50，0.75，1.00等等之類的位置值。我們可以修改位置值，特別那些接近於預測器的位置值。例如，我們可以將它們修改為0.00，0.20，0.47，0.73，0.99等。
注意，所提出的方法允許我們在每個整數位置值之間選擇任意數量的位置值。例如，在位置值0和1之間，半像素精度使用1個位置值{0.5}，1/4像素精度使用3個位置值{0.25，0.50，0.75}，以及1/8像素精度使用7個位置值{0.125，0.250，0.375，0.500，0.625，0.750，0.875}。提出的方法允許我們在0和1之間選擇任何N個位置值。例如，我們可以選擇N＝2值諸如0.3和0.6。
所提出的不均勻的亞像素運動估計和補償不是必須要應用於每個幀的每個區域。相反，可以將某些位引入到頭部中，以指示對於所述視頻幀的每個區域(例如片)其是否被開啟或關閉。除此之外，其可以在沒有任何語法改變的情況下直接應用於現有標準，因為可以應用相同的運動矢量代碼。
採用H.264 JM82軟體對所提出的不均勻的亞像素運動估計和補償進行模擬，並且其結果在以上表格中示出，其中QP代表量化參數。該模擬在x和y方向中使用位置值(...-1，-0.75，-0.5，-0.15，0，0.15，0.5，0.75，1..)。即，與使用1/4像素空間位置值的標準方法相比較，僅僅修改了在-0.25和+0.25處的位置值。除了使用新的位置值之外，所述算法在其他方面與已知的H.264標準算法相同。如在表中所示出的，第二實施例在實現相似的PSNR的同時，明顯地降低了比特率。不需要修改H.264的語法。



儘管以上描述的僅僅是本發明的幾個實施例，在本發明範圍內許多變化都是可能的。
例如，以上給出的本發明的描述是用於具有一個參考幀的P幀中的固定大小的塊。然而，本發明可以應用於具有多種子塊大小的塊，並且所述塊不是必須要非重疊的。可以有一個以上的參考幀，並且參考幀可以是視頻序列的相對於當前幀的過去或將來的任何塊。
對於視頻，一個圖像元素(像素)可以具有一個或多個分量，諸如亮度分量、紅色，綠色，藍色(RGB)分量、YUV分量、YCrCb分量、紅外分量、X光或其它分量。圖像元素的每個分量是可以表示為數字的符號，所述數字可以是自然數、整數、實數甚至是複數。在自然數的情況下，它們可以是12位，8位，或任何其它位解析度。雖然在視頻中的像素是具有的矩形採樣網格和均勻採樣周期的2維樣本，但是所述採樣網格不是必須為矩形並且所述採樣周期不是必須為是均勻的。
工業實用性本發明的每個實施例適合於由MPEG-1、MPEG-2、MPEG-4、H.261、H.263、H.264、AVS或其他可以被修改以包括以上它的相關視頻編碼標準或方法的快速、低延遲和低代價軟體和硬體實現來實現。可能的應用包括數字視頻廣播(地面、衛星、有線)、數位照相機、數字可攜式攝像機(camcorder)、數字錄像機、機頂盒、個人數字助理(PDA)、可使用多媒體的蜂窩式電話(2.5G、3G及以上)、視頻會議系統、視頻點播系統、無線區域網設備、藍牙應用、網絡伺服器、低或高帶寬應用中的視頻流伺服器、視頻代碼轉換機(從一個格式轉換到另一格式)、及其它電視通信系統等。
參考文獻以下參考文獻的公開內容於此全面引入[1]Joint Video Team of ITU-T and ISO/lEC JTC 1，「Draft ITU-TRecommendation and Final Draft international Standard of Joint VideoSpecification(ITU-T Rec.H.264|ISO/IEC 14496-10AVC)」，docunmentJVT-G050rl，may 2003[2]A.M.Tourapis，O.C.Au and M.L.Liou，「Predictive MotionVector Field Adaptive Search Technique (PMVFAST)」，ISO/IECJTCl/SC29/WG11 MPEG2000，Noordwijkerhout，ML，March』2000[3]R.LI，B.Zeng and M.L.Liou，「A new three-step searchalgorithm for block motion estimation」，On Circuits and Systems forVideo Technology，Vol4，no4，pp438-42，Aug』94[4]Z.L.He和M.L.Liou，「A high performance fast search algorithmfor block matching motion estimation」，IEEE Trans.on Circuits andSystems for Vldo 2Technology，vol.7，no5，pp826-8，Oct』97[5]A.M.Tourapis，O.C.Au，and M.L. Liou，「Fast MotionEstimation using Circular Zonal Search」，Proc.of SPIE Sym.Of VisualComm. Imagg Processin，vol2，pp.1496-1504，Jan.25-27，『99[6]A，M.Tourapis，O.C.Au，M.L Liou，G.Shen，and I.Ahmad，「Optimizing the Mpeg-4 Encoder-Advanced Diamond Zonal Search」，inPros.of 2000 IEEE Inter.Sym.on Circuits and Systems，Geneva，Switzerland，May，2000[7]K.K.Ma and P.I.Hosur，「Performance Report of Motion VectorField Adaptive Search Technique(MVFAST)」，in ISO/IECJTC1/SC29/WG11 MPEG99/m81，Noordwijkerhout，NL Mar』00[8]A.M.Tourapis，O.C.Au，and M.L.Liou，「Fast Block-MatchingMotion Estimation using Predictive Motion Vector Field Adaptive SearchTechnique(PMVFAST)」，in ISO/IEC/JTC1/SC29/WG11 MPEG2000/M5866，Noordwijkerhout，NL，Mar』00[9]Implementation Study Group，「Experimental conditiohs forevaluating encoder motion estimation algorithms」，in ISO/IEC JTC1/SC29/WG11 MPEG99/n3141，Hawaii，USA，Dec』99[10]「MPEG-4 Optimization Model Version 1.0」，in ISO/IECJTC1/SC29/WG11 MPEG2000/n3324，Noordwijkerhout，NL，Mar』00[11]T，Koga，K.linuma，A.Hirano，Y.lijima，and T.Ishlguro，「Motion compensated interframe coding for video conferencing」 Proc.Nat. Telecommun. Conf.，New Orleans，LA，pp. G.5.3.1-G.5.3.5，Dec』81。
J.R.Jain and A.K.Jain，「Displacement measurement and itsapplication in interframe image coding」，JEEE Trans.OnCommunications，vol.COM-29，pp.1799-808，Dec』81[13]JVT reference software JM9.2 for JVT/H.264 FRext
權利要求
1.一種為第一圖像中一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的方法，所述方法包括，根據對於每個候選位置的各自的代價函數的值，為所述第一圖像的所述塊的當前塊，在所述第二圖像中的多個候選位置之間進行選擇，所述代價函數包括(A)在所述第一圖像中的當前像素塊與在所述第二圖像中的候選位置處的像素塊之間的相似度測量，以及(B)與所述候選位置相對應的候選運動矢量、與所述當前塊相關的預測運動矢量、以及在所述系列塊中在所述當前塊之後的所述圖像的至少一個塊的未來預測運動矢量的函數。
2.如權利要求1所述的方法，其中，所述函數包括第一項，其表示對所述候選運動矢量進行編碼所必需的位數，以及第二項，其表示如果將在所述候選位置處的像素塊選擇作為所述第二圖像的相似塊，對所述未來預測運動矢量進行編碼所必需的位數。
3.一種為按照光柵掃描順序的第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的方法，所述方法包括，為所述第一圖像的所述塊的當前塊(i)定義所述當前塊的當前預測運動矢量；(ii)在所述第二圖像中定義搜索區域作為所述第二圖像中的多個候選位置，每個候選位置與各自的候選運動矢量(MV)相關聯，所述候選運動矢量是所述第二圖像中候選位置與所述第一圖像中當前塊的位置之間的相對位移；(iii)對於每個候選運動矢量以及對於在所述系列塊中在所述當前塊之後的所述第一圖像的至少一個未來塊(a)定義所述未來塊的未來預測運動矢量；以及(b)計算代價函數，其包括(A)在所述第一圖像中的當前塊與在所述第二圖像中的候選位置處的塊之間的相似度測量，以及(B)所述候選運動矢量、所述當前預測運動矢量、以及所述未來預測運動矢量的函數；以及(iv)選擇與具有最低的所計算代價函數的候選位置相對應的相似塊。
4.如權利要求3所述的方法，其中，所述函數包括第一項，其表示對所述候選運動矢量進行編碼所必需的位數，以及第二項，其表示如果將在所述候選位置處的塊選擇作為所述相似像素塊，對所述未來預測運動矢量進行編碼所必需的位數。
5.如權利要求4所述的方法，其中，所述第二項表示對所述候選運動矢量與每一個所述未來預測運動矢量之間差異進行編碼所需要的位數。
6.如權利要求4所述的方法，其中，所述函數是根據加權參數的值的所述第一項和所述第二項的加權和。
7.如權利要求6所述的方法，其包括得到所述加權參數的步驟。
8.如權利要求3所述的方法，其中，所述當前預測運動矢量是所述第一圖像的至少一個塊的運動矢量的函數，其中，對於所述至少一個塊，已經預先得到了所述第二圖像中的相似塊，並且所述至少一個塊在空間上鄰近所述當前塊。
9.如權利要求3所述的方法，其中，所述當前預測運動矢量是所述第一圖像之外的一個幀中的與所述當前塊相搭配的至少一個塊的運動矢量的函數。
10.如權利要求3所述的方法，其中，所述當前預測運動矢量是幀中除了與所述當前塊空間上相鄰的第一幀塊之外的至少一個塊的運動矢量的函數。
11.如權利要求3所述的方法，其中，在(iii)中的所述未來塊是根據光柵掃描順序的下一個塊，並且在(iii)(a)中的所述未來預測運動矢量是所述候選運動矢量、右上方和右右上方的運動矢量的中值。
12.如權利要求11所述的方法，其中，當在步驟(iii)中確定所述候選運動矢量中的第一個的代價小於第一閾值時，不計算餘下的所述候選運動矢量的代價函數，並且生成與所述第一候選運動矢量具有預定義的空間關係的一組第二候選運動矢量，並且在步驟(iv)之前，為所述第二候選運動矢量中的每一個計算代價函數。
13.如權利要求12所述的方法，其中，將所述第二候選運動矢量組選擇為比所述第一候選運動矢量更接近所述當前預測運動矢量，其中，在矢量對之間距離的測量是根據對所述矢量之間差異進行編碼所需要的位數來定義的。
14.如權利要求3所述的方法，其中，在步驟(ii)中，所述候選矢量中的至少一個是根據所述光柵掃描順序的所述圖像的未來塊的運動矢量。
15.如權利要求3所述的方法，其中，在步驟(ii)中，所述候選矢量中的一個是使用基於使得所選擇的候選矢量與所述當前預測運動矢量之間的距離最大化的準則，而從一組可能的候選矢量中選擇出的。
16.如權利要求3所述的方法，其中，存在多個第二圖像，所述多個候選位置包括每一個所述第二圖像中的至少一個候選位置。
17.如權利要求3所述的方法，其中，所述塊是所述第一圖像的較大區域的子塊，所述子塊是根據由編碼數定義的編碼順序來編碼的。
18.一種用於為第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自相似的像素塊的系統，所述系統包括處理器，所述處理器配置成順序地處理所述第一圖像的塊，並且根據代價函數，為所述第一圖像的所述系列塊中的每個當前塊，在所述第二圖像中的多個候選位置之間進行選擇，所述代價函數包括(A)在所述第一圖像中的當前像素塊與在所述第二圖像中的候選位置處的像素塊之間的相似度測量，以及(B)與所述候選位置相對應的候選運動矢量、與所述當前塊相關的預測運動矢量、以及在所述系列塊中在所述當前塊之後的所述圖像的至少一個塊的未來預測運動矢量的函數。
19.一種計算機系統可讀的軟體產品，其使得所述計算機系統為第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自相似的像素塊，這是通過根據代價函數，為所述第一圖像的所述系列塊中的當前塊而在所述第二圖像中的多個候選位置之間進行選擇來實現的，所述代價函數包括(A)在所述第一圖像中的當前像素塊與在所述第二圖像中的候選位置處的像素塊之間的相似度測量，以及(B)與所述候選位置相對應的候選運動矢量、與所述當前塊相關的預測運動矢量、以及在所述系列塊中在所述當前塊之後的所述圖像的至少一個塊的未來預測運動矢量的函數。
20.一種為按照光柵掃描順序的第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的方法，所述方法包括為所述第一圖像的所述塊中的當前塊，在所述第二圖像中的多個候選位置之間根據每個候選位置的各自的代價函數的值來進行選擇，所述候選矢量中的至少一個是按照光柵掃描順序的所述圖像的未來塊的預測運動矢量。
21.一種為第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的方法，所述方法包括為所述第一圖像的所述塊中的當前塊，在所述第二圖像中的多個候選位置之間根據每個候選位置的各自的代價函數的值來進行選擇，其中，所述候選矢量中的至少一個是使用基於使得所選擇的候選矢量與所述塊中的所述當前塊的當前預測運動矢量之間的距離最大化的準則，而從一組可能的候選矢量中選擇出的。
22.一種為第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的方法，所述方法包括為所述第一圖像的所述塊中的當前塊，在所述第二圖像中的多個候選位置之間根據每個候選位置的各自的代價函數的值來進行選擇，其中，所述第二候選運動矢量組是通過以下過程來選擇的，所述過程包括定義所述塊中的所述當前塊的當前預測運動；定義第一候選運動矢量，以及定義一組第二候選運動矢量，其比所述第一候選運動矢量更接近所述當前預測運動矢量，其中，在矢量對之間距離的測量是根據對所述矢量之間差異進行編碼所需要的位數來定義的。
23.一種為第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的方法，所述方法包括為所述第一圖像的所述系列塊中當前塊，在所述第二圖像中的多個候選位置之間進行選擇，所述多個候選位置包括由在各自橫向方向上的兩個位置值所定義的一組候選位置，所述方向中的至少一個的位置值為使得其無法全部由Lm表示，其中，m是整數，L是常量。
24.如權利要求23所述的方法，其中，所述候選位置組中的每一個通過相應位置值與各自的運動矢量相關聯，所述運動矢量不同於預測運動矢量。
25.如權利要求23所述的方法，其中，所述候選位置組中的每一個通過相應位置值與各自的運動矢量相關聯，所述運動矢量不同於(0，0)運動矢量。
26.一種為第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的方法，所述方法包括為所述第一圖像的所述系列塊中的當前塊，在所述第二圖像中的多個候選位置之間進行選擇，所述多個所述候選位置包括由兩個位置值所定義的一組候選位置，所述候選位置能夠寫作DAmm/n，其中m＝-...，2，-1，0，1，2...，n是1或2的冪，D是常量，而對於m的至少一個的值而言Am是小於1的值，並且對於m的所有值而言其是在0.75至1.0的範圍內。
27.如權利要求26所述的方法，其中，所述候選位置組中的每一個通過相應位置值與各自的運動矢量相關聯，所述運動矢量不同於預測運動矢量。
28.如權利要求26所述的方法，其中，所述候選位置組中的每一個通過相應位置值與各自的運動矢量相關聯，所述運動矢量不同於(0，0)運動矢量。
29.如權利要求26所述的方法，其中，對於m的所有值而言，Am的值至少為0.85。
30.如權利要求26所述的方法，其中，對於m＜-1以及m＞1而言，Am等於1。
31.一種為第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的系統，所述系統包括處理器，所述處理器配置為，為所述第一圖像的所述系列塊中當前塊，在所述第二圖像中的多個候選位置之間進行選擇，所述多個候選位置包括由在各自橫向方向上的兩個位置值所定義的一組候選位置，所述方向中的至少一個的位置值為使得其無法全部由Lm表示，其中，m是整數，L是常量。
32.一種計算機系統可讀的軟體產品，其使得所述計算機系統為第一圖像中的一系列像素塊中的每一個選擇第二圖像的各自的相似像素塊的系統，這是通過在所述第二圖像中的多個候選位置之間進行選擇來實現的，所述多個候選位置包括由在各自橫向方向上的兩個位置值所定義的一組候選位置，所述方向中的至少一個的位置值為使得其無法全部由Lm表示，其中，m是整數，L是常量。
全文摘要
提出了一種方法、系統和軟體，用於獲得與第二圖像(「參考圖像」)的塊相類似的第一圖像的塊。對第一圖像的塊順序地進行處理，為每個塊得到在第二圖像中的多個候選位置，並且為每個候選位置評估代價函數。在第二圖像中的每個候選位置是由來自第一圖像的塊的各自運動矢量來替換的。在本發明的第一方面中，所述代價函數是第一圖像的未來塊(即還沒有被處理的第一圖像的塊)的預測運動矢量的函數。在本發明第二方面中，所述運動矢量由位置值給出，所述位置值並非全部是全像素空間、半像素空間、或1/4像素空間的。
文檔編號H04N7/32GK101090491SQ20061006477
公開日2007年12月19日 申請日期2006年12月15日 優先權日2006年6月16日
發明者區子廉, 黃海明 申請人:香港科技大學