張雨田

摘要：本研究在圖像識別技術(shù)的幫助下，讓樂高機(jī)器人完成解魔方的過程。在硬件條件受到限制的情況下，通過理論分析和實(shí)際測試，盡可能用合理應(yīng)用函數(shù)、調(diào)整參數(shù)、適當(dāng)控制外部環(huán)境變量的方式使顏色識別的準(zhǔn)確性達(dá)到一個(gè)較高的水平。實(shí)驗(yàn)中，轉(zhuǎn)魔方用的機(jī)械臂、轉(zhuǎn)盤由Lego Mindstorms NXT的零件組裝而成，魔方各個(gè)面的圖像由一個(gè)普通攝像頭拍攝，由一臺電腦進(jìn)行圖像分析和還原步驟的計(jì)算。在魔方還原過程中，PC端和NXT端要運(yùn)行各自的程序，程序均使用LabVIEW編寫。

關(guān)鍵詞：LabVIEW 樂高機(jī)器人 魔方 模式匹配 圖像分析

中圖分類號：TP242 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2014）12-0136-02

隨著科技的進(jìn)步，越來越多的人試圖用機(jī)器人自動復(fù)原魔方。本研究參考了網(wǎng)上的魔方機(jī)器人的相關(guān)資料，實(shí)現(xiàn)了一個(gè)完整的魔方機(jī)器人系統(tǒng)。

1 系統(tǒng)結(jié)構(gòu)

圖1為包括機(jī)械部分和所有外部設(shè)備在內(nèi)的完整系統(tǒng)結(jié)構(gòu)。

2 硬件實(shí)現(xiàn)

機(jī)械部分采用了樂高M(jìn)indStorms NXT機(jī)器人套件，采用2個(gè)電機(jī)配合完成魔方的翻滾與扭轉(zhuǎn)，造型仿造了動力老男孩的博客中的魔方機(jī)器人[1]。此外，一臺計(jì)算機(jī)用于分析圖像和計(jì)算還原步驟并實(shí)時(shí)顯示魔方當(dāng)前狀態(tài)，一個(gè)攝像頭用于采集圖像。

如圖2所示，攝像頭從魔方上方垂直對著魔方的角度進(jìn)行拍攝，照明條件良好。使用的魔方為國甲5三階速擰魔方。

3 軟件實(shí)現(xiàn)

軟件部分分為PC端程序和NXT端程序兩部分。

3.1 PC端程序

PC端程序功能分為：（1）獲取圖像；（2）分析圖像；（3）查錯(cuò)；（4）解魔方；（5）傳送指令。

3.1.1 獲取圖像

拍攝魔方6個(gè)面的圖像，存入指定目錄下。

3.1.2 分析圖像

分析圖像部分的功能又可以分為四大塊：（1）生成模板：生成6個(gè)面中心色塊的模板。使用的模板圖要注意參數(shù)選擇。經(jīng)過理論研究和實(shí)驗(yàn)測試，最后的選擇是：模板圖的類型用HSL（U32），模板的Learn Mode選的是Shift Information[2]，模板的Feature Mode選的是Color。（2）生成色塊數(shù)組：用模式匹配識別魔方6個(gè)面的顏色分布，并將結(jié)果轉(zhuǎn)化為9*6魔方色塊數(shù)組。由于區(qū)分紅、橙、黃需要較高的色彩精確度，模式匹配函數(shù)的Color Sensitivity設(shè)為High Sensitivity。由于搜索的色塊間距較近，Search Strategy設(shè)為Conservative。（3）顯示魔方初始狀態(tài)：用顏色模板拼出6個(gè)面。（4）算出魔方初始狀態(tài)：查表把色塊數(shù)組轉(zhuǎn)化成規(guī)范的初始狀態(tài)字符串。

3.1.3 查錯(cuò)

這部分是PC根據(jù)前一部分輸出的色塊數(shù)組，判斷該色塊數(shù)組是否合理（是否每種顏色各9塊），從而判斷是否繼續(xù)進(jìn)行解魔方的操作。

3.1.4 解魔方

本研究完成的系統(tǒng)中解魔方模塊的采用Thistlethwaite's algorithm[3]算法，該算法和一般解魔方一層一層還原的思想不同。它一步一步減小魔方的打亂程度，使魔方變得能用越來越簡單的步驟還原。群降法的思想復(fù)雜，卻是最少步數(shù)還原魔方的最佳選擇。算法實(shí)現(xiàn)參考了Jaap Scherphuis編寫的[4]C++代碼。輸入魔方初始狀態(tài)（每塊的顏色，如：RU LF UB DR DL BL UL FU BD RF BR FD LDF LBD FUL RFD UFR RDB UBL RBU），輸出解魔方步驟（[面][旋轉(zhuǎn)數(shù)]，如：D1B3F1U3B1L2U3B2D3L2U1R1D1F2D1L2D2B2D3L2D1B2U2L2D2B2U2L2B2R2）。

3.1.5 傳送指令

將解魔方步驟分成一個(gè)一個(gè)小步，逐步傳給NXT，并在屏幕上顯示魔方當(dāng)前狀態(tài)、變化趨勢、還原步驟。

3.2 NXT端程序

NXT端程序分為：（1）初始化；（2）等待；（3）還原。

3.2.1 初始化

將魔方6個(gè)面的坐標(biāo)數(shù)組初始化。坐標(biāo)數(shù)組用于保存魔方每個(gè)面中心顏色（ASCII碼形式）的變化。

機(jī)器人通過推和轉(zhuǎn)的動作將要拍的面翻到頂面，然后通知電腦獲取圖像，直到6個(gè)面都拍完。

3.2.2 等待

該部分NXT的主要功能就是等待接收PC向它發(fā)送的命令。PC端的分析圖像、查錯(cuò)、解魔方以及一些手動操作都在NXT的等待階段完成。

3.2.3 還原

這一部分是NXT端的核心部分，包括兩類操作：翻面和轉(zhuǎn)面。翻面和轉(zhuǎn)面這兩種操作將會不斷交替進(jìn)行，直到收到PC端的結(jié)束信號。

（1）翻面：這一部分，要將需要扭轉(zhuǎn)的面以最簡單的步驟翻到底面，并更新坐標(biāo)數(shù)組。坐標(biāo)數(shù)組保存的是U、D、L、R、F、B六個(gè)位置的面最初所在的位置。翻轉(zhuǎn)魔方用到機(jī)器人的4種操作的結(jié)合：（1）機(jī)械臂推，（2）底盤順時(shí)針轉(zhuǎn)90度，（3）底盤逆時(shí)針轉(zhuǎn)90度，（4）底盤順時(shí)針轉(zhuǎn)180度。

（2）轉(zhuǎn)面：這部分程序只需要根據(jù)收到的旋轉(zhuǎn)數(shù)1、2、3分別在機(jī)械臂卡住魔方上兩層的狀態(tài)下讓底盤逆時(shí)針轉(zhuǎn)90度、順時(shí)針轉(zhuǎn)180度、順時(shí)針轉(zhuǎn)90度。

4 實(shí)驗(yàn)結(jié)果及流程

這里簡略從用戶角度介紹一下實(shí)驗(yàn)流程。

4.1 模式選擇

打開PC端主程序后選擇要使用的攝像頭和通信方式（USB或藍(lán)牙）。

4.2 選擇感興趣區(qū)

程序開始運(yùn)行后，PC和NXT互相配合，采集圖像，然后彈出對話框，讓用戶框出有效區(qū)。程序會在有效區(qū)中檢測線段，從而找到中心色塊，并生成6個(gè)顏色模板。

之后電腦將識別顏色，顯示出魔方的初始狀態(tài)，并判斷顏色是否正確識別。假如不正確，用戶可以選擇重新識別。

4.3 進(jìn)行還原

機(jī)器人根據(jù)PC端傳來的指令不斷進(jìn)行各種翻面、轉(zhuǎn)面的動作直到還原完畢。屏幕上會顯示魔方狀態(tài)圖和還原步驟。圖3為狀態(tài)圖。

4.4 實(shí)驗(yàn)結(jié)束

狀態(tài)圖顯示6面同色，步驟顯示欄顯示完成，魔方還原完畢。

5 結(jié)語

目前解魔方系統(tǒng)的運(yùn)行結(jié)果受到機(jī)械因素的影響較大，除了對于機(jī)械的改進(jìn)之外還可以從改進(jìn)模式匹配算法、改變顏色識別方式、增加傳感器、增加剩余時(shí)間顯示等方面進(jìn)行改進(jìn)。

本研究的重點(diǎn)在于對圖像識別技術(shù)的應(yīng)用。雖然魔方機(jī)器人屬于娛樂性質(zhì)，但是通過對圖像識別技術(shù)的研究，我們可以了解到機(jī)器視覺的性能、受到的限制以及一些彌補(bǔ)的方式，從而將這一技術(shù)沿用到更貼近生產(chǎn)、生活的方面。

參考文獻(xiàn)

[1]動力老男孩.魔方機(jī)器人.http：//www.diy-robots.com/？page_id=46.

[2]National Instruments Corp.，NI Vision for LabVIEW User Manual. www.ni.com/pdf/manuals/371007b.pdf.

[3]Scherphuis， J.， Thistlethwaite's 52-move algorithm. http：//www.jaapsch.net/puzzles/thistle.htm.

[4]Scherphuis， J.， Contest to Find a Short Program to Solve the Cube. http：//tomas.rokicki.com/cubecontest/.