Other Solutions

There are several solutions to the problem are known to the author:

1. This PerspectiveTransform, using matrixes based on SIMD Framework - Single instruction, multiple data.
2. Linear Equation using Apple Accelerate Framework is slow as it solves a generic polynomial.
3. An algebraic solution, which is spelled out linear equation calculations in a bunch of ugly code.
4. OpenCV, which requires large library installation (~250Mb) and is about 15-20 times slower.
5. Apple Core Image filters from CICategoryGeometryAdjustment suitable for UIImage transformations are slow and not applicable to views. See CIPerspectiveTransform and CIPerspectiveCorrection

Perspective Transformation

The homography is calculated here by constructing base homogeneous vectors. Since Homography=projective transformation=projectivity=collineation.

See paper on 2D projective transformations (homographies)

See Interactive Calculator in Javascript using CSS transform

Linear Equation

Using Accelerate Framework.

See this blog on Solving Linear Equations with Accelerate.

Unfortunately Accelerate is C-based and involve pointers:

dgetrs_( UnsafeMutablePointer(mutating: $0), &N, &NRHS, &inMatrix, &LDA, &pivots, &solution, &LDB, &error )

And this approach is slow as it taking generic solution. It runs 5 times slower on average then the best methods, see AccelerateSolvePerfTest

Algebraic

See QuadrilateralCalc.swift with working example, that looks like:

        let a = -H*(x2a*x3a*y14 + x2a*x4a*y31 - x1a*x4a*y32 + x1a*x3a*y42)
        let b = W*(x2a*x3a*y14 + x3a*x4a*y21 + x1a*x4a*y32 + x1a*x2a*y43)
        let c = H*X*(x2a*x3a*y14 + x2a*x4a*y31 - x1a*x4a*y32 + x1a*x3a*y42) - H*W*x1a*(x4a*y32 - x3a*y42 + x2a*y43) - W*Y*(x2a*x3a*y14 + x3a*x4a*y21 + x1a*x4a*y32 + x1a*x2a*y43)

        let d = H*(-x4a*y21*y3a + x2a*y1a*y43 - x1a*y2a*y43 - x3a*y1a*y4a + x3a*y2a*y4a)
        let e = W*(x4a*y2a*y31 - x3a*y1a*y42 - x2a*y31*y4a + x1a*y3a*y42)
        let f1 = (x4a*(Y*y2a*y31 + H*y1a*y32) - x3a*(H + Y)*y1a*y42 + H*x2a*y1a*y43 + x2a*Y*(y1a - y3a)*y4a + x1a*Y*y3a*(-y2a + y4a))
        let f2 = x4a*y21*y3a - x2a*y1a*y43 + x3a*(y1a - y2a)*y4a + x1a*y2a*(-y3a + y4a)
        let f = -(W*f1 - H*X*f2)

OpenCV

OpenCV (Open Source Computer Vision Library) provides two possible solutions: find homography and get perspective transform. See Perspective Transform & Homography Matrix compared in computer graphics.

findHomography

Find Homography method:

Mat cv::findHomography	( InputArray 	srcPoints,
                          InputArray 	dstPoints,
                          int           method = 0,
                          double 	ransacReprojThreshold = 3,
                          OutputArray 	mask = noArray(),
                          const int 	maxIters = 2000,
                          const double 	confidence = 0.995 )

See OpenCV findHomography() documentation

It solves generic plane homography in 3D space and thus is less efficient for 2D projection. It runs 20 times slower on average than other methods, see OpenCVPerformanceTest.swift. And from the maximum iterations parameter, we can infer it uses a cycle of multiple approximations to find the solution.

getPerspectiveTransform

From the latest docs getPerspectiveTransform returns 3x3 perspective transformation for the corresponding 4 point pairs.

Mat cv::getPerspectiveTransform	(const Point2f src[], const Point2f dst[])	

This method is more efficient than the previous, but still 15 times slower then matrix or algebraic solutions. Relies on linear equations solutions even less generic.

Core Image Filter

See blog A Look at Perspective Transform and Correction With Core Image. Core Image framework provides image detectors such as CIRectangleFeature to find image features, in this case, a perspective rectangle. However, rendering PNG image on top of JPEG will either inflate a JPEG size or likely to lose the sharpness of PNG.