I am trying to get my head around generalising this problem to a random perspective transformation.

For example, I want to crop the maximum area rectangle of the resulting quadrilateral.

from skimage import transform
from skimage.data import astronaut
import matplotlib.pyplot as plt

image = astronaut()

M = transform.AffineTransform(scale=0.4, translation=40, shear=0.3)

warped = transform.warp(image, M.inverse)

plt.imshow(warped)
plt.show()

results in:

And I want to be able to find the maximum area crop of the resulting quadrilateral, i.e. this (the red rectangle):

How can I do this? Any help is greatly appreciated.

I've tried casting the problem as a constrained optimisation problem, and solving it using scipy.optimize.minimize. Basically, I solve for [x, y, w, h], and minimise - w * h (negative area, since it's minimisation), subject to the constraints that the each corner of the max-area rectangle must be inside the resulting quadrilateral.

However, this doesn't work correctly for many cases, including a plethora of edge cases. Further, it seems highly inefficient, and there seems like there should be an analytical solution to this.

Hopefully it's easy enough to do with just opencv or skimage, though.