圖像運動估計的方法及系統的製作方法

2023-09-12 22:29:45

專利名稱：圖像運動估計的方法及系統的製作方法
技術領域：
本發明主題涉及視頻處理，特別是視頻處理中的運動估計。
背景技術：
視頻的傳輸和存儲對於許多應用非常重要，已經獲得了世界範圍內的關注。但是， 原始的未經壓縮的視頻序列可能非常大。例如，對於高清視頻，原始的未經壓縮的視頻數據可能近448G。而且，原始的未壓縮的視頻數據包含很多的冗餘信息，像時域上的冗餘、空域上的冗餘和/或統計冗餘。因此，利用視頻壓縮來減小原始視頻數據量。已經開發了多種視頻編碼標準，像運動視頻專家組的MPEG-V2/4和國際電信聯盟電信標準的ITU-T Η^61Λ63Λ64，以求達到高效的視頻壓縮。例如，不同的編碼標準應用運動估計和補償來實現視頻壓縮，對時域冗餘信息進行壓縮。一些視頻編碼方法應用離散餘弦變換來實現對空間冗餘信息的壓縮。一些利用熵編碼實現統計壓縮。還有一些視頻編碼標準應用量化來減少視覺冗餘以達到壓縮目的。然而，各種視頻壓縮技術都會有相應的權衡，那就是增加運算的複雜度和編碼時間。例如，整數運動估計佔用了將近60%的編碼時間。如果採用分數運動估計，相應的編碼時間會達到90%。之前對於現代的視頻處理技術上的描述的不足之處僅僅是為了提供一個對傳統系統概述的一些問題，而不是為了進行窮舉。傳統系統的其他問題在以下的描述中將更加明了。

發明內容
此處給出有關本發明概要的描述。根據一個或多個方面以及對應的公開內容，各方面都是和率失真最優化(RDO)運動矢量預測(MVP)偏移可變塊大小(VBQ運動估計算法有關(將該算法稱為率失真最優化單一運動矢量預測偏移全搜索(RD0MFQ算法)，及其對應的可重構的硬體架構。在一方面， RDOMFS使用易於硬體實現的一個單一 MVP (SMVP)及RD代價函數，以能夠取得與H. 264參考軟體JM中的FS-RD-var-mvp相似的編碼效率。在其他方面，匹配算法對應的硬體架構使用了 2-D脈動陣列來實現所提出的RD0MFS。RDOMFS重新使用當前幀中的MVP，以消除或者基本上消除將MV存儲在片上晶片中的需要。一個新穎的MV再利用架構被提出，從而可以消除，或極大地減少MV所需的存儲器。其次，RDOMFS使用了一種新型的掃描方法，在搜索窗口中使用了一種新的掃描順序，使得冗餘度去能夠被最小化，且能夠實現不同的數據利用率。以下將詳細描述這些和其它實施例。


參照附圖，進一步描述各種非限制性實施例，其中圖1顯示了提供視頻壓縮的示例性系統的上層框圖；圖2A顯示了對於不同的塊大小的H. 264中值運動矢量預測值的定義；圖2B顯示了根據一個方面的所有子塊統一的單一運動矢量預測值(SMVP)；圖2C顯示了左側、頂部和右上角子塊的空間上的不同定義圖3顯示了根據一個方面的一種視頻壓縮方法；圖4顯示了根據一個方面的一種系統；圖5顯示了所公開方面的頂層框圖；圖6A顯示了傳統的光柵掃描；圖6B顯示了傳統的蛇型掃描；圖6C顯示了根據一個方面的一種智能的蛇型掃描順序；圖6D示出了根據一個方面的圖6C的兩個放大的子區域；圖7顯示了根據一個方面的一種視頻處理的方法；圖8顯示了根據一個方面的一種視頻編碼的系統；圖9顯示了當前幀中MVP再利用方法的概念；圖10顯示了根據一個方面的一種多解析度MVP再利用策略的設備；以及圖11顯示了根據一個方面的一種視頻編碼的方法。
具體實施例方式如之前所提到的，許多應用都利用視頻的傳輸和存儲，因此，高效的視頻壓縮得到了廣泛的關注。傳統的視頻壓縮技術或應用運動估計和補償來實現視頻壓縮中對時域冗餘信息的壓縮，應用離散餘弦變換來實現對空間冗餘信息的壓縮，利用熵編碼實現統計壓縮和應用量化來減少視覺冗餘，以達到壓縮的目的。運動估計(ME)和運動補償(MC)可有效降低時域冗餘，因為時域上相鄰幀之間存在很強的時間相關性。通過使用參考幀預測的框架，構建一個預測幀，並從當前幀減掉預測幀，得到的幀(稱為殘幀)往往有比原來低得多的熵，從而可以用提升的編碼率失真性能編碼。然而，ME的效率有一個權衡，這就是增加了計算複雜性和編碼時間。運動估計主要包括兩部分整數ME和分數ME。根據H. 264參考軟體(JM)的整像素運動估計(IME)的計算複雜度可以消耗近60%的編碼時間。當包含分像素運動估計，可以消耗高達90%的編碼時間。現有運動估計技術大多是基於塊匹配(BM)。通常，在塊匹配中，當前幀被劃分為非重疊的塊，稱為宏塊(MB)，每個宏塊的大小為NXN(例如，N= 16)。對於當前幀中的每個當前的宏塊MB，搜索窗口是指在參考幀中圍繞一個參考點(例如，前一幀的相同位置的點或某一預測位置)的局域。不失一般性，在該詳細描述中，假設在水平方向和垂直方向搜索範圍是[_P，P)。在搜索窗口中的每個點被稱為一個搜索位置，相當於一個候選宏塊用以對當前宏塊進行預測。一個失真測度被定義為衡量候選宏塊和當前宏塊的相似性。在搜索窗口搜索與當前宏塊最相似的候選宏塊(即，匹配宏塊)。匹配宏塊和當前宏塊的位移稱為運動矢量(MV)。存在很多方法來確定在搜索窗口中的候選宏塊與當前宏塊的不匹配程度，如平方差(SSD)的總和、絕對變換差之和(SATD)。當然，不匹配程度越小意味著相似程度越高。然而，由於簡單性和有效性，最常用的衡量不匹配程度的是絕對差之和(SAD)。
N-I W-ISADtetl(m,n} = ^ ^ \Xt(k + ij+/)- Xt_x(fe + m+ ij + w + ;)|
i-0 /:0 ( 1)其中(m，n)為在-Rn，η <P範圍內的運動矢量，Xt (i，j)和X(h) (i，j)為在位置 (i，j)處的t時刻的當前幀和在t-1時刻的參考幀的像素值，(k，1)為在當前幀的當前塊的位置。SAD計算具有高度的一致性並且適合高效的實現。此外，傳統的運動估計架構基於 SAD。最近，另一種方法，拉格朗日率失真(RD)成本函數，已經得到廣泛的關注。RD的一般形式是RDCost = D+ λ · R (2)其中D是失真率，例如SSD，SATD或SAD，R是相關的碼率(如MV和/或殘差的)， λ是拉格朗日乘數。在一般情況下，因為MV本身可能需要許多位來編碼，尋找具有最小不匹配度的MV 的方法可能無法找到合適的MV。例如，一個次優不匹配MV可能需要很少的位數來編碼。這就是H. 264編碼器的情況，其需要用很多的位數來編碼運動矢量。例如，在H. 264編碼器中，一個接近於中值預測運動矢量(MVP)的MV比離中值更遠的MV需要用更少的位數來編碼。為了實現碼率失真優化，SAD或者SSD的成本函數一般不適合。相反，拉格朗日碼率失真成本函數是一個很好的解決方案。例如，λ的選擇使得能夠在R項和D項之間進行一種權衡。一個具有大λ的碼率失真函數往往是由R主導整個函數，這樣，傾向於選擇具有小碼率(R)的MV。另一方面，一個具有小λ的率失真代價往往是由D主導整個函數，這樣，傾向於選擇具有小失真率的MV。這是為什麼碼率失真成本函數被經常用在最先進的視頻編碼中，如H. 264/AVC，例如，去實現高質量率失真性能。在H.沈4中，λ對不同的量化參數Qp 是不同的，Qp可以有51個左右可能的值。當率失真成本函數被應用時，運動估計指的是率失真最優或者RD0。但是，在硬體中難以實現率失真成本函數，因為使用率失真成本函數的計算使用浮點乘法和/或用於查找表的硬體資源的耗費很嚴重。—個普遍的運動估計技術是全搜索塊匹配算法(FS)，其以硬算方式搜索了搜索窗口中的所有搜索點。FS是零偏置，這意味著其在參考幀中搜索窗口的中心坐標和當前MB 的位置相同或大致相同。全搜索是搜索搜索區域中的所有點，因此，可以實現全局最小不匹配，因此也有良好的視覺質量。全搜索在軟體實現中需要巨大的計算量，然而，全搜索可以有效地用硬體實現以獲得良好的數據吞吐量，因為它的數據流是有規律的且適合用於流水線。此外，數據復用可以在相鄰的搜索區域之間被利用，因為它們的參考像素區域是重疊的。除了全搜索算法，人們提出了許多快速運動估計(FME)算法來避免全搜索的巨大的計算量。許多的快速搜索算法在搜索中心周圍進行一定的搜索。搜索中心可能是零偏置或MVP偏置的。零偏置搜索中心是(0，0)運動矢量。一些常用的零偏置的快速搜索算法包括NTSS (新三步搜索)、菱形搜索，FTS (動態三角搜索)、交叉搜索。MVP偏置搜索的搜索中心是根據一定的標準從許多MVP中選擇出來的。通常典型的MVP是空間和時間上相鄰塊的 MV。此外，MVP偏置的搜索中心可能是或可能不是(0，0)運動矢量。一些常見的MVP偏置搜索包括PMVFAST (預測的運動矢量場自適應搜索技術),UMHexagonS,以及EPM (有效的預測區域算法)。通常情況下，一些局部搜索是圍繞在FME搜索中心進行的。在這種情況下，最後獲得的MV只能達到局部最小不匹配(而不是FS的全局最小)。往往這種局部最小不匹配會導致比全搜索低的視覺質量。然而，MVP偏置的快速運動估計搜索算法往往比零偏置快速運動估計搜索算法具有的更高的視覺質量，因為MVP偏置的搜索中心往往是較零偏置搜索中心更加接近全搜索的全局最低點。有時，許多MVP偏置的快速搜索算法的率失真性能大致和全局搜索的相同。這大概就是為什麼MVP偏置的快速搜索算法在MPEG-4和H. 264 等參考軟體中使用的原因。另一個MVP偏置搜索中心可取的特點是，它往往會提供比零偏置搜索中心更平滑的運動領域，更接近實際情況。然而，往往難以在硬體中實現MVP偏置的運動估計算法，因為要考慮多個MVP和局部搜索的不規則性往往可以輕易地打破硬體的流水線結構從而降低硬體效率，具有較低的數據再利用和更多的內存訪問。早期的視頻編碼標準，如MPEG-1、MPEG-2、H.沈3、和MPEG-4傾向於使用16x16的宏塊作為基本的編碼單位和執行固定塊大小(FBQ的運動估計。另一方面，最新的H. 264允許一個16x16MB的宏塊被分成均存在自己運動矢量的子塊並且對所有可能的子塊進行可變塊大小(VBS)的運動估計。例如，16x16MB可被劃分成大小16X16、16X8、8X16、8X8、 8X4、4X8和4X4的子塊。VBS的運動估計允許不同的MV有不同的子塊，從而可以為所有的子塊實現比固定塊運動估計更好的匹配。通過改進的預測，VBS的運動估計可以用於 H.沈4以實現更高的編碼效率。VBS在宏塊中包含多個運動不一致的對象時十分有用。VBS 對宏塊內存在旋轉和變形也是十分有用的。雖然VBS的運動估計比固定塊大小的運動估計有良好的碼率失真性能，但VBS巨大的計算量和不規則的內存訪問使硬體實現很困難。雖然早期的ME算法由於運算複雜性往往使用SAD作為不匹配原則，最近運動估計算法考慮碼率失真問題傾向於使用碼率失真函數。在該詳細說明中，「-SAD」和「-RD」被用來區分任何算法的兩個不同版本一個用SAD作為衡量不匹配函數，一個使用RD函數作為成本函數。例如，FS-SAD是使用的SAD的全局搜索而FS-RD是使用RD成本函數的全局搜索。同樣，在該詳細說明中，「-zero」和「-mvp」是分別用來指明零偏置版本和MVP偏置版本的。此外在該詳細說明中，「_var」和「-fix」是分別用來表示變化塊大小和固定塊大小的。例如，FS-SAD-fix-zero是零偏置的以SAD作為不匹配函數的固定塊大小的全局搜索， 和FS-RD-var-mvp是MVP偏置的以RD函數為衡量函數的變化塊大小的全局搜索。多年來，許多運動估計的架構被提出。其中，有些是針對快速運動估計的，但其中大多數是針對全局搜索的。在那些針對全局搜索的運動估計的框架中，一些是MVP偏置的， 一些是應用碼率失真函數的，但其中大部分都是零偏置的利用SAD作為失真程度的衡量標準(例如，FS-SAD-zero)。雖然早期的運動估計的架構往往是為實現固定塊搜索，而新的體系結構多為變化塊大小的搜索.一些運動估計的體系結構包括一個有16個處理單元(PE)的一維(I-D)脈動陣列結構來實現全搜索VBSME(FSVBSME)。另一個運動估計的架構是三個有256個處理單元的 2-D脈動陣列結構，在H. 264JM參考軟體中相比FS-RD-var-mvp它具有較低的RD性能。其他一些運動估計架構使用FS-RD-var-mvp，但是，這種架構要使用一個額外的晶片上大量內存來存儲所有的用於生成MVP的MV。此外，運動估計的架構可能在搜索窗口中產生大量的冗餘讀取，導致巨大延遲和相當多的功耗。在本詳細描述使用的術語「冗餘讀取」是指數據被讀取一次以上。因此，這將有利於提供更有效率的碼率失真優化(RDO)的運動估計，以利用時間冗餘達到良好的碼率失真(RD)的性能、實時的實現高數據吞吐量、規則的數據流、良好的並行性、以及高的內存利用率。此外，這將有利於提供一個更有效的整數運動估計來實時視頻編碼。這也有利於提供更有效率的VBS的運動估計。本發明的一個方面涉及到的一種方法，包括將一個或多個由多個塊創建的視頻幀劃分成多個子塊，並確定在一個或多個視頻幀中的參考幀。該方法還包括將多個子塊的一個搜索區域定義為多個運動矢量預測(MVP)的函數，其中包括將搜索區域集中限定於參考幀內的位置周圍。此外，該方法還包括搜索多個子塊中的至少一個子塊，包括確定率失真 (RD)代價，並根據RD代價選擇相應的運動矢量作為所述至少一個子塊的運動矢量(MV)。在一個實現方式中，確定RD代價包括確定代價函數中的兩個可加項，第一個可加項為當前子塊和候選參考子塊之間的誤差項(即，失真度量)，第二個可加項為lambda算子 (為子塊大小和位置、塊位置和類型、量化參數、目標碼率、及緩存條件或者緩存性能中的至少一個的函數)與候選運動矢量和運動矢量預測之間的差值的函數二者的乘積。該實現方式進一步包括確定第二可加項包括將第二可加項確定為相鄰塊或相鄰子塊的運動矢量的函數。在另一個實現方式中，該方法包括將多個MVP確定為多個相鄰塊或相鄰子塊的MV 的函數，以及其中定義搜索區域包括將將搜索中心確定為多個MVP的函數。更進一步，該方法包括將多個MVP中的一個MVP指定作為左方的塊、上方的塊和右上方的塊上的塊運動矢量的中值。在進一步的實現方式中，確定搜索區域包括將搜索中心確定為三個過去的相鄰塊的運動矢量的中值，這三個以前的相鄰塊包括一個在左邊的第一個塊、一個在上方的第二塊、和一個在右上方的第三塊。更進一步，該方法包括在當第一塊或者第二塊或者第三塊不存在時提供至少一個替代塊。在一方面，確定至少一個替代塊包括選擇左上角位置的第四塊。本發明的另一個方面涉及到一種系統，其包括將一個視頻幀分成多個塊的分割元件和將多個塊劃分成多個子塊的子分割元件。該系統還包括一個選擇元件來從多個子塊中選擇參考幀，和一個歸類元件來來確定一個包括搜索中心的搜索區域。這個搜索區域基於多個運動矢量預測值(MVP)。此外，該系統包括一個評估元件來為搜索區域中所選的搜索點計算率失真(RD)成本函數以為多個子塊選擇一個運動矢量(MV)。在一個實現方式中，RD成本函數包括第一元素和第二元素，其中第一元素是一種失真衡量，第二元素是一個參數和一個衡量候選MV和多個MVP中的一個MVP之間的差異的
10函數的乘積。更進一步，所述參數是lambda，其是子塊大小和位置、塊位置和類型、量化參數、目標碼率、緩存條件和緩存性能的函數。在一個方面，該參數為Lambda並且lambda可以近似成2的冪的線性組合。在一方面，第二元素的MVP是與過去的相鄰塊的運動矢量相關的函數。在另一方面，第二元素的MVP是與當前塊相關的左邊、上方和右上方的過去的相鄰塊的運動矢量的函數。在另一方面，第二元素的MVP是與當前塊相關的左邊、上方和右上方的過去的相鄰塊的運動矢量的中值。在一個實現方式中，搜索區域和當前塊或當前子塊和參考幀中同樣大小的候選參考塊或者候選子塊之間的運動矢量相關。在一些實現方式中，搜索中心是MVP。在一些實現方式中，搜索中心是所確定的三個過去的相鄰塊的運動矢量的中值。 更進一步，三個過去的相鄰塊包括和當前塊相關的一個左邊的塊、一個上方的塊和一個右上方的塊。本發明的另一個方面涉及到一種方法，其包括從多個視頻幀中確定參考幀和在該參考幀中確定包括多個搜索點的搜索區域，該搜索區域包含多個搜索點。該方法還包括將搜索區域劃分成多個子窗口和處理多個幀視頻，處理多個視頻幀包括在多個子窗口中確立掃描順序，每一個子窗口至少被掃描一次，並且兩個掃描順序相鄰的子窗口會在空間上相近。在一個實現中，掃描多個子窗口包括執行水平掃描、豎直掃描、或同時執行水平掃描和豎直掃描。在一些實現方式中，該方法還包括在參考幀中確定包括多個搜索點的搜索區域之前將一視頻幀分成包含NxN個像素的塊；以及其中所述處理步驟包括在一個時鐘周期內並行讀取N個像素和一次性加載子窗口內的所有像素。在進一步的實現方式中，掃描多個子窗口的步驟包括用從16種不同蛇形掃描中所選擇的至少一種蛇型掃描來進行掃描。在一些實現方式中，掃描多個子窗口的步驟還包括用第一種類型的蛇形掃描來掃描第一子窗口、移動到第二子窗口中的相鄰搜索點、以及用第二種類型的蛇形掃描來掃描
第二子窗口。在另一實現方式中，將搜索區域劃分成多個子窗口的步驟包括將搜索區域劃分成一些不相互覆蓋的子窗口。在一個實現方式中，掃描多個子窗口的步驟包括使用從搜索窗口的左上角、右上角、左下角、或右下角開始的掃描來定義掃描順序，以及其中所述掃描是水平掃描或者豎直掃描。某些實現方式中，掃描多個子窗口的步驟包括將搜索區域劃分為多個子區域，並且在多個子區域中局部地使用蛇形掃描。本發明的另外一個方面涉及一種系統，其包括選擇元件，用來確定參考幀；一個指定元件，用來在參考幀中定義搜索區域。該系統還包括一個子分割元件，用來將搜索區域分割為多個子窗口 ；一個掃描元件，用來選擇在多個子窗口之間的掃描順序，每一個子窗口至少被掃描一次，並且掃描順序相鄰的兩個子窗口在空間上是接近的。在一個實現方式上，掃描元件用來實現對多個子窗口的水平掃描、豎直掃描、或水平及豎直掃描。某些實現方式中，所述掃描元件構造為執行其中在第一方向上水平掃描第一行而在第二方向上水平掃描第二行(即，以不同的方向來掃描第一行和第二行)的水平掃描。在另一實現方式中，掃描元件被構造為執行其中在第一方向上豎直掃描第一列而在第二方向上豎直掃描第二列(即，以不同的方向來掃描第一列和第二列)的豎直掃描。在某些實現方式中，掃描元件被構造為需要選擇不同掃描順序的蛇形掃描(包括從搜索窗口區域的左上角、右上角、左下角、右下角開始的蛇形掃描)，並且其中蛇形掃描可以為水平掃描或豎直掃描。某些實現方式中，搜索窗口區域中的多個搜索點是對應於當前塊和參考幀中相同大小的候選參考塊之間的候選運動矢量，其表示相似大小的當前塊和參考塊之間的距離。某些實現方式中，子分割元件被用來將搜索區域分割成多個矩形的子窗口，以及其中搜索區域中的多個搜索點屬於多個子窗口。某些實現方式中，所述系統包含一個數據總線，其配置為在一個時鐘周期中讀取N 個像素，其中參考幀的塊包括NxN個像素。所述系統還包括一個可重構寄存器陣列，用來存儲可能再利用的像素而存儲一行的數據以用在下一行中，其中N個像素可以同時加載到多個子窗口中。在某些實現中，掃描元件被構造為從16種不同的蛇形掃描中選擇掃描順序，其中第一組蛇形掃描針對豎直掃描，而第二組蛇形掃描針對水平掃描。某些實現方式中，掃描元件被構造為選擇一種掃描順序，該掃描順序將搜索區域分割成多個子區域，並在多個子區域中局部應用蛇形掃描。本發明的另一個方面涉及一種方法，所披露方法的特性是支持多個參考幀及多個 MVP。所披露的方法同樣支持在多個參考幀中規定搜索區域，並且可以以第一 MVP及第二 MVP為中心，具體地講，其包括從一組視頻幀中確定多個參考幀，並且從多個參考幀中獲取第一運動矢量預測值(MVP)和第二 MVP。該方法還包括在多個參考幀中定義搜索區域，該搜索區域以第一 MVP或者第二 MVP為中心。其次，該披露的方法還包括基於支持多在參考幀的第一 MVP和第二 MVP的基礎上進行子塊的運動估計並且從多個參考幀的子塊中選擇運動矢量。在某些實現方式中，獲取第一 MVP和第二 MVP的過程包括基於之前塊的MV獲取第一 MVP和第二 MVP。某些實現方式中，獲取第一 MVP或獲取第二 MVP包括獲取當前塊的相鄰左塊、上塊和右上塊的MV的中值。某些實現方式中，執行運動估計包括執行單一 MVP，僅僅使用第一 MVP或者第二 MVP中的一個，而不是多個。在某些方面中，所披露的方法包括以第一 MVP或第二 MVP為中心，進行局部全搜索運動估計。在此基礎之上，執行運動估計包括計算成本函數，其包括兩個可加項，第一個為誤差項(失真項)，第二個為lambda算子(其為子塊的大小和位置、塊位置和類型、量化參數、目標碼率、及緩存條件或緩存性能中的至少一個的函數)及編碼MV所需要的碼率函數的乘積。在此，對視頻處理和圖像運動估計進行了一個簡介。在接下來將詳細介紹一些具體的實現方式。圖像的運動估計圖1顯示了一種用來實現視頻壓縮的示例性視頻處理系統100的上層框圖。視頻處理系統100包括一個分割元件102，用來將一個或多個視頻幀104分割成多個塊106。在某些實現方式中，系統100可以包括一個子分割模塊108，用以將至少一個塊106進一步分成兩個或多個子塊110。某些情況下，分割元件102可以將至少一個塊106進一步分成兩個或多個子塊110。某些情況下，至少一個塊106(有時稱為「當前塊」)可以被進一步子分割為多個當前子塊(如子塊110)。子塊110可以有不同的大小或/和不同的形狀。同時系統100還包括一個選擇元件112，用來選擇第二幀作為參考幀114。一個歸類元件116用來為至少一個子塊110定義搜索區域118。在某些情況下，搜索區域118以一個位置為中心，定義為參考幀114中的搜索中心。搜索區域118中的一個或多個點(記為「搜索點」)可以對應於候選運動矢量 (MV)，其表示當前塊(或當前子塊)與參考幀114中相似大小(或相同大小)的候選參考快(或候選參考子塊)之間的距離。某些情況下，搜索中心可以由一系列的運動矢量預測(MVP)來得到。一個或多個 MVP可以由相鄰的塊或子塊的運動矢量來得到。例如，一個MVP可以為當前塊的相鄰的左邊、上方、右上方塊的運動矢量的中值來得到(記為單一運動矢量預測SMVP)。—個評估元件120被用來針對一個或多個當前子塊，在搜索區域內進行基於RD代價方程的搜索，通過計算搜索區域內所選搜索點的RD成本函數來進行搜索。每一個搜索點都會有一個對應的RD代價，對應的運動矢量可以選擇作為該子塊的MV，基於此選擇最優的子塊的MV在某些情況下，RD代價方程會包含多個項。例如，RD代價中的第一項為可加項， 也就是當前子塊與候選參考子塊間的誤差(即，失真衡量)。RD代價中的第二項是一個參數(稱為lambda算子)與候選MV和MVP之間的差的函數(編碼MV所需要的比特數)的乘積。某些情況下，誤差項可以為SAD。某些情況下，lambda算子可以用2的冪來近似。某些情況下，所需要的比特數可以由SMVP和候選MV之間的差來估計。在某些情況下，RD代價的第二項中的MVP可以上相鄰塊或子塊的運動矢量的函數(單一 MVP)。在某些情況下， 對於當前塊中的所有(或者基本上所有)子塊，利用相同的(或類似的)MVP。綜上所述，系統100 (及其相關情況)，也被稱為率失真優化的單一 MVP偏置的全搜索(RDOMFS)，使用單一 MVP，並通過計算RD代價方程來進行搜索，即使用單一 MVP偏置和RD 代價方程(也成為成本函數)。在某些情況下，RDOMFS可以取得與FS-RD-var-mvp (H. 264 參考軟體JM中默認的運動估計算法)相當的率失真效率，並超過FS-SAD-var-zero的率失真效率。例如，在最新的H. 264標準的參考軟體JM中採用了幾種率失真效果很好並且計算複雜度低的快速運動估計算法。大部分快速運動估計算法使用MVP作為起始搜索點，並採用了局部搜索模式如鑽石搜索、六邊形搜索。一般來說，快速運動估計算法首先會計算幾個可能的候選MVP的代價，並從中選出一個作為搜索起始點。採用局部搜索可能導致局部最優的MV而不是全局最優的MV。使用多個MVP可以有效的提高全局最優的概率。一般來說，這些快速運動估計算法中所使用的MVP是通過空域或時域相鄰塊的MV 得到的。時域相鄰的MV既是參考幀中同一位置的塊的MV，這需要存儲參考幀中的塊的MV。 空域相鄰的MV則包括左邊、上方、右上方的子塊。由這三個MV來推導MVP，例如中值。注意在H.沈4中，對於左邊、上方、右上方的塊的定義可能根據子塊大小的不同而不同，並且對於不同位置上的大小相同或基本相同的子塊來說可以不同。所以，需要大量的存儲單元來存儲所有大小的子塊的MV。圖2A以子塊大小為4x4及16x16為例。另外，計算中值的數據流也是不規則的。具體的來說，使用多個MVP會造成不利於硬體實現的結果。這是因為，第一，如圖 2B所示，空域上的對於左邊、上方、右上方子塊的定義是不同的，這會導致不規則的數據流。 第二，在選擇MVP時，整體硬體的效率會下降，並不利於有效的流水線設計。第三，注意多個 MVP可能分布在搜索區域的不同位置，因此，對應多個MVP的參考像素是單獨加載的，不能被再利用，這會造成存儲器帶寬的增加。第四，需要存儲大量的MV，導致顯著的片上存儲器需求和成本。為了使算法更加易於硬體實現，本發明提出的RDOMFS中使用了一種單一的運動矢量預測(SMVP)來替代多個運動矢量預測。在一個宏塊中，對於所有的不同大小的子塊 (或者基本上所有的子塊和/或基本上所有的大小)使用統一的SMVP定義。使用符號 MV16>U6來表示16X16模式下的最優運動矢量，那麼SMVP可以被定義為SMVP =胸也咖(Μ ^, MlC^(3)它是相鄰的左，上，右上的三個宏塊的MV16xi6的中值，如同圖2C所示。也就是說， 在同一宏塊中的任意位置上的不同大小的所有的子塊(或基本上所有的子塊)都使用相同的或基本上相同的SMVP。雖然使用單一MVP會使得陷入局部最小的概率增大，當使用多個MVP的時候，局部最小與全局最小相同的概率會更高，但是實際上的效果只有微小的區別。並且，本發明所披露的SMVP可以有效地解決上述問題並帶來一系列的益處。例如，雖然所披露的SMVP是基於空域上相鄰的宏塊的MV，但由於不同大小的所有子塊都使用相同的(或大致相同的) SMVP定義，使得數據流更加規則。其二，由於使用了 SMVP，也就實際上省略了從多個MVP中選擇最終MVP的過程，使得算法更加便於流水線設計。實際上由於只存在一個候選，所以不存在MVP選擇階段。其三，同所披露的MVP再利用架構相配合，SMVP不需要存儲大量已得到的MV，可以極大的減少片上內存的需求，將會在隨後詳細討論。由於涉及規則的局部搜索，因此不同的快速運動估計(FME)算法會使用不同的迭代局部搜索，並使用不同的局部搜索模式，例如矩形搜索，菱形搜索，六邊形搜索，環狀搜索等。在每一次迭代中，快速運動估計算法根據所使用的搜索模式計算搜索點的誤差，並據此選擇最優的下一次迭代的搜索中心。估計的誤差可以使用SAD或RD。在不同迭代和不同方向上，可以使用不同的步長。在快速運動估計算法中，快速結束是一種使得搜索在一定前提下提前結束的技術。如果沒有使用快速結束技術，那麼快速運動估計算法將繼續直到完成所有的迭代，或搜索模式的中心為下一迭代的起始搜索點。上文所提到的局部搜索有著很大的缺點。例如，這樣的貪婪算法會使得搜索相對於局部全搜索率失真性能下降。其二，在各個搜索模式的搜索點中與候選相關的像素值需要被單獨讀取，無法再利用，這將導致巨大的存儲器帶寬消耗和時延。其三，由於每次迭代選擇的新起始點是不可預計的，這將導致不規則的數據流和不易於硬體實現。同樣，使用快速結束技術和不同步長也會導致這個問題。為了解決這些與規則局部搜索相關的問題，披露的RDOMFS使用了一種基於MVP的預測局部全搜索。因此，RDOMFS是FS-MVP。如上所述，在兩種常見的誤差估計方法SAD和RD之間是存在著一種關係的。SAD 的計算相對簡單且易於硬體實現，現存的絕大多數的ME硬體架構都是基於SAD的。另一方面，RD被定義為
RD (MV) = SAD (MV) + λ ^p) R (| MVmedian-MV |)(4)其中MV為候選MV，λ是拉格朗日算子(Lagrange multiplier)，其隨量化因子Qp 變化而變化，MVmedian是H. 264中的MV編碼使用的中值運動矢量預測，R是比特速率，用來編碼運動矢量誤差的。在HJ64JM參考軟體中，λ也就是λΜΕ被定義為
權利要求
1.一種方法，包括將一個或多個由多個塊創建的視頻幀劃分成多個子塊；確定在一個或多個視頻幀中的參考幀；將多個子塊的一個搜索區域定義為多個運動矢量預測(MVP)的函數，其中包括將搜索區域集中在在參考幀內定義的位置周圍；以及搜索多個子塊中的至少一個子塊，包括確定率失真(RD)代價，並根據率失真代價選擇相應的運動矢量作為所述至少一個子塊的運動矢量(MV)。
2.根據權利要求1所述的方法，其中確定率失真代價的步驟包括確定代價函數中的兩個可加項，第一個可加項為當前子塊和候選參考子塊之間的失真度量，第二個可加項為lambda算子與候選運動矢量和運動矢量預測之間的差值的函數這二者的乘積，所述 lambda算子是子塊大小和位置、塊位置和類型、量化參數、目標碼率、及緩存條件或者緩存性能中的至少一個的函數。
3.根據權利要求2所述的方法，其中確定第二可加項的步驟包括將第二可加項確定為相鄰塊或相鄰子塊的運動矢量的函數。
4.根據權利要求1所述的方法，還包括將多個運動矢量預測確定為多個相鄰塊或相鄰子塊的運動矢量的函數，以及其中定義搜索區域的步驟包括將將搜索中心確定為多個運動矢量預測的函數。
5.根據權利要求4所述的方法，還包括將多個運動矢量預測中的一個運動矢量預測指定作為左方的塊、上方的塊和右上方的塊上的塊運動矢量的中值。
6.根據權利要求1所述的方法，其中確定搜索區域的步驟包括將搜索中心確定為三個過去的相鄰塊的運動矢量的中值，這三個過去的相鄰塊包括在左邊的第一塊、在上方的第二塊、和在右上方的第三塊。
7.根據權利要求6所述的方法，還包括在第一塊、第二塊、或者第三塊中的一個不存在時確定至少一個替代塊。
8.根據權利要求7所述的方法，其中確定至少一個替代塊包括選擇左上角位置的第四塊。
9.一種系統，包括分割元件，將一個視頻幀分成多個塊；子分割元件，將多個塊劃分成多個子塊；選擇元件，從多個子塊中選擇參考幀；歸類元件，確定一個包括搜索中心的搜索區域，其中該搜索區域基於多個運動矢量預測；以及評估元件，為搜索區域中所選的搜索點計算率失真(RD)代價函數，以為多個子塊選擇一個運動矢量(MV)。
10.根據權利要求9所述的系統，其中率失真代價函數包括第一元素和第二元素，其中第一元素是一種失真度量，第二元素是一個參數與一個候選運動矢量和多個運動矢量預測中的一個運動矢量預測之間的差值的函數的乘積。
11.根據權利要求10所述的系統，其中所述參數是lambda，其是子塊大小和位置、塊位置和類型、量化參數、目標碼率、緩存條件和緩存性能的函數。
12.根據權利要求10所述的系統，所述參數是lambda，並且lambda可以近似成2的冪的線性組合。
13.根據權利要求10所述的系統，其中第二元素的運動矢量預測是過去的相鄰塊的運動矢量的函數。
14.根據權利要求10所述的系統，其中第二元素的運動矢量預測是與當前塊相關的左邊、上方和右上方的過去的相鄰塊的運動矢量的函數。
15.根據權利要求10所述的系統，其中第二元素的運動矢量預測是與當前塊相關的左邊、上方和右上方的過去的相鄰塊的運動矢量的中值。
16.根據權要求10所述的系統，其中搜索區域對應於當前塊或當前子塊與參考幀中同樣大小的候選參考塊或者候選子塊之間的候選運動矢量。
17.根據權利要求10所述的系統，其中搜索中心是運動矢量預測。
18.根據權利要求9所述的系統，其中搜索中心是所確定的三個過去的相鄰塊的運動矢量的中值。
19.根據權利要求18所述的系統，其中三個過去的相鄰塊包括和當前塊相關的一個左邊的塊、一個上方的塊和一個右上方的塊。
20.一種方法，包括從多個視頻幀中確定參考幀；在該參考幀中確定包括多個搜索點的搜索區域；將搜索區域劃分成多個子窗口 ；以及處理多個幀視頻，處理多個視頻幀包括在多個子窗口中確立掃描順序，每一個子窗口至少被掃描一次，並且兩個掃描順序相鄰的子窗口在空間上相近。
21.根據權利要求20所述的方法，其中掃描多個子窗口的步驟包括執行水平掃描、豎直掃描、或同時執行水平掃描和豎直掃描。
22.根據權利要求20所述的方法，還包括在參考幀中確定包括多個搜索點的搜索區域之前將視頻幀分成包含NxN個像素的塊；以及其中所述處理步驟包括在一個時鐘周期內並行讀取N個像素並且將這些像素一次性加載到子窗口內。
23.根據權利要求20所述的方法，其中掃描多個子窗口的步驟包括用從16種不同蛇形掃描中所選擇的至少1種蛇型掃描來進行掃描。
24.根據權利要求20所述的方法，其中掃描多個子窗口的步驟還包括用第一種類型的蛇形掃描來掃描第一子窗口；移動到第二子窗口中的相鄰搜索點；以及用第二種類型的蛇形掃描來掃描第二子窗口。
25.根據權利要求20所述的方法，其中將搜索區域劃分成多個子窗口的步驟包括將搜索區域劃分成一些不相互覆蓋的矩形子窗口。
26.根據權利要求20所述的方法，其中掃描多個子窗口的步驟包括使用從搜索窗口的左上角、右上角、左下角、或右下角開始的掃描來定義掃描順序，以及其中所述掃描是水平掃描或者豎直掃描。
27.根據權利要求20所述的方法，其中掃描多個子窗口的步驟包括將搜索區域劃分為多個子區域，並且在多個子區域中局部地應用蛇形掃描。
28.一種系統，包括選擇元件，用來確定參考幀；指定元件，用來在參考幀中定義搜索區域；子分割元件，用來將搜索區域分割為多個子窗口 ；以及掃描元件，用來選擇多個子窗口之間的掃描順序，每一個子窗口至少被掃描一次，並且掃描順序相鄰的兩個子窗口在空間上是接近的。
29.根據權利要求觀所述的系統，其中掃描元件構造為對多個子窗口執行水平掃描、 豎直掃描、或同時執行水平掃描和豎直掃描。
30.根據權利要求觀所述的系統，其中所述掃描元件構造為執行其中在第一方向上水平掃描第一行而在第二方向上水平掃描第二行的水平掃描。
31.根據權利要求觀所述的系統，其中掃描元件被構造為執行其中在第一方向上豎直掃描第一列而在第二方向上豎直掃描第二列的豎直掃描。
32.根據權利要求觀所述的系統，其中掃描元件被構造為選擇掃描順序，該掃描順序包括從搜索區域的左上角、右上角、左下角、右下角開始的蛇形掃描，以及其中蛇形掃描使用水平掃描或豎直掃描。
33.根據權利要求觀所述的系統，其中搜索區域中的多個點對應於當前塊和參考幀中相同大小的候選參考塊之間的候選運動矢量。
34.根據權利要求觀所述的系統，其中子分割元件被構造為將搜索區域分割成多個矩形的子窗口，以及其中搜索區域中的多個搜索點屬於多個子窗口。
35.根據權利要求觀所述的系統，還包括數據總線，其配置為在一個時鐘周期中並行讀取N個像素，其中參考幀的塊包括NxN個像素；以及可重構寄存器陣列，用來存儲一行的數據以用在下一行中，其中N個像素一次加載到多個子窗口中。
36.根據權利要求觀所述的系統，其中掃描元件被構造為從16種不同的蛇形掃描中選擇掃描順序，其中第一組蛇形掃描針對豎直掃描，而第二組蛇形掃描針對水平掃描。
37.根據權利要求觀所述的系統，其中掃描元件被構造為選擇一種掃描順序，該掃描順序將搜索區域分割成多個子區域，並在多個子區域中局部應用蛇形掃描。
38.一種方法，包括從一組視頻幀中確定多個參考幀，從多個參考幀中獲取第一運動矢量預測(MVP)和第二運動矢量預測(MVP)；在多個參考幀中定義搜索區域，該搜索區域以第一運動矢量預測或者第二運動矢量預測為中心；基於第一運動矢量預測和第二運動矢量預測進行子塊的運動估計；以及從多個參考幀的子塊中選擇運動矢量。
39.根據權利要求38所述的方法，其中獲取第一運動矢量預測和第二運動矢量預測的步驟包括基於過去的塊的運動矢量獲取第一運動矢量預測和第二運動矢量預測。
40.根據權利要求38所述的方法，獲取第一運動矢量預測或獲取第二運動矢量預測包括獲取當前塊的相鄰左塊的運動矢量的中值、相鄰上塊的運動矢量的中值或相鄰右上塊的的運動矢量的中值。
41.根據權利要求38所述的方法，其中執行運動估計包括執行單一運動矢量預測，僅僅使用第一運動矢量預測或者第二運動矢量預測中的一個。
42.根據權利要求41所述的方法，還包括以第一運動矢量預測或第二運動矢量預測為中心，進行局部全搜索運動估計。
43.根據權利要求38所述的方法，其中執行運動估計包括計算代價函數，該代價函數包括多個可加項，其中包括失真項和lambda參數與編碼運動矢量的碼率函數的乘積項，其中lambda參數為子塊的大小和位置、塊位置和類型、量化參數、目標碼率、及緩存條件或緩存性能中的至少一個的函數。
全文摘要
本發明提供了一種圖像運動估計的方法及系統。提供了一種子塊運動估計，其包括在運動矢量預測周圍的減少搜索範圍的完全搜索。還提供了一種單一的(或統一)運動矢量預測和一種類似率失真成本函數的函數。還提供了一種能夠降低或基本上消除多餘的數據裝載和/或實現不同的數據復用率的掃描順序。而且，還提供了一種基於單一運動矢量預測和類似於率失真代價函數的函數的可重構多解析度運動矢量重用硬體體系結構。此外，通過利用所披露的方面，只有一小部分過去的運動矢量被傳播，且這些方面可以很容易地對不同空間解析度的視頻重新配置。
文檔編號H04N7/26GK102263947SQ20111014169
公開日2011年11月30日 申請日期2011年5月27日 優先權日2010年5月27日
發明者區子廉, 聞興, 須江 申請人:香港科技大學