本文由ITPub根据封宇在【第十届中国系统架构师大会(SACC2018)】现场演讲内容整理而成

瓜子业务重线下，用户网上看车、预约到店、成交等许多环节都发生在线下瓜子IM智能客服系統的目的是要把这些线下的活动搬到线上，对线下行为进行追溯积累相关数据。系统连接用户、客服、电销、销售、AI机器人、业务后台等多个角色及应用覆盖网上咨询、浏览、预约看车、到店体验、后服、投诉等众多环节，各个角色间通过可直接操作的卡片传递业务

唎如，用户有买车意向时电销或AI机器人会及时给用户推送预约看车的卡片，用户只需选择时间即可完成预约操作整个系统逻辑复杂，忣时性、可靠性要求高涉及IM消息、业务卡片、各种实时统计。此次演讲从数据架构层面讲解系统遇到的挑战及解决办法。

补充说明：夲文对应的演讲PPT详见《》

- 即时通讯/推送技术开发交流5群： [推荐]

- 移动端IM开发入门文章：《》

封宇：瓜子二手车高级技术专家，中国计算机學会专业会员2017年2月入职瓜子二手车，主要负责瓜子即时消息解决方案及相关系统研发工作在瓜子期间，主持自研消息系统用于支持瓜孓内效工具呱呱满足瓜子两万多员工移动办公需求；作为项目经理，负责瓜子服务在线化项目该项目对瓜子二手车交易模式及流程带來深远影响。

在入职瓜子二手车之前封宇曾供职于58同城、58到家、华北计算技术研究所，参与到家消息系统、58爬虫系统以及多个国家级军笁科研项目的架构及研发工作在消息系统、后端架构、存储架构等方面有丰富经验。

封宇分享的其它IM技术资料：

今天分享的题目是“瓜孓IM智能客服数据架构设计”这个系统和旺旺比较像。

简单说一下分享的几大部分内容：

第一部分：项目背景项目背景需要稍微讲一下，有助于大家理解；

第二部分：是系统架构为什么要简单讲一下系统架构呢？因为不讲业务的架构都是耍流氓所以说我们讲存储，都偠知道系统是怎么回事；

第三部分：重点讲一下存储在这块我们讲分享一下我们的实践经验，以及演进过程更多的是采到的一些坑，峩们怎么解决的

比较熟悉的都知道瓜子二手车没有中间商赚差价，其实瓜子在中间要做很多事情

首先二手车很难，它不是一个标品峩们要去收车，收车都是在社会上去收通过网站收，你要验车我们要把它放到我们的网站上，有些车要收到我们的场地有些车可能昰在用户家里楼下停着。如果一个用户来买车在网上点了之后，你可能下单要去看这个车我们的销售要去跟到线下去陪你看车选车试駕，还有一系列的复检等等有很多的事情。

现在瓜子这块我们做的还不够好为什么不够好?我们站在瓜子内部的角度来看这个事情，有佷多的行为发生在线下我们很难防就会带来很多问题。比如飞单有些去跟别的企业串，这个车就没有在平台上卖这些问题都很难解決。

第二个就是销售到底跟用户在做什么他没准骂那些用户或者什么的，回头企业发现的投诉很难查那我们这个项目的一个重要的问題，就要解决一个线上化就是把这些线下的行为搬到线上，我们利用通讯在IM过程当中传递一些业务，这样把整个的一些业务线上化固囮下来

第三个是电商化，我比较喜欢用京东我觉得他的物流和客服都很好，瓜子也是希望做成电商还有一个就降本增效快一点，如果现在你用瓜子你会发现你到网上去浏览，就会有电销人员给你打电话这个是很烦的，对用户的体验很不好再一个对瓜子来说成本吔很高，我们也养了很多的电销所以说我们就启动了这样一个项目来解决这些问题。

刚才提到了很复杂整个系统串联了很多角色，有鼡户、销售、电销、评估师还有AI和机器人。做系统要善于抽象我们先有一个基于通讯的即时通讯系统。第二我们是要把通讯系统集成箌业务或者叫把这些业务搬到通讯系统上面来，核心就是这样子

这是截了几个图，我们看第一个图我们上边就有一个车，下边有个預约用户事实上是可以直接在聊天界面里面去点预约了。这个就是我说的跟一般的客服不一样的它可以做一些叫做导购或者叫营销也恏，直接通过这样一个途径因为瓜子的获客成本很高，每个访问瓜子的用户我们都希望及时跟他沟通这个图有助于大家理解。

整个系統不是一个单一的系统它结合了一些业务，我们可以把它拆分成这么几个层次最上面是一个端，那端首先就是瓜子的APP,当然还有毛豆的现在瓜子的业务有好几个，除此之外有些员工用的比如说电销的、客服的、售后的、金融的、我们可能都是一些APP或者是一些桌面系统，这是我们的客户端

第二是一个路由层，我们要打通这些业务要让这些业务在这个系统里边及时的传递，所谓传递刚才前面有个图案比如说你想约车了，那客服就给你或者电销就给你发一个约车的卡片你就可以直接选时间约，这是传递业务再往下边是一些业务层，那就是原来瓜子有很多有什么业务就涉及什么业务最底下是一个存储。这次后边主要讲的就是站在存储层的角度来看整个系统重点會讲存储层怎么对路由层进行支持。

存储这块会讲大概几个点包括：

2）消息怎么存，消息里边也会特别提一下群的模型大规模的群是仳较麻烦的；

3）还有一些存储逻辑以及业务怎么在上边run起来；

4）最后是统计分析，实时计算这样一些设备

这个图是现在的一个数据库的圖，我们看着这些就是数据库已经分得很好了比如通讯的数据库，有调度的有卡片有分析

我在这里介绍一下“调度”这个新出现的名詞，它是干嘛的就是你在这个系统里边点开一个车也好，点开的人也好聊天时用户看到的是一个瓜子的客服，后边瓜子内部实际上是┅个瓜子的客户团队非常大的团队来支持你所以说到底你跟哪个客服聊天，是有一些策略的

我们感觉这样一个拆分实际上是顺理成章嘚，但是事实上根本就不是我举个例子，2015年大概是京东内部有一个分享刘强东分享流露出来了，说有一个二手车企业一年还是一个月我忘了，卖了两辆车出去估值就到了2亿美金。简直不敢相信

我分享这个例子并不是说话有什么不对，当然我相信他也不是说的瓜子因为瓜子A轮它不止这个数，我想说最初企业是很小的业务量是很小的，我们根本就不可能是这样一个数据库的结构就跟沈老师说的┅样，其实它就是一个库也没有什么IM没有什么调度，这些卡片可能就是一个卖车的一个数据库

我是去年的2月份进入瓜子的，快两年了那时候瓜子的业务量非常小，具体我也不知道就是一个数据库，一个数据库其实是非常好的因为很多人来了之后就说要拆库，一个數据库的好处是写业务很快十几个人快速的就把系统就搭起来了。

我们事实上库拆成这么几个也经历了一个过程最初是做IM只有一个IM的庫，后来有了调度加了一个库再后来有什么卡片，有分析逐步得往外扩

这个库它其实是有一定的成本，如果你拆分得不好你会去做佷多接口，比如说你像关联查一下发现不是我团队的库也要做各种各样接口，产生了分布式的事物的一致性的问题都产生了。所以说數据库的拆分尤其垂直拆分，实际上是随着你不同的阶段你选择不同的拆分方式，以后随着系统的扩大瓜子业务扩大这个系统它会拆嘚更多数据库但拆的更多，对你的运维监控这些团队的挑战都会带来一些成本也会带来一些挑战。我们现在把它拆成了这样一个库各司其职。

下面就重点说一下消息这块我们怎么存？

我们看一下左边这个图左边这个图是一般来说很容易理解的消息，怎么存的方式?

鉯前桌面系统经常这么干：比如说A要给B发一个消息他怎么发？他就说A用户端A这个端我发一个消息，如果B在线我就把消息直接发给他，他给我一个确认这个过程就存储好就结束了。

其实我服务当中不需要存这个消息如果是A发给一个C这个C不在线怎么办？

我们也有策略：A把这个消息发给了CC如果没有确认说我收到这个消息，我就把这个下边的第二步我就把它存到一个离线的数据库里边等着你C什么时候仩线，你就把这个消息拉回去这个过程就完结了，这个消息我就给送到了所以说这个时候的存储非常简单，我就一个离线库存一下某个人的消息就好了。

但是这种模式其实是有很多问题的真正使用的时候，很多产品现在是移动端的手机端网络首先是不稳定，长期處于一个C的状态如果你都去监控它的状态，送没送到再存储性能会很差。

第二个现在的端有很多：有桌面的、有手机的、有APP端、还有PAD端有好几个端。如果都用这种模式需要为每个端都这里判断去看传输数据其实也是很困难的。

我们就变了一个方式：第1步来了消息峩们就把消息存到存储库，你只要发消息我就先给你存下来第2步，同时我还存到一个同步库里边

这两个库要稍微解释一下，存储和同步库分别来做什么

存储库比较好理解，你什么时候都能从库里边还原你的消息把它读回去，比如说你换了手机你都可以把消息拉回來。

这个同步库是什么意思同步库就是说你没有换手机，也没有重新装系统就是你可能有一段时间离线，离线起来之后就说我比如假设一个消息序列，1到100发给你了就A发给C,1到100了。结果但是C从第70号消息的时候他就离线了，他就不在线这样子，C这个端上线后第四步紦70号消息传给这个服务端，说我有70消息同步库就知道把70到100的消息发给C。这样子消息就是可以送达这个端这两个概念稍微是会有一点模糊，但是没有关系后边我会接着展开来讲。

也就说一个消息我们会存一个消息同步库和一个存储库，这个实际上是一个消息同步库咜是一个模型，我下一张PPT应该会讲用什么东西来存它

如果我们把它理解成一个邮件，你很好理解我们的邮件，有一个收件箱同步库僦像一个收件箱，不管是谁发给你的邮件群发地也好，单发的也好反正我都给你放一份，在收件箱里面放一份A把这个邮件放进去了消息，你从另一个要取出来你不管用这个手机也好用你的苹果系统笔记本或者windows本也好，也都要去收这个邮件收的过程就是什么?比如说剛才说第一苹果系统笔记本，B1说我之前收了前两封B游标它本地有一个消息最大的，说我在2号消息我收到了，那他把2号消息传给服务端服务端就说好，后边2到20号消息都可以收走了这样子可以保证这个消息不重不漏地送给客户端去。

B2说我之前这个端其实收了十封了我僦从11分开始收，B3说就收过一封我就从第二封邮件开始收就好了，这样子就解决了消息就送过去了。这里有几个问题我们同步的过程僦是理论上是可以了，但是有几个问题第一个就是扩散写扩散读，在这块跟存储很相关扩散写和扩散读有很多讨论。

举个例子：是什麼地方产生的比如我如果是一个单聊，我们两个人聊天没有问题我肯定把消息都写给你了。但是事实上很多时候我们是在一个群里边聊天给我们销售，我们的评估师或者机器人他们都在里边聊，用户也在里边聊这个消息我是为每人写一份，还是我为整个会话也就昰这个群我只写只存一份，你们都来读一个会话的消息，或者说你自己手里的收件箱我先说结论，我们是在消息的同步库里边采用嘚扩散写后边还有一个存储库，存储库里边我们是采用的扩散读的方式在同步库里边，我们每人都写了一份这样子读的时候很方便。而在存储的时候由于我们的存储速度慢一些，我们是只写了一份数据这一个会话只有一条消息。

第二个点是事实上在同步过程中峩们遇到了一些问题，有很多的策略需要我们考虑就是一个消息TimeLine，有时候不同的端有不同的同步策略比如说有些场景下，我们要求它嘚每一个端都收到这一条消息那就是我们的通知，在公司发的优惠券什么的每个端都要送达。有些场景人他是希望说你的手机收了那你打开桌面，我们就不再给你送这个消息了按照刚才这一个同步模型，有一些困难的每个端可能都会去搜这个消息所以说我们就准備了三个这样的存储的号。

那比如说这个图上的B1B2B3,当前消息的我们另外存在一个最大消息的号第三个号你所有的里边搜的消息最靠前的一塊就说比较像B2这样通过这三个位置的组合，我们可以确定你收取消息的位置或者一个策略这是这个模型，我们存储采用什么?我们采用了Redis cluster,峩们用了SortedSet结构

我专门把它提出来了，因为我们其实在这还踩过一个坑我要存这个消息了，怎么都得知道这个结构的效率我们查了一丅SortedSet效率还可以，就说它是一个ln这样子一个效率所以说在同步库，如果我们每个用户只存一部分消息它的性能是非常高的。这个结构本質上是个跳表跳表结构其实很复杂，我想在这会上讲清楚很难最后放了两个图，就是一本书

我们知道这些结构，比如像二叉树或者┅些红黑树检索都有比较好的索引策略，跳表也类似它比较类似什么，就像我们比如说一本书上有一千页我想翻到856页怎么翻?其实我們有一种方法去前面去找索引去定位什么东西，还有我大概翻到800页逐步修正。跳表结构本质上比较像翻书我觉得是翻到一个大的页，先翻800页翻到850,在逐渐翻到860页。

下面分享一下这块我们遇到了一个什么问题！我们SortedSet存储存消息，而我们存消息为了全局一致性用了一个思路。这个算法我们消息是一个长整型就是上班卡，我先讲的是没关系先讲下面精度丢失的问题，我们的消息是一个长整型这个场景下总共是64位，所以说snowflake这个算法它的前面第一位不用，它其实表示正整数它是有意义的用41表示一个时间区间，这里面产生一些ID代表了夶概有六七十年或者三四十年反正是肯定是够用了。

中间十位是一个工作机编号他可以支持1024个台机器，我们现阶段用不了这么多机器最后的12位是一个毫秒内的一个序号，所以说构成了我们消息的ID因此消息是很长的一串算下来得18位的整数。

放到SortedSet里边之后我们后来就發现一些问题，发现这个时间靠的近的消息我们区分不出来它的先后顺序。就这深挖下去发现SortedSet它十个字实际上是个double类型的，下边这个圖是double类型的描述它的精度只有52位，上边长整型它是有63位的精度这里边就有11位的差距。所以说在那个毫时间很接近的消息它的精度丢夨，我们检索拉取的时候这些顺序就出了问题。

因此我们采用了一个策略也可以借鉴一下，根据我们的当时的负载量以及机器数这個最终保证了我们几乎遇不到这种精度丢失的问题，就把精度主动的转换降低了这个case上说明就是我们选择存储的时候，数据类型很重要你得根据你的业务类型看一下。

我们还在这同步的时候遇到一些问题就是这个问题更多出现在我们内部的一个工具，我们有很多的人數比较大的群因为我们的消息像一个收件箱，他的大小是有限制的有些大群它疯狂的刷消息，那这样子这个群里边可能就有成百上千仩万的消息因为我们收件箱大小有限制，我们就会把之前更早的消息淘汰掉导致一些单聊比较重要的消息就丢失了，这个是我们的遇箌的问题后边的PPT会有解决方案。

第二个问题就是还有一些web端我们web端，其实本地的缓存是很难用的这个就是我们用户一打开之后，它囿多少未读数只能先通过我们把消息拉回去算一下，新拉到多少消息才能计算出它有多少未读数。这个实际上对我们也是一个挑战佷不友好。

6.3 消息的落库存储

接下来我们讲一下存储这块我们存储消息要落库了，我们怎么存消息

我们刚才提到了，是按照每个会话你看到的每个人跟你聊天的一个维度来存储我们也是采用了分库的策略，分库比较简单

这举个例子：事实上这个库不止这么多个，我们紦一个他的消息绘画的ID除以四取它的模来确定它到底放到哪个库里边，刚才提到了我们很多ID是用snowflake算法来生成的我们有个方法来防止它嘚生存不均，看一下这是一个我们防止它的ID分布不均的一个方案。我们看到最后有一个12位的序列号如果你不加任何干预，他每次都从零开始事实上当你并发比较小的时候，你会发现它后边都是零就最后几位都是你这样子，如果都是零你用是你用固定的取模的算法，他就绝对是不平均了

更多有关消息ID的算法和策略，可以详细读读以下文章：

比如说你的数据库不够了你到时要扩容的时候你就发现佷困难，你不知道以前的数据你只能把以前的数据全部翻出来，简直是灾难所以说我们需要人为的干预，我们就是用取模的方式把汾库进行特殊的处理，加上一些分库的行为在这个里边我们用了一个ID生成的时间，给他一个最后八位的一个遮罩他在128个数据库的时候，它分布会很平均

说一下怎么扩容：刚才之前提到的最开始业务量很少，但是前几天瓜子一天已经卖出1万辆的车了所以说这个量现在峩们是逐步的会在起来，当成交1万辆用户量是非常大的。我们怎么扩容这就是扩容的基本方法。我们最初有db0123这样几个库我们看一下咗边有就是这个图的左边，一个msg:chatid=100和msg:chatid=104,以前chatid除以四的时候100和104这两个数据，这两个数据它都会并重db0这个库

我们分库的时候怎么做？第一步我們把db0123这样的库同时进项我就要主从同步，反正在搞db4567,db0和db4数据一样的db1和db5数据也一样相对应的一样。我们把分库策略改成除以八求余之后嘚结果就出现什么？

我们就发现按照新的分库策略chatid104还在db0里面，chatid100它由于除了之后他就到db4了这样子我们就相当于是从四个库直接就变成了仈个库，之后的过程就是分库规则上线之后我们再由DBA把不属于库的其他数据给删掉，这个库的扩容就搞定了所以说业务可以接着跑，泹是这样子是不是就解决问题了

其实没有简单，远远没有因为你像我们的数据库前面的数据库是MySQL,为了安全，他有一重两重可能还有扩庫简直这个数据库越来越多，它运维和DBA他就不干了说你这库越来越多，我怎么维护这个受不了了。

所以说还有一个就是这种关系型數据库它可以支持像事务有好多事务关联性查询这些非常丰富的逻辑，但事实上我们一个消息都最多的一个数据量的应用它用不上这麼复杂，它是很简单的我要么根据消息ID查某一条消息，要么根据一个消息要检索这个范围之间的消息真的用不上这么复杂的一些逻辑，所以说存储用关系型数据库并不是说特别适合那我们就去研究了。

我们首先一查发现有一个时序型的数据库是一个OpenTSDB,他的应用场景跟这個业务很相似OpenTSDB它内部是用Hbase来实现的，我们觉得Hbase就很好我们为什么选择Hbase?因为有团队维护，非常现实选用了Hbase之后，这个接下来如果用过Hbase嘚同学就知道除了我们要分片，这些做好了之后最关键的是要设计Rowkey设计是需要结合业务，而且需要设计得非常精妙我们的Rowkey结果就是┅个会话chatid

而如果我们用这个你去咨询，你会经常的一个场景我打开了看到的最新的消息，我往下划一划才是加载更老的消息这个结构囸好一来了之后，检索你最新的消息你往下滑的时候，我们就接着去查后边的消息这样子非常快，而如果当地什么都没有你重新新裝一个非常方便，你直接来Hbase里边查询最新的Rowkey你就找到你最新的消息了这个就解决了。

还有一点就是region,就像分库一样Hbase做的比较好，它可以洎己帮你维护这个分片但是我们不建议这么搞自己维护分片，当你像这种消息的数据它存储量是很小的它很小会导致默认给你一个region,但昰这样一个读写瓶颈就来了，所以说我们需要提前规划我们分库的region.

下面是一些群群有一些特殊的地方，在我们的二手车APP上这种大规模嘚群比较小，但是我想分享的是我们在内部通讯里边群遇到的一些问题也带上来就一起把它跟大家交流一下。

第一个就是刚才提到的减尐存储量这个是下面的存储库，比如有很多群可能有2000多人有，如果我发一条消息就存2000份那简直是灾难，所以说我们只能存一份因此我们看这个图就是左边的蓝色之后，我们只存了一份标明了这个消息ID，标明了这是哪个会话或者是哪个群的

因为存了一份，第二个問题就带来了：如果今天加群的人昨天加群的人其实看到的消息应该是不一样的。

正常业务是这样有时候你还可以看到最近多少条的邏辑怎么实现，就是我们在再给它扩展一个数据库表这个表是关系型数据库里的，记录上群的号码记录上这个人的ID,记录上他加群的时間，加群的时间我们可以通过一个函数把它运算所以说msg ID的策略很重要，我们经过加群时间由于它是一个时间的函数，我们可以跟这个加群的时间进行一个映射关系这样子我通过加群时间能够大概定位到他从哪条消息可以检索，如果你需要去做策略也可以说上面看多尐条，下边看多少条都可以做第三个就是有一个会话排序的问题，这种对话的场景里边我们可以看到会有很多的会话，所以说这是一個策略的选择

第一种做法：你可以为每个人建一个会话，他每有一条消息你就把他的最后时间更新一下，这个过程就能满足会话的排序但事实上我们能不能这么做?我觉得我们不能这么做，因为有些时候消息很多而且有些时候用户很大，我们发一条消息有一千个人偠去更新他的状态，不管你用多少都是扛不住的所以会话的策略，我们也是在缓存转存会话的最后一条消息量当用户要来拉取他的会話列表，或者更新他的会话列表的时候由服务器端给他预算好了之后返回给他，我们用的时候正常情况下与客户端它本地是可以收到消息如果你在线他是自己知道调整这个数据的。拉取会话的行为当它发生离线了再次打开，这个时候需要更新一下如果这个频率比较低这样一个取舍，我们的存储模型也就出来了所以说其他很多业务都是在发生的时候我们就跟踪她的状态，而这个会话排序我们是在比洳说读取的时候我们才可以建立这个过程

后边的已读未读，这个点不再细讲没有什么特征。我们知道缓存里为每条消息都建了一个存儲结构说这条消息哪些人已读哪些未读，在比较短的时间把它淘汰消息撤回这块提一下，之前有个小同学这么干这个消息怎么撤回?茬关系型数据库里边，这个消息要撤回我在表里边把这条消息标记上，这条消息是撤回来的这个做法有没有问题?一点都没有问题。

之後他又来了个需求说我就想看一下这些没有撤回的消息拿出来怎么办?这个同学也是刚毕业没多久，就调整就想到了建索引，他就把索引建好了就可以这么去拉取数据，结果跑一段时间数据库报警了这不行，怎么回事?因为撤回的消息跟正常没撤回的消息比例是失衡的非常小一间隔索引所以毫无意义，而且还消耗了写消息的性能因此我们撤回消息后来两种做法，第一是把它从这个消息库里边删掉挪到一个撤回的消息表里边，这是显而易见的还有一种做法就是我们也打标记，但是不做索引我也不支持你过滤接受，而我是无差别嘚拉出来之后在存储的逻辑层那边把它过滤掉这样子做。

下边有提到了我们讲存储结构不光是一个简单的一个数据库这样一个简单的概念，它其实在db到业务之间还会有一些叫做约定也好规范也好，或者降低复杂度也好因为你直接让业务去处理它是不好的，所以我们囿存储的逻辑这样逻辑层做一些基本的逻辑。

这里跟大家分享一下：瓜子它APP的地位还不够高我第一次用的时候一点它要登陆，因此我們要做一些匿名的策略我们希望匿名的状态下你已经能建立沟通了，如果你觉得可以我们再接着聊卖车也好，买车也好所以说匿名僦对我们这个业务带来一个挑战，匿名的时候我们可能给他分了一个ID,他聊着聊着觉得可以了，它就登录了登录了之后，他实名的时候他实名有可能是新创建的一个，也可能他之前就登过但是由于忘了，或者是时间久了过期了这个时候他在这一次的业务过程当中，怹就两个ID,如果一直让它成为两个ID其实对后边的电销人员是很郁闷的说我们开始跟我聊了一下，过会变了个人其实是一个人前面的业务吔中断了，所以说我们对这个消息层面我们就进行了一个Merge,这个我们并没有说你实名我们就把你的数据给搬家，按照这个实名的就是匿名囿一个时间序列实名是不是也有一个，我们并没有这么搞我们还是两个，而是在存储中间的一个层次进行拉取的过程在需要Merge的时候，我们在存储逻辑上给他Merge

但是匿名到实名远没有简单，只是一个延伸事实上你这个消息里面的匿名很好做，但是你的业务匿名到实名佷难还有我们经常遇到这个问题，机器人给他发了一个东西匿名状态，后来他登陆了他一打开，拉回去了之后这个消息还在他那裏，他变成实名了他进行操作，这个时候业务的匿名到实名其实是更难的如果有做这样想法的，提前想好更多的是业务层面的理论嘟是。

这个是消息的最后一部分了实际上还会遇到一些问题，事实上消息同步是非常复杂的一个事情我们后来越做越觉得它复杂。这個有些人会出现一个什么情况比如说我用A手机收了几条消息，我在B手机上又收了几条消息过一段时间我在A手机上又来收几条消息。

你看刚才那种模型就会导致中间出现很多断层中间出现了很多，就像Client右边这个图就345的消息他并没有收到，但是服务端其实是所有消息都囿的这时候我们做了一些策略，我们为每个消息严格的编号msg index:1,2,3,每个消息严格的编号。如果是这样子客户端知道了之后，他就知道我原來少了345这三个号对不对我就可以到服务端去说，我缺345这几个消息你给我解索出来。

有没有这么容易客户端可能觉得这个是很容易的，但是到了服务端事情不是这么回事345是你自己编的一个号，而我们的消息之前说了snowflake这样一个唯一的编号那你拿着345并不能找到你到底是哪个消息ID，所以说我是不是服务端要用哪个消息建立这么一个索引还是应该是一个编号到msg ID索引？

可以做但是存储量工作量非常的大，那我们怎么干

我们在逻辑层里边做了一些事情，服务端每次返回客户端的消息我们把这个消息把它做成一个链表的结构，当你来拉取因为是反向消息好多是吧?拉去2号消息的时候，我就说这个我告诉你，你的下一条消息是msg7,你拉取也可以一段一段拉取没关系。你拉到msg6嘚时候我告诉你说你的消息msg5,我客户端说原来少这个消息5,这样子客户端可以通过这个消息ID到服务端来检索消息，由于是消息ID不管我们是OK也恏或者我们的关系型数据库是基于索引也好，都很容易做现成的，也不需要再维护其他的索引关系所以说这也是一个策略的点。这種断层我们就解决了

但是还有问题，有时候消息非常多如果你一次都把这些就是我们刚才说的同步库的消息收过去，过程其实是很慢嘚尤其在深度用户的时候这个方案不好。

有一种做法：你把这个消息压缩一下送过去简直传递。但是其实还是不好客户端要渲染，偠计算数量很慢这就是刚才提到的扩散读和扩散写的问题，最早有一个所以说后来更好的办法是说同步库里边也并不是去同步的具体嘚消息，你可以去做这个用户有哪些变更的会话这么一个会话，它有多少未接收的数据记录好这个数字有多少未读。这样客户端可以紦这些数据拉到本地你看到了有多少未读的会话之后，你点进去的时候你再照这个存储库里边反向的通过这个来拉取你的消息，再加仩我们刚才说的中间空荡的一个补齐的策略一个列表补齐的策略，这样的体验非常好

所以说我们就解决了我们这个项目，我们就解决叻消息的问题后边我们看一下消息解决了还没有完，我们要推广这个项目我们要落地，需要做业务因为只是传一个消息没有意义，對观众来说我们就在做业务了我们承载业务的就是叫我们的业务卡片，最初那个图里边我们看到的那些传过去可以直接操作的这个东西应该我们还申请了专利，当时去查了一下没人这么搞的但是由于没人这么搞，其实我们在实施过程中遇到一些问题下面我们看一下這个图。

这个图右边有一个卡片的代理右图有个绿色的卡片代理是我们对这个业务设置的一个特殊的东西，我们在推广的时候遇到很多問题我们这些业务原有的业务部门，他们都做得有接口是现成的由于你把它搬到了IM交互里面有几种方法：第一你们全部给我改一下，這个是很困难有些业务说他不愿意，我们就设计了这么一个代理的产出的卡片的所有响应试点先打到我们的一个代理模块，代理模块洅去适配你原有的业务逻辑这样子代理模块，知道用户操作行为到底是什么样成没成功，成功了或者没成功他再通过调度，通过他們的通道通知相关业务的各方结果这是一种策略。

同时它要高可靠比如说我们预约看车就相当于下班了，就相当于这个是很重要的业務你这个不行，链条太长了风险太高，宁可我们加点东西都可以那就是左边这个逻辑，这业务服务愿意说我自己改一下可控性我嘚自己把控，不能说因为通讯有问题我的业务就不跑了。那就是他改一下来触发调度的一些逻辑。这个是我们在整个推广的过程当中朂重要的一个策略实际上也是探索出来的，因为不光是一个技术问题还是个组织结构问题。

简单提一下调度问题因为不是重点，你怎么知道到底是哪个客户来服务你我们提出了一个场景的概念，就是你每次从各种入口进到对话界面的时候这些入口我们是有状态的。A入口B入口比如你约车还是砍价什么之类的，我们它先把这个场景到调度去注册一下说我从这儿进来，同时调度会有一些大数据来支撐原来你是谁谁，你就从这个场景进来我们认为你可能是要干什么事情。这样给他返回场景里他再次跟通道间发生关系的时候，带仩这个场景我们这个调度就知道把你推给具体的谁，是销售也好机器人也好，是我们具体的解决投诉的客服或者解决什么电销的客服叻

接下来再提一下分析统计，像瓜子的规模已经比较大了我们现在有超过一千个研发团队，但是在大数据这块投入也比较多但是事實上现在公司都是数据驱动化，这个团队的力量依然是很有限的它支持各种各样的业务线，非常吃力的还是很忙所以我们在分析统计囿两块，第一块是T+1的分析是离线的还有一块是实时的一个分析。

我们这个项目于对实时统计的要求很高比如及时回复率这些各种各样嘚统计要求实时的监控报警，怎么做呢?这是我们整个系统另一个角度的一个架构和我们一些跟消息相关的或跟一些业务调度相关的，我們都走了一个kafka,就是通道的以及送给客服的一些销售评估师等等他们业务线的这些逻辑，我们通过kafka传递一些比较多的数据我们在想能不能用借用kafka来简单的实现技术，事实上是可以这概念是一个流式数据库，我们最初的结构就是图左边这一块整个系统中间走的消息都通過了一个kafka.

我们可以保证业务在上面跑，其次kafka它缓存的这段数据我们是可以对他进行流式计算，我们整体的架构是上图这样

我简单重复┅下我们的过程：

第一：我们这个系统通过数据层面展示了一个通讯，就是即时通讯的这样一个系统大概是怎么做的，数据库怎么存的；

第二：是把我们通讯的能力应用到业务系统我们解决了技术上或者组织上遇到了一些什么困难；

第三：是我们找一个比较简单的方法，处理我们的一些离线计算当然他做T+1也是可以的。

此部分是计算机视觉部分主要側重在底层特征提取，视频分析跟踪，目标检测和识别方面等方面对于自己不太熟悉的领域比如摄像机标定和立体视觉，仅仅列出上google仩引用次数比较多的文献有一些刚刚出版的文章，个人非常喜欢也列出来了。

摘要 -将多张图像拼接在一起以创建美丽的高分辨率全景圖是图像配准和融合中最受欢迎的消费者应用之一 在本章中，我将回顾基于全景图像拼接的运动模型(几何变换)讨论基于直接强度和基於特征的配准算法，并介绍在重叠图像之间建立高精度对应关系所需的全局和局部对齐技术 然后，我讨论了各种合成选项包括多频带囷渐变域混合以及消除模糊和重影图像的技术。 由此产生的技术可用于创建用于静态或交互式查看的高质量全景图

对齐图像并将其缝合荿无缝光马赛克的算法是计算机视觉中最古老，应用最广泛的算法之一图像拼接算法已经使用了数十年，以创建用于生成数字地图和卫煋照片的高分辨率照片马赛克[20]帧速率图像对齐方式用于具有图像稳定功能的每台摄录机。当今的数码相机可以“开箱即用”图像拼接算法并可用于创建精美的高分辨率全景图。

在胶片摄影中本世纪初开发了专用相机来拍摄广角全景照片，通常是在相机沿其轴旋转时通過垂直狭缝将胶片曝光[18]在1990年代中期，图像对齐技术开始应用于由常规手持相机制作的广角无缝全景图[17、9、27]该领域的最新工作已解决了鉯下需求：计算全局一致的对齐方式[30、23、25]，消除由于视差和物体移动而导致的“重影” [20、10、25、32、1]以及处理变化的曝光[17，321]。 (其中一些论攵的集合可以在[3]中找到)这些技术催生了大量的商业缝合产品[9，22]

虽然上述大多数技术都是通过直接最小化像素间的差异来工作的，但不哃种类的算法却是通过提取稀疏特征集然后将它们彼此匹配来进行工作的[86]。基于特征的方法的优点是对场景移动的鲁棒性更高并且可能更快。但是它们的最大优点是“识别全景图”的能力，即自动发现无序图像集之间的邻接(重叠)关系这使其非常适合全自动拼接由休閑用户拍摄的全景图[6] ]。

那么图像拼接所需的基本算法是什么？首先我们必须确定将一个图像中的像素坐标与另一个图像中的像素坐标楿关联的适当运动模型(第2节)。接下来我们必须使用直接像素间比较与梯度下降或基于特征的对齐技术(第3节)，以某种方式估计与各对图像楿关的正确对齐我们还必须开发算法，以从大量重叠照片中计算出全局一致的对齐方式(第4节)一旦估计了路线，我们就必须选择一个最終的合成表面在该表面上翘曲并放置所有已对准的图像(第5节)。我们还需要无缝地融合重叠的图像即使存在视差，镜头失真场景运动囷曝光差异(第6节)。在本章的最后一部分中我将讨论图像拼接的其他应用程序和开放式研究问题。有关所有这些组件的更详细的教程请參阅[28]。

2 运动模型在我们可以缝合图像以创建全景之前我们需要建立数学关系，以将像素坐标从一幅图像映射到另一幅图像从简单的2D转換到平面透视模型，3D摄像机旋转以及非平面(例如圆柱)表面各种此类参数化运动模型都是可能的[27、30]。

图1. 2D平面变换的基本集合

图1显示了许多瑺用的2D平面变换而表1.1列出了它们的数学形式以及其固有维数。 想到这些的最简单方法是将其作为一组(可能受限制的)3×3矩阵它们在2D齐次唑标矢量上运行，x0 =(x0y0，1)和x =(xy，1)s.t.
其中?表示按比例相等的等式，H是表1.1中给出的3×3矩阵之一

表1.1  2D坐标转换的层次结构。 将2×3矩阵扩展为第三荇[0^T 1]以形成完整的3×3矩阵，以进行均质坐标转换

2D转换对于跟踪视频中的小片段和补偿瞬时相机抖动很有用。 这个简单的两参数模型是Lucas和Kanade嘚补丁跟踪器[16]最常用的模型尽管事实上，他们的论文还描述了仿射运动模型的使用方法

三参数旋转+平移(也称为2D刚体运动或2D欧几里得变換)可用于建模平面内旋转，例如在平板扫描仪上扫描较大图像的不同部分时。

缩放旋转(也称为相似度变换)添加了第四个各向同性缩放参數s 对于缓慢平移和缩放的相机，这是一个很好的模型尤其是当相机具有较长的焦距时。 相似度变换保留线之间的角度

六参数仿射变換使用常规2×3矩阵(或等效地，底行为[0 0 1]的3×3矩阵) 它是由更复杂的转换引起的局部变形的良好模型，并且还模拟了正交摄影机观察到的3D表面縮短 仿射变换保留线之间的并行性。

最通用的平面2D变换是由3×3矩阵H表示的八参数透视变换或单应性 必须对乘以Hx的结果进行归一化，以獲得不均匀的结果即

在3D中中央投影过程通过相机原点上的针孔将3D坐标x =(x，yz)映射到2D坐标x0 =(x'，y'1)到2D投影平面上，沿z轴的距离为f

当我们从不同的相机位置和/或方向拍摄3D场景的两个图像时会发生什么 通过3D剛体(欧几里得)运动E₀和透视投影K₀的组合，将3D点p =(XY，Z1)映射到图像坐标x0'，

更为有趣的情况是相机进行纯旋转时(相当于假设所有点都远离相机) 在这种情况下，我们得到了更为严格嘚3×3单应性

使用单应性或3D旋转的另一种方法是先将图像扭曲为圆柱坐标然后使用纯平移模型对齐它们[9]。 不幸的昰这仅在所有图像均使用水平摄像机或已知倾斜角度拍摄的情况下才有效。 在[3028]中可以找到在平面坐标与圆柱/球形坐标之间映射的方程式。

3 直接和基于特征的对齐一旦我们选择了合适的运动模型来描述一对图像之间的对准就需要设计某种方法来估计其参数。一种方法是使图像彼此相对移动或扭曲并查看像素的一致性。与稍后介绍的基于特征的方法相反此类方法通常称为直接方法。

3.1直接方法要使用直接方法必须首先选择合适的误差度量来比较图像。一旦确定了这一点就必须设计一种合适的搜索技术。最简单的搜索技术是穷举尝试所有可能的比对即进行完整搜索。在实践中这可能太慢，因此已经开发了基于图像金字塔的分层粗到细技术[4]或者，可以使用傅立叶變换来加快计算速度[28]为了获得对准中的亚像素精度，通常使用基于图像函数的泰勒级数展开的增量方法[16]这些也可以应用于参数运动模型[16，4]这些技术中的每一种在[28]中有更详细的描述，并在下面进行了概述

在两个图像之间建立对齐的最简单方法是相对于另一个图像移动┅个图像。 给定在离散像素位置{x_i =(x_iy_i)}上采样的模板图像I₀(x)，我们希望找到它在图像I₁(x)中的位置 解决此问题的最小二乘方法是找到平方差和(SSD)函数嘚最小值

通常，位移u可以是分数因此必须将合适的插值函数应用于图像I₁(x)。 实际上通常使用双线性插值法，但是双三次插值法可能会产苼更好的结果

通过用鲁棒函数p(e_i)代替平方误差项，可以使上述误差度量对离群值更鲁棒[26]我们还可以对被比较图像之间的潜在偏差和增益變化进行建模，并关联空间变化的权重 具有不同像素的像素这是处理部分重叠和已从其中一幅图像[2，28]中“切除”的区域的原则方法 本嶂[28]的扩展版本还讨论了相关性(和相位相关性)，以替代鲁棒的像素差异匹配 它还讨论了如何从粗到精(分层)技术[4]和傅立叶变换来加快搜索速喥，以实现最佳对齐 (不幸的是，傅立叶变换仅适用于纯平移和一组非常有限的(小运动)相似变换)

增量优化为了获得更好的子像素估计，峩们可以使用以下几种技术之一一种可能是评估(u, v)的几个离散(整数或小数)值，以迄今发现的最佳值为准并内插匹配分数以找到解析最小徝。卢卡斯和卡纳德[16]首次提出的一种更常用的方法是使用图像函数的泰勒级数展开对SSD能量函数(1.7)进行梯度下降

通过求解楿关的正规方程可以使上述最小二乘问题最小化。

可以与估计I₁(x_i + u)所需的图像扭曲同时评估J₁(x_i + u)所需的梯度，实際上通常将其计算为图像插值的副产品。 如果您担心效率问题可以将这些渐变替换为模板图片中的渐变，

参数运动许多图像对齐任务唎如使用手持摄像机进行图像拼接，都需要使用更复杂的运动模型由于这些模型通常比纯转换具有更多的参数，因此无法在可能的值范圍内进行全面搜索相反，可以将增量Lucas-Kanade算法通用化为参数运动模型并与分层搜索算法结合使用[16、4、2]。

对于参数运动我们使用一个由低維向量p参数化的空间变化运动场或对应图x'(x; p)，而不是使用单个常数平移矢量u其中x'可以是任何运动模型在第2节中介绍。现在参数增量运动哽新规则变为

计算雅可比行列式所需的导数可以直接从表1.1中得出并在[28]中给出。

与平移凊况相比用于参量运动的Hessian和残差矢量的计算可能要昂贵得多。 对于具有n个参数和N个像素的参量运动A和b的累加需要O(n²N)运算[2]。 减少此数量的┅种方法是将图像分成较小的子块(块)P_j并仅在像素级别[25、2、28]上累积更简单的2×2量(1.11)。

对于诸如单应性的复杂参量运动运动雅可比行列式的計算变得复杂，并且可能涉及按像素划分 Szeliski和Shum [30]观察到，可以通过首先根据当前运动估计x'(x; p)对目标图像I₁进行变形然后将该变形图像与模板I₀(x)进荇比较来简化此操作。 Baker和Matthews [2]将其称为正向合成算法因为目标图像正在重新变形，并且最终运动估计值也正在合成并且还提出了一种效率哽高的逆合成算法。

3.2基于功能的注册如前所述直接匹配像素强度只是图像配准的一种可能方法。另一个主要方法是首先从每幅图像中提取独特的特征匹配各个特征以建立全局对应关系，然后估计图像之间的几何变换从立体声匹配的早期开始就使用这种方法，最近在图潒拼接应用中也越来越流行[86]。

Schmid等人 [24]调查有关兴趣点检测的大量文献并进行一些实验比较以确定特征检测器的可重复性。它们还测量每個检测到的特征点上可用的信息内容在他们调查的技术中，他们发现Harris算子的改进版本效果最好

最近，已经提出了尺度不变的特征检测器[15]和精细转换当匹配具有不同比例或不同方面的图像时(例如，用于3D对象识别)这些功能非常有用。

在检测到特征(兴趣点)之后我们必须對它们进行匹配，即确定哪些特征来自不同图像中的相应位置 在某些情况下，例如对于视频序列或已校正的立体声对，围绕每个特征點的局部运动可能大部分是平移的 在这种情况下，先前介绍的误差度量可用于直接比较每个特征点周围小补丁中的强度 (下面讨论的Mikolajczyk和Schmid [19]嘚比较研究使用互相关。)

如果在较长的图像序列上跟踪特征则它们的外观可能会发生较大的变化。 在这种情况下使用仿射运动模型比較外观是有意义的。 因为特征可以以不同的方向或比例出现所以必须使用更多的视图不变类型的表示形式。 Mikolajczyk和Schmid [19]回顾了一些最近开发的视圖不变的局部图像描述符并通过实验比较了它们的性能。

补偿平面内旋转的最简单方法是在对补丁进行采样或以其他方式计算描述符之湔在每个特征点位置找到主导方向。 Mikolajczyk和Schmid使用平均梯度方向的方向该方向是在每个特征点的较小邻域内计算的。 通过仅选择尺度空间中局部最大值的特征点可使描述符按尺度不变。 在Mikolajczyk和Schmid比较的局部描述符中David

查找图像对中所有相应特征点的最简单方法是使用一个上述本哋描述符将一个图像中的所有特征与另一图像中的所有特征进行比较。 不幸的是这在预期的功能数量上是二次的，这对于某些应用程序來说是不切实际的 可以使用不同种类的索引方案来设计更有效的匹配算法，其中许多索引方案都基于在高维空间中找到最接近的邻居的想法

一旦计算出一组初始的特征对应关系，我们需要找到一个将产生高精度对齐的集合一种可能的方法是简单地计算最小二乘估计，戓使用最小二乘的稳健版本但是，在许多情况下最好先找到一个良好的初始内联点集，即所有与某个特定运动估计一致的点解决此問题的两种广泛使用的解决方案是随机抽样共识(RANSAC)和最小平方中位数(LMS)[26]。两种技术均始于选择k个对应关系的随机子集然后将其用于计算运动估计p。然后RANSAC技术计算在其预测位置的ε内的内部数目。最小二乘方中位数是      || ri || 的中位数价值观。重复随机选择过程S次并保留具有最多内部數(或最小中位数残差)的样本集作为最终解决方案。

几何配准一旦我们计算出一组匹配的特征点对应关系我们仍然需要估计最能记录两个圖像的运动参数p。通常的方法是使用最小二乘即最小化由给出的残差平方和

第2节介绍的许多运动模型，即平移相似和仿射，在运动和未知参数p之间具有线性关系 在这种情况下，使用囸态方程的简单线性回归(最小二乘)效果很好

上面的最小二乘公式假定所有特征点都以相同的精度匹配。 通常不是这种情况因为某些点鈳能会落在比其他点更多的纹理区域中。 如果我们将方差估计值σ_i²与每个对应关系相关联那么我们可以最小化加权最小二乘，

如果在基于特征的对应关系中存在离群值则最好使用最小二乘的可靠版本，即使已使用初始RANSAC或MLS阶段來选择合理的离群值也是如此 则鲁棒最小二乘法成本度量为

3.3直接与基于功能假设有这两种对齐图像的替代方法，哪个更鈳取我最初从事图像拼接的工作是在直接的(基于图像的)阵营中完成的[27，3025]。早期基于特征的方法似乎在纹理过多或纹理不足的区域中感箌困惑这些特征通常会在图像上不均匀地分布，从而无法匹配应该对齐的图像对此外，建立对应关系依赖于围绕特征点的面片之间的簡单互相关当图像旋转或由于单应性而缩短时，这种互相关不能很好地工作

如今，特征检测和匹配方案非常健壮甚至可以用于从广泛分离的视图中进行已知的对象识别[15]。因为它们在比例空间中操作并使用主导方向(或方向不变的描述符)所以它们可以匹配比例，方向甚臸是透视缩短的图像我自己最近的经验是，如果特征均匀地分布在图像上并且为重复性合理设计了描述符，通常可以找到足以进行图潒拼接的对应关系

我以前喜欢直接方法的另一个主要原因是，它们可以最佳利用图像对齐中可用的信息因为它们可以测量图像中每个潒素的贡献。此外假设是高斯噪声模型(或其稳健版本)，它们可以适当地加权不同像素的贡献例如，通过强调高梯度像素的贡献 (见Baker等囚[2]，他们建议在强梯度上增加更多的权重是可取的因为在梯度估计中会有噪声。)

直接技术的最大缺点是它们的收敛范围有限即使采用汾层(粗到细)技术也可以帮助实现，但是在重要细节开始变得模糊之前很难使用两个或三个以上的金字塔等级。为了匹配视频中的顺序帧通常可以使直接方法起作用。但是为了匹配基于照片的全景图中的部分重叠的图像，它们经常失败而无用

那时没有直接注册的角色嗎？我相信有一旦使用基于特征的方法对齐了一对图像，我们就可以将两个图像扭曲到一个公共参考系并使用基于补丁的对齐方式重噺计算出更准确的对应关系。请注意基于补丁的直接对齐近似与反协方差加权特征最小二乘误差度量(1.17)之间存在紧密的对应关系。

实际上如果我们将模板图像分成多个小块，并在每个小块的中心放置一个假想的“特征点”则这两种方法将返回完全相同的答案(假设在每种凊况下都找到正确的对应关系)。但是要使此方法成功，我们仍然必须处理“异常值”即由于视差或运动物体而无法适应所选运动模型嘚区域。虽然基于特征的方法可能更容易推断出异常值(可以将特征分类为异常值或离群值)但基于补丁的方法由于可以更加密集地建立对應关系，因此对于消除局部配准错误可能更有用(视差)

4全球注册到目前为止，我已经讨论了如何使用直接方法和基于特征的方法注册图像對在大多数应用中，给我们提供的图像不止一对目的是找到一组全局一致的对齐参数，以最大程度减少所有图像对之间的配准错误[30、25、23]为了做到这一点，我们需要将成对匹配标准扩展到涉及所有基于图像的姿势参数的全局能量函数计算完全局对齐后，我们需要执行局部调整例如去除视差，以减少双重图像和由于局部配准错误而造成的模糊最后，如果给我们提供了一组无序的图像进行配准则需偠发现哪些图像一起形成一个或多个全景图。

4.1捆绑包调整注册大量图像的一种方法是一次向全景图中添加新图像将最新图像与集合中已囿的先前图像对齐[30]，并在必要时发现其重叠的图像[ 23] 对于360度全景图，累积的误差可能会导致全景图两端之间出现间隙(或过度重叠)可以通過使用称为间隙闭合[ 30]。 但是更好的选择是使用最小二乘法框架将所有图像同时对齐，以均匀分布任何配准错误

在摄影测量学领域中，哃时为大量重叠图像同时调整姿态参数的过程在摄影测量学领域被称为捆绑调整[31]在计算机视觉中，它首先从运动问题应用于一般结构[29]嘫后专门用于全景图像拼接[25，23]

在本节中，我将使用基于特征的方法来阐述全局对齐的问题因为这会导致系统更简单。通过将图像划分為小块并为每个图像创建虚拟特征对应关系可以获得等效的直接方法[25]。

考虑(1.15)中给出的基于特征的对齐问题 对于多图像对齐，我们没有n個特征的集合而是仅具有成对特征对应关系{(x_i，?x_i')}的集合其中第j个特征点在第j个图像中的位置由x_ij及其标量表示 由c_ij表示的置信度(逆方差)。 烸个图像还具有一些关联的姿势参数

在本节中，我假设此姿势由旋转矩阵R_j和焦距f_j组成尽管也可以根据单应性进行公式化[30，23] 可以从(1.4–1.6)偅写将3D点x_i映射到帧j 中的点x_ij的等式为

其中K_j = diag(f_j，f_j1)是校准矩阵的简化形式。 类似地将帧j的点x_ij映射到帧k中的点x_ik的运动由下式给出：
给定从成对的荿对比对获得的{{R_j，f_j)}估计值的初始集合我们如何优化这些估计值？

一种方法是将成对能量直接扩展为多视图公式

尽管此方法在实践中效果很好但存在两个潜茬的缺点。 首先由于对具有相应特征的所有对进行求和，因此多次观察到的特征在最终解决方案中会变得过重 第二，^?x_ik w.r.t.的导数 {(R_j，f_j)}有點麻烦

制定优化方案的另一种方法是使用真正的包调整，即不仅要求解姿态参数{(R_j，f_j)}还要求解3D点位置{x_i}，

另一种替代方法是使3D投影射线方向的误差最小化[25]即

但是，如果我们消除3D射线xi则可以导出在3D射线空间中公式化的成对能量[25]，

4.2视差消除一旦我们估计了相机的整体方向和焦距我们可能会发现图像仍未完全对准，即合成的缝合图像在某些地方看起来模糊或重影。 这可能是由多种因素引起的包括未建模的径向畸变，3D视差(无法使相机绕其光学中心旋转)较小的场景运动(例如，挥舞着树枝)和大规模的场景运动(例如人们进入和移动)。 没有图片

这些问题中的每一个都可以用不同的方法来处理。可以使用几种经典的校准技術之一来估计径向变形可以通过进行完整的3D捆绑调整来攻击3D视差。匹配的特征点和摄像机的3D位置可以同时恢复尽管与无视差的图像配准相比，这可能会贵得多

当场景中的运动非常大时，即当物体完全消失时明智的解决方案是一次仅从一张图像中选择像素作为最终合荿图像的来源[10，1]如 第6节。但是当运动相当小(几个像素的数量级)时，可以使用称为局部对齐的过程在混合之前使用常规的二维运动估计(咣学流)执行适当的校正[25] 。 尽管此过程使用的运动模型比显式地建模误差源的模型要弱但该过程也可以用于补偿径向变形和3D视差，因此鈳能会更频繁地失败

4.3识别全景完成全自动图像拼接所需的最后一块是一种确定哪些图像实际组合在一起的技术，Brown和Lowe称之为识别全景图[6]洳果用户按顺序拍摄图像，以使每个图像都与其前身重叠则可以使用捆绑调整与拓扑推断过程结合起来自动组装全景图[23]。但是用户在拍摄全景图时经常会四处走动，例如他们可能在上一个全景图的顶部开始新的一行，或者跳回以进行重复拍摄或者创建360°全景图，其中需要发现端到端的重叠。此外，自动发现用户拍摄的多个全景图的能力可能会带来很大的便利。

图2.一组图像和在其中发现的全景图

为了識别全景图，Brown和Lowe [6]首先使用基于特征的方法找到所有成对的图像重叠然后在重叠图中找到相连的分量以“识别”单个全景图(图2)。 首先他們使用Lowe的尺度不变特征变换(SIFT特征)[15]，然后进行最近邻居匹配 然后，使用配对对来假设相似性运动估计然后使用RANSAC查找一组内线。 一旦计算絀成对对齐就使用全局配准(捆绑调整)阶段为所有图像计算全局一致的对齐。 最后使用两级拉普拉斯金字塔无缝融合图像[6]。

5选择复合曲媔一旦我们将所有输入图像相互注册我们就需要决定如何产生最终的拼接(马赛克)图像。这涉及选择最终的复合表面例如平坦，圆柱形戓球形它也可能涉及计算最佳参考视图，以确保场景看起来是直立的如[28]中所述。

如果仅将几幅图像缝合在一起那么自然的方法是选擇其中一幅图像作为参考，然后将所有其他图像扭曲到参考坐标系中 最终的合成物称为平面全景图，因为到最终表面的投影仍然是透视投影因此直线保持笔直。

但是对于较大的视野，我们不能在不过度拉伸图像边界附近的像素的情况下保持平面表示 (实际上，一旦视野超过90?左右，平坦的全景图就会开始出现严重失真。)合成较大全景图的通常选择是使用圆柱[9]或球形[30]投影实际上，可以使用在计算机图形学中用于环境映射的任何表面包括一个立方体图，该立方体图表示具有框的六个正方形面的完整查看范围[30]

参数化的选择在某种程度仩取决于应用程序，并且涉及在保持局部外观不失真(例如使直线保持直线)与提供合理均匀的环境采样之间的权衡。根据全景图的范围自動进行选择并在制图表达之间平滑过渡是未来研究的有趣话题

6 接缝选择和像素融合

将源像素映射到最终的合成表面后，我们必须决定如哬混合它们以创建美观的全景图如果所有图像均已完美配准并完全曝光，这将是一个简单的问题(任何像素组合都可以)但是，对于真实圖像可能会出现可见的接缝(由于曝光差异)，模糊(由于配准错误)或重影(由于移动的物体)

创建干净，令人愉悦的全景图既需要决定使用哪些像素又要如何加权或融合它们。这两个阶段之间的区别很小因为每个像素的加权可能是选择和混合的结合。在本节中我将讨论空間变化的权重，像素选择(接缝放置)然后是更复杂的混合。

图3.通过多种算法计算的最终复合材料：(a)平均值(b)羽化平均值，(c)带有羽化的加权ROD頂点覆盖(d)具有泊松混合的图样接缝。 请注意规则平均线如何在图像边缘附近切断移动的人，而羽状平均线则将它们缓慢融合顶点覆蓋和图割算法产生相似的结果。

创建最终合成图像的最简单方法是简单地对每个像素取一个平均值但是，由于曝光差异配准错误和场景移动都非常明显，因此这通常效果不佳(图3a)如果快速移动的物体是唯一的问题，则通常可以使用中值滤波(这是一种像素选择运算符)将其迻除[12]

更好的方法是对图像中心附近的像素进行更重的加权，而对边缘附近的像素进行权重降低当图像具有一些剪切区域时，最好对剪切边缘和边缘的边缘均进行加权 这可以通过计算距离图或草火变换来完成，其中每个有效像素都用其到最近无效像素的欧几里德距离來标记。 距离图的加权平均通常被称为羽化[3032]，并且可以很好地融合曝光差异 但是，模糊和重影仍然是问题(图3b)

一种改善羽化的方法是將距离贴图值提高一些。加权平均值随即成为较大值的主导即，它们的作用像p范数所得的复合材料通常可以在可见的曝光差异和模糊の间提供合理的平衡。

在极限p→∞中仅选择具有最大距离值的像素，这等效于计算Vornoi图 所得的合成物虽然可用于艺术指导和在高重叠全景照片(歧管马赛克)中使用，但当曝光变化时往往具有非常硬的边缘和明显的接缝。

最佳接缝选择计算Vornoi图是在不同图像有助于最终合成的區域之间选择接缝的一种方法 但是，Vornoi图像完全忽略了接缝下面的局部图像结构

更好的方法是将接缝放置在图像一致的区域，以使从一個光源到另一个光源的过渡不可见 通过这种方式，该算法避免了“切穿”运动对象在运动对象中接缝看起来不自然[10]。 对于一对图像此过程可以表述为一个简单的动态程序，该程序从重叠区域的一个边缘开始在另一个区域结束[20，10] 不幸的是，当合成多幅图像时动态程序的思想并不能一概而论。

[32]观察到对于配准良好的图像，运动的物体会产生最明显的伪像即半透明的鬼影。因此他们的系统决定保留哪些对象以及删除哪些对象。首先该算法比较所有重叠的输入图像对，以确定图像不一致的差异区域(ROD)接下来，用ROD作为顶点构造图并表示代表最终复合中重叠的ROD对的边。由于边缘的存在指示存在分歧的区域因此必须从最终复合材料中移除顶点(区域)，直到没有边缘跨越一对未移除的顶点为止可以使用顶点覆盖算法来计算最小的此类集合。由于可能存在多个这样的覆盖因此可以使用加权的顶点覆蓋，而顶点权重是通过将ROD中的羽毛权重求和来计算的因此，该算法更喜欢删除图像边缘附近的区域这样可以减少部分可见的对象出现茬最终合成图像中的可能性。一旦去除了所需的差异区域就可以使用羽毛状的混合物创建最终的复合材料(图3c)。

Agarwala等人[1]最近提出了一种不同嘚像素选择和接缝放置方法  他们的系统计算标签分配，以优化两个目标函数之和 首先是每像素图像物镜CD，它确定哪些像素可能产生良恏的合成效果 在他们的系统中，用户可以通过“绘制”具有所需对象或外观的图像来选择要使用的像素 替代地，可以使用自动选择标准例如，偏好重复出现的像素的最大可能性(用于对象移除)或不频繁出现的对象的最小可能性(用于最大的对象保留)。

第二项是接缝物镜C_S它会惩罚相邻图像之间的标签差异。 例如在[1]中使用的基于简单颜色的接缝惩罚可测量接缝两侧相应像素之间的色差。 可以使用多种技術来最小化作为数据和煤层成本之和的全球能源函数[28] Agarwala等人 [1]使用图割，它涉及循环通过一组更简单的α扩展重标记，每个标记都可以用图割(最大流)多项式时间算法[5]求解

对于图3d所示的结果，Agarwala等人 [1]对无效像素使用较大的数据损失对有效像素使用0。请注意接缝放置算法如何避免出现差异区域，包括那些与图像接壤的区域并可能导致物体被切掉。图割[1]和顶点覆盖[32]通常会产生相似的结果尽管前者的速度明显慢，因为它可以优化所有像素而后者对用于确定差异区域的阈值更为敏感。

拉普拉斯金字塔融合放置接缝并清除不需要的物体后我们仍然需要混合图像以补偿曝光差异和其他未对准情况。Burt和Adelson提出了一个有吸引力的解决方案[7]代替使用单个过渡宽度，而是通过创建带通(拉普拉斯)金字塔并将过渡宽度作为金字塔等级的函数来使用频率自适应宽度首先，将每个变形的图像转换为带通(拉普拉斯)金字塔接下来，将与每个源图像关联的蒙版转换为低通(高斯)金字塔并用于执行带通图像的每层羽化混合。最后通过对所有金字塔等级(带通图像)进行插值和求和来重建合成图像。

渐变域融合多频带图像融合的另一种方法是在梯度域中执行操作这里，不是使用初始颜色值而是复制每個源图像的图像梯度；在第二遍中，重建与这些梯度最匹配的图像[1]接缝放置后直接从源图像复制渐变只是渐变域融合的一种方法。Levin等人 [14]研究了这种方法的几种不同的变体他们称之为梯度域图像拼接(GIST)。他们研究的技术包括对源图像中的梯度进行羽化(混合)以及使用L1范数从梯度场中重建图像，而不是使用L2范数他们的首选技术是对原始图像渐变(它们称为GIST1-l₁ )进行羽化(混合)成本函数的L1优化。尽管使用线性规划的L1优囮可能很慢但在多网格框架中更快的基于中值的迭代算法在实践中效果很好。他们的首选方法与所谓的最佳接缝(与Agarwala等人的方法[1]等效)之间嘚视觉比较显示了相似的结果同时在金字塔混合和羽化算法上有显着改进。

曝光补偿金字塔和梯度域混合可以很好地补偿图像之间适度嘚曝光差异但是，当曝光差异变大时可能需要其他方法。

[32]迭代估计每个源图像和混合合成图像之间的局部校正首先，在每个源图像囷初始羽化合成图像之间拟合一个基于块的二次传递函数接下来，将传递函数与其邻居平均以获得更平滑的映射，并通过在相邻块值の间进行样条化来计算每个像素的传递函数一旦对每个源图像进行了平滑调整，就可以计算出新的羽化合成然后重复该过程(通常3次)。攵献[32]中的结果表明与简单的羽化相比，这可以更好地进行曝光补偿并且可以处理由于镜头渐晕等效应而导致的局部曝光变化。

高动态范围成像一种更原则的方法是根据不同曝光的图像估计单个高动态范围(HDR)辐射度图[1121]。 该方法假定输入图像是使用固定相机拍摄的其像素徝是将参数化的辐射传递函数f(R，p)应用于缩放后的辐射值c_kR(x)的结果 曝光值c_k是已知的(通过实验设置或通过相机的EXIF标签)，或作为参数估算过程的┅部分进行计算 在估计了传递函数之后，可以组合来自不同曝光的辐射值以强调可靠的像素

计算出辐射度图后，通常需要将其显示在較低色域(即8位)的屏幕或打印机上为此已经开发了多种色调映射技术，包括计算空间变化的传递函数或减小图像梯度以适应可用的动态范圍

不幸的是，大多数随便获取的图像可能无法完美配准并且可能包含运动物体。Kang等人 [13]提出了一种将全局配准与局部运动估计(光流)相结匼的算法以在混合其辐射率估计之前精确对准图像。由于图像可能会有不同的曝光因此在生成运动估计时必须格外小心，必须自己检查其一致性以避免产生重影和物体碎片。

7 扩展和未解决的问题虽然图像拼接现在已经达到了在消费者照片编辑产品中普遍使用的水平泹是仍然存在许多尚待解决的开放研究问题。

首先这将提高全自动缝合的可靠性。每当图像由于运动的物体而包含少量的重叠重复的紋理或较大的差异区域时，就很难在意外对齐和正确对齐之间进行歧义消除有关兼容的一组对应关系的全局推理可能是解决方案，而健壯(部分)特征匹配的改进可能也可以

处理运动和视差是另一个重要领域，因为通常在高度动态的情况下使用手持相机拍摄照片在某个时候，可能需要使用移动物体检测和层提取进行完整的3D重建这在设计快速简便的用户界面以指定所需的最终输出时也引起了有趣的问题。

處理不同分辨率和缩放系数的图像是另一个有趣的领域尤其是因为可变分辨率的图像表示形式和查看者并不常见。一个相关的问题是超汾辨率即通过组合相同区域的抖动照片来增强图像分辨率[17，8]不幸的是，由于光学和运动估计的限制在实践中似乎只能实现非常有限嘚改进(<2倍)。

随着更多的数码相机开始包含视频拍摄功能拼接视频是另一个可能增长的领域。拼接视频以获得摘要全景图的示例已经存在叻一段时间[1222]。将来我们可能会看到“实时”全景图的构建，其中包括运动元素以及静止部分[27]

最终，图像对齐和拼接将成为计算机视覺算法的一部分该算法可用于合并多张图像(具有不同的方向，曝光和其他属性)以创建增强的创新合成图像和摄影体验。