塊匹配方法中採用遺傳算法進行運動矢量初始化的方法
2023-05-20 22:48:46 1
專利名稱：塊匹配方法中採用遺傳算法進行運動矢量初始化的方法
技術領域：
本發明涉及一種圖像壓縮方法，更具體地說，涉及塊匹配方法中採用遺傳算法進行運動矢量初始化的方法。其中，根據與從圖像參考幀中檢測到的預定形狀的關係，來劃分特徵塊，並且根據被劃分的各個特徵塊執行不同的初始化運算。
在圖像壓縮技術中有兩種類型。一是幀內編碼，即利用在圖像中存在的空間冗餘度壓縮信息；二是幀間編碼，即利用時間順序上圖像之間的時間冗餘度壓縮信息。
特別是，當傳輸一幅運動圖像時，應用幀間編碼的運動補償編碼被典型地用來減少數據傳輸量。
運動補償編碼涉及傳輸表示一個運動目標的位移值的運動矢量和根據在時間上相鄰圖像幀的運動補償的預測誤差。
塊匹配算法(BMA)被用在涉及硬體的實時運動圖像傳輸系統中，作為測量目標運動量的方法。
全搜索方法，三步搜索方法，應用高速算法的逐次搜索方法，和分層的BMA方法被用在塊匹配算法中。在全搜索方法中，數據流是規則的，這樣，與其它方法相比，硬體上易於實現，並且具有好的預測特性。但是，全搜索方法有一個缺點，它需要大量的計算。
遺傳算法是基於自然選擇和遺傳結構的搜索算法，其中通過人工系統，實現了自然界的自適應現象。
為了實現遺傳算法，被優化的主題必須通過一組參數表達，即，含有遺傳信息的有效位組。這組參數在遺傳算法中是重要的。位組必須被確定為與自然目標類似的，這樣足以能表示出希望的信息。
當確定的遺傳信息被傳到下一代時，遺傳特徵被改變了。按照適配性(fitness)，即用於改變遺傳特徵的傳輸函數，來確定所要選擇的算子。遺傳算法是一種優化含有不同遺傳信息的群體的方法，它利用內在的遺傳信息而不是被其它搜索方法使用的直接現象。
遺傳算法是一種隨機搜索方法。然而，不象其它的隨機搜索方法，在遺傳算法中，除了簡單的隨機特性，也存在自然界的遺傳特徵。遺傳算法被表達為一個表示遺傳信息的集合，例如遺傳特徵(DNA或染色體)和遺傳特徵的進化和改變。因此，遺傳搜索算法不是被隨機函數確定的而是指表示遺傳信息的集合的自然現象。對於運一點，遺傳再生(reproduction)、交叉(crossover)、變換(mutation)的函數被確定了並且生物的特徵被應用了，因為遺傳特徵從一代到另一代進化，改變致使熵減小。正如上所述，遺傳算法是隨機函數，局部特性的影響被減少，被本質行為決定的作為自然現象的整個特性被有效搜索。
在遺傳算法中，按照適配性，群體的遺傳特徵從一代到另一代改變了。按照適配性，遺傳算法僅選擇一個合適的遺傳特徵。對於這樣一個過程，改變遺傳特徵的遺傳算子是必須的。在實際應用問題表現好結果的簡單遺傳算法是由再生、交叉、變換三個算子構成的。
再生是按照它們的被叫作適配性函數的目標函數複製遺傳特徵到下一代的操作。目標函數能夠是一個預測函數表(barometer)，它按照所應用的問題顯示最優狀態。按照適配性複製遺傳特徵，意味著很可能具有高適配性的遺傳特徵保持到下一代。
再生之後，以二步執行交叉。在任意地偶合新產生的遺傳特徵和選擇任意遺傳特徵的任意位置之後，遺傳特徵與對應遺傳特徵交換到最後一位。
然後，有通過給定的概率產生的變換，這是從0到1或從1到0改變遺傳特徵任意位的算子。在遺傳算法中，變換起輔助作用，僅僅通過再生和交叉不用變換就能得到最優的結果。
本發明的目的是提供一種依據在應用了遺傳算法的塊匹配方法中被檢測形狀的特徵塊的初始化方法。用這種方法通過按照與在一個圖像參考幀中檢測形狀的關係特性來劃分宏塊，並且按照被劃分的塊執行合適的初始化，可以減少運動矢量的計算量。
因此，為了達到第一個目標，提供了一種在塊匹配方法中應用遺傳算法進行初始化的方法，包含下列幾步(a)從一個圖像的參考幀中檢測一個預定的形狀，並且分段圖像成為預定的塊；(b)依照各塊與該形狀的關係特徵來劃分各個被分段圖像的塊；和(c)通過將一個適合的運動矢量應用到各特徵塊中來初始化運動矢量。在步驟(b)中，各塊被劃分成與檢測形狀無關的塊、重疊了被檢測形狀輪廓線的塊、在被檢測形狀裡的塊。在步驟(c)中，DPC(動態群體控制)方法被用到與檢測形狀無關的塊中，具有加權值的相鄰塊的運動矢量被應用到與檢測形狀輪廓線有重疊的塊中，相鄰塊的運動矢量被應用到在檢測形狀內的塊中。
通過參考附圖詳細描述一個優選實施例，本發明的上述目標和優點將會更清晰，其中；
圖1描述了一個應用遺傳算法的塊匹配方法；圖2描述了依照本發明的初始化方法；圖3描述了依照圖2的各種類型應用了遺傳算法的初始化方法；和圖4表示了一個搜索塊。
圖1描述了應用遺傳算法的塊匹配方法，它是一個利用相鄰塊的運動矢量的相關性應用遺傳算法的一個實施例。
首先，確定參考塊的運動矢量(S10)。當不考慮圖像特徵時，將隨機產生的運動矢量確定為初始值。然而，在與相鄰塊有相關性的運動圖像中，應用相關性將相鄰塊的運動矢量的平均值確定為初始值。當平均值被確定為初始值時，通過減少遺傳算法的迭代次數和所要搜索的塊數，可以減少計算量。
採用均方差(MSE)來基於初始化的運動矢量計算適配性(S12)。即，隨著誤差變小適配性變大。
具有用來計算適配性的最小均方差MSE的一對群體，即最優群體被選擇(S14)。
通過組合或交換步驟S14所選擇群體的基因，執行交叉過程(S16)。這裡，交叉處理是通過一個叫做均勻交叉(UX)的掩碼操作來執行。即，產生一個與父組的染色體相同長度的掩碼(mask)。這些位的值是被隨機確定的。當一位的值是1時，子代的值等於兩個群體的染色體之一的值。當一位的值是0時，子代的值等於另一個染色體的值。其它子代的值通過反轉掩碼被確定。
因為由於統計的原因可能有很多特徵從父組丟失，所以為了補償這一點，執行變換過程，反轉染色體的值(步驟S18)。即，能找出整體最優值，而不僅僅是一個局部最優值。
最後，重複步驟S10到S18，直到獲得一個預先確定的最優值，產生最強的染色體並且該染色體的值就是整體最優值(S20步驟)。
圖2描述了依照本發明的初始化方法，示出了一個簡化的人像，即從圖像的參考幀中被檢測的目標。
這裡，從參考幀中被分段的宏塊被分成下列塊不屬於被檢測形狀的塊，象塊A1-B1(A類塊)；包含被檢測形狀輪廓線的塊，象塊A4-B2(B類塊)；完全被包含在被檢測形狀裡的塊，象塊A5-B3(C類塊)。
在A類塊中，它的運動矢量是很難預測的，參考鄰塊的運動矢量確定初始值。由於在很多情況下，一個B類塊至少有一個運動矢量，利用鄰塊預測運動不是有效的。C類塊有相同的運動矢量具有一個高的概率。在某些部分有一個微小不同的運動。特別是，人的眼睛和嘴巴是好的例子。C類型塊適合於應用遺傳算法。
圖3描述了依據圖2的類型應用了遺傳算法的初始化方法。有構成二個父染色體和兩個子染色體的四個群體。
首先，與被檢測形狀有關的宏塊的特性被確定(S30)。
根據在S30步驟判定結果，動態群體控制(DPC)方法被應用到與檢測塊無關的塊，即A類塊中。即，在這種方法中，與前一幀相同位置的塊的一個運動矢量和位於該塊的上、下、左、右的每個塊的一個運動矢量被定義為父染色體。從圖4所示的搜索區的塊中任意選擇兩個運動矢量，並且被六種選擇中具有最小適配性的兩個染色體替換。每三代執行一次DPC。每個任意值從第三代的第一和第三搜索區中被選擇。每個任意值從第六代的第二和第四搜索區中被選擇。在第九代和第十二代中以上述的次序重複選擇搜索區域。考慮到人的眼睛在垂直方向上更敏感，才這樣確定次序。
與步驟S30中檢測的形狀有關的塊是否重疊輪廓線被確定(步驟34)。如果不重疊輪廓線，具有加權值的相鄰運動矢量被用到初始化中(S36)。即，既使形狀的某些部分位於塊中，形狀的運動也會影響整個塊。然而，存在背景運動不能被忽略的情況，則將不同的加權值附給這兩種情況。從相鄰塊中的A類塊和C類塊中，選出作為父染色體的每個運動矢量。執行交叉，以便更有效地跟隨屬於C類的父染色體的特徵。即，不是通過執行任意掩碼而是通過給予加權值來產生子代，這樣能更有效地跟隨C類塊。
根據步驟S34確定的結果，在塊不重疊輪廓線的情況下，相鄰運動矢量被用到初始化中(S38)。在這種情況下，最好能夠在被分段形狀內的塊中搜索微小的運動。因為除了考慮到整體運動，很可能形狀的運動也變成了塊自身的運動。這時，在從C類塊中選擇一個運動矢量和從與前一幀相同位置的塊中選擇一個運動矢量作為父染色體之後，可以利用例如交叉或變換的算法來搜索微小運動值。
在本發明中，為了預測最優運動矢量，對一幅圖像的特徵採用了遺傳算法。用於預測運動矢量的最精確的方法是全搜索方法，它需要太多的運算。為了解決上述問題，一個簡化的方法被應用，但是缺少精確性。即，整體最優值可能沒被發現，僅集中於局部最優值。而應用遺傳算法，可以找到整體最優值，卻沒有不正確的假設。然而，在遺傳算法中有相對大量的運算。為此，在根據圖像塊的特徵的塊匹配方法中，採用了遺傳算法。這種方法，比利用僅基於相鄰塊運動矢量的遺傳算法的方法，產生最優運動矢量的計算量小，而且應用這種方法可以計算正確的運動矢量。
權利要求
1．一種在塊匹配方法中應用遺傳算法進行初始化的方法，包括(a)從一幅圖像的參考幀中檢測一個預定形狀，並且將該圖像分段成預定塊；(b)按照各塊與該形狀的關係特徵，劃分被分段圖像的各塊；和(c)通過應用合適的運動矢量到各特徵塊中來初始化運動矢量。
2．如權利要求1的初始化方法，其中，在步驟(b)，各塊被劃分成與檢測形狀無關的塊、與檢測形狀的輪廓線有重疊的塊、在檢測形狀內的塊。
3．如權利要求2的初始化方法，其中，在步驟(c)，對與檢測形狀無關的塊採用DPC(動態群體控制)方法，對與檢測形狀輪廓線有重疊的塊採用有加權值的相鄰塊運動矢量，對在檢測形狀內的塊採用相鄰塊的運動矢量。
全文摘要
按照被檢測形狀的特徵,提供了在應用遺傳算法的塊匹配方法中初始化的方法。該方法包括有步驟:(a)從一幅圖像的參考幀中檢測一個預定形狀並且將該圖像分段成預定塊,(b)按照各塊與該形狀的關係特徵劃分被分段圖像的塊,和(c)通過應用合適的運動矢量到各特徵塊中來初始化運動矢量。這種方法比利用僅基於相鄰塊運動矢量的遺傳算法的方法,找出最優運動矢量的計算量小,而且應用該方法可以計算正確的運動矢量。
文檔編號G06N3/00GK1222041SQ98118490
公開日1999年7月7日 申請日期1998年8月20日 優先權日1997年12月29日
發明者姜相旭 申請人:三星電子株式會社