基于SoC FPGA異構平臺的魔方快速還原系統設計與實現

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

0 引言

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

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

1 系統設計

整個魔方還原系統由開發板、CCD攝像頭、魔方還原機械結構以及VGA顯示器組成。開發板控制部分基于Intel SoC FPGA異構框架，FPGA端和HPS端各自發揮所長[2]，分工協作，具體框圖如圖1所示。

圖1 系統框圖

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

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

第2步，調用顏色識別算法對魔方每個色塊的顏色進行判斷，得出初始魔方。

第3步，調用魔方還原二階段算法，得出30步閾值以內的魔方還原步驟。

第4步，將還原步驟轉換并編碼后，發送給FPGA端舵機轉動模塊。

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

1.1 CCD圖像采集模塊

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

圖2 圖像采集框圖

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

1.2 圖像處理模塊

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

1.3 VGA顯示模塊

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

圖3 VGA顯示方式

1.4 舵機控制模塊

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

2 FPGA與HPS之間的橋接

在Intel SoC FPGA的設計架構里面，FPGA與HPS之間存在兩種通信方式，FPGAto SDRAM和AXIbridge接口。FPGAto SDRAM接口是HPS內部的SDRAM控制器提供給FPGA訪問HPS內存的接口。AXIbridge是FPGA和HPS總線間數據交互的接口，包括FPGA-to-HPS AXI、HPS-to-FPGA AXI和Light-weight HPS-to-FPGA AXI。

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

3 關鍵算法

3.1 顏色識別算法

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

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

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

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

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

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

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

3.2 魔方還原算法

3.2.1 魔方的表示方法

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

表1 角塊編碼

表2 棱塊編碼

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

圖4 3種不同的藍橙黃角塊

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

圖5 2種不同的紅藍棱塊

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

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

3.2.2 二階段算法

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

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

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

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

具體流程如圖6所示。

圖6 魔方還原算法流程圖

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

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

4 機械結構設計

4.1 關于舵機

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

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

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

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

表5 高電平脈沖時間和轉動度數關系

4.2 魔方還原機械機構

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

圖7 機械手臂結構圖

圖8 魔方還原機械結構實物圖

4.3 魔方還原動作設計

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

表6 單面旋轉方式編碼

表7 前后面同時旋轉方式編碼

表8 左右面同時旋轉方式編碼

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

表9 魔方整體旋轉編碼

5 實驗結果與分析

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

為了驗證系統的性能，首先單獨測試了關鍵的顏色識別算法和魔方還原算法，然后對整套系統進行了實際的魔方還原測試，具體測試結果如下。

5.1 顏色識別測試結果

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

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

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

5.2 魔方還原算法測試結果

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

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

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

5.3 還原系統整體測試結果

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

圖10 機械結構還原魔方耗時分布圖

99%的還原成功率，驗證了系統機械結構的穩定可靠。平均40 s的魔方還原時間，驗證了系統的高效，也讓我們見證了FPGA和SoC協同工作所能產生的神奇效力。

6 結束語

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