圖像處理中塊匹配算法的GPU并行化研究.pdf

1、K近鄰搜索(k-nearest neighbor)作為分類和聚類的一種基本問題被廣泛地應(yīng)用在眾多研究領(lǐng)域。塊匹配算法是 k近鄰搜索在圖像處理領(lǐng)域中的一種具體應(yīng)用。最簡單的塊匹配算法是暴力搜索法,也叫窮舉搜索法。但是該算法極為耗時(shí),塊匹配也經(jīng)常成為圖像處理算法的性能瓶頸。為了提高圖像處理速度,目前常采用近似塊匹配方法達(dá)到減少運(yùn)算量的目的。同時(shí),圖形處理器(GPU)通用計(jì)算也為塊匹配算法加速提供了并行化的方法。本文基于CUDA(Comput

2、e Unified Device Architecture)通用并行計(jì)算架構(gòu),提出了一種并行化友好的近似塊匹配算法,并研究其并行實(shí)現(xiàn)的優(yōu)化技術(shù)。
　　首先,本文提出了一種基于傳播的近似塊匹配算法?；谙噜彽膲K的匹配塊具有相似的信息這一特性,該算法通過初始化和傳播迭代來快速完成匹配。傳播過程將最有可能的匹配塊的信息傳遞給鄰域塊,從而在減少鄰域的塊的運(yùn)算量的同時(shí),使之獲得匹配塊信息。在傳播過程中引入了Jump Flooding方法使之

3、并行化。與目前性能較好的近似塊匹配算法Barnes算法相比,本文算法有著與該算法相近的匹配誤差性能。甚至在某些應(yīng)用環(huán)境下,本文算法匹配誤差性能更優(yōu)。但與Barnes算法相比,本文提出的算法有著顯著的并行友好性,更易于在GPU平臺(tái)下實(shí)現(xiàn)從而獲得更為顯著的加速。在CUDA架構(gòu)下,本文算法相較Barnes算法有5倍以上的加速比。
　　其次,分別在GPU平臺(tái)和CPU平臺(tái)上實(shí)現(xiàn)并優(yōu)化了本文提出的基于Jump Flooding的塊匹配算法。在

4、GPU平臺(tái)上,基于CUDA架構(gòu)實(shí)現(xiàn)此算法,并采用了多種了內(nèi)存訪問優(yōu)化策略來提高算法實(shí)現(xiàn)的性能。在CPU平臺(tái),采用OpenMP的多線程方法并行地實(shí)現(xiàn)該算法。本文比較了GPU和CPU的并行計(jì)算能力與優(yōu)勢。與CPU相比,GPU在實(shí)現(xiàn)大規(guī)模并行算法上有著顯著的優(yōu)勢。
　　本文最后將該塊匹配算法應(yīng)用于去噪和紋理合成中,驗(yàn)證其在應(yīng)用中的有效性。通過改變圖像塊描述子,使用變換域系數(shù)描述塊,將該算法應(yīng)用在BM3D(block-matching a