基于BBF改进的ICP算法在点云配准中的应用研究.doc

基于 BBF改进的ICP 算法在点云配准中的应用研究孔庆超（东华大学 机械工程学院）摘 要： 在三维激光点云数据配准的过程中 ，利用传统 Iterative Closest Point（ICP）算法搜索对应点 对时速 度慢 ，而 且配准精细化程度低，远达不到三维建模后期处理的要求。很多研究人员使用KDTree对ICP算法进行改进。但KDTree搜索最近点是存在搜索无关的的问题。针对这一问题，提出一种基于BBF算法改进的ICP算法，以实现激光点云数据的快速精细化配准。通过实验验证算法的有效性和合理性，为后期模型重建过程中的三角网格化、曲面化、纹理映射提供强有力的理论和实践基础。关键词：BBF；ICP算法；点云配准；激光点云0 引言在地面三维激光扫描过程中，受物体尺寸、物体间的遮蔽以及扫描仪视场角等因素的影响，每站扫描只能获得本站扫描仪坐标系下的点云数据。对于大型立体模型而言，大多数情况下不太可能只通过一次扫描就获得全部的物体表面坐标及属性数据。因此，为了获得完整的物体表面坐标及属性数据，必须 从不同的视角来扫描场景。在点云数据处理阶段，点云配准是十分关键的问题之一，配准的精细化程度直接影响后续操作。1 扫描设备及作业流程对物体进行点云数据采集时，采用的三维激光扫描仪是 Scan Station C10 全站式三维激光扫描仪。 扫描参数设置情况如下：全 景扫描 ，扫描 视角 为 360270，扫描 速度 为50 000 点/s，扫描距离为 300 m，点位标称精度为 2 mm。设 置 好 参 数 以 后 ， 分 别 在 两 位 置 坐 标 系 下 对 只 有4个 面 的 长 方 体 实 物 进 行 扫 描 采 集 。 然 后 ，依 次 进 行 点 云数 据 的 去 噪 、 稀 疏 采 样 ， 由 此 获 得 能 足 够 表 达 物 体 模 型的 点 云 数 据 。图 1 为 使 用 Scan Station C10 扫 描 仪 的 作 业 流 程 ， 图2 为 经 过 去 噪 采 样 处 理 过 的 数 据 并 可 视 化 的 结 果 。2 配准定义点 云 配 准 简 单 来 说 就 是 将 从 多 个 站 点 获 得 的 点 云数 据 进 行 拼 接 ， 得 到 一 个 统 一 坐 标 系 下 的 三 维 数 据 点集 。 它 类 似 于 数 学 上 的 映 射 问 题 ，也 就 是 说 要 先 找 到 两个 点 云 数 据 集 间 的 对 应 关 系 ，然 后 将 一 个 坐 标 系 下 的 点云 数 据 转 换 到 另 一 个 坐 标 系 下 。配 准 过 程 主 要 有 以 下 两 个 步 骤 ：（1）寻 找 对 应 关 系 ；（ 2 ） 解 算 变 换 参 数 。 即 首 先 确 定 同 名 点 对 ， 然 后 解 算 旋转 矩 阵 R 和 平 移 矩 阵 T。同 名 点 对 ：同 一 个 点 在 不 同 坐 标 系 下 的 表 达 。图 3 所 示 为 两 站 扫 描 示 意 图 ， 在 A、B 两 处 分 别 安放 扫 描 仪 对 同 一 个 物 体 进 行 扫 描 。 在 A 处 获 得 坐 标 O1-x1y1z1下 的 点 云 数 据 M，在 B 处 获 得 坐 标 系 O2- x1y1z1下 的点 云 数 据 N， 配 准 的 目 的 就 是 将 两 个 坐 标 系 O1- x1y1z1、O2- x1y1z1下 的 点 云 数 据 M 和 N 转 换 到 同 一 个 坐 标 系 下 。对 于 从 两 站 采 集 到 的 点 云 集 合 M 和 N，Mi（ X ， Y ，Z ） ， Ni（ x ， ， z ） ， 且 Mi、 Ni为 在 不 同 坐 标 系 下 的 同 一 点 ，严 格 来 说 ，点 云 配 准 就 是 将 全 部 来 自 两 个 不 同 坐 标 系 下的 同 名 点 对 （Mi， Ni） 满 足 刚 体 变 换 （ R ， T ） ， 即 ：，其 中 ，R 为 旋 转 矩 阵 ，T 为 平 移 矩 阵。式 （1） 称 作 空 间 相 似 变 换 公 式 ， 它 是 点 云 配 准 的 基本 公 式 。 由 式 （1） 可 解 出 同 名 点 转 换 参 数 ， 而 后 进 行 点云 数 据 配 准。3 点云配准算法目 前 ，点 云 配 准 算 法 依 据 其 采 用 的 配 准 基 元 可 将 其分 为 无 特 征 的 配 准 和 基 于 特 征 的 配 准1两 大 类 。基 于 特 征 的 配 准 是 指 利 用 角 点 、 边 缘 、 面 等 几 何特征2来 解 算 变 化 参 数 。 这 类 算 法 主 要 有 以 下 几 种 ： 基 于控 制 点 的 配 准 算 法 3、 基 于 线 特 征 的 配 准 算 法 4 以 及 基于 曲 率5的 点 云 配 准 算 法 。无 特 征 的 配 准 就 是 直 接 利 用 原 始 数 据 进 行 配 准 。 此类 算 法 中 最 为 著 名 的 是 ICP （ Iterative Closest Point ）算 法 6， 但 该 算 法 只 适 用 于 存 在 明 确 对 应 关 系 的 点 集 ，并 且 计 算 速 度 慢 。 为 此 ， 在 其 他 传 统 ICP 算 法 7的 基 础之 上 ， 提 出 基 于 KDTree 8 的 改 进算法BBF改进 ICP 算 法 ， 包 括 基 于BBF搜 索 对 应 点 对 和 矩 阵 变 换 参 数 的 计 算 两 方 面 的内 容 。3 . 1 传 统 ICP 配 准 算 法基 本 思 路 ： 在 对 应 点 云 中 搜 寻 最 邻 近 点 对 ， 利 用 此最 邻 近 点 对 求 解 刚 体 变 换 参 数 R、T，在 这 个 过 程 中 点 对的 搜 寻 和 变 换 参 数 的 求 解 都 是 迭 代 计 算 的 。算 法 步 骤 如 下 ：（ 1 ） 令 为 点 云 M 和 N 的 重 叠 域 ， 设 在 然 数 集 N及 其 扩 展 情 况 ， 如 正 整 数 集 Z+、n 维 实 坐 标 中 的 任 一 点对 应 在 M 和 N 上 的 位 置 分 别 是 Mi、 Ni， 初 始 迭 代 时 两 个点 集 的 初 始 变 换 参 数 是 R0，T0。（ 2 ） 点 集 M 中 的 每 个 点 Mi， 由 初 始 变 换 参 数 最 小 为标 准 ，求 出 新 的 变 换 参 数 R、T。（ 3 ） 根 据 找 到 的 全 部 最 近 点 对 （ mi， ni） ， 求 出 两 个 点集 的 变 换 参 数 R、T，并 且 以 全 部 点 对 距 离 的 平 方 和 最 小为 标 准 ，求 出 新 的 变 换 参 数 R、T。（ 4 ） 在 相 邻 两 次 计 算 所 得 的 距 离 平 方 和 的 差 值 小 于给 定 的 阈 值 时 结 束 迭 代 ， 否 则 重 复 步 骤 （2） 和 （3） 直 至小 于 给 定 的 阈 值 。（ 5 ） 根 据 最 终 得 到 的 R 、 T 将 点 云 M 映 射 变 换 到 点云 N 的 坐 标 系 下 ，完 成 配 准 。3 . 2 改 进 的 基 于 BBF 的 ICP 算 法3 . 2 . 1 算 法 准 备 工 作由 BBF的 算 法 原 理 可 知 ， 当 邻 域 点 集 中 点 数 k为 1 时 ， 搜 寻 点 与 邻 域 点 间 建 立 一 一 映 射 关 系 。 此时 ， 搜 索 到 的 邻 域 点 是 搜 寻 点 与 邻 域 点 集 中 距 离 最小 的 点 。该 算 法 中 要 用 到 的 变 换 矩 阵 利 用 四 元 素 法 9求 解 ，过 程 如 下 ：（ 1 ） 求 解 点 集 M 、 N 的 重 心 坐 标 O1、 O2。（2）点集M、N的重心化：， （ 3 ） 构 建 矩 阵 Q（ 4 ） 求 解 Q 的 最 大 特 征 值 以 及 最 大 特 征 值 对 应 的 特征 向 量（ 5 ） 构 造 旋 转 矩 阵（ 6 ） 解 算 平 移 向 量3 . 2 . 2 算 法 实 现 步 骤（ 1 ） 设 点 集 M 、 N 的 部 分 区 域 分 别 为 目 标 点 集 M 和参 考 点 集 N。（ 2 ） 令 k = 1 ， 在 N 中 通 过 BBF加 速 搜 索 为 M 中的 任 意 点 搜 索 最 近 邻 域 点 ， 由 此 找 出 M中 任 意 一 点 的映 射 点 ， 也 就 是 找 出 M中 点 集 合 Mm=M1m， M2m， ， Mnm在 N上 的 映 射 点 集 Nm=N1m， N2m， ， Nnm ， m 代 表 迭 代 次数 ，n 代 表 点 个 数 。（ 3 ） 利 用 设 置 好 的 最 小 阈 值 距 离 Di ， 删 除 Mm、 Nm 中错 误 的 点 对 ，并 完 成 Mm、Nm 的 更 新 。（ 4 ） 利 用 四 元 素 法 计 算 Mm 、 Nm 的 变 换 矩 阵 R 和 平移 量 T。（ 5 ） 由 得 到 的 R 、 T 变 换 Mm， 得 到 最 新 的 Mm。（ 6 ） 重 复 步 骤 （ 2 ） （ 5 ） ， 求 出 Mm 中 每 一 点 到 Nm 中的 映 射 点 对 ，以 及 相 应 的 R、T。（ 7 ） 当 最 后 的 R 、 T 满 足 配 准 后 ， 对 应 点 对 坐 标 间 差值 的 阈 值收 敛 条 件|xm- xn| or | ym- yn| or | zm- zn| 时 ， 结 束 循环 ， 匹 配 成 功 ； 如 果 不 满 足 收 敛 条 件 ， 进 行 第 m+1 次 迭代 计 算 。算 法 设 计 流 程 如 图 4 所 示。图4 基于BBF改进的ICP算法实现4 实验结果与结论根 据 以 上 提 出 的 算 法 ，利 用 斯 坦 福 大 学 实 验 室 在 不同 坐 标 系 下 获 得 的 兔 子 点 云 数 据 和 实 测 的 只 有 4 个 面数 据 的 长 方 体 的 点 云 数 据 进 行