Блог

У меня есть большой список точек на Изображении, и я хочу найти Точку, ближайшую к заданной Точке.

Опробован существующий подход: разделите изображение на фрагменты и выполните поиск только в интересующей области, построив Таблицу. Светло-голубые затуманенные точки — это точки, которые я сравниваю.

Проблемы Даже при очень небольшом количестве сравнений мой алгоритм занимает больше времени, чем фактическое. Есть ли какие-либо возможности для улучшения моего текущего подхода? Есть ли другой лучший подход?

Время выполнения на моей машине: время, затраченное на

 FindNearestPoint  : 0.021145 ms  
FindNearestPointV2: 0.047953 ms
  

Конфигурация ПК: Процессор Intel (R) Core (TM) i7-6820HQ с частотой 2,70 ГГц

 // 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 "opencv2opencv.hpp"
#include "opencv2opencv_modules.hpp"

using namespace cv;
using namespace std;

bool FindNearestPoint(const Point2f Point, const vector<Point2f>vPoints, int amp;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> amp;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 amp;Index,Mat amp;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)amp;amp;(Cluster.x < GridSize.width));
        CV_Assert((Cluster.y >= 0) amp;amp; (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 mst", TimeTaken_C);
            printf("FindNearestPointV2: %f mst", t_FindNearestPtV2.getElapsedTimeInMilliSec());
            printf("Speed: %f xn", 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;
}