TWI259727B - Method for rapidly determining macroblock mode - Google Patents

Description

1259727 玖、發明說明： 【發明所屬的技術領域】 本發明係關於移動估、、目丨& # 初1古/則的技術領域，尤指一種 快速巨集區塊模式決定方法。 【先前技術】 在目前的視訊編碼標準中，其主要利用移動估 測（motion estimati0n、ME)以移除影像序列中的冗 餘，而達到高的影像壓縮效率。在H 264/mpeg_4 10 AVC視訊編碼標準中’使用可變區塊大小的移動補償 (variable blocksize motion c〇inpensati〇n)，以達到高 的影像壓縮效率。在巨集區塊（macr〇bl〇ck 卜 MB level)有四種區塊大小的模式，分別為16*1616*8、 8木16及8*8四種區塊大小的模式。在子巨集區塊（sub 15 macroblock level' sub_MB level)有四種區塊大小的 模式，分別為8*8、4*8、8*4及4*4四種區塊大小的模式。 習知技術是將移動估測（ME)及巨集區塊模式決 定（mode decision)—起同時計算。對於每一區塊大 小，先計算移動估測（ME)，而移動估測（me)所產生的移動 20成本（motion cost)則用以決定區塊大小。因對於每一種區 塊大小，均需先計算移動估測（ME)，此會使計算量會急遽 地增加。 針對巨集區塊模式決定其計算量急遽增加的問 題，於美國第USP6,782,052號專利案公告中，依據現行區 1259727 塊的鄰近區塊的模式頻率，計算現行區塊的模式頻率預測 值。如圖1所示，區塊E為現行區塊，區塊a ' B、C及D為 鄰近區塊，先決定鄰近區塊A、B、C&D的區塊模式❿八、 mB、mC及mD，再決定區塊模smA、mB、mC&mD的頻 5率及&，計算模式頻率預測值（，該模 式頻率預測值（，其中α為小於i 且大於〇的參數，如果一模式m其頻率&小於該模式頻率預 測值（F0)，則剔除模式m。其雖在巨集區塊模式決定時 減少一些模式，但當現行區塊與其鄰近區塊的關連性不大 川時，此種區塊模式決定方法其計算量仍頗為魔大並 且其效率會大幅降低。故習知的巨集區塊模式決定的 方法仍有予以改善的需求。 【發明内容】 15 本發明的目的係在提供一種快速巨集區塊模式決定方 4 ’以避免習知技術所產生計箕詈廍女沾叫％ 碼時的效率。 生十异里龐大的問題，以增加編 依據本發明的一特色，禆裎Φ ^ + 決定士、， 行巴純出一種快速巨集區塊模式 、方法’其運用於一影像圖框編碼中，兮士 判鼢, 不口化獨碼〒，该方法包含··（A) 4所一 4n*4n區塊在（〇, 0)或一預測銘說A 3 動决士曰 預劂移動向量（PMV)處的移 勒成本疋否小於第一臨界值 m 值，⑻右步驟(A)中判定小於第 匕界值，則該巨集區塊模式為4n*4n，並 方决；（C)若步驟（A)t判定不小 、"、 區堍如肋从，/ 。 第臨界值，對該4n*4n 關的4個2n 2n區塊使用一適應多樣性搜尋方法 20 1259727 (adaptive diversity search strategy)執行移動估測 (motion estimation) ; (D)判斷 4 個 2n*2n 區塊的移動成 本是否均小於第二臨界值；（E)若步驟（D)中判定均小於第 二臨界值，則該巨集區塊模式為2η*2η，並停止模式決定 5 方法。 由於本發明設計新穎，能提供產業上利用，且確有增 進功效，故依法申請發明專利。 【實施方式】 10 15 圖2係顯示本發明的快速巨集區塊模式決定方法的流 程圖，該方法係運用於一影像圖框序列編碼中。首先，= 步驟S3G5中判斷-胸6區塊在（()，〇)或預測移動向量 (predict ion motion Vector、PMV)處的移動成本是否小於 第臨界值’其中’移動成本為+ 的移動成本再加上第一 · p) ’ m=㈣，:為一移動向量（m〇t i〇n州⑽、 MV)，P=h，P/:為一預測移動向量（pMV)，與m_p)為一移動 向量資訊’“「轉㊇於：4一修正參數，㈣一臨界值 (U為具有相同模式的前2G個區塊中，找尋具有最小 為： 固定值。亦即該第一臨界值（7ϊ/ΐ6χΐ6) 16X16 ze{/|l ϋ20, ^^ith mode 16xl6}[e〇S ,(^^/)] + ， 該第一固定值（Δ77/16χ16)為6〇〇。 由於-個圖框（frame)中有大部分區域為背景而背景 20 1259727 .自域在移動向量估測時’可視為靜止或是全域平行移動。 故靜止時一區塊的移動向量為（〇，〇)。而全域平行移動 時，-區塊的移動向量可使用預測移動向量(PMV)而得到良 好的估測。對於這些背景區域，最佳模式通常為⑹ 5故於㈣S305中判斷一购6區塊在（〇〇)或預測移動向 量（PMV)處的移動成本是否小於該第一臨界值。 若步驟S305中判定小於第一臨界值，則執行步驟 S310，若否，則執行步驟S315。於步驟S31〇中設定該 巨集區塊模式為16*16,該巨集區塊的移動向量為（〇，〇) 10或是該預測移動向量（PMV)(路徑A)，並停止模式決定方法。 於步驟S315中，對該16*16區塊相關的4個8*8區塊 使用一適應多樣性搜尋方法（adaptive diversity seerxh strategy、ADSS)執行移動估測。 於步驟S320中，判斷4個8*8區塊的個別移動成本是 15否均小於第二臨界值。該第二臨界值為具有相同模式的前 20個子區塊（sub-macroblock、sub—MB)中，找尋具有最小 的移動成本再加上第二固定值。亦即該第二臨界值（) 為： 8x8 7€{/|1<z<20, Su^^zwith m〇de8xs}[cosi(M~^)]+Am8x8 ^ 20該第二固定值（)為150。若判定均小於該第二臨界 值，則執行步驟S325，若否，則執行步驟S330。 於步驟S325中，設定該巨集區塊模式為8*8，該巨集 區塊的移動向量為該適應多樣性搜尋方法（ADSS)執行移動 8 1259727 估測⑽時所找出的移動向量（路徑B)，並停止模式決定 方法。 於步驟S330中，對該16*16區塊相關的2個16*8區 塊及2個8*16區塊使用移動向量合併方法（m〇ti〇nvect〇r 5 merge，MVM)執行移動估測。 於步驟S335中，判斷該2個16*8區塊及2個8*16 區塊的移動成本是否均大於相關的4個8*8區塊的移動成 本，其中，該2個16*8區塊的移動成本為知叫』，該2 j=l 個8*16區塊的移動成本為(,·），4個8*8區塊的移 i=l 4 10成本為|>外*8(〇。若判定該2個16*8區塊及2個8*16區 塊的移動成本均大於4個8*8區塊的移動成本 (卖 C^8*16(z) > έ_8*8(/)且 Σσ⑽娜(，·) > ZcW ^ 1=1 2=1 S340(路徑C)，若否，則執行步驟3345(路徑D)。 於步驟S345中，對該16*16區塊使用移動向量合併方 15法（motion vector merge)，執行移動估測。於步驟S350 中，由該16*16區塊、2個16*8區塊及2個8*16區塊中 選擇移動成本最小者，並以該具最小移動成本的區塊作為 該巨集區塊模式’並停止模式決定方法。 於步驟S340中，對一個8*8區塊相關的8*4區塊及 20 4*8區塊使用移動向量分割方法（m〇ti()ri veetQ:r splitting)，執行移動估測。於步驟S355中，判斷該2 個8*4區塊及2個4*8區塊的移動成本是否均大於該8*8 1259727 區塊的移動成本，其中，該2個8*4區塊的移動成本為 2 ，該2個eg區塊的移動成本為〜8(〇，該8*8 1=1 區塊的移動成本為Ca^*8(/)。若判定該2個8*4區塊及2個 4*8區塊的移動成本均大於該8*8區塊的移動成本 2 5 (各c⑽㈣(0>C〇4(，·)且知，執行步驟S360(路 i=\ 徑E)，若否，則執行步驟S365(路徑F)。 於步驟S360中，設定該巨集區塊模式為8*8。於步驟 S365中’則對一個8*8區塊相關的4*4區塊使用移動向量 分割方法’執行移動估測。於步驟S370中，由4個4*4 10區塊、2個8*4區塊及2個4*8區塊中選擇移動成本最小 者’並以該具最小移動成本的區塊作為巨集區塊模式。於 步驟S375中，判斷4個8*8子區塊均完成，若否，重回步 驟S340 ’若是，則停止模式決定方法。 對於不同的模式，圖3顯示本發明排除模式的數目。 15 圖4、圖5及圖6為本發明、具有快速全域搜尋的低複雜度模 式（low-complexity mode with fast full-search、LCM-FFS) 方法及具有快速合併分割的低複雜度模式（low-complexity mode with fast merge-split search、LCM-MSS)方法的比 較。圖4係使用Foreman QCIF影像序列，圖5係使用Akiy〇 20 CIF影像序列，圖6係使用Mobile & Calendar QCIF影像序 列。由圖4、圖5及圖6中可知，本發明方法在峰值訊號雜 訊比（peak signal-to-noise ratio、PSNR)上非常接近 具有快速全域搜尋的低複雜度模式（LCM-FFS)方法，而位 1259727 元率（Mt-rate)僅稍微增加。但是本發明的計算量較習知具 有快速全域搜尋的低複雜度模式（LCM_FFS)方法減少一 半，亦杈具有快速合併分割的低複雜度模式（LCM_MSS)方 法減少。圖7係本發明排除模式數目的分析，其為使用 5 Foreman QCIF影像序列。由圖7中亦可明顯看出，本發明 技術由於先將一些模式排除，故本發明的計算量有明顯的 減少。 綜上所述，本發明快速巨集區塊模式決定方法的計算 量，由於先將一些模式排除，只需對剩下的模式進行計算， 10故本發明的計算量有明顯的減少而可解決習知技術所產生 计鼻量魔大的問題，增加編碼時的效率。 上述較佳具體實施例僅係為了方便說明而舉例而已， 本發明所主張的權利範圍自應以申請專利範圍所述為準， 而非僅限於上述實施例。 15 【圖式簡單說明】 圖1係顯示一位於現行圖框中的影像區塊及其鄰近的 衫像區塊。 圖2係顯示本發明快速巨集區塊模式決定方法的流程 20 圖。 圖3顯示本發明排除模式的數目的示意圖。 圖4、圖5及圖6為本發明與習知技術比較的示意圖。 圖7係本發明排除模式數目分析的示意圖。 11

1259727 【圖號說明】 區塊 26、28、30、32、34

12

Claims (1)

1259727 申請專利範圍 1 · 一種快速巨集區塊模式決定方法，其運用於影像圖 框編碼中，該方法包含： (A) 判斷一 4n*4n區塊在（〇,〇)或一預測移動向量（pMV) 5處的移動成本是否小於第一臨界值； (B) 若步驟（A)中判定小於第一臨界值，則該巨集區塊 模式為4n*4n，並停止模式決定方法； (C) 若步驟（A)中判定不小於第一臨界值，對該區 塊相關的4個2n*2n區塊使用一適應多樣性搜尋方法 10 (adaptive diversity search strategy)執行移動估測（motion estimation)； (D) 判斷該4個2n*2n區塊的個別移動成本是否均小於 弟—臨界值；以及 (E) 若步驟（D)中判定均小於第二臨界值，則該巨集區 15 塊模式為2n*2n，並停止模式決定方法。 2·如申請範圍第1項所述的快速巨集區塊模式決定方 法，其更包含： (F) 若步驟（D)中判定非均小於第二臨界值，對該4n*4n 區塊相關的2個4n*2n區塊及2個2n*4n區塊使用移動向量合 20 併方法（motion vector merge)，執行移動估測； (G) 判斷該2個4n*2n區塊及2個2n*4n區塊的移動成本 是否均大於4個2n*2n區塊的移動成本；以及 13 1259727 (H5)若步驟（H2)中判定該2個2n*n區塊及2個n*2n區塊 的移動成本非均大於該2n*2n區塊的移動成本，則對一個 2n*2n區塊相關的n*n區塊使用移動向量分割方法，執行移 動估測；以及 5 (H6)由該4個n*n區塊、2個2n*n區塊及2個n*2n區塊中 選擇移動成本最小者，並以該具最小移動成本的區塊作為 巨集區塊模式； (H7)重複步驟（H1)，直至該4個2n*2n區塊均完成。 • 6·如申請範圍第i項所述的快速巨集區塊模式決定方 10 法，其中，η為整數。 7·如申請範圍第1項所述的快速巨集區塊模式決定方 法，其中，η為4。 8.如申請範圍第1項所述的快速巨集區塊模式決定方 15 +Xmotion ·穴（m _ ρ)，ιη = (/^，:為一移動向量 (MV)’ 0 = 為一預測移動向量（pmv)，及（m 鲁 ·Ρ)為一移動向量資訊，^=(0.85.2^/3)^:為 一修正參數。 9 ·如申請範圍第1項所述的快速巨集區塊模式決定方 20 法，其中，該第一臨界值mi6xl6為： =_以。，庶ΐ^_[_(，)]+Δ7^16。 10 ·如申請範圍第9項所述的快速巨集區塊模式決定 方法，其中，該△7^1616為6〇〇。 15