Abstract

（2017SCI会议）许多计算机视觉问题，如立体深度估计、目标分类分割和前地面/背景分割，都可以表示为逐像素图像标记任务。给定一个或多个图像作为输入，这些方法的期望输出通常是一个灵活平滑的标签分配。大量的这类计算机视觉问题已经导致了重大的重新搜索工作，目前的技术水平已经从基于crf的方法转向深度CNNs，最近则是两者的混合体。尽管这些方法极大地改进了当前的技术水平，但绝大多数都只关注于改进定量结果，而没有针对低计算场景进行设计。在本文中，我们提出了一种新的计算机视觉标记任务的通用框架，称为HashMatch。我们的方法设计为完全并行，即每个像素独立处理，计算量小，模型复杂度比现有的基于CNN和CRF的方法低一个数量级。我们对HashMatch在视差估计、图像检索、特征逼近和背景相减等方面进行了广泛的评价，使HashMatch在获得高质量结果的同时，达到了较高的计算效率。

1. Introduction

由于Krizhevsky等人的开创性工作，[29]深度学习现在是各种计算机视觉问题的选择方法。虽然已经采取了大量的努力来提高各种标记任务的性能，但这些模型在计算效率上仍然远远不够。大部分关于高效深度学习的工作集中在试图压缩深度模型而不丢失精度和准确性[38,20,I1]。例如，在[38]中，作者使用输入和过滤器的二进制权值来训练一个深度架构。在[20]中，作者试图去除冗余连接，并迫使多个神经元共享相同的量化权重。其他的像[22]尝试设计更紧凑的层，使用更少的参数。类似于[38]，在[11,12]中提出的方法试图将整个网络工作进行二值化。然而，这些解决方案仍然需要许多包含多个卷积的复合层来推断每个像素的标签。虽然从计算的角度来看，这些算法的效率有了很大的提高，但由于它们存在多次的内存不足，因此这些算法在内存和计算上都有一定的局限性。

在深度学习时代之前，条件随机域(CRFs)是图像标记问题的主要工具之一。在其“最简单”的形式中，CRFs是由一个成对的术语和一个一元术语组合而成的，前者鼓励解决方案中的结构一致性，后者负责建模每个数据点/像素与一组预定义标签之间的兼容性。机器学习常被用来预测这种兼容性函数。认为一元势越复杂，求解CRF的结果越好。因此，从业人员倾向于使用昂贵的特征表示，例如HOG[13]、SIFT[30]甚至是深度学习的中间表示，然后使用高级分类器，如kernel-SVM[42]。一旦估计了每个像素的一元势，就可以执行实际的CRF推理。不幸的是，解决多标签CRFs是一个NP-hard问题[7]。高要求的快速和准确的解决方案导致了在这一领域的重要研究工作，每一个都提供了不同的权衡，在计算和接近被CRF捕获的后验方面。值得注意的是，计算一元势和以交互速率求解CRF是可能的(例如[10,48])，但是这些方法仍然有一些连续的步骤，并且具有很大的模型复杂度。

在这篇文章中，我们建议通过引入HashMatch来弥补这一差距，HashMatch是一种通用的、计算量极低的框架，它是为并行(即与像素无关的处理)而从头设计的。正如本文所演示的，我们的方法的效率和并行性使我们能够以前所未有的速度对各种计算机视觉问题取得令人信服的结果。例如，在高端gpu(如NVIDIA Titan X)上以每秒1000帧的速度估计130万像素图像的差异或分割掩模，在移动架构上以每秒200帧的速度估计VGA图像(如Tegra TX1)，同时在多个计算机视觉任务上提供令人信服的结果。我们的主要技术贡献有两方面。首先，提出了一种基于稀疏约束和反稀疏约束的分类、回归和最近邻任务的二元嵌入算法。这使得我们可以通过对每个像素进行少量操作来计算稳健的一元势。其次，我们提出了一种新的推理方案，它完全与复杂性并行运行，而不受解空间大小的影响。这些技术控制是在一个数学框架内表述的，其目标函数直接适用于许多不同的计算机视觉问题。

2. Related Work

二进制表示。 文献中对寻找二元和紧致表示的任务进行了详尽的研究。这通常被称为散列，问题通常被表述为：

于$x∈R ^n, b是\{0,1\}k$x∈Rn,b是{0,1}k中的二进制码，$h$h是哈希函数。$h$h可以是线性投影、球面函数、核函数、神经网络、非参数函数等。这里我们关注形式$h(x) =sign(xW)$h(x)=sign(xW)的线性哈希函数族，$W∈R^{ n×k}$W∈Rn×k，其中sign(x)在x≥0时返回1，否则返回0。生成这些哈希函数的最流行的数据无关方法称为位置敏感哈希(LSH)[23,9]。这些算法通常使用随机高斯投影来生成超平面W。尽管它们很简单，但在实践中这些哈希方案表现得相当好。对于LSH的广泛回顾，我们建议读者参考[51]。

依赖数据的哈希方案也被提出[19,37,8,54,21,43,56]。这些方法通常是无监督的，它们试图设计一个客观的函数，在新的二进制空间中保持输入信号的相似性。迭代量化(ITQ)[19]通过对数据进行主成分分析得到低维码，然后找到使码尽可能接近二进制空间的最优旋转。[8]将散列问题转换为一个自动编码器公式，但是部分优化方法会枚举所有可能的解决方案，导致非常慢的训练过程。在[37]中，作者利用稀疏性使运行时的成本与原始信号维数无关。然而，首先要对信号进行$l_2$l2​归一化，因此总体运行成本仍然取决于输入维数。最近，[52]使用一组快速决策树来对哈希函数建模，但是，该方法需要一个非平凡的聚合步骤，即添加compute。

我们的工作与文献中的工作大不相同。虽然大多数的方法都集中在最近邻的任务上，但是我们的框架非常灵活，可以用于从分类到信号重建的各种任务。与其他方法不同[8,19]，我们在运行时大量利用了稀疏性，并删除了诸如[37]中的规范化步骤。

图形模型中的推理。 估计一个多标记条件随机域(CRF)的最大后验(MAP)是一个众所周知的NP完全问题[7]。由于CRFs的成功使用促进了技术的发展，对这些模型进行(近似)推断受到了广泛的关注。所有解的主要区别在于它们是确定性的还是随机性的。随机方法包括马尔可夫链蒙特卡罗方法族，在最坏情况下具有指数收敛速度，但能提供精确的结果。对于使用“大型”CRFs的实时应用程序来说，这类方法被认为计算量太大。除了随机技术外，还有大量的确定性方法。成功的技术包括移动生成算法[7]，信念传播[17]，它证明了条件模式[3]，树重信息通过[27]，二次伪布尔优化[41]和平均场[28]。这些技术中的每一种都在逼近的质量和速度方面有不同的权衡。

值得注意的是，当数据项较强且需要高速推理时(如VGA分辨率下的深度估计)，后验的全局优化往往被局部优化所代替[40,4,32]。由于我们学会了二进制表示，我们可以提供一个非常强大的数据项。这种低熵数据项使我们能够设计和使用一种新的并行全局推断方法，在gpu上不到一毫秒的时间内为130万像素的图像提供高质量的解决方案。

3. The HashMatch Framework

我们的框架是基于成对的crf，可以使用以下的概率因子分解来表示:

数据项$ψ_u (l_ i)$ψu​(li​)模型的可能性有多大图中的一个节点(通常是一个像素)属于我(如特定类l。
“前景”)。$ψ_u (l_ i)$ψu​(li​)的具体的实现依赖于手头的任务。例如，为了找到图像块之间的最近邻，标签$l _i$li​对应于定义图像方向上位移的向量(u,v)。然后

测量以二维像素点$i和i + l_i$i和i+li​为中心的两个图像patch x的兼容性。函数$h (x) =sign(xW)$h(x)=sign(xW)是一个二进制的特性,这使我们能够计算$ψ_u (l_ i)$ψu​(li​)高度有效地通过汉明距离(4)。其他的分类或回归问题我们定义$ψ_u$ψu​

其中g是一个学习分类器或回归器，它对给定图像patch xi的二进制码$h(x_i)$h(xi​)的标签li的可能性进行评估。平滑的成本被定义为$ψ_p (x_ i = l_ i, x_j = l_ j) = max(τ,| l_i−l_ j |)$ψp​(xi​=li​,xj​=lj​)=max(τ,∣li​−lj​∣),它鼓励邻近像素$i和j$i和j被分配到类似的标签,$τ$τ是截断阈值。

我们的主要贡献是一种计算h(x)和g(·)的新方法，它捕获了数据中的基本信息，并在本节的其余部分详细介绍。

3.1. HashCodes Learning

现在，我们详细介绍了我们提出的训练函数h的方法，该函数将信号$x∈R^ n$x∈Rn映射到二进制空间$b = h(x) =sign(xW)∈\{0,1\}^k$b=h(x)=sign(xW)∈{0,1}k。然后使用这个二进制表示b来学习一个函数$g(l,b)$g(l,b)，该函数执行任何给定的任务$y∈R^ d$y∈Rd。需要注意的是，y可以对应不同的任务，如多标签分类和结构化回归。特别是，可以定义y = x用于最近邻居搜索。为了使计算成本尽可能的低，我们考虑每一个$y _l$yl​的线性模型。例如

更形式化地，我们学习了一组超平面$W∈R ^{n×k}$W∈Rn×k，以及最小化损失L的任务函数$Z∈R ^{k×d}$Z∈Rk×d:

其中$X∈R ^{m×n}和Y∈R^{ m×d}$X∈Rm×n和Y∈Rm×d是矩阵，其第i行分别对应于$x_i和y_i$xi​和yi​。$Γ(W)和Ω(Z)$Γ(W)和Ω(Z)合适regularizers鼓励两个预测所需的结构。

模型$y = Z^⊤标志(W^⊤x)$y=Z⊤标志(W⊤x),可以被视为一种神经网络与隐层和运算符(·)作为非线性(与sigmoid or ReLu[34]不同)。特别是当Y = X时，模型变得类似于带有内部二进制表示的自动编码器
(如[8])。然而，由于符号(XW)是一个分段的常数函数(因此，关于W的次梯度几乎处处为零)，因此不能使用一阶方法(如反向传播)对Eq.(6)进行优化。我们通过将任务y与二进制映射h(x)解耦来绕过这个问题。为此，我们引入一个额外的变量$B =sign(XW)$B=sign(XW)，然后通过一个最小的不同度量$D(XW,B)$D(XW,B)来放宽等式约束。这就导致了问题。

在$| | B||_∞= max_{ij} | B_{ij} |$∣∣B∣∣∞​=maxij​∣Bij​∣表示$l_∞$l∞​(或max)规范B和标量hyperparameter $µ> 0$µ>0。B约束$| |B | |_∞≤µ$∣∣B∣∣∞​≤µ介绍鼓励所谓anti-sparse解决方案,这样得到B∗Eq(7)的所有条目$B_{∗ij} =±µ$B∗ij​=±µ。抗稀疏性的概念最初是在信号处理文献中提出的，在文献中观察到，施加基于矩阵-正态矩阵的约束会产生“二元”解。我们把读者引到[33,18,25,53,44]来深入讨论极大-范数正则化(和约束)的反稀疏性。引入双元项的变量B的想法与[8]中提出的类似。然而，在这类工作中，作者在优化中对B∈{−1,1}进行了约束，从而导致NP-hard问题。另一方面，最大范数约束球是一个凸集，在下面我们讨论一个有效的优化算法来寻找B在实践中。

有趣的是,当B与条目是一个二进制矩阵等于$±µ$±µ,学习问题的线性预测W这样$\frac{1}{µ} B∼sign(XW)$µ1​B∼sign(XW)对应于一个标准多标记(或多任务)二元分类问题,与B的每一列代表不同的二进制的任务。因此，将损失函数用于逻辑、铰链、最小二乘等分类问题，是实现不相似度模型D(XW,B)的自然选择。

3.2. Optimization

式（7）所描述的优化问题在W，Z，B中不是共同凸的，但对于凸损失函数L，D和正则化器Γ，Ω，目标函数在每个变量中是分别凸的。因此，解决这个问题的自然策略是执行交替最小化[47，39]或块坐标下降[5]。下面我们将详细说明如何通过独立优化W、B和Z来实现等式（7）的最小化。

OptimizingW. 我们建议使用规范$Γ(W) =λ|W| _1$Γ(W)=λ∣W∣1​为了诱导稀疏的解决方案。特别是,在我们的实验中选择λ,相应的解决方案$W_∗$W∗​最多$s < < n$s<<n零在每一列条目。实际上,这使得计算代码$h (x) =sign(W^⊤_∗x)$h(x)=sign(W∗⊤​x)在O (sk)操作,而不是O (nk)。当不同度量D是平滑的，可以使用标准的近端前后分裂方法来寻找固定的B和Z的最佳W。该算法由生成由

在$Prox_{{σ_1}λ}|·|_ 1$Proxσ1​λ​∣⋅∣1​表示$σ_1λ| · | _1$σ1​λ∣⋅∣1​的近端运营商(见[2])。l1范数的情况下,近端运营商是著名的对应entry-wise对振动[2]:对于每个标量w,软阈值,这样$Prox_{{σ_1}λ} (w)=0$Proxσ1​λ​(w)=0 如果$|w| \leq \sigma_1$∣w∣≤σ1​否则$Prox_{{σ_1}λ|·|}| (w) = w−sign(w)σ_1λ$Proxσ1​λ∣⋅∣​∣(w)=w−sign(w)σ1​λ。选择一个合适的步长σ1(通过线搜索或根据李普希茨常数D)的梯度,Eq。(8)是保证迭代收敛于解W∗与客观的价值功能下降的速度O (1 / t) [2]。在[57]之后，我们还使用了一个早期停止条件来确定所需的变量数量，这些变量的绝对值在W的每一列中都是最高的。

Optimizing B. 如果L是平滑的，则可以再次采用最近的前后分裂方法来最小化Eq. (7) w.r.t. . B(对于固定的W和Z)来获得更新

计算近端运算符,我们利用Moreau的分解,指出对于任何函数$\phi$ϕ,$Prox_φ(B) = B−Proxφ∗(B)$Proxφ​(B)=B−Proxφ∗(B),用$φ^∗$φ∗表示Fenchel共轭$\phi$ϕ(定义为$\phi^∗(B) =sup_{C∈R ^{m×k}} tr (B^⊤C)−\phi(C)$ϕ∗(B)=supC∈Rm×k​tr(B⊤C)−ϕ(C))。在我们的例子中,可以解释为指标函数φmax-norm球的半径µ(即函数为零当| B |∞≤µ,+∞否则)。它直接显示相应的Fenchel共轭是$\phi^∗(B) =µ| B | _1$ϕ∗(B)=µ∣B∣1​。结果是

与Proxµ|·| 1 entry-wise对振动运算符介绍w .我们再次获得优化的收敛速度的顺序(1 / t) [2]。

Optimizing Z 我们认为弗罗贝尼乌斯规范调整$Ω(Z) =η||Z|| ^2$Ω(Z)=η∣∣Z∣∣2,以避免过度拟合。这个问题可以通过标准的梯度下降更新来解决

哪一个是已知的收敛为合适的步长选择η。在这种情况下，O(1/t)的收敛速度也得到了保证。在损失L[6]的条件下，增加进一步的假设可以达到更快的速率。此外，如果我们考虑$L(BZ,Y) = ||BZ−Y||^ 2$L(BZ,Y)=∣∣BZ−Y∣∣2，我们可以以封闭形式计算出该问题的解$Z_∗= (B^⊤B +ηI)^{−1} B^⊤Y$Z∗​=(B⊤B+ηI)−1B⊤Y, with I the k×k identity matrix。
块坐标下降的收敛速度。 块坐标下降法包括迭代式(8,9,11)中的步骤，每次优化一个变量，同时保持其他两个变量不变。在一般情况下，证明迭代收敛到一个固定点(如局部极小点或鞍点)是具有挑战性的，更不用说证明收敛的速度有多快了。然而，在考虑损失函数和补偿器的选择时，本文提出的方法适用于最近研究其收敛性的一类近似交替线性化最小化(PALM)优化方法[5]。作为定理1和[5]中备注6的推论，我们得到了以下结论

L和D的选择。 在Eq中描述的松弛问题。(7),所述的优化方法适用于任何光滑凸函数的选择L和不同mea -确定D实验报告在这个工作我们采用了最小二乘损失函数$L(BZ,Y) = ||BZ− Y||^2和D(WX,B) = ||WX−B||^ 2$L(BZ,Y)=∣∣BZ−Y∣∣2和D(WX,B)=∣∣WX−B∣∣2,很容易恢复李普希茨常数推导出的梯度下降步大小σ1,σ2,σ3 。这种选择的动机还在于最小二乘是回归和重建问题的标准损失函数(因此是L的自然选择)，但也经常用于分类设置[55] (因此是不同D的可行选择)。在补充材料中，我们报告了在损失和差异的选择中描述的优化策略的伪代码。

3.3. Parallel Inference

推断P(Y |D)的后验概率，以及P(Y |D)的映射(极大后验概率)，通常是非常困难的，因为它需要对所有变量x∈x求一个非常复杂的积分序列。更准确地说，我们的目标是找到一个分布Q，它是P在分布类中的“近似”分布，可以分解为独立边缘的乘积。

这种近似值在计算上很有吸引力，但很可能丢失许多关于原始分布P(Y |D)的信息。然而，当P(Y |D)的熵较小时，MAP和MPM(最大后验边缘)推理的结果将非常相似。广义地说，在我们前面所描述的两两CRF中，当一元势为“尖峰”(即向低方向)时，可以得到P(Y |D)的良好近似值。Q(Y)和P(Y|D)之间近似的性质通常用KL(Q(Y)||P(Y|D))来测量，其中KL是Kullback-Leibler散度。取Kullback-Leibler发散的不动点解26]，我们得到随机变量xi的边缘中的标签Li的更新如下:

底层的坐标提升过程使每次迭代的P / Q值得到更好的近似值，但也保证了收敛性。注意，当对图执行推断时，像beliefpropagation这样的流行技术并不能保证收敛。在这个阶段，重要的是要注意更新的$Q ^t (Y)$Qt(Y)的复杂度是$O(|Y ||L|(|N||L| + 1))$O(∣Y∣∣L∣(∣N∣∣L∣+1))。当L很小时，L上的二次复杂度不是高速推理的实际问题。然而，这使得(计算上有吸引力的)平均场框架在这个数增长到la时太慢了。我们在近似中进一步前进，并且明确地假设Q也具有低熵并且近似它具有狄拉克δ函数。这对应于设置$Q i =\sigma(l_i−argmax l_ j Q_j)$Qi=σ(li​−argmaxlj​Qj​)。我们现在可以将(15)改写如下：

3.4. Computational Analysis

下面是对提出的(离散)视差估计方法的计算分析。我们用|Y |像素和L可能的标签来包容一个输入图像。视差估计的典型值为|Y | = 1280×1024和L = 512。超平面W被训练为每个代码最多有4个非零元素。每个像素i与大小为|P i | = 11×11的patch P i相关联。取pi和W之间的点积的符号将pi映射成k = 32的二进制码。二进制代码b的计算与窗口大小|P|无关，每个超平面涉及4次乘法和。这对应于计算哈希码的每像素复杂度O(4k)。我们初始化数据项ψ我只通过评估非常有限的一组32假设随机标签。这些距离是使用新空间中的汉明距离计算的，这可以在O(1)中有效地实现，利用大多数最新的GPU架构中实现的popc()函数。初始化步骤的复杂度为每像素O(4k)。对于这种情况，我们只使用相邻的N = 3×3个像素在成对势中。每个像素的边缘可以并行更新，而不需要像[4,16]那样等待连续的传播步骤。在实践中，我们使用了所提议的推断的4个步骤，导致每像素复杂度为O(4 |N|(1 + |N|))。注意，与其他方法相比，该算法不依赖于标签数量L和patch大小|P i |。该方法计算复杂度相对较低，且所有组件完全并行，特别适用于低计算设备上的高速应用。我们测试了HashMatch框架的NVIDIA GPU泰坦X,整体运行时间890µs每帧。我们还在NVIDIA Tegra TX1上实现了该算法，总体运行时间为5ms，这为在移动平台上实现高速应用提供了可能性。

4. Results

我们在一组不同的计算机视觉任务上评估HashMatch框架。对于每个问题，我们都明确地描述了所使用的一元势的形式。我们首先展示了我们的方法如何处理连续标记问题，如视差估计。进一步，我们评估了所提出的检索和特征邻近任务的哈希方案。最后，我们评估了背景相减所提出的推论的品质。注意，对于使用建议的推理的任务，迭代次数是常数，并设置为4。

4.1. Depth Estimation

在本节中，我们重点研究了在主动光照下的立体图像深度估计[15,16]。在我们的实验中，我们使用了一个类似于[16]的硬件设置，即两个立体配置的红外摄像机和一个Kinect V1 DOE。当IL和IR红外图像校准和纠正,每个像素 p = (u, v)有一个对应的像素q = (u + L, v) IR位于同一扫描线诉我们应用HashMatch检索连续差距L∈R。然后通过$Z = \frac{bf}{ l}$Z=lbf​在深度域中重新映射视差，其中b为系统基线，f为摄像机焦距，l为推断视差。

在本节中,将数据项ψu (l i)计算,根据(4)式。我们训练超平面W通过收购10000图像和提取11×11图像补丁x, y = x我们设置了任务。我们使用k = 32超平面与最大4 W为每一列非零元素。

我们将HashMatch与最先进的方法进行比较，包括定性和定量评估。我们将相机的曝光时间设置得很低(2ms)，以便在500Hz时对捕捉到的真实数据进行评估。与30Hz采集的数据相比，该数据的信噪比(SNR)要低得多。在图1中，我们展示了HashMatch、Patch- Match立体声$[4]$[4] 和UltraStereo (US)$[16]$[16]生成的定性结果。注意，基线方法的信噪比相对较低，而HashMatch能够预测完整而平滑的深度图。我们还使用一元项和PatchMatch推理$[1]$[1](图1中的HashMatch+PM)生成结果。所提出的并行推理生成的结果与PatchMatch推理生成的结果非常接近，但是与[16]中描述的非常优化的实现相比，速度要快2倍。在图2中，我们展示了用HashMatch生成的高质量的深度图和点云，其中不显示我们的方法捕获的细节级别。


为了定量评估所提出的框架，我们采用了[15]中的方法并获取了多种已知距离下的黄曲霉图像，其变化范围在500到3500厘米之间。我们估计平均深度偏差(定义为平均误差)和深度抖动(定义为标准差)。 我们与Kinect V1, RealSense R200，PatchMatch立体声[4]，超深度[15]和UltraStereo[16]作为基线方法;结果如图3所示。HashMatch的性能优于大多数竞争对手，与[15]等更复杂的方法不相上下。

最后，我们比较了我们的哈希方案的质量与其他先进方法，如:ITQ [19]， SBE [37]， CBE[56]，二进制自动编码器(BA)[8]和超立体声[16]。我们使用了来自[16]的具有完美地面真值差异的合成数据集，并在像素差异上执行(离散的)最近邻搜索。

我们定义精度为估计视差小于1像素的像素百分比;结果见表1。尽管我们的HashMatch描述符在每个超平面上只使用4个非零元素，但是结果与密集的哈希模式(如BA)相当。我们也优于其他稀疏哈希方案，如CBE和SBE，证明了所提出的表示法的质量。值得注意的是，除了提供平滑的结果之外，使用所提议的推断将表1中报告的精度从77%提高到96%。

4.2. Nearest Neighbor Retrieval

在本节中，我们将在最近邻居检索任务上评估HashMatch。假设我们有两组有限元向量，查询和基。对于查询集中的每个样本，目标是找到基集中最近的邻居。这是两个或多个图像之间对应搜索问题的一个典型例子。本节的目标是只评估我们的散列方案，并将其与其他最新方法进行比较，因此不需要并行推理。根据式（4）计算数据项Ψu（l i）。注意，对于这个实验，不需要平滑项，因此我们放弃了它。我们使用GIST1M数据集[24]，它由三个不相交的集合组成:train、query和base。每个描述符x有960个维度，我们最小化Eq.(6)设置任务Y = x。我们使用训练集对数据相关的哈希方案进行训练，并对其他集进行测试。我们计算[email protected]，定义为R检索的收回。

我们将我们的方法与以下最先进的哈希技术进行比较:ITQ[19]、SBE[37]、CBE[56]、LSH[23]和SKLSH[36]。对于每一种方法，我们训练了16、32、64,128个编码，根据式(1)进行二进制嵌入编码，并利用汉明距离计算最近邻搜索。我们不执行任何数据预处理，如标准化步骤或扩充。对于HashMatch和SBE，我们将稀疏性参数设置为有10%的非零元素。

我们在图4中报告了召回率@R曲线。对于数量很少的代码，Hashmatch的性能大大优于所有的竞争对手，包括ITQ等密集的竞争对手。当使用较大的代码（即128）时，这个间隙减小，但hashmatch仍然提供最大的曲线下面积（AUC）

4.3. Feature Approximation

在这个实验中，我们考虑了给定一组11×11的图像patch x的复杂特征描述符的近似匹配问题。对于这个特殊的应用，我们考虑了SIFT描述符[31]s∈R 128。目标是最小化Eq.(6)，其中任务Y = S是SIFT描述符的集合。换句话说，我们将HashMatch应用于回归问题，其中目标连续函数是从手工特性计算出来的。一般来说，我们可以应用相同的框架来学习更复杂的描述符。

我们考虑了EPFL宽基线立体声数据[46]，我们在这些序列上训练HashMatch，但没有groundtruth可用。训练数据是用无监督的方法由筛选描述符生成的。在测试时，我们分别检测拐角和计算SIFT和HashMatch描述符。我们根据最接近的l2距离来匹配描述符，并通过在两个图像之间施加外极约束来过滤离群点。在图5中，我们报告了定性结果:绿色表示正确的匹配，红色表示距离大于1厘米的匹配。SIFT的平均端点误差为0.8 cm，而HashMatch非常接近，为1.2 cm。如果我们将错误< 1cm的检索匹配的百分比作为inliers, HashMatch报告的总体准确率为90%，而SIFT检索81%的更正匹配。平均来说，SIFT能够为每个图像检索350个好的匹配，HashMatch 150。虽然在HashMatch中匹配的数量更少，但我们获得了更可靠的匹配。在实践中，我们从HashMatch中获得的特性匹配的顺序将满足大多数使用SIFT的应用程序的需要，而且计算量更少，使得HashMatch在这种场景中非常强大。

4.4. Background Subtraction

在最后一个实验中，我们评估了一个静态相机背景分割任务的并行推理。典型的应用是监视和人员跟踪场景。我们认为是自然的(室内)房间。假设一个干净的背景镜头是可用的(RGB和深度)，我们想要检测任何进入场景的新对象。

此应用程序的目标是评估所提出的推理，并将其与已建立的方法（如信念传播（BP）[45]、树重加权消息传递（TRW）[50，27]、平均场[49]和补丁匹配[1]）进行比较。假设RGB和深度信息是可用的，我们使用形式为Ψu（l i）=ΨRGB（l i）+Ψ深度（l i）的一元势。这两个术语是HSV空间中的简单差异和深度域中的logistic函数，如[35]和[14]所定义。注意，一元势在所有基线方法*享，成对项是标准Potts模型。

我们从不同的对象和对象中收集了100帧图像，并从这些图像中手动标记前景以获得地面真实情况。我们在表4.4中报告了通过建议的推断和基线得到的平均能量。值得注意的是，尽管计算上的要求要低得多，所提出的推论所获得的最终能量与基线所获得的能量非常相似。定性结果如图6所示。

5. Conclusion

在这篇文章中，我们提出了HashMatch，一个为并行计算架构量身定做的高效框架。通过在一组不同的计算机视觉任务上的大量实验，我们证明了尽管HashMatch以极快的速度运行，但与更密集的计算方法相比，它在预见方面几乎没有任何折衷。所有这些特性使HashMatch成为一个吸引人的框架——适用于低计算移动平台和需要高速运行的产品。