TWI283132B - Apparatus for motion estimation using a two-dimensional processing element array and method therefor - Google Patents

Description

1283132

三達編號：TW1480PA 九、發明說明： 【發明所屬之技術領域】 本發明是有關於一種移動估計（Motion Estimation)裝置及 八方法i特別是有關於一種使用二維處理元件㈣⑽以 Ε1_ηί，ΡΕ)陣列之移動估能置及其方法。 【先前技術】 二像壓縮或影像編碼是電子元件中各種多媒體應用之重 要衣1¾移動估s十在影像壓縮當中則佔很重要的角色。例如， 職-4係、為主流影像壓縮標準之一且所應用的範圍很廣，從 局定義電視_TV)或數位多魏DVD光碟機等高位元率 (high-bn-me)、高品質影像元件到可擷取影像之手機或數位個 低位7^率行動處理裝置。在鹏G_4影像編碼 i王#動估^費相當多之計算時間以及大部份之系統 =，EG-4影像編碼而言，6〇%到8〇%之計算時間係用在 ㈣估計上。就計算負載及資源使用方面，在處理元件中且特 —般具有限的功率容量、有限的記憶資源及有限的處理 功率寻之行動處理裝置中，移動估計是執行Μ 重要因子。勒馬斋之 ,仃影像壓縮之編碼器中移動估計係為最複雜的 子，使目二： 短暫冗餘，以找出移動因 Λ 則、、構之目前區塊可以由參考座標之參考區塊來預 與目前區塊相較，參考區塊具有最小之誤差 = ::)。許多移動估計之區塊比對演算法(Β 品匕比對决异法中，例如是三步搜尋（tts)或四步搜尋（^) 5 1283132 三達編號：TW1480PA 之步搜尋演算法（Step Se⑽h Alg〇Hthm)係發展用崎低計瞀冗 餘（Computation Redundancy)以及提昇效能。然而，這些搜:演 异法所使用之資料流通常不穩定以致於演算法之硬體操 雜。此外，有鑑於處理裝置所提供之有限資源，處理裝置純 行步搜尋演算法之整體效能並無法達到演算法之理論效能 行動處理裝置而言更是如此。 ’ 在文獻上可找到許多操作BMA之結構式解決方法。例如 Costa等人於1995年五月在消費電子學IEEE會刊第Μ卷 部第248頁至第257頁所刊載之「階層式移動估計之超大規模 積體電路（Very Large Scale lntegrated Circuhs，vLSI)紝構以 及Kim等人於1997年二月在消費電子學ieee會刊第卷 1部第24頁至第33頁提出基於TSS演算法之硬體結構並著重 於PE陣列之資料流。然而，這些硬體結構所使用之吨陣 料流很複雜並專門用於TSS，導致PE陣列外部存在一些、 首先，PE陣列中複雜之資料流導致PE陣列控制電路之操 作更複雜。其次，在移動估計中PE陣列複雜 莫 =重《行畫素資料記憶趙讀取之操作。在_ = 益、帛私動 <古计結才冓及晝面記憶體之記憶體匯流排，以及 編碼器之其它單元會因忙於進行這些重複之讀取操作而降低整 體之效能。雖'然這個問題可藉由提供額外晝素資料記憶體區塊 ^緩衝來自晝面記憶體之晝素資料，並於TSS演算法之每一搜 尋步前，將所需之畫素資料載人記憶區塊而直接解決。然移動 估計之整體效能仍然、降低，且需要更高之記憶體成本。另外， ί TSS '寅异法之資料流需精密設計，較難適用於其它步搜 尋演算法’例如FSS演算法之結構。就有限之f源環境來說， 1283132 三達編號：TW1480PA 例如是行動處理穿 非常重要，必須_ “陣列外部之問題對於硬體操作上 加以使用。"改進以提昇裝置效能並可提供終端使用者 供電路因提供—種移動料結構以解決上述問題並提 电路°又计之擴充性及彈性。 【發明内容】 有鑑於此，本發明的目的就是在提供-種且有-唯處理元 件（2DPE)陣列之移動 ”有―、准處理疋 ^表置及，、方法。根據本發明，提供一 =PE陣列之資料流結構，以降低2D pE陣列控制硬體之 I、使用此資料流結構，可以降低好幾倍記憶存取量，因 而達到降低計算時間以及功率損耗之目的。2D PE陣列也可以 由其架構及資料流結構受益，並可達到降低移動估計系統電路 面積之目的。使用職陣列單元之移動估計系統也因而更適 用於具有有限電源供應之行動處理裝置，例如手機或PDA。

根據本發明的目的，提出一種移動估計裝置，包括一 PE 陣列。PE陣列單元包括延遲單元陣列以及pE陣列。延遲單元 陣列包括複數個水平延遲單元（HDU)以及複數個垂直延遲單元 (VDU)。共有三列HDU，各列HDU具有第—HDU以及第二 HDU。每個HDU包括一輸入端以及一輸出端。在各列hdu中， 第一 HDU之輸出端係連接第二HDU之輸入端。延遲陣列單元 包括第一 VDU以及第二VDU。各VDU具有一輸入端以及一輸 出端。第一 VDU之輸入端係連接於第一列中第一 HDU之輸入 端，第一 VDU之輸出端係連接第二列中第一HDU之輸入端以 及第二VDU之輸入端’弟二VDU之輸出端係連接第三列中第 一 HDU之輸入端。PE陣列包括三列PE，各列pe包括第一 pE、 1283132

三達編號：TW1480PA 為讓本發明之上述目的、特徵、和優點能更明顯易懂，下 文特舉一較佳實施例，並配合所附圖式，作詳細說明如下： 【實施方式】 。本發明之第一實施例提供一種二維處理元件（2D ]?]£)陣 單兀。這個陣列單元係配置以進行移動估計N步搜尋演算法之 一搜哥步，而在搜尋區域中畫素資料係以規律且順序地掃描書 素之方絲讀取。搜尋區域之多個區塊係與目前區塊平行^

比較三第二實施例則提供進行全點（FulKpel)移動估計之2D PE 陣列單元配置’以進行移動估計之FSS演算法。特別是，在搜 尋區域之^個區塊剌以與目前區塊平行地作比較。且搜尋區 域中晝素貧料係以根據本發明之畫素掃描順序來讀取。基於此 配置可σ十來自目月“己憶體及參考記憶體之規則資料流，允 ，一列單元之控制電路可以更簡化方式來操作。在本發明: 第二貫施财，顯卿動估計純結構，讀行移動估計 並整合於-電路巾。2D PE陣列單元可設計得更具擴充性及彈 性。在其它實施例中，更使用2DpE陣列來進行半點(祕⑽ 移動估計。 二維處理元件（2D PE)陣列單元 清參考第1圖’其繪示根據本發明第一實施例用於移動估 計之^維處理元件（2DPE)陣列單元⑽結構圖。處理元件㈣ 陣列單兀100包括延遲單元陣列(Deiay U也Arra幻以及pE陣 ^ PE陣列具有三列PE，且每列具有第—PE、第二PE以及 :::E“特別疋母個PE具有第-輸入端、第二輸入端，誤差 6里力端，以及控制端。例如’ ΡΕ0包括第一輸入端A0、第 1283132 屬

•三達編號：TW1480PA ; 二輸入端B0、誤差計量輸出端sadO(例如誤差計量為絕對差值 (SAD)之總和）、以及控制端PEOen。延遲單元陣列包括多個水 平延遲單元（HDU)以及多個垂直延遲單元（VDU)。PE陣列之第 二輸入端B0至B8係分別連接至延遲單元陣列以形成2D PE陣 列單元。 於第1圖中有三列HDU，且每一列具有第一 HDU以及第 二HDU。每一個HDU具有一輸入端以及一輸出端，且在同一 列中第一 HDU之輸出端連接第二HDU之輸入端。例如，第一 _ 列具有HDU 140以及HDU 142,且HDU 140的輸出端連接HDU 142之輸入端。第二列具有HDU 160以及HDU 162,且HDU 160 之輸出端連接HDU 162之輸入端。第三列則具有HDU 180及 HDU 182,且HDU 180之輸出端連接HDU 182之輸入端。此外， 垂直延遲單元（VDU)包括第一 VDU 150以及第二VDU 170，且 每個VDU具有一輸入端以及一輸出端。第一 VDU 150之輸入 端連接至第一列中第一 HDU 140之輸入端。第一 VDU 150之 輸出端連接至第二列中第一 HDU 160之輸入端以及第二VDU 170之輸入端。而且第二VDU 170之輸出端連接至第三列中第 ’ —HDU 180之輸入端。 第1圖係繪示根據本發明第一實施例PE陣列以及延遲單 元陣列之間連接關係。在PE陣列之每一列中，第一 PE之第二 輸入端連接至第一 HDU之輸入端，第二PE之第二輸入端連接 至第一 HDU之輸出端，且第三PE之第二輸入端連接至第二 f' HDU之輸出端。在PE陣列之第一列中，第一 PE 110 (ΡΕ0)之 - 第二輸入端B0連接至第一 HDU 140之輸入端，第二PE 112 (PE1)之第二輸入端B1連接至第一 HDU 140之輸出端，且第三 PE 114 (PE2)之第二輸入端B2連接至第二HDU 142之輸出端。 10 1283132 «

• 三達編號：TW1480PA 在PE陣列之第二列中，第一 PE 120 (PE3)之第二輸入端B3連 接至第一 HDU 160之輸入端，第二PE 122 (PE4)之第二輸入端 B4連接至第一 HDU 160之輸出端，且第三PE 124 (PE5)之第二 輸入端B5連接至第二HDU 162之輸出端。在PE陣列之第三列 中，第一 PE 130 (PE6)之第二輸入端B6連接至第一 HDU 180 之輸入端，第二PE 132 (PE7)之第二輸入端B7連接至第一 HDU 180之輸出端，且第三PE 134 (PE8)之第二輸入端B8連接至第 二HDU 182之輸出端。每一個PE係於控制端致能時用以累計 • PE第一輸入端之參考資料（Reference Data)與PE第二輸入端之 晝素資料（Pixel Data)之間特定形態之誤差計量。 第1圖所示之2D PE陣列單元係配置用以執行全點移動 估計。2D PE陣列單元使用移動估計N步搜尋演算法之其中一 搜尋步，並於以規律且順序地掃描晝素之方式讀取搜尋區域之 晝素資料時進行。當搜尋區域掃描完成，且對應之晝素資料完 全饋入2D PE陣列單元時，以平行方式進行（對應特定檢查點） 搜尋區域之多個區塊與目前區塊（Current Macro-block)之比較 以產生對應檢查點之誤差計量（Error Measure)。再根據所得到的 B 誤差計量決定具有最小誤差計量之檢查點。也就是說，可於掃 描搜尋區域過程中使用2D PE陣列單元進行移動估計N步搜尋 演算法之一搜尋步。因此，可使用2D PE陣列單元進行任何之 移動估計N步搜尋演算法。 在實際之應用中，在操作2D PE陣列單元時會選擇進行一 ， 特定之誤差計量。2D PE陣列單元可使用任何之誤差計量，例 - 如是絕對差值（SAD)之和、方均誤差（MSE)、或絕對平均誤差 (MAE)，也可以選擇使用一種或結合多種誤差計量結構。為了 說明方便，接下來之實施例係使用SAD為例。請參考第2圖， 11 1283132

三達編號：TW1480PA 其繪示在第一輸入端A與第二輸入端B之資料間進行SAD之 處理元件（PE)200之結構圖。PE 200包括絕對差值元件（Absolute Difference Device)210 以及累計器（Accumulator)250。以同步對 應方式將參考區塊（Reference Macro-block)及目前區塊之晝素 值依序應用於絕對差值元件210,可根據底下之公式（以16點xl6 點之目前區塊為例）利用累計器250決定SAD值。 SAD = Z j Ref—Datax，y — Curr_Datax，y | jc=0 〜15,少=0 〜15 > 執行全點移動估計之2D PE陣列單元配置 請參考第5圖，係繪示依照本發明第二實施例執行全點移 動估計之2D PE陣列單元配置圖。由圖可知，所有PE之第一 輸入端係連接在一起，使得送至2D PE陣列單元之參考資料可 同步地送至所有PE之第一輸入端。同時，當目前資料送至第一 列中第一 HDU 140之輸入端以及第一 PE 110 (ΡΕ0)之第二輸入 端B0時，延遲單元陣列產生具有特定延遲時間之八種不同資料 流送至PE之個別第二輸入端。在第二實施例中係依序讀取參考 資料並同步送至每一個PE之第一輸入端，並依序讀取區塊之目 > 前資料送至每一個PE之第二端，使得每一個PE可正確執行搜 尋區域之特定參考區塊與目前區塊之誤差計量，例如SAD。為 了符合需求，必須視2D PE陣列單元所使用之移動估計步搜尋 演算法來設定晝素掃描順序、延遲單元陣列以及控制PE陣列。 卜四步搜尋演算法 - 在此實施例中，如第5圖所示，2D PE陣列單元將執行移 動估計四步搜尋（FSS)演算法。FSS演算法可參考1996年六月 由Po等人刊登在視訊科技電路及系統IEEE會刊第6卷第3部 12 1283132

三達編號：TW1480PA 第313頁至第317頁。根據此文獻，FSS演算法使用如第6B圖 所示於第一步5x5視窗中具有九個檢查點之中央趨^ (Center-biased)搜尋樣式。在搜尋樣式之相鄰兩個檢查點間之步 幅（Step S1Ze)STEP_SIZE為2。搜尋視窗中央接著平移至^有= 小區塊變料量（BDM)之檢查點。下兩步之解㈣大何= 小B D Μ檢查點而定。假如最小B D M檢查點 窗的中央，進行 錢讀白層 具有3x3搜尋視f之最後―步（第四步）搜尋。否則，搜 ►大^持在第二步或第三步之5X5大小。在最後一步中、，搜函尋 視固縮小為3x3並搜尋到此小視窗為止， 在-演算法中，一步係表示搜尋在搜最小 m查點。在實際應时，需使用目前記憶體儲存待編碼之 二二t貝枓’且需使用參考記憶體儲存由解碼先前晝面得到 查構旦面晝素資料。新建構晝面用為解碼編碼過後的目前 旦面之記憶體。在參考記憶體中，

Ref—Data，係對 ：素貝枓稱為參考貧料 新建構晝面之晝素，並為人位元之亮度書 素值。在目前記憶體中，書辛資料 欠 又旦 鹿曰义金工玉 Τ旦言貝枓稱為目刚資料Cun·—Data，對 ;:1之旦素’並為八位元之亮度晝素值。在-步中，如 區，其中_ ::=為:，^ 61〇mnge.y ra咖 為16點x16點，搜尋區域 =16 +—step S~IZE x-range =16 +STEP—SIZEx2，且 y-邮如 —Εχ2。在第6B圖中，於第一步中顯 九個檢查點，且對應每個檢查點之一數值表干搜尋位自 序。第犯圖之點〇〜莫& 数值表不技哥位置之順 6A圖中。接著，《義為起始點，同時顯示於每一搜尋步之第 之下-個檢杳畔點1表示用以計算誤差計量（對應一參考區塊） ^點8為最後一個檢查點。 13 1283132 三達編號·· TW1480PA 晝素掃描順序 請參考第7圖，其繪示依照本發明第二實施例搜尋區域之 畫素掃描順序示意圖。一步之搜尋區域之參考資料係一行一行 地由標示R(〇,〇)之起始點依序讀取一直到標示為R(x_range-1， y_range-l)之搜尋區域終點。 同樣地，目前區塊之晝素掃描順序或目前區塊晝素值之讀 取也是依序式地，一個晝素接一個晝素，一行接著一行。當PEO | 被致能時，亦即當輸入PEO控制端PEOen之致能信號為「致能」 狀態時，目前區塊之晝素值係以晝素掃描順序來讀取。在一個 實施例中，當PE0被致能時，在讀取一筆參考資料之前立即先 讀取一筆目前資料。在第5圖中，於FSS演算法一步中，由PE 決定對應第6B圖檢查點之誤差計量，例如是本實施例之SAD。 例如，PE0用以使用誤差計量來比較目前區塊與檢查點（0,0)之 參考區塊，其中檢查點位於參考區塊左上角。例如於第6B圖 中，PE4 係用以比較目前區塊與檢查點（STEP—SIZE， STEP—SIZE)，例如是（2,2)之參考區塊。就PE之此項功能而言， _ Ref_Data以及Curr_Data必須正確，例如是同步送至PE陣歹， 使每一個PE可以決定檢查點之誤差計量，亦即SAD。以PEO 為例，當搜尋區域之晝素（〇,〇)晝素值及區塊之晝素（〇,〇)畫素值 分別同步送到第一輸入端A0以及第二輸入端B0時，可正確地 獲得絕對差值。其它之PE可藉由延遲單元陣列正確地輸入晝素 ^ 值。就PE0而言，當讀取一列目前區塊中最後晝素之晝素值 - Curr_Data並送至第二輸入端B0之後，PE0便被非致能。此時， 持續進行搜尋區域之掃描，但暫停掃描目前區塊直到掃描到下 一列搜尋區域之第一個晝素。當掃描到下一列搜尋區域之第一 14 1283132

三達編號·· TW1480PA 個畫素時，PEO再次被致能並繼續掃描目前區塊。因此，下一 列目前區塊之晝素值以及下一列搜尋區域之晝素值可以正確 地，例如是同步地送至PEO。以上述方式進行目前區塊之掃描 使得其它PE可以接收到正確之晝素值以決定對應之誤差計量。 延遲單元陣列 搜尋區域以及目前區塊之掃描皆以依序方式，一個晝素接 著一個晝素，一行接著一行的方式進行。在第二實施例中，當 搜尋區域掃描完成時，將決定出九個檢查點之九個誤差計量以 及此步之MBDM。利用上述之目前區塊晝素掃描順序，延遲單 元陣列提供具有特定延遲時間之八個不同資料流至PE之個別 第二輸入端，以便搜尋區域之晝素值以及延遲單元陣列之輸出 端晝素值可以正確地饋入至PE中。 在FSS演算法中，第一步、第二步及第三步之步幅為2， 而最後一步之步幅則改為1。每一個HDU之延遲時間為 STEP—SIZE個時間單位，而每一個 VDU之延遲時間為 STEP—SIZExP，其中P為區塊之寬度（晝素個數），且本實施例 中P值為16。請參考第3圖，其繪示可選擇於一個或二個時間 單元之後輸出八位元Curr_Data之HDU 300之結構圖。HDU 300 包括二個正反器（Flip-flop) 310及320、一個多工器（Multiplexer) 3 50以及一及邏輯閘（AND Logic Gate)3 60。正反器310為時脈 閘極單元（Clock Gating Cell)。HDU 300可利用多工器350之選 擇輸入端（MODE)選擇於一個或二個時間單位後輸出八位元 CurrJData。請參考第4圖，其繪示用以選擇於16x1或16x2個 時間單位後輸出八位元Curr_Data之VDU 400結構圖。VDU 400 包括32個正反器，即正反器401到正反器416、正反器421到 15 1283132

三達編號：TW1480PA 正反器436，以及及邏輯閘460，其中所有正反器為時脈閘極單 元（Clock Gating Cell)。VDU 400可利用多工器450之選擇輸入 端（MODE)選擇於16x1或16x2個時間單位（周期）後輸出八位元

Curr_Data。因此，藉由輸入控制信號至延遲單元陣列之HDU 及VDU中多工器之選擇輸入端，延遲單元陣列可提供具特定延 遲時間之八個不同資料流至PE之個別第二輸入端，因而，搜尋 區域之晝素值及目前區塊之晝素值可同步饋入至PE中。當步搜 尋演算法中下一步之步幅改變時，藉由輸出一致能信號至 _ MODE端，延遲單元可以適當地具有個別延遲時間。 例如，在FSS演算法之第一步中，步幅為2。以PE1為例， PE1負責決定搜尋區域中目前區塊與起始點為（2,0)之區塊之間 之誤差計量。因此，當搜尋區域中對應（2,0)至（17,0)之Ref_Data 依序地饋入至PE1之第一輸入端A1時，PE1即致能。同時， 對應目前區塊之（〇,〇)至（15,0)也必須依序地饋入PE1之第二輸 入端B1。請參考第5圖，HDU 140係以延遲時間STEP_SIZE(即 兩個時間單元）將Cunr_Data饋入至PE1之第二輸入端B1完成 這個需求。因此，當延遲二個周期時間將Ref_Data及Curr_Data ► ~ 正確且同步地饋入至ΡΕ0時，Ref_Data係正確且同步地饋入 PE1。對其它之PE而言，例如是PE3以及PE8，操作方式相似， 不同在於PE於不同周期致能且饋入至PE第二輸入端之

Curr_data係延遲不同周期大小。 另外，HDU及VDU也稱為延遲線並可以其它邏輯線路來 ‘操作。假如由2D PE陣列單元執行之步搜尋演算法在不同之搜 -尋步當中具有不同之步幅，正反器，例如是HDU及VDU的數 目可根據步搜尋演算法之需求而調整。 16 1283132

- 三達編號：TW1480PA ； PE陣列之控制 PE陣列之每一個PE具有控制端PEZen，其中z代表〇至 8之數字。請參考第7圖，掃描搜尋區域使得RefJData以規則 方式饋入至每一個PE之第一輸入端。CurrJData係饋入PE〇， 且以特定延遲時間由延遲陣列單元輸出之Curr—Data係饋入其 餘之PE，即PE1至PE8。以PE4為例，在搜尋區域掃描過程中， 對應某些晝素例如是搜尋區域之（〇,〇)至（1，15)之Ref—Data並不 影響檢查點（2,2)之誤差計量決定。因此，致能信號係控制pE4 馨不處理落在參考區塊範圍外之Ref一Data。根據本發明之第二實 施例，可提供致能周期使得PE陣列單元正常操作。 請參考第8圖，PE致能周期係可直觀地將搜尋區域再細分 為9個子區域來加以定義。搜尋區域係晝分為具有與目前區土免 相同大小之子區域子集，分別關連一系列檢查點（0,0)， (STEP_SIZE，0)，（2xSTEP_SIZE，0)，（0，STEP— SIZE)， (STEP_SIZE，STEP_SIZE)，（2xSTEP_SIZE，STEP_SIZE)， (0,2xSTEP_SIZE)，（STEP_SIZE，2xSTEP_SIZE)， (2xSTEP—SIZE，2xSTEP_SIZE) 〇各檢查點係定義為每一個子區 , 域所對應之一起始點。在第8圖中，PEO_enable_cycle， PE4_enable—cycle，PE8_enable_cycle 係分別以方格 810、814、 818來表示並分別關係至檢查點（0,0)，（2,2)，（4,4)。利用致能周 期之定義，PE陣列之控制可方便且操作更簡化。例如，可使用 控制邏輯電路來判斷那一個子區域包括對應搜尋區域中 ^ RefJData之晝素R(i，j)。對每一個判斷為包括晝素R(i，j)之子區 . 域，會致能對應之一個致能信號並送至對應檢查點之PE控制 端0 例如，當對應（2,2)之RefJData被讀取時，控制邏輯電路 17 Λ1283132

• 三達編號：TW1480PA : 係判定 PEO_enable—cycle、PE 1—enable—cycle、 PE3-enable_cycle 及 PE4__enable_cycle(四個子區域）包括晝素 (2,2)。對應判定為包括晝素（2,2)之四個子區域之致能信號，即 PEO—Enable 、PEI—Enable 、PE3—Enable 、PE4—Enable 被致倉巨且 輸出至對應檢查點（0,0)、（2,0)、（0,2)、（2,2)之PE控制端PEOen、 PElen、PE3en、PE4en 〇 對應執行FSS演算法之第二實施例，表一列出9種PE之 致能狀態。表一具體列出當子區域中包含有對應搜尋區域晝素 參 （X，Y)之Ref—Data時將標示為PEZ_Enable(Z= 〇〜8)致能信號致 能之狀態。值得注意的是，表一中第二欄之狀態係定義全點移 動估計之前n-1步之子區域，而第三欄之狀態則定義全點移動 估計最後一步之子區域。此外，在第二實施例中，致能信號 PEZ—Enable (Z二0〜8)係分另q饋入至pE0至pE8之控制端 PEZen(Z=0〜8)。 表一

_ 致ϋ態 全點 全點 第1步至第η-1步 第n步(最後一步） PEOEnable X=0 〜Ϊ5 X=0 〜15 Y=〇 〜15 PElEnable X = step size 〜（15+step size) X=1 〜16 Y = 0 〜1—5 ~ Y=〇 〜15 PE2_Enable X=2><step_size 〜（15+2xstep_size) Χ=2 ~ 17 Y=0 〜15 ~ Υ=0 〜15 PE3_Enable Χ=0 ~ 15 Χ=0 〜15 Y = step size 〜（15+step size) Y=1 ~ 16 PE4_Enable X = stepsize 〜（15+step_size) X—1 ~ 16 X= step size 〜（15+step size) Y=1 〜16 PE5_Enable X=2Xstep_size 〜（15+2><step_size) X=2 ~ 17 Y = step_size 〜（15+step size) Y=1 〜16 PE6_Enable ϋ 15 ϋ 15 Υ=2χstep size 〜（15+2 xstep size) Υ=2 〜17 PE7一Enable X = stepsize 〜（15+step_size) X=1 〜16 |Y=2><step size 〜（15+2><step size) Y=2 〜17 PE8—Enable X=2><step_size 〜（15+2><step_size) ~Χ=2 〜17 Y=2><step size 〜（15+2><step size) Υ=2 〜17 18 1283132

三達編號：TW1480PA 移動估計系統之結構 請參考第9圖’其緣示依照本發明第三實施例移動估計系 統（Motion Estimation System)! 000之結構方塊圖。移動估計系 統1〇〇〇包括移動估計單元1100、記憶體讀取單元（Μ_π Reading Unit)1500、控制單元16〇〇以及位址產生單元㈤办⑽ Gelation Unit)1700。第9圖繪示之系統係可輪出例如是哪 演异法之步搜尋演算法之移動向量（Mc)ti()n V⑽。小移動估計系 統1000更可配置以執行任何之移動估計N步搜尋演算法，例 如三步搜尋演算法。 移動估計單元1100包括2DPE陣列單元100、多工器 (MUltiPlexer)1150、暫存器單元（以咖如Unit)U6〇以及最°卜 SAD 判斷單元（Determination Unit)l 170。 記憶體讀取單元1500係為一種提供移動估計系統1〇⑻之 記憶體讀取介面，其中記憶體讀取介面可搭配連接移動估計系 統1 〇〇〇之記憶體匯流排1 〇所使用之至少一通訊協定。記憶體 匯流排10例如是連接至參考記憶體以及目前記憶體。因此，移 動估計系統1000可透過記憶體讀取單元15〇〇由目前記憶體以 及參考記憶體讀取目前資料以及參考資料。 控制單元1600係用以進行步搜尋計數。控制單元16〇〇可 以是有限狀態機器（Finite State Machine)，例如包括二個計數電 路（Counter Circuit)，即X計數器以及γ計數器，用以進行步搜 哥计數。X計數器用以計算一列搜尋區域讀取晝素值之書素數 目。y計數器則用以計算搜尋區域中讀取晝素值之晝素欄位 數。當讀取對應搜尋區域晝素之一筆Ref—Data資料時，X計數 器之計數值累加1。而當X計數器計數值達到一預設值 19 •1283132

• 三達編號·· TW1480PA ； X_max_count時，Y計數器計數值累加1。然後，X計數器計數 值重置為0。當Y計數器之計數值達到y_range時，結束此步 搜尋演算法。X_max_count係為搜尋區域之寬度（晝素數目），即 X—max—coimt^x—range 〇在全點移動估計之第一步至第（n_l)步 中，X_max—count二x_range=macroblock_size+STEP—SIZE><2 〇 例 如，在FSS演算法中，X—max_count=16 + 2><2=20，其中除了最 後一步之外，其它步之步幅STEP_SIZE=2。而全點移動估計之 最後一步中，X_max_count=x_range，而 STEP_SIZE 值可以是 φ 較小值。在 FFS 演算法之最後一步中， X+max+count^M+lx〗：]^，其中 STEP_SIZE二1。記憶體讀取單 元1500產生記憶體讀取信號Ref_ready並送至控制單元1600。 記憶體讀取信號是用以通知X及Y計數器更新其計數值。例 如，當對應一筆搜尋區域之一筆Ref_Data資料由例如是參考記 憶體讀取時，Ref_ready設定為致能狀態，例如是高準位。PE 致能周期係根據X以及Y計數器提供之目前計數值X及Y來 決定。 位址產生單元1700包括PE致能邏輯電路1750以及移動 ® 向量（MV)產生邏輯電路1770。PE致能邏輯電路1750由計數器 單元1600之X及Y計數器接收目前計數值X及Y，再根據目 前計數值X及Y以及表一產生致能信號，然後將致能信號輸出 至移動估計單元1100之2D PE陣列單元100。如上所述，掃描 搜尋區域之後，可獲得九個誤差計量，例如是第二實施例中對 卜 應九個檢查點之九個SAD。而最小SAD判斷單元1170可判定 • 最小誤差計量並加以輸出◦位址產生單元1700接收由最小SAD 判斷單元1170輸出之最小誤差計量。MV產生邏輯電路1770 產生搜尋演算法最後一步之移動向量。此外，位址產生單元1700 20 1283132

三達編號：TWM80PA 產生記憶體位址並提供給記憶體讀取單元i5〇〇 ,因而可由記情 體讀取單元测讀取目前資料人至移動估計單元謂Γ 移動估計系統i _係用以執行移動估計N步搜尋演算 法。假設移動估計系統1000係以時脈信號clk進行操作。首 先’2DPE陣列單元配置如第5圖所示，用以進行全點移動估 計。接者，由起始點（0,0)開始讀取搜尋區域610中苎素之 _資料’如第6A圖所示。並根據第7圖之晝素掃描順 序將言買取之R(Data資料饋入至移動估計單元ιι〇〇。當讀 .應晝素之Ref_Data資料日夸，如上所述，控制單元⑽〇之乂及 丫計數器開始計數，且PE致能邏輯電路175〇產生致能信號 PEZ—enable(Z=〇〜8)並輸出至即車列單元1〇〇。當讀取 域之Ref一Da二資料並饋入至移動估計單元i丄〇〇時，目前區塊 之CUrr_Data貝料也以目前區塊之晝素掃描順序來讀取並饋入 =動估計單元1100。2则陣列單元⑽之每一個pE判斷 疋否要根據致能信號PEZ_enable處理目前周期中饋入PE之資 料並於PEZ_enable信號致能pE時計算正確的誤差計量。二 寻區域掃描完成且對應之晝素資料完全饋入2D PE陣列單^ :夺’搜尋區域九個參考區塊(對應特定檢查點)與目前區塊之比 較係以平行方式進行，以產生對應之誤差計量，亦即第犯 知例中對應檢查點之SAD。因此，可根據最小灿判斷單元 二〇提供之誤差計量來決定具有最小誤差計量之檢查點。也就 =兄’在掃描搜尋區域中，可由2DpE陣列單幻⑻進行移動 十N步技尋演异法之—搜尋步。根據—搜尋步產生的結果， =動估計系統i _可以根據N步搜尋演算法執行依序步°搜尋 =得-最佳點，亦即最後-步之最小區塊變形計量，而移 向里即由此決定。因此，透過2DPE陣列單元_，移動估 21 • I283J32

• 三達編號：TW1480PA : 計系統1000可執行移動估計之任何N步搜尋演算法。 特別是在2DPE陣列單元100之配置上。 … ⑽之麵以及VDU係根據步搜尋演算法中目前搜尋車^几 巾田來配置。例如，當全點移動估計FSS演算法之第_/ ^ 瞻—㈣值設定為2時，如第3圖所示，咖係藉= 4戒饋入選擇輸入端__使得多工广 輸出之方式來設定。因此，每一個卿豆古T =擇正反益310 G母個HDU具有二個時間嚴

期）之延遲時間。同樣地也設定每個VDU並具有32個時。元 •(周期）之延遲時間（周期）。當2DPE陣列單元⑽執行FS 异法之最後一步時，每一個刪係設定為具有-個時間單元之 η盆r一個vdu係設定為具有16個時間單元之延遲 個實施例中，可使用2DPE陣列單元100,在 =序搜哥步中步幅可由4改變為2，或由2改變為i，以執行三 v搜哥。在這種情況下，可根據第3圖所示之聊扇來調整 2DPE陣列單元1〇〇中聊之結構以具有四個時間單元之更長 延遲時間，亚可選擇具有一個、二個或四個時間單位之延遲時 間。同樣地，2DPE陣列單元1〇〇之結構也可以加以調整 至具有16X4個時間單位之更長延遲時間，並可選擇具有16、 32或64個時間單位之延遲時間。 在全點移動估計中，係一行一行依序地讀取搜尋區域之 Ref—Da=資料。這此實施例中，當信號pE〇,仙為致能狀態 日^取對應搜尋區域晝素之—筆參考資料之前會先讀取對 • 應目前區塊之一筆目前資料。 • 在一個實施例中，可於2D PE陣列單元1〇〇之HDU以及 VDU 吏用閘極時脈技術ci_ 來控制移位 暫存器以達到有效降低功率耗損之目的。由記憶體讀取單元 22 1283132

三達編號：TW1480PA 15〇〇產生之記憶體讀取信號Ref—ready用以控制2D PE陣列單 元100之延遲單元陣列。例如，在全點移動估計中，HDU致能 k號係設定為對應記憶體讀取信號Ref_ready之一邏輯狀態， 且VDU致能信號係設定為相當於邏輯運算結果（Ref_ready &(X—count<16))之一邏輯狀態，其中當由參考記憶體讀取搜尋 區域晝素之Ref—Data資料時，Ref一ready係設定為高準位狀態。 如第3圖所示，HDU致能信號係饋入HDU之HEN端，而VDU 致月b彳5號則如苐4圖所示饋入至VDU之VEN端。時脈信號CLK ►係饋入至CLK端。 效能 在MPEG-4之環境下，區塊大小例如是ι6χ16個晝素。假 叹對應搜尋區域晝素之一筆參考資料Ref—Data，以位元組方式 排列於一個周期中讀取，且對應區塊中四個依序晝素之四塊目 刖貝料，以子元方式排式於一個周期中讀取。於一個實施例中， 第9圖繪示移動估計單元11〇〇之潤飾圖。暫存器單元1丨6〇係 _ 帛以儲存對塊目前資料（32位it)，且多ji器115Q係用以由暫存 為1160中選擇一筆目前資料（8位元），並輸出所選定之目前資 =至2D PE陣列單元1〇〇。全點移動估計FSS演算法之第一步 需要讀取（16+2χ2)χ(16+2χ2)=400塊參考資料以及讀取 256塊目釗資料，且其步幅為2。由於儲存於參考記憶體 、 考資料係以位元組方式排列，而非字元方式排列，參考資 • ，疋以一位兀組接著一位元組方式來讀取及存取。那是假設在 最佳狀況下，記憶體讀取單元可於一個周期内回覆一筆參考資 =。然而，儲存在目前記憶體之目前資料係字元排列方式且目 前資料係一字元接著一字元方式存取及讀取。在32位元之記憶 23 •1283132

二達編號：TW1480PA : 體匯流排系統中，係假設在最佳狀況下，四塊目前資料皆可在 個周期内由記憶體讀取單元回覆。因此，在此假設下，全點 移動估计之第一步需要4〇〇 + 64 = 464個周期才能完成。在最後— 步中，必須讀取（16+lx2)x(l6+lx2)二324筆參考資料。也就是 口兒王點移動估計之最後一步係以324+64二3料個周期來完成。 口此在最差的情況下，對一個目前區塊之四步搜尋需要大約 464x3+324=1716個周期來完成。 另外，早期結束是四步搜尋演算法之特色之一，平均來 •說，移動向量可於大約2·5步中來決定，平均之計算時間約為 1716χ2,5/4=1〇72·5 周期。 # 優點 上述實施财2D ΡΕ陣料元仙平行操作之九個ρ 建構’且—以簡單順序來提供資料流，並進行對應之控制。 如弟7圖所示’由於晝素掃描之順序係為順序性的， 2D ΡΕ陣列單元之硬體操作以及位址產生方式也具規則性I單 純化。因此，可降低移動估計系統所需之電路面積。 在移動估計之計算過程中mDpE陣列單元之來 料及目前資料可適當地再重覆使用。2DPE陣列單元之^曾、# 度係比習知僅使用—個找之⑽轉列單元要快九^ 此外，2請陣列單元記憶體存取之次數係° t:PE陣列單元要少九倍。由於功率損耗正比於記憶體存取 二:數二=低記憶體存取之時間，便能有效節省犯 早Γ 。因此，使用2DPE陣列單元之移動估計季= =用於有限電源供應之行動處理裝置，例如是行動電話Γ 24 1283132

三達編號：TW1480PA 此\，根據本發明之移動估計系統，可降低對記憶體匯流 卜之存取-人數，因而提高記憶體匯流排之利用性。 由於不需要如一些習知步驟中暫存參考資料之額外 塊，因此也可節省記憶體資源。根據本發明之實施例， 4考貧料饋入至2D PE陣列單元時執行移動估計之計算。 再者，2D PE陣列单元係為一種彈性結構，可以適用於不 估計演算法’且可擴充其利用性。特別是如本發明上 例所述，2DPE陣列單元可用以執行移動估計N步搜 >哥决异法。2D ΡΕ陣列單元可使用於支持特定形式演算法之 動估計系統。除了 FSS演算法之外，任彳Μ 、 如-田於教^ /麦之外任何Ν步搜尋演算法，例 =:移純計之三步搜尋或⑽搜尋演算法皆可透過丨 牛牛卩％早（來執行，#3_3_3_1搜尋演算法之第-步到第四 =分別為3、3、3及“具…陣列單元之移動: 算法。 、擇性地支板各種次异法，例如FSS以及TSS演 雖然第5圖戶斤示之2DPEP車列單元原本係用以執行全 ^计，然只要在饋入2DPE陣列單元前準備好所有之子查f 貧料，2D PE陣列單元> 旦素 或四分之W: 素移動估計，例如半點 :資：:：：計。然而，這種方法額外需要將整體之書 晝_!資料，轉換過程以及需要暫存由轉換料 ，轉換程序結束時才開始半點移動估計。而且，P= 算=外加緩衝器中進行記憶體讀寫操作之次數將增加整體計 所有子第1圖之2DPE陣列單元可不需要儲存 ”4之5己丨思體區塊而用以執行半點移動估計，並可 25 ,1283132

三達編號：TW1480PA 由本毛月第1圖之2DPE陣列單元配置存在之平行性及導線配 置特性得到最佳之效益。 為了由第1圖中2D PE陣列單元配置存在之平行性及導線 配，特性得到最佳之效益，提供半點值產生單元，而扣冲陣 J單元係用以利用半點值產生單元執行半點移動估計。 執行半點移動估計之2D PE陣列單元配置

明 > 考第12圖，其綠示依照本發明第四實施例利用第j 圖之2D PE陣列單元執行半點移動估計之結構配置圖。當於第 一階=順利找到全點移動估計之最佳點時，在第二階段，可根 據此最佳點，由半點移動估計之「半點」準確度再找出全點移 動估計之最佳點。根據本發明之第四實施例，當對搜尋區域中 對應全點之晝素資料進行掃描時，起始點為全點最佳點之目前 區塊，設為（：（0,0)，係與全點最佳點以及平行之八個相鄰半點 檢查點有關之九個參考區塊相比較。前一個晝面之搜尋區域 R(iJ)(卜1〜16,卜1〜16)在寬度及長度上比目前區塊大二個晝 素，且目前區塊係定義為（:㈦幻^吲〜丨5,尸‘丨5)。當由點r㈠，〇 到點R(16，16)依序-行—行地讀取搜尋區域之全點移動估計之 晝素貧料’或稱為全點值DR(i，j)時，平行產生之好幾組四半點 值係一組一組地饋入至第12圖之2D pD陣列單元。當各組四 個半點值饋入至第12圖之2D PE陣列單元時，pE平行地計算 其對應之誤差計量。當搜尋區域之掃描完成時，決定出九個誤 差计量並獲得具半點準確度之移動向量。

在弟12圖中，輸入資料a饋入至peo、pE]、PE6及PE8 之第一輸入端。輸入資料B饋入至PE1、pE7之第一輸入端。 輪入資料C係、饋人至PE3、PE5之第—輸人端。而輸人資料D 26 ,1283132

三達編號：TW1480PA '係饋人至PE4之第—輸人端。A、B、C及D分別代表對應標干 字母A、B、C及D鑽石圖案之晝素值。由第1〇圖可知厂：晝 素 R(-0.5, -0.5)、R(〇，_〇.5)、rg〇 5,〇)及 R(〇 〇)之畫素資料 A、、 C及D可由整數晝素叫，」）、柳，])、及R(^)之晝 素資料a、b、c及d推導而得。 旦 半點值（Half-pel Value)之產生 為了在碩取全點值時提供一組四個半點值，第i2圖所示 • 之第四實施例中2D PE陣列單元使用具有二個額外電路之半點 值產生單元（Half-pel Value Generation Unit)。半點值產生單元 包括準備延遲單元（preparatl〇n Delay Unit)以及半點產生單元 (Half-pel Generation Circuit)。請參考第11A圖，準備延遲單元 2200於一特定時間（周期）後平行地提供四個全點值a、b、c、d。 在第11A圖中，10個正反器砰22〇1至卯2219係相互串聯並 由及邏輯閘2250輸出之控制信號加以控制。由搜尋區域產生之 全點值係送至輸入端RefJ[n。經過一段準備時間後，即所謂預 ，備（Prefetch)周期，19個正反器皆饋入資料，四個全點值&、b、 c、d可同步輸出。請參考第UB圖，半點產生電路23⑻用以 透過底下之邏輯運算式將晝素資料a、b、d對應地轉換為晝 素資料A、B、C、D。 A — (a+ b + c + d + 2-rounding) >> 2， B -（b + d + 1-rounding) >> 1, C 二（c + d + 1-rounding) >> 1， • D = d， 其中A，B，C，D為半點值，且a，b，c，d為全點值。 27 .1283132 三達編號：TW1480PA : 搜尋區域以及檢查點 士在半1移動估計中，搜尋區域之定義係不同於全點移動估 〇十。搜寻區域=x—range.y—，、range = + STEP—S膨㈣’ y_mnge = 16 + STEp sizEx2=i8 STEP—SIZE=1。特別是半點搜尋之檢查點係定義於全點搜尋中 找到之最佳點R(M)附近。請參考第1G圖，所有圓圈為全點而 具有斜線之圓圈代表全點最佳點。另外，九個鑽石圖案代表九 個檢查點。藉由找尋R(0,0)與其它八個相鄰點叫_〇5, 4 φ R(〇"〇-5^R^5^5)'R(-〇.5,0)R(〇.5,〇).R(.〇.55〇.5)^ 及RMo.s)之最佳吻合度來找出準確之半點移動向量。九個檢 查點係對應於分別具有起始點為R(_〇 5, _〇·5)、r(〇，_〇 5) R(〇.5,-0.5) > R(-〇.5,〇) > R(〇,〇) > R(〇.5} 〇) . R(.〇.55〇 5) , R(〇?〇 5) 及R(0.5,0.5)之九個區塊。在水平及垂直方向相鄰兩點之步幅為 1:: 16x16半點組成之每一個區塊可以附近之全點由内插方式 獲得。搜尋區域之全點值DR(i，j)係用以產生搜尋區域之半點值 DR(i+0.5，j+0.5)，其巾卜_卜16，且卜卜16。而全點移動估計 之步幅為1。 半點移動估計操作 半點移動估計之操作如下： 百先，如第12圖所示，2D PE陣列單元係用以執行半點 移動估计，而VDU及HDIJ係設定具有特定之延遲時間。 接著，開始預備周期以產生第一組四個半點值。在預備周 期中’對應搜尋區域中晝素DR㈠，…到DR(16，16)之全點值 Ref—Data係以依序方式讀取並饋入至半點值產生單元。於此實 施例中，搜尋區域之一全點值饋入至準備延遲單元2200之輸入 28 1283132

三達編號：TW1480PA 端fef_In。當來自搜尋區域之第2〇個全點值抓⑼⑴輸入至延 遲單7L 2200 4，全點值a、b、e、d可同時輸出並送至半點產 生電路2300。四個半點值A、B、C、D同時由半點產生電路 23 00產生並饋入至第12圖之2D PE陣列單元。

c、D 再者，第12圖之2D PE陣列單元係於各組半點值a、b、 > 一組一組地饋入至第12圖之2DpE陣列單元時累計誤差 計量。當第一組半點值饋入時，第12圖之2DpE陣列單元先執 ㈣應檢查點叫…^卜叫^及柳⑴之誤差計量。 當-行-行地依序讀取搜尋區域之全點值DR(iJ)時，九個檢查 點 R(-0.5, -0.5)、R(0，-0.5)、R(〇.5，_〇 5)、R(_〇 5,〇)、r(〇,〇) r(〇、 0)、R(-G.5，G.5)、R(M，5)及Rdns)之誤差計量可以累計方式 計算。致能信號輸入至第12圖之2Dp_列單元以致能對應之 PE並處理饋入pe之資料。當搜尋區域完成掃描時，可決定出 =块差計量。因此，可決定具有最小誤差計量之檢查點，以 各又传具半點準確度之移動向量。 一為了達到上述之目的，必須根據第12圖中2DpE陣列單

兀所執打半點移動估計設定晝素掃描順序、延遲單元並控制pE 陣列。 半點移動估計之晝素掃描順序（pixel Sean⑽打） *半點移動估計中搜尋區域之晝素掃描順序類似於本發明 弟四實施例中第7圖所示之全點移動估計。搜尋區域之參考資 ^係由起始點料-D至結束點 ^^喂·1，·1…^·1)哪6，16)-行—行地依序讀取。 其中 X—range二18，且 y—range = 18。 同樣地’目則區塊之晝素值係由起始點C(0,0)至結束點 29 ·· 1283132

* 三達編號：TW1480PA :C(=，15)—行—行地依序讀取。然而，上述之預備周期係位於 目可區塊掃描開始之前’第—組四個半點值，即第ig圖所示之 A B、C、D係於預備周期之後提供。在預備周期中，全點值 DR(-1，-1)到DR(-l，〇)’全部19個全點值係由左至右一行一行地 =序績入至準備延遲單元·。當卿（或pEi)被致能時，即 當送至PEO控制端PEOen之致能信號pE〇一Εη_為致能狀態 時^前區塊叫0,0)到（15，15)之畫素值係以上述目前區域之晝 t掃描順序來讀取。在—個實施例，# pEG(或ρΕι)為致能狀態 i日守，在讀取參考資料之前立即先讀取一筆目前資料。 第12囷中PE决疋對應弟1 〇圖半點移動估計檢查點之 二差。十i例如疋本只知例之SAD。例如，PEO係用以使用sad 對目前區塊與對應檢查點R(_〇.5,_〇5)之參考區塊作比較，其中 檢查點係第ίο圖中鑽石圖案代表之左上半點。此外，pEi〜pE8 係用以使用SAD對目前區塊與分別對應檢查點R(〇，-〇 5)、 R(〇-5,-0.5) ^ R(-〇.5,0) > R(〇, 〇) . R(〇.5j〇) . R(_〇.55〇 5) . R(〇?〇 5) 及R(0.5,0·5)之參考區塊作比較。 > 為了使第12圖中每一個PE皆可正確地決定對應檢查點之 誤差計量，即SAD。來自半點產生電路23〇〇之半點值A、B、 C、D以及目前資料需要正確地，例如是同步地送至陣列。 例如’虽半點值DR(_〇 5，_〇 5)即第1〇圖之A與全點值DC(〇,〇)， 即第10圖之d同步送至第一輸入端ΑΟα及第二輸入端別時， ΡΕ0可準確地計算絕對差值。同樣地’當半點值dr(〇，_〇 5)、 ' DR(-5,0)以及DR(0,0)，即第10圖之b、c&d係與輸入PE1、

PE3及PE4第二輸入端之全點值DC(〇,〇)同步分別饋入至pE1、 PE3及PE4之第一輸入端時，pE1、托3以及冲4可正確地決 定個別之絕對差值。因此，每次提供之半點值A、B、c及D 30 :1283132

• 三達編號：TW1480PA :與全點值DC(i，j)同步饋入至PE0、PE1、PE3、PE4,使得pE〇、 pEl、PE3、PE4可對應地決定誤差計量。 、，"就PEO來說，PE0係於讀取一列目前區塊之最後一個晝素 並送至第二輸入端B0之後被非致能。此時，搜尋區域之掃描動 作仍持續進行中。另外，目前區塊之掃描動作暫停直到掃描到 下一列搜尋區域之第一個畫素。當掃描下一列搜尋區域之第一 個晝素時，PEO再次致能並繼續掃描目前區塊。因此，下一列 目前區塊之半點值以及下一列搜尋區域之半點值可以正確地， » $如是同步地送至PEG。以上述方式來掃描目前區塊可使得其 匕PE可以對應地接收到正確的晝素值以決定誤差計量。藉由延 遲單元陣列，其它之PE可以正確地輸出晝素值。 用作半點移動估計之延遲單元 利用對搜尋區域以及目前區塊之晝素掃描順序，延遲單元 必須具有個別之延遲時間，以便重覆使用目前之資料，即來自 目前區塊之全點值。如上所述，某一時間提供之半點值a、b、 ^ C、D例如是與全點值DC(iJ)同步地饋入pE〇、pEi、pE3及pE4 中，使得PE〇、PE1、PE3及PE4可以對應地決定誤差計量。因 此，在本實施例中，HDU140、16〇以及15〇係設定為沒有延遲 時間。而其它之PE設定則視下述目前資料之再使用狀況而定。 請參照第10圖以及第12圖，當PE〇被致能時，讀取全點 ' 值DC(0,0)並饋入至陣列單元。在此實施例中，於全點值DC(〇,〇) ' 以及第一組四個半點值，即A、B、C及D產生並分別饋入至 .=0、ΡΕ1、ΡΕ3及PE4之後’立即讀取全點值抓(〇,〇)。由於 第組四個半點值並不包含於對應ρε檢查點之區塊中，因此 ΡΕ2、ΡΕ5、ΡΕ6、ΡΕ7及ΡΕ8等其它ρΕ係為非致能狀態。然而， 31 .1283132

• 三達編號：TW1480PA : 當PE2、PE5、PE6、PE7及PE8被致能時，必須重覆使用全點 值DC(0,0)。如第10圖所示，當全點值DC(1，0)被讀取時，在 下一個周期中產生包括DR(0.5，-0.5)及DR(0.5,0)之下一組四個 半點值。如第12圖所示，當產生半點值DR(0.5，-0.5)及DR(0.5,0) 時，PE2及PE5被致能且此兩個半點值係饋入至第一輸入端A2 及A5,而前一個周期讀取之全點值DC(0,0)係由HDU 142及162 輸出至第二輸入端B2及B5。因此，假設當ΡΕ0為致能狀態於 每一個周期讀取目前區塊之一全點值時，HDU 142及162係各 φ 具有一個時間單元（周期）之延遲時間。 請參照第10圖，當讀取全點值DC(0，1)時，在接下來周期 中產生包括DR(-0.5,0.5)及DR(0.5,0)之一組四個半點值。如第 12圖所示，當產生半點值DR(-0.5,0.5)及DR(0.5,0)時，PE6及 PE7被致能且此兩個半點值係饋入至第一輸入端A6及A7，而 前一個周期讀取之全點值DC(0,0)係分別由VDU 170及HDU 180輸出至第二輸入端B6及B7。因此，VDU 170係設定為具 有16個時間單元之延遲時間，且HDU 180係設定為延遲時間 為0。因此，當讀取全點值DC(0，1)時，在下一個周期中產生包 ® 括DR(0.5,0.5)之下一組四個半點值。再如第12圖所示，當產 生半點值DR(0.5,0.5)時，PE8被致能且此半點值係饋入至第一 輸入端A8，而在上一個周期由HDU 180讀取之全點值DC(0,0) 係輸出至第二輸入端B8。因此，HDU 180係設定為具有一個時 間單位之延遲時間。 用作半點移動估計之PE陣列控制 與上述之討論相似，根據本發明之第四實施例，第12圖 所示之九個PE具有四個PE致能周期，用以使PE陣列單元正 32 .1283132

* 三達編號：TW1480PA : 常操作。特別是這些致能周期彼此互相重疊使得某些PE功能在 掃描參考資料過程之某些時刻係相互平行。PEO、PEI、PE3及 PE4之致能周期PEO_enable_cycle係相等。PE2及PE5之致能 周期PE2_enable_cycle係為相同。PE6及PE7也具有相同之致 能周期 PE6_enable_cycle。PE8 具有個別之致能周期 PE8_enable_cycle。這些PE致能周期可藉由將搜尋區域劃分為 如目前區塊一般具有相同大小之子區域子集來直觀地加以定 義。請參照第13A圖及第13B圖，對應起始點R(0,0)、R(l，〇)、 φ R(〇，l)及R(l，l)之四個子區域1301〜1304係分別用以定義對應 PEO、PE2、PE6及PE8之四個致能周期。 藉由致能周期之定義，可更方便控制PE陣列並降低操作 之複雜度。例如，PE致能邏輯電路可用以決定當讀取全點值 DR(i，j)時那一個子區域包括晝素R(i，j)。對每一個決定為具有晝 素R(i，j)之子區域而言，係致能其中對應之一致能信號並送至對 應子區域（或致能周期）之控制PE陣列之PE控制端。 例如，當讀取DR(1，0)時，PE致能邏輯電路判定 PEO—enable—cycle 及 PE2—enable—cycle (兩個子區域）具有晝素 瞻 — — < R(1，0)。對判定為具有晝素R(1，0)之兩個子區域而言， PE0_Enable、PElJEnable、PE3_Enable、PE4_Enable 及 PE2_Enable等致能信號被致能並送至對應之控制端，即對應致 能周期 PEO—enable—cycle 及 PE2—enable—cycle 中 PE 之 PEOen、 PElen、PE3en、PE4en、PE2en 及 PE5en 〇 、 與執行半點移動估計之第四實施例相同，表二列出如第12 - 圖所示之九個PE之致能狀態。搜尋區域之起始點定義為 (-1，-1)。表二顯示當對應搜尋區域中全點值R(X，Y)之晝素值 DR(X，Y)位於子區域中時致能信號PEZ_Enable (Z=0〜8)被致能 33 .1283132

_ 三達編號：TW1480PA ： 之狀態。另外，在第二實施例中，致能信號係分別饋入至 PEO〜PE8之控制端PEZen(Z=0〜8)。 表二 致能狀態 致能周期 半點 PEOEnable X=0 〜15，Y=0 〜15 PEOenablecycle PElEnable Χ=0 〜15, Υ=0 〜15 PEOenablecycle PE2_Enable Χ=1 〜16，Υ=0 〜15 PE2_enable_cycle PE3_Enable Χ=0 〜15, Υ=0 〜15 PEOenablecycle PE4_Enable Χ=0 〜15，Υ=0 〜15 PEOenablecycle PE5_Enable Χ=1 〜16，Υ=0 〜15 PE2_enable_cycle PE6_Enable Χ=0 〜15，Υ=1 〜16 PE6_enable_cycle PE7_Enable Χ=0 〜15，Υ=卜 16 PE6_enabIe_cycle PE8—Enable Χ=1 〜16，Υ=1 〜16 PE8_enable_cycle

註：搜哥區域之起始點定義為(-1，-1)。 執行全點及半點移動估計之移動估計系統架構 請參照第14圖，其繪示依照本發明第五實施例之移動估 計系統結構圖。移動估計系統2000包括移動估計單元2100、 記憶體讀取單元1500、控制單元1600以及位址產生單元1700。 第14圖所繪示之系統係可於第一階段中利用步搜尋演算法，例 如是FSS演算法來執行全點移動估計，並於第二階段中可選擇 性地根據全點移動估計找出之最佳點執行半點移動估計以獲得 具半點準確度之移動向量。移動估計系統2000更可以如同第九 圖顯示之系統1〇〇〇，用以執行任意之N步搜尋演算法，例如三 步搜尋演算法，以進行全點移動估計。然而，值得注意的是， 34 1283132

二達編號·· TW1480PA :=Γ=Γ°係可選擇性地執行半點移動估計，以使得由 I下列敘寻之移動向量具有半點準確度。為了簡潔起 字不再重復關於第一階段中全點移動估叶 =關於移動估計系統2_所執行之全點移動估計= 考述王點移動估計之描述及圖式。 移動估計單元2⑽包括2DPE陣列單元1〇〇 哭 ::、暫存器單元譲以及最小SAD判斷單元ιΐ7〇 了 ΓΕ=單Λ2100包括半點值產生單元，用以輸出平行於- 單元㈣ 之—組半點值。半點值產生單元包括準備延遲 (P__ Delay Unit)2以及半點產生電路（Η e_lonCircuit)23〇〇,如第UA圖以及第仙圖所干。 取介取單元1500係為移動估計系統2_之記憶體讀 讀取介面可利用連接移動估計系統雇之 L體匯排10所使用之至少-種通訊協定來執行。 可以^ 1帽儲㈣步料進行魏。㈣單元1 _ ^ ί有限狀恝機斋，例如是包括X計數器與γ計數 =:二電路二：數!計算一列搜尋區域中所讀取之晝；值 。汁數器計算搜尋區域中讀取晝素值之晝素搁數。^ 取：應搜尋區域晝素之一筆Ref_Data資料時 ；： 而當X計數器計數值達到—預設值χ—maxi=數 u ==1°然後’x計數 —range時，結束此步搜尋演算法。由於 夕 汁糸統2000係分別於不同二階段來執行全點移動仕+ =移動估計’…計數器於全點移動估計及： 估计品達到不同之預設值。 動 在執行全點移動估計之第—階段中，x—max_e。喊係為搜 35 1283132

三達編號：TW1480PA 尋區域之寬度（晝素數目），即X-max+count^ x_range。在全點 移動估計之第一步至第 （n-1) 步 中 ， X_max_count=x_range二macroblock__size+STEP_SIZE><2。{列 士口 ， 在FSS演算法中，X—max_count=16 + 2x2=20，其中除了最後一 步之外，其它步之步幅STEP_SIZE=2。而全點移動估計或半點 估計之最後一步中，X__max_count= x_range，而 STEP_SIZE 值 可以是較小值。在半點估計中，X_max_count=l6+1 χ2=1 8，其 中STEP_SIZE二1。記憶體讀取單元1500產生記憶體讀取信號 _ Ref_ready並送至控制單元1600。記憶體讀取信號是用以通知X 及Y計數器更新其計數值。例如，當對應一筆搜尋區域之一筆 Ref_Data資料由例如是參考記憶體讀取時，Refjready設定為致 能狀態，例如是高準位。PE致能周期係根據X以及Y計數器 提供之目前計數值X及Y以及表一所示全點移動估計之致能狀 態與表二所示半點移動估計之致能狀態來決定。 位址產生單元1700包括PE致能邏輯電路1750以及移動 向量（MV)產生邏輯電路1770。PE致能邏輯電路1750由計數器 單元1600之X及Y計數器接收目前計數值X及Y，再根據目 前計數值X及Y以及表一之全點移動估計或表二之半點移動估 計產生致能信號，然後將致能信號輸出至移動估計單元2100之 2D PE陣列單元100。如上所述，掃描搜尋區域之後，可獲得九 個誤差計量，例如是第二實施例中對應九個檢查點之九個 SAD。而最小SAD判斷單元1170可判定最小誤差計量並加以 輸出。位址產生單元1700接收由最小SAD判斷單元1170輸出 之最小誤差計量。在第一階段中，MV產生邏輯電路1770產生 搜尋演算法最後一步之移動向量。當第二階段欲執行半點移動 估計時，於第一階段獲得之移動向量即可用作決定是否具有半 36 ,1283132

二達編號：TW1480PA ： 點準確度之根據 。此夕卜，位址產生單一 提供給記憶體讀取單元產生記憶體位址並 讀取目前資料❿可由記憶體讀取單元1500 月J貝枓亚饋入至移動估計單元11〇〇。 半點移動估計過程之移動估計系統操作 估叶^Γ ΓπΓ統2咖係心執行半點移動估計。假設移動 入。十係以時脈錢CLK進行操作，並於第—階 王點移動估計中找到一最佳 、 又 配晉士笛,。 百先，2D PE陣列單元100係 月期以^ ’用以進行半點移動估計。接著，開始預備 =自，區域起始點R(七

；200 1 θ 7 ? 21〇〇 PE陣^電路2330得以輸出一組四個半點值至扣 陣歹i早凡1 〇 〇。接著，絲炸D F 所、十、4 4 口口- b 〇—enable 並讀取 DR(0,0) 〇 如 、rr: J早凡1600之又及¥計數器開始計數，且PE致能 邏輯電路1750根據表二產生致 致月匕 出至㈣列翠元⑽。當以搜尋le(z=0〜8)並輪 次之王，.'，占值亚饋入至移動估計單元2100時，

Cun·—Data資料也以目前區塊之蚩 鬼之 「丰點篇翻& # + I 旦素知^田順序，例如是上述之 +點移動料4讀描料」來讀取並饋人 2100JD ΡΕ陣列單开1ΠΠ + — y 石4早兀 _PEZ Μ卓 £判斷是否要根據致能信 號ΡΕΖ—enaMe處理目前周期中饋入ρΕ之資料，並於ρΕ =1=準確地計算出誤差計量。當搜尋區域婦描完成且 對應之晝素貧料完全饋入扣冲陣列單元時，搜尋區域九個來 考區塊（對應特定檢查點）與目前區塊之比較係以平行方式進 打，以產生對應之誤差計量，亦即第1〇圖實施 查點之⑽。也就是說，在掃描搜尋區域中，可由= 37 β 1283132

* 三達編號：TW1480PA ： 單元100進行半點移動估計。因此，可根據最小SAD判斷單元 1170所獲得之誤差計量決定具有最小誤差計量之一個全點檢查 點，並據以決定出具半點準確度之移動向量。所以，透過2D PE 陣列單元1〇〇,移動估計系統1〇〇〇可執行移動估計之任何N步 搜尋演算法。 特別是在2D PE陣列單元100之配置上，2D PE陣列單元 100之HDU以及VDU之配置如上述之「半點移動估計延遲單 元」。 φ 在全點移動估計中，係一行一行依序地讀取搜尋區域之

Ref_Data資料。在此實施例中，當信號PEO—Enalbe為致能狀態 時，在讀取對應搜尋區域晝素之一筆參考資料之前會先讀取對 應目前區塊之一筆目前資料。 在一個實施例中，可於2D PE陣列單元100之HDU以及 VDU中使用閘極時脈技術（gated clock technique)來控制移位暫 存器以達到有效降低功率耗損之目的。在半點移動估計中，由 記憶體讀取單元1500產生之記憶體讀取信號Ref_ready用以控 制2D PE陣列單元100之延遲單元陣列。例如，在半點移動估 ® 計中，HDU致能信號HEN—CS係設定為吻合PEl_Enable時序 之一邏輯狀態：HEN_CS = Ref__ready & (X_count > 0) & (Y_count > 0)。 VDU致能信號係設定為一邏輯狀態：VEN_CS=HEN_CS & (X_count<17)。準備延遲單元2200之致能信號SEN_CS係設定 為SEN—CS=Ref_ready。當由參考記憶體讀取搜尋區域晝素之 - Ref_Data資料時，Ref_ready係設定為高準位狀態。如第3圖所 • 示，HDU致能信號係饋入HDU之HEN端，而VDU致能信號 則如第4圖所示饋入至VDU之VEN端。準備延遲單元2200之 致能信號SEN_CS係饋入至其SEN端，如第11A圖所示。而所 38 .1283132

二達編號：TW1480PA 、 有延遲單元之CLK端係饋入時脈信號CLK。 半點移動估計之效能 p使用如上述之全點移動估計「效能」之假設。如上述 知例半點移動估計需要讀取（ΐ6+ΐχ2)χ(ΐ6+卜2)巧灸去 ^料以及讀取16X16=256塊目前資料。因此，在此假設^考 河區塊之半點移動估計需要324+256/4=388周期才能^成。目 優點 —在本發明之第四及第五實施例中，揭露了執行半點移動估 权犯PE陣列早凡配置以及執行全點及半點移動估計之移 估:十系、、A *構。根據此些實施例，具有準備延遲單元及半點產 生電路之半點值產生單元係搭配2d pE陣列單元之配置來執行 半站移動估计。2D PE陣列單元如第丨圖所示，可選擇 行全點以及半點移動估計。 ㈣乂執 、，/根據本發明，可由第丨圖所示2D pE陣列單元配置存在之 平仃|±及導線酉己置特性得㈣最佳之效益。纟掃描搜尋區域過程 :，不論是半點或全點搜尋，2D pE陣列單元可以平行方式比 區塊與搜尋區域之_組參考區塊。當完成搜尋區域之掃 描時，完成半點搜尋之步搜尋動作。 搜尋區域以及區塊之晝素掃描順序係具有規則性及簡化 使彳于控制邏輯及致能信號可以在不使用複雜硬體之情況下 來#作° 2D PE陣列之電路設計係可擴充性並具有彈性。除了 半點移動估計之外，2D PE陣列單元也可以適用於任何其它之 子晝素移動估計，例如是四分之一點移動估計或八分之一點移 動估計等。 39 ,1283132

二·達編號：TW1480PA - 综上所述，雖然本發明已以一較佳實施例揭露如上，缺豆 並非用以限定本發明，任何熟習此技藝者，在不脫離本發明之 精神和範圍内，當可作各種之更動與潤飾，因此本發明之保護 範圍當視後附之申請專利範圍所界定者為準。

40 .1283132

• 三達編號：TW1480PA : 【圖式簡單說明] 第1圖繪示根據本發明第一實施例用於移動估計之2DPE 陣列單元結構圖。 第2圖繪示在第一輸入端a與第二輸入端β之資料間進 行SAD之PE結構圖。 第3圖繪示根據本發明一實施例2D PE陣列中水平延遲單 元（HDU)之結構方塊圖。

第4圖繪示根據本發明一實施例2D PE陣列中垂直延遲沖 元（VDU)之結構方塊圖。 早 第5圖繪示依照本發明第二實施例執行全點移動估 2D PE陣列單元配置圖。 D| 一個晝面（參考晝面） 第6A圖繪示目前晝面之區塊以及前 之搜尋區域。 步之九 ㈣圖㈣執行全料動料日細步搜尋中每 晝素掃描順 第7圖繪示依照本發明第二實施例搜尋區域之 序示意圖。 實施例對應搜尋區域之子區域 第9圖繪示依照本發明第 貝她例移動估計系統之結構方 第8圖纟會示根據本發明第 之PE致能周期。 塊圖 第丨〇_示於全點搜尋中找狀最佳 作示意圖。 Μ订平點搜哥動 第11Α圖繪示用以平杆 結構圖。 "日王點值之準備延遲單元 第11B圖繪示用以將四 王』值轉換成四個半點值之半 41 ^83132 :編號：TW1480PA 點產生電路結構圖。

第^圖緣示依照本發明第四實施例利用第i圖之2D pE 早元執行半點移動估計之結構配置圖。 第13A圖與第圖繪示枢摅 尋區伙根據本备明弟四實施例對應搜 或之子區域之PE致能周期示意圖。 第14圖緣示根據本發明第五實施例使用犯 執仃全點及半點移動估計之移動估計系統結構方塊圖。 【主要元件符號說明】 10 :記憶體匯流排 100 140 150 110 112 114 120 122 124 130 132 134 200 210 250 142 170 ΡΕ0 PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 PE 絕對差值元件 累計器 320 :正反器 300 水平延遲單元 維處理元件陣列單元 160 、 162 、 180 、 182 400 :垂直延遲單元 42 310 .1283132

^ 三達編號：TW1480PA ： 350、450 :多工器 360、2250 :及邏輯閘 401〜416、421〜436 ··正反器 460 :邏輯閘 610 :搜尋區域 650 :區塊 810 : ΡΕ0致能周期 818 : PE8致能周期 1000、2000 :移動估計系統 1100、2100 ··移動估計單元 1150 :多工器 1160 :暫存器單元 1170 :最小SAD判斷單元 1301〜1304 :子區域 1500 :記憶體讀取單元 1600 :控制單元 1700 ··位址產生單元 1750 : PE致能邏輯電路 1770 : MV產生邏輯電路 2200 :準備延遲單元 2201〜2219 :正反器 2300 :半點產生電路 43

Claims (1)

1. ..1283132 二達編號：TW1480PA ： 十、申請專利範圍： • 種移動估計裝置，用於影像處理，包含： 禝數處理元件，每一處理元件具有一第一輸入端，一第二輸 入端，一控制端及一誤差計量輸出端，該些處理元件所對應之 該些第一輸入端接收一參考資料； 複數延遲單元，針對一晝素資#，產生具有特定延遲時間之 複數資料流送至該些處理元件之該些第二輸人端；以及 控制電路’提供複數控制信號至該些處理元件之該些控制 端該些處理元件收到該些控制信號時，計算該第一輸入端 與該第二輸入端之一誤差計量。 2.如申請專利範圍第i項之移動估計裝置，其中該晝素資料係 針對一目前晝面以特定掃描方式依序選出。 利耽圍第1項之移動估計裝置，其中該參考資料係 針對-搜尋區域以特定掃描方式依序選出。 4 ·如申请專利範圍第1須 ,..^員之移動估計裝置，更包含一半點值產 早兀，使该參考資料為半點資料值。 5·如申請專利範圍第丨項之 ^ ^ ^ ^ 係排列成二維陣列，而該此延:::十裝置二其中峨理元件 與複數垂纽料元，4、=^則包含複數水平延遲單元 元件之該些第二輸入端。…夺間輸入所需資料至該些處理 44 1283132 三達編號：TW1480PA 7·如申請專利範圍第6項所述之移動估計裝置，其中定 義有一區塊包括PxQ個晝素並具有一起始點C(0,0)，一搜尋區 域包括LxJ個晝素，並具有一起始點r(〇,〇)，l = 2XSTEP—SIZE+P，J = 2xSTEP_SIZE+Q，且該移動估計裝置更 包括： 一記憶體讀取單元，用以自該起始點R(〇,〇)至R(L-1，J-1) 一行一行依序地讀取與該搜尋區域中一晝素R(i，j)對應之參考 > 資料DR(i，j)，並自該起始點c(0,0)至C(P-1，Q-1)—行一行依序 地輸出與該區塊中一晝素C(p，q)對應之晝素資料DC(p，q); 其中由該記憶體讀取單元讀取之該些晝素資料DC(p，q)係 送至該第一列中該水平延遲單元之該輸入端，且由該記憶體讀 取單元讀取之該參考資料DR(i，j)係送至該處理元件陣列中每一 處理元件之該第一輸入端。 8.如申請專利範圍第7項所述之移動估計裝置，其中該 搜尋區域係晝分為具有PxQ個晝素之複數個子區域分別對應至 I 檢查點（〇,〇) 、 （STEP_SIZE，0) 、 （2xSTEP—SIZE，0)、 (0，STEP_SIZE) 、 （STEP—SIZE， STEP—SIZE) 、 (2xSTEP_SIZE，STEP—SIZE) 、 （0,2x STEP—SIZE) 、 (STEP_SIZE，2xSTEP_SIZE)以及(2x STEP_SIZE， 2x STEP—SIZE)，各該些檢查點係定義為各該些子區域才目對應之一 起始點； 各該些水平延遲單元具有STEP_SIZE個時間單位之延遲 時間； 各該些垂直延遲單元具有STEP_SIZExP個時間單位之延 46 .1283132 - 三達編號：TW1480PA ' STEP_SIZE，且 j < (L + STEP_SIZE)，根據經過對應 (2+P)xSTEP—SIZE之一延遲時間之該些晝素資料DC(x5，y5)以 及該些參考資料R(i，j)，累計對應該檢查點（2xSTEP_SIZE， STEP_SIZE)之一誤差計量，其中 x5 = i -2xSTEP—SIZE，且 y5 = j-PxSTEP_SIZE ； 若 i < P，仫 2xSTEP_SIZE，且 j < (L + 2x STEP—SIZE)， 根據經過對應2xPxSTEP_SIZE之一延遲時間之該些晝素資料 DC(x6，y6)以及該些參考資料R(i，j)，累計對應該檢查點（0, φ 2xSTEP—SIZE)之一誤差計量，其中 x6 = i ， 且 y6=j -2xPxSTEP_SIZE ; 若 i > STEP—SIZE，i < (L + STEP_SIZE)，j> 2xSTEP_SIZE，且 j < (L + 2><STEP_SIZE)，根據經過對應 (1+2xP)xSTEP—SIZE之一延遲時間之該些晝素資料DC(x7，y7) 以及該些參考資料R(i，j)，累計對應該檢查點（STEP_SIZE， 2xSTEP_SIZE)之一誤差計量，其中 x7 = i - STEP—SIZE，且 y7 叶2xPxSTEP_SIZE ;以及 若 i > 2xSTEP—SIZE，i < (L + 2xSTEP_SIZE)，j> • 2xSTEP—SIZE，且 j < (L + 2><STEP_SIZE)，根據經過對應 (2+2xP)xSTEP—SIZE之一延遲時間之該些晝素資料DC(x8，y8) 以及該些參考資料R(i，j)，累計對應該檢查點（2xSTEP_SIZE， 2xSTEP_SIZE)之一誤差計量，其中 x8二i-2xSTEP_SIZE，且 y8 二 j-2xPxSTEP_SIZE ; • 其中當完成該步驟（b)時，由該步驟（c)所決定，與該些檢 • 查點（0，0)、 （STEP_SIZE，0)、(2xSTEP_SIZE? 0)、（0, STEP_SIZE)、 （STEP_SIZE, STEP SIZE)、(2xSTEP_SIZE, STEP_SIZE)、 （0, 2xSTEP_SIZE)、（STEP SIZE，2xSTEP_SIZE) 49 I283132 二達編號：TW1480PA 以及（2xSTEP—SIZE，2xSTEP—SIZE)對應之嗲 、， 以完成。 ^二铁差計量亦得 10·如申請專利範圍第9項所述之全點移動估計方去其 中可根據對應該些檢查點之該些誤差計量、、扣宁m h ' 里央疋四步搜尋演算法 中一搜尋步之一最小區塊變形計量（ΒΕ>Μ)點， )點且四步搜尋演算 法之第一步、第二步、第三步以及第四步步 八 別“ 。η， 八八 STEP—SIZE 分 別為2、2、2及1。 如甲請專利範圍第9項所述之全點移動估計方法，豆 中可根據對應該些檢查點之該些誤差計量決定^丨演算^ 二—搜尋步之一最小區塊變形計量（BDM)點，且3_m 二 算法之第一步、第二步、第三步以及第四步之步幅ste?= 分別為3、3、3及1。 一 12.如申請專利範圍第9項所述之全點移動估計方法，直 • _可根據對應該些檢查點之該些誤差計量決定三步搜尋演算^ 令-搜尋步之-最小區塊變形計量⑽M)點，且三步搜尋演曾 :之第-步、第二步以及第三步之步幅瞻―咖分別為二 13.—種全點移動估計之方法，包括： 個畫素並具有一起始點 LxJ個晝素並具有—起始 ⑷定義一區塊，包括ΜχΝ ΜΒ(〇,〇)ϋ定義一搜尋區域，包括 點 SA(0,〇)，其中 L>p，且 J>Q ; (b)定義該搜尋區域包括對應複數個檢查點之複數個具有 50 1283132 三達編號：TW1480PA MxN 個書去 > r- '、 _ 區域，各该些檢查點係定義為各該些子區域對 應之一起始點； 一 (C)自该起始點SA(0,0)至該起始點SA(L-1，J-1) 一行一行依 ^地輸出對應該搜尋區域晝素之畫素資料，並自該起始點 該起始點應⑷則―行—行依序地輪出對應該 口口尾旦常之晝素資料； 抑步驟⑷在執行時’對於由該步驟⑷所輸出並對應 二：對庫：^素之晝素資料’送至一延遲單元陣列，用以輸出 二^應起檢查點之複數串輸出資料流，其中對於該些檢杳 點其中之_，一一 w ( ^ ’该延遲單元陣列係輸出對應之一輸出資 料流’且:輪出資料流係延遲(即M)個時間單位之晝素資料： ^⑷當該步驟⑷在執行時，根據該步驟⑷所讀取且與該搜 寸區域之:晝素SA(p，q)相對應之該晝素資料，執行下列步驟： 判斷所有子區域中包括SA(P，q)之子區域；以及 對於各個包括SA(p，q)之子區域，累計該子區域對應之 该檢查點C(f，s)所制 A ,胃 斤+應之决差計S，該誤差計量係根據來自與 =一1参c(f，g)相關之輸出f料流之晝素f料以及對應該搜尋 二二^ (p,q)之該些晝素f料而得，其中來自與該檢查點 (，g)目|之輸出資料流係對應至該區塊之—晝素MB(r，s)， p=r+f JL q^s+g ; ’、中田騎驟⑷完成時，該步驟⑷巾與所有之該些檢查 點相對應之該些誤差計量亦得以完成。 -/金丄4. 一種半點移動估計裝置’其中定義-區塊，包括PxQ 固二!*:具有一起始，點c(o,o)，並且定義-搜尋區域，包括 LxJ個旦素並具有—起始點R(〇,〇)，其中卜2+p，剛，該裝 51 .1283132 — 三達編號：TW1480PA \ 其中該記憶體讀取單元所讀取之該些晝素資料DC(p，q)係 送至該第一列中該水平延遲單元之該輸入端，且該記憶體讀取 單元讀取之該些參考資料DR(i，j)係送至該半點值產生單元。

   54