文档扫描:深度神经网络在移动端的实践

鲜于海舒(有道高级研发工程师)
随着深度学习算法在图像领域中的成功运用,学术界的目光重新回到神经网络上;而随着 AlphaGo 在围棋领域制造的大新闻,全科技界的目光都聚焦在“深度学习”、“神经网络”这些关键词上。与大众的印象不完全一致的是,神经网络算法并不算是十分高深晦涩的算法;相对于机器学习中某一些数学味很强的算法来说,神经网络算法甚至可以算得上是“简单粗暴”。只是,在神经网络的训练过程中,以及算法的实际运用中,存在着许多困难,和一些经验,这些经验是比较有技巧性的。
有道云笔记不久前更新的文档扫描功能中使用了神经网络算法。本文试图以文档扫描算法中所运用的神经网络算法为线索,聊一聊神经网络算法的原理,以及其在工程中的应用。

一、 背景篇

ynote_ocr
首先介绍一下什么是文档扫描功能。文档扫描功能希望能在用户拍摄的照片中,识别出文档所在的区域,进行拉伸(比例还原),识别出其中的文字,最终得到一张干净的图片或是一篇带有格式的文字版笔记。实现这个功能需要以下这些步骤:
1. 识别文档区域
将文档从背景中找出来,确定文档的四个角;
2. 拉伸文档区域,还原宽高比
根据文档四个角的坐标,根据透视原理,计算出文档原始宽高比,并将文档区域拉伸还原成矩形。这是所有步骤中唯一具有解析算法的步骤
3. 色彩增强
根据文档的类型,选择不同的色彩增强方法,将文档图片的色彩变得干净清洁;
4. 布局识别
理解文档图片的布局,找出文档的文字部分;
5. OCR
将图片形式的“文字”识别成可编码的文字;
6. 生成笔记
根据文档图片的布局,从 OCR 的结果中生成带有格式的笔记。
2
在上述这些步骤中,“拉伸文档区域”和“生成笔记”是有解析算法或明确规则的,不需要机器学习处理。剩下的步骤中都含有机器学习算法。其中“文档区域识别”和“OCR”这两个步骤我们是采用深度神经网络算法来完成的。
之所以在这两个步骤选择深度神经网络算法,是考虑到其他算法很难满足我们的需求:
  • 场景复杂,浅层学习很难很好的学习推广;
同时,深度神经网络的一些难点在这两个步骤中相对不那么困难
  • 属于深度神经网络算法所擅长的图像和时序领域;
  • 能够获取到大量的数据。能够对这些数据进行明确的标注。
接下来的内容中,我们将展开讲讲“文档区域识别”步骤中的神经网络算法。
二、算法篇
文档区域识别中使用的神经网络算法主要是全卷积网络(FCN)1。在介绍 FCN 前,首先简单介绍一下 FCN 的基础,卷积神经网络(这里假设读者对人工神经网络有最基本的了解)。
(一)卷积神经网络(CNN, Convolutional Neural Networks)
卷积神经网络(CNN)早在 1962 年就被提出2,而目前最广泛应用的结构大概是 LeCun 在 1998 年提出的3。CNN 和普通神经网络一样,由输入、输出层和若干隐层组成。
CNN 的每一层并不是一维的,而是有(长, 宽, 通道数)三个维度,例如输入层为一张 rgb 图片,则其输入层三个维度分别是(图片高度, 图片宽度, 3)。
与普通神经网络相比,CNN 有如下特点:
  1. 第 n 层的某个节点并不和第 n-1 层的所有节点相关,只和它空间位置附近的(n-1层)节点相关;
  2. 同一层中,所有节点共享权值;
  3. 每隔若干层会有一个池化(pool)层,其功能是按比例缩小这一层的长和宽(通常是减半)。常用的 pool 方法有局部极大值(Max)和局部均值(Mean)两种。
通过加入若干 pool 层,CNN 中隐层的长和宽不断缩小。当长宽缩小到一定程度(通常是个位数)的时候,CNN 在顶部连接上一个传统的全连接(Fully connected)神经网络,整个网络结构就搭建完成了。
3
CNN 之所以能够有效,在于它利用了图像中的一些约束。特点1对应着图像的局域相关性(图像上右上角某点跟远处左下角某点关系不大);特点2对应着图像的平移不变性(图像右上角的形状,移动到左下角仍然是那个形状);特点3对应着图像的放缩不变性(图像缩放后,信息丢失的很少)。这些约束的加入,就好比物理中”动量守恒定理“这类发现。守恒定理能让物体的运动可预测,而约束的加入能让识别过程变得可控,对训练数据的需求降低,更不容易出现过拟合。
(二)全卷积网络(FCN, Fully Convolutional Networks)
4
全卷积网络(FCN)是 CNN 基础上发展起来的算法。与 CNN 不同,FCN 要解决这样的问题:图像的识别目标不是图像级的标签,而是像素级的标签。例如:
  1. 图像分割 需要将图像根据语义分割成若干类别,其中每一个像素都对应着一个分类结果;
  2. 边缘检测 需要将图像中的边缘部分和非边缘部分分隔开来,其中每一个像素都对应着“边缘”或“非边缘”。(我们面对的就属于这类问题。)
  3. 视频分割 将图像分割用在连续的视频图像中。
在 CNN 中,pool 层让隐层的长宽缩小,而 FCN 面对的是完整长宽的标签,如何处理这对矛盾呢?
一个办法是不使用 pool 层,让每一个隐层的长宽都等于完整的长宽。这样做的缺点是,一来计算量相当大,尤其是当运算进行到 CNN 的较高层,通道数达到几百上千的时候;二来不使用 pool 层,卷积就始终是在局域进行,这样识别的结果没有利用到全局信息。
另一个办法是转置卷积(convolution transpose),可以理解为反向操作的 pool 层,或者上采样层,将隐层通过插值放缩回原来的长宽。这正是 FCN 采用的办法。当然,由于 CNN 的最后一个隐层的长宽很小,基本上只有全局信息,如果只对该隐层进行上采样,则局部细节就都丢失了。为此,FCN 会对 CNN 中间的几个隐层进行同样的上采样,由于中间层放缩的程度较低,保留了较多的局部细节,因而上采样的结果也会包含较多的局域信息。最后,将几个上采样的结果综合起来作为输出,这样就能比较好的平衡全局和局域信息。
5
整个 FCN 的结构如上图所示。FCN 去掉了 CNN 在顶部连接的全连接层,在每个转置卷积层之前都有一个分类器,将分类器的输出上采样(转置卷积),然后相加。
6
上图是我们实验中真实产生的上采样结果。可以看到,层级较低的隐层保留了很多图片细节,而层级较高的隐层对全局分布理解的比较好。将二者综合起来,得到了既包含全局信息,又没有丢失局域信息的结果。
(三)转置卷积(convolution transpose)
上文中出现的“转置卷积”是怎样实现的呢?顾名思义,转置卷积也是一种卷积操作,只不过是将 CNN 中的卷积操作的 Input 和 Output 的大小反转了过来。https://github.com/vdumoulin/conv_arithmetic 中提供了一系列转置卷积的图示,不过我个人认为更符合原意的转置卷积的图示如下图:
7
 8
与 conv_arithmetric 提供的图示对比,可以看出上图只是卷积示意图的上下翻转。在实际运算中,Input 层的某个节点数值会(以卷积核为权重)加权相加到与该节点相关的每一个 Output 层节点上。
从维度上来看,如果记卷积核的高、宽为 H 和 W,Input 层的 channel 数为 C,Output 层的 channel 数为 O,那么一次正向卷积的输入节点数为 H * W * C,输出节点数为 O;而一次转置卷积运算的输入节点数为 C ,输出节点数为 H * W * O。
(四)改进的 cross entropy 损失函数
在边缘识别问题中,每一个像素都对应着“边缘-非边缘”中的某一类。于是,我们可以认为每一个像素都是一个训练样本。这会带来一个问题:通常图片中的边缘要远少于非边缘,于是两类样本的数量悬殊。在模式识别问题中,类别不平衡会造成很多不可控的结果,是要极力避免的。
通常面对这种情况,我们会采用对少样本类别进行重复采样(过采样),或是基于原样本的空间分布产生人工数据。然而在本问题中,由于同一张图中包含很多样本,这两种常用的方法都不能进行。该怎么解决样本数量悬殊问题呢?
2015 年 ICCV 上的一篇论文4提出了名为 HED 的边缘识别模型,试着用改变损失函数(Loss Function)的定义来解决这个问题。我们的算法中也采用了这种方法。
首先我们概述一下 CNN 常用的 cross entropy 损失函数。在二分类问题里,cross entropy 的定义如下:
9
这里 l 为损失值,n 为样本数,k 表示第几个样本,Q 表示标签值,取值为 0 或者 1,p 为分类器计算出来的”该样本属于类别 1 “的概率,在 0 到 1 之间。
这个函数虽然看起来复杂,但如果对它取指数(L=exp(-l)),会发现这是全部样本均预测正确的概率。比如样本集的标签值分别为 (1, 1, 0, 1, 1, 0, …),则:
10
这里 L 是似然函数,也就是全部样本均预测正确的概率。
HED 使用了加权的 cross entropy 函数。例如,当标签 0 对应的样本极少时,加权 cross entropy 函数定义为:
11
这里 W 为权重,需要大于 1。不妨设 W = 2,此时考虑似然函数:
12
可见类别为 0 的样本在似然函数中重复出现了,比重因此而增加。通过这种办法,我们虽然不能实际将少样本类别的样本数目扩大,却通过修改损失函数达到了基本等价的效果。
三、数据篇
文档区域识别中用到的神经网络算法就介绍到这里了,接下来聊一聊我们为训练这个神经网络所构建的数据集。
(一)数据筛选
为了训练神经网络模型,我们标注了样本容量为五万左右的数据集。然而这些数据集中存在大量的坏数据,需要对数据进行进一步筛选。
五万左右的数据集,只凭人工来进行筛选成本太高了。好在根据网络的自由度等一些经验判断,我们的网络对数据集的大小要求尚没有那么高,数据集还算比较富足,可以允许一部分好的数据被错筛掉。
基于这一前提,我们人工标注了一个小训练集(500张),训练了一个 SVM 分类器来自动筛选数据。这个分类器只能判断图片中是否含有完整的文档,且分类效果并不特别强。不过,我们有选择性的强调了分类器分类的准确率,而对其召回率要求不高。换而言之,这个分类器可以接受把含有文档的图片错分成了不含文档的图片,但不能接受把不含文档的图片分进了含有文档的图片这一类中。
依靠这个分类器,我们将五万左右的数据集筛选得到了一个九千左右的较小数据集。再加上人工筛选,最终剩下容量为八千左右的,质量有保证的数据集。
四、实现篇
在模型训练中,我们使用 tensorflow 框架5进行模型训练。我们的最终目标是在移动端(手机端)实现文档区域识别功能,而移动端与桌面端存在着一些区别:
  1. 移动端的运算能力全方位的弱于桌面端;
  2. 带宽和功耗端限制,决定了移动端的显卡尤其弱于桌面端的独显;
  3. 移动端有 ios 和 Android 两个阵营,它们对密集运算的优化 API 各不相同,代码很难通用;
  4. 移动端对文件体积敏感。
这些区别使得我们不能直接将模型移植到移动端,而需要对它们做一些优化,保证其运行效率。优化的思路大致有两种:
  1. 选择合适的神经网络框架,尽可能用上芯片的加速技术;
  2. 压缩模型,在不损失精度的前提下减小模型的计算开销和文件体积。
(一)神经网络框架的选择
目前比较流行的神经网络框架包括 tensorflow, caffe6, mxnet7 等,它们大多数都有相应的移动端框架。所以直接使用这些移动端框架是最方便的选择。例如我们使用 tensorflow 框架进行模型训练,那么直接使用移动端 tensorflow 框架,就能省去模型转换的麻烦。
有的时候,我们可能不需要一个大而全的神经网络框架,或者对运行效率要求特别高。此时我们可以考虑一个底层一些的框架,在此基础上实现自己的需求。这方面的例子有 Eigen8,一个常用的矩阵运算库;NNPACK9,效率很高的神经网络底层库,等等。如果代码中已经集成了 OpenCV10,也可以考虑用其中的运算 API。
如果对运行效率要求很高,也可以考虑使用移动端的异构计算框架,将除 CPU 以外的 GPU、DSP 的运算能力也加入进来。这方面可以考虑的框架有 ios 端的 metal11,跨平台的 OpenGL12 和 Vulkan13,Android 端的 renderscript14
14
(二)模型压缩
模型压缩最简单的方法就是去调节网络模型中各个可调的超参数,这里的超参数的例子有:网络总层数、每一层的 channel 数、每一个卷积的 kernel 宽度 等等。在一开始训练的时候,我们会选择有一定冗余的超参数去训练,确保不会因为某个超参数太小而成为网络效果的瓶颈。在模型压缩的时候,则可以把这些冗余“挤掉”,即在不明显降低识别准确率的前提下,逐步尝试调小某个超参数。在调节的过程中,我们发现网络总层数对识别效果的影响较大;相对而言,每一层的 channel 数的减小对识别效果的影响不大。
除了简单的调节超参数外,还有一些特别为移动端设计的模型结构,采用这些模型结构能显著的压缩模型。这方面的例子有 SVD Network15, SqueezeNet16, Mobilenets17等,这里就不细说了。
(三)最终效果
经过神经网络框架定制、模型压缩后,我们的模型大小被压缩到 1M 左右,在性能主流的手机(iphone 6, 小米 4 或配置更好的手机)上能达到 100ms 以内识别一张图片的速度,且识别精度基本没有受到影响。应该说移植是很成功的。
五、总结
在两三年之前,神经网络算法在大家的眼里只适用于运算能力极强的服务器,似乎跟手机没有什么关联。然而在近两三年,出现了一些新的趋势:一是随着神经网络算法的成熟,一部分学者将研究兴趣放在了压缩神经网络的计算开销上,神经网络模型可以得到压缩;二是手机芯片的运算能力飞速发展,尤其是 GPU,DSP 运算能力的发展。伴随这一降一升,手机也能够得着神经网络的运算需求了。
“基于神经网络的文档扫描”功能得以实现,实在是踩在了无数前人的肩膀上完成的。从这个角度来说,我们这一代的研发人员是幸运的,能够实现一些我们过去不敢想象的东西,未来还能实现更多我们今天不能想象的东西。
参考文献

  1. Long, J., Shelhamer, E., & Darrell, T. (2015). Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (pp. 3431-3440).
  2. Hubel, D. H., & Wiesel, T. N. (1962). Receptive fields, binocular interaction and functional architecture in the cat’s visual cortex. The Journal of physiology, 160(1), 106-154.
  3. LeCun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278-2324.
  4. Xie, S., & Tu, Z. (2015). Holistically-nested edge detection. In Proceedings of the IEEE International Conference on Computer Vision (pp. 1395-1403).
  5. https://www.tensorflow.org/
  6. http://caffe.berkeleyvision.org/
  7. http://mxnet.io/
  8. http://eigen.tuxfamily.org/index.php?title=Main_Page
  9. https://github.com/Maratyszcza/NNPACK
  10. http://opencv.org/
  11. https://developer.apple.com/metal/
  12. https://www.opengl.org/
  13. https://www.khronos.org/vulkan/
  14. https://developer.android.com/guide/topics/renderscript/compute.html
  15. Denton, E. L., Zaremba, W., Bruna, J., LeCun, Y., & Fergus, R. (2014). Exploiting linear structure within convolutional networks for efficient evaluation. In Advances in Neural Information Processing Systems (pp. 1269-1277).
  16. Iandola, F. N., Han, S., Moskewicz, M. W., Ashraf, K., Dally, W. J., & Keutzer, K. (2016). SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and< 0.5 MB model size. arXiv preprint arXiv:1602.07360.
  17. Howard, A. G., Zhu, M., Chen, B., Kalenichenko, D., Wang, W., Weyand, T., … & Adam, H. (2017). Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv:1704.04861.

Avazu Click-Through Rate Prediction比赛分享

                                                                                                              燕鹏、周骁聪

Avazu Click-Through Rate Prediction是移动广告dsp公司avazu在kaggle上举办的广告点击率预测的比赛,全球共有1604支队伍参加,我和周骁聪组队参加了比赛,最终我们获得了第三名。下面是我们比赛的方法分享。

Avazu CTR Prediction

整个比赛历时两个多月,在这个过程中我们和众多数据挖掘高手交流切磋,对于广告点击率预测问题也有了更深的理解。点击率预测算法在经历了多年的研究和发展之后,如今再要有一个大的提升已经是一个比较困难的事情了。当前点击率预测算法的主要收益大都是来自于线性模型的改进+特征工程,最近几年工业界已经开始尝试用非线性模型去解决点击率预测的问题,也取得了一些不错的结果。通过这次比赛,我们也相信非线性模型的使用以及多模型的融合会带来点击率预测算法的下一次飞跃。

Scrum——在变化中求进化

贾儒(高级开发工程师)

移动互联网当道的今天,变化已经是大家习以为常的事情了。也许昨天还在街边苦等久久不来的出租车,今天已经可以在手机上点点预约车辆准时到达门口。优秀的产品带来了生活习惯、甚至生活方式的变化,这是从前无法想象的。在这背后则是互联网产品服务的变化,在这个大潮中,“进化”的周期变得越来越短,大家也许还记得当年各大杀毒软件厂商,每年才会发布一个新的功能版本,而如今几乎每一天大家的手机上都会收到各种各样的软件更新。而在这种快速更新的软件背后,需要一种能够很好适应并响应变化的团队组织方式——已经为大家所熟知的敏捷开发方法Scrum。

Continue reading

局域网内针对自制证书网站的SSL中间人攻击

孔祥欣(高级开发工程师)

对于网络上通信的两个人,我们如何窃取他们的通信信息而又不被他们发现呢?一种通用的做法就是中间人攻击。所谓的中间人攻击就是通过某种技术手段将攻击者放置在通信的两个人之间,拦截并分析他们的通信流量,然后在将流量转发给对方。

如下图所示,Alice和Bob以为他们是通过虚线通信的,实际上是通过实线由Malicious转发的,这里Malicious就是一个中间人,他可以看到Alice和Bob之间的全部通信信息。

kongxx 图1

为了防止中间人攻击,Alice和Bob决定使用SSL协议。

Continue reading

云存储系统中的数据去重与加密

段亦涛(有道首席科学家)

本文是基于作者最近发表于CCSW’14的一篇论文,Distributed Key Generation for Encrypted Deduplication:Achieving the Strongest Privacy,简要介绍云存储系统中支持数据去重的加密算法的最新进展。论文的DOI是

为了描述方便,本文采用了和论文中完全一致的参考文献标号。读者可去论文中直接参阅。

1. 背景

大规模云存储系统往往面临两个矛盾的需求:一方面系统需要压缩数据以节省存储空间的开销;另一方面,用户出于数据安全和隐私的考虑,希望自己的数据加密存储。目前数据压缩非常有效也是很常用的一个手段是去重(deduplication),即识别数据中冗余的数据块,只存储一份,其余位置存储类似指针的数据结构。研究表明,基于数据分布的不同,有效的去重能够节省高达50%甚至90%的存储空间和带宽 [32, 17, 27, 21]。去重已经被广泛用于很多商业化的系统如 Dropbox [3],EMC [36],等等。许多Peer-to-Peer (P2P) 系统也使用同样的技术来节省存储空间 [52, 53, 5, 6].
Continue reading

前端学习之iOS开发(二)

liuzq(前端开发工程师)

本文是继上一篇《前端学习之iOS开发(一)》的续集,上一篇属于iOS开发的入门篇,主要内容为前端学习iOS开发的优势和对比学习。本文的内容为介绍在新的项目《有道口语大师》中的实际应用,主要包括第三方类库管理工具pods、sqlite、文件操作、网络请求、引导动画等在项目中的实践。

一、第三方类库管理工具CocoaPods

CocoaPods作为iOS开发的第三方类库管理工具,可以很好的解决第三方类库的检索、安装、更新等操作,功能与nodejs中的npm类似。 Continue reading

用“逐步排除”的方法定位Java服务线上“系统性”故障

李斯宁(高级测试开发工程师)

一、摘要

由于硬件问题、系统资源紧缺或者程序本身的BUG,Java服务在线上不可避免地会出现一些“系统性”故障,比如:服务性能明显下降、部分(或所有)接口超时或卡死等。其中部分故障隐藏颇深,对运维和开发造成长期困扰。笔者根据自己的学习和实践,总结出一套行之有效的“逐步排除”的方法,来快速定位Java服务线上“系统性”故障。


Continue reading

Deep Learning实战之word2vec


邓澍军、陆光明、夏龙

前言Deep Learning已经很火了,本文作者算是后知后觉者,主要原因作者的工作是广告点击预测,而之前听说Deep Learning最大的突破还是在图像语音领域,NLP和在线广告点击预测方面的突破还不够大。但后来听说Google开源的word2vec还挺有意思,能够把词映射到K维向量空间,甚至词与词之间 向量操作还能和语义相对应如果换个思路,把词当做feature那么word2vec可以把feature映射到K维向量空间应该可以为现有模型提供更多的有用信,基于这个出发点,作者word2vec的相关代码和算法做了相关调研,本文是作者关于word2vec调研的总结,也是作为自己以后备用。存在疏漏之处,欢迎大家反馈:shujun_deng@163.com

 

…..继续阅读(请下载附件): word2vec

 

前端学习之IOS开发

liuzq(前端开发工程师)

随着智能手机的普及,目前移动互联网已经飞速发展,几乎每天都会有涉及人们生活的各种Android APP或者 IOS APP上线。作为一名WEB前端开发人员,一切与用户交互相关的技术都应该关注一下。前段时间有幸参与了第一个IOS项目——职场口语APP。现在站在前端开发人员的角度分享下开发心得,文章主要适用于未接触过IOS开发的前端人员,可以让其对IOS开发有个粗浅的了解。

不论是Javascript还是Object-C,作为一门编程语言它们的基本概念和编程思想都是相同的。所以这里的重点不会是数据类型、语法、语句等概念,更不会讲语言的发展史之类,至于这些基础知识需要感兴趣的同学自行学习啦。这里主要会讲如何创建第一个IOS项目、前端开发人员学习IOS开发的优势、前端开发和IOS开发的对比。

Continue reading

敏捷中的测试实践

Xing Binbin(测试工程师)

    有道云笔记团队采用敏捷的开发模式已有近两年的时间,为了更好的协作完成产品迭代,笔记测试团队也逐渐积攒了一些敏捷实践的经验。然而敏捷测试的转换和实施并不容易,和资源、环境等诸多因素有关系。如何实现从传统瀑布模型到敏捷模型的转化?本文将会结合笔记测试团队一些良好的实践来进行介绍。

    前不久ChinaTest大会上Martin Pol的演讲,阐述了测试从产生到现阶段的演变过程。如图1所示:

Continue reading