層級式運動估算方法
2023-11-02 07:13:37 2
專利名稱：層級式運動估算方法
技術領域：
本發明涉及影像處理，特別是有關於一種用以快速而準確計算運動向量的運動估 算方法。
背景技術：
運動估算(Motion Estimation; ME)是一種用在影像壓縮、影像辨識等方面的技 術，以增進視訊的畫面率(frame rate)。藉由利用運動估算，可估算一特定區塊在兩個畫 面之間的運動向量(Motion Vector; MV)，以排除運動影像的畫面之間的時間冗餘，從而增
進影像質量。利用運動估算進行影像解碼不需要每個區塊的運動向量都是正確的。然而，對於 畫面率上轉換(Frame Rate up-Conversion; FRC)，畫面的每個區塊的運動向量都必須是 正確的，以使動作影像能順暢顯示。近年來，隨著液晶屏幕被廣泛使用，FRC技術變得很重要。FRC技術是提升視訊的 畫面率以排除動作模糊以及影片晃動的現象。舉例而言，藉由利用FRC，影片原始視訊的畫 面率可以從60Hz提升到120Hz甚至到MOHz。為了達到高畫面率，必須計算額外的畫面。 如所述，可藉由利用運動估算計算原始畫面之間的正確運動向量。額外的畫面則利用運動 向量內插於原始畫面之間。為了快速且正確地估算原始畫面之間的運動向量，是在運動估算上應用動態搜尋 範圍以使高解析度視訊編碼可實時完成。動態搜尋範圍亦可應用於FRC以節省計算時間及 成本。圖IA顯示一畫面分割成九個區塊A至I。在此例中，區塊E為欲估算之當前區塊。 根據先前技術，對於當前區塊E而言，搜尋範圍是參考區塊A、B、C、D而決定，這些區塊A、B、 C、D的運動向量已經計算過。從這些周圍區塊找出在X軸與Y軸方向的最大運動向量分量 MVmX,、MVmY。當前區塊E的搜尋範圍是由這些最大運動向量分量MVmX，、MVmY決定。這些 計算可表示為
BlockMVE — BlockMVA, BlockMVB, BlockMVC, BlockMVD(1)
MVmX = max{abs(MVAX), abs(MVBX), abs(MVCX), abs(MVDX)}(2)
MVmY=max{abs(MVAY)，abs(MVBY), abs(MVCY), abs(MVDY)}(3)
有時搜尋範圍可稍微擴展S
MVEX之搜尋範圍=MVmX + δ；及
MVEY之搜尋範圍=MVmY + δ(5).
噹噹前區塊的運動向量與周圍區塊的運動向量非常不同時，運動估算會發生錯誤。圖 IB顯示該展示畫面之各區塊的運動向量。於此情形中，舉例而言，當前區塊5的運動向量明 顯大於周圍區塊1、2、3及4的運動向量，後者非常小。舉例而言，此種狀況會發生在當一個 對象在趨近靜態的背景中快速移動，或是在運動的對象邊緣有較大的運動向量變化。可以 想見，藉由利用太小的搜尋範圍估算當前區塊，會導致錯誤的運動向量。因此，如果能提供更精確的運動估算方法將是符合需求的。
發明內容
有鑑於上述現有技術之問題，本發明之目的是在提供層級式運動估算方法。運動 估算以若干層實行。藉由利用此種方法，畫面的運動向量能快速且精確估算。根據本發明，層級式運動估算方法是用於估算畫面的運動向量。此畫面在第一層 被分成若干區塊，而第一層的各區塊在第二層又被分成若干個區塊。本方法包括為第二層 之特定區塊在第一層選定參考區塊；以及藉由參考第一層之參考區塊決定第二層之特定區 塊的搜尋範圍。在這些步驟之前，第一層的參考區塊之運動向量已經以第一解析度加以估 笪弁。如果第一層為本方法中的最低層，亦即，沒有具有已知運動向量的先前層可以參 考，則第一層的各區塊之運動向量是以第一解析度利用全搜尋範圍估算。在決定第二層之特定區塊的搜尋範圍之後，利用所決定的搜尋範圍以第二解析度 估算該特定區塊的運動向量。第二解析度是高於第一解析度。於本發明之實施例中，第一 解析度為第二解析度的四分之一。
圖IA顯示一畫面分成九個區塊，而圖IB顯示該展示畫面之各區塊的運動向量。圖2概略顯示根據本發明之層級式運動估算方法之各層的搜尋範圍。圖3顯示根據本發明一畫面在層k與層k-Ι分成多個區塊。圖4顯示畫面上一特定區塊的全搜尋範圍與動態搜尋範圍。圖5顯示根據本發明之層級式運動估算方法的流程圖。圖6A與6B顯示根據本發明之利用動態搜尋範圍的運動向量估算方法的流程圖。
具體實施例方式本發明提供一種層級式運動估算方法。圖2概略顯示根據發明之層級式運動估算 方法各層的搜尋範圍。根據本方法，運動估算是以若干層執行。在最低層，整個畫面粗分為大區塊。最低 層的每個區塊其運動向量是以低解析度而利用全搜尋範圍計算。因此，由於解析度很低，最 低層的實際搜尋範圍有限。以圖2所示以三層執行運動估算的情況來說，各層的各區塊之最大可容許搜尋範 圍將利用參數P與q加以說明。如所示，如果最高層一層0的最大搜尋範圍在X軸方向為 士 P，在Y軸方向為士 q，則各區塊的最大複雜度為Op+l)XQq+l)。於層1，由於層1的分 辨率是層0的1/4，故在X軸方向的最大搜尋範圍為士p/2，在Y軸方向為士q/2。則各區塊 的最大複雜度為(p+l)X(q+l)。於層2，由於層的解析度是層0的1/16，故在X軸方向的最 大搜尋範圍為士P/4，在Y軸方向為士q/4。則各區塊的最大複雜度為(ρ/2+1) X (q/2+l)。 對於每個區塊而言，如果藉由參考先前層之運動向量所決定的動態搜尋範圍超過其最大搜 尋範圍，則當前區塊的最終搜尋範圍被選定為該最大搜尋範圍而非如正常狀況下的動態搜 尋範圍。運動估算所消耗的時間正比於各區塊之搜尋範圍的平方。於本發明中，雖然運動估算以例如三層實行，與現有技術使用全搜尋相比，各層的計算量很小，因此能迅速完成運動 估算。此外，對於較高層而言，各區塊的運動向量是參考較低層的估算運動向量加以估算， 故可估算精確的最終運動向量。稍後將詳加說明。舉例而言，對於1366X768的畫面而言，現有技術使用全搜尋需要的搜尋範圍以X 方向與Y方向表示為(士32，士 18)。如果藉由圖2之三層執行運動估算，最高層執行運 動估算的最大搜尋範圍為(士32，士 18)，中間層執行運動估算的最大搜尋範圍為(士 16， 士 9)，最低層執行運動估算的最大搜尋範圍為(士 8，士 4)，此乃由於中間層的解析度為最 低層的四倍，而最高層的解析度為中間層的四倍。首先在最低層(亦即第一層一層2)以全 搜尋(亦即整個畫面的所有區塊)在最大搜尋範圍(士8，士4)執行運動估算，該最低層的 解析度為341 X 192，為原始解析度1366X768的1/16。如所示，實際搜尋範圍在一個維度 僅為原始全搜尋範圍的1/4。由於解析度很低，計算不會那麼複雜，即使對整個畫面進行計 算仍可快速完成。第二層(亦即層1)的運動估算是在最大搜尋範圍(士 16，士9)以較高的解析度 683X384執行。在第二層一層1，第一層的各區塊被進一步分成四個區塊。第二層一層1每 個區塊的動態搜尋範圍是基於最低層(亦即層2)所估算的運動向量而決定。應注意的是， 該動態搜尋範圍不應超過如前所述最開始決定的最大搜尋範圍。在最高層(亦即第三層一 層0)，各區塊的動態搜尋範圍是基於層1所估算的運動向量決定，且最大搜尋範圍是依據 正常解析度設定為(士 32，士 18)。圖3顯示一畫面10根據本發明在層k與層k-Ι被分成若干個區塊。於此圖中，層 k顯示於左側，而層k-Ι顯示於右側。於層k，畫面10分成九個區塊A至I。於本實施例中， 假設層k為最低層，且因此各區塊的運動向量是以低解析度利用全搜尋範圍估算。舉例而 言，第二行第二列之區塊E的運動向量為(3，1)，亦即MVk(2，2) = (3，1)。層k各區塊 的最大搜尋範圍為(士8，士4)。於層k-Ι，畫面10之各區塊是進一步分成四個區塊。亦即，整個畫面10在層k-1 分成36個區塊。舉例而言，區塊E分成四個區塊a至d。對於當前區塊a(亦即第三行第三 列之區塊)而言，其運動向量MVk-I (3，3)是藉由搜尋估算，其動態搜尋範圍是藉由參考先 前層一層k的相關區塊而決定。於本發明中，用於估算層k-Ι之區塊a之運動向量的搜尋 範圍SR可藉由參考層k最近的四個區塊的運動向量而決定，這些區塊包括在層k之對應區 塊(亦即坐標0，2)之區塊E，相鄰區塊(亦即坐標(2，1)與(1，2)的區塊D與B)以 及對角區塊(亦即坐標(1，1)的區塊A)。其可表示為
SRk-I (x, y)—MVk(xl, yl), MVk (x2, y2), MVk (x3, y3), MVk (x4, y4) (6)
其中當前層之特定區塊的坐標為(χ，y)；先前層的四個參考區塊分別具有坐 標(xl，yl)、(x2，y2)、(x3，y3)及(x4, y4)，xl至x4以及yl至y4是根據下列表示式 決定
Δχ = -2*(x MOD 2) + 1 及 Ay = -2*(y MOD 2) + 1(7)
xl = [x/2],yl = [y/2](8)，
其中[]表示上整數函數(ceiling function)，而MOD表示取模運算 (modulo operation)。x2 = [χ/2] +Δ X, y2 = [y/2](9)x3 = [x/2],y3 = [y/2] + Ay(10)
x4 = [χ/2] +Δχ, y4 = [y/2] +Ay(11)
如上列表示式可推導者，對於層k-1之區塊a而言，x = 3且y = 3，區塊a之 搜尋範圍SRk-l(3，3)可藉由參考區塊A、B、D、E的運動向量決定，其可表示為 SRk-I (3，3) — MVk (2, 2)，MVk (1, 2)，MVk (2, 1)，MVk (1, 1)(12)
根據本發明，區塊a的搜尋範圍SRa (亦即SI k-l(3，3))是藉由最大X方向 運動向量分量MVmX以及最大Y方向運動方向分量MVmY決定。MVmX= max{abs(3), abs(l), abs(l), abs(l)} = 3(13) MVmY= max{abs(l), abs (0), abs (0), abs(-l)} = 1 (14)
於本實施例中，層k的解析度為層k-1的1/4。因此，為計算動態範圍SR，各最大運動 向量分量應乘以2。此外，該搜尋範圍可在各維度稍加擴展一個因子δ，其可為0或是正整 數。於本實施例中，δ是選定為1，因此區塊a之X方向的搜尋範圍SRaX以及Y方向的搜 尋範圍SRaY為
SRaX= 3X2+ δ =3X2+1=7(15)
SRaY= 1X2+ δ =1X2+1=3(16)
亦即，對於區塊a來說，X方向的動態範圍為士 7，Y方向為士 3。因此，有105個區 塊要比對((14+1) X (6+1) = 105)。區塊a的全搜尋範圍SRaf為(士 16，士9)，因此有 627個區塊要比對。藉由利用本發明之方法，於本例中可節省83. 2%的時間。圖4顯示畫面上一特定區塊之全搜尋範圍與動態搜尋範圍。對於區塊a左上角50 來說，全搜尋範圍M為(士 16，士9)，明顯大於動態搜尋範圍52，其為(士7，士3)。由於層k之區塊A至I的正確運動向量可以取得，可依據層k的運動向量有效決 定層k-Ι之各區塊的正確趨勢。如所述，層k-Ι之區塊a的動態搜尋範圍SRa是藉由層k 之區塊A、B、D及E的運動向量而決定。同理，層k-Ι之區塊b的動態搜尋範圍SRb是藉由 層k之區塊B、C、E及F的運動向量而決定。層k-Ι之區塊c的動態搜尋範圍SRc是藉由層 k之區塊D、E、G及H的運動向量而決定。層k-Ι之區塊d的動態搜尋範圍SRd是藉由層k 之區塊E、F、H及I的運動向量而決定。為了取得更準確的運動向量，動態搜尋範圍可在各 個維度以一個因子δ稍加擴展，該因子δ為0或正整數。當δ為0時，表示搜尋範圍並 未向外擴展。上述方法可參照圖5總結，圖5為顯示根據本發明之層級式運動估算方法的流程 圖。該方法於步驟SlO開始。於步驟S20，判定當前層(亦即欲估算的區塊所在的層)是否 為第一層。如是，各區塊的運動向量是以全搜尋範圍估算(步驟S30)。如上所述，由於第一 層的解析度很低，即使使用全搜尋範圍來估算運動向量也不會花費太多時間。如否，表示當 前層為更高層，則以動態搜尋範圍實行運動估算(步驟S40)。於步驟S50，判定當前層是否 為最末層或是當前層之解析度是否為最高解析度。如是，則於步驟S60結束運動估算流程， 否則，流程即返回步驟S40。以動態搜尋範圍實行之運動估算將參照圖6Α與圖6Β進一步說明，圖6Α與6Β顯 示根據本發明的利用動態搜尋範圍決定之運動向量估算方法(即圖5所示之步驟S40)。本 過程開始於步驟S102。於步驟S104，當前層(其非是最低層)的一個區塊是選定為當前區塊 (例如層k-Ι的區塊a)。於當前層中，各區塊是將先前層的區塊進一步分割而界定。舉例而言，如果當前層為層k-Ι，則層k-Ι的區塊是藉由將先前層一層k的各區塊分割成四個區塊 而得。此時，尚未計算當前層一層k-Ι中所選定的當前區塊。亦尚未決定用於估算該當前區 塊之運動向量的動態搜尋範圍。於步驟S106，從先前層一層k中決定相對於該當前區塊的 參考區塊(例如區塊A、B、D及E)。在參照圖3敘述的實施例中，選定區塊a之先前層(亦即 層k)的參考區塊為四個區塊A、B、D及E，其是由上列表示式(7)至(11)決定。如所述， 參考區塊的運動向量為已知，因為先前層的運動估算已經利用全搜尋範圍或動態搜尋範圍 完成。如果先前層為最低層，則是利用全搜尋範圍以低解析度完成運動估算。於步驟S108，由步驟S106決定的這些參考區塊中在X方向與Y方向最大的運動向 量分量是決定為
MVmX = max{abs(4_block_MVX)} (17) MVmY = max{abs(4_block_MVY)} (18) 於步驟S110，所選定區塊的動態搜尋範圍是藉由利用參考區塊的最大運動向量分量而 決定。該動態搜尋範圍SR是決定為X方向與Y方向的量，可表示為SRX及SRY如下 SRX = MVmX X 2 + δ(19)
SRY = MVmY X 2 + δ(20)
如所述，當計算動態搜尋範圍時，由於先前層的解析度是當前層的1/4，故先前層的參 考區塊之最大運動向量分量應分別乘以2。於步驟S112與步驟S116，檢查X方向與Y方向的動態搜尋範圍量SRX及SRY是否 分別超過臨界值max_SRX及max_SRY。這些臨界值max_SRX及max_SRY是如前所述在一開 始從最大搜尋範圍得出。如果動態搜尋範圍SRX超過臨界值max_SRX，則將動態搜尋範圍 SRX設定為該臨界值max_SRX(步驟S114)。如果動態搜尋範圍SRY超過臨界值max_SRY，則 將動態搜尋範圍SRY設定為該臨界值maX_SRY (步驟S118)。亦即，當所決定的動態搜尋範 圍超過最大搜尋範圍時，強迫動態搜尋範圍(士SRX，士SRY)等於最大搜尋範圍(士max_ SRX, 士max_SRY)，該最大搜尋範圍是依據當前層的解析度決定。如果動態搜尋範圍值並未 超過這些臨界值，則於步驟S120在該動態搜尋範圍中執行所選定之當前區塊的區塊匹配。 亦即，利用成本函數(cost function)在所決定的動態搜尋範圍內估算所選定之當前區 塊的運動向量，成本函數可為MSE (均方誤差)、SAD (絕對誤差和)函數等等。於步驟S122， 儲存當前區塊之最佳估算運動向量，且程序返回至步驟S104以估算下一區塊的運動向量。以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域的普通技術人 員，在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改進和潤飾也應視為 本發明的保護範圍。
權利要求
1.一種層級式運動估算方法，用於以若干層估算一畫面的運動向量，該畫面在先前層 分成若干個區塊，且先前層之各區塊於當前層又被分成若干個區塊，其特徵在於該方法包 含針對當前層的一個特定區塊在先前層選定參考區塊；以及 藉由參考先前層之這些參考區塊的運動向量而決定當前層之該特定區塊的搜尋範圍，其中這些參考區塊的運動向量是已以一先前解析度估算出。
2.根據權利要求1所述的方法，其特徵在於當前層之該特定區塊的該搜尋範圍是藉 由參考先前層之這些參考區塊的運動向量在X方向與Y方向的最大運動向量分量而決定。
3.根據權利要求1所述的方法，其特徵在於當前層之該特定區塊的該搜尋範圍是在X 方向與Y方向進一步擴展一因子S，該因子δ為等於或大於零的整數。
4.根據權利要求1所述的方法，其特徵在於在先前層之各區塊是在當前層分成四個 區塊。
5.根據權利要求1所述的方法，其特徵在於在先前層之這些參考區塊包括相對於在 當前層之該特定區塊最接近的四個區塊。
6.根據權利要求5所述的方法，其特徵在於在先前層之這些參考區塊分別具有坐標 (xl，yl)、(x2，y2)、(x3，y3)及(x4, y4),xl至x4及yl至y4是根據以下表示式決 定Δχ = -2*(x MOD 2) + 1 且 Ay = -2*(y MOD 2)+1; xl = [x/2], yl = [y/2]； x2 = [χ/2] +Δχ, y2 = [y/2]； x3 = [x/2], y3 = [y/2] + Ay； x4 = [x/2] +Δχ, y4 = [y/2] +Ay, 其中當前層之該特定區塊的坐標為(X，y)，且□表示上整數函數，而MOD表示取模運算。
7.根據權利要求5所述的方法，其特徵在於在先前層之這些參考區塊包括在先前層 對應於當前層之該特定區塊的第一區塊、相鄰於第一區塊的第二與第三區塊、以及和第一 區塊成對角並在第二與第三區塊之間的第四區塊。
8.根據權利要求1所述的方法，其特徵在於給該先前層為該方法中之最低層，則該先 前層之各區塊的運動向量是以該先前解析度利用全搜尋範圍估算，該先前解析度是設定為 最低解析度，該全搜尋範圍是基於該最低解析度決定。
9.根據權利要求1所述的方法，其特徵在於尚包含利用所決定的搜尋範圍，以一當前 解析度估算該當前層之該特定區塊的運動向量，該當前解析度是高於該先前解析度。
10.根據權利要求9所述的方法，其特徵在於該先前解析度為當前解析度的四分之一。
11.根據權利要求1所述的方法，其特徵在於當所決定的搜尋範圍超過一最大搜尋範 圍時，強制該當前層之所決定的搜尋範圍等於該最大搜尋範圍，該最大搜尋範圍是基於該 當前層之當前解析度所決定。
全文摘要
本發明提供了一種以多層實施之層級式運動估算方法。本層級式運動估算方法是用於估算畫面的運動向量。畫面在第一層分成多個區塊，而第一層的各區塊在第二層又分成若干個區塊。本方法包括為第二層之特定區塊選定在第一層的參考區塊，並藉由參考第一層之參考區塊的運動向量來決定第二層之特定區塊的搜尋範圍，第一層之參考區塊的運動向量為已知。藉由利用此種方法，可快速且精確估算畫面的運動向量。
文檔編號H04N5/14GK102088542SQ20101057159
公開日2011年6月8日 申請日期2010年12月3日 優先權日2009年12月7日
發明者張志宇, 楊紹聖, 黃文彥 申請人:矽統科技股份有限公司