Erhöhung der Effizienz der baryzentrischen Koordinatenberechnung in Python

Question

Hintergrund: Ich versuche, ein Gesicht zu einem anderen mit einer anderen Form zu verzerren.

Um ein Bild zu einem anderen zu verzerren, verwende ich eine Delaunay-Triangulation von Gesichtsmarkierungen und verforme die Dreiecke eines Porträts zu den entsprechenden Dreiecken des zweiten Portraits. Ich verwende ein baryzentrisches Koordinatensystem, um einen Punkt innerhalb eines Dreiecks auf die entsprechende verzogene Position auf dem anderen Dreieck abzubilden.

Meine erste Annäherung war, das System Ax = b mit der inversen Multiplikationsmethode zu lösen, wobei A aus den drei Ecken des Dreiecks besteht, b den aktuellen Punkt darstellt und x die baryzentrischen Koordinaten dieses Punktes darstellt (Alpha, Beta und Gamma). Ich fand das Inverse der Matrix A einmal pro Dreieck und berechnete dann für jeden Punkt innerhalb dieses Dreiecks die baryzentrischen Koordinaten, indem das Punktprodukt von A^-1 und der Punkt b gefunden wurden. Ich fand das sehr langsam (die Funktion dauert 36 Sekunden).

Nach der Empfehlung anderer Beiträge, versuchte ich eine Kleinste-Quadrate-Lösung zu verwenden, um die Effizienz dieses Prozesses zu verbessern. Die Zeit stieg jedoch auf 154 Sekunden, als ich die lsq-Methode von numpy anwendete. Ich glaube, das liegt an der Tatsache, dass die A-Matrix jedes Mal, wenn die innere Schleife läuft, berücksichtigt wird, während ich zuvor nur einmal die Umkehrung finden konnte, bevor die beiden Schleifen beginnen.

Meine Frage ist, wie kann ich die Effizienz dieser Funktion verbessern? Gibt es eine Möglichkeit, die Faktorisierung von A zu speichern, so dass jedes Mal, wenn die Lösung der kleinsten Quadrate für einen neuen Punkt berechnet wird, nicht dieselbe Arbeit wiederholt wird?

Pseudocode für diese Funktion:

# 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

Hier meine Vorschläge sind, ausgedrückt in Ihrem Pseudo-Code. Beachten Sie, dass die Vektorisierung der Schleife über die Dreiecke auch nicht viel schwieriger sein sollte.

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