[發(fā)明專利]一種基于并行流水線的窮盡運動估計搜索方法與裝置

無效

• 申請?zhí)枺?/td>: 200710124972.1
• 申請日: 2007-12-12
• 公開（公告）號: CN101227607A
• 公開（公告）日: 2008-07-23
• 發(fā)明（設(shè)計）人: 李剛;曾為
• 申請（專利權(quán)）人: 深圳市同洲電子股份有限公司
• 主分類號: H04N7/26
• 分類號: H04N7/26
• 代理公司: 深圳市康弘知識產(chǎn)權(quán)代理有限公司
• 代理人: 胡朝陽

技術(shù)領(lǐng)域

本發(fā)明涉及視頻數(shù)據(jù)壓縮技術(shù)，尤其是涉及基于流水線處理方式、采用并行存儲和比較的方式進(jìn)行運動估計的窮盡搜索方法與裝置。

背景技術(shù)

運動估計是一種幀間編碼的方法，其原理是利用幀間的空間相關(guān)性，減小空間冗余度。因此，運動估計是視頻壓縮算法的核心算法之一，是搜索當(dāng)前宏塊在參考幀中對應(yīng)的最相似塊的過程。

在視頻編碼中，運動估計相當(dāng)耗時，對編碼的實時性影響很大。因此特別強(qiáng)調(diào)快速算法。運動估計方法主要有像素遞歸法和塊匹配法兩大類，前者復(fù)雜度很高，實際中應(yīng)用較少，后者則在H.263和MPEG中廣泛采用。

目前有三種常用的匹配準(zhǔn)則：(1)絕對誤差和準(zhǔn)則(SAD，Sum?of?Absolute?Difference)；(2)均方誤差準(zhǔn)則(MSE，Mean?Square?Error)；(3)歸一化互相關(guān)函數(shù)準(zhǔn)則(NCCF，NormalizedCross?Correlation?Function)。在上述三種準(zhǔn)則中，SAD準(zhǔn)則具有不需乘法運算、實現(xiàn)簡單方便的優(yōu)點而使用最多。目前比較常用的方法有三步法、梯度法和鉆石法等。

就運動估計的搜索方法而言，最簡單、最可靠的方法是窮盡搜索法。窮盡搜索塊匹配算法是一種精度最高的運動估計方法，雖然在傳統(tǒng)的窮盡搜索塊匹配算法中它能夠得到最佳的運動估計結(jié)果，但由于其計算量驚人而且需要頻繁的訪問存放參考幀的存儲器，需要很長的時間，因而在視頻廣播領(lǐng)域應(yīng)用并不廣泛。

申請?zhí)枮?00510069219.8，申請日為2005年5月12日的中國專利申請，公開了一種優(yōu)化使用搜索模板的視頻數(shù)據(jù)壓縮方法，它包括以下步驟：根據(jù)搜索模板和搜索步長，確定搜索模板中其余各搜索模塊相對于當(dāng)前搜索模塊的偏移地址；在搜索中，根據(jù)當(dāng)前塊的起始地址和所述各偏移地址，計算各搜索塊的起始地址；以及在進(jìn)行匹配運算之前，將當(dāng)前搜索塊的視頻數(shù)據(jù)和其余各搜索塊的視頻數(shù)據(jù)依次預(yù)讀入緩存。該技術(shù)方案存在如下缺陷：

1、該方法需要經(jīng)過(M+N)次搜索比較，所需時間較長，影響編碼速度；

2、該方法搜索所找到的最優(yōu)點不一定是搜索框內(nèi)最優(yōu)點，因此精度有待進(jìn)一步提高。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是，提出了一種基于并行流水線的窮盡運動估計搜索方法，其可提高窮盡搜索的處理速度，使窮盡搜索在視頻廣播中實時處理成為可行。

為解決本發(fā)明的技術(shù)問題，本發(fā)明公開一種基于并行流水線的窮盡運動估計搜索方法，包括以下步驟：

A、將視頻數(shù)據(jù)以幀為單位輸入，且每幀數(shù)據(jù)劃分為2ⁿ個待比較塊；

B、以并行流水線方式將當(dāng)前幀的2ⁿ個待比較塊中每個待比較塊的像素數(shù)據(jù)與參考幀中的對應(yīng)比較塊的像素數(shù)據(jù)進(jìn)行匹配運算，并在一個時鐘周期內(nèi)并行輸出2ⁿ個殘差數(shù)據(jù)；

C、以并行流水線方式對2ⁿ個殘差數(shù)據(jù)進(jìn)行殘差比較處理，在一個時鐘周期內(nèi)輸出2ⁿ個殘差數(shù)據(jù)中的4個最小殘差數(shù)據(jù)、以及該4個最小殘差數(shù)據(jù)在當(dāng)前搜索區(qū)域內(nèi)對應(yīng)像素塊的地址和運動向量；

D、并依次進(jìn)行1/2像素運動估計處理和1/4像素運動估計處理，最后輸出當(dāng)前搜索區(qū)域內(nèi)1/4像素精度對應(yīng)最小的殘差數(shù)據(jù)和對應(yīng)像素塊的運動向量。

較優(yōu)的，所述步驟B中，對當(dāng)前幀的一個待比較塊中每個像素數(shù)據(jù)進(jìn)行匹配運算的步驟包括：

B1、將當(dāng)前幀的一個待比較塊中每個像素數(shù)據(jù)與參考幀中對應(yīng)的比較塊的像素數(shù)據(jù)進(jìn)行相減后取絕對值的比較運算處理；

B2、將相鄰兩個像素數(shù)據(jù)的比較運算結(jié)果進(jìn)行第1級的求和處理；

B3、將步驟B2的相鄰的兩個求和處理結(jié)果進(jìn)行第2級求和處理，以此類推，分別進(jìn)行第3至x級的求和處理，在一個時鐘周期內(nèi)獲得該待比較塊的殘差數(shù)據(jù)，其中x表示一個待比較塊中具有2^x個像素。

較優(yōu)的，所述步驟C包括：

C1、將2ⁿ個殘差數(shù)據(jù)兩兩為一組進(jìn)行第1級比較處理，輸出2^n-1個較小值；

C2、將輸出的2^n-1個較小值兩兩為一組進(jìn)行第2級比較處理，并以此類推，分別經(jīng)過第3至第n-2級處理；

C3、獲得2ⁿ個殘差數(shù)據(jù)中的4個最小殘差數(shù)據(jù)、以及該4個最小殘差數(shù)據(jù)對應(yīng)像素塊的地址和運動向量。

較優(yōu)的，所述1/2像素運動估計處理的步驟包括：

D11、將步驟C中輸出的4個最小殘差數(shù)據(jù)對應(yīng)像素塊經(jīng)1/2像素插值處理；