Matching results of Delaunay triangulation in OpenCV

1k views Asked by At

I have two sets of points - say A and B and both are the same size. I triangulate each of these sets using Delaunay triangulation in OpenCV with Subdiv2D class. The points in each set represent facial features of each face and I'm trying to sample texture within each triangle from set A and warp it to corresponding triangle from set B. Effectively, this would give me a kind of morphing one facial expression into another effect (just by warping the textures). Unfortunately, it turns out, that when I call getTriangleList method for set A and then for set B, triangle A_i does not correspond to triangle B_i. In other words, the triangle order is not the same as the order at which the points were added to each of the sets. I actually made a very simple test and I created set B as a copy of A and added constant value to x coordinate of each point in B, effectively shifting each point in B to the right. After triangulation, the order was broken again. Is there any way to keep track on which triangle is which? Without that, I am unable to properly warp from one shape to anohter (unless there's some other way to do that)

1

There are 1 answers

1
Max Walczak On BEST ANSWER

The question I asked above simply has no answer because there is no guarantee that two similar sets (A and B) with the same number, meaning and order of points will have the same topology after each of them is treated with Delaunay triangulation. In other words, if 3 points A_0 to A_2 make a triangle in A, points B_0 to B_2 don't neccesarily have to make a triangle in B (they can belong to two or more different triangles).

The solution I found is to create a map M(triangleId, pointIds) which correlates triangle id from A with vertexIds belonging to that triangleId from A. Next, I don't triangulate B at all - since the point order and meaning in B is the same as in A, I can apply the map M to B as well to triangulate B in exactly the same way, maintaining the topology. After that, the problem simply disappears. This obviously does not ensure that B will be properly triangulated according to Delaunay rule, however it solves my problem.