在Python中提高重心坐标的计算效率 [英] Increasing efficiency of barycentric coordinate calculation in python
问题描述
背景:我正在尝试将一张脸变形为另一张形状不同的脸.
Background: I'm attempting to warp one face to another of a different shape.
为了使一个图像变形为另一个图像，我使用了面部轮廓的delaunay三角剖分，并将一个肖像的三角形扭曲为第二个肖像的相应三角形.我正在使用重心坐标系来将三角形内的点映射到另一个三角形上其对应的变形位置.
In order to warp one image to another, I'm using a delaunay triangulation of facial landmarks and warping the triangles of one portrait to the corresponding triangles of the second portrait. I'm using a barycentric coordinate system to map a point within a triangle to its corresponding warped location on the other triangle.
我的第一种方法是使用逆乘法方法求解系统Ax = b，其中A由三角形的三个角组成，b表示当前点，x表示该点的重心坐标(alpha，beta和gamma).我找到每个三角形一次的矩阵A的逆，然后通过找到A ^ -1与点b的点积，为该三角形内的每个点计算重心坐标.我发现这非常慢(该功能需要36秒才能完成).
My first approach was to solve the system Ax = b with the inverse multiplication method, where A consists of the three corners of the triangle, b represents the current point, and x represents the barycentric coordinates of this point (alpha, beta, and gamma). I found the inverse of matrix A once per triangle, and then for every point within that triangle calculated the barycentric coordinates by finding the dot product of A^-1 and the point b. I found this to be very slow (the function takes 36 seconds to complete).
根据其他职位的建议，我尝试使用最小二乘解来提高此过程的效率.但是，当我使用numpy的lsq方法时，时间增加到了154秒.我相信这是由于以下事实:每次在内部循环运行时都会对A矩阵进行分解，而在两次循环开始之前，我只能一次找到逆矩阵.
Following the recommendation of other posts, I attempted to use a least squares solution to improve the efficiency of this process. However, the time increased to 154 seconds when I used numpy's lsq method. I believe this is due to the fact that the A matrix is factored every single time the inside loop runs, while before I was able to find the inverse only one time, before the two loops begin.
我的问题是，如何提高此功能的效率?有没有办法存储 A 的因式分解，以便每次为新点计算最小二乘解时，不会重复相同的工作?
My question is, how can I improve the efficiency of this function? Is there a way to store the factorization of A so that each time the least squares solution is calculated for a new point, it isn't repeating the same work?
此功能的伪代码:
# Iterate through each triangle (and get corresponding warp triangle)
for triangle in triangulation:
# Extract corners of the unwarped triangle
a = firstCornerUW
b = secondCornerUW
c = thirdCornerUW
# Extract corners of the warp triangle
a_prime = firstCornerW
b_prime = secondCornerW
c_prime = thirdCornerW
# This matrix will be the same for all points within the triangle
triMatrix = matrix of a, b, and c
# Bounding box of the triangle
xleft = min(ax, bx, cx)
xright = max(ax, bx, cx)
ytop = min(ay, by, cy)
ybottom = max(ay, by, cy)
for x in range(xleft, xright):
for y in range(ytop, ybottom):
# Store the current point as a matrix
p = np.array([[x], [y], [1]])
# Solve for least squares solution to get barycentric coordinates
barycoor = np.linalg.lstsq(triMatrix, p)
# Pull individual coordinates from the array
alpha = barycoor[0]
beta = barycoor[1]
gamma = barycoor[2]
# If any of these conditions are not met, the point is not inside the triangle
if alpha, beta, gamma > 0 and alpha + beta + gamma <= 1:
# Now calculate the warped point by multiplying by alpha, beta, and gamma
# Warp the point from image to warped image
推荐答案
以下是我的建议，以您的伪代码表示.请注意，对三角形上的循环进行矢量化也不会很困难.
Here are my suggestions, expressed in your pseudocode. Note that vectorizing the loop over the triangles should not be much harder either.
# Iterate through each triangle (and get corresponding warp triangle)
for triangle in triangulation:
# Extract corners of the unwarped triangle
a = firstCornerUW
b = secondCornerUW
c = thirdCornerUW
# Bounding box of the triangle
xleft = min(ax, bx, cx)
xright = max(ax, bx, cx)
ytop = min(ay, by, cy)
ybottom = max(ay, by, cy)
barytransform = np.linalg.inv([[ax,bx,cx], [ay,by,cy], [1,1,1]])
grid = np.mgrid[xleft:xright, ytop:ybottom].reshape(2,-1)
grid = np.vstack((grid, np.ones((1, grid.shape[1]))))
barycoords = np.dot(barytransform, grid)
barycoords = barycoords[:,np.all(barycoords>=0, axis=0)]
这篇关于在Python中提高重心坐标的计算效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
