0

OpenCV 3.1.0 on Ubuntu 14.04

  1. cmakeのバージョンを3.1.3以上にする howto
  2. With QTのチェックを外す
Advertisements
0

FLANN: sample code to try different search algorithms

#include <iostream>
#include <string>
#include <vector>
#include <map>

#include <flann/flann.hpp>
#include <flann/io/hdf5.h>

std::vector<flann::flann_algorithm_t> indexFlannAlgorithm = {
    flann::FLANN_INDEX_LINEAR,
    flann::FLANN_INDEX_KDTREE,
    flann::FLANN_INDEX_KMEANS,
    flann::FLANN_INDEX_COMPOSITE,
    flann::FLANN_INDEX_KDTREE,
    flann::FLANN_INDEX_HIERARCHICAL,
//    flann::FLANN_INDEX_LSH,
    flann::FLANN_INDEX_AUTOTUNED
};

std::map<flann::flann_algorithm_t, std::string> flannAlgorithm =
{
    std::pair<flann::flann_algorithm_t, std::string>(flann::FLANN_INDEX_LINEAR, &amp;quot;linear&amp;quot;),
    std::pair<flann::flann_algorithm_t, std::string>(flann::FLANN_INDEX_KDTREE, &amp;quot;randomized kd-tree&amp;quot;),
    std::pair<flann::flann_algorithm_t, std::string>(flann::FLANN_INDEX_KMEANS, &amp;quot;k-means&amp;quot;),
    std::pair<flann::flann_algorithm_t, std::string>(flann::FLANN_INDEX_COMPOSITE, &amp;quot;composite&amp;quot;),
    std::pair<flann::flann_algorithm_t, std::string>(flann::FLANN_INDEX_KDTREE_SINGLE, &amp;quot;single kd-tree&amp;quot;),
    std::pair<flann::flann_algorithm_t, std::string>(flann::FLANN_INDEX_HIERARCHICAL, &amp;quot;hierarchical&amp;quot;),
    std::pair<flann::flann_algorithm_t, std::string>(flann::FLANN_INDEX_LSH, &amp;quot;LSH&amp;quot;),
    std::pair<flann::flann_algorithm_t, std::string>(flann::FLANN_INDEX_AUTOTUNED, &amp;quot;autotuned&amp;quot;)
};

void printMatrix(
    const flann::Matrix<float>&amp;amp; mat,
    const std::string str
)
{
    std::cout << str << std::endl;
    std::cout << &amp;quot;dim(data): &amp;quot; << mat.cols << std::endl;
    std::cout << &amp;quot;#data: &amp;quot; << mat.rows << std::endl;
}

void loadData(
    flann::Matrix<float>&amp;amp; dataset,
    flann::Matrix<float>&amp;amp; query
)
{
    flann::load_from_file(dataset, &amp;quot;../data/dataset.hdf5&amp;quot;, &amp;quot;dataset&amp;quot;);
    flann::load_from_file(query, &amp;quot;../data/dataset.hdf5&amp;quot;, &amp;quot;query&amp;quot;);
}

void setSearchResults(
    const size_t numQuery,
    const size_t numKnn,
    flann::Matrix<size_t>&amp;amp; resultIndex,
    flann::Matrix<float>&amp;amp; resultDistance
)
{
    resultIndex = flann::Matrix<size_t>(new size_t[numQuery*numKnn], numQuery, numKnn);
    resultDistance = flann::Matrix<float>(new float[numQuery*numKnn], numQuery, numKnn);
}

flann::SearchParams getSearchParams(
    const flann::flann_algorithm_t indexType
)
{
    switch (indexType)
    {
    case flann::FLANN_INDEX_KDTREE: return flann::SearchParams(256);
    case flann::FLANN_INDEX_KMEANS: return flann::SearchParams(128);
    case flann::FLANN_INDEX_COMPOSITE: return flann::SearchParams();
    case flann::FLANN_INDEX_KDTREE_SINGLE: return flann::SearchParams(-1);
    case flann::FLANN_INDEX_HIERARCHICAL: return flann::SearchParams(2000);
    case flann::FLANN_INDEX_LSH: return flann::SearchParams(-1);
    case flann::FLANN_INDEX_AUTOTUNED: return flann::SearchParams(-2);
    default: return flann::SearchParams(0);
    }
}

flann::IndexParams getIndexParams(
    const flann::flann_algorithm_t indexType
)
{
    switch (indexType)
    {
    case flann::FLANN_INDEX_KDTREE: return flann::KDTreeIndexParams();
    case flann::FLANN_INDEX_KMEANS: return flann::KMeansIndexParams();
    case flann::FLANN_INDEX_COMPOSITE: return flann::CompositeIndexParams();
    case flann::FLANN_INDEX_KDTREE_SINGLE: return flann::KDTreeSingleIndexParams();
    case flann::FLANN_INDEX_HIERARCHICAL: return flann::HierarchicalClusteringIndexParams();
    case flann::FLANN_INDEX_LSH: return flann::LshIndexParams();
    case flann::FLANN_INDEX_AUTOTUNED: return flann::AutotunedIndexParams();
    default: return flann::LinearIndexParams();
    }
}

void testKnnSearch(
    const flann::flann_algorithm_t indexType,
    const size_t numKnn,
    flann::Matrix<float>&amp;amp; dataset,
    flann::Matrix<float>&amp;amp; query,
    flann::Matrix<size_t>&amp;amp; resultIndex,
    flann::Matrix<float>&amp;amp; resultDistance
)
{
    std::cout << flannAlgorithm[indexType] << std::endl;
    clock_t t0, t1;
    flann::IndexParams indexParams = getIndexParams(indexType);
    flann::SearchParams searchParams = getSearchParams(indexType);
    flann::Index<flann::L2<float> > index(dataset, indexParams);
    t0 = clock();
    index.buildIndex();
    t1 = clock();
    std::cout << &amp;quot;  buildIndex: &amp;quot; << static_cast<double>(t1-t0)/CLOCKS_PER_SEC << &amp;quot; sec.&amp;quot; << std::endl;

    t0 = clock();
    index.knnSearch(query, resultIndex, resultDistance, numKnn, searchParams);
    t1 = clock();
    std::cout << &amp;quot;  knnSearch: &amp;quot; << static_cast<double>(t1-t0)/CLOCKS_PER_SEC << &amp;quot; sec.&amp;quot; << std::endl;

//    for(int n = 0; n < query.rows; ++n)
    for(int n = 0; n < 2; ++n)
    {
        std::cout << &amp;quot;  &amp;quot; << n << &amp;quot;-th query: &amp;quot;;
        for(int k = 0; k < numKnn; ++k)
        {
            std::cout << &amp;quot;(&amp;quot; << resultIndex[n][k] << &amp;quot;, &amp;quot; << resultDistance[n][k] << &amp;quot;), &amp;quot;;
        }
        std::cout << std::endl;
    }
}

int  main ()
{
    int numKnn = 6;
    flann::Matrix<float> dataset;
    flann::Matrix<float> query;
    loadData(dataset, query);
    printMatrix(dataset, &amp;quot;Reference&amp;quot;);
    printMatrix(query, &amp;quot;Query&amp;quot;);

//    std::vector< std::vector<int> > indices;
//    std::vector<std::vector<float> > dists;

    flann::Matrix<size_t> resultIndex;
    flann::Matrix<float> resultDistance;
    setSearchResults(query.rows, numKnn, resultIndex, resultDistance);

    for(int n = 0; n < indexFlannAlgorithm.size(); ++n)
    {
        testKnnSearch(
            indexFlannAlgorithm[n], numKnn,
            dataset, query, resultIndex, resultDistance
        );
    }

//    flann::save_to_file(resultIndex, &amp;quot;result.hdf5&amp;quot;, &amp;quot;result&amp;quot;);

    delete [] dataset.ptr();
    delete [] query.ptr();
    delete [] resultIndex.ptr();
    delete [] resultDistance.ptr();

    return 0;
}
0

FLANN

IndexParam:

  • LinearIndexParams: 全探索(brute-force)
  • KDTreeIndexParams: randomized kd-treesの集合をparallelに探索
    • treesの数は1-16が良い
  • KMeansIndexParams: 階層k-means tree
  • CompositeIndexParams: randomized kd-treeと階層k-meansの組み合わせ
  • KDTreeSingleIndexParams: single kd-treeを構築.低次元データの検索に向いている
  • HierarchicalClusteringIndexParams: 階層クラスタリング.任意のmetricに対応しているので,2値ベクトルのハミング距離にも使える
  • LshIndexParams: multi-probe LSH.2値ベクトルのハミング距離にのみ使える.
    • multi_probe_levelを0に設定すると一般的なLSH.
  • AutotunedIndexParams:randomized kd-trees, hierarchical kmeans, linearの中から最も良いindex typeを決定する
0

CMakeLists.txt for FLANN example

cmake_minimum_required(VERSION 2.8)

set(PROJ_NAME testFlann)
PROJECT(${PROJ_NAME})

# Prevent compilation in-source
if( ${CMAKE_BINARY_DIR} STREQUAL ${PROJECT_SOURCE_DIR} )
Message( FATAL_ERROR "In-source build is not allowed. Create a build directory and run cmake in the directory.")
endif()

# enable C++11
include(CheckCXXCompilerFlag)
CHECK_CXX_COMPILER_FLAG("-std=c++11" COMPILER_SUPPORTS_CXX11)
CHECK_CXX_COMPILER_FLAG("-std=c++0x" COMPILER_SUPPORTS_CXX0X)
if(COMPILER_SUPPORTS_CXX11)
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
elseif(COMPILER_SUPPORTS_CXX0X)
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++0x")
else()
message(STATUS "The compiler ${CMAKE_CXX_COMPILER} has no C++11 support. Please use a different C++ compiler.")
endif()

set(EXT_DIR ${CMAKE_SOURCE_DIR}/extern CACHE STRING "directory storing all external libraries")
list( APPEND CMAKE_MODULE_PATH
${EXT_DIR}
)
find_package(Flann REQUIRED)
find_package(HDF5 REQUIRED)

include_directories(${FLANN_INCLUDE_DIRS})
include_directories(${HDF5_INCLUDE_DIRS})

link_directories(${HDF5_LIBRARY_DIRS})

add_executable(${PROJ_NAME}
main.cpp
)
target_link_libraries(${PROJ_NAME}
${FLANN_LIBRARIES}
${HDF5_LIBRARIES}
)