Forums - Toy example to test KDTree

Hi everyone,

 

I have implemented a toy example of use of the fcvKDTreeCreate36s8f32, fcvKDTreeQuery36s8f32, fcvKDTreeDestroy36s8f32 functions (see below).

 

As the code shows, I am creating a KDTree from a 2D vectors (4 vectors), positions x, y of an input image of 7x7 (or larger). In this example, I am only searching for 2 nearest neighbors (maxNN) but this is not important. Once the KDTree is built, I look for the 2 NN of the point (1,3) (query[0][0]=1; query[0][1]=3;) with its inverse length (float32_t  queryInvLen = { 0.316 };).

 

The thing is that I think that this source code returns wrong neighbour values (or I do not know how to interpretate them).  In this case, it returns for the nearest ids (NNInds) and the distances (NNDists):

NNInds = {int [5]} 

 [0] = {int} 2

 [1] = {int} 3

 [2] = {int} -1929522108

 [3] = {int} 127

 [4] = {int} -1497824992

 

NNDists = {float [5]} 

 [0] = {float} 2

 [1] = {float} 2

 [2] = {float} -0.00000000000000941391062

 [3] = {float} 0.000000000000000000000000000000000000000000177964905

 [4] = {float} 0.00000000000000000000000000000000000000000000280259693

 

By the way, another thing that I do not understand is why it returns 5 values if I have initilisated these vectors to 2 nearest neighbours.

 

My question is wheter this toy example is right or wrong. If right, how I have to interpretate the results? If wrong, would you be so kind of telling me how to fix it?

 

Likewise, any further suggestion about how to improve the source code would be welcome.

 

//TEST FUNCTION FOR FASTCV
void KDTreeFastCV(){

    fcvSetOperationMode(FASTCV_OP_PERFORMANCE);

    int         maxNNs = 2;
    float32_t   maxDist = 100;
    int        maxChecks = 32;
    //uint8_t*     mask;
    int32_t    numNNsFound = 0;
    int32_t    NNInds[maxNNs];
    float32_t  NNDists[maxNNs];
    fcvKDTreeDatas8f32* kdtrees = 0;

    int8_t** vector2d =(int8_t**) fcvMemAlloc(4* sizeof(int8_t*), 16);
    for(int i=0; i<4; i++) {
        vector2d[i] = (int8_t *) malloc(2 * sizeof(int8_t));
    }

    vector2d[0][0]=1;   vector2d[0][1]=1;
    vector2d[1][0]=3;   vector2d[1][1]=4;
    vector2d[2][0]=5;   vector2d[2][1]=2;
    vector2d[3][0]=7;   vector2d[3][1]=7;

    //Length of a vector is its Euclidean norm, sqrt(x^2,y^2) for a 2D vector
    //invLength gives the 1/sqrt(x^2,y^2)
    float32_t   invLengths[4] = { 0.707, 0.2, 0.185, 0.101 };

    float32_t* invLenB = (float32_t*)fcvMemAlloc(4* sizeof(float32_t), 16);
    for (uint32_t i = 0; i<4; i++) {
        invLenB[i] = invLengths[i];
    }

    fcvKDTreeCreate36s8f32(*vector2d, invLenB, 4, &kdtrees);


    int8_t** query =(int8_t**) fcvMemAlloc(1* sizeof(int8_t*), 16);
    query[0] = (int8_t *) malloc(2 * sizeof(int8_t));

    query[0][0]=1;  query[0][1]=3;
    float32_t  queryInvLen = { 0.316 };

    fcvKDTreeQuery36s8f32 (kdtrees,  //Created tree
                           *query,        //query vector
                           queryInvLen,   //inverse length of query vector
                           maxNNs,        //max number of NNs to be found
                           maxDist,       //max distance between NN and query
                           maxChecks,     //max number of leafs to check
                           NULL,          //(pointer)
                           &numNNsFound,  //(pointer)for number of NNs found
                           NNInds,        //(pointer)array for indices of found NNs; must have maxNNs length
                           NNDists);      //(pointer)array for NN distances to query; must have maxNNs length

    fcvKDTreeDestroy36s8f32 (kdtrees);
}