A Search Method Based on Binary Code Dictionary Tree

Abstract

Disclosed is a search method based on a binary code trie. The search method comprises: acquiring a binary code of each image in a database, and dividing each binary code into m segments of sub-strings (301); for the jth segment of sub-strings of all images in the database, creating a binary code trie of the jth segments of sub-strings (302), wherein the number of the binary code tries is m; and each of the binary code tries comprises: internal nodes and leaf nodes; acquiring a binary code of an image to be queried, and m segments of sub-strings of the binary code (303); for the jth segment of sub-strings of the binary code of the image to be queried, looking up, in the binary code tries corresponding to the jth segment of sub-strings of all the images in the database, binary codes of which the Hamming distances do not exceed r' (304); traversing all the sub-strings of the binary code of the image to be queried, so as to obtain a query result of each sub-string (305), wherein j is less than or equal to m; and according to the query results of all the sub-strings of the binary code of the image to be queried, performing a combination and deduplication test, so as to acquire a search result of the image to be queried (306). The method can reduce the quantity for lookup and improve the search speed during an accurate neighbor search in a Hamming space.

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