没有合适的资源?快使用搜索试试~ 我知道了~
文件标题:MaxCon中加权影响的一致性测量方法研究
8964我是X|我|i=1单调布尔函数加权影响的最大一致性张尔川(Erchuan Zhang)、David Suter、RuwanTennakoon、Tat-Jun Chin、 Alireza Bab-Hadiashar、 GiangTruong、Syed Zulqarnain Gilani、Centre for AI ML,Edith Cowan University,Perth Australia.营养与健康创新研究所,伊迪丝考恩大学,澳大利亚珀斯澳大利亚墨尔本皇家理工大学†阿德莱德大学,澳大利亚阿德莱德。{erchuan.zhang,d.suter,h.truong,s.gilani}@ ecu.edu.au,{ruwan.tennakoon,abh}@rmit.edu.autat-jun. adelaide.edu.au摘要共识最大化(MaxCon)是一个最重要的阈值ε >0时,给定类型数学模型的最大一致性准则被表述为,在计算机视觉中广泛使用的鲁棒标准。天纳孔等人(CVPR2021),在MaxConMaxθ∈θ,I<$X|、|,(一)以及单调布尔函数影响的估计。在这种情况下,涉及两个分布:定义影响度量的差异;以及用于抽样以估计影响度量的分布。本文研究了求解MaxCon的加权影响的概念。特别是,我们研究了伯努利测量。从理论上证明了在这种测度下,属于较大结构的点的加权影响一般小于属于较小结构的点的加权影响我们还考虑加权策略的另一个“自然”家族:集中在立方体的特定(汉明)水平上的均匀测量的采样。可以选择匹配分布:定义测量和实施采样的方法相同。这具有采样器是测量的无偏估计器的优点。在加权抽样的基础上,对Tennakoon等的算法进行了改进,并在合成和真实数据集上进行测试。我们展示了Bernoulli抽样的一些适度收益,并阐明了数据结构与加权测度和加权抽样之间的一些相互作用。1. 介绍稳健模型拟合是处理异常数据的基本问题,是一个长 期 而 富 有 挑 战 性 的 研 究 课 题 。 共 识 最 大 化(MaxCon)是稳健拟合最流行的标准之一,其目的是找到一个对给定测量值具有最大共识从形式上讲,S.T. r(xi,θ)<$ε,xi∈ I,式中,θ是规定数学模型的允许参数集,θ是模型参数,是子集的大小,r(xi,θ)是基准xi相对于模型θ的拟合残差。随机抽样一致性(RANSAC),其核心思想是采用一个假设和验证过程,随机抽样子集,以适应模型和计算的共识,相对于所获得的模型。这种随机化方法可 以 非 常 快 , 但 不 能 保 证 解 决 方 案 的 最 优 性 。RANSAC的变体,如LO-RANSAC [6]和PROSAC [5],可以改进原始RANSAC,但它们仍然继承了随机化方法的缺点。相关的方法是基于M-估计范式,或其他方式来修改残差测量。示例包括:l1方法[20],l∞方法[22,23],迭代加权最小二乘法[1],加权l1方法[21],精确罚函数法[15,16]。众所周知,MaxCon问题是组合困难的[3]。存在最优方法(分支定界(BnB)搜索[17]和A树搜索[2,4]),但它们的(最坏情况)运行时间随着问题的大小呈指数级增长,这使得它们对于大规模和高维问题无效。这项工作直接遵循[24] -在这里检查影响的替代定义和相关的估计方法。这项工作,反过来,使用相同的基本[4],它使用了一个树上的搜索给定数据集X={xi}n尺寸为n,结构,建立在LP类型的“基础”概念上‡8965≺i=1J联系我们.∈{- -≺≺≺∥ ·∥∥ ∥ ∥ ∥f(b)IX{}奥里该算法能够找到全局最优解。然而,这种方法是缓慢的,尽管加速介绍蔡等人。[2]的文件。在[25]中,提出了一种无监督学习方法来确定在解决鲁棒模型拟合问题时要删除基中的哪个点。这种方法采用了强化学习的框架,其中删除点是由最大化奖励指导的。像许多基于学习的方法一样,1.81.61.41.210.80.60.4点解离群值0.10.20.30.40.50.60.70.80.98765432100 10203040506070可能需要很长的时间来训练,很难分析方法及其概括能力。像[25]和[24]一样,对基本树搜索的修改失去了A的优先级队列保证,牺牲了速度的最优性保证。本文件在精神上也属于这一范畴。1.1. 影响力和共识最大化最近,Tennakoonet al. [24]用单调布尔函数理论描述了最大一致性问题,并研究了单调布尔函数影响下MaxCon解的特征。详细地,任何子集 =xin可以由长度为n的位向量b表示,其中其第i个分量bi=0表示排除数据xi,并且bi=1表示包含数据xi。那么,任何子集I都是空的而不是一个n维布尔立方体的顶点布尔函数f:{0,1}n→ {0,1}:图1.左:8个点的2D直线拟合问题。右图:与拟合问题相关的布尔立方体8D Boolean立方体在平面上被展平,其中每个蓝点表示线拟合问题的不可行子集,其他彩色点表示可行子集。这些点按照从上到下的顺序关系排列在这个玩具例子中,有四个上零,即, b6= 00111111(最大向上-每 零 , 上 标 表 示 选 择 了 多 少 个 数 据 点 ) , b4=10001101,b3 =011000010,b3′ =11010000,在立方体中突出显示,这些顶点用不同的颜色来区分 顶点b3′′ = 00001101是一个伪上零点(参见第3节中的定义)。请注意,所有低于级别3的顶点,即,少于3个点拟合,必须可行。布尔函数f的bi定义为[19]Σ Σf(b):=1, 若r(θ,xi)> ε,ij:b= 1.( 二)0, 如果r(θ,xi)<$ε其中,b=i表示翻转b中的第i位,b0,1n意味着b均匀分布在布尔立方体上。为了估计方程(3)中的影响,最明显和自然的方法是均匀抽样,并使用经验计数作为(无偏)估计。整个定义可行性(由b表示的子集xi称为如果f(b)=0则可行,否则不可行)。求解MaxCon是对最大尺寸的可行子集的搜索一个布尔函数称为单调函数,如果f(a)<$f(b)对于任何a b成立,其中排序关系意味着i-第i个分量aibi,对于n y1in。我们可以很容易地看到布尔函数(2)是单调的。其原因在于,将数据点添加到不可行子集仍然使其不可行,而从可行子集中删除数据点则使其可行。单色调布尔函数f的上零点b是顶点,使得f(b)=0且f(a)=1,对于任何a满足ba。f的最大上零b是具有最大大小的上零,即,f(b)=0和f(a)=1,其中1是l1范数.上零点本质上是系统地搜索所有可能的候选一致解,寻找最大一致性等价于寻找相关布尔函数的最大上零点。图1是一个二维直线拟合的玩具示例,它说明了单调布尔函数和MaxCon问题之间的联系。[24]中的关键概念是影响力。当赋予布尔立方体一个统一的措施,影响不幸的是,布尔立方体是如此之大,以至于均匀地分布样本不是一种有效的采样策略。这无疑导致了[ 24 ]的1.2. 本文的动机鉴于上述情况,因此可以将[24]的方法视为采用均匀测量影响的有偏估计(等式(3))。或者,可以将[24]中使用的抽样分布视为隐含地定义了一个新的(加权)影响度量(并且抽样策略现在是这个新影响度量的无偏估计)。这两种观点实际上是同一枚硬币的两面然而,主要的问题是是否有偏估计的统一措施的影响(第一个观点:有偏估计-第二观点:新的影响度量)实际上保持了影响大小的排序。简单地说,在[24]中,定义中使用的度量(以及离群值的影响更大的证明)和经验估计中使用的度量之间存在脱节:但人们可以通过使用一个影响的定义来调和这一点,001111111000110100001101 01100010 11010000Infi [f]:=Pb<${0,1}nf(b)、(3)8966−--··b和b之间的距离。(6)SLbkibkiΣ} ∈−{--我KQ1−q̸∅S−+. (n,·,·)S如将用于采样(以估计影响)。因此,我们被引导到一个更系统和连贯的研究主题称为在 第2.1 节 中, 我 们 为布 尔 立方 体 0 , 1n 配 备Bernoulli(q)测度μq,即bi=1的概率为q,bi=0的概率为1Q,其中包括作为特殊情况的一致测度(q=1)。为我们的基于加权影响的变体是[24]中版本的有效我们还提供了一个猜想,我们推导出的方程的结构的动机,可能链接和解释MaxCon的固有结构复杂性,通过一些最近的构造是什么特征的硬问题-见Con-这个无偏估计量是:2图3.1第3.2节。本文的目的是研究MaxCon下Inf(q)[f]=E[I(f(x)=f(x<$i))],(4)ixµq(x)其中I()是指示函数,E[]是随机变量的样本经验证据(见第4节)表明,基于伯努利加权影响的方法可以在更少的运行时间内实现类似的最优解,或者在类似的运行时间内实现更好的结果。但也许更重要的是,我们分析证明,这种加权措施,确保保持必要的顺序的影响-见第3节。实际上,由于我们导出的Bernoulli加权影响的表达式将均匀影响作为一种特殊情况,并且由于我们比[24]的相应部分涵盖了更一般的数据特征(第3.2节),因此本文提供了一个更全面的理论。影响力的新定义和相应的估计策略。其精神是研究这些问题-而不是产生一个1.3. 符号我们采用以下符号:(1)粗体b表示布尔立方体{0,1}n中的顶点(n位的向量),其第i个分量由bi 表 示。(2)[n]={1,2,···,n}。(3) L k:={b∈ {0,1}n|b (4)Lk:={b∈{0,1}n|b 对于Lk的类似定义。(5)对于b∈Lk,Bb∈ :={b∈ {0,1}n|(b,bLk−1,1 <$l<$k−p−1}表示确定的子立方体并对均匀测度进行了计算分析另一类测度,我们称之为Hamming(k),通过b,其中(b,b)=|{i:bi=bkibi}|是汉明:={l∈[n]|bki=j},在固定大小(固定汉明范数)k的子集上质量相等,在其他地方为零其中一个特殊的案例[24]。对于这些措施,事实证明,我们不需要其中j= 0,1.S1和S0表示索引的内值和离群值的数据点,bki∈Lk,关于iv el y。(7)Cn表示k-从头开始进行分析我们对伯努利(q)加权影响的表达式自然地按水平分层(当然,[24]中的相应方程也是伯努利(0.5)的特殊情况这允许我们通过检查来获得每个级别的可行性/不可行性翻转的数量(并且相应的加权影响然后仅仅是通过将这些计数除以给定级别中的顶点/子集的数量而产生的适当的归一化)。然而,[24]中没有指出这一点,也没有提出任何由此产生的意见。此外,由于我们分析了一组更一般的数据假设,我们也有一个更全面的图片比可以简单地通过检查方程推导[24]。我们的主要贡献可以概括为:• 我们通过加权影响的概念来描述MaxCon中离群值/内点的影响。我们证明了,对于理想和非理想情况,数据中属于较大结构的点的加权影响通常较小(定义见第3请注意,我们的分析比[24]中的分析更一般。• 我们根据经验测试对[24]的基本算法进行的修改,以适应加权采样伯努利测度 在几个鲁棒拟合任务中,一个有n个元素的集合的组合,也就是n!/k!/(nk)!,其中1kn.2. 加权影响在本节中,我们将介绍单调布尔函数的(伯努利)加权影响(2.1节)和(均匀汉明)加权影响(2.2节)的定义。2.1. Bernoulli(q)加权影响设 n= 0 ,1n是离散n维立方体的端 点,其上有Bernoulli测度μq,其中μ(b:bi=1)=q(0,1),即μ q(b)=q<$b<$1(1q)n− <$b<$1。 然后,我们可以定义一个度量在n[19]上f1,f2b∼Ωn对任意定义在n上的f1,f2.奇偶校验函数χq(b):=q<$i∈Sbi·q|S|−i∈Sbi形成空间的基,这里w是[n],b∈n,q−=−1−q,q+=.Q. χq(b)≠1,Convention.−8967我我q∈N(0,1),我们对nj上的一组顶点{b}的一˜QJJf<$q({i})=<$f,χqf(b)qbiq1−biµ(b)。(五)Infi [f]=Hq(1−q)J−+QJ1{j}hH对这些第i个变量的布尔函数f的加权一阶傅里叶系数可以由下式给出:Σ{i}+Qb−=10.90.80.70.60.50.40.3关于伯努利测度μq,第i个变量对布尔函数fde的加权影响0.20.11 2 3 4 5 6 7 8罚款的定义为(见[14]第9页)在fq[f]中:=μq({b:f(b)<$=f(b<$i)}),(6)其中f<$q({i})和Infq[f]通过1相关:定理2.1 如果f:{0,1}n→{0,1}是单调的布尔函数,则Infq[f] = −<$1f<$q({i})。图2.图1中使用的所有数据点的归一化精确和估计加权影响的比较,其中q设置为0的情况。375,我们设置样本数h=100。iq(1−q)In practice, it is not very realistic to calculate the exactvalue of (5) or (6) since the summation contains 2n possibleb to evaluate.由于我们将利用所有加权影响的顺序信息而不是它们的精确值来设计MaxCon算法,因此足以获得良好质量的近似加权影响。我们估计加权影响的方法如下所示:给定样本大小h > p和权重H2j=1根据伯努利测度的布尔立方体µq,然后翻转所有bj中的第i位以生成另一半样品 bh. 单调布尔函数f被评估为j=102+ 1个顶点。 因此,通过(5)、(6)和(7),Q定理2.1,我们将权重影响Infi[f]估计为−j=1图3.用于分离MaxCon内值和离群值的各种q的示例(3个离群值)左:所有数据点的影响-前3个异常值。右:分离函数(最小离群值和最大内围值影响之间的距离):Q的最佳选择是0。46在分离方面,对于这个数据集。注:抽样估计这一措施是一个完全不同的问题。例如,见[8,9,27] -可能诉诸均匀立方体的傅立叶理论的论点,经常回避切片上更复杂的傅立叶图像。同样,我们将不参考傅立叶系数。本质上,可以通过翻转第i位(包括或排除第i个数据点)来从转变计数的期望的定义“直接”到切片集中测量(并且因此对于sam)的预测/估计策略)。 此外,由于这些过渡-其中bj,i是bj的第i个分量。注:f的单调性可以简化计算:如果f(bj)=0且bj,i=1,则f(b<$i)=0;如果f(bj)=1且bj,i=0,则f(b<$i)=1。图2显示了估计的和精确的图1所示数据点的加权影响,其中影响通过最大影响进行归一化。有人可能会问-我们可以推荐最好的q使用吗?不幸的是,虽然我们可以说明,有一个最佳的q为玩具的问题(例如,见图。3),最佳q可能是问题相关的。此外,抽样测量是另一个复杂因素。2.2. Hamming(k)加权影响定义限制在布尔切片(相等汉明范数的水平)的傅里叶变换(以及一般分析)实际上是一个更复杂的主题,只是最近才研究。1参见证明的补充材料类似的结果可以在[14](第20页)中找到,但没有证据。估计加权影响8968K在伯努利(q)影响的适当公式中,对水平(切片)进行计数(在第3节或[24]中给出的伯努利(0.5)测量):不必重复复杂的推导/分析,而只需此外,由于人们只对影响的相对大小感兴趣,因此可以省略归一化。3. 加权影响在本节中,我们从理论上证明,属于较大结构的点具有较小的加权影响:直观地说,“内点”数据点的加权影响小于“外点”数据点的加权影响。 以下两节中所有理论结果的证明都可以在补充材料中找到。根据我们的分析,一旦可以搜索MaxCon解决方案,使用加权抽样的影响:在某种程度上,8969i=1我我公司简介i=1bk1−(C−−C+ΣΣ我1,l∈Sbki<$Skj,l∈[n],l=1bki0bkibkjl=1bkll=1bαn0+l我pL12· ··n0+mα0它必须是相对于b的离群值,1NΣ00联系我们Σi1i 2p(C−−<$C−)q(1−q)−−i0.估计值有正确的相对顺序来识别离群值。3.1. Bernoulli(q)-理想情况真实的数据集是数据集中有多个结构,这些结构通常共享许多数据点;然而,理想情况是一个有用的起点。定义3.1.假设{bki}n0一个单调布尔函数的上界,其中b是 ∈Lk,p+1<$k1<$k2<$··<$kn0<$n. 然后称f为理想,如果n ∈[n],|S1和S1|普,简单地说,我们可以看到(从is上的求和),当属于一个结构时,数据点的影响会减小(并且结构越大,减小的幅度越大),而对于该点不属于的每个结构,数据点的影响会增加(同样,如果该结构很大,则会增加更多)。这些增加和减少的权重不同(涉及q的项),使关系复杂化。注意 :对于 多个结 构,必 须小心限 定“inlier”和“outlier”。这些仅对指定的单个结构有意义。对于该结构,其他结构的所有“内点”实际上0bkibkj被提名的一个。即,结构具有非常小的重叠。Qf称为非理想的,如果n∈ i,j ∈[n],|S1第1章| > p.根据(10),数据点i的影响Infi[f]较大0bkibkj如果它是相对于更多的上零(和数据)即,至少两个结构具有显著重叠。我们称bα=(bα,· · ·,b α),定义如下:所有结构的离群值将具有所有结构中最大的影响在这里,我们引入一个新的布尔立方体{0,1}n0,对于任何.11bα:=i∈N0Sil,它对应于一个顶点(i1,i2,· · ·,in)∈lb{0,1}n0. 那么,Infq[f]是实值布尔函数0,否则,在{0,1}n0上我.为了简化符号,我们表示f[f],对于i∈一个伪上零点,对应于bki和bkj,其中reα:=|是伪上零点所属的级别|is the level that the pseudo upper zerobelongs没有我l=1bkifq(Si)。到. 设bαim0(p+1αm0,其中rei∈b1b2S0,i∈S1l=p+1l.1到bαi0;如果i是关于一个ny上零点的离群值,则α这个定理表明,如果只有一个理想,结构,即点是内点或离群点,相对于该结构,离群值定理3.3. 如果f是非理想的,则加权影响fq(Si)由下式给出:(all离群值具有相同的影响)严格地更大比那些内围值(所有内围值共享相同的影响)。pis=11秒秒0pin0+s=01秒秒0Cαs−1)qp(1 −q)n−p−1p定理3.2. (理想多重结构)如果n0>1,即,+()KsCks−αsCαs)ql(1− q)n−l−1。f是有多个上零点的理想,则,(如果l l非空),则Infq[f]为l=1bkiis=01秒秒0l=p+1in0+s=1l=p+11秒秒0n1ks 1pnp1推论3.2.1。 影响(10)具有以下或-8970Lp pis=1Ks(十)其中,fq(S·)不存在,如果S · =。证明这个定理的核心策略是归纳法公司简介Cksql(1− q)n−l−1。关于伪上零点的数目并利用定理3.2。与理想情况类似,根据定理3.3,is=0l=p+18971我们可以看到,属于较大结构的点的加权影响较小。显而易见的是,对于许多结构,表达式由于它们之间可能的交叉/重叠的组合而变得非常复杂-使内点/离群点二分法的测量复杂化(相对于任何给定的结构)。这使我们猜想:猜 想 3.1. ( MaxCon 的 复 杂 性 和 重 叠 间 隙 性 质(OGP))在[11](以及其中提到的作品)中,许多算法的计算复杂性与所谓的OGP有关。从本质上说,有人认为,如果解决方案空间是高度集群(这里的地方是衡量重叠的解决方案),那么这个问题将是很难为整个类的算法。简而言之,要么非常相似/具有大的重叠,要么广泛分离(很少中间分离)的潜在解决方案的存在是难以解决的问题的“签名”。我们推测,这是真实的MaxCon景观的可能的数据配置,上述反映(通过镜头的影响)如何这个复杂的数据实例的情况下表现在一个属性相关的寻求解决方案-影响。这个猜想特别有趣,因为最大独立集(在[11]中研究)和MaxCon之间的联系-可以证明MaxCon解是由不可行的最小尺寸子集形成的(超)图的最大独立集(也是补超图的最小顶点覆盖)。3.3. 一致汉明测度影响考虑Theo-rem3.1中定义的理想单结构情况.首先,很容易看出,对于理想的单一结构,任何算法都从一个大小大于组合维数的可行集开始,然后如果更大的集仍然可行,则增加点,将获得MaxCon解。 So it is aneasy problem with obvious so- lution strategies.但是,如果我们决定使用影响,我们可以注意到,从等式(8)中,内围影响来自仅计数水平p和p+ 1之间的可行/不可行转换因此,对于在水平p+ 1以上采样均匀汉明水平,不存在由内点引起的可行性/不可行性转变。换句话说,在该水平或更高水平上,均匀汉明影响度量对于内点将恰好为零。由于离群值的影响,对于相同的测量将是非零的,这似乎保证了一个非常有效的采样策略-可以在第一个样本中消除离群值,该样本显示了相关影响的计数-而不需要继续进行完整的估计过程。当然,实际上,这对于真实数据来说太好了--对于我们这里的严格假设来说,它非常脆弱。尽管如此,它确实暗示了一个不那么脆弱的提前结束点票策略的有用性一旦计数达到统计上显著高于其他计数的某种程度,就进行处理,而不是总是使用一定数量的样本:未来的研究课题。现在考虑理想的多重结构设置。根据等式10,由于处于某个结构(第一项)的内点而产生的影响仅在水平p和p+ 1之间产生。减法是由于“没有发生”的可行性转换因此,再次说明,在水平p以上的采样将不会但是,由于一个结构的内点是另一个结构的离群点(我们假设没有显著重叠):因此内点对任何结构的影响都不会为零-与单一结构的情况不同,因为所有结构都是(所有)其他结构的离群点,因此会产生方程中第二项的影响还容易看出,只要水平(In当计算该结构的影响时,第二项最大结构被排除在is= 0补充材料中有进一步的讨论。4. Bernoulli测度在本节中,我们通过经验证明了伯努利加权影响在合成数据集和真实数据集上的几个鲁棒模型拟合任务中的表现与我们的分析预测大致相同(基本上保留了内点/离群点分离的正确影响顺序)。我们使用的主要算法在补充材料中给出(算法1-如下[24])。为了降低丢失真正的内点的风险,我们还在算法1的最后一步实现了局部扩展(参见补充材料中的算法2),这同样遵循[24]的策略。注:[24]的算法使用固定汉明水平的统一采样(因此隐式提供基于汉明测量的结果),尽管在那里它被解释为估计统一测量影响的有偏方法,而不是像这里一样,新的影响测量。[24]根据经验优化了他们的采样水平-因此我们在这里不使用汉明采样进行实验。为了比较,我们使用:用途:RANSAC[10],Lo-RANSAC [6],A-NAPA-DIBP [2](我们仅使用它来生成具有低离群值率的合成数据的地面实况解决方案。),MBF [24],L1 [20]。我们使用加权影响的方法是WI的简称。实验采用Matlab R2020b,配备英特尔(R)i7- 8700 K CPU和32 GB RAM的计算机。4.1. 稳健的线性回归加权影响估计中的参数分析:加权影响(7)的评估需要两个参数:样本概率q和样本大小h。在这里,我们使用合成数据来研究q和h的影响8972−- −∩R∈R···r·resrex∈R∈1∈esexk(k+1)图4. 二维稳健线性回归的比较结果:SF距离相对于不同(左)样本概率q和(右)样本数量h的变化。所有实验进行50次。二维直线拟合问题我们生成n= 15个点2围绕一条直线,并随机选择30%的点作为离群点,这些离群点被范围[ 4,0. 1)(0. 1、4]。剩余点在[ 0]中被均匀分布的噪声扰动。1,0。1]中。我们将内点阈值ε设置为0。1在本小节的所有实验中。设res和rex分别为所有点的估计加权影响(由(7)计算)和精确加权影响(由(6)计算)的前k(按降序排列)。值k由离群值的数量确定(通过A-NAPA-DIBP发现)。我们通过标准化斯皮尔曼足距(SF)来测量res和rex之间的差异[7]。用(r)表示包含在3r中的元素的集合,用z·表示元素z(r)在r中的位置。res和rex之间的归一化SF距离由下式给出:1°F(r,r)=的|z− z|、z∈R(res)<$R(rex)图5. 8维稳健线性回归的比较结果:比较(左)共识误差和(右)运行时间与不同数量的离群值。地面真相是由A-NAPA-DIBP发现的。所有实验重复50次。相对性能:在这个实验中,我们考虑8维线性回归问题,其中合成数据的生成方式与我们在最后的实验 数据点的数量n是cho- sen为200,我们将异常值的数量从10到40,这受到用于生成地面实况的AAP-NAPA-DIBP的计算时间的限制。从图5中,我们可以发现Bernoulli加权影响和原始MBF都可以实现最优解,并且Bernoulli加权方法通常比MBF更补充部分对局部扩张的效果进行了比较4.2. 线性化基本矩阵估计在本小节中,我们进一步测试了基于Bernoulli加权影响的方法对来自KITTI Odometry数据集[ 12 ]序列“00”的五个图像对的影响对于两个给定的图像对,SIFT关键点[18]由VLFeat工具箱[26]检测和匹配。假设p1,p2是two匹配的特征,其中pi=(xi,yi,1)T是这里我们用k+ 1来表示zr· 如果z(r·)。越小SF距离越大,则res和rex共享相同的加权影响的前k阶的可能性越大对于固定数量的样本(h = 300,1000,3000),我们改变概率q从0。1比0。9;对于固定概率(q= 0. 3,0。5,0。7),我们的样本数量从100到5000不等。结果如图4所示,从中我们可以看出,当q(0. 2,0。4);并且对于更多的样本,SF距离较小。在下面的实验中,我们将概率q设置在(p +1)/n和0之间。4和样本大小h在100到500之间,以保持估计精度和运行时间之间的权衡请注意,SF距离无法区分共享相同加权影响的res或rex这些实验还显示了迭代地重新估计加权影响的必要性,因为一次评估所有加权影响并不完全匹配精确加权影响的顺序。2.我们选择非常少的数据点数量,因为随着n的增加,精确的加权影响需要指数时间来计算。3.表示es或ex。在视图i中的坐标,i= 1,2,则每个对应的当pTFp2= 0时,证据提供了对基本质量FR3×3的线性约束。在本实验中,我们考虑基本矩阵估计的线性化版本[13],其中内点阈值设置为0。02对于所有图像对。RANSAC和Lo-RANSAC的迭代次数被设置为匹配WI的运行时间。我们在表1中报告了平均(运行所有算法20次)共识和运行时间。注意:(1)A1-尽管L1通常非常快,但所发现的一致性大小小于基于伯努利的方法WI的一致性大小;(2)允许RANSAC和Lo-RANSAC与WI同时运行,但WI在返回的一致性大小方面仍然更好;(3)WI实现与MBF几乎相同的一致性大小,但具有更少的时间成本(在图像对198-201、417- 418上)。420,579-582,WI发现平均共有大小略高于MBF)。更多细节见补充资料。4.3. 单应性估算本实验将单应性估计与线性残差模型结合起来考虑。对于由{(xi,yi)}表示的两个视图的一组对应关系,8973∈∈表1.线性化基本矩阵估计的结果RANSAC和Lo-RANSAC的权重被设置为WI的权重104-108198-201417-420579-582738-742L1共识252264317497429时间(s)0.850.070.040.060.09RANSAC共识266.55284.00353.30497.05432.60(262,270)(283,285)(351,356)(492,503)(428,440)Lo-RANSAC共识268.55284.90355.25501.45439.35(266,273)(284 287)(354,356)(496,506)(432,443)MBF共识271.70287.70358.95507.15444.20(268,274)(284 289)(357,360)(503,510)(442,446)时间(s)3.171.882.363.613.19(2.65,4.41)(1.65,2.47)(1.96,2.66)(3.17,4.36)(2.68,3.56)Wi共识271.55288.35359.05507.65444.15(269,274)(286 289)(356,360)(502,510)(442,446)时间(s)2.641.752.103.423.09(2.26,3.31)(1.43,2.03)(1.82,2.51)(2.93,4.15)(2.80,3.57)xi,yiR2,设x∈i=(xi,1)T,y∈i=(yi ,1 ) T为齐次表示,单应性估计就是求一个 矩阵 HR3×3,使得对于内点,yi=Hxi。 由于H是8维唯一定义的尺度,因此可以将具有线性残差的单应性估计表示为线性回归问题(详见[ 13 ]中的第4章)。 我们 使 用 来 自 苏 黎 世 建 筑 物 数 据 集 的4个图像对(Building 5,22,28,37)。类似于线性化的基本矩阵估计,VLFeat工具箱用于提取SIFT特征和对应匹配。请注意,每个对应匹配产生两个残差函数,这意味着数据点的数量,内点/离群点在优化中加倍。图6. 4个苏黎世建筑物图像对的线性化单应性估计的比较结果:(左)比较共识大小和(右)运行时间。所有实验重复20次。在这个实验中,我们允许RANSAC和Lo-RANSAC与WI运行相同的时间-只是为了显示它们在这样的预算下的能力。内点阈值设置为0。1.一、从图6中,我们发现WI可以在四种基于采样的方法中实现(大致)最佳性能。WI的运行时间平均小于MBF。WI和MBF之间的进一步比较可参见补充材料。5. 结论我们研究了与Max-Con问题有关的加权影响.我们的分析比[24]在加权测度的包含和“非理想情况”的研究方面将加权影响简化到[24]的算法中是简单的。正如对合成数据和真实数据的实验所证明的那样,这样做是[24]的有效替代方案(大致上,在实现类似共识的同时节省一些运行时间,或者在类似时间预算的情况下实现更好的共识)。然而,主要的信息是,与其将有偏抽样视为(更有效地)估计均匀影响的某种方式,并“相信”由此引入的(估计中的)偏差对影响的排序(特别是对影响力大于内点的离群值)没有不利影响,对有偏测量的适当研究使我们能够分析这些影响测量的变化,检查是否保持正确的顺序。我们解决这两个“自然”家庭的偏见措施:伯努利和均匀在一个固定的汉明水平。当然,我们的工作有两个明显的局限性:我们的分析(理想情况)必然涉及假设,这些假设与现实世界数据的相关性可能受到质疑,我们的实验并不详尽。鸣谢:这项工作得到了澳大利亚研究委员会拨款DP200103448(D)的部分支持。苏特·E Zhang)和DP200101675(T.- J. Chin)。引用[1] Khurrum Aftab和Richard Hartley。迭代重加权最小二乘对稳健m-估计量的收敛性。在89742015年IEEE计算机视觉,第480-487页,2015年。1[2] Zhipeng Cai,Tat-Jun Chin,and Vladlen Koltun.共识最大化树搜索重新审视。在ICCV,第1637- 1645页,2019年。一、二、六[3] Tat-Jun Chin,Zhipeng Cai,and Frank Neumann.计算机视觉中的鲁棒拟合:容易还是难?在ECCV中,第701-716页,2018年。1[4] Tat-Jun Chin , Pulak Purkait , Anders Eriksson , andDavid Suter.树搜索的高效全局最优共识最大化。在CVPR,第2413-2421页,2015年。1[5] Ondrej Chum和Jiri Matas。与prosac匹配-渐进样本共识。见CVPR,第220-226页,2005年。1[6] Ondrej Chum,Jiri Matas,和Josef Kittler.局部优化的ransac。在Joint Pattern Recognition Symposium,第236-243页,2003年。1、6[7] Ronald Fagin , Ravi Kumar , and DakshinamurthiSivakumar. 比 较 top k 列 表 。 SIAM Journal on discretephonematics,17(1):134-160,2003. 7[8] 尤瓦尔·菲默斯Friedgut–Kalai–Naor theorem for slices ofthe 芝加哥理论计算机科学杂志,第14:1-14:17,2016。4[9] 尤瓦尔·菲默斯布尔超立方体切片上函数的正交基。电子组合学杂志,23(1):P1.23,2016。4[10] Martin A Fischler和Robert C Bolles。随机样本一致性:一个范例模型拟合与应用程序的图像分析和自动制图。Communications of the ACM,24(6):381-395,1981.1、6[11] 大卫·加马尼克。重叠间隙属性:随机结构优化的拓扑障碍。美国国家科学院院刊,118(41),2021。6[12] Andreas Geiger,Philip Lenz,and Raquel Urtasun.我们准 备 好 自 动 驾 驶 了 吗 ? Kitti Vision 基 准 套 件 。 在CVPR,第3354-3361页,2012中。7[13] 理查德·哈特利和齐瑟曼·安德鲁计算机视觉中的多视几何学。剑桥大学出版社,2000年。七、八[14] G Kalai和S Safra。门槛现象和影响,从数学,计算机科学和经济学的角度技术报告,讨论文件系列dp398,理性和互动决策理论中心,希伯来大学,耶路撒冷,2005年。4[15] Huu Le,Tat-Jun Chin,and David Suter.局部收敛最大一致性的精确罚方法。在CVPR,第1888-1896页,2017年。1[16] Huu Minh Le,Tat-Jun Chin,Anders Eriksson,Thanh-Toan Do,and David Suter.最大一致稳健拟合的确定性近似方法IEEE TPAMI,43(3):8421[17] 李宏东。鲁棒几何估计的保证全局最优性的一致集
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功