I'm trying to do a piece-wise affine transform in Python.

I have one image with a set of points hand marked and another set of points where I wish to "move" my current points and the texture between.

This is my understanding of the transformation:

  1. Find the delaunay triangulation of the moved points
  2. For each pixel in the image, find the corresponding triangle
  3. Find the barycentric coordinates of the pixel for the triangle found in 2.

  4. Multiply the barycentric coordinates for the pixel in 3 and you have the coordinates of the pixel in the new image.

I ran some tests and I believe my understanding is correct. I have two bottlenecks in my code currently. First, finding out if a point is inside a triangle. For that I am using the algorithm from the wikipedia page.

The second bottleneck, and this is the real problem, is finding out the triangle a point belongs to (hence the title :)) I tried finding the distance from the points to the centers, then ordering the triangles in each iteration by the distance from its center to the point, but that doesn't always work. I believe the problem lies in the fact that I have to use the triangulation of the image I want and not from the image I have.

I figure the displacement of the points/triangles comes into play then, but I'm not sure how.

  • $\begingroup$ I realize this is a 4 year old question, and the original asker's account no longer even exists but... FYI for future googlers: if you are using Python like the original poster, scipy's Delaunay class has a find_simplex method for accomplishing exactly this task. $\endgroup$ – Chester Jun 8 '15 at 17:47

Two things:

1) For finding out what triangle a point belongs to, I'd recommend a gridding system - overlay a small (something in the range of 20x20 to 50x50, depending on how many points are in your triangulation) grid on top of your destination triangulation and bin all the triangles into each grid cell they overlap (this should be fairly quick; with the right resolution, many of your triangles will fall into a single cell and most of the rest will only straddle a couple). Then to determine which triangle a point belongs to, figure out which bin the point is in and test only the triangles that overlap that bin. There are other, similar schemes available but this is probably the simplest and it should be more than good enough for what you're doing.

2) Since you don't make it clear which way you're iterating in your description, I want to emphasize that you should be looping over the points in your destination image, not the points in your source image; if you loop over the points in the source image and forward-transform then you may wind up with holes in your destination image; by looping over your destination image and back-transforming to find the corresponding point in the source image, you eliminate this problem. Also, you almost certainly want to do some measure of antialiasing; the easiest thing to do is probably to subsample your destination image and do 4 or 9 samples for each destination pixel.

  • $\begingroup$ Could you explain the latter part of 2) better? I don't understand what you mean by subsampling. As for 1), I'll try that. Is there a good way to estimate the size of the bins/grids? For example, if I have an image 500x750 with 192 points? Or 640x480 with 58? Also, is there not a direct way to find the triangle? I can see how 1) would help, but this didn't seem like an intractable problem to me at first. Well, not like I have an answer either. $\endgroup$ – user7542 Feb 27 '11 at 4:54
  • $\begingroup$ Given that you're using a Delauney triangulation there's probably some means of finding triangles slightly more efficiently than that, but probably not 'efficiently enough' to be worth it, especially for the point counts you're talking about. As far as grid size, I'd suggest trial-and-error, but you want the (linear) size of a bin to be on the order of the average triangle size, so probably on the order of 10x10 for both problem instances you give... $\endgroup$ – Steven Stadnicki Feb 27 '11 at 6:27
  • $\begingroup$ As far as subsampling goes, the simplest way of thinking of it is as though your destination image were twice as large (or three times, or whatever) as it actually is, and that you're resizing it down to its 'proper' size once you've done the work for the larger image. It's a way of minimizing artifacting. $\endgroup$ – Steven Stadnicki Feb 27 '11 at 6:29

Your Answer

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