Zwiększenie wydajności obliczania współrzędnych barycentrycznych w pythonie

Question

Tło: Próbuję wypaczyć twarz do innej o innym kształcie.

Aby wypaczyć jedno zdjęcie na drugie, używam delangadnej triangulacji charakterystycznych rysów twarzy i wypaczając trójkąty jednego portretu do odpowiednich trójkątów drugiego portretu. Używam barycentrycznego układu współrzędnych do mapowania punktu w trójkącie do odpowiadającej mu wypaczonej lokalizacji w drugim trójkącie.

Moje pierwsze podejście polegało na rozwiązaniu układu Ax = b metodą odwrotnego mnożenia, gdzie A składa się z trzech rogów trójkąta, b reprezentuje bieżący punkt, a x reprezentuje barycentryczne współrzędne tego punktu (alfa, beta i gamma). Znalazłem odwrotność macierzy A raz na każdy trójkąt, a następnie dla każdego punktu w tym trójkącie obliczono współrzędne barycentryczne, znajdując iloczyn punktowy A^-1 i punkt b. Zauważyłem, że jest to bardzo powolne (wykonanie tej funkcji zajmuje 36 sekund).

Zgodnie z zaleceniami innych stanowisk, próbowałem użyć rozwiązania najmniejszych kwadratów, aby poprawić efektywność tego procesu. Jednak czas ten wzrósł do 154 sekund, gdy użyłem metody numsu w lsq. Sądzę, że wynika to z faktu, że matryca A jest uwzględniana za każdym razem, gdy pętla wewnętrzna działa, podczas gdy zanim udało mi się znaleźć odwrotność tylko jeden raz, zanim zaczną się obie pętle.

Moje pytanie brzmi: jak mogę poprawić efektywność tej funkcji? Czy istnieje sposób na przechowywanie faktoryzacji A, aby za każdym razem, gdy obliczono najmniejsze kwadratowe rozwiązanie dla nowego punktu, nie powtórzyło się to samo?

Pseudokod dla tej funkcji:

# 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

Oto moje sugestie, wyrażone w Pseudokod. Zwróć uwagę, że wektoryzacja pętli nad trójkątami nie powinna być o wiele trudniejsza.

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