波陣面演算法等距

① 在圖像處理中有哪些演算法

1、圖像變換：

由於圖像陣列很大，直接在空間域中進行處理，涉及計算量很大。採用各種圖像變換的方法，如傅立葉變換、沃爾什變換、離散餘弦變換等間接處理技術，將空間域的處理轉換為變換域處理，可減少計算量，獲得更有效的處理。它在圖像處理中也有著廣泛而有效的應用。

2、圖像編碼壓縮：

圖像編碼壓縮技術可減少描述圖像的數據量，以便節省圖像傳輸、處理時間和減少所佔用的存儲器容量。

壓縮可以在不失真的前提下獲得，也可以在允許的失真條件下進行。

編碼是壓縮技術中最重要的方法，它在圖像處理技術中是發展最早且比較成熟的技術。

3、圖像增強和復原：

圖像增強和復原的目的是為了提高圖像的質量，如去除雜訊，提高圖像的清晰度等。

圖像增強不考慮圖像降質的原因，突出圖像中所感興趣的部分。如強化圖像高頻分量，可使圖像中物體輪廓清晰，細節明顯；如強化低頻分量可減少圖像中雜訊影響。

4、圖像分割：

圖像分割是數字圖像處理中的關鍵技術之一。

圖像分割是將圖像中有意義的特徵部分提取出來，其有意義的特徵有圖像中的邊緣、區域等，這是進一步進行圖像識別、分析和理解的基礎。

5、圖像描述：

圖像描述是圖像識別和理解的必要前提。

一般圖像的描述方法採用二維形狀描述，它有邊界描述和區域描述兩類方法。對於特殊的紋理圖像可採用二維紋理特徵描述。

6、圖像分類：

圖像分類屬於模式識別的范疇，其主要內容是圖像經過某些預處理（增強、復原、壓縮）後，進行圖像分割和特徵提取，從而進行判決分類。

圖像分類常採用經典的模式識別方法，有統計模式分類和句法模式分類。

(1)波陣面演算法等距擴展閱讀：

圖像處理主要應用在攝影及印刷、衛星圖像處理、醫學圖像處理、面孔識別、特徵識別、顯微圖像處理和汽車障礙識別等。

數字圖像處理技術源於20世紀20年代，當時通過海底電纜從英國倫敦到美國紐約傳輸了一幅照片，採用了數字壓縮技術。

數字圖像處理技術可以幫助人們更客觀、准確地認識世界，人的視覺系統可以幫助人類從外界獲取3/4以上的信息，而圖像、圖形又是所有視覺信息的載體，盡管人眼的鑒別力很高，可以識別上千種顏色，

但很多情況下，圖像對於人眼來說是模糊的甚至是不可見的，通過圖象增強技術，可以使模糊甚至不可見的圖像變得清晰明亮。

② 推進波前法

經過近年來的發展，推進波前法(Advancing Front Technique，AFT)已經成為通用的全自動非結構化有限元網格生成方法之一。該方法最初由Lo提出並用於平面區域三角形網格自動生成(Lo，1985)。AFT方法具有生成的邊界網格質量高、易於自適應加密等優點，但不同於Delaunay三角剖分演算法，它沒有後者那樣成熟的理論依據，在很多情形下靠經驗解決問題，但是這並不妨礙它的成功應用。

推進波前法的基本思路是:按照剖分規模將邊界離散成有序線段，然後從邊界出發，依次以邊界線段為三角形的一條邊，在邊界點與內部點中尋找合適點，組成三角形，選取組成三角形頂角最大的點為最終三角形頂點;將已形成三角形的邊界線段從邊界鏈表中刪除，形成新邊界;重復上述過程直到除邊界外的三角形的邊兩側均有三角形為止。為了更好地說明該演算法，下面先介紹幾個術語。

3.3.1.1 二維AFT方法術語定義

(1)剖分域:即需要剖分的區域。正確地定義剖分域(區域的幾何描述)是網格能夠正常生成的必要條件。剖分域是由一系列有向邊界曲線圍成的連通域，並且每條邊界曲線必須是簡單封閉曲線。通常情況下，剖分域的外邊界按照逆時針排列，而內邊界則按照順時針排列。

(2)前沿Ω:所有未剖分區域的邊界線段以及端點的集合構成Ω，前沿包括活躍前沿(記為Ω₁)和非活躍前沿(記為Ω₂)，其中活躍前沿為當前正在推進的前沿，非活躍前沿為暫時不推進的前沿。

(3)選定前沿S:選定前沿S是Ω中的一個元素。S的選取取決於網格的生成策略，如果為了保證生成網格的尺寸過渡以及保證小尺寸單元優先生成，一般選取Ω中的最小前沿作為S。如果為了程序實現上的便利，則從Ω中從前往後依次選定一個元素作為選定前沿S。

3.3.1.2 演算法要點

(1)選取合適的數據結構建立點、邊、三角形之間的關系，並建立儲存點、邊與三角形的鏈表。

(2)選取合適的驅動方式。如以三角形的邊為基礎進行波陣式擴展，必須考慮邊的使用次數與方向:任何位於區域邊界上的邊應且只應使用1次，任何位於區域內部的邊應且只應使用2次(正、反方向各1次)。因此，在初始狀態，應將邊界邊的使用次數賦1，內部邊使用次數賦0。

(3)以邊為基礎進行波陣式擴展，是以某邊為三角形的一條邊，再從點集中尋找合適的頂點組成三角形的過程。所尋找到的點必須滿足以下要求:新形成邊與已生成的邊不能相交;所有邊必須滿足使用次數要求(邊界邊使用一次，其餘邊使用兩次);新頂點與該邊(有方向)組成的三角形面積必須大於零;保證頂角最大。

3.3.1.3 演算法與程序代碼

平面區域的AFT方法主要有三大步:向剖分域中布點、離散剖分域的邊界和推進前沿生成三角形。

3.3.1.3.1 布點

布點即是根據需要得到的三角形單元的各邊的大概長度，在剖分域內生成一系列的散亂點。最常用的方法是先根據剖分域邊界上端點的x和y坐標的最大值和最小值，生成一個包含剖分域的矩形，該矩形也叫做剖分域的包圍盒;再在矩形中生成點，最簡單的是生成「棋盤狀」的一系列點，另外是生成「正三角形狀」的一系列點;生成一系列點之後，判斷這些點是否落在區域內，若是，則為需要布設的數據點，否則，刪除;同時需要注意的是若某些點落在了區域內，但是又距離邊界太近，依舊刪除這些點。圖3.9中(a)為剖分域，(b)則是布設「正三角形狀」點的結果。

圖3.9 在平面區域中布點

3.3.1.3.2 離散邊界

離散邊界即是按照剖分規模或需要得到的三角形單元的各邊的大概長度將邊界離散成有序線段，如圖3.10所示，為布點之後進行離散邊界的結果。

圖3.10 離散邊界

3.3.1.3.3 生成三角形

以三角形的邊為基礎進行波陣式擴展生成三角形，即以三角形的邊為推進前沿，主要過程有如下4小步。

第一步:建立點集PS和邊集ES。初始點集PS包括所有布設的數據點和邊界離散後小線段的端點。初始邊集ES只包括邊界離散後的有向線段。此時，邊集ES就是前沿Ω。

第二步:以邊集ES中的邊E_i為基礎搜索頂點P_i，即選定E_i作為選定前沿S，以該點為頂點、該邊為一邊形成三角形。設E_i的端點為A與B，所有待選點P_i與E_i組成的頂角為∠AP_iB，將頂角從大到小排序，從最大頂角開始，依次選擇對應的頂點P_i與E_i組成三角形。如果形成的三角形滿足以下要求，則為新三角形，P_i為合適的頂點:①新形成三角形的邊與已生成的邊不能相交;②所有邊必須滿足使用次數要求;③新頂點與該邊(有方向)組成的三角形面積必須大於零。如果不滿足則選下一個頂點。

第三步:找到合適頂點後，將新頂點與選定前沿S(即邊E_i)的端點連成的邊加入到邊集中，生成新的前沿Ω的元素，並將新形成的三角形加入到三角形集中，刪除原選定前沿S，選定邊集ES中的下一條邊作為選定前沿S。

第四步:重復第二、三步，當所有邊滿足使用次數要求時循環結束。圖3.11中，(a)、(b)和(c)依次為循環一步、二步和多步之後形成的三角形，當循環結束時得到的三角剖分如圖3.12所示。

圖3.11 推進前沿過程

三維地質建模方法及程序實現

函數CreateTrgls()中調用的函數SearchID()搜索某一點在頂點集合surf-＞pNodes的ID;函數CountCos()用於計算當一條線段/邊搜索到一頂點並組成三角形時該頂點處角度的餘弦值;函數SameLine()用於判斷兩條線段/邊是否相同。

3.3.1.4 約束的處理

區域三角剖分中的約束是指待剖分區域中存在特定的點或線，稱為點約束或線約束，其中約束點必須是剖分後網格的頂點，而約束線必須是剖分後網格三角形的邊的集合，不存在某個三角形跨越約束線的狀況。

3.3.1.4.1 點約束的處理方法

點約束的處理非常簡單，直接將約束點加入到生成的點集中，再刪除與約束點距離非常近的點，然後就可以按無約束的方法進行三角剖分了。

3.3.1.4.2 線約束的處理方法

當待剖分區域存在線約束時，可以將所有線約束作為一種邊界。在剖分前，與外邊界及內邊界的處理方法一樣，先按照一定的規模將約束線離散成順序連接的線段，每條線段均作為三角網格的邊，然後設置約束線上的邊的使用次數為0，並加入到原始邊集中，再按照按無約束的方法進行三角剖分即可完成約束三角剖分。圖3.13(a)為含線約束的待剖分區域，圖3.13(b)為約束剖分網格。

圖3.13 約束三角剖分實例

③ pso的演算法結構

對微粒群演算法結構的改進方案有很多種，對其可分類為：採用多個子種群；改進微粒學習對象的選取策略；修改微粒更新迭代公式；修改速度更新策略；修改速度限制方法、位置限制方法和動態確定搜索空間；與其他搜索技術相結合；以及針對多模問題所作的改進。
第一類方案是採用多個子種群。柯晶考慮優化問題對收斂速度和尋優精度的雙重要求並借鑒多群體進化演算法的思想，將尋優微粒分成兩組，一組微粒採用壓縮因子的局部模式PSO演算法，另一組微粒採用慣性權重的全局模式PSO演算法，兩組微粒之間採用環形拓撲結構。對於高維優化問題，PSO演算法需要的微粒個數很多，導致計算復雜度常常很高，並且很難得到好的解。因此，出現了一種協作微粒群演算法（Cooperative ParticleSwarm Optimizer, CPSO-H），將輸入向量拆分成多個子向量，並對每個子向量使用一個微粒群來進行優化。雖然CPSO-H演算法使用一維群體來分別搜索每一維，但是這些搜索結果被一個全局群體集成起來之後，在多模問題上的性能與原始PSO演算法相比有很大的改進。Chow使用多個互相交互的子群，並引入相鄰群參考速度。馮奇峰提出將搜索區域分區，使用多個子群並通過微粒間的距離來保持多樣性。陳國初將微粒分成飛行方向不同的兩個分群，其中一分群朝最優微粒飛行，另一分群微粒朝相反方向飛行；飛行時，每一微粒不僅受到微粒本身飛行經驗和本分群最優微粒的影響，還受到全群最優微粒的影響。Niu在PSO演算法中引入主—從子群模式，提出一種多種群協作PSO演算法。Seo提出一種多組PSO演算法（Multigrouped PSO），使用N組微粒來同時搜索多模問題的N個峰。Selleri使用多個獨立的子群，在微粒速度的更新方程中添加了一些新項，分別使得微粒向子群歷史最優位置運動，或者遠離其他子群的重心。王俊年借鑒遞階編碼的思想，構造出一種多種群協同進化PSO演算法。高鷹借鑒生態學中環境和種群競爭的關系，提出一種基於種群密度的多種群PSO演算法。
第二類方案是改進微粒學習對象的選取策略。Al-kazemi提出多階段PSO演算法，將微粒按不同階段的臨時搜索目標分組，這些臨時目標允許微粒向著或背著它自己或全局最好位置移動。Ting對每個微粒的pBest進行操作，每一維從其他隨機確定的維度學習，之後如果新的pBest更好則替換原pBest；該文還比較了多種不同學習方式對應的PSO演算法的性能。Liang提出一種新穎的學習策略CLPSO，利用所有其他微粒的歷史最優信息來更新微粒的速度；每個微粒可以向不同的微粒學習，並且微粒的每一維可以向不同的微粒學習。該策略能夠保持群體的多樣性，防止早熟收斂，可以提高PSO演算法在多模問題上的性能；通過實驗將該演算法與其它幾種PSO演算法的變種進行比較，實驗結果表明該演算法在解決多模復雜問題時效果很好。Zhao在PSO演算法中使用適應值最好的n個值來代替速度更新公式中的gBest。Abdelbar提出一種模糊度量，從而使得每個鄰域中有多個適應值最好的微粒可以影響其它微粒。Wang也採用多個適應值最好的微粒信息來更新微粒速度，並提出一種模糊規則來自適應地確定參數。崔志華提出一種動態調整的改進PSO演算法，在運行過程中動態調整極限位置，使得每個微粒的極限位置在其所經歷的最好位置與整體最好位置所形成的動態圓中分布。與原始PSO演算法相反，有一類方法是遠離最差位置而非飛向最優位置。Yang提出在演算法中記錄最差位置而非最優位置，所有微粒都遠離這些最差位置。與此類似，Leontitsis在微粒群演算法中引入排斥子的概念，在使用個體最優位置和群體最優位置信息的同時，在演算法中記錄當前的個體最差位置和群體最差位置，並利用它們將微粒排斥到最優位置，從而讓微粒群更快地到達最優位置。孟建良提出一種改進的PSO演算法，在進化的初期，微粒以較大的概率向種群中其他微粒的個體最優學習；在進化後期，微粒以較大的概率向當前全局最優個體學習。Yang在PSO演算法中引入輪盤選擇技術來確定gBest，使得所有個體在進化早期都有機會引領搜索方向，從而避免早熟。
第三類方案是修改微粒更新公式。Hendtlass在速度更新方程中給每個微粒添加了記憶能力。He在速度更新方程中引入被動聚集機制。曾建潮通過對PSO演算法的速度進化迭代方程進行修正，提出一種保證全局收斂的隨機PSO演算法。Zeng在PSO演算法中引入加速度項，使得PSO演算法從一個二階隨機系統變為一個三階隨機系統，並使用PID控制器來控制演算法的演化。為了改進PSO演算法的全局搜索能力，Ho提出一種新的微粒速度和位置更新公式，並引入壽命（Age）變數。
第四類方案是修改速度更新策略。Liu認為過於頻繁的速度更新會弱化微粒的局部開采能力並減慢收斂，因此提出一種鬆弛速度更新（RVU）策略，僅當微粒使用原速度不能進一步提高適應值時才更新速度，並通過試驗證明該策略可以大大減小計算量並加速收斂。羅建宏對同步模式和非同步模式的PSO演算法進行了對比研究，試驗結果表明非同步模式收斂速度顯著提高，同時尋優效果更好。Yang在微粒的更新規則中引入感情心理模型。Liu採用一個最小速度閾值來控制微粒的速度，並使用一個模糊邏輯控制器來自適應地調節該最小速度閾值。張利彪提出了對PSO演算法增加更新概率，對一定比例的微粒並不按照原更新公式更新，而是再次隨機初始化。Dioan利用遺傳演算法（GA）來演化PSO演算法的結構，即微粒群中各微粒更新的順序和頻率。
第五類方案是修改速度限制方法、位置限制方法和動態確定搜索空間。Stacey提出一種重新隨機化速度的速度限制和一種重新隨機化位置的位置限制。Liu在[76]的基礎上，在PSO演算法中引入動量因子，來將微粒位置限制在可行范圍內。陳炳瑞提出一種根據微粒群的最佳適應值動態壓縮微粒群的搜索空間與微粒群飛行速度范圍的改進PSO演算法。
第六類方案是通過將PSO演算法與一些其他的搜索技術進行結合來提高PSO演算法的性能，主要目的有二，其一是提高種群多樣性，避免早熟；其二是提高演算法局部搜索能力。這些混合演算法包括將各種遺傳運算元如選擇、交叉、變異引入PSO演算法，來增加種群的多樣性並提高逃離局部最小的能力。Krink通過解決微粒間的沖突和聚集來增強種群多樣性，提出一種空間擴展PSO演算法（Spatial ExtensionPSO，SEPSO）；但是SEPSO演算法的參數比較難以調節，為此Monson提出一種自適應調節參數的方法。用以提高種群多樣性的其他方法或模型還包括「吸引—排斥」、捕食—被捕食模型、耗散模型、自組織模型、生命周期模型（LifeCycle model）、貝葉斯優化模型、避免沖突機制、擁擠迴避（Crowd Avoidance）、層次化公平競爭（HFC）、外部記憶、梯度下降技術、線性搜索、單純形法運算元、爬山法、勞動分工、主成分分析技術、卡爾曼濾波、遺傳演算法、隨機搜索演算法、模擬退火、禁忌搜索、蟻群演算法（ACO）、人工免疫演算法、混沌演算法、微分演化、遺傳規劃等。還有人將PSO演算法在量子空間進行了擴展。Zhao將多主體系統（MAS）與PSO演算法集成起來，提出MAPSO演算法。Medasani借鑒概率C均值和概率論中的思想對PSO演算法進行擴展，提出一種概率PSO演算法，讓演算法分勘探和開發兩個階段運行。
第七類方案專門針對多模問題，希望能夠找到多個較優解。為了能使PSO演算法一次獲得待優化問題的多個較優解，Parsopoulos使用了偏轉（Deflection）、拉伸（Stretching）和排斥（Repulsion）等技術，通過防止微粒運動到之前已經發現的最小區域，來找到盡可能多的最小點。但是這種方法會在檢測到的局部最優點兩端產生一些新的局部最優點，可能會導致優化演算法陷入這些局部最小點。為此，Jin提出一種新的函數變換形式，可以避免該缺點。基於類似思想，熊勇提出一種旋轉曲面變換方法。
保持種群多樣性最簡單的方法，是在多樣性過小的時候，重置某些微粒或整個微粒群。Lvbjerg在PSO演算法中採用自組織臨界性作為一種度量，來描述微粒群中微粒相互之間的接近程度，來確定是否需要重新初始化微粒的位置。Clerc提出了一種「Re-Hope」方法，當搜索空間變得相當小但是仍未找到解時（No-Hope），重置微粒群。Fu提出一種帶C-Pg變異的PSO演算法，微粒按照一定概率飛向擾動點而非Pg。赫然提出了一種自適應逃逸微粒群演算法，限制微粒在搜索空間內的飛行速度並給出速度的自適應策略。
另一種變種是小生境PSO演算法，同時使用多個子種群來定位和跟蹤多個最優解。Brits還研究了一種通過調整適應值計算方式的方法來同時找到多個最優解。Li在PSO演算法中引入適應值共享技術來求解多模問題。Zhang在PSO演算法中採用順序生境（SequentialNiching）技術。在小生境PSO演算法的基礎上，還可以使用向量點積運算來確定各個小生境中的候選解及其邊界，並使該過程並行化，以獲得更好的結果。但是，各種小生境PSO演算法存在一個共同的問題，即需要確定一個小生境半徑，且演算法性能對該參數很敏感。為解決該問題，Bird提出一種自適應確定niching參數的方法。
Hendtlass在PSO演算法中引入短程力的概念，並基於此提出一種WoSP演算法，可以同時確定多個最優點。劉宇提出一種多模態PSO演算法，用聚類演算法對微粒進行聚類，動態地將種群劃分成幾個類，並且使用微粒所屬類的最優微粒而非整個種群的最好微粒來更新微粒的速度，從而可以同時得到多個近似最優解。Li在PSO演算法中引入物種的概念，但是由於其使用的物種間距是固定的，該方法只適用於均勻分布的多模問題；為此，Yuan對該演算法進行擴展，採用多尺度搜索方法對物種間距加以自適應的調整。
此外，也有研究者將PSO演算法的思想引入其他演算法中，如將PSO演算法中微粒的運動規則嵌入到進化規劃中，用PSO演算法中的運動規則來替代演化演算法中交叉運算元的功能。