opencv find concave hull

Question

I have a set of discrete points shown in an image, like the following

I want to reconstruct or up sampling (I'm not sure what's the correct way to describe it) the image, so that the result image would be like the following. It doesn't need to be exactly the same as the example image, but the main idea is to fill up the original one.

I have an initial idea about how to do it. But I don't know how to do it after the first step. My idea is to first separate image using kmeans and find out the different objects. And I have successfully done it. The resulting images after kmeans are: .

After kmeans, I want to use find contour or something like concave to get the outline of these shapes and fill the shape using functions like fill holes. However, I found "find contour" does not work, it will consider each single pixel as a contour.

The other way I'm thinking is to use interpolation. But I'm not sure whether it is possible with so sparse points. Does anyone have any ideas about how to do this? I'm not sure whether I'm on the right way and I'm open to any solutions.

Thanks a lot!

Why

I don't think "upsampling" is the term you're looking for. – Medorra

@MarkRansom Yes, I'm not sure what is the right term to use. Any suggestions? – Why

Answer 1

Take a look at the morphological transformations. I would start with a dilation operation using a large kernel, say the MORPH_ELLIPSE with a size(15,15). Afterwards, thin the blobs back down using the erosion operation with the same size kernel. Take a look at the docs here. Note that OpenCV offers chained, or sequenced, morphological operations, too. See here. You'll then see that my suggestion is a "closing" operation.

Update: I experimented with simple dilation and contouring to yield the results shown in the image. The results appear to satisfy the general requirements of the problem.

Likewise, what "realtime" means for the application isn't specified, but this set of operations may be quickly executed and could easily be applied to a 30fps application.

Code snippet below:

// Convert image to grayscale
cvtColor(src, gray, CV_BGR2GRAY);
threshold(gray, gray, 128.0, 128.0, THRESH_BINARY);

// Dilate to fill holes
dilate(gray, dest, getStructuringElement(MORPH_ELLIPSE, Size(13,13)));

// Find contours
vector<vector<Point> > contours;
vector<Vec4i> hierarchy;
findContours(dest, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0,0)); 

  // Prune contours
  float maxArea = 0.0f;
  for (size_t i = 0; i< contours.size(); i++)
     {
       if (contourArea(contours[i]) >= maxArea)
         {
            maxArea = contourArea(contours[i]);
         }
     } 

  float minArea = 0.20f * maxArea;
  vector<vector<Point> > prunedContours;
  for (size_t i = 0; i< contours.size(); i++)
     {
       if (contourArea(contours[i]) >= minArea)
         {
           prunedContours.push_back(contours[i]);
         }
     }

// Smooth the contours
vector<vector<Point> > smoothedContours;
  smoothedContours.resize(prunedContours.size());
  for (size_t i=0;i<prunedContours.size();i++)
    {
    vector<float> x;
    vector<float> y;

    const size_t n = prunedContours[i].size();

    for (size_t j=0;j<n;j++)
      {
        x.push_back(prunedContours[i][j].x);
        y.push_back(prunedContours[i][j].y);
      }

    Mat G;
    transpose(getGaussianKernel(11,4.0,CV_32FC1),G);

    vector<float> xSmooth;
    vector<float> ySmooth;

    filter2D(x,xSmooth, CV_32FC1, G);
    filter2D(y,ySmooth, CV_32FC1, G);

    for (size_t j=0;j<n;j++)
      {
        smoothedContours[i].push_back(Point2f(xSmooth[j],ySmooth[j]));
      }
    }

Balcer

I have though about morphology. But this method is not stable if we have different objects and we can't do this in real time. – Why

Two comments: the above morph operations are reasonably fast and can likely be accelerated in GPU (depending on platform). Can you clarify "not stable"? This sounds another constraint on your problem since morph operations are usually considered stable (in the sense that they operate without much opportunity for surprise) – Balcer

What I mean by not stable is the morphology depends on what object you are using and how the different objects looks like. My system need to work in real time that no matter what object it is, it has to be done without tuning the parameters for morphology. – Why

Again, there must be other constraints in play: morphological operators seem to fit the stated needs very well, i.e. " I want to use find contour or something like concave to get the outline of these shapes and fill the shape using functions like fill holes." Morphological operators can fill the shapes illustrated in your images to yield a single contour containing the outline of each "object". – Balcer