圖像處理,是對圖像進行分析、加工、和處理,使其滿足視覺、心理以及其他要求的技術。圖像處理是信號處理在圖像域上的一個應用,目前大多數的圖像是以數字形式存儲,因而圖像處理很多情況下指數字圖像處理。
隨著現代社會的發展,信息的形式和數量正在迅猛增長。其中很大一部分是圖像,圖像可以把事物生動地呈現在我們面前,讓我們更直觀地接受信息。下面簡單介紹下數字圖像處理領域中的經典算法。
一、深度優先搜索
深度優先遍歷圖的算法是,假定給定圖G的初始狀態是所有頂點均未被訪問過,在G中任選一個頂點i作為遍歷的初始點,則深度優先搜索遞歸調用步驟:
1、訪問搜索到的未被訪問的鄰接點;
2、將此頂點標記為已訪問節點;
3、搜索該頂點的未被訪問的鄰接點,若該鄰接點存在,則從此鄰接點開始進行同樣的訪問和搜索,反覆進行直到所有節點都被訪問為止。
二、廣度優先搜索
廣度優先搜索算法,又稱為"寬度優先搜索",簡稱BFS。它的思想是:從圖中某頂點v出發,在訪問了v之後依次訪問v的各個未曾訪問過的鄰接點,然後分別從這些鄰接點出發依次訪問它們的鄰接點,並使得先被訪問的頂點的鄰接點先於後被訪問的頂點的鄰接點被訪問,直至圖中所有已被訪問的頂點的鄰接點都被訪問到。
如果此時圖中尚有頂點未被訪問,則需要另選一個未曾被訪問過的頂點作為新的起始點,重複上述過程,直至圖中所有頂點都被訪問到為止。也就是說,廣度優先搜索遍歷圖的過程是以v為起點,由近至遠,依次訪問和v有路徑相通且路徑長度為1,2...的頂點。
三、A*搜索算法
A*算法(A-Star),作為啟發式搜索算法中的一種,是一種在圖形平面上,有多個節點的路徑,求出最低通過成本的算法,被廣泛應用在最優路徑求解和一些策略設計的問題中。
A*算法操作:首先將起始結點S放入OPEN表,CLOSE表置空,算法描述:
1、如果OPEN表不為空,從表頭取一個結點n,如果為空算法失敗。
2、n是目標解嗎?是,找到一個解(繼續尋找,或終止算法)。
3、將n的所有後繼結點展開,就是從n可以直接關聯的子結點,如果不在CLOSE表中,就將它們放入OPEN表,並把S放入CLOSE表,同時計算每一個後繼結點的估價值f(n),將OPEN表按f(x)排序,最小的放在表頭,重複算法,回到1。
四、Dijkstra算法
又叫迪科斯徹算法,是從一個頂點到其餘各頂點的最短路徑算法,解決的是有向圖中最短路徑問題。迪傑斯特拉算法主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。
Dijkstra算法採用的是一種貪心的策略,基本算法思想:
1、通過Dijkstra計算圖G中的最短路徑時,需要指定起點s。
2、引進兩個集合S和U。S的作用是記錄已求出最短路徑的頂點,而U則是記錄還未求出最短路徑的頂點。
3、初始時,S中只有起點s,U中是除s之外的頂點,並且U中頂點的路徑是"起點s到該頂點的路徑"。然後,從U中找出路徑最短的頂點,並將其加入到S中;更新U中的頂點和頂點對應的路徑。 … 重複該操作,直到遍歷完所有頂點。
五、Bellman-Ford算法
Bellman - ford算法是求含負權圖的單源最短路徑的一種算法,其原理為連續進行鬆弛,在每次鬆弛時把每條邊都更新一下,若在n-1次鬆弛後還能更新,則說明圖中有負環,因此無法得出結果,否則就完成。
Bellman-Ford算法能在更普遍的情況下解決單源點最短路徑問題,算法描述:
1、初始化:將除源點外的所有頂點的最短距離估計值。
2、迭代求解:反覆對邊集E中的每條邊進行鬆弛操作,使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離。
3、檢驗負權迴路:判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點,則算法返回false,表明問題無解。否則算法返回true,並且從源點可達的頂點v的最短距離保存在集合dist[v]中。
六、Floyd-Warshall算法
Floyd-Warshall算法是解決任意兩點間的最短路徑的一種算法,可以正確處理有向圖或負權的最短路徑問題。
算法思想:
1、創建源頂點 v 到圖中所有頂點的距離的集合S,為圖中的所有頂點指定一個距離值,初始均為I,源頂點距離為0。
2、計算最短路徑,執行 V - 1 次遍歷。
3、對於圖中的每條邊:如果起點u的距離d 加上邊的權值w小於終點v的距離d,則更新終點v的距離值d。
4.檢測圖中是否有負權邊形成了環,遍歷圖中的所有邊,計算u至v的距離,如果對於v存在更小的距離,則說明存在環。
七、Prim算法
圖論的一種算法,可在加權連通圖裡搜索最小生成樹。由此算法搜索到的邊子集所構成的樹中,不但包括了連通圖裡的所有頂點,且其所有邊的權值之和亦為最小。
Prim算法在找當前最近頂點時使用到了貪婪算法,算法描述:
1、 在一個加權連通圖中,頂點集合V,邊集合為E。
2、任意選出一個點作為初始頂點,標記為visit,計算所有與之相連接的點的距離,選擇距離最短的,標記visit。
3、在剩下的點,計算與已標記visit點距離最小的點,標記visit,證明加入了最小生成樹,重複操作,直到所有點都被標記為visit。
八、Kruskal算法
Kruskal算法是一種用來尋找最小生成樹的算法,在剩下的所有未選取的邊中,找最小邊,如果和已選取的邊構成迴路,則放棄,選取次小邊。
Kruskal算法就是基於並查集的貪心算法,算法描述:
1、將圖G看做一個森林,每個頂點為一棵獨立的樹。
2、將所有的邊加入集合S,即一開始S = E 。
3、從S中拿出一條最短的邊(u,v),如果(u,v)不在同一棵樹內,則連接u,v合併這兩棵樹,同時將(u,v)加入生成樹的邊集E'。
4、重複3直到所有點屬於同一棵樹,邊集E'就是一棵最小生成樹。
九、匈牙利算法
匈牙利算法是用於解決線性任務分配問題的算法之一,該算法的核心就是尋找增廣路徑,是用來解決二分圖最大匹配問題的經典算法,可以在多項式時間內解決問題。
算法輪廓:
1、置M為空
2、找出一條增廣路徑P,通過異或操作獲得更大的匹配M'代替M.
3、重複2操作直到找不出增廣路徑為止。
十、Ford-Fulkerson算法
也稱最大流量算法,常用於作為一個距離向量路由協議例如RIP, BGP, ISO IDRP, NOVELL IPX的算法。
Ford-Fulkerson 算法是一種迭代方法。開始時,對所有 u, v ∈ V 有 f(u, v) = 0,即初始狀態時流的值為 0。在每次迭代中,可通過尋找一條增廣路徑來增加流值。增廣路徑可以看做是從源點 s 到匯點 t 之間的一條路徑,沿該路徑可以壓入更多的流,從而增加流的值。反覆進行這一過程,直至增廣路徑都被找出為止。