基於正交分布模型的快速運動估計方法
2023-08-13 09:26:11
專利名稱：基於正交分布模型的快速運動估計方法
技術領域：
本發明涉及視頻編碼技術領域，特別是基於正交分布模型的快速運動估計方法。
背景技術：
目前流行的視頻編碼標準如國際電信聯盟(ITU)制定的H系列和國際標準組織(ISO)制定的MPEG系列採用的都是基於塊匹配的混合編碼模型。視頻數據壓縮通過去除掉相鄰塊或者是相鄰幀之間的空間或者時間冗餘，以減少存儲空間或者傳輸帶寬。運動估計通過運動矢量搜索得到運動矢量的最佳估計。運動搜索分為整像素運動搜索和子像素運動搜索。眾所周知的，全搜索方法的精度最高，但是其運算量大，實現複雜度高，故在一定的重建圖像質量的要求下，可以設計快速整像素運動搜索方法來達到加速運動搜索的目的。目前最優秀、最具有代表性的快速整像素運動搜索方法有鑽石形搜索法(DS)以及六邊形搜索法(HEXBS)。
一般整像素運動搜索方法的處理過程是，對於圖像序列當前幀中給定的圖像數據塊(連續像素點組成的矩形塊)，在圖像序列其它重建圖像幀(參考幀)的某個大小的搜索窗口中按照一定最佳匹配準則搜索最佳匹配塊。搜索窗口範圍相對於當前幀中的當前塊的中心位置為中心，範圍分別定義為wx和wy，則其窗口大小為(2wx+1)*(2wy+1)。如果wx＝wy＝w，則稱搜索窗±w。上述的最佳匹配的準則有多種定義，目前大多採用的是代價函數SAD，如式1所示SAD(P)=i=0N-1j=0M-1|f(i,j,t)-f(i-x,j-y,t-1)|---(1)]]>式(1)中NxM是當前塊(當前塊中待匹配的圖像塊)的大小，也是參考幀中搜索塊(參考幀中的圖像數據塊)的大小；f(i，j，t)是t時刻的圖像幀在(i，j)坐標位置處的像素的亮度值；(x，y)表示當前塊位置指向參考幀中像素點P位置的運動矢量的兩個分量。
前面提到，目前速度與搜索精度表現最為優秀的快速算法的主要代表有鑽石形搜索法(DS)和六邊形搜索法(HEXBS)。下面先分別介紹這兩種方法的搜索過程。
鑽石形搜索法(DS)的搜索模板以及搜索策略如圖1所示，六邊形搜索法(HEXBS)的搜索模板以及搜索策略如圖2所示。由於兩者在搜索算法上非常類似，所不同的只是搜索模板的選取，故下面以六邊形搜索法(HEXBS)為例來說明其搜索過程(1)以當前塊為中心，搜索六邊形模板的6個點，得到6個代價函數值。在這6個代價函數值與起始點的代價函數值中，代價函數值最小者為最佳匹配點。如果最佳匹配點處於六邊形的中心，則轉到第三步，否則到第二步；(2)以前一步搜索得到的最佳匹配點為起始點，搜索六邊形模板的6個點(此時已經搜索過的點並不再進行搜索)，得到6個代價函數值。在這6個代價函數值與起始點的代價函數值中，代價函數值最小者為最佳匹配點。如果最佳匹配點位於六邊形的中心，則轉到第三步，否則重複這一步；(3)以前一步搜索得到的最佳匹配點為起始點，搜索鑽石形模板的4上點得到4個代價函數值，取該4個代價函數值與起始點的代價函數值最小者為最佳匹配點，最佳匹配點對應的運動矢量即為最終的運動矢量。
由圖1可以看出當鑽石形搜索法(DS)大模板共有9個搜索點，如果第一級大模板搜索結束後的最佳匹配點位於角點和邊點時，新增搜索點數目是不相同的，當前一步搜索位於大模板的角點時，下一步新增加5個搜索點；當前一步搜索最佳匹配點位於大模板的邊點時，下一步新增加3個搜索點。而由圖2C和圖2D發現，鑽石形搜索法(HEXBS)的大模板共有七個搜索點，而且無論第一步搜索後的最佳匹配點是在六邊形上的任何一點時，在下一步搜索都只是增加3個搜索點。從以上兩點可以看出，鑽石形搜索法(DS)在搜索點數上比六邊形搜索法(HEXBS)要少，而且對於不同運動的序列，鑽石形搜索法(DS)在搜索點數上要比六邊形搜索法(HEXBS)要波動得大。
但是即使是目前快速運動搜索算法中最優秀、最具有代表性的菱形搜索算法(DS)和六邊形搜索算法(HEXBS)，在一定重建圖像質量的情況下，其運動搜索部分所耗費的計算量仍然是整個編碼器所耗費計算量的60％以上。
發明內容
為解決現有技術中存在的問題，本發明提供了一種用於視頻壓縮的快速運動搜索方法，既達到大幅度提高搜索速度的目的，又保證與現有快速運動估計算法(DS、HEXBS等)相當的搜索精度，但該方法並不僅僅局限於提供了一種快速運動搜索的方法，還提供了一種運動矢量的分布特性，運用該特性，還可與現在的快速運動搜索方法(如DS、HEXBS等)相結合，進一步對現在的算法性能進行提升。
本發明的一個方面，提出了一種新的研究運動矢量分布特性的方法，根據誤差曲面分布具有局部的特徵，而沒有全局的特徵的表示，本發明摒棄了一般的採用誤差曲面分布作為研究運動矢量分布特性的研究對象的方法，而是直接採用，更具有一般的能夠全面的反映運動矢量分布的方法，即採用所有的運動矢量來研究運動矢量的統計分布規律。
根據本發明的另一個方面，提出了一個運動矢量分布的一個正交分布模型，這是一個基於統計的分布模型。其提出的依據是因為全搜索的精度最高，通過採用全搜索所得到的大量的運動矢量作為研究對象，統計其分布的規律；考慮到現有的快速運動搜索算法都會不可避免的陷入局部最優點，我們可以對這個運動矢量的分布進行一個理想化，通過把絕大部分的運動矢量的分布都包括在分布模型當中，而把極少量的運動矢量的分布情況排除在外，這樣我們可以得到一個運動矢量的基於正交分布的理想分布模型。
根據本發明的另一個方面，根據本發明提出的正交分布模型，提出了一種與現有二級搜索方法不同的搜索方法。本發明提出了一種新的搜索方法，在該搜索方法裡，首先搜索中心處周圍的搜索點，這與現有的傳統搜索方法是一致的，但是在這一步搜索過後，根據當前搜索的最佳匹配點的位置，分別對於兩個正交方向採用各自的搜索模板，再次分別進行二級搜索，即是一種現有的二級搜索方法裡面嵌套另一種二級搜索的方法。其中嵌套的二級搜索方法是根據正交分布模型而採用的搜索方法，具有搜索點數少，方向明確且快速定位的特徵。
本方法的主要思想是通過對全搜索得到的運動矢量分布進行統計分析找出其分布規律，建立一個運動矢量的理想分布模型，並依照該模型設計了相應的搜索模板與搜索策略。該方法在保證編碼質量與編碼後的比特率與現有的方法相當的情況下，大大提升搜索速度。在保證搜索精度的前提下大幅度降低視頻壓縮中運動搜索時平均每塊的搜索點數。
技術方案一種基於運動矢量理想正交分布模型的快速整像素運動搜索方法，包括搜索模板的選擇依據於正交分布模型，利用運動矢量的正交分布特性，快速定位到最優點的附近，在各級搜索模板所對應的多個運動搜索點上進行運動搜索；根據運動搜索的結果找到多個運動搜索點中最小的運動搜索點；再根據這個最小的運動搜索點在第一級(初始)搜索模板中所處的位置來決定下一步運動搜索所採用的搜索模板。
所述的基於運動矢量理想正交分布模型的快速整像素運動搜索方法，首先搜索中心處周圍的搜索點，這一步搜索過後，根據當前搜索的最佳匹配點的位置，分別對於兩個正交方向採用各自的搜索模板，再次分別進行二級搜索，即二級搜索方法裡面嵌套另一種二級搜索的方法，其中嵌套的二級搜索方法是根據正交分布模型而採用的搜索方法。
所述的基於運動矢量理想正交分布模型的快速整像素運動搜索方法，依據第一級最佳匹配點的位置，其搜索可分為二級或者三級搜索，具體如下(a)將上一級搜索得到的最佳匹配點作為本級搜索的起始點，再依據該點是在上一級搜索模板中的位置決定採用下一級的搜索模板；
(b)如果採用初始模板搜索得到的最佳匹配點位於初始搜索模板的中心點，則以該點為本級搜索的起始點，直接採用最終搜索模板進行最終的精細搜索，得到每個點的代價函數值，代價函數值最小者即為最終的運動矢量；(c)如果採用初始模板搜索得到的最佳匹配點位於初始搜索模板的垂直或者水平方向上的位置時，則以該點作為本級搜索的起始點，直接在垂直或者水平軸向上進行快速搜索定位到最接近最終運動矢量的位置，該點為最終搜索模板的中心進行搜索，如果最終搜索模板搜索的最佳匹配點位置不在中心時，就以上級搜索得到的最佳匹配點作為最終搜索模板的中心，重新進行最終模板搜索，直到搜索得到的最佳匹配點位於最終搜索模板的中心為止。
所述的基於運動矢量理想正交分布模型的快速整像素運動搜索方法，所說的模板選取突出了方向的特徵，所說的模板定義如下首先定義一個基本的5點菱形搜索模板，也就是本發明的初始搜索模板，此模板上的各點的坐標集合ΩO-5為ΩO-5＝{(x，y)|(±2，0)，(0，±2)，(0，0)}當搜索初始搜索模板的5個搜索點後，得到5個代價函數，如果代價函數值最小對應的搜索點在第一級的5個搜索模板的中心時，則直接搜索下述的小菱形搜索模板即方法中所說的最終搜索模板，該模板搜索後得到的最佳匹配點即為最終的運動矢量所指向的塊，這個小菱形搜索模板的各點的坐標集合Ωoo-5為Ωoo-5＝{(x，y)|(±1，0)，(0，±1)，(0，0)}當搜索完初始搜索模板的5個搜索點後，得到5個代價函數，如果代價函數最小對應的搜索點在初始搜索模板的水平或者垂直方向上時，則分別採用以下模板進行搜索，水平和垂直方向上的搜索模板分別定義如下Ωh-2＝{(x，y)|(0，0)，(±2，0)}Ωv-2＝{(x，y)|(0，0)，(0，±2)}在水平和垂直方向搜索過後，最後一級採用的與初始搜索後最佳匹配點在中心時的搜索模板一致，即均為Ωoo-5，只是考慮到最佳匹配點在初始搜索模板過後，最終的匹配塊就中心點附近，故一次搜索即可，而水平或者垂直方向搜索後，只是搜索到一個在軸向上比較接近最終匹配塊的位置，故要一直搜索到最佳匹配塊位於模板中心為止。故最後一級搜索的模板均為Ωoo-5，只是不同位置採用的策略不同。
所述的基於正交模型的快速整像素運動搜索方法，所述的搜索策略，具體如下(a)以當前位置為起點，搜索初始搜索模板的5個點，得到5個搜索點的代價函數值；取代價函數值最小者為本步驟最佳匹配點，作為下一步搜索的起點；如果最佳匹配點在初始搜索模板的中心，則轉到步驟(b)；如果最佳匹配點在初始搜索模板的水平方向兩點時，轉到步驟(c)；如果最佳匹配點在初始大菱形搜索模板的垂直方向兩點時，轉到步驟(d)；(b)以前一步搜索所得的最佳匹配點作為起始點，搜索最終搜索模板的5個點，得到5個搜索點的代價函數值；代價函數值最小的點即為最終的運動矢量所指向的點，搜索終止；(c)以前一步搜索所得的最佳匹配點作為起始點，搜索水平方向搜索模板的3個點，得到3個搜索點的代價函數值，取代價函數值最小者為本步驟最佳匹配點；如果本步驟的最佳匹配點不位於中心點，則轉到步驟(c)；如果本步驟的最佳匹配點位於中心點，則轉到步驟(e)；(d)以前一步搜索所得的最佳匹配點作為起始點，搜索垂直方向搜索模板的3個點，得到3個搜索點的代價函數值，取代價函數值最小者為本步驟最佳匹配點；如果本步驟的最佳匹配點不位於中心點，則轉到步驟(d)；如果本步驟的最佳匹配點位於中心點，則轉到步驟(e)；(e)以前一步搜索所得的最佳匹配點作為起始點，搜索最終搜索模板的5個點，得到5個搜索的代價函數值，代價函數值最小的點即為本步驟所得的最佳匹配點；如果本步驟的最佳匹配點不位於中心點，則重複步驟(e)；如果本步驟的最佳匹配點位於中心點，則此最佳匹配點即為最終的運動矢量所指向的點，搜索終止。
隨後的詳細說明及附圖將更全面的闡述本發明，但是它們不應該被理解為將所附權利要求限制為所示出的具體實施，而僅僅是用於解釋和理解。
圖1A示出了鑽石形搜索法的第一級搜索模板圖。
圖1B示出了鑽石形搜索法的第二級搜索模板他圖。
圖1C示出了鑽石形搜索法第一級搜索後的最佳匹配點位於角點時的搜索策略圖。
圖1D示出了鑽石形搜索法第一級搜索後的最佳匹配點位於邊點時的搜索策略圖。
圖2A示出了六邊形搜索法的第一級搜索模板圖。
圖2B示出了六邊形搜索法的第二級搜索模板他圖。
圖2C示出了六邊形搜索法第一級搜索後的最佳匹配點位於水平方向點時的搜索策略圖。
圖2D示出了六邊形搜索法第一級搜索後的最佳匹配點位於垂直方向上的點時的搜索策略圖。
圖3示出了基於正交分布模型的整像素快速運動搜索的搜索流程圖。
圖4示出了基於正交分布模型的整像素快速運動搜索方法的搜索模板圖。
圖5示出了基於正交分布模型的整像素快速運動搜索方法的搜索策略示意圖。
圖6示出了一個正交搜索方法的搜索實例。
具體實施例方式
這裡公開了一種基於正交分布模型的快速整像素搜索方法。用於進行正交分布模型的快速整像素搜索方法的一個實施例包括以下操作在各級搜索模板所對應的多個運動搜索點上進行運動搜索；根據運動搜索的結果找到多個運動搜索點中最小的運動搜索點；再根據這個最小的運動搜索點在初始搜索模板中所處的位置來決定下一步運動搜索所採用的搜索模板。
接下來將詳細描述基於正交分布模型的快速整像素搜索方法參見圖3。
首先是選擇搜索的起始點，起始點的選擇是一個單獨的內容，在本發明中，採用的是以當前塊位置為搜索的起始點，而為了提高搜索的精度，可以加入現有的任何一種初始運動矢量預測算法，這並不影響本發明在同等條件下與同類算法的性能比較；其次就是搜索模板的設計以及搜索策略，在本發明中，為了體現出本發明所強調的運動矢量的分布是具有非常明顯特徵的特點，在本發明中提到的模板是直接採用具有上下左右四個搜索點外加一個中心點的菱形搜索模板，但本發明在這裡所要表示的是一種方法，是一種具有方向搜索的方法，並不表示局限於此模板；再次就是本發明分別針對第一級搜索後最佳匹配點的位置，分別採用了不同的搜索策略。
附圖詳細步驟說明1.以當前搜索窗的中心採用初始搜索模板進行搜索，得到MBD點，依據MBD點在初始搜索模板中的位置分別採用不同的搜索模板和搜索策略，如圖中步驟一；2.若MBD點位於初始搜索模板的中心，則採用最終搜索模板再進行一次搜索，這步得到的即為最終的運動矢量，搜索終止，如圖中步驟二；3.若MBD不位於初始搜索模板的中心，根據本方法提出的一個運運矢量正交分布的模型，則需要在水平或者是垂直方向快速定位到最佳匹配塊的附近，這一步即圖中所示的水平方向(如圖中步驟三)或者垂直方向搜索(如圖中步驟四)，這也是本方法所提到的一個在二級搜索裡再嵌套的另一個二級搜索。
4.本方法中，初始搜索得到的點位置不同導致接下來的搜索模板不同和搜索策略不同，還表現在最終搜索模板的處理上，初始模板搜索後，若MBD點位於中心，則僅僅再搜索一次最終搜索模板即可，而為了提高精度，本方法對於水平或者垂直方向的搜索後，採用的最終搜索卻是要一直迭代(如圖中步驟五所示)，直到MBD點位於最終搜索模板的中心點才終止搜索。
圖4示出了基於正交分布模型的整像素快速運動搜索方法的搜索模板圖。其中(a)，(b)為對應於中心點的二級搜索模板，(c)，(d)為對應於第一級搜索後的最佳匹配點位於水平方向時的二級搜索模板，(e)，(f)為對應於第一級搜索後的最佳匹配點位於垂直方向時的二級搜索模板。
圖5示出了基於正交分布模型的整像素快速運動搜索方法的搜索策略示意圖。其中(a)表示第一級搜索後最佳匹配點位於中心位置時的搜索策略，(b)表示第一級搜索後最佳匹配點位於水平邊點時的搜索策略，(c)表示第一級搜索後最佳匹配點位於垂直邊點時的搜索策略。
這一過程將在下面通過兩個具體的實施例詳細說明首先分析第一步搜索後最佳匹配點位於中心位置的實施例，如圖5(a)所示，首先搜索初始搜索模板的5個點，即圖5(a)中的圓形實心點，比較5個點所得的最小誤差值，取值最小的作為該步所得的最佳匹配點，若最佳匹配點位於中心位置，則採用小菱形模板即圖5(a)中的方形實心點，作為最終搜索模板，該步搜索後的最佳匹配點即為最終的運動矢量所對應的塊。
說明圓點為第一步搜索點，正方形點為第二步搜索點下面著重以一個具體的實施例來說明第一級搜索後最佳匹配點不在中心位置時的搜索過程。在附圖6中，若最終要搜索到的運動矢量為(+4，-4)。首先，採用如圖4(a)所示的初始搜索模板進行第一級搜索後，該步搜索所得的最佳匹配點位於垂直軸上的點，如圖6中的第一步所示的(0，-2)點，接下來，採用圖4(d)所示的垂直搜索模板在軸向上進行搜索，快速定位到最接近的軸向位置上，如圖6中的(0，-4)點，此時因為該步搜索所得的最佳匹配點位於圖4(d)垂直搜索模板的中心位置，故以當前的最佳匹配點為中心位置，改用圖4(b)所示的最終搜索模板搜索，如果其最佳匹配點不在小菱形的中心位置，則以該最佳匹配點作為新的最終搜索模板的中心，重新搜索該最終搜索模板，直到最佳匹配點位於小菱形搜索模板的中心為止，此時最終搜索所得的最佳匹配點如圖6中的(4，-4)點。更詳細的過程，參照附圖6。
搜索過程描述首先搜索初始搜索模板的五個搜索點(圖中第1步所示)，其MBD點為垂直方向角點時，採用垂直搜索模板，此時僅新增一個搜索點(圖中第2步所示)，若該步後，所得的MBD點不位於垂直搜索模板的中心點，則繼續以上步所得的MBD點作為新的垂直搜索模板的中心，繼續搜索(圖中第3步所示)，若搜索所得的MBD點位於當前垂直搜索模板的中心點時，則採用最終模板(圖中第4步所示)，此時新增4個搜索點，若搜索後所得的MBD點不是當前搜索模板的中心，則以當前的MBD點為中心繼續採用最終搜索模板進行搜索，直到搜索所得的MBD點位於中心時，搜索終止。
(搜索過程最終定位於運動矢量為(+4，-4))前述的一些討論僅僅描述了本發明的一些示例實施例。從這樣的討論、附圖和權利要求中，本領域的技術人員將容易認識到，在不脫離所附權利要求的精神和範圍的要求下，可以進行各種修改。因而，本說明應被看作是說明性的而不是限制性的。
本發明方法在H.264的測試平臺JM96基礎上進行了實驗，選擇了具有代表性的解析度從QCIF(176×144)到CIF(352×288)，運動劇烈程序從緩慢到劇烈的各種序列進行了測試，本發明的實驗結果表明在各種參數配置(如參考幀數、量化參數、搜索範圍等)的情況下，本發明方法與DS相比，平均psnr以及bit-rate，基本相當，搜索點數比DS下降了45％左右；與HEXBS相比，平均psnr值基本相當，bit-rate略有下降，搜索點數下降了25％左右。實驗結果還表明，本發明方法在量化參數變化的情況下，在平均每塊搜索點數上，比DS、HEXBS具有更好的魯棒性。
權利要求
1.一種基於運動矢量理想正交分布模型的快速整像素運動搜索方法，其特徵在於，包括搜索模板的選擇依據於正交分布模型，利用運動矢量的正交分布特性，快速定位到最優點的附近，在各級搜索模板所對應的多個運動搜索點上進行運動搜索；根據運動搜索的結果找到多個運動搜索點中最小的運動搜索點；再根據這個最小的運動搜索點在第一級初始搜索模板中所處的位置來決定下一步運動搜索所採用的搜索模板。
2.如權利要求1所述的基於運動矢量理想正交分布模型的快速整像素運動搜索方法，其特徵在於，首先搜索中心處周圍的搜索點，這一步搜索過後，根據當前搜索的最佳匹配點的位置，分別對於兩個正交方向採用各自的搜索模板，再次分別進行二級搜索，即二級搜索方法裡面嵌套另一種二級搜索的方法，其中嵌套的二級搜索方法是根據正交分布模型而採用的搜索方法。
3.如權利要求1所述的基於運動矢量理想正交分布模型的快速整像素運動搜索方法，其特徵在於，依據第一級最佳匹配點的位置，其搜索可分為二級或者三級搜索，具體如下(a)將上一級搜索得到的最佳匹配點作為本級搜索的起始點，再依據該點是在上一級搜索模板中的位置決定採用下一級的搜索模板；(b)如果初始模板搜索得到的最佳匹配點位於初始搜索模板的中心點，則以該點為本級搜索的起始點，直接採用最終搜索模板進行最終的精細搜索，得到每個點的代價函數值，代價函數值最小者即為最終的運動矢量；(c)如果初始搜索得到的最佳匹配點位於初始搜索模板的垂直或者水平方向上的位置時，則以該點作為新搜索模板的中心點，直接在垂直或者水平軸向上進行快速搜索定位到最接近最終運動矢量的位置，該點為最終搜索模板的中心進行搜索，如果最終搜索模板搜索的最佳匹配點位置不在中心時，就以上級搜索得到的最佳匹配點作為新的最終搜索模板的搜索中心，重新進行最終模板搜索，直到搜索得到的最佳匹配點位於最終搜索模板的中心為止。
4.如權利要求1或2所述的基於運動矢量理想正交分布模型的快速整像素運動搜索方法，其特徵在於，所說的模板選取突出了方向的特徵，所說的模板定義如下首先定義一個基本的5點菱形搜索模板，也就是本發明的初始搜索模板，此模板上的各點的坐標集合ΩO-5為ΩO-5＝{(x，y)|(±2，0)，(0，±2)，(0，0)}當搜索完初始搜索模板的5個搜索點後，得到5個代價函數，如果代價函數值最小對應的搜索點在第一級的5個搜索模板的中心時，則直接搜索下述的小菱形搜索模板，該模板搜索後得到的最佳匹配點即為最終的運動矢量所指向的塊，這個小菱形搜索模板的各點的坐標集合Ωoo-5為Ωoo-5＝{(x，y)|(±1，0)，(0，±1)，(0，0)}當搜索完初始搜索模板的5個搜索點後，得到5個代價函數，如果代價函數最小對應的搜索點在初始搜索模板的5個搜索模板的水平或者垂直方向上時，則分別採用以下模板進行搜索，水平和垂直方向上的搜索模板分別定義如下Ωh-2＝{(x，y)|(0，0)，(±2，0)}Ωv-2＝{(x，y)|(0，0)，(0，±2)}在水平和垂直方向搜索過後，最終搜索採用的初始搜索後最佳匹配點在中心時的搜索模板一致，即均為Ωoo-5，只是考慮到最佳匹配點在初始搜索模板過後，最終的匹配塊就中心點附近，故一次搜索即可，而水平或者垂直方向搜索後，僅搜索到一個在軸向上比較接近最終匹配塊的位置，故要一直迭代搜索直到最佳匹配塊位於模板中心為止。故最後一級搜索的模板均為Ωoo-5，只是不同位置採用的策略不同。
5.如權利要求3所述的基於正交模型的快速整像素運動搜索方法，其特徵在於，所述的搜索策略，具體如下(a)以當前位置為起點，搜索初始搜索模板的5個點，得到5個搜索點的代價函數值；取代價函數值最小者為本步驟最佳匹配點，作為下一步搜索的起點；如果最佳匹配點在初始搜索模板的中心，則轉到步驟(b)；如果最佳匹配點初始搜索模板的水平方向兩點時，轉到步驟(c)；如果最佳匹配點在初始搜索模板的垂直方向兩點時，轉到步驟(d)；(b)以前一步搜索所得的最佳匹配點作為起始點，搜索小菱形模板的5個點，得到5個搜索點的代價函數值；代價函數值最小的點即為最終的運動矢量所指向的點，搜索終止；(c)以前一步搜索所得的最佳匹配點作為起始點，搜索水平方向搜索大模板的3個點，得到3個搜索點的代價函數值，取代價函數值最小者為本步驟最佳匹配點；如果本步驟的最佳匹配點不位於中心點，則轉到步驟(c)；如果本步驟的最佳匹配點位於中心點，則轉到步驟(e)；(d)以前一步搜索所得的最佳匹配點作為起始點，搜索垂直方向搜索模板的3個點，得到3個搜索點的代價函數值，取代價函數值最小者為本步驟最佳匹配點；如果本步驟的最佳匹配點不位於中心點，則轉到步驟(d)；如果本步驟的最佳匹配點位於中心點，則轉到步驟(e)；(e)以前一步搜索所得的最佳匹配點作為起始點，搜索最終搜索模板的5個點，得到5個搜索的代價函數值，代價函數值最小的點即為本步驟所得的最佳匹配點；如果本步驟的最佳匹配點不位於中心點，則重複步驟(e)；如果本步驟的最佳匹配點位於中心點，則此最佳匹配點即為最終的運動矢量所指向的點，搜索終止。
6.如權利要求3所述的基於運動矢量理想正交分布模型的快速整像素運動搜索方法，其具體步驟步驟一，以當前搜索窗的中心採用初始搜索模板進行搜索，得到MBD點，依據MBD點在初始搜索模板中的位置分別採用不同的搜索模板和搜索策略；步驟二，若MBD點位於初始搜索模板的中心，則採用最終搜索模板再進行一次搜索，這步得到的即為最終的運動矢量，搜索終止；步驟三和步驟四，若MBD不位於初始搜索模板的中心，根據本方法提出的一個運運矢量正交分布的模型，則需要在水平或者是垂直方向快速定位到最佳匹配塊的附近，即水平方向或者垂直方向搜索，這也是本方法所提到的一個在二級搜索裡再嵌套的另一個二級搜索；步驟五，初始搜索得到的點位置不同導致接下來的搜索模板不同和搜索策略不同，還表現在最終搜索模板的處理上，初始模板搜索後，若MBD點位於中心，則僅僅再搜索一次最終搜索模板即可，而為了提高精度，對於水平或者垂直方向的搜索後，採用的最終搜索卻是要一直迭代，直到MBD點位於最終搜索模板的中心點才終止搜索。
全文摘要
本發明涉及視頻編碼技術領域，特別是基於正交分布模型的快速運動估計方法。包括搜索模板的選擇依據於正交分布模型，利用運動矢量的正交分布特性，快速定位到最優點的附近，在各級搜索模板所對應的多個搜索點上進行運動搜索；在運動搜索的結果找到搜索點中具有最小誤差的運動搜索點；再根據該最小誤差的運動搜索點在第一級搜索模板中所處的位置來決定下一步運動搜索所採用的搜索模板。
文檔編號H04N7/26GK1941909SQ200510105259
公開日2007年4月4日 申請日期2005年9月28日 優先權日2005年9月28日
發明者杜清秀, 鄭海波, 盧漢清 申請人:中國科學院自動化研究所