「機器學習爆款App技術解讀」如何用「攝像頭秒解數獨」

【AI WORLD 2017世界人工智慧大會倒計時22天】

Magic Sudoku（魔法數獨）是一款基於蘋果 ARKit 的 iOS 應用，能夠「用攝像頭解開數獨」——用戶只需將攝像頭對準空白的數獨題目，拍攝一下，瞬間就能得到答案，對於那些被特別難的數獨題困擾的人來說，這無疑是一個超級救星。正所謂有了 Magic Sudoku，這個世界上沒有解不開的數獨。

儘管當前的 Magic Sudoku 只是一個 Demo，但已經引發了不小的轟動，不僅得到大量用戶的追捧，這款應用還登上了 Gizmodo、CNET 乃至《快公司》等媒體的版面。開發者 Brad Dwyer 表示，該應用程序使用了幾個神經網路，而解決每個數獨題的關鍵則是一個遞歸演算法。

下面，新智元編譯了 Dwyer 發表在 Medium 的文章，詳細介紹了他開發 Magic Sudoku 的經驗教訓。

核心要點：Magic Sudoku = Keras + Vision Lib + CoreML + ARKit

工作原理：計算機視覺+機器學習+AR

Magic Sudoku 結合了計算機視覺、機器學習和增強現實，總之，用手機對準數獨難題，App 就能工作。這個應用程序的基本流程是：

1）ARKit 從相機獲取新的幀；

2）使用 iOS 11 的 Vision Library 檢測圖像中的矩形；

3）如果找到矩形，確定它們是不是數獨；

4）如果發現是數獨，就將其分解成 81 個正方形的圖像；

5）每個正方形都通過訓練好的神經網路，確定它代表什麼數字（如果有的話）；

6）收集到足夠的數字以後，使用傳統的遞歸演算法來解決這個數獨題；

7）將表示解開謎題的 3D 模型傳回 ARKit，顯示在原始相機圖像的上面

所有這些在每秒鐘內都會運行好幾次。我不會太多地講解 ARKit，也不會大書特書數獨求解演算法或實際的機器學習模型，網上已經有很多關於這些的教程。

對我來說最有趣的，是我在訓練我的第一台機器學習演算法時學到的實際方面。因此，下文將著重這部分的內容。

機器學習實踐教訓：模型、數據、訓練和部署

首先，我學會了幾種失敗的方法

我選擇解數獨作為我們開發的第一款 AR 應用程序，其中一個原因是我知道對數字進行分類，基本上是機器學習中的「Hello world」。因此，作為機器學習試水項目，同時也解決現實世界問題，開發 App 解算數獨再適合不過。

在訓練模型前，我嘗試了一些策略，如果它們有用，接下來事情將會變得更容易。可惜，這些策略都沒起效。

我嘗試的第一件事是使用一個名為 SwiftOCR 的光學字元識別庫。在我這個用例中，使用 SwiftOCR 的問題是，這個庫是用於讀取字元串（如禮品卡代碼）的，而數獨是單個的數字。我也無法讓 SwiftOCR 區分「這是個空的方塊」和「我不能讀這個數字」。經過幾個小時的實驗後，它也沒有變得比隨機猜測數字好多少。

這並不是說 SwiftOCR 不好。實際上，這是一個很棒的庫，只是不適合用於這個特殊的問題。

然後，我轉而使用一個預訓練的 MNIST 模型，已經轉換適用 CoreML。使用預訓練模型很好很方便，實際上這也是我取得的第一個里程碑： .mlmodel 文件是完全自包含的，還對應 Swift 里的一個類，幾乎可以直接運行。

不幸的是，手寫數字數據集 MNIST 里的數字跟計算機字體相差還挺大，因此不太好泛化，我的第一個原型很容易出錯。

但是，到了這裡，我已經知道我走在正確的軌道上。我希望如果我使用從數獨題目里提取的現實世界數據來訓練我的機器學習模型，後者將變得更加準確和可靠。

數據收集：巧妙設計工具，利用群眾的力量標記數據

下一步就是收集儘可能多的數獨難題實例了。我去我們當地的半價書店，買了他們所有的數獨書。

我團隊的同事幫我把這些書拆開，我修改了原型應用程序，將其掃描的每個小方塊上傳到伺服器。從每本書中掃描出各種各樣的謎題後，伺服器上存儲了大約60萬張圖像，但是它們完全沒有標籤。

所以，我耍了個小花招：我做了個簡單的管理工具，讓我們在 Hatchings 的用戶幫助我們開發他們最喜歡的應用程序——通過按他們鍵盤上的數字鍵，對圖像進行分類。我們在 Facebook 上發布聲明後，不到 24 小時，所有 60 萬張圖片都標記完了！

但不幸的是，少數人誤解了這個任務，結果數據中摻雜了大量的標記錯誤的圖像。為了糾正這一點，我又做了第二個工具，顯示 100 張圖像（都應該是相同的數字），要求用戶單擊不匹配的圖像，然後將其重新分類到第一個工具中。

然後，我就有了足夠多的驗證數據，我在兩個工具中添加了一個自動精度檢查器，它會定期顯示用戶已知的圖像並檢查其工作，從而確定在多大程度上信任用戶分類的答案。

在接下來的幾個星期，我們的玩家分類了更多的掃描數據。當我們推出 Magic Sudoku App 時，系統已經接收了數百萬個數獨的數字圖像的訓練。

我使用這個數據集代替 MNIST 數據集，並在教程的指導下，使用 Keras 製作神經網路。結果比我預期的更好：精度 98.6％！在後續版本中，精度能夠提高到 99％ 以上。

使用現實世界數據來訓練

到那時候為止，我們從書店收集來的數獨語料庫工作都很好。我們沒有意識到的是，這只是世界上數獨汪洋大海的一小部分。

Magic Sudoku 發布後，我們立即開始收到 App 不能工作的報告。現在想來這簡直太正常不過——但當時我們居然真的沒有注意到！用戶想嘗試我們的應用程序能不能用，但手頭又沒有數獨題，因此他們就在谷歌搜索，然後拍照下來試試看。

我們的機器學習模型只使用了紙上的數獨題訓練；不知道如何處理屏幕上的像素。後來的一周，我都連續熬夜，用電腦屏幕的數據重新訓練模型。

問題二是蘋果的 ARKit 只支持水平面，比如桌子和地板（而不支持豎直面，比如顯示器）。解決這個問題比較棘手，但我確實提出了一個解決方案。我使用了啟發式函數和 FeaturePoint 檢測相結合，用來識別放在非水平面上的數獨題。

另一個意外問題是 ARKit 不會自動對焦（焦距是固定的）。在設備之間也有一些變化（在我的 iPhone 7 相機感測器上能運行，但 iPhone 6S 近距離對焦就不行了）。對此，我們的「修復」方法是，將模糊圖像添加到訓練集中。

我不知道是否能夠從這些圖像中挖掘有用的信息，我甚至看都看不清楚……但是，添加模糊圖像似乎並不影響模型的準確性！這樣，即使當圖像中的數字十分模糊的時候，當前版本的 Magic Sudoku 應用程序也能很好地運行。

上云：1200 美元自己打造機器，比 AWS GPU 更划算！

最後，最近很多關於亞馬遜 AWS GPU實例深度學習和谷歌雲深度學習產品的新聞，所以兩個我都用了一下。（我還嘗試了 FloydHub 的「Heroku 深度學習」平台）。

結論：有用，但很慢。我 2016 年的 Macbook Pro 運行 tensorflow-cpu 速度都勝過 AWS p2.xlarge GPU 實例。我懷疑訓練瓶頸是磁碟而不是計算。

上雲也很貴。根據我的計算，自己建一台機器回報不到兩個月，所以我花 1200 美元，在我父母的地下室自己攢了台規格普通的機器（這裡是表單 https://pcpartpicker.com/list/FRmGCy）。

運行我的數據集，我自己的機器比 AWS GPU 實例要快 3 倍，我相信應該很快就能收回成本。

下一步

我還是機器學習初學者，但是通過開發這款 Magic Sudoku 魔術數獨 App 讓我學到了很多。

接下來的幾個星期，我有一個很長的待修複列表，還要對當前功能集進行小幅改進。現在我已經解決了大部分問題與奇怪的字體、權重、填充和模糊的問題，下一步是改善我的啟發式函數，從而更好地識別數獨題。

如果題目的拼圖和紙張邊緣之間沒有太多的填充，或邊緣附近有文字，當前版本（v1.4）可能會遇到麻煩。所以，我接下來還要繼續嘗試。

我一直在收集正確對齊的數獨題和掃描得不好的數據集，我準備使用這些數據來訓練另一個神經網路，這個神經網路的作用是過濾掉壞的掃描數據。

再看遠一點，我們還計劃添加一些非常棒的功能。例如，我們想為已經完成的數獨題添加一個「checkr」功能。大部分的這些新功能都需要從計算機給出的數字中讀取和分離筆跡，因此我們收集了來自世界各地用戶的手寫樣本，準備訓練新的機器學習模型。歡迎你提供反饋！

原文地址：https://blog.prototypr.io/behind-the-magic-how-we-built-the-arkit-sudoku-solver-e586e5b685b0

【AI WORLD 2017世界人工智慧大會倒計時22天】

大會門票銷售火熱，搶票鏈接：http://www.huodongxing.com/event/2405852054900?td=4231978320026

【掃一掃或點擊閱讀原文搶購大會門票】

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！