AR算法原理在计算机视觉中的应用

图片识别

特征点匹配就是一个高维特征空间的搜索近似最近邻点的问题。如果是用最简单的线性匹配，那么速度远远达不到性能要求。这时候我们就必须用构建高维特征空间的数据结构算法。最经典有效的当属KD树及KMeans树两种结构及对应算法。

首先KD树算法我们来举个例子，假设有特征点样本集：{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}，那么使用KD树生成算法，构建出如下的二叉树，特征点匹配的问题就转化成了二叉树查找。

假如有待查找点P(2.1, 3.1)，如上图所示。那么搜索的过程就是先从(7,2)点开始进行二叉查找。由于第一层标记为考察X轴数据，于是待查找点与目前节点(7,2)的X轴数据比较：(2.1 < 7)，选择走左子树到达(5,4)，重复使用相同算法到达叶节点(2,3)，就是所要求的最近邻特征点。以上只是简单而不精确的描述，实际查找算更复杂，因为要有回溯的过程避免遗漏路径上层子树区域内可能存在的更近距离点。

实际的KD树生成及查找算法请看相关论文(Muja et al., 2014)。

另一个很实用的最近邻查找方案是KMeans树，它和KD树查找的原理相似。区别在于，KD树是二叉树，每个节点背后对应一个样本点。而KMeans树为K叉树，使用KMeans聚类算法将特征点集分为K类，然后每类移入下一层负责分别生成下一层子树，每个节点保存的是聚类中心点等相关信息。直到叶子节点的数据量小于等于K为止，构建完成K叉树后，使用类似KD树的查找算法从Root节点开始搜索，直到找到最近邻点。K叉树如下图所示，详细相关算法可参考论文(Muja et al., 2014)。

特征点匹配的直观效果，如上图。每条蓝色线段两端连接着的是两张图片上对应的匹配点。

两张图片上的特征点匹配完成后，就需要进行下一个步骤：两图像间的相似度度量。前面普及过一个透视照相机模型，大家还有印象么？描述不同拍摄位置同一图片之间的变换，我们称之为单应性变换。如图所示的H变换。

我们使用无需相机标定的查找单应性H的算法，通过匹配的点集来得到两张图片中最佳单应性变换H，详细可参考OpenCV中的findHomography方法。然后根据得到的H，考察两图片中的匹配点集，哪些符合此单应性变换H，哪些不符合。据此，得出图片的匹配相似度量，超过预先设定阈值就认为两图片相似，即识别成功。

AR识别追踪

追踪的过程就是估计被摄物体3D姿态及3D引擎渲染对应虚拟物体姿态的过程。每一次的追踪，都依赖于前述的特征点提取、匹配、及计算单应性变换。得到单应性变换，就等于得到了被摄物体3D现实坐标点集与二维屏幕成像坐标点集。通过得到的匹配点集以及标定获得的摄像机内参数，使用求解透视N点问题的算法，就可以求出摄像机外参数，即摄像机实时姿态，随即便可估算出被摄物体3D姿态。

最后一步，使用3D引擎渲染被摄物体上的3D虚拟物体，并且把虚拟物体的姿态根据上面估计出的实际物体的姿态矩阵进行变换。如下图所展现的，虚拟与真实物体的联动，实际上就是实现增强现实的体验。

技术驱动商业变革

全民扫品牌，让广告变得更有趣

AR技术用在营销场景下，为消费者带来的扫码体验将是崭新的,遥想一群人拿着手机在街上扫描LOGO观看AR动画的盛况,简直是物物皆传播,无处不营销。与此同时,乘着内容营销的风口,众多品牌汇聚所带来的集群效应,也将进一步连接品牌与平台,实现双方价值的最大化。

图 99聚星节聚划算&哈根达斯扫Logo营销Banner

去年9.9期间,国内外160余个一线品牌参加了天猫营销平台&聚划算的品牌LOGO AR互动。几乎你身边能看到的品牌,用聚划算客户端扫一扫,都会出现酷炫的AR效果,同时消费者还可以领取品牌方发出的不同面额的现金红包。此玩法以AR这种科技手段为媒介,将用户、品牌、天猫营销平台三者进行有机结合。

消费者:通过聚划算App体验每个品牌带来的AR创意,同时可以获得自己喜爱品牌的现金红包。

品牌方:通过AR视频来表达自己的品牌理念及新品趋势告知给消费者,同时获取自己的线下目标客户信息。

天猫营销平台:从之前的告诉消费者什么品牌在参聚，变为消费者通过AR互动知道这个线下品牌在参聚,同时即使该品牌不在参聚状态下,消费者也可以通过扫LOGO获取该品牌活动,订阅该品牌,获得其参聚资讯。

2016.9.4-9.9期间,部分优质品牌方和聚划算全面线上线下联动,将品牌LOGO,聚字LOGO全面投到地铁、灯箱、建筑地标等,消费者扫LOGO即可获得由品牌方及聚划算提供丰厚红包及礼品。

那么，在以上业务场景构建完毕后，为了完成业务需求，提升用户体验，我们必须对AR算法原理进行深入考察，并实现能够很好应用于以上业务场景下的AR功能。

基于庞大的业务背景，是成百上千的Logo图标，这些Logo往往比Marker更加复杂和不规则，并不能做到像传统的Maker那样四边边框清晰。用更复杂的图像来代替Marker，简单的识别技术已经不适应现有需求。于是我们开始尝试MarkerLess AR技术，也就是文章开头为大家介绍的技术原理。

为了适应Logo数量的增长，我们需要在大量Logo的业务场景下，达到移动端快速AR识别的能力。于是，我们将以上的AR识别技术扩展到了云端，由移动端提取特征数据上传到云端，识别的过程可以在强大计算力的服务器上并行完成，并及时返回结果。目前在我们的生产环境下，已经稳定的运行着可以实时识别万级别Logo量的AR引擎。

以上，AR技术的基础框架就构建完成了。我们将此AR算法用在了扫Logo的业务场景上，并产生了很好效果。

实现量化数据，打造智能化平台

对99聚星节扫Logo活动进行了详细的复盘分析和效果评估，我们发现在实现创新营销体验的同时，也获得了营销广告的数据化监控能力。

从数据上看，我们得到了创新的营销效果。扫LOGO整体会场消费者访问UV达到近千万（仅在预热期间展示） 参与玩法用户达到20%, 到达抽奖页面50%。通过 AR 技术打通线上线下，提升用户参与感，共计超过 100 家以上的品牌参与，当天进入微博话题排行榜第三名，红包引导率接近 90%。

传统广告投放最难的就是数据监控。大多数商家只能通过各方数据汇总得到一个粗放的效果判断,无法精确到个人的具体行为。但此次聚划算的品牌扫LOGO活动却切实做到了数据的精准和量化。

而商家通过消费者的扫LOGO行为,可以精确了解,这个广告带来了多少收益,谁在哪个时间扫描了什么。进而判断出每个广告位究竟能带来多少流量、多少收益、实现多少转化。

在未来,通过扫LOGO的创新玩法以及聚划算已经积累的海量数据,将为每一个消费者量身定制出真正需要的导购页面,最终实现广告收益的最大化。

2016奥运年，里约RIO成了全球瞩目的焦点。而更巧合的是，锐澳RIO鸡尾酒与巴西里约RIO同名。RIO作为里约奥运赞助商和天猫营销平台进行了深入合作，把AR扫RIO版瓶子的活动推上了营销活动的。

通过聚划算APP扫RIO里约联名涂鸦瓶身即可体验酷炫AR，将巴西风情真实融入瓶中，例如扫描奇幻亚马逊瓶，就能感受到骨头鱼与金刚鹦鹉的奇妙互动，消费者不光能在RIO X里约联名涂鸦瓶看里约，更能在RIO X里约联名涂鸦瓶体验里约。让消费者买到产品的同时感受营销体验，无疑又是一次创意上的巨大创新突破。

业界AR引擎的发展

我们来说说业界用于手机端识别追踪的AR引擎的发展情况。一言以概括，从2015年起国外几个著名的引擎都纷纷被大厂们收购，市场对AR技术的迫切需求产生了供给空白，这就给了国内一些小创业公司提供AR SDK服务的机会。

开源中最著名的ARToolKit，2015年被DAQRI收购，然后版本进度变缓，目前一直停留在5.3.3上，很多人翘首以盼的ARToolKit6一直跳票到现在。原先国外比较著名的几个商业AR引擎，如Vuforia和Metaio，前者被高通卖给了PTC，后者在2015年被苹果收购，基本上就退出了让开发者集成AR直接使用的舞台了。

于是，从2015年底开始市场出现了明显空白，这就给具备计算机视觉技术的某些国内厂商提供了绝佳的时间窗口机会。在2016年拼杀中，国内出现了几个有代表性的产品，如视辰EasyAR和亮风台HiAR。这些商业引擎虽然没有开源，但大都提供有限制的，需要集成AR功能的个人开发者可以去试试。

值得一提的是，天猫技术内部也已经有了AR SDK相关产品，目前已经提供给天猫及聚划算内部业务作为营销的技术支撑。后续不排除有接入整个集团基础服务平台或开源相关的计划，以供大家使用，各位不妨期待一下。

AR未来技术的展望

最近几年人工智能(AI)热潮越来越猛，最典型的便是好多人在说：“人工智能正在重塑整个社会”。AI正在从听觉、视觉与数据分析等多个方向形成对于人类智能的包围。计算机视觉与AR领域，无疑会受到AI进步的深刻影响。现在越来越多的AI算法渗入到计算机视觉领域，一个使用了深度学习的算法，很容易就可以得到比传统经典算法更好的性能效果。

比如大规模图像分类、目标检测与识别、场景语义理解都方面，都有了确切效果印证了AI算法的有效性。正如有人说的：“Deep Learning in All computer vision”，未来的AR技术发展会有越来越多的经典算法被DL算法替代。那么，到时候AR会达到怎样的体验，小伙伴们一起来期待吧。

识别图片二维码▲，关注「天猫技术」

技术驱动商业变革｜做最懂商业的技术人

---

相关荐文｜你还以为，除了你寄几就没有人懂你女朋友吗？

点击下方图片即可阅读