1

I have picture on which I need to detect shape. To do this, I used template from which I shelled points, and then try to fit this points to my image for best matching. When I found best matching i need to draw curve around this points.

Problem is that taken points are not in order. (you can see on picture). How to sort points that curve will be with no "jumping", but smooth.

enter image description here

I tried with stable_sort() but without success.

stable_sort(points.begin(), points.end(), Ordering_Functor_y());
stable_sort(points.begin(), points.end(), Ordering_Functor_x());

Using stable_sort()

using stable_sort

For drawing i used this function:

polylines(result_image, &pts, &npts, 1, true, Scalar(0, 255, 0), 3, CV_AA);

Any idea how to solve this problem? Thank you.

Edit: Here is the code for getting points from template

for (int model_row = 0; (model_row < model.rows); model_row++)
{
    uchar *curr_point = model.ptr<uchar>(model_row);
    for (int model_column = 0; (model_column < model.cols); model_column++)
    {
        if (*curr_point > 0)
        {
            Point& new_point = Point(model_column, model_row);
            model_points.push_back(new_point);
        }
        curr_point += image_channels;
    }
}

In this part of code you can see where is the problem of points order. Is any better option how to save points in correct order, that i wont have problems with drawing contour?

mpour
  • 746
  • 5
  • 16
djpiky
  • 45
  • 9
  • 1
    what is not in order? your template points or your detected points? easiest would be to "shell out" your template points already in order. Otherwise in general i think you need to extract the contour with some higher method than sorting. you can try to start with the "convex hull" and use some heuristic to handle concavity. – Micka May 27 '14 at 08:42
  • another heuristic: start at one point. find the nearest neighbor. draw a line to that neighbor and remove/ignore the first point. find nearest neighbor to second point, draw line and remove second point. and so on. – Micka May 27 '14 at 08:45
  • @djpiky See the answer [here](http://answers.opencv.org/question/31515/sorting-contours-from-left-to-right-and-top-to/) might be helpful... – Haris May 27 '14 at 09:03
  • You do know OpenCV has a [drawContours](http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=drawcontours#void%20drawContours%28InputOutputArray%20image,%20InputArrayOfArrays%20contours,%20int%20contourIdx,%20const%20Scalar&%20color,%20int%20thickness,%20int%20lineType,%20InputArray%20hierarchy,%20int%20maxLevel,%20Point%20offset%29) function, right? – Aurelius May 27 '14 at 15:23

2 Answers2

0

Your current approach is to sort either the x or y values, and this is not the proper ordering for drawing the contour.

One approach could the following

  1. Caculate the center of mass of the detected object
  2. Place a polar coordinate system at the center of mass
  3. Calculate direction to all points
  4. Sort points by the direction coordinates

It will better than your current sorting, but might not be perfect.

A more involved approach is to determine the shortest path going through all the detected points. If the points are spread evenly around the contour this approach will locate the contour. The search term for this approach is the travelling salesman problem.

midtiby
  • 14,550
  • 6
  • 34
  • 43
0

I think you searching for Concave Hull algorithm. See here: http://ubicomp.algoritmi.uminho.pt/local/concavehull.html

Java implementation: here

Andrey Smorodov
  • 10,649
  • 2
  • 35
  • 42