nanoflann
v1.6.2
O Nanoflann é uma biblioteca de cabeçalho C ++ 11 para a construção de árvores KD de conjuntos de dados com diferentes topologias: R2 , R 3 (nuvens de ponto), então (2) e SO (3) (grupos de rotação 2D e 3D). Nenhum suporte para NN aproximado é fornecido. O Nanoflann não requer compilação ou instalação. Você só precisa #include <nanoflann.hpp> no seu código.
Esta biblioteca é uma biblioteca de Flann de Marius Muja e David G. Lowe, e nasceu como um projeto infantil do MRPT. Após os termos de licença original, o Nanoflann é distribuído sob a licença BSD. Por favor, para bugs, use o botão ou bifurcação de problemas e abra uma solicitação de tração.
Citar como:
@misc{blanco2014nanoflann,
title = {nanoflann: a {C}++ header-only fork of {FLANN}, a library for Nearest Neighbor ({NN}) with KD-trees},
author = {Blanco, Jose Luis and Rai, Pranjal Kumar},
howpublished = {url{https://github.com/jlblancoc/nanoflann}},
year = {2014}
}
Consulte o Release Changelog para obter uma lista de alterações no projeto.
include/nanoflann.hpp para uso onde você precisar.$ sudo apt install libnanoflann-devnanoflann com Homebrew com: $ brew install brewsci/science/nanoflann$ brew tap brewsci/science
$ brew install nanoflann$ sudo port install nanoflannbrew install homebrew/science/nanoflannEmbora o próprio Nanoflann não precise ser compilado, você pode criar alguns exemplos e testes com:
$ sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
$ mkdir build && cd build && cmake ..
$ make && make testNavegue pela documentação doxygen.
NOTA IMPORTANTE: Se as normas L2 forem usadas, observe que o raio de pesquisa e todas as distâncias passadas e retornadas são na verdade distâncias ao quadrado .
knnSearch() e radiusSearch() : PointCloud_KDD_Radius.cppEigen::Matrix<> : matrix_example.cppstd::vector<std::vector<T> > ou std::vector<Eigen::VectorXd> : vetor_of_vectors_example.cppMakefile para uso através pkg-config (por exemplo, depois de fazer um "Faça a instalação" ou após a instalação dos repositórios do Ubuntu): exemplo_with_pkgconfig/mrpt-gui , por exemplo sudo apt install libmrpt-gui-dev ):
Eficiência do tempo de execução :
flann original vem da possibilidade de escolher entre diferentes algoritmos da ANN. O custo dessa flexibilidade é a declaração de métodos virtuais puros que (em algumas circunstâncias) impõem penalidades no tempo de execução. No nanoflann todos esses métodos virtuais foram substituídos por uma combinação do padrão de modelo (CRTP) curiosamente recorrente e métodos inlinados, que são muito mais rápidos.radiusSearch() , não há necessidade de fazer uma chamada para determinar o número de pontos dentro do raio e depois chamá -lo novamente para obter os dados. Usando contêineres STL para os dados de saída, os contêineres são redimensionados automaticamente.nanoflann permite que os usuários forneçam uma caixa delimitadora pré -computada dos dados, se disponível, para evitar a recomputação.int em size_t , que remove um limite ao lidar com conjuntos de dados muito grandes. Eficiência de memória : em vez de fazer uma cópia de todo o conjunto de dados em uma matriz do tipo flann personalizada antes de criar um índice KD -Tree, nanoflann permite o acesso direto aos seus dados por meio de uma interface adaptadora que deve ser implementada em sua classe.
Consulte os exemplos abaixo ou a API C ++ de Nanoflann :: kdtreesingleIndexadaptor <> para obter mais informações.
::knnSearch()num_closest mais próximos para query_point[0:dim-1] . Seus índices são armazenados dentro do objeto de resultado. Veja um exemplo de código de uso.::radiusSearch()query_point[0:dim-1] dentro de um raio máximo. A saída é dada como um vetor de pares, dos quais o primeiro elemento é um índice de ponto e o segundo a distância correspondente. Veja um exemplo de código de uso.::radiusSearchCustomCallback()Eigen::Matrix<> Classes (matrizes e vetores de vetores).R^N : espaços euclidianos:L1 (Manhattan)L2 (norma euclidiana quadrada , favorecendo a otimização do SSE2).L2_Simple (norma euclidiana quadrada , para conjuntos de dados de baixa dimensionalidade, como nuvens de ponto).SO(2) : 2D Grupo de rotaçãometric_SO2 : diferença angular absoluta.SO(3) : Grupo de rotação 3D (melhor suposto a ser fornecido em lançamentos futuros)metric_SO3 : Produto interno entre quaternions. Você pode soltar diretamente o arquivo nanoflann.hpp em seu projeto. Como alternativa, o método padrão cmake também está disponível:
CMAKE_INSTALL_PREFIX como um caminho adequado e execute make install (Linux, OSX) ou construa o destino INSTALL (Visual Studio). # Find nanoflannConfig.cmake:
find_package (nanoflann)
add_executable (my_project test .cpp)
# Make sure the include path is used:
target_link_libraries (my_project nanoflann::nanoflann)conan Você pode instalar binários pré-construídos para nanoflann ou construí-lo a partir da fonte usando Conan. Use o seguinte comando para instalar a versão mais recente:
$ conan install --requires= " nanoflann/[*] " --build=missingPara obter instruções detalhadas sobre como usar Conan, consulte a documentação de Conan.
A receita de nanoflann Conan é mantida atualizada por mantenedores de Conan e colaboradores da comunidade. Se a versão estiver desatualizada, crie uma solicitação de problema ou puxe no repositório ConancenteRIndex.
vcpkgVocê pode baixar e instalar o Nanoflann usando o gerenciador de dependência vcpkg:
$ git clone https://github.com/Microsoft/vcpkg.git
$ cd vcpkg
$ ./bootstrap-vcpkg.sh
$ ./vcpkg integrate install
$ ./vcpkg install nanoflannO porto de Nanoflann no VCPKG é mantido atualizado pelos membros da equipe da Microsoft e pelos colaboradores da comunidade. Se a versão estiver desatualizada, crie uma solicitação de problema ou puxe no repositório VCPKG.
NANOFLANN_FIRST_MATCH : Se definido e dois pontos tiverem a mesma distância, a do índice mais baixo será retornada primeiro. Caso contrário, não há ordem específica.NANOFLANN_NO_THREADS : Se definido, os recursos de leitura multithread serão desativados, para que a biblioteca possa ser usada sem vincular -se ao Pthreads. Se alguém tentar usar vários threads, uma exceção será lançada. KDTreeSingleIndexAdaptorParams::leaf_max_sizeUma árvore KD é ... bem, uma árvore :-). E, como tal, possui um nó raiz, um conjunto de nós intermediários e, finalmente, nós "folhas" que são aqueles sem filhos.
Os pontos (ou, corretamente, os índices pontuais) são armazenados apenas nos nós foliares. Cada folha contém uma lista da qual os pontos se enquadram em seu alcance.
Ao construir a árvore, os nós são recursivamente divididos até que o número de pontos dentro seja igual ou abaixo de algum limite. Isso é leaf_max_size . Ao fazer consultas, o "algoritmo da árvore" termina selecionando nós da folha e executando a pesquisa linear (um por um) para o ponto mais próximo da consulta dentro de todos os que estão na folha.
Portanto, leaf_max_size deve ser definido como uma troca :
Qual número de selecionar realmente depende do aplicativo e mesmo do tamanho da memória do cache do processador; portanto, idealmente, você deve fazer um benchmarking para maximizar a eficiência.
Mas, para ajudar a escolher um bom valor como regra geral, forneço os dois referências a seguir. Cada gráfico representa os tempos de construção da árvore (horizontal) e consulta (vertical) para diferentes valores leaf_max_size entre 1 e 10k (como elipses de incerteza de 95%, deformados devido à escala logarítmica).
float ):scan_071_points.dat do conjunto de dados do campus de Freiburg 360, cada ponto possui coordenadas float (x, y, z)): Portanto, parece que um leaf_max_size entre 10 e 50 seria o ideal em aplicações em que o custo das consultas domina (por exemplo, ICP). Atualmente, seu valor padrão é 10.
KDTreeSingleIndexAdaptorParams::checks Esse parâmetro é realmente ignorado em nanoflann , mas foi mantido para compatibilidade com versões anteriores com a interface Flann original. Apenas ignore.
KDTreeSingleIndexAdaptorParams::n_thread_build Este parâmetro determina o número máximo de encadeamentos que podem ser chamados simultaneamente durante a construção da árvore KD. O valor padrão é 1. Quando o parâmetro é definido como 0, nanoflann determina automaticamente o número de threads a serem usados.
Veja essa solicitação de tração para um benchmarking mostrando que o uso do número máximo de threads nem sempre é a abordagem mais eficiente. Faça benchmarking em seus dados!
nanoflann : uso mais rápido e menos de memória Consulte o "Por que um garfo?" Seção acima para as principais idéias de otimização por trás de nanoflann .
Observe que não há otimizações explícitas de SSE2/SSE3 em nanoflann , mas o uso intensivo de inline e modelos na prática se transforma em código otimizado automaticamente SSE gerado pelo compilador.
flann original vs nanoflannA parte mais demorada de muitos algoritmos de nuvem de pontos (como o ICP) está consultando uma árvore KD para os vizinhos mais próximos. Esta operação é, portanto, o mais crítico do tempo.
nanoflann fornece uma economia de ~ 50% em relação à implementação original flann (os tempos neste gráfico estão em microssegundos para cada consulta):
Embora a maior parte do ganho venha das consultas (devido ao grande número delas em qualquer operação típica com nuvens de ponto), também há algum tempo economizado ao construir o índice KD-Tree, devido ao código templatizado, mas também para evitar duplicar os dados em uma matriz auxiliar (os tempos do próximo gráfico estão em moinhos):
Esses testes de desempenho são representativos apenas de nossos testes. Se você quiser repeti-los, leia as instruções em testes de perfis
Nota: o logotipo do projeto é devido a cedarsed
Colaboradores
