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

盛庆华， 杜永均， 罗 飞， 李辰龙， 何 凯

(杭州电子科技大学 a.电子信息学院； b.自动化学院，杭州 310018)

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

盛庆华a， 杜永均b， 罗 飞a， 李辰龙a， 何 凯b

(杭州电子科技大学 a.电子信息学院； b.自动化学院，杭州 310018)

针对双手臂智能机器人复原魔方这一难题，设计了一套快速解魔方系统。该系统由图像采集、图像处理和机械臂控制三部分组成。首先，利用android手机中的DroidCam软件采集魔方图像并将该图像信息传送至PC端；然后，通过LabVIEW软件提供的库函数对图像进行分析和识别，并将结果发送给STM32处理器；最后，通过层先法得到复原魔方的步骤并控制2个机械臂复原魔方。实验结果表明,本系统可智能恢复任意打乱的魔方，并且执行过程控制较为简单，性能稳定可靠。

复原魔方； 图像识别； 层先法

0 引 言

智能机器人复原魔方作为娱乐科普机器人是当今的一个研究热点，其能很好地代替人来复原复杂的魔方。本系统利用LabVIEW软件完成对魔方图像的识别[1]，IMAQ提取魔方图像[2]；然后通过腐蚀用二值算法提取色块RGB值[3]，再通过阈值识别魔方颜色。复原魔方采用了方便易懂易于实现的层先行魔方算法来获得魔方旋转步骤，然后通过算法将魔方复原步骤转换成双手臂的动作步骤来完成魔方的复原[4]。

文中的还原魔方机器人采用了类人型的双机械臂，可观赏性高，研究价值大，但执行机构控制上难度也更大。另外图像识别采用的方案也简单易行、经济，借用了智能手机摄像头作为采集图像信息。由于大多数人都有智能手机，从某种意义来说，可以节约开发成本，使用了LabVIEW软件来分析处理图像，灵活、方便。

1 系统总体设计

系统利用软件DroidCam将上位机PC和android手机通过WiFi相连接构成局域网，将手机上的摄像头实时采集到的数据传输到PC，再通过LabVIEW提供的视觉助手LabVIEW VISION ASSISTANT来处理分析图像数据[5-6]，识别魔方6个面的各个颜色信息，再利用LabVIEW提供的串口控制函数，将处理好的魔方色块信息发送给下位机STM32[7]；STM32通过串口接收到一个完整魔方的各个面颜色的信息后，再用层先法还原魔方算法函数，得到相应的复原魔方的旋转步骤，再调用复原魔方的动作函数，控制机械臂把任意打乱的魔方复原。整个系统的总体构图如图1所示，机械臂的实物图如图2所示。

图1 系统的总体框图

图2 机械臂实物图

2 软件设计

2.1 图像采集系统

2.1.1 图像采集方案论证

方案1 利用单片机结合CMOS摄像头做颜色识别[8]。优点：成本低，体积小，使用方便。缺点：对图像提取，颜色分辨算法要求较高，摄像头像素较低，受光线干扰大，不能很好地识别魔方各个色块。

方案2 利用LabVIEW上位机结合手机摄像头做颜色识别。优点：图像提取，颜色识别算法由上位机提供，方便可靠，手机摄像头清晰度高，可以有效的识别魔方各个色块。缺点：需要配备电脑联机使用，使用相对不方便。综上比较，选择方案2。

2.1.2 图像采集流程

打开手机中已安装的DroidCam并和PC通过WiFi相连接，在LabVIEW中，创建IMAQ，通过索引打开摄像头并配置连续采集，在循环中每隔40 ms采集1帧图像，最后关闭摄像头。经过检测魔方色块边缘后，腐蚀图像去除杂点，从而得到色块的位置，最后对颜色的RGB值进行匹配，确定色块颜色，最后根据NI-VISA提供的串口控制函数把信息传给下位机[9]。图像采集流程图如图3所示。

图3 图像采集流程图

2.2 魔方还原算法

2.2.1 魔方还原算法

方案1 CFOP法。实现过程如下：底层十字、同时对好前两层、调整好最后一层的朝向、调整好最后一层的顺序。此方法使用了119个公式，分为4个步骤复原魔方，使得魔方复原的最好成绩突破了6 s大关。

方案2 层先法。将魔方分为底层、中层、顶层分层复原。用层先法复原魔方一共分7步：底层十字、调整底面角块、复原中层棱块、顶面十字、顶角归位、调整顶角位置、调整顶棱的位置。按照这7步走，配合几个固定的简单公式，魔方就可以成功复原。

分析：方案1在速度上较快，但是公式繁多，对于写代码比较复杂，不易实现；方案2的特点在于不用像CFOP方法那样需要大量的公式，而是只用几个简单的公式就可以完成，代码实现相对容易，而且较为容易理解。最终选择方案2。

2.2.2 魔方抽象模型和复原魔方理论基础[10-11]

(1) 魔方特性。魔方有6个中心方块并且颜色固定不会随旋转而改变，6种颜色，12个棱块，8个角块。魔方展开数值表示如图4所示。

图4 魔方展开数值表示图

(2) 定理[12]。对于复原状态下的魔方实施任意的转动序列，打乱之后的魔方，存在一定的转动序列使得魔方变为以下4种基本情况：①仅有三棱置换；②仅有三角置换；③仅有两棱反转；④仅有两角扭转，且扭转方向不同。

(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) 复原魔方的状态表示：

(3)

(7) 数学群论[13]。

①定义：设集合M={1，2，…，n},并把M的经过某一个置换后的集合记为Mi，其中i=1,2,…,n。若M的1个置换满足：∂(M1)=M2，∂(M2)=M3，∂(Mj-1)=Mj其中，该置换周期记为j的循环，记为(M1,M2,…,Mj)。如果2个循环(M1,M2,…,Mj)，(Mk+1,Mk+2,…,Mk+j)它们没有公共的集合Mi，也就是没有相交状态，那么这两个循环不相交。

②根据以上定义，魔方的群生成元用循环形式表示：

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)

③例如，转动魔方的右面90°的情况表示：

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

(8) 魔方复原过程。当研究某个转动序列的周期性和循环特点，只需要根据数学群论的置换乘法规则，再利用数学群论的生成元基本公式就可以得出周期性规律，所以根据某些策略就可以把打乱的魔方转化成定理中的几种特殊情况，然后再研究对应特殊情况下还原魔方的转动序列，那么魔方就可以复原。

A.算过程：①根据层先法策略过程，先找出当前某块应该放的颜色块；②遍历当前整个魔方的颜色状况，找到那个颜色块对应的位置；③根据它所在的位置信息，调用层先行所封装好的那几个对应函数，同时记录下还原的旋转面及方向的步骤信息。

B.根据所得到的旋转面及方向，再调用各个面旋转的函数，把魔方的当前颜色位置信息，按照还原公式得到的还原步骤改变。

执行完了，再开始以上A、B步骤，如此重复，直到整个魔方还原。层先行程序流程图如图5所示。

图5 程序流程图

3 系统硬件及控制

3.1 系统硬件组成

参考马江[14]对6自由度机器臂构型的选择，通过改进，本系统采用4自由度的双机械手，8个LD-3015MG数字舵机[15]，270°定位，17 kg扭力。系统还采用了STM32F103RCT6芯片，TFT彩屏，PC以及android手机等。

3.2 机械臂的执行过程

由于采用的是类人型的两只机械臂，就必然会要有1只手固定，另1只手动作，为了避免在旋转不同面时，2只手出现太多的冗余切换动作，采用了一种创新的办法。即：①根据还原步骤，获得当前旋转色块的颜色值并给PresentFaceVal，机械臂1以上黄下白面的中心垂线为旋转轴(另一只机械臂为机械臂2)切换红绿橙蓝的旋转面。②若旋转面为红绿橙蓝中的一个，则计算当前旋转面PresentFaceVal与LastFaceVal上一次旋转面之间的颜色数值差，来判断两个面之间的相对空间位置，进而确定机械臂1对魔方的切换面的操作动作；③若旋转面为白色，可以直接让机械臂1抓白色面旋转；④若旋转面为黄色，用机械臂2先将魔方以蓝绿面或红橙面为轴旋转180°，此时黄色面由机械臂1直接抓住进行旋转，旋转完面后使魔方回到初始状态(即上黄下白的状态)。⑤每次旋转结束后，更新上一旋转面信息LastFaceVal=PresentFaceVal，便于下个旋转面的控制。⑥重复①～⑤的步骤直到机械臂最终按照还原步骤执行结束。

3.3 机械臂动作原理流程图

机械臂动作原理流程图如图6所示。

图6 机械臂动作原理流程图

4 结 语

本系统设计并实现了一个基于STM32F103RCT6的可以复原一个任意打乱顺序的三阶魔方的机器人。一般的魔方复原机器人的结构是4个或者6个机械臂，作为执行机构，冗余复杂，不太具有观赏性。本系统富有挑战性地采用了2个4自由度的类人机械臂，可以较灵活地复原一个三阶魔方，准确、清晰地再现了人复原魔方的步骤，项目具有一定的创新性和趣味性。但因实验室条件限制，机械臂工艺的粗糙，在以机械臂为执行机构工作时，对于一些动作执行精度并不能达到要求，其机械工艺可以进一步改进。在由复原魔方的步骤转化成机械臂的执行步骤的过程中，也可以在实践过程中进一步优化代码，减少冗余动作，加快复原魔方速度。

[1] 陈树学. LabVIEW实用工具详解[M]. 北京：电子工业出版社，2014：316-339.

[2] 丁 晟，蒋晓瑜，汪 熙. 基于LabVIEW的图像处理技术研究[J]. 微计算机信息，2010，26(29)：204-205.

[3] 张 琪. 结合边缘检测的图像二值化算法[D]. 吉林：吉林大学，2011.

[4] 梁小龙. 解魔方算法的研究和系统实现[D]. 沈阳：东北大学，2011.

[5] 田 田，徐 林，赵洪华，等. 解魔方四爪机械手结构设计与操作[J]. 机器人技术与应用，2014(5)：38-39.

[6] 张雨田. 基于LabVIEW 的魔方机器人系统设计[J]. 数字技术与应用，2014(12)：136-137.

[7] 刘 军, 张 洋, 严汉宇. 例说STM32[M]. 2版.北京：北京航空航天大学出版社，2014：107-115.

[8] 刘政林，周 铭，刘欣达，等. 基于计算机视觉的塑料瓶颜色识别和分拣系统[J]. 电子测量技术，2013，36(11)：43-48.

[9] 吴 伟. 基于VISA的仪器通信技术的研究与实现[D]. 西安：西安科技大学，2009.

[10] 胡 鑫. 基于ARM9的嵌入式魔方机器人系统设计[D]. 广州：华南理工大学，2011.

[11] 郑 瑜. 魔方原理及其应用[D]. 杭州：浙江大学应用数学系，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] 孙雨耕，俎云霄. 群图的基本理论及置换群图的构造[J]. 天津大学学报(自然科学与工程技术版)，2000，33(2)：129-133.

[14] 马 江. 6自由度机械臂控制系统设计与运动学仿真[D].北京：北京工业大学，2009.

[15] 纪海彬. 基于AVR的解三阶魔方机器人研究[D].长春：长春理工大学，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

浙江省大学生新苗计划(2016R407024)；杭州电子科技大学校级大学生创新创业项目(XJ201411)

盛庆华(1978-)，男，浙江兰溪人，副教授，硕士生导师，主要研究方向电子系统集成技术。

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

TP 273

A

1006-7167(2017)04-0029-04