基于SoC FPGA異構(gòu)平臺的魔方快速還原系統(tǒng)設(shè)計與實現(xiàn)

(湖北大學(xué) 物理與電子科學(xué)學(xué)院，武漢 430062)

0 引言

隨著科技的發(fā)展，各種自動化作業(yè)平臺在各行各業(yè)發(fā)揮著越來越重要的作用。我國對自動化智能平臺相關(guān)技術(shù)的研究投入也非常巨大。本文所研究的快速魔方還原系統(tǒng)正是自動化智能平臺的一個典型應(yīng)用場景。

該快速魔方還原系統(tǒng)基于SoC FPGA異構(gòu)平臺實現(xiàn)。其中SoC采用的是ARM處理器，它作為SoC中的佼佼者，兼顧性能、功耗、代碼密度、價格等多個方面，且第三方支持非常全面。而FPGA則以其設(shè)計靈活性和高并行著稱。在將FPGA和ARM核相結(jié)合后，可以實現(xiàn)非常高效的設(shè)計。本文快速魔方還原系統(tǒng)采用的硬件平臺是臺灣友晶公司提供的SoC FPGA異構(gòu)DE1-SoC開發(fā)板。該板卡提供了一個以Intelcyclone VSoC FPGA芯片建立的強(qiáng)大的硬件設(shè)計平臺，結(jié)合了嵌入式雙核Cortex-A9和業(yè)界領(lǐng)先的FPGA可編程邏輯。同時還包括了諸如高速DDR3內(nèi)存、ADC、以太網(wǎng)絡(luò)等豐富的功能外設(shè)。足以滿足快速魔方還原系統(tǒng)設(shè)計的需求，兼具高性能和低功耗[1]。

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

整個魔方還原系統(tǒng)由開發(fā)板、CCD攝像頭、魔方還原機(jī)械結(jié)構(gòu)以及VGA顯示器組成。開發(fā)板控制部分基于Intel SoC FPGA異構(gòu)框架，F(xiàn)PGA端和HPS端各自發(fā)揮所長[2]，分工協(xié)作，具體框圖如圖1所示。

圖1 系統(tǒng)框圖

在HPS端，分為以下4個步驟：

第1步，控制FPGA部分的圖像處理模塊和舵機(jī)轉(zhuǎn)動模塊，依次獲取魔方6個面的色塊中心區(qū)域的RGB均值。

第2步，調(diào)用顏色識別算法對魔方每個色塊的顏色進(jìn)行判斷，得出初始魔方。

第3步，調(diào)用魔方還原二階段算法，得出30步閾值以內(nèi)的魔方還原步驟。

第4步，將還原步驟轉(zhuǎn)換并編碼后，發(fā)送給FPGA端舵機(jī)轉(zhuǎn)動模塊。

在FPGA端，主要分為4個模塊：CCD攝像頭圖像采集模塊，圖像處理模塊，VGA顯示模塊，舵機(jī)控制模塊。

1.1 CCD圖像采集模塊

CCD攝像頭與CMOS攝像頭相比，在不管是強(qiáng)光還是弱光的不利條件下，圖像畫質(zhì)都要更高[3]。CCD攝像頭輸入的是模擬信號，需要經(jīng)過一系列的處理最終轉(zhuǎn)換成RGB圖像，整個圖像采集的過程如圖2所示。

圖2 圖像采集框圖

CCD攝像頭輸入的影像信號送至開發(fā)板上的電視譯碼芯片(ADV7180)，譯碼之后得到8 位 ITU_R BT.656標(biāo)準(zhǔn)接口的影像數(shù)據(jù)，然后送入FPGA芯片。在FPGA內(nèi)，先由ITU-R 656 譯碼模塊將亮度與彩度信號分解，再送入De-interlace模塊完成解交錯處理，接著送入Scaler模塊完成縮放處理，得到Y(jié)CbCr格式的圖像數(shù)據(jù)，然后進(jìn)入YCbCr2RGB模塊，轉(zhuǎn)換成 RGB值數(shù)據(jù)，再根據(jù)640*480像素VGA顯示需要的timing，將數(shù)字的RGB信號送出FPGA芯片，進(jìn)入開發(fā)板上的DA轉(zhuǎn)換芯片(ADV7123)，最終輸出三路模擬RGB信號到VGA顯示器。這樣，攝像頭拍攝到的畫面就實時顯示在了VGA顯示器上了。

1.2 圖像處理模塊

圖像采集模塊輸出的是一幀幀分辨率為 640*480 的 RGB 圖像，在此圖像處理模塊中，要做的處理分為三步，首先是要把一幀畫面中，魔方表面9個色塊的中心部分10*10 個像素點的RGB值存儲到 RAM 中[4]；然后從 RAM 中依次讀出每個色塊中心區(qū)域讀出 RGB 數(shù)據(jù)，求得R均值、G均值、B均值；最后將9組RGB值及當(dāng)前魔方面一起編碼后，傳送到 HPS端。

1.3 VGA顯示模塊

本設(shè)計采用VGA顯示器作為顯示終端，顯示的內(nèi)容分為兩部分，在VGA的左側(cè)，呈現(xiàn)的是CCD攝像頭實時獲取的畫面，右側(cè)則是繪制的魔方的展開平鋪圖。HPS端顏色識別的結(jié)果會顯示在魔方平鋪圖內(nèi)，用于人眼直觀判斷識別結(jié)果。此外，通過讀取ROM中存放的數(shù)據(jù),將湖北大學(xué)logo也顯示在里屏幕上，具體顯示效果如圖3所示。

圖3 VGA顯示方式

1.4 舵機(jī)控制模塊

本設(shè)計使用的魔方還原機(jī)械結(jié)構(gòu)主要由4個機(jī)械臂組成，若要機(jī)械臂穩(wěn)定快速的完成魔方面的旋轉(zhuǎn)，對總計8個舵機(jī)的同步控制尤為重要。本模塊的功能就是接收動作編碼，通過8個GPIO 端口，同步控制8個舵機(jī)轉(zhuǎn)動，完成機(jī)械手臂的旋轉(zhuǎn)伸縮。

2 FPGA與HPS之間的橋接

在Intel SoC FPGA的設(shè)計架構(gòu)里面，F(xiàn)PGA與HPS之間存在兩種通信方式，F(xiàn)PGAto SDRAM和AXIbridge接口。FPGAto SDRAM接口是HPS內(nèi)部的SDRAM控制器提供給FPGA訪問HPS內(nèi)存的接口。AXIbridge是FPGA和HPS總線間數(shù)據(jù)交互的接口，包括FPGA-to-HPS AXI、HPS-to-FPGA AXI和Light-weight HPS-to-FPGA AXI。

HPS向FPGA端需要傳輸?shù)臄?shù)據(jù)有控制指令、魔方還原步驟編碼，數(shù)據(jù)量較小，選用輕量級的HPS-to-FPGA AXI Bridge為傳輸通路；FPGA向HPS端僅需傳輸每個面9個色塊的中心區(qū)域的RGB均值，通過多組PIO傳輸即可。

3 關(guān)鍵算法

3.1 顏色識別算法

本設(shè)計需要做的顏色識別具有兩點特殊性：

1)讀入的數(shù)據(jù)是6個面，每個面9個色塊，總計54個色塊的中心區(qū)域100個像素點的R均值、G均值、B均值；

2)每個色塊的顏色只可能是紅橙黃綠藍(lán)白中的一種。

基于此，我們設(shè)計了如下簡單高效的顏色識別算法：

1)采集當(dāng)前環(huán)境下，還原后的魔方每個面的每個色塊的RGB值，存儲每種顏色的9組RGB值；

2)設(shè)置一個顏色判定值v=a*R+b*G+c*B，a、b、c初值均為-128，取值范圍從-128～128，變化步徑設(shè)為4。三重循環(huán)遍歷所有可能的a、b、c值組合，找到最合適的那組a、b、c值。使得某種顏色9個色塊的RGB值算得的v值接近，且遠(yuǎn)大于其余5種顏色的色塊的RGB值算得的v值。

3)依據(jù)2)得到的6組不同的a、b、c值，計算FPGA端傳過來的54組RGB的v值，依次找出每種顏色的9個色塊。

3.2 魔方還原算法

3.2.1 魔方的表示方法

采集到魔方狀態(tài)之后，我們需要用一種方式保存初始魔方狀態(tài)。魔方有8個腳塊，12個棱塊，魔方的擺放為：U藍(lán)色，F(xiàn)紅色，R黃色，L白色，B橙色，D綠色。本設(shè)計中用如下編碼存儲。

表1 角塊編碼

表2 棱塊編碼

對于每一個角塊，還需要一個參數(shù)來確定：順時針扭轉(zhuǎn)次數(shù)。如圖4，對于3個魔方前面右上角的的藍(lán)橙黃角塊，處于相同的位置，但是處于不同的扭轉(zhuǎn)狀態(tài)。若選擇頂面的藍(lán)色作為參考色，以頂面中心藍(lán)色塊為中心，第一個角塊的藍(lán)色塊已在頂面；第2個角塊可通過順時針扭轉(zhuǎn)1次，使藍(lán)色塊到達(dá)頂面；第3個角塊可通過順時針扭轉(zhuǎn)2次，使藍(lán)色塊到達(dá)頂面。分別用0，1，2表示。

圖4 3種不同的藍(lán)橙黃角塊

而對于棱塊，只有兩種可能，翻轉(zhuǎn)或者正常。如圖5，兩個魔方的前面上方的紅藍(lán)棱塊。第一個處于正確位置，用0表示，第2個通過翻轉(zhuǎn)之后可到正確位置，用1表示。

圖5 2種不同的紅藍(lán)棱塊

這樣，定義一個魔方的數(shù)組int MF[3][3][3][2][b][c]([第n行][第n列][第n層][編號或扭轉(zhuǎn)數(shù)][第b步][第c次循環(huán)])，用于保存魔方的狀態(tài)。

魔方有6個面，每個面存在3種操作(正對該面，順時針旋轉(zhuǎn)、逆時針旋轉(zhuǎn)、180度旋轉(zhuǎn))一共18種操作。本設(shè)計采用如下方式的簡稱：F=front face，前面；B=back face，后面；R=right face，右面；L=left face，左面；U=up face，上面；D=down face，下面。以前面F為例，順時針旋轉(zhuǎn)90°表示為[F]；逆時針旋轉(zhuǎn)90°表示為[F’]；180度旋轉(zhuǎn)表示為[F2]。后面則相應(yīng)為[B][B’][B2]，其余面依此類推。

3.2.2 二階段算法

本設(shè)計采用的魔方還原算法，是一種迭代加深啟發(fā)式的搜索算法(IDA*)。過程規(guī)則很簡單，沒有很復(fù)雜的狀態(tài)判斷，就只是重復(fù)循環(huán)：對每個階段的魔方不斷重復(fù)嘗試不同的旋轉(zhuǎn)，然后進(jìn)行判斷是否達(dá)到目標(biāo)狀態(tài)，如果沒有，則根據(jù)一個估價函數(shù)，選擇估價最低的操作繼續(xù)嘗試[5]。

因為魔方每一次的旋轉(zhuǎn)都有18種可能，如果每次都做18種嘗試，循環(huán)次數(shù)過于龐大。二階段算法正式為了解決這一問題，將魔方還原分為兩個階段，在第一階段需要用所有18種可能去嘗試，但是第二階段只需要用其中一部分可能轉(zhuǎn)法就確定可將魔方還原。

群是一種特殊的集合，對于一種操作，用它作用于一個集合的元素的時候，得到的結(jié)果還是這個集合里的元素時，這個集合對于某個操作構(gòu)成一個群。而魔方的所有狀態(tài)中就有著這樣的特殊集合，群[6]。對于一個未打亂的魔方，如果你使用R2、L2、F2、B2、U、U’、U2、D、D’、D2這10種轉(zhuǎn)法來轉(zhuǎn)動它，能生成的狀態(tài)僅是魔方所有可能狀態(tài)群中的一個子群。這個子群表示為 G1 = 。在這個子群中，角塊和棱塊的扭轉(zhuǎn)是不能被改變的。也就是說，當(dāng)一個棱塊或是角塊處在一個特定位置時，它的翻轉(zhuǎn)數(shù)和扭轉(zhuǎn)次數(shù)是一樣的，為0。同時，UD 夾層(U 層和 D 層中間的那一層，即中層 E)上的棱塊始終位于該夾層上。

在第一階段中，用所有18種可能的操作去作用于初始狀態(tài)，當(dāng)所有塊的翻轉(zhuǎn)數(shù)，扭轉(zhuǎn)數(shù)為0，且中間棱塊都在中間的時候，則到達(dá)G1群，第一階段完成。第二階段，僅用群的10種可能操作作用于此時狀態(tài)，直到所有塊的位置都正確，則魔方還原。

具體流程如圖6所示。

圖6 魔方還原算法流程圖

通過分析計算，第一階段最高12步還原，當(dāng)代價超過12步則舍棄后序操作，嘗試另一種操作。第二階段最高18步還原，當(dāng)代價超過18步則舍棄后序操作，嘗試另一種操作。算法第一次搜索出的結(jié)果一般很快，在30步之內(nèi)，然而，它不會馬上停止，而是繼續(xù)搜索，搜索還沒有嘗試的操作，如果所有操作都搜索完成，則改變預(yù)先的剪枝深度，比如第一階段為13步，雖然第一階段會提高步數(shù)，但是第二階段可能會減少許多步數(shù)，比如從原來的15步降低到8步，最終步數(shù)會進(jìn)一步減少。當(dāng)時間達(dá)到設(shè)定閾值，或者步數(shù)達(dá)到設(shè)定閾值的時候，算法停止工作，并輸出結(jié)果。

在具體代碼實現(xiàn)過程中，用如表3、表4對每一步的操作進(jìn)行編碼。

4 機(jī)械結(jié)構(gòu)設(shè)計

4.1 關(guān)于舵機(jī)

舵機(jī)由一個步進(jìn)電機(jī)、一個基準(zhǔn)電路以及其他的一些部件組成。信號線進(jìn)來不同的信號時會和基準(zhǔn)電路進(jìn)行比

表3 第一階段還原步驟編碼方式

表4 第二階段還原步驟編碼方式

較，從而來決定舵機(jī)的轉(zhuǎn)動方向。通過改變輸入脈沖信號的高電平時間即可控制舵機(jī)旋轉(zhuǎn)的角度。在一個周期為20 ms的脈沖里面高電平持續(xù)的時間決定了舵機(jī)轉(zhuǎn)動的角度，對于本設(shè)計中使用的180°舵機(jī)，對應(yīng)關(guān)系如表5。

表5 高電平脈沖時間和轉(zhuǎn)動度數(shù)關(guān)系

4.2 魔方還原機(jī)械機(jī)構(gòu)

本設(shè)計采用的魔方還原機(jī)械結(jié)構(gòu)由4個同樣的機(jī)械手臂，四面對稱擺放構(gòu)成[7]，單個機(jī)械手臂的結(jié)構(gòu)如圖7所示，一前一后裝有2個舵機(jī)。一個控制機(jī)械爪的伸縮，另一個控制機(jī)械爪的旋轉(zhuǎn)。整個魔方還原機(jī)械結(jié)構(gòu)的實物圖如圖8所示。

圖7 機(jī)械手臂結(jié)構(gòu)圖

圖8 魔方還原機(jī)械結(jié)構(gòu)實物圖

4.3 魔方還原動作設(shè)計

如第四章所述，魔方還原總計有18種不同的操作，但是我們的機(jī)械結(jié)構(gòu)只能做到前后左右面每個面的3種不同翻轉(zhuǎn)，總計12種不同操作。同時，若前后兩個動作分別是前面和后面或者左面和右面的操作，這兩個動作是可以同時執(zhí)行的。我們對所有可能的魔方操作進(jìn)行了如表6、表7、表8所示的編碼。

表6 單面旋轉(zhuǎn)方式編碼

表7 前后面同時旋轉(zhuǎn)方式編碼

表8 左右面同時旋轉(zhuǎn)方式編碼

對于機(jī)械結(jié)構(gòu)無法做到的U,U’,U2以及D,D’D2這6種操作，需要借助整體轉(zhuǎn)動魔方，轉(zhuǎn)換為可做到的12種操作，因此我們定義了表9中的魔方整體旋轉(zhuǎn)操作：

表9 魔方整體旋轉(zhuǎn)編碼

5 實驗結(jié)果與分析

根據(jù)上述分析，設(shè)計實現(xiàn)了魔方還原系統(tǒng)，如圖8所示。系統(tǒng)工作流程為，打開電源，4個方向的機(jī)械爪全部收回，置于機(jī)械結(jié)構(gòu)頂部的攝像頭開始工作；放入魔方，按下開始按鍵，機(jī)械爪首先夾緊魔方，然后整體轉(zhuǎn)動魔方，依次將6個面暴露在攝像頭下；攝像頭捕獲到的畫面?zhèn)魅隖PGA，一方面提取出色塊中心區(qū)域RGB均值送入HPS端，另一方面將畫面實時顯示在VGA顯示器上；HPS端執(zhí)行顏色識別程序，識別得到的完整魔方傳入魔方還原程序；還原步驟經(jīng)編碼后送回FPGA端的機(jī)械結(jié)構(gòu)控制模塊，最終由機(jī)械結(jié)構(gòu)完成對打亂魔方的復(fù)原；魔方還原完畢后，機(jī)械抓全部收回，魔方掉出。

為了驗證系統(tǒng)的性能，首先單獨測試了關(guān)鍵的顏色識別算法和魔方還原算法，然后對整套系統(tǒng)進(jìn)行了實際的魔方還原測試，具體測試結(jié)果如下。

5.1 顏色識別測試結(jié)果

基于系統(tǒng)實際工作的環(huán)境不同，而光照對于攝像頭圖像影響非常大，我們分別在光照良好的白天室內(nèi)、白光燈良好照明下的晚上室內(nèi)以及黃光燈良好照明下的晚上3種不同光照條件下，分別任意打亂魔方50次，調(diào)用顏色識別算法測試模塊檢測魔方所有色塊的顏色。得到如表10的識別結(jié)果。

表10 3種光照條件下的顏色識別測試結(jié)果

由此可見，系統(tǒng)設(shè)計的顏色識別算法，具有很好的適應(yīng)性。無論是在哪種光照條件下，識別正確率都在95%以上。

5.2 魔方還原算法測試結(jié)果

設(shè)定的步數(shù)閾值是30步，時間閾值是5秒。算法若在5秒內(nèi)找到30步以下的還原步驟就會結(jié)束搜索，返回結(jié)果，若時間超過5秒，則直接終止搜索，返回0。輸入100個不同的隨機(jī)打亂的三階魔方，得到還原時間的分布如圖9所示。

圖9 魔方還原算法求解時間分布圖

70%以上的情況，都可以在1 s內(nèi)得到30步以內(nèi)的正確還原步驟，平均還原步數(shù)為25步。HPS端系統(tǒng)主頻僅有800 M，算法無疑是非常高效的。

5.3 還原系統(tǒng)整體測試結(jié)果

為測試整套系統(tǒng)的穩(wěn)定性，進(jìn)行了100次打亂魔方的還原。每次還原結(jié)束后，記錄下結(jié)果，然后立刻隨機(jī)打亂后放入系統(tǒng)啟動還原。99次還原成功，僅在第92次還原時，因為前面累計的偏差，導(dǎo)致魔方順時針旋轉(zhuǎn)90°時，多轉(zhuǎn)了10°左右，魔方被轉(zhuǎn)亂，還原失敗。魔方采集6個面顏色，耗時都在3 s左右，求解時間平均在1.5 s，機(jī)械結(jié)構(gòu)還原時間分布如圖10所示。

圖10 機(jī)械結(jié)構(gòu)還原魔方耗時分布圖

99%的還原成功率，驗證了系統(tǒng)機(jī)械結(jié)構(gòu)的穩(wěn)定可靠。平均40 s的魔方還原時間，驗證了系統(tǒng)的高效，也讓我們見證了FPGA和SoC協(xié)同工作所能產(chǎn)生的神奇效力。

6 結(jié)束語

本文在采用FPGA和ARM核異構(gòu)平臺的基礎(chǔ)上，耗時3個月完成了快速魔方還原系統(tǒng)，該快速魔方還原系統(tǒng)由FPGA端實現(xiàn)攝像頭圖像采集和魔方色塊RGB值的獲取；HPS端完成顏色識別和魔方還原算法，再由FPGA實現(xiàn)對魔方還原機(jī)械結(jié)構(gòu)精準(zhǔn)快速的控制，從而完成實體魔方的還原。測試結(jié)果表明，該快速魔方還原系統(tǒng)能夠快速地還原魔方，充分驗證了SoC FPGA協(xié)同設(shè)計的高效。在未來，我們將進(jìn)一步發(fā)掘兩者各自的優(yōu)勢，實現(xiàn)更有價值的智能控制設(shè)計。