文字：许殊、袁艺宁、孙嘉 摄影：雷璟晗 摄像：孙嘉
>>>人物名片
鲁小虎：遥感信息工程学院2014级硕士研究生，已在MACV、ICPR、ICIP、ISPRS和ICIA等国际会议上以第一作者身份发表会议论文5篇，获得2015年中航四维奖学金、2016年研究生国家奖学金，并获专利3项。
>>>报告现场
3月3日19:30，鲁小虎做客GeoScience Café第151期学术交流活动，和大家分享了研究生三年的研究成果与心得体会。报告主要分为四部分：第一部分介绍了会议论文写作的结构技巧；第二部分介绍了三种不同类别的聚类分析，重点讲述了Plinkage 算法；第三部分介绍了灭点提取的研究成果；第四部分介绍了研究心得体会。
论文写作结构技巧
鲁小虎以他最近修改的一篇论文为例，首先分析了Introduction部分所做的几处修改。
原文中Introduction部分的第一段介绍了研究背景和研究进展，第二段将目前已有的Camera pose estimation算法归纳为三类，接下来的三段分别对这三类算法做了介绍。然而，鲁小虎认为，这样的结构并不能让读者对全文的逻辑有一个很清晰的理解。
鲁小虎在论文Introduction部分第一段的结尾加入了总结句：Among all these standard procedures of MVO, two are key issues: camera pose estimation and camera pose optimization。总起之后，自然而然地引出下文的两大方面：Camera pose estimation和Camera pose optimization，并在Camera pose estimation一段中概括了三类方法。对具体介绍方法的三段内容不做大的修改，但都使用方法名作为段落开头。
点评完Introduction部分之后，他介绍了一篇好论文应满足的三点结构特征：有始有终，回应期待；结构明确，展现诚意；草蛇灰线，伏脉千里。
有始有终，回应期待是指前面写了一句话，后面紧接着的最好是与前一句相关的、层次递进的一件事情。做到这一点的技巧是：前后句主语、宾语之间要保持联系；关键词要前后一致。
结构明确，展现诚意是指在段落与段落之间要展现逻辑感和层次性。前文提到的东西，后文要有所体现，展现出写作者的“诚意”。做到让读者看到前面的段落就可以猜到后面的段落要讲什么。
段落结构分为总分结构及并列结构。对于总分结构，作为会议论文，越直白越好；对于并列结构，可以采用例如：相同的命名风格，相同的字型字号，段落第一句即为中心句等方式突出处于并列结构的几段。
草蛇灰线，伏脉千里是指对于整篇文章的脉络结构，要注意提炼主题并紧扣主旨，串联全文。当然，做到这一点需要一定的沉淀，并不容易，也并非必需。
聚类分析
这一部分主要以二维点集为例，介绍聚类分析。聚类分析即把对象的集合分为由类似的对象组成的多个类的分析过程。换言之，就是把属于同一类别的点聚到一起，不同类别的点之间分开。
聚类分析中有两个基本构成要素，元素（elements）和聚类法则（principle）。元素由数据（data points）和聚类中心（the cluster center部分算法需要）组成。聚类法则确定了聚类元素之间的相互关系。
对于聚类算法的分类，鲁小虎从元素的角度出发将现有的算法分成了center-based，point-center based和point-point based三类，并详细介绍了三个类别对应的三个典型的代表算法：
（一） Center-based:Density Peak
Density Peak是一个典型的center-based算法，利用聚类中心点的两个特点确定聚类中心点。
图1 聚类中心点特点
聚类中心点始终有如下两个特点：
1. 聚类中心点(C1,C2,C3)周围的密度会比其他点周围的密度大；
2. 聚类中心点的周围应该是非中心点，换言之，该聚类中心点应该离其他的聚类中心点距离较大。
Density Peak算法通过将以上两点转化成两个参数进行量化来解决聚类问题，该算法包含三个步骤：
(1)求解密度，这里只演示一种常用的密度解算方法
点i的密度
上述公式中
等价于与i点距离小于dc的点数
(2)求聚类中心点间的最小距离
每个i点到比它密度大的点的所有距离中的最小值，记为每个点的第二个特征。用密度 作为X轴，最小距离 作为Y轴，做出散点图如图2。该散点图可把聚类中心点与非聚类中心点的差别表现出来。
图2 Density Peak散点图
(3)选择图2中合适的点作为聚类中心点。一旦聚类中心点确定完毕，则聚类完成。
Density Peak算法的缺点是很难确定聚类中心点的个数；在很多实际问题中，该算法并不稳定，会出现很多噪声点，干扰聚类中心点的选择。其效果如图3所示。图4为Density Peak算法在人脸分类中的应用。
图3 Density Peak算法效果
图4 Density Peak算法在人脸分类中的应用
（二） Center-point based: Mean Shift
Mean Shift算法是一种基于Center-Point的算法。Center-Point考虑的是center和point之间的关系。这种关系大概分为两种：一种是以Kmeans为代表的assign each point to a center的关系，另一种则是以Mean Shift为代表的shift each point toward a center的关系。鲁小虎主要介绍了Mean Shift算法。
如图5，对于那些在聚类中心附近的点，若能够让其梯度一步一步(step-by-step)上升，就会收敛到聚类中心上面。
图5 Mean Shift算法特点
Mean Shift主要分为以下两个步骤：
(1)计算每个点的相应窗口范围内的所有点的平均值，连接
与
的向量叫做Mean Shift Vector，如图6所示。
图6 Mean Shift Vector
(2)把均值赋给
，再重复第(1)步进行迭代，直到收敛到聚类中心上面。整个过程如图7所示。
图7 Mean Shift聚类过程
Mean Shift算法的局限是窗口大小难以确定，窗口选择比较重要，选择了合适大小的窗口，才能有好的效果。图8展示了Mean Shift算法聚类出的一些较好的效果图。
图8 Mean Shift聚类效果
（三） Point-Point based: PLinkage
PLinkage算法是一种Point-Point Based的算法。Point-Point Based这类算法中，点与点之间存在两种关系：一种是以DBSCAN为代表的Adjacent neighboring point(ANP)，另一种是以Single Link为代表的Closest neighboring point(CNP)，如图9。
DBSCAN算法的原理是首先根据点的密度找到整个点集中的中心点core，然后对每个中心点，落在其领域范围内的所有的点都与当前的中心点分成一类，这样一直从中心点出发进行搜索，直到再找不到相邻的中心点为止，即完成一个类别的聚类。
Single Link算法的原理是每次找当前N个数据中距离最近的两个数据，并合成一个数据；接下来再从剩下的N-1个数据中找出距离最近的两个数据，以此类推，一直进行合并，直到只剩一个数据为止。根据目标分类数，沿合并的逆方向寻找数据。
图9 Point-Point Based中点间关系
鲁小虎用爬山做例子，启发了大家对PLinkage算法的形象理解。PLinkage算法是对每个点，找离这个点最近的且密度比它本身高的点。这两个点之间的关系就叫做pairwise linkage。在简单地介绍了Point-Point Based这类聚类算法之后，鲁小虎给大家讲述了他在撰写关于PLinkage算法论文时的相关经历。
写这篇论文的契机是他的师兄把这篇在Science上发表的文章在组会里分享，与此同时，他又在做关于边缘提取的研究。和边缘提取的思想相似，若聚类数据符合图10类似的高斯函数曲线，那么将当前的点和周围小范围的点进行比较，若找到比当前点密度高的点，那么就可以找到聚类中心。如图10，找到p1，找到p2……如此一直找下去，就可以找到聚类中心。
图10 高斯函数曲线
以爬山做类比，Mean Shift是从下往上一步一步找上去的，而PLinkage的每个数据只需要找一步，接力式地传上去，就像送东西一样，送给下一个人就行了，不用自己亲自送到山上去。
鲁小虎也总结了当时做此算法的失败经验。由于最开始只看了Science期刊上的那一篇文章，并且不了解Mean Shift算法，所以在文章撰写中，花了很大的功夫来写PLinkage和Mean Shift的差别。文章投出去了，才发现Mean Shift下有一个分支叫做Quick Shift，与他的思路非常相似，所以最后申请撤下了这篇稿件。
科研经历是有趣的，研究算法、解决问题的过程很有成就感；但是与此同时我们也要广泛阅读文献，关注前人已经做了什么，避免重复工作。
图11 PLinkage算法示意
PLinkage算法应用实例：
(1)图像分割：输入一张原始图像，在使用一种方法计算密度后，每个点找一个比其密度更高的点连接，然后依次聚类，得到初始的聚类效果。接着，进行一次后处理、合并，得到图12中(d)的效果。
(2)点云分割：用法与图像分割基本一样，两者的区别在于密度的算法不同。先输入原始的点云，直接用PLinkage聚类后得到图13(b)效果，进行后处理、合并后得到图13(c)的效果。
图12 PLinkage图像分割效果
图13 PLinkage点云分割效果
灭点提取
灭点的定义是：如果在物方有一系列对应同样方向的三维线，那么将这些线拍摄至像片上并将其延长，则这些线相交的点称为灭点。鲁小虎用一个视频向观众展示了使用灭点对相机相对姿态进行估计的应用。
在“曼哈顿世界假设 （Manhattan World Assumption）”的前提下，灭点提取要处理好两个问题。一是全局约束，即估计出的解是全局最优。二是正交约束，灭点之间应该互相正交。除了解决两个问题之外，灭点提取的算法还需尽可能地达到实时的处理效果。
目前已有的灭点提取算法可以分为四类：
1. 基于搜索的方法：
这种方法出现最早，最直接。它的思想是通过对所有可能的情况进行遍历，挑选出效果最好的，从而满足全局约束。缺点是计算量过大，目前基本上没有人在使用。
2.基于期望的方法：
这种方法适合估计多个灭点。它的缺点是需要初始估计，不能将全局和正交约束很好地引入。
3.基于RANSAC的方法：
使用RANSAC可以比较迅速地寻找最优灭点估计位置。这类方法先定义一个最小解集，求得一个灭点，并在之后加入正交约束，逐步求得其他灭点。它的缺点是并不能保证全局最优。
4.基于优化的方法：
基于优化的方法将灭点估计转换成数学问题，利用数学方法来寻找最优解。这类方法目前采用不多，大多需要几十秒来完成处理。
通过以上的比较，鲁小虎选择了在基于RANSAC的方法的基础上继续深入研究。
基于RANSAC的灭点估计需要一个由若干条线组成的最小解集，常见的是使用一、三、或四条线，如图14，来构成最小解集。
1.使用一条线作为最小解集的RANSAC
在使用一条线作为最小解集的情况下，由于灭点不可能由一条线估计出来，所以需要有先验知识。假设先通过其它算法估计出了水平方向对应的一个灭点，第二个灭点便可通过一条线确定出来。使用获得的灭点和水平的灭点做正交运算即可得出第三个灭点。具体算法可以参考参考文献[1]。
2.使用三条线作为最小解集的RANSAC
使用三条线作为最小解集是目前比较主流的做法。从影像上提取的若干条线中任意选取两条线，假定这两条边对应着同样的灭点，即可通过两条线求出第一个灭点。接着使用第三条线得到第二个灭点。使用先前得到的两个灭点通过正交运算获得第三个灭点。这种方法存在一个问题：任选的两条线并不一定对应着同一个灭点。选出恰好满足要求的两条线是一个概率问题，需要通过一定量的穷举来保证概率。目前直接用RANSAC进行迭代，选择迭代一百多次中的最优结果作为估计的做法缺少严密的推导。具体算法可以参考参考文献[1][2]。
3.使用四条线作为最小解集的RANSAC
使用四条线作为最小解集有两种构想。第一种构想是使用前两条线确定第一个灭点，剩下两条线确定第二个灭点，通过正交运算确定第三个灭点。第二种构想是使用前两条线确定第一个灭点，第三条线对应第二个灭点，第四条线对应第三个灭点。这种解集选取方法和选择三条线的方法没有本质差别，也同样存在着概率不易计算的问题。具体算法可以参考参考文献[2][3]。
图14 基于RANSAC的灭点估计
介绍了常见的三种解集选取方法后，鲁小虎展示了他自己研究的方法。他的算法结合了RANSAC和穷举。
为了说明清楚方法，这里首先介绍equivalent Sphere。equivalent sphere是一个中心位于相机焦点的单位球。像平面被投影到朝向它的半球。在他的方法中，equivalent sphere使用了右手坐标系，其中X轴和Y轴分别与像平面X轴和Y轴一致，Z轴从相机焦点指向像主点。设像主点为
，f为相机主距，像平面上一个像素
可以通过图15中的两个公式转换到equivalent sphere坐标系统中。
图15 像平面坐标系转equivalent sphere坐标系公式
鲁小虎的具体算法分为三步：
（1）随机选择两条线求其交点，通过图15中两个公式将交点转换至equivalent sphere表面以产生第一个灭点v1。
（2）在equivalent sphere上v1所在大圆上均匀采样，比较结果获得第二个灭点v2。
（3）通过对v1和v2做叉积计算出第三个灭点。
为了解决任选两条线不一定对应同一个灭点的问题，鲁小虎使用了概率统计的方法。在给定外点率（α）和置信度水平（β）之后，可以通过图16中的公式求得至少需要多少次迭代（Its）。由于穷举的时间耗费比较大，一般需要几秒到十几秒，为了达到实时的效果，鲁小虎选择用预先建立格网的方式来加速算法。加速之后的算法，在i5的CPU上，不做任何并行处理，只需40ms即可解决问题。
图16 迭代次数计算公式
最后鲁小虎对照图17对他的算法效果进行了分析。他提出的方法在误差达到50%的情况下，准确性仍可以达到0.827；不需要至少包含两个灭点的假设，得到的结果很鲁棒。
图17 算法效果分析
心得体会
报告的最后鲁小虎与大家一起分享了他和他身边同学的五点心得体会。
一．学到实处。每天都感受到自己在进步，而不是沮丧。
二．学会总结。写博客笔记可以使你对问题理解更加深刻，而且相较于单纯保存网页，整理之后再看的可能性会比较高。
三．要有一定的刺激量。最好的状态是每天在想要解决的问题，吃饭睡觉都在想这个问题。全身心的投入到这个问题里面，就会有不一样的结果。
四．早做准备，按计划行事。
五．学点数学。数学的功底决定了想法的等级，同样的问题，不同数学基础的人想出来的解决方法级别也不同。他推荐大家如果大家有时间可以好好补一补，学一些基本的数学工具。
>>>互动交流
观众A：师兄在介绍时提到了使用灭点进行姿态估计，想请问师兄灭点在估计中所起到的作用？
鲁小虎：姿态估计有两种，一种可以得到绝对位置，另一种可以通过跟踪的方法得到后续的姿态。但是跟踪的方法存在误差累计的问题，这个时候需要使用一些绝对量来矫正。测绝对量一般需要一些额外代价。所以比较好的方法是使用跟踪的方法获得姿态，再用绝对量来进行校正。灭点可以作为一种精度不是很高的绝对量。
观众B：师兄介绍了很多论文写作的方法，请教一下师兄论文阅读的方法有哪些？
鲁小虎：在研究一个新领域时，先看一下相关论文的Introduction，在其中找到综述性的论文。再把比较新的综述性的论文拿出来看。对这个方向有了基本的了解之后再来看具体的论文。在看具体论文的过程中，首先看Introduction，如果已经看过综述性的论文，那么Introduction就可以选择忽略。接着开始看算法。最开始的时候先了解整体的结构，搞清楚每一段是做什么的，先把整体的脉络框架搞清楚。公式不必看的特别深入，不必拘泥于这个脚标、那个上标的含义。在这之后具体了解每一步是怎么实现的。除非我们想实现论文里的算法，不然一般到不了这一步。我们一般只是看下他怎么做的，不需要深入看公式。
（编辑：肖珊）
鲁小虎做报告
观众认真听讲
踊跃互动
鲁小虎（右三）与GeoScience Café团队成员合影留念
参考文献：
[1]Bazin JC, Pollefeys M (2012) 3-line RANSAC for orthogonal vanishingpoint detection. In: IEEE/RSJ International Conference on Intelligent
Robots and Systems, pp 4282–4287
[2]Zhang L, Lu H, Hu X, Koch R (2016) Vanishing point estimation andline classification in a Manhattan world with a unifying camera
model. International Journal of Computer Vision 117(2):113–130
[3]Wildenauer H, Hanbury A (2012) Robust camera self-calibration frommonocular images of Manhattan worlds. In: IEEE Conference on
Computer Vision and Pattern Recognition (CVPR), pp 2831–2838
GeoScience Café以“谈笑间成就梦想”为口号，采取最自由的交流方式，每期邀请1-4位报告人，针对自己正在进行的研究展开报告。每周五晚7:30，在测绘遥感信息工程国家重点实验室四楼休闲厅举行当期活动。报告内容不仅涉及一切与测绘有关的学科内容及学术方法，如测绘基础学科、地理信息系统、摄影测量与遥感、全球定位系统、激光雷达技术、信号处理，还包括地理信息科学以外的话题，如法律和艺术等。让任何感兴趣的人——不仅是地理信息相关专业的师生，还包括其他专业的师生，甚至是文科生——都可以听取报告，并当场向主讲嘉宾提问或者会后与其交流。
更多精彩内容(报告PPT、新闻稿及下期活动消息等)敬请关注Geoscience Café群(QQ群号：532362856)，微信公众号：GeoScienceCafe，新浪微博账号：GeoScienceCafe；优酷视频链接：http://v.youku.com/v_show/id_XMTkzNjQ3MjgyMA==.html?from=s1.8-1-1.2&spm=a2h0k.8191407.0.0
欢迎扫描二维码：
