# How to Efficiently Find a Neighbor Point in a List?

2

I have a large list of Points in an Image and I want to find the Point Nearest to a given Point.

Existing Approach Tried: Divide the Image into Tiles and search only within the Region of Interest by building a Table. The light blue cloured one are the points I'm comparing.

Problems Even with very fewer comparisons, my algorithm is taking more than the actual time. Is there any scope for improvement in my current approach? Is there any other better approach?

Run Times in my Machine: Time Taken for

FindNearestPoint  : 0.021145 ms
FindNearestPointV2: 0.047953 ms

PC Config: Intel(R) Core(TM) i7-6820HQ CPU @ 2.70 GHZ

// Feature Comparision.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include "Timer.h" //http://www.songho.ca/misc/timer/files/timer.zip

#include "opencv2\opencv.hpp"
#include "opencv2\opencv_modules.hpp"

using namespace cv;
using namespace std;

bool FindNearestPoint(const Point2f Point, const vector<Point2f>vPoints, int &Index )
{
CV_Assert(vPoints.size() != 0);

float PrevDistance = FLT_MAX;
Index = -1;//Error Case
for (size_t i = 0; i < vPoints.size(); i++)
{
float Distance = cv::norm(Point - Point2f(vPoints[i].x, vPoints[i].y));

if (Distance < PrevDistance)
{
Index = i;
PrevDistance = Distance;
}
}
return true;

}

static inline bool GetListofClustersToProcess(const Point2f Pt, const Point2f szTileSize, const Size GridSize, vector<Point> &ClusterIndices)
{
Point Index(Pt.x* szTileSize.x, Pt.y * szTileSize.y);
vector<Point> vClusterIndices;

//Prev Tile
vClusterIndices.push_back(Index + Point(-1, -1));//Prev Tile
vClusterIndices.push_back(Index + Point(-1, 0)); //Curr Tile
vClusterIndices.push_back(Index + Point(-1, 1)); //Next Tile

vClusterIndices.push_back(Index + Point(0, -1)); //Prev Tile
vClusterIndices.push_back(Index + Point(0, 0)); //Curr Tile
vClusterIndices.push_back(Index + Point(0, 1)); //Next Tile

vClusterIndices.push_back(Index + Point(1, -1)); //Prev Tile
vClusterIndices.push_back(Index + Point(1, 0));     //Curr Tile
vClusterIndices.push_back(Index + Point(1, 1));     //Next Tile

for (size_t i = 0; i < vClusterIndices.size(); i++)
{
Index = vClusterIndices[i];
if ((Index.x < 0) || (Index.x >= GridSize.width) || (Index.y < 0) || (Index.y >= GridSize.height))
{
continue;
}
ClusterIndices.push_back(Index);
}

return true;
}

bool FindNearestPointV2(const Point2f Point, const vector<Point2f>vPoints,const vector<vector<vector<int>>>vClusters,const Point2f szTileSize, const Size GridSize, int &Index,Mat &mDebugImage)
{
#define EnableDebug 0

CV_Assert(vPoints.size() != 0);

vector<cv::Point> ClusterIndices;
ClusterIndices.clear();

GetListofClustersToProcess(Point, szTileSize,GridSize, ClusterIndices);

float PrevDistance = FLT_MAX;

Index = -1;//Error Case
int KeypointIdx = 0;

for (size_t iClusterIdx = 0; iClusterIdx < ClusterIndices.size(); iClusterIdx++)
{
cv::Point Cluster(ClusterIndices[iClusterIdx]);

CV_Assert((Cluster.x >= 0)&&(Cluster.x < GridSize.width));
CV_Assert((Cluster.y >= 0) && (Cluster.y < GridSize.height));

for (size_t i = 0; i < vClusters[Cluster.y][Cluster.x].size(); i++)
{
KeypointIdx = vClusters[Cluster.y][Cluster.x][i];

CV_Assert(KeypointIdx < vPoints.size());

float Distance = cv::norm(Point - Point2f(vPoints[KeypointIdx].x, vPoints[KeypointIdx].y));

#if EnableDebug
circle(mDebugImage, vPoints[KeypointIdx], 2, Scalar(255, 255, 0), 2);

imshow("Input Features", mDebugImage);
#endif
//New Optimized Implementation
//waitKey();

if (Distance < PrevDistance)
{
Index = KeypointIdx;
PrevDistance = Distance;
}
}
}
return true;

}

int main(int argc, char* argv[])
{
/*TestKNN();
return 0;*/

Size ImageSize(900, 300);
Mat mInputImage(ImageSize, CV_8UC3, Scalar::all(0));
RNG rng(0xFFFFFFFF);
vector<Point2f>vKeypoints;
int MaxNoOfKeypoints = 2000;
uint16_t maxFilteredKeypoints = 350;
int TileSize = 32;//Tile Size in Pixels
Size GridSize((ImageSize.width / TileSize)+1, (ImageSize.height / TileSize)+1);
vector<vector<vector<int>>>vClusters;
Point ptTileIdx(0,0);
Point2f PtQuery,PtNearestPoint, PtNearestPointV2;
Point2f GridScale((float)GridSize.width / (float)ImageSize.width, (float)GridSize.height / (float)ImageSize.height);
int NoOfTestPoints = 100, Iteration = 0;

for (;;)
{
vKeypoints.clear();
vClusters.clear();
mInputImage.setTo(0);
//Generating Random Keypoints
for (size_t i = 0; i < MaxNoOfKeypoints; i++)
{
vKeypoints.push_back(Point2f(rng.uniform(0, ImageSize.width), rng.uniform(0, ImageSize.height)));
}

cout << "Grid Size :" << GridSize << "\n";
for (size_t iVerTile = 0; iVerTile < GridSize.height; iVerTile++)
{
vector<vector<int>>HorTiles;
Scalar color = Scalar(rng.uniform(0, 255), rng.uniform(0, 255), rng.uniform(0, 255));
for (size_t iHorTile = 0; iHorTile < GridSize.width; iHorTile++)
{
Rect TileRect(iHorTile*TileSize, iVerTile*TileSize, TileSize, TileSize);
rectangle(mInputImage, TileRect, color, 1);
color += Scalar(0, 0, 10);
HorTiles.push_back(vector<int>());
}
vClusters.push_back(HorTiles);
}
printf("Cluster Size : %d , %d \n",vClusters.size(),vClusters[0].size());

//Classify Tile Idx for all the Keypoints
for (size_t i = 0; i < MaxNoOfKeypoints; i++)
{
ptTileIdx.x = (int)(vKeypoints[i].x / TileSize);
ptTileIdx.y = (int)(vKeypoints[i].y / TileSize);
vClusters[ptTileIdx.y][ptTileIdx.x].push_back(i);
}

//Displaying the Keypoints
for (size_t i = 0; i < MaxNoOfKeypoints; i++)
{
circle(mInputImage, vKeypoints[i], 2, Scalar(255, 0, 0), 2);
}
Mat mInputTestImage = mInputImage.clone();
Iteration = 0;
while (Iteration<NoOfTestPoints)
{
PtQuery = Point2f(rng.uniform(0, ImageSize.width), rng.uniform(0, ImageSize.height));

circle(mInputTestImage, PtQuery, 4, Scalar(0, 255, 0), 4);
circle(mInputTestImage, PtQuery, 2, Scalar(0, 0, 255), 2);

int NearestPointIndex = -1, NearestPointIndexV2 = -1;
Timer t_FindNearestPt;
t_FindNearestPt.start();

FindNearestPoint(PtQuery, vKeypoints, NearestPointIndex);

t_FindNearestPt.stop();

PtNearestPoint = vKeypoints[NearestPointIndex];

Timer t_FindNearestPtV2;
t_FindNearestPtV2.start();
//New Optimized Implementation
FindNearestPointV2(PtQuery, vKeypoints, vClusters, GridScale, GridSize, NearestPointIndexV2,mInputTestImage);

t_FindNearestPtV2.stop();

PtNearestPointV2 = vKeypoints[NearestPointIndexV2];

if (NearestPointIndexV2 != -1)
{
circle(mInputTestImage, PtNearestPointV2, 2, Scalar(0, 0, 255), 2);
}
if (NearestPointIndex != -1)
{
circle(mInputTestImage, PtNearestPoint, 2, Scalar(0, 255, 0), 2);
}

if (NearestPointIndex != NearestPointIndexV2)
{
printf("[Error] Closest Point not Matching! \n");
cout << "Point" << PtQuery <<  " Org" << PtNearestPoint << "!= V2 " << PtNearestPointV2 << "\n";
float Distance = cv::norm(PtQuery - PtNearestPoint);
float DistanceV2 = cv::norm(PtQuery - PtNearestPointV2);
printf("Distance : %f - %f  \n", Distance, DistanceV2);
}
/*else
{
printf("[Passed] Closest Point Matching! \n");
}*/
float TimeTaken_C = t_FindNearestPt.getElapsedTimeInMilliSec();
printf("Time Taken for FindNearestPoint  : %f ms\t", TimeTaken_C);
printf("FindNearestPointV2: %f ms\t", t_FindNearestPtV2.getElapsedTimeInMilliSec());
printf("Speed: %f x\n", TimeTaken_C/t_FindNearestPtV2.getElapsedTimeInMilliSec());

imshow("Input Features", mInputTestImage);
Iteration++;
char key = (char)waitKey();
if (key == 27 || key == 'q' || key == 'Q') // 'ESC'
break;
mInputTestImage= mInputImage.clone();
}

char key = (char)waitKey();
if (key == 27 || key == 'q' || key == 'Q') // 'ESC'
break;
}

return 0;
}
c++
c
algorithm
opencv
nearest-neighbor
asked on Stack Overflow Sep 9, 2020 by Balaji R • edited Sep 9, 2020 by Balaji R