波阵面算法等距

① 在图像处理中有哪些算法

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算法中的运动规则来替代演化算法中交叉算子的功能。