魔方教学系统（基于QT）_qt 魔方还原助手

之前没能及时复盘写下来 现在很多想不起来，慢慢回忆着写吧

背景

之前指导本科生做的伺服电机的机械臂解魔方机器人，老师提出能不能低成本化，就尝试了舵机和低价相机，外边做成黑色壳子阻绝光线的方法。最终把伺服电机机械臂替换成了两个舵机和转动平台组成的执行机构，四个相机减到一个相机，实现的效果很成功。然后因为计算机解魔方有个特点，可以从一种状态解算的任何另一种状态，所以又衍生出了用魔方机器人教学的想法。通过把打乱的魔方交给魔方机器人，造出指定的场景，从而达到反复训练的目的。

系统组成

下位机是一块STM32的板卡，用来控制舵机，操作相机抓图，把魔方的角块和颜色编码后通过串口传给上位机。上位机直接就是笔记本电脑，用QT写的完整GUI界面，包括解魔方教学步骤的图片和视频，对应的要机器人还原的指定状态的选择。确定后再传回下位机控制舵机完成还原操作。
由于这套系统还在跟公司合作，以后可能会商业化，所以不能在这里放内部结构图和完整代码，有之前伺服电机解魔方机器人的图，放一些示意一下。

学习到的技术

• 颜色识别

颜色识别采用OpenCV实现。因为魔方位置和相机位置基本固定，先采用OpenCV的图像标定函数，标定出各个角块的坐标点，然后采用HSV颜色模型来识别颜色。之所以不用RGB颜色模型也是考虑到外界环境可能出现的光照等原因对颜色识别造成的误差。

在魔方拍摄与识别这一问题中只需要考虑其中的H 值与S 值即可，显然明度的问题并不会影响到本文的颜色识别，而且它最大的优点在于可以一定程度上削弱光照条件对识别结果的影响，这样可以大大地提高本文的识别效果。当然，忽略V 值的影响虽然不会在程序中影响到最终的识别情况，但是需要指出光照条件的变化H 值与S 值是会产生较大变化的，并不存在使用了HSV 模型就可以忽略光照条件的影响。

先把魔方还原，对每一个摄像头进行标定。单独启动每一个摄像头拍摄基准照片，根据拍摄的照片在其上用鼠标选择取色基准点。完成每一个摄像头的标定后开始编写程序，将每一个摄像头的每一个取色基准点的横纵坐标值输入，并同时取该点周围的8个其他像素点，读入9个点的数据计算平均值，将得到的平均值作为最终的输出结果。

因为本文的魔方有一种颜色是白色的，那本文大可以单独考虑S 值来区分这一颜色。通过对白色的面进行大量地拍摄和识别发现，白色的小块几乎不会出现S 值超过70的情况，所以将S 上的阈值设置在70，只要是S 值低于70时，则将其认为是白色。虽然看起来这样的判定方法是有些单纯的，但它的实际效果并不差，白色的识别准确率在作者的实验中是最高的，在36次的实验中白色小块没有一次被识别错误的。

对于其他的五种颜色作者则都在H 值上进行划分。通过大量的拍摄图像识别的情况来看，在白天的实验室内，保持一个相对恒定的光照条件时，以下的阈值设置效果较好，如果出现因为阈值不当而导致的识别出错问题则应该根据实际情况对阈值进行调整（实际情况来看这种操作也是比较有必要的，在上午、正午、傍晚时的阈值都需要进行一定的微调，尤其是红色的上限值和橙色的下限值，在夜晚没有外界自然光只有室内日光灯和机器补光灯的条件下往往需要对阈值进行较大的调整）。将红色的阈值设置为H 值大于等于0且小于7，而橙色的阈值为大于等于7且小于33，将黄色的阈值设置为大于等于33且小于51，将绿色的阈值设置为大于等于51且小于80，将蓝色的阈值设置为大于等于80且小于130，将大于等于130且小于180的部分判定为红色（这种情况是极少出现的）。

• 解法实现

人为地解魔方的方法有很多种，例如较为常见的有层先法和CFOP 法，这两种方法具有一个极大的优势就是它们更容易形成让人很快就能记住的解魔方的公式，即使是一个完全没有接触过三阶魔方的普通人，也能很快地学会层先法解魔方的公式。

而计算机的解魔方算法就有很多种了，因为计算机是不需要考虑公式和可记忆性问题的，也不需要考虑是否会花费大量的时间去计算复杂的数学问题，只要算法在数学原理上没有错误，编写成对应的程序就能完成解魔方的任务。目前已经被开发的较为完善的有二阶段算法、Thistlethwaite 算法、Jaap Scherphuis 算法等等。其中有的算法可能会检索出最小还原路径但牺牲的是求解的时间，有的可能求解极为迅速但可能其求解出的步骤会较多。单纯如果为此次的智能机器人创意大赛中的解魔方项目取得好成绩考虑的话，采用二阶段算法或Thistlethwaite 算法是较为合适的，因为它们能求解获得一个步骤不那么多的还原路径，并且求解的速度相对较快，是两种在速度和步骤数量上比较均衡的算法。

本文解魔方算法使用Thistlethwaite 算法。

魔方解算步骤的编码

三阶魔方具有6个颜色完全不同的面，每个面都有9个小色块。本文将这9个色块都按照第一行为1,2,3号，第二行为4,5,6号，第三行为7,8,9号进行编号，在旋转魔方时魔方本身的一个特点就是：每一个面最中间的那个5号色块是并不会转动的。因此只要保持魔方本身的姿态不变化，让某一个颜色的色块一直朝向某一个方向，就可以用一组字母来描述每个面。本文定义了U（up）、D（down）、L（left）、R（right）、F（front）、B（behind） 这几个字母来描述6个面，同时本文规定，对于一个标准三阶魔方其U 面为黄色，D 面为白色，L 面为橙色，R 面为红色，F 面为蓝色，B 面为绿色。至此，本文已经完成了对魔方每个面的定义，每一个魔方只要通过这种摆放姿势摆放，给出的一个还原路径的执行方式就唯一。
在规定了面的名称后再对面的旋转进行规定。显然每个面都只能顺、逆时针旋转90度和旋转180度，本文将其定义为“1”，“3”，“2”三个数字。需要注意的是，这里的“顺时针”和“逆时针”是指当你面向这个面时的顺时针和逆时针。举个例子，将一个魔方的F 面朝向你的脸，此时的F 面顺时针旋转90度就是将1号色块转到3号色块的位置这样旋转，而此时的B 面顺时针旋转则需要你将魔方的B 面朝向你的脸，然后将1号色块转到3号色块位置这样旋转。
通过对面的名称和旋转的规定，本文得到了U、D、L、R、F、B 六个字母和1、3、2这三个数字，将其组合就得到了F1、U2、D3等等这样的组合，这种组合形成的一系列旋转动作就是本文的还原路径了。例如F1 U2 D3 R3 U2 L1 U1这个还原路径，很显然，如果你将F 面面朝自己，这个还原路径将变成一个唯一的动作。

Thistlethwaite 算法是由Morwen B. Thistlethwaite 这位数学家设计并以他的名字进行命名的一种计算机解魔方算法[11]，整个解魔方的算法分为4个阶段，每个阶段完成一些工作来限制小块的位置，当魔方的每一个小块都只剩下一个可能的位置时就完成了魔方的还原了[6]。
使用这种算法可以得到一种步骤极少的还原魔方的路径，但是由于其四个还原步骤都相当的复杂，并且需要大量的参考表（公式），作为一个普通的人类是完全无法使用这种方法来解魔方的，因为它的参考表（公式）多到根本无法记忆（仅仅第一个还原阶段的位置数量就多达4.33*10 19种）。
对于这个算法的四个步骤做以下的简单描述：
第一步，先进行几步旋转来使得魔方的状态变成不使用U1、U3、D1和D3这四种动作就可以完成复原的状态。这个过程通常需要不超过十步来完成。
第二步，再将魔方的状态调整到不需要F1、F3、B1和B3这四种动作就可以完成复原的状态。这个过程的步骤数量或多或少，最多可能会出现十几步。
第三步，将魔方调整到只需要F2、B2、L2、R2、U2和D2动作就能完成复原的状态。这个过程所需要的步骤数量也是不确定的，要根据魔方的实际状态来看。通常情况下也是需要十几步的。
第四步，只使用F2、B2、L2、R2、U2和D2动作完成最后的调整，让所有小块可能出现的位置都变成唯一位置，完成魔方的复原。
整个过程看起来似乎并不是很难，简单来说就是在逐次地限制小块的位置可能性，让小块可能存在的位置数量越来越少，先限制U 面和D 面的小块，再限制F 面和B 面的小块，最后限制L 面和R 面的小块，当完成全部限制后，在U 面和D 面都只会存在有两种颜色的小块，F 面和B 面以及L 面和R 面也是如此，然后就可以通过F2、B2、L2、R2、U2 和D2 动作就能完成还原了。但是实际上执行这四个步骤时所需要花费的计算量是极为庞大的，下面的这张表格中显示的就是执行四个步骤时需要的一些数据量。

从数学的角度上来看，它实际上是一个嵌套组的序列，算法的每一个阶段都是一张查找表，用来寻找到商陪集空间中每一个元素的解。而最后一列中显示的就是这个陪集空间的顺序，也就是每一个阶段的查找表的大小。至于这个因子数量的计算公式，这和这种算法在限制不同面的小块时是如何限制的有关。[6]具体的一些数学原理就非常深奥了，涉及到太多作者并没有接触过的更为高深和专业数学知识，在此就不多做分析和讨论了。
在第一阶段时，目标是限制U 面与D 面都只能采用U2和D2的动作来进行后续的调整，其实它所做的工作在魔方层面来看就是修正魔方的棱块的方向，因为要求U 面与D 面都只能转半圈而不能转四分之一圈，所以就决定了是不可能再调整四边棱块的了，通过这种限制就可以完成将四边棱块限制在一个完全正确的位置上。
在第二阶段时，目标是在第一阶段的基础上开始限制F 面与B 面的小块。如果要求在F、B、U 和D 面都只能使用半圈的旋转方式而不能使用四分之一圈的旋转方式，那么这阶段就可以完成对于八个角块的位置确定，并对这八个角块的方向进行确定，让角块和第一阶段确定的棱块完成正确的拼接。在完成第二阶段后，八个角块和四个棱块都会进入位置确定，角块方向不定的一种状态，但即使是方向不定但因为魔方本身的结果和角块的颜色，它们依然会受到移动限制。
在第三阶段，开始限制剩下的L 面与R 面的小块，目的是完成对所有面上小块的限制，让每一个面都只有“相对颜色”（例如F 面为蓝色，B 面为绿色，则在完成第三阶段后，F 面和B 面都只会存在蓝色与绿色两种颜色，绝不会出现其他的4种颜色在这两个面中）。在此种状态下，所有的角块和棱块都已经进入了正确的位置，只需要在进行U2、D2、F2、B2、L2和R2这六种动作就能将魔方彻底地复原。
第四个阶段就是只使用旋转半圈的六种动作将魔方彻底地复原。
很显然这个算法的搜索方法看起来很美好，但它使用的查找表实在是太大了，及时是计算机直接去运行也会有不小的计算压力，所以就需要想办法来缩小这个检查表。为了减小这个检查表，Tistlethwaite 尝试简化了初始的这种搜索方法，这也是为什么有时他需要的实际还原步骤是比这个商空间的“直径”（搜索出的最佳的还原路径）要多一些的原因。在之后他的一些学生针对这个问题进行了更深层次的研究，他们对这些嵌套组进行了完整的分析，然后改进了算法，让搜索出的最佳还原路径降低到五十步。再随后，他们继续研究了每一个阶段的搜索算法，对每一个阶段的搜索算法又进行了全面而深入的分析，将最佳还原路径降低到了45步。再之后又有一名叫做Hans Kloosterman 的人继续改进了第三阶段和第四节段的算法，成功将最佳还原路径的步骤降低到了42步，这个42步被实现的时间是在1991年[6]。再之后计算机的运算能力开始大幅度提高，借助运算性能更强的计算机，数学家Mike Reid 通过更复杂的数学分析得出的结论是从第一阶段到第二阶段理论上需要12步即可完成，第三阶段和第四阶段理论上需要18步即可完成，将其组合起来后理论上30步之内就可以完成用这种算法来求解任何一个打乱的三阶魔方。

• 全局变量的使用

当时对面向对象理解不深刻，魔方的状态，因为在魔方解算里也用到，在串口通讯时也要用到，就定义成了全局变量。也顺便记录一下用全局变量的方法：

 extern char color_sides[6][9];
1

在头文件通过extern 声明全局变量，其他地方需要使用时，只需include进相应的头文件即可

但C++不提倡使用全局变量
因为全局变量bai容易导致代码的可复用性下降，以及对象管理的困难。
试想，如果某个类使用了全局变量，则移植该类的时候，必须将全局变量也一起移植。更可怕的是，如果这个全局变量还是一个对象，并且初始化也在不同的类中实现，那么所有这些代码将被永久捆绑在一起，无法分离了。任何一个与此全局变量相关联的代码一旦有改动，即可对其他使用该变量的代码产生不可预知的影响。

影响函数的封装性能：我们肯定是希望我们写的函数具有重入性，就如一个黑盒子一般，只 通过函数参数就能得到返回，内部 实现要独立，但是如果函数中使用了全局变量，这势必就破坏了函数的封装性，会造成对全局变量的依赖。

1 全局变量是很好。
2 但是有缺点：容易被修改错，尤其在工程很大的时候。
3 使用时一定要控制好全局变量的修改。
4 不过小工程小项目使用全局变量是很方便的！
1.全局变量在程序执行过程中一直占用存储单元，耗费空间。
2.使函数的通用性、移植性降低了，耦合性变强了。
3.使程序的可读性降低，难以判断全局变量在一定时刻的具体值。

重新构建你的数据结构，把公有数据成员抽离出来，单独做成模块，提供一个接口对其操作。
如果确实有大量数据需要共享的话，建议还是用单独的类封装一下。其实类的使用，个人认为主要还是逻辑上清晰为第一原则

• 播放器

因为要演示解魔方教学视频，所以用QT写了一个播放器。实现的功能主要有播放本地视频，暂停，进度条拖动。
用到的QT库：
QMediaplayer：用于解析音频文件和视频文件。
使用QMediaplayer，除了需要添加必要的头文件之外，还需要在.pro(Qt的工程配置文件)添加QT += multimedia。下面解析有关QMediaplayer的相关知识。
QMediaPlayer播放视频要在界面上显示出来，还需要其他类进行辅助，比如QVideoWidget。

QVideoWidget：QVideoWidget继承自QWidget，所有它可以作为一个普通窗口部件进行显示，也可以嵌入到其他窗口。将QVideoWidget指定为QMediaPlayer的视频输出窗口后，就可以显示播放的视频画面。

如果播放无图像，并报错：

DirectShowPlayerService::doRender: Unresolved error code 80040266
1

原因：
Qt 中的多媒体播放，底层是使用DirectShowPlayerService，所以安装一个DirectShow解码器，例如LAV Filters，就可以解决运行出错问题

另外为了实现进度条拖动跳转功能，又用QSlider和事件过滤器单独写了个进度条组件加到下面。通过信号槽与播放器连接，一旦拖动进度条释放鼠标后就发出信号量，播放器里接收，通过player->setpostion设定进度。

串口通讯
也用了QT库。网上很多相关写法，就不再赘述了。
#include
#include
记得配置文件.pro里要加QT += serialport

有个需要注意的地方，因为传回来的魔方数据较长，在触发串口接收函数后，要先加上：

while (m_serialPort->waitForReadyRead(500));
1

延时等待一会儿，不然会出现数据不全的情况。

• 线程

因为解魔方算法需要一定时间，所以给它专门开个线程处理。
注意几个点：
线程处理函数里不能操作图形界面，需要操作，要发信号量出来，在主线程里操作。
线程不能指定父对象，关窗口时记得delete

QT的线程真的很简便：

t = new QThread(this);
solve = new Solution;
solve->moveToThread(t);
t->start();
1
2
3
4

这就完成了，只要Solution类也继承自QObject即可。
记得析构的时候，把线程退出，并且delete掉。

• 互斥锁

因为有时候识别有错误，会出现解不出来的情况，所以需要定时检测算法有没有结果。本来想直接写个标志位解决，但有个问题，可能查查看的时候，刚好那边在写，而且也分处两个不同的线程，所以想到加个互斥锁解决。

在Qt的多线程控制中，互斥量的访问最简单的控制是添加一个mutex锁，对一个函数或者变量锁定。

如果QMutex::lock()得不到这个锁，那么它将会一直等直到得到该锁为止，而另一个方法QMutex::tryLock()可以检测当前是否可以得到这个锁，如果可以得到则返回1，否则返回0（不会一直等，但如果可以得到锁，那就拿到锁，不会光判断而不获取锁），该函数只执行一次，不会一直等到得到锁为止。

最后就是设计模式的探讨，不然情景选择按键下全是switch，这个之后再补充。

相关代码因为项目还在进行中，而且将来要商业化，所以不能放上来了。

总结

通过这次又对QT熟悉一点，开发更加迅速，而且也算把师弟领进门了。这个项目本身也很有趣，开发的过程中能够乐在其中，并且也很有挑战性，最后慢慢解出魔方，速度越来越快，真是感觉一切都值了。

参考文献：
http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=38810
https://www.cnblogs.com/sixbeauty/p/3790693.html
https://www.cnblogs.com/dupengcheng/p/7205527.html
https://blog.csdn.net/qq_36969386/article/details/85072605