Approximate Best Bin First k-d Tree All Nearest Neighbor Search with Incremental Updates

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F10%3A00175535" target="_blank" >RIV/68407700:21230/10:00175535 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Approximate Best Bin First k-d Tree All Nearest Neighbor Search with Incremental Updates

Popis výsledku v původním jazyce

We describe an approximate algorithm to find all nearest neighbors (NN) for a set of points in moderate to high-dimensional spaces. Although the method is generally applicable, it is tailored to our main application, which is a NN-based entropy estimation for an image similarity criterion for image registration. Our algorithm is unique for having simultaneously the following features: (i) It is usable for millions of data points in several tens of dimensions. (ii) It can deal with multiple points. (iii)It offers a speedup of the all-NN search task with respect to repeating a NN search for each query point. (iv) It allows exact as well as approximate search when reduced search time is needed. (v) The search tree can be updated incrementally when the change of values of the data points is small. The method is based on creating a balanced k-d tree, which is then searched using the best-bin-first strategy. The tree nodes contain both tight and loose bounding boxes. The method is presented

Název v anglickém jazyce

Approximate Best Bin First k-d Tree All Nearest Neighbor Search with Incremental Updates

Popis výsledku anglicky

We describe an approximate algorithm to find all nearest neighbors (NN) for a set of points in moderate to high-dimensional spaces. Although the method is generally applicable, it is tailored to our main application, which is a NN-based entropy estimation for an image similarity criterion for image registration. Our algorithm is unique for having simultaneously the following features: (i) It is usable for millions of data points in several tens of dimensions. (ii) It can deal with multiple points. (iii)It offers a speedup of the all-NN search task with respect to repeating a NN search for each query point. (iv) It allows exact as well as approximate search when reduced search time is needed. (v) The search tree can be updated incrementally when the change of values of the data points is small. The method is based on creating a balanced k-d tree, which is then searched using the best-bin-first strategy. The tree nodes contain both tight and loose bounding boxes. The method is presented

Druh

O - Ostatní výsledky

CEP obor

JD - Využití počítačů, robotika a její aplikace

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0567" target="_blank" >1M0567: Centrum aplikované kybernetiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů