Szablony OpenCV w zestawie danych punktów 2D

Question

Błąkałem się, jakie jest najlepsze podejście do wykrywania "figur" w tablicy punktów 2D.

W tym przykładzie mam dwa "szablony". Rysunek 1 to szablon, a rysunek 2 to szablon. Każdy z tych szablonów istnieje tylko jako wektor punktów o współrzędnej x, y.

Powiedzmy mamy trzeci wektor z punktów o współrzędnych x, y

Jaki byłby najlepszym sposobem, aby dowiedzieć się i odizolować punkty dopasowania jednego z pierwszych dwóch tablic w jednej trzeciej. (w tym skalowanie, obrót)?

staram najbliższych neigbours (FlannBasedMatcehr) lub nawet wdrożenie SVM ale nie wydaje się, żeby mnie żadnego rezultatu, szablon pasujący nie wydaje się być droga albo, myślę . Nie pracuję nad obrazami, ale tylko na punktach 2D w pamięci ...

Zwłaszcza, że ​​wektor wejściowy ma zawsze więcej punktów niż oryginalny zestaw danych, z którym ma być porównywany.

Wszystko, co musisz zrobić, to znaleźć punkty w tablicy pasujące do szablonu.

Nie jestem "specjalistą" w uczeniu maszynowym lub opencv. Chyba coś przeoczyłem od początku ...

Dziękuję bardzo za pomoc/sugestie.

Answer 1

tylko dla zabawy to próbowałem:

1. Wybierz dwa punkty punktu zbioru danych i obliczyć przekształcenie odwzorowania pierwsze dwa punkty wzór do tych punktów.
2. Sprawdź, czy wszystkie transformowane punkty wzoru znajdują się w zbiorze danych.

To podejście jest bardzo naiwne i ma złożoność O(m*n²) z n punktami danych i jednym wzorem o rozmiarze m (punkty). Ta złożoność może zostać zwiększona w przypadku niektórych metod wyszukiwania najbliższego sąsiada. Musisz więc zastanowić się, czy nie jest wystarczająco wydajny dla twojej aplikacji.

Niektóre ulepszenia mogą zawierać pewne heurystyki, aby nie wybrać wszystkich kombinacji kombinacji n², ale potrzebne są podstawowe informacje o maksymalnym skalowaniu wzoru lub coś podobnego.

Do oceny po raz pierwszy stworzył wzór:

Potem tworzyć losowe punkty i dodać wzór gdzieś wewnątrz (skalowane, obracane i przetłumaczone):

Po niektóre obliczenia ta metoda rozpoznaje wzór. Czerwona linia pokazuje wybrane punkty do obliczeń transformacji.

Oto kod:

// draw a set of points on a given destination image 
void drawPoints(cv::Mat & image, std::vector<cv::Point2f> points, cv::Scalar color = cv::Scalar(255,255,255), float size=10) 
{ 
    for(unsigned int i=0; i<points.size(); ++i) 
    { 
     cv::circle(image, points[i], 0, color, size); 
    } 
} 

// assumes a 2x3 (affine) transformation (CV_32FC1). does not change the input points 
std::vector<cv::Point2f> applyTransformation(std::vector<cv::Point2f> points, cv::Mat transformation) 
{ 
    for(unsigned int i=0; i<points.size(); ++i) 
    { 
     const cv::Point2f tmp = points[i]; 
     points[i].x = tmp.x * transformation.at<float>(0,0) + tmp.y * transformation.at<float>(0,1) + transformation.at<float>(0,2) ; 
     points[i].y = tmp.x * transformation.at<float>(1,0) + tmp.y * transformation.at<float>(1,1) + transformation.at<float>(1,2) ; 
    } 

    return points; 
} 

const float PI = 3.14159265359; 

// similarity transformation uses same scaling along both axes, rotation and a translation part 
cv::Mat composeSimilarityTransformation(float s, float r, float tx, float ty) 
{ 
    cv::Mat transformation = cv::Mat::zeros(2,3,CV_32FC1); 

    // compute rotation matrix and scale entries 
    float rRad = PI*r/180.0f; 
    transformation.at<float>(0,0) = s*cosf(rRad); 
    transformation.at<float>(0,1) = s*sinf(rRad); 
    transformation.at<float>(1,0) = -s*sinf(rRad); 
    transformation.at<float>(1,1) = s*cosf(rRad); 

    // translation 
    transformation.at<float>(0,2) = tx; 
    transformation.at<float>(1,2) = ty; 

    return transformation; 

} 

// create random points 
std::vector<cv::Point2f> createPointSet(cv::Size2i imageSize, std::vector<cv::Point2f> pointPattern, unsigned int nRandomDots = 50) 
{ 
    // subtract center of gravity to allow more intuitive rotation 
    cv::Point2f centerOfGravity(0,0); 
    for(unsigned int i=0; i<pointPattern.size(); ++i) 
    { 
     centerOfGravity.x += pointPattern[i].x; 
     centerOfGravity.y += pointPattern[i].y; 
    } 
    centerOfGravity.x /= (float)pointPattern.size(); 
    centerOfGravity.y /= (float)pointPattern.size(); 
    pointPattern = applyTransformation(pointPattern, composeSimilarityTransformation(1,0,-centerOfGravity.x, -centerOfGravity.y)); 

    // create random points 
    //unsigned int nRandomDots = 0; 
    std::vector<cv::Point2f> pointset; 
    srand (time(NULL)); 
    for(unsigned int i =0; i<nRandomDots; ++i) 
    { 
     pointset.push_back(cv::Point2f(rand()%imageSize.width, rand()%imageSize.height)); 
    } 

    cv::Mat image = cv::Mat::ones(imageSize,CV_8UC3); 
    image = cv::Scalar(255,255,255); 

    drawPoints(image, pointset, cv::Scalar(0,0,0)); 
    cv::namedWindow("pointset"); cv::imshow("pointset", image); 

    // add point pattern to a random location 

    float scaleFactor = rand()%30 + 10.0f; 
    float translationX = rand()%(imageSize.width/2)+ imageSize.width/4; 
    float translationY = rand()%(imageSize.height/2)+ imageSize.height/4; 
    float rotationAngle = rand()%360; 

    std::cout << "s: " << scaleFactor << " r: " << rotationAngle << " t: " << translationX << "/" << translationY << std::endl; 


    std::vector<cv::Point2f> transformedPattern = applyTransformation(pointPattern,composeSimilarityTransformation(scaleFactor,rotationAngle,translationX,translationY)); 
    //std::vector<cv::Point2f> transformedPattern = applyTransformation(pointPattern,trans); 

    drawPoints(image, transformedPattern, cv::Scalar(0,0,0)); 
    drawPoints(image, transformedPattern, cv::Scalar(0,255,0),3); 
    cv::imwrite("dataPoints.png", image); 
    cv::namedWindow("pointset + pattern"); cv::imshow("pointset + pattern", image); 



    for(unsigned int i=0; i<transformedPattern.size(); ++i) 
     pointset.push_back(transformedPattern[i]); 

    return pointset; 

} 

void programDetectPointPattern() 
{ 
    cv::Size2i imageSize(640,480); 

    // create a point pattern, this can be in any scale and any relative location 
    std::vector<cv::Point2f> pointPattern; 
    pointPattern.push_back(cv::Point2f(0,0)); 
    pointPattern.push_back(cv::Point2f(2,0)); 
    pointPattern.push_back(cv::Point2f(4,0)); 
    pointPattern.push_back(cv::Point2f(1,2)); 
    pointPattern.push_back(cv::Point2f(3,2)); 
    pointPattern.push_back(cv::Point2f(2,4)); 

    // transform the pattern so it can be drawn 
    cv::Mat trans = cv::Mat::ones(2,3,CV_32FC1); 
    trans.at<float>(0,0) = 20.0f; // scale x 
    trans.at<float>(1,1) = 20.0f; // scale y 
    trans.at<float>(0,2) = 20.0f; // translation x 
    trans.at<float>(1,2) = 20.0f; // translation y 

    // draw the pattern 
    cv::Mat drawnPattern = cv::Mat::ones(cv::Size2i(128,128),CV_8U); 
    drawnPattern *= 255; 
    drawPoints(drawnPattern,applyTransformation(pointPattern, trans), cv::Scalar(0),5); 

    // display and save pattern 
    cv::imwrite("patternToDetect.png", drawnPattern); 
    cv::namedWindow("pattern"); cv::imshow("pattern", drawnPattern); 

    // draw the points and the included pattern 
    std::vector<cv::Point2f> pointset = createPointSet(imageSize, pointPattern); 
    cv::Mat image = cv::Mat(imageSize, CV_8UC3); 
    image = cv::Scalar(255,255,255); 
    drawPoints(image,pointset, cv::Scalar(0,0,0)); 


    // normally we would have to use some nearest neighbor distance computation, but to make it easier here, 
    // we create a small area around every point, which allows to test for point existence in a small neighborhood very efficiently (for small images) 
    // in the real application this "inlier" check should be performed by k-nearest neighbor search and threshold the distance, 
    // efficiently evaluated by a kd-tree 
    cv::Mat pointImage = cv::Mat::zeros(imageSize,CV_8U); 
    float maxDist = 3.0f; // how exact must the pattern be recognized, can there be some "noise" in the position of the data points? 
    drawPoints(pointImage, pointset, cv::Scalar(255),maxDist); 
    cv::namedWindow("pointImage"); cv::imshow("pointImage", pointImage); 

    // choose two points from the pattern (can be arbitrary so just take the first two) 
    cv::Point2f referencePoint1 = pointPattern[0]; 
    cv::Point2f referencePoint2 = pointPattern[1]; 
    cv::Point2f diff1; // difference vector 
    diff1.x = referencePoint2.x - referencePoint1.x; 
    diff1.y = referencePoint2.y - referencePoint1.y; 
    float referenceLength = sqrt(diff1.x*diff1.x + diff1.y*diff1.y); 
    diff1.x = diff1.x/referenceLength; diff1.y = diff1.y/referenceLength; 

    std::cout << "reference: " << std::endl; 
    std::cout << referencePoint1 << std::endl; 

    // now try to find the pattern 
    for(unsigned int j=0; j<pointset.size(); ++j) 
    { 
     cv::Point2f targetPoint1 = pointset[j]; 

     for(unsigned int i=0; i<pointset.size(); ++i) 
     { 
      cv::Point2f targetPoint2 = pointset[i]; 

      cv::Point2f diff2; 
      diff2.x = targetPoint2.x - targetPoint1.x; 
      diff2.y = targetPoint2.y - targetPoint1.y; 
      float targetLength = sqrt(diff2.x*diff2.x + diff2.y*diff2.y); 
      diff2.x = diff2.x/targetLength; diff2.y = diff2.y/targetLength; 

      // with nearest-neighborhood search this line will be similar or the maximal neighbor distance must be relative to targetLength! 
      if(targetLength < maxDist) continue; 

      // scale: 
      float s = targetLength/referenceLength; 

      // rotation: 
      float r = -180.0f/PI*(atan2(diff2.y,diff2.x) + atan2(diff1.y,diff1.x)); 

      // scale and rotate the reference point to compute the translation needed 
      std::vector<cv::Point2f> origin; 
      origin.push_back(referencePoint1); 
      origin = applyTransformation(origin, composeSimilarityTransformation(s,r,0,0)); 
      // compute the translation which maps the two reference points on the two target points 
      float tx = targetPoint1.x - origin[0].x; 
      float ty = targetPoint1.y - origin[0].y; 

      std::vector<cv::Point2f> transformedPattern = applyTransformation(pointPattern,composeSimilarityTransformation(s,r,tx,ty)); 


      // now test if all transformed pattern points can be found in the dataset 
      bool found = true; 
      for(unsigned int i=0; i<transformedPattern.size(); ++i) 
      { 
       cv::Point2f curr = transformedPattern[i]; 
       // here we check whether there is a point drawn in the image. If you have no image you will have to perform a nearest neighbor search. 
       // this can be done with a balanced kd-tree in O(log n) time 
       // building such a balanced kd-tree has to be done once for the whole dataset and needs O(n*(log n)) afair 
       if((curr.x >= 0)&&(curr.x <= pointImage.cols-1)&&(curr.y>=0)&&(curr.y <= pointImage.rows-1)) 
       { 
        if(pointImage.at<unsigned char>(curr.y, curr.x) == 0) found = false; 
        // if working with kd-tree: if nearest neighbor distance > maxDist => found = false; 
       } 
       else found = false; 

      } 



      if(found) 
      { 
       std::cout << composeSimilarityTransformation(s,r,tx,ty) << std::endl; 
       cv::Mat currentIteration; 
       image.copyTo(currentIteration); 
       cv::circle(currentIteration,targetPoint1,5, cv::Scalar(255,0,0),1); 
       cv::circle(currentIteration,targetPoint2,5, cv::Scalar(255,0,255),1); 
       cv::line(currentIteration,targetPoint1,targetPoint2,cv::Scalar(0,0,255)); 
       drawPoints(currentIteration, transformedPattern, cv::Scalar(0,0,255),4); 

       cv::imwrite("detectedPattern.png", currentIteration); 
       cv::namedWindow("iteration"); cv::imshow("iteration", currentIteration); cv::waitKey(-1); 
      } 

     } 
    } 


}