【机器学习爆款App技术解读】如何用“摄像头秒解数独”

【新智元导读】最近一款名叫 Magic Sudoku(魔法数独)的 App 火了,这款 App 能够“用摄像头解数独”,使用了计算机视觉、机器学习和增强现实技术,具体说,是 Keras + Vision Lib + CoreML + ARKit。本文是开发者 Brad Dwyer 的技术解读,分享了他在项目实践中,构建模型、收集数据等的经验和技巧。

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_era)

原文发表时间:2017-10-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏磐创AI技术团队的专栏

推荐 | 7个你最应该知道的机器学习相关github项目

来源 | Analytics Vidhya 编译 | 磐石 出品 | 磐创AI技术团队 磐创AI导读:本文介绍了github上最近比较火的7个机器学习项目,每...

37440
来自专栏AI星球

我与Python--从Hacker到探索Deep Learning

进入大学之后,我们逐渐“被教授”了C、C++、Java等编程语言,但为什么我会选择python作为最喜欢的编程语言呢?

14630
来自专栏AI科技评论

多图见证模拟机器人的逆天成长:论进化策略在强化学习中的应用

AI 科技评论按:本文是 otoro.net 的系列技术博客之一,以通俗可视化的方法讲解了进化策略(Evolution Strategies)中的诸多概念。本篇...

459100
来自专栏大数据文摘

一位缺觉的父亲记录了他双胞胎宝宝的睡眠数据 并交给机器学习,结果……

21960
来自专栏Pulsar-V

SLAM初探(三)

PCL(Point cloud library) Ubuntu Linux 16 系统之所以会用Linux,很大的原因是应为SLAM在嵌入式平台上面...

37450
来自专栏媒矿工厂

【视频编码】 Content Aware ABR技术(三)

本系列的前面贴子中,我们梳理了Netflix和YouTube在ABR方面的一些进展,本文将简要介绍一下编码优化领域的一位新贵—Beamr的技术动态。 ? Bea...

44050
来自专栏大数据和云计算技术

似懂非懂Google TPU

谷歌的这款芯片被称作 Tensor Processing Unit,简称 TPU,是Google专门为深度学习定制的芯片。 第一次出现是在2016年的Googl...

33460
来自专栏人工智能头条

Etsy 数据科学主管洪亮劼带你读:WWW 2017 精选论文

16040
来自专栏大数据挖掘DT机器学习

PageRank算法(2):PageRank原理剖析

一、PageRank算法的简单举例 Google PageRank算法的思想精华在于:将一个网页级别/重要性的排序问题转化成了一个公共参与、以群体民主投票的方式...

79960
来自专栏机器人网

六轴机械手臂有哪些奇异点?

六轴机械手臂由六组不同位置的马达驱动,每个马达都能提供绕一轴向的旋转运动,其位置可参照下图。从自由度(Degree of Freedom)的概念来看,六轴机械手...

43490

扫码关注云+社区

领取腾讯云代金券