Create an accurate boundary around 2D point cloud horizontal plane

Hello everyone,

I am dealing with creating an accurate boundary (concave hull) of a point cloud. I want to create the a polygon around it and compute the center of gravity using centroid function. None of the threshold values (0-1) give me a good result. I add here a resulting boundary colored in blue and the point cloud set colored in red. Is there any better approach using another function rather then boundary+polyshape??

[Matt J]

I advise you to attach the point cloud data in a .mat file so we can experiment with it.

[Image Analyst]

Perhaps you want the "Minimum perimeter polygon". Click Here

[Bruno Luong]

Perhaps you want the "Minimum perimeter polygon"

Look like we converge to TSP suggested bellow.

[Alexandru Mihai LAPADAT]

Here you have the point cloud. I tryed also TSP and did not work. After applying it and plotting the resulting sorted XY coordinates they were not correctly linked with a line.

[Matt J]

I tryed also TSP and did not work.

Are you going to show us what you did and what you got?

[John D'Errico]

That it did not work just means you did not properly formulate the Traveling Salesman Problem correctly, or solve it correctly, or correctly interpret the results, because it WILL work.

A better more useful way to approach this would have beento provide your data, show what you tried, then state why it is that you think it did not indeed work.

Answer 1

[Bruno Luong]

You might take a look at traveling saleman problem, there are several efficient implementation in File Exchange

[Bruno Luong]

I played with the data you provides (horizontal.txt) and TSP have the hard time to get the correct boundary for many reasons:

1. There are a too large number of points (> 29000)
2. Points seem to be inconsistent (double wall) and density varies greatly
3. The data you provide does not match your plot in the question

I think you might need to preprocess the data to facilitate the TSP algorithm.

For the record here is an old post that show TSP can solve such problem with reasonable data

Answer 2

[Matt J]

You can use alphaShape.

[Alexandru Mihai LAPADAT]

Alright. I linked the corners as good as alphaShape could perform by altering the 'a' threshold. I got something like this. Now how do you suggest to create a polyshape out of this?

[Alexandru Mihai LAPADAT]

Btw. this is another horizontal slice from my building

[Matt J]

bf = boundaryFacets(shp).';
pgon=polyshape(  shp.Points(bf(:),:)  )

[Alexandru Mihai LAPADAT]

Hello Matt,

I tryed your approach. It did not give the best result as you can see:

I also tryed to make the threshold for alphashape larger and used the rmholes function to get rid of the holes from my polyshape. The result was similar to what boundary gave me from the beginning. Do you have any furhter suggestions?

[Alexandru Mihai LAPADAT]

I also thought to order the point cloud based on kNN and then use the sorted point cloud to create a polyshape.

[John D'Errico]

You have largeholesin thatboundary. In order to span those holes, you need to use too large of an alpha. But in order to probe into the inside corners of that perimeter, you need a smaller alpha. So an alpha shape will have serious problems.

Before you could use an alpha shape, you would need to close those holes, using some (unspecified) pre-processing techniques.

[darova]

convhull() ?

[John D'Errico]

A convex hull will fail because the domain is not convex, so the area enclosed will be too large. Note that it was already requested to be able to improve this result to be better than a convex hull.

[darova]

Maybe you can examine each pair of points. If L > some length then create a triangle and see if there are points inside it

Answer 3

[John D'Errico]

As I thought about your problem, there is a simple solution. This is a TSP - a Traveling Salesman Problem. You want a closed solution, so the first and the last points will be the same. What I don't know is if those lines are thinned out. You want single pixels around the perimeter of that boundary, not multi-pixel thick lines. But given that, then just use a TSP solver. There are a few to be found on the File Exchange. Try this one, for example:

https://www.mathworks.com/matlabcentral/fileexchange/13680-traveling-salesman-problem-genetic-algorithm

Answer 4

[Image Analyst]

I'm guessing that you generally like the red shape (rather than the black outline shape) but you want the ends of the red pieces to be connected to the closest other piece so that the curve/boundary is closed. So you want "edge linking" (Google it).

One way is to

1. skeletonize the image with binaryImage = bwmorph(binaryImage, 'skel', inf)
2. find endpoints with binaryImage = bwmorph(binaryImage, 'endPoints')
3. label the blobs with labeledImage = bwlabel(binaryImage).
4. use a for loop to find the closest endpoints that are not on the same labeled blob
5. connect these endpoints with imline (attached demos might help)

Now all your end points will have a line connecting them to the nearest other piece. Now you can simply use imfill to make the shape solid, then use bwboundaries to get a list of (x,y) coordinates around the entire shape.

binaryImage = imfill(binaryImage, 'holes');
boundaries = bwboundaries(binaryImage);

The only steps that are slightly more than trivial are steps 4 and 5 but I'm sure you're smart enough to handle it. If not, let me know. Steps 1-3 area all one liners that I've already given you.

[Alexandru Mihai LAPADAT]

Hello Image Anlayst,

I am trying to implement what you said. First thing that I noticed is that step 2 is not extracting all endpoints from the skelleton.

Moreover, in step 4 I don't know how to search for closest endpoint using the binary 0-1 coordinates from binaryImage matrix. I will also add my attempt and the binary image of the horizontal slice from the building.

I also mention that right after connecting the endpoints I would like to get the x,y coordinates of the centroid from this slice. The x,y coordinates should match with the relative coordinates of the point cloud from which I created the binary image (binary.jpg).

Thank you.

[Alexandru Mihai LAPADAT]

I solved the first problem with the end points

Now I still need some help with step 4. I will update the code (horizslice.m) I used for step 1,2,3, the jpg. image which was converted into binary image. I will also add the actual x,y coordinates of the points (horizontal.txt).

[Alexandru Mihai LAPADAT]

Alright! I was able to link the end points using following code (https://www.mathworks.com/matlabcentral/fileexchange/35488-connect-randomly-ordered-2d-points-into-a-minimal-nearest-neighbor-closed-contour). Now I get something like this which is what I want:

now in order to completly solve this problem I am interested in the sorted real x,y coordinates of the point cloud from which the binary image was created. These coordinates will pe put in polyshape function. Furthermore, I will use centroid function on this polygon and get the center of gravity of this horizontal slice in real point cloud coordinates.

So last question will be: How can I get the coordinates of the sorted binary endpoints back in point cloud reference system?

Thank you

[Image Analyst]

Sorry - it was night time here so I wasn't able to work on your problem but glad you found a solution.

Since you have a different solution, I don't think you need to compute endpoints (like I suggested) anymore and thus don't need to sort them.

[Alexandru Mihai LAPADAT]

Well I need to sort them in order to throw them in polyshape function. But for this I need to go back to the point-cloud xy system after sorting them as binary points. Do you have any suggestion how to do this? I found some explanation in the following link: https://www.mathworks.com/matlabcentral/answers/50787-convert-an-image-pixel-coordinate-to-physical-coordinate?s_tid=answers_rc1-3_p3_Topic. But it did not work that well for me.

[Alexandru Mihai LAPADAT]

Hello Image Anayst

I did not find the solution on my problem with converting back to real point cloud coordinate system. Could you please help me with this. I also tryed to use the point2contour function directly on the x,y point cloud but did not give a great result. I really don't know how to solve it :(

[Image Analyst]

I thought you had the image in red. It appears now you just have a collection of point locations, not an image. To do anything with my suggestion, you'd have to create an image.

Again, you might want minimum perimeter polygon - I don't know.