基于PSO智能优化的SFS三维重构算法研究

󰀁󰀁󰀁󰀁计算机工程与科学

COMPUTERENGINEERING&SCIENCE

2008年第30卷第11期󰀁󰀁Vol󰀁30,No󰀁11,2008󰀁

文章编号:1007󰀁130X(2008)11󰀁0021󰀁04

*

基于PSO智能优化的SFS三维重构算法研究

ResearchontheSFS3DReconstruction

AlgorithmBasedonthePSOIntelligentOptimization

班晓娟,李󰀁欣,宁淑荣,景俊杰

BANXiao󰀁juan,LIXin,NINGShu󰀁rong,JINGjun󰀁jie

(北京科技大学信息工程学院,北京100083)

(SchoolofInformationEngineering,BeijingUniversityofScienceandTechnology,Beijing100083,China)

摘󰀁要:智能优化算法在优化计算、搜索和人工智能方面有着广泛的应用潜力。为了提高三维重构模型的逼真度,本文把智能优化算法中的PSO算法应用在SFS算法改进中,并应用基准测试函数对算法进行仿真比较,最后分析了算法的性能效率与收敛性。可以看出,优化后的SFS算法性能有了显著提高。

Abstract:Particleswarmoptimization(PSO)isanewheuristicglobaloptimizationtechniquebasedonswarmintelli󰀁gence.Toimprovethefidelityof3Dreconstruction,thispaperusesaPSOalgorithmtooptimizetheSFSalgorithmanda󰀁doptsthebasictestfunctiontoperformemulationandcomparisons.Intheend,weanalysetheperformanceandconvergencespeedoftheimprovedSFSalgorithm.Obviously,themethodhasbeenprovedremarkably.

关键词:智能优化算法;PSO算法;SFS算法;算法性能

Keywords:intelligentoptimizedalgorithm;PSO;SFS;algorithmperformance中图分类号:TP18;TP391.9文献标识码:A

面元方法、启发式方法等,还有近几年提出的神经网络方

1󰀁引言

SFS(ShapeFromShading,简称SFS)是计算机视觉领域中三维形貌恢复的热门问题,是进行图像理解和三维目标识别的关键技术之一。

通常采用的三维表面重构手段主要有两种:一种是采用多目或多目视觉方法,即立体视觉方法;另一种是试图仅利用一幅图像上的灰度明暗变化,在单一的光源条件为已知的情况下,来恢复三维物体表面的形状及表面方向,即本文所讲的SFS算法。

自从1975年由Horn提出的SFS思想以来,早期的SFS方法主要基于变分法思想,考虑图像的辐射度和反射图之间的整体误差,将问题转化为求解目标函数的极小值,得到一组Euler方程,该方程主要用迭代方法求解。然而,SFS中使用变分法有内在困难,如PDE求解唯一性问题、非线性PDE的线性化误差等。经过几十年的发展,其他学者在Horn的基础上提出了多种SFS方法:频域方法、三角

法。但是,由于这些方法都利用了物体的局部或整体形状

的各种约束条件来获取其表面各点的相对高度或表面法方向等参数值,这些条件使得SFS算法产生一系列问题,如不确定性、算法的不稳定性及局限性、SFS还不适用于复杂的情况并且不能直接用于真实的应用环境,最重要的是得出的结果都不令人满意。

2󰀁PSO算法和SFS算法

2.1󰀁PSO算法󰀁󰀁󰀁智能群体优化算法

智能优化算法是模仿自然界规律而设计的求解问题的算法。而群智能[1,2](SwarmIntelligence)是由众多无智能的简单个体组成的群体,通过相互间的简单合作表现出智能行为的特性。自然界中的动物常以集体的力量觅食生存,这些群落中单个个体的行为是相同的且缺乏智能,而由个体组成的群体则表现了一种有效的复杂智能行为。群智能可以在适当的进化机制引导下通过个体交互以某种突现

*

收稿日期:2008󰀁02󰀁26;修订日期:2008󰀁05󰀁20

基金项目:国家自然科学基金资助项目(60503024)作者简介:班晓娟(1970󰀁),女,天津人,博士,副教授,CCF会员(E20󰀁0006262S),研究方向为人工智能、数据挖掘等;李欣,硕士,研究方向为人工智能和图像处理;宁淑荣,博士,讲师,研究方向为人工智能和图像处理。

通讯地址:100083北京市北京科技大学信息工程学院;Tel:(010)62334980;E󰀁mail:HTUbanxj@ies.ustb.edu.cnAddress:SchoolofInformationEngineering,BeijingUniversityofScienceandTechnology,Beijing100083,P.R.China

21形式起作用。典型的方法有DorigoM提出的蚁群算法和KennedyJ与EberthartR提出的微粒群算法PSO[3]。

微粒群优化算法(PSO)是一种基于群体智能的计算模型[4]。PSO算法是基于个体的协作与竞争来完成复杂搜索空间中最优解的搜索,是一种基于群体智能方法的进化计算技术。这种算法不但可用于科学研究也可用于工程应用。目前,PSO算法已经引起了进化计算、优化及其它领域的广泛关注。

局部极值的复杂函数而言,遗传算法往往在优化的收敛速

度和精度上难以达到期望的要求。

粒子群优化算法(PSO)源于鸟类捕食行为的模拟[5,6]。Shi与Eberhart的实验证明,对大多数的非线性Benchmark函数,PSO在优化速度和精度上均较遗传算法有一定的改善。因此,本文选择PSO算法来优化SFS算法。

针对SFS算法中亮度方程(见式(1))的求解,粒子可以直接编码为(x,y),而将适应度函数定义为待优化函数本身,即直接用待优化的目标函数(亮度方程)转化为适应度函数,然后按照PSO算法的步骤进行求解。

应用PSO算法解决优化问题有两个重要步骤:问题解的编码和适应性函数的选择。PSO算法首先初始化一群随机粒子(Particle),每一个粒子都代表着优化问题的一个可能解,它有自己的位置和速度,粒子位置坐标对应的目标函数值作为该粒子的适应度[7]。在每次迭代中,各个粒子记忆、追随当前最优粒子,通过跟踪两个󰀁极值󰀁来更新自己:一个是粒子本身所找到的最优解,即个体极值pbest;另一个是整个种群目前找到的最优解,称为全局极值gbest。在找到这两个最优值后,粒子按照如下公式(2)和(3)进行迭代,更新自己的速度和位置。

设在D维搜索空间中,种群粒子数为n,xj=(xj1,xj2,󰀁,xjp)、vj=(vj1,vj2,󰀁,vjp)分别表示为第j个粒子的位置和速度,则每个粒子的速度和位置分别更新为:

Vj,d(t+1)=wvj,d(t)+c1*rand()*(pbestj,d(t)-xj,d(t))+

c2*rand()*(pbestd(t)-xj,d(t))

(2)

Xj,d(t+1)=xj,dt+vj,d(t+1),j=1,2,󰀁,D(3)其中,上标t、t+1表示当前代和下一代;pbestBj,d为粒子j达到最佳位置时第d维对应的位置坐标;gbestBdB为种群目前达到最佳位置时在第d维对应的位置坐标;w为惯性权系数;c1、c2为加速因子,通常设c1=c2=2;rand()为[0,1]之间的随机数。为减少粒子飞离搜索空间的可能性,将速度vj,d(t)限制在[-vdmax,vdmax]之间,vdmax决定了粒子飞行的最大距离。其中:

vdmax=k*xdmax,0.1󰀁k󰀁0.5

max

2.2󰀁SFS算法

SFS算法由图像重建物体表面的三维形状,即利用单幅图像灰度明暗变化来恢复物体表面三维形状,在一定的约束条件下从平滑变化的灰度图像恢复出表面的取向信息,即根据一个确定的反射模型建立物体表面形状与图像亮度之间的关系,然后对这些约束关系联立求解可得到物体表面的三维形状。

SFS算法的任务是利用单幅图像中物体表面的明暗变化来恢复其表面各点的相对高度或表面法方向等参数值,为进一步对物体进行三维重构奠定基础。

SFS算法可以归纳为四个方面:最小值方法、演化方法、局部分析法和线性化方法。这些算法在可靠性、稳定性、局限性以及实用性方面都存在一定的问题。传统的四种SFS方法都是以如下亮度方程为基础来求解的:

E(x,y)=R(p(x,y),q(x,y))=

cos󰀁-pcos󰀁sin󰀁-qsin󰀁sin󰀁󰀁=

1+p2+q2󰀁(cos(󰀁-󰀁)sin󰀁sin󰀁+cos󰀁cos󰀁)

(1)

其中,E为二维图像中像素点(x,y)的灰度值;表面方向p

=󰀁z/󰀁x,q=󰀁z/󰀁y是物体表面点高度z关于图像坐标的偏导数。󰀁是曲面反射率,󰀁是光源偏角(光源方向L与x󰀁z平面的夹角),󰀁是光源倾角(光源方向L与z轴正方向的夹角)。

完整的SFS算法首先是对控制参数的估计,随后进行算法的推导和实现。其中控制参数的估计包括对󰀁、󰀁、󰀁的估计。

一般的SFS算法是通过对亮度方程的变形和转变再加上限制条件进而求出极值得到结果的。

通过上面对两种算法的简单分析我们可以看出,PSO算法的主要优点在于群体搜索和个体相互作用寻优机制,它对于目标函数的形态没有特殊的要求,在求解时不依赖于梯度信息。鉴于以上特点以及PSO本身收敛速度快、参数设置少等优势,本文从智能优化算法入手,应用PSO算法将亮度方程转化为适应度方程,并且应用PSO方法对󰀁、󰀁、󰀁这三个参数进行调节,从而对SFS算法进行优化使得结果更为逼真。

(4)

其中,xd为搜索空间第d维位置的上界。

惯性权系数w用于控制算法的收敛特性。文献[5,6]的实验表明,惯性权系数w如果随算法迭代进行而线性减少,就能改善算法的收敛性能。通常w按下式进行调节:

w-wmin

w=wmax-max*iter(5)

itermax

其中,itermax为最大进化代数,iter为当前进化代数。

3.2󰀁估计控制参数󰀁、󰀁、󰀁

一组好的(x,y)像素组合能使图像生成更逼真,同时其优化算法定义的适应度函数值也越小。基于PSO算法的参数选择方法是:首先依据经验给出一组参数值,进行SFS算法训练;然后根据目标值的大小选择另一组参数再训练,直到得到满意的训练模型。利用PSO算法在参数󰀁、󰀁、󰀁所有可能取值组合的可行解中寻找最优解,使适应度函数值最小,这就是本文参数估值的思想。

利用PSO算法参数󰀁、󰀁、󰀁估值,首先将参数编码成如下形式的粒子编码串:[󰀁󰀂 ],通过一系列寻优迭代,获得最佳参数。以此来获得SFS算法适应度函数的较小值。

3󰀁PSO改进SFS算法

3.1󰀁转化亮度方程

我们遇到的很多问题本质上都是函数优化问题或者可以转换为函数优化问题进行求解的,对于函数优化已有一些成熟的解决方法,如遗传算法等。但是,对于超高维、多

22算法流程如下图1所示。

图4󰀁人脸的三维形状恢复

实验表明,本文的优化方法是一种有效的重构算法。克服了传统SFS算法解的唯一性差的问题。

由于PSO算法存在早熟和局部收敛的问题,为了分析本文改进后SFS算法的性能,以PSO算法和传统的SFS

图1󰀁用PSO算法优化SFS算法的流程图

图1中,第二步中适应度值是用给定的适应度函数(式(1))计算粒子中每一个粒子的适应度值;第三步中所有pbest中最佳的适应度值对应的位置设置为gbest;并不断迭代,直到到达最大迭代进化代数。

算法作为参照。针对收敛性能,本文用一个典型的Rasti󰀁grin复杂函数(式(6))对新算法进行测试。这一函数应用于测试静态和动态变量,针对算法的问题性质进行统计比较。

f(x)=

i=1

󰀁(x

10

i

2

-10cos(2󰀁xi)+10),xi󰀁[-100,100](6)

4󰀁仿真实验与分析

传统SFS算法的缺陷主要在于算法性能与收敛性,针对这几方面本文做了如下仿真分析。

对半球体的三维形状恢复效果图如图2所示。对形状复杂的花瓶三维形状恢复的效果图如图3所示。经典图片测试结果如图4所示。

󰀁󰀁测试函数存在全局最小值minf(0)=0。分别用PSO算法、传统的SFS算法以及本文算法求解。三种算法收敛趋势如图5所示。

图5󰀁三种算法的收敛趋势曲线图

结果表明,改进的算法较之PSO算法和SFS算法不但提高了全局寻优能力,而且有效避免了早熟收敛问题。

5󰀁结束语

SFS算法作为计算机视觉领域重要的研究方向,在工业、农业、国防、医学、空间技术等领域具有广泛的应用前景,如单幅人脸图片、解剖模型图片以及内窥镜图片等。本文提出了利用智能优化算法改进SFS三维重构算法的一种新的设计方法,所采用的PSO算法具有简单、计算效率高、收敛效果好并且鲁棒性强的优点。从结果可以看出,相

23比于其他优化算法,本文优化后的SFS算法求解的精度获得了显著的提高。这种新的SFS算法新颖、有效、简单且适用性广泛。新方法还将应用于863项目中,为工程建设提供了有效的途径。

参考文献:

[1]󰀁ParisiD.ArtificialLifeandHigherLevelCognition[J].Brain

andCognition,1997,34:160󰀁184.

[2]󰀁AdamiC.IntroductiontoArtificialLife[M].TELOS,1998:1󰀁

15.

[3]󰀁EberhartRC,ShiYH.ParticleSwarmOptimization:Devel󰀁

opments,ApplicationsandResources[C]󰀁ProcofCongressonEvolutionaryComputation,2001:81󰀁86.

[4]󰀁KennedyJ,EberhaRC.Particleswarmoptimization[C]󰀁

ProcoftheIEEEInt󰀁lConfonNeuralNetworks,1995:1942󰀁1948.

[5]󰀁KennedyJ,EberhartR.ParticleSwarmOptimization[C]󰀁

ProcoftheIEEEInt󰀁lConfonNeuralNetworks,1995:1942󰀁1948.

[6]󰀁ShiYH,EberhartRC.AModifiedParticleSwarmOptimi󰀁

zer[C]󰀁ProcoftheIEEEInt󰀁lConfonEvolutionaryCom󰀁putation,1998:69󰀁73.

[7]󰀁ChenJie,PanFeng,CaiTao.AccelerationFactorHarmoni󰀁

ousParticleSwarmOptimizer[J].InternationalJournalofAutomationandComputing,2006,3(1):41󰀁46.

(上接第20页)

12802条,其余为攻击数据。由于该数据集特征较多,我们首先对其进行约简,采用粗糙集[6]约简为如下14个特征。Service、flag、dst_bytes、count、srv_count、rerror_rate、srv_rerror_rate、srv_diff_host_rate、dst_host_count、dst_host_same_srv_rate、dst_host_diff_srv_rate、dst_host_same_src_port_rate、dst_host_srv_diff_host_rate、dst_host_srv_serror_rate。

由此确定遗传BP的输入层神经元个数为14。由于该数据集附加的标志位表示正常或者异常,因此遗传BP的输出层的神经元个数为1。我们设定隐藏层的神经元个数为4。其他参数设定如下:种群规模n=40,变异率Pm=0.1,交叉率Pc=0.6,染色体大小为40*65,迭代代数为100,权值和阀值的初始化范围为-25~25。

5󰀁结束语

利用GA全局搜索能力,本文对BP神经网络的权值进行优化,详细讨论了遗传BP神经网络参数设定、染色体与种群的产生、适应度的计算、遗传算子的设定,给出了遗传BP神经网络的算法,并将提出的算法用于异常检测之中。在KDDCUP󰀁99入侵数据上进行了实验,结果表明,提出的遗传BP神经网络算法权值优化速度远远快于一般的BP算法,意味着利用遗传BP神经网络算法能够快速地建立异常检测模型,为快速检测攻击提供支撑。本文是基于离线攻击数据进行实验的,下一步的工作是研究如何将该优化算法用于在线异常检测之中。

参考文献:

[1]󰀁McClellandR.ParallelDistributedProcessing:Explorations

intheMicrostructureofCognition.Vol1[M].Cambridge,MA:MITPress,1986.

[2]󰀁DavisL.HandbookofGeneticAlgorithms[M].NewYork:

VanNostrandReinhold,1991.

[3]󰀁MichalewiczZ.GeneticAlgorithm+DataStructure=Evolu󰀁

tionPrograms[M].2nded.NewYork:Springer󰀁Verlag,1994.

[4]󰀁李建珍.基于遗传算法的人工神经网络学习算法[J].西北师

范大学学报,2002,38(2):33󰀁37.

[5]󰀁[2007󰀁11󰀁15].http://kdd.ics.uci.edu/databases/kddcup99/

task.htm.

[6]󰀁PawlakZ.RoughSets[J].InternationalJournalofInforma󰀁

tionandComputerSciences,1982,11(5):341󰀁356.

4.2󰀁实验结果及分析

设定好各种参数,我们使用BP遗传网络算法对实验

数据进行测试,得到的标准BP算法实验结果如图1所示,遗传BP网络算法实验结果如图2所示。

对比图1和图2可知,BP算法迭代到第75代时才达到了遗传算法第一代的全局误差水平,遗传神经网络算法在14代时收敛,而BP算法在100代时收敛。而且,在同一误差限下(0.635到0.6226范围)遗传BP算法曲线下降明显比BP算法快。这说明本文所提出算法的性能优于BP算法。对于异常检测而言,意味着遗传BP算法能够快速地学习到网络权值,从而建立检测模型,实现对异常的快速检测。

24