資源描述：
《基于圖論的圖像分割和并行化研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、劣臻交萬方數(shù)據(jù)碩士學(xué)位論文基于圖論的圖像分割和并行化研究Researchofimagesegmentationandparailelizationbasedongraphtheory作者：劉雅坤導(dǎo)師：于雙元北京交通大學(xué)2014年3月萬方數(shù)據(jù)學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解北京交通大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定。特授權(quán)北京交通大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，提供閱覽服務(wù)，并采用影印、縮印或掃描等復(fù)制手段保存、匯編以供查閱和借閱。同意學(xué)校向國家有關(guān)部門或機(jī)構(gòu)送交論
2、文的復(fù)印件和磁盤。(保密的學(xué)位論文在解密后適用本授權(quán)說明)學(xué)位論文作者簽名：剜刪簽字日期：2，。／中年≥月≯6日土坫；月獬氣亍嘩孫；抑簽期吐丌-jyr【導(dǎo)字，登萬方數(shù)據(jù)中圖分類號(hào)：TP39UDC：004．9學(xué)校代碼：10004密級(jí)：公開北京交通大學(xué)碩士學(xué)位論文基于圖論的圖像分割和并行化研究Researchofimagesegmentationandparallelizationbasedongraphtheory作者姓名：劉雅坤導(dǎo)師姓名：于雙元學(xué)位類別：工學(xué)學(xué)號(hào)：11120464職稱：副教授學(xué)位級(jí)別
3、：碩士學(xué)科專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)研究方向：分布式計(jì)算北京交通大學(xué)2014年3月萬方數(shù)據(jù)致謝本論文的工作是在我的導(dǎo)師于雙元副教授的悉心指導(dǎo)下完成的，于雙元副教授嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度和科學(xué)的工作方法給了我極大的幫助和影響。在此衷心感謝三年來于雙元老師對(duì)我的關(guān)心和指導(dǎo)。于雙元副教授悉心指導(dǎo)我們完成了實(shí)驗(yàn)室的科研工作，在學(xué)習(xí)上和生活上都給予了我很大的關(guān)心和幫助，在此向于雙元老師表示衷心的謝意。于雙元副教授對(duì)于我的科研工作和論文都提出了許多的寶貴意見，在此表示衷心的感謝。在實(shí)驗(yàn)室工作及撰寫論文期間，喬艷茹、雷瑩、婁
4、啟林等同學(xué)對(duì)我論文中的研究工作給予了熱情幫助，在此向他們表達(dá)我的感激之情。另外也感謝家人，他們的理解和支持使我能夠在學(xué)校專心完成我的學(xué)業(yè)。萬方數(shù)據(jù)jE立交道太堂亟±堂僮途塞擅噩摘要圖像分割是數(shù)字圖像處理和計(jì)算機(jī)視覺中重要任務(wù)之一。本文研究的基于圖論譜聚類分割方法是近幾年來的圖像分割領(lǐng)域的一個(gè)新的研究熱點(diǎn)，基于圖論的譜聚類基本思想是將一幅圖像映射成一個(gè)無向加權(quán)圖，將像素點(diǎn)映射為頂點(diǎn)，相鄰的像素之問的視覺信息(比如灰度或距離)的相似度來定義權(quán)值。將圖像按照某種劃分建立特定函數(shù)，當(dāng)函數(shù)達(dá)到最小值就得到圖像
5、的一個(gè)最佳分組。該方法具有高度的靈活性，它提供統(tǒng)一框架處理圖像的灰度、紋理、噪聲，適用于任何數(shù)字圖像。本論文研究的最小最大割集(Min—maxcut)充分體現(xiàn)了基于圖論的譜聚類方法的最優(yōu)準(zhǔn)則，即子圖內(nèi)相似度最大，子圖問相似性最小。將這個(gè)NP的準(zhǔn)則轉(zhuǎn)化為特征方程求解，但是這個(gè)方法存在求解大規(guī)模矩陣的特征向量的復(fù)雜問題，算法隨著圖像尺寸增大效率大大降低。圖像映射為圖構(gòu)建過程中，邊的構(gòu)建方法不再簡單的依據(jù)四鄰域或八鄰域，而以某頂點(diǎn)為中，tS,將半徑r內(nèi)所有頂點(diǎn)與其進(jìn)行關(guān)聯(lián)。相似度計(jì)算函數(shù)的構(gòu)造選用考慮了頂
6、點(diǎn)之問的灰度和距離的高斯函數(shù)。相似度矩陣更真實(shí)反映像素之間的關(guān)系。為了降低最小最大割算法中頂點(diǎn)和邊的數(shù)目，在介紹了分水嶺算法的思想和主要缺陷后，將基于數(shù)學(xué)形態(tài)學(xué)的分水嶺方法引入到最小最大割算法中，提出基于分水嶺的最小最大割算法。首先，利用分水嶺方法圖像預(yù)分割，生成的過分割小區(qū)域轉(zhuǎn)化為無向圖中的頂點(diǎn)，相鄰區(qū)域間的差異轉(zhuǎn)化為邊的權(quán)重，再利用最小最大割算法將小區(qū)進(jìn)行合并操作。基于分水嶺的最小最大割算法既能消除分水嶺的過度分割現(xiàn)象，又能降低圖中邊的數(shù)目，獲得圖像的全局特征，提高最小最大算法分割效率。文中利用
7、基于GPU的CUDA平臺(tái)加速最小最大割算法，減少算法的運(yùn)行時(shí)間。根據(jù)GPU適合處理計(jì)算密度高、計(jì)算邏輯相對(duì)簡單的大規(guī)模數(shù)據(jù)的計(jì)算特性，理論上分析了最小最大割算法加速的可行性。根據(jù)最小最大割算法實(shí)現(xiàn)步驟，設(shè)計(jì)了基于GPU的最小最大割算法。實(shí)現(xiàn)了三對(duì)角矩陣k個(gè)特征值求解加速和其對(duì)應(yīng)k個(gè)特征向量的K—means聚類加速。實(shí)驗(yàn)分析得出基于GPU的最小最大割算法加速比在1．5左右，得出的結(jié)論是大規(guī)模矩陣分塊計(jì)算提高最小最大割算法加速比的主要途徑。關(guān)鍵詞：圖像分割；圖論；最小最大割；并行化分類號(hào)：TP39萬方數(shù)
8、據(jù)韭立蔓繭笪太堂亟±堂僮論塞△墜曼!B△￡至ABSTRACTImagesegmentationplaysanimportantroleindigitalimageprocessingandcomputervision．ImageSegmentationbasedongraphtheoryisaprevalentresearchtopicinrecentlyinternationalimagesegmentationarea．Itsbasicideaistomappin
