Finding simple shapes in 2D point clouds

Question

I'm currently looking for a way to fit a simple shape (like a T or L shape) to a two-dimensional cloud. As a result, I need the position and orientation of the form.

I am considering several approaches, but most of them seem very complicated and involve first creating and exploring a sample database. Since I am dealing with very simple forms, I was hoping there might be a simpler approach.

Answer 1

Saying that you do not want to do any training, I assume that you mean that you do not want to perform any functions; function mapping is used to make good guesses about the position (location and orientation) of the object in the image and will be applied together with RANSAC to your problem to guess and test good hypotheses about the position of the object.

The easiest approach is pattern matching, but it can be too computationally complicated (it depends on your use case). In comparison with the templates, you simply sort through the possible locations of the object and its possible orientations and possible scales and check how well the template matches (a cloud that looks like L or T at this location, as well as orientation and scale) (or you sample the possible orientations of the location and scales randomly). Template validation can be done pretty quickly if your points are organized (or you organize them, for example, converting them into pixels).

If this is too slow, there are many ways to speed up template creation, and I would recommend you a Generalized Hough transform. Here, before starting the search for patterns, you cross the border of the shape you are looking for (T or L), and for each point on its border you look at the direction of the gradient, and then the angle at this point between the direction of the gradient and the origin of the object’s pattern and the distance to origin of coordinates. You add this to the table (let's call it Table A ) for each boundary point, and you get a table that maps the direction of the gradient to the many possible places of origin of the object. Now you have created a two-dimensional voting space, which is actually just a 2D array (let's call it Table B ), where each pixel contains a number representing the number of votes for the object in this place. Then, for each point of the target image (point cloud), you check the gradient and find the set of possible locations of the objects found in Table A corresponding to this gradient, and then add one vote for all the corresponding objects in Table B (Howe space).

This is a very brief explanation, but knowing that you need to look for pattern matching and a generalized Hough transform, you can find the best explanations on the Internet. For instance. Take a look at Wikipedia pages for matching patterns and Hough transforms.

Answer 2

You may need to:

1- extract some functions from the image inside which you are looking for an object.

2- extract another set of features in the image of the object

3- map functions (methods such as SIFT can be used)

4- when you find a match, apply the RANSAC algorithm. it provides you with a transformation matrix (including translation, rotation information).

To use SIFT, start with here . it is actually one of the best source code written for SIFT. It includes the RANSAC algorithm, and you do not need to implement it yourself.

You can read about RANSAC here .