【文章內(nèi)容簡(jiǎn)介】 前者如RGB、CMYK空間，YIQ、YUV、YCbCr及HSI、HSV等空間都?xì)w為后者。顧名思義，基本色空間重在說(shuō)明顏色的構(gòu)成，如RGB模型明示了顏色三基色分量，CMYK用以說(shuō)明打印一種顏色需用的顏料配比。顏色屬性空間則直接與人眼對(duì)顏色的視覺(jué)感受，即顏色三要素(亮度、色調(diào)、飽和度)密切相關(guān)，更加符合人的視覺(jué)信息獲取過(guò)程。顏色屬性空間的顯著特征就是亮色分離。顏色描述中是否實(shí)現(xiàn)亮色分離，是區(qū)分寬泛分類色彩空間的主要標(biāo)志。實(shí)現(xiàn)亮色分離就可以對(duì)顏色的亮度和色度進(jìn)行單獨(dú)處理，這為一些圖像處理問(wèn)題帶來(lái)極大便利。 最短路徑的介紹 最短路徑最短路徑這一重要問(wèn)題早在20世紀(jì)初就已經(jīng)得到人們的高度重視，當(dāng)時(shí)也有許多科學(xué)家研究這一重要問(wèn)題的求解方法。但直到1959年荷蘭計(jì)算機(jī)科學(xué)家Dijkstra（迪杰斯特拉）才給出這一問(wèn)題求解的基本思想，并給出了算法。后來(lái)這個(gè)算法就成了眾所周知的Dijkstra算法，也成為了一代經(jīng)典。當(dāng)時(shí)的Dijkstra提出的這一算法主要解決的問(wèn)題是從固定的一個(gè)點(diǎn)到其他各點(diǎn)的最短路徑問(wèn)題。但是在實(shí)際生活中往往要求解決的不只是固定一點(diǎn)到其他點(diǎn)的最短路徑，而是要求計(jì)算出任意兩點(diǎn)之間的最短距離。 隨著社會(huì)的不斷進(jìn)步，最短路徑算法在人們的日常生活中顯得越來(lái)越重要。所謂最短路徑就是網(wǎng)絡(luò)中兩點(diǎn)之間距離最短的路徑，這里講的距離可以是實(shí)際的距離，也可以引申為其他的度量，比如時(shí)間、運(yùn)費(fèi)、流量等。因此，從廣義上講，最短路徑算法就是從網(wǎng)絡(luò)中找出兩個(gè)點(diǎn)之間最小阻抗路徑的算法。 最短路徑的定義最短路徑即短程線距離的概念：(p)表示連接圖像中兩點(diǎn)r , s的曲線，Y代表像素的亮度，r , s間的短程線距離義為 (22)短程線距離對(duì)應(yīng)于連接兩點(diǎn)的所有曲線中、沿曲線方向像素亮度值的梯度積分的最小值，即短程線表示從圖像中一點(diǎn)到另一點(diǎn)的灰度變化最平緩的路徑。最短路徑的離散化定義：在數(shù)字圖像中短程線距離的計(jì)算需要采用離散形式，現(xiàn)給出一種更直觀的離散定義。用Y表示像索的亮度，則圖像中相鄰兩點(diǎn)r、s間的短程線距離為 (23)定義圖像中8連通的曲線上的曲線距離 (24)則圖像中兩點(diǎn)間的短程線距離等于連接這兩點(diǎn)的所有曲線中的最短距離 (25)這種離散定義形式便于進(jìn)行計(jì)算。短程線距離是定義在圖像中的某種最短距離，在圖論中也有類似的最短距離。給定一個(gè)雙向圖G，它的每條邊都有一個(gè)非負(fù)的長(zhǎng)度，路徑的長(zhǎng)度即為次路徑經(jīng)過(guò)的邊的長(zhǎng)度之和。(a)給出了一個(gè)具有五個(gè)頂點(diǎn)的有向圖，各邊上的數(shù)即為長(zhǎng)度，假設(shè)源頂點(diǎn)s為1，(b)中，每條路徑前的數(shù)字為路徑長(zhǎng)度。對(duì)于圖像而言，如果把每個(gè)像素對(duì)應(yīng)圖中的頂點(diǎn)，相鄰像素間的亮度差看作圖中頂點(diǎn)間的邊長(zhǎng)，那么所謂短程線距離就可等效于圖論中的最短距離。842154235143(a)圖0234611111332344502346(b)圖最短路徑 最短路徑的基本思路為了解決最短路徑問(wèn)題，首先應(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來(lái)表示一個(gè)帶權(quán)圖，表示弧，上的權(quán)值。若，不存在，則置為（在計(jì)算機(jī)上可以用允許的最大整數(shù)值來(lái)表示），S為已找到從點(diǎn)出發(fā)的最短路徑的集合，它的初態(tài)為空集。從到其他結(jié)點(diǎn)的路徑長(zhǎng)度向量為。那么從出發(fā)到圖上其余頂點(diǎn)可能達(dá)到的最短路徑長(zhǎng)度的初值為 （）2)選擇使得dist[j]=min{dist[j]， {VS}，就是當(dāng)前求得的一條從出發(fā)的最短路徑的終點(diǎn)。令S=S║{}。3)修改從出發(fā)到集合VS上任一頂點(diǎn)可達(dá)的最短路徑長(zhǎng)度。如果則修改為4)重復(fù)操作2)，3)共n1由此求得從到圖上其余各個(gè)結(jié)點(diǎn)的最短路徑。這是依據(jù)路徑長(zhǎng)度遞增的序列而求得的。 最短路徑的基本方法傳統(tǒng)的利用Dijkstra算法來(lái)實(shí)現(xiàn)圖中任意結(jié)點(diǎn)之間的最短路徑查找，其基本思想就是依次以圖中各個(gè)結(jié)點(diǎn)為起點(diǎn)利用Dijkstra算法計(jì)算出最短路徑，這樣循環(huán)n次即可得到圖中任意結(jié)點(diǎn)之間的最短路，而每步都是一個(gè)簡(jiǎn)單的重復(fù)過(guò)程。這樣雖然能夠?qū)崿F(xiàn)任意兩點(diǎn)之間的最短路徑查找，但是從效率上分析并不是最優(yōu)的。實(shí)際是可以進(jìn)行改進(jìn)，具體方法如下： 1)根據(jù)Dijkstra算法思想，可以由圖中結(jié)點(diǎn)的出入度信息來(lái)提高各點(diǎn)之間最短路徑的查找速度。 2)在帶權(quán)圖中利用Dijkstra算法找出部分結(jié)點(diǎn)之間的最短路徑后，若其他還沒(méi)有找出最短路徑的結(jié)點(diǎn)可以利用前面已找出的最短路徑信息為自己提供快速的最短路徑查找。1. 利用結(jié)點(diǎn)入度信息查找根據(jù)結(jié)點(diǎn)的入度信息來(lái)優(yōu)化查找最短路徑的基本思想是：當(dāng)某結(jié)點(diǎn)的入度為0時(shí)，圖中其他結(jié)點(diǎn)到該結(jié)點(diǎn)的最短路徑都為無(wú)窮（不可達(dá)）并且其他結(jié)點(diǎn)之間的最短路徑也不會(huì)出現(xiàn)該結(jié)點(diǎn)，所以在求圖中其他各結(jié)點(diǎn)之間的最短路徑時(shí)，可以將該結(jié)點(diǎn)先刪除以簡(jiǎn)化整個(gè)圖的最短路徑的查找。根據(jù)上述基本思路，給出優(yōu)化查找的具體步驟：1)求出圖中各結(jié)點(diǎn)的入度；2)找到入度為0的結(jié)點(diǎn)，記作；3)從點(diǎn)出發(fā)開始用Dijkstra算法求到其他各結(jié)點(diǎn)的最短路徑；4)求完后，若結(jié)點(diǎn)入度為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)的最短路徑記為無(wú)窮大即可。56 8 79ABCD 基于入度優(yōu)化的實(shí)例圖，這樣使得B，C，D結(jié)點(diǎn)之間最短路徑的查找更為簡(jiǎn)便。 79BCD A入度為0，A執(zhí)行完3),4)步后的圖示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)過(guò)此后繼結(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)?的結(jié)點(diǎn)，記作；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)化方法的基本思想是：，假設(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，C。86 93 24 51CDAB 利用最短路徑信息優(yōu)化實(shí)例圖根據(jù)上面分析，可以得出圖中任意兩結(jié)點(diǎn)之間的最短路徑。，優(yōu)化實(shí)現(xiàn)的具體步驟如下（按照A，B，C，D為出發(fā)點(diǎn)的順序查找）：從A點(diǎn)出發(fā)尋找其他各結(jié)點(diǎn)的最短路徑步驟：1)A→B的最短路徑為A，B∥由Dijkstra得