基于草图理解的数字黑板系统

收 稿 日 期 2006207220基 金 项 目 科 学 技 术 部 科 技 型 中 小 企 业 技 术 创 新 基 金 项 目 (04c26222200056)作 者 简 介 李 益 民 (1966 ) ,男 ,副 教 授 ,主 要 从 事 智 能 人 机 交 互 、 数 据 管 理 研 究 ;解 成 俊 (1962 ) ,男 ,博 士 ,教 授 ,主 要 从 事 图 形图 像 处 理 研 究 .文 章 编 号 100021832 (2008) 0120045206基 于 草 图 理 解 的 数 字 黑 板 系 统李 益 民 ,解 成 俊(北 华 大 学 计 算 机 技 术 学 院 ,吉 林 吉 林 132021)摘 要 针 对 电 子 教 学 系 统 人 机 交 互 的 自 然 性 和 用 户 适 应 性 不 足 的 问 题 ,研 究 设 计 了 基 于草 图 的 人 机 交 互 技 术 的 新 型 电 子 教 学 系 统 ,提 出 了 基 于 用 户 信 息 的 草 图 识 别 方 法 . 实 验 表 明 该方 法 具 有 很 好 的 效 果 .关 键 词 电 子 教 学 系 统 ;人 机 交 互 ;草 图 识 别 ;用 户 适 应 性中 图 分 类 号 TP 391 学 科 代 码 520 60 文 献 标 识 码 A0 引 言现 在 各 级 学 校 的 教 师 使 用 计 算 机 辅 助 教 学 日益 普 遍 . 通 常 教 师 按 照 传 统 教 学 方 式 进 行 教 学 的同 时 ,使 用 计 算 机 将 预 制 好 的 电 子 文 档 或 者 应 用程 序 通 过 投 影 机 播 放 出 来 . 这 种 新 的 教 学 方 式 虽然 丰 富 了 信 息 的 内 容 ,如 图 、 表 、 影 像 、 大 块 文 字 、模 拟 演 示 的 展 示 ,却 限 制 了 教 师 生 动 自 如 的 讲 授 ,限 制 了 教 师 与 学 生 间 的 交 流 和 互 动 ,限 制 了 教 师自 然 连 续 的 教 学 . 基 于 草 图 的 人 机 交 互 技 术 是 一种 通 过 纸 和 笔 的 自 由 勾 画 、 手 势 等 方 法 实 现 自 然高 效 人 机 交 互 的 技 术 ,目 前 已 取 得 一 些 研 究 成果 127 .本 文 在 已 有 的 基 于 草 图 的 人 机 交 互 技 术研 究 成 果 基 础 上 研 究 设 计 了 一 种 新 型 的 电 子 教 学系 统 数 字 黑 板 系 统 . 数 字 黑 板 系 统 应 用 草 图理 解 技 术 ,实 现 以 计 算 机 系 统 为 中 心 向 以 用 户 为中 心 的 交 互 模 式 转 变 ,使 得 操 作 上 更 接 近 于 教 师传 统 教 学 的 习 惯 .本 文 讨 论 了 相 关 工 作 ,描 述 了 系 统 的 体 系 结构 ,给 出 了 系 统 的 关 键 技 术 ,提 出 了 基 于 用 户 信 息的 高 效 草 图 识 别 方 法 .1 相 关 工 作研 究 符 合 教 师 自 然 教 学 习 惯 的 电 子 教 学 系 统受 到 广 泛 关 注 .文 献 8 讨 论 了 电 子 教 学 系 统 设 计 与 实 现 的关 键 开 发 技 术 、 主 体 结 构 、 基 本 功 能 ,提 出 以 ASP实 现 主 要 交 互 功 能 . 文 献 9 提 出 了 在 计 算 机 屏 幕上 直 接 进 行 标 注 的 方 法 ,可 以 在 讲 课 过 程 中 直 接在 计 算 机 屏 幕 上 现 场 标 注 信 息 或 者 绘 制 简 单 图 .文 献 829 基 于 传 统 的 WMP 界 面 技 术 研 究 电 子教 学 系 统 的 交 互 问 题 ,但 无 法 实 现 自 然 高 效 的 人机 交 互 .文 献 10 用 基 于 草 图 的 人 机 交 互 技 术 设 计 并实 现 了 一 套 几 何 教 学 系 统 ,并 将 双 向 几 何 约 束 的相 关 技 术 应 用 于 该 系 统 中 . 文 献 11 提 出 了 基 于草 图 的 人 机 交 互 界 面 制 作 新 的 解 决 方 案 ,并 实 现中 科 国 风 笔 式 电 子 教 学 系 统 ,该 系 统 集 成 了 汉 字 、公 式 、 图 形 和 手 势 等 多 种 识 别 技 术 . 文 献 10211 基 于 草 图 的 人 机 交 互 技 术 研 究 电 子 教 学 系 统 的 交互 问 题 ,该 系 统 的 人 机 交 互 自 然 高 效 ,但 对 用 户 适应 性 问 题 很 少 讨 论 .第 40 卷 第 1 期 东 北 师 大 学 报 ( 自 然 科 学 版 ) Vol. 40 No. 12008 年 3 月 Journal of Northeast Normal University (Natural Science Edition) March 2008本 文 设 计 和 实 现 的 系 统 不 仅 为 用 户 提 供 了 自然 高 效 的 交 互 手 段 ,还 在 草 图 识 别 方 法 中 引 入 用户 信 息 ,屏 蔽 用 户 绘 制 习 惯 差 异 ,具 有 良 好 的 用 户适 应 性 .2 系 统 体 系 结 构 设 计数 字 黑 板 系 统 包 括 三 个 相 对 独 立 的 组 成 部分 :数 字 黑 板 、 消 息 Agent 和 屏 幕 标 注 . 整 个 系 统结 构 如 图 1 所 示 .图 1 数 字 黑 板 系 统 结 构(1)数 字 黑 板 包 括 笔 式 交 互 界 面 、 输 入 识 别 、各 个 应 用 (如 书 写 、 显 示 、 图 形 约 束 处 理 等 )三 个 部分 . 数 字 黑 板 结 构 如 图 2 所 示 .图 2 数 字 黑 板 结 构系 统 使 用 笔 交 互 技 术 作 为 系 统 的 用 户 界 面 技术 . 笔 可 以 输 入 离 散 事 件 、 笔 画 、 手 势 等 三 类 信 息 .离 散 事 件 是 指 类 似 鼠 标 的 点 击 事 件 ,如 落 笔 事 件 、击 键 事 件 等 ;笔 画 是 指 在 一 次 相 邻 的 落 笔 、 提 笔 之间 笔 所 经 过 的 轨 迹 ,笔 画 构 成 绘 制 目 标 的 一 部 分 ;手 势 是 用 来 进 行 辅 助 编 辑 的 笔 画 ,它 不 直 接 构 成绘 制 目 标 . 用 户 在 板 书 书 写 、 绘 画 过 程 中 ,以 笔 为主 要 工 具 ,结 合 手 势 辅 助 书 写 绘 画 完 成 各 种 输 入和 操 作 ,很 方 便 地 完 成 各 种 交 互 任 务 .笔 式 交 互 界 面 :数 字 黑 板 用 户 界 面 分 为 黑 板区 和 辅 助 区 . 黑 板 区 用 于 板 书 书 写 、 绘 画 ,主 要 使用 手 势 操 作 ,辅 以 指 点 操 作 ;辅 助 区 由 各 种 工 具 、状 态 开 关 构 成 ,如 笔 、 板 擦 、 样 式 、 颜 色 、 操 作 状 态开 关 、 约 束 开 关 等 ,使 用 指 点 操 作 .几 何 图 形 识 别 :使 用 几 何 图 形 识 别 方 法 对 用户 的 勾 画 进 行 识 别 ,生 成 相 应 的 几 何 图 形 对 象 ,并负 责 图 形 的 存 储 、 访 问 等 .勾 画 :将 离 散 的 点 生 成 笔 画 对 象 ,并 负 责 对 笔画 定 向 进 行 存 储 、 访 问 等 .笔 画 预 处 理 :对 用 户 在 “ 电 子 纸 ” 上 的 输 入 进行 除 噪 和 数 据 封 装 ,生 成 单 笔 画 对 象 ,并 对 笔 画 对象 进 行 存 储 、 访 问 和 维 护 .手 势 识 别 :使 用 手 势 识 别 方 法 对 用 户 的 勾 画进 行 识 别 ,识 别 出 相 应 的 手 势 类 别 .语 义 理 解 :根 据 手 势 识 别 结 果 和 一 般 指 点 操作 提 炼 出 操 作 原 语 ,并 提 交 给 交 互 操 作 处 理 模 块 .交 互 操 作 处 理 :根 据 操 作 原 语 生 成 交 互 任 务 ,并 执 行 交 互 任 务 完 成 对 笔 画 、 图 元 、 图 形 进 行 相 应的 操 作 处 理 .图 层 处 理 :板 书 书 写 绘 画 、 图 元 分 别 处 在 不 同的 图 层 ,叠 加 后 得 到 最 终 显 示 图 层 .其 他 模 块 完 成 显 示 、 保 存 、 回 放 、 黑 板 视 窗 等64 东 北 师 大 学 报 (自 然 科 学 版 ) 第 40 卷功 能 .(2)消 息 Agent 在 后 台 运 行 ,负 责 监 视 操 作 系统 中 用 户 当 前 的 操 作 活 动 并 进 行 判 断 ,如 果 属 于功 能 中 规 定 的 屏 幕 标 注 动 作 时 ,则 将 该 信 息 发 给屏 幕 标 注 模 块 . 消 息 Agent 包 括 规 则 库 和 消 息 识别 、 消 息 过 滤 、 消 息 发 送 三 个 处 理 过 程 . 消 息 过 滤监 视 过 滤 出 用 户 对 计 算 机 的 操 作 消 息 . 规 则 库 和消 息 识 别 按 照 规 则 识 别 出 标 注 消 息 ,并 通 过 消 息发 送 ,将 该 消 息 发 送 给 屏 幕 标 注 模 块 ,其 他 消 息 则还 给 操 作 系 统 .消 息 Agent 使 用 Windows 的 Hook 技 术 实 现对 Windows 系 统 消 息 队 列 中 消 息 的 过 滤 .(3)屏 幕 标 注 是 后 台 运 行 线 程 ,按 标 注 消 息 直接 将 标 注 信 息 显 示 在 计 算 机 屏 幕 上 . 屏 幕 标 注 使用 DirectDraw 技 术 将 标 注 信 息 直 接 写 屏 ,从 而 实现 对 其 他 应 用 程 序 用 户 显 示 界 面 的 标 注 . 标 注 内容 在 设 置 的 时 间 之 后 自 动 被 清 除 .3 关 键 技 术 研 究作 为 提 供 自 然 高 效 交 互 手 段 的 电 子 教 学 系统 ,其 核 心 在 于 交 互 手 段 ,相 关 技 术 为 关 键 技 术 .主 要 体 现 在 操 作 命 令 、 高 效 在 线 草 图 识 别 和 用 户适 应 性 三 个 方 面 .3. 1 手 势 的 设 计 和 识 别在 基 于 草 图 的 交 互 中 手 势 至 关 重 要 . 手 势 是 自由 勾 画 的 具 有 一 定 意 义 的 线 条 组 合 ,与 系 统 的 命 令之 间 建 立 了 一 定 的 语 义 级 映 射 ,草 图 过 程 可 以 由 一系 列 手 势 完 成 . 手 势 设 计 遵 循 易 于 绘 制 、 易 于 记 忆 、跟 视 觉 直 观 有 联 系 和 手 势 之 间 区 分 度 大 的 原 则 .系 统 共 有 9 种 交 互 命 令 :选 择 、 复 制 、 粘 贴 、 删除 、 撤 销 、 确 认 、 移 动 、 旋 转 、 拉 伸 .其 中 ,移 动 、 旋 转 、 拉伸 用 指 点 操 作 完 成 ,其 余 6 种 使 用 手 势 操 作 完 成 .所有 的 手 势 都 是 单 笔 画 并 且 以 笔 的 右 击 事 件 作 为 开始 ,如 图 3 所 示 .手 势 识 别 就 是 判 断 新 输 入 的 手 势 属 于 预 先 定义 的 哪 一 类 手 势 的 过 程 . 系 统 选 用 经 典 的 单 笔 画识 别 方 法 Rubine 方 法 2 . Rubine 方 法 使 用 初始 角 的 正 余 弦 值 、 闭 包 盒 对 角 线 的 长 度 及 倾 斜 度 、起 点 与 终 点 的 距 离 等 11 个 几 何 特 征 和 笔 画 的 最大 速 度 值 、 起 点 到 终 点 的 时 间 值 等 2 个 动 态 特 征组 成 的 13 维 向 量 表 示 笔 画 . 通 过 训 练 获 取 各 分 量的 权 重 ,然 后 根 据 一 个 线 性 评 估 函 数 来 区 分 不 同的 笔 画 . Rubine 采 用 统 计 方 法 对 手 势 进 行 分 类 ,只 需 要 很 少 的 训 练 样 本 ,识 别 效 果 较 理 想 . 预 先 定义 的 手 势 保 存 在 手 势 库 中 .图 3 手 势 示 例3. 2 基 于 用 户 信 息 的 草 图 识 别草 图 识 别 采 用 基 于 图 元 表 示 的 方 法 ,包 括 分割 、 拟 合 、 规 整 、 识 别 等 步 骤 . 具 体 方 法 较 多 ,如SR G法 识 别 精 确 但 时 间 开 销 大 3 ;边 表 法 识 别 速度 快 但 检 索 不 精 确 4 ;笔 序 法 识 别 速 度 较 快 且 检索 精 确 5 .本 文 提 出 基 于 用 户 信 息 的 识 别 方 法 ( SRU I)改 进 完 善 了 笔 序 法 ,如 图 4 所 示 . 主 要 包 括 输 入 笔画 处 理 、 图 形 匹 配 和 用 户 信 息 . 输 入 笔 画 处 理 将 用户 输 入 的 草 图 信 息 进 行 除 噪 处 理 、 笔 画 分 割 、 基 本图 元 识 别 、 基 本 图 元 间 空 间 关 系 表 示 和 时 序 (笔序 )关 系 表 示 . 用 户 信 息 用 决 策 查 找 树 记 录 用 户 绘制 习 惯 信 息 (对 于 一 个 指 定 的 几 何 图 形 ,用 户 通 常会 按 照 一 个 相 对 固 定 的 笔 序 进 行 绘 制 ) . 图 形 匹 配首 先 按 用 户 信 息 决 策 查 找 树 匹 配 图 形 ,匹 配 失 败后 按 其 他 方 法 (如 SR G法 )匹 配 ,并 起 到 在 线 训 练的 作 用 .(1)用 户 特 征 信 息 的 表 示构 造 用 户 特 征 信 息 使 用 笔 画 、 笔 画 间 关 系 和笔 序 等 三 类 信 息 .定 义 1 笔 画 表 示 为 一 个 二 元 组 :s = ( i d , di r) .i d 为 笔 画 类 别 ,如 线 段 、 圆 弧 、 椭 圆 . di r 为 笔 画 方向 ,以 直 角 坐 标 系 x 轴 正 方 向 为 笔 画 方 向 1 ,逆 时针 依 次 旋 转 / 4 得 到 方 向 2 ,方 向 3 , ,方 向8 ,封 闭 笔 画 ,用 方 向 0 来 标 记 .定 义 2 笔 画 间 关 系 表 示 为 一 个 一 元 组 :sr = ( r) .依 据 图 形 重 心 当 前 笔 画 与 前 一 笔 画 的 位 置 关 系 信息 分 为 上 、 下 、 左 、 右 、 左 上 、 左 下 、 右 上 、 右 下 8 种 ,每 个 图 形 的 第 一 个 笔 画 无 关 系 信 息 .定 义 3 笔 序 表 示 为 一 个 有 序 二 元 组 :ts = v1 , v2 .vi = ( si , sri , w i) , si 为 笔 画 , ri 为 笔 画 间 关 系 , w i为 该 笔 画 结 点 权 重 值 . 该 有 序 序 列 由 用 户 绘 画 笔74第 1 期 李 益 民 ,等 :基 于 草 图 理 解 的 数 字 黑 板 系 统画 的 相 对 先 后 顺 序 得 到 .定 义 4 用 户 特 征 信 息 表 示 为 树 :T = ( V , E) .V 为 树 的 节 点 集 合 ,V = ( v1 , v2 , , v m ) ,v i = ( si , sri , GList i) ;E 为 树 的 边 集 合 ,E = ( ts1 , ts2 , , tsn) .图 4 几 何 图 形 识 别 方 法图 5 实 验 用 图 形多 个 用 户 特 征 信 息 表 示 为 一 森 林 .为 降 低 搜 索 复 杂 度 ,树 的 每 个 节 点 存 储 该 节点 向 下 搜 索 到 的 可 能 图 形 类 别 和 权 重 ,定 义 为 预测 图 表 GList .定 义 5 预 测 图 表 为 一 个 有 序 表 :GList = g1 , g2 , , gk ,gi = ( gi d , w ) ,gi d 为 图 形 类 别 , w 为 该 图 形 权 重 . GList 依 据 图形 权 重 排 序 .为 降 低 用 户 特 征 信 息 树 整 理 复 杂 度 ,定 义 笔序 信 息 表 SList . SList 记 录 用 户 绘 图 的 笔 序 信 息和 每 种 笔 序 画 法 的 使 用 频 率 .定 义 6 笔 序 信 息 表 为 一 个 线 性 表 :SList = ( us1 , us2 , , usl) ,usi = ( s , num ) ,num 为 笔 序 画 法 的 使 用 频 率 .(2)用 户 特 征 信 息 的 建 立用 户 特 征 信 息 树 为 决 策 查 找 树 ,为 动 态 适 应用 户 特 性 ,定 义 了 三 个 操 作 .添 加 节 点 :若 在 决 策 查 找 树 的 某 一 层 中 找 不到 当 前 笔 画 精 确 匹 配 的 结 点 ,则 在 该 层 中 添 加 新的 结 点 ,用 当 前 笔 画 值 初 始 化 新 增 节 点 . 该 节 点 之84 东 北 师 大 学 报 (自 然 科 学 版 ) 第 40 卷后 用 户 输 入 笔 画 都 作 为 新 结 点 添 加 到 树 中 .调 整 节 点 :若 在 该 层 中 找 到 当 前 笔 画 精 确 匹配 的 结 点 ,则 调 整 GList . 若 表 中 已 存 在 对 应 图 形类 别 ,则 调 整 其 权 重 ,并 重 排 表 ;否 则 在 表 中 添 加该 类 别 图 形 ,并 赋 初 始 权 重 值 .剪 枝 :整 理 SList ,删 除 很 少 使 用 的 笔 序 画 法 ,并 依 据 整 理 后 的 SList 剪 枝 决 策 树 .图 6 命 中 次 数 和 识 别 效 果 比 较(3)草 图 识 别 算 法算 法 通 过 搜 索 决 策 树 完 成 草 图 识 别 . 算 法 如下 : 置 当 前 节 点 为 决 策 树 根 节 点 ,当 前 笔 画 为用 户 输 入 的 第 一 个 笔 画 . 依 据 GList 在 当 前 节 点 的 子 节 点 中 查 找 与当 前 笔 画 精 确 匹 配 的 结 点 . 若 找 到 ,则 执 行 调 整 节点 操 作 ;若 找 不 到 ,则 执 行 添 加 节 点 操 作 . 将 找 到的 节 点 或 新 添 加 的 节 点 置 为 当 前 节 点 . 若 不 是 用 户 输 入 的 最 后 一 个 笔 画 ,则 获 取下 一 个 笔 画 ,回 步 骤 . 若 当 前 节 点 的 图 形 类 型 不 为 空 ,则 查 找 成功 ;否 则 ,这 种 笔 序 的 画 法 在 决 策 树 中 没 有 记 录 ,使 用 其 他 方 法 ( SR G) 识 别 该 草 图 ,并 在 当 前 节 点中 记 录 该 图 形 类 型 . 若 是 一 种 新 的 笔 序 的 画 法 ,则 在 SList 中添 加 一 条 新 记 录 ,记 录 其 笔 序 、 图 形 类 别 ,使 用 次数 设 置 为 1 ;若 这 种 笔 序 的 画 法 已 存 在 ,则 其 对 应记 录 的 使 用 次 数 加 1.(4)算 法 验 证 与 分 析算 法 基 于 用 户 多 次 绘 制 一 个 图 形 后 绘 制 方 法快 速 趋 向 收 敛 的 假 设 . 识 别 的 正 确 率 和 速 度 依 赖于 假 设 的 成 立 . 实 验 数 据按 笔 画 笔 数 和 笔 画 间 关 系 等 图 形 构 成 因 素 从UML 设 计 和 电 路 图 设 计 的 常 用 图 符 中 选 取 50 个复 杂 图 形 ,用 来 评 测 和 对 比 草 图 识 别 算 法 ,如 图 5所 示 ,收 集 这 50 个 图 形 不 同 画 法 的 3 000 个 数 据 . 结 果 分 析根 据 收 集 结 果 如 图 6 (a) 所 示 ,在 用 户 信 息 初始 为 空 的 情 况 下 ,在 后 1 000 个 输 入 中 使 用 990次 SRU I 法 匹 配 ,只 使 用 了 10 次 SR G法 ,命 中 率达 99 %. 证 明 用 户 多 次 绘 制 一 个 图 形 后 绘 制 方 法快 速 趋 向 收 敛 的 假 设 是 成 立 的 .根 据 收 集 结 果 如 图 6 (b) 所 示 ,在 较 高 命 中 率下 SRUI平 均 识 别 时 间 为 几 毫 秒 ,接 近 笔 序 法 的 识别 速 度 .几 毫 秒 完 全 可 以 满 足 应 用 中 的 交 互 要 求 .根 据 收 集 结 果 如 图 6 (c) 所 示 ,在 较 高 命 中 率下 SRU I 识 别 正 确 率 接 近 SR G法 ,好 于 笔 序 法 .4 结 束 语传 统 电 子 教 学 系 统 人 机 交 互 的 自 然 性 差 ,用户 适 应 性 不 强 ,本 文 研 究 、 设 计 的 系 统 既 有 自 然 高效 的 人 机 交 互 性 、 多 用 户 适 应 性 ,又 能 对 “ 展 示 型 ”94第 1 期 李 益 民 ,等 :基 于 草 图 理 解 的 数 字 黑 板 系 统电 子 教 案 进 行 有 效 标 注 ,满 足 符 合 教 师 自 然 教 学习 惯 的 要 求 . 技 术 上 ,系 统 提 出 的 基 于 用 户 信 息 的草 图 识 别 方 法 既 保 证 了 草 图 识 别 精 确 ,又 提 高 了识 别 速 度 . 今 后 工 作 将 针 对 不 同 学 科 课 程 教 学 内容 的 特 点 和 交 互 特 点 进 一 步 研 究 系 统 人 机 交 互 的学 科 适 应 性 问 题 ,以 获 得 更 好 的 应 用 效 果 .参 考 文 献 1 孙 正 兴 ,冯 桂 焕 ,周 若 鸿 . 基 于 草 图 的 人 机 交 互 技 术 研 究 进 展 J . 计 算 机 辅 助 设 计 与 图 形 学 学 报 ,2005 ,17 (9) :188921899. 2 RUBINE D. Specifying gestures by exampleJ . Computer Graphics ,1991 ,25 : 3292337. 3 XU XIAO2GAN G ,SUN ZHEN G2XIN G. Matching spatial relation graphs using a constrained partial permutation strategyJ .Journalof Southeast University , 2003 , 19 (3) :2362239. 4 孙 正 兴 ,徐 晓 刚 . 支 持 方 案 设 计 的 图 形 输 入 工 具 J . 计 算 机 辅 助 设 计 与 图 形 学 学 报 ,2003 ,15 (9) :114521152. 5 尹 建 峰 ,孙 正 兴 . 基 于 笔 序 的 手 绘 草 图 识 别 方 法 J . 计 算 机 科 学 ,2005 ,32 (1) :1982201. 6 董 士 海 ,王 坚 ,戴 国 忠 . 人 机 交 互 和 多 通 道 用