Binary code dictionary tree-based search method

Abstract

The invention discloses a binary code dictionary tree-based search method. The method comprises the steps of obtaining a binary code of each image in a database, and dividing each binary code into m sections of substrings; for the jth sections of the substrings of all images in the database, establishing a binary code dictionary tree of the jth sections of the substrings, wherein the number of binary code dictionary trees is m, and each binary code dictionary tree comprises internal nodes and external nodes; obtaining the binary code of the to-be-queried image and the m sections of the substrings of the binary code; for the jth section of the substring of the binary code of the to-be-queried image, searching for the binary code with a Hamming distance not exceeding a value defined in the specification in the binary code dictionary tree corresponding to the jth sections of the substrings of all the images in the database; and traversing all the substrings of the binary code of the to-be-queried image to obtain a query result of each substring, wherein j is smaller than or equal to m. According to the method, the search quantity can be reduced during accurate nearest neighbor search of Hamming space, so that the search speed is increased.

Description

technical field [0001] The invention relates to computer vision technology, in particular to a search method based on binary code dictionary tree. Background technique [0002] In recent years, the problem of binary representation of high-dimensional vectors has gained extensive attention. The goal of binary encoding is to compress features into a compact binary code. Binary codes have the advantages of easy storage, easy indexing, and fast comparison, and are the first choice for processing large-scale data applications. Although the Hamming distance comparison between binary codes is very fast (millions of comparisons can be completed within 1 second), when the data size is particularly large, the method of linearly scanning the entire data set still cannot achieve real-time retrieval . Therefore, it is necessary to design an efficient indexing algorithm to improve the retrieval speed of binary codes under large-scale data sets. [0003] A common method of indexing a b...

AI Technical Summary

Problems solved by technology

However, in practical applications, it is found that most of the hash buckets are empty, and accessing empty buckets (called missing lookups) is unnecessary and will waste a lot of time

Images