- 1 -
中国科技论文在线
基于偏好分析和局部约束的引导性采样#
赖桃桃，王菡子**
基金项目：高等学校博士学科点专项科研基金博导类资助课题（20110121110033）
作者简介：赖桃桃（1985-），男，博士研究生，计算机视觉
通信联系人：王菡子（1973-），男，教授，主要研究方向：计算机视觉，鲁棒统计学
（厦门大学模式分析与机器智能研究中心，福建 361005）
5 摘要：本文提出一种结合条件采样和局部约束的假设生成算法。该算法根据权重选择数据来
生成假设，这些权重是由排序后的残差索引计算得到。为了采样一个最小子集，该算法首先
随机选取一个种子点，然后计算所有数据对于该种子点的权重，再由计算得到的权重搜索该
种子点的近邻集，最后在近邻集上采样最小子集的其它数据。在引导性采样中加入局部约束
有两个优点：提高了生成干净最小子集的概率并减少了假设生成的计算量。我们采用真实图10
像并对提出的算法进行测试。实验结果表明：本文所提出的算法在有效假设生成上具有显著
的优势。
关键词：计算机视觉；假设生成；局部约束；偏好分析
中图分类号：TP391
15
Guided hypothesis generation using preference analysis and
local constraints
Lai Taotao, Wang Hanzi
(Center for Pattern Analysis & Machine Intelligence, Xiamen University, Fujian 361005)
Abstract: In this paper, we propose an effective hypothesis generation algorithm by combining 20
conditional sampling with local constraints. We sample data to generate hypotheses according to
sampling weights, which are derived from ordered residual indices. To sample a minimal subset,
we randomly choose a seed datum, compute sampling weights of all data with regard to the seed
datum, search the neighborhood set of the seed datum by using the sampling weights, and then
sample the remaining data of the minimal subset from the neighborhood set. It has two advantages 25
to consider the neighboring information in guided sampling: It raises the probability of generating
all-inlier minimal subsets and it reduces the computational loads in hypotheses generation.
Experimental results show that the proposed method has good performance by using real images.
Key words: computer vision; hypothesis generation; local constraints; preference analysis
30
0 引言
模型拟合技术在计算机视觉中有诸多应用，比如：单应矩阵和基本矩阵的估计[1]，范围
图像分割[2]，运动分割和人脸聚类[3]等。RANdom SAmple Consensus (RANSAC)[4]鲁棒模型
拟合算法不仅简单而且有效，是最广泛使用的模型拟合算法之一。为了能够在包含大量污染
噪声的数据中正确拟合一个几何模型，RANSAC 和 RANSAC-like[5]算法至少需要采样到一35
个干净的最小子集（即，只包含来自同一个结构的内点子集，用于估计一个模型假设）。在
内点比率为 的输入数据中，为了采样到一个干净的最小子集，使用随机采样策略的
RANSAC 至少需要生成 k 个最小子集，其中 k 近似等于1/ p 。也就是说，k 随 p 的增大或
的减小而指数地增大，其中 p 为组成一个最小子集的数据个数（比如：基本矩阵估计中 p
等于 7 或 8）。 40
为加速干净最小子集的生成，人们提出了很多采样算法[1,6-14]。在这些算法中，大多数
- 2 -
中国科技论文在线
算法[6-13]只考虑单结构数据，尽管可以把这些算法用于“拟合－移除”框架中来拟合多结构
数据，但是这种框架存在一个缺陷：如果一个模型参数的估计出现错误，可能会导致剩余模
型参数的估计错误。在[1]中，作者提出了一个多结构采样算法 (Multi-GS)，该算法能很好
地处理多结构数据。不过这个算法有一个缺点：它是在数据集的所有数据上进行条件采样，45
这就导致了假设生成过程过于耗时。
针对 Multi-GS 的不足，本文提出了一个基于偏好分析和局部约束的引导性采样算法
GHGPALC（即 Guided Hypothesis Generation using Preference Analysis and Local Constrains）。
GHGPALC 是在 Multi-GS 的基础上加入局部约束得到的一种快速条件采样算法。在采样一
个最小子集的过程中，GHGPALC 的大部分步骤只计算部分数据的权重并依据这些权重进行50
条件采样。这样，GHGPALC 可以有效地提高干净最小子集的生成概率并且减少计算量。
1 采样算法概述
因随机采样算法不能有效地采样干净最小子集，很多改进的采样算法被提出[1,6-14]。
NAPSAC
[6]和 Proximity[7]主要用于近邻数据的采样。GroupSAC[8]通过聚类或分割把数据
分成几组，先从数据点较多的组里进行采样，然后渐进地把采样扩展到所有的组。55
SCRAMSAC
[9]使用空间一致性检查并过滤掉错误的匹配点对以提高采样到内点的概率。这
些算法都假设来自于同一模型结构的内点间的距离较其它数据间的距离短。然而，这一假设
对于野点比率较高的数据并不一定成立，因为野点也可能成为内点的近邻。
Guided-MLESAC
[10]和PROSAC[11]假设两幅图像中匹配点对的匹配分数值较高的点对更
可能是内点。Guided-MLESAC 根据匹配点对的匹配分数计算得到权重，并使用权重进行条60
件采样，从而尽可能地选择匹配分数值较高的匹配点对。而 PROSAC 首先根据图像匹配点
对的匹配分数值进行排序，然后优先采样匹配分数值较高的匹配点对。尽管 Guided-MLESAC
和 PROSAC 都能有效地处理单结构数据，但在多结构数据上，这两个算法并不能有效地采
样到干净最小子集。
LO-RANSAC
[12]在标准 RANSAC 中插入一个局部优化过程。该优化过程从当前找到的65
最好模型假设的内点中采样最小子集。但对于内点比率高的数据，这个局部优化过程可能会
增加一个数量级的计算时间。LO+-RANSAC[13]有效地解决了该问题。然而对于多结构或者
野点比率高的单结构数据，这两个算法仍然不能有效地采样到干净最小子集。
Multi-GS
[1]和 ModeSamp[14]使用由残差排序获得的信息来加速有效假设的生成。这两个
算法能有效地处理多结构数据，但它们有个共同的缺点：假设生成的计算量较大。 70
与上述算法相比，本文提出的 GHGPALC 算法有效地加速了干净最小子集的生成。
2 GHGPALC 算法
本节首先描述从残差索引计算采样权重的相关概念和符号表示，然后详述如何使用局部
约束来加速有效假设的生成。
从残差索引中计算采样权重 75
令 X = {x1, x2, ... , xN}是由 N 个数据组成的集合， 1 2{ , ,..., }H 是由已采样的最
小子集生成的假设集。数据 xi 相对于 H 个假设的残差表示为:
1 2{r , r ,..., r }.
i i i i
Hr (1)
将残差 ir 进行非降序排列，其对应的残差索引记为 ip ：
- 3 -
中国科技论文在线
1 2{p ,p ,..., p }.
i i i i
Hp (2)
残差索引 ip 给出了 xi 对 H 个假设的偏好程度的排序。一个假设的排名越靠前，表明 xi 越有
可能成为该假设的内点。用 1:
i
sp 表示
i
p 的前 s 个元素，其中 s 被称作窗口大小且 s 的取值范80
围为 1 到 H。一对数据 xi 和 xj的相关性权重定义为：
, 1: 1:
1
| |,i ji j s sw
s
p p (3)
其中 1: 1:| |
i j
s sp p 是 1:
i
sp 和 1:
j
sp 所共有的元素个数。从上面的定义可以看出，来自同一结构的
内点对通常有较大的权重。
基于局部约束的假设生成
在单位时间内，Multi-GS 能比当前其它常用的采样算法采样到更多的干净最小子集，85
但是 Multi-GS 的总采样数却不到随机采样的五分之一。我们发现这主要是由 Multi-GS 权重
计算耗时引起的，因而我们通过加入局部约束来提高权重计算效率。
算法 1 详细描述了本文提出的算法。近邻集大小的设定在算法的第 3 和第 12 行。为了
提高权重计算效率，我们结合偏好分析和近邻信息得到新的引导性采样策略（第 8 行）。
算法1. GHGPALC的算法过程
1: 输入：数据X，最大采样次数M，最小子集元素个数p和块大小b
2: 输出：假设集
3: 初始化：设近邻集大小K = ⌈ × N⌉，其中N为X的元素个数
4: For c =1, 2, . . . ,M
5: If c ≤ b
6: 随机采样一个最小子集S
7: Else
8: 局部约束地引导采样一个最小子集S（见节）
9: End if
10: =⋃{由已采样最小子集S生成的假设θc}
11: 把xi对于θc的绝对残差添加到
i
r （i = 1,2,...,N）
12: 更新邻域集大小K (见节)
13: If c ≥ b 且 mode(c, b) = 0，则
14: 重新排序残差 ir 得到残差索 ip
15: 更新窗口大小s = ⌈ ∗ c⌉
16: End if
17: End for
90
下面，我们将详细阐述 GHGPALC 算法的两个重要步骤：近邻集大小的选取和基于局部
约束的引导性采样。
近邻集大小的选取
种子点近邻集大小 K 首先初始化为：
K = ⌈ratio × N⌉， (4)
其中 0 < ratio <1。然后在采样过程中不断地更新 K，把 K 设置为当前最好假设的内点数。95
- 4 -
中国科技论文在线
也就是，我们计算当前假设 θc（算法 1 的第 10 行）的内点数 Nc。若 Nc > K，那么令 K = Nc。
基于局部约束的引导性采样
若已采样 H 个假设，我们按如下步骤采样下一个假设。
首先，从所有数据中随机选取一个种子点
1g
x 。
然后，计算数据 X 相对于
1g
x 的权重 W2，并将其用于选择第二个数据： 100
1, 1
2
, ,
( )
0, ,
i gw if i g
i
otherwise
W (5)
其中
1,i g
w 使用公式(3)计算。先对 W2 非降序地排序得到 W2'，接着保留 W2中与 W2'前 K 个
元素相对应的元素；然后，把 W2 中的其它 N - K 个元素设置为 0 并且获取与 W2'中前 K 个
元素对应数据的索引 Υ。我们称 W2'的前 K 个数据为种子点
1g
x 的近邻。
1g
x 的近邻集记为
1 2
' {x , x ,..., x }
Kn n n
X ， (6)
它是 X 的一个子集，其中
1 2{n ,n ,..., n } {1,2,..., N}K (7)
是近邻集 X'的数据索引集。我们用权重 W2 从 X'中选择第二个数据
2g
x 。 105
最后，当 m >= 3 时计算 X'（不重采样已选择的 m - 1 个数据）的采样权重 Wm：
1
, 1 11
, , {g ,...,g },
( )
0, ,
j
m
i g mj
m
w if i i
i
otherwise
W (8)
然后用 Wm从 X'中采样第 m 个数据。
为采样一个最小子集，Multi-GS 和 GHGPALC 计算采样权重的时间复杂度分别为 O(pNH)
和 O(NH + pN′H + N logN)，其中 N′是 X'的元素个数。在多结构数据中，N′比 N 小很多，
因此 GHGPALC 的计算复杂度更小。实验结果显示，GHGPALC 的假设生成速度比 Multi-GS110
快很多。
3 实验
在本节中，我们首先介绍实验中用到的性能指标，然后评估 GHGPALC 和当前常用的采
样算法在基本矩阵估计上的性能。
性能指标 115
由干净最小子集生成的假设并不保证其能充分表示真实模型。在[14]中，作者用参数估
计错误（the error of estimated parameters (EEP)）来度量假设的优劣。一个假设的 EPP 计算
如下：
2
*min ,g g (9)
即假设 θ与最相似真实模型的距离，其中，真实模型 *
g 由第 g 个结构的所有内点拟合得到，
θ与 *
g 都规范化到 1。在下面的实验中，我们只比较各算法生成的干净最小子集的 EPP。 120
文献[1]和[14]使用了另外两个指标：单位时间内所采样到的干净最小子集总数和 TFS
（the time-to-first-solution，即采样到第一个解所需的时间）。“第一个解”是指为每个结构
- 5 -
中国科技论文在线
采样到的首个干净最小子集。一个好的假设生成算法应能在单位时间内生成尽可能多的干净
最小子集且其 TFS 尽可能地低。
基于EPP和TFS，我们介绍另外两个指标：单位时间内所采样到的有效干净最小子集总125
数和TFES（the time-to-first-effective-solution，即采样到第一个有效解所需的时间）。若一个
干净最小子集的EPP小于或等于某个阈值，我们就称这个干净最小子集为有效干净最小子
集。在基本矩阵估计实验中，我们把这个阈值设为。“第一个有效解”是指为每个结构
采样到的首个有效干净最小子集。对某一个数据，当且仅当这个数据对于某个假设的残差小
于或等于某个指定的尺度时，认为它是该假设的内点。内点尺度经验的设置为。另外，130
在实验中，我们设置b = 50（算法1第13行）和ratio = （第节）。
我们记录以下五个指标：i) 最小子集生成总数；ii) 干净最小子集生成总数；iii) 干净
最小子集的中值 EPP（MEPP）；iv) 有效干净最小子集生成总数；v) 采样到第一个有效解
的时间（TFES）。在上述五个指标中，我们认为 iv)和 v)为最重要的两个指标。
我们将 GHGPALC 和下列采样算法进行比较：Random（在标准 RANSAC[4]中使用的随135
机采样策略），NAPSAC [6]，LO-RANSAC[12]，PROSAC[11]，Guided-MLESAC[10] 及 Multi-GS[1]。
实验运行于配置 I5 CPU 的 windows 平台。
基本矩阵估计
(a) Cube (结构 1：97 内点，205 野点) (b) Game (结构 1：63 内点，170 野点) 140
(c) GameBiscuit (结构 1：73 内点，结构 2：88 内点，(d) CarChipsCube (结构 1：19 内点，结构 2：33 内点，
167 野点) 结构 3：53 内点，60 野点)
(e) ToyCubeCar (结构 1：45 内点，结构 2：69 内点，(f) Toys (结构 1：33 内点，结构 2：23 内点， 145
结构 3：14 内点，72 野点) 结构 3：41 内点，结构 4：58 内点，82 野点)
图 1 用于基本矩阵估计的图像对。野点用“+”标识，而其它结构用不同颜色标识。所有图像对均来自
AdelaideRMF 数据集[15]。
Fig. 1. The gross outliers are marked as “+”, while the inliers of the other structures are marked as different colors
respectively. All image pairs are from the AdelaideRMF dataset [15]. 150
为了数值的稳定性，我们首先对数据执行全局坐标归一化操作[16]。我们用 8 点算法[16]
估计基本矩阵和用 Sampson 距离[16]计算残差。在每个图像对上，每个算法执行 100 次，每
- 6 -
中国科技论文在线
次执行 10 秒。我们在六个图片对上进行实验，实验的中值结果记录于表 1。
155
表 1 各采样算法在基本矩阵估计上的性能比较。实验所用的图像对如图 1 所示。#total 表示 10 秒内采样到
的最小子集总数；#S-i 表示 10 秒内为结构 i 采样到的干净最小子集总数（10 秒内为结构 i 采样到的有效干
净最小子集总数）；’-’代表没有找到解。在表中，最好的结果都用粗体标注。
Tab. 1 Performance of various sampling methods for fundamental matrix estimation. The image pairs are showed
in Fig. 1. #total = the total number of p-subsets sampled within 10 seconds; #S-i = the total number of all-inlier 160
p-subsets sampled within 10 seconds for structure i (the total number of effective all-inlier p-subsets sampled
within 10 seconds for structure i). And '-' represents failure to find a solution. The best results are boldfaced.
Data Random NAPSAC LO-RAN
SAC
Guided-ML
ESAC
PROSAC Multi-GS GHGPALC
Cube
Fig. 1(a)
#total
#S-1
EPP
TFES
11987
1 (0)
-
11513
151 (5)
11892
1 (0)
-
12054
29 (4)
11850
3 (0)
-
1316
213 (16)
3484
851 (53)
Game
Fig. 1(b)
#total
#S-1
EPP
TFES
14707
0 (0)
-
-
14029
7 (0)
-
14585
0 (0)
-
-
14787
2 (0)
-
14479
0 (0)
-
-
1530
172 (21)
4051
840 (125)
GameBiscuit
Fig. 1(c)
#total
#S-1
#S-2
EPP
TFES
11216
0 (0)
0 (0)
-
-
10779
69 (31)
835(24)
11128
0 (0)
0 (0)
-
-
11280
426 (84)
0 (0)
-
11093
26 (11)
0 (0)
-
1248
168 (74)
195 (6)
3251
529 (237)
646 (16)
CarChipsCube
Fig. 1(d)
#total
#S-1
#S-2
#S-3
EPP
TFES
19011
0 (0)
0 (0)
1 (0)
-
18022
0 (0)
94(40)
2869(937)
-
18785
0 (0)
0 (0)
1 (0)
-
19181
0 (0)
0 (0)
459(72)
-
18613
0 (0)
0 (0)
6 (2)
-
1851
47 (14)
130 (59)
427 (172)
4651
278 (80)
438 (208)
1220(542)
0. 3498
0. 3432
ToyCubeCar
Fig. 1(e)
#total
#S-1
#S-2
#S-3
EPP
TFES
16497
0 (0)
2 (1)
0 (0)
-
15709
858 (109)
1846(569)
0 (0)
-
16321
0 (0)
2 (0)
0 (0)
-
16643
0 (0)
244 (28)
0 (0)
-
16210
0 (0)
5 (1)
0 (0)
-
1655
174 (26)
357 (97)
1 (0)
-
4177
523 (84)
1104(275)
15 (1)
Toys
Fig. 1(f)
#total
#S-1
#S-2
#S-3
#S-4
EPP
TFES
14723
0 (0)
0 (0)
0 (0)
0 (0)
-
-
14042
47 (12)
1 (0)
272 (101)
377 (153)
-
14582
0 (0)
0 (0)
0 (0)
0 (0)
-
-
14817
0 (0)
0 (0)
5 (0)
0 (0)
-
14471
0 (0)
0 (0)
0 (0)
0 (0)
-
-
1521
90 (24)
30 (7)
163 (65)
198 (71)
4001
352 (112)
194 (42)
529 (229)
736 (268)
如实验结果所示，仅本文提出的 GHGPALC 算法能为所有数据集找到有效解，而其余
算法不能在某个或多个多结构数据集上找到有效解。Guided-MLESAC 和 Random 总能生成165
最多的最小子集。然而，Random 在野点比率高的单结构或多结构数据集中找不到一个有效
解。LO-RANSAC 的性能类似于 Random，而 PROSAC 的性能略优于 LO-RANSAC。
Guided-MLESAC 又优于 PROSAC，但 Guided-MLESAC 在所有多结构数据集上都不能找到
有效解。Multi-GS 较 NAPSAC 有更好的性能：Multi-GS 的 TFES 都比 NAPSAC 低；NAPSAC
没能在四个数据集上找到有效解，而 Multi-GS 仅没能在一个数据集找到有效解。 170
- 7 -
中国科技论文在线
GHGPALC在四个数据集上生成了最多的（有效）干净最小子集并能最快找到第一个有
效解，GHGPALC在另外两个数据集上也有不俗的表现。尽管NAPSAC在有些数据集上采样
到最多的干净最小子集（如, ToyCubeCar和 CarChipsCube），但它却不能为这些数据集找
到一个有效解。另外，NAPSAC在野点比率高的数据集中性能较差（如, Game），且它不能
为内点个数少的结构找到干净最小子集。因此，与现有算法相比，本文提出的GHGPALC算175
法表现出了其优越性。
4 结论
本文提出了一个新的假设生成算法 GHGPALC，该算法通过加入局部约束来提高假设生
成的速度和有效性。实验结果表明：在采样有效性上，本文提出的 GHGPALC 算法优于其
它对比算法，尤其在野点比率高的单结构或多结构数据上，其表现更为突出。在较有挑战性180
的多结构数据上，大部分算法都不能找到有效解，而 GHGPALC 算法仍能快速地找到有效
解。
致谢
感谢 Adelaide 大学的 Tat-Jun Chin 和 Jin Yu 博士提供若干对比算法的代码。另外，感谢
Hoi Sim Wong 博士对 EPP 计算提供的帮助。 185
[参考文献] (References)
[1] T.-J. Chin, J. Yu and D. Suter. Accelerated hypothesis generation for multistructure data via preference
analysis[J]. IEEE Trans. Pattern Analysis and Machine Intelligence, 2012, 34(4): 625-638.
[2] H. Wang, T.-J. Chin and D. Suter. Simultaneously fitting and segmenting multiple-structure data with 190
outliers[J]. IEEE Trans. Pattern Analysis and Machine Intelligence, 2012, 34(6): 1177-1192.
[3] S. Mittal, S. Anand and P. Meer. Generalized projection based m-estimator[J]. IEEE Trans. Pattern Analysis
and Machine Intelligence, 2012, 34(12): 2351-2364.
[4] . Fischler and . Bolles. Random Sample Consensus: A Paradigm for Model Fitting with Applications
to Image Analysis and Automated Cartography[J]. Commun. ACM, 1981, 24(6): 381-395. 195
[5] H. Wang and D. Suter. Robust adaptive-scale parametric model estimation for computer vision[J]. IEEE Trans.
Pattern Analysis and Machine Intelligence, 2004, 26(11): 1459-1474.
[6] . Myatt, P. Torr, . Nasuto, . Bishop and R. Craddock. NAPSAC: high noise, high dimensional robust
estimation[A]. In Proc. British Machine Vision Conference[C], 2002. 458-467.
[7] Y. Kanazawa and H. Kawakami. Detection of Planar Regions with Uncalibrated Stereo using Distributions of 200
Feature Points[A], in: Proceedings of British Machine Vision Conference[C], 2004. 247-256.
[8] K. Ni, H. Jin and F. Dellaert. GroupSAC: Efficient consensus in the presence of groupings[A]. IEEE
International Conference on Computer Vision[C], 2009. 2193-2200.
[9] T. Sattler, B. Leibe and L. Kobbelt. SCRAMSAC: Improving RANSAC's efficiency with a spatial consistency
filter[A]. IEEE International Conference on Computer Vision[C], 2009. 2090-2097. 205
[10] . Tordoff and . Murray. Guided-MLESAC: Faster image transform estimation by using matching
priors[J]. IEEE Trans. Pattern Analysis and Machine Intelligence, 2005, 27(10): 1523-1535.
[11] O. Chum and J. Matas. Matching with PROSAC-progressive sample consensus[A]. IEEE Computer Vision
and Pattern Recognition[C], 2005. 220-226.
[12] O. Chum, J. Matas and J. Kittler. Locally optimized RANSAC[A], in DAGM-Symposium[C], 2003. 236-243. 210
[13] K. Lebeda, J. Matas and O. Chum. Fixing the Locally Optimized RANSAC[A]. In Proc. British Machine
Vision Conference[C], 2012. 1-11.
[14] . Wong, T.-J. Chin, J. Yu and D. Suter. Mode seeking over permutations for rapid geometric model
fitting[J]. Pattern Recognition, 2013, 46(1): 257-271.
[15] . Wong, T.-J. Chin, J. Yu and D. Suter. Dynamic and hierarchical multi-structure geometric model 215
fitting[A]. IEEE International Conference on Computer Vision[C], 2011. 1044-1051.
[16] R. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. 2nd ed. Cambridge University
Press, 2004.
