0

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:

enter image description here

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

enter image description here

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.

Christoph Rackwitz
  • 11,317
  • 4
  • 27
  • 36
dtorpey
  • 1
  • 4
  • wait, you want a maximum-area **inscribed rectangle**? if you know it's an affine transform of a rectangle, there's maybe a closed-form solution, or at least it's a convex problem. – Christoph Rackwitz Apr 01 '22 at 22:28
  • @ChristophRackwitz yes, that's correct – dtorpey Apr 01 '22 at 22:29
  • such problems have been discussed here previously. no, I don't remember the question URLs or have them bookmarked. perhaps try https://stackoverflow.com/search?tab=newest&q=inscribed%20%20rectangle (and substitutions like rectangle/polygon etc) – Christoph Rackwitz Apr 01 '22 at 22:30
  • I'm a little late, but I'd bet there are multiple such rectangles. i.e. slide the red rectangle you drew up-right or down-left, and its area will be constant. So you'll also need a way to choose among all these solutions- maybe the one "in the middle" is good enough? – bogovicj Apr 07 '22 at 12:47

0 Answers0