微信扫一扫背后的秘密：基于运动估计的智能传图算法(转)

作者：valiant、jamy

图1.1 常见的图像识别应用

　　本项目提出的图像算法主要解决如下问题：在移动设备实时获取图像的过程中，让算法自动决定何时进行图片发送请求、何时中断发送请求，并将此策略用在实时的图像检索应用中。目前的移动端图像检索应用，在选择发送图像时机时，多采用如下两种策略：

　　1.将图像不断地发送至后台，根据服务器端反馈结果，来决定停止发送；

　　2.加入用户交互，如拍照的方式，触发传送请求，如Google Goggles、百度识图、SOSO慧眼等当前主流视觉搜索引擎所做的那样。

　　采用第一种方案，可以保证用户较为方便地使用，由于传图密度较大，可以保证图片的质量比较好，但是缺点也是显而易见的，该策略会造成较大的网络传输量以及服务器端计算的压力；采用第二种方案，缺点是需要加入用户的交互，提高了操作的难度，且要考虑所在应用（如微信扫一扫）已有交互习惯的搭配性，因此其关键点是如何在保证图片质量的情况下大幅减小网络传输量和服务器运算压力。

二、技术介绍

（一）拍照识别与实时识别

　　图像识别是需要大数据量和大计算量的，所以一定是要放在云端。图像识别的方式有拍照识别，也有实时识别，但是我们看到市面上的所有产品几乎都是用的拍照识别的方式。其实早在做SOSO慧眼的时候，模式识别团队的同学就在思考一个问题，为什么一定要拍？我想拍照识别的最大好处就是用户意图明确，从而流量大幅减少。但是拍照识别的一个坏处就是用户一定要主动触发，而用户主动触发的情况下，只会进行一次识别尝试，一旦没有识别结果，用户的感受就会很差。如前面所述，实时识别才是更好的用户体验，但是不停传送图片的方法会造成大量的流量浪费，也会造成服务器压力过大。也正是因为此我们在上文中所提到的这些同类产品都没有实时识别的功能，而唯一有实时识别的 Goggles，经过测试，其采用的方案基本上也是定时上传的，只需用一会儿流量消耗就会很大。

　　那么我们的想法就是如何判断用户的意图？也就是只有用户确实在对准一个物体的时候会自动地上传一张图片进行识别？而在用户运动的过程中，或者图像模糊的情况下，能够不进行传输。通过这样的方式，实现了智能判断上传识别图像的方法，传输的数据量大幅缩减。

（二）基于运动估计的智能传图算法

1） 运动估计

　　运动估计的英文名称是（Motion Estimation）. 是视频编码和视频处理(例如去交织)中广泛使用的一种技术。我们这里将本来用于视频编码的运动估计思想移植到手机摄像头来，视频与手机摄像头的图像序列均有共同的连续图像相关性，因此运动估计算法是可以通用的。但是同时这二者又有很多不同点，比如手机摄像头获取图像分辨率往往较低，同时在用户实际使用的时候手机不会有太大幅度的运动。更主要的是，视频编码中所用的全局运动估计算法是非常慢的，即使在PC上也往往不能达到实时，因此我们进行这些特性进行了修改，来使得算法在各种低端手机上也能达到非常高效的性能。

图2.1 块匹配算法示意

　　我们采用的是最简单的基于块匹配的运动估计算法，示意图如图2.1所示。根据传入视频图像大小，对于视频帧中间的特定区域在其周围的一个有限邻域内采用由里到外的方式进行搜索。找到最相似的块后，根据二者位置获取两帧之间的运动矢量。搜索过程采用逼近算法，首先进行大步长的移动，找到相似度相对较小的区域，然后在区域内减小步长，逐步逼近得到最终的搜索结果。为了保证算法的高速，对于超过一定阈值的过大的视频帧图像，我们首先进行了降采样的处理。获取的运动矢量包含了方向和幅度两个信息。在手机这种场景中，根据实际的需求，我们所需要判断的运动主要有以下4种状态：运动、静止、运动到静止、静止到运动。其中前两个状态是根据实际的运动幅度判断出来的，后两个状态是根据前面的状态生成的。而运动到静止就是通常使我们认为可以上传图片的时机，而静止过程中的图片我们可以认为其图像区域没有明显的变化（或只有小幅移动），因此只需要上传其中一张就可以了。当然，虽然有了运动矢量，但具体到实际问题，更重要的是考虑防止抖动的影响以及用户慢速运动等很多情况，不能简单用阈值区分。运动估计算法整体流程图如图2.2所示。

图2.2 运动估计算法流程图

2） 图像有效性判别

有了上面的运动估计，我们已经可以较好地预测用户的意图，从而在运动到静止状态的时候启动传图到后台的识别过程。但是用户的手机存在对焦过程，并不是每一帧都是清晰的，即使是清晰的图像也不一定适合进行图像或者文字识别。因此有必要对于需要上传的图像进行有效性判断。为了提高识别率，以及根据图像识别的特征，我们采用基于FAST特征点的清晰度判别算法。针对实际使用的图片，修改训练了一套自己的FAST角点检测引擎，能够有较好的速度和角点检测能力。我们对于有效图片的定义是，第一清晰，第二具有较为丰富的纹理。这两点正好符合FAST的特征，在图片不清晰的时候，往往FAST点较少，在比如较多空白或者单一颜色的图片中，FAST点同样很少，因此只需要对于需要上传图片的FAST点进行判断，即可以获得较为有效的上传图片。在我们的实际应用中，仅需要在检测到运动到静止状态时，进行FAST点判断的过程，如果为清晰则直接上传当前帧，如果不清晰而后面仍然为静止状态，则在后面的帧中继续进行FAST角点检测，直到获得符合上传条件的帧图像。

经过优化，我们的引擎在iOS主流机型上均具有很好的性能，在每秒处理10帧的情况下，通常1-2帧处理即可进行运动和有效性估计。占用的CPU资源更是几乎忽略不计：

用户只需要打开微信“扫一扫”界面，进入“封面”或者“翻译”模式，即可进入识别状态，如下图所示：

图3.1 微信扫封面界面

其中客户端的处理流程如下：

图3.2 客户端-后台处理流程

　　“扫一扫”从摄像头获取实时的图像，预判逻辑会以一定的时间间隔从实时视频流当中截取图像进行处理，在规定的状态发生后，会自动触发图片发送逻辑，将图片发送至后台进行检索。

四、后续改进

　　虽然运动估计的算法已经能够比较简单而且快速地解决了智能上传图像识别的问题，但是后续仍然可以有很多改进的空间，比如可以区分图像和文字特征的不同，采用不同的清晰度判别方法，比如可以加入跟踪算法从而保持在已经识别到的物体尚在视频区域内时，不论其旋转或者拉远拉近，均不会因为图像发生变化而再次启动识别，等等。

　　这种探索只是一个简单而初步的尝试，但随着研究的深入，相信实时识别的技术一定会成为图像识别的主流。

附记：

感谢关注微信模式识别团队的最新技术：

微信5.0：

http://weixin.qq.com/

SOSO慧眼：

http://huiyan.qq.com/