毕业论文计算机图形识别与编辑

哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 1 -内 容 摘 要本 论 文 主 要 讲 述 了 图 像 文 件 （ bmp） 文 件 格 式 下 中 简 单 图 形 的 识别 ， 主 要 是 直 线 和 圆 的 识 别 ， 这 在 工 程 图 的 识 别 和 其 他 领 域 中 都 有很 多 的 应 用 。第 一 章 到 第 三 章 主 要 介 绍 了 在 本 论 文 中 涉 及 到 的 知 识 及 算 法 。第 四 章 是 程 序 的 实 现 方 法 和 过 程 及 结 果 等 。第 五 章 是 结 束 语关 键 词 ：图 形 识 别 、 图 像 处 理 、 霍 夫 变 换 、 单 义 域 、 多 义 域 、 delphi 哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 2 -Content AbstractThis thesis is mainly focused on the Simple Graph Recognition in Image of .bmp. The Line Recognition and the Circle Recognition, these is good use of on Engineering Graphicis.The first part to the third part is mainly focused on some points and algorithms for my thesis.The fourth part is about the methodologys 、 courses and outcome of the program.The last part is the end-words.哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 3 -Key Words图 形 识 别 (Graph Recognition)图 像 处 理 (Image Processing)霍 夫 变 换 (Hough Transform)单 义 域 (Unity Region)多 义 域 (Multi-Region)哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 4 -目 录第 二 章 概 述 .6第 一 节 引 言 .6第 二 节 在 工 程 图 的 识 别 中 常 用 的 方 法 .6第 三 章 论 文 的 工 作 基 础 和 工 作 环 境 .8第 一 节 数 字 图 像 处 理 技 术 .81. 图 像 处 理 的 基 本 内 容 .82. 主 要 的 图 像 处 理 技 术 .8第 二 节 图 像 格 式 BMP 格 式 .9第 三 节 算 法 及 数 学 基 础 .101. 霍 夫 变 换 （ Hough Transform） .102. 基 于 单 义 域 的 直 线 及 圆 识 别 算 法 .133. 主 要 技 术 .16第 四 章 直 线 和 圆 的 识 别 和 编 辑 的 实 现 .17第 一 节 系 统 的 层 次 结 构 的 图 示 .17第 二 节 系 统 数 据 结 构 及 类 的 设 计 .181. 主 要 类 的 层 次 结 构 .182. 图 形 基 类 （ CShape） .193. 图 形 类 （ CLine、 CCircle） .204. 图 形 容 器 类 （ CShapes） .225. 点 类 （ CPoint） .236. 单 义 域 类 （ CSegment） .237. 基 于 单 义 域 识 别 类 （ CSegments） .248. 霍 夫 变 换 识 别 直 线 类 （ CHTLine） .259. 霍 夫 变 换 识 别 圆 类 （ CHTCircle） .25哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 5 -第 三 节 主 程 序 实 现 .26第 四 节 系 统 功 能 介 绍 .26第 五 节 总 结 及 展 望 .31第 五 章 结 束 语 .32参 考 文 献 .34哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 6 -第 一 章 概 述第 一 节 引 言计 算 机 技 术 的 发 展 ， 使 人 类 社 会 进 入 了 信 息 化 和 自 动 化 ， 计 算 机 智 能 识 别也 随 着 计 算 机 的 发 展 得 到 了 迅 速 的 发 展 。 特 别 是 图 形 图 像 的 计 算 机 处 理 技 术 更是 有 了 前 所 未 有 的 进 步 和 应 用 。 计 算 机 识 别 也 逐 渐 的 从 图 形 图 像 处 理 的 大 环 境下 分 离 出 来 作 为 一 门 新 的 高 科 技 研 究 领 域 出 现 。 图 形 图 像 的 识 别 涉 及 到 的 学 科很 多 ， 包 括 数 字 信 号 处 理 、 工 程 数 学 、 信 息 论 、 运 筹 学 、 等 ， 它 与 计 算 机 、 自动 化 、 生 物 学 、 关 学 、 视 觉 心 里 和 生 理 学 、 人 工 智 能 、 智 能 信 息 处 理 等 众 多 领域 交 叉 、 综 合 集 成 ， 有 广 泛 的 应 用 。本 论 文 实 现 的 是 基 础 的 图 形 识 别 ， bmp 图 像 文 件 格 式 中 对 图 形 的 矢 量 化 。识 别 基 本 的 图 元 直 线 和 圆 。 直 线 和 圆 是 二 值 图 像 中 最 基 本 的 组 成 元 素 ， 也 是 最常 见 的 图 形 元 素 。 在 工 程 图 的 数 字 化 识 别 中 有 很 大 的 应 用 。关 于 理 想 情 况 的 几 点 说 明 ：1. 所 识 别 的 bmp 图 像 文 件 是 经 过 处 理 的 ， 没 有 “噪 音 ”等 ， 在 本 论 文中 直 接 采 用 的 是 用 Windows 中 的 画 图 软 件 画 出 的 图 像 。2. 本 论 文 中 图 像 中 的 图 元 都 是 单 一 的 线 性 ， 即 线 宽 是 一 个 象 素 的 情 况 。第 二 节 在 工 程 图 的 识 别 中 常 用 的 方 法图 形 的 识 别 最 主 要 的 是 图 形 特 征 的 提 取 ， 在 这 个 阶 段 ， 常 用 的 方 法 是 全 局特 征 方 法 （ 包 括 ： 不 变 距 ， 自 回 归 模 型 、 傅 立 叶 描 述 符 、 霍 夫 变 换 等 ） ， 全 局特 征 的 特 征 提 取 方 法 是 理 论 比 较 完 善 的 ， 计 算 过 程 比 较 清 楚 。 针 对 不 同 的 特 征提 取 处 理 ， 采 用 相 对 应 的 模 式 匹 配 方 法 来 将 图 形 分 类 ， 模 式 识 别 迄 今 已 有 很 多方 法 ， 有 模 板 匹 配 、 统 计 模 式 识 别 、 句 法 模 式 识 别 、 模 糊 识 别 和 神 经 网 络 识 别等 。在 二 值 图 像 的 处 理 中 ， 人 们 常 用 的 数 据 结 果 有 游 程 编 码 考 虑 了 扫 描 行 上相 邻 象 素 间 的 相 关 性 ； 行 相 邻 图 法 （ Line Adjeceney Gragh） ， 是 由 Pavlidis 提哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 7 -出 的 一 种 二 值 图 的 数 据 结 构 ， LAG 还 考 虑 了 相 邻 行 黑 游 程 之 间 的 相 邻 关 系 ，遍 历 时 很 方 便 ； BAG（ Bloek Adjeceney Gragh） 是 由 余 斌 提 出 的 ， 它 是 相 邻 图LAG 在 两 个 方 向 上 的 推 广 。 在 本 论 文 中 就 是 利 用 了 LAG 的 数 据 结 构 思 想 与c+ builder 的 数 据 结 构 相 结 合 的 方 法 即 ： 用 下 一 个 象 素 点 是 与 链 表 头 相 邻 还 是和 尾 相 邻 来 描 述 其 相 邻 的 关 系 。本 论 文 中 对 交 点 的 处 理 。 目 前 对 交 点 的 处 理 有 下 面 几 类 算 法 ：1. 基 于 网 格 算 法 ， 该 算 法 是 通 过 网 格 加 大 搜 索 步 长 来 跳 过 交 点 。2. 基 于 图 段 合 并 的 算 法 ， 是 根 据 交 点 处 行 程 段 的 连 通 性 ， 以 交 点 为 界 将图 线 分 割 成 图 段 ， 记 录 各 段 之 间 的 连 接 及 从 属 关 系 ， 然 后 连 接 或 延 长各 分 支 图 段 ， 然 后 得 到 整 条 图 线 。在 本 论 文 中 采 用 了 第 二 种 方 法 ， 基 于 图 段 合 并 的 算 法 。当 然 现 下 有 很 多 更 好 的 算 法 和 数 据 结 构 ， 但 是 大 部 分 是 针 对 具 体 的 结 构 或者 研 究 方 向 不 具 有 一 般 性 ， 所 以 本 论 文 的 实 现 用 了 上 述 的 数 据 结 构 和 方 法 。哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 8 -第 二 章 论 文 的 工 作 基 础 和 工 作 环 境第 一 节 数 字 图 像 处 理 技 术将 客 观 世 界 实 体 或 图 片 等 通 过 不 同 的 量 化 (数 字 化 )手 段 送 入 计 算 机 ， 由 计算 机 按 使 用 要 求 进 行 图 像 的 平 滑 、 增 强 、 复 原 、 分 割 、 重 建 、 编 码 、 存 储 、 传输 等 种 种 不 同 的 处 理 ， 需 要 时 把 加 工 处 理 后 的 图 像 重 新 输 出 ， 这 个 过 程 称 为 图像 处 理 。 因 此 ， 图 像 处 理 的 含 义 是 用 计 算 机 对 图 像 进 行 加 工 处 理 以 得 到 某 种 预期 的 效 果 ， 它 本 质 上 是 一 种 二 维 数 字 信 号 处 理 技 术 。1. 图 像 处 理 的 基 本 内 容图 像 处 理 的 基 本 内 容 可 以 归 结 为 ：1. 对 图 像 进 行 增 强 或 修 改 。以 改 变 或 强 调 图 像 信 息 的 某 些 特 点 (增 强 有 用 信 息 ， 无 用 信 息 )， 改 善 图像 的 视 觉 质 量 ；2. 描 述 图 像 的 特 征 并 进 行 特 征 抽 取 和 分 析 。例 如 提 取 图 像 的 纹 理 特 征 、 频 谱 特 征 、 边 界 特 征 和 颜 色 特 征 等 ； 对 像 素用 某 个 标 准 衡 量 并 进 行 分 类 比 较 ， 将 抽 取 的 特 征 归 结 为 一 定 的 模 式 ， 这 属于 模 式 识 别 的 范 围 ；3. 图 像 的 重 建 (Reconstruction)。对 图 像 的 某 些 部 分 合 并 或 进 行 重 新 组 织 ， 这 种 技 术 是 从 N1 维 的 信 息用 某 种 算 法 得 到 N 维 的 图 像 ， 例 如 计 算 机 视 觉 就 是 这 样 的 一 种 技 术 。2. 主 要 的 图 像 处 理 技 术2.1 图 像 的 增 强 和 恢 复图 像 增 强 所 追 求 的 目 标 是 改 善 图 像 的 视 觉 质 量 ， 符 合 人 们 的 主 观 要 求 ，它 不 追 究 图 像 客 观 质 量 的 降 低 原 因 。 图 像 的 视 觉 质 量 是 因 人 而 异 的 ， 其 质 量哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 9 -的 高 低 和 好 坏 受 观 看 者 的 心 理 、 爱 好 和 文 化 素 质 等 因 素 的 影 响 。 图 像 的 恢 复则 致 力 于 探 索 图 像 质 量 降 低 的 原 因 ， 并 尽 可 能 消 除 图 像 质 量 的 降 低 ， 恢 复 图像 的 本 来 面 目 。2.2 图 像 的 压 缩 编 码彩 色 数 字 图 像 通 常 是 由 三 个 二 维 数 组 组 成 的 ， 其 信 息 量 相 当 大 ， 这 给 图像 的 传 输 、 处 理 、 存 储 和 显 示 等 带 来 很 大 的 负 担 。 但 问 题 的 另 一 方 面 是 图 像中 又 往 往 存 在 很 多 冗 余 信 息 ， 在 传 输 和 存 储 时 可 以 对 数 字 图 像 进 行 一 定 方 式的 编 码 ， 删 除 图 像 中 的 冗 余 信 息 ， 以 提 高 图 像 传 输 和 存 储 的 效 率 。2.3 图 像 重 建在 医 学 和 工 程 应 用 中 ， 利 用 超 声 波 、 x 射 线 等 技 术 取 得 物 体 的 多 幅 来 自不 同 角 度 的 投 影 图 ， 通 过 计 算 可 得 到 物 钵 内 部 的 图 像 ， 这 种 技 术 称 为 投 影 重建 ， 例 如 CT 就 是 图 像 重 建 的 一 个 应 用 。2.4 图 像 的 分 割 和 描 述计 算 机 按 照 一 定 的 客 观 测 度 (例 如 灰 度 、 颜 色 和 几 何 性 质 等 )将 图 像 中 包含 的 物 体 和 区 域 从 图 像 中 区 分 出 来 ， 称 为 图 像 的 分 割 。 用 适 当 的 数 学 语 言 来表 示 被 分 割 出 来 的 物 体 或 区 域 的 结 构 和 统 计 特 性 ， 或 用 数 学 语 言 表 示 区 域 问的 关 系 ， 称 为 描 述 。 图 像 经 分 别 和 描 述 后 ， 可 较 为 容 易 地 分 类 和 识 别 。第 二 节 图 像 格 式 BMP 格 式BMP(Bitmap-File)图 形 文 件 是 Windows 采 用 的 图 形 文 件 格 式 ， 在 Windows环 境 下 运 行 的 所 有 图 像 处 理 软 件 都 支 持 BMP 图 像 文 件 格 式 。 Windows 系 统 内部 各 图 像 绘 制 操 作 都 是 以 BMP 为 基 础 的 。 Windows 3.0 以 前 的 BMP 图 文 件 格式 与 显 示 设 备 有 关 ， 因 此 把 这 种 BMP 图 像 文 件 格 式 称 为 设 备 相 关 位 图DDB(device-dependent bitmap)文 件 格 式 。 Windows 3.0 以 后 的 BMP 图 像 文 件 与显 示 设 备 无 关 ， 因 此 把 这 种 BMP 图 像 文 件 格 式 称 为 设 备 无 关 位 图 DIB(device-independent bitmap)格 式 ， 目 的 是 为 了 让 Windows 能 够 在 任 何 类 型 的 显 示 设 备上 显 示 所 存 储 的 图 像 。 BMP 位 图 文 件 默 认 的 文 件 扩 展 名 是 BMP 或 者 bmp（ 有时 它 也 会 以 .DIB 或 .RLE 作 扩 展 名 ） 。哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 10 - 文 件 结 构位 图 文 件 可 看 成 由 4 个 部 分 组 成 ： 位 图 文 件 头 (bitmap-file header)、 位 图信 息 头 (bitmap-information header)、 彩 色 表 (color table)和 定 义 位 图 的 字 节 阵 列 ，它 具 有 如 下 所 示 的 形 式 。 位 图 文 件 的 组 成 结 构 名 称 符 号位 图 文 件 头(bitmap-file header)BITMAPFILEHEADER bmfh位 图 信 息 头(bitmap-information header)BITMAPINFOHEADER bmih彩 色 表 (color table) RGBQUAD aColors图 象 数 据 阵 列 字 节 BYTE aBitmapBits第 三 节 算 法 及 数 学 基 础1. 霍 夫 变 换 （ Hough Transform）霍 夫 变 换 是 图 像 处 理 中 从 图 像 中 识 别 几 何 形 状 的 基 本 方 法 之 一 。 其 基 本 思想 就 是 把 图 像 平 面 上 的 点 对 应 到 参 数 平 面 上 的 曲 线 ， 最 后 通 过 统 计 特 性 来 解 决问 题 。 自 1962 年 Hough 公 布 了 该 算 法 以 来 ， 由 于 其 良 好 的 抗 噪 声 性 能 和 对 部分 遮 盖 的 不 敏 感 等 特 性 ， 霍 夫 变 换 在 模 式 识 别 领 域 得 到 广 泛 的 应 用 ， 如 直 线 、圆 、 椭 圆 、 矩 形 等 几 何 图 形 检 测 ， 任 意 形 状 区 域 的 边 界 提 取 ， 二 维 或 三 维 运 动的 参 数 估 计 等 。下 面 就 于 本 论 文 相 关 的 直 线 和 圆 的 识 别 进 行 简 单 的 介 绍 。哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 11 -1.1 霍 夫 变 换 识 别 直 线霍 夫 变 换 识 别 直 线 ， 是 将 图 像 空 间 中 的 一 点 变 换 为 参 数 空 间 中 的 一 条 直 线 。图 像 空 间 中 同 一 直 线 上 的 点 ， 经 霍 夫 变 换 所 形 成 的 直 线 相 交 于 参 数 空 间 中 的 一点 ， 该 点 坐 标 代 表 图 像 空 间 中 直 线 的 斜 率 及 截 距 。 利 用 累 加 数 组 累 计 参 数 空 间中 通 过 该 点 的 直 线 条 数 ， 即 代 表 图 像 空 间 中 直 线 上 的 点 数 。图 2.4.1 霍 夫 变 换 识 别 直 线 （ 1）设 已 知 一 黑 白 图 像 上 画 了 一 条 直 线 ， 要 求 出 这 条 直 线 所 在 的 位 置 。 我 们 知道 ， 直 线 的 方 程 可 以 用 来 表 示 ， 其 中 k 和 b 是 参 数 ， 分 别 是 斜 率ykxb和 截 距 。 过 某 一 点 的 所 有 直 线 的 参 数 都 会 满 足 方 程 。 即0(,)x 00ykxb图 像 空 间 中 的 一 点 确 定 了 参 数 空 间 中 的 一 族 直 线 。 方 程在 参 数 k-b 平 面 上 是 一 条 直 线 。 这 样 ， 图 像 x-y 平 面 上 的 一 个00ykx前 景 像 素 点 就 对 应 到 参 数 平 面 上 的 一 条 直 线 。霍 夫 变 换 识 别 直 线 的 算 法 描 述 如 下 ：Step1. 初 始 化 一 块 缓 冲 区 ， 对 应 于 参 数 平 面 ， 将 其 所 有 数 据 置 为 0。Step2. 对 于 图 像 上 每 一 前 景 点 ， 求 出 参 数 平 面 对 应 的 直 线 ， 把 这 直 线 上 的所 有 点 的 值 都 加 。Step3. 找 到 参 数 平 面 上 峰 值 点 的 位 置 ， 这 些 位 置 的 坐 标 就 是 原 图 像 上 直 线的 参 数 ， 每 个 位 置 对 应 于 原 图 像 上 的 一 条 直 线 。上 面 是 霍 夫 变 换 识 别 直 线 的 基 本 思 想 。 在 实 际 应 用 中 ， 形 式ykxb的 直 线 方 程 没 有 办 法 表 示 x=c 形 式 的 直 线 （ 这 时 候 ， 直 线 的 斜 率 为 无 穷 大 ） 。所 以 实 际 应 用 中 ， 是 采 用 参 数 方 程 ： osiny这 样 ， 图 像 平 面 (x, y)空 间 上 的 一 个 点 就 对 应 到 参 数 空 间 中 的 一 条 正 弦 曲线 上 。 在 变 换 后 的 空 间 中 这 条 正 弦 曲 线 上 的 任 意 一 点 对 应 于 原 始 图 像 平 面 (x, y)空哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 12 -间 的 一 条 直 线 ， 这 条 直 线 必 通 过 这 个 点 ， 而 (x, y)空 间 中 所 有 共 线 的 点(,)ixy经 过 变 换 后 所 对 应 的 各 正 弦 曲 线 都 相 交 于 一 点 。图 2.4.2 霍 夫 变 换 识 别 直 线 （ 2）1.2 霍 夫 变 换 识 别 圆1） 半 径 已 知 的 圆 的 识 别利 用 霍 夫 变 换 检 测 出 半 径 已 知 的 圆 形 ， 是 将 图 像 平 面 上 的 每 一 点 对 应 到 参数 平 面 上 的 一 个 以 已 知 半 径 为 半 径 的 圆 。 经 过 霍 夫 变 换 ， 在 参 数 平 面 上 得 到 圆相 交 于 一 点 ， 这 个 点 的 坐 标 即 为 原 图 形 坐 标 平 面 上 待 识 别 的 圆 心 坐 标 。算 法 可 以 简 单 描 述 为 ： 取 和 图 像 平 面 一 样 的 参 数 平 面 ， 以 图 像 上 每 一 个 前景 点 为 圆 心 ， 以 已 知 的 半 径 在 参 数 平 面 上 画 圆 ， 并 把 结 果 进 行 累 加 。 最 后 找 出参 数 平 面 上 的 峰 值 点 ， 这 个 位 置 就 对 应 了 图 像 上 的 圆 心 。2） 未 知 半 径 的 圆 的 识 别在 第 一 个 问 题 基 础 上 ， 把 参 数 平 面 扩 大 称 为 三 维 空 间 ， 即 x-y-R 三 维 ，对 应 圆 的 圆 心 和 半 径 。 图 像 平 面 上 的 每 一 点 就 对 应 于 参 数 空 间 中 每 个 半 径 下 的一 个 圆 ， 在 参 数 的 三 维 空 间 中 得 到 一 个 圆 锥 。 最 后 找 出 参 数 空 间 中 的 峰 值 点 ，即 得 到 待 识 别 的 圆 的 圆 心 和 半 径 。由 于 霍 夫 变 换 具 有 良 好 的 抗 噪 声 性 能 和 对 部 分 遮 盖 的 不 敏 感 等 特 性 ， 又 不受 图 像 旋 转 的 影 响 ， 在 很 多 领 域 都 有 广 泛 的 应 用 ， 有 关 霍 夫 变 换 的 研 究 和 改 进也 很 多 。 例 如 广 义 霍 夫 变 换 、 随 机 霍 夫 变 换 、 快 速 霍 夫 变 换 等 等 ， 就 是 针 对 直线 的 霍 夫 变 换 也 有 很 多 改 进 算 法 。 由 于 时 间 的 原 因 ， 在 本 软 件 中 ， 只 是 使 用 了标 准 的 霍 夫 变 换 算 法 。哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 13 -2. 基 于 单 义 域 的 直 线 及 圆 识 别 算 法霍 夫 变 换 为 几 何 图 形 的 识 别 的 一 个 重 要 算 法 ， 但 是 由 于 该 标 准 算 法 的 时 间复 杂 度 和 空 间 复 杂 度 都 是 ， 其 中 m 是 参 数 坐 标 的 维 数 ， 虽 然 有 不 少 针()mON对 具 体 问 题 （ 例 如 直 线 识 别 ） 的 改 进 算 法 ， 其 在 实 际 使 用 中 也 存 在 计 算 量 大 的问 题 。 针 对 本 论 文 的 工 作 的 实 际 情 况 ， 参 考 文 献 【 1】 ， 并 进 行 了 适 当 的 简 化 ，完 成 了 论 文 的 识 别 部 分 。 下 面 就 对 这 个 基 于 单 义 域 的 识 别 算 法 进 行 简 单 的 介 绍 。2.1 多 义 域 的 获 得单 义 域 是 指 对 待 识 别 的 图 形 进 行 分 割 得 到 的 具 有 单 一 的 几 何 意 义 （ 线 段 或圆 弧 ） 点 的 集 合 。 对 图 片 进 行 从 上 往 下 、 从 左 往 右 的 扫 描 ， 根 据 交 点 进 行 分 割得 到 多 义 域 ， 多 义 域 中 的 点 构 成 一 个 连 通 区 域 。 对 多 义 域 进 行 识 别 并 分 割 得 到单 义 域 。多 义 域 由 链 表 实 现 。算 法 描 述 如 下 ：1 对 图 形 进 行 从 上 往 下 、 从 左 往 右 的 扫 描 ；2 对 每 一 个 前 景 点 ， 判 断 其 是 否 为 交 点 ；3 将 该 点 与 现 有 的 多 义 域 的 头 （ 如 果 其 头 节 点 不 是 交 点 ） 、 尾 （ 如 果 其尾 节 点 不 是 交 点 ） 节 点 进 行 比 较 ， 如 果 与 头 节 点 相 邻 ， 将 其 插 入 到 该多 义 域 的 头 节 点 之 前 ； 如 果 与 尾 节 点 相 邻 ， 将 其 插 入 到 该 多 义 域 的 尾节 点 之 后 。4 如 果 该 前 景 点 不 属 于 任 何 现 有 多 义 域 ， 则 以 该 点 为 头 节 点 生 成 新 的 多义 域 。5 直 到 图 形 扫 描 完 毕 。注 ： 交 点 的 判 断 。由 此 得 到 的 多 义 域 将 是 一 个 线 段 、 一 个 圆 弧 或 者 线 段 和 圆 弧 的 组 合 。 在 后续 的 识 别 过 程 中 将 把 不 是 单 义 域 的 进 行 分 裂 。哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 14 -2.2 最 小 二 乘 法 拟 合 直 线 和 圆最 小 二 乘 法 首 先 由 Karl Gauss 为 进 行 行 星 轨 道 预 测 的 研 究 而 提 出 的 。 现 在最 小 二 乘 法 已 经 变 成 从 实 验 数 据 来 进 行 参 数 估 计 的 主 要 手 段 。 由 最 小 二 乘 法 获得 的 估 计 在 一 定 条 件 下 有 最 佳 的 统 计 特 性 ： 一 致 、 无 偏 、 有 效 。 它 提 供 给 我 们一 个 数 学 程 式 ， 通 过 它 能 获 得 一 个 在 最 小 方 差 意 义 上 与 实 验 数 据 最 好 拟 合 助 模型 。运 用 最 小 二 乘 法 进 行 圆 的 拟 合 公 式 如 下 ：其 中 ， 为 样 点 ， 为 所 求 圆 心 ， 为 半 径 ， 为 平 均 径 向 误(,)ixy0(,)xy差 ， 为 最 大 径 向 误 差 。运 用 最 小 二 乘 法 进 行 直 线 拟 合 的 公 式 如 下 ：（ 待 填 充 ）哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 15 -2.3 多 义 域 分 裂 和 单 义 域 的 识 别对 2.1 中 得 到 的 多 义 域 ， 运 用 最 小 二 乘 法 进 行 拟 合 ， 对 于 拟 合 不 成 功 的 多义 域 运 用 首 尾 相 连 最 大 距 离 法 进 行 分 裂 ， 得 到 单 义 域 ， 并 记 录 下 各 单 义 域 的 拟合 结 果 ， 供 全 局 考 虑 ， 识 别 直 线 和 圆 用 。算 法 描 述 如 下 ：1 从 2.1 得 到 的 多 义 域 列 表 里 取 第 一 个 多 义 域 ；2 对 选 中 的 多 义 域 运 用 最 小 二 乘 法 进 行 圆 的 拟 合 ； 如 果 得 到 的 平 均 径 向误 差 和 最 大 径 向 误 差 小 于 指 定 阈 值 ， 则 认 为 拟 合 成 功 ， 该 多 义 域 为 一圆 弧 的 单 义 域 ； 记 录 拟 合 的 结 果 ， 作 为 总 体 识 别 的 种 子 圆 ， 转 向 5 执行 ， 否 则 执 行 3。3 对 选 中 的 多 义 域 运 用 最 小 二 乘 法 进 行 直 线 拟 合 ； 如 果 得 到 的 平 均 距 离误 差 和 最 大 距 离 误 差 小 于 指 定 阈 值 ， 则 认 为 拟 合 成 功 ， 该 多 义 域 为 一线 段 的 单 义 域 ； 记 录 拟 合 结 果 ， 作 为 总 体 识 别 的 种 子 直 线 ， 转 向 5 执行 ， 否 则 执 行 4。4 该 多 义 域 为 多 个 线 段 或 圆 弧 的 组 合 。 将 该 多 义 域 的 头 尾 节 点 连 接 ， 计算 该 多 义 域 中 各 点 与 头 尾 节 点 连 线 的 距 离 ， 取 距 离 最 大 的 点 ， 对 该 多义 域 进 行 分 裂 ， 得 到 两 个 新 的 多 义 域 ， 取 代 原 先 的 多 义 域 ； 转 向 2 执行 。5 取 多 义 域 列 表 中 的 下 一 个 ， 转 向 2 执 行 。由 此 ， 所 有 的 多 义 域 都 分 裂 为 单 义 域 ， 并 对 各 单 义 域 进 行 了 拟 合 。2.4 总 体 整 合 ， 识 别 直 线 和 圆对 2.3 得 到 的 单 义 域 列 表 进 行 总 体 的 整 合 ， 得 到 直 线 和 圆 。1 选 取 单 义 域 列 表 中 的 第 一 个 单 义 域 ， 将 其 拟 合 的 图 形 （ 直 线 或 圆 ） 作为 种 子 图 形 ；2 将 列 表 中 其 他 单 义 域 的 识 别 结 果 与 种 子 图 形 进 行 比 较 ， 如 果 误 差 小 于指 定 阈 值 ， 则 属 于 同 一 直 线 或 同 一 圆 ， 将 其 与 选 定 单 一 域 进 行 合 并 ，从 列 表 中 删 除 该 单 义 域 ；3 计 算 选 定 单 义 域 的 几 何 数 据 ， 得 到 图 形 ；哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 16 -4 选 取 列 表 中 的 下 一 个 单 义 域 ， 转 动 2 执 行 。3. 主 要 技 术3.1 Borland C+ Builder本 论 文 的 编 程 环 境 之 所 以 选 用 c+ builder 是 因 为 他 有 以 下 的 优 点 ： 输 出 入 接 口 设 计 简 单 提 供 一 流 的 开 发 环 境 提 供 最 标 准 的 C C 鲁 开 发 工 具 提 供 丰 富 的 组 件 与 最 强 劲 的 调 试 工 具 VCL 类 库 中 封 装 了 Windows 的图 形 设 备 接 口 (GDI)， 使 得 用 户 很 方 便 地 在 应 用 程 序 添 加 图 像 或 处 理 图 像 。图 像 类 主 要 有Tbitmap、 TBrush、 TCanves、 TFont、 TgraphakControl、 Tgraphic、 Ticon、 TJPEGImage、 TPen 和 Tpictur 以 Tmatifile 类 。3.2 虚 类 及 虚 方 法 的 使 用虚 类 和 虚 方 法 的 使 用 在 本 论 文 中 主 要 是 Cshapes 基 类 及 虚 方 法 的 实 现 。哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 17 -第 三 章 直 线 和 圆 的 识 别 和 编 辑 的 实 现第 一 节 系 统 的 层 次 结 构 的 图 示哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 18 -第 二 节 系 统 数 据 结 构 及 类 的 设 计1. 主 要 类 的 层 次 结 构1.1 图 形 处 理 类 ：1.2 识 别 用 类 ：哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 19 -2. 图 形 基 类 （ CShape）2.1 描 述图 形 基 类 ， 提 供 所 有 图 形 的 标 准 属 性 和 方 法 。 其 他 图 形 类 （ 直 线 、 圆 ） 等都 是 该 类 的 子 类 ， 继 承 其 所 有 的 public 属 性 和 方 法 ， 对 其 中 的 虚 方 法（ virtual） 进 行 重 定 义 和 实 现 。该 类 为 虚 类 ， 其 成 员 函 数 主 要 为 虚 函 数 ， 为 其 所 有 子 类 提 供 统 一 的 接 口 ，但 是 没 有 实 现 。 其 他 模 块 对 图 形 进 行 操 作 时 ， 除 非 生 成 新 的 实 例 （ Instance） ，都 无 须 知 道 所 操 作 的 是 哪 个 具 体 的 图 形 ， 而 统 一 使 用 Cshape 类 型 ， 为 程 序 的实 现 、 扩 充 和 维 护 提 供 很 大 方 便 。2.2 实 现class CShape public:/* 属性定义 */前景色（由于时间等的限制，本系统暂时只定义该图形的属性，其/ 他如：填充色，线条型，填充型等可扩充）TColor color;/* 编辑用属性 */编辑时标志该图形是否被选择bool isSelected;/编辑操作所选中的点TPoint * editP/* 识别用属性 */ 识别的效果描述，值越小说明识别效果越好/ 最小二乘法的平均误差；/ 霍夫变换：1 - 参数空间中该图形的值/最大值double chance;/图形上点的数量int pointCount;/* 成员函数定义 */* 显示和描述用方法 */ 显示图形：在指定的位图上显示图形 virtual void draw(Graphics:TBitmap * argDest);/ 描述图形：作为TtreeView的节点（主窗体使用）virtual void discript(int index, TTreeView * tree);/ 描述图形：返回描述图形的字符串virtual String discript();/* 识别用 */ 比较两个图形，如果是同一个图形，返回True，否则 False。/ 直线上的两个线段；圆上面的两个圆弧virtual bool similarWith(CShape * argShape);/ 合并两个图形/ 经过判断为相同的图形进行合并，返回True；否则返回 False。哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 20 -virtual bool mergeWith(CShape * argShape);/ 判断图形存在的可能性（利用具体图形的几何规则）virtual bool checkPossible();/* 编辑用 */ 判断是否点击该图形，若选中则当前编辑的图形改为当前图形virtual bool isClickOnShape(int x, int y);/ 取得鼠标形状：鼠标移动到选中图形的可操作点上时，显示为编辑形状virtual TCursor getCursor(int x, int y);/ 更新图形：将编辑点移动到(x, y)点。更新成功返回True，否则False。virtual bool update(int x, int y);3. 图 形 类 （ CLine、 CCircle）3.1 描 述图 形 类 是 几 何 图 形 的 具 体 实 现 ， 实 现 对 应 几 何 图 形 的 描 述 和 相 关 操 作 。 图形 类 有 共 同 的 父 类 CShape， 对 父 类 中 定 义 的 虚 方 法 根 据 本 几 何 图 形 的 特 征 进行 实 现 。根 据 要 求 ， 本 系 统 中 实 现 了 直 线 （ CLine） 和 圆 （ CCircle） 两 个 图 形 类 。其 他 简 单 的 几 何 图 形 如 椭 圆 、 矩 形 等 也 可 以 类 似 的 方 法 实 现 ， 作 为 本 系 统 的 一个 扩 充 。本 系 统 中 ， 直 线 类 采 用 直 观 的 的 形 式 来 描 述 直 线 （ 既 避 免0AxBy点 斜 式 不 能 描 述 竖 直 直 线 ， 也 避 免 极 坐 标 方 程 转 换 的 问 题 ） 。 因 为 成 比 例 的 两组 和 表 示 同 一 条 直 线 ， 所 以 规 定 ， 如 果 B 参 数 不 为 0， 则1(,)ABC2(,)。 由 于 要 识 别 图 像 中 的 线 段 ， 所 以 增 加 两 个 端 点 进 行 限 制 。直 线 类 有 三 个 点 可 以 编 辑 ： 1） 两 个 端 点 ， 选 中 一 个 端 点 并 移 动 ， 是 以 另一 端 点 为 轴 进 行 旋 转 ； 2） 线 段 的 中 点 ， 选 中 中 点 并 移 动 ， 是 平 移 整 个 直 线 。圆 类 采 用 的 形 式 描 述 （ 其 中 为 圆 心 ， R 为 半2()()ccxyR(,)cxy径 ） ， 直 观 方 便 。 圆 上 有 两 个 点 支 持 编 辑 操 作 ： 1） 圆 心 ， 选 中 圆 心 并 移 动 ，是 平 移 整 个 圆 ； 2） 圆 上 的 一 个 点 ， 选 中 该 点 并 移 动 ， 是 改 变 圆 的 半 径 ， 圆 心不 变 。3.2 实 现 直 线 类 （ CLine）哈 尔 滨 工 业 大 学 本 科 毕 业 设 计 （ 论 文 ）- 21 -class CLine: public CShape public:/* 初始化 */CLine(double argA, double argB, double argC);/* 直线的属性