没有合适的资源?快使用搜索试试~ 我知道了~
过滤器流量实用化:大规模并行和无锁定
1过滤器流量实用化:大规模并行和无锁定萨蒂亚·N威斯康星大学麦迪逊分校ravi5@wisc.edu威斯康星大学白水分校mukherjl@uww.edu威斯康星大学麦迪逊分校yxiong43@wisc.edu威斯康星大学麦迪逊分校vsingh@biostat.wisc.edu摘要本文的灵感来自于塞茨和贝克的一个相对较新的工作,其中介绍了所谓的过滤流模型。过滤器流通过识别大的低分辨率图像集合来找到与一对(或多个)图像相关的变换。校准线性滤波器;对这些滤波器的某些结构特性施加额外的约束,使得滤波器流能够用作视觉问题谱的一般“一站式”构造:从光流到散焦到立体到仿射对准。这个想法是美丽的,但好处并没有在实践中得到证实,因为重大的计算挑战。这个问题使得大多数(如果不是全部)实际视觉问题的部署遥不可及。我们的工作的关键是识别这个模型的几何(近)等效的重新表述,可以消除这个严重的限制。我们通过一个详细的优化为重点的发展,证明过滤器流量确实可以相当有效地解决了广泛的instantiations。我们推导出高效的算法,进行广泛的理论分析,重点是收敛和parallelization和显示的结果竞争力与国家的最先进的许多应用程序可以实现与negigible应用程序特定的调整或后处理。实际的数值方案易于理解,并且实现(Matlab中的30行)-该开发将使Filter Flow成为可行的通用求解器和社区中大量应用的测试平台。1. 介绍理解同一场景的两个或多个图像是如何相关的,是计算机视觉中的一个基本问题通常,各个图像的坐标系通过相机运动而相关,而在其他情况下,场景照明可以改变,阴影可以不同和/或曝光、变焦和其他参数可以改变。相机可以从一个图像修改为另一个图像这些效应通常导致图像强度的系统性(但在其他方面是任意的)变换为了能够进行后续分析,重要的第一步是恢复描述图像之间关系的虽然在技术上是准确的,但上述描述实际上涵盖了广泛的一大类问题。在实践中,这个类中的大多数问题不是一个通用的策略,而是通过将其作为高级“转换估计”目标的具体实例来逐个解决的。明确使用与待解决的特定问题有关的附加信息(例如采集细节、待估计的参数和应用特定约束)。本课程中的代表性问题对应于现代视觉文学中的一些核心主题:光流[30,24,38]、去卷积[21,27]、非刚性变形[25]、立体(加上其变体)[34,23,37]、散焦[22]等等-这些都是不同的问题,但是在高层次上,处理估计两个或更多图像之间的关系。多年来,这种划分处理为许多问题提供了高效的算法和行业实力的这样的解决方案现在推动了许多下游交钥匙应用。尽管每个独立问题都有多种高效和成熟的人工租赁,但下面是一个有趣的科学问题考虑到许多这些公式试图估计一个变换,解释两个(或更多)图像的图像强度的变化,我们可以设计一个统一的公式,是足够丰富的模型广泛的一类变换,但提供的灵活性,精确地表达上面列出的每个不同的问题的细微差别在几年前的一篇有趣的论文中,Seitz和Baker提供了一个名为Filter Flow的框架。Filter Flow将图像变换建模为待估计的空间变量(像素特定)35493550∈- 将一对图像I1和I2相关的线性I2=TI1,T∈Γ,(1)其中T可以被认为是过滤器(或运算符),其行分别作用于源图像的矢量化版本。观察到计算由第一个恒等式指定的变换T的逆问题是严格受限的。为了使模型(1)有意义,TΓ必须充当整个附加集合的占位符。对过滤器的约束,其实现满足我们对感兴趣的特定问题的期望的唯一解决方案光流、具有照明变化的立体或仿射对准。但是想象一下,如果问题特定的需求实际上可以被编码为可行性集,那么过滤流公式提供了一个有趣的“一站式”模型,其中我们试图估计的未知变换是线性的 事实证明,视觉问题的整个目录非常适合这个公式:从散焦到具有高阶先验的立体声,到具有丰富的域特定先验的光流,每个都有自己特定的可行性集合r。这种配方具有几个优点:(a)它将传统的非线性或变分公式重新参数化为可以仅通过线性规划来解决的优化问题;(b)可以容易地修改(1)中的形式以结合另外的域特异性原,其可选择地需要在为特定目标设计的算法中进行更重要的结构修改,以及(c)虽然它可能不是用于所有可以以这种形式表达的问题的银弹,但相应的解决方案可以提供强基线并驱动更有效算法的开发。从理论角度来看,模型(1)简单而优雅。不幸的是,对于我们在实践中通常遇到的图像尺寸,(1)的直接优化是不容易的。在中等到大规模的环境中运行模型,例如,对于视频序列来说是不可能的。这看起来可能违反直觉,特别是因为目标和约束是线性的。那么,为什么这个模型不能用大规模线性规划求解器来求解呢?事实证明,虽然这种方法保证了全局最优性,但即使在高端工作站上,也无法实例化即使采用多分辨率金字塔计划作为实践启发式,运行时间也从9到20多个小时不等,具体取决于问题类型和相关约束,作者承认这是一个弱点[35]。此外,一些问题需要在非凸的对象中添加项;这些问题通过一系列线性程序(在每次迭代时使用线性近似获得)来解决总之,这一有趣的公式的潜在范围和适用性尚未完全实现,这在很大程度上是由于其严重的计算足迹。本文的主要目标是消除这一限制,使Filter Flow实用化。相关工作:本文的主要动机是设计过滤流的实用算法[35]。此外,我们在第5节中讨论了几个案例研究,具体到可以建模为过滤流的问题。处理光流[18,1]、仿射对准[20]和立体匹配[14,17]等问题的文献已经相当成熟,这里不再详细讨论,以免偏离本文的主要算法重点。在继续之前,我们指出舰队等人,[10]还提出了线性运动模型来表示各种或复杂的运动,我们的许多构造将适用于这些早期论文中的思想。我们强调一些应用领域的过滤器流模型最近已经相当成功地应用在[16]中,作者提出了一种方法,该方法使得空变多帧盲反卷积的滤波器流构造有效。后来,[9]使用这个公式计算场景深度从立体相机对下的一系列照明方向。在[15]中,过滤器流已被有效用于快速去除非均匀其他人[32]已经重新制定了过滤流中的平滑度,使其适用于各种应用,包括alpha抠图。这些方法表明,过滤流的适用性,一组不同的问题是可能的,但有十个涉及不同的解决方案。我们相信,一旦计算挑战得到解决,过滤流方法将在视觉中得到更广泛的应用。捐款. 我们前面的讨论表明,商业线性规划(LP)求解器并不适合求解(1)。然而,我们发现,在大多数情况下的过滤流(在特定的视觉问题的上下文中),该问题具有显着的结构,可以通过专门的优化方案加以利用。特别是,我们看到,对于[35]中描述的仿射对准和光流等问题的五个案例研究中的每一个,几乎等效的重新表述允许数值优化方案的适用性,该方案将标准工作站上的运行时间从数十小时减少到几分钟,而不使用任何启发式策略。所谓近似等价,是指在所选择的容差范围内,两个问题具有相同的最优解 在建模方面,我们提出了一个新的凸鼓励稀疏性的项,称为紧性项,一个2 ×2数据项和一个有效的不等式,减少了参数的搜索空间。在算法方面,通过一些更多的操作,这些问题揭示了适合大规模并行的无锁实现。为此,我们提出了一个有效的异步并行算法,解决我们的公式比以前的模型快30倍,并在经验上具有竞争力的最先进的求解器,3551222≥||−||N2数量上和数量上。详细描述了这些性质和相应的算法与收敛保证是我们的主要贡献。记法:我们用ei来表示标准基向量,1表示所有1的向量。此外,R2给出了适当维数的概率单形。小写字母表示R上的向量;大写字母表示R上向量空间之间的线性映射。由于篇幅限制,所有的证明都包含在附录中2. 过滤器流量我们简要回顾了过滤流的关键组件[35],以建立我们的讨论。设I1和I2是要计算其滤波器流在我们的公式中,可以假设I1和I2是Rn中的向量,其中n是图像I1(或I2)中的像素总数。那么过滤器流量可以用公式表示为以下优化问题1,I1中的所有像素都被仿射矩阵A变换(the[35]中所谓的GLOBA-M约束);(ii)对于OP-在纹理流中,我们鼓励相邻像素的仿射运动的平滑性;(iii)对于精确整数流,引入了鼓励稀疏性的项;(iv)对于立体声,我们要求M的行之间的平滑度。这些术语的具体细节将在后面的案例研究中介绍。3. 化学重组我们的基本假设是,重新制定的过滤器流问题将使我们能够设计实用的算法与全局收敛的保证。不幸的是,在标准计算机视觉问题的特定公式中使用的附加术语/约束(在前一节中描述)原因有二:(i)一些决策变量的非凸性,以及(ii)即使当优化问题是凸的时,附加项也导致复合函数或约束。minT∈Rn×n ||二、||2.(二)例如,在强加一个ffinesmoothness(用于op-(实际流量),我们添加术语ij∈N(i) ||2在||2in等价地,TI1的第i项是I1强度的线性组合。作者在[35]中进一步将T分解为T=MK,其中M是运动矩阵,K是一个核矩阵。M−1编码从I2到I1的运动,因此我们可以将物镜写为MI2KI12。特别地,在纯运动的情况下,K是单位矩阵。我们的结构可以用于非平凡的K,但我们假设K是单位矩阵,以简化我们的presentation和不失一般性交换I2和I1。由于这个公式是受约束的,[35]提出了一些对M的自然约束,如下所述。非负性:负系数是没有意义的;所以我们施加了一个约束条件,即M 0.行单纯形约束:我们还要求,M的每一行中的系数之和为1,即,I2中的每个像素是I1中像素的凸组合。此外,我们将每个像素i的邻域定义为(i),并确保该邻域之外的像素不参与凸组合。因此,我们可以将我们寻求解决的优化问题写为,目标,其中Ai是与以下项相关联的仿射运动:像素岛这些术语使得使用标准现成的求解器来优化问题变得困难,因为它需要多次通过数据来计算梯度。我们重新表述的目标是减轻这些问题,同时保持过滤器流模型的整体行为。接下来,我们将确定一些高级问题,这些问题使优化具有挑战性[35]中提到的约束,并提供替代方案。我们的攻击路线(或工作流程)如下.我们将首先解决过滤流模型的主要(计算上)问题,并为每个问题提供易于处理的重新表述。我们的希望是,这些重新表述将满足“更好”的技术条件,这将指导总体优化方案的选择。然后,我们将描述如何通过利用特定计算机视觉问题的问题结构(案例研究)来进一步专门化该方案。我们的目标是,每个特定的实例化都应该可以通过修改总体优化的几行代码来实现,并且仍然保持效率优势。min ||MI1− I2||2(三)3.1. 重新定义紧凑性S.T.M≥0Σj∈N(i)Mij=1,2Σj/∈N(i)Mij= 0,mi = 1至n。理想情况下,我们希望找到图像对之间的对应关系,其中I1中的每个像素都精确映射I2中的单个像素。为了确保稀疏性,[35]提出了一个虽然上述描述用作本发明的基本模板,紧凑性术语,定义为,在问题(3)中添加了过滤流模型、各种附加约束和项,以对感兴趣的底层计算机视觉问题进行建模。具体例子如下:Σ Σ我j∈N(i)MijΣ||(j − i)−MijIJ(j −i)||2(四)包括:(i)对于仿射对齐问题,要求1通过个人交流[35],我们知道选择范数是为了允许LP求解器的适用性,而不是模型的核心。但紧性项使目标函数非凸(实际上是凹的),因此,在[35]中必须使用线性化最初,3552−∈2∈∈2引理3.1||一||我≥2项被设置为零,并且在没有紧凑性项的情况下计算光流。在第一次迭代之后,使用紧性函数的线性近似,并且求解相应的线性规划(LP)。这需要多次解决一个巨大的LP问题(即使实际上使用的迭代次数仅为3 -4)。其次,求解器需要对数据进行完整的传递(或IM),在每个像素i处的单位距离仿射变换,由AiR2×3表示。直观地,Ai捕获像素i处的滤波器的质心的运动。为此,[35]施加了一个硬“LOCA-M”约束(将流量设置为等于质心)。相反,我们使用对偶形式并添加目标函数(λ2>0)中的项,即,Σ年龄),以便计算紧凑性的线性近似,这是昂贵的。λ2||Aii−Mi||2我(六)凸紧项?为了成功地用一个更有效的替代项来替换紧致项,我们首先考虑这样一个项需要编码的一些有用的属性:1)随着正则化参数的增加,它应该倾向于在每行中保持单个非零条目,2)函数的值及其导数应该是可有效计算的,以及3)它应该容易优化。为此,N1范数是获得稀疏解的自然选择。但事实证明,范数是常数(= 1)其中MiR2是滤波器在pi x eli处的质心,R3是在齐次坐标中的像素i,其中第三项等于1。只要近似解足够,我们就固定λ2的值 我们将其视为二次惩罚,如果需要更精确的解,其保证(参见[26])当我们的算法终止时满足等式约束,完全如[35]的。最后,为了获得平滑的流,将以下项添加到目标function(λ3>0),在我们问题的可行集上,所以它不适用。然而,观察到对矩阵M的约束意味着M是行随机矩阵。 所以,如果我们考虑Σ Σλ3我j∈N(i)||2||2(七)M的每一行是n个变量上的概率分布表,那么我们需要最优概率分布有小的支持,也就是说,我们希望我们的紧性项表现得像最少数字的线性组合现在,我们给出了一个结果,显示了仿射变换矩阵的一个有趣的性质,并在下一节中通知算法的选择。delta函数。在[28]中,作者证明了这个问题的一个放松版本可以在n秒内解决2F最近,C>0。C是一个有效的不等式,cone programmes并行的后来,[8]提供了一个凸公式,鼓励单纯形的稀疏性,并表明它更鲁棒。使用附录中经验证明的这些想法,我们可以将问题写为,Σnmin||MI1−I2||+ λ1||M[:,i]||二(五)直觉上,这个引理说的是Ai 注意到,1(坐标方式)和将像素的移动限制在滤波器内意味着M<$i受邻域大小的限制,这给了我们对C的最严格选择。 这个引理意味着(一个最小二乘问题的最优解是M≥0 ΣS.T.j∈N(i)2Mij=1,i=1ΣMij=0,j/∈N(i)包含在一个凸紧集合中。更重要的是,这个引理表明,我们没有通过增加这个不等式来损害任何其中λ1>0是固定的,M[:,i]表示M的i-列,λ1是正则化参数。直觉上,惩罚是一个群体套索式的惩罚,由M的列给出。因此,该术语鼓励沿着列存在很少的非零条目,并且与行上的总和为一的约束一起使得行稀疏,从而实现期望的属性。3.2. 重构仿射光滑度确保跨像素的变换的平滑性对于诸如光流之类的若干问题是重要的。在这种情况下,仿射平滑度项在[35]中显示优于其他二阶平滑度项,并在实践中产生更平滑的流场。为了鼓励仿射平滑,我们定义了一个显式的6pa-3.3. 我们应该使用哪个求解器?[35]中的模型与我们的方法之间的关键区别之一是我们用特殊类型的紧性鼓励范数取代了R1范数,使目标成为光滑凸函数。本节将看看这种范数的改变与上述引理一起如何能够利用最近开发的凸优化技术,该技术可以将优化时间加速几个数量级,假设案例研究的特定项也可以被操纵和重新公式化以服从我们的优化方案。我们现在讨论两个关键属性,即,近似和随机化将指导适当优化方案的选择。接下来,我们在模型的上下文中激励这些选择3553CCC-||||←−F←−A) 近似值:考虑在紧凸集上求解有限维优化问题。这类问题通常使用投影梯度方法(在多次迭代中)来解决,该方法涉及在可行集上的每一步投影目标。这需要在可行集上优化二次函数这些算法允许大的变化,在工作集在每次迭代不同的活动集的方法,因此可以应用于大规模的问题。然而,主要的缺点是,即使可行集非常小,简单的投影子问题如概率单形、椭球、n-1范数球等,其相应的投影子问题是非平凡的。对另一方面,存在约束优化方法,其包括在每次迭代时在可行集上优化线性函数在文献中,解决上述形式问题的方法被称为可行方向法[3]。条件梯度法(CGM)是一类具有较好理论收敛速度[3]并适用于我们的过滤流模型。最近,CGM在解决许多机器学习问题(包括SVM和核规范化问题)方面表现良好,参见[12,19],但仅在视觉中少量使用。实际上,当满足以下两个属性时,该方法在实践中蓬勃发展:i)可行集是紧凸;以及ii)优化线性函数,可行集是容易的。B) 随机化:如前所述,(7)中的双重求和项是计算瓶颈,因为它需要对数据进行完整的遍历以计算梯度。它已被证明[2,29],近似一阶信息可以用来解决这种大规模的优化问题,称为随机或随机算法。这些方法比传统条件梯度法(Conditional Gradient Method)条 件 梯 度 法 ( CGM ) : CGM 解 决 了 形 式 为minx∈Cf(x)的问题,其中f是有限维光滑凸函数,是紧凸集。给定一个可行的起始点,算法的每次迭代都求解f的线性近似,并在连接当前点和线性近似的解的线段中选择一个点。这也证明了新的观点是可行的。CGM的基本1.一、假设可以容易地计算梯度,则算法1中的步骤(*)确定CGM的复杂度Ob-表示有界的要求是必要的,因为否则来自步骤(*)的s将是无界的。CGM找到了重新表述的过滤流问题的全局最优解,因为M由(5)中的构造限定,并且Ai 这表明,如果我们暂时不担心问题的具体重新制定,CGM可以很容易地部署。随机区组坐标CGM(RBC-CGM):我们提出了一个异步随机块坐标下降的经典CGM为我们的目的。我们算法的最简单形式在Alg中概述二、在第3节中所做的重新表述已经得到了所需的简单子问题(#)。为了计算sd,我们找到对应于gd的最小元素的索引,并将其设置为1,使所有其他元素为0,并且sA=CgA/ gA,这需要计算范数。这使得我们的算法非常简单的实现和高效。算法2RBC-CGM虽然收敛确实选择任意像素i。对于t= 0,1,2,···,T做算法,并且通常可证明对噪声具有鲁棒性[13]。我们的策略是结合条件梯度法,gd←M[i,:] f,gA←Aif不不ods与随机化,以开发高效的随机块坐标条件梯度[6,5]算法(RBC-CGM),具有强稀疏性和收敛性保证,以解决标准的过滤流公式。我们展示了如何RBC-CGMs可以有效地用于串联与强大的分布式凸优化计划,从而在这些问题的实际算法。在我们介绍随机版本之前,我们简要回顾了(de-算法1条件梯度法(CGM)选择一个起始点x0∈C。对于t= 0,1,2,···,T做g←f(x)s←arg mins∈Cstg(*)xt+1(1 γt)xt+γts端sd,sA←arg mins∈N,||Q||2≤Cs gd,q gA(#)[M[i,:];Ai](1γt)[M[i,:];Ai]+γt[sd;sA]结束时结束4. 算法及收敛性我们现在讨论上述算法的一些技术性质。空间复杂度和迭代边界:如果像素i被访问t次,则清楚的是,T[i,:]中的非零条目的数量至多为t。换句话说,在几次迭代之后,有可能获得对流动的合理估计。像素i.此外,邻域大小通常相对于图像的大小是小的,这意味着在几次迭代之后,它识别当前像素被移动到的图像的区域。从经验上讲,我们可以3554F2FF←2FF2←·||−||在100个时期之后停止,(即,当每个像素被处理器访问100次时),如果滤波器大小是[-10,10]2。秒-一对图像。它可以表示为min||MI1− I2||2其次,我们可以很容易地估计所需的迭代次数在开始算法之前,对于固定量的存储器。我们现在将证明一个引理(证明在附录中),即:M,AS.T. M [i,:] ∈N,||一||22≤C,Ai=M<$ii(八)建立了该算法的块下降属性,可用于将算法简单地并行化。引理4.1将目标表示为f(y):Rn→R,其中f是凸的、光滑的,并且y被分割成J=其中A ∈ R2×3是捕获I1和I2之间的仿射偏差的全局仿射矩阵,并且λ是单位单形。设Ai为每个像素i的仿射矩阵。然后我们还可以将(8)的等价形式写为,min||MI1− I2||2{1,…,J}块,即,y =[y1,y2,...,[1],则yi∈Yj,则我们有dTif(yi(t))≤ −C′||di(t)||2,其中diM,A ¯(九)2i2s. t. M [i,:] ∈ M,Aii = Mi,Ai= A,||A我||F≤ C i是更新的方向,即,yi(t+ 1)=yi(t)+γtdi(t)C′>0是常数。在对偶等式约束Ai=A之后,我们可以将优化问题写为(λ> 0),使用上面的引理和命题5.1min||MIΣ-我||+ λ||一- -一个||2在[4]中,我们可以部署一个异步算法假设-处理器更新之间的时间延迟是M,A1 22 iF我(十)有界当然,这并不能证明每次更新都会降低目标函数的保持可行性。事实上,在条件梯度型方法中,除非我们使用线搜索方法来计算满足Armijo条件的步长γt,否则但这违背了异步方法的目的,因为每个处理器将花费任意长的时间来进行一次更新,从而影响收敛速度。此外,恒定步长策略通常取决于目标函数的参数S.T. M[i,:]∈N,Aii=M<$i,||A我||2≤Ci注意,这个问题满足3.3节中提到的两个性质。并行化:模型(10)可以如下容易地并行化。每个工作者挑选一个像素i,解决相应的优化问题并更新Ai。请注意,我们没有明确规定,||一||模型中2 ≤C。在所有工作者更新Ai之后,A可以被更新和难以先验计算的约束。幸运的是,在这种方法的收敛性证明中,我们证明了步长序列的特定选择决定了因为,ΣAarg min一我||F||F(十一)先验保证收敛(参见[19]),并且仅取决于迭代次数,使得算法自然易于并行化[4]。这是有用的,可以看到,收敛是使用对偶间隙原理建立的,而不仅仅是使用原始优化问题。上面的引理说明了我们算法的正确性,即我们算法生成的序列的任何极限点都收敛于最优解以与其序列方差相等的速率迭代但上述优化问题只是计算所有Ai的我们使用增量梯度下降法以0α<$1为对偶步长的方法λ,见[2],λλ+ α(i A1A2)。光流:把第(3)节中有关光流的目标和约束条件放在一起,我们可以将优化问题写为:也就是说,O(1/N)。对于显式收敛率,参见[36]。minΣn||2 + λ 1 ||2 + λ 1||2||2在[36]中考虑的许多方面,如碰撞,分层更新不会影响此处考虑的问题M≥0,Ai Σ2i=1ΣΣ因为单个工人之间的延迟是可以忽略的。+λi||Aii − Mi||2+λ3||2||2(十二)所以我们的证明要简单得多。现在我们将看到更新方案如何针对特定问题进行更改。S.T.2 2 2i ij∈N(i)ΣΣMij=1,Mij=0,||A我||2≤ Cij∈N(i)j/∈N(i)5. 案例研究我们研究了三个具体的问题,立即受益于快速过滤器流配方。我们还讨论了并行求解器,如果适用的话。仿射对齐:仿射对齐问题处理的任务是找到全局仿射对齐,请注意,λ1和λ3是优化问题的参数,因此是用户指定的常数。该模型与仿射对准问题的主要区别是我们对每个像素使用不同的对偶变量λi。这通常是有用的,因为光流是使用金字塔方法计算的,所以我们在局部得到了Ai的良好初始化同样,我们看到这个问题满足两个性质235552F222 22图1:光流结果:前4列显示MPI Sintel数据集的结果,后4列显示Middlebury数据集的结果。第1至3列(第5至7列)分别显示了真实数据、我们的结果和Epicflow结果。第4列(和第8列)显示了错误映射。第4列的AEE为1。08,1. 十五,一。03,第1至3行。第8列的AEE为0。06,0。042,0。033,第1至3行。我们的结果用红色标记。在第3.3节中提到。并行化:每个工人解决以下问题,min(MtI1−etI2)2+λi||Aii−Mi||2设置:首先,我们简要描述了实验设置。Jiang:我们使用Lucas Kanade算法来获得流量的初始估计,该算法适用于大多数设置。步长:步长γ的选择决定了M[i,:],AiΣ[i,:]i2 2Σn不聚散虽然可以使用线搜索,但它可能是子搜索。+j∈N(i)||2+ λ1||2+λ1i=1||2||2(十三)对于我们算法的(部分)异步方面来说是最佳的,Rithm(例如,处理器之间的时间延迟)。对于我们的并行版本,每个处理器使用自己的迭代计数。S.T. M[i,:]∈N,||A我||2≤C我们使用[11]中提出的策略,通过设置γt2κ+t+2优化问题和λi可以在每个工作者中本地这就给出了一个无锁异步并行算法.在每个工人完成上述子问题后,λi被更新为,.Σλi←λi+α·||Aii−Mi||2(14)立体:立体匹配问题使用局部平滑模型而不是全局仿射平滑来公式化,如下所示:其中κ >0是取决于目标的常数。实施情况:我们使用了一个8核3.60GHz的处理器机器,12GB的RAM,和英特尔TBB在C++的任务并行。我们固定λ3= 0。005,λ1,λ2= 1,对于所有问题和所有数据集。 未执行其他参数调整。请注意,由于求解相应LP的成本,在高分辨率图像上评估滤波器流[35]是有问题的。因此,我们使用最先进的光流法[31]进行比较。对于低分辨率图像,我们的方法和Filter Flow的结果在定性和定量上相似(见附录)。Σnmin ||MI1−I2||2 + λ1||2+ λ3||2 +λ3Σ ||Mi−Mj||光流: 我们从光流问题M≥0S.T.2i=1ΣΣMij=1,2i、jMij= 0,i(15)因为从过滤器流量的角度来看,它在计算上要求最高[35]。我们使用了两个标准的光流数据集:MPI Sintel[7]和Middlebury [1]。MPI Sin-j∈N(i)j/∈N(i)tel是大型位移数据集,而Middlebury更多的非线性运动MPI Sintel由两个版本组成这里的更新是针对光学流问题,因此相同的并行化方案适用。6. 实验我们目前的三个案例研究的实验结果介绍在第5节。我们的目标是评估(a)我们的算法相对于不使用重构策略的alternatives的运行时改进的程度;(b)重新制定的过滤流模型在最佳解算时,实际上是否能够产生与专门为每个案例研究开发的专用算法相竞争的结果;以及(c)整个方案是否足够有效,以使适合(3)中模型的视觉中的新问题能够快速原型化我们接下来讨论这些问题。=23556序列的选择,干净和最终具有相同的地面真理。为了显示[ 35 ]中“标准”过滤流公式的性能(定性和运行时间)在那里-方法最后一传干净的传球所有NOCOCC d0-10 s10-s40 所有NOCOCC d0-10 s10-s40F3-MPLF(Ours)6.272 3.092 32.207 5.0423.2264.770 2.062 26.863 3.4591.883流场5.810 2.621 31.799 4.8513.739 3.748 1.056 25.700 2.7842.110FullFlow5.895 2.838 30.793 4.9053.373 3.601 1.296 22.424 2.9442.055离散流6.077 2.937 31.685 5.1063.832 3.567 1.108 23.626 3.3982.277EpicFlow6.285 3.060 32.564 5.2053.727 4.115 1.360 26.595 3.6602.117TF+OFM6.727 3.388 33.929 5.5443.765 4.917 1.874 29.735 3.6762.349NNF-本地7.249 2.973 42.088 4.8964.183 5.386 1.397 37.896 2.7222.245图2:MPI Sintel数据集测试集的光流结果。3557×2≈≈≈×≈···图3:立体声结果:(从左到右)前三个图显示了对Middlebury 2011数据集的评估。我们的结果与地面实况非常吻合;最后三个显示了对2014年Middlebury数据集的Recycle对的评估;第五个图像是总时期的10%之后的结果,而最后一个图像是50%之后的结果。这意味着运行更多的epoch逐渐给出更准确的解决方案。 我们的结果用红色标记。因此,我们报告了我们的方法和Epicflow [31]在干净序列上的结果(注意,Γ中的附加项可以包含这些特定情况的约束)。代 表 性 的 定 性 结 果 如 图 所 示 1 用 于 MPI Sintel 和Middlebury数据集。MPI Sintel测试集的结果如图所示。二、 结果表明,该方法是可行的。1强烈表明,定性,我们的结果显然是从Epicflow获得的 在MPI Sintel中(图1(顶行)),我们的结果显示出更好的一致性与地面真相(楔形在左边,小流量在头发区域)。第4列中的误差差异图几乎全黑。在图1(第2行)中,我们的解决方案能够准确地恢复黄色区域中的血流,尽管头部区域中的估计更加模糊。 在图1中(行(3)两种方法的结果完全一致。平均终点误差(AEE),计算为像素数上的Frobenius范数,在范围[0. 03,0。06]和[1. 02,1。2]分别针对非遮挡像素的Middlebury和MPI Sintel数据集。定量,这是竞争与最近的光流论文,报告结果,这些数据集。在大多数其他序列中,我们看到类似的整体行为,其中我们的解决方案与地面实况具有良好的这是特别值得注意的,因为除了第5节中描述的约束之外,没有使用其他光流特定的修改。除了中值滤波器之外,不需要任何后处理。Stereo:Stereo模型与Opti- cal Flow的主要区别在于它不包括MRF-A项,使优化更容易。我们在MiddleburyStereo 2014 [33]和2011[1]数据集上测试了我们的算法,这些数据集是标准的立体匹配数据集。2014年的数据集是具有挑战性的,因为它包括2864 1924张具有大移动的图像。图3显示了我们算法的代表性结果。我们的方法在为2011年数据集找到正确的匹配方面做得非常好,总体AEE仅为0。07.由于数据集的大小,2014年的数据集需要更多的迭代来求解,但结果与其他方法获得的结果相当。仿射对齐:回想一下,仿射扭曲完全由6个参数决定。为了测试我们的算法,类似于[35],我们用仿射变换人为地扭曲了图像,然后分析了re-overed A和真实A之间的误差。结果表明,||2 非常小(在10−3以内),这表明从FilterFlow模型恢复的翘曲接近真实翘曲。||2wasverysmall(within10−3)suggestingthattherecoveredwarp from the Filter Flow model is close to the true warp.我们的数值方案大约需要2分钟来解决,而[35]中提到的是3总的来说,这里介绍的3个案例研究结果表明,我们的过滤器流量求解器提供了高质量的解决方案,以不同的,各种图像变换问题。这些案例研究的其他结果见附录。运行时间最后,我们描述了我们的算法如何执行w.r.t.到运行时间,这可以说是它最重要的优势。对于所有的实验,我们只运行了150个epoch的算法:我们的算法的顺序版本花费2小时,而我们的并行实现对于640× 480图像对花费10分钟,这表明并行算法几乎获得与#核心成比例的加速。附录包括一个图的收敛的目标函数直接建议的理论。它给出了经验证据,即150个历元足以得到近似解。请注意,过滤器流量[35]报告的相应时间为9+小时。7. 结论我们提出了一种过滤流的重新表述[35],这使得它适合于大规模并行异步优化方案。我们的重新表述适用于任何问题的过滤流格式表示。一般性并不涉及任何实际的妥协-我们展示了一系列实验结果,证明大多数应用不可知的数值求解器可以获得与现有技术的专门状态相竞争的结果。与原始模型[35]相比,运行时间从几个小时减少到几分钟。有趣的是,整个方案易于实施和教学。我们的求解器的原型版本只有大约30行Matlab代码(见附录)。完全异步求解器将作为OpenCV的一个分支提供。致 谢 本 工 作 得 到 NIH R01 AG040396 ( VS ) 、 NSFCAREER RI 1252725 ( VS ) 、 NSF CCF 1320755(VS)、NSF CGV 1219016(LM)和UW的支持。CPCP(U54 AI117924)。我们感谢Steven Seitz对这项工作进行了大量的讨论,也感谢他编写的代码。代码和附录可在https://github.com/sravi-uwmadison/fast filterflow上公开获取。3558引用[1] S. Baker、D. Scharstein,J.刘易斯,S。罗斯,M。J.Black和R. 塞利斯基光流数据库和评价方法International Journalof Computer Vision,92(1):1二七八[2] D. P. 伯特塞卡凸优化的增量梯度、次梯度和近似方法:一个调查。机器学习的优化,2010:1-38。五、六[3] D. P. Bertsekas.非线性规划1999. 5[4] D. P.Bertsekas和J. N.齐齐克利斯并行和分布式计算:数值方法第23卷6[5] T. Bonesky,K. Bredies,D. A. Lorenz和P.马斯稀疏约束非线性算子方程的广义条件梯度法。Inverse Problems,23(5):2041,2007. 5[6] K. Bredies,D. A. Lorenz和P.马斯广义连续梯度法及其与迭代收缩法的联系。计算优化与应用,42(2):173-193,2009年。5[7] D. J. Butler,J. Wulff,G. B. Stanley和M. J.布莱克。一个自然的开放源代码电影光流评估。在A.菲茨吉本等人(编),编辑,欧洲会议关于计算机视觉(ECCV),第IV部分,LNCS 7577,第611-625页。Springer-Verlag,Oct. 2012. 7[8] F.卡里湖Ning和T. T.乔治通过最优质量传输的凸聚类。arXiv预印本arXiv:1307.5459,2013年。4[9] H. Du,D. B. Goldman和S. M.塞茨双筒照相测量立体。在BMVC中,第1-11页。Citeseer,2011. 2[10] D. J. 弗利特J. Black,Y.Yacoob和A.D. 杰普森图像运动分析的线性模型的设计和使用。国际计算机视觉杂志,36(3):171-193,2000. 2[11] R. M. Freund和P.格里加斯条件梯度法的新分析和结果2013. 7[12] Z. Harchaoui,A. Juditsky和A.涅米罗夫斯基范数正则光滑凸优化的条件梯度算法Mathematical Programming,第1-38页,2014年。5[13] M.哈特湾Recht和Y.歌手.训练更快,推广更好:随机梯度下降的稳定性。arXiv预印本arXiv:1509.01240,2015年。5[14] Y. S. Heo,K.M. Lee和S.联合李你光照和摄像机不变立体匹配。计算机视觉和模式识别,2008年。CVPR2008。IEEE会议,第1-8页。IEEE,2008年。2[15] M. 赫 希 角 J.Schule r,S. Harmeling 和B. Sch oülkopf. 快 速 消 除 不 均 匀 的 相 机 抖 动 。 在 计 算 机 视 觉(ICCV),2011 IEEE国际会议上,第463IEEE,2011年。2[16] M. Hirsch,S.Sra,B.Scholkopf和S.伤害。用于空变多帧盲反卷积的高效滤波器流2010. 2[17] H. Hirsch müller和D. 沙尔斯坦具有辐射差异的影像立体匹配代价评估Pattern Analysis and Machine Intelligence,IEEE Transactions on,31(9):1582-1599,2009。2[18] B. K. Horn和B. G. Schunck确定光流。1981年技术研讨会,第319-331页。国际光学与光子学会,1981年。2[19] M. Jaggi 重温弗兰克-沃尔夫:无投影稀疏凸
下载后可阅读完整内容,剩余1页未读,立即下载
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)