Image Representation for Fast Query and Its Applications

在许多识别问题中，基本的过程是输入与数据集之间的匹配。这个过程可以被描述为高维向量空间中的最近邻问题。如果每个数据都位于高维空间中，那么根据维度的不同，最近邻搜索变得非常困难。例如，众所周知的kd树对于高维向量空间的搜索问题是无用的。在这篇报告中，我们首先比较了搜索算法，包括暴力破解法，kd-tree和LSH（局部敏感哈希）。我们证明，LSH是非常有效的，尽管它只能给出近似解。为了在高维向量空间中实现快速查询，重要的是降低目标数据集的维数和/或减小目标数据集的大小。LSH可以看作是对数据集进行约简检验的方法之一。在此基础上，我们首先提出了一种基于高斯混合模型和主成分分析的图像查询系统。然后，我们证明了如果数据集的分布可以被描述为“簇”，则可以实现快速查询。当数据集由多个聚类组成时，为每个输入向量识别合适的聚类是快速可靠搜索的关键。为了这个目的，我们必须从例子中学习分类器。由于我们不能期望分类器100%准确，因此希望获得产生多个假设的分类器。在我们的报告中，我们描述了一种扩展DAG-SVM以做出多个假设的方法。

In many recognition problems, basic procedure is the matching between the input and the data set. This procedure can be characterized as the nearest neighbor problem in high dimensional vector space. If each data resides in the high-dimensional space, nearest neighbor search is getting very difficult depending the dimensionality. For example, well-known kd-tree is useless for the search problem in high dimensional vector space. In this report, we first compare the search algorithms, including brute-force method, kd-tree and LSH(locality sensitivity hashing). We show, LSH can be very effective, although it can give only the approximation solution. To realize fast query in high-dimensional vector space, it is important to reduce the dimensionality and/or to reduce the size of the target data set. LSH can be seen as one of the method to reduce the data set to examine.Based on these preliminary results, we first propose an image query system based on the Gaussian mixture model and PCA(principle component analysis). Then, we show if the distribution of the data set can be described as the "clusters", fast query can be made possible. If data set is made up of several clusters, recognizing the appropriate cluster for each input vector is the key to the fast and reliable search. For that purpose, we have to learn classifiers from examples. Since we cannot expect the classifier 100% accurate, it is desirable to obtain classifiers which give rise to multiple hypotheses. In our report, we describe a method to extend DAG-SVM to make multiple hypotheses.