监督二进制编码的图像切割外文翻译资料

英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

监督二进制编码的图像切割

葛铁征、何恺明、孙剑

中国科技大学 微软研究院

摘要

由于图割问题的固有离散性，学习短二进制码面临巨大挑战。图形切割算法是计算机视觉研究离散标签分配的解决方案，但还没有被应用于解决二进制编码问题。这部分是因为目前还不清楚如何使用它来学习编码（哈希）函数的样本泛化。在本文中，我们制定监督二进制编码作为一个单一的优化问题，涉及两个编码函数和二进制标签分配。然后，我们应用图形切割算法处理有关离散优化问题，没有连续的松弛。这种方法称为图形切割编码（GCC），在不同的数据集上显示出结果。

1简介

在计算机视觉方面学习二进制编码^【32】已经吸引了越来越多的关注。在应用方面，二进制编码使得有可能存储和搜索大规模数据^【32】; 在理论方面，对二进制编码的研究一直在推进非平凡离散值问题的研究，例如[14，36，18，19，25，35，10，11，21，28，13 ]。二进制编码方案（例如[10]）也可有利于在非二进制编码问题的研究（例如[8,9，24]）。

最近的研究[ 36，18，35，10，25，23，28，21，13 ]大多是制定二进制编码作为优化问题的几个问题。编码之间的汉明距离^【14】应该保存数据中的相似性，而编码的比特应该是更好的提供数据压缩的信息。此外，编码函数（也被称为哈希函数）期望是简单的，例如，线性函数或简单的内核映射^【19,21】。如果可以，监督/半监督信息^{[18，35，25，21，28]}也应该值得重视。这些问题的配方导致非平凡的优化问题。优化中的一个主要挑战来源二值化的编码函数。各种优化技术已被采用，包括频谱松弛^【35,36]，一致量化^【10】，凹凸优化^[25]，sigmoid函数近似^[21]，和随机梯度下降^[28]。尽管策略不同,这些方法主要集中在优化编码函数f的连续参数w.r.t.。然而，问题的离散性往往被忽视。

然而，计算机视觉方面广泛涉及离散标签指派问题^[5,4]，例如，在分割图像^[5]，立体匹配^[29]，和许多其它应用中^{[20，4，1，31，27，12]}。指派问题往往是制定图形结构的能量最小化。图形切割算法^{[5，4 ]}是一个很好的解决这个问题的解决方案。

虽然图形切割算法是一种有效的解决离散标签指派问题，但它没有被应用到二进制编码。这部分是因为该图形切割算法只能以有限的一组采样的给予方案，但对看不见的（称为“样本”泛化）没有预测。要利用图形切割，我们还需要优化编码函数。

在本文中，通过图形切割我们提出了一个二进制编码方法，我们主要集中在监督方案如^{[18，35，25，21]}。我们制定监督二进制编码为最优化问题。与大多数现有的方法不同，仅涉及到参数编码函数f，我们进一步将二进制码作为在优化辅助变量。我们的目标函数适合监督二进制码，并且还控制信息损耗。然后我们可以让二进制标签单独指派优化问题的子问题，并通过图形切割算法解决它 ^{[ 5，4 ]}。在实验中，这种图形编码（GCC）方法给出了各种数据集的竞争结果。

我们的方法提供了解决离散二进制编码固有问题的新颖方法。虽然大多数现有的方法（例如^{[ 35，36，25，21 ]}）通过各种连续放松或梯度下降解决这个问题，我们的图形切割解决方案更接近于二进制性质。我们不是首先通过“图”结构来考虑二进制编码，而是使用经典的“图形切割”算法^{[ 4，5 ]}来解决这个问题。在谱哈希（SH）^[36]的工作中已经指出，SH问题等同于“图划分”。 然而，SH所提出的解决方案 ^[36]基于连续光谱松弛。锚图哈希（AUG）^[23]的工作也被认为是图形结构，但也指出，一个图的用法是挑战泛化的“样本”。

AGH通过连续松弛，而不是离散的图切割解决了这个问题。

2相关工作

我们的工作是与计算机视觉中的看似无关的两个领域：二进制编码和图形切割。

学习二进制码。二进制编码早期的方法是随机的解决方案，如局部性敏感哈希（LSH）^[14，19]。最近采取最优化方法来研究二进制编码问题。在一些监督方法中，如二元重建嵌入（BRE）^{[ 18 ]}，半监督哈希（SSH）^{[ 35 ]}，最小损失哈希^{[ 25 ]}和基于内核的监督哈希^{[ 21 ]}，能量函数最大限度地减少了数据的相似性之间的差异和sign(f)的汉明距离。这些方法优化了能量函数编码函数f的连续参数w，r,t。这通常是通过梯度下降或连续松弛处理。

图形切割。在计算机视觉中，图形切割算法^[5,4]是一种快速，有效地解决二进制多标签指派问题的方法。图形切割算法已应用于图像分割^{[ 5 ]}，图像复原^{[ 5 ]}，立体匹配^{[ 29 ]}，纹理合成^{[1， 20 ]} 、图像拼接、图像增强^{[ 27，31 ]} ，图像缩放，图像修复^{[ 12 ]}，等等。图形切割算法通常被用来最小化一种形式的能量^{[ 5]}：

其中是图像像素的标记，例如，0 / 1的二进制分割。是依赖于单个像素的元项（也称为数据项），取决于两个像素成对项（也称为二进制/平滑项）。在没有连续的松弛是必要的条件下，图形切割求解器是基于最大流/最小割^{[ 4 ]}。

3监督二进制编码的图形切割

3.1 模型建立

我们用表示空间中包含个样本的数据集。我们首先讨论的线性编码函数

其中是维向量，是标量。之后，我们将讨论的核心化案例。

现有的二进制编码方法^{[14，36，19，18，35，10，25，23，21，28，30]}大多采取符号函数计算一个比特。然而，在我们训练过程中，我们允许不同的符号函数。我们把二进制码作为辅助变量，通过损失函数控制符号函数的偏差。这使得该能量函数更加灵活。作为一个概述，我们最小化能量函数形式如下：

其中，如果B比特已知，和是该编码函数的参数, 是阶矩阵，每行作为一个样本向量的B比特位。值不是1，就是-1，是权重。

在我们的优化中，不必和符号函数一样，是用来测量和偏差。用来适应监督编码。注意辅助变量仅在训练过程中使用。训练结束后，所有的数据和查询用符号函数和优化参数进行编码。我们设计的能量基于以下几点：（i）每个编码函数应最大化每比特差额；(ii) 编码比特应尊重监督;(iii) 比特应当尽可能的独立。我们把所有的关注放在一个单一的能量函数中。

最大边缘的编码函数

我们把每个编码函数作为训练数据集中个样本和个标签的分类。这里的维向量是的第k列（所有样品的第k个比特）。在本文中，我们希望每一个分类器以最大化正/负样本之间的余量。一个二进制的支持向量机分类，可以制定最大限度地减少这种能量函数^{[ 11 ]}：

其中，表示铰链损失，是支持向量机控制软边的一个参数。

我们把所有的编码函数集合起来，把它们的成本汇总起来：

其中是Frobenius范数。

从分类的角度来看，这种能量最大化每个比特正/负样本之间的偏差。但从二进制编码的观点来看，这个能量度量和编码值之间的损耗。

我们认为监督提供了一个阶亲和矩阵^{[ 18，35，25，21 ]}。例如在KSH^[21] 中，如果相似，则，如果不相似，，如果相似性未知，。遵守监督，我们认为以尽量减少能量：

其中是求矩阵的迹，直观地说，如果，那么（注是-1或1），如果，那么。

如果我们的优化问题，只有在公式（4）和（5）有条件，它将平凡产生B相同编码函数，由于公式（4）和（5）只是简单的聚合的能量函数，共享相同的形式。下一步我们介绍一个项来避免这种情况。

位独立

我们希望所有的编码函数是独立的，以便避免琐碎的情况。理想情况下，我们希望有一个约束条件为：,其中是阶单位矩阵。这个约束最早是在考虑光谱哈希（SH）^[36]。但是这将导致一个具有挑战性的约束离散优化问题，这是在连续放松^[36]。我们在这里考虑的是正则化最小化.。我们进行放大并省略常数，得到等价最小化：

公式（5）、（6）相加得

其中是权重，是只涉及变量的能量。

能量函数

考虑公式（4）、（7），我们最小化如下问题：

公式（2）中我们凭经验设置参数。变量有待于优化。在这里，我们明确地把作为优化变量，而许多以前的作品（例如，[18，35，25，21]）只涉及。因此，在训练过程中的数据，我们的能量函数允许直接分配二进制值。

3.2位图形切割

我们通过迭代求解两个子问题优化能量（3.1）：(i)固定，更新；(ii)固定，更新。在公式（3），第一个子问题相当于解决B独立的二进制SVM分类器。第二个子问题是一个涉及的二值分配问题。我们按顺序解决每一位，固定其余位。从形式上看，每次我们更新阶向量，固定其余向量。然后我们反复更新每个位。我们表明问题可以作为一个图割问题：它只涉及到一元和成对。为便于演示，我们表示，固定和其余向量，我们将会证明优化(3.1) 等价于最小化：

其中““所有可能对的总和。表示元项，代表成对元项，例如公式(1)。

在公式(9)显示元项很容易，如下：

为了计算，我们需要表达对的贡献，用矩阵表示。注意只有对成对项有贡献。经过一些代数运算我们可以把公式（7）改写为：

其中是常数且独立于。令，那么对的贡献是，这样，成对项是：

根据这些定义，公式（9）是一个标准的能量最小化问题。

公式（9）的问题可以表示为图。有n个顶点与相对应，在图中连接和的边表示成对项。有两个额外的顶点代表两标签，通常称为源和接收器^{[ 4 ]}。这两个顶点链接每一个代表一个项。公式（9）最小的能量相当于找到一个“切割”^{[ 5 ]}，把图分离为2个不连通的部分。这切割的成本是不相连边成本的总和。该图形切割算法^[5,4]是要找到这样的切割的一个解决方案。

理论上，图形切割算法需要成对项是“子模”^[15]，即

根据公式(12), 该子模块的条件是,其实并不总是成立。然而，在各种应用^{[20，1，27，3，12]}中，它一直凭经验观察到，从该状态的偏差仍然可以产生实际上良好的效果。

此外，凭经验图形切割算法还可以很好地用于有效地降低我们的目标函数。另一种选择是应用非子模块的情况下开发的求解器，如QPBO^[15]。未来我们将研究这种替代。

3.3算法总结和讨论

算法1中描述了我们对（3.1）的解决方法。在第3-5行更新，6-10行更新。我们设定的迭代次数为，更新y为2（更多的迭代仍然可以降低能量，但训练慢）。在多标签图中，y的更新是类似于切割^{[4 ]}。在第4行SVM使用LIBLINEAR包^[7]和支持向量机，参数c通过交叉验证调整。从Q的定义中，我们凭经验令，这样有类似的量值。我们采用GCO⁷作为图割求解公式（9）。一些讨论如下。

图1:mAP与迭代次数图

图1：初始化的影响。Y轴是CIFAR10数据集平均mAP，在4.1节中，CIFAR10实验设置

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[150911]，资料为PDF文档或Word文档，PDF文档可免费转换为Word