Optimised KD-trees for fast image descriptor matching

Chanop Silpa-Anan*, Richard Hartley

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    604 Citations (Scopus)

    Abstract

    In this paper, we look at improving the KD-tree for a specific usage: indexing a large number of SIFT and other types of image descriptors. We have extended priority search, to priority search among multiple trees. By creating multiple KD-trees from the same data set and simultaneously searching among these trees, we have improved the KD-tree's search performance significantly. We have also exploited the structure in SIFT descriptors (or structure in any data set) to reduce the time spent in backtracking. By using Principal Component Analysis to align the principal axes of the data with the coordinate axes, we have further increased the KD-tree's search performance.

    Original languageEnglish
    Title of host publication26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR
    DOIs
    Publication statusPublished - 2008
    Event26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR - Anchorage, AK, United States
    Duration: 23 Jun 200828 Jun 2008

    Publication series

    Name26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR

    Conference

    Conference26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR
    Country/TerritoryUnited States
    CityAnchorage, AK
    Period23/06/0828/06/08

    Cite this