工程師開發魔術方塊破解器,鏡頭「看一眼」就能還原全步驟

【我們為什麼挑選這篇文章】魔術方塊可說是許多人的回憶,記得國中時,下課僅僅十分鐘的時間,許多男同學也不放過,硬聚在一起比賽誰解得比較快。隨著技術的發展,AI、機器人現在也能破解魔術方塊,速度甚至比人類更快,還有哪些新奇的解魔方方法?(責任編輯:賴佩萱)

本文經 AI 新媒體量子位(公眾號 ID:QbitAI)授權轉載,轉載請連繫出處
作者:量子位

魔術方塊解不開了怎麼辦,讓程式來幫你。

只需用攝影機把魔術方塊的六個面掃描一遍就能直接給出還原步驟。

即使你的魔術方塊不是標準配色或房間的照明情況特殊也可以透過顏色校準模式來識別。

這款荷蘭小哥發布的 3 階魔術方塊解算器「Qbr」已經在 GitHub 上開源。

GitHub 傳送門>>>https://github.com/kkoomen/qbr

小哥還貼心的把魔術方塊公式中的步驟代號翻譯為人話,並且支持中文,可以直接按照描述操作。

中文是小哥自學的,他還給自己起了個中文名叫「金可明」。

解算結果大概是這樣的:

攝影機幫你還原步驟,怎麼做到的?

使用 Qbr 需要你的電腦裝有 Python 3,Git 以及一個攝影機。

安裝方法如下:

運行時要注意每次運行前都要啟動虛擬環境。

操作也非常簡單,可以先按 L 鍵循環切換語言到中文,C 鍵進入/退出顏色校準模式。

掃描模式下按空格鍵保存識別好的一個面,6 個面都識別好之後按 esc 就可以在終端裡看到結果了。

如果需要將結果翻譯成「人話」,則運行時加入參數「-n」即可。

解魔方的演算法方面 Qbr 直接使用了開源的 Kociemba 演算法庫,該算法可以在 20 步以內還原任意 3 階魔方。

那麼問題來了,如何將攝影機掃描的圖像輸入給演算法呢?

鏡頭要如何辨識魔術方塊?

Qbr 使用開源的電腦視覺庫 OpenCV。

首先將圖像灰度化,稍微做一下模糊,然後用邊緣檢測識別出魔方小面的邊緣。

把所有邊緣加粗,使屬於一個邊緣的多條線可以合併。

將邊緣疊加到原始圖像上,使用 OpenCV 的 approxPolyDP 函數識別出閉合區域。

再去掉一些多餘的輪廓,就得到了魔術方塊的所有小面。

金可明在此基礎上改進了形狀檢測演算法,即使魔方小面帶有弧度、不是標準正方形也可以識別。

掃描好 6 個面後計算每個小面中顏色的平均值。

然後用 CIDE2000 演算法計算出每個小面屬於哪種標準色。

最後按順序將顏色寫程式合成為一個字符串就可以作為魔術方塊演算法的輸入了。

荷蘭工程師下一步想要做解魔方機器人

金可明出生於荷蘭,自學中文後來到中國留學。

除了 Qbr 外,他還寫過一個為程式碼自動生成文檔的 Vim 擴充軟體,並用文檔生成器(Documentation Generator)的英文字母開頭給擴充軟體命名為「Doge」,獲得 Github 500 星好評。

作為工程師的他看到這個擰魔方只需要不到 1 秒的機器人後決定自己也要做一個。

Jay Flatland 於 2016 年發布,0.9 秒的成績打破了世界紀錄

現在軟體部分寫好了,讓我們期待他何時能做出機器人吧。

參考資料

programmablebrick》、《youtube

(本文經 AI 新媒體量子位 授權轉載,並同意 TechOrange 編寫導讀與修訂標題,原文標題為 〈解魔方神器開源:攝像頭看一眼,就能還原全步驟 〉。)

看更多魔術方塊


點關鍵字看更多相關文章: