(Microsoft Word - \253\312\255\261_\246\321\244\375_)

Transcription

1 中 華 大 學 碩 士 論 文 利 用 Matlab RWTH 工 具 箱 設 計 解 魔 術 方 塊 機 器 人 Design of a Rubik s Cube Solver Robot using Matlab RWTH toolbox 系 所 別 : 電 機 工 程 學 系 碩 士 班 學 號 姓 名 : M 鮑 柏 年 指 導 教 授 : 黃 啟 光 博 士 中 華 民 國 九 十 九 年 八 月

2 摘 要 智 慧 型 機 器 人 結 合 了 電 子 機 械 自 動 化 與 人 工 智 慧, 並 且 廣 泛 的 應 用 於 工 業 以 及 服 務 業 和 娛 樂 用 途, 是 近 年 來 備 受 矚 目 的 產 業 之 一 在 此, 本 論 文 以 PC 為 基 礎 設 計 一 解 魔 術 方 塊 機 器 人, 並 利 用 樂 高 積 木 的 組 裝 快 速 與 低 成 本 的 特 性 架 設 所 需 的 實 驗 機 構 在 論 文 中, 透 過 MATLAB 的 影 像 擷 取 與 影 像 處 理 取 得 魔 術 方 塊 的 六 面 色 值, 並 帶 入 魔 術 方 塊 解 題 器 中 解 題, 最 後 將 解 題 資 訊 轉 換 成 馬 達 控 制 訊 號 進 行 魔 術 方 塊 的 轉 正 動 作 整 體 的 實 驗 過 程 結 合 了 程 式 設 計 與 運 用, 以 及 硬 體 設 備 的 應 用 關 鍵 字 : 智 慧 型 機 器 人 魔 術 方 塊 影 像 處 理 i

3 Abstract Robotics industry, a technology integration and high skill value-added industries, is a combination of mechanical, automation, electrical, electronics, information software, communications and creative content related to technology. In this thesis, a robot for a Rubik's cube game is developed based on Matlab and LEGO mindstorms NXT. In the Matlab part, a CCD Web camber is used to obtain the color information of the real-time Rubik's cube though image acquisition toolbox and image processing toolbox. And, a Rubik's cube solver is used to obtain the solve actions. In the LEGO mindstorms NXT part, a robot s arm used the DC servomotor to get the action form the Rubik's cube solver. From the experimental results, the favorable results can be achieved by the proposed robot setup. Keyword: intelligent robot, Rubik's cube, image processing ii

4 致 謝 在 研 究 所 兩 年 的 求 學 生 涯 中, 承 蒙 指 導 教 授 黃 啟 光 博 士 在 學 業 上 及 研 究 方 面 給 予 悉 心 的 指 導 與 鼓 勵, 以 及 許 駿 飛 教 授 的 諄 諄 教 誨 與 指 點 迷 津, 帶 領 我 走 向 更 深 的 領 域, 探 索 以 往 未 曾 想 過 的 問 題 學 習 過 程 中, 老 師 總 是 不 厭 其 煩 的 教 導, 從 最 基 本 的 一 步 一 步 向 上 累 積 ; 同 時 在 待 人 處 事 人 生 規 劃 方 面 亦 給 予 寶 貴 的 意 見, 讓 我 對 生 涯 規 劃 以 及 研 究 態 度 更 加 積 極, 謹 此 致 上 由 衷 的 謝 意 其 次 要 感 謝 實 驗 室 的 許 多 學 長 同 學 以 及 學 弟 的 幫 忙 指 導 與 精 神 上 的 鼓 勵, 其 中 特 別 感 謝 同 學 沈 漢 賢 在 數 學 以 及 程 式 方 面 給 予 的 寶 貴 意 見 僅 將 此 篇 論 文 獻 給 關 心 我 鼓 勵 我 的 人, 在 我 遇 到 難 題 困 惑 沮 喪 時 默 默 支 持 我 的 人, 深 深 的 感 謝 他 們 使 我 得 以 完 成 此 論 文, 願 與 他 們 分 享 此 榮 耀 鮑 柏 年 謹 識 於 中 華 大 學 2010 年 8 月 iii

5 目 錄 摘 要... i Abstract... ii 致 謝... iii 目 錄... iv 圖 目 錄... v 表 目 錄... vii 第 一 章 序 論... 錯 誤! 尚 未 定 義 書 籤 1-1 智 慧 型 機 器 人 介 紹 樂 高 機 器 人 介 紹 研 究 背 景 與 目 的... 9 第 二 章 機 器 平 台 介 紹 整 體 架 構 NXT 控 制 盒 LEGO 伺 服 馬 達 BricxCC 與 NXC 介 紹 MATLAB 影 像 擷 取 與 處 理 工 具 箱 RWTH Toolbox 介 紹 第 三 章 解 魔 術 方 塊 機 器 人 設 計 影 像 處 理 與 結 果 魔 術 方 塊 解 題 與 結 果 第 四 章 結 論 與 未 來 研 究 結 論 未 來 研 究 參 考 文 獻 iv

6 圖 目 錄 圖 1-1 日 本 本 田 公 司 所 發 表 之 Asimo 機 器 人... 2 圖 1-2 具 有 人 工 智 慧 的 Probo... 3 圖 1-3 具 有 療 癒 功 能 的 Paro... 3 圖 1-4 導 覽 機 器 人 小 美... 4 圖 1-5 室 內 多 功 能 服 務 型 機 器 人... 5 圖 1-6 QB 遠 端 臨 場 機 器 人... 6 圖 1-7 樂 高 Mindstorms NXT 機 器 人... 7 圖 1-8 NXT-G 使 用 介 面... 8 圖 1-9 各 種 多 階 與 非 標 準 魔 術 方 塊 圖 1-10 以 PC 為 基 礎 之 解 魔 術 方 塊 機 器 人 圖 1-11 以 PC 為 基 礎 之 解 魔 術 方 塊 樂 高 機 器 人 圖 1-12 以 Andriod 為 基 礎 之 解 魔 術 方 塊 樂 高 機 器 人 圖 1-13 以 NXT 為 基 礎 之 解 魔 術 方 塊 樂 高 機 器 人 圖 2-1 解 魔 術 方 塊 機 器 人 示 意 圖 圖 2-2 NXT 控 制 盒 圖 2-3 LEGO 伺 服 馬 達 解 析 圖 圖 2-4 光 學 編 碼 器 AB 相 訊 號 圖 2-5 BricxCC 程 式 開 發 環 境 圖 2-6 Watching the Brick 的 資 料 圖 表 化 功 能 ( 光 感 應 器 )...20 圖 2-7 影 像 擷 取 圖 樣...23 圖 2-8 影 像 處 理 樣 本 圖 2-9 PC 與 NXT 連 線 圖 圖 2-10 ECRobot NXT 模 組 方 塊 v

7 圖 2-11 ECRobot simulink 環 境 圖 3-1 魔 術 方 塊 六 面 影 像 圖 3-2 由 圖 3-1 轉 換 的 灰 階 圖 案 圖 3-3 由 圖 3-2 轉 換 的 二 元 化 影 像 圖 3-4 各 色 面 展 開 圖 圖 3-5 LBL 基 本 解 法 流 程 圖 圖 3-6 解 題 器 模 擬 圖 圖 3-7 魔 術 方 塊 的 6 個 面 色 值 代 入 解 題 器 中 圖 3-8 解 題 器 解 題 過 程 圖 3-9 方 塊 六 面 位 置 定 義 圖 3-10 機 器 人 的 翻 轉 方 塊 與 旋 轉 方 塊 vi

8 表 目 錄 表 2-1 MATLAB 影 像 轉 換 表 3-1 魔 術 方 塊 6 色 取 樣 表 3-2 白 色 面 九 格 方 塊 像 素 值 vii

9 第 一 章 序 論 1.1 智 慧 型 機 器 人 介 紹 機 器 人 產 業 是 結 合 機 械 自 動 化 電 機 電 子 資 訊 軟 體 通 訊 及 創 意 內 容 等 相 關 技 術, 為 一 高 度 技 術 整 合 且 高 附 加 價 值 的 明 星 產 業, 可 預 期 的 是 機 器 人 也 即 將 進 入 家 庭 環 境 成 為 一 般 民 眾 生 活 的 一 部 分, 對 於 國 家 發 展 與 國 家 經 濟 及 工 業 整 體 發 展 具 有 關 鍵 性 指 標 的 地 位 機 器 人 的 關 鍵 技 術 涵 蓋 機 械 結 構 設 計 馬 達 設 計 與 控 制 即 時 影 像 / 語 音 處 理 感 測 電 路 設 計 與 實 現 嵌 入 式 系 統 軟 硬 體 設 計 微 處 理 器 應 用 與 IC 設 計 智 慧 型 控 制 技 術 機 電 整 合 等 等 的 專 業 知 識, 是 一 個 需 要 系 統 整 合 才 能 有 效 發 展 的 研 究 領 域 [1-4] 臺 灣 社 會 從 以 農 業 為 主 的 被 殖 民 社 會, 轉 變 成 為 以 工 商 業 為 主 的 社 會, 人 民 的 生 活 水 準 提 高, 各 項 物 質 生 活 品 質 提 升, 對 於 精 神 生 活 的 重 視 也 與 日 俱 增 統 計 台 灣 三 大 都 會 區 寂 寞 人 口 達 107 萬, 生 活 型 態 趨 向 單 身 化, 再 加 上 快 節 奏 的 都 市 生 活 步 調 緊 張 的 社 會 關 係, 使 得 生 活 感 受 產 生 更 多 壓 力, 寂 寞 因 而 變 成 為 都 市 男 女 的 集 體 感 傷 因 此, 台 灣 開 始 出 現 第 四 級 幸 福 產 業, 其 目 的 主 要 讓 消 費 者 有 幸 福 親 密 感 滿 足 被 關 懷, 並 找 到 歸 屬 的 產 業, 其 中 智 慧 型 機 器 人 便 佔 有 舉 足 輕 重 之 地 位 智 慧 型 機 器 人 是 一 種 多 功 能 的 多 軸 全 自 動 或 半 自 動 機 械 裝 置, 可 透 過 程 式 化 動 作 執 行 各 項 生 產 活 動, 或 結 合 人 工 智 慧 與 感 測 技 術 的 應 用, 提 供 人 類 生 活 健 康 安 全 娛 樂 等 方 面 的 服 務 智 慧 型 機 器 人 產 業 尚 屬 起 步 階 段, 根 據 經 濟 部 的 資 料 顯 示, 目 前 的 智 慧 型 機 器 人 大 多 集 中 於 保 全 清 潔 娛 樂 和 互 動 上 面 的 應 用, 未 來 可 以 結 合 不 同 領 域 的 發 展 國 內 則 於 行 政 院 2005 年 產 業 科 技 策 略 會 議 中, 決 定 將 智 慧 型 機 器 人 產 業 發 展 目 標 分 為 三 個 階 段 第 Ⅰ 階 段 : 期 間 由 目 前 至 西 元 2008 年, 預 估 產 值 將 達 到 新 台 幣 300 億 元 ; 第 Ⅱ 階 段 : 期 間 由 西 元 2009 至 2013 年, 預 估 產 值 將 達 到 新 台 幣 900 億 元 以 上 ; 第 Ⅲ 階 段 : 期 間 由 西 元 2014 至 2020 年, 我 國 將 成 為 智 慧 型 機 器 人 主 要 製 造 國 [5] 以 下 分 別 就 國 內 外 相 關 研 究 1

10 舉 例 說 明 : Asimo 人 形 機 器 人 [6] 日 本 本 田 公 司 (Honda) 由 1986 年 開 始 研 發 人 形 機 器 人, 至 今 已 研 發 超 過 20 年, 不 論 機 器 人 可 模 擬 人 類 動 作 到 何 種 程 度, 但 總 需 要 時 間 才 能 讓 人 們 接 受, 本 田 當 初 在 研 發 ASIMO 時 就 希 望 可 研 發 最 平 易 近 人 的 機 器 人 為 目 標 ASIMO 代 表 Advanced Step in Innovative Mobility, 是 由 本 田 公 司 所 研 發, 全 球 唯 一 可 爬 行 樓 梯 且 可 慢 速 奔 跑 的 機 器 人 ASIMO 具 有 語 音 及 人 類 臉 部 辨 識 的 智 慧 功 能, 可 使 用 手 勢 與 人 類 進 行 溝 通, 且 ASIMO 的 手 臂 可 以 開 關 電 燈 大 門 等, 甚 至 還 可 以 為 客 人 端 茶 圖 1-1 日 本 本 田 公 司 所 發 表 之 Asimo 機 器 人 [6] 微 軟 公 司 的 Probo[7] 圖 1-2 的 Probo 主 要 的 任 務 就 是 陪 伴 醫 院 裡 的 病 童, 讓 孩 子 在 有 時 頗 痛 苦 的 醫 療 過 程 中, 得 到 心 靈 上 的 慰 藉 這 項 計 畫 將 來 預 計 會 在 比 利 時 首 都 布 魯 賽 爾 市 的 兩 家 醫 院 中 進 行 實 驗, 將 來 希 望 透 過 這 個 具 有 社 群 互 動 能 力, 強 調 語 言 人 工 智 慧 以 及 守 護 孩 童 心 靈 的 機 器 人, 能 讓 病 童 在 接 受 治 療 的 過 程 中 更 順 利, 並 能 健 康 平 安 的 出 院 2

11 圖 1-2 具 有 人 工 智 慧 的 Probo[7] 具 療 癒 功 能 的 Paro[8] 帕 羅 (Paro) 安 裝 有 感 知 影 像 視 覺 聽 覺 觸 覺 和 姿 勢 的 感 測 器, 可 以 根 據 人 們 對 它 的 觸 摸 方 式, 相 應 地 調 整 動 作, 如 圖 1-3 所 示 可 以 管 理 老 年 人 的 日 常 生 活 提 醒 他 們 按 時 吃 藥 它 們 還 可 以 用 作 通 訊 工 具, 為 用 戶 提 供 無 線 語 音 和 視 頻 連 接, 與 遠 方 的 朋 友 和 家 人 進 行 交 流 帕 羅 最 大 的 特 點, 是 可 以 對 人 的 接 觸 產 生 交 互 反 應 當 你 對 著 它 " 甜 言 蜜 語 " 或 愛 撫 一 番 時, 帕 羅 會 撲 閃 著 眼 睛, 眨 動 長 長 的 睫 毛 扭 動 身 軀 發 出 小 海 豹 般 的 叫 聲 ; 但 如 有 人 對 它 不 理 不 睬 ; 它 則 會 表 現 出 委 屈 和 憤 怒 帕 羅 還 有 一 套 固 定 的 作 息 時 間, 白 天 伴 人 玩 耍, 夜 晚 安 然 入 睡 其 外 形 動 作 和 聲 音 充 分 刺 激 人 的 感 官, 讓 人 們 有 與 之 交 流 的 感 覺, 從 而 豐 富 人 的 生 活, 成 為 老 年 人 的 忠 誠 伴 侶 圖 1-3 具 有 療 癒 功 能 的 Paro[8] 3

12 台 灣 大 學 導 覽 機 器 人 小 美 [9] 台 灣 大 學 在 黃 漢 邦 教 授 帶 領 成 功 研 發 全 自 動 智 慧 型 導 覽 機 器 人 小 美, 如 圖 1-4 所 示, 利 用 人 工 智 慧 與 控 制 技 術, 先 是 自 動 辨 識 人 臉 判 斷 觀 眾 所 在 位 置, 接 著 自 動 偵 測 路 線, 清 楚 帶 領 觀 眾 逐 一 導 覽 台 大 校 史 館 館 藏, 還 會 表 現 好 開 心 好 生 氣 等 八 種 表 情 與 情 緒 音 調 當 訪 客 注 視 某 處 時, 小 美 機 器 人 的 頭 部 也 會 跟 著 轉 動, 感 覺 就 像 和 訪 客 一 起 注 視 同 一 個 地 方, 容 易 讓 訪 客 覺 得 很 親 近 另 外 一 個 特 色 就 是 可 以 建 立 2D 和 3D 的 地 圖, 也 就 是 說, 它 今 天 可 以 放 在 台 大 校 史 館 那 他 也 可 以 放 在 北 美 館 也 可 以 放 在 國 美 館, 可 以 放 在 任 何 地 方, 讓 這 個 機 器 人 把 這 個 環 境 地 圖 整 個 建 立 起 來, 建 立 起 來 以 後, 它 就 可 以 根 據 這 地 圖 做 導 航 跟 進 一 步 的 解 說 圖 1-4 導 覽 機 器 人 小 美 [9] 中 正 大 學 室 內 多 功 能 服 務 型 機 器 人 [10] 中 正 大 學 羅 仁 權 教 授 的 研 究 團 隊 所 研 發 設 計 的 室 內 多 功 能 服 務 智 慧 型 機 器 人, 如 圖 1-5, 機 器 人 設 計 以 居 家 和 企 業 保 全 為 用 途, 以 多 重 感 測 理 論 為 基 礎, 機 械 手 臂 可 以 端 茶 水 攙 扶 老 人, 並 具 有 比 對 資 料 庫 的 五 官 擷 取 影 像 建 檔 以 辨 識 入 侵 者 除 完 善 的 保 全 功 能 外, 還 有 語 音 功 能, 可 應 用 於 保 全 勤 務, 並 可 透 過 語 音 系 統, 詳 細 解 說 企 業 概 況, 是 一 部 兼 具 保 全 居 家 照 顧 服 務 功 能 與 擔 任 企 業 親 善 大 使 的 機 器 人 4

13 圖 1-5 室 內 多 功 能 服 務 型 機 器 人 [10] 美 國 Anybots 的 QB 遠 端 臨 場 機 器 人 [11] QB 是 一 個 遠 端 臨 場 機 器 人, 如 圖 1-6, 目 的 為 讓 使 用 者 能 在 遠 端 透 過 網 際 網 路, 同 時 在 數 個 地 方 與 他 人 互 動 如 同 身 歷 其 境 的 參 與 任 何 一 個 遠 方 的 會 議, 不 僅 利 於 需 要 遠 端 工 作 的 人 使 用 也 可 以 應 用 於 一 些 緊 急 狀 況 QB 機 器 人 的 攝 影 機 是 用 於 操 作 者 可 以 了 解 機 器 人 的 位 置 以 及 他 所 面 對 的 障 礙 物 機 器 人 的 移 動 仍 然 要 依 靠 遠 端 的 使 用 者 操 作 因 此 可 另 外 加 入 電 腦 視 覺 的 分 析 例 如 利 用 影 像 辨 認 以 尋 找 遠 端 環 境 的 人 或 物 體 用 影 像 追 蹤 使 機 器 人 跟 隨 特 定 的 人, 或 是 建 立 工 作 環 境 的 地 圖 讓 遠 端 的 操 縱 更 加 便 利 圖 1-6 QB 遠 端 臨 場 機 器 人 [11] 5

14 1.2 樂 高 機 器 人 介 紹 樂 高 機 器 人 套 件 (LEGO MINDSTORMS Robotics Invention System) 目 前 最 著 名 的 機 器 人 學 習 的 案 例 樂 高 機 器 人 套 件 是 針 對 12 歲 以 上 的 小 孩 或 大 人, 對 機 器 人 有 興 趣 ( 或 者 啟 發 自 動 控 制 教 育 ) 的 教 育 玩 具 這 項 產 品 計 畫 始 於 1986, 由 丹 麥 樂 高 公 司 和 美 國 麻 省 理 工 學 院 的 媒 體 實 驗 室 (Media Lab) 進 行 的 一 項 可 程 式 積 木 (Programmable Brick) 的 合 作 案 一 般 的 樂 高 模 型 完 成 之 後 是 靜 態 模 型, 玩 家 可 以 自 由 想 像, 沈 浸 於 觀 賞 之 中 將 模 型 加 上 馬 達 等 動 力 元 件, 就 可 以 進 化 為 動 態 模 型, 有 了 動 作, 玩 家 可 以 有 更 多 的 玩 法 樂 高 Mindstorms NXT 是 樂 高 最 新 一 代 的 機 器 人 樂 高 (LEGO) 已 于 2006 年 9 月 上 旬 推 出 樂 高 公 司 和 美 國 麻 省 理 工 學 院 共 同 開 發 的 機 器 人 組 件 新 款 教 育 用 LEGO Mindstorms NXT, 如 圖 1-7 所 示 Mindstorms 是 將 配 備 微 處 理 器 的 LEGO 公 司 的 塑 料 積 木 組 裝 起 來, 通 過 個 人 電 腦 制 作 的 程 序 來 控 制 的 機 器 人 [12] 在 圖 1-7 中, 中 間 是 NXT 所 使 用 的 " 中 央 控 制 積 木 ", 週 邊 的 電 子 零 件 由 左 上 角 那 個 長 的 像 雞 腿 的 零 件 開 始, 順 時 針 依 序 是 馬 達 馬 達 馬 達 超 音 波 距 離 感 測 器 光 源 感 應 器 音 源 感 測 器 以 及 觸 碰 感 應 器 " 中 央 控 制 積 木 " 就 跟 RCX 那 一 大 塊 黃 色 的 積 木 功 能 一 樣, 程 式 設 計 師 將 寫 好 的 程 式 灌 入 至 此 積 木, 然 後 交 由 該 積 木 去 控 制 與 他 連 結 的 I/O 零 件 去 執 行 程 式, 馬 達 可 以 說 是 NXT 的 主 要 輸 出 零 件, 機 器 人 需 要 運 動 的 部 分 就 要 交 給 馬 達 去 執 行,NXT 除 了 這 個 輸 出 方 式 外, 還 可 以 藉 由 中 央 控 制 積 木 的 螢 幕 和 音 源 來 輸 出, 所 以 你 可 以 編 寫 一 首 簡 單 的 歌 交 給 NXT 播 放, 至 於 NXT 的 輸 入 部 分, 超 音 波 距 離 感 應 器 主 要 藉 由 發 射 超 音 波, 然 後 接 收 自 己 發 射 出 去 的 超 音 波, 得 到 兩 者 之 間 所 需 的 時 間 來 計 算 與 物 體 的 距 離, 光 源 感 應 器 有 兩 種 模 式, 一 種 是 自 己 發 出 光 線 然 後 測 反 射 回 來 光 線, 另 一 種 是 接 收 來 自 外 界 的 紅 外 線, 音 源 感 應 器 就 是 收 音 機 接 收 來 自 外 界 的 聲 音, 觸 碰 感 應 器 可 以 偵 測 該 感 應 器 是 被 壓 住 或 鬆 開 [12] 由 於 樂 高 機 器 人 套 件 的 彈 性 化, 擁 有 著 讓 使 用 者 自 行 開 發 設 計 組 合 成 各 6

15 式 不 同 類 型 的 樂 高 機 器 人 模 式, 也 因 此 這 樣 的 應 用 也 被 常 拿 來 做 教 育 上 的 教 學, 讓 小 朋 友 透 過 樂 高 的 組 合, 來 設 計 不 同 類 型 的 與 功 能 的 機 器 人, 全 球 各 地 甚 至 舉 辦 了 樂 高 機 器 人 相 互 競 賽, 並 吸 引 不 少 的 小 朋 友 參 與 而 這 樣 的 學 習 模 式 其 實 可 以 讓 學 生 來 學 習 控 制 流 程 的 設 計, 當 中 更 有 包 含 邏 輯 分 析 創 意 思 考 問 題 解 決 合 作 學 習... 等 概 念, 讓 各 組 的 學 生 發 揮 溝 通 思 考 邏 輯 合 作 等 不 同 方 式, 來 組 合 拼 湊 出 最 佳 化 的 機 器 人 世 界 各 地 許 多 知 名 的 研 究 機 構 也 皆 以 這 樂 高 機 器 人 的 使 用 來 發 展 各 式 的 學 習 模 式 以 及 各 種 不 同 的 計 畫 圖 1-7 樂 高 Mindstorms NXT 機 器 人 [12] 整 套 的 樂 高 NXT 配 件 中 也 附 帶 了 NXT-G 這 套 圖 像 化 控 制 軟 體,G 即 是 graphical 的 意 思 NXT-G 是 由 美 商 國 家 儀 器 公 司 的 LabVIEW 軟 體 所 支 援, 而 使 用 介 面 與 MATLAB 的 simulink 類 似, 它 將 所 有 的 程 式 包 成 一 個 一 個 的 方 塊, 使 用 者 只 需 拖 曳 方 塊 再 設 定 相 關 參 數 後 就 可 以 執 行, 對 於 樂 高 機 器 人 很 陌 生 的 人 也 可 以 很 容 易 上 手, 如 圖 1-8 但 與 文 字 程 式 相 比, 圖 像 化 界 面 的 程 式 再 用 性 較 低, 且 與 相 同 功 能 的 文 字 程 式 碼 相 比, 由 圖 像 化 介 面 所 完 成 的 程 式 會 用 掉 比 較 多 的 記 憶 體, 執 行 上 的 效 率 也 較 慢 這 也 促 使 了 許 多 高 階 樂 高 玩 家 致 力 於 開 發 可 以 讓 C 語 言 及 Java 等 高 階 程 式 語 言 可 以 直 接 控 制 NXT 的 程 式 環 境 7

16 圖 1-8 NXT-G 使 用 介 面 (a) 程 式 環 境 圖 1-8 NXT-G 使 用 介 面 (b) 程 式 範 例 8

17 1.3 研 究 背 景 與 目 的 魔 術 方 塊 是 匈 牙 利 首 都 布 達 佩 斯 的 一 位 年 輕 建 築 系 教 授 愛 爾 伯 - 魯 畢 克 的 作 品, 原 本 他 是 因 為 向 學 生 教 授 建 築 學 的 一 些 理 念 所 致 做 出 的 教 具, 沒 想 到 卻 變 成 今 日 的 魔 術 方 塊, 魔 術 方 塊 是 一 個 非 常 奇 特 的 結 構,26 個 小 立 方 塊 能 自 由 的 圍 繞 一 個 同 樣 大 小 的 中 心 塊 轉 動, 魯 畢 克 教 授 在 這 些 小 方 塊 的 表 面 上, 塗 上 了 不 同 的 顏 色, 這 樣 就 能 一 目 了 然 瞭 解 每 個 方 塊 的 轉 動 它 的 遊 戲 規 則 是 在 打 亂 之 後, 用 最 少 的 動 作 復 原 到 最 初 的 位 置,1975 年 這 套 遊 戲 申 請 了 專 利,1977 年 上 市 之 後 立 刻 吸 引 全 世 界 千 萬 人 投 入, 當 中 還 包 括 一 些 數 學 家, 因 為 它 總 共 有 約 四 千 三 百 億 的 變 化 [13-15] 到 了 近 幾 年, 市 面 上 更 推 出 了 多 階 魔 術 方 塊 例 如 5x5 與 7x7 等 等, 以 及 由 不 規 則 型 的 小 方 塊 組 合 而 成 的 魔 術 方 塊, 更 有 非 正 方 體 造 型 的 方 塊, 如 圖 1-9 所 示, 這 使 的 魔 術 方 塊 的 變 化 性 及 求 解 公 式 的 複 雜 性 又 更 上 了 一 層 樓 以 下 分 別 就 舉 例 說 明 幾 種 比 較 常 見 之 解 魔 術 方 塊 機 器 人 : 如 圖 1-10 所 示, 主 要 以 PC 為 基 礎 之 解 魔 術 方 塊 機 器 人, 其 透 過 CCD 將 六 個 面 之 魔 術 方 塊 資 訊 傳 至 PC 個 人 電 腦, 利 用 程 式 計 算 解 方 塊 步 驟, 再 透 過 伺 服 介 面 卡 控 制 機 器 手 臂 動 作 達 到 解 方 塊 之 目 的, 但 是 該 架 構 往 往 需 要 昂 貴 之 機 構 設 計 費 用 針 對 此 缺 點, 有 研 究 者 利 用 樂 高 積 木 設 計 組 合 成 所 需 之 機 器 手 臂, 如 圖 1-11 所 示, 如 此 可 以 大 大 減 少 開 發 之 成 本 與 時 間 (a) (b) 9

18 (c) (d) 圖 1-9 各 種 多 階 與 非 標 準 魔 術 方 塊 [16] 圖 1-10 以 PC 為 基 礎 之 解 魔 術 方 塊 機 器 人 [17] (a) (b) 圖 1-11 以 PC 為 基 礎 之 解 魔 術 方 塊 樂 高 機 器 人 [18.19] 10

19 Android 平 台 除 了 愈 來 愈 普 及, 憑 著 Open Source 優 勢 Android 平 台 首 先 就 是 其 開 發 性, 開 發 的 平 臺 允 許 任 何 移 動 終 端 廠 商 加 入 到 Android 聯 盟 中 來 開 放 的 平 台 也 會 帶 來 更 大 競 爭, 如 此 一 來, 消 費 者 將 可 以 用 更 低 的 價 位 購 得 心 儀 的 手 機 一 些 研 究 者 利 用 Android 平 台 智 慧 型 手 機 將 解 方 塊 程 式 寫 入 計 算 所 需 之 解 方 塊 步 驟, 再 利 用 藍 牙 通 訊 介 面 將 動 作 命 令 傳 送 至 NXT 中 央 控 制 積 木, 利 用 中 央 控 制 積 木 控 制 手 臂 動 作 達 到 解 方 塊 目 的, 如 圖 1-12 所 示 更 有 不 少 研 究 者 直 接 利 用 NXT 中 央 控 制 積 木 來 計 算 解 方 塊 之 步 驟, 如 圖 1-13 所 示, 如 此 即 可 不 需 使 用 PC 或 手 機 來 計 算 解 方 塊 動 作 但 是, 這 樣 單 純 以 NXT 中 央 控 制 積 木 來 實 現 解 魔 術 方 塊 機 器 人 時, 往 往 侷 限 於 NXT 軟 體 開 發 環 境 與 運 算 能 力, 時 常 無 法 快 速 解 題 或 需 較 多 步 驟 才 能 達 到 解 方 塊 之 目 的 圖 1-12 以 Andriod 為 基 礎 之 解 魔 術 方 塊 樂 高 機 器 人 [20] (a) (b) 圖 1-13 以 NXT 為 基 礎 之 解 魔 術 方 塊 樂 高 機 器 人 [21] 11

20 本 研 究 將 以 PC 為 基 礎 設 計 所 需 之 解 魔 術 方 塊 機 器 人, 在 機 構 設 計 部 分, 本 論 文 利 用 樂 高 積 木 設 計 組 合 所 需 之 機 器 人, 如 此 可 以 大 大 減 少 開 發 之 成 本 與 時 間 接 著, 並 透 過 CCD Web Camera 將 六 個 面 之 魔 術 方 塊 資 訊 傳 至 個 人 電 腦, 在 MATLAB 環 境 下 利 用 影 像 處 理 技 術 得 知 該 方 塊 顏 色 分 佈 之 情 狀, 再 進 一 步 計 算 解 方 塊 所 需 之 步 驟, 最 後, 在 電 腦 使 用 MATLAB 的 I/O 功 能 下, 透 過 藍 芽 傳 輸 傳 送 指 令 至 樂 高 機 器 人 本 論 文 所 提 出 之 MATLAB 遠 端 遙 控 樂 高 機 器 人 解 決 方 案, 可 以 有 立 即 執 行 程 式 設 計 無 需 額 外 的 工 具 與 在 MATLAB 環 境 下 進 行 研 發 與 除 錯 工 作 等 優 點 如 此, 所 提 出 之 架 構 除 了 十 分 適 合 解 魔 術 方 塊 機 器 人 使 用, 還 十 分 適 合 各 種 不 同 功 能 之 智 慧 型 機 器 人 使 用 除 了 MATLAB RWTH Toolbox 之 外, 可 用 來 控 制 NXT 的 高 階 程 式 環 境 還 有 NXC LabView for LEGO MINDSTORMS NXT Microsoft Robotics Developer Studio 等 其 中 也 有 由 美 商 國 家 儀 器 公 司 LabView 軟 體 所 支 援 的 NXT-G 圖 像 化 控 制 軟 體, 它 將 程 式 包 成 一 個 方 塊, 只 需 要 拖 拉 方 塊 並 且 設 定 參 數 就 可 執 行, 不 過 與 同 功 能 的 程 式 碼 相 比 是 比 較 耗 費 記 憶 體 的 12

21 第二章 機器平台介紹 2.1 整體架構 為了讓電腦讀取魔術方塊的六個面 並且讓機器人完成翻轉與旋轉魔術方塊 旋轉這二個動作 本章將對機器人平台加以探討 本章將對機器人平台加以探討 實驗環境主要利用 實驗環境主要利用 MATLAB 工具箱軟體的開發環境與 軟體的開發環境與樂高 NXT 主機及其積木零組件來完成解魔術方塊機 器人的實驗環境 其架構示意圖如圖 其架構示意圖如圖 2-1 所示 包含了機影像擷取裝置 包含了機影像擷取裝置 電腦 MATLAB 影像處理 MATLAB MATLAB 魔術方塊模擬器解題 RWTH 工具箱的控制指 工具箱 令 NXT 主機及樂高伺服馬達 伺服馬達 而積木部分則分為翻轉的手臂部分 而積木部分則分為翻轉的手臂部分 旋轉方塊 的平台部分與架設影像擷取裝置部分 透過影像擷取與影像處理軟體讀取魔術方 塊的六面色值 再使用 RWTH 工具箱對 NXT 控制盒下達馬達控制指令 以下 控制盒下達馬達控制指令 在本章中將逐步詳細介紹 在本章中將逐步詳細介紹 再將整個實驗環境的架設作一說明 圖 2-1 解魔術方塊機器人示意圖 13

22 2.2 NXT 控 制 盒 在 NXT 之 前, 樂 高 公 司 在 1999 年 發 表 了 第 一 代 智 慧 型 主 機 :RCX RCX 有 3 個 輸 入 端 與 3 個 輸 出 端, 可 以 接 上 多 種 感 應 器 與 馬 達, 組 成 一 台 簡 易 的 機 器 人 搭 配 Robolab 這 套 圖 像 化 軟 體, 透 過 紅 外 線 傳 輸 將 電 腦 上 的 程 式 下 載 到 RCX 上 並 執 行 經 過 數 年 之 後, 樂 高 公 司 在 2005 年 發 表 了 新 一 代 智 慧 型 主 機 :NXT 除 了 在 硬 體 效 能 方 面 有 大 幅 度 的 提 升 之 外, 也 提 供 了 更 多 種 的 感 應 器 選 擇 以 下 則 對 NXT 控 制 盒 做 詳 細 介 紹 [12]: (1) 處 理 器 與 記 憶 體 : 主 核 心 為 32 位 元 的 ARM7 微 處 理 器, 負 責 管 理 所 有 燒 錄 的 執 行 檔, 擁 有 256K 快 閃 記 憶 體 與 64K 內 存 RAM, 以 及 8 位 元 AVR 微 控 制 器, 負 責 管 理 I/O 的 控 制, 擁 有 4K 快 閃 記 憶 體 與 512B 內 存 RAM ARM (Advanced RISC Machine) 是 一 個 32 位 元 精 簡 指 令 集 微 處 理 器 架 構, 並 且 廣 泛 運 用 在 許 多 嵌 入 式 系 統 設 計 上, 其 特 點 就 是 耗 電 量 低, 故 普 遍 應 用 在 行 動 通 訊 領 域 AVR(Automatic Voltage Regulor) 微 控 制 器 是 1997 年 由 ATMEL 公 司 研 發 出 的 增 強 型 內 建 快 閃 的 RISC(Reduced Instruction Set Computing) 精 簡 指 令 集 8 位 元 單 晶 片, 其 具 有 高 可 靠 性, 高 速 度, 低 功 耗 的 特 性, 並 廣 泛 應 用 在 電 腦 外 部 設 備, 工 業 儀 器, 通 訊 設 備 等 領 域 圖 2-2 NXT 控 制 盒 14

23 (2) 傳 輸 方 式 與 I/O 端 子 : 在 電 腦 與 NXT 之 間 的 傳 輸, 可 透 過 USB 2.0 (PC-NXT) 與 藍 芽 (PC-NXT 或 NXT-NXT) 二 種 方 式 完 成 而 NXT 擁 有 3 個 馬 達 輸 出 端 與 4 個 感 應 器 輸 入 端, 並 使 用 6 芯 傳 輸 線 連 接 馬 達 與 感 應 器, 此 傳 輸 線 也 支 援 I2C 傳 輸 協 定, 包 括 了 一 個 用 於 將 來 使 用 的 IEC Type 4/EN 相 容 接 口 (3) 使 用 者 介 面 : 包 含 了 一 個 64x100 像 素 的 可 程 式 化 液 晶 顯 示 面 板, 與 左 右 鍵 及 橘 色 的 功 能 鍵, 以 及 8KHz 音 質 的 揚 聲 器 透 過 功 能 鍵 與 左 右 鍵 可 以 開 啟 NXT 的 使 用 介 面, 可 進 行 檔 案 的 執 行 與 刪 除, 或 是 在 指 定 輸 入 端 連 接 感 應 器, 便 可 顯 示 該 感 應 器 的 讀 值 在 使 用 介 面 中 也 可 編 輯 簡 易 的 圖 形 化 程 式 並 且 執 行, 但 最 多 只 可 編 輯 5 個 工 作 方 塊, 對 於 複 雜 的 動 作 還 是 必 須 使 用 高 階 的 程 式 軟 體 (4) 感 應 器 : NXT 支 援 的 感 應 器 約 可 分 為 2 種 : 類 比 感 應 器 與 I2C 感 應 器 類 比 感 應 器 有 觸 碰 感 應 器, 光 感 應 器, 聲 音 感 應 器 等 等, 這 類 感 應 器 將 讀 取 到 的 值 輸 入 NXT 主 機 進 行 類 比 數 位 轉 換 I2C 感 應 器 有 超 音 波 感 應 器, 紅 外 線 感 應 器, 以 及 一 些 近 年 來 開 發 的 新 型 感 應 器 I2C(Inter Integrated Circuit) 為 一 個 串 列 匯 流 排 介 面, 利 用 二 條 訊 號 控 制 線 (SCL,SDA) 在 二 個 IC 之 間 傳 送 資 料, 並 且 有 主 (Master) 從 (Slave) 機 制 其 優 點 為 佔 用 空 間 非 常 小, 可 大 幅 減 少 電 路 空 間, 並 且 確 保 資 料 不 失 真, 故 近 年 來 所 開 發 的 較 複 雜 類 型 感 應 器 皆 運 用 I2C 數 位 介 面 傳 輸, 也 有 將 以 往 的 類 比 類 型 溫 度 感 應 器 數 位 化, 藉 以 提 高 精 確 度 在 傳 送 速 率 上, 傳 統 的 類 比 感 應 器 將 讀 取 的 值 輸 入 NXT 主 機 進 行 類 比 數 位 轉 換,I2C 感 應 器 則 是 將 感 應 結 果 以 一 次 一 位 元 的 串 列 傳 送 方 式 輸 入 NXT 主 機, 所 以 在 速 率 上 是 較 類 比 感 應 器 慢 的 (5) 電 源 : 6 個 3 號 電 池 或 充 電 鋰 電 池 其 中 感 應 器 的 供 電 為 4.3V, 電 流 因 感 應 器 種 類 而 異 馬 達 的 供 電 為 9V 60mA 15

24 2.3 LEGO 伺 服 馬 達 工 業 用 伺 服 馬 達 可 以 精 準 的 控 制 馬 達 轉 動 角 度, 而 樂 高 公 司 也 在 NXT 上 推 出 了 內 建 角 度 感 應 器 的 伺 服 馬 達, 藉 以 做 到 定 位 (positioning), 並 且 使 用 了 很 多 齒 輪 來 達 到 增 大 扭 力 的 效 果, 其 構 造 如 圖 2-3 所 示, 相 較 於 上 一 代 的 RCX 馬 達, 以 體 積 變 大 及 高 成 本 換 取 了 功 能 更 強 大 的 馬 達 [12] NXT 馬 達 將 一 個 圓 分 為 360 等 份, 每 個 控 制 單 位 為 1 度, 這 對 於 一 些 嚴 格 要 求 馬 達 轉 動 角 度 的 專 題 得 以 進 行 光 學 編 碼 器 圖 2-3 樂 高 伺 服 馬 達 解 析 圖 而 此 角 度 感 應 器 為 一 個 光 學 編 碼 器, 利 用 一 組 發 光 二 極 體 或 是 其 他 光 源 來 發 光, 使 用 光 電 晶 體 來 感 測 在 發 光 二 極 體 與 光 電 晶 體 之 間 有 一 轉 盤, 通 常 是 聯 接 在 馬 達 的 轉 軸 上, 而 轉 盤 上 有 可 透 光 與 不 可 透 光 的 區 域, 當 馬 達 轉 動 時 會 帶 動 轉 盤, 一 照 一 暗 的 產 生 一 個 方 波 訊 號 此 方 波 訊 號 的 頻 率 相 對 應 於 馬 達 的 轉 動 速 度, 而 方 波 的 數 量 則 對 應 於 馬 達 轉 動 的 角 度 若 在 感 測 端 加 入 第 二 組 光 電 晶 體, 將 原 來 的 孔 距 定 義 成 360 度, 並 且 讓 二 組 光 電 晶 體 排 列 相 位 相 差 成 90 度 當 圓 盤 轉 動 時 便 可 產 生 二 個 相 位 差 90 度 的 AB 方 波, 若 A 方 波 領 先 B 方 波, 則 馬 達 正 轉 ; 反 之 則 馬 達 反 轉, 如 圖 2-4 所 示 至 於 NXT 馬 達 的 速 度 控 制 方 面, 有 別 於 一 般 的 直 流 馬 達 透 過 電 壓 大 小 來 改 變 馬 達 速 度, 而 是 採 用 PWM(Pulse width Modulation) 脈 波 寬 度 調 變 方 式 來 調 整 對 馬 達 的 供 電 時 間, 藉 以 達 到 改 變 馬 達 轉 速 一 般 來 說 PWM 的 頻 率 會 在 1KHz 以 16

25 上, 一 個 週 期 約 為 1 毫 秒, 以 50% 工 作 週 期 來 說 相 當 於 供 電 0.5 毫 秒 / 停 止 供 電 0.5 毫 秒 由 於 1KHz 的 頻 率 會 有 1000 個 週 期, 所 以 即 使 是 10% 的 工 作 週 期 馬 達 的 運 作 看 起 來 也 不 會 斷 斷 續 續 的 脈 波 A 轉 動 速 度 較 慢 時 B 脈 波 脈 波 A 轉 動 速 度 較 慢 時 B (a) 轉 動 速 度 較 快 時 轉 動 速 度 較 快 時 (b) 圖 2-4 光 學 編 碼 器 AB 相 訊 號 (a) 編 碼 器 做 正 向 運 轉 (b) 編 碼 器 做 反 向 運 轉 17

26 2.4 BricxCC 與 NXC 介 紹 在 2001 年,Dave Baum 發 表 了 NQC(Not Quite C): 給 RCX 使 用 的 類 C 語 言, 程 式 環 境 是 RCX Command Center, 後 來 改 版 成 Bricx Command Center Bricx Command Center(BricxCC) 是 一 個 整 合 型 程 式 環 境, 支 援 了 樂 高 智 慧 型 主 機 以 及 第 三 方 的 程 式 語 言 [22-23] 到 了 2006 年 NXT 發 表 後,John C. Hansen 依 照 NXT 的 硬 體 設 備 發 展 了 NXC (Not exactly C) NXC 依 照 NXT 規 格 對 應 了 C 語 言 語 法 並 完 整 支 援 所 有 NXT 的 硬 體 功 能 與 多 種 外 接 感 應 器, 可 在 Bricx command Center 中 進 行 編 譯, 更 提 供 了 許 多 方 便 的 直 接 控 制 介 面 而 NXC 與 BricxCC 具 有 以 下 優 點 : (1) 免 費 且 更 新 迅 速 : NXC 與 BricxCC 都 是 免 費 的, 在 官 方 網 站 上 也 時 常 有 測 試 檔 與 各 種 說 明 (2) 相 容 性 高 : 使 用 樂 高 標 準 韌 體, 不 需 要 安 裝 新 的 韌 體, 可 與 NXT-G 交 叉 測 試 (3) 穩 定 可 靠 : BricxCC 經 過 歷 代 版 本 的 更 新 後, 已 是 一 個 成 熟 的 程 式 環 境, 穩 定 性 已 比 NQC 大 幅 提 高 (4) 上 手 快 速 : 從 安 裝 BricxCC 撰 寫 簡 單 的 NXC 程 式, 並 且 組 裝 樂 高 積 木 到 機 器 人 動 起 來 不 會 超 過 30 分 鐘 而 且 NXC 有 許 多 特 有 語 法 來 存 取 感 應 器 與 馬 達 的 參 數 NXC 包 括 了 算 數 和 邏 輯 運 算 資 料 轉 移 控 制 流 程 條 件 指 令 以 及 它 特 有 的 程 式 指 令, 程 式 設 計 者 只 需 懂 得 C 或 C++ 程 式 語 言 就 足 以 撰 寫 程 式 在 BricxCC 介 面 中 可 以 選 擇 使 用 何 種 樂 高 智 慧 型 主 機, 以 及 與 電 腦 的 連 接 方 式 和 韌 體, 也 可 以 選 擇 使 用 別 種 程 式 環 境 例 如 NQC 與 NBC BricxCC 會 依 使 用 者 選 擇 18

27 的 程 式 種 類 編 譯 成 硬 體 語 言, 只 要 Compile 無 誤 便 會 產 生 一 個 rxe 檔, 這 是 NXT 唯 一 辨 識 的 執 行 檔 利 用 BricxCC 的 燒 錄 功 能 與 USB 傳 輸 線 或 藍 芽, 便 可 下 載 燒 錄 檔 至 NXT, 再 透 過 執 行 功 能 或 是 NXT 上 的 橘 色 功 能 鍵 便 可 執 行 並 驗 證 程 式 功 能 BricxCC 的 程 式 開 發 環 境 如 圖 2-5 所 示 圖 2-5 BricxCC 程 式 開 發 環 境 BricxCC 也 有 提 供 NXT 與 電 腦 連 線 的 即 時 控 制 功 能 Direct Control, 這 功 能 包 含 了 對 指 定 輸 出 腳 位 的 馬 達 進 行 正 反 轉 的 控 制 與 運 轉 速 度, 以 及 馬 達 的 剎 車 模 式, 指 定 輸 入 腳 位 的 感 應 器 種 類, 也 可 選 擇 感 應 器 的 存 取 模 式 如 預 設 的 RAW 值 與 布 林 值, 以 及 百 分 比 值 等 等 在 Watching the Brick 功 能 中, 則 可 以 即 時 觀 察 各 輸 入 輸 出 腳 位 的 馬 達 相 關 參 數 與 感 應 器 的 值, 也 可 以 將 這 些 讀 取 的 值 使 用 圖 表 模 式 顯 示 出 來, 如 圖 2-6 所 示 另 外 也 有 Brick Piano 可 以 讓 NXT 即 時 發 音, 可 以 在 此 編 輯 發 音 並 轉 換 成 NXC 程 式 碼 19

28 圖 2-6 Watching the Brick 的 資 料 圖 表 化 功 能 ( 光 感 應 器 ) 至 於 NXC 對 於 馬 達 的 控 制 方 式 約 可 分 為 無 控 制 模 式 速 度 控 制 模 式 同 步 模 式 角 度 控 制 模 式 與 PID 控 制 模 式 五 種 在 無 控 制 模 式 中, 顧 名 思 義 的 不 會 對 馬 達 給 予 誤 差 修 正 量, 只 是 純 粹 的 令 馬 達 轉 哪 個 方 向, 速 度 多 快 而 已 速 度 控 制 模 式 中, 當 給 定 馬 達 轉 動 速 度 參 數 後, 如 果 給 予 馬 達 一 個 外 力 負 載, 則 NXT 會 試 著 加 大 馬 達 的 控 制 量 以 維 持 給 定 的 速 度 參 數 同 步 模 式 中, 可 以 對 指 定 的 二 個 馬 達 設 定 同 步 百 分 比, 在 此 模 式 中 若 對 其 中 一 個 馬 達 強 加 負 載, 則 另 一 個 馬 達 速 度 也 會 跟 著 慢 下 來, 至 於 同 步 百 分 比 則 指 二 個 馬 達 的 同 步 比 率, 舉 例 來 說 設 0 的 話 二 個 馬 達 會 以 同 樣 速 度 轉 同 一 方 向, 設 20 的 話 則 其 中 一 個 馬 達 速 度 會 比 另 一 個 慢 一 些,100 的 話 則 是 二 個 馬 達 以 同 樣 速 度 轉 不 同 方 向 最 後 PID 模 式 中, 由 於 PID 控 制 器 是 內 建 於 NXT 中 的, 所 以 使 用 者 只 需 要 設 定 設 定 P 值 I 值 D 值 就 可 以 令 馬 達 旋 轉 指 定 的 角 度, 而 NXT 預 設 的 PID 值 分 別 為 , 若 觀 察 不 同 的 PID 值 例 如 只 給 P 值 其 他 為 0, 則 誤 差 無 法 抵 銷 以 至 馬 達 不 能 剛 好 轉 到 指 定 角 度 ; 若 P 值 為 0 只 給 ID 值, 則 轉 動 的 誤 差 會 變 大 ; 若 只 給 PI 值 而 D 值 為 0, 則 馬 達 會 轉 過 頭 再 轉 回 來 修 正 20

29 2.5 MATLAB 影 像 擷 取 與 處 理 工 具 箱 MATLAB 與 Simulink 影 像 處 理 工 具 提 供 工 程 師, 科 學 家 及 研 究 人 員 一 個 直 覺 式, 彈 性 化 的 環 境 來 解 決 複 雜 的 影 像 處 理 問 題 並 廣 泛 運 用 於 航 太 及 國 防 遠 距 感 應 技 術 生 物 科 技 醫 學 影 像 科 學 影 像 及 材 料 科 學 等 等 且 適 用 於 各 種 動 靜 態 影 像 處 理, 搭 配 影 像 擷 取 卡 網 路 攝 影 機 等 裝 置 擷 取 影 像, 進 行 影 像 增 強 轉 換 計 算 濾 波 器 設 計 等 影 像 分 析 及 演 算 法 發 展 之 應 用, 提 供 在 處 理 複 雜 的 影 像 問 題 時, 做 更 有 效 率 及 最 適 當 的 影 像 處 理 論 文 中 主 要 使 用 的 2 個 工 具 箱 模 組 [24]: 影 像 擷 取 工 具 箱 影 像 擷 取 工 具 箱 可 直 接 在 MATLAB 或 Simulink 的 環 境 下, 將 與 電 腦 相 容 的 影 像 硬 體 裝 置 所 擷 取 的 影 像 與 動 態 影 片 匯 入 MATLAB 裡 做 分 析 處 理, 並 支 援 許 多 硬 體 供 應 商 的 產 品 影 像 處 理 工 具 箱 影 像 處 理 工 具 箱 提 供 一 個 完 整 的 開 發 環 境 進 行 影 像 分 析 處 理 視 覺 化 及 演 算 法 開 發 功 能 可 以 恢 復 雜 訊 或 著 降 低 影 像 增 強 影 像 粹 取 功 能 分 析 陰 影 結 構, 紀 錄 2 個 影 像, 並 且 管 理 色 彩 裝 置 檔 案 搭 配 影 像 擷 取 工 具 箱 並 因 應 LEGO 積 木 所 架 設 的 機 器 人 平 台, 適 合 本 實 驗 機 構 的 影 像 擷 取 裝 置 有 CCD 與 網 路 攝 影 機, 兩 者 的 相 異 點 為 : CCD 需 要 額 外 電 源 供 應 網 路 攝 影 機 一 般 視 訊 直 接 用 USB 接 到 電 腦 後, 灌 入 驅 動 程 式 即 可 使 用, 可 是 CCD 需 要 利 用 影 像 擷 取 器 連 接 至 電 腦 CCD 所 擷 取 的 影 像 畫 質 解 析 度 較 高, 但 是 相 對 的 處 理 資 料 量 也 較 大 而 整 體 實 驗 架 構 中, 影 像 擷 取 部 分 主 要 用 以 抓 取 並 辨 識 魔 術 方 塊 一 個 面 上 的 九 宮 格 色 塊, 故 在 此 選 擇 了 架 設 容 易 但 解 析 度 較 低 的 網 路 攝 影 機 在 使 用 網 路 攝 影 機 的 實 作 情 況 則 可 以 利 用 影 像 擷 取 工 具 箱 裡 面 介 紹 的 方 法 以 及 function 實 現, 21

30 其 步 驟 如 下 : 步 驟 一 : 安 裝 與 設 定 影 像 擷 取 裝 置 安 裝 影 像 擷 取 設 備 的 驅 動 程 式 並 且 連 接 至 電 腦, 再 使 用 相 關 應 用 軟 體 預 覽 影 像 畫 面 若 使 用 CCD 則 需 多 安 裝 影 像 擷 取 卡 的 驅 動 程 式 步 驟 二 : 檢 視 影 像 擷 取 工 具 箱 唯 一 辨 識 的 影 像 擷 取 裝 置 檢 索 資 訊 要 判 斷 MATLAB 是 否 和 網 路 攝 影 機 連 接 上, 要 看 DeviceIDs 這 個 參 數 是 否 有 正 確 值, 再 進 行 下 一 個 步 驟, 一 般 正 確 的 數 值 會 是 1, 若 MATLAB 沒 有 讀 到 網 路 攝 影 機, 則 該 值 是 0, 在 此 情 形 下 須 透 過 imaqreset 指 令 清 除 所 有 影 像 擷 取 物 件, 訊 息 如 下 : info = AdaptorDllName: [1x67 char] AdaptorDllVersion: '3.3 (R2009a)' AdaptorName: 'winvideo' DeviceIDs: {[1]} DeviceInfo: [1x1 struct] 若 網 路 攝 影 機 與 MATLAB 連 接 妥 當, 則 可 觀 看 影 像 擷 取 裝 置 相 關 資 訊, 其 中 DefaultFormat 為 擷 取 圖 像 時 的 解 析 度,DeviceName 為 網 路 攝 影 機 名 稱, 訊 息 如 下 : dev_info = DefaultFormat: 'RGB24_640x480' DeviceFileSupported: 0 DeviceName: '09-ASE200' DeviceID: 1 ObjectConstructor: 'videoinput('winvideo', 1)' SupportedFormats: {1x13 cell} 22

31 步 驟 三 : 創 驗 視 訊 輸 入 物 件 在 此 步 驟 為 創 建 MATLAB 與 影 像 擷 取 裝 置 的 連 接 通 道, 可 運 用 videoinput 指 令 並 且 再 參 照 步 驟 二 獲 得 的 資 訊 進 行 相 關 設 定 訊 息 如 下 : vid = videoinput('winvideo',1,'rgb24_640x480') Summary of Video Input Object Using '09-ASE200'. Acquisition Source(s): input1 is available. Acquisition Parameters: 'input1' is the current selected source. 10 frames per trigger using the selected source. RGB24_640x480' video data to be logged upon START. 步 驟 四 : 預 覽 視 訊 由 於 是 使 用 USB 連 接 到 電 腦, 所 以 在 擷 取 影 像 時 沒 有 太 大 的 困 難, 可 由 preview(vid) 預 覽, 以 下 是 Demo 影 像 : 圖 2-7 影 像 擷 取 圖 樣 步 驟 五 : 設 定 影 像 擷 取 物 件 屬 性 當 創 建 完 視 訊 輸 入 物 件 之 後, 可 用 getselectedsource 指 令 檢 視 其 相 關 屬 性, 並 可 利 用 set function 更 改 相 關 參 數, 例 如 影 像 擷 取 禎 數 等 等 步 驟 六 : 擷 取 影 像 設 定 完 視 訊 輸 入 之 後 便 可 以 透 過 getdata 存 取 影 像 資 料 在 MATLAB 之 下, 也 23

32 可 以 使 用 imwrite 將 影 像 存 成 硬 碟 檔 案 在 取 得 影 像 資 訊 之 後 便 可 利 用 影 像 處 理 工 具 箱 進 行 影 像 處 理, 在 MATLAB 中 會 將 影 像 存 取 成 依 格 式 而 具 有 不 同 維 度 的 矩 陣, 舉 例 來 說 圖 2-6 是 一 個 640x480 像 素 的 RGB 影 像, 並 且 每 一 點 像 素 都 有 RGB 三 個 值, 則 存 取 成 一 個 三 維 640x480 矩 陣 之 後 的 一 般 處 理 方 式 有 轉 換 圖 像 的 資 料 類 型 進 行 數 學 運 算, 或 是 影 像 類 型 方 便 處 理, 可 參 照 表 2-2 處 理 的 方 式 有 對 於 灰 階 像 素 對 比 不 明 顯 的 圖 片 進 行 直 方 圖 等 化 (histogram equalization) 處 理 以 增 強 明 暗 度, 灰 階 影 像 的 不 同 閥 值 二 元 化 處 理, 使 用 濾 波 函 數 針 對 影 像 邊 緣 的 銳 利 化 或 是 去 除 影 像 雜 訊 以 及 去 除 模 糊 來 復 原 影 像, 利 用 膨 脹 與 侵 蝕 來 處 理 影 像 中 的 形 狀, 區 域 的 填 充 與 連 通 以 及 骨 架 化 處 理 等 等 [25] 函 數 用 途 格 式 ind2gray 索 引 轉 灰 階 y= ind2gray(x,map) gray2ind 灰 階 轉 索 引 [y,map]= gray2ind(x) rgb2gray RGB 轉 灰 階 y= rgb2gray(x) gray2rgb 灰 階 轉 RGB y= gray2rgb(x) rgb2ind RGB 轉 索 引 [y,map]= rgb2ind (x) ind2rgb 索 引 轉 RGB y= ind2rgb (x,map) 表 2-1 MATLAB 影 像 轉 換 圖 2-8 為 簡 易 的 樣 本 處 理, 將 原 始 的 RGB 彩 色 圖 經 過 灰 階 轉 換 並 且 經 過 直 方 圖 等 化 處 理, 再 利 用 Otsu 演 算 法 取 得 的 最 佳 閥 值 二 元 化, 之 後 再 經 過 3x3 元 素 全 為 1 的 矩 陣 侵 蝕 2 次 24

33 (a) (b) (c) (d) 圖 2-8 影 像 處 理 樣 本 (a) 原 始 灰 階 影 像 (b)histeq 處 理 後 的 灰 階 影 像 (c)otsu 最 佳 閥 值 二 元 化 (d) 以 ones(3,3) 二 次 侵 蝕 25

34 2.6 RWTH Toolbox 介 紹 RWTH Mindstorm NXT Toolbox 為 德 國 亞 琛 大 學 電 機 工 程 學 系 2007 年 發 表 的 以 MATLAB 為 基 礎 的 LEGO 機 器 人 程 式 開 發 環 境, 可 以 利 用 MATLAB function 與 機 器 人 直 接 性 的 互 動, 並 且 支 援 藍 芽 遠 端 操 控 NXT 智 慧 型 主 機, 如 圖 2-9 所 示 工 具 箱 設 計 概 念 最 大 的 優 點 就 是 可 以 將 機 器 人 應 用 與 MATLAB 的 複 雜 數 學 運 算 結 合 在 一 起, 提 供 了 機 器 人 更 多 人 工 智 慧 與 其 他 運 用 的 無 限 可 能 從 2007 年 到 2008 年 該 學 系 已 經 成 功 運 用 RWTH Mindstorm NXT Toolbox 完 成 了 200 個 機 器 人 專 題 圖 2-9 PC 與 NXT 連 線 圖 [12] 另 外 也 有 搭 配 Real-Time Workshop 和 Real-Time Workshop Embedded Coder 使 用 的 simulink 模 擬 工 具, 以 下 則 對 此 simulink 模 擬 工 具 及 其 套 件 軟 體 作 一 介 紹 : (1)Cygwin 由 於 Linux 嵌 入 式 系 統 為 現 在 最 普 遍 使 用 的, 如 果 要 使 用 simulink 來 進 行 NXT 的 實 作 與 模 擬 則 必 須 具 備 Linux 的 作 業 環 境 而 Cygwin 便 是 一 個 Windows 系 統 下 的 虛 擬 Linux 環 境, 包 含 了 類 似 Linux 的 API 仿 真 層 以 及 其 他 相 關 的 Linux 26

35 作 業 工 具, 並 且 提 供 GNUARM 的 相 容 環 境 主 程 式 可 在 官 方 網 站 下 載 : 在 安 裝 過 程 中 需 點 選 Devel 底 下 的 Make 執 行 檔 (2)GNUARM 這 是 一 個 在 Linux 作 業 系 統 下 的 toolchain, 由 於 無 法 直 接 在 Windows 底 下 執 行, 所 以 必 須 將 軟 體 安 裝 在 Cygwin 底 下 並 搭 配 使 用 主 程 式 可 在 官 方 網 站 下 載 : (3)NeXTTool NeXTTool 使 用 了 LEGO Mindstorms NXT 的 驅 動 來 傳 輸 電 腦 與 NXT 的 資 料, 可 以 進 行 燒 錄, 檢 視 NXT 的 資 訊 如 感 應 器 讀 值 儲 存 在 內 的 檔 案 或 是 下 載 新 的 韌 體 等 等 工 具 軟 體 可 在 下 載, 並 且 將 資 料 夾 放 置 在 Cygwin 下 (4)NXT standard firmware Simulink 的 模 擬 功 能 如 果 要 連 線 NXT 下 載 燒 錄 檔 則 必 須 更 新 版 本 較 高 的 韌 體 (1.06 或 更 高 ) 韌 體 可 在 下 載, 再 將 檔 案 存 放 至 NeXTTool 目 錄 下, 並 且 使 用 cmd 命 令 提 示 字 元 鍵 入 關 鍵 字 nexttool /com=usb firmware=lms_arm_nbcnxc_107.rfw 更 新 韌 體 (5)Embedded Coder Robot NXT 以 NXT 的 ARM 系 統 為 基 礎 而 設 計 出 來 的 Simulink 程 式, 可 以 拉 圖 或 是 設 計 控 制 器 模 組, 而 模 組 方 塊 的 架 構 與 各 元 素 的 定 義 為 定 點 與 浮 點 設 計 工 具 可 在 MATLAB 官 方 網 站 下 載, 資 料 夾 必 須 放 置 在 MATLAB 的 安 裝 路 徑 最 頂 端 (6)nxtOSEK nxtosek 是 NXT 程 序 化 控 制 器 的 即 時 運 作 系 統 (RTOS,Real-Time Operating Systems), 包 含 了 lejos NXJ 以 及 TOPPERS OSEK RTOS 的 I/O 驅 動, 並 且 使 NXT 智 慧 型 可 運 行 ANSI C/C++ 程 序 程 式 可 在 下 載, 將 資 料 夾 存 放 至 第 五 個 介 紹 的 軟 體 ecrobotnxt 下 的 environment 裡 27

36 安 裝 完 以 上 六 個 軟 體 後 便 可 執 行 位 於 第 五 個 介 紹 的 ecrobotnxt 資 料 夾 下 的 ecrobotnxtsetup.m 以 完 成 最 後 的 程 序, 其 中 需 要 注 意 所 有 的 資 料 夾 路 徑 中 不 可 存 在 有 空 格 或 是 參 雜 全 形 半 形 字 體 的 資 料 夾, 否 則 m-file 會 抓 取 不 到 路 徑 之 後 便 可 在 simulink 找 到 新 增 的 模 組 工 具 箱 ECRobot NXT Blockset, 其 模 組 方 塊 如 圖 2-10 所 示 : 圖 2-10 ECRobot NXT 模 組 方 塊 其 中 ExpFcnCalls scheduler 是 控 制 Function-Call Subsystems 的 執 行 時 間, 可 以 設 定 多 個 Function-Call Subsystems 並 給 予 特 定 的 時 間 參 數, 並 且 用 Subsystems 方 塊 涵 蓋 起 來, 在 Function-Call Subsystems 裡 面 可 以 給 予 一 些 特 定 功 能 排 程, 例 如 令 馬 達 跑 弦 波 訊 號, 如 圖 2-11 所 示, 分 別 給 予 三 個 Function-Call 不 同 的 時 間 參 數 100ms 500ms 1000ms 28

37 (a) (b) (c) (d) 圖 2-11 (a) 整 體 架 構 方 塊 (b)scope 數 據 圖, 橫 軸 為 時 間, 縱 軸 為 徑 度 (c)subsystems 內 的 三 個 Function-Call (d) Function-Call 內 的 模 組 方 塊 29

38 第三章 解魔術方塊機器人設計 影像處理與結果 3-1 在本節中 將依照第二章介紹的影像擷取工具箱與影像處理工具箱 擷取魔 術方塊的六個面 並處理分析六個面的色值 其中如圖 3-1 所示 先以網路攝影 機擷取好魔術方塊的六個面 並寫入硬碟成 bmp 檔 由於每個面的九個小方塊 位於正中間的小方塊是無論如何轉動方塊都不會移動位置的 這是因為它是軸心 方塊 同時也是六面顏色的判斷 圖 3-1 (a) (b) (b) (d) (e) (f) 魔術方塊六面影像 (a)白色面 (b)綠色面 (c)黃色面 (d)藍色面 (e)橘色 面 (f)紅色面 30

39 擷 取 完 影 像 後 便 可 以 進 行 影 像 處 理, 首 先 依 照 表 2-1 的 轉 換 指 令 將 原 始 的 彩 色 圖 案 轉 換 成 灰 階 圖 案, 如 圖 3-2 所 示 (a) (b) (b) (d) (e) (f) 圖 3-2 由 圖 3-1 轉 換 的 灰 階 圖 案 (a) 白 色 面 (b) 綠 色 面 (c) 黃 色 面 (d) 藍 色 面 (e) 橘 色 面 (f) 紅 色 面 之 後 再 選 擇 適 當 的 閥 值 把 灰 階 圖 案 轉 換 成 黑 白 的 二 元 化 圖 案, 如 圖 3-3 所 示, 並 經 過 相 關 的 處 理 將 方 塊 周 圍 以 外 的 白 色 區 域 去 除, 以 取 得 影 像 中 最 感 興 趣 的 地 方, 在 此 便 是 指 魔 術 方 塊 的 邊 框 31

40 (a) (b) (c) (d) (e) (f) 圖 3-3 由 圖 3-2 轉 換 的 二 元 化 影 像 (a) 白 色 面 (b) 綠 色 面 (c) 黃 色 面 (d) 藍 色 面 (e) 橘 色 面 (f) 紅 色 面 取 得 了 最 感 興 趣 的 部 分 後, 接 下 來 則 是 取 得 魔 術 方 塊 的 邊 框 位 置, 在 2-5 的 影 像 處 理 介 紹 中 提 到,MATLAB 的 影 像 處 理 是 將 原 始 影 像 轉 換 成 相 對 應 大 小 的 矩 陣, 因 影 像 的 RGB 灰 階 格 式 的 不 同 而 具 有 不 同 的 維 度, 並 且 每 一 點 的 像 素 會 因 應 顏 色 的 不 同 而 有 不 同 的 值, 例 如 RGB 影 像 的 三 個 值 皆 為 0 到 255, 灰 階 影 像 也 是 0 到 255 的 值, 二 元 化 影 像 則 是 0( 黑 ) 和 1( 白 ), 而 影 像 的 像 素 座 標 分 佈 皆 是 第 四 象 限 在 影 像 處 理 妥 善 的 情 形 下, 可 以 從 二 元 化 影 像 尋 找 出 白 色 區 32

41 域 最 小 的 x 軸 座 標 y 軸 座 標 以 及 最 大 的 x 軸 座 標 y 軸 座 標, 這 二 點 約 等 於 是 影 像 中 魔 術 方 塊 的 左 上 點 與 右 下 點 在 取 得 了 魔 術 方 塊 的 對 角 二 個 點 後, 便 可 以 透 過 最 大 與 最 小 軸 座 標 計 算 出 魔 術 方 塊 一 個 邊 的 長 度, 由 於 實 驗 中 的 方 塊 是 標 準 魔 術 方 塊, 所 以 每 一 邊 的 長 度 以 及 每 一 面 的 九 個 小 方 塊 邊 長 都 是 固 定 的, 故 取 得 了 邊 長 後 再 除 以 三 就 是 小 方 塊 的 邊 長 得 到 約 略 的 九 個 小 方 塊 的 涵 蓋 區 域 後 便 可 以 分 辨 它 們 的 顏 色, 通 常 一 個 小 面 顏 色 的 RGB 值 並 不 是 均 勻 分 佈 的, 會 因 為 環 境 光 的 影 響 而 改 變 色 值, 所 以 在 此 對 每 一 個 小 方 塊 取 9 個 等 距 離 的 點, 透 過 計 算 這 9 個 點 的 像 素 值 的 平 均 來 判 斷 這 一 小 面 是 屬 於 何 種 顏 色 在 判 斷 顏 色 之 前 必 須 要 有 魔 術 方 塊 的 六 個 顏 色 RGB 值, 在 此 先 做 了 六 個 顏 色 的 取 樣 並 四 捨 五 入, 可 參 考 表 3-1: 顏 色 R 值 G 值 B 值 紅 橙 黃 綠 藍 白 表 3-1 魔 術 方 塊 6 色 取 樣 依 照 表 3-1 的 取 樣 結 果 設 定 好 適 當 的 RGB 判 斷 區 間, 來 針 對 每 一 面 的 九 個 顏 色 進 行 判 斷, 在 此 以 白 色 面 即 圖 3-1(a) 來 作 一 判 斷, 從 以 上 說 明 取 得 白 色 面 的 九 格 像 素 平 均 值, 如 表 3-2 所 示, 其 中 白 色 面 方 塊 因 為 印 有 商 標 所 以 會 有 較 大 的 偏 差, 可 以 加 大 中 心 方 塊 的 判 斷 區 間, 或 著 經 過 其 他 5 面 的 中 心 方 塊 色 彩 判 斷 將 印 有 文 字 的 白 色 面 歸 類 為 白 色 33

42 方 塊 位 置 R 值 G 值 B 值 左 上 中 上 右 上 左 中 正 中 心 右 中 左 下 中 下 右 下 表 3-2 白 色 面 九 格 方 塊 像 素 值 透 過 程 式 的 判 斷 式 將 白 色 面 的 色 彩 進 行 歸 類, 黃 色 歸 類 為 1 綠 色 歸 類 為 2 紅 色 歸 類 為 3 橙 色 歸 類 為 4 藍 色 歸 類 為 5 白 色 歸 類 為 6, 用 3x3 矩 陣 顯 示 則 可 得 到 2 6 5, 而 其 他 的 色 面 分 別 為 : 紅 色 面 橙 色 面 黃 色 面 綠 色 面 藍 色 面 若 將 得 到 的 6 面 值 畫 成 一 個 展 開 圖 可 以 得 到 一 個 較 明 顯 的 色 彩 分 佈, 由 於 軸 心 方 塊 是 固 定 不 動 的, 同 時 也 是 各 色 面 的 原 始 顏 色 根 據, 若 以 白 色 面 來 觀 看 其 他 4 個 鄰 面 的 顏 色, 則 一 定 固 定 為 紅 綠 橙 藍 依 順 時 鐘 排 列, 而 另 一 面 則 一 定 是 黃 色, 如 圖 3-4 所 示 : 34

43 圖 3-4 各 色 面 展 開 圖 35

44 3.2 魔 術 方 塊 解 題 與 結 果 在 取 得 6 面 的 顏 色 後 就 可 以 進 行 解 題, 解 題 的 方 式 可 以 透 過 魔 術 方 塊 的 特 有 公 式 或 是 用 程 式 模 擬 器 求 解 在 特 有 公 式 的 部 分, 有 分 為 基 本 解 與 快 速 解, 許 多 人 會 認 為 魔 術 方 塊 是 一 個 面 一 個 面 慢 慢 解 的, 但 實 際 上 魔 術 方 塊 的 解 法 是 一 層 一 層 解 的, 基 本 的 解 法 是 先 轉 好 第 一 層, 再 轉 好 第 二 層, 最 後 再 轉 好 第 三 層, 這 個 基 本 的 轉 法 稱 為 LBL, 也 就 是 Layer By Layer 此 解 法 的 出 現 是 由 魔 術 方 塊 推 出 的 30 年 來, 許 多 的 玩 家 不 斷 的 討 論 與 經 驗 累 積 整 理 出 來 的, 並 且 普 遍 流 傳 在 坊 間 之 中, 對 於 熟 記 解 題 公 式 的 人 來 說 多 半 可 以 在 1 分 鐘 左 右 解 完 方 塊 至 於 要 能 夠 在 30 秒 甚 至 是 20 秒 內 解 完 魔 術 方 塊, 其 目 的 已 不 是 單 純 的 解 題 而 是 講 求 時 間, 盡 可 能 的 減 少 公 式 以 增 快 解 題 速 度, 這 類 的 解 法 稱 為 速 解 魔 方 至 於 速 解 公 式 的 始 祖, 美 國 賓 漢 頓 大 學 教 授 弗 雷 德 里 奇 (Jessica Fridrich)[13-15], 她 設 計 了 70 幾 個 公 式 並 且 可 以 17 秒 解 完 方 塊, 而 現 今 的 許 多 速 解 公 式 大 部 分 都 是 改 編 她 的 公 式 在 此 則 對 LBL 基 礎 解 法 作 一 詳 細 介 紹, 大 致 上 的 解 法 為 先 轉 好 第 一 層 的 十 字 形, 並 且 邊 塊 的 顏 色 必 須 與 鄰 面, 相 同 如 圖 3-5(a), 然 後 再 轉 正 4 個 角 塊, 顏 色 也 必 須 與 3 個 鄰 面 相 同, 如 圖 3-5(b), 如 此 第 一 層 就 轉 完 了 接 著 將 第 二 層 的 邊 塊 互 換 使 2 個 鄰 面 顏 色 相 符 合, 如 圖 3-5(c) 最 後 第 三 層 也 是 先 轉 好 該 色 面 的 十 字 形, 不 過 與 第 一 層 不 同 的 是 十 字 形 的 邊 塊 不 用 與 鄰 面 符 合, 如 圖 3-5(d), 之 後 再 針 對 4 個 角 塊 進 行 互 換 與 翻 面 至 3 個 鄰 面 相 符, 如 圖 3-5(e) 3-5(f), 最 後 再 對 4 個 邊 塊 互 換 至 與 鄰 面 相 符 合, 如 圖 3-5(g), 如 此 便 可 解 完 方 塊, 其 詳 細 流 程 如 以 下 所 示 : 圖 3-5 (a) 步 驟 一 圖 3-5 (b) 步 驟 二 36

45 圖 3-5 (c) 步 驟 三 圖 3-5 (d) 步 驟 四 圖 3-5 (e) 步 驟 五 圖 3-5 (f) 步 驟 六 圖 3-5 (g) 步 驟 七 圖 3-5 LBL 基 本 解 法 流 程 圖 [26] 魔 術 方 塊 的 解 法 除 了 記 公 式 之 外 也 可 以 利 用 魔 術 方 塊 解 題 器, 隨 著 電 腦 資 訊 的 發 展, 已 有 許 多 數 學 家 將 推 算 出 的 演 算 法 程 式 化, 實 現 在 C 語 言 或 是 Java, 以 及 MATLAB 等 程 式 環 境, 除 了 兼 具 快 速 解 題 之 外 還 附 帶 模 擬 的 魔 術 方 塊 影 像 可 以 觀 察 解 題 過 程 在 論 文 中 則 是 使 用 程 式 模 擬 器 求 解, 而 解 題 器 是 由 Alexander Mueller 所 設 計 的, 這 是 一 個 寫 在 MATLAB 底 下 的 m-file, 可 以 在 MATLAB 網 頁 上 下 載 : 開 啟 後 如 圖 3-6 所 示 : 37

46 圖 3-6 解 題 器 模 擬 圖 在 視 窗 中 可 以 翻 轉 魔 術 方 塊 的 各 個 面, 也 可 以 拖 曳 方 塊 觀 察 各 個 面 的 色 彩 分 佈, 或 是 隨 機 產 生 一 個 轉 亂 的 方 塊, 然 後 進 行 自 動 求 解 與 手 動 求 解 在 此 將 魔 術 方 塊 的 6 個 面 色 值 代 入 解 題 器 中, 如 圖 3-7 所 示 : (a) (b) (c) (d) 38

47 (e) 圖 3-7 (a) 黃 紅 綠 色 面 (b) 黃 藍 紅 色 面 (c) 黃 橙 藍 色 面 (d) 黃 綠 橙 色 面 (e) 紅 綠 白 色 面 按 下 解 題 鍵 後 便 會 產 生 一 連 串 的 解 題 動 作, 例 如 某 色 面 向 右 轉 90 度 或 是 向 左 轉 90 度 以 及 旋 轉 180 度, 以 目 前 的 方 塊 來 說, 會 產 生 以 下 的 動 作 : 綠 色 面 右 轉 90 度 > 黃 色 面 左 轉 90 度 > 橙 色 面 左 轉 90 度 > 綠 色 面 旋 轉 180 度 > 紅 色 面 右 轉 90 度 > 橙 色 面 左 轉 90 度 > 黃 色 面 左 轉 90 度 > 藍 色 面 旋 轉 180 度 > 白 色 面 右 轉 90 度 > 黃 色 面 旋 轉 180 度 > 紅 色 面 左 轉 90 度 > 綠 色 面 右 轉 90 度 > 白 色 面 右 轉 90 度 > 藍 色 面 左 轉 90 度 > 紅 色 面 左 轉 90 度 > 解 題 完 成 再 將 上 述 動 作 轉 換 成 馬 達 控 制 指 令 後, 可 藉 由 PC 端 藍 芽 無 線 模 組 將 命 令 傳 至 NXT 控 制 盒 控 制 馬 達 動 作, 以 達 到 實 際 解 題 的 目 的 而 圖 3-10(a)~3-10(s) 為 解 題 器 的 解 題 過 程 : (a) (b) 39

48 (c) (d) (e) (f) (g) (h) (i) (j) 40

49 (k) (l) (m) (n) (s) 圖 3-8 解 題 器 解 題 過 程 41

50 由於機台設計的限制 機器人只能做方塊翻面的推動作與原地旋轉換面的轉 動作 和手臂夾住方塊旋轉方塊底面 和手臂夾住方塊旋轉方塊底面 為了配合解題器所產生的動作 為了配合解題器所產生的動作 如某色面 旋轉多少度 則必須將該色面移至底面以進行夾住旋轉該色面的第一層 則必須將該色面移至底面以進行夾住旋轉該色面的第一層 則必須將該色面移至底面以進行夾住旋轉該色面的第一層 則機器 人的實際解題動作必須設計過 以符合解題器解題過程的方塊變化 以下則針對 人的實際解題動作必須設計過 以符合解題器解題過程的方塊變化 機器人動作以及方塊變化做一探討 機器人動作以及方塊變化做一探討 圖 3-9 圖 方塊六面位置定義 機器人的翻轉方塊與旋轉方塊 機器人動作 機器人的動作共有 方塊平台正轉 90 度 正 反 轉 180 度 反轉 90 度 機器手臂翻轉方塊一次 機器手臂翻轉方塊一次 二次 三次 手臂夾住方塊上二層正轉 手臂夾住方塊上二層正轉 90 度 正 反 轉 180 度 反轉 反轉 90 度 根據目標轉動色面的位置來搭配以上的動作 根據目標轉動色面的位置來搭配以上的動作 42

51 例 如 目 標 色 面 在 方 塊 的 頂 面, 則 手 臂 翻 轉 二 次 使 該 色 面 移 至 方 塊 的 底 面, 再 進 行 手 臂 夾 住 旋 轉 的 動 作 ; 或 是 目 標 色 面 在 左 面, 則 需 方 塊 平 台 反 轉 90 度, 之 後 手 臂 翻 轉 方 塊 一 次, 接 著 手 臂 夾 住 方 塊 旋 轉 方 塊 色 面 變 化 : 對 於 一 個 標 準 的 魔 術 方 塊 來 說, 由 於 內 部 軸 心 的 設 計 使 的 方 塊 每 一 面 的 中 心 小 方 塊 無 論 方 塊 如 何 轉 亂 都 不 會 轉 動 到 它, 故 此 小 方 塊 被 用 來 判 別 魔 術 方 塊 的 色 面, 同 時, 這 小 方 塊 的 另 一 面 也 會 被 固 定, 例 如 白 色 面 的 對 面 必 定 是 黃 色, 綠 色 的 對 面 必 定 是 藍 色, 紅 色 面 的 對 面 必 定 是 橙 色, 如 此 只 要 知 道 三 個 並 非 互 為 相 對 面 的 色 面, 就 可 以 知 道 方 塊 的 六 個 色 面 位 置 若 給 予 色 面 數 字 編 號 來 表 示 : 黃 色 為 1 綠 色 為 2 紅 色 為 3 橙 色 為 4 藍 色 為 5 白 色 為 6, 則 每 個 相 對 面 的 編 號 相 加 之 和 恰 好 為 7, 綜 合 以 上 各 點 可 以 方 便 於 用 數 字 來 表 示 方 塊 目 前 的 狀 態 現 在 取 三 個 互 不 為 相 對 面 的 色 面 之 編 號 放 入 1x3 的 陣 列 之 中, 在 此 取 黃 色 綠 色 紅 色 : 其 中, 元 素 1 為 方 塊 的 底 面, 元 素 2 為 方 塊 的 前 面, 元 素 3 為 方 塊 的 右 面 配 合 機 器 人 的 動 作 來 觀 看 陣 列 的 變 化, 如 平 台 旋 轉 和 手 臂 翻 轉, 可 得 到 以 下 規 律, 其 中 R 是 指 平 台 正 轉 90 度,L 是 指 平 台 反 轉 90 度,2R(2L) 是 指 平 台 旋 轉 180 度 : 平 台 正 轉 90 度 :

52 原 地 旋 轉 並 不 會 改 變 方 塊 頂 面 和 底 面 的 顏 色, 所 以 元 素 1 的 內 容 不 變 前 面 的 顏 色 會 被 原 本 右 面 的 相 對 面 取 代, 也 就 是 7 column 3 右 面 的 顏 色 會 被 原 本 的 前 面 取 代 則 結 論 可 知 原 本 的 column 3 被 替 換 成 4, 然 後 column 2 與 column 3 互 換, 如 下 所 示 : 平 台 反 轉 90 度 : 元 素 1 的 內 容 不 變 前 面 的 顏 色 會 被 原 本 的 右 面 取 代 右 面 的 顏 色 會 被 原 本 前 面 的 相 對 面 取 代, 也 就 是 7 column 2 則 結 論 可 知 原 本 的 column 2 被 替 換 成 5, 然 後 column 2 與 column 3 互 換, 如 下 所 示 : 手 臂 翻 轉 一 次 : 底 面 被 原 本 的 前 面 之 相 對 面 取 代, 也 就 是 7 column 2 前 面 被 原 本 的 底 面 取 代 翻 滾 的 動 作 並 不 會 改 變 右 面 與 左 面 的 顏 色, 所 以 元 素 3 的 內 容 不 變 則 結 論 可 知 原 本 的 column 2 被 替 換 成 5, 然 後 column 1 與 column 2 互 換, 如 下 所 示 : 而 平 台 旋 轉 180 度 以 及 手 臂 翻 轉 二 次 三 次, 可 以 由 以 上 三 種 變 化 規 律 衍 生 出 來 至 於 手 臂 夾 住 方 塊 旋 轉 的 動 作, 由 於 上 二 層 被 夾 住 固 定, 不 會 動 到 位 於 第 二 層 的 中 心 小 方 塊, 所 以 六 面 的 顏 色 不 會 改 變, 如 以 下 所 示, 其 中 r 是 指 夾 住 旋 轉 90 度,l 是 指 夾 住 旋 轉 -90 度,2r(2l) 是 指 夾 住 旋 轉 180 度 : 44

53 夾 住 正 轉 90 度 : 夾 住 反 轉 90 度 : l 綜 合 以 上 的 變 化 規 律 以 及 機 器 人 的 解 題 動 作, 可 以 列 出 一 個 較 為 完 整 的 陣 列 變 化, 在 此 以 解 題 器 的 步 驟 一 為 例, 而 方 塊 的 起 始 狀 態 定 為 : 其 中, 由 於 機 台 的 限 制 所 以 必 須 將 目 標 色 面 轉 至 底 面, 也 就 是 元 素 1 的 內 容 必 須 與 目 標 面 的 顏 色 編 號 相 同 在 步 驟 一 中 目 標 面 位 於 前 面, 所 以 機 器 人 必 須 先 平 台 旋 轉 180 度 然 後 手 臂 翻 一 次 面, 再 夾 住 方 塊 正 轉 90 度 而 目 標 面 的 可 能 位 置 共 有 6 種, 它 們 的 機 台 動 作 與 陣 列 變 化 如 下 所 示, 為 了 簡 化, 在 此 只 列 出 目 標 面 A 與 相 對 面 A, 其 餘 為 X: case I: 目 標 面 位 於 底 面 A X X 夾 住 旋 轉 無 須 旋 轉 翻 面, 可 以 直 接 夾 住 旋 轉 case II: 目 標 面 位 於 前 面 X A X X X A X A X A X X 夾 住 旋 轉 先 旋 轉 180 度 再 翻 一 次 面, 然 後 夾 住 旋 轉 則 可 得 知 case II 的 動 作 為 RRT case III: 目 標 面 位 於 右 面 X X A X A X A X X 夾 住 旋 轉 45

54 先 正 轉 90 度 再 翻 一 次 面, 然 後 夾 住 旋 轉 則 可 得 知 case III 的 動 作 為 RT case IV: 目 標 面 位 於 左 面 X X A X A X A X X 夾 住 旋 轉 先 反 轉 90 度 再 翻 一 次 面, 然 後 夾 住 旋 轉 則 可 得 知 case IV 的 動 作 為 LT case V: 目 標 面 位 於 後 面 X A X A X X 夾 住 旋 轉 翻 一 次 面, 然 後 夾 住 旋 轉 則 可 得 知 case V 的 動 作 為 T case VI: 目 標 面 位 於 頂 面 A X X X A X A X X 夾 住 旋 轉 翻 二 次 面, 然 後 夾 住 旋 轉 則 可 得 知 case VI 的 動 作 為 TT 之 後 我 們 可 以 利 用 以 上 6 種 情 況 來 設 計 機 器 人 的 動 作, 並 且 配 合 解 題 器 所 產 生 出 的 解 題 過 程 最 後 可 以 發 現, 雖 然 解 題 器 的 過 程 只 有 15 個 步 驟, 但 是 由 於 機 台 的 動 作 限 制, 換 成 機 器 人 的 動 作 可 能 會 有 大 約 70 個 步 驟, 在 此 則 設 計 了 一 個 對 應 於 解 題 器 結 果 的 機 器 人 動 作 對 照 程 式, 將 所 有 步 驟 的 目 標 色 面 編 號 以 及 夾 住 旋 轉 多 少 度 列 成 陣 列, 如 下 所 示 : r l l 2r r l l 2r r 2r l r r l l 目 標 色 面 旋 轉 度 數 為 了 方 便 設 計, 將 旋 轉 度 數 的 英 文 代 號 改 以 數 字 表 示 : 旋 轉 度 數 46

55 其 中 旋 轉 度 數 的 1 為 正 轉 90 度,2 為 旋 轉 180 度,3 為 反 轉 90 度 再 配 合 先 前 的 目 標 色 面 位 置 與 機 器 人 動 作 進 行 判 斷, 以 及 各 機 器 人 動 作 的 方 塊 色 面 變 化 規 律 進 行 狀 態 更 新, 可 產 生 以 下 所 示, 方 塊 的 起 始 狀 態 為 : 步 驟 一 : case II : RRT revolve right 180 turn once catch and revolve 90 平 台 旋 轉 180 度 翻 轉 一 次 夾 住 旋 轉 90 度 ind = 方 塊 現 在 的 狀 態 步 驟 二 : case II : RRT revolve right 180 turn once catch and revolve -90 平 台 旋 轉 180 度 翻 轉 一 次 夾 住 旋 轉 -90 度 ind = 方 塊 現 在 的 狀 態 步 驟 三 : case VI : LT revolve left 90 turn once catch and revolve -90 平 台 反 轉 90 度 翻 轉 一 次 夾 住 旋 轉 -90 度 ind = 47

56 4 1 5 方 塊 現 在 的 狀 態 步 驟 四 : case VI : LT revolve left 90 turn once catch and revolve 180 平 台 反 轉 90 度 翻 轉 一 次 夾 住 旋 轉 180 度 ind = 方 塊 現 在 的 狀 態 步 驟 五 : case V : T turn once catch and revolve 90 翻 轉 一 次 夾 住 旋 轉 90 度 ind = 方 塊 現 在 的 狀 態 步 驟 六 : case IV : TT turn twice catch and revolve -90 翻 轉 二 次 夾 住 旋 轉 -90 度 ind = 方 塊 現 在 的 狀 態 步 驟 七 : case VI : LT 48

57 revolve left 90 turn once catch and revolve -90 平 台 反 轉 90 度 翻 轉 一 次 夾 住 旋 轉 -90 度 ind = 方 塊 現 在 的 狀 態 步 驟 八 : case VI : LT revolve left 90 turn once catch and revolve 180 平 台 反 轉 90 度 翻 轉 一 次 夾 住 旋 轉 180 度 ind = 方 塊 現 在 的 狀 態 步 驟 九 : case V : T turn once catch and revolve 90 翻 轉 一 次 夾 住 旋 轉 90 度 ind = 方 塊 現 在 的 狀 態 步 驟 十 : case IV : TT turn twice catch and revolve 180 翻 轉 二 次 夾 住 旋 轉 180 度 ind = 49

58 1 2 3 方 塊 現 在 的 狀 態 步 驟 十 一 : case III : RT revolve right 90 turn once catch and revolve -90 平 台 正 轉 90 度 翻 轉 一 次 夾 住 旋 轉 -90 度 ind = 方 塊 現 在 的 狀 態 步 驟 十 二 : case III : RT revolve right 90 turn once catch and revolve 90 平 台 正 轉 90 度 翻 轉 一 次 夾 住 旋 轉 90 度 ind = 方 塊 現 在 的 狀 態 步 驟 十 三 : case VI : LT revolve left 90 turn once catch and revolve 90 平 台 反 轉 90 度 翻 轉 一 次 夾 住 旋 轉 90 度 ind = 方 塊 現 在 的 狀 態 50

59 步 驟 十 四 : case V : T turn once catch and revolve -90 翻 轉 一 次 夾 住 旋 轉 -90 度 ind = 方 塊 現 在 的 狀 態 步 驟 十 五 : case VI : LT revolve left 90 turn once catch and revolve -90 平 台 反 轉 90 度 翻 轉 一 次 夾 住 旋 轉 -90 度 ind = 方 塊 現 在 的 狀 態 由 以 上 可 以 得 到 更 完 整 的 機 器 人 動 作 資 訊, 而 這 些 動 作 都 是 連 貫 下 來 的, 並 且 隨 時 更 新 方 塊 的 目 前 狀 態 起 始 位 置 到 步 驟 四 : l l 步 驟 五 到 步 驟 九 : l l 步 驟 十 到 步 驟 十 四 : l 6 4 l 步 驟 十 五 :

60 第 四 章 結 論 與 未 來 研 究 4.1 結 論 本 論 文 以 PC 為 基 礎 設 計 解 魔 術 方 塊 機 器 人, 並 運 用 樂 高 積 木 組 合 成 理 想 的 實 驗 機 構, 樂 高 積 木 的 組 合 具 有 多 變 化 性 以 及 塑 膠 材 料 的 低 成 本 特 性, 可 大 幅 減 少 機 構 的 組 裝 時 間 及 成 本 的 開 銷 接 著 是 讓 PC 取 得 魔 術 方 塊 的 6 面 顏 色 資 訊, 這 裡 使 用 了 網 路 攝 影 機 為 影 像 擷 取 裝 置, 與 CCD 相 較 之 下 雖 然 畫 素 較 低, 但 具 有 USB 隨 插 即 用 的 優 點, 也 不 需 安 裝 影 像 擷 取 卡, 同 時 設 備 成 本 也 較 低 之 後 利 用 MATLAB 的 影 像 擷 取 工 具 箱 將 網 路 攝 影 機 的 影 像 擷 取 至 資 料 庫, 並 透 過 影 像 處 理 工 具 箱 對 擷 取 的 影 像 進 行 灰 階 及 二 元 化 處 理, 適 當 的 去 除 影 像 的 白 點 以 求 得 方 塊 的 邊 框 座 標, 如 此 便 可 得 知 九 個 小 方 塊 的 涵 蓋 區 域, 再 針 對 這 九 個 小 方 塊 進 行 顏 色 的 判 斷 最 後, 利 用 魔 術 方 塊 解 題 器 套 入 6 個 色 面 的 色 彩 分 佈 進 行 解 題, 並 將 解 題 步 驟 轉 換 為 馬 達 的 控 制 資 訊, 透 過 NXT 與 樂 高 積 木 組 合 成 的 機 構 將 方 塊 的 各 色 面 轉 正 整 體 實 驗 結 合 了 程 式 設 計 與 運 用, 以 及 硬 體 設 備 的 應 用 52

61 4-2 未 來 研 究 本 論 文 設 計 的 解 魔 術 方 塊 機 器 人 尚 有 許 多 不 足 的 地 方, 例 如 在 未 來 的 發 展 上 可 以 將 PC 端 的 MATLAB 魔 術 方 塊 解 題 器 之 演 算 法 則, 實 現 在 NXT 控 制 盒 上 也 可 以 增 加 NXT 基 底 的 影 像 擷 取 模 組, 如 NXTCam 並 且 可 以 改 善 解 解 題 器 的 演 算 法 試 著 減 少 解 題 步 驟, 以 達 到 快 速 解 題 的 目 的 而 機 構 的 部 分 可 以 改 善 機 器 手 臂 的 架 構, 論 文 中 的 機 構 只 使 用 2 個 馬 達, 對 於 某 些 翻 面 動 作 是 較 為 不 便 的, 可 以 試 著 加 入 更 多 的 馬 達 來 省 去 不 必 要 的 翻 面 動 作 53

62 參 考 文 獻 [1] 國 科 會 控 制 學 門 [2] 貝 登 堡 機 器 人 學 苑 [3] 台 灣 機 器 人 學 會 [4] 台 灣 機 器 人 產 業 發 展 協 會 [5] 內 政 部 統 計 處 [6] 本 田 企 業 ASIMO 網 頁 [7] 介 紹 網 頁 [8] 介 紹 網 頁 [9] 國 立 台 灣 大 學 機 器 人 實 驗 室 [10] 羅 仁 權 教 授 網 頁 [11] 機 器 人 世 界 情 報 網 [12] 維 基 百 科 NXT 介 紹 [13] 陸 嘉 宏, 魔 術 方 塊 破 解 祕 笈, 高 寶 出 版 社,2007 年 [14] 許 技 江, 魔 術 方 塊 高 手 制 霸 技, 采 竹 出 版 社,2009 年 [15] 陸 嘉 宏, 速 解 高 手!20 秒 解 開 魔 術 方 塊, 高 寶 出 版 社,2010 年 [16] 國 立 台 灣 師 範 大 學 郭 君 逸 助 理 教 授 魔 術 方 塊 網 站 [17] 解 魔 術 方 塊 機 器 人 影 片 [18] YouTube 解 魔 術 方 塊 機 器 人 影 片 [19] 解 魔 術 方 塊 機 器 54

63 人 影 片 [20] YouTube 解 魔 術 方 塊 機 器 人 影 片 [21] 解 魔 術 方 塊 機 器 人 影 片 [22] 網 站 [23] 曾 吉 弘 謝 宗 翰 侯 俊 宇, 機 器 人 新 視 界 NXC 與 NXT, 藍 海 文 化,2009 年 [24] 鈦 思 科 技 [25] Alasdair McAndrew, 數 位 影 像 處 理, 高 立 圖 書,2005 年 [26] 今 古 庸 龍 魔 方 網 站 55