nanoflann
v1.6.2
Nanoflann은 다른 토폴로지가있는 데이터 세트의 KD 트리를 구축하기위한 C ++ 11 헤더 전용 라이브러리 입니다 : R 2 , R 3 (포인트 클라우드), SO (2) 및 SO (3) (2D 및 3D 회전 그룹). 대략적인 NN에 대한 지원은 제공되지 않습니다. Nanoflann은 컴파일 또는 설치가 필요하지 않습니다. 코드에서 #include <nanoflann.hpp> 만 있으면됩니다.
이 도서관은 Marius Muja와 David G. Lowe의 Flann 도서관의 포크 이며 MRPT의 어린이 프로젝트로 태어났습니다. 원래 라이센스 약관에 따라 Nanoflann은 BSD 라이센스에 따라 배포됩니다. 버그가 문제 버튼을 사용하거나 포크를 사용하고 풀 요청을여십시오.
인용 :
@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}
}
프로젝트 변경 목록은 Release ChangeLog를 참조하십시오.
include/nanoflann.hpp 시킵니다.$ sudo apt install libnanoflann-devnanoflann 설치할 수 있습니다. $ brew install brewsci/science/nanoflann$ brew tap brewsci/science
$ brew install nanoflann$ sudo port install nanoflannbrew install homebrew/science/nanoflannNanoflann 자체를 컴파일 할 필요는 없지만 다음과 함께 몇 가지 예와 테스트를 구축 할 수 있습니다.
$ sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
$ mkdir build && cd build && cmake ..
$ make && make testDoxygen 문서를 찾아보십시오.
중요 참고 : L2 규범을 사용하는 경우 검색 반경과 모든 통과 및 반환 거리가 실제로 제곱 거리 라는 것을 주목하십시오.
knnSearch() 및 radiusSearch() 사용한 KD-Tree 조회 : PointCloud_kdd_radius.cppEigen::Matrix<> 에서 직접 조회합니다. : Matrix_example.cppstd::vector<std::vector<T> > 또는 std::vector<Eigen::VectorXd> 에서 직접 조회합니다.pkg-config 통한 Makefile 의 예제 (예 : "설치 만들기"또는 Ubuntu 저장소에서 설치 한 후) : example_with_pkgconfig/mrpt-gui 필요, 예를 들어 sudo apt install libmrpt-gui-dev ) :
실행 시간 효율성 :
flann 라이브러리의 힘은 다른 ANN 알고리즘 중에서 선택할 가능성에서 비롯됩니다. 이 유연성의 비용은 (어떤 상황에서는) 런타임 처벌을 부과하는 순수한 가상 방법의 선언입니다. nanoflann 에서 이러한 모든 가상 방법은 호기심으로 되풀이되는 템플릿 패턴 (CRTP)과 인라인 메소드의 조합으로 대체되었습니다.radiusSearch() 의 경우 반경 내의 점수를 결정하기 위해 호출 할 필요가 없습니다. 그런 다음 다시 호출하여 데이터를 얻습니다. 출력 데이터에 STL 컨테이너를 사용하면 컨테이너가 자동으로 크기가 커집니다.nanoflann 사용하면 사용자가 재 계산을 피하기 위해 데이터의 미리 계산 된 경계 박스를 제공 할 수 있습니다.int 에서 size_t 로 변환되어 매우 큰 데이터 세트를 처리 할 때 제한이 제거됩니다. 메모리 효율성 : KD -Tree 인덱스를 구축하기 전에 전체 데이터 세트의 사본을 사용자 정의 flann 유사 매트릭스로 만드는 대신 nanoflann 클래스에서 구현 해야하는 어댑터 인터페이스를 통해 데이터에 직접 액세스 할 수 있습니다.
자세한 내용은 아래 예제 또는 Nanoflann :: KdtreesingleIdtexAdaptor <>의 C ++ API를 참조하십시오.
::knnSearch()query_point[0:dim-1] 에 num_closest 가까운 이웃을 찾습니다. 그들의 지수는 결과 객체 안에 저장됩니다. 예제 사용 코드를 참조하십시오.::radiusSearch()query_point[0:dim-1] 찾습니다. 출력은 쌍의 벡터로 주어지며, 그 중 첫 번째 요소는 포인트 인덱스이고 두 번째는 해당 거리입니다. 예제 사용 코드를 참조하십시오.::radiusSearchCustomCallback()Eigen::Matrix<> 클래스 (매트릭스 및 벡터 벡터)와 직접 작업합니다.R^N : 유클리드 공간 :L1 (맨해튼)L2 ( 제곱 유클리드 규범, SSE2 최적화에 유리함).L2_Simple (포인트 클라우드와 같은 저차원 데이터 세트에 대한 제곱 유클리드 규범).SO(2) : 2d 회전 그룹metric_SO2 : 절대 각도 차이.SO(3) : 3D 회전 그룹 (향후 릴리스에서 제공되는 더 나은 Suppport)metric_SO3 : 쿼터니온 사이의 내부 제품. 프로젝트에서 nanoflann.hpp 파일을 직접 삭제할 수 있습니다. 또는 CMAKE 표준 방법도 사용할 수 있습니다.
CMAKE_INSTALL_PREFIX 적절한 경로로 설정 한 다음 make install (Linux, OSX)을 실행하거나 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 사용 nanoflann 용 사전 제작 된 바이너리를 설치하거나 Conan을 사용하여 소스에서 빌드 할 수 있습니다. 다음 명령을 사용하여 최신 버전을 설치하십시오.
$ conan install --requires= " nanoflann/[*] " --build=missingConan 사용 방법에 대한 자세한 지침은 Conan 문서를 참조하십시오.
nanoflann Conan 레시피는 Conan 관리자와 커뮤니티 기고자에 의해 최신 상태로 유지됩니다. 버전이 구식 인 경우 ConancenterIndex 저장소에서 문제를 만들거나 요청을 가져 오십시오.
vcpkg 사용VCPKG 종속성 관리자를 사용하여 Nanoflann을 다운로드하여 설치할 수 있습니다.
$ git clone https://github.com/Microsoft/vcpkg.git
$ cd vcpkg
$ ./bootstrap-vcpkg.sh
$ ./vcpkg integrate install
$ ./vcpkg install nanoflannVCPKG의 Nanoflann 항구는 Microsoft 팀원 및 커뮤니티 기고자가 최신 상태로 유지됩니다. 버전이 오래된 경우 VCPKG 저장소에서 문제를 만들거나 요청을 가져 오십시오.
NANOFLANN_FIRST_MATCH : 정의되고 두 점이 동일한 거리를 갖는 경우, 가장 낮은 인덱스가있는 것이 먼저 반환됩니다. 그렇지 않으면 특정 순서가 없습니다.NANOFLANN_NO_THREADS : 정의 된 경우 다중 스레딩 기능이 비활성화되어 PTHREADS와 연결하지 않고도 라이브러리를 사용할 수 있습니다. 여러 스레드를 사용하려고하면 예외가 발생합니다. KDTreeSingleIndexAdaptorParams::leaf_max_sizeKD-Tree는 ... 음, 나무 :-). 따라서 루트 노드, 중개 노드 세트 및 마지막으로 어린이가없는 "잎"노드가 있습니다.
포인트 (또는 적절하게 포인트 지수)는 잎 노드에만 저장됩니다. 각 잎에는 포인트가 범위에 속하는 목록이 포함되어 있습니다.
트리를 만드는 동안 노드는 내부 지점의 수가 일부 임계 값 이하가 될 때까지 재귀 적으로 나뉘어집니다. 그것은 leaf_max_size 입니다 . 쿼리를 수행하는 동안 "트리 알고리즘"은 리프 노드를 선택한 다음 잎의 모든 쿼리에서 가장 가까운 쿼리에 대한 선형 검색 (1-10)을 수행하여 끝납니다.
따라서 leaf_max_size 트레이드 오프 로 설정해야합니다.
선택해야 할 번호는 실제로 응용 프로그램과 프로세서 캐시 메모리의 크기에 따라 달라 지므로 효율성을 최대화하기 위해 벤치마킹을해야합니다.
그러나 경험상으로 좋은 가치를 선택하는 데 도움을주기 위해 다음 두 가지 벤치 마크를 제공합니다. 각 그래프는 1에서 10k 사이의 다른 leaf_max_size 값에 대한 트리 빌드 (수평) 및 쿼리 (수직) 시간을 나타냅니다 (95% 불확실성 타원, 로그 스케일로 인해 변형됨).
float 좌표) :scan_071_points.dat Freiburg Campus 360 데이터 세트에서 각 포인트는 (x, y, z) float 좌표를 가지고 있습니다. 따라서 10에서 50 사이의 leaf_max_size 쿼리 비용이 지배적 인 응용 프로그램에서 최적 인 것 같습니다 (예 : ICP). 현재 기본값은 10입니다.
KDTreeSingleIndexAdaptorParams::checks 이 매개 변수는 실제로 nanoflann 에서 무시되지만 원래 Flann 인터페이스와의 역 호환성을 위해 유지되었습니다. 그냥 무시하십시오.
KDTreeSingleIndexAdaptorParams::n_thread_build 이 매개 변수는 KD 트리를 구성하는 동안 동시에 호출 될 수있는 최대 스레드 수를 결정합니다. 기본값은 1입니다. 매개 변수가 0으로 설정되면 nanoflann 사용할 스레드 수를 자동으로 결정합니다.
최대 스레드 수를 사용하는 것이 항상 가장 효율적인 접근법이 아니라는 것을 보여주는 일부 벤치마킹에 대한이 풀 요청을 참조하십시오. 데이터 벤치마킹을 수행하십시오!
nanoflann : 더 빠르고 메모리 사용량이 적습니다 "왜 포크?" nanoflann 의 주요 최적화 아이디어에 대한 위의 섹션.
nanoflann 에는 명시적인 SSE2/SSE3 최적화가 없지만 실제로 inline 및 템플릿의 집중적 인 사용은 컴파일러에서 생성 된 자동으로 SSE에서 최적화 된 코드로 바뀝니다.
flann vs nanoflannICP와 같은 여러 Point Cloud 알고리즘의 가장 시간이 많이 걸리는 부분은 가장 가까운 이웃을 위해 KD-Tree를 쿼리하는 것입니다. 따라서이 작업은 가장 중요한 시간입니다.
nanoflann 원래 flann 구현과 관련하여 ~ 50% 시간 절약을 제공합니다 (이 차트의 시간은 각 쿼리에 대해 마이크로 초입니다).
대부분의 게인은 쿼리에서 비롯되지만 (포인트 클라우드가있는 전형적인 작업에서 많은 수의 이득 때문에) 템플릿 코드로 인해 KD-Tree 지수를 구축하는 동안 시간이 절약되지만 보조 매트릭스 (다음 차트의 시간)에서 데이터를 복제하는 것을 피하기 위해 시간이 절약됩니다.
이러한 성능 테스트는 테스트를 대표합니다. 반복하려면 perf-tests의 지침을 읽으십시오.
참고 : 프로젝트 로고는 cedarseed 때문입니다
기고자
