Method, system and apparatus for generating hash codes
AssigneeCanon Kabushiki Kaisha
InventorsBarry James Drake, Andrew Peter Downing
Life of this patent
Estimating the term…
Abstract
A method of generating hash codes from a query vector. An ordering of dimensions is determined for a lattice hole in an A* lattice, the lattice hole being located nearest to the query vector and the ordering of dimensions represents a mapping applied to transform a canonical hole of the A* lattice to the lattice hole. An initial hash code is determined for a first point in the A* lattice, based on the query vector, using a plurality of predetermined constants. A subsequent hash code is generated for a second point in the A* lattice, from the initial hash code by modifying the initial hash code by a multiple of a constant. The constant is selected from the plurality of predetermined constants using the determined ordering of dimensions.
Claims14
A method of determining a matching image region which matches with a region of a query image, in a database of images, using a query vector formed from the region of the query image, wherein the image region is stored in a hash table using a hash code of a lattice point corresponding to a feature vector of the image region, the method comprising:
- determining a lattice hole which is located nearest to the query vector of the query image in a permutohedral lattice, an ordering of dimensions which represents a mapping applied to transform a canonical hole of the permutohedral lattice to the lattice hole, and an offset vector;
- determining an initial hash code for a first point around the lattice hole in the permutohedral lattice, based on the query vector, using the offset vector and a plurality of predetermined constants;
- generating at least one subsequent hash code for a second point around the lattice hole in the permutohedral lattice, from the initial hash code by modifying the initial hash code by a multiple of a constant, the constant being selected from the plurality of predetermined constants using the determined ordering of dimensions;
- and
- determining the matching image region in the database of images by retrieving data from the hash table using a plurality of hash codes including the initial hash code and the at least one subsequent hash code.
A system for determining a matching image region which matches with a region of a query image, in a database of images, using a query vector formed from the region of the query image, wherein the image region is stored in a hash table using a hash code of a lattice point corresponding to a feature vector of the image region, the system comprising:
- a memory for storing data and a computer program;
- a processor for executing said computer program, said computer program comprising code for:
- determining a lattice hole which is located nearest to the query vector of the query image in a permutohedral lattice, an ordering of dimensions which represents a mapping applied to transform a canonical hole of the permutohedral lattice to the lattice hole, and an offset vector;
- determining an initial hash code for a first point around the lattice hole in the permutohedral lattice, based on the query vector, using the offset vector and a plurality of predetermined constants;
- generating at least one subsequent hash code for a second point around the lattice hole in the permutohedral lattice, from the initial hash code by modifying the initial hash code by a multiple of a constant, the constant being selected from the plurality of predetermined constants using the determined ordering of dimensions;
- and
- determining the matching image region in the database of images by retrieving data from the hash table using a plurality of hash codes including the initial hash code and the at least one subsequent hash code.
An apparatus for determining a matching image region which matches with a region of a query image, in a database of images, using a query vector formed from the region of the query image, wherein the image region is stored in a hash table using a hash code of a lattice point corresponding to a feature vector of the image region, the apparatus comprising:
- means for determining a lattice hole which is located nearest to the query vector of the query image in a permutohedral lattice, an ordering of dimensions which represents a mapping applied to transform a canonical hole of the permutohedral lattice to the lattice hole, and an offset vector;
- means for determining an initial hash code for a first point around the lattice hole in the permutohedral lattice, based on the query vector, using the offset vector and a plurality of predetermined constants;
- means for generating at least one subsequent hash code for a second point around the lattice hole in the permutohedral lattice, from the initial hash code by modifying the initial hash code by a multiple of a constant, the constant being selected from the plurality of predetermined constants using the determined ordering of dimensions;
- and
- means for determining the matching image region in the database of images by retrieving data from the hash table using a plurality of hash codes including the initial hash code and the at least one subsequent hash code.
A computer readable medium having a computer program stored thereon for causing a processor to perform a method for determining a matching image region which matches with a region of a query image, in a database of images, using a query vector formed from the region of the query image, wherein the image region is stored in a hash table using a hash code of a lattice point corresponding to a feature vector of the image region, the method comprising:
- determining a lattice hole which is located nearest to the query vector of the query image in a permutohedral lattice, an ordering of dimensions which represents a mapping applied to transform a canonical hole of the permutohedral lattice to the lattice hole, and an offset vector;
- determining an initial hash code for a first point around the lattice hole in the permutohedral lattice, based on the query vector, using the offset vector and a plurality of predetermined constants;
- generating at least one subsequent hash code for a second point around the lattice hole in the permutohedral lattice, from the initial hash code by modifying the initial hash code by a multiple of a constant, the constant being selected from the plurality of predetermined constants using the determined ordering of dimensions;
- and
- determining the matching image region in the database of images by retrieving data from the hash table using a plurality of hash codes including the initial hash code and the at least one subsequent hash code.
Dependencies are inferred from the claim text.