Image searching by approximate κ-NN graph
US8705870B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 2, 2012 |
| Grant date | Apr 22, 2014 |
| Priority date | — |
| Expiry date | Sep 6, 2032 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/583
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
This disclosure describes techniques for searching for similar images to an image query by using an approximate k-Nearest Neighbor (k-NN) graph. The approximate k-NN graph is constructed from data points partitioned into subsets to further identify nearest-neighboring data points for each data point. The data points may connect with the nearest-neighboring data points in a subset to form an approximate neighborhood subgraph. These subgraphs from all the subsets are combined together to form a base approximate k-NN graph. Then by performing more random hierarchical partition, more base approximate k-NN graphs are formed, and further combined together to create an approximate k-NN graph. The approximate k-NN graph expands into other neighborhoods and identifies the best k-NN data points. The approximate k-NN graph retrieves the best NN data points, based at least in part on the retrieved best k-NN data points representing images being similar in appearance to the image query.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.