【文章內(nèi)容簡(jiǎn)介】 以用一個(gè)圓錐空間模型來描述，此圓錐模型 比較復(fù)雜，但確能把色調(diào)、亮度及飽和度的變化情形表現(xiàn)得很清楚。 由于人的視覺對(duì)亮度的敏感程度遠(yuǎn)強(qiáng)于對(duì)顏色濃淡的敏感程度，采用 HSI色彩空間比 RGB 空間更符合人的視覺特性，也更便于色彩處理和識(shí)別。在圖像處理和計(jì)算機(jī)視覺中大量算法都可在 HSI 色彩空間中方便地使用，它們可以分開處理而且是相互獨(dú)立的。因此，在 HSI 色彩空間可以簡(jiǎn)化圖像分析和處理的工作量。 HSV空間與 HSI 類似，區(qū)別是亮度分量的計(jì)算不同，從而使得亮度和飽和度的分布及動(dòng)態(tài)范圍有一定差異。 色彩空間在本質(zhì)上是顏色的描述方式，考慮其對(duì)顏色的描述角度，可以用一種更為寬泛的形式對(duì)色彩空間進(jìn)行分類，即分為由顏色分量表示的基本色空間和利用顏色要素表達(dá)的色彩屬性空間 ； 前者如 RGB、 CMYK 空間， YIQ、 YUV、YCbCr 及 HSI、 HSV等空間都?xì)w為后者。 顧名思義，基本色空間重在說明顏色的構(gòu)成，如 RGB 模型明示了顏色三基色分量， CMYK 用以說明打印一種顏色需用的顏料配比。顏色屬性空間則直接與人眼對(duì)顏色的視覺感受，即顏色三要素 (亮度、色調(diào)、飽和度 )密切相關(guān)，更加符合人的視覺信息獲取過程。顏色屬性空間的顯著特征就是亮色分離。 基于最短路徑的圖像著色 10 顏色描述中是否實(shí)現(xiàn)亮色分離，是區(qū)分寬泛分類色彩空間的主要標(biāo)志。實(shí)現(xiàn)亮色分離就可以對(duì)顏色的亮度和色度進(jìn)行單獨(dú)處理，這為一些圖像處理問題帶來極大便利。 的介紹 最短路徑 最短路徑這一重要問題早在 20 世紀(jì)初就已經(jīng)得到人們的高度重視，當(dāng)時(shí)也有許多科學(xué)家研究這一重要問題的求解方法。但直到 1959 年荷蘭計(jì)算機(jī)科學(xué)家Dijkstra（迪杰斯特拉）才給出這一問題求解的基本思想，并給出了算法。后來這個(gè)算法就成了眾所周知的 Dijkstra 算法，也成為了一代經(jīng)典。當(dāng)時(shí)的 Dijkstra提出的這一算法主要解決的問題是從固定的一個(gè)點(diǎn)到其他各點(diǎn)的最短路徑問題。但是在實(shí)際生活中往往要求解決的不只是固定一點(diǎn)到其他點(diǎn)的最短路徑，而是要求計(jì)算出任意兩點(diǎn)之間的最短距離。 隨著社會(huì)的不斷進(jìn)步，最短路徑算法在人們的日常生活中顯得越來越重要。所謂最短路徑就是網(wǎng)絡(luò)中兩點(diǎn)之間距離最短的路徑，這里講的距離可以是實(shí)際的距離，也可以引申為其他的度量，比如時(shí)間、運(yùn)費(fèi)、流量等。因此，從廣義上講，最短路徑算法就是從網(wǎng)絡(luò)中找出兩個(gè)點(diǎn)之間最小阻抗路徑的算法。 最短路徑的定義 最短路徑的概念：短程線距離的概念： tsc, (p)表示連接圖像中兩點(diǎn) r , s 的曲線， Y 代表像素的亮度， r , s 間的短程線距離義為 ptsc dpCYtsd ts ? ??? )(m in),( , () 短程線距離對(duì)應(yīng)于連接兩點(diǎn)的所有曲線中、沿曲線方向像素亮度值的梯度積分的最小值，即短程線表示從圖像中一點(diǎn)到另一點(diǎn)的灰度變化最平緩的路徑。 最短路徑 的離散化定義：在數(shù)字圖像中短程線距離的計(jì)算需要采用離散形式，現(xiàn)給出一種更直觀的離散定義。用 Y 表示像索的亮度，則圖像中相鄰兩點(diǎn) r、基于最短路徑的圖像著色 11 s 間的短程線距離為 )()(),( tYsYtsd ?? () 定義圖像中 8連通的曲線 },...,{ 21 mpppC ? 上的曲線距離 ),()( 1111 ????? imi ippc ppdcd m () 則圖像中兩點(diǎn)間的短程線距離等于連接這兩點(diǎn)的所有曲線中的最短距離 )(min),( stc cdtsd ? () 這種離散定義形式便于進(jìn)行計(jì)算。 短程線距離是定義在圖像中的某種最短距離，在圖論中也有類似的最短距離。給定一個(gè)雙向圖 G，它的每條邊都有一個(gè)非負(fù)的長(zhǎng)度，路徑的長(zhǎng)度即為次路徑經(jīng)過的邊的長(zhǎng)度之和。 圖 (a)給出了一個(gè)具有五個(gè)頂點(diǎn)的有向圖，各邊上的數(shù)即為長(zhǎng)度，假設(shè)源頂點(diǎn) s為 1，從頂點(diǎn) 1出發(fā)到各頂點(diǎn)的最短路徑按長(zhǎng)度順序列在圖 (b)中，每條路徑前的數(shù)字為路徑長(zhǎng)度。 對(duì)于圖像而言，如果把每個(gè)像素對(duì)應(yīng)圖中的頂點(diǎn)，相鄰像素間的亮度差看作圖中頂點(diǎn)間的邊長(zhǎng)，那么所謂短程線距離就可等效于圖論中的 最短距離。 (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)。然后將 n 個(gè)輸入排成這種量度標(biāo)準(zhǔn)要求的順序，按照這種順序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已經(jīng)構(gòu)成的在這種量度意義的部分最優(yōu)解加在一起能產(chǎn)生一個(gè)可行解，則把此輸入加到這部分最優(yōu)解中，否則不加入。這種能夠在某種量度意義下得到最優(yōu)解的分級(jí)處理方法稱為貪心算法。 按照上面的思路，可以逐步地構(gòu)造出這些最短路。使用迄今已經(jīng)生成的所有路徑長(zhǎng)度之和作為一種量度，為了使這一量度達(dá)到最小，單獨(dú)的每一條路徑都必須具有最小長(zhǎng)度。使用這一量度標(biāo)準(zhǔn)，假定已經(jīng)構(gòu)造了 n 條最短路徑，則下面要構(gòu)造的路徑應(yīng)該是下一條最短的最小長(zhǎng)度路徑。 如何根據(jù)貪心算法，確定路徑上的每個(gè)節(jié)點(diǎn)而最終求得最短路徑， Dijkstra提出了一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生到各頂點(diǎn)的最短路徑的算法。 1)假設(shè)用帶權(quán)的鄰接矩陣 cost 來表示一個(gè)帶權(quán)圖， ],[cos jit 表示弧 iV ， jV 上的權(quán)值。若 iV ， jV 不存在，則置 ],[cos jit 為 ? （ 在計(jì)算機(jī)上可以用允許的最大整數(shù)值來表示）， S 為已找到從 oV 點(diǎn)出發(fā)的最短路徑的集合，它的初態(tài)為空集。0 2 3 4 6 1 1 1 1 1 3 3 2 3 4 4 5 基于最短路徑的圖像著色 13 從 oV 到其他結(jié)點(diǎn)的路徑長(zhǎng)度向量為 ][ndist 。那么從 oV 出發(fā)到圖上其余頂點(diǎn) iV 可能達(dá)到的最短路徑長(zhǎng)度的初值為 VViVtid ist io ?? ],[c o s][ （ ） 2)選擇 jV 使得 dist[j]=min{dist[j]， iV ?VS}， jV 就是當(dāng)前求得的一條從 oV 出發(fā)的最短路徑的終點(diǎn)。令 S=S║ { jV }。 3)修改從 oV 出發(fā)到集合 VS上任一頂點(diǎn) kV 可達(dá)的最短路徑長(zhǎng)度。如果 ][],[c os][ kdi sstkjtjdi st ?? 則修改 ][kdist 為 ],[c os][][ kjtjdi stkdi st ?? 4)重復(fù)操作 2)， 3)共 n1 由此求得從 oV 到圖上其余各個(gè)結(jié)點(diǎn)的最短路徑。這是依據(jù)路徑長(zhǎng)度遞增的序列而求得的。 最短路徑的基本方法 傳統(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ù)過程 。這樣雖然能夠?qū)崿F(xiàn)任意兩點(diǎn)之間的最短路徑查找 ， 但是從效率上分析并不是最優(yōu)的 。 實(shí)際是可以進(jìn)行改進(jìn) ， 具體方法如下 ： 1） 根據(jù) Dijkstra 算法思想 ， 可以由圖中結(jié)點(diǎn)的出入度信息來提高各點(diǎn)之間最短路徑的查找速度 。 2） 在帶權(quán)圖中利用 Dijkstra 算法找出部分結(jié)點(diǎn)之間的最短路徑后 ， 若其他還沒有找出最短路徑的結(jié)點(diǎn)可以利用前面已找出的最短路徑信息為自己提供快速的最短路徑查找 。 1. 利用結(jié)點(diǎn)入度信息查找 根據(jù)結(jié)點(diǎn)的入度信息來優(yōu)化查找最短路徑的基本思想是 ： 當(dāng)某結(jié)點(diǎn)的入度為0時(shí) ， 圖中其他結(jié)點(diǎn)到該結(jié)點(diǎn)的最短路徑都為無窮 （ 不可達(dá) ） 并且其他結(jié)點(diǎn)之間的最短路徑也不會(huì)出現(xiàn)該結(jié)點(diǎn) ， 所以在求圖中其他各結(jié)點(diǎn)之間的最短路徑時(shí) ， 可以將該結(jié)點(diǎn)先刪除以簡(jiǎn)化整個(gè) 圖的最短路徑的查找 。 根據(jù)上述基本思路 ， 給出優(yōu)化查找的具體步驟 ： 基于最短路徑的圖像著色 14 1)求出圖中各結(jié)點(diǎn)的入度 ； 2)找到入度為 0的結(jié)點(diǎn) ， 記作 1V ； 3)從 1V 點(diǎn)出發(fā)開始用 Dijkstra 算法求 1V 到其他各結(jié)點(diǎn)的最短路徑 ； 4)求完后 ， 若結(jié)點(diǎn) 1V 入度為 0 則刪除該結(jié)點(diǎn) ， 從而簡(jiǎn)化了連接圖 ， 也簡(jiǎn)化了查找步驟 ； 5)重復(fù) 2)， 3)步 ， 直到?jīng)]有入度滿足條件的結(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)的最短路徑記為無窮大即可 。 5 6 8 7 9 圖 將圖 A 刪除后的圖像如圖 所示 ， 這樣使得 B， C， D結(jié)點(diǎn)之間最短路徑的查找更 為簡(jiǎn)便。 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á)的 。 其次 ， 當(dāng)某個(gè)結(jié)點(diǎn)的出度為 1時(shí) ， 該結(jié)點(diǎn)只有唯一的后繼結(jié)點(diǎn) 。 并且該結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑必須經(jīng)過此后繼結(jié)點(diǎn) 。 當(dāng)該結(jié)點(diǎn)的這個(gè)唯一的后繼結(jié)點(diǎn)到其他各結(jié)點(diǎn)的最短路徑已經(jīng)求出以后 ， 該結(jié)點(diǎn)到其他各結(jié)點(diǎn)的最短路徑也就可以求出了 。 只需在其唯一后繼結(jié)點(diǎn)的最短路徑求出后再加上其唯一出度邊的權(quán)值即可 。 根據(jù)上面討論的基本思想 ， 下面是從出度著手查找的具體步驟 ： 1)首先求出圖中所有結(jié)點(diǎn)的出度 ； 2)找到出度為 0或?yàn)?1的結(jié)點(diǎn) ， 記作 mV ； 3)若出度為 0， 則不必去求從該結(jié)點(diǎn)出發(fā)的最短路徑了 ， 因?yàn)閺脑摻Y(jié)點(diǎn)出發(fā)是不可能找出到其他結(jié)點(diǎn)的最短路徑 （不可 達(dá) ）； 4)若出度為 1則也不必去求從該結(jié)點(diǎn)出發(fā)的最短路徑了 ， 只需在其唯一后繼結(jié)點(diǎn)的最短路徑求出后再加上其唯一出度邊的權(quán)值即可 ； 5)重復(fù) 2)、 3)、 4)步 ， 直到?jīng)]有出度滿足條件的結(jié)點(diǎn) 。 不論是從入度還是從出度著手都應(yīng)該考慮出入度為 1 的多個(gè)結(jié)點(diǎn) ， 并注意其前驅(qū)結(jié)點(diǎn)的順序 。 3. 利用已找出的最短路徑快速查找 這種優(yōu)化方法的基本思想是 ： 根據(jù)圖 所示 ， 假設(shè)從源點(diǎn) A 出發(fā)到結(jié)點(diǎn) C 的最短路徑已經(jīng)求出 ， 為 A， B， C， D； 那么需要求從結(jié)點(diǎn) B 出發(fā)到結(jié)點(diǎn)D 或到結(jié)點(diǎn) C 的最短路徑時(shí) ， 不用再去按照 Dijkstra 算法去求 ， 可按照已找出的A→C 的最短路徑直接得出 B→C 的最短路徑為 B， D， C； 得出 B→D 的最短路徑為 B， D 證明如下 ： 當(dāng)結(jié)點(diǎn) A 到結(jié)點(diǎn) C 的最短路徑為 A， B， C， D； 假設(shè)結(jié)點(diǎn) B 到結(jié)點(diǎn) D 的最短路徑不是 B， D； 而是 B? D 那么 可得出 A， B? D， C； 這條路徑一定比路徑 A， B， D， C 更短 ， 因此與已知 A→C 的最短路徑 A， B， D，C 矛盾 。 所以 ， 可知 B→D 的最短路徑必為 B， D； 同理可以推出 B→C 的最短路徑必為 B， D