基于STM32機械臂解魔方算法研究

盛慶華， 杜永均， 羅 飛， 李辰龍， 何 凱

(杭州電子科技大學(xué) a.電子信息學(xué)院； b.自動化學(xué)院，杭州 310018)

基于STM32機械臂解魔方算法研究

盛慶華a， 杜永均b， 羅 飛a， 李辰龍a， 何 凱b

(杭州電子科技大學(xué) a.電子信息學(xué)院； b.自動化學(xué)院，杭州 310018)

針對雙手臂智能機器人復(fù)原魔方這一難題，設(shè)計了一套快速解魔方系統(tǒng)。該系統(tǒng)由圖像采集、圖像處理和機械臂控制三部分組成。首先，利用android手機中的DroidCam軟件采集魔方圖像并將該圖像信息傳送至PC端；然后，通過LabVIEW軟件提供的庫函數(shù)對圖像進行分析和識別，并將結(jié)果發(fā)送給STM32處理器；最后，通過層先法得到復(fù)原魔方的步驟并控制2個機械臂復(fù)原魔方。實驗結(jié)果表明,本系統(tǒng)可智能恢復(fù)任意打亂的魔方，并且執(zhí)行過程控制較為簡單，性能穩(wěn)定可靠。

復(fù)原魔方； 圖像識別； 層先法

0 引 言

智能機器人復(fù)原魔方作為娛樂科普機器人是當(dāng)今的一個研究熱點，其能很好地代替人來復(fù)原復(fù)雜的魔方。本系統(tǒng)利用LabVIEW軟件完成對魔方圖像的識別[1]，IMAQ提取魔方圖像[2]；然后通過腐蝕用二值算法提取色塊RGB值[3]，再通過閾值識別魔方顏色。復(fù)原魔方采用了方便易懂易于實現(xiàn)的層先行魔方算法來獲得魔方旋轉(zhuǎn)步驟，然后通過算法將魔方復(fù)原步驟轉(zhuǎn)換成雙手臂的動作步驟來完成魔方的復(fù)原[4]。

文中的還原魔方機器人采用了類人型的雙機械臂，可觀賞性高，研究價值大，但執(zhí)行機構(gòu)控制上難度也更大。另外圖像識別采用的方案也簡單易行、經(jīng)濟，借用了智能手機攝像頭作為采集圖像信息。由于大多數(shù)人都有智能手機，從某種意義來說，可以節(jié)約開發(fā)成本，使用了LabVIEW軟件來分析處理圖像，靈活、方便。

1 系統(tǒng)總體設(shè)計

系統(tǒng)利用軟件DroidCam將上位機PC和android手機通過WiFi相連接構(gòu)成局域網(wǎng)，將手機上的攝像頭實時采集到的數(shù)據(jù)傳輸?shù)絇C，再通過LabVIEW提供的視覺助手LabVIEW VISION ASSISTANT來處理分析圖像數(shù)據(jù)[5-6]，識別魔方6個面的各個顏色信息，再利用LabVIEW提供的串口控制函數(shù)，將處理好的魔方色塊信息發(fā)送給下位機STM32[7]；STM32通過串口接收到一個完整魔方的各個面顏色的信息后，再用層先法還原魔方算法函數(shù)，得到相應(yīng)的復(fù)原魔方的旋轉(zhuǎn)步驟，再調(diào)用復(fù)原魔方的動作函數(shù)，控制機械臂把任意打亂的魔方復(fù)原。整個系統(tǒng)的總體構(gòu)圖如圖1所示，機械臂的實物圖如圖2所示。

圖1 系統(tǒng)的總體框圖

圖2 機械臂實物圖

2 軟件設(shè)計

2.1 圖像采集系統(tǒng)

2.1.1 圖像采集方案論證

方案1 利用單片機結(jié)合CMOS攝像頭做顏色識別[8]。優(yōu)點：成本低，體積小，使用方便。缺點：對圖像提取，顏色分辨算法要求較高，攝像頭像素較低，受光線干擾大，不能很好地識別魔方各個色塊。

方案2 利用LabVIEW上位機結(jié)合手機攝像頭做顏色識別。優(yōu)點：圖像提取，顏色識別算法由上位機提供，方便可靠，手機攝像頭清晰度高，可以有效的識別魔方各個色塊。缺點：需要配備電腦聯(lián)機使用，使用相對不方便。綜上比較，選擇方案2。

2.1.2 圖像采集流程

打開手機中已安裝的DroidCam并和PC通過WiFi相連接，在LabVIEW中，創(chuàng)建IMAQ，通過索引打開攝像頭并配置連續(xù)采集，在循環(huán)中每隔40 ms采集1幀圖像，最后關(guān)閉攝像頭。經(jīng)過檢測魔方色塊邊緣后，腐蝕圖像去除雜點，從而得到色塊的位置，最后對顏色的RGB值進行匹配，確定色塊顏色，最后根據(jù)NI-VISA提供的串口控制函數(shù)把信息傳給下位機[9]。圖像采集流程圖如圖3所示。

圖3 圖像采集流程圖

2.2 魔方還原算法

2.2.1 魔方還原算法

方案1 CFOP法。實現(xiàn)過程如下：底層十字、同時對好前兩層、調(diào)整好最后一層的朝向、調(diào)整好最后一層的順序。此方法使用了119個公式，分為4個步驟復(fù)原魔方，使得魔方復(fù)原的最好成績突破了6 s大關(guān)。

方案2 層先法。將魔方分為底層、中層、頂層分層復(fù)原。用層先法復(fù)原魔方一共分7步：底層十字、調(diào)整底面角塊、復(fù)原中層棱塊、頂面十字、頂角歸位、調(diào)整頂角位置、調(diào)整頂棱的位置。按照這7步走，配合幾個固定的簡單公式，魔方就可以成功復(fù)原。

分析：方案1在速度上較快，但是公式繁多，對于寫代碼比較復(fù)雜，不易實現(xiàn)；方案2的特點在于不用像CFOP方法那樣需要大量的公式，而是只用幾個簡單的公式就可以完成，代碼實現(xiàn)相對容易，而且較為容易理解。最終選擇方案2。

2.2.2 魔方抽象模型和復(fù)原魔方理論基礎(chǔ)[10-11]

(1) 魔方特性。魔方有6個中心方塊并且顏色固定不會隨旋轉(zhuǎn)而改變，6種顏色，12個棱塊，8個角塊。魔方展開數(shù)值表示如圖4所示。

圖4 魔方展開數(shù)值表示圖

(2) 定理[12]。對于復(fù)原狀態(tài)下的魔方實施任意的轉(zhuǎn)動序列，打亂之后的魔方，存在一定的轉(zhuǎn)動序列使得魔方變?yōu)橐韵?種基本情況：①僅有三棱置換；②僅有三角置換；③僅有兩棱反轉(zhuǎn)；④僅有兩角扭轉(zhuǎn)，且扭轉(zhuǎn)方向不同。

(3) 魔方屬性的表示(見表1)。

表1 魔方特性的表示

12個棱塊：BL,BR,FL,FR,DB,DL,DF,DR,UB,UL,UR,UF。

8個角塊：UFR,UBL,URB,ULF,DRF,DFL,DLB,DBR。

(4) 12個棱塊的矩陣表示：

(1)

(5) 8個角塊的矩陣表示：

(2)

(6) 復(fù)原魔方的狀態(tài)表示：

(3)

(7) 數(shù)學(xué)群論[13]。

①定義：設(shè)集合M={1，2，…，n},并把M的經(jīng)過某一個置換后的集合記為Mi，其中i=1,2,…,n。若M的1個置換滿足：?(M1)=M2，?(M2)=M3，?(Mj-1)=Mj其中，該置換周期記為j的循環(huán)，記為(M1,M2,…,Mj)。如果2個循環(huán)(M1,M2,…,Mj)，(Mk+1,Mk+2,…,Mk+j)它們沒有公共的集合Mi，也就是沒有相交狀態(tài)，那么這兩個循環(huán)不相交。

②根據(jù)以上定義，魔方的群生成元用循環(huán)形式表示：

F=(17,19,24,22) (18,21,23,20) (6,25,43,16) (7,28,42,13) (8,30,41,11)

B=(33,35,40,38) (34,37,39,36) (3,9,46,32) (2,12,47,29) (1,14,48,27)

L=(9,11,16,14) (10,13,15,12) (1,17,41,40) (4,20,44,37) (6,22,46,35)

R=(25,27,32,30) (26,29,31,28) (3,38,43,19) (5,36,45,21) (8,33,48,24)

U=(1,3,8,6) (2,5,7,4) (9,33,25,17) (10,34, 26,18) (11,35,27,19)

D=(41,43,48,46) (42,45,47,44) (14,22,33,38) (15,23,31,39) (16,24,32,40)

③例如，轉(zhuǎn)動魔方的右面90°的情況表示：

R=(FR,UR,BR,DR)(URF,BRU,DRB,FRD)

(8) 魔方復(fù)原過程。當(dāng)研究某個轉(zhuǎn)動序列的周期性和循環(huán)特點，只需要根據(jù)數(shù)學(xué)群論的置換乘法規(guī)則，再利用數(shù)學(xué)群論的生成元基本公式就可以得出周期性規(guī)律，所以根據(jù)某些策略就可以把打亂的魔方轉(zhuǎn)化成定理中的幾種特殊情況，然后再研究對應(yīng)特殊情況下還原魔方的轉(zhuǎn)動序列，那么魔方就可以復(fù)原。

A.算過程：①根據(jù)層先法策略過程，先找出當(dāng)前某塊應(yīng)該放的顏色塊；②遍歷當(dāng)前整個魔方的顏色狀況，找到那個顏色塊對應(yīng)的位置；③根據(jù)它所在的位置信息，調(diào)用層先行所封裝好的那幾個對應(yīng)函數(shù)，同時記錄下還原的旋轉(zhuǎn)面及方向的步驟信息。

B.根據(jù)所得到的旋轉(zhuǎn)面及方向，再調(diào)用各個面旋轉(zhuǎn)的函數(shù)，把魔方的當(dāng)前顏色位置信息，按照還原公式得到的還原步驟改變。

執(zhí)行完了，再開始以上A、B步驟，如此重復(fù)，直到整個魔方還原。層先行程序流程圖如圖5所示。

圖5 程序流程圖

3 系統(tǒng)硬件及控制

3.1 系統(tǒng)硬件組成

參考馬江[14]對6自由度機器臂構(gòu)型的選擇，通過改進，本系統(tǒng)采用4自由度的雙機械手，8個LD-3015MG數(shù)字舵機[15]，270°定位，17 kg扭力。系統(tǒng)還采用了STM32F103RCT6芯片，TFT彩屏，PC以及android手機等。

3.2 機械臂的執(zhí)行過程

由于采用的是類人型的兩只機械臂，就必然會要有1只手固定，另1只手動作，為了避免在旋轉(zhuǎn)不同面時，2只手出現(xiàn)太多的冗余切換動作，采用了一種創(chuàng)新的辦法。即：①根據(jù)還原步驟，獲得當(dāng)前旋轉(zhuǎn)色塊的顏色值并給PresentFaceVal，機械臂1以上黃下白面的中心垂線為旋轉(zhuǎn)軸(另一只機械臂為機械臂2)切換紅綠橙藍的旋轉(zhuǎn)面。②若旋轉(zhuǎn)面為紅綠橙藍中的一個，則計算當(dāng)前旋轉(zhuǎn)面PresentFaceVal與LastFaceVal上一次旋轉(zhuǎn)面之間的顏色數(shù)值差，來判斷兩個面之間的相對空間位置，進而確定機械臂1對魔方的切換面的操作動作；③若旋轉(zhuǎn)面為白色，可以直接讓機械臂1抓白色面旋轉(zhuǎn)；④若旋轉(zhuǎn)面為黃色，用機械臂2先將魔方以藍綠面或紅橙面為軸旋轉(zhuǎn)180°，此時黃色面由機械臂1直接抓住進行旋轉(zhuǎn)，旋轉(zhuǎn)完面后使魔方回到初始狀態(tài)(即上黃下白的狀態(tài))。⑤每次旋轉(zhuǎn)結(jié)束后，更新上一旋轉(zhuǎn)面信息LastFaceVal=PresentFaceVal，便于下個旋轉(zhuǎn)面的控制。⑥重復(fù)①～⑤的步驟直到機械臂最終按照還原步驟執(zhí)行結(jié)束。

3.3 機械臂動作原理流程圖

機械臂動作原理流程圖如圖6所示。

圖6 機械臂動作原理流程圖

4 結(jié) 語

本系統(tǒng)設(shè)計并實現(xiàn)了一個基于STM32F103RCT6的可以復(fù)原一個任意打亂順序的三階魔方的機器人。一般的魔方復(fù)原機器人的結(jié)構(gòu)是4個或者6個機械臂，作為執(zhí)行機構(gòu)，冗余復(fù)雜，不太具有觀賞性。本系統(tǒng)富有挑戰(zhàn)性地采用了2個4自由度的類人機械臂，可以較靈活地復(fù)原一個三階魔方，準(zhǔn)確、清晰地再現(xiàn)了人復(fù)原魔方的步驟，項目具有一定的創(chuàng)新性和趣味性。但因?qū)嶒炇覘l件限制，機械臂工藝的粗糙，在以機械臂為執(zhí)行機構(gòu)工作時，對于一些動作執(zhí)行精度并不能達到要求，其機械工藝可以進一步改進。在由復(fù)原魔方的步驟轉(zhuǎn)化成機械臂的執(zhí)行步驟的過程中，也可以在實踐過程中進一步優(yōu)化代碼，減少冗余動作，加快復(fù)原魔方速度。

[1] 陳樹學(xué). LabVIEW實用工具詳解[M]. 北京：電子工業(yè)出版社，2014：316-339.

[2] 丁 晟，蔣曉瑜，汪 熙. 基于LabVIEW的圖像處理技術(shù)研究[J]. 微計算機信息，2010，26(29)：204-205.

[3] 張 琪. 結(jié)合邊緣檢測的圖像二值化算法[D]. 吉林：吉林大學(xué)，2011.

[4] 梁小龍. 解魔方算法的研究和系統(tǒng)實現(xiàn)[D]. 沈陽：東北大學(xué)，2011.

[5] 田 田，徐 林，趙洪華，等. 解魔方四爪機械手結(jié)構(gòu)設(shè)計與操作[J]. 機器人技術(shù)與應(yīng)用，2014(5)：38-39.

[6] 張雨田. 基于LabVIEW 的魔方機器人系統(tǒng)設(shè)計[J]. 數(shù)字技術(shù)與應(yīng)用，2014(12)：136-137.

[7] 劉 軍, 張 洋, 嚴(yán)漢宇. 例說STM32[M]. 2版.北京：北京航空航天大學(xué)出版社，2014：107-115.

[8] 劉政林，周 銘，劉欣達，等. 基于計算機視覺的塑料瓶顏色識別和分揀系統(tǒng)[J]. 電子測量技術(shù)，2013，36(11)：43-48.

[9] 吳 偉. 基于VISA的儀器通信技術(shù)的研究與實現(xiàn)[D]. 西安：西安科技大學(xué)，2009.

[10] 胡 鑫. 基于ARM9的嵌入式魔方機器人系統(tǒng)設(shè)計[D]. 廣州：華南理工大學(xué)，2011.

[11] 鄭 瑜. 魔方原理及其應(yīng)用[D]. 杭州：浙江大學(xué)應(yīng)用數(shù)學(xué)系，2009.

[12] Xin Hu, Shuanshuan Chen, Lei Nie,etal． Design of an Embedded Vision System for the Rubik’s CubeRobot[C]//International Conference on Information and Automation ( ICIA ) 2011 IEEE International Conference， 2011，490-494．

[13] 孫雨耕，俎云霄. 群圖的基本理論及置換群圖的構(gòu)造[J]. 天津大學(xué)學(xué)報(自然科學(xué)與工程技術(shù)版)，2000，33(2)：129-133.

[14] 馬 江. 6自由度機械臂控制系統(tǒng)設(shè)計與運動學(xué)仿真[D].北京：北京工業(yè)大學(xué)，2009.

[15] 紀(jì)海彬. 基于AVR的解三階魔方機器人研究[D].長春：長春理工大學(xué)，2013.

Research of Solution of Rubik’s Cube and Implemented by a Robot Based on STM-32

SHENGQinghuaa，DUYongjunb，LUOFeia，LIChenlonga，HEKaib

(a. School of Electronic Information; b. School of Automation, Hangzhou Dianzi University, Hangzhou 310018, China)

Aiming at the problem of Rubik’s cube recovered by dual-arm robot, this paper designed a system of novel fast solving Rubik’s cube. The system consists of image acquisition, image processing and mechanical arm control. First of all, DroidCam which is an android mobile phone software is used to acquire Rubik’s cube image, then the image information is transmitted to PC. Secondly, the library function provided by LabVIEW software is utilized to analyze and recognize the image, then the result is sent to the STM32 processor. Finally, we can obtain the steps of recovering Rubik’s cube by layer first method and control the two mechanical arms to operate the scheme step by step. Experimental results prove that this system can be smart to recover any disordered Rubik’s cube, the process is relatively simple and the performance of this system is stable and reliable.

magic cube recovery; image identification; layer first method

2016-07-14

浙江省大學(xué)生新苗計劃(2016R407024)；杭州電子科技大學(xué)校級大學(xué)生創(chuàng)新創(chuàng)業(yè)項目(XJ201411)

盛慶華(1978-)，男，浙江蘭溪人，副教授，碩士生導(dǎo)師，主要研究方向電子系統(tǒng)集成技術(shù)。

Tel.:13067944675;E-mail.:sheng7@hdu.edu.cn

TP 273

A

1006-7167(2017)04-0029-04