Geometry lessons needed (aka finding a rectangle inside a rotated one)

So I have this project where I need to crop axis aligned patches out of a bigger scanned picture, containing rectangular color patches. The scan template can be transformed slightly; I build a transformation matrix and thus have access to its scale, translation and rotation values.

In other words: I want to extract an axis aligned rectangular image out of another rectangle that can be transformed one way or another. For this, I found the following code I translated to Xojo, and while it is working somewhat ok for tiny angles, it breaks for an angle of about 4° I am testing, producing negative values/rects which do not really match the conditions I am thinking of.

Anyone with a better knowledge of geometry here who can help me?
Thanks a lot!

Public Function rotatedRectWithMaxArea(w as double, h as double, angle as double) As Rect
  //Given a rectangle Of Size wxh that has been rotated by 'angle' (in
  //radians), computes the width And height Of the largest possible
  //axis - aligned rectangle(maximal area)within the rotated rectangle.
  If w <= 0 Or h <= 0 Then
    Return New Rect
  End If
  var side_long, side_short As Double
  var width_is_longer As Boolean = w >= h
  side_long = max(w, h)
  side_short = min(w, h)
  var x, wr, hr As Double
  //# since the solutions For angle, - angle And 180 - angle are all the same,
  //# If suffices To look at the first quadrant And the absolute values Of sin, cos :
  var sin_a As Double = abs(sin(angle))
  var cos_a As Double = abs(cos(angle))
  If side_short <= 2.0 * sin_a * cos_a * side_long Or abs(sin_a - cos_a) < 1e-10 Then
    //# half constrained Case : two crop corners touch the longer side,
    //# the other two corners are on the mid - line parallel To the longer line
    x = 0.5 * side_short
    If width_is_longer Then 
      wr = x / sin_a
      hr = x / cos_a
      wr = x / cos_a
      hr = x / sin_a
    End If
    // fully constrained Case : crop touches all 4 sides
    var cos_2a As Double
    cos_2a = cos_a * cos_a - sin_a * sin_a
    wr = w * (cos_a - h * sin_a) / cos_2a
    hr = (h * cos_a - w * sin_a) / cos_2a
  End If
  var w_bb As Double = w * cos_a + h * sin_a
  var h_bb As Double = w * sin_a + h * cos_a
  Return New Rect((w_bb - wr) / 2, (h_bb - hr) / 2, wr, hr)
End Function

This is why I say “it’s somewhat working”:
First image is from a scan that’s almost perfectly aligned. The color patches do not have black outlines; that’s the transformation matrix showing patch borders.
The smaller, more upright rectangle is the result of the algorithm above. Looks to me like the result could be wider, but sufficient for my purposes. On the original template both rectangles match exactly.

Bild 06.03.23 um 03.50

And here’s how the stronger transformed result looks like …

Bild 06.03.23 um 03.51

Hmm. Since you have a transformation matrix for the image, maybe it would be easier to simply rotate your image so that the swatches are aligned sufficiently such that you can simply extract the samples directly using regular coordinates?

I’d love to do so. Especially as the matrix works really well; I do not see any misplacements.
But we need an exact histogram of the extracted patches (rather 75% of it), and customer is concerned transformation could lead to some interpolation. That’s why I am (currently) looking for this tedious approach.

I knew you were going to say that. I’m all-too-familiar with color calibration swatches.

1 Like

Why don’t you do this: run a quick experiment by transforming the image and extracting the color swatches manually, and compare them to extractions from the un-transformed image. If you keep your extractions away from the edges, any interpolations should be negligible – the pixels in the extraction will be surrounded by pixels of the same swatch and shouldn’t introduce any color distortion.

I’m willing to bet the results are virtually identical.

I wonder if I shouldn’t go for a cheapo approach first. The scan will never be rotated extremely; I think that my experiment with 4° is more extreme than what any serious scan operator would produce. As I said I need only 75% of the patch, so I could just take the center of the translated patch and build a rectangle of the required size based on it.
Maybe, if I force my maths knowledge really hard, I could even implement some sanity checking for extreme angles.

And yes, I agree with your assumption. Otherwise rotating an object in an image processing app repeatedly would produce visible artefacts, I guess. But first let’s see if I can meet customer expectations.
Talking helped. Thanks!

If you were to fit an X-Y aligned square inside the rotated scan square, the scan angle can be as much as 9° off while still allowing you to get 75% coverage. That’s a pretty careless scan. :slight_smile:

1 Like

Yes, works great! Thank you!

Bild 06.03.23 um 05.34

THAT looks gorgeous! Good job!

Thank you. Thanks to Christian’s GraphicsMagickMBS plugin, that’s all pretty fast too. Getting full histogram data for almost 300 patches and their averaged color in just a few seconds.

Can I ask what kind of device you are calibrating?

Sure. And I am not sure in this case :smiley:
This is part of my work for a color management company, and while we started this subproject with Xerox copy/scan stations and a variety of printers in mind, I don’t know if it will be limited to these only in the end.
The main project supports a variety of measurement instruments mainly, but not limited to X-Rite, TechKon and Spectro.