子图配准的随机搜索算法.pdf_大学文库

,.0I:10.13374/j.issn1001-053x.1982.02.027 北京钢铁学院学报 1982年第2期子图配准的随机搜索算法计算机教研室王乘钦摘要车本文给出了一种子图配准的随机搜索算法。搜索过程是纵随机选择的起点开始的。该点由在(0,1)区间上均匀分布的假随机数所产生。这一搜索过程是朝向匹配点逐步地进行的。本算法的优点已经由试验所证实。试验是在衡口尺寸与图片尺寸的比值=0.21的情况下进行的。一、引言子图配准（又称子图鉴定）是一种逐渐获得广泛应用的图片鉴定技术。它的基本任务是应用计算机搜肃区从给定的图片中找出预先规定的子图。即输出预定平移的子图以及它的位置。譬如说，从遥感图片中找出窗口预先指定的地域和它的坐标（如经纬度），或者在 ditatitht 巡航导弹的控制中用目标地区的景场匹配技术做为末制导，或者在公安技术中用来鉴定打印文件的铅字字型等等。 M-L 子图配准的传统算法是首先要确定一个匹配的图1 判据，然后在整个图片上逐行、逐列地搜索满足这一判据的子图。如果图片的尺寸较大时，这种算法的计算工作量是相当大的。设图1中，L是图片的边长尺度，M是子图的边长尺度，那么鉴定一幅图片所需要的计算工作量，不论采用交相关最大判据、平方误差最小判据还是绝对误差最小判据，都大致和M2(L-M)2成比例〔1,2)。如果把这个量选做表征计算工作量大小的一个标志数1，并引入相对尺度=M/L,那么 n=M2(L-M)2=L‘号2(1-)2 (1) 由(1)式可以看出，计算工作盘是与图片的边长的四次方成正比。当L增大时，η增大很快。因此在处理大尺度的图片时，如何节省计算工作量就是改进子图配准算法的主要目标。(1) 式右端的因子M2标志着在窗口内计算判据所需要化费的计算工作量。因为上述判据都是积分型的判据，所以计算工作量与窗口面积M2成正比，这是很自然的。在窗口尺度M较大的情况下(>0.5)，它是造成整个算法的计算量庞大的主要原因。因此如何减小窗口内的 :计算量就是主要的考虑因素。文献〔2)就是针对这种情况来讨论算法的改进问题的。 55

北京栩铁学眺 ’ 一报年第期子图配准的随机搜索算法庵犷计算机教研室王乘钦摘要本文给出了一种子图配准的随机搜索算法。搜索过程是纵随机选择的起点开始的。该点由在，区间上均匀分布的假随机数所产生。这一搜索过程是朝向匹配点逐步地进行的。本算法的优点已经由试验所证实。试验是在窗口尺寸与图片尺寸的比值息二的情况下进行的。一、引言子图配准又称子图鉴定是一种逐渐获得广泛应用的图片鉴定技术。它的基本任务是应用计算机从给定的图片中找出预先规定的子图。即输出预定的子图以及它的位置。替如说，从遥感图片中找出预先指定的地域和它的坐标如经纬度，或者在巡航导弹的控制中用目标地区的景场匹配技术做为末制导，或者在公安技术中用来鉴定打印文件的铅字字型等等。子图配准的传统算法是首先要确定一个匹配的搜索区平移，口一判据，然后在整个图片上逐行、逐列地搜索满足这一判据的子图。图如果图片的尺寸较大时，这种算法的计算工作最是相当大的。设图中，是图片的边长尺度，是子图的边长尺度，那么鉴定一幅图片所需要的计算工作量，不论采用交相关最大判据、平方误差最小判据还是绝对误差最小判据，都大致和 “ · 一成比例〔，幻。如果把这个里选做表征计算工作大小的一个标志数月，并引入相对尺度毛人，那么月么一， ‘ 息么一七由式可以看出，计算工作盘是与图片的边长的四次方成正比。当增大时， ” 增大很快。因此在处理大尺度的图片时，如何节省计算工作量就是改进子图配准算法的主要目标。式右端的因子标志着在窗口内计算判据所需要化费的计算工作。因为上述判据都是积分型的判据，所以计算工作遥与窗口面积成正比，这是很自然的。在窗口尺度较大的情况下七，它是造成整个算法的计算里庞大的主要原因。因此如何减小窗口内的计算就是主要的考虑因素。文献〔幻就是针对这种情况来讨论算法的改进问题的。挤 DOI ：10．13374／j ．issn1001－053x．1982．02．027

但是，决定整个算法的计算工作盆大小的，还有另外一个因素，那就是式右端的因子一所标志的部分。即在搜索区内搜索匹配点所需要的搜索次数。当窗口尺度较小时七，它是决定性的因素。譬如说，当七时，由于窗口相对而言很小，而搜索区很大，在搜索区内沿方向和方向逐点搜索所化的次数当然就要很多。这时，哪伯在窗口内的计算减少到一次运算，那么仍然无济于事，整个算法仍然需要一么次运算。也就是说在较小的情况下，节省窗口内的计算量对整个算法的改进意义不大。这时，选用什么样的判据，因而化费或多或少的计算最，由于窗口的积分面积很小，而对于整个算法的计算工作盆来说显得不甚重要了。重要的是减小搜索匹配点的搜索次数。传统算法的那种按每行、每列地逐点搜索，正是问题的症结所在。在搜索区内采用一种新的搜索方法来获得匹配点，以减小搜索次数，因而减小整个算法的计算工作量，这就是本文的出发点。啼伙二、随机搜索算法这个算法的基本思想是，在搜索区内随机地任选一点做为起点，然后沿着指向匹配点的最简捷的路径跨出一个适当的步距，到达新的一点。检查这一点是否是所要求的匹配点，如果不是，则按照以上的方式继续搜索前进。当无法到达目标点时其原因后面再讨论，则重新在一个新的随机点上起一步，仍按照上述方式搜索前进。这些随机选取的、互相不重覆的起点是在搜索区内按等概率均匀分布的伪随机序列，它是由一个专门的程序产生的。下面来具体地讨论这一算法。首先碰到的问超是如何描述平移窗口内的图象，为此需要定义一个二元函数，如下，、 … 、成簇一一一一令‘ ，尹、月，气一一丁称之为 “ 透明窗口 ” ，其定义域的域界是、，如图所示。如果令，，，那么， ’ 就成为一个二维的单位阶跃函数，这正和一元函数中的有因函数是类似的。引迸早

(x,y)函数会给分析工作带来了方便，因为可以通过它建立起给定的图象函数和窗口内的图象（子图）函数之间的联系。设给定的图象函数是G(X,Y),那么把窗口平移到搜索区的(X。,Y。)点处，窗口内的图象就是m。(x,y), W。(x,y)=2(x,y)G(x+Xo,y+Y。) (2) 参见图2b。再设模板函数T(x,y)。显然，T、W。的定义城的城界都是a,b。选用平方误差判据做为匹配的准则，因而有判据S。m如下： Sum(X..Y.)-JJ(W.(x,y)-T(x,y))-dxdy :1代入（2)式得影 Sum(X.,Y)-Jf(Q(x,y)G(x+X..y+Y.)-T(x,y))-d.d, 上述积分是在整个窗口内进行的。显然，Sum是(X。,Y。)的函数，而与积分变量x、y无关。如果图象函数G是可微的，那么可以对Sum(X。,Y。)求梯度如下， 85um(X,Y,)=20(x,y)G(x+Xy+Y,）-T(x,y)× 8 Q(x,y)'8X G(x+X.,Y+))d,d, 品sum(X,0=2fQ(x,-Gx+Xy+Y,)-Tx,y2× zrad(Sum(X.Y)(-(p.Sum(X.Y+(o.Sum(X.V.) (4) 注意公式(4)求偏导数的表达式中，第二个中括号的内容代表窗口图象函数的偏导数。既然是，匹配点(X。“Y。)处平方误差判据应为最小值（这是匹配点的充要条件），那么搜索匹配点的问题就变成搜索Sum的最小值问题。这一最小值为A,'它是匹配窗口内的高斯噪声所造成的误差总和，它是一个事先知道的先验统计量。只有当G(X,Y)是“光洁” 的图片（即未被噪声干扰过的图片），那么A=0。一般情况下，总可以按下式做一个函数 Su m(Xo,Yo)=umS(Xo,Y)-A* (5) ~显然，S。m在匹配点处，应满足下述充要条外 SaM(X。*,Y,*)=0 ok.SwuXt.Yt)-0 (6) 8Y Suw(X5,Yt)=0 也就是说，在(X,Y)点处，Sum的函数值与偏导数值皆为零。或者说它既是Sum的最小值点，又是零值点。有了以上的分析，现在就能够进一步具体地描述出这一算法的大致轮哪如下，在搜索区内任选一点P(XY,),计算该点的函数值S。m(X,Y)、偏导数值以及梯度矢量的模grad〔Sun)(X,Y),如果该点不满足条外(6)，那么沿着梯度矢量的反方向前进 4 67

公，函数会给分析工作带来了方便，因为可以通过它建立起给定的图象函数相窗口内的图象子图函数之间的联系。设给定的图象函数是，，那么把窗口平移到搜索区的。，。点处，窗口内的图象就是，。，，。，，，。参见图。再设模板函数，。显然，、。的定义域的域界都是，。选用平方误差判据做为匹配的准则，因而有判据。二如下，。代入式得，。， ’ 〔。 ‘ ，，一 ‘ ， ” ’ ’ 〔。一 · ‘ 。，，。，一 ‘ ，，，〕 ’ ‘ · ，上述积分是在整个窗口内进行的。显然，是。，。的函数，而与积分变、无关。如果图象函数是可微的，那么可以对。，。求梯度如下，，圣一。， · 。〔。 · ， · · 。。卜，〕。 ‘ ， · 爵。，〕，诀一。， ‘ ，，卜。，。卜，，〕、，。，、、，汤。，、、、，广。，、、匕气口气一少七二宁一、一少一气石石一、一尹万声廿口注意公式求偏导数的表达式中，第二个中括号的内容代表窗口图象函数的偏导数既然是，匹配点。朴。勺处平方误差判据应为最小值这是匹配点的充要条件，那么搜索匹配点的问题就变成搜索的最小值问题。这一最小值为，它是匹配窗口内的高斯噪声所造成的误差总和，它是一个事先知道的先验统计最。只有当，是 “ 光洁的图片即未被噪声干扰过的图片，那么长二。一般情况下，总可以按下式做一个函数。，。 “ 。，。一铃叫显然，。二在匹配点处，应满足下述充要条外。。气。瓷一 ‘ ，，，’ “ 。、 …… 夕歇一 ‘ ，，，’ 。也就是说，在言，朴点处，的函数值与偏导数值皆为零。或者说它既是的最小值点，又是零值点。有了以上的分析，现在就能够进一步具体地描述出这一算法的大致轮廓如下，在搜索区内任选一点孟，孟，计算该点的函数值。。盖，台、偏导数值以及梯度矢的模〔〕么，告〕，如果该点不满足条外，那么沿着梯度矢的反方向前进扩李硬

一个步距入， Sum(X ,Y) grad(Sum(X,Y:)) (7) 因而到达了新的一点Q(X:,Y),重新计算上述各值。如此循环地选代下去直至满足条件(6) 为止。按照这样的方法搜索匹配点，其优点是很明显的，因为入。具有明显的几何意义，见图 3。当Sum值较大时，搜索是以大的步距向Sum数减小的方向前进，当Sum函数值变化剧烈的情况下步距变小，使搜索变得精密、仔细。但是，由于这种搜索方法是一个循环迭代的过程，所以有两个问题是必须解决的。第一个问题是这个迭代过程是否收歙：第二个题是这个过程是否会在非匹配点处形成”死循环”。对于第一个问题的答案，取决于 XY,) Sum(Xo,Y)函数在点(X,Y)处是否存在一个邻域，在此邻域内函数是处处连续可微的。如果“是”，那么图3 过程一定是收歙的；否则，答案就不一定。很明显，在向匹配点(X,Y)搜索接近时，条件(6)式使得()式右端的分母趋向于零，假如S“m函数在匹配点处沿梯度矢量的方向，是一个间断点，那么(7)式左端的入。就要趋于无穷大、过程是发散的。这一个反例的存在，就说明(7)式在应用时要谨慎，若过程发散则需要修改如下，入。= Sum(X,Y) grad (Sum(X,Y3)]x K(grad) K(grad)是一个收歙系数，它根据梯度而确定。当搜索点趋向于匹配点时，grad趋向于零，为保证收歙，则不仅要求K趋向零，而且要求K是比grad高一阶的无穷小。满足这一要求的函数K是很多的。譬如， K=1-EXP (8) a是一个供选择的常数，标志着只有grad的值小于a的情况下，K才起到改进收歙的作用。m 是大于零的整常数，它决定了做为一个无穷小量的K的阶。若选m=2,参照(7)式的右端来考查下述极限值，并注意到分子、分母都是无穷小量： Lim (X8,Y) grad (Xo,YB) -+(X,Y) +(X,Y) 由于 Lim (grad)=0 (XY:) →(X,Y) 所以 58

一个步距大。，入。孟，孟〔孟，孟〕因而到达了新的一点，幻，重新计算上述各值 · 如此循环地迭代下去直至满足条件为止。按照这样的方法搜索匹配点，其优点是很明显的，因为入。具有明显的几何意义，见图。当值较大时，搜索是以大的步距向数减小的方向前进，当函数值变化剧烈的情况下步距变小，使搜索变得情密、仔细。但是，由于这种搜索方法是一个循环迭代的过程，所以有两个问题是必须解决的。第一个问题是这个迭代过程是否收欲，第二个题是这个过程是否会在非匹配点处形成 ” 死循坏 ” 。对于第一个问题的答案，取决于。。，。函数在点言，言处是否存在一个邻域，在此邻域内函数是处处连续可微的。如果 “ 是” ，那么过程一定是收款的，否则，答案就不图一定。很明显，在向匹配点言，朴搜索接近时，条件式使得式右端的分母趋向于零，假如函数在匹配点处沿梯度矢盆的方向，是一个间断点，那么式左端的入。就要趋于无穷大、过程是发散的。这一个反例的存在，就说明式在应用时要谨做，若过程发散则需要修改如下，入孟，言谊乳忿万一是一个收欲系数，它根据梯度而确定。当搜索点趋向于匹配点时，趋向于零，为保证收救，则不仅要求趋向零，而且要求是比高一阶的无穷小。满足这一要求的函数是很多的。铃如，， ‘ 一一〔一 ‘ 飞口、少是一个供选择的常数，标志着只有的值小于的情况下，才起到改进收欲的作用。是大于零的整常数，它决定了做为一个无穷小量的的阶。若选二，参照式的右端来考查下述极限值，并注意到分子、分母都是无穷小量，自宝，， · 〔一咔 “ ，言卫丝一 ’ 盆，，所由以“于

Lim K(grad) (Xa,8) grsd=0 +X,Y) 因而，如果Sum函数在匹配点处是有限值型的间断点，则按(8)式令m=2来选择收歙系数 K,就可以保证收歙。因为这样的K可以使入。趋近于零。如果S“函数在匹配点处是无穷大型间断点，则在公式(8)中应令m>2来选取K系数。对于第二个问题的答案是：迭代过程陷入“死循环”是可能的。例如图(3)中，自P点开始向匹配点搜索，第一步经A到达P:点，第二步经B到达P,点，第三步又经A到达P:点。如此循环下去使搜索无法前进。不仅在P,P,两点之间可形成死循环，只要新的搜索点和以 :前的诸搜索点的任何一个重合，就必然形成死循环。此外，使搜索无法进行下去还有以下三 ·种情况：按步距入。确定的新搜索点处于搜索范围之外，搜索点处于极小值不为琴的极小点处，或者梯度值（模）为零的点因而使(6)式无意义。凡是出现以上四种情况，必须重新选用新的起始点Q,从而使搜索进行下去。这些起始点是选自在搜索区内均匀分布的伪随机序列。根据在本节开始时提出的基本思想，进一步廓清了这一算法的轮廓，然后在这一框架内对于几个重要的细节问题进行了讨论，并给出了解答。那么，讨论到目前为止，已经完全有条件把这一算法具体地制定出来了。它被称之为“子图配准的随机搜索算法”，它是由以下四个部分所组成。第一部分是产生在搜索区内的随机起始点(X。,Y,),其相应的离散坐标点为(I。,J)。它是先用乘同除法产生一个(0,1)区间内的伪随机实数R(N),它是由下式产生 IXw=C·IXN-I mod(M) R(N)=IXN/M N=1,2, 对于字长为32的计算机，应选M=231-1,C=48828125,IX为正整数。其初始值IX。应选 21-1以下的任何正的整奇数。这样R(N)的重覆周期约为22°。由R(N)通过区间的比例放大、取整、平移等運算就可获得满足条件 1≤I,≤NXK 1≤J,≤NYL 的随机点(I。,J。)。上式中NXK,NYL分别为搜索区沿X方向和Y方向的边界值。I。、J。分别为正整数。第二部分是对1。、J,进行鉴别。无论是从第一部分或者是从下面的第四部分所计算得到的I。、J,做为一个新的搜索点，都必须进行鉴别。凡是出现前述四种有害的情况，都应使程序的执行返回到第一部分，重选起始点。只有通过鉴别的(I。,J。)才可以执行下一部分。第三部分是对(I。,J,)点计算窗口内的各项参量，这些参量是函数值SuM,偏导数 P:x,P,yo,和梯度Gao NK NL Sum=∑ =1L=1 6K+1-,L+1-》-TK, NK NL P,x=∑∑2G(K+1-1,L +J-)-T(K,)]PaK,) K=1L=1 Px(K,L)=(G(K+1,L+J。-1)-G(K+1。-2,L+J。-1)/2 59

声、，忿，盆，，二因而，如果函数在匹配点处是有限值型的间断点，则按式令来选择收教系数，就可以保证收款。因为这样的可以使久。趋近于零。如果函数在匹配点处是无穷大型间断点，则在公式中应令来选取系数。对于第二个问题的答案是迭代过程陷入 “ 死循环” 是可能的。例如图中，自点开始向匹配点搜索，第一步经到达点，第二步经到达点，第三步又经到达，点。如此循环下去使搜索无法前进。不仅在两点之间可形成死循环，只要新的搜索点和以前的诸搜索点的任何一个重合，就必然形成死循环。此外，使搜索无法进行下去还有以下三种情况按步距入。确定的新搜索点处于搜索范围之外，搜索点处于极小值不为零的极小点处，或者梯度值模为零的点因而使式无意义。凡是出现以上四种情况，必须重新选用新的起始点，从而使搜索进行下去。这些起始点是选自在搜索区内均匀分布的伪随机序列。根据在本节开始时提出的基本思想，进一步廓清了这一算法的轮廓，然后在这一框架内对于几个重要的细节问题进行了讨论，并给出了解答。那么，讨论到目前为止，巳经完全有条件把这一算法具体地制定出来了。它被称之为 “ 子图配准的随机搜索算法” ，它是由以下四个部分所组成。第一部分是产生在搜索区内的随机起始点。，。，其相应的离散坐标点为。，。。它是先用乘同除法产生一个，区间内的伪随机实数，它是由下式产生一一二，， · ” ” ‘ 对于字长为的计算机，应选。 ‘ 一，，为正整数。其初始值。应选 ’ 一以下的任何正的整奇数。这样的重覆周期约为 “ “ 。由通过区间的比例放大、取整、平移等逮算就可获得满足条件《。《《。《的随机点。，。。上式中，分别为搜索区沿方向和方向的边界值。。、。分别为正整数。第二部分是对。、。进行鉴别。无论是从第一部分或者是从下面的第四部分所计算得到的。、。，做为一个新的搜索点，都必须进行鉴别。凡是出现前述四种有害的情况，都应使程序的执行返回到第一部分，重选起始点。只有通过鉴别的。，。才可以执行下一部分。第三部分是对。，。点计算窗口内的各项参里，这些参盆是函数值。。，偏导数，，。， ‘﹃，卜和梯度。。 “ 。艺厂， ‘ ‘ 。一 ‘ ， ‘ 。一 ‘ ’ 一 ‘ ，，」一艺艺 · 【 · ，一， · ，。一 ‘ 一，，」 · 。。，，。，〔。，。一一。一，。一

NK NL Psxo=2.(G(K+1.-1,L+J.-1)-T(K,L))-Payo(K,L) K=1L=1 Pv(K,L)=[G(K+I。-1,L+J,)-G(K+1。-1,L+J-2)]/2 G4s0=√(P,x0)2+(P,)z 上式中NK,NL是窗口的宽度，T(K,L)是模板，PGx,PGY分别是窗口内图象函数的差分，它是取一点处之相邻两点函数差的平均值做为该点的差分的。所有上述各量是由一个专门的子程序产生的。第四部分是检查匹配条件。若不满足，则进而确定步距计算下一个搜索点。应按式(6) 检查匹配条件。若满足，则(I。,J)即是所求的匹配点。若不满足，则检查GDSO,若 G4s。=0,则返回第一部分重新开始另一搜索。若G4s。中0，则 1。sSum。 Gd3 Dx0=入。X Ps￥0 Gdso Px Dy。=入。×Ga0 I。n+1=Ig-IDxe J。n+1=Jg-IDy0 式中IDx。是Dx的整数部分。新的搜索点(I+,J8*)是由上一个搜索点(I:,J:)沿梯度矢量的反方向前进一步入，而得到的。它应返回程序的第二部分接受鉴别。这就是子图配准的随机搜素算法的全部内容。附录是用FORTRTRANN写出的这一算法的主程序。图4显示出搜索过程，表示了这一算法的结果。三、结论本算法是借助于随机技巧来建立一种改进搜素方式的算法。对于任何的、从一个二维数组中搜索一个紧密的子数组这一类问题，本算 2n77777n7nW NR=1 法都是适用的。如果要从本算法收到节省计算工作量的效益，如前所述，应该是在<0.5 NR 的情况下。本文建议，以0.05≤≤0.2做为使用本算法的有利范围。曾在灰度级为32的、纹理结构复杂、谱带很 NR-3 宽的图片上试用了本算法，结果是成功的。图片搜索区尺寸为NXNY=64×64,子图的尺寸为NK· NL=10×14,搜索范围为NXK·NYL=55 4- ×51这样E=0.21。按照传统算法约应计算 Tithiitatitttthtls 匹配点 1400点而使用本算法，仅计算了97个点，占用。一随机起始点计算机的CPU时间仅19秒钟。多次试算的结 △一中间搜紫点果都证明了这一算法的效果。图4 步距入。的选择，并不一定要拘泥于(7)式(7)式。为了改普收歙的速度，入。可以按一定 60

· 乏艺 · 〔，。一，。一，，一，〕 · 。，。，，二，。，二。侧一，。。一，。一，。一」上式中，是窗口的宽度，，是模板，。。，。，。分别是窗口内图象函数的差分，它是取一点处之相邻两点函数差的平均值做为该点的差分的。所有上述各量是由一个专门的子程序产生的。第四部分是检查匹配条件。若不满足，则进而确定步距计算下一个搜索点。应按式检查匹配条件。若满足，则。，。即是所求的匹配点。若不满足，则检查，若。。，则返回第一部分重新开始另一搜索。若。笋，则入。二。。。入。。。一，飞赞，舀。 ” ‘ ’ 卜。。 “ “ 尝一，。式中。是。的整数部分。新的搜索点十 ‘ ，忿 ’ 是由一个搜索点言，沿梯度矢最的反方向前进一步入。，而得到的。它应返回程序的第二部分接受鉴别。这就是子图配准的随机搜索算法的全部内容。附录是用写出的这一算法的主程序。图显示出搜索过程，表示了这一算法的结果。三、结论本算法是借助于随机技巧来建立一种改进搜索方式的算法。对于任何的、从一个二维数组中搜索一个紧密的子数组这一类问题，本算法都是适用的。如果要从本算法收到节省计算工作的效益，如前所述，应该是在乙的情况下。本文建议，以。《七《做为使用本算法的有利范围。曾在灰度级为的、纹理结构复杂、谱带很宽的图片上试用了本算法，结果是成功的。图片尺寸为一，子图的尺寸为，搜索范围为一这样七。。按照传统算法约应计算点而使用本算法，仅计算了个点，占用计算机的时间仅秒钟。多次试算的结果都证明了这一算法的效果。步距入。的选择，并不一定要拘泥于 ’ 式产式。。－随机起始点么一中间搜索点图为了改善收欲的速度，入。可以按一定