python - 提高python中重心坐标计算的效率

Question

背景:我正在尝试将一张脸变形为另一张不同形状的脸。

为了将一幅图像变形为另一幅图像，我使用了面部特征的 delaunay 三角剖分，并将一幅肖像的三角形变形为第二幅肖像的相应三角形。我正在使用重心坐标系将一个三角形内的一个点映射到另一个三角形上相应的扭曲位置。

我的第一个方法是用逆乘法求解系统 Ax = b，其中 A 由三角形的三个角组成，b 代表当前点，x 代表该点的重心坐标(alpha，beta和 Gamma )。我为每个三角形找到一次矩阵 A 的逆矩阵，然后对于该三角形内的每个点，通过找到 A^-1 和点 b 的点积来计算重心坐标。我发现这非常慢(该功能需要 36 秒才能完成)。

根据其他帖子的推荐，我尝试使用最小二乘法来提高这个过程的效率。但是，当我使用 numpy 的 lsq 方法时，时间增加到 154 秒。我相信这是因为每次内部循环运行时 A 矩阵都会因式分解，而在我只能找到一次逆矩阵之前，在两个循环开始之前。

我的问题是，如何才能提高这个函数的效率呢？有没有一种方法可以存储 A 的因式分解，以便每次为新点计算最小二乘解时，都不会重复相同的工作？

这个函数的伪代码:

# 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

Answer 1

这是我的建议，用您的伪代码表达。请注意，矢量化三角形上的循环也不应该更难。

# 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)]