高维数据的近邻搜索方法以及快速近似图像搜索方法

摘要

本发明涉及高维数据的近邻搜索技术领域，特别涉及一种高维数据的近邻搜索方法，包括以下步骤：1、利用机器学习算法建立具有预定深度的搜索树；2、将数据库中的高维数据放入搜索树中；3、利用经过步骤2建立好的搜索树进行近邻搜索。还涉及一种快速近似图像搜索方法，图像的特征向量为高维数据，利用本发明的高维数据的近邻搜索方法搜索；4、建立多个步骤1中所述的搜索树，根据多个搜索树得到多个近邻搜索结果，然后选取所有结果的交集作为最终的搜索结果。本发明的高维数据的近邻搜索方法以及快速近似图像搜索方法，能够处理高维数据，真正达到次线性速度的近邻搜索，并且搜索结果稳定，正确率高。

说明书

技术领域

本发明涉及高维数据的近邻搜索技术领域，特别涉及一种高维数据的近邻搜索方法以及快速近似图像搜索方法。

背景技术

随着科学技术的发展，大规模图像搜索引擎必须具备快速近似图像搜索的能力，即搜索时间与数据库中的图像总数之间必须是次线性的关系。现在常用的快速近似图像搜索方法都是基于向量空间模型的图像特征的相似性匹配方法。目前数据库领域里具备次线性近似数据搜索能力的技术包括k-d树，R-树等。但是，这两种数据结构以及它们的变换结构只适用于搜索维数较低的数据。为了增加搜索精度，用于表征图像的特征向量往往具有高维特性，其维数数量级可达到10⁵。当数据的维数超过100，甚至达到上千维时，上述数据结构的近似数据搜索能力将会急速地衰退，最后变得和线性搜索一样，甚至不如线性搜索，此现象也被称为维数灾难。

为了克服k-d树，R-树的维数灾难的问题，RBM(Restricted BoltzmannMachine，限制性波尔兹曼机)、Spectral Hashing(谱哈希算法)等新一代技术被发明了出来。然而，这些技术的主要目的，是在不导致大规模信息丢失的前提下把高维的数据，例如图像特征向量，转换为几个byte，至多几百个byte的紧凑代码，从而使一台服务器的内存能够容纳几千万幅，甚至上亿幅图片。但是这些技术只是将数据压缩，并没有提供以次线性的速度快速搜索近似图像的解决方案。

发明内容

本发明要解决的技术问题是：为了克服现有技术中，当数据的维数较高时，近似数据搜索能力急速衰退的不足，本发明提供一种高维数据的近邻搜索方法以及大规模图像搜索引擎中的快速近似图像搜索方法，能够处理高维数据，真正达到次线性速度的近邻搜索，并且搜索正确率高。

本发明解决其技术问题所采用的技术方案是：一种高维数据的近邻搜索方法，从高维数据的数据库中搜索高维样本数据S的近邻数据，包括以下步骤：

(1)利用机器学习算法建立具有预定深度的搜索树：

(a)给定N个代表数据库中的高维数据分布特性的训练样本，输入N个训练样本以及训练样本的N×N近邻关系矩阵，根据近邻关系矩阵把整个高维数据空间分割为两个子空间，使分割后的子空间包含最多的近邻数据；

(b)将步骤(a)中分割后的子空间作为待分割子空间；

(c)根据近邻关系矩阵把待分割子空间分割成两个新的子空间，使本次分割后的新的子空间包含最多的近邻数据；

(d)判断新的子空间是否分割到预定的深度，如果是，则停止分割；否则将新的子空间作为待分割子空间，并返回步骤(c)；

分割后的高维数据空间与搜索树的对应关系为：搜索树的根节点对应整个高维数据空间，每个结点的两个子节点分别对应同一次分割所得到的两个子空间；

(2)将数据库中的高维数据放入搜索树中；

(3)利用经过步骤(2)建立好的搜索树进行近邻搜索：输入高维样本数据S，找出高维样本数据S在搜索树中所对应的节点，所述的节点中的高维数据即为找出的近邻数据；

(4)建立多个步骤(1)中所述的搜索树，根据所述的多个搜索树得到多个步骤(3)的近邻搜索结果，然后选取所有结果的交集作为最终的搜索结果。

步骤(1)中，空间分割的方法为根据近邻关系矩阵寻找最佳分隔面，所述的最佳分隔面使分割后的子空间包含最多的近邻数据。

步骤(1)中所述的搜索树为二叉树，建立所述的搜索树的方法为，包括以下步骤：

(1a)输入N个训练样本以及训练样本的N×N近邻关系矩阵H，N个训练样本均为X维向量；

(1b)创建根节点R，使其对应整个X维空间，把根节点R放入等待队列Q中；

(1c)判断等待队列Q中是否有节点，如果有，则从队列Q中取出第一个节点T，否则输出创建的搜索树；

(1d)判断取出的节点T是否到达预定深度，如果是，则返回步骤(1c)，否则在取出的节点T所对应的X维空间O内，随机地或者根据一定的规则获取一个Y维子空间W，Y＜＜X，将X维空间O内的所有向量投影到Y维子空间W中；

(1e)根据近邻矩阵H，在Y维子空间W里寻找分隔面P，将Y维子空间W分割成W_L和W_R两个子空间，并且使W_L和W_R两个子空间均包含最多的近邻数据；同时，分隔面P将X维空间O分割成O_L和O_R两个子空间；

(1f)把Y维子空间W及分隔面P的信息保存到步骤(1c)中取出的节点T中，创建节点T的两个子节点T_L和T_R，则子节点T_L和T_R分别对应步骤(1e)中所述的子空间O_L和O_R；

(1g)将子节点T_L和T_R放入等待队列Q中，返回步骤(1c)。

步骤(2)的具体方法为：数据库中高维数据为X维向量，将数据库中的X维向量投影到Y维子空间W中，判断所述的数据库中的X维向量的投影在分隔面P的左面还是右面，即判断得出对应搜索树的左节点还是右节点；如果对应的搜索树的节点是叶节点，则将所述的数据库中的X维向量放入当前叶节点中。

步骤(2)的具体方法为，包括以下步骤：

(2a)数据库中高维数据为X维向量，输入一个数据库中的X维向量，作为待填充数据；

(2b)从搜索树的根节点开始，取出根节点中记录的Y维子空间W及分隔面P的信息；

(2c)将待填充数据投影到Y维子空间W中；

(2d)判断待填充数据的投影在分隔面P的左面还是右面，如果是左面，则搜索树下降到分隔面P的左面所对应的子节点；如果是右面，则搜索树下降到分隔面P的右面所对应的子节点；

(2e)判断当前子节点是否是叶节点，如果是，则把待填充数据放入当前子节点中；否则取出当前子节点中记录的Y维子空间W及分隔面P的信息，并返回步骤(2c)；

(2f)判断当前待填充数据是否是数据库中的最后一个数据，如果是，则结束，即步骤(2)的操作完成；否则输入数据库中的下一个X维向量作为待填充数据，并返回步骤(2b)。

步骤(3)的具体方法为：高维样本数据S为X维向量，将高维样本数据S的X维向量投影到Y维子空间W中，判断高维样本数据S的X维向量的投影在分隔面P的左面还是右面，即判断得出对应搜索树的左节点还是右节点；如果对应的搜索树的节点是叶节点，返回叶节点中的所有X维向量，返回的X维向量即为找出的近邻数据。

步骤(3)的具体方法为：

(3a)高维样本数据S为X维向量，输入高维样本数据S的X维向量；

(3b)从搜索树的根节点开始，取出根节点中记录的Y维子空间W及分隔面P的信息；

(3c)将代表高维样本数据S的X维向量投影到Y维子空间W中；

(3d)判断代表高维样本数据S的X维向量的投影在分隔面P的左面还是右面，如果是左面，则搜索树下降到分隔面P的左面所对应的子节点；如果是右面，则搜索树下降到分隔面P的右面所对应的子节点；

(3e)判断当前子节点是否是叶节点，如果是，则返回当前子节点中的所有数据；否则取出当前子节点中记录的Y维子空间W及分隔面P的信息，并返回步骤(3c)。

一般地，作为优选，子空间W的维数为Y＝1，在子空间W上寻找一个切割点，分隔面P为将所述的切割点作为垂点的切割面。

一般地，作为优选，子空间W的维数为Y＝2，在子空间W上寻找一条直线，分隔面P为经过所述的直线并且垂直于子空间W的切割面。

一般地，作为优选，子空间W的维数为Y＝3，分隔面P为子空间W上的一个平面。

一种快速近似图像搜索方法，从图像数据库里的图像中搜索样本图片S的近似图像，包括以下步骤：

(1)利用机器学习算法建立具有预定深度的搜索树：

(a)给定图像数据库的N个代表数据库中的高维数据分布特性的训练样本，输入N个训练样本的X维特征向量以及所述的训练样本的N×N近邻关系矩阵，根据近邻关系矩阵把整个特征空间分割为两个子空间，使分割后的子空间包含最多的近邻图像；

(b)将步骤(a)中分割后的子空间作为待分割子空间；

(c)根据近邻关系矩阵把待分割子空间分割成两个新的子空间，使本次分割后的新的子空间包含最多的近邻图像；

(d)判断新的子空间是否分割到预定的深度，如果是，则停止分割；否则将新的子空间作为待分割子空间，并返回步骤(c)；

分割后的特征空间与搜索树的对应关系为：搜索树的根节点对应整个特征空间，同一子树中的两个子节点分别对应同一次分割所得到的两个子空间；

(2)将图像数据库里的图像放入搜索树中：将图像数据库里的图像放入到其在搜索树中所属的叶结点中；

(3)利用经过步骤(2)建立好的搜索树进行近似图像搜索：输入样本图片S，找出样本图片S在搜索树中所对应的叶节点，所述的叶节点中的图像即为找出的近似图像；

(4)建立多个步骤(1)中所述的搜索树，根据所述的多个搜索树得到多个步骤(3)的近似图像搜索结果，然后选取所有结果的交集作为最终的搜索结果。

步骤(1)中，空间分割的方法为根据近邻关系矩阵寻找最佳分隔面，所述的最佳分隔面使分割后的子空间包含最多的近邻图像。

步骤(1)中所述的搜索树为二叉树，建立所述的搜索树的方法为，包括以下步骤：

(1a)输入N个训练样本的X维特征向量以及所述的训练样本的N×N近邻关系矩阵H；

(1b)创建根节点R，使其对应整个X维特征空间，把根节点R放入等待队列Q中；

(1c)判断等待队列Q中是否有节点，如果有，则从队列Q中取出第一个节点T，否则输出创建的搜索树；

(1d)判断取出的节点T是否到达预定深度，如果是，则返回步骤(1c)，否则在取出的节点T所对应的X维特征空间O内，随机地或者根据一定的规则获取一个Y维子空间W，Y＜＜X，将X维特征空间O内的所有特征向量投影到Y维子空间W中；

(1e)根据近邻矩阵H，在Y维子空间W里寻找分隔面P，将Y维子空间W分割成W_L和W_R两个子空间，并且使W_L和W_R两个子空间均包含最多的近邻图像；同时，分隔面P将X维特征空间O分割成O_L和O_R两个子空间；

(1f)把Y维子空间W及分隔面P的信息保存到步骤(1c)中取出的节点T中，创建节点T的两个子节点T_L和T_R，则子节点T_L和T_R分别对应步骤(1e)中所述的子空间O_L和O_R；

(1g)将子节点T_L和T_R放入等待队列Q中，返回步骤(1c)。

步骤(2)的具体方法为，包括以下步骤：

(2a)输入图像数据库中的一幅图像，作为待填充图像；

(2b)提取待填充图像的X维特征向量；

(2c)从搜索树的根节点开始，取出根节点中记录的Y维子空间W及分隔面P的信息；

(2d)将待填充图像的X维特征向量投影到Y维子空间W中；

(2e)判断待填充图像的X维特征向量的投影在分隔面P的左面还是右面，如果是左面，则搜索树下降到分隔面P的左面所对应的子节点；如果是右面，则搜索树下降到分隔面P的右面所对应的子节点；

(2f)判断当前子节点是否是叶节点，如果是，则把待填充图像放入当前子节点中；否则取出当前子节点中记录的Y维子空间W及分隔面P的信息，并返回步骤(2d)；

(2g)判断当前待填充图像是否是图像数据库中的最后一幅图像，如果是，则结束，即步骤(2)的操作完成；否则输入图像数据库中的下一幅图像作为待填充图像，并返回步骤(2b)。

步骤(3)的具体方法为：将样本图片S的X维特征向量投影到Y维子空间W中，判断样本图片S的X维特征向量的投影在分隔面P的左面还是右面，即判断得出对应搜索树的左节点还是右节点；如果对应的搜索树的节点是叶节点，返回叶节点中的所有图像，返回的图像即为找出的近似图像。

步骤(3)的具体方法为：

(3a)输入样本图片S；

(3b)提取样本图片S的X维特征向量；

(3c)从搜索树的根节点开始，取出根节点中记录的Y维子空间W及分隔面P的信息；

(3d)将样本图片S的X维特征向量投影到Y维子空间W中；

(3e)判断样本图片S的X维特征向量的投影在分隔面P的左面还是右面，如果是左面，则搜索树下降到分隔面P的左面所对应的子节点；如果是右面，则搜索树下降到分隔面P的右面所对应的子节点；

(3f)判断当前子节点是否是叶节点，如果是，则返回当前子节点中的所有图像；否则取出当前子节点中记录的Y维子空间W及分隔面P的信息，并返回步骤(3d)。

一般地，作为优选，子空间W的维数为Y＝2，在子空间W上寻找一条直线，分隔面P为经过所述的直线并且垂直于子空间W的切割面。

一般地，作为优选，子空间W的维数为Y＝3，分隔面P为子空间W上的一个平面。

一般地，作为优选，子空间W的维数为Y＝1，在子空间W上寻找一个切割点，分隔面P为将所述的切割点作为垂点的切割面。

《光子学报》2005年1月第34卷第1期《一种多分辨率高维图像特征匹配算法》中提出，传统的基于树结构的多维检索算法大多采用数据分割和空间分割的方法，其基本思想就是将距离相近的向量存储在同一个叶子节点中，而根节点中则保存其叶子节点中所有向量所构成的空间区域。在对向量进行匹配时，要判断向量是否包含在根节点所代表的空间区域内，依据此规则在树中遍历根节点和叶子节点，在进行高维特征向量匹配时，如果向量维数比较高，不同的根节点和叶子节点代表的空间区域可能完全重合，对树结构进行遍历时往往要访问所有的叶子节点，其性能反而不如线性穷举搜索。

文献中还指出，既然基于树结构的多维检索方法在高维情况下性能低于线性穷举搜索，在向量近似方法中搜索方法采用了线性穷举搜索的方法，但是在搜索时是对近似向量进行匹配，在进行向量近似时，将向量空间分割成2^b个超立方体的子空间，然后对每个子空间分配一个唯一的数字位串，每个数字位串的长度都为b.因为特征向量可以看作是向量空间中的一个点，这个点所在的子空间的数字位串就是此特征向量的近似向量，所有近似向量组成的序列就是一个向量近似文件。在利用线性穷举搜索对向量q进行匹配时，读取近似文件中的近似向量，就可以计算出向量q到此近似向量代表的子空间的距离的下限，如果距离下限大于目前的已经计算出近邻距离时，就可以把此向量过滤掉，从而减少算法的运算复杂度。

发明人考虑到上述问题后，

1、将近邻关系矩阵作为输入信息，即事先给定，无需在搜索中计算各特征向量之间的距离，减轻计算机负担，减少误码率，提高搜索效率。

2、对整个特征空间建立搜索二叉树，先把根节点分割为两个子节点，这相当于把对应的特征空间分割为两个子空间。针对每个子节点重复特征空间分割这一操作，直到二叉树达到事先指定的深度。在进行特征空间分割时，尽可能地让分割后的特征空间保持最多的近邻图像。这种方法建立的搜索二叉树，在特征向量维数比较高时，不同的根节点和叶子节点代表的空间区域不会重合；然后将图像数据库中的每一幅图像放入其所属的叶节点中，最终返回的是叶节点中的图像，结果稳定，正确率高。

本发明的有益效果是，本发明的高维数据的近邻搜索方法以及快速近似图像搜索方法，能够处理高维数据，真正达到次线性速度的近邻搜索，并且搜索结果稳定，正确率高；在实际搜索中，通常会建立多个所述的搜索树，一般为10个左右，根据建立的多个搜索树得到多个搜索结果，然后选取所有结果的交集作为最终搜索结果，根据概率论分析，最终得到的搜索结果受Y维子空间W是随机取样的影响不大。

附图说明

下面结合附图和实施例对本发明进一步说明。

图1是本发明的快速近似图像搜索方法中建立搜索树的流程图。

图2是本发明的快速近似图像搜索方法中将数据库中的图像填充入搜索树中的流程图。

图3是本发明的快速近似图像搜索方法中利用搜索树进行近似图像搜索的流程图。

具体实施方式

现在结合附图对本发明作进一步详细的说明。

本发明的高维数据的近邻搜索方法与本发明的快速近似图像搜索方法原理相同，近似图像搜索方法中利用图像的特征向量进行搜索，图像特征向量即对应高维数据近邻搜索方法中的高维数据，因此，以下具体实施方式仅详细说明快速近似图像搜索的方法。

本发明的快速近似图像搜索方法，从图像数据库里的所有图像中搜索样本图片S的近似图像，包括以下步骤：

(1)利用机器学习算法建立具有预定深度的搜索二叉树；

(2)将图像数据库里的所有图像放入搜索二叉树中；

(3)利用经过步骤(2)建立好的搜索树进行近似图像搜索；

(4)建立多个步骤(1)中所述的搜索树，根据多个搜索树得到多个步骤(3)的近似图像搜索结果，然后选取所有结果的交集作为最终的搜索结果。

其中，如图1所示，步骤(1)中所述的搜索二叉树的建立方法包括以下步骤：

(1a)输入N个代表数据库中的高维数据分布特性的训练样本的X维特征向量以及所述的训练样本的N×N近邻关系矩阵H；

(1b)创建根节点R，使其对应整个X维特征空间，把根节点R放入等待队列Q中；

(1c)判断等待队列Q中是否有节点，如果有，则从队列Q中取出第一个节点T，否则输出创建的搜索树；

(1d)判断取出的节点T是否到达预定深度，如果是，则返回步骤(1c)，否则在取出的节点T所对应的X维特征空间O内，随机地或者根据一定的规则获取一个Y维子空间W，Y＜＜X，将X维特征空间O内的所有特征向量投影到Y维子空间W中；

(1e)根据近邻矩阵H，在Y维子空间W里寻找分隔面P，将Y维子空间W分割成W_L和W_R两个子空间，并且使W_L和W_R两个子空间均包含最多的近邻图像；同时，分隔面P将X维特征空间O分割成O_L和O_R两个子空间；

(1f)把Y维子空间W及分隔面P的信息保存到步骤(1c)中取出的节点T中，创建节点T的两个子节点T_L和T_R，则子节点T_L和T_R分别对应步骤(1e)中所述的子空间O_L和O_R；

(1g)将子节点T_L和T_R放入等待队列Q中，返回步骤(1c)。

以下选取3个实施例对步骤(1d)和步骤(1c)，即特征空间O的分割方法加以说明。

实施例1

子空间W的维数为Y＝1，随机选取一根轴作为子空间W，在轴上寻找一个切割点，分隔面P为将所述的切割点作为垂点的切割面，分隔面P将子空间W切割成W_L和W_R两个子空间，使切割后的W_L和W_R两个子空间均包含最多的近邻图像。此时，X维特征空间O被分割成O_L和O_R两个子空间。

实施例2

子空间W的维数为Y＝2，随机选取一个面作为子空间W，在面上寻找一条直线，分隔面P为经过所述的直线并且垂直于子空间W的切割面，分隔面P将子空间W切割成W_L和W_R两个子空间，使切割后的W_L和W_R两个子空间均包含最多的近邻图像。此时，X维特征空间O被分割成O_L和O_R两个子空间。

实施例3

子空间W的维数为Y＝3，随机选取一个三维空间作为子空间W，分隔面P为子空间W上的一个平面，所述的平面将子空间W切割成W_L和W_R两个子空间，使切割后的W_L和W_R两个子空间均包含最多的近邻图像。此时，X维特征空间O被分割成O_L和O_R两个子空间。

如图2所示，步骤(2)的具体方法包括以下步骤：

(2a)输入图像数据库中的一幅图像，命名为I；

(2b)提取图像I的X维特征向量；

(2c)从搜索二叉树的根节点开始，取出根节点中记录的Y维子空间W及分隔面P的信息；

(2d)将图像I的X维特征向量投影到Y维子空间W中；

(2e)判断图像I的X维特征向量的投影在分隔面P的左面还是右面，如果是左面，则搜索二叉树下降到分隔面P的左面所对应的子节点；如果是右面，则搜索二叉树下降到分隔面P的右面所对应的子节点；

(2f)判断当前子节点是否是叶节点，如果是，则把图像I放入当前子节点中；否则取出当前子节点中记录的Y维子空间W及分隔面P的信息，并返回步骤(2d)；

(2g)判断当前的图像I是否是图像数据库中的最后一幅图像，如果是，则结束，即步骤(2)的操作完成；否则输入图像数据库中的下一幅图像，命名为I，并返回步骤(2b)。

如图3所示，步骤(3)的具体方法包括以下步骤：

(3a)输入样本图片S；

(3b)提取样本图片S的X维特征向量；

(3c)从搜索二叉树的根节点开始，取出根节点中记录的Y维子空间W及分隔面P的信息；

(3d)将样本图片S的X维特征向量投影到Y维子空间W中；

(3e)判断样本图片S的X维特征向量的投影在分隔面P的左面还是右面，如果是左面，则搜索二叉树下降到分隔面P的左面所对应的子节点；如果是右面，则搜索二叉树下降到分隔面P的右面所对应的子节点；

(3f)判断当前子节点是否是叶节点，如果是，则返回当前子节点中的所有图像；否则取出当前子节点中记录的Y维子空间W及分隔面P的信息，并返回步骤(3d)。

本发明的快速近似图像搜索方法的优越性能比较测试：因为谱哈希算法被公认为是性能最好的近似图像搜索技术之一，所以，我们选择它作为性能比较的对象。对同一图像数据库进行图像搜索，表1表示的是本发明的快速近似图像搜索方法的搜索性能，表2表示的是谱哈希算法的搜索性能。表1的第一列中的数字表明建立索引所使用的近似图像搜索树的个数，所述的建立索引是为了寻找使用多个搜索树得到的结果的交集。本发明的一个搜索树相当于表2第一列中谱哈希算法的16比特。表1和表2中的第二列代表搜索时返回的近似图像的平均数和标准偏差数，“±”前面的数字为平均数，“±”后面的数字为标准偏差数。表1和表2中最后4列的含义如下：hitN代表在返回的近似图像中，真正是前N个近邻图像的数目。显然，这个数字越大，代表返回的图像的正确率越高。可以看出，本发明的近似图像搜索树在hit10，hit20，hit50，hit100这4项测试中都远远高于谱哈希算法。此外，因为表2第二列中的平均值及标准偏差值都非常大，所以使用谱哈希算法实施近似图像搜索，每次所返回的图像数目偏大，可能出现的差异也更大，这些将大大增加后处理的负担。相反，本发明的近似图像搜索树所返回的图像平均数和标准偏差都比谱哈希算法小很多，标准偏差更是小1～2个数量级。因此，本发明的快速近似图像搜索方法的搜索结果比较稳定，不会增加后处理的负担，并且返回的近似图像正确率高。

通过上述的说明内容，相关工作人员完全可以在不偏离本项发明技术思想的范围内，进行多样的变更以及修改。本项发明的技术性范围并不局限于说明书上的内容，必须要根据权利要求范围来确定其技术性范围。

表1

  #trees  #returns  hit10  hit20  hit50  hit100  10  95±14.9  4.96  8.79  17.58  27.26  20  171±29.0  6.74  12.40  26.20  42.65  50  352±83.0  8.59  16.44  37.35  65.49  100  576±168.8  9.38  18.34  43.59  80.54  200  900±313.7  9.77  19.35  47.20  90.59

表2

  #bits  #returns  hit10  hit20  hit50  hit100  160  493±1301.3  1.80  3.25  7.08  12.61  160  1913±4147.1  4.00  7.47  16.92  31.16  1600  135±293.3  3.88  6.97  14.59  24.84  1600  667±1119.3  5.92  11.09  25.17  46.15  1600  1332±2098.9  6.73  12.77  29.42  54.86