368_088-115CP-TW

:::

368_088-115CP-TW

發佈日期 : 2009-04-29

發明專利說明書
﹝本說明書格式，順序及粗體字，請勿任意更動，※號部份請勿填寫﹞
	※申請案號： 089108467
	※申請日期： 20000502 ※ＩＰＣ分類： Int.Cl.(6) H04N 7/32，3/26

一、發明名稱： (中文/英文)
	一種使用在影像區塊匹配移動估計的模糊搜尋方法 (全文下載) Fuzzy Search Method for Image Block-matching Motion Estimation
二、申請人：共 1 人
	1 . 　姓名或名稱：(中文/英文) 　　行政院國家科學委員會 / NATIONAL SCIENCE COUNCIL 　代　表　人：(中文/英文) 　　 / 　住居所或營業所地址：(中文/英文) 　　臺北市大安區和平東路二段一○六號十八樓 / 　國　　　　籍：(中文/英文) 　　中華民國 / TW
三、發明人：共 2 人
	1 . 　姓名：(中文/英文) 　　周哲民 / JOU, JE-MIN 　國　　　籍：(中文/英文) 　　中華民國 / TW 　 2 . 　姓名：(中文/英文) 　　陳培殷 / CHEN, PEI-YIN 　國　　　籍：(中文/英文) 　　中華民國 / TW
四、聲明事項
	□主張專利法第二十二條第二項 □ 第一款或 □ 第二款規定之事實，其事實發生日期為：年　月　日 □申請前已向下列國家(地區)申請專利: 　【格式請依:受理國家(地區)、申請日、申請案號、順序註記】
	□ 有主張專利法第二十七條第一項國際優先權：　□無主張專利法第二十七條第一項國際優先權：
	□ 主張專利法第二十九條第一項國內優先權：　【格式請依:申請日、申請案號、順序註記】
	□ 主張專利法第三十條生物材料：　□ 須寄存生物材料者：　　　國內生物材料【格式請依:寄存機構、日期、號碼、順序註記】　　　國外生物材料【格式請依:寄存國家、機構、日期、號碼、順序註記】
□ 不須寄存生物材料者: 　　　所屬技術領域中具有通常知識者易於獲得時，不須寄存。

五、中文發明摘要：
	本發明係一個應用於影像區塊匹配移動估計的快速模糊搜尋方法。本方法中，要決定某個參考區塊的移動向量，可分成三個主要步驟：A)應用模糊推理以泱定該參考區塊的預測移動向量，B)決定區塊匹配搜尋範圍之初始中心位置，C)區塊匹配搜尋以決定該參考區塊的最後移動向量。

六、英文發明摘要：


七、指定代表圖：
（一）本案指定代表圖為：
（二）本代表圖之元件符號簡單說明：



八、本案若有化學式時，請揭示最能顯示發明特徵的化學式：


九、發明說明：
	產業上之利用領域　　本發明乃提出一個應用於影像區塊匹配移動估計的快速模糊搜尋方法。背景　　現今之多媒體應用，動輒數百萬位元以上的資料傳輸，以目前之儲存媒介、傳輸技術實無法輕易滿足此要求。因而一個具高效能的壓縮（或編碼）系統愈來愈顯重要。針對動態視訊(video)之編碼，國際標準組織(ISO)提出了如動態影像壓縮(MPEG,Motion Picture Estimation GrouP)和H.263等標準。而為了達到較佳的壓縮效率，在這些標準中，使用區塊匹配移動估計(block-matching motion estimation)的方法來降低視訊信號中畫面間的累贅(inter-frame redundancy)。　　移動估計之成功與否乃決定於其採用的區塊匹配方法是否能正確、快速地估計出影像區塊的移動向量。完全搜尋法是重建影像品質最佳的區塊匹配方法；然而，由於該法需要極大量的數學運算，不易達到即時影像編碼的要求。因此，許多品質稍差，但運算甚快的快速搜尋方法已被提出。本發明提出一個應用模糊推理的高速模糊搜尋方法。由於此方法可正確且快速地決定影像區塊的移動向量，因此，移動估計所產生的重建影像其品質甚佳，且所需的運算時間大量的降低，可達到影像即時編碼的要求。由於在動態影像壓縮(MPEC)或H.263等視訊編碼標準中，讓使用者可依其需要採用任何適當的搜尋方法來實現區塊匹配，故此發明可應用於採用區塊匹配移動估計的視訊編碼標準和其相關的應用中。習知技藝　　本發明乃提出一個應用於影像區塊匹配移動估計的快速模糊搜尋方法。由於方法中採用模糊推理的原理，因此，在此首先簡單說明所採用的模糊推理原理，然後再詳細介紹區塊匹配搜尋方法。　　所採用的模糊推理原理　　模糊推理又可稱為知識庫基礎(knowledge based)推論，1990年C.C.Lee於iEEE Trans.Syst.,Man,Cybern.第20卷第2期第404至435頁利用符號語言的規則記述來模仿專家的經驗及操作模式，使得模糊推論採用了類似專家系統的動作方式及規則記述去做推論。唯模糊推理處理的資料是不確定性的，其推論邏輯為多重邏輯，此有別於專家系統之確定性及雙值邏輯。一個模糊推理機構應由四大部份組成：(1)模糊器(fuzzifier),(2)知識庫(knowledge base),(3)推論機(inference mecha-nism),(4)解模糊器(defuzzifier)，見圖一。玆分別介紹如下：(1)模糊器：模糊器(fuzzifier)主要實現輸入模糊化的動作。模糊化可區分為兩步驟來進行；依序為對應(mapping)，與量化。所謂對應(mapping)，係將外界真實輸入範圍轉換至相對應的輸入變數歸屬函數。而量化，係對於特定的歸屬數值，依照事先釐訂之論域加以等分。本發明釐訂之論域範圍為0~63以u值代表，歸屬數值範圍為0~15以X(u)值代表；0表示最小歸屬度0.0，而15表示最大歸屬度1.0。並採用模糊程度為5的三角形模糊器。假設真實輸入值為x，經過三角形模糊器所產生的相對應歸屬函數X，如圖二，可用下式表示：　　　　 (2)知識庫(knowledge base)：知識庫的核心是一組推論規則，另外還包含前提與結論歸屬函數的定義。知識庫的優劣對於結果的好壞有決定性的影響，故通常利用經驗或實驗數據，來訂出完整的推論規則。假設有一個2輸入1輸出的模糊系統，其中X和Y分別表示經過模糊器產生的輸入歸屬函數，Z代表總和的模糊輸出結果，M _i 和N _i 是前提歸屬函數(antecr-dent membership functions)，而O _i 是結論歸屬函數(consequentmembership functions)，則推論規則可表示為：Rule i: if X is M _i and Y is N _i then Z is O _i, fori=1,2, _… 　　 (3)推論機(inference mechanism):本發明採用Mamdani教授最初在應用上使用之推論法稱直接法。採用此法的原因在於其簡易性及有效性。　　推論過程如下：首先，將X和Y與所有規則的前提部分(antecedent part)相比較，可得出每個規則的(X and M _i )和(Y and N _i )的匹配值如下：　　　　然後，規則i的激發強度可表示為：ω _i =min(η ,η ). 　　因此，規則i對系統提供的輸出可表示為：　　　　最後，所有規則的總模糊輸出結果表示如下：　　　　 (4)解模糊器(defuzzifier)：解模糊器是要將上述求得之總模糊輸出Z轉換成確切的結論輸出(crisp output)以z代表。此部份有三種方法；介別為a.)最大歸屬度法(maximum criterion),b.)中位數法(mean of maximum),c.)重心法(center ofgravity)。由於重心法之結果較類似傳統PI控制器而有較佳之穩態表現，故採用此法。重心法之算式，可表示如下：　　　　整個模糊推理過程可以圖三表示。　　先前區塊匹配移動估計的相關方法一般而言，區塊匹配演算法(Block-Matching Algorithms)是先將一個影像畫面分割成大小為N×N的不重疊方形區塊，然後，由左而右、由上而下求出每一個區塊的移動向量。其方法簡述如下：假如最大可能位移是W個像素寬，則將目前影像畫面中即將編碼區塊，又稱為參考區塊(reference block)內的所有像素值，與前一張編碼後影像畫面中一個(N+2w)×(N+2w)搜尋範圍內可能的候選區塊(candidate blocks)相比較。當最匹配(best-matched)的候選區塊被決定後，參考區塊與最匹配區塊的座標差異即是所謂的移動向量(motion vector)。　　圖四是一個區塊匹配演算法的示意圖，當目前影像畫面中每個區塊的移動向量都被決定後，再以前一張畫面加上每個區塊的移動向量來建立一個目前畫面之預測影像。此時，將真實的目前影像畫面減去預測影像便得到誤差影像，此誤差影像在經過編碼後送出。由於只傳送誤差影像而非真實的目前畫面，只要移動估計作的好，誤差影像便會很小而達到較高的壓縮效率。　　影響區塊匹配演算法效能的兩個主要原因是：a)區塊失真度量(block distortion measure)與b)搜尋方法(searchmethod)。假設目前大小N×N的參考區塊，其最左上角的像素是在座標位置(m,n)，則該參考區塊可表示為B _ref (m,n)；而B _c (m+u,n+v)則代表在前一畫面搜尋範圍內和參考區塊有位移(u,v)的候選區塊。當最大移動位移是w個像素寬，兩個最常見的區塊失真度量法分述如下：1)絕對誤差的總和(SAD,Sum of Absolute Difference)SAD(u,v)= ｜B _ref (m,n)－B _c (m+u,n+v)｜其中－w u,v w.2)誤差平方的平均值(MSE,Mean Squared Error)MSE(u,v)= [B _ref (m,n)－B _c (m+u,n+v)] ² 其中－w≦u,v≦w. 　　針對前一張畫面搜尋範圍內的可能的候選區塊，一一計算其絕對誤差的總和(SAD)或誤差平方的平均值(MSE)。具有最小的絕對誤差的總和(SAD)，或誤差平方的平均值(MSE)之候選區塊即是所謂的最匹配(best－matched)區塊，而該區塊的(u,v)就是移動向量(motion vector,MV)，定義如下：MV=(u,v)∣ _min_{SAD(u,v)/MSE(u,v)} 誤差平方的平均值(MSE)通常產生比絕對誤差的總和(SAD)品質更好的重建影像，但是其運算量也遠高於絕對誤差的總和(SAD)。　　目前已有許多論文，1996年Y.Beak等人於IEEE Trans.ConsumerElectronics第42卷第4期第885至892頁，1997年Z.He等人於IEEE International Symposium on Circuits and Systems第4卷第2809至2812頁提出減少區塊失真度量所需運算、且使硬體實現更簡易的各種方法。實際應用時，使用者可依其需要，選擇過當的區塊失真度量法。　　另一個影響區塊匹配演算法效能的原因是搜尋方法的優劣。完全搜尋是最直接的區塊匹配搜尋方法；由於此法會尋找搜尋範圍(search area)內所有可能的候選區塊，因此它需要(2w+1) ² 吹的區塊匹配運算來決定每個參考區塊之移動向量。雖然完全搜尋可找到最佳的移動向量，但因其需要龐大的誤差平方的平均值(MSE)或絕對誤差的總和運算(SAD)運算，導致搜尋時間過長不易達到影像即時編碼的要求。從1981年以來為了解決運算量過於龐大，許多論文如1997年L.Luo等人於IEEE Trans.Consumer Electronics第43卷第1期第56頁至61頁報導搜尋時間過長的問題，及本國專利公告第312887、31728號，專利第091890、091864號提出各種不同的快速搜尋方法。這些方法中，有的產生較差的影像品質，有的所需的搜尋時間仍然太長。因此，本發明乃提出一個應用模糊推理的快速搜尋方法來解決這些缺點。　　發明目標本發明之首要目的係揭示一個採用模糊推理原理提出之估計影像區塊匹配移動的快速模糊搜尋方法。　　凡是熟悉該技藝的人士在閱讀下列經由不同圖解所展示之較佳實施例詳細說明後，無疑地將非常清楚本發明所揭示之目的和優點。　　發明之詳細說明本發明「使用在影像區塊匹配移動估計的模糊搜尋方法」乃針對每一個方形區塊(block)，快速地決定其相對應的移動向量(motion vector)。本方法中，要決定某個參考區塊的移動向量，可分成三個主要步驟：A)應用模糊推理以決定該參考區塊的預測移動向量，B)決定區塊匹配搜尋範圍之初始中心位置，C)區塊匹配搜尋以決定該參考區塊的最後移動向量。各步驟的詳細步驟，分述於後。　　 (A)應用模糊推理以決定該參考區塊的預測移動向量，係將參考區塊的四個相鄰區塊之已知的移動向量，以模糊推理出其水平方向預測向量及垂直方向預測向量；(B)決定區塊匹配搜尋範圍之初始中心位置，依據步驟(1A)中所獲得的參考區塊的預測移動向量，以決定區塊匹配搜尋範圍之初始中心位置之座標；(C)區塊匹配搜尋以決定該參考區塊的最後移動向量，使用步驟(B)所得之搜尋範圍初始中心位置為搜尋中心點，用一個3×3的搜尋視窗在搜尋範圍內搜尋，直到最匹配的區塊位於目前3×3搜尋視窗的中心或是搜尋迴圈吹數超過使用者所設定的最大搜尋迴圈吹數才停止搜尋。　　 A.應用模糊推理以決定該參考區塊的預測移動向量步驟A乃利用參考區塊的四個相鄰區塊之已知的移動向量，來模糊推理以決定該參考區塊的預測移動向量。假設目前待處理的參考區塊B _ref 是位於畫面第m行第n列，因此標示為B _ref (m,n)，其相鄰的四個區塊以B _i 表示，其中i值從1到4，如圖五所示四個區塊的位置擁有相關聯性，分別為B ₁ (m-32,n)、B ₂ (m-16,n)、B ₃ (m,n-16)、B ₄ (m,n-32)。如果此四個相鄰區塊的已知移動向量用V _i =[△c _i ,△r _i ]表示(i=1,2,3,4)，其中△c _i 係行（水平）之位移,△r _i 係列（垂直）之位移；而參考區塊B _ref 的預測移動向量以 _ref =[△ _ref ,△ _ref ]表示。在影像畫面中，最上兩列、最左兩行的所有區塊的預測移動向量皆令為0，而其他行與其他列的區塊之預測移動向量則用下述動作決定。　　為了求出某參考區塊的 _ref ，使用v ₁ 和v ₂ 來模糊推理出目前參考區塊的水平方向預測向量 _{ref_H} =[△ _{ref_H} ,△ _{ref_H} ]。同理，使用v ₃ 和v ₄ 來模糊推理出目前參考區塊的垂直方向預測向量。然後決定 _ref ，因為。由於B ₂ 比B ₁ 更接近B _ref ，所以v ₂ 應比v ₁ 提供更多且更重要的訊息來決定 _ref ；同理v ₄ 應比v ₃ 提供更多且更重要的訊息來決定 _ref 。運用此原理並經過許多的實驗，本發明可定義出模糊推理所需的歸屬函數及其相關的規則，如圖六所示步驟A之詳細執行步驟如下：　　步驟A1：從先前處理過區塊的移動向量中，取出目前參考區塊中四個相鄰區塊Bi的移動向量V _i ；亦即(△c _i ,△r _i )，其中i=1~4。例如以(△c ₁ ,△r ₁ )表示移動向量V ₁ ，其係四個相鄰區塊標示為B ₁ 、B ₂ 、B ₃ 、B ₄ 中B ₁ 的移動向量。　　步驟A2：以和為模糊推理的兩個輸入，應用前述的模糊推理及圖六所示的規則，推論出輸出值。　　步驟A3：以和為模糊推理的兩個輸入，應用前述的模糊推理及圖六所示的規則，推論出輸出值。　　步驟A4：以和為模糊推理的兩個輸入，應用前述的模糊推理及圖六所示的規則，推論出輸出值。　　步驟A5：以和為模糊推理的兩個輸入，應用前述的模糊推理及圖六所示的規則’推論出輸出值。　　步驟A6：用下式決定該參考區塊的預測移動向量：　　　　 B.決定區塊匹配搜尋範圍之初始中心位置依據在步驟A中所獲得的參考區塊的預測移動向量 _ref ，步驟B訂定出區塊匹配搜尋範圍之初始中心位置(the initialcenter of search area)的座標為((m+△ _ref ),(n+△ _ref ))。　　 C.區塊匹配搜尋以決定該參考區塊的最後移動向量步驟C乃使用步驟B所得之搜尋範圍初始中心位置為搜尋中心點，用一個3×3的搜尋視窗在搜尋範圍內搜尋，直到最匹配的區塊位於目前3×3搜尋視窗的中心或是搜尋迴圈次數超過使用者所設定的最大搜尋迴圈次數才停止搜尋（其中，搜尋一個3×3的視窗，即執行9個區塊匹配運算稱為執行一次搜尋迴圈）。當停止搜尋時，所得的最匹配的區塊位置（在前一張畫面），可決定此目前畫面參考區塊之最後移動向量。　　在本發明中，使用者可使用任何的失真度量法以實現區塊匹配。假設目前待處理的參考區塊B _ref 是位於畫面第m行第n列、搜尋迴圈次數用S表示、且MAX表示使用者自設的最大搜尋迴圈次數，步驟C的詳細步驟如下：　　步驟C1：令搜尋迴圈次數S為1，且令((m+△ _ref )，(n+△ _ref )為目前3×3搜尋視窗的初始中心位置（依據步驟B決定）。搜尋目前搜尋視窗內的9個區塊，找出區塊失真度量最小（最匹配）的那個區塊。　　步驟C2：如果S>MAX或最匹配區塊位於目前3×3搜尋視窗的中心，則跳至步驟C3。否則，S=S+1，且使用下述兩個搜尋模式再進行搜尋，最後再重複此步驟。　　 (1)假如最匹配區塊是位於目前3×3搜尋視窗的垂直／或水平邊緣的中心，則此最匹配區塊的位置就是下一次3×3搜尋視窗的中心位置，且加入三個額外的垂直／水平搜尋點到下一次的3×3搜尋視窗中，如圖七(a)所示。　　 (2)假如最匹配區塊是位於目前3×3搜尋視窗的角落，則此最匹配區塊的位置就是下一次3×3搜尋視窗的中心位置，且加入三個額外的角落搜尋點到下一次的3×3搜尋視窗中，如圖七(b)所示。　　步驟C3：停止搜尋並計算最後的移動向量。　　圖八為使用本發明方法對兩個不同搜尋方向的搜尋示意圖。實施效果　　本發明方法可用軟體程式或特殊設計晶片(ASIC)來實現。而為了降低模糊推理所需的運算時間，可將步驟A2至步驟A5所述的2個輸入1輸出模糊推理過程用查表法來實現。假設區塊最大移動位移W定為±7，則每個模糊輸入值可用4個bits來表示，且模糊輸出值（預測移動向量）也可用4個bits來表示。為了建構模糊推理表(fuzzy table)，需先將每一個可能的輸入組合，代入前述的模糊推理過程，並使用圖六所定的規則，則可得到一個相對應的輸出值。將所有可能輸入所產生的輸出值一一計算，並存入表中。因此只要使用一個具2 ^4×2 個位址線（每個8-bit位址線代表2個輸入的可能組合），每個位址存4bits資料（模糊輸出）的記憶體，其大小為128bytes，就可實現此模糊推理過程。模擬結果　　為了驗證本發明的效果，本發明敘述許多軟體實驗。實驗中，區塊的大小設定為16×16，最大移動位移W定為±7。模糊推理過程則用前述的查表法實現。為了達到比較的目的，另使用九個不同搜尋演算法，詳細的比較本發明和他們方法的搜尋效能。此九個他種搜尋法表示如下：1)完全搜尋(FS,fullsearch),2)1981年T.Koga，等人於Proc.NTC81第C9.6.1至9.6.5頁報導三段搜尋(3SS,three-step search),3)1990年M.Ghanbari於IEEE Trans.Communications，第38卷第7期第950至953頁報導混合搜尋(CS,cross search),4)1991年L.-G.Chen等人於IEEE Trans.Circuits and System for Video Tech第1卷第4期第378至385頁報導類似等級體系的一度空間搜尋(PHODS,parallel hierarchical one-dimensional search),5)1996年L.-M.Po等人於IEEE Trans.Circuits and System forVideo Tech.，第6卷第3期第313至317頁報導四段搜尋(4SS,four-step search),6)1996年L.-K.Liu等人於IEEE Trans.Circuits and System for Video Tech.第6卷第4期第419至422頁報導基本區塊梯度下降搜尋(BBGDS,block-based gradi-ent descent search),7)1997年J.Lu等人於IEEE Trans.Circuits and System for Video Tech第7卷第2期第429至433頁報導簡易且高效率的搜尋(SES,simp1e and efficientsearch),8)1997年L.Luo等人於IEEE Trans.ConsumerElectronics第43卷第1期第56至61頁報導預報搜查演算搜尋(PSA,prediction search algorithm),9)1999年J.M.Jou等人於IEEE Trans.Cicuits and System for Video Tech報導grey預報搜尋(GPS,grey prediction search)，與10)搜尋(FPS，本發明方法)。” 　　橄欖球(Football)”、”火車(Mobile)”、”風車(Windmill)”、”花卉(Flower)”、”網球(Tennis)”、”外務員(Salesman)”和”美國小姐(Miss America)”等七個不同的連續影像(image se-quence)的前一百張畫面被用來測試上述搜尋演算法。這7個連續影像包含了靜止、慢速和快速移動的物件。在表一到表六中分別列出針對不同演算法、不一樣的連續影像對1)平均誤差平方的平均值(MSE,mean square error,2)平均訊號尖峰雜訊比(PSNR,(peak sign al-to-noise ratio),3)平均每像素誤差(prediction errors per pixel),4)平均誤差熵(entropyof prediction errors),5)平均每畫面之不能預測像素百分比(percentage of unpredictable pixelper frame),6)平均每區塊搜尋吹數(search points per block)，的實驗結果。根據表一到表五，很明顯的，本發明的方法得到較佳的影像品質。圖八則列出”橄欖球(Football)”連續影像中的第十五張原始影像，和使用完全搜尋(FS)，三段搜尋(3SS)，四段搜尋(4SS)，基本區塊梯度下降搜尋(BBGDS)and本發明(FPS)等法所的重建影像畫面。很明顯的，只有完全搜尋和本發明方法可清楚的分辨出滑倒在地上的那位球員的背號為82號。因此，可證明本法之優越性。　　此外，本發明和一般搜尋方法，例如完全搜尋(FS)，三段搜尋(3SS)與四段搜尋(4SS)主要的不同乃是使用模糊推理來決定初始的搜尋中心位置。換句話說，本發明比其他方法多使用了步驟A與步驟B所定義的運算。依前所述，模糊推理使用查表法實現；故步驟A共需四次讀取（V ₁ 到V ₄ ）、四次查表（步驟二到步驟五）、2次加法與兩次除法運算；而步驟B則需二次加法運算。從表六可知，本發明的平均搜尋次數（9.94次）只有完全搜尋(FS（202次）)的二十分之一，三段搜尋(3SS(23.1))的二分之一。當區塊大小為16×16，一次搜尋次數(one searchpoint)代表256個像素值的比較，例如絕對誤差的總和運算(SAD)或誤差平方的平均值(MSE)。很明顯的，搜尋次數的多寡，影響整個搜尋時間的長短最大。因此，和其他方法相比，本發明實可達快速搜尋的目的。　　　　　　　　　　　　表例說明　　表一不同搜尋法對誤差平方的平均值(MSE)的結果表二不同搜尋法對訊號尖峰雜訊比(PSNR,peak signal-to-noise-ratio)的結果表三不同搜尋法對預測誤差(prediction error)的結果表四不同搜尋法對預測誤差熵(entropy of prediction er-rors)表五不同搜尋法對不能預測像素百分比(percentage ofunpredictable pels)的結果表六不同搜尋法對搜尋次數(search points)的結果圖式簡單說明　　圖一模糊推理機構　　圖二三角形模糊器　　圖三模糊推理過程示意圖　　圖四區塊匹配演算法的示意圖　　圖五參考區塊和其相鄰四區塊位置圖　　圖六歸屬函數及其相關的模糊規則　　圖七不同搜尋模式(a)搜尋視窗的垂直／或水平邊緣的中心(b)搜尋視窗的角落　　圖八 ”橄欖球(Football)”連續影像中的第十五張(a)原始影像(b)完全搜尋(FS)(c)三段搜尋(3SS)(d)四段搜尋(4SS)(e)基本區塊－梯度下降搜尋(BBGDS)(f)本發明(FPS) 主要元件符號說明　　 401．．．最匹配候選方塊(best-matched candidate block) 　　 402．．．移動向量(motion vector) 　　 403．．．參考區塊　　 404．．．搜尋範圍(search area) 　　 701．．．目前搜尋視窗　　 702．．．目前搜尋視窗的最匹配區塊　　 703．．．用於下一個搜尋視窗的新增搜尋點　　 704．．．下一個搜尋視窗

十、申請專利範圍：
	1、一種用於區塊匹配移動估計的模糊搜尋方法，該方法包括以下步驟：(A)應用模糊推理以決定該參考區塊的預測移動向量，係將參考區塊的四個相鄰區塊之已知的移動向量，以模糊推理出其水平方向預測向量及垂直方向預測向量；(B)決定區塊匹配搜尋範圍之初始中心位置，依據步驟(A)中所獲得的參考區塊的預測移動向量，以決定區塊匹配搜尋範圍之初始中心位置之座標；(C)區塊匹配搜尋以決定該參考區塊的最後移動向量，使用步驟(B)所得之搜尋範圍初始中心位置為搜尋中心點，用一個3×3的搜尋視窗在搜尋範圍內搜尋，直到最匹配的區塊位於目前3×3搜尋視窗的中心或是搜尋迴圈次數超過使用者所設定的最大搜尋迴圈次數才停止搜尋。　　 2、根據申請專利範圍第1項所述之模糊搜尋方法，其步驟(A)更包含下列步驟：(A1)從先前處理過區塊的移動向量中，取出目前參考區塊中四個相鄰區塊Bi的移動向量V _i ；亦即(△c _i ,△r _i )，其中i=1~4;(A2)輸入△c ₁ 和△c ₂ ，使用相關模糊規則，推論出△ _{ref_H} ;(A3)以△r ₁ 和△r ₂ 為輸入，使用相關模糊規則，推論出△ _{ref_H} ;(A4)以△c ₃ 和△c ₄ 為輸入，使用相關模糊規則，推論出△ _{ref_V} ;(A5)以△r ₃ 和△r ₄ 為輸入，使用相關模糊規則，推論出△ _{ref_V} ;(A6)再用下式決定該參考區塊的預測移動向量：　　 3、根據申請專利第1項所述之模糊搜尋方法，其中步驟B係將區塊匹配搜尋範圍之初始中心位置的座標定為((m+△ _ref ),(n+△ _ref ))。　　 4、根據申請專利第1項所述之模糊搜尋方法，其中步驟C係更包含下列步驟：(C1)令搜尋次數記數器S為1,((m+△ _ref ),(n+△ _ref ))為目前3×3搜尋視窗的初始中心位置；搜尋目前搜尋視窗內的9個區塊，找出區塊失真度量最小（最匹配）的那個區塊；(C2)如果S值大於使用者預先設定的最大可執行搜尋次數或最匹配區塊位於目前3×3搜尋視窗的中心，則跳至步驟C3；否則，S=S+1，且使用下述兩個搜尋模式進行搜尋，再重複此步驟：(1)假如最匹配區塊是位於目前3×3搜尋視窗的垂直／或水平邊緣的中心，則此最匹配區塊的位置就是下一次3×3搜尋視窗的中心位置且加入三個額外的垂直／水平搜尋點；(2)假如最匹配區塊是位於目前3×3搜尋視窗的角落，則此最匹配區塊的位置就是下一次3×3搜尋視窗的中心位置且加入三個額外的角落搜尋；(C3)停止搜尋並計算最後的移動向量。


十一、圖式：

瀏覽數: