【正文】 X，B到C的路徑集合為Y。通過一定的定義，把路徑的灰度變化程度進行量化描述。從集合X中挑選出一條路徑，使其滿足該路徑灰度變化最小，同理從集合Y中也挑選出一條這樣的路徑。通過比較得出到達C像素灰度變化最小的路徑，像素C的顏色就取灰度變化最小的路徑另一端的像素顏色。當所有未著色像素都進行了這樣的彩色化過程后，整副圖像的彩色化就完成了。上述方法的關(guān)鍵就是如何定量描述一條路徑的灰度變化程度，“不平度”正是為此而定義的。對于兩個像素之間的任意一條路徑，求出每兩個相鄰像素之間的灰度差，然后找到其中最大的那一個，來表示該路徑的灰度變化程度，稱之為該路徑的不平度。連接兩個像素所有路徑的不平度的最小值定義為這兩個像素之間的不平度，它表示的是兩個像素之間的灰度變化的程度，這正是假設(shè)中進行顏色傳遞的約束機制。灰度變化越大說明這兩個像素之間顏色的一致性越小，反之則說明兩個像素之間的顏色一致性越大，而且不平度的大小與路徑的長短無關(guān)，由此可見不平度很適合作為顏色擴展的約束機制。為了使邊界附近的結(jié)果更加平滑，我們也采用了顏色混合的方法。所謂顏色混合就是對于未著色像素，把到達該像素的不平度最小的3個著色區(qū)域顏色輔以一個關(guān)于不平度的函數(shù)進行加權(quán)求和，從而得到最終的顏色。對于加權(quán)函數(shù)的選取需要符合如下條件： (35) (36)其中d表示不平度。根據(jù)這兩個條件，我們選擇了函數(shù)。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)原則，即不管前面的策略如何，此后的決策必須是基于當前狀態(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=1,2,…,N)的邊界。APS中的像素t向其8鄰域的像素擴展，把它的不平度與他們之間的灰度差比較之后傳遞給相鄰像素，若與其相鄰的像素所對應(yīng)的最小的3個不平度發(fā)生了變化，就把添加到APS中；當根據(jù)t處理完相鄰像素的不平度之后，將t從APS中刪除，循環(huán)往復(fù)直至APS為空。原始圖像部分著色圖像初始化APS空？傳遞不平度（短程線）將被傳遞像素加入APS被傳遞像素的不平度（短程線）改變？將原像素從ASP中去除顏色混合輸出彩色圖像 算法流程圖4) 基于不平度的顏色彩色化快速方法的實現(xiàn)本方法在算法實現(xiàn)方面還是采用了迭代動態(tài)規(guī)劃算法。設(shè)定一個活性像素集合APS(Active Pixel Set)表示要向外進行顏色擴展的像素集合，其初始元素即涂色區(qū)域 (n=l,2,…,N)的邊界。APS中的像素t向其8鄰域的像素擴展，把它的不平度與它們間的灰度差比較之后把其中小的值傳遞給相鄰像素，作為該像素的不平度。若與其相鄰的像素所對應(yīng)不平度發(fā)生了變化，就把添加到APS中；當根據(jù)t處理完相鄰像素的不平度之后，將t從APS中刪除。此循環(huán)往復(fù)，直至APS為空。之后在對顏色信息進行區(qū)域適應(yīng)性的平滑，消除圖像邊緣處的著色誤差之后就能得到最后的彩色結(jié)果。部分著色圖像原始圖像初始化是APS空？否傳遞不平度（短程線）被傳遞像素的不平度（短程線）改變？將被傳遞像素加入APS是否將元像素從APS中去除邊緣處理輸出彩色圖像 彩色化程序流程圖 基于最短路徑的圖像著色的結(jié)果圖像著色的目的使處理后圖像的某些內(nèi)容更加醒目,利用最短路徑的方法給黑白圖像著色是為了可以更快的得到著色后的圖像。下圖是兩幅黑白圖像在利用本文所介紹的基于最短路徑的圖像著色方法在MATLAB中實現(xiàn)的著色圖像。 黑白圖像Lilies 對Lilies進行局部顏色涂抹 對Lilies著色后的彩圖，為了使圖像可以醒目的呈現(xiàn)在大家眼前，對Lilies進行著色，首先這幅圖需要著色的部分有花朵和葉片，然后根據(jù)灰度值的不同，每種顏色向其相同或相近的灰度值擴展。 黑白圖像Arch 對Arch進行局部顏色涂抹 對Arch著色后的彩圖。經(jīng)過著色后的圖像不僅看起來漂亮而且醒目。而且可以得到從黑白圖像中得不到的信息。結(jié)束語轉(zhuǎn)眼間這次的畢業(yè)設(shè)計已經(jīng)接近尾聲，作為一個本科生的畢業(yè)設(shè)計，由于經(jīng)驗的匱乏，難免有許多考慮不周全的地方，如果沒有導師的督促指導，想要完成這個設(shè)計是很有難度的。在這半年的時間里我感受很深。從這次的畢業(yè)設(shè)計中我學到了很多東西。最短路徑在現(xiàn)實生活中越來越重要，所謂最短路徑就是網(wǎng)絡(luò)中兩點之間距離最短的路徑，這里講的距離可以是實際的距離，也可以引申為其它的度量，如時間、運費、流量等。因此，最短路徑就是為了能快速、高效的實現(xiàn)各種需要的一種方法。圖像著色的目的是使處理后圖像的某些內(nèi)容更加醒目。人眼對彩色的分辨能力遠遠大于對黑白灰度的分辨能力：對一般的觀察者來說，通常只能分辨十幾級灰度，而人眼可分辨出上千種彩色的色調(diào)和強度。因此，在一幅黑白圖像中檢測不到的信息，經(jīng)圖像著色增強后可較容易地檢測出來。圖像著色的方法有很多種，例如：基于過度分割的圖像彩色化，基于拉普拉斯方程的圖像彩色化等，本論文是從最短路徑的方向研究圖像著色。利用最短路徑盡量實現(xiàn)對圖像的最快著色。這次畢業(yè)設(shè)計在老師的悉心教導下讓我充分體會到了圖像著色的重要性。在現(xiàn)實生活中，彩色圖像無處不見，已經(jīng)成為人們不可或缺的一部分。在這次畢業(yè)設(shè)計過程中我學到了什么事最短路徑以及什么是圖像著色。也學到了怎樣利用最短路徑的方式進行圖像著色。我相信我在這次畢業(yè)設(shè)計中所學到東西在我以后的生活中會有很大的幫助。參考文獻[1] Anany （潘彥譯）.北京：清華大學出版社, 2004[2] 殷人昆,（用面向?qū)ο蠓椒ㄅcC++描述）.北京：清華大學出版社,2000[3] 龍光正,2002,24(6)：106108[4] ：,2001,30(3)：269275[5] 王杰臣,楊得志,1999,16(4)：282285[6] 王曉東,陳國龍,2002,23(9)：10831087[7] 羅理,2007,21(2)：5358[8] 樂陽, ,199909,24(3)：4752[9] , 20070508[10] amp。CG國家重點實驗室,20020812[11] 滕升華,諶安軍,2006,28(7)：3944[12] ：中國廣播電視出版社,2001：1314[13] ：[博士].中國科學院電子學研究所,2007：3641[14] 朱秀昌,劉峰,：北京郵電大學出版社,2002：9093[15] ：電子工業(yè)出版社,2001：212214[16] 劉慶祥,(交通科學與工程版),200303[17] ,20060101[18] ,2004 [19] 胡偉,200505[20] Guillermo partial differential equations and image Univercity Press,2001[21] 張德豐,雷小平,：電子工業(yè)出版社, 201005致謝感謝我的導師張可為老師，他嚴謹細致、一絲不茍的作風一直是我工作、學習中的榜樣，他循循善誘的教導和不拘一格的思路給予我無盡的啟迪。從課題的選擇到課題的研究及論文的完成都是在張老師的悉心指導和幫助下完成的，在這一過程中，我碰到過很多問題，曾多次向張老師請教，張老師都很有耐心的為我一一解答，張老師給了我很多的幫助，讓我克服了很多的困難，張老師為人樸實，思維敏捷，知識淵博都深深的感染了我，我覺得我應(yīng)該向張老師學習。在此還要感謝一直教育我的湖南工程學院的老師們，是你們讓我學習到了很多的知識，也教會我如何去為人處事。你們默默地給了我關(guān)心和幫助，你們無私的奉獻讓我們感到無限的溫暖。許鳳英2011年6月33