一種實現菱形搜索算法的硬體結構的製作方法

2023-05-17 11:24:41

專利名稱：一種實現菱形搜索算法的硬體結構的製作方法
技術領域：
本實用新型屬於圖像壓縮技術領域，涉及一種實現菱形搜索算法的硬體 結構。
背景技術：
現實的視頻信號中含有大量的冗餘信息，主要是空間冗餘和時間冗餘， 可以通過數據壓縮去除這些信息數據之間的時間空間函數的自相關性和互 相關性(即去除冗餘)，保留相互獨立的信息分量，從而可以節約存儲空間， 提高傳輸效率，同時使視頻信息在較低速率的信道上進行實時傳送成為可 能。運動估計能夠有效的去除視頻信息之間的時間冗餘，它佔整個視頻壓縮
編碼量的60%-80%，直接影響著編碼的速度和效率，是視頻編碼的一項關鍵 技術。在運動估計中，當前將要傳輸的圖像作為當前幀，已傳輸的作為參考
的圖像稱為參考幀。在進行運動估計運算時的具體流程為首先將每幀圖像 劃分成NxN的宏塊；然後將當前幀的每一個圖像塊與參考幀中對應搜索區 域的所有圖像塊進行匹配計算，找出最佳匹配塊；最後輸出最佳匹配塊的行 列坐標，也就是運動向量MV。因為在對當前塊編碼時相當於只描述了當前 塊相對於參考塊的位移量而沒有具體描述其內容，從而實現去除視頻信息之 間的時間冗餘，這就是運動估計。
運動估計所採用的主要算法通常為塊匹配算法，而塊匹配法大致可分為 兩類:全搜索算法(FSBMA)和快速搜索算法，而後者又包括了如三步法(TSS)，
菱形搜索法(DS算法)，四步法(FSS)等。在快速搜索算法中，菱形搜索由於
利用了在現實視頻中最佳匹配點的分布概率主要集中於以中心點為核心的
一個菱形分布的特點，相對於其他典型的快速算法擁有良好的性能表現，但
是由於其數據流不規則的特性造成硬體系統難於實現，也就限制了菱形搜索
在現實中的實際應用。
發明內容
本實用新型的目的是，提供一種實現菱形搜索算法的硬體結構，來解決 現有技術中很難使用硬體結構實現運動估計中菱形搜索算法的問題。
本實用新型所採用的技術方案是， 一種實現菱形搜索算法的硬體結構， 包M核心控制器，核心控制器通過數據線分別與參考塊存儲器、PE陣列、 SAD陣列、地址生成器、編碼模塊連接；地址生成器通過數據線再與參考塊 存儲器連接；參考塊存儲器和當前塊存儲器的信息流輸出端同時接入PE陣 列的信息流輸入端，PE陣列的信息流輸出端與SAD陣列的信息流輸入端 連接；SAD陣列的信息流輸出端與編碼模塊的信息流輸入端連接。
本實用新型的有益效果是，該硬體結構只使用了很低的輸入帶寬和較少 的硬體損耗實現了菱形搜索算法，加快了視頻編碼中運動估計速度。

圖1是本實用新型硬體結構的示意圖2是菱形搜索中的各種搜索位置示意圖，其中圖2(a)所示為鑽石形狀 的九個起始位置、圖2 (b)所示為頂點搜索時需要附加的搜索位置、圖2 (c) 所示為邊搜索時需要附加的搜索位置、圖2(d)所示為最終的最佳匹配位置；
圖3是一個完整的菱形搜索算法例的示意圖4是參考塊存儲器結構示意圖5是參考塊存儲器中的更新順序和輸出順序示意圖，其中圖5(a)所示 為左下到右上的輸出順序、圖5 (b)所示為左上到右下的輸出順序、圖5(c) 所示為右下到左上的輸出順序、圖5 (d)所示為右上到左下的輸出順序；
圖6是PE陣列結構示意圖7是SAD陣列結構示意圖8是菱形搜索的數據流分析和掃描順序示意圖9是菱形搜索中的四種移動模式示意圖，其中圖9 (a)為參考塊從左 下到右上的移動、圖9 (b)為參考塊從左上到右下的移動、圖9 (c)為參 考塊從右下到左上的移動、圖9 (d)為參考塊從右上到左下的移動；
圖中，1、當前塊存儲器，2、參考塊存儲器，3、 PE陣列，4、 SAD陣 列，5、地址生成器，6、編碼模塊，7、核心控制器。
具體實施方式

以下結合附圖和具體實施方式
對本實用新型進行詳細說明。
如圖1所示，本實用新型裝置主要包括核心控制器7，核心控制器7通 過數據線分別與參考塊存儲器2、 PE陣列3、 SAD陣列4、地址生成器5、 編碼模塊6連接；地址生成器5通過數據線再與參考塊存儲器2連接；參考 塊存儲器2和當前塊存儲器1的信息流輸出端同時接入PE陣列3的信息流 輸入端，PE陣列3的信息流輸出端與SAD陣列4的信息流輸入端連接； SAD陣列4的信息流輸出端與編碼模塊6的信息流輸入端連接。圖中黑細線 為交互控制指令的傳輸線，寬箭頭為信息流的傳輸方向。
以下說明中都設定運動估計劃分的基本圖像塊大小為NxN。
菱形搜索算法(DS算法)的計算方式如下，
如圖2所示，為DS算法第一步和其他步驟的搜索位置，DS算法第一
步的搜索位置呈菱形形狀排列，在以後的步驟中，每一步的搜索位置由上一 步得出的結果確定。
算法的具體步驟為，
第一步、對搜索窗口中心，如圖2(a)所示的鑽石形狀的九個位置作匹配 運算，如果得出的最佳匹配位置在鑽石的中心(c， c)，則跳到第三步;如果得 出的最佳匹配位置在鑽石的邊上(c-l， c+l)， (c-l, c-l), (c+l， c-l)， (c+l: c+l)，或頂點上(c-2， 0) , (c+2， 0) ， (0， c-2) ， (0, c+2)則跳到第二步；
第二步、如果第一步得到的最佳匹配位置在邊上，即點(c-l，c+l), (c-l, c-l) ， (c+l,c-l) , (c+l,c+l)，則作邊搜索。邊搜索時需要附加的搜索位置
如圖2(C)所示，在四個邊上的情況相同；如果第一步得到的最佳匹配位置在
頂點上，即點(c-2，0)，(c+2，0),(0，c-2)，(0，c+2)，則作頂點搜索。頂點搜索 時需要附加搜索的位置如圖2 (b)所示。如果這一步得到的最佳匹配位置在中 心位置，則跳到第三步，否則，跳回第二步開始，繼續作搜索；
第三步、以上一步得到的最佳匹配位置(c,c)為中心，對(c-l,c)，(c+l,c)， (c，c-l)， (c， c+l)四個位置作匹配運算，此時需要附加搜索的位置如圖2 (d) 所示，得到最終的最佳匹配位置。
如圖3所示，是應用菱形搜索算法的一個完整過程的例子，如果第一步 得到最小絕對差值之和(SAD)的位置是坐標原點，則對a，b,c，d四個位置 作最後的匹配運算。否則要對附加的搜索位置進行匹配。圖中得到的最佳匹 配位置是(6， —3)。
根據算法設計的整體結構中，每個單元的具體結構和工作原理如下
當前塊存儲器1用於存儲當前圖像塊的象素值，是一個NxN的寄存器 組，電路開始工作後每個時鐘從外部依次讀入一個象素進入相應的寄存器，
當NxN個時鐘後讀滿並可以進入工作狀態，即可以向PE陣列3輸入當前塊 的象素值。
如圖4所示，參考塊存儲器2的結構是一個NxN的寄存器組，用於存 儲參考塊的象素值，並將象素值按照一定順序輸出到PE陣列3。為了方便 說明，圖中顯示的是當N二4時的結構，當N為其他值時的結構依此類推。 該結構中的輸入帶寬為一個象素，即8bit。圖中的@ 是編程開關， 可以實現連接和斷開兩種狀態。根據對菱形搜索數據流的分析得到的四種移 動模式，在參考塊中對應的動作如下-
a.左下到右上時，@導通而 關斷，其對應的寄存器間的數據 流如下
formula see original document page 7b.左上到右下時， 導通而@ @關斷，其對應的寄存器間的數據
流如下
formula see original document page 7
C.右下到左上時， 導通而@ 關斷，其對應的寄存器間的數據 流如下
扁
formula see original document page 8
d.右上到左下時， 導通而@ 關斷，其對應的寄存器間的數據
流如下
formula see original document page 8
因為PE陣列3由N/2個PE構成，所以每次由參考塊存儲器2向PE陣 列3輸出N/2個象素點以供其計算。經過分析發現，在上述四種移動模式中， 每種的參考塊中間(N-2) X (N-2)的象素總是重複的。
如圖5所示，本實用新型設置了與上述四種移動模式相對應的輸出順序
a. 左下到右上(如圖5 (a))
b. 左上到右下(如圖5 (b))
c. 右下到左上(如圖5 (c))
d. 右上到左下(如圖5 (d))
圖中數字代表讀出的順序，深色點代表需要更新的象素點，箭頭表示更新象
素點的順序，參考塊存儲器2每個時鐘周期輸出N/2個象素點，圖中的N為 8，每個時鐘周期可以更新一個象素點。每個參考塊中一共有N+(N-1)個象素 需要更新，而每個時鐘周期輸出N/2個象素，所以只要按照圖中的順序更新 象素和輸出，就能在象素更新結束後的下一周期將所有象素輸出完畢。
如圖6所示，PE陣列3用於計算當前塊和參考塊之間的SAD值。整個 PE陣列3由N/2個PE構成，為了方便說明，所以圖中顯示的是當N二8時 的PE陣列結構，當N為其他值時的結構依此類推。每個PE可以計算兩個 象素之間的絕對差值，加法器將PE輸出的絕對差值相加後存儲到累加器 (ACCM)，當整個參考塊於當前塊的象素點(NxN個象素點)被計算完後， 這個參考塊的SAD值經過選擇器被送到與其位置對應的SAD陣列4中的寄 存器中去。
SAD陣列4用於存儲菱形搜索中對應候選塊位置上的SAD值，並將 SAD值提供給編碼模塊6以供其使用。該結構利用菱形搜索的數據流特點， 充分復用了己經計算過的SAD值，可以大大減少重複的計算量。
如圖7所示，圖中的②②是編程開關，根據控制實現連接和斷開兩 種狀態，其開關條件取決於最優匹配點的位置，並且每次只有一個開關導通， 其他的開關此刻都斷開。X1 X4， Y1 Y4的導通條件如下
XI:最優點為上方的點；
X2:最優點為右方的點；
X3:最優點為下方的點；
X4:最優點為左方的點；
Yl:最優點為右上方的點；
Y2:最優點為右下方的點； Y3:最優點為左上方的點； Y4:最優點為左下方的點；
利用這個結構，可以大幅減少重複的候選點的SAD計算，從而提高了計算速度。
地址生成器5用於根據參考塊需要輸出到PE陣列3的象素順序產生相 應的象素在參考塊中的地址，以使得參考塊能夠正確輸出。
編碼模塊6用於根據SAD陣列4存儲的SAD值，找到SAD最小的匹 配塊，從而找到最優的匹配塊並輸出其運動矢量。
核心控制器7用於協調所有模塊的工作和控制所有時序。
如圖8所示，該結構是根據菱形搜索的數據流特點設計的，菱形搜索的 數據流特點可以從菱形搜索流程中看出，為一個菱形搜索的所有候選點的位 置，其中a， b， c三點的對應參考塊也顯示了出來，由圖8中可以看出，ab c三點為近鄰點，而近鄰點之間的參考塊之間都有(N-l)X(N-l)的象素是重疊 的。圖8中箭頭顯示的是LDS和SDS的搜索路線。
如圖9所示，在菱形搜索中，其對應的參考塊更新象素點的分布方式分 為四種
A、 左下到右上(如圖9 (a))
B、 左上到右下(如圖9 (b))
C、 右下到左上(如圖9 (c))
D、 右上到左下(如圖9 (d))
菱形搜索的方式有大菱形搜索(LDS)和小菱形搜索(SDS)，利用上面提出 的四種移動方式，可以涵蓋菱形搜索中所有的移動。最終根據這個特點設計
了參考塊存儲器2，使該參考塊存儲器2硬體消耗小且輸入帶寬小的同時保 持了運算所需要的高速度。
另一方面，在計算SAD值的時候，當最優點不在中央而在邊上或者角 上時，在下一個菱形搜索框中其實有很多候選點對應參考塊的SAD值是已 經在前一個菱形搜索框中計算過的，其中，當最優點在角上時，在下一個菱 形搜索框中有4個點的SAD值已經在前面的菱形搜索框中計算過，當最優 點在邊上時，在下一個菱形搜索框中有6個點的SAD值已經在前面的菱形 搜索框中計算過。因此利用這個特點設置SAD陣列4。該陣列在最優點在邊 上或角上的情況下，將計算過的SAD值移動到新的菱形搜索框中對應的位 置，只計算新的候選點的SAD值，從而減少了重複計算。
本實用新型根據上述分析的菱形搜索數據流特點，設置了電路的硬體結 構，該電路的工作過程是，首先分別從當前幀和參考幀中讀入圖像數據進入 當前塊存儲器1和參考塊存儲器2，然後兩個存儲器的象素按照設計的順序 進入PE陣列3，並由PE陣列3計算出當前塊和參考塊之間的SAD值，SAD 值計算完畢後由PE陣列3計送入SAD陣列4中相應位置的存儲器中，然後 用同樣的方法計算下一個參考塊的SAD值，如此循環直到所有菱形搜索需 要的所有參考塊的SAD值計算完畢。最終由編碼模塊6根據SAD陣列4中 的各模塊的SAD值來判斷最佳匹配點，並由最佳匹配點的位置來判斷下一 次菱形搜索的菱形搜索位置，並再次計算新的菱形搜索範圍內所有參考塊的 SAD值，再判斷最優點。如此循環，直到最優點的位置收斂為中心點，然後 在計算完中心點和周圍四點的SAD值後，由編碼模塊6判斷出SAD值最小 的匹配塊，並將其相對於當前塊的水平和垂直位移量作為運動矢量輸出，從 而完成運動估計。
本實用新型充分利用了菱形搜索中的數據流特點，減少了重複數據的輸 入和計算並同時提高了計算的速度。
權利要求1.一種實現菱形搜索算法的硬體結構，其特徵在於包括核心控制器(7)，核心控制器(7)通過數據線分別與參考塊存儲器(2)、PE陣列(3)、SAD陣列(4)、地址生成器(5)、編碼模塊(6)連接；地址生成器(5)通過數據線再與參考塊存儲器(2)連接；參考塊存儲器(2)和當前塊存儲器(1)的信息流輸出端同時接入PE陣列(3)的信息流輸入端，PE陣列(3)的信息流輸出端與SAD陣列(4)的信息流輸入端連接；SAD陣列(4)的信息流輸出端與編碼模塊(6)的信息流輸入端連接。
專利摘要本實用新型公開了一種實現菱形搜索算法的硬體結構，包括核心控制器分別與參考塊存儲器、PE陣列、SAD陣列、地址生成器、編碼模塊連接；地址生成器再與參考塊存儲器連接；參考塊存儲器和當前塊存儲器的信息流輸出端同時接入PE陣列的信息流輸入端，PE陣列的信息流輸出端與SAD陣列的信息流輸入端連接；SAD陣列的信息流輸出端與編碼模塊的信息流輸入端連接。該硬體結構充分利用了搜索算法中的重複數據，只使用了很低的輸入帶寬和較少的硬體損耗實現了運動估計中的菱形搜索算法。本實用新型可以使用於任何視頻編碼硬體設備中，可以用於多種匹配塊尺寸大小情況下的菱形搜索。
文檔編號H04N7/26GK201066898SQ20072003226
公開日2008年5月28日 申請日期2007年7月17日 優先權日2007年7月17日
發明者餘寧梅, 廖裕民, 王冬芳 申請人:西安理工大學