【導(dǎo)讀】據(jù)我所知，除文中已經(jīng)注明引用的內(nèi)容外，本論文（設(shè)計）不包含其他個。人已經(jīng)發(fā)表或撰寫過的研究成果。對本論文（設(shè)計）的研究做出重要貢獻的個人和集。體，均已在文中作了明確說明并表示謝意。計）的電子版和紙質(zhì)版。有權(quán)將論文（設(shè)計）用于非贏利目的的少量。復(fù)制并允許論文（設(shè)計）進入學(xué)校圖書館被查閱。保密的論文（設(shè)計）在解密后適用本規(guī)。文科類論文正文字?jǐn)?shù)不少于萬字。合國家技術(shù)標(biāo)準(zhǔn)規(guī)范。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準(zhǔn)用徒。色問題轉(zhuǎn)化為混色問題求解。2．用matlab語言編程實現(xiàn)基于基于最短路徑離的黑白圖像著色算法。3．完成畢業(yè)論文。論文初審，定稿。也一直是圖像處理中一個活躍的、有挑戰(zhàn)性的研究課題。

　　

【正文】 于最短路徑的圖像著色 23 是為此而定義的。對于兩個像素之間的任意一條路徑，求出每兩個相鄰像素之間的灰度差，然后找到其中最大的那一個，來表示該路徑的灰度變化程度，稱之為該路徑的不平度。連接兩個像素所有路徑的不平度的最小值定義為這兩個像素之間的不平度，它表示的是兩個像素之間的灰度變化的程度，這正是假設(shè)中進行顏色傳遞的約束機制。 灰度變化越大說明這兩個像素之間顏色的一致性越小，反之則說明兩個像素之間的顏色一致性越大，而且不平度的大小與路徑的長短無關(guān)，由此可見不平度很適合作為顏色擴展的約束機制。 為了使邊界附近的結(jié)果更加平滑，我們也采用了顏色混合的方法。所謂顏色混合就是對于未著色像素，把到達該像素的不平度最小的 3 個著色區(qū)域顏色輔以一個關(guān)于不平度的函數(shù)進行加權(quán)求和，從而得到最終的顏色。對于加權(quán)函數(shù)的選取需要符合如下條件 ： ??? )(lim0 dd ? （ ） 0)(lim1 ?? dd ? （ ） 其中 d 表示不平度。根據(jù)這兩個條件，我們選擇了函數(shù) )ln()( dd ??? 。 3) 基于不平度的顏色混合彩色化算法的實現(xiàn) 在圖像彩色化中要計算每個未涂色像素與涂色區(qū)域的不平度，該過程可以利用迭代動態(tài)規(guī)劃算法 （ interactive dynamic programming algorithm） 來實現(xiàn)。迭代動態(tài)規(guī)劃算法就是利用迭代方式來求解動態(tài)規(guī)劃遞歸方程。 動態(tài)規(guī)劃 （ principle of optimality） 是采 用最優(yōu)原則來建立用于計算最優(yōu)解的遞歸式。所謂最優(yōu)原則，即不管前面的策略如何，此后的決策必須是基于當(dāng)前狀態(tài) (由上一次決策產(chǎn)生 )的最優(yōu)決策。在得到最優(yōu)解的遞 歸式之后，需要執(zhí)行回（ traceback）以構(gòu)造最優(yōu)解。如果不能有效地避免重復(fù)計算， 遞歸程序的復(fù)雜性將非?？捎^。如果可以在遞歸程序設(shè)計中解決重復(fù)計算問題，那么計算的復(fù)雜性將急劇下降 。動態(tài)規(guī)劃遞歸方程如果用迭代方式來求解，能夠很自然地避免 重復(fù)計算。盡管迭代程序與避免重復(fù)計算的遞歸程序有相同的復(fù)雜性，但迭代程序 不要附加的遞歸?？臻g，因此比避免重復(fù)計算的遞歸程序更快。 迭代動態(tài)規(guī)劃算法首先設(shè)定一個活性像素集合 APS(Active Pixel Set)表示要向外進行顏色擴展的像素集合，其初始元素即涂色區(qū)域 n? (n=1,2,…,N )的邊界。 基于最短路徑的圖像著色 24 被傳遞像素的不平度（短程線）改變？ APS 中的像素 t 向其 8鄰域的像素擴展，把它的不平度與他們之間的灰度差比較之后傳遞給相鄰像素，若與其相鄰的像素 )8~1( ?ipi 所對應(yīng)的最小的 3個不平度發(fā)生了變化，就把 ip 添加到 APS 中；當(dāng)根據(jù) t 處理完相鄰像素的不平度之后，將 t 從 APS 中刪除，循環(huán)往復(fù)直至 APS 為空。算法的流程圖如圖 圖 算法流程圖 初始化 APS空？ 傳遞不平度（短程線） 將原像素從 ASP 中去除 原始圖像 部分著色圖像 顏色混合 輸出彩色圖像 將被傳遞像素加入 APS 基于最短路徑的圖像著色 25 4) 基于不平度的顏色彩色化快速方法的實現(xiàn) 本方法在算法實現(xiàn)方面還是采用了迭代動態(tài)規(guī)劃算法。設(shè)定一個活性像素集合 APS(Active Pixel Set)表示要向外進行顏色擴展的像素集合，其初始元素即涂色區(qū)域 n? (n=l,2,…,N )的邊界。 APS 中的像素 t 向其 8鄰域的像素擴展，把它的不平度與它們間的灰度差比較之后把其中小的值傳遞給相鄰像素，作為該像素的不平度。若與其相鄰的像素 )8~1( ?ipi 所對應(yīng)平度發(fā)生了變化，就把 ip 添加到 APS 中 ； 當(dāng)根據(jù) t 處理完 相鄰 像素的不平度之后，將 t 從 APS 中刪除。此循環(huán)往復(fù)，直至 APS 為空。之后在對 顏色 信息進行區(qū)域適應(yīng)性的平滑，消除圖像邊緣處的著色誤差之后就能得到最后的彩色結(jié)果。 圖 為彩色化程序流程圖。 基于最短路徑的圖像著色 26 圖 彩色化程序流程圖 基于最短路徑的圖像著色的結(jié)果 圖像著色的目的 使處理后圖像的某些內(nèi)容更加醒目 ,利用最短路徑的方法給被傳遞像素的不平度（短程線）改變？ 原始圖像 部分著色圖像 初始化 APS 空？ 將被傳遞像素加入 APS 將元像素從 APS中去除 邊緣處理 輸出彩色圖像 是 否 是 否 傳遞不平度（短程線） 基于最短路徑的圖像著色 27 黑白圖像著色是為了可以更快的得到著色后的圖像。下圖是兩幅黑白圖像在利用本文所介紹的基于最短路徑的圖像著色方法在 MATLAB 中實現(xiàn)的著色圖像。圖 和圖 分別是兩幅黑白圖像，圖 和圖 分別是對兩幅黑白圖像進行局部顏色涂抹，圖 和圖 分貝是對兩幅黑白圖像經(jīng)過著色后的彩色圖像。 圖 黑白圖像 Lilies 圖 對 Lilies 進行局部顏色涂抹 基于最短路徑的圖像著色 28 圖 對 Lilies 著色后的彩圖 圖 Lilies 的黑白圖像，為了使圖像可以醒目的呈現(xiàn)在大家眼前，對 Lilies 進行著色，首先這幅圖需要著色的部分有花朵和葉片，然后對它們進行局部顏色涂抹得到圖 ，然后根據(jù)灰度值的不同，每種顏色向其相同或相近的灰度值擴展，最終得到彩色圖像 。 圖 黑白圖像 Arch 基于最短路徑的圖像著色 29 圖 對 Arch 進行局部顏色涂抹 圖 對 Arch 著色后的彩圖 Arch 與 Lilies 采用的一樣的方式最后得到彩色圖像 。經(jīng)過著色后的圖像不僅看起來漂亮而且醒目。 基于最短路徑的圖像著色 30 結(jié)束語 轉(zhuǎn)眼間這次的 畢業(yè)設(shè)計已經(jīng)接近尾聲，作為一個本科生的畢業(yè)設(shè)計，由于 經(jīng)驗的匱乏，難免有許多考慮不周全的地方，如果沒有導(dǎo)師的督促指導(dǎo) ，想要完成這個設(shè)計是 很有難度 的。 在這半年的時間里我感受很深。從這次的畢業(yè)設(shè)計中我學(xué)到了很多東西。 最短路徑在現(xiàn)實生活中越來越重要，所謂最短路徑就是網(wǎng)絡(luò)中兩點之間距離最短的路徑，這里講的距離可以是實際的距離，也可以引申為其它的度量，如時間、運費、流量等。因此，最短路徑就是為了能快速、高效的實現(xiàn)各種需要的一種方法。 圖像著色的目的是使處理后圖像的某些內(nèi)容更加醒目。人眼對彩色的分辨能力遠遠大于對黑白灰度的分辨能力：對一般的觀察者來說，通常只能分辨十幾級灰度，而人眼可分辨出上千種彩色的色調(diào)和強度。因此，在一幅黑白圖像中檢測不到的信息，經(jīng)圖像著色增 強后可較容易地檢測出來。 圖像著色的方法有很多種，例如：基于過度分割的圖像彩色化，基于拉普拉斯方程的圖像彩色化等，本論文是從最短路徑的方向研究圖像著色。利用最短路徑盡量實現(xiàn)對圖像的最快著色。 這次畢業(yè)設(shè)計在老師的悉心教導(dǎo)下讓我充分體會到了圖像著色的重要性。在現(xiàn)實生活中，彩色圖像無處不見，已經(jīng)成為人們不可或缺的一部分。在這次畢業(yè)設(shè)計過程中我學(xué)到了什么事最短路徑以及什么是圖像著色。也學(xué)到了怎樣利用最短路徑的方式進行圖像著色。我相信我在這次畢業(yè)設(shè)計中所學(xué)到東西在我以后的生活中會有很大的幫助。 基于最短路徑的圖像著色 31 參考文 獻 [1]Anany （ 潘彥譯 ） .北京 ： 清華大學(xué)出版社 , 2020 [2]殷人昆 ,陶永雷 .數(shù)據(jù)結(jié)構(gòu) （ 用面向?qū)ο蠓椒ㄅc C++描述 ） .北京 ： 清華大學(xué)出版社 ,2020 [3]龍光正 ,楊建軍 .改進的最短路算法 [J].系統(tǒng)工程與電子技術(shù) ,2020,24（ 6）：106108 [4]陸鋒 .最短路徑算法 ： 分類體系與研究進展 [J].測繪學(xué)報 ,2020,30（ 3）：269275 [5]王杰臣 ,楊得志 ,張偉 .最短路徑問題的一種改進算法 [J].解放軍測繪學(xué)院報 ,1999,16（ 4）： 282285 [6]王曉東 ,陳國龍 ,林柏鋼 .網(wǎng)絡(luò)最短路問題的改進算法 [J].小型微型計算機系統(tǒng) ,2020,23(9):10831087 [7]羅理 ,王鋒 .基于 Dijkstra 的最短路徑改進算法 .昆明理工大學(xué)：信息工程與自動化學(xué)院湖北汽車工業(yè)學(xué)院學(xué)報 ,007,21（ 2） [8]樂陽 ,龔健雅 .Dijkstra 最短路徑算法的一種高效率實現(xiàn) .武漢測繪科技大學(xué)學(xué)報 ,199909,24(3) [9]劉勇 .關(guān)于彩色化灰度圖像的算法研究及實現(xiàn) .山東大學(xué)碩士學(xué)位論文 , 20200508 [10]董兆華 .給灰度圖像著色 .浙江大學(xué) CADamp。CG 國家重點實驗室 ,20200812 [11]滕 升華 ,諶安軍 ,鄒謀炎 等 .一種改進的基于過度分割的圖像彩色化方法 .電信息學(xué)報 ,2020,28(7) [12]鄭志航 .數(shù)字電視原理與應(yīng)用 .北京：中國廣播電視出版社 ,2020： 1314 [13]李志永 .黑白影像的彩色化研究 信號與信息處理 ： [博士 ].中國科學(xué)院電子學(xué)研究所 ,2020 [14]朱秀昌 ,劉峰 ,胡棟 .數(shù)字圖像處理與圖像通信 .北京：北京郵電大學(xué)出版社 ,2020： 9093 [15]阮秋琦 .數(shù)字圖像處理學(xué) .北京：電子工業(yè)出版社 ,2020： 212214 [16]劉慶祥 ,蔣天發(fā) .彩色與灰度圖像間轉(zhuǎn)換算法的研究 .武漢理工大學(xué)學(xué)報 (交基于最短路徑的圖像著色 32 通科學(xué)與工程版 ),2020,3 [17]姚敏 .數(shù)字圖像處理 .機械工業(yè)出版社 ,20200101 [18]孫屹 .MATLAB 通信仿真開發(fā)手冊 .國防工業(yè)出版社 ,2020 [19]胡偉 ,秦開懷 .高分辨率灰度圖像的快速著色 .清華大學(xué)計算機科學(xué)與技術(shù)系計算機學(xué)報 ,2020,5 [20]Guillermo partial differential equations and image Univercity Press,2020 [21]張德豐 ,雷小平 ,周燕 .詳解 MATLAB 圖形繪制技術(shù) .北京：電子工業(yè)出版社 , 202005 基于最短路徑的圖像著色 33 致謝 感謝我的導(dǎo)師張可為老師，他嚴(yán)謹(jǐn)細致、一絲不茍的作風(fēng)一直是我工作、學(xué)習(xí)中的榜樣 ， 他循循善誘的教導(dǎo)和不拘一格的思路給予我無盡的啟迪。 從課題的選擇到課題的研究及論文的完成都是在張老師的悉心指導(dǎo)和幫助下完成的，在這一過程中，我碰到過很多問題，曾多次向張老師請教，張老師都很有耐心的為我一一解答，張老師給了我很多的幫助，讓我克服了很多的困難，張老師為人樸實，思維敏捷，知識淵博都深深的感染了我，我覺得我應(yīng)該向張老師學(xué)習(xí)。 在此還要感謝一直教育我的湖南工程學(xué)院的老師們，是你們讓我學(xué)習(xí)到了很多的知識，也教會我如何去為人處 事。你們默默地給了我關(guān)心和幫助，你們無私的奉獻讓我們感到無限的溫暖。 許鳳英 2020 年 6 月