子图配准的随机搜索算法

,.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

但是，决定整个算法的计算工作量大小的，，还有另外一个因素，那就是(1)式右端的因 子(L~M)所标志的部分。即在搜索区内搜索匹配点所需要的搜索次数。当窗口尺度M较 小时（ 则按照以上的方式继续搜素 前进。当无法到达目标点时 (b) (其原因后面再讨论)，则 图2 重新在一个新的随机点上起 步，仍按照上述方式搜索前进。这些随机选取的、互相不重覆的起点是在搜索区内按等概率 均匀分布的伪随机序列，它是由一个专门的程序产生的。 下面来具体地讨论这一算法。 首先碰到的问题是如何描述平移窗口内的图象，为此需要定义一个二元函数2(x,y)如 下 a a X- 2 2 (X,y)=1 y- 2 2 x-2 2 (X,y)=0 b y- 72 ◆ 称之为“透明窗口”，其定义域的域界是a、b,如图2a所示。如果令a+o,b→o,那么2 (x,y)就成为一个二维的单位阶跃函数，这正和一元函数中的有因函数1(t)是类似的。引进 56

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

(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

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

规律放大或缩小。譬如可以选用它的平方根来缩小步距，以求搜索得细密。步距的放大或缩 小，都是属于使用本算法的技巧问题。并不影啊算法的实质。重要的实质问题是搜索的方向 不变，依然是梯度矢量的反方向。 如果说，均匀分布的随机起点保证了以最大的概率把搜索过程建立在收歙区域内，那 么，沿梯度矢量的反方向搜索则是保证了以最短的路径向匹配，点收歙。这两点是本算法所以 能成功的最本质的概括。 本文曾承孙一康先生审阅，笔者又做了修改。特此志谢。 参考文献 (1)IEEE,TRANS ON COMPUTER VOL C-25,1976 PP 1336-40 〔2)航空学报1980年第一期，P、68 (3]K.S,Fu,DigitaL Pattetn Recognition,Chap.5 (4)A.Ralston,H.S.wiLf:Mathematical Methods for Digital Comgnter,Chap.6.§12 (5)R.O.Duda,P.E.Hart:Pattern CLassification and Scenes AnaLysis Chapt.7 附录 用FORTRANN写出的随机搜索算法的主程序（四部分） SOURCE STAEMNTS C MAIN PROGRAM RANDOMLy SEARCHING ALGORITHM C FOR SUBPICTURE REGIRATION C DIMENSION COOP(64,64),DIGPC(64,64),PRQPC(64,64), ADIGPC(64,64),AT(10,14),IDX(64,64),MI(900),MJ(900),R(2) COMMON /P/COOPC,DIGPC /Q/PPOPC/R/ADIGPC,AT READ(5,100)NX,NY,NK,NL READ(5,101)((CODPC(I,J),J=1,NY),I=1,NX) C C CHANGING CODED IMAGE INTO DIGITAL IMAGE CALL CITODI(NX,NY) C C FORMING TEMPLATE, DO 01 K=1,NK D001L=1,NL 01 AT(K,L)=DIGPC(K+51,L+36) D002I=1,NX 61

规律 放大或缩小 。 譬如可 以选 用 它 的平方根来缩小步距 ， 以求搜索得细密 。 步距 的放大或缩 小 ， 都是 属于 使用 木算法 的 技 巧 问题 。 并不 影 响算法的 实质 。 重要 的实质 问题是 搜索的方向 不 变 ， 依 然是梯度矢量 的反 方 向 。 如 果 说 ， 均匀分布的 随机 起点保证 了以 最大的概率把搜索过程建 立 在收欲 区域 内 ， 那 么 ， 沿梯度矢量 的反方 向搜索则是 保 证 了以最 短 的路径 向匹配点 收欲 。 这 两点是本算法所以 能成功的最本质 的概 括 。 本文 曾承孙一康先生审阅 ， 笔者又做 了修 改 。 特此志谢 。 参考文献 〔 〕 ， 一 ， 一 〕 航空学报 年第一 期 ， 、 〔 〕 、 、 ， ， 〔 ， ， 夸 〕 ， 附录 用 写出的随机搜索算法的主程 序 四 部分 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ，

D002J=1,NY IDX(I,J)=0 PROPC(I,J)=32.0 02 ADIGPC(I,J)=DIGPC(I,J) NXK=NX-NK+1 NYL=NY-NL+1 N=0 C C CHOOSEING RADOMLY STARTING POINTS NR=0 IX=584287 05D008KK=1,2 IX=IX#48828125 IX=MOD(IX,2147483647) IF(IX)06,07,07 06IX=(IX+2147483647)+1 07R(KK)=FL0AT(IX)#0.4656613E-9 08 CONTINUE 10=1+IFIX(R(1)*(NXK-1)) j0=1+IFIX(R(2)*(NYL-1)) NR=NR+1 WRITE(6,150)NR,R(1),R(2) IF(NO)20,20,10 C C IDENIFYING I0,Jo 10D015KK=1,N0 IF(MI(KK).EQ.I0.AND.MJ(KK).EQ.Jo)GO TO 05 15 CONTINUE IF(I0,GT.NXK.OR.Jo.GT,NYL)GO TO 05 IF(10.LT,1.OR.Jo.LT.1)GO TO 05 C C CALCUATEING PARAMETERS SUMO,PSXO,PSYO,GDSO OF THE WINDOW AT I0,Jo C AND CHECKING THE MATCHING WITH TEMPLATE 20 CALL SPGO(NO,10,Jo,NK,NL,SUM,PSXO,PSYO,GDSO, SITAO,IDXO) NO=NO+1 MI(NO)=10 MJ(NO)=Jo WRITE(6,130)NR,I0,Jo,SUMO,PSYO,GDSO,SITAO,IDXO, ?

， ， ， 二 ， ， 一 一 二 ， 势 ， ， ， 份 一 价 一 一 一 二 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 母

◆NO I=10 J=Jo IDX(I,J)=IDXo EPS=1E-8 IF(SUMO.LT.EPS)GO TO 25 C ONE STEP FORW ARO IF(SUMO.NE.0.0.AND.GDS0.EQ.0.0)GO TO 05 RAMDA=SUMO/GOSO RAMDA=SQRT(RAMDA) RAMDA=RAMDA/GDSO DXO=RAMDA*PSXO DYo=RAMDA*PSYO IF (DX0.GE.0.0)IDX0=IFIX(DX0+0.5) IF (DXO.LT.0.0)IDXO=IFIX(DX0-0.5) IF (DY0.GE.0.0)IDYO=IFIX(DY0+0.5) IF (DYO.LT.0.0)IDYO=IFIX(DYO-0.5) 10=I0-IDX0 JO=Jo-IDX0 G0T010 C OUT-PUT AND DISLAY 28 WRITE(6,158)I0,J0 25 WRITE(6,140) 24 WRITE(6,120)((IDX(I,J),J=1,NY),I=1,NX) PROPC(1,1)=1,0 DO 30 K=1,NK DO 30 L=1,NL I=K+I0-1 J=L+J0-1 30 PROPC(I,J)=DIGPC(I,J)DIGPC(I,J) CALL PICDSP(NX,NY,0) D040I=1,NX D040J=1,NY 40 PROPC(I,J)=DIGPC(I,J) CALL PICDSP(NX,NY,0) STOP 100 FORMAT(414) 101 FORMAT(64A1) 120 FORMAT(1H ,2X,6412) 130 FORMAT(1H,2X,2X,4H NR4HIO,,4H Jo,,6H SUMO,,6H 63

， 一 朴 赞 一 一 一 一 一 ， ， ， ， ， ， ， ， ， ， ， ， ， 一 一 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 肠

PSX0,,6H PSY0,, 6H GDS0,,7H SITA0,,5H IDXO,2H=,I3, 2I4,5F8.1,I3J5) 140 FORMAT(1H1) 150 FORMAT(1H0,2X,4HNR,,6HR(1),6HR(2),2H=,I3,2E16, 7)END t 64

， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 二 ， ， ，