前言

　　隨著現(xiàn)代社會(huì)的發(fā)展，信息的形式和數(shù)量正在迅猛增長。其中很大一部分是圖像，圖像可以把事物生動(dòng)地呈現(xiàn)在我們面前，讓我們更直觀地接受信息。同時(shí)，計(jì)算機(jī)已經(jīng)作為一種人們普遍使用的工具為人們的生產(chǎn)生活服務(wù)。

　　圖像處理概況

　　圖像處理，是對(duì)圖像進(jìn)行分析、加工、和處理，使其滿足視覺、心理以及其他要求的技術(shù)。圖像處理是信號(hào)處理在圖像域上的一個(gè)應(yīng)用。目前大多數(shù)的圖像是以數(shù)字形式存儲(chǔ)，因而圖像處理很多情況下指數(shù)字圖像處理。本文接下來將簡單粗略介紹下數(shù)字圖像處理領(lǐng)域中的經(jīng)典算法。

　　圖算法領(lǐng)域10大經(jīng)典算法

　　基本遍歷

　　一、深度優(yōu)先搜索

　　深度優(yōu)先搜索算法思想

　　深度優(yōu)先遍歷圖的方法（一種遞歸的定義）是，假定給定圖G的初始狀態(tài)是所有頂點(diǎn)均未被訪問過，在G中任選一個(gè)頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遞歸調(diào)用包含以下操作：

　?。?）訪問搜索到的未被訪問的鄰接點(diǎn)；

　?。?）將此頂點(diǎn)標(biāo)記為已訪問節(jié)點(diǎn)；

　　（3）搜索該頂點(diǎn)的未被訪問的鄰接點(diǎn)，若該鄰接點(diǎn)存在，則從此鄰接點(diǎn)開始進(jìn)行同樣的訪問和搜索。

　　深度優(yōu)先搜索算法實(shí)現(xiàn)：

　　1. 使用棧來實(shí)現(xiàn)。相關(guān)算法實(shí)現(xiàn)總結(jié)為：

　　（1） 將初始節(jié)點(diǎn)壓棧。

　?。?） While（棧非空） {

　?。?） 取出棧頂點(diǎn)，暫時(shí)存儲(chǔ)這個(gè)節(jié)點(diǎn)node_t信息。

　?。?） 訪問該節(jié)點(diǎn)，并且標(biāo)示已訪問。

　?。?） 將棧頂元素出站。

　?。?） For（遍歷node_t的相鄰的未訪問過的節(jié)點(diǎn)）{

　?。?） 將其入棧。

　　}

　　}

　　注意事項(xiàng)：一定要先將該訪問節(jié)點(diǎn)出棧后，再將其鄰接的未訪問的節(jié)點(diǎn)入棧。切記不要，之前我的經(jīng)歷，如果沒有鄰接點(diǎn)就出棧，否則就不出站，但是標(biāo)記了該節(jié)點(diǎn)為訪問節(jié)點(diǎn)的。

　　2. 使用遞歸來實(shí)現(xiàn)。相關(guān)算法實(shí)現(xiàn)總結(jié)為：

　?。?） DFS（初始節(jié)點(diǎn)）

　?。?） Function DFS（一個(gè)節(jié)點(diǎn)） {

　　（3） 訪問該節(jié)點(diǎn)，并且標(biāo)示已訪問。

　?。?） For（遍歷該節(jié)點(diǎn)的相鄰的未訪問過的節(jié)點(diǎn)） {

　　（5） DFS（這個(gè)鄰接節(jié)點(diǎn)）。

　　}

　　}

　　二、廣度優(yōu)先搜索

　　此圖遍歷中最基本的倆種算法，BFS，DFS，入選本圖算法十大算法，自是無可爭議。

　　因?yàn)?，這倆種搜索算法，應(yīng)用實(shí)為廣泛而重要。

　　關(guān)于此BFS、DFS算法，更多，請(qǐng)參考：

　　http://blog.csdn.net/v_JULY_v/archive/2011/01/01/6111353.aspx

　　三、A*搜索算法

　　DFS和BFS在展開子結(jié)點(diǎn)時(shí)均屬于盲目型搜索，也就是說，

　　它不會(huì)選擇哪個(gè)結(jié)點(diǎn)在下一次搜索中更優(yōu)而去跳轉(zhuǎn)到該結(jié)點(diǎn)進(jìn)行下一步的搜索。

　　在運(yùn)氣不好的情形中，均需要試探完整個(gè)解集空間， 顯然，只能適用于問題規(guī)模不大的搜索問題中。

　　A*算法，作為啟發(fā)式算法中很重要的一種，被廣泛應(yīng)用在最優(yōu)路徑求解和一些策略設(shè)計(jì)的問題中。

　　而A*算法最為核心的部分，就在于它的一個(gè)估值函數(shù)的設(shè)計(jì)上：

　　f（n）=g（n）+h（n）

　　其中f（n）是每個(gè)可能試探點(diǎn)的估值，它有兩部分組成：

　　一部分，為g（n），它表示從起始搜索點(diǎn)到當(dāng)前點(diǎn)的代價(jià)（通常用某結(jié)點(diǎn)在搜索樹中的深度來表示）。

　　一部分，即h（n），它表示啟發(fā)式搜索中最為重要的一部分，即當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估值。

　　更多，請(qǐng)參考：

　　經(jīng)典算法研究系列：一、A*搜索算法

　　附：

　　Flood Fill

　　LeeMaRS、wtzyb4446：

　　圖形學(xué)中Flood Fill是滿水法填充，是用來填充區(qū)域的。

　　就好比在一個(gè)地方一直到水，水會(huì)往四周滿延開，直到高地阻擋。

　　Flood Fill就是從一個(gè)點(diǎn)開始往四周尋找相同的點(diǎn)填充，直到有不同的點(diǎn)為止。

　　我們用的Flood Fill和這個(gè)差不多原理，就是BFS的一種形式。

　　假設(shè)在（i，j）滴好大一滴紅墨水，然后水開始漫開，向它的上下左右染色，也就是（i-1，j），（i+1，j），（i，j-1），（i，j+1）這四個(gè)點(diǎn)。然后在分別再從這四個(gè)點(diǎn)開始向周圍染色。。。直到碰到某種邊界為止。

　　把這個(gè)轉(zhuǎn)化為BFS的思想，就是隊(duì)列中初始元素是（i，j），然后把（i，j）擴(kuò)展?fàn)顟B(tài)，得到（i-1，j），（i+1，j），（i，j-1），（i，j+1）這四個(gè)狀態(tài)，加入隊(duì)列。把（i，j）出列，繼續(xù)擴(kuò)展下一個(gè)結(jié)點(diǎn)。如此
?

　　最短路徑算法

　　四、Dijkstra

　　Dijkstra 算法，又叫迪科斯徹算法（Dijkstra），

　　算法解決的是有向圖中單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問題。

　　此Dijkstra 算法已在本BLOG內(nèi)倆篇文章中，有所具體闡述，請(qǐng)參見：

　　I、經(jīng)典算法研究系列：二、Dijkstra 算法初探

　　http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx

　　II、經(jīng)典算法研究系列：二之續(xù)、徹底理解Dijkstra算法

　　http://blog.csdn.net/v_JULY_v/archive/2011/02/13/6182419.aspx

　　五、Bellman-Ford

　　Bellman-Ford：

　　求單源最短路，可以判斷有無負(fù)權(quán)回路（若有，則不存在最短路），

　　時(shí)效性較好，時(shí)間復(fù)雜度O（VE）。

　　附：

　　SPFA：

　　是Bellman-Ford的隊(duì)列優(yōu)化，時(shí)效性相對(duì)好，時(shí)間復(fù)雜度O（kE）。（k《《V）。

　　六、Floyd-Warshall

　　Floyd-Warshall：求多源、無負(fù)權(quán)邊的最短路。用矩陣記錄圖。時(shí)效性較差，時(shí)間復(fù)雜度O（V^3）。此算法是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題。

　　更多，請(qǐng)參考：

　　幾個(gè)最短路徑算法比較：

　　http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx

　　附：Kneser圖

　　Kneser圖是與圖的分?jǐn)?shù)染色有關(guān)的算法。

　　給定正整數(shù)a，b，a≥2b，Kneser圖Ka:b是以如下方式定義的一個(gè)圖：

　　其頂點(diǎn)是從給定的a個(gè)元素的集合中選出的b個(gè)元素構(gòu)成的子集，兩頂點(diǎn)間有邊當(dāng)且僅當(dāng)這兩個(gè)頂點(diǎn)為不交的集合。

　　最小生成樹

　　七、Prim

　　八、Kruskal

　　此最?。?quán)值）生成樹的倆種算法，日后，會(huì)在本BLOG內(nèi) 具體而深入闡述。

　　圖匹配

　　九、匈牙利算法

　　匈牙利算法是眾多用于解決線性任務(wù)分配問題的算法之一，是用來解決二分圖最大匹配問題的經(jīng)典算法，可以在多項(xiàng)式時(shí)間內(nèi)解決問題，由匈牙利數(shù)學(xué)家Jack Edmonds于1965年提出。

　　這個(gè)算法，比較生疏，下面，稍微闡述下：

　　I、匈牙利算法應(yīng)用問題的描述：

　　設(shè)G=（V，E）是一個(gè)無向圖。如頂點(diǎn)集V可分區(qū)為兩個(gè)互不相交的子集V1，V2之并，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬于這兩個(gè)不同的子集。則稱圖G為二分圖。二分圖也可記為G=（V1，V2，E）。

　　給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。 選擇這樣的子集中邊數(shù)最大的子集稱為圖的最大匹配問題（maximal matching problem）

　　如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備，完美匹配。

　　II、算法描述

　　求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個(gè)算法的時(shí)間復(fù)雜度為邊數(shù)的指數(shù)級(jí)函數(shù)。因此，需要尋求一種更加高效的算法。

　　下面介紹用增廣路求最大匹配的方法（稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出）。

　　增廣路的定義（也稱增廣軌或交錯(cuò)軌）：

　　若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬于M的邊和不屬于M的邊（即已匹配和待匹配的邊）在P上交替出現(xiàn)，則稱P為相對(duì)于M的一條增廣路徑。

　　由增廣路的定義可以推出下述三個(gè)結(jié)論：

　　1－P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。

　　2－將M和P進(jìn)行異或操作（去同存異）可以得到一個(gè)更大的匹配M’。

　　3－M為G的最大匹配當(dāng)且僅當(dāng)不存在M的增廣路徑。

　　算法輪廓：

　?。?）置M為空

　?。?）找出一條增廣路徑P，通過異或操作獲得更大的匹配M’代替M

　?。?）重復(fù)（2）操作直到找不出增廣路徑為止

　　III、時(shí)間復(fù)雜度與空間復(fù)雜度

　　時(shí)間復(fù)雜度

　　鄰接矩陣：最壞為O（n^3） 鄰接表：O（mn）

　　空間復(fù)雜度：

　　鄰接矩陣：O（n^2） 鄰接表：O（m+n）

　　附：

　　Edmonds‘s matching

　　強(qiáng)連通分支算法與網(wǎng)絡(luò)流

　　十、Ford-Fulkerson

　　最大流量算法（Ford-Fulkerson Algorithm），

　　也叫做貝爾曼-福特算法，被用于作為一個(gè)距離向量路由協(xié)議例如RIP， BGP， ISO IDRP， NOVELL IPX的算法。

　　附：Edmonds-Karp、Dinic、Push-relabel、maximum flow

　　強(qiáng)連通分支算法：

　　Kosaraju、 Gabow、 Tarjan。

　　此類算法，日后闡述。

　　完。