# US 2019/0171665 A1 · Image similarity search via hashes with expanded dimensionality and sparsification

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0171665 A1
- Document ID: US20190171665A1
- Status: Published application
- Kind: A1
- Application number: 16/211,190
- Filed: 2018-12-05
- Published: 2019-06-06
- Earliest claimed: 2017-12-05
- Assignees: The Salk Institute for Biological Studies
- Applicants: Salk Institute for Biological Studies
- Inventors: Saket Navlakha; Charles F. Stevens
- Web page: https://patentgrep.com/patent/US20190171665A1

## CPC

- G06F 16/51: Indexing; Data structures therefor; Storage structures
- G06F 16/532: Query formulation, e.g. graphical querying
- G06F 16/538: Presentation of query results
- G06F 16/56: having vectorial format
- G06F 16/9014: {hash tables}
- G06F 18/2136: based on sparsity criteria, e.g. with an overcomplete basis
- G06F 18/22: Matching criteria, e.g. proximity measures
- G06V 10/761: {Proximity, similarity or dissimilarity measures}
- G06V 10/7715: {Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods}
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

Image similarity searching can be achieved by improving utilization of computing resources so that computing power can be reduced while maintaining accuracy or accuracy can be improved using a same level of computing power. Such a similarity search can be achieved via an expansion matrix that expands the number of dimensions in an input feature vector of a query image. Dimensionality of an input feature vector can be increased, resulting in a higher dimensional hash. Sparsification can then be applied to the resulting higher dimensional hash. Sparsification can use a winner-take-all technique or setting a threshold, resulting in a hash of reduced length, but can still be considered of the expanded dimensionality. Matching the query image against a corpus of sample images can be achieved via nearest neighbor techniques via the resulting hashes to find sample images matching the query image.

## Claims

### Claim 1

A computer-implemented method of performing an image similarly search, the method comprising:
for a query image, generating a query image hash via a hash model, wherein generating the query image hash comprises expanding dimensionality of a query image feature vector representing the query image and sparsifying the hash after expanding dimensionality;
matching the query image hash against hashes in a sample image hash database, wherein the hashes in the sample image hash database are previously generated via the hash model for respective sample images and represent the respective sample images, and wherein the matching identifies one or more matching hashes in the database; and
outputting the one or more matching hashes as a result of the similarity search.

### Claim 2 (depends on 1)

The method of claim 1, wherein the hash comprises a K-dimensional vector.

### Claim 3 (depends on 1)

The method of claim 1, wherein the expanding dimensionality comprises applying a matrix that is sparse or binary to the feature vector.

### Claim 4 (depends on 3)

The method of claim 3, wherein the matrix is random.

### Claim 5 (depends on 1)

The method of claim 1, wherein the expanding dimensionality comprises multiplying the query image feature vector by a random projection matrix.

### Claim 6 (depends on 5)

The method of claim 5, wherein the random projection matrix is sparse or binary.

### Claim 7 (depends on 1)

The method of claim 1, wherein the hash model implements locality-sensitive hashing.

### Claim 8 (depends on 1)

The method of claim 1, wherein the sparsifying the hash comprises:
applying a winner-take-all technique or a value threshold to choose one or more winning values of the hash; and
eliminating values from the hash that are not chosen as winning values.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
for the query image hash, generating a pseudo-hash via a pseudo-hash model, wherein generating the pseudo-hash comprises reducing the dimensionality of the query image hash after sparsifying the hash; and
matching the pseudo-hash of the query image against pseudo-hashes in a sample image pseudo-hash database, wherein the pseudo-hashes in the sample image pseudo-hash database are previously generated via the pseudo-hash model for respective sample image hashes and represent the respective sample image hashes, and wherein the matching identifies one or more matching pseudo-hashes in the database; and
outputting the sample image hashes of the one or more matching sample image pseudo-hashes in the sample image hash database.

### Claim 10 (depends on 1)

The method of claim 1, wherein the matching comprises:
receiving the query image hash and the sample image hash database; and
finding one or more nearest neighbors in the sample image hash database to the query image hash.

### Claim 11 (depends on 1)

The method of claim 1, wherein:
the matching comprises finding a matching hash in the sample image hash database, wherein the matching hash is associated with a bin identifier; and
the method further comprises outputting the bin identifier.

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
before generating the query image hash, normalizing the query image feature vector.

### Claim 13 (depends on 12)

The method of claim 12, wherein normalizing the query image feature vector comprises:
setting the same mean for the query image as the hashes in the sample image hash database; or
converting feature vector values of the query image feature vector to positive numbers.

### Claim 14

A similarity search system comprising:
one or more processors; and
memory coupled to the one or more processors, wherein the memory comprises computer-executable instructions causing the one or more processors to perform a process comprising:
for a query image, generating a query image hash via a hash model, wherein generating the query image hash comprises expanding dimensionality of a query image feature vector representing the query image and sparsifying the hash after expanding dimensionality;
matching the query image hash against hashes in a sample image hash database, wherein the hashes in the sample image hash database are previously generated via the hash model for respective sample images and represent the respective sample images, and wherein the matching identifies one or more matching hashes in the database; and
outputting the one or more matching hashes as a result of the similarity search.

### Claim 15 (depends on 14)

The system of claim 14, wherein the expanding dimensionality comprises applying a matrix that is sparse or binary to the feature vector.

### Claim 16 (depends on 14)

The system of claim 14, wherein the expanding dimensionality comprises multiplying the query image feature vector by a random projection matrix.

### Claim 17 (depends on 16)

The system of claim 16, wherein the random projection matrix is sparse and binary.

### Claim 18 (depends on 14)

The method of claim 14, wherein the hash model implements locality-sensitive hashing.

### Claim 19 (depends on 14)

The method of claim 14, further comprising:
for the query image, generating a pseudo-hash via a pseudo-hash model, wherein generating the pseudo-hash comprises reducing the dimensionality of the query image hash after sparsifying the hash; and
matching the pseudo-hash of the query image against pseudo-hashes in a sample image pseudo-hash database, wherein the pseudo-hashes in the sample image pseudo-hash database are previously generated via the pseudo-hash model for respective sample image hashes and represent the respective sample image hashes, and wherein the matching identifies one or more matching pseudo-hashes in the database; and
outputting the one or more matching pseudo-hashes in the sample image hash database as candidate matches for the similarity search.

### Claim 20

One or more computer-readable media having encoded thereon computer-executable instructions that, when executed, cause a computing system to perform a similarity search method comprising:
receiving one or more sample images;
extracting feature vectors from the sample images, the extracting generating sample image feature vectors;
normalizing the sample image feature vectors;
with a hash model, generating sample image hashes from the normalized sample image feature vectors, wherein the hash model expands dimensionality of the normalized sample image feature vectors and subsequently sparsifies the sample image hashes after expanding dimensionality;
storing the hashes generated from the normalized sample image feature vectors into a sample image hash database;
receiving a query image;
extracting a feature vector from the query image, the extracting generating a query image feature vector;
normalizing the query image feature vector;
with the hash model, generating a query image hash from the normalized query image feature vector, wherein the hash model expands dimensionality of the normalized query image feature vector and subsequently sparsifies the query image hash after expanding dimensionality;
matching the query image hash against hashes in the sample image hash database; and
outputting matching sample image hashes of the sample image hash database as a result of the similarity search.
