【正文】 性聲明 本人所呈交的畢業(yè)論文（設(shè)計(jì)） 是我在導(dǎo)師的指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。 ：任務(wù)書、開題報(bào)告、外文譯文、譯文原文（復(fù)印件）。 第 3～ 6 周 ： 畢業(yè)設(shè)計(jì)開題報(bào)告、文獻(xiàn)綜述 第 7 周 ： 總體設(shè)計(jì)，完成方案的選擇 第 8～ 9 周 ： 確定數(shù)據(jù)模型，算法實(shí)現(xiàn) 第 10～ 11 周 ： 基本算法驗(yàn)證、編程實(shí)現(xiàn) 第 12～ 13 周 ： 論文撰寫。一般認(rèn)為是有 Wilson Markle 1970年發(fā)明，最初用于處理阿波羅登月計(jì)劃獲取的月球影像。這是短程線距離能夠放映亮度變化、進(jìn)而可以用來進(jìn)行顏色擴(kuò)展的現(xiàn)實(shí)基礎(chǔ)。其中第一種情況應(yīng)用最為廣泛。不同于單幀圖像彩色化，多幀彩色化的關(guān)鍵是要充分利用相鄰幀的處理結(jié)果。 像素間短程線距離越小，其 間 的顏色就越相近。 圖像臺(tái)成是給定環(huán)境光信息 (光譜能量分布 )及前景與背景信息 (物體的幾何形狀、位置、表面的反射率分布函數(shù) )條件下 ， 計(jì)算所期望的場(chǎng)景圖像的顏色 。雖然這類圖像本身沒有顏色，但為了使圖像更便于觀察，常根據(jù)圖像灰度添加 不同的顏色以突出細(xì)節(jié)。這類彩色處理方式稱為“假彩色”（ false colofization） . 關(guān)于假彩色這個(gè)術(shù)語，學(xué)術(shù)界對(duì)其解釋不盡相同。光對(duì)人眼引起的視覺效果可以用色調(diào) (hue)、飽和度 (saturation)及亮度 (brightness)三個(gè)參量來表示，稱為顏色的三要素。根據(jù)亮度感覺的強(qiáng)弱，從最明亮到最暗可以分為三個(gè)水平 :白 — 高亮度端的非彩色覺 ； 黑 — 低亮度端的非彩色覺 ； 灰— 介于白與黑之間的中 間層次亮度感覺。在計(jì)算機(jī)圖像處理軟件和圖形處理軟件的色彩管理系統(tǒng)中， RGB 色彩空間是數(shù)字照相機(jī)、掃描儀、顯示器所使用的顏色系統(tǒng)，是一個(gè)與設(shè)備相關(guān)的顏色空間。 RGB 到 YIQ 的變換關(guān)系為 ???????????????????????????????????BGRQIY3 1 2 1 3 2 7 9 1 1 8 9 （ ） 利用人的視覺系統(tǒng)對(duì)亮度變化比對(duì)色調(diào)和飽和度變化更敏感這一特性， YIQ基于最短路徑的圖像著色 9 標(biāo)準(zhǔn)中表示 Y 時(shí)分配較大的帶寬 (指數(shù)字顏色所用比特?cái)?shù) )，而在表示 I、 Q 時(shí)可以采用較小的帶寬。在圖像處理和計(jì)算機(jī)視覺中大量算法都可在 HSI 色彩空間中方便地使用，它們可以分開處理而且是相互獨(dú)立的。實(shí)現(xiàn)亮色分離就可以對(duì)顏色的亮度和色度進(jìn)行單獨(dú)處理，這為一些圖像處理問題帶來極大便利。因此，從廣義上講，最短路徑算法就是從網(wǎng)絡(luò)中找出兩個(gè)點(diǎn)之間最小阻抗路徑的算法。 (a)圖 1 4 3 2 5 2 4 8 5 3 4 1 基于最短路徑的圖像著色 12 0 2 3 4 6 (b)圖最短路徑 圖 最短路徑的基本思路 為了解決最短路徑問題，首先應(yīng)根據(jù)要求選取一種量度標(biāo)準(zhǔn)。 1)假設(shè)用帶權(quán)的鄰接矩陣 cost 來表示一個(gè)帶權(quán)圖， ],[cos jit 表示弧 iV ， jV 上的權(quán)值。 最短路徑的基本方法 傳統(tǒng)的利用 Dijkstra 算法來實(shí)現(xiàn)圖中任意結(jié)點(diǎn)之間的最短路徑查找 ， 其基本思想就是依次以圖中各個(gè)結(jié)點(diǎn)為起點(diǎn)利用 Dijkstra 算法計(jì)算出最短路徑 ， 這樣循環(huán) n 次即可得到圖中任意結(jié)點(diǎn)之間的最短路 ，而每 步都是一個(gè)簡(jiǎn)單的重復(fù)過程 。 7 9 如 A 入度為 0， A 執(zhí)行完 3） ,4） 步后的圖示 B C D A B C D 基于最短路徑的圖像著色 15 2. 利用結(jié)點(diǎn)出度信息查找 基于結(jié)點(diǎn)出度信息查找圖中各結(jié)點(diǎn)間的最短路徑的基本思想是 ： 當(dāng)某結(jié)點(diǎn)的出度為 0時(shí) ， 從該結(jié)點(diǎn)出發(fā)到圖中任何一個(gè)結(jié)點(diǎn)都是不可達(dá)的 。 所以 ， 可知 B→D 的最短路徑必為 B， D； 同理可以推出 B→C 的最短路徑必為 B， D， C。 MATLAB 語言已是當(dāng)今國際上科學(xué)界最具影響力、也是最有活力的軟件。 MATLAB 語言的功能 也 越來越強(qiáng)大，不斷使用的要求提出新的解決方法。 2) 直觀靈活的語言 MATLAB 不僅僅是一套打包好的函數(shù)庫，同事也是一種高級(jí)的、面向?qū)ο蟮木幊陶Z言，使用 MATLAB 可事半功倍的開發(fā)自己的程序。 現(xiàn)將 MATLAB 中進(jìn)行編寫程序和調(diào)試程序的步驟說明如下： （ 1）編輯： 程序從鍵盤上輸入后要修改輸入的錯(cuò)誤。其核心工具箱又可分為兩大類：功能性工具箱主要用來擴(kuò)充其符號(hào)計(jì)算功能、圖示建模仿真功能、文字處理功能以及與硬件實(shí)時(shí)交互功能。 圖像彩色化是進(jìn)行影像彩色化處理的基礎(chǔ)。初始情況下，通過手工的方式給部分區(qū)域著色，目標(biāo)就是利用這些初始條件給未著色的像素賦予合理的顏色，根據(jù)假設(shè)可知，未著色的像素的顏色應(yīng)該和到該像素灰度變化最平緩的已著色像素的顏色一致。對(duì)于兩個(gè)像素之間的任意一條路徑，求出每?jī)蓚€(gè)相鄰像素之間的灰度差，然后找到其中最大的那一個(gè)，來表示該路徑的灰度變化程度，稱之為該路徑的不平度。迭代動(dòng)態(tài)規(guī)劃算法就是利用迭代方式來求解動(dòng)態(tài)規(guī)劃遞歸方程。 迭代動(dòng)態(tài)規(guī)劃算法首先設(shè)定一個(gè)活性像素集合 APS(Active Pixel Set)表示要向外進(jìn)行顏色擴(kuò)展的像素集合，其初始元素即涂色區(qū)域 n? (n=1,2,…,N )的邊界。 圖 為彩色化程序流程圖。 在這半年的時(shí)間里我感受很深。利用最短路徑盡量實(shí)現(xiàn)對(duì)圖像的最快著色。 從課題的選擇到課題的研究及論文的完成都是在張老師的悉心指導(dǎo)和幫助下完成的，在這一過程中，我碰到過很多問題，曾多次向張老師請(qǐng)教，張老師都很有耐心的為我一一解答，張老師給了我很多的幫助，讓我克服了很多的困難，張老師為人樸實(shí)，思維敏捷，知識(shí)淵博都深深的感染了我，我覺得我應(yīng)該向張老師學(xué)習(xí)。 基于最短路徑的圖像著色 31 參考文 獻(xiàn) [1]Anany （ 潘彥譯 ） .北京 ： 清華大學(xué)出版社 , 2020 [2]殷人昆 ,陶永雷 .數(shù)據(jù)結(jié)構(gòu) （ 用面向?qū)ο蠓椒ㄅc C++描述 ） .北京 ： 清華大學(xué)出版社 ,2020 [3]龍光正 ,楊建軍 .改進(jìn)的最短路算法 [J].系統(tǒng)工程與電子技術(shù) ,2020,24（ 6）：106108 [4]陸鋒 .最短路徑算法 ： 分類體系與研究進(jìn)展 [J].測(cè)繪學(xué)報(bào) ,2020,30（ 3）：269275 [5]王杰臣 ,楊得志 ,張偉 .最短路徑問題的一種改進(jìn)算法 [J].解放軍測(cè)繪學(xué)院報(bào) ,1999,16（ 4）： 282285 [6]王曉東 ,陳國龍 ,林柏鋼 .網(wǎng)絡(luò)最短路問題的改進(jìn)算法 [J].小型微型計(jì)算機(jī)系統(tǒng) ,2020,23(9):10831087 [7]羅理 ,王鋒 .基于 Dijkstra 的最短路徑改進(jìn)算法 .昆明理工大學(xué)：信息工程與自動(dòng)化學(xué)院湖北汽車工業(yè)學(xué)院學(xué)報(bào) ,007,21（ 2） [8]樂陽 ,龔健雅 .Dijkstra 最短路徑算法的一種高效率實(shí)現(xiàn) .武漢測(cè)繪科技大學(xué)學(xué)報(bào) ,199909,24(3) [9]劉勇 .關(guān)于彩色化灰度圖像的算法研究及實(shí)現(xiàn) .山東大學(xué)碩士學(xué)位論文 , 20200508 [10]董兆華 .給灰度圖像著色 .浙江大學(xué) CADamp。因此，在一幅黑白圖像中檢測(cè)不到的信息，經(jīng)圖像著色增 強(qiáng)后可較容易地檢測(cè)出來。經(jīng)過著色后的圖像不僅看起來漂亮而且醒目。此循環(huán)往復(fù)，直至 APS 為空。動(dòng)態(tài)規(guī)劃遞歸方程如果用迭代方式來求解，能夠很自然地避免 重復(fù)計(jì)算。根據(jù)這兩個(gè)條件，我們選擇了函數(shù) )ln()( dd ??? 。當(dāng)所有未著色像素都進(jìn)行了這樣的彩色化過程后，整副圖像的彩色化就完成了。根據(jù)上面的這些公式，像素 s 到已經(jīng)著色區(qū)域 ? 的不平度公式（ ）。由于人眼對(duì)灰度的敏感度遠(yuǎn)不如顏色 ， 對(duì)于一些灰度圖像如：紅外照片、科學(xué)圖片、磁共振成像等，我們希望把灰度圖像變成彩色圖像以增強(qiáng)視覺效果。如果執(zhí)行結(jié)果正確，說明程序已經(jīng)調(diào)試完畢；如果不符合用原來的語意，就需要進(jìn)行調(diào)試，從而修改原來的程序。 5) 用戶使用方便 MATLAB 語言靈活、方便，其調(diào)試程序手段豐富，調(diào)試速度快。 MATLAB 給用戶提供的是最直觀、最簡(jiǎn)潔的開發(fā)環(huán)境。它可以將使用者從煩瑣、無謂的底層編程中解放出來，把有限的寶貴時(shí)間更多地花在解決問題中，這樣無疑會(huì)提高工作效率。 MATLAB 可以進(jìn)行矩形運(yùn)算、繪制函數(shù)和數(shù)據(jù)、實(shí)現(xiàn)算法、創(chuàng)建用戶界面、連接其他編程語言的程序等，主要應(yīng)用于恭喜橫計(jì)算、控制設(shè)計(jì)、信號(hào)處理與通信、圖像處理、信號(hào)檢測(cè)、金融建模設(shè)計(jì)與分析等領(lǐng)域。 不論是從入度還是從出度著手都應(yīng)該考慮出入度為 1 的多個(gè)結(jié)點(diǎn) ， 并注意其前驅(qū)結(jié)點(diǎn)的順序 。 如圖 所示 ， A 的入度為 0， 當(dāng)求出了以 A 點(diǎn)出發(fā)到圖中其他各點(diǎn)的最短路徑后 ， 再求其他結(jié)點(diǎn)間的最短路徑時(shí) ， 就可以將結(jié)點(diǎn) A 刪除 ， 并把其他結(jié)點(diǎn)到 A 結(jié)點(diǎn)的最短路徑記為無窮大即可 。如果 ][],[c os][ kdi sstkjtjdi st ?? 則修改 ][kdist 為 ],[c os][][ kjtjdi stkdi st ?? 4)重復(fù)操作 2)， 3)共 n1 由此求得從 oV 到圖上其余各個(gè)結(jié)點(diǎn)的最短路徑。使用這一量度標(biāo)準(zhǔn)，假定已經(jīng)構(gòu)造了 n 條最短路徑，則下面要構(gòu)造的路徑應(yīng)該是下一條最短的最小長度路徑。 圖 (a)給出了一個(gè)具有五個(gè)頂點(diǎn)的有向圖，各邊上的數(shù)即為長度，假設(shè)源頂點(diǎn) s為 1，從頂點(diǎn) 1出發(fā)到各頂點(diǎn)的最短路徑按長度順序列在圖 (b)中，每條路徑前的數(shù)字為路徑長度。 隨著社會(huì)的不斷進(jìn)步，最短路徑算法在人們的日常生活中顯得越來越重要。顏色屬性空間的顯著特征就是亮色分離。 HSI 色彩空間可以用一個(gè)圓錐空間模型來描述，此圓錐模型 比較復(fù)雜，但確能把色調(diào)、亮度及飽和度的變化情形表現(xiàn)得很清楚。 3) YIQ 類色彩空間 YIQ 是北美 NTSC 電視系統(tǒng)中采用的色彩系統(tǒng)， Y 是指顏色的亮度， I 和 Q分別是色調(diào)和飽和度。三基色原理認(rèn) 為自然界中的絕大多數(shù)的彩色光能分解為互相獨(dú)立的紅 (red)、綠 (green)、藍(lán) (blue)三種基色光 ； 反之用互相獨(dú)立的紅、綠、藍(lán)三種基色以不同的比例混合，可模擬出自然界中絕大多數(shù)的顏色。 3) 亮度 亮度是區(qū)分明暗層次的非彩色覺的視覺屬性，這種明暗層次決定于光刺激能量水平的高低。 顏色與色彩空間 牛頓認(rèn)為 :“準(zhǔn)確地說，光線是沒有顏色的，它所擁有的只是引起這樣或那樣顏色知覺的能量分布 。 2) 假彩色 原本彩色的場(chǎng)景由于成像條件所限造成顏色被動(dòng)丟失，即傳統(tǒng)意義上的黑白照片、黑白電影等。 這類黑白影像由成像機(jī)理決定了其記錄的內(nèi)容本身并沒有顏色，甚至并非常規(guī)意義上的圖像，是表示非可見電磁波穿透特性的數(shù)據(jù)顯示。 圖像著色 彩色圖像的合成與分析分別是計(jì)算機(jī)圖像學(xué)和計(jì)算機(jī)視覺研究的主要課題之一 。 論文內(nèi)容 本文的內(nèi)容是利用短程線的方法實(shí)現(xiàn)灰度圖像的著色。對(duì)處理效率和處理效果的要求同各類圖像處理的是一致的，即力求以最小的處理代價(jià)獲得最優(yōu)的處理結(jié)果。最短路徑問題要解決的就是求加權(quán)圖 G=V,E,W中兩給定頂點(diǎn)之間的最短路徑，實(shí)際上就是根據(jù)網(wǎng)絡(luò)的鏈路代價(jià)計(jì)算一對(duì)節(jié)點(diǎn)之間的最小代價(jià)路徑。雖然像素亮度變化與顏色變化并非嚴(yán)格的一一對(duì)應(yīng)，但二者之間聯(lián)系緊密：亮度劇烈變化的地方一般對(duì)應(yīng)顏色的巨變，亮度平緩變化貨保持恒定通常顏色變化程度也不明顯。最后編程運(yùn)用 Matlab 軟件 實(shí)