高维视觉特征的Fried二进制嵌入算法

1高维视觉特征的Fried二进制嵌入魏祥洪俊松袁Sreyasee Das Bhattacharjee电气与电子工程学院，新加坡南洋理工大学{wxhong，JSYUAN}@ ntu.edu.sg，sreya. gmail.com摘要现有的二进制嵌入方法大多倾向于采用压缩的二进制码（b维），以避免投影高维数据的高计算和内存开销视觉特征（d维，b d）。我们认为，长二进制码（b=O（d））是至关重要的，以充分利用高维视觉特征的鉴别能力，并可以在各种任务，如近似最近邻搜索取得更好的结果。生成长二进制码涉及大的投影矩阵和高维矩阵向量乘法，因此是存储器和计算密集的。为了解决这些问题，我们提出了Fried二进制嵌入算法（FBE），它利用自适应Fastfood变换分解投影矩阵，这是几个结构矩阵的乘积。结果表明，FBE可以降低计算复杂度，时间复杂度为O（d2）到O（dlogd），内存开销为O（d2）到O（d）。更重要的是，通过使用结构化的方法，FBE可以调节投影矩阵，防止过度拟合，并且在相同的 长 码 长 度 下 ， 比 使 用 未 约 束 的 投 影 矩 阵 （ 如ITQ[4]）实验比较国家的最先进的方法在各种视觉应用程序证明了效率和性能的优势FBE。1. 介绍最近，视觉社区已经投入了大量的注意力到二进制嵌入[22，4，3，25，28，21]由于视觉数据的爆炸性增长，这使得有效的搜索和存储成为迫切的要求。二进制嵌入的目的是将高维特征向量编码为紧凑的二进制码，同时保持原始高维特征的成对相似性。通过将高维特征编码成二进制码，可以利用汉明距离计算进行有效的搜索;同时，存储成本也显著降低。由于直接学习是NP困难的，最优二进制码[22]，大多数现有的二进制嵌入方法基于两阶段策略工作：投影和量化。 具体地说，给定一个特征向量x∈Rd，这些方法首先将x乘以投影矩阵R∈Rb×d产生一个b维的低维向量，然后通过将这个低维向量赋给汉明空间中与它最近的顶点，将它转换为b虽然紧凑的二进制码是首选，以节省存储，最近的工作表明，长位码可以带来优于紧凑的性能，特别是当视觉特征是成千上万的dimens。例如，4096维的长二 进 制 码 在 DNN-4096 数 据 集 上 可 以 达 到 82% 的mAP[23]，而256维二进制码的mAP仅为51%。然而，生成长二进制码需要大的投影矩阵，这导致两个挑战：（1）高维矩阵-向量乘法的高计算成本，以及（2）过拟合的风险。对于第一个挑战，已经注意到，对于输入特征向量，对于维数d，达到合理精度所需的二进制码的长度b通常是O（d）[17，3，25]。当d很大且b≠ O（d）时，投影矩阵R ∈Rb×d可能涉及数百万甚至数十亿个参数。如此高的成本是不赞成当我们编码一个大的视觉特征的数据集，或者当计算资源是关注点时，例如，在移动平台上。对于第二个挑战，已经努力通过调节投影矩阵和减少自由参数的程度来解决它。有趣的是，这种正则化也可以带来快速的矩阵向量乘法，这也将有利于计算效率。代表性的工作包括循环二进制嵌入（CBE）[25]、双线性投影（BP）[3]、快速正交投影（KBE）[28]和稀疏投影（SP）[23]等。更具体地说，CBE[25]利用循环矩阵来加速矩阵向量乘法，BP[3]将投影矩阵约束为两个较小矩阵的Kronecker积，而SP[23]则寻求稀疏投影矩阵。Al-27492750F虽然CBE[25]和BP[3]显示出有希望的编码效率，但它们在使用相同码长的情况下实现的精度不如密集投影方法（如ITQ[4]）而SP[23]在性能方面与稠密投影方法相比具有竞争力。不幸的是，它仍然其计算代价为O（d2）为了解决上述两个挑战，我们提出了一种新的Fried Binary Embedding（FBE）是一种有效生成长二进制码的方法。其思想是使用自适应快餐变换[12，24]分解投影矩阵R，该变换是几个结构矩阵的乘法。结构化矩阵通常由依赖项组成，这意味着一个固定的“自由芽”分布在矩阵中。利用快速傅立叶变换或其变种，结构矩阵的卷积导致快速此外，最终投影矩阵R由于其每个分量的固有结构而具有受限的自由度例如，当将4096维特征向量编码为4096位二进制代码时，我们的FBE只有12，288个可调参数，仅为稀疏投影的1%[23]和0。ITQ的1%[4]。约束自由度自然是反对过拟合的，因此可能会导致良好的泛化性能.FBE的另一个好处是结构化矩阵可以有效地时间复杂度为O（n），时间复杂度为O（n必须明确存储。因此，存储R也显著减少。结构化矩阵的参与使得操作-最优化问题很难，因此我们采用变量分裂和惩罚技术[23，2，20]来开发一种替代优化算法。通过引入一个辅助变量将原优化问题分解为若干个可行子问题，然后迭代求解这些子问题直至收敛。在第4.4节中，我们进一步证明了我们的算法可证明地收敛于局部最优。我们称我们的方法为油炸二进制嵌入（FBE），遵循Deep Fried Convnets [24]和循环二进制嵌入[25]。大量的实验表明，我们的方法不仅在紧凑位的情况下实现了有竞争力的性能，但也优于国家的最先进的方法在长位的情况下。迭代量化（ITQ）[4]的目的是找到哈希码，通过将每个比特视为相应维度的量化值，使哈希码和数据项它包括两个步骤：（1）主成分分析降维;（2）找到散列码以及最佳旋转。双线性投影（BP）[3]通过两个较小的矩阵而不是单个大矩阵来投影数据向量，基于数据向量通过重塑矩阵来制定的假设。BP的这种假设对于许多传统的手工特征都是有效的，如SIFT [13]，GIST [15]，VLAD [8]和Fisher Vectors [16]，但对于学习的特征，如深度神经网络（DNN）[11，18]。循环二进制嵌入（CBE）[25]在投影矩阵上强加了一个循环结构，以实现高效的矩阵向量乘法。由于采用 了 快 速 傅 里 叶 变 换 ， CBE 的 计 算 量 仅 为 O（dlogd），比稠密投影方法的O（d2）小得多。它值得注意的是，CBE与我们的AP有相似的想法然而，BP和CBE在使用相同码长的情况下，其精度都不如密集投影方法（如ITQ[4]）快速正交投影（KBE）[28]将投影矩阵分解为一系列较小的正交矩阵。与CBE [25]类似，存在一种计算Kronecker 投 影 的 快 速 算 法 ， 其 时 间 复 杂 度 为 O（dlogd），因此，与密集投影方法（如ITQ [4]）相比，KBE在效率方面表现出很大的优势。稀疏投影（SP）[23]引入了稀疏正则化器以实现编码效率。同时也表明稠密投影矩阵中存在着许多冗余参数然而，根据[23]中的图4，他们的方法要求非零元素的百分比在10%左右，以获得竞争性性能，如果d和b都非常大，这仍然会受到影响。3.问题公式化在[19，23]之后，我们将ITQ[4]的降维和最优旋转放入一个集成目标中：2. 相关工作minR、CRX −CX2（一）关于二进制嵌入的一个很好的综述可以在[19]中找到。在这里，我们专注于几个密切相关的工作，包括迭代量化（ITQ）[4]及其四个变体。迭代量化对于理解我们的工作至关重要。ITQ的三种变体是双线性投影（BP）[3]，循环二进制嵌入（CBE）[25]，稀疏投影（SP）[23]和快速正交投影（KBE）[28]，它们是高维二进制嵌入的最新作品。S.T. RT R = I.其中X∈Rd×n是数据集，C是一个b×n矩阵，只包含1和−1。矩阵R∈Rb×d既可降维又可旋转。ITQ[4]通过交替更新求解方程1。在找到R之后，ITQ可以使用下面的哈希函数生成二进制代码：c =sgn（Rx），（2）2751FF其中x∈Rd表示数据向量r，sgn（·）是符号函数，对于正数输出1，否则输出−1。为了简单起见，我们首先做两个假设：（1）R∈Rd× d;（2）存在整数l使得d=2l.我们将继续讨论对一般稠密投影矩阵的O（d2）代价进行了理论改进总之，我们可以通过将等式1和等式3放在一起来实现我们的优化目标更广泛的案例。minS、G、B、 CRX −CX2虽然ITQ[4]已经显示了二进制嵌入的情况下，方程2中矩阵-向量乘法的计算量为O（d2），这限制了它在高维二值嵌入中的应用为了降低计算Rx的成本，我们使用自适应Fastfood变换[24]分解投影矩阵R，即，S.T.RT R = I，R = SHG<$HB，S，G，B ∈ D。4. 优化（五）R= SHG HB。（三）因此，我们的哈希函数变成了c= sgn（SHG → HBx）。（四）为了解释这种分解的原因，我们需要描述自适应Fastfood变换的组件模块自适应Fastfood变换有三种类型的模块：由于涉及结构化矩阵，与等式1相比，等式5是更具有挑战性的问题。 更新S、G、B的任何条目都可能导致R上的正交约束的违反。为了找到一个可行的解决方案，我们采用了变量分裂和惩罚技术，最优化中的niques [23，2，20]。具体来说，我们将正交约束移动到辅助变量R<$X上，同时惩罚R<$X和RX之间的差异。因此，我们将等式5中的问题放宽为以下等式形式：• S、G和B是可调参数的对角矩阵min<$R<$X−C<$2+β<$R<$X−RX<$2特斯作为比较，原始非自适应快餐配方[12]中的S，G和B是随机的，S，G，B，C，RS.T.FR<$TR<$=I，F（六）其条目只计算一次，并保持不变了因为它们是对角矩阵，所以计算和存储成本仅为O（d）。在这项工作中，我们定义D是所有对角矩阵的集合。对于任意方阵S∈Rd×d，我们用它的小写字母s∈Rd表示由S的对角元素组成的向量，即s=diag（S）。• n ∈ {0，1}d× d是一个随机置换矩阵，由随机数排序生成.它可以实现为查找表，因此存储和计算成本也是O（d）。R=SHG<$HB，S，G，B∈ D，其中β是惩罚权重。这种松弛类似于半二次分裂[20]。通过引入一个辅助变量，原问题可以分解为可行的子问题，并且当β → ∞ [20]时，方程6的解将收敛到方程5的解。我们以交替的方式求解方程6：用固定的变量更新一个变量。4.1. 更新C这个子问题等于minC<$R<$X−C<$2=F• H表示Walsh-Hadamard矩阵，其为MaxCi，j（RX）ijCij，其中i，j是矩阵的索引递归地进行罚款，Σ Σ元素 因为Cij∈ {-1，1}，这个问题可以是这个问题很容易通过Cij=sgn（（R<$X）ij）求解，或者简单地H2：=1 11−1H2d：=Hd HdHd−HdC=sgn（R<$X）。（七）快速Hadamard变换是快速傅立叶变换的一个变体，它使我们能够在O（dlogd）时间内计算Hdx。注意，H不需要被扩展存储。4.2. 更新R'当R固定时，方程6中的两项都是R ′的二次项。通过某些推导，问题等式6变为：因此，使用自适应Fastfood变换来计算Rx的计算成本为O（ dlogd ），而2752存储R的存储成本仅为O（d）。这些都是实质性的minR¯S.T.<$R<$X-Y<$2R<$TR<$=I，（八）2753FIJFFFF其中Y=（C+βRX）/（1+β）。这个问题被称为正交procrustes问题[5]，最近S、G或B，则所有这三个子问题可以基于等式10和11统一为以下形式：广泛研究二进制嵌入[4，3，23]。根据[5]，procrustes问题是可解的minWtrace（ET WDTDWE）−2 trace（KW）（十三）只有当b≥d。对于固定的Y，等式8被最小化如下：首先找到矩阵YXT的SVD为YXT=U <$VT，则令R<$=U VT。（九）在b d）。MIRFLICKR-1 M数据集[6]。AlexNet包含五个卷积层和两个全连接（fc）层，后面是一个softmax分类器。使用该网络，我们提取4096维输出的第二fc层作为图像特征。每个图像的大小都被调整为保持相同的长宽比，但较小的边为256，中心224×224区域用于计算特征。 我们把这个数据集DNN-4096额外的1，000个随机样本用作查询。请注意，每个4096维原始特征（实数）需要16，384字节（131，072位）的存储。遵循[23]中的协议，我们使用平均精度（mAP）来衡量搜索质量，即，准确率-召回率曲线下的给定一个查询，我们执行汉明排序，即，数据集中的样本基于它们的二进制代码，根据它们到查询的汉明距离进行排序。使用原始特征的数据集中每个查询的50个最近邻被定义为真阳性样本，这是我们评估mAP的基础事实在图3a中，我们展示了mAP如何随着不同的代码长度b而变化。所提出的FBE在短比特场景下实现了具有竞争力的mAP，并且在长比特场景下显著优于其他现有技术的方法，即，位长度与特征尺寸相当或长于特征尺寸。FBEITQFBEITQFBE快餐SPBPCBEITQKBE地图FBESPBPCBEITQKBE量化损失地图编码时间/ms27580.80.70.60.50.40.30.20.110.90.80.70.60.50.4表1：将DNN-4096特征编码为不同长度的二进制代码注意032641282565121024204840968192比特(a) GIST-9600.31024 2048 4096 8192比特(b) VLAD-2560016384BP不适用于生成比原始特征向量长的二进制代码。例如，与SP [23]，KBE [28]，BP [3]，CBE [25]和ITQ[4]相比，FBE在嵌入4096维CNN特征方面表现最好。有趣的是，尽管我们提出的方法的性能在1024位以下并不比快餐变换[12]好，但在1024位以上时，它显著优于快餐变换[12]这验证了我们将S，G和B优化为等式5，与使用S，G和B的随机矩阵（如Fastfood变换[12]）相比，确实提高了性能。如图3b所示，计算二进制代码的编码时间不会线性增加到b。与SP和KBE相比，FBE的编码时间更短，但不如BP和CBE。虽然CBE和BP可以实现优于FBE的加速比，但它们的性能相对较低，并且BP不适用于产生较长的代码（b > d）。我们比较了我们提出算法和表1中的基线。除了较少编码时间的优点之外，所提出的FBE需要少得多的参数来构建投影矩阵R，这不仅降低了存储器的成本，而且降低了过拟合的风险。例如，当将4096维特征向量编码为4096位二进制代码时，我们的FBE只有12，288个可调参数，仅为稀疏投影的1%[23]和0。ITQ的1%[4]。尽管BP [3]、CBE[25]和KBE [28]在产生相同长度的二进制码时需要比我们的参数更少的参数，但这些方法在性能方面不如所提出的FBE，如图3a和图4所示。5.1.2传统特征为了验证我们提出的FBE的通用性，除了使用深度学习功能之外，我们还在两个传统功能的数据集上评估了我们的方法。第一个数据集是GIST-960[7]，其中包含100万个960维GIST特征[15]和10，000个查询。第二个数据集是VLAD-25600 [23]。 VLAD特征[8]是从INRIA随机抽样的100，000张图像中提取的图4：与传统特征的比较。(a)GIST-960数据集上mAP相对于比特的变化（b）相对于VLAD-25600数据集上的位的mAP的变化。图像集[7]。25600维VLAD特征是通过将128维SIFT向量[13]编码到200个中心码本来生成的。1000个样本的额外随机子集用作此数据集中的查询。图4显示了这些数据集上的近似最近邻搜索结果，使用与图3a相同的协议。对于每个查询，我们检索的前50个最近的邻居的基础上的汉明距离的二进制代码，并将其与地面真理在原始特征空间。FBE在长比特情况下仍优于现有的方法，同时编码高维视觉特征的速度比ITQ，SP和KBE更快。对GIST和VLAD特征的实验表明，该方法同样适用于传统特征，再次证明了自适应Fastfood变换对高维视觉特征的潜力.5.2. 图像检索我们在“Holidays + MIRFlickr-1 M”数据集上评估了图像检索任务的二进制嵌入性能[7]。该数据集包含500个不同场景中的1，419张图像，另外还有100万张MIRFlickr-1 M图像作为干扰项。另外500个查询图像连同它们在相同场景类别下的地面实况邻居一起提供鉴于最近的图像检索和利用DNN特征作为图像描述符的对象搜索工作中报告的良好性能[1，27，26，14]，我们通过AlexNet的第二fc层的4096维响应来表示每个图像[11]。根据以前的实践[8，3，22，23]，我们将图像检索视为编码特征的ANN搜索问题，而地面真实邻居由场景标签定义给定一个查询图像，我们执行汉明排名和评估的mAP使用的语义地面真相。表2显示了Holidays+1M数据集的结果。作为使用原始特征的基线，4096维深度学习特征的mAP为49。百分之五为了保持这样的性能，我们将我们的方法与BP[3] ， CBE[25] ， SP[23] ， KBE[28] 和 原 始 的Fastfood trans.com进行比较。FBE快餐SPBPCBEITQKBEFBE快餐SPBPCBEITQKBE地图地图比特2048409681921638432768ITQ[4]8. 3 ×1061 .一、6×1073 .第三章。2×107六、4×1071 .一、2×108SP[23]8. 3 ×1051 .一、6×1063 .第三章。2×106六、4×1061 .一、2×107英国石油公司[3]61448192---2759地图编码时间（毫秒）原始深度特征（4096-d）百分之四十九点五-1024位英国石油公司[3]百分之四十四点五0.41CBE[25]百分之四十四点三0.85SP[23]百分之四十四点九0.47KBE[28]45.0%0.92快餐[12]百分之四十四点七1.12FBE（我们的）45.6%4096位英国石油公司[3]46.4%1.03CBE[25]46.6%0.85SP[23]47.1%1.33KBE[28]百分之四十七点二1.36快餐[12]百分之四十六点二1.12FBE（我们的）百分之四十七点二8192比特CBE[25]百分之四十七点八1.52SP[23]48.5%3.12KBE[28]百分之四十八点八2.18快餐[12]47.6%1.88FBE（我们的）49.3%表2：Holidays+1M上的图像检索性能。格式[12]使用1024，4096和8192位。我们的方法可以导致最好的mAP在所有的位长度。在8192位的情况下，我们的方法几乎没有退化（49。3%mAP）与使用原始深度学习功能相比。然而，我们没有观察到更好的性能时，使用- ING16384位。5.3. 图像分类我们进一步评估了二进制代码作为CIFAR-10数据集[10]上图像分类的紧凑特征，使用top-1准确度作为度量。作为基线，我们提取AlexNet[11]中第二个fc层的4096维响应作为图像特征。我们首先在CIFAR-10的训练集上微调Caffe[9]提供的预训练模型，然后使用微调后的模型为训练图像和测试图像生成特征。然后，我们学习CIFAR- 10[10]训练集特征的哈希参数在[23]之后，我们使用one-vs-rest线性SVM作为分类器。 我们观察到，一对休息线性SVM达到82。6%的分类准确率，高于softmax层（78. 9%）。我们比较了我们的方法与BP[3]， CBE[25]， SP[23]， KBE[28]和原始快速-食物变换[12]使用1024、4096、8192和16384位。当进一步增加比特长度时，我们没有看到性能的显著改善。表3列出了比较结果。在相同比特数的情况下，FBE的性能优于BP、CBE、SP和KBE。值得注意的是，即使比特数大于输入维度4096，这些表示仍然比原始特征更紧凑例如，16，384位仅需要实数的原始4096维特征的1/8存储成本。分类精度编码时间（毫秒）原始深部特征（4096-d）百分之八十二点六-1024位英国石油公司[3]76.6%0.41CBE[25]百分之七十六点三0.85SP[23]77.8%0.47KBE[28]百分之七十八点三0.92快餐[12]77.4%1.12FBE（我们的）79.7%4096位英国石油公司[3]百分之七十七点五1.03CBE[25]77.4%0.85SP[23]78.6%1.33KBE[28]79.3%1.36快餐[12]百分之七十八点三1.12FBE（我们的）百分之八十点七8192比特CBE[25]百分之七十八点一1.52SP[23]百分之七十九点五3.12KBE[28]百分之八十点五2.182760表3：CIFAR-10数据集的分类准确性5.4. 讨论在上面的实验中（图3a，4和表2，3），我们观察到实现优雅降级所需的二进制代码长度b（与没有编码相比）通常在b≠ O（d）左右，这证明了对高维数据使用长二进制代码的合理性。短双-二元码具有相当大的准确性降低，并且可能影响真实世界使用的质量，因此在实践中，期望具有对高维二进制嵌入的可行且准确的解决方案。6. 结论提出了一种新的高维二进制嵌入方法-Fried二进制嵌入法。通过使用自适应分解稠密投影矩阵，通过Fastfood变换，我们提出的FBE将原来O（d2）的计算和内存开销分别降低到O（dlogd）和O（d）此外，由于其每个组成部分的固有结构，最终投影矩阵将有限制的自由，这是自然反对过拟合，并在我们的实验中表现出更好的泛化性能。通过引入一个辅助变量，将结构矩阵优化问题分解为多个可行子问题，然后迭代求解这些子问题直至收敛。我们比较FBE与几个国家的最先进的方法在三个任务，包括近似最近邻（ANN）搜索，图像检索，图像分类。实验结果验证了我们的FBE的效率和准确性的优势。2761确认这项工作得到了新加坡教育部学术研究基金Tier 2MOE 2015-T2- 2-114的部分支持，并在新加坡南洋理工大学的快速丰富对象搜索（ROSE）实验室ROSE实验室是由新加坡国家研究基金会支持的互动数字媒体（IDM）战略研究计划。我们非常感谢NVIDIA AI技术中心（NVAITC）捐赠的Tesla K80和M60 GPU，用于我们在ROSE实验室的研究。作者感谢谭玉的宝贵讨论。引用[1] S. D. Bhattacharjee，J. Yuan，W. Hong和X.阮。使用对象草图查询自适应实例搜索。在2016年ACM多媒体会议上，第1306-1315页。ACM，2016。[2] R.柯朗解平衡和振动问题的变分方法。Bulletin of theAmerican Mathematical Society，49（1）：1[3] Y. 贡，S.库马尔，H.A. Rowley和S.Lazebnik 使用双线性投影学习高维数据的二进制代码IEEE计算机视觉和模式识别会议论文集，第484-491页，2013年[4] Y. Gong和S. Lazebnik迭代量化：一种学习二进制代码的 亲 克 鲁 斯 特 方 法 。 在 Computer Vision and PatternRecognition（CVPR），2011 IEEE Conference on，第817-824页中。IEEE，2011年。[5] J. C. Gower和G. B.迪克斯特豪斯Procrustes的问题。30号牛津大学出版社，2004年。[6] M. J. Huiskes和M. S.卢米尔Flickr检索评估。第一届ACM多媒体信息检索国际会议论文集，第39-43页。ACM，2008年。[7] H.杰古湾Douze和C.施密特最近邻搜索的乘积量化。IEEEtransactionsonpatternanalysisandmachineintelligence，33（1）：117[8] H. 我也是M. 杜兹角Schmid，和P. 佩雷斯。将局部描述符聚集到一个紧凑的图像表示中。在计算机视觉和模式识别（CVPR），2010年IEEE会议上，第3304-3311页。IEEE，2010。[9] Y. Jia、E.Shelhamer，J.多纳休S.Karayev，J.隆河，西-地Gir- shick，S. Guadarrama和T.达雷尔。Caffe：用于快速特征嵌入的卷积架构。第22届ACM国际多时间数据，第675-678页。ACM，2014年。[10] A.克里热夫斯基从微小的图像中学习多层特征。2009年[11] A.克里热夫斯基岛Sutskever和G. E.辛顿Imagenet分类与深度卷积神经网络。神经信息处理系统的进展，2012年。[12] Q. Le，T. Sar lo's和A. 斯莫拉对数线性时间中的Fastfood近似核展开2013年国际机器学习会议论文[13] D. G.洛从尺度不变关键点中提取独特的图像特征。国际计算机视觉杂志，60（2）：91[14] J. Meng，H. Wang，J. Yuan和Y.- P. Tan。从关键帧到关键对象：通过代表性对象建议选择进行视频摘要在IEEE计算机视觉和模式识别会议论文集，第1039- 1048页[15] A. Oliva和A.托拉尔巴建模场景的形状国际计算机视觉杂志，42（3）：145[16] F. Perronnin和C.跳舞吧基于视觉词汇的Fisher核图像分类。《计算机视觉与模式识别》，2007。07年CVPR。IEEE会议，第1-8页。IEEE，2007年。[17] J. 桑切斯和F。佩罗宁用于大规模图像分类的高维特征在计算机视觉和模式识别（