image processing - 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!

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]));
      }
    }