高维近邻对搜索方法和系统

专利主权项内容

1.一种高维近邻对搜索方法，其特征在于，包括以下步骤：根据图像样本向量的数值生成对应的样本签名；根据所述样本签名生成近邻候选组；计算每个近邻候选组中的任意两个样本之间的距离，将距离满足预设要求的样本对作为近邻搜索结果；若生成a个近邻候选组，每个近邻候选组包含b个样本，则可计算每个近邻候选组中任意两个样本之间的距离并按从小到大排序，分别选择a组中排序在前的K个样本对，，再从小到大进行排序，选择此时排序在前的K个样本对，即得到近邻搜索结果；所述样本签名为二值向量；通过投影矩阵将样本向量从原始向量映射到目标向量，其中，d是原始向量的维度，k是目标向量的维度，d大于k；如果所述目标向量的值不小于零，则在样本签名的相应位置赋1；如果所述目标向量的值小于零，则在样本签名的相应位置赋0；所述投影矩阵/>由高斯分布N(0, 1/k)随机生成；其中，根据所述样本签名生成近邻候选组，包括：S21：构造深度为N的二叉树，并将所述样本签名保存在所述二叉树的叶节点中，其中，从所述二叉树的根节点到叶节点的路径与所述样本签名前N维的数值对应，前N位签名相同的样本保存在同一个叶节点中，N小于所述样本签名的长度M；S22：当叶节点中的样本签名数量大于第一预设值T时，将第N+1位数值不同的样本签名分入该叶节点下的两个不同的子叶节点；S23：对树进行剪枝，将第N层的叶节点剪除；S24：重复步骤S22和S23，直至不存在需要切分的叶节点。