全局運動估計的製作方法

2023-08-10 01:00:06

專利名稱：全局運動估計的製作方法
技術領域：
本發明涉及運動估計，尤其但不排他地涉及在採用幀間差分編碼的視頻編碼器的環境下的運動估計。

背景技術：
圖1示出了公知形式的視頻編碼器。輸入緩衝器1接收視頻信號(通常為數字形式)。減法器2形成輸入信號和來自幀儲存器3的預測信號之間的差值，該差值隨後在塊4中被進一步編碼。此處所進行的編碼對於本發明來說並不重要，但是可以包括閾值(以抑制零差值或小差值的傳播)量化或變換編碼作為示例。到幀儲存器的輸入是在加法器5中形成的、預測信號和在本地解碼器6中進行了解碼的已編碼差值信號的總和(從而編碼和解碼處理中的信息丟失被包括在預測器環中)。
差分編碼實質上是幀間差分編碼，並且該預測可以簡單地包括由幀存儲器3提供的一幀延遲；然而，如圖所示，還可以包括運動估計器7。這對正被編碼的圖像的幀和提供給預測器的先前幀進行了比較。對於(被認為是該圖像所分成的)當前幀的各個塊，其識別先前幀的與該塊最相似的區域(region)。所識別的區域與所關注的塊之間的位置方面的向量差被稱為運動向量(因為其通常表示電視圖像所描繪的場景內的對象的運動)，並且被應用於將先前幀的所識別的區域移動到當前幀中的相關塊的位置的運動補償單元8，從而產生更好的預測。這使得由減法器2形成的差值平均起來更小，並且允許編碼器4使用比其他情況下更低的比特率對圖像進行編碼。運動向量與來自4的已編碼差值信號一起被發送到解碼器。
通常，運動估計器必須將各個塊與先前幀的對應塊和在位置上相對於該塊位置偏移的區域進行比較；在實際系統中，儘管該搜索被限制在所限定的搜索區域中而不是對整個幀進行，但是其仍然涉及相當大的處理量並且經常需要對這兩個幀的已存儲版本進行許多訪問。注意，這要求輸入緩衝器1引入用於運動估計器7對當前塊及其搜索區域進行訪問的足夠延遲，以在該塊到達減法器2之前完成運動估計器7對該塊的運動估計。
通常，運動估計器將正在進行編碼的電視圖像的「當前」幀視為被分成8×8塊-即，垂直方向八行水平方向八個圖像元素(像素)。儘管這些原理同樣可以應用於隔行掃描系統，但是為了簡化說明，假設是非隔行掃描圖像。運動估計器被設計成針對各個塊生成表示8×8區域的位置的運動向量，該8×8區域位於圖像的所述(或一個)先前幀的所限定的搜索區域內，該搜索區域與所關注的塊最相似。圖2示出了具有8×8塊N(陰影部分)和由矩形SN表示的典型的相關聯的23×23搜索區域的範圍(field)。如果用坐標x，y來標識水平方向的像素和垂直方向的行(原點在左上角)，則左上角像素的坐標為xN，yN的塊的搜索區域是在水平方向上從(xN-8)到(xN+14)並且在垂直方向上從(yN-8)到(yN+14)延伸的區域。
為了獲得運動向量，需要進行搜索，在該搜索中，將塊與先前幀的位於搜索區域內的256個可能的8×8區域(即，其左上像素的坐標為xN+u，yN+v的區域，其中u和v在-8到+7的範圍內)中的每一個進行比較。運動向量是該比較表明具有最大相似性的u、v的值。可以任意常規地使用針對相似性的測試-例如，「當前」塊中的各個像素與先前幀的相關區域之間的差的絕對值的總和。
由於該操作的計算強度高，所以提出了一種公知的方法(例如，參見J.Y.Tham，S.Ranganath，M.Ranganath，and A.A.Kassim，″A novelunrestricted center-biased diamond search algorithm for block motionestimation″，IEEE Trans.Circuits Syst.Video Technol.，vol.8，no.4，pp.369-377，Aug 1998)用於對運動向量進行初始估計，並使用該初始估計來限定偏移搜索區域的位置。於是該搜索區域可以更小並且可以更快地執行該搜索。一種這樣的方法涉及迭代方法，在該迭代方法中，該搜索區域僅包括五個位置-即，相對於所估計的偏移位置的位置(0，0)、(-1，0)、(1，0)、(0，-1)以及(0，1)。經更新的估計是由這五個位置中給出最小E值的一個位置表示的位置。然後根據需要重複該操作，直到沒有獲得進一步的改善(即，相對位置(0，0)給出了最小E)為止。
Chen and Li，″A Novel Flatted Hexagon Search Pattern for Fast BlockMotion Estimation″，2004 International Conference on Image Processing(ICIP)，IEEE，vol.3，pp.1477-1480注意到水平偏移運動的概率比垂直偏移運動的概率更大並且通過以平面六邊形(flattened hexagon)的形狀選擇搜索區域來尋求搜索速度的提高。
對於初始估計的可能選項包括 -已經生成了針對所述先前(或前一)幀的對應位置處的塊的運動向量； -已經生成了針對所關注的塊的上方緊接著的塊的運動向量； -已經生成了針對所關注的塊的左邊緊接著的塊的運動向量。
一種有用的方法(Tourapis，A.et al.Predictive Motion Vector FieldAdaptive Search Technique(PMVFAST).Dept.of Electrical Engineering，The Hong Kong University of Science and Technology，該文獻可以在線獲得http://www.softlab.ntua.gr/～tourapis/papers/4310-92.pdf)涉及使用全部三個運動向量和(0，0)，並選擇給出最低E的運動向量，並使用所選擇的運動向量作為迭代的起始點。
一些建議引入了全局運動向量(即，標識當應用於電視圖像的整個幀時產生良好的預測的單個偏移的向量)的思想。例如，參見HirohisaJozawa，Kazuto kamikura，Atsushi Sagata，Hiroshi Kotera，and HiroshiWatanabe，″Two-Stage Motion Compensation Using Adaptive Global MC andLocal Affine MC″.IEEE Trans.on Circuits and Systems for VideoTechnology，Vol.7，No.1 February 1997，pp.75-85。同樣，全局向量可以為搜索更好的向量提供起始點。Winger(US2004/0013199A)獲得了兩個全局運動估計，他使用這兩個全局運動估計來為兩個同時進行的搜索提供初始偏移。
Sun和Lei在″Efficient Motion estimation using Global MotionPredictor″，Proceedings of the Fifth lasted International Conference of Signaland Image Proceeding，2003，pp.177-182中提出了一種全局運動估計的方法，其中，通過僅考慮幀邊界附近的圖像的大約為幀的5％的子區域來減小計算量。


發明內容
根據本發明，提供了一種對第一視頻幀估計全局運動向量的方法，該全局運動向量標識了一偏移，當該偏移被應用於電視圖像的另一幀時增加了它們之間的相似性，該方法包括 從所述第一幀中選擇多個圖像元素； 將所選擇的圖像元素與另一幀的對應位置處的圖像元素進行比較，以產生相對於零偏移的相似性的量度； 對於多個試驗偏移中的每一個，將所選擇的圖像元素與另一幀的具有相同相互位置但偏移了相應偏移的圖像元素進行比較，以產生相對於該偏移的相似性的量度； 識別產生了表示高相似性的量度的偏移(或零偏移)； 該方法的特徵在於所選擇的圖像元素的數量在所述幀中的圖像元素的總數的0.1％到5％的範圍內。
本發明的其他方面在權利要求中限定。



現將參照附圖以示例的方式來描述本發明的一個實施方式，附圖中 圖1是公知形式的視頻編碼器的框圖； 圖2是表示圖1的運動估計器使用的坐標系和搜索區域的電視圖像的圖； 圖3是本發明的一個實施方式中使用的運動估計器的框圖；以及 圖4和5是表示圖3的估計器的操作的流程圖。

具體實施例方式 現在對具有與如圖1中所示相同的結構的視頻編碼器進行說明。除了運動估計器7以外，該編碼器的操作都是常規的，現在將對該運動估計器7進行說明。
如圖3所示，運動估計器的功能由處理器10來執行、由存儲在存儲器12中的程序11控制。該處理器訪問存儲在幀存儲器3中的「先前幀」像素和存儲在緩衝器1中的正被編碼的當前幀的像素。其任務是針對當前幀的每個8×8塊生成運動向量。當然，該算法可以容易地適用於其他塊大小。實際上，在H.264中，可以針對各種塊大小(16×16、16×8、8×16、8×8、8×4、4×8、4×4)來對運動向量進行編碼。一個令人感興趣的方法是針對一個以上的塊大小執行運動估計，並選擇給出最佳結果的向量。
注意，儘管對於16×16塊的SOAD絕不會比在將其分成四個8×8塊時獲得的四個SOAD的總和更好，但是一旦針對需要發送的不同開銷的數據進行適當的調整(due allowance)時，它可以表現出優勢。
現在將在圖4的流程圖的幫助下解釋針對一個8×8塊的處理器操作。
在步驟100中，該系統獲得針對與先前幀或一些其他參考幀相關的當前幀的全局運動向量；或者，如果需要，可以獲得一個以上的全局運動向量。
在步驟101中，該系統針對當前塊計算進一步的候選，如上所述； 在步驟102中，對這些候選中的每一個以及空向量(0，0)進行評估，並且選擇給出最佳SOAD的向量。
在步驟103處，使用前面描繪的公知過程對所選擇的向量進行迭代。然後，該處理返回到步驟101以處理另一個塊。
圖5示出了詳細表示步驟100的獲得全局運動向量的流程圖。要描述的方法被發現在快速運動的情況下給出了經改善的結果。快速運動的問題在於它可以導致正確的運動向量較大-實際上大到常規方法提供的搜索範圍(extent)不足以找到它。簡單地增大搜索區域的大小不是令人滿意的解決方案，因為計算量會很快變得難以管理地大並且計算緩慢。本方法旨在提供較大的搜索範圍(至少在水平方向上)並且通過將比較處理限制在所關注的幀的少數圖像元素來緩解將出現的計算的增加。所選擇的元素的數量可以低至該幀中的圖像元素的總數的0.1％到5％。
我們更喜歡從相對小數量的行中獲取圖像元素，通常在每個所選擇的行中選擇多數的元素。在本示例中，所選擇的圖像元素是從圖像的三行中的每一行中獲取的中央部分。這些行的準確位置並不重要我們選擇這些行，以使這些行將該幀分成四個等份；因此，如果該幀包括288行(編號為1到288)，則我們選擇第72、144和216行。
從這些行中的每一行選擇的圖像元素的數量大約是該行中的元素的總數的50％；我們發現使用固定數量來覆蓋幀大小的範圍是方便的。典型數字(還給出了搜索範圍)為 176≤寬度＜320 行長度＝128；搜索範圍＝24 320≤寬度＜640 行長度＝224；搜索範圍＝48 640≤寬度 行長度＝384；搜索範圍＝128。
因此，對於寬度為352的被編號為1到352的圖像元素，所選擇的圖像元素為65到288。
在較小數量的行上而不是在整個圖像上分散地選擇圖像元素的原因在於這使得能夠有效地使用處理器的高速緩存，因為被用作搜索窗的圖像元素的相同的有限集合被置換(displace)。此外，在使用沿著該行的連續像素的情況下，可以利用允許同時計算八個SOAD的SSE2(和類似的)單指令多數據處理器指令。
在本示例中，運動向量搜索是水平的，其垂直分量為零。我們考慮向量值為從-S到+S，其中S為剛提到的搜索範圍。
參照該流程圖，在步驟200處，將運動向量的水平分量s設置為-S。可變BestSOAD被設置為任意大的數(足夠大，以始終大於SOAD的任意實際值)；在我們的實現中，使用了常數LONGMAX(＝2147483647)。在步驟202處，計算當前幀的所選擇的圖像元素與參考幀內的具有相同位置但偏移了s的圖像像素之間的相似性的量度。在本示例中，相似性的量度為絕對差值的總和(SOAD)。對於所選擇的圖像元素為第72、144和216行的65到288元素的情況，如果當前幀的行L上的像素P的亮度是Y(P，L)並且參考幀中的行L上的像素P的亮度是R(P，L)，則SOAD為 存儲(203)該值以在以後與對應的s值一起使用；在步驟204處，將該值與BestSOAD進行比較。如果新的值較低，則在步驟205處，將BestSOAD設置為該新的值，並將Bestvector(0)設置為當前的s值。
然後，在步驟206處，使s遞增。如果s沒有超過S，則該處理返回到步驟202以計算另一SOAD。
一旦計算了所有的SOAD，則Bestvector包含所希望的結果(全局運動向量的水平分量)。然而，在本示例中，我們還選擇將多達N個的與SOAD(被認為是s的函數)的局部最小值相對應的s值標識為附加候選。然而，我們排除對僅在一個像素已經被選擇的少數像素中的任意s的選擇或者具有比找到的最低值大125％的SOAD值的任意s的選擇。因此，該處理接下來進入進一步的循環。在208處，運動向量的水平分量再次被初始化為-S。
在209處，對該s值進行檢查，以尋找局部最小值，並且如果找到(受該125％的限制)，則在210處將標記Localminimum(s)設置為True(真)。對於該操作的條件為 {[s＝-S並且SOAD(s)＜SOAD(s+1)]或者 [s＝S並且SOAD(s)＜SOAD(s-1)]或者 [-S＜s＜S並且SOAD(s)＜SOAD(s+1)並且SOAD(s)＜SOAD(s-1)]} 並且SOAD(s)＜1.25*BestSOAD。
然後，在步驟211處，使s遞增。如果(212)s沒有超過S，則該處理返回到步驟209以檢查另一個值並適當設置該標記。
在標記了局部最小值後，則在步驟213處，通過對這些位置將Localminimum設置為false(假)來去除Bestvector處或Bestvector的±5圖像元素內的任意局部最小值。
在步驟214處，將用於找到多至N-1個進一步向量的計數器n設置為1，並且NextbestSOAD被初始化為高值(215)。然後，進入循環，該循環將各個局部最小值的SOAD與當前(running)最佳值(NextbestSOAD)進行比較。
更具體地 在216處，運動向量水平分量s被再次初始化為-S； 在217處，檢查是否存在在該s值處被標記的具有比當前值NextbestSOAD更好(即，更小)的SOAD的局部最小值；如果存在，則在步驟218處，將Bestvector(n)設置為s，並且將NextbestSOAD設置為該剛找到的新的較低SOAD。
在219處，使s遞增，如果(220)s沒有超過S，則搜索從217繼續。
在211處，通過對於這些位置將Localminimum設置為false(假)來去除位於Bestvector(n)處或Bestvector(n)的±5圖像元素內的任意局部最小值。然後，使n遞增(222)，並且如果n沒有達到N，則該處理返回到步驟215，以搜索仍剩餘的那些位置的最佳局部最小值。
在圖5中示出的處理的結論處，N個最佳全局運動向量被存儲在Bestvector(0)到Bestvector(N-1)中，準備在圖4的步驟101中使用。該處理還包括在滿足塊217中給出的標準的元素實際上少於N個的情況下要提前終止該處理的規定，但是為了清楚並沒有示出這些規定。
權利要求
1.一種對第一視頻幀估計全局運動向量的方法，該全局運動向量標識了一偏移，當該偏移被應用於電視圖像的另一幀時增加了它們之間的相似性，該方法包括
從所述第一幀中選擇多個圖像元素；
將所選擇的圖像元素與另一幀的對應位置處的圖像元素進行比較，以產生相對於零偏移的相似性的量度；
對於多個試驗偏移中的每一個，將所選擇的圖像元素與另一幀的具有相同相互位置但偏移了相應偏移的圖像元素進行比較，以產生相對於該偏移的相似性的量度；
識別產生了表示高相似性的量度的偏移或零偏移；
該方法的特徵在於所選擇的圖像元素僅是從所述圖像的所選擇的多行中選擇的，所選擇的多行的數量小於所述幀中的行的總數的5％。
2.根據權利要求1所述的方法，其中，所選擇的多行的數量小於五。
3.根據權利要求2所述的方法，其中，所選擇的多行的數量為3。
4.根據權利要求1、2或3所述的方法，其中，所選擇的圖像元素包括從各個所選擇的行的中央部分獲取的連續圖像元素的集合。
5.根據以上權利要求中的任意一項所述的方法，其中，所述多個試驗偏移中的大多數試驗偏移的水平分量大於垂直分量。
6.根據權利要求5所述的方法，其中，所述垂直分量為零。
7.一種對第一視頻幀估計全局運動向量的方法，該全局運動向量標識了一偏移，當該偏移被應用於電視圖像的另一幀時增加了它們之間的相似性，該方法包括
從所述第一幀中選擇多個圖像元素；
將所選擇的圖像元素與另一幀的對應位置處的圖像元素進行比較，以產生相對於零偏移的相似性的量度；
對於多個試驗偏移中的每一個，將所選擇的圖像元素與另一幀的具有相同相互位置但偏移了相應偏移的圖像元素進行比較，以產生相對於該偏移的相似性的量度；
識別產生了表示高相似性的量度的偏移或零偏移；
該方法的特徵在於所述多個試驗偏移中的大多數試驗偏移的水平分量大於垂直分量。
8.根據權利要求7所述的方法，其中，所述垂直分量為零。
9.根據權利要求7或8所述的方法，其中，所選擇的圖像元素的數量在所述幀中的圖像元素的總數的0.1％到5％的範圍內。
10.根據權利要求9所述的方法，其中，所選擇的圖像元素的數量在所述幀中的圖像元素的總數的0.15％到2％的範圍內。
11.根據以上權利要求中的任意一項所述的方法，該方法包括識別產生表示最大相似性的量度的偏移，以及與由該量度表示的相似性的局部最大值相對應的至少一個其它偏移。
全文摘要
本發明提供了一種全局運動估計。第一視頻幀的全局運動向量標識了一偏移，當該偏移被應用於電視圖像的另一幀時增加了這兩幀之間的相似性。為了估計該偏移，該方法包括從所述第一幀中選擇多個圖像元素；將所選擇的圖像元素與另一幀的對應位置處的圖像元素進行比較，以產生相對於零偏移的相似性的量度；對於多個試驗偏移中的每一個，將所選擇的圖像元素與另一幀的具有相同相互位置但偏移了相應偏移的圖像元素進行比較，以產生相對於該偏移的相似性的量度；識別產生了表示高相似性的量度的偏移或零偏移。所選擇的圖像元素僅是從所述圖像的所選擇的多行中選擇的，所選擇的多行的數量小於所述幀中的行的總數的5％-可能甚至少至三行。所選擇的圖像元素包括從各個所選擇的行的中央部分獲取的連續圖像元素的集合。所考慮的偏移可以主要或者甚至完全是水平的。
文檔編號H04N7/26GK101120594SQ200680004749
公開日2008年2月6日 申請日期2006年2月3日 優先權日2005年3月14日
發明者麥可·埃爾林·尼爾森 申請人:英國電訊有限公司