Image Perspective Distortion Filter

// Helper class: PerspectiveTransform
// Adapted from https://github.com/ivank-/PerspectiveTransform.js (Public Domain / Unlicense)
// ivank-'s version is a fork of https://github.com/Albergo/PerspectiveTransform.js (BSD-3-Clause like license)
// This class calculates coefficients for perspective transformation and its inverse.
class PerspectiveTransform {
    constructor(srcPts, dstPts) {
        // srcPts and dstPts are arrays of 8 values: [x0,y0, x1,y1, x2,y2, x3,y3]
        // Point order for this class: Top-Left, Top-Right, Bottom-Left, Bottom-Right
        // (x0,y0) = Top-Left
        // (x1,y1) = Top-Right
        // (x2,y2) = Bottom-Left
        // (x3,y3) = Bottom-Right
        
        this.coeffs = this._calculateCoefficients(srcPts, dstPts);
        this.coeffsInv = this._calculateCoefficients(dstPts, srcPts);
    }

    _gaussianElimination(matrix, N, rhs) {
        // Standard Gaussian elimination with partial pivoting to solve Ax = b
        // matrix is A (NxN), rhs is b (Nx1)
        
        // Forward elimination
        for (let i = 0; i < N; i++) {
            let maxRow = i;
            for (let j = i + 1; j < N; j++) {
                if (Math.abs(matrix[j][i]) > Math.abs(matrix[maxRow][i])) {
                    maxRow = j;
                }
            }

            // Swap rows in matrix and rhs vector
            [matrix[i], matrix[maxRow]] = [matrix[maxRow], matrix[i]];
            [rhs[i], rhs[maxRow]] = [rhs[maxRow], rhs[i]];

            // Check for singularity (pivot is too small)
            if (Math.abs(matrix[i][i]) <= 1e-10) { // Using 1e-10 as epsilon for zero
                return null; // Singular matrix, no unique solution
            }

            // Eliminate column i variable from subsequent rows
            for (let j = i + 1; j < N; j++) {
                const factor = matrix[j][i] / matrix[i][i];
                for (let k = i; k < N; k++) {
                    matrix[j][k] -= factor * matrix[i][k];
                }
                rhs[j] -= factor * rhs[i];
            }
        }

        // Back substitution to find solution x
        const solution = new Array(N);
        for (let i = N - 1; i >= 0; i--) {
            let sum = 0;
            for (let j = i + 1; j < N; j++) {
                sum += matrix[i][j] * solution[j];
            }
            solution[i] = (rhs[i] - sum) / matrix[i][i];
        }
        return solution; // Array of 8 coefficients: [a,b,c,d,e,f,g,h]
    }

    _calculateCoefficients(src, dst) {
        // Perspective transform equations:
        //   X = (ax + by + c) / (gx + hy + 1)
        //   Y = (dx + ey + f) / (gx + hy + 1)
        // (where src points are (x,y) and dst points are (X,Y))
        //
        // Rearranging them into a system of 8 linear DLT equations:
        //   X = ax + by + c - gXx - hXy
        //   Y = dx + ey + f - gYx - hYy
        // (This sets up an 8x8 matrix for the 8 unknown coefficients a,b,c,d,e,f,g,h)

        const r1 = [src[0], src[1], 1, 0, 0, 0, -dst[0] * src[0], -dst[0] * src[1]];
        const r2 = [0, 0, 0, src[0], src[1], 1, -dst[1] * src[0], -dst[1] * src[1]];
        const r3 = [src[2], src[3], 1, 0, 0, 0, -dst[2] * src[2], -dst[2] * src[3]];
        const r4 = [0, 0, 0, src[2], src[3], 1, -dst[3] * src[2], -dst[3] * src[3]];
        const r5 = [src[4], src[5], 1, 0, 0, 0, -dst[4] * src[4], -dst[4] * src[5]];
        const r6 = [0, 0, 0, src[4], src[5], 1, -dst[5] * src[4], -dst[5] * src[5]];
        const r7 = [src[6], src[7], 1, 0, 0, 0, -dst[6] * src[6], -dst[6] * src[7]];
        const r8 = [0, 0, 0, src[6], src[7], 1, -dst[7] * src[6], -dst[7] * src[7]];

        const matrix = [r1, r2, r3, r4, r5, r6, r7, r8];
        const rhs = [dst[0], dst[1], dst[2], dst[3], dst[4], dst[5], dst[6], dst[7]];
        const N = 8; // Number of equations/unknowns

        return this._gaussianElimination(matrix, N, rhs);
    }

    transform(srcX, srcY) {
        if (!this.coeffs) return null; // Singular matrix was detected during calculation
        const [a, b, c, d, e, f, g, h] = this.coeffs;

        const denominator = g * srcX + h * srcY + 1;
        if (Math.abs(denominator) < 1e-10) return null; // Avoid division by zero (point on vanishing line)

        const dstX = (a * srcX + b * srcY + c) / denominator;
        const dstY = (d * srcX + e * srcY + f) / denominator;
        return [dstX, dstY];
    }

    transformInverse(dstX, dstY) {
        if (!this.coeffsInv) return null; // Singular matrix was detected
        const [a, b, c, d, e, f, g, h] = this.coeffsInv;

        const denominator = g * dstX + h * dstY + 1;
        if (Math.abs(denominator) < 1e-10) return null; // Avoid division by zero

        const srcX = (a * dstX + b * dstY + c) / denominator;
        const srcY = (d * dstX + e * dstY + f) / denominator;
        return [srcX, srcY];
    }
}

function processImage(originalImg, dst_x0, dst_y0, dst_x1, dst_y1, dst_x2, dst_y2, dst_x3, dst_y3) {
    const W = originalImg.width;
    const H = originalImg.height;

    // Default destination points (no distortion). Parameters define the destination quadrilateral
    // Parameter order: Top-Left, Top-Right, Bottom-Right, Bottom-Left.
    dst_x0 = (dst_x0 === undefined) ? 0 : dst_x0;
    dst_y0 = (dst_y0 === undefined) ? 0 : dst_y0;
    dst_x1 = (dst_x1 === undefined) ? W : dst_x1;
    dst_y1 = (dst_y1 === undefined) ? 0 : dst_y1;
    dst_x2 = (dst_x2 === undefined) ? W : dst_x2;
    dst_y2 = (dst_y2 === undefined) ? H : dst_y2;
    dst_x3 = (dst_x3 === undefined) ? 0 : dst_x3;
    dst_y3 = (dst_y3 === undefined) ? H : dst_y3;
    
    // Source quadrilateral (entire image). Order for PerspectiveTransform class: TL, TR, BL, BR.
    const libSrcCorners = [
        0, 0, // Top-Left
        W, 0, // Top-Right
        0, H, // Bottom-Left
        W, H  // Bottom-Right
    ];

    // Destination quadrilateral (from function parameters). Must be mapped to PerspectiveTransform's expected order: TL, TR, BL, BR.
    // Input params are: (dst_x0,y0 TL), (dst_x1,y1 TR), (dst_x2,y2 BR), (dst_x3,y3 BL)
    const libDstCorners = [
        dst_x0, dst_y0, // Top-Left (from param dst_x0, dst_y0)
        dst_x1, dst_y1, // Top-Right (from param dst_x1, dst_y1)
        dst_x3, dst_y3, // Bottom-Left (from param dst_x3, dst_y3)
        dst_x2, dst_y2  // Bottom-Right (from param dst_x2, dst_y2)
    ];

    const transform = new PerspectiveTransform(libSrcCorners, libDstCorners);

    const minX = Math.min(dst_x0, dst_x1, dst_x2, dst_x3);
    const maxX = Math.max(dst_x0, dst_x1, dst_x2, dst_x3);
    const minY = Math.min(dst_y0, dst_y1, dst_y2, dst_y3);
    const maxY = Math.max(dst_y0, dst_y1, dst_y2, dst_y3);

    const canvasWidth = Math.round(maxX - minX);
    const canvasHeight = Math.round(maxY - minY);

    const canvas = document.createElement('canvas');
    
    if (canvasWidth <= 0 || canvasHeight <= 0) {
        canvas.width = Math.max(1, canvasWidth); // Ensure positive dimensions
        canvas.height = Math.max(1, canvasHeight);
        const ctx = canvas.getContext('2d');
        ctx.fillStyle = 'rgba(255,0,0,0.1)';
        ctx.fillRect(0,0,canvas.width,canvas.height);
        ctx.font = "10px Arial"; ctx.fillStyle = "red"; ctx.textAlign = "center";
        ctx.fillText("Error: Output has no area.", canvas.width/2, canvas.height/2, Math.max(0, canvas.width-4));
        return canvas;
    }
    
    canvas.width = canvasWidth;
    canvas.height = canvasHeight;
    const ctx = canvas.getContext('2d');

    if (!transform.coeffsInv) { // Matrix calculation failed (e.g. singular)
        console.error("Perspective transformation failed: singular matrix. Likely due to degenerate destination quadrilateral.");
        ctx.fillStyle = 'rgba(255,0,0,0.1)';
        ctx.fillRect(0,0, canvas.width, canvas.height);
        ctx.font = "12px Arial"; ctx.fillStyle = "red"; ctx.textAlign = "center";
        ctx.fillText("Error: Could not apply transform.", canvas.width/2, canvas.height/2, Math.max(0, canvas.width-4));
        return canvas;
    }
    
    const tempCanvas = document.createElement('canvas');
    tempCanvas.width = W; tempCanvas.height = H;
    const tempCtx = tempCanvas.getContext('2d', { willReadFrequently: true });
    tempCtx.drawImage(originalImg, 0, 0, W, H);
    const srcImageData = tempCtx.getImageData(0, 0, W, H);
    const srcPixels = srcImageData.data;

    const destImageData = ctx.createImageData(canvasWidth, canvasHeight);
    const destPixels = destImageData.data;

    for (let y = 0; y < canvasHeight; y++) {
        for (let x = 0; x < canvasWidth; x++) {
            const currentDstX = x + minX; // Coordinate in the space of libDstCorners
            const currentDstY = y + minY;

            const srcCoords = transform.transformInverse(currentDstX, currentDstY);
            let r = 0, g = 0, b = 0, a = 0;

            if (srcCoords) { // If transformInverse succeeded (non-null)
                const srcX = srcCoords[0];
                const srcY = srcCoords[1];

                // Check if the source point is within the original image bounds
                if (srcX >= 0 && srcX < W && srcY >= 0 && srcY < H) {
                    // Bilinear interpolation
                    const x_floor = Math.floor(srcX);
                    const y_floor = Math.floor(srcY);
                    // Clamp ceiling coordinates to be within image bounds (W-1, H-1)
                    const x_ceil = Math.min(W - 1, x_floor + 1);
                    const y_ceil = Math.min(H - 1, y_floor + 1);

                    const tx = srcX - x_floor; // Fractional part of x
                    const ty = srcY - y_floor; // Fractional part of y

                    // Indices for the four surrounding pixels in the source image data array
                    const p00_idx = (y_floor * W + x_floor) * 4;
                    const p10_idx = (y_floor * W + x_ceil) * 4;  // Pixel to the right
                    const p01_idx = (y_ceil * W + x_floor) * 4;  // Pixel below
                    const p11_idx = (y_ceil * W + x_ceil) * 4;   // Pixel diagonally down-right
                    
                    // Interpolate R, G, B, A channels
                    for (let i = 0; i < 4; i++) {
                        const c00 = srcPixels[p00_idx + i]; // Top-left
                        const c10 = srcPixels[p10_idx + i]; // Top-right
                        const c01 = srcPixels[p01_idx + i]; // Bottom-left
                        const c11 = srcPixels[p11_idx + i]; // Bottom-right

                        let interp_val = 
                            c00 * (1 - tx) * (1 - ty) +  // Weight for c00
                            c10 * tx * (1 - ty) +        // Weight for c10
                            c01 * (1 - tx) * ty +        // Weight for c01
                            c11 * tx * ty;               // Weight for c11
                        
                        if (i === 0) r = interp_val;
                        else if (i === 1) g = interp_val;
                        else if (i === 2) b = interp_val;
                        else if (i === 3) a = interp_val;
                    }
                }
            } // else: srcCoords is null or out of bounds, pixel remains transparent black (r,g,b,a = 0)
            
            const destIdx = (y * canvasWidth + x) * 4;
            destPixels[destIdx]     = r;
            destPixels[destIdx + 1] = g;
            destPixels[destIdx + 2] = b;
            destPixels[destIdx + 3] = a;
        }
    }

    ctx.putImageData(destImageData, 0, 0);
    return canvas;
}