基于Normalized Cut的圖像分割及其CUDA并行實(shí)現(xiàn).pdf

1、圖像分割是圖像處理和分析中的重要過程，它的輸出結(jié)果直接影響著后續(xù)的處理效果.基于圖論的圖像分割算法由于有比較完備的數(shù)學(xué)理論基礎(chǔ)，最近獲得了廣泛研究.Normalized Cut是一種平衡的基于圖論的圖像分割方法，不僅擁有其它圖論圖像分割算法的優(yōu)點(diǎn)，并且解決了Min-Cut算法傾向于分割孤立結(jié)點(diǎn)的問題.然而，Normalized Cut存在計(jì)算復(fù)雜度高，分割速度慢等問題.
　　針對該問題，本論文研究利用CUDA并行計(jì)算平臺對Norm

2、alized Cut圖像分割算法進(jìn)行加速，提高算法在實(shí)際應(yīng)用的執(zhí)行速度.主要研究內(nèi)容有:
　　(1)介紹傳統(tǒng)的Normalized Cut圖像分割算法，目的是挖掘可以進(jìn)行并行化的過程，研究并行化算法替代耗時(shí)的串行執(zhí)行過程.
　　(2)在將圖像映射為相似度矩陣時(shí)，論文利用任意兩像素點(diǎn)之間的權(quán)值與其它像素點(diǎn)無關(guān)的特點(diǎn)，啟動(dòng)多個(gè)平行線程，每一個(gè)線程負(fù)責(zé)計(jì)算兩像素點(diǎn)間的權(quán)值，這種方法加速相似矩陣計(jì)算.
　　(3)利用并行規(guī)約算

3、法替代傳統(tǒng)的數(shù)組求和，設(shè)計(jì)一種高速并行矩陣乘法替代串行的矩陣乘法，由于數(shù)組求和和矩陣乘法在Normalized Cut算法中出現(xiàn)頻率高，提高這兩種算法的執(zhí)行性能會(huì)顯著地提高整體算法的效率.
　　(4)在求解矩陣特征值階段，論文改進(jìn)了傳統(tǒng)的二分法(Bisection)，使其平行地計(jì)算同層區(qū)間結(jié)點(diǎn)的子區(qū)間結(jié)點(diǎn).求解矩陣特征值是整個(gè)算法較耗時(shí)的過程之一，并行化求解矩陣特征值會(huì)對提高整體算法的性能有重要意義.
　　(5)實(shí)驗(yàn)結(jié)果證實(shí)