Aumentare l'efficienza del calcolo delle coordinate baricentriche in python

Question

Sfondo: sto tentando di deformare un volto con un altro di forma diversa.

Al fine di deformare un'immagine a un'altra, sto usando una triangolazione delaunay di punti di riferimento facciali e deformando i triangoli di un ritratto ai triangoli corrispondenti del secondo ritratto. Sto usando un sistema di coordinate baricentriche per mappare un punto all'interno di un triangolo nella sua posizione deformata corrispondente sull'altro triangolo.

Il mio primo approccio è stato risolvere il sistema Ax = b con il metodo di moltiplicazione inversa, dove A è costituito dai tre angoli del triangolo, b rappresenta il punto corrente e x rappresenta le coordinate baricentriche di questo punto (alfa, beta e gamma). Ho trovato l'inverso della matrice A una volta per triangolo, e quindi per ogni punto all'interno di quel triangolo calcolato le coordinate baricentriche trovando il prodotto punto di A^-1 e il punto b. Ho trovato questo molto lento (la funzione richiede 36 secondi per essere completata).

In seguito alla raccomandazione di altri post, ho tentato di utilizzare una soluzione dei minimi quadrati per migliorare l'efficienza di questo processo. Tuttavia, il tempo è aumentato a 154 secondi quando ho usato il metodo lsq di numpy. Credo che ciò sia dovuto al fatto che la matrice A viene calcolata ogni volta che il ciclo interno viene eseguito, mentre prima ero in grado di trovare l'inverso solo una volta, prima che inizino i due cicli.

La mia domanda è, come posso migliorare l'efficienza di questa funzione? C'è un modo per memorizzare la fattorizzazione di A in modo che ogni volta che viene calcolata la soluzione dei minimi quadrati per un nuovo punto, non si ripeta lo stesso lavoro?

Pseudocodice per questa funzione:

# 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

qui sono i miei suggerimenti, espresso nel vostro pseudocodice. Si noti che la vettorizzazione del loop sui triangoli non dovrebbe essere molto più difficile.

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