基於歸一化相關係數的模板匹配高速並行實現方法和裝置與流程

2023-12-01 15:44:46

本發明涉及圖像模板匹配技術領域，特別涉及一種基於歸一化相關係數的模板匹配高速並行實現方法和裝置。

背景技術：
模板匹配主要用來定位圖像中的一個目標，它廣泛應用於圖像對齊、邊緣檢測、雙目立體視覺等圖像處理領域，並且這些圖像處理手段已經在飛彈目標識別、衛星圖像監控、醫療圖像融合、基於雙目立體視覺的測量等軍用民用領域中得到廣泛應用。模板匹配主要是通過計算搜索位置處已知模板圖與實時圖搜索區域之間的相似性測度來定位與模板圖有類似尺寸和圖像的目標。由於歸一化互相關係數對亮度和對比度變化具有不變性，其算法相對簡單並且具有很高的精度，因此迄今為止它是模板匹配中應用最廣泛的一種測度。假設實時圖由A表示，模板圖由B表示，其尺寸分別為K×L和M×N個像素。在任一搜索位置(u,v)（0≤u≤K-M，0≤v≤L-N）的歸一化互相關係數(NCC-NormalizedCross-Correlation)定義為：其中∑∑表示為模板圖的灰度均值，為在當前搜索位置的實時圖與模板圖重疊部分的灰度均值。由此可以看出，實際上該運算就是在實時圖中平移模板圖，並對實時圖和模板圖重疊點進行歸一化相乘，然後進行累加操作。為了獲得精確定位，模板匹配需要在實時圖中搜索與模板圖相重合的每一個區域，因此對於一個通常的應用，需要搜索的位置數目往往非常多。對於自動目標識別、跟蹤等實時應用領域，基於歸一化互相關測度的模板匹配計算量相對還是太大從而導致其應用受到很大限制。目前已經提出許多技術來加速模板匹配計算，由於這些技術不需要對所有位置進行匹配，因此大幅度的降低了計算量，但是這些技術通常由於局部的極值點幹擾導致錯誤的匹配。事實上，由於模板匹配的計算是針對圖像各個像素進行相關運算，因此該方法本身能夠通過並行的方法來加速。另外也提出了一些多處理器系統來加速模板匹配的計算。但是對於要求小型化、微功耗的嵌入式應用，多處理器方法無法滿足實際應用要求，並且也不經濟。近年來，隨著電子技術和製造工藝的快速發展，現場可編程門陣列(FPGA)的容量越來越大、速度越來越快，這使得FPGA具有了一般微處理器所無法比擬的強大的並行性，因此FPGA特別適用於實現模板匹配計算。專利申請號為200910069272.6高速圖像匹配方法及裝置提出的是一種實現歸一化互相關係數方法，該方法實現結構簡單，但具體實現流程需要太多的切換，乘累加模塊的輸入需要切換多個輸入，這將增加邏輯資源消耗、增加布線的難度，導致布線路徑較長從而降低系統可能達到的最高內核速度，同時增加了功耗；輸出的只是中間累加結果，這將導致需要更多的外部存儲空間或者需要DSP緊密配合運算，從而佔用大量的DSP運行時間，導致DSP的控制和通信的複雜度，降低DSP運行的實時性。而本發明能夠解決上面的問題。

技術實現要素：
本發明針對上述現有技術的不足，提出了一種基於歸一化相關係數的模板匹配高速並行實現方法，該方法可由現場可編程門陣列(FPGA)或超大規模集成電路(VLSI)通過並行方式來高速高精度地計算歸一化互相關係數，能夠進一步減少邏輯資源消耗，降低功耗和成本，同時提高運算速度；採用該方法的設備能夠實現精度高、參數設置靈活、實時性強的高速模板匹配。本發明解決上述技術問題所採用的技術方案是：基於歸一化相關係數的模板匹配高速並行實現方法和裝置，高速並行實現方法包括有如下步驟：步驟1：讀入實時圖和模板圖數據到對應的內部RAM緩衝塊中，同時實時圖數據存儲到用於計算實時圖灰度值總和與實時圖灰度值平方總和的實時圖數據緩衝RAM中，同時進行模板圖灰度值總和模板圖灰度值平方總和的計算和第1行第1列搜索位置處實時圖灰度值總和實時圖灰度值平方總和的計算；步驟2：計算搜索位置第1行後續各列的實時圖灰度值總和同時計算當前位置實時圖灰度值平方總和搜索位置第1行各列模板圖實時圖灰度值乘積總和及歸一化相關係數；步驟3：讀入新一行的實時圖數據到數據已經無效的內部RAM緩衝塊，同時該新一行實時圖數據讀入到用於計算實時圖灰度值總和與實時圖灰度值平方總和的實時圖數據緩衝RAM中覆蓋已經無效的數據，同時計算當前行第1列的實時圖灰度值總和實時圖灰度值平方總和值；步驟4：採用上述步驟2、步驟3相同的方式，依次計算出後續各行歸一化相關係數。上述模板匹配方法所用的歸一化相關係數公式如下：A表示實時圖，B表示模板圖，其尺寸分別為K×L和M×N個像素。(u,v)為任一搜索位置，0≤u≤K-M，0≤v≤L-N。ΣΣ表示為模板圖像的灰度平均值，為當前搜索位置(u,v)處實時圖與模板圖重疊部分的灰度平均值。步驟1所述的模板圖數據讀入到對應的內部RAM緩衝塊，是將每一行N列的灰度值存儲到一個RAM塊中，共存入M行，即採用了M個RAM塊，每個RAM塊包含N個存儲單元；實時圖數據讀入到對應的內部RAM緩衝塊，是將每一行L列的灰度值存儲到一個RAM塊中，共存入M行，同樣採用了M個RAM塊，每個RAM塊包含L個存儲單元；實時圖數據存儲到用於計算實時圖灰度值總和和實時圖灰度值平方總和的實時圖數據緩衝RAM中，總計存入M行N列數據，即該塊RAM包含M×N個存儲單元。步驟1所述的模板圖灰度值總和的運算在讀入模板圖數據時，通過時序控制模塊控制一個累加器實現。累加器的輸入端連接到模板圖數據輸入端，其輸出即為模板圖灰度值總和。步驟1所述的模板圖灰度值平方總和的運算在讀入模板圖數據時，通過時序控制模塊控制一個平方運算模塊和累加器實現。平方運算模塊的輸入端連接到模板圖數據輸入端，平方運算模塊的輸出連接到累加器的輸入端，累加器輸出即為模板圖灰度值平方總和。步驟1中所述的搜索位置第1行第1列的實時圖灰度值總和的計算，是通過時序控制模塊控制一個行數據累加模塊在讀入每一行實時圖數據時，對實時圖第1行第1列搜索位置處每一行數據進行累加，然後通過一個列累加器對這些行數據累加模塊輸出結果逐列進行累加，並且和經過M步(模板圖行數步)延遲的列累加器累加結果相減獲得。步驟1中所述的搜索位置第1行第1列的實時圖灰度值平方總和的計算，是通過時序控制模塊控制一個行數據累加模塊在每一行實時圖數據讀入時，對實時圖第1行第1列搜索位置處每一行數據平方後進行累加，然後通過一個列累加器對這些行數據累加模塊輸出結果逐列進行累加，並且和經過M步(模板圖行數步)延遲的列累加器累加結果相減獲得。步驟2中後續各列每一個實時圖灰度值總和計算，是從搜索位置第2列開始，通過時序控制模塊控制實時圖數據緩衝RAM同時依次逐行輸出實時圖與模板圖重疊區域中相對於前一個搜索位置新進的一列數據和剛移出的一列數據，由減法器作差後，再通過累加器逐行求和，並且與前一列搜索位置處的該累加器結果值求和（即該累加器從第2列開始保留所有的累加值），然後由加法器與已經計算出的當前行第1列搜索位置處的相加即可獲得當前列的步驟2中後續各列每一個實時圖灰度值平方總和計算，是從搜索位置第2列開始，通過時序控制模塊控制實時圖數據緩衝RAM同時依次逐行輸出實時圖與模板圖重疊區域中相對於前一個搜索位置新進的一列數據和剛移出的一列數據，分別由平方運算模塊求平方後再由減法器作差，然後通過累加器逐行求和，並且與前一列搜索位置處的該累加器結果值求和（即該累加器從第2列開始保留所有的累加值），最後由加法器與已經計算出的當前行第1列搜索位置處的相加即可獲得當前列的步驟2中模板圖與實時圖當前搜索位置的灰度值乘積總和的計算如下實現。模板圖RAM緩衝塊的所有輸出端連接到一個多路選通開關，多路選通開關的輸出連接到乘法模塊中的一個乘法器的一端，乘法器的另一端對應連接到實時圖像RAM緩衝塊的輸出端；採用模板圖最大行數(M)個這樣的並行通道進行並行運算，然後各個通道輸出端連接到一個並加模塊的輸入端，並加模塊的輸出端連接到一個累加模塊。在具體計算時，時序控制模塊控制選通開關使得對應的模板圖數據與實時圖數據進行乘積運算，改變模板圖像和實時圖像RAM緩衝塊的地址，逐列輸出模板圖和實時圖的對應數據進行乘積運算，然後經過並加模塊對當前列各行數據進行求和，然後由累加模塊對並加模塊輸出結果逐列求和，獲得當前列各個搜索位置的步驟2所述計算歸一化相關係數是在和計算出來以後，相應的可以由乘法器、平方運算、加、減法器計算出來。歸一化相關係數計算公式中的分母由兩個求根模塊進行求根運算，然後再對兩者進行相乘獲得。然後歸一化相關係數計算公式中的分子和分母由定點轉化為浮點，最終通過一個浮點除法運算得到浮點數據類型的歸一化相關係數。步驟2所述的搜索位置第1行歸一化相關係數的計算，是模板圖像第1到M行與實時圖第1到M行數據對應計算，搜索位置第1列歸一化相關係數的計算為模板圖像第1到N列與實時圖像第1到N列數據對應計算，同時計算第2列的模板圖像在實時圖像中右移一列，並計算該處的同時計算第3列的此時後續的求平方根、浮點除法等後續運算同步流水進行，以此重複，直到第一行歸一化相關係數計算完成。步驟3所述從外部RAM讀入新一行的實時圖數據到相應的內部RAM緩衝塊中，為第一行相關係數計算完成後，讀入一行新的實時圖數據覆蓋不用的實時圖RAM塊數據，在後續各行計算時需要通過時序控制模塊重新切換多路選通開關使模板圖RAM緩衝塊輸出與實時圖RAM緩衝塊輸出順序變化對應。同時該新一行實時圖數據讀入到實時圖數據緩衝RAM中覆蓋已經無效的數據。步驟3中所述在讀入實時圖新一行數據時，同時由前述方式相應的計算出當前行第1列的實時圖灰度值總和的值，後續列實時圖灰度值總和亦是按前述方式依次計算得出。步驟3中所述在讀入實時圖新一行的數據時，此時會由前述方式相應的計算出當前行第1列的實時圖灰度值平方總和的值，後續列實時圖灰度值平方總和亦是按前述方式依次計算得出。步驟4所述計算出後續各行歸一化互相關係數，是指計算實時圖像第2行至第K-M+1行歸一化相關係數，第一行相關係數計算完成後，依次讀入一行新的實時圖數據覆蓋不用的實時圖RAM緩衝塊數據和對應的實時圖數據緩衝RAM中的數據，並且通過時序控制模塊重新選擇模板圖RAM緩衝塊輸出多路選通開關使其與之對應，這樣相當於模板圖像在待匹配圖像中下移一行，然後按照步驟2和步驟3方式進行計算，依次得到每行的歸一化相關係數。本發明還提出了一種基於歸一化相關係數的模板匹配高速並行方法的裝置，該裝置是由高速相關運算器10、模板圖實時圖數據存儲器9、結果存儲器11和微處理器37組成，高速相關運算器10與模板圖實時圖數據存儲器9、結果存儲器11、微處理器37相連，模板圖實時圖數據存儲器9、結果存儲器11也與微處理器37相連。所述的高速相關運算器10由歸一化相關係數計算模塊36、外部通信接口模塊7以及時序控制模塊8組成。歸一化相關係數計算模塊36主要用於歸一化相關係數的計算。外部通信接口模塊7主要通過寄存器與處理器進行參數輸入輸出、指令輸入、狀態查詢輸出。時序控制模塊8主要基於上述步驟控制整個歸一化相關係數計算的工作流程，它與各個模塊中的RAM的地址及控制線、選通開關的選通地址、使能端寄存器的使能端相連。模板圖實時圖數據存儲器9、結果存儲器11分別存儲原始圖像數據以及運算結果，微處理器37由高速相關運算器10的外部通信接口模塊7通過寄存器訪問的方式進行參數輸入輸出、指令輸入和狀態查詢輸出，從而命令高速相關運算器10進行相應的操作，同時也進行原始圖像數據的準備工作。高速相關運算器10把結果存儲到結果存儲器11中，並且從模板圖實時圖數據存儲器9中讀取數據。高速模板匹配裝置中高速相關運算器10的歸一化相關係數計算模塊36包括模板圖灰度值求和模塊2，模板圖灰度值平方求和模塊1，實時圖灰度值求和模塊4、實時圖灰度值平方求和模塊5、實時圖模板圖灰度值乘積求和模塊3和後續計算模塊6。模板圖灰度值求和模塊2由一個累加器14組成，模板圖灰度值平方求和模塊1由一個平方運算模塊12和一個累加器13相連而成。實時圖灰度值求和模塊4由與實時圖灰度值平方求和模塊5共用的實時圖數據緩衝RAM21、第1列累加模塊24、減法器22、累加器23和加法器組成。實時圖灰度值平方求和模塊5由與實時圖灰度值平方求和模塊4共用的實時圖數據緩衝RAM21、第1列累加模塊28、平方運算模塊26、27、38、減法器25、累加器29和加法器組成。實時圖模板圖灰度值乘積求和模塊3由實時圖RAM緩衝塊20、模板圖RAM緩衝塊15、多路選通開關16、乘法器17、並加模塊18和累加器19組成。後續計算模塊由乘法器、加、減法器和分子分母定點浮點轉換模塊(30、31)、分母方根運算模塊（33、34）、浮點除法運算模塊32組成。高速模板匹配裝置工作流程為：首先微處理器37把原始模板圖和實時圖數據存入模板圖實時圖數據存儲器9中，然後向高速相關運算器10輸入圖像的尺寸參數，而後輸入啟動命令啟動歸一化相關運算。在運算過程中通過寄存器訪問的方式查詢運算的進程狀態。在運算完成以後，微處理器37會從高速相關運算器10收到完成的中斷信號，為可靠起見，微處理器37進一步查詢高速相關運算器10的完成標誌，在確保完成以後從結果存儲器讀取歸一化相關係數計算結果進行後續處理工作。高速模板匹配裝置中所包含的高速相關運算器可以利用FPGA實現，也可利用VLSI實現。高速相關運算器中實時圖像以及模板圖像的行數和列數都是可以由外部微處理器輸入的可變的參數，而最終實現的並行通道數目，包括內部實時圖和模板圖RAM緩衝塊的數目，是由任務要求決定的最大的行數。本發明的有益效果：1、本發明的實現方法通過合理、精細的設計，有效地減少了系統邏輯資源消耗，加快了運行速度，從而降低了功耗。2、本發明縮短了布線路徑，提高了FPGA內核所能達到的最大運行速度。3、本發明降低了對外部微處理器的要求，並且該實現縮小了系統的體積。附圖說明圖1是基於歸一化相關係數的模板匹配高速並行實現方法的原理結構框圖。圖2是基於歸一化相關係數的模板匹配高速並行實現方法的工作流程圖。圖3是累加器的結構圖。圖4是圖1中第1列累加模塊實現原理結構圖。圖5是模板匹配原理示意圖。圖6是(a)累加-並加運算；(b)並加-累加運算。圖7是並加實現結構圖。圖8是基於歸一化相關係數的高速並行模板匹配裝置原理結構框圖。圖9是高速相關運算器的時序仿真波形結果圖。圖10是基於...