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