I am computing some partitions in my work and would like to be able to extract informations in an automatic way when given a certain partition structure. To see what I have in mind, look at the photos attached below.

enter image description here enter image description here

Given the partition I can easily extract contours in 2D or triangulations of the surface of the cells in 3D.

Are there any "classic", not too complicated to implement methods which can put such objects (contours, surface triangulations) into classes which are similar modulo euclidean transformations?

In 2D the cells are close to being polygons, so extracting information in the number of neighbors can give a rough classification (pentagons, hexagons,...). In 3D, however things get more complicated and that is what interests me most.

  • $\begingroup$ OpenCV already has contour detection (docs.opencv.org/3.1.0/dd/d49/tutorial_py_contour_features.html), so have you tried using that? If I understood correctly what you're asking about 3d, then your image is still 2d, and extracting a 3d object from a 2d image is (I think?) a hard research problem, although there might be some standard libraries out there. $\endgroup$ – Kirill May 4 '17 at 21:59
  • $\begingroup$ @Krill: Thank you for pointing out OpenCV. In fact I have all the data, not just the image. I can construct triangulations of the surfaces. I just search an algorithm which can classify them, if it exists. $\endgroup$ – Beni Bogosel May 4 '17 at 22:29

I found a way to do the classification in 3D. It is not very rigorous, but it works very nice and it is not too expensive (less than one minute for 120 cells, which could probably be optimized further). The main idea is to use the "heuristic" that similar surfaces have similar Laplace-Beltrami spectrum.

The procedure is as follows: for each cell

  • compute a triangulation of the surface

  • compute the first 10 (for example) Laplace-Beltrami eigenvalues on this triangulation

  • Normalize the vector of eigenvalues (since dilated surfaces have rescaled eigenvalues)

Once I have these vectors for each cell, I compute the norms of the pairwise differences and I look for all norm differences below a certain treshold (in my case 0.01 seems to work fine). I applied this algorithm successfully on the 3D partition in the question and I obtained as expected four classes containing: 4 elements (corners), 36 elements (cells on the sides), 60 elements (cells in the interior of faces), 20 elements (cells in the interior of the pyramid).

So it seems like the spectrum is a nice indicator of likeliness.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.