步长加速算法对powell算法在图像配准中的改进研究

贾亮，孙成林

                沈阳航空航天大学  电子与通信工程学院  110136

摘要：利用powell算法进行图像配准的过程中，由于其局部搜索能力强，无需进行梯度计算的优点而被广泛采用，但是在收敛速度和全局搜索能力上仍可提高。步长加速算法通过改变搜索步长可以有效地加快收敛速度，一定程度上提高全局搜索能力，因此将步长加速算法和powell算法进行结合，可以提高powell算法的运算速度。

关键词：powell算法 ；图像配准；步长加速算法；运算速度

Research on improvement of step acceleration algorithm for Powell algorithm in image registration

Jia Liang,Sun Chenglin

School of Electronic and Communication Engineering ,Shenyang Aerospace University  110136

Abstract: in the process of image registration using Powell algorithm, because of its strong local search ability, it is widely adopted without the advantage of gradient calculation, but the convergence speed and global search ability can still be improved. The step acceleration algorithm can effectively accelerate the convergence speed by changing the search step, and improve the global search ability to a certain extent. Therefore, combining the step acceleration algorithm with the Powell algorithm can improve the speed of the Powell algorithm.
  Key words: Powell algorithm; Image registration; Step-length acceleration algorithm; Operation speed

  图像融合的关键在于图像配准，图像配准就是通过建立空间模型，寻找进行配准的两幅图像之间的图像特征点，利用合适的搜索策略搜索最大相识度的过程。目前图像研究领域将互信息值作为图像配准的主要研究方向，主要因为利用图像的最大互信息值进行图像配准时具有计算量小，无需进行图像分割，配准的精度较高，同时具有鲁棒性好的特点。

图像配准的过程中通常需要合适的搜索策略进行配准信息的搜索。Powell算法作为目前十分流行的搜索策略，但是存在着容易陷入局部极值，影响配准精度。而步长加速算法，通过搜索过程中步长改变，可以降低局部极值的影响，加快收敛速度，加强全局搜索能力。通过步长加速算法和powell算法的结合，可以帮助powell算法再配准过程中提高图像配准精度，提高收敛速度。

1 图像配准原理

1.1图像的特征空间

图像的特征空间通常指从参考图像和浮动图像之间提取的有效特征。本文利用灰度图像为配准图像，灰度图像的特征点通常为图像像素的灰度点。利用图像的特征进行图像配准时，则将图像的点，线，边缘等作为特征空间要素。对于图像点的特征检测一般采用空间滤波的方式；对于图像的线检测通常采用Hough变换原理。对于图像的边缘检测多产用导数原理进行边缘检测^[1]。

1.2图像的搜索策略

图像的搜索策略是为了在对特征空间搜索时，搜索最优的特征参数，搜素策略的效果则用搜索过程中的相似行度量值进行评判。进行图像配准的过程中，需要进行较多的数字计算，而有效的搜索策略不仅决定了图像配准的速度，也对图像的融合效果具有一定的影响。目前常用的搜索策略分为黄金分割法，插值法，powell算法，牛顿法，遗传算法，蚁群算法等。

1.3 最大互信息值测度

互信息通常指两个图像系统之间的相关性，也可以理解为一个图像系统内具有另一个图像系统的信息量。一般用熵表示^[2]，公式如下：

                       (1)

 其中表示参考图像，表示浮动图像，表示最大互信息值。其中表示参考图像的熵；表示浮动图像的熵；表示已知浮动图像时参考图像的条件熵。

其中              =        （2）

                           （3）  

   （4）  

其中表示参考图像完全独立的概率分布，表示浮动图像完全独立时的概率分布，表示参考图像和浮动图像的联合概率分布。

将公式（2）（3）（4）分别带入公式（1）化解整理得

                   （5）

1.4 PV插值计算联合直方图

灰度插值法主要用于解决像素图像灰度级的赋值问题。联合直方图则是用以统计两幅图像对应点的灰度级数值出现的次数。联合直方图通常用二维图像表示，图像的X轴表示参考图像的灰度极值，图像的Y轴表示参考图像的弧度极值。如果参考图像和浮动图像的完全符合，那么图像的点则分布在斜率为1的斜线上。两幅图像的相识度越低，图像的点越分散。

Pv插值法则是专门用于两幅图像的联合直方图的插值计算技术^[3]。PV插值法计算过程如下图：图中表示联合直方图函数，为经过反向变换求得的浮点数点，N1,N2,N3,N4则表示相邻的四个像素点。 表示参考图像，表示浮动图像。

   (8)             （9）

     (10)                    (11)

2图像配准算法

2.1 步长加速算法

步长加速算法作为一种直接算法，不需要进行梯度计算。具有较强的收敛速度和全局搜索能力。步长加速算法由探测移动和模式搜索两部分组成。在实际运用中，根据不同的要求重复执行其中一部分甚至两部分都执行^[4]。主要实现步骤如下：

2.2 powell优化算法

  Powell算法通过比较归一化互信息值的大小，进行迭代，最终求得目标极值。原有的powell算法存在着搜索过程中无法保证搜索方向的线性无关性，因此目前使用的powell算法多为优化后的powell算法。改良后的powell算法^[5]流程如下：

 （1）设定初始点,设定误差>0，设定个线性无关方向，…，方向向量均为单位向量，设定。

  （2）令，将作为此轮搜索初始点，沿着，…方向进行一维搜索。得到搜索后的对应位置，…。对应点的函数值则用pv插值法求解。设点求得

        (12)

新的搜索方向 ：    

如果>||||，停止搜索，否则继续下一步（3）。

 （3）设定系数，满足

 ，求得目标函数极大值时的。利用

求出极大值点对应的相关参数。

如果||||<.算法终止迭代，否则进行下一步（4）。

 （4）如果

||>表明算法共轭性满足要求，那么令

否则在保持现有搜索方向的前提下，令

  转到（2）进行新的搜索。

3步长加速算法对powell算法的改进

    图像配准的过程中，由于图像本身的特征点具有区域分布特点，因此进行一维搜索时通过结合步长加速算法改变搜索步长不仅可以影响图像相关系数的变化，同时可以将对极值点的搜索在一定程度上扩展为极值区域上的搜索。搜索时先搜索一定区域然后对极值点进行搜索可以在一定程度上减少极值点对比时间，也有利于增强全局搜索能力。一维搜索完成后结合改进的powell算法，以保证搜索方向的线性无关性，从而进行多轮迭代，求得最优极值。具体算法流程如下：  (1)设定搜索初始点，搜索误差>0，个搜索方向 ，设定初始搜索步长为，同时置。

(2)将作为轮搜索初始点，。计算和，如果则从点沿移动搜索。如果,则令，如果，则从点沿方向移动搜索。如果则让搜索点从点沿方向移动搜索，转向(3)。如果均不符合，则令，返回（1）。

(3)根据（2）步骤理念完成对个方向的搜索。求得最优点值时的方向。满足

最大互信息值变换最快的点方向为，如果||||,运算停止，就是最优互信息点。否则进行（4）。

(4)按照步长加速算法中模式搜索理念，模式搜索方向为－等同于此时搜索点  ，如果 ，此时求出相应步长。令－，如果此时满足||||，那么停止搜索。则此点为此轮最优点。否则进行（5）。

(5)为了保障搜索方向的共轭性，对搜索方向进行确认，搜索步长满足    

则将轮的迭代方向在搜索函数值最大点之前的方向均与第轮相同，将点方向去掉，将－加上，形成新的方向组。否则就令和轮方向相同，转到（2）

4实验结果分析

选取了以下两幅图片分别为参考图像和浮动图像。为了保证配准的准确度，两幅图像的大小均为689*2862。运算过程中将误差设定为0.1，初始点为[0 0 0]。运算结果如下：图像A为参考图像，图像B为浮动图像，图像C为融合后图像。

由上图可知，改进后的算法可以实现图像配准。为了验证改进的算法能否加快配准速度。我们在相同的实验条件下，分别对原有powell算法和改进后的算法各进行三次配准，配准数据结果如下：

配准参数结果对比

Powell    互信息值        配准运算时间        powell运算时间

1       4.8609              10.850                   9.327

2       4.8609              10.677                   9.238

3       4.8609              10.872                   9.383

改进算法    互信息值       配准运算时间      改进算法运算时间

1           4.8609              10.469                8.990

2           4.8609              10.359                8.986

3           4.8609              10.366              8.980

上述实验结果是通过原算法和改进算法各进行三次运算求得的实验数据。由数据可以发现，powell算法本身的运算速度虽然较快，但是通过融合步长加速算法理念后，其收敛速度得以提升，进而促进了整个配准时间的缩短。由此可以证明，在进行图像配准的过程中，由于将图像的归一化互信息作为配准测度，利用步长加速算法进行粗配准，连接powell算法进行具体规划，可以提升搜索速度，并且在一定程度上保证了搜索方向的线性无关性。

参考文献：

[1]  陈显毅.图像配准技术及其MATLAB编程实现[M].北京：电子工业出版社，2009.5

[2]  Dobrushin R L.General formulation of shannon’ s main theorem in information[J].Uspekhi Mat Nauk,1959,14(3):92-104.

[3]  Maes F，Collignon A，Vandermeulen D，et al.Multimodality image registration by maximization of mutual information[J].IEEE Transactions on Medical Imaging，1997，(2):187-198

[4] 栗塔山.最优化计算原理与算法程序设计.长沙：国防科技大学出版社，2001.2

[5]  李乔亮，汪国有，刘建国，等．基于样条金字塔和互信息的快速图像配准［J］．计算机应用研究，2009.26(5):1949-1950,1960.

   LI Qiaoliang, WANG Guoyou,LIU jianguo,et al.Fast image registration based on spline pyramid and mutual informations[J].Application Research of Computers,2009,26(5):1949-1950,1960.